22. CPU Scheduling(2)

안녕하세요. 오늘은 CPU Scheduling(스케쥴링) 두번째 시간입니다. 2021.11.30 - [학부공부/OS_운영체제] - 20. CPU Scheduling(1)

20. CPU Scheduling(1)

포스팅에서 CPU 스케쥴링에 대한 Basic concepts와 scheduling criteria를 살펴보았는데요. 오늘은 다양한 스케쥴링 알고리즘을 알아보도록 하겠습니다.

 

 

22.01. FCFS Scheduling

First-Come, First-Served Scheduling인 FCFS 스케쥴링은 Ready queue에 있는 순서대로 CPU의 자원을 할당합니다. 자료구조 과목에서 배웠던 익숙한 자료구조가 떠오르시죠? FIFO queue를 사용하여 간단하게 구현이 가능합니다. 하나의 Case를 살펴보겠습니다.

Process	P1	P2	P3
Burst Time	24	3	3

P1, P2, P3 순서대로 요청하였을 때 대기시간은 P1 = 0, P2 = 24, P3 = 27이 됩니다. 평균대기시간을 구하면 17이 되겠죠. 만약 P2, P3, P1 순서대로 CPU를 스케쥴링한다면 평균대기시간은 3이 됩니다. 첫번째 경우보다 짧은 대기시간을 가질 수 있습니다. 이 Case에서 알 수 있듯이 FCFS Scheduling은 job의 수행 순서에 따라 대기시간이 변할 수 있습니다. 이처럼 burst time이 긴 프로세스에 의해 짧은 프로세스의 실행이 지연되는 것을 Convey effect라고 합니다.

 

일반적으로 스케쥴러는 다양한 CPU Burst time을 가진 프로세스가 있을 때 짧은 응답시간을 갖게하는 스케쥴링일수록 좋습니다. 이때 빨리 시작할 수 있으려면 대기시간이 짧아져야 하는 것이죠. 이를 바탕으로 다른 스케쥴링을 알아보겠습니다.

 

 

22.02. Shortest-Job-First Scheduling(SJF)

평균대기시간을 짧게 하기 위해 Shortest-Job-First스케쥴링이 고안되었습니다. CPU Burst time이 가장 짧은 프로세스에게 CPU를 할당하는 것입니다. 이때 최소의 평균대기시간을 제공한다는 것은 증명할 수 있으니 시도해보시기 바랍니다.(아래의 증명을 두긴 했습니다. 아래로 내려가기 전에 시도해보시기 바랍니다.)

 

한가지 의문이 들 수 있는데요. 가장 짧다는 것의 기준은 무엇일까요?

여기서 짧다는 것의 기준은 평균대기시간을 짧게하기 때문에 remaining입니다. 하지만 남은 시간을 정확히 알기는 힘듭니다. 정보가 미리 주어진다면 가능하겠지만 어렵죠. 80년대에는 예상시간을 입력하게 하는 시스템이 있었는데 이러한 시스템은 사용자들이 우선순위를 앞당기기 위해 작은값을 임의로 집어넣는 문제가 있었습니다. 

 

비선점형과 선점형 스케쥴링에 대해 이야기해드렸었는데요. 각각 적용해 보겠습니다. 

Process	P1	P2	P3	P4
Arrival Time	0	2	4	5
Burst Time	7	4	1	4

비선점형 스케쥴링에서 평균대기시간은 4입니다.( (0 + 6 + 3 + 7) / 4 )

 

만약 Time quantum이 1인 선점형 스케쥴링(preemptive SJF = SRTF : Shortest Remaining Time First Scheduling)이라면 평균대기시간은 3이 됩니다. ( (9 + 1 + 0 + 2) / 4 ) QT마다 CPU burst time이 가장 짧은 프로세스를 선택합니다. 다만 이때 CPU burst time을 미리 알 수 없어 approximation, prediction합니다. 참고로 여기서 선점이라는 의미는 새 프로세스가 도착할 때도 스케쥴링을 한다는 의미입니다. 추가로 더 설명드리자면 latency라는 광범위하게 사용되는 용어는 여기서 응답시간을 가리키는 경우가 많습니다. 물론 대기시간을 의미하는 경우도 있고요.

 

