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

1、.成績 課程設(shè)計(jì)報(bào)告 題 目 操作系統(tǒng)算法設(shè)計(jì) 課 程 名 稱 操作系統(tǒng)課程設(shè)計(jì) 院 部 名 稱 計(jì)算機(jī)工程學(xué)院 專 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 班 級(jí) 14計(jì)算機(jī)科學(xué)與技術(shù)單 學(xué) 生 姓 名 邵佳楠 學(xué) 號(hào) 141320100 課程設(shè)計(jì)地點(diǎn) A107 課程設(shè)計(jì)學(xué)時(shí) 20學(xué)時(shí) 指 導(dǎo) 教 師 潘 金陵科技學(xué)院教務(wù)處制目 錄摘 要1一、課程設(shè)計(jì)的目的和要求3二、系統(tǒng)需求分析3三、總體設(shè)計(jì)3四、詳細(xì)設(shè)計(jì)4五、測試、調(diào)試過程7六、結(jié)論與體會(huì)16附錄：源程序17摘 要32一、課程設(shè)計(jì)的目的和要求33二、系統(tǒng)需求分析33三、總體設(shè)計(jì)33四、詳細(xì)設(shè)計(jì)33五、測試、調(diào)試過程34六、結(jié)論與體會(huì)38附錄：源程序39摘

2、 要47一、設(shè)計(jì)的目的和要求48二、系統(tǒng)需求分析48三、總體設(shè)計(jì)48四、詳細(xì)設(shè)計(jì)48五、測試、調(diào)試過程50六、結(jié)論與體會(huì)54附錄：源程序55操作系統(tǒng)算法設(shè)計(jì)-進(jìn)程調(diào)度程序摘 要隨著計(jì)算機(jī)的普及，人們生活得到極大改善，人們?cè)诰穹矫嬉餐瑯有枰岣?，所以越來越多的人進(jìn)行著各種各樣的學(xué)習(xí)。操作系統(tǒng)是計(jì)算機(jī)中最重要的環(huán)節(jié)之一，也是計(jì)算機(jī)專業(yè)學(xué)生的一門重要的專業(yè)課程。操作系統(tǒng)的好壞，直接影響整個(gè)計(jì)算機(jī)系統(tǒng)的性能和用戶對(duì)計(jì)算機(jī)的使用。一個(gè)精心設(shè)計(jì)的操作系統(tǒng)能極大的擴(kuò)展計(jì)算機(jī)的功能，充分發(fā)揮系統(tǒng)中的各種設(shè)備的使用效率，提高系統(tǒng)的可靠性。由于操作系統(tǒng)中各種軟硬件資源的管理，內(nèi)容比較繁瑣，具有很強(qiáng)的實(shí)踐性，要學(xué)

3、好這門課程，必須把理論和時(shí)間緊密結(jié)合，才能取得較好的學(xué)習(xí)效果。本次課程設(shè)計(jì)師在學(xué)習(xí)完操作系統(tǒng)教程后，進(jìn)行的一次全面的綜合訓(xùn)練，通過課程設(shè)計(jì)，讓學(xué)生更好的掌握操作系統(tǒng)的原理以及實(shí)現(xiàn)方法，加深對(duì)操作系統(tǒng)基礎(chǔ)理論和重要算法的理解，加強(qiáng)對(duì)學(xué)生的動(dòng)手能力。熟悉“最高優(yōu)先級(jí)優(yōu)先調(diào)度算法”、“基于時(shí)間片輪轉(zhuǎn)法”、“多級(jí)反饋隊(duì)列調(diào)度算法”、“最高優(yōu)先級(jí)優(yōu)先算法”，雖然不用全部每一個(gè)都弄清楚，但是了解其中的算法思想也是有好處的。關(guān)鍵詞：最高優(yōu)先級(jí)優(yōu)先調(diào)度算法、基于時(shí)間片輪轉(zhuǎn)法、多級(jí)反饋隊(duì)列調(diào)度算法、最高優(yōu)先級(jí)優(yōu)先算法 一、 課程設(shè)計(jì)的目的和要求程序能夠完成以下操作：創(chuàng)建進(jìn)程：先輸入進(jìn)程的數(shù)目，再一次輸入每個(gè)進(jìn)程

4、的進(jìn)程名、運(yùn)行總時(shí)間和優(yōu)先級(jí)，先到達(dá)的先輸入；進(jìn)程調(diào)度：進(jìn)程創(chuàng)建完成后就選擇進(jìn)程調(diào)度算法，并單步執(zhí)行，每次執(zhí)行的結(jié)果都從屏幕上輸出來。二、系統(tǒng)需求分析在多道程序系統(tǒng)中，一個(gè)作業(yè)被提交后必須經(jīng)過處理機(jī)調(diào)度后，方能獲得處理機(jī)執(zhí)行。對(duì)于批量型作業(yè)而言，通常需要經(jīng)歷作業(yè)調(diào)度（又稱高級(jí)調(diào)度或長程調(diào)度）和進(jìn)程調(diào)度（又稱低級(jí)調(diào)度或短程調(diào)度）兩個(gè)過程后方能獲得處理機(jī)；對(duì)于終端型作業(yè)，則通常只需經(jīng)過進(jìn)程調(diào)度即可獲得處理機(jī)。在較完善的操作系統(tǒng)中，為提高內(nèi)存的利用率，往往還設(shè)置了中級(jí)調(diào)度（又稱中程調(diào)度）。對(duì)于上述的每一級(jí)調(diào)度，又都可采用不同的調(diào)度方式和調(diào)度算法。三、總體設(shè)計(jì)編寫進(jìn)程調(diào)度程序，“最高優(yōu)先級(jí)優(yōu)先”算法常

