推广做网站多少钱,开发app制作公司,有哪些做ppt用图片的网站有哪些问题,怎样在手机上建网站文章目录1 虚拟内存1.1 传统存储管理方式的特征、缺点1.2 局部性原理1.3 虚拟内存主要特征1.4 如何实现虚拟内存技术1.5 虚拟内存的基本概念小结2 请求分页管理方式2.1 页表机制2.2 缺页中断机构2.3 地址变换机构2.4 请求分页管理方式小结3 页面置换算法3.1 最佳置换算法 OPT3.…
文章目录1 虚拟内存1.1 传统存储管理方式的特征、缺点1.2 局部性原理1.3 虚拟内存主要特征1.4 如何实现虚拟内存技术1.5 虚拟内存的基本概念小结2 请求分页管理方式2.1 页表机制2.2 缺页中断机构2.3 地址变换机构2.4 请求分页管理方式小结3 页面置换算法3.1 最佳置换算法 OPT3.2 先进先出置换算法FIFO3.3 最近最久未使用置换算法LRU3.4 时钟置换算法CLOCK3.4.1 简单的CLOCK算法3.4.2 改进型的时钟置换算法3.5 页面置换算法小结4 页面分配策略4.1 页面分配、置换策略4.1.1 驻留集4.1.2 分配、置换策略4.2 何时调入页面4.3 从何处调入页面4.4 抖动颠簸现象4.5 页面分配策略小结1 虚拟内存 在传统存储管理方式的基础上引入了交换技术、覆盖技术使得内存利用率有所提升并且能从逻辑上扩充内存容量。 1.1 传统存储管理方式的特征、缺点 一次性作业必须一次性全部装入内存后才能开始运行。这会造成两个问题①作业很大时不能全部装入内存导致大作业无法运行②当大量作业要求运行时由于内存无法容纳所有作业因此只有少量作业能运行导致多道程序并发度下降。 驻留性一旦作业被装入内存就会一直驻留在内存中直至作业运行结束。事实上在一个时间段内只需要访问作业的一小部分数据即可正常运行这就导致了内存中会驻留大量的、暂时用不到的数据浪费了宝贵的内存资源。 可用虚拟存储技术解决上述问题
1.2 局部性原理 时间局部性如果执行了程序中的某条指令那么不久后这条指令很有可能再次执行如果某个数据被访问过不久之后该数据很可能再次被访问。因为程序中存在大量的循环 空间局部性一旦程序访问了某个存储单元在不久之后其附近的存储单元也很有可能被访问。 因为很多数据在内存中都是连续存放的并且程序的指令也是顺序地在内存中存放的 如何应用局部性原理
高速缓冲技术的思想 将近期会频繁访问到的数据放到更高速的存储器中暂时用不到的数 据放在更低速存储器中。 快表机制就是将近期常访问的页表项副本放到更高速的联想寄存器中 基于局部性原理在程序装入时可以将程序中很快会用到的部分装入内存暂时用不到的部分留在外存 就可以让程序开始执行。 在程序执行过程中当所访问的信息不在内存时由操作系统负责将所需信息从外存调入内存然后继续 执行程序。 若内存空间不够由操作系统负责将内存中暂时用不到的信息换出到外存。 在操作系统的管理下在用户看来似乎有一个比实际内存大得多的内存这就是虚拟内存 操作系统虚拟性的一个体现实际的物理内存大小没有变只是在逻辑上进行了扩充。
易混知识点 虚拟内存的最大容量是由计算机的地址结构CPU寻址范围确定的 虚拟内存的实际容量 min内存和外存容量之和CPU寻址范围 Eg某计算机地址结构为32位按字节编址内存大小为512MB外存大小为2GB。 则虚拟内存的最大容量为2 32B4GB 虚拟内存的实际容量min(2 32B,512MB2GB)2GB512MB 1.3 虚拟内存主要特征
虚拟内存有一下三个主要特征 多次性无需在作业运行时一次性全部装入内存而是允许被分成多次调入内存。对换性在作业运行时无需一直常驻内存而是允许在作业运行过程中将作业换入、换出。虚拟性从逻辑上扩充了内存的容量使用户看到的内存容量远大于实际的容量。 1.4 如何实现虚拟内存技术 虚拟内存技术允许一个作业分多次调入内存。如果采用连续分配方式会不方便实现。因此 虚拟内存的实现需要建立在离散分配的内存管理方式基础上。 主要区别 在程序执行过程中当所访问的信息不在内存时由操作系统负责将所需信息从外存调入内存然后继续执行程序。 操作系统要提供请求调页或请求调段功能 若内存空间不够由操作系统负责将内存中暂时用不到的信息换出到外存。操作系统要提供页面置换或段置换的功能
1.5 虚拟内存的基本概念小结 2 请求分页管理方式
请求分页存储管理与基本分页存储管理的主要区别
在程序执行过程中当所访问的信息不在内存时由操作系统负责将所需信息从外存调入内存然后继续执行程序。 操作系统要提供请求调页功能 将缺失页面从外存调入内存若内存空间不够由操作系统负责将内存中暂时用不到的信息换出到外存。 操作系统要提供页面置换的功能 将暂时用不到的页面换出外存
2.1 页表机制 与基本分页管理相比请求分页管理中为了实现“请求调页”操作系统需要知道每个页面是否已经调入内存如果还没调入那么也需要知道该页面在外存中存放的位置。 当内存空间不够时要实现“页面置换”操作系统需要通过某些指标来决定到底换出哪个页面有的页面没有被修改过就不用再浪费时间写回外存。有的页面修改过就需要将外存中的旧数据覆盖因此操作系统也需要记录各个页面是否被修改的信息。 为此引入页表机制描述页面和内存的情况 基本分页存储管理的页表VS请求分页存储管理的页表 2.2 缺页中断机构
在请求分页系统中每当要访问的页面不在内存时便产生一个缺页中断然后由操作系统的缺页中断处理程序处理中断。 此时缺页的进程阻塞放入阻塞队列调页完成后再将其唤醒放回就绪队列。如果内存中有空闲块则为进程分配一个空闲块将所缺页面装入该块并修改页表中相应的页表项。如果内存中没有空闲块则由页面置换算法选择一个页面淘汰若该页面在内存期间被修改过则要将其写回外存。未修改过的页面不用写回外存。
缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的因此属于内中断。 一条指令在执行期间可能产生多次缺页中断。 如copy A to B即将逻辑地址A中的数据复制到逻辑地址B而A、B属于不同的页面则有可能产生两次中断 中断回顾 2.3 地址变换机构 请求分页存储管理的地址变换机构较基本分页存储管理的地址变换机构的主要区别 新增步骤1请求调页查到页表项时进行判断 新增步骤2页面置换需要调入页面但没有空闲内存块时进行 新增步骤3需要修改请求页表中新增的表项 过程如下 注意 快表中有的页面一定是在内存中的。若某个页面被换出外存 则快表中的相应表项也要删除 否则可能访问错误的页面找到对应页表项后若对应页面未调入内存 则产生缺页中断之后由操作系统的缺页中断处理程序进行处理 在具有快表机构的请求分页系统中访问一个逻辑地址时若发生缺页则地址变换步骤是 查快表(未命中)——查慢表(发现未调入内存)——调页(调入的页面对应的表项会直接加入快表)——查快表(命中)——访问目标内存单元 补充细节 ①只有“写指令”才需要修改 “修改位”。并且一般来说只需修改快表中的数据只有要将快表项删除时才需要写回内存中的慢表。这样可以减少访存次数。 ②和普通的中断处理一样缺页中断处理依然需要保留CPU现场。 ③需要用某种“页面置换算法” 来决定一个换出页面。 ④换入/换出页面都需要启动慢速的I/O操作可见如果换入/ 换出太频繁会有很大的开销。 ⑤页面调入内存后需要修改慢表同时也需要将表项复制到快表中。 2.4 请求分页管理方式小结 3 页面置换算法 页面的换入、换出需要磁盘I/0会有较大的开销因此好的页面置换算法应该追求更少的缺页率
3.1 最佳置换算法 OPT
最佳置换算法OPTOptimal每次选择淘汰的页面将是以后永不使用或者在最长时间内不再被访问的页面这样可以保证最低的缺页率。 例假设系统为某进程分配了三个内存块并考虑到有一下页面号引用串会依次访问这些页面70120304230321201701 最佳置换算法可以保证最低的缺页率但实际上只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此最佳置换算法是无法实现的。
3.2 先进先出置换算法FIFO
先进先出置换算法FIFO每次选择淘汰的页面是最早进入内存的页面实现方法把调入内存的页面根据调入的先后顺序排成一个队列需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块。 例假设系统为某进程分配了三个内存块并考虑到有以下页面号引用串 321032432104 例假设系统为某进程分配了四个内存块并考虑到有以下页面号引用串 321032432104 Belady异常一一当为进程分配的物理块数增大时缺页次数不减反增的异常现象。 只有FIFO算法会产生Belady异常。另外FIFO算法虽然实现简单但是该算法与进程实际运行时的规律不适应因为先进入的页面也有可能最经常被访问。因此算法性能差 3.3 最近最久未使用置换算法LRU
最近最久未使用置换算法LRUleast recently used每次淘汰的页面是最近最久未使用的页面实现方法赋予每个页面对应的页表项中用访问字段记录该页面自上次被访问以来所经历的时间t。 当需要淘汰一个页面时选择现有页面中t值最大的即最近最久未使用的页面。 例假设系统为某进程分配了四个内存块并考虑到有以下页面号引用串 18178272183821317137 在手动做题时若需要淘汰页面可以逆向检查此时在内存中的几个页面号。在逆向扫描过程中最后一个出现的页号就是要淘汰的页面。 该算法的实现需要专门的硬件支持虽然算法性能好但是实现困难开销大
3.4 时钟置换算法CLOCK 最佳置换算法性能最好但无法实现先进先出置换算法实现简单但算法性能差最近最久未使用置换算法性能好是最接近OPT算法性能的但是实现起来需要专门的硬件支持算法开销大。 时钟置换算法是一种性能和开销较均衡的算法又称CLOCK算法或最近未用算法NRUNot Recently Used
3.4.1 简单的CLOCK算法 简单的CLOCK算法实现方法为每个页面设置一个访问位再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时其访问位置为1。当需要淘汰一个页面时只需检查页的访问位。如果是0就选择该页换出如果是1则将它置为0暂不换出继续检查下一个页面若第一轮扫描中所有页面都是1则将这些页面的访问位依次置为0后再进行第二轮扫描第二轮扫描中一定会有访问位为0的页面因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描 3.4.2 改进型的时钟置换算法
简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上如果被淘汰的页面没有被修改过就不需要执行I/0操作写回外存。只有被淘汰的页面被修改过时才需要写回外存。因此除了考虑一个页面最近有没有被访问过之外操作系统还应考虑页面有没有被修改过。在其他条件都相同时应优先淘汰没有修改过的页面避免I/0操作。这就是改进型的时钟置换算法的思想。修改位0表示页面没有被修改过修改位1表示页面被修改过。为方便讨论用访问位修改位的形式表示各页面状态。如11表示一个页面近期被访问过且被修改过。
算法规则将所有可能被置换的页面排成一个循环队列 第一轮从当前位置开始扫描到第一个00的帧用于替换。本轮扫描不修改任何标志位第二轮若第一轮扫描失败则重新扫描查找第一个01的帧用于替换。本轮将所有扫描过的帧访问位设为0第三轮若第二轮扫描失败则重新扫描查找第一个00的帧用于替换。本轮扫描不修改任何标志位第四轮若第三轮扫描失败则重新扫描查找第一个01的帧用于替换。 由于第二轮已将所有帧的访问位设为0因此经过第三轮、第四轮扫描一定会有一个帧被选中因此改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描 第一优先级最近没访问且没修改的页面第二优先级最近没访问但修改过的页面第三优先级最近访问过但没修改的页面第四优先级最近访问过且修改过的页面
3.5 页面置换算法小结 4 页面分配策略
4.1 页面分配、置换策略
4.1.1 驻留集 驻留集指请求分页存储管理中给进程分配的物理块的集合。在采用了虚拟存储技术的系统中驻留集大小一般小于进程的总大小。 若驻留集太小会导致缺页频繁系统要花大量的时间来处理缺页实际用于进程推进的时间很少驻留集太大又会导致多道程序并发度下降资源利用率降低。所以应该选择一个合适的驻留集大小。 考虑一个极端情况若某进程共有100个页面则该进程的驻留集大小为100时进程可以全部放入内存运行期间不可能再发生缺页。若驻留集大小为1则进程运行期间必定会极频繁地缺页。 注意系统为某个进程分配N个物理块等价于某个进程的驻留集大小为N
4.1.2 分配、置换策略 固定分配操作系统为每个进程分配一组固定数目的物理块在进程运行期间不再改变。即驻留集大小不变可变分配先为每个进程分配一定数目的物理块在进程运行期间可根据情况做适当的增加或减少。 即驻留集大小可变局部置换发生缺页时只能选进程自己的物理块进行置换。全局置换可以将操作系统保留的空闲物理块分配给缺页进程也可以将别的进程持有的物理块置换到外存再分配给缺页进程。 分配、置换策略搭配 固定分配局部置换系统为每个进程分配一定数量的物理块在整个运行期间都不改变。若进程在运行中发生缺页则只能从该进程在内存中的页面中选出一页换出然后再调入需要的页面。 这种策略的缺点是很难在刚开始就确定应为每个进程分配多少个物理块才算合理。采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给出的参数来确定为一个进程分配的内存块数 可变分配全局置换刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。当某进程发生缺页时从空闲物理块中取出一块分配给该进程若已无空闲物理块则可选择一个未锁定的页面换出外存再将该物理块分配给缺页的进程。 采用这种策略时只要某进程发生缺页都将获得新的物理块仅当空闲物理块用完时系统才选择一个未锁定的页面调出。被选择调出的页可能是系统中任何一个进程中的页因此这个被选中的进程拥有的物理块会减少缺页率会增加。 锁定系统会锁定一些页面这些页面中的内容不能置换出外存如重要的内核数据可以设为“锁定” 可变分配局部置换刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时只允许从该进程自己的物理块中选出一个进行换出外存。如果进程在运行中频繁地缺页系统会为该进程多分配几个物理块直至该进程缺页率趋势适当程度反之如果进程在运行中缺页率特别低则可适当减少分配给该进程的物理块。 可变分配全局置换只要缺页就给分配新物理块 可变分配局部置换要根据发生缺页的频率来动态地增加或减少进程的物理块
4.2 何时调入页面 预调页策略根据局部性原理一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没被访问过则又是低效的。因此可以预测不久之后可能访问到的页面将它们预先调入内存但目前预测成功率只有50%左右。故这种策略主要用于进程的首次调入 由程序员指出应该先调入哪些部分。 请求调页策略进程在运行期间发现缺页时才将所缺页面调入内存。由这种策略调入的页面一定会被访问到但由于每次只能调入一页而每次调页都要磁盘I/O操作因此I/O开销较大。 预调页策略运行前调入; 请求调页策略运行时调入 4.3 从何处调入页面 系统拥有足够的对换区空间页面的调入、调出都是在内存与对换区之间进行这样可以保 证页面的调入、调出速度很快。在进程运行前 需将进程相关的数据从文件区复制到对换区。 系统缺少足够的对换区空间凡是不会被修改的数据都直接从文件区调入由于这些页面不会被修改因此换出时不必写回磁盘下次需要时再从文件区调入即可。对于可能被修改的部分换出时需写回磁盘对换区下次需要时再从对换区调入。 UNIX 方式运行之前进程有关的数据全部放在文件区故未使用过的页面都可从文件区调入。若被使用过的页面需要换出则写回对换区下次需要时从对换区调入。 4.4 抖动颠簸现象 刚刚换出的页面马上又要换入内存刚刚换入的页面马上又要换出外存这种频繁的页面调度行为称为抖动或颠簸。 产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数分配给进程的物理块不够 为进程分配的物理块太少会使进程发生抖动现象。为进程分配的物理块太多又会降低系统整体的并发度降低某些资源的利用率
为了研究为应该为每个进程分配多少个物理块Denning提出了进程 “工作集”的概念
驻留集VS 工作集 驻留集指请求分页存储管理中给进程分配的内存块的集合。工作集指在某段时间间隔里进程实际访问页面的集合。 操作系统会根据“窗口尺寸”来算出工作集。 例 某进程的页面访问序列如下窗口尺寸为4各时刻的工作集为 工作集大小可能小于窗口尺寸实际应用中操作系统可以统计进程的工作集大小根据工作集大小给进程分配若干内存块。 如窗口尺寸为5经过一段时间的监测发现某进程的工作集最大为3那么 说明该进程有很好的局部性可以给这个进程分配3个以上的内存块即可满足进程的运行需要。 一般来说驻留集大小不能小于工作集大小否则进程运行过程中将频繁缺页。 拓展基于局部性原理可知进程在一段时间内访问的页面与不久之后会访问的页面是有相关性的。 因此可以根据进程近期访问的页面集合工作集来设计一种页面置换算法——选择一个不在工作集中的页面进行淘汰。 4.5 页面分配策略小结
