操作系統(tǒng)-主存儲器空間的分配和回收

1、_實習(xí)四主存儲器空間的分配和回收一，實習(xí)題目本實習(xí)模擬在兩種存儲管理方式下的主存分配和回收。第一題：在可變分區(qū)管理方式下采用最先適應(yīng)算法實現(xiàn)主存分配和實現(xiàn)主存回收。提示 ：可變分區(qū)方式是按作業(yè)需要的主存空間大小來分割分區(qū)的。當(dāng)要裝入一個作業(yè)時，根據(jù)作業(yè)需要的主存量查看是否有足夠的空閑空間，若有，則按需要量分割一個分區(qū)分配給該作業(yè)；若無，則作業(yè)不能裝入。隨著作業(yè)的裝入、撤離，主存空間被分成許多個分區(qū)，有的分區(qū)被作業(yè)占用，而有的分區(qū)是空閑的。例如：05k操作系統(tǒng)10k14k作業(yè) 126k32k作業(yè) 3空閑區(qū)128k作業(yè) 2空閑區(qū)為了說明哪些區(qū)是空閑的，可以用來裝入新作業(yè)，必須要有一張空閑區(qū)說明表，

2、格式如精品資料_下：起址長度狀態(tài)第一欄14 K12 K未 分 配第二欄32 K96 K未 分 配空 表 目空 表 目其中，起址指出一個空閑區(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)為“空表目”的登記欄目，否則造成表格“溢出”無法登記。上述的這張說明表的登記情況

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

4、作業(yè)的需要量，查空閑區(qū)說明表，順序查看登記欄，找到第一個能滿足要求的空閑區(qū)。當(dāng)空閑區(qū)大于需要量時，一部分用來裝入作業(yè)，另一部分仍為空閑區(qū)登記在空閑區(qū)說明表中。由于本實習(xí)是模擬主存的分配，所以把主存區(qū)分配給作業(yè)后并不實際啟動裝入程序裝入作業(yè)，而用輸出“分配情況”來代替。最先適應(yīng)分配算法如圖4-1 。(4) 當(dāng)一個作業(yè)執(zhí)行結(jié)束撤離時，作業(yè)所占的區(qū)域應(yīng)該歸還，歸還的區(qū)域如果與其它空閑區(qū)相鄰，則應(yīng)合成一個較大的空閑區(qū)，登記在空閑區(qū)說明表中。例如，在提示（1）中列舉的情況下，如果作業(yè)2 撤離，歸還所占主存區(qū)域時，應(yīng)與上、下相鄰的空閑區(qū)一起合成一個大的空閑區(qū)登記在空閑區(qū)說明表中。歸還主存時的回收算法如圖4

5、-2 。(5)請按最先適應(yīng)算法設(shè)計主存分配和回收的程序。然后按（1 ）中假設(shè)主存中已裝入三個作業(yè)，且形成兩個空閑區(qū)，確定空閑區(qū)說明表的初值?，F(xiàn)有一個需要主存量為6K 的作業(yè) 4 申請裝入主存；然后作業(yè) 3 撤離；再作業(yè) 2 撤離。請你為它們進(jìn)行主存分配和回收，把空閑區(qū)說明表的初值以及每次分配或回收后的變化顯示出來或打印出來。二，本實驗用到的一些數(shù)據(jù)結(jié)構(gòu)有：typedef struct NODEchar name;/ 名稱float start;/ 起始位置float end;/ 大小精品資料_int flag;/ 是否分配的標(biāo)志NODE;NODE OSCOUNT;/數(shù)組三，流程圖開始初始化申請

6、釋放提出請求找 到 合否否釋放是否適大小正確是是結(jié)束進(jìn)行分配修改標(biāo)志位四，源代碼#include <stdio.h>#include<math.h>#define COUNT 512typedef struct NODEchar name;/ 名稱float start;/ 起始位置float end;/ 大小int flag;/ 是否分配的標(biāo)志精品資料_NODE;NODE OSCOUNT;/數(shù)組int count;/ 被分成的塊數(shù)統(tǒng)計int applyfree;float numb;char c;/先對數(shù)組進(jìn)行初始化，使沒有分配的名稱為Pvoid init()coun

