EDF scheduler in eCos

EDF scheduler in eCos

[Yurij Grechishhev]

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