Design and Development of a Time-triggered Co-operative Scheduler

Introduction

One of the most exciting and challenging fields of Computer Engineering is Embedded Systems. It is a research topic that includes both hardware and software components, that perform a dedicated function. As the name "Embedded Systems" implies, the software is embedded into the hardware component to run the tasks in real-time. It is worth noting that embedded real-time systems combine embedded systems and real-time computing technologies. In today's world, embedded systems implementations are used in almost any electronic product.

Aims and Objectives

In this experiment, the aim is to design and develop a time-triggered co-operative scheduler to run multiple tasks at a fixed timeframe. Each task is allowed a pre-defined time limit and each task corresponds to illuminating an LED on the Hardware board and there is a total of eight LEDs, which means eight tasks.

The time-triggered co-operative scheduler should be designed to run six short periodic tasks in a given time frame, therefore tasks will be divided into odd and even cycles as there are eight tasks in total. The first six tasks will be run in an odd cycle and the rest tasks in even cycles and all these tasks are executed periodically. For example, in an odd cycle, LEDs

1,2,3,4,5,6 will be lit in sequence and even cycles lit LEDs corresponding to tasks 8,7,1,2,3,4.

The learning outcome of this course is to understand the real-time scheduling concepts using a time-triggered co-operative/non pre-emptive scheduler as an approach to the implementation of concurrent computational processes in an embedded system.

Once the time-triggered scheduler is designed and developed, the following objectives have to be achieved:

1. The task overrun protection technique has to be implemented, which helps in rescheduling the bad tasks in the task queue. Also, task recovery should be performed on a bad task. Anyone task out of eight tasks will be made faulty and recovered after a set time, basically simulation of fault task.

2. Pulse width modulation (PWM) must be implemented to increase and decrease the brightness of the LEDs over time.

The details of the hardware board, used in this experiment are provided in the Hardware details section of this document.

The time-triggered co-operative scheduler will be developed using the "C" programming language. The compiler used in this experiment to compile the "C" program is gcc.

Design details of the pulse width modulation, task scheduler, and task overrun protection will be discussed later in this document.

Concepts – Embedded Systems

Real-time embedded systems are often time-critical systems and are dedicated to a particular application or function. Therefore, we call it a real-time system when a system must respond to a request within a strictly specified time. This time limit is referred to as a deadline for completing the task. One should incorporate real-time computation in the sense of embedded systems by installing a special kind of operating system onto the embedded device. Operating systems act as a bridge between embedded hardware and software.

Some examples of real-time embedded systems are ABS (Antilock braking system), airbags in cars, televisions, mobiles, and programmable logic controls, etc.

This comprehensive application of the subject has therefore made it necessary to examine the specifications of each embedded project/task-specific dedicated application for the possible choice of hardware and software components that could be used in developing the Embedded Systems project.

Hardware and Software Components of Embedded Systems

Embedded Systems Hardware

An embedded system requires a hardware platform and it may consist of either a microcontroller or microprocessor. The hardware also consists of memory modules, I/O interfaces, and display, etc. Further, the hardware could be divided into microcontroller or microprocessor-based systems and the differences between these are given below:

- Microcontroller-based: Microcontroller is a central processing unit with integrated memory or peripherals devices in it. This is a very widely used hardware platform in embedded systems as they need very few extra components.

- Microprocessor-based: Microprocessors contain a central processing unit, but these hardware platforms use external memory modules and peripheral devices. This type of hardware platform can be used when one wants to choose custom peripherals and large amounts of memory to perform the specific embedded task. Usually, this hardware setup is used for bigger embedded systems.

Embedded System Software

The embedded software is written to work as a specific task. Usually, it is written in a highlevel programming language like "C/C++", which then is compiled down to machine/hex code that can be loaded into a non-volatile memory within the hardware.

The tasks to be executed must be scheduled by the scheduler appropriately for execution by the CPU as embedded systems deals with time-critical applications.

Therefore, it is important to understand the types of task schedulers that are available and the differences between them.

Types of CPU Scheduling Schemes

There are two types of CPU scheduling schemes and they are:

Pre-emptive Scheduling

In pre-emptive scheduling, CPU resource is allocated to the process for a limited amount of time. The process in execution can be pushed back into a ready queue if there is any other high-priority process that needs CPU for execution. In simple terms, a process can be interrupted during execution and placed back into the ready queue, if it still needs CPU for completion.

