Atomicity
| On path: IPC | 1: Processes • 2: Interprocess Communication • 3: Shared Memory • 4: Files • 5: Unix Signals • 6: Pipes • 7: Sockets • 8: Synchronisation • 9: Synchronisation Barrier • 10: Atomicity • 11: Mutual exclusion • 12: Signal and Wait |
|---|
| Depends on | Processes • Locks • Concepts |
|---|
Sometimes a set of machine operations have to be coupled so that they happen ‘together’; there is the possibility of failure if they are separated. A simple (but ‘classic’) example is if two independent processes each increment a shared variable:
If operations are able to interleave arbitrarily, sometimes the
second case can happen. This leads to a non-deterministic result,
which is unlikely to be what was intended!
If this is to work reliably, some means of assuring atomicity of (in
this example) the load-increment-store is needed.
Depending upon the particular example and needs, this can be achieved in various ways:
- In a single-processor system, preventing thread/process switching by disabling interrupts may be sufficient.
(User applications are not allowed to do this directly.)- On most processors system call will disable interrupts by default.
- At processor level, system call entry/exit needs to change the privilege level of the processor and the program flow (PC) _simultaneously.
- Incrementing a semaphore: a variable in memory needs to be read, modified and rewritten without interference. As computer memory can only perform one operation at once, the ‘read-modify-write’ must be sequenced in time. However whilst this is in progress it is important that no other operations interfere.
- Peripheral device modification. Example: an output device (a printer, for example) may have a status indicator to say if it is busy or not. A process may be waiting until it is not busy so it can output something. It is important that no other process ‘jumps in’ between perceiving the device is ready and busying it with the new output.
- In a database, multiple different fields may need to be changed simultaneously, on an all-or-nothing basis.
(This is not a typical O.S. example but illustrates the same principle, applied elsewhere.)
There are plenty more examples; all these rely on achieving atomicity of operations in some way.
Sometimes it is possible for a processor to achieve atomicity with a single instruction; such is the case with system call and return.
Sometimes the ‘atom’ has to be an instruction sequence; this is often the case when dealing with hardware devices and complex data structures. Safety can be guaranteed by ensuring only a single thread performs the interaction but that is not always trivial in a multi-tasking system. For example, in the case of a device output it might be possible for a processor to context switch during the sensitive sequence.
Context switching may be prevented by disabling interrupts during the sensitive code; this works on a single processor, but will not prevent interference in a multicore machine if another processor can also run that code (simultaneously). Mutual exclusion may be needed to ensure that at most one thread on one code is in a particular critical section.
In the general sense, there needs to be some form of lock which prevents a thread entering a critical section when it would be dangerous.
| Also refer to: | Operating System Concepts, 10th Edition: Chapter 6-7, pages 257-316 |
|---|
