主存空間的分配與回收實驗報告

1、實 驗 報 告課程名稱： 操作系統(tǒng) 實驗名稱： 主存空間的分配與回收 學 號： 110310014 學生姓名： 于釗 班 級： 信管1101班 指導(dǎo)教師： 吳聯(lián)世 實驗日期： 2013 年12 月 5日1、實驗?zāi)康模?熟悉主存的分配與回收。理解在不同的存儲管理方式下，如何實現(xiàn)主存空間的分配與回收。掌握動態(tài)分區(qū)分配方式中的數(shù)據(jù)結(jié)構(gòu)和分配算法及動態(tài)分區(qū)存儲管理方式及其實現(xiàn)過程。2、實驗要求實驗要求使用可變分區(qū)存儲管理方式，分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)采用空閑分區(qū)表和空閑分區(qū)鏈來進行，分區(qū)分配中所用的算法采用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最佳適應(yīng)算法三種算法來實現(xiàn)主存的分配與回收。同時，要求設(shè)計一個實

2、用友好的用戶界面，并顯示分配與回收的過程。3、實驗環(huán)境硬件： CPU ：AMD QL64 內(nèi)存：2GB 顯卡：ATI 4570 硬盤：日立250G軟件：Windows 2000/XP。 開發(fā)工具：VC+6.0。4、實驗內(nèi)容1）實現(xiàn)原理主存的分配和回收的實現(xiàn)是與主存儲器的管理方式有關(guān)的。所謂分配，就是解決多道作業(yè)或多進程如何共享主存空間的問題。所謂回收，就是當作業(yè)運行完成時將作業(yè)或進程所占的主存空間歸還給系統(tǒng)?？勺兎謪^(qū)管理是指在處理作業(yè)過程中建立分區(qū)，使分區(qū)大小正好適合作業(yè)的需求，并且分區(qū)個數(shù)是可以調(diào)整的。當要裝入一個作業(yè)時，根據(jù)作業(yè)需要的主存量查看是否有足夠的空閑空間，若有，則按需要量分割一個

3、分區(qū)分配給該作業(yè)；若無，則作業(yè)不能裝入，作業(yè)等待。隨著作業(yè)的裝入、完成，主存空間被分成許多大大小小的分區(qū)，有的分區(qū)被作業(yè)占用，而有的分區(qū)是空閑的。為了說明那些分區(qū)是空閑的，可以用來裝入新作業(yè)，必須有一張空閑說明表例如：010k20k45k65k110k256k操作系統(tǒng)（10KB）作業(yè)1（10KB）作業(yè)4（25KB）空閑區(qū)1（20KB）作業(yè)2（45KB） 空閑區(qū)2（146KB）  空閑區(qū)說明表格式如下：  起始地址長度狀態(tài)第一欄45 K20KB未 分 配第二欄110 K146 KB未 分 配MM   空 表 目

4、60; 空 表 目  MM其中，起址指出一個空閑區(qū)的主存起始地址，長度指出空閑區(qū)的大小。 長度指出從起始地址開始的一個連續(xù)空閑的長度。 狀態(tài)有兩種狀態(tài)，一種是“未分配”狀態(tài)，指出對應(yīng)的由起址指出的某個長度的區(qū)域是空閑區(qū)；另一種是“空表目”狀態(tài)，表示表中對應(yīng)的登記項目是空白（無效），可用來登記新的空閑區(qū)（例如，作業(yè)完成后，它所占的區(qū)域就成了空閑區(qū)，應(yīng)找一個“空表目”欄登記歸還區(qū)的起址和長度且修改狀態(tài)）。由于分區(qū)的個數(shù)不定，所以空閑區(qū)說明表中應(yīng)有適量的狀態(tài)為“空表目”的登記欄目，否則造成表格“溢出”無法登記。2、當有一個新作業(yè)要求裝入主存時，必須查空閑區(qū)說明表，從中找

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

