CPU 스케줄링

CPU 스케줄링

CPU 스케줄링 이란?

• 준비 큐의 프로세스들 중에서 CPU를 할당할 순서를 정하는 것
• 운영체제의 단기 스케줄러가 수행함

---

언제 CPU 스케줄링을 할까?

1. 실행 상태에서 대기 상태로 전환될 때
2. 실행 상태에서 준비 상태로 전환될 때
3. 대기 상태에서 준비 상태로 전환될 때
4. 종료할 때

---

CPU 스케줄링 기준

1. CPU 사용률(Utilization)
   • 단위 시간당 CPU 사용시간의 비율
2. 처리량(Throughput)
   • 단위 시간당 완료된 프로세스의 개수
3. 반환시간(Turnaround time)
   • 특정 프로세스를 실행하는데 걸린 총 시간
4. 대기시간(Waiting time)
   • 프로세스가 준비 큐에서 대기하면서 기다린 시간의 합
5. 응답시간(Response time)
   • 작업을 요청한 후 첫번째 응답이 나올 때까지의 시간

---

선점(preemptive)과 비선점(nonpreemptive)

• 선점 : CPU를 사용하던 프로세스가 CPU를 빼앗김
• 비선점 : CPU가 한 프로세스에 할당되면, 프로세스가 CPU를 반환할 때까지 CPU를 사용함

---

CPU 스케줄링 알고리즘

FCFS(First-Come, First-Served) : 비선점식

• 프로세스가 준비큐에 도착한 순서대로 처리하는 알고리즘
• Convoy effect 발생가능
  • 실행시간이 짧은 프로세스가 긴 프로세스 뒤에서 기다리는 것
• 비선점식 방식이므로 자신이 CPU를 반납하기 전까지는 CPU를 계속 점유함
• 시분할 시스템에 사용할 수 없음
  

---

SJF(Shortest-Job-First) : 비선점식

• 각 프로세스의 다음 CPU 버스트 크기를 비교하여 가장 작은 것을 가진 프로세스에게 CPU를 할당함

  • 버스트 크기가 작은 프로세스 부터 처리해야 평균 대기시간이 작아지기 때문
  

---

SRTF(Shortest-Remaining-Time-First) : 선점식

• 선점식 SJF
• 새로 도착하는 프로세스가 생겼을때, 새 프로세스의 CPU 버스트 크기가 현재 실행 중인 프로세스의 남아있는 CPU 버스트보다 작다면 새 프로세스에게 CPU를 할당함

<다음 CPU 버스트 크기 결정>

• 정확한 값은 알 수 없고, 예측해서 사용한다
• 이전 CPU 버스트의 크기를 이용하여 지수 평균(exponential averaging) 방법을 사용해서 추정
  

---

RR(Round Robing) : 선점식

• 시분할 시스템을 위해 만들어짐
• 각 프로세스는 시간할당량 동안 CPU를 할당 받는다. 시간량은 보통10~100 밀리초이다. 이 시간이 지나면 프로세스는 CPU를 빼앗기고 준비 큐의 끝에 들어간다
• 준비큐는 선입 선출 방식이다.
• 운영체제는 타이머 인터럽트를 설정하여 주기적으로 인터럽트를 일으킨다. 인터럽트가 발생하면 , 운영체제가 실행되므로 이때 스케줄러를 실행한다

시간 할당량 : 2

<RR 스케줄링의 시간할당량>

• 시간 할당량이 크면 FCFS 방식이 된다
• 시간 할당량이 적다면, Context Switch의 부담이 증가한다
• 대부분의 CPU버스트 시간은 10밀리초 미만이므로 시간할당량을 10정도로 설정하면 스스로 CPU를 반환하므로 Context Switch 부담이 줄어든다.

---

Multilevel Queue : 선점식

• 준비 큐를 여러 개의 큐로 나눈다

  • 전면 작업(대화식) : 빠른응답 시간을 요구함 - RR
  • 후면 작업(일괄처리) : FCFS

• 각 큐는 낮은 우선순위의 큐보다 절대적인 우선순위를 가진다.

• 우선순위가 높은 큐의 프로세스가 처리되지 않으면 낮은 우선순위 큐에 있는 프로세스는 처리될 수 없다

• 문제점 : 기아상태

  • 우선순위가 낮은 큐의 프로세스가 영영 실행되지 못하는 경우 발생

• 해결법 : 각 큐는 CPU의 일정량을 분배 받음

  • 전면 작업은 CPU의 80%, 후면 작업은 CPU의 20%

---

Multilevel Feedback Queue : 선점식

• 프로세스가 큐 사이를 이동하는 Multilevel Queue 방식
• CPU를 많이 사용하는 프로세스는 낮은 우선순위 큐로 이동시킨다
• 입출력 중심, 대화식 프로세스들은 높은 우선순위 큐로 이동시킨다
• 높은 우선순위의 큐가 비어야 낮은 우선순위의 큐의 프로세스가 실핼 될 수 있다. 낮은 우선순위의 큐의 프로세스가 실행되는 도중, 높은 우선순위의 큐에 프로세스가 들어오면 선점된다
• 문제점 : 기아상태
  • 우선순위가 낮은 큐의 프로세스가 영영 실행되지 못하는 경우 발생
• 해결법 : 에이징
  • 낮은 우선순위의 큐에서 오래 대기하는 프로세스들을 높은 우선순위의 큐로 이동

---

HRN(Hightest Response-rate Next) : 비선점식

• 가변식 우선순위의 비선점식 스케쥴링
• 우선순위가 높은 프로세스에게 먼저 CPU를 할당
• 우선순위 = (대기시간+CPU burst) / CPU burst
• 따라서 CPU burst가 짧을수록 우선순위가 높고, 오래 대기할수록 우선순위가 높다