※ 引述《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) 第3題是邊查書邊寫~ ※ 編輯: qazwsxee 來自: 114.39.210.24 (01/28 21:41)