6、要量時，一部分用來裝入作業(yè)，另一部分仍為空閑區(qū)登記在空閑區(qū)說明表中。由于本實驗是模擬主存的分配，所以把主存區(qū)分配給作業(yè)后并不實際啟動裝入程序裝入作業(yè)，而用輸出“分配情況”來代替。4、當一個作業(yè)執(zhí)行完成撤離時，作業(yè)所占的分區(qū)應(yīng)該歸還給系統(tǒng)，歸還的分區(qū)如果與其它空閑區(qū)相鄰，則應(yīng)合成一個較大的空閑區(qū)，登記在空閑區(qū)說明表中。例如，在上述中列舉的情況下，如果作業(yè)2撤離，歸還所占主存區(qū)域時，應(yīng)與上、下相鄰的空閑區(qū)一起合成一個大的空閑區(qū)登記在空閑區(qū)說明表中。2）程序結(jié)構(gòu)（流程圖）首次適應(yīng)分配模擬算法主存回收算法3）實現(xiàn)步驟實現(xiàn)動態(tài)分區(qū)的分配與回收，主要考慮三個問題：第一，設(shè)計記錄主存使用情況的數(shù)據(jù)表格，用來

7、記錄空閑區(qū)和作業(yè)占用的區(qū)域；第二，在設(shè)計的數(shù)據(jù)表格基礎(chǔ)上設(shè)計主存分配算法；第三，在設(shè)計的數(shù)據(jù)表格基礎(chǔ)上設(shè)計主存回收算法。1 設(shè)計記錄主存使用情況的數(shù)據(jù)表格由 于動態(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ū)進行分 配，然

8、后填寫已分配區(qū)表，主要操作在空閑區(qū)；某個作業(yè)執(zhí)行完后，將該分區(qū)貶詞空閑區(qū)，并將其與相鄰的空閑區(qū)合并，主要操作也在空閑區(qū)。由此可見，主存的分 配與回收主要時對空閑區(qū)的操作。這樣為了便于對主存空間的分配與回收，就建立兩張分區(qū)表記錄主存的使用情況：“已分配區(qū)表”記錄作業(yè)占用分區(qū)，“空閑區(qū) 表”記錄空閑區(qū)。這兩張表的實現(xiàn)方法一般由兩種：鏈表形式、順序表形式。在本實驗中，采用順序表形式，用數(shù)組模擬。由于順序表的長度必須提前固 定，所以無論是“已分配區(qū)表”還是“空閑區(qū)表”都必須事先確定長度。它們的長度必須是系統(tǒng)可能的最大項數(shù)，系統(tǒng)運行過程中才不會出錯，因此在多數(shù)情況下， 無論是“已分配表區(qū)”還是“空閑區(qū)表

