进程同步与通信xiuga.ppt

第3章 进程同步与通信 进程同步与互斥 经典进程同步问题 管程 AND信号量 进程通信 本章要点本章要点 取空闲块的进程Getspace: Begin 局部变量 g g=stacktop top=top1 返回值为g End 释放数据块ad的进程Release(ad): Begin top=top1 stacktop=ad End 设t0时刻，top=3。假设执行顺序为： 先执行Release(ad)的第一条： top=top1 = 31= 4 再执行Getspace： g=stack4，top=top1= 3 再执行Release(ad)的第二条： stack3=ad 3.1 进程的同步与互斥 3.1 进程的同步与互斥 同步与互斥的引入 OS引入进程后，由于进程的异步性， 可能会导致程序执行结果的不确定性， 使程序执行时出现不可再现性。 进程互斥与同步的主要任务是使并发执 行的诸进程之间能有效地共享资源和相 互合作，从而使程序的执行具有可再现 性。 程序的制约方式有如下两种 ： （1）间接制约方式。互斥 这是由于竞争相同资源而引起的，得到资 源的程序段可以投入运行，而得不到资源 的程序段就是暂时等待，直至获得可用资 源时再继续运行。 （2）直接制约方式。同步 这通常是在那些逻辑上相关的程序段之间 发生的。一般是由于各种程序段要求共享 信息引起的。 进程同步的基本概念 同步：指多个进程中发生的事件存在着某种时 序关系，它们必须按规定时序执行，以共同完成 一项任务 。 互斥：多个进程不能同时使用同一资源。 临界资源：某段时间内仅允许一个进程使用的 资源。 临界区：每个进程中访问临界资源的那段代码 。 例：P1，P2两进程共 享变量COUNT（ COUNT的初值为5 ） P1: R1=COUNT; R1=R1+1; COUNT=R1; P2: R2=COUNT; R2=R2+1; COUNT=R2; 分析： 1执行顺序P2P1 执行结果 P1：COUNT为7， P2：COUNT为6。 2执行顺序 P1：R1=COUNT P2：R2=COUNT P1：R1=R1+1；COUNT=R1 P2：R2=R2=1；COUNT=R2 执行结果 P1：COUNT为6， P2：COUNT为6。 临界资源实例 例：P1，P2两线程共 享变量COUNT（ COUNT的初值为5 ） P1: R1=COUNT; R1=R1+1; COUNT=R1; P2: R2=COUNT; R2=R2+1; COUNT=R2; 用Bernstein条件考察 R（P1）=R1，COUNT W（P1）=R1，COUNT R（P2）=R2，COUNT W（P2）=R2，COUNT R（P1）W（P2） 临界资源实例 P1、P2不符合Bernstein条件 必须对程序的执行顺序施加某种限制 While(1) 空闲让进 当无进程处于临界区时，临界资源 处于空闲状态。此时允许进程进入 临界区。 忙则等待 当已有进程进入临界区时，临界资 源正在被访问，其他想进入临界区 的进程必须等待。 有限等待 对于要求访问临界资源的进程，应 保证在有效的时间内进入，以免进 入“死等”状态。 让权等待 当进程不能进入临界区时，应立即 释放处理机，以免进程进入“忙等 ”。 进入区 临界区 退出区 剩余区 同步机制应遵循的准则 访问临界资源的进程描述为 互斥实现的硬件方法 禁止中断 专用机器指令 TS（Test and Set）指令 Swap指令 /TS指令： boolean TS(lock); boolean lock; boolean temp; temp = lock; lock = true; return temp; Lock有两种状态： 当lock=false时，表示资源空闲; 当lock=true时，表示资源正在被使用。 为了实现互斥，设布尔变量lock，其初值为false, 表示资源空闲。利用TS指令实现互斥。 缺点：没有做到：“让权等待”。 /TS指令的使用 while (TS(lock) /*什么也不做*/; 临界区; lock = false; 剩余区; TS（Test and Set）指令 互斥实现的软件方法 /进程0 while (turn!=0) /什么都不做; 临界区; turn = 1; 剩余区; /进程1 while (turn!=1) do /什么都不做; 临界区; turn = 0; 剩余区; 设置公共整型变量 turn，用于指示进 入临界区的进程编 号i(i=0,1)。使P0 、P1轮流访问临界 资源。 缺点：强制性轮流 进入临界区，不能 保证“空闲让进” 。 单标志算法 /进程0 while (flag1) /什么都不做 ; flag0=true; 临界区; flag0 =false; 剩余区; /进程1 while ( flag0) /什么都不做 ; flag1=true; 临界区; flag1 =false; 剩余区; 设置数组flag，初始时设 每个元素为false,表示 所有进程都未进入临界 区。若flagi=true, 表示进程进入临界区执 行。 在每个进程进入临界区时 ，先查看临界资源是否 被使用，若正在使用， 该进程等待，否则才可 进入。解决了“空闲让 进”问题。 缺点：可能同时进入临界 区，不能保证“忙则等 待”。 用软件方法解决互斥问题 双标志、先检查算法 /进程0 flag0=true; while (flag1) /什么也不做; 临界区; flag0 =false; 剩余区; 两进程先后同时作flagi=true; 缺点：保证了不同时进入临界区，但 又可能都进不去。不能保证“有空让 进”。 /进程1 flag1=true; while (flag0) /什么也不做; 临界区; flag1 =false ; 剩余区; 双标志、先修改后检查算法 用软件方法解决互斥问题 /进程0 flag0=true; turn=1; while (flag1) 临界区; flag0 =false ; 剩余区; 保证了“有空让进”和“忙则等待”。 /进程1 flag1=true; turn=0; while (flag0) 临界区; flag1 =false ; 剩余区; 先修改、后检查、后修改算法 用软件方法解决互斥问题 信号量和PV操作 1965年，荷兰学者Dijkstra提出了信号灯机 制，卓有成效地解决了进程同步问题。 记录型信号灯的定义 struct semaphore int value; struct PCB *queue; 信号灯的PV操作 void wait(semaphore s) s.value = s.value - 1; if (s.value 0 是 sem0 返回 P原语V原语 sem为互斥信号量，取值（1，0，-1）。 sem=1表示有一个空闲资源。即，进程PA和PB都没进临界区 。 sem=0表示有0个空闲资源。即，某进程已经进入临界区 sem=-1表示差一个空闲资源。即，某进程已经进入临界区， 但另有一进程已经做了P原语，正在等待。 Pb: P(sem) V(sem); 可具体化 用信号灯解决互斥问题 用信号灯解决互斥问题 semaphore mutex=1; P1: while (1) P(mutex); 临界区; V(mutex); 剩余区; ; P2: while (1) P(mutex); 临界区 V(mutex); 剩余区; ; A：测试，直到buf为空 计算 计算结果buf goto A 计算进程Pc打印进程Pp B：测试，直到buf满 打印buf中的数据 清除buf中的数据 goto B 这里假定已经对公有缓冲区buf进行了互斥措施。 缺点：用“测试”来实现同步，消耗大量CPU时间。 用“测试”来实现同步 A：wait(Bufempty) 计算 计算结果buf Bufempty=false signal(Buffull=true) goto A 计算进程Pc打印进程Pp B：wait(Buffull) 打印buf中的数据 清除buf中的数据 Buffull=false signal(Bufempty=true) goto B 1、设消息名Bufempty表示buf空，消息名Buffull表示buf满。 2、初始化Bufempty=true，Buffull=false。 wait的时候，可处于等待状态。 不消耗CPU。 返回节目录 用wait和signal实现同步 私用信号量 公有信号量：用于互斥。表示公有资源是否可用。 私用信号量：用于同步。例如，Bufempty是计算进程 的私用信号量，Buffull是打印进程的私用信号量。 用P，V原语实现同步 1、设Bufempty为进程Pa的私用信号量，Buffull为Pb的私用信号量 2、初始化：Bufempty=n；Buffull=0。 Pa：deposit(data) 局部变量x P(Bufempty) 选择一个空区Buf(x) Buf(x) data Buf(x)置满标记 V(Buffull) 发送进程Pa接收进程Pb B：remove(data) 局部变量x P(Buffull) 选择一个空区Buf(x) data Buf(x) Buf(x)置空标记 V(Bufempty) 问题：需要考虑互斥吗？ 用信号灯解决同步问题 semaphore a,b=0,0; s1; V(a); V(b) P(a); s2 P(b); s3 生产者消费者问题 读者写者问题 哲学家进餐问题 打磕睡的理发师问题 3.2经典进程同步问题 生产者-消费者问题 指有两组进程共享一个环形的缓冲池。一组进程被称为 生产者，另一组进程被称为消费者。 缓冲池是由若干个大小相等的缓冲区组成的，每个缓冲 区可以容纳一个产品。 生产者进程不断地将生产的产品放入缓冲池，消费者进 程不断地将产品从缓冲池中取出。 用信号量解决“生产者-消费者”问题 void consumer()/消费者进程 while (true) P(full); P(mutex); data_c = bufferj; j = (j + 1) % n; V(mutex); V(empty); consume the item in data_c; semaphore mutex =1; semaphore empty = n; semaphore full = 0; int i,j; ITEM buffern; ITEM data_p, data_c; void producer() /生产者进程 while (true) produce an item in data_p; P(empty); P(mutex); bufferi = data_p; i = (i + 1) % n; V(mutex); V(full); 读者-写者问题 一个数据对象若被多个并发进程所共享， 且其中一些进程只要求读该数据对象的内容 ，而另一些进程则要求写操作，对此，我们 把只想读的进程称为“读者”，而把要求写的 进程称为“写者”。 问题描述： 读者可同时读； 读者读时，写者不可写； 写者写时，其他的读者、写者均不可进 入。 读者进程： while(true) 有人要读 P(Wmutex); 读; 无人读了 V(Wmutex); 写者进程： while(true) P(Wmutex); 写; V(Wmutex); semaphore Wmutex=1; 用信号量解决读者-写者问题 void reader() /*读者进程*/ while (true) P(Rmutex); if (Rcount = 0) P(Wmutex); Rcount = Rcount + 1; V(Rmutex); read; /* 执行读操作 */ P(Rmutex); Rcount = Rcount - 1; if (Rcount = 0) V(Wmutex); V(Rmutex); Semaphore Wmutex,Rmutex=1,1; int Rcount; 用信号量解决读者-写者问题 void writer() /*写者进程*/ while (true) P(Wmutex); write; /* 执行写操作 */ V(Wmutex); 哲学家进餐问题 五个哲学家，他们的生活方式是交替地思考和 进餐。 哲学家们共用一张圆桌，围绕着圆桌而坐，在 圆桌上有五个碗和五支筷子，平时哲学家进行思 考，饥饿时拿起其左、右的两支筷子，试图进餐 ，进餐完毕又进行思考。 这里的问题是哲学家只有拿到靠近他的两支筷 子才能进餐，而拿到两支筷子的条件是他的左、 右邻居此时都没有进餐。 semaphore chopstick5 =1,1,1,1,1; void philosopher (int i ) /*哲学家进程*/ while (true) P(chopsticki); P(chopstick(i + 1) % 5); eating; /* 进餐 */ V(chopsticki); V(chopstick(i + 1) % 5); thinking; /* 思考 */ 用信号量解决哲学家进餐问题 哲学家能顺利地吃到饭吗 打磕睡的理发师问题 理发店有一名理发师，一把理发椅，还有N把供等 候理发的顾客坐的普通椅子。如果没有顾客到来 ，理发师就坐在理发椅上打磕睡。当顾客到来时 ，就唤醒理发师。如果顾客到来时理发师正在理 发，顾客就坐下来等待。如果N把椅子都坐满了 ，顾客就离开该理发店去别处理发。 用信号量解决打磕睡的理发师问题 void customer () /顾客进程 P(mutex); if (waiting = 1 i = n; i = i + 1) si = si -1; else /* 某些资源不能满足要求时*/ block(si.queue ) /*将进程投入第一个小于1的 信号量的等待队列si.queue */ ; AND信号量定义 AND信号量定义 Ssignal(s1,s2,sn) for (i = 1; i = n; i = i + 1) si = si +1; for ( 等待队列si.queue中的每个进程P) if ( 进程P通过Swait中的测试) /* 通过检查，即资源够用 */ wackup(p); /唤醒进程P； else /* 未通过检查，即资源不够用 */ 进程P继续等待； 用AND信号量解决哲学家进餐问题 semaphore chopstick5 =1,1,1,1,1; void philosopher ( int i ) /*哲学家进程*/ while (true) Swait(chopsticki, chopstick (i + 1) % 5); eat(); /* 进餐 */ Ssignal(chopsticki, chopstick(i + 1) % 5); think(); /* 思考 */ 管程机制 引入的原因： 信号灯机制虽然既方便又有效地解决了 进程同步问题，但要求访问临界资源的进 程自备同步操作wait(s)、signal(s)，使得大 量的同步操作分散在各个进程中，给进程 的管理带来不便，并会因同步操作使用不 当导致死锁。 Hoare和Hanson提出了管程的概念把分散 在各个进程中的与同一共享资源有关的同 步处理从各进程中抽出并集中起来。 一个管程定义了一个数据结构和能为 并发进程所执行（在该数据结构上） 的一组操作，这组操作能同步进程和 改变管程中的数据。 管程 = 数据结构 + 操作 + 对数据结构中变量的初始化 3.4管程的定义 管程的结构 条件变量 用管程实现进程同步，设置 两个同步操作原语 wait,signal 为了区别等待的原因，引入 条件变量condition 其形式为 var x,y:condition 条件变量置于wait和signal 之前，表示为 x.wait和 x.signal 例如：由于共享数据被占用 而使调用进程等待，该条 件变量的形式为notbusy; wait原语应改为notbusy.wait monitor_name=monitor variable declarations procedure P1(); procedure P2(); procedure Pn(); init code 管程的语法 利用管程解决生产者-消费者问题 monitor monitor_PC; char buffern; int nextin, nextout; int count; condition notfull, notempty; void put(char x); /*过程*/ if (count = n) cwait(notfull); buffernextin = x; nextin = (nextin + 1) % n; count = count + 1; csignal(notempty); void get(char x); /*过程*/ if (count = 0) cwait(notempty); x = buffernextout; nextout = (nextout + 1) % n; count = count - 1; csignal(notfull); /*管程体*/ nextin = 0; nextout = 0; count = 0; /*变量初始化*/ void producer() /* 生产者进程 */ char x; while (true) produce an char in x; monitor_PC.put(x); void consumer() /* 消费者进程 */ char x; while (true) monitor_PC.get(x); consume an x; 利用管程解决生产者-消费者问题 3.5 进程通信 信号灯作为进程同步和互斥工具是卓有 成效的。但作为通信工具就不够理想。 其原因为： 效率低一次只传一条消息。 通信对用户不透明。 因此必须引入高级通信工具，解决进 程之间大量的信息传递问题 进程通信的类型 共享存储器系统 消息传递系统 直接通信方式 间接通信方式 管道通信 进程通信中的几个问题 通信链路的建立方式 显示建立链路 隐式建立链路 通信方向 通信链路连接方式 通信链路的容量 数据格式 同步方式 阻塞方式 不阻塞方式 消息缓冲 申请消息缓冲区接收区接收进程A的消息队列 发送进程1接收进程A 接收进程B的消息队列接收区 接收进程B 互斥的原因：对于缓冲区（发送区、接收区）和消息队列，系统内所有进程是 共享的。系统内有多个发送进程，也有多个接收进程。例如，多个发送进程并 发执行，会引起消息队列的混乱。 半同步的原因：消息队列的长度，并不是固定的。多个队列的长度也不尽相同 接收进程A的消息队列 发送进程1 发送进程2 2个发送进程并发执行，可能引起混乱 头指针尾指针 1SEND(A)（发送消息）原语 n发送消息原语被进程用于把消息发送到存放消息 的缓冲区。A是原语的参数，表示发送区的地址。 n其工作原理是：首先调用“寻找目标进程的PCB”的 程序查找接收进程的PCB，如果接收进程存在，申 请一个存放消息的缓冲区，消息缓冲区为空时，接 收此消息的进程因等待此消息的到来而处于阻塞状 态，则唤醒此进程，并把消息的内容、发送原语的 进程名和消息等，复制到预先申请的存放消息的缓 冲区，且将存放消息的缓冲区连接到接收进程的 PCB上；如果接收进程不存在，则由系统给出一个“ 哑”回答；最后控制返回到发送消息的进程继续执行 ，或转入进程调度程序重新分配处理机。如果消息 缓冲区已满，则返回到非同步错误处理程序入口进 行特殊处理。如图所示。 有接收进程吗 缓冲区有空吗 申请缓冲区 接收进程在就绪态 唤醒接收进程 发送区内容缓冲区 返回 非同步错误处理 给出哑回答 有 有 否 无 无 是 发送消息过程流图 2READ（A）（读取消息） 原语 nREAD(A)原语用来读取消息。 n接收进程读取消息之前，在自己的空 间中确定一个接收区A。然后使用 READ(A)原语。 nA是接收进程提供的接收区开始地址。 如图所示。 图示 读取消息 返回本节目录 消息缓冲队列-示意图 消息缓冲队列-数据结构定义 /消息缓冲区定义 struct message_buffer char sender30; /*发送进程标识符*/ int size; /*消息长度*/ char text200; /*消息正文*/ struct message_buffer *next;/指向下一个消息缓冲区的指针 /PCB中有关通信的数据项 struct process_control struct message_buffer *mq; /*消息队列队首指针*/ semaphore mutex=1; /*消息队列互斥信号量，初值为1*/ semaphore sm=0; /*消息队列同步信号量，记录消息的个数.初值为0*/ /发送原语 char receiver30; struct message_buffer a; void send(receiver, a) struct message_buffer i; struct process_control j; getbuf(a.size, i); /*发送区a消息的长度申请一缓冲区i*/ i.sender = a.sender; i.size = a.size; i.text = a.text; i.next = NULL; getid(PCB_set, receiver, j); /*获得接收进程的进程标识符j*/ P(j.mutex); Insert(j.mq, i); /*将消息缓冲区i挂到的消息队列j.mq上*/ V(j.mutex); V(j.sm); 消息缓冲队列-发送原语 消息缓冲队列-接收原语 struct message_buffer b; void receive(b) struct message_buffer i; struct process_control j; j = internal_name(); /*接收进程的内部标识符*/ P(j.sm); P(j.mutex); remove(j.mq, i); /*从消息队列中摘下第一个消息缓冲区*/ V(j.mutex); b.sender = i.sender; b.size = i.size; b.text = i.text; 发送进程Send(m) begin 申请一个新消息缓冲区 P(mutex) 消息m新消息缓冲区 新消息缓冲区队列 V(mutex) V(SM) end 接收进程Receive(n) begin P(SM) P(mutex) 从队列中摘下消息n 将消息n拷贝到接收区 释放内容已取走的缓冲区 V mutex) end 设公用信号量mutex为互斥信号量，初值为1； SM为接收进程的私用信号量，表示等待接收的消息个数，初值为0。 邮箱通信机制 1、设Bufempty为进程Pa的私用信号量，Buffull为Pb的私用信号量 2、初始化：Bufempty=n；Buffull=0。 申请消息缓冲区接收区大小固定的邮箱 发送进程接收进程 不用考虑互斥的原因：邮箱是发送进程和接收进程私有的，系统内 其它进程不能访问。 同步的原因：发送时，要有空格；接收时，要有满格。 Pa：deposit(data) 局部变量x P(Bufempty) 选择一个空区Buf(x) dataBuf(x) Buf(x)置满标记 V(Buffull) 发送进程Pa接收进程Pb B：remove(data) 局部变量x P(Buffull) 选择一个空区Buf(x) data Buf(x) Buf(x)置空标记 V(Bufempty) 返回本节目录 客户服务器系统通信 常用的通信方式： 命名管道 套接字 远程过程调用 利用UNIX提供的系统调用pipe，可建立一条同步 通信管道。其格式为： pipe(fd) intfd2； 这里，fd1 为写入端，fd0为读出端。 n2. 示例 n例1： 用C语言编写一个程序，建立一个pipe， 同时父进程生成一个子进程，子进程向pipe中 写入一字符串，父进程从pipe中读出该字符串 。 n解： 程序如下： n#include stdio.h nmain() n n intx，fd2； n char buf30，s30； n pipe(fd)；/*创建管道*/ n while(x=fork()=-1)；/*创建子进程失败时，循环*/ n if(x=0) n n sprintf(buf，This is an examplen)