第3章进程同步-wax

1、W内 容l 嵌入式操作系统概述嵌入式操作系统概述l 进程管理进程管理l 同步与互斥同步与互斥l 调度调度lSmall RTOSSmall RTOS任务管理任务管理lSmall RTOSSmall RTOS同步与互斥同步与互斥lSmall RTOSSmall RTOS时间管理时间管理lSmall RTOSSmall RTOS应用应用进程同步进程同步 进程同步是指对多个相关进程在执行次序上进行协调，它的目的是使系统中诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性；或系统中诸进程之间在逻辑上的相互制约的关系（直接的-同步；间接的-互斥）。 用来实现同步的机制称为同步机制。如：信号

2、量机制；管程机制。进程的两种制约关系进程的两种制约关系 间接制约:进程间由于共享某种系统资源，而形成的相互制约互斥。例如打印机 直接制约： 进程间由于合作而形成的相互制约同步。例：A:c=x+y;B:x=u-v进程B B 资源进程A进程A进程B B一、进程同步的基本概念一、进程同步的基本概念同步与互斥比较同步与互斥比较同同 步步互互 斥斥进程-进程进程-资源-进程时间次序上受到某种限制竞争不到某一物理资源时不允许进程工作相互清楚对方的存在及作用，交换信息不一定清楚其进程情况指几个进程共同完成一个任务 指多个任务多个进程间通讯制约例：生产与消费之间，发送与接受之间，作者与读者之间，供者与用者之间

3、例：交通十字路口，单轨火车的拨道岔互斥是并发执行的多个进程由于竞争同一资源而产生的相互排斥的关系同步是进程间共同完成一项任务时直接发生相互作用的关系同步进程间具有合作关系 在执行时间上必须按一定的顺序协调进行2 2、临界资源、临界区、临界资源、临界区 一次只允许一个进程使用的共享资源称为临界资源，如打印机，绘图机；变量，数据等 诸进程间采取互斥方式实现对这种临界资源的共享，从而实现并行程序的封闭性。2 2、临界资源、临界区、临界资源、临界区例例：有两个进程A和B，它们共享一个变量x，且两个进程按以下方式对变量X进行访问和修改:A: R1=X;B: R2=X;A: R1=R1+1; X=R1;B

4、: R2=R2+1; X=R2;A: R1=X; R1=R1+1; X=R1;B: R2=X; R2=R2+1; X=R2;（1 1）变量）变量X X必必需按临界资源需按临界资源处理。处理。其中R1和R2为处理机中的两个寄存器。A与B均对X+1，即X+2。结果x只加了1.若按另一顺序对变量进行修改：（2 2）每个进程）每个进程中访问临界资中访问临界资源的那段代码源的那段代码称为临界区，称为临界区，进程必须互斥进入临界区访问临界区的循环进程描述访问临界区的循环进程描述repeat进入区进入区临界区临界区退出区退出区剩余区剩余区检查临界资源是否能访问检查临界资源是否能访问将临界区标志设为未访问将临

5、界区标志设为未访问 until false;火车2 2、临界资源、临界区、临界资源、临界区 要进入临界区的若干进程必须满足要进入临界区的若干进程必须满足：（1）一次只允许一个进程进入一个临界区（2）任何时候，处于单个临界区的进程不得多于一个（3）进入临界区的进程要在有限的时间内退出（4）如果不能进入自己的临界区，则应让出处理机资源进入区临界区退出区剩余区2 2、临界资源、临界区、临界资源、临界区解决临界区（互斥）问题的几类方法：解决临界区（互斥）问题的几类方法：（1）软件方法（P-V操作）（2）硬件方法进入区临界区退出区剩余区同步机制同步机制遵循的原则 空闲让进空闲让进忙则等待忙则等待有限等待

