第一篇：操作系統(tǒng)課程設(shè)計(jì)

《操作系統(tǒng)》/《操作系統(tǒng)課程設(shè)計(jì)》課設(shè)指導(dǎo)書

《操作系統(tǒng)》 《操作系統(tǒng)課程設(shè)計(jì)》

指導(dǎo)

信息技術(shù)學(xué)院課設(shè)書

《操作系統(tǒng)》/《操作系統(tǒng)課程設(shè)計(jì)》課設(shè)指導(dǎo)書

《操作系統(tǒng)》/《操作系統(tǒng)課程設(shè)計(jì)》

課設(shè)項(xiàng)目指導(dǎo)書

課設(shè)項(xiàng)目1 磁盤調(diào)度算法程序設(shè)計(jì)

一、目的

磁盤是經(jīng)常使用的一種重要的外設(shè)，對(duì)磁盤數(shù)據(jù)的尋道時(shí)間的長短直接影響機(jī)器的整體運(yùn)行速度，本設(shè)計(jì)要求用C語言（或高級(jí)語言）編寫程序模擬實(shí)現(xiàn)磁盤調(diào)度的常用算法。以加深對(duì)磁盤調(diào)度常用算法的理解和實(shí)現(xiàn)技巧。

二、課設(shè)要求

1）、設(shè)計(jì)一個(gè)函數(shù)完成先來先服務(wù)的磁盤調(diào)度功能。2）、設(shè)計(jì)一個(gè)函數(shù)完成最短尋道時(shí)間優(yōu)先的磁盤調(diào)度功能。3）、設(shè)計(jì)一個(gè)函數(shù)完成電梯算法的磁盤調(diào)度功能。

三、課設(shè)設(shè)備、環(huán)境

奔騰以上計(jì)算機(jī)，裝有Turbo C 2.0軟件

四、課設(shè)方法及步驟

1、設(shè)計(jì)方法：

根據(jù)設(shè)計(jì)任務(wù)書的要求，畫出程序設(shè)計(jì)流程圖，確定程序的功能，把整個(gè)程序根據(jù)功能要求分解為各個(gè)子程序，利用TC語言分編寫程序代碼，然后進(jìn)行上機(jī)調(diào)試、修改、進(jìn)行連接，測試，寫出設(shè)計(jì)總結(jié)報(bào)告。

2、設(shè)計(jì)步驟：

1）、自定義磁盤調(diào)度相關(guān)的數(shù)據(jù)結(jié)構(gòu)。

2）、依據(jù)先來先服務(wù)算法（FCFS）、最短尋道優(yōu)先算法（SSTF）、掃描(SCAN，也稱電梯)算法的原理，編寫對(duì)應(yīng)函數(shù)，模擬系統(tǒng)的磁盤調(diào)度服務(wù)。

3）、為了更好地模擬和評(píng)價(jià)算法的性能，隨機(jī)產(chǎn)生需尋道的磁道序列，磁道序列的首磁道為磁頭的當(dāng)前位置；在SCAN算法中，允許用戶指定當(dāng)前尋道方向。

4）、統(tǒng)計(jì)各算法總尋道次數(shù)和平均尋道距離；分析各算法性能，并作出評(píng)價(jià)。5）、設(shè)計(jì)要求一人單獨(dú)進(jìn)行，獨(dú)立完成設(shè)計(jì)，上機(jī)進(jìn)行運(yùn)行調(diào)試。6）、寫出課程設(shè)計(jì)報(bào)告書。

課設(shè)項(xiàng)目2 進(jìn)程調(diào)度程序設(shè)計(jì)

一、目的

進(jìn)程調(diào)度是處理機(jī)管理的核心內(nèi)容。本設(shè)計(jì)要求用C語言編寫和調(diào)試一個(gè)簡單的進(jìn)程調(diào)度程序。通過設(shè)計(jì)本可以加深理解有關(guān)進(jìn)程控制塊、進(jìn)程隊(duì)列的概念，并體會(huì)和了解最高優(yōu)先數(shù)優(yōu)先的調(diào)度算法（即把處理機(jī)分配給優(yōu)先數(shù)最高的進(jìn)程）和先來先服務(wù)算法的具體實(shí)施辦法。

二、課設(shè)要求

1）進(jìn)程調(diào)度算法：采用最高優(yōu)先數(shù)優(yōu)先的調(diào)度算法（即把處理機(jī)分配給優(yōu)先數(shù)最高的進(jìn)程）和先來先服務(wù)算法。

2）每個(gè)進(jìn)程有一個(gè)進(jìn)程控制塊（PCB）表示。進(jìn)程控制塊可以包含如下信息：進(jìn)程名、優(yōu)先數(shù)、到達(dá)時(shí)間、需要運(yùn)行時(shí)間、已用CPU時(shí)間、進(jìn)程狀態(tài)等等。

3）進(jìn)程的優(yōu)先數(shù)及需要的運(yùn)行時(shí)間可以事先人為地指定（也可以由隨機(jī)數(shù)產(chǎn)生）。進(jìn)程的到達(dá)時(shí)間為進(jìn)程輸入的時(shí)間。進(jìn)程的運(yùn)行時(shí)間以時(shí)間片為單位進(jìn)行計(jì)算。

4）每個(gè)進(jìn)程的狀態(tài)可以是就緒 W（Wait）、運(yùn)行R（Run）、或完成F（Finish）三種狀態(tài)之一。

5）就緒進(jìn)程獲得 CPU后都只能運(yùn)行一個(gè)時(shí)間片。用已占用CPU時(shí)間加1來表示。如果運(yùn)行一個(gè)時(shí)間片后，進(jìn)程的已占用 CPU時(shí)間已達(dá)到所需要的運(yùn)行時(shí)間，則撤消該進(jìn)程，如果運(yùn)行一個(gè)時(shí)間片后進(jìn)程的已占用CPU時(shí)間還未達(dá)所需要的運(yùn)行時(shí)間，也就是進(jìn)程還需要繼續(xù)運(yùn)行，此時(shí)應(yīng)將進(jìn)程的優(yōu)先數(shù)減1（即降低一級(jí)），然后把它插入就緒隊(duì)列等待CPU。

6）每進(jìn)行一次調(diào)度程序都打印一次運(yùn)行進(jìn)程、就緒隊(duì)列、以及各個(gè)進(jìn)程的 PCB，以便進(jìn)行檢查。

7）重復(fù)以上過程，直到所要進(jìn)程都完成為止。

三、課設(shè)設(shè)備、環(huán)境

奔騰以上計(jì)算機(jī)，裝有Turbo C 2.0軟件

四、課設(shè)方法及步驟

1、設(shè)計(jì)方法：

根據(jù)設(shè)計(jì)任務(wù)書的要求，畫出程序設(shè)計(jì)流程圖，確定進(jìn)程調(diào)度程序的功能，把整個(gè)程序根據(jù)功能要求分解為各個(gè)子程序，利用TC語言分編寫程序代碼，然后進(jìn)行上機(jī)調(diào)試、修改、進(jìn)行連接，測試，寫出設(shè)計(jì)總結(jié)報(bào)告。

《操作系統(tǒng)》/《操作系統(tǒng)課程設(shè)計(jì)》課設(shè)指導(dǎo)書

進(jìn)程調(diào)度算法參考流程圖

2、設(shè)計(jì)步驟：

1）充分了解各項(xiàng)設(shè)計(jì)要求。深入理解有關(guān)進(jìn)程控制塊、進(jìn)程隊(duì)列的概念，并體會(huì)和了解最高優(yōu)先數(shù)優(yōu)先的調(diào)度算法（即把處理機(jī)分配給優(yōu)先數(shù)最高的進(jìn)程）和先來先服務(wù)算法的具體實(shí)施辦法。

2）、按要求對(duì)進(jìn)程調(diào)度程序進(jìn)行分解，根據(jù)功能將其分解成多個(gè)子模塊。

3）、建立主控模塊程序流程圖及各功能子模塊程序流程圖，要求條理清楚、簡單明了、功能完備。

4）、根據(jù)流程圖編制主程序代碼及子程序代碼。要求程序設(shè)計(jì)結(jié)構(gòu)清晰，簡潔，便于修改和調(diào)試。

5）、上述設(shè)計(jì)要求一人單獨(dú)進(jìn)行，獨(dú)立完成設(shè)計(jì)。6）、設(shè)計(jì)完成后，上機(jī)進(jìn)行運(yùn)行調(diào)試。

7）、程序運(yùn)行成功，然后進(jìn)行某些功能測試，選擇有實(shí)用性、特殊性的數(shù)據(jù)進(jìn)行錄入調(diào)試，使設(shè)計(jì)進(jìn)一步得到改進(jìn)并完善。

8）、打印出程序運(yùn)行結(jié)果，并對(duì)結(jié)果進(jìn)行分析，驗(yàn)證程序設(shè)計(jì)的正確性。9）、寫出課程設(shè)計(jì)報(bào)告書。

《操作系統(tǒng)》/《操作系統(tǒng)課程設(shè)計(jì)》課設(shè)指導(dǎo)書

課設(shè)項(xiàng)目3 銀行家算法程序設(shè)計(jì)

一、目的

銀行家算法是避免死鎖的一種重要方法，本設(shè)計(jì)要求用C語言（或高級(jí)語言）編寫和調(diào)試一個(gè)簡單的銀行家算法程序。加深了解有關(guān)資源申請(qǐng)、避免死鎖等概念，并體會(huì)和了解死鎖和避免死鎖的具體實(shí)施方法。通過對(duì)這個(gè)算法的設(shè)計(jì),讓學(xué)生能夠?qū)局R(shí)有更深的理解,在操作和其它方面有更高的提升,同時(shí)對(duì)程序設(shè)計(jì)的水平也有所提高。

二、課設(shè)要求

設(shè)計(jì)一個(gè)n個(gè)并發(fā)進(jìn)程共享m個(gè)系統(tǒng)資源的程序?qū)崿F(xiàn)銀行家算法。要求包含： 1）、簡單的選擇界面。

2）、前系統(tǒng)資源的占用和剩余情況。

3）、為進(jìn)程分配資源，如果進(jìn)程要求的資源大于系統(tǒng)剩余的資源，不與分配并且提示分配不成功。

4）、撤銷作業(yè)，釋放資源。

三、課設(shè)設(shè)備、環(huán)境

奔騰以上計(jì)算機(jī)，裝有Turbo C 2.0軟件

四、課設(shè)方法及步驟

1、設(shè)計(jì)方法：

根據(jù)設(shè)計(jì)任務(wù)書的要求，畫出程序設(shè)計(jì)流程圖，確定程序的功能，把整個(gè)程序根據(jù)功能 要求分解為各個(gè)子程序，利用TC語言分編寫程序代碼，然后進(jìn)行上機(jī)調(diào)試、修改、進(jìn)行連接，測試，寫出設(shè)計(jì)總結(jié)報(bào)告。

2、設(shè)計(jì)步驟：

1）、充分了解各項(xiàng)設(shè)計(jì)要求。深入理解多道程序系統(tǒng)中，進(jìn)程并發(fā)執(zhí)行的資源分配問題，和系統(tǒng)安全狀態(tài)的概念。了解資源在進(jìn)程并發(fā)執(zhí)行中的資源分配策略并體會(huì)和掌握銀行家算法的具體實(shí)現(xiàn)。

2）、按要求對(duì)進(jìn)程調(diào)度程序進(jìn)行分解，根據(jù)功能將其分解成多個(gè)子模塊。

3）、模塊程序流程圖及各功能子模塊程序流程圖，要求條理清楚、簡單明了、功能完備。4）、根據(jù)流程圖編制主程序代碼及子程序代碼。要求程序設(shè)計(jì)結(jié)構(gòu)清晰，簡潔，便于修改和調(diào)試。

5）、上述設(shè)計(jì)要求一人單獨(dú)進(jìn)行，獨(dú)立完成設(shè)計(jì)。6）、設(shè)計(jì)完成后，上機(jī)進(jìn)行運(yùn)行調(diào)試。

7）、程序運(yùn)行成功，然后進(jìn)行某些功能測試，選擇有實(shí)用性、特殊性的數(shù)據(jù)進(jìn)行錄入調(diào)

試，使設(shè)計(jì)進(jìn)一步得到改進(jìn)并完善。

8）、打印出程序運(yùn)行結(jié)果，并對(duì)結(jié)果進(jìn)行分析，驗(yàn)證程序設(shè)計(jì)的正確性。9）、設(shè)計(jì)報(bào)告書。

3、算法描述

設(shè)Request[i] 是進(jìn)程Pi的請(qǐng)求向量，如果Requesti[j]=K,表示進(jìn)程Pi需要K個(gè)Rj類型的資源，當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下面步驟進(jìn)行檢查：

1）、如果Requesti[j]<=Need[i,j]，便轉(zhuǎn)向步驟2；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù) 已超過它所宣布的最大值。

2）、如果Requesti[j]<=Available[j],便轉(zhuǎn)向步驟3；否則，表示尚無足夠資源，Pi須等待。

3）、系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：

Available[j]:=Available[j]-Requesti[j];Allocation[i,j]:=Allocation[i,j]+Requesti[j];Need[i,j]:=Need[i,j]-Requesti[j];

4）、系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才 正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來 的資源分配狀態(tài)，讓進(jìn)程Pi等待。

4、數(shù)據(jù)結(jié)構(gòu)

銀行家算法中的數(shù)據(jù)結(jié)構(gòu)：

1）、可利用資源向量Available。這是一個(gè)含有n個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。如果Available[j]=K,則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。

2）、最大需求矩陣Max。這是一個(gè)m*n的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Max[i,j]=K,則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。3）、分配矩陣Allocation。這也是一個(gè)m*n的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocation[i,j]=K,則表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。