Get Help With Your Essay

If you need assistance with writing your essay, our professional essay writing service is here to help!

Essay Writing Service

Non-preemptive scheduling

In this scheduling, once CPU resource is allocated to a process, the process holds the CPU until it completes execution. So, therefore, other processes must wait until the running process completes its execution. This type of task scheduling is also called Co-operative scheduling, as the processes wait in queue for the CPU resource until the running process releases it.

The different States of a Process

A process can have five different states and they are as follows:

a. NEW – A process is being created.

b. READY – Process is waiting in the ready queue to get CPU resources for execution.

c. RUNNING – Process currently executed by the CPU.

d. WAITING/BLOCKED – Process is waiting for some external event to occur.

e. TERMINATED – Process has finished execution.

Possible process states under Pre-emptive and Non pre-emptive schedulers A process under the Pre-emptive scheduler can have any of the five states mentioned above. That means the scheduler can re-schedule the process for execution at a later point in time. Usually, a process re-schedule happens when a process is in a RUNNING or WAITING state.

A process under a non-preemptive scheduler can have any of the four states mentioned in the above list, except the WAITING state, which means there is no choice of re-scheduling a process in this scheduler. Once a process enters into the RUNNING state, then the next stage of that process will be the TERMINATED state.

Types of Modeling of Systems

There are two types of modeling systems and they are:

1. Finite State Machines.

2. Petri Net

The differences between these two modeling systems are that in Finite State Machines, the system can only be in any one state at a given point in time, whereas in Petri nets multiple locations can contain one or more tokens representing concurrency in the system.

Finite State Machines

A model of computation based on a hypothetical system consisting of one or more states is a finite-state machine, in short, it is called FSM. Only a single state can be active at the same time, so to perform various actions, the system must switch from one state to another. A graph, where the nodes are the states and the edges are the transitions, can represent an FSM. Each edge has a label that tells when the transition should take place. In FSM, all the states are reachable as the FSM consists of only a finite number of states.

The task scheduler experiment is based on the FSM model and various states of the system transitions are shown in Diagram-4 of this document. An example of FSM model is shown below:

Petri Net

Petri nets are used as a tool for studying systems. Petri nets are represented using arcs, places, and transitions. The places in the Petri nets hold tokens. The state of the system is based on the marking of a net by assigning tokens to the places. An example of Petri-net is shown below:

Places in the Petri net can hold multiple tokens. Transitions cannot hold any tokens, but they transfer the token from one place to another place as per the arc direction. When the number of tokens in the input places is equal to the weight of the arc going from the place to the transition, then a transition is set to be enabled. A transition that is enabled may fire at any time. When a transition is fired, the tokens in the input places are moved to output places, as per the place capacities and arc weights. The transition results in a net with new markings. Petri nets can be used to represent concurrent systems.

Specification

Time-Triggered Co-operative Scheduler

This scheduler is a type of non preemptive scheduler and is known as TTCS in short. Illustration of Time-Triggered Co-operative scheduler is shown in diagram-1, where three processes are running in sequence. It could be noticed that the time taken by each task varies and other tasks wait until the current task completes execution. TASK-B and TASK-C wait until TASK-A completes execution. TASK-C waits until TASK-B completes its execution.

Why Co-operative scheduler?

The co-operative scheduler is chosen because all the tasks are equal, small, and take the same amount of time. Also, there are advantages of using this type of scheduler for smaller tasks and they are:

• It offers a low scheduling overhead.
• It offers high throughput.
• It is very simple to implement.
• Less computational resources are required.

Embedded Hardware and Software used for TTCS

Hardware Details

The hardware board used for TTCS implementation consists of an ARM7 processor and this CPU is based on RISC architecture (reduced instruction set computer). This processor supports clock speed up to 100MHz at 2.5v and 66MHz at 2.3v. It is a 32bit processor and has the operation modes mentioned in Table-1.

The technical details provided in the table-1 are from the online processor's technical manual whose reference is provided in the reference section.

Table 1 - Operating Modes of ARM7

The above modes are used for servicing or accessing resources safely during interrupts or exceptions. CPSR code is a code used to set the value in the Current Program Status Register. System mode can be entered from any other Privileged mode but not from User mode. It should be noted that except for User mode all other modes are privileged mode which is used for handling exceptions.

