最佳置换算法c++

2022-05-18 23:41:51

算法思想：

最佳置换算法是一种理想化算法，淘汰未来最长时间内不再被访问的页面，因为未来是无法预测的，所以说是理想化的。

代码如下：

总体来说实现难度不大。

#include<iostream>
#include<vector>
#include<algorithm>
#include<map> 
using namespace std;
vector<int> jincheng;
vector<int> kuai;
map<int, int> m;
int n;    // 页面数
int t;    // 物理块数
int cnt;  // 记录缺页次数 
int maxn = -1;

int main() {
	jincheng.clear();
	kuai.clear(); 
	cout << "请输入页面数量：" << "\n";
	cin >> n;
	cout << "请输入物理块数：" << "\n";
	cin >> t;
	
	cout << "请输入页面序列：" << "\n";
	int x;
	for(int i = 0; i < n; i ++) {
		cin >> x;
		jincheng.push_back(x);
	}
	
	for(int i = 0; i < t; i ++) {
		kuai.push_back(jincheng[i]);
		cout << "这是访问第" << i + 1 << "个页面时的情况:\n";
		for(int i = 0; i < kuai.size(); i ++) {
			cout << kuai[i] << " "; 
		}
		cout << "\n";
	}

	for(int i = t; i < n; i ++) {
		bool flag = false;
		for(int j = 0; j < t; j ++) {
			if(kuai[j] == jincheng[i]) {
				kuai[j] = jincheng[i];
				flag = true;
			}
		}
		if(flag == false) {
			cnt ++;
			m.clear();
			maxn = -1;
			for(int k = 0; k < t; k ++) {
				bool flagg = false;
				for(int r = i + 1; r < n; r ++) {
					if(kuai[k] == jincheng[r]) {
						maxn = max(maxn, r);
						m[r] = k;  // 把物理块里页面的位置在页面序列中的位置存下来 
						flagg = true;
						break;
					}
				}
				if(flagg == false) {
					m[maxn] = k;
					break;
				} 
			}
			kuai[m[maxn]] = jincheng[i];
		}
		
		cout << "这是访问第" << i + 1 << "个页面时的情况:\n";
		for(int i = 0; i < t; i ++) {
			cout << kuai[i] << " "; 
		}
		cout << "\n";
	}
	
	cout << "页面置换次数为：" << "\n";
	cout << cnt << "\n";
	cout << "缺页率为：" << "\n";
	printf("%.2lf\n", 1.0 * cnt / n); 
	
	return 0;
}

更多相关内容

用C++实现LRU页面置换算法
2020-06-03 09:24:22

使用LRU算法实现页面置换算法。LRU算法基于一种假设，长期不使用的数据，在未来的使用性也不大。因此，当数据占用内存达到一定的阙值时，我们要移除最近最少使用的数据。LRU算法中，使用了一种有趣的数据结构，叫做...

收起
操作系统—页面置换算法（C++实现）
2019-05-13 17:37:47

资源包含三个算法：OPT---最佳置换算法、//FIFO---先进先出、//LRU---最近最久未使用操作：用户输入物理块数、页面待要访问的个数、每个页面编号，计算出缺页数、置换数、缺页率语言：C++ 运行环境：Visual ...

收起
操作系统 C++ 页面置换算法（含实验报告）有opt，LRU，先进先出，时钟算法，改进的时钟算法等所有算法
2020-10-04 06:00:14

最佳置换算法（OPT）：选择永不使用或是在最长时间内不再被访问（即距现在最长时间才会被访问）的页面淘汰出内存。用于算法评价参照。随机置换算法（S）：产生一个取值范围在0和N-1之间的随机数，该随机数即可表示...

收起

操作系统--页面置换算法（三种置换算法） C++高效实现附代码

千次阅读 多人点赞 2020-08-17 08:13:29

最佳置换算法 先来先服务置换算法最近最久未使用置换算法代码示例 #include<iostream> #include<algorithm> #include<array> #include<vector> using namespace std; class page_...

运行示例：

物理块大小初始化为4，待IO数据为：1,2,5,7,5,7,1,4,3,5,6,4,3,2,1,5,2

最佳置换算法
先来先服务置换算法
最近最久未使用置换算法

代码示例

#include<iostream>
#include<algorithm>
#include<array>
#include<vector>

using namespace std;

class page_replacement {
private:
	//OPT数据结构
	typedef struct opt {
		int next = 99999; //与此相同的下一个数据
		int order = -1; //页面序号
	}opt;
	//FIFO数据结构
	typedef struct fifo {
		int first = -1; //最早到达页号
		int order = -1; //页面序号
	}fifo;
	//LRU数据结构
	typedef struct lru {
		int recent = 0x80;  //时间戳
		int order = -1;
	}lru;
	//int data;
	
public:
	//构造函数
	page_replacement() {
		cout << "Object is being created!" << endl;
	}//page_replacement
	//析构函数
	~page_replacement() {
		cout << "\nObject is being deleted!" << endl;
	}//~page_replacement
	void OPT();
	void FIFO();
	void LRU();
	void format(int len);
	template<typename T1, typename T2>
	void printResult(int len, int ans, int cnt, T1 &rede, T1 &elim, T2 &block_tencent);
};

array<int, 17>order = { 1,2,5,7,5,7,1,4,3,5,6,4,3,2,1,5,2 };
//array<int, 20>order = { 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 };

//格式调整
void page_replacement::format(int len) {
	for (int i = 0; i < len; i++)
		cout << "- - ";
	cout << endl;
}//format

//page函数模板
template<class T1, class T2>
void page_replacement::printResult(int len, int ans, int cnt, T1 &rede, T1 &elim, T2 &block_content) {
	cout << "物理块页面内容：" << endl;
	format(len);
	for (int i = 0; i < len; i++) {
		if (i == 0)
			cout << "  " << order[i] << " ";
		else
			cout << ": " << order[i] << " ";
	}//for
	cout << endl;
	format(len);
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < block_content.size(); j++) {
			if (block_content[j][i].order == -1) {
				cout << "    ";
				continue;
			}//if
			if (j - 1 >= 0 && block_content[j - 1][i].order == -1 || j == 0)
				cout << "  " << block_content[j][i].order << " ";
			else
				cout << ": " << block_content[j][i].order << " ";
		}//for
		cout << endl;
	}//for
	format(len);
	//迭代器
	cout << "换出页面序列：        ";
	for (auto iter = elim.begin(); iter != elim.end(); iter++)
		cout << iter->order << " ";
	cout << "\n换入页面序列：";
	for (auto iter = rede.begin(); iter != rede.end(); iter++)
		cout << iter->order << " ";
	float result = (float)(ans + cnt) / len;
	cout << "\n缺页次数：" << cnt << " | 页面置换次数：" << ans;
	cout << endl << "缺页率：" << result << endl;
}//printResult

