操作系統(tǒng)實驗 可變分區(qū)內存分配首次適應算法模擬參考模板

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

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

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

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

5、ngxianj.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;四、實驗結果五、實驗小結在設計的過程中，有很多問題不是很清楚，所以做起來就就很困難，剛開始的時候都有點無從下手的感覺。很多時候在遇到問題時，基本知識都了解，但是就不知道怎么才能把它們都整合到一塊，也就是說知識都是很零散的，沒有一個完整的系統(tǒng)。而且，又由于基礎知識不牢固，使得我在這次的課程設計中感到更加力不從心。在設計的過程中，每走一步就會發(fā)現，思路想出來很容易，但涉及到實現的時候，總是有點手無足措。對于本次的課程設計，里面還有很多需要改

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

8、kongxianN;struct zuoyeint start; /起址int end; /結束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ū)

9、n2=0; /初始沒有作業(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 結束:%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 結束:%d 長度:

10、%dn",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結束n");while(scanf("%d",&t)!=EOF)if(t=1) /裝入新作業(yè)printf("請輸入作業(yè)的占用空間的長度 ");scanf("%d",&len)

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

12、ngxianj+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>zuoye

13、id.end)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,

14、sizeof(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.

15、length+=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