实验三 操作系统——虚拟存储管理

⼀一、实验⽬目的

存储管理理的主要功能之⼀一是合理理的分配空间。请求⻚页式管理理是⼀一种常⽤用的虚拟存储管理理技术。本实验的⽬目的是请求⻚页式存储管理理中⻚页⾯面置换算法模拟设计，了了解虚拟存储技术的特点，掌握请求⻚页式存储管理理的⻚页⾯面置换⽅方法。

⼆二、实验原理理

设计程序模拟内存⾸首次适应算法，最佳适应算法和最差适应算法的⼯工作过程。

三、实验要求

存分配算法的过程；

2. 上机时独⽴立编程、调试程序；3. 根据具体实验要求，完成好实验报告。

1. 上机前认真复习⻚页⾯面置换算法，熟悉内存⾸首次适应算法，最佳适应算法和最差适应算法三种内

四、实验代码分析

First_fit — ⾸首次适应算法

123456789101112131415161718

Status First_fit(int request) { //为申请作业开辟新空间且初始化

DuLinkList temp = (DuLinkList) malloc(sizeof(DuLNode)); temp->data.size = request; temp->data.state = Busy;

DuLNode *p = block_first->next; while (p) {

if (p->data.state == Free && p->data.size == request) {//有⼤大⼩小恰好合适的空闲块

p->data.state = Busy; return OK; break; }

if (p->data.state == Free && p->data.size > request) {//有空闲块能满⾜足需求且有剩余

temp->prior = p->prior; temp->next = p;

temp->data.address = p->data.address; p->prior->next = temp;

19202122232425262728

p->prior = temp;

p->data.address = temp->data.address + temp->data.size; p->data.size -= request; return OK; break; }

p = p->next; }

return ERROR;}

Best_fit — 最佳适应算法

1234567891011121314151617181920212223242526272829303132333435

Status Best_fit(int request) { int ch; //记录最⼩小剩余空间

DuLinkList temp = (DuLinkList) malloc(sizeof(DuLNode)); temp->data.size = request; temp->data.state = Busy;

DuLNode *p = block_first->next; DuLNode *q = NULL; //记录最佳插⼊入位置

while (p) //初始化最⼩小空间和最佳位置 {

if (p->data.state == Free && (p->data.size >= request)) { if (q == NULL) { q = p;

ch = p->data.size - request;

} else if (q->data.size > p->data.size) { q = p;

ch = p->data.size - request; } }

p = p->next; }

if (q == NULL) return ERROR;//没有找到空闲块 else if (q->data.size == request) { q->data.state = Busy; return OK; } else {

temp->prior = q->prior; temp->next = q;

temp->data.address = q->data.address; q->prior->next = temp; q->prior = temp;

q->data.address += request; q->data.size = ch; return OK;

363738

}

return OK;}

Worst_fit — 最差适应算法

1234567891011121314151617181920212223242526272829303132333435363738

Status Worst_fit(int request) { int ch; //记录最⼤大剩余空间

DuLinkList temp = (DuLinkList) malloc(sizeof(DuLNode)); temp->data.size = request; temp->data.state = Busy;

DuLNode *p = block_first->next; DuLNode *q = NULL; //记录最佳插⼊入位置

while (p) //初始化最⼤大空间和最佳位置 {

if (p->data.state == Free && (p->data.size >= request)) { if (q == NULL) { q = p;

ch = p->data.size - request;

} else if (q->data.size < p->data.size) { q = p;

ch = p->data.size - request; } }

p = p->next; }

if (q == NULL) return ERROR;//没有找到空闲块 else if (q->data.size == request) { q->data.state = Busy; return OK; } else {

temp->prior = q->prior; temp->next = q;

temp->data.address = q->data.address; q->prior->next = temp; q->prior = temp;

q->data.address += request; q->data.size = ch; return OK; }

return OK;}

五、实验结果

附：实验源码

