7-1 内存分区分配--首次适应算法 (100 分)
生活随笔
收集整理的這篇文章主要介紹了
7-1 内存分区分配--首次适应算法 (100 分)
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
一：題目7-1 內存分區分配–首次適應算法 (100 分) 寶 今天你看我博客了嗎
輸入內存的大小和閾值minsize，按照首次適應算法進行連續的分區分配。在劃分時，若剩余的內存小于等于minsize，則將整塊內存分配給該進程不再進行劃分。 根據菜單選擇相應的操作：
1.初始化：輸入內存的大小和閾值minsize，初始狀態下空閑分區名字為“void”。
2.分配：輸入申請進程的名字、大小。
若可以分配，顯示“分配成功！”；
若剩余空間不足，顯示不分配原因“剩余空間不足，不予分配。”；
若剩余的空間通過緊湊技術，可以再分配，提示“是否通過緊湊技術，重新劃分？(Y/N)”若選擇“Y”，通過緊湊技術重新劃分并分配，成功后，顯示“分配成功！”若選擇“N”，則輸出“沒有合適的剩余空間，不予分配。”
3.回收：輸入回收進程的名字，若有相鄰空閑分區，需要合并，并輸出“回收成功！”；若輸入錯誤，提示“查無此分區！” 4.顯示：顯示當前內存的分配狀態。
0.退出
其他：輸出“輸入錯誤，請重新輸入。”
輸入格式:
先進行初始化后，按照菜單進行相應的操作。
輸出格式:
菜單只顯示一次，按照相應的選擇輸出。
輸入樣例1:
在這里給出一組輸入。例如：
結尾無空行
輸出樣例1:
在這里給出相應的輸出。例如：
結尾無空行
輸出樣例2:
在這里給出相應的輸出。例如：
結尾無空行
輸入樣例3:
在這里給出一組輸入。例如：
輸出樣例3:
在這里給出相應的輸出。例如：
結尾無空行
輸入樣例4:
在這里給出一組輸入。例如：
結尾無空行
輸出樣例4:
在這里給出相應的輸出。例如：
結尾無空行
輸入樣例5:
在這里給出一組輸入。例如：
結尾無空行
輸出樣例5:
在這里給出相應的輸出。例如：
二:思路
思路：
1.解釋算法：動態分區分配-首次適應算法:
<1>:動態分區分配是根據進程的實際需要，動態的為之分配內存的空間,
<2>:那么首次適應算法首次適應算法，要求空閑分區鏈以地址遞增的次序鏈接，
在分配內存時，從鏈首開始順序查找，直到找到一個大小能滿足要求的
空閑分區為止，然后再按照作業的大小，
從該分區中劃出一塊內存空間分給請求者，余下的空閑分區仍停留在空閑鏈中。
2.寫碼思路：先將整個框架寫好，然后挨個寫功能
3.選擇數據結構:因為每組數據有多個，所以我們選擇結構體數組
4.輸入的要求
<1>.初始化：輸入內存的大小和閾值minsize，初始狀態下空閑分區名字為“void”。
<2>.分配：輸入申請進程的名字、大小。
若可以分配，顯示“分配成功！”；
若剩余空間不足，顯示不分配原因“剩余空間不足，不予分配。”；
若剩余的空間通過緊湊技術，可以再分配，提示“是否通過緊湊技術，
重新劃分？(Y/N)”若選擇“Y”，通過緊湊技術重新劃分并分配，成功后，
顯示“分配成功！”若選擇“N”，則輸出“沒有合適的剩余空間，不予分配。”
<3>.回收：輸入回收進程的名字，若有相鄰空閑分區，需要合并，并輸出“回收成功！”；
若輸入錯誤，提示“查無此分區！”
<4>.顯示：顯示當前內存的分配狀態。
<0>.退出
其他：輸出“輸入錯誤，請重新輸入。”
5.注意如果輸入的進程沒有占滿內存，需要將剩下的內存也得輸出來 并表示為空閑狀態；
三:演示流程
四：debug(貼心杰的建議方式)
1:每實現一個功能就測試，不要等都寫完了在去測試
2:整個碼都碼完了，那就挨個測試給出的示例，
3:如果上方還為未測試出你的bug,那么你就還是用給出的示例 但有一點，每當我們測試完一個用例后，不要退出，直接用功能 3 回收各個進程，然后再測試下一個用例
4：如果還沒有，那就用PTA自帶的測試用例，可以測你的格式是否正確，這道題最狗的還有是你輸出的一定要跟樣例一樣，包括標點符號
五：上碼（有些沒用的注解 懶得刪了 嘻嘻）
/**思路：1.解釋算法：動態分區分配-首次適應算法:<1>:動態分區分配是根據進程的實際需要，動態的為之分配內存的空間,<2>:那么首次適應算法首次適應算法，要求空閑分區鏈以地址遞增的次序鏈接，在分配內存時，從鏈首開始順序查找，直到找到一個大小能滿足要求的空閑分區為止，然后再按照作業的大小，從該分區中劃出一塊內存空間分給請求者，余下的空閑分區仍停留在空閑鏈中。2.寫碼思路：先將整個框架寫好，然后挨個寫功能3.選擇數據結構:因為每組數據有多個，所以我們選擇結構體數組4.輸入的要求<1>.初始化：輸入內存的大小和閾值minsize，初始狀態下空閑分區名字為“void”。<2>.分配：輸入申請進程的名字、大小。若可以分配，顯示“分配成功！”；若剩余空間不足，顯示不分配原因“剩余空間不足，不予分配。”；若剩余的空間通過緊湊技術，可以再分配，提示“是否通過緊湊技術，重新劃分？(Y/N)”若選擇“Y”，通過緊湊技術重新劃分并分配，成功后，顯示“分配成功！”若選擇“N”，則輸出“沒有合適的剩余空間，不予分配。”<3>.回收：輸入回收進程的名字，若有相鄰空閑分區，需要合并，并輸出“回收成功！”；若輸入錯誤，提示“查無此分區！” <4>.顯示：顯示當前內存的分配狀態。<0>.退出其他：輸出“輸入錯誤，請重新輸入。” 5.注意如果輸入的進程沒有占滿內存，需要將剩下的內存也得輸出來 并表示為空閑狀態； **/ #include<bits/stdc++.h> using namespace std;struct Node{int id;//id號 string partition = "void";//分區int start;//起始地址 int end; //結束地址int size;//大小 string state = "空閑";//當前的狀態 }node[1000];int cnt = 0; int memory,minsize;//內存的大小和闕值 int sumSize = 0;//記錄累計的容量 //1.初始化 void Initialize(){cin >> memory >> minsize;node[cnt].id = 1;node[cnt].start = 0;node[cnt].end = memory - 1;node[cnt].size = memory;} //2.分配//分區號 分區 起始地址 結束地址 大小 當前狀態 //1 void 0 1023 1024 空閑//分區號 分區 起始地址 結束地址 大小 當前狀態 //1 A 0 99 100 已分配 //2 B 100 299 200 已分配 //3 C 300 449 150 已分配 void distribution(){string processName;int processSize;cin >> processName >> processSize;if(cnt == 0){//這里主要是處理首個進程的計算 node[cnt].end = -1;} int temp1 = memory - node[cnt].end - 1;//這里是求出容器距離上一次的結束地址 還剩的空間大小int temp2 = memory - sumSize;//這里是總的剩余內存的大小 //考慮闕值int temp3 = temp1 - processSize;if(temp3 <= minsize && temp3 >= 0){ //如果剩余的空間小于闕值，那么的話我們就將剩下的空間全給其進程 processSize = temp1;} if(temp1 >= processSize){cnt++;node[cnt].id = cnt;node[cnt].partition = processName;if(cnt == 1){node[cnt].start = 0;}else{node[cnt].start = node[cnt-1].start + node[cnt-1].size;//本次的開始地址等于上次的開始地址加其大小 }node[cnt].end = node[cnt].start + processSize - 1;//本次的結束地址為開始地址+其大小減一 node[cnt].size = processSize;node[cnt].state = "已分配"; sumSize += processSize; cout << "分配成功！" << endl; }else if(temp2 >= processSize){//如果第一個條件不滿足，那么的話就判斷剩余的總內存，也就是緊湊 cout << "是否通過緊湊技術，重新劃分？(Y/N)" << endl;char ch;cin >> ch;/*如果我們的第一個if條件已經滿足的話根本就不用考慮是否緊湊，那么好，如果我們要緊湊的話，只能說明在這個容器的前面還有空間，那么容器的前面有空間就說明發生了回收這時候如果我們選擇 Y 那么的話我們就要更新前面的id....,如果是 N,那就不用更新 */ if(ch == 'Y'){//更新前面的空閑區，將非空的進程賦值給前面空的進程，緊湊出空間給新的進程 for(int i = 1; i <= cnt; i++) { if(node[i].partition == "void"){int value = node[i].size;//記錄下來空閑區的大小 int j = i;bool temp = false; for( ; j < cnt; j++){node[j].id = j; node[j].partition = node[j+1].partition;node[j].start = node[j+1].start - value;node[j].end = node[j+1].end - value;node[j].size = node[j+1].size;node[j].state = node[j+1].state;temp = true; } cnt--;//這時候騰出一個空間,所以結構體數組的大小減一 i = 0;//再從頭開始遍歷空閑區，因為空閑區可能不止一個 if(temp == false)//說明要緊湊的空間是最后一個，那么直接跳出循環 break;} } //這時候考慮我們的闕值 因為當沒有緊湊的時候根本沒有空間來判斷剩余空間的大小//跟闕值的關系int laterTemp1 = memory - node[cnt].end - 1;//緊湊后的空間大小int laterTemp3 = laterTemp1 - processSize;if(laterTemp3 <= minsize){processSize = laterTemp1;} //賦值，當上方完成后這時候就騰出一個大的size cnt++; node[cnt].id = cnt;node[cnt].partition = processName;if(cnt == 1){node[cnt].start = 0;}else{node[cnt].start = node[cnt-1].start + node[cnt-1].size;//本次的開始地址等于上次的開始地址加其大小 }node[cnt].end = node[cnt].start + processSize - 1;node[cnt].size = processSize;node[cnt].state = "已分配";sumSize += processSize; cout << "分配成功！" << endl;}else if (ch == 'N'){cout << "沒有合適的剩余空間，不予分配。" << endl;} }else{cout << "剩余空間不足，不予分配。" << endl; } } //3.回收 void recycling(){ /*如果發生回收的話，要將 分區改為 void,其狀態為空閑，其他均不變;分為四種情況：<1>:如果其上下均無空閑區，那么該回收的進程就單獨成一行<2>:如果該回收的進程上放有一個空的空閑區，那么就要和其上方進行合并，修改上方的結束地址和空間大小<3>:如果該回收的進程的下方有一個空閑區，那么就修改回收進程的大小和結束地址即可<4>:如果該回收的進程上下都有空閑區，那么的話我們就修改最上方的空閑區的大小和結束地址即可 */ string processName;int flag = 0; cin >> processName;for(int i = 1; i <= cnt; i++) {if(processName == node[i].partition){node[i].partition = "void";node[i].state = "空閑"; sumSize -= node[i].size;//一旦發生回收那么這個累計的容量就要減去回收的容量 flag = 1;break;}} if(flag == 1){cout << "回收成功！" << endl;/*這里我們在合并空閑區的時候只需要當發現一個空閑區的時候，看看下一個分區是否是空閑區如果是就合并 */for(int i = 1; i < cnt; i++){if(node[i].partition == "void" && node[i+1].partition == "void"){node[i].size += node[i+1].size;//其大小為兩個分區的和 node[i].end = node[i+1].end;//其結束地址為下一個空閑區的結束地址//因為分區少了一個所以要更新后面分區的id號int j = i+2;for( ; j <= cnt; j++){node[j-1].id = j - 1; node[j-1].partition = node[j].partition;node[j-1].start = node[j].start;node[j-1].end = node[j].end;node[j-1].size = node[j].size;node[j-1].state = node[j].state; } cnt--;//分區少一個 i = 0;//再從頭開始遍歷 因為可能有多個空閑區 } } }else{cout << "查無此分區！" << endl;} } //4.顯示 void show(){cout << "分區號 分區 起始地址 結束地址 大小 當前狀態" << endl;if (cnt == 0) {for(int i = 0; i <= cnt; i++){cout << node[i].id << ' ' << node[i].partition << ' ' << node[i].start << ' ' << node[i].end << ' '<< node[i].size << ' '<< node[i].state;} } else {//這里需要將剩余的空間也得輸出一下int remainTemp = memory - node[cnt].end - 1; //這里寫大于0 是因為上方我已經處理 minsize; if(remainTemp > 0){cnt++;node[cnt].id = cnt;node[cnt].partition = "void";if(cnt == 1){node[cnt].start = 0;}else{node[cnt].start = node[cnt-1].start + node[cnt-1].size;//本次的開始地址等于上次的開始地址加其大小 } node[cnt].end = node[cnt].start + remainTemp - 1;node[cnt].size = remainTemp;node[cnt].state = "空閑"; }for(int i = 1; i <= cnt; i++){ cout << node[i].id << ' ' << node[i].partition << ' ' << node[i].start << ' ' << node[i].end << ' '<< node[i].size << ' '<< node[i].state << endl; } } } //菜單欄 void menu(){cout << "1.初始化" << endl; cout << "2.分配" << endl;cout << "3.回收" << endl;cout << "4.顯示" << endl; cout << "0.退出" << endl;cout << "請選擇：" << endl; } int main(){bool flag = true;menu();while(flag){int option;cin >> option;switch(option){case 1: Initialize();break;case 2: distribution();break;case 3: recycling();break;case 4: show();break;case 0 : flag = false;break; default: cout << "輸入錯誤，請重新輸入。" << endl; } } }//測試分配區 //分區號 分區 起始地址 結束地址 大小 當前狀態 //1 A 0 99 100 已分配 //2 B 100 299 200 已分配 //3 C 300 449 150 已分配 //4 D 450 699 250 已分配 //5 E 700 899 200 已分配 //6 F 900 999 100 已分配//回收A之后 //分區號 分區 起始地址 結束地址 大小 當前狀態 //1 B 0 199 200 已分配 //2 C 200 349 150 已分配 //3 D 350 599 250 已分配 //4 E 600 799 200 已分配 //5 X 800 949 150 已分配 //6 void 950 999 50 空閑//測試回收區 //回收 A 和 B //分區號 分區 起始地址 結束地址 大小 當前狀態 //1 void 0 99 100 空閑 //2 void 100 299 200 空閑 //3 C 300 449 150 已分配 //4 D 450 699 250 已分配 //5 E 700 899 200 已分配 //6 F 900 999 100 已分配//測試分配區//A 300 //B 200 //C 200 // //回收 A // //D 500寶！！我讓你把你不喜歡的博主取關了，你咋還把我給取關了呢！！ 趕緊嘚，給我關注回來，我天天給你寫博客看！！！
創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎總結
以上是生活随笔為你收集整理的7-1 内存分区分配--首次适应算法 (100 分)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 如何使用aftereffect制作雨中的
- 下一篇： PrivaZer如何设置定时清理 Pri