Round Robin Non-Preemptive SchedulerIn These Notes . . .What is Scheduling?A Simple ExampleA More Complex ExampleOver-extended Embedded SystemReview of Scheduler InformationRound Robin Scheduler APISet up Timer B0 in Init_RR_SchedulerTask List StructureRunning the SchedulerTask List InitializationAdding a TaskTask SelectionRemoving a TaskEnabling or Disabling a TaskRescheduling a TaskStart Round Robin SystemEmbedded SystemsRound Robin Non-Preemptive Scheduler Lecture 17 17-1Embedded SystemsIn These Notes . . . What is Scheduling?What is the basis of Round Robin non-preemptive scheduling?Examples of Round RobinRound Robin (cooperative) scheduler17-2Embedded SystemsWhat is Scheduling?We have seen a “reactive” system – activities are processed based on interrupts.When scheduled activities are needed, you can set up timer interrupts, or you can have the operating system schedule these periodic tasks (perhaps triggered by interrupts…). Scheduling is choosing which task to run and then running itThe rules:–Define certain functions to be tasks–If there is a task ready to run, then run it–Finish a task before you start another one–If there is more than one task to start, run the highest priority task first (0 is highest priority)17-3Embedded SystemsA Simple Example•We will keep track of how long until the task will run (“time”) and if it is scheduled now (“run”) Priority Length FrequencyTask 1 2 1 20Task 2 1 2 10Task 3 3 1 5Elapsed time 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25Task executed T3 T2 T3 T3 T2 T1 T3 T3time T1 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 20 19 18 17 16 15time T2 10 9 8 7 6 5 4 3 2 1 10 9 8 7 6 5 4 3 2 1 10 9 8 7 6 5time T3 5 4 3 2 1 5 4 3 2 1 5 4 3 2 1 5 4 3 2 1 5 4 3 2 1 5run T1 1 1 1run T2 1 1run T3 1 1 1 1 1 1 1 1 1 117-4Embedded SystemsA More Complex Example•Note at the end, things “stack up” (one T3 missed)PriorityLength FrequencyTask 1 2 1 20Task 2 1 2 10Task 3 3 1 5Task 4 0 1 3Elapsed time 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25Task executed T4 T3 T4 T4 T2 T4 T3 T4 T3 T4 T2 T4 T1 T4 T3time T1 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 20 19 18 17 16 15time T2 10 9 8 7 6 5 4 3 2 1 10 9 8 7 6 5 4 3 2 1 10 9 8 7 6 5time T3 5 4 3 2 1 5 4 3 2 1 5 4 3 2 1 5 4 3 2 1 5 4 3 2 1 5time T4 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2run T1 1 1 1 1run T2 1 1run T3 1 1 1 1 1 1 1 1 1 1 1 1 1run T4 1 1 1 1 1 1 1 1 117-5Embedded SystemsOver-extended Embedded SystemThis is an “overextended” system because some tasks are missed – several times. There is not enough processor time to complete all of the work. This is covered in more detail in a future lecture. Priority Length FrequencyTask 1 2 1 20Task 2 1 2 10Task 3 3 1 5Task 4 0 2 3Elapsed time0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30Task executed T4 T3 T4 T4 T2 T4 T4 T3 T4 T2 T4 T1 T4 T4 T3 T4time T1 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 20 19 18 17 16 15 14 13 12 11 10time T2 10 9 8 7 6 5 4 3 2 1 10 9 8 7 6 5 4 3 2 1 10 9 8 7 6 5 4 3 2 1 10time T3 5 4 3 2 1 5 4 3 2 1 5 4 3 2 1 5 4 3 2 1 5 4 3 2 1 5 4 3 2 1 5time T4 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3run T1 1 1 1 1 1run T2 1 1 1 1run T3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1run T4 1 1 1 1 1 1 1 1 1 1 1 1 117-6Embedded SystemsReview of Scheduler InformationScheduler provided in these slidesDetails–Scheduler uses a software timer per task–All software timers are decremented using a timer tick based on the Timer B0 hardware overflow interrupt–Each task runs to completion before yielding control of MCU back to Scheduler (non-preemptive)17-7Embedded SystemsRound Robin Scheduler APIInit_RR_Scheduler(void)–Initialize tick timer B0 and task timersAdd Task(task, time period, priority)–task: address of task (function name without parentheses)–time period: period at which task will be run (in ticks)–priority: lower number is higher priority. Also is task number.–automatically enables task –return value: 1 – loaded successfully, 0 – unable to loadRemove Task(task)–removes task from scheduler.Run Task(task number)–Signals the scheduler that task should run when possible and enables it Run RR Scheduler()–Run the scheduler! –Never returns–There must be at least one task scheduled to run before calling this function.Enable_Task(task_number) and Disable_Task(task_number)–Set or clear enabled flag, controlling whether task can run or notReschedule_Task(task_number, new_period)–Changes the period at which the task runs. Also resets timer to that value.17-8Embedded SystemsSet up Timer B0 in Init_RR_SchedulerSet up B0 timer to generate an interrupt every 1 millisecond// default tb0 will be = 65536 (timer tick = 5.4613 ms)// if you load tb0 = 12000, timer tick will = 1.0000msinit_Task_Timers(); // Initialize all taskstb0 = 12000; // 1 ms timer tickDISABLE_INTStb0ic = 1; // Timer B0 overflowENABLE_INTS tb0st = 1; // start timer B017-9Embedded SystemsTask List Structure#define USE_ROUND_ROBIN_SCH 1 // Set to 1 if using Round Robin Task Scheduler#define MAX_TASKS 5 // Set maximum number of tasks to be used in system // Will affect performance. typedef struct { int initialTimerValue; // “frequency” of task int timer; // time to next “run” int run; // binary – 1 = “run now” int enabled; void (* task)(void); // address of function} task_t;task_t GBL_task_list[MAX_TASKS];int GBL_run_scheduler=0; 17-10Embedded SystemsRunning the Schedulervoid Run_RR_Scheduler(void) { // Always running int i; GBL_run_scheduler = 1; while (1) { // Loop forever & Check each task for (i=0 ; i<MAX_TASKS ; i++) { // If this is a scheduled task if (GBL_task_list[i].task != NULL) { if (GBL_task_list[i].enabled == 1) { if (GBL_task_list[i].run == 1) { GBL_task_list[i].run=0; // Reset task timer GBL_task_list[i].task(); // Run the task break; } } } } }}17-11Embedded SystemsTask List Initializationvoid init_Task_Timers(void) { // …
View Full Document
Unlocking...