CPU Scheduling

CPU Scheduling: runnable processes 중에 누가 다음 순서로 실행될지를 결정하는 것

 

Scheduling algorithm의 목표

• 모든 시스템
  • No starvation
  • 우선순위에 비례한 Fairness: 각각의 프로세스에 우선순위에 맞게 CPU 자원을 공유
  • Balance: 시스템의 모든 part들이 바쁘게 움직이도록 유지
• Batch 시스템
  • Throughput: 시간당 처리하는 job 수가 최대
  • Turnaround time: 작업 처리 소요 시간이 최소
  • CPU utilization: CPU가 항상 유의미한 작업을 실행
• Interactive 시스템
  • Response time: 요청에 가능한 한 빨리 응답
  • Proportionality: 사용자들의 기대에 충족
• Real-time 시스템
  • Meeting deadlines: 데이터 손실을 방지
  • Predictability: 멀티미디어 시스템에서 품질 저하 방지

 

Starvation

• 어느 한 프로세스가 다른 프로세스 때문에 실행이 안되는 상황
• poor scheduling policy가 starvation을 유발할 수 있다
  • 만약 높은 우선순위의 프로세스가 항상 낮은 우선순위의 프로세스를 이기는 경우
• 동기화가 starvation을 유발할 수 있다
  • lock을 얻는 데에 있어 하나의 스레드가 항상 다른 스레드를 이기는 경우
  • reader-writer 문제에서 계속 reader가 들어오는 경우

 

Scheduling의 두 가지 분류

• Non-preemptive scheduling
  • 스케줄러가 현재 실행 중인 job이 끝나고 자발적으로 CPU 자원을 돌려줄 때까지 기다린다 (CPU가 가면 완료까지 계속 사용)
• Preemptive scheduling
  • 스케줄러가 강제로 interrupt와 context switch를 할 수 있다

 

FCFS (First Come, First Served) 

• 선입선출 (선착순)
• 현실에서 가장 많이 쓰이는 방식
• non-preemptive 방식으로 starvation이 없다
• 짧은 job이 긴 job을 기다리는 경우에는 평균 waiting time이 커질 수 있다 (convoy effect)
• CPU를 못 뺏어서 I/O와 CPU의 overlap 효과가 거의 없다

위와 같이 P2, P3은 짧은 데도 불구하고 P1 때문에 오래 기다려서 평균 waiting time이 길어지는 경우를 convoy effect라고 한다. 위의 경우가 만약, p2, p3, p1 순이라면 평균 waiting time은 3에 불과하기 때문이다.

 

SJF (Shortest Job First)

• 맨 처음 도착하는 job 이후에 도착하는 job들끼리의 순서가 burst time (사용 시간)에 의해 결정된다 (같은 burst time이라면 먼저 도착하는 순)
• 평균 waiting time이 가장 작은 방법
• non-preemptive
• 미래의 CPU burst를 예측할 수가 없다 (history를 보고 추측할 수밖에 없다)
• 더 짧은 job이 계속 들어오는 경우 starvation이 발생할 수 있다

위의 경우는 p1에 맨 처음 도착하고 p1이 끝나기 전에 p2, p3, p4가 모두 도착한다. 이 경우 burst time이 가장 적은 p3이 다음 순서이고 p2와 p4는 burst time이 같기 때문에 먼저 도착한 p2이 먼저 처리된다. 따라서, p1 -> p3 -> p2 -> p4 순이다.

 

SRTF (Shortest Remaining Time First)

• SJF의 preemptive 버전
• 만약 새로운 프로세스가 도착한 시점에서 새로운 프로세스의 burst time이 현재 실행 중인 프로세스의 remaining time보다 작은 경우 새로운 프로세스가 즉시 CPU를 선점한다

맨 처음 p1이 도착하여 실행된다. 2 시점에서 p1의 remaining time은 5이고 p2의 burst time은 4이므로 p2가 바로 선점하여 실행한다. 4 시점에서 p2의 remaining time은 2이고 p3의 burst time은 1이므로 p3이 선점한다. p3이 끝나는 5 시점에서 p4가 도착하지만 p2의 remaining time은 2이므로 p2가 마저 실행된다. p2가 끝나면 p1의 remaining time은 5이고 p4의 burst time은 4이므로 p4가 다 실행되고 p1이 마저 실행된다.

 

RR (Round Robin)

• 각각의 job은 time quantum만큼 쓰고 강제로 회수된다 (보통, 10~100 ms)
• timesharing (multitasking)에 좋다
  • starvation이 없음
  • 전반적으로 SJF보다 평균 waiting time이 길지만 response time은 더 좋다
