OS- -请求分页系统、请求分段系统和请求段页式系统(二)
文章目录
OS- -请求分页系统、请求分段系统和请求段页式系统(二)
一、基本分段存储管理方式
1.分段系统的组成:
2.段表
3.查找过程
4.分段和分页的对比
二、段页式内存管理方式
1.分页, 分段管理的优缺点分析
2.段页式管理的结构
3.段表, 页表
4.查找过程
三、虚拟内存
四、请求分页管理方式
1.页表机制
2.缺页中断机构
3.页面置换算法
四、页面分配策略
1.驻留集
2.几种分配策略
3.何时调入页面
4.何处调入页面
5.抖动(颠簸)现象
6.工作集

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

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

1.分段系统的组成:

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


2.段表

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


关于段表 :



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


3.查找过程

4.分段和分页的对比

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


分段比分页更容易实现信息的共享和保护

二、段页式内存管理方式
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.工作集


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

OS- -请求分页系统、请求分段系统和请求段页式系统(一)
文章目录
OS- -请求分页系统、请求分段系统和请求段页式系统(一)
一、内存管理的概念
二、内存空间的扩充
覆盖与交换
三、内存空间的分配和回收
连续分配管理方式
非连续分配管理方式
四、基本分页存储管理
1.页框和页面
2.地址转换的实现
页号和页内偏移量
页表
基本地址变换机构
具有快表的地址变换机构
两级页表



进程应该放在内存的哪里?


操作系统如何记录哪些内存区域已经被分配了, 哪些还空闲?


当进程运行结束之后, 如何将进程占用的内存空间释放?


一、内存管理的概念

 操作系统负责内存空间的分配与回收
 操作系统需要提供某种技术从逻辑上对内存空间进行扩充
 操作系统需要实现地址转换功能, 负责程序的逻辑地址和物理地址的转换
 操作系统需要提供内存保护功能, 保证各进程在各自存储空间内运行, 互不干扰

实现内存保护的两种方法:

在CPU设置一对上, 下限寄存器, 存放进程的上, 下限地址. 进程的指令要访问某个地址时, CPU检查是否越界
采用重定位寄存器(又叫基地址寄存器) 和界地址寄存器(又叫限长寄存器) 进行越界检查. 重定位寄存器中存放的是进程的起始物理地址, 界地址寄存器中存放的是进程的最大逻辑地址.

二、内存空间的扩充
覆盖与交换

覆盖, 交换, 虚拟存储技术常用于实现内存空间的扩充

😊覆盖技术的思想 : 将程序分为多个段, 常用的段常驻内存, 不常用的段在需要的时候调入内存


内存中分为一个"固定区" 和若干个"覆盖区", 常用的段放在固定区, 不常用的段放在覆盖区


缺点 : 必须由程序员声明覆盖结构, 对用户不透明, 增加了用户的编程负担, 覆盖技术只用于早期的操作系统中.




 😊交换技术的思想 : 内存空间紧张时, 系统将内存中某些进程暂时换出外存, 把外存中某些已具备运行条件的进程换入内存(即进程在内存与磁盘间动态调度)



三、内存空间的分配和回收
连续分配管理方式


 单一连续分配


在单一连续分配的方式中, 内存被分为系统区和用户区, 系统区用于存放操作系统的相关数据, 用户区用于存放用户进程的相关数据,内存中只能有一道用户程序, 用户程序独占整个用户区空间.


优点 : 实现简单, 无外部碎片; 可以采用覆盖技术扩充内存; 不一定需要采取内存保护


缺点 : 只能用于单用户, 单任务的操作系统中; 有内部碎片; 存储器利用率极低





内部碎片 : 分配给某进程的内存区域有一部分没有用上, 即存在" 内部碎片 ".


外部碎片 : 内存中的某些空闲分区由于太小而难以利用






 固定分区分配


