Scheduling

이준희·2022년 7월 7일

CS OS

OS

목록 보기

3/6

Scheduling

What is Scheduling?

다음에 어떤 Process가 실행될 것인지 정하는 Policy

Non-preemptive scheduling

지금 수행중인 running process가 반환하지 않으면 CPU를 뺏어오지 못한다
프로세스는 반드시 협조적이어야 한다

Preemptive scheduling

process가 CPU를 반환하지 않더라도 스케줄러가 강제로 CPU를 뺏어온다
timer inturrupt와 비슷하다

용어 설명

Workload
- CPU로 수행하는 작업의 집합(Process와 비슷하다)
Scheduler
- 다음에 수행할 job을 결정하는 로직
Metric
- 스케줄의 성능을 비교하는 지표
- Turnaround time(어떤 job이 시작해서 완료까지 걸리는 시간) : T_complete - T_arrival
- Fairness(job들이 얼마나 공평하게 CPU를 받았는지)
- Response time(도착시간부터 첫 실행이 될 때까지의 시간) : T_firstrun - T_arrival

Workload의 가정

각 작업은 같은 시간동안 수행된다
각 작업은 같은 시간에 도착한다
각 작업은 완료될 때까지 수행된다
각 작업은 CPU만 사용한다
각 작업의 수행시간을 알고 있다

FIFO(First In, First Out)

먼저 온 job의 순서대로 처리한다.

매우 간단하다
현실에서 사용되는 방법이다(마트의 계산 줄 서기 등)
Non-preemptive하다
평등하다

위의 사진에서 평균 turnaround time은 20초이다.

단, 첫번째 가정을 완화해보자

위의 사진에서 평균 turnaround time은 110초가 된다.
이러한 경우에 FIFO는 좋지 못하다.

SJF(Shortest Job First)

수행시간이 짧은 job을 먼저 수행한다

Non-preemptive하다

SJF를 사용하면 turnaround time이 50초로 짧아졌다.

이번에는 두번째 가정을 완화해보자.

A가 시작된 뒤에 B와 C가 도착해버리면 turnaround time은 103.33초가 되어버린다.

STCF(Shortest Time-to-Completion First)

SJF에다가 preemptive를 추가한 것이다.
새로운 job과 원래 수행중이던 job을 비교해서 짧은 것을 수행한다.
이로써 가정 2번과 3번을 완화해주었다.

B와 C가 도착했을 때 길이를 비교하고, 짧은 B와 C를 먼저 수행해주었다.
이 경우에 turnaround time은 50초로 짧아진다.

RR(Round Robin) Scheduling

각 job에게 time slice를 할당해주고 time slice를 다 쓰면 다음 job에게 CPU를 넘기는 방식이다

time slice는 반드시 timer interrupt의 배수가 되어야 한다
preemptive하고, No starvation하다
RR은 공평하지만, turnaround time이 길어질 수 있다

SJF를 사용한 방식으로, response time은 좋지 못하지만, turnaround time에 강점이 있다.
response time : 5초, turnaround time : 10초

RR를 사용한 방식으로, turnaround time은 좋지 못하지만, response time에 강점이 있다.
response time : 1초, turnaround time : 14초

Time slice의 길이는 어떻게 정할까?

Shorter time slice
- response time에 강점이 있다
- context switching이 더 많이 발생하기 때문에 지연시간이 걸릴 수 있다
Longer time slice
- switching이 적게 일어난다
- response time이 느리다

context switching과 response time은 서로 trade-off 관계에 있다!