计算机操作系统课件(第四版)第二章

第二章

进程管理2.1 前驱图和程序执行2.2进程的描述2.3进程控制2.4进程同步2.5经典进程同步问题2.6进程通信2.7线程的基本概念2.1前驱图和程序执行程序的顺序执行前趋图与前趋关系程序的并发执行1、程序顺序执行的特征(1)程序的顺序执行语句1语句2语句3语句4语句5I1C1P1I2C2P2程序1程序2(2)特征①顺序性②封闭性③可再现性2、前趋图与前趋关系前趋图(PrecedenceGraph)一个有向无循环图描述程序或程序段之间执行的前后关系前趋关系“”如果：(Pi,Pj)∈，也可以写成：PiPj则称：Pi是Pj的直接前趋,Pj是Pi的直接后继初始结点：没有前趋终止结点：没有后继P1P2P3P8P6P5P7P4P9观察下图，初始结点是哪个？终止结点是哪个？有哪些前驱关系？思考：下图是否为前趋图？S1S2S33、程序的并发执行I1C1P1I2C2P2I3C3P3I4C4P4输入程序计算程序打印程序对于下述四条语句的程序段：S1：a:=x+2;S2：b:=y+4;S3：c:=a+b;S4：d:=c+b;S2S1S3S4并发执行时的特征间断性——“停停走走”失去封闭性——原因：多个程序共享资源不可再现性程序A{n=n+1;}程序B{print(n);n=0;}

例如:有两个循环程序A和B，共享一个变量n。程序A和B以不同的速度运行。可能出现的情况如下：1、A快B慢，得到的n值为：n+1,n+1,02、B快A慢，得到的n值为：n,0,13、n:=n+1在print(n)和n:=0之间，如图，得到的n值为

n,n+1,02.2进程的描述进程的定义和特征进程的基本状态和转换挂起操作和状态转换进程管理中的数据结构2.2.1、进程的定义和特征进程的定义进程的特征进程的定义进程：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。进程实体＝程序段＋相关的数据段＋PCB进程组成系统数据段，PCB程序段数据段LinuxLinux的进程实体组成Linux进程是由三部分组成：正文段、用户数据段和系统数据段。(1)正文段（text）——程序段正文段是只能读不能修改的指令代码，它允许系统中多个进程共享这一代码段。(2)用户数据段（usersegment）——数据段用户数据段是进程执行时直接操作的所有数据（包括全部变量在内），这些信息是可以被修改的。(3)系统数据段（systemsegment）——PCB

系统数据段存放着进程的控制信息，即进程控制块（PCB），它存放了程序的运行环境。PCB程序段数据段进程的结构图示：进程控制块动态特征的集中反映描述要完成的功能操作对象及工作区进程的其他定义：进程是一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。进程是并发程序的一次执行过程。是系统进行资源分配和调度的独立单位。进程是可以和别的计算并发执行的计算。进程与程序的区别进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。进程是暂时的，程序的永久的：进程是一个状态变化的过程，程序可长久保存。进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。进程的特征动态性：“它由创建而产生，由调度而执行，由撤销而消亡”。进程具有动态的地址空间（数量和内容），地址空间上包括：代码（指令执行和CPU状态的改变）数据（变量的生成和赋值）系统控制信息（进程控制块PCB的生成和删除）独立性：进程是一个能独立运行、独立分配资源和独立调度的基本单位。各进程的地址空间相互独立。并发性：引入进程的目的正是为了使其程序能和其他进程的程序并发执行；异步性：进程按各自独立的、不可预知的速度向前推进结构性：进程由程序段、数据段及PCB三部分组成，在Linux中称为“进程映像”2.2.2进程的基本状态及转换就绪状态（Ready）得到了除CPU以外的所有必要资源执行状态（Running）已获得处理机，程序正在被执行阻塞状态（Blocked）因等待某事件发生而暂时无法继续执行，从而放弃处理机，使程序执行处于暂停状态1、进程的三种基本状态中断接纳完成进程调度事件发生等待某事件创建终止就绪执行阻塞进程基本状态转换图创建状态为新进程创建PCB，填写信息，该进程转入就绪状态并插入就绪队列中。引入创建状态可保证进程的调度在创建工作完成后，确保对PCB操作的完整性。终止状态等待OS进行善后处理将PCB清零，将PCB空间返还系统。终止态的进程不能再执行，但需等待其它进程完成对它的信息提取后，OS再将它删除。进程的挂起状态（静止状态）引入父进程考查和修改、协调子进程间的活动操作系统协调资源使用或进行记账终端用户的请求，希望自己的程序暂时静止下来负荷调节的需要，如实时紧急任务，由系统把一些不重要的进程挂起内存外存活动静止进程的挂起状态挂起就绪挂起阻塞活动就绪执行活动阻塞挂起I/O请求挂起激活挂起调度释放激活释放唤醒1、操作系统中用于管理控制的数据结构资源信息表、进程信息表：数据结构表征其实体。包含了资源或进程的标识、描述、状态等信息及一批指针。2.2.4、进程管理中的数据结构内存设备文件进程内存表设备表文件表进程表1进程表n进程1进程n...进程实体及所用资源列表2、PCB(ProcessControlBlock)PCB中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息。OS是根据PCB来对并发执行的进程进行控制和管理的。是进程存在的唯一标志。PCB可被操作系统中的多个模块读或修改，如被调度程序、资源分配程序、中断处理程序以及监督和分析程序读或修改。PCB经常被系统访问，故应常驻内存。2.2.4、进程管理中的数据结构Linux的PCB结构3、PCB中的信息进程标识符：唯一的标识一个进程内部标识（OS）外部标识（由创建者提供，由字母数字组成）处理机状态：由CPU的各种寄存器中的内容组成。通用R指令计数器PC程序状态字PSW用户栈指针进程调度信息：进程状态进程优先级其它信息等待事件（阻塞原因）进程控制信息：程序和数据的地址同步和通信机制资源清单链接指针4、进程控制块的组织方式PCB数目一个系统中的PCB数目可为数十个、数百个甚至数千个线性方式把所有的PCB都组织在一张线性表中，将表的首地址放在内存的专用区中。链接方式把具有同一状态的PCB，用其链接字链接成一个队列就绪队列、若干个阻塞队列、空队列索引方式系统根据所有进程的状态建立相应的索引表就绪索引表、阻塞索引表等，索引表在内存的首地址记录在内存的一些专用单元中。PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9……PCB线性表示示意图PCBn执行指针就绪队列指针阻塞队列指针空闲队列指针PCB14PCB23PCB30PCB48PCB5PCB67PCB79PCB80PCB911……PCB链接队列示意图PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9……执行指针就绪队列指针阻塞队列指针按索引方式组织PCB第三节