7、t=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;i>m+1;i-)OSi=OSi-1;OSm.start =st;OSm.end=en;/移動操作，即對數(shù)組的刪除操作void move(int m)int i;for(i=m;i<count-1;i+)OSi=OSi+1;count-;/如果相鄰塊都沒有分配，則要合并到一起void rremove(int m,fl

8、oat 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;printf(" 名稱標(biāo)識 起址 長度 狀態(tài) n");for(i=0;i<c

9、ount;i+)if(OSi.flag )printf("P");elseprintf("%c ",OS );printf("%d %1.0f%1.0f",i,OSi.start ,OSi.end );if(OSi.flag )printf(" 未分配 n");elseprintf(" 已分配 n");/從鍵盤輸入數(shù)據(jù)void putin()printf(" 請輸入申請或者釋放的進(jìn)程名稱及資源數(shù)量：n");rewind(stdin);scanf("%c&

10、quot;,&c);scanf("%d",&applyfree);scanf("%f",&numb);int apply()int i=0;int applyflag=0;int freeflag=0;if(applyfree)/ 提出申請資源while(!applyflag&&i<count)if(OSi.end >=numb&&OSi.flag )if(OSi.end =numb)OS =c;OSi.flag =0;elseinsert(i+1,OSi.start +nu

11、mb,OSi.end -numb);OSi+1.flag =1;精品資料_OSi+1.name ='P'OSi.start =OSi.start ;OS =c;OSi.end =numb;OSi.flag =0;applyflag=1;i+;if(applyflag)printf(" 申請成功！ n");return 1;elseprintf(" 申請失??！沒有足夠大的空閑空間。n");return 0;else/ 提出釋放資源while(!freeflag&&i<count)if(OS =c

12、)if(OSi.end =numb)rremove(i,OSi.start ,OSi.end );elseif(OSi.end >numb)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 );elseprintf(" 釋放失敗，因為正使用的數(shù)量小于要求釋放的數(shù)量。n");return 0;freeflag=1;i+;if(

13、freeflag)精品資料_printf(" 釋放成功！ n");return 1;elseprintf(" 釋放失??！未找到匹配的進(jìn)程名稱。n");return 0;void main()init();show();while(1)putin();apply();show();五，執(zhí)行結(jié)果空閑區(qū)說明表的初始狀態(tài)作業(yè) 4 的申請量以及為作業(yè)4 分配后的空閑區(qū)說明表狀態(tài)精品資料_作業(yè) 3 和作業(yè) 2 的歸還量以及回收作業(yè)3 ，作業(yè) 2 所占主存后的空閑區(qū)說明表精品資料_第二題 ：在分頁式管理方式下采用位示圖來表示主存分配情況，實現(xiàn)主存空間的分配和回收。提示

14、 ：(1) 分頁式存儲器把主存分成大小相等的若干塊，作業(yè)的信息也按塊的大小分頁，作業(yè)裝入主存時可把作業(yè)的信息按頁分散存放在主存的空閑塊中， 為了說明主存中哪些塊已經(jīng)被占用， 哪些塊是尚未分配的空閑塊， 可用一張位示圖來指出。 位示圖可由若干存儲單元來構(gòu)成，其中每一位與一個物理塊對應(yīng)，用0/1 表示對應(yīng)塊為空閑/已占用。(2) 假設(shè)某系統(tǒng)的主存被分成大小相等的64 塊，則位示圖可用 8 個字節(jié)來構(gòu)成，另用一單元記錄當(dāng)前空閑塊數(shù)。如果已有第 0 ， 1， 4，5 ， 6 ，9 ， 11， 13， 24， 31，共 10 個主存塊被占用了，那么位示圖情況如下：精品資料_字位節(jié)數(shù)01234567號01

15、1001110101010100200000000310000001400000000500000000600000000700000000圖 4-1最先適應(yīng)分配模擬算法精品資料_圖 4-2 主存回收算法(3) 當(dāng)要裝入一個作業(yè)時，根據(jù)作業(yè)對主存的需要量，先查當(dāng)前空閑塊數(shù)是否能滿足作業(yè)要求，若不能滿足則輸出分配不成功。若能滿足，則查位示圖，找出為“0”的一些位，置上占用標(biāo)志“1，” 從“當(dāng)前空閑塊數(shù)”中減去本次占用塊數(shù)。按找到的計算出對應(yīng)的塊號，其計算公式為：塊號 = j8+i其中， j 表示找到的是第n 個字節(jié)， I 表示對應(yīng)的是第n 位。根據(jù)分配給作業(yè)的塊號，為作業(yè)建立一張頁表，頁表格式：

