本章知识结构图如下：

一、进程与线程

1.进程的概念和特征

(1)进程的概念

  进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。所谓的资源是指处理机的时间片。
  进程映像/进程实体：由程序段、相关数据段和PCB三部分构成了进程映像（进程实体）。所谓创建进程，实质上是创建进程映像中的PCB；而撤销进程，实质上是撤销进程的PCB。
  PCB：为了使参与并发执行的程序（含数据）能独立地运行，必须为之配置一个专门的数据结构，称为进程控制块（ProcessControl Block，PCB）。系统利用PCB来描述进程的基本情况和运行状态，进而控制和管理进程。
  值得注意的是，进程映像是静态的，进程则是动态的。

(2)进程的特征

  进程是由多道程序的并发执行而引出的，特征如下：

• 动态性
• 并发性
• 独立性
• 异步性
• 结构性

2.进程的状态与转换

• 运行态
• 就绪态：已获得除处理机以外的一切资源，在就绪队列中等待处理机资源。
• 阻塞态/等待态：等待某资源为可用，即时处理机空闲也不行。
• 创建态
• 结束态：进程消失前的状态。

  需要注意的是，一个进程从运行态变成阻塞态是主动的行为，而从阻塞态变成就绪态是被动的行为，需要其他相关进程的协助。

3.进程控制

  进程控制用到的程序段是原语，是不可分割的整体。

(1)进程的创建

  允许一个进程创建另一个进程。此时创建者称为父进程，被创建的进程称为子进程。子进程可以继承父进程所拥有的资源。当子进程被撤销时，应将其从父进程那里获得的资源归还给父进程。此外，在撤销父进程时，必须同时撤销其所有的子进程。
  在操作系统中，终端用户登录系统、作业调度、系统提供服务、用户程序的应用请求等都会引起进程的创建。设备分配不会引起进程的创建。 创建原语∶

• 分配进程标志号，申请空白的PCB，若PCB申请成功进行下一步。
• 分配必要的资源，比如内存空间。若资源不够，进入阻塞态等待。
• 初始化PCB。
• 进入就绪队列。

(2)进程的终止

  引起终止的事件：①正常结束②异常③外部干预
  撤销原语：

• 根据进程标志号检索PCB，读出进程状态。
• 若进程在执行，终止执行；若有子进程在运行，终止。
• 回收进程资源，子进程还给父进程，父进程还给操作系统。
• 删除PCB。

(3)进程的阻塞和唤醒

  Block 原语(阻塞)和Wakeup原语(唤醒)是一对作用刚好相反的原语，必须成对使用。Block 原语是由被阻塞进程自我调用实现的，而Wakeup原语则是由一个与被唤醒进程合作或被其他相关的进程调用实现的。
  进程唤醒，是指进程从阻塞进入就绪态，而不是立马开始运行。

(3)进程切换

  任何进程都是在操作系统内核的支持下运行的，是与内核紧密相关的。
  注意∶"调度"和"切换"的区别。调度是指决定资源分配给哪个进程的行为，是一种决策行为；切换是指实际分配的行为，是执行行为。一般来说，先有资源的调度，然后才有进程的切换。
  注意，进程切换与处理机模式切换是不同的，模式切换时，处理机逻辑上可能还在同一进程中运行。若进程因中断或异常进入核心态运行，执行完后又回到用户态刚被中断的程序运行，则操作系统只需恢复进程进入内核时所保存的CPU现场，而无须改变当前进程的环境信息。但若要切换进程，当前运行进程改变了，则当前进程的环境信息也需要改变。

4.进程的组织

(1) 进程控制块PCB

  操作系统通过PCB表来管理和控制进程。

(2) 程序段

  程序段就是能被进程调度程序调度到CPU执行的程序代码段。注意，程序可被多个进程共享，即多个进程可以运行同一个程序。

(3) 数据段

  一个进程的数据段，可以是进程对应的程序加工处理的原始数据，也可以是程序执行时产生的中间或最终结果。

5.进程的通信

(1)共享存储

  操作系统只负责为通信进程提供可共享使用的存储空间和同步互斥工具，而数据交换则由用户自己安排读/写指令完成。

  注意，用户进程空间一般都是独立的，进程运行期间一般不能访问其他进程的空间，要想让两个用户进程共享空间，必须通过特殊的系统调用实现，而进程内的线程是自然共享进程空间的。
  简单理解就是，甲和乙中间有一个大布袋，甲和乙交换物品是通过大布袋进行的，甲把物品放在大布袋里，乙拿走。但乙不能直接到甲的手中拿东西，甲也不能直接到乙的手中拿东西。

