Semaphores and Shared Data

Semaphores and shared data
Reference: Simon Chapter 6
CPE 355 - Real Time Embedded Kernels - Spring 12 Nuno Alves (nalves@wne.edu), College of Engineering
Shared data problems
RTOS can cause a new class of shared-data problems by: Switching the microprocessor from task to task Changing the ow of execution (similar to interrupts) Something called semaphores helps preventing shared
data problems.
Trains do two things with semaphores

1.When a train leaves the protected section of track, it raises the semaphore. 2. 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

No trains allowed in! Train waits until this ag is raised... Train leaves the protected section, allowing the other train in...
RTOS semaphores
Most RTOS normally use the paired terms take and release. Tasks can call two RTOS functions, TakeSemaphore and
ReleaseSemaphore.
Other RTOS paired terms may be get-give, pend-post, wait-signal.
If one task has called Take-Semaphore to take the semaphore and

has not called ReleaseSemaphore to release it, then any other task that calls TakeSemaphore will be blocked until the rst task calls ReleaseSemaphore.
Only one task can have the semaphore at a time.

Tank monitoring system

Imagine I have 300 watering tanks
in my greenhouse
I have one microprocessor that
constantly monitors the water level at every single tank.
It takes a while to determine the

water level for each tank.
Whenever I press a button I want

to immediately know the water level for a particular tank.
Tank monitoring system implemented with semaphores

struct { long ITankLevel; long ITimeUpdated; } tankdata[MAX_TANKS]; /* "Button Task" - High priority */ void vRespondToButton (void) { 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" - Low priority */ void vCalculateTankLevels (void) { int i = 0; while (TRUE) { (...) TakeSemaphore (); !! Set tankdata[i].ITimeUpdated !! Set tankdata[i].ITankLevel ReleaseSemaphore (); (...) } } void main (void) { //Initialize (but do not start) the RTOS InitRTOS (); StartTask StartTask (vRespondToButton, HIGH_ PRIOTY); (vCalculateTankLevels, L0W_PRIOTY);
//Start the RTOS. StartRTOS ();
Sequence of events for the tank monitoring system (part 1/2)

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: 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.
Sequence of events for the tank monitoring system (part 2/2)

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.
Entire sequence of events for the tank monitoring system
Another example: nuclear reactor temperature checking
Premise for the shared-data problem

This is a nuclear reactor. Periodic temperature
measurements occur at two separate locations. two locations are different then sound the alarm! means we may have a nuclear fallout!
If the temperature at these Different temperatures
#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; 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 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
void vReadTemperatureTask (void) { while (TRUE) { //Delay of 0.25 seconds OSTimeDly (5); OSSemPend (p_semTemp, WAIT_FOREVER); !! read in iTemperatures[0]; !! read in iTemperatures[1]; OSSemPost (p_semTemp); } }
#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; 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 vControlTask (void) { p_semTemp = OSSemlnit (1); while (TRUE) { OSSemPend (p_semTemp, WAIT_FOREVER); if ( iTemperatures[0] != iTernperatures[1]) !!Set off howling alarm;
OS_EVENT structure (dened in the RTOS) stores the data that represents the semaphore.
OSSemPost (p_semTemp); !! Do other useful work
#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;
A task rather than an interrupt routine reading the temperatures.
void main (void) { //Initialize (but do not start) the RTOS OSInit ();
OSSemPost and OSSemPend functions // Tell the and RTOS lower about our tasks raise the OSTaskCreate ( vReadTemperatureTask, semaphore. NULLP, WAIT_FOREVER OSTaskCreate ( parameter to the vControlTask, NULLP, (void *)&ControlStk[STK_SIZE], OSSemPend function TASK_PRIORITY_CONTROL); indicates that the task //Start the RTOS. //This function never returns. making the call is willing to OSStart (); wait forever for the semaphore.
(void *)&ReadStk[STK_SIZE], TASK_PRIORITY_READ );
#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; void main (void) { //Initialize (but do not start) the RTOS OSInit (); // OSTaskCreate ( vReadTemperatureTask, NULLP, (void *)&ReadStk[STK_SIZE], TASK_PRIORITY_READ );
vControlTask checks continuously that the two temperatures are equal.
The calls to OSSemPend and OSSemPost in this code x the shared-data Tell the problems. RTOS about our tasks
OSTimeDly function causes current task to OSTaskCreate ( a certain time; block for vControlTask, NULLP, the event that unblocks it (void *)&ControlStk[STK_SIZE], TASK_PRIORITY_CONTROL); is simply the expiration of //Start theamount RTOS. that of time. //This function never returns.
} OSStart ();
#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;
The function OSSemlnit initializes a semaphore.
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);
...What is the problem with this code???
//Start the RTOS. //This function never returns. OSStart ();
#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; void main (void) { //Initialize (but do not start) the RTOS OSInit ();
OSSemlnit must happen before vRead TemperatureTask calls OSSemPend to use the semaphore.
How do you know that this really happens? You // Tell the RTOS about our tasks OSTaskCreate (don't. vReadTemperatureTask, NULLP, ... vReadTemperatureTask OSTaskCreate ( calls OSTimeDly at the vControlTask, NULLP, beginning before calling (void *)&ControlStk[STK_SIZE], TASK_PRIORITY_CONTROL); OSSemPend, vControlTask //Start should the RTOS. (but not //This function never returns. OSStart (); necessarily) have enough time to call OSSemlnit.
(void *)&ReadStk[STK_SIZE], TASK_PRIORITY_READ );
#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; 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);
How do you know that there isn't some higherpriority task that takes up all of the delay time in vReadTemperatureTask? main (void)
OSTimeDly is an attempt at ensuring the system will work as desired.
Best solution is to put OSSemlnit in some startup code that's guaranteed //Start the RTOS. //This never returns. to function run rst... such as the OSStart (); main function.
Reentrancy and semaphores
Semaphores make a function reentrant

