操作系統(tǒng)課程設(shè)計(jì)題目及代碼5篇

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

題目一

模擬操作系統(tǒng)設(shè)計(jì)

設(shè)計(jì)一個(gè)模擬操作系統(tǒng)管理程序，實(shí)現(xiàn)下列管理功能： 1．內(nèi)存管理功能 2．文件管理功能 3．磁盤管理功能

題目二

虛擬存儲(chǔ)器各頁面置換算法的實(shí)現(xiàn)與比較內(nèi) 容：設(shè)計(jì)一個(gè)虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū)，通過產(chǎn)生一個(gè)隨機(jī)數(shù)的方法得到一個(gè)頁面序列，假設(shè)內(nèi)存給定的頁面數(shù)由鍵盤輸入，分別計(jì)算使用下述各方法時(shí)的內(nèi)存命中率：

先進(jìn)先出算法（FIFO）、最近最少使用算法（LRU）、最佳淘汰算法（OPT）、最少訪問頁面算法（LFU）等。

參考資料

題目二

資料

虛擬存儲(chǔ)器各頁面置換算法的實(shí)現(xiàn)與比較

1．實(shí)驗(yàn)?zāi)康?/p>

存儲(chǔ)管理的主要功能之一是合理的分配空間。請(qǐng)求頁式管理是一種常用的虛擬存儲(chǔ)管理技術(shù)。

本實(shí)驗(yàn)的目的是通過請(qǐng)求頁式存儲(chǔ)管理中頁面置換算法模擬設(shè)計(jì)，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，掌握請(qǐng)求頁式存儲(chǔ)管理的頁面置換算法。2．實(shí)驗(yàn)內(nèi)容

（1）通過隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列，共320條指令。指令的地址按下述原則生成： 1）50%的指令是順序執(zhí)行的；

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

1）在[0，319]的指令地址之間隨機(jī)選取一起點(diǎn)m； 2）順序執(zhí)行一條指令，即執(zhí)行地址為m+1的指令；

3）在前地址[0，m+1]中隨機(jī)選取一條指令并執(zhí)行，該指令的地址為m'； 4）順序執(zhí)行一條指令，其地址為m'+1；

5）在后地址[m'+2,319]中隨機(jī)選取一條指令并執(zhí)行； 6）重復(fù)上述步驟1）-5），直到執(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)存容量下的命中率。1）先進(jìn)先出的算法（FIFO）； 2）最近最少使用算法（LRR）;3）最佳淘汰算法(OPT)：先淘汰最不常用的頁地址； 4）最少訪問頁面算法（LF.U）； 5）最近最不經(jīng)常使用算法（NUR）。其中３）和４）為選擇內(nèi)容。命中率＝１－頁面失效次數(shù)／頁地址流長(zhǎng)度

在本實(shí)驗(yàn)中，頁地址流長(zhǎng)度為３２０，頁面失效次數(shù)為每次訪問相應(yīng)指令時(shí)，該指令所對(duì)應(yīng)的頁不在內(nèi)存的次數(shù)。３．隨機(jī)數(shù)產(chǎn)生辦法

關(guān)于隨機(jī)數(shù)產(chǎn)生辦法，Linux或Unix系統(tǒng)提供函數(shù)srand()和rand()，分別進(jìn)行初始化和產(chǎn)生隨機(jī)數(shù)。例如： srand()；

語句可初始化一個(gè)隨機(jī)數(shù)； a[0]=10*rand()/32767*319+1;a[1]=10*rand()/32767*a[0]；

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

提示：

首先用Srand()和rand()函數(shù)定義和產(chǎn)生指令序列，然后將指令序列變換成相應(yīng)的頁地址流，并針對(duì)不同的算法計(jì)算出相應(yīng)的命中率。

命中率=1-頁面失效次數(shù)/頁地址流長(zhǎng)度

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

（1）頁面類型 typedef struct{

int pn,pfn,counter,time;}pl-type;

其中pn為頁號(hào)，pfn為頁面號(hào)，count為一個(gè)周期內(nèi)訪問該頁面的次數(shù)，time為訪問時(shí)間。

（2）頁面控制結(jié)構(gòu) 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]定義用戶進(jìn)程虛頁控制結(jié)構(gòu)，*freepf_head為空頁面頭的指針，*busypf_head為忙頁面頭的指針，*busyf_tail為忙頁面尾的指針。

