首次適應(yīng)算法實(shí)驗(yàn)報(bào)告(共8頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上操作操作系統(tǒng)大作業(yè)題目：首次適應(yīng)算法分配內(nèi)存學(xué) 號(hào)： 學(xué)生姓名： 張魯云 班 級(jí)：計(jì)科121 首次適應(yīng)算法分配內(nèi)存一、 問題描述在內(nèi)存分配中，動(dòng)態(tài)分區(qū)是根據(jù)實(shí)際的進(jìn)程需求，動(dòng)態(tài)地為之分配空間。而首次適應(yīng)算法分配時(shí)從表頭指針開始查找可利用空間表，將找到的第一個(gè)大小不小于“請(qǐng)求”的空閑塊的一部分分配給用戶?？衫每臻g表本身既不按節(jié)點(diǎn)的初始地址有序，也不按節(jié)點(diǎn)的大小有序。用戶釋放內(nèi)存，回收時(shí)只是將空閑塊插入在鏈表的表頭即可，此算法比較節(jié)省時(shí)間。二、 運(yùn)行環(huán)境 VC6.0三、 算法思想。首次適應(yīng)算法要求空閑分區(qū)鏈以地址遞增的次序鏈接。在分配內(nèi)存時(shí)，從鏈?zhǔn)组_始查找，直到找到一個(gè)

2、大小能滿足要求的空閑分區(qū)為止；然后按照作業(yè)大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，余下的空閑區(qū)仍留在空閑鏈中。若從鏈?zhǔn)椎芥溛捕疾荒苷业揭粋€(gè)能滿足要求的分區(qū)，則此次分配失敗。四、 實(shí)驗(yàn)?zāi)康脑谟?jì)算機(jī)系統(tǒng)中，為了提高內(nèi)存區(qū)的利用率，必須給電腦內(nèi)存區(qū)進(jìn)行合理的分配。本實(shí)驗(yàn)通過對(duì)內(nèi)存區(qū)分配方法首次適應(yīng)算法的使用，來了解內(nèi)存分配的模式。五、 首次適應(yīng)算法分配內(nèi)存算法概要 （1） 結(jié)構(gòu)體Typedef struct freearea/定義一個(gè)空閑區(qū)說明表結(jié)構(gòu) long size; /分區(qū)大小long address; /分區(qū)地址int state; /狀態(tài)ElemType; / 線性表的雙向鏈表存儲(chǔ)結(jié)

3、構(gòu)Typedef struct DuLNode ElemType data; structDuLNode *prior; /前趨指針structDuLNode *next; /后繼指針 DuLNode,*DuLinkList;Status Initblock(intMAX_length)/開創(chuàng)帶頭結(jié)點(diǎn)的內(nèi)存空間鏈表 block_first=(DuLinkList)malloc(sizeof(DuLNode); block_last=(DuLinkList)malloc(sizeof(DuLNode); block_first->prior=NULL; /頭結(jié)點(diǎn)的前驅(qū)指針指向空 block

4、_first->next=block_last; /頭結(jié)點(diǎn)的后繼指針指向尾結(jié)點(diǎn) block_last->prior=block_first; /尾結(jié)點(diǎn)的前驅(qū)指針指向頭結(jié)點(diǎn) block_last->next=NULL; /尾結(jié)點(diǎn)的后繼指針指向空 block_last->data.address=0; /尾結(jié)點(diǎn)的地址是0 block_last->data.size=MAX_length; /分區(qū)大小是最大分區(qū) block_last->data.state=Free; /狀態(tài)是空 return OK; （2）主要函數(shù)說明：void alloc()；進(jìn)行內(nèi)存分配的功

5、能函數(shù)。Status free(int flag)將地址為flag的分區(qū)的內(nèi)存回收。Status First_fit(int request)創(chuàng)建進(jìn)程空間的子函數(shù)；其中，參數(shù)request表示空閑分區(qū)鏈的鏈?zhǔn)字羔槪灰浜虾瘮?shù)alloc（）使用。void show()查看內(nèi)存中的分區(qū)情況。輸入內(nèi)存空間大小六、 流程圖開辟內(nèi)存空間內(nèi)存分配情況顯示輸入操作序列號(hào)其他數(shù)輸入有誤，請(qǐng)重試！1Alloc輸入分配區(qū)間大小3退出FFirst_fit request<0 |request=0FTT分配成功！內(nèi)存不足，分配失??！配大小不合適，請(qǐng)重試！輸入回收區(qū)號(hào)分區(qū)回收2free(flag)七、 代碼實(shí)現(xiàn)#

6、include<iostream.h>#include<stdlib.h>#include<stdio.h>#define Free 0 /空閑狀態(tài)#define Busy 1 /已用狀態(tài)#define OK 1 /完成#define ERROR 0 /出錯(cuò)/#define MAX_length 640 /最大內(nèi)存空間為640KB typedefint Status; int flag; typedefstructfreearea/定義一個(gè)空閑區(qū)說明表結(jié)構(gòu) long size; /分區(qū)大小long address; /分區(qū)地址int state; /狀態(tài)El

