S-Nets : Tool for the performance evaluation of hard real-time scheduling algorithms

Abstract

A new Petri net-based tool is developed for an integrated analysis of schedulability and performance of Hard Real-Time Systems (HRTSs). The existing Deterministic Timed Petri Nets (DTPNs) do not facilitate modeling of scheduling policies encountered in HRTSs. Additionally, the number of places and transitions in the DTPN model of an HRTS is prohibitively large, and its graph representation is difficult to follow. To overcome these limitations, we have developed S-nets, which are based on DTPNs but augmented with:

New types of places: resource places and signal places A scheduler block to model scheduling algorithms Coloured tokens, classified into four types Defined transition firing rules Transition folding to reduce model complexity and improve intuitiveness for multiframe real-time systems

Analysis Techniques Schedulability analysis and performance evaluation using S-nets are based on reachability analysis, which involves:

Generating states Constructing the reachability graph Exhaustively exploring whether desired conditions hold in these states

It is shown that the reachability graph is finite for S-net models of HRTSs operating in multiple time frames. S-nets allow modeling of scheduling algorithms as black boxes. The reachability graph of an S-net model is a semi-Markov chain, and steady-state probabilities exist for this chain. A method is outlined to compute generic performance measures from the steady-state probability distribution.

Performance Measures Two performance measures are defined:

Resource utilization Uniformity of workload distribution

These can be computed from the steady-state probability distribution of the embedded Markov chain. The utility of S-nets for evaluating heuristic-based scheduling algorithms is demonstrated using eleven heuristics applied to various real-time workload cases.

Tool Development Due to the complexity of reachability analysis, a software package called SnetSim is developed. It:

Interactively accepts S-net model specifications Builds the reachability graph Uses a state space generation algorithm with proven termination Provides an upper bound for the number of states Uses dynamic memory with a simple coding scheme to minimize memory requirements