[운영체제] 2. CPU 스케줄링

CPU 스케줄링

• Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.

FCFS 스케줄링

• 먼저 대기 큐에 들어온 프로세스 먼저 스케줄

• Example

  Process	Burst Time
  $P_1$	24
  $P_2$	3
  $P_3$	3

• 프로세스의 도착 순서 $P_1$ , $P_2$ ,$P_3$

• Wating Time for $P_1$ = 0, $P_2$ = 24, $P_3$ = 27

• Gantt chart
  

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

• Convoy effect :burst time이 짧은 process 뒤에 burst time이 긴 process가 위치

SJF 스케줄링

• 각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용

• CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄

• Example

  Process	Arrival Time	Burst Time
  $P_1$	0.0	7
  $P_2$	2.0	4
  $P_3$	4.0	1
  $P_4$	5.0	4

• Gantt chart

• Average waiting time = (0 + 6 + 3 + 7) / 4 =4

• SJF is optimal

  • 주어진 프로세스들에 대해 minimum average waiting time을 보장

  • Preemptive(SRTF 스케줄링)가 더욱 optimal한 방법

• SJF의 단점

1. 기아현상 발생
   계속 CPU burst time이 짧은 프로세스가 수행되게 될 경우, CPU burst time이 긴 프로세스는 영원히 수행되지 못함

2. CPU burst time을 예측할 수 없음

SRTF 스케줄링

• 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김

• Example (SJF예와 동일)

  Process	Arrival Time	Burst Time
  $P_1$	0.0	7
  $P_2$	2.0	4
  $P_3$	4.0	1
  $P_4$	5.0	4

• Gantt chart
  

• Average waiting time = (9 + 1 + 0 + 2) /4 =3

Round Robin 스케줄링

• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐 (일반적으로 10ms ~100ms)

• 할당시간이 지나면 프로세스는 선점(preempted)당하고 ready queue의 제일 뒤에 가서 다시 줄을 섭니다.

• n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻습니다.

• 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않습니다.

• Example

  Process	Burst Time
  $P_1$	53
  $P_2$	17
  $P_3$	68
  $P_4$	24

• Gantt chart

• Performances

  • Q large => FCFS
  • Q small => context switch 오버헤드가 커집니다.
  • 그렇면 어떻게 Q를 정해야 할까?
  • I/O bound job은 작게 CPU bound job은 크게

• 일반적으로 SJF보다 average turnaround time이 길지만 response time은 더 짧습니다.

  • 시분할 환경에서 인터랙티브한 작업을 처리하기 위해서는 response time이 중요합니다.

  • Long job과 Short job이 섞여 있는 환경에서 적합합니다. 동일한 burst time이 있는 작업이 수행되어야 한다면, average turnaround time이 길어지게 될 수 있습니다.

그 외 스케줄링 방법

• Multilevel Queue

  • Ready queue를 여러 개로 분할

    • Foreground (interactive)
    • Background (batch – no human interaction)

  • 각 큐는 독립적인 스케줄링 알고리즘을 가짐

    • Foreground – RR
    • Background - FCFS

  • 큐에 대한 스케줄링이 필요

    • Fixed priority scheduling
    • Time slice

• Multilevel Feedback Queue

  • 프로세스가 다른 큐로 이동 가능

  • 에이징(aging)을 이와 같은 방식으로 구현할 수 있다.

  • Multilevel-feedback-queue scheduler를 정의하는 파라미터들

    • Queue의 수
    • 각 큐의 scheduling algorithm
    • Process를 상위 큐로 보내는 기준
    • Process를 하위 큐로 내쫓는 기준
    • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준