在产生了支持多道程序的系统后, 为了能在内存中装入多道程序而互相之间不产生干扰,将整个用户区划分为若干个固定大小的分区(分区大小可以相等也可以不相等),在每个分区中只能装入一道作业,形成了最早的可运行多道程序的内存管理方式.




操作系统建立一个数据结构----分区说明表, 来实现各个分区的分配和回收, 每个表对应一个分区, 通常按分区大小排列. 每个表项包括对应分区的大小, 起始地址, 状态


优点 : 实现简单, 无外部碎片;


缺点 : 有内部碎片; 存储器利用率不高;


 动态分区分配


动态分区分配又称为可变分区分配, 这种分配方式不会预先划分内存分区. 而是在进程装入内存时根据进程大小动态地建立分区, 并使得分区的大小正好适合进程的需要.


几个问题 :


系统用什么数据结构记录内存的使用情况?
当多个空闲分区都满足需求应该选择哪个分区进行分配?
如何进行分区的分配和回收操作?


四种动态分配的算法：

首次适应算法：每次都从低地址开始查找, 找到第一个能满足大小的空闲分区



实现 : 把空闲分区按地址递增的次序排列.


每次分配内存时顺序地查找空闲分区链, 找到大小能满足要求的第一个空闲分区.



最佳适应算法 ：优先使用小的空闲分区



实现 : 空闲分区按容量递增次序链接.


每次分配内存时顺序查找空闲分区链, 找到大小能满足要求的第一个空闲分区


缺点 : 每次都选择最小的分区进行分配, 会留下越来越多的容量很小难以利用的内存块, 即产生很多的外部碎片



最坏适应算法 ：优先使用大的空闲分区



实现 : 空闲分区按容量递减次序链接


缺点 : 每次都选用最大的分区进行分配, 当较大的连续空闲区被小号之后, 如果有大进程到来则没有内存分区可以利用



邻近适应算法 ：在首次适应算法的基础上, 每次都从上次查找结束的位置开始查找空闲分区链(表), 找到大小能满足的第一个空闲分区


缺点 : 邻近适应算法导致无论低地址还是高地址的空闲分区都有相同的概率被使用, 也就导致了高地址部分的大分区更可能被使用划分为小分区, 最后导致没有大分区可用

非连续分配管理方式

 基本分页存储管理
 基本分段存储管理
 段页存储管理

四、基本分页存储管理
1.页框和页面

思想 : 把内存分为一个个相等的小分区, 再按照分区大小把进程拆分成一个个小部分.


注意区分页框和页面的概念, 页框是针对内存的, 页面是针对进程的


2.地址转换的实现

特点 : 页面离散存放, 但是页面内部连续存放
访问逻辑地址A :



确定逻辑地址A的 " 页号 " P
找到P号页面在内存中的起始地址 ( 需要查找页表 )
确定逻辑地址A的 " 页内偏移 " W
逻辑地址 Ａ的物理地址 = P号页面在内存中的起始地址 + 页内偏移量W


页号和页内偏移量


为了方便计算页号和页内偏移量, 页面大小一般设置为2的整数幂?？？？



厉害了我的哥



页表


tips : 页表中的页号是"隐含"的, 可以不占用存储空间

e.g:



假设某系统物理内存大小为 4GB， 页面大小为 4KB， 则 每个页表项至少应该为多少字节？


内存块大小=页面大小=4KB= 212B


4GB 的内存总共会被分为232212=220个内存块


内存块号的范围应该是 0 ~ 220−1


内存块号至少要用 20 bit 来表示


至少要用3B来表示块号(3*8=24bit)


(但是, 为了方便页表的查询, 常常会让一个页表项占更多的字节, 使得每个页面恰好可以装得下整数个页表项)


如何理解 “页号是隐含的” :



基本地址变换机构



 步骤总结 :


根据逻辑地址计算出页号和页内偏移量


判断页号是否越界


查询页表, 找到页号对应的页表项, 确定页面存放的内存块号


