操作系統(tǒng)課程設(shè)計(jì)連續(xù)存儲空間管理仿真實(shí)現(xiàn)

1、 操作系統(tǒng)原理課程設(shè)計(jì)實(shí)踐報(bào)告題 目: 連續(xù)存儲空間管理仿真實(shí)現(xiàn) 姓 名: 學(xué) 院: 專 業(yè): 班 級: 學(xué) 號: 指導(dǎo)教師: 職稱: 教授 2014年3月 10 日連續(xù)存儲空間管理仿真實(shí)現(xiàn)摘要：連續(xù)分配方式，是指為一個(gè)用戶程序分配一個(gè)連續(xù)的內(nèi)存空間。模擬連續(xù)存儲空間固定分區(qū)、可變分區(qū)、伙伴系統(tǒng)三種分配方法，其中可變分區(qū)采用四種適應(yīng)算法。整個(gè)系統(tǒng)中包括以下功能：查詢、分配、回收、退出，并能通過良好的用戶界面體現(xiàn)出來，為了深刻理解操作系統(tǒng)中的內(nèi)存分配技術(shù)，動態(tài)地為進(jìn)程分配內(nèi)存空間，本系統(tǒng)可按照用戶分配的作業(yè)自動完成內(nèi)存管理的模擬演示。這對深入理解操作系統(tǒng)內(nèi)存分配原理，透析作業(yè)執(zhí)行的各種情況，發(fā)現(xiàn)

2、和探究新的更加高效的內(nèi)存管理方式有重大意義。關(guān)鍵字：存儲空間管理；固定分區(qū)；可變分區(qū)；伙伴系統(tǒng)；仿真1 目的及意義存儲器是計(jì)算機(jī)系統(tǒng)的重要組成部分，而如何有效地管理存儲器對系統(tǒng)地性能有很大的影響，存儲器管理的主要對象是內(nèi)存。連續(xù)分配方式，是指為一個(gè)用戶程序分配一個(gè)連續(xù)的內(nèi)存空間。這種分配方式曾被廣泛應(yīng)用于20世紀(jì)6070 年代的os中，它至今仍在內(nèi)存分配方式中占有一席之地；又可把連續(xù)分配方式進(jìn)一步分為單一連續(xù)分配、固定分區(qū)分配、動態(tài)分區(qū)分配以及動態(tài)重定位分區(qū)分配四種方式。由于在一臺計(jì)算機(jī)中的內(nèi)存分配過程的不可視性、算法的復(fù)雜性、內(nèi)存情況的多樣性和不確定性，使得算法分析與其它算法間的比較相當(dāng)困難

3、。用模擬系統(tǒng)的方法將整個(gè)內(nèi)存的分配使用的過程可視化，這對深入理解操作系統(tǒng)的存儲器管理，透析算法原理，創(chuàng)新算法具有重要意義。2 理論基礎(chǔ) 2.1 固定分區(qū)理論基礎(chǔ)固定分區(qū)式分配是最簡單的一種可運(yùn)行多道程序的存儲管理方式。這是將內(nèi)存用戶空間劃分為若干個(gè)固定大小的區(qū)域，在每個(gè)分區(qū)中只裝入一道作業(yè)，這樣，把用戶空間劃分為幾個(gè)分區(qū)，便允許有幾道作業(yè)并發(fā)運(yùn)行。當(dāng)有一空閑分區(qū)時(shí)，便可以再從外存的后備作業(yè)隊(duì)列中選擇一個(gè)適當(dāng)大小的作業(yè)裝入該分區(qū)，當(dāng)該作業(yè)結(jié)束時(shí)，又可再從后備作業(yè)隊(duì)列中找出另一作業(yè)調(diào)入該分區(qū)。1劃分分區(qū)的方法分區(qū)大小不等。為了克服分區(qū)大小相等而缺乏靈活性的這個(gè)缺點(diǎn)，可把內(nèi)存區(qū)劃分成含有多個(gè)較小的分

4、區(qū)、適量的中等分區(qū)及少量的大分區(qū)。這樣，便可根據(jù)程序的大小為之分配適當(dāng)?shù)姆謪^(qū)。2內(nèi)存分配為了便于內(nèi)存分配，通常將分區(qū)按大小進(jìn)行排隊(duì)，并為之建立一張分區(qū)使用表，其中各表項(xiàng)包括每個(gè)分區(qū)的起始地址、大小及狀態(tài)(是否已分配)，見圖1所示。當(dāng)有一用戶程序要裝入時(shí)，由內(nèi)存分配程序檢索該表，從中找出一個(gè)能滿足要求的、尚未分配的分區(qū)，將之分配給該程序，然后將該表項(xiàng)中的狀態(tài)置為“已分配”；若未找到大小足夠的分區(qū)，則拒絕為該用戶程序分配內(nèi)存。1圖1：固定分區(qū)分區(qū)示意及內(nèi)存分配圖2.2 可變分區(qū)理論基礎(chǔ)動態(tài)分區(qū)分配是根據(jù)進(jìn)程的實(shí)際需要，動態(tài)地為之分配內(nèi)存空間。在實(shí)現(xiàn)可變分區(qū)分配時(shí)，將涉及到分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)、