9、”都是空閑欄目。已分配區(qū)表中除了分區(qū)起始地址、長度外，也至少還有一項“標志”，如果是空閑欄目，內(nèi)容為“空”，如 果為某個作業(yè)占用分區(qū)的登記項，內(nèi)容為該作業(yè)的作業(yè)名；空閑區(qū)表除了分區(qū)起始地址、長度外，也要有一項“標志”，如果是空閑欄目，內(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; /已

10、分分區(qū)長度，單位為字節(jié) int flag; /已分配表區(qū)登記欄標志，用0表示空欄目，used_tablen; /已分配區(qū)表空閑區(qū)表的定義：#define m 10 /假定系統(tǒng)允許的空閑區(qū)表最大為mstruct float address; /空閑區(qū)起始地址 float length; /空閑區(qū)長度，單位為字節(jié) int flag; /空閑區(qū)表登記欄目用0表示空欄目，1表示未分配?free_tablem; /空閑區(qū)表其中分區(qū)起始地址和長度數(shù)值太大，超出了整形表達范圍，所有采用float類型。2 在設(shè)計的表格上進行主存分配當 要裝入一個作業(yè)時，從空閑區(qū)表中查找標志為“未分配”的空閑區(qū)，從中找一個能容

11、納該作業(yè)的空閑區(qū)。如果找到的空閑區(qū)正好等于該作業(yè)的長度，則把該分區(qū)全部 分配給該作業(yè)。這時應(yīng)該把該空閑區(qū)登記欄中的標志改為“空”，同時在已分配區(qū)表中找到一個標志為“空”的欄目登記新裝入作業(yè)所占用分區(qū)的起始地址、長度和 作業(yè)名。如果找到的空閑區(qū)大于作業(yè)長度，則把空閑區(qū)分成兩部分，一部分用來裝入作業(yè)，另一部分你仍然為空閑區(qū)，這時只要修改空閑區(qū)的長度，且把新裝入的作 業(yè)登記到已分配區(qū)表中。主存分配算法目前一般采用三種算法：首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最佳適應(yīng)算法。本實驗中采用最佳適應(yīng)算法為作業(yè)分配主存。最佳適應(yīng)算法會出現(xiàn)空閑分區(qū)分割后剩下的空閑分區(qū)很小以至于無法使用的情況，為了在一定程度上解決這

12、個問題，如果空閑分區(qū)的大小比作業(yè)要求的長度略大一點，不再將空閑區(qū)分區(qū)分割成已分分區(qū)和空閑分區(qū)兩部分，而是將整個空閑區(qū)分配給作業(yè)。 在實現(xiàn)最佳適應(yīng)算法時，可把空閑分區(qū)按長度遞增方式登記在空閑區(qū)表中。分配時順序查找空閑表，查找到的第一個空閑區(qū)就是滿足作業(yè)要求的最小分區(qū)。這樣查找 速度快，但是為使空閑區(qū)按照長度遞增登記在空閑表中，就必須在分配回收時進行空閑區(qū)的調(diào)整。空閑區(qū)表調(diào)整時移動標模的代價要高于查詢整張表的代價，所以實 驗中不采用空閑區(qū)有序登記在空閑表中的方法。3 動態(tài)分區(qū)方式下的主存回收 動態(tài)分區(qū)方式下回收主存空間時應(yīng)該檢查是否有與歸還區(qū)相鄰的空閑區(qū)域。若有，則應(yīng)該合并成一個空閑區(qū)。一個歸還區(qū)

13、可能有上鄰空閑區(qū)，也可能有下鄰空閑區(qū)，或者既有上鄰空閑區(qū)又有下鄰空閑區(qū)，或者既無上鄰空閑區(qū)也無下鄰空閑區(qū)。 在實現(xiàn)回收時，首先將作業(yè)歸還的區(qū)域在已分配表中找到，將該欄目的狀態(tài)變?yōu)椤翱铡?，然后檢查空閑區(qū)表中標志為“未分配”欄目，查找是否又相鄰空閑區(qū)；最后合并空閑區(qū)，修改空閑區(qū)表。假定歸還作業(yè)的分區(qū)起始地址為S，長度為L，則：1） 歸還區(qū)又下鄰空閑區(qū)如果SL正好等于空閑區(qū)表中某個登記欄目（假定為第j欄）的起始地址則表明歸還區(qū)有一個下鄰空閑區(qū)。這時候只需要修改第j欄登記項的內(nèi)容： 起始地址S；第j欄長度第j欄長度L則第j欄指示的空閑區(qū)時歸還區(qū)和下鄰空閑區(qū)合并后的大空閑區(qū)。2） 歸還區(qū)又上鄰空閑區(qū)如果

14、空閑區(qū)表中某個登記欄目（假定為第k欄）的“起始地址長度”正好等于S，則表明歸還區(qū)有一個上鄰空閑區(qū)。這時要修改第k欄登記項的內(nèi)容（起始地址不變）： 第k欄長度第k欄長度L；于是第k欄指示的空閑區(qū)是歸還區(qū)和上鄰空閑區(qū)合并后的大空閑區(qū)。3） 歸還區(qū)既有上鄰空閑區(qū)又有下鄰空閑區(qū)如果SL正好等于空閑區(qū)表中某個登記欄目（假定為第j欄）的起始地址，同時還有某個登記欄目（假定為第k欄）的“起始地址長度”正好等于S，這表明歸還區(qū)既有一個上鄰空閑區(qū)又又一個下鄰空閑區(qū)。此時對空閑區(qū)的修改如下： 第k欄的長度第k欄的長度第j欄的長度L；（第k 欄的起始地址不變） 第j欄的狀態(tài)“空”（將第j欄的登記項刪除） 這樣，第k

