第一篇：操作系統(tǒng)-課程設計報告-處理機調度程序

操作系統(tǒng)

課程設計報告

學校：廣州大學

學院：計算機科學與教育軟件學院 班級：計算機127班 課題：處理機調度程序

任課老師：陶文正、陳文彬

姓名：黃俊鵬

學號：1200002111 班內序號：27 成績：

日期：2015年1月6日

一、設計目的

在多道程序和多任務系統(tǒng)中，系統(tǒng)內同時處于就緒狀態(tài)的進程可能有若干個。也就是說能運行的進程數(shù)大于處理機個數(shù)。為了使系統(tǒng)中的進程能有條不紊地工作，必須選用某種調度策略，選擇一進程占用處理機。要求學生設計一個模擬處理機調度算法，以鞏固和加深處理機調度的概念。

二、設計要求

1）進程調度算法包括：時間片輪轉法，短作業(yè)優(yōu)先算法，動態(tài)優(yōu)先級算法。2）可選擇進程數(shù)量

3）本程序包括三種算法，用C語言實現(xiàn)，執(zhí)行時在主界面選擇算法（可用函數(shù)實現(xiàn)）（進程數(shù)，運行時間，優(yōu)先數(shù)由隨機函數(shù)產生）執(zhí)行，顯示結果。

三、設計思路及算法思想

1.界面菜單選項

一級菜單提供2個選項： ① 自動生成進程數(shù)量 ② 手動輸入所需進程數(shù)量

一級菜單選擇完畢后進入二級菜單： ① 重新生成進程 ② 時間片輪轉法 ③ 短作業(yè)優(yōu)先算法 ④ 動態(tài)優(yōu)先級算法 ⑤ 退出程序

2.調度算法

程序所用PCB結構體

需要用到的進程結構體如上圖所示

1)時間片輪轉法

主要是設置一個當前時間變量，curTime和時間片roundTime。

遍歷進程組的時候，每運行一個進程，就把curTime += roundTime。進程已運行時間加roundTime

2)短作業(yè)優(yōu)先算法

遍歷進程組，找到未運行完成并且運行時間最短的進程，讓它一次運行完成，如此往復，直到所有進程都運行完成為止。

3)動態(tài)優(yōu)先級算法

做法跟短作業(yè)優(yōu)先算法類似，此處主要是比較進程的優(yōu)先數(shù)，優(yōu)先級高者，先執(zhí)行。直到全部執(zhí)行完畢。當一個進程運行完畢后，適當增減其余進程的優(yōu)先數(shù)，以達到動態(tài)調成優(yōu)先級的效果。

3.程序流程圖

四、運行截圖

1）啟動后輸入5，生成5個進程

2）輸入1，選擇時間片輪轉法。

自動輸出結果，分別是時間片為1和4的結果

3）輸入2，選擇短作業(yè)優(yōu)先算法

4）輸入3，選擇動態(tài)優(yōu)先級算法

5）輸入0，重新生成進程，再輸入3，生成3個進程，選擇2.短作業(yè)優(yōu)先算法

6）輸入q，退出

五、心得體會

通過這次實驗，讓我對操作系統(tǒng)的進程調度有了更進一步的了解。這個實驗的模擬程度跟真實系統(tǒng)相比只是冰山一角，由此可見操作系統(tǒng)是何其復雜的軟件產品，僅進程調度就有那么豐富和內涵的知識需要掌握。

但是再復雜的系統(tǒng)，都是由小部件構成的。古語云：不積跬步,無以至千里。不積小流,無以成江海。掌握這些基礎的知識，可以為以后打下扎實的基礎。

六、附錄（源代碼）

//

// main.c

// ProcessDispatch //

// Created by Jeans on 1/5/15.// Copyright(c)2015 Jeans.All rights reserved.//

#include #include

//最小進程數(shù)

#define MIN_PROCESS //最大進程數(shù)

#define MAX_PROCESS

//最小優(yōu)先數(shù)

#define MIN_PRIORITY

0 //最大優(yōu)先數(shù)

#define MAX_PRIORITY

//最小運行時間

#define MIN_RUNNING_TIME

//最大運行時間

#define MAX_RUNNING_TIME

typedef struct PCB{

char name;

//進程名

int priority;

//優(yōu)先數(shù)

int runningTime;

//運行時間

int arriveTime;

//到達時間

int beginTime;

//開始時間

int finishTime;

//完成時間

int cyclingTime;

//周轉時間

double weigthCyclingTime;//帶權周轉時間

int hadRunTime;

//已經運行時間

int finish;

//是否完成 }PCB;//獲取隨機數(shù)

int GetRandomNumber(int min,int max){

return arc4random()%(max-min)+ min;}

//初始化PCB組

void InitPCBGroup(PCB p[],int num){

char name = 'A';

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

p[i].name = name;

p[i].priority = GetRandomNumber(MIN_PRIORITY, MAX_PRIORITY);

p[i].runningTime = GetRandomNumber(MIN_RUNNING_TIME,MAX_RUNNING_TIME);

name++;

} }

void PrintResult(PCB p[],int num){

double avgCycTime = 0,avgWeiCycTime = 0;

printf(“|進程名

到達時間

運行時間

開始時間

完成時間

周轉時間

帶權周轉時間

優(yōu)先數(shù)

|n”);

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

printf(“|%3c

%-4d

%-4d

%-4d

%-4d

%-4d

%-6.2f

%-4d|n”,p[i].name,p[i].arriveTime,p[i].runningTime,p[i].beginTime,p[i].finishTime,p[i].cyclingTime,p[i].weigthCyclingTime,p[i].priority);

avgCycTime += p[i].cyclingTime;

avgWeiCycTime += p[i].weigthCyclingTime;

//還原

p[i].arriveTime = 0;

p[i].beginTime = 0;

p[i].finishTime = 0;

p[i].cyclingTime = 0;

p[i].weigthCyclingTime = 0;

p[i].hadRunTime = 0;

p[i].finish = 0;

}

avgWeiCycTime /= num;

avgCycTime /= num;

printf(“平均周轉時間：%.2f

平均帶權周轉時間:%.2fn”,avgCycTime,avgWeiCycTime);} //時間片輪轉法

