操作系统学习笔记（二）进程管理

进程和线程

进程的概念、组成、组织方式、特征

概念

引入多道程序技术之后，为了方便操作系统管理，完成程序的并发执行，引入了进程，进程实体的概念
内存中的PCB,程序段，数据段三部分构成了进程实体（进程印象），一般来说进程实体可以简称为进程
严格来说，进程实体和进程是不一样的，进程是动态的，是程序的一次执行过程，是系统进行资源分配和调度的独立单位；进程实体是静态的。
同一个程序多次执行会对应多个进程

组成

当进程被创建时，操作系统会为该进程分配一个唯一的、不重复的“身份证号”—— PID（Process ID，进程ID）
信息都被保存在一个数据结构PCB（Process Control Block）中，即进程控制块
操作系统需要对各个并发运行的进程进行管理，但凡管理时所需要的信息，都会被放在PCB中
涉及到进程的管理所需要的数据都在PCB中，程序本身运行所需要的数据则在程序段和数据段中

进程的组织

特征

动态性：动态性是进程最基本特征，进程有着创建、活动、暂停、终止等过程，具有生命周期

并发性：多个进程实体同时存在内存中，引入进程的目的就是为了程序与其他程序并发执行

独立性：进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位。没有建立PCB的程序，都不能作为一个独立单位参与运行

异步性：进程相互制约，进程以不可预知的速度向前推进。所以操作系统中一定要配置响应的进程同步机制程序段

结构性：每个进程都配置一个PCB对其进行描述（数据段、进程实体、进程控制段）

进程的状态与转换

进程的状态

创建态
就绪态
运行态
阻塞态
终止态

进程的转换

进程控制

什么是进程控制

进程控制就是要实现进程状态转换

如何实现进程控制

用“原语”实现

原语的执行具有原子性，即执行过程只能一气呵成，期间不允许被中断。
原语可以用“关中断指令”和“开中断指令”这两个特权指令实现原子性

进程的相关原语

进程控制会导致进程状态的转换。无论哪个原语，要做的无非是三件事情：

更新PCB中的信息（如修改进程状态标志，将运行环境保存到PCB，从PCB恢复运行环境）
1. 所有进程控制原语一定都会修改进程状态标志
2. 剥夺当前运行进程的CPU使用权必然需要保存其运行环境
3. 某进程开始运行前必然要恢复其运行环境
将PCB插入合适的队列
分配/回收资源

进程的创建

进程的终止

进程的阻塞和唤醒

进程的切换

进程通信

什么是进程通信？

进程通信就是指进程之间的信息交换
进程是分配系统资源的单位（包括内存地址空间），因此各进程拥有的内存地址空间相互独立。
为了保证安全，一个进程不能直接访问另一个进程的地址空间。

共享存储

两个进程对共享空间的访问必须是互斥的（互斥访问通过操作系统提供的工具实现）
操作系统只负责提供共享空间和同步互斥工具（如P,V操作）
基于数据结构的共享：比如共享空间里只能放一个长度为10的数组。这种共享方式速度慢、限制多，是一种低级通信方式
基于存储区的共享：在内存中画出一块共享存储区，数据的形式、存放位置都由进程控制，而不是操作系统。相比之下，这种共享方式速度更快，是一种高级通信方式。

管道通信

“管道“是指用于连接读写进程的一个共享文件，又名pipe文件。其实是在内存中开辟一个大小固定的缓冲区
管道只能采用半双工通信，某一个时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道
数据以字符流的形式写入管道，当管道写满时，写进程的write（）系统调用将被阻塞，等待读进程将数据取走。当读进程将数据全部取走后，管道变空，此时读进程的read（）系统调用将被阻塞。

如果没写满，就不允许读。如果没读空，就不允许写。

数据一旦被读出，就从管道中被抛弃，这就意味着读进程最多只能有一个，否则可能会有读错数据的情况。

消息传递

进程间的数据交换以格式化的消息（Message）为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。
直接通信：信息直接挂到接收进程的信息缓存队列上
间接通信：消息要先发送到中间实体（信箱）中，因此也称“信箱通信方式”。

