同步互斥与通信.ppt

嵌入式系统及应用第六章 同步、互斥与通信主要内容概述信号量邮箱和消息队列管道ISR xTask yPOSTPEND任务与任务与任务与任务与ISRISR之间的同步之间的同步之间的同步之间的同步（单向）（单向）（单向）（单向）Task xTask yPOSTPENDPOSTPEND任务与任务任务与任务任务与任务任务与任务之间的同步之间的同步之间的同步之间的同步（双向）（双向）（双向）（双向）任务与任务任务与任务任务与任务任务与任务之间的同步之间的同步之间的同步之间的同步（单向）（单向）（单向）（单向）Task xTask yPOSTPEND在单处理器平台上，嵌入式操作系统内核提供的同步、互斥与通信机制主要包括：信号量（semaphore），用于互斥与同步事件（组）（event group），用于同步异步信号（asynchronous signal），用于同步邮箱（mailbox）、消息队列（message queue），用于消息通信管道（pipe），提供非结构化数据交换和实现同步 以下一些机制也可用于同步与通信（在单处理器或多处理器系统中）：全局变量共享内存Sockets远程过程调用（Remote Procedure Call）第一节信号量信号量的种类及用途信号量的种类及用途信号量的定义信号量的定义互斥信号量互斥信号量二值信号量二值信号量计数信号量计数信号量信号量机制的主要数据结构信号量机制的主要数据结构典型的信号量操作典型的信号量操作什么是信号量信号量被定义为一个整形变量，在其上定义了以下三个操作：1、可以被初始化一个非负数2、wait操作（P操作）将信号量的值减1后，若该值为负，则执行wait操作的任务等待3、signal操作（V操作）将信号量的值增1后，若该值为非正，则执行signal操作的任务唤醒 信号量用于实现任务与任务之间、任务与中断处理程序之间的同步与互斥。信号量一般分为三种：信号量的种类及用途用于解决互斥问题。它比较特殊，可能用于解决互斥问题。它比较特殊，可能会引起优先级反转问题。会引起优先级反转问题。用于解决同步问题用于解决同步问题用于解决资源计数问题用于解决资源计数问题将信号量进行种类细分，可以根据其用途，在具体将信号量进行种类细分，可以根据其用途，在具体实现时做专门处理，提高执行效率和可靠性。实现时做专门处理，提高执行效率和可靠性。互斥信号量 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);/如果有其他任务等待使用该共享资源，则从等待队列中如果有其他任务等待使用该共享资源，则从等待队列中 将该任务移除将该任务移除 wakeup(id);/将该任务的状态改为就绪态将该任务的状态改为就绪态(唤醒任务唤醒任务)end用信号量实现任务间的互斥var mutex:Shared Semaphore;begin mutex:=1;parbegin P1:P2:Pi:repeat Wait(mutex);“进程Pi的临界代码段”；Signal(mutex);forever Pn:parend endTask1Task2共享资源共享资源互斥信号量状态图互斥信号量状态图互斥信号量状态图开启开启锁定锁定初始化初始化值为值为1申请并获得申请并获得值为值为0释放释放值为值为1申请申请(递归递归)并获得并获得锁定数加锁定数加1释放释放(递归递归)锁定数减锁定数减1各种互斥机制比较比较项目比较项目关中断关中断使用测试并置使用测试并置位指令位指令禁止任务禁止任务切换切换使用信号量使用信号量锁定范围锁定范围互互斥斥力力度度最最强强，锁定所有外部可屏蔽中断，凡是以中断形式到达的外部事件以及与之相关联的任务或处理过程均得不到执行凡是使用该指令访问共享资源的代码所有的任务只只影影响响竞竞争争共共享资源的任务享资源的任务对系统响应时对系统响应时间的影响间的影响如果关中断的时间较长，对系统的响应性能有很大影响较小如果禁止切换的时间过长，则影响系统的响应性能对对系系统统响响应应性性能能有有一一定定影影响响，可可能能导导致优先级反转致优先级反转实现时的系统实现时的系统开销开销小小小较大较大注意事项注意事项关关中中断断时时间间要要尽量短尽量短不不是是所所有有的的处处理理器器都都具具备备这这种种指指令令，影响可移植性影响可移植性关关调调度度的的时时间间要尽量短要尽量短需需采采用用一一定定的的策策略略解解决决优优先先级反转问题级反转问题二值信号量可获得可获得不可获得不可获得申请并获得申请并获得(值为值为0)释放释放(值为值为1)初始化初始化值为值为0二值信号量状态图二值信号量状态图Task1()执行一些操作执行一些操作;将信号量将信号量sem1置置1;申请信号量申请信号量sem2;Task2()申请信号量申请信号量sem1;执行一些操作执行一些操作;将信号量将信号量sem2置置1;Task2申申请请信信号号量量sem1失失败败，系系统统切换到切换到Task1sem1被被 置置 1后后，Task2得得 到到 sem1并并抢占抢占Task1Task2运运行行到到某某处处时时因因某某种种原原因因被被阻阻塞塞，系系统统切切换换到到Task1用二值信号量实现两个任务之间的双向同步用二值信号量实现两个任务之间的双向同步用二值信号量实现两个任务之间的双向同步用二值信号量实现两个任务之间的双向同步 Task2Task2优先级高于优先级高于优先级高于优先级高于Task1Task1 sem1sem1和和和和sem2sem2的初始值均为的初始值均为的初始值均为的初始值均为0 0二值信号量实现同步 计数信号量Task1Task2共享资源实例共享资源实例nTask m共享资源实例共享资源实例1计数信号量计数信号量状态图计数信号量状态图可可获获得得不可不可获获得得初始化初始化值值大于大于0申申请请并并获获得得值为值为0释释放放值为值为1申申请请并并获获得得值值减减1释释放放值值加加1计数(一般)信号量同步原语Wait(S):S.value:=S.value-1;/有新任务来使用共享资源将信号量的值减1 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的绝对值表示在该信号量列表中已阻塞的任务数目计数信号量Var E,F:Semaphore;mutex:binary Semaphore;begin(*main program*)F:=0;E:=n;mutex=1;parbegin producer1;producern;consumer1;consumerm；parendend信号量机制的主要数据结构SCB1SCB2信号量控制信号量控制块块count信号量名字或信号量名字或IDTask1Task2任任务务等待列表等待列表信号量机制的主要数据结构信号量控制块：管理所有创建的信号量，内核在系统运行时动态分配和回收信号量控制块互斥和二值信号量控制块结构:Binary_Semaphore_Control_Blockwait_queue任务等待队列任务等待队列attributes信号量属性信号量属性lock_nesting_behavior 试图嵌套获得时的规则试图嵌套获得时的规则 wait_discipline 任务等待信号量的方式任务等待信号量的方式priority_ceiling 优先级天花板值优先级天花板值lock是否被占有是否被占有holder拥有者拥有者 nest_count嵌套层数嵌套层数计数信号量控制结构Counting_Semaphore_Control_Block wait_queue任务等待队列任务等待队列 attributes计数信号量属性计数信号量属性 maximum_count 最大计数值最大计数值 wait_discipline任务等待信号量的方式任务等待信号量的方式 count当前计数值当前计数值信号量机制的主要数据结构典型的信号量操作创建信号量获取（申请）信号量释放信号量删除信号量清除信号量的任务等待列表 获取有关信号量的各种信息 创建信号量功能：根据应用传递的参数创建一个信号量参数：信号量的名字、属性和初始值等。内核动作：从空闲信号量控制块链中分配一个信号量控制块，并初始化信号量属性。创建成功时，为其分配唯一的ID号返回给应用。如果已创建信号量数量已达到用户配置的最大数量，就返回错误。信号量的属性信信号号量量的的属属性性信号量的类型互斥信号量（互斥信号量（MUTEX_SEMAPHORE）计数信号量（计数信号量（COUNTING_SEMAPHORE）二值信号量（二值信号量（BINARY_SEMAPHORE）任务等待信号量的方式先进先出（先进先出（FIFO）顺序）顺序优先级（优先级（PRIORITY）顺序）顺序优先级反转问题的解决方法（只适用于互斥信号量）优先级继承算法（优先级继承算法（INHERIT_PRIORITY）优先级天花板算法优先级天花板算法(PRIORITY_CEILING)，需给，需给出所有可能获得此信号量的任务中优先级最高出所有可能获得此信号量的任务中优先级最高的任务的优先级。的任务的优先级。获取（申请）信号量功能：试图获得应用指定的信号量。该功能流程如下：if 信号量的值大于0then 将信号量的值减1else 根据接收信号量的选项，将任务放到等待 队列中，或是直接返回获取（申请）信号量当所申请的信号量不能被立即获得时，可以有以下几种选择：永远等待 不等待，立即返回，并返回一个错误状态码指定等待时限（可有效避免死锁）注意：不允许在ISR中选择等待当任务选择等待时，将被按FIFO或优先级顺序放置在等待队列中释放信号量功能：释放一个应用指定的信号量。if 没有任务等待这个信号量then 信号量的值加1 else 将信号量分配给一个等待任务（将相应的任务 移出等待队列，使其就绪）如果使用了优先级继承或优先级天花板算法，那么执行该功能（系统调用）的任务的优先级将恢复到原来的高度。删除信号量功能：从系统中删除应用指定的一个信号量内核动作：将信号量控制块返还给系统删除信号量的不一定是创建信号量的任务如果有任务正在等待获得该信号量，执行此功能将使所有等待这个信号量的任务回到就绪队列中，且返回一个状态码指示该信号量已被删除清除信号量的任务等待列表为了清除等待一个信号量的所有任务，某些内核支持Flush操作，以便释放信号量等待任务列表中的所有任务。当多个任务的执行必须在某些点相遇时，需要这样的机制。SignalTaskTask2 二值信号量二值信号量初值为初值为0FlushTask1Task3第二节邮箱和消息队列通信方式概述通信方式概述消息队列机制的主要数据结构消息队列机制的主要数据结构典型的消息队列操作典型的消息队列操作任务间的通信方式任务间的通信方式:直接通信直接通信 间接通信间接通信 消息：消息：内存空间中一段长度可变的缓冲区，其长内存空间中一段长度可变的缓冲区，其长度和内容均可以由用户定义，其内容可以是实际度和内容均可以由用户定义，其内容可以是实际的数据、数据块的指针或空。的数据、数据块的指针或空。消息进一步分为：邮箱和消息队列消息队列机制的主要数据结构队队列控制列控制块块队队列列长长度度QCB1队队列名或列名或IDTask3Task4接收任接收任务务等待列等待列表表Task1Task2发发送任送任务务等待列等待列表表最大最大消息消息长长度度QCB2消息队列及其相关的参数和支持数据结构消息队列及其相关的参数和支持数据结构 Sending TaskReceiving TaskMessage1Message1Message1发送任务的发送任务的内存区域内存区域消息队列的消息队列的内存区域内存区域接收任务的接收任务的内存区域内存区域1st copy2nd copy发送和接收消息的消息拷贝和内存使用发送和接收消息的消息拷贝和内存使用发送和接收消息的消息拷贝和内存使用发送和接收消息的消息拷贝和内存使用 这种消息传递方法效率低、占用空间大这种消息传递方法效率低、占用空间大这种消息传递方法效率低、占用空间大这种消息传递方法效率低、占用空间大 一种效率更高的方式是传递消息指针一种效率更高的方式是传递消息指针一种效率更高的方式是传递消息指针一种效率更高的方式是传递消息指针消息的发送或接收的两种方法number_of_messagemax_message_countnumber_of_messagemax_message_sizewait_disciplinewait_queuequeue_startqueue_inqueue_outqueue_endmessagemessagemessagemessagemessagemessagemessagemessagemessagemax_message_count消息队列消息队列控制块控制块消息队列消息队列缓冲区缓冲区消息队列机制的主要数据结构消息队列的环形缓冲消息队列的环形缓冲消息队列的环形缓冲消息队列的环形缓冲消息队列机制的主要数据结构max_message_countqueue_endqueue_startqueue_outnumber_of_messagequeue_in消息指针消息指针消息队列状态图非空非空满满队列创建队列创建消息数为消息数为0消息队列状态图消息队列状态图消息发送消息发送消息数加消息数加1空空消息发送消息发送消息数为消息数为1消息接收消息接收消息数为消息数为0消息接收消息接收消息数减消息数减1消息接收消息接收消息数减消息数减1消息发送消息发送消息数等于队列长度消息数等于队列长度典型的消息队列操作创建消息队列发送普通消息发送紧急消息发送广播消息接收消息删除消息队列获取有关消息队列的各种信息 创建消息队列创建消息队列时，调用者可以指定如下参数：消息的最大长度每个消息队列中最多的消息数消息队列的属性任务等待消息时的排队方式：FIFO或PRIORITY系统为新创建的消息队列分配唯一的ID 发送消息Msg 3接收任务接收任务等待列表等待列表Msg 2Msg 1消息队列消息队列发送普通消息先进先出发送普通消息先进先出（FIFO）次序）次序Msg 3接收任务接收任务等待列表等待列表Msg 2Msg 1消息队列消息队列发送紧急消息后进先出发送紧急消息后进先出（LIFO）次序）次序接收消息Task 4High消息队列消息队列接收任务等待列表接收任务等待列表任务等待列表基于任务等待列表基于优先级的次序优先级的次序Task 2mediumTask 3mediumTask 1LowTask 4High消息队列消息队列接收任务等待列表接收任务等待列表任务等待列表先进先出任务等待列表先进先出（FIFO）次序）次序Task 2mediumTask 3mediumTask 1Low删除消息队列从系统中删除指定的消息队列，释放消息队列控制块及消息队列缓冲区。任何知道此消息队列ID号的代码都可以删除它。消息队列被删除后，所有等待从这个消息队列接收消息的任务得到一个错误信息表明消息队列已被删除都回到并回到就绪态。消息队列的其他典型使用紧耦合的单向数据通信：发送任务发送消息后要求一个响应信号，表明接收任务已经成功接收到消息。Task1Task2 消息队列的其他典型使用紧耦合的双向数据通信：如果数据需要在任务之间双向流动，则可以采用紧耦合的双向数据通信模式（也称为全双工通信）。Task1Task2第三节管道概述概述管道机制的主要数据结构管道机制的主要数据结构典型的管道操作典型的管道操作管道机制的典型应用管道机制的典型应用管道机制概述管道（pipe）是提供非结构化数据交换和实现任务间同步的内核对象。在传统的实现中，管道是单向数据交换设施。Task1Task2管道管道管道中的数据管道中的数据写描述符写描述符读读描述符描述符向管道向管道写数据写数据从管道从管道读读数据数据数据在管道内像一个非结构字节流，按数据在管道内像一个非结构字节流，按FIFOFIFO的次序从管道的次序从管道中读出。当管道空时，阻塞读者，当管道满时，阻塞写者。中读出。当管道空时，阻塞读者，当管道满时，阻塞写者。管道机制概述管道允许有多个读者和写者。Task1Task5管道管道Task2Task3Task4Task6ISR1ISR2ISR3公共管道操作公共管道操作管道管道的状态转换图非空非空满满创创建管道建管道无写入数无写入数据据读读数据，有数据，有剩余数据剩余数据空空写数据写数据读读数据，数据，无数据留无数据留下下写数据，有写数据，有剩余空剩余空间间读读数据数据写数据，无写数据，无剩余空剩余空间间管道机制的主要数据结构管道控制管道控制块块Byte countData bufferBuffer sizeOutput positionInput positionTask3Task4接收任接收任务务等待列表等待列表Task1Task2发发送任送任务务等待列表等待列表典型的管道操作选择（Select）操作 Select操作允许一个任务阻塞并等待一个或多个管道上的一个指定条件的发生。Task1ISRTask2Task3Pipe1Pipe2Pipe3任务任务Task3Task3等待从等待从Pipe1Pipe1和和Pipe2Pipe2这两个管道读数这两个管道读数据并写到第三个管道据并写到第三个管道Pipe3Pipe3上。在这种情况下，上。在这种情况下，当头两个管道中的任意当头两个管道中的任意一个有数据时，一个有数据时，SelectSelect调用返回。调用返回。管道机制的典型应用Task ATask BSelect操作操作Select操作操作管道管道C管道管道D任务任务A A和任务和任务B B打开两个打开两个管道作为任务间的通信管道作为任务间的通信方式：打开管道方式：打开管道C C作为从作为从任务任务A A到任务到任务B B的数据传的数据传输，打开管道输，打开管道D D作为从任作为从任务务B B到任务到任务A A的回应。任的回应。任务务A A等待管道等待管道C C编程可写，编程可写，也等待管道也等待管道D D上来自任务上来自任务B B的回应。的回应。两个任务之间的同步管道主要用于任务到任务或管道主要用于任务到任务或ISRISR到任务的数据传输到任务的数据传输第四节事 件概述概述事件机制的主要数据结构事件机制的主要数据结构典型的事件操作典型的事件操作事件机制的典型应用事件机制的典型应用在嵌入式实时内核中，事件是指一种表明预先定义的系统事件已经发生的机制。事件机制用于任务与任务之间、任务与ISR之间的同步。其主要的特点是可实现一对多的同步。一个事件就是一个标志，不具备其它信息。一个或多个事件构成一个事件集。事件集可以用一个指定长度的变量（比如一个8bit,16bit或32bit的无符号整型变量，不同的操作系统其具体实现不一样）来表示，而每个事件由在事件集变量中的某一位来代表。概述事件及事件集有以下特点：事件间相互独立事件仅用于同步，不提供数据传输功能事件无队列，即多次发送同一事件，在未经过任何处理的情况下，其效果等同于只发送一次。提供事件机制的意义在于：当某任务要与多个任务或中断服务同步时，就需要使用事件机制。若任务需要与一组事件中的任意一个发生同步，可称为独立型同步（逻辑“或”关系）。任务也可以等待若干事件都发生时才同步，称为关联型同步（逻辑“与”关系）。概述“或或或或”同步和同步和同步和同步和“与与与与”同步同步同步同步概述任务任务任务任务任务任务任务任务ISRISRORAND“与与”型同步型同步“或或”型同步型同步事件集事件集事件集事件集POSTPOSTPENDPEND用多个事件的组合发信号给多个任务用多个事件的组合发信号给多个任务用多个事件的组合发信号给多个任务用多个事件的组合发信号给多个任务概述任务任务任务任务任务任务ISRORAND事件集事件集事件集事件集事件集事件集（8，16或或32位）位）POSTPENDPEND术语：发送事件集。指在一次发送过程中发往接收者（比如任务）的一个或多个事件的组合。待处理事件集。指已被发送到一个接收者但还没有被接收（即正在等待处理）的所有事件的集合。事件条件。指事件接收者在一次接收过程中期待接收的一个或多个事件的集合。“或”同步：待处理事件集只要包括事件条件中的任一事件即可满足要求；“与”同步：其二是待处理事件集必须包括事件条件中的全部事件方可满足要求。概述事件机制的主要数据结构（1）事件集控制块结构（Event_set_Control_Block）：attribute 事件集的属性（排队方式:FIFO或PRIORITY）event_set 当前事件集（指示被置位且未被接受的事件标志位）eventset_condition_queue_and 事件集”与”等待队列 eventset_condition_queue_or 事件集”或”等待队列 内核为每个等待事件集的任务生成一个“任务事件集等待控制块”（2）任务事件集等待控制块结构（Event_set_Task_Waited_Buddy）task 等待任务的控制块指针 event_set 任务当前等待的事件集 flag_node_array 任务等待标志节点数组 任务等待标志节点数组的长度等于事件集的位数，其中每个节点元素对应一个 等待的事件标志典型的事件操作创建事件集删除事件集发送事件（集）接收事件（集）获取有关事件集的各种信息 创建事件集、删除事件集创建事件集：申请空闲事件集控制块，设置事件集属性，初始化控制块中的域（当前事件集、“与”/“或”等待队列），分配ID号删除事件集：回收事件集控制块到空闲链中，等待接收该事件集的任务被恢复就绪接收事件（集）在接收事件（集）时可以有如下选项WAITNO_WAIT接收事件（集）时可等待接收事件（集）时可等待接收事件（集）时不等待接收事件（集）时不等待接收者永远等待，直到事件接收者永远等待，直到事件条件被满足后成功返回；条件被满足后成功返回；接收者根据指定的时限等待。接收者根据指定的时限等待。EVENT_ALLEVENT_ANY待处理事件集必须包含事件条件中的全部事件方可满足要求，待处理事件集必须包含事件条件中的全部事件方可满足要求，即按照即按照“与与”条件接收事件条件接收事件待处理事件集只要包含事件条件中的任一事件即可满足要求，待处理事件集只要包含事件条件中的任一事件即可满足要求，即按照即按照“或或”条件接收事件条件接收事件发送事件（集）调用者（任务或中断）构造一个事件（集），将其发往接收者（比如目标任务）。可能会出现以下几种情况之一：目标任务正在等待的事件条件得到满足，任务就绪；目标任务正在等待的事件条件没有得到满足，该事件（集）被按“或”操作，保存到目标任务的待处理事件集中，目标任务继续等待；目标任务未等待事件（集），该事件（集）被按“或”操作，保存到目标任务的待处理事件集中。获取有关事件集的各种信息 获取有关事件集的各种信息：包括活动事件集的列表，事件集的名称和ID等。设设置事件置事件设设置事件置事件Task1ISR来自某设备的来自某设备的中断中断Task2消息队列消息队列Q事件标志集事件标志集信号量信号量S01000100发发送消息送消息释释放信号量放信号量接收消息接收消息获获取信号取信号量量事件机制的典型应用解决复杂的应用设计问题发送方（发送方（Task1Task1或或ISRISR）发送信息（消息）发送信息（消息或信号量）；或信号量）；发送方（发送方（Task1Task1或或ISRISR）设置相应的事件）设置相应的事件标志（指示消息或信号标志（指示消息或信号量的发送）；量的发送）；接收方（接收方（Task2Task2）检）检测事件标志集，判断是测事件标志集，判断是否满足其接收条件（否满足其接收条件（“与与”条件接收或条件接收或“或或”条件接收）；条件接收）；接收方（接收方（Task2Task2）根）根据事件标志集的指示定据事件标志集的指示定向接收信息（消息或信向接收信息（消息或信号量），达到和不同发号量），达到和不同发送方（送方（Task1Task1或或ISRISR）同）同步或通信的目的。步或通信的目的。适用情况：适用情况：Task2Task2，需要获得消息队列，需要获得消息队列Q Q的消息或得到信号量的消息或得到信号量S S，单纯使用获取消息操作，则可能被阻塞在消息队列上，无法及单纯使用获取消息操作，则可能被阻塞在消息队列上，无法及时得到信号量，反之亦然。时得到信号量，反之亦然。谢谢！谢谢！