計算機操作系統(tǒng)課程設計課件

計算機操作系統(tǒng)課程設計文志強計算機與通信學院計算機操作系統(tǒng)課程設計文志強1課程設計內容任務1進程管理演示任務2存儲管理系統(tǒng)設計任務3編程序模擬銀行家算法任務4磁盤調度算法的實現(xiàn)與分析任務5文件系統(tǒng)演示課程設計內容任務1進程管理演示2任務1進程管理演示課程設計內容設計一個允許n個進程并發(fā)運行的進程管理模擬系統(tǒng)。運行隊列PCBi∧就緒隊列PCBjPCBj＋1PCBj＋1∧阻塞隊列PCBkPCBk＋1PCBk＋1∧任務1進程管理演示課程設計內容運行隊列PCBi就緒隊列P3接收進程就緒隊列1就緒隊列2

...就緒隊列n超時事件1發(fā)生事件2發(fā)生等待事件1等事件2...處理機終止進程事件m發(fā)生等事件m現(xiàn)代操作系統(tǒng)中進程狀態(tài)表示方法:接收進程就緒隊列1就緒隊列2...就緒隊列n超時事件1發(fā)生4PCB進程控制塊其中包括參數(shù)①進程名name；②要求運行時間runtime；③優(yōu)先級prior；④狀態(tài)state；⑤已運行時間runedtime等。為簡單起見，只設運行隊列，就緒鏈表，阻塞隊列三種數(shù)據(jù)結構，進程的調度在這兩個隊列中切換，每個進程運行時間隨機產生，為1~20之間的整數(shù)。時間片的大小由實驗者自己定義，可為3或5，優(yōu)先級也可以隨機產生。各進程之間有一定的同步關系（可選），注意進程狀態(tài)轉換的時機。PCB進程控制塊5任務2存儲管理系統(tǒng)設計實驗內容：采用一些常用的存儲器分配算法，設計一個請求頁式存儲管理模擬系統(tǒng)并調試運行。

（1）通過隨機數(shù)產生一個指令序列，共320條指令。指令的地址按下述原則生成（可選，也可隨機產生）：①

50%的指令是順序執(zhí)行的；②25%的指令是均勻分布在前地址部分；③

25%的指令是均勻分布在后地址部分；具體的實施方法是：①

在[0，319]的指令地址之間隨機選取一起點m；②

順序執(zhí)行一條指令，即執(zhí)行地址為m+1的指令；③

在前地址[0，m+1]中隨機選取一條指令并執(zhí)行，該指令地址為m’；④

順序執(zhí)行一條指令，其地址為m’+1;⑤

在后地址[m’+2，319]中隨機選取一條指令并執(zhí)行；⑥

重復上述步驟①~⑤，直到執(zhí)行320次指令。任務2存儲管理系統(tǒng)設計實驗內容：采用一些常用的存儲器分配算6（2）將指令序列變成為頁地址流設：①頁面大小為1k；

②用戶內存容量分別為4頁到32頁；

③用戶虛存容量為32k。在用戶虛存中，按每k存放10條指令排列虛存地址，即320條指令在虛存中的存放方式為：第0條-第9條指令為第0頁（對應虛存地址為[0，9]）；第10條-第19條指令為第1頁（對應許存地址為[10，19]）；

…….第310條-第319條指令為第31頁（對應許存地址為[310，319]）；按以上方式，用戶指令可組成32頁。（2）將指令序列變成為頁地址流7（3）

計算并輸出下述各種算法在不同內存容量下的命中率。①

先進先出的算法（FIFO）；

頁面失效次數(shù)命中率=1-————————

頁地址流長度

在本次實驗中，頁地址長度為320，頁面失效次數(shù)為每次訪問相應指令時，該指令所對應的頁不在內存的次數(shù)。

（3）

計算并輸出下述各種算法在不同內存容量下的命中率。83．隨機數(shù)產生辦法關于隨機數(shù)產生法，系統(tǒng)提供函數(shù)srand()和rand()，分別進行初始化和產生隨機數(shù)。例如：

srand()；語句可初始化一個隨機數(shù)；

a[0]=rand()%320；

a[1]=rand()%a[0]；

S=a[1]+rand()%(a[0]-a[1])……

語句可用來產生a[0]與a[1]中的隨機數(shù)。

3．隨機數(shù)產生辦法9整個算法的思想見下頁整個算法的思想見下頁10

ipnpfn

3131-1

3030-100-1

11-122-1

33-1

44-1

66-1

77-1

55-1

2929-1

2828-1

2727-1………

pnpfnnext

^0123頁表結構空閑物理頁框初始狀態(tài)freefp_headpn表示頁號；pfn表示有效位，當頁幀不在內存時為－1，否則為指向其內存地址。

66-1ipnpfn3131-13011

ipnpfn

3131-1

3030-100-1

11-122-1

33-1

44-1

660

77-1

55-1

2929-1

2828-1

2727-1………

pnpfnnext

^0123頁表結構空閑物理頁框第一次分配freefp_head

6^Busypf_headBusypf_tail2727-1ipnpfn3131-13012

