2026. 11. 18. 20:25ㆍComputer Science/Operating System

쨋든 CPU는 분신술을 써서 프로세스를 처리하는 관계로 Scheduling이 필수적이라고 할 수 있겠는데, 이러한 Scheduling을 관장하는 알고리즘은 상당히 다양하다. 물론 멀티코어로 가면 머리가 깨지는 관계로 싱글 코어 기준으로 설명하자.
참고로 Scheduling의 기준으로는 아래를 들 수 있으니 참고하자.
- CPU Utilization : CPU를 최대한 굴려먹어야 성능이 좋을거 아닌가?
- Throughput(처리량) : 당연히 CPU를 열심히 노예처럼 굴려 먹어서 처리량이 많아야 좋을 것 아닌가?
- Turnaround Time(반환 시간) : 프로세스가 종결 되기 까지의 시간, 다시 말해서 레디 큐에서 잡아먹은 시간 + CPU에서 실행되는 시간 + I/O 시간.
- Waiting Time : 레디큐에서 잡아먹은 시간. 참고로 프로세스가 레디큐로 도로아미타불 될 수 있으니 유의.
- Response Time : 프로세스가 CPU를 할당 받을때 까지 걸린 시간.
FCFS : First-Come, First-Served

가장 심플한 Non-preemptive CPU 알고리즘으로, 먼저 선빵치는놈을 먼저 처리하는 FCFS 알고리즘이 있겠다. 진짜 말그대로 선빵필승이라(First-Come, First-Served) 이러한 순서를 관리할때는 FIFO 자료형인 Queue를 사용하면 쉽사리 끝난다. 표기는 Gantt Chart를 이용하면 아주 손쉽게 처리할 수 있다.
물론 가장 단순한 만큼 상당한 단점을 가지고 있는데.. 바로 대기 시간이 꽤 길다는 점이다. 예를 들어서 위에서 1번째 프로세스의 처리시간을 0ms, 2번째를 24ms, 3번째를 27ms라 해보자. 그럼 평균적으로 17ms 대기를 타야하는것 아니겠는가? 반면 2->3->1번 순서로 프로세스를 처리하면 평균 3ms를 기다려야 하니, 쨋든 평균 대기 시간이 늘어지는 문제점이 발생한다. 특히 프로세스가 CPU-Bound라면 더더욱! 이렇게 큰 프로세스가 시간을 다 잡아 먹는 것을 Convoy Effect라고 하게 된다.
SJF : Shortest-Job-First (Shortest-next-CPU-burst)

SJF 알고리즘은, CPU가 사용 가능하면 최대한 작업량이 적은(==CPU Burst Time이 작은) 작업을 선택하게 되는 알고리즘이다. (선점/비선점 두가지 종류가 있음) 만약 Burst Time이 같다면 FIFO의 것을 그대로 따라가게 된다.
SJF 알고리즘은 통상적으로는 프로세스에게 가장 짧은 대기시작을 제공한다. 상식적으로 짧은거 먼저 처리해야 대기시간이 줄어들거 아닌가? 다만 다음 CPU Burst의 길이를 알 수가 없을 것이기에 CPU Sheduling에서 실행 될 수가 없을 뿐이지. 뭐야 그럼 왜있는데라고 생각할 수 있을텐데.. 예측은 할 수 있으므로 SJF의 존재 의의가 있다.
일반적으로 다음 CPU Burst는 이전 CPU burst들의 지수적 평균으로 예측되곤 한다. t_n을 nth CPU Burst라고 하고, 타우_n+1을 예측값이라 하면...

여기서 알파값은 이전 값을 얼마나 반영할 지가 되시겠다. 통상적으로는 1/2를 사용하는 편이고, 따라서 이전 예측샷이랑 최근 예측샷이 동일한 비율로 반영된다. (Initial Value는 상수거나 전체 시스템 평균으로 하는 편임)
RR : Round-Robin

RR 알고리즘은 사실 문득 보기에는 FCFS랑 비슷한데... 선점이 허용된다. 이는 시간을 Slice 쳐서(통칭 Time quantum or Time Slice라고 부름) 가능하다. 또한 ready queue가 순환하게 된다.
쨋든 스케쥴러의 입장에서 생각해보자. 스케쥴러는 ready queue에서 한가지 프로세스를 골라, 1 슬라이스 만큼 dispatch 때린다. 그리고 만약에 프로세스가 추후 CPU Burst를 1 Time slice보다 작게 먹는다? 바로 프로세스를 내려 버리고 레디큐 끝으로 쳐박아 버린다. 그리고 다시 레디큐에서 하나를 뽑아오게 된다. 그리고 예상 할 수 있다 싶이, RR의 성능은 time slice의 크기에 따라 달라지게 된다. 만약 Time slice가 겁나게 크면 사실상 FCFS랑 다를 바가 없을 것이며... 너무 time slice가 작다면 context switching이 과도하게 발생할 것이다. (통상적으로는 Context Switching에 있어서 10ms 언더로 걸리기에, Time slice를 10~100ms로 잡는 편이다. 그리고 이는 Turnaround Time에도 영향을 미치게 된다.)
어.. 물론 RR 하에서 평균 대기시간은 종종 늘어질 수 있다. 아무래도 돌아가는 프로세스가 한개가 아닌 이상, 슬라이스 마다 둥글게 둥글게 Time Slice를 배정해 주기 때문. 고로 RR은 Preemtive 하다고 할 수 있겠다.
Priority Scheduling

