1、南通大學(xué)計算機科學(xué)與技術(shù)學(xué)院操作系統(tǒng)課程設(shè)計報 告 書課 題 名 操作系統(tǒng)課程設(shè)計 班 級 姓 名 指導(dǎo)教師 時 間 1、 設(shè)計目的1、 模擬實現(xiàn)計算機的處理機調(diào)度。幫助學(xué)生理解計算機的處理機調(diào)度的工作原理和實現(xiàn)過程。2、 模擬實現(xiàn)計算機的主存儲器空間的分配與回收。幫助學(xué)生理解計算機主存儲器空間的分配與回收的工作原理和實現(xiàn)過程2、 設(shè)計內(nèi)容1、 設(shè)計一個按優(yōu)先數(shù)調(diào)度算法實現(xiàn)處理機調(diào)度的程序。2、設(shè)計一個在可變分區(qū)管理方式下采用最先適應(yīng)算法實現(xiàn)主存的分配與回收的程序。3、 設(shè)計要求1、 完成課程調(diào)試和運行。2、 完成課程設(shè)計報告書。3、課程設(shè)計報告書含數(shù)據(jù)結(jié)構(gòu)、符號說明、流程圖、源程序并附注解。

2、四、設(shè)計思路（1） 按優(yōu)先數(shù)調(diào)度算法實現(xiàn)處理機調(diào)度系統(tǒng)假設(shè)5個進(jìn)程，進(jìn)程控制塊PCB的格式為： 進(jìn)程名 指針 要求運行時間 優(yōu)先數(shù) 狀態(tài)進(jìn)程名作為進(jìn)程的標(biāo)識，5個進(jìn)程的進(jìn)程名分別為p1,p2,p3,p4,p5。指針按優(yōu)先數(shù)大小把5個進(jìn)程連成隊列，用指針指出下一個進(jìn)程的進(jìn)程控制塊PCB的首地址，最后一個進(jìn)程的指針為“0”。要求運行時間進(jìn)程需要運行的單位時間數(shù)。優(yōu)先數(shù)進(jìn)程的優(yōu)先數(shù)，調(diào)度時按優(yōu)先數(shù)大的進(jìn)程先執(zhí)行。狀態(tài)假設(shè)有兩種狀態(tài)，“就緒”狀態(tài)和“結(jié)束”狀態(tài)。5個進(jìn)程的初始狀態(tài)為“就緒”狀態(tài)，用“R”表示，“結(jié)束”狀態(tài)用“E”表示。（1） 在運行優(yōu)先數(shù)調(diào)度算法處理機調(diào)度程序時，輸入每個進(jìn)程的“要求運

3、行時間”和“優(yōu)先數(shù)”（2） 為方便調(diào)度，5個進(jìn)程按優(yōu)先數(shù)由大到小連成隊列，用一單元指出隊首進(jìn)程，用指針指出隊首進(jìn)程，用指針指出隊列連接情況：PCB1PCB2PCB3PCB4PCB5進(jìn)程K1K2K3K4K5進(jìn)程名P1P2P3P4P5優(yōu)先數(shù)15342需要運行時間23124優(yōu)先數(shù)15342狀態(tài)RRRRR（3）處理機調(diào)度采用動態(tài)改變優(yōu)先數(shù)的辦法，進(jìn)程每執(zhí)行一次優(yōu)先數(shù)加“1”，模擬調(diào)度不對進(jìn)程進(jìn)行實際的啟動運行，而執(zhí)行：優(yōu)先數(shù)=優(yōu)先數(shù)+1；需要運行時間=需要運行時間-1；來模擬調(diào)度的一次執(zhí)行。（4）進(jìn)程運行一次后，如要求運行時間0，則將其再加入隊列（按優(yōu)先數(shù)大小插入，并置隊首標(biāo)志），如要求運行時間=0，

