操作系统 内存管理 虚拟存储技术与虚拟页式存储管理方案的实现
虚拟存储技术
基本思想：利用大容量的外存来扩充内存，产生一个比有限的实际内存空间大得多的、逻辑的虚拟内存空间，简称虚存。
操作系统把程序当前使用的部分保留在内存，而把其他部分保存在磁盘上，并在需要时在内存与磁盘之间动态交换。支持多道程序设计技术。
实现虚拟存储器需要以下的硬件支持：
- 系统有容量足够大的内存。
- 系统有一定容量的内存。
- 最主要的是：硬件提供实现虚-实地址映射的机制。
工作原理：当进程开始运行时，现将一部分程序转入内存，另一部分暂时留在外存但要执行的指令不在内存时，系统自动选择部分内存空间将其中原有的内容交换到磁盘扇区，并释放这些内存空间供其他进程使用。
交换技术是以进程为单位进行的，进程所需内存大于当前西戎内存，那么该进程就不能在系统中运行。
虚拟内存一般是以页或段为单位，所以如果一个进程所需内存大于当前系统内存，那么该进程仍然可以在系统中正常运行，因为该进程的一部分可以被还出到外存上。
虚拟页式存储管理
基本思想
在进程开始运行之前，不是装如全部页面。而是转入一个或零个页面，之后根据进程运行的需要，动态转入其他页面，当内存空间已满，而又需要装入新的页面时，则根据某种算法置换出某个页面，易变装入新的页面。
在使用虚拟页式存储管理时需要在页表中增加以下表项：
- 页号—页面的编号。
- 有效位—又称驻留位、存在位或中断位，表示该页是在内存还是在外存。
- 页框号—页面在内存中时所对应的内存块号。
- 访问位—又称引用位或参考位，表示该页在内存期间是否被访问过。
- 修改位—表示该页在内存中是否被修改过。
- 保护位—是否能读写执行。
- 禁止缓存位—采用内存映射I/O的机器中需要的位。
缺页中断
页面调度策略
虚拟存储器系统通常定义三种策略来规定如如何（或何时）进行页面调度：调入策略、置页策略和置换策略。
调入策略
什么时候将一个页由外存调入内存中。
- 请求调页：只调入发生缺页时所需的页面。这种调入策略实现简单，但容易产生较多的缺页中断，造成对外存I/O次数过多，时间开销过大，容易产生抖动现象。
- 预调页：在发生缺页需要调入某页时，一次调入该页以及相邻的几个页。提高了调页I/O效率，减少I/O次数。
置页策略
当线程产生缺页中断，内存管理器还必须确定将调入的虚拟页放在物理内存的何处。用于确定最佳位置的一组规则。
置换策略
如果缺页中断发生时物理内存已经满，“置换策略”被用于确定那个虚拟页面必须从内存中移出，为新的页面腾出空位。
- 固定分配局部置换：可基于进程的类型，为每一进程分配固定的页数的空间，在整个运行期间都不会再改变。采用该策略时，如果进程在运行中出现缺页，则只能从该进程的N个页面中选出一个换出，然后再调入一页，以保证分配给该进程的内存空间不变。
- 可变分配全局置换：先为系统中的每一进程分配一定数量的物理快，操作协同本身也保持一个空闲物理快队列，当某进程发生缺页是，由系统的空闲物理快队列中取出一物理快分配给该进程。但当空闲物理快队列中的物理快用完时，操作系统才从内存中选这一块调出。该块可能是系统中任意一个进程的页。
- 可变分配局部变量：基于进程的类型，为每个进程分配一定的数目的内存空间。但当某进程发生缺页时，只允许从该进程的页面中选出一页换出，这样就不影响其他进程的运行。
页面置换算法
如果刚被调出的页面又要立即要用，因而又要把它装入，而装入不久又被选中调出，调出不久又被装入，如此反复，使调度非常频繁，这种现象称之为“抖动”或称“颠簸”。
先进先出页面置换算法FIFO
选择最先装入内存的一页调出，或者说是把驻留在内存中时间最长的一页调出。
把转入内存的哪些页面的页号按进入的先后次序排好队，每次总是调用队首的页，当装入一个新页面后，把新页面的页号排入队尾。
把操作系统维护一个所有当前在内存中的页面的链表，最老的页面在表头，最新的页面在表尾。当发生缺页时，置换表头的页面并把新调入的页面加到表尾。
最近最少使用页面置换算法LRU
在缺页发生时，首先置换掉最长时间未被使用过的页面。
总是选择距离现在最长时间内没有被访问过的页面先调出。实现这种算法的一种方法是在页表中为每个页增加一个“计时”标志，记录该页面自上次被访问以来的所经历的时间，每个访问一次都应从“0”开始计时。
计时值最大的那一页调出（即最近一段时间里最长时间没有被使用过的页），此开销比较大。
最近最不常用页面置换算法LFU
根据在一段时间里页面被使用的次数选择可以调出的页，如果一个页面被访问的次数比较多，则是最常使用的页面，就不应该把它调出。
每一页设置一个计数器，每当访问一页时就把该页对应的计数器加1，另外，操作系统还要确定一个周期T，在周期T的一段时间内，若没有发生缺页中断，则把所有的计数器清“0”，开始一个新的周期从新计数。若在周期T的时间内发生了缺页中断，则选择计数值最小的那页调出。
实现要花很大的开销，并且要确定一个合适的周期T也有一定的难度。
理想页面置换算法OPT
该算法置换以后不再需要的或者在最长时间以后才会用到的页面。
作为衡量其他页面置换算法优势的一个标准。
最近未使用页面置换算法NRU
当访问页面（读或写）时设置R位，当写入页面（即修改页面）时设置M位。
用R位和M位可以构造一个简单的页面置换算法：当启动一个进程时，它的所有页面的两个位都是由操作系统设置为0，定期将R位（比如在每次时钟中断时）清零，以区别最近没有被访问的页面和被访问的页面。
NRU算法随机地从类编号最小的非空类中挑选一个页面淘汰。在最近一个时钟滴答中（典型的时间为20ms）置换一个没有被访问的已经修改的页面比要置换一个被频繁使用的“干净”页面好。
优点：易于理解和能够有效地被实现。但性能并不是最好的。
第二次机会页面置换的算法
FIFO算法可能会把经常使用的页面置换出去。检查进入内存时间最久的页面的R位，如果是0，那么这个页面即老有没有被使用过，可以立刻置换掉；如果是1，就将R位清0，并把该页放到链表的尾部，修改其进入时间，然后继续搜索。
基本思想：寻找一个从来没有访问过的页面，如果所有的页面都被访问过了，该页面就退化为FIFO算法。
时钟页面置换算法Clock
把所有的页面都保存在一个类似时钟面的环形链表中，一个表针指向最老的页面。当发生缺页中断时，算法首先检查表针指向的页面，如果他的R位为0，就置换这个页面，并把新的页面插入到这个位置，然后把表针前移一个位置，如果是R位是1，就清楚R位并把表指针前移一个位置，重复这个过程直到找到一个R位为0的页面为止。
缺页中断率
假设一个程序共有n页，系统分配给它的内存块是m块（m、n均为正整数，且1<=m<=n）。该程序最多有m页可以同时装入内存。如果程序执行中访问页面的总次数为A，其中有F次访问的页面尚未装入内存，故产生了F次缺页中断。
f = F / A
把f称为“缺页中断率”。
缺页中断率与缺页中断的次数有关。
分配给程序的内存块数
分配给程序的内存块数多，这同时装入内存的页面数就越多，故减少了缺页中断的次数，也就降低了缺页中断率，反之，缺页中断率就高。
页面的大小
页面的大小取决于内存分块的大小，快大页面也大，每个页面大了则程序的页面数就少。装入程序时是按页面存放在内存中的，因此，装入一页的信息量就越大，就减少了缺页中断的次数，降低了缺页中断率。反之，若页面小则缺页中断率就越高。
程序编制方法
缺页中断率与程序的局部化程度密切相关。
页面置换算法
页面置换算法对缺页中断率的影响很大，调度不好就会出现“抖动”，理想的调度算法（OPT）能使缺页中断率最低。
虚拟存储管理的性能问题
在虚拟内存中，页面可能在内存与外存之间频繁调度，有可能出现抖动或颠簸。
颠簸是由于缺页率高引起的。
一般进程在一段时间内集中访问一些页面，称为“活动页面”，如果分配给一个进程的内存物理页面数太少，使得该进程所需要的“活动页面”不能全部装入内存，则进程在运行过程中会频繁的发生缺页中断，从而产生颠簸。
段式与段页式存储管理方案
段式与段页式存储管理方案
设计思想
系统将内存空间动态划分为为若干个长度不同的区域，每个区域乘坐一个物理段。每个物理段在内存中有一个起始地址，乘坐段首址。将物理段中的所有单元从0开始依次编址，称为段内地址。
用户程序则按逻辑上有完整意义的段来划分，称为逻辑段（简称段），将用户程序的所有逻辑段从0开始编号，称为段号。将一个逻辑段中的所有单元从0开始编址，称为段内地址。用户程序的逻辑地址由段号和段内两部分组成。
内存分配时，系统以段为单位进行内存分配，为每个逻辑段分配一个连续的内存区（物理段）。逻辑上连续的段在内存中不一定连续存放。
段表包括逻辑段号、物理段起始地址（段首址）和物理长度三项内容。
按逻辑段的顺序排列，放在内存中。
地址转换
与页式存储管理相同，为了实现段式管理，系统提供一对寄存器：段表起始地址和段表长度寄存器。
段表起始地址寄存器用于保存正在运行程序的段表在内存的首地址。当进程被调度程序选中并投入使用时，系统将其段表首地址从进程控制块中取出送入该寄存器。
段表长度寄存器用于保护正在运行进程的段表的长度。当进程被选中时，系统将他从进程控制块中取出送入该寄存器。
与可变分区管理方案的比较
相同：有相同结构的内存分配表，包括已分配区表和空闲区表。
不同：段式存储管理是为程序的每一个分段分配一个连续的内存空间。
段页式存储管理方案
为用户提供了一个二维地址空间，满足程序和信息的逻辑分段的要求。段式管理反映了程序的逻辑结构，有利于段的动态增长以及共享和内存保护，大大方便了用户。
特征：等分内存，有效的克服了碎片，提高了存储器的利用率。
基本思想：用页式存储方法来分配和管理内存空间，即把内存划分为若干大小的相等的页面；用段式方法对用户程序按照其内在的逻辑关系划分成若干个大小相等的页面。内存是以页为基本单位的分配给每个用户程序的，逻辑上相邻的页面在物理内存中不一定相邻。
需要增加段式管理和页式管理的成分：必须为每个程序建立一张段表；由于一个段又被分为了若干也，系统有为每个段建立一张表页。段表中记录了该段对应页表的起始地址和长度，而页表则给出该段逻辑页面与内存块号之间的对应关系。