Group #: 7 Project topic: Implementation of EDF, PIP and PCEP on RT-Linux Solved issues: All: Successfully implemented and tested EDF functionality; by All: Successfully implemented and tested PCEP. Next Steps: All: Implementation and testing of PIP by 30th Nov. All: Final report by 2nd December. Design of EDF: We decided to add EDF functionality as a separate loadable module in RT-Linux. This approach will not require any changes in the existing fixed-priority scheduler. A new file rtl_sched_edf.c is added to support EDF fucntionality. This module will be loaded during run time. Following files/functions have been modified for EDF: 1. include/rtl_sched.h: Modifications: a. Added following structure for EDF parameters struct EDF { hrtime_t orig_deadline; /*The actual abs. deadline when there is no inheritance*/ hrtime_t eff_deadline; /*The inherited deadline used for scheduling when PIP is enabled*/ hrtime_t rl_deadline; /*The relative deadline of the thread*/ int inherit_flag; /*This flag indicates whether a thread has inherited a priority*/ }; We are using deadline as priority, the earlier the deadline, the higher the priority. There is no priority field as such. b. Added a pointer to EDF structure defined above in rtl_thread_struct structure. This structure stores all the thread states. 2. Added a new file rtl_sched_edf.c to rtlinux/schedulers/ directory. The following functions of this file are different from original rtl_sched.c file that comes with rtlinux a. rtl_schedule(): The default scheduler in rt-linux is fixed-priority based. We made the following changes in rtl_schedule function of rt-linux. 1. Added code for calculating Absolute deadline. 2. Find the next thread to be scheduled according to the earliest Absolute deadline. b. find_preemptor(): The next preemptor of this thread will be the thread which is released before the absolute deadline of chosen thread. If there are no such threads then, SCheduler will wakeup after a constant time (HRTICKS_PER_SEC/HZ)/2). c. new_pthread_make_periodic_np(): New API to support specification of relative dealines from application programs. This function is same as pthread_make_periodic_np function of rt-linux. We have added code to initialize EDF structure in the new fucntion. d. pthread_create(): Added code for allocating memory for EDF structure. Did other initialization for EDF scheduling. e. init_module(): Linux thread is handled separately by rt-linux. Its memory is assigned in init_module() of rtl_sched_edf.c. So, added code to allocate memory for EDF structure, and made the deadline of this thread as HRINFINITY. This will ensure that Linux thread will have lowest priority. Issues: We are facing major problem with validation of EDF functionality. The offline schededule based on WCET matches for small period of time, and then the order in which threads are executed are different than offline schedule. We tried to do some reserach into this and found out that other groups who have tried to implement EDF faced the same problem, and there is no good way to validate EDF functionality. Design of PCEP: We decided to implement PCEP for single instance of mutex. PCEP is enabled if the _RTL_POSIX_THREAD_PRIO_PROTECT is defined during configuration of RTLinux. The PCEP protocol runs with the default static priority based scheduler of RTLinux. Following files/functions have been modified for PCEP: 1. include/rtl_mutex.h: Modifications: a. Added a new pointer field in the pthread_mutex_t structure to point to the thread which has locked this mutex. #ifdef _RTL_POSIX_THREAD_PRIO_PROTECT struct rtl_thread_struct* owner_thread; #endif b. Added a new structure for implementing a linked list of all the mutexes in the system. This list is used to update the system ceiling and priorities of threads on locking/unlocking of mutexes. MAXPRIO is the initial system ceiling which is lower than the priority of lowest thread. #ifdef _RTL_POSIX_THREAD_PRIO_PROTECT typedef struct mutex_list* list_ptr; struct mutex_list { pthread_mutex_t * mutex_element; list_ptr next; }; #define MAXPRIO 99999 #endif c. Added the declaration of dump_mutex_list to dump the mutex_list used for purposes. #ifdef _RTL_POSIX_THREAD_PRIO_PROTECT extern void dump_mutex_list(void); #endif 2. include/rtl_sched.h Modifications: a. Added a structure for maintaining system ceiling and the thread id because of which the system ceiling is at the present level. struct ceiling_t { int sys_ceiling; /*The system ceiling for PCEP*/ struct rtl_thread_struct* ceiling_thread; }; b. Added a new field called base_sched_priority in the structure rtl_thread_struct for storing the original priority as the thread priority will change as and when it locks/unlocks a mutex. c. Added a line in the function pthread_setschedparam() to initialize the base_sched_priority of a thread. 3. include/rtl_mutex.c Modifications: a. Declared variable header for mutex linked list and ceiling_pcep structure. list_ptr header = 0; struct ceiling_t ceiling_pcep = {MAXPRIO,0} b. Modified pthread_mutex_detsroy function to remove the mutex from the linked list of mutexes. c. Modified pthread_mutex_init fucntion to add the mutex to linked list of mutexes. d. Modifed __pthread_mutex_trylock function to incorporate following functionalities: 1. If the thread priority is less than the current ceiling, then return EBUSY as this thread is ineligible to lock the mutex. If the thread priority is same as system ceiling and this thread is not the system ceiling thread (i.e thread, due to which the current system ceiling exists), then return EBUSY. 2. Raise the priority of thread to mutex ceiling priority. 3. Raise the system ceiling to mutex ceiling priority. Update the system ceiling thread. 4. Update the owner thread in mutex. e. Modified pthread_mutex_unlock function to incorporate following functionalities: 1. Iterate through the linked list of mutexes to find the next highest priority locked mutex. The ceiling of this mutex will be the new system ceiling. 2. Wake-up all the threads that were blocked due to wait on an occupied mutex or were not eligible due to their priorites( threads of step d.1) 3. Iterate through the linked list of mutexes to find the next highes priority mutex locked by the current thread. The priority ceiling of this thread will be the new priority of the thread if it is greater than sched_base_priority. If no such mutexes exist, then thread will return back to its base sched priority. Issues: We have tested the above changes for PCEP policy for simple test cases (for one period). It worked fine. Currently we are working on adding protection on the linked list of mutex to ensure mutually exclusive operations on this list. Then, we plan to test the functionalities with more test cases.