6、有限等待让权等待让权等待信号量机制中心街道 楼宇 1小区A小区 B城市公路进程信号量l 信号量是一种数据结构l 信号量的值与相应资源的使用情况有关l 信号量的值仅由P、V操作改变二、信号量机制 信号量机制是荷兰科学家E.W.Dijkstra在1965年提出的一种同步机制，也称为P、V操作。由最初的整型信号量发展为记录型信号量，进而发展为信号量集。整型信号量整型信号量记录型信号量记录型信号量信号量集（信号量集（AND信号量集）信号量集）整型信号量 整型信号量整型信号量非负整数，除了初始化外，只能通过两个原子操作waitwait和signalsignal（P P，V V）来访问。SP操作（操作（w

7、ait）原语）原语V操作（操作（signal）原语）原语l Wait（S）: while S0 do no-op0 do no-op S:=S-1; S:=S-1;l Signal（S）: S:=S+1;S:=S+1; waitwait（s s）和）和signalsignal（S S）是原子操作是原子操作. . 只要信号量只要信号量S S00就不断测就不断测试，不满足让权等待试，不满足让权等待. .记录型信号量 基本思想基本思想 1、设置一个代表资源数目的整型变量valuevalue（资源信号量） 2、设置一链表L L用于链接所有等待的进程记录型信号量的数据结构记录型信号量的数据结构，包含两个

8、数据项： type semaphore=record value:integer; L:list of process; endValueLS S.value为整型，是资源信号量,其初值：某类资源的数目 wait操作：申请一个单位资源操作：申请一个单位资源Procedure wait(s)Var S:semaphore;beginendsignal操作：释放一个单位资源操作：释放一个单位资源Procedure signal(s)Var S:semaphore;beginendlS.valueS.value00：表示系统中可用的：表示系统中可用的资源数量资源数量lS.valueS.value 0

9、 0：其绝对值表示已阻塞：其绝对值表示已阻塞的进程数量的进程数量lS.ValueS.Value初值为初值为1 1时：只允许一个时：只允许一个进程访问临界资源，是互斥信号进程访问临界资源，是互斥信号量量wait（Dmutex）wait（Emutex）wait（Emutex）wait（Dmutex）会造成死锁的僵持状态会造成死锁的僵持状态AND型信号量 AND型信号量基本思想：将进程在整个运行中需要的所有资源，一次性全部分配给进程，待进程使用完后一起释放。 在在wait中加入中加入AND条件，条件，又称又称AND同步或同时同步或同时wait操作：操作：SwaitSwait(S1，S2，Sn) If

10、 S11 and Sn1 then for i:=1 to n do Si:= Si-1; endfor else 当发现第一个当发现第一个Si0），一群生产者进程），一群生产者进程p1,p2,，pm，一群消费者进程，一群消费者进程c1,c2,，cm，如，如图所示。假定生产者和消费者是相互等效，只要图所示。假定生产者和消费者是相互等效，只要缓冲区未满，生产者就可以把产品送入缓冲区，缓冲区未满，生产者就可以把产品送入缓冲区，类似地，只要缓冲区未空，消费者便可以从缓冲类似地，只要缓冲区未空，消费者便可以从缓冲区取走产品并消耗它。区取走产品并消耗它。 P1P2pmc1c2cml 在输入时，输入进程是

11、生产者，计算进程是消费者；l 在输出时，计算进程是生产者，打印进程是消费者。生产者一消费者问题实际上是相互合作进程关系生产者一消费者问题实际上是相互合作进程关系的一种抽象，例如的一种抽象，例如生产者一消费者问题生产者一消费者问题禁止生产者向满的缓冲区输送产品禁止生产者向满的缓冲区输送产品也禁止消费者从空的缓冲区提取产品也禁止消费者从空的缓冲区提取产品制约关系：制约关系：用记录型信号量解决生产者一消费者问题 设有设有n个缓冲区，每个缓冲区存放一个消个缓冲区，每个缓冲区存放一个消息，用互斥信号量息，用互斥信号量mutex对缓冲池实现互对缓冲池实现互斥访问；斥访问； 利用资源信号量利用资源信号量em

