精华内容
下载资源
问答
  • opt页面置换算法流程图
    千次阅读
    2018-01-19 20:41:48

    1.先进先出置换算法(FIFO):是最简单的页面置换算法。这种算法的基本思想是:当需要淘汰一个页面时,总是选择驻留主存时间最长的页面进行淘汰,即先进入主存的页面先淘汰。其理由是:最早调入主存的页面不再被使用的可能性最大。
    2.最佳置换算法(OPT)(理想置换算法):从主存中移出永远不再需要的页面;如无这样的页面存在,则选择最长时间不需要访问的页面。于所选择的被淘汰页面将是以后永不使用的,或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。
    3.最近最久未使用(LRU)算法:这种算法的基本思想是:利用局部性原理,根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面,在最近的将来可能也不会再被访问。所以,这种算法的实质是:当需要淘汰一个页面时,总是选择在最近一段时间内最久不用的页面予以淘汰。

    具体代码实现:

    /**

    • 先进先出页面置换算法FIFO
    • 借助JDK内置数据结构队列
      */
    package com.page_replacementAlgorithm;
    import java.util.Queue;
    import java.util.concurrent.ArrayBlockingQueue;
    public class FIFO {
    
    	private final int capacity = 3;
    	private int index = 0;
    	// 构造一个初始容量为3的空列表
    	private Queue<Integer> queue = new ArrayBlockingQueue<Integer>(capacity);
    
    	public FIFO(int[] arr) {
    		for (int i = 0; i < arr.length; i++) {
    			if (queue.size() < capacity) { // 小于queue初始容量
    				if (!queue.contains(arr[i])) { // queue没有该页面,将其添加进queue尾部
    					queue.add(arr[i]);
    				} else {
    					continue;
    				}
    			} else {// 超出queue容量,置换掉最先调入内存的页面
    				if (!queue.contains(arr[i])) {
    					queue.poll();//获取并移除此队列的头,如果此队列为空,则返回 null。
    					queue.add(arr[i]);
    				} else {
    					continue;
    				}
    			}
    			traverse();
    		}
    		System.out.println("访问页面需从外存调入的次数为:"+(num-1));
    		System.out.println("缺页率为:"+(float)(num-1)/arr.length);
    	}
    
    	/**
    	 * 遍历queue容器
    	 */
    	int num = 1;
    	public void traverse() {
    		System.out.print("第" + (num++) + "次" + "页面置换:\t");
    		for (int i : queue) {
    			System.out.print(i + " ");
    		}
    		System.out.println();
    	}
    }
    
    

    -***************
    /**

    • 最佳置换算法OPT
    • 借助ArrayList数据结构
      */
    package com.page_replacementAlgorithm;
    
    import java.util.ArrayList;
    import java.util.List;
    
    
    public class OPT {
    
    	private final int capacity = 3;
    	private int[] index = new int[2];
    	private List<Integer> list = new ArrayList<Integer>(capacity);
    	public OPT(int[] arr) {
    		for (int i = 0; i < arr.length; i++) {
    			if (list.size() < capacity) { // 小于list初始容量
    				if (!list.contains(arr[i])) { // list没有该页面,将其添加进list尾部
    					list.add(arr[i]);
    				} else {
    					continue;
    				}
    			} else {// 超出list容量
    				index[0] = 100;
    				index[1] = 101;
    				if (!list.contains(arr[i])) { // 下一个页面如果不在list中
    					int a = 0;
    					for (int j = i; j < arr.length; j++) {
    						if (list.contains(arr[j])) { // arr[j]这个页面会在测试数据中会出现较早
    							if (index[0] != list.indexOf(arr[j])) {
    
    								index[a++] = list.indexOf(arr[j]);// 返回此列表中首次出现的指定元素的索引
    								if (a == 2) {
    									break;
    								}
    							}
    						}
    					}
    					list.set(noExist(), arr[i]);// 置换掉永不使用的,或许在最长时间内不再访问的页面
    				} else { // 下一个页面在list中
    					continue;
    				}
    			}
    			traverse();
    		}
    		System.out.println("访问页面需从外存调入的次数为:"+(num-1));
    		System.out.println("缺页率为:"+(float)(num-1)/arr.length);
    	}
    
    	/**
    	 * 遍历list容器
    	 */
    	int num = 1;
    
    	public void traverse() {
    		System.out.print("第" + (num++) + "次" + "页面置换:\t");
    		for (int i : list) {
    			System.out.print(i + " ");
    		}
    		System.out.println();
    	}
    
    	/**
    	 * 返回要替换的下标
    	 */
    	private int noExist() {
    		int[] brr = { 0, 1, 2 };
    		if (brr[0] != index[0] && brr[0] != index[1])
    			return brr[0];
    		if (brr[1] != index[0] && brr[1] != index[1])
    			return brr[1];
    		if (brr[2] != index[0] && brr[2] != index[1])
    			return brr[2];
    		return 2;
    	}
    }
    
    

    ********************************************** -**********************

    /**

    • 最近最久未使用和最少使用置换算法 LRU
    • 自己写的一个栈MyStack数据结构
      */
    package com.page_replacementAlgorithm;
    
    public class LRU {
    
    	// 初始化一个容量为 5 的栈
    	private MyStack<Integer> stack = new MyStack<Integer>(5);
    	private int index = 0;// 一个数组下标的标识,用来除去栈底元素
    
    	public LRU(int[] arr) {
    		for (int i = 0; i < arr.length; i++) {// 将数组里 数据存入栈中
    			if (stack.getLength() < stack.size()) { // 判断栈不满
    				if (!stack.exist(arr[i])) { // 判断栈中有没有该元素,有的话返回true
    					stack.push(arr[i]);
    					 stack.traverse();
    				} else { // 如果有该元素,删除掉栈中该元素,并将该元素置于栈顶
    					stack.removeSameElement(arr[i]);
    					stack.push(arr[i]);
    					stack.traverse2();
    				}
    			} else { // 栈已满,删除到栈底元素
    				if (stack.exist(arr[i])) { // 继续判断如果栈中存在相同元素,将该元素从栈中取出放到栈顶
    					stack.removeSameElement(arr[i]);
    					stack.push(arr[i]);
    					stack.traverse2();
    				} else { // 栈中没相同元素,删除栈底元素,在栈顶加新元素
    					stack.remove(arr[index++]);
    					stack.push(arr[i]);
    					stack.traverse(); // 遍历栈中元素
    				}
    			}
    		}
    		System.out.println("访问页面需从外存调入的次数为:"+(stack.getNum()-1));
    		System.out.println("缺页率为:"+(float)(stack.getNum()-1)/arr.length);
    	}
    }
    

    -******************************
    以下是栈
    *****-

    
    package com.page_replacementAlgorithm;
    
    import java.util.EmptyStackException;
    
    /**
     * @ClassName: MyStack
     */
    public class MyStack<E> {
    
    	private Object[] Capacity;
    	private int size = 0;
    	private int length = 0;
    	private int index = 0;
    	/**
    	 * 初始化一个空栈
    	 */
    	public MyStack() {
    	}
    	
    	/**
    	 * 初始化一个大小为 Capacity 的栈
    	 */
    	public MyStack(int initialCapacity) {
    		if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            Capacity = new Object[initialCapacity];
            size = initialCapacity;
    	}
    	
    	/**
    	 *  栈的大小
    	 */
    	public int size() {
    		return  size;
    	}
    	/**
    	 * 把项压入堆栈顶部
    	 */
    	public E push(E item) {
    		if(length < size()) {
    			Capacity[index++] = item;
    			length++;
    		}else {
    			try {
    				throw new Exception("栈满");
    			} catch (Exception e) {
    				e.printStackTrace();
    			}
    		}
    		return item;
    	}
    	
    	/**
    	 * 移除堆栈顶部的对象,并作为此函数的值返回该对象。
    	 */
    	public synchronized E pop() {
    		int len = getLength();
    		if (len == 0)
    			throw new EmptyStackException();
    		Capacity[--index] = null;
    		length--;
    		index--;
    		return (E) Capacity[index];
    	}
    	
    	/**
    	 * 移除堆栈中的对象,并作为此函数的值返回该对象。
    	 */
    	public synchronized boolean removeSameElement(E element) {
    		int len = getLength();
    		if (len == 0)
    			throw new EmptyStackException();
    		
    		int in = searchIndex(element);
    		if(in!=-1) {
    			int i=in;
    			for(; i<size()-1;i++) {
    				if(Capacity[i+1]!=null) {
    					Capacity[i] = Capacity[i+1];
    				}
    			}
    			Capacity[i] = null;
    			length--;
    			index--;
    			return true;
    		}
    		return false;
    	}
    	
    	/**
    	 * 栈满的话,移除栈底元素
    	 */
    	public synchronized boolean remove(E element) {
    		int len = getLength();
    		if (len == 0)
    			throw new EmptyStackException();
    		int i;
    		for (i = 0; i < size() - 1; i++) {
    			Capacity[i] = Capacity[i + 1];
    		}
    		Capacity[i] = null;
    		length--;
    		index--;
    		return true;
    	}
    	
    	/**
    	 * 查看堆栈顶部的对象,但不从堆栈中移除它。
    	 */
    	public synchronized E peek() {
    		int len = size();
    		if (len == 0)
    			throw new EmptyStackException();
    		return (E) Capacity[index-1];
    	}
    
    	/**
    	 * 测试堆栈是否为空。
    	 */
    	public boolean empty() {
    		return getLength() == 0;
    	}
    	
    	/**
    	 * 返回堆栈对象的个数
    	 */
    	public int getLength() {
    		return length;
    	}
    	
    	/**
    	 * 根据下标查找堆栈中的对象
    	 */
    	public E search(int i) {
    		if(i<size() || i>=0)
    			return (E) Capacity[i];
    		throw new ArrayIndexOutOfBoundsException();
    	}
    	
    	/**
    	 * 根据元素查找此在堆栈中的下标
    	 * 返回-1 表示查找失败
    	 */
    	public int searchIndex(E element) {
    		for(int i=0; i<getLength(); i++) {
    			if(Capacity[i].equals(element)) {
    				return i;
    			}
    		}
    		return -1;
    	}
    	
    	/**
    	 * 查看堆栈中是否存在 该对象
    	 */
    	public boolean exist(E element) {
    		for (Object object : Capacity) {
    			if(object != null) {
    				if(object.equals(element) || object==element)
    					return true;
    			}
    		}		
    		return false;
    	}
    	
    	/**
    	 * 从栈底到栈顶遍历堆栈中的对象
    	 */
    	int num = 1;
    	public void traverse() {
    		System.out.print("第"+(num++)+"次"+"页面置换:\t\t");
    		for (Object object : Capacity) {
    			System.out.print(object+"\t");
    		}
    		System.out.println(); 
    	}
    	public void traverse2() {
    		System.out.print("容器内未置换页面:\t");
    		for (Object i : Capacity) {
    			System.out.print(i + "\t");
    		}
    		System.out.println();
    	}
    	public int getNum() {
    		return num;
    	}
    }
    

    *********************************-

    
    /**
     * 测试页面置换算法
     */
    package com.page_replacementAlgorithm;
    
    import java.util.Scanner;
    
    
    public class Test {
    	
    	/**
    	 * OPT课本数据 20个页面
    	 * 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
    	 */
    	/**
    	 * FIFO课本数据    20个页面 
    	 * 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
    	 */
    
    	/**
    	 * LRU课本上的数据   11个数据 
    	 * 4 7 0 7 1 0 1 2 1 2 6
    	 */
    	private static boolean flag = true;
    	public static void main(String[] args) {
    		Scanner s = new Scanner(System.in);
    		while (flag) {
    			System.out.println("*************************");
    			System.out.println("   请输入  1或2或3 进行选择        ");
    			System.out.println("          1.OPT          ");
    			System.out.println("          2.FIFO         ");
    			System.out.println("          3.LRU          ");
    			System.out.println("*************************");
    
    			int result = s.nextInt();
    			// int[] arr = input();
    			if(result == 1) {
    				new OPT(input());
    				isContinue();
    			} else if (result == 2) {
    				new FIFO(input());
    				isContinue();
    			} else if (result == 3) {
    				new LRU(input());
    				isContinue();
    			} else {
    				System.out.println("您输入的信息有误,请重新输入!");
    				isContinue();
    			}
    		}
    	}
    
    	private static int[] input() {
    		System.out.println("请输入有多少个页面:");
    		Scanner s = new Scanner(System.in);
    		int num = s.nextInt();
    		System.out.println("在输入页面号,以空格隔开");
    		int[] arr = new int[num]; // 用来保存输入的页面数据
    		for (int i = 0; i < num; i++) {
    			arr[i] = s.nextInt();
    		}
    		return arr;
    	}
    	
    	private static void isContinue() {
    		Scanner s = new Scanner(System.in);
    		while(true) {
    			System.out.println("是否继续: y/n");
    			String result = s.nextLine();
    			if(result.equalsIgnoreCase("n")) {
    				flag = false;
    				System.out.println("***********************");
    				System.out.println("*        谢谢观赏            *");
    				System.out.println("***********************");
    				break;
    			} else if(result.equalsIgnoreCase("y")) {
    				break;
    			}else {
    				System.out.println("输入有误");
    			}
    		}
    	}
    }
    
    更多相关内容
  • 前提:设置三个内存块 1、FIFO页面置换算法 第一种: 第二种: 2、LRU页面置换算法 第一种: 第二种:

    前提:

    1.设置三个内存块;
    2. * 指的是缺页;
    3. / 指的是命中。

    1、先进先出页面置换算法(FIFO)

    总是淘汰在内存中停留时间最长的一页,,即先进入内存的一页,先被替换出。

    第一种:
    在这里插入图片描述
    第二种:
    在这里插入图片描述

    2、最近最久未使用页面置换算法(LRU)

    选择在最近一段时间里没有被使用过的页面,将其淘汰,也就是被其他页面替换。

    第一种:

    在这里插入图片描述
    第二种:

    在这里插入图片描述

    3、最佳置换算法(OPT)

    选择在将来不被使用,或者在最远的将来才被使用的老页面,也就是选择该页面后面较远才出现,甚至不出现的页面,将其淘汰,即被替换。

    第一种:
    在这里插入图片描述
    第二种:
    在这里插入图片描述

    一开始,我也搞不明白这两种表格有什么不同,还以为其中的一种是错的,后来才发现两种都是正确的,只不过略有不同。

    区别:
    第一种表格,例如数字2被替换出去,那么新进来的数字1 将被安排在刚刚被替换出去的数字2的原位置;
    第二种表格,例如数字2被替换出去,那么新进来的数字1依旧始终被安排在最上面第一个内存块,即内存块a,后面内存块中的数字依次向下移动,数字2的空位置在移动过程中被占据。

    展开全文
  • 该工程具体是在codeblock上面实现了操作系统课程上讲解的页面置换算法,包括先进先出(FIFO)、最佳置换算法(OPT)、最久最近未使用算法(LRU)。 具体实现功能有: 1、建立相应的数据结构 2、在屏幕上显示页面...
  • 包括了操作系统页面置换算法,其中有OPT,FIFO,LRU,CLOCK,改进型的CLOCK算法
  • 页面置换算法.doc

    2020-03-23 22:48:13
    深入掌握内存调度算法的概念原理和实现方法,编写程序实现: (1) 先进先出页面置换算法(FIFO) ...操作系统页面置换算法课程设计,完整的课设结构,有详细的流程图、Java源码,还有调试截图!!!
  • 最佳置换OPT页面置换算法的源代码,以及可执行程序。
  • OPT页面置换算法1

    千次阅读 2019-06-09 17:31:47
    OPT页面置换算法1 OPT简单/简陋/算法实现 对于页面置换计数有待改进 当要调入一页而必须淘汰旧页时,应该淘汰以后不再访问的页,或距现在最长时间后要访问的页面。它所产生的缺页数最少,然而,却需要预测程序的页面...

    OPT页面置换算法1

    OPT简单/简陋/算法实现
    对于页面置换计数有待改进
    当要调入一页而必须淘汰旧页时,应该淘汰以后不再访问的页,或距现在最长时间后要访问的页面。它所产生的缺页数最少,然而,却需要预测程序的页面引用串,这是无法预知的,不可能对程序的运行过程做出精确的断言,不过此理论算法可用作衡量各种具体算法的标准。
    在这里插入图片描述

    #include <iostream>
    #define N 3
    using namespace std;
    int main()
    {
        int ym[]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
        int size=20;
        int opt[N]={7,0,1};
        int len[N]={0,0,0};
        int sum;
        int dq=3;
        int flag=0;
        int allchagetime=0;
        do{
            for(int i=0;i<N;i++)
            {
                cout<<opt[i]<<"  ";
            }
            cout<<endl;
    
    //判断下一次是否发生页面置换,以及置换谁,通过遍历页框和页面寻找下一个出现的时长度,置换距离最长的
    //每次发现一个则接续寻找使用break;
          for(int i=0;i<N;i++)
            {
               sum=0;
                if(ym[dq]==opt[0]||ym[dq]==opt[1]||ym[dq]==opt[2])
                 {
                     flag=1;
                     break;
                 }
    
                 else{
                        flag=0;
                     for(int j=dq;j<=20;j++)
             {
    
    
                   sum++;
                 if(opt[i]==ym[j]||j==20)
                 {
                     len[i]=sum;
    
                     break;
                 }
                 }
    
             }
    
                 }
    
    
    
         if(flag==0)
         {
    
    
             int max=len[0];
        int res;
        for(int t=0;t<N;t++)
        {
             if(len[t]>=max)
             {
                res=t;
                 max=len[t];
             }
        }
        opt[res]=ym[dq];
           allchagetime++;
         }
    
            dq++;
        }while(dq!=21);
        cout<<"缺页"<<allchagetime+3-1<<"次,"<<"置换"<<allchagetime-1<<"次"<<endl;
    }
    
    

    在这里插入图片描述

    欢迎使用Markdown编辑器

    你好! 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章,了解一下Markdown的基本语法知识。

    新的改变

    我们对Markdown编辑器进行了一些功能拓展与语法支持,除了标准的Markdown编辑器功能,我们增加了如下几点新功能,帮助你用它写博客:

    1. 全新的界面设计 ,将会带来全新的写作体验;
    2. 在创作中心设置你喜爱的代码高亮样式,Markdown 将代码片显示选择的高亮样式 进行展示;
    3. 增加了 图片拖拽 功能,你可以将本地的图片直接拖拽到编辑区域直接展示;
    4. 全新的 KaTeX数学公式 语法;
    5. 增加了支持甘特图的mermaid语法1 功能;
    6. 增加了 多屏幕编辑 Markdown文章功能;
    7. 增加了 焦点写作模式、预览模式、简洁写作模式、左右区域同步滚轮设置 等功能,功能按钮位于编辑区域与预览区域中间;
    8. 增加了 检查列表 功能。

    功能快捷键

    撤销:Ctrl/Command + Z
    重做:Ctrl/Command + Y
    加粗:Ctrl/Command + B
    斜体:Ctrl/Command + I
    标题:Ctrl/Command + Shift + H
    无序列表:Ctrl/Command + Shift + U
    有序列表:Ctrl/Command + Shift + O
    检查列表:Ctrl/Command + Shift + C
    插入代码:Ctrl/Command + Shift + K
    插入链接:Ctrl/Command + Shift + L
    插入图片:Ctrl/Command + Shift + G

    合理的创建标题,有助于目录的生成

    直接输入1次#,并按下space后,将生成1级标题。
    输入2次#,并按下space后,将生成2级标题。
    以此类推,我们支持6级标题。有助于使用TOC语法后生成一个完美的目录。

    如何改变文本的样式

    强调文本 强调文本

    加粗文本 加粗文本

    标记文本

    删除文本

    引用文本

    H2O is是液体。

    210 运算结果是 1024.

    插入链接与图片

    链接: link.

    图片: Alt

    带尺寸的图片: Alt

    居中的图片: Alt

    居中并且带尺寸的图片: Alt

    当然,我们为了让用户更加便捷,我们增加了图片拖拽功能。

    如何插入一段漂亮的代码片

    博客设置页面,选择一款你喜欢的代码片高亮样式,下面展示同样高亮的 代码片.

    // An highlighted block
    var foo = 'bar';
    

    生成一个适合你的列表

    • 项目
      • 项目
        • 项目
    1. 项目1
    2. 项目2
    3. 项目3
    • 计划任务
    • 完成任务

    创建一个表格

    一个简单的表格是这么创建的:

    项目Value
    电脑$1600
    手机$12
    导管$1

    设定内容居中、居左、居右

    使用:---------:居中
    使用:----------居左
    使用----------:居右

    第一列第二列第三列
    第一列文本居中第二列文本居右第三列文本居左

    SmartyPants

    SmartyPants将ASCII标点字符转换为“智能”印刷标点HTML实体。例如:

    TYPEASCIIHTML
    Single backticks'Isn't this fun?'‘Isn’t this fun?’
    Quotes"Isn't this fun?"“Isn’t this fun?”
    Dashes-- is en-dash, --- is em-dash– is en-dash, — is em-dash

    创建一个自定义列表

    Markdown
    Text-to- HTML conversion tool
    Authors
    John
    Luke

    如何创建一个注脚

    一个具有注脚的文本。2

    注释也是必不可少的

    Markdown将文本转换为 HTML

    KaTeX数学公式

    您可以使用渲染LaTeX数学表达式 KaTeX:

    Gamma公式展示 Γ ( n ) = ( n − 1 ) ! ∀ n ∈ N \Gamma(n) = (n-1)!\quad\forall n\in\mathbb N Γ(n)=(n1)!nN 是通过欧拉积分

    Γ ( z ) = ∫ 0 ∞ t z − 1 e − t d t &ThinSpace; . \Gamma(z) = \int_0^\infty t^{z-1}e^{-t}dt\,. Γ(z)=0tz1etdt.

    你可以找到更多关于的信息 LaTeX 数学表达式here.

    新的甘特图功能,丰富你的文章

    Mon 06 Mon 13 Mon 20 已完成 进行中 计划一 计划二 现有任务 Adding GANTT diagram functionality to mermaid
    • 关于 甘特图 语法,参考 这儿,

    UML 图表

    可以使用UML图表进行渲染。 Mermaid. 例如下面产生的一个序列图::

    张三 李四 王五 你好!李四, 最近怎么样? 你最近怎么样,王五? 我很好,谢谢! 我很好,谢谢! 李四想了很长时间, 文字太长了 不适合放在一行. 打量着王五... 很好... 王五, 你怎么样? 张三 李四 王五

    这将产生一个流程图。:

    链接
    长方形
    圆角长方形
    菱形
    • 关于 Mermaid 语法,参考 这儿,

    FLowchart流程图

    我们依旧会支持flowchart的流程图:

    Created with Raphaël 2.2.0 开始 我的操作 确认? 结束 yes no
    • 关于 Flowchart流程图 语法,参考 这儿.

    导出与导入

    导出

    如果你想尝试使用此编辑器, 你可以在此篇文章任意编辑。当你完成了一篇文章的写作, 在上方工具栏找到 文章导出 ,生成一个.md文件或者.html文件进行本地保存。

    导入

    如果你想加载一篇你写过的.md文件或者.html文件,在上方工具栏可以选择导入功能进行对应扩展名的文件导入,
    继续你的创作。


    1. mermaid语法说明 ↩︎

    2. 注脚的解释 ↩︎

    展开全文
  • 页面置换算法( 详解 )

    2022-07-22 08:07:16
    进程运行时,若其访问的页面不在内存而需将其调入,但内存已无空闲空间时,就需要从内存中调出一页程序或数据,送入磁盘的对换区,其中选择调出页面的算法就称为页面置换算法。好的页面置换算法应有较低的页面更换...


    一、什么是页面置换算法?

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

    好的页面置换算法应有较低的页面更换频率,也就是说,应将以后不会再访问或者以后较长时间内不会再访问的页面先调出

    在地址映射过程中,若在页面中发现所要访问的页面不在内存中,则产生缺页中断。当发生缺页中断时,如果操作系统内存中没有空闲页面,则操作系统必须在内存选择一个页面将其移出内存,以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法

    二、常用的页面置换算法

    1. FIFO(先进先出算法)

    (优先淘汰最早进入内存的页面)

    FIFO算法是最简单的页面置换算法。FIFO页面置换算法为每个页面记录了调到内存的时间,当必须置换页面时会选择最旧的页面

    "FIFO算法当进程分配到的页面数增加时,缺页中断的次数可能增加也可能减少”
    在这里插入图片描述
    FIFO算法基于队列实现,不是堆栈类算法

    注意,并不需要记录调入页面的确切时间,可以创建一个FIFO队列,来管理所有的内存页面。置换的是队列的首个页面。当需要调入页面到内存时,就将它加到队列的尾部

    FIFO页面置换算法易于理解和编程。然而,它的性能并不总是十分理想:
    (1)所置换的页面可以是很久以前使用过但现已不再使用的初始化模块
    (2)所置换的页面可以包含一个被大量使用的变量,它早就初始化了,但仍在不断使用

    2. OPT(最佳置换算法)

    (淘汰以后不会使用的页面)

    发现Belady 异常的一个结果是寻找最优页面置换算法,这个算法具有所有算法的最低的缺页错误率,并且不会遭受Belady 异常。这种算法确实存在,它被称为OPT 或 MIN
    在这里插入图片描述
    这种页面置换算法确保对于给定数量的帧会产生最低的可能的缺页错误率

    FIFO和OPT算法的区别在于:除了在时间上向后或向前看之外,FIFO算法使用的是页面调入内存的时间,OPT算法使用的是页面将来使用的时间

    3. LRU(最近最少使用算法)

    (淘汰最近没有使用的页面)

    选择最近最长时间未访问过的页面予以淘汰,它认为过去一段时间内未访问过的页面,在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段,来记录页面自上次被访问以来所经历的时间,淘汰页面时选择现有页面中值最大的予以淘汰
    在这里插入图片描述

    OPT和LRU算法的区别在于:LRU算法根据各页以前的情况,是"向前看"的,而最佳置换算法则根据各页以后的使用情况,是"向后看"的

    LRU 性能较好,但需要寄存器和栈的硬件支持
    LRU是堆栈类的算法,理论上可以证明,堆栈类算法不可能出现 Belady异常

    4. Clock(时钟置换算法)

    简单的CLOCK算法是给每一帧关联一个附加位,称为使用位。

    当某一页首次装入主存时,该帧的使用位设置为1;
    当该页随后再被访问到时,它的使用位也被置为1。

    对于页替换算法,用于替换的候选帧集合看做一个循环缓冲区,并且有一个指针与之相关联。
    当某一页被替换时,该指针被设置成指向缓冲区中的下—帧。
    当需要替换一页时,操作系统扫描缓冲区,以查找使用位被置为0的一帧。
    每当遇到一个使用位为1的帧时,操作系统就将该位重新置为0;

    如果在这个过程开始时,缓冲区中所有帧的使用位均为0,则选择遇到的第一个帧替换;
    如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周,把所有使用位都置为0,并且停留在最初的位置上,替换该帧中的页。

    由于该算法循环地检查各页面的情况,故称为CLOCK算法,又称为最近未用( NotRecently Used,NRU )算法。
    在这里插入图片描述

    5. LFU(最不常用算法)

    最不经常使用(LFU)页面置换算法要求置换具有最小计数的页面。

    这种选择的原因是,积极使用的页面应当具有大的引用计数。然而,当一个页面在进程的初始阶段大量使用但是随后不再使用时,会出现问题。由于被大量使用,它有一个大的计数,即使不再需要却仍保留在内存中。一种解决方案是,定期地将计数右移1位,以形成指数衰减的平均使用计数。

    6. MFU(最常使用算法)

    最经常使用(MFU)页面置换算法是基于如下论点:具有最小计数的页面可能刚刚被引入并且尚未使用。
    MFU和LFU置换都不常用。这些算法的实现是昂贵的,并且它们不能很好地近似OPT置换。

    三、程序设计

    #include<stdio.h>
    #include<stdlib.h>
    #define PN 12//页面访问列长度
    #define FN 3//分配给进程的内存块数
    
    int *pageSeq;//页面访问序列
    int *frames;//内存块数组
    int fault,exchange;//缺页次数和置换次数
    float ratio;//缺页率
    
    void init();//初始化页面访问向量
    void clear();//初始化内存块
    void print();//输出最后结果
    void print1(int);//输出每一步结果
    void OPT(int*,int,int*,int);//OPT算法
    void FIFO(int*,int,int*,int);//FIFO算法
    void LRU(int*,int,int*,int);//LRU算法
    int search(int,int*,int,int);//搜索页面在序列某段中的位置,找到返回下标,否则返回-1
    
    int main()
    {
    int num;
    printf("【页面置换算法】\n");
    printf("序列长度:%d\n",PN);
    printf("内存块数:%d\n",FN);
    printf("======================\n\n");
        init();//初始化页面访问向量
        printf("操作说明:\n");
        printf("    num=0  程序结束\n");
        printf("    num=1  OPT算法\n");
        printf("    num=2  FIFO算法\n");
        printf("    num=3  LRU算法\n");
        printf("==============================\n");
        printf("\n");
        printf("输入操作序号num:");
        scanf("%d",&num);
        while(1)
        {
            switch(num)
            {
                case 0:printf("\n=====程序结束!=====\n");return 0;
                case 1:printf("\n【OPT算法】\n");OPT(pageSeq,PN,frames,FN);break;
                case 2:printf("\n【FIFO算法】\n");FIFO(pageSeq,PN,frames,FN);break;
                case 3:printf("\n【LRU算法】\n");LRU(pageSeq,PN,frames,FN);break;
                default:printf("\n=====重新输入=====\n");goto L1;
            }
            print();
    L1:     printf("\n");
            printf("输入操作序号num:");
            scanf("%d",&num);
        }
    }
    
    void init()//输入访问序列
    {
        int i;
        pageSeq=(int*)(malloc(PN*sizeof(int)));
        frames=(int*)(malloc(FN*sizeof(int)));
        printf("向pageSeq输入页面访问序列:");
        for(i=0;i<PN;i++)
            scanf("%d",&pageSeq[i]);
        printf("\n");
        printf("页面访问序列:\n\n");//输出页面访问序列
        for(i=0;i<PN;i++)
            printf("%3d",pageSeq[i]);
        printf("\n\n");
        printf("===============================================================\n");
    }
    
    void clear()//重新初始化内存块frames,因为有0号页面,所以置-1
    {
        int i;
        fault=0;//缺页次数
        exchange=0;//置换次数
        for(i=0;i<FN;i++)//内存块置-1
            frames[i]=-1;
    }
    
    void print1(int flag)//flag为缺页标志,输出每一步结果
    {
        int t;
        for(t=0;t<FN;t++)//每访问一个页面,都输出一次内存块(页面)
            printf("%3d",frames[t]);
        if(flag) printf("  fault");//在缺页位置标记“fault”
        printf("\n");
    }
    
    void print()//输出最后结果
    {
        exchange=fault-FN;
        ratio=(float)fault/PN*100;
        printf("------------------------------\n");
        printf("缺页次数:%d\n",fault);
        printf("置换次数:%d\n",exchange);
        printf("缺 页 率:%4.1f%%\n",ratio);
        printf("==============================\n");
    }
    
    int search(int p,int* ar,int start,int end)//参数说明:(页号,页面访问序列或者内存块数组,起点,终点)
    {//检测页面p是否存在数组ar中(起点start,终点end),存在则返回其在ar中的位置(下标),否则返回-1
        int i,f;
        if(start>end)f=-1;//f作为方向标志,f=1时,循环变量递增;f=-1时,循环变量递减
        else f=1;
        i=start;//从strat位置开始搜索
        while(i!=end+f)//i超过end时结束循环
        {//在OPT算法中,start<end,循环变量递增,f=1;而在LRU算法中则相反,f=-1
            if(p==ar[i])return i;//首次搜索到p即返回下标
            i=i+f;
        }
        return -1;//未搜索到页面p,即p在未来不再被访问
    }
    
    void OPT(int* arp,int p,int* arf,int f)
    {//参数说明:(页面访问序列数组,数组长度,内存块数组,数组长度)
        int i=0,j,flag;
        int kf=0;//kf为进入内存页面数,当kf>=f时,内存块满,此时缺页产生置换,且kf的值不再增加
        int kp;//搜索起点,即页面访问序列中当前页的下一位置
        int posi,pmaxi,pmaxj;//未来最久不使用页面在arp和arf中的位置
        clear();//内存块数据清零
        printf("页面访问过程:\n");
        printf("------------------------------\n");
        for(i=0;i<p;i++)//扫描页面序列
        {
            flag=0;//缺页标志,初值置0,不缺页
            if(search(arp[i],arf,0,f-1)==-1)//页不在内存
            {
                flag=1;//缺页,flag置1
                fault++;//缺页+1
                if(kf<f)//有空闲内存块,无置换
                {
                    arf[kf]=arp[i];//页面直接调入内存块arf[kf]中
                    kf++;//当内存块放满页面后,kf不再增加
                }
                else//没有空闲内存块,将产生置换
                {
                   kp=i+1; //设置页面访问序列arp中向后搜索的起点,选择淘汰页面
                   pmaxi=-1;//被淘汰页面在访问序列arp中的位置,初值置-1
                   for(j=0;j<f;j++)
                   {//对内存arf中的每个页面依次查找其在访问序列arp中(未来)第一次出现的位置,并存放在posi中
                       posi=search(arf[j],arp,kp,p-1);
                       if(posi==-1)//search()返回-1,说明该页面在未来不存在,即不会再被访问到
                       {
                           arf[j]=arp[i];//置换并终止循环
                           break;
                       }
                       if(posi>pmaxi)
                       {//search()返回值不是-1,则记录最久未使用页面在访问序列arp中的位置
                           pmaxi=posi;//记录最大位置
                           pmaxj=j;//记录最久未使用页面在内存arf中的位置
                       }
                   }
                   if(j>=f)arf[pmaxj]=arp[i];//当内存块数组arf中所有页面在未来都会被访问到时,置换
                }
            }
            print1(flag);//输出一次内存页面情况
        }
    }
    
    void FIFO(int* arp,int p,int* arf,int f)
    {//参数说明:(页面访问序列数组,数组长度,内存块数组,数组长度)
        int i,j=0,flag;
        clear();//内存块数据清零
        printf("页面访问过程:\n");
        printf("------------------------------\n");
        for(i=0;i<p;i++)
        {
            flag=0;//缺页标志,同OPT
            if(search(arp[i],arf,0,f-1)==-1)//如果当前页面arp[i]不在内存
            {
                fault++;//缺页+1
                flag=1;
                arf[j]=arp[i];//页面调入内存
                j=(j+1)%f;//j+1,循环
            }
            print1(flag);//输出一次内存页面情况
        }
    }
    
    void LRU(int* arp,int p,int* arf,int f)
    {//参数说明:(页面访问序列数组,数组长度,内存块数组,数组长度)
        int i,j;
        int kf=0;//kf>=f时,内存块满,此时缺页产生置换
        int flag;//缺页标志
        int pmini,pminj;//最久未访问页面在arp[]中过去的位置和在arf[]中的位置
        int posi;
        clear();//清理内存块数据等
        for(i=0;i<p;i++)
        {
            flag=0;
            if(search(arp[i],arf,0,f-1)==-1)//页面不在内存
            {
                flag=1;
                fault++;//缺页
                if(kf<f)//有空闲块,无置换
                {
                    arf[kf]=arp[i];
                    kf++;
                }
                else//无空闲块,产生置换
                {//在arp[]中向前搜索,寻找最久未被访问的页面位置
                    pmini=p;//pmini值初值(最大值或者当前值i)
                    for(j=0;j<f;j++)
                    {
                        posi=search(arf[j],arp,i-1,0);//这里与OPT不同,不会出现页面不存在的情况
                        if(posi<pmini)
                        {
                            pmini=posi;
                            pminj=j;
                        }
                    }
                    arf[pminj]=arp[i];//置换
                }
            }
            print1(flag);//输出一次内存页面情况
        }
    }
    
    展开全文
  • 页面置换算法(FIFO&LRU)

    万次阅读 多人点赞 2020-12-27 11:23:43
    页面置换算法 实验目的 1.通过模拟实现几种基本页面置换的算法,了解虚拟存储技术的特点。 2.通过置换算法的模拟和比较,进一步了解它们的优缺点。 3.锻炼知识的运用能力和实践能力 实验要求 编写程序实现:先进先出...
  • 【JAVA操作系统——页面置换算法】LRU&OPT
  • 文章目录1、最佳淘汰算法(Optimal)举例代码流程图2、先进先出的算法(FIFO)举例代码流程图3、最近最久未使用算法(LRU)举例代码流程图4、简单时钟(钟表)算法(CLOCK)举例代码流程图 1、最佳淘汰算法OPT)  ...
  • 【操作系统】页面置换算法(最佳置换算法)(C语言实现) #####(编码水平较菜,写博客也只是为了个人知识的总结和督促自己学习,如果有错误,希望可以指出) 1.页面置换算法: 在地址映射过程中,若在页面中发现所...
  • (1)加深对页面置换算法的理解。 (2)掌握几种页面置换算法的实现方法。 (3)通过实验比较各种置换算法的优劣。
  • 一、缺页异常(缺页中断) 当 CPU 访问的⻚⾯不在物理内存时,便会产⽣⼀个...缺⻚中断的处理流程,如下: 在 CPU ⾥访问⼀条 Load M 指令,然后 CPU 会去找 M 所对应的⻚表项。 如果该⻚表项的状态位是「有效的」.
  • 页面置换算法的模拟,包含最佳置换算法、先进先出页面置换算法、最近最久未使用算法、最少使用置换算法、Clock置换算法的模拟
  • 计算并输出下述各种算法在不同内存容量下的命中率。 A. FIFO先进先出的算法 B. LRR最近最少使用算法 C. OPT最佳淘汰算法(先淘汰最不常用的页地址)
  • 一分钟学会页面置换算法OPT、FIFO、LRU、NUR】

    千次阅读 多人点赞 2020-03-26 19:26:04
    采用最佳置换算法可保证获得最低的缺页率。但是由于无法预知哪一个页面是未来最长时间内不再被访问的,因而该算法是无法实现的; 先进先出(FIFO)算法:淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面...
  • 页面置换算法实验报告_16281100_雷兵

    万次阅读 多人点赞 2019-05-28 14:35:35
    页面置换算法实验报告 1实验题目 设计和实现最佳置换算法、先进先出置换算法、最近最久未使用置换算法、页面缓冲置换算法;通过页面访问序列随机发生器实现对上述算法的测试及性能比较。 2实验要求 假设前提 ...
  • 包含五种基本算法,有算法的文字介绍,算法流程图,C语言代码。 本实验的程序设计基本上按照实验内容进行,用C语言编写程序。首先用srand( )和rand( )函数定义和产生指令序列,然后将指令序列变换成相应的页地址流,...
  • 计算机操作系统实验之页面置换算法(C语言)

    万次阅读 多人点赞 2019-12-08 17:25:19
    在进程运行过程中,如果它需要访问的页面不在内存,需要把它调入内存,但是内存已满时,需要把内存中的某页数据送到磁盘的对换区中。而选择哪个页面,则由固定的算法来决定,称为页面置换算法
  • 操作系统页面置换算法实验报告.doc

    千次阅读 2021-05-21 02:18:17
    操作系统页面置换算法实验报告,页面置换算法实验报告,18,操作系统页面置换算法,页面置换算法,lru页面置换算法,最佳页面置换算法,fifo页面置换算法,页面置换算法代码,opt页面置换算法学 生 实 验 报 告姓名: 年级...
  • 作者 |小林coding来源 |小林coding(CodingLin)最近,我偷偷潜伏在各大技术群,因为...所以,我这边总结了操作系统的三大调度机制,分别是「进程调度/页面置换/磁盘调度算法」,供大家复习,希望大家在秋招能斩获自...
  • 内存页面置换算法

    千次阅读 2021-12-13 21:39:09
    最佳页面置换算法OPT) 先进先出置换算法(FIFO) 最近最久未使用的置换算法(LRU) 时钟页面置换算法(Lock) 最不常用置换算法(LFU) 最佳页面置换算法OPT) 最佳页面置换算法基本思路是,置换在「未来」...
  • 在驻留集大小不变的页面置换算法当中,常用的算法主要有:FIFO、OPT 、LRU。本文讨论的对象是FIFO、LRU算法。在进程运行过程中,若所要访问的页面不在内存中,需要调入页面时,选择内存中的那个物理页面将其调出。...
  • 多久没有用过了 3核心算法流程图 4实验测试数据 特定实验测试数据(调试用) 页面数量:6 内存块物理块数:3 访问序列的长度:10 初始化数据 四、运行结果 理论分析 置换只发生于内存块满了,而且内存块中没有与页面...
  • !! FIFO算法:先进先出调度算法,该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面...CLOCK算法:根据页面内存是否被访问来决定是否置换页面。 改进版CLOCK算法:在之前的CLOCK算法上面除了使用
  • 页面置换算法-CLOCK置换算法及其改进版算法

    万次阅读 多人点赞 2018-12-29 13:31:51
    页面置换算法中的LRU算法最接近理想情况下的OPT算法,但是实现起来比较困难且开销较大,所以很多设计者试图用开销比较小的算法接近LRU算法,CLOCK算法就是其中一种。 1.简单的CLOCK算法是通过给每一个访问的页面...
  • 计算机操作系统之页面置换算法课程设计(python实现,可运行有界面程序exe)一、课程设计的目的和意义二、方案设计及开发过程1.... **算法流程图**(1) OPT页面置换算法流程图![OPT置换算法](https://i...
  • 实用标准文案精彩文档操作系统实验报告页面置换算法模拟——OFT、FIFO和LRU算法班级:2013级软件工程1班学号:X X X姓名:萧氏一郎数据结构说明:Memery[10]物理块中的页码Page[100]页面号引用串Temp[100][10]辅助...
  • 1、了解虚拟存储技术的特点,掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程,并比较它们的效率。 2、了解程序设计技术和内存泄露的原因 二、实验内容 1、模拟实现请求页式存储管理的几种...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 740
精华内容 296
热门标签
关键字:

opt页面置换算法流程图