第二章 进程与线程

2.1进程的概念、组成与特征

2.1.1 进程与程序的区别

​ 1.程序：静态的，就是放在磁盘里的可执行文件，如：QQ.exe。

​ 2.进程：动态的，是程序的一次执行过程，如：可同时启动多次QQ程序。

​ 在多道程序环境下，程序的执行属于并发执行，因此它们会失去封闭性，即系统的各种资源将会被它们所共享，而这些资源的状态也会由这些程序来改变，致使其中任一程序正在执行时，其执行环境必将会收到其他程序的影响。封闭性表示了程序在执行过程中不管是连续执行还是间断执行，程序的执行速度都不会改变它的执行结果，而此时失去封闭性意味着程序的计算结果会与执行速度有关。换言之，程序经过多次执行后，虽然多次执行的环境和初始条件相同，但得到的结果却各不相同。

2.1.2 进程的组成

​ 为了使参与并发执行的每个程序都能独立运行，操作系统为其配置了一个专门的数据结构——进程控制块（process control block，PCB），OS需要对各个并发运行的进程进行管理，但凡管理时所需要的信息都会被存放在PCB中。

​ 由程序段（程序代码）、相关数据段（运行过程中产生的各种数据）和PCB共同构成进程实体（或进程映像），一般情况下进程实体简称为进程，如：所谓创建进程实际上是指创建进程的PCB，同理撤销进程也就是撤销进程的PCB。因此PCB是进程存在的唯一标志。

​ 引入进程概念后，我们将OS中的进程定义为：进程是程序的执行过程，是系统进行资源分配和调度的一个独立单位。

2.1.3 进程的特征

​ （1）动态性 进程是程序的执行过程，是动态地产生、变化和消亡的

​ （2）并发性 多个进程共存于内存中，且能在同一段时间内同时执行

​ （3）独立性 指进程是一个能够独立运行、独立获得资源、独立接收调度的基本单位

​ （4）异步性 各个进程按各自独立的、不可预知的速度向前推进。为了使进程在并发执行时虽具有异步性，但仍能保证进程并发执行的结果是可再现的，在OS中引入了进程的概念，并且配置了相应的进程同步机制

2.1.4 小结

2.2进程的状态与转化

2.2.1 进程的状态与转化

1.进程的状态

​ 一般而言每个进程至少应处于3种基本状态之一：①就绪态②执行态③阻塞态

​ ①就绪态 进程已处于准备好执行的状态，即进程已分配到除CPU以外的所有必要资源后，只要再获得CPU，即可立刻执行。若系统中有许多处于就绪态的进程，则通常会将它们按照一定的策略排列成一个队列，即就绪队列。

​ ②执行态 指进程获得CPU后其程序“正在执行”这一状态。对任何一个时刻而言，在单处理机系统中，只有一个进程处于执行状态，而在多处理机系统中，则可能会有多个进程处于执行状态。

​ ③阻塞态 正在执行的进程由于发生某事件（如I/O请求、申请缓冲区失败等）而暂时无法继续执行，即指进程的执行受到了阻塞。此时会引发进程调度，OS会把处理机分配给另一个就绪进程，而让受阻进程处于暂停状态，即阻塞态。实际上，在较大的系统中，为了减少阻塞队列操作开销，提高系统效率，根据阻塞原因的不同，会设置多个阻塞队列。

​ 当然为了满足进程控制块对数据域操作的完整性要求以及增强管理的灵活性，通常会在系统中为进程引入另外两种常见的状态：①创建态②终止态

​ ①创建态 创建进程时，首先需要申请一个空白PCB，并向PCB中填写用于控制和管理进程的信息，然后为该进程分配运行时所需必要资源；最后将该进程的状态转化为就绪态并插入就绪队列中。但若进程所必须的资源尚不能得到满足，如系统没有足够的内存来存储进程，此时，创建工作就无法完成，进程不能被调度运行，因此，进程此时所处状态为创建态。

​ 引入创建态是为了保证进程的调度必须在创建工作完成后进行，以确保PCB操作的完整性，当进程获得了必须的资源，并完成了对PCB的初始化工作后，便可由创建态转入就绪态。

​ ②终止态 当一个进程运行完成，或者出现错误或异常，被OS或是其他有终止权的进程所终止时就会进入终止态。首先，等待OS进行善后处理，然后将进程PCB清零，并将PCB空间返还OS。进入终止态的进程将不会再被执行，但在OS中依然会保留一个纪录，其中会保存状态码和一些计时系统数据以供其他进程收集。一但其他进程完成了对其信息的提取，系统就会删除该进程，即将其PCB清零，并将该空白PCB返还OS。

2.进程状态间的转换

