计算机操作系统教程文件.ppt

《计算机操作系统教程文件.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统教程文件.ppt（141页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章 进 程 管 理 计算机操作系统第二章 进 程 管 理 若(Pi,Pj)，可写为 Pi Pj，前者是后者的前驱，后者是前者的直接后继。在前趋图中，初始结点无前驱，终止结点无后继。前驱图中必须不存在循环，否则无法实现。所以前趋图是一个有向无循环图，记为DAG(Directed Acyclic Graph)举例：IiCiPi 和 S1S2S3 第二章 进 程 管 理 对于图 2-2(a)所示的前趋图，存在下述11个前趋关系：P1P2,P1P3,P1P4,P2P5,P3P5,P4P6,P4P7,P5P8,P6P8,P7P9,P8P9第二章 进 程 管 理 或表示为：P=P1,P2,P3,P4,

2、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 这种前驱关系无法满足。第二章 进 程 管 理 对于具有下述四条语句的程序段：S1:a=x+2 S2:b=y+4 S3:c=a+b S4:d=c+b 图 2-4 四条语句的前趋关系第二章 进 程 管 理 2.1.2 程序的顺序执行及其特征程序的顺序执行及其特征 1.单道

3、程序的顺序执行单道程序的顺序执行 程序的顺序执行是指单道程序按照程序规定的顺序去执行。这种执行顺序可以表示为前驱关系。仅当前一操作(程序段)执行完后，才能执行后继操作。例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。又例如：S1:a=x+y;S2:b=a-5;S3:c=b+1;显然S1作完，S2才能作。S2作完，S3才能作。第二章 进 程 管 理 图 2-1 程序的顺序执行 把这两个例子表示为前驱图：第二章 进 程 管 理 2.单道程序顺序执行时的特征单道程序顺序执行时的特征 顺序性：顺序性：执行完一条，紧接着执行下一条。程序规定的顺序就是程序执行的顺序，程

4、序和计算机执行程序的活动严格地一一对应。封闭性：封闭性：程序执行时，独占系统的全部资源，其计算结果值取决于程序本身。可再现性：可再现性：只要程序执行的环境和初始条件相同，必将获得相同的结果，与其执行的速度无关。即执行程序的两个动作之间如有停顿，不会影响程序的执行结果。第二章 进 程 管 理 2.1.3 程序的并发执行及其特征程序的并发执行及其特征 1.程序的并发执行程序的并发执行 图 2-3 并发执行时的前趋图 在该例中存在下述前趋关系：IiCi，IiIi+1,CiPi,CiCi+1，PiPi+1 而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之间，可以并发执行。第二章

5、进 程 管 理 2资源共享 系统中的硬件、软件资源不再为单个用户程序所独占，而由几道用户程序共同使用。那么，这些资源的状态也就不再取决于一道程序，而是由多道用户程序的活动共同决定，这就打破了一道程序封闭于一个系统中执行的局面。第二章 进 程 管 理 3.程序并发执行时的特征程序并发执行时的特征（1）失去了程序的封闭性和可再现性 举例：观察者与报告者并行工作，卡车单向行驶于公路，观察者对通过的卡车计数，报告者定时打印观察者的计数值，然后将计数器清零。BeginCount:integer;Count:=0;Cobegin Observer Begin L1:Observe next car;Cou

6、nt:=Count+1;Goto L1:EndReporter Begin L2:.Print Count;Count:=0;EndCoendEnd 第二章 进 程 管 理 三种不同的执行序列:假设执行前，二者的共享变量c=n序列 报告者打印的值 观察者执行后的值a)c=c+1;print c;c=0;n+1 0b)print c;c=0;c=c+1;n 1c)print c;c=c+1;c=0;n 0 执行的结果与执行的序列有关，即与执行的速度有关，就会有三种不同的执行结果。第二章 进 程 管 理（2）.程序和计算机执行程序的活动不再一一对应，即程序与计算不再一一对应。程序顺序执行时，程序和

