进程管理（第二、三、四章）

进程

进程基本概念

概念

程序的一次执行

系统进行资源分配和调度的基本单位

每个进程相互独立

组成

程序代码——二进制

数据段——包括变量、常量等

PCB进程控制块——管理进程；一个进程对应一个PCB；包含操作系统对进程的描述和控制信息

特征

动态性——进程动态创建和销毁；进程的实质（一个程序启动时创建一个进程，程序结束时进程终止）

并发性——多个进程实体可以存在于内存当中，在同一时间内同时运行

独立性——独立获取和独立接受调度的基本单位；一个进程崩溃不会影响别的进程的执行

异步性——进程间相互制约，使进程具有执行的间断性；进程执行有随机性

结构特性——PCB

状态

状态——

新建状态【分配资源，初始化进程的PCB】、

就绪状态【还没有获得CPU的执行权限】、

运行状态【执行进程指令，CPU上运行】、

阻塞状态（等待状态）【等待某些事件发生，进程暂停执行】、

终止状态【完成进程任务后或由于错误异常情况，释放占用的资源，从系统中移除】

挂起状态【进程暂时中止进行，但并未被终止，可恢复之前状态】【挂起就绪：就绪状态被挂起，在就绪队列但不会被进行；挂起阻塞：阻塞状态被挂起，在阻塞队列但不会等待阻塞事件发生】

基本状态——就绪态、执行态、阻塞态

※

若系统无运行进程，就一定没有就绪进程。因为：若系统中没有运行进程，则系统很快会选择一个就绪进程执行；只有就绪队列中无进程，CPU才可能处于空闲状态。

若系统中既没有运行进程，也没有就绪进程，不一定没有进程。因为：系统中所有进程可能处于等待态，也可能处于死锁状态，也有可能因为等待的事件未发生而进入循环等待态

在采用优先级进程调度时，运行进程不一定是系统中优先级最高的进程。因为：高优先级的进程可能正处于等待队列中，进程调度会从就绪队列中选择一个进程占用CPU，这个被选中的进程可能优先级较低。

进程控制

进程创建

创建新的进程，分配必要资源

必须完成申请一个空白的进程控制块，初始化进程控制块，一般设置为就绪态

进程终止

完成任务或发生错误时，终止进程，释放资源，清除系统中相关信息

进程的阻塞与唤醒

暂停进程，CPU分配给其他可执行的进程；将已经阻塞的进程唤醒，进入就绪状态

阻塞是一个主动行为，唤醒是一个被动行为

进程挂起与激活

暂时停止执行使其进入一个非活动状态；将已经挂起的进程唤醒，进入挂起之前的状态

进程切换

多任务环境下，一个进程到另一进程

CPU资源有限，多进程共享资源

合理分配CPU时间给不同进程

开销较大

进程通信IPC

不同进程之间进行数据交换、信息传递或资源共享的一种机制

共享存储器系统

允许不同进程共享同一块物理内存区域，直接读写该内存区域的数据

同步互斥工具（PV操作）

消息传递、借助信息缓冲区

借助消息缓冲区，用于在多个进程之间传递信息或数据

直接通信方式：点对点的通信连接；发送进程需要知道接受进程的标识符或地址，将消息发送给接受进程；需要维护大量的连接信息，复杂性

间接通信方式：中间实体；灵活，但维护中间实体

管道通信

半双工的通信机制

常用于在父进程和子进程之间传递数据

管道本身互斥进入，数据一个方向中流动

客户机-服务器系统

分布式系统中，不同计算机之间的交互方式

套接字：不仅限于同一台计算机上的进程通信，可用于不同计算机之间的通信

远程调用RPC：不同进程之间，调用远程的函数或过程

※进程与程序

进程与程序的本质区别：进程的实质是进程实体的执行过程，有动态性；而程序时一组有序指令的集合，并存放在某种介质上，静态的；

进程与程序的区别：进程存储在内存；程序存储在外存

线程

目的

多任务并发执行，提高程序性能

进程内的执行单元

一个进程可包含多个线程

程序分成多个独立的执行流，并发执行任务

特点

轻量级：创建和销毁的开销较进程小

共享资源：同一个进程中共享相同的资源

