二、进程管理

1、进程的描述

定义：可并发执行的程序在一个数据集合是运行过程。

1.1进程的特征

• 动态性：动态性是进程的最基本特征，程序是静态的，它是存放在介质上的一组有序指令的集合

• 并发性：指多个进程实体同存于内存中，能在一段时间内同时运行。

• 独立性：进程是一个能独立运行的基本单位，即是一个独立获得资源和独立调度的单位，而程序不作为独立单位参加运行。

• 异步性：进程按照各自的速度（按异步的方式）执行，导致程序执行的不可再现性。

• 结构性：进程实体由程序段、数据段和进程控制块三部分组成。

1.2进程的三个基本状态

• 运行态/执行态：指一个进程在处理机上运行。
• 就绪态：一个进程获得了除处理机外的一切所需资源，一旦得到处理机即可运行。
• 阻塞态：（又称挂起状态、等待状态）一个进程正在等待某一事件发生而暂时停止运行，即使把处理机分配给进程也无法运行。

三个基本状态转换关系如下：

注意：阻塞态→运行态、就绪态→阻塞态这两种状态转换不可能发生。

1.3系统中各进程状态管理

• 处于运行态进程：如果系统有一个处理机，则在任何一时刻，最多只有一个进程处于运行态。
• 处于就绪态进程：一般处于就绪态的进程按照一定的算法l排成一个就绪队列RL。
• 处于阻塞态进程：处于阻塞态的进程排在阻塞队列中。由于等待事件原因不同，阻塞队列也按事件分成几个队列WLi。

1.4进程控制块

• 进程控制块的作用――进程存在的唯一实体

  由于进程控制块中记录进程存在的特性信息；PCB与进程同生死，创建一个进程就是为其建立一个PCB，当进程被撤消时，系统就回收它的PCB；OS对进程的控制要是根据PCB来进行，对进程管理也通过对PCB管理来实现，所以进程控制块是进程存在的唯一实体。

• PCB的信息

  • 进程标识符：用于唯一地标识一个进程。
  • 进程调度信息：包括进程状态、队列、调度参数等数据。
  • 处理状态信息：由处理机各种寄存器所组成，该类信息使进程被中断后重新执行时能恢复现场从断点处继续运行。
  • 进程控制信息：包括程序和数据的地址、I／O资源清单，保证进程正常运行的同步和通信机制等。
  • 家族信息：包括该进程的父、子进程标识符、进程的用户等。

1.5进程上下文

• 静态角度看，进程是由程序、数据和进程控制块组成。
• 进程上下文实际上是执行活动全过程的静态描述，其包括与执行进程相关的信息：各种寄存器的值、程序段、数据集、各种堆栈值和PCB结构。
• 一个进程的执行是在该进程的上下文中执行。
• UNIX 操作系统的进程上下文称为进程映象。

2、进程控制

2.1进程控制的基础知识

1. 核心态和用户态
   ​操作系统代码在核心态下运行，用户应用程序代码在用户态下运行。
2. 原语
   原语是一种特殊的广义指令，它的功能是由系统通过一段不可分割（一旦开始执行就要执行完，不能中途中断）的指令操作来完成，它又称原子操作，原语在核心态下完成
3. 内核功能
   ​内核是计算机硬件上的第一层扩充软件，它是OS中关键部分，它是管理控制中心，内核在核心态下运行。

2.2进程状态的细化

• ”挂起“”激活“操作的引入：

​ 系统提供”挂起“操作，暂停进程运行，同时也提供”激活“的操作，恢复挂起进程。

• 被挂起前进程状态有三种，挂起后则多出两种：静止就绪态和静止阻塞态，挂起前的进程就绪和阻塞态也改为活动就绪态和活动阻塞态。

• 进程处于运行态和活动就绪态时，执行挂起操作，进程状态转换为静止就绪态。处于活动阻塞态时，执行挂起操作，进程状态转换为静止阻塞态。处于静止就绪态的进程执行激活操作转换为活动就绪态

转换图如下：

2.3进程控制原语