7、计算是一一对应的。并发执行时:一个并发程序可以为多个用户作业调用，使该程序处于多个执行当中，形成多个计算，.一个程序也可以分为多个进程或者线程，并发地执行，第二章 进 程 管 理（3）并发的程序之间相互制约，使他们走走停停，出现了间断性 资源的共享和并发活动时的系统的工作情况错综复杂，表现在并发程序之间的相互依赖和相互制约方面，直接制约关系，发生在彼此有逻辑关系的几个并发程序活动之间，如输入，计算，打印形成的停-等关系，间接制约是由竞争使用同一资源引起的，也引起停-等。各个程序活动走走停停，具有执行-暂停-执行的活动规律。第二章 进 程 管 理（4）进程概念的引入 综上所述，在多道程序环境下，

8、程序的并发执行代替了程序的顺序执行，破坏了程序的封闭性和可再现性，使得程序和计算不再一一对应，而且，由于资源的共享和程序的并发执行导致在各个程序的活动之间可能存在相互制约关系，即 程序活动不再处于一个封闭的系统中，出现了许多新的特性，如独立性，并发性，动态性，相互制约性，因此，程序这个静态的概念已不能如实地反映程序活动的这些特征。二 十 世 纪 六 十 年 代 中 期，MULTICS的 设 计 者 和 以E.W.Dijkstra为 首 的 T.H.E系 统 的 设 计 者，开 始 使 用 进 程（Process）来描述系统和用户的程序活动，IBM用任务（Task）来描述。第二章 进 程 管 理

9、 2.2 进程的定义、表示、调度状态和特征进程的定义、表示、调度状态和特征2.2.1 定义定义有多种说法：程序是行为的规则，进程是程序在处理机上执行时所发生的活动。进程是一个程序与其数据在处理机上顺序执行时所发生的活动。进程是程序的一次执行，该程序可以与其他的程序并发地执行。进程是程序在一个数据集合上运行的过程，是系统进行资源分配和调度的独立单位。本书定义：进程是进程实体的运行过程，是系统进行资源分配和调度的独立单位。第二章 进 程 管 理 2.2.2 进程的表示进程的表示1进程的组成进程的组成进程由三部分组成:(进程的结构性定义)进程实体=代码+数据+进程控制块 =CODE+DATA+PCB

10、 程程序序代代码码CODE：描述进程要完成的功能，是进程执行时不可修改的部分.数数据据集集合合DATA：包括程序在执行时所需的数据和工作区，是进程的可修改的部分，只能为一个进程专用。程序和数据集合两部分是进程存在的物质基础。第二章 进 程 管 理 进程控制块进程控制块（Process Control Block PCB）是系统创建进程时，为其开辟的专用的存储区，是记录型的数据结构，包括进程的描述信息，和控制信息。是进程动态特性的集中反映。PCB随着进程的创建而建立，随着进程的撤销而撤销，随着进程的运行而变化。系统通过PCB感知进程的存在，通过PCB来控制和管理进程，是进程存在的唯一标志。正像在

11、磁盘上通过目录来感知文件的存在。PCB 常驻于内存的专门的区域，组织称为若干队列，被系统频繁地访问。进程三部分的组合有几种形态：第二章 进 程 管 理 PCB程序数据集合PCBPCBPCB程序程序数据集合数据集合数据集合有人说，程序、数据是进程的躯体，PCB是进程的灵魂。第二章 进 程 管 理 进程控制块的作用进程控制块的作用 进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。这可以回答一个问题。为什么说，在多道程序的环境下，程序，包含数据，不能独立运行

12、，而进程则成为独立运行的基本单位。第二章 进 程 管 理 2.进程控制块中的信息进程控制块中的信息（1）进程标识符进程标识符 进程标识符用于惟一地标识一个进程。一个进程通常有两种标识符：内部标识符。在所有的操作系统中，都为每一个进 程赋予一个惟一的数字标识符，它通常是一个进程的序号。设置内部标识符主要是为了方便系统使用。外部标识符。它由创建者提供，通常是由字母、数字组成，往往是由用户(进程)在访问该进程时使用。为了描述进程的家族关系，还应设置父进程标识及子进程标识。此外，还可设置用户标识，以指示拥有该进程的用户。第二章 进 程 管 理（2）处理机状态 处理机状态信息主要是由处理机的各种寄存器中

