操作系统课件进程同步与通信
操作系统第4章 进程 同步与通信本章主要内容:4-1 进程间的相互作用 4-2 进程通信 4-3 死锁 4-4 Linux进程间通信4.1 进程间的相互作用4-1-1 进程间的联系资源共享关系 相互合作关系 § 临界资源是一种多个进程访问的资源。其属性是:访问临界资 源的进程必须互斥得访问它,也就是说,同一时刻只允许一个 进程访问的资源叫临界资源 § 临界区 不论是硬件临界资源,还是软件临界资源,多个进程 必须互斥地对它进行访问。我们把在每个进程中访问临界资源 的那段代码称为临界区(critical section)4.1 进程间的相互作用§ 同步机制应遵循的准则空闲让进、忙则等待、有限等待、让权等待 4-1-2 利用软件方法解决进程互斥问题 § 算法1设置一个公用整型变量turn,用于指示被允许进入临界 区的进程的编号算法描述如下: while (1)while (turn!=1)no-op; critical sectionturn=2;算法不能保证实现“空闲让进”的准则§ 算法2设置一个数组,使其中每个元素的初值为0,表示所有进程都未进入 临界区,在每一个进程访问临界资源之前,先去查看一下临界资源是否 正被访问。若正被访问,该进程需等待;否则进入自己的临界区 算法描述如下: int flag2=0,0;P1:while (1)while (flag1)no-op;flag0=1;critical sectionflag0=0;4.1 进程间的相互作用违背了“忙则等待”的准则§ 算法3使要进入临界区的进程先设置其要求进入的标志,然后,再去查看其 他进程的标志算法描述如下:int flag2=0,0; P1:while (1)flag0=1;while (flag1) no-op;critical sectionflag0=0;4.1 进程间的相互作用违背了“空闲让进”和“有限等待”准则§ 算法4(正确算法)为每个进程设置了相应的标志为flag;还设置了一个turn变量,用 于指示允许进入临界区的进程编号算法描述如下: int flag2=0,0; P1:while (1)flag0=1; turn=2;while (flag1critical sectionflag0=0;保证了“忙则等待”,又实现了“空闲让进”4.1 进程间的相互作用4.1 进程间的相互作用4-1-3 利用硬件方法解决进程互斥问题 § 利用Test-and-Set指令实现互斥Test-and-Set指令为:int TS(static int lock)int TS=lock;lock=1;return(TS);用TS指令实现进程互斥的循环描述为:while (1)while (TS(lock) do no-op;critical sectionlock=0; 4.1 进程间的相互作用§利用Swap指令实现进程互斥Swap指令称为交换指令,描述为:void Swap(static int a,b)int temp;temp=a;a=b;b=temp;利用Swap指令实现进程互斥的循环可描述为:while (1)key=1;doSwap(lock,key);while(key);critical sectionlock=0;4.1 进程间的相互作用4-4-4 信号量机制信号量机制是一种卓有成效的进程同步工具 § 记录型信号量机制在信号量机制中,除了需要一个用于代表资源数目的整型 变量value外,还有一个进程链表L,用于链接所有等待该信号 量代表资源的进程 Ø 记录型数据结构描述 typedef struct int value;list of process *L;semaphore; 4.1 进程间的相互作用Ø 对信号量的操作信号量除初始化外,仅能通过两个标准的原子操作wait(s)和 signal(s)来访问。这两个操作很长时间以来被称为P、V操作。当一个进程在修改某信号量时,没有其他进程可以同时对该信号量进 行修改。wait操作 void wait(static semaphore s) s.value-;if (s.value0)block(s.L); singal操作void signal(static semaphore s) s.value+;if (s.value0)wackup(s.L); 4.1 进程间的相互作用Ø 利用信号量实现进程互斥的过程描述为使多个进程互斥地访问某个临界资源,只需为该资源设置一个信号量 ,并设其初始值为1,此时的信号量可以称为“互斥信号量”。semaphore mutex=1; void procedure1() while (1)wait(mutex);critical sectionsignal(mutex); void procedure2() while (1)wait(mutex);critical sectionsignal(mutex); main() cobegin procedure1();procedure2(); 4.1 进程间的相互作用Ø 利用信号量来描述程序或语句之间的前趋关系方法:一条边一个信号量(信号量初值为0); wait以该节点为终点所 有边的信号量,执行该节点,signal以该节点为始点所有边的信号量例:有6个语句的前驱图main() semaphore a=b=c=d=e=f=g=0;cobegin T1;signal(a);signal(b);wait(a);T2;signal(c);signal(d);wait(b);T3;signal(e);wait(c);T4;signal(f);wait(d);T5;signal(g);wait(e);wait(f);wait(g);T6; 4.1 进程间的相互作用§ 信号量集机制 Ø AND型信号量集机制对若干个临界资源的分配采取原子操作方式,要么全部分配到进程,要 么一个也不分配Swait(Simultaneous Wait)操作Swait(S1,S2,Sn)if (S11i0 R.wait;rc+;R.signal; entry end_readrc-;if rc=0 w.signal; entry start_write wc+;if( rc>0| wc>1 )W.wait; entry end_write wc-;if(wc>0) W.signal;else R.signal; rc=wc=0;4.2 进程通信4-2-1 基本概念 进程通信是指进程之间的信息交换进程的互斥和同步可归结为低级通信高级进程通信是指用户可直接利用操作系统所提供的 一组通信命令高效地传送大量数据的一种通信方式 4-2-2 进程通信的类型 Ø 共享存储器系统在共享存储器系统中,相互通信的进程共享某些数据结 构或共享存储区,进程之间能够通过它们进行通信基于共享数据结构的通信方式 基于共享存储区的通信方式。4.2 进程通信Ø 消息传递系统 进程间的数据交换以消息为单位,程序员直接利用系统提 供的一组通信命令(原语)来实现通信直接通信方式 间接通信方式 (信箱通信方式) Ø 管道通信所谓管道是指用于连接一个读进程和一个写进程以实现 它们之间通信的共享文件,又称为pipe文件。为了协调双方的通信,管道通信机制必须提供以下三方 面的协调能力:互斥、同步、双方是否存在4.2 进程通信4-3-3直接通信和间接通信Ø 直接通信方式直接通信方式是指发送进程利用操作系统所提供的发送 命令直接把消息发送给目标进程。系统提供下述两条通信原语 :send(receiver,message);receive(sender,message); 利用直接进程通信原语来解决生产者-消费者问题4.2 进程通信void producer()while (1)produce an item in nextp;send(consumer,nextp);void consumer()while (1)receive(producer,nextc);consume the item in nextc;main()cobegin producer();consumer();4.2 进程通信Ø 间接通信方式所谓间接通信方式,是指进程之间的通信需要通过作为某种共享 数据结构的实体,该实体用来暂存发送进程发送给目标进程的消息;接 收进程则从该实体中取出对方发送给自己的消息。通常把这种中间实体 称为信箱 信箱可由操作系统创建,也可由用户进程创建。可把信箱分为以 下三类:私有信箱、共有信箱、共享信箱在利用信箱通信时,在发送进程和接收进程之间存在着下述四种 关系:一对一关系、多对一关系、一对多关系、多对多关系 4-3-4 消息缓冲队列通信机制 在这种通信机制中,发送进程利用send原语将消息直接发送给接收 进程;接收进程则利用receive原语接收消息 4.2 进程通信§ 消息缓冲队列通信机制中的数据结构 Ø 消息缓冲区消息缓冲区数据结构描述为: struct message_buffersender; / 发送者进程标识符size; / 消息长度text; / 消息正文next; / 指向下一个消息缓冲区的指针; Ø PCB中有关通信的数据项在PCB中应增加的数据项可描述为:struct processcontrol_blockmq; / 消息队列队首指针mutex; / 消息队列互斥信号量sm; / 消息队列资源信号量; 4.2 进程通信§ 发送原语 void send(receiver,a)getbuf(a.size,i); / 根据a.size申请缓冲区i.sender=a.sender; / 将发送区a中的信息复制到消息缓冲区i中i.size=a.size;i.text=atext;i.next=0;getid(PCB set,receiver,j); / 获得接收进程内部标识符jwait(j.mutex);insert(j.mq,i); / 将消息缓冲区插入消息队列signal(j.mutex);signal(j.sm);4.2 进程通信§接收原语 void receive(b) j=internal name; / j为接收进程的内部标识wait(j.sm);wait(j.mutex);remove(j.mq,i); / 将消息队列中第一个消息移出signal(j.mutex);b.sender=i.sender; / 把消息缓冲区i中的信息复制到接 收区bb.size=i.size;b.next=i.next; 4.3 死锁4-3-1 产生死锁的原因和必要条件 § 死锁的定义 所谓死锁是指在多道程序系统中,一组进程中的每 一个进程均无限期地等待被该组进程中的另一个进程所占有 且永远不会释放的资源;这种现象称系统处于死锁状态,简 称死锁。处于死锁状态的进程称为死锁进程 § 产生死锁的原因 Ø 竞争资源多个进程所共享的资源不足,引起它们对资源的竞争而 产生死锁竞争可剥夺和非剥夺性资源 竞争非剥夺性资源 竞争临时性资源 4.3 死锁Ø 进程推进顺序不当引起死锁 进程运行过程