1、操作系統課程實驗報告 學生姓名： 尹朋 班 學 號： 111131 指導教師： 袁國斌 中國地質大學信息工程學院2015年 1月 4日1 / 15實習題目：內存管理模型的設計與實現【需求規格說明】對內存的可變分區申請采用鏈表法管理進行模擬實現。要求：1.對于給定的一個存儲空間自己設計數據結構進行管理，可以使用單個鏈表，也可以使用多個鏈表，自己負責存儲空間的所有管理組織，要求采用分頁方式（指定單元大小為頁，如4K，2K，進程申請以頁為單位）來組織基本內容；2.當進程對內存進行空間申請操作時，模型采用一定的策略（如：首先利用可用的內存進行分配，如果空間不夠時，進行內存緊縮或其他方案進行處理）對進程

2、給予指定的內存分配；3.從系統開始啟動到多個進程參與申請和運行時，進程最少要有3個以上，每個執行申請的時候都要能夠對系統當前的內存情況進行查看的接口；4.對內存的申請進行內存分配，對使用過的空間進行回收，對給定的某種頁面調度進行合理的頁面分配。5.利用不同的顏色代表不同的進程對內存的占用情況，動態更新這些信息。【算法設計】（1）設計思想：通過建立一個鏈表，來描述已分配和空閑的內存分區。對于每一個分區，它可能存放了某個進程，也可能是兩個進程間的空閑區。鏈表中的每一個結點，分別描述了一個內存分區，包括它的起始地址、長度、指向下一個結點的指針以及分區的當前狀態。在基于鏈表的存儲管理中,當一個新的進程

3、到來時,需要為它分配內存空間,即為它尋找某個空閑分區,該分區的大小必須大于或等于進程的大小.最先匹配法:假設新進程的大小為M,那么從鏈表的首節點開始,將每一個空閑節點的大小與M相比較,直到找到合適的節點.這種算法查找的節點很少,因而速度很快.最佳匹配算法:搜索整個鏈表,將能夠裝得下該進程的最小空閑區分配出去.最壞匹配法：在每次分配的時候,總是將最大的那個空閑區切去一部分,分配給請求者.它的依據是當一個很大的空閑區被切割成一部分后,可能仍然是一個比較大的空閑區,從而避免了空閑區越分越小的問題.（2）設計表示： 分區結點設計： template<class T> class Chain

4、Node friend Chain<T> public: char pro; /內存塊存放的程序名"o" 代表操作系統代表空閑區 T size; /內存塊的大小 T begin; /內存塊起始地址 ChainNode<T> *link; /下一個內存塊 ; template<class T>分區鏈表設計： class Chain public: Chain() first=NULL; Chain(); int ff(int manage,char pro,int size); void assign(ChainNode<T>

5、*q,char pro,int size);/動態分配內存 int bf(int manage,char pro,int size);/最佳適應法 int wf(int manage,char pro,int size);/最壞適應法 int delpro(int manage,char pro);/撤銷進程，可能要進行內存塊的合并 void del_pro(int manage); void init(int manage);/內存的初始化void assign_pro(int manage); /public:ChainNode<T> *first; ChainNode<

6、T> *p; ;（3）詳細設計表示：Main() childmenu(int manage)/子菜單蹋?show()/顯示內存使用情況 assign_pro(manage) /給進程pro根據選擇情況分配內存wf(manage,pro,size)bf(manage,pro,size)ff(manage,pro,size)/最先適應法 /最佳適應法 /最壞適應法【調試報告】【附錄】#include <iostream.h>#include <stdio.h>#include <process.h>template<class T> class

7、 ChainNode friend Chain<T> public: char pro; /內存塊存放的程序名"o" 代表操作系統代表空閑區 T size; /內存塊的大小 T begin; /內存塊起始地址 ChainNode<T> *link; /下一個內存塊 ; template<class T> class Chain public: Chain() first=NULL; Chain(); int ff(int manage,char pro,int size); void assign(ChainNode<T> *

8、q,char pro,int size);/動態分配內存 int bf(int manage,char pro,int size);/最佳適應法 int wf(int manage,char pro,int size);/最壞適應法 int delpro(int manage,char pro);/撤銷進程，可能要進行內存塊的合并 void del_pro(int manage); void init(int manage);/內存的初始化void assign_pro(int manage); /public:ChainNode<T> *first; ChainNode<T

9、> *p; ;memory *base;/代表內存，一個頭指針,內存總大小為256k/int snum=20,50,30,45,54,52; /void assign(memory *q,char pro,int size);void init(int manage)/內存的初始化memory *p,*q;if(base!=NULL)/這一塊是釋放鏈表p=base;while(p)q=p->next;delete p;p=q;base=new memory; /操作系統，大小5k,起始地址是0kbase->begin=0;base->pro='o'bas

10、e->size=5;if(manage=0)/靜態內存，初始化7個內存塊，第一個內存塊是操作系統p=base;q=new memory;/空閑塊1，大小20，起始地址5kq->begin=5;q->pro=0;q->size=20;p->next=q;p=q;q=new memory;/空閑塊2，大小50，起始地址25kq->begin=25;q->pro=0;q->size=50;p->next=q;p=q;q=new memory;/空閑塊3，大小30，起始地址75kq->begin=75;q->pro=0;q->si

11、ze=30;p->next=q;p=q;q=new memory;/空閑塊4，大小45，起始地址105kq->begin=105;q->pro=0;q->size=45;p->next=q;p=q;q=new memory;/空閑塊5，大小54，起始地址150kq->begin=150;q->pro=0;q->size=54;p->next=q;p=q;q=new memory;/空閑塊6，大小52，起始地址204kq->begin=204;q->pro=0;q->size=52;p->next=q;q->ne