4、則將其狀態(tài)改成“結(jié)束”狀態(tài)E，并退出隊列。（5）如“就緒”狀態(tài)的進(jìn)程隊列不為空，則重復(fù)上面的（3）和（4）的步驟，直到所有的進(jìn)程都為“結(jié)束”狀態(tài)E。（6）在設(shè)計的過程中應(yīng)有輸出語句，顯示每次被選中的進(jìn)程的進(jìn)程名和運行一次后進(jìn)程隊列的變化。（二）可變分區(qū)管理方式下采用最先適應(yīng)算法實現(xiàn)主存的分配與回收<1>可變分區(qū)管理方式是按作業(yè)需要的主存空間大小來分割分區(qū)的。當(dāng)要裝入一個作業(yè)時，根據(jù)作業(yè)需要的主存量查看是否有足夠的空閑空間，若有，則按需要量分割一個分區(qū)分配給該作業(yè)；若無，則該作業(yè)不能裝入。隨著作業(yè)的裝入，撤離，主存空間被分成許多個分區(qū)，有的分區(qū)被作業(yè)占用，而有的分區(qū)是空閑的。如圖A所

5、示：為了說明哪些區(qū)是空閑的，可以用來裝入新作業(yè)，必須有一張空閑區(qū)說明表，格式如圖B所示：操作系統(tǒng)作業(yè)1作業(yè)1空閑區(qū)作業(yè)1空閑區(qū)起址長度狀態(tài)14K12K未分配32K96K未分配空表目空表目空表目5K10K14K26K32K128K其中，起址：指出一個空閑區(qū)的主存起始地址。 長度：指出從起始地址開始的一個連續(xù)空閑區(qū)的長度。 狀態(tài)：有兩種狀態(tài)。一種是“未分配”狀態(tài)，指出對應(yīng)的由起始地址接線出的某個長度的區(qū)域是空閑區(qū)；另一種是“空表目”狀態(tài)，表示對應(yīng)的登記項目是空白，可用來登記新的空閑區(qū)（例如，作業(yè)撤消后，它所占用的區(qū)域就成了空閑區(qū)為。應(yīng)找一個“空表目”欄登記歸還區(qū)的起址和長度修改狀態(tài)）。由于分區(qū)的個

6、數(shù)不定，所以空閑區(qū)說明表中應(yīng)有適量的狀態(tài)為“空表目”的登記欄目，否則造成表格溢出無法登記。圖（B）說明表的內(nèi)容是按圖（A）主存使用情況登記的。<2>當(dāng)有一個新作業(yè)裝入主存時，必須查找空閑區(qū)說明表，從中找出一個足夠大的空閑區(qū)。有時找到的空閑區(qū)可能大于作業(yè)需要量。這時應(yīng)把原來的空閑區(qū)分成兩個部分：一部分分配給作業(yè)占用，另一部分又成為一個較小的空閑區(qū)。為了盡量減少由于分割造成的“碎片”，采用二個措施：一是在作業(yè)裝入時盡可能的利用主存的低地址部分的空閑區(qū)，而盡量保存高地址部分有較大的連續(xù)空間區(qū)域，以有利于大型作業(yè)的裝入。為此，在空閑區(qū)說明表中，把每個空閑區(qū)域按其地址順序登記，即每個后續(xù)的空

7、閑區(qū)其始地址總是比前者大。為了查找方便，還可使表格“緊縮”，總是讓“空表目”欄集中在表格的后部。二是當(dāng)“碎片”小于某一選定值時，空閑區(qū)不再分割，全部分配給作業(yè)。<3>采用最先適應(yīng)法分配主存空間按照作業(yè)的需要量，查找空閑區(qū)說明表，找到第一個滿足要求的空閑區(qū)。當(dāng)空閑區(qū)大于作業(yè)量與選定常量之和時，一部分用來裝入作業(yè)，另一部分仍為空閑區(qū)登記在空閑區(qū)說明表中。<4>當(dāng)一個作業(yè)執(zhí)行結(jié)束撤離時，作業(yè)所占的區(qū)域應(yīng)該歸還，歸還的區(qū)域與其它空閑區(qū)相鄰，則應(yīng)合成一個較大的空閑登記區(qū)在空閑區(qū)說明表中。例在圖A的情況下，如果作業(yè)2撤離，歸還所占主存區(qū)域時，應(yīng)與上，下相鄰的空閑區(qū)一起合并成一個大的