5、分區(qū)分配算法和分區(qū)的分配與回收操作這樣三個(gè)問題。1分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu) 空閑分區(qū)鏈：為了實(shí)現(xiàn)對空閑分區(qū)的分配和鏈接，在每個(gè)分區(qū)的起始部分，設(shè)置一些用于控制分區(qū)分配的信息，以及用于鏈接各分區(qū)所用的前向指針；在分區(qū)尾部則設(shè)置一后向指針，通過前、后向鏈接指針，可將所有的空閑分區(qū)鏈接成一個(gè)雙向鏈。 2分區(qū)分配算法（1） 首次適應(yīng)算法(first fit)在分配內(nèi)存時(shí)，從鏈?zhǔn)组_始順序查找，直至找到一個(gè)大小能滿足要求的空閑分區(qū)為止；然后再按照作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍留在空閑鏈中。若從鏈?zhǔn)字敝伶溛捕疾荒苷业揭粋€(gè)能滿足要求的分區(qū)，則此次內(nèi)存分配失敗，返回。 1（2）

6、 循環(huán)首次適應(yīng)算法(next fit)該算法是由首次適應(yīng)算法演變而成的。在為進(jìn)程分配內(nèi)存空間時(shí)，不再是每次都從鏈?zhǔn)组_始查找，而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找，直至找到一個(gè)能滿足要求的空閑分區(qū)，從中劃出一塊與請求大小相等的內(nèi)存空間分配給作業(yè)。1 3（3） 最佳適應(yīng)算法(best fit)所謂“最佳”是指每次為作業(yè)分配內(nèi)存時(shí)，總是把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)，避免“大材小用”。為了加速尋找，該算法要求將所有的空閑分區(qū)按其容量以從小到大的順序形成一空閑分區(qū)鏈。1 （4） 最壞適應(yīng)算法(worst fit)最壞適應(yīng)分配算法要掃描整個(gè)空閑分區(qū)表或鏈表，總是挑選一個(gè)最大的空閑

7、區(qū)分割給作業(yè)使用。1 32.3 伙伴系統(tǒng)理論基礎(chǔ)12伙伴系統(tǒng)規(guī)定，無論已分配分區(qū)或空閑分區(qū)，其大小均為2 的k 次冪，k 為整數(shù)，lkm，其中：21 表示分配的最小分區(qū)的大小，2m 表示分配的最大分區(qū)的大小，通常2m是整個(gè)可分配內(nèi)存的大小。假設(shè)系統(tǒng)的可利用空間容量為2m個(gè)字，則系統(tǒng)開始運(yùn)行時(shí)，整個(gè)內(nèi)存區(qū)是一個(gè)大小為2m的空閑分區(qū)。在系統(tǒng)運(yùn)行過程中，由于不斷的劃分，可能會形成若干個(gè)不連續(xù)的空閑分區(qū)，將這些空閑分區(qū)根據(jù)分區(qū)的大小進(jìn)行分類，對于每一類具有相同大小的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)雙向鏈表。這樣，不同大小的空閑分區(qū)形成了k(0km)個(gè)空閑分區(qū)鏈表。當(dāng)需要為進(jìn)程分配一個(gè)長度為n 的存儲

8、空間時(shí)，首先計(jì)算一個(gè)i 值，使2i1<n2i，然后在空閑分區(qū)大小為2i 的空閑分區(qū)鏈表中查找。若找到，即把該空閑分區(qū)分配給進(jìn)程。否則，表明長度為2i的空閑分區(qū)已經(jīng)耗盡，則在分區(qū)大小為2i1的空閑分區(qū)鏈表中尋找。若存在2i1 的一個(gè)空閑分區(qū)，則把該空閑分區(qū)分為相等的兩個(gè)分區(qū)，這兩個(gè)分區(qū)稱為一對伙伴，其中的一個(gè)分區(qū)用于分配，而把另一個(gè)加入分區(qū)大小為2i 的空閑分區(qū)鏈表中。若大小為2i1的空閑分區(qū)也不存在，則需要查找大小為2i2的空閑分區(qū)，若找到則對其進(jìn)行兩次分割：第一次，將其分割為大小為2i1 的兩個(gè)分區(qū)，一個(gè)用于分配，一個(gè)加入到大小為2i1的空閑分區(qū)鏈表中；第二次，將第一次用于分配的空閑區(qū)

9、分割為2i 的兩個(gè)分區(qū)，一個(gè)用于分配，一個(gè)加入到大小為2i的空閑分區(qū)鏈表中。若仍然找不到，則繼續(xù)查找大小為2i3的空閑分區(qū)，以此類推。由此可見，在最壞的情況下，可能需要對2k的空閑分區(qū)進(jìn)行k 次分割才能得到所需分區(qū)。一次分配可能要進(jìn)行多次分割一樣，一次回收也可能要進(jìn)行多次合并，如回收大小為2i的空閑分區(qū)時(shí)，若事先已存在2i的空閑分區(qū)時(shí)，則應(yīng)將其與伙伴分區(qū)合并為大小為2i1的空閑分區(qū)，若事先已存在2i1的空閑分區(qū)時(shí)，又應(yīng)繼續(xù)與其伙伴分區(qū)合并為大小為2i2的空閑分區(qū)，依此類推。33 設(shè)計(jì)思想及設(shè)計(jì)功能說明 3.1 固定分區(qū)設(shè)計(jì)思想一開始對于固定分區(qū)的連續(xù)內(nèi)存分配我的想法是利用二維數(shù)組設(shè)計(jì)內(nèi)存分配表