13、的内容组成的。通用寄存器，又称为用户可视寄存器，它们是用户程序可以访问的，用于暂存信息，在大多数处理机中，有 832 个通用寄存器，在RISC结构的计算机中可超过 100 个；指令计数器，其中存放了要访问的下一条指令的地址；程序状态字PSW，其中含有状态信息，如条件码、执行方式、中断屏蔽标志等；用户栈指针，指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶。第二章 进 程 管 理（3）进程调度信息 在PCB中还存放一些与进程调度和进程对换有关的信息，包括：进程状态，指明进程的当前状态，作为进程调度和对换时的依据；进程优先级，用于描述进程使

14、用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机；进程调度所需的其它信息，它们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等；事件，是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。第二章 进 程 管 理（4）进程控制信息 进程控制信息包括：程序和数据的地址，是指进程的程序和数据所在的内存或外存地(首)址，以便再调度到该进程执行时，能从PCB中找到其程序和数据；进程同步和通信机制，指实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等，它们可能全部或部分地放在PCB中；资源清单，是一张列出了除CPU以外的、进程所需的全部资源

15、及已经分配到该进程的资源的清单；链接指针，它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址。第二章 进 程 管 理 3.进程控制块的组织方式进程控制块的组织方式 1)链接方式 图 2-7 PCB链接队列示意图 第二章 进 程 管 理 2)索引方式 图 2-8 按索引方式组织PCB 第二章 进 程 管 理 2.2.3 进程的调度状态进程的调度状态1三种基本的调度状态三种基本的调度状态 运行状态：进程已获得必要的资源，并占有一个处理机，处理机正在执行该进程的程序代码，是正在运行的进程，一个系统的现运行进程数必可用的处理机数。就绪状态：进程已具备运行条件，等待分配处理机，称为可运行状态

16、，具有这种状态的进程有多个，要排成队列。阻塞状态：进程在运行过程中，因为等待某一事件，如I/O操作的完成，而暂时不能运行的状态，即运行受到阻碍，称为不可运行的状态，这样的进程也有多个，也要排成队列。第二章 进 程 管 理 图 2-5 进程的三种基本状态及其转换 2.进程的三种基本状态的转换进程的三种基本状态的转换 第二章 进 程 管 理 3.挂起状态挂起状态（1）引入挂起状态的原因）引入挂起状态的原因 终端用户的请求。父进程请求。负荷调节的需要。操作系统的需要（2）挂起状态的含义）挂起状态的含义 处于就绪状态的进程挂起时，不再接受调度，成为静止就绪状态。处于阻塞状态的进程挂起时，成为静止阻塞状

17、态，当其所期望的事件出现时，变为静止就绪。新状态：新状态：进程刚刚建立，尚未进入就绪队列，终止状态：终止状态：进程的运行已经结束，已经溢出队列，但尚未撤销。第二章 进 程 管 理 图 2-6 具有挂起状态的进程状态图 4五种状态的的转换图五种状态的的转换图 进程状态的转换活动就绪静止就绪。活动阻塞静止阻塞。静止就绪活动就绪。静止阻塞活动阻塞。第二章 进 程 管 理 2.2.4进程的特性进程的特性 结构特征：进程实体由三部分组成。尤其是PCB，是必不可少的部分。动态性：由创建而产生，由调度而执行，由撤销而消亡。进程实体有一定的生命周期。并发性：多个进程实体共处于内存中，在一段时间内同时运行。独立

18、性：进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。异步性：进程按各自独立的、不可预知的速度向前推进，进程实体按异步方式运行。这五条也是进程与程序的主要区别。第二章 进 程 管 理 2.3 进进 程程 控控 制制 2.3.1 进程控制的基本概念进程控制的基本概念 1什么是进程控制？什么是进程控制？进程控制是指系统使用一些具有特定功能的程序段来创建进程、撤销进程、完成进程各种状态的转换，达到多进程高效并发执行和协调，实现资源共享的目的。2谁来完成进程控制？谁来完成进程控制？完完成成进进程程控控制制的的机机构构是是操操作作系系统统的的内内核核Kernel 中中的的相相关关软软件件模