//最佳置换算法
void page_replacement::OPT() {
	int len = order.size();
	int cnt = 0;  //缺页次数
	int ans = 0;  //页面置换
	vector<opt>opt_arr(len);
	vector<opt>rede; //换入
	vector<opt>elim; //换出
	array<opt, 4>block_memory; //物理块
	vector<array<opt, 4>>block_content;

	//初始化opt_arr
	for (int i = 0; i < len; i++) {
		opt_arr[i].order = order[i];
		int index = 0;
		for (int j = i+1; j < len; j++) {
			index++;
			if (opt_arr[i].order == order[j]) {
				opt_arr[i].next = index;
				break;
			}//if
		}//for
		cout << index << " ";
	}//for
	cout << endl;
	//页面调用
	for (int i = 0; i < len; i++) {
		//物理块空间充足
		if (i<4) {
			block_memory[i] = opt_arr[i];
			rede.push_back(opt_arr[i]);
			block_content.push_back(block_memory);
			ans++;
			for (int j = 0; j < i; j++)
				block_memory[j].next -= 1;
			continue;
		}//if
		//物理块空间不足,需要页面置换
		else {
			//如果物理块中存在该页面，直接引用即可
			bool flag = true;
			int index = 0;
			int future = -1;
			int tmp = future;
			for (int j = 0; j < 4; j++) {
				if (block_memory[j].order == opt_arr[i].order) {
					block_memory[j].next = opt_arr[i].next;
					flag = false;
					break;
				}//if
				else {
					tmp = max(tmp, block_memory[j].next);
					if (tmp > future) {
						future = tmp;
						index = j;
					}//if
				}//else
			}//for
			if (flag) {
				//置换页面
				elim.push_back(block_memory[index]);//换出页面
				block_memory[index] = opt_arr[i];
				rede.push_back(opt_arr[i]);//换入页面
				cnt++;  //缺页次数加1
			}//if
			for (int j = 0; j < 4; j++) {
				block_memory[j].next -= 1;
			}//for
			block_content.push_back(block_memory);
		}//else
	}//for
	cout << "\n\nOPT最佳置换算法\n";
	printResult(len, ans, cnt, rede, elim, block_content);
}//OPT

//先来先服务置换算法
void page_replacement::FIFO() {
	int len = order.size();
	int ans = 0;
	int cnt = 0;
	array<fifo, 4>block;  //物理块容量为4
	vector<array<fifo, 4>>block_content;
	vector<fifo>fifo_f(len);
	vector<fifo>elim, rede;

	//初始化
	for (int i = 0; i < len; i++) {
		fifo_f[i].order = order[i];
	}//for
	//页面调用
	for (int i = 0; i < order.size(); i++) {
		//物理块空间充足
		if (i < 4) {
			block[i].order = order[i];
			block[i].first += 1;
			rede.push_back(block[i]);
			block_content.push_back(block);
			for (int j = 0; j < i; j++) {
				block[j].first += 1;
			}//for
			ans++;
			continue;
		}//if
		//物理块空间不足
		else {
			bool flag = true;
			int index = 0;
			int max_fifo = -1;
			int tmp = max_fifo;
			//计算待换出的页面
			for (int j = 0; j < 4; j++) {
				if (block[j].order == fifo_f[i].order) {
					flag = false;
					break;
				}//if
				else {
					tmp = max(tmp, block[j].first);
					if (tmp > max_fifo) {
						max_fifo = tmp;
						index = j;
					}//if
				}//else
			}//for
			//置换页面
			if (flag) {
				elim.push_back(block[index]);
				block[index] = fifo_f[i];
				rede.push_back(fifo_f[i]);
				cnt++;
				for (int j = 0; j < 4; j++) {
					if (j == index)continue;
					block[j].first += 1;
				}//for
			}//if
			block_content.push_back(block);
		}//else
	}//for
	//输出置换结果
	cout << "\n\nFIFO先来先服务置换算法\n";
	printResult(len, ans, cnt, rede, elim, block_content);
}//FIFO

//最近最久未使用置换算法
void page_replacement::LRU() {
	int len = order.size();
	int ans = 0, cnt = 0;
	array<lru, 4>block;  //物理块容量为4
	vector<array<lru, 4>>block_content;
	vector<lru>lru_r(len);
	vector<lru>elim, rede;

	//初始化LRU
	for (int i = 0; i < len; i++) {
		lru_r[i].order = order[i];
	}//for
	//页面调用
	for (int i = 0; i < len; i++) {
		//物理块空间充足
		if (i < 4) {
			block[i] = lru_r[i];
			rede.push_back(block[i]);
			block_content.push_back(block);
			ans++;
			for (int j = 0; j < i; j++)
				block[i].recent >>= 1;
			for (int j = 0; j <= i; j++)
				cout << block[j].recent << " ";
			cout << endl;
		}//if
		//物理块空间不足
		else {
			bool flag = true;
			int last_no_used = 99999;
			int tmp = last_no_used;
			int index = 0;
			for (int j = 0; j < 4; j++)
				block[j].recent >>= 1;
			for (int j = 0; j < 4; j++) {
				if (block[j].order == lru_r[i].order) {
					block[j].recent |= 0x80;
					flag = false;
					break;
				}//if
				else {
					tmp = min(tmp, block[j].recent);
					if (tmp < last_no_used) {
						last_no_used = tmp;
						index = j;
					}//if
				}//else
			}//for
			if (flag) {
				elim.push_back(block[index]);
				rede.push_back(lru_r[i]);
				block[index] = lru_r[i];
				block[index].recent |= 0x80;
				cnt++;
			}//flag
			block_content.push_back(block);
		}//else
	}//for
	//输出置换结果
	cout << "\n\nLRU最近最久未使用置换算法\n";
	printResult(len, ans, cnt, rede, elim, block_content);
}//LRU

int main() {
	page_replacement page_r;
	page_r.OPT();
	page_r.FIFO();
	page_r.LRU();
	system("pause");
	return 0;
}//main

收起

展开全文

操作系统数据结构

页面置换算法（OPT、FIFO、LRU）实现--C++版本-页面置换算法（Optimal、FIFO、LRU）
2019-12-18 10:16:04

该工程具体是在codeblock上面实现了操作系统课程上讲解的页面置换算法，包括先进先出（FIFO）、最佳置换算法（OPT）、最久最近未使用算法（LRU）。具体实现功能有： 1、建立相应的数据结构 2、在屏幕上显示页面...

收起
5种页面置换算法C++实现
2011-06-28 20:10:56

计算并输出下述各种算法在不同内存容量下的命中率。 A. FIFO先进先出的算法 B. LRR最近最少使用算法 C. OPT最佳淘汰算法（先淘汰最不常用的页地址）

收起
OPT最佳页面置换算法
2013-12-19 10:12:29

是OPT算法的C语言实现，希望对你们有帮助！