线程的概念和多线程模型

什么是线程，为什么要引入线程？

有的进程可能需要“同时”做很多事，而传统的进程只能串行地执行一系列程序。为此，引入了“线程”，来增加并发度。

可以把线程理解为“轻量级进程”。
线程是一个基本的CPU执行单元，也是程序执行流的最小单位。
引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务（如QQ视频、文字聊天、传文件）

引入线程后，进程只作为除CPU之外的系统资源的分配单元（如打印机、内存地址空间等都是分配给进程的）。线程则作为处理机的分配单元。

进程与线程比较

线程属性

线程的实现方法

多线程模型

while 循环就是一个最弱智的“线程库”，线程库完成了对线程的管理工作（如调度）

调度

调度的概念、层次

基本概念

合理的对进程进行处理及分配

调度的层次

高级调度（作业调度）

按一定的原则从外存的作业后备队列中挑选一个（或多个）作业调入内存，并创建进程。每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB。

中级调度（内存调度）

暂时调到外存等待的进程状态为挂起状态。被挂起的进程PCB会被组织成挂起队列
PCB不会一起被调到外存，而是常驻内存
按照某种策略决定将哪个处于挂起状态的进程重新调入内存。
一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高。

低级调度（进程调度/处理机调度）

按照某种策略从就绪队列中选取一个进程，将处理机分配给它。

进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。
进程调度的频率很高，一般几十毫秒一次。

补充知识：七种状态

进程调度的时机切换与过程调度方式

切换时机

不能切换的情况

在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。
进程在操作系统内核程序临界区中。
在原子操作过程中（原语）。原子操作不可中断，要一气呵成（如之前讲过的修改PCB中进程状态标志，并把PCB放到相应队列）

可以切换的情况

当前运行的进程主动放弃处理机
- 进程正常终止
- 运行过程中发生异常而终止
- 进程主动请求阻塞（如等待I/O）

当前运行的进程被动放弃处理机
- 分给进程的时间片用完
- 有更紧急的事需要处理（如I/O中断）
- 有更高优先级的进程进入就绪队列

调度方式

非剥夺调度方式，又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。
剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。

进程的切换与过程

进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。
狭义的进程调度指的是从就绪队列中选中一个要运行的进程。
广义的进程调度包含了选择一个进程和进程切换两个步骤。
进程切换的过程主要完成了：

对原来运行进程各种数据的保存
对新的进程各种数据的恢复

调度算法的评价指标

调度算法1

先来先服务（FCFS）

最短作业优先（SJF）

最高响应比优先（HRRN）

调度算法2

时间片轮转（RR）

优先级调度

多级反馈队列

对各类型进程相对公平（FCFS的优点）；
每个新到达的进程都可以很快就得到响应（RR的优点）；
短进程只用较少的时间就可完成（SPF的优点）；
不必实现估计进程的运行时间（避免用户作假）；
可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/O密集型进程（拓展：可以将因I/O而阻塞的进程重新放回原队列，这样I/O型进程就可以保持较高优先级）
一般不说它有缺点，不过可能导致饥饿

互斥同步

进程同步、进程互斥

进程同步

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。
进程间的直接制约关系就是源于它们之间的相互合作。
解决异步问题

进程互斥

间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待

临界区资源的互斥访问

临界区：访问临界资源的那段代码
进入区：负责检查是否可进入临界区
退出区：负责解除正在访问临界资源的标志
剩余区：做其他处理
临界区是进程中访问临界资源的代码段。
进入区和退出区是负责实现互斥的代码段。
临界区也可称为“临界段”。

原则

空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区；
忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待；
有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）；
让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

进程互斥的软件实现方法

单标志法

算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。交替进入临界区。

主要问题：违背“空闲让进”原则，必须“轮流访问”

双标志先检查法

每个进程访问临界资源前，先检查临界资源是否被访问，如果空闲才能进
优点：不用交替进入可以连续使用
主要问题：违反“忙则等待”原则。
原因在于，进入区的“检查”和“上锁”两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。

双标志后检查法

