q Scheduling for
q Time-Driven Systems
v Time-Driven Real-Time Systems
¨ Time-Triggered Protocol used for inter-processor communication
¨ Process activation as well as message transmission are time based
¨ Static process scheduling
¨ TTP cyclic communications
¨ Scheduling goal is to minimize and meet system level specifications for the worst-case system delay
¨ Communications processes are modeled just as regular processes
¨ Bus is modeled just like the nodes are, one communication slot can be on the bus at a time
¨ We must assume that processors available are not all identical and not any process can be assigned to any available node
¨ We must progressively assign processes to allocated processors with the goal of minimizing and meeting the specifications for total length of schedule (system latency)
¨ Static cyclic scheduling (static periodic schedule) has been and still is the most common approach used for applications that have data dependencies
¨ Static schedules for each node is constructed off-line (a priori)
§ Since schedule is computed off-line, we have time to use computationally complex algorithms to construct the schedule
¨ Each scheduling decision is made at specific times (timer interrupts) which are independent of system events (job release, job completion, etc.)
¨ Advances in priority preemptive scheduling coupled with advances in processor technology and operating systems have shown that hard real-time systems could also use preemptive scheduling
v Scheduling with Control and Data Dependencies
¨ Map Conditional Process Graph to processing nodes
¨ Construct static schedule based on the graph that could meet and minimize the worst case delay
¨ Scheduling algorithms are used to generate a static schedule of the processes such that the worst case delay is as small as possible
¨ Algorithm produces a schedule table that contains all the information needed by the run time scheduler to activate processes in the distributed system
¨ A non-preemptive scheduler stored on each node actives processes and communications from the node based on the value of processing graph conditions
¨ Each node only stores part of the schedule table pertaining to the node and all the processes that may run on the node
¨ Value of conditions are broadcast in the system over the communications bus
¨ Just before termination of the any process that outputs a condition, the value of the condition is broadcast from the processor to all other processors in the distributed system
v Requirements for the Conditional Process Graph (CPG) schedule table
¨ No process is activated if, the conditions required for its activation are not true
¨ Activation times are unique based on the conditions
¨ Activation of a process Pi, at a certain time depends only on the condition values at time t known to the processing element which executes the process Pi
¨ Example of a Schedule Table with CPG
v List schedule algorithms
¨ Constructing an Optimum schedule is an NP-complete problem
¨ The goal is to develop heuristics that can produce good schedules in reasonable time
§ Suboptimum, good enough
¨ Process schedule time is based on process priority lists
¨ Ready list contains processes eligible to be activated on the processor at current time
¨ A priority function is used to select a process to be scheduled from the set of ready processes
§ The highest priority ready process is selected to be scheduled first
¨ Algorithm is recursive at each disjunction node
¨ Priorities are based on Critical Path from the current node to the sink node
§ The priority assigned to a process is the maximum execution time from current node to sink node
lPi= max (k) ∑ (PjЄΠik) C Pj
§ Where k is a paths from current node Pi to the sink node
§ Where Πik is the kth path from node Pi to the sink node
¨ Looking at all paths from Pi the maximum critical path equals the priority of process Pi
¨ Length of Critical Path is used as process priority for scheduling
¨ Delay Estimation Scheduling algorithm uses lower bound on total delay of all processing chains from the current node as criteria for scheduling priority
§ Assumes processes executed on the same processor could be used as criteria to schedule
¨ Calculate delay estimation for Partial Critical Path Scheduling
¨ Goal is to minimize worst-case delay of an application modeled as conditional process graphs
¨ Delay estimation for Partial Critical Path scheduling example
v Scheduling for Time-Driven Systems
¨ We will assume that each process is mapped on a processor
¨ The worst-case execution time of each process is known
¨ The length of each message is known as well as message latency
¨ Scheduling decisions are only made at the beginning of each frame
¨ Knowing the above we must:
§ Compute the worst case delay on the system execution time to minimize and meet the required specification for the system performance
¨ Static cyclic scheduling example with TTP
¨ The ordering of slots and the slot lengths influence worst-case execution delay of the system
Improved Priority Function
¨ Improvement of the resulting schedule can be obtained by including knowledge of bus access scheme into the priority function
¨ Priority Function example
¨ This anomaly, is because our process graph over simplifies message transfer between processes without taking into consideration the TDMA protocol
¨ Message communications is not a simple delay on the CPG
§ It is not realistic because we did not account for TDMA slot arrival and sequences
¨ Priority estimation has to be based on message planning with the TDMA schedule
¨ The Modified Partial Critical Path (MPCP) is computed during scheduling when ready processes are to be scheduled on the same resource
¨ Computation of the MPCP is similar to that of PCP
¨ Starts with the process that is assigned to a different processor and has to use the bus for message passing
¨ Delay introduced by a message passing node is the difference between the time that the slot to which the message is suppose to be assigned will arrive and the time that the process generating the message terminates (the message is ready to be placed on the bus)
¨ When using MPCP, priority of each ready process has to be calculated dynamically when multiple ready processes are available to be scheduled
¨ Because we use more realistic delay estimates to get more accurate priorities, this algorithm can produce better quality scheduling and shorter delay for the graph
¨ The drawback is since dynamic scheduling is used, scheduling time and processing needs are increased
v Bus Access Optimization
¨ Bus access performance depends on
§ Ordering of the slots
§ Size of slots
¨ There are various methods to simulate and estimate appropriate slot length and ordering
¨ Greedy approach
§ Assigns nodes to slots in order
§ Slot length is assigned to be the length of the largest message generated by process at the node
§ Start with first slot and find the node that when assigned to transmit on this slot, minimizes the system delay
§ In the same loop, search for the best length for this slot as well
§ Solution can get stuck in a local minima and miss the optimum solution
¨ Simulated annealing
§ Tries to escape local minima by randomly selecting a neighboring solution
§ Randomly swapping slots
§ Changing the length of a randomly selected slot
§ Exhaustive search for the optimum solution
v Frame size selection
¨ Frame size should long enough such that every job can start and complete its execution within a frame
¨ Frame size should be at least as big as the largest execution time
¨ Hyper period of the scheduling cycle should be an integer multiple of the frame size
¨ Between release time of each job and deadline, there should be at least one frame
¨ Aperiodic and sporadic jobs are scheduled to use the time not used by periodic tasks
¨ Cyclic executive takes over the processor and executes according to the schedule table at the processor at the beginning of each frame
¨ Each time cyclic executive is activated, it also checks for over-runs
§ If the job executing at the last frame is still not complete, at the start of the new frame
· If the job is not a periodic job, it is preempted and placed on the non periodic jobs queue, it can resume when slack time is available
· If the job is periodic, a frame over run has occurred, this is result of a system hardware failure or unknown defect in the software
· Cyclic executive takes action to resolve this system failure
v Scheduling sporadic jobs
§ Have deadlines
§ Unlike periodic tasks, the scheduler may not be aware of the sporadic task’s maximum or average execution time
§ Not possible to guarantee that all sporadic jobs will complete before their deadlines
§ Sporadic jobs are only scheduled when no periodic jobs are ready to be scheduled
v Sporadic job acceptance test
§ Based on the schedule tables, if there is sufficient time in the frames before the sporadic job’s deadline, scheduler may accept the job
§ Earliest Deadline First (EDF) scheduling used to decide which sporadic job is run
§ Cyclic EDF algorithm for scheduling sporadic jobs is an on-line algorithm
1/24