整理了一些 os 的选择题知识点、大题的重要知识点，还有一些简答的梳理。

# 单元 1 操作系统概论

# 操作系统分类

# 批处理系统

** 多道：** 在内存中同时存放多个作业，一个时刻只有一个作业运行，这些作业共享 CPU 和外部设备等资源。

** 成批：** 用户和作业之间没有交互性。用户自己不能干预自己的作业的运行，发现作业错误不能及时改正。

# 分时操作系统

它能很好地将一台计算机提供给多个用户同时使用，提高计算机的利用率。分时系统是指，在一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户通过自己的终端，以交互方式使用计算机，共享主机中的资源。

1. 同时性：计算机系统能被多个用户同时使用；
2. 独立性：用户和用户之间都是独立操作系统的，在同时操作时并不会发生冲突，破坏，混淆等现象；
3. 及时性：系统能以最快的速度将结果显示给用户；
4. 交互作用性：用户能和电脑进行人机对话。

# 实时操作系统

所谓 “实时”，是表示 “及时”，而实时系统是指系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致的运行。其应用需求主要在实时控制和实时信息处理。

实时操作系统必须在规定时间内处理来自外部的事件

特点：

高精度计时系统：计时精度是影响实时性的一个重要因素。在实时应用系统中，经常需要精确确定实时地操作某个设备或执行某个任务，或精确的计算一个时间函数。这些不仅依赖于一些硬件提供的时钟精度，也依赖于实时操作系统实现的高精度计时功能。
多级中断机制：一个实时应用系统通常需要处理多种外部信息或事件，但处理的紧迫程度有轻重缓急之分。有的必须立即作出反应，有的则可以延后处理。因此，需要建立多级中断嵌套处理机制，以确保对紧迫程度较高的实时事件进行及时响应和处理。
实时调度机制：实时操作系统不仅要及时响应实时事件中断，同时也要及时调度运行实时任务。但是，处理机调度并不能随心所欲的进行，因为涉及到两个进程之间的切换，只能在确保 “安全切换” 的时间点上进行，实时调度机制包括两个方面，一是在调度策略和算法上保证优先调度实时任务；二是建立更多 “安全切换” 时间点，保证及时调度实时任务。

# 多用户操作系统

# 分布式系统

分布式系统是由一组通过网络进行通信、为了完成共同的任务而协调工作的计算机节点组成的系统。

# 特权指令

能引起损害的机器指令作为特权指令

1. 允许和禁止中断，控制中断禁止屏蔽位
2. 在进程间切换处理
3. 存取用于主存保护的寄存器
4. 执行 I/O 操作
5. 停止一个中央处理器的工作
6. 清理内存
7. 设置时钟
8. 建立存储键
9. 加载 PSW

# 操作系统管理的资源

• 所有硬件资源，如 CPU、存储器、输入输出设备
• 软件资源等，如程序和数据等。

# 并发性

共享性、虚拟性、异步性

• 并行是指两个或多个事件可以在同一个时刻发生。
• 并发是指两个或多个事件可以在同一个时间间隔发生。

同一时刻即为并行，一定的时间间隔发生即为并发。

# 多道程序设计

多道程序设计：允许多个程序（作业）同时进入一个计算机系统的内存并启动进行交替计算的方法，也就是，计算机中可以同时存放多道程序，从宏观上来看它们是并行的，多道程序都同时处于运行过程中，但都未运行结束，但是微观上是串行的，轮流占用 CPU 交替执行，引入多道程序设计技术的根本目的是提高 CPU 的利用率，充分发挥计算机系统部件的并行性。

多道程序设计的特点

1. CPU 与外部设备充分并行
2. 外部设备之间充分并行
3. 发挥 CPU、内存和设备的使用效率
4. 提高单位时间的算题量 (吞吐率)

多道程序设计的主要缺点：

1. 延长了作业的周转时间。

# SPOOLing 技术

SPOOLing 技术便可将一台物理 I/O 设备虚拟为多台逻辑 I/O 设备，同样允许多个用户共享一台物理 I/O 设备。

# 单元 2 处理器管理

目态：用户态

管态：特权态、系统态、核心态

进程与线程

1. 进程是资源分配和管理的单位
2. 线程是处理器调度的基本单位。

PCB：进程控制块

# 进程概念

进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动。

1. 具有一定独立功能的程序：进程是相对独立的
2. 关于某个数据集合：对于不同数据集合的操作不是同一个进程。
3. 一次运行活动：有生命周期

动态性、共享性、独立性、制约性、并发性

# 进程管理原语，0

进程创建

进程撤销

进程阻塞

进程唤醒

进程挂起

进程激活

# 进程转换模型

运行态：进程占用处理器运行

就绪态：进程具备运行条件等待处理器运行

等待态：又称阻塞态、睡眠态，进程由于等待资源、输入输出、信号等而不具备运行条件

挂起态：挂起态与等待态有着本质区别，后者占有已申请到的资源处于等待，前者没有任何资源

# 线程

# 用户级线程和内核级线程的区别

1. ULT 适用于解决逻辑并行性问题
2. KLT 适用于解决物理并行性问题

# jacketing 技术

为了解决一个 ULT 的阻塞，将引起整个进程的阻塞的问题，出现了 jacketing 技术。

jacketing 技术将阻塞式的系统调用改造成非阻塞式的，当线程陷入系统调用时，检查 jacketing 程序，由 jackting 程序来检查资源使用情况，以决定是否执行进程切换或传递控制权给另一个线程。

