【计算机体系知识】操作系统笔记（持续更新）

传送门

由于操作系统知识太多，再加上我总结的比较细，所以一篇放不下，拆分成了多篇文章。

操作系统笔记——概述、进程、并发控制
操作系统笔记——储存器管理、文件系统、设备管理
操作系统笔记——Linux系统实例分析、Windows系统实例分析
北理工操作系统实验合集 | API解读与例子
北京理工大学操作系统复习——习题+知识点
资料包百度云下载，含2022年真题一套，提取码cyyy

概述

入门书籍与视频推荐

建议先自己看一看《计算机是怎么跑起来的》，操作系统和计算机网络都是先开发出系统，后出现的理论，所以建议从实践入手。我认为一门学科要先把他朴素的思想掌握，然后再深挖，否则你一上来就看现代操作系统，速度会很慢。

16分钟了解计算机组成以及启动

1. 指令是如何运行的；
2. 计算机的基本构成；
3. 计算机是如何启动的；
4. x86汇编的准备工作。

45分钟更详细的操作系统启动视频

1. 计算机系统的工作原理；
2. 电源开关按下后，系统启动的过程；

定义操作系统

计算机系统层次：

1. 硬件就是裸机，人要想操作就得用0101二进制码。
2. 操作系统，将对硬件的二进制指令封装起来，构成操作系统API
3. 系统应用建立在操作系统之上，是一些底层的应用，比如链接网络之类的
4. 应用程序建立在系统应用之上，编程语言可以调用系统应用或者操作系统底层，实现应用级操作。

操作系统实际上是建立在裸机之上的一种大型底层软件，其重要职责有两个方向：

1. 向下，以最佳的策略调度软硬件资源，提高计算机工作效率。
2. 向上，对用户来说，提供系统接口，使得用户对硬件的操作更加便利。

操作系统设计目标与其目的匹配，从上到下分为三方面：

1. 易用。对用户来说，要好用。
2. 易维护。对操作系统自己来说，要可扩展，易于维护。
3. 高效。对系统来说，效率要高。

综上，这是一个权衡的过程，想一想python，好用是好用，但是效率低，所以好用和效率之间是有矛盾的，易于维护和效率之间也是有矛盾的。

操作系统的形成

顺序处理（无操作系统）

这个时候的代码就是纸带，打不打孔代表0和1。一条纸带就是一条代码。

除了程序，一切都是人工，计算机资源的调度也是人工，有一个管理者。
每一个上机的人可以理解为一个任务/作业。
全是缺点。

批处理系统

单通道批处理系统

这个时候出来一个监控程序，用来替代管理者，接收程序。

操作员把任务成批地放到输入设备上，监控程序逐个执行。很明显这仍然是一种单线程的串行的执行方式，缩短了CPU等待作业输入/撤出的时间，效率比以前只高了一点点，仅仅是省下了等待时间以及管理人力。

为什么说他还有很大的提升空间呢？看这个图，串行操作导致用户程序的输入受阻，用户需要等前一个任务干完才能再次输入。而且不仅要CPU处理完，还要对外设IO完成，执行完全部流程才行，在IO的时候，CPU还在摸鱼，浪费时间。

多通道批处理系统

多通道的目标是为了让CPU保持忙碌状态。关键在于IO的时候，让CPU继续忙碌。

多通道批处理系统实现了不同资源之间的并行。如果多个任务分别使用不同的资源，基本可以实现并行，但是如果多个任务使用同一资源，那就和串行一样。

既然IO不需要CPU，那就把IO和CPU分离，用一个通道来执行IO操作，CPU告诉通道去执行IO，然后通道负责在主存和外设之间IO，同一时刻，CPU继续处理其他任务。通道本质上是一个处理器，相当于一个简化版的CPU，它具有一些简单的控制功能，因此能够自动执行CPU的命令。（详见第二篇笔记中的IO控制部分）

可以这么理解，CPU原来是事事亲力亲为，通道技术的出现，让CPU把一些任务（比如IO）分发给别的组件，腾出时间处理任务。通道之于CPU，就好比将军之于皇帝。

这里实现的并行仅仅是CPU处理和IO之间的并行，而不同任务之间在CPU上仍然是串行。表面上人们看到任务一股脑丢进去了，实际上还是一个处理完再处理下一个。

看下面这个图，CPU在程序A,B，操作系统调度这三者之间，同一时间只能选择1个来做。虽然CPU内部不能并行，但是已经实现与IO的并行。

任务A在进行IO的时候，CPU没有等着IO结束，而是直接运行程序B，当B程序IO的时候，没程序需要处理，这才休息了一会，等A程序IO完成，又开始处理A，处理完A以后，恰好B程序IO完了，又处理B程序（此时如果B没有IO完，又没有新的程序，那CPU还可以摸鱼）

下图给出一些指标，可以用一个实际问题来计算一下：

1. 资源利用率。这个指标是针对某个资源计算的，比如CPU，比如打印机，比如磁盘。资源一直在运转就是100%利用率
2. 吞吐量。完成任务的速度
3. 周转时间。一个任务在系统内的总时间。

这里将CPU调度的时间忽略，三个任务的资源互不重叠，所以并行处理。

首先计算出总时间。分别是30min和15min

然后看吞吐量。吞吐任务是3个job，除以时间得出吞吐量。所谓的吞吐量，实际上是单位时间完成任务数。

周转时间。因为任务是批量放入的，计算如下：

$$\begin{gathered} 多通道=\frac{1+15+10}{3}=10 \\ 单通道=\frac{(5)+(5+15)+(5+15+10)}{3}=\frac{55}{3}\approx 18 \end{gathered}$$

至于利用率，就是某一资源占用时间/总时间就可以，很明显，在利用不同资源的情况下，多通道系统的资源利用率是很高的。

批处理系统的特点：

1. 多道程序。“批”字代表多道
2. 并行。宏观上
3. 串行。微观上

批处理系统的缺点在于，任务只要丢进去，控制权就和用户无关了。万一碰上拥挤的情况，你也不知道里面是什么情况。
本质上，就是没有合理的任务调度机制，导致任务平均周转时间较长。

分时系统

批处理系统是由管理员独占的。这不符合多用户的需求，于是产生了面向多用户的分时系统。