进程的控制系统内核进程创建进程撤消进程阻塞进程唤醒进程挂起与激活进程管理中最基本功能是进程控制。进程控制的作用：创建新进程，终止已完成进程，并负责进程的状态转换。进程控制是由OS内核中的原语实现的。OS内核：把一些与硬件紧密相关的模块（如中断）、各种常用设备的驱动程序、运行频率较高的模块（时钟管理、进程调度等）以及为许多模块公用的一些基本操作，安排在靠近硬件的软件层次中，以提高OS的运行效率。OS内核是常驻内存的程序和数据。2.3.1操作系统内核原语：是由若干条指令组成的，用于完成一定功能的一个过程。具有不可分割性。

具有原子性。即：原语的执行必须是连续的，在执行的过程中不允许被中断。处理机的执行状态具有两种状态：核心态(系统态、管态)：OS的管理程序执行时处理机所处状态。具有较高的特权，能执行一切指令，访问所有寄存器和存储区。OS运行在系统态。用户态（目态）：用户程序执行时处理机所处状态。具有较低特权的执行状态，仅能执行规定的指令访问制定的寄存器和存储区。应用程序一般运行在用户态。

1、进程创建（Creat()）进程之间的关系：父、子进程与祖先进程：PCB中标识继承归还资源、“父”创建“子”、父撤子消引起创建进程的事件用户登录、作业调度、提供服务、应用请求进程创建的过程申请空白PCB、为新进程分配资源、初始化PCB、插入就绪进程队列PDPBPEPCPFPAPIPHPGPJPKPLPMPNHD就绪队列指针PCB15PCB2PCB3PCB4PCB513PCB60PCB7PCB89PCB912PCB10PCB11PCB1225PCB136……空PCB队列指针RAM程序+数据PCB80PCB682、进程撤消（Terminat()）引起进程终止（Termination）的事件正常结束：执行到最后的结束指令、中断异常结束：出现错误或因故障而被迫终止外界干扰：进程应外界的请求而终止运行进程撤消的过程检索进程状态、结束并置调度标志、撤销其所有的子进程、归还资源、移出队列一个进程可以向其父进程申请撤消自己；也可以因父进程的被撤销而被同时撤消。PDPBPEPCPFPAPIPHPGPJPKPLPMPN3、进程阻塞（Block()）引起阻塞的事件请求系统服务、启动某种操作、数据尚未到达、无新工作可做进程阻塞的过程发现上述事件，调用阻塞原语把自己阻塞停止进程的执行，修改PCB中的状态信息，并将其插入相应的阻塞队列转调度程序进行重新调度4、进程唤醒（Wakeup()）引起唤醒的事件与引起阻塞的事件相对应进程唤醒的过程阻塞进程所期待的事件出现，有关的进程调用唤醒原语，将等待该事件的进程唤醒将PCB从阻塞队列中移出，修改PCB中的状态信息，再将其插入到就绪进程队列中阻塞与唤醒要匹配使用，以免造成“永久阻塞”5、进程挂起与激活

