English
资源说明：simulation and analysis tool for some real time scheduling algorithms
*RT SIMULATE*
* DONE implement the worst case response time algorithm
CLOSED: [2009-08-31 Mon 09:31]
- CLOSING NOTE [2009-08-31 Mon 09:31] \\
Algorithm working on simple cases
* TODO write an automatic generator + tester or random task sets
* Description and usage
This program will show interactively how some real time algorithms work.
In general it:
1. takes a set of tasks as input
2. chooses a scheduling algorithm
3. check if is schedulable or not
4. return the scheduled hyperperiod if possible
Tasks are taken from a configuration file.
In plus there will is an interactive modality where those operations should be possible:
- add a new task
- remove a task
- see the timeline
To start it simply ./rt_simulate.py -i
[[http://dit.unitn.it/~abeni/RTOS/index.html][This]] is the official site, more information on laboratories [[http://dit.unitn.it/~abeni/RTOS/lab.html][here]].
* GUI
** FIG format :ARCHIVE:
[[http://homepage.usask.ca/~ijm451/fig/][fig format description]]
See the [[http://www-epb.lbl.gov/xfig/frm_drawing.html][xfig user manual]]
Must find a python library able to translate in xfig format.
Here is the format: [[http://www-epb.lbl.gov/xfig/fig-format.html][fig format]], [[file:fig_format.txt][txt fig format]]
** SVGfig
*** Doc
[[http://code.google.com/p/svgfig/wiki/Introduction][svgfig tutorial]], one big library composed of only one file.
Possibility to export in different formats
Some nice links:
- [[http://en.wikipedia.org/wiki/Scalable_Vector_Graphics][wikipedia SVG page]]
- [[http://www.datenverdrahten.de/svglbc/][learning by coding]]
- [[http://www.december.com/html/spec/colorspottable.html][table of colors available]]: color are the same used in the CSS style
** wxPython :ARCHIVE:
*** Functions
One simple menubar where you can:
- load a configuration file
- run the scheduling
- check if everything is working
- add a new task to the current task set (this enable automatic redrawing)
The main window must contain the hyperperiod scheduling, made of blocks of different colors and lines for the deadlines.
*** Implementation
We'll use a *wxSizer* object, allows to place objects which will be automatically resized or replaced.
Important to remember that sizer != parent object.
After the layout is ready (box/grid or other) we set up everything with:
1. window.SetSizer(sizer)
2. window.SetAutoLayout(true)
3. sizer.Fit(window)
*** Hints
When taking input from user *wxValidator* is needed to check if the input is correct
(Note: Your wxValidator sub-class must implement the wxValidator.Clone() method.)
*** Debugging
A nice way to debug is using pycrust
* Languages used
- python (for the gui and control interface)
* Language table
| ACRONYM | EXPLANATION |
|------------+------------------------------|
| Task | Schedulable entity |
| Preemptive | OS can regain control of cpu |
| WCET | Worst Case Execution Time |
* Theory summary
OS kernel creates the illusion of multiple CPUs, concurrency is implemented by multiplexing tasks.
Tasks are associated to temporal constraints (*deadlines*)
Scheduler is responsible for selecting the tasks to execute.
* Algorithms
** STATIC scheduling algorithm
- Time axis divided in time slots
- Slots statically allocated to the tasks
- $\tau$ = *gcd*, $T$ = *lcm*
- Very simple implementation, no operating system needed
** Fixed priority scheduling
Very simple /preemptive/ scheduling algorithm.
- every task has a fixed priority p_i
- active task with highest priority are scheduled
To have a better response of the system the priority must be chosen dynamically.
So the problem becomes, how to assign priorities to manage to have a schedulable set of tasks?
** Dynamic priority scheduling algorithms:
Given a set, how to assign priorities?
Two possible objectives:
- schedulability
- response time
- Given a set of tasks where all periods are equal to deadlines and offsets equal to 0.
($\forall i, D_i = T_i
\forall i, r_i0 = 0$)
[[rate][rate monotonic]] is the best choice
- Given a set of tasks where all periods are different from deadlines
[[dead][deadline monotonic]] is the best choice
If we consider periodic tasks with offsets, then /there is no optimal priority assignment possible/
#<>
*** Deadline monotonic
Shorter period $\rightarrow$ higher priority.
#<>
*** Rate monotonic
Shorter relative deadline $\rightarrow$ higher priority.
** Analysis
Given a set of tasks, how can we make sure that is possible to schedule them?
1. simulate the system to check if deadlines missed:
/hyperperiod/ ($H = lcm\{Ti\}$)
*The number can be very large*
2. *Utilisation analysis for RM*:
Based on the utilisation bound, only works for deadline monotonic case (deadline = period)
Each task uses the processor:
$Ui = Ci/Ti$
Total processor utilisation is:
$U = \sum_i Ci/Ti$
So we get:
$U > 1 \rightarrow$ not schedulable
$U < Ulub \rightarrow$ schedulable
$U < 1 \rightarrow$ don't know, other checks needed
$Ulub = 1$ would be optimal
3. *Utilisation analysis for DM*:
In this case we consider
$U' = \sum_i Ci/Di$
$\tau = (C,D,D)$ is the worst possible case of $\tau = (C,D,T)$
So if one is satisfied the other is also satisfied
This bound is very pessimistic.
4. *Response time analysis*:
Compute the /worst case response time/ for every task.
Valid for an arbitrary assignment.
Assumes periodic tasks with no offsets.
*Critical instant*: job $Ji,j$ is released at the same time with a job in every high priority task
本源码包内暂不包含可直接显示的源代码文件，请下载源码包。