4）、需求矩陣Need。這也是一個(gè)n*m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Need[i,j]=K,則表示進(jìn)程i還需要Rj類資源K個(gè)，方能完成其任務(wù)。

5）、工作數(shù)組Work.。這是一個(gè)含有n個(gè)元素的數(shù)組，它代表可以提供分配的資源數(shù)，初始值是Available中的數(shù)值，隨著資源的回收，它的值也會(huì)改變，公式是 6

《操作系統(tǒng)》/《操作系統(tǒng)課程設(shè)計(jì)》課設(shè)指導(dǎo)書

Work[i]=Work[i]+Allocation[i]。

課設(shè)項(xiàng)目4 存儲(chǔ)管理程序設(shè)計(jì)

一、目的

存儲(chǔ)管理的主要功能之一是合理地分配空間。請(qǐng)求頁式管理是一種常用的虛擬存儲(chǔ)管理技術(shù)。本次設(shè)計(jì)的目的是通過請(qǐng)求頁式存儲(chǔ)管理中頁面置換算法模擬設(shè)計(jì)，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，掌握請(qǐng)求頁式管理的頁面置換算法。

二、課設(shè)要求

設(shè)計(jì)一個(gè)請(qǐng)求頁式存儲(chǔ)管理方案。并編寫模擬程序?qū)崿F(xiàn)之。要求包含： 1．過隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列，共320條指令。其地址按下述原則生成： ①50%的指令是順序執(zhí)行的；

②25%的指令是均勻分布在前地址部分； ③25%的指令是均勻分布在后地址部分； #具體的實(shí)施方法是：

A.在[0，319]的指令地址之間隨機(jī)選區(qū)一起點(diǎn)M;B.順序執(zhí)行一條指令，即執(zhí)行地址為M+1的指令；

C.在前地址[0，M+1]中隨機(jī)選取一條指令并執(zhí)行，該指令的地址為M’;D.順序執(zhí)行一條指令，其地址為M’+1；

E.在后地址[M’+2，319]中隨機(jī)選取一條指令并執(zhí)行； F.重復(fù)A—E，直到執(zhí)行320次指令。2．指令序列變換成頁地址流

設(shè)：（1）頁面大小為1K；

（2）用戶內(nèi)存容量為4頁到32頁；（3）用戶虛存容量為32K。

在用戶虛存中，按每K存放10條指令排列虛存地址，即320條指令在虛存中的存放方式為：

第0條—第9條指令為第0頁（對(duì)應(yīng)虛存地址為[0，9]）；

第10條—第19條指令為第1頁（對(duì)應(yīng)虛存地址為[10，19]）；

。。。。。。。。。。。

第310條—第319條指令為第31頁（對(duì)應(yīng)虛存地址為[310，319]）； 按以上方式，用戶指令可組成32頁。

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

《操作系統(tǒng)》/《操作系統(tǒng)課程設(shè)計(jì)》課設(shè)指導(dǎo)書

A.FIFO先進(jìn)先出的算法 B.LRR最近最少使用算法

C.OPT最佳淘汰算法（先淘汰最不常用的頁地址）D.LFR最少訪問頁面算法 E.NUR最近最不經(jīng)常使用算法

三、課設(shè)設(shè)備、環(huán)境

奔騰以上計(jì)算機(jī)，裝有Turbo C 2.0軟件

四、課設(shè)方法及步驟

1、設(shè)計(jì)方法：

根據(jù)設(shè)計(jì)任務(wù)書的要求，畫出程序設(shè)計(jì)流程圖，確定程序的功能，把整個(gè)程序根據(jù)功能要求分解為各個(gè)子程序，利用TC語言分編寫程序代碼，然后進(jìn)行上機(jī)調(diào)試、修改、進(jìn)行連接，測試，寫出設(shè)計(jì)總結(jié)報(bào)告。

2、設(shè)計(jì)步驟：

1）、充分了解各項(xiàng)設(shè)計(jì)要求。深入理解有關(guān)頁表、頁面置換的概念，并體會(huì)和了解先進(jìn)先出頁面置換算法、先來先服務(wù)算法的具體實(shí)施辦法。

2）、按要求對(duì)存儲(chǔ)管理程序進(jìn)行分解，根據(jù)功能將其分解成多個(gè)子模塊。

3）、建立主控模塊程序流程圖及各功能子模塊程序流程圖，要求條理清楚、簡單明了、功能完備。

4）、根據(jù)流程圖編制主程序代碼及子程序代碼。要求程序設(shè)計(jì)結(jié)構(gòu)清晰，簡潔，便于修改和調(diào)試。

5）、上述設(shè)計(jì)要求一人單獨(dú)進(jìn)行，獨(dú)立完成設(shè)計(jì)。6）、設(shè)計(jì)完成后，上機(jī)進(jìn)行運(yùn)行調(diào)試。

7）、程序運(yùn)行成功，然后進(jìn)行某些功能測試，選擇有實(shí)用性、特殊性的數(shù)據(jù)進(jìn)行錄入調(diào)試，使設(shè)計(jì)進(jìn)一步得到改進(jìn)并完善。

8）、打印出程序運(yùn)行結(jié)果，并對(duì)結(jié)果進(jìn)行分析，驗(yàn)證程序設(shè)計(jì)的正確性。9）、寫出課程設(shè)計(jì)報(bào)告書。

課設(shè)項(xiàng)目5 文件系統(tǒng)程序設(shè)計(jì)

一、目的

本設(shè)計(jì)要求用C語言編寫和調(diào)試一個(gè)簡單的文件系統(tǒng)，模擬文件管理的工作過程。本次課程設(shè)計(jì)的目的是通過一個(gè)簡單多用戶文件系統(tǒng)的設(shè)計(jì)，加深理解文件系統(tǒng)的內(nèi)部功能和內(nèi)部實(shí)現(xiàn)。

二、課設(shè)要求

要求設(shè)計(jì)一個(gè) n個(gè)用戶的文件系統(tǒng)，每次用戶可保存m個(gè)文件，用戶在一次運(yùn)行中只能打開一個(gè)文件，對(duì)文件必須設(shè)置保護(hù)措施，且至少有Create、delete、open、close、read、write等命令。要求包含：

1）設(shè)計(jì)一個(gè)10個(gè)用戶的文件系統(tǒng)，每次用戶可保存10個(gè)文件，一次運(yùn)行用戶可以打開5個(gè)文件。

2）程序采用二級(jí)文件目錄（即設(shè)置主目錄[MFD]）和用戶文件目錄（UED）。另外，為打開文件設(shè)置了運(yùn)行文件目錄（AFD）。

3）為了便于實(shí)現(xiàn)，對(duì)文件的讀寫作了簡化，在執(zhí)行讀寫命令時(shí)，只需改讀寫指針，并不進(jìn)行實(shí)際的讀寫操作。

4）可以實(shí)現(xiàn)下列幾條命令

LOGIN 用戶登陸 DIR 列文件目錄 CREATE 創(chuàng)建文件 DELETE 刪除文件 OPEN 打開文件 CLOSE 關(guān)閉文件 READ 讀文件 WRITE 寫文件

5）因系統(tǒng)小，文件目錄的檢索可使用簡單的線性搜索。

三、課設(shè)設(shè)備、環(huán)境

奔騰以上計(jì)算機(jī)，裝有Turbo C 2.0軟件

四、課設(shè)方法及步驟

1、設(shè)計(jì)方法：

《操作系統(tǒng)》/《操作系統(tǒng)課程設(shè)計(jì)》課設(shè)指導(dǎo)書

根據(jù)設(shè)計(jì)任務(wù)書的要求，畫出程序設(shè)計(jì)流程圖，確定程序的功能，把整個(gè)程序根據(jù)功能要求分解為各個(gè)子程序，利用TC語言分編寫程序代碼，然后進(jìn)行上機(jī)調(diào)試、修改、進(jìn)行連接，測試，寫出設(shè)計(jì)總結(jié)報(bào)告。

2、設(shè)計(jì)步驟：

1）、充分了解各項(xiàng)設(shè)計(jì)要求。深入理解有關(guān)文件控制塊、目錄的概念，并體會(huì)和了解目錄管理的具體實(shí)施辦法。

2）、按要求對(duì)進(jìn)程調(diào)度程序進(jìn)行分解，根據(jù)功能將其分解成多個(gè)子模塊。

3）、建立主控模塊程序流程圖及各功能子模塊程序流程圖，要求條理清楚、簡單明了、功能完備。

4）、根據(jù)流程圖編制主程序代碼及子程序代碼。要求程序設(shè)計(jì)結(jié)構(gòu)清晰，簡潔，便于修改和調(diào)試。

5）、上述設(shè)計(jì)要求一人單獨(dú)進(jìn)行，獨(dú)立完成設(shè)計(jì)。6）、設(shè)計(jì)完成后，上機(jī)進(jìn)行運(yùn)行調(diào)試。

7）、程序運(yùn)行成功，然后進(jìn)行某些功能測試，選擇有實(shí)用性、特殊性的數(shù)據(jù)進(jìn)行錄入調(diào)試，使設(shè)計(jì)進(jìn)一步得到改進(jìn)并完善。

8）、打印出程序運(yùn)行結(jié)果，并對(duì)結(jié)果進(jìn)行分析，驗(yàn)證程序設(shè)計(jì)的正確性。9）、寫出課程設(shè)計(jì)報(bào)告書。

第二篇：操作系統(tǒng)課程設(shè)計(jì)

操作系統(tǒng)課程設(shè)計(jì)

注意事項(xiàng)：

0.請(qǐng)每位同學(xué)必須按時(shí)提交課程設(shè)計(jì)報(bào)告（包括電子版和紙質(zhì)版），算入期末成績

1.在三個(gè)題目中選擇一個(gè)

2.如果選擇題目

（一）進(jìn)程調(diào)度算法，要求實(shí)現(xiàn)其中2個(gè)以上（包括2個(gè)）進(jìn)程調(diào)度算法 3.如果選擇題目

（二）銀行家算法，要求能夠判斷系統(tǒng)的安全狀態(tài)

4.如果選擇題目

（三）頁面調(diào)度算法，要求實(shí)現(xiàn)其中2個(gè)以上（包含2個(gè)）進(jìn)程調(diào)度算法 5.報(bào)告應(yīng)包含算法分析、實(shí)驗(yàn)截圖、核心算法源代碼，請(qǐng)各位同學(xué)認(rèn)真對(duì)待，獨(dú)立完成 6.提交要求：電子版（包括實(shí)驗(yàn)程序）請(qǐng)發(fā)至ropeal@163.com，紙質(zhì)版請(qǐng)班長收齊，由班長統(tǒng)一在課堂上提交（并提交未交人員名單），截止時(shí)間第16周周三(2014.1.31)7.格式要求：

7.1 A4紙10頁左右

7.2 封面請(qǐng)注明班級(jí)、姓名、學(xué)號(hào)、所選題目

7.3 電子版發(fā)送時(shí)，請(qǐng)打包成一個(gè)文件，將文件名設(shè)置為：學(xué)號(hào)+姓名+題目名稱（如20130000張三進(jìn)程調(diào)度算法課程設(shè)計(jì)），郵件主題同文件名

一、進(jìn)程調(diào)度算法

1.1 實(shí)驗(yàn)?zāi)康模? a、設(shè)計(jì)進(jìn)程控制塊PCB表結(jié)構(gòu)，模擬實(shí)現(xiàn)進(jìn)程調(diào)度算法：FIFO，靜態(tài)優(yōu)先級(jí)調(diào)度，時(shí)間片輪轉(zhuǎn)調(diào)度，多級(jí)反饋隊(duì)列調(diào)度。（實(shí)現(xiàn)其中之二）。* b、建立進(jìn)程就緒隊(duì)列。對(duì)不同算法編制入鏈子程序。c、編寫一進(jìn)程調(diào)度程序模擬程序。模擬程序只對(duì)PCB進(jìn)行相應(yīng)的調(diào)度模擬操作，不需要實(shí)際程序。* 由用戶輸入進(jìn)程名和進(jìn)程長度，然后按照短進(jìn)程優(yōu)先的進(jìn)程處理順序給出進(jìn)程的排序。

1.2 實(shí)驗(yàn)原理 調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。1.2.1 先來先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法

1.先來先服務(wù)調(diào)度算法。先來先服務(wù)（FCFS）調(diào)度算法是一種最簡單的調(diào)度算法，該算法既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。FCFS算法比較有利于長作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）。由此可知，本算法適合于CPU繁忙型作業(yè)，而不利于I/O繁忙型的作業(yè)（進(jìn)程）。

2.短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法。短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法（SJ/PF）是指對(duì)短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法，該算法既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。但其對(duì)長作業(yè)不利；不能保證緊迫性作業(yè)（進(jìn)程）被及時(shí)處理；作業(yè)的長短只是被估算出來的。1.2.2 高優(yōu)先權(quán)優(yōu)先調(diào)度算法

1.優(yōu)先權(quán)調(diào)度算法的類型。為了照顧緊迫性作業(yè)，使之進(jìn)入系統(tǒng)后便獲得優(yōu)先處理，引入了最高優(yōu)先權(quán)優(yōu)先（FPF）調(diào)度算法。此算法常被用在批處理系統(tǒng)中，作為作業(yè)調(diào)度算法，也作為多種操作系統(tǒng)中的進(jìn)程調(diào)度，還可以用于實(shí)時(shí)系統(tǒng)中。當(dāng)其用于作業(yè)調(diào)度，將后備隊(duì)列中若干個(gè)優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。當(dāng)其用于進(jìn)程調(diào)度時(shí)，把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程，此時(shí)，又可以進(jìn)一步把該算法分成以下兩種： 1)非搶占式優(yōu)先權(quán)算法

2)搶占式優(yōu)先權(quán)調(diào)度算法（高性能計(jì)算機(jī)操作系統(tǒng)）