面向多用户，自然就有一套资源调度方法，从多通道批处理到分时系统的核心进步就是分时调度策略。

系统把计算资源按之间切片，供给不同用户使用，即使用户A的任务还没有完成，只要用户A的时间片消耗完了，就暂停A的任务，去执行其他用户的任务，实现一种多用户之间的伪“并行”。

分时系统特点如下：

1. 同时性。多用户同时使用。
2. 独立性。这个独立是伪独立，只是感觉不到其他用户，并不是独占CPU。
3. 交互性。虽然不独占CPU，但是独占一个终端，可以理解为发送任务就调用时间片资源。
4. 及时性。相对及时，比批处理系统快，比实时系统慢。这是因为不用等前一个任务整个完成，只需要等他的时间片过了就好，但是一个时间片还是要等的。

实时系统

分时系统中多用户的级别是平等的，时间分配也是平均的。但是有一些情况需要对重要的事情做出立即响应，这就是实时系统。

实时系统相对于分时系统，核心改进是优先级加入。现代操作系统都是接近于实时系统的。

实时系统特性如下：

1. 实时性：实际任务并不是均等地位的，所以要加上优先级，如果有更重要的任务来了，当前任务即刻暂停，资源被抢占，实时响应。
2. 确定性：优先级是确定的，所以执行顺序也是确定的，可以基本计算出响应时间，这样就可以预测一个任务消耗的时间，如果是一个最重要的任务，那一定是实时执行的，就不可能出现拥堵。
3. 可靠性：这种系统一般都是用于重要的场景，不能耽误的场景，所以通常有备用机，体现出可靠性。

嵌入式系统

分时系统和实时系统有点臃肿，嵌入式硬件放不下，于是有了嵌入式系统。

嵌入式系统的核心改进在于可裁剪，可以理解为一种定制化。

操作系统类型总结

由前文可知，有三种基本的操作系统类型：

1. 批处理系统：多任务，宏观并行，微观串行
2. 分时系统：同时性（更强的并行性），独立性，交互性，及时性
3. 实时系统：实时性（优先级并行），确定性，可靠性

批处理系统广泛用于多任务，批量计算场景，分时系统用于多用户场景，实时系统用于要求快速响应，高可靠性的场景。
而现在的通用操作系统兼顾这三种基本类型的特点。

操作系统的功能，服务，特性

功能

总的来说

1. 向上，为用户提供简洁易用的系统接口，让用户更好地操作硬件。
2. 向下，管理计算机的软硬件资源，提高系统运行的效率。

具体有4个方面，这四个方面就是操作系统学习的几个章节目录。其实向上和向下并不是完全分割的，比如文件管理，既可以提高效率，也给用户提供了简洁易用的接口。：

为了实现上面的功能，要重点关注这几个表（数据结构），其和操作系统的功能一一对应，储存了系统的资源状态信息。

服务（API）

服务可以理解为API。前面开始介绍了4大功能，如果将这4大功能理解为向下的功能，那这里列出的服务就是操作系统面向用户的API。太多了，直接略过就好，总之就都是用户可以接触到的接口。

特性

1. 并发性。程序之间宏观并发
2. 共享性。程序之间资源共享。并发和共享是离不开的，在多通道系统中，资源可以共享才能实现资源的并行，宏观的并行。
3. 虚拟性。把一个实物资源变成若干个逻辑上虚拟资源，支撑了多用户的使用。比如虚拟机，虚拟打印机。
4. 异步性（随机性）。最后的异步性其实是一个缺点，并发与资源之间的制约导致进程之间的调度不完全由管理员和用户控制。

操作系统的发展

1. 个人计算机操作系统：
   • 单用户单任务MS-DOS；
   • 单用户多任务Windows；
   • 多用户多任务Unix，Linux
2. 多处理机操作系统：
   • 非对称多处理（ASMP），多个CPU是主从关系，一个CPU负责操作系统与调度，其他负责任务处理；
   • 对称多处理（SMP），多个CPU是平等的，是现在的主流方法，能够充分共享资源，提高效率。
3. 网络操作系统。 计算机网络将不同的计算机联系起来。这时一个计算机就可以使用其他计算机的资源了，其中一个重要的概念就是TCP/IP协议栈。网络操作系统有两种模式：
   • 客户/服务器模式，这种情况下服务器压力比较大；
   • 对等模式（Peer-to-peer），这就是大名鼎鼎的p2p，没有服务器和客户端的区别。所以p2p下载，可以提速，我的猜测就是多个用户分开下载，然后互相传输，服务器用户下发了1个文件的数据，就一次性分发给了n个用户，把传输负载分摊到用户身上。如果是服务器模式，那就得分发n次。
4. 分布式操作系统。可以理解为，将n个计算机通过网络连接成虚拟的单台主机。目前还没有一个大成的分布式操作系统，但是已经有基于软件框架的集群系统了，比如hadoop，就是典型的分布式框架，只要配置好网络，即使节点机器都各自有一个私有的操作系统，也可以成为集群。
5. 虚拟化和云计算。虚拟化可以理解为物理层和逻辑层的分离。物理层可以是m台机器，虚拟的逻辑层则是n台机器。虚拟化可以从操作系统层就开始虚拟化，也可以通过VmWare/virtual box这种建立在操作系统上的软件层开始虚拟化。而云计算是基于虚拟化技术的云端服务。
   

用户与操作系统的接口

图形接口

封装的最好的是图形接口，这个接口是一个叫Explorer.exe的进程，Linux的话有KDE/GNOME接口。

命令行接口

其次是命令接口，一个shell就是一个进程，shell相当于命令解释程序。

核心态与系统调用接口

最底层的是系统调用。系统提供函数，函数进行系统调用，比如Linux/Unix POSIX API，Windows Win32 API。当然，系统调用的底层执行和普通库函数是不一样的，这涉及到CPU的运行状态。

CPU有用户态和核心态。用户态操作的是不太关键的组件，资源，而系统关键的资源都必须在核心态运行，保证安全。这两个状态之间的关键区别就在于核心态可以执行CPU指令集中的全部指令，包括特权指令。

系统调用属于关键任务，所以要把CPU切换到核心态。

