Operating System: CPU Scheduling (Chapter 6)

State Diagram - revisited

• Batch jobs: 수행 해야할 일을 list up하고, 한 번에 수행하는 것
• New Queue: 새로운 process들이 모여있는 queue
• New Queue -> Ready Queue: Long-term scheduling이 New state process들 중 CPU를 줘도 괜찮은 것들을 선택
• Ready Queue -> Processor: Short-term scheduling이 process에게 CPU를 주면 process가 열심히 돌아감 
• Processor -> Ready Queue: time-out에 의해서 process가 다 끝나지 않았지만, CPU를 반납하고 ready state로 돌아감
• Processor -> Blocked Queue: 돌아가던 process에서 I/O 가 발생해서 blocked(=waiting) queue로 내려감
• Processor -> Release: 모든 instruction이 끝났기 때문에, process는 terminated state로 감
• 이번에 추가된 내용
  • Suspend state: memory를 할당받지 못한 process의 상태를 의미. Memory에 관련된 일이므로, medium-term scheduling에 의해 결정됨
  • Ready Queue -> Ready/Suspend Queue: 사용자에 의해 suspend stsate로 이동된 상황. suspend가 풀리면 바로 Ready queue로 이동
  • Blocked Queue -> Blocked/Suspend Queue: I/O interrupt 끝나기를 기다리던 중 suspend 된 process의 전이를 의미. 기다리던 중 I/O가 오면 ready/suspend queue로 이동

CPU Scheduling

• Multiprogramming environment에 필수
• CPU scheduler의 역할: memory에 올라온 process들 중에서 CPU를 잡으면 실행 가능한 process를 파악하고, 그 process에게 CPU를 할당함
• CPU scheduler가 결정을 내리는 상황들
  1. Running -> Ready: time out
  2. Waiting -> Ready: I/O finished interrupt가 도착. 
  3. Running -> Waiting: I/O request에 의한 전이
  4. Running -> Terminated: 모든 프로그램 수행 완료. 
• 위의 네가지 상황들 중, 1, 2는 preemtive, 3, 4는 non-preemtive이다.
  • 3과 4의 경우, process는 자신의 instructoin에 의해 CPU를 빼앗기게 된 것이므로 억울하지 않다. 
  • 그러나 1과 2의 경우 process는 다른 process의 상황에 의해 CPU를 빼앗기게 된 것이므로 억울하다. 
  • 이때, 2의 경우는 왜 CPU scheduling이 필요할까?
    • Waiting 하고 있든 process가 요청했던 I/O interrupt 처리는 kernel의 몫으로, 이를 위한 처리를 CPU가 하고 있다가, 처리가 다 끝나면 (waiting -> ready 전이 순간) CPU가 순간적으로 비게 된다. 
    • 이 때 이 CPU를 할당 받을 process를 골라야하기 때문에, CPU scheduling이 관여하게되는 것이다.  

Dispatcher

• CPU를 줄 process를 schduler가 결정하면, 실제로 CPU를 할당하는 역할을 한다
• Step1: Context switch 
• Step2: Switch to user mode
• Step3: User program에서 다음으로 수행해야할 곳으로 jump & restart
• Dispatch Latendcy: dispatcher에 의해 발생하는 지연시간으로, 대부분이 context switch overhead에 의한 것

CPU Scheduling Criteria (어떤 알고리즘이 좋은 Scheduling을 만드는가의 기준)

1. CPU Utilization: CPU가 노는 시간 없이 계속해서 돌아가는 것
2. Throughput: 단위 시간당 처리 가능한 process의 수
3. Turnaround time: 하나의 process가 처리되는 데 소요되는 시간
4. Waiting time: process가 ready queue에서 대기하는 시간의 합
5. Response time: process가 시작하고 사용자에게 첫 응답을 보내는데 걸리는 시간

• 가장 중요한 것 = (1) CPU utilization
• 그 다음으로 영향을 많이 미치는 것 = (4) Waiting time
  • (4)가 줄어들면, (2), (3), (5) 모두 영향을 미친다
• 다섯 가지 criteria 모두 만족 가능한 OS가 있는가? = NO
  • (2)와 (5)는 서로 상충되는 관계이다
  • (5)를 만족하기 위해서는 각 process가 CPU를 짧게 짧게 잡아야 한다 -> Context Switch↑ -> (2) 증가
  • (2)를 만족하기 위해서는 process가 한 번 CPU 잡으면 오래 잡아야 한다 -> (5) 증가 -> 사용자 만족 감소
• 그렇다면 어떤 criteria를 중점적으로 해야하는가? -> 설계하려는 device type 별로 다르게!
  • batch에서는 (2)가 중요, 일반 PC에서는 (5)가 중요 (사용자 만족과 직결되기 때문)

 

CPU Scheduling Algorithms

• 대표적인 종류: FCFS, Shortest Job First (SJF), Shortest-Remaining Time First (SRTF), Round Robin, Multilevel Queue, Multilevel Feedback Queue, Priority Scheduling(이건 알고리즘 아니고 framework)

FCFS (First Come First Serve)

• 처음 도착하는 process에게 먼저 CPU를 할당
• 장점: Non preemtive라서 공정함 
• 단점: Convoy effect. long process의 도착 순서에 따라서 waiting time 평균의 차이가 크다 

