实时操作系统同步、互斥与通信.ppt
《实时操作系统同步、互斥与通信.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,并回送显示器 任何程序可以重复地调用此过程,接收用户输入,并在用户的屏幕上显示,考虑一个支持单用户单处理器、多道程序设计系统 将其当作一个共享过程,载入到所有应用程序公用的全局存储区中。这样每个应用程序都能使用这个过程,由于每个应用程序只
3、需使用echo过程的一个副本,从而节省空间 进程间共享主存是非常有用的,它允许进程间有效而紧密的交互,有利于进程的相互通信。但是,共享也可能会带来一些问题,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
4、() ; chout = chin; putchar(chout) ; ,P2,资源 正忙,唤 醒,在单处理器平台上,嵌入式操作系统内核提供的同步、互斥与通信机制主要包括: 信号量(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 = c
6、ount; R1+; R2+; count = R1; count = R2; (设count的初始值为5) 为互斥地使用临界资源,需保证进程互斥地进 入临界区。,临界资源和临界区,临界区的进入准则 空闲让进:临界资源空闲时,允许进程进入临界区 忙着等待:临界资源正在被访问时,其他需要进入临界区的进程必须等待 有限等待:保证进程在有效的时间内进入临界区,避免“死等” 让权等待:当进程不能进入临界区时,应立即释放处理机,以免其它进程“忙等”,临界资源和临界区,进程互斥进入临界区的实现方法 硬件方法 禁止中断 在进程进入临界区之后,禁止该进程中断 专用机器指令 TS指令,Swap指令 软件方法 信
7、号量和PV操作,临界资源和临界区,信号量是一个数据结构,其定义如下: struct semaphore int value; struct PCB * queue; 信号量semaphore包括一个整型值和一个等待队列。信号量只能通过P原语和V原语访问。,什么是信号量,什么是信号量,信号量被定义为一个整形变量,在其上定义了以下三个操作: 1、可以被初始化一个非负数 2、wait操作(P操作)将信号量的值减1后,若该值为负,则执行wait操作的任务等待 3、signal操作(V操作)将信号量的值增1后,若该值为非正,则执行signal操作的任务唤醒,P 原语 P(S) S := S - 1; 如
8、果 S =0,则表示有资源,该进程继续执行; 如果 S 0,则表示已无资源,执行原语的进程被置成阻塞状态,并使其在 S 信号量的队列中等待,直至其他进程在 S 上执行 V 操作释放它为止,P原语,P原语,(1)若信号量S大于0,则将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);/
9、阻塞进程 ,P原语,V 原语 V(S) S := S + 1 如果 S 0,则该进程继续执行 如果 S 0,说明有进程被挂起,则唤醒一阻塞进程,即从S信号量的等待队列首摘下一个PCB,将其置为就绪状态,执行 V(S) 者继续执行 P操作可能会引起进程的阻塞,V操作不会引起本身进程状态的变化,但可能唤醒其他进程,使其从阻塞状态转变到就绪状态,V原语,V原语,(1)若信号量S的等待队列中有等待进程,则取队首进程,将其置为就绪状态并返回。 (2)否则信号量S加1,并放回,V原语,是否有等待进程,S=S+1,返回,取队首进程置为就绪态,否,是,V原语操作原型 void signal (semaphor
10、e s) s.value = s.value + 1; if (s.value =0) wakup(s.queue);/唤醒进程 ,V原语,P原语的作用 申请临界资源,如果该资源正被其他进程使用,则等待。 V原语的作用 释放临界资源,如有其他进程等待该资源,则唤醒。 使用PV原语可以解决进程的互斥和同步,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
11、=1,v(s) S=s+1=2,哲学家就餐问题,某天的某个地方,有5位哲学家住在一起,每位哲学家的生活就是思考和吃饭。通过多年的思考,所有的哲学家一致同意最有助于他们思考的食物是意大利面条 吃饭的布置很简单:一个圆桌上有一大碗面,5个盘子,每位哲学家一个,还有5根筷子。每个想吃饭的哲学家将坐到桌子旁分配给他的位置上,使用盘子两侧的筷子,夹面条吃。,问题是:设计一个算法以允许哲学家吃饭。算法必须保证互斥 (没有两个哲学家同时使用同一根筷子) ,同时还要避免死锁和饿死,死锁的产生,为克服死锁危险,可以再另买5跟筷子 (一个更卫生的解决方案) 或者教会哲学家仅用一跟筷子吃面 另一种方法是,考虑增加一
12、位服务员,他只允许4位哲学家同时坐上餐桌吃饭,由于最多有4位哲学家就座,因而至少有一位哲学家可以拿到两跟筷子,这里再次使用了信号量。,哲学家就餐问题,类似资源定序的解决方案: 规定哲学家取筷子的顺序:单号哲学家先取右边的筷子再取左边的筷子;双号哲学家先去左边的筷子再取右边的筷子。 在取第一根筷子时总有哲学家没拿到筷子,因此必定能保证有一个哲学家能取到另一边的筷子,吃完面后,将筷子给其他哲学家用。,哲学家就餐问题, 4.5死锁,信号量用于实现任务与任务之间、任务与中断处理程序之间的同步与互斥。 信号量一般分为三种:,信号量的种类及用途,用于解决互斥问题。它比较特殊,可能会引起优先级反转问题。,用
13、于解决同步问题,用于解决资源计数问题,将信号量进行种类细分,可以根据其用途,在具体 实现时做专门处理,提高执行效率和可靠性。,互斥信号量,计数信号量,二值信号量,一般地,如果有n个进程共享某一临界资源,则先找出每个进程的临界区,再使用PV原语实现进入和退出临界区: semaphone mutex; P(mutex); 临界区; V(mutex); ,信号量实现进程互斥,例如:卖机票的进程实现互斥 semaphone mutex = 1; P(mutex); value = count; /count为剩余机票数量(临界资源) if (value = 1) value = value 1; co
14、unt = value; /打印一张机票; else /显示机票已售完; V(mutex);,信号量实现进程互斥,用信号量实现任务间的互斥,var mutex:Shared Semaphore; begin mutex:=1; parbegin P1: P2: Pi:repeat Wait(mutex); “进程Pi的临界代码段”; Signal(mutex); forever Pn: parend end,互斥信号量,WaitB(S): /申请信号量 if S.value1; /当前没有其他任务使用信号量 then S.value=S.value-1=0/将信号量值修改为0,独占共享资源 e
15、lse begin Insert(CALLER,S.L); /如果当前有其他任务使用信号量,将该任务放入等待 队列 Block(CALLER); /修改该任务的状态为等待态(阻塞任务) end SignalB(S): /释放信号量 if S.L queue is empty; /如果等待序列为空,没有其他任务等待使用该共享资源 then S.value=1; /释放信号量 else begin Remove(S.L,id); /如果有其他任务等待使用该共享资源,则从等待队列中 将该任务移除 wakeup(id); /将该任务的状态改为就绪态(唤醒任务) end,互斥信号量状态图,互斥信号量状态
16、图,各种互斥机制比较,二值信号量,可获得,不可获得,申请并获得 (值为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() 申请信号量sem1; 执行一些操作; 将信号量sem2置1; ,Task2申请信号量sem1失败,系统切换到Task1,sem1被置1后,Task2
17、得到sem1并抢占Task1,Task2运行到某处时因某种原因被阻塞,系统切换到Task1,用二值信号量实现两个任务之间的双向同步 Task2优先级高于Task1 sem1和sem2的初始值均为0,二值信号量实现同步,计数信号量,计数信号量,计数信号量状态图,可获得,不可获得,初始化 值大于0,申请并获得 值为0,释放 值为1,申请并获得 值减1,释放 值加1,计数(一般)信号量同步原语,Wait(S): S.value:= S.value-1; /有新任务来使用共享资源将信号量的值减1 if S.value0 /如果信号量的值为负,表示共享资源已经分配完毕 then begin Insert
18、(CALLER,S.L);/将该任务插入等待序列 Block(CALLER); /将该任务状态改为等待态(阻塞任务) end Signal(S): S.value:= S.value+1; /任务使用完共享资源,将信号量的值加1,释放 一个信号量 if S.value=0 /如果信号量为负,表示仍有等待该资源的任务被 阻塞 then begin Remove(S.L,id); /将等待队列中的一个任务从队列中移除 wakeup(id); /将该任务的状态修改为就绪态,唤醒任务 end S的绝对值表示在该信号量列表中已阻塞的任务数目,计数信号量,计数信号量使用实例:有界缓冲问题,生产者-消费者问
19、题,生产者-消费者模型,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,c4,ci,. . .,. . .,生产
20、者/消费者问题,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+1) m
21、od 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); /退出
22、缓冲区 V(empty); /唤醒生产者进程 ,生产者-消费者问题,生产者消费者问题中需注意的问题: 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 producer
23、1; producern; consumer1; consumerm; parend end,58,生产者任务 begin repeat 生产数据 /生产者生产数据 Wait(E); /减少一个空缓冲区项 Wait(mutex); /分配空缓冲区和移动指针P操作是互斥的 “分配空缓冲区并调整指针P的临界段”; “向空缓冲区中装入数据” Signal(mutex); /释放互斥信号量 Signal(F); /增加一个满缓冲区项 forever end,消费者任务 begin repeat 消费数据 /消费者取走数据 Wait(F); /减少一个满缓冲区项 Wait(mutex); /分配满缓冲区
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实时 操作系统 同步 通信
链接地址:https://www.31doc.com/p-2897904.html