进程管理

• 一、进程与线程基本知识
• 二、处理机调度
• 三、进程的同步与互斥
• 四、死锁

一、进程与线程基本知识

进程是资源分配、接收调度的基本单位。

在多道程序技术下，由于程序并发执行，导致他们失去封闭性，由此，引入进程。

1.PCB

1.1、PCB的概念

PCB是一种特殊的数据结构，来描述进程的基本情况和运行状态，进而控制和管理进程。
程序段、数据段和PCB三部分构成进程映像，进程映像是静态的，而进程是动态的。
PCB是进程存在的唯一标志！

1.2、PCB的组成
（1）PID：进程标识符，每个进程有唯一的标识号。
（2）UID：用户标识符，进程归属的用户，主要为了共享和保护。
（3）进程控制和管理信息：包括进程当前状态、进程优先级、进入内存时间等。
（4）处理及相关信息：状态字以及各种寄存器的值。

2.进程的组织

进程的组织方式常用的有链接方式和索引方式。

2.1链接方式
根据进程的PCB中的状态链接成队列，分为就绪队列、阻塞队列等。

2.2索引方式
将同一状态的进程组织在同一索引表中，表项指向PCB，分为就绪索引表和阻塞索引表。

3.进程的状态与转换

3.1进程的状态
（1）运行态：进程正在处理机上运行。
（2）就绪态：进程得到了处理机外的一切资源，只要处理机选中了它，便可立即运行。
（3）阻塞态：进程正在等待某一事件发生而暂停运行（如等待输入输出完成），此时即使处理机空闲也不能运行。
（4）创建态：进程正在被创建，尚未到就绪态。
（5）终止态：进程正在从系统中消失，可能是正常结束或者因为中断而退出运行。

3.2进程的转换

4.进程的控制

进程的控制主要功能是对系统中的所有进程实施有效的管理，主要包括进程创建、撤销进程、进程状态的转换等。一般吧进程控制的程序成为原语。

5.进程的通信

由于进程的内存地址空间相互独立，一个进程不能直接访问另一个进程的地址空间，所以需要共享。进程通信是指进程之间的信息交换，PV操作是低级操作，这里指高级操作。

5.1、共享存储
低级方式的共享是基于数据结构的，高级方式的共享是基于存储区的。
在这种共享方式下，操作系统会提供一个存储区和同步互斥工具，通过特殊的系统调用让两个进程共享空间。
两个进程要互斥地访问共享空间。

5.2、消息传递
发送进程把消息发到某个中间实体，接收进程从中间实体取得消息，中间实体称为信箱。

5.3、管道通信
“管道”指连接读写进程的一个pipe文件，其实就是内存中一个到小固定的缓冲区。
管道只能采用半双工通信，若想实现全双工通信需要建立两个管道。
各进程要互斥地访问管道。
管道不满不读，管道不空不写。

6.线程

Q:为什么要引入线程？
A:因为有的进程要执行很多事情，如QQ既要传送文件，又要视频聊天，如果没有线程，这两个功能只能一个个地执行，引入线程可以使多道程序并发执行，还可以减少程序在并发执行时所付出的时空开销（如切换进程的运行环境）。

6.1、线程与进程
引入线程后，进程只是系统资源的分配单元，而线程是处理机的分配单元
用于各个线程共享进程的地址空间，所以线程的同步与通信容易实现。

6.2、线程的属性
由于进程是资源的分配单位，所以线程是不具有系统资源的。线程也有一个唯一的标识符和线程控制块。

6.3、线程的实现方式
线程分为（1）内核级线程 （2）用户级线程
简单的说，内核级线程是操作系统能看到的，用户级线程是用户能看到的。
用户级线程的管理由应用程序来完成，线程切换等可以在用户态下完成。
内核级线程的管理是操作系统内核完成的，线程切换等在核心态下完成。
由于操作系统只能看见内核级线程，所以内核级线程才是处理机分配的单位！

7.多线程模型

（1）多对一模型：将多个用户级线程映射到一个内核级线程，线程管理在用户空间完成，但是一个停了，所有都要停，而且这些线程不能同时运行在多处理机上（因为在OS看来他们是一个线程）。
（2）一对一模型：将用户级线程和内核级线程一一对应，一个线程阻塞不会影响其他线程，并发度高，开销也大。
（3）多对多模型：将n个用户级线程对应到m个内核级线程中，中和了一对一模型和一对多模型的优点。