7、emType; / 線性表的雙向鏈表存儲(chǔ)結(jié)構(gòu)typedefstructDuLNode ElemType data; structDuLNode *prior; /前趨指針structDuLNode *next; /后繼指針 DuLNode,*DuLinkList; DuLinkListblock_first; /頭結(jié)點(diǎn)DuLinkListblock_last; /尾結(jié)點(diǎn)Status alloc(int);/內(nèi)存分配Status free(int); /內(nèi)存回收Status First_fit(int);/首次適應(yīng)算法void show();/查看分配Status Initblock();/開創(chuàng)

8、空間表Status Initblock(intMAX_length)/開創(chuàng)帶頭結(jié)點(diǎn)的內(nèi)存空間鏈表 block_first=(DuLinkList)malloc(sizeof(DuLNode); block_last=(DuLinkList)malloc(sizeof(DuLNode); block_first->prior=NULL; /頭結(jié)點(diǎn)的前驅(qū)指針指向空 block_first->next=block_last; /頭結(jié)點(diǎn)的后繼指針指向尾結(jié)點(diǎn) block_last->prior=block_first; /尾結(jié)點(diǎn)的前驅(qū)指針指向頭結(jié)點(diǎn) block_last->nex

9、t=NULL; /尾結(jié)點(diǎn)的后繼指針指向空 block_last->data.address=0; /尾結(jié)點(diǎn)的地址是0 block_last->data.size=MAX_length; /分區(qū)大小是最大分區(qū) block_last->data.state=Free; /狀態(tài)是空 return OK; /分配主存Status alloc() int request = 0; printf("請(qǐng)輸入需要分配的主存大小(單位:KB)：");scanf("%d",&request); if(request<0 |request=0)

10、 printf("配大小不合適，請(qǐng)重試！"); return ERROR; if(First_fit(request)=OK) printf("分配成功！"); elseprintf("內(nèi)存不足，分配失敗！"); return OK; /首次適應(yīng)算法Status First_fit(int request) /為申請(qǐng)作業(yè)開辟新空間且初始化DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode);temp->data.size=request; temp->data.state=B

11、usy; DuLNode *p=block_first->next; while(p) if(p->data.state=Free && p->data.size=request) /有大小恰好合適的空閑塊p->data.state=Busy; return OK; break; if(p->data.state=Free && p->data.size>request) /有空閑塊能滿足需求且有剩余temp->prior=p->prior; temp->next=p; temp->data.ad

12、dress=p->data.address; p->prior->next=temp; p->prior=temp; p->data.address=temp->data.address+temp->data.size; p->data.size-=request; return OK; break; p=p->next; return ERROR; /主存回收Status free(int flag) DuLNode *p=block_first; for(inti= 0; i<= flag; i+) if(p!=NULL) p=p

13、->next;elsereturn ERROR; p->data.state=Free; if(p->prior!=block_first&& p->prior->data.state=Free)/與前面的空閑塊相連 p->prior->data.size+=p->data.size; p->prior->next=p->next; p->next->prior=p->prior; p=p->prior; if(p->next!=block_last&& p->

14、next->data.state=Free)/與后面的空閑塊相連 p->data.size+=p->next->data.size; p->next->next->prior=p; p->next=p->next->next; if(p->next=block_last&& p->next->data.state=Free)/與最后的空閑塊相連 p->data.size+=p->next->data.size; p->next=NULL; return OK; /顯示主存分配情

15、況void show() int flag = 0;printf("主存分配情況:n"); DuLNode *p=block_first->next; printf("分區(qū)號(hào)t起始地址t分區(qū)大小t狀態(tài)nn"); while(p) printf("%d ",flag);flag+;printf("%d t",p->data.address);printf("%dKB t",p->data.size); if(p->data.state=Free) printf("

16、空閑nn"); elseprintf("已分配nn"); p=p->next; printf("+nn"); /主函數(shù)void main() int c=1;intMAX_length;/算法選擇標(biāo)記printf("首次適應(yīng)算法內(nèi)存分配算法：n");printf("input MAX_length:n");scanf("%d",&MAX_length);Initblock(MAX_length); /開創(chuàng)空間表int choice;/操作選擇標(biāo)記while(c=1)sho

17、w();printf("請(qǐng)輸入您的操作："); printf("n1: 分配內(nèi)存n2: 回收內(nèi)存n0: 退出n"); scanf("%d",&choice);if(choice=1) alloc(); / 分配內(nèi)存c=1;else if(choice=2) / 內(nèi)存回收 int flag; printf("請(qǐng)輸入您要釋放的分區(qū)號(hào)：n"); scanf("%d",&flag); free(flag);c=1; else if(choice=0) break; /退出 else /輸入操作有誤 printf("輸入有誤，請(qǐng)重試！n"); c=1; printf("&&&&&&&n");八、 運(yùn)行截圖九、 思考Jiesu