状态机模型并发进程模型

《状态机模型并发进程模型》由会员分享，可在线阅读，更多相关《状态机模型并发进程模型（51页珍藏版）》请在金锄头文库上搜索。

1、嵌入式系统设计： 硬件/软件的统一状态机模型、并发进程模型1Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 概要模型与语言的比较状态机模型FSM/FSMDHCFSM 和状态图表语言程序状态机模型 (PSM)并发进程模型通信同步实现数据流模型实时系统2Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 嵌入式系统处理行为的描述描述起来或

2、许非常困难随着IC容量的增加，复杂度也随之增加。嵌入式早期应用：洗衣机、小游戏等仅有数百行的程序代码如今的应用：电视机机顶盒和手机等。可能需要几十万行的程序代码在设计初期，所需的行为甚至不能完全让人理解，许多的系统缺陷都是描述不清造成的。使用英语或其它自然语言来描述所需行为，这是合理描述的第一步。但是，这样做仍然不够，因为自然语言并不精确。如： 发动机相关代码，达数千页之长。引言3Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 模型与语言我们如何用计算模型描述所

3、需的系统行为呢?我们可许想到用计算机语言 来描述，如，C、 C+等。计算模型可以帮助设计者理解和描述行为。常见的计算模型时序程序模型（ Sequential program model ）提供一组语句、语句规则以及说明语句如何执行的语义。通信进程模型（ Communicating process model ）该模型支持对多进程的并发执行。状态机模型（ State machine model ）该模型用于以控制为主的系统，监视控制输入、设置控制输出。数据流模型（ Dataflow model ）该模型用于以数据为主的系统，把数据输入流转换成输出数据流。面向对象模型（Object-oriente

4、d model）该模型用于将复杂的软件分解为简单而确定的片断。4Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 模型与语言计算模型描述系统行为如，菜谱，时序程序。语言可以捕获模型具体形式，如，C语言、英语等。时序模型可以用不同的语言来表达例如，C、C+、或JAVA 一种语言还可以描述很多不同的模型例如，C+语言可以描述时序模型、面向对象模型、状态机模型某些程序语言可能比其它语言更容易表达计算模型模型语言食谱西班牙语英语日语诗词故事时序程序C+CJava状态机数据

5、流食谱与英文食谱与英文时序程序与时序程序与C语言语言5Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 文字语言与图形语言模型/语言、文字/图形不能相混淆。文字和图形仅仅是语言的两种形式文本：如字母、数字。图形:X = 1;Y = X + 1;X = 1Y = X + 16Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 简单实例：一

6、个电梯控制系统简单控制器请求解决器 ： 协调不同的楼层请求，确定一个被请求楼层。单元控制器： 移动电梯到达请求楼层我们可以尝试用C语言来描述将电梯向上或向下移动到被请求楼层;到达被请求楼层后，打开电梯门至少10秒，并一直保持打开状态，直到被请求楼层改变。确保电梯在移动中绝不会打开。不能改变电梯移动方向，除非向上移动时没有更高层请求或向下移动时没有更低层请求。部分文字描述部分文字描述电梯内的按钮单元控制器b1downopenfloor.请求解决器.各层的上/下按钮b2bNup1up2dn2dnNrequp系统界面系统界面up3dn37Embedded Systems Design: A Unif

7、ied Hardware/Software Introduction, (c) 2000 Vahid/Givargis 使用时序程序模型进行描述 将电梯向上或向下移动到被请求楼层;到达被请求楼层后，打开电梯门至少10秒，并一直保持打开状态，直到被请求楼层改变。确保电梯在移动中绝不会打开。不能改变电梯移动方向，除非向上移动时没有更高层请求或向下移动时没有更低层请求。部分文字描述部分文字描述电梯内的按钮单元控制器b1downopenfloor.请求解决器.各层的上/下按钮b2bNup1up2dn2dnNrequp系统介面系统介面up3dn3时序程序模型时序程序模型void UnitControl(

8、) up = down = 0; open = 1; while (1) while (req = floor); open = 0; if (req floor) up = 1; else down = 1; while (req != floor); up = down = 0; open = 1; delay(10); void RequestResolver() while (1) . req = . .void main() Call concurrently: UnitControl() and RequestResolver()Inputs: int floor; bit b1.

