分區(qū)存儲管理算法模擬

1、 2013 -2014學年 第3學期 實驗項目名稱分區(qū)存儲管理算法模擬實驗日期2014/12/25實驗成績實驗類型 驗證型實驗目的與要求一個好的計算機系統(tǒng)不僅要有一個足夠容量的、存取速度高的、穩(wěn)定可靠的主存儲器，而且要能合理地分配和使用這些存儲空間。當用戶提出申請存儲器空間時，存儲管理必須根據(jù)申請者的要求，按一定的策略分析主存空間的使用情況，找出足夠的空閑區(qū)域分配給申請者。當作業(yè)撤離或主動歸還主存資源時，則存儲管理要收回作業(yè)占用的主存空間或歸還部分主存空間。主存的分配和回收的實現(xiàn)雖與主存儲器的管理方式有關(guān)的，通過本實驗幫助學生理解在不同的存儲管理方式下應怎樣實現(xiàn)主存空間的分配和回收。實驗原理用

2、最先使用算法模擬內(nèi)存的分配和回收實驗環(huán)境C語言 Dev C+實驗方案設(shè)計實驗內(nèi)容1. 可變分區(qū)方式是按作業(yè)需要的主存空間大小來分割分區(qū)的。當要裝入一個作業(yè)時，根據(jù)作業(yè)需要的主存量查看是否有足夠的空閑空間，若有，則按需要量分割一個分區(qū)分配給該作業(yè)；若無，則作業(yè)不能裝入。隨著作業(yè)的裝入、撤離，主存空間被分成許多個分區(qū)，有的分區(qū)被作業(yè)占用，而有的分區(qū)是空閑的。如下圖3.1所示。 圖3.1主存分區(qū)分配示意圖為了說明哪些區(qū)是空閑的，可以用來裝入新作業(yè)，必須要有一張空閑區(qū)說明表，格式如下表3.1所示。其中，起址指出一個空閑區(qū)的主存起始地址。長度指出從起始地址開始的一個連續(xù)空閑的長度。狀態(tài)有兩種狀態(tài)，一種是

3、“未分配”狀態(tài)，指出對應的由起址指出的某個長度的區(qū)域是空閑區(qū)；另一種是“空表目”狀態(tài)，表示表中對應的登記項目是空白（無效），可用來登記新的空閑區(qū)（例如，作業(yè)撤離后，它所占的區(qū)域就成了空閑區(qū)，應找一個“空表目”欄登記歸還區(qū)的起址和長度且修改狀態(tài)）。由于分區(qū)的個數(shù)不定，所以空閑區(qū)說明表中應有適量的狀態(tài)為“空表目”的登記欄目，否則造成表格“溢出”無法登記。表3.1空閑區(qū)說明表起 址長 度狀 態(tài)第一欄14 K12 K未 分 配第二欄32 K96 K未 分 配MM空 表 目空 表 目MM上述的這張說明表的登記情況是按圖3.1中的例子所裝入的三個作業(yè)占用的主存區(qū)域后填寫的。2. 當有一個新作業(yè)要求裝入主存

4、時，必須查空閑區(qū)說明表，從中找出一個足夠大的空閑區(qū)。有時找到的空閑區(qū)可能大于作業(yè)需要量，這時應把原來的空閑區(qū)變成兩部分：一部分分給作業(yè)占用；另一部分又成為一個較小的空閑區(qū)。為了盡量減少由于分割造成的空閑區(qū)，而盡量保存高地址部分有較大的連續(xù)空閑區(qū)域，以利于大型作業(yè)的裝入。為此，在空閑區(qū)說明表中，把每個空閑區(qū)按其地址順序登記，即每個后繼的空閑區(qū)其起始地址總是比前者大。為了方便查找還可使表格“緊縮”，總是讓“空表目”欄集中在表格的后部。3. 采用最先適應算法（順序分配算法）分配主存空間。按照作業(yè)的需要量，查空閑區(qū)說明表，順序查看登記欄，找到第一個能滿足要求的空閑區(qū)。當空閑區(qū)大于需要量時，一部分用來裝

