English
资源说明：Edf implememtation over Xenomai
Edfomai
=======
Edf implememtation over Xenomai
ALMA MATER STUDIORUM - University of Bologna
Computer Engineering, Sistemi e controllo per l'automazione
DevTeam: Bellavista Daniele,Mella Luca,Ricci Luca
#### Architecture
-------
Other approaches implement EDF scheduling policy directly in inside the kernel scheduler,
extending the Xenomai Nucleus and adding new user API (eg.Native skin).
Our approach is slighty different in fact we do not modify any line of code of the Xenomai patch, we exploit Xenomai
low level APIs to build a Kernel module that hooks to the Kernel scheduler and changes tasks priorities dinamically.
In order to avoid new syscall definition (and consequential Kernel modification) we decide to develop a device-driver
module and by wrapping user/driver communication we can also provide a handy user API, pretty similar to the native one.
.----------.
| RT Task |-------------------.
'----|-----' |
| |
.----|--------------. ,-----|-------.
| Edfomai User API | __ | Native skin |
'---|---------------' '-------------'
|
.---|-----,----------------------------.
| Edfomai | Kernel |
| Driver | (Nucleus) |
'---------'----------------------------'
Edfomai Driver module doesn't simply react to user messages, it also starts a priority recalculation service which is wake up every time the scheduler is invoked, in order to safely recalculate and set current tasks priority.
#### Features
-------
* EDF scheduling policy over RMPO scheduler
* Support to both sporadic and periodic tasks
* Deadline miss notification (first draft, we use an `RT_QUEUE` at the moment)
* No kernel recompilation
#### Further Work
-------
* Improve priority recalculation complexity: from `O(N+N)` to `O(log(N)+N)`
* Refine deadline miss detection enabling per task watchdog
* Improve user APIs
#### Techincal Notes
-------
Here we summarize the key-point of our EDF scheduling policy implementation, in particular we'll show most interesting
Xenomai APIs that had enabled us to build the system.
* `rt_task_add_hook` : permit to add an user defined hook procedure that will be invoked whenever scheduler is invoked. This API is reachable in kernel space only (so we develop a kernel module)
* `rt_task_set_priority` : set a new priority value to a given task. This function might casuse a rescheduling, in other worlds it can invoke the scheduling procedure and consequentially trigger registered scheduler's hook. (This might lead to a system hang)
* `xnregistry_bind` : which permit to obtain a `xnhandle_t` (which is a pointer to a `xnobject_t`) by specifying a key string (in our case the task name). This function in part on the Nucleus API, so its reachable only in kernel space.
* `xnregistry_fetch` : obtain the corresponting real time object of a given `xnhandle_t`. In our case its used to fetch a thread object so it returns a pointer to a `xnthread_t`.
* `T_DESC` : macro that retrieve a pointer to the `RT_TASK` structure wich contains the specified `xnthread_t` as thread_base
After this quick glance to these APIs it's pretty immediate understand the reason which made us move to the architecure descripted above, in fact priority recalculation service avoid kernel hanging caused by the recoursive invocation of scheduler, hook procedure and set_priority.
Deadline related data has been stored in ad hoc data structures where relative deadline, absolute deadline and remaining time are stored. For the sake of simplicity (lack of time) we decided to adapt `uthash` hash map to kernel space, this way we obtain a scheduling complexity of `O(2N)` which should not be the maximum performance reachable, but it's acceptable for our purposes.
#### Code Map
-------
* `edfomai` contains source code of kernel module (`edfomai-drv*`), user API (`edfomai-app*`) and a couple of test programs
* `edfomai/exercise-xenomai` contains some xenomai test programs (pretty useless, I tink we will erase'em all)
* `edfomai/exercise-edfomai` contains some edfomai test programs (demo purposes)
* `edfomai/datastructures` contains modified uthash source code (http://uthash.sourceforge.net/)
* `edfomai/kernel-images` contains both header and binaries of a xenomai patched kernel (x86_32) useful for testing purposes.
#### Build
-------
To correctly build the module patched kernel header are required (we haven't tested it in case of unpatched kernel header) and Xenomai framework should be installed (we compile demo code using xenomai generated gcc flags).
Once these requirements are satisfied:
* `make` : builds driver module `edfomai.ko` and demos (both sporadic and periodic)
* `make dirver` : builds only driver module
* `make demo` : builds only demos
* `make install` : install `edfomai.ko` as system module (then it could be loaded and unloaded with `modprobe`)
* `make clean` : clean both driver and demo
Then module could be mounted with `insmod edfomai.ko` (or `modprobe edfomai`) and unmounted with `rmmod edfomai`. Debugging print are still enabled in Makefile configuration, so `dmesg|grep Edfomai` output could be sufficiently verbose for better understanding of the events.
#### Release Note
-------
At the moment this project is not meant to be a professional edf scheduler, further improvements and test should be done in order to achive that maturity. So, currently, this project remains an academic project (just a draft).
Hope someone help us in improving it :)
#### License
-------
GPL v2
本源码包内暂不包含可直接显示的源代码文件，请下载源码包。
