计算机操作系统第2章进程管理ppt课件.ppt

计算机操作系统,南京工业大学信息学院,第二章 进程管理, 进程的基本概念 进程控制 进程同步 经典进程同步问题 进程通信 线程,这一章介绍如下几个问题：,2.1 进程的基本概念(1),程序的顺序执行及其特征,顺序执行包含两层含义： 对于多个用户程序来说，所有程序是依次执行的。（外部顺序性） 对于一个程序来说，它的所有指令是按序执行的。（内部顺序性）,2.1 进程的基本概念(2),程序顺序执行的特征,（1）顺序性：,处理机的操作严格按照程序所规定的顺序执行，即每一操作必须在下一操作开始之前结束（或者说下一操作必须在当前操作结束后才能开始）。,（2）封闭性：,程序是在封闭的环境下执行的。即程序运行时独占全机资源，资源的状态（除初始态外）只有本程序才能改变它。程序一旦开始执行，其执行结果不受外界影响。,（3）可再现性：,只要程序执行时的环境和初始条件相同，当程序重复执行时，都将获得相同的结果。,2.1 进程的基本概念(3),程序的并发执行及其特征,程序的并发执行包括两层含义：,对于一个程序来说，它的所有指令是按序执行的。（内部顺序性） 对于多个程序（进程）来说，所有进程是交叉执行的。（外部并发性）,2.1 进程的基本概念(4),程序并发执行时的特征,1）间断性:,程序在并发执行时，由于它们共享系统资源，以及为完成同一任务而相互合作，致使这些并发执行的程序之间形成了相互制约的关系。（互斥关系、同步关系）,相互制约导致并发执行的程序具有“执行暂停执行”这种间断性活动规律。,2）失去封闭性：,程序在并发执行时，由于多个程序共享系统资源，因而这些资源的状态将由多个程序来改变，致使程序的运行已失去了封闭性。,某程序的执行时，会受到其他程序的影响。,2.1 进程的基本概念(5),程序并发执行时的特征,3）不可再现性与时间有关的错误,程序在并发执行时，由于失去了封闭性，也将导致其再失去可再现性。例如：有两个循环程序A和B，它们共享一个变量N。,L1：N = N+1； goto L1；,L2：print (N )； N = 0； goto L2；,程序A,程序B,程序A和B并发执行时，可能出现下述三种情况（设某时刻N的值为10）：（1）N=N+1在print(N)和N=0之前，此时得到的N值分别为11，11，0。（2）N=N+1在print(N)和N=0之后，此时得到的N值分别为10，0，1。（3）N=N+1在print(N)和N=0之间，此时得到的N值分别为10，11，0。,计算结果已与并发程序的执行速度有关，从而使程序执行失去了可再现性。,2.1 进程的基本概念(6),进程的特征与状态,1进程的定义和特征,进程是程序在一个数据集上的运行过程，是系统进行资源分配和调度的一个独立单位。 (传统OS的定义),定义,1）结构特征：,进程的特征,程序段、相关的数据段、PCB三部分构成了进程实体。,通常的程序是不能并发执行的，为使程序（含数据）能独立运行，应为之配置一进程控制块（即PCB）。,在许多情况下所说的进程，实际上是指进程实体。如，所谓创建进程，,2）动态性：,进程的实质是进程实体的一次执行过程，故动态性是进程的最基本特征。,3）并发性：,这是指多个进程实体同存于内存中，且能在一段时间内同时运行。,2.1 进程的基本概念(7),进程的特征与状态,4）独立性 ：,进程的特征：,在传统的OS中，独立性是指进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。,5）异步性 ：,是指进程按各自独立的、不可预知的速度向前推进，或说进程实体按异步方式运行。,2.1 进程的基本概念(8),进程的特征与状态,进程的三种基本状态：,1）就绪（Ready）状态：,当进程已分配到除CPU以外的所有资源后，只要再获得CPU，便可立即执行，进程这时的状态称为就绪状态。,系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称为就绪队列。,2）执行（Running）状态:,进程已获得CPU，其程序正在执行。,3）阻塞（Blocked）状态:,正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，亦即进程的执行受到阻塞，把这种暂停状态称为阻塞状态（或等待状态）。,使进程阻塞的典型事件：请求I/O，申请缓冲空间等等。,2.1 进程的基本概念(9),进程的特征与状态,进程的三种基本状态的转换：,进程调度：就绪态执行态时间片完：执行态就绪态 请求I/O：执行态阻塞态 I/O完成：阻塞态就绪态,引起进程状态转换的典型事件：,2.1 进程的基本概念(10),进程的特征与状态,挂起状态：,有些系统除了进程的三种基本状态外，还有挂起状态。,1）引入挂起状态的原因：,（1）终端用户的请求：,（2）父进程请求：,（3）负荷调节的需要 ：,（4）操作系统的需要 ：,当终端用户在自己的程序运行期间发现有可疑问题时，希望暂停执行。,希望考察和修改子进程，或协调各子进程间的活动时,实时系统中工作负荷较重时，系统可把一些不重要的进程挂起。,操作系统有时希望挂起某些进程，以便检查运行中的资源使用情况或进行记账。,2.1 进程的基本概念(11),进程的特征与状态,挂起状态：,2）进程状态的转换,活动就绪静止就绪,活动阻塞静止阻塞,静止就绪活动就绪,静止阻塞活动阻塞,挂起原语Suspend,激活原语Active,2.1 进程的基本概念(12),进程控制块（PCB）,为了描述和控制进程的运行，系统为每个进程定义了一个数据结构进程控制块。进程控制块是进程实体的一部分，是操作系统中最重要的记录型数据结构。,1. PCB作用：,使一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发进程进行控制和管理的。,例如：进程调度；现场保护和恢复；进程同步和通信。,PCB是进程存在的唯一标志,2.1 进程的基本概念(13),进程控制块（PCB）,2进程控制块中的信息,PCB中记录了操作系统所需的、用于描述进程当前情况以及控制进程运行的全部信息。具体包括下述四方面的信息：,1）进程标识符：,内部标识符(进程号)；外部标识符(名)；父进程标识及子进程标识；用户标识,2）处理机状态：,处理机状态信息主要由处理机的各种寄存器中的内容组成的。寄存器包括：通用寄存器、指令计数器、程序状态字（PSW）寄存器、用户栈指针。(保护、恢复现场),当处理机被中断时，这些信息都必须保存到PCB中，以便该进程重新执行时，能从断点继续执行。,2.1 进程的基本概念(14),进程控制块（PCB）,2进程控制块中的信息,3）进程调度信息：,在PCB中还存放一些与进程调度和进程对换有关的信息。包括：,进程状态作为调度和对换时的依据。 进程优先级由于描述进程使用处理机的优先级别的一个整数，优先级高的进程优先获得处理机。 进程调度所需的其它信息它们与所采用的进程调度算法有关。 事件即阻塞原因。,2.1 进程的基本概念(15),进程控制块（PCB）,2进程控制块中的信息,4）进程控制信息：,程序和数据的地址指程序和数据所在的内存或外存首地址； 进程同步和通信机制如信号量、消息队列指针等，它们可能全部或部分地存放在PCB中； 资源清单是一张列出了除CPU外的、进程所需的全部资源及已经分配到该进程的资源的清单； 链接指针它给出本进程（PCB）所在队列中下一个进程的PCB的首址。,2.1 进程的基本概念(16),进程控制块（PCB）,3进程控制块的组织方式(1),常用的组织方式有两种：链接方式和索引方式。,1）链接方式,把具有同一状态的PCB，用其中的链接字链接成一个队列。形成：就绪队列、阻塞队列、空白队列等,2.1 进程的基本概念(17),进程控制块（PCB）,3进程控制块的组织方式(2),2）索引方式:,系统根据所有进程的状态建立几张索引表。如， 就绪索引表 阻塞索引表等,索引表的首址记录在专用单元中；每个索引表的表目中，记录具有相应状态的某个PCB的首址。,2.2 进程控制(1),进程控制是进程管理中最基本的功能。 进程控制包括： 创建进程 终止进程 进程状态转换,进程控制是由OS的内核完成的。,2.2 进程控制(2),2.2.1 进程的创建,1引起创建进程的事件,用户登录 作业调度 提供服务,当用户进程提出某种请求后，系统将专门创建一个进程来提供用户所需的服务。如，文件打印。,上述三种情况，都是由系统内核为它创建一个新进程。,应用请求：,是基于应用进程的需求，由应用进程自己创建一个新进程，以便新进程以并发运行方式完成特定任务。,2.2 进程控制(3),2.2.1 进程的创建(2),2进程的创建,调用进程创建原语Create（），按下述步骤创建一个进程：,（1）申请空白PCB；（2）为新进程分配资源。主要是内存空间。 （3）初始化PCB。包括：,初始化标识信息 初始化处理机状态信息：,程序计数器，堆栈指针等,进程状态就绪或静止就绪、优先级等。,初始化处理机控制信息：,（4）将新进程插入就绪队列。,2.2 进程控制(4),2.2.2 进程的终止,1引起进程终止的事件,正常结束 异常结束,外界干预,常见的异常结束事件有：,越界错误 保护错试图访问不允许访问的资源或文件，或者以不适当方式访问 非法指令 特权指令错用户程序试图执行只允许OS执行的指令运行超时 等待超时算术运算错被0除 I/O故障,操作员或操作系统干预（如发生死锁） 父进程请求 父进程终止,2.2 进程控制(5),2.2.2 进程的终止,2进程的终止过程,OS调用终止原语，按下述过程终止进程：,（1）根据被终止进程的标识，从PCB集合中找除该进程的PCB，读出该进程状态。 （2）若被终止进程正处于执行状态，应立即终止其执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。若该进程还有子孙进程，应将其所有子孙进程终止，以防止它们成为不可控进程。（3）将被终止进程的所有资源，或者归还给其父进程，或者归还给系统。 （4）将被终止进程（它的PCB）从所在队列中移出，等待其他进程来搜索信息。,2.2 进程控制(6),2.2.2进程的阻塞和唤醒,1引起进程阻塞和唤醒的事件,请求系统服务,无新工作可做,当执行进程请求OS服务时，由于某种原因，OS并不立即满足该进程的请求时，该进程只能转变为阻塞状态来等待。如，进程请求打印机，,系统往往设置一些具有特定功能的系统进程，每当这种进程完成任务后，便把自己阻塞起来以等待新任务到来。如，系统中发送数据的进程，,启动某种操作,当进程启动某种操作后，如果该进程必须在该操作完成后才能继续执行，则必须先使该进程阻塞，以等待操作完成。如，启动了某I/O设备，,新数据尚未到达,对于相互合作的进程，如果其中一个进程需要获得另一个（合作）进程提供的数据才能运行以对数据进行处理，则只要其所需数据尚未到达，该进程只有阻塞（等待）。如，,2.2 进程控制(7),2.2.2进程的阻塞和唤醒,2进程阻塞过程,调用阻塞原语block把自己阻塞。（主动行为）,阻塞（block）过程：,立即停止执行；把PCB中进程状态由“执行”改为“阻塞”； 将PCB插入具有相同事件的阻塞队列； 转进程调度程序，将处理机分配给某个就绪进程，并进行进程切换保留被阻塞进程的处理机状态（在PCB中），再按新进程的PCB中处理机状态设置CPU的环境。,2.2 进程控制(8),2.2.2进程的阻塞和唤醒,3进程唤醒过程,调用唤醒原语wakeup( )，将等待事件的进程唤醒。,唤醒原语执行过程：,将被唤醒进程的PCB从阻塞队列移出； 将其PCB中进程状态由“阻塞”改为“就绪”； 将改PCB插入到就绪队列中。,block（）和wakeup（）是成对的。,2.2 进程控制(9),2.2.4 进程的挂起和激活,1进程的挂起,当出现了引起进程挂起的事件时(用户进程请求将自己挂起，或父进程请求将子进程挂起)，系统将用挂起原语suspend( )将指定进程或处于阻塞状态的进程挂起。,挂起原语的执行过程：,检查被挂起进程的状态：,若处于活动就绪或执行状态，则将其转为静止就绪；若处于活动阻塞,则将其转为静止阻塞。,把该进程的PCB复制到某指定内存区域,为方便用户或父进程考查该进程的运行状态。,若该进程正在执行，则转进程调度程序重新调度。,2.2 进程控制(10),2.2.4 进程的挂起和激活,2进程的激活,当发生激活进程的事件时(如父进程或用户请求激活指定进程，而内存中已有足够空间时)，系统利用激活原语active( )将指定进程激活。,激活过程是：,将进程从外存调入内存；,若是静止就绪，则改为活动就绪； 若是静止阻塞，则改为活动阻塞。,若采用的是抢占式调度策略，则应检查被激活就绪进程的优先级，若其优先级比先行执行进程高，则应将处理机分配给被激活进程。,检查该进程现行状态：,2.3 进程同步,由于进程的异步性，尤其是它们竞争临界资源时，可能会给系统造成混乱。进程同步的主要任务，是使并发执行的进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。,2.3 进程同步(2),2.3.1 进程同步的基本概念,1两种形式的制约关系,（1）间接制约关系,间接制约关系源于资源共享。如，共享打印机。,进程互斥,（2）直接制约关系,源于进程间的合作。如，,进程同步,2临界资源,在一段时间内只允许一个进程访问的资源，即仅当一个进程访问完并释放该资源后，才允许另一个进程访问的资源，称为临界资源或独占资源。,如，打印机、磁带机、共享变量、队列、,2.3 进程同步(3),2.3.1 进程同步的基本概念,【例】生产者-消费者问题著名的进程同步问题,共享变量：临界资源,循环缓冲区,生产者投放一个产品后，输入指针in加1：in = ( in + 1 ) % n （n是缓冲区个数，整型常量），in初值为0； 消费者每取出一个产品，输出指针out加1：out = ( out + 1 ) % n，out初值为0；,引入一个共享变量counter,初值为0。生产者投放一个产品，counter加1，counter = n时不能再投放产品 消费者每取一个产品，counter减1，counter = 0时不能再取出产品,前面交通观察站例子亦然。,rocess producer：while （condition） produce an item in nextp；while(counter=n) no-op；/no-op表示空操作bufferin = nextp；in = (in + 1)% n ；counter = counter + 1 ；,生产者进程算法如下：,process consumer：struct item nextc ；while （condition） while （counter = 0）no-op ；nextc = bufferout ；out = （out + 1）% n ；counter = counter 1 ；consume the item in nextc ；,消费者进程算法如下：,上面的生产者程序和消费者程序，在顺序执行时其结果也是正确的。但若并发执行时，可能会出现差错，问题在于这两个进程共享变量counter。生产者对它做加1操作，消费者对它做减1操作，这两个操作在机器语言实现时，常可用下面的形式描述：,生产者执行的操作： register1 = counter ； register1 = register1 + 1 ； counter = register1；,消费者执行的操作： register2 = counter ； register2 = register2 - 1 ； counter = register2；,假设counter当前的值为5，按下述顺序执行：,register1 = counter; (5) register1 = register1 + 1; (6)register2 = counter; (5)register2 = register2 1; (4)counter = register1; (6)counter = register2; (4),最终counter的值为4，正确的counter值应是5，出现了差错。,学生可以考虑出现6的情况。,解决此问题的关键，是应将变量counter作为临界资源处理，亦即让生产者进程和消费者进程互斥地访问变量counter。,2.3 进程同步(4),2.3.1 进程同步的基本概念,3临界区（critical section）,每个进程中访问临界资源的那段代码称为临界区。,不论是硬件临界资源，还是软件临界资源，多个进程必须互斥地对它们访问。,显然，若能保证诸进程互斥地进入自己的临界区，便可实现诸进程对临界区的互斥访问。为此，每个进程在进入临界区之前，应先对欲访问的临界资源进行检查，看是否正被访问，如果此刻该资源未被访问，便可进入临界区对该临界资源进行访问，并设置它正被访问的标志；如果此刻它正被访问，则本进程不能进入临界区。,因此必须在临界区前增加一段用于上述检查的代码，把这段代码称为进入区（entry section）；相应地，在临界区后面也要加上一段称为退出区（exit section）的代码，用于将临界区正被访问的标志恢复为未被访问的标志。,定义：,进程互斥不允许两个或两个以上进程同时访问同一个临界资源。进程互斥不允许两个或两个以上进程同时进入相关临界区。,2.3 进程同步(5),2.3.1 进程同步的基本概念,4同步机制应遵循的原则,为了实现各进程互斥地进入自己的临界区，一般是在系统中设置专门的同步机制来协调各进程间的运行。,所有同步机制都应遵循如下四条准则：,空闲让进,忙则等待,当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以便有效地利用临界资源。,有限等待,当已有进程进入临界区时，表明临界资源正在被访问，因而其他试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。,让权等待,对要求访问临界资源的进程，应保证在有限的时间内能进入自己的临界区，以免陷入“死锁”状态。不死等。,当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”。不忙碌等待。,2.3 进程同步(6),2.3.2 信号量机制,信号量（Semaphores）机制是一种卓有成效的进程同步工具。信号量机制已被广泛应用于单处理机和多处理机系统以及计算机网络中。,信号量机制的发展：,整型信号量,记录型信号量,AND型信号量,信号量集,“忙等”，未遵循“让权等待”准则。,后边重点介绍。,学生在深刻理解记录型信号量后自学。,2.3 进程同步(7),2.3.2 信号量机制,记录型信号量,需要一个用于代表临界资源数目的整型变量value；还要一个在该资源上阻塞的队列（链表）指针L)。故信号量应采用记录型（C语言中为结构型）的结构：,struct semaphore int value ； struct semphore *L ； ；,记录型信号量的结构定义,信号量除初始化外，只能通过两个原子操作(称为原语)wait（S）和signal（S）来访问。它们以前被称为P、V操作。下页介绍wait和signal操作。,2.3 进程同步(8),2.3.2 信号量机制,wait和signal操作可用C/C+语言描述如下：,void wait（S）struct semaphore S; S.value = S.value 1 ; if (S.value 0 ) block (S.L ) ; /* 让权等待 */ ,void signal ( S )struct semaphore S ; S.value = S.value + 1 ;if ( S.value = 0 ) wakeup ( S.L ) ; /*唤醒第一个等待的进程 */ ,P(S),V(S),S.value的初值表示系统中某类资源的数目。资源信号量。,2.3 进程同步(9),2.3.2 信号量机制,wait和signal操作的物理意义：,对信号量S的每次wait操作，意味着进程请求一个该类临界资源，因此描述为S.value=S.value-1；当S.value0时，表示该类资源已分配完，因此进程应调用block原语进行自我阻塞，放弃处理机，并插入到信号量链表S.L(阻塞队列)中。可见该机制遵循了“让权等待”准则。类似地，可以解释signal操作,S.value的初值表示系统中某类资源的数目。资源信号量。 S.value的初值为1，表示只允许一个进程访问，此时信号量转化为互斥信号量。,2.3 进程同步(10),2.3.3 信号量的应用,1利用信号量实现进程互斥,方法要点：,为临界资源设置一个互斥信号量mutex，其初值为1； 各进程访问该资源的临界区置于wait（mutex）和signal（mutex）之间即可。,wait（mutex）进入区signal（mutex）退出区,请看下页的例子,利用信号量实现进程互斥的简单例子,某交通路口设置了一个自动计数系统，该系统由“观察者”进程和“报告者”进程组成。观察者进程能识别卡车，并对通过的卡车计数；报告者进程定时（可设为每隔1小时，准点时）将观察者的计数值打印输出，每次打印后把计数值清“0”。两个进程的并发执行可完成对每小时中卡车流量的统计。这两个进程的功能如下：,process observer while (condition) observe a lorry; wait（S）; count = count + 1; signal（S）; ,临界区,process reporter wait（S）; print（count）; count = 0； signal（S）; ,临界区,struct semaphore S ；int count = 0 ；S.value = 1 ；,【注意】wait（S）和signal（S）必须成对出现,利用信号量实现前趋关系,【例】利用信号量，按语句的前趋关系（见图2-6）,写出一个可并发执行的程序。,图中表示：进程P1中有语句S1；进程P2中有语句S2；语句S1执行后才能执行语句S2和语句S3；语句S2执行后才能执行语句S4和S5；语句S3、S4和S5执行后，才能执行语句S6。,P1执行完应通知P2、P3；P2得到通知后才开始执行；P2执行完应通知P4、P5；,struct semaphore a，b，c，d，e，f，g ；a.value=b.value=c.value=0;d.value=e.value=g.value=0;,程序描述如下：,初始化,arbegin /*parbegin表示并发执行开始*/process P1： S1；signal（a）；signal（b）； process P2： wait（a）；S2；signal（c）；signal（d）； process P3： wait（b）；S3；signal（e）； process P4： wait（c）；S4；signal（f）； process P5： wait（d）；S5；signal（g）； process P6： wait（e）；wait（f）；wait（g）；S6； parend /*用parend表示并发执行结束 */,2.4 经典进程同步问题,生产者-消费者问题 读者-写者问题 哲学家进餐问题,在多道程序环境下，进程同步问题十分重要，引起了不少学者对它进行研究，由此产生了一系列经典的进程同步问题，其中较有代表性的是：,通过对这些问题的研究和学习，可以帮助我们更好地理解进程同步概念及实现方法。,2.4 经典进程同步问题(2),2.4.1 生产者-消费者问题,前面已经对生产者-消费者问题做了一些描述，但是未考虑进程的互斥和同步问题，因而造成了共享变量counter的不确定性。 生产者-消费者问题是相互合作进程关系的一种抽象，例如，,先介绍最简单的P-C问题,生产者-消费者问题从特殊到一般(从易到难)可以分3种形式：,一个生产者、一个消费者、一个缓冲区的问题；一个生产者、一个消费者、n个缓冲区的问题； k个生产者、m个消费者、n个缓冲区的问题；,2.4 经典进程同步问题(3),最简单的生产者-消费者问题,一个生产者、一个消费者、一个缓冲区的问题如右图所示。,当缓冲区空时，生产者可将产品存入缓冲区；当缓冲区满时，生产者必须等待 (阻塞)，待消费者取走产品后将其唤醒后，才能将产品存入。当缓冲区满时，消费者可从缓冲区取出产品进行消费；当缓冲区空时，消费者必须等待(阻塞)，待生产者存入产品后将其唤醒后，才能再从缓冲区取产品。,用信号量机制解决进程同步问题的基本方法：,1为生产者设置1个私有信号量empty，其初值为1，表示有1个空缓冲区；为消费者设置1个私有信号量full，其初值为0，表示开始时没有空缓冲区；（由物理意义确定）2生产者将产品存入缓冲区之前，应先测试缓冲区是否空：执行wait(empty)操作；离开临界区(存入产品)后，应通知(可能会唤醒)消费者：执行signal(full)操作；3消费者从缓冲区取产品之前，应先测试缓冲区是否满：执行wait(full)操作；离开临界区(取走产品)后，应通知(可能会唤醒)生产者：执行signal(empty)操作,2.4 经典进程同步问题(4),最简单的生产者-消费者问题,一个生产者、一个消费者、一个缓冲区的生产者-消费者问题的算法描述如下所示：,semaphore empty,full;empty=1;full=0;parbeginprocess Producer: . produce an item in nextp; wait(empty);/测试 buffer=nextp; signal(full);/通知消费者,rocess Consumer: wait(full); /测试 nextc=buffer; signal(empty); /通知 consume the item in nextc;parend,2.4 经典进程同步问题(5),一个生产者、一个消费者、n个缓冲区的P-C问题,信号量empty=n(初值),信号量full=0(初值),资源信号量,semaphore empty,full;empty=n;full=0;int in=0,out=0; /下标parbeginprocess Producer: . produce an item in nextp; wait(empty);/测试 bufferin=nextp; in=(in+1)%n; signal(full);/通知消费者,资源信号量,rocess Consumer: wait(full); /测试 nextc=bufferout; out=(out+1)%n; signal(empty); /通知 consume the item in nextc;parend,与前不同,本题中in和out不是共享变量，无需互斥访问。,2.4 经典进程同步问题(6),2.4.1 生产者-消费者问题,下面介绍生产者-消费者问题一般形式：k个生产者、m个消费者、n个缓冲区的问题。一般形式的生产者-消费者问题的图示如下：,2.4.1 生产者-消费者问题,用互斥信号量mutex对缓冲区(共享变量in和out)的互斥使用，互斥信号量mutex初值为1； 用资源信号量empty表示多缓冲中空缓冲区的数目，empty的初值为n；用资源信号量full表示多缓冲中满缓冲区的数目，full的初值为0；只要多缓冲未满，生产者便可将消息送入缓冲区；只要多缓冲不空，消费者便可从缓冲区取走一个消息。生产者用共享变量in作为下标访问缓冲区，mutex为其互斥信号量；消费者用共享变量out作为下标访问缓冲区，其互斥信号量也用mutex。,arbegin /并发执行开始 process produceri (i=1,2,k） item nextp ； while （condition） produce an item in nextp； wait（empty）； wait（mutex）； bufferin = nextp ； in = （in + 1）% n ； signal（mutex）； signal（full）； ,生产者-消费者问题可描述如下：,rocess consumerj (j=1,2,m） item nextc ； while （condition） wait（full）； wait（mutex）； nextc = bufferout ； out = （out + 1）% n ； signal（mutex）； signal（empty）； consume the item in nextc ； parend /并发执行结束,临界区,在每个进程中，实现互斥的wait（mutex）和signal（mutex）必须成对出现；对资源信号量empty和full的wait和signal操作也要成对地出现，但它们处于不同的进程中。 在每个进程中的多个wait操作顺序不能颠倒，应先执行对资源信号量（也称私有信号量）的wait操作，然后执行对互斥信号量（公有信号量）的wait操作，否则可能引起进程死锁。(Why?),semaphore mutex,empty,full ;item buffern ;int in = 0，out = 0 ；mutex.value = 1;empty.value = n，full.value = 0;,初始化,临界区,2.4 经典进程同步问题(7),2.4.2 哲学家进餐问题,Dijkstra提出并解决的哲学家就餐问题是经典的进程同步问题。哲学家就餐问题描述如下：,有5个哲学家共用一张圆桌，分别坐在周围的5张椅子上，在圆桌上有5个碗和5只筷子，他们的生活方式是交替地进行思考和进餐。平时，每个哲学家进行思考，饥饿时便试图拿起其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐完毕，放下筷子继续思考。图2-7是其示意图。,2.4 经典进程同步问题(8),利用记录型信号量解决哲学家进餐问题,桌子上的筷子f0，f1，f4是临界资源，应互斥使用，可用一个信号量表示一只筷子，5只筷子的5个信号量构成信号量数组，所有信号量的初值均为1。,struct semaphore chopstick5 ；chopstick0.value=chopstick1.value=1;chopstick2.value=chopstick3.value=1 ;chopstick4.value=1 ;,初始化,每个哲学家算法流程为,(1) 拿起左、右筷子；(2) 吃面条；(3) 放下左、右筷子；(4) 思考问题；(5) 返回(1)。,2.4 经典进程同步问题(9),第i个哲学家的活动可描述如下：,arbeginprocess Pi（i = 0，1，2，3，4） while （logical） wait（chopsticki）； /拿起左边筷子 wait（chopstick（i + 1）%5）； /拿起右边筷子 eating ； signal（chopsticki）； /放下左边筷子 signal（chopstick（i+1）%5）；/放下右边筷子 thinking ； parend,此算法虽然能保证相邻哲学家对筷子的访问互斥，但可能引起死锁。(Why?),2.4 经典进程同步问题(10),对上述哲学家算法的死锁问题，可采取下面几种解决方法之一：,（1）至多允许4个哲学家同时取左边的筷子，这样能至少保证一个哲学家能就餐，并在用毕后释放他用过的两只筷子，从而使更多的哲学家能够进餐。（请学生考虑算法的描述）（2）仅当哲学家左右两只筷子均可用时，才允许他拿起筷子进餐。（用AND信号量机制）（3）规定奇数号哲学家先拿左边筷子，然后再拿右边筷子；而偶数号哲学家先拿右边筷子，然后再拿左边筷子。（4）规定每个哲学家先拿序号小的筷子按序号分配。请学生考虑算法的描述。,2.4 经典进程同步问题(11),2.4.3 读者-写者问题,一个数据文件或记录，可被多个进程共享，我们把只要求读该文件的进程称为“读者进程”，其他进程称为“写者进程”。,允许多个读者进程同时读一个共享文件，因为读操作不会使数据文件混乱；不允许两个或两个以上写者进程同时访问共享文件，因为这种访问将会引起混乱；不允许一个写者进程和其他读者进程同时访问共享文件，因为这种访问将会引起混乱。,所谓“读者-写者问题”是指保证一个Writer进程必须与其它进程互斥地访问共享对象的同步问题。,2.4 经典进程同步问题(12),利用记录型信号量解决读者-写者问题,【算法分析】, 为实现Reader进程和Writer进程间的互斥，设置一个互斥信号量Wmutex，其初值为1； 设置一个整型变量Rcounter，记录正在读的读者进程数。其初值为0； 由于只要有一个Reader进程在读，便不允许Writer进程去写，因此第一个读者进程需要执行wait（Wmutex）操作，即当Rcounter =0时，Reader进程才需要执行wait（Wmutex）操作。若wait（Wmutex）操作成功（表示此时无Writer进程在写），Reader进程便可去读，同时做Rcounter+1的操作。若wait（Wmutex）操作成功（表示此时无Writer进程在写），Reader进程便可去读，同时做Rcounter+1的操作。, 同理，最后一个Reader进程离开时(Rcounter-1后变为0)应执行signal（mutex）操作，以便让Writer进程写。 Rcounter是被多个Reader进程访问的临界资源，为了对它互斥访问，应为它设置一个互斥信号量Rmutex。,2.4 经典进程同步问题(13),根据前面分析，读者-写者问题可描述如下：,semaphore Wmutex，Rmutex;int Rcounter = 0;Wmutex.value=Rmutex.value=1; parbeginprocess Readeri (i = 1，2，)wait(Rmutex);if(Rcounter=0) wait(Wmutex);Rcounter = Rcounter + 1;signal(Rmutex);Reading;wait(Rmutex);Rcounter = Rcounter 1;if(Rcounter=0)signal(Wmutex);signal(Rmutex);,process Writerj (j=1，2，) wait(Wmutex); Writing; signal(Wmutex);parend,【分析】当第一个读者在读文件时，后续读者也可进入临界区读该文件，后续写者不能写(在Wmutex上阻塞)；待所有读者退出时，由最后退出的读者唤醒一个写者。当有一个写者在写时，后续写者不能写，在Wmutex上阻塞；后续读者不能读，其中第一个读者在Wmutex上阻塞，其余读者在Rmutex上阻塞。该写者退出时，唤醒一个写者或读者。,读者优先,2.4 经典进程同步问题(14),上述算法实际上是“优先读者”算法，当有读者正在读，且后续读者源源不断到来时，写者将长期得不到服务。写者“饿死”。 为此，可以考虑“优先写者”的算法当有写者要写时，待目前正在读的读者读完后，立即让写者去写（即一旦有写者到达，后续的读者都必须等待，而无论是否有读者在读文件）。请学生思考，写出该算法的描述。,可以增加一个互斥信号量W，用于在写进程到达时封锁后续的读者进程:读者进程进入时访问Rcouter时,增加执行wait(W)和signal(W)；写者进入临界区时，增加执行wait(W)和signal(W)。,2.4 经典进程同步问题(15),复习思考题,1若一只盘子一次只能放一个水果，A只往盘中放苹果，B只往盘中放梨子，C只从盘中取苹果，D只从盘中取梨子。试用P、V操作写出同步算法。 2有三个进程PA、PB、PC共享两个缓冲器B1和B2。缓冲器B1中可存放n件产品，缓冲