操作系统期末复习简记（更新中~）-Toy模板网

这篇具有很好参考价值的文章主要介绍了操作系统期末复习简记（更新中~）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

文件

文件的逻辑结构

文件的目录结构

文件系统的层次结构

目录实现

文件的分配（在磁盘上）

文件空闲空间管理

文件共享

1、绕弯路文件共享方

2、索引节点共享

3、符号链

I/O设备

基本概念

I/O设备分类

IO设备的构成

IO控制器主要作用

IO控制器的组成

对IO设备的控制方式

1、程序直接控制方式

2、中断驱动方式

3、DMA方式

4、通道控制方式

IO软件层次结构

SPOOLing技术

设备管理中的数据结构

静态分配与动态分配

设备分配时应该考虑的因素

设备分配步骤

缓冲区管理

补充磁盘的结构

寻道时间

延迟时间

传输时间

磁盘调度算法

先来先服务调度算法

最短寻找时间优先算法

编辑

扫描算法

编辑

Look调度算法

循环扫描算法（C-SCAN）

C-LOOK调度算法

内存管理

进程运行的基本原理

链接的类型

装入的类型

逻辑地址与物理地址

内存保护

覆盖与交换

内存管理方式-连续分配管理方式

内存管理-非连续分配

基本分段存储管理

虚拟内存

请求分页管理-页表

请求分页管理-缺页中断机构

请求分页管理-地址变换机构

页面置换算法

页面分配策略

何时调入页面

何地调入页面

进程管理

什么是进程

进程的结构

进程的特征

线程是什么

线程的分类

进程的状态

进程控制

处理机调度的层次

处理机调度方式

处理机调度过程（上下文切换）

进程调度指标

进程调度算法

先来先服务

短作业优先

高响应比优先调度

优先级调度

时间片轮转调度

多级反馈队列调度

进程通信

共享存储

消息传递

管道通信

进程同步与互斥

实现同步互斥的高级方法-信号量机制

经典同步问题

单生产者消费者

多生产者多消费者问题

哲学家进餐问题

读者写者问题

管程

死锁

死锁的避免-银行家算法

死锁的检测与解除

补充实时调度算法-EDF和LLF

操作系统引论

什么是操作系统

单道批处理系统

多道批处理系统

分时系统

实时系统

文件

定义：文件是以计算机硬盘为载体的存储在计算机上的信息集合（宽泛的）

属性：描述文件状态的信息，eg.名称，修改时间等等

基本操作：创建、打开、修改文件

文件的逻辑结构

1、无结构文件（流式文件）

以字节为单位

没有具体结构

使用穷举的方式搜索

eg.我们常用的txt文件，图片都是流式文件

2、有结构文件（记录式文件）

顺序文件

索引文件

索引顺序文件

直接文件或散列文件（hash file）

文件的目录结构

1、文件控制块

基本信息

存取基本信息（权限）

使用信息

实际上我们在window系统中打开一个目录时，如下图所示，展现的就是各个文件控制块的信息

2、索引结点

如上图所示，索引结点是根据文件名创建的结点，可以方便我们对文件进行检索

3、目录结构

目录结构实际上类似数据结构中的树形结构

对于公用文件，其中实现的原理是：各个用户对该目录建立一个连接用于访问

文件系统的层次结构

如上图所示，从上到下各个层次的作用分别为：用户对文件进行打开、读写、删除等操作，文件系统对用户操作的文件进行打开（可以理解为获取到该文件的索引结点），检验文件权限，将文件的逻辑地址转换为物理地址，最后到物理地址读取到文件

目录实现

首先需要明确的是目录实际上也可以被看作为一个文件，并且是一个包含多个FCB的文件，因此对目录的实现即对这些FCB存储结构的实现

线性列表

哈希表

文件的分配（在磁盘上）

首先需要知道的是磁盘的最小单位是 扇区/磁盘块

1、连续分配

即将文件存储在磁盘上的空间分布是连续，这样分配的优点是方便顺序和直接访问速度快，但是如果我们想要在原先文件中新增内容的话则需要在原先磁盘位置的后面新增块进行存储，此时可能需要的块已经被占用了，这时操作起来就比较麻烦了

2、链接分配

隐式链接：将磁盘块之间的指针存储在块中

优点是支持顺序访问，方便扩展，不会产生碎片

缺点是不支持直接访问即不能像顺序分配那样可以直接计算得到所有块，效率较低，同时块与块之间的链接较为容易丢失

显式链接

与隐式链接不同的是，显式链接将指针从盘块中拿了出来，以一个表的形式进行存储

此外，我们可以将该文件分配表在一开始就将其加载到内存当中，因此该种显式分配方式的效率较高，且支持顺序访问，无外部碎片，方便扩展

3、索引分配

所谓的索引分配即在盘块中使用一个盘块用于存储索引表，其中索引表存放的就是当前文件的所有物理块号，其中值得一提的是为了提高效率，我们通常会建立多级索引或链接索引块或在多级索引的基础上结合快表的思想

文件空闲空间管理

首先需要知道磁盘的一些结构知识，通常来说，磁盘我们可以将其分为一个一个的卷，其中每一个卷又可以看作一个磁盘，而磁盘中存放的区域我们可以划分为目录区域文件区

1、空闲表与空闲链表

如上图所示，磁盘中灰色的盘块代表空闲盘块，其中空闲表中每一行存放一个空闲区域的第一个空闲块号以及该区域的空闲块数即可

相对地，表的结构也可以使用链表进行实现

但是整体而言，它们的效率都不高，特别是面对大文件时，我们如果顺序访问的话，那么访问的次数会太多，导致效率低下

成组链接法

如上图所示，我们将所有的空闲块分为每100个为一组，其中我们将每一组作为一个栈的结构进行存储，每一组的栈底元素会存放下一组的所有信息，分配时我们按照后进先分配，回收时进行进栈即可