어쩌면 SJF 알고리즘의 일반적인 경우라고 할 수 있겠다. 각각의 프로세스에 우선 순위를 집어넣고, 우선순위가 가장 높은 친구에게 할당해 주기 때문. (SJF의 경우에는 순위를 시간이 얼마나 짧은가? 로 정해둔 것이 되겠다.) 참고로 우선순위가 같다면 FCFS 마냥 작동하게 된다.
참고로 우선순위가 높냐 낮느냐는 일반적으로 숫자로 표현이 된다. 물론 0이 높은걸 의미하는지 낮은걸 의미하는지는 시스템 마음이라고 할 수 있겠다. 그리고 우선 순위는 양적으로 측정할 수 있는 것이라면 외부적 요인이던 내부적 요인이던 상관 없기는 하다. 뭐 예를 들면 시간 제한이라던가, 메모리 요구량이라던가, 앞으로 깔 파일의 양이라던가..
그리고 Priority Scheduling은 선점적이던 비선점적이던 둘 중 하나가 될 수 있다. 만약 선점이라면 레디큐에 프로세스가 하나 도착하면 우선순위를 따져 현재 실행 중인 프로세스가 유배를 가던 할것이다. 비선점 적인 경우에는 새 프로세스도 가차없이 레디큐에 쳐박을 것인다.
다만 Priority Scheduling 알고리즘에는 indefinit blocking 또는 starvation이라는 최악의 문제점이 존재한다. 쉽게 말해서 프로세서의 우선순위가 후순위라면 어쩌면 하아아아안참동안 레디큐에 쳐박혀서 CPU 자원을 배분받을 수 없을지도 모르는 일이다. 늦게 실행되면 다행이고, 최악의 경우에는 크래시가 터져서 뻗을 수도 있다..
그래서 Aging이라고 불리는 솔루션이 존재하게 된다. 쉽게 말해서 오랫동안 기다리면 기다릴수록 우선 순위를 올려주는 개념인 셈. 아니면 위에서 언급한 RR이랑 짬뽕시킬 수도 있겠다.
Multilevel Queue

근데 가만 생각해보면은, Priority+RR 방식에서는 큐를 하나만 쓰지 않았는가. 그러면 Queue를 돌때마다 시간 복잡도가 O(n)이 될테고.. 음.. 경우에 따라서는 거시기하고 거시기 할 수 있겠다.
그래서 Multilevel Queue 방식의 경우에는 Prioriy별로 Queue를 나눠버린다! 그리고 나서 RR마냥 돌려버린다... 쨋든 이런 식으로 하면 Foreground/Background 마냥 프로세스를 나눠서 적당히 잘 처리할 수도 있을 것이다. 일반적으로는 우선 순위를 아래와 같이 잡는 편이긴 하다.
- Real-time Processes
- System Processes
- Interactive Processes
- Batch Processes
Multilevel Feedback Queue

어.. 근데 Multilevel Feedback의 경우 여전히 Starvation 문제가 발생 할 수 있을 것이다. 그래서 Multilevel Feedback Queue 알고리즘의 경우 프로세스가 큐들 사이를 오갈 수 있게 해준다. 만약에 사용 시간을 초과했다면 (==CPU Bursts가 너무 길다면) 아래로 유배보내 버리고, 너무 Age가 많다면 위로 올리는 식인 셈.
이때 생각해야 할 정책들은 다음과 같다.
- Queue의 갯수
- 각각의 큐에 대한 스케쥴링 알고리즘
- 어쩔때 위로 올릴지에 대한 방법
- 어쩔때 아래로 유배보내 버릴지에 대한 방법
- 프로세스를 어느 큐로 보내버릴지에 대한 방법
'Computer Science > Operating System' 카테고리의 다른 글
| Thread Strategy (0) | 2026.11.18 |
|---|---|
| About Process (2) : Process Scheduling (0) | 2026.11.12 |
| About Process (1) : Memory, and State (0) | 2026.11.12 |
| System Calls (0) | 2026.11.04 |