2.優(yōu)先權(quán)類型。對(duì)于最高優(yōu)先權(quán)優(yōu)先調(diào)度算法，其核心在于：它是使用靜態(tài)優(yōu)先權(quán)還是動(dòng)態(tài)優(yōu)先權(quán)，以及如何確定進(jìn)程的優(yōu)先權(quán)。3．高響應(yīng)比優(yōu)先調(diào)度算法

為了彌補(bǔ)短作業(yè)優(yōu)先算法的不足，我們引入動(dòng)態(tài)優(yōu)先權(quán)，使作業(yè)的優(yōu)先等級(jí)隨著等待時(shí)間的增加而以速率a提高。該優(yōu)先權(quán)變化規(guī)律可描述為：優(yōu)先權(quán)=（等待時(shí)間+要求服務(wù)時(shí)間）/要求服務(wù)時(shí)間；即 =（響應(yīng)時(shí)間）/要求服務(wù)時(shí)間 1.2.3 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法

1.時(shí)間片輪轉(zhuǎn)法。時(shí)間片輪轉(zhuǎn)法一般用于進(jìn)程調(diào)度，每次調(diào)度，把CPU分配隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)記時(shí)器發(fā)出一個(gè)時(shí)鐘中斷請(qǐng)求，該進(jìn)程被停止，并被送往就緒隊(duì)列末尾；依次循環(huán)。2.多級(jí)反饋隊(duì)列調(diào)度算法 多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法，不必事先知道各種進(jìn)程所需要執(zhí)行的時(shí)間，它是目前被公認(rèn)的一種較好的進(jìn)程調(diào)度算法。其實(shí)施過程如下：

1)設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)。在優(yōu)先權(quán)越高的隊(duì)列中，為每個(gè)進(jìn)程所規(guī)定的執(zhí)行時(shí)間片就越小。

2)當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先放入第一隊(duì)列的末尾，按FCFS原則排隊(duì)等候調(diào)度。如果他能在一個(gè)時(shí)間片中完成，便可撤離；如果未完成，就轉(zhuǎn)入第二隊(duì)列的末尾，在同樣等待調(diào)度?? 如此下去，當(dāng)一個(gè)長作業(yè)（進(jìn)程）從第一隊(duì)列依次將到第n隊(duì)列（最后隊(duì)列）后，便按第n隊(duì)列時(shí)間片輪轉(zhuǎn)運(yùn)行。3)僅當(dāng)?shù)谝魂?duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行；僅當(dāng)?shù)?到第（i-1）隊(duì)列空時(shí)，才會(huì)調(diào)度第i隊(duì)列中的進(jìn)程運(yùn)行，并執(zhí)行相應(yīng)的時(shí)間片輪轉(zhuǎn)。4)如果處理機(jī)正在處理第i隊(duì)列中某進(jìn)程，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊(duì)列，則此新隊(duì)列搶占正在運(yùn)行的處理機(jī)，并把正在運(yùn)行的進(jìn)程放在第i隊(duì)列的隊(duì)尾。

1．3 實(shí)驗(yàn)要求

a、使用模塊化設(shè)計(jì)思想來設(shè)計(jì)； b、給出算法的流程圖或偽碼說明。c、學(xué)生可按照自身?xiàng)l件，隨意選擇采用的算法，（例如：采用冒泡法編寫程序，實(shí)現(xiàn)短進(jìn)程優(yōu)先調(diào)度的算法）

d、進(jìn)程調(diào)度程序模擬程序只對(duì)PCB進(jìn)行相應(yīng)的調(diào)度模擬操作，不需要實(shí)際程序。

1.4 算法簡析 a、每個(gè)進(jìn)程可有三個(gè)狀態(tài)，并假設(shè)初始狀態(tài)為就緒狀態(tài)。b、為了便于處理，程序中的某進(jìn)程運(yùn)行時(shí)間以時(shí)間片為單位計(jì)算。各進(jìn)程的優(yōu)先數(shù)或輪轉(zhuǎn)時(shí)間數(shù)以及進(jìn)程需運(yùn)行的時(shí)間片數(shù)的初始值均由用戶給定。c、在優(yōu)先數(shù)算法中，優(yōu)先數(shù)可以先取值為（50-該進(jìn)程所需時(shí)間），進(jìn)程每執(zhí)行一次，優(yōu)先數(shù)減3，CPU時(shí)間片數(shù)（CPUtime）加1，* 進(jìn)程還需要的時(shí)間片數(shù)（needtime）減1。在時(shí)間片輪轉(zhuǎn)算法中，采用固定時(shí)間片

（即：每執(zhí)行一次進(jìn)程，該進(jìn)程的執(zhí)行時(shí)間片數(shù)為已執(zhí)行了2個(gè)單位），這時(shí)，CPU時(shí)間片（CPUtime）數(shù)加2，* 進(jìn)程還需要的時(shí)間片數(shù)（needtime）減2，并排列到就緒隊(duì)列的尾上。

d、對(duì)于遇到優(yōu)先數(shù)一致的情況，采用FIFO策略解決。

二、銀行家算法

2.1 概述

2.1.1 設(shè)計(jì)目的1、了解多道程序系統(tǒng)中，多個(gè)進(jìn)程并發(fā)執(zhí)行的資源分配。

2、掌握死鎖的產(chǎn)生的原因、產(chǎn)生死鎖的必要條件和處理死鎖的基本方法。

3、掌握預(yù)防死鎖的方法，系統(tǒng)安全狀態(tài)的基本概念。

4、掌握銀行家算法，了解資源在進(jìn)程并發(fā)執(zhí)行中的資源分配策略。

5、理解死鎖避免在當(dāng)前計(jì)算機(jī)系統(tǒng)不常使用的原因

2.2 關(guān)于死鎖

2.2.1 死鎖概念：

在多道程序系統(tǒng)中，雖可借助于多個(gè)進(jìn)程的并發(fā)執(zhí)行，來改善系統(tǒng)的資源利用率，提高系統(tǒng)的吞吐量，但可能發(fā)生一種危險(xiǎn)━━死鎖。所謂死鎖(Deadlock),是指多個(gè)進(jìn)程在運(yùn)行中因爭奪資源而造成的一種僵局(Deadly_Embrace),當(dāng)進(jìn)程處于這種僵持狀態(tài)時(shí)，若無外力作用，它們都將無法再向前推進(jìn)。一組進(jìn)程中，每個(gè)進(jìn)程都無限等待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而永遠(yuǎn)無法得到的資源，這種現(xiàn)象稱為進(jìn)程死鎖，這一組進(jìn)程就稱為死鎖進(jìn)程。

2.2.2 關(guān)于死鎖的一些結(jié)論：

參與死鎖的進(jìn)程最少是兩個(gè)（兩個(gè)以上進(jìn)程才會(huì)出現(xiàn)死鎖）

參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有資源

參與死鎖的所有進(jìn)程都在等待資源

參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集

注：如果死鎖發(fā)生，會(huì)浪費(fèi)大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。

2.2.3 資源分類：

永久性資源： 可以被多個(gè)進(jìn)程多次使用（可再用資源），分為：可搶占資源與不可搶占資源

臨時(shí)性資源：只可使用一次的資源；如信號(hào)量,中斷信號(hào)，同步信號(hào)等（可消耗性資源）

“申請(qǐng)--分配--使用--釋放”模式

2.2.4 產(chǎn)生死鎖的四個(gè)必要條件：

1、互斥使用（資源獨(dú)占）

一個(gè)資源每次只能給一個(gè)進(jìn)程使用

2、不可強(qiáng)占（不可剝奪）

資源申請(qǐng)者不能強(qiáng)行的從資源占有者手中奪取資源，資源只能由占有者自愿釋放

3、請(qǐng)求和保持（部分分配，占有申請(qǐng)）

一個(gè)進(jìn)程在申請(qǐng)新的資源的同時(shí)保持對(duì)原有資源的占有（只有這樣才是動(dòng)態(tài)申請(qǐng)，動(dòng)態(tài)分配）

4、循環(huán)等待

存在一個(gè)進(jìn)程等待隊(duì)列

{P1 , P2 , ? , Pn}，其中P1等待P2占有的資源，P2等待P3占有的資源，?，Pn等待P1占有的資源，形成一個(gè)進(jìn)程等待環(huán)路

2.2.5 死鎖的解決方案 1 產(chǎn)生死鎖的例子

申請(qǐng)不同類型資源產(chǎn)生死鎖

P1： ?

申請(qǐng)打印機(jī) 申請(qǐng)掃描儀 使用

釋放打印機(jī) 釋放掃描儀 ? P2： ?

申請(qǐng)掃描儀 申請(qǐng)打印機(jī) 使用

釋放打印機(jī) 釋放掃描儀 ?

申請(qǐng)同類資源產(chǎn)生死鎖（如內(nèi)存）

設(shè)有資源R，R有m個(gè)分配單位，由n個(gè)進(jìn)程P1,P2,?,Pn（n > m）共享。假設(shè)每個(gè)進(jìn)程對(duì)R的申請(qǐng)和釋放符合下列原則： * 一次只能申請(qǐng)一個(gè)單位 * 滿足總申請(qǐng)后才能使用 * 使用完后一次性釋放

m=2，n=3 資源分配不當(dāng)導(dǎo)致死鎖產(chǎn)生

2死鎖預(yù)防: 定義:在系統(tǒng)設(shè)計(jì)時(shí)確定資源分配算法，保證不發(fā)生死鎖。具體的做法是破壞產(chǎn)生死鎖的四個(gè)必要條件之一

①破壞“不可剝奪”條件

在允許進(jìn)程動(dòng)態(tài)申請(qǐng)資源前提下規(guī)定，一個(gè)進(jìn)程在申請(qǐng)新的資源不能立即得到滿足而變?yōu)榈却隣顟B(tài)之前，必須釋放已占有的全部資源，若需要再重新申請(qǐng) ②破壞“請(qǐng)求和保持”條件

要求每個(gè)進(jìn)程在運(yùn)行前必須一次性申請(qǐng)它所要求的所有資源，且僅當(dāng)該進(jìn)程所要資源均可滿足時(shí)才給予一次性分配 ③破壞“循環(huán)等待”條件 采用資源有序分配法：

把系統(tǒng)中所有資源編號(hào)，進(jìn)程在申請(qǐng)資源時(shí)必須嚴(yán)格按資源編號(hào)的遞增次序進(jìn)行，否則操作系統(tǒng)不予分配。

2.2.6 安全狀態(tài)與不安全狀態(tài)

