1、實驗二 單處理器系統(tǒng)的進程調(diào)度1實驗?zāi)康募由顚M程概念的理解，明確進程和程序的區(qū)別；深入了解系統(tǒng)如何組織進程、創(chuàng)建進程；進一步認識如何實現(xiàn)處理器調(diào)度。2實驗預(yù)備知識進程的概念；進程的組織方式；進程的創(chuàng)建；進程的調(diào)度。3實驗內(nèi)容編寫程序完成單處理機系統(tǒng)中的進程調(diào)度，要求采用時間片輪轉(zhuǎn)調(diào)度算法。實驗具體包括：首先確定進程控制塊的內(nèi)容，進程控制塊的組成方式；然后完成進程創(chuàng)建原語和進程調(diào)度原語；最后編寫主函數(shù)對所作工作進程測試。4提示與講解這個實驗主要要考慮三個問題：如何組織進程、如何創(chuàng)建進程和如何實現(xiàn)處理器調(diào)度。考慮如何組織進程，首先就要設(shè)定進程控制塊的內(nèi)容。進程控制塊PCB記錄各個進程執(zhí)行時的情況

2、。不同的操作系統(tǒng)，進程控制塊記錄的信息內(nèi)容不一樣。操作系統(tǒng)功能越強，軟件也越龐大，進程控制塊記錄的內(nèi)容也就越多。這里的實驗只使用了必不可少的信息。一般操作系統(tǒng)中，無論進程控制塊中信息量多少，信息都可以大致分為以下四類： 標識信息每個進程都要有一個惟一的標識符，用來標識進程的存在和區(qū)別于其他進程。這個標識符是必不可少的，可以用符號或編號實現(xiàn)，它必須是操作系統(tǒng)分配的。在后面給出的參考程序中，采用編號方式，也就是為每個進程依次分配一個不相同的正整數(shù)。 說明信息用于記錄進程的基本情況，例如進程的狀態(tài)、等待原因、進程程序存放位置、進程數(shù)據(jù)存放位置等等。實驗中，因為進程沒有數(shù)據(jù)和程序，僅使用進程控制塊模擬

3、進程，所以這部分內(nèi)容僅包括進程狀態(tài)。 現(xiàn)場信息現(xiàn)場信息記錄各個寄存器的內(nèi)容。當進程由于某種原因讓出處理器時，需要將現(xiàn)場信息記錄在進程控制塊中，當進行進程調(diào)度時，從選中進程的進程控制塊中讀取現(xiàn)場信息進行現(xiàn)場恢復(fù)?，F(xiàn)場信息就是處理器的相關(guān)寄存器內(nèi)容，包括通用寄存器、程序計數(shù)器和程序狀態(tài)字寄存器等。在實驗中，可選取幾個寄存器作為代表。用大寫的全局變量AX、BX、CX、DX模擬通用寄存器、大寫的全局變量PC模擬程序計數(shù)器、大寫的全局變量PSW模擬程序狀態(tài)字寄存器。 管理信息管理信息記錄進程管理和調(diào)度的信息。例如進程優(yōu)先數(shù)、進程隊列指針等。實驗中，僅包括隊列指針。因此可將進程控制塊結(jié)構(gòu)定義如下：stru

4、ct pcbint name; /進程標識符 int status; /進程狀態(tài) int ax, bx, cx,dx; /進程現(xiàn)場信息，通用寄存器內(nèi)容 int pc; /進程現(xiàn)場信息，程序計數(shù)器內(nèi)容 int psw; /進程現(xiàn)場信息，程序狀態(tài)字寄存器內(nèi)容 int next; /下一個進程控制塊的位置確定進程控制塊內(nèi)容后，要考慮的就是如何將進程控制塊組織在一起。多道程序設(shè)計系統(tǒng)中，往往同時創(chuàng)建多個進程。在單處理器的情況下，每次只能有一個進程處于運行態(tài)，其他的進程處于就緒狀態(tài)或等待狀態(tài)。為了便于管理，通常把處于相同狀態(tài)的進程的進程控制塊鏈接在一起。單處理器系統(tǒng)中，正在運行的進程只有一個。因此，單處

5、理器系統(tǒng)中進程控制塊分成一個正在運行進程的進程控制塊、就緒進程的進程控制塊組織成的就緒隊列和等待進程的進程控制塊組成的等待隊列。由于實驗?zāi)M的是進程調(diào)度，沒有對等待隊列的操作，所以實驗中只有一個指向正在運行進程的進程控制塊指針和一個就緒進程的進程控制塊隊列指針。操作系統(tǒng)的實現(xiàn)中，系統(tǒng)往往在主存中劃分出一個連續(xù)的專門區(qū)域存放系統(tǒng)的進程控制塊，實驗中應(yīng)該用數(shù)組模擬這個專門的進程控制塊區(qū)域，定義如下：#define n 10 /假定系統(tǒng)允許進程個數(shù)為10struct pcb pcbarean; /模擬進程控制塊區(qū)域的數(shù)組 這樣，進程控制塊的鏈表實際上是數(shù)據(jù)結(jié)構(gòu)中使用的靜態(tài)鏈表。進程控制塊的鏈接方式可

