스케줄링과 그 방법: FIFO, SJF, STCF, RR / Busy Waiting, Sleeping

제한된 자원(CPU)를 어떻게 프로세스들에게 나누어 줄 것이냐의 이야기

 

* 단어 : 워크로드

작업의 양

컴퓨터 과학에서는 작업의 양+ 특성

 

* 단어: 매트릭스

평가 기준. 스케줄링의 경우..

1. 반환시간(Turnaround Time) : 종료시간 - 도착시간

2. 응답시간(Response Time) : 첫 실행시간 - 도착시간

3. 공평성(Fairness)

4. 처리율(Throughput)

5. Deadline

 

여기서 반환시간과 응답시간을 중점으로 보게 될 것입니다.

* 데드라인이 필요할 정도의 환경이면 애초에 스케줄링을 안 돌리고 프로세스 하나만 쭉 돌리는 게 나을 것입니다.

1. FIFO

프로세스 A, B, C가 동시에 도착하고, 같은 크기의 작업을 가지고 있을 경우

 

 

위 이미지의 1번 경우에서는

평균 반환시간: (10 + 20 + 30) / 3 = 20

평균 응답시간 = (0 + 10 + 20) / 3 = 10

 

문제는 2번 경우: 크기가 다른데, 작업 양이 큰 프로세스가 앞에 오는 경우입니다.

평균 반환시간: (100 + 110 + 120) / 3 = 110

평균 응답시간 = (0 + 100 + 110) / 3 = 73.3333...

뒤에 있는 프로세스들이 너무 밀림

 

장점: 단순하고 구현하기 쉬움

단점: 기다리는 시간이 너무 길어짐 (Convoy Effect)

 

2. SJF( Shortest Job First == SPN, Shortest Process Next )

프로세스 A, B, C가 동시에 도착한 경우

 

 

1번 경우, 동시에 들어온 프로세스들의 경우 길이가 짧은 프로세스부터 처리합니다.

평균 반환시간: (10 + 20 + 120) / 3 = 50

평균 응답시간 = (0 + 10 + 20) / 3 = 10

 

2번 경우는 A가 제일 양이 많은데 동시에 안오고 살짝 일찍 온 경우입니다.

이 경우 FIFO에서 보았던 문제가 다시 떠오릅니다.

 

 

3. STCF ( Shortest Time-to-Compliation First == SRT, Shortest Remaining-Time next )

SJF에다 Preemptive, 선점 개념(Dispatch)을 넣은 것입니다.

이전까진 하나의 프로세스가 Compliation 될 때까지 자리를 유지했으나,

이제는 실행중 더 짧은 프로세스가 들어오면 뒤로 미룹니다.

 

 

위 이미지가 예시입니다.

평균 반환시간: (10 + 20 + 120) / 3 = 50

평균 응답시간 = (0 + 10 + 20) / 3 = 10

 

문제는, 프로세스를 완전히 끝내고 넘어가야 하다보니 응답시간이 너무 깁니다.

응답이 너무 느리면, 답답해서 사용하지 못할 것입니다.

 

4. RR ( Round-Robin )

한 잡을 타임 슬라이스 (타임 퀀텀)만큼 멈추고 멈춥니다.

그리고 다음 잡으로 넘어갑니다. => 타임 슬라이스 만큼이 리스폰스 타임이 될 것

 

이 타임 슬라이스를 점점 줄이다, 컨텍스트 스위치의 오버헤드와의 균형을 적절히 맞출 때 멈춥니다.

타임 슬라이스를 작게 주면 응답성은 오르지만 오버헤드가 커져서, 트레이드오프가 있습니다.

(Amortization)

 

 

위 이미지 기준

평균 반환시간: (13 + 14 + 15) / 3 = 14

평균 응답시간 = (0 + 1 + 2) / 3 = 1

자른 만큼 응답시간은 빨라질 수 밖에 없지만,

그만큼 작업 완료가 늦어지니 반환시간은 늦어질 것입니다.

 

둘 중 하나는 포기해야 하는데,

대화형 컴퓨터는 응답 시간이 중요하니 응답 시간을 선택하게 됩니다.

 

 

Busy Waiting과 Sleeping

이번엔 I/O가 끼어드는 경우에 대해 생각해 볼 수 있습니다. 이러면 레디/런 두 상태만으론 문제가 있습니다.

Busy Waiting은 I/O 도중에 CPU 권한을 놓지 않고 붙잡는, Run 상태를 유지하는 걸 의미합니다.

그럼 I/O 시간만큼 손해를 보게 됩니다.

 

그래서 Sleep 방식을 사용하게 됩니다.

I/O 중에는 Wating (Blocked) 상태가 되고, 그 시간에 다른 프로세스를 끼워넣어 Run 시키는 것입니다.