注：查看全文請關注作者，或點擊前往：主存儲器空間的分配和回收的C++實現 實驗七-2 主存儲器空間的分配和回收 第一題 可變分區管理方式下的最先適應算法 實驗題目

在可變分區管理方式下采用最先適應算法實現主存分配和實現主存回收。

鄂州ssl適用于網站、小程序/APP、API接口等需要進行數據傳輸應用場景，ssl證書未來市場廣闊！成為創新互聯的ssl證書銷售渠道，可以享受市場價格4-6折優惠！如果有意向歡迎電話聯系或者加微信：18982081108（備注：SSL證書合作）期待與您的合作！提示

(1) 可變分區方式是按作業需要的主存空間大小來分割分區的。當要裝入一個作業時，根據作業需要的主存量查看是否有足夠的空閑空間，若有，則按需要量分割一個分區分配給該作業；若無，則作業不能裝入。隨著作業的裝入、撤離，主存空間被分成許多個分區，有的分區被作業占用，而有的分區是空閑的。例如：

為了說明哪些區是空閑的，可以用來裝入新作業，必須要有一張空閑區說明表，格式如下：

（2）當有一個新作業要求裝入主存時，必須查空閑區說明表，從中找出一個足夠大的空閑區。有時找到的空閑區可能大于作業需要量，這時應把原來的空閑區變成兩部分：一部分分給作業占用；另一部分又成為一個較小的空閑區。為了盡量減少由于分割造成的空閑區，而盡量保存高地址部分有較大的連續空閑區域，以利于大型作業的裝入。為此，在空閑區說明表中，把每個空閑區按其地址順序登記，即每個后繼的空閑區其起始地址總是比前者大。為了方便查找還可使表格“緊縮”，總是讓“空表目”欄集中在表格的后部。

（3）采用最先適應算法（順序分配算法）分配主存空間。按照作業的需要量，查空閑區說明表，順序查看登記欄，找到第一個能滿足要求的空閑區。當空閑區大于需要量時，一部分用來裝入作業，另一部分仍為空閑區登記在空閑區說明表中。

由于本實驗是模擬主存的分配，所以把主存區分配給作業后并不實際啟動裝入程序裝入作業，而用輸出“分配情況”來代替。最先適應分配算法如圖：

（4）當一個作業執行結束撤離時，作業所占的區域應該歸還，歸還的區域如果與其它空閑區相鄰，則應合成一個較大的空閑區，登記在空閑區說明表中。例如，在提示（1）中列舉的情況下，如果作業2撤離，歸還所占主存區域時，應與上、下相鄰的空閑區一起合成一個大的空閑區登記在空閑區說明表中。歸還主存時的回收算法如圖：

（5）請按最先適應算法設計主存分配和回收的程序。然后按（1）中假設主存中已裝入三個作業，且形成兩個空閑區，確定空閑區說明表的初值。現有一個需要主存量為6K的作業4申請裝入主存；然后作業3撤離；再作業2撤離。請你為它們進行主存分配和回收，把空閑區說明表的初值以及每次分配或回收后的變化顯示出來或打印出來。

程序中使用的數據結構及符號說明

1. 結構體及其數組（數據結構）：空閑區條目和作業條目

struct item //空閑區條目和作業條目的結構體
{int len;   //長度
	int start; //起址(閉)
	int end;   //終址(開)=起址+長度
	int num;   //編號（用于作業）
};
item Free[10010]; //空閑區條目
item work[10010]; //主存中作業的條目

2. 整型變量

int Freecnt = 0;  //空閑區條目的數量
int workcnt;      //主存中作業的數量
int max_len;      //主存空間的大長度
int os_len;       //操作系統的長度

3. 自定義函數
   • bool cmp(item a, item b)：將條目按起始地址排序
   • void display_work()：輸出作業表
   • display_Free()：輸出空閑表
   • void init()：初始化主存
   • void alloc()：分配新作業
   • void release()：作業撤離，歸還空間

源程序并附上注釋

// 可變分區管理最先適應算法
#include#include 
#includeusing namespace std;