5、用語批處理系統(tǒng)中，在進(jìn)程調(diào)度中，每次調(diào)度時(shí)，系統(tǒng)把處理機(jī)給就緒隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程。在非搶占式優(yōu)先級(jí)算法下系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程后，這個(gè)進(jìn)程就會(huì)一直運(yùn)行，直到完成或發(fā)生某事件使它放棄處理機(jī)，這時(shí)系統(tǒng)才能重新將處理機(jī)分配給就緒隊(duì)列中的理你個(gè)優(yōu)先級(jí)最高的進(jìn)程。靜態(tài)優(yōu)先級(jí)是在創(chuàng)建進(jìn)程時(shí)確定的，并在整個(gè)運(yùn)行期間不再改變。動(dòng)態(tài)優(yōu)先級(jí)是指進(jìn)程的優(yōu)先級(jí)在創(chuàng)建進(jìn)程時(shí)可以給定一個(gè)初始值，并且可以按一定原則修改優(yōu)先級(jí)。“輪轉(zhuǎn)法”算法中，系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則，排成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。時(shí)間片的大小從幾ms到幾百ms。當(dāng)執(zhí)行的

6、時(shí)間片用完時(shí)，由一個(gè)計(jì)時(shí)器發(fā)出時(shí)鐘中斷請(qǐng)求，調(diào)度程序便據(jù)此信號(hào)來停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾;然后，再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。這樣就可以保證就緒隊(duì)列中的所有進(jìn)程，在一給定的時(shí)間內(nèi)，均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間。 “多級(jí)反饋隊(duì)列調(diào)度”算法中，進(jìn)程在進(jìn)入待調(diào)度的隊(duì)列等待時(shí)，首先進(jìn)入優(yōu)先級(jí)最高的隊(duì)列等待。先調(diào)度優(yōu)先級(jí)高的隊(duì)列中的進(jìn)程，若高優(yōu)先級(jí)中隊(duì)列中已沒有調(diào)度的進(jìn)程，則調(diào)度次優(yōu)先級(jí)隊(duì)列中的進(jìn)程。對(duì)于同一個(gè)隊(duì)列中的各個(gè)進(jìn)程，按照時(shí)間片輪轉(zhuǎn)法調(diào)度。在低優(yōu)先級(jí)的隊(duì)列中的進(jìn)程在運(yùn)行時(shí)，又有新到達(dá)的作業(yè)，那么在運(yùn)行完這個(gè)時(shí)間片后，CPU馬上分配給新到

7、達(dá)的作業(yè)（搶占式）。最高優(yōu)先級(jí)優(yōu)先算法:從鍵盤輸入若干個(gè)進(jìn)程，進(jìn)程包括進(jìn)程名，進(jìn)程優(yōu)先級(jí)，進(jìn)程運(yùn)行時(shí)間。就緒隊(duì)列按照優(yōu)先級(jí)從高到低排列，進(jìn)程調(diào)度中，獲取就緒隊(duì)列隊(duì)首進(jìn)程，即優(yōu)先級(jí)最高的進(jìn)程，在進(jìn)程獲得一次CPU后，就將該進(jìn)程的優(yōu)先級(jí)減1。重新排列就緒隊(duì)列，獲取就緒隊(duì)列隊(duì)首進(jìn)程進(jìn)行調(diào)度。四、詳細(xì)設(shè)計(jì)進(jìn)程調(diào)度程序中，靜態(tài)優(yōu)先級(jí)算法的基本原理與簡單輪轉(zhuǎn)調(diào)度的算法還有多級(jí)反饋調(diào)度算法相似，都是先用戶輸入進(jìn)程信息、對(duì)用戶輸入的進(jìn)程按優(yōu)先級(jí)排序，然后輸出就緒隊(duì)列中的進(jìn)程、輸出正在運(yùn)行的進(jìn)程、輸出已完成的進(jìn)程、靜態(tài)優(yōu)先級(jí)算法，區(qū)別在于簡單輪轉(zhuǎn)調(diào)度算法多一個(gè)對(duì)用戶輸入的進(jìn)程按FCFS排序。動(dòng)態(tài)優(yōu)先級(jí)算法是根據(jù)

