Reconfigurable computing
Small Embedded Systems
Unit 6.1 Problems with Sharing Data between Tasks
Introduction
Dealing with a single thread of execution is simple
But normally there are multiple pieces of code that can be triggered in an order that can’t be predicted
Interrupt service routines (ISRs)
RTOS tasks
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
Historic Example: Therac-25 (1985)
Computer controlled machine for radiation therapy
Delivered massive overdoses to at least 6 patients (4 died)
https://www.crcpress.com/authors/i351-john-wang/news/i3158-therac-25-and-industrial-design-engineering-of-socio-technical-systems
Historic Example: Therac-25
Software had race conditions on shared data
Overdose could be triggered by operator typing too fast on console
Dosage mode could change, without operator display being updated to reflect this fact
Predecessor, Therac-20, had hardware interlocks which meant that overdose was impossible.
The software bugs were present, but didn’t matter
Hardware interlocks were removed on Therac-25
Therac-20 software was copied over to Therac-25
Patients died as a result
Access to Shared Resources
Interleaving different tasks, swapping them on and off the processor, can create problems if they access shared memory
If all of the tasks can only read the memory we have no problems
However, if one or more tasks can modify the memory contents, we have a problem
Access to Shared Resources
Example:
Code for handling bank paying-in machine
What happens if two deposits are made at same time by two different tasks?
https://commons.wikimedia.org/wiki/File:Cash-in_machine_(CDM)_of_ABA_Bank.jpg (Creative commons license)
Bank Account Example
Say the account balance starts at £200
We have two deposits: one for £40, one for £30
What is the resulting balance?
If two run in sequence, there is no problem
Task 1 Task 2 Balance
£200
Read balance: £200 £200
Deposit: £40 £200
Update balance: £200+£40 £240
Read balance: £240 £240
Deposit: £30 £240
Update balance: £240+£30 £270
Task 1 Task 2 Balance
£200
Bank Account Example
Say the account starts at £200
We have two deposits: one for £40, one for £30
If the tasks interleave, we have a race condition
The final balance is wrong
Task 1 Task 2 Balance
£200
Read balance: £200 £200
Read balance: £200 £200
Deposit: £30 £200
Deposit: £40 £200
Update balance: £200+£40 £240
Update balance: £200+£30 £230
Task 1 Task 2 Balance
£200
Access to Shared Resources
Result depends on details of order in which tasks are swapped in and out of processor
Result will not always be correct
Code with this problem is hard to test, as problem may manifest only very rarely
How often do two deposits to the same bank account happen simultaneously?
Not often, but with millions of users it will eventually
We run many tests and think the code is OK
Deploy it, and then find it has problems
Protecting Shared Resources
In everyday life, we have resources that only one person can use at a time
We enforce single usage using a lock
A person who acquires use of the resource applies the lock
Others see resource is in use and will not attempt access until lock released
When user is finished, releases the lock
Now others can use the resource
Vacant
Engaged
Software Locks
We have already seen that this code is unsafe
We will make a modification
task1(amount) {
read balance;
deposit amount;
update balance;
}
task2(amount) {
read balance;
deposit amount;
update balance;
}
task1(amount) {
take lock;
read balance;
deposit amount;
update balance;
release lock;
}
task2(amount) {
take lock;
read balance;
deposit amount;
update balance;
release lock;
}
Critical Sections
A code section that must not be accessed concurrently is called a critical section
We have assumed we have some kind of datatype called a lock (we’ll see how it is implemented later)
On entering critical section, we apply lock
On leaving critical section, we release lock
task1(amount) {
take lock;
read balance;
deposit amount;
update balance;
release lock;
}
task2(amount) {
take lock;
read balance;
deposit amount;
update balance;
release lock;
}
Critical section
The Operation of Locks
When a task runs:
If it finds that the critical section is unlocked, the task applies the lock and enters the critical section
If it finds that the critical section has already been locked, the task blocks until the lock is released
On exiting the critical section, a task releases the lock
task1(amount) {
take lock;
read balance;
deposit amount;
update balance;
release lock;
}
task2(amount) {
take lock;
read balance;
deposit amount;
update balance;
release lock;
}
The Operation of Locks
Say task1 and task2 are both ready
Task2 is selected by the scheduler and starts to run
task1(amount) {
take lock;
read balance;
deposit amount;
update balance;
release lock;
}
task2(amount) {
take lock;
read balance;
deposit amount;
update balance;
release lock;
}
Unlocked
Locked
Ready
Ready
The Operation of Locks
Say task1 and task2 are both ready
Task2 is selected by the scheduler and starts to run
Task2 applies the lock and enters critical section…
but then gets swapped out before it completes
It transitions back to the Ready state
task1(amount) {
take lock;
read balance;
deposit amount;
update balance;
release lock;
}
task2(amount) {
take lock;
read balance;
deposit amount;
update balance;
release lock;
}
Unlocked
Locked
Ready
Running
Ready
The Operation of Locks
Task 2 has had its turn, and goes to the back of the queue of ready tasks
Eventually task 1 will be selected to run
It will find the critical section already locked
Task 1 will now stop and go into the blocked state
task1(amount) {
take lock;
read balance;
deposit amount;
update balance;
release lock;
}
task2(amount) {
take lock;
read balance;
deposit amount;
update balance;
release lock;
}
Unlocked
Locked
Ready
Ready
Running
Blocked
The Operation of Locks
Eventually task 2 will be selected to run
It continues from where it left off
It releases the lock and completes
This unblocks task 1
When 1 is next selected to run, it can enter critical section
task1(amount) {
take lock;
read balance;
deposit amount;
update balance;
release lock;
}
task2(amount) {
take lock;
read balance;
deposit amount;
update balance;
release lock;
}
Unlocked
Locked
Blocked
Ready
Running
Ready
Summary
Concurrent tasks create problems for shared data if any of the tasks can modify the data
Regions of code that should only allow access by one task at a time (mutual exclusion) are called critical sections
/docProps/thumbnail.jpeg