struct item //空閑區條目和作業條目的結構體
{int len;   //長度
	int start; //起址(閉)
	int end;   //終址(開)=起址+長度
	int num;   //編號（用于作業）
};
item Free[10010]; //空閑區條目
item work[10010]; //主存中作業的條目
int Freecnt = 0;  //空閑區條目的數量
int workcnt;      //主存中作業的數量
int max_len;      //主存空間的大長度
int os_len;       //操作系統的長度

bool cmp(item a, item b) //將條目按起始地址排序
{return a.start< b.start;
}

//輸出作業表
void display_work()
{cout<< "作業表如下："<< endl;
	cout<< "---------------------------------"<< endl;
	cout<< "|序號|  作業  | 起址 | 長度 |"<< endl;
	for (int i = 1; i<= workcnt; i++)
	{cout<< "|"<< setw(4)<< i;
		cout<< "| 作業"<< left<< setw(3)<< work[i].num;
		cout<< "|"<< right<< setw(4)<< work[i].start<< "k |";
		cout<< right<< setw(4)<< work[i].len<< "k |";
		cout<< endl;
	}
	cout<< "---------------------------------"<< endl;
}

//輸出空閑表
void display_Free()
{cout<< "空閑表如下："<< endl;
	cout<< "------------------------"<< endl;
	cout<< "|序號| 起址 | 長度 |"<< endl;
	for (int i = 1; i<= Freecnt; i++)
	{cout<< "|"<< setw(4)<< i;
		cout<< "|"<< right<< setw(4)<< Free[i].start<< "k |";
		cout<< right<< setw(4)<< Free[i].len<< "k |";
		cout<< endl;
	}
	cout<< "------------------------"<< endl;
}

//初始化主存
void init()
{cout<< "請輸入主存空間的長度（長度單位均為k）：";
	cin >>max_len;
	//構建主存中的操作系統空間
	cout<< "請輸入操作系統所占空間的長度：";
	cin >>os_len;
	//構建主存中的作業
	cout<< "請輸入主存中作業的條目：";
	cin >>workcnt;
	for (int i = 1; i<= workcnt; i++)
	{cout<< "請輸入第"<< i<< "個作業的起始地址、長度：";
		cin >>work[i].start >>work[i].len;
		work[i].end = work[i].start + work[i].len;
		work[i].num = i;
		if (work[i].end >max_len)
		{	cout<< "超出了主存空間的大長度，請重新輸入"<< endl;
			i--;
		}
		else if (work[i].start< os_len)
		{	cout<< "與操作系統空間部分重疊，請重新輸入"<< endl;
			i--;
		}
		else
		{	for (int j = 1; j< i; j++)
			{		if ((work[i].start >work[j].start) && (work[i].start< work[j].end))
				{cout<< "與作業"<< j<< "部分重疊，請重新輸入"<< endl;
					i--;
					break;
				}
				else if ((work[j].start >work[i].start) && (work[j].start< work[i].end))
				{cout<< "與作業"<< j<< "部分重疊，請重新輸入"<< endl;
					i--;
					break;
				}
			}
		}
	}
	sort(work + 1, work + 1 + workcnt, cmp);
	//OS相當于最開始的作業
	work[0].start = 0;
	work[0].len = os_len;
	work[0].end = os_len;
	//基于主存剩余空間構建空閑表
	for (int i = 1; i<= workcnt; i++)
	{if (work[i].start >work[i - 1].end) //起址大于上一項的尾地址，則構建空閑區
		{	Freecnt++; //空閑區個數加1
			Free[Freecnt].start = work[i - 1].end;
			Free[Freecnt].len = work[i].start - work[i - 1].end;
			Free[Freecnt].end = work[i].start;
		}
	}
	//主存末端的空閑區
	if (work[workcnt].end< max_len) //起址最后的作業的尾地址小于主存長度則存在
	{Freecnt++;
		Free[Freecnt].start = work[workcnt].end;
		Free[Freecnt].len = max_len - Free[Freecnt].start;
		Free[Freecnt].end = max_len;
	}
	display_work();
	display_Free();
	return;
}

