public inbox for
 help / color / mirror / Atom feed
From: Yurij Grechishhev <>
Subject: EDF scheduler in eCos
Date: Thu, 24 Mar 2011 14:47:00 -0000	[thread overview]
Message-ID: <> (raw)

Hello All!
A few month ago I began to develop a EDF-based scheduler for eCos.
Some information about Earliest-Deadline scheduling policy:

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:
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
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
(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,
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] = {

// ---------------------------------------------------------------------
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);


in_process[0] = in_process[1] = in_process[2] = 1;

// ---------------------------------------------------------------------
void entry0(volatile cyg_addrword_t data)
  cyg_tick_count_t ticks;
  int tnum;
      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,
      in_process[tnum] = 0;


// ---------------------------------------------------------------------
// 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,

  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

                 reply	other threads:[~2011-03-24 14:47 UTC|newest]

Thread overview: [no followups] expand[flat|nested]  mbox.gz  Atom feed

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \ \ \ \

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).