• JAVA实现页面置换算法——LRU算法
2021-04-23 22:02:49

理解算法才能实现算法，要不然就和我一样无从下手，抓破头皮也没用！！！

LRU算法：http://flychao88.iteye.com/blog/1977653import java.util.*;

import java.io.*;

public class Main{

public static void main(String args []){

LRUmethod fm=new LRUmethod();

}

}

class LRUmethod{

int times;

int fail;

int cap;

ArrayList al=new ArrayList();

public LRUmethod(){

Scanner in=new Scanner(System.in);

fail=0;

System.out.println("请输入用户指令：");

String s=in.nextLine();

String sarr[]=s.split(" ");

times=sarr.length;

for(int i=0;i

}

System.out.println("请输入容量：");

cap=in.nextInt();

run();

}

public void run(){

for(int i=0;i

int t=al.get(i);

if(!ll.contains(t)){

fail++;

if(ll.size()

else{

ll.removeFirst();

}

}

else{

ll.remove((Integer)t);

}

System.out.print("第"+(i+1)+"次 ：");

Iterator it=ll.iterator();

while(it.hasNext()){

Integer itg=it.next();

System.out.print(itg+" ");

}

System.out.println();

}

System.out.println("命中率："+(1-(float)fail/times));

}

}

可能有很多问题，欢迎大佬指正。

更多相关内容
• 主要为大家详细介绍了java实现页面置换算法，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下
• import java.util.HashMap; import java.util.Map.Entry; import java.util.Set; public class LRUCache<K, V> { private int currentCacheSize; private int CacheCapcity; private HashMap&l...
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Set;

public class LRUCache<K, V> {

private int currentCacheSize;
private int CacheCapcity;
private HashMap<K,CacheNode> caches;
private CacheNode first;
private CacheNode last;

public LRUCache(int size){
currentCacheSize = 0;
this.CacheCapcity = size;
caches = new HashMap<K,CacheNode>(size);
}

public void put(K k,V v){
CacheNode node = caches.get(k);
if(node == null){
if(caches.size() >= CacheCapcity){

caches.remove(last.key);
removeLast();
}
node = new CacheNode();
node.key = k;
}
node.value = v;
moveToFirst(node);
caches.put(k, node);
}

public Object  get(K k){
CacheNode node = caches.get(k);
if(node == null){
return null;
}
moveToFirst(node);
return node.value;
}

public Object remove(K k){
CacheNode node = caches.get(k);
if(node != null){
if(node.pre != null){
node.pre.next=node.next;
}
if(node.next != null){
node.next.pre=node.pre;
}
if(node == first){
first = node.next;
}
if(node == last){
last = node.pre;
}
}

return caches.remove(k);
}

public void clear(){
first = null;
last = null;
caches.clear();
}

private void moveToFirst(CacheNode node){
if(first == node){
return;
}
if(node.next != null){
node.next.pre = node.pre;
}
if(node.pre != null){
node.pre.next = node.next;
}
if(node == last){
last= last.pre;
}
if(first == null || last == null){
first = last = node;
return;
}

node.next=first;
first.pre = node;
first = node;
first.pre=null;

}

private void removeLast(){
if(last != null){
last = last.pre;
if(last == null){
first = null;
}else{
last.next = null;
}
}
}
@Override
public String toString(){
StringBuilder sb = new StringBuilder();
CacheNode node = first;
while(node != null){
sb.append(String.format("%s:%s ", node.key,node.value));
node = node.next;
}

return sb.toString();
}

class CacheNode{
CacheNode pre;
CacheNode next;
Object key;
Object value;
public CacheNode(){

}
}


展开全文
• 操作系统os 页面置换算法java实现） Clock.java Lru.java Opt.java Fifo.java
• java实现页面置换算法，包括FIFO、LRU、Clock三种算法
• 原理就不说了，直接上代码
• FIFO
import java.util.ArrayList;
import java.util.List;

import utils.ListUtils;

/**
*
*
* @author cnkeysky
*
*/

public class FIFO {

public void run() {
String[] inputStr = {"1", "2", "3", "4", "2", "1", "2", "3", "5", "2", "3", "7", "6"};
// 内存块
int memory = 3;
List<String> list = new ArrayList<>();
for(int i = 0; i < inputStr.length; i++){
if(i == 0){
System.out.println("第"+ i +"次访问：\t\t" + ListUtils.listToString(list));
}else {
if(ListUtils.find(list, inputStr[i])){
System.out.println("第" + i + "次" + "访问：\t\t" + ListUtils.listToString(list));
}else{
if(list.size() < memory){
}else{
list.remove(0);

}
System.out.println("第" + i + "次" + "访问：\t\t" + ListUtils.listToString(list));
}
}
}
}

}

• LRU
import utils.ListUtils;

import java.util.ArrayList;
import java.util.List;

/**
* 最近最久未用置换算法
* @author cnkeysky
*
*/

public class LRU {

public static void main(String[] args) {
String[] inputStr = {"6", "7", "6", "5", "9", "6", "8", "9", "7", "6", "9", "6"};
// 内存块
int memory = 3;
List<String> list = new ArrayList<>();
for(int i = 0; i < inputStr.length; i++){
if(i == 0){
System.out.println("第"+ i +"次访问：\t\t" + ListUtils.listToString(list));
}else {
if(ListUtils.find(list, inputStr[i])){
// 存在字符串，则获取该下标
int index = ListUtils.findIndex(list, inputStr[i]);
// 下标不位于栈顶时，且list大小不为1时
if(!(list.get(list.size() - 1)).equals(inputStr[i]) && list.size() != 1) {
String str = list.get(index);
list.remove(index);
}
System.out.println("第" + i + "次" + "访问：\t\t" + ListUtils.listToString(list));
}else{
if(list.size()>= memory) {
list.remove(0);
System.out.println("第" + i + "次" + "访问：\t\t" + ListUtils.listToString(list));
}else {
System.out.println("第" + i + "次" + "访问：\t\t" + ListUtils.listToString(list));
}
}
}
}
}
}

• Clock
import java.util.ArrayList;
import java.util.List;

import utils.ListUtils;

/**
*
*
* @author cnkeysky
*
*/
public class Clock {

public static void main(String[] args) {
String[] inputStr = {"6", "7", "6", "5", "9", "6", "8", "9", "7", "6", "9", "6"};
List<String> list = new ArrayList<>();
// 内存块
int memory = 3;
// 缺页次数
int count = 0;
String[] clock = new String[memory];
int indexNext = 0;
int index = 0;
// 初始化时钟
for(int i = 0; i < memory; i++) {
clock[i] = "0";
}
for(int i = 0; i < inputStr.length; i++) {
int indexPre = 0;
if (i == 0) {
clock[indexNext] = "1";
indexNext++;
System.out.println("第"+ i +"次访问：\t\t" + ListUtils.listToString(list));
}else {

if(ListUtils.find(list, inputStr[i])) {
indexPre = ListUtils.findIndex(list, inputStr[i]);
if(clock[indexPre].equals("0")) {
clock[indexPre] = "1";
}
count++;
System.out.println("第"+ i +"次访问：\t\t" + ListUtils.listToString(list));
}else {
if(list.size() < memory) {
clock[indexNext] = "1";
indexNext++;
System.out.println("第"+ i +"次访问：\t\t" + ListUtils.listToString(list));
}else {
index = ListUtils.findZero(indexNext, clock, memory);
list.remove(index);
clock[index] = "1";
indexNext = index + 1;
System.out.println("第"+ i +"次访问：\t\t" + ListUtils.listToString(list));
}
}
}
if(indexNext > memory - 1) {
indexNext = Math.abs(memory - indexNext);
}
}
System.out.println("缺页次数：" + (inputStr.length-count));
}

}

• 工具类ListUtils
import java.util.List;

public class ListUtils {

public ListUtils() {

}

/**
* 输出
* @param list 将List转为数组并输出, out: 2, 3, 4
* @return
*/
public static String listToString(List list){

StringBuffer content = new StringBuffer();
for(int i = 0; i < list.size(); i++){
content.append(list.get(i));
if(i < list.size() - 1){
content.append(",");
}
}
return content.toString();
}

/**
* 在list中查找是否有str
* @param list
* @param str
* @return
*/
public static boolean find(List<String> list, String str){
boolean flag = false;
for(String lis : list){
if(lis.equals(str)){
flag = true;
}
}
return flag;
}

/**
* 在List中查找是否有String,如果有返回下标, 否则返回 -1
* @param list
* @param str
* @return
*/
public static int findIndex(List<String> list, String str) {

int index = 0;
for(String lis : list) {
if(lis.equals(str)) {
return index;
}
index++;
}
return -1;
}

public static boolean clockJudge(String[] clock, int index) {
if(clock[index].equals("0")) {
return true;
}
return false;
}
/**
*
* @param index 下标
* @param clock 时钟
* @param range 当前使用内存块
* @return
*/
public static int findZero(int index, String[] clock, int range) {

while(true) {

if(clock[index].equals("0")) {
break;
}else {
clock[index] = "0";
index++;
if(index > range-1) {
index = Math.abs(range - index);
}
}
}
return index;
}

/**
* 在数组中查找是否存在该字符串
* @param obj
* @param str
* @return
*/
public static boolean strJudge(Object[] obj, String str) {
boolean flag = false;
if(obj == null) {
return flag;
}
for(int i = 0; i < obj.length; i++) {
if(str.equals(obj[i])) {
flag = true;
break;
}
}
return flag;
}

/**
* 获取二维数组中同一列的行的长度
* @param str 数据
* @param length 二维数组的列
* @param memory 内存块
* @return
*
*/

public static int findNull(Object[][] str, int length, int memory) {

int index = 0;
if(str == null) {
return -1;
}
for(int i = 0; i < memory; i++) {
if(str[i][length] != null) {
index = i;
}
}
return index;
}
}

展开全文
• 通过请求页式管理方式中页面置换算法的模拟设计，了解虚拟存储技术的特点，掌握请 求页式存储管理中的页面置换算法。 容 二、课程设计内容 模拟实现 OPT（最佳置换）、FIFO 和 LRU 算法，并计算缺页率。 示 三、要求...
• 操作系统存储管理页面置换算法-----最佳页面置换算法模拟（JAVA实现） 话不多说，我们直接展示 package com.company; import java.util.Arrays; /** * @Auther: Bender * @Date: 2021/11/14 - 16:57 * @...

## 操作系统存储管理页面置换算法-----最佳页面置换算法模拟（JAVA实现）

话不多说，我们直接展示

package com.company;

import java.util.Arrays;

/**
* @Auther: Bender
* @Date: 2021/11/14 - 16:57
* @Description: com.company
* @version: 1.0
*/

//注释掉的是第一次做的程序，考虑不充分失败了
public class MyAlg {
public static boolean isIn(int a, int[] arr) {                  //判断某个数是否在数组中，返回true或者false
for(int i: arr){
if(a==i){
return true;
}
}
return false;

}

public static int isIn(int[] arr, int a) {                      //isIn方法重载，返回相等元素的数组下标，没有则返回下标
for(int i=0; i<arr.length; i++){
if(arr[i] == a)
return i;
}
return -1;

}
public static void optAdd(int[] contain, int[]list, int k) {                //最佳置换算法的缺页处理（前提：内存区已满）
/*分析：应该分为多种情况，******需要注意的是当作业队列中出现多次已经存在内存中的作业时（例子：内存区[5,6,7]   作业队列[1,6,7,6]）,我们只取第一个******
1.当后续作业队列中没有找到内存中已有的作业时
例子：内存区[6,7,8]   作业队列[1,2,3,4,5]
处理方式：默认替换0号元素
2.当后续作业队列中找到一个已经在内存中存在的作业时
例子：内存区[1,2,3]   作业队列[5,6,7,1,8]
处理方式：从0号元素开始，将未在作业队列中的元素依次替换
3、当后续作业队列中找到两个已经在内存中存在的作业时
例子：内存区[5,6,7]   作业队列[8,5,6]
处理方式：直接替换掉未出现的元素
4.当后续作业队列中找到内存区所有元素
例子：内存区[5,6,7]    作业队列[8,5,6,7]
处理方式：替换掉最后出现的元素
*/
int[] index = {-3,-3,-3};                           //要返回的下标队列，选取其中最小的值作为第k个元素要替换的下标******
int inum = 3;                                       //给index中的元素复制，随着赋值次数递减，最小的就是要替换的
int goalindex = 0;
for(int i=k+1; i<list.length; i++){                 //从k的下一个元素开始遍历，原因：第K个元素调用此方法的前提是这个元素并不在内存中
if(isIn(list[i],contain)){                      //该元素在内存中
int num = isIn(contain,list[i]);            //返回相同的元素下标

if(index[num]==-3)                          //确保只取第一次，后续忽略
index[num] = inum--;
}
}
if(index[0]<0 && index[1]<0 && index[2]<0 ){  //情况一：默认替换第0个元素
index[0] = -4;
}
int temp = index[0];
for(int i=1; i<index.length; i++){              //找出index中的最小值
if(index[i]<temp) {
temp = index[i];
goalindex = i;
}

}
contain[goalindex] = list[k];
System.out.println("缺页中断"+ Arrays.toString(contain));

}
public static void opt(int[] list) {
System.out.println("-----这是最佳页面置换算法-----");
int times = 0;                      //记录缺页率
int[] contain = new int[3];         //模拟内存空间，大小为3
int isempty = 0;                    //对contain模拟内存中的元素进行计数
/*此循环的作用：将contain模拟内存装满

*/
int i;                                          //在循环体外定义循环变量i是为了当循环结束时返回i的值（当内存区满后，对作业队列的执行从i+1开始）
for(i=0; i<list.length; i++) {
if(!isIn(list[i],contain)){                  //当要放入的元素不在内存区中
contain[isempty] = list[i];
isempty++;                              //内存区元素加一
System.out.println("缺页中断"+Arrays.toString(contain));
times++;
if(isempty==3) {                         //当内存区的元素个数为3（内存区已满的情况）即可跳出此循环
break;
}
}//当要访问的元素在内存区已经存在时，我们不做任何操作
}
//执行至此处内存区已满，下面对作业队列遍历，缺页时执行页面置换操作，不缺页时不做任何操作
//具体的页面置换我希望单独设计成一个方法（前提：内存区此时已满，不达成这个前提，程序设计会复杂的多）
for(++i; i<list.length; i++){                   //从上一个循环的下一个位置开始遍历作业队列
if(!isIn(list[i],contain)){                 //缺页时的操作
times++;
}//不缺页不执行任何操作

}
System.out.println("缺页次数:" + times + ",缺页中断率:" + (float)times / list.length);

}
//    public static int search(int[] contain, int[] arr, int index){      //返回在之后的作业队列中，内存中最后一个被访问的内存块的下标
//        int renum = 0;                                              //最后该方法的返回值，指明要替换的主存块
//        for(int i=index; i<arr.length; i++){                        //对之后的作业队列进行遍历
//            int num = isIn(contain,arr[i]);
//            if(num!=-1)
//                renum = num;
//        }
//        return renum;

//    }

//    public static void opt(int[] arr) {
//        System.out.println("-----这是最佳置换算法-----");
//        System.out.println("作业队列："+Arrays.toString(arr));
//        int times = 0;                          //用于记录置换次数（缺页中断次数），计算缺页率
//        int elements = 0;                       //记录内存中的作业数
//        int[] contain = new int[3];             //模拟主存空间
for(int i=0; i<3; i++){                 //三个作业装入，现在主存装满
contain[i] = arr[i];
}
//        contain[0] = arr[0];                    //先将第一个作业放入内存
//        times++;                                 //缺页中断次数加一
//        elements++;                              //内存作业数加一，变为1
//        System.out.println("主存块："+Arrays.toString(contain));
//        for(int i=1; i<arr.length; i++){           //遍历作业队列
//            if(!isIn(arr[i],contain)){              //当要访问的作业不在主存时
//                times++;                            //缺页终断率加一
//                if(elements>=3){                     //内存已满
int index = search(contain,arr,i);
contain[index] = arr[i];
//                    System.out.println("中断："+times+"次，"+Arrays.toString(contain));                   //打印置换后的内存情况
//                }else{                              //内存未满，直接加如内存
//                    contain[elements] = arr[i];
//                    elements++;
//                }
//            }else{                                  //当要访问的作业就在内存时，将被访问的作业调至最后，其他作业依次向前移，因为当后续作业队列中的作业都不在主存时，默认替换主存数组的第0个元素（即距离上次调用的时间最长）
//                if(elements>=3){                    //内存区已满的情况
//                    int index = isIn(contain,arr[i]);
//                    if(index==1){
//                        int temp = contain[1];
//                        contain[1] = contain[2];
//                        contain[2] = temp;
//                    }else if(index == 0){
//                        int temp = contain[0];
//                        contain[0] = contain[1];
//                        contain[1] = contain[2];
//                        contain[2] = temp;
//                    }
//                    System.out.println("未发生中断"+Arrays.toString(contain));
//                }
//            }
//            System.out.println("主存块："+Arrays.toString(contain));
//
//        }
//
//    }

public static void main(String[] args) {
int[] arr = {6,7,6,5,9,6,8,9,7,6,9,6};
opt(arr);
}
}



运行结果的展示：

看了这篇页面置换算法的文章，试运行了一下发现错误很多，很多点没有考虑到，所以自己重写了一下

展开全文
• } public void menu(){ System.out.println("**** 选择最佳置换算法请按1 **********"); System.out.println("**** 选择先进先出置换算法请按2 *******"); System.out.println("**** 选择最近最远未使用置换算法请...
• 该压缩包是页面置换算法的综合设计，包括五种页面置换算法，optimal算法，Fifo算法，lru算法，Lfu算法，改进型Clock算法，而且拥有完整的页面操作，可以直接在IDEA中导入工程，编译即可通过。
• 大学课程操作系统会有很多实验，LRU页面置换也是其中的一部分，希望能够参考，此LRU内存最大块为五块，可以修改成最大块为输入限制。
• 页面置换算法 在一个请求分页系统中，分别采用最佳置换算法、先进先出置换算法、最近最久未使用置换算法(LRU)时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数M分别为3和...
• 定义：OPT（最佳置换算法）：从主存中移出永远不再需要的页面，如果没有这样的页面存在，那就选择最长时间不需要访问的页面，来保证最低的缺页率。 import java.util.*; public class OPT { private static List&...
• 页面置换算法， 三种算法编写的程序，支持随机数输入，也支持示例输入，自带PPT例子验证结果
• 带有界面的算法，视自己需求下载。 主界面选择使用三种算法的一个。在创建中输入页面数，随机生成页面。在指定物理块中实现置换。点击查看将置换的过程显示出来。
• 本资源使用Java实现页面置换算法OPT、FIFO、LRU的模拟实现以及FIFO和LRU的命中率对比，内容包括Java源项目、jar包和bat文件。该资源的文字版信息请访问博客《操作系统实验：页面置换算法的模拟实现及命中率对比...
• 模拟操作系统页面置换的过程，具体实现了四种经典算法，即OPT、LRU、FIFO、CLOCK，并且利用Java中的图形库制作了一个好看的图形化界面
• 实验报告五 实验名称: 模拟页面置换算法 FIFOLRU 的实现 日期2015-12-9 班级13 级计科 一 实验目的 学号: 姓名 了解页面置换的概念理解页面置换的算法加深对页面置换算法的理解 二 实验内容 Java 编程语言实现 FIFO ...
• Java语言实现模拟页面置换算法.doc
• FIFO算法核心是对内存分配给进程的页块的处理 import java.util.Scanner; public class FIFO { public static void main(String[] args){ Scanner scan=new Scanner(System.in); int mempag=scan.nextInt(); ...
• 页面置换算法综合实现JavaJava Swing）算法导入算法分析一、界面分析二、界面设计三、界面相关算法设计算法展示一、操作展示二、算法比较结尾 算法导入        失踪人口回归...
• 一、背景 程序的运行，需要将指令和数据装入内存中进行执行，可内存的资源十分有限（目前常用的差不多8G,...当所访问的信息不在内存时，由OS将所需的部分调入内存，暂时不需要的内容换出（置换）到外存上。 二、置换
• 一次操作系统算法的描述，有最佳置换算法，先进先出置换算法，和最近最久未使用和最少使用算法（这是一个），需要的人自行下载 代码类型：JAVA 附注释，每行方便理解，最难写的是opt算法。 算法要求：（1）给出页面...

...

java 订阅