운영체제의 기초 - 8. CPU Scheduling 1

Basics Concepts

Preemptible Resource: 한 프로세스가 점유한 상태에서 다른 프로세스에게 양보할 수 있는 자원

  - 대표적인 예. CPU, main memory

  - 어떤 프로세스가 CPU를 점유해서 돌고 있었는데 양보해야할 시점이 왔을 때 그 점유한 프로세스에 state를 안전하게 대피시키는 것(Context Switching)

Non-Preemptible Resource: 한 프로세스가 점유하면 사용을 마칠 때까지 프로세스에게 양보할 수 없는 자원

  - 대표적인 예. printer

  - 문서가 반쯤 프린터 됐는데 그걸 다른 job이 가져갔다 말도 안되죵

스케쥴링 문제를 나눠서 보면 2가지로 분류할 수 있음

1. 여러 프로세스가 CPU를 잡으려고 할 때 누구에게 줄 것이냐? 이것을 결정하는 문제

2. 프로세스가 CPU를 잡으면 얼만큼 CPU를 부여할 것인가?

리소스 문제도 2가지로 나뉠 수 있음

1. 다음에 누구한테 줄 것이냐?

2. 일단 잡은 놈 있으면 얼만큼 그 리소스를 사용하게 할 것이냐?

이것을 공부하는 것이 이번 목차의 포인트~!

CPU Burst: 프로그램의 수행 중에 연속적으로 CPU를 사용하는 단절된 구간, 스케줄링의 단위(CPU를 받아 수행하는 시간단위)

I/O Burst: 프로그램의 수행 중에 I/O의 완료를 기다리며 블록되는 구간

CPU 스케줄링을 얘기할 때는 한 프로세스 단위의 프로세스를 말하는 것이 아니라

그 프로세스가 수행하는 CPU Burst 단위로 스케줄링을 말한다

CPU Burst의 사이즈에 따라 스케줄링 기법이 달라진다.

CPU Scheduling이 결정하는 2가지

- 현재 프로세스가 수행을 하지 않아야 할 때 다음에 어떤 프로세스에게 CPU를 줄 것인가를 결정하는 작업

- 그 프로세스가 CPU를 할당 받으면 얼마나 오랫동안 수행할 것인가?

CPU의 State transition에 중요한 3가지 (ready, waiting, running)

ready -> running: dispatcher

running -> ready: H/W interrupt -> Operation scheduler 개입 -> preemptive  scheduling (강제로 CPU 뺏음)

running -> waiting: Non-preemptive scheduling (자기 스스로 CPU  yield() 함수 호출)

running -> terminated: Non-preemptive scheduling 

waiting -> ready: preemptive  scheduling 의 한부분이 됨. 왜? asynchronous이벤트가 발생해야 함

이와 같이 스케줄링이라는 것은 Process state transition 다이어그램에서 state transition을 촉발하는 행위들이다.

이 전에 상세하게 설명했음

Scheduling Policies (1)

스케줄링의 목적

- 자원활용의 극대화

- 오버헤드 최소화

- 문맥교환(context switching) 최소화

- CPU time을 여러 프로세스들에게 골고루 나눠주는 것

Aging: 태스크가 CPU를 기다리는 시간에 비례하여 우선순위를 점차적으로 높이는 기법

스케줄링의 목적

- waiting time 최소화

- response time 최소화

- turnaround time 최소화

- throughput(처리량) 최대화: 단위시간에 그 컴퓨터 시스템이 수행을 종료시키는 프로세스의 개수

   CPU를 많이 소모하면서 수행해야 하는 job들

CPU Burst 단위로 FIFO 함

장점: 단순하고 직관적임

단점

- 긴 CPU Burst를 이용해서 독점현상이 발생 이를 예방하기 위해 OS가 timer를 통해 강제로 개입

- short job이 왔을 때 특별히 처리해 주지 못 함

- 어떤 순서로 job이 오느냐에 따라 responce time에 큰 영향을 줌

FIFO로 스케줄링할 때 Ready queue에 프로세스가 여러개 있으면 먼저 온 것을 먼저 수행시키는 것 보다 

CPU Burst time이 짧은 것을 먼저 수행시키는 것이 더 좋음

그것이 Shortest Job First (SJF) 스케줄링임 (= optimal 알고리즘)

SJF 스케쥴링의 문제점

운영체제가 태스크의 남은 CPU Burst Size를 예측할 수 없음

2가지로 나뉠 수 있음

Non-preemptive: 일단 도착해서 ready queue를 쫙 보고 어떤 job이 CPU burst time이 제일 짧다고 한다면 걔한테 CPU를 할당

  - 존재하지 않는 알고리즘. CPU burst size를 다 안다고 가정

preemptive: 현재는 가장 짧은 cpu burst여서 수행을 하고 있었는데 새로운 프로세스가 도착. 그런데 새로운 프로세스가 더 짧다 했을 때 rescheduling하는 것

  - preemptive shortest job first 알고리즘을 Shortest Remaining Time First(SRTF) 또는 Shortest Time to Completion First(STCF)라고도 한다.

  - 즉, 남은시간이 제일 짧은 프로세스한테 CPU를 할당한다는 의미

Preemptive SJF의 스케쥴링 시점

- 현재 수행 중인 태스크가 종료될 때

- 새로운 태스크가 생성되거나 깨어날 때

Shortest Time to Completion First(STCF)의 문제점: Burst size를 예측해야 함

Burst size를 예측하는 기법 (Exponential average 지수 평균)

 - 어떤 프로세스가 도착했을 때 해당 CPU burst size를 예측

 - 바로 직전의 실제 측정한 burst size에 알파를 곱하고 (1-알파)를 그 전에 예측했던 값에 곱함

 - 알파 = 0  //  과거의 근사값만 고려 (최근 history는 무시)

 - 알파 = 1  //  바로 지난번의 burst size를 이번 size로 받아들임

 - 알파의 값을 크게 하면 Recent history를 보는 것이고

 - 알파의 값을 작게 하면 아주 옛날 history를 보면서 CPU burst 사이즈를 예측하게 됨

 - 결국 알파값을 찾아야 하는데, 알파값은 애플리케이션 마다 다르고 workload(작업량) 마다 다르기 때문에

 - 알파에 적합한 값을 찾는 것은 불가능 함 (이론적 개념일 뿐 실제로 적용하기에 어려움)

SJF가 optimal한 것은 알고 있는데 CPU burst time을 예측할 수 없기 때문에 포기하는 것은 억울함..

Round Robin 스케쥴링은

FIFO로 스케쥴링을 하되 timeout 값을 설정하여 CPU Burst size가 timeout보다 크면 수행을 강제종료당하고 ready queue 맨뒤로 보내는 방법임.

- Timeout값을 얼마로 할 것인가? (timeout 값을 RR에서는 time slice라고 함)

RR스케쥴링에서의 Time slice (Time Quantum)

태스크에게 CPU가 할당된 후  다음 스케쥴링을 위한 Timer interrupt가 발생할 때까지의 시간

RR스케쥴링이 효과를 발휘하려면 Time Quantum이 적절한 값 이어야함

Time Quantum이 무한대면 FIFO가 됨

Time Quantum이 0이면 엄청 정확한 알고리즘이 되지만 interrupt가 많이 수행되기 때문에 오버헤드가 커지게 됨

---

출처 - http://snui.snu.ac.kr/ocw/index.php?mode=view&id=647

출처 - http://snui.snu.ac.kr/ocw/index.php?mode=view&id=648