15、欄指示的空閑區(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ū)。 由于是實驗，沒有真正的主存要分配，所有在實驗中，首先應(yīng)建立一張空閑區(qū)表，初始狀態(tài)只有一個空閑登記項（假定的主存空閑區(qū)）和一張所有狀態(tài)都為“空”的 已分配區(qū)表，假定主存空間1

16、00KB，全部為空閑區(qū)（實際上操作系統(tǒng)需要占用一部分）；然后，可以選擇進行主存分配或回收，如果是分配，要求輸入作業(yè)名和 所需主存空間大小；如果是回收，輸入回收作業(yè)名；循環(huán)進行主存分配和回收后，如果需要，則顯示兩張表的內(nèi)容，以檢查主存的分配和回收是否正確。4）實驗測試及分析：6、實驗心得體會這次實驗比較復(fù)雜，用了很多時間，但同時收獲了很多，對主存空間分配認識加深了很多附錄：源代碼#include<stdio.h>#include<stdlib.h>#define OK 1 /完成#define ERROR 0 /出錯typedef int Status;typedef s

17、truct free_table/定義一個空閑區(qū)說明表結(jié)構(gòu) int num; /分區(qū)序號 long address; /起始地址 long length; /分區(qū)大小 int state; /分區(qū)狀態(tài)ElemType;typedef struct Node/ 線性表的雙向鏈表存儲結(jié)構(gòu) ElemType data; struct Node *prior; /前趨指針 struct Node *next; /后繼指針Node,*LinkList; LinkList first; /頭結(jié)點LinkList end; /尾結(jié)點int flag;/記錄要刪除的分區(qū)序號Status Initblock()

