【正文】 pcbarea[].next=i。=i。pcbarea[].next= 1。掛入就緒隊列：=i。=i。pcbarea[].next= 1。結(jié)束圖2 進(jìn)程創(chuàng)建流程圖多道程序設(shè)計的系統(tǒng)中，處于就緒態(tài)的進(jìn)程往往是多個，它們都要求占用處理器，可是單處理器系統(tǒng)的處理器只有一個，進(jìn)程調(diào)度就是解決這個處理器競爭問題的。進(jìn)程調(diào)度的任務(wù)就是按照某種算法從就緒隊列中選擇一個進(jìn)程，讓它占有處理器。因此進(jìn)程調(diào)度程序就應(yīng)該包括兩部分，一部分是在進(jìn)程就緒隊列中選擇一個進(jìn)程，并將其進(jìn)程控制塊從進(jìn)程就緒隊列中摘下來，另一部分工作就是分配處理器給選中的進(jìn)程，也就是將指向正在運行進(jìn)程的進(jìn)程控制塊指針指向該進(jìn)程的進(jìn)程控制塊，并將該進(jìn)程的進(jìn)程控制塊信息寫入處理器的各個寄存器中。實驗中采用時間片輪轉(zhuǎn)調(diào)度算法。時間片輪轉(zhuǎn)調(diào)度算法讓就緒進(jìn)程按就緒的先后次序排成隊列，每次總是選擇就緒隊列中的第一個進(jìn)程占有處理器，但是規(guī)定只能使用一個“時間片”。時間片就是規(guī)定進(jìn)程一次使用處理器的最長時間。實驗中采用每個進(jìn)程都使用相同的不變時間片。采用時間片輪轉(zhuǎn)調(diào)度算法的進(jìn)程調(diào)度流程圖如圖3所示。開始Y就緒隊列為空？N就緒隊列頭指針賦給i，i =就緒隊列頭指針后移=pcbarea[].nextN就緒隊列為空？無進(jìn)程可以調(diào)度Y就緒隊列尾指針置為空，= 1修改進(jìn)程控制塊狀態(tài)pcbarea[i].status=running設(shè)置相對時鐘寄存器TIME=時間片恢復(fù)該進(jìn)程現(xiàn)場信息：AX=ax。BX=bx。CX=cx。DX=dxPC=pc。PSW=psw修改指向運行進(jìn)程的指針run=i 圖3 進(jìn)程調(diào)度流程圖完成上述功能后，編寫主函數(shù)進(jìn)行測試：首先建立一個就緒隊列，手工輸入信息建立幾個進(jìn)程；然后進(jìn)行進(jìn)程調(diào)度；最后將指向正在運行進(jìn)程的指針指向的進(jìn)程控制塊的內(nèi)容輸出，察看結(jié)果。五、作業(yè)題編程實現(xiàn)采用①先進(jìn)先出；②優(yōu)先數(shù)；③最短作業(yè)優(yōu)先調(diào)度算法的進(jìn)程調(diào)度。六、參考程序 。執(zhí)行后，輸入以下數(shù)據(jù)：輸入進(jìn)程編號(避免編號的沖突，以負(fù)數(shù)輸入結(jié)束，最多可以創(chuàng)建10個進(jìn)程)：12…1運行結(jié)果：進(jìn)程標(biāo)識符 進(jìn)程狀態(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ù)備知識存儲管理中動態(tài)分區(qū)的管理方式。三、實驗內(nèi)容編寫程序完成動態(tài)分區(qū)存儲管理方式的主存分配回收的實現(xiàn)。實驗具體包括：首先確定主存空間分配表；然后采用最優(yōu)適應(yīng)算法完成主存空間的分配和回收；最后編寫主函數(shù)對所做工作進(jìn)行測試。四、提示與講解 動態(tài)分區(qū)管理方式預(yù)先不將主存劃分成幾個區(qū)域，而把主存除操作系統(tǒng)占用區(qū)域外的空間看作一個大的空閑區(qū)。當(dāng)作業(yè)要求裝入主存時，根據(jù)作業(yè)需要主存空間的大小查詢主存內(nèi)各個空閑區(qū)，當(dāng)從主存空間中找到一個大于或等于該作業(yè)大小的主存空閑區(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ù)也隨主存分配和回收變動。總之。所有分區(qū)情況隨時可能發(fā)生變化，數(shù)據(jù)表格的設(shè)計必須和這個特點相適應(yīng)。由于分區(qū)長度不同，因此設(shè)計的表格應(yīng)該包括分區(qū)在主存中的起始地址和長度。由于分配時空閑區(qū)有時會變成兩個分區(qū)：空閑區(qū)和已分分區(qū)，回收主存分區(qū)時，可能會合并空閑分區(qū)，這樣如果整個主存采用一張表格記錄已分分區(qū)和空閑區(qū)，就會使表格操作繁瑣。主存分配時查找空閑區(qū)進(jìn)行分配，然后填寫已分配區(qū)表，主要操作在空閑區(qū)；某個作業(yè)執(zhí)行完后，將該分區(qū)變成空閑區(qū)，并將其與相鄰的空閑區(qū)合并，主要操作也在空閑區(qū)。由此可見，主存的分配和回收主要是對空閑區(qū)的操作，這樣為了便于對主存空間的分配和回收，就建立兩張分區(qū)表記錄主存使用情況，一張表格記錄作業(yè)占用分區(qū)的“已分配區(qū)表”；一張是記錄空閑區(qū)的“空閑區(qū)表”。這兩張表的實現(xiàn)方法一般有兩種，一種是鏈表形式，一種是順序表形式。在實驗中，采用順序表形式，用數(shù)組模擬。由于順序表的長度必須提前固定，所以無論是“已分配區(qū)表”還是“空閑區(qū)表”都必須事先確定長度。它們的長度必須是系統(tǒng)可能的最大項數(shù)，系統(tǒng)運行過程中才不會出錯。因而在多數(shù)情況下，無論是“已分配區(qū)表”，還是“空閑區(qū)表”都有空閑欄目。已分配區(qū)表中除了分區(qū)起始地址、長度外，也至少還要有一項“標(biāo)志”，如果是空閑欄目，內(nèi)容為空，如果為某個作業(yè)占用分區(qū)的登記項，內(nèi)容為該作業(yè)的作業(yè)名；空閑區(qū)表除了分區(qū)起始地址,長度外，也要有一項“標(biāo)志”，如果是空閑欄目，內(nèi)容為空，如果為某個空閑區(qū)的登記項，內(nèi)容“未分配”，在實際系統(tǒng)中,這兩表格的內(nèi)容可能還要多，實際中僅僅使用上述必須的數(shù)據(jù)。為此，“已分配區(qū)表”和“空閑區(qū)表”在實驗中有如下的結(jié)構(gòu)定義。 已分配區(qū)表的定義：define n 10 //假定系統(tǒng)允許的最大作業(yè)數(shù)量為nstruct {float address。 //已分分區(qū)起始地址 float length。 //已分分區(qū)長度,單位為字節(jié) int flag。 //已分配區(qū)表登記欄標(biāo)志.0表示空欄目,實驗中只支持一個字符的作業(yè)名}used_table[n]。 //已分配區(qū)表空區(qū)表的定義：define m 10 struct {float address。 //空閑區(qū)起始地址 float length。 //空區(qū)長度,單位為字節(jié) int flag。 //空閑區(qū)表登記欄標(biāo)志.0表示空欄目,用1表示未分配} free_table[m]。 //空閑區(qū)表其中分區(qū)起始地址和長度數(shù)值太大，超出了整型表達(dá)范圍，所以采用float類型。 然后，就要考慮如何在設(shè)計的數(shù)據(jù)表格上進(jìn)行主存的分配。當(dāng)要裝入一個作業(yè)時，從空閑區(qū)表中查找標(biāo)志為“未分配”的空閑區(qū)，從中找出一個能容納該作業(yè)的空閑區(qū)。如果找到的空閑正好等于該作業(yè)的長度，則把該分區(qū)全部分配給作業(yè)。這時應(yīng)該把該空閑區(qū)登記欄中的標(biāo)志改為空，同時在已分配區(qū)表中找到一個標(biāo)志為空的欄目登記新裝入作業(yè)所占用分區(qū)的起始地址，長度和作業(yè)名。如果找到的空閑區(qū)大于作業(yè)長度，則把空閑區(qū)的長度，且把空閑區(qū)分成兩部分，一部分用來裝入作業(yè)，另外一部分仍為空閑區(qū)，這時只要修改原空閑區(qū)的長度，且把新裝入的作業(yè)登記到已分配去表中。 實驗中主存分配算法采用“最優(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è)要求的長度略大一點，不再將空閑區(qū)分成已分區(qū)和空閑分區(qū)兩部分，而是將整個空閑區(qū)分配給作業(yè)。在實現(xiàn)最優(yōu)算法時，可把空閑區(qū)按長度以遞增的方式登記在空閑去表中。分配時順序查找空閑表,查找到的第一個空閑區(qū)就是滿足作業(yè)要求的最小分區(qū)。這樣查找速度快，但是為使空閑區(qū)按長度以遞增順序登記在空閑區(qū)表中，就必須在分配回收時進(jìn)行空閑區(qū)表的調(diào)整，空閑區(qū)表調(diào)整時移動表目的代價要高于查詢整張表的代價，所以實驗中不采用空閑區(qū)有序登記在空閑表中的方法。動態(tài)分區(qū)方式的主存分配流程如圖4所示。作業(yè)J申請xk大小的主存空間i=0；k=1Ni是空閑區(qū)表中一欄（i=m）YY是否找到滿足需求的分區(qū)k？第i欄標(biāo)志為“未分配”且滿足作業(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ū)方式下的主存回收問題。 動態(tài)分區(qū)方式下回收主存空間時，應(yīng)該檢查是否有歸還區(qū)相鄰的空閑區(qū)。若有，則應(yīng)合并成一個空閑區(qū)。一個歸還區(qū)可能有上鄰空閑區(qū)，也可能有下鄰空閑區(qū)，或者既有上鄰空閑區(qū)又有下鄰空閑區(qū)，或者既無上鄰空閑區(qū)也無下鄰空閑區(qū)。在實現(xiàn)回收時，首先將作業(yè)歸還的區(qū)域在已分配表中找到，將該欄目的狀態(tài)變?yōu)椤翱铡保缓髾z查空閑區(qū)表中標(biāo)志為“未分配”的欄目，查找是否有相鄰空閑區(qū)；最后，合并空閑區(qū)，修改空閑區(qū)表。假定作業(yè)歸還的分區(qū)起始地址為S，長度為L，則：（1）歸還區(qū)有下鄰空閑區(qū) 如果S+L正好等于空閑區(qū)表中某個登記欄目（假定為第j欄）的起始地址，則表明歸還區(qū)有一個下鄰空閑區(qū)。這時只要修改第j欄登記項的內(nèi)容： 起始地址=S； 第j欄長度=第j欄長度+L； 則第j欄指示的空閑區(qū)是歸還區(qū)和下鄰空閑區(qū)合并后的大空閑區(qū)。（2）歸還區(qū)有上鄰空閑區(qū) 如果空閑區(qū)表中某個登記欄目（假定為第k欄）的“起始地址+長度”正好等于S，則表明歸還區(qū)有一個上鄰空閑區(qū)。這時要修改第k欄登記項的內(nèi)容（起始地址不變）； 第k欄長度=第k欄長度+L； 于是第k欄指示的空閑區(qū)是歸還區(qū)和上鄰空閑區(qū)合并后的大空閑區(qū)。（3）歸還區(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ū)和上、下鄰空閑區(qū)合并后的大空閑區(qū)；原來的下鄰空閑區(qū)登記項（第j 欄）被刪除，置為“空”。（4）歸還區(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ū)域的流程如圖5所示。 由于是實驗，沒有真正的主存要分配，所以在實驗中，首先應(yīng)建立一張空閑表，初始狀態(tài)只有一個空閑登記項（假定的主存空閑區(qū)）和一張所有狀態(tài)都為“空”的已分配區(qū)表，假定主存空間110KB，操作系統(tǒng)占用10KB，其余為空閑區(qū)；然后，可以選擇進(jìn)行主存分配或主存回收，如果是分配，要求輸入作業(yè)名和所需主存空間大小，如果是回收，輸入回收作業(yè)的作業(yè)名，循環(huán)進(jìn)行主存分配和回收后，如果需要，則顯示兩張表的內(nèi)容，以檢查主存的分配和回收是否正確。五、作業(yè)題①編程實現(xiàn)頁式存儲管理的主存分配和回收。②用鏈表方式表示主存空間分配情況，完成動態(tài)分區(qū)管理方式下的主存空間分配和回收。六、參考程序。作業(yè)J歸還空間s=0s=s+1已分配區(qū)表第s欄狀態(tài)為作業(yè)J(s=n)?NNY未找到作業(yè)，回收失敗s為已分配區(qū)表中一欄？Y結(jié)束S=已分配區(qū)表第s欄起始地址L=已分配區(qū)表第s欄長度已分配區(qū)表第s欄狀態(tài)為空假設(shè)下鄰空閑區(qū)在第j欄j= 1假設(shè)上鄰空閑區(qū)在第k欄k=1i=0第i欄不是空閑區(qū)表中一欄或回收分區(qū)的上下上下鄰空閑區(qū)均找到？YYN回收分區(qū)有上鄰?i=i+1YN回收分區(qū)有下鄰?回收分區(qū)有下鄰?第i欄狀態(tài)為“未分配”?NYNN和下鄰合并：第j欄長度=第j欄長度+L；第j欄起始地址=S和上下鄰三項合并：第k欄長度=第k欄長度+第j欄長度+L；第j欄狀態(tài)=“空”Yt=0第i欄為回收分區(qū)的上鄰?j=it=t+1YYN第t欄是空閑表中非空欄？和上鄰合并：第k欄長度=第k欄長度+L；第i欄為回收分區(qū)的下鄰?Nj=iYYN第t欄是空閑表一欄？