内存管理计算

阅读：评论：0

内存管理计算

一、补充概念

为了保证CPU执行指令时可正确访问存储单元，需将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址，这一过程称为地址映射。地址映射一般是由硬件完成的；页表项的相关状态位由硬件确定。

最佳适应算法（空闲内存管理）：从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。

首次适应算法（空闲内存管理）：从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表(空闲区链)中的空闲分区要按地址由低到高进行排序。该算法优先使用低地址部分空闲区。

最差适配算法（空闲内存管理）：从全部空闲区中找出能满足作业要求的、且大小最大的空闲分区，从而使得链表中的结点大小趋于均匀，适用于请求分配的内存大小范围较窄的系统。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按大小从大到小进行排序，自表头开始查找到第一个满足要求的自由区分配。该算法保留小的空闲区，尽量减少小的碎片产生。

下次适应算法（空闲内存管理）：下次适应算法总是最先找到、满足存储要求的那个空闲分区作为分配对象，但其每次找到合适的空闲分区就记住它的位置，以便下次就从该位置开始往下找，而不是像首次适应算法那样从头开始找。

位宽就是内存或显存一次能传输的数据量。虚拟存储空间主要与计算机地址位宽有关。

为了保证操作系统中文件的安全，可以采用的方法是建立副本、定时转储、规定文件的存取权限。

为了提高内存利用率并减少内部碎片，页面的划分与页表数量相关，可以找到平衡点。由于页表是位于内存连续存储空间的，所以页表也不应过大（即页面不应过小而导致页表大小过大）。

让操作系统跟踪每个进程的工作集，并为进程分配大于其工作集的物理块，如果还有空闲物理块，则可以再调一个进程到内存以增加多道程序数。如果所有工作集之和增加以至于超过了可用物理块的总数，那么操作系统会暂停一个进程，将其页面调出并且将其物理块分配给其他进程，防止出现抖动现象。

文件存储空间常用管理方法：空闲表法、空闲链表法、位示图法、成组链接法（Unix中利用空闲磁盘空间存储空闲磁盘信息）等。

内存空闲空间常用管理方法：空闲页面表法、空闲块链表法、位示图法等。

局部性原理：CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。三种不同类型的局部性如下：

时间局部性：如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。

空间局部性：在最近的将来将用到的信息很可能与现在正在使用的信息在空间地址上是邻近的，如代码顺序性、内存访问的顺序性。

顺序局部性：在典型程序中，除转移类指令外，大部分指令是顺序进行的。

编译、链接、装载代码运行过程中，链接是指把所有编译后得到的目标模块连接装配起来，再与函数库相连接成一个整体的过程。

在采用交换和覆盖技术的存储管理系统中，进程交换是指将暂时不用的进程代码、数据和部分进程控制块交换至磁盘。在分时系统中，用户的进程比内存能容纳的数量要多，这就需要在磁盘上保存那些内存放不下的进程。在需要运行这些进程时，再将它们装入内存。进程从内存移到磁盘，并再移回内存称为交换。

在虚拟页式存储管理中，某一时刻CPU的利用率很低而磁盘繁忙率（利用率）过高，意味着I/O损耗过高（可能是进程过多，频繁缺页导致），此时可以适当减少进程数量以提高系统效率。

在引入虚拟页式存储管理的系统中，可能会出现页面抖动、Belady异常、缺页中断以及页面写错误。

虚拟存储器系统通常定义三种策略来规定如何（或何时）进行页面调度：调入策略、置页策略和置换策略。

页表信息中的有效位，又称驻留位、存在位或中断位，表示该页是在内存还是外存。

快表存放在缓存（cache）中。

在虚拟页式存储管理中，为实现地址变换所涉及到的数据结构是空闲区表、页表、位图。

实现虚拟页式存储管理的硬件支持：系统有容量足够大的外存、系统有一定容量的内存、硬件提供实现虚-实地址映射的机制、缺页中断处理机制。

