操作系统第3章

计算机操作系统第3章进程与线程目录3.1进程概念3.2进程控制3.3线程3.4互斥和同步2预备知识：前趋图前趋图是一个有向无环图（DirectedAcyclicGraph,DAG）3.1进程概念3.1.1程序的顺序执行及其特征1.程序的顺序执行通常可以把一个应用程序分成若干个程序段，各程序段之间必须按照某种先后次序顺序执行，仅当前一程序段（操作）执行完后，才能执行后继程序段（操作）。

63.1.1程序的顺序执行及其特征1.程序的顺序执行

7图3.1多道程序的顺序执行3.1.1程序的顺序执行及其特征2.程序顺序执行的特征（1）顺序性：处理机的操作严格按照程序所规定的顺序执行，即每一操作必须在上一个操作结束之后开始。（2）封闭性：程序是在封闭的环境下执行的，即程序运行时独占整个系统资源，资源的状态（除初始状态外）只有本程序可以改变。（3）可再现性：只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它的执行方式如何，是连续执行，还是“走走停停”的执行，其结果都是相同的。93.1.2程序的并发执行及其特征1.程序的并发执行

为了提高计算机的利用率、处理速度和系统的吞吐量，并行处理技术和并发程序设计技术在计算机中已经得到了广泛应用，成为了现代操作系统的基本特征之一。

10图3.2多道程序并发执行3.1.2程序的并发执行及其特征前趋图的引入：前趋图是一个有向无环（DirectedAcyclicGraph,DAG）考虑具有以下四条语句的一个程序段：

S1:a:=x+2;S2:b:=y+4;S3:c:=a+b;S4:d:=c+b;

11图3.3四条语句的前趋图S1:a:=x+2;S2:b:=y+4;S3:c:=a+b;S4:d:=c+b;S1:a:=x+2;S2:b:=y+4;S3:c:=a+b;S4:d:=c+b;3.1.2程序的并发执行及其特征2.程序并发执行的特征（1）间断（异步）性：程序在并发执行时，由于它们共享系统资源，以及为了完成同一任务而相互合作，致使这些并发程序之间形成了相互制约的关系。（2）失去封闭性：程序在并发执行时，多个程序共享系统中的各种资源，因此，系统资源的状态将由多个程序来改变，致使程序失去了封闭性。

（3）不可再现性：程序在并发执行时，由于失去了封闭性，也将导致其失去执行的可再现性。

14不可再现性下面是两个并发执行的程序A，B，描述如下已有的进程定义：进程是程序的一次执行；进程是可以和别的计算并发执行的计算；进程是定义在一个数据结构上，并能够在其上进行操作的一个程序；进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。3.1.3进程的概念及其特征17我们将进程定义为：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。3.1.3进程的概念及其特征18程序和进程之间的区别与联系：程序是完成特定任务的一组指令的结合，可以永久保存，具有静态性；进程是程序在某一数据结构上的一次执行过程，是系统进行资源分配和调度的基本单位，具有动态性；一个进程可以包含多个程序，一个程序也可以被多个进程执行。3.1.3进程的概念及其特征191.两状态模型包含运行态（Running）和非运行态（Notrunning）两种进程状态创建了一个新进程之后，它会以非运行态加入到系统中，等到操作系统为其分派处理器当前处于运行态的进程会不时地中断，由系统中的分派器选择处于非运行状中的某一个进程运行3.1.4进程状态20（a）

状态变迁图3.1.4进程状态21（b）

排队图3.1.4进程状态22什么在排队是它－－PCB(processcontrolblock)进程控制块（描述进程进关信息的数据结构）2.五状态模型包括就绪态（Ready）、运行态（Running）、阻塞态（Blocked）、新建态（New）和终止态（Terminate）进程状态描述：（1）新建态：刚刚创建的新进程，通常是指进程控制块已经创建，但还没有加载到系统内存中的进程。（2）就绪态：进程等待系统为其分派处理器，而此时处理器被其它进程占据，所以该状态进程不能执行，但已经具备了除处理器之外的进程执行所需要的所有条件。3.1.4进程状态24（3）运行态：进程已获得所需资源并占据处理器，处理器正在执行该进程。（4）阻塞态：也称为等待态、挂起态或睡眠态，进程在等待某个事情的发生而暂时不能运行，例如等待某个I/O操作的完成。（5）终止态：进程或者因为执行结束或者因为被撤销而从可执行进程组中退出。3.1.4进程状态25图3.5五状态模型3.1.4进程状态26进程状态间可能的转换及原因有：新建→就绪：系统纳入一个新进程。就绪→运行：进程被调度程序选中，占据处理器而进入运行状态。运行→终止：进程运行结束或被撤销则退出系统进入终止态。运行→就绪：进程分配的占据处理器的时间片已经用完，或者是具有更高优先级的进程进入系统，当前正在运行的进程被抢占了处理器，此时进程从运行态转换到就绪态。运行→阻塞：进程在等待系统分配资源或者等待某些事件的发生，进程让出处理器由运行态转入阻塞态。阻塞→就绪：处于阻塞队列中的进程等待的资源可用或者等待的事件发生之后，进程从阻塞态转换到就绪态，等待处理器选中它运行。27挂起状态的引入