需要注意的是，对于盘块的回收中，在回收到一组满了的时候，我们会新建一组同时将新组的指针指向下一组的栈顶

位示图法

如上图所示，我们将每一个磁盘都使用一个二维矩阵进行标志，其中矩阵中的每一个元素代表磁盘中的一个块，其中元素的值为1代表已经被分配了，为0代表未分配，具体盘块号与矩阵的行与列的计算关系见上图

文件共享

1、绕弯路文件共享方

类似linus中的目录命令

2、索引节点共享

3、符号链

I/O设备

基本概念

I/O就是输入输出，将数据输入到计算机，或接收计算机的数据输出到外部设备

I/O设备分类

按信息交换的单位分类

块设备：信息的存取以数据块为单位，如磁盘

字符设备：无结构的数据I/O，如键盘.1、打印机

按设备的外部特征分类

存储设备：存储信息的设备，如磁盘、磁带

输入设备：外部向计算机输送数据，如键盘

输出设备：计算机向外部输送数据，如打印机

按传输速率分类

低速设备：1kByte/s以下，如键盘、鼠标

中速设备：1k-100kB/s，如打印机

高速设备：100Kb/s以上，磁盘机

按设备的共享属性分类

独占设备：一段时间只允许一个用户使用

共享设备：可同时（并发）允许多个用户使用

虚拟设备：采用虚拟技术将一物理设备变换为多个逻辑设备

IO设备的构成

机械部件：比如键盘鼠标的按键，用于执行具体的IO操作

电子部件（可以简单理解为驱动）：即IO控制器、设备控制器，是CPU与硬件设备之间的桥梁

IO控制器主要作用

接收并识别CPU命令

向CPU报告设备状态

数据交换

地址识别

IO控制器的组成

CPU与控制器之间的接口

IO逻辑

控制器与设备之间的接口

上图需要注意的是如果右边对应有多个设备接口，那么每个设备在左边都会有自己的数据寄存器、控制寄存器和状态寄存器

对IO设备的控制方式

1、程序直接控制方式

如上图所示，CPU向IO控制器发出指令后，IO逻辑会向状态寄存器中添加一个状态表示当前自己在忙，我们知道CPU相对IO设备来说是非常快的，因此CPU在发出自己的指令后会一直访问状态寄存器，直到CPU通过状态寄存器知道了IO操作以及完成，而IO控制器之后便是通过接口得到CPU想要的东西后则将其存放到数据寄存器中后再修改自己的状态寄存器的值

在上述过程中

可以看出该种方式的优缺点：

实现简单，但是CPU与IO设备串行了，导致CPU处于盲等状态（即频繁访问状态寄存器等待IO操作完成）

2、中断驱动方式

与上面一种方式类似，不过这种方式CPU在发出指令后会收到来自IO控制器的一个中断信号，即告诉CPU可以先去干别的事，那么此时CPU就会将当前IO进程阻塞了，等到IO操作完成，IO控制器又会再次向CPU发送一个中断指令告诉CPU IO操作已经完成，让CPU回来

上述过程很好地改善了前面一种方式的缺点，即让CPU不再轮询IO控制器，但是由于每次的读写操作大小为一个字，而大部分时候我们需要操作的大小肯定大于一个字，那么CPU就会频繁中断IO进程，这样会影响效率

3、DMA方式

首先前面两种方式我们知道有两个共同的缺点，第一个是每次IO操作只能传输一个字的大小，第二个是每次IO操作都要经过CPU的寄存器再运输到内存

DMA方式就很好地解决了上述问题

DMA方式每次传输的单位不在是字而是块了，IO控制器在DR（数据寄存器）中存储需要运输的数据，其中需要注意的是，如果需要运输的数据在设备中的存储是连续存储的，那么我们是可以连续读取多个块到DR的，但是如果不是连续存储则需要重新中断读取

其中DC会对当前所运输到DR的字节数进行计数，如果已经满了，那么IO控制器会告诉CPU IO操作已经完成，这个时候CPU就可以从DR中直接将数据读到内存中了

4、通道控制方式

该种方式解决了上面所有方式出现的缺点

它的实现是我们直接在硬件上新增一个专用于IO操作的处理机，即类似GPU专门用于渲染图片视频，这个处理机我们称为通道，且它同时也是IO控制器，CPU向其发送指令后，通道会到内存中读取自己需要的程序命令，然后去底层硬件将需要的资源得到后直接写入内存，最后会发送中断信号给CPU告诉它IO操作已经完成

IO软件层次结构

用户层软件

实现用户交互接口

通过库函数实现系统调用

设备独立性软件

向上一层提供调用接口

设备保护

容错处理

设备分配与回收

数据缓冲区管理

逻辑设备与物理设备映射

设备驱动程序
不同设备硬件特性不同，但是CPU指令相同，负责控制硬件设备，将CPU指令转成设备操作驱动程序会以独立进程存在

中断处理程序
IO完成后会发出中断信号，执行中断处理程序，会直接操作硬件

SPOOLing技术

该技术是为缓和CPU的高速性与I/O设备低速性之间的矛盾而引入的

由系统中的两个专门负责I/O的进程，模拟I/O外围机的功能，实现（假）脱机输入/输出

在磁盘上开辟出两个存储区域

输入井模拟脱机输入时的磁盘，用于收容I/O设备输入的数据

输出井模拟脱机输出时的磁盘，用于收容用户程序的输出数据。

在内存中开辟的两个缓冲区

输入缓冲区用于暂存由输入设备送来的数据，以后再传送到输入井。

输出缓冲区用于暂存从输出井送来的数据，以后再传送到输出设备。

输入进程模拟脱机输入时的外围控制机，将用户要求的数据从输入机通过输入缓冲区再送到输入井。当CPU需要输入数据时，直接将数据从输入井读入内存输出进程模拟脱机输出时的外围控制机，把用户要求输出的数据先从内存送到输出并，待输出设备空闲时，再将输出井中的数据经过输出缓冲区送到输出设备