比如说，当线程需要 I/O 资源时，它不直接去调用系统 I/O 例程，而是让线程调用一用户级的 I/O 的 Jacketing 例程，这个 jacket 例程中的代码用来检查并确定 I/O 设备是否忙。如果忙，该线程进入阻塞状态并将控制传送给另一个线程。当这个线程后来又重新获得控制时，jacketing 例程会再次检查 I/O 设备。

# 多线程实现的混合式策略

1. 线程创建完全在用户空间中完成，线程的调度和同步也在应用程序中进行
2. 一个应用中的多个用户级线程被映射到一些 (小于等于用户级线程数目) 内核级线程上

<img src="https://quasdo.oss-cn-hangzhou.aliyuncs.com/img/20.png" alt="img" style="zoom:33%;" />

<img src="https://quasdo.oss-cn-hangzhou.aliyuncs.com/img/21.png" alt="img" style="zoom:33%;" />

# 单元 3 存储管理

存储分配：位进程分配内存空间以便运行，完成内存区的分配和去配工作。

地址映射：内存被抽象为一维或二维地址空间；逻辑空间到物理空间映射。

存储保护：系统隔离分配给进程的内存区，防止地址越界或操作越权。

存储共享：系统允许多个进程共享内存区。

存储扩充：形成虚拟存储器

# 静态重定位 / 动态重定位

地址转换：又称重定位，即把逻辑地址转换成绝对地址

1. 静态重定位：在程序装入内存时进行地址转换：由装入程序执行，早期小型 OS 使用，基于地址固定值进行偏移。
2. 动态重地位 (主流)：在 CPU 执行程序时进行地址转换：从效率出发，依赖硬件地址转换机构，运行时正确的将其逻辑地址转换为物理地址。

# 存储保护

为避免主存中的多个进程相互干扰，必须对主存中的程序和数据进行保护

1. 私有主存区中的信息：可读可写
2. 公共区中的共享信息：根据授权
3. 非本进程信息：不可读写

# 内存碎片 / 外存碎片

（1）性质不同：

①内存碎片：指的是已经被分配出去的，但是却没有被使用的内存空间。 因为基本存储单位的限制

②外存碎片：指的是还没有被分配的，但是由于太小或者是不连续，而导致不满足要求，所以没办法被分配的内存空间

（2）存储位置不同：

①内存碎片是存储于已分配区域内部的

②外存碎片是存储于未分配区域的

（3）状态不同：

①内存碎片：其他进程没办法使用它，因为它被某一个进程占有

②外存碎片：其他进程没办法使用它，因为它可存储的位置不连续或者是太小了

分页存储会产生内存碎片，不会产生外存碎片；

分段存储不会产生内存碎片，会产生外存碎片。

段页式存储：产生内存碎片、外存碎片。

# 存储扩充

对换技术：把部分不运行的进程调出

虚拟技术：只调入进程的部分内容，对单个进程不使用对换技术完成，特点是自动化、透明

# 内存不足的存储技术

移动技术：当未分配区表中找不到足够大的空闲区来装入新进程时，我们使用移动技术来完成内存紧凑，实现方法：

1. 全部移动到一侧
2. 移动直到有足够大的空闲区

需要动态重定位支撑:

对换技术：如果当前一个或多个驻留进程都处于阻塞态，此时选择其中一个进程，将其暂时移出内存，腾出空间给其他进程使用，；同时把磁盘中的某个进程换入内存，让其投入运行，这种互换称为对换。

内存覆盖技术：指程序执行过程中程序的不同模块在内存中相互替代，以达到小内存执行大程序的目的。

# 存储层次

<img src="https://quasdo.oss-cn-hangzhou.aliyuncs.com/img/3.png" alt="3" style="zoom:33%;" />

# 页式存储

逻辑地址 = 页号 + 页面偏移

物理地址 = 页架号（页框号） + 单元号（页内偏移)

页的共享：

1. 数据共享：不同进程可以使用不同页号共享数据页
2. 程序共享：不同进程必须使用相同页号共享代码页

页式存储管理的地址转换

<img src="https://quasdo.oss-cn-hangzhou.aliyuncs.com/img/image-20230610100614192.png" alt="image-20230610100614192" style="zoom:50%;" />

页表控制寄存器存储了当前的页表的地址和长度

多级页表

<img src="https://quasdo.oss-cn-hangzhou.aliyuncs.com/img/image-20230610101214843.png" alt="image-20230610101214843" style="zoom:50%;" />

逻辑地址结构有三部分组成：页目录、页表页和位移

<img src="https://quasdo.oss-cn-hangzhou.aliyuncs.com/img/image-20230610103318317.png" alt="image-20230610103318317" style="zoom:50%;" />

反置页表 IPT

正向页表：以页号为索引 (隐含)，完整连续排列，页表项中不含页号，每个进程单独一个页表

反置页表：以页框号为索引 (隐含)，完整连续排列，每个页框填入的是哪个进程的哪个页号，索引进程共用一个反置页表。其页表项不包含页框号

通过这个结构，哈希表和反向表中只有一项对应于一个实存页 (面向实存)，而不是虚拟页 (面向虚存)。
因此，不论由多少进程、支持多少虚拟页，页表都只需要实存中的一个固定部分。

页表结构：页号、进程标识符、控制位、哈希链指针

<img src="https://quasdo.oss-cn-hangzhou.aliyuncs.com/img/image-20230610104452727.png" alt="image-20230610104452727" style="zoom:50%;" />

<img src="https://quasdo.oss-cn-hangzhou.aliyuncs.com/img/image-20230618104409177.png" alt="image-20230618104409177" style="zoom: 25%;" />

# 段式存储

逻辑地址 = 段号 + 段内偏移