这些切换涉及到安全问题，肯定不能由用户实现。用户到核心通过硬件实现，核心到用户通过内核程序实现。
这个硬件指的是硬件中断，中断可以简单理解为消息，用户态向内核发送一个中断，内核解析这个中断，经过判断后允许用户态执行系统调用，同时切换为核心态。

操作系统的运行方式

前面说到，中断是硬件级别的，听起来像是故障，但是却是正常的功能，起到传递消息的作用。操作系统不一定会马上处理中断，所以是异步事件。

异常由软件产生，即刻处理，且不能被屏蔽，是真正地故障。

操作系统的设计规范与结构设计

1. 单块式（整体式）内核：操作系统就是一个整体，通常是比较小的内核，比如DOS，比较简陋，也不会区分模块
   

2. 分层结构是最常见的。
   

3. 微内核将内核的不同功能拆分，移到用户空间。这样灵活，安全，但是拆分代表着要通信，通信成本会影响效率。
   

进程管理

进程的引入和概念

顺序与并发

1. 顺序执行，比如单通道批处理系统。
   • 封闭性。因为独占，所以是封闭的，不受外界影响
   • 可再现性。既然不受外界影响，那必然是结果每次相同，即可再现性
2. 并发时，资源共享，这就等同于引入外界影响。
   • 程序与CPU之间不再一一对应。说白了，就是多个程序可以宏观地在一个CPU上执行了，这是并发最大的意义。
   • 失去了封闭性和可再现性。在复杂场景下，不同程序的执行顺序，并发时不同的操作顺序，就可能引起结果的不同。
   • 程序之间会出现制约。再加上两个程序如果都需要一个资源，就会出现制约，又或者一个程序需要另一个程序处理出的结果，这又是制约关系。

进程的定义

进程没有特定的概念，大致上说，一个进程就相当于实际中的一个任务，具体到计算机，一个进程就对应一个程序。
拿前面那个编译来说，n个C语言编译任务就相当于n个进程。

进程可以说是为并发任务而专门创建的概念，主要功能就是区分不同的任务。进程有如下特性：

1. 动态性。因为任务有开始和结束，所以进程是动态的，要开始一个任务就创建，跑完就自动释放。
2. 独立性。因为任务本身就是独立的，所以进程之间也不应该互相干扰，因此系统以进程为单位调度资源。
3. 并发性。多进程一CPU。
4. 结构型。为了便于管理，每个进程都有一个PCB块，用于控制进程。

进程与程序

进程之于程序，好比执行之于规划。程序规定了该怎么做，进程负责具体的执行与协调。由此引出下列所有概念。

1. 进程是动态，暂时的的，程序是静态的，永久的。程序规定了该怎么做，进程负责具体的执行与协调
2. 进程是规划的具体化，所以进程不仅有程序（规划），还有数据和PCB（规划执行时的信息）
3. 进程和程序是多对多关系。一个程序可以多开，对应多个进程。程序可以调用程序，所以一个进程也可以对应多程序。

进程的描述：PCB、状态

进程的地址空间

进程看到的地址其实是虚拟地址，否则程序很容易把操作系统写坏了，所以操作系统内核中有虚实地址转换的功能。

一个进程可以有4G的虚拟地址空间，在虚拟地址中，地址也会有分类，比如用户和内核的地址就要分开，各种区也都要分开，这样做是为了防止区内数据溢出区域而互相覆盖，干扰。

具体的分布如下图，不必细看。低地址放代码，代码紧接着就是数据，数据完了是堆，高地址放栈，堆栈的生长方向相反，中间有一片共享区。

PCB

前面说了，进程由程序，数据，PCB组成，PCB控制整个进程。具体来说，PCB里储存进程的元数据。

PCB主要由如下信息构成：

1. 进程标识符。
2. 进程状态，调度，储存器管理的信息。比如进程状态（运行，阻塞等），优先级，程序的地址。
3. 进程的资源信息。进程打开的设备，文件。
4. CPU现场保护区。比如寄存器信息。

进程的五种状态（3+2）

进程的状态存在PCB里。

1. 运行态就是有CPU有资源，正在跑。
2. 阻塞态，占用了CPU，但缺少其他条件或者资源而卡顿，比如IO，信号，事件。
3. 就绪态与阻塞态相反，已经占用资源了，但是缺少CPU。

1. 就绪到运行。CPU如果空闲，就会从就绪态里进程里，找出一个来进行调度（激活），具体怎么个找法，就是调度策略了。
2. 运行到就绪。既然可以激活，那也可以进行休眠，比如有更高优先级任务来了，或者时间片消耗完毕，那就只能把运行态变成就绪态了。
3. 运行到阻塞。如果在进程执行的时候如果需要等待事件，进程就变成阻塞态，此时既然用不了CPU，CPU就会释放。
4. 阻塞到就绪。等事件给出响应，阻塞态就会重新变成就绪态，等待CPU的调度。

除了三种基本状态，还有两个额外状态：

1. 创建态。创建，无CPU无资源。如果进程处于就绪态，其实他已经占用了资源，所以就绪态进程数量肯定是被限制的，如果已经满了，进程就会停在创建态。
2. 终止态。终止态就是已经停了，但是资源还没回收，当资源彻底回收以后，进程就会被销毁，PCB也就不复存在了。

进程的组织

进程有这么多类型，自然就需要一套组织结构管理。

管理各种进程使用数组或者链表（队列）。链表还可以分类，比如就绪队列，阻塞队列。
队列内部可以排序，比如就绪队列可以按照调度排列。
队列还可以进一步分类，把阻塞进程按照不同原因拆分，比如等待磁盘I/O队列，等待磁带I/O队列等。

进程的控制：创建，撤销，阻塞，唤醒

进程控制包括进程的创建，销毁，状态的转换。进程控制是由操作系统内核实现的，是属于原语一级的操作，不能被中断。所谓原，就是指原子性，不可分割。

原语大致有这么几种：

1. 创建/撤销原语。对应进程的创建与销毁
2. 阻塞/唤醒原语。对应进程从运行态到阻塞态，以及从阻塞态到就绪态
3. 挂起/解挂原语。对应进程的主动暂停，继续。

创建/撤销原语

