状态机模型、并发进程模型.ppt

《状态机模型、并发进程模型.ppt》由会员分享，可在线阅读，更多相关《状态机模型、并发进程模型.ppt（51页珍藏版）》请在三一办公上搜索。

1、1,状态机模型、并发进程模型,2,概要,模型与语言的比较状态机模型FSM/FSMDHCFSM 和状态图表语言程序状态机模型(PSM)并发进程模型通信同步实现数据流模型实时系统,3,嵌入式系统处理行为的描述描述起来或许非常困难随着IC容量的增加，复杂度也随之增加。嵌入式早期应用：洗衣机、小游戏等仅有数百行的程序代码如今的应用：电视机机顶盒和手机等。可能需要几十万行的程序代码在设计初期，所需的行为甚至不能完全让人理解，许多的系统缺陷都是描述不清造成的。使用英语或其它自然语言来描述所需行为，这是合理描述的第一步。但是，这样做仍然不够，因为自然语言并不精确。如：发动机相关代码，达数千页之长。,引言,4

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

3、ct-oriented model）该模型用于将复杂的软件分解为简单而确定的片断。,5,模型与语言,计算模型描述系统行为如，菜谱，时序程序。语言可以捕获模型具体形式，如，C语言、英语等。时序模型可以用不同的语言来表达例如，C、C+、或JAVA 一种语言还可以描述很多不同的模型例如，C+语言可以描述时序模型、面向对象模型、状态机模型某些程序语言可能比其它语言更容易表达计算模型,6,文字语言与图形语言,模型/语言、文字/图形不能相混淆。文字和图形仅仅是语言的两种形式文本：如字母、数字。图形:,X=1;Y=X+1;,X=1,Y=X+1,7,简单实例：一个电梯控制系统,简单控制器请求解决器：协调不同的

4、楼层请求，确定一个被请求楼层。单元控制器：移动电梯到达请求楼层我们可以尝试用C语言来描述,8,使用时序程序模型进行描述,9,有限状态机模型（FSM）,如果我们用时序程序模型来描述该行为似乎是一件令人头疼的事。相反，我们可以考虑用FSM来描述系统行为。可能的状态如，Idle,GoingUp,GoingDn,DoorOpen。针对一个输入可能产生的从一种状态到另一种状态的转换如，req floor每个状态下的行为操作。如，在GoingUp状态下，u,d,o,t=1,0,0,0(up=1,down,open,and timer_start=0),10,有限状态机模型,11,正式的定义,FSM一个6元

5、组 F其中S是状态的集合s0,s1,slI 输入的集合 i0,i1,imO 是输出的集合 o0,o1,onF 是次态集合(S x I S)H 是输出函数，将状态映射到输出(S O)s0 是初始状态摩尔型（Moore）输出仅与状态有关。米莱型（Mealy）输出仅与状态转移有关。使用速记符进行一些简化描述可以认为在状态中未赋值的输出为0.每个转移条件隐含着与有效时钟沿相与。,12,具有数据路径的有限状态机模型(FSMD),FSMD是对 FSM的扩展，如增加了复杂数据类型和存储数据的变量。FSMs 仅使用布尔类型来进行运算，没有变量。FSMD模型可以定义为一个7元组F S 是状态的集合 s0,s1,

6、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 称为输出函数，而是称做操作函数。因为它不仅描述输出，而且也描述变量的更新。对于该模型，完整的系统状态不仅包括当前状态，而且还包括所有变量的值。,Idle,GoingUp,req floor,req floor,!(req floor),!(timer 10),req floor,DoorOpen,GoingDn,

7、req floor,u,d,o,t=1,0,0,0,u,d,o,t=0,0,1,0,u,d,o,t=0,1,0,0,u,d,o,t=0,0,1,1,u is up,d is down,o is open,req=floor,!(reqfloor),timer 10,t is timer_start,We described UnitControl as an FSMD,13,将系统描述为状态机,1.列举所有可能的状态,2.声明所有的变量(本例中没有声明),3.对每个状态，列出到其他状态的所有可能的转移和相关的条件。,4.对于每个状态，列出相关操作,5.对每个状态，确保现有的转移条件下是互斥和完