共享打印机是使用 SPOOLing 技术的一个实例

当用户进程请求打印输出时，SPOOLing 系统并不真正立即把打印机分配给该用户进程，而只为它做两件事：

由输出进程在输出井中为之申请一个空闲磁盘块区，并将要打印的数据送入其中。

输出进程再为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入其中，再将该表挂到请求打印队列上。

设备管理中的数据结构

具体数据结构如上图所示，简单了解即可，其中各个表中的队列指的是进程等待队列

静态分配与动态分配

在设备分配中，静态分配指的是在进程运行前分配所有资源，而动态分配指的是在运行中动态申请资源，一般我们采用动态分配

设备分配时应该考虑的因素

设备分配步骤

根据物理设备名查找SDT

查DCT中当前设备状态，尝试分配给进程，如果状态忙，则将进程的PCB加入等待队列

查COCT，尝试分配给进程，步骤同上

查CHCT，尝试分配给进程，步骤同上

上述步骤反过来则是设备的回收

缓冲区管理

为了缓解CPU与IO设备之间速度不匹配的矛盾而建立的临时存储区域

其中我们有单缓冲区、双缓冲区、循环缓冲区、缓冲池，其中每个缓冲区的大小一般为一个块的大小，且缓冲区的原则是非空不写，非满不读

对于缓冲池而言，我们将系统中所有的缓冲区都放在其中，且将它们分为三类缓冲区，分别为空缓冲队列，输入缓冲队列，输出缓冲队列

补充磁盘的结构

如上图所示，就是一个磁盘在拆开之后的结构了，磁盘的表面由一些磁性物质组成，用这些物质来存储二进制数据

如上图所示就是一个磁盘的盘面，每一个圈就是一个磁道，一个磁道又被划分为一个一个的扇区（就是前面说的磁盘块），每个扇区的存储大小是相同的，但内圈扇区面积小因此密度大

如果想要读取扇区中的内容的话，需要移动磁头臂带动磁头，然后找到想要的磁道，磁盘转动即可

可用（柱面号，盘面号，扇区号）定位任意一个磁盘块

寻道时间

即在读写数据之前，磁头移动到指定磁道所需时间

寻道时间=启动磁头时间+需跨越磁道数*跨越一个磁道所需时间

延迟时间

即通过旋转磁盘使得磁头定位到目标扇区所需时间，定义磁盘转速为r

那么磁盘转一圈所需时间为1/r

找到目标扇区平均需要转半圈

因此延迟时间=1/2 * 1/r

传输时间

即从磁盘读出数据或向磁盘中写入数据所需时间，定义磁盘转速为r，此次写入/读出字节数为b，每条磁道字节数为N，那么我们写入或读出的磁道长度占总磁道长度为b/N，因此

传输时间=b/N * 1/r

磁盘调度算法

通过上面的分析不难知道延迟时间和传输速度都与磁盘转速直接相关，但是磁盘转速为硬件条件不能优化，因此要想优化磁盘读写速度只能优化寻道时间

先来先服务调度算法

即按照进程请求访问磁盘的顺序进行调度即可

最短寻找时间优先算法

扫描算法

Look调度算法

该算法用于优化上面的扫描算法的第一个缺点

循环扫描算法（C-SCAN）

C-LOOK调度算法

那么为了解决上面的C-SCAN算法的缺点，我们提出该算法

内存管理

首先简单认识一下计算机中的存储器结构

CPU寄存器

高速缓存（一个独立的硬件，不属于谁）

主存储器（即我们狭义上认为的内存条）

硬盘缓存（属于硬盘上的一块空间，例如我们在将进程挂起时即存储在这块区域）

固定磁盘（即我们认识的固定硬盘）

可移动存储介质（即我们认识的U盘，移动硬盘等等可移动的硬件）

进程运行的基本原理

用户程序如何变为进程

编译（即我们在写程序时进行的编译操作，是由用户完成的）

链接（将我们在程序中需要的一些库与我们所写程序合并为一个链接程序并成为一个模块）

装入（将模块装入内存）

链接的类型

静态链接（即在成为链接程序的过程中直接将所有需要的库加载成为链接程序，适用于小程序）

装入时动态链接（即在成为链接程序的过程中可以先将一部分库加载进入，等到装入程序开始进行装入时，再进行剩余部分库的链接，即实现装入与链接的并行，适用于大程序）

运行时动态链接（即在程序运行进行链接和装入操作，如果程序在内存中运行时发现缺少某个模块时进行链接和装入，适用于大程序）

装入的类型

绝对装入（适用于早期的单道程序，即由程序员去确认自己需要将程序装入到内存的哪个位置（物理地址），因为在单道程序中，内存除了操作系统占用的位置外，不可能有其他程序再占用内存了，并且注意这里是一次性将程序所需的全部空间都装入到内存）

可重定位装入（适用于早期的多道程序，这个时候因为在装入程序的时候，我们就很难去确认我们需要的物理地址是否已经被某个程序所占用，这里的每个程序在装入时都需要重新计算自己的装入位置，例如原本1号程序想要装入内存位置为0的，但是此时位置为0已经被某个大小为1024的程序所占用，那么我们的1号程序装入内存的位置计算则为0+1024，同样的注意这里也是一次性将程序所需的全部空间都装入到内存）

动态运行时装入（适用于现代的多道程序，即程序在内存中运行时发现缺少某个模块时才去进行链接装入，因此这里不再是一次性分配某个程序的全部所需空间了，而是在内存中可能各个程序的模块都是乱七八糟的，即可能当前位置是1号程序的某个模块，下一个位置就是其他程序的某个模块，再下一个位置又是1号程序的某个模块）

逻辑地址与物理地址

