計算機(jī)操作系統(tǒng)課程設(shè)計-課件

計算機(jī)操作系統(tǒng)課程設(shè)計1ppt課件計算機(jī)操作系統(tǒng)課程設(shè)計1ppt課件課程設(shè)計內(nèi)容任務(wù)1進(jìn)程管理演示任務(wù)2存儲管理系統(tǒng)設(shè)計任務(wù)3編程序模擬銀行家算法任務(wù)4磁盤調(diào)度算法的實現(xiàn)與分析任務(wù)5文件系統(tǒng)演示2ppt課件課程設(shè)計內(nèi)容任務(wù)1進(jìn)程管理演示2ppt課件任務(wù)1進(jìn)程管理演示課程設(shè)計內(nèi)容設(shè)計一個允許n個進(jìn)程并發(fā)運(yùn)行的進(jìn)程管理模擬系統(tǒng)。運(yùn)行隊列PCBi∧就緒隊列PCBjPCBj＋1PCBj＋1∧阻塞隊列PCBkPCBk＋1PCBk＋1∧3ppt課件任務(wù)1進(jìn)程管理演示課程設(shè)計內(nèi)容運(yùn)行隊列PCBi就緒隊列P接收進(jìn)程就緒隊列1就緒隊列2

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

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

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

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

在[0，319]的指令地址之間隨機(jī)選取一起點(diǎn)m；②

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

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

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

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

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

②用戶內(nèi)存容量分別為4頁到32頁；

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

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

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

先進(jìn)先出的算法（FIFO）；

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

頁地址流長度

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

8ppt課件（3）

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

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

a[0]=rand()%320；

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

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

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

9ppt課件3．隨機(jī)數(shù)產(chǎn)生辦法9ppt課件整個算法的思想見下頁10ppt課件整個算法的思想見下頁10ppt課件

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頁表結(jié)構(gòu)空閑物理頁框初始狀態(tài)freefp_headpn表示頁號；pfn表示有效位，當(dāng)頁幀不在內(nèi)存時為－1，否則為指向其內(nèi)存地址。

66-111ppt課件ipnpfn3131-130

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頁表結(jié)構(gòu)空閑物理頁框第一次分配freefp_head

6^Busypf_headBusypf_tail2727-112ppt課件ipnpfn3131-130

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頁表結(jié)構(gòu)空閑物理頁框第二次分配freefp_head

6Busypf_headBusypf_tail2828-113ppt課件ipnpfn3131-130

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頁表結(jié)構(gòu)空閑物理頁框第三次分配freefp_head

6Busypf_headBusypf_tail3030-114ppt課件ipnpfn3131-130

ipnpfn

3131-1

3030300-1

11-122-1

33-1

44-1

660

77-1

55-1

2929-1

28282

27271…

…

…

pnpfnnext

^0271282303^頁表結(jié)構(gòu)空閑物理頁框第四次分配freefp_head

6Busypf_headBusypf_tail第五次分配

22-115ppt課件ipnpfn3131-130

ipnpfn

3131-1

3030300-1

11-122-1

33-1

44-1

66-1

77-1

55-1

2929-1

28282

27271…

…

…

pnpfnnext

^0271282303^頁表結(jié)構(gòu)空閑物理頁框第五次,淘汰一頁freefp_head

6^Busypf_headBusypf_tail

22-116ppt課件ipnpfn3131-130

ipnpfn

3131-1

3030300-1

11-1220

33-1

44-1

66-1

77-1

55-1

2929-1

28282

27271…

…

…

pnpfnnext

^0271282303頁表結(jié)構(gòu)空閑物理頁框第五次,分配一頁freefp_head

2^Busypf_headBusypf_tail17ppt課件ipnpfn3131-130擴(kuò)展的銀行家算法描述n為系統(tǒng)中的進(jìn)程個數(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ìn)程對第j類資源的最大申請量為k.r1r2r3224413316223P1P2P3P4任務(wù)3編程序模擬銀行家算法編制銀行家算法程序，并檢測所給狀態(tài)的系統(tǒng)安全性。18ppt課件擴(kuò)展的銀行家算法描述r1r2r322441Allocation(1:n,1:m):資源分配矩陣。Allocation(i,j)=k表示進(jìn)程i已占有k個j類資源。Need(1:n,1:m):進(jìn)程以后還需要的資源矩陣。Need(i,j)=k表示第i個進(jìn)程以后還需要k個第j類資源。顯然Need=Max-AllocationRequest(1:n,1:m):進(jìn)程申請資源矩陣。Request(i,j)=k表示進(jìn)程i申請k個第j類資源。r1r2r3200112115001P1P2P3P4r1r2r3024301201222P1P2P3P419ppt課件Allocation(1:n,1:m):資源分配矩陣。r1資源分配程序的工作過程描述：

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

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

定義長度為m的向量X，Y間的關(guān)系為：

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

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

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

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

Available=Available-Requesti Allocationi=Allocationi+Requesti Needi=Needi-Requesti

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

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

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

Available=Available+Requesti Allocationi=Allocationi-Requesti Needi=Needi+Requesti22ppt課件（續(xù)）22ppt課件安全狀態(tài)檢查算法：設(shè)Work(1:m)為臨時工作向量。初始時Work=Available.令N={1,2,…,n}1.尋找j∈N使其滿足Needj≤Work,若不存在這樣的j則轉(zhuǎn)(3);2.Work=Work+Allocationj

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

P3314211103

P4422002420

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

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

P3314211103

P4422002420

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

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

P3314212102

P4422002420

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

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

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

18383955589015016018410032ppt課件假設(shè)磁盤有200個磁道，磁盤請求隊列中是一些隨機(jī)請求。被請求假設(shè)磁盤有200個磁道，磁盤請求隊列中是一些隨機(jī)請求。被請求的磁道按接收順序分別為：55、58、39、18、90、160、150、38、184，當(dāng)前磁頭在100磁道處

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

18383955589015016018410033ppt課件假設(shè)磁盤有200個磁道，磁盤請求隊列中是一些隨機(jī)請求。被請求假設(shè)磁盤有200個磁道，磁盤請求隊列中是一些隨機(jī)請求。被請求的磁道按接收順序分別為：55、58、39、18、90、160、150、38、184，當(dāng)前磁頭在100磁道處

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

1838395558901501601841002