From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 18018 invoked by alias); 9 Jun 2011 06:27:33 -0000 Received: (qmail 18005 invoked by uid 22791); 9 Jun 2011 06:27:31 -0000 X-SWARE-Spam-Status: No, hits=-1.6 required=5.0 tests=AWL,BAYES_00,RCVD_IN_DNSWL_LOW,T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mailhub4.uq.edu.au (HELO mailhub4.uq.edu.au) (130.102.149.131) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 09 Jun 2011 06:27:16 +0000 Received: from smtp4.uq.edu.au (smtp4.uq.edu.au [130.102.128.19]) by mailhub4.uq.edu.au (8.13.8/8.13.8) with ESMTP id p596REcx028455 for ; Thu, 9 Jun 2011 16:27:14 +1000 Received: from UQEXET01.soe.uq.edu.au (uqexet01.soe.uq.edu.au [130.102.6.2]) by smtp4.uq.edu.au (8.13.8/8.13.8) with ESMTP id p596REjH018918 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=NOT) for ; Thu, 9 Jun 2011 16:27:14 +1000 Received: from UQEXHT03.soe.uq.edu.au (130.102.4.79) by UQEXET01.soe.uq.edu.au (130.102.6.2) with Microsoft SMTP Server (TLS) id 8.2.247.2; Thu, 9 Jun 2011 16:27:13 +1000 Received: from UQEXMB03.soe.uq.edu.au ([130.102.4.74]) by UQEXHT03.soe.uq.edu.au ([130.102.4.79]) with mapi; Thu, 9 Jun 2011 16:27:14 +1000 From: Yi Tang To: "ecos-devel@sourceware.org" Date: Thu, 09 Jun 2011 06:27:00 -0000 Subject: Anyone interested in EDF Scheduler? Message-ID: <51037EA24D544D4D92628498CDDE0B3E3968E504A6@UQEXMB03.soe.uq.edu.au> Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-UQ-FilterTime: 1307600834 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-06/txt/msg00004.txt.bz2 Hi all,=20 I have checked the group and it seems we have already got talks about=20 edf scheduling. I have written a native version of edf for ecos,=20 implemented by using a sorted queue for task's absolute deadline, plan=20 to test it in the next few weeks.=20 For the deadline sorted queue, I utilize the Cyg_CList_T class to=20 implement that.=20 One problem I found for the edf is how to apply it to periodic task=20 model. For priority task, new job still got the same priority. But new=20 job in edf get different absolute deadline.=20 Thus I introduce two new thread controls:=20 complete() =A0 -- showing thread complete current job, wait for next activa= te=20 release() =A0 =A0 =A0-- activate again for new job, update abs deadline=20 For the schdinfo init, I have these two functions in kapi=20 // init task deadline=20 void cyg_thread_edf_initddl(=20 =A0 =A0 =A0 =A0 cyg_handle_t =A0 =A0 =A0 =A0 =A0 =A0thread,=20 =A0 =A0 =A0 =A0 cyg_tick_count_t =A0 =A0 =A0 ddl_init,=20 =A0 =A0 =A0 =A0 cyg_bool =A0 =A0 =A0 =A0init_mode =A0 =A0 //init mode abs = or rel=20 );=20 // periodic task deadline=20 void cyg_thread_edf_perioddl( =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 = =A0 =A0=20 =A0 =A0 =A0 =A0 cyg_handle_t =A0 =A0 =A0thread,=20 =A0 =A0 =A0 =A0 cyg_alarm =A0 =A0 =A0 =A0 *alarm,=20 =A0 =A0 =A0 =A0 cyg_alarm_t =A0 =A0 =A0 *alarm_fn, // Call-back function =A0 =A0 =A0 =A0 cyg_tick_count_t =A0ddl_period =A0 =A0// relative value only );=20 I noticed that the kapi already provide a deadline_wait function which=20 also set the start_time and run_time. But my view is that these two=20 values is not always needed in applications and it is really hard to=20 know in advance the exact run_time for a task job.=20 Please give some comments on my edf scheduler interface?=20 typedef cyg_uint64 cyg_deadline; // thread deadline type class Cyg_SchedThread_Implementation : public Cyg_DNode_T { friend class Cyg_Scheduler_Implementation; friend class Cyg_ThreadQueue_Implementation; protected: =20=20=20=20 cyg_deadline peroid_ddl; // peroidic deadline cyg_deadline init_ddl; // init deadine cyg_deadline tmval; // Absolute deadine cyg_bool init_mode; // 1 =3D init abs deadline, 0 =3D init rel deadl= ine cyg_bool release_flag; =09 cyg_priority priority; // here just to pass compile =20=20=20=20 Cyg_SchedThread_Implementation(CYG_ADDRWORD sched_info); // These are not applicable in a edf scheduler; placeholders: inline void rotate_queue( cyg_priority pri ) { }; inline void to_queue_head( void ) { }; void yield( void ); public: =09 void release( void ); =09 void complete( void ); void set_init_deadline( cyg_deadline ddl_i, cyg_bool imode ); void set_period_deadline( cyg_deadline ddl_p ); }; class Cyg_Scheduler_Implementation=20 =A0 =A0 : public Cyg_Scheduler_Base=20 {=20 =A0 =A0 friend class Cyg_SchedThread_Implementation;=20 =A0 =A0 friend class Cyg_HardwareThread;=20 =A0 =A0 friend void cyg_scheduler_set_need_reschedule();=20 // These pointers point to the head element of each list.=20 =A0 =A0 static Cyg_Counter =A0 =A0 =A0 =A0 *rtclock; =A0 =A0 =A0=20 // The run queue applies a sorted threads queue based on=20 // absolute deadline.=20 =A0 =A0 =A0 =A0 Cyg_RunQueue run_queue;=20 =A0 =A0 =A0 =A0 Cyg_Thread *idle_thread;=20 protected:=20 =A0 =A0 Cyg_Scheduler_Implementation(); =A0 =A0 // Constructor=20 ..... following same as other scheduler