实际上对于多道程序的装入内存过程中，会存在一个地址转换的过程，即我们默认在我们程序中的数据默认地址是从0开始的，但是在实际内存中就不一定了，可能我们1号程序想要的地址是0开始的，但是实际内存中该位置已经被占用了，那么我们就需要从空闲的地址开始往后顺延，例如空闲的地址开始是1024那么我们的数据就存放在0+1024的位置上，这就是逻辑地址与物理地址的一个转换

内存保护

内存保护的实质就是使得每个进程在内存中只操作属于自己的内存空间而不越界，具体实现思路就是记录下每个进程在内存中的边界值，然后每当进程操作数据时我们进行判断是否越界即可，这里的记录进程在内存中的边界值可以有不同的方式

覆盖与交换

实际上，我们可能存在如下情况：内存大小为1G，但是我们现在有一个应用程序（假设只有这一个）为2G，那么我们只能将该应用程序的1G先加载到内存中，那么剩余的怎么办呢

覆盖：在内存空间中划分出一部分空间可以被用于覆盖的，即程序在运行时发现某一部分文件缺失，那么它就会去重新链接装入，并且这里装入的位置是前面所划分的覆盖区域，这样就实现了内存扩充

交换：在我们装入内存的文件中必然会存在一些不活跃的模块，那么我们在需要某个缺失的模块时，我们就将我们的不活跃某块换入到硬盘缓存中

内存管理方式-连续分配管理方式

单一连续分配

注意理解这里的外部碎片指的是分配给用户进程之外的内存空间是否全部利用，因为这里是单用户，因此整个用户区都是当前用户的也就不存在用户进程之外的空间，故无外部碎片

内部碎片指的是分配给用户进程内的内存空间是否全部利用，在整个用户区中，可能当前用户只使用了其中的一小部分空间，那么其他的空间便被浪费了，因此存在内部碎片

固定分区分配

固定分区分配指的是预先对内存的空间进行划分，划分为一个又一个的分区空间用于分配给进程，其中，我们可以有两种分区划分的方式，即分区大小相等与分区大小不等

此外为了方便对各个分区进行分配与回收，我们还会有一个分区记录表，用于记录各个分区的使用情况

这里因为内存空间都被划分为分区进行分配，因此无外部碎片

因为分区的大小不可能完全匹配进程所需空间，因此有内部碎片

动态分区分配

同固定分区分配不同的是，动态分区分配可以根据进程所需的空间在内存中创建相应的分区空间，因此系统分区的大小和数目是可变的

首先介绍记录内存使用情况的数据结构

有两种常用的数据结构：空闲分区表与空闲分区链

例如某一时刻内存使用情况如下：

那么空闲分区表如下：

空闲分区链如下（双向链表）：

正如上面的情况，例如现在有一个4MB的进程进来内存了，那么我们应该选择哪个分区进行分配呢？这里就需要考虑进程的分区分配算法了，常用算法如下

首次适应算法：从低地址查找合适空间

最佳适应算法：优先使用最小空闲空间

最坏适应算法：优先使用最大连续空间

临近适应算法：从上次查找处向后查找

具体各个算法的优缺点如下：

现在我们讨论分区的回收问题

如果回收的进程空间前后相邻空间均为空闲空间，那么我们将其合并为一个大空间，同时加入空闲分区表或分区链即可

反之，我们直接将其加入空闲分区表/链

内存管理-非连续分配

前面我们认识了内存管理的连续分配，下面介绍非连续分配

如上图所示，标出大小的空间为空闲空间，如果现在有一个大小为13M的进程想要进入内存，我们如果使用连续分配的话很明显是无法分配成功的，但是如果使用非连续分配就可以，即将进程拆分成多个模块放入内存中

那么如果我们将进程拆分为多个内存块的话，那我们的进程在内存中想要进行计算什么的，就需要一个数据结构去记录下各个内存块的位置以及大小等信息

基本分页存储管理方式

我们将整个内存空间按照固定大小去给他划分为分区（一般为4k），这个分区的大小一般不会太大，如果太大，产生的内部碎片也会随之变大，太小的话，分区的数目也会太多

实际上分页存储管理方式的实质类似我们前面所学的固定分区分配，只不过这里的分区大小较小

这里的叶框的名字不是固定的，各个版本的叫法不同，我们这里统一叫内存块

同样的，想要进入内存的进程也拥有类似叶框的概念，即对进程也进行分区，我们称之为页

页表

页表是实现我们在进程中的逻辑地址到内存中的物理地址的转换的关键

页表存储在进程控制块中(PCB)

如上图所示，页表中存储的是页号与块号，例如我们现在有一个数据存储在逻辑地址1024中，我们希望使得这个数据加一，那么我们需要得到该数据的物理地址对其加一，我们需要先得到逻辑地址1024在哪个页，然后通过页表得到其所在块，最后得到该数据的物理地址进行计算

逻辑地址与物理地址的转换

例如现在我们希望得到逻辑地址4097的物理地址

首先计算该逻辑地址所在页号，4097/4096=1，即该地址处于页号为1的位置，那么我们对照页表可以得到其所在块号为2，那么在2号块的哪个位置呢，我们还需要计算偏移量4097%4096=1，据此我们就得到了物理地址在2号块里位置为1的地方

快表

如上图所示，在前面的例子中，我们发现实际上得到一个数据的物理地址，我们就经历了两次内存访问，分别是访问页表、访问内存地址，而访问内存的效率实际上又是不如CPU和寄存器的，那么这样我们就可能被内存降低了效率，因此我们提出快表的概念进行优化

我们将内存中的页表称为慢表，在高速缓存中建立一个表称为快表，每当访问一次慢表，我们就讲对应的页号和块号加入到快表中，如果下次再访问同一个地址，我们就直接从快表中得到对应块号即可

直接将页号和快表页号比较

匹配成功，直接计算物理地址

匹配失败，访问主存页表，并同步到快表（局部性原理）

二级页表