收起
页面置换算法（OPT、FIFO、LRU）实现--C++版本
2016-09-15 21:46:55

该工程具体是在codeblock上面实现了操作系统课程上讲解的页面置换算法，包括先进先出（FIFO）、最佳置换算法（OPT）、最久最近未使用算法（LRU）。具体实现功能有： 1、建立相应的数据结构 2、在屏幕上显示页面的...

收起
操作系统页面替换算法（OPT最佳置换算法与LRU最近最久未使用算法）
2019-06-27 19:37:59

操作系统页面替换算法（OPT最佳置换算法与LRU最近最久未使用算法）

收起
请求分页储存管理的页置换算法模拟.exe
2021-06-16 15:19:50

C++编写的请求分页储存管理的页置换算法模拟程序，模拟OPT，FIFO和LRU算法。可以输入序列也可以随机生成访问序列。可以输出整个调度的流程（表），缺页次数和缺页率。

收起

操作系统课设(页面置换算法C++版)

2022-01-16 13:23:20

本次设计的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。在进程运行过程中，如果要访问的页面不在内存，就须将此页面调入内存，但当内存已无...

运行结果

（1）data.txt文本文件：

请添加图片描述

                             图1 输入文件

将页面引用串输入到名为data.txt的文本文件中，以空格隔开。

（2）各种置换算法的输出结果：
请添加图片描述

                       图2 OPT页面置换算法运行结果

请添加图片描述

                      图3 FIFO页面置换算法运行结果

请添加图片描述

                        图4 LRU页面置换算法运行结果

请添加图片描述

                      图5 Clock页面置换算法运行结果

请添加图片描述

                       图6 LRU页面置换算法运行结果

完整代码

#include <iostream>
#include <vector>
#include <string>
#include <fstream>

#define random(a,b) (rand()%(b-a)+a)

using namespace std;

// 总虚页数
int t;
// 实页数
int size;
// 序列
vector<int> v;

// 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
void print(vector<pair<int, vector<int>>> res, int lackPageNum, int totalNum){

    for (int i = 0; i < size; ++i) {

        // 遍历每一个序列的第i个数
        for (int j = 0; j < res.size(); ++j) {
            printf("|");
            pair<int, vector<int>> cur = res[j];

            int isLack = cur.first;
            vector<int> v = cur.second;
            if(!isLack || v.size() < (i + 1)){
                printf("   ");
            }else{
                printf("%3d", v[i]);
            }
            printf("  ");
        }
        puts("|");
    }

    printf("缺页数为：%d\n", lackPageNum);
    printf("命中数：%d\n", (totalNum - lackPageNum));
    printf("缺页率为：%.3f%%\n", (lackPageNum * 100.0 / totalNum));
    printf("命中率为：%.3f%%\n", ((totalNum - lackPageNum) * 100.0 / totalNum));
}

void FIFO(){

    // 结果<是否缺页,页面>
    vector<pair<int, vector<int>>> res;

    // 上一页
    vector<int> pre;

    // 判断是否缺页的
    bool flag;

    int lackPageNum = 0;

    for(int num: v){

        flag = true; // 是否缺页

        for (int i = 0; i < pre.size(); ++i) {
            if(num == pre[i]){
                flag = false;
            }
        }

        if(!flag){
            res.push_back(make_pair(0, vector<int>(pre.begin(), pre.end())));
            continue;
        }

        lackPageNum++;

        if(pre.size() < size){

            pre.push_back(num);

        }else{

            // 缺页则换出队头
            pre.erase(pre.begin());
            pre.push_back(num);
        }

        res.push_back(make_pair(1, vector<int>(pre.begin(), pre.end())));
    }

    printf("FIFO(先进先出)算法：\n");
    print(res, lackPageNum, t);
    puts("");
    puts("");
}

void LRU(){

    // <是否缺页,页面>
    vector<pair<int, vector<int>>> res;

    // 上一页
    vector<int> pre;

    // 判断是否缺页的
    bool flag;
    // 缺页数
    int lackPageNum = 0;

    // 当前页在队中那个位置
    int idx = 0;

    for(int num: v){

        flag = true; // 是否缺页

        for (int i = 0; i < pre.size(); ++i) {
            if(num == pre[i]){
                flag = false;
                idx = i;
            }
        }

        if(!flag){
            // 换到队头
            pre.erase(pre.begin() + idx);
            pre.insert(pre.begin(), num);
            res.push_back(make_pair(0, vector<int>(pre.begin(), pre.end())));
            continue;
        }

        lackPageNum++;

        if(pre.size() < size){
            pre.insert(pre.begin(), num);
        }else{
            // 缺页则换出队尾
            pre.erase(pre.end()-1);
            pre.insert(pre.begin(), num);
        }

        res.push_back(make_pair(1, vector<int>(pre.begin(), pre.end())));
    }

    printf("LRU(最近最久未使用)算法：\n");
    print(res, lackPageNum, t);
    puts("");
    puts("");
}

void OPT(){

    // <是否缺页,页面>
    vector<pair<int, vector<int>>> res;

    // 上一页
    vector<int> pre;

    // 判断是否缺页的
    bool flag;
    // 缺页数
    int lackPageNum = 0;

    for(int k = 0; k < v.size(); k++){

        int num = v[k];
        flag = true; // 是否缺页

        for (int i = 0; i < pre.size(); ++i) {
            if(num == pre[i]){
                flag = false;
            }
        }

        if(!flag){
            res.push_back(make_pair(0, vector<int>(pre.begin(), pre.end())));
            continue;
        }

        lackPageNum++;

        if(pre.size() < size){
            pre.push_back(num);
        }else{
            // 最后面的数在v中的位置
            int last = -1;
            // 最后面的数在pre中的位置
            int idx;
            // 当前pre[i] 是否存在与v中
            bool isExit;
            // 缺页则换出pre中在v序列最后面的或者不在后面的序列的
            for (int i = 0; i < pre.size(); ++i) {
                isExit = false;
                for (int j = k + 1; j < v.size(); ++j) {
                    if(pre[i] == v[j]){
                        isExit = true;
                        if(j > last){
                            idx = i;
                            last = j;
                        }
                        break;
                    }
                }
                // 当前pre[i] 根本不在v中,则直接退出循环
                if(!isExit){
                    idx = i;
                    break;
                }
            }

            pre.erase(pre.begin() + idx);
            pre.insert(pre.begin()+ idx, num);
        }

        res.push_back(make_pair(1, vector<int>(pre.begin(), pre.end())));
    }

    printf("OPT(最佳)置换算法：\n");
    print(res, lackPageNum, t);
    puts("");
    puts("");
}

void setToOne(int &num, int idx){
    num = num + (1 << idx);
}