12、pty和和full分别表示缓分别表示缓冲池中空缓冲区及满缓冲区的数量又冲池中空缓冲区及满缓冲区的数量又假定这些生产者和消费者相互等效，只假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可缓冲池；只要缓冲池未空，消费者便可从缓冲池取走一个消息。从缓冲池取走一个消息。 “生产者生产者消费者消费者”问题的同步算法描述问题的同步算法描述 semaphore full=0; semaphore empty=n; semaphore mutex=1; Main() cobegin producer(); consumer

13、(); coend “ “生产者生产者消费者消费者”问题的解决问题的解决 while(true) while(true) 生产一个产品生产一个产品; ; p(empty); p(empty); P(mutex P(mutex); ); 将一个产品送入缓将一个产品送入缓冲区；冲区； V(mutexV(mutex);); V(full); V(full); Producer() while(true) while(true) p(full); p(full); P(mutex P(mutex); ); 从缓冲区取走一个产从缓冲区取走一个产品品; ; V(mutex V(mutex);); V(em

14、pty); V(empty); 消费一个产品；消费一个产品； consumer()“生产者生产者- -消费者消费者”问题中应注意问题中应注意1. 1. 互斥信号量的互斥信号量的P,VP,V操作在每一程序中必须成对出现操作在每一程序中必须成对出现. .2.2.对资源信号量对资源信号量empty和和full的的P、v操作成对出现，但它操作成对出现，但它们分别处于不同的程序中，例如们分别处于不同的程序中，例如P在计算进程中，而在计算进程中，而v则在打印进程中，计算进程若因执行则在打印进程中，计算进程若因执行P而阻塞，则以而阻塞，则以后将由打印进程将它唤醒。后将由打印进程将它唤醒。3. 3. 多个多个

15、P P操作顺序不能颠倒：先执行资源信号量的操作顺序不能颠倒：先执行资源信号量的P P操作操作, ,再执行互斥信号量的再执行互斥信号量的P P操作操作, ,否则可能引起进程死锁否则可能引起进程死锁. .“生产者生产者- -消费者消费者”问题中应注意问题中应注意4. 4. 它是一个同步问题：它是一个同步问题： （1 1）消费者想要取产品，有界缓冲区中至少有一个单）消费者想要取产品，有界缓冲区中至少有一个单元是满的。元是满的。 （2 2）生产者想要放产品，有界缓冲区中至少有一个是）生产者想要放产品，有界缓冲区中至少有一个是空的。空的。5. 5. 它是一互斥问题它是一互斥问题 有界缓冲区是临界资源，因

16、此，各生产者进程和各有界缓冲区是临界资源，因此，各生产者进程和各消费者进程必须互斥执行。消费者进程必须互斥执行。哲学家进餐问题 问题描述：有五个哲学家，他们的生活方式是问题描述：有五个哲学家，他们的生活方式是交替地进行思考和进餐。哲学家们共用一张圆交替地进行思考和进餐。哲学家们共用一张圆桌，分别坐在周围的五张椅子上。在圆桌上有桌，分别坐在周围的五张椅子上。在圆桌上有五个碗和五支筷子，平时一个哲学家进行思考，五个碗和五支筷子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近他的筷子，饥饿时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐毕，只有在他拿到两支筷子时才能进

17、餐。进餐毕，放下筷子又继续思考。放下筷子又继续思考。分析 筷子是临界资源，在一段时间内只允许一个哲筷子是临界资源，在一段时间内只允许一个哲学家使用学家使用 用一个信号量表示一支筷子，由这五个信号量用一个信号量表示一支筷子，由这五个信号量构成信号量组。构成信号量组。var chopstick: array04of semaphore 所有信号量被初始化为所有信号量被初始化为1用记录型信号量用记录型信号量解决哲学家进餐问题解决哲学家进餐问题第第i个哲学家的活动可描述为个哲学家的活动可描述为repeat wait(chopsticki); wait(chopstick(i+1)mod 5); eat