Shorted Job First (SJF)

• FCFS에서 얻은 교훈을 그대로 반영하여, next CPU burst까지 가장 시간이 짧은 process에게 CPU를 먼저 할당
• Non-preemtive, Preemtive 두 가지 shceme 모두 가능
  • Non-preemtive: P0가 돌고 있는 중에, P0의 남은 시간보다 더 짧은 process P1가 queue에 도착해도, P0는 CPU를 뺏기지 않고 계속 일함. Non-preemtive CPU scheduler들 중에는 SJF가 가장 짧은 waiting time 제공
  • Preemtive = Shorted-Remaining Time First(SRTF, 혹은 shortes-time to completion first로 STCF): P0가 돌고 있는 중에, P0의 남은 시간보다 더 짧은 process P1가 도착하면, P0는 CPU를 빼앗긴다. 언뜻보면 SRTF가 SJF보다 당연히 낫겠지! 라고 생각할 수 있으나, context switch overhead를 고려하면, SRTF가 항상 낫다고 하기 어렵다. 
• 근데 여기서 생기는 근본적인 문제: next CPU burst time을 어떻게 알지?
  • 결론: next CPU burst time을 알수는 없고 추정(estimate)할 뿐이다. 
  • 추정하는 공식이 있는데, 그 공식은 O(n)의 시간이 소요된다. 매우 빠른 속도로 연산되어야 하는 CPU Scheduler에는 O(logn)을 넘는 연산을 넣을 수 없다. 
  • 따라서 SJF나 SRTF는 실제로 사용되지 않는 알고리즘이다. 

Priority Scheduling

• process마다 매겨진 priority에 따라서 CPU를 배정하자는 framework의 일종
  • 예: SJF는 CPU burst time에 의해서 priority를 매긴 algorithm이다
  • 실제로 multimedia program을 수행하는 Process의 priority는 높게 매겨져 있다
• 발생 가능한 문제: Starvation
  • Priority가 낮은 long process는 계속 밀려 들어오는 다른 process들에 의해서 CPU를 빼앗긴다
  • 이로 인해 이 process는 영영~ 실행 되지 않는다
• 해결책: Aging
  • 시간이 지남에 따라서 Process의 priority를 점차 증가 시켜준다

Round Robin

• 지정된 time quantum q만큼만 CPU를 차지하고 시간이 지나면 Ready Queue의 맨 끝으로 가는 algorithm
• System에서는 upper bound를 제공하는 것이 무척 중요한데, RR을 따르면, 모든 process들은 (n-1)q 이하의 시간을 기다린다. (여기서 n은 process의 수)
• 장점: Response time이 짧아진다. 
• 단점: 잦은 Context switch로 인해서 waiting time이 길어진다. 
• time quantum q에 따라서도 scheduler의 특성이 달라진다. 
  • q가 너무 긴 경우: FCFS랑 차이가 없어진다. (convoy effect가 재발)
  • q가 너무 짧은 경우: 너무 잦은 Context switch로 인해서 waiting time이 완전 길어짐. 성능 저하

Multilevel Queue

• process가 수행하는 job의 종류에 따라 process는 I/O bound job, CPU bound job으로 나누어진다. 
  • 이때 I/O bound job은 주로 user와 밀접한 작업으로, response time이 매우 중요하다
  • 반면 CPU bound job은 user와 밀접하지 않아서, throughput이 상대적으로 중요하다 
• 이런 특성을 활용하여, process type 별로 서로 다른 queue를 두고, type 별로 다른 CPU scheduling을 적용하자는 것이 multilevel queue의 아이디어다
• 두 가지 queue로 구성된 multilevel queue를 소개하자면 아래 표와 같다

	Foreground Queue	Background Queue
Job	I/O bound job	CPU bound job
Scheduler	Round Robin	FCFS
Major Criteria	Response time	Throughput

• 두가지 queue 에 있는 process들 중 어느 queue의 것에 CPU를 먼저 할당할지 결정 해야한다
  • Fixed Priority Scheduling: 항상 Foreground에서 먼저 process를 선택한다. Foreground가 비어있는 경우에만 Background queue의 Process를 선택한다. 
    • 이럴 경우 background queue에서 Starvation 문제가 다시 발생 
  • Time Slice: foreground 80%, background 20%로 시간을 배분하여 process를 선택한다. 

Multilevel Feedback Queue

• Multilevel queue에서 발전된 형태. 
• Process는 늘 CPU bound job이나 I/O bound job 중 한가지 특성만 갖는 것은 아니다. CPU bound job을 수행하던 중, 일의 특성이 I/O bound job으로 변화될 수 있다. 이럴 경우 Multilevel Queue에서 해당 process가 계속 background queue에 있다면, context switch가 잦아지는 문제가 발생한다. 
• 따라서, 이런 문제를 해결하기 위해 queue 간에 이동을 허용한 것이 MLFQ이다. 
• 장점: I/O bound job 특성이 있는 일의 경우 response time 줄어든다. CPU bound job 특성으로 변하면 FCFS 수행하는 queue로 넘겨서 throughput을 높인다. 
• 단점: Too complex. 따라서 잘 사용되지 않는다.