//分配新作業
void alloc()
{cout<< "開始分配新作業："<< endl;
	int tempcnt = workcnt + 1; //作業編號的臨時值
	cout<< "請輸入作業"<< tempcnt<< "長度：";
	cin >>work[tempcnt].len;
	work[tempcnt].num = tempcnt;
	bool flag = 0; //分配是否成功的標記
	//遍歷(未分配)空閑表
	for (int i = 1; i<= Freecnt; i++)
	{if (Free[i].len >= work[tempcnt].len) //空閑區長度大于等于作業長度，則可在此空閑區分配
		{	//確定作業起址
			work[tempcnt].start = Free[i].start;
			work[tempcnt].end = work[tempcnt].start + work[tempcnt].len;
			//修改空閑區
			Free[i].len -= work[tempcnt].len;
			Free[i].start += work[tempcnt].len;
			if (Free[i].len == 0) //若空閑區長度變為0，刪除該空閑區
			{		Freecnt--;
				for (int j = i; j<= Freecnt; j++)
				{Free[j] = Free[j + 1];
				}
			}
			//標記：成功
			flag = 1;
			break;
		}
	}
	if (flag) //分配成功
	{workcnt++; //主存中作業數加一
		cout<< "分配成功！起址為"<< work[workcnt].start<< "K"<< endl;
		cout<< "----------------------"<< endl;
		sort(work + 1, work + 1 + workcnt, cmp); //按起址排序
	}
	else
	{cout<< "分配失敗！"<< endl;
		cout<< "----------"<< endl;
	}
	display_work();
	display_Free();
	return;
}

//作業撤離，歸還空間
void release()
{int temp_num;
	cout<< "請輸入要撤離的作業編號：";
	cin >>temp_num;
	bool flag1 = 0; //標記作業是否存在于主存
	int pos;        //作業位置
	//尋找作業位置
	for (int i = 1; i<= workcnt; i++)
	{if (work[i].num == temp_num)
		{	flag1 = 1;
			pos = i;
			break;
		}
	}
	if (flag1 == 0)
	{cout<< "該作業不在主存中！";
		cout<< "------------------"<< endl;
		return;
	}
	//檢查是否有與歸還區下鄰的空閑區
	bool flag2 = 0; //標記：是否有與歸還區下鄰的空閑區
	for (int i = 1; i<= Freecnt; i++)
	{//若有，合并成一個較大的空閑區
		if (work[pos].end == Free[i].start)
		{	flag2 = 1;
			Free[i].start = work[pos].start;
			Free[i].len += work[pos].len;
			break;
		}
	}
	//檢查是否有與歸還區上鄰的空閑區
	bool flag3 = 0; //標記：是否有與歸還區上鄰的空閑區
	for (int i = 1; i<= Freecnt; i++)
	{//若有
		if (work[pos].end == Free[i].start)
		{	flag3 = 1;
			if (flag2) //若歸還區已和下鄰的空閑區合并，合成一個更大的空閑區
			{		Free[i].len += Free[i + 1].len;
				Free[i].end = Free[i + 1].end;
				//刪除被合并的空閑區
				Freecnt--;
				for (int j = i + 1; j<= Freecnt; j++)
				{Free[j] = Free[j + 1];
				}
			}
			if (!flag2) //若歸還區沒有和下鄰的空閑區合并
			{		Free[i].len += work[pos].len;
				Free[i].end = work[pos].end;
			}
			break;
		}
	}
	if (flag2 == 0 && flag3 == 0) //若沒有相鄰空閑區，則新建一個空閑區
	{Freecnt++; //空閑區個數加1
		//新建
		Free[Freecnt].start = work[pos].start;
		Free[Freecnt].len = work[pos].len;
		Free[Freecnt].end = work[pos].end;
		sort(Free + 1, Free + 1 + Freecnt, cmp); //排序
	}
	work[pos].start = 0x3f3f3f;              //將被釋放的作業的起址改為無窮大
	sort(work + 1, work + 1 + workcnt, cmp); //排序
	workcnt--;                               //在主存中的作業總數減一
	display_work();
	display_Free();
	return;
}

