一、请求分页管理方式

• 请求分页 存储管理与基本分页存储管理的主要区别：
  ①、在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存【操作系统要提供请求调页功能，将缺失页面从外存调入内存】，然后继续执行程序。
  ②、若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存【操作系统要提供页面置换的功能，将暂时用不到的页面换出外存】。

（一）页表机制

（二）缺页中断机构

• 假设此时要访问逻辑地址=（页号，页内偏移量）=（0, 1024）
• 在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。
• 此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。

1. 内存存在空闲块

• 如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。
  

2. 内存中不存在空闲块

• 如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。
  

（三）缺页中断机构

• 缺页中断**是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断一条指令在执行期间，可能产生多次缺页中断。（如：copy A to B，即将逻辑地址A中的数据复制到逻辑地址B，而A、B属于不同的页面，则有可能产生两次中断）

（四）地址变换机构

• 请求分页存储管理与基本分页存储管理的主要区别：
  在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。
  若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。
  
• 新增步骤1：请求调页（查到页表项时进行判断）
• 新增步骤2：页面置换（需要调入页面，但没有空闲内存块时进行）
• 新增步骤3：需要修改请求页表中新增的表项
  
  

二、页面分配策略

（一）驻留集

• 驻留集：指请求分页存储管理中给进程分配的物理块的集合。
• 在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。
• 考虑一个极端情况，若某进程共有100个页面，则该进程的驻留集大小为100时进程可以全部放入内存，运行期间不可能再发生缺页。若驻留集大小为1，则进程运行期间必定会极频繁地缺页
• 若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少；
• 驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小。
• 固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。即，驻留集大小不变
• 可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。即，驻留集大小可变。
• 局部置换：发生缺页时只能选进程自己的物理块进行置换。
• 全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。
  

（二）页面分配、置换策略

• 固定分配局部置换 ：系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。这种策略的缺点是：很难在刚开始就确定应为每个进程分配多少个物理块才算合理。（采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给出的参数来确定为一个进程分配的内存块数）
• 可变分配全局置换 ：刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。当某进程发生缺页时，从空闲物理块中取出一块分配给该进程；若已无空闲物理块，则可选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程。采用这种策略时，只要某进程发生缺页，都将获得新的物理块，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。被选择调出的页可能是系统中任何一个进程中的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加。【系统会锁定一些面，这些页面中的内容不能置换出外存（如：重要的内核数据可以设为“锁定”）】
• 可变分配局部置换 ：刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存。如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度；反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块。
• 可变分配全局置换 ：只要缺页就给分配新物理块
• 可变分配局部置换 ：要根据发生缺页的频率来动态地增加或减少进程的物理块

（三）何时调入页面？

1. 预调页策略：根据局部性原理【局部性原理：主要指空间局部性，即：如果当前访问了某个内存单元，在之后很有可能会接着访问与其相邻的】，一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没被访问过，则又是低效的。因此可以预测不久之后可能访问到的页面，将它们预先调入内存，但目前预测成功率只有50%左右。故这种策略主要用于进程的首次调入【运行前调入】，由程序员指出应该先调入哪些部分。
2. 请求调页策略：进程在运行期间发现缺页时才将所缺页面调入内存【运行时调入】。由这种策略调入的页面一定会被访问到，但由于每次只能调入一页，而每次调页都要磁盘I/O操作，因此I/O开销较大。

• 系统拥有足够的对换区空间：页面的调入、调出都是在内存与对换区之间进行，这样可以保证页面的调入、调出速度很快。在进程运行前，需将进程相关的数据从文件区复制到对换区。
  
• 系统缺少足够的对换区空间：凡是不会被修改的数据都直接从文件区调入，由于这些页面不会被修改，因此换出时不必写回磁盘，下次需要时再从文件区调入即可。对于可能被修改的部分，换出时需写回磁盘对换区，下次需要时再从对换区调入。
  
• UNIX 方式：运行之前进程有关的数据全部放在文件区，故未使用过的页面，都可从文件区调入。若被使用过的页面需要换出，则写回对换区，下次需要时从对换区调入。
  

（四）抖动（颠簸）现象

（五）工作集

• 驻留集 ：指请求分页存储管理中给进程分配的内存块的集合。
• 工作集 ：指在某段时间间隔里，进程实际访问页面的集合。
  