10、，將內(nèi)存塊的起始地址、占用長度、占用標(biāo)志等信息用數(shù)組的一項(xiàng)進(jìn)行表示，然后我用了40分鐘寫了100行左右的代碼，并且有比較簡介清晰的顯示界面。但是之后跟其他同學(xué)交流，與組員的溝通使我明白，連續(xù)內(nèi)存分配的固定分區(qū)方式不是簡單地用數(shù)組進(jìn)行標(biāo)識模擬，這只是理論上的分配，并沒有真正的實(shí)現(xiàn)內(nèi)存的分配。借鑒了可變分區(qū)的實(shí)現(xiàn)，我決定采用鏈表去做，建立了相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，建了一個(gè)空閑區(qū)鏈表，一個(gè)已分配鏈表，將手動輸入的信息動態(tài)建立結(jié)點(diǎn)，插入到相對應(yīng)的鏈表中，以此來模擬分配內(nèi)存，由于固定分區(qū)是固定大小的內(nèi)存塊，所以要查找比輸入所需內(nèi)存容量大的內(nèi)存塊，有就放置，沒有就給出提示。再之后跟老師交流之后，尤其是助教的講解，

11、使得我們明白，在操作系統(tǒng)中的連續(xù)內(nèi)存分配的過程中是與cpu緊密聯(lián)系的，動態(tài)的建立進(jìn)程，不確定的生成進(jìn)程信息，可以被cpu執(zhí)行的進(jìn)程才會進(jìn)入就緒隊(duì)列，其余的進(jìn)程則是在后備等待隊(duì)列中等待系統(tǒng)資源的滿足。對此我們小組經(jīng)過幾次激烈的討論，最終確定代碼的各項(xiàng)規(guī)范以及數(shù)據(jù)結(jié)構(gòu)的最終版本，并緊趕時(shí)間完成代碼，并且將之前的手動輸入進(jìn)程信息改成隨機(jī)數(shù)生成，將之前的文本形式的輸出改成圖形化可控制輸出顯示，很好的提高了用戶交互的友好性。3.2 可變分區(qū)設(shè)計(jì)思想對于首次適應(yīng)算法：從空閑分區(qū)中從頭遍歷，低地址開始直到找到一個(gè)大于等于申請內(nèi)存大小的分區(qū)，直接在已分區(qū)中按照地址遞增順序增加該進(jìn)程。同時(shí)判斷該分區(qū)長度是否等于

12、零。若等于零，則刪除該分區(qū)，分配完畢?；厥漳硡^(qū)時(shí)，首先在已分配區(qū)中找到該進(jìn)程，釋放該進(jìn)程所占的分區(qū)，并將該分區(qū)插入到空閑分區(qū)中。插入到空閑分區(qū)中時(shí)要從頭遍歷空閑分區(qū)判斷該分區(qū)是否能與相鄰分區(qū)拼接。拼接有三種情況：與左分區(qū)、與右分區(qū)、與左右分區(qū)拼接，拼接后相應(yīng)的改變分區(qū)的地址和長度。若不能進(jìn)行拼接，則按照地址遞增順序作為獨(dú)立分區(qū)加入到空閑分區(qū)當(dāng)中，回收完畢。6對于下次適應(yīng)算法：與首次適應(yīng)算法類似，不同的是，總是從空閑區(qū)的上次掃描結(jié)束處順序查找空閑區(qū)表，直到找到第一個(gè)能滿足長度要求的空閑區(qū)為止。圖2：首次適應(yīng)算法及下次適應(yīng)算法分配內(nèi)存流程圖判斷后備等待隊(duì)列是否有進(jìn)程n拼接與左結(jié)點(diǎn)相鄰與右結(jié)點(diǎn)相鄰y

13、與左右結(jié)點(diǎn)相鄰n新分區(qū)空閑結(jié)點(diǎn)n回收內(nèi)存地址<空閑區(qū)最小地址拼接可與右結(jié)點(diǎn)拼接y地址>空閑區(qū)最大地址拼接可與左結(jié)點(diǎn)拼接yy圖3：首次適應(yīng)算法及下次適應(yīng)算法回收內(nèi)存流程圖對于最優(yōu)適應(yīng)算法：分配內(nèi)存時(shí)，先把空閑區(qū)按長度遞增順序排列，通過掃描整個(gè)空閑區(qū)從空閑區(qū)中挑選一個(gè)能滿足進(jìn)程要求的最小分區(qū)進(jìn)行分配。具體分配過程與最先適應(yīng)算法相同，分配完畢?；厥辗秩r(shí)，現(xiàn)在已分配區(qū)中找到該進(jìn)程，并釋放進(jìn)程節(jié)點(diǎn)，首先把該回收的分區(qū)插在空閑區(qū)的鏈尾，從頭遍歷空閑分區(qū)，判斷左拼接和右拼接，若可以拼接，則直接修改鏈尾分區(qū)的地址和長度，同時(shí)刪除與之拼接的分區(qū)，回收完畢。將空閑區(qū)大小排序nyy分區(qū)長度-=size

14、 進(jìn)程加入已分配鏈表在空閑區(qū)遍歷查找最佳分區(qū)分區(qū)長度=0分區(qū)長度>=sizefree分區(qū)pcb進(jìn)入后備waitlistn對于最差適應(yīng)算法：與最優(yōu)適應(yīng)算法類似，不同的是再分配內(nèi)存時(shí)，首先把空閑區(qū)按長度遞減順序排列，使分配內(nèi)存時(shí)總是挑選一個(gè)最大的空閑區(qū)分割給作業(yè)使用。3圖4：最優(yōu)適應(yīng)算法及最差適應(yīng)算法分配內(nèi)存流程圖nynny回收內(nèi)存無空閑區(qū)鏈在鏈尾并遍歷空閑區(qū)加入空閑區(qū)按分區(qū)大小排序合并分區(qū)合并分區(qū)y與右分區(qū)相鄰 y與左分區(qū)相鄰 與右分區(qū)相鄰 n圖5：最優(yōu)適應(yīng)算法及最差適應(yīng)算法回收內(nèi)存流程圖3.3 伙伴系統(tǒng)設(shè)計(jì)思想24假設(shè)系統(tǒng)的可利用內(nèi)存空間容量為2m個(gè)字（地址從0到2m-1），則