安全狀態(tài)： 如果存在一個(gè)由系統(tǒng)中所有進(jìn)程構(gòu)成的安全序列P1，?Pn，則系統(tǒng)處于安全狀態(tài)。一個(gè)進(jìn)程序列{P1，?，Pn}是安全的，如果對(duì)于每一個(gè)進(jìn)程Pi(1≤i≤n），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj(j < i)當(dāng)前占有資源量之和，系統(tǒng)處于安全狀態(tài)(安全狀態(tài)一定是沒有死鎖發(fā)生的)。

不安全狀態(tài):不存在一個(gè)安全序列，不安全狀態(tài)一定導(dǎo)致死鎖。

2.3 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

1.可利用資源向量矩陣AVAILABLE。這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。如果AVAILABLE [j]= K，則表示系統(tǒng)中現(xiàn)有R類資源K個(gè)

2.最大需求矩陣MAX。這是一個(gè)n*m的矩陣，用以表示每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果MAX [i,j]=K，則表示進(jìn)程i需要R類資源的數(shù)目為K。

3.分配矩陣ALLOCATION。這也是一個(gè)n*m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果ALLOCATION [i,j]=K，則表示進(jìn)程i當(dāng)前已分得R類資源的數(shù)目為K。

4.需求矩陣NEED。這也是一個(gè)n*m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果NEED [i,j]=K，則表示進(jìn)程i還需要R類資源K個(gè)，才能完成其任務(wù)。上述矩陣存在下述關(guān)系：

NEED [i,j]= MAX[i,j]﹣ ALLOCATION[i,j]

2.4 算法的實(shí)現(xiàn) 2.4.1 初始化 由用戶輸入數(shù)據(jù)，分別對(duì)可利用資源向量矩陣AVAILABLE、最大需求矩陣MAX、分配矩陣ALLOCATION、需求矩陣NEED賦值。2.4.2 銀行家算法

在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可以避免發(fā)生死鎖。

銀行家算法的基本思想是分配資源之前,判斷系統(tǒng)是否是安全的;若是,才分配。它是最具有代表性的避免死鎖的算法。

設(shè)進(jìn)程cusneed提出請(qǐng)求REQUEST [i]，則銀行家算法按如下規(guī)則進(jìn)行判斷。(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，則轉(zhuǎn)(2)；否則，出錯(cuò)。

(2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，則轉(zhuǎn)(3)；否則，出錯(cuò)。(3)系統(tǒng)試探分配資源，修改相關(guān)數(shù)據(jù)： AVAILABLE[i]-=REQUEST[cusneed][i];ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];NEED[cusneed][i]-=REQUEST[cusneed][i];(4)系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險(xiǎn)性分配作廢，系統(tǒng)恢復(fù)原狀，進(jìn)程等待。

2.4.3 安全性檢查算法

(1)設(shè)置兩個(gè)工作向量Work=AVAILABLE;FINISH(2)從進(jìn)程集合中找到一個(gè)滿足下述條件的進(jìn)程，F(xiàn)INISH==false;NEED<=Work;如找到，執(zhí)行(3)；否則，執(zhí)行(4)(3)設(shè)進(jìn)程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。

Work+=ALLOCATION;Finish=true;GOTO 2(4)如所有的進(jìn)程Finish= true，則表示安全；否則系統(tǒng)不安全。

三、頁面調(diào)度算法 3.1 實(shí)驗(yàn)名稱

頁式虛擬存儲(chǔ)管理：頁面調(diào)度算法 3.2 實(shí)驗(yàn)?zāi)康?/p>

頁式虛擬存儲(chǔ)器實(shí)現(xiàn)的一個(gè)難點(diǎn)是設(shè)計(jì)頁面調(diào)度（置換）算法，即將新頁面調(diào)入內(nèi)存時(shí)，如果內(nèi)存中所有的物理頁都已經(jīng)分配出去，就要按某種策略來廢棄某個(gè)頁面，將其所占據(jù)的物理頁釋放出來，供新頁面使用。本實(shí)驗(yàn)的目的是通過編程實(shí)現(xiàn)幾種常見的頁面調(diào)度（置換）算法，加深讀者對(duì)頁面思想的理解。3.3 實(shí)驗(yàn)原理

頁面調(diào)度算法

目前有許多頁面調(diào)度算法，本實(shí)驗(yàn)主要涉及先進(jìn)先出調(diào)度算法、最近最少調(diào)度算法、最近最不常用調(diào)度算法。本實(shí)驗(yàn)使用頁面調(diào)度算法時(shí)作如下假設(shè)，進(jìn)程在創(chuàng)建時(shí)由操作系統(tǒng)為之分配一個(gè)固定數(shù)目物理頁，執(zhí)行過程中物理頁的數(shù)目和位置不會(huì)改變。也即進(jìn)程進(jìn)行頁面調(diào)度時(shí)只能在分到的幾個(gè)物理頁中進(jìn)行。

下面對(duì)各調(diào)度算法的思想作一介紹。

<1> 先進(jìn)先出調(diào)度算法

先進(jìn)先出調(diào)度算法根據(jù)頁面進(jìn)入內(nèi)存的時(shí)間先后選擇淘汰頁面，先進(jìn)入內(nèi)存的頁面先淘汰，后進(jìn)入內(nèi)存的后淘汰。本算法實(shí)現(xiàn)時(shí)需要將頁面按進(jìn)入內(nèi)存的時(shí)間先后組成一個(gè)隊(duì)列，每次調(diào)度隊(duì)首頁面予以淘汰。

<2>最近最少調(diào)度算法

先進(jìn)先出調(diào)度算法沒有考慮頁面的使用情況，大多數(shù)情況下性能不佳。根據(jù)程序執(zhí)行的局部性特點(diǎn)，程序一旦訪問了某些代碼和數(shù)據(jù)，則在一段時(shí)間內(nèi)會(huì)經(jīng)常訪問他們，因此最近最少用調(diào)度在選擇淘汰頁面時(shí)會(huì)考慮頁面最近的使用，總是選擇在最近一段時(shí)間以來最少使用的頁面予以淘汰。算法實(shí)現(xiàn)時(shí)需要為每個(gè)頁面設(shè)置數(shù)據(jù)結(jié)構(gòu)記錄頁面自上次訪問以來所經(jīng)歷的時(shí)間。

<3>最近最不常用調(diào)度算法

由于程序設(shè)計(jì)中經(jīng)常使用循環(huán)結(jié)構(gòu)，根據(jù)程序執(zhí)行的局部性特點(diǎn)，可以設(shè)想在一段時(shí)間內(nèi)經(jīng)常被訪問的代碼和數(shù)據(jù)在將來也會(huì)經(jīng)常被訪問，顯然這樣的頁面不應(yīng)該被淘汰。最近最不常用調(diào)度算法總是根據(jù)一段時(shí)間內(nèi)頁面的訪問次數(shù)來選擇淘汰頁面，每次淘汰訪問次數(shù)最少的頁面。算法實(shí)現(xiàn)時(shí)需要為每個(gè)頁面設(shè)置計(jì)數(shù)器，記錄訪問次數(shù)。計(jì)數(shù)器由硬件或操作系統(tǒng)自動(dòng)定時(shí)清零。

缺頁調(diào)度次數(shù)和缺頁中斷率、缺頁置換率計(jì)算

缺頁中斷次數(shù)是缺頁時(shí)發(fā)出缺頁中斷的次數(shù)。

缺頁中斷率=缺頁中斷次數(shù)/總的頁面引用次數(shù)*100%

缺頁調(diào)度次數(shù)是調(diào)入新頁時(shí)需要進(jìn)行頁面調(diào)度的次數(shù)

缺頁置換率=缺頁調(diào)度次數(shù)/總的頁面引用次數(shù)*100% 3.4 實(shí)驗(yàn)內(nèi)容

（1）設(shè)計(jì)程序?qū)崿F(xiàn)以上三種頁面調(diào)度算法，要求：

①.可以選擇頁面調(diào)度算法類型；

②.可以為進(jìn)程設(shè)置分到物理頁的數(shù)目，設(shè)置進(jìn)程的頁面引用情況，可以從鍵盤輸入頁面序列，也可從文件中讀??；

③.隨時(shí)計(jì)算當(dāng)前的頁面調(diào)度次數(shù)的缺頁中斷率；

④.使用敲鍵盤或響應(yīng)WM-TIMER的形式模仿時(shí)間的流逝；

⑤.以直觀的的形式將程序的執(zhí)行情況顯示在計(jì)算機(jī)屏幕上；

⑥.存盤及讀盤功能，可以隨時(shí)將數(shù)據(jù)存入磁盤文件，供以后重復(fù)實(shí)驗(yàn)時(shí)使用。

（2）假定進(jìn)程分配到3個(gè)物理塊，對(duì)于下面的頁面引用序列：（test.txt）

7-0-1-2-0-3-0-4-2-3-0-3-2-1-2-0-1-7-0-1

請(qǐng)分別用先進(jìn)和先出調(diào)度算法，最近最少用調(diào)度算法，最近最不常用調(diào)度算法計(jì)算缺頁中斷次數(shù)，缺頁中斷率和缺頁調(diào)度次數(shù)、缺頁置換率。

再假定進(jìn)程分配到4、5個(gè)物理塊，重復(fù)本實(shí)驗(yàn)。

（3）假定進(jìn)程分配到3個(gè)物理塊，對(duì)于下面的頁面引用序列：（test2.txt）

4-3-2-1-4-3-5-4-3-2-1-5-0-7-3-8-9-0-2-1-4-7-3-9

請(qǐng)分別用先進(jìn)先出調(diào)度算法、最近最少用調(diào)度算法，最近最不常用調(diào)度算法計(jì)算缺頁中斷次數(shù)，缺頁中斷率和缺頁調(diào)度次數(shù)、缺頁置換率。

再假定進(jìn)程分配到4、5個(gè)物理塊，重復(fù)本實(shí)驗(yàn)。

（4）假定進(jìn)程分配到3個(gè)物理塊，使用程序的動(dòng)態(tài)頁面序列生成算法，生成一個(gè)頁面序列，將此序列存入磁盤文件。再從磁盤文件讀入該序列，用程序分別計(jì)算三種算法下的缺頁中斷次數(shù)、缺頁中斷率和缺頁調(diào)度次數(shù)、缺頁置換率。

第三篇：操作系統(tǒng)課程設(shè)計(jì)

湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

（操作系統(tǒng)課程設(shè)計(jì)）

連續(xù)動(dòng)態(tài)分區(qū)內(nèi)存

管理模擬實(shí)現(xiàn)

學(xué)生姓名： 韓 慧 學(xué)生學(xué)號(hào)： 031140312 班 級(jí)： 031140--3 0311401、02、03、04班制

二〇一三年十二月 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

目錄

《操作系統(tǒng)》課程設(shè)計(jì).......................................................1 引言......................................................................3 課程設(shè)計(jì)目的和內(nèi)容......................................................3 需求分析.........................................................................3 概要設(shè)計(jì)...................................................................3 開發(fā)環(huán)境........................................................................4 系統(tǒng)分析設(shè)計(jì).....................................................................4 有關(guān)了解內(nèi)存管理的相關(guān)理論..................................................4 內(nèi)存管理概念........................................................................4 內(nèi)存管理的必要性..............................................................4 內(nèi)存的物理組織.............................................................4 什么是虛擬內(nèi)存.................................................................5 連續(xù)動(dòng)態(tài)分區(qū)內(nèi)存管理方式...................................................5 單一連續(xù)分配（單個(gè)分區(qū))...................................................5

固定分區(qū)存儲(chǔ)管理...............................................................5 可變分區(qū)存儲(chǔ)管理（動(dòng)態(tài)分區(qū)）..............................................5 可重定位分區(qū)存儲(chǔ)管理........................................................5 問題描述和分析....................................................................6 程序流程圖........................................................................6 數(shù)據(jù)結(jié)構(gòu)體分析..................................................................8 主要程序代碼分析...............................................................9 分析并實(shí)現(xiàn)四種內(nèi)存分配算法.................................................11 最先適應(yīng)算.....................................................................11 下次適應(yīng)分配算法..........................................................13 最優(yōu)適應(yīng)算法...............................................................16 最壞適應(yīng)算法...............................................................18 回收內(nèi)存算法................................................................20 調(diào)試與操作說明.................................................................22

初始界面.......................................................................22 模擬內(nèi)存分配...............................................................23

已分配分區(qū)說明表面............................................................24 空閑區(qū)說明表界面.............................................................24 回收內(nèi)存界面.....................................................................25 重新申請(qǐng)內(nèi)存界面..........................................................26.總結(jié)與體會(huì)......................................................................28 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

參考文獻(xiàn).........................................................................28

引言

操作系統(tǒng)是最重要的系統(tǒng)軟件，同時(shí)也是最活躍的學(xué)科之一。我們通過操作系統(tǒng)可以理解計(jì)算機(jī)系統(tǒng)的資源如何組織，操作系統(tǒng)如何有效地管理這些系統(tǒng)資源，用戶如何通過操作系統(tǒng)與計(jì)算機(jī)系統(tǒng)打交道。

存儲(chǔ)器是計(jì)算機(jī)系統(tǒng)的重要組成部分，近年來，存儲(chǔ)器容量雖然一直在不斷擴(kuò)大，但仍不能滿足現(xiàn)代軟件發(fā)展的需要，因此，存儲(chǔ)器仍然是一種寶貴而又緊俏的資源。如何對(duì)它加以有效的管理，不僅直接影響到存儲(chǔ)器的利用率，而且還對(duì)系統(tǒng)性能有重大影響。而動(dòng)態(tài)分區(qū)分配屬于連續(xù)分配的一種方式，它至今仍在內(nèi)存分配方式中占有一席之地。

課程設(shè)計(jì)目的和內(nèi)容：

理解內(nèi)存管理的相關(guān)理論，掌握連續(xù)動(dòng)態(tài)分區(qū)內(nèi)存管理的理論；通過對(duì)實(shí)際問題的編程實(shí)現(xiàn)，獲得實(shí)際應(yīng)用和編程能力。

編寫程序?qū)崿F(xiàn)連續(xù)動(dòng)態(tài)分區(qū)內(nèi)存管理方式，該程序管理一塊虛擬內(nèi)存，實(shí)現(xiàn)內(nèi)存分配和回收功能。分析并實(shí)現(xiàn)四種內(nèi)存分配算法，即最先適應(yīng)算法，下次最先適應(yīng)算法，最優(yōu)適應(yīng)算法，最壞適應(yīng)算法。內(nèi)存分配算法和回收算法的實(shí)現(xiàn)。

需求分析

動(dòng)態(tài)分區(qū)分配是根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)地為之分配內(nèi)存空間。在實(shí)現(xiàn)動(dòng)態(tài)分區(qū)分配時(shí)，將涉及到分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)、分區(qū)分配算法和分區(qū)的分配和回收操作這樣三個(gè)問題。常用的數(shù)據(jù)結(jié)構(gòu)有動(dòng)態(tài)分區(qū)表和動(dòng)態(tài)分區(qū)鏈。在對(duì)數(shù)據(jù)結(jié)構(gòu)有一定掌握程度的情況下設(shè)計(jì)合理的數(shù)據(jù)結(jié)構(gòu)來描述存儲(chǔ)空間，實(shí)現(xiàn)分區(qū)存儲(chǔ)管理的內(nèi)存分配功能，應(yīng)該選擇最合適的適應(yīng)算法（首次適應(yīng)算法，最佳適應(yīng)算法，最后適應(yīng)算法，最壞適應(yīng)算法），在動(dòng)態(tài)分區(qū)存儲(chǔ)管理方式中主要實(shí)現(xiàn)內(nèi)存分配和內(nèi)存回收算法，在這些存儲(chǔ)管理中間必然會(huì)有碎片的產(chǎn)生，當(dāng)碎片產(chǎn)生時(shí)，進(jìn)行碎片的拼接等相關(guān)的內(nèi)容

概要設(shè)計(jì)

本程序采用機(jī)構(gòu)化模塊化的設(shè)計(jì)方法，共分為四大模塊。⑴最先適應(yīng)算法實(shí)現(xiàn)

從空閑分區(qū)表的第一個(gè)表目起查找該表，把最先能夠滿足要求的空閑區(qū)分配給作業(yè)，這種方法目的在于減少查找時(shí)間。為適應(yīng)這種算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按地址由低到高進(jìn)行排序。該算法優(yōu)先使用低址部分空閑區(qū)，在低址空間造成許多小的空閑區(qū)，在高地址空間保留大的空閑區(qū)。⑵下次適應(yīng)分配算法實(shí)現(xiàn) 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

該算法是最先適應(yīng)算法的變種。在分配內(nèi)存空間時(shí)，不再每次從表頭（鏈?zhǔn)祝╅_始查找，而是從上次找到空閑區(qū)的下一個(gè)空閑開始查找，直到找到第一個(gè)能滿足要求的的空閑區(qū)為止，并從中劃出一塊與請(qǐng)求大小相等的內(nèi)存空間分配給作業(yè)。該算法能使內(nèi)存中的空閑區(qū)分布得較均勻。⑶最優(yōu)適應(yīng)算法實(shí)現(xiàn)

