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

清疚 2022-11-05 03:19 3阅读 0赞

注：其他实验见：[点击查看][Link 1]

### 基本分页存储管理 ###

*  一、实验内容及要求
 *  二、实验环境
 *  三、设计思想
 *  四、数据结构
 *  五、实验代码
 *  六、运行结果

# 一、实验内容及要求 #

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

# 二、实验环境 #

windows 10,Visual Studio 2019

# 三、设计思想 #

1.  设内存大小为2GB，页面大小为4KB。
2.  建立进程：由用户输入进程ID与大小，随机数分配各个页面对应的物理块号；
3.  地址变换（十进制）：  
    \[1\] 由用户输入一个十进制的逻辑地址A；  
    \[2\] 则页号为P=INT\[A/L\]，页内地址为d=\[A\] MOD L，L为页面大小（4096）；  
    \[3\] 查询页表，找到页号对应的物理块号B，计算物理地址B×L+d。
4.  地址变换（二进制）：  
    \[1\] 由用户输入一个二进制的逻辑地址A；  
    \[2\] 设页内地址的位数为x,则页号为A>>x,页内地址为A的低x位；  
    \[3\] 查询页表，找到页号对应的物理块号，计算物理地址将物理块号与页内地址拼接即可。

# 四、数据结构 #

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

class PCB {
        
    public:
    	PCB(int a, int b) :id(a), size(b) {
        };
    private:
    	int id;                   //进程编号
    	int size;                 //进程大小
    	int length;               //页表长度
    	vector<int> page_table;   //页表
    public:
    	void init(vector<int> &s);       //给每页分配相应的物理块号
    	void disp();                     //显示页表信息
    	int comp(int a,int b);           //越界检查
    	int comp(bitset<31> a, int b);   //越界检查
    	int trans(int a);                //查询页表
    	int trans(bitset<31> a);         //查询页表
    };

1.  对于二进制的处理，使用bitset<31>结构来进行相关的逻辑移位、按位与或运算、转换成十进制等。

# 五、实验代码 #

