호야의 블로그
들어가며
long-term 스케줄러: new->ready 사이
midium-term 스케줄러: swap에 관여
short-term 스케줄러: CPU 스케줄링, ready -> run (CPU에서 동작해서 속도가 제일 빠르다)
이중에서도 short-term 스케줄러에 해당하는 CPU 스케줄링 알고리즘에 대해 알아보도록 하겠습니다.
평가기준(performance criteria)
CPU 스케줄링을 평가하는 기준이 있습니다. CPU에 동작시간이나, 사용량, 응답시간 등 아래와 같은 다양한 평가기준이 존재하죠.
CPU utilization(사용량) = running time(CPU 동작시간)/running time + idle time(전체 동작시간)
thru-put: 단위시간 당 처리한 프로세스 수 = process의 갯수/총 시간
response time: 일을 시작해서 결과가 다 나올 때까지 시간(응답시간) 대기시간 포함
mean response time = Σresponse time(총 응답시간)/process의 갯수
waiting time: 레디 큐에서 소비한 시간
turn around time = 종료시간 – 도착시간 -> I/O까지 고려한 시간
이러한 기준들은 다양한 상황에 맞게 효율적으로 스케줄링을 하는데 목적이 있습니다. 최대한 WT(waiting time)를 줄이고, RT(response time)을 줄여 더 빠르게 응답할 수 있도록 해야하므로 이러한 평가기준은 필수적이라 볼 수 있습니다.
이외에도 우선순위, 유저 레벨 등 다양한 평가기준이 있습니다.
FCFS(first come first service;FIFO)
선입선출이라고 불리는 가장 기본적이고 단순한 스케줄링 방법입니다.CPU 요청, 즉 AT(arrival time)이 가장 빠른 순으로 처리하는 것입니다. 먼저 사용신청을 한 프로세스부터 차례로 CPU를 할당하는 것이죠. 동작 중간에 다른 프로세스가 침입할 수 없어 비선점(non-preemptive) 스케줄링입니다.
Process |
AT(arrival time) | BT(burst time) |
P1 |
0 | 1 |
P2 |
1 | 5 |
P3 |
3 | 2 |
위 표와 같이 프로세스 3개가 사용을 신청합니다. AT가 0일 때 P1이 도착했습니다. BT동안 작업을 하고, AT = 1 일때 P2가 도착하여 BT = 5 만큼 작업합니다. 이후 마찬가지로 P3가 3에 도착하여 2만큼 동작합니다.
스루-풋을 구하려면 총시간 8, 프로세스 3개를 알고, 3/8 = 0.375 임을 알 수 있습니다. 그리고 프로세스의 TAT(turn--around time=WT+BT)는 P1, P2, P3 각각 1, 5, 5입니다. P3는 WT 3 + BT 2를 더해 TAT가 5 인 것입니다.(다른 방법은 도착시간 8 - 출발시간 3으로 구할 수 있습니다) 이때 평균 TAT는 11/3 = 3.67입니다.
만약 아래와 같이 너무 BT가 긴 프로세스가 들어올 경우 Convoy effect 현상이 발생합니다. Convoy effect란 긴 프로세스가 큐에 할당되어 있어서 끝날 때까지 뒤의 프로세스가 오래 대기해야 하는 현상입니다. 이러한 문제는 비선점 알고리즘에서 많이 나타나는 문제 중 하나입니다.
Process | AT(arrival time) | BT(burst time) |
P1 | 0 | 1 |
P2 | 1 | 99 |
P3 | 3 | 2 |
SJF(shortest job first)
최단 작업 우선 스케줄링은 평균대기 시간을 최소화하기 위해 CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식의 CPU 스케줄링 알고리즘으로 평균 대기시간을 최소로 만드는 걸 최적으로 두고 있는 알고리즘입니다. 요구 시간이 긴 프로세스가 요구 시간이 짧은 프로세스에 항상 양보 되어 기아 상태가 발생할 수 있으며, 대기 상태에 있는 프로세스의 요구시간에 대한 정확한 자료를 얻기 어렵다는 문제점이 있습니다. 단기 스케줄링보다는 장기 스케줄링에 유리하며 이 알고리즘은 비선점형와 선점형 모두에 적용될 수 있는데, 선점형에 적용되는 SJF 스케줄링을 특별히 SRTF 스케줄링이라 합니다.
Process | AT(arrival time) | BT(burst time) |
P1 | 0 | 4 |
P2 | 1 | 5 |
P3 | 3 | 2 |
위 표와 같이 프로세스 3개가 사용을 신청합니다. 기본적으로 FCFS를 원칙으로 따르나 동작이 끝난 이후 도착한 프로세스들 중에서 BT가 짧을 것으로 예상되는 프로세스를 우선 실행합니다. 위 표에서는 P1 작업이 끝난 이후 P2와 P3가 대기중인데 이때 늦게 도착했음에도 P3가 BT가 짧아서 우선 실행되는 것입니다.
프로세스의 TAT(turn--around time=WT+BT)는 P1, P2, P3 각각 4, 10, 3입니다. 평균 TAT는 17/3 = 5.67 입니다. 같은 상황에서 FCFS를 적용한다면 TAT 각각 4, 8, 8이며, 평균 TAT는 20/3 = 6.67 입니다. 이를 통해 상황에따라 총 걸리는 시간이 달라진다는 것을 알았고, 더 효율적인 알고리즘을 찾는 것이 중요할 것입니다.
하지만 SJF의 문제는 기아현상(starvation)입니다. 기아현상은 프로세스 처리 중에 계속 짧은 프로세스가 들어오면 긴 프로세스는 계속 서비스를 못 받는 현상입니다.
Process | AT(arrival time) | BT(burst time) |
P1 | 0 | 3 |
P2 | 1 | 99 |
P3 | 2 | 1 |
P4 | 2.5 | 2 |
P5 | 4 | 5 |
P6 | 5 | 4 |
P7 | 6 | 9 |
<Starvation 현상>
예를들어 위같은 상황에선 P1이 작업하는 동안 P2, P3, P4가 대기중인데 가장 BT가 낮은 P3가 우선순위를 갖습니다. P2의 우선순위는 먼저 도착했음에도 무한히 뒤로 밀려 서비스를 받지 못하는 상황을 기아현상이라고 합니다.
이를 해결하기 위한 대책으로 에이징(Aging) 방법을 이용합니다. 에이징은 레디 큐에 있는 나이가 많은(오래 된) 프로세스에게 우선권을 주는 정책입니다. 이 방법으로 너무 오래된 P2와 같은 프로세스를 강제로 작업할 수 있도록 해줍니다.
SJF with preemptive(SRT; shortest remaining Time First)
SRT란 매시간 대기 중인 프로세스의 BT를 계산하여 짧은 프로세스부터 우선 처리하는 스케줄링 알고리즘입니다. 비교 후 강제로 프로세스를 대기시키고, 동작시켜 선점형(Preemptive) 방식입니다. 계속 비교하기 위해 정보를 항상 유지하고 있어야해서 부하가 올 수 있는 단점이 있습니다. 만약 남은 BT가 같은 프로세스가 있다면 FCFS를 따릅니다.
Process | AT(arrival time) | BT(burst time) |
P1 | 0 | 1 |
P2 | 1 | 5 |
P3 | 3 | 2 |
위 표와 같이 프로세스 3개가 사용을 신청합니다. AT가 0일 때 P1이 도착했습니다. 1의 작업을 마치니 P2가 도착했습니다. P1이 작업을 마치고 P2가 작업을 2만큼 진행한 후 AT가 3이 된 순간 P3가 도착했습니다. 남은 시간을 비교하니 P2 남은시간 = 3, P3 남은시간 = 2 입니다. 이때 Preemptive하게 P2는 대기상태, P3는 running 상태가 되어 작업을 시작합니다. P3가 작업을 마치면 P2가 나머지 작업을 한 후 종료되는 알고리즘입니다.
프로세스의 TAT(turn--around time=WT+BT)는 P1, P2, P3 각각 1, 7, 2이며 평균 TAT는 10/3 = 3.33 입니다.
HRN(highest Response ratio Next)
Process | WT(waiting time) | BT(burst time) | DP(Dynamic Priority) | 우선순위 |
P1 | 0 | 3 | 1 | 7순위 |
P2 | 1 | 10 | 1.1 | 6순위 |
P3 | 3 | 1 | 4 | 1순위 |
P4 | 6 | 8 | 1.75 | 4순위 |
P5 | 4 | 5 | 1.8 | 3순위 |
P6 | 2 | 4 | 1.5 | 5순위 |
P7 | 10 | 9 | 2.11 | 2순위 |
위와 같이 같은 시간에 도착했을 때 7가지 프로세스는 각각의 동적 우선순위 DP가 주어집니다. WT와 BT로 매시간 계산하여 DP가 높은 순서대로 우선순위가 책정되며 동작하게 됩니다. 위 상황에선 우선순위가 가장 높은 P3가 다음 동작을 하게 됩니다.
RR(Round-Robin Scheduling)
Process | AT(arrival time) | BT(burst time) |
P1 | 0 | 3 |
P2 | 1 | 5 |
P3 | 3 | 2 |
P4 | 4 | 7 |
<RR 퀀텀이 1인 경우>
위 그림은 퀀텀이 1인 경우 1 time마다 대기와 동작을 선점형으로 스케줄링하는 모습입니다. 먼저 들어온 순서대로 1퀀텀씩 동작을 하며 각 TAT는 7, 12, 6, 13으로 평균 TAT는 9.5입니다. WT은 각각 4, 7, 4, 6이며 평균 WT은 5.25입니다.
<RR 퀀텀이 2인 경우>
위 그림은 퀀텀이 2인 경우 2 time마다 대기와 동작을 선점하는 모습입니다. 각 TAT는 9, 13, 3, 13이며 평균 TAT는 9.5로 퀀텀 1인 경우와 같습니다. WT은 각각 6, 8, 1, 6이며 평균 WT은 5.25입니다. 이는 퀀텀이 1인 경우와 차이가 없는 같은 수치입니다.
위 그림은 퀀텀이 3인 경우 3 time마다 대기와 동작을 선점하는 모습입니다. 각 TAT는 3, 12, 5, 13이며 평균 TAT는 8.25로 퀀텀 1인 경우와 같습니다. WT은 각각 0, 7, 3, 6이며 평균 WT은 4입니다. 이 수치는 퀀텀이 1, 2인 경우보다 대기시간이 1 time 이상으로 많이 줄었고, 전체 소요시간 또한 1 time 이상 줄었습니다. 이러한 결과를 통해 각각의 상황에 맞는 알고리즘으로 최적의 효율을 찾아야 한다는 것을 알 수 있습니다.
Multi Queue Scheduling
이 외에 Multilevel Feedback Queue Scheduling 다단계 피드백 큐 스케줄링은 다단계 큐 스케줄링에서 한 단계 발전된 방식입니다. 단계 큐 스케줄링에서는 프로세스가 하나의 큐에 영구적으로 할당되었지만, 다단계 피드백 큐 스케줄링에서는 프로세스들이 큐를 갈아탈 수 있도록 했습니다. 그리고 작업들이 서로 다른 유형의 작업들로 분류될 경우 사용됩니다.
후기 및 정리
이상 간단하게 CPU 스케줄러에 대해 알아보았습니다. 약간 어려울 수도 있지만 차근차근 해보시면 잘 하실거라 생각합니다. 다음 시간은 C로 직접 스케줄러를 구현해보도록 하겠습니다. 감사합니다.
OS 7번째 글: 2018/10/26 - [IT/OS] - [OS] 운영체제 3차 정리 - Memory Management (2)
OS 6번째 글: 2018/10/26 - [IT/OS] - [OS] 운영체제 3차 정리 - Memory Management (1)
OS 5번째 글: 2018/10/26 - [IT/OS] - [OS] 운영체제 2차 정리 - 데드락(Deadlock)
OS 4번째 글: 2018/10/26 - [IT/OS] - [OS] 운영체제 1차 정리 - Scheduling
OS 3번째 글: 2018/10/24 - [IT/OS] - [OS] CPU 스케줄러
OS 2번째 글: 2018/10/24 - [IT/OS] - [OS] 진짜 간단히 정리한 프로세스 개념
OS 1번째 글: 2018/10/18 - [IT/OS] - [OS] 운영체제에 대해서
조금의 도움이 되셨다면 로그인 없이도 가능한 댓글과
왼쪽 아래 ♥공감 버튼을 꾹 눌러주세요!
'IT > OS' 카테고리의 다른 글
| 운영체제 3차 정리 - Memory Management (1) (0) | 2018.10.26 |
|---|---|
| 운영체제 2차 정리 - 데드락(Deadlock) (0) | 2018.10.26 |
| 운영체제 1차 정리 - 스케줄링 (1) | 2018.10.26 |
| 진짜 간단히 정리한 OS 프로세스 개념 (2) | 2018.10.24 |
| 운영체제에 대해서 (0) | 2018.10.18 |