15、在開始運(yùn)行時(shí)，整個(gè)內(nèi)存區(qū)是一個(gè)大小為2m的塊?？臻e將所有的大小相同的空閑塊建于一張子表中。每個(gè)子表是一個(gè)雙重鏈表，這樣的鏈表可能有m+1個(gè)，將這m+1個(gè)表頭指針用向量結(jié)構(gòu)組織成一個(gè)表，稱為可利用空間表。3程序模擬把所有的空閑頁框分組為11個(gè)塊鏈表，每個(gè)塊鏈表分別包含大小為1，2，4，8，16，32，64，128，256，512和1024個(gè)連續(xù)頁框的頁框塊。最大可以申請1024個(gè)連續(xù)頁框，對應(yīng)4mb大小的連續(xù)內(nèi)存。每個(gè)頁框塊的第一個(gè)頁框的物理地址是該塊大小的整數(shù)倍。 2要申請一個(gè)256個(gè)頁框的塊，先從256個(gè)頁框的鏈表中查找空閑塊，如果沒有，就去512個(gè)頁框的鏈表中找，找到了則將頁框塊分為2個(gè)2

16、56個(gè)頁框的塊，一個(gè)分配給應(yīng)用，另外一個(gè)移到256個(gè)頁框的鏈表中。如果512個(gè)頁框的鏈表中仍沒有空閑塊，繼續(xù)向1024個(gè)頁框的鏈表查找，如果仍然沒有，則返回錯(cuò)誤。分配內(nèi)存是否空閑？add_full_memory()下一級大小size<=memory_sizej圖6：伙伴系統(tǒng)分配內(nèi)存示意圖內(nèi)核要分配一組連續(xù)的頁框，必須建立一種健壯、高效的分配策略。為此，必須解決著名的外部碎片（external fragmentation）問題。頻繁地請求和釋放不同大小的一組連續(xù)頁框，必然導(dǎo)致在已分配頁框的塊內(nèi)分散了許多小塊的空閑頁框。由此帶來的問題是，即使有足夠的空閑頁框可以滿足請求，但要分配一個(gè)大塊的連

17、續(xù)頁框就可能無法滿足。以上過程的逆過程就是頁框塊的釋放過程，也是該算法名字的由來。內(nèi)核試圖把大小為b的一對空閑伙伴塊合并為一個(gè)大小為2b的單獨(dú)塊。滿足以下條件的兩個(gè)塊稱為伙伴： 兩個(gè)塊具有相同的大小，記作b。 它們的物理地址是連續(xù)的。 第一塊的第一個(gè)頁框的物理地址是2×b×212的倍數(shù)。起始地址為p，大小為2k的內(nèi)存塊，其伙伴塊的起始地址為：2buddyp，k=p+2k若 p mod 2k+1=0p-2k若 p mod 2k+1=2k add_free_memory()回收內(nèi)存 delete_full_memory(p); address%(2*data)=dat

18、a buddy(p)address%(2*data)=0左合并右合并圖7：伙伴系統(tǒng)回收內(nèi)存示意圖3.4 設(shè)計(jì)功能說明1. 輸入先判斷使用哪種方式，分別有固定分區(qū)、可變分區(qū)、伙伴系統(tǒng)，在可變分區(qū)中還要在首次適應(yīng)算法、下次適應(yīng)算法、最優(yōu)適應(yīng)算法、最差適應(yīng)算法中選擇一個(gè)算法。隨后隨機(jī)產(chǎn)生進(jìn)程，產(chǎn)生的進(jìn)程數(shù)由用戶輸入，保存到pcb表中。4，2. 界面（1）隨機(jī)產(chǎn)生的進(jìn)程將顯示在屏幕上，隨機(jī)的信息包含進(jìn)程名，所占內(nèi)存大小，起始時(shí)間和持續(xù)時(shí)間；（2）動態(tài)顯示內(nèi)存分配，利用計(jì)算機(jī)圖形學(xué)的知識，將不同的進(jìn)程顯示不同的額顏色，按照系統(tǒng)時(shí)間進(jìn)行分配，一旦回收就進(jìn)行擦除即從pcb表中刪除該進(jìn)程。4 核心數(shù)

19、據(jù)結(jié)構(gòu)說明 4.1 核心數(shù)據(jù)結(jié)構(gòu)刪除n回收申請y pcb表內(nèi)存后備等待隊(duì)列就緒隊(duì)列圖8：整體框架示意圖利用隨機(jī)數(shù)生成隨即進(jìn)程，將其放入到pcb表中，記錄好隨機(jī)生成的進(jìn)程名，起始時(shí)間，持續(xù)時(shí)間等要素。這時(shí)這些進(jìn)程申請內(nèi)存，如果這時(shí)候內(nèi)存足夠則將其放入到就緒隊(duì)列中，即為其分配內(nèi)存。反之，當(dāng)內(nèi)存不夠則將其加入到后備等待隊(duì)列。每來一個(gè)進(jìn)程先優(yōu)先掃描后備等待隊(duì)列，這里的后備等待隊(duì)列采取先來先服務(wù)算法，從頭開始進(jìn)行掃描，一旦后備等待隊(duì)列里含有進(jìn)程則優(yōu)先為其分配內(nèi)存，如若內(nèi)存不足則將下一個(gè)進(jìn)程加入到后備等待隊(duì)列，以此類推。具體流程見圖也就是說程序中將有pcb表，就緒隊(duì)列，后備等待隊(duì)列三個(gè)區(qū)，進(jìn)程周轉(zhuǎn)在其中。