• Preemptive
• A rule of thumb: 80% 이상의 CPU burst time이 time quantum보다 작아야 한다
• 모든 job은 공평하게 스케줄링된다

위의 경우에서 time quantum이 20이라고 해보자. 모든 job은 20만큼 CPU를 쓰고 다음 프로세스에게 반납할 것이다. 그 과정이 차트에 나와 있다. 위의 과정은 분명히 SJF보다는 평균 waiting time이 길지만 반응 시간 면에서는 더 뛰어나다.

위의 그림은 time quantum이 따른 context switch를 보여준다. 결국 time quantum을 작게 하면 그만큼 반응은 더 빨라지겠지만 context switching이 빈번하게 일어나므로 관리비용이 증가하게 된다. 또한, 스케줄 패턴은 그대로인데 time quantum만 늘릴 경우에도 오히려 turnaround time (CPU time + waiting time)만 늘어나는 경우도 존재하므로 잘 따져보고 변경하여야 한다.

 

Priority scheduling

• 가장 높은 우선순위의 job 순서대로 실행한다
• SJF도 CPU burst 기반의 priority scheduling
• Round-robin이나 FCFS는 똑같은 우선순위를 가짐
• preemptive or non-preemptive
• 우선순위는 실행 중에 조정이 가능
• Multi-level Feedback Queue로 모델링된다 (starvation 방지 위해)

Starvation problem: 높은 우선순위의 job이 계속 공급된다면 낮은 우선순위의 job들은 영원히 실행되지 못하는 문제 Priority inversion problem: 낮은 우선순위의 job이 자원을 소유하고 있어서 높은 우선순위의 job이 실행할 수 없는 상황 Solution

1. Aging (일정 시간이 지나면 우선순위를 높이거나 낮춘다)

• wait time만큼 우선순위를 올리는 방법
• CPU time만큼 우선순위를 내리는 방법

2. Priority inheritance protocol (PIP)

• 높은 우선순위의 job이 자원을 소유하고 있는 낮은 우선순위의 job에게 자신의 우선순위를 기부함으로써 자원을 가지고 있는 프로세스가 빨리 완료되도록 하는 것

3. Priority ceiling protocol (PCP)

• 낮은 우선순위의 job이 자원을 소유하게 되면 그 즉시 우선순위를 상승시킨다
• 상한 값은 미리 정해놔야 한다

 

Multi Feedback Queue

• job이 다양한 queue 사이를 이동할 수 있는 Multi-level queue scheduling
• Queue는 우선순위를 가진다
• 프로세스가 너무 많은 CPU time을 가질 경우 낮은 우선순위의 queue로 이동시킨다
• I/0 작업이 많거나 interactive 한 프로세스들은 높은 우선순위의 queue로 이동시킨다
• 어느 프로세스가 낮은 우선순위의 queue에서 너무 많이 기다릴 경우에는 높은 우선순위의 queue로 이동시킨다 (aging – starvation 방지)
• Redy queue는 그 안에서 다음과 같이 나뉘어 있다.
  • foreground (interactive)
  • background (batch)
• 각각의 queue는 자신만의 scheduling algorithm을 갖는다
  • foreground: RR
  • background: FCFS
• 스케줄링은 반드시 queue 사이에서 이루어져야 한다
  • Fixed priority scheduling: 모든 job들을 foreground에 갖다 놓고 그 후 background에 갖다 놓는다 (starvation 발생 가능)
  • Time slice: 각각의 queue는 일정 비율의 CPU time을 얻는다
  • background는 20%의 비율을 차지한다
• Aging 종류
  • queue들의 수
  • scheduling algorithm
  • 프로세스를 승격시킬 시기를 결정하는 메서드
  • 프로세스를 강등시킬 시기를 결정하는 메서드
  • 프로세스가 서비스를 필요로 할 때 어떤 queue를 사용할 것인지 결정하는 메서드
• 우선순위는 CPU를 많이 쓰는 형태면 낮고 제안된 시간보다 적게 쓰거나 I/O를 일으키면 높다.

 

Real-Time Scheduling

• Hard real-time systems: 시간 내에 완료하지 못하면 실패로 처리하며 전용 OS로 필요하다 – time-critical, rigid
• Soft real-time computing: 시간 내에 완료하지 못하면 실패까지 아니고 품질 저하로 이어지며 범용 OS로 구현 가능하다 – QoS