1

UNIT-3
Introduction to Real-Time Operating Systems

❖ It is real-time kernel, RTK

❖ Most real-time operating systems are rather different from desktop machine operating
systems.
❖ On a desktop computer the operating system takes control of the machine as soon as it
is turned on and then lets you start your applications.
❖ You compile and link your applications separately from the operating system.
❖ In an embedded system, you usually link your application and the RTOS. At boot-up
time, your application usually gets control first, and it then starts the RTOS.
❖ Many RTOSs do not protect themselves as carefully from your application as do
desktop operating systems.
❖ Whereas most desktop operating systems check that any pointer you pass into a
system function is valid, many RTOSs skip this step in the interest of better
performance.
❖ To save memory RTOSs typically include just the services that you need for your
embedded system and no more.
❖ Vendors: ​VxWorks, VRTX, pSOS, Nucleus, C Executive, ​LynxOS​, QNX, Multi-Task!,
AMX, ​and dozens more.
❖ Unless your requirements for speed or code size or robustness are extreme, the
commercial RTOSs represent a good value, in that they come already debugged and
with a good collection of features and tools.
❖ In many ways the systems are very similar to one another: they offer most or all of the
services discussed in this chapter and the next, they each support various
microprocessors, and so on.
❖ Some of them even conform to the POSIX (Portable Operating System Interface to
define the ​application programming interface (API) for software ) standard (IEEE
standard number 1003.4 )

EMBEDDED SYSTEMSJP
 2

Tasks and Task States:

❖ The basic building block of software written under an RTOS is the task.
❖ Tasks are very simple to write: under most RTOSs a task is simply a subroutine.
❖ At some point in your program, you make one or more calls to a function in the RTOS
that starts tasks, telling it which subroutine is the starting point for each task and some
other parameters.
❖ Most RTOSs allow you to have as many tasks as you could reasonably want.
❖ Each task in an RTOS is always in one of ​three​ states:

1. Running​—which means that the microprocessor is executing the instructions that

make up this task.
2. Ready​—which means that some other task is in the running state but that this task has
things that it could do if the microprocessor becomes available. Any number of tasks
can be in this state.
3. Blocked​—which means that this task hasn't got anything to do right now, even if the
microprocessor becomes available. Tasks get into this state because they are waiting
for some external event. Any number of tasks can be in this state as well.

❖ Most RTOSs seem to proffer a double handful of other task states. Included among
the offerings are suspended, pended, waiting, dormant, and delayed.

The Scheduler:

❖ A part of the RTOS called the scheduler keeps track of the state of each task and
decides which one task should go into the running state.
❖ The schedulers in most RTOSs are entirely simpleminded about which task should get
the processor: they look at priorities you assign to the tasks, and among the tasks that
are not in the blocked state, the one with the highest priority runs, and the rest of them
wait in the ready state.
❖ The lower-priority tasks just have to wait; the scheduler assumes that you knew what
you were doing when you set the task priorities.

EMBEDDED SYSTEMSJP
 3

❖ block to mean "move into the blocked state,"

❖ run to mean "move into the running state“ or "be in the running state,"
❖ switch to mean "change which task is in the running state."

❖ A task will only block because it decides for itself that it has run out of things to do.
Other tasks in the system or the scheduler cannot decide for a task that it needs to wait
for something.
❖ While a task is blocked, it never gets the microprocessor. Therefore, an interrupt
routine or some ​other t​ ask in the system must be able to signal that whatever the task
was waiting for has happened. Otherwise, the task will be blocked forever.
❖ The shuffling of tasks between the ready and running states is entirely the work of the
scheduler. Tasks can block themselves, and tasks and interrupt routines can move
other tasks from the blocked state to the ready state, but the scheduler has control over
the running state.

EMBEDDED SYSTEMSJP
 4

​ he
❖ How does the scheduler know when a task has become blocked or unblocked? T
RTOS provides a collection of functions that tasks can call to tell the scheduler what
events they want to wait for and to signal that events have happened.

❖ What happens if all the tasks are blocked? I​ f all the tasks are blocked, then the
scheduler will spin in some tight loop somewhere inside of the RTOS, waiting for
something to happen. If nothing ever happens, then that's your fault. You must make
sure that something happens sooner or later by having an interrupt routine that calls
some RTOS function that unblocks a task. Otherwise, your software will not be doing
very much.

