《操作系统实验》模拟请求分页存储管理

我就是我 2023-01-18 04:23 257阅读 0赞

### 模拟请求分页存储管理 ###

*  一、实验内容
 *  二、实验要求
 *  三、实验过程
 *   *  1、设计思想
     *  2、数据结构
 *  四、实验代码
 *  五、实验结果

# 一、实验内容 #

模拟请求分页存储管理方式。

# 二、实验要求 #

1、模拟请求分页存储管理方式，采用最近最久未使用替换算法；  
2、程序要添加适当的注释，程序的书写要采用缩进格式；  
3、程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应；  
4、程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。

# 三、实验过程 #

## 1、设计思想 ##

1.  设内存大小为4MB，页面大小为4KB。
2.  立进程：由用户输入进程大小，随机数分配给进程页框数；
3.  请求访问：  
    \[1\] 由用户输入一个十进制的逻辑地址；  
    \[2\] 如果页面已装入内存，通过地址变换机构计算其物理地址即可；  
    \[3\] 如果页面未装入内存，查看分配的页框是否已经占满。若占满则使用最近最久未使用替换算法替换页面；若没有占满则直接将页面存入内存。
4.  地址变换机构（十进制）：  
    \[1\] 由用户输入一个十进制的逻辑地址A；  
    \[2\] 则页号为P=INT\[A/L\]，页内地址为d=\[A\] MOD L，L为页面大小；  
    \[3\] 查询页表，找到页号对应的物理块号B，计算物理地址B×L+d。
5.  最近最久未使用替换算法：  
    赋予每个页面一个访问字段，用于记录一个页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择所有页面中t值最大的予以淘汰。

## 2、数据结构 ##

1.定义一个pcb类，表示每一个进程，含有进程的编号、大小、页表等信息：

class PCB {
        
    private:
    	unsigned size;                        //进程大小
    	unsigned page_item_num;               //为进程分配的页框数
    	unsigned occu;                        //占用的页框数
    	unsigned length;                      //页表长度
    	vector<page_table_item> page_table;   //页表
    public:
    	void init(unsigned ps);                             //初始化
    	void disp();                                        //显示页表信息
    	bool comp(unsigned a);                              //越界检查
    	unsigned trans(unsigned a, vector<unsigned>& s);    //查询页表
    	void LRU(vector<page_table_item>::iterator p);      //LRU置换算法
    };

2.对于每一个页表项，建立类page\_table\_item，包含访问为、状态位等信息：

class page_table_item {
        
    public:
    	page_table_item() {
        
    		chunk_no = NULL;
    		state = 0;
    		visit = 0;	
    	}
    public:
    	unsigned chunk_no;   //物理块号
    	bool state;          //状态位,1表示已调入内存
    	unsigned visit;      //访问位
    };

# 四、实验代码 #

pcb.h

#include<vector>
    
    using namespace std;
    
    class page_table_item {
        
    public:
    	page_table_item() {
        
    		chunk_no = NULL;
    		state = 0;
    		visit = 0;	
    	}
    public:
    	unsigned chunk_no;   //物理块号
    	bool state;          //状态位,1表示已调入内存
    	unsigned visit;      //访问位
    };
    
    class PCB {
        
    private:
    	unsigned size;                        //进程大小
    	unsigned page_item_num;               //为进程分配的页框数
    	unsigned occu;                        //占用的页框数
    	unsigned length;                      //页表长度
    	vector<page_table_item> page_table;   //页表
    public:
    	void init(unsigned ps);               //初始化
    	void disp();                          //显示页表信息
    	bool comp(unsigned a);                              //越界检查
    	unsigned trans(unsigned a, vector<unsigned>& s);    //查询页表
    	void LRU(vector<page_table_item>::iterator p);      //LRU置换算法
    };

pcb.cpp