void RealRoundRobin(PCB p[],int num,int roundTime){

printf(“nn-----------------------------時間片：%d------n”,roundTime);

int finishNum = 0;

int curTime = 0;

while(finishNum!= num){

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

if(p[i].finish)continue;

//開始時間

if(p[i].beginTime == 0 && i!= 0){

p[i].beginTime = curTime;

}

//已經完成

if(p[i].hadRunTime + roundTime >= p[i].runningTime){

p[i].finishTime = curTime + p[i].runningTimep[i].arriveTime;

p[i].weigthCyclingTime = p[i].cyclingTime/(double)p[i].runningTime;

p[i].finish = 1;

finishNum ++;

curTime += p[i].runningTimep[min].arriveTime;

p[min].weigthCyclingTime = p[min].cyclingTime/(double)p[min].runningTime;

p[min].finish = 1;

finishNum++;

curTime = p[min].finishTime;

}

PrintResult(p, num);}

//動態(tài)優(yōu)先級算法

void DynamicPriorityFirst(PCB p[],int num){

printf(“nn-----------------------------動態(tài)優(yōu)先級算法--n”);

int finishNum = 0;

int curTime = 0;

while(finishNum!= num){

int min = 0;

//查找優(yōu)先級最高下標

for(int i = 1;i < num;i++){

if(p[i].finish == 0 && p[min].priority >= p[i].priority)

min = i;

else if(p[i].finish == 0 && p[min].finish == 1)

min = i;

}

p[min].beginTime = curTime;

p[min].hadRunTime = p[min].runningTime;

p[min].finishTime = p[min].beginTime + p[min].runningTime;

p[min].cyclingTime = p[min].finishTime-p[min].arriveTime;

p[min].weigthCyclingTime = p[min].cyclingTime/(double)p[min].runningTime;

p[min].finish = 1;

finishNum++;

curTime = p[min].finishTime;

}

PrintResult(p, num);}

int main(int argc, const char * argv[]){

PCB pcbGroup[30];

//pcb數(shù)組

int processNum = 0;//進程數(shù)

while(1){

//選擇進程數(shù)量

while(1){

if(processNum!= 0)

break;

printf(“n----------n”);

printf(“當前默認進程數(shù)范圍%d--%dn”,MIN_PROCESS,MAX_PROCESS);

printf(“1)輸入0可隨機生成進程數(shù)目n2)輸入%d-%d范圍內數(shù)字，回車，可生成指定數(shù)目進程n>>>>>>”,MIN_PROCESS,MAX_PROCESS);

int num = 0;

scanf(“%d”,&num);

if(num == 0){

processNum = GetRandomNumber(MIN_PROCESS, MAX_PROCESS);

break;

}else{

if((num >= MIN_PROCESS)&&(num <= MAX_PROCESS)){

processNum = num;

InitPCBGroup(pcbGroup,processNum);

break;

}else

printf(“n輸入有誤，請重新輸入.n”);

}

}

//選擇算法

printf(“n-----------------------------請輸入對應選項序號-----------------------------n”);

printf(“0.重新生成進程 | 1.時間片輪轉法 | 2.短作業(yè)優(yōu)先算法 | 3.動態(tài)優(yōu)先級算法 | q.退出n>>>>>>”);

char ch;

while((ch = getchar())== 'n');

switch(ch){

case '0'://0 重新生成進程

processNum = 0;break;

case '1'://1 時間片輪轉法

RoundRobin(pcbGroup, processNum);break;

case '2'://2 短作業(yè)優(yōu)先算法

ShortestJobFirst(pcbGroup, processNum);break;

case '3'://3 動態(tài)優(yōu)先級算法

DynamicPriorityFirst(pcbGroup,processNum);break;

case 'q'://q 退出

exit(0);

default:

break;

}

}

return 0;}

第二篇：操作系統(tǒng) 單處理機系統(tǒng)的進程調度

一.實驗內容描述

1.目的

（1）了解Windows內存管理器（2）理解Windows的地址過程 2.內容

任意給出一個虛擬地址，通過WinDbg觀察相關數(shù)據(jù)并找到其物理地址

二.理論分析

Windows采用頁式虛擬存儲管理技術管理內存，頁面是硬件級別上的最小保護單位 1.Windows內存管理器

Windows的內存管理主要由Windows執(zhí)行體中的虛存管理程序負責，并由環(huán)境子系統(tǒng)負責，并由環(huán)境子系統(tǒng)負責與具體API相關的一些用戶態(tài)特性的實現(xiàn)。虛存管理程序是Windows中負責內存管理的那些子程序和數(shù)據(jù)結構的集合 內存管理器的主要任務是：

地址變換：將一個進程的虛擬地址空間轉譯為物理內存地址

交換：當內存不足時，將內存中的有些內容轉移到磁盤上，并且以后還要再次將這些內容讀回

2.Windows內存管理策略

Windows采用頁式虛擬存儲管理技術管理內存，頁面是硬件級別上最小的保護單位。根據(jù)硬件的體系結構不同，頁面尺寸被分為兩種，大頁面和小頁面。X86系統(tǒng)下小頁面為4KB，大頁面為4MB。大頁面的優(yōu)點是：當引用同一頁面內其他數(shù)據(jù)時，地址轉移的速度會很快。不過使用大頁面通常要較大的內存空間，而且必須用一個單獨的保護項來映射，因此可能會造成出現(xiàn)錯誤而不引發(fā)內存訪問違例的情況。通常PC機都為小頁面 3.Windows虛擬地址空間布局 x86結構下的布局方式：

默認情況下，32位Windows系統(tǒng)中每個用戶進程可以占有2GB的私有地址空間。操作系統(tǒng)占有另外的2GB 2GB用戶的進程地址空間布局如表：

2GB的系統(tǒng)地址空間布局如同：

3.虛擬地址轉譯

地址轉譯是指將進程的虛擬地址空間映射到實際物理頁面的過程。x86系統(tǒng)中地址轉譯過程如圖：

關鍵數(shù)據(jù)結構如下： 頁目錄：每個進程都有一個頁目錄，它是內存管理器為了映射進程中所有的頁表位置而創(chuàng)建的一個頁面。進程也目錄的地址被保存在內核進程快KPROCESS中，在x86系統(tǒng)上，它被映射到虛擬地址0xC0300000，當一個進程正在執(zhí)行時，CPU可以通過寄存器CR3知道該進程頁目錄的位置。頁目錄由目錄項（PDE）構成，每個PDE長4字節(jié)，描述了該進程中所有可能的頁表的狀態(tài)和位置。其格式和PTE類似。x86系統(tǒng)上，要描述完整的4GB虛擬地址空間，需要1024個頁表。因此映射這些頁表的進程頁目錄需包含1024個PDE，恰好占用一個頁面。

頁表：進程的頁目錄項指向頁表。每個頁表占用一個頁面，由1024項PTE組成。一個有效的PTE大小為4字節(jié)，包含兩個主域：數(shù)據(jù)所在的物理頁面的頁面幀編號（PNF）或者內存中一個頁面的物理地址的PFN；一些描述該頁面狀態(tài)和保護屬性的標志。

虛擬地質結構：x86系統(tǒng)上，一個32位虛擬地址被解釋為三個單獨的部分，頁目錄索引、頁表索引和字節(jié)索引。由于頁目錄項有1024個，因此頁目錄索引為10位；一個也表中含有1024個PTE。因此頁表索引也為10位，字節(jié)索引為12位，正好表示一頁（4KB）內容

三.實驗步驟及結果

1.查找頁目錄首地址

以程序WG.exe作為觀測對象。

啟動WinDbg到內核調試模式，運行程序WG.exe。終斷目標機運行，輸入命令：kd>!process

發(fā)現(xiàn)WG.exe進程正處于運行狀態(tài) 輸入命令：

在KPROCESS中名為DirectoryTableBase的域，對應值為0x9fa6000，即WG.exe進程頁目錄的物理地址 查看CR3寄存其中的內容，輸入命令：

CR3寄存其中的值和KPROCESS中記錄的頁目錄基址相同。這是因為在CPU切換執(zhí)行任務時，其內容要更新為當前進程的頁目錄基址。2.地址轉譯過程

假設給定的虛擬地址為0x401001 輸入命令：

可以看到：

PDE的虛擬地址為C0300004.PTE的虛擬地址為C0001004 最后一行信息“pfn 9e4a---DA--UWEV”表示PDE中的具體內容，9e4a是給定虛擬地址所在頁表在內存中對應的物理頁號，“---DA—UWEV”是標志信息，“pfn a173----A--UREV”表示PTE中的具體內容，a173是數(shù)據(jù)頁裝入內存的物理頁號。

將數(shù)據(jù)頁對應的物理頁號a173加上業(yè)內索引（0x1）即可得到虛擬地址0x401001的物理地址

3.觀察系統(tǒng)頁表

給定觀測虛擬地址為0x80001001 輸入命令：

當前正在執(zhí)行的進程是：WG.exe 輸入命令：

得到PDE為C0300800，其對應的物理頁號為3b 繼續(xù)讓目標機運行，啟動A.exe，然后中斷目標機運行。輸入命令：

當前正在執(zhí)行的進程為A.exe 輸入命令：

PDE信息和對應的物理頁號與前面觀測到的相同

四.結論

1.數(shù)據(jù)頁對應的物理頁號加上相應業(yè)內索引即可得到虛擬地址的物理地址 2.不同的進程頁目錄都指向了相同的系統(tǒng)表頁