int main()
{init();
	int op; //操作號
	while (1)
	{cout<< "請輸入操作（1:分配新作業 2:撤離作業 0:結束）：";
		cin >>op;
		if (op == 1)
			alloc();
		else if (op == 2)
			release();
		else if (op == 0)
			break;
	}
	cout<< "程序結束"<< endl;
	return 0;
}

程序運行時的初值及運行結果 1

主存空間的長度（長度單位均為k）：128
操作系統所占空間的長度：10
主存中作業的條目：3
第1個作業的起始地址、長度：10 4
第2個作業的起始地址、長度：32 8
第3個作業的起始地址、長度：14 12

2

分配新作業：

作業4長度：6

3

撤離作業：

要撤離的作業編號：3

4

撤離作業：

要撤離的作業編號：2

第二題 分頁式管理方式下的位示圖 實驗題目

在分頁式管理方式下采用位示圖來表示主存分配情況，實現主存空間的分配和回收。

提示

（1）分頁式存儲器把主存分成大小相等的若干塊，作業的信息也按塊的大小分頁，作業裝入主存時可把作業的信息按頁分散存放在主存的空閑塊中，為了說明主存中哪些塊已經被占用，哪些塊是尚未分配的空閑塊，可用一張位示圖來指出。位示圖可由若干存儲單元來構成，其中每一位與一個物理塊對應，用0/1表示對應塊為空閑/已占用。

（2） 假設某系統的主存被分成大小相等的64塊，則位示圖可用8個字節來構成，另用一單元記錄當前空閑塊數。如果已有第0，1，4，5，6，9，11，13，24，31，共10個主存塊被占用了，那么位示圖情況如下圖：

（3） 當要裝入一個作業時，根據作業對主存的需要量，先查當前空閑塊數是否能滿足作業要求，若不能滿足則輸出分配不成功。若能滿足，則查位示圖，找出為“0”的一些位，置上占用標志“1”，從“當前空閑塊數”中減去本次占用塊數。按找到的計算出對應的塊號，其計算公式為：塊號=j*8+i。其中，j表示找到的是第n個字節，i表示對應的是第n位。根據分配給作業的塊號，為作業建立一張頁表，頁表格式：

（4）當一個作業執行結束，歸還主存時，根據該作業的頁表可以知道應歸還的塊號，由塊號可計算出在位示圖中的對應位置，把對應位的占用標志清成“0”，表示對應的塊已成為空閑塊。歸還的塊數加入到當前空閑塊數中。由塊號計算在位示圖中的位置的公式如下：

• 字節號 j=[塊號/8] （[ ]表示取整）
• 位數 i={塊號/8} （{ }表示取余）

（5）設計實現主存分配和回收的程序。假定位示圖的初始狀態如（2）所述，現有一信息量為5頁的作業要裝入，運行你所設計的分配程序，為作業分配主存且建立頁表（格式如（3）所述）。然后假定有另一作業執行結束，它占用的塊號為第4，5，6和31塊，運行你所設計的回收程序，收回作業歸還的主存塊。

要求能顯示和打印分配或回收前后的位示圖和當前空閑塊數，對完成一次分配后還要顯示或打印為作業建立的頁表。

程序中使用的數據結構及符號說明

1. 結構體及其數組（數據結構），保存作業條目

   struct item                //作業條目的結構體
   {int page_num;   //頁個數
   	int list[1001]; //頁表
   	int num;        //編號
   	bool in;        //是否存在于主存
   };
   item work[1001];

2. 整型數組（數據結構）

   int bit_img[1001][1001];   //位示圖
   int work_list[1001][1001]; //作業的頁表

3. 整型變量

   int byte_num;              //位示圖的字節數
   int free_block;            //空閑塊數
   int work_cnt;              //總數

4. 自定義函數

   • void display_bit()：輸出位示圖
   • void display_page(int i)：輸出作業work[i]的頁表
   • void init()：初始化
   • void create()：分配新作業
   • void release()：回收作業

源程序并附上注釋

#include#includeusing namespace std;

int bit_img[1001][1001];   //位示圖
int work_list[1001][1001]; //作業的頁表
int byte_num;              //位示圖的字節數
int free_block;            //空閑塊數
int work_cnt;              //總數
struct item                //作業條目的結構體
{int page_num;   //頁個數
	int list[1001]; //頁表
	int num;        //編號
	bool in;        //是否存在于主存
};
item work[1001];

