操作系統(tǒng)實(shí)驗(yàn) 可變分區(qū)內(nèi)存分配首次適應(yīng)算法模擬

1、 題 目 可變分區(qū)內(nèi)存分配首次適應(yīng)算法模擬 姓 名： 學(xué) 號： 專 業(yè)： 學(xué) 院： 指導(dǎo)教師： 林夕 二零一八 年 十一月一、實(shí)驗(yàn)?zāi)康闹鞔娴姆峙浜突厥盏膶?shí)現(xiàn)與主存儲器的管理方式有關(guān)的，通過本實(shí)驗(yàn)幫助學(xué)生理解在可變分區(qū)管理方式下應(yīng)怎樣實(shí)現(xiàn)主存空間的分配和回收。二、實(shí)驗(yàn)內(nèi)容及原理編寫一個內(nèi)存動態(tài)分區(qū)分配模擬程序，模擬內(nèi)存的分配和回收的完整過程。模擬在可變分區(qū)管理方式下采用最先適應(yīng)算法實(shí)現(xiàn)主存分配和回收。 可變分區(qū)方式是按作業(yè)需要的主存空間大小來分割分區(qū)的。當(dāng)要裝入一個作業(yè)時，根據(jù)作業(yè)需要的主存量查看是否有足夠的空閑空間，若有，則按需要量分割一個分區(qū)分配給該作業(yè)；若無，則作業(yè)不能裝入。隨著作業(yè)的裝入

2、、撤離，主存空間被分成許多個分區(qū)，有的分區(qū)被作業(yè)占用，而有的分區(qū)是空閑的。當(dāng)進(jìn)程運(yùn)行完畢釋放內(nèi)存，系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)鏈表中找到相應(yīng)的插入點(diǎn)，此時可能出現(xiàn)以下4種情況之一：1.回收區(qū)與插入點(diǎn)的前一個空閑分區(qū)F1相鄰接，此時將兩個分區(qū)合并2.回收區(qū)與插入點(diǎn)的后一個空閑分區(qū)F2相鄰接，此時將兩個分區(qū)合并3.回收區(qū)與插入點(diǎn)的前，后兩個空閑分區(qū)相鄰接，此時將三個分區(qū)合并4.回收區(qū)既不與F1相鄰接，又不與F2相鄰接，此時應(yīng)為回收區(qū)單獨(dú)建立一個新表項三、程序設(shè)計1.算法流程3.詳細(xì)設(shè)計（1）定義兩個結(jié)構(gòu)體struct kongxian /空閑分區(qū)int start; /起址int end; /結(jié)

3、束int length; /長度kongxianN;struct zuoye /作業(yè)分區(qū)int start; /起址int end; /結(jié)束int length; /長度zuoyeN;（2）init() /初始化函數(shù)kongxian 結(jié)構(gòu)體為 0 1023 1024 print1() /打印空閑分區(qū) print2() /打印作業(yè)分區(qū)main（）中具體實(shí)現(xiàn)算法：printf("請輸入作業(yè)的占用空間的長度 ");scanf("%d",&len);flag=0;for(i=0;i<n1;i+)if(kongxiani.length>=len

4、) /首次適應(yīng)算法flag=1;break;if(!flag)printf("內(nèi)存分配失敗n");else/將該作業(yè)加入作業(yè)區(qū)里zuoyen2.start=kongxiani.start;zuoyen2.end=zuoyen2.start+len;zuoyen2.length=len;n2+; /作業(yè)數(shù)加1if(kongxiani.length=len) /該分區(qū)全部用于分配，刪除該空閑分區(qū)for(j=i;j<n1-1;j+)kongxianj.start=kongxianj+1.start;kongxianj.end=kongxianj+1.end;kongxian

5、j.length=kongxianj+1.length;n1-;else /該空閑分區(qū)部分用于分配，剩余的留在空閑分區(qū)中kongxiani.start+=len;kongxiani.length-=len;（3）回收作業(yè)：printf("輸入要回收的作業(yè)ID "); scanf("%d",&id);front=middle=behind=0;for(i=0;i<n1;i+)if(kongxiani.start>zuoyeid.end)break;if(kongxiani.end=zuoyeid.start) /待回收的作業(yè)上面有空閑分

6、區(qū)front=1;t1=i;if(kongxiani.start=zuoyeid.end) /待回收的作業(yè)下面有空閑分區(qū)behind=1;t2=i;四、實(shí)驗(yàn)結(jié)果五、實(shí)驗(yàn)小結(jié)在設(shè)計的過程中，有很多問題不是很清楚，所以做起來就就很困難，剛開始的時候都有點(diǎn)無從下手的感覺。很多時候在遇到問題時，基本知識都了解，但是就不知道怎么才能把它們都整合到一塊，也就是說知識都是很零散的，沒有一個完整的系統(tǒng)。而且，又由于基礎(chǔ)知識不牢固，使得我在這次的課程設(shè)計中感到更加力不從心。在設(shè)計的過程中，每走一步就會發(fā)現(xiàn)，思路想出來很容易，但涉及到實(shí)現(xiàn)的時候，總是有點(diǎn)手無足措。對于本次的課程設(shè)計，里面還有很多需要改進(jìn)的地方。一