void Task1 (void) { (...) vCountErrors (9); (...) } void Task2 (void) { (...) vCountErrors (11); (...) } static int cErrors; static SEMAPHORE semErrors; void vCountErrors (int cNewErrors) { OSSemPend (&semErrors,SUSPEND); cErrors += cNewErrors; OSSemPost (&semErrors); }
The code that modies cErrors is

surrounded by calls to semaphore routines. have protected cErrors with a semaphore.
In the language of data sharing, we Whichever task calls vCountErrors

second will be blocked when it tries to take the semaphore. atomic and therefore have made the function vCountErrors reentrant.
We have made the use of cErrors

void Task1 (void) { (...) OSSemPend (&semErrors,SUSPEND); vCountErrors (9); OSSemPost (&semErrors); (...) } void Task2 (void) { (...) OSSemPend (&semErrors,SUSPEND); vCountErrors (11); OSSemPost (&semErrors); (...) } static int cErrors; static SEMAPHORE semErrors; void vCountErrors (int cNewErrors) { cErrors += cNewErrors; }
Does this code still work if the calls

to OSSemPend and OSSemPost are now around the calls to vCountErrors instead of being within the function itself?

void Task1 (void) { (...) OSSemPend (&semErrors,SUSPEND); vCountErrors (9); OSSemPost (&semErrors); (...) } void Task2 (void) { (...) OSSemPend (&semErrors,SUSPEND); vCountErrors (11); OSSemPost (&semErrors); (...) } static int cErrors; static SEMAPHORE semErrors; void vCountErrors (int cNewErrors) { cErrors += cNewErrors; }
Does this code still work if the calls

to OSSemPend and OSSemPost are now around the calls to vCountErrors instead of being within the function itself?
Yes!
Multiple semaphores
Multiple semaphores
The semaphore functions all take a parameter that identies

the semaphore that is being initialized, lowered, or raised.
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 By having one semaphore protect the temperatures and a
task takes the semaphore to change data in a shared array of temperatures, the highest-priority task might block waiting for that semaphore. 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. corresponding semaphore. protects.
A task that is modifying the error count must take the You must decide what shared data each of your semaphores
Semaphores as a signaling device

Another common use of semaphores is as a simple way to
//Semaphore to wait for report to finish. static 0S_EVENT *semaphoreA; void taskA(void) { (...) //Initialize the semaphore semPrinter = OSSemlnit(O); //take the semaphore OSSemPend (&semaphoreA,SUSPEND); (...) } void interruptA (void) { //Release the semaphore. OSSemPost (&semaphoreA); }
communicate from one task to another (or from an interrupt routine to a task).
The semaphoreA will only be released after the interruptA occurs.
Semaphore problems
Semaphore problem cause #1: Forgetting to take the semaphore

Semaphores do NOT solve all our shared-data problems. In fact, your systems will probably work better, the fewer times
you have to use semaphores.
Semaphores only work if you use them perfectly. Forgetting to take the semaphore: Semaphores only work if
every task that accesses the shared data, for read or for write, uses the semaphore.
Semaphore problem cause #2: Forgetting to release the semaphore
Forgetting to release the semaphore: If any task fails to release
the semaphore, then every other task that ever uses the semaphore will sooner or later be blocked as they wait to take that semaphore.
Semaphore problem cause #3: Taking the wrong semaphore
Taking the wrong semaphore: If you are using multiple
semaphores, then taking the wrong one is as bad as forgetting to take one.
Semaphore problem cause #4: Holding a semaphore for too long
Holding a semaphore for too long: Whenever one task takes a