（Suspend()、Active()）进程挂起检查被挂进程的状态，改为相应的挂起状态。把进程的PCB复制到指定的区域。最后，转向调度程序重新调度。进程激活先将进程从外存调入内存。检查该进程的现行状态，改为相应的活动状态。根据优先级确定是否需要重新调度。第四节

进程同步

进程同步的主要任务是使并发执行的诸进程之间有效地共享资源和相互合作，从而使程序的执行具有可再现性。基本概念硬件同步机制信号量机制信号量的应用进程互斥：一个进程正在访问临界资源，另一个要访问该资源的进程必须等待。并发执行可产生与时间有关的错误2.4.1基本概念两种形式的制约关系直接相互制约：源于进程间的合作间接相互制约：源于进程对资源的共享进程同步：合作完成同一个任务的多个进程，在执行速度或某些时序点上必须相互协调的合作关系。进程同步举例：例1：接力赛例2：司机－售票员司机：P1while(true){

启动车辆；正常运行；到站停车；

}售票员：P2while(true){

关门；售票；开门；

}互斥现象火车到站的调度

火车1火车2火车3…

站台轨道例1：两个同学做抢椅子的游戏。同学甲……if有空椅子then坐下……同学乙……if有空椅子then搬走……例2：民航售票系统主机A窗口B窗口C窗口D窗口每个进程执行的操作：设x表示某航班的票数。

……ifx>0thenx:=x-1;……在某时刻x=1，有a、b两人分别去A窗口、B窗口买票，分析售票情况：时间片到a人b人例3：交通流量统计统计在一定的时间段之内在路面上通过的车辆数量。利用计算机计数车辆数。S表示车辆数。S:=0;Delay(600);Write(S);中断处理程序：S:=S+1;例4：存储管理分配进程（B）……ifx<Bthen等待elsex=x-B;……回收进程（B）……x=x+B;唤醒；……(x为可用内存空间)例5：哲学家就餐问题五个哲学家围着桌子坐，工作方式：思考；

if饿了{拿左叉子；拿右叉子；吃饭；放左叉子；放右叉子；}//只能拿靠近自己左右两边的叉子临界区（临界段）临界资源：一段时间内只允许一个进程访问的资源临界区：每个进程中访问临界资源的代码段临界区的使用原则：各进程互斥地进入临界区，可实现互斥访问临界资源criticalsection;//临界区repeatuntilfalse;entrysection//进入区exitsection//退出区remaindersection;//剩余区同步应遵循的规则空闲让进、忙则等待、有限等待、让权等待P1：

a:=a+1print(a)互斥P2：a:=a-1print(a)互斥P3：ifa<0thena:=a+1elsea:=a-1互斥程序中的临界区。考察变量a2.4.2、硬件同步机制关中断利用Test-and-Set指令实现互斥利用Swap指令实现进程互斥

计算机提供一些特殊的硬件指令，允许对一个字中的内容进行检测和修正，或者是对两个字的内容进行交换。利用这些特殊指令解决临界区问题。临界区的标志可以看做一个锁。锁开、锁关两种状态关中断关中断是实现互斥的最简单的方法之一。进入锁测试之前关闭中断，直至完成锁测试，并上锁之后才能打开中断。进程在临界区中执行期间，计算机系统不响应中断，也不会引发进程调度。缺点：滥用关中断权利关中断时间过长，会影响系统效率不适用于多CPU系统利用Test-and-Set指令实现互斥是一种借助TS（测试建立）硬件指令实现互斥TS指令的一般性描述：booleanTS(boolean*lock){booleanold;old=*lock;*lock=TRUE;returnold;}do{...whileTS(&lock)；criticalsection;lock=False;remaindersection;}while(TRUE)利用Swap指令实现进程互斥对换指令(用于交换两个字的内容)：booleanswap(boolean*a,*b){booleantemp;temp=*a;*a=*b;*b=temp;}do{key=TRUE；do{swap(&lock,&key);}while(key!=FALSE);criticalsection;lock=False;remaindersection;}while(TRUE)3、信号量（灯）机制1965年，荷兰人Dijkstra首先提出信号量机制信号量（Semaphores）用于表示资源数目或请求使用某一资源的进程个数的数据结构。信号量是一个被保护的变量，它的值只能通过初始化和两个wait、signal原语来操作——作为OS核心代码执行。wait操作（P原语）——进程申请使用资源的操作（或申请进入临界区的操作），类似于进入区的功能。P是荷兰语的test(proberen)signal操作（V原语）——进程用此释放临界资源，类似于退出区的功能。V是荷兰语的increment(verhogen)Dijkstra（迪杰斯特拉）信号量的类型：整型：S为初值非负的整型变量，通常描述资源的状态或可用资源的数量。记录型：二元组(S,Q)，Q初始状态为空的队列。AND型：一次需要多个共享资源，改进wait-signal操作。信号量集：一次需要N个多类资源，改进wait-signal操作。整型信号量