As per the objective of the coursework, we need to schedule six periodic tasks which in turn illuminate the LED's present on the hardware board. The sequence and the associated task number for each LED's on the hardware board is shown in diagram-2:

Diagram 2 - LED Pattern/Sequence

The register address of the above LEDs is pre-defined in the program's header file (.h). To lit the LED, the program must set the appropriate bit value in the LED register. The value of the LED register can be set only by being in the privileged mode (SVC) during program runtime.

Software Details

The scheduler code is developed using "C" programming. Komodo debugger for ARM processor is used to run the ARM processor code. All required ARM libraries are used to compile the "C" code to generate the ARM-compatible executable program. The software toolchain used in this experiment is a custom monitor debugger - KMD

(Komodo), which is a graphical debugger tool, developed by "Charlie Brej" et al. for Manchester University and is made available to the public through the following Web Link: https://studentnet.cs.manchester.ac.uk/resources/software/komodo/.

This debugger is used to load and execute the compiled "C" program in the target hardware board. All the CPU register values can be examined in this tool. There are a host of features that makes it easy to examine and debug the code.

Image 1 - Screenshot of Komodo debugger software tool

Modeling of TTCS Scheduler Using FSM

Design of the TTCS scheduler

Diagram -3 shows the design of the time-triggered co-operative scheduler, which will be developed in this experiment. It could be noticed that there are six tasks and are released by the timer interrupt at a time. There is a total of eight tasks and six tasks are grouped to execute in odd and even cycles and the same is shown in diagram-3.

Diagram 3 – Co-operative scheduler of six tasks for each timer interrupt.

Finite State Machine (FSM) of the TTCS Scheduler

The finite state machine diagram for the time-triggered scheduler is shown in diagram-4.

There are six states in this FSM. From the "initialize" state (main) it transitions to the "sleep" state by setting a timer interrupt which in turn transitions to the "update" state after 1millisecond.

In the "update" state, the tasks queue is loaded with six tasks based on the odd/even execution cycle.

Post task queue updates, the system transitions to the "dispatcher" state where the tasks are dispatched one by one to the "task" state. Here, the task queue index is incremented by one for every task release from the queue. Once the task queue becomes empty it transitions to a "sleep" state by setting the timer interrupt. If the task queue is not empty it will transition to the "task" state, at this point, it will change the ARM processor mode to SVC_MODE i.e., supervisor mode before transitioning.

Once the system transitions to the "task" state the LED value appropriate to the task number is copied into the LED register. At this stage, the ARM operating mode will be changed to USR mode, since the tasks should be executed in the user mode. Post these changes the system transitions to the "swi" state. If in case a task takes more CPU time than the allocated time then the system will be transitioned to the "update" state to re-order the tasks to place the bad task at the end of the task queue.

Also, pulse width modulation (PWM) calculations for controlling the brightness of the LEDs will be performed in this state. Once the brightness of LEDs calculations is performed the LED register is set with the appropriate value (on or off) and transitioned to the "swi" state.

In the "swi" state software interrupt instruction is used to enter the supervisor mode. Using "SWI" interrupt causes the system to act as a hardware interrupt and this is an unscheduled subroutine call that puts the processor into a privileged mode. In this experiment, the call to "swi" interrupt is used because it allows a program to switch to a privileged mode from User mode. From this "swi" state, the system transitions to the "dispatcher" state to process the next task in the queue.

Diagram 4 – FSM of TTCS Scheduler.

TTCS Implementation and flow chart

The implementation of the TTCS scheduler consists of several states as described in the FSM diagram-4. To achieve these states in "C" programming "naked" functions are used in which there are no return statements from methods or subroutines. Also, pre-processor macros are used to define interrupts, for example, the "IRQ_ENABLE" is defined as an ARM assembly language in the "C" programming header file. Using this macro the code in the program will be replaced with the assembly language.

So, using this macro will execute the ARM assembly code. Even the register addresses are predefined in the header file as macros. Please note that this information is not described in the TTCS flow chart. The source code of the header file is provided in the Appendix-1 section of this document for reference.

Before starting the explanation of the logic implemented in each state of the TTCS scheduler, it is important to understand the data structure used to store and process the data for the scheduler. A typedef structure in "C" programming is used to store the data related to the tasks. The variable parameters that are used in this data structure are as follows, all variable types used in the structure are integers:

Code snippet:

typedef struct { int led, brt_cnt, bad_task, fault_freq_cnt, pwm_cnt; } pwm_data;

pwm_data pwm_tasks[TOTAL_TASKS+1];.

To store data for eight tasks an array of the data structure of size eight is created. The data stored in this data structure for each task is related to the LED brightness, task status (bad or good), bad task recovery time, and pulse width modulation timer counter.

Start or Initialize state: This is the starting state where all the required variables are initialized and timer interrupt is set before transitioning to the "sleep" state. An IRQ request happens due to the timer interrupt and the system transitions to the "irq" state. The "irq" state is known as the "update" state in the FSM diagram-4. In this state, tasks are populated into the task queue based on the odd/even cycle. The odd/even cycle is tracked using an integer variable.

Since timer interrupt plays an important role here, let's look at the timer interrupt details and its functionality in this experiment.

Diagram -5 shows the timer interrupt circuit, whose register addresses are predefined in the "C" header file as a pre-processor macro. Using these macros, values could be set into the register. Once, the timer approaches the set time in the program an IRQ_ENABLE will be executed. IRQ_ENABLE is defined as a macro with ARM assembly code and is given below.

mrs r2, cpsr bic r2, r2, #0x80

msr cpsr_c, r2

Diagram 5 – Timer Interrupts Image source - Lecture videos

Details on the task queue population in odd and even cycles are as follows. In even cycle i.e., cycle "0" tasks populated into the task queue are 0,1,2,3,4,5 and in odd cycle i.e., cycle "1" tasks 6,7,0,1,2,3 are populated into the task queue. It could be noticed that tasks 0,1,2,3 are populated in both cycles. Therefore, these tasks will run continuously, whereas tasks 6,7,4,5 will be executed in alternate cycles. To populate these tasks into the task "queue" array, we use a "for" loop with maximum value as the number of tasks in each cycle. For even cycle, the tasks to be populated are different, therefore, "if" conditions are used to populate the task queue.

An illustration of the task queue in odd and even cycles are given in diagram-6:

Even Cycle Odd Cycle

Diagram – 6: Odd/Even cycle tasks

Code snippet for the task population in odd cycle is given below: for (int i=0; i<=max_iter; i++) { task_no += 1; if (count > 0) {

int task_val = q_index + i + 1; if (max_iter != TASKS) {

task_val = q_index + task_no + 1;

}

if (pwm_tasks[task_val].bad_task == 1) {

queue[TASKS] = task_val;

max_iter--; i--; } else {

queue[i] = task_val; // LED task numbers 6,7 (LED 7,8).

} count--; } else {

int task_val = i - 2; if (max_iter != TASKS) {

task_val = task_no - 2;

}

if (pwm_tasks[task_val].bad_task == 1) {

queue[TASKS] = task_val;

max_iter--; i--; } else {

queue[i] = task_val; // LED task values 0,1,2,3.

}

}

}

A global integer variable named "q_index" is used to navigate the task queue to fetch the task numbers and the value of this variable is incremented for every task execution. The value of this variable is incremented in the "dispatcher" state.

The odd and even cycles are tracked in the program using an integer variable and the following code snippet shows how it is achieved:

odd_even = !odd_even;

Experiments

Two experiments are performed as part of the TTCS implementation and they are:

1. Task overrun protection in the form of tasks re-order in the task queue.

2. PWM implementation for LEDs to increase and decrease brightness over time.

Tasks overrun protection

To test the overrun protection a bad task must be simulated. In this experiment, a bad task is simulated by considering the task number in a shared global variable. We perform checks on the tasks while populating the tasks into the task queue. If any of the tasks are marked as bad tasks then that task will be put to last in the task queue.

Illustration of tasks re-order in the tasks queue is shown below, task "1" is considered a bad task in an even cycle, and task "6" is considered as a bad task in the odd cycle.

Bad tasks

Even cycle Odd cycle

A time counter is kept to track the bad task which will be incremented for every odd and even cycle of task execution, once this counter reaches a pre-defined time value, a recovery on the bad task will be performed. After the recovery, the bad task counter and the bad task status of that task will be reset to zero.

Code macros for bad task and the error recovery is shown below:

// ERROR DETECTION AND REORDER.

#define BAD_TASK -1 #define FAULT_RECOVER_CNT 10000