2.2.2 进程管理中的数据结构

1.OS中用于管理资源和控制进程的数据结构

​ 计算机系统中存在资源信息表和进程信息表，其中包含了资源和进程的标志、描述、状态等信息及一些指针，通过这些指针可以将同类资源和进程信息表，或者同一进程所占用的资源信息表分类链接成不同的队列便于OS查找。OS管理的这些控制表一般可以分为：内存表、设备表、文件表和用于进程管理的进程表，通常进程表又被称为PCB。

2.PCB的组织方式

​ PCB常用的组织方式有以下3种：

（1）线性方式 所有PCB都组织在一张线性表中，如下图所示。该表的起始地址存放在内存的一个专用区域中。适合进程数目不多的系统

（2）链接方式 通过PCB中链接字将具有相同状态的进程的PCB分别链接成一个队列，如下图所示。这样即可形成就绪队列、若干个阻塞队列和空闲队列等。对于就绪队列，其往往会按进程的优先级将PCB从高到低进行排列，优先级高的进程PCB被排在前列。同样的，也可根据阻塞原因的不同，把处于阻塞状态的进程PCB排成多个阻塞队列。

（3）索引方式 系统根据进程状态的不同，建立几张索引表，如就绪索引表、阻塞索引表等，并把各个索引表在内存中的起始地址记录在内存的一些专用单元中。在每个索引表的表目中，记录具有相应状态的某个PCB在PCB表中的地址。如下图所示。

2.2.3 小结

2.5.1 调度的基本概念及层次

​ 调度在多道程序系统中指的就是一种资源分配；当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序，这就是“调度”研究的问题。如：银行为客户的服务，银行就是处理机，客户就是待分配资源的进程，对于一般客户而言，银行对其的服务遵循先来先服务的原则；当然也可以根据客户所需服务时间长短，由时间短到长的排列进行服务。如果此时有一个重要的VIP客户到来，那么银行就可以选择先对这位重要的客户进行先服务，即插队。

1.高级调度

​ 高级调度（high level scheduling）又称长程调度或作业调度，其调度对象为作业。所谓作业实际上就是指一个具体任务，它不仅包含通用的程序和数据，并且配有一份作业说明书，系统会根据该说明书对程序的运行进行控制。如：用户向系统提交一个作业就相当于是用户请求系统运行某个程序来处理某个具体的任务。然后系统就会依据某种算法，决定将外存中处于后备队列的某些作业调入内存中，并为其创建PCB（创建进程、分配资源等），然后将其放入就绪队列。每个作业只被调入一次和调出一次，调入时创建PCB，调出时撤销PCB。高级调度主要用于多道批处理系统中。

2.低级调度

​ 低级调度（low level scheduling）又称短程调度或进程调度，其调度对象为进程。依据某种算法，决定就绪队列中的某个进程可以获得处理机的服务，由分派程序将处理机分配给选中的进程。低级调度是最基本的一种调度，且调度频率很高，在多道批处理、分时和实时系统中都必须配置。

3.中级调度

​ 中级调度（intermediate scheduling）又称内存调度，可以提高内存利用率和系统吞吐量。当内存不足时，可以将某些不能运行的进程调至外存等待，此时进程处于挂起状态。当它们具有运行条件或者内存稍有空闲时，再有中级调度来决定把外存上已经具备运行条件的就绪进程重新调入内存，并修改为就绪态，并挂在就绪队列等待。一个进程可能会被多次调出和调入，因此，中级调度的调度频率要比高级调度高。

4.挂起状态

​ 当挂起态作用于某个进程时，该进程就会被挂起，即意味着此时该进程处于静止状态，当引入挂起操作后，进程状态之间的转换如下图所示：

三种调度的联系与对比：

调度方式	内容	场地	发生频率	对进程状态的影响
高级调度（作业调度）	按照某种规则，将外存后备队列中的某个作业调入内存，并为其创建进程	外存→内存（面向作业的调度）	最低	无→创建态→就绪态
中级调度（内存调度）	按照某种规则，从挂起队列中选择合适的进程调回内存	外存→内存（面向进程的调度）	中等	挂起态→就绪态（或阻塞挂起→阻塞态）
低级调度（进程调度）	按照某种规则，从就绪队列中选择一个进程为其分配处理机	内存→CPU	最高	就绪态→运行态

2.5.2 知识点总结与回顾

2.5.3 进程调度

1.进程调度概念

进程调度有狭义和广义两个概念：

​ （1）狭义的进程调度指的是从就绪队列中选中一个要运行的进程。

​ （2）广义的进程调度包含选择一个进程与进程切换两个部分。