内存是有限的不能容纳所有的进程，对于内存中的多个进程，处理器依次选中运行，当一个进程正在等待I/O事件发生时，处理器转移到另一个进程。但是，处理器的速度比I/O要快很多，有可能内存中所有进程都在等待I/O事件的完成，导致处理器处于空闲状态。

一种可行的解决问题的办法是引入挂起（Suspend）的概念。3.1.4进程状态28图3.6引入挂起的进程状态转换模型3.1.4进程状态29进程控制块（Processcontrolblock,PCB）是操作系统用来记录进程状态和相关信息，控制进程运行的数据结构，是进程的唯一标识符在PCB中，主要包含如下的信息:3.1.5进程控制块30进程标识符进程状态调度信息程序计数器上下文数据内存指针I/O状态信息进程控制是进程管理中最基本的功能在操作系统中，不同功能都是通过执行各种原语（Primitive）操作实现原语是由若干条指令构成、可完成特定功能的程序段。原语是原子操作，是一个不可分割的基本单元，在执行过程中不会被中断。3.2进程控制31引起进程创建的事件：（1）批处理作业

（2）用户登录

（3）提供服务

（4）进程派生3.2.1进程创建32创建一个新进程的具体步骤：（1）系统为新建进程申请一个空白的进程控制块，获得一个唯一的进程标识符。（2）系统为新建进程分配运行所需的资源，包括：内存、处理器时间、I/O设备等。（3）进程控制块（PCB）初始化。（4）设置链接，如果就绪队列允许新进程插入，则将新进程插入就绪队列。3.2.1进程创建33引起进程终止的事件：（1）正常完成（2）运行超时（3）等待超时（4）内存不足（5）越界错误（6）保护错误（7）算术错误3.2.2进程终止34（8）

I/O错误（9）无效指令（10）特权指令（11）操作员或操作系统干涉（12）父进程请求（13）父进程终止终止原语的具体步骤：（1）根据需要终止进程的进程标识符，从PCB集合中查找对应的进程，从中读出该进程的状态。（2）若被终止进程正处在执行状态，则应立即终止该进程的执行，并设置相应的调度信息，用于指示该进程被终止后应重新进行调度。（3）将被终止进程所拥有的所有资源归还给其父进程，或者归还给系统。3.2.2进程终止35（3）若被终止进程还拥有子孙进程，则将其所有子孙进程一并终止。（4）归还PCB所占据的空间。3.2.2进程终止361.进程阻塞进程阻塞是指进程在执行过程中因等待某个事件的发生或等待某个操作的完成而不得不让出处理器。引起进程阻塞的主要事件有：

（1）请求系统服务。（2）启动某种操作。（3）新数据尚未到达。（4）无新工作可做。3.2.3进程阻塞和唤醒37阻塞原语（Blockprimitive）的具体步骤：

（1）正在执行的进程立即终止执行，把PCB中的进程状态由执行改为阻塞，并将处理机状态写入PCB中。（2）将PCB插入阻塞队列中，等到事件的发生或操作的完成。（3）系统将处理机重新分派给另一就绪进程，按照新进程的处理机状态更新处理机环境，就绪进程开始执行。（4）当被阻塞进程等待的事件发生或者等待的操作完成时，则操作系统会通过唤醒原语将等待该事件的进程唤醒。3.2.3进程阻塞和唤醒382.进程唤醒当被阻塞进程等待的事件发生，如等待的I/O操作已完成，或者等待的操作完成时，则操作系统会通过唤醒原语将等待该事件的进程唤醒。唤醒原语（Wakeupprimitive）的具体步骤：（1）根据进程标识符从等待该事件的阻塞队列中找到需要唤醒的进程PCB。（2）将PCB中的进程状态阻塞改成就绪，并将该进程插入到就绪队列中。3.2.3进程阻塞和唤醒391.进程挂起当系统中出现了引起挂起的事件，如内存资源不足时，操作系统将利用挂起原语将处于阻塞状态的进程挂起。挂起原语（Suspendprimitive）的具体步骤：（1）根据进程标示符，在PCB集合中找到需要挂起的进程。（2）检查挂起进程的状态。3.2.4进程挂起和激活402.进程激活激活，对应于挂起，是让被挂起的进程重新活跃起来，也就是把进程从外存调入到内存中。当系统中出现了引起激活的事件时，操作系统会利用激活原语将挂起进程激活。激活原语（Activeprimitive）的具体步骤：（1）根据进程标示符，在PCB集合中找到需要激活的进程。（2）检查激活进程的状态。3.2.4进程挂起和激活41早期的计算机操作系统中，进程既是资源分配的基本单位，又是调度的基本单位操作系统发展至今，进程在调度中会存在许多问题，增加了调度的难度和开销例如：现代操作系统很重要的一方面是进程的并发执行，然而进程的并发执行使得进程调度的开销日益增大，系统效率明显降低3.3线程42进程包含两方面的特点：

（1）资源所有权，进程是一个可拥有资源的独立单位。（2）调度，进程同时又是一个可独立调度和分派的基本单位。一个进程沿着通过一个或多个程序的一条执行路径执行。执行中可能与其它进程的执行过程交替进行，所以，一个进程具有一个执行状态和一个分派的优先级，同时又是一个能被操作系统调度和分派的实体。3.3.1线程简介43在操作系统中引入进程的目的，是为了使多个程序能并发执行，以提高资源利用率和系统吞吐量。在操作系统中再引入线程，则是为了减少程序在并发执行时所付出的时空开销，使操作系统具有更好的并发性。通常把调度和分派的基本单位称做线程或轻量级进程（Lightweightprocess,LWP）,而把资源分配的基本单位称做进程或者任务。3.3.1线程简介441.多线程概念进程在任一时刻只有一个执行控制流，通常将这种结构的进程称为单线程进程（Singlethreadedprocess）。多线程进程（Multiplethreadedprocess）——同一进程中设计出多条控制流，并且满足：（1）多控制流之间可以并行执行；