页式存储管理中页的划分对程序员不可见。

段式存储管理中段的划分对程序员可见。

<img src="https://quasdo.oss-cn-hangzhou.aliyuncs.com/img/image-20230610105016781.png" alt="image-20230610105016781" style="zoom:50%;" />

# 段页式存储管理

<img src="https://quasdo.oss-cn-hangzhou.aliyuncs.com/img/image-20230610105414145.png" alt="image-20230610105414145" style="zoom:50%;" />

# 页面调度（未看）

OPT 页面调度算法（Belady 算法）

先进先出页面调度算法 FIFO-Belady 异常 - 更多的页框导致了更高的缺页率，页框为 3 和 4 的时候

<img src="https://quasdo.oss-cn-hangzhou.aliyuncs.com/img/image-20230618105652127.png" alt="image-20230618105652127" style="zoom:25%;" />

页面缓冲算法

最近最少用 LRU

第二次机会页面替换算法 SCR

最不常用 LFU

时钟 CLOCK

# 单元 4 设备管理

# 分类

1. 按信息传输方向 (I/O 操作特性) 分类

   1. 输入
   2. 输出
   3. 输入输出

2. 按交互功能划分

   1. 人机交互
   2. 存储
   3. 机机通信

3. 按设备管理 (I/O 信息交换单位) 划分

   1. 字符
   2. 块
   3. 网络

4. 按传输速率

   1. 低速设备，键盘、鼠标

      大多数低速设备都属于独享设备

   2. 中速设备，激光打印机

   3. 高速设备，磁盘机、光盘机

# IO 控制方式

1. 轮询（程序直接控制方式）
   • 重复测试
   • CPU 和设备串行工作
2. 中断
   • CPU 和设备部分并行
3. DMA（Direct Memory Access 直接存储器访问）
   • 内存和设备之间有一条数据通路成块地传送数据，无需 CPU 参与
   • 流程：
     • 处理器向 DMA 模块发出 I/O 命令
     • 处理器继续执行其它工作，DMA 模块负责传送全部数据
     • 数据传送结束后，DMA 中断处理器
   • 周期窃取：CPU 总是将总线的占有权让给 DMA 一个或几个主存周期，一般是 1 个存取周期，让设备和内存之间交换数据。
4. IO 通道
   • 定义：
     • 一个具有特殊功能的处理器，它有自己的指令和程序，专门负责数据输入输出的传输控制 (CPU 把传输控制的功能下放给通道)。通道受 CPU 的 I/O 指令启动、停止或改变其工作状态。
   • 功能：
     • 按 I/O 指令要求启动 I/O 设备
     • 执行通道指令
     • 组织 I/O 设备和主存进行数据传输
     • 向 CPU 报告中断
   • CPU 与通道高度并行
   • IO 指令由 IO 通道所包含的处理器执行
   • 与 DMA 的区别：可以连接多个设备，读取多个数据块
   • 通道指令：又叫通道控制字 (CCW)，它是通道用于执行 I/O 操作的指令，它可以由管理程序存放在主存的任何地方，由通道从主存取出并执行。【IO 指令是 CPU 指令系统的一部分，用于控制输入输出操作的指令，通道指令是通道本身的指令，用来执行 IO 操作】
   • 通道程序：由通道指令组成，它完成某种外围设备与主存传送信息的操作，如将磁带记录区的部分内容送到指定地址的主存缓冲区内。
   • 这是一种硬件机制。

一个有趣的例子 belike：

5. 总线
   1. 单总线
   2. 传统的三级总线
   3. 采用南北桥的多级总线
   4. 采用 IO 通道的多级总线

# IO 软件的实现【todo 再看看】

同步 / 异步传输：支持阻塞和中断驱动两种工作方式

层次：

# IO 中断处理程序

1. 处理 IO 中断：检查设备状态寄存器内容，判断产生中断的原因，根据 I/O 操作的完成情况进行相应的处理
2. 报告错误：如果数据传输有错，向上层软件报告设备的出错信息，实施重新执行
3. 唤醒驱动程序：如果正常结束，唤醒等待传输的进程，使其转换为就绪态设备驱动程序

# 设备驱动程序

任务：

1. 把用户提交的逻辑 I/O 请求转化为物理 I/O 操作的启动和执行，如设备名转换为端口等
2. 监督设备是否正确执行，管理数据缓冲区，进行必要的纠错处理

功能：

1. 设备初始化：在系统初次启动或设备传输数据时，预置设备和控制器以及通道状态
2. 执行设备驱动例程
   1. 负责启动设备，进行数据传输
   2. 对于具有通道方式，还负责生成通道指令和通道程序，启动通道工作
3. 调用和执行中断处理程序：负责处理设备和控制器及通道所发出的各种中断

# 独立于设备的 IO 软件

# 用户空间的 IO 软件

SPOOLing 软件

# 缓冲技术

缓冲区：在内存中开辟的存储区，专门用于临时存放 I/O 操作的数据

解决 CPU 与设备之间速度不匹配的矛盾

基本思想：写缓冲、读缓冲

实现：

1. 单缓冲

   • 工作机制：
     • 输入：将数据读至缓冲区，系统将缓冲区数据送至用户区，应用程序对数据进行处理；如此往复，系统读入后续的数据
     • 输出：把数据从用户区复制到缓冲区，再将数据输出后，应用程序继续请求输出
   • 性能计算

2. 双缓冲

3. 多缓冲

   多缓冲组成的循环缓冲技术，多缓冲的缓冲区是系统的公共资源，可供进程共享并由系统统一分配和管理。

4. 缓冲池

   使多个进程能够有效地同时处理输入和输出

