C++ 高級程式設計第一次上機考試題--記憶體管理
題目說明
實作一個簡單的動態記憶體管理器
預備知識
在介紹分配演算法之前，需要先了解該演算法的一些基本組成部分:
- 首部（header）：位于記憶體塊的起始處，占 4 個位元組，細分為兩個部分：前 29 個二進制位表示對應記憶體塊的 實際可用大小（以 8 位元組為單位，也就是說，如果這個部分的值為 3，表示記憶體塊的實際可用大小為 3 × 8 = 24 位元組）；后 3 個二進制位用于標志本記憶體塊是否是空閑的（000 表示空閑，001 表示已分配）
- 尾部（footer）：內容與首部相同，但是位于記憶體塊的結尾處
- 初始時，整個堆記憶體中除了首部和尾部的其余位元組應均為
0xdf
也就是說，一個記憶體塊的內容應該如下所示（一個正方形表示一個位元組）:
如前所述，這個記憶體塊表示一個實際可用大小為 8 位元組（0x04 到 0x0b 這 8 個位元組）的空閑記憶體塊
記憶體管理演算法
記憶體分配
記憶體的分配采用最先適配（first-fit）的方式，即，對于一個分配 \(B\) 位元組的請求，從低地址向高地址找到第一個實際可用大小為 \(S\) 的滿足 \(B \leq S\) 且空閑的記憶體塊，如果沒有滿足條件的記憶體塊，則列印錯誤訊息
記憶體釋放
將對應記憶體塊首部和尾部的標志位設為 0，其他不變
輸入描述
輸入的第一行為兩個整數，分別表示堆記憶體的大小（包括初始時首部和尾部所占的 8 位元組在內，保證為正數且是 8 的整數倍）和最多分配多少個物件（物件序號為從 1 開始的連續整數），
輸入的第二行為一個整數 \(N\) ，表示接下來有 \(N\) 條命令（保證接下來一定有 \(N\) 條命令），
- 請求分配記憶體的
ALLOC <object-id> <object-size>，其中<object-id>從 1 開始，為正 整數, 單位為位元組且不保證是 8 的整數倍（所以你需要一種方式將 <object-size>向上取整到 8 的整數倍，否 則無法使用前面提到的首部結構的方案），保證不會在分配成功之后對同樣的物件再次分配， - 請求釋放記憶體的
FREE <object-id>，其中<object-id>的含義同上，
-請求列印整個堆記憶體的 SHOW， 保證輸入的所有整數在 int 范圍內，
輸出描述
對于 ALLOC，如果找到了符合條件的記憶體塊，輸出 succeeded to alloc object <object-id>，否則輸出 failed to alloc object <object-id>，
對于 FREE，如果 <object-id> 所標識的物件是已分配的，則輸出 succeeded to free object <object-id>， 否則輸出 invalid memory access，
對于 SHOW，按照十六進制（不需要 0x 前綴）輸出整個堆記憶體的內容，每行輸出4個位元組，
示例
輸入
64 5
ALLOC 1 1
ALLOC 2 2
ALLOC 3 3
ALLOC 4 8
FREE 1
FREE 2
FREE 3
ALLOC 5 10
SHOW
輸出
succeeded to alloc object 1
succeeded to alloc object 2
succeeded to alloc object 3
succeeded to alloc object 4
succeeded to free object 1
succeeded to free object 2
succeeded to free object 3
failed to alloc object 5
00000008
dfdfdfdf
dfdfdfdf
00000008
00000008
dfdfdfdf
dfdfdfdf
00000008
00000008
dfdfdfdf
dfdfdfdf
00000008
00000009
dfdfdfdf
dfdfdfdf
00000009
分析
這道題我在考試的時候想要通過位運算進行, 因為題目中提到在首尾部的 4 個位元組中, 前 29 位標識著 實際可用大小,那么移位就可以獲得. 但是我用了 char** heap 這個二維陣列來模擬堆,每行有 4 個單元, 每個單元是一個 char 這使得移位變得無比復雜, 因為每一行的四個 char 并沒有什么聯系, 手動拼接費時費力. 如果真的需要這樣做, 需要注意 <<,>> 的優先級低于 +, -
更好的做法是, 使用這樣的結構模擬堆(當然, 肯定有更更好的方法):
union line {
unsigned int line_num;
unsigned char line_char[4];
};
line* heap;
- 若需獲得這塊記憶體的大小, 將首部的
line_num右移 3 位即可獲得 - 需要修改實際可用大小以及標志位的時候,將
line_num賦值為分配的大小左移 3 位后加 1 即可 SHOW的時候, 列印每行line_char[4]的內容(便于格式化輸出), 這里要注意大小端的問題, 在此處認為是小端即字資料的高位元組存盤在高地址中.
以下為代碼:
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip >
using namespace std;
///一行就是 4 個位元組
//每個單位是 8 個位元組(兩行)
#pragma pack(1)
union line {
unsigned int line_num;
unsigned char line_char[4];
};
line* heap;
int total_space = 0;//總的位元組數
const char* fun[] = {
"ALLOC",
"FREE",
"SHOW"
};
///
unsigned int round2eight(unsigned int source) {
return (source + 8 - 1) & (0b11111111111111111111111111111000);
}
void initial() {
//注意每一行是倒著的！！！ 3 2 1 0
heap = new line[total_space / 4];
heap[0].line_num = (total_space / 8 - 1) << 3;
heap[total_space / 4 - 1].line_num = (total_space / 8 - 1) << 3;
for (int i = 1; i < total_space / 4 - 1; i++)
{
heap[i].line_num = 0xdfdfdfdf;
}
}
void show() {
for (int i = 0; i < total_space / 4; i++)
{
for (int j = 0; j < 4; j++)
{
cout << hex << setw(2) << setfill('0') << int(heap[i].line_char[3 - j]);
}
cout << endl;
}
cout << endl;
}
/// <summary>
///
/// </summary>
/// <param name="alloc_size">需要的位元組數</param>
/// <returns></returns>
int alloc(size_t alloc_size) {
int flag = -1;
int row_cnt = total_space / 4;//總行數
for (int i = 0; flag == -1 && i < row_cnt; i++)
{
size_t this_size = (heap[i].line_num >> 3) * 8;//這一塊多大位元組（有效的）
if ((heap[i].line_char[0] & 0b111) == 0b001) {
//已經分配
i += this_size / 4 + 1;
}
else {
if (this_size < alloc_size) {
//不夠大
i += this_size / 4 + 1;
}
else {
size_t next3 = i + this_size / 4 + 1;
heap[i].line_num = ((alloc_size / 8) << 3) + 1;
size_t next1 = i + (heap[i].line_num >> 3) * 2 + 1;
heap[next1].line_num = heap[i].line_num;
size_t next2 = next1 + 1;
if (next2 < row_cnt && next3 < row_cnt)
{
size_t left_size = this_size - alloc_size - 8;
heap[next2].line_num = ((left_size / 8) << 3);
heap[next3].line_num = ((left_size / 8) << 3);
}
flag = i;
}
}
}
return flag;
}
int free(size_t line) {
int flag = -1;
if ((heap[line].line_char[0] & 0b111) == 0b001) {
flag = 1;
heap[line].line_num -= 1;
heap[line+(heap[line].line_num >> 3) * 2 + 1].line_num -= 1;
}
return flag;
}
int main() {
unsigned int obj_cnt = 0;
unsigned int N = 0;
cin >> total_space >> obj_cnt;
cin >> N;
initial();
//show(total_space / 4);
int* obj_idx = new int[obj_cnt + 1];
for (unsigned int i = 0; i <= obj_cnt; i++)
{
obj_idx[i] = -1;
}
char** orders;
orders = new char* [N];
for (size_t i=0; i < N; i++)
{
orders[i] = new char[20];
if (i == 0)
{
cin.ignore();
}
cin.getline(orders[i],20);
}
for (unsigned int i = 0; i < N; i++)
{
char fun_name[20];
unsigned int obj_id = 0;
unsigned int obj_size = 0;
sscanf(orders[i], "%s%d%d", fun_name,&obj_id,&obj_size);
for (unsigned int fun_index = 0; fun_index < 3; fun_index++)
{
if (strcmp(fun_name, fun[fun_index]) == 0) {
switch (fun_index)
{
case 0:
//待分配物件數為0 或者該物件已經分配
if (obj_cnt == 0 || obj_idx[obj_id] == 1) {
cout << "failed to alloc object " << obj_id<<endl;
}
else {
int is_succ = alloc(round2eight(obj_size));
if (is_succ != -1) {
cout << "succeeded to alloc object " << obj_id << endl;
obj_cnt--;
obj_idx[obj_id] = is_succ;
}
else {
cout << "failed to alloc object " << obj_id << endl;
}
}
break;
case 1:
if (obj_idx[obj_id] != -1)//說明已分配
{
int is_succ = free(obj_idx[obj_id]);
if (is_succ) {
cout << "succeeded to free object " << obj_id << endl;
obj_cnt++;
obj_idx[obj_id] = -1;
}
else {
cout << " invalid memory access" << endl;
}
}
else {
cout << " invalid memory access";
}break;
case 2:
show();
break;
}
break;
}
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/281112.html
標籤：C++
上一篇：Java回顧第七章