2、函數(shù)定義

（1）Void initialize()：初始化函數(shù)，給每個(gè)相關(guān)的頁面賦值。（2）Void FIFO()：計(jì)算使用FIFO算法時(shí)的命中率。（2）Void LRU（）：計(jì)算使用FIFO算法時(shí)的命中率。（4）VoidOPT（）：計(jì)算使用OPT算法時(shí)的命中率。（5）Void LFU（）：計(jì)算使用LFU算法時(shí)的命中率。（6）Void

NUR（）：計(jì)算使用NUR算法時(shí)的命中率。

3、變量定義

(1)int a[tatal_instruction] ：指令流數(shù)據(jù)組。

(2)int page[total_instruction]：每條指令所屬頁號(hào)。

(3)int offset[total_instruction]：每頁裝入不敷出0條指令后取模運(yùn)算頁號(hào)偏移量。(4)int total_pf：用戶進(jìn)程的內(nèi)存頁面數(shù)。(5)int diseffect：頁面失效次數(shù)。

程序清單

程序: 程序: #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 /*指令流長(zhǎng)*/ #define total_vp 32 /*虛頁長(zhǎng)*/ #define clear_period 50 /*清0周期*/ typedef struct { int pn,pfn,counter,time;}pl_type;pl_type pl[total_vp];/*頁面數(shù)據(jù)結(jié)構(gòu)*/ struct pfc_struct{ /*頁面控制結(jié)構(gòu)*/ 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);/*由于每次運(yùn)行時(shí)進(jìn)程號(hào)不同，故可用來作為初始化隨機(jī)數(shù)隊(duì)