// 统一右移
void rightMove(vector<pair<int, int>> & visNum){

//    puts("");
    for(pair<int, int> &p: visNum){
//        printf("%d ", p.second);
        p.second = p.second >> 1;
    }

//    puts("");
}
// 判断是否在visNum中
bool isExit(vector<pair<int, int>> & visNum, int num){
    for(pair<int, int> &p: visNum){
        if(p.first == num){
            return true;
        }
    }
    return false;
}
// 找到某个数在队列中的索引
int findIdx(vector<pair<int, int>> & visNum, int num){
    for (int i = 0; i < visNum.size(); ++i) {
        pair<int, int> p = visNum[i];
        if(p.first == num){
            return i;
        }
    }
    return -1;
}

// 找到 freq 最小的在 pre 中的位置
int findMinIdx(vector<pair<int, int>> visNum, vector<int> pre){

    int id = -1;
    int min = (1 << 31) - 1;

    for (int i = 0; i < pre.size(); ++i) {
        for (int j = 0; j < visNum.size(); ++j) {
            pair<int, int> p = visNum[j];
            if(pre[i] == p.first && p.second < min){
                id = i;
                min = p.second;
            }
        }
    }
    return id;
}

void LFU(){

    vector<pair<int, vector<int>>> res;
    vector<int> pre;

    // 记录访问频率<数, 频率>
    vector<pair<int, int>> visNum;
    int lackPageNum = 0;

    for (int num: v) {

        bool flag = true;
        rightMove(visNum);

        for (int i = 0; i < pre.size(); ++i) {
            if(pre[i] == num){
                flag = false;
            }
        }

        if(!flag){
            int idx = findIdx(visNum, num);
            setToOne(visNum[idx].second, 30);
            res.push_back(make_pair(0, vector<int>(pre.begin(), pre.end())));
            continue;
        }

        lackPageNum++;

        bool isEx = isExit(visNum, num);

        if(pre.size() < size){
            pre.push_back(num);
            visNum.push_back({num, (1 << 30)});
        }else{

            if(!isEx){
                visNum.push_back({num, (1 << 30)});
            }else{
                int idx = findIdx(visNum, num);
                setToOne(visNum[idx].second, 30);
            }

            int idx = findMinIdx(visNum, pre);

            pre.erase(pre.begin() + idx);
            pre.push_back(num);
        }

        res.push_back(make_pair(1, vector<int>(pre.begin(), pre.end())));
    }

    printf("LFU(最少使用)置换算法：\n");
    print(res, lackPageNum, t);

    puts("");
    puts("");
}

// 1 3 4 2 5 6 3 4 7
void CLK(){

    vector<pair<int, vector<int>>> res;

    vector<int> pre;
    int vis[t + 5];

    int lackPageNum = 0;
    bool flag;

    // 指针
    int idx = 0;

    for (int num: v) {
        flag = true;
        for (int i = 0; i < pre.size(); ++i) {
            if(pre[i] == num){
                vis[i] = 1;
                flag = false;
            }
        }

        if(!flag){
            res.push_back(make_pair(0, vector<int>(pre.begin(), pre.end())));
            continue;
        }

        lackPageNum++;

        if(pre.size() < size){
            pre.push_back(num);
            vis[pre.size()-1] = 1;
        }else{

            while (true){

                if(!vis[idx]){
                    pre.erase(pre.begin() + idx);
                    pre.insert(pre.begin() + idx, num);
                    vis[idx] = 1;
                    idx = (idx + 1) % size;
                    break;
                }

                vis[idx] = 0;
                idx = (idx + 1) % size;
            }
        }

        res.push_back(make_pair(1, vector<int>(pre.begin(), pre.end())));
    }

    printf("NRU(最近未用)置换算法：\n");
    print(res, lackPageNum, t);

    puts("");
    puts("");
}


void init1(){

    printf("可用物理块大小：");
    scanf("%d", &size);
    printf("调入序列长度：");
    scanf("%d", &t);

    int num;

    printf("请输入调入页面序列：");

    printf("");
    for (int i = 0; i < t; ++i) {
        scanf("%d", &num);
        v.push_back(num);
    }
}

void init2(){

    ifstream df("../data.txt");

    if (!df.is_open()){

        cout << "Error opening file";
        exit (1);
    }
    df >> size;
    df >> t;
    int num;
    for (int i = 0; i < t; ++i) {
        df >> num;
        v.push_back(num);
    }

    df.close();
}

void init3(){

    int a = 1, b = 10;
    size = 3;
    t = 20;
    int num;

    for (int i = 0; i < t; ++i) {
        num = random(a, b);
        v.push_back(num);
    }
}

int main(){

//    int num = 1;
//    setToOne(num, 4);
//    cout << num;

//    init1();
    init2();
//    init3();

    printf("\n\n\n访问序列：");
    for (int i = 0; i < v.size(); ++i) {
        printf("%d  ", v[i]);
    }

    puts("");

    FIFO();
    LRU();
    OPT();
    LFU();
    CLK();


    // Test
//    vector<pair<int, int>> vp;
//    vp.push_back({3, 8});
//    rightMove(vp);
//    setToOne(vp[0].second, 30);
//    cout << vp[0].second;

    return 0;
}

收起

展开全文

操作系统

操作系统页面置换算法在C++中的实现

千次阅读 2021-05-19 19:58:37

本代码的目的是通过请求页式管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。代码实现头文件及宏定义 #include<iostream> #include<time.h> #include<...

操作系统存储管理在C++中的实现

存储管理代码简介

存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。
本代码的目的是通过请求页式管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。
在这里插入图片描述

代码实现

头文件及宏定义

#include<iostream>
#include<time.h>
#include<string>
#include<map>
using namespace std;
#define random(x) rand()%(x)

由于要使用字符串定义来增强用户使用的可观方便性，输入字符串（比如：FIFO、LRU）会比输入数字（比如：1、2、3）更容易理解和操作，所以引入头文件string。
我们还需使用map来构建数据结构，因为map的一一对应的优越性，不但可以保存指令号还可以保存在指令流中的序号，大大增强代码的内聚性，所以这里我们引入map头文件。
另外，我们需要用到随机数给出每个指令构建指令流，所以添加宏定义，方便后续代码随机数的使用，也提高代码的可读性。
同时需要插入头文件time.h作为随机数种子，让随机数真正随机。

指令流模块

我们分析程序的要求后发现，对于随机生成的页面流并不是完全随机那么简单的，我们需要让①50%的指令是顺序执行的②25%的指令是均匀分布在前地址部分③25%的指令是均匀分布在后地址部分。
这里我解释一下定义的指令，指令其实就是划分更细的页面，可以理解为0到9指令都算页面0,10到19都算页面1，如此下去直到页面31，总共32页。
正是因为指令划分的比较细，防止完全随机的数会引起无论什么算法页面一直在置换，失去模拟的意义，所以才引入了对随机数的要求。具体代码如下：