它從全部空閑區(qū)中找出能滿足作業(yè)要求的、且大小最小的空閑分區(qū)，這種方法能使碎片盡量小。為適應(yīng)此算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按從小到大進(jìn)行排序，自表頭開始查找到第一個(gè)滿足要求的自由分區(qū)分配。⑷最壞算法實(shí)現(xiàn)

最壞適應(yīng)分配算法要掃描整個(gè)空閑分區(qū)或鏈表，總是挑選一個(gè)最大的空閑分區(qū)分割給作業(yè)使用。該算法要求將所有的空閑分區(qū)按其容量從大到小的順序形成一空閑分區(qū)鏈，查找時(shí)只要看第一個(gè)分區(qū)能否滿足作業(yè)要求。

開發(fā)環(huán)境：

win7 下 VC++6.0 系統(tǒng)分析設(shè)計(jì)：

相關(guān)算法原理，算法流程圖，涉及的數(shù)據(jù)結(jié)構(gòu)內(nèi)容都相應(yīng)包含在各章節(jié)中

有關(guān)了解內(nèi)存管理的相關(guān)理論

內(nèi)存管理概念：

內(nèi)存管理，是指軟件運(yùn)行時(shí)對(duì)計(jì)算機(jī)內(nèi)存資源的分配和使用的技術(shù)。其最主要的目的是如何高效，快速的分配，并且在適當(dāng)?shù)臅r(shí)候釋放和回收內(nèi)存資源。內(nèi)存不是預(yù)先劃分好的，而是在系統(tǒng)運(yùn)行的過程中建立分區(qū).當(dāng)作業(yè)裝入主存時(shí)，根據(jù)作業(yè)所需要的主存容量查看是否有足夠的主存空間，若有則按需要分割一個(gè)分區(qū)給該作業(yè)；否則令該作業(yè)等待.分區(qū)長度不固定分區(qū)個(gè)數(shù)不固定。這種存儲(chǔ)管理的方法克服了固定分區(qū)嚴(yán)重浪費(fèi)主存的問題，提高了主存資源的利用率。

內(nèi)存管理的必要性：

內(nèi)存管理對(duì)于編寫出高效率的 Windows 程序是非常重要的，這是因?yàn)閃indows 是多任務(wù)系統(tǒng)，它的內(nèi)存管理和單任務(wù)的 DOS 相比有很大的差異。DOS是單任務(wù)操作系統(tǒng)，應(yīng)用程序分配到內(nèi)存后，如果它不主動(dòng)釋放，系統(tǒng)是不會(huì)對(duì)它作任何改變的；但 Windows 卻不然，它在同一時(shí)刻可能有多個(gè)應(yīng)用程序共享內(nèi)存，有時(shí)為了使某個(gè)任務(wù)更好地執(zhí)行，Windows 系統(tǒng)可能會(huì)對(duì)其它任務(wù)分配的內(nèi)存進(jìn)行移動(dòng)，甚至刪除。因此，我們?cè)?Windows 應(yīng)用程序中使用內(nèi)存時(shí)，要遵循Windows 內(nèi)存管理的一些約定，以盡量提高 Windows 內(nèi)存的利用率。湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

1.3 內(nèi)存的物理組織：

物理地址：

把內(nèi)存分成若干個(gè)大小相等的存儲(chǔ)單元，每個(gè)存儲(chǔ)單元占 8 位，稱作字節(jié)（byte）。每個(gè)單元給一個(gè)編號(hào)，這個(gè)編號(hào)稱為物理地址（內(nèi)存地址、絕對(duì)地址、實(shí)地址）。

二、物理地址空間： 物理地址的集合稱為物理地址空間（主存地址空間），它是一個(gè)一維空間。

什么是虛擬內(nèi)存：

虛擬內(nèi)存是內(nèi)存管理技術(shù)的一個(gè)極其實(shí)用的創(chuàng)新。它是一段程序（由操作系統(tǒng)調(diào)度），持續(xù)監(jiān)控著所有物理內(nèi)存中的代碼段、數(shù)據(jù)段，并保證他們?cè)谶\(yùn)行中的效率以及可靠性，對(duì)于每個(gè)用戶層（user-level）的進(jìn)程分配一段虛擬內(nèi)存空間。當(dāng)進(jìn)程建立時(shí)，不需要在物理內(nèi)存件之間搬移數(shù)據(jù)，數(shù)據(jù)儲(chǔ)存于磁盤內(nèi)的虛擬內(nèi)存空間，也不需要為該進(jìn)程去配置主內(nèi)存空間，只有當(dāng)該進(jìn)程被被調(diào)用的時(shí)候才會(huì)被加載到主內(nèi)存。

連續(xù)動(dòng)態(tài)分區(qū)內(nèi)存管理方式的實(shí)現(xiàn)

在早期的操作系統(tǒng)中，主存分配廣泛采用連續(xù)分配方式。連續(xù)分配方式，是指為一個(gè)用戶程序分配一個(gè)連續(xù)的內(nèi)存空間，該連續(xù)內(nèi)存空間指的的是物理內(nèi)存。下面介紹連續(xù)分配的四種方式。

單一連續(xù)分配（單個(gè)分區(qū)）

最簡單的存儲(chǔ)管理方式，用于多道程序設(shè)計(jì)技術(shù)之前。內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)，系統(tǒng)區(qū)由操作系統(tǒng)使用。用戶區(qū)作為一個(gè)連續(xù)的分區(qū)分配給一個(gè)作業(yè)。分區(qū)存儲(chǔ)管理是滿足多道程序設(shè)計(jì)的最簡單的一種存儲(chǔ)管理方法，它允許多 4個(gè)用戶程序同時(shí)存在系統(tǒng)內(nèi)存中，即共享內(nèi)存空間。按分區(qū)劃分方式可分為固定分區(qū)和可變分區(qū)。

固定分區(qū)存儲(chǔ)管理

把內(nèi)存的用戶區(qū)預(yù)先劃分成多個(gè)分區(qū)，每個(gè)分區(qū)大小可以相同，也可以不同。（分區(qū)的劃分由計(jì)算機(jī)的操作員或者由操作系統(tǒng)給出，并給出主存分配表）分區(qū)個(gè)數(shù)固定，分區(qū)的大小固定。一個(gè)分區(qū)中可裝入一個(gè)作業(yè)，作業(yè)執(zhí)行過程中不會(huì)改變存放區(qū)域。早期的 IBM 的 OS/MFT（具有固定任務(wù)數(shù)的多道程序系統(tǒng)）采用了這種固定分區(qū)的方法。

可變分區(qū)存儲(chǔ)管理（動(dòng)態(tài)分區(qū)）

內(nèi)存不是預(yù)先劃分好的，而是在系統(tǒng)運(yùn)行的過程中建立分區(qū).當(dāng)作業(yè)裝入主存時(shí)，根據(jù)作業(yè)所需要的主存容量查看是否有足夠的主存空間，若有則按需要分割一個(gè)分區(qū)給該作業(yè)；否則令該作業(yè)等待。分區(qū)長度不固定分區(qū)個(gè)數(shù)不固定。這種存儲(chǔ)管理的方法克服了固定分區(qū)嚴(yán)重浪費(fèi)主存的問題，提高了主存資源的利用率。ＩＢＭ操作系統(tǒng)ＯＳ／ＭＶＴ采用可變分區(qū)存儲(chǔ)管理。湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

可重定位分區(qū)存儲(chǔ)管理

解決碎片問題的一種簡單方法是采用可重定位分區(qū)分配.。其中心思想是，把不同程序，且在內(nèi)存中地址不連續(xù)的想法讓他們連續(xù)。

例：內(nèi)存中現(xiàn)有 3 個(gè)空閑區(qū)，現(xiàn)有一作業(yè)到達(dá)，要求獲得 30k 內(nèi)存空間，沒有分區(qū)滿足容量要求，若想把作業(yè)裝入，可將內(nèi)存中所有作業(yè)進(jìn)行移動(dòng)，這樣把原來分散的空閑區(qū)匯集成一個(gè)大的空閑區(qū)。將內(nèi)存中的作業(yè)進(jìn)行移動(dòng)使它們連接在一起把原來分散的多個(gè)小分區(qū)拼接成一個(gè)大的空閑區(qū).這個(gè)過程稱為”緊湊”或”移動(dòng)”。需解決的問題:每次”緊湊”后程序或數(shù)據(jù)裝入的物理地址變化采用動(dòng)態(tài)重定位。

問題描述和分析

系統(tǒng)應(yīng)利用某種分配算法，從空閑分區(qū)鏈表中找到所需大小的分區(qū)，如果空閑分區(qū)大小大于請(qǐng)求分區(qū)大小，則從該分區(qū)中按改請(qǐng)求的大小劃分出一塊內(nèi)存空間大小劃分出一塊內(nèi)存空間分配出去，余下的部分仍留在空閑鏈表中。然后，將分配區(qū)的首址返回給調(diào)用者。

當(dāng)進(jìn)程運(yùn)行完畢師范內(nèi)存時(shí)，系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)中找到相應(yīng)的插入點(diǎn)，此時(shí)可能出現(xiàn)以下四種情況之一：

⑴該空閑區(qū)的上下兩相鄰分區(qū)都是空閑區(qū)：將三個(gè)空閑區(qū)合并為一個(gè)空閑區(qū)。新空閑區(qū)的起始地址為上空閑區(qū)的起始地址，大小為三個(gè)空閑區(qū)之和。空閑區(qū)合并后，取消可用表或自由鏈中下空閑區(qū)的表目項(xiàng)或鏈指針，修改上空閑區(qū)的對(duì)應(yīng)項(xiàng)。

⑵該空閑區(qū)的上相鄰區(qū)是空閑區(qū)：將釋放區(qū)與上空閑區(qū)合并為一個(gè)空閑區(qū)，其起始地址為上空閑區(qū)的起始地址，大小為上空閑區(qū)與釋放區(qū)之和。合并后，修改上空閑區(qū)對(duì)應(yīng)的可用表的表目項(xiàng)或自由鏈指針。

⑶該空閑區(qū)的下相鄰區(qū)是空閑區(qū)：將釋放區(qū)與下空閑區(qū)合并，并將釋放區(qū)的起始地址作為合并區(qū)的起始地址。合并區(qū)的長度為釋放區(qū)與下空閑區(qū)之和。同理，合并后修改可用表或自由鏈中相應(yīng)的表目項(xiàng)或鏈指針。

⑷兩相鄰區(qū)都不是空閑區(qū)：釋放區(qū)作為一個(gè)新空閑可用區(qū)插入可用表或自由鏈。

程序流程圖

內(nèi)存分配流程圖，如圖

湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

從頭開始查表檢索完否？NY返回分區(qū)大小>所需大小N繼續(xù)檢索下一個(gè)表項(xiàng)Y分區(qū)大小-所需大小<=不可再分割大小N從該分區(qū)中劃出所需大小的新分區(qū)Y將該分區(qū)從鏈中移出將該分區(qū)分配給請(qǐng)求者修改有關(guān)數(shù)據(jù)結(jié)構(gòu)返回

內(nèi)存回收流程圖，如圖

湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

開始判斷空閑區(qū)上下內(nèi)存情況上為空下為空上下都為空上下都不為空將上面的空閑區(qū)合并，并回收將下面的空閑區(qū)合并，并回收將上下的空閑區(qū)合并，并回收直接將其回收結(jié)束 數(shù)據(jù)結(jié)構(gòu)體分析

⑴進(jìn)程屬性結(jié)構(gòu)體 typedef struct readyque { char name[10];int size;}readyque,*readyqueue;⑵空閑鏈表結(jié)構(gòu)體 typedef struct idlyspace { int from;int size;idlyspace * next;}idlyspace,*idly;⑶已分配鏈表結(jié)構(gòu)體 typedef struct busyspace { int from;readyque r;湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

busyspace * next;}busyspace,*busy

主要程序代碼分析

⑴主函數(shù)//代碼請(qǐng)?zhí)砑舆m當(dāng)?shù)淖⑨?。int main(){ Is=(idly)malloc(sizeof(idlyspace));Is->from=0;Is->size=256;Is->next=NULL;Is2=Is;Bs=(busy)malloc(sizeof(busyspace));Bs->next=NULL;int t,t1;printf(“n.......................歡迎來到動(dòng)態(tài)分區(qū)存儲(chǔ)管理系統(tǒng)..................nn”);printf(“...........................請(qǐng)選擇要執(zhí)行的算法:...........................n”);printf(“.........................1.最先適應(yīng)算法

...............................n”);printf(“.........................2.下次適應(yīng)算法............................n”);printf(“..........................3.最優(yōu)適應(yīng)算法

...............................n”);printf(“.........................4.最壞適應(yīng)算法................................n”);printf(“........................................................................n”);printf(“請(qǐng)輸入您的選擇:”);scanf(“%d”,&t);int i;while(i!=5){

printf(“........................................................................n”);

printf(“.........................操作菜單如下：（請(qǐng)選擇）.......................n”);

printf(“..........................1.輸入進(jìn)程分配空間...........................n”);

printf(“.........................2.進(jìn)程撤銷回收空間...........................n”);

printf(“.........................3.輸出所有空閑分區(qū)

..........................n”);

printf(“..........................4.輸出所有已分配分區(qū)..........................n”);

printf(“..........................5.退

出..........................n”);

printf(“........................................................................n”);

scanf(“%d”,&i);

switch(i)

{

case 1:

switch(t)

{

case 1:

t1=FF();湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

break;

case 2:

t1=NF();

break;

case 3:

t1=BF();

break;

case 4:

t1=WF();

break;

default:

printf(“選擇算法錯(cuò)誤n”);

return 1;

}

if(t1)

printf(“分配空間成功n”);

else

printf(“分配空間失敗n”);

break;

case 2:

t1=recover();

if(t1)

printf(“回收成功n”);

else

printf(“回收失敗n”);

break;

case 3:

Isprint();

break;

case 4:

Bsprint();

break;

} } return 0;}