7、個程序的順利出爐，少不了反復(fù)地調(diào)試和修改。在調(diào)試的過程中，總是會發(fā)生很多錯誤，但在解決這些錯誤的時候，開始很模糊的概念就會變得越來越清晰。其實(shí)很多錯誤都是很類似的，只要解決了一個，其余的就會迎刃而解了。#include<stdio.h>#include<string.h>#include<stdlib.h>#include<math.h>#define N 10000int n1;/空閑分區(qū)的個數(shù)int n2;/作業(yè)區(qū)的個數(shù)struct kongxianint start; /起址int end; /結(jié)束int length; /長度kongxi

8、anN;struct zuoyeint start; /起址int end; /結(jié)束int length; /長度zuoyeN;int cmp1(const void *a,const void *b)return (*(struct kongxian *)a).start-(*(struct kongxian *)b).start;int cmp2(const void *a,const void *b)return (*(struct zuoye *)a).start-(*(struct zuoye *)b).start;void init()n1=1; /初始時只有一個空閑區(qū)n2=0;

9、/初始沒有作業(yè)kongxian0.start=0;kongxian0.end=1023;kongxian0.length=1024;void print1() /打印空閑分區(qū)int i;for(i=0;i<n1;i+)printf("空閑分區(qū)ID:%d 起止:%d 結(jié)束:%d 長度:%dn",i,kongxiani.start,kongxiani.end,kongxiani.length);void print2() /打印作業(yè)分區(qū)int i;for(i=0;i<n2;i+)printf("作業(yè)分區(qū)ID：%d 起止:%d 結(jié)束:%d 長度:%dn&qu

10、ot;,i,zuoyei.start,zuoyei.end,zuoyei.length);int main()int i,j,k,t,len,flag,id;int front,middle, behind;int t1,t2;init();print1();printf("輸入1裝入新作業(yè)，輸入0回收作業(yè)，輸入-1結(jié)束n");while(scanf("%d",&t)!=EOF)if(t=1) /裝入新作業(yè)printf("請輸入作業(yè)的占用空間的長度 ");scanf("%d",&len);flag=

11、0;for(i=0;i<n1;i+)if(kongxiani.length>=len) /首次適應(yīng)算法flag=1;break;if(!flag)printf("內(nèi)存分配失敗n");else/將該作業(yè)加入作業(yè)區(qū)里zuoyen2.start=kongxiani.start;zuoyen2.end=zuoyen2.start+len;zuoyen2.length=len;n2+; /作業(yè)數(shù)加1if(kongxiani.length=len) /該分區(qū)全部用于分配，刪除該空閑分區(qū)for(j=i;j<n1-1;j+)kongxianj.start=kongxian

12、j+1.start;kongxianj.end=kongxianj+1.end;kongxianj.length=kongxianj+1.length;n1-;else /該空閑分區(qū)部分用于分配，剩余的留在空閑分區(qū)中kongxiani.start+=len;kongxiani.length-=len;else if(t=0)printf("輸入要回收的作業(yè)ID "); scanf("%d",&id);front=middle=behind=0;for(i=0;i<n1;i+)if(kongxiani.start>zuoyeid.end

13、)break;if(kongxiani.end=zuoyeid.start) /待回收的作業(yè)上面有空閑分區(qū)front=1;t1=i;if(kongxiani.start=zuoyeid.end) /待回收的作業(yè)下面有空閑分區(qū)behind=1;t2=i;if(!front&&!behind) /待回收的作業(yè)上下均沒有空閑分區(qū) kongxiann1.start=zuoyeid.start;kongxiann1.end=zuoyeid.end;kongxiann1.length=zuoyeid.length;n1+; /空閑分區(qū)增加一個qsort(kongxian,n1,sizeof

14、(struct kongxian),cmp1); /插入空閑分區(qū)后排序for(j=id;j<n2-1;j+) /在作業(yè)分區(qū)中刪除該作業(yè)zuoyej.start=zuoyej+1.start;zuoyej.end=zuoyej+1.end;zuoyej.length=zuoyej+1.length; n2-;if(front &&behind) /待回收的作業(yè)上下均有空閑分區(qū)middle=1;if(front&&!middle) /合并待回收的作業(yè)和上面的空閑分區(qū)kongxiant1.end+=zuoyeid.length;kongxiant1.length

15、+=zuoyeid.length;for(j=id;j<n2-1;j+) /在作業(yè)分區(qū)中刪除該作業(yè)zuoyej.start=zuoyej+1.start;zuoyej.end=zuoyej+1.end;zuoyej.length=zuoyej+1.length; n2-;if(middle) /合并待回收的作業(yè)和上下的空閑分區(qū)kongxiant1.end=kongxiant2.end;kongxiant1.length+=(zuoyeid.length+kongxiant2.length);/刪除空閑分區(qū)t2for(j=t2;j<n1-1;j+)kongxianj.start=kongxianj+1.start;kongxianj.end=kongxianj+1.end;kongxianj.length=kongxianj+1.length;n1-;for(j=id;j<n2-1;j+) /在作業(yè)分區(qū)中刪除該作業(yè)zuoyej.start=zuoyej+1.start;zuoyej.end=zuoyej+1.end;zuoyej.length=zuoyej+1.length; n2-; if(behind &&!middle) /合并待回收的作業(yè)和下面的分區(qū)kongx