intS;//Semaphore wait(S){whileS≦0dono-op；

S--;} signal(S) {S++;} wait(s)和signal(s)是原子操作只要信号量S≦0就不断测试，不满足让权等待是一个记录型的数据结构，包含两个数据项，一是记数值域，另一是等待该信号量的进程队列首指针域。描述如下：记录型信号量：typedefStructSemaphore{intvalue;//整型变量

List_of_processL;//进程等待队列

}S;SvalueLwait(S){S.value--;ifS.value<0thenblock（S.L）;//将该进程状态置为等待状态；并将该进程的PCB插入相应的等待队列S.L末尾}wait(S)原语描述如下：执行一次wait操作意味着请求分配一个单位的资源，因此描述为:s.value=s.value-1。减1后：若s.value≥0，则进程继续进行；若s.value＜0，表示已无资源可用，因此请求该资源的进程将被阻塞，要把它排在信号量s的等待队列中，此时，s.value的绝对值等于该信号量等待队列上的进程数目。s.value的物理含义：信号量的物理意义：S>0：S表示可用资源的个数

S=0：S表示无资源，无等待进程

S<0：|S|表示等待队列中进程的个数signal(S){S.value++;ifS.value≤0thenwakeup（S.L）;//唤醒相应等待队列中等待的第一个进程：改变其状态为就绪态；并将其插入到就绪队列。}signal(S)原语描述如下：

执行一次signal操作意味着释放一个单位的资源，故s.value=s.value+1。加1后：若s.value＞0，则进程继续；若s.value≤0，表示信号量请求队列中仍有因请求该资源而被阻塞的进程，因此应把队列中的一个或几个进程唤醒，使之转至就绪队列中。举例：已知系统中有两台打印机，又有A、B、C、D四个进程都要使用打印机，分析其wait、signal操作和信号量变化。设打印机资源信号量为s，初值为2。A：{wait(s);

使用打印机；

signal(s);}B：{wait(s);

使用打印机；

signal(s);}C：{wait(s);

使用打印机；

signal(s);}D：{wait(s);

使用打印机；

signal(s);}s=1s=0s=-1s=-2s=-1s=0s=1s=24、信号量的应用实现进程互斥例如：两个进程都使用一台打印机实现进程同步例如：矩阵运算A＋B利用信号量实现前驱关系(1)实现进程互斥mutex=1；

…wait(mutex))

临界区代码

signal(mutex)

…

SAVE：

{m1=amountm1=m1+10amount=m1}TAKE：

{m2=amountm2=m2-10amount=m2}如何用wait、signal操作实现两并发进程的互斥执行？例2

兄弟俩共用一个账号，每次仅限存取十元钱，存钱和取钱的进程分别如下所示：

amount=0parbeginSAVE;TAKEparend解决方法：设信号量mutex（初值为1）控制进程对变量amount的互斥使用。amount=0parbeginSAVE;TAKEparendSAVE：

{wait(mutex)m1=amountm1=m1+10amount=m1signal(mutex)}

TAKE：

{

wait(mutex)m2=amountm2=m2-10amount=m2signal(mutex)}

(2)实现进程同步例3：矩阵A+B运算(3)实现前趋关系前趋关系：并发执行的进程P1和P2中，分别有代码C1和C2，要求C1在C2开始前完成。为该前趋关系设置一个同步信号量S12，其初值为0。{…C1

Signal（S12）

…}P1：{…

Wait（S12）

C2…}P2：C1C2s12S1S3S2S4S5S6S7S8例4：利用信号量来描述前趋图关系

该前趋图具有8个结点，共有有向边10条，可设10个信号量，初值均为0；有8个结点，可设计成8个并发进程，具体描述如下：S1S3S2S4S5S6S7S8agefbcdhijsmaphorea，b，c，d，e，f，g，h，I，j=0,0,0,0,0,0,0,0,0,0；parbegin {S1;signal（a）；signal（b）；signal（c）；}{wait（a）；S2；signal（d）；}{wait（b）；S3；signal（e）；signal（f）；}{wait（c）；S4；signal（g）；}{wait（d）；wait（e）；S5；signal（h）；}{wait（f）；wait（g）；S6；signal（i）；}{wait（h）；wait（i）；S7；signal（j）；}{wait（j）；S8；}parendS1S3S2S4S5S6S7S8agefbcdhij用信号量解题的关键步骤：

信号量的设置；

给信号量赋初值（常用的互斥和同步信号量值的大小）；

wait、signal操作安排适当的位置注意：1）互斥信号量：互斥时使用的信号量（二元信号量）：其初值为1或n，表示临界资源的数目，用作互斥。它wait、signal操作在同一个进程中。

2）同步信号量：它联系着一组并行进程，但其初值为０或为某个正整数ｎ，主要用于进程同步，wait、signal操作在两个进程中配对出现。信号量小结信号量必须置初值，且只能置一次初值。初值可为非负整数信号量分类：互斥的信号量：它的P、V在同一个进程中同步的信号量：它的P、V在不同的进程中信号量的物理意义：S>0：S表示可用资源的个数S=0：S表示无资源，无等待进程

S<0：|S|表示等待队列中进程的个数第五节

经典进程同步问题生产者-消费者问题生产者与消费者互斥访问公用数据缓冲区生产“数据”，消费“数据”读者-写者问题数据文件或记录被多个进程共享并互斥访问的问题允许多个Reader同时访问，但不允许一个Writer和其它Reader或任何两个以上的Writer同时访问哲学家就餐问题多资源共享及互斥访问五个哲学家的思考与互斥共享五根筷子就餐的问题生产者-消费者问题仓库放取生产者——消费者问题分类：第一类：一个生产者，一个消费者，单一资源第二类：一个生产者，一个消费者，多个资源第三类：多个生产者，多个消费者，多个资源情况一：单一资源的Producer-Consumer问题（同步问题）BufPC①分析进程间的同步关系：②设置信号量：

设进程P的同步信号量：buffer(empty)，初值为1，表示缓冲区个数（空缓冲区的个数）。设进程C的同步信号量：product(full)

，初值为0，表示产品个数(满缓冲区的个数)。P：

while(true){

生产一产品；

P(buffer);

送产品到缓冲区；}；C：

while(true){P(product);

从缓冲区取一产品；消费产品；}；V(product);V(buffer);初值buffer=1;product=0情况二：多个资源的P—C问题（有限资源）…...n1PCBuffer（n个缓冲区）1、设置信号量

①buffer————进程P的私用信号量,初始值为n。（缓冲区的个数）

②product

————进程C的私用信号量,初始值为0。2、算法描述

Main（）

{smaphorebuffer=n,product=0；

intin=0,out=0;parbegin

P;C;parend}P：

while(true){

生产一产品；

P(buffer);

往Buffer[i]放产品；

V(product);in=(in+1)%n;//环形缓冲区

}；C：

while(true){P(product);

从Buffer[j]取产品；

V(buffer);

消费产品；

out=(out+1)%n;}；初值buffer=n；product=0情况三：n个缓冲区，m个生产者，k个消费者123…….……nP1P2…Pm.C1C2…Ck要求：任何时刻只能有一个进程可对共享缓冲池进行操作。1)分析进程的同步关系2)设置信号量

