[OS] CPU스케줄링 - 스케줄링 알고리즘

- CPU스케줄러(CPU scheduler)

  CPU가 유휴상태가 될 때마다, 운영체제는 준비 완료 큐(ready queue)에 있는 프로세스들 중 하나를 선택해 실행해야 한다. 선택 절차는 short term(단기) 스케줄러에 의해 수행된다.

* short term scheduler = CPU scheduler

  CPU 스케줄러는 ready queue에 있는 어느 프로세스에게 CPU를 할당할 것인지를 결정하는 문제를 다룬다. 이에는 여러가지 알고리즘들이 존재한다.

 

---

 

1.     선입 선처리 스케줄링(First-Come, First-Served Scheduling)

  비선점 알고리즘이다. 가장 간단한 CPU스케줄링 알고리즘이며 FIFO라고도 한다. CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당 받는다.

FCFS 스케줄링 Gantt차트

  여기서 각각의 turnaround time은 25, 30, 33이며 평균 대기 시간은 (0+25+30)/3=18.33이다. 이때 프로세스의 순서를 P3, P2, P1순으로 바꾸어주면 (0+3+8)/3=3.66으로 크게 줄어든다.

* convoy effect(호위효과) : 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU가 양도하기를 기다리는 것을 말한다. 호위효과는 작을수록 좋다.

 

2.     최단 작업 우선 스케줄링(Shortest-Job-First Scheduling)

  SJF 스케줄링은 장기 스케줄링에서 자주 사용된다. 이 스케줄링은 선점일 수도 있고 비선점일 수도 있다. CPU의 버스트 길이를 연관시켜 구현하였다.

SJF 스케줄링 - 비선점형 Gantt차트

  평균 대기 시간은 (3+0+16+9)/4=7이다. 하지만 SJF의 어려움은 다음 CPU의 길이를 파악하는 것이다. 다음 burst(프로세스)는 지수 평균한 것으로 예측한다. 아래는 선점형 SJF알고리즘을 통해 구현한 스케줄링이다.

 

SJF 스케줄링 - 선점형 Gantt차트

3.     라운드 로빈 스케줄링(Round-Robin Scheduling)

  RR알고리즘은 선점형 알고리즘으로, 시분할 시스템을 위해 설계되었다. FCFS스케줄링과 비슷하지만 시스템이 프로세스들 사이를 옮겨 다닐 수 있도록 선점이 추가된다. 시간 할당량(time quantum) 또는 time slice라는 시간의 '단위'를 정의하여 구현한다. 어떤 프로세스가 이 단위 시간을 지나면 실행을 강제로 다른 프로세스에게 선점시키는 것이다. 일반적으로 time quantum은 10에서 100밀리초 동안이다.

RR 스케줄링 Gantt차트

  평균 대기시간은 (0+5+6+9)/4=5밀리초이다. 반응 시간의 정의는 처음 반응한 시간이기 때문에 P2의 반응 시간은 3밀리초이다. RR 알고리즘의 성능은 time quantum(시간 할당량)의 크기에 매우 큰 영향을 받는다. time quantum이 너무 큰 경우에는 FCFS와 같아질 것이며 time quantum이 너무 작아진다면 context switch가 자주 일어나 프로세스의 실행이 느려질 수 있다.

 

4.     다단계 큐 스케줄링(Multilevel Queue Scheduling)

  다단계 큐 스케줄링 알고리즘은 foreground(대화형) 프로세스와 background(일괄처리) 프로세스들을 구분한다. 이들 두 유형의 프로세스는 응답시간에 대한 요구사항이 다르기 때문에, 스케줄링 요구 또한 다를 것이다. 다단계 큐 스케줄링 알고리즘은 ready queue를 다수의 별도의 큐로 구분하여 각 큐는 자신의 스케줄링 알고리즘을 가지고 있다.

각 큐는 우선순위를 가진다.

     1. 시스템 프로세스

     2. 대화형 프로세스

     3. 대화형 편집 프로세스

     4. 일괄처리 프로세스

     5. 학생 프로세스

  시스템 프로세스가 가장 높은 우선수위를 가지며 학생 프로세스가 가장 낮은 우선순위를 가진다. 높은 우선순위를 가진 프로세스를 위한 큐 들이 비어있지 않으면 다음 우선순위의 큐는 실행될 수 없다. 

  foreground queue는 자신의 프로세스들 사이에서 라운드 로빈 스케줄링을 위해 CPU시간의 80%가 주어지고, background queue는 CPU시간의 20%를 받아 자신의 프로세스들에게 선입 선처리 방식으로 줄 수 있다.