8、整的。互斥是指两个条件不可能同时成立。否则的话，这个状态机是一个非确定性状态机完整性是指任意时间所有条件中总有一个条件成立。,u is up,d is down,o is open,t is timer_start,14,状态机与时序程序模型的比较,每种模型反映了对系统行为的不同考虑方式状态机模型：要求设计者要考虑所有可能的状态，以及所有可能输入条件下可能进行的所有状态转移。时序程序模型：它是通过一系列可重复执行或有条件执行的指令来变换数据的。状态机模型在许多场合中用来描述效果更好。因为用状态机来进行描述提供了更自然的计算方法。并不是因为它提供了一种图形化的表达方式。状态机描述可以用文字状态语

9、言表达(如，状态图)。而时序程序模型可以用图形来表达(如，流程图)。,15,用FSM表达其它的行为,如，当有消息时，电话应答机的灯光闪烁。如，一个简单的电话应答机，可以接听四个电话。如，一个简单的十字路口控制灯。,16,用时序程序语言来表达状态机,尽管使用状态机来描述，有许多的优点。但是，最流行的开发工具却使用时序程序设计语言。如C,C+,Java,Ada,VHDL,Verilog等。这些开发工具通常复杂而昂贵。所以必需保护这些开发工具的投资。用时序程序设计语言来表达状态机，通常有两种方法：前端工具法（Front-end tool）安装支持状态机的附加工具。这些工具常用来定义图形和文字状态机语