(2)消息传递

  在消息传递系统中，进程间的数据交换是以格式化的消息（Message）为单位的。若通信的进程之间不存在可直接访问的共享空间，则必须利用操作系统提供的消息传递方法实现进程通信。进程通过系统提供的发送消息和接收消息两个原语进行数据交换。

• 直接通信方式。发送进程直接把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中取得消息。
• 间接通信方式。 发送进程把消息发送到信箱，接收进程从信箱取得消息。该通信方式广泛应用于计算机网络中，相应的通信系统称为电子邮件系统。

(3)管道通信

  所谓"管道"，是指用于连接一个读进程和一个写进程以实现它们之间的通信的一个共享文件，又名 pipe文件。向管道（共享文件）提供输入的发送进程（即写进程），以字符流形式将大量的数据送入（写）管道；而接收管道输出的接收进程（即读进程）则从管道中接收（读）数据。为了协调双方的通信，管道机制必须提供以下三方面的协调能力∶互斥、同步和确定对方的存在。

• 管道/缓冲区大小是一定的。
• 读进程可能比写进程快，read()可能会被阻塞。
• 从管道读数据是一次性操作，数据一旦被读取，它就从管道中被抛弃，释放空间以便写更多的数据。
• 管道只能采用半双工通信，即某一时刻只能单向传输。要实现父子进程双方互动通信，需要定义两个管道。
• 只要管道中有数据，就不能写入，write()可能会阻塞；只要管道中有数据，就可以读出。

6.线程

(1)线程的概念

  线程最直接的理解就是"轻量级进程"，它是一个基本的CPU执行单元，也是程序执行流的最小单元，由线程ID、程序计数器、寄存器集合和堆栈组成。线程自己不拥有系统资源(只有一点必不可少的)，但它可与同属一个进程的其他线程共享进程所拥有的全部资源。
  一个线程可以创建和撤销另一个线程，同一进程中的多个线程之间可以并发执行。由于线程之间的相互制约，致使线程在运行中呈现出间断性。线程也有就绪、阻塞和运行三种基本状态。
  引入线程后，进程的内涵发生了改变，进程只作为除 CPU外的系统资源的分配单元，而线程则作为处理机的分配单元。 由于一个进程内部有多个线程，若线程的切换发生在同一个进程内部，则只需要很少的时空开销。

  为什么线程的提出有利于提高系统并发性?可以这样来理解∶由于有了线程，线程切换时，有可能会发生进程切换，也有可能不发生进程切换，平均而言每次切换所需的开销就变小了，因此能够让更多的线程参与并发，而不会影响到响应时间等问题。

(2)线程与进程的比较

• 调度和拥有资源： 线程是独立调度的基本单位，进程是拥有资源的基本单位。进程间相互独立，同一进程的线程间共享资源。
• 并发性： 进程间可并发，线程间可并发，使操作系统具有更好的并发性，提高了系统的吞吐量。
• 系统开销： 以线程为调度单位，减小了系统开销，因此这些线程之间的同步与通信非常容易实现，甚至无须操作系统的干预。
• 通信： 进程间通信要保证同步和互斥，线程间通信可通过进程的全局变量来通信。

(3)多线程模型

• 多对一模型

线程管理在用户态中，对操作系统/核心态不可见，效率比较高。
一个线程在使用内核服务时被阻塞，整个进程都会被阻塞;多个线程不能并行地运行在多处理机上，并发性差。

• 一对一模型

一个线程阻塞后，不影响别的线程，并发能力强。
系统开销大，影响程序性能。

• 多对多模型

克服了上面两种的缺点，又兼具它们的优点。

二、处理机调度

  处理机调度是对处理机进行分配，即从就绪队列中按照一定的算法（公平、高效）选择一个进程并将处理机分配给它运行，以实现进程并发地执行。处理机调度是多道程序操作系统的基础，是操作系统设计的核心问题。

1.调度的层次

  一个作业从提交开始直到完成，往往要经历以下三级调度：

• 作业调度/高级调度(进程的创建与消灭)：

  主要任务是按一定的原则从外存上处于后备状态的作业中挑选一个或多个作业，分配资源，并建立相应的进程。简言之，作业调度就是内存与辅存之间的调度。对于每个作业只调入一次、调出一次。
  多道批处理系统中大多配有作业调度，而其他系统中通常不需要配置作业调度。作业调度的执行频率较低，通常为几分钟一次。

