Pil0tXia 的书房 Pil0tXia 的书房
首页
  • 第一章 操作系统引论
  • 第二章 进程的描述与控制
  • 第三章 处理机调度与死锁
  • 第四章 存储器管理
  • 第五章 虚拟存储器
  • 期末考试备考
汇编语言课程笔记
GitHub (opens new window)
首页
  • 第一章 操作系统引论
  • 第二章 进程的描述与控制
  • 第三章 处理机调度与死锁
  • 第四章 存储器管理
  • 第五章 虚拟存储器
  • 期末考试备考
汇编语言课程笔记
GitHub (opens new window)
  • 关于本文档

    • 操作系统课程笔记
  • 第一章 操作系统引论

    • 单道批处理
    • 多道批处理
    • 并发与并行的区别
    • 分时操作系统
    • 实时操作系统
    • 操作系统的四个基础特性
    • 现代OS的基本单位
    • 作业1
    • 内核
    • 中断和异常
    • 系统调用
    • 冷启动和热启动
    • 补充资料
    • 作业2
    • 附言
  • 第二章 进程的描述与控制

    • 程序的基本概念
    • 进程的基本概念
    • 作业
    • 进程控制
    • 进程的特征
    • 进程同步
    • 进程通信
    • 线程
  • 第三章 处理机调度与死锁

    • 处理机调度的层次
    • 队列调度模型
    • 选择调度算法的原则
    • 调度算法
    • 死锁
  • 第四章 存储器管理

    • 多级存储器结构
    • 程序的装入与链接
    • 连续内存分配
    • 非连续内存分配
  • 第五章 虚拟存储器

    • 虚拟存储器概述
    • 请求分页存储管理方式
    • 页面置换算法
      • 最佳置换算法
        • 案例分析
      • 先进先出置换算法
        • 案例分析
      • 最近最久未使用置换算法
        • 案例分析
      • Clock 置换算法
    • 内存分配策略和分配算法
    • 抖动与工作集
  • 第六章 输入输出系统

  • 第七章 文件管理

  • 期末考试备考

    • 考试题型
  • 操作系统
  • 第五章 虚拟存储器
Pil0tXia
2023-02-08
目录
最佳置换算法
案例分析
先进先出置换算法
案例分析
最近最久未使用置换算法
案例分析
Clock 置换算法

页面置换算法

# 页面置换算法

# 最佳置换算法

  • 是一种理想化的算法,有最好的性能,但无法实现

  • 可以用该算法来评价其他算法

  • 思想:被置换的页面是以后永远不使用或以后长时间不使用的(需向后遍历)

# 案例分析

系统为某个进程(有 8 个页面)只分配了 3 个物理块,进程有如下的页面号引用

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

求该进程在最佳置换算法下执行完毕缺页多少次?中断多少次?缺页率为多少?页面置换多少次?

image-20230208102620030

缺页次数:9 次

中断次数:每次缺页都会产生一次缺页中断 = 缺页次数 = 9 次

页面执行次数:页面走向中一共有 20 个页面执行

缺页率:缺页次数 / 页面执行次数 = 9/20 = 45%(不管用什么算法,都不可能使缺页率小于 45%)

页面置换次数:新页面置换内存中老的页面的次数 = 9 - 3 = 6 次

# 先进先出置换算法

  • 思想:淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面给予淘汰(向前看)

# 案例分析

题干同上

缺页次数或中断次数:15 次

页面执行次数:20

缺页率:15/20 = 75%

页面置换次数:15 - 3 = 12 次

# 最近最久未使用置换算法

  • 思想:选择和现在相比最长时间没有使用的页面进行置换(向前看)

  • 硬件

    • 寄存器:记录某进程在内存中各页的使用情况
    • 栈:用来保存当前使用的各个页面的页面号

# 案例分析

题干同上

缺页次数或中断次数:12 次

页面执行次数:20

缺页率:12/20 = 60%

页面置换次数:12 - 3 = 9 次

# Clock 置换算法

了解即可,不考察。

LRU 算法是较好的一种算法,但由于它要求有较多的硬件支持,故在实际应用中,大多采用 LRU 的近似算法。Clock 算法就是用得较多的一种 LRU 近似算法。

思想:为每页设置一位访问位,再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页被访问时,其访问位被置为 1。置换算法选择一位淘汰时,只需检查页的访问位。如果是 0,就选择该页换出;若为 1,则重新将它置 0,暂不换出,而是给该页第二次驻留内存的机会,再按照 FIFO 算法检查下一个页面。

image-20230208113938194

image-20230208114149443

image-20230208114239244

← 请求分页存储管理方式 内存分配策略和分配算法→

Copyright © 2022-2025 Pil0tXia | CC BY-NC-SA 4.0 Licensed | 苏ICP备2023001491号-1
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式