1. 创建原语：一个进程可借助创建原语来创建一个新进程，该新进程是它的子进程，创建一个进程主要是为新进程创建一个PCB。
2. 撤销原语/终止：进程系统撤消原语采用的策略是由父进程发出，撤消它的一个子进程及该子进程所有的子孙进程，被撤销的资源归还系统。
3. 阻塞原语：首先立即停止原来程序的执行，把PCB中的现行状态由运行态改为活动阻塞态，并将PCB插入到等待某事件的阻塞队列中，最后调用进程调度程序进行处理机的重新分配。
4. 唤醒原语：调用wakeup原语，将阻塞的进程唤醒，将等待该事件的进程从阻塞队列移出，插入到就绪队列中，修改进程的PCB中现行状态。
5. 挂起原语：调用挂起原语的进程只能挂起它自己或它的子孙，而不能挂起别的族系的进程。
6. 激活原语：用户进程或父进程通过调用激活原语将被挂起的进程激活。

2.4线程概念

2.4.1线程的引入

• 并发执行的进程的两个基本属性：

  1.进程既是一个拥有资源的独立单位，它可独立分配虚地址空间、主存和其它资源。

  2.又是一个可独立调度和分派的基本单位。

• 资源拥有单元称为进程（或任务），调度的单位称为线程、又称轻进程。

• 线程只拥有一点在运行中必不可省的资源，但它可与同属一个进程的其它线程共享进程拥有的全部资源

• 线程是进程的一个实体。

2.4.2多线程

• 多线程是OS在一个进程内支持多个线程的能力。

  

• 一个进程定义为保护的单元和资源分配的单元，与一个进程有关的是：

  1. 保存进程映象的虚地址空间
  2. 对处理器、其它进程、(如进程通信)、文件和I／O资源受保护的存取

• 在一个进程内有多个线程，与一个线程有关的是：

  1. 一个线程的执行状态
  2. 不运行时保存一个线程的内容

2.4.4线程的好处

1. 在一个存在的进程中产生（或终止）一个线程比产生（或终止）一个进程花费少得多的时间。
2. 同一进程内二个线程间切换时间也要比二个进程切换时间小得多。
3. 线程机制也增加了通讯的有效性。线程间通讯是在同一进程的地址空间内，共享主存和文件，无需内核参与。

例子：局域网上文件服务器。

3、进程同步

3.1进程同步的 概念

1. 进程间制约关系
2. 资源共享关系
3. 竞争资源的三个控制问题互斥、死锁、饥饿
4. 相互合作关系

3.2临界资源

• 定义：像打印机这类一次只允许一个进程使用的资源称为临界资源。
• 像磁盘等资源，它允许进程间共享，即可交替使用，所以它称为共享资源，而临界资源又称独享资源。

3.3临界区

多个进程共享临界资源时必须互斥使用

为此，将各进程代码分解，把访问临界资源的那段代码（称为临界区）与其它段代码分割开来，只对各种进程进入自己的临界区加以限制，即各进程互斥地进入自己的临界区。

3.4进程同步机制

• 多个相关进程在执行次序上的协调称为进程同步

• 用于保证多个进程在执行次序上的协调关系的相应机制称为进程同步机制。应遵循以下四条准则：

  1. 空闲礼让
  2. 忙则等待
  3. 有限等待
  4. 让权等待

• 进程同步机制在临界区前加上进入区，它负责对欲访问的临界资源状态进行检查，以决定是允许该进程进入临界区还是等待。

• 同时在临界区后加上退出区，它负责释放临界资源以便其它等待该临界资源的进程使用。

• 实现进程互斥和同步的机制有软件方法、硬件指令方法、信号量机制和管程等

3.5信号量机制

3.5.1记录型信号量结构

• 在信号量机制中，信号量是代表资源物理实体的数据结构

• 信号量的值（value）只能通过两个原子操作：

  P、V操作来改变，它代表申请资源和释放资源。

3.5.2信号量类型

按联系进程关系分为两类：

• 公用信号量（互斥信号量）：代表永久性的共享的临界资源（可反复使用）
• 专用信号量（同步信号量）：它代表消耗性的专用资源，只有使用该资源的进程才能对它施加PV操作

3.5.3信号量S取值意义

3.5.4PV操作（是原语）

信号量施加P、V操作代表申请和释放资源。

3.6利用信号量机制实现进程互斥

1. 为使多个进程能互斥地访问某临界资源，只需为该资源设置一个互斥信号量mutex,并设其初值为1
2. 规定每个进程在进入临界区CS前必须申请资源，即对互斥信号量mutex施加P操作，在退出、临界区CS后必须释放资源，即对互斥信号量mutex施加V操作。
3. 将各进程的临界区CS置于P（mutex）和**V(mutex)**操作之间

