CPU 스케줄링, 스케줄링의 종류와 Multilevel Queue

1. CPU 스케줄러 CPU Scheduler

• cpu 스케줄러 : 운영체제가 ready 상태의 cpu 중 running 할 cpu를 선택하는 것을 의미한다.
• Dispatcher : CPU의 제어권이 스케줄러에 의하여 다른 프로세서 넘어가는 것을 의미한다. 문맥 교환에서 디스패쳐가 사용된다.
• nonpreemtive : cpu의 자진 반납. 시스템 콜 등
• preemtive : cpu를 강제로 빼앗김. 인터럽트 등
• Cpu bound job : cpu를 길게 사용하는 작업 : 통계, AI 등
• I/O bound job : I/O를 길게 사용하는 작업 : 사람과 interactive한 대화형 작업 등
• 앞의 두 개의 job이 섞여 있는 상황에서, cpu를 효율적으로 분배해야 함.

2. 성능 척도 Scheduling Criteria

• CPU 스케줄러를 평가하는 척도
• 척도의 기준은 프로세스의 New와 Terminated 까지의 과정을 의미하지 않음. Cpu burst(ready) - I/O burst(block)의 기준임.
• CPU 이용률 CPU utilization : 얼마나 긴 시간 동안 CPU를 사용했는지. 최대한 CPU를 바쁘게 할 수록 좋다.
• 처리량 Throughput : 프로세서가 얼마나 많은 양의 업무를 하였는지.
• 소요시간 Turnaround Time : ready - running - cpu반환까지 걸린 시간의 총합
• 대기시간 Waiting Time : ready queue에서 대기한 시간
• 응답시간 Response Time : 프로세서가 new가 되고 ready queue에 대기하여 running이 처음으로 될 떄까지 걸린 시간.

---

3. FCFS First-Come First-Served

• 프로세스의 도착 순서대로 cpu를 점유한다.
• 먼저 도착한 작업의 cpu burst가 길고 뒤의 작입이 cpu burst가 짧으면, 대기시간이 길어져서 비효율 적이다.

4. SJF Shortest-Job-First

• 하나의 스케쥴링이 종료된 후, ready queue에 있는 프로세스 중 cpu를 가장 짧은 시간만을 사용할 것으로 예측되는 프로세스가 cpu를 점유한다.
• 비선점(Nonpreemtive)으로서 중도에 cpu를 빼앗기지 않는다.
• 비선점으로 인하여 FCFS와 마찬가지로 작업 중인 프로세스의 cpu burst가 길면, 기다리는 cpu의 대기시간이 길어질 수 있다.

5. SRTF Shortest-Remaining-Time-First, Preemptive SJF

• SJF의 문제를 해소하기 위하여, 선점(Preemptive)으로 작동한다.
• ready queue에 새로운 프로세스가 진입할 때마다, 프로세스의 예상 작업 시간과 진행 중인 프로세스의 남은 작업시간을 비교하여, 기다리는 프로세스의 시간이 짧으면 문맥 교환을 한다.
• 대기시간에 있어서만큼은 Optimal(최적화)를 보장한다.
• SJF와 SRTF의 공통적인 문제점은 Starving(기아) 현상에 있다. CPU Burst가 긴 작업은 다른 짧은 시간의 작업에 밀려서, 극단적인 상황에서는 cpu를 전혀 사용하지 못할 수도 있다.
• CPU Burst의 시간은 과거의 CPU burst 시간을 통해 예측한다. 그것은 Exponential Averaging이란 계산식을 통해 도출한다. 이 계산식은 최근의 작업시간을 그 전의 작업 시간보다 더 많이 고려하여 예상 시간을 도출하는 방식을 가진다.

6. Priority Scheduling

• 우선순위 priority number를 각각의 프로세서에 할당한다. 높은 우선 순위(숫자가 낮을 수록)의 프로세서에 우선적으로 cpu를 할당한다.
• SJF, SRTF도 일종의 우선순위 스케줄링이다. CPU Burst Time을 우선순위로 두기 때문에.
• Starving(기아 현상)이 발생할 수 있다. SJF와 마찬가지로 우선순위가 낮은 프로세스가 전혀 cpu를 점유하지 못하는 경우가 발생할 수 있다.
• 해결책으로 Aging을 우선순위에 반영한다. 기다리는 시간이 길 수록, 우선순위를 점차 높히는 방식이다.

7. RR Round Robin