8、空閑區(qū)后登記在空閑區(qū)說明表中。五、數(shù)據(jù)結(jié)構(gòu)1、進(jìn)程定義用了結(jié)構(gòu)體，結(jié)構(gòu)體包含了進(jìn)程的名稱、進(jìn)程的運行時間、進(jìn)程的優(yōu)先級以及進(jìn)程的指針。代碼如下：struct Nodestring name;int need_time;int privilege;char state;Node *next;2、 在可變分區(qū)管理中，也用結(jié)構(gòu)體分別表示了作業(yè)信息（作業(yè)號、作業(yè)起址、作業(yè)長度、指針）和空閑區(qū)的信息（起址、長度、狀態(tài)、指針）。代碼如下：作業(yè) 空閑區(qū)struct Jobstruct Fspaceint jno; int fstart;int jstart; int flen;int jlen; char

9、fstatus;Job *next; Fspace *next;3、在優(yōu)先數(shù)調(diào)度算法和可變分區(qū)管理中都運用了單向鏈表。優(yōu)先數(shù)調(diào)度算法通過鏈表將進(jìn)程連接起來，并按照優(yōu)先數(shù)進(jìn)行排序（選擇排序）；可變分區(qū)管理分配內(nèi)存時，從鏈?zhǔn)组_始順序查找，直到找到第一個滿足要求的空間并分配給進(jìn)程，把分配后余下的空間仍然留在鏈表中。若從鏈?zhǔn)字伶溛捕疾粷M足要求，則分配失敗。該算法傾向于優(yōu)先使用低地址的空間。六、流程圖1、優(yōu)先數(shù)調(diào)度算法2、首次適應(yīng)法 (1) 分配流程圖(2) 回收流程圖七、測試報告數(shù)據(jù)主界面設(shè)計一個框架分別去鏈接處理機管理和存儲器管理相關(guān)的程序。1、處理器管理（優(yōu)先級調(diào)度算法）運行界面（1） 初始化：通

10、過void Initialize(Node *head)對鏈表進(jìn)行初始化，然后直接輸出鏈表上的數(shù)據(jù)，之后通過Sort(Node *head)函數(shù)對單向鏈表進(jìn)行排序，并不輸出。（2） 1-2次運行結(jié)果：遞歸函數(shù)Run( Node *head)執(zhí)行，每執(zhí)行一次優(yōu)先數(shù)減一，運行時間減一，再次排序（優(yōu)先數(shù)遞減），遞歸執(zhí)行Run( Node *head)函數(shù)。（3） 3-4次運行結(jié)果：當(dāng)運行時間為0時，將該進(jìn)程狀態(tài)改為E，并將其從此鏈表中移動到心鏈表End中（如4次），反復(fù)執(zhí)行Run( Node *head)。（4） 5-6次運行結(jié)果（5） 7-8次運行結(jié)果（6） 9-10次運行結(jié)果（7） 11-12次

11、運行結(jié)果：直到原鏈表中無數(shù)據(jù)時，運行結(jié)束（如12次）。2、可變分區(qū)管理（最先適應(yīng)算法）(1) 初始化作業(yè)表和空閑區(qū)表；通過void Init(Job *j, Fspace *f)函數(shù)兩個鏈表進(jìn)行初始化（當(dāng)輸入全為0時退出），并且通過void ShowJob(Job *J)和void ShowSpace(Fspace *F)分別輸出兩個鏈表的數(shù)據(jù)。(2) 作業(yè)申請通過FirstAllocate(Job *J,Fspace *F)函數(shù)進(jìn)行最先適應(yīng)算法進(jìn)行分配，通過比較申請空間長度和空閑區(qū)表中的長度，等于則進(jìn)行裝入，修改該空閑區(qū)狀態(tài)位，通過bool ImproveFspace(Fspace *F)函

