操作系统复习，知识点总结
4.内存管理
5.设备管理
上一篇文章——>操作系统知识点总结（一）
下一篇文章——>操作系统知识点总结（三）
四、内存管理
(1)内存管理的基本概念:链接与装入，逻辑地址与物理地址空间，对换与覆盖，重定位
源程序变为可执行程序的过程:
首先是编译，由编译程序将用户源代码编译成若干目标模块;
其次是连接，由链接程序将个目标模块，以及他们所要的库函数链接在一起，形成一个完整的装入模块;
最后是装入，由装入程序将装入到内存。
程序的链接:由链接程序将目标模块和所需库函数链接在一起，形成完整的装入模块。
链接有三种方式:
- 1)静态链接:在程序运行前，将目标模块和所需的库函数，连接成一个完整的装入模块， 以后不再分开。
- 2)装入时动态链接:将得到的目标模块，再装入内存时，采用边装入边链接的链接方式。
优点:- 1)便于更新和修改，各目标模块分开存放，所以要修改和更新目标模块非常容易。
- 2)便于实现对目标模块的共享。
- 3)运行时动态链接:对某些模块的链接推迟到程序执行时才去链接。 程序的装入:由装入程序将装入模块装入到内存。优点:不仅加快了程序的装入过程，而且 可以节省大量内存空间。
装入有三种方式:
1)绝对装入方式:
2) 可重定位装入(静态重定位):特点:一个作业装入内存时，必须给他分配要求的全部内 存空间，若没有足够的内存则不能装入。此外，作业一旦装入内存，整个运行期间不能在内 存中移动，也不能申请内存空间。
3)动态运行时装入(动态重定位):特点:可将程序分配到不连续的存储区;在程序装入 前，装入它的部分代码即可运行，运行期间，根据需要动态申请分配内存;便于程序段共享， 可以向用户提供一个比存储空间大的多的地址空间。
逻辑地址与物理地址:
逻辑地址空间:编译后每个每个目标模块都从 0 号单元开始编址，这称为该目标模块的相对 地址(逻辑地址)。当连接程序将各个目标模块链接一个完整的可执行目标程序时，链接程 序顺序依次按各个模块的相对地址构成统一的从 0 号单元开始编址的逻辑地址空间。
物理地址空间:是指内存中物理单元的集合，是地址转化的最终地址。当装入程序将可执行 代码装入内存时，必须通过地址转换将逻辑地址装换为物理地址，这个过程称为地址重定位。
对换与覆盖:
对换(交换):把处于等待状态的程序从内存移到辅存，再把内存空间腾出来，这一过程称 为换出，再把准备好竞争 CPU 运行的程序从辅存移到内存，这一过程称为换入。中级调度 采用的就是对换技术。
覆盖:由于程序运行时，并非任何时候都要访问程序及数据的各个部分，因此可以把用户空 间分为一个固定区和若干个覆盖区，将经常活跃的部分放在固定区，其余部分按调用关系分 段。首先将那些即将访问的段放入覆盖区，其他段放在外存中，在需要调用前，系统将其调 入覆盖区，覆盖原有的段。
(2)连续内存分配方法，离散内存分配方法(分页、分段、段页)，
连续内存分配:是指为一个程序分配一个连续的内存空间。
分配方式主要有三种:
- 1)单一连续分配:此方式下分为系统区和用户区，低地址的系统区仅供操作系统使用。内 存中永远只有一道程序。优点:简单，无外部碎片，可采用覆盖技术，不要额外的技术支持。 缺点:只能用于单任务，单用户的操作系统，有内部碎片，存储器利用率极低。
- 2)固定分区分配:最简单的一种可运行多道程序的存储管理方式。将内存用户空间划分为 若干个固定大小的区域，在每个分区中只装入一道作业，允许几道作业并发运行。
划分分区的方法:
1)分区大小相等
2)分区大小不等
固定分区分配通常会建立一张分区使用表，每个表项包括包括每个分区的起始地址，大小， 和状态(是否已分配)，当某一用户程序要装入时，由分配程序检索该表，找到一个大小满 足且未分配的分区，分配给该程序。并置状态为已分配。 缺点:程序可能太大而放不进任何一个分区;主存利用率低，有内部碎片。 - 3)动态分区分配:不预先划分内存，而是在进程装入内存时，根据进程的大小动态的建立 分区，并使分区大小刚好适合进程需要。在开始 i 分配时很好，但在之后会导致内存中出现 许多小的内存块，随着时间推移，内存中会出现越来越多的碎片，内存利用率随之下降。这 碎片称为外部碎片，克服外部碎片可以采用紧凑技术。
在进程装入或换入时，需要确定分配哪个内存块给进程，这就是动态分区的分配策略。
1) 首次适应算法
2)最佳适应算法
3)最坏适应算法
4)临近适应算法(循环首次适应算法， 分配内存时从上次查找结束的位置开始查找) - 4)可重定位分区分配(主要看书)
离散内存分配方法:
离散内存分配:允许一个程序分散的装入不相邻的内存分区。根据分区大小是否固定分为分 页储存管理方式和分段储存管理方式。
基本分页存储管理:分页存储管理将一个进程的逻辑地址空间分成若干个大小相等的片，称 为页。相应的，把内存空间分成与页面大小相等的若干个储存块，称为物理块或页框。 页表:实现页号到物理块号的地址映射。
基本分段存储管理:引入的目主要是为了满足程序员在编程和使用上的诸多要求。
1)方便 编程
2)信息共享
3)信息保护
4)动态增长
5)动态链接
分段和分页的主要区别:
1)分页是信息的物理单位，段是信息的逻辑单位
2)页的大小固定 且由系统固定，段的长度不固定，决定于用户编写程序的长度
3)分页的作业地址空间是一 维的，程序员只用一个记忆符即可表示一个地址;分段的地址空间是二维的，程序员在表示 一个地址时，既需要给出段名又需要给出段内地址。
段页式存储管理:分段与分页管理相结合，先将用程序分为若干段，再把每个段分为若干个 页，地址结构由段号，段内页号，页内地址组成。地址变换过程:配置一个段表寄存器，其 中存放段表始址和段表长。进行地址变换时，先将段号与段表长比较，若小于段表长，表示 未越界，于是利用段表始址和段号求出该段所对应的段表项在段表中的位置，从中得到该段 的页表始址，并利用段内页号来获得对应的页表项位置，从中得出该页所在的物理块号，在 利用块号和页内地址构成物理地址。(三次访问内存!)
(3)虚拟内存分配方法(虚拟内存的概念，局部性原理，实现虚拟内存所需的硬件和软件 支持，请求分页(段)管理，页面置换算法)
虚拟存储器:指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储 器系统。
局部性原理:时间局部性:典型原因:程序中存在大量的循环操作。 空间局部性:程序在一定时间内访问的地址，可能集中在一定范围内。
实现虚拟内存所需的硬件和软件支持:
请求分页管理:
硬件支持
1)一定容量的内存和外存
2)页表机制
3)中断机构
4)地址变 换机构
软件支持
1)实现请求调页的软件
)实现页面置换的软件
请求分段管理:
硬件支持
1)一定容量的内存和外存
2)段表机制
3)中断机构
4)地址变 换机构
软件支持 1)
1)实现请求调段的软件
2)实现段置换的软件
虚拟存储器的特征:
1)多次性
2)对换性
3)虚拟性
请求分页(段)管理:
页表机制:页表除了含有页号及其对对应的物理块号以外，还有状态位:用于指示该页是否调入内存。访问字段:记录一段时间内被访问次数。修改位:表示该页在调入内存后是 否被修改过。
缺页中断机构:缺页中断是一种特殊的中断，与一般中断相比，主要区别有以下两个方面:
1)指令执行期间产生和处理中断信号
2)一条指令执行期间，可能产生多次缺页中断。
地址变换机构:请在书中重点理解、记忆基本地址变换机构（用于实现逻辑地址到物理地址转换的一组硬件机构）的原理和流程。
物理块的分配策略:
1)固定分配局部置换
2)可变分配全局置换
3)可变分配局部置换 调入页面的时机:1)预调页策略 2)请求调页策略(每次调入一页)
页面置换算法(重点掌握):
1)最佳置换算法(opt)
2)先进先出页面置换算法(FIFO)
3)最近最久未使用置换算法(LRU)
4)时钟置换算法(CLOCK)
5)改进型 clock 置换算法
(4)内存保护与共享
内存保护:保护操作系统不受用户进程的影响，同时保护用户进程不受其他用户进程的影响。 主要有两种方法:
1)在 CPU 设置一对上下限寄存器，存放用户作业在主存中的上限和下限地址，每当 CPU 访问一个地址时，分别和两个寄存器的值比较，判断有无越界。
2)采用重定位寄存器(基址寄存器)和界地址寄存器(限长寄存器)。重定位寄存器含有 最小的物理地址值，界地址寄存器含逻辑地址最大值。每个逻辑地址必须小于界地址寄存器， 内存管理机构动态的将逻辑地址与界地址寄存器进行比较，若未发生地址越界，则加上重定 位地址寄存器的值形成物理地址。(重定位寄存器用来加，界地址寄存器用来比)
内存共享:在书中了解
(5)抖动的概念和处理方法
抖动:刚刚换出的页面马上就要换入主存，刚刚换入的页面马上就要换出主存，这种频繁的 页面调度现象称为抖动或颠簸。
主要原因是:某个进程频繁访问的页面数目高于可用的物理页帧数目。
处理方法:
采取局部置换策略
仅允许进程在自身范围内进行置换。即使发生抖动，也可以把影响限制在较小范围内。
五、设备管理
(1)I/O 体系结构
整个 IO 系统可视为具有四个层次的系统结构:用户层 IO、设备独立性软件、设备驱动程序、 中断处理程序
用户层 IO:实现与用户交互的接口。
设备独立性软件:用于实现用户程序与设备驱动器的统一接口、设备命令、设备保护及设备 分配与释放等等，同时为设备管理与数据传送提供必要的存储空间。
设备驱动程序:与硬件直接相关，负责具体实现系统对设备发出的操作指令，驱动 IO 设备 工作的驱动程序。
中断处理程序:用户保存被中断进程的 CPU 环境，处理完并回复被中断程序的现场后，返 回到被中断进程。
设备控制器的基本功能:
1)接受和识别命令
2)数据交换
3)标识和报告设备状态
4)地址 识别
5)数据缓冲
6)差错控制
设备控制器的组成:
1)设备控制器与处理机接口
2)设备控制器与设备的接口
3)IO 逻辑
(2)I/O 控制方法
外围设备与内存的输入输出控制有四种
- 1)程序直接控制
优点:简单易于实现 缺点:CPU 和 IO 设备串行工作，导致 CPU 利用率相当低。 - 2)中断驱动方式:
中断驱动方式的思想是:允许 IO 设备主动打断 CPU 运行并请求服务，从而“解放”CPU，使 得其向 IO 控制器发出读命令后，可以继续做其他有用的工作。
优点:大大提高了 CPU 利用率 缺点:数据中每个字在存储器与 IO 设备控制器之间的传输 必须经过 CPU，导致了终端驱动仍然会消耗较多的 CPU 时间。 - 3)DMA 方式(直接存储器存取):
基本思想:在 IO 设备和内存之间开辟直接的数据交换通路，彻底解放 CPU。
特点:
1)基本单位数据块
2)所传送的数据，是从设备直接送入内存的，或者相反 3)仅 在传送一个或多个数据块开始或结束时，才需要 CPU 的干预，整块数据的传送是在 DMA 控制器的控制下完成的。
DMA 控制器的组成(机组要求请参考书中内容):
DMA 的工作方式:CPU 接到 DMA 的工作请求时，给 IO 控制器发一条命令，启动 DMA 控 制器，然后继续其他工作。之后 CPU 就把控制操作委托给 DMA 控制器，由该控制器负责处 理。DMA 控制器直接与存储器交互，传送整个数据块，每次传送一个字，这个过程不需要 CPU 的参与。传送完成后，DMA 控制器发送一个中断信号给 CPU。
DMA 与中断驱动方式的区别是:
1)中断驱动方式在每个数据传送需要中断 CPU，而 DMA 控制方式则是在所要求传送的一批数据全部传送结束时才中断 CPU
2)中断驱动方式数据 传送是在中断处理时由 CPU 控制完成，而 DMA 控制方式则是在 DMA 控制器的控制下完成 的。
- 4)通道控制方式:
IO 通道:是指专门负责输入输出的处理机，是 DMA 方式的发展，他可以进一步减少 CPU 的干预，即把对一个控制块的读写为单位的干预，减少为对一组数据块的读写的及有关控制 和管理为单位的干预。同时，又可以实现 CPU、通道和 IO 设备三者的并行操作，从而更有 效的提高整个系统的资源利用率。
IO 通道与一般处理机的区别:通道指令的类型单一，没有自己的内存，通道执行的通道程 序是放在主机的内存中的，也就是说通道与 CPU 共享内存。
IO 通道与 DMA 方式的差别:DMA 方式需要 CPU 来控制和传输数据块的大小以及传输的内 存位置，而通道方式中的这些信息是由通道控制的;另外，每个 DMA 控制器对应一台设备 与内存传递数据，而一个通道可以控制多台设备与内存的数据交换。
(3)I/O 分配中的数据结构和分配方法
在设备分配时，通常借助一些表格:设备控制表、控制器控制表、通道控制表、系统设备表。
设备控制表(DCT):每个设备配备一张设备控制表，用于记录本设备的情况。
控制器控制表(COCT):系统为每个控制器设置了一张用于记录本控制情况的控制器控制表。
通道控制表(CHCT):每个通道都配有一张通道控制表。
系统设备表(SDT):这是系统范围的数据结构，记录了系统中全部设备的情况。每个设备 占有一个表目，其中包括设备类型，设备标识符，设备控制表以及设备驱动程序的入口等。
设备分配时应考虑到的因素:
1)设备固有属性
2)设备分配算法
3)设备分配时的安全性
4) 设备独立性
设备的固有属性有三种
1)独占性设备
2)共享性设备
3)可虚拟设备
设备分配算法:
1)先来先服务
2)优先级高者有优先。
设备分配中的安全性:
1)安全分配方式:放弃了“请求和保持”条件，CPU 与 IO 串行工作
2) 不安全分配方式:可能造成死锁。
(4)通道和通道程序
通道:一种特殊的处理机，具有执行 IO 指令的能力，并通过执行通道程序来控制 IO 操作。
类型:
1)字节多路通道
2)数组选择通道
3)数组多路通道
字节多路通道:按字节交叉方式工作。含有许多非分配型子通道，这些子通道按时间片转轮 方式共享主通道。只要扫描各子通道速度足够快，而连接到子通道设备速率不是太高时，不 会丢失信息。(不适用于连接高速设备)
数组选择通道:可以连接多台高速设备，但只有一个分配型子通道，在一段时间内只能执行 一道通道程序。通道利用率极低。
数组多路通道:前两者优点结合。既具有很高的数据传送速率，又有令人满意的 CPU 利用 率。
瓶颈问题:通道价格昂贵，因此较少，通道不足会造成瓶颈问题。，解决方法:增加设备到 主机间的通路，而不增加通道。为了防止出现瓶颈。通常采用多通路的 IO 系统结构。
通道程序:通道是通过执行通道程序，并与设备控制器共同实现对 IO 设备的控制的。由一 系列通道指令(命令)构成。与一般机器指令不同，在他的每条指令中，都包含如下信息:
1) 操作码
2)内存地址
3)技计数
4)通道程序结束位
5)记录结束标志。
(5)设备独立性及其实现方法
为提高 OS 的可适应性和可扩展性，必须实现设备独立性(设备无关性)。基本含义:应用 程序独立于具体使用的物理设备。
好处:
1)设备分配时的灵活性
2)易于实现 IO 重定向。
实现方法:在应用程序中使用逻辑设备名来请求使用某类设备，在系统中设置一张逻辑设备 表(LUT)，用于将逻辑设备名映射成物理设备名。表的表目中包含三项:逻辑设备名，物 理设备名和设备驱动程序的入口地址。
建立逻辑设备表的两种方式:1)在整个系统中只设置一张 LUT，适用于单用户系统 2) 为每个用户设置一张 LUT。
(6)虚拟设备和 SPOOLing 技术
SPOOLing(假脱机)技术可以将一台物理 IO 设备虚拟为多台逻辑 IO 设备，允许多个用户 共享一台物理 IO 设备。实质上是一种以空间换时间的技术，而请求分页的页面调度算法时 典型的以时间换空间。
SPOOLing 是对脱机输入、输出系统的模拟。必须建立在多道程序功能的基础上，而且还要有高速随机外存的支持，通常采用磁盘存储技术。
SPOOLing 主要有三个部分:
1)输入井和输出井，在磁盘上开辟的两个大存储空间，输入井是模拟脱机输入的磁盘设备， 用于暂存 IO 设备输出得数据，输出井是模拟脱机输出的设备，用于暂存用户程序的输出数 据。
2)输入缓冲区和输出缓冲区，为缓和 CPU 和 IO 设备速度不匹配的矛盾，在内存中开辟两 个缓冲区:输入和输出缓冲区，输入缓冲区用来暂存由输入设备送来的数据，以后在传送到 输入井;输出缓冲区用于暂存从输出井送来的数据，以后在传送给输出设备。
3)输入进程和输出进程:利用这两个进程模拟脱机 IO 时的外围控制机。其中输入进程模 拟脱机输入时的外围控制机，将用户要求的数据从输入机通过输入缓冲区在送到输入井，当 CPU 需要输入数据时，直接从输入井读到内存;输出进程模拟输出时的外围控制机，把用 户要求输出的数据先从内存送到输出井，待输出设备空闲时，再将输出井中的数据经过输出 缓冲区送到输出设备上。
打印机是经常要用到的独占输出设备。利用 SPOOLing 可以改造成共多个用户共享的设备， 从而提高设备利用率。
(7)缓冲管理
引入缓冲区的主要原因:1)缓和 CPU 和 IO 设备间速度的不匹配的矛盾 2)减少对 CPU 的 中断频率，放宽 CPU 中断响应时间的限制 3)提高 CPU 和 IO 设备之间的并行性。缓冲区 数据非空时，不能往缓冲区冲入数据，只能把数据传出;当缓冲区为空时，可以冲入数据， 但必须把缓冲区充满后，才能从缓冲区把数据传出。 根据系统设置缓冲器的个数，缓冲技术可分为四种:
1)单缓冲:从磁盘把一块数据输入到缓冲区的时间为 T，操作系统将该缓冲区的数据送到 用户区的时间为 M，CPU 对这块数据的处理时间为 C，T 和 C 是可以并行的，因此可把系 统对每一块数据的处理时间表示为 max(T,C)+M。
2)双缓冲:为了加快输入输出速度，提高设备利用率，引入双缓冲也成缓冲对换。处理一 块数据所用时间为 max(C+M,T)，单缓冲机制不允许双方同时向对方发送数据，而双缓冲 可以。
3)循环缓冲:包含多个大小相等的缓冲区，每个缓冲区中由一个链接指针指向下一个缓冲 区，构成一个环形。
4)缓冲池:在池中设置多个可供进程共享的缓冲区。
组成:
1)空闲缓冲区(空缓冲队列)
2)装满输入数据的缓冲区(输入缓冲队列)
3)装 满输出数据的缓冲区(输出缓冲队列)。
(8)设备处理与 I/O 软件
IO 软件总体设计目标是高效率和通用性。
IO 软件应实现的目标:
1)与具体设备无关
2)统一命名
3)对错误的处理
4)缓冲技术
5) 设备分配和释放
6)IO 控制方式 四个层次:用户层软件、设备独立性软件、设备驱动程序、中断处理程序。
(9)设备分配
1） 设备分配中的数据结构
在进行设备分配时，通常都需要借助于一些表格的帮助，在表格中记录了相应设备或控制器的状态及对设备或控制器进行控制所需的信息，在进行设备分配时所需要的数据结构有设备控制表、控制器控制表、通道控制表和系统设备表等。
① 设备控制表（DCT），系统为每个设备都配置了一张设备控制表，用于记录本设备的情况。
说明：设备队列队首指针（凡因为请求本设备而未得到满足的进程，其PCB都应按照一定的策略排成一个队，称该队列为设备请求队列或简称设备队列，其队首指针指向队首PCB），设备状态（当设备处于使用状态时，应该设备设置为忙/闲标志置为1），与设备连接的控制器表指针（该指针指向该设备所连接的控制器的控制表），重复执行次数（由于外部设备在传送数据时，较容易发生数据传送错误，因而在许多系统中，如果发生传送错误，并不立即认为传送失败，而是令它重传，并由系统规定设备在工作中发生错误时应重复执行的次数）
② 控制器控制表（COCT)，系统为每个控制器都设置了一张用于记录本控制器情况的控制器控制表。
③ 通道控制表（CHCT），每个通道都配有一张通道控制表。
④ 系统设备表（SDT），系统范围的数据结构，记录了系统中全部设备的情况，每个设备占用一个表目，其中包括有设备类型、设备标识符、设备控制表及设备驱动程序的入口等。