a.互斥信号量mutex，表示缓冲池是否可用，初值为1。

b.生产者的同步信号量buffer(empty)，表示缓冲区个数（空单元数），初值为n。

c.消费者的同步信号量product(full)，表示产品个数（满单元个数），初值为0。Producer：

while(true){

生产一产品；

wait(buffer);

往Buffer[in]放产品；

in=(in+1)%n;signal(product);}；Consumer：

while(true){wait（product）；

从Buffer[out]取产品；

out=(out+1)%n;signal（buffer）;

消费一产品；}；wait（mutex）;signal（mutex）;wait(mutex);signal(mutex);初值buffer=n；product=0；mutex=1

该问题中的两个wait操作的顺序不能颠倒，否则容易导致死锁。例如，消费者进程的两个wait操作顺序如下：

Consumer：

while(true){wait(mutex);wait（product）；从Buffer[out]取产品；

out=(out+1)%n;signal(mutex);signal（buffer）;

消费一产品；}；Producer：

while(true){

生产一产品；

wait(buffer);wait(mutex);

往Buffer[in]放产品；

in=(in+1)%n;signal(mutex);signal(product);}；问题：其实生产者和消费者间是不用互斥的，为了提高效率，为生产者和消费者分别设置互斥信号量。解决方法：为所有生产者设置一互斥信号量：mutex1;为所有消费者设置一互斥信号量：mutex2；初值均为1。代码如下：Producer：

while(true){

生产一产品；

wait（buffer）;

往Buffer[in]放产品；

in=(in+1)%n;

signal(product);}；Consumer：

while(true){wait（product）;

从Buffer[out]取产品；

out=(out+1)%n;signal（buffer）;

消费一产品；}；初值buffer=n；product=0；mutex1=1；mutex2=1wait（mutex1）;signal（mutex1）;wait（mutex2）;signal（mutex2）;小结P(S)表示申请（请求、使用）一个资源V(S)表示释放（归还）一个资源信号量的初值应该>=0P、V必须成对出现，但不一定一一对应。当互斥操作时，处于同一进程当同步操作时，则在不同进程如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要。一个同步P操作与一个互斥P操作在一起时，同步P操作应在互斥P操作前，而两个V操作无关紧要。思考：有一个充分大的池子，两个人分别向池中扔球。甲扔红球，乙扔兰球，一次扔一个。开始时池中有红球、兰球各一个，要求池中球满足条件：1<=红球数/兰球数<=2试用P、V描述两个过程。AND型信号量集AND型信号量集是指同时需要多种资源，且每种占用一个时的信号量操作。基本思想：在一个原语中申请整段代码需要的多个临界资源，要么全分配给它要么一个都不分配。AND型信号量集P原语：Swait(SimultaneousWait)AND型信号量集V原语：SsignalSwait(S1,S2,…,Sn)//P操作{while(true){if(S1>=1&&S2>=1&&…&&Sn>=1){for(i=1;i<=n;++i)--Si;break;}else{