用内存块号和页内偏移量得到物理地址 ( 页表长度*物理块号 + 页内偏移 = 物理地址 ( 计算机直接采用拼接物理块号和页内偏移的方式得到物理地址 ) )


访问目标单元


😊( 一共需要访问两次内存 : 第一次用来查页表, 第二次用于访问目标内存单元 )
具有快表的地址变换机构


 局部性原理


时间局部性





如果执行了程序中的某条指令, 那么不久之后这条指令很有可能再次执行; 如果某个数据被访问过, 不久之后该数据很可能再次被访问


( 程序中存在大量的循环 )




空间局部性



一旦程序访问了某个存储单元, 在不久之后, 其附近的存储单元也很有可能被访问到

( 很多数据在内存中连续存放 )


 快表(TLB)
快表又成为联想寄存器(TLB), 是一种访问速度比内存快很多的高速缓冲存储器, 用来存放当前访问的若干页表项, 以加速地址变换的过程. 与此对应的, 内存中的页表常称为慢表.




步骤总结 :


快表与基本地址变换机构的比较 :




tips : TLB 和 普通 Cache 的区别——TLB 中只有页表项的副本， 而普通 Cache 中可能会有其他各种数据的副本

两级页表

单级页表存在的问题 :

1.由于页号隐式表示, 所以要根据页号查询页表需要 :


K 号页对应的页表项存放位置 = 页表始址 + K * 4
要在所有的页表项都连续存放的基础上才能用这种方法找到页表项


2.同时, 由局部性原理可知, 很多时候, 进程在一段时间内只需要访问某几个页面就可以正常运行了, 因此没有必要让整个页表都常驻内存




解决 : 把页表再分页并离散存储， 然后再建立一张页表记录页表各个部分的存放位置， 称为页目录表， 或称外层页表， 或称顶层页表.







关于页表常驻内存的解决 – ( 虚拟存储技术 ) , 在页表项中增加一个标志位, 用于表示该页面是否已经调入内存




 注意:


如果采用多级页表机制, 各级页表不能超过一个页面


两级页表的访存次数分析 :





n级页表访存次数为n+1次: ( 以2级页表为例 )


访问内存中的页目录表 ( 顶级页表 )


访问内存中的二级页表 访问目标内存单元

请求分页系统建立在基本分页系统基础之上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页是目前最常用的一种实现虚拟存储器的方法。

在请求分页系统中，只要求将当前需要的一部分页面装入内存，便可以启动作业运行。在作业执行过程中，当所要访问的页面不在内存时，再通过调页功能将其调入，同时还可以通过置换功能将暂时不用的页面换出到外存上，以便腾出内存空间。

为了实现请求分页，系统必须提供一定的硬件支持。除了需要一定容量的内存及外存的计算机系统，还需要有页表机制、缺页中断机构和地址变换机构。

页表机制
请求分页系统的页表机制不同于基本分页系统，请求分页系统在一个作业运行之前不要求全部一次性调入内存，因此在作业的运行过程中，必然会出现要访问的页面不在内存的情况，如何发现和处理这种情况是请求分页系统必须解决的两个基本问题。为此，在请求页表项中增加了四个字段，如图3-24所示。




图3-24  请求分页系统中的页表项

增加的四个字段说明如下：
状态位P：用于指示该页是否已调入内存，供程序访问时参考。
访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近己有多长时间未被访问，供置换算法换出页面时参考。
修改位M：标识该页在调入内存后是否被修改过。
外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考。

缺页中断机构
在请求分页系统中，每当所要访问的页面不在内存时，便产生一个缺页中断，请求操作系统将所缺的页调入内存。此时应将缺页的进程阻塞（调页完成唤醒)，如果内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改页表中相应页表项，若此时内存中没有空闲块，则要淘汰某页（若被淘汰页在内存期间被修改过，则要将其写回外存)。

