[OS] 운영체제 6. CPU Scheduling : CPU 성능척도, 스케쥴링 방법(FCFS, SJF, Priority Scheduling, Round Robin)

CPU Scheduling 

CPU를 누구에게 줄것인가, 주고나서 뺏어올 것인가

 

※ CPU and I/O Bursts in program execution

사용자와의 interaction 이 많은 프로그램일 수록 I/O burst 높다

 

 

※ CPU-burst Time의 분포

I/O bound job : I/O 많이 사용, many short CPU bursts

CPU bound job : CPU 많이 사용(계산 위주의 job), few very long CPU bursts.

-> 여러 종류의 job(process)이 섞여 있기 때문에 CPU 스케쥴링이 필요.

 

※ CPU Scheduler & Dispatcher

- CPU Scheduler :

Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다(OS 안에서 처리됨, 별도의 하드웨어나 소프트웨어가 아님)

- Dispatcher :

CPU 제어권을 CPU scheduler 에 의해 선택된 프로세스에게 넘긴다

이 과정을 context switch(문맥 교환)라고 한다

 

※ CPU 스케쥴링이 필요한 경우

1. Running -> Blocked (ex: I/O 요청하는 시스템 콜) : 자진 반납(nonpreemptive)

2. Terminate : 자진 반납(nonpreemptive)

3. Blocked -> Ready (ex: I/O완료 후 interrupt) : 강제 반납(preemptive)

4. Running -> Ready (ex: 할당시간만료로 timer interrupt) : 강제 반납(preemptive)

 

 

Scheduling Criteria

: Performance Index(=Performance Measure, 성능척도)

1. CPU utillization (이용료)

: Keep the CPU as busy as possible (ex: 주방장이 일하는 시간)

2. Throughput (처리량)

: # of processes that complete their execution per time unit

(ex: 얼마나 많은 손님이 다녀갔는가)

3. Turnaround Time (소요시간, 평균시간)

: amount of time to execute a particular process

cpu 처리시간의 총합

(ex: 손님이 와서 식사 하는 시간의 총합(코스요리의 경우 먹고 쉬고 먹고 쉬고를 반복, 먹는 시간의 합))

4. Waiting time (대기 시간)

: amount of time a process has been waiting in the ready queue

(ex: 손님이 와서 기다리는 시간의 총합(코스요리))

5. Response time (응답 시간)

: amount of time it takes from when a request was submitted until the first response is produced, not output

처음으로 응답되는데 까지 걸리는 시간

(ex: 손님이 와서 밑반찬을 네주는데 걸리는 시간)

 

※

1, 2 는 시스템 입장에서 CPU 성능척도

3, 4, 5 는 process 입장에서의 성능척도

 

 

CPU Scheduling 종류

1. FCFS(First-Come First-Served)

프로세스 도착 순서대로 처리(비선점형 nonpreemptive)

※ 문제점

Convoy effect : short process behind long process

앞에 긴 프로세스가 존재하여 뒤에 짧은 프로세스가 처리되지 못하는 현상

 

2. SJF(Shortest-Job-First)

- 각 프로세스와 다음번 CPU burst time을 가지고 스케쥴링에 활용

- CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케쥴

1) Nonpreemptive

CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 뺏기지 않음

2) Preemptive

현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time 을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗긴다. 이를 SRTF(Shortest-Remaining-Time-First)라고 부른다.

- SJF is optimal(최적화) : 주어진 프로세스에 대해 minimum average waiting time을 보장

 

※ CPU Burst Time의 예측

- 다음번 CPU burst time 은 추정(estimate)만 가능

- 과거의 CPU burst time 을 이용해서 추정 (exponential averaging)

CPU Burst Time 예측 공식 정리가 되어있는 곳 : https://darkluster.tistory.com/43

 

3. Priority Scheduling

- A priority number(integer) is associated with each process

- 가장 높은 우선수위를 가진 프로세스에게 CPU 할당(smallest integer = highest priority)

- SJF 는 일종의 priority scheduling

※ 문제점

Starvation(기아현상)

: low priority processes may never execute. (낮은 우선순위 프로세스가 영원히 CPU를 얻지 못하는 것)

※ 해결책

Aging(노화)

: as time progresses increase the priority of the process (시간이 지나면 우선순위를 올려주는 것)

 

4. Round Robin(RR)

- 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가진다 (일반적으로 10-100milliseconds)

- 할당 시간이 지나면 프로세스는 선점(preempted) 당하고 ready queue와 제일 뒤에 가서 다시 줄을 선다

- n 개의 프로세스가 ready queue에 있고 할당 시간이 q time unit 인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다 (어떤 프로세스도 (n-1)q time unit 이상을 기다리지 않는다)

※ 장점

1) 응답시간이 빠르다.

2) CPU가 길게 필요하면 길게 기다리고, 짧게 필요하면 짧게 기다린다. (짧은 프로세스는 빨리 나가고 긴 프로세스는 길게(많이) 기다리게 되므로 프로세스의 waiting time 과 turnaround time 이 비례)

※ 할당시간에 따른 차이

q large (할당시간이 길다면) => FCFS

q small (할당시간이 짧다면)=> context switch 오버헤드가 커진다.

 

Multilevel Queue

Queue가 여러줄이며 우선순위가 높은 큐의 프로세스가 CPU 우선권을 가진다

1) Ready queue를 여러개로 분할

  - foreground (interactive(IO))

  - background(batch - no human interaction)

2) 각 큐는 독립적인 스케쥴링 알고리즘을 가진다

  - foreground - RR (빠른 응답속도)

  - background - FCFS

3) 큐에 대한 스케쥴링 필요

  - Fixed priority scheduling : starvation 문제

  - Time slice : 각 큐에 CPU time을 적절한 비유로 할당한다

    80% to foreground in RR, 20% to background in FCFS

 

Multilevel Feedback Queue

프로세스 처리가 끝나면 바로 나감, 처리가 끝나지 못하면 두번째 큐로 이동, 또 처리가 되지 못했다면 맨 밑의 큐로 이동

처리가 짧은 프로세스에게 우선권을 먼저 준다

 

※ Multiple-Processor Scheduling

CPU가 여러개인 경우

1) Homogeneous processor 인 경우

- Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가도록

- 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우 문제가 복잡해진다

2) Load sharing

- 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요

- 별개의 큐를 두는 방법 vs. 공동 큐를 사용하는 방법

3) Symmetric Multiprocessing(SMP)

- 각 프로세서가 각자 알아서 스케쥴링 결정

4) Asymmetric multiprocessing

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

 

※ Real-Time Scheduling

1) Hard real-time systems : 정해진 시간안에 반드시 끝내도록 스케쥴링

2) Soft real-time computing : 일반 프로세스에 비해 높은 우선순위를 갖도록 해야 한다

 

3. Thread Scheduling

1) Local Scheduling : User level thread 의 경우 사용자 수준의 thread library에 의해 어떤 thread 를 스케쥴할 지 결정

2) Global Scheduling : Kernel level thread 의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케쥴러가 어떤 thread 스케쥴할지 결정 

 

 

※ Algoritm Evaluation 알고리즘 평가방법

1) Queueing models

확률 분포로 주어지는 arrival rate와 service rate 등은 통해 각종 performance index 값을 계산

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

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

3) Simulation (모의 실험)

알고리즘을 모의 프로그램으로 작성 후 trace를 입력하여 결과 비교

 

 

※ 이화여자대학교 반효경 교수님의 운영체제 강의 정리