调用进程进入第一个小于1信号量的等待队列Sj.L;

阻塞调用进程；

}}}

Ssignal(S1,S2,…,Sn)//V操作{for(i=1;i<=n;++i){++Si//释放占用的资源；

for(在Si.L中等待的每个进程P)//检查每种资源的等待队列的所有进程

{从等待队列Si.L中取出进程P；

if(判断进程P是否通过Swait中的测试){进程P进入就绪队列；}//通过检查时的处理

else{进程P进入某等待队列；}//未通过检查时的处理

}}}哲学家就餐问题……………0101223344信号量定义：varchopstick[0,…,4]ofsemaphore;所有信号均量初始化为1第i位哲学家的活动描述：

while(true){ P(chopstick[i]); P(chopstick[(i+1)%5]); …… eating; …… V(chopstick[i]); V(chopstick[(i+1)%5]); …… thinking; }Swait(chopstick[i],chopstick[(i+1)%5]);Ssignal(chopstick[i],chopstick[(i+1)%5]);1、至多只允许四位哲学家同时坐在桌旁；2、仅当哲学家左右两边的筷子均可用时才允许他拿起筷子；3、规定奇数号哲学家先拿起他左边的筷子，再拿右边的筷子；而偶数号哲学家先拿起他右边的筷子再拿左边的筷子。死锁的解决办法如下：第1种解决解决方法：Semaphorechopstick[5]={1，1，1，1，1};Semaphoresm=4;while(true){wait（sm）；

wait（chopstick[i]）; wait（chopstick[(i+1)%5]）; …… eating; …… signal（chopstick[i]）; signal（chopstick[(i+1)%5]）;signal（sm）；

…… thinking;}第2种解决解决方法：用AND型信号量解决信号量定义：semaphorechopstick[5];所有信号均量初始化为1第i位哲学家的活动描述：

while(true){ wait(chopstick[i]); wait(chopstick[(i+1)%5]); …… eating; …… signal(chopstick[i]); signal(chopstick[(i+1)%5]); …… thinking; }Swait(chopstick[i],chopstick[(i+1)%5]);Ssignal(chopstick[i],chopstick[(i+1)%5]);while(true){ifi%2==0then{wait(chopstick[i]);wait(chopstick[(i+1)%5]);……eating;……signal(chopstick[i]);signal(chopstick[(i+1)%5]);……thinking;}else{wait(chopstick[(i+1)%5]);wait(chopstick[i]);……eating;……signal(chopstick[(i+1)%5]);signal(chopstick[i]);……thinking;}}

第3种解决解决方法：则第i位哲学家的活动描述：Semaphorechopstick[5]={1，1，1，1，1};一般信号量集一般信号量集是指同时需要多种资源，每种占用的数目不同、且可分配的资源还存在一个临界值时的信号量处理。基本思路：在AND型信号量集的基础上进程扩充，在一次原语操作中完成所有的资源申请。对应的PV原语格式为：

Swait(S1,t1,d1;…;Sn,tn,dn)Ssignal(S1,d1;…;Sn,dn)进程对信号量Si的

下限值（测试值）为ti（表示信号量的判断条件，要求Si>=ti;即当资源数量低于ti时，便不予分配）需求值（占用值）为di（表示资源的申请量，即Si=Si-di）Swait(S,d,d)Swait(S,1,1)Swait(S,1,0)

//只测试，不占用（可控开关）一般信号量集的几种情况：读者—写者问题有两组并发进程：读者、写者，共享一组数据区要求：允许多个读者同时执行读操作不允许读者、写者同时操作（读写互斥）不允许多个写者同时操作（只能一人写）第一类：读者优先

如果读者来：无读者、写者，新读者可以读有写者在等待，但有其他读者在读，则新读者也可以读有写者在写，新读者等待

如果写者来：无读者，新写者可以写有读者，新写者等待有其他写者，新写者等待例如：教室——共享文件上自习——读者（多个人使用教室）练歌——写者（1个人使用教室）策略：1、唱歌的人进来后，把门关上，其他任何人等待2、自习的人进来后，把前门关上，后门开。其他自习的人从后门进，唱歌的人等待。关键：1、第一个读者进入后把前门关，后门开2、最户一个读者离开时，把后门关，从前门出读者：

while(true){if(readcount==0)P(wmutex);readcount++;

读；

readcount--;if(readcount==0)V(wmutex)

};P(rmutex);V(rmutex);P(rmutex);V(rmutex);写者：

while(true){P(wmutex);

写

V(wmutex);};初值

