오퍼레이팅 시스템 : Processor Scheduling Ⅰ

1. Types of processor scheduling

1) Terminologies

1. Burst(time)

• CPU Burst : CPU가 작업을 실행하는 데 걸리는 시간
• I/O Burst : CPU가 I/O를 wait하는 데 걸리는 시간

2. CPU-I/O burst cycle

• 각 프로세스 실행은 CPU execution(실행) 및 I/O wait 주기로 구성된다.
• CPU 및 I/O Burst 교대

3. 프로세스 유형 또는 프로그램 동작

• (a) CPU(또는 processor) bound
  • I/O로부터 blocking 전 CPU의 long burst
  • 프로세스가 주로 계산 작업을 수행하고 때때로 I/O 장치를 사용하는 경우에 processor bound로 간주된다.
• (b) I/O bound
  • I/O로부터 blocking 전 CPU의 short burst
  • 프로세스를 실행하는 데 걸리는 시간이 주로 I/O 작업 대기 시간에 따라 달라지는 경우 프로세스는 I/O bound로 간주된다.

2) Types of Scheduling

• Multiprogramming의 핵심은 scheduling이다.
  • 일반적으로 네 가지 유형의 스케줄링이 포함된다.
    1. Long-term scheduling : 실행할 프로세스 풀에 추가하는 결정(multiprogramming과 관련)
    2. Medium-term scheduling : main memory에 부분적으로 또는 전체적으로 있는 프로세스 수에 추가하는 결정
    3. Short-term scheduling : 프로세서가 사용 가능한 프로세스를 실행할 것인지에 대한 결정
    4. I/O scheduling : 보유 중인 프로세스의 I/O 요청에 대한 결정은 사용 가능한 I/O 장치에서 처리해야 한다.
  • Processor scheduling의 목적
    • 시간이 지남에 따라 프로세서가 시스템 목표를 충족하는 방식으로 실행할 프로세스를 할당한다.
  • Processor scheduling의 세가지 유형
    • 이러한 기능을 수행하는 상대적 빈도에 따라서 구분됨
    • Long-term scheduling과 medium-term scheduling
      • multiprogramming의 정도와 관련이 있다.
    •  이 장에서는 short-term scheduling에 중점을 둠
      • actual scheduling function 관련

(1)  Types of Processor Scheduling

1. Long-term scheduling
   • 새 프로세스가 생성될 때 수행됨
   • 현재 active 상태인 프로세스의 집합에 새 프로세스를 추가할지 여부
2. Medium-term scheduling
   • degree of multiprogramming 관리가 필요한 경우
   • main memory에 적어도 부분적으로 있으므로 실행에 사용할 수 있는 프로세스에 프로세스를 추가할지 여부
3. Short-term scheduling
   • 현재 프로세스를 차단하거나 현재 실행 중인 프로세스를 preempt(선점)할수 있는 기회를 제공할 수 있는 이벤트가 발생할 때마다 호출
   • 프로세서에서 사용 가능한 프로세스를 실행할 것인지에 대한 결정

• 일부 시스템에서는 새로 생성된 프로세스가 swapped-out condition에서 시작될 수 있다.
• processs bound된 프로세스와 I/O bounde된 프로세스를 혼합하고 I/O 사용량을 조절한다.

3) Scheduling Criteria(평가 척도)

• 일반적으로 사용되는 기준은 2차원으로 분류할 수 있다,
  1. User Oriented(사용자 지향)
     • Turnaround time : 프로세스의 submission과 completion의 시간 간격
     • Response time : interactive process의 경우, submission of a request에서 응답이 수신되기 시작할 때까지의 시간
     • Deadlines : Process completion deadlines을 지정할 수 있으며 해당 프로세스가 deadline 내에 완료되어야 한다.
  2. System Oriented(시스템 지향)
     • Throughput(처리량) : 시간 단위당 완료된 프로세스 수
     • Processor utilization : 프로세서가 사용 중인 시간의 백분율
     • Fairness : 프로세스는 동일하게 취급되어야 하며, 어떤 프로세스도 starvation을 겪어서는 안됨
• turnaround time을 기준으로 스케줄링 알고리즘이 분류됨
• 슈퍼 컴퓨터의 경우 system oriented criteria가 더 중요
• short-term scheduling의 주요 목표는 시스템 동작의 하나 이상의 측면을 최적화하는 방식으로 프로세서 시간을 할당하는 것

4) Which metrics are important?(어떤 측정 기준이 중요하나?)