8、靜態(tài)優(yōu)先級(jí)算法進(jìn)行更改，總體差不多只是相對(duì)靈活性更加靈活。而多級(jí)反饋調(diào)度算法是按優(yōu)先級(jí)排序，整體上差不多。下面是各個(gè)算法的程序流程圖：初始化是否開始輸入進(jìn)程按優(yōu)先級(jí)高低排入就緒隊(duì)列中是否繼續(xù)輸入進(jìn)程就緒隊(duì)列是否為空獲取就緒隊(duì)列隊(duì)首進(jìn)程進(jìn)程獲得一個(gè)CPU該進(jìn)程是否完成按優(yōu)先級(jí)高低插入就緒隊(duì)列中釋放進(jìn)程節(jié)點(diǎn)結(jié)束NYYNNYYN圖1.1 最高優(yōu)先級(jí)優(yōu)先算法流程圖初始化是否開始輸入進(jìn)程按先來先服務(wù)排入就緒隊(duì)列中是否繼續(xù)輸入進(jìn)程就緒隊(duì)列是否為空獲取就緒隊(duì)列隊(duì)首進(jìn)程進(jìn)程在時(shí)間片T內(nèi)運(yùn)行該進(jìn)程是否完成排入就緒隊(duì)列隊(duì)尾釋放進(jìn)程節(jié)點(diǎn)結(jié)束NYYNNYYN圖1.2 簡單輪轉(zhuǎn)法優(yōu)先算法流程圖初始化退出系統(tǒng)選擇功能菜單

9、輸入進(jìn)程是否繼續(xù)輸入按先來先服務(wù)算法插入就緒第一隊(duì)列是否完成獲取最高優(yōu)先隊(duì)列隊(duì)首進(jìn)程，若為空，則，尋在下一隊(duì)列該進(jìn)程獲取CPU的一個(gè)時(shí)間片時(shí)間釋放進(jìn)程節(jié)點(diǎn)把該進(jìn)程插入所在隊(duì)列（n）的下一個(gè)隊(duì)列（n+1）的隊(duì)尾是否找到進(jìn)程圖1.3 多級(jí)反饋調(diào)度算法流程圖五、測試、調(diào)試過程在靜態(tài)優(yōu)先級(jí)調(diào)度算法中，判斷出了在運(yùn)用getch()的時(shí)候需要頭文件#include <conio.h>這一項(xiàng)的。動(dòng)態(tài)優(yōu)先級(jí)算法在根據(jù)靜態(tài)優(yōu)先級(jí)算法的基礎(chǔ)上改的整體的框架沒有改變，簡單輪轉(zhuǎn)調(diào)度算法、多級(jí)反饋調(diào)度算法和靜態(tài)優(yōu)先級(jí)調(diào)度算法都有一個(gè)通用的問題就是conio.h，在編寫程序的過程中要熟悉系統(tǒng)文件的頭文件對(duì)應(yīng)的

10、功能。下面是各個(gè)程序的運(yùn)行結(jié)果：靜態(tài)優(yōu)先級(jí)調(diào)度算法：動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法：簡單輪轉(zhuǎn)調(diào)度算法：多級(jí)反饋調(diào)度算法：六、結(jié)論與體會(huì)在運(yùn)行的這幾個(gè)程序中，普遍的問題就是缺少頭文件，或者是系統(tǒng)的函數(shù)在沒有弄清楚的情況下沒有注意分開。操作系統(tǒng)這門課與實(shí)際運(yùn)用聯(lián)系也是很大的，比如銀行家算法，雖然課程設(shè)計(jì)里面沒有做到。在程序的幾個(gè)調(diào)度算法中其實(shí)也可以看到現(xiàn)實(shí)的例子，比如進(jìn)程調(diào)度，我們可以把他設(shè)計(jì)成一個(gè)公司內(nèi)部管理調(diào)度，其性質(zhì)和原理其實(shí)是一樣的并沒有什么太大的區(qū)別。在這門課上我學(xué)習(xí)到了如何獨(dú)立自主的面對(duì)程序調(diào)試運(yùn)行出現(xiàn)的問題。冷靜的思考是很有必要的。附錄：源程序進(jìn)程調(diào)度程序/靜態(tài)優(yōu)先級(jí)調(diào)度算法.c#include

11、 <stdio.h>#include <conio.h>#include <string.h>#define MAX 24struct pcb/建立進(jìn)程控制塊char pname10;int priority;int reachtime;int needtime;int usecputime;char status;typedef struct pcb PCB;void inputpcb(PCB pcb,int *n)/用戶輸入進(jìn)程信息int i;int num;printf("n請(qǐng)輸入進(jìn)程個(gè)數(shù)");scanf("%d"