Memory_Allocation.cpp

123456789101112131415161718192021222324252627

//

// Created by Plusirin on 2020/5/30.//

#include#include

using namespace std;

#define Free 0 //空闲状态#define Busy 1 //已⽤用状态#define OK 1 //完成#define ERROR 0 //出错

#define MAX_length 640 //最⼤大内存空间为640KBtypedef int Status;int flag;

typedef struct freearea//定义⼀一个空闲区说明表结构{

long size; //分区⼤大⼩小 long address; //分区地址 int state; //状态} ElemType;

// 线性表的双向链表存储结构typedef struct DuLNode { ElemType data;

28293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576

struct DuLNode *prior; //前趋指针 struct DuLNode *next; //后继指针}

DuLNode, *DuLinkList;

DuLinkList block_first; //头结点DuLinkList block_last; //尾结点Status alloc(int);//内存分配Status free(int); //内存回收

Status First_fit(int);//⾸首次适应算法Status Best_fit(int); //最佳适应算法Status Worst_fit(int); //最差适应算法void show();//查看分配

Status Initblock();//开创空间表

Status Initblock()//开创带头结点的内存空间链表{

block_first = (DuLinkList) malloc(sizeof(DuLNode)); block_last = (DuLinkList) malloc(sizeof(DuLNode)); block_first->prior = NULL; block_first->next = block_last; block_last->prior = block_first; block_last->next = NULL; block_last->data.address = 0; block_last->data.size = MAX_length; block_last->data.state = Free; return OK;}

//分配主存

Status alloc(int ch) { int request = 0;

cout << \"请输⼊入需要分配的主存⼤大⼩小(单位:KB)：\"; cin >> request;

if (request < 0 || request == 0) {

cout << \"分配⼤大⼩小不不合适，请重试！\" << endl; return ERROR; }

if (ch == 2) //选择最佳适应算法 {

if (Best_fit(request) == OK) cout << \"分配成功！\" << endl; else cout << \"内存不不⾜足，分配失败！\" << endl; return OK; }

if (ch == 3) //选择最差适应算法 {

if (Worst_fit(request) == OK) cout << \"分配成功！\" << endl; else cout << \"内存不不⾜足，分配失败！\" << endl;

7778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123

return OK;

} else //默认⾸首次适应算法 {

if (First_fit(request) == OK) cout << \"分配成功！\" << endl; else cout << \"内存不不⾜足，分配失败！\" << endl; return OK; }}

//⾸首次适应算法

Status First_fit(int request) { //为申请作业开辟新空间且初始化

DuLinkList temp = (DuLinkList) malloc(sizeof(DuLNode)); temp->data.size = request; temp->data.state = Busy;

DuLNode *p = block_first->next; while (p) {

if (p->data.state == Free && p->data.size == request) {//有⼤大⼩小恰好合适的空闲块

p->data.state = Busy; return OK; break; }

if (p->data.state == Free && p->data.size > request) {//有空闲块能满⾜足需求且有剩余

temp->prior = p->prior; temp->next = p;

temp->data.address = p->data.address; p->prior->next = temp; p->prior = temp;

p->data.address = temp->data.address + temp->data.size; p->data.size -= request; return OK; break; }

p = p->next; }

return ERROR;}

//最佳适应算法

Status Best_fit(int request) { int ch; //记录最⼩小剩余空间

DuLinkList temp = (DuLinkList) malloc(sizeof(DuLNode)); temp->data.size = request; temp->data.state = Busy;

DuLNode *p = block_first->next; DuLNode *q = NULL; //记录最佳插⼊入位置

124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172

while (p) //初始化最⼩小空间和最佳位置 {

if (p->data.state == Free && (p->data.size >= request)) { if (q == NULL) { q = p;

ch = p->data.size - request;

} else if (q->data.size > p->data.size) { q = p;

ch = p->data.size - request; } }

p = p->next; }

if (q == NULL) return ERROR;//没有找到空闲块 else if (q->data.size == request) { q->data.state = Busy; return OK; } else {

temp->prior = q->prior; temp->next = q;

temp->data.address = q->data.address; q->prior->next = temp; q->prior = temp;

q->data.address += request; q->data.size = ch; return OK; }

