操作系統(tǒng)實(shí)驗(yàn)課程的任務(wù)，使用首次適應(yīng)算法完成內(nèi)存的分配與回收。
下面的代碼可以實(shí)現(xiàn)用戶指定的內(nèi)存初始化、內(nèi)存分配、內(nèi)存回收和連續(xù)隨機(jī)回收內(nèi)存直到得到一個(gè)完整內(nèi)存空間的操作。
重慶分公司
重慶分公司
#include#include#include#include#include#includeusing namespace std;
//前向引用聲明
struct AllocMem;
struct FreeMem;
static unsigned Memspace; //定義內(nèi)存空間的總大?。ㄒ訩B為單位）
static string errorMessage; //記錄創(chuàng)建內(nèi)存分區(qū)時(shí)的錯(cuò)誤信息的字符串
static listAllocted_List; //借助C++STL的鏈表結(jié)構(gòu)定義已分配分區(qū)鏈
static listFree_List; //借助STL鏈表結(jié)構(gòu)定義的空閑分區(qū)鏈
//以結(jié)構(gòu)體的形式定義每一個(gè)已分配內(nèi)存分區(qū)，內(nèi)容包括起始地址、分區(qū)大小和程序號(hào)
struct AllocMem
{unsigned Start_Address; //內(nèi)存分區(qū)的開始地址（之所以用unsigned類型表示是為了突出地址只能為非負(fù)數(shù)），以KB為單位
unsigned size; //內(nèi)存分區(qū)的大?。ㄖ杂胾nsigned類型是為了表示分區(qū)大小只能為非負(fù)數(shù)）
unsigned processID; //內(nèi)存分區(qū)對(duì)應(yīng)的程序號(hào)，基于類似的原因仍然使用unsigned類型定義
//結(jié)構(gòu)體的顯式構(gòu)造函數(shù)，參數(shù)為起始地址、分區(qū)大小和程序號(hào)，采用內(nèi)聯(lián)形式以進(jìn)一步提高執(zhí)行效率
explicit inline AllocMem(const unsigned& Start_Address, const unsigned& size, const unsigned& processID) :\
Start_Address(Start_Address), size(size), processID(processID) {}
};
//同樣以結(jié)構(gòu)體的形式定義未分配內(nèi)存分區(qū)，內(nèi)容包括起始地址和大小
struct FreeMem
{unsigned Start_Address; //內(nèi)存分區(qū)的開始地址（之所以用unsigned類型表示是為了突出地址只能為非負(fù)數(shù)），以KB為單位
unsigned size; //內(nèi)存分區(qū)的大?。ㄖ杂胾nsigned類型是為了表示分區(qū)大小只能為非負(fù)數(shù)）
//與已分配內(nèi)存分區(qū)類似的顯式構(gòu)造函數(shù)
explicit inline FreeMem(const unsigned& Start_Address, const unsigned& size) :Start_Address(Start_Address), size(size) {}
};
//用于判斷新加入的內(nèi)存分區(qū)是否有效的函數(shù)，根據(jù)已有的內(nèi)存分區(qū)表和新加入的內(nèi)存分區(qū)信息作為參數(shù)，返回布爾值
bool isValid(const list& Allocted_List, const unsigned& Start_Address, const unsigned& size, const unsigned& processID,const unsigned& Memspace)
{//通過C++STL的增強(qiáng)型for循環(huán)逐一檢查新增加的內(nèi)存分區(qū)是否與之前的內(nèi)存分區(qū)存在矛盾
for (auto& element : Allocted_List)
{//第一種矛盾情況：發(fā)生進(jìn)程號(hào)重復(fù)
if (element.processID == processID)
{ errorMessage = "進(jìn)程號(hào)重復(fù)！";
return false;
}
//第二種矛盾情況：發(fā)生內(nèi)存分區(qū)空間重合
if (!(Start_Address >= element.Start_Address + element.size || Start_Address + size<= element.Start_Address))
{ errorMessage = "內(nèi)存空間重合！";
return false;
}
//第三種矛盾情況：分配空間高地址大于內(nèi)存空間大地址
if (Start_Address + size >Memspace)
{ errorMessage = "超過內(nèi)存空間大小！";
return false;
}
}
//不存在矛盾，因此返回true值
return true;
}
//用于輸出某一時(shí)刻的分區(qū)信息的函數(shù)
void print(void)
{cout<<"分區(qū)號(hào) "<< "起始地址 "<< "分區(qū)大小 "<< "進(jìn)程號(hào) "<< endl;
list::iterator it1(Allocted_List.begin()); //記錄已分配分區(qū)鏈的遍歷位置的迭代器
list::iterator it2 (Free_List.begin()); //記錄空閑分區(qū)鏈的遍歷位置的迭代器
unsigned pos(1); //記錄當(dāng)前的分區(qū)號(hào)
//當(dāng)兩個(gè)鏈表都還未遍歷完成時(shí)持續(xù)進(jìn)行循環(huán)
while (it1 != Allocted_List.end() && it2 != Free_List.end())
{//通過比較兩個(gè)鏈表中當(dāng)前節(jié)點(diǎn)的起始地址屬性，可以得知需要先按順序輸出哪一個(gè)節(jié)點(diǎn)的信息
if (it1->Start_Address< it2->Start_Address)
{ cout<< setw(6)<< setiosflags(ios::right)<< pos++<< setw(14)<< setiosflags(ios::right)<< it1->Start_Address \
<< setw(12)<< setiosflags(ios::right)<< it1->size<< setw(10)<< setiosflags(ios::right)<< it1->processID<< endl;
it1++;
}
else
{ cout<< setw(6)<< setiosflags(ios::right)<< pos++<< setw(14)<< setiosflags(ios::right)<< it2->Start_Address \
<< setw(12)<< setiosflags(ios::right)<< it2->size<< setw(10)<< setiosflags(ios::right)<< "無進(jìn)程"<< endl;
it2++;
}
}
//循環(huán)結(jié)束時(shí)，已經(jīng)完成遍歷了一個(gè)鏈表，那么就繼續(xù)將另一個(gè)鏈表中的信息輸出（類似于數(shù)據(jù)結(jié)構(gòu)中的歸并排序中的歸并過程）
//第一種情況：已分配內(nèi)存分區(qū)鏈表先完成遍歷
if (it1 == Allocted_List.end())
{while (it2 != Free_List.end())
{ cout<< setw(6)<< setiosflags(ios::right)<< pos++<< setw(14)<< setiosflags(ios::right)<< it2->Start_Address \
<< setw(12)<< setiosflags(ios::right)<< it2->size<< setw(10)<< setiosflags(ios::right)<< "無進(jìn)程"<< endl;
it2++;
}
}
//第二種情況：空閑分區(qū)鏈表先完成遍歷
else
{while (it1 != Allocted_List.end())
{ cout<< setw(6)<Start_Address \
<< setw(12)<size<< setw(10)<< setiosflags(ios::right)<< it1->processID<< endl;
it1++;
}
}
cout<< endl;
}
//使用首次適應(yīng)法進(jìn)行內(nèi)存分區(qū)分配的函數(shù)
void FF_Allocate(void)
{unsigned pid; //記錄進(jìn)程號(hào)
unsigned space; //記錄空間大小
//獲取用戶輸入的進(jìn)程號(hào)和空間大小
cout<< "請(qǐng)輸入所需分配內(nèi)存的進(jìn)程的進(jìn)程號(hào)：";
cin >>pid;
cout<< "請(qǐng)輸入分配空間的大?。?;
cin >>space;
//遍歷已分配進(jìn)程表，判讀進(jìn)程號(hào)是否重復(fù)
for (auto& e : Allocted_List)
{if (e.processID == pid)
{ cout<< "進(jìn)程號(hào)重復(fù)，本次分配內(nèi)存空間結(jié)束！"<< endl;
return;
}
}
//循環(huán)遍歷空閑分區(qū)鏈，找到第一個(gè)可以容納當(dāng)前進(jìn)程的內(nèi)存分區(qū)
list::iterator it = Free_List.begin();
while (true)
{//當(dāng)前內(nèi)存分區(qū)的容量足夠容納用戶進(jìn)程的情況
if (it->size >= space)
{ //記錄分區(qū)的起始位置
unsigned start = it->Start_Address;
//首先修改空閑分區(qū)鏈中的相應(yīng)內(nèi)容
//情況1：該內(nèi)存分區(qū)的容量剛好與用戶進(jìn)程所需內(nèi)存容量相同
if (it->size == space)
{ //從空閑分區(qū)表中刪除當(dāng)前的空閑分區(qū)，表示該分區(qū)已經(jīng)被分配
auto it2 = it;
Free_List.erase(it2);
}
//情況2：該內(nèi)存分區(qū)的容量大于用戶，則將該分區(qū)的一部分分配給用戶進(jìn)程
else
{ it->Start_Address += space; //修改分區(qū)的起始地址
it->size -= space; //修改分區(qū)的容量大小
}
//接下來修改已分配分區(qū)鏈中的相應(yīng)內(nèi)容，那么就需要找到插入節(jié)點(diǎn)的位置，通過遍歷的方式進(jìn)行
auto pos = Allocted_List.begin();
while (pos!=Allocted_List.end())
{ //如果當(dāng)前所遍歷到的內(nèi)存分區(qū)的起始地址小于插入新分區(qū)的起始地址，則繼續(xù)向后遍歷
if (pos->Start_Address< start)
{pos++;
}
//找到了一個(gè)合適的添加位置的情況，操作完成后函數(shù)直接返回
else
{//第一種情況：之前所有已分配分區(qū)的起始地址都小于當(dāng)前分區(qū)的起始地址，則直接在尾部添加
if (pos == Allocted_List.end())
{AllocMem* tempSpace = new AllocMem(start, space, pid);
Allocted_List.push_back(*tempSpace);
}
//第二種情況：新分配分區(qū)的位置在兩個(gè)已有分配區(qū)域的中間，則從中間插入
else
{AllocMem* tempSpace = new AllocMem(start, space, pid);
Allocted_List.insert(pos, *tempSpace);
}
cout<< "已經(jīng)成功為新進(jìn)程分配分區(qū)！"<< endl;
cout<< endl;
return;
}
}
//迭代完成后如果沒有找到插入位置，則在鏈表尾部進(jìn)行添加
if (pos == Allocted_List.end())
{ AllocMem* tempSpace = new AllocMem(start, space, pid);
Allocted_List.push_back(*tempSpace);
cout<< "已經(jīng)成功為新進(jìn)程分配分區(qū)！"<< endl;
cout<< endl;
return;
}
}
//當(dāng)前內(nèi)存分區(qū)不足以容納用戶進(jìn)程，則繼續(xù)考察下一個(gè)內(nèi)存分區(qū)
else
{ it++;
}
}
//循環(huán)退出，表示經(jīng)過遍歷后仍然沒有找到足夠用戶進(jìn)程的內(nèi)存分區(qū)，則輸出提示信息
cout<< "沒有找到滿足大小的空閑分區(qū)，分區(qū)分配失敗！"<< endl;
return;
}
//用于釋放進(jìn)程的函數(shù)
void SetFree(const unsigned& pid)
{//通過遍歷的方式來找到指定進(jìn)程號(hào)的已分配分區(qū)
auto it1 = Allocted_List.begin();
while (it1 != Allocted_List.end())
{//第一種情況：當(dāng)前遍歷到的進(jìn)程對(duì)應(yīng)的進(jìn)程號(hào)和用戶輸入的不同，則繼續(xù)考察下一個(gè)進(jìn)程
if (it1->processID != pid)
{ it1++;
}
//第二種情況：當(dāng)前遍歷到的進(jìn)程對(duì)應(yīng)的進(jìn)程號(hào)就是用戶所輸入的進(jìn)程號(hào)，那么就處理這個(gè)進(jìn)程
else
{ //首先記錄當(dāng)前分區(qū)的起始地址和大小
unsigned start = it1->Start_Address;
unsigned size = it1->size;
//從已分配分區(qū)鏈表中將這個(gè)分區(qū)刪除
Allocted_List.erase(it1);
//接下來處理空閑分區(qū)鏈表，找到將這塊分區(qū)歸還所應(yīng)該存放的位置
//首先考慮空閑分區(qū)鏈表為空的情況
if (Free_List.size() == 0)
{ FreeMem* tempSpace = new FreeMem(start, size);
Free_List.push_back(*tempSpace);
cout<< "已經(jīng)成功刪除指定進(jìn)程的內(nèi)容！"<< endl;
cout<< endl;
return;
}
auto it2 = Free_List.begin();
while (it2!=Free_List.end())
{ //對(duì)于當(dāng)前迭代器所指示的內(nèi)存分區(qū)首地址小于當(dāng)前分區(qū)起始地址的情況，則繼續(xù)向后遍歷
if (it2->Start_Address< start)
{it2++;
}
//對(duì)于找到了合適的位置的情況，則需要分情況進(jìn)行討論（共有4種情況）
else
{//首先考慮從鏈表頭部進(jìn)行添加的情況
if (it2 == Free_List.begin())
{//第一種情況：歸還分區(qū)與下一個(gè)分區(qū)右相鄰，則修改下一個(gè)分區(qū)的起始地址和大小即可
if (start + size == it2->Start_Address)
{ it2->Start_Address = start;
it2->size += size;
}
//第二種情況：歸還分區(qū)與下一個(gè)分區(qū)不相鄰，則需要?jiǎng)?chuàng)建一個(gè)新的節(jié)點(diǎn)從空閑分區(qū)鏈的頭部插入
else
{ FreeMem* tempSpace = new FreeMem(start, size);
Free_List.push_front(*tempSpace);
}
cout<< "已經(jīng)成功刪除指定進(jìn)程的內(nèi)容！"<< endl;
cout<< endl;
return;
}
//找到當(dāng)前遍歷位置的前一個(gè)位置進(jìn)行分析
auto temp0 = it2;
auto temp1 = (--temp0);
//第一種情況：當(dāng)前新插入的分區(qū)與前后兩個(gè)分區(qū)都不是緊鄰的，則直接插入即可
if (temp1->Start_Address + temp1->size< start&&it2->Start_Address>(start+size))
{FreeMem* tempSpace = new FreeMem(start, size);
Free_List.insert(it2,*tempSpace);
}
//第二種情況：當(dāng)前新插入的分區(qū)與前一個(gè)分區(qū)緊鄰，與后一個(gè)分區(qū)存在間隔，則修改前一個(gè)分區(qū)的大小即可
else if(temp1->Start_Address+temp1->size==start&& start && it2->Start_Address >(start + size))
{temp1->size += size;
}
//第三種情況：當(dāng)前新插入的分區(qū)與后一個(gè)分區(qū)緊鄰，與前一個(gè)分區(qū)存在間隔，則修改后一個(gè)分區(qū)的起始地址和大小即可
else if (temp1->Start_Address + temp1->sizeStart_Address ==(start + size))
{it2->Start_Address = start;
it2->size += size;
}
//第四種情況：當(dāng)前新插入的分區(qū)與前后兩個(gè)分區(qū)都緊鄰，則將三個(gè)分區(qū)進(jìn)行合并
else
{temp1->size = temp1->size + size + it2->size;
Free_List.erase(it2);
}
//操作完成，向用戶輸出提示信息
cout<< "已經(jīng)成功刪除指定進(jìn)程的內(nèi)容！"<< endl;
cout<< endl;
return;
}
}
//遍歷完成后沒有找到可以插入的地方，說明歸還的內(nèi)存分區(qū)位于內(nèi)存空間的末尾，此時(shí)有兩種情況
it2--;
//第一種情況：該內(nèi)存分區(qū)與前一個(gè)內(nèi)存分區(qū)緊鄰，則修改前一個(gè)空閑內(nèi)存分區(qū)的大小即可
if (it2->Start_Address + it2->size == start)
{ it2->size += size;
}
//第二種情況：該內(nèi)存分區(qū)與前一個(gè)內(nèi)存分區(qū)不緊鄰，則向空閑分區(qū)鏈表中新增加一個(gè)節(jié)點(diǎn)
else
{ FreeMem* tempSpace = new FreeMem(start, size);
Free_List.push_back(*tempSpace);
}
//輸出結(jié)束提示信息
cout<< "已經(jīng)成功刪除指定進(jìn)程的內(nèi)容！"<< endl;
cout<< endl;
return;
}
}
//遍歷完所有現(xiàn)存進(jìn)程都沒有找到指定進(jìn)程號(hào)的進(jìn)程，那么輸出提示信息
cout<< "不存在指定進(jìn)程號(hào)的內(nèi)存分區(qū)，本次釋放進(jìn)程過程結(jié)束！"<< endl;
return;
}
//隨機(jī)刪除且進(jìn)行過程展示的函數(shù)
void Multiple_Random_Delete(void)
{//首先記錄鏈表長(zhǎng)度
size_t length = Allocted_List.size();
for (; length >0; length--)
{//記錄隨機(jī)刪除的位置
int randNum = rand() % length;
list::iterator it = Allocted_List.begin();
for (unsigned pos (0); pos< length - 1; ++pos)
{ it++;
}
//將指定位置的元素刪除
cout<< "本次隨機(jī)刪除的進(jìn)程的進(jìn)程號(hào)為為："<< it->processID<< endl;
SetFree(it->processID);
//顯式刪除后的效果
print();
}
}
int main(void)
{//定義初始狀態(tài)下內(nèi)存分區(qū)的個(gè)數(shù)
unsigned AllocMem_Num;
//獲取用戶輸入的內(nèi)存空間的總大小，此處為方便起見并考慮實(shí)際情況，選擇使用KB作為單位
cout<< "請(qǐng)輸入內(nèi)存空間的大?。▎挝粸镵B）：";
cin >>Memspace;
cout<< endl;
//獲取用戶輸入的初始狀態(tài)下進(jìn)程個(gè)數(shù)，接下來獲取初始狀態(tài)下每一個(gè)進(jìn)程內(nèi)存分區(qū)的信息
cout<< "請(qǐng)輸入初始狀態(tài)下的進(jìn)程個(gè)數(shù)：";
cin >>AllocMem_Num;
cout<< "接下來請(qǐng)按照起始地址的遞增順序逐一輸入初始狀態(tài)下每個(gè)內(nèi)存分區(qū)的信息："<< endl;
cout<< endl;
for (unsigned i(0); i< AllocMem_Num; ++i)
{unsigned startAddress;
unsigned size;
unsigned processID;
//獲取當(dāng)前內(nèi)存分區(qū)的起始地址
cout<< "請(qǐng)輸入第"<< (i + 1)<< "個(gè)內(nèi)存分區(qū)的起始地址（以KB為單位）：";
cin >>startAddress;
//獲取當(dāng)前內(nèi)存分區(qū)的分區(qū)大小
cout<< "請(qǐng)輸入第"<< (i + 1)<< "個(gè)內(nèi)存分區(qū)的分區(qū)大?。?;
cin >>size;
//獲取當(dāng)前內(nèi)存分區(qū)的進(jìn)程號(hào)
cout<< "請(qǐng)輸入第"<< (i + 1)<< "個(gè)內(nèi)存分區(qū)對(duì)應(yīng)的進(jìn)程號(hào)：";
cin >>processID;
//首先通過自定義的函數(shù)判斷輸入的內(nèi)存分區(qū)是否有效，即不存在分區(qū)重疊、進(jìn)程號(hào)重名和超過空間大小
if (isValid(Allocted_List,startAddress, size, processID,Memspace) == true)
{ //以結(jié)構(gòu)體的形式創(chuàng)建一個(gè)新的已分配內(nèi)存分區(qū)
AllocMem* tempSpace = new AllocMem(startAddress, size, processID);
//將新創(chuàng)建的內(nèi)存分區(qū)從尾部插入已分配內(nèi)存分區(qū)鏈中
Allocted_List.push_back(*tempSpace);
}
//如果內(nèi)存分區(qū)無效，則輸出無效原因的提示信息，同時(shí)程序終止
else
{ cout<< "程序錯(cuò)誤信息："<< errorMessage<< endl;
return 0;
}
cout<< endl;
}
//接下來對(duì)空閑分區(qū)鏈表進(jìn)行初始化
list::iterator it1 = Allocted_List.begin();
//首先判斷首地址為0的一段地址空間是否已經(jīng)被分配
if (it1->Start_Address != 0)
{FreeMem* tempSpace = new FreeMem(0, it1->size);
Free_List.push_back(*tempSpace);
}
//通過遍歷的方式逐一獲取每一段空閑分區(qū)的起始地址和大小
list::iterator it2 = (--Allocted_List.end());
for(; it1 != it2; it1++)
{//上一個(gè)已分配內(nèi)存分區(qū)的終止位置就是該空閑分區(qū)的起始位置
unsigned start = it1->Start_Address + it1->size;
//空閑分區(qū)的大小即下一個(gè)已分配內(nèi)存分區(qū)的起始地址和該空閑分區(qū)的起始位置的差值
list::iterator it3 = (++it1);
it1--;
unsigned size = it3->Start_Address-start;
//如果差值為零則說明兩個(gè)已分配的內(nèi)存分區(qū)緊鄰，此時(shí)兩者之間不存在空閑分區(qū)，因此跳過本次循環(huán)
if (size == 0)continue;
//大小不為零時(shí)，創(chuàng)建一個(gè)新的未分配內(nèi)存分區(qū)并將其放入空閑分區(qū)表中
FreeMem* tempSpace = new FreeMem(start, size);
Free_List.push_back(*tempSpace);
}
//判斷最后一個(gè)已分配分區(qū)是否與內(nèi)存大小的上界緊鄰，如果不緊鄰則再增加一個(gè)空閑分區(qū)進(jìn)入空閑分區(qū)鏈中
unsigned lastPos = it2->Start_Address + it2->size;
if (lastPos< Memspace)
{FreeMem* tempSpace = new FreeMem(lastPos, Memspace - lastPos);
Free_List.push_back(*tempSpace);
}
//初始化工作完成，輸出內(nèi)存分區(qū)結(jié)果
cout<< "初始化工作完成，下面輸出內(nèi)存分區(qū)的結(jié)果："<< endl;
//通過調(diào)用自定義的print函數(shù)輸出結(jié)果
print();
char ch = getchar();
//接下來由用戶通過鍵盤輸入指定操作類型來完成對(duì)應(yīng)類型的操作（包括進(jìn)程的創(chuàng)建、刪除、多次隨機(jī)刪除過程展示和退出程序）
while (true)
{char cmd; //記錄用戶的操作類型
cout<< "請(qǐng)輸入您需要進(jìn)行的操作（C創(chuàng)建進(jìn)程，D刪除進(jìn)程，M多次隨機(jī)刪除過程展示，P當(dāng)前內(nèi)存分區(qū)展示，Q退出程序）：";
cmd = getchar();
//根據(jù)用戶的操作類型調(diào)用不同的函數(shù)處理
switch (cmd)
{//創(chuàng)建進(jìn)程操作
case 'C': {FF_Allocate(); break; }
//刪除進(jìn)程操作
case 'D':
{ unsigned pid;
//獲取用戶輸入的需要釋放空間的進(jìn)程號(hào)
cout<< "請(qǐng)輸入需要釋放內(nèi)存空間的進(jìn)程號(hào)：";
cin >>pid;
SetFree(pid);
break;
}
//多次隨機(jī)刪除過程展示
case 'M': {Multiple_Random_Delete(); break; }
//當(dāng)前內(nèi)存分區(qū)展示
case 'P': {print(); break; }
//退出程序
case 'Q': {cout<< "程序退出！"<< endl; return 0; break; }
//其余情況處理（充分考慮程序的魯棒性）
default: {cout<< "無法識(shí)別您的命令，請(qǐng)重新輸入。"<< endl; cout<< endl; break; }
}
cmd = getchar();
}
return 0;
}
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