先设置标志，表示自己想进入，检查对方标志，如果对方也要进入，那么就等待否则就进入

优点：不会两个进程都进入临界区

缺点：双方会互相谦让，导致饥饿

Peterson 算法

算法思想：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”（谦让）。做一个有礼貌的进程。
增加标志位
优点：不会饥饿
缺点：复杂

进程互斥的硬件实现方法

中断屏蔽法

利用“开/关中断指令”实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况）
优点：简单、高效
缺点：不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险）

TestAndSet指令（TSL）

TSL 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成
相比软件实现方法，TSL 指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。
优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境
缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。

Swap指令（XCHG）

逻辑上来看 Swap 和 TSL 并无太大区别，都是先记录下此时临界区是否已经被上锁（记录在 old 变量上），再将上锁标记 lock 设置为 true，最后检查 old，如果 old 为 false 则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。

优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境

缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。

信号量机制

实现进程互斥、同步的方法

信号量其实就是一个变量，可以用一个信号量来表示系统中某种资源的数量

wait、signal 原语常简称为P、V操作（来自荷兰语proberen 和verhogen）。因此，做题的时候常把wait（S）、signal（S）两个操作分别写为P（S）、V（S）

P上锁

V解锁

用信号量机制实现进程互斥、同步、前驱关系

实现进程互斥

上锁——解锁

实现进程同步、前驱关系

解锁——上锁

实现前驱关系

画图非常有用

生产者消费者问题

生产者：先生产后互斥
消费者：先消费后互斥

思考：能否改变相邻P、V操作的顺序？

会导致：我要放东西通过了，但满了放不进去，去到消费者，但通道被生产者占住了，形成死锁
同步：查看缓存区容量和非空区
互斥：消费者和生产者不能同时使用缓存区

多生产者-多消费者

画图非常有用

吸烟者问题

读者-写者问题

写和读，写和写不能同时访问

但读和读可以同时访问

“读优先”

第一个读者先加两把锁，都关上，再打开互斥锁，让其他读者进行访问

”写优先“相对公平

第一个读者先加三把锁，都关上，再打开互斥锁和写优先锁，且先打开写优先锁，使只要读者读完就给写

哲学家进餐问题

引出死锁问题

管程

为什么要引入管程

信号量机制存在的问题：编写程序困难、易出错

管程的定义

局部于管程的共享数据结构说明；
对该数据结构进行操作的一组过程；
对局部于管程的共享数据设置初始值的语句；
管程有一个名字。

基本特征

局部于管程的数据只能被局部于管程的过程所访问；
一个进程只有通过调用管程内的过程才能进入管程访问共享数据
每次仅允许一个进程在管程内执行某个内部过程。

死锁

死锁的概念

在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是“死锁”。发生死锁后若无外力干涉，这些进程都将无法向前推进。

必要条件

互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）。
不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。

预防死锁

破坏互斥条件

互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁。

把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。

缺点：并不是所有的资源都可以改造成可共享使用的资源。

破坏不剥夺条件

不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。

破坏不剥夺条件：
方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。

方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级（比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用）

缺点：

实现起来比较复杂。
释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU。
反复地申请和释放资源会增加系统开销，降低系统吞吐量。
若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。

破坏请求和保持条件

请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。

可以采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了。

缺点：
有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。

另外，该策略也有可能导致某些进程饥饿。

破坏循环等待条件

循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。

可采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（即编号相同的资源）一次申请完。

原理分析：一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象。

该策略的缺点：

不方便增加新的设备，因为可能需要重新分配所有的编号；
进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费；
必须按规定次序申请资源，用户编程麻烦。

避免死锁

什么是安全序列

安全性算法步骤：

检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。不断重复上述过程，看最是

否能让所有进程都加入安全序列。

系统处于不安全状态未必死锁，但死锁时一定处于不安全状态。系统处于安全状态一定不会死锁。

检测和解除

死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁

死锁的解除

一旦检测出死锁的发生，就应该立即解除死锁。
补充：并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后，还连着边的那些进程就是死锁进程解除死锁的主要方法有：

资源剥夺法。挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
撤销进程法（或称终止进程法）。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。