嵌入式系统代写代做代考 Embedded Systems Reconfigurable computing

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