srand(time(NULL));
	multimap<int, int>insstream;
	int count = 0;
	while (count < 320) {
		int m = random(319);
		count++;
		insstream.insert(pair<int, int>(count,m+1));
		int m1 = random(m + 1);
		count++;
		insstream.insert(pair<int, int>(count, m1));
		count++;
		insstream.insert(pair<int, int>(count, m1+1));
		int m2 = random(319 - (m1 + 2) + 1) + m1 + 2;
		count++;
		insstream.insert(pair<int, int>(count, m2));
	}
	for (auto ins = insstream.begin(); ins != insstream.end(); ins++)
		cout << ins->second<<" ";

这里我们首先在代码的最开始定义随机数种子，让随机数完全随机。
再定义一个map数据结构来存储页面流，名为insstream（指令流）。
然后定义一个计数器，用于对指令计数，不仅可以在map里逐个标出指令顺序，还可以用于循环限制条件，控制循环结束。
然后按照前面的要求生成随机数，首先生成0-319的随机数，由于下面要让这个数+1作为指令号进入指令流，所以这里我定义为0-318取随机数，防止指令上溢；那么下溢问题呢，验算一下发现即使取0也不影响后续指令的选取，不会下溢。
这边注意我们要在每个指令插入指令流map之前就将count++，否则对应在map里的first值将不正确对应指令执行序号。
对于想要生成n~m的数，我们就用这个公式random（m-n+1）+n。所以这里要生成[m’+2,319]的随机指令就是random(319 - (m1 + 2) + 1) + m1 + 2。
在循环外我们使用迭代器来输出整个指令流检查是否正常运行，运行如下：
在这里插入图片描述

页面流模块

按照我们之前说的，指令流只是对于现实情况更加细致的模拟，而真正的页面置换依然是建立在页面的层面的，所以我们需要将刚刚的指令流转化为页面流。具体代码如下：

multimap<int, int>pagestream;
	for (auto ins = insstream.begin(); ins != insstream.end(); ins++)
		pagestream.insert(pair<int, int>(ins->first, ins->second/10));
	for (auto page = pagestream.begin(); page != pagestream.end(); page++)
		cout << page->second << " ";

同样地，我们建立一个名为pagestream（页面流）的map数据结构，用迭代器迭代指令流里每个指令转化为对应的页面：我们观察发现页面号刚好为指令号/10并且去掉小数部分，所以我们将pagestream的map依然定义为int int，这样可以直接将每个指令/10就得到对应的页面号。
在循环外我们也使用迭代器来输出整个页面流检查是否正常运行，运行如下：
在这里插入图片描述

选择模块

string choose;
	cout << "*************************************************" << endl;
	cout << "欢迎使用本程序~" << endl;
	int allocation = random(6 - 3 + 1) + 3;
	cout << "本次分配的物理块数为：" << allocation << "块！" << endl;
	while (true) {
		cout << "请选择您需要的算法（FIFO、LRU、OPT、LFR）：" << endl;
		cout << "或输入S或s停止程序~" << endl;
		cin >> choose;
		double miss = 0;
		map<int, int>run;
		if (choose == "FIFO" || choose == "fifo") {
		
		}
		else if (choose == "LRU" || choose == "lru") {

		}
		else if (choose == "OPT" || choose == "opt") {

		}
		else if (choose == "LFR" || choose == "lfr") {

		}
		else if (choose == "S" || "s") { break; }
		else {
			cout << "您的输入有误！请输入：FIFO、LRU、OPT、LFR中的一个！" << endl;
		}
	}
	cout << "感谢您的使用~祝您生活愉快！" << endl;
	cout << "*************************************************" << endl;
}

对于选择模块需要注意的就是界面的可观性强，以及要考虑到用户输入错误以及大小写问题，我们需要提升代码的鲁棒性。
另外，在这一模块，我们将物理块数随机为3~6块，方便后续算法的编写。
同时，再定义出名为run的map数据结构，用来存放当前在物理块中的页面。

先进先出算法（FIFO）模块

if (choose == "FIFO" || choose == "fifo") {
			for (auto page = pagestream.begin(); page != pagestream.end(); page++)
			{
				for (auto r = run.begin(); r != run.end(); r++)
				{
					if (r->second == page->second) { goto skip; }
				}
				run.insert(pair<int, int>(page->first, page->second));
				miss++;
				if (run.size() > allocation)
					run.erase(run.begin());
			skip:
				cout << "";
				/*检测运行流
				for (auto r = run.begin(); r != run.end(); r++)
					cout << r->second << " ";
				cout << endl;
				*/
			}
			cout << "页面命中率=" << 1 - (miss / 320) << endl;
		}

首先我们先在最外层构建一个pagestream页面流的迭代器，用于逐个判断页面流中的页面。
在里面嵌套一层run物理块的迭代器，用于逐个判断当前页面是否和物理块中有相同的页面，如果有就直接不插入，并且跳出run迭代器的循环。
注意：一个容器的迭代器中不能给该容器插入或删除元素，否则会破坏迭代器结构，引起xtree报错或者运行结果始终不对！！！
所以这就是为什么我们这里使用goto的原因，因为插入不能在迭代器中完成，所以我们写在run迭代器的外层，并且用goto在页面命中时跳过插入语句。
这里的skip: cout << "";是为了做一个标记，并没有实际运转，如果没有这个cout就会报错。
检测运行流部分可以将注释符号删除来观察运行过程中物理块中的页面变化过程。
最后输出一个页面命中率即可，计算方式在本文开头有。

最近最久未访问算法（LRU）模块

else if (choose == "LRU" || choose == "lru") {
			for (auto page = pagestream.begin(); page != pagestream.end(); page++)
			{
				for (auto r = run.begin(); r != run.end(); r++)
				{
					if (r->second == page->second) {
						run.erase(r);
						goto skip2;
					}
				}
				miss++;
			skip2:
				run.insert(pair<int, int>(page->first, page->second));
				if (run.size() > allocation)
					run.erase(run.begin());
				/*检测运行流
				for (auto r = run.begin(); r != run.end(); r++)
					cout << r->second << " ";
				cout << endl;
				*/
			}
			cout << "页面命中率=" << 1 - (miss / 320) << endl;
		}

对于LRU算法，我们的思路就是，无论来的页面有没有和物理块中的重复，都要插入，因为这样可以将该页面的序号变大，从而排在run运行流的最尾端，实现LRU算法的思想。
在页面有重复时，删除掉物理块中该页面的数据，再插入页面号相同但在运行流中序号不同的数据；若没有重复，还是正常插入。
这里可以在迭代器中删除元素的原因是删除后直接goto跳出了循环，不再迭代，也就不考虑破坏迭代器结构了~

最佳淘汰算法（OPT）模块

