操作系统内存块分配算法

最先适应算法//最先适应算法 #include iostream #include vector using namespace std; class FreeBlock{ //块节点 public: int id; int size; FreeBlock* pre; FreeBlock* next; FreeBlock(int _id 0, int _size 0) { id _id; size _size; pre next nullptr; } }; class BlockList{ //块链 public: FreeBlock* head; //头节点不存储信息 BlockList(){ head new FreeBlock(); head-next head; head-pre head; } }; //void clearList(BlockList list) { // FreeBlock* p list.head-next; // while (p ! list.head) { // FreeBlock* tmp p; // p p-next; // delete tmp; // } // list.head-next list.head; // list.head-pre list.head; //} void initList(BlockList list, vectorint v) { // clearList(list); FreeBlock* head list.head; for (int i 0; i v.size(); i ) { FreeBlock* node new FreeBlock(i 1, v[i]); //分配第 i 1 个块的大小为 v[i] //循环链表构建 node-pre head-pre; node-next head; head-pre-next node; head-pre node; } list.head head; } void allocSize(FreeBlock* block, int request){ block-size - request; cout 当前请求为 request k, 分配到了 block-id 区 endl; } void first_fit(BlockList list, int request) { FreeBlock* p list.head-next; while (p ! list.head) { if (p-size request) { allocSize(p, request); return ; } p p-next; } cout 当前请求为 request k, 空闲空间大小不够无法分配 endl; } int main (void) { vectorint freeSizes {10, 4, 20, 18, 7, 9, 12, 15}; // vectorint request1 {12, 10, 9}; // vectorint request2 {12, 10, 15, 18}; cout 输出需要分配的空间个数: ; int n; cin n; vectorint requestList(n); for (int i 0; i n; i ) { cout 需要分配的大小为: ; cin requestList[i]; cout endl; } cout endl; BlockList list; initList(list, freeSizes); for (auto x : requestList) { first_fit(list, x); } cout endl; cout 分配后的空闲区序列为: endl; cout 块号 空闲空间 endl; FreeBlock* p list.head-next; int i 0; while (p ! list.head) { cout p-id freeSizes[i] ( p-size ) endl; p p-next; } cout endl; } //free 10, 4, 20, 18, 7, 9, 12, 15 // 3 12 10 9 // 4 12 10 15 18最佳适应算法//最佳适应算法 #include iostream #include vector #include climits using namespace std; class FreeBlock{ //块节点 public: int id; int size; FreeBlock* pre; FreeBlock* next; FreeBlock(int _id 0, int _size 0) { id _id; size _size; pre next nullptr; } }; class BlockList{ //块链 public: FreeBlock* head; //头节点不存储信息 BlockList(){ head new FreeBlock(); head-next head; head-pre head; } }; //void clearList(BlockList list) { // FreeBlock* p list.head-next; // while (p ! list.head) { // FreeBlock* tmp p; // p p-next; // delete tmp; // } // list.head-next list.head; // list.head-pre list.head; //} void initList(BlockList list, vectorint v) { // clearList(list); FreeBlock* head list.head; for (int i 0; i v.size(); i ) { FreeBlock* node new FreeBlock(i 1, v[i]); //分配第 i 1 个块的大小为 v[i] //循环链表构建 node-pre head-pre; node-next head; head-pre-next node; head-pre node; } list.head head; } void allocSize(FreeBlock* block, int request){ block-size - request; cout 当前请求为 request k, 分配到了 block-id 区 endl; } void best_fit(BlockList list, int request) { FreeBlock* p list.head-next; FreeBlock* best nullptr; int bestSize INT_MAX; while (p ! list.head) { if (p-size request p-size bestSize) { best p; bestSize p-size; } p p-next; } if (best ! nullptr) { allocSize(best, request); return ; } cout 当前请求为 request k, 空闲空间大小不够无法分配 endl; } int main (void) { vectorint freeSizes {10, 4, 20, 18, 7, 9, 12, 15}; // vectorint request1 {12, 10, 9}; // vectorint request2 {12, 10, 15, 18}; cout 输出需要分配的空间个数: ; int n; cin n; vectorint requestList(n); for (int i 0; i n; i ) { cout 需要分配的大小为: ; cin requestList[i]; cout endl; } cout endl; BlockList list; initList(list, freeSizes); for (auto x : requestList) { best_fit(list, x); } cout endl; cout 分配后的空闲区序列为: endl; cout 块号 空闲空间 endl; FreeBlock* p list.head-next; int i 0; while (p ! list.head) { cout p-id freeSizes[i] ( p-size ) endl; p p-next; } cout endl; } //free 10, 4, 20, 18, 7, 9, 12, 15 // 3 12 10 9 // 4 12 10 15 18最坏适应算法//最坏适应算法 #include iostream #include vector #include climits using namespace std; class FreeBlock{ //块节点 public: int id; int size; FreeBlock* pre; FreeBlock* next; FreeBlock(int _id 0, int _size 0) { id _id; size _size; pre next nullptr; } }; class BlockList{ //块链 public: FreeBlock* head; //头节点不存储信息 BlockList(){ head new FreeBlock(); head-next head; head-pre head; } }; //void clearList(BlockList list) { // FreeBlock* p list.head-next; // while (p ! list.head) { // FreeBlock* tmp p; // p p-next; // delete tmp; // } // list.head-next list.head; // list.head-pre list.head; //} void initList(BlockList list, vectorint v) { // clearList(list); FreeBlock* head list.head; for (int i 0; i v.size(); i ) { FreeBlock* node new FreeBlock(i 1, v[i]); //分配第 i 1 个块的大小为 v[i] //循环链表构建 node-pre head-pre; node-next head; head-pre-next node; head-pre node; } list.head head; } void allocSize(FreeBlock* block, int request){ block-size - request; cout 当前请求为 request k, 分配到了 block-id 区 endl; } void best_fit(BlockList list, int request) { FreeBlock* p list.head-next; FreeBlock* best nullptr; int bestSize INT_MIN; while (p ! list.head) { if (p-size request p-size bestSize) { best p; bestSize p-size; } p p-next; } if (best ! nullptr) { allocSize(best, request); return ; } cout 当前请求为 request k, 空闲空间大小不够无法分配 endl; } int main (void) { vectorint freeSizes {10, 4, 20, 18, 7, 9, 12, 15}; // vectorint request1 {12, 10, 9}; // vectorint request2 {12, 10, 15, 18}; cout 输出需要分配的空间个数: ; int n; cin n; vectorint requestList(n); for (int i 0; i n; i ) { cout 需要分配的大小为: ; cin requestList[i]; cout endl; } cout endl; BlockList list; initList(list, freeSizes); for (auto x : requestList) { best_fit(list, x); } cout endl; cout 分配后的空闲区序列为: endl; cout 块号 空闲空间 endl; FreeBlock* p list.head-next; int i 0; while (p ! list.head) { cout p-id freeSizes[i] ( p-size ) endl; p p-next; } cout endl; } //free 10, 4, 20, 18, 7, 9, 12, 15 // 3 12 10 9 // 4 12 10 15 18