[OS] 5. CPU Scheduling

CPU Scheduling : 자원을 어떤 시점에 어떤 프로세스에 할당할지를 결정하는 개념 ⇒ CPU를 어떤 방식으로 할당

CPU Scheduler

어떤 실행할 준비가 된 프로세스들 중에 어떤 프로세스를 선택할지 골라준다.

CPU scheduling을 언제 하냐

1. 프로세스 running to waiting state (I/O request)

2. 프로세스 running to ready state (e.g. time slice expiration)

3. 프로세스 waiting to ready state (e.g. I/O completion)

4. 프로세스 terminates

(1), (4) 의 경우는 non-preemptive 비선점 : 자원을 다 사용할 때 까지 해당 자원을 뺏을 수 없음

(2), (3) 의 경우는 preemptive 선점 : 실행중인 프로세스를 interrupt 할수 있거나, 준비상태로 이동 가능 한 케이스

Scheduling Criteria

높을수록 좋다

• CPU utilization : 사용량
  • CPU를 가능한 바쁘게 유지한다 ( 0% ~ 100% )
• Throughput : 처리율
  • number of processes / time unit (프로세스 / 단위시간)

---

낮을수록 좋다

• Turnaround time
  • 요청 → 만료까지의 시간
• Waiting time
  • CPU 할당 전까지 걸리는 시간, Ready queue에 있는 시간 총합
• Response time
  • 처음으로 response 받은 시간

Maximize : CPU utilization, throughput
Minimize : turnaround time, waiting time, response time

response time의 경우 평균값(average)을 기준으로 최소화할수 있고 편차(variance)를 기준으로 최소화 할 수 있는데 편차를 기준으로 최소화 하는 것이 모여있어서 위치특정에 용이하다

Sheduling: Introduction

Sheduling을 위해 아래의 상황들을 가정한다

1. 각각의 프로세스는 동일한 시간만큼 동작한다
2. 모든 프로세스는 동일한 시간에 도착한다
3. CPU가 활용 되는 케이스만 고려한다 (no I/O)
4. 각 프로세스의 run-time을 알고있다.

Scheduling Metics

Performance metric : Turnaround time

\[T_{turnaround} = T_{completion} - T_{arrival}\]

빨리 처리 되는게 좋아서 낮을수록 좋다
다른 metric은 fairness
Performance 와 fiarness 스케줄링에서 둘 다 잡기 어렵다

First In, First Out(FIFO)

First Come, First served (FCFS)

• 매우 간단하고 수행하기 쉽다

• 일괄처리 시스템에서는 효율적이다.
• 빠른 응답을 원하는 대화식 시스템에서는 비적합하다.

Why FIFO is not that great? - Convoy effect

각각의 프로세스는 동일한 시간만큼 동작한다는 (가정 1)을 없애자

Shortest Job First(SJF)

프로세스가 짧은 순으로 실행 ⇒ Non-preemptive sheduler

모든 프로세스는 동일한 시간에 도착한다는 (가정 2) 를 없애자

비선점 형태라 CPU를 뺏지 못한다

A가 길어서 B,C가 대기하고 있어야 돼서 turnaround가 길다 ⇒ 비효율적

Shortest Time-to-Completion First (STCF)

SJF에다가 선점 방식을 더한다 ⇒ 프로세스를 더이상 동시에 하지 못한다

SJF의 선점 버전

⇒ Shortest Job First(PSJF) 혹은 Shortest Remaining Time First(SRTF)이라고도 표현한다

새로운 프로세스가 들어오면 기존의 프로세스의 남은시간과 새로운 프로세스의 시간을 비교해서 시간이 더 짧은 프로세스부터 처리한다. ⇒ 대기시간 최소화

SJF 는 A,B,C가 들어왔을때 각각의 CPU burst time을 알고 누가 먼저 실행되는지 선택하는 알고리즘이다.

실제로는 각각의 프로세스에 대한 CPU burst time을 정확하게 알 수가 없다. 해당 스케쥴링 알고리즘을 적용하는데 있어서 각각의 프로세스에 대한 CPU burst time을 어떻게 정할 것인지가 중요한 점이다

이전 CPU burst times를 기반으로 해서 해당 프로세스의 burst time 추정할 수 있다.

exponential averaging

1. \(t_n\) = actual length of \(n^{th}\) CPU burst
2. \(τ_{n+1}\) = predicted value for the next CPU burst
3. α, 0 ≤ α ≤ 1 → 적응의 속도
4. Define : \(τ_{n+1}\) = \(αt_n + (1 -α) τ_n\)

New scheduling metric: Response time

프로세스가 처음 도착하고 CPU를 할당 받을 때 까지의 시간

\[T_{response} = T_{firstrun} - T_{arrival}\]

response time이 짧다 = CPU를 빠르게 할당 받았다

response time을 최소화하는 방식으로 알고리즘을 설계해야한다.

하지만 STCF는 response time이 좋다고 할 수 없다. 왜냐하면 남은 시간이 짧은 것부터 수행하는 알고리즘인데 가장 먼저 들어온것의 burst time이 길어서 가장 나중에 실행될 수도 있기 때문에 response time이 길어질 수 있다.

Round Robin (RR) Scheduling

Time slicing Scheduling

시간을 쪼개서 프로세스를 실행시키고 다음 프로세스로 넘어간다.

• Time slice는 Scheduling quantum으로도 불린다.

이 동작은 프로세스가 끝날때까지 반복

타임 슬라이스의 길이는 타이머의 길이보다는 길어야지만 스케쥴링 알고리즘 동작시킬 수 있다.

RR은 fair 하지만 turnadround time에서는 안좋다

The length of the time slice is critical

time slice가 짧아지면

• response time 향상
• context switching (overhead) 비용이 좋아진 성능으로인한 비용보다 커진다

time slice가 길어지면

• switching 비용은 줄어든다.
• response time 안좋아짐

적절한 time slice값을 선택하는것이 Scheduling Algorithm에서 중요하다

Incorporating I/O

CPU가 활용 되는 케이스만 고려한다는 (가정 3) 을 없애자 ⇒ I/O 고려

A는 I/O 요청이 들어오면 CPU를 반환하기 때문에 CPU → I/O → CPU 이런식으로 동작하다가 A가 끝나면 B를 동작한다.

CPU utilization을 최대화 하기 위해서 A가 I/O를 위해 CPU를 반환했을때 B를 동작할 수 있다.

I/O요청이 들어오면

• 프로세스를 ready 나 run이 아닌 block을 시킨다
• block을 시키면 그때 CPU에 다른 프로세스를 할당해서 수행할 수 있다.

I/O가 완료 되면

interrupt가 발생한다 OS가 block된 프로세스를 가져와서 ready 상태로 돌려놓고 다시 수행한다.

맨 위로 이동하기

OS 카테고리 내 다른 글 보러가기