#include"pcb.h"
    #include<ctime>
    #include<random>
    #include<cmath>
    #include<iostream>
    
    using namespace std;
    
    //初始化PCB
    void PCB::init(unsigned ps) {
        
    	size = ps;
    	uniform_int_distribution<unsigned> u(3, 5);
    	default_random_engine e(time(0));
    	page_item_num = u(e);
    	cout << "为进程分配的页框数为：" << page_item_num << endl;
    	occu = 0;
    	length = size / 4;
    	if (size % 4 != 0)
    		length++;
    	for (unsigned i = 0; i < length; i++) {
        
    		page_table.push_back(page_table_item());
    	}
    }
    
    //显示页表信息
    void PCB::disp() {
        
    	int no = 0;
    	auto i = page_table.begin();
    	cout << "页号" << "\t" << "物理块号" << "\t"
    		<< "状态位" << "\t" << "访问字段" << "\t" << endl;
    	while (i != page_table.end()) {
        
    		if (i->state == 1) {
        
    			cout << no << "\t" << i->chunk_no << "\t\t"
    			<< i->state << "\t" << i->visit << "\t\t" << endl;
    		}
    		no++;
    		i++;
    	}
    }
    
    //越界检查
    bool PCB::comp(unsigned a) {
        
    	if (a >= length || a < 0)
    		return 1;
    	else
    		return 0;
    }
    
    //查询页表
    unsigned PCB::trans(unsigned a, vector<unsigned>& s) {
        
    	auto p = page_table.begin();
    	unsigned no,flag=0;
    	uniform_int_distribution<unsigned> u(0, unsigned(pow(2, 10.0)));
    	default_random_engine e(time(0));
    	for (unsigned i = 0; i < a; i++) {
        
    		p++;
    	}
    	//页在内存中
    	if (p->state == 1) {
        
    		return p->chunk_no;
    	}
    	//页不在内存中
    	if (occu < page_item_num) {
        
    		p->state = 1;
    		for (auto i = page_table.begin(); i != page_table.end(); i++) {
        
    			i->visit++;
    		}
    		p->visit=0;
    		no = u(e);
    		while (!flag) {
        
    			for (auto q = s.begin(); q != s.end(); q++) {
        
    			    if (*q == no) 
    					flag = 1;
    				break;
    			}
    			if (!flag) {
        
    				p->chunk_no = no;
    				s.push_back(no);
    				flag = 1;
    			}
    			else {
        
    				no++;
    				flag = 0;
    			}
    		}
    		occu++;
    	}
    	else if (occu >= page_item_num) {
        
    		LRU(p);		
    	}
    	return p->chunk_no;
    }
    
    void PCB::LRU(vector<page_table_item>::iterator p) {
        
    	auto q = page_table.begin();
    	while (q->state != 1) {
        
    		q++;
    	}
    	auto index = q;
    	while (q != page_table.end()) {
        
    		if(q->visit>index->visit&&q->state==1){
        //找到访问值最大的
    			index = q;
    		}
    		q++;
    	}
    	p->state = 1;
    	index->state = 0;
    	p->chunk_no = index->chunk_no;
    	index->chunk_no = NULL;
    	for (auto i = page_table.begin(); i != page_table.end(); i++) {
        
    		i->visit++;
    	}
    	p->visit = 0;
    }

exp7.cpp

#include"pcb.h"
    #include<iostream>
    #include<cmath>
    #include<string>
    
    using namespace std;
    
    //内存大小4MB，页面大小4KB
    //创建进程
    bool create(PCB& p) {
        
    	unsigned psize;
    	cout << "请输入进程大小(KB)：";
    	cin >> psize;
    	p.init(psize); //初始化
    	return 0;
    }
    
    //地址转换机构
    void addr_trans(PCB& pro, vector<unsigned>& s) {
        
    	unsigned addr;
    	unsigned page_no, offset;
    	cout << "输入十进制地址：";
    	cin >> addr;
    	page_no = unsigned(addr / 4096);
    	//进行越界检查
    	while (pro.comp(page_no)) {
        
    		cout << "地址越界，重新输入十进制地址：";
    		cin >> addr;
    		page_no = unsigned(addr / 4096);
    	}
    	offset = unsigned(addr % 4096);
    	//访问页表
    	cout << "物理地址为：" << pro.trans(page_no, s) * 4096 + offset << endl;
    }
    
    int main() {
        
    	int choose = 0;
    	PCB pro;
    	vector<unsigned> s;   //记录占用的物理块号
    	cout << "1.创建进程\n"
    		<< "2.显示进程页表\n"
    		<< "3.请求访问\n"
    		<< "4.退出" << endl;
    	while (choose != 4) {
        
    		cout << "\n请选择：";
    		cin >> choose;
    		switch (choose) {
        
    		case 1:
    			if (create(pro))
    				cout << "创建失败！" << endl;
    			else
    				cout << "创建成功！" << endl;
    			break;
    		case 2:
    			pro.disp();
    			break;
    		case 3:
    			addr_trans(pro, s);
    			break;
    		default:
    			break;
    		}
    	}
    	return 0;
    }

# 五、实验结果 #

![实验结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5Nzc0OQ_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5Nzc0OQ_size_16_color_FFFFFF_t_70]: /images/20221021/9eac85e4a51245c785d7173b34c649b4.png