第三章 ：分析并實(shí)現(xiàn)四種內(nèi)存分配算法

最先適應(yīng)算法

空閑區(qū)按地址從小到大的次序排列。

分配：當(dāng)進(jìn)程申請(qǐng)大小為 SIZE 的內(nèi)存時(shí)，系統(tǒng)順序查找空閑區(qū)表（鏈），直到找到容量滿足要求（≥SIZE）的空閑區(qū)為止。從該空閑區(qū)中劃出大小為 SIZE的分區(qū)分配給進(jìn)程，余下的部分仍作為一個(gè)空閑區(qū)，但要修改其首址和大小。湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

優(yōu)點(diǎn)：這種算法是盡可能地利用低地址部分的空閑區(qū)，而盡量地保證高地址 6部分的大空閑區(qū)，有利于大作業(yè)的裝入。

缺點(diǎn):主存低地址和高地址分區(qū)利用不均衡。在低地址部分集中了許多非常小的空閑區(qū)碎片降低了主存的利用率。最先適應(yīng)算法 int FF(){ int t=0;readyque D;printf““請(qǐng)輸入進(jìn)程名:””);scanf““%””,D.name);

printf““輸入進(jìn)程申請(qǐng)空間大小:””);scanf““%””,&D.size);

idly l=Is;int mt=256;busy b=Bs;idly min=NULL;while(l)

//尋找空閑表中大小滿足申請(qǐng)進(jìn)程所需大小并且起址最小的空閑結(jié)點(diǎn)

{

if(D.size<=l->size)

{

if(l->from

{ mt=l->from;min=l;t=1;

}

}

l=l->next;} if(mt!=256)

{

busy j;

j=(busy)malloc(sizeof(busyspace));

//如果找到則為進(jìn)程分配空間

湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

j->from=min->from;

for(int i=0;i<10;i++)

{

j->r.name[i]=D.name[i];

}

j->r.size=D.size;

while(b->next)

{ if(b->next->fromfrom)

b=b->next;else

break;

}

j->next=b->next;

b->next=j;

min->from=min->from+D.size;

min->size=min->size-D.size;} return t;}

下次適應(yīng)分配算法

最先適應(yīng)算法的變種。

總是從空閑區(qū)上次掃描結(jié)束處順序查找空閑區(qū)表（鏈），直到找到第一個(gè)滿足容量要求的空閑區(qū)為止，分割一部分給作業(yè)，剩余部分仍作為空閑區(qū)。下次適應(yīng)分配算法 int NF(){ int t=0;readyque D;printf““請(qǐng)輸入進(jìn)程名:””);scanf““%””,D.name);

湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

printf““輸入進(jìn)程申請(qǐng)空間大小:””);scanf““%””,&D.size);

int mt=256;idly l=Is2;idly min=NULL;busy b=Bs;while(l)//尋找空閑表中大小滿足申請(qǐng)進(jìn)程所需大小并且起址最小的空閑結(jié)點(diǎn)

{

if(D.size<=l->size)

{

if(l->from

{ mt=l->from;min=l;t=1;

}

}

l=l->next;} if(mt!=256)

{

busy j;

j=(busy)malloc(sizeof(busyspace));

j->from=min->from;

for(int i=0;i<10;i++)

{

j->r.name[i]=D.name[i];

}

j->r.size=D.size;

while(b->next)

{ if(b->next->fromfrom)

b=b->next;else

break;

//如果找到則為進(jìn)程分配空間

湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

}

//將申請(qǐng)空間進(jìn)程插入到已分配鏈表中

j->next=b->next;

b->next=j;

//修改相應(yīng)空閑節(jié)點(diǎn)的起址和大小

min->from=min->from+D.size;

min->size=min->size-D.size;

Is2=min->next;

結(jié)點(diǎn)

t=1;

return t;}

l=Is;//l指向空閑表的頭

while(l!=Is2)

{

if(D.size<=l->size)

{

if(l->from

{ mt=l->from;min=l;t=1;

}

}

l=l->next;} if(mt!=256){

busy j;

j=(busy)malloc(sizeof(busyspace));

j->from=min->from;

for(int i=0;i<10;i++)

{

//ls2指向修改結(jié)點(diǎn)的下一個(gè)

//循環(huán)查找 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

j->r.name[i]=D.name[i];

}

j->r.size=D.size;

while(b->next)

{ if(b->next->fromfrom)

b=b->next;else

break;

}

j->next=b->next;

b->next=j;

min->from=min->from+D.size;

min->size=min->size-D.size;

Is2=min->next;

t=1;

return t;} return t;}

最優(yōu)適應(yīng)算法

空閑區(qū)按容量遞增的次序排列。

分配：當(dāng)進(jìn)程申請(qǐng)存儲(chǔ)空間，系統(tǒng)順序查找空閑區(qū)表（鏈），直到找到第一個(gè)滿足容量要求的空閑區(qū)為止。采用最優(yōu)適應(yīng)算法選中的空閑區(qū)是滿足容量要求的最小空閑區(qū)。優(yōu)點(diǎn)：選中的空閑區(qū)是滿足容量要求的最小空閑區(qū)，而不致于毀掉較大的空閑區(qū)。

缺點(diǎn)：空閑區(qū)的大小一般與申請(qǐng)分區(qū)大小不相等，因此將其一分為二，留下來的空閑區(qū)一般情況下是很小的，以致無法使用。隨著時(shí)間的推移，系統(tǒng)中的小空閑區(qū)會(huì)越來越多，從而造成存儲(chǔ)空間的浪費(fèi)。最優(yōu)適應(yīng)算法 int BF(){ int t=0;湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

readyque D;printf““請(qǐng)輸入進(jìn)程名:””);scanf““%””,D.name);

printf““輸入進(jìn)程申請(qǐng)空間大小:””);scanf““%””,&D.size);

idly l=Is;idly min=NULL;int mt=256;busy b=Bs;while(l)//在空閑鏈中尋找第一個(gè)大于所輸入的進(jìn)程大小的空閑塊

{

if(D.size<=l->size)

{

if(l->size

{

mt=l->size;min=l;t=1;

}

}

l=l->next;} if(mt!=256)

{

busy j;

j=(busy)malloc(sizeof(busyspace));空間

j->from=min->from;

//申請(qǐng)分配用于存放進(jìn)程的內(nèi)存

//找到第一個(gè)滿足要求的空閑塊

//將第一個(gè)滿足要求的空閑塊（min）的首地址賦給j

for(int i=0;i<10;i++)

{

j->r.name[i]=D.name[i];16 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

}

j->r.size=D.size;

while(b->next)

//按從小到大的順序查找新進(jìn)程在已分配區(qū)中的位置

{ if(b->next->fromfrom)

b=b->next;else

break;

}

j->next=b->next;

b->next=j;

min->from=min->from+D.size;

min->size=min->size-D.size;

} return t;}

最壞適應(yīng)算法

為了克服最佳適應(yīng)算法把空閑區(qū)切割得太小的缺點(diǎn)，人們提出了一種最壞適應(yīng)算法，即每次分配時(shí)，總是將最大的空閑區(qū)切去一部分分配給請(qǐng)求者，剩余的部分仍是一個(gè)較大的空閑區(qū)。避免了空閑區(qū)越分越小的問題。要求空閑區(qū)按容量遞減的順序排列。

分配：進(jìn)程申請(qǐng)存儲(chǔ)區(qū)時(shí)，檢查空閑區(qū)表（鏈）的第一個(gè)空閑區(qū)的大小是否滿足要求，若不滿足則令進(jìn)程等待；若滿足則從該空閑區(qū)中分配一部分存儲(chǔ)區(qū)給用戶，剩下的部分仍作為空閑區(qū)。最壞適應(yīng)算法 int WF(){ int t=0;readyque D;printf““請(qǐng)輸入進(jìn)程名:””);scanf““%””,D.name);

printf““輸入進(jìn)程申請(qǐng)空間大小:””);

//將所輸入的進(jìn)程插入進(jìn)程鏈

//改變?cè)摽臻e塊的起始地址 //改變?cè)摽臻e塊的剩余大小 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

scanf““%””,&D.size);

//輸入進(jìn)程申請(qǐng)的空間大小

idly l=Is;//l指向空閑鏈表ls頭

idly min=NULL;int mt=0;busy b=Bs;

//b指向已分配鏈表Bs頭

//找到空閑分區(qū)中大小滿足進(jìn)程的請(qǐng)求且尺寸最大的結(jié)點(diǎn)

while(l){

if(D.size<=l->size)//判斷進(jìn)程所申請(qǐng)的大小是否小于空閑區(qū)的各結(jié)點(diǎn)大小

{

if(l->size>mt)

{ mt=l->size;min=l;//min指向空閑區(qū)中尺寸最大的結(jié)點(diǎn)

t=1;

}

}

l=l->next;} if(mt!=0)點(diǎn)

{

busy j;

j=(busy)malloc(sizeof(busyspace));

j->from=min->from;

for(int i=0;i<10;i++)

{

j->r.name[i]=D.name[i];

}

j->r.size=D.size;

//判斷是否找到了空閑區(qū)的滿足結(jié)

//l指向空閑鏈表下一個(gè)結(jié)點(diǎn)

湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

while(b->next)置

//尋找插入到已分配鏈表中的位

{ if(b->next->fromfrom)

b=b->next;else

break;

}

//把此進(jìn)程結(jié)點(diǎn)j插入到已分配鏈表中

j->next=b->next;

b->next=j;

//修改空閑鏈表的相應(yīng)結(jié)點(diǎn)的參數(shù)

min->from=min->from+D.size;

min->size=min->size-D.size;} return t;}

可變分區(qū)的回收

當(dāng)某個(gè)進(jìn)程釋放某存儲(chǔ)區(qū)時(shí)，系統(tǒng)首先檢查釋放區(qū)是否與系統(tǒng)中的空閑區(qū)相鄰若相鄰則把釋放區(qū)合并到相鄰的空閑區(qū)去，否則把釋放區(qū)作為一個(gè)空閑區(qū)插入到空閑表的適當(dāng)位置。

釋放區(qū)與空閑區(qū)相鄰的四種情況。

（1）釋放區(qū)與前空閑區(qū)相鄰：把釋放區(qū)與前空閑區(qū)合并到一個(gè)空閑區(qū)。其首址仍為前空閑區(qū)首址，大小為釋放區(qū)大小與空閑區(qū)大小之和。

（2）釋放區(qū)與后空閑區(qū)相鄰：則把釋放區(qū)合并到后空閑區(qū)，其首地址為釋放區(qū)首地址，大小為二者之和。

（3）釋放區(qū)與前后兩空閑區(qū)相鄰：這三個(gè)區(qū)合為一個(gè)空閑區(qū)，首地址為前空閑區(qū)首址，大小為這三個(gè)空閑區(qū)之和，并取消后空閑區(qū)表目。

（4）釋放區(qū)不與任何空閑區(qū)相鄰：將釋放區(qū)作為一個(gè)空閑區(qū)，將其大小和首址插入到空閑區(qū)表的適當(dāng)位置。

湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

回收內(nèi)存算法

int recover(){ readyque D;printf““請(qǐng)輸入想要回收的進(jìn)程名””);

scanf““%””,D.name);

busy b=Bs;idly l=Is;while(b->next)鏈表中

{

bool yo=1;

for(int i=0;i<10;i++)

{

if(b->next->r.name[i]==D.name[i])yo=yo*1;

else yo=0;

}

//如果在已分配鏈表中則釋放該結(jié)點(diǎn)所占空間

if(yo)

{

int t=b->next->from;

int ts=b->next->r.size;

//查找輸入的進(jìn)程名是否在已分配湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

while(l)

{ if(l->from>t+ts)不鄰接

{ idly tl;tl=(idly)malloc(sizeof(idlyspace));tl->from=t;tl->size=ts;tl->next=l;Is=tl;break;} if(l->from==t+ts)

l->from=t;

l->size=l->size+ts;

busy tb=b->next;

b->next=b->next->next;

free(tb);

return 1;}

if(l->from+l->size

idly tl;

tl=(idly)malloc(sizeof(idlyspace));

tl->from=t;

tl->size=ts;

tl->next=l->next;

l->next=tl;

break;}

else if(l->from+l->size==t)

//所回收進(jìn)程與空閑結(jié)點(diǎn)上鄰接 {

//所回收進(jìn)程與空閑結(jié)點(diǎn)上下都不鄰接

//所回收進(jìn)程與空閑結(jié)點(diǎn)下鄰接 {

//所回收進(jìn)程與空閑結(jié)點(diǎn)上下都 21 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

l->size=l->size+ts;

if(l->from+l->size==l->next->from)接

{

l->size=l->size+l->next->size;

idly tm=l->next;

l->next=l->next->next;

freI);

}

br

l=l->next;

}

//從已分配鏈表中釋放所回收進(jìn)程

busy tb=b->next;

b->next=b->next->next;

free(tb);

return 1;

}

b=b->next;} printf(“沒找到這”進(jìn)程n”);return 0;}

//所回收進(jìn)程與空閑結(jié)點(diǎn)上下都鄰調(diào)試與操作說明

初始界面

程序初始界面，有四個(gè)塊選擇，選擇要執(zhí)行的算法，調(diào)試以最壞算法為例，如圖

湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

選擇最壞適應(yīng)算法，如圖

模擬內(nèi)存分配

給進(jìn)程a分配內(nèi)存20，如圖

湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

已分配分區(qū)說明表界面

同理，給進(jìn)程b分配內(nèi)存30，給進(jìn)程c分配內(nèi)存40，給進(jìn)程d分配50，給進(jìn)程e分配60，如圖

空閑分區(qū)說明表界面 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

查看空閑分區(qū)，如圖

回收內(nèi)存界面

回收進(jìn)程b和d所占內(nèi)存，如圖