선점형 프로세스는 심각한 단점이 있는데 바로 계속 새로운 프로세스가 들어오면 실행하지 못하는 프로세스가 존재할 수도 있다는 것입니다. 이를 starvation(기아 상태)이라고 합니다.

 

Starvation

프로세스가 끊임없이 필요한 컴퓨터 자원을 가져오지 못하는 상황. 기아 상태는 스케줄링이나 상호 배제 알고리즘의 오류에 기인하지만 자원 누수에 의해 일어날 수도 있으며 서비스 거부 공격을 통해 고의적으로 발생할 수도 있다. 기아 상태는 과도하게 단순한 스케줄링 알고리즘에 의해 발생하는 것이 보통이다. 이를테면 (낮은 품질로 설계된) 멀티태스킹 시스템이 처음 두 태스크 간에 (세 번째는 실행하지 않고) 무조건 교환을 하는 경우 세 번째 태스크는 CPU 시간을 기아 상태로 만든다. 커널의 일부인 스케줄링 알고리즘은 자원을 균등하게 할당하도록 고안되었다. 즉, 이 알고리즘은 어떠한 프로세스도 영구적으로 필요 자원이 부족하지 않도록 자원을 할당하는 방식이다.

 

Remaining 시간이 같다면?

FIFO를 사용할 수 있습니다. 이런 additional한 설정이 필요합니다.

 

SJF 선점형 스케쥴링은 FCFS보다 문맥교환이 더 발생하는가?

Yes, 하지만 일반적으로 문맥교환 시간은 작다고 간주합니다. 물론 아주 extreme하게 time quantum이 작으면 문제가 될 수 있죠.(ISR도 DOS 공격이 되긴 할겁니다.) 그래서 스케쥴러와 chip design할 때 이런 overhead를 치명적이지 않게 만듭니다. State save나 이동같은 경우 하드웨어적으로 1step만에 처리되도록하는 명령어를 사용하는 방식이죠. 사용자들이 프로세스를 진행시키지 못하는 것은 bug이고 이런 커널의 bug를 방지하는 것도 하나의 연구 topic입니다.(이런 bug를 쓰레싱이라 합니다.) 결국 FCFS의 문제는 배치였는데요. 이를 바탕으로 Priority를 생각하게 됩니다.

 

쓰레싱

과도한 페이징 작업. 다중 프로그래밍 정도가 높아짐에 따라 CPU 이용률이 높아진다. CPU이용률이 최대값에 도달 하였을때, 다중 프로그래밍의 정도가 그 이상으로 더 커지면 쓰레싱이 일어나게 되고 CPU 이용률은 급격히 떨어진다. 이는 locality를 이용한 교환 알고리즘, 우선순위 교환 알고리즘을 사용하거나 각 프로세스가 필요로 하는 최소한의 프레임 개수를 보장함으로써 방지할 수 있습니다.

 

사실 SJF스케쥴링은 low bound를 제시해준다는 점에서 의미가 있을 수 있습니다. burst time을 알 수 없더라도 어떠한 스케쥴러를 만들 때 best가 어디인지 즉, 이 이상은 못한다는 것을 제시해준다는 거죠. 어떤 문제를 풀 때 최선이 어디까지인지를 알고 모르고는 상당한 차이입니다.

 

 

22.02.1. Proof

SJF is a scheduling algorithm that assigns to each process the length of its next CPU burst/execution time. CPU is then given to the process with the minimal CPU burst from the waiting queue. SJF is provably optimal, in that for a given set of processes and their CPU bursts/execution times it gives the least average waiting time for each process. The average waiting time for a process is defined by:

The main drawback of the SJF alogrithm is that, of course, in modern operating system enviroments we cannot precisely determine the length of the process' next CPU burst. We can at best approximate it, and that only by a certain degree and in certain conditions.

 

22.02.2. CPU Burst prediction

이전 CPU Burst 길이를 사용하여 다음 CPU Burst 길이를 예측합니다. 이때 다음 Burst 길이는 이전의 값과 비슷할 것이라고 가정합니다. Exponential average를 사용하는데 다음 예측값은 이전 예측값과 이전 CPU Burst의 지수 평균입니다.

이때 초기값이 t_0는 상수 또는 전체 평균으로 정의합니다. 

결과론적으로는 FCFS와 SJF 스케쥴링 모두 computer에 적합하지 않습니다. 다음에 살펴볼 우선순위 스케쥴링이 실제로 사용하는 알고리즘입니다.

 