独立调度：每个线程都有自己的调度单元，不同线程的调度是独立的

线程是处理机调度的单位，线程允许多个任务在同一时间内并发执行，每个线程可以独立执行不同的任务，从而实现并发处理

与进程类似，有三种基本状态，以及线程控制块（操作系统内核中）

※进程与线程

进程与线程的区别：

传统OS中，进程既是拥有资源的基本单位，也是调度和分派的基本单位

引入线程OS中，进程作为调度和分派的基本单位，线程是拥有资源的基本单位

调度

对系统中的进程或线程进行分配处理器时间和资源的过程

调度层次

高级调度（/作业调度/长期调度）

最上层的调度机制

外部资源池中选择一些任务，分配内存和必要资源，建立进程，将其放入就绪队列等待执行

决策过程较为宽松，分钟级或更长时间尺度

中级调度（/内存调度）

将内存中进程选择一部分调度到外存中，从而得到更多内存资源

阻塞态和挂起态的转换

低级调度（/进程调度/时间片调度）

最底层的调度层次

从内存中的就绪队列中选择一个进程，分配处理器时间，让其在CPU上执行

公平性和高吞吐量

评价指标

调度算法是否适合当前系统

处理机调度算法的共同目标

CPU利用率——CPU在一段时间内的工作负载

公平性——任务在调度过程中被公平对待的程度

平衡性——资源分配，避免资源竞争和死锁等问题

策略强制执行——操作系统根据预定义的规则和算法强制执行特定的调度策略，决定哪个进程或线程获得CPU执行权

批处理系统的调度算法共同目标

平均周转时间短——作业或进程提交到系统开始运行到完成运行并终止的整个时间间隔的平均值

带权周转时间，考虑作业或进程的权重和优先级

系统吞独量高——单位时间内完成的任务数量或处理的数据量

处理机利用率高

分时系统的调度算法共同目标

响应时间快——用户发送请求到系统开始处理请求并返回响应结果的整个时间间隔，包括用户发送请求到请求到达系统的时间、系统处理请求的时间、将处理结果返回给用户的时间

保证均衡性——保证每个分时进程都能尽快处理，处理的算法是时间轮转算法

实时系统的调度算法共同目标

保证满足截止时间的要求

保证可预测性

调度算法

先来先服务

简单易实现，平均等待时间较长，不利于短作业和短进程，适合CPU繁忙型作业/进程，不利于I/O繁忙型作业/进程

短作业/进程优先

平均等待时间短，预估时间难以得到，长任务饥饿，未考虑紧迫度

优先级调度算法

优先级

基于紧迫程度由外部赋予优先级，整数表示，较小的值有较高的优先级

调度算法分类：抢占式优先级调度算法【可被更高优先级的任务或进程抢占，即使正在进行的任务尚未完成】、非抢占式优先级调度算法【当前任务完成后，再选择优先级较高的任务执行】

原则：系统进程>用户进程；交互型进程>非交互型进程；I/O进程>计算型进程

优先级分类：静态优先级【创建时就分配固定优先级】、动态优先级【允许在任务执行过程中，根据实际情况进行优先级的变化】

高响应比优先调度算法：动态优先级调度算法；；不会饥饿，但增加系统开销

时间片轮转调度算法

每个任务或进程都被分配一个固定的时间片，当任务执行时，将被允许执行一个时间片的时间，一旦该时间片时间用完，任务暂停，放回就绪队列的末尾，等待下一次调度

多用于分时系统

时间片大小确定需要综合考虑系统响应时间、就绪队列进程数目、系统处理能力

进程调度：中断处理结束后，系统检测时间片是否用完，如果用完就将其设为就绪态或结束运行，若就绪列不空，则从就序队列队首进程执行；当前进程阻塞时，将其放入阻塞队列，若就绪队列不空，则调度新进程执行；进程执行结束后会导致当前进程释放CPU，并从就绪态中选择一个进程获得CPU；进程时间片用完，导致当前进程让出CPU，同时选择就绪队列的队首进程获得CPU

多级反馈队列调度算法

划分多个就绪队列，每个队列采用FCFS调度算法，不同队列的优先级不同，按队列优先级调度

负责而灵活的动态优先级调度算法，结合多个队列和反馈机制