已分配分區(qū)說明表和空閑分區(qū)說明表 如圖 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

重新申請(qǐng)內(nèi)存界面

再為新進(jìn)程i分配內(nèi)存30，如圖

湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

根據(jù)最壞適應(yīng)算法結(jié)合圖所示可知，該算法將會(huì)從空閑分區(qū)表中選擇一塊最大的內(nèi)存空間分配給進(jìn)程i，從圖也可看出該模擬算法實(shí)現(xiàn)了最壞適應(yīng)算法

湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

總結(jié)與體會(huì)

本次做的課題是動(dòng)態(tài)分區(qū)分配算法實(shí)現(xiàn)，此次課程設(shè)計(jì)成功實(shí)現(xiàn)了內(nèi)存分配和內(nèi)存回收，內(nèi)存分配中包含了四種算法，分別是首次適應(yīng)算法，循環(huán)首次適應(yīng)算法，最佳適應(yīng)算法和最壞適應(yīng)算法。經(jīng)編碼調(diào)試，表明該程序模塊是有效可行的。

通過這門課程的學(xué)習(xí)讓我充分了解了內(nèi)存管理的機(jī)制實(shí)現(xiàn)，從而更深一步的的對(duì)計(jì)算機(jī)

有了很多了解，這對(duì)于以后我們的研究和學(xué)習(xí)計(jì)算機(jī)系統(tǒng)起到了很重要的作用。

對(duì)于本次論文制作，自己的編程能力有所提高，對(duì)操作系統(tǒng)內(nèi)存分配，存儲(chǔ)空間的回收都有全新的認(rèn)識(shí)。

在這次操作系統(tǒng)課程設(shè)計(jì)中，我使用了c++編寫系統(tǒng)軟件，對(duì)os中可變分區(qū)存儲(chǔ)管理有了深刻的理解，但是過程中遇到了很多困難，一邊做一邊學(xué)，對(duì)c++有了比較多的理解。

實(shí)驗(yàn)中遇到很多問題，浪費(fèi)了很多時(shí)間，總而言之是自己學(xué)習(xí)還不夠好，不扎實(shí)，希望在以后學(xué)習(xí)中加以改善，學(xué)到更多知識(shí)。

參考文獻(xiàn)

【1】 湯子瀛，哲鳳屏，湯小丹.計(jì)算機(jī)操作系統(tǒng).西安：西安電子科技大學(xué)出版社，2001.。湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)

【2】 任愛華.操作系統(tǒng)實(shí)用教程.北京：清華大學(xué)出版社，2001。

第四篇：操作系統(tǒng)課程設(shè)計(jì)

長春理工大學(xué) 軟件學(xué)院 0813111班 27號(hào)

姓名：丁為勝 一． 概述

1、課程設(shè)計(jì)目的及任務(wù)課程設(shè)計(jì)地點(diǎn)及要求

每個(gè)學(xué)生一臺(tái)微機(jī)，需要安裝windows98或windows2000操作系統(tǒng)，配備VC、VB、java或C編程語言，每個(gè)學(xué)生上機(jī)時(shí)間不少于24個(gè)小時(shí)。

操作系統(tǒng)是計(jì)算機(jī)專業(yè)的核心專業(yè)課，“操作系統(tǒng)課程設(shè)計(jì)”是理解和鞏固操作系統(tǒng)基本理論、原理和方法的重要的實(shí)踐環(huán)節(jié)。

操作系統(tǒng)課程主要講述的內(nèi)容是多道操作系統(tǒng)的原理與技術(shù)，與其它計(jì)算機(jī)原理、編譯原理、匯編語言、計(jì)算機(jī)網(wǎng)絡(luò)、程序設(shè)計(jì)等專業(yè)課程關(guān)系十分密切。本課程設(shè)計(jì)的目的綜合應(yīng)用學(xué)生所學(xué)知識(shí)，建立系統(tǒng)和完整的計(jì)算機(jī)系統(tǒng)概念，理解和鞏固操作系統(tǒng)基本理論、原理和方法，掌握操作系統(tǒng)基本理論與管理方式。在算法基礎(chǔ)上，解決實(shí)際的管理功能的問題，提高學(xué)生實(shí)際應(yīng)用、編程的能力。

主要任務(wù)是實(shí)現(xiàn)操作系統(tǒng)和相關(guān)系統(tǒng)軟件的設(shè)計(jì)，其中涉及進(jìn)程創(chuàng)建，同步，進(jìn)程間的通信，存儲(chǔ)管理，文件系統(tǒng)等操作系統(tǒng)概念。

2.課程設(shè)計(jì)地點(diǎn)及要求

每個(gè)學(xué)生一臺(tái)微機(jī)，需要安裝windows98或windows2000操作系統(tǒng)，配備VC、VB、java或C編程語言，每個(gè)學(xué)生上機(jī)時(shí)間不少于24個(gè)小時(shí)。

3.課程設(shè)計(jì)的內(nèi)容

設(shè)計(jì)二： 設(shè)計(jì)任務(wù)：

掌握進(jìn)程的管道通訊機(jī)制和信號(hào)量同步互斥機(jī)制。1． 進(jìn)程的管道通訊

編制一個(gè)程序，程序中創(chuàng)建一個(gè)子進(jìn)程。然后父子進(jìn)程各自獨(dú)立運(yùn)行，父進(jìn)程不斷地在標(biāo)準(zhǔn)輸入設(shè)備上讀入小寫字母，寫入管道。子進(jìn)程不斷地從管道中讀取字符，轉(zhuǎn)換為大寫字母后輸出到標(biāo)準(zhǔn)輸出設(shè)備上。當(dāng)讀到x時(shí)，結(jié)束。

2． 信號(hào)量實(shí)現(xiàn)的同步互斥機(jī)制

編制一個(gè)程序，程序中創(chuàng)建5個(gè)子進(jìn)程，代表五位哲學(xué)家，然后父進(jìn)程結(jié)束。使用信號(hào)量機(jī)制解決哲學(xué)家進(jìn)餐問題。當(dāng)哲學(xué)家進(jìn)餐時(shí)，屏幕輸出：

[進(jìn)程號(hào)] eating!當(dāng)哲學(xué)家思考時(shí)，屏幕輸出： [進(jìn)程號(hào)] thinging!相關(guān)的系統(tǒng)調(diào)用和函數(shù)：pipe();write();read();semget();sepop();semctl();要求：查找并閱讀上述系統(tǒng)調(diào)用的相關(guān)資料，將上述相關(guān)的函數(shù)封裝為P()、V()操作，使用你封裝的P()、V()操作實(shí)現(xiàn)5位哲學(xué)家的同步和互斥。

二． 設(shè)計(jì)的基本概念和原理

1.進(jìn)程的管道通訊

管道（Pipe）實(shí)際是用于進(jìn)程間通信的一段共享內(nèi)存，創(chuàng)建管道的進(jìn)程稱為管道服務(wù)器，連接到一個(gè)管道的進(jìn)程為管道客戶機(jī)。命名管道（Named Pipes）是在管道服務(wù)器和一臺(tái)或多臺(tái)管道客戶機(jī)之間進(jìn)行單向或雙向通信的一種命名的管道。一個(gè)命名管道的所有實(shí)例共享同一個(gè)管道名，但是每一個(gè)實(shí)例均擁有獨(dú)立的緩存與句柄，并且為客戶——服務(wù)通信提供有一個(gè)分離的管道。實(shí)例的使用保證了多個(gè)管道客戶能夠在同一時(shí)間使用同一個(gè)命名管道。

2.信號(hào)量實(shí)現(xiàn)的同步互斥機(jī)制

規(guī)定奇數(shù)號(hào)的哲學(xué)家先拿起他左邊的筷子,然后再去拿他右邊的筷子;而偶數(shù)號(hào) 的哲學(xué)家則相反.按此規(guī)定,將是1,2號(hào)哲學(xué)家競爭1號(hào)筷子,3,4號(hào)哲學(xué)家競爭3號(hào)筷子.即 五個(gè)哲學(xué)家都競爭奇數(shù)號(hào)筷子,獲得后,再去競爭偶數(shù)號(hào)筷子,最后總會(huì)有一個(gè)哲學(xué)家能獲 得兩支筷子而進(jìn)餐。而申請(qǐng)不到的哲學(xué)家進(jìn)入阻塞等待隊(duì)列，根FIFO原則，則先申請(qǐng)的哲 學(xué)家會(huì)較先可以吃飯，因此不會(huì)出現(xiàn)餓死的哲學(xué)家。

三． 總體設(shè)計(jì)

1.實(shí)現(xiàn)的方法和主要技術(shù)路線

1.無名管道

無名管道用于具有親緣關(guān)系的父子進(jìn)程，子子進(jìn)程之間的通訊。它的實(shí)現(xiàn)函數(shù)有 int pipe(int fd[2]);

//fd[2] 為描述符數(shù)組，包含一個(gè)讀描述符與一個(gè)寫描述符，在使用管道通信時(shí)，關(guān)閉某些不需要的讀或?qū)懨枋龇⑵饐蜗虻淖x或?qū)懝艿溃缓笥胷ead 和write 像操作文件一樣去操作它即可。

如圖便是進(jìn)程1 到進(jìn)程2 的一個(gè)讀管道。

分別在父進(jìn)程和父子進(jìn)程里向管道寫數(shù)據(jù)，然后在子進(jìn)程和子子進(jìn)程里讀數(shù)據(jù)。2.哲學(xué)家進(jìn)餐偽碼：