• 工作集大小可能小于窗口尺寸，实际应用中，操作系统可以统计进程的工作集大小，根据工作集大小给进程分配若干内存块。如：窗口尺寸为5，经过一段时间的监测发现某进程的工作集最大为3，那么说明该进程有很好的局部性，可以给这个进程分配3个以上的内存块即可满足进程的运行需要。一般来说，驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页。
• 拓展：基于局部性原理可知，进程在一段时间内访问的页面与不久之后会访问的页面是有相关性的。因此，可以根据进程近期访问的页面集合（工作集）来设计一种页面置换算法——选择一个不在工作集中的页面进行淘汰。
  

OS- -请求分页系统、请求分段系统和请求段页式系统(二)

一、基本分段存储管理方式

• 分段 : 进程的地址空间会按照自身的逻辑关系划分为若干个段, 每个段都有一个段名, 每段从0开始编址
• 内存分配规则 : 以段为单位进行分配, 每个段在内存中占据连续空间, 但各段之间可以不相邻

1.分段系统的组成:

• 段号------ 段号的位数决定了每个进程最多可以分为几个段
• 段内地址------段内地址的位数决定了每个段的最大长度是多少

2.段表

• 程序分为多个段, 各个段离散地装入内存, 为了保证程序能正常运行, 就必须能从物理内存中找到各个逻辑段的存放位置. 为此,需为每个进程建立一张段映射表, 简称 " 段表 " .
  
• 关于段表 :

• 每个段对应一个段表项, 记录着该段在内存中的起始位置 ( 基址 ) 和 段长
• 各个段表项的长度是相同的, 因此和页号一样, 段号是" 隐含"的, 不占据存储空间

3.查找过程

4.分段和分页的对比

• 页是信息的物理单位, 分页的主要目的是为了实现离散分配, 提高内存利用率. 分页仅仅是系统管理上的需要, 完全是系统行为,对用户是不可见的
• 段是信息的逻辑单位, 分段的主要目的是更好地满足用户需求. 一个段通常包含着一组属于一个逻辑模块的信息, 分段对用户是可见的,用户编程时需要显式地给出段名
• 页的大小是固定且由系统决定, 段的长度却不固定, 决定于用户编写的程序
• 分页的用户进程地址空间是一维的, 分段的用户进程是二维的.
  
• 分段比分页更容易实现信息的共享和保护

二、段页式内存管理方式

1.分页, 分段管理的优缺点分析

2.段页式管理的结构

• 先分段 , 再分页
  
• 段页式管理的逻辑地址结构 :由段号, 页号, 页内偏移 组成
  
• 段号的位数决定了每个进程最多可以分为几个段
• 页号位数决定了每个段最大有多少页
• 页内偏移量决定了页面大小和内存块的大小

• 注意 :

• "分段"对用户是可见的, 而将各段"分页"对用户是不可见的, 系统会根据段内地址自动划分页号和段内偏移量,

• 因此段页式管理的地址结构是"二维"的.

3.段表, 页表

• 每一个进程对应一个段表, 每一个段又对应一个页表, 因此一个进程可能对应多个页表.
  

4.查找过程

1. 由逻辑地址得到段号, 页号, 页内偏移
2. 段号与段表寄存器的段长度比较, 检查是否越界
3. 由段表始址, 段号找到对应段表项 ---- ( 一次访存)
4. 根据段表中记录的页表长度, 检查页号是否越界
5. 由段表中的页表地址, 页号得到查询页表, 找到相应页表项 ---- ( 二次访存)
6. 由页面存放的内存块号, 页内偏移得到最终的物理地址
7. 访问目标单元 ---- ( 三次访存)

三、虚拟内存

• 传统存储管理方式的特征, 缺点：
  
• 一次性 : 作业必须一次性全部装入内存才能开始运行
• 作业很大时, 无法装入导致大作业无法运行
• 大量作业要求运行时内存无法容纳所有作业, 导致多道程序并发度下降
• 驻留性 : 一旦作业被装入内存, 就会一直驻留在内存中, 直到作业运行结束, 这样会导致内存中驻留大量的, 暂时用不到的数据,浪费内存资源

虚拟内存—基于局部性原理

1. 在程序装入时, 将程序中很快会用到的部分装入内存, 暂时用不到的部分留在外存, 就可以让程序开始执行.
2. 在程序执行过程中, 当所访问的信息不在内存时, 由操作系统负责将所需信息由外存调入内存, 然后继续执行程序.
3. 内存空间不够时, 操作系统负责将内存中暂时用不到的信息换出到外存
4. 在用户看来, 就有一个比实际内存大很多的内存, 这就叫虚拟内存

注意 :