19、模块块。操作系统内核是紧靠硬件的第一层扩充软件，包括与硬件紧密相关的模块和运行频率高的模块，它们常驻内存，需要加以特殊的保护。第二章 进 程 管 理 操作系统如何才能得到对处理机的控制操作系统如何才能得到对处理机的控制 操作系统是以中断来驱动的，即OS通过中断方式才能得对于处理机的控制，进程控制是以事件来驱动的。有三种情况会打断当前进程的执行，外部随机事件的中断，错误或异常条件管理的TRAP；调用了操作系统的功能。OS得得到到处处理理机机的的控控制制权权后后，是是否否作作为为进进程程在在系系统统中中运运行行，有三种方案。有三种方案。非进程的内核模式 OS在用户进程内部执行 操作系统的进程方式，

20、OS的各种功能作为系统进程运行，称为服务器进程，与用户进程构成客户机/服务器的模式 第二章 进 程 管 理 3怎样进行进程的控制？怎样进行进程的控制？在在OS中，通常把进程控制所用到的程序段作为中，通常把进程控制所用到的程序段作为原语原语。原语是在系统态下执行的某些具有特定功能的程序段，一类是机器指令级的，执行期间不允许中断，是一个不可分割的单位，另一类是功能级的。作为原语的程序段不允许并发地执行，并且，都在系统态下执行，被高层软件调用来完成某个系统管理的功能。以事件来驱动；以原语来实现，这是学习进程控制的基本观点。第二章 进 程 管 理 2.3.2 进程的创建进程的创建 1.进程图(Proc

21、ess Graph)图 2-9 进程树 进程图是描述进程之间家族关系的有向树。结点代表进程，有向边由父进程指向子进程。树的根结点是进程家族的祖先。子进程可以继承父进程的资源，撤销时归还。若要撤销父进程，也须同时撤销其子进程。在PCB中，记录了家族关系。第二章 进 程 管 理 2.引起创建进程的事件引起创建进程的事件(1)用户登录用户登录。分时系统中。(2)(2)作业调度作业调度。批处理系统中。(3)(3)提供服务提供服务。用户进程提出请求(4)以上三种情况，都由系统内核为其创建一个新进程。(5)(4)应用请求应用请求。基于应用进程的需求，由它自己创建一个新的进程。第二章 进 程 管 理 3.进

22、程的创建进程的创建(Creation of Progress)调用进程创建原语create()(1)申请空白PCB。(2)为新进程分配资源。(3)初始化进程控制块。(4)将新进程插入就绪队列，如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列。第二章 进 程 管 理 2.3.3 进程的终止进程的终止 1.引起进程终止引起进程终止(Termination of Process)的事件的事件 1)正常结束 在任何计算机系统中，都应有一个用于表示进程已经运行完成的指示。进程运行完毕，可产生一个中断。2)异常结束 在进程运行期间，由于出现某些错误和故障而迫使进程终止。越界错误。保护错。非法指令。特

23、权指令错。运行超时。等待超时。算术运算错。I/O故障。第二章 进 程 管 理 3)外界干预外界干预并非指在本进程运行中出现了异常事件，而是指进程应外界的请求而终止运行。这些干预有：操操作作员员或或操操作作系系统统干干预预。由于某种原因，例如，发生了死锁，由操作员或操作系统终止该进程；父父进进程程请请求求。由于父进程具有终止自己的任何子孙进程的权利，因而当父进程提出请求时，系统将终止该进程；父父进进程程终终止止。当父进程终止时，OS也将他的所有子孙进程终止。第二章 进 程 管 理 2.进程的终止过程进程的终止过程 调用进程终止原语，执行以下操作。调用进程终止原语，执行以下操作。(1)根据被终止进

24、程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。(2)若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。(3)若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程。(4)将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。(5)将被终止进程(它的PCB)从所在队列(或链表)中移出，等待其他程序来搜集信息。第二章 进 程 管 理 2.3.4 进程的阻塞与唤醒进程的阻塞与唤醒1.引起进程阻塞和唤醒的事件引起进程阻塞和唤醒的事件 请求系统服务请求系统服务，而要求得不到满足。启动某种操

