操作系统几种主要的页面置换算法分别是用什么数据结构实现的

算法通常只是描述解决问题的一个步骤,具体用什么数据结构实现则是视情况而定。LRU“实现起来比较困难,且开销大是因为LRU算法希望淘汰最后未使用的页面,而CLOCK算法则放低的要求,较久未使用即可,不一定是最久的。
算法通常只是描述解决问题的一个步骤,具体用什么数据结构实现则是视情况而定。LRU“实现起来比较困难,且开销大是因为LRU算法希望淘汰最后未使用的页面,而CLOCK算法则放低的要求,较久未使用即可,不一定是最久的。CLOCK算法恰好可以充分使用现有的为“请求分页存储管理“设计的硬件机构,所以也会更加高效,而LRU则难以使用现成的硬件机构来加速算法执行。
LRU又称最近最少使用,意为每次都淘汰最久未使用的页面。按照LRU的思想,一种实现思路如下三点:
下面来逐一分析这三点:
名列前茅点:这块内存空间不能太小,否则极易导致数据溢出,尤其是对于运行在server上OS来说,可能一开机就很久不关机,溢出的可能性更大。这段内存空间也不能太大,不然会造成空间浪费;
第二点:每执行一条指令必定带来至少一次访存,甚至更多,每次访存都要去维护这个时间开销无疑是很大的(CLOCK算法也要去维护一个bit,但是开销却小得多,原因后面再讨论),因为使用数组记录则需要线性的时间来维护,使用heap记录则需要对数时间来维护,而访存则是十分频繁的,这个代价是不能接受的;值得一提的是虽然看起来heap开销小一些,但是数据量很大的话heap相对无序array来说对缓存不友好,这也是一个问题,不过我不知道是否可以忽略;
第三点:选择出最久未使用的页面的开销也很大,使用无序array记录则需要线性的时间来查找,使用heap记录则需要对数时间来查找;
综合上述三点可知LRU具体实现起来确实很困难开销也很大。那么CLOCK算法和LRU相比优势在哪里?
未改进CLOCK算法需要维护一个bit,用来标志该页面是否被使用过;很自然地想到同样需要三点,即存储,维护和查找,但是前两点(存储和维护)的实现和开销相对LRU则简单很多。
延伸阅读:
功能:
当缺页中断发生,需要调入新的页面而内存已满时,选择内存当中哪个物理页面被置换。
目标:
尽可能地减少页面的换进换出次数(既缺页中断的次数)。具体来说,把未来不再使用的或短期内较少使用的页面换出,通常只能在局部性原理指导下依据过去的统计数据来进行预测。
页面锁定(frame locking):
用于描述必须常驻内存的操作系统的关键部分或时间关键(time-critical)的应用程序。实现的方法是L在页表中添加锁定标志位(lock bit)。使其不在页面置换算法范围之内,也就说不会被换入换出。
通常只需要考虑页号,因为偏移号一般不起作用。只保留页号。基于这个list来设计各种的页面替换算法。
通过模拟一个页面置换的行为并且记录产生页缺失数的数量。一般情况下,产生的缺页次数越少,性能就越高。
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系邮箱:hopper@cornerstone365.cn 处理,核实后本网站将在24小时内删除。
相关文章推荐
织信低代码开发“核心引擎”与“拓展能力”介绍
低代码平台不能只看表单、流程和页面。真正进入企业管理场景后,更重要的是底层能不能承载数据、权限、流程、集成、自动化和AI能力。
织信低代码平台的能力,可以分成两部分:核心引擎和拓展能力。核心引擎决定系统能不能搭起来、跑起来;拓展能力决定系统能不能接入更多业务场景,持续扩展。
一、核心引擎:支撑企业应用运行
1、数据建模引擎
织信以数据模型为基础,支持数据表、字段、记录、关联关系等能力。企业可以围绕客户、供应商、项目、合同、物料、设备、工单、库存等业务对象搭建系统,而不是只做一张张孤立表单。
它的价值在于:先把业务数据结构建清楚,再承接流程、权限、报表、接口和AI能力。这是织信区别于轻量表单工具的重要特点。
2、流程自动化引擎
织信提供工作流能力,支持审批、任务、变量、事件、子流程、多实例、多版本等机制。企业可以用它搭建采购审批、合同审批、项目立项、设备维修、费用报销、异常处理等流程。
流程自动化的价值,不只是线上审批,更是把责任、状态、节点和处理记录留在系统里,让业务可追踪、可复盘。
3、权限治理引擎
织信支持组织、部门、用户、角色、应用成员、应用角色等权限管理能力,可以根据岗位、部门和业务场景配置访问范围和操作权限。
企业系统里,不同部门看到的数据、能修改的字段、能审批的节点都不同。权限治理做细,系统才能既安全,又能正常协同。
4、自动化与脚本引擎
织信支持自动化、定时任务、监听器、脚本、HTTP请求等能力,可以在数据变化、流程变化或时间条件满足时自动触发动作。
例如自动提醒、自动校验、自动同步、自动生成记录、自动调用接口。这样系统不只是记录工具,也能参与业务执行。
二、拓展能力:支撑复杂场景扩展
1、系统集成能力
织信支持WebAPI、开放接口、HTTP、JDBC、消息队列、第三方集成、单点登录等能力,可以连接ERP、MES、CRM、OA、财务系统、钉钉、企业微信、飞书、LDAP、数据库等系统。
这让织信既能搭建新应用,也能作为企业系统之间的协同层。
2、界面与组件拓展能力
织信提供表单设计器、组件设计器、自定义组件字段、自定义视图、仪表盘、网站页面等能力,可以根据不同业务场景设计页面、看板和操作入口。
这使企业既能快速搭建标准应用,也能针对复杂需求做个性化扩展。
3、AI Agent能力
织信官方文档将其定位为企业级AI开发平台,强调数据建模、流程自动化、权限治理、系统集成与AI Agent能力。
在织信中,AI能力可以结合知识库、专家、技能、智能体、设计器智能体等模块,参与应用搭建、数据分析、流程辅助和业务处理。
更重要的是,织信的AI能力建立在数据、流程、权限和系统集成之上。这样AI进入企业系统时,能明确数据范围、操作边界和审批要求。
三、织信的独特之处
织信不是单点工具,而是企业信息化AI开发底座。
它既有低代码平台常见的表单、流程、权限、报表和自动化能力,也具备企业级系统需要的集成、部署、运维、SSO、信创适配、私有化部署等能力,同时把AI Agent纳入应用建设过程。
因此,织信更适合有复杂业务系统建设需求的企业。比如项目管理、OA、ERP扩展、MES补位、WMS、SRM、CRM、设备管理、人事管理等场景,都可以基于织信进行搭建和扩展。
简单来说,织信的价值在于:把数据模型、业务流程、权限治理、自动化执行、系统集成和AI能力放在同一个平台里,让企业系统搭得快、管得住、连得上,也能持续扩展。
各行业用户的共同选择