#include<vector>
    #include<bitset>
    #include<ctime>
    #include<random>
    #include<cmath>
    #include<iostream>
    #include<string>
    
    using namespace std;
    
    class PCB {
        
    public:
    	PCB(int a, int b) :id(a), size(b) {
        };
    private:
    	int id;                   //进程编号
    	int size;                 //进程大小
    	int length;               //页表长度
    	vector<int> page_table;   //页表
    public:
    	void init(vector<int> &s);       //给每页分配相应的物理块号
    	void disp();                     //显示页表信息
    	int comp(int a,int b);           //越界检查
    	int comp(bitset<31> a, int b);   //越界检查
    	int trans(int a);                //查询页表
    	int trans(bitset<31> a);         //查询页表
    };
    
    //给每页分配相应的物理块号
    void PCB::init(vector<int> &s) {
        
    	int num,a,flag=1;
    	num = size / 4;
    	if (size % 4 != 0) {
        
    		num++;
    	}
    	static uniform_int_distribution<int> u(0, int(pow(2,19)));
    	static default_random_engine e(time(0));
    	while(page_table.size()!=num) {
        
    		a = u(e);
    		for (auto j = s.begin(); j != s.end(); j++) {
            //检查物理块是否被占用
    			if (*j == a) {
        
    				flag = 0;
    				break;
    			}
    		}
    		if (flag) {
        
    			page_table.push_back(a);
    			s.push_back(a);
    		}
    	}
    	length = page_table.size();
    }
    
    //显示页表信息
    void PCB::disp() {
        
    	int no=0;
    	auto i = page_table.begin();
    	while (i != page_table.end()) {
        
    		cout << no << "\t" << *i << endl;
    		no++;
    		i++;
    	} 
    }
    
    //越界检查
    int PCB::comp(int a,int b) {
        
    	if (id!=b)
    		return 1;
    	else if (a > length|| a < 0)
    		return 2;
    	else
    		return 0;
    }
    
    //越界检查
    int PCB::comp(bitset<31> a, int b) {
        
    	if (id != b)
    		return 1;
    	else if (a.to_ulong() > length - 1 || a.to_ulong() < 0)
    		return 2;
    	else
    		return 0;
    }
    
    //查询页表
    int PCB::trans(int a) {
        
    	auto p = page_table.begin();
    	for (int i = 0; i < a; i++) {
        
    		p++;
    	}
    	return *p;
    }
    
    //查询页表
    int PCB::trans(bitset<31> a) {
        
    	auto p = page_table.begin();
    	for (int i = 0; i < int(a.to_ulong()); i++) {
        
    		p++;
    	}
    	return *p;
    }
    
    //内存大小2GB，页面大小4KB
    //创建进程
    bool create(vector<PCB>& pcbs, vector<int>& s) {
        
    	unsigned pid,psize;
    	cout << "请输入进程编号与大小(KB)：";
    	cin >> pid >> psize;
    	if (psize > (524288 - s.size()) * 4) {
        
    		return 1;
    	}
    	pcbs.push_back(PCB(pid, psize));
    	auto p = pcbs.end();
    	p--;
    	p->init(s);
    	return 0;
    }
    
    //显示页表
    void display(vector<PCB> pcbs) {
        
    	int num=1;
    	for (auto i = pcbs.begin(); i != pcbs.end(); i++) {
        
    		cout << "第" << num << "个进程：" << endl;
    		cout << "页号\t" << "块号" << endl;
    		i->disp();
    		num++;
    	}
    }
    
    //地址转换机构1
    bool addr_trans(vector<PCB> pcbs) {
        
    	int no,addr;
    	int chunk_no,offset;
    	auto p = pcbs.begin();
    	cout << "输入转换的进程编号：";
    	cin >> no;
    	cout << "输入十进制地址：";
    	cin >> addr;
    	chunk_no = addr / 4096;
    	//找到进程并进行越界检查
    	while (p!=pcbs.end()&&p->comp(chunk_no, no)) {
        
    		if (p->comp(chunk_no, no) == 1)
    			p++;
    		else if (p->comp(chunk_no, no) == 2) {
        
    			cout << "地址越界，重新输入十进制地址：";
    			cin >> addr;
    			chunk_no = addr / 4096;
    		}	
    	}
    	if (p == pcbs.end()) {
        
    		cout << "未找到该进程！";
    		return 1;
    	}
    	offset = addr % 4096;
    	cout << "对应的物理地址为：" << p->trans(chunk_no)*int(pow(2,12.0)) + offset << endl;
    	return 0;
    }
    
    //地址变换机构2
    bool addr_trans2(vector<PCB> pcbs) {
        
    	bitset<31> addr,chunk_no, offset, s(string("0000000000000000000111111111111"));
    	bitset<31> p_addr;
    	int no;
    	auto p = pcbs.begin();
    	cout << "输入转换的进程编号：";
    	cin >> no;
    	cout << "输入二进制地址：";
    	cin >> addr;
    	chunk_no = addr >> 12;
    	//找到进程并进行越界检查
    	while (p != pcbs.end()&&p->comp(chunk_no, no)) {
        
    		if (p->comp(chunk_no, no) == 1)
    			p++;
    		else if (p->comp(chunk_no, no) == 2) {
        
    			cout << "地址越界，重新输入十进制地址：";
    			cin >> addr;
    			chunk_no = addr >> 12;
    		}
    	}
    	if (p == pcbs.end()) {
        
    		cout << "未找到该进程！";
    		return 1;
    	}
    	offset = addr & s;
    	p_addr = p->trans(chunk_no);
    	p_addr = p_addr << 12;
    	p_addr = p_addr | offset;
    	cout << "对应的二进制物理地址为：" << p_addr 
    		<< "\n转化为十进制为：" << p_addr.to_ulong()
    		<< endl;
    	return 0;
    }
    
    int main() {
        
    	int choose = 0;
    	vector<PCB> pcbs;
    	vector<int> s;   //记录占用的物理块号
    	cout << "1.创建进程\n"
    		<< "2.显示进程页表\n"
    		<< "3.逻辑地址转换（十进制）\n"
    		<< "4.逻辑地址转换（二进制）\n"
    		<< "5.退出" << endl;
    	while (choose != 5) {
        
    		cout << "\n请选择：" ;
    		cin >> choose;
    		switch (choose) {
        
    		case 1:
    			if (create(pcbs,s))
    				cout << "创建失败！" << endl;
    			else
    				cout << "创建成功！" << endl;
    			break;
    		case 2:
    			display(pcbs);
    			break;
    		case 3:
    			if (addr_trans(pcbs)) {
        
    				cout << "转换失败！" << endl;
    			};
    			break;
    		case 4:
    			if (addr_trans2(pcbs)) {
        
    				cout << "转换失败！" << endl;
    			};
    			break;
    		default:
    			break;
    		}
    	}
    	return 0;
    }

# 六、运行结果 #

![运行结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5Nzc0OQ_size_20_color_FFFFFF_t_70]

[Link 1]: https://blog.csdn.net/weixin_44197749/article/details/113704955?spm=1001.2014.3001.5501
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5Nzc0OQ_size_20_color_FFFFFF_t_70]: /images/20221023/3950570dbbaf4b2b857b9918b417c527.png