缺页中断作为中断同样要经历，诸如保护CPU环境、分析中断原因、转入缺页中断处理程序、恢复CPU环境等几个步骤。但与一般的中断相比，它有以下两个明显的区别：
在指令执行期间产生和处理中断信号，而非一条指令执行完后，属于内部中断。
一条指令在执行期间，可能产生多次缺页中断。

地址变换机构
请求分页系统中的地址变换机构，是在分页系统地址变换机构的基础上，为实现虚拟内存，又增加了某些功能而形成的。




图3-25请求分页中的地址变换过程

如图3-25所示，在进行地址变换时，先检索快表：
若找到要访问的页，便修改页表项中的访问位（写指令则还须重置修改位)，然后利用页表项中给出的物理块号和页内地址形成物理地址。
若未找到该页的页表项，应到内存中去查找页表，再对比页表项中的状态位P，看该页是否已调入内存，未调入则产生缺页中断，请求从外存把该页调入内存

回顾几种分配策略：

固定分区分配
动态分区分配
伙伴系统
可重定位分区分配

页面置换策略：

全局置换
局部置换

其中，关于分区分配策略已经很熟悉了，需要特别说明的是页面置换策略。这是我们在课本上不太强调的。
局部置换只置换本进程内的物理页面。一个进程占用的物理页面总数是限定的，当需要置换时，即总数已经用完，新进来一个页面，本进程就需要出去一个老的页面。所谓，朋友圈就那么大，有人进来自然需要有人出去。但是需要注意的是，如果分配给你的总数还没用完，自然是不用置换的，那是最初的红利时期，竞争还不激烈，先到先得。
全局置换指的是进程缺页时，可能置换的是内存中所有可换出的物理页面。即要换进的是A进程的页面，出去的可以是B进程的页面，因此分配给进程的页面总数是动态变化的。
这两种总的置换策略下有各自的方法：


局部置换：

最优算法
先进先出算法(有Belady异常)
Least Recently Used(最近最久未使用算法)
时钟算法
最不常用算法(Least Frequently Used)算法



全局置换：

工作集算法
缺页率算法



(2015.30) 请求分页系统中，页面分配策略和页面置换策略不能组合使用的是：$C$

A. 可变分配，全局置换

B. 可变分配，局部置换

C. 固定分配，全局置换

D. 固定分配，局部置换

分析

固定分配：将内存用户空间划分为多个固定大小的区域，在每个分区中只装入一个作业。

划分分区的方法有两种：

分区大小相等
分区大小不等

内存分配方法：按照分区大小建立分区使用表。记录每个分区的起始地址，大小和状态。
因此，固定分配不可能实现跨越进程的页面分配，个人自扫门前雪类型。
动态分区分配：根据进程的实际需要，动态地为之分配内存空间。

这句话不可以简单跳过，根据的是进程的需要，进程是动态的，是一次静态程序的执行过程。
为了实现这个，需要建立空闲分区表和空闲分区链。空闲分区表自然也是记录分区区号，分区起始地址和大小等。分区可以是离散的，因此需要链表来维护分区之间的关系。
分配内存：根据某种分配算法(首次适应，循环首次适应，最佳适应，最坏适应，快速适应等)，从空闲分区链中找到需要的分区，根据一个算式：

m.size−u.size≤sizem.size−u.size≤size,其中m.size是每个空闲分区的大小，u.size是请求的分区大小，size是规定的不可再切割的剩余分区的大小。即，如果分配完以后，剩余部分小于size这条线了，那么就把整个分区给你，否则，你只能拿到你所需要的。也即是超过一定量的交易额是大客户，待遇要好于小客户。
从这个过程中我们可以看到，空闲分区没有属于哪个进程的概念，即大家是吃大锅饭的。则在实现分页系统时，可以实现全局分配。局部分配是基础配置，自然不必多说。
因此，C项是无法组合在一起使用的。
转载自：https://blog.csdn.net/u011240016/article/details/53128209