❖ What if two tasks with ​the same priority are ready? ​The answer is depending upon
which RTOS you use. At least one system solves this problem by making it illegal to
have two tasks with the same priority. Some other RTOSs will time-slice between two
such tasks. Some will run one of them until it blocks and then run the other.

❖ If one task is running and another, higher-priority task unblocks, does the task ​that is
running get stopped and moved to the ready state right away? ​A preemptive RTOS
will stop a lower-priority task as soon as the higher-priority task unblocks. A
nonpreemptive RTOS will only take the microprocessor away from the lower-priority
task when that task blocks.
A Simple Example:

❖ An RTOS can make a difficult system easy to build. This pseudo-code is from the
underground tank monitoring system
❖ vLevelsTask task uses up a lot of computing time figuring out how much gasoline is
in the tanks
❖ Low-priority vLevelsTask task
❖ High-priority vButtonTask task
❖ One convenient feature of the RTOS is that the two tasks can be written
independently of one another, and the system will still respond well.

EMBEDDED SYSTEMSJP
 5

Uses for Tasks:

EMBEDDED SYSTEMSJP
 6

/* "Button Task" */

void vButtonTask (void) /* High priority */

while (TRUE)

!! ​Block until user pushes a button

!!​ Quick: respond to the user

/* "Levels Task" */

void vLevelsTask (void) /* Low priority */

while (TRUE) {

!! ​Read levels of floats in tank

!!​ Calculate average float level

!! ​Do some interminable calculation

!! ​ Do more interminable calculation

!! ​Do yet more interminable calculation

!! ​Figure out which tank to do next

EMBEDDED SYSTEMSJP
 7

RTOS Initialization Code:

• InitRTOS: initializes the RTOS data structures

• StartRTOS: starts the RTOS running, never returns;

EMBEDDED SYSTEMSJP
 8

void main (void)

/* Initialize (but do not start) the RTOS */

InitRTOS ();

/* Tell the RTOS about our tasks */

StartTask (vRespondToButton, HIGH_PRIORITY);

StartTask (vCalculateTankLevels, L0W_PRI0RITY);

/* Start the RTOS. (This function never returns.) */

StartRTOS ();
}
Tasks and Data
❖ Each task has its own private context, which includes the register values, a program
counter, and a stack.
❖ However, all other data—global, static, initialized, uninitialized, and everything
else—is shared among all of the tasks in the system.
❖ As shown in Figure, Task 1, Task 2, and Task 3 can access any of the data in the
system.
❖ The RTOS typically has its own private data structures, which are not available to any
of the tasks.

EMBEDDED SYSTEMSJP
 9

❖ Since you can share data variables among tasks, it is easy to move data from one task
to another: the two tasks need only have access to the same variables.
❖ You can easily accomplish this by having the two tasks in the same module in which
the variables are declared, or you can make the variables public in one of the tasks
and declare them extern in the other.
❖ vRespondToButton task prints out some data that is maintained by the
vCalculateTankLevels task.
❖ Both tasks can access the tankData array of structures just as they could if this system
were written without an RTOS.

EMBEDDED SYSTEMSJP
 10

❖ Sharing Data among RTOS Tasks:

EMBEDDED SYSTEMSJP
 11

struct {

long ITankLevel;

long lTimellpdated;

} tankdata[MAX_TANKS];

/* "Button Task" */

void vRespondToButton (void) /* High priority */{

int i;

while (TRUE){

!! ​Block until user pushes a button

i = !! ​ID of button pressed;

printf ("​\nTIME​: %081d LEVEL: %081d",

tankdata[i].ITimeUpdated,

tankdata[i].ITankLevel);

}}

/* "Levels Task" */

void vCalculateTankLevels (void) /* Low priority */{

int i =0;

while (TRUE) {

!! ​Read levels of floats in tank i

!!​ Do more interminable calculation

!! ​Do yet more interminable calculation

/* Store the result */

tankdata[i] .ITimeUpdated = !! ​Current time

EMBEDDED SYSTEMSJP
 12

/* ​Between these two instructions is a bad place for a task switch */

tankdata[i] .ITankLevel = !! ​Result of calculation

!! Figure out which tank to do next

i = !! ​something new

}}

