Real Time Operating Systems And Scheduling Techniques Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Abstract- this paper will discuss and give an insight into Real Time Operating Systems (RTOS). What is required and what is needed to be considered when designing a RTOS will be discussed. The characteristics involved in designing a RTOS system will also be mentioned as these characteristics will determine whether a RTOS is efficient, fast, reliable or simply poor.

The scheduling techniques will be explored. What algorithms are available for RTOS and which are most commonly used in today's real time operating systems.

Key works- Real Time Operating System, characteristics, scheduling, algorithm

Introduction

Real Time Operating Systems (RTOS) are an important aspect of everyday life. They are applications that are in control of laboratory experiments, telecommunications, robotics, air traffic control and military command and control systems.

But what exactly is a RTOS???An RTOS is an operating system that has being developed for real time application and embedded systems. It is necessary to give an explanation of what an operation system is and also give a definition for real time application to understand the basic concepts of real time operating systems.

A real time application is an application that guarantees both correctness of result and the added constraint of meeting a deadline.

Operating System will be explained below as it requires more than a definition.

OPERATING SYSTEM

The operating system acts as an mediator between programs and the computer hardware. It provides

Resource allocation

Task management, scheduling and interaction

Hardware abstraction

I/O interface

Time control

Error handling

The core of the operating systems is the Kernel. It is the smallest part of the operating system. Kernel is highly optimized and is typically a set of libraries.

There are a few different types of kernels available.

nanokernel/picokernel - dispatcher

Microkernel - a nanokernel with task scheduling

Kernel- a microkernel with intertask synchronization

Executive- a kernel that includes privatized memory blocks, I/O services, and other complex issues.

Operating System- an executive that also provides generalized user interface, security, file management system, etc

Fig 1 Basic architecture of an operating system

REAL TIME OPERATING SYSTEM CHARACTERISTICS

Now that operating systems are explained and what real time is, RTOS can now be looked into with greater detail. As mentioned above RTOS is an operating system (OS) intended to serve real time applications requests.

There are a number of characteristics that are required for a RTOS. These characteristics for RTOS can be characterized as having unique requirements in 8 general areas:

Hard real-time

Soft real-time

Aperiodic task

Deterministic

Responsiveness

User control

Reliability

Fail-soft operation

Hard real-time - refers to a task that must be completed and meet its deadline. Failure to meet time constraints leads to system failure or unwanted damage causing fatal error to the system.

Soft real-time - refers to a task that is not completed before the deadline but the resulting failure is not critical. Performance is degraded by failure to meet the task time constraints but the task will be completed.

Fig. 2 Illustrate between Soft and Hard tasks

Aperiodic task - has a deadline by which it must finish or start, or it may have a constraint on both start and finish time.

Deterministic - A operating systems is deterministic to the extent that all operations must be time bound. It performs operations at fixed, predetermined times or within predetermined time intervals.

Responsiveness - works in conjunction with deterministic. Deterministic is concerned with how long an operating system delays before acknowledging an interrupt while responsiveness is concerned with how long, after the acknowledgment, it takes an operating system to check the interrupt.

User control - RTOS allow the user control over task priority (aperiodic, hard or soft), control over memory allocation, control over what disk transfer algorithms to be used....etc.

Reliability - RTOS have to be reliable considering they are in control of so much vital operations. Loss or degradation of performance may have horrible and catastrophic consequences resulting in worst case scenario, loss of life. Therefore RTOS must be reliable.

Fail-soft operation - this characteristic refers to the way a system preserved as much capability and data as possible if a system fails.

These characteristics are required to design an effective RTOS. What is required for an actual RTOS design containing all of these characteristics is discussed below.

DESIGN OF AN REAL TIME OPERATING SYSTEM

This section will look at the main requirements for real time operating system design. The design follows the principle of implementing the following:

Memory Management

Multitasking Capabilities

Inter task communication & Recourse sharing

Input/output management

Interrupt Handler

Task and Scheduling

Memory Management - The design of memory allocation is very important for real time operating systems. The general memory schemes utilised to control memory allocation usually fragments memory which can take up valuable time to defragment. This is a major issue for tasks that are time sensitive.

Memory in RTOS, only certain blocks of fixed size of dynamic memory can be required by tasks. This scheme does not allow fragmentation. Also allows the use of malloc() and free() and does not have any garbage collection.

Multi-tasking Capabilities - A RTOS application is divided into multiple tasks. The separation into tasks helps to keep the CPU busy.

Inter task communication and Resource sharing - this involves the communication of tasks to allow the sharing of hardware and data. It is regarded as unsafe for 2 tasks to have access to the same specific data or have access to the same hardware resource simultaneously. This could result in unpredictability or inconsistency behaviour. To prevent this, there are 3 ways available

Binary Semaphores

Message passing

Temporarily masking/disabling interrupted

Input/Output Management - a RTOS must be able to handle input/output devices. There is such a wide variety of applications and devices, therefore it is difficult to develop a consistent solution. The input/output management must be able to deal with the unpredictable behaviour of these devices.

Interrupt Handler - Interrupt handler are used to block the highest priority task from running. These interrupts may be triggered by either hardware or software instructions. RTOS systems are designed to keep interrupt latency to a minimum.

Task and Scheduler - The word task has being used throughout this document and has yet to be explained. It has being accepted that a task is simply a job but has a more important definition.

A task can be described as a piece of executable code. This maybe a function, a program or a kernel module just to name a few. Tasks run concurrently and are designed as a block, Task Control Block (TCB).

This TCB in the RTOS contains the task id, task priority, task status and a copy of the last execution context. An example of a TCB is shown below.