• Scenario and Observation
  1. 슈퍼 컴퓨터
     • 사용자가 제출한 대규모 장기 실행 작업
     • CPU bound된 작업이 많고 I/O가 적은 것
  2. 클라우드 서비스를 위한 서버 컴퓨터 
     •  각 작업이 해당 공유 비율에 따라 CPU 리소스를 받도록 함
  3. Personal Computer
     • 인간은 데스크탑의 상호 작용을 좋아함
     • I/O가 진행될 때까지 대기하는 경우가 빈번함
  4. Embedded system or Real-time
     • 신속한 인터럽트 처리 및 task dispatching 강조
     • A mixed of criticality

2. Selection Function

• ready process 중 실행을 위해 다음에 선택할 프로세스를 결정한다.
• function은 우선순위, resource requirement(자원 요구사항) 또는 프로세스의 execution characteristics(실행 특성)에 기초할 수 있다.
  • w : 지금까지 시스템에서 소요된 시간, waiting ( 대기시간 )
  • e : 지금까지 실행에 소요된 시간 ( 수행시간 )
  • s : e를 포함하여 프로세스에 필요한 총 서비스 시간. 일반적으로 이 수량은 사용자가 추정하거나 제공해야 함.( 예상수행시간 )
• 예를 들어, selection function max[w[는 FCFS discipline를 가리킨다. 
  • max[w]는 ready state의 프로세스 중 대기시간(w)가 가장 큰 프로세스를 다음 프로세스로 결정함

3. Desicion Mode

• seleciton function이 실행되는 시간의 인스턴스를 지정한다.
• 두 가지 general category가 있다.
  1. Non-preemptive(비선제적)
     • 이 경우 프로세스가 running state가 되면 (a) 프로세스가 종료되거나 (b) I/O를 기다리거나 일부 운영 체제 서비스를 요청하기 위해 자체적으로 block될 때까지 프로세스가 계속 실행
  2. Preemptive(선제적)
     • 현재 실행 중인 프로세스가 운영 체제에 의해 중단되어 ready state로 이동할 수 있다.
     • preempt에 대한 결정은 새 프로세스가 도착했을 때,  blocked process를 ready state로 만드는 인터럽트가 발생했을 때 또는 clock interrupt를 기준으로 주기적으로 수행될 수 있다.

4. Scheduling Algorithms

• 다음 알고리즘들을 설명하기 위한 프로세스들의 정보

1) FIFO(First In, First Out)

• 현재 프로세스 실행이 중지(cease)되면 ready list에서 w가 가장 긴 프로세스가 선택된다.
  • FCFS(First Come First Served)라고도 알려져 있음
• Selection Function : max[w]
• Decision Mode : Non-preemptive
• 장점 / 단점
  1. 가장 단순한 scheduling policy
  2. 짧은 프로세스보다 긴 프로세스에서 더 나은 성능 제공
  3. I/O-bound 프로세스보다 processor-bound 프로세스를 더 선호
     • 대부분 또는 모든 I/O 디바이스가 idle 상태일 수 있다.
• FIFO는 convoy effect(호송 효과)로 인해 어려움을 겪을 수 있다.
  • CPU가 ready queue의 앞쪽 끝에서 더 높은 burst 시간의 프로세스를 가져오면 더 낮은 burst 시간의 프로세스가 wait될 수 있다.
  • 프로세스 Y : 시스템에 있는 총 시간이 필요한 processing time의 100배이다.

Y 프로세스는 앞에 long porcess가 있어서 1초짜리임에도 불구하고 Turnaround time이 100배가 됨

(1) FIFO 예시

• Turnaround time(arrival time - finish time) : A(3 - 0=3), B(9 - 2 = 7), C(13 - 4 = 9), D(18 - 6 = 12), E(20 - 8 = 12)
• Average Turnaround time : (3 + 7 + 9 + 12 + 12) / 5 = 8.6

2) SPN(Shortest Process Next)

• FCFS에서 긴 프로세스를 선호하는 편향(bias)를 줄이는 또 다른 접근 방식은 SPN policy이다.
• 짧은 프로세스가 queue의 맨 앞으로 이동한다.
  • Shortest job First(SJF)라고도 불림
• Selection function : min[s]
• Decision mode : Non-preemptive
• 장점 / 단점
  1. TAT(turnarround time) 측면에서 전반적인 성능이 크게 향상됨
  2. 더 긴 프로세스에 대한 starvation 가능성이 생김
     • 보다 짧은 프로세스가 안정적으로 공급되는 한
  3. 어려운 점은 필요한 프로세스 시간을 알아야 한다는 점이다.
     • OS는 각 프로세스에 필요한 시간의 실행 평균을 유지할 수 있음
     • Simple Average