To simulate the bad task, setting the value of the "BAD_TASK" macro will set the specified task as bad for simulating purpose and the corresponding LED will not be illuminated until error recovery on that task takes place. Once the recovery of the bad task has been performed the LED of the corresponding task will start illuminating.

Introduction to Pulse Width Modulation (PWM)

Pulse Width Modulation is a process in which the output signal is controlled by means of chopping the input signal into discrete parts, hence reducing the average output power. In Diagram-6 a square wave input/output signal is shown, in which it could be noticed that the input signal is reduced to half in the output signal.

The term "Duty Cycle" is used to express the proportion of "on" time to that of the input signal over a period of time and is represented in percentage. Signal high represents "on" and low represents "off". The duty cycle of the signal shown in Diagram-6 is 50%.

^{Original Signal}

^{Discrete-Time parts - LED on-off}

Diagram 6 – PWM input/output signal

Application of PWM to the brightness of the LED tasks

The brightness of the LED lights related to the tasks is controlled by dividing the time duration of the LED illumination into discrete parts. In this experiment, all the six tasks in each cycle are executed in 1-millisecond, therefore for a 1000-millisecond (1 second) duration 50% duty cycle could be achieved by illuminating the LED light for 500milliseconds. But it should be noted that 1000-milliseconds should be divided into discrete time duration parts in such a way that LEDs are gaining and reducing brightness gradually, rather than switching it on and off for 500-milliseconds.

Find Out How UKEssays.com Can Help You!

Our academic experts are ready and waiting to assist with any writing project you may have. From simple essay plans, through to full dissertations, you can guarantee we have a service perfectly matched to your needs.

View our academic writing services

To achieve the gradual brightness, increase and decrease of the LED lights, the two parts of the time duration 500-milliseconds are further divided into discrete time duration parts to achieve 50% of 500-milliseconds in each 500-milliseconds parts. Therefore, 500-milliseconds are split into 20-milliseconds discrete-time duration yielding 25 parts. Therefore, a macro with PWM_CYCLE is defined as 25 in the TTCS code. In this discrete-time duration LED will be switched on for 50% of the time and turned off for the rest of the time. Hence an LED is illuminated for 500-milliseconds in a total of 1000-milliseconds in tiny discrete duration parts yielding a 50% duty cycle.

Macro code for the PWM related data is given below and the brightness of the LEDs are calculated in the "calculate_pwm()" subroutine, which is provided in the source code section – Appendix - 1:

// PWM RELATED VALUES

#define HALF_SEC 500

#define ONE_SEC 1000

#define PWM_CYCLE 25

Discussion

ARM processor runs several processes simultaneously and hence provides several operating modes by which processes get control of the processor, memory, and I/O devices for a limited time. Since the processor and its resources can be shared by several processes, it is important to understand the usage of these modes while programming. These modes provide protected access to the shared resources to avoid other processes interfering while the processor is executing a process.

In this experiment, changing mode to user mode "USR_MODE" to set the LED did not function as intended, therefore code for this is commented out in the source code provided in Appendix-1. Usually, ARM processor mode is changed to user mode while executing the user tasks. User mode is an unprivileged mode and has restricted access to system resources. This is done to avoid potential problems with other processes. After task execution is complete, the mode is changed back to privileged mode as it needs to fetch the next task from the queue. In privilege mode program can access the resources without any restriction.

During the "C" program compilation in this experiment, compilation errors were encountered for assigning a value for shared global variables, it might due to the limitation of ARM-based "C" libraries. Therefore, values to these global variables are assigned inside the "init_values()" method during program runtime. Source code for this experiment can be found in the Appendix-1 section of this document.

Conclusion

To conclude, the experiment on Time-Triggered Cooperative Scheduler has provided knowledge on several topics and concepts, which includes faulty task rescheduling and recovery of the faulty task.

Firstly, details on the types of schedulers available for Real-time embedded systems and how TTCS scheduler as a concurrent process is advantageous over other schedulers in case the tasks are of simple tasks. Also, a study on system modeling using FSM and Petri-nets has provided knowledge on how to model a system and to know various states of the system before proceeding to implement it.

Learning outcome includes gaining a lot of details on the ARM processors which includes the instruction sets and operating modes, a truly hands-on experience working on these processors. Also, to mention the usage of the PWM process to control the brightness of the

task LEDs in this experiment has provided a clear understanding of the PWM concepts and their application to any other projects.