二级页表的存在也是为了解决内存访问的效率低下的问题而存在的

例如在32位机器上，假设前20位用于存储页号，那么就有2^20个页号，即1MB个页，那么对应到页表中就有百万级别的数组，这样的大小实际上是会影响页表的查询的，因此我们希望优化页表查询效率，因此建立多级页表

二级页表的查询与前面一级页表的查询大差不差，这里不再赘述，主要是学习分页的思想

基本分段存储管理

我们知道前面所学的分页是指我们把物理内存空间按照固定的大小分成很多很多的块，实际上用户进程一般都会被划分为多个模块，例如子进程作为一个模块，所有进程的公共数据作为一个模块，因此我们就把用户进程的地址空间也按照模块进程划分，这就是分段存储管理，它与分页存储的区别在于每个段的大小都是不一定相同的，因为一个进程的模块一般都是不相等的

与页表类似的，分段存储也有段表，其逻辑地址与物理地址的转换也与页表基本相同，即得到一个逻辑地址后查询段表得到物理基地址后再根据段内地址合成物理地址

段的共享：如果说对于一个公共数据模块，子进程只需在自己的段表中加入该模块的信息即实现段的共享

段的保护：与页的物理地址访问类似的，我们在访问段的物理空间时需要考虑是否越界的问题

相对页而言，分段存储更容易实现信息共享和保护，因为在分页存储中，如果我们想要共享一个模块的话，可能对应的是好几百甚至更多的页，但是对应到段实际只有一个段

段页式管理方式

这里说明一下为什么分段会产生外部碎片：即当一个段比较大时，内存的存储空间暂时没有那么大的空间时，即产生了不能分配给进程的空间，因此产生外部碎片

实际上段页式管理方式就是先分段再分页，即在分段的内部我们进行分页

一个进程对应一个段表

一个段表项对应一个页表

一个页表对应多个物理块

它的逻辑地址与物理地址之间的转换也并不难

根据段表始址+段号得到段表项

根据段表长度/页表长度判断越界情况

页表地址+页号得到页表项

内存块号+页内地址得到物理地址

虚拟内存

虚拟内存即具有请求调入与置换功能，从逻辑上对内存容量加以扩充的一种存储器系统

虚拟内存的特征如下：

多次性：即这里对于一些大进程不再是一次性将其全部加入到内存中，而是先将其核心内容加入到内存中，之后需要什么内容再动态地加入

对换性：即我们在不需要某一个进程时运行将其挂起到硬盘缓存中

虚拟性：即虚拟内存实现了对内存逻辑大小的扩充

请求分页管理-页表

请求分页管理的页表与基本分页管理的页表区别如下：

状态位：表示该页是否已经调入内存

访问字段：表示该页在一定时间内被访问的次数

修改位：表示该页是否被修改过

外存地址：表示该页如果进行换入换出的话进入的外存地址

请求分页管理-缺页中断机构

即程序在内存中运行的过程中发现想要的块内容不存在，那么这个时候我们需要到外存中去将其加载进入内存

例如我们现在将页号为0的位置将其从外存地址x加载进来，同时更新页表

此外当根据页面置换算法选择将某一个页号的内容淘汰时，则与上述过程相反，根据其外存地址将其换出即可

请求分页管理-地址变换机构

请求调页，判断是否存在内存中

可能需要页面置换（内存不够）

新增、修改页表项

热点表项同步到快表中

页面置换算法

最佳页面置换算法

选择被置换的页面，将是未来永不使用的页面，或以后最长时间不使用的页面

优点：可保证最低的缺页率

缺点：不可能真正实现，只可作为其它算法的评价参考

2.先进先出算法

选择最先进入内存的页面，即选择在内存中驻留时间最长的页面予以淘汰

优点：算法简单

缺点：性能不佳

3.最近最久未使用算法（LRU）

选择最近最久未被使用的页面淘汰

优点：性能较好

缺点：需要较多的硬件支持

4.Clock算法

Clock 算法中，设置 1 位访问位，记录页面是否被访问过 ( 访问过为 1 ，未访问为 0)

5.改进型Clock算法

改进型 Clock 置换算法除设置 1 位访问位 (A) ，还设置 1 位修改位（ M ）

页面分配策略

前面的页面置换算法解决了我们选择页面进行换入换出的选择问题

实际上，当一个进程在进入内存时，我们在保证其能够运行的条件下，对其分配内存的大小

如果分配空间小，那么我们可以有更多的内存去容纳更多的进程，系统的并发性就增强，但是分配空间小则进程需要更多地去外存加载自己需要的模块，会导致缺页率的增加

所以我们需要选择合适的页面分配策略

固定分配局部置换（分配固定的内存大小，缺页时，从本进程中，按一定算法，选择一页调出）

可变分配全局置换（缺页时，系统从空闲物理块中分配一物理块，如果没有新的空闲块，则从整个内存中按一定算法选择一页调出）

可变分配局部置换（先在本进程页面中置换，缺页频繁时，系统增加分配内存块数；缺页很少时，系统减少分配内存块数）

何时调入页面

何地调入页面

全部从对换区调入页面

未运行过的页面，从文件区调入；如果该页面运行过程中被修改，则换出时，放到对换区；再调入时，则从对换区调入；未被修改的页面仍从文件区调入

进程管理

什么是进程

进程是程序的一次执行，是进程实体（包括程序段、数据和PCB）的运行过程，此处强调进程的动态，进程是系统进行资源分配与调度的独立单位

进程 ＝程序（纯代码段＋数据段）＋程序专用控制数据区

程序实体=控制块+数据段+程序段
进程的结构

此处需要强调的是，同一个应用程序的不同进程之间是共享程序段的，因为使用的是一样的程序段，这样可以避免占用内存空间

进程的特征

线程是什么

线程是进程的“轻型实体”，是一条执行路径，不能单独存在，必须包含在进程中，线程是OS中调度和执行的基本单位（进程是资源分配的基本单位），线程的存在进一步提高了系统的并发性，线程都共享自己进程的资源