5、入作業(yè)，另一部分仍為空閑區(qū)登記在空閑區(qū)說明表中。由于本實驗是模擬主存的分配，所以把主存區(qū)分配給作業(yè)后并不實際啟動裝入程序裝入作業(yè)，而用輸出“分配情況”來代替。最先適應分配算法如圖3.2。4. 當一個作業(yè)執(zhí)行結(jié)束撤離時，作業(yè)所占的區(qū)域應該歸還，歸還的區(qū)域如果與其它空閑區(qū)相鄰，則應合成一個較大的空閑區(qū)，登記在空閑區(qū)說明表中。例如，在圖3.1中列舉的情況下，如果作業(yè)2撤離，歸還所占主存區(qū)域時，應與上、下相鄰的空閑區(qū)一起合成一個大的空閑區(qū)登記在空閑區(qū)說明表中。歸還主存時的回收算法如圖3.3。5. 請按最先適應算法設(shè)計主存分配和回收的程序。然后按圖3.1中假設(shè)主存中已裝入三個作業(yè)，且形成兩個空閑區(qū)，確定

6、空閑區(qū)說明表的初值?，F(xiàn)有一個需要主存量為6K的作業(yè)4申請裝入主存；然后作業(yè)3撤離；再作業(yè)2撤離。請你為它們進行主存分配和回收，把空閑區(qū)說明表的初值以及每次分配或回收后的變化顯示出來或打印出來。調(diào)試過程及實驗結(jié)果總結(jié)此實驗還可以寫一個用戶自己的輸入來驗證，增加驗證的準確性附錄#include #include #define COUNT 512typedef struct NODE char name;/名稱float start;/起始位置float end;/大小int flag;/是否分配的標志NODE; NODE OSCOUNT;/數(shù)組int count;/被分成的塊數(shù)統(tǒng)計int app

7、lyfree; float numb; char c; /先對數(shù)組進行初始化，使沒有分配的名稱為pvoid init() count=1; OS0.name =P; OS0.start =0; OS0.end =COUNT; OS0.flag =1; /對數(shù)組的插入操作void insert(int m,float st,float en) int i;count+; for(i=count;im+1;i-) OSi=OSi-1; OSm.start =st; OSm.end =en; /移動操作，即對數(shù)組的刪除操作void move(int m) int i; for(i=m;icount-

8、1;i+) OSi=OSi+1; count-; /如果相鄰塊都沒有分配，則要合并到一起void rremove(int m,float st,float en) if(!OSm-1.flag &!OSm+1.flag ) OS =P; OSm.flag =1; if(OSm-1.flag ) OSm-1.end =OSm-1.end +en; move(m); if(OSm+1.flag ) OSm.end =OSm.end +OSm+1.end; OS =P; OSm.flag =1; move(m+1); /打印輸出void show() int i; print

9、f(名稱 標識 起址 長度 狀態(tài)n); for(i=0;icount;i+) if(OSi.flag ) printf(P ); else printf(%c ,OS ); printf(%d %1.0f %1.0f ,i,OSi.start ,OSi.end ); if(OSi.flag ) printf(未分配n); else printf(已分配n); /從鍵盤輸入數(shù)據(jù)void putin() printf(請輸入申請或者釋放的進程名稱及資源數(shù)量：n); rewind(stdin); scanf(%c,&c); scanf(%d,&applyfree); scanf(%f,&

10、numb); int apply() int i=0; int applyflag=0; int freeflag=0; if(applyfree)/提出申請資源 while(!applyflag&i=numb&OSi.flag ) if(OSi.end =numb) OS =c; OSi.flag =0; else insert(i+1,OSi.start +numb,OSi.end -numb); OSi+1.flag =1; OSi+1.name =P; OSi.start =OSi.start; OS =c; OSi.end =numb; OSi.flag =0

11、; applyflag=1; i+; if(applyflag) printf(申請成功！n); return 1; else printf(申請失?。]有足夠大的空閑空間。n); return 0; else/提出釋放資源 while(!freeflag&inumb) insert(i+1,OSi.start +numb,OSi.end -numb); OSi+1.name =P; OSi+1.flag =0; OSi.end =numb; OSi.flag =1; if(OSi-1.flag ) rremove(i,OSi.start ,OSi.end ); else printf(釋放失敗，因為正使用的數(shù)量小于要求釋放的數(shù)量。n); retu