❖ Shared-Data Problems:
❖ Bugs cropped up because an interrupt routine shared data with task code in the
system.
❖ Two tasks sharing data, and unfortunately all of the same kinds of bugs can come
right back to haunt us.
❖ The RTOS might stop vCalculateTankLevels at any time and run vRespondToButton.
❖ However, the RTOS might stop vCalculateTankLevels right in the middle of setting
data in the tankdata array (which is not an atomic operation), and vRespondToButton
might then read that half-changed data.
❖ In it, both Task1 and Task2 call vCountErrors. This is a perfectly valid thing to do in
an RTOS: any or all of the tasks can share as many subroutines as is convenient.
❖ The difficulty with the program in below task code is that because both Task1 and
Task2 call vCountErrors, and since vCountErrors uses the variable cErrors, the
variable cErrors is now shared by the two tasks (and again used in a nonatomic way).
❖ If Task1 calls vCountErrors, and if the RTOS then stops Task1 and runs Task2, which
then calls vCountErrors, the variable cErrors may get corrupted in just the same way
as it would if Task2 were an interrupt routine that had interrupted Task1.

EMBEDDED SYSTEMSJP
 13

Tasks Can Share Code:

void Task1 (void) {

vCountErrors (9);

void Task2 (void) {

vCountErrors (11); .

static int cErrors;

void vCountErrors (int cNewErrors) {

cErrors += cNewErrors;

❖ The assembly code for vCountErrors is at the top of that figure; below it is a potential
sequence of events that causes a bug.
❖ Suppose that the value 5 is stored in cErrors. Suppose that Task1 calls
vCountErrors(9), and suppose that vCountErrors does the MOVE and ADD
instructions, leaving the result in register R1(14).
❖ Suppose now that the RTOS stops Task1 and runs Task2 and that Task2 calls
vCountErrors (11). The code in vCountErrors fetches the old value of cErrors(5), adds
11 to it, and stores the result(16).
❖ Eventually, the RTOS switches back to Task1, which then executes the next
instruction in vCountErrors, saving whatever is in register R1(14) to cErrors and
overwriting the value written by Task2(16).

EMBEDDED SYSTEMSJP
 14

❖ Instead of cErrors ending up as 25 (the original 5, plus 11 plus 9), as it should, it ends
up as 14.

EMBEDDED SYSTEMSJP
 15

❖ Reentrancy:

❖ Reentrant functions are functions that can be called by more than one task and that
will always work correctly, even if the RTOS switches from one task to another in the
middle of executing the function. The function vCountErrors does not qualify.
❖ You apply three rules to decide if a function is reentrant:

- A reentrant function may ​not u​ se variables in a nonatomic way unless they are
stored on the stack of the task that called the function or are otherwise the
private variables of that task.

- A reentrant function may ​not c​ all any other functions that are not themselves
reentrant.

- A reentrant function may ​not u​ se the hardware in a nonatomic way.

A Review of C Variable Storage:

❖ To better understand reentrancy, and in particular rule 1 above, you must first
understand where the C compiler will store variables.
❖ Review your knowledge of C by examining below task code and answering these
questions:

- Which of the variables in below task code are stored on the stack and which in
a fixed location in memory?

- What about the string literal "Where does this string go?"

- What about the data pointed to by vPointer? By parm_ptr?

EMBEDDED SYSTEMSJP
 16

❖ Task code for Variable Storage

static int static_int;

int public_int;

int initialized = 4;

char *string = "Where does this string go?";

void *vPointer;

void function (int parm, int *parm_ptr)

static int static_local;

int local;

❖ static_int—is in a fixed location in memory and is therefore shared by any task that
happens to call function.
❖ public_int—Ditto. The only difference between static_int and public_int is that
functions in other C files can access public_int, but they cannot access static_int.
❖ initialized—The same. The initial value makes no difference to where the variable is
stored.
❖ string—The same.
❖ "Where does this string go?"—Also the same.
❖ vPointer—The pointer itself is in a fixed location in memory and is therefore a shared
variable. If function uses or changes the data values ​pointed to b​ y vPointer, then those
data values are ​also s​ hared among any tasks that happen to call function.

❖ parm—is on the stack. If more than one task calls function, parm will be in a different
location for each, because each task has its own stack.
❖ parm_ptr—is on the stack. Therefore, function can do anything to the value of

EMBEDDED SYSTEMSJP
 17

parm_ptr without causing trouble. However, if function uses or changes the values of
whatever is ​pointed to b​ y parm_ptr, then we have to ask where ​that d​ ata is stored
before we know whether we have a problem.
❖ static_local—is in a fixed location in memory. The only difference between this and
static_int is that static_int can be used by other functions in the same C file, whereas
static_local can only be used by function.
❖ local—is on the stack.

Applying the Reentrancy Rules:

❖ This function is not reentrant, for two reasons.

❖ First, the variable fError is in a fixed location in memory and is therefore shared by
any task that calls display.
❖ The use of fError is not atomic, because the RTOS might switch tasks between the
time that it is tested and the time that it is set. This function therefore violates rule 1.
❖ Note that the variable j is no problem; it's on the stack.
❖ The second problem is that this function may violate rule 2 as well.
❖ For this function to be reentrant, printf must also be reentrant. Is printf reentrant?

EMBEDDED SYSTEMSJP
 18

​Another Reentrancy Example

BOOL fError; /* Someone else sets this */

void display (int j)

if (!fError)

printf ("​\nValue​: %d", j);

j = 0;

fError = TRUE;

else

printf ("​\nCould​ not display value");

fError = FALSE;

}}

Gray Areas of Reentrancy:

❖ There are some gray areas between reentrant and nonreentrant functions. The code
here shows a very simple function in the gray area.

❖ static int cErrors;

❖ void vCountErrors (void) {++cErrors; }

❖ This function obviously modifies a nonstack variable, but rule 1 says that a reentrant
​ he question is: is
function may not use nonstack variables ​in a nonatomic way. T
incrementing cErrors atomic?

EMBEDDED SYSTEMSJP
 19

❖ If you're using an 8051, an 8-bit microcontroller, then ++cErrors is likely to compile

into assembly code something like this:

MOV DPTR,#cErrors+01H

MOVX A,@DPTR

INC A

MOVX ©DPTR,A

JNZ noCarry

MOV DPTR,# cErrors

MOVX A,@DPTR

MOVX ©DPTR,A

noCarry:

RET
❖ which doesn't look very atomic and indeed isn't anywhere close to atomic, since it
takes nine instructions to do the real work, and an interrupt might occur anywhere
among them.

❖ if you're using an Intel 80x86, you might get:

❖ INC (cErrors)

❖ RET
❖ If you really need the performance of the one-instruction function and you're using an
80x86 and you put in lots of comments, perhaps you can get away with writing
vCountErrors this way.
❖ However, there's no way to know that it will work with the next version of the
compiler or with some other microprocessor to which you later have to port it.

EMBEDDED SYSTEMSJP
 20

​Semaphores and Shared Data:

❖ RTOS can cause a new class of shared-data problems by switching the
microprocessor from task to task and, like interrupts, changing the flow of execution.
❖ Trains do two things with semaphores. First, when a train leaves the protected section
of track, it raises the semaphore. Second, when a train comes to a semaphore, it waits
for the semaphore to rise, if necessary, passes through the (now raised) semaphore,
and lowers the semaphore. The typical semaphore in an RTOS works much the same
way.
❖ Railroad semaphore

RTOS Semaphores
❖ No RTOS uses the terms raise and lower; they use get and give, take and release, pend
and post, p and v, wait and signal, and any number of other combinations. This book
use take (for lower) and release (for raise).
❖ A typical RTOS binary semaphore: tasks can call two RTOS functions, Take
Semaphore and Release Semaphore. If one task has called Take-Semaphore to take
the semaphore and has not called Release Semaphore to release it, then any other task
that calls Take Semaphore will block until the first task calls ReleaseSemaphore. Only

EMBEDDED SYSTEMSJP
 21

one task can have the semaphore at a time.

Semaphores Protect Data:

EMBEDDED SYSTEMSJP
 22

struct

long ITankLevel;

long ITimeUpdated;

} tankdata[MAX_TANKS];