• 매번 전체 합계를 다시 계산하지 않도록 하기 위해서 rewrite할 수 있다.

(1) SPN 예시

• Turnarround time : A(3 - 0 = 3), B(8 - 2 = 6), C(15 - 4 = 11), D(20 - 6 = 14), E(11 - 8 = 3)
• Average turnarround time : (3+7+11+14+3) / 5 = 7.6

(2) Exponential average

• 더 최근의 인스턴스는 미래의 동작을 반영할 가능성이 높기 때문에 더 큰 weight(비중)을 둠
• 미래 가치를 예측하기 위한 일반적인 기법

알파는 wait time(0 ~ 1사이의 실수)

(3) Example (FIFO vs SPN)

1. Case : A = 20, B = 30, C = 10

• SPN 또는 SRT는 뛰어난 turnarround time performance를 제공한다(shorter process를 더 선호)

2. Case : A = 20, B = 20, C = 20

• workload에 따라 단순히 FIFO가 더 나은 성능을 발휘할 수 있다.(경우에 따라 SPN보다 FIFO가 나을 수 있다,)
  • 아래의 경우 TAT는 같지만 SPN이 추가적으로 프로세스 Service time을 구하기 위한 계산이 필요함

3) SRT(Shortest Remaining Time)

• 이 schedular는 항상 예상 남은 시간이 가장 짧은 프로세스를 선택한다.
• SPN의 preemptive version
  • 새로운 프로세스가 ready 상태가 될 때 현재 프로세스를 preempt(선점)
  • 긴 프로세스에게 불이익을 준다.
• Selection Function : min[s - e] ( 남은 수행 시간)
• Decision mode : preemption
• 장점 / 단점
  • 또한 SPN에 뛰어난 turnarround time 성능 제공
  • Overhead가 높을 수 있음
  • Starvagion은 여전히 발생할 수 있다.

SRT와 SPN의 공통 문제점
1. s에 대한 문제 : s라는 시간을 계산을 해야 함
2. long process에 대한 starvation 가능성 문제

(1) SRT 예시

• Turnarround time : A(3 - 0 = 3), B(15 - 2 = 13), C(8 - 4 = 4), D(20 - 6 = 14), E(10 - 8 = 2)
• Average turnarround time : (3+13+4+14+2) / 5 = 7.2

4) HRRN(Highest Response Ratio Next)

• R 값이 가장 큰 ready process를 선택
  • Response ratio : normalized turnaround time
    • 실제 서비스 시간에 대한 turnarround time의 ratio
    • R = (w + s) / s
• Selection Function : max[(w+s)/s]
• Decision Mode : Non-preemptive
• 장점 / 단점
  1. 프로세스가 길어지면 프로세스의 age를 설명하기 때문에 결국 competing shorter job을 얻게 된다.
     • w + s / s = w / s + 1 → s가 작을 수록 R이 커지고 w이 클수록 R이 커짐
     • 결과적으로 long process의 starvation 문제를 해결
  2. 예상 서비스 시간을 추정해야 한다.

(1) HRRN 예시

• Turnarround time : A(3 - 0 = 3), B( 9 - 2 = 7), C(13 - 4 = 9), D(20 - 6 = 12), E(15 - 8 = 7)
• Average turnarround time : (3+7+9+14+7) / 5 = 8.0

non-preemptive이기 때문에 한 프로세스가 끝날 때마다 ready queue에 존재하는 프로세스의 R값을 구해야 함

• t = 9, C의 R(7 + 6 / 6), D의 R(3 + 5 / 5), E의 R(1 + 2 / 2) --> C가 다음 프로세스로 채택

5) Round-Robin

• FIFO로 인해 짧은 job이 겪는 패널티를 줄이는 간단한 방법
• 각 프로세스는 preempt(선점)되기 전에 slice of time이 주어진다.
  • timer를 기준으로 preemption 사용
  • 이 기술은 time slicing으로 알려져 있다,
• Seleciton Function : constant(상수)
• Desicion Mode : Preemptive → process switch가 non-preemptive보다 상대적으로 많아저 비용이 증가

(1) Round-Robin 예시

• Turnarround time : A(4 - 0  = 4), B(18 - 2 = 16), C(17 - 4 = 13), D(20 - 6 = 14), E(15 - 8 = 7)
• Average turnarround time : (4 + 16+13+14+7) / 5 = 10.8