1. 第一步相当于分配元数据空间
2. 第二步是分配进程本身的空间，并且进行填充
3. 第三部是填充元数据空间
4. 前三部都是进程本身的信息，而第四部是让进程被一个更高级的模块管理

撤销其实就是销毁进程，基本是创建反过来执行一遍，逐步，递归地释放资源，最后删除PCB（撤销内部管理）并且从高级模块中撤销对这个进程的管理（撤销外部管理）。

阻塞/唤醒原语

阻塞/唤醒造成的影响是PCB内部状态改变+外部队列信息改变。

阻塞原语请求是进程发出的，由内核执行。
唤醒原语同样不是进程自己调用，有两个来源：

1. 如果是因为IO等资源问题，则从硬件层面进行中断处理，在中断处理中调用唤醒
2. 如果是等待另一个进程的事件，那就由发送事件的进程调用唤醒。

挂起/解挂原语

处理器调度——进程调度：分配给CPU某一进程（重点）

当进程数大于处理器数，就会产生竞争，这时就要调度。系统运行性能受调度的影响非常大。处理器的调度级别有三种级别，我们研究的是最底层的进程调度，专注于为进程分配处理器。

注意区分，处理器调度与进程调度是包含关系。

再次声明，注意区分，处理器调度与进程调度是包含关系。

进程调度的功能

进程的执行状态是存在PCB里的，进程调度的功能有三个：

1. 管理系统中各种进程的PCB块。
2. 选择进程进行CPU占领
3. 与CPU占领伴随的是上下文切换。

所谓上下文，就是把和程序相关的临时状态，临时信息都存了起来。

进程调度的方式

1. 非抢先方式（非剥夺）。以前没有进程调度，直接批处理。
2. 抢先方式（剥夺方式）。自从分时系统以及优先级算法出来以后，就都是抢占式的了，因为这样比较灵活，制定好优先级以后能兼顾重要程序的稳定优先与一般程序的效率。

进程调度的时机

进程调度的时机，简单来说，就两种情况：

1. 执行完了或者卡住了。进程完成，等待IO
2. 被调度了。比如分时系统中，时间用完了。又或者更高优先级的过来了，就会被切换到就绪态或者阻塞态。

用这个程序举例，其中计算的成本是很低的，但是IO的成本很高，所以有相当一部分时间，CPU是在等待IO的。所以在每一个循环中，CPU计算完等IO的时候，CPU就会切换到另一个进程中，等IO完再切回来。

int main(int argc, char* argv[])
{
	int i, to, *fp, sum=0;
	to=atoi(argv[i]);
	for(i=1;i<=to,i++)
	{
		sum=sum+i;
		fprintf(fp,”%d”,sum);	//CPU调度的时机
	}
}
1
2
3
4
5
6
7
8
9
10

经典进程调度算法

以上的调度时机只是给出简单思路，但是更多的是要具体到算法了。

方法很多，记起来，大致可以这么记：3是1和2的综合，6是4和5的综合。

1. 先来先服务（FCFS，First come First serve）。就是曾经的单通道批处理系统，缺点很明显，所有任务都是阻塞的，如果出现耗时操作，系统会卡很久。
2. 最短作业优先。就是对作业长短进行排序，对单通道批处理做出了一些优化。但是对长作业有点亏，本来就耗时，还要等，如果再有短作业不断插入进来，长作业就没法执行了，这种叫长作业饥饿状态。
3. 响应比高者优先。RP=1+$\frac{作业等待时间}{作业估计运行时间}$，RP大的先执行。直观看，等的越久，越应该放前面，耗时越短，越应该放前面。总的来说，是1，2算法的结合，缺点是计算量较大。
4. 优先级调度算法需要单独拿出来说。简单说就是将CPU分配给就绪队列中优先级最高的进程。
   - 静态优先级：在进程创建时确定的，运行时保持不变。通常赋予系统进程较高优先级（重要的）；赋予申请资源量少的进程较高优先级（不耗时的）。
   - 动态优先级：原优先级可随进程的推进而改变。根据进程占用CPU或等待CPU时间的长短动态调整。
5. 轮转法（RR，Round Robin）。进程地位是平等的，但是时间片长度需要考虑，太长了就失去了并行优势，太短了会增加调度开销。
6. 多级反馈队列轮转法。这是优先级+轮转法的结合。说白了就是，优先级算法中，一个优先级只对应一个进程，但是在这里，一个优先级对应一整个队列的进程。
   • 整体过程。多个队列，对应不同优先级。高优先级的队列先轮转，清空队列后再轮转低优先级。在每一个队列内部，进程地位平等，进行轮转。
   • 时间片长短问题。整体轮转过程中，为了防止低优先级进程饿死，分配给高优先级的时间片比较短（但是优先），低优先级的较长（虽然不容易轮到，但是一旦轮到就可以安稳执行完毕）。
   • 动态优先级。当然，优先级并不是一成不变的，具体的变化比较复杂。比如刚创建的默认放在高优先级，但是如果检测到占用时间过长或者卡IO了，就会降级。

实时系统比较特殊，调度算法特殊，略过。

线程的引入

为何引入线程

到这里已经不对劲了，从本质上来说，一个进程对应一个任务，但是一个任务本身也是有多个部分的，这几个部分可能是可以并行的，所以完全可以把一个进程再进行划分，这就是线程。

使用了多线程以后，读取，解码，播放被分配到了三个线程，并行处理，一片一片地播放，就不会卡顿，资源也利用的较好。

在线程这个概念出来之前，实现这种并发是通过多进程实现的。但是你想，进程对应程序，进程之间理论上是尽可能隔离的，这才有利于并发，而这三个进程的资源是共享的，所以用多进程实现并不是好方案。

线程的概念

线程是进程的一部分，是进程中指令执行流的最小单元，CPU调度的基本单位。

从物理层面说，线程之间是共享地址，共享资源的，而进程之间是隔离的。共享资源就不需要通信了，但是缺点就是一个线程崩了就都崩了（资源共享，用的资源都崩了，其他线程自然崩）。

在线程出现以后，进程就变成了资源分配单位，而具体的执行，处理器调度，是由线程负责的。

一个进程必然伴随一个主线程，只包含主线程的进程和原来的进程是一样的

一个线程控制块有如下信息：

