操作系統(tǒng) 上機(jī)操作實(shí)驗(yàn)題目.doc

此文檔收集于網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系網(wǎng)站刪除實(shí)驗(yàn)一 批處理系統(tǒng)的作業(yè)調(diào)度一、實(shí)驗(yàn)?zāi)康?1.加深對(duì)作業(yè)概念的理解。 2.深入了解批處理系統(tǒng)如何組織作業(yè)、管理作業(yè)和調(diào)度作業(yè)。二、實(shí)驗(yàn)預(yù)備知識(shí) 1.作業(yè)的概念。 2.作業(yè)的創(chuàng)建。 3.作業(yè)的調(diào)度。三、實(shí)驗(yàn)內(nèi)容 編寫(xiě)程序完成批處理系統(tǒng)中的作業(yè)調(diào)度，要求采用響應(yīng)比高者優(yōu)先的作業(yè)調(diào)度算法。實(shí)驗(yàn)具體包括：首先確定作業(yè)控制塊的內(nèi)容，作業(yè)控制塊的組成方式；然后完成作業(yè)調(diào)度；最后編寫(xiě)主函數(shù)對(duì)所做工作進(jìn)行測(cè)試。四、提示與講解 操作系統(tǒng)根據(jù)允許并行工作的道數(shù)和一定的算法從系統(tǒng)中選取若干作業(yè)把它們裝入主存儲(chǔ)器，使它們有機(jī)會(huì)獲得處理器運(yùn)行，這項(xiàng)工作被稱為“作業(yè)調(diào)度”。實(shí)現(xiàn)這部分功能的程序就是“作業(yè)調(diào)度程序”。作業(yè)調(diào)度的實(shí)現(xiàn)主要有兩個(gè)問(wèn)題，一個(gè)是如何將系統(tǒng)中的作業(yè)組織起來(lái)；另一個(gè)是如何進(jìn)行作業(yè)調(diào)度。 為了將系統(tǒng)中的作業(yè)組織起來(lái)，需要為每個(gè)進(jìn)入系統(tǒng)的作業(yè)建立檔案以記錄和作業(yè)相關(guān)的信息，例如作業(yè)名、作業(yè)所需資源、作業(yè)執(zhí)行時(shí)間、作業(yè)進(jìn)入系統(tǒng)的時(shí)間、作業(yè)信息存儲(chǔ)器中的位置、指向下一個(gè)作業(yè)控制塊的指針等信息。這個(gè)記錄作業(yè)相關(guān)信息的數(shù)據(jù)塊稱為作業(yè)控制塊（JCB），并將系統(tǒng)中等待作業(yè)調(diào)度的作業(yè)控制塊組織成一個(gè)隊(duì)列，這個(gè)隊(duì)列稱為后備隊(duì)列。一個(gè)作業(yè)全部信息進(jìn)入系統(tǒng)后，就為其建立作業(yè)控制塊，并掛入后備隊(duì)列。當(dāng)進(jìn)行作業(yè)調(diào)度時(shí)，從后備隊(duì)列中查找選擇作業(yè)。 由于實(shí)驗(yàn)中沒(méi)有實(shí)際作業(yè)，作業(yè)控制塊中的信息內(nèi)容只使用了實(shí)驗(yàn)中需要的數(shù)據(jù)。作業(yè)控制塊中首先應(yīng)該包括作業(yè)名；其次是作業(yè)所需資源，根據(jù)需要，實(shí)驗(yàn)中只包括需要主存的大?。ú捎每梢苿?dòng)的動(dòng)態(tài)分區(qū)方式管理主存，作業(yè)大小就是需要主存的大?。?、需要打印機(jī)的數(shù)量和需要磁帶機(jī)的數(shù)量；采用響應(yīng)比作業(yè)調(diào)度算法，為了計(jì)算響應(yīng)比，還需要有作業(yè)的估計(jì)執(zhí)行時(shí)間、作業(yè)在系統(tǒng)中的等待時(shí)間；另外，指向下一個(gè)作業(yè)控制塊的指針必不可少。 實(shí)驗(yàn)中，作業(yè)控制塊及隊(duì)列的數(shù)據(jù)結(jié)構(gòu)定義如下：typedef struct jcb char name4; /作業(yè)名int length; /作業(yè)長(zhǎng)度，所需主存大小int printer; /作業(yè)執(zhí)行所需打印機(jī)的數(shù)量int tape; /作業(yè)所需磁帶機(jī)的數(shù)量int runtime; /作業(yè)估計(jì)執(zhí)行時(shí)間int waittime; 作業(yè)在系統(tǒng)中的等待時(shí)間int next; /指向下一個(gè)作業(yè)控制塊的指針JCB /作業(yè)控制塊類型定義存放作業(yè)控制塊的區(qū)域：define n 10 /假定系統(tǒng)中可容納的作業(yè)數(shù)量為nJCB jobtable10; /作業(yè)表int jobcount ; /系統(tǒng)內(nèi)現(xiàn)有作業(yè)數(shù)量 將作業(yè)控制塊組織成一個(gè)隊(duì)列，實(shí)驗(yàn)中采用靜態(tài)鏈表的方式模擬作業(yè)的后備隊(duì)列，如下圖所示。 作業(yè)隊(duì)列頭指針定義：int *head;開(kāi)始p指向作業(yè)隊(duì)列的隊(duì)首p=headq=s=-1Np沒(méi)有空？YN指針p后移； s=p；p=jobtablep.next找到滿足條件的作業(yè)（q!=-1）？系統(tǒng)可用資源是否滿足作業(yè)需求？YN結(jié)束YNq是作業(yè)隊(duì)列的第一個(gè)？計(jì)算p指向作業(yè)的響應(yīng)比xkYp是第一個(gè)滿足必要條件的作業(yè)或作業(yè)q的響應(yīng)比p的響應(yīng)比從作業(yè)隊(duì)列摘下q：jcbtablet.next= jcbtableq.next;從作業(yè)隊(duì)列摘下q：head=jcbtablehead.nextN為作業(yè)q分配資源：分配主存空間；分配磁帶機(jī)；分配打印機(jī)；并輸出作業(yè)名Yq=p；t=s;k=xk圖1 采用響應(yīng)比高者優(yōu)先算法的作業(yè)調(diào)度程序流程圖 確定作業(yè)組織方式之后，就要開(kāi)始考慮如何進(jìn)行作業(yè)調(diào)度。盡管不同的計(jì)算機(jī)系統(tǒng)可以采用不同的調(diào)度原則和調(diào)度算法，但是都必須遵循一個(gè)必要條件，即系統(tǒng)現(xiàn)有的尚未分配的資源可以滿足被選作業(yè)的資源要求。就是說(shuō)，所有的作業(yè)調(diào)度都是按照一定的算法，從滿足必要條件的作業(yè)中選擇一部分作業(yè)裝入主存儲(chǔ)器。實(shí)驗(yàn)中，主存采用可移動(dòng)的動(dòng)態(tài)分區(qū)管理方法，即只要主存空閑區(qū)總和比作業(yè)大就可以滿足作業(yè)對(duì)主存的需求；對(duì)打印機(jī)和磁帶機(jī)這兩種獨(dú)占型設(shè)備采用靜態(tài)分配法，即作業(yè)執(zhí)行前必須獲得所需資源，并且執(zhí)行完才歸還。 常用的作業(yè)調(diào)度算法有先來(lái)先服務(wù)算法、計(jì)算時(shí)間短的作業(yè)優(yōu)先算法、響應(yīng)比高者優(yōu)先算法、優(yōu)先數(shù)調(diào)度算法和均衡調(diào)度算法。實(shí)驗(yàn)中采用響應(yīng)比高者優(yōu)先算法，響應(yīng)比的定義為： 響應(yīng)比 = 作業(yè)的等待時(shí)間/作業(yè)估計(jì)執(zhí)行時(shí)間 采用響應(yīng)比高者優(yōu)先調(diào)度算法，進(jìn)行調(diào)度時(shí)必須計(jì)算出系統(tǒng)中的所有滿足必要條件作業(yè)的響應(yīng)比；從中選擇響應(yīng)比最高的一個(gè)作業(yè)裝入主存儲(chǔ)器分配資源，由于是實(shí)驗(yàn)，所以就用將作業(yè)的作業(yè)控制塊出隊(duì)，并輸出作業(yè)的作業(yè)名代替裝入主存儲(chǔ)器，同時(shí)修改系統(tǒng)的資源數(shù)量；用同樣方法選擇第二個(gè)、第三個(gè)直到不再有滿足必要條件的作業(yè)。采用響應(yīng)比高者優(yōu)先算法的作業(yè)調(diào)度程序流程圖如圖1所示。 模擬程序中，先要假設(shè)系統(tǒng)的資源情況，假設(shè)系統(tǒng)資源只有主存（memory）64MB（以KB為單位分配）、磁帶機(jī)（tape）4個(gè)和打印機(jī)（printer）2臺(tái)；然后，手工輸入某個(gè)時(shí)刻系統(tǒng)中的各個(gè)作業(yè)情況；最后進(jìn)行作業(yè)調(diào)度，并將結(jié)果輸出。五、作業(yè)題將上述實(shí)驗(yàn)中的作業(yè)調(diào)度算法改為先來(lái)先服務(wù)；短作業(yè)優(yōu)先調(diào)度算法重新完成上述工作。六、參考程序參見(jiàn)Job.c。執(zhí)行后，輸入以下數(shù)據(jù)：輸入作業(yè)名、作業(yè)大小、磁帶機(jī)數(shù)、打印機(jī)數(shù)、等待時(shí)間、估計(jì)執(zhí)行時(shí)間J1 1024 1 1 1 5輸入作業(yè)名、作業(yè)大小、磁帶機(jī)數(shù)、打印機(jī)數(shù)、等待時(shí)間、估計(jì)執(zhí)行時(shí)間J2 8000 1 1 4 10輸入作業(yè)名、作業(yè)大小、磁帶機(jī)數(shù)、打印機(jī)數(shù)、等待時(shí)間、估計(jì)執(zhí)行時(shí)間J3 2048 1 1 9 15輸入作業(yè)名、作業(yè)大小、磁帶機(jī)數(shù)、打印機(jī)數(shù)、等待時(shí)間、估計(jì)執(zhí)行時(shí)間J4 5024 2 1 15 20輸入作業(yè)名、作業(yè)大小、磁帶機(jī)數(shù)、打印機(jī)數(shù)、等待時(shí)間、估計(jì)執(zhí)行時(shí)間J5 8088 1 1 20 3輸入作業(yè)名、作業(yè)大小、磁帶機(jī)數(shù)、打印機(jī)數(shù)、等待時(shí)間、估計(jì)執(zhí)行時(shí)間0 -1 0 0 0 0運(yùn)行結(jié)果：選中作業(yè)的作業(yè)名:J5選中作業(yè)的作業(yè)名:J4 輸入以下數(shù)據(jù)：輸入作業(yè)名、作業(yè)大小、磁帶機(jī)數(shù)、打印機(jī)數(shù)、等待時(shí)間、估計(jì)執(zhí)行時(shí)間J1 12048 1 1 14 26輸入作業(yè)名、作業(yè)大小、磁帶機(jī)數(shù)、打印機(jī)數(shù)、等待時(shí)間、估計(jì)執(zhí)行時(shí)間J2 6024 1 1 9 5輸入作業(yè)名、作業(yè)大小、磁帶機(jī)數(shù)、打印機(jī)數(shù)、等待時(shí)間、估計(jì)執(zhí)行時(shí)間J3 8000 1 1 34 14輸入作業(yè)名、作業(yè)大小、磁帶機(jī)數(shù)、打印機(jī)數(shù)、等待時(shí)間、估計(jì)執(zhí)行時(shí)間J4 7048 1 1 39 31輸入作業(yè)名、作業(yè)大小、磁帶機(jī)數(shù)、打印機(jī)數(shù)、等待時(shí)間、估計(jì)執(zhí)行時(shí)間J5 1248 2 1 59 41輸入作業(yè)名、作業(yè)大小、磁帶機(jī)數(shù)、打印機(jī)數(shù)、等待時(shí)間、估計(jì)執(zhí)行時(shí)間0 -1 0 0 0 0運(yùn)行結(jié)果：選中作業(yè)的作業(yè)名:J3選中作業(yè)的作業(yè)名:J2實(shí)驗(yàn)二 單處理器系統(tǒng)的進(jìn)程調(diào)度一、實(shí)驗(yàn)?zāi)康?加深對(duì)進(jìn)程概念的理解，明確進(jìn)程和程序的區(qū)別。2深入了解系統(tǒng)如何組織進(jìn)程、創(chuàng)建進(jìn)程。3進(jìn)一步認(rèn)識(shí)如何實(shí)現(xiàn)處理器調(diào)度。二、實(shí)驗(yàn)預(yù)備知識(shí) 1進(jìn)程的概念。 2進(jìn)程的組織方式。 3進(jìn)程的創(chuàng)建。 4進(jìn)程的調(diào)度。三、實(shí)驗(yàn)內(nèi)容編寫(xiě)程序完成單處理機(jī)系統(tǒng)中的進(jìn)程調(diào)度，要求采用時(shí)間片輪轉(zhuǎn)調(diào)度算法。實(shí)驗(yàn)具體包括：首先確定進(jìn)程控制塊的內(nèi)容，進(jìn)程控制塊的組成方式；然后完成進(jìn)程創(chuàng)建原語(yǔ)和進(jìn)程調(diào)度原語(yǔ)；最后編寫(xiě)主函數(shù)對(duì)所做工作進(jìn)行測(cè)試。四、提示與講解 這個(gè)實(shí)驗(yàn)主要考慮三個(gè)問(wèn)題：如何組織進(jìn)程、如何創(chuàng)建進(jìn)程和如何實(shí)現(xiàn)處理器調(diào)度。 考慮如何組織進(jìn)程，首先就要設(shè)定進(jìn)程控制塊的內(nèi)容。進(jìn)程控制塊PCB記錄各個(gè)進(jìn)程執(zhí)行時(shí)的情況。不同的操作系統(tǒng)，進(jìn)程控制塊記錄的信息內(nèi)容不一樣。操作系統(tǒng)功能越強(qiáng)，軟件也越龐大，進(jìn)程控制塊記錄的內(nèi)容也就越多。這里的實(shí)驗(yàn)只使用了必不可少的信息。一般操作系統(tǒng)中，無(wú)論進(jìn)行控制塊中信息量多少，信息都可以大致分為以下四類： 標(biāo)識(shí)信息 每個(gè)進(jìn)程都要有一個(gè)惟一的標(biāo)識(shí)符，用來(lái)標(biāo)識(shí)進(jìn)程的存在和區(qū)別于其他進(jìn)程。這個(gè)標(biāo)識(shí)符是必不可少的，可以用符號(hào)或編號(hào)實(shí)現(xiàn)，它必須是操作系統(tǒng)分配的。在后面給出的參考程序中，采用編號(hào)方式，也就是為每個(gè)進(jìn)程依次分配一個(gè)不相同的正整數(shù)。 說(shuō)明信息 用于記錄進(jìn)程的基本情況，例如進(jìn)程的狀態(tài)、等待原因、進(jìn)程程序存放位置、進(jìn)程數(shù)據(jù)存放位置等等。實(shí)驗(yàn)中，因?yàn)檫M(jìn)程沒(méi)有數(shù)據(jù)和程序，僅使用進(jìn)程控制塊模擬進(jìn)程，所以這部分內(nèi)容僅包括進(jìn)程狀態(tài)。 現(xiàn)場(chǎng)信息 現(xiàn)場(chǎng)信息記錄各個(gè)寄存器的內(nèi)容。當(dāng)進(jìn)程由于某種原因讓出處理器，需要將現(xiàn)場(chǎng)信息記錄在進(jìn)程控制塊中，當(dāng)進(jìn)行進(jìn)程調(diào)度時(shí)，從選中進(jìn)程的進(jìn)程控制塊中讀取現(xiàn)場(chǎng)信息進(jìn)行現(xiàn)場(chǎng)恢復(fù)?，F(xiàn)場(chǎng)信息就是處理器的相關(guān)寄存器內(nèi)容，包跨通用寄存器、程序計(jì)數(shù)器和程序狀態(tài)字寄存器等。在實(shí)驗(yàn)中，可選取幾個(gè)寄存器作為代表。用大寫(xiě)的全局變量AX、BX、CX、DX模擬通用寄存器、大寫(xiě)的全局變量PC模擬程序計(jì)數(shù)器、大寫(xiě)的全局變量PSW模擬程序狀態(tài)字寄存器。 管理信息管理信息記錄進(jìn)程管理和調(diào)度的信息。例如進(jìn)程優(yōu)先數(shù)、進(jìn)程隊(duì)列指針等。實(shí)驗(yàn)中，僅包括隊(duì)列指針。因此可將進(jìn)程控制塊結(jié)構(gòu)定義如下：struct pcb int name; /進(jìn)程標(biāo)識(shí)符 int status; /進(jìn)程狀態(tài) int ax,bx,cx,dx; /進(jìn)程現(xiàn)場(chǎng)信息，通用寄存器內(nèi)容 int pc; /進(jìn)程現(xiàn)場(chǎng)信息，程序計(jì)數(shù)器內(nèi)容 int psw; /進(jìn)程現(xiàn)場(chǎng)信息，程序狀態(tài)字寄存器內(nèi)容 int next; /下一個(gè)京城控制塊的位置 確定進(jìn)程控制塊內(nèi)容后，要考慮的就是如何將進(jìn)程控制塊組織在一起。多道程序設(shè)計(jì)系統(tǒng)中，往往同時(shí)創(chuàng)建多個(gè)進(jìn)程。在單個(gè)處理器的情況下，每次只能有一個(gè)進(jìn)程處于運(yùn)行態(tài)，其他的進(jìn)程處于就緒狀態(tài)或等待狀態(tài)。為了便于管理，通常把處于相同狀態(tài)的進(jìn)程的進(jìn)程控制塊鏈接在一起。單處理器系統(tǒng)中，正在運(yùn)行的進(jìn)程只有一個(gè)。因此，單處理器系統(tǒng)中進(jìn)程控制塊分成一個(gè)正在運(yùn)行進(jìn)程的進(jìn)程控制塊、就緒進(jìn)程的進(jìn)程控制塊組織成的就緒隊(duì)列和等待進(jìn)程的進(jìn)程控制塊組成的等待隊(duì)列。由于實(shí)驗(yàn)?zāi)M的是進(jìn)程調(diào)度，沒(méi)有對(duì)等待隊(duì)列的操作，所以實(shí)驗(yàn)中只有一個(gè)指向正在運(yùn)行進(jìn)程的進(jìn)程控制塊指針和一個(gè)就緒進(jìn)程控制塊隊(duì)列指。操作系統(tǒng)的實(shí)現(xiàn)中，系統(tǒng)往往在主存中劃分出一個(gè)連續(xù)的專門(mén)區(qū)域存放系統(tǒng)的進(jìn)程控制塊，實(shí)驗(yàn)中應(yīng)該用數(shù)組模擬這個(gè)專門(mén)的進(jìn)程控制塊區(qū)域，定義如下：#define n 10 /假定系統(tǒng)允許進(jìn)程個(gè)數(shù)為10struct pcb pcbarean; /模擬進(jìn)程控制塊區(qū)域的數(shù)組這樣，進(jìn)程控制塊的鏈表實(shí)際上是數(shù)據(jù)結(jié)構(gòu)中使用的靜態(tài)鏈表。進(jìn)程控制塊的鏈接方式可以采用單向和雙向鏈表，實(shí)驗(yàn)中，進(jìn)程控制塊隊(duì)列采用單向不循環(huán)靜態(tài)鏈表。為了管理空閑進(jìn)程控制塊，還應(yīng)該將將空閑控制塊鏈接成一個(gè)隊(duì)列。實(shí)驗(yàn)采用時(shí)間片輪轉(zhuǎn)調(diào)度算法，這種算法是將進(jìn)程控制塊按照進(jìn)入就緒隊(duì)列的先后次序排成隊(duì)列。關(guān)于就緒隊(duì)列的操作就是從隊(duì)頭摘下一個(gè)進(jìn)程控制塊和從隊(duì)尾掛入一個(gè)進(jìn)程控制塊。因此為就緒隊(duì)列定義兩個(gè)指針，一個(gè)頭指針，指向就緒隊(duì)列的第一個(gè)進(jìn)程控制塊；一個(gè)尾指針，指向就緒隊(duì)列的最后一個(gè)進(jìn)程控制塊。實(shí)驗(yàn)中指向運(yùn)行進(jìn)程的進(jìn)程控制塊指針、就緒隊(duì)列指針和空閑進(jìn)程控制塊隊(duì)列指針定義如下：int run; /定義指向正在運(yùn)行進(jìn)程的進(jìn)程控制塊的指針struct int head; int tail;ready; /定義指向就緒隊(duì)列的頭指針head和尾指針tailint pfree;/定義指向空閑進(jìn)程控制塊隊(duì)列的指針以上是如何組織進(jìn)程，下面考慮如何創(chuàng)建進(jìn)程。進(jìn)程創(chuàng)建是一個(gè)原語(yǔ)，因此在實(shí)驗(yàn)中應(yīng)該用一個(gè)函數(shù)實(shí)現(xiàn)，進(jìn)程創(chuàng)建的過(guò)程應(yīng)該包括： （1）申請(qǐng)進(jìn)程控制塊：進(jìn)程控制塊的數(shù)量是有限的，如果沒(méi)有空閑進(jìn)程控制塊，則進(jìn)程不能創(chuàng)建，如果申請(qǐng)成功才可以執(zhí)行第二步；（2）申請(qǐng)資源：除了進(jìn)程控制塊外，還需要有必要的資源才能創(chuàng)建進(jìn)程，如果申請(qǐng)資源不成功，則不能創(chuàng)建進(jìn)程，并且歸還已申請(qǐng)的進(jìn)程控制塊；如果申請(qǐng)成功，則執(zhí)行第三步，實(shí)驗(yàn)無(wú)法申請(qǐng)資源，故模擬程序忽略了申請(qǐng)資源這一步；（3）填寫(xiě)進(jìn)程控制塊：將該進(jìn)程信息寫(xiě)入進(jìn)程控制塊內(nèi)，實(shí)驗(yàn)中只有進(jìn)程標(biāo)識(shí)符、進(jìn)程狀態(tài)可以填寫(xiě)，每個(gè)進(jìn)程現(xiàn)場(chǎng)信息中的寄存器內(nèi)容由于沒(méi)有具體數(shù)據(jù)而使用進(jìn)程（模擬進(jìn)程創(chuàng)建時(shí)，需輸入進(jìn)程標(biāo)識(shí)符字，進(jìn)程標(biāo)識(shí)符本應(yīng)系統(tǒng)建立，并且是惟一的，輸入時(shí)注意不要沖突），剛剛創(chuàng)建的進(jìn)程應(yīng)該為就緒態(tài)，然后轉(zhuǎn)去執(zhí)行第四步；（4）掛入就緒隊(duì)列：如果原來(lái)就緒隊(duì)列不為空，則將該進(jìn)程控制塊掛入就緒隊(duì)列尾部，并修改就緒隊(duì)列尾部指針；如果原來(lái)就緒隊(duì)列為空，則將就緒隊(duì)列的頭指針、尾指針均指向該進(jìn)程控制塊，進(jìn)程創(chuàng)建完成。進(jìn)程創(chuàng)建流程圖如圖2所示。開(kāi)始Y空閑進(jìn)程控制塊隊(duì)列為空？N取空閑進(jìn)程控制塊隊(duì)列的第一個(gè)i=pfreepfree后移：Pfree=pcbareapfree.next創(chuàng)建進(jìn)程失敗填寫(xiě)該進(jìn)程控制塊內(nèi)容：=name;pcbareai.status=aready;初始化進(jìn)程控制塊內(nèi)現(xiàn)場(chǎng)信息；就緒隊(duì)列為空？N掛入就緒隊(duì)列：pcbareaready.tail.next=i;ready.tail=i;pcbareaready.tail.next= -1;掛入就緒隊(duì)列：ready.head=i;ready.tail=i;pcbareaready.tail.next= -1;結(jié)束圖2 進(jìn)程創(chuàng)建流程圖多道程序設(shè)計(jì)的系統(tǒng)中，處于就緒態(tài)的進(jìn)程往往是多個(gè)，它們都要求占用處理器，可是單處理器系統(tǒng)的處理器只有一個(gè)，進(jìn)程調(diào)度就是解決這個(gè)處理器競(jìng)爭(zhēng)問(wèn)題的。進(jìn)程調(diào)度的任務(wù)就是按照某種算法從就緒隊(duì)列中選擇一個(gè)進(jìn)程，讓它占有處理器。因此進(jìn)程調(diào)度程序就應(yīng)該包括兩部分，一部分是在進(jìn)程就緒隊(duì)列中選擇一個(gè)進(jìn)程，并將其進(jìn)程控制塊從進(jìn)程就緒隊(duì)列中摘下來(lái)，另一部分工作就是分配處理器給選中的進(jìn)程，也就是將指向正在運(yùn)行進(jìn)程的進(jìn)程控制塊指針指向該進(jìn)程的進(jìn)程控制塊，并將該進(jìn)程的進(jìn)程控制塊信息寫(xiě)入處理器的各個(gè)寄存器中。實(shí)驗(yàn)中采用時(shí)間片輪轉(zhuǎn)調(diào)度算法。時(shí)間片輪轉(zhuǎn)調(diào)度算法讓就緒進(jìn)程按就緒的先后次序排成隊(duì)列，每次總是選擇就緒隊(duì)列中的第一個(gè)進(jìn)程占有處理器，但是規(guī)定只能使用一個(gè)“時(shí)間片”。時(shí)間片就是規(guī)定進(jìn)程一次使用處理器的最長(zhǎng)時(shí)間。實(shí)驗(yàn)中采用每個(gè)進(jìn)程都使用相同的不變時(shí)間片。采用時(shí)間片輪轉(zhuǎn)調(diào)度算法的進(jìn)程調(diào)度流程圖如圖3所示。開(kāi)始Y就緒隊(duì)列為空？N就緒隊(duì)列頭指針賦給i，i =ready.head就緒隊(duì)列頭指針后移ready.head=pcbareaready.head.nextN就緒隊(duì)列為空？無(wú)進(jìn)程可以調(diào)度Y就緒隊(duì)列尾指針置為空，ready.tail= -1修改進(jìn)程控制塊狀態(tài)pcbareai.status=running設(shè)置相對(duì)時(shí)鐘寄存器TIME=時(shí)間片恢復(fù)該進(jìn)程現(xiàn)場(chǎng)信息：AX=ax;BX=bx;CX=cx;DX=dxPC=pc;PSW=psw修改指向運(yùn)行進(jìn)程的指針run=i 圖3 進(jìn)程調(diào)度流程圖完成上述功能后，編寫(xiě)主函數(shù)進(jìn)行測(cè)試：首先建立一個(gè)就緒隊(duì)列，手工輸入信息建立幾個(gè)進(jìn)程；然后進(jìn)行進(jìn)程調(diào)度；最后將指向正在運(yùn)行進(jìn)程的指針指向的進(jìn)程控制塊的內(nèi)容輸出，察看結(jié)果。五、作業(yè)題編程實(shí)現(xiàn)采用先進(jìn)先出；優(yōu)先數(shù)；最短作業(yè)優(yōu)先調(diào)度算法的進(jìn)程調(diào)度。六、參考程序 參見(jiàn)Process.c。執(zhí)行后，輸入以下數(shù)據(jù)：輸入進(jìn)程編號(hào)(避免編號(hào)的沖突，以負(fù)數(shù)輸入結(jié)束，最多可以創(chuàng)建10個(gè)進(jìn)程)：12-1運(yùn)行結(jié)果：進(jìn)程標(biāo)識(shí)符 進(jìn)程狀態(tài) 寄存器內(nèi)容：ax bx cx dx pc psw: 1 1 1 1 1 1 1 1實(shí)驗(yàn)三 動(dòng)態(tài)分區(qū)存儲(chǔ)管理方式的主存分配回收一、實(shí)驗(yàn)?zāi)康纳钊肓私鈩?dòng)態(tài)分區(qū)存儲(chǔ)管理方式主存分配回收的實(shí)現(xiàn)。二、實(shí)驗(yàn)預(yù)備知識(shí)存儲(chǔ)管理中動(dòng)態(tài)分區(qū)的管理方式。三、實(shí)驗(yàn)內(nèi)容編寫(xiě)程序完成動(dòng)態(tài)分區(qū)存儲(chǔ)管理方式的主存分配回收的實(shí)現(xiàn)。實(shí)驗(yàn)具體包括：首先確定主存空間分配表；然后采用最優(yōu)適應(yīng)算法完成主存空間的分配和回收；最后編寫(xiě)主函數(shù)對(duì)所做工作進(jìn)行測(cè)試。四、提示與講解 動(dòng)態(tài)分區(qū)管理方式預(yù)先不將主存劃分成幾個(gè)區(qū)域，而把主存除操作系統(tǒng)占用區(qū)域外的空間看作一個(gè)大的空閑區(qū)。當(dāng)作業(yè)要求裝入主存時(shí)，根據(jù)作業(yè)需要主存空間的大小查詢主存內(nèi)各個(gè)空閑區(qū)，當(dāng)從主存空間中找到一個(gè)大于或等于該作業(yè)大小的主存空閑區(qū)時(shí)，選擇其中一個(gè)空閑區(qū)，按作業(yè)需求量劃出一個(gè)分區(qū)裝入該作業(yè)。作業(yè)執(zhí)行完后，它所占的主存分區(qū)被收回成為一個(gè)空閑區(qū)。如果該空閑區(qū)的相鄰分區(qū)也是空閑區(qū)，則需要將相鄰空閑區(qū)合并成一個(gè)空閑區(qū)。 實(shí)現(xiàn)動(dòng)態(tài)分區(qū)的分配和回收，主要考慮的問(wèn)題有三個(gè)：第一。設(shè)計(jì)記錄主存使用情況的數(shù)據(jù)表格，用來(lái)記錄空閑區(qū)和作業(yè)占用的區(qū)域；第二，在設(shè)計(jì)的數(shù)據(jù)表格基礎(chǔ)上設(shè)計(jì)主存分配算法；第三，在設(shè)計(jì)的數(shù)據(jù) 表格基礎(chǔ)上設(shè)計(jì)主存回收算法。 首先，考慮第一個(gè)問(wèn)題：設(shè)計(jì)記錄主存使用情況的數(shù)據(jù)表格，用來(lái)記錄空閑區(qū)和作業(yè)占用的區(qū)域。由于動(dòng)態(tài)分區(qū)的大小是由作業(yè)需求量決定的，故分區(qū)的長(zhǎng)度是預(yù)先不固定的，且分區(qū)的個(gè)數(shù)也隨主存分配和回收變動(dòng)。總之。所有分區(qū)情況隨時(shí)可能發(fā)生變化，數(shù)據(jù)表格的設(shè)計(jì)必須和這個(gè)特點(diǎn)相適應(yīng)。由于分區(qū)長(zhǎng)度不同，因此設(shè)計(jì)的表格應(yīng)該包括分區(qū)在主存中的起始地址和長(zhǎng)度。由于分配時(shí)空閑區(qū)有時(shí)會(huì)變成兩個(gè)分區(qū)：空閑區(qū)和已分分區(qū)，回收主存分區(qū)時(shí)，可能會(huì)合并空閑分區(qū)，這樣如果整個(gè)主存采用一張表格記錄已分分區(qū)和空閑區(qū)，就會(huì)使表格操作繁瑣。主存分配時(shí)查找空閑區(qū)進(jìn)行分配，然后填寫(xiě)已分配區(qū)表，主要操作在空閑區(qū)；某個(gè)作業(yè)執(zhí)行完后，將該分區(qū)變成空閑區(qū)，并將其與相鄰的空閑區(qū)合并，主要操作也在空閑區(qū)。由此可見(jiàn)，主存的分配和回收主要是對(duì)空閑區(qū)的操作，這樣為了便于對(duì)主存空間的分配和回收，就建立兩張分區(qū)表記錄主存使用情況，一張表格記錄作業(yè)占用分區(qū)的“已分配區(qū)表”；一張是記錄空閑區(qū)的“空閑區(qū)表”。這兩張表的實(shí)現(xiàn)方法一般有兩種，一種是鏈表形式，一種是順序表形式。在實(shí)驗(yàn)中，采用順序表形式，用數(shù)組模擬。由于順序表的長(zhǎng)度必須提前固定，所以無(wú)論是“已分配區(qū)表”還是“空閑區(qū)表”都必須事先確定長(zhǎng)度。它們的長(zhǎng)度必須是系統(tǒng)可能的最大項(xiàng)數(shù)，系統(tǒng)運(yùn)行過(guò)程中才不會(huì)出錯(cuò)。因而在多數(shù)情況下，無(wú)論是“已分配區(qū)表”，還是“空閑區(qū)表”都有空閑欄目。已分配區(qū)表中除了分區(qū)起始地址、長(zhǎng)度外，也至少還要有一項(xiàng)“標(biāo)志”，如果是空閑欄目，內(nèi)容為空，如果為某個(gè)作業(yè)占用分區(qū)的登記項(xiàng)，內(nèi)容為該作業(yè)的作業(yè)名；空閑區(qū)表除了分區(qū)起始地址,長(zhǎng)度外，也要有一項(xiàng)“標(biāo)志”，如果是空閑欄目，內(nèi)容為空，如果為某個(gè)空閑區(qū)的登記項(xiàng)，內(nèi)容“未分配”，在實(shí)際系統(tǒng)中,這兩表格的內(nèi)容可能還要多，實(shí)際中僅僅使用上述必須的數(shù)據(jù)。為此，“已分配區(qū)表”和“空閑區(qū)表”在實(shí)驗(yàn)中有如下的結(jié)構(gòu)定義。 已分配區(qū)表的定義：#define n 10 /假定系統(tǒng)允許的最大作業(yè)數(shù)量為nstruct float address; /已分分區(qū)起始地址 float length; /已分分區(qū)長(zhǎng)度,單位為字節(jié) int flag; /已分配區(qū)表登記欄標(biāo)志.0表示空欄目,實(shí)驗(yàn)中只支持一個(gè)字符的作業(yè)名used_tablen; /已分配區(qū)表空區(qū)表的定義：#define m 10 struct float address; /空閑區(qū)起始地址 float length; /空區(qū)長(zhǎng)度,單位為字節(jié) int flag; /空閑區(qū)表登記欄標(biāo)志.0表示空欄目,用1表示未分配 free_tablem; /空閑區(qū)表其中分區(qū)起始地址和長(zhǎng)度數(shù)值太大，超出了整型表達(dá)范圍，所以采用float類型。 然后，就要考慮如何在設(shè)計(jì)的數(shù)據(jù)表格上進(jìn)行主存的分配。當(dāng)要裝入一個(gè)作業(yè)時(shí)，從空閑區(qū)表中查找標(biāo)志為“未分配”的空閑區(qū)，從中找出一個(gè)能容納該作業(yè)的空閑區(qū)。如果找到的空閑正好等于該作業(yè)的長(zhǎng)度，則把該分區(qū)全部分配給作業(yè)。這時(shí)應(yīng)該把該空閑區(qū)登記欄中的標(biāo)志改為空，同時(shí)在已分配區(qū)表中找到一個(gè)標(biāo)志為空的欄目登記新裝入作業(yè)所占用分區(qū)的起始地址，長(zhǎng)度和作業(yè)名。如果找到的空閑區(qū)大于作業(yè)長(zhǎng)度，則把空閑區(qū)的長(zhǎng)度，且把空閑區(qū)分成兩部分，一部分用來(lái)裝入作業(yè)，另外一部分仍為空閑區(qū)，這時(shí)只要修改原空閑區(qū)的長(zhǎng)度，且把新裝入的作業(yè)登記到已分配去表中。 實(shí)驗(yàn)中主存分配算法采用“最優(yōu)適應(yīng)”算法。最優(yōu)適應(yīng)算法是按作業(yè)要求挑選一個(gè)能滿足作業(yè)要求的最小空閑區(qū)，這樣保證可以不去分割一個(gè)大的區(qū)域，使裝入大作業(yè)時(shí)比較容易得到滿足，但是最優(yōu)適應(yīng)算法容易出現(xiàn)找到的一個(gè)分區(qū)可能只比作業(yè)所要求的長(zhǎng)度略大一點(diǎn)的情況，這時(shí)，空閑區(qū)分割后剩下的空閑區(qū)就很小，這種很小的空閑區(qū)往往就無(wú)法使用，影響了主存的使用。為了一定程度上解決這個(gè)問(wèn)題，如果空閑區(qū)的打下比作業(yè)要求的長(zhǎng)度略大一點(diǎn)，不再將空閑區(qū)分成已分區(qū)和空閑分區(qū)兩部分，而是將整個(gè)空閑區(qū)分配給作業(yè)。在實(shí)現(xiàn)最優(yōu)算法時(shí)，可把空閑區(qū)按長(zhǎng)度以遞增的方式登記在空閑去表中。分配時(shí)順序查找空閑表,查找到的第一個(gè)空閑區(qū)就是滿足作業(yè)要求的最小分區(qū)。這樣查找速度快，但是為使空閑區(qū)按長(zhǎng)度以遞增順序登記在空閑區(qū)表中，就必須在分配回收時(shí)進(jìn)行空閑區(qū)表的調(diào)整，空閑區(qū)表調(diào)整時(shí)移動(dòng)表目的代價(jià)要高于查詢整張表的代價(jià)，所以實(shí)驗(yàn)中不采用空閑區(qū)有序登記在空閑表中的方法。動(dòng)態(tài)分區(qū)方式的主存分配流程如圖4所示。作業(yè)J申請(qǐng)xk大小的主存空間i=0；k=-1Ni是空閑區(qū)表中一欄（i=m）YY是否找到滿足需求的分區(qū)k？第i欄標(biāo)志為“未分配”且滿足作業(yè)需求xk？NN第k欄長(zhǎng)度-作業(yè)需求=minsize?YN主存分配失敗結(jié)束切割空閑區(qū)：第k欄長(zhǎng)度減去xkad=第k欄起始地址-第k欄長(zhǎng)度分配整個(gè)分區(qū)：第k欄狀態(tài)為“空”ad=第k欄起始地址；xk=第k欄長(zhǎng)度第i欄空閑區(qū)為第一個(gè)滿足需求的或第i欄空閑區(qū)長(zhǎng)度小于第k欄空閑區(qū)長(zhǎng)度？Ni=0k=i第i欄是已分配區(qū)表中一欄且第i欄狀態(tài)不為空？i=i+1i=i+1YNYN第i欄是為已分配表中一欄？第i欄是為已分配表中一欄？YN填寫(xiě)已分配區(qū)表第j欄起始地址=ad；第j欄長(zhǎng)度=xk；第j欄狀態(tài)=作業(yè)名J空閑區(qū)表第k欄長(zhǎng)度加xk空閑區(qū)表狀態(tài)未分配已分配區(qū)表長(zhǎng)度不足，分配失敗結(jié)束 圖4 動(dòng)態(tài)分區(qū)最優(yōu)分配算法流程圖 最后是動(dòng)態(tài)分區(qū)方式下的主存回收問(wèn)題。 動(dòng)態(tài)分區(qū)方式下回收主存空間時(shí)，應(yīng)該檢查是否有歸還區(qū)相鄰的空閑區(qū)。若有，則應(yīng)合并成一個(gè)空閑區(qū)。一個(gè)歸還區(qū)可能有上鄰空閑區(qū)，也可能有下鄰空閑區(qū)，或者既有上鄰空閑區(qū)又有下鄰空閑區(qū)，或者既無(wú)上鄰空閑區(qū)也無(wú)下鄰空閑區(qū)。在實(shí)現(xiàn)回收時(shí)，首先將作業(yè)歸還的區(qū)域在已分配表中找到，將該欄目的狀態(tài)變?yōu)椤翱铡?，然后檢查空閑區(qū)表中標(biāo)志為“未分配”的欄目，查找是否有相鄰空閑區(qū)；最后，合并空閑區(qū)，修改空閑區(qū)表。假定作業(yè)歸還的分區(qū)起始地址為S，長(zhǎng)度為L(zhǎng)，則：（1）歸還區(qū)有下鄰空閑區(qū) 如果S+L正好等于空閑區(qū)表中某個(gè)登記欄目（假定為第j欄）的起始地址，則表明歸還區(qū)有一個(gè)下鄰空閑區(qū)。這時(shí)只要修改第j欄登記項(xiàng)的內(nèi)容： 起始地址=S； 第j欄長(zhǎng)度=第j欄長(zhǎng)度+L； 則第j欄指示的空閑區(qū)是歸還區(qū)和下鄰空閑區(qū)合并后的大空閑區(qū)。（2）歸還區(qū)有上鄰空閑區(qū) 如果空閑區(qū)表中某個(gè)登記欄目（假定為第k欄）的“起始地址+長(zhǎng)度”正好等于S，則表明歸還區(qū)有一個(gè)上鄰空閑區(qū)。這時(shí)要修改第k欄登記項(xiàng)的內(nèi)容（起始地址不變）； 第k欄長(zhǎng)度=第k欄長(zhǎng)度+L； 于是第k欄指示的空閑區(qū)是歸還區(qū)和上鄰空閑區(qū)合并后的大空閑區(qū)。（3）歸還區(qū)既有上鄰空閑區(qū)又有下鄰空閑區(qū) 如果S+L正好等于空閑區(qū)表中某個(gè)登記欄目（假定為第j欄）的起始地址，同時(shí)還有某個(gè)登記欄目（假定為第k欄）的“起始地址+長(zhǎng)度”正好等于S，這表明歸還區(qū)既有一個(gè)上鄰空閑區(qū)又有一個(gè)下鄰空閑區(qū)。此時(shí)對(duì)空閑區(qū)表的修改如下： 第k欄長(zhǎng)度=第k欄長(zhǎng)度+第j欄長(zhǎng)度+L；（第k欄起始地址不變） 第j欄狀態(tài)=“空”;（將第j欄長(zhǎng)度登記項(xiàng)刪除） 這樣，第k欄指示的空閑區(qū)是歸還區(qū)和上、下鄰空閑區(qū)合并后的大空閑區(qū)；原來(lái)的下鄰空閑區(qū)登記項(xiàng)（第j 欄）被刪除，置為“空”。（4）歸還區(qū)既無(wú)上鄰空閑區(qū)又無(wú)下鄰空閑區(qū)如果在檢查空閑區(qū)表時(shí)，無(wú)上述三種情況出現(xiàn)，則表明歸還區(qū)既無(wú)上鄰空閑區(qū)又無(wú)下鄰空閑區(qū)。這時(shí)，應(yīng)該在空閑區(qū)表中查找一個(gè)狀態(tài)為“空”的欄目（假定查到的是第t欄），則第t欄的內(nèi)容修改如下： 第t欄起始地址=S； 第t欄長(zhǎng)度=L； 第t欄狀態(tài)=“未分配” 這樣，第t欄指示的空閑區(qū)是歸還區(qū)。 按上述方法歸還主存區(qū)域的流程如圖5所示。 由于是實(shí)驗(yàn)，沒(méi)有真正的主存要分配，所以在實(shí)驗(yàn)中，首先應(yīng)建立一張空閑表，初始狀態(tài)只有一個(gè)空閑登記項(xiàng)（假定的主存空閑區(qū)）和一張所有狀態(tài)都為“空”的已分配區(qū)表，假定主存空間110KB，操作系統(tǒng)占用10KB，其余為空閑區(qū)；然后，可以選擇進(jìn)行主存分配或主存回收，如果是分配，要求輸入作業(yè)名和所需主存空間大小，如果是回收，輸入回收作業(yè)的作業(yè)名，循環(huán)進(jìn)行主存分配和回收后，如果需要，則顯示兩張表的內(nèi)容，以檢查主存的分配和回收是否正確。五、作業(yè)題編程實(shí)現(xiàn)頁(yè)式存儲(chǔ)管理的主存分配和回收。用鏈表方式表示主存空間分配情況，完成動(dòng)態(tài)分區(qū)管理方式下的主存空間分配和回收。六、參考程序參見(jiàn)Memory.c。作業(yè)J歸還空間s=0s=s+1已分配區(qū)表第s欄狀態(tài)為作業(yè)J(s10ad=laddress&0x3ff查頁(yè)表第lnumber行N頁(yè)在主存？缺頁(yè)中斷從頁(yè)表中取得塊號(hào)pnumber合并塊號(hào)和塊內(nèi)地址形成物理地址paddress;paddress=pnumber10|ad結(jié)束 圖7 模擬地址轉(zhuǎn)換的流程圖 頁(yè)表用數(shù)組模擬，在實(shí)驗(yàn)中頁(yè)表數(shù)據(jù)結(jié)構(gòu)定義為：define n 32 /實(shí)驗(yàn)中假定的頁(yè)表長(zhǎng)度，/頁(yè)表的長(zhǎng)度實(shí)際上是由系統(tǒng)按照作業(yè)長(zhǎng)度決定的struct int lnuber; /頁(yè)號(hào) int flag; /表示該頁(yè)是否在主存，“1”表示在主存，“0”表示不在主存 int pnuber; /該頁(yè)所在主存塊的塊號(hào) int writer; /該頁(yè)是否被修改過(guò)，“1”表示修改過(guò)，“0”表示沒(méi)有修改過(guò) int dnuber; /該頁(yè)存放在磁盤(pán)上的位置，即磁盤(pán)塊號(hào)pagen; /頁(yè)表定義 缺頁(yè)處理過(guò)程簡(jiǎn)單闡述如下：（1）根據(jù)當(dāng)前執(zhí)行指令中邏輯地址的頁(yè)號(hào)查頁(yè)表，判斷該頁(yè)是否在主存儲(chǔ)器中，若該頁(yè)標(biāo)志為“0”，形成缺頁(yè)中斷。中斷裝置通過(guò)交換PSW讓操作系統(tǒng)的中斷處理程序占用處理器；（2）操作系統(tǒng)處理缺頁(yè)中斷的方法就是查主存分配表，找一個(gè)空閑主存塊；若無(wú)空閑塊，查頁(yè)表，選擇一個(gè)已在主存的頁(yè)面，把它暫時(shí)調(diào)出主存。若在執(zhí)行過(guò)程中該頁(yè)被修改過(guò)。則需將該頁(yè)信息寫(xiě)回磁盤(pán)，否則不必寫(xiě)回；（3）找出該頁(yè)的磁盤(pán)位置，啟動(dòng)磁盤(pán)讀出該頁(yè)信息，把磁盤(pán)上讀出的信息裝入第2步找到的主存塊，修改頁(yè)表中該頁(yè)的標(biāo)志為“1”；（4）由于產(chǎn)生缺頁(yè)中斷的那條指令沒(méi)有執(zhí)行完。所以頁(yè)面裝入后應(yīng)重新執(zhí)行被中斷的指令。當(dāng)重新執(zhí)行該指令時(shí)。由于要訪問(wèn)的頁(yè)面夜在主存中，所以可以正常執(zhí)行。 關(guān)于第2步的查找裝入新頁(yè)面的主存塊處理方式，不同系統(tǒng)采用的策略可能有所不同，這里采用局部置換算法，就是每個(gè)作業(yè)分得一定的主存塊，只能在分得的主存塊內(nèi)查找空閑塊，若無(wú)空閑主存塊，則從該作業(yè)中選擇一個(gè)頁(yè)面淘汰出主存。實(shí)驗(yàn)中使用局部置換算法。 使用局部算法時(shí)，存在這樣一個(gè)問(wèn)題：就是 在分配給作業(yè)主存空間時(shí)，裝入哪些頁(yè)？有的系統(tǒng)采用裝入任何一頁(yè)，當(dāng)執(zhí)行過(guò)程中需要時(shí)才將其調(diào)入。有的系統(tǒng)采用頁(yè)面預(yù)置的方法，就是估計(jì)可能某些頁(yè)面會(huì)先用到，在分配主存塊后將這些頁(yè)面裝入。實(shí)驗(yàn)中，采用第2種方法，分配主存空間時(shí)將前幾頁(yè)調(diào)入主存，假定系統(tǒng)中沒(méi)個(gè)作業(yè)分得主存塊m(m=4)，則將第 0m-1頁(yè)裝入主存。 因?yàn)槭悄M硬件工作，所以實(shí)驗(yàn)中如果訪問(wèn)的頁(yè)不在主存時(shí)，則輸出該頁(yè)頁(yè)號(hào)，表示硬件產(chǎn)生缺頁(yè)中斷，然后直接轉(zhuǎn)去缺頁(yè)中斷處理；由于采用頁(yè)面預(yù)置方法，在給定的主存塊中一定無(wú)空閑魁岸，只能淘汰已主存的一頁(yè)；沒(méi)有啟動(dòng)磁盤(pán)的工作，淘汰的頁(yè)需要寫(xiě)回磁盤(pán)時(shí)，用輸出頁(yè)號(hào)表示，調(diào)入新的一頁(yè)時(shí)，該頁(yè)在頁(yè)表中的存在標(biāo)志置為“1”，輸出頁(yè)號(hào)表示將該頁(yè)調(diào)入主存。 主存中無(wú)空閑塊時(shí)，為裝入一個(gè)頁(yè)面，必須按某種算法從已在主存的頁(yè)中選擇也頁(yè)，將它暫時(shí)調(diào)出主存，讓出 主存空間，用來(lái)存放需裝入的頁(yè)面，這個(gè)工作稱為“頁(yè)面調(diào)度”。如何選擇調(diào)出的頁(yè)是很重要的，常用的頁(yè)面調(diào)度算法有先進(jìn)先出算法、最近最少用算法和最近最不常用算法。實(shí)驗(yàn)中使用先進(jìn)先出調(diào)度算法。先進(jìn)先出算法總是選擇駐留在主存時(shí)間最長(zhǎng)的一頁(yè)調(diào)出。先進(jìn)先出算法簡(jiǎn)單，易實(shí)現(xiàn)?？梢园言谥鞔鎯?chǔ)器的頁(yè)的頁(yè)號(hào)按進(jìn)入主存的先后次序排成隊(duì)列，沒(méi)次總是調(diào)出隊(duì)首的頁(yè)，當(dāng)裝入一個(gè)新頁(yè)后，把新頁(yè)的頁(yè)號(hào)排入隊(duì)尾。實(shí)驗(yàn)中，用一個(gè)數(shù)組存放頁(yè)號(hào)的隊(duì)列。假定分配給作業(yè)的主存塊數(shù)為m，數(shù)組可有m個(gè)元素組成，p0，p1，pn；隊(duì)首指針；采用頁(yè)面預(yù)置的方法，頁(yè)號(hào)隊(duì)列的長(zhǎng)度總是m，tail等于(head+1)%m。因此可以使用一個(gè)指針，只用head即可。在裝入一個(gè)新的頁(yè)時(shí)，裝入頁(yè)和淘汰頁(yè)同時(shí)執(zhí)行，當(dāng)裝入一個(gè)新的頁(yè)時(shí)，將其頁(yè)號(hào)存入數(shù)組：淘汰頁(yè)的頁(yè)號(hào)=phead；phead=新裝入頁(yè)的頁(yè)號(hào)；head=(head+1)%m；實(shí)驗(yàn)中，采用先進(jìn)先出頁(yè)面置換算法的缺頁(yè)中斷流程如圖8所示。頁(yè)號(hào)為lnumber 輸出：* lnumber淘汰頁(yè)的頁(yè)號(hào)j=phead;phead=lnumberhead=(head+1)%m;N第j頁(yè)修改標(biāo)志=1？Y輸出：頁(yè)號(hào)j修改頁(yè)表：第j頁(yè)存在標(biāo)志改為“0”第lnumber頁(yè)存在標(biāo)志改為“1”第lnumber頁(yè)修改標(biāo)志改為“0”第lnumber頁(yè)主存塊號(hào)為第j頁(yè)原主存塊號(hào)輸出：頁(yè)號(hào)lnumber結(jié)束圖8 采用先進(jìn)先出頁(yè)面置換算法的缺頁(yè)中斷流程圖實(shí)驗(yàn)執(zhí)行一條指令時(shí)，不模擬指令的執(zhí)行，只是考慮指令執(zhí)行是否修改頁(yè)面，若修改頁(yè)面，則將該頁(yè)的頁(yè)表中修改標(biāo)志位置“1”，然后輸出轉(zhuǎn)換后的物理地址，并輸出物理地址來(lái)表示一條指令執(zhí)行完成；如果訪問(wèn)的頁(yè)不在主存時(shí)，則產(chǎn)生缺頁(yè)中斷，然后直接轉(zhuǎn)去缺頁(yè)中斷處理，最后模擬中斷返回，就是返回重新進(jìn)行地址轉(zhuǎn)換。一條指令執(zhí)行的模擬流程如圖9所示。開(kāi)始取指令中的頁(yè)號(hào)lnumber查頁(yè)表第lnumber欄缺頁(yè)中斷N第lnumber頁(yè)存在標(biāo)志=1？Y形成物理地址輸出：物理地址N指令會(huì)修改頁(yè)內(nèi)容？Y第lnumber頁(yè)修改標(biāo)志改為“1”結(jié)束圖9 一條指令執(zhí)行的模擬流程圖因?yàn)闆](méi)有實(shí)際主存，所以在模擬程序中首先手工輸入頁(yè)表信息，創(chuàng)建該作業(yè)的頁(yè)表；然后循環(huán)執(zhí)行假定的指令，觀察地址轉(zhuǎn)換情況。五、作業(yè)題采用LRU頁(yè)面調(diào)度算法編程實(shí)現(xiàn)上述虛擬頁(yè)式存儲(chǔ)管理的地址轉(zhuǎn)換。六、參考程序 參見(jiàn)VM.c。將VM.c編譯連接成可執(zhí)行文件，然后運(yùn)行，操作如下：輸入頁(yè)表的信息,創(chuàng)建頁(yè)表(若頁(yè)號(hào)為-1,則結(jié)束輸入)輸入頁(yè)號(hào)和輔存地址:1 11輸入頁(yè)號(hào)和輔存地址:2 22輸入頁(yè)號(hào)和輔存地址:3 33輸入頁(yè)號(hào)和輔存地址:4 44輸入頁(yè)號(hào)和輔存地址:-1 0輸入主存塊號(hào),主存塊數(shù)要小于4,(以-1結(jié)束):100 101 -1輸入指令性質(zhì)(1-修改,0-不需要,其他-結(jié)束程序運(yùn)行)和邏輯地址1 a邏輯地址是:a 對(duì)應(yīng)物理地址是:1900a輸入指令性質(zhì)(1-修改,0-不需要,其他-結(jié)束程序運(yùn)行)和邏輯地址1 1000不存在該頁(yè)輸入指令性質(zhì)(1-修改,0-不需要,其他-結(jié)束程序運(yùn)行)和邏輯地址1 caa發(fā)生缺頁(yè)中斷*3將頁(yè)0寫(xiě)回磁盤(pán)第11塊淘汰主存塊100中的頁(yè) 0,從磁盤(pán)第44塊中調(diào)入 3邏輯地址是:caa 對(duì)應(yīng)物理地址是:190aa分析舉例： 邏輯地址：a 轉(zhuǎn)換為二進(jìn)制：0000 0000 0000 1010 頁(yè)號(hào)為：0 頁(yè)內(nèi)地址：00 0000 1010 查找頁(yè)表 找到對(duì)應(yīng)的塊號(hào)：100 轉(zhuǎn)換為二進(jìn)制：1100100 物理地址：1 1001 0000 0000 1010 16進(jìn)制輸出：1900a實(shí)驗(yàn)五 磁盤(pán)文件