操作系統(tǒng)-存儲(chǔ)管理動(dòng)態(tài)分區(qū)分配及回收算法(附源碼)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上存儲(chǔ)管理動(dòng)態(tài)分區(qū)分配及回收算法課程名稱：計(jì)算機(jī)操作系統(tǒng) 班級(jí)：信1501-2實(shí)驗(yàn)者姓名：李琛 實(shí)驗(yàn)日期：2018年5月20日評(píng)分： 教師簽名：一、實(shí)驗(yàn)?zāi)康姆謪^(qū)管理是應(yīng)用較廣泛的一種存儲(chǔ)管理技術(shù)。本實(shí)驗(yàn)要求用一種結(jié)構(gòu)化高級(jí)語言構(gòu)造 分區(qū)描述器，編制動(dòng)態(tài)分區(qū)分配算法和回收算法模擬程序，并討論不同分配算法的特點(diǎn)。二、實(shí)驗(yàn)要求1、編寫：First Fit Algorithm 2、編寫：Best Fit Algorithm 3、編寫：空閑區(qū)回收算法三、實(shí)驗(yàn)過程（一）主程序 1、定義分區(qū)描述器 node，包括 3 個(gè)元素： （1）adr分區(qū)首地址 （2）size分區(qū)大小 （3）n

2、ext指向下一個(gè)分區(qū)的指針 2、定義 3 個(gè)指向 node 結(jié)構(gòu)的指針變量： （1）head1空閑區(qū)隊(duì)列首指針 （2）back1指向釋放區(qū) node 結(jié)構(gòu)的指針 （3）assign指向申請(qǐng)的內(nèi)存分區(qū) node 結(jié)構(gòu)的指針 3、定義 1 個(gè)整形變量： free用戶申請(qǐng)存儲(chǔ)區(qū)的大?。ㄓ捎脩翩I入） （二）過程 1、定義 check 過程，用于檢查指定的釋放塊（由用戶鍵入）的合法性 2、定義 assignment1 過程，實(shí)現(xiàn) First Fit Algorithm 3、定義 assignment2 過程，實(shí)現(xiàn) Best Fit Algorithm 4、定義 acceptment1 過程，實(shí)現(xiàn) Fir

3、st Fit Algorithm 的回收算法 5、定義 acceptment2 過程，實(shí)現(xiàn) Best Fit Algorithm 的回收算法 6、定義 print 過程，打印空閑區(qū)隊(duì)列 （三）執(zhí)行 程序首先申請(qǐng)一整塊空閑區(qū)，其首址為 0，大小為 32767；然后，提示用戶使用哪種分配算法，再提示是分配還是回收；分配時(shí)要求輸入申請(qǐng)區(qū)的大小，回收時(shí)要求輸入釋放區(qū)的首址和大小。實(shí)驗(yàn)代碼Main.cpp#include<stdio.h>#include<stdlib.h>#include<string.h>#include<iostream>using

4、namespace std;#define MAX_SIZE 32767typedef struct nodeint id;int adr;int size;struct node *next;Node;Node *head1, *head2, *back1, *back2, *assign;int request;int check(int add, int siz, char c)Node *p, *head;int check = 1;if (add<0 | siz<0)check = 0;/*地址和大小不能為負(fù)*/if (c = 'f' | c = '

5、;F')head = head1;elsehead = head2;p = head->next;while (p != NULL) && check)if (add<p->adr) && (add + siz>p->adr) | (add >= p->adr) && (add<p->adr + p->size)check = 0;elsep = p->next;if (check = 0)printf("t輸入釋放區(qū)地址或大小有錯(cuò)誤！n");retur