1. 有一个唯一的标识符
2. 处理器相关信息。表示处理机状态和运行现场的一组寄存器。
3. 关联的进程和线程指针
4. 函数执行堆栈。两个堆栈，分别用于用户态和核心态调用时进行参数传递
5. 一个独立的程序计数器（与CPU指令有关）

进程和线程的比较

拥有的资源：

1. 进程拥有所有资源（独立的地址空间，用来存放若干代码段和数据段。拥有打开的文件，以及至少一个线程）
2. 线程之间都是用的进程里的资源，所以是共享的。
   一个线程内也拥有独立的资源，但是这些资源很少（指令流执行的必要资源，如寄存器和栈）

调度：

1. 进程调度需进行进程上下文的切换，开销大。
2. 同一进程内的线程切换，仅把线程拥有的一小部分资源变换了即可，效率高。

并发性：

引入线程后，系统的并发粒度就变细了。进程之间、进程内的多线程之间可并发执行。

安全性：

1. 多进程。资源隔离，安全性好
2. 多线程。资源共享，效率高，但是有崩盘风险。

系统的线程支持

用户级线程（多对一）

简单说，用户管理线程，系统只知道进程。

1. 用户管理线程，系统内核并不知道线程的存在。
2. 系统内核以进程为单位进行调度。用户级多线程对应核心级一个进程。
3. 一个线程阻塞，内核则判定其依附的进程也阻塞。

除了线程阻塞导致进程阻塞外，还有一个缺陷，因为内核不知道线程，所以不能做到进程间线程切换，要想解决这个，就必须要让内核知道线程的存在。

内核级线程（一对一）

可以看到，内核里多了线程表。有关线程的管理工作都由内核完成。应用程序通过系统调用来创建或撤销线程。

因此，一个线程的阻塞，不影响其他线程的执行。同时，进程间的线程切换也可以实现了。

Windows，Linux，多处理机系统都在用这种技术。

混合模型（多对多）

实际上，把线程切换交给系统会增大系统负担，用户级的线程切换就很方便。
我们之所以用系统级线程，只是因为要在进程间进行线程切换。

那么，完全可以这样：

1. 进程内线程切换：用户级
2. 进程间线程切换：内核级

这样既可最大化并行性，也可以最大限度的减小调度开销。

进程之间的并发控制

并发进程的关系

1. 间接制约，互斥关系。对资源的共享引起的互斥关系。进程之间本应该相互独立，但是因为使用的资源是共享的，比如两个进程都要用打印机，所以进程之间实际上是有制约的关系的。
2. 直接制约，同步关系。协作完成同一个任务引起的同步关系。一组协作进程要在某些同步点上相互等待发信息后才能继续运行。直接制约关系，同步关系。有时进程之间其实还是需要进行通信的。
3. 进程之间的前序关系。由于进程之间的互斥同步关系，使得进程之间具有了前序关系，这些关系决定了各个进程创建和终止的时间。

S：Sequence，顺序，P：Parallel，并行。

进程之间的低级通信

低级通信通过信号量通信，传输较少的信息。
IPC（InterProcess Communication）

进程之间的互斥

概念与原则

1. 共享资源：①慢速的硬设备，如打印机；②软件资源，如共享变量、共享文件和各种队列等。
2. 临界资源：是一种共享资源，但是一次仅允许一个进程使用
3. 临界区(critical section)：并发进程访问临界资源的那段必须互斥执行的程序。往往一大段代码中，只有一小部分代码是访问临界资源的，其实只有在执行这一小部分的时候才互斥，所以临界区指的是代码中的特殊区域。

并发进程进入临界区的原则：

1. 互斥使用；
2. 让权等待，等待的时候进入阻塞态
3. 有空让进，进程之间低位平等，来了就都有机会进入临界区
4. 有限等待，不能让等待区中的进程饿死

关中断

最简单的方法。在进程刚进入临界区时，立即禁止所有中断。

禁用中断，就无法进行进程的调度与切换（CPU只有在发生时钟中断或其它中断时才会进行进程切换），很明显，就算其他进程不进入临界区，也会被阻塞。

进一步说，禁用中断代表此时独占CPU，缺点如下：

1. 限制并发，效率低，其他进程只能用别的CPU。
2. 多CPU情况下，互斥进程还可以通过其他没有被关中断的CPU访问临界资源，封锁效果不太好
3. 不安全，如此关键的功能不应该让用户接触到。

testset

使用锁位变量W标记临界资源，即加锁的思路。

W=0，表示资源空闲可用；W=1，表示资源已被占用。当然，读取W的函数是不能被中断的，否则就乱套了，所以将这个函数制作成机器指令，这样就不会被中断了。

const int n=/*进程数 */
int w;
void p(int i){
  while(1){
    while(!testset(w));
    //临界区
    w=0;
    <remainder section>
}}
1
2
3
4
5
6
7
8
9

这段代码展示出testset的缺点：忙等。
就是每次访问临界区之前，会用while不断的询问，等待，但是while本身也是消耗资源的，浪费CPU资源。

所以应该把while循环等待变成信号机制，这样就不会浪费时间了。

进程之间的同步

信号量和P、V操作（重点）

信号量就是信号机制，卡住就阻塞，等另一个进程发来信号就会被唤醒。
因为是事件驱动的，所以信号量比testset更加高效。

信号量是一个特殊的变量。只能通过PV原语操作。
value：代表可用资源个数，如果电脑有3台打印机，有一个打印机被占用后，value就变成了2。直到变成0或者负的，代表不可用。

typedef struct{ 	//信号量的类型描述
      int value; //表示该类资源的可用数量
      struct process *list; //等待使用该类资源的进程排成队列的队列头指针。
   }semaphore, sem;
1
2
3
4

所以，PV信号的本质就是，设定可以同时共享一个资源资源的进程数的上限。

如果是1，就是互斥，k就代表最多k个。

PV原语

申请资源，如果没有就阻塞，然后加入到等待队列中

1. P：申请资源，对应先S-1，再判断是否为负，如果初始S为0（-1后为负）则会阻塞
2. V：释放资源，对应S+1，再判断是否为负，如果+1后还是负，则说明阻塞链表中还有进程，执行唤醒。V不会导致阻塞

