[OS Chapter 5] CPU Scheduling

CPU 스케줄링

CPU burst와 I/O burst를 하는 단계가 번갈아가면서 사용

• CPU를 오랫동안 쓰는 job을 CPU bound job (점유) 계산 위주의 job
• I/O를 자주하는 job은 I/O bound job (빈도) I/O에 많은 시간이 필요한 job

 

여러 job이 섞여 있기 때문에 CPU 스케줄링(누구에게 얼만큼 시간을 주고 뺏을 것이냐)이 필요하다.

---

CPU Scheduler & Dispatcher

CPU Scheduler

• Ready상태 프로세스 중에서 CPU를 줄 프로세스를 고르는 역할

Dispatcher

• CPU의 제어권을 CPU Scheduler로 부터 선택된 프로세스에 넘긴다.
• 이 과정을 Context Switch라고 한다.

주의! 둘다 하드웨어가 아니라 운영체제 안에 있는 거다

 

스케줄링이 필요한 경우

1. Running -> Blocked (I/O요청하는 시스템 콜)
2. Running -> Ready (timer interrupt)
3. Blocked -> Ready (I/O완료 후 인터럽트)
4. Terminate

1, 4는 nonpreemptive(비선점형) 강제로 빼앗지 않고 자진 반납

2, 3은 preemptive(선점형) 강제로 빼앗음

---

Scheduling Criteria

(= Prefomance Index = Perfomance Measure = 성능척도)

 

시스템 입장에서 성능척도

• CPU utilization(이용률)
  • CPU를 가능한 바쁘게 일을 시키는 것
• Throughput(처리량)
  • 주어진 수행시간동안 몇개의 프로세스를 완료했는가.

프로그램 입장에서 성능 척도

• Turnaround Time(소요시간, 반환시간)
  • CPU를 가져온 후 다 쓰고 나갈때 까지의 시간
  • 프로세스가 끝나는 시간이 아니라 CPU 수행을 끝나는 시간
• Waiting time(대기 시간)
  • ready 큐에서 줄서서 기다리는 시간
  • 매번 CPU를 기다리는 시간의 총합
• Response time(응답 시간)
  • ready 큐에서 최초로 CPU를 얻기까지의 시간
  • 최초의 CPU를 얻기까지의 시간으로 waiting time과 차이점이 있음.

주의! 프로세스의 시작과 끝의 시간 관점이 아닌 CPU가 process를 가지고 있는 시간의 관점임

 

예시

중국집(시스템)

• CPU utilization = 주방장이 일하는 시간
• Throughput = 단위시간당 손님이 얼마나 왔다가냐

고객(프로그램)

• Turnaround Time = 고객이 와서 주문하고 먹고 나가는 시간(코스요리, 짜장면 둘다)
• Waiting time = 밥먹는 시간 외에 기다리는 시간
• Response time = 첫번째 음식이 나오기전까지의 시간

---

Scheduling Algorithm

1. FCFS(First-Come First-Serverd)

• 먼저 온 순서대로 먼저 처리해주는 알고리즘
• 비선점형
• 효율적이지 않음

예시

Process	Burst Time
P1	24
P2	3
P3	3

• Waiting time P1 = 0, P2 = 24, P3 = 27
• AVG(Waiting time) = (0 + 24 + 27) / 3 = 17

순서가 반대로 올경우 waiting time이 크게 달라짐

Convoy effect: 긴 프로세스가 앞에 오면 짧은 프로세스는 오래 기다리는 현상

 

 

2. SJF(Shortest Job First)

• CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
• 2가지 방식
  •  Nonpreemptive
    • 일단 CPU를 잡으면 CPU burst가 완료 될 때까지 CPU를 선점 당하지 않음
  • Preemptive
    • 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 뺏김
    • 이 방법을 Shortest Remaining Time First(SRTF)이다.

Average waiting time이 제일 적어지는 알고리즘이다. (SRTF)

예시

Process	Arrival Time	Burst Time
P1	0	7
P2	2	4
P3	4	1
P4	5	4

SJF(non-preemptive) 기준

P1 -> P3 -> P2 -> P4 순으로 진행된다.

CPU 나가는 시점(burst time)이 끝날 때 스케줄링을 한다.

Average waiting time = (0 + 6 + 3 + 7)/4 = 4

 

SJF(preemptive) 기준 = (SRTF)

P1 -> P2 -> P3 -> P2 -> P4 -> P1 순으로 진행된다.

새로운 프로세스가 왔을 때 스케줄링을 한다.

Average waiting time = (9 + 1 + 0 + 2)/4 = 3(모든 알고리즘 중에 Min)

 

문제점