线程的分类

内核级线程：线程的处理均由内核实现，内核为线程保留TCB，并通过TCB感知线

用户级线程：线程的处理不通过内核实现，线程的状态信息等全部存放在用户空间中，内核不能感知用户级线程

二者本质的区别在于线程的控制块是在内核还是在用户空间

进程的状态

首先了解一下进程的生命周期概念：即一个进程从在内存中被创建PCB到从内存中销毁的过程

进程的三个基本状态如上图所示

首先对于就绪状态而言，即进程在内存中已经具备了除CPU之外的一切条件，就等着处理机进行调度即可，这里面包含着队列的数据结构，即各个进程在内存中排队等待CPU

之后按照一定的进程调度算法，选择某个进程进入CPU处理，即进入执行状态

注意这里进程进入CPU处理，CPU会分配给进程一定的时间片，如果没有发生任何意外，那么进程的时间片用完了，就会回到就绪队列的队尾继续排队等待进入CPU

但是如果进程在进入CPU之后，发生了意外，例如进程发现自己缺页了，发出了IO请求（当然引发阻塞的原因很多），那么相当于进程主动放弃了CPU，则该进程会进入阻塞队列中，直到意外解决，那么该进程则重新回到就绪队列排队等待CPU调度

接着补充两种状态：创建和终止

创建状态，即一个应用程序从磁盘中将所有需要的资源加载到内存中，同时创建自己的PCB

终止状态：即一个进程的任务已经完成了或者我们人为介绍了该进程，这里可以是正常终止也可以是异常终止

进程控制

即OS对进程实现有效的管理，包括创建新进程、撤销已有进程、挂起、阻塞和唤醒、进程切换等操作，OS通过原语实现进程控制

原语：由若干条指令组成，完成特定的功能，是一种原子操作

原语的特点：

原子操作，要么全做，要么不做，执行过程中不会被中断

在内核中执行，常驻内存

是内核三大功能之一（中断处理、时钟管理、原语操作）

下面补充进程的另外两个状态：对进程挂起、对进程激活

注意这里挂起操作的实质是将进程放到外存中去，即暂时可能不需要这个进程而将其挂起，需要注意的是刚创建的进程也可以被挂起，例如创建了该进程的PCB后系统突然发现内存不够了因此可能将其挂起

处理机调度的层次

高级调度/作业调度（相当于进入就绪状态）

把后备作业调入内存

只调入一次，调出一次

中级调度/内存调度（相当于挂起操作、激活操作）

将进程调至外存，条件合适再调入内存

在内外存对换区进行进程对换

低级调度/进程调度（即进入执行状态）

从就绪队列分配进程给处理机

调度频率很高

处理机调度方式

抢占式调度

立即暂停当前进程

分配处理机给另一个进程

原则：优先权/短进程优先/时间片原则

非抢占式调度

若有进程请求执行

等待直到当前进程阻塞或完成

适用于批处理系统，不适用于分时/实时xiton

处理机调度过程（上下文切换）

保存镜像：记录进程当前现场信息

调度算法：确认分配处理机的原则

进程切换：分配处理机给其他进程

处理机回收：从进程收回处理机

恢复现场：利用镜像还原现场信息

进程调度指标

周转时间：作业（进程）i从提交（进入时刻）到完成的时间称为该作业的周转时间Ti
pTi = 完成时刻 – 进入时刻

平均周转时间：平均周转时间为n个作业（进程）周转时间的平均值

带权周转时间：作业(进程)周转时间Ti与实际运行时间Tsi之比称为该作业的带权周转时间Wi

平均带权周转时间：•平均带权周转时间为n个作业（进程）带权周转时间的平均值

平均等待时间：进程i从进入就绪队列到获得CPU的时间称为该进程的等待时间WTi

进程调度算法

先来先服务

算法内容：调度作业/就绪队列中最先入队者

算法原则：按照作业/进程到达顺序服务

调度方式：非抢占式

使用场景：作业/进程调度

优缺点

有利于CPU繁忙型作业，充分利用CPU资源

不利于IO繁忙型作业，操作耗时

短作业优先

算法内容：所需服务时间最短的作业/进程优先服务（执行）

算法原则：追求最小的平均（带权）周转时间

调度方式：非抢占式

使用场景：作业/进程调度

优缺点

平均等待/周转时间最小

长作业周转时间会增加或饥饿

估计时间不准确，不能保证紧急任务及时处理

高响应比优先调度

算法内容：结合先来先服务、短作业优先，综合考虑等待时间和服务时间计算响应比，高的优先调度

算法原则：综合考虑作用/进程的等待时间和服务时间

调度方式：非抢占式

使用场景：作业/进程调度

优缺点

响应比=（等待时间+预估服务时间）/预估服务时间

只有当前进程放弃执行权（完成/阻塞）时，重新计算所有进程响应比

长作业等待时间越久响应比越高，更容易获得处理机

优先级调度

算法内容：按照作业/进程的优先级（紧迫程度）进行调度

算法原则：优先级最高（最紧迫）的作业/进程先调度

调度方式：抢占式/非抢占式

使用场景：作业/进程调度

优缺点

静态（进程创建时即设置优先级不变了）/动态（进程在运行过程中优先级可能改变）

系统进程>用户进程；交互型进程>非交互型进程；IO型进程>计算型进程

低优先级进程可能会产生饥饿

时间片轮转调度

算法内容：按照进程到达就绪队列的顺序，轮流分配一个时间片去执行，时间用完则剥夺

算法原则：公平、轮流地为每个进程服务，进程在一定时间内都能得到响应

调度方式：抢占式，由时钟中断确定时间到

使用场景：进程调度

优缺点

公平、响应快，适用于分时系统

时间片决定因素：系统响应时间、就绪队列进程数量、系统处理能力