6、以采用單向和雙向鏈表，實驗中，進程控制塊隊列采用單向不循環(huán)靜態(tài)鏈表。為了管理空閑進程控制塊，還應(yīng)該將空閑控制塊鏈接成一個隊列。實驗中采用時間片輪轉(zhuǎn)調(diào)度算法，這種算法是將進程控制塊按照進入就緒隊列的先后次序排成隊列。關(guān)于就緒隊列的操作就是從隊頭摘下一個進程控制塊和從隊尾掛入一個進程控制塊。因此為就緒隊列定義兩個指針，一個頭指針，指向就緒隊列的第一個進程控制塊；一個尾指針，指向就緒隊列的最后一個進程控制塊。實驗中指向運行進程的進程控制塊指針、就緒隊列指針和空閑進程控制塊隊列指針定義如下：int run; /定義指向正在運行進程的進程控制塊的指針structint head; int tail;re

7、ady; /定義指向就緒隊列的頭指針head和尾指針tailint pfree; /定義指向空閑進程控制塊隊列的指針以上是如何組織進程，下面考慮如何創(chuàng)建進程。進程創(chuàng)建是一個原語，因此在實驗中應(yīng)該用一個函數(shù)實現(xiàn)，進程創(chuàng)建的過程應(yīng)該包括：申請進程控制塊：進程控制塊的數(shù)量是有限的，如果沒有空閑進程控制塊，則進程不能創(chuàng)建，如果申請成功才可以執(zhí)行第步；申請資源：除了進程控制塊外，還需要有必要的資源才能創(chuàng)建進程，如果申請資源不成功，則不能創(chuàng)建進程，并且歸還已申請的進程控制塊；如果申請成功，則執(zhí)行第三步，實驗無法申請資源，所以模擬程序忽略了申請資源這一步；填寫進程控制塊：將該進程信息寫入進程控制塊內(nèi)，實驗中

8、只有進程標識符、進程狀態(tài)可以填寫，每個進程現(xiàn)場信息中的寄存器內(nèi)容由于沒有具體數(shù)據(jù)而使用進程（模擬進程創(chuàng)建時，需輸入進程標識符字，進程標識符本應(yīng)系統(tǒng)建立，并且是惟一的，輸入時注意不要沖突），剛剛創(chuàng)建的進程應(yīng)該為就緒態(tài)，然后轉(zhuǎn)去執(zhí)行第四步；掛入就緒隊列：如果原來就緒隊列不為空，則將該進程控制塊掛入就緒隊列尾部，并修改就緒隊列尾部指針；如果原來就緒隊列為空，則將就緒隊列的頭指針、尾指針均指向該進程控制塊，進程創(chuàng)建完成。進程創(chuàng)建流程圖如圖2.2所示。多道程序設(shè)計的系統(tǒng)中，處于就緒態(tài)的進程往往是多個，它們都要求占用處理器，可是單處理器系統(tǒng)的處理器只有一個，進程調(diào)度就是解決這個處理器競爭問題的。進程調(diào)度的

9、任務(wù)就是按照某種算法從就緒進程隊列中選擇一個進程，讓它占有處理器。因此進程調(diào)度程序就應(yīng)該包括兩部分，一部分是在進程就緒隊列中選擇一個進程，并將其進程控制塊從進程就緒隊列中摘下來，另一部分工作就是分配處理器給選中的進程，也就是將指向正在運行進程的進程控制塊指針指向該進程的進程控制塊，并將該進程的進程控制塊信息寫入處理器的各個寄存器中。圖2.2 進程創(chuàng)建流程圖實驗中采用時間片輪轉(zhuǎn)調(diào)度算法。時間片輪轉(zhuǎn)調(diào)度算法讓就緒進程按就緒的先后次序排成隊列，每次總是選擇就緒隊列中的第一個進程占有處理器，但是規(guī)定只能使用一個“時間片”。時間片就是規(guī)定進程一次使用處理器的最長時間。實驗中采用每個進程都使用相同的不變的

10、時間片。采用時間片輪轉(zhuǎn)調(diào)度算法的進程調(diào)度流程圖如圖2.3所示。完成上述功能后，編寫主函數(shù)進行測試：首先建立一個就緒隊列，手工輸入信息建立幾個進程；然后進行進程調(diào)度；最后將指向正在運行進程的指針指向的進程控制塊的內(nèi)容輸出，察看結(jié)果。5課外題編程實現(xiàn)采用優(yōu)先數(shù)調(diào)度算法的進程調(diào)度。6參考程序圖2.3 進程調(diào)度流程圖#include stdio.h#define running 1/用running表示進程處于運行態(tài)#define aready 2/用aready表示進程處于就緒態(tài)#define blocking 3/用blocking表示進程處于等待態(tài)#define sometime 5/用some

