[OS] CPU 스케줄링

스케줄링

스케줄링: 다중 프로그래밍을 가능하게 하는 운영체제의 동작 기법.

• 즉, 어떤 프로세스를 실행시키거나 중단할지 결정하는 것
• 다양한 스케줄링 정책이 있고, 이는 discipline이라고도 볼림

핵심질문: 스케줄링 정책은 어떻게 개발하는가?

• 스케줄링 정책의 핵심 가정은?
• 어떠한 평가 기준이 중요한지?
• 컴퓨터 시스템에 사용된 기본 접근법은?

아래의 내용을 통해 스케줄링 정책이 어떻게 개발되는지 알아볼 것

1. 워크로드에 대한 가정

워크로드(workload): 일련의 프로세스들이 실행하는 상황

• 워크로드 결정은 곧 정교한 정책개발로 이어짐

워크로드에 대한 가정

1. 모든 작업은 같은 시간동안 실행됨 (실행시간 일정함)
2. 모든 작업은 동시에 도착
3. 각 작업은 시작되면 완료될 때까지 실행됨
4. 모든 작업은 CPU만 사용(입출력 x)
5. 각 작업의 실행시간은 사전에 알려져 있음

이 가정은 매우 이상적이고 비현실적임
고로 논의가 진행됨에 따라 가정을 완화시킬 것이고,
최종적으로 "제대로 동작하는 스케줄링 정책"을 만들 것임

2. 스케줄링 평가 항목

스케줄링의 정책 비교를 위해 스케줄링 평가 항목(scheduling metric)을 결정해야함

스케줄링 평가 항목

• 반환 시간 = 작업 완료 시각 - 작업 도착 시간
  • 모든 작업은 동시에 도착한다고 가정했으므로 작업 도착 시간 = 0이라고 볼 수 있다
  • 따라서 위의 가정에서는 반환 시간 = 작업 완료 시각 (가정 완화할 것임)
  • 반환시간은 성능 측면에서의 평가기준 (성능 ↔️ 공정성)

(원래는 평가 기준 다양한데, 문제를 간단히 하기 위해 "반환시간"이라는 하나의 평가기준만을 사용)

3. 선입선출(FIFO)

선입선출의 스케줄링 방법은

• 단순하다
• 구현이 쉽다
• 우리의 가정 하에서는 잘 동작한다
  • ex)
    A: 0초에 시스템에 도착, 10초 소요
    B: 10초에 시스템에 도착, 10초 소요
    C: 20초에 시스템에 도착, 10초 소요
    
  • 평균 반환 시간은 (10+20+30)/3 = 20

Convoy effect

그러나 FIFO 스케줄링은 1번 가정을 완화하면 성능이 안 좋아짐

• 만약 1번 가정(모든 작업은 같은 시간동안 실행됨)을 완화한다면?
  • ex)
    A: 0초에 시스템에 도착, 100초 소요
    B: 100초에 시스템에 도착, 10초 소요
    C: 110초에 시스템에 도착, 10초 소요
    
  • 평균 반환 시간은 (100+110+120)/3 = 110

convoy effect: 짧은 프로세스들이 오래걸리는 프로세스의 종료를 기다리는 현상

그렇다면 작업 실행 시간이 다른 경우 더 좋은 알고리즘은?

4. 최단 작업 우선(Shortest Job First, SJF)

최단 작업 우선(Shortest Job First, SJF): 실행시간 가장 짧은 작업 먼저 처리

• 비선점형 스케줄러 (시작했으면 끝까지 감)
• 모든 작업이 동시에 도착한다면 최적의 스케줄링 알고리즘!
  • 위의 예를 SJF로 스케줄하면, BCA 순으로 처리
    
  • 평균 반환 시간은 (10+20+120)/3 = 50으로 훨씬 효율적이다
• ... 그러나 실제로는 모든 작업이 동시에 도착하지 않음
• 가정 2를 완화하면 -> 작업들이 임의의 시간에 도착할 수 있음
  • ex)
    A: 0초에 시스템에 도착, 100초 소요
    B: 10초에 시스템에 도착, 10초 소요
    C: 10초에 시스템에 도착, 10초 소요
    
  • 이 경우 순수 SJF 스케줄링을 하면, 0초인 시점에 프로세스 A만 존재하므로 A가 최단 작업이 되어 이를 수행하게 됨
  • 그 후 10초에 B,C가 시스템에 도착하지만, 이미 A를 수행하고 있어 B,C는 대기해야함
  • 평균 반환 시간은 (100 + (110-10) + (120-10))/3 = 103.33
    • 효율 구림. 더 효율적인 스케줄링 방법은..?