semaphore chopstick[5]={1，1，1，1，1};void philosopher(int i){

while(true){

think();

if(i%2 == 0)//偶數(shù)哲學(xué)家，先右后左。

{

wait(chopstick[ i + 1 ] mod 5);wait(chopstick[ i]);eat();

signal(chopstick[ i + 1 ] mod 5);signal(chopstick[ i]);}

Else //奇數(shù)哲學(xué)家，先左后右。

{

wait(chopstick[ i]);

wait(chopstick[ i + 1 ] mod 5);eat();

signal(chopstick[ i]);

signal(chopstick[ i + 1 ] mod 5);} } 四． 詳細(xì)設(shè)計(jì)

進(jìn)程的管道通信代碼： import java.io.IOException;import java.io.PipedReader;

public class ReceiverThread1 extends Thread { PipedReader pipedReader;

public ReceiverThread1(SenderThread1 sender)throws IOException

{

pipedReader=new PipedReader(sender.getPipedWriter());

}

public void run()

{ char[] ch=new char[100];StringBuffer sb=null;String str=null;int i=0;try {

while((i=pipedReader.read(ch))!=-1)

{

sb=new StringBuffer();

for(int j=0;j

{

sb.append(ch[j]);

}

str=sb.toString();

System.out.println(“子進(jìn)程讀取的字符為：”+str.toUpperCase());

if(!str.endsWith(“x”))

{

System.out.print(“父進(jìn)程讀入字符為：”);

}else if(str.endsWith(“x”))

{

System.out.println(“結(jié)束無法再次輸入字符”);

}

} } catch(IOException e){

e.printStackTrace();}finally{

try {

pipedReader.close();

} catch(IOException e){

e.printStackTrace();

} }

}

}

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.io.PipedWriter;

public class SenderThread1 extends Thread { PipedWriter pipedWriter;

public SenderThread1(){

pipedWriter=new PipedWriter();}

public PipedWriter getPipedWriter(){

return pipedWriter;}

public void run()

{ BufferedReader ir=new BufferedReader(new InputStreamReader(System.in));char[] ch=new char[100];StringBuffer sb=null;String str=null;int i=0;System.out.print(“父進(jìn)程讀入字符為：”);try {

while((i=ir.read(ch))!=-1)

{

sb=new StringBuffer();

for(int j=0;j

{

if(ch[j]>='a' && ch[j]<='z')

{

sb.append(ch[j]);

if(ch[j]=='x')

{

break;

}

}

}

str=sb.toString();

pipedWriter.write(str);

if(str.startsWith(“x”)||str.endsWith(“x”))

{

break;

// this.stop();

}

}

} catch(IOException e){

e.printStackTrace();}finally{

try {

ir.close();

pipedWriter.close();

} catch(IOException e){

e.printStackTrace();

}

}

} }

public class ThreadComm1 { public static void main(String[] args)throws Exception{ SenderThread1 sender=new SenderThread1();ReceiverThread1 receiver=new ReceiverThread1(sender);sender.start();receiver.start();} } 哲學(xué)家進(jìn)餐問題代碼： #include “stdafx.h” using namespace std;bool chop[100];//定義筷子 class ph { protected: bool * left,* right;//哲學(xué)家的左右手指向的筷子

int eattime;//哲學(xué)家的吃飯時(shí)間 public: bool check()//用于檢查哲學(xué)家左右手的筷子是不是被占用

{

if(*left && *right)

return true;

else

return false;} void eat(int ineattime)//哲學(xué)家開始進(jìn)餐

{

eattime=ineattime;

*left=false;

*right=false;} bool finish()//檢查哲學(xué)家是否完成進(jìn)餐

{

if(eattime>0)//沒完成的話剩余時(shí)間減少

{

eattime--;

if(eattime==0)//完成的話歸還筷子

{

*left=true;

*right=true;

return true;

}

else

return false;

}

else

return false;} void init(int num,int max)//初始化哲學(xué)家，指定他們使用的筷子

{

eattime=0;

left=&chop[num];

if(num

right=&chop[num+1];

else

right=&chop[0];} };void main(){ system(“title 哲學(xué)家進(jìn)餐問題”);int in,i,temp,time,j=1;queue Q;ph P[100];

for(int i=0;i<5;i++){

chop[i]=1;

} for(int i=0;i<5;i++){ P[i].init(i,5);} cout<<“輸入哲學(xué)家進(jìn)餐隊(duì)列：”<>in;if(in==0)

break;else

if(in>5)

{

cout<<“一共只有”<<5<<“個(gè)人！”<

}

else

{

Q.push(in-1);

} } cout<<“每個(gè)人吃飯時(shí)間：”<>time;system(“CLS”);system(“color 0a”);while(!Q.empty()){ temp=Q.front();Q.pop();if(P[temp].check()){

P[temp].eat(time);

cout<

if(temp+2>5)

cout<<1<

else

cout<

Q.push(temp);} for(i=0;i<5;i++)

{

if(P[i].finish())

cout<

}

//Q.push(-1);

for(i=0;i

{

temp=Q.front();

Q.pop();

//if(temp!=-1)

{

cout<

Q.push(temp);

}

//else

{

// Q.pop();

break;

}

} } for(int j=0;j

if(P[i].finish())

{

cout<

} getch();}

第五篇：操作系統(tǒng)課程設(shè)計(jì)

引言

操作系統(tǒng)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的主要專業(yè)基礎(chǔ)課和主干課。操作系統(tǒng)對(duì)計(jì)算機(jī)系統(tǒng)資源實(shí)施管理，是所有其他軟件與計(jì)算機(jī)硬件的唯一接口，所有用戶在使用計(jì)算機(jī)時(shí)都要得到操作系統(tǒng)提供的服務(wù)。

通過模擬操作系統(tǒng)的全部或者部分功能的實(shí)現(xiàn)，加深對(duì)操作系統(tǒng)工作原理和操作系統(tǒng)實(shí)現(xiàn)方法的理解，達(dá)到練習(xí)編程的目的，提高學(xué)生運(yùn)用理論知識(shí)分析問題、解決問題的能力，為學(xué)生從事科學(xué)研究和獨(dú)立負(fù)擔(dān)計(jì)算機(jī)及其應(yīng)用方面的工作打好扎實(shí)的基礎(chǔ)。

0 河北大學(xué)工商學(xué)院2011級(jí)操作系統(tǒng)課程設(shè)計(jì)論文（設(shè)計(jì)）課程設(shè)計(jì)任務(wù)及要求

2.1 設(shè)計(jì)任務(wù)

模擬采用多道程序設(shè)計(jì)方法的單用戶操作系統(tǒng)，該操作系統(tǒng)包括進(jìn)程管理、存儲(chǔ)管理、設(shè)備管理、文件管理和用戶接口四部分。

本部分要求實(shí)現(xiàn)文件的邏輯結(jié)構(gòu)、文件的物理結(jié)構(gòu)、目錄結(jié)構(gòu)、磁盤分配和回收、文件的保護(hù)和用戶接口。

2.2 實(shí)現(xiàn)方法和原理

2.2.1文件的邏輯結(jié)構(gòu)：

文件的邏輯結(jié)構(gòu)采用流式結(jié)構(gòu)； 文件均采用文本文件；

系統(tǒng)中有兩種文件，一種是存放任意字符的文件，一種是可執(zhí)行文件?？蓤?zhí)行文件的內(nèi)容就是模擬系統(tǒng)內(nèi)進(jìn)程的程序體。

文件中要有一種特定命令的“可執(zhí)行”文件，文件中的命令非常簡單，包括： x=?;

給x賦值一位數(shù) x++;

x加1 x--;

x減1!??；

第一個(gè)？為A,B,C中某個(gè)設(shè)備，第二個(gè)？為一位數(shù)，表示使用設(shè)備的時(shí)間（由于沒有實(shí)際設(shè)備，所以無法知道設(shè)備何時(shí)工作完成，所以假定一個(gè)數(shù)，這個(gè)數(shù)隨著系統(tǒng)時(shí)間增加而遞減，減到0時(shí)，認(rèn)為是設(shè)備工作完成）；

end.表示文件結(jié)束，同時(shí)將結(jié)果寫入文件out，其中包括文件路徑名和x的值。2.2.2 磁盤模擬：

用一個(gè)文件disk模擬磁盤，磁盤的每個(gè)盤塊64字節(jié)，模擬磁盤共有128塊。第0、1塊存放文件分配表，第2塊存放根目錄，其余存放子目錄和文件。2.2.3目錄結(jié)構(gòu)

目錄結(jié)構(gòu)采用樹型目錄結(jié)構(gòu)，目錄項(xiàng)內(nèi)容共十六個(gè)字節(jié)。①目錄項(xiàng)內(nèi)容（8個(gè)字節(jié)）： 目錄名、文件名：3個(gè)字節(jié)；

河北大學(xué)工商學(xué)院2011級(jí)操作系統(tǒng)課程設(shè)計(jì)論文（設(shè)計(jì)）

擴(kuò)展名：1個(gè)字節(jié)（可執(zhí)行文件擴(kuò)展名為e，目錄沒有擴(kuò)展名）； 目錄、文件屬性：1字節(jié)； 起始盤塊號(hào)：1個(gè)字節(jié)；

文件長度：2字節(jié)（目錄沒有長度）。②根目錄

根目錄位置固定，為磁盤第2塊，大小固定，共8項(xiàng)，占用模擬磁盤第2塊； ③子目錄

位置不固定，大小不固定。2.2.4磁盤分配

磁盤的分配采用鏈接結(jié)構(gòu)（顯式鏈接）的分配方式。系統(tǒng)采用文件分配表方式記錄磁盤空間的使用情況和鏈接結(jié)構(gòu)的指針。

因?yàn)榇疟P有占用磁盤由128塊，所以文件分配表中一項(xiàng)需要1字節(jié)，而磁盤由128塊，因而需要128項(xiàng)，所以模擬磁盤空間中的第0、1塊被用來存放文件分配表。2.2.5用戶接口

用戶接口提供用戶命令接口，要求實(shí)現(xiàn)以下命令： 創(chuàng)建文件：create 拷貝文件：copy 刪除文件：delete 移動(dòng)文件：move 顯示文件：type 編輯文件：edit 改變文件屬性：change 磁盤格式化命令 format 建立目錄：makdir 改變目錄路徑：chadir

刪除空目錄：rdir 刪除目錄：deldir（既可刪除空目錄又可刪除非空目錄）

河北大學(xué)工商學(xué)院2011級(jí)操作系統(tǒng)課程設(shè)計(jì)論文（設(shè)計(jì)）

磁盤分區(qū)命令：fdisk 運(yùn)行可執(zhí)行文件：可執(zhí)行文件的文件名（可創(chuàng)建進(jìn)程）。

上述命令在實(shí)際系統(tǒng)中都是需要建立進(jìn)程才可以實(shí)現(xiàn)的，這里由于模擬系統(tǒng)的能力達(dá)不到，所以除運(yùn)行可執(zhí)行文件需要建立進(jìn)程外，其他指令執(zhí)行不必在模擬系統(tǒng)中建立進(jìn)程，可直接執(zhí)行。

注意打開文件表。2.2.6屏幕顯示

如圖所示，屏幕顯示要求包括：

用戶命令接口，用于系統(tǒng)運(yùn)行時(shí)用戶輸入命令； 磁盤目錄顯示，要求顯示磁盤的樹型目錄結(jié)構(gòu)；

磁盤使用情況，顯示磁盤每一個(gè)磁盤塊的空間是占用還是空閑。

3程序設(shè)計(jì)與實(shí)現(xiàn)

3.1目錄結(jié)構(gòu)的實(shí)現(xiàn)

3.1.1創(chuàng)建目錄

#region CreateMenu(建立目錄)

public void CreateMenu(string pathname,string harddisk)3.1.2刪除空目錄

刪除空目錄首先要找到該目錄，如果目錄不存在，執(zhí)行指令失??；如果存在，但是根 河北大學(xué)工商學(xué)院2011級(jí)操作系統(tǒng)課程設(shè)計(jì)論文（設(shè)計(jì)）

目錄或非空目錄顯示不能刪除，操作失??；若是非空子目錄，則刪除器目錄項(xiàng)并回收對(duì)應(yīng)空間。刪除空目錄的過程和刪除文件的過程相似。

3.1.3刪除目錄

#region DeleteMenu(刪除目錄)

public void DeleteMenu(string pathname, string harddisk)

{

if(Search(pathname,harddisk)== 1)

{

MessageBox.Show(“文件路徑不正確！”, “注意”, MessageBoxButtons.OK, MessageBoxIcon.Exclamation);3.2文件 3.2.1創(chuàng)建文件

#region CreateFile(建立文件)public void CreateFile(string pathname, byte attribute, byte address, char length, string harddisk){

if(attribute == 3 || attribute == 5){

MessageBox.Show(“只讀性質(zhì)，建立失??！”, “注意”, MessageBoxButtons.OK，MessageBoxIcon.Exclamation);

return;} 3.2.2拷貝文件

#region CopyFile(復(fù)制文件,只復(fù)制FCB)

public void CopyFile(string pathname1, string pathname2, string harddisk)

{

string[] pnames = pathname1.Split(new char[] { '', '.' });

string halfpathname = pathname1.Remove(pathname1.Length1]);

UTF8Encoding utf = new UTF8Encoding();4 河北大學(xué)工商學(xué)院2011級(jí)操作系統(tǒng)課程設(shè)計(jì)論文（設(shè)計(jì)）

byte[] name = utf.GetBytes(pnames[pnames.Length1];

CreateFile(pathname2, buffer.Attribute, buffer.Address, buffer.Length,harddisk);

}

#endregion 3.2.3刪除文件 #region DeleteFile(刪除文件)

public void DeleteFile(string pathname, string harddisk)

{

if(Search(pathname,harddisk)==1)

{

MessageBox.Show(“文件路徑不正確！”, “注意”, MessageBoxButtons.OK, MessageBoxIcon.Exclamation);

return;

}

else if(Search(pathname,harddisk)== 2)

//文件存在 {

string[] pnames = pathname.Split(new char[] { '', '.' });

string halfpathname = pathname.Remove(pathname.Length2]);

int disknum;

if(pnames.Length == 3)

//c:aaa.t

{

disknum = 3;

}

else

{

disknum = Search(halfpathname,harddisk);

}

int item = FindItem(disknum, name, attribute,harddisk)[0];

int address = FindItem(disknum, name, attribute,harddisk)[1];

byte addr = Convert.ToByte(address);

DeleteFCB(disknum, item,harddisk);

//刪除FCB

if(addr==0)

{

return;3.2.4移動(dòng)文件

#region CutFile(移動(dòng)文件)

public void CutFile(string pathname1, string pathname2, string harddisk)

{

CopyFile(pathname1, pathname2,harddisk);//復(fù)制FCB到新目錄下

string[] pnames = pathname1.Split(new char[] { '', '.' });

string halfpathname = pathname1.Remove(pathname1.Length1]);

UTF8Encoding utf = new UTF8Encoding();6 河北大學(xué)工商學(xué)院2011級(jí)操作系統(tǒng)課程設(shè)計(jì)論文（設(shè)計(jì)）

byte[] name = utf.GetBytes(pnames[pnames.Length1)+ 8 *(Itemnumber-1), SeekOrigin.Begin);

Disk.Write(buffer.Name, 0, buffer.Name.Length);

Disk.Seek(0, SeekOrigin.Current);

Disk.WriteByte(buffer.Type);

Disk.Seek(0, SeekOrigin.Current);

Disk.WriteByte(buffer.Attribute);

Disk.Seek(0, SeekOrigin.Current);

Disk.WriteByte(buffer.Address);7 河北大學(xué)工商學(xué)院2011級(jí)操作系統(tǒng)課程設(shè)計(jì)論文（設(shè)計(jì)）

Disk.Seek(0, SeekOrigin.Current);

Disk.WriteByte(Convert.ToByte(buffer.Length));

}

Disk.Close();

}

#endregion

3.2.7顯示文件

#region ReadFile(讀文件畫節(jié)點(diǎn))

public void ReadFile(TreeView treeView, ContextMenuStrip contextMenuStrip,ImageList imageList)

{

treeView.Nodes.Clear();

//刪除集合中所有樹節(jié)點(diǎn)

//重新添加樹節(jié)點(diǎn)

treeView.ImageList = imageList;

TreeNode root = new TreeNode(“計(jì)算機(jī)”, 0, 0);

TreeNode node_C = new TreeNode(“本地磁盤C”, 4, 4);

TreeNode node_D = new TreeNode(“本地磁盤D”, 4, 4);

node_C.ContextMenuStrip = contextMenuStrip;

node_D.ContextMenuStrip = contextMenuStrip;

treeView.Nodes.Add(root);

root.Nodes.Add(node_C);

root.Nodes.Add(node_D);

DrawTree(node_C, 3,“disk1.txt”,contextMenuStrip);

DrawTree(node_D, 3, “disk2.txt”,contextMenuStrip);

treeView.ExpandAll();

}

#endregion

4.程序運(yùn)行部分截圖

4.1主頁面 河北大學(xué)工商學(xué)院2011級(jí)操作系統(tǒng)課程設(shè)計(jì)論文（設(shè)計(jì)）

4.2創(chuàng)建文件

4.3編輯文件河北大學(xué)工商學(xué)院2011級(jí)操作系統(tǒng)課程設(shè)計(jì)論文（設(shè)計(jì)）

4.4創(chuàng)建目錄 總結(jié)

在此系統(tǒng)我主要模擬的是文件部分。通過編寫此系統(tǒng)，采用了c#語言。但是，在實(shí)現(xiàn)此系統(tǒng)中，一方面因?yàn)槲覍?duì)c#這門語言掌握的不是很熟練，另外一方面，對(duì)操作系統(tǒng)理解的不夠深入以至于部分功能沒有實(shí)現(xiàn)，讓我發(fā)現(xiàn)了自己的不足，從而要在以后的學(xué)習(xí)中更加努力，不短提高自己個(gè)方面的能力。

河北大學(xué)工商學(xué)院2011級(jí)操作系統(tǒng)課程設(shè)計(jì)論文（設(shè)計(jì)）

裝

訂