开发成长之路（22）-- 不可不知的操作系统知识（2）
文章目录
知识框图
存储器管理
－计算机系统中存储器一般分为内存储器和辅助存储器两级 －内存可以分成系统区和用户区两部分，系统区用来存储操作系统等系统软件，用户区用于分配给用户作业使用
为用户提供方便、安全和充分大的存储空间.
内存的分配和回收
当用户作业要装入内存时，需向操作系统提出申请，操作系统按一定策略分配存储空间，若某作业执行完毕，需归还内存空间时。
为避免内存中若干道程序相互干扰，尤其是为了防止用户程序侵犯系统程序所在的内存区域，必须对内存采取保护措施 ，内存储器的地址保护功能一般由硬件和软件配合实现。
为提高内存利用率，需要进行内存空间的共享，包括两方面的含义： －共享内存储器资源 －共享内存储器的某些区域
内存储器的扩充不是硬件设备上的扩充，而是用虚拟技术来实现的逻辑上的扩充，即虚拟存储概念
程序的链接和装入
静态链接方式：在程序运行以前，将各个目标模块及它们所需要的库函数，链接成一个完整的装入模块，又可称为可执行文件，通常不再拆开。
装入时动态链接：用户源程序经编译后所得的目标模块，在装入内存时，边装入边链接，即在装入一个目标模块时，如果发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存，进行链接。 优点：①便于修改和更新。②便于实现对目标模块的共享。
运行时动态链接：这种链接方式是将对某些模块的链接推迟到执行时才进行。在执行过程中，当发现一个被调用模块尚未调入内存时，立即由操作系统去找到该模块并装入内存，再把它链接到调用者模块上。
各种存储管理方式
单一连续分配：
基本思想：
内存的用户区一次只分配给一个用户程序使用
存储保护机制：
基址寄存器和界限地址寄存器
特点：
这种管理方式的分配、去配算法非常简单，内存的利用率很低分区分配：
分区分配的存储管理是为了适应多道程序设计技术而产生的最简单的管理方式固定分区：
- 基本思想
系统预先把内存中的用户区分成若干个连续的区域，每个区域称为一个“分区”。程序装入时，根据它对内存大小的需求量，系统将按照一定的策略，把能满足它要求的一个分区分配给该程序
- 分配和回收
固定分区分配表，内容包括分区号、起始地址、长度、占用标志等.分区分配算法
首次适应算法：要求空闲分区链以地址递增的次序链接，在进行内存分配时，从链首开始顺序查找，直至找到一个能满足其大小要求的空闲分区为止
循环首次适应算法：在为程序分配内存空间时，不再每次从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找。直至找到第一个能满足要求的空闲分区
最佳适应算法 ：把既能满足要求、又是最小的空闲分区分配给程序
最差适应算法：每次为程序分配内存时，总是找到一个满足程序长度要求的最大空闲分区进行分配
内存分区回收操作
当进程运行完毕释放内存时，系统根据回收区的首址，从空闲分区表（链）中找到相应的插入点，进行回收，此时可能出现以下四种情况：
－回收区与插入点的前一个分区相邻接，两分区合并
－回收区与插入点的后一个分区相邻接 ，两分区合并
－回收区同时与插入点的前、后两个分区邻接 ，三分区合并
－回收区与插入点前、后两个分区都不相邻 ，单独一个分区内存回收算法
假定进程归还的分区起始地址为S，长度为L，则： ① 归还区有下邻空闲区 如果S+L正好等于空闲区表中某个登记栏目（假定为第j栏）的起始地址，则表明归还区有一个下邻空闲区。这时只要修改第j栏登记项的内容： 起始地址=S； 第j栏长度=第j栏长度+L；
② 归还区有上邻空闲区 如果空闲区表中某个登记栏目（假定为第k栏）的“起始地址+长度”正好等于S，则表明归还区有一个上邻空闲区。这时要修改第k栏登记项的内容（起始地址不变）： 第k栏长度=第k栏长度+L；
③ 归还区既有上邻空闲区又有下邻空闲区 如果S+L正好等于空闲区表中某个登记栏目（假定为第j栏）的起始地址，同时还有某个登记栏目（假定为第k栏）的“起始地址+长度”正好等于S，这表明归还区既有一个上邻空闲区又有一个下邻空闲区。此时对空闲区表的修改如下： 第k栏长度=第k栏长度+第j栏长度+L；（第k栏起始地址不变） 第j栏状态=“空”；（将第j栏登记项删除）
④ 归还区既无上邻空闲区又无下邻空闲区 如果在检查空闲区表时，无上述三种情况出现，则表明归还区既无上邻空闲区又无下邻空闲区。这时，应该在空闲区表中查找一个状态为“空”的栏目（假定查到的是第t栏），则第t栏的内容修改如下： 第t栏起始地址=S； 第t栏长度=L； 第t栏状态=“未分配”
可变分区分配的优缺点
优点：有助于多道程序设计，提高了内存的利用率
要求硬件支持少，代价低 管理算法简单，实现容易
缺点：必须给作业分配一连续的内存区域
碎片问题严重，内存仍不能得到充分利用 不能实现对内存的扩充
分页存储管理方式
将程序的逻辑地址空间和存储空间按相同长度为单位进行等划分。把每个程序逻辑空间分成一些大小相同的片段，叫做页面或页。把内存的存储空间也分成大小与页面相同的片段，叫做物理块或页框。分配的物理块可以连续也可以不连续。
页表
页表的作用是实现从页号到物理块号的映射 系统在内存空间设置一片区域作为页表区，系统为每个进程提供一个页表。进程页表的起始地址存放在进程PCB中。
存取控制
在页表的表项中设置一存取控制字段，用于对该存储块中的内容进行保护。
地址变换
地址变换即通过地址变换机构把逻辑地址变换成相应的物理地址，实际上是将逻辑地址中的页号，转 换为内存中的物理块号。因为页表的作用就是用于实现页号到物理块号的变换，因此，地址变换任务是借助于页表来完成的 除此以外，系统设置了一个页表寄存器PTR其中存放页表在内存的始址和页表的长度
动态地址变换
逻辑地址可以分解成：页号、页内位移量（页内地址） 物理地址可以分解成：物理块号、物理块内位移（物理块内地址）
p=逻辑地址/页面大小 d=逻辑地址-p×页面大小
地址变换过程
⑴ 根据逻辑地址计算出页号p和页内地址d， p=逻辑地址/页面大小 d=逻辑地址%页面大小 ⑵ 根据页号p查页表，得到对应块号f ⑶ 块内地址和页内地址相同，计算物理地址 物理地址=f×块大小+d （块大小等于页大小）
若页面大小为2的幂，则页号和页内地址可以直接取高位和地位部分获得，物理地址可以用块号和块内地址拼接而成分页系统中的地址变换机构
快表
由于页表存储在内存中，所以当要按照给定的逻辑地址进行读/写时，需要两次访问内存: 第一次是根据页号访问页表，读出页表相应栏中的块号以便形成物理地址； 第二次是根据物理地址进行读/写操作。 这样比通常执行指令的速度慢一倍。为了提高存取速度，在地址变换机构中增设了一个具有并行查寻能力的特殊高速缓冲存储器，又称为“联想存储器”或“快表”
利用快表的地址变换机构
两级和多级页表
现代的大多数计算机系统都支持非常大的逻辑地址空间，此时，页表就变得非常大，要为它分配一大段连续的内存空间将变得十分困难
解决办法：
①采用离散分配方式来解决难以找到一块连续的内存空间问题；
②只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。分段存储管理
基本思想
每个程序的地址空间按照自身的逻辑关系划分成若干段（比如主程序段、子程序段、数据段、堆栈段等）每个段都有自己的名字，通常可用一个段号来代替段名，每个段都从0开始独立编址，段内地址连续。段的长度由相应的逻辑信息组的长度决定，因而各段的长度不等。分配内存时，为每个段分配一连续的存储空间，段间地址空间可以不连续段表
段表实现了从逻辑段到物理内存区的映射.系统为每个进程建立了一张段映射表，简称“段表”。进程的每个段在段表中占有一个表项，在其中记录了该段在内存中的起始地址（基址）和段的长度段与页的差别
基本思想 每个程序的地址空间按照自身的逻辑关系划分成若干段（比如主程序段、子程序段、数据段、堆栈段等）每个段都有自己的名字，通常可用一个段号来代替段名，每个段都从0开始独立编址，段内地址连续。段的长度由相应的逻辑信息组的长度决定，因而各段的长度不等。分配内存时，为每个段分配一连续的存储空间，段间地址空间可以不连续 段表 段表实现了从逻辑段到物理内存区的映射.系统为每个进程建立了一张段映射表，简称“段表”。进程的每个段在段表中占有一个表项，在其中记录了该段在内存中的起始地址（基址）和段的长度
段页式
内存分成大小相同的块，每个程序地址空间按照逻辑关系分成若干段，并为每个段赋予一个段名，每段可以独立从0编址，每段按内存块大小分成页，每段分配与其页数相同的内存块，内存块可以连续也可以不连续。系统为每段建立页表记录每页对应的块，同时还为该程序建立段表记录每段对应的页表
地址变换
为了实现地址变换，配置一段表寄存器，在该寄存器中存放段表的始址和段长
在段页式存储管理方式中，执行一条指令需要三次访问内存。第一次访问段表，从中得到页表的位置，第二次访问页表，得出该页所对应的物理块号，第三次按照得到的物理地址访问内存 －为了提高地址变换速度，同样可以和分页存储管理方式和分段存储管理方式一样，设置一高速缓寄存器，利用段号和页号去检索该寄存器，得到相应的物理块号
分页虚拟存储管理方式
分页虚拟存储管理
基本原理
分页虚拟存储管理方式是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的虚拟存储器系统。 在分页虚拟存储管理时使用的页表，是在原来页表的基础上发展起来的，包括以下内容：物理块号、状态位、访问位、修改位、外存地址 。
缺页中断
每当要访问的页面不在内存时，便产生一缺页中断，请求操作系统把所缺页面调入内存。，请求操作系统把所缺页面调入内存。缺页中断作为中断，它同样需要经历诸如保护CPU现场环境、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU环境等几个步骤。
缺页中断与与一般的中断的区别
－在指令执行期间产生和处理中断信号。 －一条指令在执行期间，可能产生多次缺页中断。
地址变换
在分页存储管理方式中的地址变换机构的基础上，增加了产生和处理缺页中断，以及从内存中换出一页等功能。具体过程：
- 保存当前进程的CPU现场环境，从辅存中找到该页；
- 查看当前内存是否有空闲空间调入该页，如果有则启动I/O，将该页由辅存调入内存，同时修改页表，再按分页存储管理方式的地址变换过程转换地址；如果内存已满，则按照某种算法选择一页作为淘汰页调出，腾出空间后再调入。当然如果被淘汰的页在内存中已经被修改过，则需将该页写回辅存。
页面置换算法
如果内存空间己被装满而又要装入新页时，必须按某种算法将内存中的一些页淘汰出去，以便调入新页，这个工作称为“页面置换”。选择被淘汰页的方法成为页面置换算法。
下面都看这张图，并思考如何实现
最佳置换算法
－算法：淘汰那些以后永不使用，或者是在最长时间内不再被访问的页 －无法实现的，只能作为其它置换算法的衡量标准
先进先出算法
－算法：每次淘汰最先进入内存的页 －优点：简单，易于实现 －缺点：效率不高，可能产生“抖动”现象
先进先出算法
－算法：每次淘汰最先进入内存的页 －优点：简单，易于实现 －缺点：效率不高，可能产生“抖动”现象
最近最久未使用（LRU）算法
－算法：淘汰那些在最近一段时间里最久未被使用的一页 － LRU算法是较好的一个算法，但是开销太大，要求系统有较多的支持硬件(移位寄存器或栈）
改进型Clock置换算法
－算法：除了考虑到页面的使用情况外，还增加了置换代价，选择换出页面时，既要是未使用过的页面，又要是未被修改过的页面把同时满足两条件的页面作为首选被淘汰的页。 －该算法与简单Clock算法比较，可减少磁盘的I/O操作次数 ，但实现该算法本身的开销将有所增加
分页虚拟存储器
内存分配策略和分配算法
最小物理块数
- 最小物理块数是指能保证进程正常运行所需的最少物理块数。
- 进程所需的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。
物理块的分配策略
固定分配局部置换
- 基于进程的类型或根据程序员的建议，为每个进程分配一定数量的物理块，在整个运行期间都不再改变。
- 如果进程在运行期间发现缺页，则只能在该进程在内存的n个页面中选出一页换出，然后在调入一页，保证分配给该进程的物理块数保持不变。
- 困难：难以确定为每个进程分配的物理块数，若太少，则会频繁地出现缺页中断，降低了系统的吞吐量；若太多，则必然使内存中驻留的进程数目减少，进而可能造成CPU空间或其它资源的浪费，而且在实现进程交换时，会花费更多的时间。
可变分配全局置换
- 先为系统中的每个进程分配一定数量的物理块，而操作系统本身也保留一个空闲物理块队列。
- 当某个进程发现缺页时，由系统从空闲物理块队列中，取出一个物理块分配给该进程，并将欲调入的（缺）页装入其中。仅当空闲物理块队列中的物理块用完时，操作系统才从内存中选择一页调出，该页可能是系统中任一进程的页，
- 会使被淘汰页的那个进程的物理块数减少，进而使其缺页率增加。
- 最容易实现的一种物理块分配和置换策略。
可变分配局部置换
- 进程的类型或根据程序员的要求，为每个进程分配一定数目的物理块；但当某进程发生缺页时，只允许从该进程在内存的页面中选出一页换出。
- 如果进程在运行中频繁地发生缺页中断，则系统须再为该进程分配若干附加的物理块，直至进程的缺页率减低到适当程度为止；反之，若一个进程在运行过程中的缺页率特别低，则此时可适当减少分配给该进程的物理块，但不应引起其缺页率的明显增加。
调页策略
请求调页策略
- 当缺页中断发生时进行调度，即当访问某一页面而该页面不在内存时由操作系统将其调入内存。 预调页策略
- 也称先行调度，是当缺页中断发生前进行调度，即当一个页面即将被访问之前就将其调入内存。
- 预调页可以节省进程因缺页中断而等待页面调入的时间。
抖动问题
－进程的大部分时间，都用于页面的换进换出，而几乎不能再去做任何有效的工作，从而导致发生处理机利用率急剧下降，而趋于零的现象，我们称此时系统处于抖动状态。 －产生抖动的原因 产生抖动的根本原因是，系统中进程的数量太多，因此分配给每个进程的物理块数量太少，使得每个进程在运行时频繁的发生缺页中断 －工作集 所谓工作集就是指在某段时间间隔∆内，进程访问页面的集合。为了使进程有较低的缺页率，应在该段时间内把进程的全部工作集装入内存中
预防抖动的方法
采用局部置换策略
利用工作集算法防止抖动
利用“L=S”准则调节缺页率
挂起某些进程 分段虚拟存储管理
基本原理
－分段虚拟存储管理原理同分页虚拟存储管理原理一样，在程序运行前，不必调入所有分段，只需先调入若干个分段便可启动运行。当所访问的段不在内存中时，可请求操作系统将所缺的段调入内存 －分段虚拟存储管理中的段表包括：段名、段长、段的基址、存取方式、访问位、修改位、存在位、增补位和外存地址
缺段中断
－在分段虚拟存储管理系统中，如果访问的段不在内存中，系统将产生一个缺段中断，请求操作系统将该段调入到内存 －缺段中断和缺页中断一样 ，但段是信息的逻辑单位，所以不可能出现一条指令和一组信息被分割在两个段里的情况
概念复习
附赠： 《数据结构和算法常见面试题大全》
腾讯云开发者