else if (choose == "OPT" || choose == "opt") {
			for (auto page = pagestream.begin(); page != pagestream.end(); page++)
			{
				for (auto r = run.begin(); r != run.end(); r++)
				{
					if (r->second == page->second) { goto skip3; }
				}
				if (run.size() == allocation) {
					multimap<int, int>length;
					for (auto r = run.begin(); r != run.end(); r++) {
						for (auto page2 = page; page2 != pagestream.end(); page2++) {
							if (r->second == page2->second) {
								int len = page2->first - page->first;
								length.insert(pair<int, int>(len, r->first));
								break;
							}
							if (page2 == pagestream.find(pagestream.size())) {
								int len = 321 - page->first;
								length.insert(pair<int, int>(len, r->first));
								break;
							}
						}
					}
					auto last = length.rbegin(); 
					if (last != length.rend()) {
						auto r = run.find(last->second);
						if (r != run.end()) {
							run.erase(r);
						}
					}
				}
				run.insert(pair<int, int>(page->first, page->second));
				miss++;
			skip3:
				cout << "";
				/*检测运行流
				for (auto r = run.begin(); r != run.end(); r++)
					cout << r->second << " ";
				cout << endl;
				*/
			}
			cout << "页面命中率=" << 1 - (miss / 320) << endl;
		}

OPT算法是比较复杂的，他的思路并不像FIFO和LRU那么简单，除了判断新来的页面是否已经存在于物理块中，它还需要我们在需要发生置换时判断每个在物理块中的页面下一次出现与现在的“距离”。
判断是否相等依然用和前面一样的goto语句，可以快速跳出多重迭代器，简化代码。
这里当需要置换时我们并不能先插入后删除，因为需要给物理块中每个页面判断距离，如果先插入很可能会又被删除，很明显不符合页面置换算法。
所以判断条件变为了run.size() == allocation而不是上面的>。
在条件成立时，我们建立一个新的multimap（长度可能会相同，为了防止数据丢失，必须使用multimap）名为length用于存放物理块中每个物理块从当前位置到下一次出现的距离。

if (r->second == page2->second) {
	int len = page2->first - page->first;
	length.insert(pair<int, int>(len, r->first));
	break;
}
if (page2 == pagestream.find(pagestream.size())) {
	int len = 321 - page->first;
	length.insert(pair<int, int>(len, r->first));
	break;
}

这个两个语句是计算每个物理块中的页面从当前位置到下次出现的距离，如果不出现，距离就是总页面数（320）+1再减去当前位置。
把距离作为key值存放入length中，这样可以利用map的自动排序，将最久不会出现的页面放在最末端，将r->first（物理块中页面序号，同时也是run的key值）作为value值，这样我们需要删除run中元素时就可以轻松调用key值去删除。

auto last = length.rbegin(); 
					if (last != length.rend()) {
						auto r = run.find(last->second);
						if (r != run.end()) {
							run.erase(r);
						}
					}

这个模块特别重要！是一个对map深层的理解，如果不清楚这个可能会一直报错出错，还找不到任何逻辑错误！！！
当我们需要调用length最后一个元素的value值时，我们首先要找到它的迭代器，由于迭代器中的end()并不是指向末尾元素的，而是末尾元素的下一位，所以我们需要用我这里的定义才能正确返回length末尾元素的迭代器。有的教程会说，直接定义auto last = length.end();last--;就可以了，实际上这样很容易报错，提示调用了无效的参数，建议按照我的定义来，亲测不报错。
找到length末尾元素的迭代器后，再利用它的value值作为寻找run中key值的中间量，从而删除掉最久不会出现的元素。
成功删除后便可以插入了，然后缺页数miss++自增，最后在整个迭代器外计算命中率。

最近最少访问算法（LFU）模块