25、作启动某种操作，必须待其完成，如I/O。新数据尚未到达新数据尚未到达，需要此数据的进程只能等待。无新工作可做无新工作可做，具有特定功能的系统进程。第二章 进 程 管 理 2.进程阻塞过程进程阻塞过程 进程通过调用阻塞原语block把自己阻塞。阻塞是进程自身的一种主动行为。该进程立即停止执行停止执行，将CPU控制权交给OS。OS将该进程PCB中的现行状态由“执行”改改为为阻阻塞塞，保留被阻塞进程的处理机状态，存储相关信息，将该进程PCB插插入入阻阻塞塞队队列列。如果存在多个阻塞队列，应将该进程插入到具有相同事件的阻塞(等待)队列。转调度程序进行重重新新调调度度，将处理机分配给另一就绪进程，并进行

26、切换，即按新进程的PCB中的处理机状态设置CPU的环境。第二章 进 程 管 理 3.进程唤醒过程进程唤醒过程 当被阻塞进程所期待的事件出现时，如I/O完成或其所期待的数据已经到达，则由有关进程(比如，用完并释放了该I/O设备的进程)调用唤醒原语wakeup()，将等待该事件的进程唤醒。唤醒原语执行的过程是：首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪，然后再将该PCB插入到就绪队列中。第二章 进 程 管 理 2.3.5 进程的挂起与激活进程的挂起与激活 1.进程的挂起进程的挂起 当出现了引起进程挂起的事件时，比如，用户进程请求将自己挂起，或父进程请求将自

27、己的某个子进程挂起，系统将利用挂起原语suspend()将指定进程或处于阻塞状态的进程挂起。挂起原语的执行过程是：首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。为了方便用户或父进程考查该进程的运行情况而把该进程的PCB复制到某指定的内存区域。最后，若被挂起的进程正在执行，则转向调度程序重新调度。第二章 进 程 管 理 2.进程的激活过程进程的激活过程 当发生激活进程的事件时，例如，父进程或用户进程请求激活指定进程，若该进程驻留在外存而内存中已有足够的空间时，则可将在外存上处于静止就绪状态的进程换入内存。这时，系统将利用激活原语ac

28、tive()将指定进程激活。激活原语先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞便将之改为活动阻塞。假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重新调度，即由调度程序将被激活进程与当前进程进行优先级的比较，如果被激活进程的优先级更低，就不必重新调度；否则，立即剥夺当前进程的运行，把处理机分配给刚被激活的进程。第二章 进 程 管 理 2.3 进进 程程 同同 步步2.3.1 进程同步的基本概念进程同步的基本概念1.两种形式的制约关系两种形式的制约关系（1）直接相互制约关系 一进程收不到另一进程提供的必要的信息，就不能继续

29、运行下去，即两个进程在某些点要交换信息，称为直接制约关系，形式为进程-进程，如 ICP。（2）间接相互制约关系 一个资源不允许两个进程同时使用，若一个进程正在使用它，另一个进程要使用这个资源，就只能等到占用资源的进程释放后才能使用，称为间接制约关系，形式为进程-资源-进程。第二章 进 程 管 理 2进程之间的同步关系进程之间的同步关系 进程在异步的环境下运行，以各自的独立的不可预知的速度向运行的终点推进，有时必须相互配合。例1：公共汽车上，司机和售票员的关系。司机正常行车到站停车开车售票员售票开车门关车门第二章 进 程 管 理 例2：Z=F1(X)*F2(X)进程P1 计算F1(X)进程P2算

30、完F2(X)了吗 取P2计算结果，计算Z 进程P2 计算F2(X)设置计算完标志 终止 发信号 阻塞 Y N 终止 第二章 进 程 管 理（1）临界资源）临界资源（Critical Resource）临界资源是一次仅允许一个进程使用的资源 许多物理设备，如 输入机，打印机，磁带机，都是，临界资源也称为可逐次再使用资源，也称为互斥资源 进程互斥是指两个或两个以上的进程，由于不能同时使用同一临界资源，只能一个进程使用完毕，另一进程才能使用的现象。举例：p1,p2使用打印机：请求资源R释放资源R请求资源R释放资源R进程A进程B分配拒绝R使用R阻塞唤醒就绪运行第二章 进 程 管 理（2）另一类临界资源