• 虚拟内存的最大容量是由计算机的地址结构 ( CPU的寻址范围 ) 确定的,
• 虚拟内存的实际容量 = 𝑚𝑖𝑛(内存容量+外存容量,𝐶𝑃𝑈寻址范围)
  

• 虚拟内存的实现 :

• 请求分页存储管理

• 请求分段存储管理

• 请求段页式存储管理

• 操作系统需要提供的功能 :

• 请求调页 ( 段 )

• 页面置换 ( 段置换 )

• 缺页时请求掉页不一定页面置换, 若还有可用的内存块, 就不用进行页面置换

四、请求分页管理方式

1.页表机制

2.缺页中断机构

• 在请求分页操作系统中, 每当要访问的页面不在内存时, 便产生一个缺页中断, 然后由操作系统的缺页中断处理程序处理中断

• 此时缺页的进程阻塞, 放入阻塞队列, 调页完成后再将其唤醒, 放回就绪队列

• 如果内存中有空闲块, 则为进程分配一个空闲块, 将所缺页面装入该块, 并修改页表中相应的页表项

• 如果内存中没有空闲块, 则由页面置换算法选择一个页面淘汰, 若该页面在内存期间被修改过, 则要将其写回外存, 未修改过的页面不用写回外存

• 缺页中断是因为当前执行的指令想要访问目标页面未调入内存而产生的, 因此属于内中断 :
  

3.页面置换算法

• 最佳置换算法OPT

• 每次选择淘汰的页面是以后永不使用或者在最长时间内不会使用的页面, 保证最低的缺页率 . 但是操作系统无法预判页面访问序列, 这种算法是无法实现的

• 先进先出置换算法 FIFO

• 每次淘汰的页面是最早进入内存的页面

• 实现 : 将调入内存的页面根据调入的先后顺序排成一个队列, 需要置换页面的时候选择队首的页面.

• 实现简单, 算法性能差, 不适应进程实际运行时的规律

• 最近最久未使用算法 LRU
  

• 当需要淘汰一个页面的时候, 选择现有页面中t值最大的, 即最近最久未使用的页面.

• 需要淘汰页面时, 逆向检查此时在内存中的几个页面号, 最后一个出现的页号就是需要被淘汰的

• LRU算法的特点 : 性能好, 但实现起来需要专门的硬件支持, 算法开销大

• 时钟置换算法 ( CLOCK ) / 最近未用算法 ( NRU )

他们是同一种算法.

• 简单的CLOCK算法的实现方法 :
  
• 简单的时钟置换算法仅考虑到了一个页面最近是否被访问过
• 但是事实上, 如果被淘汰的页面没有被修改过, 就不需要执行I/O操作写回外存. 只有被淘汰的页面被修改过时, 才需要写回外存
• 因此, 除了考虑一个页面最近有没有被访问过之外, 操作系统还应该考虑页面有没有被修改过.
• 在其他条件都相同时, 应该优先淘汰没有修改过的页面, 避免I/O操作, 这就是改进型的时钟置换算法的思想.

利用 (访问位, 修改位) 的形式表示各页面状态

• 特点 : 开销小, 性能也不错

四、页面分配策略

1.驻留集

• 请求分页存储管理器中给进程分配的物理块的集合. ( 系统给进程分配了n各物理块 ----的另一种表述 : 驻留集大小为n)

• 在采用虚拟存储技术的系统中, 驻留集的大小一般小于进程的总大小

• 如果驻留集太小, 会导致缺页频繁, 系统要花大量的时间来处理缺页, 实际用于进程推进的时间很少

• 如果驻留集太大, 会导致多道程序并发度下降, 资源利用率降低

2.几种分配策略

• 固定分配全局置换不存在, 因为进程物理块固定后不会再分配给别人
  

• 可变分配全局置换 : 只要缺页就给分配新物理块
• 可变分配局部置换 : 根据发生缺页的频率来动态地增加或减少进程的物理块

3.何时调入页面

• 预调页策略
• 请求调页策略
  
  

4.何处调入页面

• 文件区用于调入不会被修改的数据, 对换区用用于调入可能被修改的数据

5.抖动(颠簸)现象

6.工作集

• 一般来说 驻留集的大小不能小于工作集的大小, 否则进程运行过程中将频繁缺页.

4.5 虚拟存储器的基本概念

• 一、虚拟存储器的引入
• 二、虚拟存储器的实现方法
• 三、虚拟存储器的特征

一、虚拟存储器的引入