5. 循环缓冲

# 驱动调度技术

磁盘是一种直接存取存储设备，磁带是一种顺序存取存储设备

1. 三维地址（磁头号、柱面号、扇区号）
   1. 盘面号也被叫做磁头号
   2. 磁道号也被叫做柱面号
   3. 区别:"0 面 0 道 1 扇区" 中的 "面" 是指磁头，不是柱面
      1. 面和道都是 0 开始
      2. 扇区是从 1 开始
2. 磁盘存取时间 = 寻道时间 + 旋转延迟 + 传送时间

# 磁盘的驱动调度

1. 旋转调度
   • 目的: 使得旋转延迟的总时间最少
   • 旋转排序
     • 通过优化 I/O 请求排序，在最少旋转圈数内完成位于同一柱面的访问请求
   • 优化分布
     • 通过信息在存储空间的排列方式来减少旋转延迟
2. 移臂调度

3. 磁盘冗余阵列
4. cache / 替换

# 设备分配

1. 设备的分类：

   • 独占设备：一次只能由一个进程独占使用
   • 共享设备：多个进程同时使用的设备，其管理工作主要是驱动调度和实施驱动，一般不必分配
   • 虚拟设备：使用一类物理设备模拟另一类物理设备的技术，让独享型设备变为共享设备

2. 设备独立性：

   • 用户通常不指定物理设备，而是指定逻辑设备，使得用户作业和物理设备分离开来，再通过其它途径建立逻辑设备和物理设备之间的映射
   • 设备管理的功能就是将逻辑设备名转换为物理设备名，为此系统需要提供逻辑设备名和物理设备名的对应表以供转换使用。
     • 逻辑设备号由用户定义。
     • 物理设备号由系统规定，不可修改。
   • 绝对号 / 相对号
     • 绝对号：就是将每一台设备确定一个编号（相当于一个绝对地址）
     • 相对号：就是为了用户程序的方便而设的，在用户请求使用时，采用 “设备类 - 相对号” 来提出使用设备要求。

3. 分配方式：

   • 静态分配：防止死锁
   • 动态分配：设备利用率高

4. 设备分配算法：

   1. 先来先服务
   2. 优先级高者优先

5. SPOOLing 设备（假脱机技术）

   • 将独占设备改成共享设备的技术
   • 采用预输入、缓输出和井管理技术
   • 通过创建守护进程和特殊目录解决独占型设备的空占问题
   • 目的：提高 IO 设备的使用效率
   • 缓和 CPU 的高速性与 IO 设备低速性之间的矛盾，以空间换时间

   例子：共享打印机

   打印机守护进程和 SPOOLing 打印目录

   1. 守护进程是唯一有特权使用打印机设备的进程
   2. 打印文件前，用户进程先产生完整的待输出文件，并存放在打印目录下
   3. 打印机空闲时，启动守护进程，打印待输出文件

# 单元 5 文件管理

# 文件系统及其功能

主要目的：实现对文件的按名存取

同一个文件必须从逻辑文件和物理文件两个侧面来观察它

1. 对于用户，需要并遵守文件系统的规则来定义文件信息的逻辑结构，由文件系统提供按名存取方式来实现对文件信息的存储和检索。
2. 对于系统，必须采用特定数据结构和有效算法实现文件的逻辑结构到存储结构的映射，实现对文件存储空间和文件信息的管理，提供多种存取方法

# 文件的逻辑结构

# 逻辑文件

独立于物理环境的，用户概念中的抽象信息组织方式是文件的逻辑结构，用户能观察到的，并加以处理的数据集合构成逻辑文件

1. 流式文件
   • 无结构文件，指文件内的数据不再组成记录，只是由一串依次的字节组成的信息流序列，称为字节流文件
   • 这种文件常常按长度来读取所需信息，也可以用插入的特殊字符作为分界，使用读写指针访问
   • Linux 系统只提供流式文件
2. 记录式文件
   • 记录式文件是一种有结构的文件，它是若干逻辑记录信息所组成的记录流文件
     1. 逻辑记录是文件中按信息在逻辑上的独立含义所划分的信息单位
     2. 每个职工的工资信息是一个逻辑记录；
     3. 整个单位职工的工资信息便组成了该单位工资信息的记录式文件
   • 逻辑记录是文件内独立的最小信息单位，文件记录位置代替字节位置。
   • 记录是文件常用的记录组织和使用方法
     1. 记录式顺序文件：文件的记录顺序生成并被顺序访问。
     2. 记录式索引文件：文件使用索引表，表项包含记录键和索引指针，记录键由应用程序确定，而索引文件便指向相应记录。

# 物理结构

文件的物理结构和组织是指逻辑文件在物理存储空间中的存放方法和组织关系。

此时文件看做物理文件，即相关物理块的集合。文件的存储结构涉及块的划分、记录的排列、索引的组织、信息的搜索等许多问题

1. 顺序文件

   • 将一个文件中逻辑上连续的信息存放到存储介质的依次相邻的块中便形成顺序结构，这类文件叫顺序文件，又称连续文件

2. 连接文件

   • 使用连接字 (指针) 来表示文件中各条记录之间的关系

3. 直接文件、散列文件或哈希文件

   • 在直接存取存储设备上，利用哈希法将记录的关键字与其地址之间建立某种对应关系，以便实现快速存取的文件

4. 索引文件

   • 索引文件为每个文件建立了一张索引表，索引表记录方式有多种：
     1. 记录组成文件的磁盘块号，适用于流式文件。
     2. 所以表项包含记录键及其磁盘块号，适用于记录式文件。

# 存取方法