//輸出位示圖
void display_bit()
{cout<< "位示圖如下："<< endl;
	//表頭
	cout<< "| 位數 |";
	for (int i = 0; i< 8; i++)
	{cout<< ' '<< setw(2)<< i<< " |";
	}
	cout<< endl;
	cout<< "|字節數|";
	for (int i = 0; i< 8; i++)
	{cout<< "____"
		<< "|";
	}
	cout<< endl;
	for (int j = 0; j< byte_num; j++)
	{cout<< "|  "<< setw(2)<< j<< "  |";
		for (int i = 0; i< 8; i++)
		{	cout<< ' '<< setw(2)<< bit_img[j][i]<< " |";
		}
		cout<< endl;
	}
	for (int i = 0; i< 48; i++)
	{cout<< '-';
	}
	cout<< endl;
	cout<< "當前空閑塊數："<< free_block<< endl;
}

//輸出作業work[i]的頁表
void display_page(int i)
{cout<< "作業"<< work[i].num<< "的頁表如下"<< endl;
	//表頭
	cout<< "| 頁號 | 塊號 |"<< endl;
	for (int j = 0; j< work[i].page_num; j++)
	{cout<< "|  "<< setw(2)<< j<< "  | "<< setw(4)<< work[i].list[j]<< " |"<< endl;
	}
	cout<< "--------------"<< endl;
}

//初始化
void init()
{cout<< "請輸入位示圖的字節數：";
	cin >>byte_num;
	free_block = byte_num * 8;
	//初始化位示圖每一位為0
	for (int j = 0; j< byte_num; j++)
	{for (int i = 0; i< 8; i++)
		{	bit_img[j][i] = 0;
		}
	}
	//初始化主存中的作業
	cout<< "請輸入主存中作業的個數：";
	cin >>work_cnt;
	for (int i = 1; i<= work_cnt; i++)
	{cout<< "請輸入第"<< i<< "個作業的信息"<< endl;
		cout<< "編號：";
		cin >>work[i].num;
		cout<< "頁個數：";
		cin >>work[i].page_num;
		for (int j = 0; j< work[i].page_num; j++)
		{	cout<< "請輸入頁"<< j<< "所在的塊為：";
			cin >>work[i].list[j];
			if (bit_img[work[i].list[j] / 8][work[i].list[j] % 8] == 1) //若該塊被占用
			{		cout<< "該塊已被占用，請重新輸入"<< endl;
				j--;
			}
			else if (work[i].list[j] >8 * byte_num)
			{		cout<< "超過了主存大小，請重新輸入"<< endl;
				j--;
			}
			else
			{		bit_img[work[i].list[j] / 8][work[i].list[j] % 8] = 1;
				free_block--;
			}
		}
		display_page(i);
		work[i].in = 1; //標記存在于主存
	}
	display_bit();
	return;
}

//分配新作業
void create()
{int i = work_cnt + 1;
	cout<< "請輸入第"<< i<< "個作業的信息"<< endl;
	cout<< "編號：";
	cin >>work[i].num;
	cout<< "頁個數：";
	cin >>work[i].page_num;
	for (int j = 0; j< work[i].page_num; j++)
	{cout<< "請輸入頁"<< j<< "所在的塊為：";
		cin >>work[i].list[j];
		if (bit_img[work[i].list[j] / 8][work[i].list[j] % 8] == 1) //若該塊被占用
		{	cout<< "該塊已被占用，請重新輸入"<< endl;
			j--;
		}
		else if (work[i].list[j] >8 * byte_num)
		{	cout<< "超過了主存大小，請重新輸入"<< endl;
			j--;
		}
		else
		{	bit_img[work[i].list[j] / 8][work[i].list[j] % 8] = 1;
			free_block--;
		}
	}
	work[i].in = 1; //標記存在于主存
	work_cnt++;     //作業個數增加
	display_page(i);
	display_bit();
}