二、处理机调度

1.调度的概念

Q：什么是处理机调度？
A：处理及调度是对处理机进行分配，即从就绪队列按照一定算法选择一个进程并将处理机分配给它运行。实现程序并发执行。
处理机调度是多道程序操作系统的基础，是操作系统设计的核心问题。

2.调度的层次

（1）作业调度：称为高级调度，由于内存有限，无法将所有作业都调入内存，按一定算法从使其从后备队列到内存中，从外存到内存，并创建对应的PCB。（主要是调入，只会调入调出一次）。
（2）内存调度：可将暂时不能运行的进程调至外存等待，调到外存的进程状态为挂起态。被挂起的进程的PCB不会被调到外存，而是会常住在内存中，并且他们会在挂起队列中。被挂起的进程要按照一定算法重新调入内存（频率高于高级调度）。

（3）进程调度：按某种算法从就绪队列中选择一个进程分配处理机。

3.调度的时机及方式

3.1调度发生的情况
（1）当前进程主动放弃处理机（如正常结束，请求IO阻塞）。
（2）当前进程被动放弃处理机（如更高优先级进程进入就绪队列）。

3.2不能进行调度调度的情况
（1）处理中断的过程中。
（2）进程在操作系统内核的临界区。
（3）在原子操作中。

4.调度方式
（1）非剥夺式方式：即进程主动放弃处理机，即使有更重要的进程进入就绪队列，也得等当前进程处理完毕后才能上处理机。不能应用于分时和实时系统即不能优先处理紧急任务或人机交互。
（2）剥夺式方式：当一个高优先级的进程进入队列后，当前占有处理机的进程会被迫放弃处理机，把处理机分配给高优先级的进程。

5.调度的基本准则

（1）CPU利用率：计算公式为 【忙碌时间/总时间】。
（2）系统吞吐量：指单位时间内CPU完成作业的数量，长短作业不做区别。
（3）周转时间：周转时间指提交到作业完成所经历的时间，它包括：

• 作业在后备队列等待高级调度的时间
• 作业在就绪队列等待的时间
• 进程在处理机上的执行时间
• 进程等待IO操作的时间

周转时间=作业完成时间-作业提交时间
平均周转时间=所有作业周转时间/作业数量
带权周转时间=作业周转时间/作业实际上运行时间
（4）等待时间：指进程/作业处于等处理机状态的时间。进程的等待时间与作业的等待时间不同，另外不能把IO时间算进等待时间。
（5）响应时间：指用户从提出请求到被首次响应所经历的时间

6.调度算法

饥饿：指一个进程或者作业长时间得不到服务。
非剥夺式算法人机交互能力差，不关注响应时间等。

（1）先来先服务算法（FCFS）：按照进程/作业到达的顺序来执行

（2）短作业/进程优先算法（SJF）：选择估计运行时间最短的算法优先运行，默认是非剥夺式，也有剥夺版本

严格来讲，抢占式的SJF算法平均等待时间和平均周转时间最少。

（3）高响应比优先算法（SJF）：要综合考虑进程/作业的等待时间和要求服务时间，响应比=（等待时间+要求服务时间）/要求服务时间

由于不可剥夺，所以即使有高响应比的进来也要等当前进程主动放弃处理机。

（4）时间片调度算法：处理机选择就绪队列中第一个进程执行，但是仅能运行一个时间片，在时间片结束后即使没有运行完，处理机也会分配给下一个进程，被剥夺的进程回到队尾。

当P1结束走到队尾时，此时P2进程刚进入，默认新的进程上处理机，即P2。
主要适用于分时系统所以，关心响应时间，不在意周转时间。
如果时间片过大，变成先来先服务，如果时间片过小，则CPU利用率低。
时钟装置会发出时钟中断来告诉操作系统时间片已到。

（5）优先级调度算法：按照优先级来调度。既有抢占式也有非抢占式。

抢占式和非抢占式的可能发生调度的点分别是：当前进程运行完毕和新进程进入就绪队列。

