计算机操作系统第二章

第二章进程管理,2.1进程的基本概念2.2进程控制2.3进程同步2.4经典进程的同步问题2.5管程机制2.6进程通信2.7线程,程序的顺序执行和并发执行程序的执行有两种方式：顺序执行和并发执行。顺序执行是单道批处理系统的执行方式，也用于简单的单片机系统；现在的操作系统多为并发执行，具有许多新的特征。引入并发执行的目的是为了提高资源利用率。,在多道程序环境下，程序不能独立运行。作为资源分配和独立运行的基本单位是进程。操作系统所有的特征都是基于进程而体现的为了描述程序在并发执行时对系统资源的共享，我们需要一个描述程序执行时动态特征的概念，这就是进程。通常把这个正准备进入内存的程序称为作业，当这个作业进入内存后我们把它称为进程。进程通常具有三种状态：运行状态（正在使用CPU）、阻塞状态（等待输入/输出）和就绪状态（等待分配CPU）。,进程的特征动态性：进程具有动态的地址空间（数量和内容），地址空间上包括：代码（指令执行和CPU状态的改变）数据（变量的生成和赋值）系统控制信息（进程控制块的生成和删除）独立性：各进程的地址空间相互独立，除非采用进程间通信手段；并发性、异步性：虚拟结构化：代码段、数据段和核心段（在地址空间中）；程序文件中通常也划分了代码段和数据段，而核心段通常就是OS核心（由各个进程共享，包括各进程的PCB）,进程与程序的区别和相互关系：（1）动态性和静态性。（2）从结构上看每个进程的实体都是由程序段和相应的数据段两部分构成的，这一特征与程序的含义相近。（3）一个进程可以涉及到一个或几个程序的执行；反之一程序可以对应多个进程，即同一程序段可在不同数据集合上运行，可构成不同的进程。（4）并发性。（5）进程具有创建其他进程的功能。（6）操作系统中的每一个程序都是在一个进程现场中运行的。,程序顺序执行的特征：顺序性：按照程序结构所指定的次序（可能有分支或循环）封闭性：独占全部资源，计算机的状态只由于该程序的控制逻辑所决定可再现性：初始条件相同则结果相同。如：可通过空指令控制时间关系。,2.1进程的基本概念,2.1.1程序的顺序执行及其特征,1.程序的顺序执行仅当前一操作(程序段)执行完后，才能执行后继操作。例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。S1:a=x+y;S2:b=a-5;S3:c=b+1;,图2-1程序的顺序执行,1程序的顺序执行及其特性,由于各类软件的出现及日益复杂化，使得程序设计的概念和方法有了很大的发展，在单道程序工作环境中，我们把一个“程序”理解为“一个在时间上按严格次序前后相继的操作序列”。,2.程序顺序执行时的特征,顺序性：(2)封闭性：资源独占。(3)可再现性：结果的无关性。,2.1.2前趋图,前趋图是一个有向无循环图，记为DAG，用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序或前趋关系“”。在前趋图中，把没有前趋的结点称为初始结点，把没有后继的结点称为终止结点。,每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。,IiCiPi和S1S2S3,图2-2前趋图,对于图2-2(a)所示的前趋图，存在下述前趋关系：,P1P2,P1P3,P1P4,P2P5,P3P5,P4P6,P4P7,P5P8,P6P8,P7P9,P8P9或表示为：P=P1,P2,P3,P4,P5,P6,P7,P8,P9=(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5),(P4,P6),(P4,P7),(P5,P8),(P6,P8),(P7,P9),(P8,P9)应当注意，前趋图中必须不存在循环，但在图2-2(b)中却有着下述的前趋关系：S2S3,S3S2这是无法满足的.,2.1.3程序的并发执行及其特性,无论是操作系统自身的程序还是用户程序，通常总是存在一些相对独立、但又能并发执行的程序段。由于这些程序段可以被多个用户作业调用，因此可在同一时间间隔内发生。这样一来，某个程序段可能对应多个“计算”，于是程序与“计算”已不具有一一对应关系了。这些“并发程序”就构成了一个“并发环境”。,并发执行的特征间断(异步)性：走走停停，一个程序可能走到中途停下来，失去原有的时序关系；失去封闭性：共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。失去可再现性：失去封闭性失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重复特征。,2.1.3程序的并发执行及其特征,2.1.3程序的并发执行及其特征,1.程序的并发执行,图2-3并发执行时的前趋图,在该例中存在下述前趋关系：IiCi，IiIi+1,CiPi,CiCi+1，PiPi+1而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之间，可以并发执行。对于具有下述四条语句的程序段：S1:a=x+2S2:b=y+4S3:c=a+bS4:d=c+b,图2-4四条语句的前趋关系,2.程序并发执行时的特征,间断性2)失去封闭性3)不可再现性,例如，两个循环程序A和B，它们共享一个变量N。程序AN=N+1；程序BPrint(N)；N=0；程序A和B以不同的速度运行。(1)N=N+1在Print(N)和N=0之前，此时得到的N值分别为n+1,n+1,0。(2)N=N+1在Print(N)和N=0之后，此时得到的N值分别为n,0,1。(3)N=N+1在Print(N)和N=0之间，此时得到的N值分别为n,n+1,0。,2.1.4进程的特征与状态,1.进程的特征和定义,结构特征程序段、相关数据段、PCB构成进程实体2)动态性3)并发性4)独立性5)异步性,行为的一个规则叫做程序，程序在处理机上执行时所发生的活动称为进程（Dijkstra)。进程是这样的计算部分，它是可以和其它计算并行的一个计算。(Donovan)进程（有时称为任务）是一个程序与其数据一道通过处理机的执行所发生的活动。（Alan.C.Shaw)进程是执行中的程序。（KenThompsonandDennisRitchie)教材上给出的进程的定义：进程，即是一个具有一定独立功能的程序关于某个数据集合的一次活动。,较典型的进程定义有：(1)进程是程序的一次执行。(2)进程是一个程序及其数据在处理机上顺序执行时所发生的活动。(3)进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。传统OS中的进程定义为：“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位”。,程序与进程,联系：程序是构成进程的组成部分之一。一个进程的运行目标就是执行它所对应的程序，如果没有程序，进程就失去了其实际存在的意义。从静态的角度看，进程是由程序、数据和进程控制块（PCB）三部分组成。,区别：程序是静态的，而进程是动态的；程序的存在是永久的，进程的存在是暂时的，动态的产生和消亡；一个进程可以执行一个或几个程序，一个程序亦可以构成多个进程；进程具有创建其它进程的功能。,2.进程的三种基本状态,就绪(Ready)状态2)执行状态3)阻塞状态,图2-5进程的三种基本状态及其转换,（1）运行状态：进程正在处理机上运行的状态，该进程已获得必要的资源，也获得了处理机，用户程序正在处理机上运行。（2）阻塞状态：进程等待某种事件完成（例如，等待输入/输出操作的完成）而暂时不能运行的状态，处于该状态的进程不能参加竞争处理机，此时，即使分配给它处理机，它也不能运行。（3）就绪状态：该进程运行所需的一切条件都得到满足，但因处理机资源个数少于进程个数，所以该进程不能运行，而必须等待分配处理机资源，一旦获得处理机就立即投入运行。,3.挂起状态引入挂起状态的原因终端用户的请求。(2)父进程请求。(3)负荷调节的需要。(4)操作系统的需要。,挂起进程在操作系统中可以定义为暂时被淘汰出内存的进程，机器的资源是有限的，在资源不足的情况下，操作系统对在内存中的程序进行合理的安排，其中有的进程被暂时调离出内存，当条件允许的时候，会被操作系统再次调回内存，重新进入等待被执行的状态即就绪态。,2)进程状态的转换,活动就绪静止就绪。(2)活动阻塞静止阻塞。(3)静止就绪活动就绪。(4)静止阻塞活动阻塞。,图2-6具有挂起状态的进程状态图,2.1.5进程控制块,1.进程控制块的作用,进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。PCB是进程存在的唯一标志。,进程控制块,为了刻画进程的动态变化，通常把进程表示为由程序段、私有数据块和进程控制块组成，如图3.4（a）所示。程序部分描述进程本身所要完成的功能，而“私有数据块”是接受程序规定操作的一组存储单元的内容，是操作的对象。进程控制块是在进程创建时产生的，当进程存在于系统时（运行），进程控制块就标识了这个进程。如图3.4（b）所示。,下一页,Loik,进程控制块是进程存在的标志，当系统或父进程创建一个进程时，实际上就是为其建立一个进程控制块。进程控制块既能标识进程的存在，又能刻画出进程的动态特征，它是一个进程仅有的被系统真正感知的部分。对操作系统而言，所有进程控制块将构成并发执行控制和维护系统工作的依据。,进程控制块的作用：,2.进程控制块中的信息,1)进程标识符(1)内部标识符。主要是为了方便系统使用。在所有的操作系统中，都为每一个进程赋予一个惟一的数字标识符，它通常是一个进程的序号。(2)外部标识符。它由创建者提供，通常是由字母、数字组成，往往是由用户(进程)在访问该进程时使用。,2)处理机状态通用寄存器：用户程序可以访问的，存放信息。指令计数器，存放要访问的下一条指令的地址；程序状态字PSW，其中含有状态信息，如条件码、执行方式、中断屏蔽标志等；用户栈指针，指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶。,3)进程调度信息进程状态，指明进程的当前状态，作为进程调度和对换时的依据；进程优先级，用于描述进程使用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机；进程调度所需的其它信息；事件，是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。,4)进程控制信息程序和数据的地址进程同步和通信机制；资源清单，是一张列出了除CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单；链接指针，它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址。,家族联系processfamily有的系统允许一个进程可创建自已的子进程，子进程还可以创建，一个进程往往处在一个家族之中，就需要记录进程在家族中位置的信息。,3.进程控制块的组织方式,1)链接方式,图2-7PCB链接队列示意图,2)索引方式,图2-8按索引方式组织PCB,进程的类型,在系统中同时有多个进程存在，但归纳起来有两大类：1、系统进程系统进程起着资源管理和控制的作用。或者：执行操作系统核心代码的进程。2、用户进程执行用户程序的进程。,进程的类型,系统进程与用户进程的区别：1、系统进程被分配一个初始的资源集合，这些资源可以为它独占，也能以最高优先权的资格使用。用户进程通过系统服务请求的手段竞争使用系统资源；2、用户进程不能直接做I/O操作，而系统进程可以做显示的、直接的I/O操作。3、系统进程在管态下活动，而用户进程则在用户态（目态）下活动。另一种分类：计算进程，I/O进程等,进程是有生命周期的，产生、运行、暂停、终止，对进程的这些操作叫进程控制。进程控制的职责是对系统中全部进程实施有效的管理，它是处理机管理的部分（另一部分是进程调度），当系统允许多进程并发执行时，为了实现共享、协调并发进程的关系，处理机管理必须提供对进程实行有效的管理。,2.2进程控制,进程控制进程控制的概念,进程控制包括：进程创建、进程撤消、进程阻塞、进程唤醒。这些操作都要对应地执行一个特殊的程序段（操作系统核心程序），同时系统也通过系统调用给用户提供进程控制的功能。教材上叫原语（一种特殊的系统调用）。,运行状态等待状态进程阻塞等待状态就绪状态进程唤醒新建进程置为就绪状态进程创建进程终止（消亡）进程撤消就绪状态运行状态进程调度,原语,在操作系统中，某些被进程调用的操作，例如队列操作、对信号灯的操作、检查启动外设操作等，一旦开始执行就不能被中断，否则就会出现操作错误，造成系统混乱。原语就是为实现这些操作而设置的。,原语(primitive)：由若干条指令构成的“原子操作(atomicoperation)”过程，作为一个整体而不可分割要么全都完成，要么全都不做。许多系统调用就是原语。,注意：系统调用并不都是原语。进程A调用read()，因无数据而阻塞，在read()里未返回。然后进程B调用read()，此时read()被重入。系统调用不一定一次执行完并返回该进程，有可能在特定的点暂停，而转入到其他进程。,图3.5进程家族示例,2.2.1进程的创建,进程图(ProcessGraph)继承(inherit)：子进程可以从父进程中继承环境变量、打开文件、文件系统的当前目录、控制终端、已经连接的共享存储区、信号处理例程入口表等.不被继承：进程标识符，父进程标识符。,图2-9进程树,2.引起创建进程的事件,用户登录。(2)作业调度。(3)提供服务。(4)应用请求。,（1）创建进程。系统在创建进程时，必须为之分配其所必需的、除处理机以外的所有资源。如内存空间、I/O设备以及建立相应的PCB结构。（2）撤消进程。系统在撤消进程时，又必须先对这些资源进行回收操作，然后再撤消PCB结构。（3）进程切换。在对进程进行切换时，由于要保留当前进程的CPU环境和设置新选中进程的CPU环境，为此需花费不少处理机时间。,3.进程的创建(CreationofProgress),(1)申请空白PCB。申请唯一的数字表示符；(2)为新进程分配资源。(3)初始化进程控制块。初始化标识符，处理机状态信息和控制信息。(4)将新进程插入就绪队列，如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列。,2.2.2进程的终止,引起进程终止(TerminationofProcess)的事件正常结束异常结束越界错误保护错误非法指令。特权指令错误。运行超时。等待超时。算术运算错误。I/O故障。,3)外界干预外界干预并非指在本进程运行中出现了异常事件，而是指进程应外界的请求而终止运行。操作员或操作系统干预。父进程请求。父进程终止。,2.进程的终止过程(1)根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。(2)终止执行进程重新进行调度。(3)终止其所有子孙进程。(4)将被终止进程所拥有的全部资源，归还给其父进程，或者系统。(5)将被终止进程(它的PCB)从所在队列(或链表)中移出，等待其他程序来搜集信息。,2.2.3进程的阻塞与唤醒,1.引起进程阻塞和唤醒的事件,请求系统服务2)启动某种操作3)新数据尚未到达4)无新工作可做,正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用阻塞原语block把自己阻塞。可见，进程的阻塞是进程自身的一种主动行为。进入block过程后，立即停止执行，把进程控制块中的现行状态由“执行”改为阻塞，并将PCB插入阻塞队列。最后，转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换。,2.进程阻塞过程,当被阻塞进程所期待的事件出现时，则由有关进程(比如，用完并释放了该I/O设备的进程)调用唤醒原语wakeup()，将等待该事件的进程唤醒。唤醒原语执行的过程是：首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪，然后再将该PCB插入到就绪队列中。,3.进程唤醒过程,2.2.4进程的挂起与激活,1.进程的挂起原语suspend()将指定进程或处于阻塞状态的进程挂起。挂起原语的执行过程是：首先检查被挂起进程的状态。为了方便用户或父进程考查该进程的运行情况而把该进程的PCB复制到某指定的内存区域。最后，若被挂起的进程正在执行，则转向调度程序重新调度。,2.进程的激活过程激活原语先将进程从外存调入内存，检查该进程的现行状态。假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重新调度，即由调度程序将被激活进程与当前进程进行优先级的比较，如果被激活进程的优先级更低，就不必重新调度；否则，立即剥夺当前进程的运行，把处理机分配给刚被激活的进程。,2.3进程同步,2.3.1进程同步的基本概念,1.两种形式的制约关系,间接相互制约关系-资源共享关系(2)直接相互制约关系-相互合作关系,进程互斥互斥的概念,引例：宿舍电话的使用打印机的使用1.临界资源：一次仅允许一个进程使用的资源称为临界资源。引例中的电话和打印机都属于临界资源。除此之外，还有内存变量、指针、数组等等也是临界资源。,2、临界区：每个进程中访问临界资源的那段程序段称为临界段）。,进程互斥互斥的概念,互斥定义:在操作系统中，当某一进程正在访问某临界区时，就不允许其它进程进入，否则就会发生(后果)无法估计的错误。我们把进程之间的这种相互制约的关系称为互斥。例如：飞机定票系统中的机票库,进程互斥互斥的概念,进入临界区的准则：(1)每次至多有一个进程处于临界区；(2)当有若干个进程欲进入临界区时，应在有限的时间内使其进入；(3)进程在临界区内仅逗留有限的时间。,进程互斥互斥的概念,解决进程互斥的最简单的办法是加锁。在系统中为每个临界资源设置一个锁位，0表示资源可用，1表示资源已被占用（不可用）。,锁和上锁、开锁操作,这样当一个进程使用某个临界资源之前必须完成下列操作：1、考察锁位的值；2、若原来的值是为“0”，将锁位置为“1”（占用该资源）；3、若原来值是为“1”，（该资源已被别人占用），则转到1。当进程使用完资源后，将锁位置为“0”，称为开锁操作。,用上锁原语和开锁原语实现互斥,假设有两个进程共享打印机，两个进程中使用打印机的程序段为临界区。为保证打印的正确，设置打印机的锁位print，其初值为“0”，表示打印机可。,2.临界资源(CriticalResouce),在一段时间内只允许一个进程访问的资源称为临界资源。生产者-消费者(producer-consumer)问题是一个著名的进程同步问题。每个生产者可不断地每次往缓冲池中送一个生产产品，而每个消费者则可不断地每次从缓冲池中取出一个产品同步关系：即不允许消费者进程到一个空缓冲区去取产品；也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。,生产者与消费者问题,Dijkstra把广义同步问题抽象成一种“生产者与消费者问题”（Producer-consumer-relationship）的抽象模型。事实上，计算机系统中的许多问题都可归结为生产者与消费者问题，生产者与消费者可以通过一个环形缓冲池（见图3.8）联系起来，环形缓冲池由几个大小相等的缓冲块组成，每个缓冲块容纳一个产品。,图3.8环形缓冲池,对于循环队列，当队空和队满时，都有：front=rear怎么判断循环队列的队空和队满呢？,有两种处理方法：1)另设一个标志位以区别队列是“空”或“满”。2)少用一个存储单元，队满条件是：（rear1）%MaxSize=front其中，MaxSize是队列的最大长度。队空条件：frontrear,生产者消费者共享下列变量：intin=0,out=0,count=0;item=buffern;/枚举类型说明；,voidconsumer()while(1)while(counter=0);nextc=bufferout;out=(out+1)%n;counter-;consumertheiteminnextc;,voidproducer()while(1)produceaniteminnextp;while(counter=n);bufferin=nextp;in=(in+1)%n;counter+;,若并发执行时，就会出现差错，问题就在于这两个进程共享变量counter。生产者对它做加1操作，消费者对它做减1操作，这两个操作在用机器语言实现时，常可用下面的形式描述：register1=counter;register2=counter;register1=register1+1;register2=register2-1;counter=register1;counter=register2;,假设：counter的当前值是5。如果生产者进程先执行左列的三条机器语言语句，然后消费者进程再执行右列的三条语句，则最后共享变量counter的值仍为5；反之，如果让消费者进程先执行右列的三条语句，然后再让生产者进程执行左列的三条语句，counter值也还是5，但是，如果按下述顺序执行：register1=counter;(register1=5)register1=register1+1;(register1=6)register2=counter;(register2=5)register2=register2-1;(register2=4)counter=register1;(counter=6)counter=register2;(counter=4),互斥，指多个进程不能同时使用同一个资源；,死锁，指多个进程互不相让，都得不到足够的资源；,饥饿，指一个进程一直得不到资源（其他进程可能轮流占用资源）,3.临界区(criticalsection),可把一个访问临界资源的循环进程描述如下：repeat检查代码看临界区是否占用criticalsection;恢复临界区的访问标志为未被访问remaindersection;untilfalse;,entrysection,exitsection,每个进程中访问临界资源的那段代码称为临界区。,临界区(criticalsection)：进程中访问临界资源的一段代码。进入区(entrysection)：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应“正在访问临界区”标志。退出区(exitsection)：用于将“正在访问临界区”标志清除。剩余区(remaindersection)：代码中的其余部分。,4.同步机制应遵循的规则,空闲让进：其他进程均不处于临界区；(2)忙则等待：有进程处于其临界区；(3)有限等待：等待进入临界区的进程不能死等；(4)让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）。,信号灯和P、V操作信号灯的概念,信号灯的概念是由Dijkstra提出的（1968）。他把互斥的关键概念抽象到信号量这个概念中，信号量是一个被保护的变量，只有P操作、V操作和一种称为信号量初始化操作才能访问和改变它的值。,信号灯的定义：信号灯是一个确定的二元组（s,q），s是一个具有非负初值的整型变量，q是一个初始状态为空的排队站。S代表资源的实体。在实际应用中应准确地说明s的意义和初值，每个信号灯都有一个队列，其初始状态为空。,信号灯的值仅能由P、V操作来改变，对信号灯的P操作记为：P(S)，P操作是一个原子操作。对信号灯的V操作记为：V(S),V操作是一个原子操作。在实际操作系统中，一般情况下是由机器硬件提供P、V操作的指令，当然是原子操作，若机器不提供P、V操作的指令，则操作系统提供P、V操作原语。,2.3.2信号量机制：一种同步机制,1.整型信号量最初由Dijkstra把整型信号量定义为一个整型量S，除初始化外，仅能通过两个标准的原子操作(AtomicOperation)wait(S)和signal(S)来访问。这两个操作一直被分别称为P、V操作。wait和signal操作可描述为：P原语wait(S)while(S0)；S-;signal(S)S+;Vsignal(S):原语通常唤醒进程等待队列中的头一个进程,2.记录型信号量在整型信号量机制中的wait操作，只要是信号量S0，就会不断地测试。因此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。,记录型信号量机制，则是一种不存在“忙等”现象的进程同步机制。在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表L，用于链接所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。它所包含的上述两个数据项可描述为：,typedefstructintvalue;structprocess_control_block*list;semaphore;,相应地，wait(S)操作可描述为p53：wait(semaphore*S)S-value-;if(S-value0)block(S-list)；,在记录型信号量机制中，S-value的初值表示系统中某类资源的数目，因而又称为资源信号量。如果S-value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。对它的每次wait操作，意味着进程请求一个单位的该类资源，当S-value0时，表示该类资源已分配完毕。,signal(S)操作可描述为p54：signal(semaphore*S)S-value+;if(S-value0)wakeup(S-list);,对信号量的每次signal操作，表示执行进程释放一个单位资源，若加1后仍是S-value0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S-list链表中的第一个等待进程唤醒。,P操作：wait(s)（1）s值减1；（2）若相减结果大于等于0，则进程继续执行；（3）若结果小于0，则该进程挂起。注：挂起该进程包括：保留调用进程CPU现场；置“等待”状态；入等待队列；转进程调度；,-s.count;/表示申请一个资源;,if(s.count0)/表示没有空闲资源;,调用进程进入等待队列s.queue;,阻塞调用进程;,V操作：signal(s),（1）s值加1；（2）若相加结果大于0，进程继续执行；（3）否则，唤醒一个（或多个）等待该信号灯的进程，然后本进程继续执行。,+s.count;/表示释放一个资源；if(s.count=0)/表示有进程处于阻塞状态；从等待队列s.queue中取出一个进程P;进程P进入就绪队列;,V原语通常唤醒等待队列中的头一个进程,P、V操作,临界区门前有棵树，用来挂红灯；进程想进CPU门；先得上树取盏灯（调用一次P）；取下一个去敲门（SS1）；如果树上没有灯取（S0）；树说欠你一盏灯（S为负时）；没辙只好外边排队等（WAIT（S）；得灯进程续运行，运行完了要出门（调用一次V)；上树还回一盏灯（SS1）；若有进程在催债（S0）；放个进去事完成（Release（S）。,AND型信号量集：是指同时需要多种资源且每种占用一个时的信号量操作。AND型信号量集的基本思想:在一个原语中申请整段代码需要的多个临界资源,要么全部分配给它,要么一个都不分配。,3.AND型信号量p54,在两个进程中都包含两个对Dmutex和Emutex的操作，即processA:processB:wait(Dmutex);wait(Emutex);wait(Emutex);wait(Dmutex);若进程A和B按下述次序交替执行wait操作：processA:wait(Dmutex);于是Dmutex=0processB:wait(Emutex);于是Emutex=0processA:wait(Emutex);于是Emutex=-1A阻塞processB:wait(Dmutex);于是Dmutex=-1B阻塞,AND同步机制的基本思想是：对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配。为此，在wait操作中，增加了一个“AND”条件，故称为AND同步，或称为同时wait操作，即Swait(Simultaneouswait)定义如下：,Swait(S1,S2,Sn)while(true)if(Si1elseplacetheprocessinthewaitingqueueassociatedwiththefirstSifoundwithSi1,andsettheprogramcountofthisprocesstothebeginningofSwaitoperation,Ssignal(S1,S2,Sn)while(true)for(i=1;i=ti，表示资源数量低于ti时，便不予分配），占用值为di（用于信号量的增减，即Si=Si-di和Si=Si+di）Swait(S1,t1,d1,.;Sn,tn,dn);Ssignal(S1,d1,.;Sn,dn);,一般信号量集用于同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的处理,4.信号量集,其中S为信号量，d为需求值，而t为下限值。Swait(S1,t1,d1,Sn,tn,dn)if(S1t1elsePlacetheexecutingprocessinthewaitingqueueofthefirstSiwithSitiandsetitsprogramcountertothebeginningoftheSwaitOperation.,signal(S1,d1,Sn,dn)for(i=1;i=n;i+)Si=Si+di;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueue,一般“信号量集”的几种特殊情况：(1)Swait(S,d,d)。此时在信号量集中只有一个信号量S，但允许它每次申请d个资源，当现有资源数少于d时，不予分配。(2)Swait(S,1,1)。此时的信号量集已蜕化为一般的记录型信号量(S1时)或互斥信号量(S=1时)。(3)Swait(S,1,0)。这是一种很特殊且很有用的信号量操作。当S1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。,进入临界区的准则：(1)每次至多有一个进程处于临界区；(2)当有若干个进程欲进入临界区时，应在有限的时间内使其进入；(3)进程在临界区内仅逗留有限的时间。,2.3.3.利用信号量实现互斥,为临界资源设置一个互斥信号量mutex(MUTualExclusion)，其初值为1；在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间必须成对使用P和V原语：遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）；P、V原语不能次序错误、重复或遗漏,信号量的应用,1.利用信号量实现进程互斥,semaphoremutex=1;PA()while(1)wait(mutex);criticalsectionsignal(mutex);remaindersection,PB()while(1)wait(mutex);criticalsectionsignal(mutex);remainderseetion注意：必须保证Wait（mutex）与Signal（mutex）成对出现。,2.利用信号量实现前趋关系,图2-10前趋图举例,p1()S1;signal(a);signal(b);p2()wait(a);S2;signal(c);signal(d);/p3()wait(b);S3;signal(e);/p4()wait(c);S4;signal(f);/p5()wait(d);S5;signal(g);/p6()wait(e);wait(f);wait(g);S6;/、main()semaphorea,b,c,d,e,f,g;a.value=b.value=c.value=0;/为每个前趋关系设置一个互斥信号量，其初值为0d.value=e.value=0;f.value=g.value=0;cobeginp1();p2();p3();p4();p5();p6();coend,2.4经典进程的同步问题,2.4.1生产者消费者问题由于生产者消费者问题是相互合作的进程关系的一种抽象，例如，在输入时，输入进程是生产者，计算进程是消费者；而在输出时，则计算进程是生产者，而打印进程是消费者，因此，该问题有很大的代表性及实用价值。,1.利用记录型信号量解决生产者消费者问题下面给出基于环形缓冲区的生产者与消费者关系的形式描述，设：（1）公用信号量mutex：初值为1，用于实现临界区互斥。（2）生产者私用信号量empty：初值为n，指示空缓冲块数目。（3）消费者私用信号量full：初值为0，指示满缓冲块数目。（4）整型量in和out初值均为0，in指示首空缓冲块序号，out指示首满缓冲块序号。模块设计如下：,intin=0,out=0;itembuffern;semaphoremutex=1,empty=n,full=0;voidproceducer()doproduceraniteminnextp;wait(empty);wait(mutex);bufferin=nextp;in=(in+1)%n;signal(mutex);signal(full);while(true),voidconsumer()dowait(full);wait(mutex);nextc=bufferout;out=(out+1)%n;signal(mutex);signal(empty);consumertheiteminnextc;while(true),voidmain()cobeginproceducer();comsumer();coend,在生产者消费者问题中应注意：首先，在每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对地出现；其次，对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它们分别处于不同的程序中。最后，在每个程序中的多个wait操作顺序不能颠倒。应先执行对资源信号量的wait操作，然后再执行对互斥信号量的wait操作，否则可能引起进程死锁。,2.利用AND信号量解决生产者消费者问题,intin=0,out=0;itembuffern;semaphoremutex=1,empty=n,full=0;voidproceducer()doproduceaniteminnextp;Swait(empty,mutex);buffer(in)=nextp;in=(in+1)%n;Ssignal(mutex,full);while(TURE),voidconsumer()doSwait(full,mutex);nextc=buffer(out);out=(out+1)%n;Ssignal(mutex,empty);consumertheiteminnextc;while(TURE);,2.哲学家进餐问题(thediningphilosophersproblem),问题描述：（由Dijkstra首先提出并解决）5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子，每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐；不出现有人永远拿不到筷子；,2.4.2哲学家进餐问题,1.利用记录型信号量解决哲学家进餐问题P77经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。其描述如下：semaphorechopstick5=1,1,1,1,1;,所有信号量均被初始化为1，第i位哲学家的活动可描述为：dowait(chopsticki);wait(chopstick(i+1)%5);eat;signal(chopsticki);signal(chopstick(i+1)%5);think;while(true);,上述算法可能出现每个哲学家拿到一只筷子的状况即出现死锁。可采取以下几种解决方法：(1)至多只允许有四位哲学家同时去拿左边的筷子，(2)仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。(3)规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。,2.利用AND信号量机制解决哲学家进餐问题在哲学家进餐问题中，要求每个哲学家先获得两个临界资源(筷子)后方能进餐，这在本质上就是前面所介绍的AND同步问题，故用AND信号量机制可获得最简洁的解法。semaphorechopstick5=1,1,1,1,1;dothink;Sswait(chopstick(i+1)%5,chopsticki);eat;Ssignal(chopstick(i+1)%5,chopsticki);while(true);,3.读者写者问题(thereaders-writersproblem)问题描述：对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许多个“读写”互斥，“写写”互斥，读读允许,1.利用记录型信号量解决读者-写者问题为实现Reader与Writer进程间在读或写时的互斥而设置了一个互斥信号量Wmutex。因此，仅当Readcount=0,表示尚无Reader进程在读时，Reader进程才需要执行Wait(Wmutex)操作。同理，仅当Reader进程在执行了Readcount减1操作后其值为0时，才须执行signal(Wmutex)操作，以便让Writer进程写。又因为Readcount是一个可被多个Reader进程访问的临界资源，因此，应该为它设置一个互斥信号量rmutex。,读者-写者问题可描述如下：semaphorermutex=1,wmutex=1;intreadcount=0;voidreader()dowait(rmutex);if(readcount=0)wait(wmutex);/若wait(wmutex)为0则说明正有进程在作写操作，进程自我阻塞Readcount+;signal(rmutex);performreadoperation;,wait(rmutex);readcount-;/读操作结束故再次调用readcount使其减1if(readcount=0)signal(wmutex);signal(rmutex);while(true);,voidwriter()dowait(wmutex);performwriteoperation;signal(wmutex);while(true);voidmain()cobeginreader();writer();coend,2.利用信号量集机制解决读者-写者问题,intRN;semaphoreL=RN,mx=1;voidreader()doSwait(L,1,1);/只要有个进程在读那么开关就允许多个进程同时读Swait(mx,1,0);performreadoperation;Ssignal(L,1);while(true);,信号量集机制的几种特别情况,voidwriter()doSwait(mx,1,1;L,RN,0);/mx=1所以为互斥performwriteoperation;Ssignal(mx,1);while(true);,voidmain()cobeginreader();writer();coend,补充题1：,有十个读者和两个编辑同时处理一篇文章，对于读操作是可以同时进行的，若有读者正在读这篇文章，编辑就不能工作，若编辑正在处理这篇文章，读者就不能作读操作，编辑与编辑的工作也是互斥的，试用信号灯及P、V操作写出读者与编辑之间协同工作的程序描述。,信号量机制的引入解决了进程同步的描述问题，但信号量的大量同步操作分散在各个进程中不便于管理，还有可能导致系统死锁。如：生产者消费者问题中将P、V颠倒可能死锁。为此Dijkstra于1971年提出：把所有进程对某一种临界资源的同步操作都集中起来，构成一个所谓的秘书进程。凡要访问该临界资源的进程，都需先报告秘书，由秘书来实现诸进程对同一临界资源的互斥使用。,2.5管程机制,1.管程的引入,2.5.1管程的基本概念,1.管程的定义,管程由三部分组成：局部于管程的共享变量说明；对该数据结构进行操作的一组过程；对局部于管程的数据设置初始值的语句。此外，还须为管程赋予一个名字。,所谓管程就是：（进程同步）将共享变量以及对于共享变量所能进行的所有操作集中在一个模块中，由此构成的软件包或模块。管程有一个很重要的特性，使它们能有效地完成互斥：任一时刻管程中只能有一个活跃进程。,图2-11管程的示意图,管程的语法如下：typemonitor-name=monitor/管程名variabledeclarations/*共享变量说明*/procedureentryP1();/*对数据结构操作的函数*/beginend;procedureentryP2();beginend;,procedureentryPn();beginend;begininitializationcode;/*设初值语句*/end,管程的基本特性局部于管程的数据只能被局部于管程内的函数所访问。一个进程只有通过调用管程内的函数才能进入管程访问共享数据。每次仅允许一个进程在管程内执行某个函数。由于管程是一个语言成分，所以管程的互斥访问完全由编译程序在编译时自动添加上，无需程序员关心，而且保证正确。,管程还提供了一种办法以使得进程在无法继续运行时被阻塞。解决方法在于引入条件变量(conditionvariables)，及相关的两个操作：Wait和Signal。当一个管程过程发现它无法继续时，它在某些条件变量上执行Wait。这个动作引起调用进程阻塞。它也允许另一个先前被挡在管程之外的进程现在进入管程。,2.条件变量,管程中对每个条件变量，都须予以说明，其形式为：Varx,y:condition。该变量应置于wait和signal之前，即可表示为X.wait和X.signal。例如，由于共享数据被占用而使调用进程