[OS] 3. CPU 스케줄링 (CPU Scheduling)
CPU 스케줄링 (CPU Scheduling) : CPU 스케줄러에서 어느 프로세스를 다음에 실행할지 지정
CPU 스케줄링은 CPU 스케줄러에서 어느 프로세스를 다음에 실행할지 지정하는 작업이다. CPU 스케줄링에는 선점(Preemptive)과 비선점(Non-Preemptive) 방식이 있다. 선점 방식에서는 한 프로세스가 CPU를 점유하는 동안, 다른 프로세스가 CPU를 강제로 점유할 수 있다. 반면 비선점 방식에서는 한 프로세스가 CPU를 점유하는 동안, 다른 프로세스가 CPU를 점유할 수 없으며, 예외적으로 I/O가 발생할 경우에만 점유가 변경된다.
CPU 스케줄링 척도 (CPU Scheduling Criteria)
CPU 스케줄링의 효율을 분석하는 기준에는 여러 가지가 있다. CPU 점유율(CPU Utilization)은 현재 CPU가 작업을 수행하는 비율로, 이 비율이 높을수록 좋다. 처리율(Throughput)은 단위 시간 당 완료되는 프로세스의 개수를 의미하며, 많을수록 좋다. 소요 시간(Turnaround Time)은 프로세스가 생성된 시간부터 종료되는 데까지 걸린 시간으로, 짧을수록 좋다. 대기 시간(Waiting Time)은 CPU 제어를 위해 Ready Queue에서만 대기한 시간으로, 이 시간도 짧을수록 좋다. 평균 대기 시간(Average Waiting Time)은 각 프로세스들의 대기 시간의 합을 프로세스들의 개수로 나눈 값이다. 응답 시간(Response Time)은 Interactive System에서 입력에 대한 반응 시간을 의미하며, 짧을수록 좋다.
선입선출 (First-Come, First-Served) 스케줄링
선입선출 스케줄링은 가장 먼저 작업을 요청한 프로세스를 먼저 수행하는 비선점(Non-Preemptive) 방식이다. 그러나 들어온 순서대로 작업을 수행한다고 해도 그것이 반드시 효율적이지는 않다. CPU를 많이 점유하는 프로세스가 먼저 수행되면 나머지 프로세스들이 오래 대기하는 Convoy Effect가 발생할 수 있다.
| Process | Burst Time (msec) |
|---|---|
| P1 | 3 |
| P2 | 3 |
| P3 | 24 |
예를 들어, FCFS 스케줄링에서 CPU에 요청받은 순서대로 P1, P2, P3 순으로 처리한다면 Average Waiting Time은 (0 + 3 + 6) / 3 = 3msec이다. 반면에 다음과 같은 경우를 보자.
| Process | Burst Time (msec) |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
이 경우, FCFS 스케줄링에서 CPU에 요청받은 순서대로 P1, P2, P3 순으로 처리한다면 Average Waiting Time은 (0 + 24 + 27) / 3 = 17msec이 된다. 이와 같이 CPU를 오래 점유하는 P3로 인해 상대적으로 빠른 처리가 가능한 P1과 P2가 오래 대기하는 Convoy Effect가 발생한다.
최단작업 (Shortest-Job-First) 스케줄링
최단작업 스케줄링은 시간이 가장 짧게 수행되는 프로세스를 먼저 수행한다. 이는 비선점(Non-Preemptive)과 선점(Preemptive) 방식 모두 사용될 수 있다. 일반적으로 가장 빠른 평균 대기 시간을 가지나, 각 프로세스의 CPU 점유 시간이 주어지지 않아 비현실적이다.
| Process | Burst Time (msec) |
|---|---|
| P1 | 6 |
| P2 | 8 |
| P3 | 7 |
| P4 | 3 |
예를 들어, FCFS 스케줄링에서 CPU에 요청받은 순서대로 P1, P2, P3, P4 순으로 처리한다면 Average Waiting Time은 (0 + 6 + 14 + 21) / 4 = 10.25msec이다. 반면, SJF 스케줄링에서 작업 시간이 짧은 순서대로 P4, P1, P3, P2 순으로 처리한다면 Average Waiting Time은 (0 + 3 + 9 + 16) / 4 = 7msec이 된다.
우선순위 (Priority) 스케줄링
우선순위 스케줄링은 우선순위가 가장 높은 프로세스를 먼저 수행하는 방식이다. 이는 비선점(Non-Preemptive)과 선점(Preemptive) 방식 모두 사용될 수 있다. 우선순위는 정수값으로 표현되며, 값이 작을수록 우선순위가 높다.
| Process | Burst Time (msec) | Priority |
|---|---|---|
| P1 | 10 | 3 |
| P2 | 1 | 1 |
| P3 | 2 | 4 |
| P4 | 1 | 5 |
| P5 | 5 | 2 |
예를 들어, Priority 스케줄링에서 우선순위가 높은 순서대로 P2, P5, P1, P3, P4 순으로 처리한다면 Average Waiting Time은 (0 + 1 + 6 + 16 + 18) / 5 = 8.2msec이 된다.
라운드 로빈 (Round-Robin) 스케줄링
라운드 로빈 스케줄링은 원 모양으로 모든 프로세스를 돌아가면서 수행하는 선점(Preemptive) 방식이다. 시분할 시스템에서 CPU가 한 프로세스를 일정 시간(Time Quantum) 수행한 뒤 대기 상태로 보내고, 다음 프로세스를 수행하는 것을 반복한다. Time Quantum은 CPU가 한 프로세스를 수행하는 시간으로, 스케줄링의 효율성이 Time Quantum의 크기에 의존한다.
| Process | Burst Time (msec) | Time Quantum |
|---|---|---|
| P1 | 7 | 4msec |
| P2 | 4 | 4msec |
| P3 | 4 | 4msec |
예를 들어, Round-Robin 스케줄링에서 CPU에 요청받은 순서대로 P1, P2, P3, 그리고 완료하지 못한 P1 순으로 처리한다면 Average Waiting Time은 (4 + 8 + 12) / 3 = 8msec이 된다.
| Process | Burst Time (msec) | Time Quantum |
|---|---|---|
| P1 | 7 | 3msec |
| P2 | 4 | 3msec |
| P3 | 4 | 3msec |
또한, Round-Robin 스케줄링에서 CPU에 요청받은 순서대로 P1, P2, P3, 완료하지 못한 P1, P2, P3, 그리고 P1 순으로 처리한다면 Average Waiting Time은 (12 + 13 + 14) / 3 = 13msec이 된다.
멀티레벨 큐 (Multi-level Queue) 스케줄링
멀티레벨 큐 스케줄링은 각 프로세스 그룹에 따른 큐를 두어 수행한다. 프로세스를 기준에 따라 여러 그룹으로 나누고, 각 그룹에 따른 큐를 배치한다. 예를 들어, Interactive Process는 사용자 수준에서 데이터를 바로바로 처리하는 I/O bound Process이고, Batch Process는 일정 시간에 데이터를 한번에 처리하는 CPU bound Process이다. 우선순위에 따라 대기할 큐를 지정할 수 있고, 각 큐마다 서로 다른 스케줄링 방식을 사용할 수 있다.
멀티레벨 피드백 큐 (Multi-level Feedback Queue) 스케줄링
멀티레벨 피드백 큐 스케줄링은 멀티레벨 큐에 피드백을 추가한 것이다. 멀티레벨 큐처럼 프로세스를 여러 그룹으로 나누고, 각 그룹에 따른 큐를 배치한다. 모든 프로세스는 처음에는 무조건 우선순위가 가장 높은 큐에서 대기하게 된다. 멀티레벨 큐와 달리 우선순위에 따른 큐 지정은 불가능하다. 피드백(Feedback)은 time out이 발생한 프로세스를 보다 낮은 우선순위의 큐로 격하시키는 방식이다. I/O bound Process는 높은 우선순위를 가지며, CPU bound Process는 낮은 우선순위를 가지게 된다.