​ 进程切换指的是一个进程让出处理机让另一个进程上处理机运行的过程，在这个过程中主要完成两件事：（1）对原来运行进程的运行环境进行保存（2）对新进程的运行环境进行恢复。当然进程的切换是有代价的，若过于频繁的进行进程的调度、切换，必然会使整个系统的效率降低，因为系统大部分时间都花在了进程切换上，真正用于执行进程的时间减少了。

​ 这里运行环境指：程序计数器、程序状态字、各种数据寄存器等处理机现场信息。他们主要被保存在进程控制块（PCB）中。

2.进程调度的任务

​ 进程调度有三个任务：

①保存CPU现场信息。在进行进程调度时，首先需要保存当前进程的CPU信息，如程序计数器、多个通用寄存器中的内容，便于在进程恢复运行时能够还原当时的运行环境。

②按照某种算法选择进程。调度程序按照某种算法在就绪队列中选择一个进程，将其状态改为运行态，并把CPU分配给它。

③把CPU分配给进程。由分派程序把CPU分配给该进程，此时需要将选中进程的PCB内有关CPU的现场信息装入CPU相应的各个寄存器中，并把CPU的控制权交给该进程，使其能够从上次的断点恢复运行。

​ 当进程状态的转换的过程是由调度程序引起的，调度程序可以决定：哪个进程可以上处理机运行（调度算法）、能运行多久（时间片大小）。那么什么样的事件会触发调度程序的工作（调度时机）？主要有以下几种情况：

• 创建新进程。此时调度程序会来检查是否让新进程上处理机运行。
• 进程退出。调度程序需要从就绪队列中选择一个合适的进程上处理机运行。
• 运行进程阻塞。由于正在运行的进程进入阻塞态，此时调度程序需要选择一个新进程上处理机运行。
• I/O中断发生（可能唤醒某些阻塞态进程）。此时由于进程从阻塞态转变为就绪态，就绪队列发生改变，调度程序就需要决定是否让其上处理机运行。
• 非抢占式调度策略 只有运行进程阻塞或退出才触发调度程序工作
• 抢占式调度策略 每个时钟中断或k个时钟中断会触发调度程序工作

3.进程调度机制

​ 进程调度机制示意图如下图所示，其包含3个基本部分：

（1）排队器。为了提高进程的效率，应事先将系统重的就绪进程，按照一定的策略排成一个或多个队列，以便调度程序能尽快找到它们。后续每当有一个进程切换为就绪态，排队器就可以将其插入相应的就绪队列。

（2）分派器。分派器将进程调度程序所选定的进程从就绪队列中取出，然后进行从分派器到新选进程间的上下文切换，将CPU分配给新选进程。其中，上下文指的是进程执行时的运行环境状态。

（3）上下文切换器。在对处理机进行切换时，会发生两对上下文的切换操作：

​ ①第一对上下文切换时，OS会将当前运行进程的上下文，即运行环境保存到该进程PCB的相应单元中，而装入分派程序的上下文，则可以方便分派程序运行。

​ ②第二对上下文切换是移出分派程序的上下文，把新选进程的上下文，即运行环境载入CPU的各个相应寄存器中，以便新选进程的运行。

4.进程调度方式

（1）非抢占调度方式

​ 当前运行的进程主动放弃处理机，如：进程正常终止、进程运行过程发生异常而终止、进程主动请求阻塞（等待I/O）等。采用这种调度方式，进程会一直占用处理机。

（2）抢占调度方式

​ 当前运行的进程被动放弃处理机，如：时间片用完、有更紧急的事情需要处理、有更高优先级的进程进入就绪队列等。采用这种调度方式可以防止一个进程长时间的占用处理机，以确保处理机能为所有进程提供更为公平的服务。

​ 抢占式也需遵循一定的原则：①优先级原则 当有新进程到达时，如果其优先级比当前进程优先级更高，则调度程序会剥夺当前进程的运行，并将处理机分配给新进程。②短进程优先原则 当新到进程比当前进程（还需运行的时间）明显短时，将处理机分配到新的短进程。③时间片原则 一个正在执行的进程用完其时间片后，便会终止该进程的执行而重新进行调度。

5.进程调度的时机

​ 进程在操作系统内核程序临界区中不能进行调度与切换

​ 进程在临界区时可以进行处理机调度

​ 上述操作系统内核程序临界区和临界区是不同的，首先引入一个临界资源的概念，其是一个时间段内只允许一个进程使用的资源，各个进程之间需要互斥访问临界资源。临界区是指一段访问共享资源（如全局变量、硬件设备、数据结构等）的代码区域。在并发环境中，如：多线程或多处理机系统中若执行多个单元（线程、进程等）同时进入临界区，可能会导致竞态条件，从而引发数据不一致或系统崩溃。