/* "Button Task" */

void vRespondToButton (void) /'* High priority */

int i;

while (TRUE)

!! ​Block until user pushes a button

i = !! ​Get ID of button pressed

TakeSemaphore ();

printf ("​\nTIME​: %081d LEVEL: %081d",

tankdata[i].ITimeUpdated,

tankdata[i].ITankLevel);

ReleaseSemaphore ();

/* "Levels Task" */

void vCalculateTankLevels (void) /* Low priority */

EMBEDDED SYSTEMSJP
 23

int i = 0;

while (TRUE)

TakeSemaphore ();

!!​ ​Set tankdata[i].ITimeUpdated

!! Set tankdata[i].ITankLevel

ReleaseSemaphore ();

❖ If the user presses a button while the levels task is still modifying the data and still has
the semaphore, then the following sequence of events occurs:

EMBEDDED SYSTEMSJP
 24

1. The RTOS will switch to the "button task," just as before, moving the levels task to
the ready state.

2. When the button task tries to get the semaphore by calling TakeSemaphore, it will
block because the levels task already has the semaphore.

3. The RTOS will then look around for another task to run and will notice that the levels
task is still ready. With the button task blocked, the levels task will get to run until it
releases the semaphore.

4. When the levels task releases the semaphore by calling ReleaseSemaphore, the
button task will no longer be blocked, and the RTOS will switch back to it.