• Starvation(기아 현상) - 시간이 긴 프로세스가 CPU를 못 얻을 수 있음
• CPU burst time을 미리 알수는 없음
  • 과거의 흔적을 가지고 추정은 가능 - 비슷한 패턴을 나타내기 때문
  • exponential averaging 식을 사용
    • tn = 실제 cpu burst시간
    • Tn = 예측한 cpu burst시간  
    • Tn+1 = 다음 예측한 cpu burst시간
    • Τn+1 = αtn + (1 - α)Τn
    • 전개를 해보면 최근의 값을 더 가중치를 많이 주고 과거의 값일 수록 가중치가 적어지는 모습이다.

 

 

3. Priority Scheduling

• 우선순위 스케줄링
• 가장 높은 priority를 가진 프로세스에게 CPU 할당
• preemptive / nonpreeptive 두가지 버전이 있음
  • 우선순위 높은 프로세스가 오면 CPU뺏을 수 있냐의 관점

주의! SJF도 priority scheduling의 일부이다. 기준 = predicted cpu burst time

 

문제점

• starvation
• 해결 방법: aging - process가 시간이 지남에 따라 우선순위를 조금씩 높여가는 것이다.

 

4. Round Robin(RR)

• 현대 스케줄링의 기반
• 선점형 스케줄링
• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐 (10 ~ 100ms)
• 할당 시간이 지나면 프로세스는 선점 당하고 ready queue에 맨뒤로 간다.
• 응답시간이 빨라짐
• 기다리는 시간은 본인의 CPU 타임에 비례하게 된다.

할당 시간을 크게 잡으면 FCFS, 작게 잡으면 context switch 오버헤드가 커진다.

 

예시

Process	Burst Time
P1	53
P2	17
P3	68
P4	24

할당시간 = 20

P1 -> P2 -> P3 -> P4 -> P1 -> P3 -> P4 -> P1 -> P3 -> P3 순으로 진행된다.

일반적으로 SJF보다 Average turnaround time은 길어지나 response time은 더 짧아진다.

 

---

Multilevel Queue

• 이제 큐가 한줄이 아니라 여러 큐가 있음
• 우선순위가 높은것부터 낮은 순으로 실행

출처: https://www.geeksforgeeks.org/multilevel-feedback-queue-scheduling-mlfq-cpu-scheduling/

예시

• 시스템
• 인터렉티브
• 언터렉티브 에디팅
• 배치
• 스튜던트

순으로 되어있으나 priority의 기준은 다름. (참고용)

 

고려해야 할 점!

• process를 어느 줄에 넣을 것인가
• 우선순위가 높은 큐만 먼저 처리할것인가

ready queue를 여러 개로 분할

• foreground queue(interactive)
• background queue(batch ~ no human interaction)

각 큐는 독립적인 스케줄링 알고리즘

• foreground - RR
• background - FCFS

큐에 대한 스케줄링이 필요

• Fixed priority scheduling - 우선순위가 높은순으로 부여, starvation 가능성
• Time slice - CPU time을 적절한 비율로 할당, ex) foreground 80% background 20%

 

Multilevel Feedback Queue

고려해야 할 점!

• 각 큐의 scheduling algorithm
• 큐의 승격/강등 기준
• 처음에 어디 큐에 집어넣을 것인가의 문제

 

처음에는 할당시간이 제일 작은 RR의 큐에 할당된다.

시간이 끝나면 낮은 큐로 옮김

프로세스 시간이 짧을 경우 우선순위가 높아지는 방식 길수록 점점 밑으로 쫓겨남 

---

Multi processeor scheduling

CPU가 여러개일 경우 스케줄링은 더욱 복잡해짐

 

Homogeneous processor인 경우

• queue를 한줄로 세워서 각 프로세서가 알아서 꺼내가게 해야한다.
• 반드시 특정 프로세서가 처리해야할 경우도 있는데 더 복잡해짐
• 예시! 헤어디자이너가 여러명 있는데 특정 디자이너에게 자르기

Load Sharing

• 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요
• 별개의 큐 vs 공동 큐

Symmetric Multiprocessing(SMP)

• 모든 프로세서가 대등하여 각 프로세서가 각자 알아서 스케줄링 하는 것이다.

Asymmetric Multiprocessing 

• 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

 

개념만 설명하고 넘어감.

Real Time Scheduling

Hard real time systems - 정해진 시간안에 반드시 끝내도록

Soft real time computing - 일반 프로세스에 비해 높은 priority를 갖는 프로세스 갖는 방식(데드라인 x)

Thread Scheduling

Local Scheduling - User level thread 사용자 프로세스가 직접 thread관리 운영체제가 모름

Global Scheduling - Kernel level thread의 경우 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정

---

Alogorithm Evaluation

Queueing models

• 확률분포로 주어지는 arriaval rate도착률가 service rate처리률 등을 통해 perfomance index

Implementation & Measurement (구현 & 성능 측정)

• 실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정비교

Simulation(모의 실험)

• 위의 실측방법보다 간단한 방법
• 모의 프로그램으로 작성후 trace(input data)를 입력으로 하여 결과 비교