11、time表示時間片大小#define n 10/假定系統(tǒng)允許進程個數(shù)為nstructint name;/進程標識符int status;/進程狀態(tài)int ax,bx,cx,dx;/進程現(xiàn)場信息，通用寄存器內(nèi)容int pc;/進程現(xiàn)場信息，程序狀態(tài)寄存器內(nèi)容int psw;/下一個進程控制塊的位置int next;/模擬進程控制塊的數(shù)組pcbarean;/模擬進程控制塊區(qū)域的數(shù)組int PSW,AX,BX,CX,DX,PC,TIME;/模擬寄存器int run;/定義指向正在運行進程的進程控制塊的指針struct int head;int tail;ready;/定于就緒隊列的頭指針head和尾

12、指針tailint pfree;/定義指向空閑進程控制塊隊列的指針sheduling()/進程調(diào)度函數(shù)int i;if(ready.head=-1)printf(無就緒進程n);return;i=ready.head;/就緒隊列頭指針賦給iready.head=pcbareaready.head.next;/就緒隊列頭指針后移if(ready.head=-1)ready.tail=-1;/就緒隊列為空，修正尾指針ready.tailpcbareai.status=running;/修改進程控制塊狀態(tài)TIME=sometime;/設(shè)置相對時鐘寄存器/恢復(fù)該進程現(xiàn)場信息：AX=pcbarearun

13、.ax;BX=pcbarearun.bx;CX=pcbarearun.cx;DX=pcbarearun.dx;PC=pcbarearun.pc;PSW=pcbarearun.psw;run=i;/修改指向運行進程的指針/進程調(diào)度函數(shù)結(jié)束create(int x)/創(chuàng)建進程int i;if(pfree=-1)/空閑進程控制塊隊列為空printf(無空閑進程控制塊，進程創(chuàng)建失敗n);return;i=pfree;/取空閑進程控制塊隊列的第一個pfree=pcbareapfree.next;/pfree后移/填寫該進程控制塊內(nèi)容：=x;pcbareai.status=are

14、ady;pcbareai.ax=x;pcbareai.bx=x;pcbareai.cx=x;pcbareai.dx=x;pcbareai.pc=x;pcbareai.psw=x;if(ready.head!=-1)/就緒隊列不空時，掛入就緒隊列方式pcbareaready.tail.next=i;ready.tail=i;pcbareaready.tail.next=-1;else /就緒隊列空時,掛入就緒隊列方式ready.head=i;ready.tail=i;pcbareaready.tail.next=-1;/進程創(chuàng)建函數(shù)結(jié)束main()/系統(tǒng)初始化int num,i,j,block;

15、run=ready.head=ready.tail=block=-1;pfree=0;for(j=0;j=0)create(num);scanf(%d,&num);sheduling();/進程調(diào)度if(run!=-1)printf(進程標識符 進程狀態(tài) 寄存器內(nèi)容:ax bx cx dx pc psw:n);printf(%8d%10d%3d%3d%3d%3d%3d%3dn,,pcbarearun.status,pcbarearun.ax,pcbarearun.bx,pcbarearun.cx,pcbarearun.dx,pcbarearun.pc,pcbare

16、arun.psw);/main()結(jié)束實驗三 動態(tài)分區(qū)存儲管理方式的主存分配回收1實驗?zāi)康纳钊肓私鈩討B(tài)分區(qū)存儲管理方式的主存分配回收的實現(xiàn)。2實驗預(yù)備知識存儲管理中動態(tài)分區(qū)的管理方式。3實驗內(nèi)容編寫程序完成動態(tài)分區(qū)存儲管理方式的主存分配回收的實現(xiàn)。實驗具體包括：首先確定主存空間分配表；然后采用最優(yōu)適應(yīng)算法完成主存空間的分配，完成主存空間的回收；最后編寫主函數(shù)對所作工作進程測試。4提示與講解動態(tài)分區(qū)管理方式預(yù)先不將主存劃分成幾個區(qū)域，而把主存除操作系統(tǒng)占用區(qū)域外的空間看作一個大的空閑區(qū)。當作業(yè)要求裝入主存時，根據(jù)作業(yè)需要的主存空間的大小查詢主存內(nèi)各個空閑區(qū)，當從主存空間中找到一個大于或等于該作業(yè)

17、大小的主存空閑區(qū)時，選擇其中一個空閑區(qū)，按作業(yè)需求量劃出一個分區(qū)裝入該作業(yè)。作業(yè)執(zhí)行完后，它所占的主存分區(qū)被收回，成為一個空閑區(qū)。如果該空閑區(qū)的相鄰分區(qū)也是空閑區(qū)，則需要將相鄰空閑區(qū)合并成一個空閑區(qū)。實現(xiàn)動態(tài)分區(qū)的分配和回收，主要考慮的問題有三個：第一，設(shè)計記錄主存使用情況的數(shù)據(jù)表格，用來記錄空閑區(qū)和作業(yè)占用的區(qū)域；第二，在設(shè)計的數(shù)據(jù)表格基礎(chǔ)上設(shè)計主存分配算法；第三，在設(shè)計的數(shù)據(jù)表格基礎(chǔ)上設(shè)計主存回收算法。首先，考慮第一個問題：設(shè)計記錄主存使用情況的數(shù)據(jù)表格，用來記錄空閑區(qū)和作業(yè)占用的區(qū)域。由于動態(tài)分區(qū)的大小是由作業(yè)需求量決定的，故分區(qū)的長度是預(yù)先不固定的，且分區(qū)的個數(shù)也隨主存分配和回收變動。