20、4.2 具體模塊實(shí)現(xiàn)1固定分區(qū)分配與回收（c語言）（1）pcb表：typedef struct pcb int sign; int data; long start; int time1; struct pcb *next;*pcb;typedef struct pcb front;pcb rear;pcb_head;（2）后備等待隊(duì)列：typedef struct node int sign; int data; int time; struct node *next;*queue;typedef struct queue front; queue rear;queue_head;2. 可變

21、分區(qū)分配與回收（c語言）first_fit：空閑分區(qū)按起始地址從小到大排序next_fit：空閑分區(qū)按起始地址從小到大排序best_fit ：空閑分區(qū)按大小從小到大排序worst_fit ：空閑分區(qū)按大小從大到小排序（1）pcb表：typedef struct pcb int sign; int data; long start; int time1; struct pcb *next;*pcb;typedef struct pcb front;pcb rear;pcb_head;（2）后備等待隊(duì)列：typedef struct node int sign; int data; int tim

22、e; struct node *next;*queue;typedef struct queue front; queue rear;queue_head;（3）就緒隊(duì)列：typedef struct pnode/內(nèi)存塊結(jié)點(diǎn)int data;int sign; /進(jìn)程名int address;int time; /持續(xù)時(shí)間struct pnode *pre; /指向前結(jié)點(diǎn)struct pnode *next;*queueptr;typedef struct /頭結(jié)點(diǎn) queueptr front; queueptr rear;linkqueue;3. 伙伴系統(tǒng)分配與回收（c+）2（1）pcb表

23、：class pcb public: pcb()/構(gòu)造函數(shù) pcb *next string sign;/進(jìn)程名 int data;/所占內(nèi)存大小 long start;/起始時(shí)間 int time;/持續(xù)時(shí)間 int flag;（2）后備等待隊(duì)列：class wait public: wait()/構(gòu)造函數(shù) wait *next； string sign;/進(jìn)程名 int data;/所占內(nèi)存大小 int time;/持續(xù)時(shí)間;（3）就緒隊(duì)列：class full_memory public: full_memory()/構(gòu)造函數(shù) full_memory *pre,*next string

24、sign;/進(jìn)程名 int full_data;/所占內(nèi)存 int address;/起始地址 int lasttime;/持續(xù)時(shí)間;5 核心算法流程 5.1 固定分區(qū)算法流程圖9：固定分區(qū)算法流程圖固定分區(qū)分區(qū)大小是提前設(shè)定好的，且每個(gè)分區(qū)中裝入一個(gè)作業(yè)，所以利用鏈表設(shè)計(jì)內(nèi)存分配表，將內(nèi)存塊的起始地址、占用長度、占用標(biāo)志等信息進(jìn)行表示。建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，一個(gè)空閑區(qū)鏈表，一個(gè)已分配鏈表，將隨機(jī)產(chǎn)生的進(jìn)程的信息動態(tài)建立結(jié)點(diǎn)，插入到相對應(yīng)的鏈表中，以此來模擬分配內(nèi)存，由于固定分區(qū)是固定大小的內(nèi)存塊，所以要查找比輸入所需內(nèi)存容量大的內(nèi)存塊，若有就放置，并將系統(tǒng)時(shí)間增加1，持續(xù)時(shí)間減去1；若沒有就給

25、出提示，同時(shí)將其加入到后備等待隊(duì)列中，之后掃描時(shí)先查看后備等待隊(duì)列，一旦后備等待隊(duì)列中有內(nèi)容，先為后備等待隊(duì)列首個(gè)進(jìn)程分配，新來的進(jìn)程插入到后備等待隊(duì)列中，循環(huán)做。當(dāng)進(jìn)程的持續(xù)時(shí)間為零，即進(jìn)程已經(jīng)運(yùn)行完畢，則將其從已分配鏈表和pcb表中刪除，當(dāng)pcb表中沒有內(nèi)容時(shí)，整個(gè)程序結(jié)束。初始化pcb表選擇分配算法結(jié)束clk=pcb->startynn后備wait有進(jìn)程內(nèi)存回收pcb進(jìn)入后備waitlistclk+<=時(shí)間內(nèi)存占用內(nèi)存分配lasttime-內(nèi)存空間>=sizepcb進(jìn)入readylist5.2 可變分區(qū)算法流程圖10：可變分區(qū)算法流程圖算法開始時(shí)，先模擬進(jìn)程并發(fā)環(huán)境，將