31、）另一类临界资源 由若干个进程所共享的变量，数据结构，表格和队列，是另一类临界资源，通常也不允许两个进程同时使用。在高级语言中，常有这样的赋值语句。X=X+1,但是，实际上这条语句是由多条执行指令构成的，其对应的汇编语言往往是:LOAD A,X INC A,1 STORE A,X 第二章 进 程 管 理 举例：现有两个进程P1,P2共享同一变量X,P1,P2的主要操作为：P1:R1=X;R1=R1+1;X=R1;P2:R2=X;R2=R2+1;X=R2;其中：R1,R2 是处理机上的两个通用寄存器，理想的正确的结果是，两个进程各对于X作加一的操作，两进程共同访问和修改的结果，应该使X加2。第二

32、章 进 程 管 理 当P1,P2并发执行的时候，他们按照各自的独立的速度向前推进，则可能的执行顺序是：P1:R1=X;P2:R2=X;P1:R1=R1+1;X=R1;P2:R2=R2+1;X=R2;其结果仅使得X加了1，为什么？是因为没有把X当作临界资源，没有实施互斥的操作。第二章 进 程 管 理（3）互斥的定义）互斥的定义 互互斥斥是指一种现象，一组并发进程中的一个或多个程序段，因共享某一公有资源，而导致它们必须作为一个不允许交叉执行的单位来执行，互斥也指系统分配和释放相应的公有资源的管理办法。我们把这种由于共享某一公有资源而引起的，在临界区内不允许并发进程交叉执行的现象，称为由共享公享资源

33、而造成的，对并发进程执行速度的间接制约。当程序段本身作为公有资源，被多个并发的进程共享时，仅当该程序为纯过程，即执行过程中不改变过程自身的代码，各个并发的进程才可以同时访问它 第二章 进 程 管 理 4临界区临界区(critical section)临界区是每个进程中访问临界资源的那段代码。对于此类临界资源的互斥访问，是指应保证诸进程互斥地进入自己的临界区，即各个进程互斥地执行操作临界资源的程序段。把不允许多个并发进程交叉执行的一段程序，称为临界区，对于临界区的互斥访问是由属于不同的并发进程的程序段共享公用数据、变量、或者操作公共外设而引起的，因此，临界区也可以被称为访问公共数据或访问公共资源

34、的那段程序。第二章 进 程 管 理 可把一个访问临界资源的循环进程描述如下：repeat critical section;remainder section;until false;entry sectionexit section5程序的四段模式程序的四段模式 进入区、临界区、退出区、剩余区进入区、临界区、退出区、剩余区 第二章 进 程 管 理 6.同步机制应遵循的规则同步机制应遵循的规则（1）空闲让进。（2）忙则等待（3）有限等待。（4）让权等待。第二章 进 程 管 理 2.3.2 信号量机制信号量机制 1 概述概述 荷荷兰兰的的Dijkstra，1965年年提提出出信信号号量量（Sem

35、aphores）的的同同步步机机制制。基基本本原原则则是是：在在多多个个相相互互合合作作的的进进程程之之间间，用用信信号号量量来来同同步步，一一个个进进程程强强制制地地被被停停在在一一个个特特定定的的地地方方，直直到到收收到到一一个专门的信号。个专门的信号。信信号号量量的的主主要要部部分分是是一一个个整整数数型型变变量量，对对它它只只能能进进行行三三个个操作操作，可被初始化为一个非负数，可被初始化为一个非负数，P操作，操作，WAIT操作，荷兰语：操作，荷兰语：Passeren,V操作，操作，SIGNAL操作，荷兰语：操作，荷兰语：Verhoog。信信号号量量机机制制既既可可以以用用于于解解决决

36、互互斥斥的的问问题题，也也可可以以解解决决同同步步的问题的问题。第二章 进 程 管 理 2整型信号量整型信号量（1）整型信号量的定义）整型信号量的定义type semaphore =integer;var S:semaphore;S:=非负数非负数;procedure wait(S):While S=1 Then Ri=Ri-1;Xk=Ri;signal(S);输出一张票；Else signal(S);输出：票已经售完 Endif End Parend End 第二章 进 程 管 理 小结：用信号量实现互斥的特点：定义公用的信号量S，并且，将它的初始值设置为1。同步原语P(S)和V(S)必须在

