I INTRODUCTION
• An OS has multiple functionalities like Memory Management, Scheduling of tasks, Device Management, File Management
etc. In this mini-project, the focus is on programming a Task Scheduler that can schedule the tasks in an embedded
environment based on priority associated with the tasks.
• In this report, threads or tasks both refer to while(1) loops that run indefinitely. The terms threads and tasks both mean the
same thing and may be used interchangeably.
II TASK S CHEDULER
• A scheduler is an OS function that makes it appear as though multiple tasks are active in the micro-controller. It gives tasks
the notion of Concurrent Processing. Even though it may appear as though multiple tasks are running at the same time,
only one thread will be running at any point of time.
• Cortex-M has only one processor. So only one task can be run at any point of time. The other tasks will be contending for
processor time.
III TYPES OF TASK S CHEDULERS
• Non Preemptive Scheduler (Co-Operative Scheduler)
• Preemptive Scheduler (Non Co-Operative Scheduler).
IV N ON P REEMPTIVE S CHEDULER
• In a Non Preemptive Scheduler(Co-Operative Scheduler), the main threads will themselves decide when to stop running.
This is done by each thread calling a function (Suspend() for example).
• This function Suspend() will suspend the running thread, run the scheduler which chooses a new thread and the new thread
is launched. Although easy to implement, a Co-operative Scheduler is not appropriate for real time systems.
V PREEMPTIVE S CHEDULER
• Assume there are a list of main threads that are ready to be run. When the processor is free, it chooses one main thread to
be run. In a preemptive scheduler, the main threads will be suspended by a periodic interrupt, and the scheduler will choose
a main thread to be run. When we return from the interrupt, the chosen new thread will be launched.
• In a Preemptive Scheduler, the OS itself will decide when a running thread needs to be suspended, thus returning it to the
active state. The following picture denotes 4 main threads that run using a preemptive scheduler :
Figure 1: Preemptive Scheduler. Picture Courtesy : Real Time Operating Systems by Jonathan Valvano
VI TYPES OF T HREADS
• Event threads.
• Main threads.
VII EVENT T HREAD
• These threads are attached to hardware and should execute based on changes in status of hardware.
• Some of the examples include periodic threads that should be executed at a fixed rate (data acquisition), input threads that
need to be executed when new data is available at the input (like an operator pushing a button), output threads that need to
be executed when output device is idle and new data must be sent to the output device. Time to execute an event thread
must be short and bounded (less than 10µ seconds). In an embedded system, event threads are simply Interrupt Service
Routines(ISR)
VIII MAIN T HREAD
• The main thread is executed on start up and it never returns. These threads execute an initialization loop and then execute a
sequence of steps within a while loop.
IX THREAD C ONTROL B LOCK (TCB)
• A Thread Control Block is also referred to as a Task Control Block. Each thread will have a TCB data structure associated
with it that has a pointer to its own stack and a pointer pointing to the TCB of the next task to be executed.
X IMPLEMENTATION OF THE S CHEDULER
• A priority based Preemptive scheduler will be used in this project. The priorities are for the interrupts that take up very little
time of the processor(Event Threads).
• The threads will be linked to each other using a linked list data structure. This holds true for both the main threads and the
event threads.
• First we assign a number of main threads that will be running in a Weighted Round Robin manner. The threads will be
created using function pointers. In Weighted Round Robin, the main threads will be running in a circular fashion but with
unequal weighting.
• For example, assume there are three threads 1,2 and 3. The threads can be run in the sequence 1,2,1,3,1,2,1,3…..In this
example thread 1 receives 50% of the processor time and threads 2 and 3 receive 25% each. Here the threads can be
blinking of LEDs in different colours, displaying numbers in the seven segment display, displaying text in the LCD etc
• A pointer RunPt will be pointing to the TCB of the task that is currently running. If a thread is running, it will be using the
real Stack Pointer as its stack pointer. However, the other threads will hold a dummy array whose value will be pushed on
to the actual stack when they begin to function. So this dummy array helps us save the context when switching from one
task to another.
• The Systick timer will be configured in such a way that whenever the timer fires, Systick Handler() function will be called
and this function will be help us save the context of the task that is currently running and then move the SP to the stack
pointer of the next task in the list.
• The priorities will be associated with the interrupts. These interrupts will take very little time to execute, unlike the main
threads that are run in weighted round robin fashion. This priority information will be present in the TCB of the event
threads. Lower the number of the priority field in TCB, higher is the priority associated with it.
• Multiple threads may have the same priority. A priority 2 thread must be run only if there are no priority 1 threads that are
ready to be run. A priority 3 thread must be run only when there are no priority 1 or priority 2 threads ready to be run.
• We aim to demonstrate this priority based scheduling of the event threads by assigning the task of generating a sine wave to
one of the event threads. We can have multiple other event threads with varying priorities. When task of generating a sine
wave has a higher priority and is executed frequently we get a smooth sine wave. But when this task does not have a high
priority and when it is executed less frequently, we do not get a smooth sine waveform and the shape of the sine wave will
be distorted.
Figure 2: Linked List of TCBs. Picture Courtesy : Real Time Operating Systems by Jonathan Valvano
XI COMPONENTS R EQUIRED
• TIVA micro-controller
• Edu Arm Board with LTC 1661 DAC
XII REFERENCES
• Real Time Operating Systems for ARM Cortex-M Microcontrollers by Jonathan Valvano.
code: Task_Scheduler_Final_Submission
Video: Priority Based Task Scheduler For Multi-Threaded System
Recent Comments