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

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

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

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

4、;#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 = 'F')head

5、= 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ū)地址或大小有錯誤！n");return check;void

6、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 = (Node*)mallo

7、c(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->adr;elseafter-

8、>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->id = rd;back1-

9、>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;if (insert)if

10、(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->id = afte

11、r->id;free(after);after = back1;printf("t首先分配算法回收內(nèi)存成功！n");elseprintf("t首先分配算法回收內(nèi)存失?。");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->id = num;ass-

12、>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;q->size -=

13、 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, int siz, int

14、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)/空閑隊列為空head2->next = back2;head2->size = back2->size;else/空閑隊列不為空whi

15、le (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 + back2->

16、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->size<back

17、2->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ū)隊列信息Node *p;if (choice = 'f' | choice = 'F

18、9;)p = head1->next;elsep = head2->next;if (p)printf("n空閑區(qū)隊列的情況為：n");printf("t編號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, add, rd;while (

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

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