【正文】 。盤塊的塊號從0編起，0，1，2，3……，127。因為是實驗，不使用真正的磁盤，所以實驗中用一個文件模擬一個小磁盤。某個文件的起始盤塊號為3,在該文件盤塊號依次為113。磁盤有多少塊，文件分配表就有多少項，若某文件的一個磁盤塊號i，則這個文件的下一個磁盤的塊號應(yīng)該記錄在文件分配表第i項。實驗只支持流式文件，采用稱為顯示鏈接的物理文件結(jié)構(gòu)，把磁盤中每一塊的指針部分提出來，組織在一起，形成文件分配表（FAT）。因此，這個實驗雖然是文件操作的模擬實現(xiàn)，但是還必須模擬一部分文件的組織結(jié)構(gòu)、目錄結(jié)構(gòu)和磁盤空間管理的實現(xiàn)。我們把文件系統(tǒng)設(shè)計的這一組功能模塊稱為“文件操作”，實驗就是要模擬實現(xiàn)一些文件操作。最后編寫主函數(shù)對所做工作進行測試。二、實驗預(yù)備知識 文件的操作； 文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)； 磁盤空間的管理； 磁盤目錄結(jié)構(gòu)。六、參考程序 。開始取指令中的頁號lnumber查頁表第lnumber欄缺頁中斷N第lnumber頁存在標志==1？Y形成物理地址輸出：物理地址N指令會修改頁內(nèi)容？Y第lnumber頁修改標志改為“1”結(jié)束圖9 一條指令執(zhí)行的模擬流程圖因為沒有實際主存，所以在模擬程序中首先手工輸入頁表信息，創(chuàng)建該作業(yè)的頁表；然后循環(huán)執(zhí)行假定的指令，觀察地址轉(zhuǎn)換情況。N第j頁修改標志==1？Y輸出：頁號j修改頁表：第j頁存在標志改為“0”第lnumber頁存在標志改為“1”第lnumber頁修改標志改為“0”第lnumber頁主存塊號為第j頁原主存塊號輸出：頁號lnumber結(jié)束圖8 采用先進先出頁面置換算法的缺頁中斷流程圖實驗執(zhí)行一條指令時，不模擬指令的執(zhí)行，只是考慮指令執(zhí)行是否修改頁面，若修改頁面，則將該頁的頁表中修改標志位置“1”，然后輸出轉(zhuǎn)換后的物理地址，并輸出物理地址來表示一條指令執(zhí)行完成；如果訪問的頁不在主存時，則產(chǎn)生缺頁中斷，然后直接轉(zhuǎn)去缺頁中斷處理，最后模擬中斷返回，就是返回重新進行地址轉(zhuǎn)換。頁號為lnumber 輸出：* lnumber淘汰頁的頁號j=p[head]。因此可以使用一個指針，只用head即可。實驗中，用一個數(shù)組存放頁號的隊列。先進先出算法簡單，易實現(xiàn)。實驗中使用先進先出調(diào)度算法。 主存中無空閑塊時，為裝入一個頁面，必須按某種算法從已在主存的頁中選擇也頁，將它暫時調(diào)出主存，讓出 主存空間，用來存放需裝入的頁面，這個工作稱為“頁面調(diào)度”。實驗中，采用第2種方法，分配主存空間時將前幾頁調(diào)入主存，假定系統(tǒng)中沒個作業(yè)分得主存塊m(m=4)，則將第 0~m1頁裝入主存。 使用局部算法時，存在這樣一個問題：就是 在分配給作業(yè)主存空間時，裝入哪些頁？有的系統(tǒng)采用裝入任何一頁，當執(zhí)行過程中需要時才將其調(diào)入。 關(guān)于第2步的查找裝入新頁面的主存塊處理方式，不同系統(tǒng)采用的策略可能有所不同，這里采用局部置換算法，就是每個作業(yè)分得一定的主存塊，只能在分得的主存塊內(nèi)查找空閑塊，若無空閑主存塊，則從該作業(yè)中選擇一個頁面淘汰出主存。當重新執(zhí)行該指令時。則需將該頁信息寫回磁盤，否則不必寫回；（3）找出該頁的磁盤位置，啟動磁盤讀出該頁信息，把磁盤上讀出的信息裝入第2步找到的主存塊，修改頁表中該頁的標志為“1”；（4）由于產(chǎn)生缺頁中斷的那條指令沒有執(zhí)行完。中斷裝置通過交換PSW讓操作系統(tǒng)的中斷處理程序占用處理器；（2）操作系統(tǒng)處理缺頁中斷的方法就是查主存分配表，找一個空閑主存塊；若無空閑塊，查頁表，選擇一個已在主存的頁面，把它暫時調(diào)出主存。 //該頁存放在磁盤上的位置，即磁盤塊號}page[n]。 //該頁所在主存塊的塊號 int writer。 //頁號 int flag。0x3ff查頁表第lnumber行N頁在主存？缺頁中斷從頁表中取得塊號pnumber合并塊號和塊內(nèi)地址形成物理地址paddress。這樣，在實驗中頁表格式如圖7所示。在頁式虛擬存儲管理方式中，作業(yè)信息作為副本放在磁盤上，作業(yè)執(zhí)行時僅把作業(yè)信息的部分頁面裝入主存儲器，作業(yè)執(zhí)行時若訪問的頁面在主存中，則按上述方式進行地址轉(zhuǎn)換，若訪問的頁面不在主存中，則產(chǎn)生一個“缺頁中斷”，由操作系統(tǒng)把當前所需要的頁面裝入主存儲器后，再次執(zhí)行時才可以按上述方法進行地址轉(zhuǎn)換。四、提示與講解頁式虛擬存儲管理中地址轉(zhuǎn)換過程很簡單，假定主存塊的大小為2為字節(jié)，主存大小字節(jié)和邏輯地址位，則進行地址轉(zhuǎn)換時，首先從邏輯地址中的高位中取得頁號，然后根據(jù)頁號查頁表，得到塊號，并將塊號放入物理地址的高位，最后從邏輯地址中取得低位放入物理地址的低位就得到了物理地址，過程如圖6所示。實驗具體包括：首先對給定的地址進行地址轉(zhuǎn)換工作，若發(fā)生缺頁則先進行缺頁中斷處理，然后再進行地址轉(zhuǎn)換；最后編寫主函數(shù)對所做工作進行測試。 二、實驗預(yù)備知識 頁式虛擬存儲管理地址轉(zhuǎn)換的方法； 頁式虛擬存儲的缺頁中斷處理方法。六、參考程序。五、作業(yè)題①編程實現(xiàn)頁式存儲管理的主存分配和回收。 按上述方法歸還主存區(qū)域的流程如圖5所示。（4）歸還區(qū)既無上鄰空閑區(qū)又無下鄰空閑區(qū)如果在檢查空閑區(qū)表時，無上述三種情況出現(xiàn)，則表明歸還區(qū)既無上鄰空閑區(qū)又無下鄰空閑區(qū)。此時對空閑區(qū)表的修改如下： 第k欄長度=第k欄長度+第j欄長度+L；（第k欄起始地址不變） 第j欄狀態(tài)=“空”。這時要修改第k欄登記項的內(nèi)容（起始地址不變）； 第k欄長度=第k欄長度+L； 于是第k欄指示的空閑區(qū)是歸還區(qū)和上鄰空閑區(qū)合并后的大空閑區(qū)。這時只要修改第j欄登記項的內(nèi)容： 起始地址=S； 第j欄長度=第j欄長度+L； 則第j欄指示的空閑區(qū)是歸還區(qū)和下鄰空閑區(qū)合并后的大空閑區(qū)。在實現(xiàn)回收時，首先將作業(yè)歸還的區(qū)域在已分配表中找到，將該欄目的狀態(tài)變?yōu)椤翱铡?，然后檢查空閑區(qū)表中標志為“未分配”的欄目，查找是否有相鄰空閑區(qū)；最后，合并空閑區(qū)，修改空閑區(qū)表。若有，則應(yīng)合并成一個空閑區(qū)。作業(yè)J申請xk大小的主存空間i=0；k=1Ni是空閑區(qū)表中一欄（i=m）YY是否找到滿足需求的分區(qū)k？第i欄標志為“未分配”且滿足作業(yè)需求xk？NN第k欄長度作業(yè)需求=minsize?YN主存分配失敗結(jié)束切割空閑區(qū)：第k欄長度減去xkad=第k欄起始地址第k欄長度分配整個分區(qū)：第k欄狀態(tài)為“空”ad=第k欄起始地址；xk=第k欄長度第i欄空閑區(qū)為第一個滿足需求的或第i欄空閑區(qū)長度小于第k欄空閑區(qū)長度？Ni=0k=i第i欄是已分配區(qū)表中一欄且第i欄狀態(tài)不為空？i=i+1i=i+1YNYN第i欄是為已分配表中一欄？第i欄是為已分配表中一欄？YN填寫已分配區(qū)表第j欄起始地址=ad；第j欄長度=xk；第j欄狀態(tài)=作業(yè)名J空閑區(qū)表第k欄長度加xk空閑區(qū)表狀態(tài)未分配已分配區(qū)表長度不足，分配失敗結(jié)束 圖4 動態(tài)分區(qū)最優(yōu)分配算法流程圖 最后是動態(tài)分區(qū)方式下的主存回收問題。這樣查找速度快，但是為使空閑區(qū)按長度以遞增順序登記在空閑區(qū)表中，就必須在分配回收時進行空閑區(qū)表的調(diào)整，空閑區(qū)表調(diào)整時移動表目的代價要高于查詢整張表的代價，所以實驗中不采用空閑區(qū)有序登記在空閑表中的方法。在實現(xiàn)最優(yōu)算法時，可把空閑區(qū)按長度以遞增的方式登記在空閑去表中。最優(yōu)適應(yīng)算法是按作業(yè)要求挑選一個能滿足作業(yè)要求的最小空閑區(qū)，這樣保證可以不去分割一個大的區(qū)域，使裝入大作業(yè)時比較容易得到滿足，但是最優(yōu)適應(yīng)算法容易出現(xiàn)找到的一個分區(qū)可能只比作業(yè)所要求的長度略大一點的情況，這時，空閑區(qū)分割后剩下的空閑區(qū)就很小，這種很小的空閑區(qū)往往就無法使用，影響了主存的使用。如果找到的空閑區(qū)大于作業(yè)長度，則把空閑區(qū)的長度，且把空閑區(qū)分成兩部分，一部分用來裝入作業(yè)，另外一部分仍為空閑區(qū)，這時只要修改原空閑區(qū)的長度，且把新裝入的作業(yè)登記到已分配去表中。如果找到的空閑正好等于該作業(yè)的長度，則把該分區(qū)全部分配給作業(yè)。 然后，就要考慮如何在設(shè)計的數(shù)據(jù)表格上進行主存的分配。 //空閑區(qū)表登記欄標志.0表示空欄目,用1表示未分配} free_table[m]。 //空閑區(qū)起始地址 float length。 //已分配區(qū)表登記欄標志.0表示空欄目,實驗中只支持一個字符的作業(yè)名}used_table[n]。 //已分分區(qū)起始地址 float length。為此，“已分配區(qū)表”和“空閑區(qū)表”在實驗中有如下的結(jié)構(gòu)定義。因而在多數(shù)情況下，無論是“已分配區(qū)表”，還是“空閑區(qū)表”都有空閑欄目。由于順序表的長度必須提前固定，所以無論是“已分配區(qū)表”還是“空閑區(qū)表”都必須事先確定長度。這兩張表的實現(xiàn)方法一般有兩種，一種是鏈表形式，一種是順序表形式。主存分配時查找空閑區(qū)進行分配，然后填寫已分配區(qū)表，主要操作在空閑區(qū)；某個作業(yè)執(zhí)行完后，將該分區(qū)變成空閑區(qū)，并將其與相鄰的空閑區(qū)合并，主要操作也在空閑區(qū)。由于分區(qū)長度不同，因此設(shè)計的表格應(yīng)該包括分區(qū)在主存中的起始地址和長度?？傊?。 首先，考慮第一個問題：設(shè)計記錄主存使用情況的數(shù)據(jù)表格，用來記錄空閑區(qū)和作業(yè)占用的區(qū)域。 實現(xiàn)動態(tài)分區(qū)的分配和回收，主要考慮的問題有三個：第一。作業(yè)執(zhí)行完后，它所占的主存分區(qū)被收回成為一個空閑區(qū)。四、提示與講解 動態(tài)分區(qū)管理方式預(yù)先不將主存劃分成幾個區(qū)域，而把主存除操作系統(tǒng)占用區(qū)域外的空間看作一個大的空閑區(qū)。三、實驗內(nèi)容編寫程序完成動態(tài)分區(qū)存儲管理方式的主存分配回收的實現(xiàn)。執(zhí)行后，輸入以下數(shù)據(jù)：輸入進程編號(避免編號的沖突，以負數(shù)輸入結(jié)束，最多可以創(chuàng)建10個進程)：12…1運行結(jié)果：進程標識符 進程狀態(tài) 寄存器內(nèi)容：ax bx cx dx pc psw: 1 1 1 1 1 1 1 1實驗三 動態(tài)分區(qū)存儲管理方式的主存分配回收一、實驗?zāi)康纳钊肓私鈩討B(tài)分區(qū)存儲管理方式主存分配回收的實現(xiàn)。五、作業(yè)題編程實現(xiàn)采用①先進先出；②優(yōu)先數(shù)；③最短作業(yè)優(yōu)先調(diào)度算法的進程調(diào)度。DX=dxPC=pc。BX=bx。采用時間片輪轉(zhuǎn)調(diào)度算法的進程調(diào)度流程圖如圖3所示。時間片就是規(guī)定進程一次使用處理器的最長時間。實驗中采用時間片輪轉(zhuǎn)調(diào)度算法。進程調(diào)度的任務(wù)就是按照某種算法從就緒隊列中選擇一個進程，讓它占有處理器。pcbarea[].next= 1。掛入就緒隊列：=i。=i。pcbarea[i].status=aready。進程創(chuàng)建流程圖如圖2所示。//定義指向空閑進程控制塊隊列的指針以上是如何組織進程，下面考慮如何創(chuàng)建進程。}ready。 //定義指向正在運行進程的進程控制塊的指針struct {int head。因此為就緒隊列定義兩個指針，一個頭指針，指向就緒隊列的第一個進程控制塊；一個尾指針，指向就緒隊列的最后一個進程控制塊。實驗采用時間片輪轉(zhuǎn)調(diào)度算法，這種算法是將進程控制塊按照進入就緒隊列的先后次序排成隊列。進程控制塊的鏈接方式可以采用單向和雙向鏈表，實驗中，進程控制塊隊列采用單向不循環(huán)靜態(tài)鏈表。操作系統(tǒng)的實現(xiàn)中，系統(tǒng)往往在主存中劃分出一個連續(xù)的專門區(qū)域存放系統(tǒng)的進程控制塊，實驗中應(yīng)該用數(shù)組模擬這個專門的進程控制塊區(qū)域，定義如下：define n 10 //假定系統(tǒng)允許進程個數(shù)為10struct pcb pcbarea[n]。因此，單處理器系統(tǒng)中進程控制塊分成一個正在運行進程的進程控制塊、就緒進程的進程控制塊組織成的就緒隊列和等待進程的進程控制塊組成的等待隊列。為了便于管理，通常把處于相同狀態(tài)的進程的進程控制塊鏈接在一起。多道程序設(shè)計系統(tǒng)中，往往同時創(chuàng)建多個進程。 //進程現(xiàn)場信息，程序狀態(tài)字寄存器內(nèi)容 int next。 //進程現(xiàn)場信息，通用寄存器內(nèi)容 int pc。 //進程標識符 int status。實驗中，僅包括隊列指針。 管理信息管理信息記錄進程管理和調(diào)度的信息。用大寫的全局變量AX、BX、CX、DX模擬通用寄存器、大寫的全局變量PC模擬程序計數(shù)器、大寫的全局變量PSW模擬程序狀態(tài)字寄存器。現(xiàn)場信息就是處理器的相關(guān)寄存器內(nèi)容，包跨通用寄存器、程序計數(shù)器和程序狀態(tài)字寄存器等。 現(xiàn)場信息 現(xiàn)場信息記錄各個寄存器的內(nèi)容。實驗中，因為進程沒有數(shù)據(jù)和程序，僅使用進程控制塊模擬進程，所以這部分內(nèi)容僅包括進程狀態(tài)。216。這個標識符是必不可少的，可以用符號或編號實現(xiàn)，它必須是操作系統(tǒng)分配的。一般操作系統(tǒng)中，無論進行控制塊中信息量多少，信息都可以大致分為以下四類：216。操作系統(tǒng)功能越強，軟件也越龐大，進程控制塊記錄的內(nèi)容也就越多。進程控制塊PCB記錄各個進程執(zhí)行時的情況。四、提示與講解 這個實驗主要考慮三個問題：如何組織進程、如何創(chuàng)建進程和如何實現(xiàn)處理器調(diào)度。三、實驗內(nèi)容編寫程序完成單處理機系統(tǒng)中的進程調(diào)度，要求采用時間片輪轉(zhuǎn)調(diào)度算法。 3．進程的創(chuàng)建。二、實驗預(yù)備知識 1．進程的概念。2．深入了解系統(tǒng)如何組織進程、創(chuàng)建進程。