18、總之，所有分區(qū)情況隨時可能發(fā)生變化，數(shù)據(jù)表格的設(shè)計必須和這個特點相適應(yīng)。由于分區(qū)長度不同，因此設(shè)計的表格應(yīng)該包括分區(qū)在主存中的起始地址和長度。由于分配時空閑區(qū)有時會變成兩個分區(qū)：空閑區(qū)和已分分區(qū)，回收主存分區(qū)時，可能會合并空閑分區(qū)，這樣如果整個主存采用一張表格記錄已分分區(qū)和空閑區(qū)，就會使表格操作繁瑣。主存分配時查找空閑區(qū)進行分配，然后填寫已分配區(qū)表，主要操作在空閑區(qū)；某個作業(yè)執(zhí)行完后，將該分區(qū)變成空閑區(qū)，并將其與相鄰的空閑區(qū)合并，主要操作也在空閑區(qū)。由此可見，主存的分配和回收主要是對空閑區(qū)的操作。這樣為了便于對主存空間的分配和回收，就建立兩張分區(qū)表記錄主存使用情，一張表格記錄作業(yè)占用分區(qū)的“已

19、分配區(qū)表”；一張是記錄空閑區(qū)的“空閑區(qū)表”。這兩張表的實現(xiàn)方法一般有兩種，一種是鏈表形式，一種是順序表形式。在實驗中，采用順序表形式，用數(shù)組模擬。由于順序表的長度必須提前固定，所以無論是“已分配區(qū)表”還是“空閑區(qū)表”都必須事先確定長度。它們的長度必須是系統(tǒng)可能的最大項數(shù)，系統(tǒng)運行過程中才不會出錯，因而在多數(shù)情況下，無論是“已分配區(qū)表”還是“空閑區(qū)表”都有空閑欄目。已分配區(qū)表中除了分區(qū)起始地址、長度外，也至少還要有一項“標志”，如果是空閑欄目，內(nèi)容為“空”，如果為某個作業(yè)占用分區(qū)的登記項，內(nèi)容為該作業(yè)的作業(yè)名；空閑區(qū)表中除了分區(qū)起始地址、長度外，也要有一項“標志”，如果是空閑欄目，內(nèi)容為“空”，

20、如果為某個空閑區(qū)的登記項，內(nèi)容為“未分配”（。在實際系統(tǒng)中，這兩表格的內(nèi)容可能還要多，實驗中僅僅使用上述必須的數(shù)據(jù)。為此,“已分配區(qū)表”和“空閑區(qū)表”在實驗中有如下的結(jié)構(gòu)定義。已分配區(qū)表的定義：#define n 10 /假定系統(tǒng)允許的最大作業(yè)數(shù)量為nstructfloat address; /已分分區(qū)起始地址 float length; /已分分區(qū)長度，單位為字節(jié) int flag; /已分配區(qū)表登記欄標志，“0”表示空欄目，實驗中只支持一個字符的作業(yè)名used_tablen; /已分配區(qū)表空閑區(qū)表的定義：#define m 10 /假定系統(tǒng)允許的空閑區(qū)表最大為mstructfloat ad

21、dress; /空閑區(qū)起始地址 float length; /空閑區(qū)長度，單位為字節(jié) int flag; /空閑區(qū)表登記欄標志，用“0”表示空欄目，用“1”表示未分配free_tablem; /空閑區(qū)表其中分區(qū)起始地址和長度數(shù)值太大，超出了整型表達范圍，所以采用了float類型。然后，就要考慮如何在設(shè)計的數(shù)據(jù)表格上進行主存的分配。當要裝入一個作業(yè)時，從空閑區(qū)表中查找標志為“未分配”的空閑區(qū)，從中找出一個能容納該作業(yè)的空閑區(qū)。如果找到的空閑區(qū)正好等于該作業(yè)的長度，則把該分區(qū)全部分配給作業(yè)。這時應(yīng)該把該空閑區(qū)登記欄中的標志改為“空”，同時在已分配區(qū)表中找到一個標志為“空”的欄目登記新裝入作業(yè)所占用

22、分區(qū)的起始地址、長度和作業(yè)名。如果找到的空閑區(qū)大于作業(yè)長度，則把空閑區(qū)分成兩部分，一部分用來裝入作業(yè)，另外一部分仍為空閑區(qū)。這時只要修改原空閑區(qū)的長度，且把新裝入的作業(yè)登記到已分配區(qū)表中。實驗中主存分配算法采用“最優(yōu)適應(yīng)”算法。最優(yōu)適應(yīng)算法是按作業(yè)要求挑選一個能滿足作業(yè)要求的最小空閑區(qū)，這樣保證可以不去分割一個大的區(qū)域，使裝入大作業(yè)時比較容易得到滿足。但是最優(yōu)適應(yīng)算法容易出現(xiàn)找到的一個分區(qū)可能只比作業(yè)所要求的長度略大一點的情況，這時，空閑區(qū)分割后剩下的空閑區(qū)就很小，這種很小的空閑區(qū)往往無法使用，卻影響了主存的使用。為了一定程度上解決這個問題，如果空閑區(qū)的大小比作業(yè)要求的長度略大一點，不再將空閑