else if (choose == "LFU" || choose == "lfu") {
			for (auto page = pagestream.begin(); page != pagestream.end(); page++)
			{
				for (auto r = run.begin(); r != run.end(); r++)
				{
					if (r->second == page->second) { goto skip4; }
				}
				if (run.size() == allocation) {
					int time = 0;
					multimap<int, int>times;
					for (auto r = run.begin(); r != run.end(); r++) {
						for (auto page2 = pagestream.begin(); page2 != page; page2++) {
							if (r->second == page2->second) {
								time++;
							}
						}
						times.insert(pair<int, int>(time, r->first));
						time = 0;
					}
					run.erase(times.begin()->second);
				}
				run.insert(pair<int, int>(page->first, page->second));
				miss++;
			skip4:
				cout << "";
				/*检测运行流
				for (auto r = run.begin(); r != run.end(); r++)
					cout << r->second << " ";
				cout << endl;
				*/
			}
			cout << "页面命中率=" << 1 - (miss / 320) << endl;

LFU算法的实现和OPT非常相似，基本上稍微改一些就能实现了。
讲一下唯一的不同点：OPT算法是对于物理块中的页面检测后面再出现的距离，而LFU是检测前面出现的次数，OPT遍历当前位置的后面，LFU遍历前面。
我们只需要类似OPT地定义一个名为times的multimap来存放物理块中页面出现的次数即可。其余部分和OPT基本一致。

源代码及运行过程图片

下面是完善界面后的源代码，以及一次运行的过程截图：

#include<iostream>
#include<time.h>
#include<string>
#include<map>
using namespace std;
#define random(x) rand()%(x)
int main()
{
	srand(time(NULL));
	map<int, int>insstream;
	int count = 0;
	while (count < 320) {
		int m = random(319);
		count++;
		insstream.insert(pair<int, int>(count, m + 1));
		int m1 = random(m + 1);
		count++;
		insstream.insert(pair<int, int>(count, m1));
		count++;
		insstream.insert(pair<int, int>(count, m1 + 1));
		int m2 = random(319 - (m1 + 2) + 1) + m1 + 2;
		count++;
		insstream.insert(pair<int, int>(count, m2));
	}
	/*检测指令流
	for (auto ins = insstream.begin(); ins != insstream.end(); ins++)
		cout << ins->second << " ";
		*/
	map<int, int>pagestream;
	for (auto ins = insstream.begin(); ins != insstream.end(); ins++)
		pagestream.insert(pair<int, int>(ins->first, ins->second / 10));
	//检测页面流
	cout << "页面流如下：" << endl;
	for (auto page = pagestream.begin(); page != pagestream.end(); page++)
	{
		cout << page->second << " ";
		if (page->first % 32 == 0) { cout << endl; }
	}
	string choose;
	cout << "*************************************************" << endl;
	cout << "欢迎使用本程序~" << endl;
	int allocation = random(6 - 3 + 1) + 3;
	cout << "本次分配的物理块数为：" << allocation << "块！" << endl;
	while (true) {
		cout << "请选择您需要的算法（FIFO、LRU、OPT、LFU）：" << endl;
		cout << "或输入S或s停止程序~" << endl;
		cin >> choose;
		double miss = 0;
		map<int, int>run;
		if (choose == "FIFO" || choose == "fifo") {
			for (auto page = pagestream.begin(); page != pagestream.end(); page++)
			{
				for (auto r = run.begin(); r != run.end(); r++)
				{
					if (r->second == page->second) { goto skip; }
				}
				run.insert(pair<int, int>(page->first, page->second));
				miss++;
				if (run.size() > allocation)
					run.erase(run.begin());
			skip:
				cout << "*****************" << endl;
				//检测运行流
				for (auto r = run.begin(); r != run.end(); r++)
					cout << r->second << " ";
				cout << endl;
			}
			cout << "*********************" << endl;
			cout << "FIFO算法的页面命中率=" << 1 - (miss / 320) << endl;
			cout << "*********************" << endl;
		}
		else if (choose == "LRU" || choose == "lru") {
			for (auto page = pagestream.begin(); page != pagestream.end(); page++)
			{
				for (auto r = run.begin(); r != run.end(); r++)
				{
					if (r->second == page->second) {
						run.erase(r);
						goto skip2;
					}
				}
				miss++;
			skip2:
				run.insert(pair<int, int>(page->first, page->second));
				if (run.size() > allocation)
					run.erase(run.begin());
				//检测运行流
				cout << "*****************" << endl;
				for (auto r = run.begin(); r != run.end(); r++)
					cout << r->second << " ";
				cout << endl;
			}
			cout << "*********************" << endl;
			cout << "LRU算法的页面命中率=" << 1 - (miss / 320) << endl;
			cout << "*********************" << endl;
		}
		else if (choose == "OPT" || choose == "opt") {
			for (auto page = pagestream.begin(); page != pagestream.end(); page++)
			{
				for (auto r = run.begin(); r != run.end(); r++)
				{
					if (r->second == page->second) { goto skip3; }
				}
				if (run.size() == allocation) {
					multimap<int, int>length;
					for (auto r = run.begin(); r != run.end(); r++) {
						for (auto page2 = page; page2 != pagestream.end(); page2++) {
							if (r->second == page2->second) {
								int len = page2->first - page->first;
								length.insert(pair<int, int>(len, r->first));
								break;
							}
							if (page2 == pagestream.find(pagestream.size())) {
								int len = 321 - page->first;
								length.insert(pair<int, int>(len, r->first));
								break;
							}
						}
					}
					auto last = length.rbegin(); 
					if (last != length.rend()) {
						auto r = run.find(last->second);
						if (r != run.end()) {
							run.erase(r);
						}
					}
				}
				run.insert(pair<int, int>(page->first, page->second));
				miss++;
			skip3:
				cout << "*****************" << endl;
				//检测运行流
				for (auto r = run.begin(); r != run.end(); r++)
					cout << r->second << " ";
				cout << endl;
				
			}
			cout << "*********************" << endl;
			cout << "OPT算法的页面命中率=" << 1 - (miss / 320) << endl;
			cout << "*********************" << endl;
		}
		else if (choose == "LFU" || choose == "lfu") {
			for (auto page = pagestream.begin(); page != pagestream.end(); page++)
			{
				for (auto r = run.begin(); r != run.end(); r++)
				{
					if (r->second == page->second) { goto skip4; }
				}
				if (run.size() == allocation) {
					int time = 0;
					multimap<int, int>times;
					for (auto r = run.begin(); r != run.end(); r++) {
						for (auto page2 = pagestream.begin(); page2 != page; page2++) {
							if (r->second == page2->second) {
								time++;
							}
						}
						times.insert(pair<int, int>(time, r->first));
						time = 0;
					}
					run.erase(times.begin()->second);
				}
				run.insert(pair<int, int>(page->first, page->second));
				miss++;
			skip4:
				cout << "*****************" << endl;
				//检测运行流
				for (auto r = run.begin(); r != run.end(); r++)
					cout << r->second << " ";
				cout << endl;
			}
			cout << "*********************" << endl;
			cout << "LFU算法的页面命中率=" << 1 - (miss / 320) << endl;
			cout << "*********************" << endl;
		}
		else if (choose == "S" || "s") { break; }
		else {
			cout << "您的输入有误！请输入：FIFO、LRU、OPT、LFU中的一个！" << endl;
		}
	}
	cout << "感谢您的使用~祝您生活愉快！" << endl;
	cout << "*************************************************" << endl;
}

在这里插入图片描述

总结

对于页面置换算法在C++中实现会比进程调度以及银行家算法都要困难很多，数据结构的定义以及算法的选择都很重要。map这种一一对应的容器可以很好地存放页面的数据，对于map调用的底层规则在本文也有细节讲述，希望能给大家一些帮助。

收起

展开全文

fifo lru map

【操作系统】页面置换算法的c++实现
千次阅读 2020-12-14 22:53:46

页面置换算法实验本次实验一共用到了两个封装的类。一个是作业的类，Block，其中的属性包括其中存入的页面的页号，和布尔类型的是否为空的属性。另一个是pageRaplacing类，用来进行页面置换算法。包括页面数组...

收起

操作系统
操作系统——页面置换算法c++的实现（fifo和lru）
千次阅读 2019-12-07 14:17:03

1、首先建立本次实验的流程图： 1、然后建立储存相应...其中name表示页面名，nomber在lru算法中起到标记时间的作用 2、设置一个指针，在fifo算法中指向最老进程 Physicalblock *p=pb;//指向最老进程的指针 3、...

收起

操作系统
【南邮操作系统实验】页面置换算法（FIFO、LRU、OPT） C++ 版
千次阅读 2019-12-01 01:06:18

写好了 Java 版和 Python 版的… ...FIFO 页面置换算法： #include<bits/stdc++.h> // 怕麻烦直接引万能头 using namespace std; int main(){ int pageFrameNum; // 物理页框数 int pageFront...

收起

操作系统实验操作系统
页面置换算法 c++
2011-12-15 22:22:56

(1) 最佳适应(Optimal)页面置换算法； (2) 先进先出(FIFO)页面置换算法； (3) 最近最久未使用(LRU)页面置换算法； (4) 最少使用(LFU)页面置换算法。要求可适用于键盘输入和自动产生随机页面走向序列两种数据...

收起

FIFO LRU
操作系统实验报告用C++实现页面置换算法，LRU与FCFS
2017-12-02 22:11:57

操作系统实验报告，用C++实现最近最久未使用LRU,先来先服务页面置换算法FIFO

收起
页面置换算法（最佳置换算法(OPT) 、先进先出置换算法(FIFO) 、最近最久未使用置换算法(LRU) 、时钟置换...
千次阅读 2021-09-01 02:20:25

文章目录前言知识总览最佳置换算法（OPT）先进先出置换算法（FIFO）最近最久未使用置换算法（LRU)时钟置换算法（CLOCK)改进型的时钟置换算法知识回顾与重要考点前言此篇文章是我在B站学习时所做的笔记，大部分图片...

收起