静态优先级：给一个优先级后，就不会再变了。
动态优先级：随着进程的情况动态的调整优先级。
系统进程优先级>用户进程优先级
IO型进程优先级（IO繁忙性进程）>计算型进程（CPU繁忙性进程）
（个人理解：IO设备与CPU可以并行运行，让IO先运行会增加利用率）

（6）多级反馈队列调度算法：
结构：有多个就绪队列组成，就绪队列分优先级高低，优先级高的队列的时间片小。
行为：
当新进程到达时，先到优先级最高的队列，按FCFS原则分配时间片，时间片运行结束之,进入下一队列的队尾。
只有当优先级高的队列为空时，优先级较低的队列才会开始分配时间片。
如果优先级低的队列中有进程正在执行，此时一个新进程到达优先级较高的队列，则正在执行的进程回到所在队列队尾。
如果进程已经在优先级最低的队列中了，当时间片结束时，回到队尾即可（因为已经没有优先级更低的队列了）。

UNIX系统使用的就是这种。

三、进程的同步与互斥

1.进程同步

进程同步：即使多道并发程序具有异步性，但是某些程序在执行过程中应该有先后顺序，进程同步就是让异步性的进程也要按一定次序来执行（直接制约关系）。

2.进程互斥

计算机的某些资源在一个时间段内只允许一个进程访问，这类资源称为临界资源，对临界资源的访问只能互斥地进行（间接制约关系）。

对临界资源的访问逻辑上分为四个部分：
（1）进入区：负责检查是否有进程访问临界资源，若自己可进入，则表示“自己正在访问临界区”即（上锁）防止其他进程进入。
（2）临界区：访问临界资源的代码。
（3）退出区：解除自己正在访问临界资源的标志，即（解锁）。
（4）剩余区：做其他处理（不重要）。

3.软件实现进程互斥

（1）单标志法

这种算法对临界区的访问一定是轮流交替的，如果P0不访问临界区，由没有把turn改成1，则此时临界区空闲，P1却无法进入。

（2）双标志先检查法

通俗的理解为“你用不用，不用我用”，两个进程同时这么以为，由于最开始设定的都是不用，导致两个进程同时进入临界区
可能会出现两个进程同时访问临界区的状况。
1,2不是一气呵成的，先检查后上锁，如果1,2是原子操作不会发生进程切换的，那么这个算法没毛病。

（3）双标志后检查法

通俗理解为“我要用，你用吗”，两个进程最开始初始化为自己要用，每个进程都一位对方要用，所以两者都不进入临界区。

（4）Peterson算法

通俗的理解为“我想用，但你先来吧”，turn代表允许哪个进程进入，而lag表示自己进入的意愿。

4.硬件实现进程互斥

通过硬件实现临界段的方法成为低级方法或元方法。

（1）中断屏蔽算法：当一个进程要访问临界区时，最简单的方法是禁止一切中断发生即关中断，在访问临界区之后，再开中断。
（2）TestAndSet指令:也称为TS或TSL指令。这条指令是由硬件实现的，这个指令是一个原子操作，即执行期间不能被中断。

通俗地理解为：lock是否为true,表示是否临界区正在被使用，如果正在被使用，lock为true，其他进程一检查，进不来，之后访问临界区的代码执行完毕之后会自己把lock设置为false让其他进程进来。
左边的函数就是“是否有锁啊，有的话，返回有，然后lock=true依旧有，如果没有的话，那lock=true这回有了”。
优点：实现简单，一气呵成，适用于多处理及操作系统。
缺点类似于单标志法。
（3）Swap指令：也称Exchange指令或XCHG指令

与TSL指令在逻辑上是一样的。

5.信号量机制

信号量机制是一种功能较强用来解决进程同步和互斥问题的机制，他只能被两个标准的原语wait(S)和signal(S)访问，也可记为P操作和V操作。原语是由关中断和开中断实现的。
信号量其实际上是一个变量，用来表示系统中某种资源的数量。
wait(S)相当于进入区，signal（S）相当于退出区。
（1）整型信号量

（2）记录性信号量

这个阻塞条件与唤醒条件可以这么理解：
进入区表示我要用这类资源，所以我先把它的剩余资源总数减一，如果此时正好为0，说明它是原来有一，被我占用了之后变为0，所以我被分配到了资源，那么阻塞条件应该是“S.value<0”即原来是小于等于0的，我申请后，变成负数了。
退出区表示我用完了这类资源，如果此时“S.value<=0”那么肯定是有进程等着用呢，所以我把阻塞队列唤醒一个。