1、常规存储器管理方式的特征

 一次性：作业在运行前一次性地全部装入内存
 驻留性：作业装入内存后，便一直驻留在内存中，直至作业运行结束

问题：一次性及驻留性在程序运行时是否是必须的？

2、程序运行的局部性原理

3、虚拟存储器的定义

• 基于局部性原理，应用程序在运行前，没有必要全部装入内存，，仅将当前要运行的部分页面或段先装入内存即可，其余部分暂留在外存上。
• 虚拟存储器：是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却接近于外存。

二、虚拟存储器的实现方法

在虚拟存储器中，允许将一个作业分多次调入内存。如果采用连续分配方式，不仅造成内存资源的浪费，而且无法从逻辑上扩大内存容量。因此，虚拟存储器的实现都是建立在离散分配的存储管理方式的基础上。

两种实现方法：请求分页系统和请求分段系统

三、虚拟存储器的特征

• 多次性：一个作业被分成多次调入内存运行
• 对换性：允许在作业的运行过程中进行换进、换出
• 虚拟性：能够从逻辑上扩充内存容量，使用户所看到的内存容量远远大于实际内存容量

虚拟性以多次性和对换性为基础。

多次性和对换性又必须建立在离散分配的基础上。

4.6 请求分页系统

请求分页系统是建立在基本分页基础上的，增加了请求调页功能和页面置换功能。换入和换出的基本单位都是长度固定的页面，因而在实现上比请求分段系统简单。

• 一、请求分页中的硬件支持
• 二、内存分配策略和分配算法
• 三、调页策略

一、请求分页中的硬件支持

1、页表机制

在请求分页系统中所需要的主要数据结构是页表。基本作用仍是将用户地址空间中的逻辑地址变换为内存空间中的物理地址。由于只将程序的一部分装入内存，还有一部分在外存中，因此须在页表中增加若干项，供程序或数据在换进换出时参考。

2、缺页中断机构

3、地址变换机构

请求分页系统中的地址变换机构，是在分页系统地址变换机构的基础上，再为实现虚拟存储器而增加了某些功能而形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等。

二、内存分配策略和分配算法

为进程分配内存时，涉及三个问题：

• 最小物理块数的确定
• 物理块的分配策略
• 物理块的分配算法

1、最小物理块数的确定

• 最小物理块数，指能保证进程正常运行所需的最小物理块数。
• 当系统为进程分配的物理块数小于此值时，进程将无法运行。
• 进程应获得的最小物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。

2、物理块的分配策略

在请求分页系统中，可以采取两种内存分配策略，即固定和可变分配策略。在进行置换时，也可以采取两种策略，即全局置换和局部置换。于是组合出三种适合的策略。

• 固定分配局部置换
• 可变分配全局置换
• 可变分配局部置换

固定分配局部置换

• 为每个进程分配一定数目的物理块，在整个运行期间不再改变。采用该策略时，如果进程在运行中发现缺页，只能从该进程在内存中的n个页面中选出一页换出，然后再调入一页。
• 困难：应为每个进程分配多少个物理块难以确定。

可变分配全局置换

在采用这种策略时，先为系统中的每个进程分配一定数目的物理块，而OS自身也保持一个空闲的物理块队列。如果某进程发生缺页时，由系统从空闲的物理块队列中，取出一个物理块分配给该进程，并将欲调入的页装入其中。当空闲物理块队列中的物理块用完后，OS才能从系统中的任一进程中选择一页调出。

可变分配局部置换

为每个进程分配一定数目的物理块，如果某进程发生缺页时，只允许从该进程在内存的页面中选出一页换出，不会影响其他进程执行。如果进程在运行中频繁发生缺页中断，则系统再为进程分配若干物理块；如果进程在运行中缺页率特别低，则适当减少分配给该进程的物理块。

3、物理块分配算法

在采用固定分配策略时，如何将系统中可供分配的物理块分配给各个进程，可采用以下几种算法：

• （1）平均分配算法：将系统中所有可供分配的物理块，平均分配给各个进程。
  缺点：未考虑各进程本身的大小。

• （2）按比例分配算法
  

• （3）考虑优先权的分配算法
  在实际应用中，为了照顾重要的、急迫的作业尽快完成，应为它分配较多的内存空间。

方法：

把内存中可供分配的物理块分为两部分：

• 一部分按比例分配给各进程；
• 一部分则根据各进程的优先权，适当的增加其相应份额，分配给各进程。

三、调页策略

整个过程由系统来实现，不需用户来操作！