先进先出置换算法时钟置换算法改进型时钟置换算法
磁盘调度算法C++ 模拟FIFO，OPI和LRU页面置换算法的工作过程
2011-06-19 15:53:08

模拟先进先出FIFO，最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程报告册和源程序

收起
页面置换算法的模拟实现及命中率对比
2020-02-02 07:00:17

模拟实现 OPT（最佳置换）、FIFO 和 LRU 算法，并计算缺页率。示三、要求及提示本题目必须单人完成。 1、首先用随机数生成函数产生一个“指令将要访问的地址序列”，然后将地址序列变换成相应的页地址流（即页...

收起
页面置换算法——C/C++实现 [ OTP, FIFO, LRU, LFU + 开源代码 + 详细解析]
千次阅读 多人点赞 2021-12-24 14:15:11

关键字：C/C++实现、页面置换算法、最佳置换算法（OPT）、先进先出算法（FIFO）、最近最久未使用算法（LRU）、最不经常使用算法（LFU）、操作系统

收起

c语言操作系统
操作系统页面置换算法之最佳(OPT)置换算法（C语言实现）
千次阅读 2020-12-09 22:12:35

最佳(OPT)置换算法 #include <iostream> int accessPage[20] = { 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 }; int flagOPT[3] = { -1,-1,-1 }; // 用来在OPT算法中标记三个物理块是否有页面；-1：物理...

收起

操作系统
clock页面置换算法
2013-06-22 08:47:31

简单的clock页面置换算法 采用CLOCK置换算法仿真请求分页系统 1、设计目的：用高级语言编写和调试一个内存分配程序，加深对内存分配算法的理解。 2、设计要求： 1) 实现请求分页存储管理方式的页面置换算法：...

收起

clock
操作系统课程设计页面置换算法FIFO和 LRU
2018-08-14 08:27:10

这是一个自己完成软件工程的操作系统课程课程设计题目：此程序用于模拟虚拟磁盘页面置换算法，实现了FIFO页面置换算法和LRU页面置换算法，获得课程设计优秀的好成绩

收起
页面置换算法；最佳置换算法、先进先出置换算法、最近最久未使用置换算法
万次阅读 多人点赞 2018-06-20 12:32:11

2. 掌握请求页式存储管理的页面置换算法，如最佳（Optimal）置换算法、先进先出（Fisrt In First Out）置换算法和最近最久未使用（LeastRecently Used）置换算法。二、实验内容设计模拟实现OPT、FIFO和LRU页面置换...

收起

操作系统
[操作系统]页面置换算法实验及C++实现(OPT、FIFO、LRU)
2022-06-16 08:06:19

进程运行时，若其访问的页面不再内存中而需将其调入，但内存已无空闲空间时，就需要从内存中调出一页程序或数据，送入磁盘的对换区。选择调出页面的算法就称为页面置换算法。

收起

开发语言操作系统
页面置换算法（FIFO , LRU, OPT）（C++实现模拟）
万次阅读 2018-06-27 11:40:07

第一个数表示使用什么页面置换算法。 1 表示FIFO. 2 表示LRU 3 表示OPT 第二个是什么操作： get A，B表示运行完第A个序列之后，B在也页表中么？在就输出1，否则0。 pf A表示的是，运行...

收起

fifo lru
模拟实现请求分页存储管理——最佳置换算法
2009-03-07 23:26:32

最佳置换算法 struct b {int x; //物理块存放的内容 int y; //第几次替换 int z; //需几次替换有相同的内容出现或替换后情况 }; 页面顺序由一数组定义，由于在最佳算法中需要记录每次置换后还有几次再次被调度，在...

收起
操作系统：Java模拟页面置换算法（最佳置换算法、先进先出算法、最近最久未使用算法）
千次阅读 2020-06-08 09:47:39

// 最少使用算法 } /** * 最佳置换算法：所选择的被淘汰页面是以后永不使用或最长时间不再被访问的页面 * 相关参数： * arr：存放页面号的待处理原数组 * blockArr: 物理块中存放页面号的数组 * blockNum: 记录...

收起

java

算法思想：

代码如下：

用C++实现LRU页面置换算法

操作系统—页面置换算法（C++实现）

操作系统 C++ 页面置换算法（含实验报告）有opt，LRU，先进先出，时钟算法，改进的时钟算法等所有算法

操作系统--页面置换算法（三种置换算法） C++高效实现 附代码

页面置换算法（OPT、FIFO、LRU）实现--C++版本-页面置换算法（Optimal、FIFO、LRU）

5种页面置换算法C++实现

OPT最佳页面置换算法

页面置换算法（OPT、FIFO、LRU）实现--C++版本

操作系统 页面替换算法（OPT最佳置换算法与LRU最近最久未使用算法）

请求分页储存管理的页置换算法模拟.exe

操作系统课设(页面置换算法C++版)

运行结果

完整代码

操作系统页面置换算法在C++中的实现

操作系统存储管理在C++中的实现

存储管理代码简介

代码实现

头文件及宏定义

指令流模块

页面流模块

选择模块

先进先出算法（FIFO）模块

最近最久未访问算法（LRU）模块

最佳淘汰算法（OPT）模块

最近最少访问算法（LFU）模块

源代码及运行过程图片

总结

【操作系统】 页面置换算法的c++实现

操作系统——页面置换算法c++的实现（fifo和lru）

【南邮操作系统实验】页面置换算法（FIFO、LRU、OPT） C++ 版

页面置换算法 c++

操作系统实验报告 用C++实现页面置换算法，LRU与FCFS

页面置换算法（最佳置换算法(OPT) 、先进先出置换算法(FIFO) 、最近最久未使用置换算法(LRU) 、时钟置换...

磁盘调度算法C++ 模拟FIFO，OPI和LRU页面置换算法的工作过程

页面置换算法的模拟实现及命中率对比

页面置换算法——C/C++实现 [ OTP, FIFO, LRU, LFU + 开源代码 + 详细解析]

操作系统页面置换算法之最佳(OPT)置换算法（C语言实现）

clock页面置换算法

操作系统 课程设计 页面置换算法FIFO和 LRU

页面置换算法；最佳置换算法、先进先出置换算法、最近最久未使用置换算法

[操作系统]页面置换算法实验及C++实现(OPT、FIFO、LRU)

页面置换算法（FIFO , LRU, OPT）（C++实现模拟）

模拟实现请求分页存储管理——最佳置换算法

操作系统：Java模拟页面置换算法（最佳置换算法、先进先出算法、最近最久未使用算法）

最佳置换算法c++

操作系统--页面置换算法（三种置换算法） C++高效实现附代码

操作系统页面替换算法（OPT最佳置换算法与LRU最近最久未使用算法）

【操作系统】页面置换算法的c++实现

操作系统实验报告用C++实现页面置换算法，LRU与FCFS

操作系统课程设计页面置换算法FIFO和 LRU