23、區(qū)分成已分分區(qū)和空閑區(qū)兩部分，而是將整個空閑區(qū)分配給作業(yè)。在實現(xiàn)最優(yōu)適應(yīng)算法時，可把空閑區(qū)按長度以遞增方式登記在空閑區(qū)表中。分配時順序查找空閑表，查找到的第一個空閑區(qū)就是滿足作業(yè)要求的最小分區(qū)。這樣查找速度快，但是為使空閑區(qū)按長度以遞增順序登記在空閑表中，就必須在分配回收時進行空閑區(qū)表的調(diào)整。空閑區(qū)表調(diào)整時移動表目的代價要高于查詢整張表的代價，所以實驗中不采用空閑區(qū)有序登記在空閑表中的方法。動態(tài)分區(qū)方式的主存分配流程圖如圖2.4所示。最后是動態(tài)分區(qū)方式下的主存回收問題。動態(tài)分區(qū)方式下回收主存空間時，應(yīng)該檢查是否有與歸還區(qū)相鄰的空閑區(qū)。若有，則應(yīng)該合并成一個空閑區(qū)。一個歸還區(qū)可能有上鄰空閑區(qū)，也

24、可能有下鄰空閑區(qū)，或者既有上鄰空閑區(qū)又有下鄰空閑區(qū)，或者既無上鄰空閑區(qū)也無下鄰空閑區(qū)。在實現(xiàn)回收時，首先將作業(yè)歸還的區(qū)域在已分配表中找到，將該欄目的狀態(tài)變?yōu)椤翱铡保缓髾z查空閑區(qū)表中標志為“未分配”的欄目，查找是否有相鄰空閑區(qū)；最后，合并空閑區(qū)，修改空閑區(qū)表。假定作業(yè)歸還的分區(qū)起始地址為S，長度為L，則： 歸還區(qū)有下鄰空閑區(qū)如果S+L正好等于空閑區(qū)表中某個登記欄目（假定為第j欄）的起始地址，則表明歸還區(qū)有一個下鄰空閑區(qū)。這時只要修改第j欄登記項的內(nèi)容：起始地址=S；第j欄長度=第j欄長度+L；則第j欄指示的空閑區(qū)是歸還區(qū)和下鄰空閑區(qū)合并后的大空閑區(qū)； 歸還區(qū)有上鄰空閑區(qū)如果空閑區(qū)表中某個登記欄

25、目（假定為第k欄）的“起始地址+長度”正好等于S，則表明歸還區(qū)有一個上鄰空閑區(qū)。這時要修改第k欄登記項的內(nèi)容（起始地址不變）：第k欄長度=第k欄長度+L；于是第k欄指示的空閑區(qū)是歸還區(qū)和上鄰空閑區(qū)合并后的大空閑區(qū)； 歸還區(qū)既有上鄰空閑區(qū)又有下鄰空閑區(qū)如果S+L正好等于空閑區(qū)表中某個登記欄目（假定為第j欄）的起始地址，同時還有某個登記欄目（假定為第k欄）的“起始地址+長度”正好等于S，這表明歸還區(qū)既有一個上鄰空閑區(qū)又有一個下鄰空閑區(qū)。此時對空閑區(qū)表的修改如下：第k欄長度=第k欄長度+第j欄長度+L；（第k欄起始地址不變）第j欄狀態(tài)=“空”；（將第j欄登記項刪除）這樣，第k欄指示的空閑區(qū)是歸還區(qū)和

26、上、下鄰空閑區(qū)合并后的大空閑區(qū)；原來的下鄰空閑區(qū)登記項（第j欄）被刪除，置為“空”。 2.4 動態(tài)分區(qū)最優(yōu)分配算法流程圖圖2.5 動態(tài)分區(qū)回收流程圖 歸還區(qū)既無上鄰空閑區(qū)又無下鄰空閑區(qū)如果在檢查空閑區(qū)表時，無上述三種情況出現(xiàn)，則表明歸還區(qū)既無上鄰空閑區(qū)又無下鄰空閑區(qū)。這時，應(yīng)該在空閑區(qū)表中查找一個狀態(tài)為“空”的欄目（假定查到的是第t欄），則第t欄的內(nèi)容修改如下：第t欄起始地址=S；第t欄長度=L；第t欄狀態(tài)=“未分配”這樣，第t欄指示的空閑區(qū)是歸還區(qū)。按上述方法歸還主存區(qū)域的流程圖如圖2.5所示。由于是實驗，沒有真正的主存要分配，所以在實驗中，首先應(yīng)建立一張空閑區(qū)表，初始狀態(tài)只有一個空閑登記項