列的種子*/ S=(float)319*rand()/32767+1;for(i=0;inext;pl[busypf_head->pn].pfn=INVALID;freepf_head=busypf_head;/*釋放忙頁面隊(duì)列中的第一個(gè)頁面*/ freepf_head->next=null;busypf_head=p;} p=freepf_head->next;/*按FIFO方式調(diào)新頁面入內(nèi)存頁面*/ freepf_head->next=null;freepf_head->pn=page[i];pl[page[i]].pfn=freepf_head->pfn;if(busypf_tail==null)

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;ipl[j].time&&pl[j].pfn!=INVALID){min=pl[j].time;minj=j;} freepf_head=&pfc[pl[minj].pfn];pl[minj].pfn=INVALID;pl[minj].time=-1;freepf_head->next=null;} pl[page[i]].pfn=freepf_head->pfn;pl[page[i]].time=present_time;freepf_head=freepf_head->next;} else pl[page[i]].time=present_time;present_time++;} printf(“LRU:%6.4f”,1-(float)diseffect/320);} void NUR(total_pf)/*NUR*/ int total_pf;{ int i,j,dp,cont_flag,old_dp;pfc_type *t;initialize(total_pf);dp=0;for(i=0;inext=null;} pl[page[i]].pfn=freepf_head->pfn;freepf_head=freepf_head->next;} else pl[page[i]].counter=1;if(i%clear_period==0)for(j=0;jnext=null;pl[maxpage].pfn=INVALID;} pl[page[i]].pfn=freepf_head->pfn;freepf_head=freepf_head->next;} } printf(“OPT:%6.4f”,1-(float)diseffect/320);} void LFU(total_pf)/*LFU*/ int total_pf;{ int i,j,min,minpage;pfc_type * t;initialize(total_pf);for(i=0;ipl[j].counter&&pl[j].pfn!=INVALID){ min=pl[j].counter;minpage=j;} pl[j].counter=0;} freepf_head=&pfc[pl[minpage].pfn];pl[minpage].pfn=INVALID;freepf_head->next=null;} pl[page[i]].pfn=freepf_head->pfn;freepf_head=freepf_head->next;} else pl[page[i]].counter++;} printf(“LFU:%6.4f”,1-(float)diseffect/320);} void initialize(total_pf)/*初始化相關(guān)數(shù)據(jù)*/ int total_pf;/*用戶進(jìn)程的內(nèi)存頁面數(shù)*/ {int i;diseffect=0;for(i=0;i

1、操作系統(tǒng)實(shí)驗(yàn)教程張麗芬編著

清華大學(xué)出版社

2、操作系統(tǒng)原理實(shí)驗(yàn)教程（基于Linux）胡峰松編

清華大學(xué)出版社

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

遼寧科技大學(xué)操作系統(tǒng)課程設(shè)計(jì)指導(dǎo)書

一、課程設(shè)計(jì)目的和要求

本設(shè)計(jì)是專業(yè)基礎(chǔ)課《操作系統(tǒng)》的課程設(shè)計(jì)。由于操作系統(tǒng)課的學(xué)時(shí)有限，安排實(shí)驗(yàn)的次數(shù)不多。為了進(jìn)一步鞏固實(shí)驗(yàn)成果，加強(qiáng)理論聯(lián)系實(shí)際、分析問題、解決問題的能力，加深對(duì)操作系統(tǒng)的基本概念、原理、技術(shù)和方法的理解，特安排此次課程設(shè)計(jì)。它是操作系統(tǒng)課程的實(shí)踐環(huán)節(jié)。由于具體的操作系統(tǒng)相當(dāng)復(fù)雜，在短短的一周之內(nèi)，不可能對(duì)所有管理系統(tǒng)進(jìn)行詳細(xì)地分析。因此，選擇了操作系統(tǒng)中最重要的管理之一進(jìn)程管理（或進(jìn)程的死鎖、頁面置換算法）作為本設(shè)計(jì)的任務(wù)。另外，通過此次設(shè)計(jì)使學(xué)生在使用系統(tǒng)調(diào)用的同時(shí)，進(jìn)一步了解系統(tǒng)內(nèi)部是如何實(shí)現(xiàn)系統(tǒng)調(diào)用的全過程，使學(xué)生在更深層次上對(duì)操作系統(tǒng)有所了解。要求：

1.在具有自主版權(quán)的Linux環(huán)境下，用c或c++語言，以及相關(guān)的系統(tǒng)調(diào)用，編程實(shí)現(xiàn)進(jìn)程的創(chuàng)建、控制、軟中斷通信、管道通信等功能。2.利用某種高級(jí)語言編程實(shí)現(xiàn)銀行家算法。

3.常用的頁面置換算法有：最佳置換算法（Optimal）、先進(jìn)先出法（Fisrt In First Out）、、最近最久未使用（Least Recently Used），至少實(shí)現(xiàn)其中的兩種算法。

二、課程設(shè)計(jì)內(nèi)容

設(shè)計(jì)題目1：進(jìn)程管理及理解（1）進(jìn)程的創(chuàng)建

編寫一段程序，使用系統(tǒng)調(diào)用fork（）創(chuàng)建兩個(gè)子進(jìn)程。當(dāng)此程序運(yùn)行時(shí)，在系統(tǒng)中有一個(gè)父進(jìn)程和兩個(gè)子進(jìn)程活動(dòng)。讓每一個(gè)進(jìn)程在屏幕上顯示一個(gè)字符：父進(jìn)程顯示“a”；子進(jìn)程分別顯示字符“b”和“c”。試觀察記錄屏幕上的顯示結(jié)果，并分析原因。

（2）進(jìn)程的控制

修改已編寫的程序，將每個(gè)進(jìn)程輸出一個(gè)字符改為每個(gè)進(jìn)程輸出一句話，再觀察程序執(zhí)行時(shí)屏幕上出現(xiàn)的現(xiàn)象，并分析原因。

如果在程序中使用系統(tǒng)調(diào)用lockf（），來給每一個(gè)進(jìn)程加鎖，可以實(shí)現(xiàn)進(jìn)程之間的互斥，觀察并分析出現(xiàn)的現(xiàn)象。

（3）①編制一段程序，使其實(shí)現(xiàn)進(jìn)程的軟中斷通信。

要求：使用系統(tǒng)調(diào)用fork（）創(chuàng)建兩個(gè)子進(jìn)程，再用系統(tǒng)調(diào)用signal（）讓父進(jìn)程捕捉鍵盤上來的中斷信號(hào)；當(dāng)捕捉到中斷信號(hào)后，父進(jìn)程用系統(tǒng)調(diào)用kill（）向兩個(gè)子進(jìn)程發(fā)出信號(hào)，子進(jìn)程捕捉到信號(hào)后分別輸出下列信息后終止：

Child Process11 is Killed by Parent！Child Process12 is Killed by Parent！

父進(jìn)程等待兩個(gè)子進(jìn)程終止后，輸出如下的信息后終止： Parent Process is Killed！

②在上面的程序中增加系統(tǒng)調(diào)用signal（SIGINT,SIG_IGN）和signal（SIGQUIT,SIG_IGN），觀察執(zhí)行結(jié)果，并分析原因。

（4）進(jìn)程的管道通信

編制一段程序，實(shí)現(xiàn)進(jìn)程的管道通信，使用系統(tǒng)調(diào)用pipe（）建立一個(gè)管道文件；兩個(gè)子進(jìn)程P1和P2分別向管道各寫一句話： Child1 is sending a message！Child2 is sending a message！

而父進(jìn)程則從管道中讀出來自于兩個(gè)子進(jìn)程的信息，顯示在屏幕上。

要求父進(jìn)程先接收子進(jìn)程P1發(fā)來的消息，然后再接收子進(jìn)程P2發(fā)來的消息。設(shè)計(jì)題目2：銀行家算法實(shí)現(xiàn)資源分配

要求如下：

(1)進(jìn)程可動(dòng)態(tài)地申請(qǐng)資源和釋放資源，系統(tǒng)按各進(jìn)程的申請(qǐng)動(dòng)態(tài)地分配資源。(2)要求程序具有顯示和打印各進(jìn)程的某一時(shí)刻的資源分配表和安全序列的功能。(3)顯示和打印各進(jìn)程依次要求申請(qǐng)的資源號(hào)以及為某進(jìn)程分配資源后的有關(guān)資源數(shù)據(jù)。

(4)可能用到的數(shù)據(jù)結(jié)構(gòu)：

? 可利用資源向量Available。它是一個(gè)含有m個(gè)元素的數(shù)組，其中每個(gè)元素代表一類可利用資源的數(shù)目。

? 最大需求矩陣Max。n*m矩陣，表示n個(gè)進(jìn)程的每一個(gè)對(duì)m類資源的最大需求。? 分配矩陣Allocation。n*m矩陣，表示每個(gè)進(jìn)程已分配的每類資源的數(shù)目。? 需求矩陣Need。n*m矩陣，表示每個(gè)進(jìn)程還需要各類資源數(shù)。設(shè)計(jì)題目3：虛擬頁面置換算法的實(shí)現(xiàn)

要求如下：

(1)至少實(shí)現(xiàn)OPT、FIFO、LRU三種置換算法中的兩種。

(2)做成GUI界面最好，若不能，則要求界面盡量友好，便于操作。(3)算法中涉及到的頁面訪問序列可以固定，也可以隨機(jī)生成。

(4)在實(shí)現(xiàn)算法的同時(shí)要計(jì)算每種算法的缺頁數(shù)。(5)以表格的形式輸出最終的頁面置換結(jié)果。

注：以上三個(gè)題目任選其一，還可以自擬其它題目。

選擇題目1的同學(xué)，應(yīng)事先了解（1）Linux的命令及使用格式；

可通過下面的幾個(gè)任務(wù)熟悉有關(guān)文件（夾）操作的命令。

（2）在虛擬機(jī)vmware下讓Linux加載U盤的方法。

（3）利用gcc、gdb編譯、調(diào)試C/C++程序

第三篇：《操作系統(tǒng)課程設(shè)計(jì)》題目要求

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

一．設(shè)計(jì)目的

熟悉Linux編程環(huán)境，加強(qiáng)對(duì)Linux命令的理解及函數(shù)的運(yùn)用

二．設(shè)計(jì)內(nèi)容

1.在Linux環(huán)境下模擬實(shí)現(xiàn)簡(jiǎn)單命令解釋器。(1)要求實(shí)現(xiàn)的基本命令包括：

pwd

//顯示當(dāng)前所在目錄的路徑名

dir <目錄名>

//列出指定目錄名中的所有目錄及文件 cd <目錄名或路徑>

//改變當(dāng)前工作目錄 newdir <目錄名>

//刪除目錄

exit //退出命令解釋程序(2)可選做的擴(kuò)展命令包括：

rename <舊文件名> <新文件名> //重命名一個(gè)文件或目錄

find <目錄>-name <待查找的文件名> //在指定的目錄及其子目錄中查找指定的文件

date //顯示當(dāng)前日期(3)提示：整個(gè)程序的大致框架可參考如下：

while(exit未被輸入){

接收鍵盤的一行輸入

分析輸入的命令

對(duì)輸入的命令進(jìn)行處理，調(diào)用系統(tǒng)函數(shù)實(shí)現(xiàn)功能

} 2.設(shè)計(jì)要求

(1)設(shè)計(jì)必須在Linux環(huán)境下進(jìn)行。

(2)命令解釋程序的提示符為：姓名拼音@(3)程序編寫中不得使用system()系統(tǒng)調(diào)用。

(4)整個(gè)程序必須嚴(yán)格經(jīng)過測(cè)試，完成所有基本功能。源程序應(yīng)有較詳盡的注釋。

3.可能用到的系統(tǒng)調(diào)用：

open(),close(),read(),write(),creat()chdir(), opendir(),readdir(),rewinddir(),closedir(),rmdir(),mkdir()getcwd(), ftw()

time(), localtime(), asctime()三．提交要求：

1.完成的源程序和可執(zhí)行程序必須保存在Linux服務(wù)器上。

2.要求實(shí)現(xiàn)的基本命令必須全部實(shí)現(xiàn)。完成可選做的擴(kuò)展命令將得到較高的分?jǐn)?shù)。容錯(cuò)性強(qiáng)和功能細(xì)節(jié)考慮更完全也將得到較高的分?jǐn)?shù)。