22.03. Priority Scheduling

Priority Scheduling은 말 그대로 우선순위에 따라 CPU를 할당합니다. 문제는 낮은 우선순위를 가진 프로세스을 전혀 수행하지 않는 starvation이 발생할 수 있다는 것입니다. 이를 해결하는 방법은 의외로 간단합니다. 계속 기다리는 것이 문제이니 기다리는 시간에 따라 프로세스의 우선순위를 증가시켜주어 해결할 수 있습니다. 이를 Aging 기법이라고 합니다. 잠깐 짚고넘어가자면 이 우선순위는 PCB에 저장할 수 있습니다.(PCB에 대해 포스팅을 하였으니 참고해주시면 감사하겠습니다.)

The process priority, pointers to scheduling queues etc. is the CPU scheduling information that is contained in the PCB. This may also include any other scheduling parameters.

 

우선순위 스케쥴링에서 우선순위는 시간 제한, 메모리 요구, 프로세스 중요도, cost 등에 따라 책정할 수 있고 SJF 스케쥴링은 다음 CPU burst time의 예측값을 우선순위로 하는 우선순위 스케쥴링의 special case라고 할 수 있습니다.

 

22.04. Round Robin Scheduling(RR Scheduling)

Round Robin 스케쥴링은 그 자체가 선점형 스케쥴링입니다. Time quantum으로 CPU를 할당하는 방식으로 시간단위만큼을 수행한 프로세스는 Ready queue의 끝으로 재배치되어 다시 할당을 기다립니다.(Timer interrupt 사용) 하나의 Case를 보자면

Process	P1	P2	P3	P4
Burst Time	53	17	68	24

0 ~ 20	20 ~ 37	37 ~ 57	57 ~ 77	77 ~ 97	97 ~ 117	117 ~ 121	121 ~ 134	...
P1	P2	P3	P4	P1	P3	P4	P1

순으로 실행됩니다.(Arrival time은 그닥 중요하지 않습니다. 그냥 Quantum만큼 쪼개서 계속 시행하면 됩니다.) 사실 익숙한 case입니다. 보통 time sharing이라고 이야기하면 round robin방식으로 동작하는 것을 의미합니다.

 

Arrival time이 왜 중요하지 않을까요?

fork()와 스케쥴러는 별도입니다. 즉, 스케쥴러는 fork라는 semantics를 알려고 하지 않습니다. 물론 control group(C group)을 만들어 프로세스를 묶어 처리하기도 합니다만 기본적으로 프로세스가 도착 또는 만들어지는 이슈와 스케쥴링 이슈는 별도의 이슈입니다.(이전 포스팅에서도 말씀 드렸다시피 복잡한 시스템을 모델링할 때 각 모듈이 할 일은 정확히 구분해놓아야 합니다. 각각의 이슈와는 독립적으로 동작하지 않게하는 것은 아주 중요합니다. 하나의 component가 다른 component의 결정을 하지 않는 것이죠,)

 

 

RR 스케쥴링은 response time이 짧습니다. 평균적으로 (n - 1) * QT / 2의 시간을 가지게 되죠. 따라서 interactive 시스템에 유리합니다. 또한 각 프로세스의 다음 Time quantum이 돌아오기까지의 대기시간은 최대 (n - 1) * QT이라는 것도 예측가능성 측면에서 장점입니다. n만 주어지면 bound가 정해지기 때문입니다. 다만 QT가 클 경우 FCFS 시케쥴링과 유사하게 동작하고 너무 작으면 문맥전환에 필요한 시간이 있기 때문에 효율이 낮아질 수 있습니다. 그래서 QT를 전체 CPU burst time의 약 80% 정도가 quantum time보다 짧도록 설정합니다. 그렇다면 time sharing을 이야기할 때도 한번 생각해보았듯이 Queue의 size에 따라 time quantum을 바꾸면 어떨까요?

Time quantum의 duration을 최적화해보면 어떨까라는 생각을 하셨다면 아주 훌륭합니다. 실제 Linux의 CFS 스케쥴러는 time quantum을 queue의 size에 따라 adaptive하게 변경합니다. 이것을 바꿔서 일정한 response time을 제공해줄 수 있다는 것은 굉장히 좋은 insight, idea입니다. 결국 response time의 편차를 크게 하는 것은 좋지 않아 어느정도 OS가 control하면 좋겠다는 생각까지 미친다면 더 금상첨화겠군요.

 

