一. Clock 算法介绍

二. 改进型Clock算法介绍

2.1 介绍

2.2 代码实现

  1. package com.wangt.java;
  3. import java.util.*;
  5. /**
  6.  * @author 王天赐
  7.  * @create 2019-12-11 20:27
  8.  */
  9. public class ClockProMain {
  10.     /**
  11.      * 记录命中数
  12.      */
  13.     private static int selectPages;
  14.     /**
  15.      * 存储命中率
  16.      */
  17.     private static double selectPagesRate;
  18.     /**
  19.      * 内存大小
  20.      */
  21.     private final static int MEMORY_SIZE = 5;
  23.     /**
  24.      * 获取随机进程数
  25.      * @return
  26.      */
  27.     private static List<Integer> getProcessSeq(){
  28.         // 随机页号的起始值
  29.         int start = 1;
  30.         // 随机页号的结束值
  31.         int end = 10;
  32.         List<Integer> processSeq = new ArrayList<>();
  33.         for (int i = 0; i < 10; i++) {
  34.             processSeq.add(randomInt(start, end));
  35.         }
  36.         return processSeq;
  37.     }
  39.     /**
  40.      * 随机生成指定范围的Int类型的数
  41.      * @param start 开始值
  42.      * @param end 结束值为 end - 1
  43.      * @return
  44.      */
  45.     private static int randomInt(int start , int end){
  46.         return (int)((Math.random() * (end - start)) + start);
  47.     }
  49.     /**
  50.      * 打印随机生成的页面信息
  51.      * @param processSeq
  52.      */
  53.     public static void printPageInfo(List<Integer> processSeq){
  54.         System.out.println("<==================== [页面信息] ====================>");
  55.         for (int i = 0; i < processSeq.size(); i++) {
  56.             System.out.println("第" + i +"个页面号为:" + processSeq.get(i));
  57.         }
  58.         System.out.println("<==================== [页面信息] ====================>");
  59.         System.out.println();
  60.     }
  62.     public static void printPageReplacementCase(List<Integer> memory){
  64.         for (int i = 0; i < 5; i++) {
  65.             if (memory.size() > i) {
  66.                 System.out.print(memory.get(i) + " ");
  67.             } else {
  68.                 System.out.print("0 ");
  69.             }
  70.         }
  71.         System.out.println();
  72.     }
  74.     /**
  75.      * 第一轮页面扫描
  76.      * @param memory
  77.      * @return
  78.      */
  79.     public static Integer firstRoundScan(Map<Integer,Page> memory){
  80.         // 要被淘汰的页号
  81.         Integer pageNum = -1;
  83.         for (Map.Entry<Integer, Page> kv : memory.entrySet()) {
  84.             Page page = kv.getValue();
  85.             if(page.getVisit() == 0 && page.getEdit() == 0){
  86.                 pageNum = kv.getKey();
  87.                 break;
  88.             }
  89.         }
  90.         return pageNum;
  91.     }
  93.     /**
  94.      * 第二轮页面扫描
  95.      * @param memory
  96.      * @return
  97.      */
  98.     public static Integer secondRoundScan(Map<Integer,Page> memory){
  99.         // 要被淘汰的页号
  100.         Integer pageNum = -1;
  102.         for (Map.Entry<Integer, Page> kv : memory.entrySet()) {
  103.             Page page = kv.getValue();
  104.             // 如果寻找到 访问位为 0, 编辑为 1的页面,则停止扫描
  105.             if(page.getVisit() == 0 && page.getEdit() == 1){
  106.                 pageNum = kv.getKey();
  107.                 break;
  108.             }else{
  109.                 // 第二遍扫描将访问位置为 0
  110.                 page.setVisit(0);
  111.             }
  112.         }
  113.         return pageNum;
  114.     }
  116.     public static void main(String[] args) {
  118.         List<Integer> processes = getProcessSeq();
  119.         Map<Integer,Page> pages = new HashMap<>();
  120.         List<Integer> memory = new ArrayList<>();
  122.         // 打印随机生成的页面信息
  123.         printPageInfo(processes);
  125.         for (Integer process : processes) {
  126.             // 判断内存中是否有该页面
  127.             if(pages.get(process) == null){
  128.                 // 如果返回值等于null, 则说明内存中没有该页面
  129.                 // 此时判断内存是否已满
  130.                 if(memory.size() < MEMORY_SIZE){
  131.                     // 如果内存没有满, 则直接添加即可
  132.                     // 该页面访问位置为 0 , 编辑为设置为 0
  133.                     memory.add(process);
  134.                     pages.put(process, new Page(process,1,0));
  135.                 }else{
  136.                     // 如果内存已满, 则需要换出页面
  137.                     // 换出策略 : V 表示访问位, E表示编辑位, 0 表示未访问, 1表示已访问/已编辑
  138.                     // V:0 ,E:0
  139.                     // V:0 ,E:1
  140.                     // V:1 ,E:0
  141.                     // V:1 ,E:1
  142.                     // 记录需要移除的页号
  143.                     Integer removePageNum = -1;
  144.                     do {
  145.                         // 第一轮扫描 : 查询 => 访问位=0,编辑位=0 的页面号
  146.                         if ((removePageNum = firstRoundScan(pages)) == -1) {
  147.                             // 第二轮扫描 : 查询 => 访问位=0,编辑位 =1的页面, 并且将扫描过的页面的访问位置为0
  148.                             removePageNum = secondRoundScan(pages);
  149.                         }else {
  150.                             break;
  151.                         }
  152.                         // 第三轮扫描 : 重复上述过程
  153.                         // 提示 如果都是 访问位=1,编辑位=0, 在进行第二轮扫描后, 都会变成 0,0 !
  155.                     }while (removePageNum == -1);
  156.                     // 移除需要淘汰的进程号
  157.                     memory.remove(removePageNum);
  158.                     pages.remove(removePageNum);
  159.                     // 将置换的页面添加进主存中
  160.                     memory.add(process);
  161.                     pages.put(process, new Page(process,1,0));
  162.                 }
  163.             }else{
  164.                 // 命中数加一
  165.                 selectPages++;
  166.             }
  167.             // 打印页面置换情况
  168.             printPageReplacementCase(memory);
  169.         }
  170.     }
  171. }
  173. class Page{
  174.     // 页号
  175.     private Integer pageNumber;
  176.     // 访问位
  177.     private Integer visit;
  178.     // 修改位
  179.     private Integer edit;
  181.     public Page() {
  182.     }
  184.     public Page(Integer pageNumber, Integer visit, Integer edit) {
  185.         this.pageNumber = pageNumber;
  186.         this.visit = visit;
  187.         this.edit = edit;
  188.     }
  190.     public Integer getPageNumber() {
  191.         return pageNumber;
  192.     }
  194.     public void setPageNumber(Integer pageNumber) {
  195.         this.pageNumber = pageNumber;
  196.     }
  198.     public Integer getVisit() {
  199.         return visit;
  200.     }
  202.     public void setVisit(Integer visit) {
  203.         this.visit = visit;
  204.     }
  206.     public Integer getEdit() {
  207.         return edit;
  208.     }
  210.     public void setEdit(Integer edit) {
  211.         this.edit = edit;
  212.     }
  213. }