EMBEDDED SYSTEMSJP
 25

The nuclear reactor system:

❖ A task rather than an interrupt routine reading the temperatures
❖ OSSemPost and OSSemPend functions raise and lower the semaphore
❖ OSSemCreate function initializes the semaphore, and it must be called before either
of the other two.

EMBEDDED SYSTEMSJP
 26

❖ OS_EVENT structure stores the data that represents the semaphore

❖ WAIT_FOREVER parameter to the OSSemPend function indicates that the task
making the call is willing to wait forever for the semaphore

❖ OSTimeDly function causes vReadTemperatureTask to block for approximately a

quarter of a second; the event that unblocks it is simply the expiration of that amount
of time.
❖ vControlTask checks continuously that the two temperatures are equal
❖ The calls to OSSemPend and OSSemPost in this code fix the shared-data problems

Semaphores Protect Data in the Nuclear Reactor

#define TASK_PRIORITY_READ 11

#define TASK_PRIORITY_CONTROL 12

#define STK_SIZE 1024

static unsigned int ReadStk [STK_SIZE];

static unsigned int ControlStk [STK_SIZE];

static int iTemperatures[2];

OS_EVENT *p_semTemp;
Figure 6.14 Semaphores Protect Data in the Nuclear Reactor

EMBEDDED SYSTEMSJP
 27

void main (void)

/* Initialize (but do not start) the RTOS */

OSInit ();

/* Tell the RTOS about our tasks */

OSTaskCreate (vReadTemperatureTask, NULLP,

(void *)&ReadStk[STK_SIZE], TASK_PRIORITY_READ);

OSTaskCreate (vControlTask, NULLP,

(void *)&ControlStk[STK_SIZE], TASK_PRIORITY_CONTROL);

/* Start the RTOS. (This function never returns.) */

OSStart ();

void vReadTemperatureTask (void)

while (TRUE)

OSTimeDly (5); /* Delay about 1/4 second */

OSSemPend (p_semTemp, WAIT_FOREVER);

!!​ ​read in iTemperatures[0];

!! read in iTemperatures[1];

OSSemPost (p_semTemp);

EMBEDDED SYSTEMSJP
 28

void vControlTask (void)

p_semTemp = OSSemlnit (1);

while (TRUE)

OSSemPend (p_semTemp, WAIT_FOREVER);

if (iTemperatures[0] != iTernperatures[1])

!!​Set off howling alarm;

OSSemPost (p_semTemp);

!! ​Do other useful work

Initializing Semaphores:

❖ The bug arises with the call to OSSemCreate, which must happen before
vRead​TemperatureTask calls OSSemPend to use the semaphore.
❖ How do you know that this really happens? You don't.
❖ Since vReadTemperatureTask calls OSTimeDly at the beginning before calling
OSSemPend, vControlTask should have enough time to call OSSemCreate.
❖ How do you know that there isn't some higher-priority task that takes up all of the
delay time in vReadTemperatureTask?