9、bN; up1.upN-1; dn2.dnN;Outputs: bit up, down, open;Global variables: int req;8Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 有限状态机模型（FSM）如果我们用时序程序模型来描述该行为似乎是一件令人头疼的事。相反，我们可以考虑用FSM来描述系统行为。可能的状态如， Idle, GoingUp, GoingDn, DoorOpen 。针对一个输入可能产生的从一种状态到另一种状态的转换如，

10、 req floor每个状态下的行为操作。如， 在GoingUp状态下， u,d,o,t = 1,0,0,0 (up = 1, down, open, and timer_start = 0)9Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 有限状态机模型IdleGoingUpreq floorreq floor) !(timer 10)req flooru,d,o, t = 1,0,0,0u,d,o,t = 0,0,1,0u,d,o,t = 0,1,0,0u,

11、d,o,t = 0,0,1,1U表示UP（上）、d表示down（下）、o表示open（打开）req = floor!(reqfloor)timer 10T表示计时器的启动信号timer_start使用状态机描述的使用状态机描述的UnitControl进程进程10Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 正式的定义FSM一个6元组 F其中S是状态的集合s0, s1, , slI 输入的集合 i0, i1, , imO 是输出的集合 o0, o1, , onF

12、 是次态集合 (S x I S)H 是输出函数，将状态映射到输出 (S O)s0 是初始状态摩尔型（Moore）输出仅与状态有关 。米莱型（Mealy）输出仅与状态转移有关。使用速记符进行一些简化描述可以认为在状态中未赋值的输出为0.每个转移条件隐含着与有效时钟沿相与。11Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 具有数据路径的有限状态机模型 (FSMD)FSMD是对 FSM的扩展，如增加了复杂数据类型和存储数据的变量。FSMs 仅使用布尔类型来进行运算，

13、没有变量。FSMD模型可以定义为一个7元组F S 是状态的集合 s0, s1, , slI 是输入的集合 i0, i1, , imO 是输出的集合 o0, o1, , onV 是变量的集合是变量的集合 v0, v1, , vnF 是次态的集合 (S x I x V S)H 操作函数 (S O + V)S0是初始状态I,O,V 可以描述复杂的数据类型 (如，整数、浮点数等)。F,H 可以代表算术运算。在此没有将H 称为输出函数，而是称做操作函数。因为它不仅描述输出，而且也描述变量的更新。对于该模型，完整的系统状态不仅包括当前状态，而且还包括所有变量的值。IdleGoingUpreq floorr

14、eq floor) !(timer 10)req flooru,d,o, t = 1,0,0,0u,d,o,t = 0,0,1,0u,d,o,t = 0,1,0,0u,d,o,t = 0,0,1,1u is up, d is down, o is openreq = floor!(reqfloor)timer floor!(req floor) u,d,o, t = 1,0,0,0u,d,o,t = 0,0,1,0u,d,o,t = 0,1,0,0u,d,o,t = 0,0,1,1u is up, d is down, o is openreq floorreq = floorreq floo

