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

1、實(shí)習(xí)四主存儲(chǔ)器空間的分配和回收一，實(shí)習(xí)題目本實(shí)習(xí)模擬在兩種存儲(chǔ)管理方式下的主存分配和回收。第一題：在可變分區(qū)管理方式下采用最先適應(yīng)算法實(shí)現(xiàn)主存分配和實(shí)現(xiàn)主存回收。提示:可變分區(qū)方式是按作業(yè)需要的主存空間大小來(lái)分割分區(qū)的。當(dāng)要裝入一個(gè)作業(yè)時(shí)，根據(jù)作業(yè)需要的主存量查看是否有足夠的空閑空間，若有，則按需要量分割一個(gè)分區(qū)分配給該作業(yè)；若無(wú)，則作業(yè)不能裝入。隨著作業(yè)的裝入、撤離，主存空間被分成許多個(gè)分區(qū)，有的分 區(qū)被作業(yè)占用，而有的分區(qū)是空閑的。例如：為了說(shuō)明哪些區(qū)是空閑的,可以用來(lái)裝入新作業(yè),必須要有一張空閑區(qū)說(shuō)明表,格式如下:第一欄第二欄起址長(zhǎng)度狀態(tài)14 K12 K未分配32 K96 K未分配空表目

2、空表目其中，起址一一指出個(gè)空閑區(qū)的主存起始地址。長(zhǎng)度指出從起始地址開始的一個(gè)連續(xù)空閑的長(zhǎng)度。狀態(tài)一一有兩種狀態(tài)，一種是“未分配”狀態(tài)，指出對(duì)應(yīng)的由起址指出的某個(gè)長(zhǎng)度的區(qū)域是空閑區(qū)；另一種是“空表目”狀態(tài)，表示表中對(duì)應(yīng)的登記項(xiàng)目是空白（無(wú)效），可用來(lái)登記新的空閑區(qū)（例如，作業(yè)撤離后，它所占的區(qū)域就成了空閑區(qū)， 應(yīng)找一個(gè)“空表目” 欄登記歸還區(qū)的起址和長(zhǎng)度且修改狀態(tài)）。由于分區(qū)的個(gè)數(shù)不定，所以空閑區(qū)說(shuō)明表中應(yīng)有適量的狀態(tài)為“空表目”的登記欄目，否則造成表格“溢出”無(wú)法登記。上述的這張說(shuō)明表的登記情況是按提示（1）中的例所裝入的三個(gè)作業(yè)占用的主存區(qū)域后填寫的。（2）當(dāng)有一個(gè)新作業(yè)要求裝入主存時(shí)，必須

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

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

5、個(gè)空閑區(qū)，確定空閑區(qū)說(shuō)明表的初值?，F(xiàn)有一個(gè)需要主存量為6K的作業(yè)4申請(qǐng)裝入主存；然后作業(yè)3撤離；再作業(yè)2撤離。請(qǐng)你為它們進(jìn)行主存分配和回收，把空閑區(qū)說(shuō)明表的初值以及每次分配或回收后的變化顯示出來(lái)或打印出來(lái)。二，本實(shí)驗(yàn)用到的一些數(shù)據(jù)結(jié)構(gòu)有：typedef struct NODEchar n ame; 名稱float start;/ 起始位置int flag;/是否分配的標(biāo)志NODE;NODE OSCOUNT; 數(shù)組三，流程圖H四，源代碼#include <stdio.h>#include<math.h>#define COUNT 512typedef struct NOD

6、Echar name;/ 名稱 float start;/ 起始位置 float end;/ 大小int flag;/是否分配的標(biāo)志NODE;NODE OSCOUNT; 數(shù)組int count;/ 被分成的塊數(shù)統(tǒng)計(jì)int applyfree;float numb;char c;/先對(duì)數(shù)組進(jìn)行初始化，使沒有分配的名稱為Pvoid init()count=1;OS0.name ='P'OSO.start =0;OS0.end =COUNT;OSO.flag =1;/對(duì)數(shù)組的插入操作void insert(int m,float st,float en)int i;count+;fo

7、r(i=count;i>m+1;i-)OSi=OSi-1;OSm.start =st;OSm.end =en;/移動(dòng)操作，即對(duì)數(shù)組的刪除操作void move(int m)int i;for(i=m;i<count-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 +

8、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)識(shí)起址長(zhǎng)度狀態(tài)n");for(i=0;i<count;i+)if(OSi.flag )printf( "P");elseprintf("%c",OS);printf("%d%1.0f%1.0f ",i,OSi.start ,OSi.end )

