作者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