3.每位同學(xué)必須完成操作系統(tǒng)課程設(shè)計(jì)說明書并上交紙質(zhì)打印版（不少于3000字），設(shè)計(jì)說明書格式請(qǐng)從ftp下載《操作系統(tǒng)課程設(shè)計(jì)說明書（模板）》查看。（學(xué)習(xí)委員收齊后交到老師辦公室）。說明書電子版提交到老師的FTP

11計(jì)算機(jī)2班的同學(xué)：交給韋婷老師

說明書電子版提交到：ftp://we:345678@10.5.1.請(qǐng)?zhí)峤坏皆揻tp的“/作業(yè)/操作系統(tǒng)課程設(shè)計(jì)/”文件夾中每位同學(xué)的課程設(shè)計(jì)說明書按以下格式命名： “班內(nèi)序號(hào)-姓名.doc”

例如：05-李凱.doc

4.獨(dú)立完成，不得抄襲，凡是發(fā)現(xiàn)抄襲的（無論抄與被抄者），均不及格。5.課程設(shè)計(jì)上交截止日期： 11月12 日

6.設(shè)計(jì)提交后將抽取一部分同學(xué)進(jìn)行答辯，答辯時(shí)間另行通知。

注意：

1.Linux服務(wù)器遠(yuǎn)程連接方式：telnet 10.5.1.6（telnet連接服務(wù)器的過程可能需要十幾秒，屬正?，F(xiàn)象，請(qǐng)耐心等待）2.登陸的用戶名和密碼 11計(jì)算機(jī)2班的同學(xué)：