• 中级调度/内存调度(管理就绪态的进程)：

  其作用是提高内存利用率和系统吞吐量，应将那些暂时不能运行的进程调至外存等待，把此时的进程状态称为挂起态。当它们已具备运行条件且内存又稍有空闲时，由中级调度来决定把外存上的那些已具备运行条件的就绪进程，再重新调入内存，并修改其状态为就绪态，挂在就绪队列上等待。

• 进程调度/低级调度(从就绪态中唤醒进程)：

  主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度的频率很高，一般几十毫秒一次。

• 三级调度的关系：

  作业调度从外存的后备队列中选择一批作业进入内存，为它们建立进程，这些进程被送入就绪队列，进程调度从就绪队列中选出一个进程，并把其状态改为运行态，把CPU分配给它。中级调度是为了提高内存的利用率，系统将那些暂时不能运行的进程挂起来。当内存空间宽松时，通过中级调度选择具备运行条件的进程，将其唤醒。

①作业调度为进程活动做准备，进程调度使进程正常活动起来，中级调度将暂时不能运行的进程挂起，中级调度处于作业调度和进程调度之间。
②作业调度次数少，中级调度次数略多，进程调度频率最高。
③进程调度是最基本的，不可或缺。

2.调度的时机、切换与过程

  进程调度发生在操作系统内核中，请求调度的事件发生后，才可能运行进程调度程序。

• 现代操作系统中，不能进行进程的调度与切换的情况有以下几种∶

  ①在处理中断的过程中。
  ②进程在操作系统内核程序临界区中。注意是操作系统内核程序临界区，不是所有的临界区。
  ③其他需要完全屏蔽中断的原子操作过程中。

  若在上述过程中发生了引起调度的条件，则不能马上进行调度和切换，应置系统的请求调度标志，直到上述过程结束后才进行相应的调度与切换。

• 应该进行进程调度与切换的情况如下∶

  ①发生引起调度条件且当前进程无法继续运行下去时，可以马上进行调度与切换。若操作系统只在这种情况下进行进程调度，则是非剥夺调度。
  ②中断处理结束或自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志，即可马上进行进程调度与切换。若操作系统支持这种情况下的运行调度程序，则实现了剥夺方式的调度。

  进程切换往往在调度完成后立刻发生，它要求保存原进程当前切换点的现场信息，恢复被调度进程的现场信息。现场切换时，操作系统内核将原进程的现场信息推入当前进程的内核堆栈来保存它们，并更新堆栈指针。内核完成从新进程的内核栈中装入新进程的现场信息、更新当前运行进程空间指针、重设PC寄存器等相关工作之后，开始运行新的进程。

3.进程调度方式

• 非剥夺式/非抢占式：

  非剥夺调度方式是指当一个进程正在处理机上执行时，即使有某个更为重要或紧迫的进程进入就绪队列，仍然让正在执行的进程继续执行，直到该进程完成或发生某种事件而进入阻塞态时，才把处理机分配给更为重要或紧迫的进程。
  这种方式的优点是实现简单、系统开销小，适用于大多数的批处理系统，但它不能用于分时系统和大多数的实时系统。

• 剥夺方式/抢占方式：

  剥夺调度方式是指当一个进程正在处理机上执行时，若有某个更为重要或紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给这个更为重要或紧迫的进程。
  采用剥夺式的调度，对提高系统吞吐率和响应效率都有明显的好处。但"剥夺"不是一种任意性行为，必须遵循一定的原则，主要有优先权、短进程优先和时间片原则等。

4.与调度相关的一些性能指标

• CPU利用率： 尽可能让CPU忙起来，提高利用率。
• 系统吞吐量： 单位时间CPU完成作业的数量。
• 周转时间： 指从作业提交到作业完成所经历的时间，是作业等待、在就绪队列中排队、在处理机上运行及进行输入/输出操作所花费时间的总和。

周转时间 = 作业完成时间-作业提交时间
平均周转时间=（作业1的周转时间 +…+作业n的周转时间）/n
带权周转时间=作业周转时间/作业实际运行时间
平均带权周转时间=（作业1的带权周转时间+…+作业n的带权周转时间）/n

