页面调度
本文主要介绍了OS页面调度的两种算法(FIFO LRU)，希望对您有所帮助
一. 实验目的
- 了解内存分页管理及调页策略
- 掌握FIFO LRU调度算法
- 实现FIFO LRU算法
- 区别两种不同的方法的优点和缺点
二. 实验内容
- FIFO 先进先出置换算法
- LRU 最近最少使用置换算法
三. 实验环境
- 实践平台 windows
- 编写环境 java
- 编译器 idea
四. 实验设计原理
FIFO 先进先出置换算法
如果新页面进入时，内存中有空余块，则直接加入，已存在的块不动；如果进入时以及满，则需要找出已经在内存中呆的时间最长的块进行page替换。
LRU 最近最少使用置换算法
最近最少使用与FIFO的实现思路基本一致，区别在于page进入时如果已经在某个块中则重新开始前面的计时。
五. 实验详细实现过程和算法流程
FIFO 先进先出置换算法
LRU 最近最少使用置换算法
六. 实验调试与结果分析
测试FIFO
测试LRU
对比增加块后的结果 FIFO算法
增加块儿数但是置换次数没有减少反而增加，即FIFO的问题Belady现象
七. 源代码
Page类
2
3
4
5
6
7
8
9
10public class Page {
public int index;
public int num;
public Page(int index){
this.index = index;
}
public void num_empty(){
num = 0;
}
}memory类
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23public class memory {
public List<Page> mem;
public int size;
public memory(int n){
mem = new ArrayList<Page>();
this.size = n;
}
public void init(){
for(int i=0;i<size;i++){
Page p = new Page(0);
mem.add(p);
}
}
public Page getn(int n){
return mem.get(n);
}
public void display(){
for (int i =0;i<mem.size();i++){
System.out.print(mem.get(i).index+" ");
}
System.out.println();
}
}主类
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37public class diaodu {
public static List<Page> pages = new ArrayList<Page>(0);//页面数据
public static List<Integer> page_xulie = new ArrayList<Integer>(0);//页面序列
public static int zhihuan_num=0;
public static memory[] mem_xulie = new memory[3];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入页面数");
int page_num;
page_num = scanner.nextInt();
//初始化页面计数
for(int i=0;i<page_num;i++){
Page p = new Page(i+1);
p.num = 0;
pages.add(p);
}
System.out.println("请输入页面序列号(以0结束)");
int test = scanner.nextInt();
while(test!=0){
page_xulie.add(test);
test = scanner.nextInt();
}
int syn;
System.out.println("请选择算法(1.FIFO 2.LRU)");
syn = scanner.nextInt();
//初始化mem
for(int i=0;i<3;i++){
mem_xulie[i] = new memory(page_xulie.size());
mem_xulie[i].init();
}
if(syn==1){
FIFO();
}else if(syn==2){
LRU();
}
}
}主类-FIFO
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67public static void FIFO(){
for (int i=0;i<page_xulie.size();i++){
int dangqian = page_xulie.get(i);
//遍历序列
Page[] lie = new Page[3];
if(i>0){
//取出上一列的数据
for(int j=0;j<3;j++){
lie[j] = mem_xulie[j].getn(i-1);
}
}else{
//如果刚开始没数据
for(int j=0;j<3;j++){
lie[j] = new Page(0);
}
}
boolean is_zai = false;
int zai_weizhi = 0;
int max_weizhi = 0;
int meiman_weizhi = 0;
boolean is_man = false;
Page max_page = lie[0];
for(int j=0;j<3;j++){
//先判断在不在
if(lie[j].index == dangqian){
//说明在
is_zai = true;
zai_weizhi = j;
break;
}
//找出num最大值
if(max_page.num < lie[j].num){
max_weizhi =j;
max_page = lie[j];
}
if(lie[j].index!=0){
is_man=true;
meiman_weizhi++;
}else {
is_man = false;
}
}
lie[0].num++;
lie[1].num++;
lie[2].num++;
if(!is_zai){
//如果满了 替换掉最大的 顺便把最大的num置0
Page p = new Page(dangqian);
p.num = 1;
zhihuan_num++;
if(is_man){
max_page.num = 0;
lie[max_weizhi] = p;
}
//没满则直接放
else{
lie[meiman_weizhi] = p;
}
}
//存入数据
for(int j=0;j<3;j++){
mem_xulie[j].mem.set(i, lie[j]);
}
}
output();
}主类-LRU
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69public static void LRU(){
for (int i=0;i<page_xulie.size();i++){
int dangqian = page_xulie.get(i);
//遍历序列
Page[] lie = new Page[3];
if(i>0){
//取出上一列的数据
for(int j=0;j<3;j++){
lie[j] = mem_xulie[j].getn(i-1);
}
}else{
//如果刚开始没数据
for(int j=0;j<3;j++){
lie[j] = new Page(0);
}
}
boolean is_zai = false;
int zai_weizhi = 0;
int max_weizhi = 0;
int meiman_weizhi = 0;
boolean is_man = false;
Page max_page = lie[0];
for(int j=0;j<3;j++){
//先判断在不在
if(lie[j].index == dangqian){
//说明在
is_zai = true;
zai_weizhi = j;
break;
}
//找出num最大值
if(max_page.num < lie[j].num){
max_weizhi =j;
max_page = lie[j];
}
if(lie[j].index!=0){
is_man=true;
meiman_weizhi++;
}else {
is_man = false;
}
}
lie[0].num++;
lie[1].num++;
lie[2].num++;
if(!is_zai){
//如果满了 替换掉最大的 顺便把最大的num置0
Page p = new Page(dangqian);
p.num = 1;
zhihuan_num++;
if(is_man){
max_page.num = 0;
lie[max_weizhi] = p;
}
//没满则直接放
else{
lie[meiman_weizhi] = p;
}
}else{
lie[zai_weizhi].num=1; //与FIFO唯一差距----
}
//存入数据
for(int j=0;j<3;j++){
mem_xulie[j].mem.set(i, lie[j]);
}
}
output();
}output函数
2
3
4
5
6
7
8
9
10
11private static void output() {
for (int i=0;i< page_xulie.size();i++){
System.out.print(page_xulie.get(i)+" ");
}
System.out.println();
for(int i=0;i<3;i++){
mem_xulie[i].display();
}
System.out.println("置换次数 "+zhihuan_num);
System.out.println("置换率 "+(double)zhihuan_num/ page_xulie.size());
}
八. 感悟
在这次实验中不仅实现了FIFO和LRU算法，对他们的原理也更加清晰，还分析了OPT算法的思路，虽然不易拿代码实现，但是可以作为分析调度算法的优劣的重要参考。
OPT 算法可保证获得最低的缺页率，但是由于目前还无法准确预知一个进程在内存的若干的页面中，哪一个页面是未来最长时间内不被访问的，我们无法做到开天眼，因而该算法在实际应用中无法实现。FIFO 算法有时候比较差，因为它所依据的条件是各个界面调入内存的时间,而页面调入的先后顺序不能反映页面的使用情况。LRU 算法虽然是一种比较好的置换算法，但是在实际中需要用到寄存器和栈的硬件支持。同时对比不同内存块数下的程序运行结果能够看出，算法的缺页率与分配的内存块数有关系，虽然会出现Belady现象，但基本规律是分配的内存块数越多，缺页率越低。
总之，这次的实验让我回顾了很多知识点，相比于前两次实验，这次的代码实现思路流程更复杂一些，锻炼了思维还有debug的能力。
页面调度
http://kaikai12321.github.io/2022/10/25/页面调度/