void P (sem &s)
{  	
	s.value = s.value-1;   //表示申请一个资源（或通过信号量s接收消息）
    if (s.value < 0)
         { add this process to s.list;
            block( );
         } //资源用完，调用阻塞原语。“让权等待”
}
1
2
3
4
5
6
7
8

// signal(s);  
void V (sem &s) {  
     s.value = s.value+1;
      //释放一个资源（或通过信号量s发消息） 
  if (s.value <= 0) { //存在等待进程
      remove a process P from s.list;  
      wakeup( );
     }//表示在信号链表中，仍有等待该资源的进程被阻塞。 调用唤醒原语。
}
1
2
3
4
5
6
7
8
9

信号量互斥方法

P原语的参数是信号量value的初值。

mutex=1表示互斥，即最多有一个进程使用进入临界区。
你可以给不同进程的不同区域加互斥信号量，但只要是一个互斥信号量，那么这几个区域就不能同时执行。

信号量值为负时，说明有一个进程正在临界区执行，其它的正排在信号量等待队列中等待，等待的进程数等于信号量值的绝对值。

所以信号量的取值范围：+1～ -(n-1)，因为最多有一个空闲，最多有n-1个进程在等待。

[例]若P、V操作的信号量初值为1，当前值为-3，则表示有 3个等待进程。

信号量同步方法

看下面代码

s1用于写，初始为1，代表缓冲区是空的（有1个空间可写）
s2用于读，初始为0，代表缓冲区无空间可读

计算进程：s1–，变成0，写入，表示缓冲区满了，同时s2++，变成1，代表缓冲区有东西了
打印进程：s2–，变成0，读取，表示读过了。同时s1++，变成1，表示缓冲区可以覆盖了

如果s1是0，就不可以再写了，因为还有没读完的
如果s2是0，就不可以再读了，因为没有东西可读

有人问能否用一个信号量，不能的。因为P原语阻塞的原理就是判断value是否小于0，如果只用一个，那就不能阻塞两个进程了。比较抽象，但是这就是本质。

还有就是如何扩展缓存区呢，就是把s1设成更大的值。

生产者和消费者问题

以上问题本质上是生产者和消费者问题。但是生产者和消费者是相对的，对空间的消费就是对内容的生产。

1. 计算进程：打印数据的生产者；空缓冲的消费者
2. 打印进程：打印数据的消费者；空缓冲的生产者

对于生产者和消费者问题，首先有一个环形缓冲区。 使用两个指针指定位置。

其次就是三个信号量：
empty和full是一对同步信号量
为什么会有mutex互斥信号量呢？这是因为就像打印机之类的东西，本质上还是一个临界资源，虽然打印过程内部是同步的，但是对外部，这个打印进程是互斥的，当生产消费进程执行的过程的时候，不允许其他进程触碰当前进程的环形缓冲区，否则顺序可能被破坏。

1. empty：表示空缓冲区的个数，初值为k
2. full：有数据的缓冲区个数，初值为0
3. mutex：互斥访问临界区的信号量，初值为1

这里有人可能会有疑问，看起来信号量是int变量，很普通，怎么共享呢？实际上是有一个共享变量区的，这里只是伪代码，具体写代码会进行特殊声明，详见开头部分API接口那篇文章。

还有一个疑问，mutex也是共享的吗？如果mutex共享，那就意味着生产者在运行的时候，消费者是阻塞的。我觉得mutex应该不共享，生产者进程用一个，消费者用一个，这样保证了同时只能有一个生产者和消费者。但是这种机制实行起来需要更多的编程，目前没有这种机制，也有人在研发。

预防PV死锁

注意，应该先判断数据是否可用，再去判断互斥，占用。即，同步PV要在互斥PV之前。

死锁的本质就是互相等待资源。

假设P互斥在P同步之前，如果消费者需要等待生产者放入资源，但是生产者需要等待消费者释放互斥信号量（V操作），这就形成了死锁。反过来，如果是P同步在P互斥之前，在占用临界资源之前会先判断数据是否可用，可用以后才进行。

记住，互斥PV只是保证了执行的原子性，但是务必要保证原子性语句是可以执行下去的。

案例

理发师问题——阻塞进程有上限

一个理发师，一把理发椅，n把等候理发的顾客椅子，如果没有顾客则理发师便在理发椅上睡觉 ，当有一个顾客到达时，首先看理发师在干什么，如果理发师在睡觉，则唤醒理发师理发，如果理发师正在理发，则查看是否有空的顾客椅子可坐， 如果有，坐下等待，如果没有，则离开。

理发师问题在生产着消费者问题上，增加了满座则走的判断。下面我写的代码版本是直接从生产者消费者改过来的，实际上，还有另一种写法更加常用，后面给出。

int customer=0,cheer=n
int mutex=1

Barber:
while(1)
{
	P(customer)
	P(mutex)
	理发
	V(cheer)
	V(mutex)
}