wmutex:=1rmutex:=1用一般信号量集表示：

(只允许至多RN个人同时读)写者：

Swait(mx,1,1;rcount,RN,0);//既无写者也无读者才可“写”操作写

Ssignal(mx,1);读者：

Swait(rcount,1,1;mx,1,0);

读；

Ssignal(rcount,1);

初值mx:=1rcount:=RN控制读者人数管程机制

管程的基本概念管程应用分析1、管程的基本概念管程的提出：

采用P、V同步机制来编写并发程序，对于共享变变量及信号量变量的操作将被分散于各个进程中。缺点：易读性差、不利于修改和维护、正确性难以保证管程的产生：Dijkstra（1971）：”秘书”进程

Hansen和Hoare（1973）：管程概念：管程（Monitor）定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。管程的形式：构成部分名字局部于管程的数据结构说明——共享变量；局部于管程的对该数据结构进行操作的一组过程/函数对局部于管程的数据的初始化语句。

typemonitor-name=monitorvariabledeclarationsprocedureentryp1(…);begin….end;…prcedureentryPn(…);begin…end;begininitializationcode;end管程的特点：1、封装性—管程内的共享变量在管程外不可见。2、管程必须互斥进入3、管程通常是用来管理资源的，因而在管程中应当设有进程等待队列以及相应的等待和唤醒操作。问题：多个进程出现在管程中

当一个进入管程的进程Q执行等待操作时，它应当释放管程的互斥权；当另一个进入管程的进程P执行唤醒操作时，(如P唤醒Q)，管程中便存在两个同时处于活动状态的进程。(这是管程所不允许的)处理方法有三种：（前提：P唤醒Q）1、P等待、Q继续，直到Q退出或等待 2、Q等待、P继续，直到P退出或等待3、规定唤醒操作为管程中最后一个可执行的操作入口等待队列：等待进入管程紧急等待队列：在管程内部由于执行唤醒操作，可能会出现多个等待进程注：紧急等待队列优先级高于入口等待队列。条件变量condition：

当进入管程的进程因资源被占用等原因不能继续运行时要使其等待，为此在管程内部可以说明和使用一种特殊类型的变量，称为条件变量：

Varcconditon；

对于条件变量可以执行wait和signal操作。c.wait：如果紧急等待队列非空，则唤醒第一个等待者；否则，释放管程的互斥权，执行此操作的进程的PCB入C链尾部。c.signal：如果C链为空，则相当于空操作，执行此操作的进程继续；否则，唤醒第一个等待者，执行此操作的进程的PCB入紧急等待队列的尾部。2、管程应用分析生产者-消费者问题put(item)，产品放入缓冲区中get(item)，从缓冲区中取出一产品producer－consumer，简称p_ctypep_c=monitorVarin,out,count:integer;buffer:array[0,…n-1]ofitem;

notfull,notempty:condition;

procedureentryput(Varpro:item)begin

ifcount>=nthennotfull.wait;buffer[in]:=pro;in:=(in+1)modn;count:=count+1;ifnotempty.queue**notempty.signal;end

procedureentryget(Varpro:item)begin

ifcount<=0thennotempty.wait;pro:=buffer[out];out:=(out+1)modn;count:=count-1;

ifnotfull.queuethennotfull.signal;endbeginin:=out:=0;count:=0;endProducer:beginrepeatproduceaniteminnextp;

p_c.put(nextp);untilfalse;endConsumer:beginrepeat

p_c.get(nextc);consumetheiteminnextc;untilfalse;end第六节

进程通信进程通信的概念进程通信的类型消息传递通信的实现方法消息传递系统实现中的若干问题消息缓冲队列通信机制1、进程通信的概念进程通信，是指进程之间的信息交换。低级通信（互斥、同步）利用信号量机制实现进程间的数据传递。缺点：效率低；对用户不透明。高级通信（进程通信）进程之间利用OS提供的一组通信命令，高效地传送大量数据的信息交换方式。优点：高效，方便，简化了通信程序的设计。2、进程通信的类型高级通信机制可分为：共享存储器系统、消息传递系统、管道通信系统三种。共享存储器系统基于共享数据结构的通信方式基于共享存储区的通信方式消息传递系统进程之间的数据交换，是以格式化的消息为单位消息（Message报文）及相关的一组命令直接通信方式和间接通信方式管道通信系统（首创于UNIX系统）管道（Pipe文件）：用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件。管道通信：发送进程和接收进程利用管道进程通信。双方进程的协调：互斥、同步、确定对方存在。3、消息传递通信的实现方法直接通信方式发送进程利用OS提供的发送命令原语，直接把消息发送给目标进程。Send(Receiver,message)、Receive(Sender,message)利用直接通信原语，解决生产者－消费者问题：生产者消费者

repeat……produceaniteminnextp;……send(consumer,nextp);untilfalse;

