CPU scheduling

▶ Round Robin (RR)

- Each process gets a small unit of CPU time (time quantum), usually 10-100 milliseconds. 

   After this time has elapsed, the process is preempted and added to the end of the ready queue.

- If there are n processes in the ready queue and the time quantum is q,

                                                                  then each process gets 1/n of the CPU time in chunks of at most q time units at once. 

  No process waits more than (n-1)q time units.

- Performance

              q large → FIFO

              q small → q must be large with respect to context switch, otherwise overhead is too high.

 

 

+ 시간 할당량(time quantum) = 시간 조각(time slice)

RR 스케줄링 알고리즘은 시분할 시스템을 위해 특별히 설계되었기 때문에, RR 스케줄링 알고리즘의 성능은 시간 할당량의 크기에 매우 많은 영향을 받는다. 극단적인 경우, 시간 할당량이 매우 크면, RR 정책은 선입선출 정채과 같다. 시간 할당량이 매우 적다면(예를 들어 1마이크로초), 라운드 로빈 방식은 처리기 공유(processor sharing) 라 불리며, 이론적으로는 n 개의 프로세스들 각각이 실제 처리기의 1/n 속도록 실행되는 자신의 처리기를 가지고 있는 것처럼 사용자에게 보인다.

 

- 작은 시간 할당량은 문맥교환을 증가시킴을 보임

 

또한, RR 스케줄링의 성능에 문맥교환(context switching)의 영향을 고려해야 할 필요가 있다. 우리가 10시간 단위를 갖는 하나의 프로세스를 가지고 있다고 가정해보자. 시간 할당량이 12시간 단위라면, 프로세스는 아무런 오버헤드 없이 1시간 할당량 이전에 끝난다. 만일 시간할당량이 6시간 단위라면, 프로세스는 2시간 할당량이 필요하므로, 한번 문맥교환을 해야한다. 시간할당량이 1시간 단위라면, 9번의 문백 교환이 발생할 것이고, 따라서 프로세스의 실행이 느려진다.

그러므로, 우리는 시간 할당량이 문맥교환 시간에 비해 더 클 것을 원한다.

 

- 총처리 시간이 time quantum에 따라 변함을 예시

 

총처리 시간(turnaround time) 또한, 시간 할당량의 크기에 좌우된다. 한 프로세스 집합의 평균 총처리 시간은 시간 할당량의 크기가 증가하더라도 반드시 개선되지 않는다. 문맥 교환 시간이 추가된다면, 더 많은 문맥교환이 요구되기 때문에 더작은 시간 할당량에 대해서는 평균 총처리 시간이 증가된다. 반면에, 시간 할당량이 너무 크다면 RR 스케줄링은 선입 선처리 정책으로 퇴보한다. 

▶ 다단계 피드백 큐 ( Multievel Feedback Queue )

- A process can move between the various queues; aging can be implemented this way.

- Multilevel-feedback-queue scheduler defined by the following parameters:

     ㆍnumber of queues

     ㆍscheduling algorithms for each queue

     ㆍmethod used to determine when to upgrade a process

     ㆍmethod used to determine when to demote a process

     ㆍmethod used to determine which queue a process will enter when that process needs service

 

  + 다단계 피드백 큐 (Multievel Feedback Queue) 스케줄링 수행 시 기대효과 

일반적으로 프로세스들이 스시템 진입 시에 영구적으로 하나의 큐에 할당되며, 큐사이를 프로세스들은 이동하지 않는다. 그러나 다단계 피드백 큐 스케줄링 알고리즘에서는 프로세스가 큐들 사이로 이동한다. 어떤 프로세스가 CPU 시간을 너무 많이 사용하면, 낮은 우선순위의 큐로 이동되고, 입/출력 중심의 프로세스와 대화형 프로세스들을 높은 우선순위의 큐에 넣어주어 효율이 향상되는 효과를 갖게 한다.

 

 

자세히 살펴보면, 준비된 큐를 다수의 분리된 큐로 나누고 각 큐에 우선순위를 연관시킨다. 우선순위가 낮을수록 큐에서 사용하는 time quantum는 증가된다. 각 큐의 프로세스들은 그 큐보다 높은 우선순위의 큐들이 empty인 경우에만 CPU를 할당받을 수 있다. 모든 프로세스들은 처음에는 highest priority queue에 들어간다.