semaphore, every other task that subsequently wants that semaphore has to wait until the semaphore is released.
Consequence #1: Priority inversion

Lets say consider a system with 3 different tasks:
TaskC (low priority) TaskB (medium priority) TaskA (high priority)

According to our RTOS paradigm, when the system demands a high priority task (TaskA) to be executes, it must be done immediately!
A nasty semaphore problem can arise if the RTOS switches from a lowpriority 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 indenitely.
This is problematic! TaskA, which is a high priority task should have been executed immediately!
Consequence #2: Deadly embrace

int a; int b; static 0S_EVENT *semaphoreA; static 0S_EVENT *semaphoreB; void vTaskl { OSSemPend OSSemPend a = b; OSSemPost OSSemPost } void vTask2 { OSSemPend OSSemPend b = a; OSSemPost OSSemPost } (void) (&semaphoreA,SUSPEND); (&semaphoreB,SUSPEND); (&semaphoreB); (&semaphoreA); (void) (&semaphoreB,SUSPEND); (&semaphoreA,SUSPEND); (&semaphoreA); (&semaphoreB);
In this code
Taskl and Task2 operate on variables a and b after getting permission to use them by getting semaphores SemaphoreA and SemaphoreB.
Do you see the problem?

If vTaskl calls gets SemaphoreA,
but before it can call OSSemPend to get SemaphoreB, the RTOS stops it and runs vTask2.
The task vTask2 now calls

OSSemPend and gets SemaphoreB.
When vTask2 then calls
OSSemPend to get SemaphoreA, it blocks, because another task (vTaskl) already has that semaphore.

The RTOS will now switch back

to vTaskl, which now calls OSSemPend to get SemaphoreB.
Since vTask2 has SemaphoreB,
however, vTaskl now also blocks.

Deadly-embrace problems
would be easy to nd and x if they always looked as clean as this code. However, deadly embrace is just as deadly if vTaskl takes the rst 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 rst. In this case the problem will not be so obvious.

Semaphores and Shared Data

Uploaded by

Document Informationclick to expand document information

Copyright:

Available Formats

Semaphores and Shared Data

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Semaphores and Shared Data

Uploaded by

Copyright:

Available Formats

Semaphores and shared data

Reference: Simon Chapter 6

Shared data problems

Trains do two things with semaphores

The typical semaphore in an RTOS works much the same way

Other RTOS paired terms may be get-give, pend-post, wait-signal.

If one task has called Take-Semaphore to take the semaphore and

Only one task can have the semaphore at a time.

Tank monitoring system

I have one microprocessor that

constantly monitors the water level at every single tank.

It takes a while to determine the

Whenever I press a button I want

Tank monitoring system implemented with semaphores

//Start the RTOS. StartRTOS ();

Sequence of events for the tank monitoring system (part 1/2)

Sequence of events for the tank monitoring system (part 2/2)

Entire sequence of events for the tank monitoring system

Another example: nuclear reactor temperature checking

Premise for the shared-data problem

If the temperature at these Different temperatures

A task rather than an interrupt routine reading the temperatures.

vControlTask checks continuously that the two temperatures are equal.

The function OSSemlnit initializes a semaphore.

...What is the problem with this code???

//Start the RTOS. //This function never returns. OSStart ();

OSTimeDly is an attempt at ensuring the system will work as desired.

Reentrancy and semaphores

Semaphores make a function reentrant

The code that modies cErrors is

In the language of data sharing, we Whichever task calls vCountErrors

We have made the use of cErrors

Reentrancy and semaphores

Does this code still work if the calls

Reentrancy and semaphores

Does this code still work if the calls

The semaphore functions all take a parameter that identies

The semaphores are all independent of one another: if one

What's the advantage of having multiple semaphores?

Semaphores as a signaling device

The semaphoreA will only be released after the interruptA occurs.

Semaphore problem cause #1: Forgetting to take the semaphore

Semaphore problem cause #2: Forgetting to release the semaphore

Forgetting to release the semaphore: If any task fails to release

Semaphore problem cause #3: Taking the wrong semaphore

Taking the wrong semaphore: If you are using multiple

Semaphore problem cause #4: Holding a semaphore for too long

Holding a semaphore for too long: Whenever one task takes a

Consequence #1: Priority inversion

TaskC (low priority) TaskB (medium priority) TaskA (high priority)

Consequence #1: Priority inversion

Consequence #1: Priority inversion

Consequence #1: Priority inversion

Consequence #2: Deadly embrace

Do you see the problem?

Consequence #2: Deadly embrace

If vTaskl calls gets SemaphoreA,

The task vTask2 now calls