16、頁號塊號012精品資料_(4) 當(dāng)一個作業(yè)執(zhí)行結(jié)束，歸還主存時，根據(jù)該作業(yè)的頁表可以知道應(yīng)歸還的塊號，由塊號可計算出在位示圖中的對應(yīng)位置， 把對應(yīng)位的占用標(biāo)志清成“ 0，”表示對應(yīng)的塊已成為空閑塊。歸還的塊數(shù)加入到當(dāng)前空閑塊數(shù)中。由塊號計算在位示圖中的位置的公式如下：字節(jié)號j= 塊號 /8（ 表示取整）位數(shù)i= 塊號 /8（ 表示取余）(5)設(shè)計實現(xiàn)主存分配和回收的程序。假定位示圖的初始狀態(tài)如（2）所述，現(xiàn)有一信息量為5 頁的作業(yè)要裝入，運(yùn)行你所設(shè)計的分配程序，為作業(yè)分配主存且建立頁表（格式如（ 3）所述）。然后假定有另一作業(yè)執(zhí)行結(jié)束，它占用的塊號為第4，5 ，6 和 31 塊，運(yùn)行你所設(shè)計的

17、回收程序，收回作業(yè)歸還的主存塊。要求能顯示和打印分配或回收前后的位示圖和當(dāng)前空閑塊數(shù)，對完成一次分配后還要顯示或打印為作業(yè)建立的頁表。二，源代碼#include<stdio.h>#define N 64/物理塊數(shù)#define M 100000/最多輸入文件數(shù)struct file/ 文件結(jié)構(gòu)體，包含文件號，文件頁長，頁號，幾頁號對應(yīng)的塊號int filenum;int yechang;精品資料_int yenum;int kuainum;struct file flN;/文件結(jié)構(gòu)體數(shù)組void put(int a88)/ 輸出位示圖int i,j;for(i=0;i<8;i

18、+)for(j=0;j<8;j+)printf("t%d",aij);printf("n");void huishou(int a88,int b)/ 回收規(guī)定的頁面int c4=4,5,6,31;int i,j,k,empty;int h4;for(k=0;k<4;k+)精品資料_hk=ck;i=ck/8;j=ck%8;aij=0;printf("n 需要回收的頁號和塊號分別為:n");printf(" 頁號 t 塊號 n");for(k=0;k<4;k+)printf("%dt%dn

19、",k,hk);printf(" 回收后的頁表位示圖為:n");put(a);empty=0;for(i=0;i<8;i+)for(j=0;j<8;j+)if(aij=1)empty+=1;精品資料_empty=64-empty;printf(" 剩余的塊數(shù) :%dn",empty);void shixian(int a88,int b)/ 實現(xiàn)存儲空間的分配與回收int i,j,k,x,y,m,empty,full,fileshu,kuainum,hN,gNN;int cishu=0,hang=0,lie=0,filenum=0,

20、wenjianshu=0;int pM=-1;int jian=0;empty=b;beg:printf(" 請輸入需要裝入的文件的頁數(shù):");scanf("%d",&m);printf("n");cishu=0;if(empty<m)printf(" 需要裝入的頁數(shù)大于頁表中的空閑頁數(shù)，分配失敗n");elsewenjianshu+=1;精品資料_for(i=1;i<=wenjianshu;i+)if(fli.yechang=0)filenum=i;elsefilenum+=1;hfilenu

21、m=m;flfilenum.filenum=filenum;for(i=0;i<m;i+)flfilenum.yenum=i;for(i=0;i<8;i+)for(j=0;j<8;j+)if(aij=0)aij=1;kuainum=i*8+j;cishu+=1;精品資料_flfilenum.yenum=cishu;flfilenum.kuainum=kuainum;gfilenumcishu=kuainum;if(cishu>=m)break;if(cishu>=m)break;flfilenum.yechang=m;printf(" 文件號 :%dt

22、文件頁長 :%dn",flfilenum.filenum,flfilenum.yechang);printf(" 頁號 t 塊號 n");for(i=0;i<m;i+)printf("%dt",flfilenum.yenum-m+i);printf("%dn",gfilenumi+1);full=0;for(i=0;i<8;i+)精品資料_for(j=0;j<8;j+)if(aij=1)full+=1;empty=64-full;printf(" 剩余的塊數(shù) :%dn",empty);p

23、rintf(" 分配后的頁表位示圖為:n");put(a);printf(" 繼續(xù)裝入文件請輸入1，回收頁面請輸入2，輸入其他鍵結(jié)束:");scanf("%d",&y);if(y=1)goto beg;else if(y=2)goto aeg;elsegoto end;aeg:printf(" 請輸入需要回收的文件號大于0 且不在下列數(shù)集中的數(shù)-t");精品資料_for(i=1;i<=jian;i+)if(pjian!=-1)printf("%dt",pjian);printf("n 輸入的需要回收的頁數(shù)為:");scanf("%d",&fileshu);if(wenjianshu<fileshu)printf(" 你輸入的文件號不存在!n");if(fileshu<=0)printf(" 你輸入的文件號不存在!n");elsek=gfilesh