Fig 3 Task control Block

A task can be in 3 states and is controlled by the scheduler.

Running - actually execution

Ready -ready to be dispatched

Blocked - task is blocked by another task or resource and has to wait until state is turned to ready

The scheduler is responsible for scheduling or shuffling tasks between Running and Ready states. Scheduler selects the next task to be executed and maintains queues. The scheduler uses static or dynamic scheduling.

Static scheduling is a complete schedule is computed before execution.

Dynamic scheduling uses priorities assigned to the process to dynamically decide the next executed process.

These scheduling techniques and the algorithms that are used in RTOS to control the Task Control blocks will be discussed in the next section. Below is a figure of the task in operation between states.

Fig. 4 Task in Operation

REAL TIME SCHEDULING ALGORITHMS

There are a number of scheduling algorithms available; they can be classified under these categories

Clock driven scheduling

Weighted Round-Robin Scheduling

Priority Scheduling

Clock Driven Scheduling- Also known as time driven. All parameters about jobs (release time/execution time) known in advance. Decisions on which job to execute are made at specific times. Schedule can be done when computer offline or at some regular time instances (run time use). Clock driven scheduling requires minimal runtime overhead. These types of algorithms are used mostly with static systems. All the properties of all the jobs are known at design time.

Weight Round-Robin Scheduling- this is an advance step from the original Round Robin algorithm. The Round Robin algorithm assigns time slices to each process in equal portions and in circular order. Process handling all process without priority. The time for each process to execute for one slice is known as round. Weighted Round-robin allows processes to run for different lengths of time. Time quantum given to jobs is proportional to its weight. A job with weight wt gets wt time slices each round.

Fig. 5 Weighted Round Robin Scheduling

Priority Scheduling- are a large class of scheduling algorithms that never leave any resource idle intentionally. The decisions for scheduling are made when the release and completion of jobs occur. Priority driven algorithms are used mostly with dynamic systems. They use a mix of periodic tasks and event driven tasks where the system has to modify to changing events and conditions. Within priority scheduling, the scheduling may be premptive, where a task can be temporarily interrupted without requiring the task cooperation and with the intent of resuming the task at a later time, or non-premptive.

There are a number of scheduling algorithms under these categories but this paper will focus on

Rate Monotonic

Deadline Monotonic

Earliest Deadline First

Least Slack Time

As they are the most commonly used algorithms for RTOS and are all priority scheduling.

Rate Monotonic - is a fixed priority algorithm and assigns all tasks the same priority. The priority is based on the tasks period. The shorter the period, the higher the priority. The rate of task release is the inverse of the period. Therefore task with higher rate will have the higher priority. Rate Monotonic can schedule a set of tasks to meet deadlines if the total resource utilization is less than 69.3%

Consider a system with 3 tasks where

T = (phase(Φi),period(pi),execution time(ei),

relative deadline(di))

and where phase(Φi) = 0 by default and

relative deadline(di) = period(pi)

T1 = (3,1) Rate = 1/3

T2 = (5,2) Rate = 1/5

T3 = (9, 5) Rate = 1/9

Results in: T1 > T2 > T3

Fig 6 Demonstrate Rate Monotonic Scheduling of the 3 tasks.

Deadline Monotonic - This scheduling algorithm assigns task priority according to their deadlines. The task with the shortest deadline will be assigned the highest priority. Deadline Monotonic has a close relationship with Real Monotonic. When relative deadline of every task is equal to its period, then Deadline Monotonic and Rate monotonic give same results but if Rate Monotonic fails, Deadline Monotonic will also fail.

Consider a system with 3 tasks where

T = (phase(Φi),period(pi),execution time(ei),

relative deadline(di))

T1 = (50,50,25,100)

T2 = (0,62.5,10,20)

T3 = (0,125,25,50)

In this case using Deadline Monotonic, T2 has the highest priority because its relative deadline is 20. T3 is next in line and T1 has the lowest priority as its relative deadline is 100. If Rate Monotic was used in this case, deadline would be missed.

Fig 7 Demonstrate Deadline Monotonic Scheduling of the 3 tasks.

Earliest Deadline First - (EDF) This is a well known dynamic priority algorithm. Earliest Deadline First assigns priorities to individual jobs in tasks according to their deadline. Earlier deadline is rewarded with a higher priority.

Consider a system with 3 tasks where

T = (phase(Φi),period(pi),execution time(ei),

relative deadline(di))

T1 = (2, 0.9)

T2 = (5, 2.3)

T1 earliest deadline at 0.9 so gets highest priority.

Fig 8 Earliest Deadline First Scheduling of the 3 task

Least Slack Time -(LST) this is another well known algorithm. This algorithm is based on the slack time between execution time t, and remaining execution time tr and has a deadline d. Using the relationship between these, deadline d is equal to d - t - tr. Using the scheduler, it checks the slacks of all the tasks that are ready to be process each time a new task is released. The smaller the slack, the higher the priority.

There are a number of other algorthims available like First-In-First-out (FIFO), Last-In-First-Out(LIFO) and Longest-Execution-Time-First (LETF) but the algorithms mentioned about are the most widely used, hence why this paper explains them in detail.

Example of a Real Time Operating System

VxWorks is a example of a real time operating system. It was created in 1982 and is developed by Wind River Systems. VxWorks is designed for use in embedded systems. It will run on pratically any CPU that is used in the embedded market.

VxWorks is still a popular RTOS and is deployed in over 500million devices around the world. The latest release was of Jan 2010 VxWorks 6.8.

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.