27、（假定的主存空閑區(qū)）和一張所有狀態(tài)都為“空”的已分配區(qū)表，假定主存空間110KB，操作系統(tǒng)占用10KB,其余為空閑區(qū)；然后，可以選擇進行主存分配或主存回收，如果是分配，要求輸入作業(yè)名和所需主存空間大小，如果是回收，輸入回收作業(yè)的作業(yè)名，循環(huán)進行主存分配和回收后，如果需要，則顯示兩張表的內(nèi)容，以檢查主存的分配和回收是否正確。5.課外題編程實現(xiàn)頁式存儲管理的主存分配和回收。用鏈表方式表示主存空間分配情況，完成動態(tài)分區(qū)管理方式下的主存空間的分配和回收。#define n 10 /假定系統(tǒng)允許的最大作業(yè)數(shù)量為n#define m 10 /假定系統(tǒng)允許的空閑區(qū)表最大為m#define minisize

28、100struct float address; /已分分區(qū)起始地址 float length; /已分分區(qū)長度，單位為字節(jié) int flag; /已分配區(qū)表登記欄標志，用0表示空欄目，實驗中只支持一個字符的作業(yè)名used_tablen; /已分配區(qū)表structfloat address; /空閑區(qū)起始地址 float length; /空閑區(qū)長度，單位為字節(jié) int flag; /空閑區(qū)表登記欄標志，用0表示空欄目，用1表示未分配free_tablem; /空閑區(qū)表 allocate(J,xk) /采用最優(yōu)分配算法分配xk大小的空間 char J; float xk;int i,k; fl

29、oat ad; k=-1; for(i=0;i=xk&free_tablei.flag=1) if(k=-1|free_tablei.lengthfree_tablek.length) k=i; if(k=-1) /未找到可用空閑區(qū)，返回 printf(無可用空閑區(qū)n); return; /找到可用空閑區(qū)，開始分配：若空閑區(qū)大小與要求分配的空間差小于minisize大小，則空閑區(qū)全部分配；若空閑區(qū)大小與要求分配的空間差大于minisize大小，則從空閑區(qū)劃出一部分分配 if(free_tablek.length-xk=minisize) free_tablek.flag=0; ad=free_

30、tablek.address; xk=free_tablek.length; else free_tablek.length=free_tablek.length-xk; ad=free_tablek.address+free_tablek.length; /修改已分配區(qū)表 i=0; while(used_tablei.flag!=0&i=n) /無表目填寫已分分區(qū) printf(無表目填寫已分分區(qū)，錯誤n); /修正空閑區(qū)表 if(free_tablek.flag=0) /前面找到的是整個空閑區(qū) free_tablek.flag=1; else /前面找到的是某個空閑區(qū)的一部分 free_t

31、ablek.length=free_tablek.length+xk; return; else /修改已分配區(qū)表 used_tablei.address=ad; used_tablei.length=xk; used_tablei.flag=J; return; /主存分配函數(shù)結(jié)束 reclaim(J)/回收作業(yè)名為J的作業(yè)所占主存空間 char J; int i,k,j,s,t; float S,L; /尋找已分配區(qū)表中對應(yīng)登記項 s=0; while(used_tables.flag!=J|used_tables.flag=0)&s=n) /在已分配區(qū)表中找不到名字為J的作業(yè) print