18、/開創(chuàng)帶頭結(jié)點的內(nèi)存空間鏈表 first=(LinkList)malloc(sizeof(Node); end=(LinkList)malloc(sizeof(Node); first->prior=NULL; first->next=end; end->prior=first; end->next=NULL; end->data.num=1; end->data.address=40; end->data.length=600; end->data.state=0; return OK;void sort()/分區(qū)序號重新排序 Node *p=

19、first->next,*q; q=p->next; for(;p!=NULL;p=p->next) for(q=p->next;q;q=q->next) if(p->data.num>=q->data.num) q->data.num+=1; /顯示主存分配情況void show() int flag=0;/用來記錄分區(qū)序號 Node *p=first; p->data.num=0; p->data.address=0; p->data.length=40; p->data.state=1; sort(); pri

20、ntf("ntt主存空間分配情況n"); printf("*nn"); printf("分區(qū)序號t起始地址t分區(qū)大小t分區(qū)狀態(tài)nn"); while(p) printf("%dtt%dtt%d",p->data.num,p->data.address,p->data.length); if(p->data.state=0) printf("tt空閑nn"); else printf("tt已分配nn"); p=p->next; printf(&q

21、uot;*nn");/首次適應(yīng)算法Status First_fit(int request) /為申請作業(yè)開辟新空間且初始化 Node *p=first->next; LinkList temp=(LinkList)malloc(sizeof(Node); temp->data.length=request; temp->data.state=1; p->data.num=1; while(p) if(p->data.state=0)&&(p->data.length=request) /有大小恰好合適的空閑塊 p->data

22、.state=1; return OK; break; else if(p->data.state=0) && (p->data.length>request) /有空閑塊能滿足需求且有剩余 temp->prior=p->prior; temp->next=p; temp->data.address=p->data.address; temp->data.num=p->data.num; p->prior->next=temp; p->prior=temp; p->data.address=te

23、mp->data.address+temp->data.length; p->data.length-=request; p->data.num+=1; return OK; break; p=p->next; return ERROR;/最佳適應(yīng)算法Status Best_fit(int request) int ch; /記錄最小剩余空間 Node *p=first; Node *q=NULL; /記錄最佳插入位置 LinkList temp=(LinkList)malloc(sizeof(Node); temp->data.length=request

24、; temp->data.state=1; p->data.num=1; while(p) /初始化最小空間和最佳位置 if(p->data.state=0) && (p->data.length>=request) ) if(q=NULL) q=p; ch=p->data.length-request; else if(q->data.length > p->data.length) q=p; ch=p->data.length-request; p=p->next; if(q=NULL) return ERR

25、OR;/沒有找到空閑塊 else if(q->data.length=request) q->data.state=1; return OK; else temp->prior=q->prior; temp->next=q; temp->data.address=q->data.address; temp->data.num=q->data.num; q->prior->next=temp; q->prior=temp; q->data.address+=request; q->data.length=ch;

26、q->data.num+=1; return OK; return OK;/最差適應(yīng)算法Status Worst_fit(int request) int ch; /記錄最大剩余空間 Node *p=first->next; Node *q=NULL; /記錄最佳插入位置 LinkList temp=(LinkList)malloc(sizeof(Node); temp->data.length=request; temp->data.state=1; p->data.num=1; while(p) /初始化最大空間和最佳位置 if(p->data.stat

27、e=0 && (p->data.length>=request) ) if(q=NULL) q=p; ch=p->data.length-request; else if(q->data.length < p->data.length) q=p; ch=p->data.length-request; p=p->next; if(q=NULL) return ERROR;/沒有找到空閑塊 else if(q->data.length=request) q->data.length=1; return OK; else t

28、emp->prior=q->prior; temp->next=q; temp->data.address=q->data.address; temp->data.num=q->data.num; q->prior->next=temp; q->prior=temp; q->data.address+=request; q->data.length=ch; q->data.num+=1; return OK; return OK;/分配主存Status allocation(int a) int request;/申

29、請內(nèi)存大小 printf("請輸入申請分配的主存大小(單位:KB):"); scanf("%d",&request); if(request<0 |request=0) printf("分配大小不合適，請重試！"); return ERROR; switch(a) case 1: /默認首次適應(yīng)算法 if(First_fit(request)=OK) printf("t*分配成功！*"); else printf("t*內(nèi)存不足，分配失??！*"); return OK;break;

30、 case 2: /選擇最佳適應(yīng)算法 if(Best_fit(request)=OK) printf("t*分配成功！*"); else printf("t*內(nèi)存不足，分配失??！*"); return OK; break;case 3: /選擇最差適應(yīng)算法 if(Worst_fit(request)=OK) printf("t*分配成功！*"); else printf("t*內(nèi)存不足，分配失?。?"); return OK;break; Status deal1(Node *p)/處理回收空間 Node *q=f

31、irst; for(;q!=NULL;q=q->next) if(q=p) if(q->prior->data.state=0&&q->next->data.state!=0) q->prior->data.length+=q->data.length; q->prior->next=q->next; q->next->prior=q->prior; q=q->prior; q->data.state=0; q->data.num=flag-1; if(q->prior-

32、>data.state!=0&&q->next->data.state=0) q->data.length+=q->next->data.length; q->next=q->next->next; q->next->next->prior=q; q->data.state=0; q->data.num=flag; if(q->prior->data.state=0&&q->next->data.state=0) q->prior->data.

33、length+=q->data.length; q->prior->next=q->next; q->next->prior=q->prior; q=q->prior; q->data.state=0; q->data.num=flag-1; if(q->prior->data.state!=0&&q->next->data.state!=0) q->data.state=0; return OK;Status deal2(Node *p)/處理回收空間 Node *q=first; fo

34、r(;q!=NULL;q=q->next) if(q=p) if(q->prior->data.state=0&&q->next->data.state!=0) q->prior->data.length+=q->data.length; q->prior->next=q->next; q->next->prior=q->prior; q=p->prior; q->data.state=0; q->data.num=flag-1; if(q->prior->data

35、.state!=0&&q->next->data.state=0) q->data.state=0; if(q->prior->data.state=0&&q->next->data.state=0) q->prior->data.length+=q->data.length; q->prior->next=q->next; q->next->prior=q->prior; q=q->prior; q->data.state=0; q->data.n

36、um=flag-1; if(q->prior->data.state!=0&&q->next->data.state!=0) q->data.state=0; return OK;/主存回收Status recovery(int flag) Node *p=first; for(;p!=NULL;p=p->next) if(p->data.num=flag) if(p->prior=first) if(p->next!=end)/當前P指向的下一個不是最后一個時 if(p->next->data.state=0) /與后面的空閑塊相連 p->data.length+=p->next->data.length; p->next->next->prior=p; p->next=p->next->next; p->data.state=0; p-&g