참고로 옛날에는 비선점(non-preemptive) 스케줄러가 개발되었었음. 비선점 스케줄러는 각 작업이 종료될 때까지 계속 실행 (위의 예와 비슷).

현대 스케줄러는 모두 선점형 스케줄러 (문맥교환 가능)

5. 최소 잔여시간 우선 (Shortest Time-to-Completion First, STCF)

위의 문제를 해결하기 위해서는 가정 3 (작업은 끝날 때까지 계속 실행)을 완화해야한다.
즉, 프로세스 A가 아직 안 끝났어도 A를 중지하고 B나 C를 실행하기로 결정하는 것이다. (물론 이후 A는 다시 실행됨)

최소 잔여시간 우선(STCF): 잔여시간이 적은 작업부터 처리

• 선점형 스케줄러 (실행중인 프로세스 일시 중지 후 문맥교환 가능)
• 새로운 프로세스가 시스템에 들어오면, 잔여 실행 시간을 계산하고 그 중 가장 적은 잔여 시간을 가진 작업을 스케줄
  • 아까 전 문제점
    
    • B, C가 시스템에 도착했지만, A가 먼저 수행중이라 대기해야함
    • 평균 반환 시간 103.33
  • STCF으로 해결
    
  • 평균 반환 시간은 (120 + (20-10) + (30-10))/3 = 50

현재까지의 가정 (바뀐것 포함)
1. 모든 작업 실행시간 일정 -> 실행시간 일정하지 않음
2. 모든 작업은 동시에 도착 -> 작업 도착 시간 다를 수 있음
3. 각 작업은 시작되면 완료될 때까지 실행됨
4. 모든 작업은 CPU만 사용(입출력 x)
5. 각 작업의 실행시간은 사전에 알려져 있음

평가 기준: 반환 시간

6. 새로운 평가기준: 응답시간

앞선 문제들에서는 문제를 간단히 하기 위해 평가기준을 오로지 "반환시간" 하나만 설정하였다.

과거에는 반환시간만 가지고도 유의미한 스케줄링을 할 수 있었지만, 시분할 컴퓨터의 등장으로 사용자는 시스템에게 상호작용을 원활이 하게 되었다.

따라서 이제는 원활한 상호작용을 위한 "응답시간"이라는 새로운 평가기준이 필요

• ex) 프로세스 A,B,C 모두 동시에 도착, 모두 5초 소요
  
  • ABC 순으로 스케줄링을 하기로 결정하였으면, B는 5초간, C는 10초간 기다리기만 함
  • 반환시간 기준으로는 괜찮음 (반환시간 = 10)
  • 평균 응답 시간: (0+5+10)/3 = 5
    응답시간과 상호작용 측면에서는 비효율적!
    (프로세스 C는 10초 뒤에 실행됨...)

응답시간에 민감한 스케줄러는 어떻게 만들 수 있을까?

7. 라운드 로빈(RR)

라운드 로빈(Round-Robin, RR) 스케줄링: 작업을 처음부터 끝까지 실행시키지 않고, 일정 시간(타임 슬라이스)동안 실행한 후 실행 큐의 다음 작업으로 전환하는 방식

• 타임 슬라이스 (time slice): 작업을 실행시킬 시간 단위
  • 타임 슬라이스의 길이는 타이머 인터럽트 주기의 배수여야 함
    (타이머: 10ms -> 타임 슬라이스: 10ms, 20ms, ...)
  • 타임 슬라이스가 짧을수록 평균 응답 시간이 짧아짐 (대신 문맥 교환 비용 발생)
  • 스케줄링 퀀텀 (scheduling quantum) 이라고도 함
• 아까 전 STCF의 문제점을 Round-Robin으로 해결할 수 있다
  
  • 평균 응답 시간(good): (0+1+2)/3 = 1
  • 평균 반환 시간(very bad): (13+14+15)/3 = 14
    • 사실 RR은 반환 시간 기준으로는 매우 안 좋은 스케줄러