时间片太大，相当于先来先服务；太小，处理机切换频繁，开销大

多级反馈队列调度

算法内容：设置多个按优先级排序的就绪队列，优先级从高到低，时间片从小到大，时间片从小到大，新进程采用队列降级法，即进程先进入第一级队列，按先到先得分配时间片，如果分配的时间片用完了进程也未完成，那么进程进入下一级队列队尾，直至进程完成，需要注意的时，CPU按照优先级队列执行进程，如果前面队列不为空，不会执行后续队列进程

算法原则：集前面所学算法的优点，相当于优先级调度+时间片算法

调度方式：抢占式

使用场景：进程调度

优缺点

对各个类型进程相对公平，能够快速响应

短作业优先

周转时间短

长作业也能够在前面的队列先得到部分执行

进程通信

概念：进程通信即进程之间的信息交换

进程是资源分配的基本单位，各进程的内存空间是相互独立的

一个进程不能随意访问其他进程地址空间

共享存储

基于共享数据结构的通信方式

多个进程共用某个数据结构（由OS提供并控制）

由用户负责同步处理

是一种低级通信，只能传递少量数据，效率低

基于共享存储区的通信方式

多个进程共用内存的一块存储区域

由进程控制数据的形式和方式（即进程自己动态申请）

高级通信：可以传递大量数据，效率高

但是以上两种通信方式都存在安全隐患，因为数据收发双方不可见

消息传递

直接通信：点到点发送

发送时指明双方进程的ID

每个进程维护一个消息缓存队列

间接通信：广播信箱

以信箱为媒介，作为中间实体

发进程将信息发送到信箱内，收进程从信箱中读入信息（注意与共享存储不同的是这里的收和发都是使用原语进行操作的）

可以广播（即允许将某条信息发给多个进程），容易建立双向通信链

管道通信

管道

是用于连接读/写进程的共享文件，pipe文件

本质是内存中固定大小的缓冲区

半双工通信

同一时段只能单向通信，想要双向通信只能创建两个管道

以先进先出方式组织数据传输

通过系统调用read()/write()函数实现读写操作

进程同步与互斥

广义上，进程同步指的是协调进程之间的相互制约关系,使得他们按照预期的方式执行的过程

下面介绍临界区与临界资源的概念

其实临界资源又称为共享资源，即一个时刻只能由一个进程使用的资源

进程同步的其中一种情况就是互斥地访问临界资源

访问临界资源的原则

实现同步互斥的高级方法-信号量机制

下面则是信号量机制所使用的一对原语

整型信号量

注意整型信号量与普通整型变量的区别在于对信号量的操作只有三种，即初始化、P操作、V操作

可以看到上面wait代码中存在可能的死循环while，因此它是不满足让权等待原则的，可能会发生忙等

记录型信号量

记录型信号量即使用一个记录型数据结构表示信号量

信号量实现进程互斥

信号量机制实现进程同步

首先复习一下进程同步的概念：让并发进程有序地向前推进

例如上述代码中我们需要保证代码4在代码1和代码2执行完毕后再执行

总结：

前V后P

在前操作之后执行V操作

在后操作之前执行P操作

经典同步问题

首先给出此类问题的解题步骤

关系分析，找出题目中描述的各个进程之间的同步、互斥关系

整理思路，根据前一步得到的关系确定PV操作的顺序（前V后P)

设置信号量，并根据信号量设置其初始值

单生产者消费者

这里比较容易就能找到进程间的关系

各个进程之间互斥访问缓冲区（避免数据覆盖）

缓冲区未满——》生产者生产

缓冲区未空——》消费者消费

据此我们设置如下信号量

接着实现代码就容易了

这里我们可能会有这样的疑问就是为什么不把对互斥的P操作放在最前面呢？

举个例子：

当某个时刻，缓冲区中已经被已经被放满了产品，那么此时empty=0，full=n，则此时生产者进程，先对互斥上锁，然后对empty信号量实行P操作，发现此时empty为0因此该进程阻塞，那么进行进程调度，消费者来了发现此时的mutex已经被上锁了，因此也阻塞了，此时便构成了死锁

多生产者多消费者问题

我们可以将父亲和母亲看作两个生产者，儿子与女儿看作两个消费者，盘子看作一个大小为1 的缓冲区

找进程之间的关系

4个进程之间肯定是互斥访问的

父亲放入苹果-》女儿吃掉苹果

母亲放入橘子-》儿子吃掉橘子

盘子为空-》父亲或母亲放水果

综上我们设置四个信号量

具体实现如下

哲学家进餐问题

如上图所示，我们对每位哲学家进行编号，同时对桌子上的筷子进行编号，那么不难看出每位哲学家左边的筷子=哲学家编号，右边筷子=（哲学家编号+1 ）%5

那么我们不难发现实际上该题只有一个互斥关系，及即每位哲学家拿起左右筷子-》吃饭

那么我们这样实现

但是，这样实现会出现死锁（因为该题每个进程需要拥有两个临界资源才能执行）

例如，每位哲学家在拿到自己左边的筷子后则进行调度，那么则每位哲学家都变成了等待自己右手边的筷子！

考虑如下三种解决方案

1、对哲学家进程施加限制条件

我们增加一个新的信号量用于限制最多运行4位哲学家进餐，则这样可以保证至少一位哲学家可以拿到一双筷子

实现如下
mutex=4
arr[5]={1,1,1,1,1}

P(mutex)
P(arr[i])
P(arr(i+1)%5)
吃饭
V(arr[i])
V(arr(i+1)%5)
P(mutex)
还是前面的例子如果每位哲学家在拿起左边筷子后被调度，那么我们不难发现在第5个哲学家执行P(mutex)时就会被阻塞，那么则上一位哲学家就可以拿到一双筷子

2、设置哲学家拿筷子的顺序

