1. CPU-I/O Burst Cycle
프로세스 실행은 CPU burst와 I/O burst가 번갈아 나타나는 순환(cycle)으로 구성된다.
CPU Burst 분포
- 대부분의 CPU burst는 매우 짧다 (Hyperexponential distribution)
- I/O-bound job: 짧은 CPU burst가 많음
- CPU-bound job: 길고 적은 CPU burst
2. CPU Scheduler
Multiprogramming 환경에서 CPU scheduler는 메모리에 있는 Ready 상태의 프로세스 중 하나를 선택하여 CPU를 할당한다.
2.1 Scheduling이 발생하는 시점
- Process가 Running → Waiting 상태로 전환 (예: I/O 요청)
- Process가 Running → Ready 상태로 전환 (예: Time quantum 만료)
- Process가 Waiting → Ready 상태로 전환 (예: I/O 완료 Interrupt)
- Process가 Terminated
2.2 Preemptive vs Non-preemptive
| 유형 | 발생 시점 | 설명 |
|---|---|---|
| Non-preemptive | 1, 4만 | 프로세스가 자발적으로 CPU를 반납할 때만 스케줄링. 실행 중인 프로세스를 강제로 빼앗지 않음 |
| Preemptive | 1, 2, 3, 4 모두 | 실행 중인 프로세스를 중간에 선점(preempt)하여 다른 프로세스에게 CPU를 줄 수 있음 |
3. Dispatcher
Dispatcher는 Short-term scheduler가 선택한 프로세스에게 CPU 제어권을 넘기는 모듈이다.
수행 작업:
- Context switching
- User mode로 전환
- 사용자 프로그램의 적절한 위치로 jump하여 재시작
Dispatch latency: Dispatcher가 하나의 프로세스를 멈추고 다른 프로세스를 시작하는 데 걸리는 시간 (주로 Context switch overhead)
4. Scheduling 성능 기준 (Scheduling Criteria)
| 기준 | 목표 | 설명 |
|---|---|---|
| CPU Utilization | 최대화 | CPU를 가능한 한 바쁘게 유지 |
| Throughput | 최대화 | 단위 시간당 완료되는 프로세스 수 |
| Turnaround Time | 최소화 | 특정 프로세스를 완료하는 데 걸리는 전체 시간 |
| Waiting Time | 최소화 | Ready queue에서 대기한 시간의 총합 |
| Response Time | 최소화 | 요청 제출부터 첫 번째 응답이 생산될 때까지의 시간 (Timesharing 환경에 중요) |
5. Scheduling Algorithms
5.1 FCFS (First-Come First-Served)
도착한 순서대로 CPU를 할당하는 가장 단순한 알고리즘. Non-preemptive.
예제:
| Process | Burst Time |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
도착 순서 P1, P2, P3:
| P1 | P2 | P3 |
0 24 27 30
- Waiting time: P1=0, P2=24, P3=27
- Average waiting time = (0+24+27)/3 = 17
도착 순서 P2, P3, P1:
| P2 | P3 | P1 |
0 3 6 30
- Waiting time: P1=6, P2=0, P3=3
- Average waiting time = (6+0+3)/3 = 3 - 훨씬 좋음!
Convoy effect: 긴 프로세스 뒤에 짧은 프로세스들이 줄을 서서 전체 대기 시간이 커지는 현상
5.2 SJF (Shortest-Job-First)
다음 CPU burst가 가장 짧은 프로세스에게 CPU를 할당한다. SJF는 최적(Optimal) - 주어진 프로세스 집합에 대해 평균 Waiting time을 최소화한다.
Non-preemptive SJF 예제:
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0.0 | 7 |
| P2 | 2.0 | 4 |
| P3 | 4.0 | 1 |
| P4 | 5.0 | 4 |
| P1 | P3| P2 | P4 |
0 7 8 12 16
- Average waiting time = (0+6+3+7)/4 = 4
5.3 SRTF (Shortest-Remaining-Time-First)
SJF의 Preemptive 버전. 새 프로세스가 도착했을 때 남은 실행 시간이 현재 프로세스보다 짧으면 선점한다.
Preemptive SJF (SRTF) 예제 (같은 데이터):
| P1 | P2 | P3| P2 | P4 | P1 |
0 2 4 5 7 11 16
- Average waiting time = (9+1+0+2)/4 = 3
5.4 CPU Burst 길이 예측 - Exponential Averaging
실제로는 다음 CPU burst 길이를 알 수 없으므로 과거 데이터를 기반으로 예측한다.
공식:
T(n+1) = a * t(n) + (1 - a) * T(n)
- t(n): n번째 CPU burst의 실제 길이
- T(n): n번째 CPU burst에 대한 예측 값
- a: 가중치 (0 ⇐ a ⇐ 1)
a 값에 따른 특성:
- a = 0: T(n+1) = T(n) - 최근 이력 무시, 초기 추정치만 사용
- a = 1: T(n+1) = t(n) - 직전 실제 burst만 반영
- 전개하면: T(n+1) = a*t(n) + (1-a)at(n-1) + … + (1-a)^(n+1)*T(0)
- a와 (1-a) 모두 ⇐ 1이므로, 과거로 갈수록 가중치가 지수적으로 감소
5.5 Priority Scheduling
각 프로세스에 Priority 번호(정수)를 부여하고, 가장 높은 우선순위(보통 작은 숫자 = 높은 Priority)의 프로세스에게 CPU를 할당한다.
- Preemptive 또는 Non-preemptive 모두 가능
- SJF는 Priority scheduling의 특수한 경우 (Priority = 예측된 다음 CPU burst 길이)
문제점:
- Starvation (기아): 낮은 우선순위의 프로세스가 영원히 실행되지 못할 수 있다
해결책:
- Aging: 시간이 지남에 따라 대기 중인 프로세스의 우선순위를 점진적으로 높여줌
5.6 RR (Round Robin)
각 프로세스가 Time quantum(보통 10-100ms)만큼의 작은 CPU 시간을 받는다. 시간이 다 되면 프로세스는 선점되어 Ready queue 끝에 추가된다.
특성:
- Ready queue에 n개 프로세스, Time quantum이 q초이면:
- 각 프로세스는 CPU 시간의 1/n을 최대 q초 단위로 받음
- 어떤 프로세스도 *(n-1)q 시간 이상 대기하지 않음
- q가 크면 - FIFO(FCFS)와 동일
- q가 너무 작으면 - Context switch overhead가 커짐
예제 (Time quantum = 20):
| Process | Burst Time |
|---|---|
| P1 | 53 |
| P2 | 17 |
| P3 | 68 |
| P4 | 24 |
|P1 |P2 |P3 |P4 |P1 |P3 |P4|P1 |P3 |P3|
0 20 37 57 77 97 117 121 134 154 162
- SJF보다 일반적으로 Average turnaround time이 높지만, Response time은 더 좋다
5.7 Multilevel Queue
Ready queue를 여러 개의 별도 Queue로 분할한다.
예시 구성 (높은 우선순위 → 낮은 우선순위):
- System processes
- Interactive processes
- Interactive editing processes
- Batch processes
- Student processes
각 Queue의 스케줄링 알고리즘:
- Foreground (Interactive): RR
- Background (Batch): FCFS
Queue 간 스케줄링:
- Fixed priority: 상위 Queue를 모두 처리한 후 하위 Queue 처리 - Starvation 가능
- Time slice: 각 Queue에 CPU 시간의 일정 비율 배분 (예: Foreground 80% RR, Background 20% FCFS)
5.8 Multilevel Feedback Queue
Multilevel Queue와 달리, 프로세스가 Queue 간 이동(migrate)할 수 있다.
정의해야 할 파라미터:
- Queue의 수
- 각 Queue의 스케줄링 알고리즘
- 프로세스를 상위 Queue로 승격(upgrade)하는 기준
- 프로세스를 하위 Queue로 강등(demote)하는 기준
- 프로세스가 서비스를 받을 때 어느 Queue에 진입할지 결정하는 방법
예제 (3개 Queue):
| Queue | Time Quantum | 알고리즘 |
|---|---|---|
| Q0 | 8 ms | FCFS |
| Q1 | 16 ms | FCFS |
| Q2 | - | FCFS |
동작:
- 새 Job이 Q0에 들어감 (FCFS)
- CPU를 받아 8ms 실행
- 8ms 안에 완료하지 못하면 - Q1로 이동
- Q1에서 16ms 추가 실행
- 16ms 안에도 완료하지 못하면 - Q2로 이동 (FCFS로 처리)
이 구조는 짧은 Job을 빠르게 처리하고, 긴 Job은 점차 낮은 우선순위로 보내는 효과가 있다.
6. Real-Time Scheduling
| 유형 | 설명 |
|---|---|
| Hard real-time | 중요한 작업(Critical task)을 보장된 시간 내에 반드시 완료해야 함 |
| Soft real-time | 중요한 프로세스가 덜 중요한 프로세스보다 우선순위를 받을 것을 요구하지만, 절대적 보장은 아님 |