文件存取方法在某种程度上依赖于文件的物理结构

1. 顺序存取
   • 按记录顺序进行读 / 写操作的存取方法称顺序存取
   • 磁带机是最常用的一种顺序存取存储设备，它具有存储容量大、稳定可靠、卷可装卸和便于保存等优点，广泛用作存档
   • 光盘也是一种顺序存取存储设备，光盘上的磁道不是同心圆，而是螺旋形的，本质的线性的。
2. 随机存取（直接存取）
   • 可以非顺序地从文件中的任何位置存取文件内容
   • 要求快速地以任意次序直接读写某个记录
   • 磁盘文件
3. 索引存取
   • 基于索引文件的索引存取方法
   • 文件的记录不按位置而是按其记录名和记录键来编址

# 文件操作

# 文件的创建 create

int fd;           // 创建成功后系统返回的文件描述符

int mode;         //mode 是文件所具有的权限

char *filenamep;  // 指向要创建的文件路径名的字符串指针

fd = create(filenamep, mode);

# 文件的删除

unlink(filenamep)

# 文件的打开 open

int fd, mode;

char * filenamep;

fd = open(filenamep, mode);

输入是含路径的文件名

→→ 依据层次式目录结构解释与检索

→→ 匹配文件名并读取目录项

→→ 提取 inode 号

→→ 按号定位，在 inode 区读取 inode 数据结构 (主存活动 inode)

→→ 输出是返回文件描述符（字），即 file descriptor（成功打开文件，则会返回一个大于 0 的文件描述符；如果打开文件失败，则会返回 - 1）

# 文件的关闭 close

int fd;

close(fd);

# 文件的读取 read

int nr;     // 系统调用后实际读入的字节数

int fd;     // 文件描述符

int count;  // 要求传送的字符

char buf[]; // 应该输入的用户数据区的首地址

nr = read(fd, buf, count);

# 文件的写 write

int nw;     // 系统调用后实际写入的字节数

int fd;     // 文件描述符

int count;  // 要求传送的字符

char buf[]; // 数据传送的源地址

nw = write(fd, buf, count);

# 文件的随机存取

long offset;      // 当前的 offset

int whence;       // 

int fd;           // 指向一个以读或写方式打开的文档

lseek(fd, offset, whence);

文件描述字 fd 必须指向一个用读或写方式打开的文件

1. 当 whence 是 0 时，则 f_offset 被置为 offset，
2. 当 whence 是 1 时，则 f_offset 被置为文件当前位置加上 offset。

# 文件目录

文件目录是实现文件的按名存取的关键数据结构

# linux

linux 基本目录项：inode = 文件名 + inode 号

嵌入在 inode 中的索引地址表不可以太大

1. 文件较小使用直接地址 (直接索引)
2. 文件较大使用间接索引

f_count 和 i_count 分别反映进程动态地共享一个文件的两种方式

1. f_count 反映不同进程通过同一个系统打开文件表项共享一个文件的情况；
2. i_count 反映不同进程通过不同系统打开文件表项共享一个文件的情况。

# 多级层次目录结构

易于规定不同层次或子树中文件的不同存取权限，便于文件的保护、保密和共共享

为了解决不同用户文件 “命名冲突” 的问题，通常在文件系统中采用多级目录。

# 单元 6 并行

# 临界区

临界资源：互斥共享变量所代表的资源，即一次只能被一个进程使用的资源

1. 举例：火车上的卫生间就是一种互斥使用的共享资源
2. 使用共享变量代表共享资源

临界区 (critical section)：并发进程中与互斥共享变量相关的程序段，与同一变量有关的临界区分散在各进程的程序段中，而各进程的执行速度不可预见

临界区：每个进程中访问临界资源的那段代码称为临界区。

# 信号量

P(s)：

1. 将信号量 s 减去 1，若结果小于 0，则调用 P (s) 的进程被置成等待信号量 s 的状态
2. 负数的绝对值就是等待的进程的个数

V (s)：将信号量 s 加 1，若结果不大于 0，则释放 (唤醒) 一个等待信号量 s 的进程，使其转换为就绪态

# 进程通信（信息传递）

当进程互相交互时，必须满足两个基本要求：同步和通信

# 进程直接通信

• 对称直接寻址，发送进程和接收进程必须命名对方以便通信

• 非对称直接寻址，只要发送者命名接收者，而接收者不需要命名发送者

  • receive(id, message) 接收来自任何进程的消息，变量 id 置成与其通信的进程名称

# 进程间接通信

发送或者接收信件通过一个信箱来进行，该信箱有唯一标识符

消息不是直接从发送者发送到接收者，而是发送到由临时保存这些消息的队列组成的一个共享数据结构，这些队列通常成为信箱 (mailbox)

# 管道和套接字

管道和套接字都是基于信箱的消息传递方式的一种变体

# 死锁

不仅与系统拥有的资源数量有关，而且与资源分配策略，进程对资源的使用要求以及并发进程的推进顺序有关

# 死锁产生的四个必要条件

1. 互斥条件：进程应互斥使用资源，任一时刻一个资源仅为一个进程独占
2. 占有和等待条件：一个进程请求资源得不到满足而等待时，不释放已占有的资源
3. 不剥夺条件：任一进程不能从另一进程那里抢夺资源
4. 循环等待条件：存在一个循环等待链，每一个进程分别等待它前一个进程所持有的资源
5. 前三个是死锁存在的必要条件，但不是充分条件，第四个条件是前三个条件同时存在时所产生的结果。

# 死锁防止

