An Improved Quasi static Scheduling Algorithm for Mixed Data Control Embedded Software EE 249 project report Cong Liu and Xuanming Dong 12 10 2001 Abstract An embedded system is defined as a set of concurrent processes that communicate through channels Described in flow C each process is a sequential program that may contain data dependent or synchronization dependant control structures A task is a set of sequential operations that the system will perform to respond to the inputs from the environment The embedded software coordinates these tasks generated for input events A software synthesis approach includes two correlated parts scheduling and code generation Our scheduling algorithm can guarantee that all tasks can be executed within finite memory for arbitrary input streams and the code generated can have a smaller size than those previously used Petri net PN is used the underlying model of computation MoC to do formal analysis and verification 1 Introduction A reactive embedded system must respond to the inputs from the environment at the speed and with the delay dictated by the environment The embedded software coordinates system operations Scheduling of these operations is subject to satisfy hard time constrains and make most use of the system resources minimize CPU idle time This report is organized as follow in Section 2 system definitions background knowledge and underlying models are given in Section 3 the detail about the algorithm is presented in Section 4 some experiments and results are offered in Section 5 some open topics are illustrated for future research directions 2 System Processes and Tasks We define an embedded system as a set of concurrent processes A set of input and out put ports are defined for each process and point to point communication between processes occurs through uni directional channels between ports We support multi rate communication in which the number of objects read or written by a process at any given time may be an arbitrary constant A process may communicate with the environment in which the system is executed This is done through input and output ports for which no channel is defined Such primary input ports can belong to one of two classes which we call controllable and uncontrollable The latter is used to trigger an execution of the system i e when the system receives an object at an uncontrollable port it reacts to the environment by performing operations On the other hand the system may request the environment for further inputs through controllable ports while this is not allowed for uncontrollable ports Output ports are always written under system control and the environment must be ready to accept them at any time as allowed by the concurrent process specification We restrict our attention to processes described as sequential programs and whose implementation is mapped as software to be executed on a programmable processor The sequential program for each process is specified in Flow C which is based on C but extended to specify communication operations It may contain both datadependent control statements e g if then else or arbitrary while or for loops and synchronizationdependant control statements e g SELECT A task is generated for each input uncontrollable port which performs the operations that required to react to an event of that port 2 1 Static quasi static and dynamic scheduling Static scheduling does most of the work at compile time so the resulting software behavior is highly predictable and the overhead due to task context switching is minimized They may also achieve very high 1 CPU utilization if the rate of arrival of inputs to be processed from the environment has predictable regular rates that are reasonably known at compile time Static scheduling however is limited to specifications without runtime choice called Marked Graphs or Static Dataflow 2 Researchers have recently started looking into ways of computing a static execution order for operations as much as possible while leaving data or synchronization dependant choices at runtime This body of work is known as Quasi Static Scheduling QSS Dynamic scheduling is commonly used for a system which contains real time controls and the run time behavior is heavily dependent on the occurrence of external events 2 2 Petri Net A Petri net PN is defined by a tuple of P T F Mo where P T are sets of places and transitions respectively F is a function from T P P T to non negative integers A marking is a function from P to non negative integers where its output for a place is denoted by M p which we call the number of tokens at p in M If M P is positive the place is said to be marked at M Mo is a marking which we refer to as the initial marking A Petri net can be represented by a directed bipartite graph where an edge u v exists if F u v is positive which is called the weight of the edge We may call v a successor of u and u a predecessor of v respectively A transition is enabled at a marking M p if M p F p t for all p of P In this case one may fire the transition at the marking which yields a marking M given by M p M p t M denotes the fact that a transition t is enabled at a F p t F t p for each p of P In the sequel M marking M and M is obtained by firing t at M A sequence of transitions t1 t2 tk is said to be fireable t from a marking M if there exists a sequence of markings M1 M2 Mk such that M1 M and Mi i Mi 1 holds for each I 1 2 k A transition is said to be a source if F p t 0 for all p of P A marking M is said to be reachable from M if there is a sequence of transitions fireable from M that leads to M The set of markings reachable from the initial marking is denoted by R M0 The reachability graph of a Petri net is a directed graph in which R M0 is the set of nodes and each edge M M is a transition t t M The reachability tree of a Petri net is a tree in which each node is labeled with a marking of with M R M0 the root node is labeled with M0 and each edge v v trepresents a transition with M M A key notion we use in Petri nets for defining schedules is equal conflict sets A pair of non source transitions ti and tj is said to be in equal conflict if F p ti F p tj for all p of P These transitions are in conflict in the sense that ti is enabled at a given marking if and only if tj is enabled i e if the firing of one transition disables ti it also disables tj The equal conflict is an equivalence relation defined on the set of nonsource transitions and each equivalence
View Full Document
Unlocking...