(2) Round-Robin 특징

• 설계 문제는 time slice 길이가 q인 것이다.
  • 만약 ready queue에 n개의 프로세스가 있다면 time slice는 q이다.
  • (n - 1)q 시간 단위 이상 기다리는 프로세스는 없다.
• shorter time slice
  • response time 단축
  • clock interrupt 처리, process switch 수행 및 scheduling function과 관련된 scheduling overhead가 있다.
  • long process가 불리
  • SPN
• longer time slice
  • response time 안 좋음
  • scheduling overhead 감소
  • short process가 불리
  • FIFO

(3) Example(according to q)

1. Case : A = 15, B= 5, C =55, D = 5

• q가 작아질수록 response time은 좋아지지만 turnarround time은 경우에 따라 다름

2. Case A = 20, B = 20, D = 20

• turnarround time과  response time 사이의 trade-off(균형 조절)
• q가 작을수록 response time은 개선되지만 turnarround time은 악화될 수 있다.

(4) Exampel (Incorporating I/O - I/O 통합)

• system utilization 관점에서 좋은 알고리즘은?
• 예시 : 두 프로세스
  • A : 10ms 동안 실행하고 50ms동안 I/O에 대해 대기
  • B : No-waiting(CPU-intensive) → CPU bound process

• q = 100ms, scheduling cycle 동안 CPU는 100%(110/110)로 사용, I/O는 50/110만큼 사용
• q = 10ms, scheduling cycle 동안 CPU는 100%(60/60)로 사용, I/O는 50/60만큼 사용

(5) The durations of CPU bursts

• 프로세스에 따라, 그리고 컴퓨터에 따라 크게 다르지만 frequency curve(주파수 곡선)을 갖는 경향이 있다.

• 짧은 CPU burst 수가 많고 긴 CPU burst 수가 적은 분포

(6) Drawback of round robin

• processor-bound process는 일반적으로 실행하는 동안 전체 time quantum을 사용하고 즉시 ready queue로 돌아간다.
  • CPU-bound process : time slice를 다 사용
• I/O-bound process는 짧은 시간 동안 프로세서를 사용한 다음 I/O에 의해 blocked된다.
  • I/O-bound process : time slice를 다 사용 x

<Solution> → Short process가 유리할 수 있게 하거나 long process에게 패널티를 주는 방식으로 균형을 맞추자

• Virtual Round Robin
• Multi-Level Feedback Queues

6) Virtual Round Robin(VRR)

• 더 긴 프로세스를 위해 bias(편향)을 줄인다. → short process에 favor를 주는 방식
  • CPU-bound process는 일반적으로 실행 중에 complete time quantum을 사용하고 즉시 ready queue로 돌아간다.
• dispatching decision이 내려질 때,
  
  • auxiliary(보조) queue의 프로세스가 main ready queue의 프로세스보다 우선시 한다.

7) Multi-Level Feedback Queue

• 프로세스가 queue 간에 이동할 수 있다.
  • 이 개념은 CPU burst의 특성에 따라 프로세스를 분리하는 것이다.
  • Task는 우선 순위가 가장 높은 run queue에서 실행을 시작한다.
  • 프로세스가 time slice를 모두 사용한다면(Preemption)
    • 우선 순위가 낮은 다음 queue로 강등됨
    • 일반적으로 다음에는 두 배의 time slice 사용
  • Long-running job은 많은 interactive job으로 인해 starvation될 수 있다.

short process가 많으면 time slice가 작은 게 유리 / long process가 많으면 time slice가 큰 게 유리
→ time slice를 다 쓴 것이 long process일 확률이 큼을 이용해 dynamic scheduling이 나옴

Demotion : time slice를 다 쓰면 long process라고 판단하고 lower queue로 보냄

프로세스가 block되거나 preempt되면 프로세스를 여러 priority queue 중 하나로 넘긴다.

• queue가 꽉 차면 다음 queue로 자동으로 강등
• 이 scheme에는 여러가지 변형이 있다.
• 다음 파라미터로 정의된 multilevel-feedback-queue schedular
  • queue의 수
  • 각 queue에 대한 scheduling 알고리즘(queue마다 다른 time slice)
  • 프로세스를 promote(승격) 시기를 결정하는데 사용되는 방법
  • 프로세스를 demote(강등) 시기를 결정하는데 사용되는 방법
  • starvation을 피하기 위한 aging

5. 정리