ipnpfn

3131-1

3030-100-1

11-122-1

33-1

44-1

660

77-1

55-1

2929-1

2828-1

27271………

pnpfnnext

^0271^23頁表結構空閑物理頁框第二次分配freefp_head

6Busypf_headBusypf_tail2828-1ipnpfn3131-13013

ipnpfn

3131-1

3030-100-1

11-122-1

33-1

44-1

660

77-1

55-1

2929-1

28282

27271………

pnpfnnext

^0271282^3頁表結構空閑物理頁框第三次分配freefp_head

6Busypf_headBusypf_tail3030-1ipnpfn3131-13014

ipnpfn

3131-1

3030300-1

11-122-1

33-1

44-1

660

77-1

55-1

2929-1

28282

27271………

pnpfnnext

^0271282303^頁表結構空閑物理頁框第四次分配freefp_head

6Busypf_headBusypf_tail第五次分配

22-1ipnpfn3131-13015

ipnpfn

3131-1

3030300-1

11-122-1

33-1

44-1

66-1

77-1

55-1

2929-1

28282

27271………

pnpfnnext

^0271282303^頁表結構空閑物理頁框第五次,淘汰一頁freefp_head

6^Busypf_headBusypf_tail

22-1ipnpfn3131-13016

ipnpfn

3131-1

3030300-1

11-1220

33-1

44-1

66-1

77-1

55-1

2929-1

28282

27271………

pnpfnnext

^0271282303頁表結構空閑物理頁框第五次,分配一頁freefp_head

2^Busypf_headBusypf_tailipnpfn3131-13017擴展的銀行家算法描述n為系統(tǒng)中的進程個數(shù)。m為系統(tǒng)中的資源類型數(shù)。Available(1:m):現(xiàn)有資源向量。Available(j)=k表示有k個未分配的j類資源。如：Available＝(9,3,6)Max(1:n,1:m):資源最大申請量矩陣。Max(i,j)=k表示第i個進程對第j類資源的最大申請量為k.r1r2r3224413316223P1P2P3P4任務3編程序模擬銀行家算法編制銀行家算法程序，并檢測所給狀態(tài)的系統(tǒng)安全性。擴展的銀行家算法描述r1r2r32244118Allocation(1:n,1:m):資源分配矩陣。Allocation(i,j)=k表示進程i已占有k個j類資源。

Need(1:n,1:m):進程以后還需要的資源矩陣。Need(i,j)=k表示第i個進程以后還需要k個第j類資源。顯然Need=Max-AllocationRequest(1:n,1:m):進程申請資源矩陣。Request(i,j)=k表示進程i申請k個第j類資源。

r1r2r3200112115001P1P2P3P4r1r2r3024301201222P1P2P3P4Allocation(1:n,1:m):資源分配矩陣。r119資源分配程序的工作過程描述：

基本思想：當進程提出資源申請時，系統(tǒng)首先檢查該進程對資源的申請量是否超過其最大需求量，以及系統(tǒng)現(xiàn)有資源能否滿足進程需要。若能，則進一步檢查：若把資源分給該進程，系統(tǒng)能否處于安全狀態(tài)？若安全則分配，否則置該進程為等待資源狀態(tài)。

為簡單起見，記Ai為A(i,1),A(i,2),…,A(i,m)，其中A為n×m矩陣。

定義長度為m的向量X，Y間的關系為：

X≤Y當且僅當X(i)≤Y(i)(i=1,2,…,m)資源分配程序的工作過程描述：20

1.如果Requesti>Needi則報錯返回。

2.如果Requesti>Available,則進程i進入等待資源狀態(tài)，返回。

3.假設進程i的申請已獲準，于是修改系統(tǒng)狀態(tài)：

Available=Available-Requesti

Allocationi=Allocationi+Requesti

Needi=Needi-Requesti

4.調用安全狀態(tài)檢查算法。設進程i申請資源，申請資源向量為Requesti，則有如下的資源分配過程：1.如果Requesti>Needi則報錯返回。設進21（續(xù)）

5.若系統(tǒng)處于安全狀態(tài)，則將進程i申請的資源分配給進程i，返回。

6.若系統(tǒng)處于不安全狀態(tài)，則進程i進入等待資源狀態(tài)，并恢復系統(tǒng)狀態(tài)后返回：

Available=Available+Requesti

Allocationi=Allocationi-Requesti Needi=Needi+Requesti（續(xù)）22安全狀態(tài)檢查算法：

設Work(1:m)為臨時工作向量。初始時Work=Available.令N={1,2,…,n}1.尋找j∈N使其滿足Needj≤Work,若不存在這樣的j則轉(3);2.Work=Work+Allocationj

N=N-{j},轉(1);3.如果N為空則返回系統(tǒng)安全；如果N不為空則返回系統(tǒng)不安全。算法時間復雜度為O(m×n2)，如果每類資源只有一個，則時間復雜度為O(n2)安全狀態(tài)檢查算法：23假定系統(tǒng)中有四個進程P1、P2、P3、P4，三種類型的資源R1、R2、R3，數(shù)量分別為9、3、6，在T0時刻的資源分配情況如下表所示。舉例：資源進程maxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3P1322100222112P2613511102

