Locks
U05730dg [
PHRhYmxlIGNsYXNzPSJ0d3BvcHVwIj48dHI+PHRkIGNsYXNzPSJ0d3BvcHVwLWVudHJ5dGl0bGUiPkdyb3Vwczo8L3RkPjx0ZD51c2VyPGJyIC8+PC90ZD48L3RyPjwvdGFibGU+] (talk | contribs) (→A couple of examples of structural locks)| Depends on | Deadlock |
|---|
A processor may go quite quickly but it only does one thing at once. You may think of this as a statement or a machine instruction; in practice it can be of even finer granularity than this.
Sometimes, to be correct, it is important to do two or more things indivisibly. An example – relevant to operating systems – is the entry/exit of system calls which must change the execution point in memory and the privilege level simultaneously. This is provided for by specific machine instructions.
Sometimes it is possible to order the operations safely. However in other instances this becomes necessary in the software.
The basic locking structure looks something like:
...
tum-te-tum;
...
acquire_lock();
<critical section>
release_lock();
...
tum-te-tum;
...
Of course there is no guarantee that the lock will be available immediately – thus acquire_lock(); may have to wait. There are two options:
- Busy-wait (a.k.a. “spinlock”): if the lock reads back unavailable, go back and read it again in the hope that it has been released in the meantime.
N.B. this is a poor strategy in a uniprocessor system (because…?)! - Block on the lock and context switch.
The former strategy is often best in a multiprocessor environment if it is known the critical section is short (quick) because context switching – even just between threads – may waste more time than simply waiting. In other circumstances a long wait (hopefully not a permanent wait!) can ensue.
Aside: the lock-token mechanism protecting a critical section is not unique to computing. Click here for an illustration.
(It makes a nice change of subject for a moment.)
A couple of examples of structural locks
- A system call to claim some resource, such as obtaining some (more) memory: it is important that the structure holding the list of free areas is modified by one process at once.
- When it comes to writing to a file, usually only a single process should be allowed to do this over any given period.
Implementation
There are different ways to implement locks. A simple mechanism if the control flow is deterministic can be implemented where one thread sets up permission for its successor when it has finished its current access. Often, though, the access pattern is unpredictable and some other mechanism is required. Some typical examples are:
- Mutex: a one-at-a-time permission mechanism
- Semaphore: an extension to allow several threads into a critical region, but still control the maximum number.
Locking machine instructions
Consider a processor which can increment a byte in memory with a single instruction; for example x86 processors can do this. The processor cannot context switch or be interrupted in the middle of an instruction so this makes the operation almost atomic.
The “almost” is because the processor has to read the byte, modify it internally, then write it back. If another processor has access to the same memory it could interfere with this.
Processors designed to facilitate multi-processor operation typically allow such operations to be made atomic; in the x86 example it is possible to lock the operation so the memory is forbidden to others between the read and the write. Such operations are the basis of many mutual exclusion mechanisms.
Such instructions may be needed to implement a more complex lock in software.
Avoiding locks
Any lock comes with some implementation cost – especially if it can cause a wait – and some risk of deadlock (if misused). There is therefore considerable interest (and research) in lock-free algorithms.
Another subject of interest is to use transactions in programming. A high-level programming example serves as a good illustration:
Think of an airline booking system; it is typically processing many concurrent requests. One mechanism would be to lock the (entire) database every time a customer came to look at availability etc. How efficient would that be? Instead, bookings are serviced as transactions. An enquiry returns a copy of the relevant data at that moment and notes this. If, later, a booking request comes back then it may refuse this if the data supplied is now out of date, otherwise it goes ahead. The customer is informed of a failure and must start again; however failures don’t happen very often so it usually works efficiently. Notice that many enquiries can be processed in parallel without harm unless two people want the same seat at almost the same moment. There is no locking to slow down processing when someone is ‘only browsing’. (Notice the read-modify-write again, there.)
The advantages of such a scheme have now been transferred to processors – this is more important in these days of multi-processors – and the preferred scheme for protecting critical sections/data now tends to use such an approach at machine level. … but this is probably too much detail here!
| Also refer to: | Operating System Concepts, 10th Edition: Chapter 13.1.2, pages 534-536 |
|---|