• 破坏互斥条件：把独占型资源改造成共享性资源
• 破坏占有和等待条件：
  • 静态分配是指进程在执行中不再申请资源，就不会出现占有某些资源再等待另一些资源的情况。
  • 所有并发执行的进程要求的资源总和不超过系统拥有的资源数
• 破坏不剥夺条件
  • 采用剥夺式调度方法
• 破坏循环等待条件
  • 层次分配策略
    • 一个进程得到某一层的一个资源后，它只能再申请在较高层的资源
    • 当一个进程要释放某层的一个资源时，必须先释放所占用的较高层的资源
    • 当一个进程获得了某一层的一个资源后，它想再申请该层中的另一个资源，那么，必须先释放该层中的已占资源
  • 按序分配策略
    • 把系统的所有资源排一个顺序，例如，系统若共有 n 个进程，共有 m 个资源，用 ri 表示第 i 个资源，于是这 m 个资源是：r1,r2,...,rm
    • 规定如果进程不得在占用资源 ri (1≤i≤m) 后再申请 rj (j<i)。不难证明，按这种策略分配资源时系统不会发生死锁。

# 死锁避免

把资源分配给申请者会产生死锁的话，则拒绝分配，否则接收申请，为它分配资源

• 银行家算法（todo）

# 死锁检测与恢复

• 检测

  • 可设置两张表格来记录进程使用资源的情况

    1. 等待资源表记录每个被阻塞进程等待的资源
    2. 占用资源表记录每个进程占有的资源

    如果出现循环等待，则出现了死锁

  • 资源分配图

    看看这个理解理解：https://blog.csdn.net/qq_39328436/article/details/111123779

    • 每个资源用一个方框表示

    • 方框中的黑圆点表示此资源类中的各个资源

    • 每个进程用一个圆圈表示

    • 有向边表示进程申请资源和资源被分配情况

      如果进程 - 资源分配图中无环路，此时系统没有发生死锁。

      如果进程 - 资源分配图中有环路，且每个资源都只有一个资源则发生死锁。

      如果进程 - 资源分配图中有环路，且所涉及资源有多个资源，则未必发生死锁。可以通过消去法来判断，消去既不阻塞其他进程又与其他进程相关的进程的所有请求边和分配边，得到一个孤立点。接着将等待资源的进程分配后再次消去，如果最后所有的进程都成为孤立点则是无死锁的，图是可完全简化的，否则图是不可以完全简化的。

  • 死锁定理

    • 系统为死锁状态的充分条件是：当且仅当该状态的进程 - 资源分配图是不可完全简化的。该充分条件称为死锁定理

• 恢复

  • 资源剥夺法
  • 进程回退法
  • 进程撤销法
  • 系统重启法

# 并发

# Bernstein 条件

并发进程的无关性是进程的执行与时间无关的一个充分条件

# peterson 算法

举旗子，贴上对方的标签，如果对方举起且门上是对方的标签，则等待，否则进入

# 实现临界区管理的硬件设施

1. 关中断
2. 测试并建立指令
3. 对换指令

# 操作系统中并发问题解决方案的知识框架

# 大题

1. 多道程序设计

2. CPU 调度算法

   周转时间：作业结束时间 - 作业开始时间

   提交给系统开始到执行完成获得结果为止的这段时间间隔称周转时间，应该使周转时间或平均周转时间尽可能短

   响应比：（等待时间 + 期待时间）/ 期待时间

   1. FCFS (先来先服务) 非抢占
      • 一个短进程可能不得不等待很长时间才能获得执行
      • 偏袒计算为主的进程
        • I/O 多的进程不得不等待计算为主的进程做完
   2. RR (时间片轮转) 抢占 Round-Robin
      • 基于时钟做抢占式调度
      • 以一个周期性间隔产生时钟中断，当中断发生时，当前正在运行的进程被置于就绪队列中，然后基于 FCFS 策略选择下一个就绪进程运行
      • 延长短进程的等待时间
   3. SPN (最短进程优先) Shortest process
      • 非抢占，真正操作系统没有办法使用
      • 选择所需处理时间最短的进程
      • 短进程将会越过长进程，优先获得调度
   4. SRT (最短剩余时间优先) Shortest Remaining Time
      • 抢占，真正操作系统没有办法使用
      • 调度器总是选择预期剩余时间更短的进程，当一个新进程加入就绪队列，他可能比当前运行的进程具有更短的剩余时间，只要该新进就绪，调度器就可能抢占当前正在运行的进程
   5. HRRF (最高响应比优先) Highest Response Ratio Next
      • 非抢占，真正操作系统没有办法使用
   6. Feedback (多级反馈调度) 抢占
      • 建立多个不同优先级的就绪进程队列
      • 多个就绪进程队列之间按照优先数调度
      • 高优先级的就绪进程，分配的时间片短
      • 单个就绪进程队列中的进程的优先数和时间片相同，按照先来先服务算法调度
      • 2ⁱ 的 i 是从 0 开始的，也就是最高优先级队列的时间片为 1

   RR, q = 4 时答案有问题，应为 ABBBBCDDDDBBBBDDDDBD

3. 死锁避免银行家算法 ，死锁检测

   做题思路：

   1. 试探性地将 available 的资源分配给某个进程，满足它的 Claim - Allocation 的需求，进程结束后，归还所拥有的 Allocation ，系统未分配的资源增加，可分配资源为 available + allocation ，循环此过程，直至所有进程都被满足
   2. 否则，系统将处于不安全状态