❖ You can make it work for sure by giving vControlTask a higher priority than
vReadTemperatureTask. Yes, that's true, too . . . until some compelling (and probably
more valid) reason comes up to make vReadTemperatureTask a higher priority than
vControlTask and someone makes the change without realizing that you put this time
bomb into the code.

EMBEDDED SYSTEMSJP
 29

❖ Put the semaphore initialization call to OSSemCreate in some start-up code that's
guaranteed ​to run first. The main function shown in above task code, somewhere
before the call to OSStart, would be a good place for the call to OSSemlnit.

Reentrancy and Semaphores

❖ However, the code that modifies the static variable cErrors is surrounded by calls to
semaphore routines. In the language of data sharing, we have protected cErrors with a
semaphore.
❖ Whichever task calls vCountErrors second will be blocked when it tries to take the
semaphore.
❖ In the language of reentrancy, we have made the use of cErrors atomic and therefore
have made the function vCountErrors reentrant.

EMBEDDED SYSTEMSJP
 30

Void Task1 (void){

vCountErrors (9);

void Task2 (void)

vCountErrors (11);

static int cErrors;

static NU_SEMAPHORE semErrors;

void vCountErrors (int cNewErrors)

NU_Obtain_Semaphore (&semErrors,NU_SUSPEND);

cErrors += cNewErrors;

NU_Release_Semaphore (&semErrors);
}

Multiple Semaphores:

❖ The semaphore functions all take a parameter that identifies the semaphore that is
being initialized, lowered, or raised.

EMBEDDED SYSTEMSJP
 31

❖ The semaphores are all independent of one another: if one task takes semaphore A,
another task can take semaphore B without blocking. Similarly, if one task is waiting
for semaphore C, that task will still be blocked even if some other task releases
semaphore D.

What's the advantage of having multiple semaphores?

❖ Whenever a task takes a semaphore, it is potentially slowing the response of any other
task that needs the same semaphore.
❖ In a system with only one semaphore, if the lowest-priority task takes the semaphore
to change data in a shared array of temperatures, the highest-priority task might block
waiting for that semaphore.
❖ By having one semaphore protect the temperatures and a different semaphore protect
the error count, you can build your system so the highest-priority task can modify the
error count even if the lowest-priority task has taken the semaphore protecting the
temperatures. Different semaphores can correspond to different shared resources.
How does the RTOS know which semaphore protects which data?
❖ It doesn't. If you are using multiple semaphores, it is up to you to remember which
semaphore corresponds to which data.
❖ A task that is modifying the error count must take the corresponding semaphore. You
must decide what shared data each of your semaphores protects.

Semaphores as a Signaling Device:

❖ Another common use of semaphores is as a simple way to communicate from one task
to another or from an interrupt routine to a task.
❖ The task waits for a semaphore after it has formatted each report. The interrupt
routine signals the task when the report has been fed to the printer by releasing the
semaphore; when the task gets the semaphore and unblocks, it knows that it can
format the next report.
❖ The interrupt routine will release the semaphore and thereby unblock the task when
the report is printed.

EMBEDDED SYSTEMSJP
 32

Using a Semaphore as a Signaling Device

EMBEDDED SYSTEMSJP
 33

/* Place to construct report. */

static char a_chPrint[10][21];

/* Count of lines in report. */

static int iLinesTotal;

/* Count of lines printed so far. */

static int iLinesPrinted;

/* Semaphore to wait for report to finish. */

static 0S_EVENT *semPrinter;

void vPrinterTask(void)

BYTE byError; /* Place for an error return. */

Int wMsg;

/* Initialize the semaphore as already taken. */

semPrinter = OSSemlnit(O);

while (TRUE)

/* Wait for a message telling what report to format. */

wMsg = (int) OSQPend (QPrinterTask, WAIT_FOREVER, &byError);

!! ​Format the report into a_chPrint

iLinesTotal = !! ​count of lines in the report

/* ​Print the first line of the report */

i LinesPrinted = 0;