采用虚拟页式存储管理方式，需要缺页中断处理程序、页面调入策略、页面置换策略、程序分页机制和页表的软件条件。

第二次机会页面置换算法（页面置换）：在FIFO算法的基础上为每个页面增加一个R位，每次选择页面进行置换时，检查进入内存时间最久页面的R位，如果是0，那么这个页面既存储时间久又没有被使用，可以立即置换掉；如果是1，则将R位清0，并把该页面放到当前内存中页面链表的尾部，修改其进入时间，然后继续搜索；在下次置换之前，如果R位为0的页面再次被访问，则置R位为1。相对于FIFO，第二次机会置换算法给了每个页面第二次留下来的机会。

页式存储管理方案同固定分区一样，将物理内存划分成固定大小的块，每一块都可以分配使用，因而可以很好地避免外部碎片，但页式存储管理中，进程的最后一页经常装不满一个物理块，因此存在内部碎片，同样，固定分区存储管理方案中，分区通常要比装入的进程大，所以也存在内部碎片；而段式存储管理方案和可变分区一样，总是划分和进程大小相同的块来存放进程，所以不存在内部碎片，但是内存空间被多次分配、回收之后，总会留下一些很难再被分配的小空间，因此存在外部碎片；段页式存储管理同页式存储管理一样，可以很好地解决内存的外部碎片问题。

存储保护的目的在于为多个程序共享内存提供保障，使在内存中的各程序只能访问其自己的区域，避免各程序间相互干扰。存储保护的内容包括：保护系统程序不被用户有意或无意地冒犯；不允许用户程序读写不属于自己地址空间的数据，如系统区地址空间、其他用户程序的地址空间。

存储保护机构是操作系统运行环境中一个非常重要的部分。最常用的存储保护机构有界限寄存器和存储保护键。

缺页处理过程的简单描述：

①根据当前执行指令中的逻辑地址查页表的有效位，判断该页是否在内存；

②该页有效位“0”，形成缺页中断。保留现场，中断装置通过交换PSW让操作系统的中断处理程序占用处理器；

③操作系统处理缺页中断，寻找一个空闲的页面；

④若有空闲页，则把磁盘上读出的信息装入该页面中；

⑤修改页表及内存分配表，表示该页已在内存；

⑥如果内存中无空闲页，则按某种算法选择一个已在内存的页面，把它暂时调出内存；

⑦恢复现场，重新执行被中断的指令。

在一个多道程序设计系统中，地址转换的方式有地址重定位、静态重定位和动态重定位。其中动态重定位由软件和硬件相互配合来实现，硬件要有一个地址转换机构，该机构可由一个基址寄存器和一个地址转换路线组成。

采用可变分区方式管理时，要有硬件的地址转换机构做支持。硬件设置两个专用的控制寄存器：基址寄存器和限长寄存器。基址寄存器用来存放程序所占分区的起始地址，限长寄存器用来存放程序所占分区的长度。

二、计算题

（一）某虚拟页式存储管理系统采用二级页表进行地址转换，若不考虑高速缓存和快表，则进程每执行一条指令至少需要访问几次内存？

三次。一次访问一级索引，二次访问二级索引，三次访问该指令。（详细见《操作系统概念汇总一》）

（二）在一个请求调页的虚拟存储管理系统中，页面的大小为1024B。某进程在运行过程中要访问的虚拟地址分别为2050、4121、89、1056、2100、144、4097、156、1121、2200、3996、288、2200、567、5109，系统给该进程分配3个页框。若采用LRU页面置换算法，该进程的缺页率为多少？

（三）页式内存分配

（三）位示图文件管理（0表示空闲、1表示已使用）

（四）虚拟页式存储进程运行执行指令地址形式

（五）使用快表与查询页表的平均查询时间计算（仅考虑做题）

（6）CLOCK页面置换法的示例