（2）多控制流切换不需通过进程调度；（3）多控制流之间可以通过内存直接通信联系，从而降低通信开销。3.3.2多线程45图3.7进程和线程3.3.2多线程46比如每下载一个文件可以单独开一个线程2.多线程环境下的进程和线程（1）多线程环境下的进程在多线程环境中，进程被定义为资源分配的基本单位，与进程相关的有：存放进程映象的虚拟地址空间受保护地对处理器、其他进程、文件和I/O资源的访问3.3.2多线程47（2）多线程环境下的线程一个进程内包含一个或者多个线程，每个线程都包含：线程执行状态当线程处于非运行状态时，有一个受保护的线程上下文，用于存储现场信息一个执行堆栈容纳每个线程的局部变量的存储空间与进程内的其它线程共享访问进程的内存空间和资源3.3.2多线程48线程的主要特性：（1）并发性（2）共享性（3）动态性（4）结构性3.3.2多线程49图3.8单线程和多线程环境下的进程模型3.3.2多线程503.线程状态线程的关键状态有：运行态、就绪态和阻塞态与线程状态转换相关的操作：派生阻塞解除阻塞结束3.3.2多线程51进程与线程的区别:进程和线程的主要差别在于它们是不同的操作系统资源管理方式。进程有独立的地址空间，一个进程崩溃后，在保护模式下不会对其它进程产生影响，而线程只是一个进程中的不同执行路径。线程有自己的堆栈和局部变量，但线程之间没有单独的地址空间，一个线程死掉就等于整个进程死掉，所以多进程的程序要比多线程的程序健壮，但在进程切换时，耗费资源较大，效率要差一些。但对于一些要求同时进行并且又要共享某些变量的并发操作，只能用线程，不能用进程。进程与线程的区别:1)简而言之,一个程序至少有一个进程,一个进程至少有一个线程.2)线程的划分尺度小于进程，使得多线程程序的并发性高。3)进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率。4)从逻辑角度来看，多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理以及资源分配。例如：下载一个文件可以开多个线程。线程和进程的优缺点:线程和进程在使用上各有优缺点：线程执行开销小，但不利于资源的管理和保护；而进程正相反。线程适合于在对称多处理机系统机器上运行，而进程则可以跨机器迁移。引入线程带来的主要好处：主要好处：(1)在进程内创建、终止线程比创建、终止进程要快；(2)同一进程内的线程间切换比进程间的切换要快,尤其是用户级线程间的切换。深入理解进程就是一个程序运行的时候被CPU抽象出来的，一个程序运行后被抽象为一个进程，但是线程是从一个进程里面分割出来的，由于CPU处理进程的时候是采用时间片轮转的方式，所以要把一个大个进程给分割成多个线程。例如：网际快车中文件分成100部分10个线程文件就被分成了10份来同时下载1-10占一个线程11-20占一个线程,依次类推,线程越多,文件就被分的越多,同时下载当然速度也就越快。深入理解进程是程序在计算机上的一次执行活动。当你运行一个程序，你就启动了一个进程。显然，程序只是一组指令的有序集合，它本身没有任何运行的含义，只是一个静态实体。而进程则不同，它是程序在某个数据集上的执行，是一个动态实体。它因创建而产生，因调度而运行，因等待资源或事件而被处于等待状态，因完成任务而被撤消，反映了一个程序在一定的数据集上运行的全部动态过程。进程是操作系统分配资源的单位。在Windows下，进程又被细化为线程，也就是一个进程下有多个能独立运行的更小的单位。线程(Thread)是进程的一个实体，是CPU调度和分派的基本单位深入理解线程和进程的关系

线程是属于进程的，线程运行在进程空间内，同一进程所产生的线程共享同一内存空间，当进程退出时该进程所产生的线程都会被强制退出并清除。线程可与属于同一进程的其它线程共享进程所拥有的全部资源，但是其本身基本上不拥有系统资源，只拥有一点在运行中必不可少的信息(如程序计数器、一组寄存器和栈)。深入理解

在同一个时间里，同一个计算机系统中如果允许两个或两个以上的进程处于运行状态，这便是多任务。现代的操作系统几乎都是多任务操作系统，能够同时管理多个进程的运行。多任务带来的好处是明显的，比如你可以边听mp3边上网，与此同时甚至可以将下载的文档打印出来，而这些任务之间丝毫不会相互干扰。就是说只有一颗心，要让它一心多用，同时运行多个进程，就必须使用并发技术。深入理解-并发技术时间片轮转进程调度算法在操作系统的管理下，所有正在运行的进程轮流使用CPU，每个进程允许占用CPU的时间非常短(比如10毫秒)，这样用户根本感觉不出来CPU是在轮流为多个进程服务，就好象所有的进程都在不间断地运行一样。但实际上在任何一个时间内有且仅有一个进程占有CPU。如果一台计算机有多个CPU，情况就不同了，如果进程数小于CPU数，则不同的进程可以分配给不同的CPU来运行，这样，多个进程就是真正同时运行的，这便是并行。但如果进程数大于CPU数，则仍然需要使用并发技术。1.线程实现（1）用户级线程（Userlevelthread,ULT）

