Reconfigurable computing
Small Embedded Systems
Unit 6.2
Locks, Semaphores and Mutexes
Introduction
In most useful code, we have multiple tasks that can be triggered in an order that can’t be predicted
We have a problem if
one task starts to work on a piece of data
before it can finish, another task modifies that data
the original task can’t tell that the data was modified and uses the old data
We will look at mechanisms that enable safe sharing:
Semaphore
Mutex
Semaphores
A semaphore is a data structure commonly used to control and synchronize tasks
Semaphore has a non-negative integer value and supports two operations:
Take(): operation that waits for semaphore to become positive, then decrements it by 1
Give(): operation that increments the semaphore by 1
Any task that had executed a Take on a semaphore and had to wait because it was 0, can now wake up
The theory literature and different programming languages use many different names for these operations:
Take(): P(), wait(), acquire(), down()
Give(): V(), signal(), release(), up()
Semaphore Illustration
Semaphore initialised to 2
Semaphore can be thought of as a pool of permits
Take() takes a permit if one is available, waits if not
Give() returns a permit to the pool
Permits available:
2
1
Take()
0
Semaphore Illustration
Semaphore initialised to 2
Semaphore can be thought of as a pool of permits
Take() takes a permit if one is available, waits if not
Give() returns a permit to the pool
Permits available:
1
Take()
0
Semaphore Illustration
Semaphore initialised to 2
Semaphore can be thought of as a pool of permits
Take() takes a permit if one is available, waits if not
Give() returns a permit to the pool
Permits available:
Take()
1
0
Semaphore Illustration
Semaphore initialised to 2
Semaphore can be thought of as a pool of permits
Take() takes a permit if one is available, waits if not
Give() returns a permit to the pool
Permits available:
Give()
1
0
Semaphore Illustration
Semaphore initialised to 2
Semaphore can be thought of as a pool of permits
Take() takes a permit if one is available, waits if not
Give() returns a permit to the pool
Permits available:
Uses of Semaphores: Mutex
Binary semaphore (initialised to 1)
Mutual exclusion lock on a critical section
Only one task at a time can enter critical section
A Mutex is a special kind of binary semaphore, which has extra features to make it safe:
We’ll see more on that later
task1(amount) {
semaphore.take();
read balance;
deposit amount;
update balance;
semaphore.give();
}
task2(amount) {
semaphore.take();
read balance;
deposit amount;
update balance;
semaphore.give();
}
Critical section
Uses of Semaphores: Synchronisation
Binary semaphore (initialised to 0)
Used by one task to signal to another that it can start
Here are two tasks, but task2’s job make no sense until task1 has completed its work.
We must make sure that they don’t run in the wrong order
task1() {
do_initial_processing();
}
task2() {
do_final_processing();
}
Uses of Semaphores: Synchronisation
Binary semaphore (initialised to 0)
Used by one task to signal to another that it can start
Here are two tasks, but task2’s job make no sense until task1 has completed its work.
We must make sure that they don’t run in the wrong order
If task2 gets picked by the scheduler before task1, it will block when it tries to take the semaphore
When task1 completes its processing, it will give the semaphore and task2 can now run
task1() {
do_initial_processing();
semaphore.give();
}
task2() {
semaphore.take();
do_final_processing();
}
Uses of Semaphores: Synchronisation
Binary semaphore (initialised to 0)
Used by one task to signal to another that it can start
Here are two tasks, but task2’s job make no sense until task1 has completed its work.
We must make sure that they don’t run in the wrong order
If task2 gets picked by the scheduler before task1, it will block when it tries to take the semaphore
When task1 completes its processing, it will give the semaphore and task2 can now run
task1() {
do_initial_processing();
semaphore.signal();
}
task2() {
semaphore.wait();
do_final_processing();
}
Uses of Semaphores: FIFO Queue
A counting semaphore is a semaphore whose maximum value is greater than 1
Common use is producer-consumer problems with buffer
Suppose we have two tasks:
Task 1 produces data to be processed
Task 2 consumes data from the buffer and processes it
Don’t want tasks to operate in precise lockstep, as that would be slow (both tasks go at pace of slowest)
Use FIFO buffer as queue to pass data
Task1
Task2
Uses of Semaphores: FIFO Queue
This is essentially same as railway junction problem earlier
Task1 must stop putting data into queue if it is full
Task 2 must stop taking data from queue if it is empty
Status of queue can be semaphore
Task 1 performs give() operation
Task 2 performs take() operation
Task1
Task2
Interaction of Locks and Priorities
Suppose we have 2 tasks that share a lockable resource
One task is high priority and one is low priority
Low priority task is running and takes lock
Eventually high priority task needs to run and pre-empts
Eventually high priority task requests lock but can’t get it
Low priority task takes over, runs until it releases lock
As soon as lock is released, high priority task pre-empts
Time
High
Low
Take lock
Request lock
Release lock
Take lock
https://science.nasa.gov/toolkits/spacecraft-icons
Interaction of Locks and Priorities
This is fine as long as the low priority task takes the lock for only a very short period of time
It is a rule of concurrent programs that critical sections should be as short and quick as possible
Time
High
Low
Take lock
Request lock
Release lock
Take lock
https://science.nasa.gov/toolkits/spacecraft-icons
Interaction of Locks and Priorities
If a low-priority task holds the lock for a long time, we have a problem
But in well-written code the delay should be short
The worst case hold-up should be incorporated into the utilisation calculation for RMS
Time
High
Low
Take lock
Request lock
Release lock
Deadline missed
https://science.nasa.gov/toolkits/spacecraft-icons
Priority Inversion
Now suppose we have an additional medium priority task
This will cause us a problem:
Priority inversion
High priority task is locked out by medium priority task for so long that it misses its deadline
Time
Medium
Low
High
https://science.nasa.gov/toolkits/spacecraft-icons
Priority Inversion
Low priority task is running and takes lock
Then medium priority task needs to run and pre-empts
Then high priority task needs to run and pre-empts
It requests lock but can’t get it: task blocks
Next highest priority task takes over and keeps running
High priority task is blocked until medium priority finishes
Time
Medium
Low
Take lock
Request lock
Release lock
Deadline missed
High
https://science.nasa.gov/toolkits/spacecraft-icons
Example of Priority Inversion
Sojourner: Mars rover, landed July 1997
Designed to take pictures and perform scientific experiments
After a few days it went into endless cycle of reboots
Problem was priority inversion
Problem was eventually fixed and mission continued
https://science.nasa.gov/toolkits/spacecraft-icons
Mars Rover Priority Inversion
Problem was low priority meteorology task accessed bus
High priority management task also accessed the bus
Coordinated with a Mutex
Long-running communications task was medium priority
Prevented management task from running
Watchdog timer triggered reboot
Time
Comms
Weather
Lock bus
Request bus lock
No input from management task
Watchdog timer triggers reboot
Management
https://science.nasa.gov/toolkits/spacecraft-icons
Priority Inheritance
RTOS had protection against priority inversion
Programmers forgot to turn it on in initial design (but could wirelessly upload a patch to Mars to fix it)
Mutexes can be created with priority inheritance
Low priority task that holds lock is elevated to priority of task that requests lock
Time
Lock bus
Request lock
Task is temporarily high priority
Pre-empt
Release lock
Comms
Weather
Management
Completed
https://science.nasa.gov/toolkits/spacecraft-icons
Summary
Semaphores can be used for mutual exclusion, for resource sharing and for synchronisation of tasks
Mutexes are semaphores with additional features, notably priority inheritance
Priority inversion is a problem that can lock out a high priority task when a low priority task has taken the mutex
Priority inheritance remedies this by promoting a low priority task to the priority of the task that has requested the mutex
/docProps/thumbnail.jpeg