作者hkjluy18 (阿LAN)
看板Army-Sir
标题Re: [问题] 93计概(排程)
时间Mon Jan 25 23:54:32 2010
※ 引述《taipingeric (一只羊)》之铭言：
: 在多工作业系统中，考虑四个Jobs到达Ready Queue的时间和所需CPU时间如下
: Job 到达Ready Queue的时间 所需CPU时间
: 1 0 8
: 2 1 3
: 3 2 9
: 4 3 5
: 若CPU的排程演算法采用最短作业优先排程(Shortest-Job-First)法，则平均等待时间为
: 多少？
: (A) 5ms (B) 5.75ms
: (C)7.25ms (D) 8.25
: A:(C)
: 我找到的投影片有说明SJF 没有"到达Ready Queue的时间"是(job 2>4>1>3)
: 不过有"到达Ready Queue的时间"的顺序都看不太懂
: 请问有没有解说的资料? 或是有强者解题的?
: 感谢
: PPT解法
: http://yfrog.com/2qframevzj
SJF-(1)最小的CPU执行时间的优先做
(2)不可抢夺的
0 1 2 3 8 11 16 25
|--*--*--*------*--------*--------*-------------|
| | | p1:5 p2:3 p3:9 p3:9
| | | p2:3 p3:9 p4:5 (p4做完)
p1:8 | | p3:9 p4:5 (p2做完) (p3做)
| | p4:5 (p1做完) (p4做)
| | (p2做)
p1:7 |
p2:3 |
|
|
p1:6
p2:3
p3:9
等待时间=拿到CPU的时间-到达的时间
p1 p2 p3 p4
[(0-0)+(8-1)+(16-2)+(11-3)]/4 = 29/4 = 7.25
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 118.165.50.30
1F：推 EZ55:请问p1做完p2做.p2做完p4做.p4做完p3做 顺序要怎麽判断? 01/26 00:06
2F：→ EZ55:那又为什麽p3不是(16-2) p4不是(11-3) ? 01/26 00:07
※ 编辑: hkjluy18 来自: 118.165.50.30 (01/26 00:16)
3F：→ hkjluy18:sorry p3 p4 打错了~ 执行的顺序是依照所需的执行时间来 01/26 00:17
4F：→ hkjluy18:做排序 01/26 00:18
5F：→ hkjluy18:所以当在8的时间点，P1做完P2 P3 P4的CPU执行时间做比较 01/26 00:20
6F：推 b912327:29/4=7.25 01/26 00:20
7F：推 j80217:我懂了 @@ 01/26 00:21
8F：→ hkjluy18:P2所需的时间最短所以先做 在11的时候P3 P4做比较 P4较少 01/26 00:21
9F：→ hkjluy18:所以先做 01/26 00:21
※ 编辑: hkjluy18 来自: 118.165.50.30 (01/26 00:22)
10F：推 EZ55:P1比P2先做的原因是因为到达Ready Queue的时间比较快吗? 01/26 00:27
11F：推 j80217:楼上 是 所需CPU时间才对 01/26 00:28
12F：→ j80217:好像说错了 @@ 01/26 00:28
13F：推 EZ55:所需时间不是P2最小吗? 那为啥不是P2先做? 01/26 00:29
14F：→ j80217:你是对的 当我没说 >< 01/26 00:29
15F：→ EZ55:大家一起讨论啦@@"不然我也不会ˊˇˋ 01/26 00:30
16F：→ hkjluy18:P1比P2先做的确是因为到达的时间比较早 又因SJF属於不可 01/26 00:35
17F：→ hkjluy18:抢夺的排程 所以就算他到达的时候所需时间比P1少 也必须 01/26 00:36
18F：→ hkjluy18:等P1执行完才可以做 01/26 00:37
19F：推 EZ55:因为不可抢夺.所以不管怎样都一定是P1先做 这样对吗? 01/26 00:40
20F：→ hkjluy18:恩 01/26 00:41
21F：推 taipingeric:感谢 01/26 00:42
22F：推 EZ55:感谢>"< 01/26 00:42