//回收作業
void release()
{int temp_num;
	cout<< "請輸入要回收的作業：";
	cin >>temp_num;
	int pos; //作業的位置
	//尋找位置
	int i;
	for (i = 1; i<= work_cnt; i++)
	{if (work[i].num == temp_num && work[i].in) //編號相同且作業存在于主存
		{	pos = i;
			break;
		}
	}
	if (i == work_cnt + 1)
	{cout<< "作業"<< temp_num<< "不存在于主存！"<< endl;
		return;
	}
	for (int i = 0; i< work[pos].page_num; i++)
	{bit_img[work[pos].list[i] / 8][work[pos].list[i] % 8] = 0;
		free_block++;
	}
	work[pos].in = 0; //標記不存在于主存
	cout<< "回收成功！"<< endl;
	display_bit();
	return;
}

int main()
{init();
	int op; //操作號
	while (1)
	{cout<< "請輸入操作（1:分配新作業 2:回收作業 0:結束）：";
		cin >>op;
		if (op == 1)
			create();
		else if (op == 2)
			release();
		else if (op == 0)
			break;
	}
	cout<< "程序結束"<< endl;
	return 0;
}

程序運行時的初值及運行結果 1

位示圖的字節數：8
主存中作業的個數：2
第1個作業的信息
編號：1
頁個數：6
頁0所在的塊為：0
頁1所在的塊為：1
頁2所在的塊為：9
頁3所在的塊為：11
頁4所在的塊為：13
頁5所在的塊為：24

第2個作業的信息
編號：2
頁個數：4
頁0所在的塊為：4
頁1所在的塊為：5
頁2所在的塊為：6
頁3所在的塊為：31

2

分配新作業

第3個作業的信息
編號：3
頁個數：5
頁0所在的塊為：2
頁1所在的塊為：10
頁2所在的塊為：18
頁3所在的塊為：26
頁4所在的塊為：34

3

回收作業2

思考題

結合實際情況，參考書本，仔細考慮各種主存分配算法的優缺點。把主存分成大小相等的若干塊，作業的信息也按塊的大小分頁，作業裝入主存時把作業的信息按頁分散存放在主存的空閑塊中，這樣很可能導致每個作業按頁裝入主存中時，某一頁還存在一定的空閑空間，思考如何才能有效的利用這些空閑區域。

各種主存分配算法

1. 最先適應算法：地址遞增，順序查找，第一個能滿足的即分配給進程。

   優點：最簡單的，而且通常也是最好和最快的。

   缺點：會使得內存的低地址部分出現很多小的空閑分區，而每次分配查找時，都要經過這些分區，因此也增加了查找的開銷。

2. 鄰近適應算法：循環首次適應算法。

   優點：比較塊

   缺點：常常會導致在內存的末尾分配空間，分裂成小碎片。

3. 最佳適應算法：容量遞增，找到第一個能滿足要求的空閑分區。

   優點：每次分配給文件的都是最合適該文件大小的分區。

   缺點：內存中留下許多難以利用的小的空閑區。

4. 最壞適應算法：容量遞減，找到第一個能滿足要求的分區。

   優點：盡可能地利用存儲器中大的空閑區。

   缺點：容易導致沒有可用的大的內存塊造成浪費。

空閑空間可以通過緊湊來解決，就是操作系統不時地對進程作業進行移動和整理。

實驗心得

1. 第一個實驗Allocation_and_recycling_of_main_storage_space算法實現的關鍵點就在于置換算法的設計。了解該算法后，選用合適的數據結構作為內存中的頁隊列，并按照算法思想對隊列進行維護即可。通過該實驗，我對Allocation_and_recycling_of_main_storage_space及其他置換算法有了更加深入的理解。
   的大小分頁，作業裝入主存時把作業的信息按頁分散存放在主存的空閑塊中，這樣很可能導致每個作業按頁裝入主存中時，某一頁還存在一定的空閑空間，思考如何才能有效的利用這些空閑區域。

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

網頁名稱：主存儲器空間的分配和回收模擬的C++實現-創新互聯
當前路徑：http://www.yijiale78.com/article46/csoceg.html

成都網站建設公司_創新互聯，為您提供靜態網站、云服務器、軟件開發、微信小程序、電子商務、品牌網站制作

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