OS - 5. CPU Scheduling (1)

1. Scheduling

• 어떻게 하면 일을 빠르게 처리 할수 있는가?

• 어떻게 하면 공평하게 일을 처리 할수 있는가?
• Short Term Scheduler에서 담당한다.

2. Preemptive Scheduler

    1. 실행 상태 -> 대기 상태
    2. 실행 상태 -> 준비 완료 상태
    3. 대기 상태 -> 준비 완료 상태
    4. 프로세스 종료할 때
위 상태에서 스케줄링이 발생을 하는데 1번과 4번의 경우 스케줄링의 측면에서 선택의 여지가 없다. 그러나 2번과 3번은 스케줄링을 할 여지가 있다. 그렇기 때문에 1번과 4번은 비선점형으로 진행하고 2번과 3번은 상황에 따라서 조정하면된다.

3. Dispatcher

• 디스패처는 CPU의 제어를 단기 스케줄러가 선택한 프로세스에게 주는 모듈
• 문액을 교환하는 일
• 사용자 모드로 전환하는 일
• 프로그램을 다시 시작하기 위해 적절한 위치로 jump하는 일

• 디스패처는 모든 프로세스의 문맥 교환 시 호출되므로, 가능한 한 빨라야 한다.
• 디스패처가 하나의 프로세스를 중단시키고 다른 프로세스를 실행시키는 데 소요되는 시간을 디스패치 지연(dispatch latency)이라고 한다.

4. 스케줄링 기준

• CPU 이용율
• 처리량 : 시간당 처리량으로 처리된 프로세스의 수이다.
• 총 처리 시간 : 프로세스당 평균 처리 시간이다. 
• 대기 시간 : 평균 대기시간이 적게 스케줄링 하는 것이다.
• 응답 시간 : 하나의 요구를 제출 한 후 첫 번째 응답이 나올 때 까지의 시간이다.

5. FCFS Scheduling

•  먼저들어온 것이 먼저 나간다.
•  제일 처리 시간이 긴 프로세스가 먼저 들어와 짧은 애들이 기다리는 것을 Convoy Effect(호위효과)라고 한다.
•  Waiting time for P1  = 0; P2  = 24; P3 = 27

•  Average waiting time:  (0 + 24 + 27)/3 = 17

6. SJF Scheduling

• 버스트 시간이 가장 짧은 순서대로 처리한다.
• Waiting time for P1  = 3; P2  = 16; P3 = 9; P4 = 0

• Average waiting time:  (3 + 16 + 9 + 0)/4 = 7
• SJF 스케줄링 알고리즘은 최소의 평균 대기 시간을 가진다. 그러나 이러한 스케줄링을 하기위한 CPU의 총 시간을 구하기 힘들다.
• 단기 CPU 스케줄링에서 구현하기 힘들고 장기 스케줄링에서 사용한다.
•Tn은 n번째 실제 버스트 시간이다. 

7. Priority Scheduling

•  우선순위로 스케줄링을 한다. 우선순위에 대한 정보를 가지고 있어야 한다.
•  가장 큰 문제점은 무기한 봉쇄 또는 기아 상태이다. 해결방법으로 시간이 지날때 마다 우선순위를 증가시켜준다.
•  우선순위로 스케줄링을 한다. 우선순위에 대한 정보를 가지고 있어야 한다.
• Waiting time for P1  = 6; P2  = 0; P3 = 18; P4 = 0; P5=1

•  Average waiting time = (6 + 0 + 16 +18 + 1)/5 = 8.2

8. RR(라운드 로빈) Scheduling

• 시분할 시스템을 위하여 설계되었다.
• 먼저들어온 것이 먼저 나가지만 CPU를 점유 할 수 있는 시간이 제한되어있다.
• Time Quantum이 작으면 오버헤드가 크고 너무 크면 FCFS와 똑같다.
• CPU를 얻기 까지의 최대 대기 시간은 (n-1)•Quantum이다.

9. Multilevel Feedback Queue

• 각 큐마다 스케줄링 알고리즘을 가진다.
• 우선순이가 높은 큐의 프로세스를 먼저 처리한다. -> 기아현상을 일으킬 수 있다.

• Multilevel Queue로 프로세스가 큐간 이동이 가능하도록 하게 한다.