최종적으로 SJF 스케쥴링과 비교하자면 turnaround time은 더 크지만 response time은 짧습니다.(참고로 time quantum duration이 증가함에 따라 평균 총 처리시간이 반드시 개선되는 것은 아닙니다.)

 

 

22.05. Multilevel Queue Scheduling

Multilevel Queue 스케쥴링은 priority 스케쥴링과 관련이 있습니다. 우선순위를 구현하는 여러가지 방법이 존재하는데요. 그 중 하나가 ready queue를 여러개 만들어 각각에 대해 다른 우선순위와 스케쥴링 알고리즘을 사용하는 기법입니다. Foreground queue와 Background queue로 나누어 foreground queue에는 응답시간이 중요한 프로세스를 동작시키기 위해 Round Robin 스케쥴링을 적용하고 background queue에는 CPU 연산 job이 많은 프로세스를 수행시키기 위해 FCFS 스케쥴링을 적용할 수 있습니다. 이때 foreground를 먼저 실행하고 background를 실행하는 거죠. 다만 이런 방식은 상위 queue에 프로세스가 계속 존재한다면 하위 queue에 starvation이 발생한다는 문제점이 있습니다.

 

또다른 Case로는 Kernel 프로세스(init process)와 Normal 프로세스, Batch 프로세스(굉장히 오래 돌아가는 프로세스 예를 들면 Bank 시스템에서 거래정지시간에 거래를 정리하는 프로세스가 있습니다.) 전용 queue를 나눌 수도 있습니다. 

 

그렇다면 starvation을 해결해볼까요?

문제는 우선순위가 낮은 queue의 프로세스가 실행되지 않을 수도 있다는 것이였습니다. 그럼 우선순위가 낮은 queue에 있는 프로세스가 다른 queue로 이동할 수 있도록 하면 됩니다. Aging의 한 방법이죠. 이제 우리는 queue의 수와 각 queue의 스케쥴링 기법, queue에서 프로세스가 이동 point를 설정하면 됩니다.(Design choices)

 

참고자료에 아주 좋은 예시가 있어 가져와 보았습니다. Q0와 Q1은 Timequantum이 다르고 어떤 프로세스가 CPU를 많이 사용하면 downgrade합니다.(물론 적게 사용하면 Aging하여 priority를 상승시킬 수도 있습니다.)  

만약 새로운 프로세스가 들어온다면 Q0에서 실행하고 여기서 종료되지 않으면 Q1으로 이동해 16 QT만큼 실행하고 여기서도 종료되지 못하면 Q2로 이동해 FCFS로 수행되는 방식입니다. 즉 생성되고 24 QT동안 종료되지 않은 프로세스는 CPU를 많이 사용한다고 간주하고 FCFS기법을 사용해 충분한 CPU 자원을 할당해줄 수 있습니다. 물론 이렇게 Q2로 이동한 프로세스는 Q0와 Q1이 비어있을 때 CPU 자원을 할당받습니다.

 

 

22.06. Scheduling Algorithm Evaluation

특정 시스템을 위한 알고리즘을 선택하는 방법은 앞서 말씀드린 여러가지 선택 기준들 중 시스템에 맞는 기준에 가중치를 두어 평가하는 것입니다. 평가방법에는 Deteministic model과 같이 미리 정의된 부하를 사용하여 측정하거나 Queueing model과 같이 부하를 확률 분포로 분석하여 Queueing network의 수학적 분석을 활용할 수도 있습니다. 또는 시스템 모델을 프로그래밍하는 작업을 포함하여 시뮬레이션해볼 수도 있는데 random number generator가 예가 될 수 있습니다. 

 

 

 

이번시간에는 여러 스케쥴링 알고리즘을 알아보았습니다. 많은 창의적인 idea가 나올 수 있는 topic인 것 같습니다. 질문과 오류지적은 언제든 환영합니다. 댓글로 남겨주시면 감사하겠습니다. 다음 포스팅에서는 multicore 스케쥴링 방식과 Linux 스케쥴링(CFS)에 대해 알아볼 것입니다.

 

 

Reference

Proof of SJF : Andrej Blagojevic, Computer Science and Engineering student, School of Electrical Engineering, University of Belgrade, Serbia.