[Operating System] CPU Scheduling

cpu scheduling(= short-term scheduling) : process 상태를 ready → running으로 바꾸는 역할

process type

process type은 크게 CPU bound job과 I/O bound job로 나뉜다.

• CPU bound job : cpu 연산을 주로 하는 process(i.e. 소인수분해 process ..)
  ⇒ CPU빈도는 적지만, CPU점유시간은 길다.
• I/O bound job : I/O 연산을 주로하는 process(i.e. 카톡, HWP ..)
  ⇒ CPU빈도는 많지만, CPU점유시간은 짧다.

I/O bound job은 사용자와의 interaction이 자주 발생하므로 먼저 cpu를 할당해줘야 한다.

basic scheduling pipeline

CPU Scheduler

cpu scheduling은 기본적으로 ready 상태의 process를 running 상태로 변경시켜주는 과정이기 때문에 multiprogramming 환경에서 사용하게 된다.

when cpu scheduling take place?

1. 현재 running 상태의 cpu가 I/O request를 요청해 wait 상태로 들어가게 될 때
2. 현재 running 상태의 cpu가 time run out으로 인해 ready 상태로 들어가게 될 때
3. 현재 running 상태의 cpu가 작업이 끝나 terminate 상태로 들어가게 될 때
4. 현재 wait 상태인 cpu가 I/O finished interrupt를 받아 ready 상태로 들어가게 될 때

💡 cpu가 I/O handler code를 실행한 뒤, 원래 수행 중인 process를 실행하는 것이 아니라 다시 cpu scheduling을 하게 된다.

 

cpu scheduling이 오직 1,3번에 의해서만 발생되는 scheduling을 nonpreemptive scheduling이라 한다.

cpu scheduling이 2,4번에 의해서도 발생되는 scheduling을 preemptive scheduling이라 한다.

CPU Scheduling Criteria

Performance Index

1. CPU utilization : cpu가 얼마나 많이 일하는가
2. Throughput : 시간 당 얼마나 많은 process를 끝내는가
3. Turnaround time : 어떤 process가 끝나는데 얼마나 많은 시간이 걸리는가
4. Waiting time : process가 ready queue에 얼마나 오래 있는가
   ⇒ I/O request에 의해 waiting state 시간은 포함하지 않는다.
5. Response time : request가 주어졌을 때 얼마나 빨리 응답하는가

Dispatcher

process가 cpu scheduler에 의해 ready → running으로 변경될 때 실행되는 module로 해당 process에게 cpu의 할당하는 역할을 한다.

dispatcher는 cpu를 할당하기 전에 다음과 같은 작업을 먼저 하게 된다.

1. context switching
2. user mode로 변경
   ⇒ dispatch가 kernel mode로 실행되기 때문에 모든 dispatch 작업이 끝나면 현재 상태를 다시 user mode로 변경해야 한다.
3. 현재 process가 이전에 실행하고 있던 코드 위치로 이동

dispatch 과정에서 대부분의 overhead는 context switching에서 발생하게 된다.

Scheduling Algorithms

FCFS scheduling

FCFS : First-Come First-Served(=FIFO)

• 먼저 들어온 process를 먼저 처리하는 scheduling기법
• nonpreemptive scheduling
• Convoy effect가 발생한다.
  ⇒ convoy effect : 긴 process 뒤에 온 short process의 turnaround time이 길어지는 문제
  
  

SJF scheduling

SJF : Shortest-Job-First scheduling
SRTF : Shortest-Remaining-Time-First

• cpu 점유시간이 가장 짧은 process먼저 처리하는 방식
• priority scheduling의 한 예시로 볼 수 있다.
• 점유시간이 긴 process는 계속 후순위로 밀려 실행되지 않는 starvation현상이 발생
• SJF : nonpreemptive, SRTF : preemptive

💡 SJF의 경우 실행 중 queue에 현재 process보다 더 짧은 process가 와도 그대로 진행하는 반면, SRTF의 경우 process를 교체한다.

 

SJF(SRTF) algorithm의 경우 waiting time 측면에서 가장 효율적인 algorithm이다.

SRTF waiting time < SJF waiting time

 

SJF scheduling의 문제점은 process의 실행 시간을 미리 어떻게 아느냐는 것이다.

💡 특정 process의 실행 시간을 예측하기 위해 이전 process 실행 시간을 exponential averaging해 예측하게 된다.

 

• alpha값으로 직전의 관측값을 얼마나 참조할 것인지를 조절할 수 있다.
  • alpha =0은 초깃값을 변화시키지 않는다.
  • alpha=1은 바로 이전 관측값만을 반영한다.

 

alpha값이 클수록 이전 값의 감소가 커진다.

 