12、xt=NULL;else/動態內存，只有一個大的內存塊p=new memory;/空閑塊251k,起始地址是5kp->begin=5;p->pro=0;p->size=251;p->next=NULL;base->next=p;void assign(memory *q,char pro,int size)/動態，給進程pro在內存塊q->next上分配size大小，q不為空且q->next不為空/因為要進行插入操作，所以傳的是要分配內存塊的前指針memory *p=q->next;memory *temp=new memory;temp=new

13、 memory;/代表進程pro的內存塊temp->begin=p->begin;temp->size=size;temp->pro=pro;q->next=temp;if(p->size!=size)/插入的內存塊小于空閑區塊p->size=p->size-size;p->begin=temp->begin+temp->size;temp->next=p;else/插入的內存塊等于空閑區塊temp->next=p->next;delete p;int ff(int manage,char pro,int si

14、ze)/最先適應法memory *p=base;memory *q=p;while(p)/遍歷內存找到第一個適合進程pro的內存塊，保存它的前指針if(p->size<size|p->pro!=0)q=p;p=p->next;else break;if(p=NULL)return 0;/沒找到,返回0else/找到了,返回1if(manage=0)p->pro=pro;/靜態，直接讓進程進駐內存else assign(q,pro,size);/動態，調用assign來給進程pro分配return 1;int bf(int manage,char pro,int s

15、ize)/最佳適應法memory *p=base,*temp=NULL,*q,*front;int min=256;while(p)/遍歷內存找到最佳的內存塊，保存它的前指針if(p->pro=0&&p->size>=size&&min>p->size)min=p->size;front=q;temp=p;q=p;p=p->next;if(temp=NULL)return 0;/沒找到,返回0else if(manage=0)temp->pro=pro;/靜態，直接讓進程進駐內存else assign(front,

16、pro,size);/動態，調用assign來給進程pro分配return 1;int wf(int manage,char pro,int size)/最壞適應法memory *p=base,*temp=NULL,*q,*front;int max=0;while(p)/遍歷內存，找到最大的一塊內存if(p->pro=0&&p->size>=size&&max<p->size)max=p->size;front=q;temp=p;q=p;p=p->next;if(temp=NULL)return 0;/沒找到,返回0e

17、lse /找到了,返回1if(manage=0)temp->pro=pro;/靜態，直接讓進程進駐內存else assign(front,pro,size);/動態，調用assign來給進程pro分配return 1;int delpro(int manage,char pro)/撤銷進程，可能要進行內存塊的合并memory *p=base,*q;while(p)/遍歷內存，尋找進程proif(p->pro!=pro)q=p;p=p->next;else break;if(p=NULL)return 0;/沒找到,返回0else/找到了,返回1if(manage=0)p-&g

18、t;pro=0;/靜態內存，直接撤銷進程，不用內存塊合并else/動態內存，可能要進行內存合并，分4種情況if(q->pro!=0)if(p->next=NULL|p->next->pro!=0)/前后內存塊都不是空閑塊p->pro=0;else/前內存塊不是空閑塊，后內存塊是空閑塊q->next=p->next;p->next->begin=p->begin;p->next->size=p->size+p->next->size;delete p;elseif(p->next=NULL|p->

19、;next->pro!=0)/前內存塊是空閑塊，后內存塊不是空閑塊q->next=p->next;q->size=q->size+p->size;delete p;else/前后內存塊都是空閑塊q->next=p->next->next;q->size=q->size+p->size+p->next->size;delete p->next;delete p;return 1;void print(char ch,int begin,int size)/根據內存塊內容，格式化輸入一塊內存塊switch(c

20、h)case 'o':printf("操作系統區t%3dkt%3dk%3dkn",size,begin,begin+size-1);break;case 0 :printf("空閑區 t%3dkt%3dk%3dkn",size,begin,begin+size-1);break;default :printf("進程%c t%3dkt%3dk%3dkn",ch,size,begin,begin+size-1);break;void show()/格式化顯示內存的儲存情況memory *p=base;int count=

21、1;cout<<"內存現在的儲存情況是："<<endl;printf("塊號t 內容tt大小t起始-結束地址n");while(p)printf(" %2d ",count+);print(p->pro,p->begin,p->size);p=p->next;void del_pro(int manage)/撤銷進程pro，調用delpromemory *p=base;char pro,result;cout<<"請輸入你要撤銷的進程的名字："cin>

22、;>pro;if(pro='o')cout<<"操作系統不可撤銷"<<endl;elseresult=delpro(manage,pro);if(result=0)cout<<"沒有找到進程"<<pro<<",撤銷失敗"<<endl;else cout<<"進程"<<pro<<"撤銷成功"<<endl;void assign_pro(int manage)

23、/給進程pro根據選擇情況分配內存int size,result=-1;char choose ,pro;cout<<"請輸入進程的名字:"cin>>pro;cout<<"請輸入進程請求的內存大小:"cin>>size;cout<<"請選擇分配算法：1，最先適應法。2，最佳適應法。3，最壞適應法"<<endl;cin>>choose;switch(choose)case '1':result=ff(manage,pro,size);br

24、eak;case '2':result=bf(manage,pro,size);break;case '3':result=wf(manage,pro,size);break;if(result=0)cout<<"進程"<<pro<<"分配失敗"<<endl;else if(result=1)cout<<"進程"<<pro<<"分配成功"<<endl;else cout<<"輸入錯誤"<<endl;void childmenu(int manage)/子菜單char choice