推 tedmax100:感謝 ╤︿╤ , 小弟英文實在太差了 01/28 20:28
第3題是邊查書邊寫~
※ 編輯: qazwsxee 來自: 114.39.210.24 (01/28 21:41)
→ guts:樓上是班上英文高手 .... 01/28 20:59
推 chenbojyh:推薦這個用心的超詳解 01/29 00:51
※ 引述《tedmax100 (tedmax)》之銘言：
: Consider a computer system with 1MB user space memory
: and using buddy system as the scheme for memory allocation.
: Initially, all processes are in disk job pool.
剛開始,all processes都在硬碟中，不在記憶體!
: Give the following information:
: Process CPU cycle (sec) Arrival time (sec) Process size
: P1 8 0 100K
: P2 4 2 240K
: P3 2 8 64K
: P4 5 6 256K
: P5 10 4 75K
: Consider two CPU scheduling algorithms: FCFS, preemptive SJF,
: RR with time quantum = 7. Please answer the following questions.
: 1) Draw the Gantt chart for each algorithm. (12%)
FCFS:
0________8____12__________22_____27__29
P1 P2 P5 P4 P3
preemptive SJF: //可插隊 最短時間先做法
0__2 _________
P1 Memory job pool: P2
剩餘時間 ￣4￣￣￣
P1做了2秒後，P2此時抵達ready Queue。
因為在ready Queue中的工作P2工作時間4 < P2工作時間(8-2)=6
換下P1，讓P2上去CPU執行
0__2____6 __________
P1 P2 Memory job pool:P1,P5,P4
剩餘時間: 6￣10￣5￣
在第6秒後，P2做完(中間P5,P4依序抵達，但工作時間都大於當時P2剩餘工作量，故略)
換P4上去
0__2____6__8
P1 P2 P4
在第8秒時P3抵達，(P3=2) < (P4剩餘3)
換下P4，讓P3上去CPU執行
...
..(略)
.
0__2____6__8__10___13_____19__________29
P1 P2 P4 P3 P4 P1 P5
(最後出來的甘特圖)
RR with time quantum = 7:
0_______7 進入時間: 2__4__6___
P1 ready Queue:P2,P5,P4
剩餘時間: 4￣10￣5￣
執行到第7秒後，上限值7到了，強制換人
換上ready Queue最左邊的Process，也就是P2。 (謹記ready Queue由右邊進，左邊出)
ready Queue亦是Memory job pool
只是有Queue先進先出之特性。
0_______7____11 進入時間: 4__6__７__8_
P1 P2 ready Queue:P5,P4,P1,P3
剩餘時間: 10￣5￣1￣2
一般最容易出錯的順序就在於，後來的P1跟P3時常有人寫錯誤以為先P3再P1，
因為有ready Queue的存在，所以我們可以很清楚的知道其先後進入順序。
P1在第7秒時被換下進入ready Queue，P3則是在第8秒時才進入ready Queue。
0_______7____11_______18_____23 進入時間:_7__8_18_
P1 P2 P5 P4 ready Queue: P1,P3,P5
剩餘時間: 1￣2￣3￣
...
..(略)
.
0_______7____11_______18_____23_24__26___29
P1 P2 P5 P4 P1 P3 P5
(最後出來的甘特圖)
: 2) Compute the average waiting time for each algorithm. (6%)
FCFS:
0________8____12__________22_____27__29
P1 P2 P5 P4 P3
waiting time=[(0-0)+(8-2)+(27-8)+(22-6)+(12-4)] /5
= 9.8秒
preemptive SJF:
0__2____6__8__10___13_____19__________29
P1 P2 P4 P3 P4 P1 P5
(最後出來的甘特圖)
waiting time=[(13-2-0)+(2-2)+(8-8)+(10-6-2)+(19-4)]/5
=5.6秒
RR with time quantum = 7:
0_______7____11_______18_____23_24__26___29
P1 P2 P5 P4 P1 P3 P5
(最後出來的甘特圖)
waiting time=[(23-(7-0)-0)+(7-2)+(24-8)+(18-6)+(26-4-(18-11))]/5
=(16+5+16+12+15)/5
= 12.8秒
: 3) For each scheduling algorithm, show the memory configuration snapshoot
: (i.e., which range of memory is used to allocate which process,
: and which range denote available space)
好像意思是說:記憶體的範圍被用以 分配給Process，並記錄【可用空間範圍】
: at the time when process P4 starts execution. (12%)
: 請問一下第三題是要做什麼? 有大大能幫忙解答的嗎?
翻譯:
對這3個演算法，秀出記憶體 單位狀況 when在P4開始執行時
(各P1~P5都有他的大小~~記憶體現今總大小為1MB)
: Process CPU cycle (sec) Arrival time (sec) Process size
: P1 8 0 100K
: P2 4 2 240K
: P3 2 8 64K
: P4 5 6 256K
: P5 10 4 75K
不知道要不要Process做完後釋放，記錄新的【可用空間範圍】
若要的話~圖就要改ㄧ下進進出出的位置順序~
上面說使用 buddy system
以2的次方來切~找到ㄧ個大小適合他的位置~放入
照著3個演算法的甘特圖順序 畫出他的狀況囉(ㄧ開始是空~當然是由上方往下~由左往右~)
1024
/ \ //他說畫到P4開始執行的狀況，可是Process
512 512 進入Memory job pool就是進入記憶體了
/ \ / \
256 256 256 256 //P4開始執行的時間是22秒，最後ㄧ個P3早已抵達
/ \ P2 P4 / \ Memory job pool，所以有排P3!
128 128 128 128
P1 P5 / \
64 64
P3
FCFS:
____ 0
|/P1/| (這段是裝P1:長度100k)
|////| 100k
| | (101k~128K之間是空，外部碎裂)
|----|128k ---------------------------------------------
|/P5/| (這段是裝P5::長度75k)
|////| 203k
| | (外部碎裂=空)
|----|256K ---------------------------------------------
|/P2/|
|////| (這段是裝P2:長240k)
|////|
|////| 496k
| | (外部碎裂=空)
|----|512k ---------------------------------------------
|/P4/|
|////|
|////| (這段滿滿全裝P4:長256k)
|////|
|////|
|----|768K ---------------------------------------------
|/P3/| (這段滿滿全裝P3:長64k)
|----|832k ---------------------------------------------
| |
| | 【剩下的可用空間有:1024-832=192K】
| |
| |
|____|1024K
(第6秒時)
preemptive SJF: P4(在第6秒開始執行，此時P3未進入，而P5比P4早抵達=>早進入記憶體)
(第8秒) (4秒時)
1024
/ \
512 512
/ \ / \
256 256 256 256
/ \ P2 P4
128 128
P1 P5
____ 0
|/P1/| (這段是裝P1:長度100k)
|////| 100k
| | (101k~128K之間是空，外部碎裂)
|----|128k ---------------------------------------------
|/P5/| (這段是裝P5::長度75k)
|////| 203k
| | (外部碎裂=空)
|----|256K ---------------------------------------------
|/P2/|
|////| (這段是裝P2:長240k)
|////|
|////| 496k
| | (外部碎裂=空)
|----|512k ---------------------------------------------
|/P4/|
|////|
|////| (這段滿滿全裝P4:長256k)
|////|
|////|
|----|768K ---------------------------------------------
| |
| | 【剩下的可用空間有:1024-768=256K】
| |
| |
|____|1024K
RR with time quantum = 7: P4在第18秒時開始執行，all Process都抵達了(同FCFS)
【抵達順序是固定的~大小也是固定的~
所以進入記憶體~被配置到哪邊也是固定的
所以重點關鍵在P4開始執行的時間，P3抵達記憶體否?】
(應該同FCFS)
差不多是這樣~~剛剛寫的最初版本沒看到buddy system(夥伴系統:核心記憶體配置法)
用2的次方~不斷向下切~切出一個適合的大小給Process~
概念懂了就好~~該是時候要去讀書了~~
(這題太難了~難怪有12%...)
--
學長學長!那邊有飆車族 學長學長!那邊剛好像有女生 學長學長!那邊有人紅燈右轉
砍人 被壓上車 ψQSWEET
鴿 ◥ 鴿 ◥ 鴿 ◥ 鴿 ◥ 鴿 ◥他媽的◤ 鴿
◤◎ ◎ 喔~~ ◤︶ ︶ ◤◎ ◎ 喔~~ ◤︶ ︶ ◤◎ ◎ 攔下來呀!⊙ ⊙◥
◥ ◤ ◥ █◤ ◥ ◤ ◥ 3◤╯ξ ◥ ◤沒王法了◥皿 ◤
◥ ◥◥ (哈欠)◤ ◥◤ ◥ ◥◥ (煙~) ◤ ◥ ◤￣ ◥ ◥◥是不是?!(◥ ◤ ◤)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.39.210.24
※ 編輯: qazwsxee 來自: 114.39.210.24 (01/28 20:09)
※ 編輯: qazwsxee 來自: 114.39.210.24 (01/28 20:13)
※ 編輯: qazwsxee 來自: 114.39.210.24 (01/28 20:23)