[Operating System] CPU Scheduling (2)

Round-Robin Scheduling (RR Scheduling)

• FCFS 스케줄링과 비슷하지만 preemption이 추가되었다.

• A small unit of time, called a time quantum or time slice, is defined.

• time quantum : 일반적으로 10 ~ 100ms

• ready queue는 circular queue처럼 취급된다.

• CPU scheduler는 ready queue를 순회하면서 1 time quantum 동안 각 프로세스에게 CPU를 할당해준다.

• RR scheduling을 위해서 우선 ready queue를 FIFO를 통해 구현한다.

• 새 프로세스들은 ready queue의 tail에 추가된다.

• CPU scheduler는 ready queue에서 첫 번째 프로세스를 골라서 timer가 1 time quantum 이후에 interrupt하게끔 설정하고 process를 dispatch한다.

• 두 가지 경우가 일어나게 된다.

  • 프로세스가 1 time quantum보다 더 적은 CPU burst를 가진다. -> CPU를 스스로 놓아주게 된다.
  • 프로세스가 1 time quantum보다 더 큰 CPU burst를 가진다 -> timer에 의해 운영체제에 interrupt를 발생시킨다. -> context switch가 실행되고, 프로세스는 ready queue의 tail에 놓이게 된다.

• 이 작업을 원형 큐를 돌면서 다음 프로세스 -> 다음 프로세스 -> ...의 과정을 반복한다.

• 예시 : time quantum = 4ms인 경우
  

  • Gantt chart는 다음과 같다 :
    
  • 각 process의 waiting time : $P_1$ = 6ms, $P_2$ = 4ms, $P_3$ = 7ms
  • Average waiting time : 5.66ms

• 하나의 프로세스가 1 time quantum보다 더 큰 CPU burst를 가지면, 자동으로 interrupt가 발생하므로 RR은 preemptive algorithm이라고 할 수 있다.

• RR algorithm의 퍼포먼스는 time quantum의 사이즈에 많이 의존한다. 만약 time quantum이 매우 크면, RR policy는 FCFS policy와 같아진다. 반대로 time quantum이 너무 작으면, 너무 많은 context switch가 일어나게 된다.
  

• 실제로, 현대 시스템들은 time quantum을 10 ~ 100ms로, context switch 시간을 10$\mu$s로 설정하고 있으므로, context-switch time은 time quantum에 비해 작은 비율을 가지고 있다.
  

• average turnaround time은 time-quantum size가 증가할수록 줄어들지 않는다.

• 일반적으로, average turnaround time은 한 프로세스가 single time quantum 안에 끝난다면 개선될 수 있다. 예를 들면, 3개의 프로세스가 10 time units를 가지고, quantum이 1 time unit을 가진다면, average turnaround는 29이다. quantum을 10 time units로 바꾼다면 20으로 줄어들게 된다. context switch까지 고려하면 시간은 더 단축하게 된다. time quantum이 커야 turnaround time이 줄어들지만, 너무 크면 결국 FCFS와 동일하게 되므로 잘 조절해야 한다.

• 국룰 : CPU burst의 80퍼센트는 time quantum보다 작아야 한다.

Priority Scheduling

• 프로세스 별로 우선순위가 정해져 있고, 이 우선순위에 따라 CPU를 할당한다. 만약 같다면, FCFS의 순서를 따른다.
• SJF algorithm은 일반적인 priority-scheduling algorithm의 특수한 케이스인데, 그저 priority가 (예측된)next CPU burst의 inverse인 경우이다.
• 시스템별로 low number가 high priority인 경우도 있고, low priority인 경우도 있다.
• 여기서는 low number일 수록 high priority라고 가정한다.
• 예시
  
  • Gantt chart는 다음과 같다.
    
  • Average waiting time : 8.2ms
• priority 결정하는 방법
  • internal priority
    • measurable quantities를 이용해 priority를 계산한다.
    • ex) time limit, memory requirement, the number of open files, ratio of average I/O burst to average CPU burst have been used in computing priorities 등등..
  • external priority
    • 운영체제 밖의 기준으로 설정된다.
    • ex) process의 중요성, the type and amount of funds being paid for computer use, the department sponsoring the work, 등등..
• preemptive일 수도 nonpreemptive일 수도 있다. 예를 들어 process가 ready queue에 도착했을 때, 현재 실행중인 프로세스와 priority를 비교하게 된다. 만약 새로운 프로세스의 priority가 더 높다면,
  • preemptive : preempt한다.
  • nonpreemptive : 새로운 프로세스를 queue의 head에 놓는다.
• major problem : indefinite blocking 혹은 starvation.
  • CPU를 기다리고 있으면서 실행될 준비가 된 프로세스는 blocked상태이다. 하지만 low-priority process의 경우 무기한으로 기다리게 될 수 있다. 만약 heavily loaded computer system이라서 high-priority process들이 계속 들어온다면, low-priority process는 CPU를 가져 보지도 못할 것이다.
  • 일반적으로, 둘 중 하나가 발생할 수 있다.
    • 겨어어얼국 나중에 실행되거나,
    • 컴퓨터 시스템이 crash되어서 low-priority process들이 다 없어지던가.
• 해결 방안?
  - aging
  - 시간이 지날 수록 프로세스의 priority를 증가시키는 방법.
  - ex) priority : (high) 0 ~ 127 (low) 라고 하자.
  waiting process의 priority를 일정 시간마다 1씩 증가시킬 수 있다. -> 127의 priority를 갖는 프로세스도 언젠가 최우선이 되어 실행될 수 있다.
  - round-robin과 priority scheduling을 결합
  - 기본은 priority scheduling인데 같은 priority의 경우 round-robin을 적용한다.
  - ex) equal priority의 경우 round-robin을 사용, time quantum = 2ms로 설정.
  
  - Gantt chart는 다음과 같다.
  
  너무 많다. 또 이어서...

참고 자료

• Abraham Silberschatz, Operating System Concepts, 10th edition