4. 连续分配，分区分配：适配算法，伙伴系统

   1. 可变分区存储

      最先适应分配算法：

      1. 最先适应就是从上向下查找，找到第一块区域放进去，将剩下的区域分割后仍作为空闲区。
      2. 有利于大作业装入，但也使得内存低地址和高地址两端的分区利用不均衡，回收分区麻烦。

      邻近适应分配算法：

      1. 从上次查找结束的地方开始执行最先适应分配算法
      2. 缩短平均查找时间，且存储空间利用率更均衡，不会使得小空闲区集中在内存一侧

      最优适应分配算法：

      1. 每次都是分配最接近需要使用大小的部分，会生成很多很小的内存内零头。
      2. 通常会将空闲区按照长度递增顺序排列，等同于最先适应分配算法，查找时间最长

      最坏适应分配算法：

      1. 每次都是挑选最大的一块区域进行分配
      2. 有利于中小型作业。
      3. 可把空闲区按长度递减顺序排列，等同于最先适应分配算法。

      快速适应分配算法：课本补充

      1. 为经常用到的长度的空闲区设立单独的空闲区链表，查找非常快速
      2. 归还内存空间时和邻近空闲区的合并复杂且耗时。

      最常用的是最先适应分配算法，其次是邻近适应分配算法和最优适应分配算法

5. 地址转换计算：分页管理方式；分段管理方式。

   1. 分页管理

      逻辑地址 = 页号 + 页面偏移

      物理地址 = 页架号（页框号） + 单元号（页内偏移)

      <img src="https://quasdo.oss-cn-hangzhou.aliyuncs.com/img/image-20230618102557678.png" alt="image-20230618102557678" style="zoom:25%;" />

   2. 分段管理

      逻辑地址 = 段号 + 段内偏移

      <img src="https://quasdo.oss-cn-hangzhou.aliyuncs.com/img/image-20230618102527564.png" alt="image-20230618102527564" style="zoom: 25%;" />

   3. 段页式管理

      逻辑地址 = 段号 + 页号 + 单元号

      <img src="https://quasdo.oss-cn-hangzhou.aliyuncs.com/img/image-20230618103033633.png" alt="image-20230618103033633" style="zoom: 15%;" />

6. 页面置换算法

   1. OPT 页面调度算法（Belady 算法）

      当要调入新页面时，首先淘汰以后不再访问的页，然后选择距现在最长时间后再访问的页。

   2. 先进先出页面调度算法 FIFO-Belady 异常

      首先淘汰最先调入主存的那一页，或者说主存驻留时间最长的那一页 (常驻的除外)

   3. 最近最少用 LRU-Least Recently Used

      淘汰最近一段时间较久未被访问的那一页，即那些刚被使用过的页面，可以马上还要被使用到。

   4. 最不常用 LFU-Least Frequently Used

   5. 时钟 CLOCK

      采用循环队列机制构造页面队列，形成了一个类似钟表面的环形表，队列指针则相当于钟表面上的表针，指向可能要淘汰的页

7. 抖动现象，工作集（不考）

   1. MIN

      进程在时刻 t 访问某页面，如果该页面不在主存中，导致一次缺页，把该页面装入一个空闲页框

   2. 工作集

      向前看

      指 "在某一段时间间隔内进程运行所需访问的页面集合"，W (t，Δ) 表示在时刻 t-Δ 到时刻 t 之间 ( (t-Δ，t)) 所访问的页面集合，进程在时刻 t 的工作集

8. 磁盘调度算法

   1. 先来先服务 FCFS

   2. 最短查找时间优先 (最小短距离法) SSTF，Shortest Service Time First

   3. 扫描算法 SCAN

      向一个方向，碰壁折返

   4. 电梯调度 LOOK

      不碰壁返回

   5. C-LOOK

      始终沿同一方向

9. 文件系统的计算

   1. 位示图

      它将文件存储器的存储空间建立一张位示图，用以反映整个盘空间的分配情况。

      磁盘空间通常使用固定大小的块，可方便地用位示图管理，用若干字节构成一张位示图，其中每一字位对应一个物理块，字位的次序与块的相对次序一致，字位为‘1’表示相应块已占用，字位为‘0’表示该块空闲。

   2. 空白文件目录

      这种方法将盘空间的一个未分配区域称为一个空白文件，系统为所有的空白文件建立一个目录，每个空白文件在这个目录中建立一个表目。

   3. 空白块链：

      这种方法将盘上的所有空白块用链接指针或索引结构组织成一个空白文件。

   4. Linux 文件管理

      1. 直接地址索引
      2. 间接地址索引

10. PV 操作

11. 管程

、

分区分配：

1. 静态分配：进程运行前申请

   实现简单，能够防止系统发生死锁，

   但会降低设备利用率

2. 动态分配：进程随用随申请

   提高设备利用率

# 简答

1. 试述系统调用的定义、实现原理，陷阱机制和绘制系统调用的处理过程，并阐述系统调用的处理逻辑

   1. 定义：操作系统实现的完成某种特定功能的过程，为所有运行程序提供访问操作系统的接口

   2. 实现原理：

      1. 编写系统调用服务例程；
      2. 设计系统调用入口地址表，每个入口地址都指向一个系统调用的服务例程，有些包含系统调用自带参数的个数；
      3. 开辟现场保护区，以保存发生系统调用时应用程序的处理器现场

   3. 陷阱机制：操作系统实现系统调用功能的机制称为系统陷阱，由于系统调用而引起处理器中断的机器指令称为陷入指令，在用户态下执行时会由用户态转换到内核态

   4. 处理逻辑：

      1. 应用程序执行系统调用，产生中断转向内核态，进入陷阱处理程序；
      2. 按功能号查询入口地址表，并转至对应服务例程执行；
      3. 完成后退出中断，返回应用程序断点继续运行