26、產(chǎn)生的進(jìn)程送入到pcb表中，選擇最先適應(yīng)算法、最優(yōu)適應(yīng)算法、下次適應(yīng)算法、最差適應(yīng)算法四個(gè)算法中的一個(gè)進(jìn)行開始。這是判斷有沒有到達(dá)進(jìn)入時(shí)間的進(jìn)程，如果有就開始申請內(nèi)存，一旦內(nèi)存足夠就對其分配內(nèi)存，與此同時(shí)判斷該進(jìn)程是否已經(jīng)結(jié)束，即持續(xù)時(shí)間為零如果已經(jīng)結(jié)束就從pcb表中刪除該進(jìn)程，同時(shí)系統(tǒng)時(shí)間加1。如果內(nèi)存不足夠分配則將該進(jìn)程加入到后備等待隊(duì)列中，每次內(nèi)存回收結(jié)束后下一次分配開始前都要檢查后備等待隊(duì)列中是否有進(jìn)程一旦有就采取先來先服務(wù)策略為第一個(gè)進(jìn)程分配空間，對內(nèi)存的判斷還與之前相同。一旦后備等待隊(duì)列里有，就不再為信賴的進(jìn)程分配空間而是將其直接加入到等待隊(duì)列中，重復(fù)以上過程直到pcb表中沒有進(jìn)程

27、為止，程序結(jié)束。結(jié)束systime=pcb->start初始化pcb表pcb進(jìn)入full_memoryynn后備wait有進(jìn)程內(nèi)存回收pcb進(jìn)入后備waitlistsystime+<=時(shí)間內(nèi)存占用內(nèi)存分配lasttime-內(nèi)存空間>=size5.3 伙伴系統(tǒng)算法流程圖11：伙伴系統(tǒng)算法流程圖伙伴系統(tǒng)整體流程與可變分區(qū)類似，區(qū)別在于分配存儲空間的方式和回收存儲空間的方式，即具體區(qū)別于算法。6 開發(fā)調(diào)試及運(yùn)行環(huán)境 6.1 開發(fā)及運(yùn)行環(huán)境vc+6.06.2 用戶手冊1. 安裝使用（1）在vc+6.0安裝路徑中找到lib文件夾加入提供的lib文件夾中的項(xiàng)目；（2）在vc+6.0安裝路

28、徑中找到include文件夾加入提供的include文件夾中的項(xiàng)目；（3）將19211209_李艷偉文件夾拷貝到e盤根目錄下；（4） 雙擊連續(xù)存儲空間管理仿真系統(tǒng).exe。2. 操作（1）根據(jù)提示輸入數(shù)據(jù)；（2）每一次循環(huán)輕敲一下回車，輸出數(shù)據(jù)；（3）按任意鍵結(jié)束。3. 注意事項(xiàng)（1）內(nèi)存長度設(shè)定為1024；（2）伙伴系統(tǒng)建議輸入較小的起始時(shí)間以及持續(xù)時(shí)間以免長時(shí)間不出現(xiàn)變化。7 功能說明及測試數(shù)據(jù)分析 7.1 功能說明1. 固定分區(qū)圖12：隨機(jī)產(chǎn)生進(jìn)程顯示圖圖13：固定分區(qū)分區(qū)圖圖14：固定分區(qū)內(nèi)存分配圖 由隨機(jī)數(shù)產(chǎn)生隨機(jī)進(jìn)程，進(jìn)行分配，每一種顏色代表一個(gè)新的進(jìn)程，在進(jìn)程占用內(nèi)存時(shí)會將黑色置

29、為內(nèi)存的顏色這樣便于查看。左上角顯示的是系統(tǒng)時(shí)間，每檢索一次時(shí)間增加1，與進(jìn)程的持續(xù)時(shí)間與開始時(shí)間相匹配。2. 可變分區(qū)圖15：隨機(jī)產(chǎn)生進(jìn)程顯示圖圖16：可變分區(qū)分區(qū)圖17：可變分區(qū)內(nèi)存分配圖可變分區(qū)與固定分區(qū)相類似，只不過內(nèi)存開始不再劃分為固定的塊，而是根據(jù)產(chǎn)生的進(jìn)程對其按照四種可選的不同算法進(jìn)行分配，依舊使用顏色表示不同進(jìn)程，左上角顯示系統(tǒng)時(shí)間。 3. 伙伴系統(tǒng)圖18：伙伴系統(tǒng)內(nèi)存分配圖由于時(shí)間不足，所以伙伴系統(tǒng)缺少圖形化界面而是采用文字輸出，不過為了清晰也按順序輸出內(nèi)存塊占用情況，以及地址及占用其的進(jìn)程，方便查看。7.2 測試數(shù)據(jù)及分析設(shè)置的內(nèi)存大小為1024，所以我們選擇了許多有代表性

30、的數(shù)據(jù)：（1）進(jìn)程1:32；進(jìn)程2:64；進(jìn)程3:128；進(jìn)程4:256（2）進(jìn)程1:512；進(jìn)程2:664；進(jìn)程3:128；進(jìn)程4:256（3）進(jìn)程1:256；進(jìn)程2:256；進(jìn)程3:256；進(jìn)程4:256這三組數(shù)據(jù)可分別測試普通情況不存在內(nèi)存不足情況下、存在內(nèi)存占用需進(jìn)入后備等待隊(duì)列情況下、以及是否能正確合并伙伴的三種情況，這三組數(shù)據(jù)都返回了良好的結(jié)果。8 存在問題及改進(jìn)設(shè)想8.1 存在問題（1）后備等待隊(duì)列采取先來先服務(wù)的策略，可能會使某些申請小內(nèi)存的進(jìn)程長時(shí)間滯留。（2）對于同類別的分配算法，沒有找到合適的比較優(yōu)劣的指標(biāo)。（3）沒有實(shí)現(xiàn)搬家問題。（4）對于同時(shí)到來的進(jìn)程沒有優(yōu)先級處理，