线程管理的所有工作都由应用程序完成，内核意识不到线程的存在。3.3.3线程实现与线程模型61用户级线程方式优点：因为所有线程的管理数据结构都在该进程的用户空间中，因此，线程切换不需要转换到内核空间，从而节省了模式切换的开销。调度算法可以是基于不同进程量身定做。不同进程可以根据自身需要，为自己量身定做适合自身的调度算法对线程进行管理和调度。用户级线程的实现与操作系统平台无关，即可以在任何操作系统中运行。3.3.3线程实现与线程模型62用户级线程方式缺点：许多系统调用会引起阻塞，当用户级线程执行一个系统调用时，不仅该线程会被阻塞，而且该线程所在进程内的所有线程都会被阻塞。但是，如果在内核级线程方式中，一个线程被阻塞，进程中的其它线程仍然可以运行。在纯粹的用户级线程实现方式中，多线程应用不能利用多处理机技术进行多重处理。内核一次只为每个进程分配一个处理器，即进程每次只有一个线程处于运行状态，其它线程此时只能等待。3.3.3线程实现与线程模型63（2）内核级线程（Kernellevelthread,KLT）

线程管理的所有工作都是由内核完成，应用程序并没有参与其中。即无论是用户进程中的线程，还是系统进程中的线程，他们的创建、终止和切换等也是依靠内核，在内核空间实现的。3.3.3线程实现与线程模型64内核级线程方式优点：内核能够同时为同一进程中的多个线程分配多个处理器，即能让多个线程并行执行。如果进程中的一个线程被阻塞了，内核可以为该进程中的其它线程分派处理器资源使其运行，当然也可以调度其它进程中的线程运行。内核本身也可以采用多线程技术，可以提高系统的执行速度和效率。3.3.3线程实现与线程模型65内核级线程方式缺点：因为线程调度和管理是在内核实现，而用户进程的线程却是在用户态下运行。因此在进行线程与同一进程内其它线程切换时，需要从用户态转到内核态进行，从而导致较大的系统开销。3.3.3线程实现与线程模型66（3）组合方式