2. 试写出进程映像包括哪些组成部分

   程序块、数据块、核心栈、用户栈、进程控制块

   <img src="https://quasdo.oss-cn-hangzhou.aliyuncs.com/img/image-20230620234550456.png" alt="image-20230620234550456" style="zoom: 25%;" />

3. 试述操作系统中三个最基础的抽象，并回答为什么要引入它们

   1. 进程抽象：对正在运行的程序在处理器上操作的状态集的抽象
   2. 虚存抽象：对内存的抽象，使用虚拟地址引用物理存储单元
   3. 文件抽象：对设备的抽象，按名存取
   4. 原因：防止硬件资源被应用程序滥用，屏蔽复杂的硬件资源操作细节，为应用程序提供使用硬
      件资源的简单且一致的方法

4. 简述 IO 软件的四层结构

5. 简述虚存分页的原理，并画出流程图
   原理：

   1. 主存被划分成大小固定相等的块，每个进程也被分成同样大小的块；
   2. 进程中称为页的块可以指定到内存中称为页框或者页框的可用块；
   3. 操作系统为每个进程维护一个页表，给出该进程的每一页对应的页框的位置

   <img src="https://quasdo.oss-cn-hangzhou.aliyuncs.com/img/image-20230621004122948.png" alt="image-20230621004122948" style="zoom:33%;" />

6. create 系统调用的参数，返回值是什么，实现原理是什么

   实现原理：

   1. 为新文件分配索引节点和活动索引节点，并把索引节点编号与文件分量名组成新目录项，记到目录中
   2. 在新文件所对应的活动索引节点中设置初值，如置存取权限 i_mode，连接计数 i_nlink 等
   3. 分配打开文件表项和系统打开文件表项，并为表项分配初值
   4. 通过指针建立表项与活动索引节点间的联系。
   5. 把文件描述字，即用户打开文件表中对应的表项序号返回给调用者

7. open 系统调用的参数，返回值是什么，实现原理是什么

   参数：文件权限，文件路径名的字符串

   返回值：文件描述符

   实现原理：

   1. 检索目录，把它的外存索引节点复制到活动索引节点中来
   2. 根据参数 mode 核对权限，如果非法，则打开失败
   3. 合法时，为文件分配用户打开文件表项和系统打开文件表项，并为表项分配初值
   4. 通过指针建立表项与活动索引节点间的联系。
   5. 把文件描述字，即用户打开文件表中对应的表项序号返回给调用者

8. 结合进程状态转换模型，解释操作系统是如何中断驱动的

   运行态：进程占用处理器运行

   就绪态：进程具备运行条件等待处理器运行

   等待态：又称阻塞态、睡眠态，进程由于等待资源、输入输出、信号等而不具备运行条件

   当操作系统遇到中断事件时，如键盘输入、I/O 操作完成时，它会将当前正在运行的进程切换到阻塞状态，并将 CPU 分配给一个已经处于就绪状态的进程。如果没有就绪状态的进程，则操作系统会将 CPU 保留在空闲状态，等待下一个进程变为就绪状态。
   当事件完成后，操作系统会将被阻塞的进程重新切换到就绪状态，以便再次执行。在这个过程中，进程状态转换图的状态如下：

   1. 从运行状态转换到阻塞状态：当操作系统接收到中断请求时，正在运行的进程会被中断和放入
      阻塞状态。
   2. 从阻塞状态转换到就绪状态：当操作系统完成中断请求时，进程将被重新放回就绪状态，等待
      操作系统重新分配 CPU 时间。
      通过这种方式，操作系统可以实现中断驱动的机制，以处理来自外部设备的事件或请求。该机制使
      得操作系统可以在不阻塞当前进程的情况下同时响应多个事件，并实现了 CPU 的高效利用。

9. 画多级反馈队列的模型图、阐述多级反馈的原理，比 RR 的优点、缺陷以及改进方法

   原理：

   • 建立多个不同优先级的就绪进程队列：
   • 多个就绪进程队列之间按照优先数调度
   • 单个就绪进程队列中的进程的优先数和时间片相同，按照先来先服务算法调度

   比 RR 的优点：优先级课调整、时间片大小可调整、适应性强、响应时间短

   缺陷：长时间运行的进程，可能会一直在较低的优先级队列中等待；算法复杂度高

   改进方法：引入抢占式调度、加强进程优先级管理、动态调整时间片大小

10. 请画出经典的三进程状态模型及其状态转换图并解释状态之间各类转换关系的含义

    运行态 - 等待态：等待资源、IO、信号量

    等待态 - 就绪态：资源满足、IO 结束、信号量完成

    就绪态 - 运行态：处理器空闲时选择高优先权进程抢占

    运行态 - 就绪态：运行时间片到，被高优先权进程抢占

11. 请画出经典的五进程状态模型及其状态转换图并解释状态之间各类转换关系的含义

12. 请画出经典的七进程状态模型及其状态转换图并解释状态之间各类转换关系的含义

13. Spooling 的设计思想，并画出系统组织结构图

• 将独占设备改成共享设备的技术
• 采用预输入、缓输出和井管理技术
• 通过创建守护进程和特殊目录解决独占型设备的空占问题
• 缓和 CPU 的高速性与 IO 设备低速性之间的矛盾，以空间换时间

<img src="https://quasdo.oss-cn-hangzhou.aliyuncs.com/img/image-20230616154208873.png" alt="image-20230616154208873" style="zoom: 15%;" />

# 选择题补充（除慕课）

实际物理地址 = (段寄存器 << 4) + 偏移地址

访问到的是实地址。.

GDT LDT IDT（中断描述符表）