18、 signal(chopsticki); signal(chopstick(i+1)mod 5); think; until false;问题 假如五个哲学家同时饥饿而各自拿起左边的筷子，会使五个信号量均为0，当他们再试图拿起右边筷子时，都将无限期地等待。解决方法 (1)至多四个人同时拿左边的筷子，保证至少有一个人至多四个人同时拿左边的筷子，保证至少有一个人可以进餐，最终释放筷子使更多的人进餐。可以进餐，最终释放筷子使更多的人进餐。 (2)仅当哲学家的左右两支筷子均可用时，才允许他拿仅当哲学家的左右两支筷子均可用时，才允许他拿起筷子进餐。起筷子进餐。 (3)规定奇数号哲学家先拿起其左边的筷子，

19、再拿右边规定奇数号哲学家先拿起其左边的筷子，再拿右边的，偶数号哲学家则相反。即：的，偶数号哲学家则相反。即：l、2号人竞争号人竞争1号筷号筷子，子，3、4号人竞争号人竞争3号筷子，即五个人都先竞争奇数号筷子，即五个人都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会号筷子，获得后，再去竞争偶数号筷子，最后总会有某一人进餐。有某一人进餐。用用AND型信号量型信号量解决哲学家进餐问题解决哲学家进餐问题var chopstick: array04of semaphore：=（1，1，1，1，1）第第i个哲学家的活动个哲学家的活动repeat think ; Swait(chopstick(i+

20、1)mod 5, chopsticki); eat Ssignal(chopstick(i+1)mod 5，chopsticki); think; until false;读者一写者问题读者一写者问题 问题描述： 一个数据对象（数据文件或记录）可被多个进程共享。其中，reader进程要求读，writer 进程要求写或修改。允许多个reader进程同时读共享数据，但绝不允许一个writer进程与其它的reader进程或writer进程同时访问，即writer进程必须与其它进程互斥访问共享对象。 所谓读者一写者问题是指保证一个Writer进程必须与其它进程互斥地访问共享对象的同步问题。信号量设置为

21、解决一个为解决一个WriterWriter进程和其它进程和其它ReaderReader进程互斥，进程互斥，设互斥信号量设互斥信号量WmutexWmutex，初值为初值为1 1设置共享变量设置共享变量ReadercountReadercount表示正在读的进程表示正在读的进程数目数目. .初值为初值为0 0。ReadercountReadercount是一个可被多个是一个可被多个ReaderReader进程访问进程访问的临界资源，为它设置互斥信号量的临界资源，为它设置互斥信号量RmutexRmutex. .初初值为值为1 1 仅当仅当ReadercountReadercount 0 0表示无表示

22、无ReaderReader进程在读时，进程在读时， ReaderReader进程才需要执行进程才需要执行p p操作。若操作。若p p操作成功，操作成功， ReaderReader进程便可去读使进程便可去读使Readercount+1Readercount+1，原因，原因是：是： ReadercountReadercount0,0,说明已有说明已有ReaderReader进程在安全的读进程在安全的读数据。数据。 “读者读者写者写者”问题的同步算法描述问题的同步算法描述 semaphore rmutex=1; semaphore wmutex=1; int readcount=0; Main()