응답시간 vs 문맥 교환 비용

• 타임 슬라이스가 짧으면 응답시간이 짧아지지만, 문맥 교환 비용이 늘어남
• 시스템이 최적의 상태로 동작할 수 있도록 타임 슬라이스의 길이를 결정해야 함
  • 타임 슬라이스 10ms, 문맥교환비용 1ms 이면, 10%의 시간이 문맥 교환에 사용됨, 낭비!
  • 타임 슬라이스 100ms, 문맥교환비용 1ms 이면, 1%의 시간이 문맥 교환에 사용됨, 적절한 비용 상쇄

공정한 정책(RR) vs 불공정한 정책(SJF, STCF)

• RR과 같은 공정한 정책은 작업들이 균등하게 수행되는 것이 목표.
  응답과 상호작용 측면에선 좋지만, 반환 시간의 측면에선 안 좋음

• SJF, STCF과 같은 불공정한 정책은 반환 시간을 최적화하는 것이 목표.
  하나의 작업을 끝까지 실행할 수 있지만, 나머지 작업들이 대기해야 될 수 있음 (응답 시간의 측면에서 안 좋음)

• 결국 응답시간과 반환시간 중 하나를 최적화하면 나머지 하나는 안 좋아지고, 절충이 필요함

현재까지의 가정 (바뀐것 포함)
1. 모든 작업 실행시간 일정 -> 실행시간 일정하지 않음
2. 모든 작업은 동시에 도착 -> 작업 도착 시간 다를 수 있음
3. 각 작업은 시작되면 완료될 때까지 실행됨 -> 작업 완료 전에 다른 작업으로 전환 가능
4. 모든 작업은 CPU만 사용(입출력 x)
5. 각 작업의 실행시간은 사전에 알려져 있음

평가 기준: 반환 시간, 응답 시간

8. 입출력 연산의 고려

이번에는 가정 4를 완화하여 입출력 작업도 수행한다고 하자.

입출력 작업을 요청한 경우 스케줄러는 다음에 어떤 작업을 실행시킬지 결정해야함.

• 입출력 작업 요청한 프로세스는 입출력 끝날 때까지 CPU 못 쓰기 때문
• 입출력 요청을 한 프로세스는 대기 상태가 되고, 운영체제는 그 시간동안 다른 작업을 스케줄 해야함

또한 입출력 완료 시에도 의사결정 필요

• 입출력이 완료되면 인터럽트 발생
• 입출력을 요청한 프로세스가 대기상태 -> 준비상태로 전환
• 입출력이 완료되고 인터럽트 발생 시 요청 프로세스를 바로 실행시킬 수도 있음 (결정하기 나름)

입출력 연산 예시

두 프로세스 A,B가 있고, 각 작업은 50초 소요
프로세스 A는 10초동안 실행된 후 입출력 요청을 함 (입출력 시간은 10초)

• 중첩(overlap) X
  
  • A 작업이 완료된 후에 B 실행
  • A가 입출력 요청을 하여 CPU를 사용하고 있지 않을 때에도 B가 실행되지 않음
  • 총 140초 소요
• 중첩(overlap) O
  
• 이번에는 A 작업이 입출력을 요청하여 CPU를 사용하지 않을 때, 작업 B를 수행
• 총 100초 소요
• 대화형 프로세스, 입출력을 실행하는 동안 다른 CPU-intensice한 작업들이 실행됨

현재까지의 가정 (바뀐것 포함)
1. 모든 작업 실행시간 일정 -> 실행시간 일정하지 않음
2. 모든 작업은 동시에 도착 -> 작업 도착 시간 다를 수 있음
3. 각 작업은 시작되면 완료될 때까지 실행됨 -> 작업 완료 전에 다른 작업으로 전환 가능
4. 모든 작업은 CPU만 사용(입출력 x) -> 입출력을 사용하는 작업 존재
5. 각 작업의 실행시간은 사전에 알려져 있음

평가 기준: 반환 시간, 응답 시간

9. No more Oracle

그러나 마지막 가정(5. 각 작업의 실행시간은 사전에 알려져 있음)이 있었기에 위의 스케줄러들이 힘을 쓸 수 있었던 것.

