C++ 操作系統(tǒng)內(nèi)存分配算法的實現(xiàn)詳解
更新時間：2021年11月18日 09:00:28 作者：Carmelo_7
本文主要介紹了在動態(tài)分區(qū)管理方式下采用不同的分配算法實現(xiàn)主存分配和實現(xiàn)主存回收，旨在幫助學生理解在動態(tài)分區(qū)管理方式下應怎樣實現(xiàn)主存空間的分配和回收。感興趣的可以了解一下
一、實驗目的
通過本實驗幫助學生理解在動態(tài)分區(qū)管理方式下應怎樣實現(xiàn)主存空間的分配和回收。
二、實驗內(nèi)容
在動態(tài)分區(qū)管理方式下采用不同的分配算法實現(xiàn)主存分配和實現(xiàn)主存回收。
三、實驗要求
（1）可變分區(qū)方式是按作業(yè)需要的主存空間大小來分割分區(qū)的。當要裝入一個作業(yè)時，根據(jù)作業(yè)需要的主存量查看是否有足夠的空閑空間，若有，則按需要量分割一個分區(qū)分配給該作業(yè)；若無，則作業(yè)不能裝入。隨著作業(yè)的裝入、撤離、主存空間被分成許多個分區(qū)，有的分區(qū)被作業(yè)占用，而有的分區(qū)是空閑的。例如：
為了說明哪些區(qū)是空閑的，可以用來裝入新作業(yè)，必須要有一張空區(qū)說明表，格式如下：
其中
起址——指出一個空閑區(qū)的主存起始地址。
長度——指出從起始地址開始的一個連續(xù)空閑區(qū)的長度。
狀態(tài)——有兩種狀態(tài)，一種是“未分配”狀態(tài)，指出對應的由起址指出的某個長度的區(qū)域是空閑區(qū)；另一種是“空表目”狀態(tài)，表示表中對應的登記項目是空白（無效），可用來登記新的空閑區(qū)（例如，作業(yè)撤離后，它所占的區(qū)域就成了空閑區(qū)，應找一個“空表目”欄登記歸還區(qū)的起址和長度且修改狀態(tài)）。
由于分區(qū)的個數(shù)不定，所以空閑區(qū)說明表中應有適量的狀態(tài)為“空表目”的登記欄目，否則造成表格“溢出”無法登記。
上述的這張說明表的登記情況是按提示
（1）中的例所裝入的三個作業(yè)占用的主存區(qū)域后填寫的
（2）當有一個新作業(yè)要求裝入主存時，必須查空閑區(qū)說明表，從中找出一個足夠大的空閑區(qū)。有時找到的空閑區(qū)可能大于作業(yè)需要量，這時應把原來的空閑區(qū)變成兩部分：一個部分分給作業(yè)占用；另一部分又成為一個較小的空閑區(qū)。為了盡量減少由于分割造成的“碎片”，在作業(yè)請求裝入時，盡可能地利用主存的低地址部分的空閑區(qū)，而盡量保存高地址部分有較大的連續(xù)空閑區(qū)域，以利于大型作業(yè)的裝入。為此，在空閑區(qū)說明表中，把每個空閑區(qū)按其地址順序登記，即每個后繼的空閑區(qū)其起始地址總是比前者大。為了方便查找還可使表格“緊縮”，總是讓“空表目”欄集中在表格的后部。
（3）采用首次適應算法或循環(huán)首次算法或最佳適應算法分配主存空間。由于本實驗是模擬主存的分配，所以當把主存區(qū)分配給作業(yè)后并不實際啟動裝入程序裝入作業(yè)，而用輸出“分配情況”來代替。（即輸出當時的空閑區(qū)說明表及其內(nèi)存分配表）
（4）當一個作業(yè)執(zhí)行結束撤離時，作業(yè)所占的區(qū)域應該歸還，歸還的區(qū)域如果與其它空閑區(qū)相鄰，則應合成一個較大的空閑區(qū)，登記在空閑區(qū)說明表中。例如，在提示（1）中列舉的情況下，如果作業(yè)2撤離，歸還所占主存區(qū)域時，應與上、下相鄰的空閑區(qū)一起合成一個大的空閑區(qū)登記在空閑區(qū)說明表中。
（5）請分別按首次適應算法、循環(huán)首次算法和最佳適應算法設計主存分配和回收的程序。然后按（1）中假設主存中已裝入三個作業(yè)，且形成兩個空閑區(qū)，確定空閑說明表的初值?，F(xiàn)有一個需要主存量為6K的作業(yè)4 申請裝入主存；然后作業(yè)3 撤離；再作業(yè)2 撤離。請你為它們進行主存分配和回收，把空閑區(qū)說明表的初值以及每次分配或回收后的變化顯示出來或打印出來。
四、代碼實現(xiàn)
MemoryAllocation.cpp
#include <iostream>
#include <Windows.h>
#include <fstream>
#include <string>
#include <queue>
using namespace std;
int MemorySize = 0;
int OSSize = 0;
int Memory[1000] = { 0 };
struct Struct1{
int begin;
int length;
string state;//值為未分配或者空條目
};
queue<Struct1> WORK;//作業(yè)集合
queue<Struct1> EMPTY;//空區(qū)集合
//更新EMPTY隊列，空區(qū)集合
void UpdateEMP(){
while (!EMPTY.empty()) {
EMPTY.pop();
}
for (int i = 0; i < MemorySize; i++) {
if (Memory[i] == 0) {
for (int j = i + 1; j < MemorySize; j++) {
if (Memory[j] == 1 || j == MemorySize - 1) {
Struct1 emp1;
emp1.begin = i;
if (j == MemorySize - 1) {
emp1.length = j - i + 1;
}
else {
emp1.length = j - i;
}
emp1.state = "未分配";
EMPTY.push(emp1);
i = j;
break;
}
}
}
}
cout << "現(xiàn)有的空區(qū)說明表為：" << endl;
int s = EMPTY.size();
cout << s << "塊空區(qū)" << endl;
for (int i = 0; i < s; i++) {
Struct1 emp1;
emp1 = EMPTY.front();
EMPTY.push(emp1);
EMPTY.pop();
cout << " 起始：" << emp1.begin << " 長度：" << emp1.length << " 狀態(tài)：" << emp1.state << endl;
}
}
//首次適應算法(FF)
void FF(int applyNum) {
if (EMPTY.empty()) {
cout << "沒有足夠的主存空間！！" << endl;
exit(0);
}
bool flag = false;
while (!EMPTY.empty()) {
Struct1 emp1 = EMPTY.front();
if (emp1.length > applyNum) {
for (int i = emp1.begin; i< applyNum + emp1.begin ;i++) {
Memory[i] = 1;
}
Struct1 work3;
work3.begin = emp1.begin;
work3.length = applyNum;
work3.state = "作業(yè)4";
WORK.push(work3);
UpdateEMP();
flag = true;
break;
}
EMPTY.pop();
}
if (!flag) {
cout << "沒有足夠的主存空間！！" << endl;
exit(0);
}
Sleep(2000);
//作業(yè)三撤離
for (int i = 0; i < WORK.size(); i++) {
Struct1 work1;
work1 = WORK.front();
if (work1.state == "作業(yè)3") {
for (int i = work1.begin; i < work1.begin+ work1.length;i++) {
Memory[i] = 0;
}
WORK.pop();
cout << endl << "作業(yè)三撤離！" << endl;
UpdateEMP();
break;
}
else {
WORK.pop();
WORK.push(work1);
}
}
Sleep(2000);
//作業(yè)二撤離
for (int i = 0; i < WORK.size(); i++) {
Struct1 work1;
work1 = WORK.front();
if (work1.state == "作業(yè)2") {
for (int i = work1.begin; i < work1.begin + work1.length; i++) {
Memory[i] = 0;
}
WORK.pop();
cout << endl << "作業(yè)二撤離！" << endl;
UpdateEMP();
break;
}
else {
WORK.pop();
WORK.push(work1);
}
}
}
//循環(huán)首次適應算法（NF）
void NF(int applyNum) {
if (EMPTY.empty()) {
cout << "沒有足夠的主存空間?。? << endl;
exit(0);
}
bool flag = false;
while (!EMPTY.empty()) {
Struct1 emp1 = EMPTY.front();
if (emp1.length > applyNum) {
for (int i = emp1.begin; i < applyNum + emp1.begin; i++) {
Memory[i] = 1;
}
Struct1 work3;
work3.begin = emp1.begin;
work3.length = applyNum;
work3.state = "作業(yè)4";
WORK.push(work3);
UpdateEMP();
flag = true;
break;
}
EMPTY.pop();
}
if (!flag) {
cout << "沒有足夠的主存空間??！" << endl;
exit(0);
}
Sleep(2000);
//作業(yè)三撤離
for (int i = 0; i < WORK.size(); i++) {
Struct1 work1;
work1 = WORK.front();
if (work1.state == "作業(yè)3") {
for (int i = work1.begin; i < work1.begin + work1.length; i++) {
Memory[i] = 0;
}
WORK.pop();
cout << endl << "作業(yè)三撤離！" << endl;
UpdateEMP();
break;
}
else {
WORK.pop();
WORK.push(work1);
}
}
Sleep(2000);
//作業(yè)二撤離
for (int i = 0; i < WORK.size(); i++) {
Struct1 work1;
work1 = WORK.front();
if (work1.state == "作業(yè)2") {
for (int i = work1.begin; i < work1.begin + work1.length; i++) {
Memory[i] = 0;
}
WORK.pop();
cout << endl << "作業(yè)二撤離！" << endl;
UpdateEMP();
break;
}
else {
WORK.pop();
WORK.push(work1);
}
}
}
//最佳適應算法(BF)
void BF(int applyNum) {
if (EMPTY.empty()) {
cout << "沒有足夠的主存空間??！" << endl;
exit(0);
}
bool flag = false;
int col = 10000000;//記錄每一個空區(qū)與請求大小的差值
string e = "";
int em = EMPTY.size()*2;
for (int i = 0; i < em; i++) {
Struct1 emp1 = EMPTY.front();
if (emp1.length > applyNum) {
if (col == (emp1.length - applyNum) && e==emp1.state) {
for (int i = emp1.begin; i < applyNum + emp1.begin; i++) {
Memory[i] = 1;
}
Struct1 work3;
work3.begin = emp1.begin;
work3.length = applyNum;
work3.state = "作業(yè)4";
WORK.push(work3);
UpdateEMP();
flag = true;
break;
}
if (col > (emp1.length - applyNum)) {
col = (emp1.length - applyNum);
e = emp1.state;
}
}
EMPTY.pop();
EMPTY.push(emp1);
}
if (!flag) {
cout << "沒有足夠的主存空間??！" << endl;
exit(0);
}
Sleep(2000);
//作業(yè)三撤離
for (int i = 0; i < WORK.size(); i++) {
Struct1 work1;
work1 = WORK.front();
if (work1.state == "作業(yè)3") {
for (int i = work1.begin; i < work1.begin + work1.length; i++) {
Memory[i] = 0;
}
WORK.pop();
cout << endl << "作業(yè)三撤離！" << endl;
UpdateEMP();
break;
}
else {
WORK.pop();
WORK.push(work1);
}
}
Sleep(2000);
//作業(yè)二撤離
for (int i = 0; i < WORK.size(); i++) {
Struct1 work1;
work1 = WORK.front();
if (work1.state == "作業(yè)2") {
for (int i = work1.begin; i < work1.begin + work1.length; i++) {
Memory[i] = 0;
}
WORK.pop();
cout << endl << "作業(yè)二撤離！" << endl;
UpdateEMP();
break;
}
else {
WORK.pop();
WORK.push(work1);
}
}
}
//主函數(shù)
int main() {
//打印提示信息
cout << "************************************************\n";
cout << " 操作系統(tǒng)實驗內(nèi)存分配算法\n";
cout << " 作者：CSDN Carmelo_7 主頁： https://blog.csdn.net/Carmelo_7?spm=1000.2115.3001.5343 \n";
cout << "************************************************\n";
ifstream inFile;
inFile.open("MemoryAllocation.dat");
if (!inFile.is_open())
cout << "文件打開時候出錯！！" << endl;
inFile >> MemorySize >> OSSize;
cout << "請輸入主存的現(xiàn)有狀態(tài)" << endl;
cout << "正在讀取數(shù)據(jù)文件..." << endl;
Sleep(2000);
//打印空閑區(qū)說明表的初始狀態(tài)
cout << "主存總大小：" << MemorySize << endl <<"操作系統(tǒng)占用空間：" << OSSize <<endl;
for (int i = 0;i<OSSize; i++) {
Memory[i] = 1;
}
int n = 0;
while (!inFile.eof()) {
n++;
Struct1 work1;
inFile >> work1.begin >> work1.length;
work1.state = "作業(yè)"+to_string(n);
WORK.push(work1);
}
int s = WORK.size();
for (int i = 0; i < s; i++) {
Struct1 work2;
work2 = WORK.front();
WORK.push(work2);
WORK.pop();
cout << work2.state << " 起始：" << work2.begin << " 長度：" << work2.length << endl;
for (int i = work2.begin; i < work2.length + work2.begin; i++) {
Memory[i] = 1;
}
}
/*for (int i : Memory) {
cout << i;
}*/
UpdateEMP();
cout << "請輸入新的作業(yè)的申請主存數(shù)量：" << endl;
//打印作業(yè)4的申請量
int applyNum = 0;
cin >> applyNum;
cout << "作業(yè)" << n << "申請了"<< applyNum <<"主存空間" << endl;
cout << "===================================================================================" << endl;
cout << "1.首次適應算法(FF) :將所有空閑分區(qū)按照地址遞增的次序鏈接，在申請內(nèi)存分配時，從鏈首開始查找，將滿足需求的第一個空閑分區(qū)分配給作業(yè)。" << endl;
cout << "2.循環(huán)首次適應算法（NF）：將所有空閑分區(qū)按照地址遞增的次序鏈接，在申請內(nèi)存分配時，總是從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，將滿足需求的第一個空閑分區(qū)分配給作業(yè)" << endl;
cout << "3.最佳適應算法(BF) : 將所有空閑分區(qū)按照從小到大的順序形成空閑分區(qū)鏈，在申請內(nèi)存分配時，總是把滿足需求的、最小的空閑分區(qū)分配給作業(yè)。" << endl;
cout << "===================================================================================" << endl;
cout << "請輸入對應的序號選擇算法：" << endl;
int choose = 0;
cin >> choose;
switch (choose) {
case 1:
FF(applyNum);
break;
case 2:
NF(applyNum);
break;
case 3:
BF(applyNum);
break;
default:
cout << "你輸入的序號有誤?。?！" << endl;
exit(0);
break;
}
}
MemoryAllocation.dat
128 5 5 5 26 6 10 4
五、測試樣例
到此這篇關于C++ 操作系統(tǒng)內(nèi)存分配算法的實現(xiàn)詳解的文章就介紹到這了,更多相關操作系統(tǒng)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
strncpy這個可以指定拷貝字符的長度，指定源地址，目標地址，還有需要拷貝的字符的長度； strcpy只能傳入兩個參數(shù)，只指定拷貝的起始地址跟目標地址，然后整體拷貝；2015-10-10
這篇文章主要介紹了C++設計模式編程中簡單工廠與工廠方法模式的實例對比,文中最后對兩種模式的優(yōu)缺點總結也比較詳細,需要的朋友可以參考下2016-03-03
歸并排序是典型分治思想的代表——首先把原問題分解為兩個或多個子問題，然后求解子問題的解，最后使用子問題的解來構造出原問題的解2022-03-03
本篇文章是對C++中函數(shù)參數(shù)取默認值進行了詳細的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了講解C語言編程中指針賦值的入門實例,通過const int i與int *const pi這樣兩個例子來分析指針的賦值和地址指向,需要的朋友可以參考下2015-12-12
這篇文章主要介紹了C++機房預約系統(tǒng)實現(xiàn)流程，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習吧2022-10-10
使用UART與PC通信實現(xiàn)msp430g2553單片機超聲波測距示例
這篇文章主要介紹了使用UART與PC通信實現(xiàn)msp430g2553單片機超聲波測距示例,需要的朋友可以參考下2014-05-05
在多進程系統(tǒng)中,文件的并發(fā)讀寫可能導致數(shù)據(jù)競爭、文件損壞等問題,為了確保多個進程能夠安全地訪問同一文件,我們需要使用文件鎖,本文將介紹如何使用 C++ 實現(xiàn)文件鎖,并確保文件的并發(fā)讀寫操作是安全的,需要的朋友可以參考下2025-02-02
C++中將string封裝為單獨的類,string?類是?C++?標準庫中的一個非常重要的類,用于表示和操作字符串,這篇文章主要介紹了C++標準庫介紹及使用string類,需要的朋友可以參考下2024-08-08
運算符重載的方法是定義一個重載運算符的函數(shù)，在需要執(zhí)行被重載的運算符時，系統(tǒng)就自動調(diào)用該函數(shù)，以實現(xiàn)相應的運算。也就是說，運算符重載是通過定義函數(shù)實現(xiàn)的2021-09-09