31、實(shí)際變?yōu)椴煌瑫r(shí)間的進(jìn)程處理。8.2改進(jìn) （1）采用更優(yōu)質(zhì)的算法比如多級反饋隊(duì)列處理。（2）多查找閱讀相關(guān)文獻(xiàn)找到合適的比較可變分區(qū)不同算法優(yōu)劣的指標(biāo)。（3）實(shí)現(xiàn)搬家問題。（4）更加人性化的界面。9實(shí)踐體會及心得9.1 工作分配（1）組長：李艷偉 固定分區(qū)存儲管理、固定分區(qū)并發(fā)環(huán)境模擬 可變分區(qū)并發(fā)環(huán)境模擬（2）組員：李小敏 可變分區(qū)存儲管理，四個(gè)算法分配與回收 最終匯報(bào)ppt制作（3）組員：毛新玥 伙伴系統(tǒng)、伙伴系統(tǒng)并發(fā)環(huán)境模擬 最終匯報(bào)ppt制作、撰寫實(shí)驗(yàn)報(bào)告9.2 時(shí)間分配2014.2.9-2.15 小組成員復(fù)習(xí)操作系統(tǒng)知識選擇三個(gè)題目2014.2.16-2.17 組員線上討論，確定數(shù)據(jù)結(jié)

32、構(gòu)、所用語言最終題目及分工2014.2.18-2.22 組員自己尋找資料掌握自己分工部分知識并開始寫算法2014.2.23-3.2 繼續(xù)完善自己算法2014.3.3 與老師交流加入并行2014.3.5 與老師交流增加后續(xù)等待隊(duì)列以及pcb表2014.3.6-3.7 收尾工作以及測試匯報(bào)2014.3.7-3.12 撰寫實(shí)驗(yàn)報(bào)告9.3實(shí)踐體會參考文獻(xiàn)：1 湯子丹，梁紅兵，哲鳳屏，湯子瀛.計(jì)算機(jī)操作系統(tǒng)（第三版）m.西安：西安電子科技大學(xué)出版社.2007 p1212 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（c語言版）m.北京：清華大學(xué)出版社.2007 p2033 孫鐘秀，費(fèi)翔林，駱斌.操作系統(tǒng)教程（第4版）m.北

33、京：高等教育出版社.2008.4 p2374 溫秀梅，丁學(xué)鈞.visual c+面向?qū)ο蟪绦蛟O(shè)計(jì)教程與實(shí)驗(yàn)（第二版）m.北京：清華大學(xué)出版社.2009.4 p2075 鄭曉曦，張虎.一種改進(jìn)的伙伴系統(tǒng)內(nèi)存管理方法.j.計(jì)算機(jī)與數(shù)字工程.20086 譚耀銘.操作系統(tǒng)導(dǎo)論.m.光明日報(bào)出版社.2008.6核心部分源碼： #include <stdlib.h> #include <stdio.h> #include <conio.h>#include <iostream.h>typedef struct pnodeint data;int sign;i

34、nt address;struct pnode *pre;struct pnode *next;pnode,*queueptr;typedef structqueueptr front;queueptr rear;linkqueue;linkqueue ff,ff_fenpei; /空閑區(qū)鏈與已分配區(qū)鏈queueptr ff_ff;queueptr ff_next_ff; /針對下次適應(yīng)算法，保存每次掃描完未分配區(qū)的位置int ff_count=0; /已分配的進(jìn)程數(shù)int ff_total=0; /已分配的分區(qū)容量void banjia(linkqueue &ff,linkqueue

35、 &ff_fenpei) /搬家queueptr p,q,r;p=ff_fenpei.front;p->address=0;q=p->next;while(q) /修改已分配鏈表中進(jìn)程的地址q->address=p->address+p->data;p=q;q=q->next;/q能否=nullr=ff.front; /修改空閑區(qū)q=r->next;r->address=p->address+p->data;r->data=10000-ff_total;r->next=null;r->pre=null;ff.

36、rear=r;while(q) /釋放原空閑區(qū)中其它結(jié)點(diǎn)p=q->next;free(q);q=p;void sort(linkqueue &ff) /按分區(qū)從小到大排序(針對最佳適應(yīng)算法)int num=0,t1,t2;queueptr ff_ff;ff_ff=ff.front;while(ff_ff!=null) /確定空閑區(qū)中分區(qū)的數(shù)目num+;ff_ff=ff_ff->next;ff_ff=ff.front;for(int i=0;i<num-1;i+) /冒泡排序for(int j=0;j<num-1-i;j+)if(ff_ff->data>

37、;ff_ff->next->data)t1=ff_ff->data;ff_ff->data=ff_ff->next->data;ff_ff->next->data=t1;t2=ff_ff->address;ff_ff->address=ff_ff->next->address;ff_ff->next->address=t2;ff_ff=ff_ff->next;ff_ff=ff.front;void sort1(linkqueue &ff) /按分區(qū)從大到小排序(針對最差適應(yīng)算法)int num=0

38、,t1,t2;queueptr ff_ff;ff_ff=ff.front;while(ff_ff!=null) /確定空閑區(qū)中分區(qū)的數(shù)目num+;ff_ff=ff_ff->next;ff_ff=ff.front;for(int i=0;i<num-1;i+) /冒泡排序for(int j=0;j<num-1-i;j+)if(ff_ff->data<ff_ff->next->data)t1=ff_ff->data;ff_ff->data=ff_ff->next->data;ff_ff->next->data=t1;t2

39、=ff_ff->address;ff_ff->address=ff_ff->next->address;ff_ff->next->address=t2;ff_ff=ff_ff->next;ff_ff=ff.front;void add_ff(linkqueue &ff_fenpei,queueptr process) /按照地址遞增順序添加進(jìn)程控制塊于已分配鏈表中if(ff_fenpei.front=null)/已分配鏈表中空，該進(jìn)程成為頭結(jié)點(diǎn)ff_fenpei.front=ff_fenpei.rear=process;elsequeueptr

