计算机操作系统学习笔记(9)——页面置换算法

简介: 计算机操作系统学习笔记(9)——页面置换算法

一、缺⻚异常(缺⻚中断

缺⻚异常(缺⻚中断)

当 CPU 访问的⻚⾯不在物理内存时,便会产⽣⼀个缺⻚中断,请求操作系统将所缺⻚调⼊到物理内存。就需要「⻚⾯置换算法」选择⼀个物理⻚,把它换出到磁盘,最后把正在访问的⻚⾯装⼊到这个物理⻚中。

⻚⾯置换算法的功能是,当出现缺⻚异常,需调⼊新⻚⾯⽽内存已满时,选择被置换的物理⻚⾯,也就是说选择⼀个物理⻚⾯换出到磁盘,然后把需要访问的⻚⾯换⼊到物理⻚。


二、最佳⻚⾯置换算法

最佳⻚⾯置换算法基本思路是,置换在「未来」最⻓时间不访问的⻚⾯。


所以,该算法实现需要计算内存中每个逻辑⻚⾯的「下⼀次」访问时间,然后⽐较,选择未来最⻓时间不访问的⻚⾯。


这很理想,但是实际系统中⽆法实现,因为程序访问⻚⾯时是动态的,我们是⽆法预知每个⻚⾯在「下⼀次」访问前的等待时间。所以,最佳⻚⾯置换算法作⽤是为了衡量你的算法的效率,你的算法效率越接近该算法的效率,那么说明你的算法是⾼效的。


三、先进先出置换算法

选择在内存驻留时间很⻓的⻚⾯进⾏中置换,这个就是「先进先出置换」算法的思想。

跟最佳⻚⾯置换算法⽐较起来,先进先出置换算法性能差了很多。


四、最近最久未使⽤的置换算法

最近最久未使⽤(LRU)的置换算法的基本思路是,发⽣缺⻚时,选择最⻓时间没有被访问的⻚⾯进⾏置换,也就是说,该算法假设已经很久没有使⽤的⻚⾯很有可能在未来较⻓的⼀段时间内仍然不会被使⽤。


这种算法近似最优置换算法,最优置换算法是通过「未来」的使⽤情况来推测要淘汰的⻚⾯,⽽ LRU 则是通过「历史」的使⽤情况来推测要淘汰的⻚⾯。


LRU实现的代价很⾼。需要在内存中维护⼀个所有⻚⾯的链表,最近最多使⽤的⻚⾯在表头,最近最少使⽤的⻚⾯在表尾。在每次访问内存时都必须要更新「整个链表」。在链表中找到⼀个⻚⾯,删除它,然后把它移动到表头是⼀个⾮常费时的操作


五、时钟⻚⾯置换算法

时钟⻚⾯置换算法就可以两者兼得,它跟 LRU 近似,⼜是对 FIFO 的⼀种改进。

该算法的思路是,把所有的⻚⾯都保存在⼀个类似钟⾯的「环形链表」中,⼀个表针指向最⽼的⻚⾯。


当发⽣缺⻚中断时,算法⾸先检查表针指向的⻚⾯:

如果它的访问位位是 0 就淘汰该⻚⾯,并把新的⻚⾯插⼊这个位置,然后把表针前移⼀个位置;

如果访问位是 1 就清除访问位,并把表针前移⼀个位置,重复这个过程直到找到了⼀个访问位为 0 的⻚⾯为⽌;


六、最不常⽤算法(LFU)

当发⽣缺⻚中断时,选择「访问次数」最少的那个⻚⾯,并将其淘汰


但还有个问题,LFU 算法只考虑了频率问题,没考虑时间的问题,⽐如有些⻚⾯在过去时间⾥访问的频率很⾼,但是现在已经没有访问了,⽽当前频繁访问的⻚⾯由于没有这些⻚⾯访

问的次数⾼,在发⽣缺⻚中断时,就会可能会误伤当前刚开始频繁访问,但访问次数还不⾼的⻚⾯。


相关实践学习
CentOS 7迁移Anolis OS 7
龙蜥操作系统Anolis OS的体验。Anolis OS 7生态上和依赖管理上保持跟CentOS 7.x兼容,一键式迁移脚本centos2anolis.py。本文为您介绍如何通过AOMS迁移工具实现CentOS 7.x到Anolis OS 7的迁移。
目录
相关文章
|
24天前
|
算法 调度 UED
探索操作系统的心脏:调度算法的奥秘与影响
【10月更文挑战第9天】 本文深入探讨了操作系统中至关重要的组件——调度算法,它如同人体的心脏,维持着系统资源的有序流动和任务的高效执行。我们将揭开调度算法的神秘面纱,从基本概念到实际应用,全面剖析其在操作系统中的核心地位,以及如何通过优化调度算法来提升系统性能。
|
4天前
|
算法
虚拟内存的页面置换算法有哪些?
【10月更文挑战第25天】不同的页面置换算法各有优缺点,在实际应用中,操作系统会根据不同的应用场景和系统需求选择合适的页面置换算法,或者对算法进行适当的改进和优化,以平衡系统的性能、开销和资源利用率等因素。
18 5
|
9天前
|
算法 大数据 Linux
深入理解操作系统之进程调度算法
【10月更文挑战第24天】本文旨在通过浅显易懂的语言,带领读者深入了解操作系统中的进程调度算法。我们将从进程的基本概念出发,逐步解析进程调度的目的、重要性以及常见的几种调度算法。文章将通过比喻和实例,使复杂的技术内容变得生动有趣,帮助读者建立对操作系统进程调度机制的清晰认识。最后,我们还将探讨这些调度算法在现代操作系统中的应用和发展趋势。
|
26天前
|
算法 调度 UED
深入理解操作系统的进程调度算法
【10月更文挑战第7天】在操作系统的心脏——内核中,进程调度算法扮演着至关重要的角色。它不仅影响系统的性能和用户体验,还直接关系到资源的合理分配。本文将通过浅显易懂的语言和生动的比喻,带你一探进程调度的秘密花园,从最简单的先来先服务到复杂的多级反馈队列,我们将一起见证算法如何在微观世界里编织宏观世界的和谐乐章。
|
1月前
|
边缘计算 算法 调度
探究操作系统的心脏:调度算法的进化与影响
【10月更文挑战第2天】 本文深入探讨了操作系统中核心组件——调度算法的历史演变、关键技术突破及其对现代计算的影响。通过详细回顾从单任务到多任务、实时系统及分布式计算环境下调度算法的发展,文章揭示了这些算法如何塑造我们的数字世界,并对未来的趋势进行了展望。不同于传统的摘要,本文特别聚焦于技术细节与实际应用的结合点,为读者提供一幅清晰的技术演进蓝图。
44 4
|
1月前
|
算法 调度 UED
探索操作系统的心脏:进程调度算法
【9月更文挑战第32天】在数字世界的每一次心跳中,都隐藏着一个不为人知的英雄——进程调度算法。它默默地在后台运作,确保我们的命令得到快速响应,应用程序平稳运行。本文将带你走进操作系统的核心,一探进程调度的奥秘,并通过代码示例揭示其背后的智慧。准备好跟随我一起深入这趟技术之旅了吗?让我们开始吧!
|
2月前
|
算法 调度
操作系统的心脏:深入解析进程调度算法
本文旨在深入探讨现代操作系统中的核心功能之一——进程调度。进程调度算法是操作系统用于分配CPU时间片给各个进程的机制,以确保系统资源的高效利用和公平分配。本文将详细介绍几种主要的进程调度算法,包括先来先服务(FCFS)、短作业优先(SJF)、时间片轮转(RR)以及优先级调度(PS)。我们将分析每种算法的基本原理、优缺点及其适用场景。同时,本文还将讨论多级反馈队列(MFQ)调度算法,并探讨这些算法在实际应用中的表现及未来发展趋势。通过深入解析这些内容,希望能够为读者提供对操作系统进程调度机制的全面理解。
|
2月前
|
存储 算法 前端开发
深入理解操作系统:进程调度与优先级队列算法
【9月更文挑战第25天】在操作系统的复杂世界中,进程调度是维持系统稳定运行的核心机制之一。本文将深入探讨进程调度的基本概念,分析不同的进程调度算法,并着重介绍优先级队列算法的原理和实现。通过简洁明了的语言,我们将一起探索如何优化进程调度,提高操作系统的效率和响应速度。无论你是计算机科学的初学者还是希望深化理解的专业人士,这篇文章都将为你提供有价值的见解。
|
22天前
|
算法
有哪些页面置换算法?
页面置换算法(Page Replacement Algorithms)在计算机操作系统中用于管理虚拟内存。
|
2月前
|
人工智能 算法 大数据
探究操作系统的心脏:调度算法的进化与影响
本文深入探讨了操作系统中核心组件——调度算法的发展及其对系统性能的影响。通过分析先来先服务、短作业优先、时间片轮转等传统调度算法,阐述了它们的原理和优缺点。同时,讨论了现代调度算法如多级队列和优先级调度在提高系统响应速度和处理能力方面的作用。文章还探讨了实时系统中的调度挑战,以及如何通过优化调度策略来满足不同应用场景下的性能需求。