• 等待时间： 指进程处于等处理机状态的时间之和，等待时间越长，用户满意度越低。处理机调度算法实际上并不影响作业执行或输入/输出操作的时间，只影响作业在就绪队列中等待所花的时间。因此，衡量一个调度算法的优劣，常常只需简单地考察等待时间。
• 响应时间： 指从用户提交请求到系统首次产生响应所用的时间。在交互式系统中，从用户角度来看，调度策略应尽量降低响应时间，使响应时间处在用户能接受的范围之内。

5.调度算法

• 先来先服务调度算法FCFS

  FCFS调度算法属于不可剥夺算法，不能作为分时系统和实时系统的主要调度策略。但它常被结合在其他调度策略中使用。例如，在使用优先级作为调度策略的系统中，往往对多个具有相同优先级的进程按 FCFS 原则处理。
  FCFS调度算法的特点是算法简单，但效率低；对长作业比较有利，但对短作业不利（相对SJF和高响应比）;有利于CPU繁忙型作业，而不利于I/O繁忙型作业。

  为什么FCFS有利于CPU繁忙型作业，而不利于I/O繁忙型作业?
  因为CPU繁忙型进程长时间占用cpu很少有I/O操作，一旦获得cpu，就会运行很长时间，就会长时间占用cpu，而I/O繁忙型由于要频繁访问IO端口，每次访问都要放弃cpu，等I/O访问完后要重新等待下一次调度（此时排到了就绪队列的队尾），所以要等待很久才能重新被调度。因此先来先服务有利于cpu繁忙型而不利于I/O繁忙型。

• 短作业优先调度算法SJF/短进程优先调度算法SPF

  优先调度短的作业/进程。
  对长作业不利；不能保证紧迫性作业会被及时处理；时间估计可能不准确，不一定能真正做到短作业优先调度。
  SJF调度算法的平均等待时间、平均周转时间最少。

• 优先级调度算法

  优先级用于描述作业运行的紧迫程度。
  优先级调度算法分为剥夺式优先级调度算法、非剥夺式优先级调度算法。
  根据优先级是否可变，又分为动态优先级(可根据占用CPU时间、等待CPU时间调整)、静态优先级(依据是进程类型、进程对资源的要求、用户要求)。

  进程优先级的设置可以参照以下原则∶
  系统进程>用户进程。
  交互型进程>非交互型进程（或前台进程>后台进程）
  I/O型进程>计算型进程。I/O处理比CPU慢很多。

• 高响应比优先调度算法

  高响应比优先调度算法主要用于作业调度，是对FCFS调度算法和SJF调度算法的一种综合平衡，同时考虑了每个作业的等待时间和估计的运行时间。

  作业的等待时间相同时，要求服务时间越短，响应比越高，有利于短作业。
  要求服务时间相同时，作业的响应比由其等待时间决定，等待时间越长，其响应比越高，因而它实现的是先来先服务。
  对于长作业，作业的响应比可以随等待时间的增加而提高，等待时间足够长时，其响应比便可升到很高，从而也可获得处理机。因此，克服了饥饿状态，兼顾了长作业。

• 时间片轮转调度算法

  时间片轮转调度算法主要适用于分时系统。按照先来先得的原则依次轮时间片。是绝对可抢占的。
  时间片的长短不宜太长或太短，通常由以下因素确定∶系统的响应时间、就绪队列中的进程数目和系统的处理能力。

• 多级反馈调度算法(融合了前几种算法的优点)

  实现思想如下∶
  ①设置多个就绪队列，并为各个队列赋予不同的优先级，第1级队列的优先级最高，第2
级队列次之，其余队列的优先级逐次降低。
  ②赋予各个队列中进程执行时间片的大小各不相同。在优先级越高的队列中，每个进程的运行时间片越小。例如，第2级队列的时间片要比第1级队列的时间片长1倍·……第i+1级队列的时间片要比第i级队列的时间片长1倍。
  ③一个新进程进入内存后，首先将它放入第1级队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统;若它在一个时间片结束时尚未完成，调度程序便将该进程转入第2级队列的末尾，再同样按FCFS 原则等待调度执行;若它在第2级队列中运行一个时间片后仍未完成，再以同样的方法放入第3 级队列……如此下去，当一个长进程从第1级队列依次降到第n级队列后，在第n级队列中便采用时间片轮转的方式运行。
  ④仅当第1级队列为空时，调度程序才调度第2级队列中的进程运行;仅当第1～（i-1）级队列均为空时，才会调度第i级队列中的进程运行。若处理机正在执行第i级队列中的某进程，这时又有新进程进入优先级较高的队列【第1～（i-1）中的任何一个队列】，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回第i级队列的末尾，把处理机分配给新到的更高优先级的进程。

  优点是：不用预先估计作业的时间；短作业优先；周转时间短；长作业不会饥饿。

