Hello All! A few month ago I began to develop a EDF-based scheduler for eCos. Some information about Earliest-Deadline scheduling policy: http://en.wikipedia.org/wiki/Earliest_deadline_first_scheduling
The main feature of the EDF scheduler is it can guarantee all the deadlines in the system at higher loading. For certain applications it can be very usefull. Many RTOS already support the EDF scheduler. And I think, it should be not that difficult to add this scheduler to eCos. Earlier there were attempts to implement a EDF scheduler for the eCos. For example: http://sourceware.org/ml/ecos-discuss/2006-05/msg00109.html http://sourceware.org/ml/ecos-discuss/2010-01/msg00017.html But they were not finished until the end. I have examined the approaches used in other systems for EDF. The basic idea is that it is necessary to keep a list of threads sorted by the time the absolute deadline. Regular doubly linked list for this is not suitable. In real-time extension for Linux and in RTEMS the red-black binary trees http://en.wikipedia.org/wiki/Red-black_tree used for this purpose. All operations efficient with a O(logn) time coplexity (instead of O(n) for doubly linked list). So I had to implement new classes for red-black tree. This are Cyg_RBNode, Cyg_RBTree, Cyg_RBTree_T, Cyg_RBNode_T (files rbtree.hxx and rbtree.cxx in directories infra/current/include and infra/current/src) that are similar to Cyg_DNode and Cyg_CList classes in infra/current/include/clist.hxx. Next I changed classes Cyg_ThreadQueue_Implementation and Cyg_SchedThread_Implementation (in the added files kernel/current/include/edf.hxx and kernel/current/src/sched/edf.cxx) for working with rbtrees and added a new in kapi.h, kapidata.h and ktypes.h. Then I added EDF scheduler in kernel/cdl/scheduler.cdl. I have a first working version that I'm testing in the psim simulator and PowerPC405 processor. The next problem is an implementation of the dynamic synchronisation protocols (such as Preemption Ceiling Protocol (PreCPs) and Dynamic Priority Inheritance Protocol (DPIP)) for mutex. I would be grateful if someone could give me a good description of these protocols. Below is an example of working with the EDF scheduler. /* ************************************************************************* * File: edftest.c * Deadline test for EDF scheduler * Processor utilization = 16/29+13/38+5/49=0.995 * *************************************************************************/ #include <cyg/kernel/kapi.h> cyg_thread thread_obj[3]; char stack[3][2048]; cyg_handle_t simple_thread[3]; cyg_thread_entry_t entry0, entry1, entry2; cyg_handle_t counter_hdl, sys_clk, alarm_hdl[3]; cyg_tick_count_t ticks; cyg_alarm_t alarm_handler; cyg_alarm alarm_obj[3]; int in_process[3] = {1, 1, 1}; // Periods of tasks in ticks of RTC #define PERIOD0 29 #define PERIOD1 38 #define PERIOD2 49 cyg_tick_count_t periods[3] = { PERIOD0, PERIOD1, PERIOD2 }; // Worst-case computation-times in ticks of RTC #define CTIME0 16 #define CTIME1 13 #define CTIME2 5 cyg_tick_count_t ctimes[3] = { CTIME0, CTIME1, CTIME2 }; // Thread parameters for the EDF // Format: <Deadline> <Computation time> <Period> // All the times in ticks of RTC cyg_edf_sched_info_t edf_info[3] = { { PERIOD0, CTIME0, PERIOD0 }, { PERIOD1, CTIME1, PERIOD1 }, { PERIOD2, CTIME2, PERIOD2 }, }; // --------------------------------------------------------------------- // externC void cyg_start(void) { cyg_thread_create((cyg_addrword_t)edf_info, entry0, (cyg_addrword_t) 0, "Thread A", (void *) stack[0], 2048, &simple_thread[0], &thread_obj[0]); cyg_thread_create((cyg_addrword_t)(edf_info + 1), entry0, (cyg_addrword_t) 1, "Thread B", (void *) stack[1], 2048, &simple_thread[1], &thread_obj[1]); cyg_thread_create((cyg_addrword_t)(edf_info + 2), entry0, (cyg_addrword_t) 2, "Thread C", (void *) stack[2], 2048, &simple_thread[2], &thread_obj[2]); sys_clk = cyg_real_time_clock(); cyg_clock_to_counter (sys_clk, &counter_hdl); cyg_alarm_create(counter_hdl, alarm_handler, 0, &alarm_hdl[0], &alarm_obj[0]); cyg_alarm_create(counter_hdl, alarm_handler, 1, &alarm_hdl[1], &alarm_obj[1]); cyg_alarm_create(counter_hdl, alarm_handler, 2, &alarm_hdl[2], &alarm_obj[2]); // Periods for task activations cyg_alarm_initialize(alarm_hdl[0], cyg_current_time() + PERIOD0, PERIOD0); cyg_alarm_initialize(alarm_hdl[1], cyg_current_time() + PERIOD1, PERIOD1); cyg_alarm_initialize(alarm_hdl[2], cyg_current_time() + PERIOD2, PERIOD2); cyg_thread_resume(simple_thread[0]); cyg_thread_resume(simple_thread[1]); cyg_thread_resume(simple_thread[2]); in_process[0] = in_process[1] = in_process[2] = 1; cyg_scheduler_start(); } // --------------------------------------------------------------------- // void entry0(volatile cyg_addrword_t data) { cyg_tick_count_t ticks; int tnum; while(1) { ticks = cyg_current_time(); tnum = (int)data; diag_printf ("\n Thread %d start at time %llu \n", tnum, ticks); in_process[tnum] = 1; while (cyg_current_time() < ticks + ctimes[tnum]) { // Performed CTIMES ticks } diag_printf (" Thread %d end at time %llu \n", tnum, cyg_current_time()); in_process[tnum] = 0; cyg_thread_suspend(simple_thread[tnum]); } } // --------------------------------------------------------------------- // Task activation // cyg_addrword_t data - number of thread void alarm_handler (cyg_handle_t alarm_handle, cyg_addrword_t data) { int tnum = (int)data; diag_printf ("\nActivation of thread %d at time %llu \n", tnum, cyg_current_time()); if (in_process[tnum] == 1) // Aaa! task is not processed diag_printf("\n\n!!! Thread %d DEADLINE \n", tnum); // Set new deadline for the thread cyg_thread_set_edf_deadline(simple_thread[tnum], cyg_current_time() + periods[tnum]); cyg_thread_resume (simple_thread[tnum]); } // end of edftest.c Execution log: Thread 0 start at time 0 Thread 0 end at time 16 Thread 1 start at time 16 Activation of thread 0 at time 29 Thread 1 end at time 29 Thread 2 start at time 29 Thread 2 end at time 34 Thread 0 start at time 34 Activation of thread 1 at time 38 Activation of thread 2 at time 49 Thread 0 end at time 50 Thread 1 start at time 50 Activation of thread 0 at time 58 Thread 1 end at time 63 Thread 0 start at time 63 Activation of thread 1 at time 76 Thread 0 end at time 79 Thread 2 start at time 79 Thread 2 end at time 84 Thread 1 start at time 84 Activation of thread 0 at time 87 Thread 1 end at time 97 Thread 0 start at time 97 Activation of thread 2 at time 98 Thread 0 end at time 113