用戶名：112班內(nèi)序號(hào)

例如: 11計(jì)算機(jī)2班的5號(hào)同學(xué)的用戶名是：11205

初始密碼：123456

3.在Linux環(huán)境編程，若要使用cin、cout，則必須用

#include using namespace std;并使用g++進(jìn)行編譯。

4.本課程設(shè)計(jì)所需資料從ftp://we:345678@10.5.1.5 “/下載/操作系統(tǒng)課程設(shè)計(jì)/” 文件夾中下載。

第四篇：機(jī)票操作系統(tǒng)代碼

操作系統(tǒng)代碼

1，查詢航班：AVH/緊跟輸入城市段、日期（數(shù)字）、月份（英文）后回車查看。如果查詢指定航空公司月份后加“/”再加航空公司代號(hào)。

2，訂座：SD后緊跟序號(hào)計(jì)劃預(yù)定倉位跟人數(shù)后回車。（如果顯示JET代表待定航班）

3．人名：NM1后緊跟客人姓名，如果多個(gè)個(gè)客人，人名雨人名之間用數(shù)字1隔開（國(guó)際航班必須輸入英文，中國(guó)人姓在前后加/，外國(guó)人名在前）

4，聯(lián)系方式：CT后輸入聯(lián)系電話

5，預(yù)留時(shí)間：TKTL/后跟幾點(diǎn)/日期月份BJS…（代碼）

6，封口：@IK（封口號(hào)碼為5位數(shù)字）

7，提記錄：RT后緊跟封口號(hào)碼