15、r!(reqfloor)!(timer 10)timer floor) state = GOINGUP; if (req floor) state = GOINGUP; if (!(reqfloor) state = DOOROPEN; break; GOINGDN: up=1; down=0; open=0; timer_start=0; if (req floor) state = GOINGDN; if (!(reqfloor) state = DOOROPEN; break; DOOROPEN: up=0; down=0; open=1; timer_start=1; if (time

16、r 10) state = DOOROPEN; if (!(timerfloorreqfloor)timeout(10)reqflooru,d,o = 1,0,0u,d,o = 0,0,1u,d,o = 0,1,0req=floor!(req1u,d,o = 0,1,0u,d,o = 0,0,1!fireFireDrOpenfloor=1fireu,d,o = 0,0,1单元控制器fire!fireFireGoingDnfloor1u,d,o = 0,1,0FireDrOpenfloor=1fire火警模式eu,d,o = 0,0,1有分级有分级IdleGoingUpreqfloorreqfl

17、oor)timeout(10)reqflooru,d,o = 1,0,0u,d,o = 0,0,1u,d,o = 0,1,0req=floor!(reqfloor)u,d,o = 0,0,1正常模式单元控制器正常模式火警模式月火警无火警单元控制器电梯控制器请求解决器.并发的请求解决器并发的请求解决器无分级，不易让人理解。有分级，易让人理解。20Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 程序状态机模型 (PSM)程序状态机允许用FSM或时序程序来定义其状态的

18、操作。设计者可以选择自己喜欢的方式。PSM的分级比状态图表的HCFSM 更严格。它只允许兄弟状态之间的转移 。它包含了一个程序状态完成的概念，程序状态可以是一个“完成”子状态。如果某一个程序状态是一个时序程序，则到达这个程序代码的终点表示该程序状态已完成。PSM可以加入一个特殊的完成子状态。PSM 有两种转移类型立即转移型 (TI): 表示在其转移条件成立时，立即发生转移，而不考虑源程序状态的情况。完成转移型 (TOC): 表示只有在条件满足且源程序状态是完成状态的情况下才会发生的转移。SpecCharts是一个用来表达PSM的VHDL的扩展语言。up = down = 0; open = 1

19、; while (1) while (req = floor); open = 0; if (req floor) up = 1; else down = 1; while (req != floor); open = 1; delay(10); 正常模式火警模式火警模式up = 0; down = 1; open = 0;while (floor 1);up = 0; down = 0; open = 1;有火警无火警单元控制器电梯控制器请求解决器.req = .int req;用时序语言描述正常模式和火警模式从FireMode到NormalMode的TOC转移，只有在FireMode完成后

20、才会发生。21Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 适当模型和语言的角色确定一种合适的模型来表达嵌入式系统是一个很重要的步骤。模型可以决定设计者考虑系统的方式。考虑模型是如何决定设计者对电梯控制器实例中UnitContro行为思考方式，为了建立图中所表达的时序程序，因此我们想到了一个操作序列。首先，等待被请求楼层不同于当前楼层。然后把门关上。再上移或下移到所需楼层。接着打开电梯门。然后重复该操作序列。为了建立一个状态机，我们应该想到系统状态和状态之间的

21、转移。当系统必须响应各种变化的输入时，状态机模型或许是最佳选择。HCFSM能更好、更清晰地描述火灾行为。语言能很容易表达所选择的模型理想情况下，语言应该具有可以直接表达模型特色的结构。用时序程序来表达火警模式应该非常复杂。因为必须在程序中到处插入检查火灾信号的程序代码。其它因素也要求我们考虑选择相应的模型。我们可以考虑使用结构化的技术。比如，可以用时序程序语言来表达状态机模型。22Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 并发进程模型系统的功能可以用多种计

22、算模型来描述由于并发进程固有的多任务性，许多系统的功能很容易用它来描述。一些简单的实例用户先提供2个数字X和Y 每隔X秒就在显示器上显示“Hello World”每隔Y秒就在显示器上显示“How are you?”我们可以试着用时序程序或状态机来描述。子程序执行时序子程序执行时序timeReadXReadYPrintHelloWorldPrintHowAreYou一个简单的并发进程实例一个简单的并发进程实例ConcurrentProcessExample() x = ReadX() y = ReadY() Call concurrently: PrintHelloWorld(x) and Pr

23、intHowAreYou(y)PrintHelloWorld(x) while( 1 ) print Hello world. delay(x); PrintHowAreYou(x) while( 1 ) print How are you? delay(y); 输入和输出实例输入和输出实例Enter X: 1Enter Y: 2Hello world. (Time = 1 s)Hello world. (Time = 2 s)How are you? (Time = 2 s)Hello world. (Time = 3 s)How are you? (Time = 4 s)Hello wor

24、ld. (Time = 4 s).23Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 数据流模型它是并发进程模型派生的一种模型。在该模型中，结点用来表示变换。可以并发执行在该模型中，边表示从一个结点到另一个结点的数据流向。每条边可能有、也可能没有数据当某个结点的所有输入边都至少有一个令牌时，该节点可触发（fire）。结点触发后，将使用每条输入边的一个令牌，对所有使用的令牌进行数据变换，并在输出边上产生一个令牌。多个结点可以同时触发。有几种商业工具支持用图形化语言

25、来表达数据流模型。这些工具可以自动将数据流模型转换为并发进程模型。它将每个结点转换为一个进程，每条边转换为一个通道。调制卷积变换ABCDZ表示更复杂变换的结点表示更复杂变换的结点t1t2+*ABCDZ表示算术变换的结点表示算术变换的结点t1t2Z = (A + B) * (C - D)24Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 同步数据流在很多数字信号处理系统中，数据流速是固定的。节点在每次触发中可以使用和产生多个令牌。同步数据流模型正是利用了这一点。在

26、每条边上标注了每次触发所使用和产生的令牌数。用静态方式调度节点，产生时序程序模型。不需要实时操作系统就可以执行。我们如何把这种模型映射为时序程序语言呢?开发用于节点调度的算法，其目标是将所有节点安排到多个“单外观”（single appearance）调度中。其中仅有一条调用每个结点相关程序的语句。这种调度允许程序内嵌指令（procedure inlining），避免了使用多条语句调用各节点的相关程序所造成的过渡膨胀现象，从而降低了系统开销。modulateconvolvetransformABCDZ同步数据流同步数据流mt1ct2mAmBmCmDtZtt1tt2t1t225Embedded

27、Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 并发进程与实时系统26Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 并发进程看两个实例：各自运行，但共享数据。用时序程序模型写一个系统是一件很困难的事，但用并发进程模型来实现却很容易。每个任务有各自的程序（进程）。进程间彼此通信B1.4心跳脉冲心跳监护系统Task 1:Read pulseIf pu

28、lse Hi then Activate SirenSleep 1 secondRepeatTask 2:If B1/B2 pressed then Lo = Lo +/ 1If B3/B4 pressed then Hi = Hi +/ 1Sleep 500 msRepeat机顶盒系统输入信号Task 1:Read SignalSeparate Audio/VideoSend Audio to Task 2Send Video to Task 3RepeatTask 2:Wait on Task 1Decode/output AudioRepeatTask 3:Wait on Task 1D

29、ecode/output VideoRepeatVideoAudio27Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 进程进程是一段连续的程序，通常是一个无穷循环。进程间并发执行。它将我们带入一个“程序同时执行”的世界。进程中的基本操作创建和终止（Create and Terminate）可以这样比喻， Create就像一个程序调用，但却不能像程序调用那样去等待。Create就是建立一个新进程。Terminate指停止正在执行的进程，并删除该进程的所有数据。在

30、HelloWord/HowAreYou的实例中, 我们创建了进程。暂停和恢复（Suspend and resume）Suspend 是指停止进程的执行，此外，还要保存进程的有关数据。Resume 是指允许被暂停进程再次执行。连接（Join）一个进程要暂停，直到它要连接的进程执行完为止。28Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 进程通信进程间需要进行数据和信号的通信以完成他们的计算任务。那些彼此不通信的进程仅仅是一些相互独立来完成各自任务的程序。实例:

31、生产者/消费者（Producer/Consumer）进程A生产数据元素、进程B消费数据元素如，进程A 对视频包进行解码、进程B把解码后的数据输出到显示器。进程间的通信方式有两种方式 共享存储器消息传递 processA() / Decode packet / Communicate packet to B void processB() / Get packet from A / Display packetEncoded video packetsDecoded video packetsTo display29Embedded Systems Design: A Unified Hardw

32、are/Software Introduction, (c) 2000 Vahid/Givargis 共享存储器进程间共用公共变量该方式容易实现。但不好用，经常出错。实例：生产者/消费者问题的一种错误解决方案共享缓冲区bufferN, countcount = # of valid data items in buffer进程A 生产数据元素并放入共享缓冲区中如果缓冲区满，则等待。进程B 消费共享缓冲区消费数据元素如果缓冲区空，则等待。当两个进程都试图改变 count值时，就会出错。 (lines 10 and 19) ，以下的执行序列将导致在count存入错误的值。假设count为3从存储器

33、中将count的值载入CPU寄存器 R1中 (R1 = 3)将 R1中的值加1 (R1 = 4)从存储器将 count (count = 3)的值载入CPU寄存器 R2中 (R2 = 3)将 R2的值减1 (R2 = 2)将 R1 的值存回count的存储器位置 (count = 4)将 R2 的值存回count 的存储器位置 (count = 2)经过上述执行序列后，count的值会被 错误地设置为201: data_type bufferN;02: int count = 0;03: void processA() 04: int i;05: while( 1 ) 06: produce(

34、&data);07: while( count = N );/*loop*/08: bufferi = data;09: i = (i + 1) % N;10: count = count + 1;11: 12: 13: void processB() 14: int i;15: while( 1 ) 16: while( count = 0 );/*loop*/17: data = bufferi;18: i = (i + 1) % N;19: count = count - 1;20: consume(&data);21: 22: 23: void main() 24: create_pr

35、ocess(processA); 25: create_process(processB);26: 30Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 消息传递消息传递进程间直接交换数据发送进程要发送数据给另一个进程的话，就执行一个特殊的 “send”操作。接收进程要接收数据，也要执行一个特殊的 “receive”操作。两个进程都需要有一个标识符（identifier），以明确将数据送给那个进程，或那个进程应该接收数据。receive操作可以被阻塞，但send操

36、作既可能是、也可能不是可阻塞的操作。消息传递模式的安全性高，但不够灵活。void processA() while( 1 ) produce(&data) send(B, &data); /* region 1 */ receive(B, &data); consume(&data); void processB() while( 1 ) receive(A, &data); transform(&data) send(A, &data); /* region 2 */ 31Embedded Systems Design: A Unified Hardware/Software Introdu

37、ction, (c) 2000 Vahid/Givargis 共享存储器: 互斥某些程序代码不能被同时执行。关键段（Critical section）它也可能不是连续的程序代码段，在这个代码段中，多个处理器同时更新共享存储器位置。当一个进程进入Critical section后，其它的进程必须被锁定，直到该进程退出Critical section为止。互斥（Mutex）互斥是一个共享对象，具有两个分别用于锁定和解锁共享数据段的操作。锁定（Lock）和解锁（Unlock）。不允许对其所保护的共享存储器进行多个读写存取。多个进程可以同时执行锁定操作，但只有一个进程能取得锁。其它试图获得锁的进程进入

38、阻塞状态，无法进入程序代码的关键段，直到拥有锁的进程退出关键段之后，将执行解锁操作。然后，这些进程将返回到可执行状态，再去竞争以取得锁。32Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 生产者/消费者问题的一种正确解决方法我们用基元（primitive）互斥（mutex）来锁住程序代码的关键段，使得在该代码段内同时只有一个进程在执行。下边的内容是一段跟以前相同功能的执行序列A/B：对 count_mutex 执行 lock操作A or B 有一个获得锁假设B

39、获得A 被阻塞B ：从存储器将count的值载入寄存器 R2 (R2 = 3)B ：R2的值减1 (R2 = 2)B ：将R2的值返回到count的存储器位置 (count = 2)B ：执行unlock操作A可再次执行A ：从存储器中将count的值载入 R1 (R1 = 2)A ：将 R1的值加1 (R1 = 3)A ：将R1的值存回 count 的存储器位置 (count = 3)Count 的值被正确地修改为 301: data_type bufferN;02: int count = 0;03: mutex count_mutex;04: void processA() 05: in

40、t i;06: while( 1 ) 07: produce(&data);08: while( count = N );/*loop*/09: bufferi = data;10: i = (i + 1) % N;11: count_mutex.lock();12: count = count + 1;13: count_mutex.unlock();14: 15: 16: void processB() 17: int i;18: while( 1 ) 19: while( count = 0 );/*loop*/20: data = bufferi;21: i = (i + 1) % N

41、;22: count_mutex.lock();23: count = count - 1;24: count_mutex.unlock();25: consume(&data);26: 27: 28: void main() 29: create_process(processA); 30: create_process(processB);31: 33Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 进程通信我们可以尝试对电梯控制器中“req” 的值进行建模使

42、用共享存储器方式使用共享存储器和互斥操作使用消息传递 方式buttonsinsideelevator控制单元b1downopenfloor.请求解决器.up/downbuttons on eachfloorb2bNup1up2dn2dnNrequp系统界面系统界面up3dn334Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 并发程序设计中的一个常见问题：死锁死锁（Deadlock）：在这种情况下，多个进程都被阻塞，互相等待对方的关键段解锁。多个进程都处于锁定状

43、态都不能执行解锁操作，从而相互一直永远等待。实例中，有两个关键段可能被并发执行。需要两个锁 (mutex1, mutex2)下面的执行序列可能产生死锁A ：对 mutex1执行lock操作 (A取得锁mutex1)B ：对 mutex2执行lock( B取得锁mutex2)A/B ：分别执行关键段1和2A ：对 mutex2执行lock操作A被阻塞，直到B将 mutex2解锁B ：对 mutex1执行lock操作B被阻塞，直到A将 mutex1解锁这时就产生了死锁消除死锁的一种协议是，只允许以递增顺序锁定经过编号的互斥体，除此之外，还需二阶段锁定(2PL)。获取第一阶段锁定，解除第二阶段锁定。

44、01: mutex mutex1, mutex2;02: void processA() 03: while( 1 ) 04: 05: mutex1.lock();06: /* critical section 1 */07: mutex2.lock();08: /* critical section 2 */09: mutex2.unlock();10: /* critical section 1 */11: mutex1.unlock();12: 13: 14: void processB() 15: while( 1 ) 16: 17: mutex2.lock();18: /* crit

45、ical section 2 */19: mutex1.lock();20: /* critical section 1 */ 21: mutex1.unlock();22: /* critical section 2 */23: mutex2.unlock();24: 25: 35Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 进程同步有时，并发运行的进程必须同步执行。当一个进程等待：另一进程以计算某个数值到达执行中的某个点告知某种情况再次回忆producer

46、/consumer 问题如果缓冲区满的话，进程A 等待。如果缓冲区空的话，进程B 等待。上面的情况，我们称之为忙等等待的进程只是进行空操作CPU 时间白白浪费更有效的方法我们前边讨论的连接操作及可阻塞的发送和接收基元它们都是阻塞忙等的进程，从而不浪费CPU的时间。条件变量和监视程序36Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 条件变量条件变量（Condition variable ）是一个具有两个操作的对象，分别是： signal操作和 wait操作。在一

47、个条件变量下，执行等待操作的进程被阻塞，直到另一进程完成对该条件变量的singnal操作。具体是咋做的呢?进程A 取得互斥锁然后，进程A 执行等待，传给等待操作一个互斥变量。等待操作对该互斥进行解锁进程B 可以获取相同的锁进程B 进入关键段计算某个值或使某个条件变为成立当条件成立时，进程B执行signal操作从而使进程 A 可再次取得该互斥的锁进程 A 变为可执行的状态37Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 条件变量实例：consumer/produ

48、cer问题两个条件变量buffer_empty说明缓冲区中是否至少有一个可用的空位置buffer_full说明缓冲区中是否至少有一个有效的数据进程A: 生产一个数据元素取得关键段的锁检查count的值if count = N, buffer is full对条件变量 buffer_empty执行wait操作对自己锁的关键段进行解锁，从而使进程B进入关键段，来消费数据元素，并释放一个缓冲位置。进程B 执行 signal操作if count N, buffer is not full进程A 给 buffer中添加数据元素 Count值增1告知进程B，至少有一个新的数据元素可供使用。01: data

49、_type bufferN;02: int count = 0;03: mutex cs_mutex;04: condition buffer_empty, buffer_full;06: void processA() 07: int i;08: while( 1 ) 09: produce(&data);10: cs_mutex.lock();11: if( count = N ) buffer_empty.wait(cs_mutex);13: bufferi = data;14: i = (i + 1) % N;15: count = count + 1;16: cs_mutex.unl

50、ock();17: buffer_full.signal();18: 19: 20: void processB() 21: int i;22: while( 1 ) 23: cs_mutex.lock();24: if( count = 0 ) buffer_full.wait(cs_mutex);26: data = bufferi;27: i = (i + 1) % N;28: count = count - 1;29: cs_mutex.unlock();30: buffer_empty.signal();31: consume(&data);32: 33: 34: void main

51、() 35: create_process(processA); create_process(processB);37: 使用条件变量实现生产者使用条件变量实现生产者/消费者问题的同步消费者问题的同步38Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 监视程序监视程序是一组数据作用于该数据的方法或子程序，与面向对象实例中的对象类似。它可以保证任何时间只有一个进程可以在监视程序内运行。(a)如果进程X执行时，进程Y必须等待。(b) 如果进程X对某个条件变量执行等

52、待操作那么，允许进程Y进入监视程序。(c) 如果进程Y告知该条件变量，进程X正在等待进程Y被阻塞允许进程X 继续执行(d) 如果进程X终止或等待某个条件，则进程Y允许再次进入监视程序。进程 X监视程序数据代码(a)进程Y进程X监视程序数据代码(b)进程 Y进程X监视程序数据代码(c)进程 Y进程 X监视程序数据代码(d)进程Y等待等待39Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 监视程序实例: consumer/producer问题使用监视程序来封装生产者

53、/消费者进程的时序程序，共享的buffer也被封装在监督程序内。一个进程可以允许被首先执行。假设进程B允许首先执行它将执行，直到进程B发现count=0为止这时，它将对buffer_full条件变量执行等待操作允许进程A进入监督程序进程A产生一个数据元素当进程A发现count N 时，就向buffer中添加一个数据元素，并且给让count加1.进程A通过告知操作 告知 buffer_full条件变量进程A被阻塞进程B可以再次进入监视程序并执行，来消费数据元素01: Monitor 02: data_type bufferN;03: int count = 0;04: condition buf

54、fer_full, condition buffer_empty;06: void processA() 07: int i;08: while( 1 ) 09: produce(&data);10: if( count = N ) buffer_empty.wait();12: bufferi = data;13: i = (i + 1) % N;14: count = count + 1;15: buffer_full.signal();16: 17: 18: void processB() 19: int i;20: while( 1 ) 21: if( count = 0 ) buff

55、er_full.wait();23: data = bufferi;24: i = (i + 1) % N;25: count = count - 1;26: buffer_empty.signal();27: consume(&data);28: buffer_full.signal();29: 30: 31: /* end monitor */32: void main() 33: create_process(processA); create_process(processB);35: 40Embedded Systems Design: A Unified Hardware/Soft

56、ware Introduction, (c) 2000 Vahid/Givargis 实现把系统的功能映射到硬件处理器系统的功能可以使用多种计算模型来描述也可能用多种语言去描述实现的选择与语言的选择是相互独立的。实现的选择基于处理器的性能、大小、时间和成本因素。最终的实现还要进行可行性测试。最终还依赖于是否适合进行大规模的生产制造。计算模型的选择取决于该计算模型是否允许设计者描述系统语言的选择取决于该语言是否能表达设计者的计算模型。实现的选择取决于该实现是否满足功率、大小、性能和成本时序程序状态机数据流并发进程C/C+PascalJavaVHDL实现A实现B实现C41Embedded Syst

57、ems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 并发进程模型：实现本节将使用单用途或通用处理器来实现方法一：使用多处理器，每个处理器执行一个进程真正的多任务 (进程间并行运行)使用通用处理器使用C语言来描述进程的功能，再将其编译成处理器的指令但这种方法非常昂贵，在多数情况下没必要使用。普通的单用途处理器更常用方法二：用一个通用处理器执行所有进程大多数进程并没有使用CPU100%的时间。很多进程可以共享一个处理器的时间，仍能以要求的速度执行。方法三：前两种的综合多进程共享一个通用处理器，同

58、时一个或多个进程也可以在各自的单用途处理器上执行。Process1Process2Process3Process4Processor AProcessor BProcessor CProcessor DCommunication Bus(a)(b)Process1Process2Process3Process4General Purpose ProcessorProcess1Process2Process3Process4Processor AGeneral Purpose ProcessorCommunication Bus(c)42Embedded Systems Design: A Un

59、ified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 实现：多进程共享单用途处理器方法一：用手工方式将这些进程改写为一个时序程序。对简单应用而言，这种方式是可行的，但对复杂的应用而言，则实现起来极为困难。我们可以借助一些自动化技术帮助完成这项改写工作，但这种方法并不常用。如，我们前面讨论过的 Hello World 程序 。:I = 1; T = 0;while (1) Delay(I); T = T + 1;if X modulo T is 0 then call PrintHelloWorldif Y modulo T

60、is 0 then call PrintHowAreYou方法二：使用多任务操作系统。这种方法较常用。操作系统负责进程调度、存储空间分配、与外设的接口等。实时操作系统 (RTOS) 能够保证进程的执行速度受到约束。我们可以选择使用内建进程的语言 (Java, Ada, etc.)来描述并发进程，也可以使用时序程序语言(C, C+)描述。但使用时序程序语言的话，需要使用例程库来扩展该语言，以支持并发进程。方法三：将进程转变为内含进程调度器的时序程序。该方法额外成本低 (不依赖操作系统)但该方法实现起来很复杂，而且不易维护。43Embedded Systems Design: A Unified

61、Hardware/Software Introduction, (c) 2000 Vahid/Givargis 进程与线程的比较在操作系统的术语中，两者是不同的。普通进程重量级进程拥有自己的虚拟地址空间 (堆栈、数据、程序代码)它有自己的系统资源 (如，打开文件)线程轻量级进程它是进程内的子进程仅有程序计数器、堆栈和寄存器与其它进程共享地址空间和系统资源允许线程间更快速的通信它比进程小可以被快速创建线程间的切换系统开销也较小44Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Gi

62、vargis 进程暂停和恢复、进程连接用单任务处理器实现多个进程进程的暂停和恢复必须作为这些处理器实现的一部分来实现。可为处理器多设计一个输入信号，该信号把处理器设置为暂停状态。还需要用附加逻辑来表明处理器是否在执行。额外的输出信号用来表明处理器的完成。用一个通用处理器来实现多个进程进程的暂停和恢复必须在描述这些进程的程序设计语言或特殊的多任务函数库内实现。程序语言或函数库都需要依靠操作系统来处理这些操作。45Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 进程

63、调度用通用处理器来实现多进程时，这些并发进程必须考虑时序要求。对多任务处理器而言，则没有这方面的要求。调度：它是一个用来决定每个进程何时、以何种方式、被执行多长时间的一个特殊进程。分为抢占式调度和非抢占式调度两种抢占式调度进程执行一段预定时间，然后将其逐出，以允许其他进程在处理器上执行。这段预定时间，称为时间配额(可能有几十到几百毫秒长)决定下一个将要被执行的进程。非抢占式调度只决定当前进程执行完后，下一个将要执行的进程。46Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Giv

64、argis 调度：优先级问题具有最高优先权的进程一定能第一个被调度器选中。进程的优先级通常是在进程创建时静态决定，可能在执行期间动态改变。FIFO调度器当进程创建后或变成可执行时，将其加入到FIFO对列中。而在当前正在执行的进程配额已用完或进程被阻塞时，可以将其他进程从FIFO对列中移出，并使其在处理器上执行。优先级队列当进程创建后或变成可执行时，再一次将其加入到FIFO对列中。当调度器选择新进程来执行时，只需要选择优先级最高的进程。当多个进程具有相同优先级时，调度器根据先来先服务的原则进行选择。如果使用的是非抢占式调度器，该调度方式我们称为优先级调度法。如果使用的是抢占式调度器，该调度方式我

65、们称为轮盘调度法。47Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 优先级分配进程的周期它是指重复的时间间隔，在这个时间间隔内，进程只能执行一次。如，周期 = 100 ms ，则进程必须每隔100ms执行一次。进程的周期是由系统的描述来决定的如，负责更新显示设备上的屏幕的进程，必须每秒执行27次，相当于周期是37ms。执行期限（execution deadline）它可以定义为一段约束时间，进程必须在这个时间之内完成执行。如， 执行时间是 5 ms，期限是20

66、 ms，周期是 100 ms。则进程必须在开始执行后的20ms内完成。这说明进程A开始执行后，可以执行4ms，接着休眠14ms，再恢复执行1ms。则该进程从开始执行到结束的总共时间为4+14+1=19ms。比期限小，说明这种调度有效。周期单调调度法这种方法中，周期较短的进程会分配到较高的优先级。当执行期限等于周期时，这种方法很常用。期限单调调度法这种方法中，执行期限较短的进程会分配到较高的优先级。当执行期限小于周期时，这种方法很常用。ProcessABCDEFPeriod25 ms50 ms12 ms100 ms40 ms75 msPriority536142ProcessGHIJKLDead

67、line17 ms50 ms32 ms10 ms140 ms32 msPriority523614周期单调优先级分配周期单调优先级分配期限单调优先级分配期限单调优先级分配48Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 实时系统实时系统是由2个或2个以上并发进程组成的系统，这些进程必须按严格的时间要求执行，并且彼此合作，以实现共同目标。如，机顶盒中，为了使输出影像连续，每秒钟至少要对20个视频帧进行解码，所以它用一个进程进行读取图像或声音，另一进程进行图像或声

68、音的解码。其它对实时操作有严格要求的实例有：手机导航和进程控制系统组装线监视系统多媒体和网络系统 以上这些系统中，进程间的通信和同步是很关键的。因此，并发进程模型最适合描述这些系统。49Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 实时操作系统(RTOS)RTOS是为建立真正实时的嵌入式系统提供机制、基本功能元件和指导原则。Windows CE特别为嵌入式系统和家电市场而开发，提供了实时的32位平台。支持Windows API。特别适合用于与互联网连接的系统。

69、采用抢占式优先权调度法，每个进程有256个优先级。内核大小为约400KB。QNX由实时微核及周围的可选进程组成，并提供与POSIX 和UNIX 兼容的系统微核仅仅支持最基本的服务可选资源管理允许从小的基于ROM的系统扩展到通过网络和通信技术连接的大型的多处理系统采用抢占式优先权调度法，包括先入先出服务（FIFO）、轮盘（round-robin）自适应（adaptive）和 优先权驱动（priority-driven）等调度法。每个进程由32 个优先级，微核不到 10 Kbytes， 符合 POSIX 实时标准。50Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis 总结计算模型和语言是不同的时序程序模型很流行大部分常见语言，比如c语言都直接支持该模型。状态机模型更适用于以控制为主的系统状态机模型的扩展，例如HCFSM提供了额外的功能PSM 综合了状态机和时序程序模型并发进程模型适用于描述多任务系统存在通信与同步的方法调度是关键数据流模型适合描述信号处理51