利用信号量实现共享打印机的A、B两进程互斥的类并行PASCAL程序描述如下

3.7利用信号量机制实现进程同步

• 为实现进程同步，需采用专用信号量

规则1：只有当C进程把数据送入Buffer后，P进程才能从Buffer中取出数据来打印。
设置一个专用信号量full，它代表的消耗性的专用资源是:缓冲器装满的数据。

规则2：只有当P进程从Buffer中取走数据后，C进程才能将新计算的数据再存入Buffer

​ 设置另一个专用信号量empty，它代表缓冲器空，是消耗性的专用资源。

根据两个规则来实现的类PASCAL程序：

两个P操作不能互换位置:因为在不知道有没有空盒子的情况下，就执行P( mutex）进入缓冲区域，若里面无空盒子，则在缓冲区域睡觉等待，导致外面的进程进不来，里面的进程也无法被唤醒，导致死锁。但是两个V操作可以换位置。

• 同步也可以理解为：

  先做动作的进程C在动作完成后对同步信号量施加V操作，代表发送消息；后做动作的进程P在动作前对同步信号量施加P操作，代表测试消息是否到达。

4、进程通信

高级通信要求能高效地传送大量数据，同时通信过程对用户透明，以简化程序设计的复杂性

高级通信机制可归结为三大类：

1. 共享存储器系统
2. 消息传送系统
   1. 直接通信方式
   2. 间接通信方式

​ 3.管道通信系统

4.1消息传送系统

4.1.1直接通信方式

指发送进程利用OS提供的发送命令直接把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上。接收进程利用OS提供的接收命令直接从消息缓冲队列中取得消息。

​ 1.1消息缓冲队列机制通信原理

• 由系统管理一组缓冲区，其中每个缓冲区可以存放一个消息。
• 当发送进程要发送消息时先要向系统申请一个缓冲区，然后把消息写进去，接着把该缓冲区连接到接收进程的消息缓冲队列中。
• 接收进程可以在适当的时候从消息缓冲队列中摘下消息缓冲区，读取消息，并释放该缓冲区。

​ 1.2消息缓冲队列通信的数据结构

• 消息缓冲区
• 进程PCB中有关通信的扩充数据项

4.1.2间接通信方式

在间接通信情况，消息不直接从发送者发送到接收者，而是发送到暂存消息的共享数据结构组成的队列，这个实体称为信箱（mailbox）因此两个进程通信情况，一个进程发送一个消息到某个信箱，而另一个进程从信箱中摘取消息。

间接通信的使用好处是增加了使用消息的灵活性

4.2管道通信

管道是指用于连接一个读进程和一个写进程，以实现它们之间通信的一个打开的共享文件，又称为pipe文件。

5、调度

5.1作业的状态

1. 提交状态：一个作业被提交给机房后正在通过外围机进行输入或用户通过终端向计算机中键入其作业时所处于的状态为提交状态。
2. 后备状态：作业已输入到磁盘输入井(输入缓冲区)，等待调入内存运行，此时作业处于后备状态。
3. 运行状态：一个在后备作业队列的作业被作业调度程序选中后，分配必要的资源，建立一组相应的进程后，调入内存，该作业就进入运行状态。
4. 完成状态：当进程正常运行结束或因发生错误而终止时，作业进入完成状态。终止作业程序将负责善后处理。

5.2处理机三级调度

1. 高级调度——作业调度

   作业调度用于决定把外存输入井上处于作业后备队列上的哪些作业调入内存，并为它们分配必要的资源，再将新创建的进程排在就绪队列上，参加CPU争夺。但分时系统和实时系统一般不需作业调度。

2. 低级调度——进程调度

   进程调度决定就绪队列中哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。
   进程调度是最基本的调度，任何操作系统都有进程调度

3. 中级调度——对换
   引入中级调度的目的是为了提高主存利用率和系统吞吐量。但当内存紧急时，会有阻塞/就绪态的进程调度到外存去，涉及内外存交换，速度慢。

5.3处理机调度模型

1. 仅有进程调度的调度队列模型
   在分时系统中通常仅设置了进程调度。

2. 有进程调度和中级调度队列模型
   在具有虚拟存储器技术的分时系统中（例如UNIX系统等），一般采用具有进程调度和中级调度的调度模型。

3. 具有高级调度和低级调度的调度队列模型
   在多道批处理系统中，一般处理机管理设置作业和进程两级调度。

4. 同时具有三级调度的调度队列模型
   在通用系统的多模式OS中，一般采用具有三级调度的调度队列模型，由于多模式OS同时支持批处理、分时和实时处理，所以它必须具有以上模型。

5.4进程调度

• 进程调度方式

1. 非抢占（非剥夺）方式：不允许某进程抢占已经分配出去的处理机。
2. 抢占（剥夺）方式：允许进程调度程序根据某个原则，去停止某个正在执行的进程，将已分配给进程的处理机，重新分配给另一个进程，抢占原则有：
   • 时间片原则：各进程按时间片运行，适用于分时系统。
   • 优先权原则：对一些紧急的进程赋予较高的优先权，其优先权比正在执行的进程优先权高，便停止正在执行的进程，将处理机分配给优先权高的进程。

5.5调度方式和算法的选择准则和评价

5.5.1面向用户的准则和评价

• 周转时间短：它是评价批处理系统的重要性能指标。
• 响应时间快：是评价分时系统的性能指标。
• 截止时间保证：是用来评价实时系统的重要指标。
• 优先权准则：选择批处理、分时和实时系统的调度算法时，都可引用优先权准则。

5.5.2面向系统的准则

• 达到系统设计目标
• 系统吞吐量大：是用来评价批处理系统的重要指标**，系统吞吐量是单位时间内完成的作业数**
• 处理机利用率高
• 各类资源的平衡使用

5.6作业/进程调度算法

5.6.1先来先服务（FCFS）调度算法

• 原理：按照作业到达后备作业队列（或进程进入就绪队列）的先后次序来选择作业（或进程）。
• 特点：易于实现，表面上很公平，有利于长作业，对短作业不利；有利于CPU繁忙型作业，对I/O繁忙型作业不利。

5.6.2短作业/进程优先（SJF）调度算法

• 主要用于作业调度
• 原理：它从作业后备队列中挑选所需运行时间（估计值）最短的作业进入主存运行
• 有利于短作业，对长作业不利。

5.6.3高响应比优先（HRRN）调度算法

• 原理：先计算此时后备作业队列中每个作业的响应比R，然后选择其值最大的作业投入运行。

• 有利于短作业，但也兼顾到长作业

5.6.4时间片轮转（RR）调度算法

• 用于进程调度，是分时系统采用的主要调度算法

5.6.5优先权调度算法

• 静态优先权：每个进程的优先级在生存周期内是一成不变的，其确定依据是

  • 进程类型：系统进程优先权一般高于用户态进程。
  • 进程对资源的需求：进程执行时间及内存需要省的进程应赋予较高的优先权。
  • 用户要求：用户的紧迫程度及用户所付费用的多少来确定进程的优先权。

• 动态优先权：：每个进程的优先级在运行周期内是可以改变的，其考虑因素

  • 进程的等待时间
  • 已使用处理机的时间
  • 资源使用情况

5.6.6多级队列调度算法

• 定义：根据作业的性质和类型的不同，将就绪队列再分为若干个子队列，所有的作业（或进程）按其性质排入相应的队列中，而不同的就绪队列采用不同的调度算法。
• 各就绪队列按进程性质赋予不同的优先权，优先权高的就绪队列的进程优先被调度。
• 为每个队列分配一定的占用CPU时间的比例。

5.6.7多级反馈队列调度算法

• 将就绪队列分为若干个子就绪队列，上面就绪队列为高优先级。
• 在优先级越高的队列中，每个进程的执行时间片就规定得越小。
• 这种优先级下降的队列间反馈真正有利于短进程优先。
• 一个进程从阻塞态变为就绪态时要提高优先级。
• 这种反馈真正有利于I/O频繁的进程优先。

6、进程死锁

定义：指计算机系统和进程所处的一种状态。在系统中，两个或多个进程无限期地等待永远不会发生的事件，此时称系统处于死锁状态。

6.1死锁产生的原语和条件

6.1.1产生死锁的原因

1. 竞争资源引起死锁
   由于系统拥有的不可抢占的资源有限，多个进程竞争不可抢占的资源就可能引起死锁。
2. 进程推进顺序不当引起死锁
   在多道程序系统中，并发执行的进程推进序列不可预测，有些推进顺序，进程可以顺利完成，的推进顺序会引起进程无限期地等待，造成了死锁

6.1.2产生死锁的必要条件

1. 互斥条件：一个资源一次只能被一个进程所使用

2. 不可抢占条件：一个资源仅能被占有它的进程所释放，而不能被别的进程强占

3. 请求和保持条件：进程已保持一个资源，又提出新的资源要求，该资源又已被其它进程占有，此时请求进程阻塞，但又对已经获得的资源保持不放。

4. 环路等待条件：当每类资源只有一个时，在发生死锁时，必然存在一个进程-资源的环形链。

以上四个条件仅是必要条件而不是充分条件，即只要发生死锁则这四个条件一定同时成立。

6.2处理死锁的基本方法

1. 死锁的预防
   ​ 静态方法：通过设置某些限制条件，去破坏产生死锁的四个必要条件之一。

2. 死锁的避免

   动态方法：在进程申请资源时用某种方法去防止系统进入不安全状态，从而避免发生死锁。

3. 死锁的检测和解除

   通过系统设置的检测机构及时检测死锁的发生，如检测到死锁，则采用撤消进程等死锁解除方法使系统恢复正常工作。

4. 鸵鸟算法

   发生死锁采用重启动和人工恢复方法。

6.3死锁的预防

预防死锁的方法是破坏四个产生死锁的必要条件之一。

1. 破坏互斥条件

   互斥使用是资源本身特征所决定的。使用硬软件结合可改变资源本身特性，例如采用SPOOLing技术可将“独享” 打印机改变为“共享”的打印机。

2. 破坏不可抢占条件

   抢占式调度法主要用于处理机和存储器资源调度，它们的状态容易保存和恢复。

3. 破坏请求和保持条件

   系统可采用资源静态预先全分配方式来破坏请求保持条件。优点是简单、易于实现且很安全，但其资源利用率很低，进程也延迟运行。

4. 破坏循环等待条件

   • 有序资源使用法：将所有的资源按类型进行线性排队，并赋予不同的序号，所有进程对资源的请求必须严格按资源序号递增的次序提出。

6.4死锁避免

6.4.1根据系统的安全状态避免死锁

该方法允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性。

• 系统安全状态：
  安全状态是指系统的一种状态，在此状态开始，系统能按某种顺序（例如P1、P2……Pn）来为各个进程分配其所需资源，这种序列称为安全序列，直至最大需求，使每个进程都可顺序地一个个地完成。

• 由安全状态向不安全状态的转换

如果在T0状态不按安全序列进行分配，可能会导致系统进入一个不安全状态

6.4.2利用银行家算法避免死锁

1. 银行家算法的数据结构

• 可用资源向量
• 最大需求矩阵
• 分配矩阵
• 需求矩阵

2. 银行家算法
   假设在进程并发执行时进程i提出请求j类资源k个后，表示为Requesti[j]=k。系统按下述步骤进行安全检查：

• 如果Requesti≤Needi则继续以下检查，否则显示需求申请超出最大需求值的错误。
• 如果Requesti≤Available则继续以下检查，否则显示系统无足够资源，Pi阻塞等待。
• 系统试探把要求的资源分配给进程i并修改有关数据结构的值
• 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态，安全，才正式将资源分配给进程i

6.5死锁的检测

6.5.1资源分配图的简化

系统处于某状态S时可用资源分配图表示，可用资源分配图简化来判断系统是否处于死锁状态。

• 在资源分配图中找一个既不阻塞又非孤立的进程结点PI（如某进程既无已分配的资源也不需申请资源，即无分配边又无申请边，则该进程结点是孤立结点），让它获得所需资源而继续运行直至完毕，再释放它拥有的所有的资源，这相当于取消PI的分配边和请求边，使它成为孤立结点。
• 所有的进程结点都是孤立结点则称资源分配图是可完全简化的

6.5.2死锁定理

系统状态S为死锁状态的充要条件，当且仅当S状态的资源分配图是不可完全简化时，称为死锁定理。

6.6死锁的解除

1.撤销进程法：当前系统中所使用的死锁恢复办法是强制性地从系统中撤消一个或多个死锁进程以断开循环等待链，并收回分配给终止进程的全部资源供剩下的进程使用。

2.资源剥夺法:从一些进程那里强行剥夺足够数量的资源分配给死锁进程，以解除死锁状态。

3.进程回退法：让一个或多个进程回退到足以解除死锁的位置。