👀 Process Scheduling Algorithms
- CPU Scheduling은 Ready Queue에 있는 어느 process에게 CPU를 할당할 것인지를 결정하는 문제를 다로고, CPU Scheduling에는 FCFS, SJF 등 많은 알고리즘이 존재한다.
📕 First- Come, First-Served (FCFS) Scheduling
- First in, First out (FIFO)
| Process | Burst Time |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
- Waiting time : P1 = 0; P2 = 24; P3 = 27;
- Average waiting time : (0 + 24 + 27)/3 = 17 msec
- CPU를 먼저 요청한 process가 CPU를 먼저 할당받는다.
- FCFS scheduling algorithm is non-preemptive
• Once the CPU has been allocated to a process, that process keeps the CPU until it releases the CPU, either by terminating or by requesting I/O.
• is particularly troublesome for time-sharing systems (interactive computing environment).
Convoy effect
- a problem of FCFS
- When one CPU-bound process with long CPU burst
and many I/O-bound processes with short CPU burst. - All I/O bound processes wait for the CPU-bound process to get off the CPU while I/O is idle
- All I/O- and CPU- bound processes executes I/O operation while CPU is idle.
- results in low CPU and device utilization
Summary
- FCFS algorithm은 비선점형 (non-preemptive)이다.
- 하나의 process가 할당받으면, 그 process는 끝나든, I/O를 요청받든 CPU에서 나갈 때까지 CPU를 점유한다.
- 시분할 시스템 (time-sharing systems)에서 FCFS 방식이 문제가 된다.
Convoy effect (호위 효과)
- 모든 다른 process들이 하나의 긴 process가 CPU를 양도하기를 기다리는 것
- ex) 하나의 긴 CPU burst를 가진 CPU-bound process와
짧은 CPU burst를 가진 많은 I/O-bound processes가 있다고 하면, 모든 I/O-bound processes는 CPU-bound process가 CPU를 넘겨주기를 기다려야 한다.- CPU와 device의 사용률이 현저히 낮아지게 된다!
📙 Shortest-Job-First (SJF) Scheduling
- Associate with each process the length of its next CPU burst
• Use these lengths to schedule the process with the shortest time - SJF is optimal
gives minimum average waiting time for a given set of processes
| Process | Burst Time |
|---|---|
| P1 | 6 |
| P2 | 8 |
| P3 | 7 |
| P4 | 3 |
- Average waiting time : (0+3+9+16)/4 = 7 msec
- while FCFS WT: 10.25 msec
- 가장 작은 Burst Time을 가진 porcess부터 할당한다.
Determining Length of Next CPU Burst
-
The difficulty is knowing the length of the next CPU request, can only estimate the length -> should be similar to the previous one
• Then pick process with shortest predicted next CPU burst -
Can be done by using the length of previous CPU bursts,
using exponential averaging
then,
-
Commonly, α set to ½
-
Preemptive version called shortest-remaining-time-first
Summary
SJF 방식의 문제점은 다음 CPU request의 길이를 모른다는 것이다.
오직 길이를 추측만 할수 있다는 건데, 다음 CPU burst가 직전의 burst의 길이와 비슷하다고 예상하여 구한다.
- tn : 실제 n번째 CPU burst
- τn+1 : 다음 n+1번째 CPU burst에 대한 예측값
- α, 0<=α<=1의 값을 가진다. 이때,
- τn+1 = αtn + (1-α)τn 의 공식이 나오게 된다.
- 일반적으로, α는 ½로 둔다.
- Preemptive (선점형) 방식은 shortest-remaining-time-first라고 불린다.
- 특별한 case:
- α = 0 일 때
- τn+1 = τn
- 직전의 CPU burst는 따지지 않는다.
- α = 1 일 때
- τn+1 = tn
- 직전의 CPU burst만 따진다.
- 만약, 이 공식을 확장시킨다면,,?
τn+1 = αtn + (1-α)αtn-1 + ... + (1-α)jαtn-j + ... + (1-α)n+1τ0
-> α와 (1-α) 모두 1보다 작기 때문에 뒷항으로 갈수록 숫자는 작아진다.
(each successive term has less weight than its predecessor)
Two schemes in SJF
1. non-preemptive
- once CPU given to the process it cannot be
preempted until completes its CPU burst
2. preemptive, Shortest-Remaining-Time-First (SRTF)
- if a new process arrives with CPU burst length less
than remaining time of current executing process, preempt.
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
- Average waiting time = [(10-1)+(1-1)+(17-2)+5-3)]/4 = 26/4 = 6.5 msec
- while non-preemptive SJF scheduling ave. WT: 7.75 msec
Summary
- SJF에는 non-preemptive(비선점) 과 preemptive(선점형) 2가지가 있다.
1. non-preemptive (비선점형)
- 한번 할당했으면 중간에 다른 process가 선점할 수 없다.
2. preemptive (선점형), Shortest-Remaining-Time-First (SRTF)
- 남은 시간이 제일 적은 순서대로, 중간에 선점할 수 있다.
