《实时操作系统同步、互斥与通信.ppt》由会员分享，可在线阅读，更多相关《实时操作系统同步、互斥与通信.ppt（134页珍藏版）》请在三一办公上搜索。
1、嵌入式实时操作系统及应用开发,第六章 同步、互斥与通信,主要内容,概述信号量邮箱和消息队列管道事件,并发的进程之间的协作包括如下类型：进程互斥 多个进程不能同时使用同一个资源，某个进程使用该资源时，其他进程必须等待。保证各个进程不同时进入临界区，有效访问临界资源。进程同步 多个进程的调用存在时序关系，某些进程的执行必须先于另一些进程。保证进程运行的合理顺。进程通信 多个进程之间传递消息。互斥和同步是进程并发的两个要素,概述,ISR x,Task y,POST,PEND,任务与ISR之间的同步（单向）,Task x,Task y,POST,PEND,POST,PEND,任务与任务之间的同步（双向
2、）,任务与任务之间的同步（单向）,Task x,Task y,POST,PEND,概述,进程互斥与同步,考虑下面一个字符回显的的过程 void echo()chin=getchar();chout=chin;putchar(chout);从键盘获得输入，每击一下键，输入字符就保存在变量chin中，然后传送给变量chout，并回送显示器任何程序可以重复地调用此过程，接收用户输入，并在用户的屏幕上显示,考虑一个支持单用户单处理器、多道程序设计系统将其当作一个共享过程，载入到所有应用程序公用的全局存储区中。这样每个应用程序都能使用这个过程，由于每个应用程序只需使用echo过程的一个副本，从而节省空间
3、进程间共享主存是非常有用的，它允许进程间有效而紧密的交互，有利于进程的相互通信。但是，共享也可能会带来一些问题,void echo()chin=getchar();chout=chin;putchar(chout);,进程互斥与同步,P1,P2,getchar（）,X,X,getchar（）,Y,Y,Y,putchar（）,Y,Y,Y,？,echo,void echo()chin=getchar();chout=chin;putchar(chout);,P1,void echo()chin=getchar();chout=chin;putchar(chout);,P2,资源正忙,唤 醒,在单处
4、理器平台上，嵌入式操作系统内核提供的同步、互斥与通信机制主要包括：信号量（semaphore），用于互斥与同步事件（组）（event group），用于同步异步信号（asynchronous signal），用于同步邮箱（mailbox）、消息队列（message queue），用于消息通信管道（pipe），提供非结构化数据交换和实现同步,概述,忙等待模型 持续检查一个变量，直到它可用为止睡眠-唤醒模型 通过PV原语操作保证进程间的互斥消息传递模型 通过消息传送系统实现多进程之间的互斥,进程互斥和同步的经典解决机制,第一节信号量,信号量的种类及用途信号量的定义互斥信号量二值信号量计数信号量信号
5、量机制的主要数据结构典型的信号量操作,临界资源和临界区,操作系统把一次仅允许一个进程使用的资源称为临界资源。一个进程中访问临界资源的那段程序称为临界区。,进程P1和P2共享同一打印机资源，其操作流程如下：p1:entry code使用打印机exit code p2:entry code使用打印机exit code系统打印机即为临界资源P1和p2的访问临界资源打印机的代码即为临界区,临界资源和临界区,进程P1 进程P2 R1 count;R2=count;R1+;R2+;count=R1;count=R2;（设count的初始值为5）为互斥地使用临界资源，需保证进程互斥地进入临界区。,临界资源和
6、临界区,临界区的进入准则空闲让进：临界资源空闲时，允许进程进入临界区忙着等待：临界资源正在被访问时，其他需要进入临界区的进程必须等待有限等待：保证进程在有效的时间内进入临界区，避免“死等”让权等待：当进程不能进入临界区时，应立即释放处理机，以免其它进程“忙等”,临界资源和临界区,进程互斥进入临界区的实现方法硬件方法禁止中断在进程进入临界区之后，禁止该进程中断专用机器指令TS指令，Swap指令软件方法信号量和PV操作,临界资源和临界区,信号量是一个数据结构，其定义如下：struct semaphore int value;struct PCB*queue;信号量semaphore包括一个整型值和
7、一个等待队列。信号量只能通过P原语和V原语访问。,什么是信号量,什么是信号量,信号量被定义为一个整形变量，在其上定义了以下三个操作：1、可以被初始化一个非负数2、wait操作（P操作）将信号量的值减1后，若该值为负，则执行wait操作的任务等待3、signal操作（V操作）将信号量的值增1后，若该值为非正，则执行signal操作的任务唤醒,P 原语 P(S)S:=S-1；如果 S=0，则表示有资源，该进程继续执行；如果 S 0，则表示已无资源，执行原语的进程被置成阻塞状态，并使其在 S 信号量的队列中等待，直至其他进程在 S 上执行 V 操作释放它为止,P原语,P原语,(1)若信号量S大于0，
8、则将S减1，P操作返回，该进程继续执行(2)若信号量S小于0，则将进程挂入S的等待队列，将进程设置为阻塞状态，并转调度程序,P原语,S0,S=S-1,返回,调用进程进入等待队列,转进程调度,是,否,P原语操作原型 void wait(semaphore s)/s.value=s.value 1;if(s.value 0)block(s.queue);/阻塞进程,P原语,V 原语 V(S)S:=S+1如果 S 0，则该进程继续执行如果 S 0，说明有进程被挂起，则唤醒一阻塞进程，即从S信号量的等待队列首摘下一个PCB，将其置为就绪状态，执行 V(S)者继续执行P操作可能会引起进程的阻塞，V操作不
9、会引起本身进程状态的变化，但可能唤醒其他进程，使其从阻塞状态转变到就绪状态,V原语,V原语,(1)若信号量S的等待队列中有等待进程，则取队首进程，将其置为就绪状态并返回。(2)否则信号量S加1，并放回,V原语,是否有等待进程,S=S+1,返回,取队首进程置为就绪态,否,是,V原语操作原型 void signal(semaphore s)s.value=s.value+1;if(s.value=0)wakup(s.queue);/唤醒进程,V原语,P原语的作用 申请临界资源，如果该资源正被其他进程使用，则等待。V原语的作用 释放临界资源，如有其他进程等待该资源，则唤醒。使用PV原语可以解决进程的
10、互斥和同步,P原语与V原语,P1,P2,P3,P4,关于s信号量的阻塞队列,信号量S的初值为：,2,P(s)S=s-1=1,P(s)S=s-1=0,P(s)S=s-1=-1,P3,P(s)S=s-1=-2,P4,v(s)S=s+1=-1,就绪,v(s)S=s+1=0,就绪,v(s)S=s+1=1,v(s)S=s+1=2,哲学家就餐问题,某天的某个地方，有5位哲学家住在一起，每位哲学家的生活就是思考和吃饭。通过多年的思考，所有的哲学家一致同意最有助于他们思考的食物是意大利面条吃饭的布置很简单：一个圆桌上有一大碗面，5个盘子，每位哲学家一个，还有5根筷子。每个想吃饭的哲学家将坐到桌子旁分配给他的位
11、置上，使用盘子两侧的筷子，夹面条吃。,问题是：设计一个算法以允许哲学家吃饭。算法必须保证互斥(没有两个哲学家同时使用同一根筷子)，同时还要避免死锁和饿死,死锁的产生,为克服死锁危险，可以再另买5跟筷子(一个更卫生的解决方案)或者教会哲学家仅用一跟筷子吃面另一种方法是，考虑增加一位服务员，他只允许4位哲学家同时坐上餐桌吃饭，由于最多有4位哲学家就座，因而至少有一位哲学家可以拿到两跟筷子，这里再次使用了信号量。,哲学家就餐问题,类似资源定序的解决方案：规定哲学家取筷子的顺序：单号哲学家先取右边的筷子再取左边的筷子；双号哲学家先去左边的筷子再取右边的筷子。在取第一根筷子时总有哲学家没拿到筷子，因此必
12、定能保证有一个哲学家能取到另一边的筷子，吃完面后，将筷子给其他哲学家用。,哲学家就餐问题,4.5死锁,信号量用于实现任务与任务之间、任务与中断处理程序之间的同步与互斥。信号量一般分为三种：,信号量的种类及用途,用于解决互斥问题。它比较特殊，可能会引起优先级反转问题。,用于解决同步问题,用于解决资源计数问题,将信号量进行种类细分，可以根据其用途，在具体实现时做专门处理，提高执行效率和可靠性。,互斥信号量,计数信号量,二值信号量,一般地，如果有n个进程共享某一临界资源，则先找出每个进程的临界区，再使用PV原语实现进入和退出临界区：semaphone mutex;P(mutex);临界区;V(mut
13、ex);,信号量实现进程互斥,例如：卖机票的进程实现互斥 semaphone mutex=1;P(mutex)；value=count;/count为剩余机票数量(临界资源)if(value=1)value=value 1;count=value;/打印一张机票；else/显示机票已售完;V(mutex);,信号量实现进程互斥,用信号量实现任务间的互斥,var mutex:Shared Semaphore;begin mutex:=1;parbegin P1:P2:Pi:repeat Wait(mutex);“进程Pi的临界代码段”；Signal(mutex);forever Pn:paren
14、d end,互斥信号量,WaitB(S):/申请信号量if S.value1;/当前没有其他任务使用信号量 then S.value=S.value-1=0/将信号量值修改为0，独占共享资源else begin Insert(CALLER,S.L);/如果当前有其他任务使用信号量，将该任务放入等待 队列 Block(CALLER);/修改该任务的状态为等待态（阻塞任务）endSignalB(S):/释放信号量if S.L queue is empty;/如果等待序列为空，没有其他任务等待使用该共享资源 then S.value=1;/释放信号量else begin Remove(S.L,id)
15、;/如果有其他任务等待使用该共享资源，则从等待队列中 将该任务移除 wakeup(id);/将该任务的状态改为就绪态(唤醒任务)end,互斥信号量状态图,互斥信号量状态图,各种互斥机制比较,二值信号量,可获得,不可获得,申请并获得(值为0),释放(值为1),初始化值为0,二值信号量状态图,例如：有两个程序段S1和S2，要求S1先于S2执行。semaphore mutex=0;P1进程：S1;V(mutex);/唤醒进程P2;P2进程：P(mutex);/等待P1执行;S2;,二值信号量实现同步,Task1()执行一些操作;将信号量sem1置1;申请信号量sem2;,Task2()申请信号量se
16、m1;执行一些操作;将信号量sem2置1;,Task2申请信号量sem1失败，系统切换到Task1,sem1被置1后，Task2得到sem1并抢占Task1,Task2运行到某处时因某种原因被阻塞，系统切换到Task1,用二值信号量实现两个任务之间的双向同步Task2优先级高于Task1sem1和sem2的初始值均为0,二值信号量实现同步,计数信号量,计数信号量,计数信号量状态图,可获得,不可获得,初始化值大于0,申请并获得值为0,释放值为1,申请并获得值减1,释放值加1,计数(一般)信号量同步原语,Wait(S):S.value:=S.value-1;/有新任务来使用共享资源将信号量的值减1
17、 if S.value0/如果信号量的值为负，表示共享资源已经分配完毕 then begin Insert(CALLER,S.L);/将该任务插入等待序列 Block(CALLER);/将该任务状态改为等待态(阻塞任务)endSignal(S):S.value:=S.value+1;/任务使用完共享资源，将信号量的值加1，释放 一个信号量 if S.value=0/如果信号量为负，表示仍有等待该资源的任务被 阻塞 then begin Remove(S.L,id);/将等待队列中的一个任务从队列中移除 wakeup(id);/将该任务的状态修改为就绪态，唤醒任务 end S的绝对值表示在该信号
18、量列表中已阻塞的任务数目,计数信号量,计数信号量使用实例：有界缓冲问题,生产者-消费者问题,生产者-消费者模型,p1,p2,p3,p4,pi,c1,c2,c3,c4,ci,.,.,生产者/消费者问题,p1,p2,p3,p4,pi,c1,c2,c3,c4,ci,.,.,生产者/消费者问题,管理员，怎么没东西！,消费者对生产者有依赖关系：只有生产者生产出产品，才能给消费者提供产品消费,p1,p2,p3,p4,pi,c1,c2,c3,c4,ci,.,.,生产者/消费者问题,生产者对消费者有依赖关系：只有消费者消费掉产品，才能给生产者提供存放产品的空间,p1,p2,p3,p4,pi,c1,c2,c3,
19、c4,ci,.,.,生产者/消费者问题,p1,c1,同一时刻只允许一个生产者或者一个消费者进入缓冲池（仓库）,生产者/消费者问题,分析 生产者与生产者之间互斥 消费者与消费者之间互斥 生产者与消费者之间即有同步又有互斥设置信号量（设初始缓冲池为空，共有n个缓冲区）用于互斥的公共信号量：s1 生产者的私有信号量：emptyn 消费者的私有信号量：full0流程图和程序：,生产产品,P(empty),P(s),buffer(in):=product;in:=(in+1)mod n;,V(full),V(s),生产者,P(full),P(s),goods:=buffer(out);out:=(out
20、+1)mod n;,V(empty),V(s),消费者,消费产品,信号量解决方法：semaphore mutex=1;semaphore empty=n;/空闲的缓冲区数量semaphore full=0;/存放产品的缓冲区数量生产者进程：while(1)P(empty);P(mutex);/等待进入缓冲区 生产出的产品放入buffer；V(mutex);/退出缓冲区 V(full);/唤醒消费者进程,生产者-消费者问题,消费者进程：while(1)P(full);P(mutex);/等待进入缓冲区 从buffer中取出产品；V(mutex);/退出缓冲区 V(empty);/唤醒生产者进程,
21、生产者-消费者问题,生产者消费者问题中需注意的问题：n个缓冲区为临界资源，必须互斥访问，通过P(mutex)和V(mutex)实现，且须成对出现；full和empty为资源信号量，full+empty=n，P(empty)和V(full)成对出现，但属于不同进程；多个P，V顺序不能颠倒，否则可能引起死锁。,生产者-消费者问题,计数信号量,Var E,F:Semaphore;mutex:binary Semaphore;begin(*main program*)F:=0;E:=n;mutex=1;parbegin producer1;producern;consumer1;consumerm；p
22、arendend,58,生产者任务begin repeat 生产数据/生产者生产数据 Wait(E);/减少一个空缓冲区项 Wait(mutex);/分配空缓冲区和移动指针P操作是互斥的“分配空缓冲区并调整指针P的临界段”；“向空缓冲区中装入数据”Signal(mutex);/释放互斥信号量 Signal(F);/增加一个满缓冲区项 forever end,消费者任务begin repeat 消费数据/消费者取走数据 Wait(F);/减少一个满缓冲区项 Wait(mutex);/分配满缓冲区和移动指针C操作是互斥的“分配满缓冲区并调整指针C的临界段”；“从满缓冲区中取走数据”Signal(m
23、utex);/释放互斥信号量 Signal(F);/增加一个空缓冲区项 forever end,计数信号量,读者和写者问题,一个文件或记录（即数据对象）可被多个进程共享。有些进程只要求读reader；有些进程要修改内容writer。允许多个reader进程读一个共享对象；但不允许writer进程和其他writer进程或reader进程同时访问共享数据对象分析：对于writer，只需在访问数据对象前，对信号量做p操作，释放数据对象时，做v操作。对于reader，第一个访问数据对象者，要对信号量做一个p操作，而v操作，则由最后一个释放对象的执行,因此设置一个变量readcount，以表示正在进行读
24、操作的进程数目，初值为0。则 进入：每增加一个reader进程，readcountreadcount+1 readcount1，reader进程对读写互斥信号量执行p操作 退出：每个reader进程退出，则readcountreadcount-1 readcount0，reader进程执行v操作,读者和写者问题,设置信号量写者与其它写者和读者的互斥信号量：wrt 初值为1；读者对于readcount的互斥信号量：mutex 初值为1实现同步互斥关系 流程图和程序,读者和写者问题,4.2进程的同步与互斥信号量,writer：,Reader:,读者和写者问题,Procedure writer；be
25、gin P（wrt）；writing is performing；V（wrt）；end；,Procedure reader；begin P（mutex）；Readcountreadcount+1；if readcount1 then P(wrt);V（mutex）；reading is perfoming；P（mutex）；Readcountreadcount-1；if readcount0 then V(wrt);V（mutex）；,理发室,椅子,入口,出口,等候室,简单理发店问题,简单理发店问题,一个理发店由一个有几张椅子的等候室、一个放有一张理发椅的理发室和一个理发师组成。若没有要理发的
26、顾客，则理发师就去睡觉；若一顾客走进理发店且所有的椅子都被占用了，则该顾客就离开理发店；若理发师正在为人理发，则该顾客就找一张空椅子坐下等待;若理发师在睡觉，则顾客就唤醒他。,简单理发店问题,分析只有当顾客坐上理发椅，理发师才开始理发同步当正在理发的顾客理好发，等待的顾客才能理发同步同一时刻只有一个顾客能理发互斥同一时刻只有有限的顾客能在等待室等待互斥资源与信号量对于理发师：坐上理发椅的顾客，信号量barber0对于理完发的顾客：是否有顾客等待，信号量wait0对于进入的顾客：是否有人在理发，及等候室是否已满，变量count0保证对共享变量count的互斥访问的信号量：entry1,简单理发店
27、问题,/共享数据结构：var barber,wait:semaphore;(初始值=0)entry:semaphore;(初始值=1)couter:integer;(初始值=0)/关于理发师的代码段：while true do P(barber);“Shave”,简单理发店问题,/关于顾客的代码段：P(entry);if count=n then V(entry);exit;count:=count+1;if count 1 then V(entry);P(wait);,else V(entry);V(barber);“Shave”P(entry);count:=count 1;if coun
28、t 0 then V(wait);V(entry);,barber信号量队列,wait信号量队列,entry信号量队列,理发师,理发师,P（barber）,PP（entry）,P（entry）,count,=0,=1,v（entry）,count=1,v（entry）,Count=2,P（wait）,V（barber）,理发师,barber信号量队列,wait信号量队列,entry信号量队列,P（entry）,count=5,V（entry）,P（entry）,count=5,count=4,V（entry）,V（wait）,V（barber）,信号量机制的主要数据结构,信号量机制的主要数据结
29、构,信号量控制块：管理所有创建的信号量，内核在系统运行时动态分配和回收信号量控制块互斥和二值信号量控制块结构:Binary_Semaphore_Control_Block,wait_queue任务等待队列attributes信号量属性lock_nesting_behavior 试图嵌套获得时的规则 wait_discipline 任务等待信号量的方式priority_ceiling 优先级天花板值lock是否被占有holder拥有者 nest_count嵌套层数,计数信号量控制结构Counting_Semaphore_Control_Block wait_queue任务等待队列 attribu
30、tes计数信号量属性 maximum_count 最大计数值 wait_discipline任务等待信号量的方式 count当前计数值,信号量机制的主要数据结构,典型的信号量操作,创建信号量获取（申请）信号量释放信号量删除信号量清除信号量的任务等待列表 获取有关信号量的各种信息,创建信号量,功能：根据应用传递的参数创建一个信号量参数：信号量的名字、属性和初始值等。内核动作：从空闲信号量控制块链中分配一个信号量控制块，并初始化信号量属性。创建成功时，为其分配唯一的ID号返回给应用。如果已创建信号量数量已达到用户配置的最大数量，就返回错误。,信号量的属性,信号量的属性,信号量的类型,互斥信号量（M
31、UTEX_SEMAPHORE）,计数信号量（COUNTING_SEMAPHORE）,二值信号量（BINARY_SEMAPHORE）,任务等待信号量的方式,先进先出（FIFO）顺序,优先级（PRIORITY）顺序,优先级反转问题的解决方法（只适用于互斥信号量）,优先级继承算法（INHERIT_PRIORITY）,优先级天花板算法(PRIORITY_CEILING)，需给出所有可能获得此信号量的任务中优先级最高的任务的优先级。,获取（申请）信号量,功能：试图获得应用指定的信号量。该功能流程如下：if 信号量的值大于0then 将信号量的值减1else 根据接收信号量的选项，将任务放到等待 队列中，
32、或是直接返回,获取（申请）信号量,当所申请的信号量不能被立即获得时，可以有以下几种选择：永远等待 不等待，立即返回，并返回一个错误状态码指定等待时限（可有效避免死锁）注意：不允许在ISR中选择等待当任务选择等待时，将被按FIFO或优先级顺序放置在等待队列中,释放信号量,功能：释放一个应用指定的信号量。if 没有任务等待这个信号量then 信号量的值加1 else 将信号量分配给一个等待任务（将相应的任务 移出等待队列，使其就绪）如果使用了优先级继承或优先级天花板算法，那么执行该功能（系统调用）的任务的优先级将恢复到原来的高度。,删除信号量,功能：从系统中删除应用指定的一个信号量内核动作：将信号
33、量控制块返还给系统删除信号量的不一定是创建信号量的任务如果有任务正在等待获得该信号量，执行此功能将使所有等待这个信号量的任务回到就绪队列中，且返回一个状态码指示该信号量已被删除,清除信号量的任务等待列表,为了清除等待一个信号量的所有任务，某些内核支持Flush操作，以便释放信号量等待任务列表中的所有任务。当多个任务的执行必须在某些点相遇时，需要这样的机制。,第二节邮箱和消息队列,通信方式概述消息队列机制的主要数据结构典型的消息队列操作,任务间的通信方式,消息：内存空间中一段长度可变的缓冲区，其长度和内容均可以由用户定义，其内容可以是实际的数据、数据块的指针或空。为了能高效率地实现进程通信，操作
34、系统设计了多种高级通信原语send(A)原语和receive(A)原语,消息,send(A)(读取消息)原语send(A)原语用来发送消息，A是发送进程提供的发送区起始地址send(A)原语先申请一个消息缓冲区，然后把发送区的内容复制到消息缓冲区中。然后找到接收进程的PCB，把消息缓冲区连入接收进程的消息缓冲区队列中代码,消息,procedure send（A）；bengin new（p）；p.sptr=address of sends PCB;mov message to buffer p;find the receives PCB;p(mutex);add the buffer p to
35、the massage queue;v(sm);v(mutex);end；,消息,receive(A)(读取消息)原语receive(A)原语用来读取消息，A是接收进程提供的接收区起始地址receive(A)原语把消息缓冲区中的消息内容、消息长度以及发送进程的名字读取到接收区，然后把消息缓冲区从链表中去掉，并释放消息缓冲区如果没有消息可读取，则阻塞接收进程，直至消息发送来为止,消息,procedure receive（A）bengin P(Sm);p(mutex);move out a buffer F from the message queue of the Receive;v(mutex
36、);move senders name and text from buffer F to receiber;end；,进程p,send,发送区（消息）,进程q,receive,接受区（消息）,hptr,mutex,sm,PCB,nptr,消息,消息通信的分类：直接通信方式 发送进程直接把消息发送到目标进程Send(P，message)发送一个消息到任务PReceive(Q，message)从任务Q接收一个消息 间接通信方式，也叫信箱通信方式 进程间的通信需要通过作为某种共享数据结构的实体信箱。send(A，message)发送一个消息给邮箱Areceive(A，message)从邮箱A接收一
37、个消息,消息、消息队列、邮箱,内核一般提供以下邮箱服务：,消息邮箱与信号量最大的区别：消息邮箱可以存放一条完整的内容信息，而用信号量进行行为同步时，只能提供同步时刻的信息，不能提供内容信息。,如果邮箱内有消息，则任务将消息从邮箱中取走；如果邮箱内没有消息，则内核不将该任务挂起(ACCEPT)，返回空指针。,内核,POST,内容初始化,PEND,ACCEPT,邮箱内消息的内容初始化，此时邮箱内是否有消息并不重要；,等待有消息进入邮箱(PEND)；,将消息放入邮箱(POST)；,消息邮箱,满,消息指针PC,空,一般来说，消息邮箱只有2种状态：即空状态（消息邮箱中没有消息）、满状态（消息邮箱中存放了
38、消息）。,消息邮箱的状态,满,空,1.向消息邮箱发送消息,有任务在等待消息,任务优先级足够高,PC,获得消息,注意：如果发送消息指针是以广播的形式发送，那么所有等待此消息的任务都获得消息,无任务在等待消息,PC,PC,返回错误码说明消息邮箱已满,操作成功,PC,发送失败,OSMboxPost()对应以上3种情形,消息邮箱,满,空,2.从消息邮箱接收消息,PC,PC,操作成功,延时中获得消息，操作成功,设定延时到，无消息，返回超时错误,PC,空,满,另一个任务（或中断服务程序）向消息邮箱发出消息,PC,OSMboxPend()对应以上3种情形,消息邮箱,消息队列就象一个类似于缓冲区的对象，通过消
39、息队列任务和ISR发送和接收消息，实现数据的通信和同步。消息队列具有一定的容量，可以容纳多条消息，因此可以看成是多个邮箱的组合。,PC,PC,PC,PC,PC,PC,FIFO,PC,PC,PC,PC,PC,PC,提高消息在队列中的优先级实现LIFO算法,LIFO,消息队列,等待消息的到来（PEND）；,将消息放入队列中去（POST）；,无等待取得消息，如果消息队列中有消息，则任务将消息从消息队列中取走；如果消息队列为空，则内核不将该任务挂起，返回空指针。,内核一般提供以下消息队列服务：,与信号量和邮箱相比，消息队列的最大优点就是通过缓冲的方式来传递多个消息，从而避免了信息的丢失或混乱。,内核,
40、POST,初始化,PEND,ACCEPT,消息队列初始化，队列初始化时总是清为空；,消息队列,一般来说，消息队列有3种状态，即空状态（消息队列中没有任何消息）、满状态（消息队列中的每个存储单元都存放了消息）、正常状态（消息队列中消息但又没有到满的状态）。,空状态,正常状态,满状态,消息队列,消息队列状态图,非空,满,队列创建消息数为0,消息队列状态图,消息发送消息数加1,空,消息发送消息数为1,消息接收消息数为0,消息接收消息数减1,消息接收消息数减1,消息发送消息数等于队列长度,消息队列机制的主要数据结构,消息队列及其相关的参数和支持数据结构,1.向消息队列发送消息,有任务在等待消息,任务优
41、先级足够高,PC,获得消息,注意：如果发送消息指针是以广播的形式发送，那么所有等待此消息的任务都获得消息,当任务向消息队列中发送消息时，它首先判断是否有任务在等待消息队列的消息。,OSQPost()对应3种情形,消息队列,未满,无任务在等待消息,PC,返回错误码说明消息队列已满,操作成功,PC,如果没有任务在等待消息队列的消息，那么就会再判断消息队列当前是否已满。,发送失败,已满,OSQPost()对应3种情形,消息队列,101,2.从消息队列接收消息,PC,消息队列中已存在消息，通过内核服务将消息传递给等待消息的任务中优先级最高的任务，或最先进入等待消息任务列表的任务。,操作成功,任务优先级
42、足够高,获得消息,OSQPend()对应3种情形,消息队列,102,如果消息队列为空，则等待消息的任务被放入等待消息的任务列表中，直到有其它任务向消息队列发送消息后才能解除该等待状态或在超时的情况下运行。,PC,延时中获得消息，操作成功,任务优先级足够高,获得消息,PC,OSQPend()对应3种情形,消息队列,103,一般来说，OSQPend()函数允许用户定义一个最长的等待时间Timeout作为它的参数，这样可以避免该任务无休止地等待下去。,任务优先级足够高,设定延时到，无消息，返回超时错误,一直无消息,超时,OSQPend()对应3种情形,消息队列,发送和接收消息的消息拷贝和内存使用这种
43、消息传递方法效率低、占用空间大一种效率更高的方式是传递消息指针,消息的发送或接收的两种方法,number_of_message,max_message_count,消息队列控制块,消息队列缓冲区,消息队列机制的主要数据结构,消息队列的环形缓冲,消息队列机制的主要数据结构,max_message_count,queue_end,queue_start,queue_out,number_of_message,queue_in,消息指针,典型的消息队列操作,创建消息队列发送普通消息发送紧急消息发送广播消息接收消息删除消息队列获取有关消息队列的各种信息,创建消息队列,创建消息队列时，调用者可以指定如下
44、参数：消息的最大长度每个消息队列中最多的消息数消息队列的属性任务等待消息时的排队方式：FIFO或PRIORITY系统为新创建的消息队列分配唯一的ID,发送消息,接收消息,删除消息队列,从系统中删除指定的消息队列，释放消息队列控制块及消息队列缓冲区。任何知道此消息队列ID号的代码都可以删除它。消息队列被删除后，所有等待从这个消息队列接收消息的任务得到一个错误信息表明消息队列已被删除都回到并回到就绪态。,消息队列的其他典型使用,紧耦合的单向数据通信：发送任务发送消息后要求一个响应信号，表明接收任务已经成功接收到消息。,消息队列的其他典型使用,紧耦合的双向数据通信：如果数据需要在任务之间双向流动，则
45、可以采用紧耦合的双向数据通信模式（也称为全双工通信）。,第三节管道,概述管道机制的主要数据结构典型的管道操作管道机制的典型应用,管道机制概述,管道（pipe）是提供非结构化数据交换和实现任务间同步的内核对象。在传统的实现中，管道是单向数据交换设施。,Task1,Task2,管道,管道中的数据,写描述符,读描述符,向管道写数据,从管道读数据,数据在管道内像一个非结构字节流，按FIFO的次序从管道中读出。当管道空时，阻塞读者，当管道满时，阻塞写者。,管道机制概述,管道允许有多个读者和写者。,管道,管道的状态转换图,非空,满,创建管道无写入数据,读数据，有剩余数据,空,写数据,读数据，无数据留下,写
46、数据，有剩余空间,读数据,写数据，无剩余空间,管道机制的主要数据结构,典型的管道操作,选择（Select）操作 int select(int nfds,fd_set*readfds,fd_set*writefds,fd_set*exceptfds,struct timeval*timeout);Select操作允许一个任务阻塞并等待一个或多个管道上的一个指定条件的发生。,Task1,ISR,Task2,Task3,任务Task3等待从Pipe1和Pipe2这两个管道读数据并写到第三个管道Pipe3上。在这种情况下，当头两个管道中的任意一个有数据时，Select调用返回。,用来让程序监视多个文件
47、描述符(file descrptor)的状态变化的,管道机制的典型应用,Task A,Task B,Select操作,Select操作,管道C,管道D,任务A和任务B打开两个管道作为任务间的通信方式：打开管道C作为从任务A到任务B的数据传输，打开管道D作为从任务B到任务A的回应。任务A等待管道C编程可写，也等待管道D上来自任务B的回应。,两个任务之间的同步,管道主要用于任务到任务或ISR到任务的数据传输,第四节事 件,概述事件机制的主要数据结构典型的事件操作事件机制的典型应用,在嵌入式实时内核中，事件是指一种表明预先定义的系统事件已经发生的机制。事件机制用于任务与任务之间、任务与ISR之间的同
48、步。其主要的特点是可实现一对多的同步。一个事件就是一个标志，不具备其它信息。一个或多个事件构成一个事件集。事件集可以用一个指定长度的变量（比如一个8bit,16bit或32bit的无符号整型变量，不同的操作系统其具体实现不一样）来表示，而每个事件由在事件集变量中的某一位来代表。,概述,事件及事件集有以下特点：事件间相互独立事件仅用于同步，不提供数据传输功能事件无队列，即多次发送同一事件，在未经过任何处理的情况下，其效果等同于只发送一次。提供事件机制的意义在于：当某任务要与多个任务或中断服务同步时，就需要使用事件机制。若任务需要与一组事件中的任意一个发生同步，可称为独立型同步（逻辑“或”关系）。
49、任务也可以等待若干事件都发生时才同步，称为关联型同步（逻辑“与”关系）。,概述,“或”同步和“与”同步,概述,任务,任务,任务,任务,ISR,ISR,OR,AND,“与”型同步,“或”型同步,事件集,事件集,POST,POST,PEND,PEND,用多个事件的组合发信号给多个任务,概述,任务,任务,任务,ISR,OR,AND,事件集,事件集,事件集（8，16或32位）,POST,PEND,PEND,术语：发送事件集。指在一次发送过程中发往接收者（比如任务）的一个或多个事件的组合。待处理事件集。指已被发送到一个接收者但还没有被接收（即正在等待处理）的所有事件的集合。事件条件。指事件接收者在一次接
50、收过程中期待接收的一个或多个事件的集合。“或”同步：待处理事件集只要包括事件条件中的任一事件即可满足要求；“与”同步：其二是待处理事件集必须包括事件条件中的全部事件方可满足要求。,概述,事件机制的主要数据结构,（1）事件集控制块结构（Event_set_Control_Block）：attribute 事件集的属性（排队方式:FIFO或PRIORITY）event_set 当前事件集（指示被置位且未被接受的事件标志位）eventset_condition_queue_and 事件集”与”等待队列 eventset_condition_queue_or 事件集”或”等待队列 内核为每个等待事件集