三、进程同步

四、死锁

附：王道选择题笔记

1.关于线程的叙述：
线程包含CPU现场，可以独立执行程序。
线程没有自己独立的地址空间，只共享同一进程的资源。
用户级线程的切换不一定需要内核的支持。
引入线程不会增加程序执行的时空开销，反而会减少。
统一进程内、不同进程间的线程都可以并发执行。
错误说法：操作系统为每个用户级线程建立一个线程控制块，这属于一对一模型，不一定的。

2.关于进程的叙述：
进程获得处理器运行是通过调度得到的。
如果没有线程的概念，可以说进程是系统进行资源分配和调度的独立单元。
可能唤醒进程的事件：I/O结束、某进程退出临界区等等。

3.进程实体各组成部分：
PCB：进程描述和管理信息、资源分配清单、处理机资源信息
共享正文段：常量值、全局变量
数据堆段：动态分配存储区
数据栈段：实参传递值、未赋值的局部变量

4.同一程序经多次创建，运行在不同的数据集上，形成了不同的进程。
系统线程被不同进程所调用，他们是相同的线程。

5.若就绪队列不空，就绪的进程数目越多，处理器的效率不变。

6.降低进程优先级的合理时机：进程时间片用完，可降低其优先级以让其他进程被调度进入执行状态。

7.有以下进程需要调度执行：

若用非抢占式短进程优先调度算法，问这5个进程的平均周转时间是：10.62
若用抢占式短进程优先调度算法，问这5个进程的平均周转时间是：6.8

8.一个多道批处理系统中仅有P和P2两个作业，P2比P晚5ms到达，它的计算和I/O操作顺序如下∶
P1∶计算60ms，I/O 80ms，计算20ms
P2∶计算120ms，I/O40ms，计算40ms
若不考虑调度和切换时间，则完成两个作业需要的时间最少是（260ms）。

9.关于处理机调度的叙述：
在进程结束时、创建进程后、系统调用完成用户态时、进程处于临界区时，能进行处理机调度。

10.关于导致饥饿现象的调度算法：
短任务无论是抢占式还是非抢占式，都会导致长作业饥饿。
时间片轮转绝不会导致饥饿现象。
优先数调度可能会导致饥饿现象。

11.某系统采用基于优先权的非抢占式进程调度策略，完成一次进程调度和进程切换的系统时间开销为1us。在T时刻就绪队列中有3个进程P、P2和P2，其在就绪队列中的等待时间、需要的CPU时间和优先权如下表所示。若优先权值大的进程优先获得CPU，从T时刻起系统开始进程调度，则系统的平均周时间为（75us）。

由优先权可知，进程的执行顺序为P2→P3→P1。P2的周转时间为1＋15＋24=40us;Ps的周转时间为18＋1＋24＋1＋36=80us;P1的周转时间为30＋1＋24＋1＋36＋1＋12=105us;平均周转时间为（40＋80＋105）/3=225/3=75us。

12.系统采用二级反馈队列调度算法进行进程调度。就绪队列Q采用时间片轮转调度算法，时间片为10ms;就绪队列Q2采用短进程优先调度算法;系统优先调度Q1队列中的进程，当Q1为空时系统才会调度Q2中的进程;新创建的进程首先进入Q1;Q1中的进程执行一个时间片后，若未结束，则转入Q2。若当前Q1，Q2为空，系统依次创建进程P，P2后即开始进程调度，P1，P2需要的CPU时间分别为30ms和20ms，则进程P1，P2在系统中的平均等待时间为（15ms）。
进程P1，P2依次创建后进入队列Q1，根据时间片调度算法的规则，进程P1，P2将依次被分配10ms的CPU时间，两个进程分别执行完一个时间片后都会被转入队列Q2，就绪队列Q2采用短进程优先调度算法，此时P1还需要20ms的CPU时间，P2还需要10ms的CPU时间，所以P2 会被优先调度执行，10ms后进程P2执行完成，之后P1再调度执行，再过20ms后P1也执行完成。运行图表述如下。

进程P，P2的等待时间分别为图中的虚横线部分，平均等待时间=（P，等待时间 +P2等待时间）/2=（20＋ 10）/2=15。