操作系统电子教案

操作系统电子教案 第二章进程管理第二章进程管理2.1进程的基本概念2.2进程控制2.3进程同步2.4经典进程的同步问题2.5管程机制2.6进程通信2.7线程第二章进程管理2.1进程的基本概念2.1.1程序的顺序执行及其特征1.程序的顺序执行仅当前一操作(程序段)执行完后，才能执行后继操作。 例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。 S1:a=x+y;S2:b=a-5;S3:c=b+1;第二章进程管理I1C1P1I2C2P2S1S2S3图2-1程序的顺序执行(a)程序的顺序执行(b)三条语句的顺序执行第二章进程管理2.程序顺序执行时的特征 (1)顺序性 (2)封闭性 (3)可再现性第二章进程管理2.1.2前趋图前趋图(Precedence Graph)是一个有向无循环图，记为DAG(Directed AcyclicGraph)，用于描述进程之间执行的前后关系。 图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序(Partial Order)或前趋关系(Precedence Relation)“”。 =(P i,P j)|P imust pletebefore P j maystart,如果(P i,P j),可写成P iP j，称P i是P j的直接前趋，而称Pj是P i的直接后继。 在前趋图中，把没有前趋的结点称为初始结点(Initial Node)，把没有后继的结点称为终止结点(Final Node)。 第二章进程管理每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。 I iC iP i和S1S2S3P2P5S1图2-2前趋图P1P3P8P9P4P6P7S2S3(a)具有九个结点的前趋图(b)具有循环的前趋图第二章进程管理对于图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程序的并发执行及其特征1.程序的并发执行I1I2I3I4图2-3并发执行时的前趋图P1P2P3P4C1C2C3C4第二章进程管理在该例中存在下述前趋关系I iC i，I iI i+1,C iP i,C iC i+1，P iP i+1而I i+1和C i及P i-1是重迭的，亦即在P i-1和C i以及I i+1之间，可以并发执行。 对于具有下述四条语句的程序段S1:a=x+2S2:b=y+4S3:c=a+bS4:d=c+b第二章进程管理S1S S图2-4四条语句的前趋关系S2S3S4第二章进程管理2.程序并发执行时的特征1)间断性2)失去封闭性3)不可再现性例如，有两个循环程序A和B，它们共享一个变量N。 程序A每执行一次时，都要做N=N+1操作；程序B每执行一次时，都要执行Print(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.进程的特征和定义1)结构特征2)动态性3)并发性4)独立性5)异步性第二章进程管理进程与程序的区别 (1)程序是指令的有序集合，其本身没有任何运行的含义，是一个静态的概念。 而进程是程序在处理机上的一次执行过程，它是一个动态的概念。 程序是指令的有序集合，其本身没有任何运行的含义，是一个静态的概念。 而进程是程序在处理机上的一次执行过程，它是一个动态的概念。 (2)程序可以作为一种软件资料长期存在，而进程是有一定生命期的。 程序是永久的，进程是暂时的。 程序可以作为一种软件资料长期存在，而进程是有一定生命期的。 程序是永久的，进程是暂时的。 (3)进程更能真实地描述并发，而程序不能 (4)进程是由程序和数据两部分组成的 (5)进程具有创建其他进程的功能，而程序没有 (6)同一程序同时运行于若干个数据集合上，它将属于若干个不同的进程。 也就是说同一程序可以对应多个进程同一程序同时运行于若干个数据集合上，它将属于若干个不同的进程。 也就是说同一程序可以对应多个进程第二章进程管理思考？为什么引入进程的概念？第二章进程管理2.进程的三种基本状态 (1)就绪(Ready)状态(2执行状态() (3)阻塞状态第二章进程管理就绪时间片完进程调度I/O完成图2-5进程的三种基本状态及其转换阻塞执行I/O请求第二章进程管理3.挂起状态1)引入挂起状态的原因 (1)终端用户的请求。 (2)父进程请求。 (3)负荷调节的需要。 (4)操作系统的需要。 第二章进程管理2)进程状态的转换 (1)活动就绪静止就绪。 (2)活动阻塞静止阻塞。 (3)静止就绪活动就绪。 (4)静止阻塞活动阻塞。 第二章进程管理活动就绪静止就绪执行挂起激活释放挂起请求I/O图2-6具有挂起状态的进程状态图释放活动阻塞静止阻塞挂起激活释放第二章进程管理思考？1如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？2.有没有这样的状态转换，为什么？等待有没有这样的状态转换，为什么？等待运行；就绪等待第二章进程管理2.1.5进程控制块为了描述一个进程和其它进程以及系统资源的关系，为了刻画一个进程在各个不同时期所处的状态，人们采用了一个与进程相联系的数据块，称为进程控制块（为了描述一个进程和其它进程以及系统资源的关系，为了刻画一个进程在各个不同时期所处的状态，人们采用了一个与进程相联系的数据块，称为进程控制块（PCB）。 系统利用）。 系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志1.进程控制块的作用进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。 或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。 程存在的唯一标志进程与PCB是一一对应的第二章进程管理2.进程控制块中的信息1)进程标识符进程标识符用于惟一地标识一个进程。 一个进程通常有两种标识符(1。 ，一()内部标识符在所有的操作系统中都为每个进程赋予一个惟一的数字标识符，它通常是一个进程的序号。 设置内部标识符主要是为了方便系统使用。 (2)外部标识符。 它由创建者提供，通常是由字母、数字组成，往往是由用户(进程)在访问该进程时使用。 为了描述进程的家族关系，还应设置父进程标识及子进程标识。 此外，还可设置用户标识，以指示拥有该进程的用户。 第二章进程管理2)处理机状态处理机状态信息主要是由处理机的各种寄存器中的内容组成的。 通用寄存器，又称为用户可视寄存器，它们是用户程序可以访问的，用于暂存信息，在大多数处理机中，有832个通用寄存器，在RISC结构的计算机中可超过100个；指令计数器，其中存放了要访问的下一条指令的地址；程序状态字PSW，其中含有状态信息，如条件码、执行方式、中断屏蔽标志等；用户栈指针，指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。 栈指针指向该栈的栈顶。 第二章进程管理3)进程调度信息在PCB中还存放一些与进程调度和进程对换有关的信息，包括进程状态，指明进程的当前状态，作为进程调度和对换时的依据；进程优先级，用于描述进程使用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机；进程调度所需的其它信息，它们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等；事件，是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。 第二章进程管理4)进程控制信息进程控制信息包括程序和数据的地址，是指进程的程序和数据所在的内存或外存地(首)址，以便再调度到该进程执行时，能从PCB中找到其程序和数据；进程同步和通信机制，指实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等，它们可能全部或部分地放在PCB中；资源清单，是一张列出了除CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单；链接指针，它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址。 第二章进程管理3.进程控制块的组织方式1)链接方式PCB14PCB2PCB3PCB4308执行指针就绪队列指针图2-7PCB链接队列示意图PCB4PCB5PCB6PCB7PCB8PCB987901绪阻塞队列指针空闲队列指针第二章进程管理2)索引方式执行指针就绪索引表PCB1PCB2PCB3就绪表指针图2-8按索引方式组织PCB PCB4PCB5PCB6PCB7阻塞索引表就绪表指针阻塞表指针第二章进程管理思考？OS如何进行进程切换？何时会发生进程切换？第二章进程管理2.2进程控制2.2.1进程的创建1.进程图(Process Graph)B CA进程控制就是对系统中的所有进程实施管理，进程控制一般有进程控制就是对系统中的所有进程实施管理，进程控制一般有原语来实现。 所谓原语是一种特殊的系统功能调用，它可以完成一个特定的功能，其特点图2-9进程树D EF GHI JK LM它可以完成个特定的功能，其特点是原语执行时不可被中断。 常用原语。 常用原语创建原语终止原语阻塞原语、唤醒原语创建原语终止原语阻塞原语、唤醒原语第二章进程管理2.引起创建进程的事件 (1)用户登录。 (2)作业调度。 (3)提供服务。 (4)应用请求。 第二章进程管理3.进程的创建(Creation ofProgress) (1)申请空白PCB。 (2)为新进程分配资源。 (3)初始化进程控制块。 (4)将新进程插入就绪队列，如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列。 第二章进程管理2.2.2进程的终止1.引起进程终止(Termination ofProcess)的事件1)正常结束一在任何计算机系统中，都应有个用于表示进程已经运行完成的指示。 例如，在批处理系统中，通常在程序的最后安排一条Holt指令或终止的系统调用。 当程序运行到Holt指令时，将产生一个中断，去通知OS本进程已经完成。 在分时系统中，用户可利用Logs off去表示进程运行完毕，此时同样可产生一个中断，去通知OS进程已运行完毕。 第二章进程管理2)异常结束在进程运行期间，由于出现某些错误和故障而迫使进程终止。 这类异常事件很多，常见的有越界错误。 这是指程序所访问的存储区，已越出该进程的区域；保护错。 进程试图去访问一个不允许访问的资源或文件，或者以不适当的方式进行访问，例如，进程试图去写一个只读文件；非法指令。 程序试图去执行一条不存在的指令。 出现该错误的原因，可能是程序错误地转移到数据区，把数据当成了指令；特权指令错。 用户进程试图去执行一条只允许OS执行的指令；运行超时。 进程的执行时间超过了指定的最大值；等待超时。 进程等待某事件的时间，超过了规定的最大值；算术运算错。 进程试图去执行一个被禁止的运算，例如，被0除；I/O故障。 这是指在I/O过程中发生了错误等。 第二章进程管理3)外界干预外界干预并非指在本进程运行中出现了异常事件，而是指进程应外界的请求而终止运行。 这些干预有操作员或操作系统干预。 由于某种原因，例如，发生了死锁，由操作员或操作系统终止该进程；父进程请求。 由于父进程具有终止自己的任何子孙进程的权利，因而当父进程提出请求时，系统将终止该进程；父进程终止。 当父进程终止时，OS也将他的所有子孙进程终止。 第二章进程管理2.进程的终止过程 (1)根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。 (2)若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。 (3)若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程。 (4)将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。 (5)将被终止进程(它的PCB)从所在队列(或链表)中移出，等待其他程序来搜集信息。 第二章进程管理2.2.3进程的阻塞与唤醒1.引起进程阻塞和唤醒的事件1)请求系统服务2)启动某种操作3)新数据尚未到达4)无新工作可做第二章进程管理2.进程阻塞过程正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用阻塞原语block把自己阻塞。 可见，进程的阻塞是进程自身的一种主动行为。 进入block过程后，由于此时该进程还处于执行状态，所以应先立即停止执行，把进程控制块中的现行状态由“执行”改为阻塞，并将PCB插入阻塞队列。 如果系统中设置了因不同事件而阻塞的多个阻塞队列，则应将本进程插入到具有相同事件的阻塞(等待)队列。 最后，转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换，亦即，保留被阻塞进程的处理机状态(在PCB中)，再按新进程的PCB中的处理机状态设置CPU的环境。 第二章进程管理3.进程唤醒过程当被阻塞进程所期待的事件出现时，如I/O完成或其所期待的数据已经到达，则由有关进程(比如，用完并释放了该I/O设备的进程)调用唤醒原语wakeup()，将等待该事件的进程唤醒。 唤醒原语执行的过程是首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪，然后再将该PCB插入到就绪队列中。 第二章进程管理2.2.4进程的挂起与激活1.进程的挂起当出现了引起进程挂起的事件时，比如，用户进程请求将自己挂起，或父进程请求将自己的某个子进程挂起，系统将利用挂起原语suspend()将指定进程或处于阻塞状态的进程挂起。 挂起原语的执行过程是首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。 为了方便用户或父进程考查该进程的运行情况而把该进程的PCB复制到某指定的内存区域。 最后，若被挂起的进程正在执行，则转向调度程序重新调度。 第二章进程管理2.进程的激活过程当发生激活进程的事件时，例如，父进程或用户进程请求激活指定进程，若该进程驻留在外存而内存中已有足够的空间时，则可将在外存上处于静止就绪状态的进程换入内存。 这时，系统将利用激活原语active()将指定进程激活。 激活原语先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞便将之改为活动阻塞。 假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重新调度，即由调度程序将被激活进程与当前进程进行优先级的比较，如果被激活进程的优先级更低，就不必重新调度；否则，立即剥夺当前进程的运行，把处理机分配给刚被激活的进程。 第二章进程管理思考？为什么创建进程要用原语来实现？请设想一下进程在什么情况下会变为阻塞为什么创建进程要用原语来实现？请设想一下进程在什么情况下会变为阻塞？状态？阻塞进程在什么情况下会被唤醒？谁来唤醒它？阻塞进程在什么情况下会被唤醒？谁来唤醒它？第二章进程管理进程在活动中会相互制约所有进程都是相互独立的2.3进程同步进程以异步方式并发执行第二章进程管理同步同步是进程间共同完成一项任务时直接发生相互作用的关系第二章进程管理同步进程间具有合作关系在执行时间上必须按一定的顺序协调进行第二章进程管理互斥互斥是并发执行的多个进程由于竞争同一资源而产生的相互排斥的关系第二章进程管理互斥进程彼此在逻辑上是完全无关的互斥进程彼此在逻辑上是完全无关的它们的运行不具有时间次序的特征第二章进程管理临界资源和临界区信号量临界资源和临界区信号量P、V操作第二章进程管理临界资源一次仅允许一个进程使用的共享资源如打印机、内存单元、表格第二章进程管理临界区在每个进程中访问临界资源的那段程序?空闲让进?忙则等待?有限等待?让权等待第二章进程管理信号量?一般说来，信号量的值与相应资源的使用情况有关?信号量的值仅由P P、V V操作改变第二章进程管理P P、V V操作都是原语P申请一个单位资源V释放一个单位资源第二章进程管理P P操作P()若S0入等待队列P(s):若S=0，继续取，继续取s值减1第二章进程管理V V操作V()若S=0唤醒一等待V(s):若S0，继续取，继续取s值加1第二章进程管理用P P、V V原语实现互斥例打印机分配m初1互斥信号量mutex（初值为1）Pa为分配进程Pb为释放进程第二章进程管理Pa.P P（mutex）分配打印机Pb.P P（mutex）释放打印机分配打印机（读写分配表）V V（mutex）.释放打印机（读写分配表）V V（mutex）.第二章进程管理用P P、V V原语实现简单同步例供者和用者对单缓冲区的同步信号量S1缓冲区空否（初值为1）S2缓冲区满否（初值为0）第二章进程管理供者进程L1P P（S1）启动读卡机）启动读卡机用者进程L2P P（S2）从缓冲区取出信）从缓冲区取出信息收到输入结束中断收到输入结束中断V V（S2）goto L1息V V（S1）goto L2第二章进程管理信号量及P、V操作讨论对于两个并发进程，互斥信号量的值仅取 1、0和-1三个值?若1表示没有进程进入临界区?若0表示有一个进程进入临界区?若-1表示一个进程进入临界区，另一个进程等待进入。 第二章进程管理思考?对于N个并发进程，信号量的取值范围是什么，有什么含义。 第二章进程管理1)信号量的物理含义S0表示有S个资源可用S=0表示无资源可用S0则|S|表示S等待队列中的进程个数信号量及P、V操作讨论（续1）S0则|S|表示S等待队列中的进程个数P(S)表示申请一个资源V(S)表示释放一个资源。 信号量的初值应该大于等于0第二章进程管理2)P.V操作必须成对出现，有一个P操作就一定有一个V操作当为互斥操作时它们同处于同进程信号量及P、V操作讨论（续2）当为互斥操作时，它们同处于同一进程当为同步操作时，则不在同一进程中出现如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要。 一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前而两个V操作无关紧要第二章进程管理3）P、V操作的优缺点优点简单而且表达能力强（用P V操作可解信号量及P、V操作讨论（续3）简单，而且表达能力强（用P、V操作可解决任何同步互斥问题）缺点不够安全，P、V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂第二章进程管理合作进程的执行次序?若干个进程为了完成一个共同任务而并发执行，在这些进程中，有些进程之间有次序的要求，有些进程之间没有次序的要求，为了描述方便，可以用一个图来表示进程集合的执行次序。 如图第二章进程管理例如图，试用信号量实现这三个进程的同步。 设有两个信号量S B、S C，初值均为Pa PbPcP(S B);P(S C)V(S B);V(S C);第二章进程管理【思考题1】如图，试用信号量实现这三个进程的同步。 第二章进程管理解设有两个信号量S 1、S2，初值均为P1P2P3PS1()V(S1);V(S2);P(S2)第二章进程管理【思考题2】如图，试用信号量实现这6个进程的同步第二章进程管理解设有5个信号量S 2、S 3、S 4、S 5、S6，初值均为P1P2P3P(S2);P(S3)V(S2);P4P5P6P(S4);P(S5);P(S6);P(S5);P(S6);V(S2);V(S3)；V(S4);V(S6);V(S5)P(S5);P(S6);V(S5)；V(S6);第二章进程管理【思考题3】司机进程while (1)司机进程while (1)启动车辆售票员进程while (1)售票员进程while (1)关门用P.V操作解决司机与售票员的问题启动车辆正常驾驶到站停车正常驾驶到站停车关门售票开门售票开门第二章进程管理解?设有两个信号量S1，S2，初值均为0。 司机进程while (1)司机进程while (1)售票员进程while (1)售票员进程while (1)P(S1)启动车辆正常驾驶到站停车启动车辆正常驾驶到站停车V(S2)关门V(S1)售票P(S2)开门开门第二章进程管理共享缓冲区的进程的同步?设某计算进程和打印进程共用一个单缓冲区，进程负责不断地计算数据并送入缓冲区中，进程负责不断地从缓冲区中取出数据去打印。 第二章进程管理分析通过分析可知，、必须遵守以下同步规则?当进程把计算结果送入缓冲区时，IOP进程才能从缓冲区中取出结果去打印;?当IOP进程把缓冲区中的数据取出打印后，进程才能把下一个计算结果送入缓冲区第二章进程管理解?为此设有两个信号量Sa=0，Sb=1，Sa表示缓冲区中有无数据，Sb表示缓冲区中有无空位置。 ?两个进程的同步可以描述如下第二章进程管理【思考题】1.用P.V操作解决下图之同步问题提示分别考虑对缓冲区S和T的同步，再合并考虑get copyputs t第二章进程管理解?设置四个信号量Sin=1，Sout=0，Tin=1，Tout=0；get copyput while （1）P(Sin）;将数放入S;V(Sout);while （1）P(Sout）;P(Tin）;将数从S取出放入T;V(Tout);V(Sin);while （1）P(Tout）;将数从T取走;V(Tin);第二章进程管理总结进程互斥总结进程互斥在OS中，当某一进程正在访问cs时，就不允许其它进程来读写(访问)，否则就会发生后果无法估计的错误，进程之间的这种相互制约关系为进程互斥。 进程同步并发进程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通消息，称为进程同步。 第二章进程管理进程同步与互斥关系都反映了在异步环境下并发进程间的相互制约关系。 可归于同步范畴，但互斥是同步问题的一个特例，互斥解决临界区的使用，同步是并发进程在一些关键点上需互相等待互发消息。 第二章进程管理【思考题】?桌上有一空盘，最多允许存放一只水果。 爸爸可向盘中放一个苹果或放一个桔子，儿子专等吃盘中的桔子，女儿专等吃苹果。 试用P、V操作实现爸爸、儿子、女儿三个并发进程的同步。 提示设置一个信号量表示可否向盘中放水果，一个信号量表示可否取桔子，一个信号量表示可否取苹果。 第二章进程管理解设置三个信号量S,So,Sa，初值分别为1，0，0。 分别表示可否向盘中放水果，。 可否取桔子，可否取苹果第二章进程管理Father()while (1)p(S);Son()while (1)p(So)Daughter()while (1)p(Sa)p();将水果放入盘中;if(是桔子)v(So);else v(Sa);p()取桔子v(S);吃桔子;p()取苹果v(S);吃苹果;第二章进程管理【思考题】?四个进程A、B、C、D都要读一个共享文件F，系统允许多个进程同时读文件F。 但限制是进程A和进程C不能同时读文件F，进程B和进程D也不能同时读文件F。 为了使这四个进程并发执行时能按系统要求使用文件，现用PV操作进行管理，请回答下面的问题第二章进程管理? (1)应定义的信号量及初值? （2）在下列的程序中填上适当的P、V操作，以保证它们能正确并发工作?A()B()C()D()?1;3;5;7;?read F;read F;read F;read F;?2;4;6;8;?第二章进程管理解 （1）定义二个信号量S 1、S2，初值均为1，即S1=1，S2=1。 其中进程A和C使用信号量S1，进程B和D使用信号量S2。 （2）从1到8分别为P(S1)V(S1)P(S2)V(S2)P(S1)V(S1)P(S2)V(S2)第二章进程管理【思考题】有一阅览室，读者进入时必须先在一张登记表上进行登记，该表为每一座位列一表目，包括座号和读者姓名。 读者离开时要消掉登记信号，阅览室中共有100个座位，请问 (1)为描述读者的动作，应编写几个程序？设置几个进程？进程与程序间的对应关系如何？ (2)用类Pascal语言和P,V操作写出这些进程间的同步算法。 第二章进程管理答 (1)应编写1个程序；设置2个进程；进程与程序间的对应关系是多对1。 第二章进程管理 (2)beginS1:=100(有100个座位)S2:=0(有没阅读者)mutex:=1cobeginP1:repeatP(S1);P(mutex);登记信息;P2:repeatP(S2)P(mutex);登记信息;V(muetx);V(S2)就座，阅读；until falsecoendend();消掉信息;V(muetx);V(S1);离开阅览室;until false第二章进程管理【思考题】理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子?如果没有顾客，理发师便在理发椅上睡觉。 ?一个顾客到来时，它必须叫醒理发师?如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开。 如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开。 第二章进程管理var waiting:integer;/*等候理发的顾客数*/CHAIRS:integer;/*为顾客准备的椅子数*/customers,barbers，mutex:semaphore;/*等候理发的顾客数*/CHAIRS:integer;/*为顾客准备的椅子数*/customers,barbers，mutex:semaphore;customers:=0;barbers:=0;waiting:=0;mutex:=1;Procedure barber;beginwhile(TRUE);customers:=0;barbers:=0;waiting:=0;mutex:=1;Procedure barber;beginwhile(TRUE);/*理完一人,还有顾客吗?*/P(cutomers);/*若无顾客,理发师睡眠*/P(mutex);/*进程互斥*/waiting:=waiting/*理完一人,还有顾客吗?*/P(cutomers);/*若无顾客,理发师睡眠*/P(mutex);/*进程互斥*/waiting:=waiting1;/*等候顾客数少一个*/V(barbers);/*理发师去为一个顾客理发*/1;/*等候顾客数少一个*/V(barbers);/*理发师去为一个顾客理发*/;开*V(mutex);/*开放临界区*/cut-hair();/*正在理发*/end;procedure customerbeginP(mutex);/*进程互斥*/if waiting 计算机系统中的每个进程都可以消费（使用）或生产（释放）某类资源。 这些资源可以是硬件资源，也可以是软件资源。 ?当某一进程使用某一资源时，可以看作是消费，称该进程为消费者。 而当某一进程释放某一资源时，它就相当于生产者。 第二章进程管理问题描述通过一个有界缓冲区可以把一群生产者p1,p2,pm，和一群消费者Q1Q2Qn。 Q,Q,Q联系起来如图?只要缓冲区未满，生产者就可以把产品送入缓冲区;?只要缓冲区未空，消费者就可以从缓冲区中取走物品。 第二章进程管理图.P Q放消息取消息.nn个缓冲区(Buffer)ij第二章进程管理问题分析?为解决生产者消费者问题，应该设两个同步信号量，一个说明空缓冲区的数目，S1，N，用表示初值为有界缓冲区的大小另一个说明已用缓冲区的数目，用S2表示，初值为。 ?由于在此问题中有M个生产者和N个消费者，它们在执行生产活动和消费活动中要对有界缓冲区进行操作。 由于有界缓冲区是一个临界资源，必须互斥使用，所以，另外还需要设置一个互斥信号量第二章进程管理问题的解Q j=0;while (1)P(S2);P(mutex);Pi=0;while (1)生产产品;P(S1);P(mutex);从Bufferj取产品;j=(j+1)%n;V(mutex);V(S1);消费产品;P(S1);P(mutex);往Bufferi放产品;i=(i+1)%n;V(mutex);V(S2);第二章进程管理【思考题】?如果生产者消费者问题中的缓冲区是无界的，又该如何解呢？第二章进程管理解设信号量S1,mutex初值均为0Q j=0;while (1)P(S1);P(mutex);Pi=0;while (1)生产产品;P(mutex);从Bufferj取产品;j=(j+1)%n;V(mutex);消费产品;P(mutex);往Bufferi放产品;i=(i+1)%n;V(mutex);V(S1);第二章进程管理【思考题】有一个仓库，可以存放A和B两种产品，但要求一 （1）每次只能存入种产品（A或B） （2）NA产品数量B产品数量M。 其中，N和M是正整数。 试用P、V操作描述产品A与B的入库过程。 提示设两个信号量Sa、SbSa表示允许A产品比B产品多入库的数量Sb表示允许B产品比A产品多入库的数量第二章进程管理解设两个信号量Sa、Sb，初值分别为M-1，N-1Sa表示允许A产品比B产品多入库的数量Sb表示允许B产品比A产品多入库的数量设互斥信号量mutex，初值为1。 第二章进程管理B产品入库进程j=0;while (1)P(Sb);P(mutex);A产品入库进程i=0;while (1)生产产品;P(Sa);P(mutex);B产品入库V(mutex);V(Sa);消费产品;P(Sa);P(mutex);A产品入库V(mutex);V(Sb);第二章进程管理读者/写者问题有两组并发进程:读者和写者,共享一组数据区要求允许多个读者同时执行读操作不允许读者、写者同时操作不允许多个写者同时操作第二章进程管理第一类读者优先如果读者来1）无读者、写者，新读者可以读2）有写者等，但有其它读者正在读，则新读者也可以读1）无读者、写者，新读者可以读2）有写者等，但有其它读者正在读，则新读者也可以读有33）有写者写，新读者等如果写者来1）无读者，新写者可以写2）有读者，新写者等待3）有其它写者，新写者等待1）无读者，新写者可以写2）有读者，新写者等待3）有其它写者，新写者等待第二章进程管理第一类读者写者问题的解法?设有两个信号量w=1，mutex=1?另设一个全局变量readcount=0?w用于读者和写者、写者和写者之间的互斥?readcount表示正在读的读者数目?mutex用于对readcount这个临界资源的互斥访问第二章进程管理读者while (1)P(mutex);readcount+;if(readcount=1)P(w);写者while (1)P(w);写V(w);V(mutex);读P(mutex);readcount-;if(readcount=0)V(w);V(mutex);第二章进程管理【思考题】写优先?修改以上读者写者问题的算法，使之对写者优先，即一旦有写者到达，后续的读者必须必须等待，无论是否有读者在读。 ?提示，增加一个信号量，用于在写者到达后封锁后续的读者第二章进程管理解增加一个信号量s，初值为1读者while (1)P(s);P(mutex);readcount+;if(readcount=1)P(w);V(mutex);写者while (1)P(s);P(w);写V()();V(s);读P(mutex);readcount-;if(readcount=0)V(w);V(mutex);V(w);V(s);第二章进程管理哲学家就餐问题?有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子?每个哲学家的行为是思考，感到饥饿，然后吃通心粉?为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子第二章进程管理设fork5为5个信号量，初值为均1Philosopheriwhile (1)解思考；P(forki);P(fork(i+1)%5)；进食；V(forki);V(fork(i+1)%5)；第二章进程管理以上解法会出现死锁为防止死锁发生可采取的措施?最多允许4个哲学家同时坐在桌子周围分析最多允许个哲学家同时坐在桌子周围?仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（?）?给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之第二章进程管理2.7线程2.7.1线程的基本概念为使程序能并发执行，系统还必须进行以下的一系列操作。 1)创建进程2)撤消进程3)进程切换第二章进程管理2.线程的属性 (1)轻型实体。 (2)独立调度和分派的基本单位。 (3)可并发执行。 (4)共享进程资源。 第二章进程管理3.线程的状态 (1)状态参数。 在OS中的每一个线程都可以利用线程标识符和一组状态参数进行描述。 状态参数通常有这样几项寄存器状态，它包括程序计数器PC和堆栈指针中的内容；堆栈，在堆栈中通常保存有局部变量和返回地址；线程运行状态，用于描述线程正处于何种运行状态；优先级，描述线程执行的优先程度；线程专有存储器，用于保存线程自己的局部变量拷贝；信号屏蔽，即对某些信号加以屏蔽。 第二章进程管理 (2)线程运行状态。 如同传统的进程一样，在各线程之间也存在着共享资源和相互合作的制约关系，致使线程在运行时也具有间断性。 相应地，线程在运行时，也具有下述三种基本状态执行状态，表示线程正获得处理机而运行；就绪状态，指线程已具备了各种执行条件，一旦获得CPU便可执行的状态；阻塞状态，指线程在执行中因某事件而受阻，处于暂停执行时的状态。 第二章进程管理4.线程的创建和终止在多线程OS环境下，应用程序在启动时，通常仅有一个线程在执行，该线程被人们称为“初始化线程”。 它可根据需要再去创建若干个线程。 在创建新线程时，需要利用一个线程创建函数(或系统调用)，并提供相应的参数，如指向线程主程序的入口指针、堆栈的大小，以及用于调度的优先级等。 在线程创建函数执行完后，将返回一个线程标识符供以后使用。 终止线程的方式有两种一种是在线程完成了自己的工作后自愿退出；另一种是线程在运行中出现错误或由于某种原因而被其它线程强行终止。 第二章进程管理5.多线程OS中的进程在多线程OS中，进程是作为拥有系统资源的基本单位，通常的进程都包含多个线程并为它们提供资源，但此时的进程就不再作为一个执行的实体。 多线程OS中的进程有以下属性 (1)作为系统资源分配的单位。 (2)可包括多个线程。 (3)进程不是一个可执行的实体。 第二章进程管理2.7.2线程间的同步和通信1.互斥锁(mutex)互斥锁是一种比较简单的、用于实现进程间对资源互斥访问的机制。 由于操作互斥锁的时间和空间开锁都较低，因而较适合于高频度使用的关键共享数据和程序段。 互斥锁可以有两种状态，即开锁(unlock)和关锁(lock)状态。 相应地，可用两条命令(函数)对互斥锁进行操作。 其中的关锁lock操作用于将mutex关上，开锁操作unlock则用于打开mutex。 第二章进程管理2.条件变量每一个条件变量通常都与一个互斥锁一起使用，亦即，在创建一个互斥锁时便联系着一个条件变量。 单纯的互斥锁用于短期锁定，主要是用来保证对临界区的互斥进入。 而条件变量则用于线程的长期等待，直至所等待的资源成为可用的。 线程首先对mutex执行关锁操作，若成功便进入临界区，然后查找用于描述资源状态的数据结构，以了解资源的情况。 只要发现所需资源R正处于忙碌状态，线程便转为等待状态，并对mutex执行开锁操作后，等待该资源被释放；若资源处于空闲状态，表明线程可以使用该资源，于是将该资源设置为忙碌状态，再对mutex执行开锁操作。 第二章进程管理下面给出了对上述资源的申请(左半部分)和释放(右半部分)操作的描述。 Lock mutexLock mutexcheckdata structures;mark resourceas free;while(resource busy);unlock mutex;wait(condition variable);wakeup(condition variable);mark resourceas busy;unlock mutex;第二章进程管理3.信号量机制 (1)私用信号量(private samephore)。 当某线程需利用信号量来实现同一进程中各线程之间的同步时，可调用创建信号量的命令来创建一私用信号量，其数据结构是存放在应用程序的地址空间中。 私用信号量属于特定的进程所有，OS并不知道私用信号量的存在，因此，一旦发生私用信号量的占用者异常结束或正常结束，但并未释放该信号量所占有空间的情况时，系统将无法使它恢复为0(空)，也不能将它传送给下一个请求它的线程。 第二章进程管理 (2)公用信号量(public semaphort)。 公用信号量是为实现不同进程间或不同进程中各线程之间的同步而设置的。 由于它有着一个公开的名字供所有的进程使用，故而把它称为公用信号量。 其数据结构是存放在受保护的系统存储区中，由OS为它分配空间并进行管理，故也称为系统信号量。 如果信号量的占有者在结束时未释放该公用信号量，则OS会自动将该信号量空间回收，并通知下一进程。 可见，公用信号量是一种比较安全的同步机制。 第二章进程管理2.7.3内核支持线程和用户级线程1.内核支持线程