repeat……receive(producer,nextc);……consumeraniteminnextc;untilfalse;间接通信方式进程之间通过一个作为共享数据结构的中间实体—信箱，以消息暂存方式实现的通信。操作原语：信箱的创建、撤消；消息的发送接收Send(mailbox,message)Receive(mailbox,message)信箱的创建和拥有者：OS或用户（通信）进程。信箱的种类：私用信箱、公用信箱、共享信箱利用信箱通信时，发送和接收进程之间的关系：一对一、多对一、一对多、多对多4、消息传递系统实现中的问题通信链路网络中：显式调用“建立/拆除连结原语”单机中：系统自动建立/拆除连结，只需调用发送原语消息格式消息头（单机简单）+消息正文定长、变长消息格式。通常系统同时支持两种格式。进程同步发送进程阻塞、接收进程阻塞发送进程不阻塞、接收进程阻塞发送进程和接收进程均不阻塞选讲5、消息缓冲队列通信机制Hansen教授首先提出的消息缓冲队列通信机制是通过内存中公用的消息缓冲区进行进程通信，属直接通信方式。发送原语send(receiver,a)a：发送区的地址接收原语receive(b)b：接收区的地址数据结构消息缓冲区PCB中有关通信的数据项通信过程：构成消息：发送进程在工作区设置发送区a，将消息正文和有关控制信息填入其中。发送消息：将消息从发送区a复制到消息缓冲区，并把它插入到目标进程的消息队列中。接收消息：由目标进程从自己的消息队列中找到第一个消息缓冲区，并将其中的消息复制到自己的接收区b中。（1）消息缓冲区：typemessagebuffer=recordsender；发送区进程标识符

size；消息长度

text；消息正文

next；指向下一个消息缓冲区的指针

end（2）PCB中有关通信的数据项：typeprocesscontrolblock=record…mq；消息队列首指针

mutex；消息队列互斥信号量

sm；消息队列资源信号量end发送原语：proceduresend(receiver,a)begingetbuf(a,size,i)//根据a.size申请缓冲区

i.sender:=a.sender;i.size:=a.size;i.text:=a.text;i.next:=0;getid(PCBset,receiver,j);//获得接收进程内部标识符

wait(j.mutex);insert(j.mq,i);//将消息缓冲区插入消息队列

signal(j.mutex);signal(j.sm);end//将发送区a的信息复制到消息缓冲区中接收原语：procedurereceive(b)beginj:=internalname;//j为接收进程的内部标识符

wait(j.sm);wait(j.mutex);remove(j.mq,i);//将消息队列中第一个消息移出

signal(j.mutex);b.sender:=i.sender;b.size:=i.size;b.text:=i.text;

releasei;//将消息缓冲区i归还系统end//将消息缓冲区i的信息复制到接收区b

进程A PCB(B) 进程B

Send(B,a)Sender:ASize:6Text:Hello!Receive(b)Sender:ASize:6Text:Hello!Sender:ASize:6Text:Hello!Next:0……首指针：mq互斥：mutex队列资源：sm……a发送区ab接收区b消息缓冲通信第七节

线程的基本概念线程的引入线程和进程的比较线程的属性线程的状态多线程OS中的进程1、线程的引入进程（60年代）目的：使多个程序并发执行，提高资源利用率和系统吞吐量定义：在OS中能拥有资源和独立运行的基本单位进程的创建、撤消与切换存在较大的时空开销，限制了并发程度的提高。线程（80年代）目的：减少程序在并发执行时所付出的时空开销。思想：“轻装上阵”——将进程的两个属性分离。定义：线程是系统独立调度和分派（即可独立运行）的基本单位。进程——拥有资源的单位调度线程是调度和分派的基本单位，进程是拥有资源的基本单位并发性同族、非同族线程均可并发。拥有资源线程几乎不占资源系统开销线程的切换、同步、通信无须内核干预。开销小2、线程和进程的特点轻型实体：线程几乎不占资源（TCB、程序计数器、寄存器、堆栈）独立运行的基本单位：切换迅速且开销小可并发执行：同族、非同族的线程皆可并发共享进程的资源：同族的线程共享进程的资源可以创建、撤销另一个线程3、线程的属性

每个线程都利用TCB和一组状态参数进行描述(1)状态参数：寄存器状态、堆栈、运行状态、优先级、专用存储器、信号屏蔽(2)运行状态：就绪态、执行态、阻塞态4、线程的状态进程作为系统资源分配的单位进程不是一个可执行的实体进程可包括一个或多个线程单进程单线程（各种UNIX版本）单进程多线程（WindowsNT/Solaris/OS/2）5、多线程OS中的进程地址空间和其他资源（如打开文件）：同一进程的各线程间共享资源－－进程间相互独立通信进程间通信IPC－－线程间可以直接读写进程数据段（如全局变量）来进行通信，需要线程间同步和通信手段的辅助，以保证数据的一致性调度

不论是系统进程还是用户进程，进程的创建