From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 8136 invoked by alias); 24 Mar 2011 14:47:01 -0000 Received: (qmail 7877 invoked by uid 22791); 24 Mar 2011 14:46:59 -0000 X-SWARE-Spam-Status: No, hits=1.6 required=5.0 tests=AWL,BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW,T_TO_NO_BRKTS_FREEMAIL X-Spam-Check-By: sourceware.org Received: from mail-iy0-f177.google.com (HELO mail-iy0-f177.google.com) (209.85.210.177) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 24 Mar 2011 14:46:53 +0000 Received: by iyf40 with SMTP id 40so38616iyf.36 for ; Thu, 24 Mar 2011 07:46:53 -0700 (PDT) MIME-Version: 1.0 Received: by 10.43.55.10 with SMTP id vw10mr5453152icb.151.1300978012892; Thu, 24 Mar 2011 07:46:52 -0700 (PDT) Received: by 10.42.164.138 with HTTP; Thu, 24 Mar 2011 07:46:52 -0700 (PDT) Date: Thu, 24 Mar 2011 14:47:00 -0000 Message-ID: Subject: EDF scheduler in eCos From: Yurij Grechishhev To: ecos-devel@ecos.sourceware.org Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-IsSubscribed: yes Mailing-List: contact ecos-devel-help@ecos.sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Post: List-Help: , Sender: ecos-devel-owner@ecos.sourceware.org X-SW-Source: 2011-03/txt/msg00022.txt.bz2 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 =C2=A0and 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 =3D 16/29+13/38+5/49=3D0.995 * *************************************************************************/ #include 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 =C2=A0 =C2=A0counter_hdl, =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 sys_clk, =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 alarm_hdl[3]; cyg_tick_count_t ticks; cyg_alarm_t alarm_handler; cyg_alarm =C2=A0 alarm_obj[3]; int in_process[3] =3D {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] =3D { 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] =3D { CTIME0, CTIME1, CTIME2 }; // Thread parameters for the EDF // Format: // All the times in ticks of RTC cyg_edf_sched_info_t edf_info[3] =3D { =C2=A0 { PERIOD0, CTIME0, PERIOD0 }, =C2=A0 { PERIOD1, CTIME1, PERIOD1 }, =C2=A0 { PERIOD2, CTIME2, PERIOD2 }, }; // --------------------------------------------------------------------- // externC void cyg_start(void) { =C2=A0 cyg_thread_create((cyg_addrword_t)edf_info, entry0, (cyg_addrword_t)= 0, =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 "Thread A", (void *) stack[0], 2048, =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 &simple_thread[0], &thread_obj[0]); =C2=A0 cyg_thread_create((cyg_addrword_t)(edf_info + 1), entry0, (cyg_addrw= ord_t) 1, =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 "Thread B", (void *) stack[1], 2048, =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 &simple_thread[1], &thread_obj[1]); =C2=A0 cyg_thread_create((cyg_addrword_t)(edf_info + 2), entry0, (cyg_addrw= ord_t) 2, =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 "Thread C", (void *) stack[2], 2048, =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 &simple_thread[2], &thread_obj[2]); sys_clk =3D 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] =3D in_process[1] =3D in_process[2] =3D 1; cyg_scheduler_start(); } // --------------------------------------------------------------------- // void entry0(volatile cyg_addrword_t data) { =C2=A0 cyg_tick_count_t ticks; =C2=A0 int tnum; =C2=A0 while(1) =C2=A0 { =C2=A0 =C2=A0 =C2=A0 ticks =3D cyg_current_time(); =C2=A0 =C2=A0 =C2=A0 tnum =3D (int)data; =C2=A0 =C2=A0 =C2=A0 diag_printf ("\n =C2=A0 =C2=A0Thread %d start at time = %llu \n", tnum, ticks); =C2=A0 =C2=A0 =C2=A0 in_process[tnum] =3D 1; =C2=A0 =C2=A0 =C2=A0 while (cyg_current_time() < ticks + ctimes[tnum]) =C2=A0 =C2=A0 =C2=A0 { =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 // Performed CTIMES ticks =C2=A0 =C2=A0 =C2=A0 } =C2=A0 =C2=A0 =C2=A0 diag_printf (" =C2=A0 =C2=A0Thread %d end at time %llu= \n", tnum, cyg_current_time()); =C2=A0 =C2=A0 =C2=A0 in_process[tnum] =3D 0; =C2=A0 =C2=A0 =C2=A0 cyg_thread_suspend(simple_thread[tnum]); =C2=A0 } } // --------------------------------------------------------------------- // Task activation // cyg_addrword_t data - number of thread void alarm_handler (cyg_handle_t alarm_handle, cyg_addrword_t data) { =C2=A0 int tnum =3D (int)data; =C2=A0 diag_printf ("\nActivation of thread %d at time %llu \n", tnum, cyg_current_time()); =C2=A0 if (in_process[tnum] =3D=3D 1) =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0// Aaa! task is not processed =C2=A0 =C2=A0 =C2=A0 diag_printf("\n\n!!! Thread %d DEADLINE \n", tnum); =C2=A0 // Set new deadline for the thread =C2=A0 cyg_thread_set_edf_deadline(simple_thread[tnum], cyg_current_time() + periods[tnum]); =C2=A0 cyg_thread_resume (simple_thread[tnum]); } // end of edftest.c Execution log: Thread 0 start at time 0 =C2=A0 Thread 0 end at time 16 =C2=A0 Thread 1 start at time 16 Activation of thread 0 at time 29 =C2=A0 Thread 1 end at time 29 =C2=A0 Thread 2 start at time 29 =C2=A0 Thread 2 end at time 34 =C2=A0 Thread 0 start at time 34 Activation of thread 1 at time 38 Activation of thread 2 at time 49 =C2=A0 Thread 0 end at time 50 =C2=A0 Thread 1 start at time 50 Activation of thread 0 at time 58 =C2=A0 Thread 1 end at time 63 =C2=A0 Thread 0 start at time 63 Activation of thread 1 at time 76 =C2=A0 Thread 0 end at time 79 =C2=A0 Thread 2 start at time 79 =C2=A0 Thread 2 end at time 84 =C2=A0 Thread 1 start at time 84 Activation of thread 0 at time 87 =C2=A0 Thread 1 end at time 97 =C2=A0 Thread 0 start at time 97 Activation of thread 2 at time 98 =C2=A0 Thread 0 end at time 113