vHardwarePrinterOutputLine (a_chPrint[i LinesPrinted++]);

EMBEDDED SYSTEMSJP
 34

/* Wait for print job to finish. */

OSSemPend (semPrinter, WAIT_FOREVER, &byError);

}}

void vPrinterlnterrupt (void)

if (iLinesPrinted == iLinesTotal)

/* The report is done. Release the semaphore. */

OSSemPost (semPrinter);

else

/* Print the next line. */

vHardwarePrinterOutputLine (a__chPrint[iLinesPrinted++]);

}
Semaphore Problems:

❖ When first reading about semaphores, it is very tempting to conclude that they
represent the solutions to all of our shared-data problems. This is not true. In fact,
your systems will probably work better, the fewer times you have to use semaphores.
❖ The problem is that semaphores work only if you use them perfectly, and there are no
guarantees that you (or your co-workers) will do that.
​ emaphores only work if every task that accesses
❖ Forgetting to take the semaphore. S
the shared data, for read or for write, uses the semaphore.
❖ Forgetting to release the semaphore. I​ f any task fails to release the semaphore, then
every other task that ever uses the semaphore will sooner or later block waiting to
take that semaphore.
❖ Taking the wrong semaphore. I​ f you are using multiple semaphores, then taking the
wrong one is as bad as forgetting to take one.

EMBEDDED SYSTEMSJP
 35

​ henever one task takes a semaphore, every other

❖ Holding a semaphore for too long. W
task that subsequently wants that semaphore has to wait until the semaphore is
released.

Priority inversion:

❖ A particularly perverse instance of this problem can arise if the RTOS switches from a
low-priority task (Task C) to a medium-priority task (Task B) after Task C has taken a
semaphore.
❖ A high-priority task (Task A) that wants the semaphore then has to wait until Task B
gives up the microprocessor: Task C can't release the semaphore until it gets the
microprocessor back.
❖ No matter how carefully you code Task C, Task B can prevent Task C from releasing
the semaphore and can thereby hold up Task A indefinitely. This problem is called
priority inversion; some RTOSs resolve this problem with priority inheritance — they
temporarily boost the priority of Task C to that of Task A whenever Task C holds the
semaphore and Task A is waiting for it.

EMBEDDED SYSTEMSJP
 36

❖ Causing a deadly embrace. ​The below task code illustrates the problem called deadly
embrace. The functions ajsmrsv and ajsmrls in that figure are from an RTOS called
AMX.
❖ The function ajsmrsv "reserves" a semaphore, and the function ajsmrls "releases" the
semaphore.
❖ The two additional parameters to ajsmrsv are time-out and priority information and
are not relevant here.
❖ In the below code, both Taskl and Task2 operate on variables a and b after getting
permission to use them by getting semaphores hSemaphoreA and hSemaphoreB.

EMBEDDED SYSTEMSJP
 37

int a;

int b;

AMXID hSemaphoreA;

AMXID hSemaphoreB;

void vTaskl (void)

ajsmrsv (hSemaphoreA, 0, 0);

ajsmrsv (hSemaphoreB, 0, 0);

a = b;

ajsmrls (hSemaphoreB);

ajsmrls (hSemaphoreA);

void vTask2 (void)

ajsmrsv (hSemaphoreB, 0, 0);

ajsmrsv (hSemaphoreA, 0, 0);

b = a;

ajsmrls (hSemaphoreA);

ajsmrls (hSemaphoreB);

❖ if vTaskl calls ajsmrsv to get hSemaphoreA, but before it can call ajsmrsv to get
hSemaphoreB, the RTOS stops it and runs vTask2.
❖ The task vTask2 now calls ajsmrsv and gets hSemaphoreB.

EMBEDDED SYSTEMSJP
 38

❖ When vTask2 then calls ajsmrsv to get hSemaphoreA, it blocks, because another task
(vTaskl) already has that semaphore.
❖ The RTOS will now switch back to vTaskl, which now calls ajsmrsv to get
hSemaphoreB.
❖ Since vTask2 has hSemaphoreB, however, vTaskl now also blocks.
❖ deadly-embrace problems would be easy to find and fix if they always appeared on
one page of code.
❖ However, deadly embrace is just as deadly if vTaskl takes the first semaphore and
then calls a subroutine that later takes a second one while vTask2 takes the second
semaphore and then calls a subroutine that takes the first.

