操作系統(tǒng)實(shí)驗(yàn)—動(dòng)態(tài)分區(qū)分配算法

1、操作系統(tǒng)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)2 動(dòng)態(tài)分區(qū)分配算法報(bào)告日期：2016-6-15姓 名：學(xué) 號(hào)：班 級(jí)：任課教師：實(shí)驗(yàn)2 動(dòng)態(tài)分區(qū)分配算法一、實(shí)驗(yàn)內(nèi)容編寫(xiě)一個(gè)內(nèi)存動(dòng)態(tài)分區(qū)分配模擬程序，模擬內(nèi)存的分配和回收的完整過(guò)程。二、實(shí)驗(yàn)?zāi)康囊粋€(gè)好的計(jì)算機(jī)系統(tǒng)不僅要有一個(gè)足夠容量的、存取速度高的、穩(wěn)定可靠的主存儲(chǔ)器，而且要能合理地分配和使用這些存儲(chǔ)空間。當(dāng)用戶提出申請(qǐng)存儲(chǔ)器空間時(shí)，存儲(chǔ)管理必須根據(jù)申請(qǐng)者的要求，按一定的策略分析主存空間的使用情況，找出足夠的空閑區(qū)域分配給申請(qǐng)者。當(dāng)作業(yè)撤離或主動(dòng)歸還主存資源時(shí)，則存儲(chǔ)管理要收回作業(yè)占用的主存空間或歸還部分主存空間。主存的分配和回收的實(shí)現(xiàn)與主存儲(chǔ)器的管理方式有關(guān)的，通過(guò)本實(shí)

2、驗(yàn)幫助學(xué)生理解在可變分區(qū)管理方式下應(yīng)怎樣實(shí)現(xiàn)主存空間的分配和回收。三、實(shí)驗(yàn)原理模擬在可變分區(qū)管理方式下采用最先適應(yīng)算法實(shí)現(xiàn)主存分配和回收。(1)可變分區(qū)方式是按作業(yè)需要的主存空間大小來(lái)分割分區(qū)的。當(dāng)要裝入一個(gè)作業(yè)時(shí)，根據(jù)作業(yè)需要的主存量查看是否有足夠的空閑空間，若有，則按需要量分割一個(gè)分區(qū)分配給該作業(yè)；若無(wú)，則作業(yè)不能裝入。隨著作業(yè)的裝入、撤離，主存空間被分成許多個(gè)分區(qū)，有的分區(qū)被作業(yè)占用，而有的分區(qū)是空閑的。例如：05k10k14k26k32k512k操作系統(tǒng)作業(yè)1作業(yè)3空閑區(qū)作業(yè)2空閑區(qū)為了說(shuō)明哪些區(qū)是空閑的，可以用來(lái)裝入新作業(yè)，必須要有一張空閑區(qū)說(shuō)明表，格式如下：起 址長(zhǎng) 度狀 態(tài)第一欄

3、14 K12 K未 分 配第二欄32 K96 K未 分 配MMMM其中，起址指出一個(gè)空閑區(qū)的主存起始地址。 長(zhǎng)度指出從起始地址開(kāi)始的一個(gè)連續(xù)空閑的長(zhǎng)度。 狀態(tài)有兩種狀態(tài)，一種是“未分配”狀態(tài)，指出對(duì)應(yīng)的由起址指出的某個(gè)長(zhǎng)度的區(qū)域是空閑區(qū)。 (2) 當(dāng)有一個(gè)新作業(yè)要求裝入主存時(shí)，必須查空閑區(qū)說(shuō)明表，從中找出一個(gè)足夠大的空閑區(qū)。有時(shí)找到的空閑區(qū)可能大于作業(yè)需要量，這時(shí)應(yīng)把原來(lái)的空閑區(qū)變成兩部分：一部分分給作業(yè)占用；另一部分又成為一個(gè)較小的空閑區(qū)。為了盡量減少由于分割造成的空閑區(qū)，而盡量保存高地址部分有較大的連續(xù)空閑區(qū)域，以利于大型作業(yè)的裝入。為此，在空閑區(qū)說(shuō)明表中，把每個(gè)空閑區(qū)按其地址順序登記，即