12、數(shù)來優(yōu)化空閑區(qū)表（通過標(biāo)志位判斷空閑區(qū)是否空閑狀態(tài)，void DeleteJob(Job *J,Job *j)刪除非空閑狀態(tài)標(biāo)志位，遍歷空閑區(qū)表查找并合并連續(xù)的空閑區(qū)），比其大則進(jìn)行裝入，若并且重新劃分空閑區(qū)；并用void InsertJob(Job *J,Job *j)函數(shù)在作業(yè)表中插入新的紀(jì)錄，最后進(jìn)行兩個鏈表的輸出。a) 申請作業(yè)3申請作業(yè)號3，需求量2，則將起址為14的空閑區(qū)進(jìn)行劃分，并且作業(yè)增加一條記錄，而空閑區(qū)表的一條記錄起址從14變?yōu)?6。b) 申請作業(yè)4申請作業(yè)號3，需求量14，空閑區(qū)第一條記錄不滿足，就選擇第二個滿足條件的空閑區(qū)進(jìn)行裝入。c) 申請作業(yè) 5d) 申請作業(yè) 6e

13、) 申請作業(yè) 7f) 申請作業(yè) 8當(dāng)沒有符合的空閑區(qū)時，則不進(jìn)行插入。如下圖：(3)作業(yè)撤銷通過void BackJob(Job *J,Fspace *F,int jno)進(jìn)行作業(yè)的撤銷，并且刪除作業(yè)表中的作業(yè)記錄和更改并優(yōu)化（bool ImproveFspace(Fspace *F)函數(shù)）空閑區(qū)表。a) 撤銷作業(yè)6查找作業(yè)表中作業(yè)號為6的并將其刪除，并向空閑區(qū)表中增加一條記錄，然后通過bool ImproveFspace(Fspace *F)優(yōu)化空閑區(qū)表，合并連續(xù)空閑區(qū)。如下圖，合并后空閑區(qū)輸出。b) 撤銷作業(yè)3空閑區(qū)不連續(xù)，則不合并如下圖c) 撤銷作業(yè)5d) 撤銷作業(yè)2e) 撤銷作業(yè)7f)

14、 全部撤銷當(dāng)作業(yè)表中作業(yè)全部撤銷時，如下圖：八、心得體會通過這次操作系統(tǒng)的課程設(shè)計，我對進(jìn)程的調(diào)度算法及可變分區(qū)管理這兩部分內(nèi)容有了更深的了解。通過參考老師給的代碼，自己進(jìn)行了修改，全部用單向鏈表來進(jìn)行表示表。這次實驗讓我對單向鏈表有了深入的理解和認(rèn)識，并且基本掌握了單向鏈表的插入刪除，排序等等。但是，實際編程時還是會出現(xiàn)各種各樣的意想不到的錯誤，比如鏈表的結(jié)尾不為空等等。通過這次實驗讓我對c+有了深刻的理解，并且為了完善主界面，參考了網(wǎng)上各種主界面的設(shè)計，讓我對遞歸函數(shù)和while()循環(huán)的用法有了深刻的體會。總的來說，處理器管理中的動態(tài)優(yōu)先數(shù)調(diào)度算法和可變分區(qū)中最先適應(yīng)算法有了深刻的掌握，

15、不僅僅是理論上的，已經(jīng)能夠模擬實現(xiàn)這兩個算法，這次實驗讓我收獲良多。附件一（源代碼）#include<iostream>#include<string>using namespace std;#define Memory 128#define NUM 5static int Count = 0;void start();/主界面void Fpf();/優(yōu)先數(shù)調(diào)度算法void Cunchu();/存儲管理/-struct Nodestring name;int need_time;int privilege;char state;Node *next;void Switc

16、h(Node *max, Node *p)string name = max->name;int need_time = max->need_time;int privilege = max->privilege;char state = max->state;max->name = p->name;max->need_time = p->need_time;max->privilege = p->privilege;max->state = p->state;p->name = name;p->need_ti