10、言也可能支持图形模拟这些工具自动产生时序程序设计语言代码，这些代码用于输入到主开发工具中。缺点:必须支持另外的工具(如，软件授权成本、版本升级等)语言子集法（Language subset approach）它是一种最常用的方法。,17,语言子集法,下面是用等价的时序程序语言来表达状态机模型使用软件设计语言C 和硬件设计语言VHDL用C来表达UnitControl状态机枚举所有可能的状态(#define)声明一个状态变量，交将其设置为初始状态(IDLE)多个状态分支每种状态的动作up,down,open,timer_start检查转移条件以确定下一状态if()state=;,#define I

11、DLE0#define GOINGUP1#define GOINGDN2#define DOOROPEN3void UnitControl()int state=IDLE;while(1)switch(state)IDLE:up=0;down=0;open=1;timer_start=0;if(req=floor)state=IDLE;if(req floor)state=GOINGUP;if(req floor)state=GOINGUP;if(!(reqfloor)state=DOOROPEN;break;GOINGDN:up=1;down=0;open=0;timer_start=0;i

12、f(req floor)state=GOINGDN;if(!(reqfloor)state=DOOROPEN;break;DOOROPEN:up=0;down=0;open=1;timer_start=1;if(timer 10)state=DOOROPEN;if(!(timer10)state=IDLE;break;,用时序程序语言表达状态机的通用模板,18,通用模板,#define S00#define S11.#define SNNvoid StateMachine()int state=S0;/or whatever is the initial state.while(1)switc

13、h(state)S0:/Insert S0s actions here,19,HCFSM 和状态图表语言,分级/并发有限状态机模型(HCFSM)它是对状态机模型的扩展，用于支持分级和并发它可将一个状态分解为另一个状态有分级的状态机模型和无分级的状态模型的功能基本上是一样的，但前者具有较少的状态转移。我们称之为或分解。状态可以并发执行我们称之为与分解状态图用图表语言描述 HCFSM超时（timeout）：是一个以时间约束作为其条件的转移。历史（history）：是一种记忆机制，可以记住一个或分解状态A在转移到到一个状态B之前所处的最近子状态。在重新回到状态A时，可以从所记住的子状态开始，而不必从

14、状态A的初始状态开始。,20,具有火灾模式的UnitControl状态机,火灾模式 当发生火灾时，电梯下移到第一层，然后打开电梯。,无分级,Idle,GoingUp,reqfloor,reqfloor,!(reqfloor),timeout(10),reqfloor,DoorOpen,GoingDn,reqfloor,u,d,o=1,0,0,u,d,o=0,0,1,u,d,o=0,1,0,req=floor,!(reqfloor),u,d,o=0,0,1,单元控制器,无分级，不易让人理解。,有分级，易让人理解。,21,程序状态机模型(PSM),程序状态机允许用FSM或时序程序来定义其状态的操作

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

16、malMode的TOC转移，只有在FireMode完成后才会发生。,22,适当模型和语言的角色,确定一种合适的模型来表达嵌入式系统是一个很重要的步骤。模型可以决定设计者考虑系统的方式。考虑模型是如何决定设计者对电梯控制器实例中UnitContro行为思考方式，为了建立图中所表达的时序程序，因此我们想到了一个操作序列。首先，等待被请求楼层不同于当前楼层。然后把门关上。再上移或下移到所需楼层。接着打开电梯门。然后重复该操作序列。为了建立一个状态机，我们应该想到系统状态和状态之间的转移。当系统必须响应各种变化的输入时，状态机模型或许是最佳选择。HCFSM能更好、更清晰地描述火灾行为。语言能很容易表达

17、所选择的模型理想情况下，语言应该具有可以直接表达模型特色的结构。用时序程序来表达火警模式应该非常复杂。因为必须在程序中到处插入检查火灾信号的程序代码。其它因素也要求我们考虑选择相应的模型。我们可以考虑使用结构化的技术。比如，可以用时序程序语言来表达状态机模型。,23,并发进程模型,系统的功能可以用多种计算模型来描述由于并发进程固有的多任务性，许多系统的功能很容易用它来描述。一些简单的实例用户先提供2个数字X和Y 每隔X秒就在显示器上显示“Hello World”每隔Y秒就在显示器上显示“How are you?”我们可以试着用时序程序或状态机来描述。,24,数据流模型,它是并发进程模型派生的一

18、种模型。在该模型中，结点用来表示变换。可以并发执行在该模型中，边表示从一个结点到另一个结点的数据流向。每条边可能有、也可能没有数据当某个结点的所有输入边都至少有一个令牌时，该节点可触发（fire）。结点触发后，将使用每条输入边的一个令牌，对所有使用的令牌进行数据变换，并在输出边上产生一个令牌。多个结点可以同时触发。有几种商业工具支持用图形化语言来表达数据流模型。这些工具可以自动将数据流模型转换为并发进程模型。它将每个结点转换为一个进程，每条边转换为一个通道。,25,同步数据流,在很多数字信号处理系统中，数据流速是固定的。节点在每次触发中可以使用和产生多个令牌。同步数据流模型正是利用了这一点。在

19、每条边上标注了每次触发所使用和产生的令牌数。用静态方式调度节点，产生时序程序模型。不需要实时操作系统就可以执行。我们如何把这种模型映射为时序程序语言呢?开发用于节点调度的算法，其目标是将所有节点安排到多个“单外观”（single appearance）调度中。其中仅有一条调用每个结点相关程序的语句。这种调度允许程序内嵌指令（procedure inlining），避免了使用多条语句调用各节点的相关程序所造成的过渡膨胀现象，从而降低了系统开销。,26,并发进程与实时系统,27,并发进程,看两个实例：各自运行，但共享数据。用时序程序模型写一个系统是一件很困难的事，但用并发进程模型来实现却很容易。每

20、个任务有各自的程序（进程）。进程间彼此通信,B1.4心跳脉冲,28,进程,进程是一段连续的程序，通常是一个无穷循环。进程间并发执行。它将我们带入一个“程序同时执行”的世界。进程中的基本操作创建和终止（Create and Terminate）可以这样比喻，Create就像一个程序调用，但却不能像程序调用那样去等待。Create就是建立一个新进程。Terminate指停止正在执行的进程，并删除该进程的所有数据。在HelloWord/HowAreYou的实例中,我们创建了进程。暂停和恢复（Suspend and resume）Suspend 是指停止进程的执行，此外，还要保存进程的有关数据。Res

21、ume 是指允许被暂停进程再次执行。连接（Join）一个进程要暂停，直到它要连接的进程执行完为止。,29,进程通信,进程间需要进行数据和信号的通信以完成他们的计算任务。那些彼此不通信的进程仅仅是一些相互独立来完成各自任务的程序。实例:生产者/消费者（Producer/Consumer）进程A生产数据元素、进程B消费数据元素如，进程A 对视频包进行解码、进程B把解码后的数据输出到显示器。进程间的通信方式有两种方式 共享存储器消息传递,processA()/Decode packet/Communicate packet to B,void processB()/Get packet from A

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

23、错误的值。假设count为3从存储器中将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的值会被 错误地设置为2,01:data_type bufferN;02:int count=0;03:void processA()04:int i;05:while(1)06:produce(26:,31,消息传递,消息

24、传递进程间直接交换数据发送进程要发送数据给另一个进程的话，就执行一个特殊的“send”操作。接收进程要接收数据，也要执行一个特殊的“receive”操作。两个进程都需要有一个标识符（identifier），以明确将数据送给那个进程，或那个进程应该接收数据。receive操作可以被阻塞，但send操作既可能是、也可能不是可阻塞的操作。消息传递模式的安全性高，但不够灵活。,void processA()while(1)produce(,void processB()while(1)receive(A,/*region 2*/,32,共享存储器:互斥,某些程序代码不能被同时执行。关键段（Critic

25、al section）它也可能不是连续的程序代码段，在这个代码段中，多个处理器同时更新共享存储器位置。当一个进程进入Critical section后，其它的进程必须被锁定，直到该进程退出Critical section为止。互斥（Mutex）互斥是一个共享对象，具有两个分别用于锁定和解锁共享数据段的操作。锁定（Lock）和解锁（Unlock）。不允许对其所保护的共享存储器进行多个读写存取。多个进程可以同时执行锁定操作，但只有一个进程能取得锁。其它试图获得锁的进程进入阻塞状态，无法进入程序代码的关键段，直到拥有锁的进程退出关键段之后，将执行解锁操作。然后，这些进程将返回到可执行状态，再去竞争以

26、取得锁。,33,生产者/消费者问题的一种正确解决方法,我们用基元（primitive）互斥（mutex）来锁住程序代码的关键段，使得在该代码段内同时只有一个进程在执行。下边的内容是一段跟以前相同功能的执行序列A/B：对 count_mutex 执行 lock操作A or B 有一个获得锁假设B 获得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的值存回 cou

27、nt 的存储器位置(count=3)Count 的值被正确地修改为 3,01:data_type bufferN;02:int count=0;03:mutex count_mutex;04:void processA()05:int i;06:while(1)07:produce(31:,34,进程通信,我们可以尝试对电梯控制器中“req”的值进行建模使用共享存储器方式使用共享存储器和互斥操作使用消息传递 方式,35,并发程序设计中的一个常见问题：死锁,死锁（Deadlock）：在这种情况下，多个进程都被阻塞，互相等待对方的关键段解锁。多个进程都处于锁定状态都不能执行解锁操作，从而相互一直永

28、远等待。实例中，有两个关键段可能被并发执行。需要两个锁(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)。获取第一阶段锁定，解除第二阶段锁定。,01:mutex mutex1,mutex2;02:

29、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:/*critical section 2*/19:mutex1.lock();20:/*critical section 1*/21

30、:mutex1.unlock();22:/*critical section 2*/23:mutex2.unlock();24:25:,36,进程同步,有时，并发运行的进程必须同步执行。当一个进程等待：另一进程以计算某个数值到达执行中的某个点告知某种情况再次回忆producer/consumer 问题如果缓冲区满的话，进程A 等待。如果缓冲区空的话，进程B 等待。上面的情况，我们称之为忙等等待的进程只是进行空操作CPU 时间白白浪费更有效的方法我们前边讨论的连接操作及可阻塞的发送和接收基元它们都是阻塞忙等的进程，从而不浪费CPU的时间。条件变量和监视程序,37,条件变量,条件变量（Condit

31、ion variable）是一个具有两个操作的对象，分别是：signal操作和 wait操作。在一个条件变量下，执行等待操作的进程被阻塞，直到另一进程完成对该条件变量的singnal操作。具体是咋做的呢?进程A 取得互斥锁然后，进程A 执行等待，传给等待操作一个互斥变量。等待操作对该互斥进行解锁进程B 可以获取相同的锁进程B 进入关键段计算某个值或使某个条件变为成立当条件成立时，进程B执行signal操作从而使进程 A 可再次取得该互斥的锁进程 A 变为可执行的状态,38,条件变量实例：consumer/producer问题,两个条件变量buffer_empty说明缓冲区中是否至少有一个可用的

32、空位置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，至少有一个新的数据元素可供使用。,39,监视程序,监视程序是一组数据作用于该数据的方法或子程序，与面向对象实例中的对象类似。它可以保证任

33、何时间只有一个进程可以在监视程序内运行。(a)如果进程X执行时，进程Y必须等待。(b)如果进程X对某个条件变量执行等待操作那么，允许进程Y进入监视程序。(c)如果进程Y告知该条件变量，进程X正在等待进程Y被阻塞允许进程X 继续执行(d)如果进程X终止或等待某个条件，则进程Y允许再次进入监视程序。,40,监视程序实例:consumer/producer问题,使用监视程序来封装生产者/消费者进程的时序程序，共享的buffer也被封装在监督程序内。一个进程可以允许被首先执行。假设进程B允许首先执行它将执行，直到进程B发现count=0为止这时，它将对buffer_full条件变量执行等待操作允许进程

34、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 buffer_full,condition buffer_empty;06:void processA()07:int i;08:while(1)09:produce(35:,41,实现,把系统的功能映射到硬件处理器系统的功能可以使用

35、多种计算模型来描述也可能用多种语言去描述实现的选择与语言的选择是相互独立的。实现的选择基于处理器的性能、大小、时间和成本因素。最终的实现还要进行可行性测试。最终还依赖于是否适合进行大规模的生产制造。,42,并发进程模型：实现,本节将使用单用途或通用处理器来实现方法一：使用多处理器，每个处理器执行一个进程真正的多任务(进程间并行运行)使用通用处理器使用C语言来描述进程的功能，再将其编译成处理器的指令但这种方法非常昂贵，在多数情况下没必要使用。普通的单用途处理器更常用方法二：用一个通用处理器执行所有进程大多数进程并没有使用CPU100%的时间。很多进程可以共享一个处理器的时间，仍能以要求的速度执行

36、。方法三：前两种的综合多进程共享一个通用处理器，同时一个或多个进程也可以在各自的单用途处理器上执行。,43,实现：多进程共享单用途处理器,方法一：用手工方式将这些进程改写为一个时序程序。对简单应用而言，这种方式是可行的，但对复杂的应用而言，则实现起来极为困难。我们可以借助一些自动化技术帮助完成这项改写工作，但这种方法并不常用。如，我们前面讨论过的 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 is 0 then call Print

37、HowAreYou方法二：使用多任务操作系统。这种方法较常用。操作系统负责进程调度、存储空间分配、与外设的接口等。实时操作系统(RTOS)能够保证进程的执行速度受到约束。我们可以选择使用内建进程的语言(Java,Ada,etc.)来描述并发进程，也可以使用时序程序语言(C,C+)描述。但使用时序程序语言的话，需要使用例程库来扩展该语言，以支持并发进程。方法三：将进程转变为内含进程调度器的时序程序。该方法额外成本低(不依赖操作系统)但该方法实现起来很复杂，而且不易维护。,44,进程与线程的比较,在操作系统的术语中，两者是不同的。普通进程重量级进程拥有自己的虚拟地址空间(堆栈、数据、程序代码)它有

38、自己的系统资源(如，打开文件)线程轻量级进程它是进程内的子进程仅有程序计数器、堆栈和寄存器与其它进程共享地址空间和系统资源允许线程间更快速的通信它比进程小可以被快速创建线程间的切换系统开销也较小,45,进程暂停和恢复、进程连接,用单任务处理器实现多个进程进程的暂停和恢复必须作为这些处理器实现的一部分来实现。可为处理器多设计一个输入信号，该信号把处理器设置为暂停状态。还需要用附加逻辑来表明处理器是否在执行。额外的输出信号用来表明处理器的完成。用一个通用处理器来实现多个进程进程的暂停和恢复必须在描述这些进程的程序设计语言或特殊的多任务函数库内实现。程序语言或函数库都需要依靠操作系统来处理这些操作。

39、,46,进程调度,用通用处理器来实现多进程时，这些并发进程必须考虑时序要求。对多任务处理器而言，则没有这方面的要求。调度：它是一个用来决定每个进程何时、以何种方式、被执行多长时间的一个特殊进程。分为抢占式调度和非抢占式调度两种抢占式调度进程执行一段预定时间，然后将其逐出，以允许其他进程在处理器上执行。这段预定时间，称为时间配额(可能有几十到几百毫秒长)决定下一个将要被执行的进程。非抢占式调度只决定当前进程执行完后，下一个将要执行的进程。,47,调度：优先级问题,具有最高优先权的进程一定能第一个被调度器选中。进程的优先级通常是在进程创建时静态决定，可能在执行期间动态改变。FIFO调度器当进程创建

40、后或变成可执行时，将其加入到FIFO对列中。而在当前正在执行的进程配额已用完或进程被阻塞时，可以将其他进程从FIFO对列中移出，并使其在处理器上执行。优先级队列当进程创建后或变成可执行时，再一次将其加入到FIFO对列中。当调度器选择新进程来执行时，只需要选择优先级最高的进程。当多个进程具有相同优先级时，调度器根据先来先服务的原则进行选择。如果使用的是非抢占式调度器，该调度方式我们称为优先级调度法。如果使用的是抢占式调度器，该调度方式我们称为轮盘调度法。,48,优先级分配,进程的周期它是指重复的时间间隔，在这个时间间隔内，进程只能执行一次。如，周期=100 ms，则进程必须每隔100ms执行一次

41、。进程的周期是由系统的描述来决定的如，负责更新显示设备上的屏幕的进程，必须每秒执行27次，相当于周期是37ms。执行期限（execution deadline）它可以定义为一段约束时间，进程必须在这个时间之内完成执行。如，执行时间是 5 ms，期限是20 ms，周期是 100 ms。则进程必须在开始执行后的20ms内完成。这说明进程A开始执行后，可以执行4ms，接着休眠14ms，再恢复执行1ms。则该进程从开始执行到结束的总共时间为4+14+1=19ms。比期限小，说明这种调度有效。周期单调调度法这种方法中，周期较短的进程会分配到较高的优先级。当执行期限等于周期时，这种方法很常用。期限单调调度

42、法这种方法中，执行期限较短的进程会分配到较高的优先级。当执行期限小于周期时，这种方法很常用。,49,实时系统,实时系统是由2个或2个以上并发进程组成的系统，这些进程必须按严格的时间要求执行，并且彼此合作，以实现共同目标。如，机顶盒中，为了使输出影像连续，每秒钟至少要对20个视频帧进行解码，所以它用一个进程进行读取图像或声音，另一进程进行图像或声音的解码。其它对实时操作有严格要求的实例有：手机导航和进程控制系统组装线监视系统多媒体和网络系统 以上这些系统中，进程间的通信和同步是很关键的。因此，并发进程模型最适合描述这些系统。,50,实时操作系统(RTOS),RTOS是为建立真正实时的嵌入式系统提

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