《操作系统原理与实践教程(第二版)》第3章： 进程同步与死锁

第3章进程同步与死锁3.1进程的引入3.2进程的概念3.3进程控制3.4线程3.5处理器调度3.6调度算法3.7多处理器调度和实时调度3.1.1程序的顺序执行在早期的单道程序计算机系统中，一次只能运行一个程序，当有多个程序需要运行时，程序的执行方式必须是顺序的，即必须在一个程序执行完成之后，才允许执行另一个程序。程序段的顺序执行示意图：I1P2C2I2P1C13.1.1程序的顺序执行程序顺序执行的特征如下：顺序性。处理机在执行程序时，严格按照程序所规定的顺序执行，即每一操作都必须在下一操作开始之前完成。封闭性。程序一旦开始运行就独占系统资源，只有本程序才能改变资源的状态，执行结果不受外界条件的影响。可再现性。只要初始条件和运行环境相同，多次执行同一程序，都会得到相同的结果。3.1.2程序的并发执行程序的顺序执行降低了计算机系统的整体处理能力，使系统资源得不到充分利用，效率低下。为了提高计算机系统的资源利用率，现代计算机普遍采用并发操作，即若干个程序段同时在系统中运行，这些程序段的执行在时间上是重叠的，当一个程序还未执行结束时，另一个可能已经开始运行了。3.1.2程序的并发执行程序的并发执行可以大大提高系统的吞吐量，具有以下三方面的特征：间断性。为了完成同一项任务而相互合作的多个程序并发执行时，由于互相协调、相互制约会导致“暂停—执行—暂停”的间断性运行规律。失去封闭性。程序在并发执行时，多个程序需要共享系统中的多种资源。所以，这些资源的状态是由多个程序改变的，从而使程序的运行失去了封闭性。不可再现性。程序在并发执行时，由于失去了封闭性，从而导致其失去可再现性。3.2.1进程的定义引入“进程”的原因是为了使程序能够并发执行，并且能对并发的程序加以描述和控制而引入的。一般把进程理解为：“可并发执行且具有独立功能的程序在一个数据集合上的运行过程，它是操作系统进行资源分配和调度的基本单位”。进程是一个程序运行的动态过程，而且该程序必须具有并发运行的程序结构；运行过程必须依赖一个数据集合而独立运行，从而形成了系统中的一个单位。3.2.1进程的定义进程的五大特性：动态性。进程的实质是程序的一次执行过程，是个动态的概念，有一定的生命周期，要经历创建、执行、撤销过程。结构性。它由进程控制块、程序段和数据段组成。并发性。指在一个系统内可以同时存在多个进程，它们通过交替使用处理器，从而实现并发执行。异步性。指进程之间在交替使用计算机资源时没有强制的顺序，按各自独立的、不可预知的速度向前推进。独立性。指进程在系统中是一个可独立运行的、具有独立功能的基本单位，也是系统分配资源和进行调度的独立单位。3.2.1进程的定义进程的分类：系统进程：它们是执行操作系统核心代码的进程，起到对系统资源的管理和控制作用。用户进程：主要是执行用户程序的进程。系统进程和用户进程的区别：(1)系统进程可以独占分配给它们的资源，也能以最高优先级运行；而用户进程需要通过系统服务请求(系统调用)的方式来竞争使用系统资源。(2)用户进程不能直接执行I/O操作，而系统进程可以。(3)系统进程在内核态(管态)下活动，而用户进程则是在用户态(目态)下活动。3.2.1进程的定义进程和程序既有区别也有联系，主要体现在以下几个方面：(1)程序是指令集合，是静态概念。进程是程序在处理机上的一次执行的过程，是动态的概念。(2)进程是一个独立的运行单位，能与其它进程并发(并行)执行。而程序则不可以并发执行。(3)进程是进行计算机资源分配的基本单位，也是进行处理机调度的基本单位。(4)一个程序可以作为多个进程的运行程序，这些进程可以同时存在，而它们使用的是同一程序。3.2.2进程的状态在系统中有多个进程存在时，它们是交替运行的，即进程会执行一段时间、暂停一下、然后再执行一段时间，重复该过程直到执行完毕。进程运行的间断性决定了进程可能具有多种状态。3.2.2进程的状态进程在运行过程中通常有三种基本状态，分别是：(1)就绪状态(Ready)进程已获取到除CPU之外的所有必要资源，只要再得到CPU，就可以马上投入运行，这时进程所处的状态为就绪状态。(2)运行状态(Running)处于就绪状态的进程得到CPU控制权后，就可以使用处理器进行数据运算和处理，而其所处的状态称为运行状态。(3)阻塞状态(Wait)当一个进程正在等待某个事件的发生(如等待I/O的完成)而暂停执行，这时，即使分配有CPU时间，它也无法执行，则称该进程处于阻塞状态，又称等待状态。3.2.2进程的状态进程在执行过程中的状态会不断变化，三种基本状态之间的转换关系如下图所示：某事件发生（如等待I/O完成）运行活动就绪活动阻塞某事件被解除（如I/O完成）分配处理机时间片已用完3.2.2进程的状态在引入挂起状态的操作系统中，又增加了静止就绪和静止阻塞两个新的进程状态。进程状态之间的转换关系如下图所示：某事件发生（如I/O申请）运行活动就绪活动阻塞某事件被解除（如I/O完成）分配处理机时间片已用完某事件被解除（如I/O完成）挂起挂起激活激活创建静止就绪静止阻塞3.2.3进程控制块进程控制块(ProcessControlBlock，PCB)是操作系统为了管理进程而设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程。系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志。进程与PCB是一一对应的。3.2.3进程控制块不同的操作系统对进程的控制和管理机制不同，PCB中的信息多少也不一样。PCB通常包含如下信息：(1)进程标识符。每个进程都必须有一个唯一的标识符。(2)进程当前状态。(3)进程相应的程序和数据地址，以便把PCB与其程序和数据联系起来。(4)进程资源清单。(5)进程优先级。(6)CPU现场保护区。(7)进程同步与通信机制。(8)进程所在队列PCB的链接字。(9)与进程有关的其它信息。如进程记账信息、进程占用CPU的时间等。3.3.1进程控制的概念进程控制是进程管理中的最基本功能。是对系统中所有进程从创建到消亡的全过程实施有效的控制，不但要完成对运行过程中状态转换的控制，还需要能够创建新进程，或者撤销已经执行完毕的进程。进程控制一般由操作系统内核来完成。3.3.2进程控制机构进程的控制机构是由操作系统内核实现的。通常将与硬件密切相关的模块放在紧挨硬件的软件层中，并使它们常驻内存，以提高操作系统的运行效率，通常将这部分称为操作系统内核。操作系统内核为系统对进程进行控制、对存储器进行管理提供了有效的控制机制。3.3.2进程控制机构不同的操作系统内核所包含的功能不同，但大多数操作系统内核都包含支撑功能和资源管理功能。支撑功能：(1)中断处理。操作系统的各种重要活动最终都依赖于中断。(2)时钟处理。(3)原语操作。内核在执行某些操作时，往往是通过原语操作实现的。原语是由若干条机器指令构成的、用于完成特定功能的一段程序。原语在执行过程中是不可分割的。进程控制原语主要有：创建原语、撤销原语、挂起原语、激活原语、阻塞原语以及唤醒原语。3.3.2进程控制机构资源管理功能：(1)进程管理。进程管理的大部分或者全部功能都放在内核中，如进程的调度与分配、进程的创建和撤销。(2)存储器管理。内存的分配和回收、内存保护和对换等功能模块都放在内核中。(3)设备管理：设备驱动程序、缓冲区管理、设备分配等功能都放在内核中。内核中包含的原语主要有：进程控制、进程通信、资源管理以及其它原语。3.3.3进程创建一个进程在执行的过程中可以创建新的进程，通常将这样的进程称为父进程，而将被创建的新进程称为父进程的子进程。子进程还可以再创建子进程，被子进程新创建的进程被称为孙子进程，从而形成进程树，树的根结点是整个进程家族的祖先。祖先根GFEDBAC3.3.3进程创建当子进程被创建时，它可以直接向操作系统申请资源，也可以继承父进程所拥有的资源。当子进程被撤销时，应该把从父进程那里获得的资源还给父进程。当撤销父进程时，应当把它创建的所有子进程也一同撤销。不论是系统还是用户，创建进程的操作必须调用创建原语来实现。3.3.3进程创建创建原语的主要功能：新进程申请获得惟一的数字标示符，并从PCB集合中获取一个空白PCB；为新进程的程序和数据以及用户栈分配必要的内存空间；对PCB进程初始化；将新进程插入就绪队列中，等待被调度执行。3.3.4进程撤销当进程完成任务或在执行的过程中发生异常时，系统将调用进程终止原语来终止该进程。终止进程的过程如下：根据被终止进程的标示符从PCB集合中查找到该进程的PCB，从中读出该进程的状态，终止该进程的执行；如果该进程还有子孙进程，应该将它的所有子孙进程终止，防止它们成为不可控进程；然后回收进程所拥有的资源；最后将被终止进程(它的PCB)从所在队列(或链表)中移出，等待其它程序来搜集信息。3.3.5进程阻塞正在运行的进程由于提出系统服务请求(如I/O操作)，但因为某种原因而未得到操作系统的立即响应，或者需要从其它合作进程获得的数据尚未到达等原因，该进程只能调用阻塞原语把自己阻塞，等待相应的事件出现后才被唤醒。可以看出，进程的阻塞是进程自身的一种主动行为。3.3.6进程唤醒当阻塞进程所等待的事件出现时，比如所需的数据已到达，或者等待的I/O操作已经完成，则由另外的与阻塞进程相关的进程(如用完并释放该I/O设备的进程)调用唤醒原语，将等待该事件的进程唤醒。阻塞进程不能唤醒自己。唤醒原语执行的过程为：首先把被阻塞的进程从等待该事件的队列中移出，将其PCB中的状态由阻塞修改为就绪，然后将该PCB插入到就绪队列中。3.4线程自20世纪60年代推出进程概念后，在操作系统中都是以进程作为独立运行的基本单位。直到20世纪80年代中期，人们又提出了比进程更小的能独立运行的基本单位—线程。目的是提高系统内程序并发执行的程度，从而进一步提高系统的吞吐量。3.4.1线程的概念传统的进程有两个基本属性：可拥有资源的独立单位、可处理器调度和分配的基本单位。引入线程以后，将传统进程的两个基本属性分开，线程作为处理器调度和运行的基本单位，进程作为分配资源的基本单位，可以通过创建线程来完成任务，以减少程序并发执行时付出的时空开销。线程是由线程ID、程序计数器、寄存器集合和堆栈组成。它与同属一个进程的其它线程共享其代码段、数据段和其它操作系统资源(如打开文件和信号)。一个传统的进程只有一个控制线程。如果进程有多个控制线程，那么它就能同时做多个任务。3.4.2线程的特点与状态线程是程序中一个单一的顺序控制流程。在单个程序中可以同时运行多个线程完成不同的工作，称为多线程。多线程是为了同步完成多项任务，通过提高资源使用效率来提高系统的效率。多线程是在同一时间需要完成多项任务的时候实现的。3.4.2线程的特点与状态多线程编程具有以下优点：(1)响应程度高。如果对一个交互式应用程序采用多线程，即使它部分阻塞或执行较冗长的操作，那么，该程序仍然能继续工作，从而提高对用户的响应程度。(2)资源共享。线程默认共享自身所属进程的内存和资源。(3)经济。创建进程所需要的内存和资源的分配比较昂贵，而由于线程允许共享自身所属进程的资源，所以，创建线程和上下文切换会更经济。(4)多处理器体系结构的利用。多线程的优点之一是能充分使用多处理器体系结构，以便每个线程能够并行运行在不同的处理器上。3.4.3线程的实现许多现代操作系统都已实现了线程，但各系统的实现方式并不完全相同.主要分为两种方式：用户级线程和内核级线程。3.4.3线程的实现用户级线程仅存在于用户空间中。用户级线程的创建、撤销、线程间的同步与通信等功能都无需通过系统调用来实现。用户级线程的切换，常常发生在一个应用进程的诸多线程之间，同样也无需内核的支持。由于切换的规则远比进程调度简单，所以线程间的切换速度