40、 ff_fenpei_ff,ff_fenpei_ff1;ff_fenpei_ff=ff_fenpei.front;while(ff_fenpei_ff!=null)if(process->address<ff_fenpei_ff->address)if(process->address<ff_fenpei.front->address) /如果小于已分配的最低地址，則成為已分配鏈表的頭結(jié)點(diǎn) process->next=ff_fenpei_ff;process->pre=null;ff_fenpei_ff->pre=process;ff_fe

41、npei.front=process;else /不小于已分配的最低地址 if(ff_fenpei_ff->pre!=null) ff_fenpei_ff->pre->next=process; process->next=ff_fenpei_ff; process->pre=ff_fenpei_ff->pre; break;ff_fenpei_ff1=ff_fenpei_ff; /記錄每次比較的結(jié)點(diǎn)ff_fenpei_ff=ff_fenpei_ff->next;if(ff_fenpei_ff=null) /大于已分配的最大地址ff_fenpei_ff

42、1->next=process; /進(jìn)程鏈在最后process->pre=ff_fenpei_ff1;ff_fenpei.rear=process;void first_fit(linkqueue &ff,queueptr &ff_ff,linkqueue &ff_fenpei) / 最先適應(yīng)算法int name,size; bool find;while(1)cout<<"請輸入作業(yè)名（1-9）"cin>>name;cout<<"請輸入作業(yè)所需內(nèi)存空間"cin>>siz

43、e;l1:ff_ff=ff.front;find=false;while(ff_ff!=null) /從低地址開始遍歷查找if(ff_ff->data>=size)queueptr process=(queueptr)malloc(sizeof(pnode);process->address=ff_ff->address;process->data=size;process->sign=name;process->next=null;process->pre=null;add_ff(ff_fenpei,process); / 將進(jìn)程加入已分配鏈表

44、ff_ff->data-=size; /分區(qū)長度減小ff_ff->address+=size; /分區(qū)地址增加find=true; ff_count+; ff_total+=size; if(ff_ff->data=0) /如果該分區(qū)已經(jīng)分配完 則刪除結(jié)點(diǎn)if(ff_ff->pre=null) /如果該分區(qū)是首分區(qū)ff.front=ff_ff->next;if(ff.front!=null) /還存在可用分區(qū)ff.front->pre=null;else if(ff_ff->next=null) /尾分區(qū)ff_ff->pre->next=n

45、ull; else /在中間ff_ff->pre->next=ff_ff->next; ff_ff->next->pre=ff_ff->pre;free(ff_ff); /刪除節(jié)點(diǎn)break;ff_ff=ff_ff->next;if(!find) /如果沒有合適大小的分區(qū)可供使用，則判斷是否可以進(jìn)行移動搬家int rest=10000-ff_total;/剩余的分區(qū)長度 if(rest>=size) /搬家banjia(ff,ff_fenpei);goto l1; /搬家后繼續(xù)分配elsecout<<"已無足夠空間，請等待!

46、n"break;void next_fit(linkqueue &ff,queueptr &ff_ff,linkqueue &ff_fenpei) /下次適應(yīng)算法int name,size; bool find;while(1)cout<<"請輸入作業(yè)名（1-9）"cin>>name;cout<<"請輸入作業(yè)所需內(nèi)存空間"cin>>size;if(ff_next_ff=null) /循環(huán)，又從頭結(jié)點(diǎn)開始l2:ff_next_ff=ff.front;find=false;wh

47、ile(ff_next_ff!=null) /從低地址開始遍歷查找if(ff_next_ff->data>=size)queueptr process=(queueptr)malloc(sizeof(pnode);process->address=ff_next_ff->address;process->data=size;process->sign=name;process->next=null;process->pre=null;add_ff(ff_fenpei,process); / 將進(jìn)程加入相應(yīng)進(jìn)程隊(duì)列ff_next_ff->da

48、ta-=size; /分區(qū)長度減小ff_next_ff->address+=size; /分區(qū)地址增加find=true; ff_count+; ff_total+=size; if(ff_next_ff->data=0) /如果該分區(qū)已經(jīng)分配完 則刪除結(jié)點(diǎn)if(ff_next_ff->pre=null) /如果該分區(qū)是首分區(qū)ff_next_ff=ff_next_ff->next;if(ff_next_ff!=null) /還存在可用分區(qū)ff_next_ff->pre=null;else /非首分區(qū)if(ff_next_ff->next=null) /尾分區(qū)

49、ff_next_ff->pre->next=null; /ff_next_ff=ff.front;else /在中間ff_next_ff->pre->next=ff_next_ff->next; ff_next_ff->next->pre=ff_next_ff->pre; free(ff_next_ff);break;ff_next_ff=ff_next_ff->next;if(!find) /如果沒有合適大小的分區(qū)可供使用，則判斷是否可以進(jìn)行移動搬家int rest=10000-ff_total; if(rest>=size) /經(jīng)移動搬家可以湊出所需空間banjia(ff,ff_fenpei);goto l2; /搬家后繼續(xù)分配elsecout<<"已無足夠空間，請等待!n" break;void best_fit(linkqueue &ff,queueptr &ff_ff,linkqueue &ff_fenpei) / 最佳適應(yīng)算法sort(ff); /按分區(qū)長度大小排序int name,size; bool find;while(1)cout<&