17、me = need_time;p->privilege = privilege;p->state = state;void Initialize(Node *head)/初始化進(jìn)程Node *K, *g;for (int i = 0; i < NUM; i+)g = new Node;g->name = 'A' + char(i);cout << "tt請輸入" << g->name << "進(jìn)程的運行時間 優(yōu)先數(shù)："cin >> g->need_time

18、 >> g->privilege;g->state = 'R'if (!g->need_time)g = NULL;break;elsefor (K = head; K->next; K = K->next);g->next = K->next;K->next = g;g = NULL;void Sort(Node *head)/進(jìn)程按優(yōu)先數(shù)排序Node *p, *q, *max;p = head->next;while (p)max = p;q = p->next;while (q)if (max->

19、;privilege < q->privilege)max = q;q = q->next;if (max != p)Switch(max, p);p = p->next;return;void Show(Node *head)/輸出進(jìn)程Node *h;if (!head->next)cout << "ttt此隊列中無進(jìn)程！" << endl;elsecout << "ttt進(jìn)程名t"for (h = head; h->next; h = h->next)cout <&l

20、t; h->next->name << 't'cout << endl;cout << "ttt時間t"for (h = head; h->next; h = h->next)cout << h->next->need_time << 't'cout << endl;cout << "ttt優(yōu)先數(shù)t"for (h = head; h->next; h = h->next)cout <&l

21、t; h->next->privilege << 't'cout << endl;cout << "ttt狀態(tài)t"for (h = head; h->next; h = h->next)cout << h->next->state << 't'cout << endl;void Run(Node *Ready, Node *End)/優(yōu)先數(shù)調(diào)度運行進(jìn)程Node *p, *q = End;if (Ready->next = NULL

22、)return;elseCount+;Sort(Ready);-(Ready->next->privilege);-(Ready->next->need_time);if (Ready->next->need_time = 0)Ready->next->state = 'E'p = Ready->next;Ready->next = p->next;p->next = NULL;while (q->next)q = q->next;q->next = p;cout << &qu

23、ot;tt第" << Count << "次運行結(jié)果" << endl;cout << "ttReady隊列" << endl;Show(Ready);cout << "ttEnd隊列" << endl;Show(End);cout << endl;Run(Ready, End);/-struct Jobint jno;int jstart;int jlen;Job *next;struct Fspaceint fstart;in

24、t flen;char fstatus;Fspace *next;int SumJobMem(Job *job)/已占總空間大小Job *j = job->next;int sum = 0;while (j)sum += j->jlen;j = j->next;return sum;int SumMem(Fspace *F)/已知空閑區(qū)總空間int sum = 0;Fspace *f = F;while (f->next)sum += f->flen;f = f->next;return sum;void Init(Job *j, Fspace *f)/初始

25、化作業(yè)表、空閑區(qū)表Job *p = new Job,*s;Fspace *q = new Fspace,*r;cout << "ttt請輸入已分配內(nèi)存的作業(yè)的作業(yè)號、起址、長度："cin >> p->jno >> p->jstart >> p->jlen;while (p->jlen != 0)p->next = NULL;if (SumJobMem(j) + p->jlen > Memory)cout << "ttt內(nèi)存空間不足！"break;else

26、 for (s = j; s->next; s = s->next);s->next = p;p = new Job;cout << "ttt請輸入已分配內(nèi)存的作業(yè)的作業(yè)號、起址、長度："cin >> p->jno >> p->jstart >> p->jlen;cout << "ttt請輸入空閑區(qū)表的起址、長度、狀態(tài)："cin >> q->fstart >> q->flen >> q->fstatus;w

27、hile (q->flen != 0)q->next = NULL;if (SumMem(f) + q->flen > Memory)cout << "ttt內(nèi)存空間不足！"break;elsefor (r = f; r->next; r = r->next);r->next = q;q = new Fspace;cout << "ttt請輸入空閑區(qū)表的起址、長度、狀態(tài)："cin >> q->fstart >> q->flen >> q-&g