Types of Semaphores:

Binary Semaphores:

❖ A binary semaphore is a synchronization object that can have only two states:

1. Not taken​.
2. Taken​.

❖ Two operations are defined:

1. Take​ (chBSemWait() in ChibiOS/RT). Taking a binary semaphore brings it in the

“taken” state, trying to take a semaphore that is already taken enters the invoking
thread into a waiting queue.
2. Release​ (chBSemSignal() in ChibiOS/RT). Releasing a binary semaphore brings it in
the “not taken” state if there are not queued threads. If there are queued threads then a
thread is removed from the queue and resumed, the binary semaphore remains in the
“taken” state. Releasing a semaphore that is already in its “not taken” state has no
effect.

Binary semaphores have no ownership attribute and can be released by any thread or
interrupt handler regardless of who performed the last take operation. Because of these binary

EMBEDDED SYSTEMSJP
 39

semaphores are often used to synchronize threads with external events implemented as ISRs,
for example waiting for a packet from a network or waiting that a button is pressed.

Because there is no ownership concept a binary semaphore object can be created to be

either in the “taken” or “not taken” state initially.

Counting Semaphores:

A counting semaphore is a synchronization object that can have an arbitrarily large

number of states. The internal state is defined by a signed integer variable, the counter. The
counter value (N) has a precise meaning:

Negative​, there are exactly -N threads queued on the semaphore.

Zero​, no waiting threads, a wait operation would put in queue the invoking thread.

Positive​, no waiting threads, a wait operation would not put in queue the invoking thread.

Two operations are defined for counting semaphores:

1. Wait​ (chSemWait() in ChibiOS/RT). This operation decreases the semaphore

counter, if the result is negative then the invoking thread is queued.
2. Signal​ (chSemSignal() in ChibiOS/RT). This operation increases the semaphore
counter, if the result is non-negative then a waiting thread is removed from the queue
and resumed.

EMBEDDED SYSTEMSJP
 40

Counting semaphores have no ownership attribute and can be signaled by any thread
or interrupt handler regardless of who performed the last wait operation.

Because there is no ownership concept a counting semaphore object can be created

with any initial counter value as long it is non-negative.

The counting semaphores are usually used as guards of resources available in a

discrete quantity. For example the counter may represent the number of used slots into a
circular queue, producer threads would “signal” the semaphores when inserting items in the
queue, consumer threads would “wait” for an item to appear in queue, this would ensure that
no consumer would be able to fetch an item from the queue if there are no items available.
Note that this is exactly how I/O queues are implemented in ChibiOS/RT, very convenient.

Mutex semaphore:

A mutex is a synchronization object that can have only two states:

1. Not owned​.
2. Owned​.

Two operations are defined for mutexes:

1. Lock​ (chMtxLock() in ChibiOS/RT). This operation attempts to take ownership of a

mutex, if the mutex is already owned by another thread then the invoking thread is
queued.
2. Unlock​ (chMtxUnlock() in ChibiOS/RT). This operation relinquishes ownership of a
mutex. If there are queued threads then a thread is removed from the queue and
resumed, ownership is implicitly assigned to the thread.

EMBEDDED SYSTEMSJP
 41

A mutex can be unlocked only by the thread that owns it, this precludes the use of
mutexes from interrupt handles but enables the implementation of the Priority Inheritance
protocol, most RTOSs implement this protocol in order to address the Priority Inversion
problem. It must be said that few RTOSs implement this protocol fully (any number of
threads and mutexes involved) and even less do that efficiently.

Mutexes have one single use, Mutual Exclusion, and are optimized for that.
Semaphores can also handle mutual exclusion scenarios but are best used as a communication
mechanism between threads or between ISRs and threads.

Binary Counter
Feature Mutexes
Semaphores Semaphores

Internal states 2 N 2
Use from ISRs yes yes No
Ownership no no yes
Priority Inheritance no no yes
either taken or always not
Initialization counter >= 0
not taken owned
Queue organization FIFO or priority FIFO or priority Priority

EMBEDDED SYSTEMSJP