6.信号量实现同步、互斥

（1）信号量实现进程互斥：

只要有进程访问临界区了，互斥信号量就<=0,其他进程就进不来，很轻松就实现了互斥。
不同的临界资源要设置不同的互斥信号量

（2）信号量实现进程同步

个人理解：之所以在前代码后加V，在后代码加P，后代码想要执行，P之前，必须标志位得是大于0的（因为P还会减1），而初始标志位就是0，所以后代码必须得等V操作结束后才能运行。
而V操作在前代码后是保证前代码在后代码之前就执行完毕，V操作就是让后代码执行的钥匙，所以V应该在前代码之后。

（3）进程的前驱关系
进程的前驱关系本质上就是进程同步。

7.管程

管程其实也是一种同步机制（跟PV操作一样），就是一种代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的ziyu7an管理程序。

管程的特性（管程其实类似于java中的类）
（1）管程把对共享资源的操作封装起来，管程内的数据结构只能被管程中的过程所访问。
（2）每次仅允许一个进程进入管程，从而实现进程互斥（由编译器实现）

管程有一个条件变量机制，就是当一个进程被阻塞时，将该阻塞原因定义为条件变量condition，此时其他进程无法进入管程。
条件变量与信号量的区别在于，信号量是有值的，而管程只是一个状态位。

四、死锁

1.死锁的定义

死锁：是指多个进程因竞争资源导致互相等待，若没有外力进入，这些进程都无法推进。

2.死锁产生的原因

只要这四个条件有一个不成立，死锁就不会发生。
（1）互斥条件：指临界区资源同一时间内只能互斥地被访问。
（2）不剥夺条件：指一个进程在占有CPU资源时，不能被其他进程抢走，只能等该进程主动放弃。
（3）请求并保持条件：指一个资源在等待其他资源时，对自己已有的资源不会放弃。
（4）循环等待：存在一种进程资源的循环等待链，每个进程手上已有的资源都是另外的进程所请求的。
循环等待不一定有死锁，但死锁一定存在循环等待。
可以理解为循环等待中，可能会有可替代的资源。

3.死锁的预防

死锁预防即破坏以上四个条件之一。
（1）破坏互斥条件：不太可行，因为有些资源注定要互斥访问，如打印机、摄像头。
（2）破坏不可剥夺条件：反复的进行资源抢夺可能会增加系统开销。
（3）破坏请求并保持条件：这种采用静态分配方式，即一个进程要运行之前，要把所有他所需要的资源分配给它，它才会执行，这样做会严重浪费系统资源。
（4）破坏循坏等待条件：给系统资源编号，使每一个进程必须按编号递增的顺序请求资源。

4.银行家算法

Q：什么是系统安全状态？
A：指系统按某种进程推进顺序可以满足每个进程对资源的需求，使每个进程都可以顺利完成，如果能找到这样的一个安全序列，则系统处于安全状态。
不安全状态可能进入死锁，安全状态一定不会死锁，死锁系统一定处于不安全状态。

银行家算法通俗易懂地理解就是：当一个进程申请资源时，先看它是否超过它的最大需求量，若超过则拒绝分配，若没超过，进行下面分析。
看看当前系统能否满足进程所需要资源，能的话则试探性地分配给它，否则延后处理。

5.死锁的检测和解除

资源分配图：圆圈表示进程，框表示一类资源，从进程到资源的有向边叫请求边，从资源到进程的叫分配边。

死锁定理：简单地讲就是对资源分配图进行简化，若改图能消去所有的边，说明该图是可以简化的。系统发生死锁的条件是当且仅当资源分配图是不可完全简化的，这就是死锁定理。
如图，R1资源一共有仨，分配了三个，这是P2向他请求是满足不了的。

死锁解除方法：
（1）资源剥夺法：挂起某些进程，抢占他的资源，但应该注意避免饥饿。
（2）撤销进程法：直接撤销部分或全部死锁进程，并剥夺这些资源。
（3）进程回退法：让一个或多个进程回退到能避免死锁的时候，这种方法需要寄存器来记录历史信息。