进程的同步与通信.

——操作系统设计系列讲座作者：蒋石竹部门：研发部硬件二室邮件地址：[e-mail]联系电话：82029090--3393进程的同步与通信授课提纲第一章进程的同步1.1进程同步的基本概念1.2进程同步的常用机制及案例分析1.3经典的进程同步问题第二章进程的通信2.1进程同步与进程通信的关系2.2进程通信的常用机制及案例分析第一章进程的同步1.1进程同步的基本概念1.2进程同步的常用机制及案例分析1.3经典的进程同步问题1.1.1进程同步的基本概念之一【概念一】：进程间可能存在的关系I.资源共享关系例1：打印机II.相互合作关系例1：缓冲区的读写1.1.2进程同步的基本概念之二【概念二】进程同步的主要任务使并发执行的诸进程之间能够有效地共享资源和互相合作，从而使程序的执行具有可再现性。1.1.3进程同步的基本概念之三【概念三】临界资源与临界区临界资源是一次仅允许一个进程使用的资源。对临界资源的访问应采取互斥方式，实现对资源的共享。每个进程中访问临界资源的那段代码称为临界区。保证每个进程互斥地进入自己的临界区，就可以实现它们对临界资源的互斥访问。1.1.4进程同步的基本概念之四【概念四】进程同步的四项原则I.空闲让进II.忙则等待III.有限等待IV.让权等待1.1.4进程同步的基本概念之四（续）repeatwhileturn!=idono_op;criticalsectionturn=j;remaindersectionuntilfalse;•特点：强制两个进程轮流地进入临界区，可以保证每次只允许一个进程进入临界区。•缺点：违反了“空闲让进”原则。同步算法一1.1.4进程同步的基本概念之四（续）varbooleanflag[n]repeatwhileflag[j]dono_opflag[i]=true;criticalsectionflag[i]=false;remaindersectionuntilfalse;•特点：遵循了“空闲让进”•缺点：违背了“忙则等待”同步算法二1.1.4进程同步的基本概念之四（续）repeatflag[i]=ture;whileflag[j]dono_opcriticalsectionflag[i]=falseremaindersectionUntilfalse;•特点：可以有效防止两个进程同时进入临界区。•缺点：违背“有空让进”和“有限等待”。同步算法三1.1.4进程同步的基本概念之四（续）repeatflag[i]=ture;turn=j;while(flag[j]andturn=j)dono_opcriticalsectionflag[i]=falseremaindersectionUntilfalse;特点：即保证了“忙则等待”，又实现了“空闲让进”同步算法四第一章进程的同步1.1进程同步的基本概念1.2进程同步的常用机制及案例分析1.3经典的进程同步问题1.2进程同步的常用机制I.整型信号量机制II.记录型信号量机制III.信号量集机制1.2.1整型信号量机制整型信号量被定义为一个整型量S。S的物理意义：资源数目或请求使用某一资源的进程的个数。S=0S等于可供并发进程使用的资源数S0|S|等于正在等待使用临界区的进程数目1.2.1整型信号量机制(续)对S的访问：两个原子的操作P操作和V操作P操作：wait(s)whiles=0dono_ops=s–1V操作：signal(s)s=s+1整型信号量的缺陷：违背“让权等待”原则。1.2.2记录型信号量机制记录型信号量：整型变量value+进程链表LP操作wait(S)varsemaphoreSbeginS.value=S.value–1ifS.value0thenblock(S,L)end1.2.2记录型信号量机制（续）V操作signal(S)varsemaphoreSbeginS.value=S.value+1;if(S.value=0)thenwakeup(S,L)end1.2.2记录型信号量机制——案例分析I.UCOS实现的记录型信号量i.信号量的创建ii.信号量的P操作iii.信号量的V操作II.OSE实现的记录型信号量i.信号量的创建ii.信号量的P操作iii.信号量的V操作1.2.3信号量集机制信号量集的提出源于下面的问题:•多个进程对多个临界资源的互斥访问•一个进程的一次任务的执行需要获得两个或两个以上的共享资源采用多个单一的信号量解决上面的问题容易出现死锁。1.2.3信号量集机制(续)AND型信号量集：对若干个临界资源的分配采取原子操作方式。一次性全部获得一次性全部释放1.2.3信号量集机制(续)AND信号量集的P操作swait(S1,S2,…,Sn)ifS1=1and…andSn=1thenfori=1tondoSi=Si–1endforelse阻塞当前任务，直到获得欠缺的资源全部备齐endif1.2.3信号量集机制(续)AND信号量集的V操作Ssignal(S1,S2,…,Sn)fori=1tondoSi=Si+1endfor解除阻塞任务队列中可获得所需全部资源的任务的阻塞状态1.2.3信号量集机制案例分析Linux的信号量集的介绍第一章进程的同步1.1进程同步的基本概念1.2进程同步的常用机制及案例分析1.3经典的进程同步问题1.3经典的进程同步问题I.生产者—消费者问题II.读者—写者问题1.3.1生产者-消费者问题i.问题的描述；ii.利用记录型信号量的解决方案；iii.利用AND信号量集的解决方案；1.3.2读者-写者问题i.问题的描述；ii.利用记录型信号量的解决方案；授课提纲第一章进程的同步1.1进程同步的基本概念1.2进程同步的常用机制及案例分析1.3经典的进程同步问题第二章进程的通信2.1进程同步与进程通信的关系2.2进程通信的常用机制及案例分析第二章进程的通信2.1进程同步与进程通信的关系2.2进程通信的常用机制及案例分析2.1进程同步与进程通信的关系进程通信分为低级通信和高级通信。低级通信：进程之间仅进行控制信息的交换。高级通信：用户可以直接利用操作系统所提供的一组通信命令，高效地传送大量的数据。进程同步属于低级通信。第二章进程的通信2.1进程同步与进程通信的关系2.2进程通信的常用机制及案例分析2.2进程通信的常用机制I.共享存储器系统II.消息传递系统III.管道通信2.2.1共享存储器系统相互通信的进程通过共享数据结构和存储区进行通信。i.共享数据结构ii.共享存储区2.2.1共享存储器系统—案例分析Linux的共享内存机制介绍2.2.2消息传递系统进程间的数据交换以消息为单位进行。程序员直接利用系统提供的一组通信命令来实现通信。因其实现方法不同，可分为：i.直接通信方式（消息缓冲机制）ii.间接通信方式（信箱通信机制）2.2.2.1直接通信方式•关键数据结构•发送原语•接收原语•案例分析2.2.2.1直接通信方式—关键数据结构•消息缓冲区typedefmessagebuffer=recordsender；发送者进程标识符size；消息长度text；详细征文next；指向下一个消息缓冲区的指针end2.2.2.1直接通信方式—关键数据结构续•PCB中有关通信的数据项typedefPCB=record…mq；消息队列首指针mutex；消息队列互斥信号量sm；消息队列资源信号量…end2.2.2.1直接通信方式—发送原语proceduresend(receiver,a)begingetbuf(a.size,i);i.sender=a.sender;i.size=a.size;i.text=a.text;i.next=0;2.2.2.1直接通信方式—发送原语(续)getid(PCBset,receiver,j);wait(j.mutex);insert(j.mq,i);signal(j.mutex);signal(j.sm);end2.2.2.1直接通信方式—接收原语procedurereceive(b)beginj=internalname;wait(j.sm);wait(j.mutex);remove(j.mq,I);signal(j.mutex);2.2.2.1直接通信方式—接收原语（续）b.sender=i.sender;b.size=i.size;b.text=i.text;end2.2.2.1直接通信方式—案例分析OSE的Signal通信机制介绍2.2.2.2间接通信方式•信箱的组成•发送过程•接收过程•信箱的分类•案例分析2.2.2.2间接通信方式—信箱的组成•信箱头–信箱的控制信息。根据不同的信箱机制的实现，信箱头包含的内容不同。•信箱体–若干个抽屉，每个抽屉可以存放一封信2.2.2.2间接通信方式—发送过程send（N，M）：把信件M送到指定的信箱N中步骤：a.查找指定信箱N；b.若信箱未满，则把信件M送入信箱且释放“等信件”者；c.若信箱已满置发送信件进程为“等信箱”状态；2.2.2.2间接通信方式—接收过程receive（N，X）：从指定信箱N中取出一封信，存放到指定的地址X中步骤：a.查找指定信箱N；b.若信箱中有信，则取出一封信存于X中且释放“等信箱”者；c.若信箱中无信件则置接收信件进程“等信件”状态；2.2.2.2间接通信方式—信箱的分类•私用信箱•公用信箱•共享信箱2.2.2.2间接通信方式—案例分析VxWorks的MessageQueue通信机制介绍2.2.3管道通信I.管道通信的定义II.字符流方式的特点III.如何协调通信IV.案例分析2.2.3.1管道通信的定义也称共享文件方式，基于文件系统，利用一个打开的共享文件连接两个相互通信的进程，文件作为缓冲传输介质。发送进程接收进程字符流方式写入读出先进先出顺序2.2.3.2字符流方式的特点•发送进程可以源源不断的从pipe一端写入数据流，在规定的pipe文件的最大长度（如4096字节）范围内，每次写入的信息长度是可变的•接收进程在需要时可以从pipe的另一端读出数据，读出单位长度也是可变的2.2.3.3如何协调通信•互斥：一个进程正在对管道进行读/写操作时，另一进程必须等待。•同步：当写进程把一定数量的数据写入管道后，便去睡眠等待，直到读进程取走数据将其唤醒；当读进程读一空pipe，也应睡眠等待，直至写进程将数据写入管道，才将其唤醒。•对方是否存在：只有确定对方已存在时，才能进行管道通信，否则会造成因对方不存在而无限期等待。2.2.3.4管道通信—案例分析Linux的管道机制介绍授课提纲第一章进程的同步1.1进程同步的基本概念1.2进程同步的常用机制及案例分析1.3经典的进程同步问题第二章进程的通信2.1进程同步与进程通信的关系2.2进程通信的常用机制及案例分析谢谢！