• 현대에 가장 많이 사용하는 스케줄링 방식이다. (Time sharing)
• 각 프로세스 마다 동일한 크기의 할당시간time quantum을 가진다(일반적으로 10-100 milliseconds).
• 할당 시간이 지나면 선점(prrempted) 당하며 ready queue의 제일 마지막에 배치된다.
• 응답시간이 짧다. 응답시간이 (할당 시간)X(queue ready 프로세서)를 초과하지 않는다. 응답시간이 짧은 작업(I/O burst)이 많을 경우 유리하다.
• 반대로 Cpu Burst가 긴 작업에는 불리하다. ready queue에 있는 프로세서의 작업 시간이 길면, cpu 점유 시간을 조금씩만 나눠서 할당되기 때문에, 그만큼 작업이 모든 작업의 terminated 되기 까지의 시간이 길어진다. 10개의 프로세스가 동일하게 100초가 필요로 하면, 1000초 후에 모든 프로세스가 동시에 종료될 것이다.
• 할당 시간이 길면 : FCFS와 같아짐. 먼저 도착한 것이 먼저 끝나게 된다.
• 할당 시간이 짧으면 : 문맥 교환으로 인한 오버헤드가 과도하게 발생한다.

---

8. Multilevel Queue

• Ready Queue를 여러 개로 분할하고, 각각의 queue의 우선순위를 정하고, 각각의 프로세스는 해당 프로세스의 우선 순위에 따라 각각의 queue에 배치되고, queue 간 경쟁을 통해 하나의 queue가 cpu를 점유하는 형태.
• foreground 큐와 background 큐로 분할. 전자는 interactive하며 cpu burst가 짧은 queue로서 우선 순위가 높다. 후자는 batch 등 긴 시간을 필요로 하는 작업이다.
• 각 queue마다 사용하는 스케줄링 알고리즘이 다르다. foreground의 경우 RR 방식, Backgournd의 경우 FCFS를 사용한다.
• Queue 간의 시간 점유 시간의 격차가 크면 클수록 기아 현상이 일어날 가능성이 높다. 그러므로 Time Slice를 통해 각 큐의 CPU time을 적절하게 할당해야 한다.

9. Multilevel Feedback Queue

• Multilevel queue의 경우 queue와 프로세스에 대한 우선순위를 정해야 하고, queue의 time slice를 하는 등, 구현 방법이 복잡하다.
• Multilevel Feedback Queue의 경우 Aging 형태와 유사. 모든 작업은 Q0(그림으로는 quantum = 8)로부터 시작한다. 그리고 8만큼 시간 동안 작업을 하여도 끝나지 않은 작업은 Q1(사진 상 16)으로 옮겨진다. Q1에서 해당 프로세스를 진행해도 끝나지 않으면 Q2(FCFS)로 이동한다.
• 알고리즘에 따라 Q2가 Q1으로 이동할 수 있다.

---

10. 멀티 프로세서 CPU의 스케줄링

• 다수의 cpu로 구성된 멀티 프로세서 상황에서 스케줄링을 고려해야 한다.

• Queue를 하나로 세우고, 순서에 따라 비어진 cpu를 할당 받으면, 앞서의 스케줄링 방식과 큰 차이를 가지지 않음(은행의 대기표. 창구가 10개라도 queue는 하나이다). 하지만 프로세서 간 차이를 가지는 경우 스케줄링이 복잡해진다.

• 특정 프로세서에서만 작업을 해야하는 프로세스

• 각 프로세스가 평등한 Symmetric Multiprocessing(SMP)와, 하나의 프로세서가 나머지 프로세서를 관리하고 총괄적인 업무를 하는 Asymmetric Multiprocessing 방식이 있음.

• 모든 프로세서 같이 바쁠 수록 좋음. 부담을 공유 Load Sharing 하는 방식으로 스케줄링을 고려 해야 함.

11. Real-Time Scheduling

• 특히 Hard real-time scheduling의 경우 정해진 시간 안에 반드시 작업이 종료되어야 함.
• 보통 리얼타임 스케줄링의 경우 매 시간 마다 일정 시간을 보장하는 형태를 띔. 특정 시간 마다 특정 시간 만큼을 보장하는 방식으로 스케줄링을 정함.

12. Thread Scheduling

• Local Scheduling : 유저 레벨에서의 스레드의 경우, 프로세스 내부의 라이브러리가 스레드의 스케쥴링을 담당.
• Global Scheduling : 커널 레벨에서 해당 스레드를 통제할 경우, 단기 스케줄러가 스케줄링을 담당.

사진 등 자료의 출처, 참고 자료 : http://www.kocw.net/home/search/kemView.do?kemId=1046323
이화여대 반효경 교수의 영상강의를 주요자료로 하여 운영체제를 학습하고 정리하고 있습니다.