32、f(找不到該作業(yè)n); return; /修改已分配區(qū)表 used_tables.flag=0; /取得歸還分區(qū)的起始地址S和長度L S=used_tables.address; L=used_tables.length; j=-1;k=-1;i=0; /尋找回收分區(qū)的上下鄰空閑區(qū)，上鄰表目k，下鄰表目j while(im&(j=-1|k=-1) if(free_tablei.flag=0) if(free_tablei.address+free_tablei.length=S)k=i; /找到上鄰 if(free_tablei.address=S+L)j=i; /找到下鄰 i+; if(k!

33、=-1) if(j!=-1) / 上鄰空閑區(qū)，下鄰空閑區(qū)，三項合并 free_tablek.length=free_tablej.length+free_tablek.length+L; free_tablej.flag=0; else / 上鄰空閑區(qū)，下鄰非空閑區(qū)，與上鄰合并 free_tablek.length=free_tablek.length+L; else if(j!=-1) /上鄰非空閑區(qū)，下鄰為空閑區(qū)，與下鄰合并 free_tablej.address=S; free_tablej.length=free_tablej.length+L; else /上下鄰均為非空閑區(qū)，回收區(qū)

34、域直接填入 /在空閑區(qū)表中尋找空欄目 t=0; while(free_tablet.flag=1&t=m) /空閑區(qū)表滿,回收空間失敗,將已分配區(qū)表復(fù)原 printf(主存空閑表沒有空間,回收空間失敗n); used_tables.flag=J; return; free_tablet.address=S; free_tablet.length=L; free_tablet.flag=1; return(t); /主存歸還函數(shù)結(jié)束 main( ) int i,a; float xk; char J; /空閑區(qū)表初始化 free_table0.address=10240; free_table0

35、.length=; free_table0.flag=1; for(i=1;im;i+) free_tablei.flag=0; /已分配區(qū)表初始化 for(i=0;in;i+) used_tablei.flag=0; while(1) printf(選擇功能項（0-退出,1-分配主存,2-回收主存,3-顯示主存）n); printf(選擇功項(03) :); scanf(%d,&a); switch(a) case 0: exit(0); /a=0程序結(jié)束 case 1: /a=1分配主存空間 printf(輸入作業(yè)名J和作業(yè)所需長度xk: ); scanf(%*c%c%f,&J,&xk);

36、 allocate(J,xk);/分配主存空間 break; case 2: /a=2回收主存空間 printf(輸入要回收分區(qū)的作業(yè)名); scanf(%*c%c,&J); reclaim(J);/回收主存空間 break; case 3: /a=3顯示主存情況，輸出空閑區(qū)表和已分配區(qū)表 printf(輸出空閑區(qū)表：n起始地址 分區(qū)長度 標志n); for(i=0;im;i+) printf(%5.0f%10.0f%6dn,free_tablei.address,free_tablei.length, free_tablei.flag); printf( 按任意鍵,輸出已分配區(qū)表n); ge

37、tch(); printf( 輸出已分配區(qū)表：n起始地址 分區(qū)長度 標志n); for(i=0;in;i+) if(used_tablei.flag!=0) printf(%6.0f%9.0f%6cn,used_tablei.address,used_tablei.length, used_tablei.flag); else printf(%6.0f%9.0f%6dn,used_tablei.address,used_tablei.length, used_tablei.flag); break; default:printf(沒有該選項n); /case /while /main( )結(jié)束

38、實驗四 頁式虛擬存儲管理中地址轉(zhuǎn)換和缺頁中斷1實驗?zāi)康纳钊肓私忭撌酱鎯芾砣绾螌崿F(xiàn)地址轉(zhuǎn)換；進一步認識頁式虛擬存儲管理中如何處理缺頁中斷。2實驗預(yù)備知識頁式存儲管理中的地址轉(zhuǎn)換的方法；頁式虛擬存儲的缺頁中斷處理方法。3實驗內(nèi)容編寫程序完成頁式虛擬存儲管理中地址轉(zhuǎn)換過程和模擬缺頁中斷的處理。實驗具體包括：首先對給定的地址進行地址轉(zhuǎn)換工作，若發(fā)生缺頁則先進行缺頁中斷處理，然后再進行地址轉(zhuǎn)換；最后編寫主函數(shù)對所作工作進程測試。假定主存64KB，每個主存塊1024字節(jié)，作業(yè)最大支持到64KB，系統(tǒng)中每個作業(yè)分得主存塊4塊。4提示與講解頁式存儲管理中地址轉(zhuǎn)換過程很簡單，假定主存塊的大小為2n字節(jié)，主存大

39、小為2m字節(jié)和邏輯地址m位，則進行地址轉(zhuǎn)換時，首先從邏輯地址中的高m-n位中取得頁號，然后根據(jù)頁號查頁表，得到塊號，并將塊號放入物理地址的高m-n位，最后從邏輯地址中取得低n位放入物理地址的低n位就得到了物理地址，過程如圖2.61所示。頁 號 頁內(nèi)地址塊 號 塊內(nèi)地址頁號 塊號物理地址邏輯地址m n n-1 0m n n-1 0圖2.6 頁式存儲管理系統(tǒng)地址轉(zhuǎn)換示意圖地址轉(zhuǎn)換是由硬件完成的，實驗中使用軟件程序模擬地址轉(zhuǎn)換過程，模擬地址轉(zhuǎn)換的流程圖如圖2.7所示（實驗中假定主存64KB，每個主存塊1024字節(jié)，即n=10,m=16，物理地址中塊號6位、塊內(nèi)地址10位；作業(yè)最大64KB，即m=16

40、，邏輯地址中頁號6位、頁內(nèi)地址10位）。在頁式虛擬存儲管理方式中，作業(yè)信息作為副本放在磁盤上，作業(yè)執(zhí)行時僅把作業(yè)信息的部分頁面裝入主存儲器，作業(yè)執(zhí)行時若訪問的頁面在主存中，則按上述方式進行地址轉(zhuǎn)換，若訪問的頁面不在主存中，則產(chǎn)生一個“缺頁中斷”，由操作系統(tǒng)把當前所需的頁面裝入主存儲器后，再次執(zhí)行時才可以按上述方法進行地址轉(zhuǎn)換。頁式虛擬存儲管理方式中頁表除頁號和該頁對應(yīng)的主存塊號外，至少還要包括存在標志（該頁是否在主存），磁盤位置（該頁的副本在磁盤上的位置）和修改標志（該頁是否修改過）。這樣，在實驗中頁表格式如圖2.7所示。頁表用數(shù)組模擬，在實驗中頁表數(shù)據(jù)結(jié)構(gòu)定義為：define n 32 /實

41、驗中假定的頁表長度，頁表的長度實際上是由系統(tǒng)按照作業(yè)長度決定的structint lnumber; /頁號 int flag; /表示該頁是否在主存，“1”表示在主存，“0”表示不在主存 int pnumber; /該頁所在主存塊的塊號 int write; /該頁是否被修改過，“1”表示修改過，“0”表示沒有修改過 int dnumber; /該頁存放在磁盤上的位置，即磁盤塊號pagen; /頁表定義圖2.7 模擬地址轉(zhuǎn)換的流程圖缺頁處理過程簡單闡述如下： 根據(jù)當前執(zhí)行指令中邏輯地址中的頁號查頁表，判斷該頁是否在主存儲器中，若該頁標志為“0”，形成缺頁中斷。中斷裝置通過交換PSW讓操作系統(tǒng)的