return OK;}

//最差适应算法

Status Worst_fit(int request) { int ch; //记录最⼤大剩余空间

DuLinkList temp = (DuLinkList) malloc(sizeof(DuLNode)); temp->data.size = request; temp->data.state = Busy;

DuLNode *p = block_first->next; DuLNode *q = NULL; //记录最佳插⼊入位置

while (p) //初始化最⼤大空间和最佳位置 {

if (p->data.state == Free && (p->data.size >= request)) { if (q == NULL) { q = p;

ch = p->data.size - request;

} else if (q->data.size < p->data.size) { q = p;

173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218

ch = p->data.size - request; } }

p = p->next; }

if (q == NULL) return ERROR;//没有找到空闲块 else if (q->data.size == request) { q->data.state = Busy; return OK; } else {

temp->prior = q->prior; temp->next = q;

temp->data.address = q->data.address; q->prior->next = temp; q->prior = temp;

q->data.address += request; q->data.size = ch; return OK; }

return OK;}

//主存回收

Status free(int flag) { DuLNode *p = block_first; for (int i = 0; i <= flag; i++) if (p != NULL) p = p->next; else

return ERROR;

p->data.state = Free;

if (p->prior != block_first && p->prior->data.state == Free)//与前⾯面的空闲块相连 {

p->prior->data.size += p->data.size; p->prior->next = p->next; p->next->prior = p->prior; p = p->prior; }

if (p->next != block_last && p->next->data.state == Free)//与后⾯面的空闲块相连 {

p->data.size += p->next->data.size; p->next->next->prior = p; p->next = p->next->next; }

219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266

if (p->next == block_last && p->next->data.state == Free)//与最后的空闲块相连 {

p->data.size += p->next->data.size; p->next = NULL; }

return OK;}

//显示主存分配情况void show() { int flag = 0;

cout << \"\\n主存分配情况:\\n\";

cout << \"++++++++++++++++++++++++++++++++++++++++++++++\\n\\n\"; DuLNode *p = block_first->next;

cout << \"分区号\起始地址\分区⼤大⼩小\状态\\n\\n\"; while (p) {

cout << \" \" << flag++ << \"\\";

cout << \" \" << p->data.address << \"\\\"; cout << \" \" << p->data.size << \"KB\\\"; if (p->data.state == Free) cout << \"空闲\\n\\n\"; else cout << \"已分配\\n\\n\"; p = p->next; }

cout << \"++++++++++++++++++++++++++++++++++++++++++++++\\n\\n\";} //主函数int main() {

int ch;//算法选择标记

cout << \"请输⼊入所使⽤用的内存分配算法：\\n\";

cout << \"(1)⾸首次适应算法\\n(2)最佳适应算法\\n(3)最差适应算法\\n\";

cin >> ch;

while (ch < 1 || ch > 3) {

cout << \"输⼊入错误，请重新输⼊入所使⽤用的内存分配算法：\\n\"; cin >> ch; }

Initblock(); //开创空间表 int choice; //操作选择标记

while (1) { show();

cout << \"请输⼊入您的操作：\";

cout << \"\\n1: 分配内存\\n2: 回收内存\\n0: 退出\\n\";

cin >> choice;

267268269270271272273274275276277278279280281

if (choice == 1) alloc(ch); // 分配内存 else if (choice == 2) // 内存回收 {

int flag;

cout << \"请输⼊入您要释放的分区号：\"; cin >> flag; free(flag);

} else if (choice == 0) break; //退出 else //输⼊入操作有误 {

cout << \"输⼊入有误，请重试！\" << endl; continue; } }}