P3314211103

P4422002420

假定系統(tǒng)中有四個進程P1、P2、P3、P4，三種類型的資源R24T0時刻的安全性利用安全性算法對T0時刻的安全性進行分析，如下表，可知T0時刻存在一個安全序列{P2、P1、P3、P4}，所以系統(tǒng)是安全的。資源

進程WorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3P2112102511623TrueP1623222100723TrueP3723103211934TrueP4934420002936TrueT0時刻的安全性資源WorkNeedAllocationWo25(2)P2請求資源P2發(fā)出請求向量Request2(1,0,1),系統(tǒng)按銀行家算法進行檢查：Request2(1,0,1)<=Need2(1,0,2)Request2(1,0,1)<=Available(1,1,2)3)系統(tǒng)先假定可為P2分配資源，并修改Available、Allocation2、Need2向量，資源變化情況如下表。資源進程maxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3P1322100222011P2613612001

P3314211103

P4422002420

(2)P2請求資源資源maxAllocationNeed264)再利用安全性算法檢查此時系統(tǒng)是否安全，如下表?？芍嬖谝粋€安全序列{P2、P1、P3、P4}，所以系統(tǒng)是安全的，可以立即將P2所申請的資源分配給它。資源

進程WorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3P2011001612623TrueP1623222100723TrueP3723103211934TrueP4934420002936True4)再利用安全性算法檢查此時系統(tǒng)是否安全，如下表?？芍嬖?7(3)P1請求資源P1發(fā)出請求向量Request1(1,0,1),系統(tǒng)按銀行家算法進行檢查：Request1(1,0,1)<=Need1(2,2,2)Request1(1,0,1)≮Available(0,1,1)，讓P1等待(4)P3請求資源P3發(fā)出請求向量Request3(0,0,1),系統(tǒng)按銀行家算法進行檢查：Request3(0,0,1)<=Need3(1,0,3)Request3(0,0,1)<=Available(0,1,1)3)系統(tǒng)先假定可為P3分配資源，并修改Available、Allocation3、Need3向量，資源變化情況如表5。(3)P1請求資源(4)P3請求資源28表5P3申請資源后的資源分配表資源進程maxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3P1322100222010P2613612001

P3314212102

P4422002420

4)再利用安全性算法檢查此時系統(tǒng)是否安全，從上表可看出，可用資源Available(0,1,0)已不能滿足任何進程的需要，故系統(tǒng)進入不安全狀態(tài)，此時系統(tǒng)不分配資源給P3。表5P3申請資源后的資源分配表資源maxAllocat29任務4磁盤調度算法的實現(xiàn)與分析

編程序實現(xiàn)下述磁盤調度算法，并求出每種算法的平均移動磁道數(shù)，并分析結果：①先來先服務算法（FCFS）②最短尋道時間優(yōu)先算法（SSTF）③掃描算法（SCAN）④循環(huán)掃描算法（C-SCAN）任務4磁盤調度算法的實現(xiàn)與分析編程序實現(xiàn)下述磁盤調度算法30磁盤調度策略1、先來先服務FCFS(FirstComeFirstServer)：這是最簡單的磁盤調度策略，它根據(jù)進程請求訪問磁盤的時間順序進行調度。2、最短尋道時間優(yōu)先SSFT(ShortestSeekTimeFirst)：它是根據(jù)磁頭當前的位置，選擇請求隊列中距離磁頭最短的請求響應。3、SCAN：也稱電梯策略，要求磁頭臂僅僅沿一個方向移動，并在途中滿足所有未完成的請求，直到它到達這個方向的最后一個磁道，或這個方向沒有別的請求為止，然后倒轉服務方向，同樣按順序完成的有請求。4、C－SCAN：是循環(huán)掃描法，當?shù)竭_最后一個磁道時，磁頭臂返回到磁頭的另一端，并再次開始掃描。磁盤調度策略1、先來先服務FCFS(FirstCome31假設磁盤有200個磁道，磁盤請求隊列中是一些隨機請求。被請求的磁道按接收順序分別為：55、58、39、18、90、160、150、38、184，當前磁頭在100磁道處

FCFS策略磁頭臂的移動軌跡如下：

183839555890150160184100假設磁盤有200個磁道，磁盤請求隊列中是一些隨機請求。被請求32假設磁盤有200個磁道，磁盤請求隊列中是一些隨機請求。被請求的磁道按接收順序分別為：55、58、39、18、90、160、150、38、184，當前磁頭在100磁道處

SSTF策略磁頭臂的移動軌跡如下：

183839555890150160184100假設磁盤有200個磁道，磁盤請求隊列中是一些隨機請求。被請求33假設磁盤有200個磁道，磁盤請求隊列中是一些隨機請求。被請求的磁道按接收順序分別為：55、58、39、18、90、160、150、38、184，當前磁頭在100磁道處

SCAN策略磁頭臂的移動軌跡如下：

1838395558901501601