同一个进程内的多个线程可以同时在多处理器上并行执行，而且一个线程被阻塞时，同一进程内的其它线程可以调度运行，并不需要阻塞整个进程。所以，组合方式多线程机制能够结合KLT和ULT两者的优点，并克服了其各自的不足。3.3.3线程实现与线程模型67图3.9线程实现方式3.3.3线程实现与线程模型682.线程模型（1）多对一模型3.3.3线程实现与线程模型69图3.10多对一模型（2）一对一模型3.3.3线程实现与线程模型70图3.11一对一模型（3）多对多模型3.3.3线程实现与线程模型71图3.12多对多模型操作系统设计中的核心问题是关于进程和线程的管理：采用多道程序设计技术管理单处理器系统中的多个进程采用多处理技术管理多处理器系统中的多个进程采用分布式处理技术管理多台分布式计算机系统中的多个进程并发是上述管理问题实现的基础，也是操作系统设计的核心3.4互斥和同步72并发涉及的术语：（1）临界区（Criticalsection）（2）竞争（Competition）（3）同步（Synchronization）（4）互斥（Mutualexclusion）（5）死锁（Deadlock）（6）饥饿（Starvation）3.4.1并发原理73临界区（Criticalsection）每个进程中访问临界资源的那段代码称为临界区（CriticalSection）（临界资源是一次仅允许一个进程使用的共享资源）。每次只准许一个进程进入临界区，进入后不允许其他进程进入。不论是硬件临界资源，还是软件临界资源，多个进程必须互斥地对它进行访问。Critical：关键的;批评的，爱挑剔的;严重的;极重要的;进程进入临界区的调度原则是：1、如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入。2、任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则其它所有试图进入临界区的进程必须等待。3、进入临界区的进程要在有限时间内退出，以便其它进程能及时进入自己的临界区。4、如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象。竞争（Competition）多个线程或者进程在读写一个共享数据时结果依赖于它们执行的相对时间，这种情形叫做竞争。竞争条件发生在当多个进程或者线程在读写数据时，其最终的的结果依赖于多个进程的指令执行顺序。例如：假设两个进程P1和P2共享了变量a。在某一执行时刻，P1更新a为1，在另一时刻，P2更新a为2。因此两个任务竞争地写变量a。在这个例子中，竞争的“失败者”(最后更新的进程）决定了变量a的最终值。多个进程并发访问和操作同一数据且执行结果与访问的特定顺序有关，称为竞争条件。同步（Synchronization）

同步是指在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系。我们把异步环境下的一组并发进程因直接制约而互相发送消息、进行互相合作、互相等待，使得各进程按一定的速度执行的过程称为进程间的同步。互斥（Mutualexclusion）两个或两个以上的进程，不能同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的错误，这种现象被称作进程互斥。

exclusion:拒绝，杜绝;排除，驱逐;（或事物）被排斥在外的人;排外主义;死锁(deadlock)

死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时执行程序中两个或多个线程发生永久堵塞（等待），每个线程都在等待被其他线程占用并堵塞了的资源。例如，线程A和线程Ｂ都需要访问记录1和2，如果线程A锁住了记录1并等待记录2，而线程B锁住了记录2并等待记录1，这样两个线程就发生了死锁现象。Deadlock:僵局;停顿，停滞;没有弹簧的锁;成僵局;饥饿（Starvation）

饥饿是指一个可运行的进程虽然能继续执行，但被调度程序无限期地忽视而不能执行的情况。举个例子，当有多个进程需要打印文件时，如果系统分配打印机的策略是最短文件优先，那么长文件的打印任务将由于短文件的源源不断到来而被无限期推迟，导致最终的饥饿甚至饿死。

1.两种制约关系（1）直接相互制约关系------进程同步（2）间接相互制约关系------进程互斥3.4.1并发原理811、进程之间两种形式的制约关系系统中诸进程之间在逻辑上存在着两种制约关系：直接制约关系（进程同步）：即为完成同一个任务的诸进程间，因需要协调它们的工作而相互等待、相互交换信息所产生的直接制约关系。

间接制约关系（进程互斥）：是进程共享独占型资源而必须互斥执行的间接制约关系。同步与互斥比较同步互斥进程-进程进程-资源-进程时间次序上受到某种限制竞争到某一物理资源时不允许进程工作相互清楚对方的存在及作用，交换信息不一定清楚其它进程情况往往指有几个进程共同完成一个任务往往指多个任务多个进程间相互制约例：生产与消费之间，作者与读者之间例：交通十字路口互斥与同步所谓互斥，是指散步在不同进程之间的若干程序片断(临界区)，当某个进程运行其中一个程序片段时，其它进程就不能运行它们之中的任一程序片段，只能等到该进程运行完这个程序片段后才可以运行。所谓同步，是指散步在不同进程之间的若干程序片断，它们的运行必须严格按照规定的某种先后次序来运行，这种先后次序依赖于要完成的特定的任务。

显然，同步是一种更为复杂的互斥，而互斥是一种特殊的同步。互斥与同步互斥是两个线程之间不可以同时运行，他们会相互排斥，必须等待一个线程运行完毕，另一个才能运行，而同步也是不能同时运行，但他是必须要安照某种次序来运行相应的线程。

互斥：是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。

同步：是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。在大多数情况下，同步已经实现了互斥，特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源。为什么就买一个烧饼妻子对正要上班出门丈夫说：“晚上回来时买两个烧饼，如果看到卖西瓜的，就买一个。”

转眼到了下午下班，丈夫回到家把一个烧饼放到桌上，妻子怒问：”为什么就买一个烧饼？！“丈夫答曰：”因为我看到了卖西瓜的。“因为他丈夫是程序员.程序员的愿望有一天，一个程序员见到了上帝.

上帝:

小伙子,我可以满足你一个愿望.程序员:

我希望中国国家队能再次打进世界杯.

上帝:

这个啊!这个不好办啊,你还说下一个吧!程序员:

那好!我的下一个愿望是每天都能休息6个小时以上.

上帝:

还是让中国国家打进世界杯.3.4.1并发原理重点部分难点部分AND2.临界区和临界资源进程间竞争资源产生如下的几个控制问题（1）互斥（2）死锁（3）饥饿3.4.1并发原理90一次只允许一个进程使用的资源称为临界资源(CriticalResource)，如打印机、绘图机、变量、数据等，进程之间采取互斥方式式实现对临界资源的共享，从而实现并行程序的封闭性。引起不可再现性是因为对临界资源没有进行互斥访问。在每个进程中，访问临界资源的那一段代码称为临界区（CriticalSection），简称CS区。

例：有两个进程A和B，它们共享一个变量X，且两个进程按以下方式对变量X进行访问和修改，其中R1和R2为处理机中的两个寄存器(或变量)。A:R1=X;R1=R1+1;X=R1;B:R2=X;R2=R2+1;X=R2;

A与B均对X加1，即X加2。临界区临界区产生错误的原因：不加控制地访问共享变量X对临界区需要进行保护（互斥访问）结果X只加了1A:R1=X;B:R2=X;A:R1=R1+1;X=R1;B:R2=R2+1;X=R2;如果按另一顺序对变量进行修改为了保证临界资源的正确使用，可以把临界资源的访问过程分成以下几部分：进入区临界区退出区剩余区进入区：增加在临界区前面的一段代码，用于检查欲访问的临界资源此刻是否被访问。退出区：增加在临界区后面的一段代码，用于将临界资源的访问标志恢复为未被访问标志。临界区：进程访问临界资源的那段代码。剩余区：进程中除了进入区、临界区及退出区之外的其余代码。多个进程共享临界区，需遵循如下的调度原则：空闲让进:当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。忙则等待:当已有进程进入临界区时，表明临界资源正在被访问，因而其他试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。有限等待:对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入死等状态。让权等待:当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入忙等。95同步机制解决临界区（互斥）问题的几类方法软件方法用编程解决。重点：信号量及P-V操作硬件方法用硬件指令解决。1.关中断访问共享资源的最简单的方法是关中断：一个任务在对共享资源进行访问前将中断关闭，然后执行访问共享资源的关键段落代码，访问共享资源结束后再打开终端。3.4.2硬件同步971.关中断while(true){/*关中断*//*临界区*//*开中断*//*其余部分*/}缺点：3.4.2硬件同步98关中断的优缺点优点：简单。缺点：

1.代价高，效率低：限制了处理器交替执行各进程的能力。

2.不能用于多处理器：关中断不能保证互斥。

3.影响系统的实时。为了减轻对系统实时性的不利影响，访问共享资源的关键段落代码必须尽量简短，绝对不允许在关键段落代码中包含有可能使自己挂起的系统服务函数；否则将使系统死机。由于关中断直接影响系统的实时性，因此只能用于对简单共享资源的短暂访问。由此可以得出，关中断方法常用于对全局变量和小规模全局数据结构的访问。2.TestAndSet指令（自旋锁

）

自旋锁是专为防止多处理器并发而引入的一种锁，它在内核中大量应用于中断处理等部分，是为了解决对某项资源的互斥使用。在任何时刻最多只能有一个执行单元获得锁。对于互斥锁，如果资源已经被占用，资源申请者只能进入睡眠状态。但是自旋锁不会引起调用者睡眠，如果自旋锁已经被别的执行单元保持，调用者就一直循环在那里看是否该自旋锁的保持者已经释放了锁，"自旋"一词就是因此而得名。3.4.2硬件同步1002.TestAndSet指令（自旋锁

）TestAndSet指令描述如下：booleanTestAndSet(boolean*lock){

booleantemp=*lock;

*lock=TRUE;

returntemp;}3.4.2硬件同步101实参值为真，则返回真，不改变实参的值。实参值为假，则返回假，同时改变实值的值为真。TestAndSet指令实现互斥的示例如下：lock=FALSE;

……do{while(TestAndSet(&lock));

//donothing不做任何事

//criticalsection临界区

lock=FALSE;表示空闲

//remaindersection其他代码}while(TRUE);3.4.2硬件同步102booleanTestAndSet(boolean*lock){

booleantemp=*lock;

*lock=TRUE;

returntemp;}自旋锁存在的问题死锁。试图递归地获得自旋锁必然会引起死锁。在递归程序中使用自旋锁应遵守下列策略：递归程序决不能在持有自旋锁时调用它自己，也决不能在递归调用时试图获得相同的自旋锁。此外如果一个进程已经将资源锁定，那么，即使其它申请这个资源的进程不停地疯狂“自旋”,也无法获得资源，从而进入死循环。过多占用cpu资源。如果不加限制，由于申请者一直在循环等待，因此自旋锁在锁定的时候,如果不成功,不会睡眠,会持续的尝试,单cpu的时候自旋锁会让其它进程动不了.因此，一般自旋锁实现会有一个参数限定最多持续尝试次数.超出后,自旋锁放弃当前时间片.等下一次机会3.Swap指令Swap指令为对换指令，定义如下：voidSwap(boolean*a,boolean*b){Booleantemp=*a;*a=*b;*b=temp;}3.4.2硬件同步104功能：将a,b指针指向的值互换使用Swap指令实现互斥的示例如下：Lock=false：//全局变量；do{data=TRUE;//局部变量while(data==TRUE)Swap(&lock,&data);//criticalsection临界区lock=FALSE;//remindersection其他部分}while(TRUE);3.4.2硬件同步105硬件实现的优点与缺点：硬件方法的优点：适用于任意数目的进程，不管是单处理机还是多处理机；简单、容易验证其正确性。可以支持进程内有多个临界区，只需为每个临界区设立一个布尔变量。

硬件方法的缺点：进程等待进入临界区时要耗费处理机时间，不能实现让权等待。从等待进程中随机选择一个进入临界区，有的进程可能一直选不上，从而导致“饥饿”现象。

PV操作在操作系统中，PV操作是进程管理中的难点。我国读者常常不明白这一同步机制为什么叫PV操作，原来这是狄克斯特拉用荷兰文定义的，因为在荷兰文中，通过叫passeren，释放叫vrijgeven，PV操作因此得名。这是在计算机术语中不是用英语表达的极少数的例子之一。P就是请求资源，V就是释放资源。PV操作的含义PV操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量进行操作，具体定义如下：

P（S）：①将信号量S的值减1，即S=S-1；②如果S≥0，则该进程继续执行；否则该进程置为等待状态，排入等待队列。

V（S）：①将信号量S的值加1，即S=S+1；②如果S>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。信号灯

所谓信号灯，实际上就是用来控制进程状态的一个代表某一资源的存储单元。例如，P1和P2是分别将数据送入缓冲B和从缓冲B读出数据的两个进程。对P1和P2可定义两个信号量S1和S2，初值分别为1和0。进程P1在向缓冲B送入数据前执行P操作P（S1），在送入数据后执行V操作V（S2）。进程P2在从缓冲B读取数据前先执行P操作P（S2），在读出数据后执行V操作V（S1）。当P1往缓冲B送入一数据后信号量S1之值变为0，在该数据读出后S1之值才又变为1，因此在前一数未读出前后一数不会送入，从而保证了P1和P2之间的同步。什么是信号量信号量值与相应资源的使用情况有关。当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数。注意，信号量的值仅能由PV操作来改变。信号量信号量S≥0时，S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源，因此S的值减1；当S<0时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。而执行一个V操作意味着释放一个单位资源，因此S的值加1；若S≤0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。实现进程互斥的一般模型是：使用PV操作实现进程互斥时应该注意的是：

（1）每个程序中用户实现互斥的P、V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。若有多个分支，要认真检查其成对性。

（2）P、V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。

（3）信号量S用于互斥，互斥信号量的初值一般为1。简单理解P，V操作

临界区门前有棵树，用来挂红灯（信号量，初始为１）P操作：进程想进临界区的门，先得上树取下盏灯（调用一次P）取灯（S＝S－1）有灯（S＞=0），进程进入临界区没灯(S＜0)，进程只好在门外边（临界区外）排队等V操作：得灯的进程继续运行，运行完了要出门（调用一次V）马上还回一盏灯（S＝S＋1）如果没有进程在等（S＞0），继续运行如果有进程在等（S＜＝0），放个进程进去（临界区）后，继续运行难点解析

V原语的主要操作是：（1）信号量（sem）加1；（2）若相加结果大于零，则进程继续执行；（3）若相加结果小于或等于零，则唤醒一阻塞在该信号量上的进程，然后再返回原进程继续执行或转进程调度。疑问1：以V原语的1、2步来做，Sem不就永远大于0，那进程不就一直循环执行成为死循环了？疑问2：信号量大于0那就表示有临界资源可供使用，为什么不唤醒进程？疑问3：信号量小于0应该是说没有临界资源可供使用，为什么还要唤醒进程？Semaphoren.臂板信号系统;

vt.&vi.发出信号，打旗语;信号量大于１时有2个某类资源，四个进程A、B、C、D要用该类资源，最开始Sem=2，当A进入，Sem=1，当B进入Sem=0,表明该类资源刚好用完。

当C进入时Sem=-1,表明有一个进程被阻塞了，D进入，Sem=-2。当A用完该类资源时，进行V操作，Sem=-1，释放该类资源，而这时Sem<0,表明有进程阻塞在该类资源上，于是唤醒一个。疑问4：如果是互斥信号量的话，应该设置信号量Sen=1，但是当有5个进程都访问的话，最后在该信号量的链表里会有4个在等待，也是说S=-4，那么第一个进程执行了V操作使S加1，释放了资源，下一个应该能够执行，但唤醒的这个进程在执行P操作时因S〈0,也还是执行不了,这是怎么回事呢？答：当一个进程阻塞了的时候，它已经执行过了P操作，并卡在临界区那个地方。当唤醒它时就立即进入它自己的临界区，并不需要执行P操作了，当执行完了临界区的程序后，就执行V操作。疑问5：

Sem的绝对值表示等待的进程数，同时又表示临界资源，这到底是怎么回事？？答：当信号量Sem小于0时,其绝对值表示系统中因请求该类资源而被阻塞的进程数目.S大于0时表示可用的临界资源数。注意在不同情况下所表达的含义不一样。当等于0时，表示刚好用完。桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放香蕉，儿子专等吃盘中的香蕉，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者使用，请用P，V原语实现爸爸、儿子、女儿三个并发进程的同步。桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果和香蕉，儿子专等吃盘中的香蕉，女儿专等吃盘中的苹果。Vardish,apple,banana:Semaphore:=1,0,0;Main(){cobeginFather();son();daugher();Coend}Father(){while(true){p(dish);if放的是苹果v(apple);elseV(banana)}}son(){while(true){p(banana);从盘子取香蕉；v(dish);

吃香蕉；}}daugher(){while(true){p(apple);从盘子取苹果；v(dish);

吃苹果；}}//dish—互斥使用盘子；apple—盘中苹果数；banana—盘中香蕉数例题（1）V（S1）V（S2）P（S1）V（S3）V（S4）（2）P（S2）V（S5）（3）P（S3）P（S4）P（S5）1.整型信号量

Dijkstra把整型信号量s定义成一个用于表示资源数目的整型变量。进程通过信号量传送信号，利用两个特殊的操作发送和接收信号。

signal(s)：通过信号量s传送信号

wait(s)：通过信号量接收信号

如果相应的信号仍然没有发送，则进程被挂起，直到发送完为止。3.4.3信号量机制122wait()操作定义如下voidwait(s){while(s<=0);//donothings--;}signal()操作定义如下voidsignal(s){s++;}3.4.3信号量机制1232.记录型信号量整型信号量机制没有满足让权等待的原则，可能使进程处于饥饿的忙等状态。假设s为一个记录型数据结构，其中一个分量为整形量value，另一个为信号量队列queue。value通常是一个具有非负初值的整型变量，queue是一个初始状态为空的进程队列，当一个进程必须等待信号量时，就加入到进程队列中去。3.4.3信号量机制124wait和signal操作定义如下：wait(s)：信号量s减l，若结果小于0，则调用wait(s)的进程被设置成等待信号量s的状态。signal(s)：将信号量s加1，若结果不大于0，则释放一个等待信号量s的进程。3.4.3信号量机制126分析得出以下结论：

（1）若信号量s.value值为正，则该值表示在对进程进行阻塞之前对信号量s可以实施的wait()操作个数，即系统中某类资源实际可用数目；（2）若信号量s.value值为负，则其绝对值表示阻塞队列s.queue中等待的进程个数；（3）每次wait()操作，意味着进程请求一个单位的该类资源，使系统中可供分配的该类资源数减少一个，每次signal()操作，表示执行进程释放一个单位资源，使系统中可供分配的该类资源数增加一个。3.4.3信号量机制1273.二元信号量假设s为一个记录型数据结构，其中一个分量为value，它仅能取值0和1，另一个分量为信号量队列queue。一个二元信号量的值只能是0或者13.4.3信号量机制128P-V同步缺点：对于共享变量及信号量变量的操作将被分散于各个进程中，有几个缺点：（１）易读性差，因为要了解对于一组共享变量及信号量的操作是否正确，则必须通读整个系统或者并发程序（２）不利于修改和维护，因为程序的局部性很差，所以任一组变量或一段代码的修改都可能影响全局（３）正确性难以保证，因为操作系统或并发程序通常很大，要保证这样一个复杂的系统没有逻辑错误是很难的管程的引入

信号量机制的引入解决了进程同步的描述问题，但信号量的大量同步操作分散在各个进程中不便于管理，还有可能导致系统死锁。如：生产者消费者问题中将P、V颠倒可能死锁。

Dijkstra于1971年提出：把所有进程对某一种临界资源的同步操作都集中起来，构成一个所谓的秘书进程。凡要访问该临界资源的进程，都需先报告秘书，由秘书来实现诸进程对同一临界资源的互斥使用。1.管程的定义

管程是由一个或多个过程、一个初始化序列和数据组成的软件模块，是一种程序设计语言结构成分，具有和信号量同等的表达能力。进程可以通过调用管程实现对资源的请求和释放。

百度百科：管程(英语：Monitors，也称为监视器)定义了一个数据结构和能为并发进程所执行的一组操作，这组操作能同步进程和改变管程中的数据。3.4.4管程132管程的基本思想

将共享变量和对它们的操作集中在一个模块中，操作系统或并发程序就由这样的模块构成。这样模块之间联系清晰，便于维护和修改，易于保证正确性。管程的主要特点：共享性：一个进程通过调用管程的一个过程进入管程，管程中的移出过程可被所有要调用管程的过程的进程所共享。安全性：管程的局部数据变量只能被管程的过程访问，任何其它外部过程都不能访问，一个管程的过程也不能访问任何非局部于它的变量。互斥性：在任一时刻，只能有一个进程能够进入管程执行，调用管程的其它任何进程都将被阻塞，只能等待直到当前访问进程退出管程。3.4.4管程1342.管程的条件变量在管程的调用过程中，存在如下的现象：一个进程调用了管程，并且它在管程中处于阻塞或挂起状态，当进程解除阻塞或挂起的条件满足后才能恢复执行。引入条件变量（Conditionvariables）的同步机制，以及对应的两个原语操作cwait和csignal。3.4.4管程135cwait和csignal操作意义：

（1）cwait(c)操作：正在调用管程过程的进程因条件c没有满足而被阻塞或者挂起，则调用cwait操作将自己插入到条件变量c的等待进程队列中。与此同时，被阻塞进程释放管程，直到条件c发生改变，其它进程可以调用管程。（2）csignal(c)操作：正在调用管程的进程检测到条件c发生了改变，则调用csignal操作重新唤醒一个因条件c而被阻塞或者挂起的进程。如果等待进程队列中有多个进程，则选择其中一个唤醒，否则继续执行原进程。3.4.4管程1361.生产者-消费者问题（1）问题描述

假设有n个生产者和m个消费者，连接在一个有k个公用缓冲区的有界缓冲上，pi表示生产者进程，cj表示消费者进程。

满足：只要缓冲区未满，生产者pi即可将生产的产品放入空闲缓冲区中只要缓冲区不为空，消费者进程cj就可从缓冲区从取走并消耗产品在任何时刻，要么是一个生产者访问缓冲区，要么是一个消费者在访问缓冲区3.4.5经典同步问题138有1个生产者和1个消费者，一个有1个公用缓冲区生产者进程

while(TRUE){

生产一个产品;

P(empty);

产品送往Buffer;

V(full);

}

消费者进程

while(True){

P(full);

从Buffer取出一个产品;

V(empty);

消费该产品;

}定义两个同步信号量：

empty——表示缓冲区是否为空，初值为1。

full——表示缓冲区中是否为满，初值为0。

有1个生产者和1个消费者，一个有n个公用缓冲区生产者进程while(TRUE){生产一个产品;P(empty);产品送往buffer（in）；in=(in+1)modn；V(full);}消费者进程while(TRUE){P(full);从buffer（out）中取出产品；out=(out+1)modn；V(empty);消费该产品;}定义两个同步信号量：empty——表示缓冲区是否为空，初值为n。full——表示缓冲区中是否为满，初值为0。设缓冲区的编号为1～n-1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指针，指向下一个可用的缓冲区。有多个生产者（互斥）和多个消费者（互斥），一个有n个公用缓冲区在这个问题中，不仅生产者与消费者之间要同步，而且各个生产者之间、各个消费者之间还必须互斥地访问缓冲区。定义四个信号量：empty——表示缓冲区是否为空，初值为n。full——表示缓冲区中是否为满，初值为0。mutex1——生产者之间的互斥信号量，初值为1。mutex2——消费者之间的互斥信号量，初值为1。设缓冲区的编号为1～n-1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指针，指向下一个可用的缓冲区。有多个生产者（互斥）和多个消费者（互斥），一个有n个公用缓冲区生产者进程

while(TRUE){

生产一个产品;

P(empty);

P(mutex1)；

产品送往buffer（in）；

in=(in+1)modn；

V(mutex1);

V(full);

}消费者进程