12、;,&num);for(i=0;i<num;i+)printf("n請(qǐng)輸入第%d個(gè)進(jìn)程的名稱:",i+1);scanf("%s",pcbi.pname);printf("n請(qǐng)輸入第%d個(gè)進(jìn)程的優(yōu)先級(jí):",i+1);scanf("%d",&pcbi.priority);printf("n進(jìn)程的默認(rèn)到達(dá)時(shí)間為O.n");printf("n請(qǐng)輸入第%d個(gè)進(jìn)程的運(yùn)行時(shí)間:",i+1);scanf("%d",&pcbi.needtime

13、);pcbi.reachtime=0;pcbi.usecputime=0;pcbi.status='r'*n=num;void paixupcb(PCB pcb,int n)/對(duì)用戶輸入的進(jìn)程按優(yōu)先級(jí)排序int i,j;PCB pcbtemp;for(i=0;i<n-1;i+)for(j=i+1;j<n;j+)if(pcbi.priority<pcbj.priority)pcbtemp=pcbi;pcbi=pcbj;pcbj=pcbtemp;void printpcb(PCB pcb,int n)/輸出就緒隊(duì)列中的進(jìn)程int i;printf("n進(jìn)

14、程名 優(yōu)先級(jí) 到達(dá)時(shí)間 需要運(yùn)行時(shí)間 已用CPU時(shí)間 進(jìn)程狀態(tài)");for(i=0;i<n;i+)if(pcbi.status!='F')printf("n %s %d %d %d %d %c",pcbi.pname,pcbi.priority,pcbi.reachtime,pcbi.needtime,pcbi.usecputime,pcbi.status);printf("n");void printRpcb(PCB pcb,int n)/輸出正在運(yùn)行的進(jìn)程int i;printf("n進(jìn)程名 優(yōu)先級(jí) 到達(dá)時(shí)間

15、 需要運(yùn)行時(shí)間 已用CPU時(shí)間 進(jìn)程狀態(tài)");for(i=0;i<n;i+)if(pcbi.status='R')printf("n %s %d %d %d %d %c",pcbi.pname,pcbi.priority,pcbi.reachtime,pcbi.needtime,pcbi.usecputime,pcbi.status);printf("n");void printFpcb(PCB pcb,int n)/輸出已完成的進(jìn)程int i;printf("n進(jìn)程名 優(yōu)先級(jí) 到達(dá)時(shí)間 需要運(yùn)行時(shí)間 已用CPU

16、時(shí)間 進(jìn)程狀態(tài)");for(i=0;i<n;i+)if(pcbi.status='F')printf("n %s %d %d %d %d %c",pcbi.pname,pcbi.priority,pcbi.reachtime,pcbi.needtime,pcbi.usecputime,pcbi.status);printf("n");void staPRI(PCB pcb,int n,int times)/靜態(tài)優(yōu)先級(jí)算法int i=0;printf("n當(dāng)前的系統(tǒng)時(shí)間為:%dn",times);getc

17、h();printf("n按優(yōu)先級(jí)排序，到達(dá)就緒隊(duì)列中的進(jìn)程為：");paixupcb(pcb,n);getch();for(i=0;i<n;i+)while(pcbi.needtime>pcbi.usecputime)pcbi.status='R'printf("n按靜態(tài)優(yōu)先級(jí)對(duì)進(jìn)程調(diào)度，正在運(yùn)行的進(jìn)程為：");pcbi.usecputime+;times+;printRpcb(pcb,n);getch();printf("n當(dāng)前的系統(tǒng)時(shí)間為:%dn",times);getch();pcbi.status

18、='r'paixupcb(pcb,n);if(pcbi.needtime=pcbi.usecputime)pcbi.status='F'printf("n此時(shí)刻，進(jìn)程%s已經(jīng)完成，進(jìn)程%s被撤銷!n",pcbi.pname,pcbi.pname);getch();printf("n按優(yōu)先級(jí)排序，就緒隊(duì)列中的進(jìn)程為：");printpcb(pcb,n);getch();printf("n按優(yōu)先級(jí)隊(duì)列中已經(jīng)沒有進(jìn)程，至此，所有的進(jìn)程已經(jīng)完成!n");getch();printf("n完成信息如下：

19、");printFpcb(pcb,n);getch();printf("nn進(jìn)程調(diào)度完畢!請(qǐng)按任意鍵退出!");/動(dòng)態(tài)優(yōu)先級(jí)算法void dynPRI(PCB pcb,int n,int times) int i=0; char temp10; int min; ;printf("n當(dāng)前的系統(tǒng)時(shí)間為:%dn",times);getch();printf("n按優(yōu)先級(jí)排序，到達(dá)就緒隊(duì)列中的進(jìn)程為：");paixupcb(pcb,n);printpcb(pcb,n);getch(); for(i=0;i<n-1;i+) i

20、f(pcbi.reachtime>pcbi+1.reachtime) min=pcbi.reachtime; pcbi.reachtime=pcbi+1.reachtime; pcbi+1.reachtime=min; min=pcbi.needtime; pcbi.needtime=pcbi+1.needtime; pcbi+1.needtime=min; min=pcbi.priority; pcbi.priority=pcbi+1.priority; pcbi+1.priority=min; strcpy(temp,pcbi.pname); strcpy(pcbi.pname,pc

21、bi+1.pname); strcpy(pcbi+1.pname,temp); for(i=0;i<n;i+) if(pcbi.priority<pcbi+1.priority) min=pcbi.priority; pcbi.priority=pcbi+1.priority; pcbi+1.priority=min; min=pcbi.reachtime; pcbi.reachtime=pcbi+1.reachtime; pcbi+1.reachtime=min; min=pcbi.needtime; pcbi.needtime=pcbi+1.needtime; pcbi+1.n

22、eedtime=min; strcpy(temp,pcbi.pname); strcpy(pcbi.pname,pcbi+1.pname); strcpy(pcbi+1.pname,temp); / pcbsi.usetime+; /按進(jìn)程優(yōu)先級(jí)排序，最高的排在最前面 printf("n按優(yōu)先級(jí)隊(duì)列中已經(jīng)沒有進(jìn)程，至此，所有的進(jìn)程已經(jīng)完成!n");getch();printf("n完成信息如下：");printFpcb(pcb,n);getch();printf("nn進(jìn)程調(diào)度完畢!請(qǐng)按任意鍵退出!");void main()PCB

23、pcbrMAX;int pnum=0;int systime=0;printf("tttt進(jìn)程調(diào)度模擬演示程序");inputpcb(pcbr,&pnum);printf("n用戶輸入的進(jìn)程信息為：");printpcb(pcbr,pnum);staPRI(pcbr,pnum,systime);/簡單輪轉(zhuǎn)法調(diào)度算法.c#include <stdio.h>#include <string.h>#include <conio.h>#define MAX 24struct pcb/建立進(jìn)程控制塊char pname1

24、0;int reachtime;int needtime;int usecputime;char status;typedef struct pcb PCB;void inputpcb (PCB pcb,int *n)/用戶輸入進(jìn)程信息int i;int num;printf("n請(qǐng)輸入進(jìn)程個(gè)數(shù)");scanf("%d",&num);for(i=0;i<num;i+)printf("n請(qǐng)輸入第%d個(gè)進(jìn)程的名稱:",i+1);scanf("%s",&pcbi.pname);printf(&quo

25、t;n請(qǐng)輸入第%d個(gè)進(jìn)程的提交時(shí)間:",i+1);scanf("%d",&pcbi.reachtime);printf("n請(qǐng)輸入第%d個(gè)進(jìn)程的運(yùn)行時(shí)間:",i+1);scanf("%d",&pcbi.needtime);pcbi.usecputime=0;pcbi.status='r'*n=num;void fcfspcb(PCB pcb,int n)/對(duì)用戶輸入的進(jìn)程按FCFS排序int i,j;PCB pcbtemp;for(i=0;i<n-1;i+)for(j=i+1;j<

26、n;j+)if(pcbi.reachtime>pcbj.reachtime)pcbtemp=pcbi;pcbi=pcbj;pcbj=pcbtemp;void printpcb(PCB pcb,int n)/輸出用戶輸入的進(jìn)程int i;printf("n進(jìn)程名 到達(dá)時(shí)間 需要運(yùn)行時(shí)間");for(i=0;i<n;i+)printf("n %s %d %d",pcbi.pname,pcbi.reachtime,pcbi.needtime);printf("n");void printrpcb(PCB pcb,int n)/輸

27、出就緒隊(duì)列中的進(jìn)程int i;printf("n進(jìn)程名 到達(dá)時(shí)間 需要運(yùn)行時(shí)間 已用CPU時(shí)間 進(jìn)程狀態(tài)");for(i=0;i<n;i+)if(pcbi.status='r')printf("n %s %d %d %d %c",pcbi.pname,pcbi.reachtime,pcbi.needtime,pcbi.usecputime,pcbi.status);printf("n");void printRpcb(PCB pcb,int n)/輸出正在運(yùn)行的進(jìn)程int i;printf("n進(jìn)程名

28、到達(dá)時(shí)間 需要運(yùn)行時(shí)間 已用CPU時(shí)間 進(jìn)程狀態(tài)");for(i=0;i<n;i+)if(pcbi.status='R')printf("n %s %d %d %d %c",pcbi.pname,pcbi.reachtime,pcbi.needtime,pcbi.usecputime,pcbi.status);printf("n");void printFpcb(PCB pcb,int n)/輸出已完成的進(jìn)程int i;printf("n進(jìn)程名 到達(dá)時(shí)間 需要運(yùn)行時(shí)間 已用CPU時(shí)間 進(jìn)程狀態(tài)");fo

29、r(i=0;i<n;i+)if(pcbi.status='F')printf("n %s %d %d %d %c",pcbi.pname,pcbi.reachtime,pcbi.needtime,pcbi.usecputime,pcbi.status);printf("n");void simTSC(PCB pcb,int n)int i=0;int j;PCB pcbtemp;printf("n按先來先服務(wù)排序，就緒隊(duì)列中的進(jìn)程:");fcfspcb(pcb,n);getch();while(pcbi.need

30、time>pcbi.usecputime&&i<n)pcbi.status='R'printf("n按簡單時(shí)間片輪轉(zhuǎn)發(fā)對(duì)進(jìn)程進(jìn)行調(diào)度，正在運(yùn)行的進(jìn)程為:");pcbi.needtime+;printRpcb(pcb,n);getch();if(pcbi.needtime=pcbi.usecputime)pcbi.status='F'printf("n此時(shí)刻，進(jìn)程%s已經(jīng)完成，進(jìn)程%s被撤銷!n",pcbi.pname,pcbi.pname);getch();i+;elsepcbi.status=

31、'r'pcbtemp=pcbi;for(j=i;j<n-1;j+)pcbj=pcbj+1;pcbj=pcbtemp;printf("n本次調(diào)度完成!準(zhǔn)備進(jìn)行下一次調(diào)度.n");getch();printf("n就緒隊(duì)列中的進(jìn)程為:");printrpcb(pcb,n);getch();printf("n就緒隊(duì)列中已經(jīng)沒有進(jìn)程，致辭，所有的進(jìn)程已經(jīng)完成");getch();printf("n完成信息如下:");printFpcb(pcb,n);getch();printf("nn進(jìn)程調(diào)

32、度完畢!請(qǐng)按任意鍵退出!");void main()PCB pcbrMAX;int pnum=0;printf("tttt進(jìn)程調(diào)度模擬演示程序");inputpcb(pcbr,&pnum);printf("n用戶輸入的原始程序信息為:");printpcb(pcbr,pnum);simTSC(pcbr,pnum);/多級(jí)反饋隊(duì)列調(diào)度算法.c#include <stdio.h>#include <conio.h>#include <string.h>#define MAX 24struct pcb/建立

33、進(jìn)程控制塊char pname10;int priority;int reachtime;int needtime;int usecputime;char status;typedef struct pcb PCB;void inputpcb(PCB pcb,int *n)/用戶輸入進(jìn)程信息int i;int num;printf("n請(qǐng)輸入進(jìn)程個(gè)數(shù)");scanf("%d",&num);for(i=0;i<num;i+)printf("n請(qǐng)輸入第%d個(gè)進(jìn)程的名稱:",i+1);scanf("%s",

34、pcbi.pname);printf("n請(qǐng)輸入第%d個(gè)進(jìn)程的優(yōu)先級(jí):",i+1);scanf("%d",&pcbi.priority);printf("n進(jìn)程的默認(rèn)到達(dá)時(shí)間為O.n");printf("n請(qǐng)輸入第%d個(gè)進(jìn)程的運(yùn)行時(shí)間:",i+1);scanf("%d",&pcbi.needtime);pcbi.reachtime=0;pcbi.usecputime=0;pcbi.status='r'*n=num;void paixupcb(PCB pcb,int

35、 n)/對(duì)用戶輸入的進(jìn)程按優(yōu)先級(jí)排序int i,j;PCB pcbtemp;for(i=0;i<n-1;i+)for(j=i+1;j<n;j+)if(pcbi.priority<pcbj.priority)pcbtemp=pcbi;pcbi=pcbj;pcbj=pcbtemp;void printpcb(PCB pcb,int n)/輸出就緒隊(duì)列中的進(jìn)程int i;printf("n進(jìn)程名 優(yōu)先級(jí) 到達(dá)時(shí)間 需要運(yùn)行時(shí)間 已用CPU時(shí)間 進(jìn)程狀態(tài)");for(i=0;i<n;i+)if(pcbi.status!='F')printf(

36、"n %s %d %d %d %d %c",pcbi.pname,pcbi.priority,pcbi.reachtime,pcbi.needtime,pcbi.usecputime,pcbi.status);printf("n");void printRpcb(PCB pcb,int n)/輸出正在運(yùn)行的進(jìn)程int i;printf("n進(jìn)程名 優(yōu)先級(jí) 到達(dá)時(shí)間 需要運(yùn)行時(shí)間 已用CPU時(shí)間 進(jìn)程狀態(tài)");for(i=0;i<n;i+)if(pcbi.status='R')printf("n %s %

37、d %d %d %d %c",pcbi.pname,pcbi.priority,pcbi.reachtime,pcbi.needtime,pcbi.usecputime,pcbi.status);printf("n");void printFpcb(PCB pcb,int n)/輸出已完成的進(jìn)程int i;printf("n進(jìn)程名 優(yōu)先級(jí) 到達(dá)時(shí)間 需要運(yùn)行時(shí)間 已用CPU時(shí)間 進(jìn)程狀態(tài)");for(i=0;i<n;i+)if(pcbi.status='F')printf("n %s %d %d %d %d %c

38、",pcbi.pname,pcbi.priority,pcbi.reachtime,pcbi.needtime,pcbi.usecputime,pcbi.status);printf("n");void staPRI(PCB pcb,int n,int times)/靜態(tài)優(yōu)先級(jí)算法int i=0;printf("n當(dāng)前的系統(tǒng)時(shí)間為:%dn",times);getch();printf("n按優(yōu)先級(jí)排序，到達(dá)就緒隊(duì)列中的進(jìn)程為：");paixupcb(pcb,n);getch();for(i=0;i<n;i+)while

39、(pcbi.needtime>pcbi.usecputime)pcbi.status='R'printf("n按靜態(tài)優(yōu)先級(jí)對(duì)進(jìn)程調(diào)度，正在運(yùn)行的進(jìn)程為：");pcbi.usecputime+;times+;printRpcb(pcb,n);getch();printf("n當(dāng)前的系統(tǒng)時(shí)間為:%dn",times);getch();pcbi.status='r'paixupcb(pcb,n);if(pcbi.needtime=pcbi.usecputime)pcbi.status='F'printf(&

40、quot;n此時(shí)刻，進(jìn)程%s已經(jīng)完成，進(jìn)程%s被撤銷!n",pcbi.pname,pcbi.pname);getch();printf("n按優(yōu)先級(jí)排序，就緒隊(duì)列中的進(jìn)程為：");printpcb(pcb,n);getch();printf("n就緒隊(duì)列中已經(jīng)沒有進(jìn)程，至此，所有的進(jìn)程已經(jīng)完成!n");getch();printf("n完成信息如下：");printFpcb(pcb,n);getch();printf("nn進(jìn)程調(diào)度完畢!請(qǐng)按任意鍵退出!");void main()PCB pcbrMAX;

41、int pnum=0;int systime=0;printf("tttt進(jìn)程調(diào)度模擬演示程序");inputpcb(pcbr,&pnum);printf("n用戶輸入的進(jìn)程信息為：");printpcb(pcbr,pnum);staPRI(pcbr,pnum,systime);操作系統(tǒng)算法設(shè)計(jì)-主存分配回收摘 要在內(nèi)存初始化完成以后，內(nèi)存中就常駐有內(nèi)核映像（內(nèi)核代碼和數(shù)據(jù)）。以后，隨著用戶程序的執(zhí)行和結(jié)束，就需要不斷地分配和釋放物理頁面，內(nèi)核應(yīng)該為分配一組連續(xù)的頁面而建立一種穩(wěn)定、高效的分配策略。為此，必須解決一個(gè)比較重要的內(nèi)存管理問題，即外碎

42、片問題。頻繁地請(qǐng)求和釋放不同大小的一組連續(xù)頁面，必然導(dǎo)致在已分配的內(nèi)存塊中分散許多小塊的空閑頁面。由此帶來的問題是，即使這些小塊的空閑頁面加起來足以滿足所請(qǐng)求的頁面，但是要分配一個(gè)大塊的連續(xù)頁面可能就根本無法滿足，Linux采用注明的伙伴（Buddy）系統(tǒng)算法來解決外碎片問題。但是請(qǐng)注意，在Linux中，CPU不能按物理地址來訪問存儲(chǔ)空間，而必須使用虛擬地址；因此，對(duì)于內(nèi)存頁面的管理，通常是在虛存空間中分配一個(gè)虛存區(qū)間，然后才根據(jù)需要為此區(qū)間分配相應(yīng)的物理頁面并建立起映射，也就是說，虛存區(qū)間的分配在前，而物理頁面的分配在后，但是為了承接上一節(jié)的內(nèi)容，我們先介紹內(nèi)存的分配和回收，然后在介紹用戶進(jìn)

43、程虛存區(qū)間的建立。分配效率、碎片問題是操作系統(tǒng)中內(nèi)存分配的兩大問題。一個(gè)好的分配器應(yīng)該能夠快速地滿足各種大小的分配要求，同時(shí)不能產(chǎn)生大量的碎片浪費(fèi)空間?；跀?shù)據(jù)結(jié)構(gòu)的伙伴系統(tǒng)的分配與回收思想給出了一個(gè)有效的算法。關(guān)鍵詞：操作系統(tǒng) 內(nèi)存分配 首次適應(yīng)算法 循環(huán)首次適應(yīng)算法 最佳適應(yīng)算法最壞適應(yīng)算法一、 課程設(shè)計(jì)的目的和要求操作系統(tǒng)的課程設(shè)計(jì)非常有必要，可以是學(xué)生通過編程實(shí)驗(yàn)，更加深入得理解和掌握了操作系統(tǒng)的基本理論和功能技術(shù)。示例如下：1.掌握進(jìn)程的概念、加深對(duì)進(jìn)程調(diào)度算法的理解、掌握C語言的編程初步；2.寫出主存空間的分配和回收程序的設(shè)計(jì)方案，包括方案描述及流程圖；3.用高級(jí)語言完成一個(gè)主存空

44、間的分配和回收程序，以加深對(duì)動(dòng)態(tài)分區(qū)分配方式及其算法的理解。二、系統(tǒng)需求分析主存分配與回收采用連續(xù)分配方式之動(dòng)態(tài)分區(qū)分配存儲(chǔ)管理，使用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最佳適應(yīng)算法和最壞適應(yīng)算法4種算法設(shè)計(jì)。設(shè)計(jì)一個(gè)作業(yè)申請(qǐng)隊(duì)列以及作業(yè)完成后的釋放順序，實(shí)現(xiàn)主存的分配和回收。采用分區(qū)說明表進(jìn)行，或在程序運(yùn)行過程，由用戶指定申請(qǐng)與釋放。設(shè)計(jì)一個(gè)空閑區(qū)說明表，以保存某時(shí)刻主存空間占用情況。把空閑區(qū)說明表的變化情況以及各作業(yè)的申請(qǐng)、釋放情況顯示。三、總體設(shè)計(jì)編程序?qū)崿F(xiàn)下述在不同的存儲(chǔ)管理方式下的主存空間的分配與回收，其中原始數(shù)據(jù)設(shè)為空閑區(qū)說明表結(jié)構(gòu)體(1).設(shè)計(jì)基于空閑區(qū)說明表的可變分區(qū)分配與回收算法

45、；(2).或設(shè)計(jì)基于空閑區(qū)鏈表的可變分區(qū)的分配與回收；四、詳細(xì)設(shè)計(jì)主存分配回收程序中，采用連續(xù)分配方式之動(dòng)態(tài)分區(qū)分配存儲(chǔ)管理，使用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最佳適應(yīng)算法和最壞適應(yīng)算法4種算法完成設(shè)計(jì)。主存分配回收中，我采用的是讓應(yīng)用人員自己選擇運(yùn)用的采用什么算法，首次適應(yīng)算法、最佳適應(yīng)算法，任務(wù)書上是有四種算法的，我選擇了這兩種。當(dāng)然程序中需要初始化函數(shù)、輸出列表函數(shù)、首次適應(yīng)載入進(jìn)程函數(shù)：讓你嘗試一把自己把需要的數(shù)據(jù)插入進(jìn)去、最佳算法載入進(jìn)程函數(shù)：和首次適應(yīng)載入進(jìn)程函數(shù)差不多，但是看你選擇的過程中親自體驗(yàn)?zāi)膫€(gè)算法比較好、釋放進(jìn)程的子函數(shù)：程序運(yùn)行結(jié)束需要結(jié)束進(jìn)程。下面是各個(gè)算法的程序流

46、程圖：NNNNYYY開始按enter進(jìn)入程序1？Y輸入字符ss=a?s=r?s=d?返回1執(zhí)行a(),shu()輸出4個(gè)選項(xiàng)執(zhí)行r(),shu()輸出4個(gè)選項(xiàng)執(zhí)行d(),shu()輸出4個(gè)選項(xiàng)返回0結(jié)束圖1.4 主存分配回收流程圖五、測試、調(diào)試過程（1）程序運(yùn)行沒有按預(yù)期完成任務(wù)，解決方法是每次對(duì)內(nèi)存分配和回收之前和之后都要對(duì)空閑區(qū)按地址進(jìn)行排序（2）程序不能顯示作業(yè)狀況，解決辦法是為作業(yè)作一個(gè)已分配表用來存儲(chǔ)作業(yè)記錄下面是各個(gè)程序的運(yùn)行結(jié)果：主存分配回收：六、結(jié)論與體會(huì)在這次設(shè)計(jì)中遇到了很多實(shí)際性的問題，在實(shí)際設(shè)計(jì)中才發(fā)現(xiàn)，書本上理論性的東西在實(shí)際運(yùn)用中的還是有一定距離的。一切問題必須要靠自

47、己一點(diǎn)一滴的解決，而在解決的過程當(dāng)中你會(huì)發(fā)現(xiàn)自己在飛速的提升。程序設(shè)計(jì)是一個(gè)很靈活的東西，它反映了你解決問題的邏輯思維和創(chuàng)新能力，是一個(gè)設(shè)計(jì)的靈魂所在，通過這次課程設(shè)計(jì)我也發(fā)現(xiàn)了自己存在的不足之處，雖然感覺理論上已經(jīng)掌握，但在運(yùn)動(dòng)到實(shí)踐過程中仍有意想不到的困惑，經(jīng)過一番努力才得以解決。總之，通過這次課程設(shè)計(jì)的細(xì)節(jié)問題，而這些問題是我在從低級(jí)的程序員向高級(jí)程序設(shè)計(jì)師過度的過程必須要解決的。而我個(gè)人認(rèn)為，我越早接觸，越多接觸，越快解決對(duì)我本人所斷過程有重要的意義。附錄：源程序#include <stdio.h>#include <stdlib.h>#include <

48、string.h>struct pcbchar name10;int size;int begin;char status;int end;PCB20;int n=1;int size=1024;void c()/初始化函數(shù)printf("n初始化，設(shè)內(nèi)存總存量為1Mn");printf("n系統(tǒng)從低地址部分開始使用，占用100K;n");strcpy(PCB0.name,"SYSNAME");PCB0.begin=0;/開始地址為0PCB0.status='u'/狀態(tài)忙碌PCB0.size=100;/占用內(nèi)存大

49、小100KPCB0.end=100;/結(jié)束地址為100strcpy(PCB1.name,"-");PCB1.begin=PCB0.end;PCB1.size=size-PCB0.size;/剩下空閑的內(nèi)存大小PCB1.status='f'PCB1.end=1024;size=size-100;shu()/輸出列表函數(shù)int i;int a=1;while(n=0)printf("隊(duì)列為空n");return 1;printf("空閑列表區(qū)Free:nn");printf(" NO proname begin size statusn");for(i=0;i<n+1;i+)/空閑列表輸出if(PCBi.status='f')printf(" NO.%d%8s%7d%7d%6cn",a,PCB,PCBi.begin,PCBi.size,PCBi.status);a=a+1;printf("n=n");a=1;printf("已分配列表區(qū)Userd：nn");printf(" NO proname begin size statusn");for(i=0;i<n+1;i+)