​ 对于操作系统内核临界区，如：当一个进程正在内核程序临界区访问就绪队列，此时就绪队列会被上锁，若进程一直在访问，还没退出就进行进程调度，此时进程调度相关的程序也需要访问就绪队列，而就绪队列是上锁的，因此无法顺利进行进程调度。此时若不尽快释放内核程序临界访问的临界资源，可能会影响到操作系统内核的其他管理工作。因此在访问内核程序临界期间不能进行进程调度与切换。

​ 对于普通临界区，如进程正在访问外设如打印机设备，在打印机打印完成之前，进程一直处于临界区内，若此时临界资源给打印机上锁，由于打印机是慢速设备，若一直不允许进程调度就会导致CPU一直被占用而处于空闲状态。此外普通临界区访问的临界资源不会直接影响操作系统内核的管理工作。因此在访问普通临界区时可以进行进程的调度与切换。

2.5.4 处理机调度算法的目标

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

​ （1）资源利用率 为了提高系统的资源利用率，应使系统中的处理机和其他所有资源都尽可能的保持忙碌状态，其中最重要的资源便是CPU的利用率：

​ $$CPU利用率=\frac{CPU有效工作时间}{CPU有效工作时间+CPU空闲等待时间}$$

​ （2）公平性 应使各个进程都获得合理的CPU时间，以防发生进程饥饿现象，值得注意的是公平是相对的，相同类型的进程应获得相同的服务；对于不同的进程，由于它们的紧急程度或重要性不同，为它们提供的服务也会不同。

​ （3）策略强制执行 对于制定的策略，只要需要就必须执行。

2.批处理系统中处理机调度算法的目标

​ （1）系统吞吐量高 系统吞吐量指的是单位时间内系统完成的作业数，对于计算机而言，希望能用尽可能少的时间完成尽可能多的作用。系统吞吐量公式表示为：

​ $$系统吞吐量=\frac{总共完成了多少道作业}{总共花了多少时间}$$

​ （2）平均周转时间 指的是从作业被提交给系统开始到作业完成为止的这段时间间隔，包括4部分：作业在外存后备队列上等待作业调度的时间，进程在就绪队列等待进程调度的时间（就绪态），进程在CPU上运行所耗费的时间（运行态），及进程等待I/O操作完成的时间（阻塞态）。后三项在一个作业的整个处理过程中可能会发生多次。

​ 对于用户而言，他们都希望自己的作业周转时间最短。但作为计算机系统的管理者，则希望作业的平均周转时间最短，这不仅可以有效提高系统资源的利用率，还可以使大部分用户感到满意。平均周转时间用公式表示为：

​ $$\text{平均周转时间}=\frac{\text{各作业周转时间之和}}{\text{作业数}}$$

​ 然而有的作业运行时间长，有的运行时间短，因此实际情况下，计算机系统的管理者会使作业的周转时间和作业的平均周转时间都尽可能短，否则，等待时间过长会引起特别是短作业用户的不满。为了进一步反应调度的性能，更清晰地描述各个进程在周转时间中“等待时间和执行时间”的具体分配情况，引入带权周转时间：

​ $$带权周转时间=\frac{作业周转时间}{作业实际运行的时间}=\frac{作业完成时间-作业提交时间}{作业实际运行的时间}$$

由于作业周转时间中包含着作业实际运行时间，因此，带权周转时间必然≥1，同时周转时间和带权周转时间都是越小越好。对于周转时间相同的两个作业，实际运行时间长的作业在相同时间内被服务的时间更多，带权周转时间更小，用户满意度更高。对于实际运行时间相同的两个作业，周转时间短的带权周转时间更小，用户满意度更高。

​ （3）等待时间 指的是进程或作业处于等待处理机状态的时间之和，等待时间越长，用户满意度越低。

​ 对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间。

​ 对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。

​ （4）响应时间 对于计算机用户来说，会希望自己的提交的请求（比如通过键盘输入了一个调试命令）尽早地开始被系统服务、回应。因此，响应时间指从用户提交请求到首次产生响应所用的时间。

2.5.5 小结

2.6 调度算法

2.6.1 先来先服务

先来先服务（first come first server，FCFS）即可用于作业调度，也可用于进程调度，是一种非抢占式算法。
当作业调度采用该算法时，OS按照作业到达的先后顺序进行调度，或者说OS会优先考虑在系统中等待时间最长的作业，无论执行时间长短，选择作业将它们调入内存，并为其分配资源和创建进程，然后放入就绪队列。
当进程调度采用该算法时，OS会按照进入就绪队列进程的顺序，为其分配处理机，使之运行。该进程已知运行到完成或者发生某事件而阻塞后，进程调度程序才会将处理机分配给其他进程。