我们可以要求奇数位的哲学家先拿左边的筷子再拿右边筷子，而偶数位哲学家先拿右边再拿左边，这样我们必然可以使得其中一位哲学家拿起一支筷子后另一位哲学家直接阻塞，避免了哲学家拿着一支筷子之后阻塞的情况

具体实现如下
if(i%2){
P(arr[i])
P(arr(i+1)%5)
}else{
P(arr(i+1)%5)
P(arr[i])
}
吃饭
V(arr[i])
V(arr(i+1)%5)
3、设置仅当哲学家左右手筷子同时拿起

哲学家问题我们主要学习如何解决死锁问题

读者写者问题

仔细分析题目不难发现，进程之间的关系如下

写进程与写进程之间

写进程与读进程之间

如上只是简单的实现了题目，具体其中还有一些细节这里没有注意的，该问题主要是为我们提供了复杂互斥问题的解题思路

管程

基本概念：管程即管理进程，是用于实现进程同步的工具，是由代表共享资源的数据结构和一组过程（进行PV操作的函数）组成的管理程序（封装）

我们可以将管程看作一个类，其中包含了进程想要访问的临界资源，并且这些资源是类私有的，管程会对外提供一些公共方法用于进程的访问临界资源，即PV操作，管程对临界资源实现了封装，它是一个模块化的基本程序单位，可以单独编译

条件变量/条件对象（相当于互斥信号量）

进入管程的进程可能由于条件不满足而阻塞，此时进程应该释放管程以便其他进程调用管程

进程被阻塞的条件很多，会被移入不同的条件队列

进程被移入条件队列后应该释放管程

死锁

死锁产生的必要条件

互斥条件：即一个共享资源同一时刻只能有一个进程得到

不剥夺条件：即进程拥有共享资源后不会被其他进程抢占

请求并保持条件：即一个进程在拥有一个共享资源后还需要申请其他资源

循环等待条件：即进程互相等待对方的资源释放

死锁的预防

设置某些限制条件，破坏产生死锁的必要条件中的一个或几个条件

一次分配全部资源(摒弃“请求和保持”条件)

当请求的资源得不到满足时，释放已分配的资源（摒弃“不剥夺”条件）

对资源的申请必须按一定顺序进行（摒弃“环路等待”条件）

死锁的避免-银行家算法

分配资源之前，先判断是否会进入不安全区（危险区和禁区），如果会进入危险区，则不分配资源，进程在分配资源之前需要先告诉系统自己最大需要多少资源以便系统进行判断，即如果进程在动态分配过程中请求的资源数量大于自己的最大需要资源数则拒绝，此外如果系统所剩资源数不够分配给进程所申请的资源数也会拒绝

死锁的检测与解除

死锁的解除有如下三种方法：

进程回退

抢占资源

        抢占足够数量的资源分配给死锁进程，以解除死锁状态

终止或撤消进程
        终止一个或多个死锁进程，直至打破循环环路

终止进程的方法
        终止所有的死锁进程，全部撤消法
        按照某种顺序，逐个地终止进程

对于死锁的检测我们使用死锁定理进行检验

首先画出资源分配图

将既不是孤立的进程点又不是阻塞的进程点所连接的边都删除（判断进程是否阻塞可以通过当前进程所请求的资源是否能够得到判断）

如果最后能够将所有的点变为孤立的点则不存在死锁，反之存在

补充实时调度算法-EDF和LLF

简单来说

EDF就是根据任务的开始截止时间（开始截止时间即在这个时间到达之前必须开始这个任务）来进行调度

LLF就是根据任务松弛度进行调度（松弛度即当前时间距离Deadline还有多远，松弛度=截止时间-运行时间-当前时间）

参考资料1

参考资料2

操作系统引论

什么是操作系统

操作系统是一个三明治结构，向上利用接口对接用户、向下利用驱动对接硬件、作用是对系统资源进行管理的一系列程序的集合（自己总结）

操作系统特征如下：

并发性

虚拟性

异步性

共享性

操作系统的功能

处理机管理

进程控制

进程同步

进程通信

进程调度

存储器管理

内存分配

内存保护

地址映射

内存扩充（虚拟存储器）

设备管理

缓冲管理

设备分配

设备处理

设备独立性

虚拟设备

文件管理

存储空间管理

文件系统

用户接口

命令接口

程序接口（系统调用）

图形接口

单道批处理系统

•需要监督程序（Monitor）

•多个作业顺序轮流使用计算机（共享）

•计算机的控制权在监督程序与作业之间交替使用

单批道处理程序特征如下：

自动性

顺序性

单道性

多道批处理系统

• 计算机中同时有几道作业（程序）在运行，提高了计算机资源的使用效率

• 多道批处理系统特征：

• 多道性，无序性，调度性

• 现有三道作业，第一道作业需要输入10 S，运行20 S，输出20 S；第二道作业需要输入20 S，运行20 S，输出30 S，然后再运行30,输出10 S；第三道作业需要输入20 S，运行30 S，输出30 S

其中ABC分别代表三个作业，针对上图我们计算各个程序的设备利用率

分时系统

•计算机内存中同时有多个用户程序

•每个用户程序运行一小段时间（时间片，如0.1秒），然后停止该程序运行，由系统再调用下一个用户程序运行

•每个用户程序在不长的时间内，都能执行一次

分时系统的特性如下：

•多路性：系统中有多个用户程序同时运行

•独立性：每个用户(程序)独立操作，互不干扰

•及时性：用户的请求能在较短(秒级或以下)时间内获得响应

•交互性：用户可以同系统进行人机对话

•分时系统的主要目的提高资源的使用方便性

实时系统

•要求计算机系统及时响应随机发生的外部事件，并以足够快的速度完成对事件的处理

•实时控制：工业生产的控制，信息采集的控制等（中断）

•实时信息处理：及时信息检索或处理

•分时系统 VS.实时系统

文章来源地址https://www.toymoban.com/news/detail-492968.html