42、中斷處理程序占用處理器； 操作系統(tǒng)處理缺頁中斷的方法就是查主存分配表，找一個空閑主存塊；若無空閑塊，查頁表，選擇一個已在主存的頁面，把它暫時調(diào)出主存。若在執(zhí)行過程中該頁被修改過，則需將該頁信息寫回磁盤，否則不必寫回； 找出該頁的磁盤位置，啟動磁盤讀出該頁信息，把磁盤上讀出的信息裝入第2步找到的主存塊，修改頁表中該頁的標志為“1”； 由于產(chǎn)生缺頁中斷的那條指令沒有執(zhí)行完，所以頁面裝入后應(yīng)重新執(zhí)行被中斷的指令。當重新執(zhí)行該指令時，由于要訪問的頁面已在主存中，所以可正常執(zhí)行。關(guān)于第步的查找裝入新頁面的主存塊的處理方式，不同系統(tǒng)采用的策略可能有所不同，這里采用局部置換算法，就是每個作業(yè)分得一定的主存塊

43、，只能在分得的主存塊內(nèi)查找空閑塊，若無空閑主存塊，則從該作業(yè)中選擇一個頁面淘汰出主存。實驗中使用局部置換算法。使用局部置換算法時，存在這樣一個問題：就是在分配給作業(yè)主存空間時，裝入哪些頁？有的系統(tǒng)采取不裝入任何一頁，當執(zhí)行過程中需要時才將其調(diào)入。有的系統(tǒng)采用頁面預(yù)置的方法，就是估計可能某些頁面會先用到，在分配主存塊后將這些頁面裝入。實驗中，采用第二種方法，分配主存空間時將前幾頁調(diào)入主存，假定系統(tǒng)中每個作業(yè)分得主存塊m（m=4）塊，則將第0m-1頁裝入主存。因為是模擬硬件工作，所以實驗中如果訪問的頁不在主存時，則輸出該頁頁號，表示硬件產(chǎn)生缺頁中斷，然后直接轉(zhuǎn)去缺頁中斷處理；由于采用頁面預(yù)置方法，

44、在給定的主存塊中一定無空閑塊，只能淘汰已在主存的一頁；沒有啟動磁盤的工作，淘汰的頁需要寫回磁盤時，用輸出頁號表示，調(diào)入新的一頁時，將該頁在頁表中的存在標志置為“1”，輸出頁號表示將該頁調(diào)入主存。圖2.8 采用先進先出頁面置換算法的缺頁中斷流程圖主存中無空閑塊時，為裝入一個頁面，必須按某種算法從已在主存的頁中選擇一頁，將它暫時調(diào)出主存，讓出主存空間，用來存放需裝入的頁面，這個工作稱為“頁面調(diào)度”。如何選擇調(diào)出的頁是很重要的，常用的頁面調(diào)度算法有先進先出算法、最近最少用算法和最近最不常用算法。實驗中使用先進先出調(diào)度算法。先進先出調(diào)度算法總是選擇駐留在主存時間最長的一頁調(diào)出。先進先出算法簡單，易實現(xiàn)

45、?？梢园言谥鞔鎯ζ鞯捻摰捻撎柊催M入主存的先后次序排成隊列，每次總是調(diào)出隊首的頁，當裝入一個新頁后，把新頁的頁號排入隊尾。實驗中，用一個數(shù)組存放頁號的隊列。假定分配給作業(yè)的主存塊數(shù)為m，數(shù)組可由m個元素組成，p0，p1pm-1；隊首指針head；采用頁面預(yù)置的方法，頁號隊列的長度總是m，tail等于(head+1)%m。因此可以使用一個指針，只用head即可。在裝入一個新的頁時，裝入頁和淘汰頁同時執(zhí)行，當裝入一個新的頁時，將其頁號存入數(shù)組：淘汰頁的頁號=phead;phead=新裝入頁的頁號；head=(head+1)%m;實驗中，采用先進先出頁面置換算法的缺頁中斷流程圖如圖2.8所示。圖2.9 一條指令執(zhí)行的模擬流程圖實驗執(zhí)行一條指令時，不模擬指令的執(zhí)行，只是考慮指令執(zhí)行是否修改頁面，若修改頁面，則將該頁的頁表中修改標志為置“1”，然后輸出轉(zhuǎn)換后的物理地址，并輸出物理地址來表示一條指令執(zhí)行完成；如果訪問的頁不在主存時，則產(chǎn)生缺頁中斷，然后直接轉(zhuǎn)去缺頁中斷處理，最后模擬中斷返回，就是返回重新進行地址轉(zhuǎn)換。一條指令執(zhí)行的模擬流程圖如圖2.9所示。因為沒有實際主存，所以在模擬程序中首先手工輸入頁表信息，創(chuàng)建該作業(yè)的頁表；然后循環(huán)執(zhí)行假定的指令，觀察地址轉(zhuǎn)換情況。5課外題采用LRU頁面調(diào)度算法編程實現(xiàn)上述虛擬頁式存儲管理的地址轉(zhuǎn)換。#incl