YAO-SIM: Yet Another Operating system SIMulator
for real-time scheduling: Quick-Start Guide
Welcome to the home page of the YAO-SIM
project. YAO-SIM stands for Yet Another Operating scheduling SIMulator. The purpose
of the program is to simulate the scheduling of a set of real-time tasks
according to different scheduling algorithms.
YAO-SIM has been developed at Retis Lab of the Scuola Superiore Sant'Anna as an internal project. This software package simulates
different scheduling policies on randomly generated task sets in which
preemption can be fully enabled, fully disabled, or partially enabled through
specific algorithms.
YAO-SIM is written in C and compiled with GCC 4.3.4 and above. We release this program as
open source, in the hope that other researcher all over the world can play with the
simulator, come up and test their novel scheduling algorithms.
The simulator currently includes the
following scheduling policies:
- Fixed priority scheduling: This policy assigns fixed priorities to tasks according to a rule
defined by the user. It can be used to implement Rate Monotonic
(RM) and Deadline Monotonic (DM) scheduling. The scheduler can be executed in a fully preemptive
mode or by disabling preemptions.
- Earliest Deadline First: This policy implements the Earliest Deadline First (EDF)
algorithm, where tasks are scheduled according to their
absolute deadlines. It can be executed in a fully preemptive
version or by disabling preemptions.
- Preemption Thresholds: This approach, proposed by Wang and Saksena, allows a
task to disable preemption up to a specified priority level,
called preemption threshold. Thus, each task is assigned a
regular priority and a preemption threshold, and the preemption is
allowed to take place only when the priority of the arriving task
is higher than the threshold of the running task.
- Deferred preemptions - Activation-triggered model:
In this model, non-preemptive regions are triggered by the arrival
of a higher priority task and programmed by a timer to last
exactly for q units of time (unless the task finishes
earlier), after which preemption is enabled. Once a timer is set
at time t, additional activations arriving before the timeout
(t+q) do not postpone the preemption any further. Once a
preemption takes place, a new high-priority arrival can trigger
another non-preemptive region.
- Fixed preemption points:
According to this approach, a task
implicitly executes in non-preemptive mode and preemption is
allowed only at predefined locations inside the task code, called
preemption points. In this way, a task is divided into a
number of non-preemptive chunks. If a higher
priority task arrives between two preemption points of the running
task, preemption is postponed until the next preemption point.
This approach is also referred to as Cooperative scheduling, because tasks cooperate to offer suitable preemption
points to improve schedulability.
You can download the software package
here
- main.c: This file includes the main function, which collects the results from the simulation
- main_rmedf.c: This file provides an example to compare the number of preemptions between EDF and RM
- schedule.c: This file includes the low-level routines for task scheduling, managing the ready/pending/running
tasks queues
- pts.c: This file includes the functions dealing with preemption threshold scheduling, including the one
for computing the max/min threshold assignment and schedulability test
- lps.c: This file includes the functions dealing with floating and fixed preemption region model
- rmedf.c: This file includes the functions for simulating the classical RM and EDF scheduling algorithms
- taskgen.c: This file includes the functions for the task sets generation. The utilization for each task
is generated with the UUnifast algorithm, then you can generate a random number either for period or execution
time, and compute the other one.
Download and unpack the archive file. As the first example, the results from main.c illustrate the different
schedulability level each scheduling method can achieve on randomly generated task sets. Each column on the
output window represents one specific scheduling algorithm, and it is also plotted in the figure for
better visibility.
The second example compares the number of preemptions generated by EDF and RM. The results are collected
based on 5 thousand tasksets, and it is implemented in main_rmedf.c.
Reference
- M. Bertogna, G. Buttazzo, and G. Yao. Improving feasibility of fixed priority tasks using non-preemptive
regions. In Proceedings of 32nd IEEE Real-Time Systems Symposium (RTSS 2011), Vienna, Austria, Nov.
30 - Dec. 2, 2011.
- A. Burns. Preemptive priority based scheduling: An appropriate engineering approach. S. Son, editor,
Advances in Real-Time Systems, pages 225-248, 1994.
- G. Buttazzo, M. Bertogna, and G. Yao. Limited preemptive scheduling for real-time systems: a survey.
submitted to IEEE Transactions on Industrial Informatics, 2011.
- J. Leung and J. Whitehead. On the complexity of fixed-priority scheduling of periodic real-time tasks.
Performance Evaluation, 2(4):237-250, 1982.
- C. Liu and J. Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment.
Journal of the Association for Computing Machinery, 20(1):46-61, January 1973.
- Y. Wang and M. Saksena. Scheduling fixed-priority tasks with preemption threshold. In Proc. of the 6th
IEEE Int. Conference on Real-Time Computing Systems and Applications (RTCSA 99), Hong Kong, China,
December, 1999.
- G. Yao, G. Buttazzo, and M. Bertogna. Feasibility analysis under fixed priority scheduling with limited
preemptions. Real-Time Systems, 47(3):198-223, 2011.
Development
YAO_SIM has been partially supported by the European project PREDATOR.
For bug report, support, or suggestions, please contact Gang Yao, Giorgio Buttazzo, Marko Bertogna.
Gang Yao