만약 주어진 time quantum가 만기되면 실행되던 프로세스는 그 프로세스가 있었던 우선순위 큐의 바로 하위의 우선순위 큐로 이동된다. 따라서 CPU-bounded process는 점차 낮은 우선순위 큐로 이동된다. lowest priority queue의 프로세스에 대해 time quantum가 만기된 경우였다면 그 프로세스는 다시 lowest priority queue에 들어간다.  

만약 프로세스가 I/O 종료 후 다시 큐로 들어가야 한다면 그 프로세스는 I/O 요청 이전에 있었던 우선순위 큐의 바로 상위의 우선순위 큐에 들어간다. 따라서 I/O-bounded process는 점차 높은 우선순위 큐로 이동된다. highest-priority queue의 프로세스에 대해 I/O 종료가 발생한 경우였다면 그 프로세스는 다시 highest priority queue에 들어간다.

 

+ 다단계 피드백 큐 스케줄링과 기아상태

스케줄링 수행시 실행 준비는 되어 있으나 CPU를 사용하지 못하는 프로세스는 CPU를 기다리면서 봉쇄된 것으로 간주될 수 있다. 예를 들면,부하가 과중한 컴퓨터 시스템에서 높은 우선순위의 프로세스들이 꾸준히 들어와 낮은 우선순위의 프로세스들이 CPU를 얻지 못하게 됨으로써, 낮은 순위의 프로세스들은 무한봉쇄(indefinite blocking) 또는 기아상태(starvation)가 되는 것이다.

낮은 우선순위의 프로세스들을 무한히 봉쇄하는 문제(기아상태)에 대한 해결방안은 노화(aging)이다. 노화란, 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 방법으로, 다단계 피드백 큐 스케줄링 수행시 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동하여 기아상태를 예방할 수 있다.

 

▶ 우선 순위 역전 (priority inversion)

 높은 우선순위의 프로세스가 현재 낮은 우선순위의 프로세스에 의해 접그되고 있는 커널 자료를 읽거나 변경할 필요가 있을 경우 어떠한 일이 발생할 수 있을까? 이때 높은 우선순위의 프로세스는 낮은 우선순위의 프로세스가 끝나기를 기다려야 한다. 이는 우선순위 역전(inversion) 이라고 알려져 있다. 사실, 높은 우선순위의 프로세스가 필요로 하는 자원들을 접근하고 있는 프로세스들의 체인이 있을 수 있다.

이러한 문제는, 이러한 모든 프로세스들(높은 우선순위 프로세스가 필요로 하는 자원을 접근하는 모든 프로세스들) 이 그 자원을 사용 완료할 때까지 높은 우선순위를 상속하는, 우선순위 상속(priority-inheritance) 프로토콜로 해결할 수 있다. 이들은 종료할 때 우선순위가 원래의 값으로 복귀한다. 

 

▶ 실시간 스케줄링 ( Real-time scheduling )

- 경성 실시간 시스템(Hard real-time system)

ㆍ정해진 시간 내에 특정 작업이 완료되기를 요구한다. 

ㆍresource reservation : scheduler는 process가 정해진 시간 내에 완료되는 것이 보장될 경우 수행하고, 그렇지 않으면 요청을 거절한다.

ㆍ현대의 computer와 운영체제에는 완전한 기능성은 갖추어 있지 않으며 특정 process를 위해서 사용되는 hardware 상에서 실행되는 특수 목적의 software로 구성된다.

ㆍ단점 : scheduler가 각 type의 운영체제 기능이 수행되기 위해 얼마나 오랜 시간이 소요되는지 정확하게 알아야만 한다. 따라서 각 operation이 최대 시간을 취할 수 있도록 보장해야 한다. 그러나 이러한 보장은 secondary storage나 virtual memory를 가진 system에서는 불가능하다.

- 연성 실시간 시스템(Soft real-time system)

ㆍhard real-time system 보다는 덜 제한적이다. 중요한 process들이 상대적으로 덜 중요한 process들 보다 높은 priority를 가질 것을 요구한다.

ㆍ단점 :  time-sharing system에 soft real-time 기능을 첨가하는 것은 자원의 불공정한 할당을 야기할 수도 있으며 더 긴 지연이나 심지어는 starvation을 초래할 수도 있다.