《分布式操作系统》PPT课件.ppt

第二章 进程管理及并发控制和同步 第1节进程的定义和特征第2节进程的状态和进程控制块第3节进程控制第4节进程的同步与互斥第5节并发执行的描述方式第6节基于共享变量的同步操作原理第7节基于消息传递的同步操作原语第8节进程调度 进程的定义和特征 1 进程的定义 2 进程的特征 3 进程的结构 进程的定义 进程 process 或任务 task 这一术语是在六十年代初期 首先在麻省理工学院 MIT 的MULTICS系统和IBM公司的CTSS 360系统中引入的 其后有许多人对进程下过各式各样的定义 下面列举几种比较能反映进程实质的定义 进程的定义 进程是程序的一次执行 亦即进程是在指定的内存区域中的一组指令序列的执行过程 进程 或任务task 是可以和别的计算并发 concurrent 执行的计算 进程可以定义为一个数据结构和能在其上进行操作的一个程序 进程是程序在一个数据集合上运行的过程 它是系统进行资源分配和调度的一个独立单位 进程 process 是一个具有独立功能的程序关于相关的数据集在处理机上的执行过程 进程的特征 进程具有顺序性动态性并发性独立性和异步性等特征 进程的最基本的特征是并发性 顺序性 一个进程的顺序性是指每个进程在顺序处理机上的执行是严格按次序进行的 即只有当其中的一个操作结束后 才能开始其后续操作 动态性 进程的动态性是指它是程序的一次执行过程 表现为它是由 创建 create 而产生 由调度程序 调度 而运行 因 等待事件 而阻塞 最后 由 撤消 destroy 而消亡 可见 进程是有一定生命期的 是动态地产生 运行和消亡的 并发性 进程的并发性是指多个进程可以同时在一个系统中并发地执行 独立性 进程的独立性是指它可以作为系统进行资源分配和调度的独立单位 异步性 进程的异步性是指系统中的活动的进程总是按照各自独立的 不可预测的速度运行 进程的结构 为了描述进程的运动变化过程并使之能独立地运行 应该为每个进程配置一个进程控制块 processcontrolblock简记为PCB 进程的结构 三部分所组成 一个程序段相应的数据段一个进程控制块在UNIX系统中 把这三部分统称为进程映像 image 而将进程定义为 进程映像的执行 进程的状态 就绪状态 Ready 运行状态 Running 阻塞状态 Blocked 进程的状态 进程的状态 UNIX 进程控制块 进程标识符 Identification 进程的当前状态 Status 处理机状态保护区 进程的起始地址 资源清单 进程优先数 队列指针 pointer 或链接字 link 进程族的联系 计账信息 为了对于进程进行控制 操作系统内必须设置一个机构 它具有上述进程控制及进程通讯和资源管理等功能 这样的机构称为操作系统的内核 Kernel 原语 所谓原语 Primitive 是机器指令的延伸 它由若干条指令组成 用以完成特定功能的一段程序 为了保证原语操作的正确性 原语在执行期间是原子的 亦即原语在执行期间是不可分割的 原语 创建原语 CreatePrimitive 悬挂原语 SuspendPrimitive 激活原语 ActivatePrimitive 阻塞原语 BlockPrimitive 唤醒原语 WakeupPrimitive 撤消原语 DestroyPrimitive 对进程之间共享资源的控制必须满足下列要求 安全性 safety 活动性 liveness 公正性 fairness 安全性 safety 在任意一个给定时刻只允许至多一个进程使用一个共享资源 不允许两个及两个以上进程同时使用同样的共享资源 否则 进程对共享资源操作的结果往往是破坏性的 活动性 liveness 活动性表现为两个方面 一方面任意一个进程在使用共享资源时 必须在有限时间内释放 不能无限期地占用而导致其它进程永远无法使用 另一方面当某个进程欲使用共享资源时 则应在有限时间内达到目的 而不应该互相阻止导致彼此永远都不能使用 公正性 fairness 对进程使用共享资源的次序不作不公正的规定 当某个进程欲使用共享资源时 只要其它进程不在使用该共享资源 就应该允许该进程使用 并且任意一个要求使用共享资源的进程不能无限期地等待 总应该在某个公正的时间界限内获得该资源 第4节进程的同步与互斥 进程之间常常相互作用 并存在某种彼此依赖或互相制约的关系这些关系按其性质可分为同步 synchronization 和互斥 mutualexclusion 关系 进程的同步 一进程运行到某点时 要求另一伙伴进程它提供信息 在未得到这一信息时 该进程等待 直至收到这一信息后 才能继续执行 它们彼此都清楚对方的存在及作用 而且每一进程还可能直接依赖于本组进程中其它成员所产生 或所提供 的数据 这是进程间的一种直接交互关系 表现了进程间协同工作的特性 因此称为进程间的同步关系 临界资源 并发进程可以共享系统中的各种资源 但系统中的有些资源具有一次仅允许一个进程所使用的属性 我们称这类资源为临界资源 criticalresources 进程的互斥 若一进程在使用临界资源时 则其它欲占用者必须等待 仅当使用者释放后 等待的进程才可使用它 这就导致了若干进程因竞争临界资源而不得互斥地执行的情况 进程间的这种现象就称为进程的互斥 临界区 在操作系统中把访问临界资源的那段程序称为临界段或临界区 criticalsection 临界段问题实质上是一个互斥问题 临界段应遵循下面的原则 当有多个进程都希望进入它们的临界段时 它们不应相互封锁 而应在有限时间内让其中之一进入临界段 每次至多只有一个进程进入临界段中 当某一进程已进入临界段 其它试图进入该临界段的进程必须等待 位于临界段中的进程只能在其中逗留有限的时间一旦它离开临界段 则应允许某个等待进入临界段的进程进入其中 同步机制 进程的同步是通过同步机制实现的 同步机制主要有两个作用 第一 它能够推迟一个进程的执行直至给定的条件成立 第二 它可用来保证一个语句序列是一个不可分割的操作 1 忙等待 busywaiting 为了唤醒一个条件 进程给一个共享变量置值 为了等待那个条件 进程反复地测试那个共享变量直至获得所需要的值 由于等待条件的进程必须反复地测试那个共享变量 因此称采用这种方式阻塞进程执行的技术为忙等待 计算机硬件配置指令 测试与设置 TestandSet简记为TS functionTest and Set vartarget boolean boolean Test and Set target target TRUE end 利用测试与设置的同步 lock mutex while TS mutex unlock mutex mutex FALSE 计算机硬件配置指令 对换 Swap 指令该对换指令对换内存两个单元的内容 procedureSwap vara b boolean vartemp boolean begintemp a a b b tempend 利用对换指令的同步 lock mutex key TRUE repeatSwap mutex key untilkey FALSE unlock mutex mutex FALSE Dekker的软件解 1968 intturn booleanflag 2 process i inti while TRUE compute flag i TRUE while flag i 1 mod2 if turn i continue flag i FALSE Dekker的软件解 while turn i gototry critical section turn turn 1 mod2 flag i FALSE turn 0 flag 0 FALSE flag 1 FALSE Process 0 ANDprocess 1 Peterson的软件解 198l includeprototypes h defineFALSE0 defineTRUE1 defineN2 numberofprocess intturn whoseturnisit intinterested N allvaluesinitially0 FALSE voldenter region intprocess process whoisentering 0or1 intother other 1 process interested process TRUE turn process while turn process nullstatement voidleave region intprocess process whoisleaving 0or1 interested process FALSE indicatedeparturefromcriticalregion intturn booleanflag 2 process i inti while TRUE compute flag i TRUE while flag i 1mod2 turn i 1mod2 critical section turn turn 1 mod2 flag i FALSE turn 0 flag 0 FALSE flag 1 FALSE Process 0 ANDprocess 1 2 信号量及其P V操作 信号量 semaphore Dijkstra 1963 是一个整型变量 与其相关的两个操作是P V操作 它是最早提出的同步操作原话 P V操作的名称源于荷兰字Prolagen 试图降低 和Verhogen 升起 信号量及其P V操作 定义2 1一个信号量s是一个非负整型变量 它仅仅可以由下列的两个不可分的 即原子的 访问例程之一来测试和修改 P s 和V s 操作 P s whiles 0do s s 1 V s s s 1主要缺点是忙等待 P s 操作 typesemaphore recordvalue integer L listofprocess end 信号量的value初值表示系统中某类资源的数目 因此 这类信号量又称资源信号量 P s 操作 P semaphoreS S value S value l IfS value 0then阻塞该进程 并把它置入S L等待队列中 操作系统重新调度 else该进程继续执行 V s 操作 V semaphoreS S value S value l IfS value 0then从S L等待队列中取出一进程 将其状态改为 就绪 并且放入就绪队列 else该进程继续执行 互斥问题 为了解决互斥问题 每个临界段前后分别放一个P V操作 它们都操作在同一信号量上 所有互斥的临界段利用相同的信号量 且该信号量的初值为1 programmutex example varmutex semaphoreinitial 1 processP1 1oopP mutex 临界段 V mutex 非临界段 endend end processP2 1oopP mutex 临界段 V mutex 非临界段 endend programsynch example vars1 s2 semaphoreinitial 0 0 processP1 1oopsend message V s1 P s2 end end end processP2 1oopP s1 receive message V s2 end end 有界缓冲区 生产者和消费者 问题 假设一个系统包含两个进程 其中之一产生信息 称之为生产者进程 producerprocess 另一个使用生产者进程所产生的信息 称之为消费者进程 consumerprocess 两个进程可以交换所需信息 使生产者进程从一个空缓冲池 bufferpool 中得到一个空缓冲区 将信息填写其中 然后再把它放到满缓冲池之中 有界缓冲区 生产者和消费者 问题 消费者进程从满缓冲池内取出满缓冲区 从满缓冲区复制出信息 然后再把它放到空缓冲池之中 以便再循环利用 我们不喜欢给生产者和消费者进程以无限个缓冲区 而只分配N个缓冲区给它们以交换信息 下列程序表示了生产者和消费者进程的程序 有界缓冲区 生产者和消费者 问题 Semaphores 1 Semaphorefull 0 Semaphoreempty N buf typebuffer N producer ANDconsumer produrcer buf type next here while TRUE produce item next P empty P s here obtain empty V s copy buffer next here P s release here full V s V full consumer buf type next here while TRUE P full P s here obtain full V s copy buffer here next P s release here empty V s V empty consume item next 读者和作者 Readers Writers 问题 Courtois Heymans和Parnas在1971年提出了另一个有趣的同步问题 即读者和作者问题 假设一个资源被两类不同类型的进程集合之间共享 一类进程称为读者 而另一类进程称为作者 一个读者进程可以和任何其它读者进程共享该资源 但是不和任何一个作者进程共享 每当一个作者进程需要访问这个资源时 要求互斥访问 这种情景非常类似于一个文件被一组进程所共享 读者和作者 Readers Writers 问题 为了管理共享资源 可以实施若干不同的策略 通常有弱读者进程优先 强读者进程优先和作者进程优先三种策略 例如 每当任何一个读者进程访问该共享资源时 则任何一个作者进程请求访问该共享资源必须等待 直到无活动的读者进程为止 该共享资源变为可用 这种弱读者进程优先的策略其实现算法请见 弱读者进程优先策略 resource type resource intread count 0 读者计数器semaphores 1 semaphorewrite block 1 第一个读者和所有作者执行P write block 最后一个读者离开时执行V write block read while TRUE other computing P s read count read count 1 if read count 1 P write block V s access resource P s read count read count 1 if read count 0 V write block V s writer while TRUE other computing P write block access resource V write block Therecouldbemanyreadersandmanywriters reader ANDwriter 作者进程优先策略 resource type resource intread count 0write count 0 semaphores1 1 s2 1 semaphoreread block 1 semaphorewrite pending 1 semaphorewrite block 1 第一个作者阻塞在read block上随后读者阻塞在write pending上 read while TRUE other computing P write pending P read block P s1 read count read count 1 if read count 1 P write block V s1 V read block V write pending access resource P s1 read count read count 1 if read count 0 V write block V s1 writer while TRUE other computing P s2 write count write count 1 if write count 1 P read block V s2 P write block access resource V write block P s2 write count write count 1 if write count 0 V read block V s2 Therecouldbemanyreadersandmanywriters reader ANDwriter AND同步机制 在许多并行程序中 进程们必须在某个条件集合上而不是仅在单个条件上同步 下面的哲学家用餐问题就是一个很好的例子 哲学家用餐问题 Dijkstra引入了五个哲学家问题 假定五个哲学家围住在餐桌旁每人前面放了一个盘子 在相邻的两个盘子之间放了一只筷子 当哲学家在思考时 他不使用盘子和筷子 但是当哲学家决定吃时 他必须拿到他面前盘子的左右两只筷子才能吃 我们规定在一个给定的时刻 哲学家只能拿一只筷子 哲学家们就这样交替地思考和吃 是一个典型的信号量解 不幸地 这个解是不安全的 因为当所有的同时决定吃时 出现死锁 semaphorefork 5 philosopher i inti while TRUE Thinking P fork i P fork i 1 mod5 eat V fork i 1 mod5 V fork i 同时P simultaneousP 操作 假定一个P操作能够保证得到在一个集合中的所有信号量或者没有任一个 我们称这个P操作为同时P simultaneousP 操作 同时P操作具有形式为 Psimultaneous S1 S2 Sn 同时V操作具有形式为 Vsimultaneous S1 S2 Sn Psimultaneous S1 S2 Sn if S1 1 S2 1 Sn 1 thenfori 1tondoSi Si 1 endforelse把进程放在首先找到Si 1相联的等待队列中 并置该进程的程序计数器为此操作的开始 endif Vsimultaneous S1 S2 Sn fori 1tondoSi Si 1 把与Si相联的等待队列中所有的进程移到就绪队列 endfor 当n 2时Psimultaneous的一种实现 Sharedvariables intS1 R1 semaphoremutex semaphoreblock Initializesemaphores mutex 1 block 0 P S R P mutex S1 S1 1 R1 R1 1 if S1 0 R1 0 V mutex P block elseV mutex V S R P mutex S1 S1 1 R1 R1 1 if S1 0 R1 0 V block V mutex Psimultaneous S1 t1 d1 S2 t2 d2 Sn tn dn if S1 t1 S2 t2 Sn tn thenfori 1tondoSi Si di endforelse把进程放在首先找到Si ti相联的等待队列中 并置该进程的程序计数器为此操作的开始 endif Vsimultaneous S1 d1 S2 d2 Sn dn fori 1tondoSi Si di 把与Si相联的等待队列中所有的进程移到就绪队列 endfor 条件临界域 虽然信号量基本上可用于解决差不多任何类型的同步问题 但P V操作是非结构化的原语 因此在使用它们时极易出错 执行临界段之前必须先执行一个P操作 在退出临界段时再执行一个V操作 在相同的信号量上 忽略一个P或V操作或者意外地让P操作在一个信号量上而让V操作在另一个信号量上就会乱套 在这种情况下 互斥执行的特性不再会得到保证 条件临界域 此外 在运用信号量时 程序员可能会忘记将所有涉及到共享变量的语句包括在临界段中 显然 这也可能破坏临界段所需要的互斥执行 使用信号量的另一困难是条件同步互斥都是使用相同形式的原语对偶来编码的 从而难以弄清一对给定的P V操作的目的 因为互斥和条件同步是不同的概念 它们应该有不同的表示形式 条件临界域 条件临界域 conditionalcriticalregion Hoare 1972 BrinchHansen 1972 通过提供结构化的表示法来描述同步而弥补了上述不足 共享变量明显地归纳为一组 并且予以命名 称为资源resource 每个共享变量至多只处于一个resource中且只能在命名该resource的条件临界域 简记为CCR 语句中存取 条件临界域 一个包含变量v1 v2 vn的resourceR说明为resourceR v1 v2 vn R中的变量只能由命名R的CCR语句存取 这种语句形如 regionRwhenBdoS 其中 B是一个布尔表达式 S是一组语句 局部于正在执行的进程的局部变量也可以出现在CCR语句中 互斥是通过保证执行不同的CCR语句来实现的 条件临界域 即每个命名相同resource的语句是不重迭的 条件同步是通过CCR语句中明显地给出的布尔条件加以保证 CCR语句阻塞执行它的进程直至B为true 然后执行s 计算B和执行S是不可由另外命名相同resource的一些CCR语句所中断的 因此 当开始执行S时 B保证为true 这种机制通常假定是公正的 一个处于等待条件B的进程最终会由于B为true而得以继续执行 条件临界域 programOPSYS typebuffer T recordslots array 0 N 1 ofT head tail 0 N 1initial 0 0 size 0 Ninitial 0 end varinpbuff buffer cardimage outbuff buffer lineimage resourceib inpbuff ob outbuff 条件临界域 processreader varcard cardimage loopreadcardfromcardreader regionibwheninpbuff size Ndoinpbuff slots inpbuff tail card inpbuff size inpbuff size 1 inpbuff tail inpbuff tail 1 modNendendend 条件临界域 processexecuter varcard cardimage line lineimage loopregionibwheninpbuff size 0docard inpbuff slots inpbuff head inpbuff size inpbuff size 1 inpbuff head inpbuff head 1 modNend processcardandgenerateline 条件临界域 regionobwhenoutbuff size Ndooutbuff slots outbuff tail line outbuff size outbuff size 1 outbuff tail outbuff tail 1 modNendendend 条件临界域 processprinter varline lineimage loopregionobwhenoutbuff size 0doline outbuff slots outbuff head outbuff size outbuff size 1 outbuff head outbuff head 1 modNendendend end 条件临界域 虽然CCR有许多优点 但实现起来代价过大 因为CCR语句中的条件可以包含对局部变量的访问 而且每个进程都必须计算它自己的条件 在一个含有多道程序的处理机上 这种计算的结果导致若干内容的切换 频繁地保存和恢复进程状态 其中的许多工作可能是无效的 因为活跃的进程仍然可能发现相应的条件为false 若每个进程都在它自己的处理机上运行且内存是共享的 则CCR语句很容易利用忙等待技术实现 条件临界域 Edison语言 BrinchHansen 1981 包含有CCR语句 该语言是专为多处理机系统设计的 CCR语句的一些变种也在DP BrinchHansen 1978 和Argue Liskov Scheifler 1982 中使用了 管程 monitor 管程 monitor Dijkstra 1968 BrinchHansen 1973 Hoare 1974 是指一组公共数据同与其有关的操作的集合 只有引用管程中的操作才能访问管程中的数据 一个进程引用管程中操作时 只有在管程中的各操作均不处于活跃状态时才被响应 当管程中一个操作已执行完毕或在执行中处于等待状态时 它就不是活跃状态 管程将公共数据同与其有关的操作集中在一起 使得并发程序容易理解 也易于保证程序的正确性 因此 管程是一种结构化的同步机制 管程 monitor 定义 Hoare的定义 管程是一个抽象数据类型 在任何给定的时刻仅仅一个进程能够执行管程内的过程 管程 monitor 局部于管程的变量仅能被该管程中的过程所访问 一个管程与外部世界的通信是通过其所含过程的参数进行的 管程本身是一个静态的被动的对象 一个进程执行管程的唯一方式是通过调用管程中的过程来体现的 执行给定管程中的过程保证是互斥进行的 这确保了局部于该管程的变量 即该管程首部说明的量 是决不能并发存取的 条件变量 conditionvariable 条件变量 conditionvariable 用于推迟管程中正在执行的进程 它只能在管程中说明 定义在条件变量上的两个操作是signal和wait 如果cond是一条件变量 那么执行cond wait将引起引用者阻塞在cond上 并撤消它的互斥控制 条件变量 conditionvariable 执行cond signal的工作过程如下 若没有进程阻塞在cond上 则该引用者继续执行 否则 该引用者暂时被挂起 并且重新激活阻塞在cond上的一个进程 仅当该管程中不存在其它正在执行的进程时 才允许由于signal操作而挂起的进程继续执行 有界缓冲区管程 typebuffer T monitor varslots array 0 N 1 ofT head tail 0 N 1 size 0 N notfull notempty condition 有界缓冲区管程 proceduredeposit p T beginifsize Nthennotfull wait slots tail p size size 1 tail tail 1 modN notempty signalend 有界缓冲区管程 procedurefetch varit T beginifsize 0thennotempty wait it slots head size size 1 head head 1 modN notfull signal end beginsize 0 head 0 tail 0 end 用管程技术编写的简单批处理操作系统 programOPSYS typebuffer T monitor varinpbuff buffer cardimage outbuff buff buffer lineimage processreader varcard cardimage 1oopreadcardfromcardreader callinpbuff deposit card endend 用管程技术编写的简单批处理操作系统 processexecuter varcard cardimage line lineimage 1oopcallinpbuff fetch card processcardandgenerateline calloutbuff deposit line endend 用管程技术编写的简单批处理操作系统 processprinter varline lineimage 1oopcalloutbuff fetch line printlineonlineprinter endend end 优先wait语句 有时程序设计者希望控制唤醒被推迟进程的次序 为此 可使用 优先wait 语句 cond wait p 它与cond wait的语义基本相同 主要差别在于阻塞在条件变量cond上的进程此时是按P的递增次序予以唤醒 管程 monitor 并发PASCAL是支持管程的第一个程序设计语言 该语言己被用于编写若干操作系统 例如Solo 一个单用户操作系统 Jobstream 处理PASCAL程序的一个批处理操作系统 以及一个实时处理控制系统 Modula Wirih 1977 也含有类似管程的模块 定序器和事件计数器SequencersandEventcounts 定义一个事件计数器 eventcount 是一个整型变量 初始值为0 它取值于一个严格单调增加的非负整数集合 一个事件计数器仅仅能够实施下列操作 advance E 过程advance E 用于宣告一个和E有关的事件的出现 它引起事件计数器E增加1 并且唤醒处在事件计数器E等待队列中的一个或多个进程 即E E 1 并且唤醒处在事件计数器E等待队列中的达到E当前值的一个或多个进程 事件计数器 read E 一个进程利用read E 来决定事件计数器E的值 它返回事件计数器E的当前值 即 return E await E v 一个进程调用await E v 将引起该进程在E v时被阻塞 即 ifE vthen将调用的进程放在于E相关的等待队列中 变成阻塞状态 调用进程调度程序 endif 定序器 定义一个定序器 sequencer 是一个整型变量 初始值为0 它取值于一个严格单调增加的非负整数集合 仅仅ticket T 能够应用到定序器T上 它导致定序器T增加并且返回定序器T增加前的值 对ticket的调用是原子的 即定序器T被用来在某个半序事件集合上放一个全序 定序器 一个定序器相应于刚抵达的顾客所拿到的服务号码 一个定序器的值是下一个将要取的号码 可以将定序器看成一个自动售票机 ticket操作对应于一个新来的顾客取一个唯一的服务号码 一个事件计数器可以看成是一个服务号码栈 它的当前值是服务号码栈顶值 一个await操作对应于一个顾客开始等待服务 一个advance操作对应于一个初始化服务 事件计数器被增加并且允许服务下一个顾客 进程 定序器 一个进程执行临界区的操作序列为await E ticket S 临界区 advance E 利用定序器和事件计数器实现P和V Structsemaphore intinitial value Initialvalueofthesemaphore eventcounte sequencert s 利用定序器和事件计数器实现P和V P s V s semaphores semaphores inti advance s e i ticket s t await s e i 1 s initial value eventcountin out sequencerPticket Cticket buffer array 0 N ofmessage producer consumer intt i 1 intu i 1 message m messagem while true while true m produce t ticket Pticket u ticket Cticket 一次一个生产者 一次一个消费者 await in t awit out u awit out t N 1 await in u 1 等待一个空缓冲区别 等待一个消息 buffer tmodN m m buffer umodN advance in advance out 信号一个满缓冲区及 信号一个满缓冲区 允许其它生产者 允许其它消费者 consume m 图 利用定序器和事件计数器实现生产者和消费者问题eventcountE sequencerT Pboth R S semaphoreR S intq r s q ticket T await E q r ticket R t s ticket S t advance E await R e r 1 R initial value await R e r 1 R initial value 图 利用定序器和事件计数器实现SimultaneousP 利用定序器和事件计数器实现P和V P s V s semaphores semaphores inti advance s e i ticket s t await s e i 1 s initial value eventcountin out sequencerPticket Cticket buffer array 0 N ofmessage producer consumer intt i 1 intu i 1 message m messagem while true while true m produce t ticket Pticket u ticket Cticket 一次一个生产者 一次一个消费者 await in t awit out u awit out t N 1 await in u 1 等待一个空缓冲区别 等待一个消息 buffer tmodN m m buffer umodN advance in advance out 信号一个满缓冲区及 信号一个满缓冲区 允许其它生产者 允许其它消费者 consume m 图 利用定序器和事件计数器实现生产者和消费者问题eventcountE sequencerT Pboth R S semaphoreR S intq r s q ticket T await E q r ticket R t s ticket S t advance E await R e r 1 R initial value await R e r 1 R initial value 图 利用定序器和事件计数器实现SimultaneousP 利用定序器和事件计数器实现P和V P s V s semaphores semaphores inti advance s e i ticket s t await s e i 1 s initial value eventcountin out sequencerPticket Cticket buffer array 0 N ofmessage producer consumer intt i 1 intu i 1 message m messagem while true while true m produce t ticket Pticket u ticket Cticket 一次一个生产者 一次一个消费者 await in t awit out u awit out t N 1 await in u 1 等待一个空缓冲区别 等待一个消息 buffer tmodN m m buffer umodN advance in advance out 信号一个满缓冲区及 信号一个满缓冲区 允许其它生产者 允许其它消费者 consume m 图 利用定序器和事件计数器实现生产者和消费者问题eventcountE sequencerT Pboth R S semaphoreR S intq r s q ticket T await E q r ticket R t s ticket S t advance E await R e r 1 R initial value await R e r 1 R initial value 图 利用定序器和事件计数器实现SimultaneousP 利用定序器和事件计数器实现P和V P s V s semaphores semaphores inti advance s e i ticket s t await s e i 1 s initial value eventcountin out sequencerPticket Cticket buffer array 0 N ofmessage producer consumer intt i 1 intu i 1 message m messagem while true while true m produce t ticket Pticket u ticket Cticket 一次一个生产者 一次一个消费者 await in t awit out u awit out t N 1 await in u 1 等待一个空缓冲区别 等待一个消息 buffer tmodN m m buffer umodN advance in advance out 信号一个满缓冲区及 信号一个满缓冲区 允许其它生产者 允许其它消费者 consume m 图 利用定序器和事件计数器实现生产者和消费者问题eventcountE sequencerT Pboth R S semaphoreR S intq r s q ticket T await E q r ticket R t s ticket S t advance E await R e r 1 R initial value await R e r 1 R initial value 图 利用定序器和事件计数器实现SimultaneousP 利用定序器和事件计数器实现P和V P s semaphores inti i ticket s t await s e i 1 s initial value V s semaphores advance s e 利用定序器和事件计数器实现生产者和消费者问题 eventcountin out sequencerPticket Cticket buffer array 0 N ofmessage producer consumer intt i 1 intu i 1 message m messagem while true while true m produce t ticket Pticket u ticket Cticket 一次一个生产者 一次一个消费者 await in t awit out u awit out t N 1 await in u 1 等待一个空缓冲区别 等待一个消息 buffer tmodN m m buffer umodN advance in advance out 信号一个满缓冲区及 信号一个满缓冲区 允许其它生产者 允许其它消费者 consume m eventcountE sequencerT Pboth R S semaphoreR S intq r s q ticket T await E q r ticket R t s ticket S t advance E await R e r 1 R initial value await R e r 1 R initial value 图 利用定序器和事件计数器实现SimultaneousP producer intt i 1 message m while true m produce u ticket Cticket 一次一个生产者 await in t awit out t N 1 等待一个空缓冲区 buffer tmodN m advance in 信号一个满缓冲区及 允许其它生产者 consumer intu i 1 message m while true t ticket Pticket 一次一个消费者 awit out u await in u 1 等待一个消息 m buffer umodN advance out 信号一个满缓冲区 允许其它消费者 consume m 利用定序器和事件计数器实现同时P eventcountE sequencerT Pboth R S semaphoreR S intq r s q ticket T await E q r ticket R t s ticket S t advance E await R e r 1 R initial value await R e r 1 R initial value 路径表达式 路径表达式 pathexpression 是由Campbell和Habermann 1974 首先提出的 后人又对其进行了完善和扩充 路径表达式的语法公式为pathpath listend其中path list由操作名和路径操作符组成 路径操作符包括 表示并发 表示顺序 n path list 表示path list的 至多 n次并发激活 path list 表示path list的无穷次并发激活 路径表达式 例如 路径表达式pathdeposit fetchend既没有限制deposit和fetch执行的次序 也没有规定它们的激活次数 它等价于下面的路径表达式 path deposit fetch end或path deposit fetch end但路径表达式pathdeposit fetchend规定了每个fetch之前应有一个deposit 路径表达式 每个操作的多次激活可以并发地执行 只要活动或已完成的fetch操作的个数不超过已完成的deposit操作的个数 又例如 实现容量为1的有界缓冲区的模块可以包含如下的路径表达式 pathl deposit fetch end它规定第一次引用的操作是deposit 每个deposit后接一个fetch 而且至多激活序列 deposit fetch 的一个例示 简言之 deposit和fetch交替且互斥地执行 路径表达式 有关容量为N的有界缓冲区的同步制约可用下面的路径表达式描述 pathN l deposit 1 fetch end它确保了 deposit的激活是互斥的 fetch的激活是互斥的 fetch的每次激活都有一个已完成的deposit操作在先 已完成的deposit操作的次数决不大于N 但大于已完成的fetch操作的次数 路径表达式表示简单批处理操作系统 modulebuffer T pathN l deposit 1 fetch end varslots array 0 N l ofT head tail 0 N 1 proceduredeposit p T beginslots tail p tail tail 1 modN end 路径表达式 procedurefetch varit T beginit slots head head head 1 modN end beginhead 0 tail 0end 路径表达式 注意 一个deposit和一个fetch可以并发地处理 这一点对于中给出的buffer管程来说是不可能的 基于这个原因 这里面有变量size 因为它是受并发存取所支配的 路径表达式不怎么适合描述条件同步 为解决这类问题 必须引进附加的成分 不过 路径表达式已被证明对于描述并发计算的语义是很有用的 shields 1979 shaw 1980 Best 1982 进程通信 进程通信是指进程间的信息交换 低级通信 进程的低级同步和互斥高级通信 是指用户可直接利用操作系统所提供的一组通信命令 高效地传送大量数据的一种通信方式 共享内存 Sharedmemorysystem 消息传递 Messagepassingsystem 管道通信 Pipe 共享存储系统 基于共享数据结构的通信方式 相互通信的进程公用某些共享数据结构 进程通过它们交换信息 操作系统只需提供共享存储 低效少量数据 基于共享存储区的通信方式 相互通信的进程可通过对共享存储区的数据 进行读或写来实现通信 消息传递系统 进程间的数据交换以消息 message 为单位 在计算机网络中 message又称为报文 操作系统提供一组通信命令 原语 来实现通信 直接通信方式 间接通信方式 直接通信方式 发送进程直接把消息发送给接收进程 并将它挂在接收进程的消息缓冲队列上 接收进程从消息缓冲队列取消息 此时 要求双方以显式方式 提供对方的标识符 操作系统提供下列两条通信原语 Send Receiver Message Receive Sender Message 间接通信方式 发送进程直接把消息发送给某个中间实体中 接收进程从其取得消息 这种中间实体一般称为信箱 故这种通信方式又称信箱通信方式 网络系统中称为电子邮件系统 间接通信方式 操作系统提供下列原语 信箱的创建和撤消 进程利用创建信箱原语 来建立一个新信箱 创建者应给出信箱名字和属性 对于共享信箱 还应给出共享者的名字 可用撤消原语撤消信箱 消息的发送和接收 Send mailbox message Receive mailbox message 信箱属性 私有信箱 用户进程创建 并成为该进程的一部分 可单向通信链路实现 公用信箱 操作系统创建 系统所有核准使用 双向通信链路实现 系统运行期间始终存在 共享信箱 用户进程创建 指明共享进程的名字 信箱拥有者和共享者都有权取走自己的消息 发送进程和接收进程间的四种关系 一对一关系 可建立专用通信链路 多对一关系 客户 服务器 client server 交互 一对多关系 多点或广播 多对多关系 允许建立一个公用信箱 多个进程发取消息 通信链路 communicationlink 显式建立链路 由发送进程在通信前用 建立连接 命令 原语 请求系统为之建立一条通信链路 链路用完后 用 撤消连接 命令斥拆除链路 主要用于计算机网络 隐式建立链路 利用系统提供的发送命令 原语 系统自动为之建立一条通信链路 主要用于单机 通信链路 根据通信链路的连接方式 可分为 点对点通信链路 一条链路只连接两个结点 进程 多点连接通信链路 一条链路连接多个 大于两个 结点 进程 通信链路 根据通信方式 通信链路可分为 单向通信链路 只允许发送进程向接收进程发送消息 双向通信链路 允许两个进程同时双向发送消息 通信链路 根据通信链路的容量 可分为 无容量通信链路 通信链路上没有缓冲区 不能暂存任何消息 有容量通信链路 通信链路上设置了缓冲区 因而能暂存消息 缓冲区愈大 容量也愈大 管道通信 管道 pipe 是指用于连接一个读进程和一个写进程 以实现它们之间通信的共享文件 又称为管道文件 管道通信 向管道 共享文件 提供输入的发送进程 即写进程 以字符流形式将大量数据送入管道 而接收管道输出的接收进程 即读进程 可从管道中接收数据 由于发送和接收进程是利用管道进行通信 故又称为管道通信 首创于UNIX系统 管道通信必须提供下列能力 互斥 当一个进程正在对管道进行读或写操作时 另一进程必须等待 同步 当写进程把数据写入管道后 便睡眠等待 直至读进程取走数据后 再把它唤醒 当读进程读一空管道时 也应睡眠等待 直至写进程把数据写入管道后 才把它唤醒 对方是否存在 只有确定对方存在 才能通信 基于消息传递的同步操作原语 消息传递 messagepassing 也是信号量的派生和发展 它可以看作是将信号量加以扩充用以传输数据并实现同步的 当消息传递用于通信和同步时 进程中的send和receive替代了 写 和 读 共享变量 当接收者进程接收到一个消息 它就获得了来自某个发送者进程送来的信息 从而完成了进程间的通信 基于消息传递的同步操作原语 一个消息可以被接收者进程所