28、t;fstatus;void ShowJob(Job *J)/輸出作業(yè)表cout << endl;cout << "tttt作業(yè)表n"if (!J->next)cout <<"ttt作業(yè)表中無作業(yè)！" << endl;elseJob *j;cout << "ttt作業(yè)號t起址t長度n"for (j = J->next; j; j = j->next)cout << "ttt" << j->jno <&l

29、t; 't' << j->jstart << 't' << j->jlen << endl;void ShowSpace(Fspace *F)/輸出空閑區(qū)表cout <<"tttt空閑區(qū)表" << endl;if (!F->next)cout << "ttt無空閑區(qū)！" << endl;elsecout << "ttt起址t長度t狀態(tài)n"Fspace *f;for (f = F-

30、>next; f; f = f->next)cout << "ttt" << f->fstart << 't' << f->flen << 't' << f->fstatus << endl;cout << endl;void InsertJob(Job *J,Job *j)/作業(yè)插入作業(yè)表Job *job = J;while (job->next)job = job->next;j->next =

31、job->next;job->next = j;void InsertSpace(Fspace *F, Fspace *f)/空閑區(qū)插入空閑區(qū)表bool flag = true;Fspace *fs = F;Fspace *p;while (fs->next)p = fs->next;if (f->fstart < p->fstart)fs->next = f;f->next = p;flag = false;break;else fs = fs->next;if (flag)f->next = fs->next;fs-&

32、gt;next = f;void DeleteSpace(Fspace *F, Fspace *f)/刪除空閑區(qū)Fspace *p = F, *q;while(p->next)q = p->next;if (f->fstart = q->fstart)p->next = q->next;q = NULL;break;else p = q;void DeleteJob(Job *J,Job *j)/刪除作業(yè)Job *p = J, *q;while (p->next)q = p->next;if (j->jno = q->jno)p-&g

33、t;next = q->next;q = NULL;break;else p = q;bool ImproveFspace(Fspace *F)/優(yōu)化空閑區(qū)表/SortFspace(F);Fspace *f = F->next;Fspace *p;for (; f; f = f->next)if (f->fstatus != 'F')DeleteSpace(F, f);for (f = F->next; f->next; f = p)p = f->next;if (f->fstart + f->flen = p->fs

34、tart)p->fstart = f->fstart;p->flen += f->flen;DeleteSpace(F,f);else if (f->fstart + f->flen > p->fstart)cout << "空閑表異常！"break;else continue;return true;void FirstAllocate(Job *J,Fspace *F)/最先適應(yīng)算法分配空閑區(qū)int jno, jlen;Fspace *f;Job *j;cout << "tt請輸入申請的作

35、業(yè)信息作業(yè)號、需要量:"cin >> jno >> jlen;while (jlen != 0)for (f = F->next; f; f = f->next)if (f->flen >= jlen && f->fstatus = 'F')j = new Job;j->jno = jno;j->jlen = jlen;j->jstart = f->fstart;InsertJob(J,j);if (f->flen - jlen < 0.25)f->fsta

36、tus = 'N'elsef->fstart = f->fstart + jlen;f->flen = f->flen - jlen;break;if (!f)cout << "ttt無合適的空閑區(qū)！n"elseImproveFspace(F);ShowJob(J);ShowSpace(F);cout << "tt請輸入申請的作業(yè)信息作業(yè)號、需要量:"cin >> jno >> jlen;void BackJob(Job *J,Fspace *F,int jno)/回

37、收作業(yè)Job *j,*p;Fspace *f = new Fspace;for (j = J->next; j; j = p)p = j->next;if (jno = j->jno)f->fstart = j->jstart;f->flen = j->jlen;f->fstatus = 'F'InsertSpace(F,f);DeleteJob(J,j);break;if (!j)cout << "ttt輸入有誤！"ShowJob(J);ImproveFspace(F);ShowSpace(F);/-void Fpf()int n;cout << " ttt-處理機管理-" << endl;cout << "tttt1.優(yōu)先數(shù)調(diào)度算法t 2.返回開始菜單" << endl;cout << "ttt請輸入選擇的操作："cin >> n;Node *Ready = new Node;Node *End = new Node;switch (n)case 1: cout << endl;Rea