9、;if(OSi.flag )printf("未分配 n");elseprintf("已分配 n");/從鍵盤輸入數(shù)據(jù)void putin()printf("請(qǐng)輸入申請(qǐng)或者釋放的進(jìn)程名稱及資源數(shù)量：n");rewind(stdin);scanf("%c", &c);scanf("%d", &applyfree);scanf("%f",&numb); int apply()int i=0;int applyflag=0;int freeflag=0;if(

10、applyfree)/ 提出申請(qǐng)資源while(!applyflag &&i vcount)if(OSi.end >=numb&&OSi.flag )if(OSi.end =numb)OS =c;OSi.flag =0;elseinsert(i+1,OSi.start +numb,OSi.end -numb); OSi+1.flag =1;0Si+1.name ='P：OSi.start =OSi.start ;OS =c;OSi.end =numb;OSi.flag =0;applyflag=1;i+；if(applyfl

11、ag)printf("申請(qǐng)成功！ n");return 1;elseprintf("申請(qǐng)失??！沒有足夠大的空閑空間。n");return 0;else/提出釋放資源while(!freeflag&&i vcount)if(OS =c)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

12、;OSi.end =numb;OSi.flag =1; if(OSi-1.flag ) rremove(i,OSi.start ,OSi.end );elsen");printf("釋放失敗，因?yàn)檎褂玫臄?shù)量小于要求釋放的數(shù)量。 return 0; freeflag=1;i+;if(freeflag)printf(” 釋放成功！ n");return 1;elseprintf("釋放失敗！未找到匹配的進(jìn)程名稱。n");return 0;void main()init();show();while(1)putin();apply();show()

13、;五，執(zhí)行結(jié)果空閑區(qū)說(shuō)明表的初始狀態(tài)標(biāo)識(shí)起址長(zhǎng)度 迖裔 醫(yī)輸入申魯或者釋鐵的進(jìn)程鶉及資m ；作業(yè)4的申請(qǐng)量以及為作業(yè) 4分配后的空閑區(qū)說(shuō)明表狀態(tài)!1己己已酉酉-已 己 a3-k作業(yè)3和作業(yè)2的歸還量以及回收作業(yè) 3，作業(yè)2所占主存后的空閑區(qū)說(shuō)明表情輸入申請(qǐng)或者釋放的進(jìn)程名稱及資源數(shù)重;(10醫(yī)舉成功！ 名稱；標(biāo)識(shí)起址0 100112迪長(zhǎng)度100 12 150 巧訶酸配已亦配未券配P請(qǐng)輸入申請(qǐng)或者釋放的進(jìn)程名稱及資源數(shù)量C0150釋放成功!標(biāo)識(shí)01起址100112長(zhǎng)度1001240a b 備輸入申請(qǐng)或者釋放的進(jìn)程名稱及資源數(shù)量20靱失?。∶Q彳未脊配岸名稱 尺度 迖態(tài) la00100已壞配卜11

14、0012已分配P2112400未分酉己睛輸入申請(qǐng)或者釋放的進(jìn)程名稱及資源數(shù)量:第二題:在分頁(yè)式管理方式下采用位示圖來(lái)表示主存分配情況，實(shí)現(xiàn)主存空間的分配和回收。提示:(1) 分頁(yè)式存儲(chǔ)器把主存分成大小相等的若干塊，作業(yè)的信息也按塊的大小分頁(yè)，作業(yè)裝入主存時(shí)可把作業(yè)的信息按頁(yè)分散存放在主存的空閑塊中，為了說(shuō)明主存中哪些塊已經(jīng)被占用，哪些塊是尚未分配的空閑塊，可用一張位示圖來(lái)指出。位示圖可由若干存儲(chǔ)單元來(lái)構(gòu)成，其中每一位與一個(gè)物理塊對(duì)應(yīng)，用0/1表示對(duì)應(yīng)塊為空閑/已占用。(2) 假設(shè)某系統(tǒng)的主存被分成大小相等的64塊，則位示圖可用8個(gè)字節(jié)來(lái)構(gòu)成，另用一單元記錄當(dāng)前空閑塊數(shù)。如果已有第0, 1，4，

15、5，6，9 ,11 ,13，24，31，共10個(gè)主存塊被占用了，那么位示圖情況如下：圖4-1最先適應(yīng)分配模擬算法上邨空備黑連記 芒中隹度堆M1LVr與的述育 恵f癇的空紅X圖4-2主存回收算法(3) 當(dāng)要裝入一個(gè)作業(yè)時(shí)，根據(jù)作業(yè)對(duì)主存的需要量，先查當(dāng)前空閑塊數(shù)是否能滿足作業(yè)要求，若不能滿足則輸出分配不成功。若能滿足，則查位示圖，找出為“0”的一些位,置上占用標(biāo)志“ 1 ”，從“當(dāng)前空閑塊數(shù)”中減去本次占用塊數(shù)。按找到的計(jì)算出對(duì)應(yīng)的塊號(hào)，其計(jì)算公式為:塊號(hào)=j 8+i其中，j表示找到的是第n個(gè)字節(jié)，I表示對(duì)應(yīng)的是第n位。根據(jù)分配給作業(yè)的塊號(hào)，為作業(yè)建立一張頁(yè)表，頁(yè)表格式：頁(yè)號(hào)塊號(hào)012（4）當(dāng)一

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

17、后的位示圖和當(dāng)前空閑塊數(shù)，對(duì)完成一次分配后還要顯示或打印為作業(yè)建立的頁(yè)表。二，源代碼#in clude<stdio.h>#define N 64/物理塊數(shù)#define M 100000/最多輸入文件數(shù)struct file /文件結(jié)構(gòu)體，包含文件號(hào)，文件頁(yè)長(zhǎng)，頁(yè)號(hào)，幾頁(yè)號(hào)對(duì)應(yīng)的塊號(hào)int file num;int yecha ng;int yenum;int kua inum;；struct file flN; /文件結(jié)構(gòu)體數(shù)組void put(int a88)/ 輸出位示圖int i,j;for(i=0;i<8;i+)for( j=0;j<8;j+)prin tf(

18、"t%d",aij);prin tf("n ”);void huishou(int a88,int b)/ 回收規(guī)定的頁(yè)面int c4=4,5,6,31;int i,j,k,empty;int h4;hk=ck;i=ck/8;j=ck%8;aij=0；:n");prin tf("n需要回收的頁(yè)號(hào)和塊號(hào)分別為printf("頁(yè)號(hào) t 塊號(hào) n");for(k=0;k<4;k+)prin tf("%dt%dn",k,hk);printf("回收后的頁(yè)表位示圖為：n");put(a);

19、empty=O;for(i=0;i<8;i+)for( j=0;j<8;j+)if(ai j=1)empty+=1;empty=64-empty;printf(” 剩余的塊數(shù):%dn",empty);void shixian(int a88,int b)/實(shí)現(xiàn)存儲(chǔ)空間的分配與回收int i,j,k,x,y,m,empty,full,fileshu,kuainum,hN,gNN;int cishu=0,hang=0,lie=0,filenum=0,wenjianshu=0;in t pM=-1;int jia n=0;empty=b;beg:printf("請(qǐng)輸入

20、需要裝入的文件的頁(yè)數(shù)：”)；scan f("%d",&m);prin tf("n");cishu=0;if(empty<m)n");printf("需要裝入的頁(yè)數(shù)大于頁(yè)表中的空閑頁(yè)數(shù)，分配失敗elsewenjia nshu+=1;if(fli.yecha ng=O)file num=i;elsefile nu m+=1;hfile num=m;flfile nu m.file num=file num;for(i=0;i<m;i+)flfile nu m.ye num=i;for(i=0;i<8;i+)for

21、( j=0;j<8;j+)if(ai j=0)aij=1;kuai num=i*8+j;cishu+=1;flfile nu m.ye num=cishu;flfile nu m.kua inum=kua inum;gfile nu mcishu=kua inum;if(cishu>=m)break;if(cishu>=m)break;flfile nu m.yecha ng=m;printf(” 文件號(hào)：dt 文件頁(yè)長(zhǎng)：dn",flfilenum.filenum, flfile nu m.yecha ng);printf("頁(yè)號(hào) t 塊號(hào) n"

22、);for(i=0;i<m;i+)prin tf("%dt",flfile nu m.ye nu m-m+i);prin tf("%dn",gfile numi+1);full=0;for( j=0;j<8;j+)if(ai j=1)full+=1;empty=64-full;printf(” 剩余的塊數(shù):%dn",empty);printf(”分配后的頁(yè)表位示圖為:n");put(a);printf("繼續(xù)裝入文件請(qǐng)輸入1，回收頁(yè)面請(qǐng)輸入2，輸入其他鍵結(jié)束：”);scan f("%d", &

23、amp;y);if(y=1)goto beg;else if(y=2)goto aeg;elseaeg:goto end;printf("請(qǐng)輸入需要回收的文件號(hào)大于0且不在下列數(shù)集中的數(shù)-t");if(pjia n!=-1)prin tf("%dt",pjia n);prin tf("n輸入的需要回收的頁(yè)數(shù)為scan f("%d", &fileshu);if(wenjia nshu<fileshu)printf("你輸入的文件號(hào)不存在if(fileshu<=0)printf("你輸入的

24、文件號(hào)不存在elsek=gfileshu1;file num=fileshu;for(x=0;x<hfileshu;x+)k=gfileshux+1;i=k/8;j=k%8;aij=0;printf(”回收頁(yè)面后的頁(yè)表位示圖為!n");!n");:n");put(a);empty=O; /顯示空閑頁(yè)數(shù)for(i=0;i<8;i+)for( j=0;j<8;j+)if(ai j=1)empty+=1;empty=64-empty;printf("剩余的塊數(shù):%dn",empty);flfileshu.yecha ng=0;jia n+=1;pjia n=fileshu;