Operation Ordering

Depends on	Concepts • Multi Threading

Computer programs do sets of things; often it does not matter too much the exact order in which things are done. For example, if a program needs to increment a counter and output a value message to the screen it may not matter how this is expressed.

count = count + 1;
printf("Hello.\n");

count = count + 1;
printf("Hello.\n");

On the other hand, sometimes it is relevant – but that is ‘obvious’:

count = count + 1;
printf("count has reached %d.\n", count);

However when there may be parallel threads (or processes) sometimes the order of statements can be important.

Example: linking into a list

Two pseudo-code descriptions of adding a record into a linked list.

1 create new record
2 find position in list for insertion
3 link from 'previous' to new record
4 link from new record to 'next'

1 find position in list for insertion
2 create new record
3 link from new record to 'next'
4 link from 'previous' to new record

Obviously steps 3 & 4 (in either version) depend absolutely on steps 1 & 2. However, in a single threaded environment both versions will work.

In a multi-threaded environment, if other threads use this data structure, one version can fail.

The figure should be adequate to show the potential danger: if another thread traverses the structure between steps 3 & 4, in one case the list is broken, in the other there is still an intact structure. There is a race as to whether another thread sees the structure before or after the insertion – but if this mattered the thread should have been controlled at a more abstract, structural level.

How could this happen?

• Context switching during the insertion sequence
• An interrupt during the insertion sequence
  (arguably a limited context switch).
• Another hardware processor concurrently running an interacting thread.

All of these are unlikely to happen; none is impossible. The fault will occur rarely, unpredictably and intermittently. That just makes debugging a whole lot harder.

What can be done?

The critical section could be locked to ensure that steps 3 & 4 (either version) are atomic. This is safe – and sometimes necessary – but it does involve more code in all interacting threads. In some cases, including this one, locks are not necessary in the second case, resulting in shorter, faster, neater code.

When dealing with multi-threading, always consider the ordering of operations and think of the consequences of different sequences. If something is potentially risky it may be possible to make is safe without locking which is a Good Thing. When you have done this, please please please highlight it with a comment to: a) show how smart you’ve been; b) so no one breaks it in future.

Puzzle: unlinking from the list

This one’s for you. Reverse the problem to take a record out of a linked list. This is not entirely trivial so think hard before you refer to a possible.

Answer

The first thing to do is to unlink the unwanted record from the list (by changing the pointer in ‘previous’). That’s the most obvious bit.

However the record cannot yet be disposed of – someone(s) might still be using it! It can only be marked for deletion for later disposal. This is moving towards the complex area of garbage collection.

Did you spot that second issue?

Caveat!

Remember that modern compilers typically try to optimise execution speed by reordering instructions. Usually this feature can be disabled over a critical region but you must remember to do so!

Failure to do this can result in extremely hard-to-spot intermittent bugs.

---

Context Dependencies Dependants

Max. number:

Max. distance:

Next

Articles on Concepts

About this resource • Application Binary Interface (ABI) • Arrays • Atomicity • Boot • Cache • Cacheability • Caching • Concepts • Containers • Context • Context Switching • Deadlock • Direct Memory Access (DMA) • Environment Variables • Exceptions • File Attributes • Fragmentation • Hypervisor • Interrupts • Operation Ordering • PATH • Pointers • Process Scheduling • Processes • Processor Privilege • Queues • Real Time • Reentrancy • Relocatable Code • Spooling and Buffering • Synchronisation • Thrashing • Threads • Virtual Memory • Virtualisation

Articles on Deadlock

Atomicity • Deadlock • File Locking • Locks • Multi Threading • Multiprocessors • Mutual exclusion • Operation Ordering • Race Conditions • Reentrancy • Semaphores • Starvation • Threads