4、每個(gè)后繼的空閑區(qū)其起始地址總是比前者大。(3) 采用最先適應(yīng)算法（順序分配算法）分配主存空間。按照作業(yè)的需要量，查空閑區(qū)說(shuō)明表，順序查看登記欄，找到第一個(gè)能滿足要求的空閑區(qū)。當(dāng)空閑區(qū)大于需要量時(shí)，一部分用來(lái)裝入作業(yè)，另一部分仍為空閑區(qū)登記在空閑區(qū)說(shuō)明表中。由于本實(shí)驗(yàn)是模擬主存的分配，所以把主存區(qū)分配給作業(yè)后并不實(shí)際啟動(dòng)裝入程序裝入作業(yè)，而用輸出“分配情況”來(lái)代替。(4) 當(dāng)一個(gè)作業(yè)執(zhí)行結(jié)束撤離時(shí)，作業(yè)所占的區(qū)域應(yīng)該歸還，歸還的區(qū)域如果與其它空閑區(qū)相鄰，則應(yīng)合成一個(gè)較大的空閑區(qū)，登記在空閑區(qū)說(shuō)明表中。(5) 請(qǐng)按最先適應(yīng)算法設(shè)計(jì)主存分配和回收的程序。假設(shè)初始時(shí)主存中沒(méi)有作業(yè)，現(xiàn)按下面序列進(jìn)行內(nèi)存

5、的申請(qǐng)與釋放：作業(yè)1申請(qǐng)300K，作業(yè)2申請(qǐng)100K，作業(yè)1釋放300K，作業(yè)3申請(qǐng)150K，作業(yè)4申請(qǐng)30K， 作業(yè)5申請(qǐng)40K， 作業(yè)6申請(qǐng)60K， 作業(yè)4釋放30K。 請(qǐng)你為它們進(jìn)行主存分配和回收，把空閑區(qū)說(shuō)明表的初值以及每次分配或回收后的變化顯示出來(lái)或打印出來(lái)。四、實(shí)驗(yàn)報(bào)告1. 畫(huà)出算法流程圖。2. 源代碼#define _CRT_SECURE_NO_WARNINGS 1 #include#include#include#include#define N 10000int n1;/空閑分區(qū)的個(gè)數(shù)int n2;/作業(yè)區(qū)的個(gè)數(shù)struct kongxianint start; /起址int

6、 end; /結(jié)束int length; /長(zhǎng)度kongxianN;struct zuoyeint start; /起址int end; /結(jié)束int length; /長(zhǎng)度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).star

7、t;void init()n1 = 1; /初始時(shí)只有一個(gè)空閑區(qū)n2 = 0; /初始沒(méi)有作業(yè)kongxian0.start = 0;kongxian0.end = 511;kongxian0.length = 512;void print1() /打印空閑分區(qū)int i;for (i = 0; in1; i+)printf(空閑分區(qū)ID:%d 起止:%d 結(jié)束:%d 長(zhǎng)度:%dn, i, kongxiani.start, kongxiani.end, kongxiani.length);void print2() /打印作業(yè)分區(qū)int i;for (i = 0; in2; i+)printf

8、(作業(yè)分區(qū)ID：%d 起止:%d 結(jié)束:%d 長(zhǎng)度:%dn, i, zuoyei.start, zuoyei.end, zuoyei.length);int main()int i, j, 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(請(qǐng)輸入作業(yè)的占用空間的長(zhǎng)度 );scanf(%d, &len);flag = 0;for (i =

9、0; i= 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; jn1 - 1; j+)kongxianj.start = kongxianj + 1.start;kongxianj.end = kong

10、xianj + 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; izuoyeid.end)break;if (kongxiani.end = zuoyeid.start) /待回收的作業(yè)上面有空閑分區(qū)front = 1

11、;t1 = i;if (kongxiani.start = zuoyeid.end) /待回收的作業(yè)下面有空閑分區(qū)behind = 1;t2 = i;if (!front&!behind) /待回收的作業(yè)上下均沒(méi)有空閑分區(qū)kongxiann1.start = zuoyeid.start;kongxiann1.end = zuoyeid.end;kongxiann1.length = zuoyeid.length;n1+; /空閑分區(qū)增加一個(gè)qsort(kongxian, n1, sizeof(struct kongxian), cmp1); /插入空閑分區(qū)后排序for (j = id; jn2

12、 - 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 += zuoyeid.length;for (j = id; jn2 - 1; j+) /在作業(yè)

13、分區(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; jn1 - 1; j+)kongxianj.start = kongxianj + 1.start;kon

14、gxianj.end = kongxianj + 1.end;kongxianj.length = kongxianj + 1.length;n1-;for (j = id; jn2 - 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ū)kongxiant2.start -= zuoyeid.length;kongxiant2.length += zuoyeid.length;for (j = id; jn2 - 1; j+) /在作業(yè)分區(qū)中刪除該作業(yè)zuoyej.start = zuoyej + 1.start;zuoyej.end = zuoyej + 1.end;zuoyej.length = zuoyej + 1.length;n2-;elseprintf(操作結(jié)束n);break;print1();pr