Customer:
while(1)
{
	P(mutex)
	if(cheer==0)//没有空椅子，离开
	{
		离开
		V(mutex)
	}
	else
	{
		P(cheer)
		V(customer)
		V(mutex)
		等待理发
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

下面是另一种写法：在这个写法里，顾客来了要先V再P，因为customer代表顾客数量。
之后就是新增了一个waiting变量，其实这个变量和customer值相同，所以其实和我的思路也没太大区别，只是更贴近实际编程罢了。

信号量 customer = 0; // 顾客资源数
信号量 server = 0; // 服务人员资源数
信号量 mutex = 1;
int waiting = 0; // 正在等待的顾客数量

Server(){
    while(1){
        P(customer); 
        P(mutex); //
        叫号;
        waiting--;
        V(mutex); //
        V(server);
        提供服务;
    }
}

Customer(){
    P(mutex); //
    if (waiting < M){
        取号;
        waiting++;
        V(mutex); //
        V(customer);
        P(server);
        被服务;
    }
    else{
        V(mutex);
        离店;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

果盘问题——一个缓冲区两种资源

这个例子没有加互斥PV信号量，可以选择加一个。

哲学家进餐问题——一次申请多种资源

这两个同步P，可以推广到多种，而且位置关系也不一定是相邻。总之是一次申请多种/多个资源。

读写问题——带条件的PV

读者优先

读写策略是很多的，前面只是给出一种读者优先策略，这种策略比较粗糙，和我们实际中的不一样。比如你正在用notepad++读取一个文本，但是用windows txt修改文本（写）仍然是可以的，并且之后npp会重新加载文本。

读者优先策略描述如下：

1. 多进程可以同时读
2. 只允许一个进程写
3. 读者会阻止写者进入

分析：

1. 写写互斥，读写互斥。所以有rmutex和wmutex。
2. 读读不互斥，但是可以设置读取上限

代码分析：

1. 首先实现读写互斥，和写写互斥。最简单的思路就是用一个wmutex，给读写都加上锁。但是这样会带来一个问题，就是读读也会互斥
2. 为了解决读读互斥，需要加入if条件与一个int值——readcount判断是否有进程在读。如果已经获取了wmutex（有进程在读，readcount＞0），那就不需要再申请wmutex了。如果没有进程获取wmutex（readcount==0），就申请一个wmutex，把写操作排斥。在读操作完毕后，readcount–，表示减少一个读取进程，当减到0以后，就要释放wmutex。
3. 问题来了，rmutex又有什么用？rmutex其实就和我们前面生产者消费者里的mutex用法一样，是防止多进程访问共享变量的时候，readcount自增自减被打断，出现幽灵数据的问题。但是注意粒度要细，不要把中间的读取区域覆盖了。

最后讨论一下附加问题，能否限制读取进程上限？加一个readmax信号量就好，设为5。下面代码的P（readmax）放在了读取操作的前面。

	  int readmax=5;
Reader：
begin
		P(rmutex);
		if(readcount==0)then P(wmutex);
		readcount++;
		V(rmutex);
		P(readmax);
		read_file();
		V(readmax);
		P(rmutex);
		readcount=readcount-1;
		if(readcount==0)then V(wmutex);
		V(rmutex);
	end

writer:
begin
   p(wmutex);
   write data;
   v(wmutex);
   …
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

写者优先

1. 可以多个读者
2. 写者会阻止读者进入
3. 写者可以插队

从本质上来说，优先级就是通过if判断的。如果一个进程可以通过if跳过P操作，那是不是就意味着优先级更高？所以，读者写者问题的核心就在于如何通过if构造优先级。如果读写进程都用一个互斥量，不加if，那就是公平，如果想给谁提升优先级，就给谁加if。

写者优先基于读者优先改进，在最外面加了一个互斥量，这个互斥量x可以理解为有写进程的标志，如果一直有写进程进入，这个标志就一直是0，就会屏蔽读者的进入。

int readcount,writecount;
semaphore rmutex=1,wmutex=1,rwmutex=1,x=1;
reader：
		p(x);   //一个读进程与一个写进程在x上竞争
		p(rmutex);  //读进程互斥访问readcount
		++readcount;
		if(readcount==1) p(rwmutex); 
		v(rmutex);
		v(x);
		read data;  //临界区
		p(rmutex);
		--readcount;
		if(readcount==0) v(rwmutex);
		v(rmutex);

Writer：
		p(wmutex);      //写进程互斥访问writecount
		++writecount;
		if(writecount==1) p(x);  //一个写进程与一个读进程在x上竞争
		v(wmutex);
		p(rwmutex);     //其他写进程在rwmutex上排队
		write data;  //临界区
		v(rwmutex);
		p(wmutex);
		--writecount;
		if(writecount==0) v(x); //写进程都写完时，通过v(x)允许读进程读
		v(wmutex);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

读写公平

1. 允许多个读者
2. 读者存在会阻止写者进入，写者存在会阻止读者进入。

因为没有优先级，所以就撤掉写者对z变量的优先级（if），两个进程对z都没有if，就不存在插队问题：

int rmutex=1,rwmutex=1,readcount=0;
reader:
begin
   p(z);   //读写进程在z上排队。
   p(rmutex);
   if(readcount=0) then p(rwmutex);
   end if
   ++readcount;
   v(rmutex);
   v(z);   //无写者时，多个读者可以同时读.
   read data;
   p(rmutex);
   --readcount;
   if(readcount=0 then v(rwmutex);
   end if;
   v(rmutex);
   …
end
writer:
begin
   p(z);   //读写进程在z上排队。
   p(rwmutex);
   write data;
   v(rwmutex);
   v(z);
   …
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

管程（考试考一个概念）

信号量比较复杂，而且容易出死锁，所以就出现了管程，管程将PV封装，更加方便有效。

大概来说，管程将共享资源封装成数据结构（管程类），程序员调用这个管程类的方法去操作共享资源。这是一种面向对象的思路。

管程由高级语言提供接口，有的高级语言，比如c，Pascal就没有管程机制。

蓝色的对应于面向对象的：

1. 成员声明
2. 方法声明，是对外部暴露的接口。
3. 方法定义

红色的是管程特有：

1. 条件变量
2. use：引入外部操作，比如wait，signal等

进程的高级通信

低级通信的缺点：

1. 繁琐，写起来太麻烦
2. 不安全，比如死锁
3. 难以维护，bug难找

于是有了各种高级通信，可以分类：

消息缓冲通信——直接通信

一种直接通信的方式。

本来一个进程的内容可以直接发到另一个进程，但是这里加了一个消息缓冲区作为中介。
发进程先发到消息缓冲区，然后消息缓冲区链接到收进程的消息队列上。

底层实现用到了PV操作。但是用户只需要send和receive就行了。

信箱通信——间接通信

类似于消息缓冲，信箱也是一种中介，但是比缓冲隔离性更强。所以是间接通信。

同样是send和receive

其他通信机制

1. 管道通信。和前面说的管程不同。在两个进程之间建立一个单进单出的管道（队列），一个进程写，一个进程读，和其他进程没关系。
2. 共享储存区（共享内存）。如果要进行大量的通信，最好还是直接在内存里读，所以在内存中弄了一片共享的储存区，只需要简单定义一下存取相关的信息，就可以简单实现大量数据的存取。windows中的类似机制是文件映射。

死锁

死锁发生的无声无息，不是bug，却比bug还要恐怖，令程序员闻风色变。

死锁定义与产生条件

死锁因为资源的争夺而产生，所以先说资源：

1. 可抢占资源（抢了也没事）：当资源从占用进程剥夺走时，对进程不产生什么破坏性的影响。如主存、CPU。
2. 不可抢占资源（临界资源，抢了就坏事）：一旦分配，不能强收回，只能由其自动释放。如打印机、磁带机。

所谓死锁，本质上就是，A等B的资源，B等A的资源，然后互不相让。
类似于两个狭路相逢的车，如果一个车不后退，谁也过不去了就。

拿生产者消费者举例：

Procuder:
P(mutex)
P(empty)

Consumer:
P(full)
P(mutex)

生产者拿到了互斥资源（缓冲区），但是发现已经占满了，想写写不进去，阻塞。
消费者拿不到互斥资源，无法消耗缓冲区。

具体来说，死锁产生的条件如下，顺起来就是，临界资源，拿着不放，别人抢不了，循环等待：

1. 互斥条件
2. 保持和请求条件。进程因请求资源而阻塞时，对已经获得的资源保持不放。
3. 不可被剥夺条件。
4. 循环等待条件。存在一个进程循环链，链中每个进程都在等待链中的下一个进程所占用的资源。

满足这些条件，如果再有如下诱因就会产生死锁：

1. 系统临界资源不足。比如打印机只有一台，这是竞争的根本原因
2. 并发进程的同步关系管理不当。并发进程是异步的，谁先谁后没有明确管理

解决死锁的办法

忽略死锁——鸵鸟算法

崩溃就崩溃，大不了重启。
这种一般是很少发生死锁的情况。

Unix，Linux，Windows都有这种机制。

预防死锁——不太靠谱

破坏4个条件之一。

解决互斥

使用虚拟化技术将独占资源变成共享资源。比如一台打印机，虚拟成4台打印机。虚拟的底层是spooling技术，借助磁盘空间，先缓冲任务，再一个一个提交。

但是磁盘也是有限的，仍然可能出现问题。

静态申请

以前的进程都是动态申请资源的，这采用静态方法。
在执行进程之前就占用所有需要的资源，再进入进程。

这种方法显然不靠谱，一来需要的资源有时候无法预料，二来会极大地影响用户体验

剥夺阻塞进程的资源

进程被阻塞的时候，把已经占用的资源先交出来。

这样的代价比较大，也不靠谱。

破坏循环等待条件

将系统全部资源按类进行全局编号排序。进程对资源的请求必须按照资源的序号递增顺序进行。这样，就不会出现进程循环等待资源，预防死锁。

但是前提是要将资源排好序，但是资源利用还是不合理的。

避免死锁（重点，银行家算法）

在每次分配资源之前预测这种操作可能的后果。

如果本次分配大概率是安全的，分配，否则就等待。

这种就需要有特殊的算法支持预测。

进程—轨迹资源图

横纵坐标代表AB进程执行过程中的若干步骤。横纵坐标形成的每一个方格构成一个状态，进程并行执行的过程中，状态从起点（左下角，两个进程还没有启动）到终点（右上角，两个进程全部执行完成）不断转移。

每一个状态都有一个安全评级，大致有安全，可能危险，禁区三种等级，理想的轨迹是保证进程走在安全的道路上。但是为了效率，很有可能是走在灰色地带，但是绝对不能走到禁区。

至于怎么走，就由操作系统本身来计算，调度了。可见，这种方式需要好的算法。

银行家算法

Dijkstrea提出了银行家算法，基于上面的进程轨迹图，核心在于通过算法避免进入危险区。
大致来说，银行放贷类似于资源调度，如果出现死锁，就类似于借贷的对象资金无法回笼造成坏账。

先看一个简单的例子，理解思想。

从a到b是一个正常的分配过程，但是b到c就会陷入危险状态。
如何预测？就看我把资源全部交给某一个任务后，他能不能完成任务。如果不能完成任务，系统的资源没了，进程也还在等资源。

用b举例，A需要5，B需要4，C需要2，D需要4，系统有2，如果给C，就可以，但是给其他顾客，系统就会陷入危险。比如给了c，资源就不够了，直接卡死。

以上只是一类资源，实际中有多类资源，会构成一个矩阵。一般是横轴为进程，纵轴为资源类型。相对应的，系统资源也变成了一个横向量。具体做的只是把前面的过程按资源遍历一次就行。

有如下矩阵：

1. 最大需求矩阵。固定
2. 已分配矩阵。
3. 剩余需求矩阵。最大需求矩阵-已分配矩阵
4. 总资源向量。固定
5. 剩余资源向量。总资源向量-已分配矩阵按第二维求和

两步走：

1. 判断安全性。计算系统是否安全，就用剩余资源向量和剩余需求矩阵比，只要有一行（对应一个进程）的资源可以被剩余资源向量完全满足，那就是安全的。
2. 资源分配与回收。把分配给一行以后，资源释放，将已分配矩阵和剩余需求矩阵中的对应行划掉，把对应行之前占用的资源加到剩余资源向量中，资源回收。

由此就完成一个分配，之后不断执行，直到全部完成或者死锁。

上面的例题中，系统是安全的。因为根据剩余请求矩阵R，可以找到一个进程完成序列 P4, P1, P2, P3, P5。

银行家算法的缺陷在于，需要遍历一个矩阵，是$O(nm)$，还有就是，他只判断一步安全，在不断行走的过程中仍然有被危险区包围的可能。

检测与恢复死锁

允许死锁发生（实际上你想让死锁不发生也不行，死锁总会有），但是在发生死锁之后，检测并且恢复。

检测

检测程序定期启动，检测进程资源图中，是否有环路，如果有环路，那就死锁了。

上图的资源都是只有一个，实际上资源可以有多个，如果上面的c中，T资源有两个，那就可以把T方块切成两个，相当于把环路切开了，就不会构成死锁。

恢复

一种思路比较粗暴，把环路里所有进程都一次性kill。很明显，影响太大了，我因为一个小程序把一系列程序都杀了，得不偿失。

另一种思路叫资源剥夺。这种思路更加精确，从进程图里找出环路，在环路中一次剥夺一个进程的资源，分给环路中其他进程。而被剥夺的进程，执行回滚操作，保存一些信息，后面再重新申请。