이러한 exponential averaging 방식은 process time이 일정하게 변화하는 경우 이전 process time을 평균내는 것보다 훨씬 정확하다.

하지만 만약 process time이 규칙없이 변경된다면 오히려 평균내는 것보다 더 부정확할 수도 있다.

Priority Scheduling

각 process에 priority를 부여해 높은 priority를 가진 process를 먼저 처리하는 방식

• SJF는 cpu 점유 시간을 priority로 한 scheduling이다.
• priority scheduling의 경우 priority가 낮은 process는 계속 후순위로 밀려 실행되지 않는 starvation 현상이 발생한다.
• starvation 현상을 완화하기 위해 Aging기법을 적용
  ⇒ Aging : queue에 오래있을수록 process의 priority를 조금씩 높혀가는 방식

Round Robin

적절한 time quantum 동안만 process가 실행되도록 하는 방식

• 항상 모든 process가 주어진 시간을 사용하는 것이 아니라 I/O request나 terminate 시에는 cpu를 반환하게 된다.
• Round Robin : preemptive scheduling
• process 대기시간의 upper bound를 제공한다.
  ⇒ time quantum q이며 n개의 process가 memory에 있다면, 최대 대기시간은 (n-1)*q
• 적절한 time quantum을 찾는 것이 어렵다.
  • q가 너무 작은 경우, context switching이 빈번하게 발생해 overhead가 증가
  • q가 너무 큰 경우, FIFO(FCFS)와 동일하게 동작하게 됨

💡 Round Robin의 경우 multi-programming 환경에서 모든 process가 적절히 진도를 나갈 수 있게 해주기 때문에 scheduling 시 필수적인 기법이다.
⇒ 따라서 최신 OS에서는 Round Robin scheduling + 추가적인 scheduling을 적용하게 된다.

 

time quantum = 20이라고 할 때

일반적으로 Round Robin scheduling은 SJF보다 turnaround time은 오래 걸리지만 response time이 적게 걸린다는 장점이 있다.

Multilevel Queue

여러 queue를 이용해 scheduling하는 방식.

• 여러 queue로 구성되어 있기 때문에 queue 간의 scheduling도 별도로 필요하게 된다.

Ready queue의 경우 2개의 분리된 queue로 구성되어 있다.

• foreground : I/O bound job으로 구성되어 있는 queue
  ⇒ Round Robin scheduling. I/O의 경우 점유시간이 길지 않으므로
• background : CPU bound job으로 구성되어 있는 queue
  ⇒ FCFS

위에서 언급했듯이 기본적으로 I/O bound job을 먼저 처리해줘야 하므로 queue 간의 scheduling을 foreground queue를 우선적으로 처리할 수 있도록 설계해야 한다.

1. Fixed priority scheduling : foreground 작업을 모두 마친 후에야 background 작업을 시작
   ⇒ starvation 문제가 발생
2. Time slice : 각 queue에 적절한 CPU 시간을 분배
   ⇒ 예를 들어 foreground queue에 cpu시간의 80%를, background에 20%를 부여하는 식으로 구현할 수 있다.

ready queue에서는 2개의 queue만을 사용했지만, 더 많은 queue를 사용해 scheduling할 수도 있다.

Multilevel Feedback Queue

위의 multilevel queue에서 각 process의 유형에 맞춰 각기 다른 queue에 넣을 수 있었다.

하지만 초기 process가 어떤 type의 process인지 알기 어렵기 때문에 feedback 과정을 설계해 process가 level 간 이동을 할 수 있도록 함

multilevel-feedback-queue scheduler를 구현하기 위해 다음과 같은 parameter가 정의되어야 한다.

1. queue의 개수
2. 각 queue의 scheduling algorithms
3. process의 레벨 상승 조건
4. process의 레벨 하락 조건
5. process의 초기 조건

⇒ ready queue의 경우

1. queue의 개수 : 2
2. 각 queue의 scheduling algorithms : RR, FCFS
3. process의 레벨 상승 조건 : I/O 연산이 대부분인 경우
4. process의 레벨 하락 조건 : CPU 연산이 대부분인 경우
5. process의 초기 조건 : I/O연산으로 간주 or CPU 연산으로 간주

그 외의 예시

위의 간단한 예시로도 I/O bound job은 RR scheduling으로, CPU bound job은 FCFS로 처리되도록 분리할 수 있다.

Real-time Scheduling

Hard real-time systems

약간의 오차가 치명적인 결과를 초래하는 경우

⇒ 미사일 궤도 예측, 핵발전소 가동 ...

Soft real-time systems

실시간 처리가 중요하지만 치명적인 결과를 초래하지는 않는 경우

⇒ video stream

 

참고

- Operating System Concepts

- 운영체제, 한양대학교 강수용 교수님