Shortest-Job-First (SJF)
FCFS RR , , . , . CPU burst , , , CPU burst. , FCFS. . " " Shortest Job First (SJF).
SJF- , . SJF - , , . SJF - ( ) . CPU burst , CPU burst , .
SJF. , p0, p1, p2 p3, CPU burst. 3.4. , , CPU burst, - .
3.4. | ||||
p0 | p1 | p2 | p3 | |
CPU burst |
SJF p3, CPU burst. p1, p0 , , p2. 3.5.
3.5. | ||||||||||||||||
p0 | ||||||||||||||||
p1 | ||||||||||||||||
p2 | ||||||||||||||||
p3 |
, SJF (4 + 1 + 9 + 0)/4 = 3,5 . , FCFS p0, p1, p2, p3 (0 + 5 + 8 + 15)/4 = 7 , . . , SJF. , ( ) SJF .
|
|
SJF p0, p1, p2 p3 CPU burst , (. . 3.6.).
3.6. | ||
CPU burst | ||
p0 | ||
p1 | ||
p2 | ||
p3 |
, p0 p3. CPU burst p3, (. 3.7.). 2 p1. CPU burst , CPU burst p3, . 2 p1 , p3. t = 6 , , p2, 7 , p3 1 , p3 . t = 7 p0 p2, p0. , p2.
3.7. | ||||||||||||||||||||
p0 | ||||||||||||||||||||
p1 | ||||||||||||||||||||
p2 | ||||||||||||||||||||
p3 |
SJF CPU burst . , , . SJF - . , , , , . , . , . CPU burst, . n - CPU burst, T(n + 1) n + 1 - CPU burst, 0 1.
|
|
T(0) . , . ,
T(n)= T(n+1)=...=T(0)
. . CPU burst , .
, . , CPU burst CPU burst:
. , T(n + 1). , CPU burst 2, , 1 . T(n + 1) SJF - .
N , , ~1/N . 1 N. i : Ti , , . Ti/N .
i - .
i.
. . . , , .
SJF . , . FCFS. SJF CPU burst. , . . , .
, , . : , , -, I/O burst CPU burst . . SJF . - , . , $100 .
, . , , . . .
|
|
, , , SJF, (. . 3.8.). , 1 4 . , , , . . p3, p0.
3.8. | |||
CPU burst | |||
p0 | |||
p1 | |||
p2 | |||
p3 |
? t = 0 p3, . t = 5 , , p0 p1. p1, (. . 3.9.). t = 8 p2, p0.
3.9. | ||||||||||||||||||||
p0 | ||||||||||||||||||||
p1 | ||||||||||||||||||||
p2 | ||||||||||||||||||||
p3 |
(. . 3.10.). , , p3, p1. t = 6 p2 t = 13. , , p0.
3.10. | ||||||||||||||||||||
p0 | ||||||||||||||||||||
p1 | ||||||||||||||||||||
p2 | ||||||||||||||||||||
p3 |
. . , . , . , . , , , , . , . , - : , , . SJF . . , .
|
|
, . . ( , ). , ( IBM 7094 1973 , 1967 ). , . 128 255. 1. , , . , .
(Multilevel Queue)
, , . , (. . 3.5). . , , . , , , , . , , , , , . . , , , ( ), FCFS, RR. , , : .
. 3.5.