37、一个进程中成对地使用，并且，将临界区的程序段放在其中。如果有一个进程进入了临界区，S就变为非正，其余的进程就只能等待，这样，就实现了多个进程的互斥。第二章 进 程 管 理 举例举例2.利用信号量实现进程互斥利用信号量实现进程互斥 利用信号量实现进程互斥的进程可描述如下：利用信号量实现进程互斥的进程可描述如下：Var mutex:semaphore=1;begin parbegin process 1:begin repeat wait(mutex);critical section signal(mutex);remainder section until false;end process

38、2:begin repeat wait(mutex);critical section signal(mutex);remainder section until false;end parend end 第二章 进 程 管 理（3）利用信号量实现进程之间同步）利用信号量实现进程之间同步 对于前驱图：S1 S2 进程P1中的S1操作完成后，进程P2中的S2才能开始。为二者定义信号量S，初值设为0。进程P1.S1;(S=0)L1:signal(S);.(S=1)进程P2L2:wait(S);等待S=1S2;S=0.第二章 进 程 管 理 举例1：利用信号量实现前趋关系利用信号量实现前趋关系 图

39、2-10 前趋图举例 第二章 进 程 管 理 Var a,b,c,d,e,f,g;semaphore=0,0,0,0,0,0,0;begin parbegin begin S1;signal(a);signal(b);end;begin wait(a);S2;signal(c);signal(d);end;begin wait(b);S3;signal(e);end;begin wait(c);S4;signal(f);end;begin wait(d);S5;signal(g);end;begin wait(e);wait(f);wait(g);S6;end;parend end 第二章 进

40、 程 管 理 例2：公共汽车上，司机和售票员的关系。司机正常行车到站停车开车售票员售票Wait(S1);关车门Signal(S1);Wait(S2);开车门Signal(S2);第二章 进 程 管 理 小结：用信号量来实现同步的特点，小结：用信号量来实现同步的特点，对于前驱进程和后继进程，共用一个信号量，来协调它们的执行顺序，信号量的初值设置为0，前驱进程首先做事，做完了，发信号，后继进程要先等待，然后做事，（4）私用信号量和公用信号量）私用信号量和公用信号量互斥时使用的信号量与所有的并发进程有关，所以，称为公用的信号量。实现进程之间的同步时候，也将进程之间发送的消息，看作信号量，因为它只与制

41、约进程和被制约进程有关，而不是与整组的并发进程有关，所以，称为私用信号量。（5）这是以忙等待处理的信号量机制）这是以忙等待处理的信号量机制 第二章 进 程 管 理 3.记录型信号量记录型信号量 整型信号量机制中的wait操作，未遵循“让权等待”的准则，使进程处于“忙等”的状态。记录型信号量机制不存在“忙等”，等待时进程阻塞，放弃CPU。多个进程等待访问同一临界资源，必须排成队列，因此引入链表指针。记录型信号量的定义：type semaphore=recordvalue:integer;L:list of process;end 第二章 进 程 管 理 相应地，wait(S)和signal(S)

42、操作可描述为：procedure wait(S)var S:semaphore;beginS.value=S.value-1;if S.value0 then block(S,L)endprocedure signal(S)var S:semaphore;beginS.value=S.value+1;if S.value0 then wakeup(S,L);end第二章 进 程 管 理 4.AND型信号量型信号量 问题：执行多次wait操作，如顺序不当，可能引起死锁。例如：process A:process B:wait(Dmutex);wait(Emutex);wait(Emutex);wa

43、it(Dmutex);若进程A和B按下述次序交替执行wait操作：process A:wait(Dmutex);于是Dmutex=0 process B:wait(Emutex);于是Emutex=0 process A:wait(Emutex);于是Emutex=-1 A阻塞 process B:wait(Dmutex);于是Dmutex=-1 B阻塞 第二章 进 程 管 理 AND同步机制的基本思想 将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。亦即，对若干个临界资源的分配，