五.心得體會

在這次上機實驗，通過對WinDbg和VPc的調試運用，我熟悉了Windows內存管理器的結構，也認知到Windows如何進行地址轉譯和轉換。對相關的知識也進行了溫習，更牢的掌握了相關知識。當然這些還遠遠不夠，我以后還要繼續(xù)不斷努力，去學習了解掌握操作系統(tǒng)的各方面知識。

附錄：

1.A.exe代碼

#include #include

#define N 1

HANDLE mutexSemaphore;HANDLE synchSemaphore_1;HANDLE synchSemaphore_2;

HANDLE mutexDisplay;

void Display(char*str,int delayTime){ if(WaitForSingleObject(mutexDisplay,INFINITE)==WAIT_OBJECT_0){ printf(“%snn”,str);ReleaseMutex(mutexDisplay);Sleep(delayTime);} }

void useTime(double limit){ for(double i=0;i<=limit;i+=0.001);}

void CreateProduct(){ Display(“Creating a production...”,0);useTime(200000);Display(“Creating finished.”,100);}

void PutProduct(){ Display(“Putting a production...”,0);useTime(150000);Display(“Putting finished”,100);}

void GetProduct(){ Display(“Getting a production...”,0);useTime(100000);Display(“Getting finished.”,100);}

void ConsumeProduct(){ Display(“Cosuming a production...”,0);useTime(100000);Display(“Cosuming finished.”,100);}

void Producer(){ while(true){ CreateProduct();

if(WaitForSingleObject(synchSemaphore_1,INFINITE)==WAIT_OBJECT_0){

if(WaitForSingleObject(mutexSemaphore,INFINITE)==WAIT_OBJECT_0){ PutProduct();ReleaseSemaphore(mutexSemaphore,1,NULL);} ReleaseSemaphore(synchSemaphore_2,1,NULL);} } }

void Consumer(){ while(true){

if(WaitForSingleObject(synchSemaphore_2,INFINITE)==WAIT_OBJECT_0){

if(WaitForSingleObject(mutexSemaphore,INFINITE)==WAIT_OBJECT_0){ GetProduct();ReleaseSemaphore(mutexSemaphore,1,NULL);} ReleaseSemaphore(synchSemaphore_1,1,NULL);} ConsumeProduct();} }

int main(){ HANDLE thread[2];DWORD threadID[2];

synchSemaphore_1=CreateSemaphore(NULL,N,N,NULL);synchSemaphore_2=CreateSemaphore(NULL,0,N,NULL);mutexSemaphore=CreateSemaphore(NULL,1,1,NULL);

mutexDisplay=CreateMutex(NULL,FALSE,NULL);

printf(“Program start.Please use WinDbg to observe main thread.nPress any key to continue...n”);getchar();

thread[0]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(Producer),NULL,CREATE_SUSPENDED,&threadID[0]);printf(“A producer was created.Please use WinDbg to observe producer thread.nPress any key to continue...n”);getchar();

thread[1]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(Consumer),NULL,CREATE_SUSPENDED,&threadID[1]);printf(“A Consumer was created.Please use WinDbg to observe Consumer thread.nPress any key to continue...n”);getchar();

printf(“Please select:n[1]Make producer thread runn[2]Make Consumer thread runn”);bool flag=true;bool flag_1=true,flag_2=true;int count=0;while(flag){ if(getchar()=='1'&&flag_1){ ResumeThread(thread[0]);count++;flag_1=false;} else if(getchar()=='2'&&flag_2){ ResumeThread(thread[1]);count++;flag_2=false;} if(count==2)flag=false;} WaitForMultipleObjects(1,thread,TRUE,INFINITE);

return 0;}

2.WG.exe代碼： #include

int main(){ int a=0;printf(“I'm Wangn”);while(true){a++;} }

第三篇：操作系統(tǒng)課程設計-磁盤調度算法

1.實驗題目:

磁盤調度算法。

建立相應的數(shù)據(jù)結構；

在屏幕上顯示磁盤請求的服務狀況；

將一批磁盤請求的情況存磁盤文件，以后可以讀出并重放； 計算磁頭移動的總距離及平均移動距離； 支持算法：FIFO、SSTF、SCAN、CSCAN;

2.設計目的:

調度磁盤I/O請求服務，采用好的方式能提高訪問時間和帶寬。本實驗通過編程對磁盤調度算法的實現(xiàn)，加深對算法的理解，同時通過用C++語言編寫程序實現(xiàn)這些算法，并在windos平臺上實現(xiàn)，更好的掌握操作系統(tǒng)的原理以及實現(xiàn)方法，提高綜合運用專業(yè)課知識的能力。

3.任務及要求

3.1 設計任務

編程實現(xiàn)下述磁盤調度算法，并求出每種算法的平均尋道長度：

1、先來先服務算法（FCFS）

2、最短尋道時間算法（SSTF）

3、掃描算法（SCAN）

4、循環(huán)掃描算法（CSCAN）

3.2 設計要求

對用戶指定的磁盤調度請求序列，基于以上四種算法，實現(xiàn)各自的調度順序并輸出，同時計算出各種算法下的平均尋道長度。

4.算法及數(shù)據(jù)結構

4.1算法的總體思想

queue[n] 為請求調度序列，diskrode為磁盤磁道數(shù)，headstarts為正在調度的磁道

①先來先服務算法（FCFS）按queue[n]數(shù)組的順序進行磁盤調度，將前一個調度磁道與下一個調度磁道的差值累加起來，得到總的尋道長度，再除以n得到平均尋道長度。

②最短尋道時間優(yōu)先算法（SSTF）將queue[n]進行由小到大的排序，首先定位當前調度磁headstarts在queue[n]的位置，通過循環(huán)語句找出離起始磁頭最短的位置。

③掃描算法（SCAN）

將queue[n]進行由小到大的排序，首先定位當前調度磁headstarts在queue[n]的位置，然后在此位置按給定的方向遍歷queue[n]，當?shù)蓝它c（queue[0]或queue[n-1]）時，再在定位處反向遍歷到另一端。當調度磁道不在queue端點時，總的尋道長度為為前一個磁道與后一個磁

道差值的累加，當?shù)竭_端點且queue[n]未全調度時，總尋道長度加上端點值再加上下一個調度磁道的值，再按前面的算法進行，直到磁道全部都調度完畢，得到總的尋道長度，除以n得到平均尋道長度。

④循環(huán)掃描算法（CSCAN）將queue[n]進行由小到大的排序，首先定位當前調度磁headstarts在queue[n]的位置，然后在此位置按給定的方向遍歷queue[n]，當?shù)蓝它c（queue[0]或queue[n-1]）時，反向到另一端點再以此方向進行遍歷，直到queue[n]中所有都調度完。當調度磁道不在queue端點時，總的尋道長度為為前一個磁道與后一個磁道差值的累加，當?shù)竭_端點且queue[n]未全調度時，總尋道長度加上端點值再加上磁盤磁道總長度，再加上下一個調度磁道的值，再按前面的算法進行，直到磁道全部都調度完畢，得到總的尋道長度，除以n得到平均尋道長度。

5、源代碼：

#include #include #include void menu(){ cout<<“*********************菜單*********************”<

1、先來先服務算法（FCFS)**********”<

cout<<“******

2、最短尋道時間優(yōu)先算法(SSTF)**********”<

cout<<“******

3、掃描算法(SCAN)**********”<

cout<<“******

4、循環(huán)掃描算法(CSCAN)**********”<

cout<<“******

5、退出 **********”<

