[OS] 스케줄링
0. 스케줄링의 종류
상대적으로 소요하는 시간에 따라 스케줄링의 종류가 분류 된다. Long > Medium > short 순으로 오래 걸린다.
- Long-term scheduling (job scheduling): 어떤 프로그램들이 필요한지 결정하는데 걸리는 스케줄링을 말한다.
- Medium-term scheduling (swapper): disk에서 memory로 어떤 process 들을 올릴지 결정한다. 어느 process 상태를 suspend queue로 만들지 결정하는 시간.
- Short-term scheduling (CPU scheduler): 어느 프로세스를 cpu에게 진행 시켜지도록 할지 결정한다. 즉, 이전 시간에 코드로 배운 process_switch 함수 전에 어떤 녀석을 고를지 리턴해주는 schedule()함수의 역할을 의미한다.
- I/O scheduling: 이녀석이 가장 짧은 건 아니고 번외로 같은 device에 대한 어느 프로세스의 I/O를 먼저 해줄 지 고민하는 것을 의미한다.
지금부터 주로 다룰 이야기는 short-term scheduling 이다.
1. 스케줄링 알고리즘 속성
이제부턴 schedule() 함수가 어떤 컨셉으로 어느 프로세스에게 우선권을 줄 지 배워야 한다. 그 전에 용어 정리를 해보자.
- Selection function: ready queue에 존재하는 프로세스 중에서 어떤 프로세스를 고를지 기준이 되는 함수.
- Decision Mode: Selection function에서 나온 프로세스를 어느 시점 부터 실행시킬 것인지 하는 컨셉이다. Preemtive와 Nonpreemtive가 존재한다. 이게 무슨 말이냐면 뒤에서 자세히 다룰 것이니 일단 있다고만 생각하자.
입력 상태 예시를 먼저 들겠다. 앞으로 스케줄링 알고리즘 컨셉들에 대한 예시이다.
| Process | Arrival time | Service time |
| A | 0 | 3 |
| B | 2 | 6 |
| C | 4 | 4 |
| D | 6 | 5 |
| E | 8 | 2 |
A라는 프로세스가 0초에 입력이 들어오고 실행하는데 3초의 시간이 걸린다고 가정 한 것이다. B는 2초에 요청이 들어오고 6초의 실행시간이 필요한 프로세스 이다.
2. FIFO
첫번째 컨셉은 FIFO이다. 요청이 먼저 들어온 process 부터 끝내자는 것이다. 비선점 방식(Non-preemption)을 사용한다. 실행 순서는 아래와 같다.
| A | A | A | B | B | B | B | B | B | C | C | C | C | D | D | D | D | D | E | E |
즉, arrival time이 작은 녀석 부터 실행하면 된다. 꽤 무식해 보이지만 장점이 있다. 간단하다는 것과 긴 프로세스에게는 유리하다는 것, 스케쥴링 속도가 O(1)이라는 것이다. 하지만 단점도 있다. convoy effect라고 불리는데, E와 같이 금방 끝나는 녀석이지만 B,C,D 같은 무지막지한 녀석들 때문에 늦게 종료된다는 것이다.
이 경우 turnarround time(들어오기 ~ 처리 완료 시간. 반환 시간이라 부른다.) 은 A: 3, B: 7, C:9, D:12, E:12 이다. 평균 반환 시간은 8.6
3.SPN
Shortest-Process-Next의 줄임말. 사실상 최적에 가깝다. Non-preemtion mode이고 selection function은 min(s), s는 service time을 의미한다.
| A | A | A | B | B | B | B | B | B | E | E | C | C | C | C | D | D | D | D | D |
어떤 느낌이냐면 현재 진행 중인 프로세스가 끝나는 순간에 실행 예정 시간이 가장 짧은 녀석 부터 실행하는 것이다.
turnaround time는 A:3, B:7, C:11, D:14, E:3 이고 평균 반환 시간은 7.6이다.
최적인 이녀석도 사실상 단점이 존재한다. 수행시간이 긴 프로세스의 경우 우선순위가 밀리는 현상(starvation)이 발생 할 수 있다. 예를 들어 20초 걸리는 작업이 들어왔는데 이 전에 2초 간격으로 3초 실행시간이 걸리는 프로세스가 계속 들어온다면 20초 짜리는 영영 차례가 돌아오지 않는다.. ㅜㅜ 게다가 service time을 구하는 것이 사실상 불가능하다. 통계적으로 유의미한 계산 법이 있기는 하다. 해당 프로세스에 대한 지난 service time 역사들을 기록해 두고, 최근일 수록 가중치를 두어 service time을 예측하는데 영향력을 주게 한다. 하지만 지난 기록이 없으면 문제가 되고, 많다면 저장하고 연산도 꽤나 오래 걸린다. 그런 단점이 존재한다...
~~ 지금 부터는 이 2가지를 업그레이드 한 것이나 파생 상품을 설명할 것이다~~~
2.1 Round-Robin
2.1로 단락을 설정한 만큼 FIFO를 기반으로 한 것을 알 수 있다. preemtion이 가능한 mode 이고 selection function은 큐에 들어있는 순서이다. ?? FIFO랑 같은 건가? FIFO이긴 한데 대신 할당된 time quantum이 존재한다. 즉, 위의 예시에서 4 time quantum을 주었다고 가정하면, 어느 프로세스건 최대 4초 실행 하고 만약 실행할 거리가 남았다면 큐에 들어간다. 이후 큐에서 가장 앞에 있는 녀석을 실행한다.
| A | A | A | B | B | B | B | C | C | C | C | D | D | D | D | B | B | E | E | D |
turnaround time는 A:3, B:15, C:7, D:14, E:11 이고 평균 반환 시간은 10.0이다.
round-robin의 컨셉은 수행시간이 짧은 process의 convey effect를 해소하기 위해 등장했다.
만약 time quantum 값이 1이라면?
| A | A | B | A | B | C | B | D | C | B | E | D | C | B | E | D | C | B | D | D |
와 같다. 어찌 보면 사실상 SPN이 된다. 아주 미세하게 잘라버리니 실행시간이 짧은 프로세스가 더 먼저 끝나게 된다. 하지만 반대로 quantum 값을 굉장히 크게 주면 사실상 FIFO와 다를 바가 없다.
즉, 정리하자면 RR은 q값이 크면 FIFO이고 작으면 SPN이다. 오! 그럼 SPN이 최적이니 RR의 작은 q가 제일 좋네!! 라고 할 수 있지만 지금 일어나는 일은 process switch 이다. process switch는 지난시간에 자세히 다루었듯이 굉장히 cost가 큰 작업이다.. 보이지 않는 단점이 존재한다는 것.
3.1 SRT
Shortest-Remaining-Time의 줄임말로 남은 수행시간이 가장 짧은 녀석을 선택하는 selection function을 가지고 있다. 선점이 가능하다. 사실상 선점 가능한 SPN이라고 생각하면 된다. selection function을 수식으로 나타내면 min[s-e]라고 볼 수 있다. s는 service time, e는 실행 지나온 실행 시간.
| A | A | A | B | C | C | C | C | E | E | B | B | B | B | B | D | D | D | D | D |
turnaround time는 A:3, B:13, C:4, D:14, E:2 이고 평균 반환 시간은 7.2이다.
SPN version2 답게 굉장히 좋아 보이지만 위에서 말했듯 service time을 예측해야 한다는 것과 계속해서 min[s-e]를 계산해야 한다는 것이 쉽지 않다. 게다가 수행시간이 긴 프로세스에게는 startvation이 존재할 수 있다.. 위에만 봐도 B와 D의 turn around time이 무지막지한 것을 볼 수 있다.
4. HRRN
Highest-Response-Ratio-Next의 줄임말이다. selection function은 max[(q+s)/s]이고 q는 기다린 시간, s는 service time을 의미한다. Decision mode 는 non-preemtion. preemtion이면 혼란이 올 것 같다..ㅋㅋ
기본적으로 service time이 짧은 프로세스일 경우 우선순위가 높다. 하지만 service time이 큰 프로세스의 경우 q가 커지면서 우선순위를 갖게 될 수 있다.
즉, non-preemption이니 현재 진행하는 프로세스가 끝났을 때 적절한 밸런스 (q+s)/s를 따져서 다음 녀석을 고르게 된다.
| A | A | A | B | B | B | B | B | B | C | C | C | C | E | E | D | D | D | D | D |
turnaround time는 A:3, B:7, C:9, D:14, E:7 이고 평균 반환 시간은 8.0이다.
즉, 대기시간을 파라미터로 만들어서 longer process가 어느 순간에는 우선순위를 가지게 되는게 특징이다.