44、采取原子操作方式：要要么么全全部部分分配配到到进进程程，要要么么一一个个也也不不分分配配。由死锁理论可知，这样就可避免上述死锁情况的发生。为此，在wait操作中，增加了一个“AND”条件，故称为AND同步，或称为同时wait操作，即Swait(Simultaneous wait)。第二章 进 程 管 理 定义如下：Swait(S1,S2,Sn)if Si1 and and Sn1 then for i=1 to n do Si=Si-1;endfor elseplace the process in the waiting queue associated with the first Si

45、found with Si1,and set the program count of this process to the beginning of Swait operation endif 第二章 进 程 管 理 Ssignal(S1,S2,Sn)for i=1 to n do Si=Si+1;Remove all the process waiting in the queue associated with Si into the ready queue.endfor;5.信号量集信号量集 问题：问题：P、V操作仅能对信号量加操作仅能对信号量加1减减1，每次只能获得或释放一个，每次

46、只能获得或释放一个资源，如果以此需要多个同类资源，则操作低效。资源，如果以此需要多个同类资源，则操作低效。有时，当资源数量低于某一下限时，便不予分配。有时，当资源数量低于某一下限时，便不予分配。第二章 进 程 管 理 一般化的信号量机制一般化的信号量机制 S为信号量，为信号量，d为需求值，为需求值，t为下限值。为下限值。Swait(S1,t1,d1,Sn,tn,dn)if Sit1 and and Sntn then for i=1 to n do Si=Si-di;endforelse Place the executing process in the waiting queue of t

47、he first Si with Siti and set its program counter to the beginning of the Swait Operation.endif 第二章 进 程 管 理 signal(S1,d1,Sn,dn)For i=1 to n do Si=Si+di;Remove all the process waiting in the queue associated with Si into the ready queueendfor;第二章 进 程 管 理 一般“信号量集”的几种特殊情况：(1)Swait(S,d,d)。此时在信号量集中只有一个信号

48、量S，但允许它每次申请d个资源，当现有资源数少于d时，不予分配。(2)Swait(S,1,1)。此时的信号量集已蜕化为一般的记录型信号量(S1时)或互斥信号量(S=1时)。(3)Swait(S,1,0)。这是一种很特殊且很有用的信号量操作。当S1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。第二章 进 程 管 理 6.同步原语的不可分割性同步原语的不可分割性信号量本身是多个进程可以访问的共享变量，P、V操作代码都是临界区代码，在任何时候，只能允许一个进程执行同步原语，操作系统规定：信号量上的同步原语是原子操作。是一个整体不可分的操作，包含两

49、层意思：保证进程间互斥地使用同步原语。整体操作，不可分割，即不可打断其执行，不可中断。现代操作系统，一般用硬件和固件直接实现同步原语，并保证互斥使用和整体性。第二章 进 程 管 理 2.4 经典进程的同步问题经典进程的同步问题 2.4.1 生产者生产者消费者问题消费者问题(The proceducer-consumer problem)1.1.生产者生产者消费者问题是许多并发进程间存在的内在关系的一消费者问题是许多并发进程间存在的内在关系的一种抽象，有代表性。种抽象，有代表性。2.2.问题描述与分析问题描述与分析1)通过一个环形缓冲区（实际是长度为n的有界缓冲区，n0）将一群生产者进程和一群消

50、费者进程联系起来，并且生产者和消费者相互等效。0123n-1P1P2.PmC1C2.Ck满单元空单元第二章 进 程 管 理 2)生产者和消费者的同步关系同步即协调配合问题。有货才可取，有空才能放。当缓冲区满时，生产者等待消费者；当缓冲区空时，消费者等待生产者。3)生产者和消费者的互斥关系m个生产者之间，k个消费者之间，生产者与消费者之间必须互斥的访问缓冲区。生产者消费者缓冲区空缓冲区满生产者消费者互斥互斥互斥第二章 进 程 管 理 3.解决方案解决方案 设置公用信号量mutex，初值为1，表示没有进程进入自己的临界区，用于实现各进程间互斥。设置私用信号量full，用于表示缓冲区中产品数目（满单