/*======================初始化序列=======================*/ void init(int queue[],int queue_copy[],int n){ int i;for(i=0;i

//對當前正在執(zhí)行的磁道號進行定位，返回磁道號小于當前磁道中最大的一個 int fix(int queue[], int n, int headstarts){ int i =0;while(iqueue[i]){ i++;} if(i>n-1)return n-1;//當前磁道號大于磁盤請求序列中的所有磁道 if(i==0)return-1;//當前磁道號小于磁盤請求序列中的所有磁道 else return i-1;//返回小于當前磁道號中最大的一個 } /*=================使用冒泡算法從小到大排序==============*/ int *bubble(int queue[],int m){ int i,j;int temp;for(i=0;i queue[j]){ temp=queue[i];queue[i]=queue[j];queue[j]=temp;} } cout<<“排序后的磁盤序列為：”;for(i=0;i

/* ====================以下是FCFS算法==================*/ void FCFS(int queue[],int n,int diskrode,int headstarts)//queue是請求調度序列，n為其個數(shù)，diskroad為磁盤磁道數(shù)，headstarts為正在調度的磁道 { cout<<“************以下為FCFS調度算法***********”<queue[0])count +=headstarts-queue[0];else count+=queue[0]-headstarts;cout<<“調度序列為: ”;cout<queue[i+1])count +=queue[i]-queue[i+1];else count +=queue[i+1]-queue[i];} cout<

/*=====================SSTF算法====================*/ void SSTF(int queue[], int n, int diskrode, int headstarts){ int k=1;int l,r;int i,j,count=0;queue =bubble(queue,n);cout<<“************以下為SSTF調度算法***********”<=0;i--)cout<=headstarts)//若當前磁道號小于請求序列中最小者，則直接由內向外依次給予各請求服務 { cout<<“磁盤掃描序列為： ”;cout<queue[0] && headstarts =0)&&(r

-headstarts)){ cout<=0;j--){ cout<

/*======================以下是SCAN算法====================*/ void SCAN(int queue[], int n, int diskrode, int headstarts){ int direction, i, fixi;cout<<“***********以下是SCAN調度算法*************”<>direction;double count=0;*bubble(queue,n);fixi = fix(queue,n,headstarts);cout<=0;i--){ cout<=0;i--)//從大到小 { cout<-1;i--){ cout<-1;i--)//從大到小 { cout<

/*======================以下是CSCAN算法====================*/ void CSCAN(int queue[],int n,int diskrode,int headstarts){ int direction,i,fixi;cout<<“***********以下是CSCAN調度算法*************”<>direction;int count=0;//count表示磁道移動的長度 *bubble(queue,n);fixi=fix(queue,n,headstarts);cout<<“調度序列為: ”<-1;--i){ cout<-1;--i){ cout<-1;i--){ cout<fixi;i--){ cout<

void main(){ int n, i, diskrode, headstarts;//n表示調度磁盤請求序列queue的長度，diskrode表示磁盤磁道的個數(shù)，headstarts表示目前正在調度的磁道； cout<<“請輸入磁盤的總磁道數(shù):”<> diskrode;cout<<“請輸入磁盤調度請求序列個數(shù):”<>n;int *queue;queue =(int*)malloc(n*sizeof(int));//給quneue數(shù)組分配空間...int *queue_copy;queue_copy =(int*)malloc(n*sizeof(int));cout<<“請依次輸入該序列的值:”<>queue[i];for(i=0;i>headstarts;int menux;menu();cout<<“請按菜單選擇，輸入相應的數(shù)字: ”;cin>>menux;while(menux!=0){ if(menux ==1)FCFS(queue,n,diskrode,headstarts);

if(menux ==2)SSTF(queue,n,diskrode,headstarts);

if(menux ==3)SCAN(queue,n,diskrode,headstarts);if(menux ==4)CSCAN(queue,n,diskrode,headstarts);if(menux ==5)cout<<“程序結束,謝謝使用！”<>menux;cout<

第四篇：操作系統(tǒng)課程設計,磁盤調度算法范文

沈陽理工大學課程設計專用紙 Noi

目 錄 1 課程設計目的及要求……………………………………………………錯誤！未定義書簽。2 相關知識…………………………………………………………………錯誤！未定義書簽。3 題目分析…………………………………………………………………2 4 概要設計…………………………………………………………………2 4.1 先來先服務（FCFS）的設計思想……………………………….2 4.2 最短尋道時間優(yōu)先調度（SSTF）的設計思想…………………..2 4.3 掃描算法（SCAN）的設計思想…………………………………2 4.4 循環(huán)掃描（CSCAN）的設計思想………………………………..2 5 代碼及流程………………………………………………………………3 5.1 流程圖……………………………………………………………...3 5.2 源代碼……………………………………………………………...8 6 運行結果…………………………………………………………………16 7 設計心得…………………………………………………………………19 參考文獻…………………………………………………………………………19

沈陽理工大學 沈陽理工大學課程設計專用紙 No1 1 課程設計目的及要求

設計目的：加深對操作系統(tǒng)原理的進一步認識，加強實踐動手能力和程序開發(fā)能力的培養(yǎng)，提高分析問題解決問題的能力，培養(yǎng)合作精神，以鞏固和加深磁盤調度的概念。操作系統(tǒng)是一門工程性很強的課程，它不僅要求學生掌握操作系統(tǒng)的工作原理和理論知識，也要求學生的實際動手能力，以加深對所學習內容的理解，使學生熟練地掌握計算機的操作方法，使用各種軟件工具，加強對課程內容的理解。這次課程設計，就是通過模擬磁臂調度來加深對操作系統(tǒng)中磁臂調度概念的理解。使學生熟悉磁盤管理系統(tǒng)的設計方法；加深對所學各種磁盤調度算法的了解及其算法的特點。

設計要求：編程序實現(xiàn)下述磁盤調度算法,并求出每種算法的平均尋道長度；要求設計主界面可以靈活選擇某算法，且以下算法都要實現(xiàn)

1、先來先服務算法（FCFS）

2、最短尋道時間優(yōu)先算法（SSTF）

3、掃描算法（SCAN）

4、循環(huán)掃描算法（CSCAN）相關知識

數(shù)據(jù)結構：數(shù)組 now:當前磁道號;

array[]:放置磁道號的數(shù)組;

void FCFS(int array[],int m)先來先服務算法(FCFS)void SSTF(int array[],int m)最短尋道時間優(yōu)先算法(SSTF)void SCAN(int array[],int m)掃描算法(SCAN)void CSCAN(int array[],int m)循環(huán)掃描算法(CSCAN)磁盤調度：當有多個進程都請求訪問磁盤時，采用一種適當?shù)尿寗诱{度算法，使各進程對磁盤的平均訪問（主要是尋道）時間最小。目前常用的磁盤調度算法有：1）閑來先服務2）最短尋道時間優(yōu)先3）掃描算法4）循環(huán)掃描算法等

沈陽理工大學 沈陽理工大學課程設計專用紙 No2 3 題目分析

選擇一個自己熟悉的計算機系統(tǒng)和程序設計語言模擬操作系統(tǒng)基本功能的設計方法及其實現(xiàn)過程

完成各分項功能。在算法的實現(xiàn)過程中，要求可決定變量應是動態(tài)可變的；同時模塊應該有一個合理的輸出結果。具體可參照實驗的程序模擬.各功能程序要求自行編寫程序實現(xiàn)，不得調用現(xiàn)有操作系統(tǒng)提供的模塊或功能函數(shù)。磁盤調度程序模擬。先來先服務調度算法.最短尋道時間優(yōu)先調度，循環(huán)（SCAN）調度算法。程序設計語言自選，最終以軟件（含源代碼以及執(zhí)行程序）和設計報告的形式提交課程設計結果.。磁盤調度讓有限的資源發(fā)揮更大的作用。在多道程序設計的計算機系統(tǒng)中，各個進程可能會不斷提出不同的對磁盤進行讀/寫操作的請求。由于有時候這些進程的發(fā)送請求的速度比磁盤響應的還要快，因此我們有必要為每個磁盤設備建立一個等待隊列。概要設計

1.先來先服務（FCFS）的設計思想

即先來的請求先被響應。FCFS策略看起來似乎是相當“公平”的，但是當請求的頻率過高的時候FCFS策略的響應時間就會大大延長。FCFS策略為我們建立起一個隨機訪問機制的模型，但是假如用這個策略反復響應從里到外的請求，那么將會消耗大量的時間。為了盡量降低尋道時間，看來我們需要對等待著的請求進行適當?shù)呐判颍皇呛唵蔚氖褂肍CFS策略。這個過程就叫做磁盤調度管理。有時候fcfs也被看作是最簡單的磁盤調度算法。

2.最短尋道時間優(yōu)先調度（SSTF）的設計思想

最短時間優(yōu)先算法選擇這樣的進程。要求訪問的磁道，與當前磁頭所在的磁道距離最近，以使每次的尋道時間最短。

3.掃描算法（SCAN）的設計思想

掃描（SCAN）調度算法:該算法不僅考慮到欲訪問 的磁道與當前磁道間的距離，更優(yōu)先考慮的是磁頭當前的移動方向。例如，當磁頭正在自里向外移動時，SCAN算法所考慮的下一個訪問對象，應是其欲訪問的磁道，既在當前磁道之外，又是距離最近的。這樣自里向外的訪問，直至再無更外的磁道需要訪問時，才將磁道換向自外向里移動。這時，同樣也是每次選擇這樣的進程來調度，也就是要訪問的當前位置內距離最近者，這樣，磁頭又逐步地從外向里移動，直至再無更里面的磁道要訪問，從而避免了出現(xiàn)“饑餓”現(xiàn)像。

4.循環(huán)掃描（CSACN）的設計思想

循環(huán)掃描（CSCAN）算法：當磁頭剛從里向外移動而越過了某一磁道時，恰好又有一進程請求訪問此磁道，這時，該里程就必須等待，為了減少這種延遲，CSCAN算法規(guī)定磁頭單向移動，而本實驗過程中我們所設計的是磁頭從里向外移動，而從外向里移動時只須改方向而已，本實驗未實現(xiàn)。但本實驗已完全能演示循環(huán)掃描的全過程。

沈陽理工大學 沈陽理工大學課程設計專用紙 No3 5 代碼及流程

1.先來先服務（FCFS）

圖 1—1 FCFS的流程圖

沈陽理工大學 沈陽理工大學課程設計專用紙 No4 2.最短尋道時間優(yōu)先調度（SSTF）

圖1—2 SSTF的流程圖

沈陽理工大學 沈陽理工大學課程設計專用紙 No5 3.掃描算法（SCAN）

圖1—3 SCAN的流程圖

沈陽理工大學 沈陽理工大學課程設計專用紙 No6 4.循環(huán)掃描（CSCAN）

圖1—4 CSCAN的流程圖

沈陽理工大學 沈陽理工大學課程設計專用紙 No7

圖1—5 主函數(shù)的流程圖

沈陽理工大學 沈陽理工大學課程設計專用紙 No8 源代碼：

#include“stdio.h” #include“stdlib.h” //#include“iostream.h” #define maxsize 100 //定義最大數(shù)組域

//先來先服務調度算法 void FCFS(int array[],int m){ int sum=0,j,i;int avg;printf(“n FCFS調度結果: ”);for(i=0;i

} avg=sum/(m-1);//計算平均尋道長度 printf(“n 移動的總道數(shù)： %d n”,sum);printf(“平均尋道長度： %d n”,avg);}

//最短尋道時間優(yōu)先調度算法 void SSTF(int array[],int m){ int temp;int k=1;int now,l,r;int i,j,sum=0;int avg;for(i=0;iarray[j])//兩磁道號之間比較 { temp=array[i];

沈陽理工大學 沈陽理工大學課程設計專用紙 No9 array[i]=array[j];array[j]=temp;} } } for(i=0;i

for(i=m-1;i>=0;i--)//將數(shù)組磁道號從大到小輸出 printf(“%d ”,array[i]);sum=now-array[0];//計算移動距離 } else if(array[0]>=now)//判斷整個數(shù)組里的數(shù)是否都大于當前磁道號 {

for(i=0;i=0)&&(r

printf(“%d ”,array[l]);sum+=now-array[l];//計算移動距離 now=array[l];l=l-1;} else

沈陽理工大學 沈陽理工大學課程設計專用紙 No10 {

printf(“%d ”,array[r]);sum+=array[r]-now;//計算移動距離 now=array[r];r=r+1;} } if(l=-1){

for(j=r;j

printf(“%d ”,array[j]);} sum+=array[m-1]-array[0];//計算移動距離 } else {

for(j=l;j>=0;j--){

printf(“%d ”,array[j]);} sum+=array[m-1]-array[0];//計算移動距離 } } avg=sum/m;printf(“n 移動的總道數(shù)： %d n”,sum);printf(“平均尋道長度： %d n”,avg);} //掃描算法

void SCAN(int array[],int m)//先要給出當前磁道號和移動臂的移動方向 { int temp;int k=1;int now,l,r,d;int i,j,sum=0;int avg;for(i=0;iarray[j])//對磁道號進行從小到大排列

沈陽理工大學 沈陽理工大學課程設計專用紙 No11 { temp=array[i];array[i]=array[j];array[j]=temp;} } } for(i=0;i

printf(“n SCAN調度結果: ”);for(i=m-1;i>=0;i--){ printf(“%d ”,array[i]);//將數(shù)組磁道號從大到小輸出 } sum=now-array[0];//計算移動距離 } else if(array[0]>=now)//判斷整個數(shù)組里的數(shù)是否都大于當前磁道號 {

printf(“n SCAN調度結果: ”);for(i=0;i

沈陽理工大學 沈陽理工大學課程設計專用紙 No12 { for(j=l;j>=0;j--){ printf(“%d ”,array[j]);} for(j=r;j=0;j--){ printf(“%d ”,array[j]);} sum=-now-array[0]+2*array[m-1];//計算移動距離 }//磁道號增加方向 } avg=sum/m;printf(“n 移動的總道數(shù)： %d n”,sum);printf(“平均尋道長度： %d n”,avg);}

//循環(huán)掃描算法

void CSCAN(int array[],int m){ int temp;int k=1;int now,l,r,d;int i,j,sum=0;int avg;for(i=0;iarray[j])//對磁道號進行從小到大排列

沈陽理工大學 沈陽理工大學課程設計專用紙 No13 { temp=array[i];array[i]=array[j];array[j]=temp;} } } for(i=0;i

printf(“n CSCAN調度結果: ”);for(i=0;i

printf(“%d ”,array[i]);//將磁道號從小到大輸出 } sum=now-array[0]+array[m-1];//計算移動距離 } else if(array[0]>=now)//判斷整個數(shù)組里的數(shù)是否都大于當前磁道號 {

printf(“n CSCAN調度結果: ”);for(i=0;i

printf(“%d ”,array[i]);//將磁道號從小到大輸出 } sum=array[m-1]-now;//計算移動距離 } else { while(array[k]

沈陽理工大學 沈陽理工大學課程設計專用紙 No14 { for(j=l;j>=0;j--){ printf(“%d ”,array[j]);} for(j=m-1;j>=r;j--){ printf(“%d ”,array[j]);} sum=2*(array[m-1]-array[0])-array[r]+now;//計算移動距離 }//磁道號減小方向 else { for(j=r;j

// 操作界面 int main(){ int c;FILE *fp;//定義指針文件

int cidao[maxsize];//定義磁道號數(shù)組 int i=0,count;fp=fopen(“cidao.txt”,“r+”);//讀取cidao.txt文件 if(fp==NULL)//判斷文件是否存在 { printf(“n 請 先 設 置 磁 道!n”);exit(0);} while(!feof(fp))//如果磁道文件存在

沈陽理工大學 沈陽理工大學課程設計專用紙 No15 { fscanf(fp,“%d”,&cidao[i]);//調入磁道號 i++;} count=i-1;printf(“n-------------------n”);printf(“ 10-11OS課程設計--磁盤調度算法系統(tǒng)n”);printf(“

計算機科學與技術二班n”);printf(“

姓名：宋思揚n”);printf(“

學號：0803050203n”);printf(“

電話：************n”);printf(“

2010年12月29日n”);printf(“n-------------------n”);printf(“n 磁道讀取結果：n”);for(i=0;i

1、先來先服務算法（FCFS）n”);printf(“

2、最短尋道時間優(yōu)先算法（SSTF）n”);printf(“

3、掃描算法（SCAN）n”);printf(“

4、循環(huán)掃描算法（CSCAN）n”);printf(“ 5.退出n”);printf(“n”);printf(“請選擇：”);scanf(“%d”,&c);if(c>5)break;switch(c)//算法選擇 { case 1: FCFS(cidao,count);//先來先服務算法 printf(“n”);break;case 2: SSTF(cidao,count);//最短尋道時間優(yōu)先算法 printf(“n”);break;case 3:

沈陽理工大學 沈陽理工大學課程設計專用紙 No16 SCAN(cidao,count);//掃描算法 printf(“n”);break;case 4: CSCAN(cidao,count);//循環(huán)掃描算法 printf(“n”);break;case 5: exit(0);} } return 0;} 6 運行結果

圖2—1 運行界面

沈陽理工大學 沈陽理工大學課程設計專用紙 No17

圖2—2 運行FCFS的界面

圖2—3 運行SSTF的界面

圖2—4 運行SCAN的界面

沈陽理工大學 沈陽理工大學課程設計專用紙 No18

圖2—5 運行SCAN的界面

圖2—6 運行CSCAN的界面

圖2—7 運行CSCAN的界面

沈陽理工大學 沈陽理工大學課程設計專用紙 No19 運行結果： 四種磁盤調度運行結果正確，與預期的相符。設計心得

此次操作系統(tǒng)的課程設計，從理論到實踐，在兩個星期的日子里，可以說是苦多于甜，但是可以學到很多很多的的東西，同時不僅可以鞏固了以前所學過的知識，而且學到了很多在書本上所沒有學到過的知識。通過這次課程設計使我懂得了理論與實際相結合是很重要的，只有理論知識是遠遠不夠的，只有把所學的理論知識與實踐相結合起來，從理論中得出結論，才能真正為社會服務，從而提高自己的實際動手能力和獨立思考的能力。

本次實驗首先要了解磁盤調度的工作原理及四種調度方法的工作原理。在課程設計前的準備工作時，先把這部分工作做完了。在設計總的程序框架的時候，要注意各功能模塊的位置，盡量做到簡潔、有序；各功能模塊與主程序要正確銜接。

在設計的過程中遇到許多問題，我設計的是四種調度算法中的后兩種。例如：在最初程序設計時主要有兩種構思：1）選用數(shù)據(jù)結構是鏈表的。2）選用數(shù)組。我最初嘗試了用鏈表，覺得方便易懂，但是在循環(huán)掃描處出現(xiàn)了些問題，后來又轉變了設計思路，選用了數(shù)組，直接進行排序，然后再聯(lián)系到各功能模塊。

同時在設計的過程中發(fā)現(xiàn)了自己的不足之處，對以前所學過的知識理解得不夠深刻，掌握得不夠牢固，自身知識的很多漏洞，看到了自己的實踐經驗還是比較缺乏，理論聯(lián)系實際的能力還急需提高。比如說編語言掌握得不好，應用程序編寫不太會……通過這次課程設計之后，一定把以前所學過的知識重新溫故。在此，也感謝在課程設計過程中幫我解惑的老師和同學。參考文獻

[1] 《操作系統(tǒng)》

人民郵電出版社

宗大華 宗濤 陳吉人 編著

[2] 《C語言程序設計》

清華大學出版社

馬秀麗 劉志嫵 李筠 編著 [3] 《操作系統(tǒng)實驗指導書》 沈陽理工大學

唐巍 菀勛 編著

沈陽理工大學

第五篇：操作系統(tǒng)課程設計報告

課程設計報告

題 目： 模擬請求頁式管理

課程名稱： 計算機操作系統(tǒng) 學 院： 信息工程學院

專 業(yè)： 計算機科學與技術

班 級： 14計本（1）學生姓名： * * * 學 號： 201403031** 指導教師： * * 成 績：

開課時間： 2016-2017 學年 一 學期

模擬請求頁式管理

第1章 需求分析

1.1設計要求

請求頁式管理是一種常用的虛擬存儲管理技術。本設計通過請求頁式存儲管理中頁面置換算法模擬設計，了解虛擬存儲技術的特點，掌握請求頁式管理的頁面置換算法。本實驗要求用Vc＋＋或其他高級語言編寫和調試。

編寫程序實現(xiàn)：

（1）先進先出頁面置換算法（FIFO）（2）最近最久未使用頁面置換算法（LRU）最佳置換頁面置換算法（OPT）設計一個虛擬存儲區(qū)和內存工作區(qū)，編程序演示以上三種算法的具體實現(xiàn)過程，并計算訪問命中率。

1.2解決方案

首先確定實現(xiàn)語言使用c#實現(xiàn)圖形化界面，后確定要實現(xiàn)哪些功能，比如算法選擇，頁面添加，模擬控制。然后確定輸出結構以便于程序的測試和驗證。將基本框架建立后再進行編程。編程前進行算法結構分析最后編程實現(xiàn)。

1.3算法實現(xiàn)原理

1、先進先出置換算法（FIFO）：

發(fā)生缺頁中斷時按照頁面進入內存順序總是淘汰最先進入內存的頁面。

2、最近最久未使用置換算法（LRU）：

發(fā)生缺頁中斷時總是淘汰存在內存中最長時間未被使用的頁面。

3、最佳置換算法（OPT）：

發(fā)生缺頁中斷時若一個或幾個頁面將來將不會被調用則按先進先出原則淘汰頁面，若將來都有調用則比較調用時刻選擇最遠時刻頁面淘汰。

4、缺頁率：缺頁次數(shù)占頁面調用次數(shù)的百分比。

第2章 概要設計

2.1數(shù)據(jù)設計

常變量：調用頁面最大數(shù)量（MaxN），內存最大頁面數(shù)（MaxM）待調用頁面數(shù)組：page_dd[MaxN]存放等待調用的頁面號

頁面數(shù)組專用指針 page_p，用于指向page_dd數(shù)組中正需調入內存的頁號 內存塊數(shù)組：Memery[MaxM]，存放內存當前存放的頁號 缺頁計數(shù)器：count，記錄缺頁次數(shù)

內存塊狀態(tài)數(shù)組：M1[MaxN],M2[MaxN],M3[MaxN]，記錄每次頁面調用結束后內存各塊的狀態(tài)

缺頁記錄數(shù)組s[MaxN]，用于記錄頁面調用時是否產生缺頁中斷，初始化為是

2.2函數(shù)設計

1、頁面添加函數(shù)：void btnAdd_Click(object sender, EventArgs e)用于實現(xiàn)通過點擊按鈕實現(xiàn)數(shù)據(jù)輸入。

2、內存初始化函數(shù)：init(int[] a, int[] b,int []m1,int[]m2,int[]m3)參數(shù)有頁面數(shù)組、內存數(shù)組、狀態(tài)數(shù)組，采用先進先出算法對內存先進行裝滿 服務于先進先出頁面置換函數(shù)和最佳置換函數(shù)。

3、輸出函數(shù)：void display(int[]a,int[]m1,int[]m2,int[]m3,char[]c)用于輸出模擬結果，參數(shù)有頁面數(shù)組，內存數(shù)組，狀態(tài)數(shù)組，缺頁記錄數(shù)組。再模擬之后調用。

4、模擬控制函數(shù)：void btnmo_Click(object sender, EventArgs e）用于實現(xiàn)通過單擊模擬按鈕，根據(jù)用戶所選算法進行模擬并顯示結果。

5、先進先出算法模擬函數(shù)：

void FIFO(int[] a, int[] b,int[]m1,int[]m2,int[]m3,char[] s)用于實現(xiàn)先進先出算法模擬，參數(shù)有頁面數(shù)組，內存數(shù)組、內存狀態(tài)記錄數(shù)組，缺頁記錄數(shù)組。在模擬函數(shù)中調用。

6、最近最久未使用算法模擬函數(shù)：

void LRU(int[] a, int[] b, int[] m1, int[] m2, int[] m3, char[] s)用于 3 實現(xiàn)最近最久未使用算法模擬，參數(shù)有頁面數(shù)組，內存數(shù)組，內存狀態(tài)記錄數(shù)組，缺頁記錄數(shù)組。在模擬函數(shù)中被調用。

7、最近最久未使用函數(shù)輔助函數(shù)：void LUR_I(int[] a,int e)用于對最近最久未使用算法中所用輔助數(shù)組（記錄頁面存在時長）進行調整，參數(shù)有輔助數(shù)組及需調整的數(shù)據(jù)下標。在最近最久未使用函數(shù)中調用。

8、最佳置換算法模擬函數(shù)：

void OPT(int[] a, int[] b, int[] m1, int[] m2, int[] m3, char[] s)用于模擬最佳置換算法。參數(shù)有頁面數(shù)組，內存數(shù)組，內存狀態(tài)記錄數(shù)組，缺頁記錄數(shù)組。在模擬函數(shù)中被調用。

9、最佳置換算法輔助函數(shù)：void OPT_F(int[] a, int e)用于對最佳置換算法中的輔助數(shù)組進行調整。參數(shù)有輔助數(shù)組，需調整數(shù)據(jù)下標。在最佳置換算法中被調用。

10、重置函數(shù)：void btncz_Click(object sender, EventArgs e)用于重新選擇算法進行新的模擬。

2.3主要算法設計

1、初始化函數(shù)算法：

第一步：將第一個頁面調入內存，調整最佳置換算法輔助數(shù)組，缺頁計數(shù)器加一，保存內存數(shù)組狀態(tài)。

第二步：調用下一個頁面并判斷內存中是否有本頁面有轉第三步，無轉第四步。第三步：更改缺頁數(shù)組對應下標值，記錄當前內存狀態(tài)，調整最佳置換算法輔助數(shù)組，頁面指針指向下一頁。

第四步：將頁面調入內存，調整最佳置換算法輔助函數(shù)，缺頁計數(shù)器加一，保存內存數(shù)組狀態(tài)。若內存尚不滿轉第一步。具體見圖1初始化算法流程圖。

開始頁面調入內存缺頁計數(shù)器加一記錄內存狀態(tài)調用下一頁否否內存是否有該頁面是記錄內存狀態(tài)修改缺頁數(shù)組內存已滿是結束

圖1 初始化算法流程圖

2、先進先出頁面置換算法：

第一步：檢查內存中是否已有需調用頁面，有則轉第二步，無則轉第三步。第二步：記錄當前內存狀態(tài)，修改缺頁數(shù)組對應下標值。

第三步：內存中無需要調用的頁面，進行出隊操作，然后進行入隊操作，記錄內存塊狀態(tài)，缺頁計數(shù)器加一。

第四步：若頁面數(shù)組未被調用結束轉第一步。具體見圖2先進先出算法流程圖。

開始頁面調入內存該頁在內存中是否已存在是否否先出隊操作后入隊操作記錄內存狀態(tài)修改缺頁數(shù)組值記錄內存狀態(tài)缺頁計數(shù)器加一頁面調用結束是結束

圖2 先進先出算法流程圖

3、最近最久未使用置換算法：

第一步：將頁面調入內存，記錄內存狀態(tài)，缺頁計數(shù)器加一，調整輔助數(shù)組，頁面指針加一。

第二步：檢查內存中是否已有所需頁面，有轉第三步，無轉第一步。

第三步：修改缺頁數(shù)組對應下標記錄，記錄內存狀態(tài)，調整輔助數(shù)組，頁面指針加一。第四步：內存是否已滿，無則轉第一步，是則轉第五步。

第五步：檢查內存中是否有所需頁面，有則記錄當前內存狀態(tài)，修改缺頁數(shù)組對應下標值。無則轉第六步。

第六步：檢查輔助數(shù)組找出最大值并記錄其下標，置換內存中對應下標的數(shù)據(jù)，調整輔助數(shù)組，缺頁計數(shù)器加一。

第七步：頁面是否調用結束未結束則轉第五步。具體見圖3最近最久未使用算法流程圖。

開始調入頁面至內存記錄內存狀態(tài)計數(shù)器加一否調整輔助數(shù)組調用下一頁內存中是否已有該頁否內存已滿是通過輔助數(shù)組確定淘汰頁面是修改缺頁數(shù)組記錄內存狀態(tài)調整輔助數(shù)組否頁面置換記錄內存狀態(tài)計數(shù)器加一調用結束是結束

圖3 最近最久未使用算法

4、最佳置換算法：

第一步：檢查內存中是否已有所需頁面，有則記錄內存狀態(tài)，修改缺頁數(shù)組對應下標數(shù)值。無則轉第二步。

第二步：判斷內存中各頁面的未來調用情況，記錄是否還有調用，若有則記錄調用時刻。

第三步：分析調用情況，內存中頁面都在將來不會被調用轉第四步，有一個被調用轉第五步，有兩個被調用轉第六步，全被調用轉第七步。

第四步:查找輔助數(shù)組找到內存中存在時間最長的頁面進行置換，修改內存狀態(tài)，缺頁計數(shù)器加一，修改輔助數(shù)組。

第五步：查找到不會被調用的頁面，并根據(jù)輔助數(shù)組選擇最早進入內存的頁面將其置換。修改內存狀態(tài)，缺頁計數(shù)器加一，修改輔助數(shù)組。

第六步：查找輔助數(shù)組找到將來不需要在調用的頁面將其置換，修改輔助數(shù)組，記錄內存狀態(tài)，缺頁計數(shù)器加一。

第七步：查找輔助數(shù)組，找尋最晚被調用的頁面，將其置換。記錄內存狀態(tài)，修改輔助數(shù)組，缺頁計數(shù)器加一。

第八步：頁面是否調用完成，否則轉第一步。具體見圖4最佳置換算法流程圖

開始調入頁面記錄內存狀態(tài)計數(shù)器加一更新輔助函數(shù)是頁面已存在否向后檢查內存當前頁面調用情況所有頁面都不會再度調用否是一個頁面會調用否否是兩個頁面會調用是否查找輔助數(shù)組得到最先進入頁面通過輔助數(shù)組得到不會再調用的頁面通過輔助數(shù)組獲取最晚調用的頁面通過輔助數(shù)組得到另外兩個頁面中最先進入的頁面置換頁面記錄內存狀態(tài)計數(shù)器加一更新輔助函數(shù)頁面調用結束是結束

圖4 最佳置換算法流程圖 2.4界面設計

采用c# 設計windows窗體應用程序，使用下拉列表框選擇算法，通過按鈕添加待調用的頁面。通過文本控件顯示模擬結果。顯示樣式：第一行：算法名稱；

第二行：調用頁面順序；

第三行至第五行顯示內存在每調用一次頁面后的狀態(tài)；

第六行：是否缺頁；

最后一行顯示缺頁率；

第3章 詳細設計與實現(xiàn)

3.1函數(shù)設計

1、添加按鈕功能實現(xiàn)代碼

主要功能：實現(xiàn)單擊一次添加一個調用頁面，并給出相應的提示，如正在輸入的是第幾次調度頁面，在輸入為空時能夠彈出對話框提示用戶，在輸入完成時為避免數(shù)組越界應在輸入完成時隱藏；輸入過程中始終保證時輸入焦點。private void btnAdd_Click(object sender, EventArgs e){ if(txtAdd.Text!= “")//輸入不為空才能繼續(xù)輸入 { page_dd[i_add] = Convert.ToInt32(txtAdd.Text);/*將輸入值賦值給頁面數(shù)組*/ txtShow.Text += txtAdd.Text + ” “;/*顯示供用戶查閱*/ i_add++;txtAdd.Clear();/*清空*/ if(i_add == MaxN)//輸入結束時 { txtAdd.ReadOnly = true;//不允許繼續(xù)輸入 btnAdd.Hide();//按鈕隱藏 return;} txtAdd.Focus();//設置為輸入焦點

label2.Text = ”第“ +(i_add + 1)+ ”次調度頁面：“;/*提示用戶正在輸入的是第幾次調度頁面*/ } /*輸入為空則彈出對話框提示用戶輸入為空*/ else { MessageBox.Show(”請輸入調用頁面！“, ”輸入為空“, MessageBoxButtons.OK, MessageBoxIcon.Warning);txtAdd.Focus();} }

2、初始化函數(shù)

主要功能：將內存一先進先出方式填滿，并記錄每個頁面進入時間，服務于先進先出頁面置換算法和最佳置換算法。

void init(int[] a, int[] b,int []m1,int[]m2,int[]m3){ /*內存未滿時循環(huán)*/ for(int i = 0;i < MaxM&&page_p

//調整輔助數(shù)組將剛進入內存的頁面的對應時間 OPT_F(O_Q ,i)； count++;//缺頁計數(shù)器加一 m1[page_p] = b[0];//保存內存狀態(tài) m2[page_p] = b[1];m3[page_p] = b[2];page_p++;//調用下一頁面

//檢查內存中是否原先就有需要的頁面； for(int j = 0;j <= i&&page_p

s[page_p] = 'F';//缺頁數(shù)組對應數(shù)據(jù)更改 m1[page_p] = b[0];//記錄內存狀態(tài) m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q,-1);//調整最佳置換算法輔助函數(shù) page_p++;//調用下一頁 j =-1;//重新開始尋找 } } } }

3、先進先出頁面置換函數(shù)

主要功能：根據(jù)先進先出算法要求在產生缺頁中斷時采用先進先出方式確定淘汰頁面，并在每次頁面調用時記錄下內存狀態(tài)，缺頁次數(shù)；采用循環(huán)隊列使得每次出隊的一定是最先進入內存的。

private void FIFO(int[] a, int[] b,int[]m1,int[]m2,int[]m3,char[] s){ int Fpage_p = page_p;int front, rear;//定義隊列對手和對尾指針并初始化 front = 0;rear = MaxM1;int sa;for(;Fpage_p < MaxN;Fpage_p++){ sa = 0;for(int i = 0;i < MaxM;i++)//檢查內存中是否已有要調用的頁面。

{ if(b[i] == a[Fpage_p]){ m1[Fpage_p] = b[0];m2[Fpage_p] = b[1];m3[Fpage_p] = b[2];s[Fpage_p] = 'F';sa = 1;break;} } if(sa == 0){ front =(front + 1)% MaxM;

rear =(rear + 1)% MaxM;b[rear] = a[Fpage_p];m1[Fpage_p] = b[0];m2[Fpage_p] = b[1];m3[Fpage_p] = b[2];count++;} else continue;} } /*最近最久未使用算法輔助數(shù)組調整函數(shù)*/ private void LUR_I(int[] a,int e){ int temp;temp = a[e];a[e] = 1;for(int i = 0;i < MaxM;i++){ if(a[i] < temp && i!=e)a[i]++;} } /*最佳置換算法輔助數(shù)組調整函數(shù)*/ private void OPT_F(int[] a, int e){ if(e!=-1){ a[e] = 0;for(int i = 0;i < MaxM;i++){ if(i!= e)a[i]++;} } else for(int i = 0;i < MaxM;i++){ a[i]++;} } /*最近最久未使用算法*/ private void LRU(int[] a, int[] b, int[] m1, int[] m2, int[] m3, char[] s){

int[] L_Q = new int[MaxM]{3,3,3};int sa;for(int i = 0;i < MaxM && page_p < MaxN;i++){ b[i] = a[page_p];//調入內存 count++;m1[page_p] = b[0];//保存內存狀態(tài) m2[page_p] = b[1];m3[page_p] = b[2];LUR_I(L_Q, i);page_p++;for(int j = 0;j <= i && page_p < MaxN;j++){ if(b[j] == a[page_p]){ s[page_p] = 'F';m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];LUR_I(L_Q, j);page_p++;j =-1;} } } for(;page_p < MaxN;page_p++){ sa = 0;for(int i = 0;i < MaxM;i++)//用的頁面。{ if(b[i] == a[page_p]){ m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];s[page_p] = 'F';LUR_I(L_Q, i);sa = 1;break;} } if(sa == 0){

檢查內存中是否已有要調40 for(int i = 0;i < MaxM;i++){ if(L_Q[i] == 3){ b[i] = a[page_p];m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];LUR_I(L_Q, i);break;} } count++;} else continue;} } /*最佳置換算法*/ private void OPT(int[] a, int[] b, int[] m1, int[] m2, int[] m3, char[] s){ int sa;int O_p;int Ocount;int[] OPT_I=new int [MaxM ]{-1 ,-1 ,-1 };int[] OPT_J=new int [MaxM]{MaxN ,MaxN ,MaxN };for(;page_p < MaxN;page_p++){ for(int i = 0;i < MaxM;i++){ OPT_I[i] =-1;//刷新狀態(tài)數(shù)組 OPT_J[i] = MaxN;} sa = 0;for(int i = 0;i < MaxM;i++)//檢查內存中是否已有要調用的頁面。

{

if(b[i] == a[page_p]){ m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q,-1);

s[page_p] = 'F';sa = 1;break;} } if(sa == 0)//缺頁 { Ocount = 0;for(int i = 0;i < MaxM;i++){ O_p = page_p + 1;for(;O_p < MaxN;O_p++){ if(b[i] == a[O_p]){ Ocount++;OPT_I[i] = 1;OPT_J[i] = O_p;break;} } } switch(Ocount){ case 0://全部頁面以后都不會再度調用 int temp = 0;for(int i = 0;i < MaxM;i++){ if(O_Q[i] > O_Q[temp])temp = i;} b[temp] = a[page_p];m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q ,temp);count++;break;case 1://有一個頁面將在以后調用 temp = 0;for(int i = 0;i < MaxM;i++){ if(OPT_I[i]!= 1 && O_Q[i] > O_Q[temp])temp = i;

} b[temp] = a[page_p];m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q ,temp);count++;break;case 2: for(int i = 0;i < MaxM;i++){ if(OPT_I[i] ==-1){ b[i] = a[page_p];m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q, i);count++;} } break;case 3: int p = 0;for(int i = 0;i < MaxM;i++){ if(OPT_J[i] >OPT_J[p])p = i;} b[p] = a[page_p];m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q, p);count++;break;} } } } /*重置函數(shù)*/ private void btncz_Click(object sender, EventArgs e){ comboBox1.SelectedIndex = 0;

txtAdd.Text = ”“;page_p = 0;i_add = 0;count = 0;//txtShow.Text = ”";for(int i = 0;i < MaxM;i++)Memery[i] =-1;for(int i = 0;i < MaxN;i++)s[i] = 'T';} } }