즉, 미래를 예측할 수 없는 운영체제의 근본적인 문제는 해결할 수 없음

다만, 가까운 과거를 이용하여 미래를 예측하는 스케줄러는 구현 가능!
(다음 장의 주제인 "멀티 레벨 피드백 큐")

문제

https://github.com/remzi-arpacidusseau/ostep-homework/tree/master/cpu-sched
에 있는 scheduler.py를 실행시켜보며 문제를 해결해보자

문제 1

길이가 200인 세 개의 작업을 SJF와 FIFO 스케줄링 방식으로 실행할 경우 응답시간과 반환 시간을 계산하시오.

• SJF
  ./scheduler.py -p SJF -l 200,200,200 -c
  평균 응답시간: (0+200+400)/3 = 200
  평균 반환시간: (200+400+600)/3 = 400
• FIFO
  ./scheduler.py -p FIFO -l 200,200,200 -c
  평균 응답시간: (0+200+400)/3 = 200
  평균 반환시간: (200+400+600)/3 = 400

문제 2

같은 조건이지만 작업의 길이가 각각 100, 200 및 300일 경우에 대해 계산하시오.

• SJF
  ./scheduler.py -p SJF -l 100,200,300 -c
  평균 응답시간: (0+100+300)/3 = 133.3
  평균 반환시간: (100+300+600)/3 = 333.3
• FIFO
  ./scheduler.py -p FIFO -l 100,200,300 -c
  평균 응답시간: (0+100+300)/3 = 133.3
  평균 반환시간: (100+300+600)/3 = 333.3
  • FIFO의 경우 작업의 순서가 바뀌면 응답시간 및 반환시간도 바뀜

문제 3

2번과 같은 조건으로 타임 슬라이스가 1인 RR스케줄러에 대해서도 계산하시오.

• RR
  ./scheduler.py -p RR -q 1 -l 100,200,300 -c
  

문제 4

SJF와 FIFO가 같은 반환 시간을 보이는 워크로드의 유형은 무엇인가?

• 작업의 길이가 오름차순으로 시스템에 도착하는 경우

문제 5

SJF가 RR과 같은 응답 시간을 보이기 위한 워크로드와 타임 퀀텀의 길이는 무엇인가?

• 작업의 길이 순으로 오름차순으로 시스템에 도착하고, 타인 퀀텀의 길이가 제일 긴 작업보다 큰 경우

• 사실 처음에는 타인 퀀텀의 길이가 제일 긴 작업보다 크면 된다고 생각했으나, 아니였음

  • ./scheduler.py -p SJF -l 100,200,300 -c
    
  • ./scheduler.py -p RR -q 300 -l 300,200,100 -c
    
    • 워크로드의 순서가 SJF처럼 짧은 것부터 오름차순이 아니면 안 됨

문제 6

작업의 길이가 증가하면 SJF의 응답 시간은 어떻게 되는가?

• 앞의 작업들이 끝나는 시간들도 늘어나므로, 아직 실행되지 않은 작업들의 응답이 늦어짐

변화의 추이를 보이기위해서 시뮬레이터를 사용할 수 있는가?

• ./scheduler.py -p SJF -l 100,200,300 -c
  
• ./scheduler.py -p SJF -l 200,300,400 -c
  
• ./scheduler.py -p SJF -l 300,400,500 -c
  

문제 7

타임 퀀텀의 길이가 증가하면 RR의 응답 시간은 어떻게 되는가?
(작업: 100,200,300)

• 타임퀀텀: 1
  
• 타임퀀텀: 2
  
• 타임퀀텀: 3
  
• 타임퀀텀: 100
  
• 타임퀀텀: 150
  
• 타임퀀텀: 200
  
• 타임퀀텀: 300
  
• 타임퀀텀: 400
  

• 보통은 늦어짐, 그러나 작업의 길이보다 타임퀀텀의 길이가 커지면 응답시간에 영향을 주지 않음

N개의 작업이 주어졌을 때, 최악의 응답 시간을 계산하는 식을 만들 수 있는가?

• 모든 작업이 q보다 큰 경우, 마지막 작업에 도달하기까지 N-1번의 타임 슬라이스만큼의 시간이 소요되므로 (N-1)*q
• 평균 응답시간의 wors-case는 (N-1)q / N