8，取消訂票：XEPNR

9，價(jià)格查詢：FD:城市段(只使用于國(guó)內(nèi)查詢)PAT:A 查國(guó)內(nèi)稅和價(jià)格

10：查詢那些航空公司飛：SKPEK緊跟目的地

11，查詢指定日期直達(dá)航班：AV：城市段/日期月份

12，查詢經(jīng)停點(diǎn)：IT：航班號(hào)/日期月份

13，查詢航班經(jīng)停的城市起降時(shí)間和機(jī)型：FF:航班號(hào)/日期月份（沒有經(jīng)停的不顯示）14，查稅（價(jià)格）：QTE：/承運(yùn)人（航空公司）（必須輸入完行程封口或達(dá)到上面第二步），如果出來很多倉位，在輸入XSFSQ后跟代表倉位代碼的序號(hào)。（共享的航班不能查稅）15, 查詢學(xué)生機(jī)票的稅和價(jià)格QTE:SD/航空公司

16,查詢移民機(jī)票價(jià):QTE:EM/航空公司

17,查詢青年機(jī)票價(jià)格:QTE:ZZ/航空公司

18，OPE票的預(yù)定指令：SN：承運(yùn)人---艙位---出發(fā)地與目的地

19,查詢SPA價(jià)格的指令:NFAD：城市段/CA（只能用于國(guó)航聯(lián)運(yùn)協(xié)議的航空公司。國(guó)際段的查詢）

20，查匯率：XS（空格跟FSC后跟幣種代碼/人民幣（可以互換）

21，查代碼代表城市：CD：跟城市代碼

22，用姓名查找記錄：RT/旅客姓的拼音/航班號(hào)/日月年

23，SK:城市段/日期查詢?cè)谔囟ㄖ芷趦?nèi)所有航班的信息，所顯示的航班信息時(shí)間為指定時(shí)間的前后三天一周的時(shí)間

24,查看是否出票：提記錄后，輸入PG1回車，有票號(hào)證明已經(jīng)出票完畢。

25，查詢國(guó)際段航班價(jià)格指令：XSFSD(空格)行程/日期/航空公司，如果后加X,最便宜的會(huì)顯示在最前面。

26,如果沒有艙位需要候補(bǔ)艙位:SD后跟序號(hào)在跟艙位/LL后跟人數(shù)

CP全清屏I清上次屏PN下翻PB上翻PF最前頁P(yáng)G重新顯示當(dāng)前頁P(yáng)L最后頁。Q值的計(jì)算方法：Q值乘以兌換率。(如果使用系統(tǒng)里票面價(jià)格的時(shí)候不用單獨(dú)計(jì)算Q值，因?yàn)橄到y(tǒng)里的報(bào)價(jià)已經(jīng)包含全部費(fèi)用，如果使用促銷價(jià)即不使用系統(tǒng)里顯示的價(jià)格的時(shí)候要計(jì)算Q值再加稅)

學(xué)生票：LH的Q艙位UA的V艙位大部分情況下代表學(xué)生票

外航（例如：AC,UA,NW等）大部分是Q票面，（國(guó)際段的價(jià)格票面應(yīng)該以做境外段的票務(wù)公司報(bào)出的價(jià)格為準(zhǔn)）國(guó)航的價(jià)格看系統(tǒng)或大本政策。去往北美洲國(guó)航聯(lián)運(yùn)的比較AC,UA等轉(zhuǎn)機(jī)的價(jià)格略高。去往歐洲的國(guó)航相對(duì)法航的要便宜，HU飛日本韓國(guó)便宜去往東南亞國(guó)家南航便宜，北京去往韓國(guó)MU，北京到香港CZ便宜

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

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

注意事項(xiàng)：

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

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)班長(zhǎng)收齊，由班長(zhǎ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)程長(zhǎng)度，然后按照短進(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)度算法是一種最簡(jiǎn)單的調(diào)度算法，該算法既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。FCFS算法比較有利于長(zhǎng)作業(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ì)長(zhǎng)作業(yè)不利；不能保證緊迫性作業(yè)（進(jìn)程）被及時(shí)處理；作業(yè)的長(zhǎng)短只是被估算出來的。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è)長(zhǎng)作業(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 算法簡(jiǎn)析 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)行中因爭(zhēng)奪資源而造成的一種僵局(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ù)、缺頁置換率。