第一篇：操作系統課程設計題目及代碼
題目一
模擬操作系統設計
設計一個模擬操作系統管理程序，實現下列管理功能： 1．內存管理功能 2．文件管理功能 3．磁盤管理功能
題目二
虛擬存儲器各頁面置換算法的實現與比較 內 容：設計一個虛擬存儲區和內存工作區，通過產生一個隨機數的方法得到一個頁面序列，假設內存給定的頁面數由鍵盤輸入，分別計算使用下述各方法時的內存命中率：
先進先出算法（FIFO）、最近最少使用算法（LRU）、最佳淘汰算法（OPT）、最少訪問頁面算法（LFU）等。
參考資料
題目二
資料
虛擬存儲器各頁面置換算法的實現與比較
1．實驗目的
存儲管理的主要功能之一是合理的分配空間。請求頁式管理是一種常用的虛擬存儲管理技術。
本實驗的目的是通過請求頁式存儲管理中頁面置換算法模擬設計，了解虛擬存儲技術的特點，掌握請求頁式存儲管理的頁面置換算法。2．實驗內容
（1）通過隨機數產生一個指令序列，共320條指令。指令的地址按下述原則生成： 1）50%的指令是順序執行的；
2）25%的指令是均勻分布在前地址部分； 3）25%的指令是均勻分布在后地址部分； 具體的實施方法是：
1）在[0，319]的指令地址之間隨機選取一起點m； 2）順序執行一條指令，即執行地址為m+1的指令；
3）在前地址[0，m+1]中隨機選取一條指令并執行，該指令的地址為m'； 4）順序執行一條指令，其地址為m'+1；
5）在后地址[m'+2,319]中隨機選取一條指令并執行； 6）重復上述步驟1）-5），直到執行320次指令。（2）將指令序列變換成為頁地址流 設：1）頁面大小為1k；
2）用戶內存容量為4頁到32頁； 3）用戶虛存容量為32k； 在用戶虛存中，按每k存放10條指令排列虛存地址，即320條指令在虛存中的存放方式為： 第0條-第9條指令為第0頁（對應虛存地址為[0，9]）； 第10條-第19條指令為第1頁（對應虛存地址為[10，19]）；
...第310條-第319條指令為第31頁（對應虛存地址為[310，319]）；
按以上方式，用戶指令可組成為32頁。
（3）計算并輸出下列各種算法在不同內存容量下的命中率。1）先進先出的算法（FIFO）； 2）最近最少使用算法（LRR）;3）最佳淘汰算法(OPT)：先淘汰最不常用的頁地址； 4）最少訪問頁面算法（LF.U）； 5）最近最不經常使用算法（NUR）。其中３）和４）為選擇內容。命中率＝１－頁面失效次數／頁地址流長度
在本實驗中，頁地址流長度為３２０，頁面失效次數為每次訪問相應指令時，該指令所對應的頁不在內存的次數。３．隨機數產生辦法
關于隨機數產生辦法，Linux或Unix系統提供函數srand()和rand()，分別進行初始化和產生隨機數。例如： srand()；
語句可初始化一個隨機數； a[0]=10*rand()/32767*319+1;a[1]=10*rand()/32767*a[0]；
..語句可用來產生a[0]與a[1]中的隨機數。
提示：
首先用Srand()和rand()函數定義和產生指令序列，然后將指令序列變換成相應的頁地址流，并針對不同的算法計算出相應的命中率。
命中率=1-頁面失效次數/頁地址流長度
1、數據結構
（1）頁面類型 typedef struct{
int pn,pfn,counter,time;}pl-type;
其中pn為頁號，pfn為頁面號，count為一個周期內訪問該頁面的次數，time為訪問時間。
（2）頁面控制結構 pfc_struct{
int pn,pfn;
struct pfc_struct *next;
};typedef struct
pfc_struct pfc_type;pfc_type
pfc[total_vp],*freepf_head,*busypf_head;pfc_type *busypf_tail;其中，pfc[total_vp]定義用戶進程虛頁控制結構，*freepf_head為空頁面頭的指針，*busypf_head為忙頁面頭的指針，*busyf_tail為忙頁面尾的指針。
2、函數定義
（1）Void initialize()：初始化函數，給每個相關的頁面賦值。（2）Void FIFO()：計算使用FIFO算法時的命中率。（2）Void LRU（）：計算使用FIFO算法時的命中率。（4）VoidOPT（）：計算使用OPT算法時的命中率。（5）Void LFU（）：計算使用LFU算法時的命中率。（6）Void
NUR（）：計算使用NUR算法時的命中率。
3、變量定義
(1)int a[tatal_instruction] ：指令流數據組。
(2)int page[total_instruction]：每條指令所屬頁號。
(3)int offset[total_instruction]：每頁裝入不敷出0條指令后取模運算頁號偏移量。(4)int total_pf：用戶進程的內存頁面數。(5)int diseffect：頁面失效次數。
程序清單
程序: 程序: #include “stdio.h” #include “process.h” #include “stdlib.h” #define TRUE 1 #define FALSE 0 #define INVALID-1 #define null 0 #define total_instruction 320 /*指令流長*/ #define total_vp 32 /*虛頁長*/ #define clear_period 50 /*清0周期*/ typedef struct { int pn,pfn,counter,time;}pl_type;pl_type pl[total_vp];/*頁面數據結構*/ struct pfc_struct{ /*頁面控制結構*/ int pn,pfn;struct pfc_struct *next;};typedef struct pfc_struct pfc_type;pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;int diseffect,a[total_instruction];int page[total_instruction],offset[total_instruction];void initialize();void FIFO();void LRU();void OPT();void LFU();void NUR();main(){ int S,i,j;srand(getpid()*10);/*由于每次運行時進程號不同，故可用來作為初始化隨機數隊
列的種子*/ S=(float)319*rand()/32767+1;for(i=0;i
busypf_head=busypf_tail=freepf_head;else {busypf_tail->next=freepf_head;busypf_tail=freepf_head;} freepf_head=p;} } printf(“FIFO:%6.4”,1-(float)diseffect/320);} void LRU(total_pf)/*LRU*/ int total_pf;{ int min,minj,i,j,present_time;initialize(total_pf);present_time=0;for(i=0;i 1、操作系統實驗教程 張麗芬編著 清華大學出版社 2、操作系統原理實驗教程（基于Linux）胡峰松編 清華大學出版社 遼寧科技大學操作系統課程設計指導書 一、課程設計目的和要求 本設計是專業基礎課《操作系統》的課程設計。由于操作系統課的學時有限，安排實驗的次數不多。為了進一步鞏固實驗成果，加強理論聯系實際、分析問題、解決問題的能力，加深對操作系統的基本概念、原理、技術和方法的理解，特安排此次課程設計。它是操作系統課程的實踐環節。由于具體的操作系統相當復雜，在短短的一周之內，不可能對所有管理系統進行詳細地分析。因此，選擇了操作系統中最重要的管理之一進程管理（或進程的死鎖、頁面置換算法）作為本設計的任務。另外，通過此次設計使學生在使用系統調用的同時，進一步了解系統內部是如何實現系統調用的全過程，使學生在更深層次上對操作系統有所了解。要求： 1.在具有自主版權的Linux環境下，用c或c++語言，以及相關的系統調用，編程實現進程的創建、控制、軟中斷通信、管道通信等功能。2.利用某種高級語言編程實現銀行家算法。 3.常用的頁面置換算法有：最佳置換算法（Optimal）、先進先出法（Fisrt In First Out）、、最近最久未使用（Least Recently Used），至少實現其中的兩種算法。 二、課程設計內容 設計題目1：進程管理及理解（1）進程的創建 編寫一段程序，使用系統調用fork（）創建兩個子進程。當此程序運行時，在系統中有一個父進程和兩個子進程活動。讓每一個進程在屏幕上顯示一個字符：父進程顯示“a”；子進程分別顯示字符“b”和“c”。試觀察記錄屏幕上的顯示結果，并分析原因。 （2）進程的控制 修改已編寫的程序，將每個進程輸出一個字符改為每個進程輸出一句話，再觀察程序執行時屏幕上出現的現象，并分析原因。 如果在程序中使用系統調用lockf（），來給每一個進程加鎖，可以實現進程之間的互斥，觀察并分析出現的現象。 （3）①編制一段程序，使其實現進程的軟中斷通信。 要求：使用系統調用fork（）創建兩個子進程，再用系統調用signal（）讓父進程捕捉鍵盤上來的中斷信號；當捕捉到中斷信號后，父進程用系統調用kill（）向兩個子進程發出信號，子進程捕捉到信號后分別輸出下列信息后終止： Child Process11 is Killed by Parent！Child Process12 is Killed by Parent！ 父進程等待兩個子進程終止后，輸出如下的信息后終止： Parent Process is Killed！ ②在上面的程序中增加系統調用signal（SIGINT,SIG_IGN）和signal（SIGQUIT,SIG_IGN），觀察執行結果，并分析原因。 （4）進程的管道通信 編制一段程序，實現進程的管道通信，使用系統調用pipe（）建立一個管道文件；兩個子進程P1和P2分別向管道各寫一句話： Child1 is sending a message！Child2 is sending a message！ 而父進程則從管道中讀出來自于兩個子進程的信息，顯示在屏幕上。 要求父進程先接收子進程P1發來的消息，然后再接收子進程P2發來的消息。設計題目2：銀行家算法實現資源分配 要求如下： (1)進程可動態地申請資源和釋放資源，系統按各進程的申請動態地分配資源。(2)要求程序具有顯示和打印各進程的某一時刻的資源分配表和安全序列的功能。(3)顯示和打印各進程依次要求申請的資源號以及為某進程分配資源后的有關資源數據。 (4)可能用到的數據結構： ? 可利用資源向量Available。它是一個含有m個元素的數組，其中每個元素代表一類可利用資源的數目。 ? 最大需求矩陣Max。n*m矩陣，表示n個進程的每一個對m類資源的最大需求。? 分配矩陣Allocation。n*m矩陣，表示每個進程已分配的每類資源的數目。? 需求矩陣Need。n*m矩陣，表示每個進程還需要各類資源數。設計題目3：虛擬頁面置換算法的實現 要求如下： (1)至少實現OPT、FIFO、LRU三種置換算法中的兩種。 (2)做成GUI界面最好，若不能，則要求界面盡量友好，便于操作。(3)算法中涉及到的頁面訪問序列可以固定，也可以隨機生成。 (4)在實現算法的同時要計算每種算法的缺頁數。(5)以表格的形式輸出最終的頁面置換結果。 注：以上三個題目任選其一，還可以自擬其它題目。 選擇題目1的同學，應事先了解（1）Linux的命令及使用格式； 可通過下面的幾個任務熟悉有關文件（夾）操作的命令。 （2）在虛擬機vmware下讓Linux加載U盤的方法。 （3）利用gcc、gdb編譯、調試C/C++程序 操作系統課程設計要求 一．設計目的 熟悉Linux編程環境，加強對Linux命令的理解及函數的運用 二．設計內容 1.在Linux環境下模擬實現簡單命令解釋器。(1)要求實現的基本命令包括： pwd //顯示當前所在目錄的路徑名 dir <目錄名> //列出指定目錄名中的所有目錄及文件 cd <目錄名或路徑> //改變當前工作目錄 newdir <目錄名> //新建目錄 deldir <目錄名> //刪除目錄 exit //退出命令解釋程序(2)可選做的擴展命令包括： rename <舊文件名> <新文件名> //重命名一個文件或目錄 find <目錄>-name <待查找的文件名> //在指定的目錄及其子目錄中查找指定的文件 date //顯示當前日期(3)提示：整個程序的大致框架可參考如下： while(exit未被輸入){ 接收鍵盤的一行輸入 分析輸入的命令 對輸入的命令進行處理，調用系統函數實現功能 } 2.設計要求 (1)設計必須在Linux環境下進行。 (2)命令解釋程序的提示符為：姓名拼音@(3)程序編寫中不得使用system()系統調用。 (4)整個程序必須嚴格經過測試，完成所有基本功能。源程序應有較詳盡的注釋。 3.可能用到的系統調用： open(),close(),read(),write(),creat()chdir(), opendir(),readdir(),rewinddir(),closedir(),rmdir(),mkdir()getcwd(), ftw() time(), localtime(), asctime()三． 提交要求： 1.完成的源程序和可執行程序必須保存在Linux服務器上。 2.要求實現的基本命令必須全部實現。完成可選做的擴展命令將得到較高的分數。容錯性強和功能細節考慮更完全也將得到較高的分數。 3.每位同學必須完成操作系統課程設計說明書并上交紙質打印版（不少于3000字），設計說明書格式請從ftp下載《操作系統課程設計說明書（模板）》查看。（學習委員收齊后交到老師辦公室）。說明書電子版提交到老師的FTP 11計算機2班的同學： 交給韋婷老師 說明書電子版提交到：ftp://we:345678@10.5.1.請提交到該ftp的“/作業/操作系統課程設計/”文件夾中 每位同學的課程設計說明書按以下格式命名： “班內序號-姓名.doc” 例如：05-李凱.doc 4.獨立完成，不得抄襲，凡是發現抄襲的（無論抄與被抄者），均不及格。5.課程設計上交截止日期： 11月12 日 6.設計提交后將抽取一部分同學進行答辯，答辯時間另行通知。 注意： 1.Linux服務器遠程連接方式：telnet 10.5.1.6（telnet連接服務器的過程可能需要十幾秒，屬正常現象，請耐心等待）2.登陸的用戶名和密碼 11計算機2班的同學： 用戶名：112班內序號 例如: 11計算機2班的5號同學的用戶名是：11205 初始密碼：123456 3.在Linux環境編程，若要使用cin、cout，則必須用 #include 4.本課程設計所需資料從ftp://we:345678@10.5.1.5 “/下載/操作系統課程設計/” 文件夾中下載。 操作系統代碼 1，查詢航班：AVH/緊跟輸入城市段、日期（數字）、月份（英文）后回車查看。如果查詢指定航空公司月份后加“/”再加航空公司代號。 2，訂座：SD后緊跟序號計劃預定倉位跟人數后回車。（如果顯示JET代表待定航班） 3．人名：NM1后緊跟客人姓名，如果多個個客人，人名雨人名之間用數字1隔開（國際航班必須輸入英文，中國人姓在前后加/，外國人名在前） 4，聯系方式：CT后輸入聯系電話 5，預留時間：TKTL/后跟幾點/日期月份BJS…（代碼） 6，封口：@IK（封口號碼為5位數字） 7，提記錄：RT后緊跟封口號碼 8，取消訂票：XEPNR 9，價格查詢：FD:城市段(只使用于國內查詢)PAT:A 查國內稅和價格 10：查詢那些航空公司飛：SKPEK緊跟目的地 11，查詢指定日期直達航班：AV：城市段/日期月份 12，查詢經停點：IT：航班號/日期月份 13，查詢航班經停的城市起降時間和機型：FF:航班號/日期月份（沒有經停的不顯示）14，查稅（價格）：QTE：/承運人（航空公司）（必須輸入完行程封口或達到上面第二步），如果出來很多倉位，在輸入XSFSQ后跟代表倉位代碼的序號。（共享的航班不能查稅）15, 查詢學生機票的稅和價格QTE:SD/航空公司 16,查詢移民機票價:QTE:EM/航空公司 17,查詢青年機票價格:QTE:ZZ/航空公司 18，OPE票的預定指令：SN：承運人---艙位---出發地與目的地 19,查詢SPA價格的指令:NFAD：城市段/CA（只能用于國航聯運協議的航空公司。國際段的查詢） 20，查匯率：XS（空格跟FSC后跟幣種代碼/人民幣（可以互換） 21，查代碼代表城市：CD：跟城市代碼 22，用姓名查找記錄：RT/旅客姓的拼音/航班號/日月年 23，SK:城市段/日期 查詢在特定周期內所有航班的信息，所顯示的航班信息時間為指定時間的前后三天一周的時間 24,查看是否出票：提記錄后，輸入PG1回車，有票號證明已經出票完畢。 25，查詢國際段航班價格指令：XSFSD(空格)行程/日期/航空公司，如果后加X,最便宜的會顯示在最前面。 26,如果沒有艙位需要候補艙位:SD后跟序號在跟艙位/LL后跟人數 CP全清屏I清上次屏PN下翻PB上翻PF最前頁PG重新顯示當前頁PL最后頁。Q值的計算方法：Q值乘以兌換率。(如果使用系統里票面價格的時候不用單獨計算Q值，因為系統里的報價已經包含全部費用，如果使用促銷價即不使用系統里顯示的價格的時候要計算Q值再加稅) 學生票：LH的Q艙位UA的V艙位 大部分情況下代表學生票 外航（例如：AC,UA,NW等）大部分是Q票面，（國際段的價格票面應該以做境外段的票務公司報出的價格為準）國航的價格看系統或大本政策。去往北美洲國航聯運的比較AC,UA等轉機的價格略高。去往歐洲的國航相對法航的要便宜，HU飛日本韓國便宜 去往東南亞國家南航便宜，北京去往韓國MU，北京到香港CZ便宜 操作系統課程設計 注意事項： 0.請每位同學必須按時提交課程設計報告（包括電子版和紙質版），算入期末成績 1.在三個題目中選擇一個 2.如果選擇題目 （一）進程調度算法，要求實現其中2個以上（包括2個）進程調度算法 3.如果選擇題目 （二）銀行家算法，要求能夠判斷系統的安全狀態 4.如果選擇題目 （三）頁面調度算法，要求實現其中2個以上（包含2個）進程調度算法 5.報告應包含算法分析、實驗截圖、核心算法源代碼，請各位同學認真對待，獨立完成 6.提交要求：電子版（包括實驗程序）請發至ropeal@163.com，紙質版請班長收齊，由班長統一在課堂上提交（并提交未交人員名單），截止時間第16周周三(2014.1.31)7.格式要求： 7.1 A4紙10頁左右 7.2 封面請注明班級、姓名、學號、所選題目 7.3 電子版發送時，請打包成一個文件，將文件名設置為：學號+姓名+題目名稱（如20130000張三進程調度算法課程設計），郵件主題同文件名 一、進程調度算法 1.1 實驗目的： a、設計進程控制塊PCB表結構，模擬實現進程調度算法：FIFO，靜態優先級調度，時間片輪轉調度，多級反饋隊列調度。（實現其中之二）。* b、建立進程就緒隊列。對不同算法編制入鏈子程序。c、編寫一進程調度程序模擬程序。模擬程序只對PCB進行相應的調度模擬操作，不需要實際程序。* 由用戶輸入進程名和進程長度，然后按照短進程優先的進程處理順序給出進程的排序。 1.2 實驗原理 調度算法是指：根據系統的資源分配策略所規定的資源分配算法。1.2.1 先來先服務和短作業（進程）優先調度算法 1.先來先服務調度算法。先來先服務（FCFS）調度算法是一種最簡單的調度算法，該算法既可用于作業調度，也可用于進程調度。FCFS算法比較有利于長作業（進程），而不利于短作業（進程）。由此可知，本算法適合于CPU繁忙型作業，而不利于I/O繁忙型的作業（進程）。 2.短作業（進程）優先調度算法。短作業（進程）優先調度算法（SJ/PF）是指對短作業或短進程優先調度的算法，該算法既可用于作業調度，也可用于進程調度。但其對長作業不利；不能保證緊迫性作業（進程）被及時處理；作業的長短只是被估算出來的。1.2.2 高優先權優先調度算法 1.優先權調度算法的類型。為了照顧緊迫性作業，使之進入系統后便獲得優先處理，引入了最高優先權優先（FPF）調度算法。此算法常被用在批處理系統中，作為作業調度算法，也作為多種操作系統中的進程調度，還可以用于實時系統中。當其用于作業調度，將后備隊列中若干個優先權最高的作業裝入內存。當其用于進程調度時，把處理機分配給就緒隊列中優先權最高的進程，此時，又可以進一步把該算法分成以下兩種： 1)非搶占式優先權算法 2)搶占式優先權調度算法（高性能計算機操作系統） 2.優先權類型。對于最高優先權優先調度算法，其核心在于：它是使用靜態優先權還是動態優先權，以及如何確定進程的優先權。3．高響應比優先調度算法 為了彌補短作業優先算法的不足，我們引入動態優先權，使作業的優先等級隨著等待時間的增加而以速率a提高。該優先權變化規律可描述為：優先權=（等待時間+要求服務時間）/要求服務時間；即 =（響應時間）/要求服務時間 1.2.3 基于時間片的輪轉調度算法 1.時間片輪轉法。時間片輪轉法一般用于進程調度，每次調度，把CPU分配隊首進程，并令其執行一個時間片。當執行的時間片用完時，由一個記時器發出一個時鐘中斷請求，該進程被停止，并被送往就緒隊列末尾；依次循環。2.多級反饋隊列調度算法 多級反饋隊列調度算法多級反饋隊列調度算法，不必事先知道各種進程所需要執行的時間，它是目前被公認的一種較好的進程調度算法。其實施過程如下： 1)設置多個就緒隊列，并為各個隊列賦予不同的優先級。在優先權越高的隊列中，為每個進程所規定的執行時間片就越小。 2)當一個新進程進入內存后，首先放入第一隊列的末尾，按FCFS原則排隊等候調度。如果他能在一個時間片中完成，便可撤離；如果未完成，就轉入第二隊列的末尾，在同樣等待調度?? 如此下去，當一個長作業（進程）從第一隊列依次將到第n隊列（最后隊列）后，便按第n隊列時間片輪轉運行。3)僅當第一隊列空閑時，調度程序才調度第二隊列中的進程運行；僅當第1到第（i-1）隊列空時，才會調度第i隊列中的進程運行，并執行相應的時間片輪轉。4)如果處理機正在處理第i隊列中某進程，又有新進程進入優先權較高的隊列，則此新隊列搶占正在運行的處理機，并把正在運行的進程放在第i隊列的隊尾。 1．3 實驗要求 a、使用模塊化設計思想來設計； b、給出算法的流程圖或偽碼說明。c、學生可按照自身條件，隨意選擇采用的算法，（例如：采用冒泡法編寫程序，實現短進程優先調度的算法） d、進程調度程序模擬程序只對PCB進行相應的調度模擬操作，不需要實際程序。 1.4 算法簡析 a、每個進程可有三個狀態，并假設初始狀態為就緒狀態。b、為了便于處理，程序中的某進程運行時間以時間片為單位計算。各進程的優先數或輪轉時間數以及進程需運行的時間片數的初始值均由用戶給定。c、在優先數算法中，優先數可以先取值為（50-該進程所需時間），進程每執行一次，優先數減3，CPU時間片數（CPUtime）加1，* 進程還需要的時間片數（needtime）減1。在時間片輪轉算法中，采用固定時間片 （即：每執行一次進程，該進程的執行時間片數為已執行了2個單位），這時，CPU時間片（CPUtime）數加2，* 進程還需要的時間片數（needtime）減2，并排列到就緒隊列的尾上。 d、對于遇到優先數一致的情況，采用FIFO策略解決。 二、銀行家算法 2.1 概述 2.1.1 設計目的1、了解多道程序系統中，多個進程并發執行的資源分配。 2、掌握死鎖的產生的原因、產生死鎖的必要條件和處理死鎖的基本方法。 3、掌握預防死鎖的方法，系統安全狀態的基本概念。 4、掌握銀行家算法，了解資源在進程并發執行中的資源分配策略。 5、理解死鎖避免在當前計算機系統不常使用的原因 2.2 關于死鎖 2.2.1 死鎖概念： 在多道程序系統中，雖可借助于多個進程的并發執行，來改善系統的資源利用率，提高系統的吞吐量，但可能發生一種危險━━死鎖。所謂死鎖(Deadlock),是指多個進程在運行中因爭奪資源而造成的一種僵局(Deadly_Embrace),當進程處于這種僵持狀態時，若無外力作用，它們都將無法再向前推進。一組進程中，每個進程都無限等待被該組進程中另一進程所占有的資源，因而永遠無法得到的資源，這種現象稱為進程死鎖，這一組進程就稱為死鎖進程。 2.2.2 關于死鎖的一些結論： 參與死鎖的進程最少是兩個（兩個以上進程才會出現死鎖） 參與死鎖的進程至少有兩個已經占有資源 參與死鎖的所有進程都在等待資源 參與死鎖的進程是當前系統中所有進程的子集 注：如果死鎖發生，會浪費大量系統資源，甚至導致系統崩潰。 2.2.3 資源分類： 永久性資源： 可以被多個進程多次使用（可再用資源），分為：可搶占資源與不可搶占資源 臨時性資源：只可使用一次的資源；如信號量,中斷信號，同步信號等（可消耗性資源） “申請--分配--使用--釋放”模式 2.2.4 產生死鎖的四個必要條件： 1、互斥使用（資源獨占） 一個資源每次只能給一個進程使用 2、不可強占（不可剝奪） 資源申請者不能強行的從資源占有者手中奪取資源，資源只能由占有者自愿釋放 3、請求和保持（部分分配，占有申請） 一個進程在申請新的資源的同時保持對原有資源的占有（只有這樣才是動態申請，動態分配） 4、循環等待 存在一個進程等待隊列 {P1 , P2 , ? , Pn}，其中P1等待P2占有的資源，P2等待P3占有的資源，?，Pn等待P1占有的資源，形成一個進程等待環路 2.2.5 死鎖的解決方案 1 產生死鎖的例子 申請不同類型資源產生死鎖 P1： ? 申請打印機 申請掃描儀 使用 釋放打印機 釋放掃描儀 ? P2： ? 申請掃描儀 申請打印機 使用 釋放打印機 釋放掃描儀 ? 申請同類資源產生死鎖（如內存） 設有資源R，R有m個分配單位，由n個進程P1,P2,?,Pn（n > m）共享。假設每個進程對R的申請和釋放符合下列原則： * 一次只能申請一個單位 * 滿足總申請后才能使用 * 使用完后一次性釋放 m=2，n=3 資源分配不當導致死鎖產生 2死鎖預防: 定義:在系統設計時確定資源分配算法，保證不發生死鎖。具體的做法是破壞產生死鎖的四個必要條件之一 ①破壞“不可剝奪”條件 在允許進程動態申請資源前提下規定，一個進程在申請新的資源不能立即得到滿足而變為等待狀態之前，必須釋放已占有的全部資源，若需要再重新申請 ②破壞“請求和保持”條件 要求每個進程在運行前必須一次性申請它所要求的所有資源，且僅當該進程所要資源均可滿足時才給予一次性分配 ③破壞“循環等待”條件 采用資源有序分配法： 把系統中所有資源編號，進程在申請資源時必須嚴格按資源編號的遞增次序進行，否則操作系統不予分配。 2.2.6 安全狀態與不安全狀態 安全狀態： 如果存在一個由系統中所有進程構成的安全序列P1，?Pn，則系統處于安全狀態。一個進程序列{P1，?，Pn}是安全的，如果對于每一個進程Pi(1≤i≤n），它以后尚需要的資源量不超過系統當前剩余資源量與所有進程Pj(j < i)當前占有資源量之和，系統處于安全狀態(安全狀態一定是沒有死鎖發生的)。 不安全狀態:不存在一個安全序列，不安全狀態一定導致死鎖。 2.3 數據結構設計 1.可利用資源向量矩陣AVAILABLE。這是一個含有m個元素的數組，其中的每一個元素代表一類可利用的資源數目，其初始值是系統中所配置的該類全部可用資源的數目，其數值隨該類資源的分配和回收而動態地改變。如果AVAILABLE [j]= K，則表示系統中現有R類資源K個 2.最大需求矩陣MAX。這是一個n*m的矩陣，用以表示每一個進程對m類資源的最大需求。如果MAX [i,j]=K，則表示進程i需要R類資源的數目為K。 3.分配矩陣ALLOCATION。這也是一個n*m的矩陣，它定義了系統中每一類資源當前已分配給每一進程的資源數。如果ALLOCATION [i,j]=K，則表示進程i當前已分得R類資源的數目為K。 4.需求矩陣NEED。這也是一個n*m的矩陣，用以表示每一個進程尚需的各類資源數。如果NEED [i,j]=K，則表示進程i還需要R類資源K個，才能完成其任務。上述矩陣存在下述關系： NEED [i,j]= MAX[i,j]﹣ ALLOCATION[i,j] 2.4 算法的實現 2.4.1 初始化 由用戶輸入數據，分別對可利用資源向量矩陣AVAILABLE、最大需求矩陣MAX、分配矩陣ALLOCATION、需求矩陣NEED賦值。2.4.2 銀行家算法 在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統性能。在該方法中把系統的狀態分為安全狀態和不安全狀態，只要能使系統始終都處于安全狀態，便可以避免發生死鎖。 銀行家算法的基本思想是分配資源之前,判斷系統是否是安全的;若是,才分配。它是最具有代表性的避免死鎖的算法。 設進程cusneed提出請求REQUEST [i]，則銀行家算法按如下規則進行判斷。(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，則轉(2)；否則，出錯。 (2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，則轉(3)；否則，出錯。(3)系統試探分配資源，修改相關數據： AVAILABLE[i]-=REQUEST[cusneed][i];ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];NEED[cusneed][i]-=REQUEST[cusneed][i];(4)系統執行安全性檢查，如安全，則分配成立；否則試探險性分配作廢，系統恢復原狀，進程等待。 2.4.3 安全性檢查算法 (1)設置兩個工作向量Work=AVAILABLE;FINISH(2)從進程集合中找到一個滿足下述條件的進程，FINISH==false;NEED<=Work;如找到，執行(3)；否則，執行(4)(3)設進程獲得資源，可順利執行，直至完成，從而釋放資源。 Work+=ALLOCATION;Finish=true;GOTO 2(4)如所有的進程Finish= true，則表示安全；否則系統不安全。 三、頁面調度算法 3.1 實驗名稱 頁式虛擬存儲管理：頁面調度算法 3.2 實驗目的 頁式虛擬存儲器實現的一個難點是設計頁面調度（置換）算法，即將新頁面調入內存時，如果內存中所有的物理頁都已經分配出去，就要按某種策略來廢棄某個頁面，將其所占據的物理頁釋放出來，供新頁面使用。本實驗的目的是通過編程實現幾種常見的頁面調度（置換）算法，加深讀者對頁面思想的理解。3.3 實驗原理 頁面調度算法 目前有許多頁面調度算法，本實驗主要涉及先進先出調度算法、最近最少調度算法、最近最不常用調度算法。本實驗使用頁面調度算法時作如下假設，進程在創建時由操作系統為之分配一個固定數目物理頁，執行過程中物理頁的數目和位置不會改變。也即進程進行頁面調度時只能在分到的幾個物理頁中進行。 下面對各調度算法的思想作一介紹。 <1> 先進先出調度算法 先進先出調度算法根據頁面進入內存的時間先后選擇淘汰頁面，先進入內存的頁面先淘汰，后進入內存的后淘汰。本算法實現時需要將頁面按進入內存的時間先后組成一個隊列，每次調度隊首頁面予以淘汰。 <2>最近最少調度算法 先進先出調度算法沒有考慮頁面的使用情況，大多數情況下性能不佳。根據程序執行的局部性特點，程序一旦訪問了某些代碼和數據，則在一段時間內會經常訪問他們，因此最近最少用調度在選擇淘汰頁面時會考慮頁面最近的使用，總是選擇在最近一段時間以來最少使用的頁面予以淘汰。算法實現時需要為每個頁面設置數據結構記錄頁面自上次訪問以來所經歷的時間。 <3>最近最不常用調度算法 由于程序設計中經常使用循環結構，根據程序執行的局部性特點，可以設想在一段時間內經常被訪問的代碼和數據在將來也會經常被訪問，顯然這樣的頁面不應該被淘汰。最近最不常用調度算法總是根據一段時間內頁面的訪問次數來選擇淘汰頁面，每次淘汰訪問次數最少的頁面。算法實現時需要為每個頁面設置計數器，記錄訪問次數。計數器由硬件或操作系統自動定時清零。 缺頁調度次數和缺頁中斷率、缺頁置換率計算 缺頁中斷次數是缺頁時發出缺頁中斷的次數。 缺頁中斷率=缺頁中斷次數/總的頁面引用次數*100% 缺頁調度次數是調入新頁時需要進行頁面調度的次數 缺頁置換率=缺頁調度次數/總的頁面引用次數*100% 3.4 實驗內容 （1）設計程序實現以上三種頁面調度算法，要求： ①.可以選擇頁面調度算法類型； ②.可以為進程設置分到物理頁的數目，設置進程的頁面引用情況，可以從鍵盤輸入頁面序列，也可從文件中讀取； ③.隨時計算當前的頁面調度次數的缺頁中斷率； ④.使用敲鍵盤或響應WM-TIMER的形式模仿時間的流逝； ⑤.以直觀的的形式將程序的執行情況顯示在計算機屏幕上； ⑥.存盤及讀盤功能，可以隨時將數據存入磁盤文件，供以后重復實驗時使用。 （2）假定進程分配到3個物理塊，對于下面的頁面引用序列：（test.txt） 7-0-1-2-0-3-0-4-2-3-0-3-2-1-2-0-1-7-0-1 請分別用先進和先出調度算法，最近最少用調度算法，最近最不常用調度算法計算缺頁中斷次數，缺頁中斷率和缺頁調度次數、缺頁置換率。 再假定進程分配到4、5個物理塊，重復本實驗。 （3）假定進程分配到3個物理塊，對于下面的頁面引用序列：（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 請分別用先進先出調度算法、最近最少用調度算法，最近最不常用調度算法計算缺頁中斷次數，缺頁中斷率和缺頁調度次數、缺頁置換率。 再假定進程分配到4、5個物理塊，重復本實驗。 （4）假定進程分配到3個物理塊，使用程序的動態頁面序列生成算法，生成一個頁面序列，將此序列存入磁盤文件。再從磁盤文件讀入該序列，用程序分別計算三種算法下的缺頁中斷次數、缺頁中斷率和缺頁調度次數、缺頁置換率。第二篇：操作系統課程設計題目
第三篇：《操作系統課程設計》題目要求
第四篇：機票操作系統代碼
第五篇：操作系統課程設計
點擊咨詢 