23、cobegin reader(); writer(); coend “ “读者读者写者写者”问题的解决问题的解决 while(true) while(true) p(rmutex p(rmutex); ); if(readcount= =0) p(wmutex if(readcount= =0) p(wmutex);/);/* *第一位读者阻止写者第一位读者阻止写者* */ / readcount readcount+;+; V(rmutex V(rmutex);); 读数据集；读数据集； p(rmutexp(rmutex); ); readcount readcount-; -; if(re

24、adcount= =0) v(wmutex if(readcount= =0) v(wmutex);/);/* *第末位读者允许写者进第末位读者允许写者进 V(rmutexV(rmutex);); reader()修改修改readcount修改修改readcount while(true) p(wmutex); /*阻止其它进程（读、写）进阻止其它进程（读、写）进/ 写数据集；写数据集； V(wmutex); /*允许其它进程（读、写）进允许其它进程（读、写）进/writer()进程通信进程通信 进程通信是指进程之间的信息交换 交换的信息量 一个状态或数值 上千个字节进程通信分类进程通信分类1

25、)1) 低级通信：进程的互斥和同步低级通信：进程的互斥和同步2)2) 高级通信：高级通信： 指用户可直接利用指用户可直接利用osos提供的一组提供的一组通通信命令信命令，高效地传送大量数据的一种通信方式。，高效地传送大量数据的一种通信方式。对用户透明。对用户透明。高级通信分类 共享存储器系统共享存储器系统 消息传递系统消息传递系统 管道通信管道通信共享存储器系统共享存储器系统 (1)(1)共享数据结构的通信方式共享数据结构的通信方式 进程之间通过某进程之间通过某种数据结构，如缓冲池进行通信属于低级通信种数据结构，如缓冲池进行通信属于低级通信方式；方式； (2)(2)共享存储区通信方式共享存储区

26、通信方式 为了传送大量信息，为了传送大量信息，在存储器中划出一块共享存储区，进程可通过在存储器中划出一块共享存储区，进程可通过对共享存储区进行读或写来实现通信，属于高对共享存储区进行读或写来实现通信，属于高级通信方式。级通信方式。消息传递系统信息交换的单位是消息或报文，分成两种：信息交换的单位是消息或报文，分成两种：1 1直接通信方式直接通信方式 2 2间接通信方式间接通信方式 计算机网络中将消息称为计算机网络中将消息称为报文报文。直接通信方式直接通信方式 o 发送进程直接把消息发送给目标进程发送进程直接把消息发送给目标进程o 发送进程和接收进程都以显式方式分别提供对发送进程和接收进程都以显式

27、方式分别提供对方的标识符。方的标识符。o 系统提供两条通信原语系统提供两条通信原语 Send(Receiver,message); Receive(Sender,message);例如例如: Send(P2,m1); Receive(P1,m1);解决生产者一消费者问题repeat produce an item in nextp; Send(consumer,nextp);until false; repeat Receive(producer, nextp); Consumer the item in nextc;until false;间接通信方式间接通信方式 进程之间的通信需要通过某种

28、中间实体，该实体用进程之间的通信需要通过某种中间实体，该实体用来暂存发送进程发送给目标进程的消息；接收进程来暂存发送进程发送给目标进程的消息；接收进程则从该实体中取出对方发送给自己的消息。则从该实体中取出对方发送给自己的消息。这种中间实体称为信箱。这种中间实体称为信箱。消息在信箱中可以安全地保存只允许核准的目标消息在信箱中可以安全地保存只允许核准的目标用户随时读取，故可实现非实时通信。用户随时读取，故可实现非实时通信。信箱的创建和撤消进程用信箱创建原语来建立一个新信箱。创建进程用信箱创建原语来建立一个新信箱。创建者进程应给出信箱名字、信箱属性者进程应给出信箱名字、信箱属性( (公用、私公用、私

29、用或共享用或共享) )；对于共享信箱，还应给出共享者；对于共享信箱，还应给出共享者的名字。的名字。用信箱撤消原语来撤消。用信箱撤消原语来撤消。消息的发送与接收 Send(mailbox,message)：将一个消息发送到指定信箱；：将一个消息发送到指定信箱； Receive (mailbox,message) 从指定信箱中接收一个消息从指定信箱中接收一个消息信箱分类v私用信箱。私用信箱。v公用信箱。公用信箱。v共享信箱。共享信箱。私用信箱私用信箱 用户进程建立，作为该进程的一部分。用户进程建立，作为该进程的一部分。 拥有者有权读消息其他用户只能发送。拥有者有权读消息其他用户只能发送。 采用单向通信链路。采用单向通信链路。 进程结束时信箱也消失。进程结束时信箱也消失。公用信箱公用信箱 它由它由OSOS创