基于公平原则的调度算法

实时调度

※调度算法的平均周转时间

例题：5个进程P1,P2,P3,P4,P5几乎同时到达，预期运行时间分别为10,6,2,4,8个时间单位。各个进程的优先级分别为3,5,2,1,4（数值越大，优先级越高），根据调度算法计算任务的平均周转时间和平均带权周转时间（进程切换开销可忽略不计）

先来先服务（P1,P2,P3,P4,P5）算法：

时间片轮转算法（假定时间片大小为两个时间单位）：

优先权调度算法：

※资源分配（银行家算法和安全性检查算法的应用）

假定系统有5个进程P0,P1,P2,P3,P4和四种资源A,B,C,D，若出现如表所示资源分配情况

那么

（1）该状态安全，

（2）如果进程P0，提出资源请求request=（0,0,0,1），系统会把资源分配给它

条件：①request<=need；②request<=available

式子：available=available-request；allocation=allocation+request；need=need-request

然后用第一问算法再算一次，若存在一个安全序列则可以实施分配

死锁

定义

多个进程或线程因竞争资源有限造成的相互等待的状态，系统无法进行，进而死循环

产生原因

通常并发环境中

竞争资源

进程推进顺序不当

必要条件

互斥条件——至少一个资源一次只能被一个进程或线程占用，即一段时间内，该资源不能同时被其他进程或线程访问

请求和保持——一个进程或线程在持有某些资源的同时又请求别的资源并不释放自己持有的资源，导致其他进程或线程无法获取到所需的资源

不可剥夺——资源不能被强制性地从一个进程或线程中抢占，只能由持有者主动释放

环路等待——多个进程或线程之间形成一个环路，每个进程或线程都在等待下一个进程或线程持有的资源

处理方法

死锁预防

合理分配资源 破坏死锁必要条件

死锁避免

资源分配前进行动态规划，预先计算资源请求的可能性

银行家算法

安全性检查算法

死锁检测

实时监测系统中资源分配情况

死锁解除

抢占资源或回滚进程等

恢复策略（终止 释放资源）

※进程与死锁

若系统有n（n>=2）个进程，每个进程均需要使用某类临界资源2个，则系统不会发生死锁所需的该资源总数至少是n+1【极端情况，n个进程，每个进程1个临界资源等待另一个资源，就会发生死锁】

进程同步

临界

临界资源：并发环境，同时被多个线程或进程访问的共享资源；一次只能供一个进程使用

临界区：程序中访问临界资源的代码块，需要在任意时刻最多只允许一个线程或进程访问；临界区内，对临界资源的访问必须是原子的，即不可被中断。

同步（进程间的直接制约关系）

合作完成

互斥（进程间的间接制约关系）

任意时刻只能有一个进程访问共享资源，其他进程需要等待

原则：

空闲让进、忙则等待、有限等待、让权等待（进程不能进入自己的临界区时，立即释放处理机CPU；但不是必须遵循的原则例如Peterson算法）

实现方法：

软件方法——Peterson算法（不依赖硬件提供的特殊指令）（只有两个进程需要互斥访问共享资源）

硬件方法——①中断屏蔽方法（关中断）②硬件指令方法：TestAndSet指令、Swap指令

信号量方法——整型信号量、记录型信号量（整数值+等待队列）、AND信号量、信号量集

※缓冲区的使用

一次只运行一个进程使用，故设置信号量S初始值为1

经典进程同步问题

生产者消费者问题

※

例题：三个进程R、W1、W2共享一个缓冲区Buf。进程R读入数据到Buf；若缓冲区中的数为奇数，则进程W1将其取出显示；若缓冲区中的数为偶数，则进程W2将其取出显示。限制条件如下，（1）缓冲区中每次只能存放一个数；（2）仅当缓冲区中没有数，或W1或W2将数取走后，进程R才可以将新读入的数放到缓冲区中；（3）进程W1或W2对每次存入缓冲区中的数只能显示一次，且W1和W2都不能从空的缓冲区中取数。假定开始时，缓冲区为空。利用记录型信号量及wait、Signal操作写出三个并发进程正确工作程序。

哲学家进餐问题

读者写者问题模型