6、n check;void init()Node *p;head1 = (Node*)malloc(sizeof(Node);head2 = (Node*)malloc(sizeof(Node);p = (Node*)malloc(sizeof(Node);head1->next = p;head2->next = p;p->size = MAX_SIZE;p->adr = 0;p->next = NULL;p->id = 0;Node* assignment1(int num, int req)Node *before, *after, *ass;ass =

7、 (Node*)malloc(sizeof(Node);before = head1;after = head1->next;ass->id = num;ass->size = req;while (after->size<req)before = before->next;after = after->next;if (after = NULL)ass->adr = -1;elseif (after->size = req)before->next = after->next;ass->adr = after->a

8、dr;elseafter->size -= req;ass->adr = after->adr;after->adr += req;return ass;void acceptment1(int address, int siz, int rd)Node *before, *after;int insert = 0;back1 = (Node*)malloc(sizeof(Node);before = head1;after = head1->next;back1->adr = address;back1->size = siz;back1->i

9、d = rd;back1->next = NULL;while (!insert&&after)/將要被回收的分區(qū)插入空閑區(qū)（按首址大小從小到大插入）if (after = NULL) | (back1->adr <= after->adr) && (back1->adr >= before->adr)before->next = back1;back1->next = after;insert = 1;elsebefore = before->next;after = after->next;i

10、f (insert)if (back1->adr = before->adr + before->size)/和前邊分區(qū)合并before->size += back1->size;before->next = back1->next;free(back1);else if (after&&back1->adr + back1->size = after->adr)/和后邊分區(qū)合并back1->size += after->size;back1->next = after->next;back1-

11、>id = after->id;free(after);after = back1;printf("t首先分配算法回收內(nèi)存成功！n");elseprintf("t首先分配算法回收內(nèi)存失??！n");Node* assignment2(int num, int req)Node *before, *after, *ass, *q;ass = (Node*)malloc(sizeof(Node);q = (Node*)malloc(sizeof(Node);before = head2;after = head2->next;ass->

12、id = num;ass->size = req;while (after->size<req)before = before->next;after = after->next;if (after = NULL)ass->adr = -1;elseif (after->size = req)before->next = after->next;ass->adr = after->adr;elseq = after;before->next = after->next;ass->adr = q->adr;

13、q->size -= req;q->adr += req;before = head2;after = head2->next;if (after = NULL)before->next = q;q->next = NULL;elsewhile (after->size)<(q->size)before = before->next;after = after->next;before->next = q;q->next = after;return (ass);void acceptment2(int address,

14、int siz, int rd)Node *before, *after;int insert = 0;back2 = (Node*)malloc(sizeof(Node);before = head2;after = head2->next;back2->adr = address;back2->size = siz;back2->id = rd;back2->next = NULL;if (head2->next = NULL)/空閑隊(duì)列為空head2->next = back2;head2->size = back2->size;el

15、se/空閑隊(duì)列不為空while (after)if (back2->adr = after->adr + after->size)/和前邊空閑分區(qū)合并before->next = after->next;after->size += back2->size;back2 = after;elsebefore = before->next;after = after->next;before = head2;after = head2->next;while (after)if (after->adr = back2->adr

16、 + back2->size)/和后邊空閑區(qū)合并before->next = after->next;back2->size += after->size;elsebefore = before->next;after = after->next;before = head2;after = head2->next;while (!insert)/將被回收的塊插入到恰當(dāng)?shù)奈恢茫ò捶謪^(qū)大小從小到大）if (after = NULL | (after->size>back2->size) && (before->

17、;size<back2->size)before->next = back2;back2->next = after;insert = 1;break;elsebefore = before->next;after = after->next;if (insert)printf("t最佳適應(yīng)算法回收內(nèi)存成功！n");elseprintf("t最佳適應(yīng)算法回收內(nèi)存失敗！n");void print(char choice)/輸出空閑區(qū)隊(duì)列信息Node *p;if (choice = 'f' | choic

18、e = 'F')p = head1->next;elsep = head2->next;if (p)printf("n空閑區(qū)隊(duì)列的情況為：n");printf("t編號(hào)t首址t終址t大小n");while (p)printf("t%dt%dt%dt%dn", p->id, p->adr, p->adr + p->size - 1, p->size);p = p->next;void menu()/菜單及主要過程char chose;int ch, num=0, r, ad

19、d, rd;while (1)system("cls");printf("-存儲(chǔ)管理動(dòng)態(tài)分區(qū)分配及回收算法-n");printf(" F 最先適應(yīng)算法n");printf(" B 最佳適應(yīng)算法n");printf(" E 退出程序n");printf("-n");printf("請(qǐng)選擇算法:");cin >> chose;/scanf("%c", &chose);if (chose = 'e' | c

20、hose = 'E')exit(0);elsesystem("cls");while (1)if (chose = 'f' | chose = 'F')printf("最先適應(yīng)算法:n");if (chose = 'b' | chose = 'B')printf("最佳適應(yīng)算法:n");printf("-n");printf(" 1 分配內(nèi)存n");printf(" 2 回收內(nèi)存n");print

21、f(" 3 查看內(nèi)存n");printf(" 4 返回n");printf("-nn");printf("請(qǐng)選擇:");scanf("%d", &ch);fflush(stdin);switch (ch)case 1:printf("輸入申請(qǐng)的分區(qū)大?。?quot;); scanf("%d", &r);if (chose = 'f' | chose = 'F')assign = assignment1(num, r);elseassign = as