CS 431 -- Operating Systems
Dr. Tim McGuire
Sam Houston State University
Problems with concurrent execution
- Concurrent processes (or threads) often need to share data (maintained either in shared memory or files) and resources
- If there is no controlled access to shared data, some processes will obtain an inconsistent view of this data
- The action performed by concurrent processes will then depend on the order in which their execution is interleaved
- Process P1 and P2 are running this same procedure and have access to the same variable "a"
- Processes can be interrupted anywhere
- If P1 is first interrupted after user input and P2 executes entirely
- Then the character echoed by P1 will be the one read by P2 !!
- Situations like this where processes access the same data concurrently and the outcome of execution depends on the particular order in which the access takes place is called a race condition
- How must the processes coordinate (or synchronize) in order to guard against race conditions?
- When a process executes code that manipulates shared data (or resource), we say that the process is in its criticalsection (CS) (for that shared data)
- The execution of critical sections must be mutually exclusive: at any time, only one process is allowed to execute in its critical section (even with multiple CPUs)
- Then each process must request permission to enter its critical section (CS)
- The section of code implementing this request is called the entry section
- The critical section (CS) might be followed by an exit section
- The remaining code is the remainder section
- The critical section problem is to design a protocol that the processes can use so that their action will not depend on the order in which their execution is interleaved (possibly on many processors)
- Each process executes at nonzero speed but no assumption on the relative speed of n processes
- General structure of a process:
- Many CPUs may be present but memory hardware prevents simultaneous access to the same memory location
- No assumption about order of interleaved execution
- For solutions: we need to specify entry and exit sections
- Mutual Exclusion
- At any time, at most one process can be in its critical section (CS)
- Only processes that are not executing in their RS can participate in the decision of which process will enter next in the CS
- This selection cannot be postponed indefinitely
- Bounded Waiting
- After a process has made a request to enter its CS, there is a bound on the number of times that the other processes are allowed to enter their CS
- otherwise the process will suffer from starvation
- Of course, also no deadlock
- Software solutions
- algorithms whose correctness does not rely on any other assumptions (see framework)
- Hardware solutions
- rely on some special machine instructions
- Operation System solutions
- provide some functions and data structures to the programmer
- We consider first the case of 2 processes
- Algorithm 1 and 2 are incorrect
- Algorithm 3 is correct (Petersons algorithm)
- Then we generalize to n processes
- We start with 2 processes: P0 and P1
- When presenting process Pi, Pj always denotes the other process (i != j)
- The shared variable turn is initialized (to 0 or 1) before executing any Pi
- Pis critical section is executed iff turn = i
- Pi is busy waiting if Pj is in CS: mutual exclusion is satisfied
- Progress requirement is not satisfied since it requires strict alternation of CSs
- If a process requires its CS more often then the other, it cannot get it.
- Keep one bool variable for each process: flag and flag
- Pi signals that it is ready to enter its CS by: flag[i]=true
- Mutual Exclusion is satisfied but not the progress requirement
- If we have the sequence:
- T0: flag=true
- T1: flag=true
- Both process will wait forever to enter their CS: we have a deadlock
- Initialization: flag=flag=false
- Willingness to enter CS specified by flag[i] = true
- If both processes attempt to enter their CS simultaneously, only one turn value will last
- Exit section: specifies that Pi is unwilling to enter CS
turn = 0 or 1
- Mutual exclusion is preserved since:
- P0 and P1 are both in CS only if flag = flag = true and only if turn = i for each Pi (impossible)
- We now prove that the progress and bounded waiting requirements are satisfied:
- Pi cannot enter CS only if stuck in while() with condition flag[ j] = true and turn = j.
- If Pj is not ready to enter CS then flag[ j] = false and Pi can then enter its CS
- If Pj has set flag[ j]=true and is in its while(), then either turn=i or turn=j
- If turn=i, then Pi enters CS. If turn=j then Pj enters CS but will then reset flag[ j]=false on exit: allowing Pi to enter CS
- but if Pj has time to reset flag[ j]=true, it must also set turn=i
- since Pi does not change value of turn while stuck in while(), Pi will enter CS after at most one CS entry by Pj (bounded waiting)
- If all 3 criteria (ME, progress, bounded waiting) are satisfied, then a valid solution will provide robustness against failure of a process in its remainder section (RS)
- since failure in RS is just like having an infinitely long RS
- However, no valid solution can provide robustness against a process failing in its critical section (CS)
- A process Pi that fails in its CS does not signal that fact to other processes: for them Pi is still in its CS
- Before entering their CS, each Pi receives a number. Holder of smallest number enter CS (like in bakeries, ice-cream stores...)
- When Pi and Pj receives same number:
- if i<j then Pi is served first, else Pj is served first
- Pi resets its number to 0 in the exit section
- (a,b) < (c,d) if a < c or if a = c and b < d
- max(a0,...ak) is a number b such that
- Shared data:
- choosing: array[0..n-1] of boolean;
- number: array[0..n-1] of integer;
- Correctness relies on the following fact:
- If Pi is in CS and Pk has already chosen its number[k]!= 0, then (number[i],i) < (number[k],k)
- but the proof is somewhat tricky...
- Processes that are requesting to enter in their critical section are busy waiting (consuming processor time needlessly)
- If Critical Sections are long, it would be more efficient to block processes that are waiting...
- On a uniprocessor: mutual exclusion is preserved but efficiency of execution is degraded: while in CS, we cannot interleave execution with other processes that are in RS
- On a multiprocessor: mutual exclusion is not preserved
- CS is now atomic but not mutually exclusive
- Generally not an acceptable solution
- Normally, access to a memory location excludes other access to that same location
- Extension: designers have proposed machines instructions that perform 2 actions atomically (indivisible) on the same memory location (ex: reading and writing)
- The execution of such an instruction is also mutually exclusive (even with multiple CPUs)
- They can be used to provide mutual exclusion but need to be complemented by other mechanisms to satisfy the other 2 requirements of the CS problem (and avoid starvation and deadlock)
- A C++ description of test-and-set: (this instruction is atomic, that is indivisible)
- An algorithm that uses test-and-set for Mutual Exclusion:
- Shared variable b is initialized to 0
- Only the first Pi that sets b enters CS
- Mutual exclusion is preserved: if Pi enter CS, the other Pj are busy waiting
- Problem: still using busy waiting
- When Pi exit CS, the selection of the Pj who will enter CS is arbitrary: no bounded waiting. Hence starvation is possible
- Processors (ex: Pentium) often provide an atomic xchg(a,b) instruction that swaps the content of a and b.
- But xchg(a,b) suffers from the same drawbacks as test-and-set
- Shared variable b is initialized to 0
- Each Pi has a local variable k
- The only Pi that can enter CS is the one who finds b=0
- This Pi excludes all the other Pj by setting b to 1
- Synchronization tool (provided by the OS) that do not require busy waiting
- A semaphore S is an integer variable that, apart from initialization, can only be accessed through 2 atomic and mutually exclusive operations:
- To avoid busy waiting: when a process has to wait, it will be put in a blocked queue of processes waiting for the same event
- Hence, in fact, a semaphore is a record (structure):
- When a process must wait for a semaphore S, it is blocked and put on the semaphores queue
- The signal operation removes (acc. to a fair policy like FIFO) one process from the queue and puts it in the list of ready processes
- S.count must be initialized to a nonnegative value (depending on application)
- When S.count >=0: the number of processes that can execute wait(S) without being blocked = S.count
- When S.count<0: the number of processes waiting on S is = |S.count|
- Atomicity and mutual exclusion: no 2 process can be in wait(S) and signal(S) (on the same S) at the same time (even with multiple CPUs)
- Hence the blocks of code defining wait(S) and signal(S) are, in fact, critical sections
- The critical sections defined by wait(S) and signal(S) are very short: typically 10 instructions
- uniprocessor: disable interrupts during these operations (i.e.: for a very short period). This does not work on a multiprocessor machine.
- multiprocessor: use previous software or hardware schemes. The amount of busy waiting should be small.
- For n processes
- Initialize S.count to 1
- Then only 1 process is allowed into CS (mutual exclusion)
- To allow k processes into CS, we initialize S.count to k
- We have 2 processes: P1 and P2
- Statement S1 in P1 needs to be performed before statement S2 in P2
- Then define a semaphore "synch"
- Initialize synch to 0
- Proper synchronization is achieved by having in P1:
- And having in P2:
- A producer process produces information that is consumed by a consumer process
- Ex1: a print program produces characters that are consumed by a printer
- Ex2: an assembler produces object modules that are consumed by a loader
- We need a buffer to hold items that are produced and eventually consumed
- A common paradigm for cooperating processes
- We assume first an unbounded buffer consisting of a linear array of elements
- in points to the next item to be produced
- out points to the next item to be consumed
- We need a semaphore S to perform mutual exclusion on the buffer: only 1 process at a time can access the buffer
- We need another semaphore N to synchronize producer and consumer on the number N (= in - out) of items in the buffer
- an item can be consumed only after it has been created
- The producer is free to add an item into the buffer at any time: it performs wait(S) before appending and signal(S) afterwards to prevent customer access
- It also performs signal(N) after each append to increment N
- The consumer must first do wait(N) to see if there is an item to consume and use wait(S)/signal(S) to access the buffer
P/C: unbounded buffer
- Putting signal(N) inside the CS of the producer (instead of outside) has no effect since the consumer must always wait for both semaphores before proceeding
- The consumer must perform wait(N) before wait(S), otherwise deadlock occurs if consumer enter CS while the buffer is empty
- Using semaphores is a difficult art...
- can consume only when number N of (consumable) items is at least 1 (now: N!=in-out)
- can produce only when number E of empty spaces is at least 1
- As before:
- we need a semaphore S to have mutual exclusion on buffer access
- we need a semaphore N to synchronize producer and consumer on the number of consumable items
- In addition:
- we need a semaphore E to synchronize producer and consumer on the number of empty spaces
The Dining Philosophers Problem
- 5 philosophers who only eat and think
- each need to use 2 forks for eating
- we have only 5 forks
- A classical synchron. problem
- Illustrates the difficulty of allocating resources among process without deadlock and starvation
- Each philosopher is a process
- One semaphore per fork:
- fork: array[0..4] of semaphores
- Initialization: fork[i].count:=1 for i:=0..4
- A first attempt:
- Deadlock if each philosopher start by picking his left fork!
- A solution: admit only 4 philosophers at a time that tries to eat
- Then 1 philosopher can always eat when the other 3 are holding 1 fork
- Hence, we can use another semaphore T that would limit at 4 the numb. of philosophers "sitting at the table"
- Initialize: T.count:=4
- The semaphores we have studied are called counting (or integer) semaphores
- We have also binary semaphores
- similar to counting semaphores except that "count" is Boolean valued
- counting semaphores can be implemented by binary semaphores...
- generally more difficult to use than counting semaphores (e.g.: they cannot be initialized to an integer k > 1)
- semaphores provide a powerful tool for enforcing mutual exclusion and coordinate processes
- But wait(S) and signal(S) are scattered among several processes. Hence, difficult to understand their effects
- Usage must be correct in all the processes
- One bad (or malicious) process can fail the entire collection of processes
- Are high-level language constructs that provide equivalent functionality to that of semaphores but are easier to control
- Found in many concurrent programming languages
- Concurrent Pascal, Modula-3, uC++, Java...
- Can be implemented by semaphores...
- Is a software module containing:
- one or more procedures
- an initialization sequence
- local data variables
- local variables accessible only by monitors procedures
- a process enters the monitor by invoking one of its procedures
- only one process can be in the monitor at any one time
- The monitor ensures mutual exclusion: no need to program this constraint explicitly
- Hence, shared data are protected by placing them in the monitor
- The monitor locks the shared data on process entry
- Process synchronization is done by the programmer by using condition variables that represent conditions a process may need to wait for before executing in the monitor
- are local to the monitor (accessible only within the monitor)
- can be access and changed only by two functions:
- cwait(a): blocks execution of the calling process on condition (variable) a
- the process can resume execution only if another process executes csignal(a)
- csignal(a): resume execution of some process blocked on condition (variable) a.
- If several such process exists: choose any one
- If no such process exists: do nothing
- Awaiting processes are either in the entrance queue or in a condition queue
- A process puts itself into condition queue cn by issuing cwait(cn)
- csignal(cn) brings into the monitor 1 process in condition cn queue
- Hence csignal(cn) blocks the calling process and puts it in the urgent queue (unless csignal is the last operation of the monitor procedure)
- Two types of processes:
- Synchronization is now confined within the monitor
- append(.) and take(.) are procedures within the monitor: are the only means by which P/C can access the buffer
- If these procedures are correct, synchronization will be correct for all participating processes
- Monitor needs to hold the buffer:
- buffer: array[0..k-1] of items;
- needs two condition variables:
- notfull: csignal(notfull) indicates that the buffer is not full
- notempty: csignal(notempty) indicates that the buffer is not empty
- needs buffer pointers and counts:
- nextin: points to next item to be appended
- nextout: points to next item to be taken
- count: holds the number of items in buffer
- Is a general method used for interprocess communication (IPC)
- for processes inside the same computer
- for processes in a distributed system
- Yet another mean to provide process synchronization and mutual exclusion
- We have at least two primitives:
- send(destination, message)
- received(source, message)
- In both cases, the process may or may not be blocked
- For the sender: it is more natural not to be blocked after issuing send(.,.)
- can send several messages to multiple dest.
- but sender usually expect acknowledgment of message receipt (in case receiver fails)
- For the receiver: it is more natural to be blocked after issuing receive(.,.)
- the receiver usually needs the info before proceeding
- but could be blocked indefinitely if sender process fails before send(.,.)
- Hence other possibilities are sometimes offered
- Ex: blocking send, blocking receive:
- both are blocked until the message is received
- occurs when the communication link is unbuffered (no message queue)
- provides tight synchronization (rendezvous)
- direct addressing:
- when a specific process identifier is used for source/destination
- but it might be impossible to specify the source ahead of time (ex: a print server)
- indirect addressing (more convenient):
- messages are sent to a shared mailbox which consists of a queue of messages
- senders place messages in the mailbox, receivers pick them up
- A mailbox can be private to one sender/receiver pair
- The same mailbox can be shared among several senders and receivers
- the OS may then allow the use of message types (for selection)
- Port: is a mailbox associated with one receiver and multiple senders
- used for client/server applications: the receiver is the server
- A port is usually own and created by the receiving process
- The port is destroyed when the receiver terminates
- The OS creates a mailbox on behalf of a process (which becomes the owner)
- The mailbox is destroyed at the owners request or when the owner terminates
- Consists of header and body of message
- In Unix: no ID, only message type
- control info:
- what to do if run out of buffer space
- sequence numbers
- Queuing discipline: usually FIFO but can also include priorities
- create a mailbox mutex shared by n processes
- send() is non blocking
- receive() blocks when mutex is empty
- Initialization: send(mutex, "go");
- The first Pi who executes receive() will enter CS. Others will be blocked until Pi resends msg.
- We will now make use of messages
- The producer place items (inside messages) in the mailbox mayconsume
- mayconsume acts as our buffer: consumer can consume item when at least one message is present
- Mailbox mayproduce is filled initially with k null messages (k= buffer size)
- The size of mayproduce shrinks with each production and grows with each consumption
- can support multiple producers/consumers
Keeping out of each other's way
February 9, 2015
Let’s start off with some definitions. In this discussion, we will use the terms processes and threads interchangeably. In all cases, we refer to threads of execution and it does not matter whether they are multiple threads of the same process or multiple processes. The underlying assumption is that the processes or threads have access to the same shared regions of memory. This sharing is automatic for threads but is also possible with processes on most operating systems if they explicitly create a shared memory segment.
A set of threads is concurrent if the threads exist at the same time. These threads may be running at the same time in multiprocessing environments or their execution may be interleaved through preemption via the scheduler. The execution of these threads may be interleaved in any order, as long as each thread of execution follows the order dictated by the program.
Threads are asynchronous if they require occasional synchronization and communication among themselves. For the most part, the execution of one thread neither speeds up nor slows down the execution of another.
Threads are independent if they have no reliance on one another. This means that they never communicate and that one thread does not generate any side effects that impact another thread.
Synchronous threads are threads that are kept synchronized with each other such that the order of execution among them is guaranteed. One thread may keep another thread from making progress just to ensure that their progress is synchronized.
Parallel threads run at the same time on separate processors.
In this section we examine the reasons for thread synchronization and how it can be realized.
The race is on!
Suppose two or more asynchronous processes or threads access to a common, shared piece of data. Any process can be preempted at any time. What problems can arise?
Let’s look at an example where you have a system-wide global variable called characters that counts all the characters received from all terminal devices connected to a computer. Suppose also that each process that reads characters uses the following code to count them:
and that the compiler generates the following machine instructions for this code:
As a concrete example, the x86–64 code generated by the gcc compiler for that one line of code is:
Where is a CPU register and is used to create a position-independent reference to the memory location of the integer . When the code is loaded linked, gets replaced by a byte offset from the current instruction. is the 64-bit instruction pointer and the operand is a RIP-relative address, an offset value.
Let’s assume that characters is 137. Process A executes the first two instructions and is then preempted by process B. Process B now reads characters, which is still 137 because A did not get around to writing its result. Process B adds 1 and writes out the result: 138. Some time later, process A gets a chance to run again. The operating system restores A’s state (CPU registers, program counter, stack pointer, and flags) from the point where it was preempted and allows it to continue execution. It already added 1 to 138 and and has the result in a register, so all it does is write the contents of register, 138, out to memory. We now lost count of a character!
Let us suppose that your current checking account balance is $1,000. You withdraw $500 from an ATM machine while, unbeknownst to you, a direct deposit for $5,000 was coming in. We have these two concurrent actions:
|1. Read account balance||1. Read account balance|
|2. Subtract 500.00||2. Add 5,000.00|
|3. Write account balance||3. Write account balance|
Consider the possible outcomes:
- The proper outcome, of course, is that your checking account will have $5,500 after both operations are finished. Either the Deposit sequence of operations takes place first or the Withdrawal sequence does. Either way, the answer is the same.
- Suppose that the system just completed step 1 of the Withdrawal operation. At that time, the thread gets preempted and the Deposit thread gets to run. It goes through its steps: reads the account balance ($1,000), adds $5000 ($6,000), and writes the result ($6,000). Then the Withdrawal thread is allowed to resume running. It already completed step 1, where it read $1,000 (not knowing that the value has been modified!), so it resumes operation with step 2 and subtracts $500 from $1,000, storing $500 in step 3. Your account balance is now $500. The actions of Deposit have effectively vanished.
- Now suppose that the operations are now scheduled in a slightly different order. The Deposit thread runs first, reads the account balance ($1,000) and adds $5,000 (giving $6,000). At this time, the thread is preempted and the Withdrawal thread is scheduled to run. In step 1, it reads the balance ($1,000, since the new balance was not yet written), subtracts $500, and stores the result, $500. When the Deposit thread is now given a chance to run, all it has left to do is step 3: store its result, $6,000. The effects of the Withdrawal thread have been obliterated.
As a final example, let’s consider a linked list. Multiple threads are running concurrently and add items to the list by adding a new node to the head of the list:
Currently, we have two items on the list; see Figure 1.
Thread A now needs to add a new element to the list: Item 3. At more or less the same time, thread B also needs to add a new element to the list, Item 4. Thread A is currently running and executes the first three instructions. The head of the list has not yet been set to point to the new element. Figure 2 shows how things look at this point in time:
All is well so far. Now the operating system preempts thread A and gives thread B a chance to run. Thread B executes the same instructions and runs the entire sequence 1–4. It allocates a new list cell, sets its next pointer to the current head of the list, and then changes the global list head to point to this new cell. Fgure 3 shows what we have now.
Thread B may go on to do other things and is eventually preempted so that thread A can run. Thread A continues where it left off, at step 4. It sets the global list head to point to the new cell that it added to the list. Figure 4 shows us how the list looks now. Item 4 is effectively gone from the list since head does not point to it.
What happened is that thread A was oblivious to the fact that thread B snuck in and added a list element. Thread A overwrote the head of the list without taking into account the fact that thread B modified it.
The above examples illustrate how bad things can happen when multiple threads or processes access shared data. These bugs result from race conditions. A race condition is a bug where the outcome of concurrent threads is dependent on the precise sequence of the execution of one relative to the other. Thread (or process) synchronization deals with developing techniques to avoid race conditions.
We’ll use threads and processes almost interchangeably in our discussion and the principles apply equally to both. Processes or threads on different processes, since they generally do not share the same memory with other processes, have to rely on interprocess communication mechanisms (IPC), such as explicitly setting up regions of shared memory, to share data and communicate. Threads within the same process, of course, share the same address space and hence the same static data and heap (all dynamically allocated memory that is not stack-based). This increases the likelihood that race conditions may arise.
The above problems can be resolved by not allowing other threads or processes to run while a process that is manipulating shared data is active. This is a drastic approach and not a good one. First, it’s not particularly fair. Because one process is running, others won’t get a chance to run. Secondly, it is overbearing: it is possible, even likely, that this or other processes have a lot more useful work to do outside of touching shared data. Thirdly, it may not even be feasible. It is possible that the processes require communication with each other to accomplish their result.
What we can do instead is to identify the regions in a program that access shared memory (or other shared resources) and may cause race conditions to arise. These regions are called critical sections. A critical section is a sequence of code that reads shared data, uses and modifies it, and then writes it back out.
To avoid race conditions, only one thread should be allowed to access a shared resource at a time. Enforcing this condition is known as mutual exclusion. If a thread is in its critical section, any other thread that wants to access the shared resource must wait (be blocked).
When we introduce mutual exclusion into the system, we have to be careful that a thread will not be perpetually blocked because of a circular dependency. An example of this is if one thread in a critical section R but also needs to enter critical section S. However, another thread is in critical section S and needs to access critical section R. This is a circular dependency and the condition is known as deadlock. The two threads are deadlocked, each waiting for the other to free up a resource (i.e., let go of a critical section).
A related problem is livelock. Here, there is no strict circular dependency but threads may be communicating and constantly changing state yet not making any progress. In some ways, this is more insidious than deadlock because it is more difficult to detect as no thread is in a waiting state.
Starvation is the case where the scheduler never gives a thread a chance to run. One reason that a scheduler may do this is because the thread’s priority is lower than that of other threads that are ready to run. Never getting a chance to run is bad. It’s even worse when the thread is in a critical section since, by not running, it will not get a chance to release the critical section.
The logical approach for a programmer to deal with critical section is via locks: you acquire a lock before you enter a critical section and then release it when you exit the critical section. This ensures that only one thread can be in the critical section at the same time. Here is a representation of the withdrawal/deposit scenario with locks around the critical sections. We define a critical section that we lock with a lock variable that we call transfer_lock. To enter it, we call an acquire function. If any thread is already in the critical section, then we block until that thread releases it via release. This ensures that only one thread at a time can be in the code following acquire.
|1. Acquire(transfer_lock)||1. Acquire(transfer_lock)|
|2. Read account balance||2. Read account balance|
|3. Subtract 500.00||3. Add 5000.00|
|4. Write account balance||4. Write account balance|
|5. Release(transfer_lock)||5. Release(transfer_lock)|
A solution for managing critical sections requires the following conditions to hold.
- Mutual exclusion. No threads may be inside the same critical sections simultaneously.
- Progress. If no thread is executing in its critical section and some thread or threads want to enter the critical section, the selection of a thread that can do so cannot be delayed indefinitely. Specifically, if only one thread wants to enter, it should be permitted to do so. If more than one wants to enter, only one of them should be allowed to.
- Bounded waiting: No thread should wait forever to enter a critical section.
- No thread running outside its critical section may block others from entering a critical section.
A good solution for managing critical sections should also ensure that
- No assumptions are made on the number of processors. The solution should work even if threads are executing at the same time on different processors.
- No assumptions are made on the number of threads or processes. The solution should not be designed to only support, for example, two threads.
- No assumptions are made on the relative speed of each thread. We cannot assume any knowledge of when or if a thread will request a critical section again. It will be undesirable to have an algorithm where a thread has to wait unnecessarily for another thread.
Achieving mutual exclusion
Let’s examine a few approaches that we may implement to try to achieve mutual exclusion among a number of concurrent threads.
Proposed solution #1: disable interrupts
Have each thread disable all interrupts just before entering its critical section and re-enable them when leaving. This ensures that the operating system will not get a timer interrupt and have its scheduler preempt the thread while it is in the critical section.
This gives the thread too much control over the system. Moreover, it is something that can only be done if the thread is executing in kernel mode; user processes are disallowed from disabling interrupts. Consider what happens if the logic in the critical section is incorrect and interrupts are never enabled? The operating system will not get its timer interrupt and will not be able to preempt the thread and let any other process run. The system will have to be rebooted. Even if the thread does re-enable interrupts after the critical section, what happens if the critical section itself has a dependency on some other interrupt, thread, or system call? For example, the logic in the critical section may need to read data from a file on a disk but the operating system will not get the disk interrupt that tells it that data is ready. Finally, if you’re on a multiprocessor system, disabling interrupts will only disable them on one processor, so the technique does even work on these systems.
This is a simple approach and, on a uniprocessor system, is guaranteed to work. It is very tempting to use within the kernel for code that modifies shared data.
In short, this is clearly not a good idea for the general welfare of the operating environment. However, because of its extreme simplicity, this was a common approach to mutual exclusion in operating system kernels, at least before multiprocessors spoiled the fun.
Proposed solution #2: test & set locks
We can keep a shared lock variable and set it to 1 if a process is in a critical section and 0 otherwise. When a process wants to enter its critical section, it first reads the lock. If the lock variable is 0, the process sets the lock to 1 and executes its critical section. If the lock is 1, the process waits until it becomes 0.
Here’s a sample snippet of code that uses a global variable called locked:
The really big problem with this approach is that a race condition exists for reading and setting the lock. Here’s why. After the while loop sees that locked is zero, the thread could be preempted. Another thread that is waiting for the critical section will also see that locked is zero and will also exit its while loop and enter the critical section. When the first thread is given a chance to continue running, it is already out of the while loop and simply sets locked = 1, unaware that somebody else already entered the critical section and set locked to 1.
This solution is extremely simple to understand, implement, and trace. Unfortunately, it is a buggy, and hence invalid, solution. It’s been used for operations such as locking a mailbox file to prevent another mail reading program from modifying the file. The insidious nature of race conditions is that the bugs may not present themselves even after a lot of intensive testing, so buggy solutions might appear to be flawless.
Proposed solution #3: lockstep synchronization
This attempt at a solution involves keeping a shared variable (turn) that tells you which thread’s turn it is to execute a critical section. Each thread that may want to access the critical section is given a unique number and the turn variable cycles through these numbers. In the simple case of only two threads, we can use the numbers 0 and 1. For instance, thread 0 gets to run its critical section when turn is 0 and thread 1 gets to run its critical section when turn is 1.
This solution works in avoiding race conditions but has a major disadvantage: it forces strict alternation between the threads. As soon as thread 0 finishes its critical section, it sets turn to 1, forcing the next entry into the critical section has to be by thread 1. If thread 0 happens to be faster than thread 1 or just needs to access the critical section more frequently, this scheme forces thread 0 to slow down (by waiting for its turn) to the same rate of critical section access as thread 1. It turns asynchronous threads into synchronous threads.
There have been a number of pure software solutions proposed to handle reliable entry into critical sections. We’ll provide a brief overview of one of them, known as Peterson’s algorithm, for the simple case of a two-thread system.
The algorithm relies on a shared array (one element per thread) and a shared variable. The array, wants, identifies which threads want to enter a critical section. The variable, turn, indicates whose turn it is. Everything is initialized to zero initially.
A thread calls a function, acquire, before running its critical section. This function sets an array element in the shared array (wants) that corresponds to its position (e.g., thread 0 sets element 0) to show that the thread wants to enter the critical section. It sets the shared variable (turn) to the thread number. Then it spins in a busy wait loop if it’s the thread’s turn but the other thread wants the critical section. Upon completing the critical section, the thread calls release.
Let’s see how this works. Suppose that Thread 0 is calling acquire and Thread 1 is not. Here’s what happens in acquire when Thread 0 calls it:
The while loop tells us that thread 1 does not want the critical section (wants is 0), so we can continue into the critical section. Now suppose that Thread 1 wants to enter the critical section and calls acquire:
Thread 1 is now kept waiting because Thread 0 set its wants entry to 1 (true). When Thread 0 is done with its critical section, it sets wants to 0 (false) and Thread 1 will jump out of the while loop.
Now let’s see if race conditions can develop by examining the case when both threads try to enter the critical section at the same time. It doesn’t matter which thread gets to set wants first because, even though it’s a shared array, only one thread ever sets a particular entry; there is no contention to write to the same location. The variable turn, on the other hand, can be set by either thread. Suppose Thread 0 gets to set turn to its thread number (0) first.
|Thread 0||Thread 1|
Now if Thread 0 gets to set turn first, the following happens:
|Thread 0||Thread 1|
We see that the algorithm works by disallowing the last thread that set turn to proceed unless nobody else wants to enter the critical section.
The disadvantage with this and other algorithmic techniques is that they can be tricky to implement correctly, especially when there are more than two threads involved. The example presented only works for two threads. With higher-level languages such as C or C++, you need to rely on the volatile data type to ensure that reads and writes actually reach main memory and that the compiler does not optimize the code to use registers or delay writing to memory.
Help from the processor
Most processors have specific instructions that aid in programming critical sections. The key to these instructions is that the operations that they perform are atomic, meaning that they are indivisible. A system interrupt cannot come in and preempt the instruction after the first part of its operations finished, which was the problem with a solution such as a our pure software test & set solution.
Different processors offer different instructions that help with critical sections. We will look at three variations of these atomic instructions:
Test and set
A test-and-set instruction reads the contents of a memory word into a register, writes a value of 1 into that location, and returns the previous contents of the memory. The crucial item here is that this operation is guaranteed to be atomic: indivisible and non-interruptible. This is what it does (indivisibly):
Test-and-set always sets a lock but it lets you know if it was already set at the time that you executed the instruction. If the lock was already set when you ran test-and-set then somebody simply got the lock before you did; you don’t have it. If the lock was not set when you ran the instruction (i.e., the instruction returned a zero), then it is now set and you have the lock. Managing a critical section can look like this:
Compare and swap
The compare-and-swap instruction compares the value of a memory location with an “old” value that is given to it. If the two values match then the “new” value is written into that memory location. This is the sequence of operations:
Think of compare_and_swap(int *x, int A, int B) as having the function of set x to B only if x is currently set to A and return the value that x really contained.
Remember our attempt at a software-only test-and-set lock? We’d loop while a memory location, locked, was not zero and then set it to one? The problem was that we had a race condition between those two operations: somebody else could come in and set the value of locked to 1 after we tested it. With compare-and-swap, we’re telling it the value we last read from that memory location and what we’d like to set it to provided that somebody did not change the contents since we last read it. If they did, our new value will not be set since our idea of the old value was not correct. The return value tells us what the contents of the memory location were when the compare-and-swap instruction was executed. An example of how we control entry to and exit from a critical section using compare-and-swap is:
Here, we spin on compare_and_swap and keep trying to set locked to 1 (last argument) if lock’s current value is 0. Let’s consider a few cases:
If nobody has the region locked, then locked is 0. We execute compare_and_swap and tell it to set locked to 1 if the current value is 0. The instruction does this and returns the old value (0) to us so we break out of the while loop.
If somebody has the region locked, then locked is 1. We execute compare_and_swap and tell it to set locked to 1 if the old value was 0. But the old (current) value is 1, so compare_and_swap does not set it (it wouldn’t matter) and returns the value that was already in locked, 1. Hence, we stay in the loop.
Let’s consider the potential race condition when two threads try to grab a lock at the same time. Thread 1 gets to run compare_and_swap first, so the instruction sets locked to 1 and returns the previous value of 0. When Thread 2 runs the instruction, locked is already set to 1 so the instruction returns 1 to the thread, causing it to keep looping.
In summary, we’re telling the compare_and_swap instruction to set the contents of locked to 1 only iflocked is still set to 0. If another thread came in and set the value of locked to non-zero, then the instruction will see that the contents do not match 0 (old) and therefore will not set the contents to new.
Fetch and increment
The final atomic instruction that we’ll look at is fetch-and-increment. This instruction simply increments a memory location but returns the previous value of that memory location. This allows you to “take a ticket” and then wait until it’s your turn to use the critical section. This technique is known as a ticket lock. Think of fetch-and-increment as one of those take-a-number machines at the deli counter in a supermarket:
The return value, last_value corresponds to the number on your ticket while the machine is now ready to generate the next higher number. To implement a critical section, we grab a ticket (myturn) and wait our turn. Our turn arrives when the turn-o-matic machine shows our number and the deli clerk calls it (turn == myturn):
The variable ticket represents the ticket number in the machine. The variable myturn represents your ticket number and turn represents the number that is currently being served. Each time somebody takes a ticket via fetch_and_increment, the value of ticket is incremented. Each time somebody is done with their critical section and is ready for the next thread to get served, they increment turn.
Spin locks and priority inversion
One problem with any of the above solutions is that we end up with code that sits in a while loop (spins), waiting for conditions to allow it entry into the critical section. This constant checking is called busy waiting or a spinlock. The process is always busy running but it is really just waiting since it is making no process in execution. From a resource utilization point of view, this is not efficient. To an operating system, the thread is in a ready state and gets scheduled to run (use the CPU) even though it will not make any progress. It is a waste of CPU time.
What makes this situation even worse is that it is possible that the process that is currently holding the lock may not even be allowed to run or may be significantly delayed. Suppose we have a priority-based scheduler and a lower-priority process has obtained a lock and is in the critical section. Now suppose that a higher-priority process wants to get access to the critical section and is sitting in a spin lock. As far as the operating system is concerned, that higher-priority process is always ready to run and will be scheduled instead of the process that is in the critical section (the scheduler simply picks the higher priority thread or process). This situation is known as priority inversion. What really needs to happen for the higher priority process to make progress (i.e., to get the lock and get into the critical section) is for the lower priority process to get to run so that it can get out of the critical section and relinquish its lock.
One technique that may be used to avoid priority inversion is to increase the priority of any process in a critical section to the maximum priority level of any of the processes that are waiting for the lock. Once the process releases its lock, its priority goes back to its normal level. This approach is known as priority inheritance. The challenge with implementing this is that you need to ensure that there is some way for the operating system to know about whether a process is in a critical section, looping on a spinlock for that same critical section, or doing something completely unrelated.
Spin locks are a fundamental problem with pure software solutions. Without having a way for a thread to ask the operating system to suspend itself, all that a thread can do to stop itself from making progress is to loop while waiting for some condition to change. Ideally, we’d like to create operating system constructs for mutual exclusion that will let us block the process instead of having it spin.
OS mechanisms for synchronization
All of the above solutions to accessing a critical section have the drawback of busy waiting: if a thread cannot enter its critical section, it sits in a loop waiting until it can do so. This has two problems. First, it wastes CPU time since the thread is always ready to run and the operating system scheduler will schedule it to do so periodically. Secondly, and more seriously, is that cases can arise when a thread that has the lock is not allowed to run. Suppose the operating system uses a thread scheduler that always favors higher-priority threads. If a lower priority thread obtained a lock on a critical section, the higher priority thread can do nothing but loop and wait for the other thread to give up the lock. However, because this higher priority thread is always ready to run, the lower priority thread never gets a chance to run and give up its critical section. This situation is known as priority inversion.
It would greatly help us if we can get some support from the operating system to put a thread to sleep (block it) when it cannot enter a critical section and then wake it up when it is finally allowed access to the critical section.
We will now look at a few mechanisms that operating systems give us.
In 1963, Edsger W. Dijkstra created a special variable type called a semaphore that allows one to manage access to critical sections EWD123. A semaphore is an integer variable with two associated operations: down (also known as p or wait) and up (known as v or signal).
The following actions take place for up and down, all indivisible.
The indivisibility of these operations is ensured by the operating system’s implementation of semaphores and may involve lower-level mutual exclusion operations, such as spinlocks. While we discussed spinlocks as a bad thing, they serve a purpose within the kernel for acquiring mutual exclusion locks for small sections of code. We just want to avoid them for potentially long-term operations.
Whenever a thread calls down on a semaphore, the semaphore’s value is decremented and the thread can continue running. The value of a semaphore, however, cannot go below zero. If the value of a semaphore is zero and a thread calls down on that semaphore, the kernel will put that thread to sleep. Specifically, that thread will be in a blocked state and the thread ID will be placed on a list of any other threads that are blocked on that semaphore.
Whenever a thread calls up on a semaphore, the kernel checks to see whether there are any threads in the list of threads that are blocked on that semaphore. If so, one of the threads is moved to the ready state and can continue execution. The value of the semaphore does not change. If there are no threads blocked on the semaphore, the value of that semaphore is simply incremented. The up operation never blocks a thread.
One way to look at semaphores is to think of a semaphore as counting the number of threads that are allowed to be in a section of code at the same time. Each time a thread enters the section, it performs a down, allowing one fewer access (threads that will be allowed entry). When there are no more accesses allowed, any thread requesting access is forced to block. When a thread is done with its section, it performs an up, which allows a waiting thread to enter or, if none are waiting, increments the count of threads that are allowed to enter.
Semaphores are often initialized to 1 and are used by two or more threads to ensure that only one of them can enter a critical section. Such semaphores are known as binary semaphores. Here is an example of accessing a critical section using a binary semaphore:
Let us suppose that there are two processes: a producer that generates items that go into a buffer and a consumer that takes things out of the buffer. The buffer has a maximum capacity of N items. If a producer produces faster than the consumer consumes then it will have to go to sleep until there’s enough room in the buffer. Similarly, if the consumer consumes faster than the producer produces, the consumer will go to sleep until there is something for it to consume. This scenario is formally known as the Bounded-Buffer Problem.
As we saw in our discussion on race conditions, we need to avoid race conditions to properly keep track of the items in the buffer in case we produce and consume something at the same time. To handle this, we’ll use a binary semaphore that we’ll call mutex (for mutual exclusion). We’ll initialize it to 1 so that we can use it to guarantee mutual exclusion whenever we add or remove something from the buffer.
We want the producer to go to sleep when there is no more room in the buffer and for it to wake up again when there is free room in the buffer. To do this, we will create a semaphore called empty and initialize it to N, the number of free slots in the buffer. When we execute down(&empty), the operation will decrement empty and return to the thread until empty is 0 (no more slots). At that point, any successive calls to down(&empty) will cause the producer to go to sleep.
When the consumer consumes something, it will execute up(&empty), which will wake up the producer if it is sleeping on the semaphore and allow it to add one more item to the buffer. If the producer was not sleeping because there there is still room in the buffer, up(&empty) will simply increment empty to indicate that there is one more space in the buffer.
The empty semaphore was used to allow the producer to go to sleep when there was no more room in the buffer and wake up when there were free slots. Now we have to consider the consumer. We want the consumer to go to sleep when the producer has not generated anything for the consumer to consume. To put the consumer to sleep, we will create yet another semaphore called full and have it count the number of items in the buffer. Since there are no items in the buffer initially, we will initialize full to 0. Initially, when the consumer starts running, it will run down(&full), which will put it to sleep. When the producer produces something, it calls up(&full), which will cause the consumer to wake up. If the producer works faster than the consumer, successive calls to up(&full) will cause full to get incremented each time. When the consumer gets to consuming, successive calls to down(&full) will just cause full to get decremented until full reaches 0 (no more items to consume), at which point the consumer will go to sleep again.
Now we will look at a Readers-Writers example. Here, we have a shared data store, such as a database. Multiple processes may try to access it at the same time. We can allow multiple processes to read the data concurrently since reading does not change the value of the data. However, we can allow at most one process at a time to modify the data to ensure that there is no risk of inconsistencies arising from concurrent modifications. Moreover, if a process is modifying the data, there can be no readers reading it until the modifications are complete.
To implement this, we use a semaphore (canwrite) to control mutual exclusion between a writer or a reader. This is a simple binary semaphore that will allow just one process access to the critical section. Used this way, it would only allow one of anything at a time: one writer or one reader. Now we need a hack to allow multiple readers. What we do is to allow other readers access to the critical section by bypassing requesting a lock if we have at least one reader that has the lock and is in the critical section. To keep track of readers, we keep a count (readcount). If there are no readers, the first reader gets a lock. After that point, readcount is 1. When the last reader exits the critical section (readcount goes to 0), that reader releases the lock.
We also use a second semaphore, mutex, to protect the region where we change readcount and then test it.
The point of the mutex semaphore is to make sure that only one thread ever runs the chunk of code that it protects at any time. We have two chunks protected by the mutex semaphore.
The mutex keeps us from having two threads update the value of readcount or check its value at the same time. The if statements in the above chunks simply check if we already have a reader inside the thread. If we do, then we don’t touch the canwrite semaphore.
If we’re the first reader, then we do a down(&canwrite) so that another thread will get blocked if it calls writer() since that function does a down(&canwrite) as well. Alternatively, we may end up blocking if another thread is currently active inside writer(). If a thread calls reader(), then we bypass the down() because readcount > 1. At the end, we check if we were the last reader. If so, then we up() the canwrite semaphore. This will now allow any thread that is blocked in writer() to proceed.
An event counter is a special data type that contains an integer value that can only be incremented. Three operations are defined for event counters:
- read(E): return the current value of event counter E
- advance(E): increment E (this is an atomic operation)
- await(E,v): wait until E has a value greater than or equal to v
Here is an example of the producer-consumer problem implemented with event counters. Both the consumer and producer maintain a sequence number locally. Think of the sequence number as the serial number of each item that the producer produces. From the consumer’s point, think of the sequence number as the serial number of the next item that the consumer will consume.
The event counter in is the number of the latest item that was added to the buffer. The event counter out is the serial number of the latest item that has been removed from the buffer.
The producer needs to ensure that there’s a free slot in the buffer and will wait (sleep) until the difference between the sequence number and out (the last item consumed) is less than the buffer size. The consumer needs to wait (sleep) until there is at least one item in the buffer; that is, in is greater than or equal to the next sequence number that it needs to consume.
The producer’s sequence number mirrors the value of in and the consumer’s sequence number mirrors the value of out. We can simplify the code a bit by getting rid of sequence numbers. The producer needs to ensure that there’s a free slot in the buffer and will wait (sleep) until the difference between in and out is less than the buffer size. The consumer sleeps until there is at least one item ready (in > out). Here is the slightly simplified ode.
Note that there is no mutual exclusion protection around enter_item and remove_item as we had with semaphores. This is because the way the code is written, the consumer waits until the buffer is full and the producer waits until the buffer is empty.
Condition variables (monitors)
Controlling critical sections reliably (without deadlocking) is often difficult and error-prone. A monitor is an attempt to create a higher level synchronization primitive to make it easier to synchronize events. A monitor is a collection of procedures and data with the following characteristics:
- Processes may call the functions in a monitor but may not access the monitor’s internal data structures.
- Only one process may be active in a monitor at any instant. Any other process that tries to access an active monitor will be suspended.
A monitor is a programming construct: part of the programming language rather than the operating system. The compiler has to understand how to compile code to implement monitors (for example, it may implement the monitor constructs using the operating system’s semaphores). Two operations are supported by monitors:
- Blocks until condition_variable is “signaled.” Another thread is allowed to run.
- Wakes up one thread that is waiting on the condition variable. This function is often called notify (e.g., in Java).
A separate condition variable has to exist for each reason that a process might need to wait.
Resource allocation with monitors
Here’s a small example of how a monitor may be used to allow a process to grab exclusive access to some resource and then relinquish it when it’s done:
If these were normal functions, we would have to worry about a race condition developing in get_resource between the time we check in_use and set it (another thread might be switched in at that point and try to get a resource). Because this is a monitor, we are assured that mutual exclusion holds for the entire monitor, so these problems do not arise.
Monitors have the advantage of making parallel programming easier and less error prone than using techniques such as semaphores.
The major drawback of monitors is that they have to be implemented as part of the programming language. The compiler must generate code for them. This gives the compiler the additional burden of having to know what operating system facilities are available to control access to critical sections in concurrent processes. Since few languages have any understanding of concurrency, many languages do not support monitors. Some languages that do support monitors are Java, C#, Visual Basic, Ada, and Concurrent Euclid.
Producer-consumer example with Java
This illustrates a Java example of the producer-consumer problem. The synchronized keyword for the consume_item method ensures that the method is a critical section.
One drawback of monitors, semaphores, and global data structures to control mutual exclusion is that they assume that all concurrent threads or processors have access to common memory and share the same operating system kernel (which is responsible for putting processes to sleep and waking them up). Asynchronous processes do two things: they synchronize (e.g., wait on one another) and they exchange data.
While this is a fine assumption for threads and processes, these solutions don’t work on distributed systems where each system has its own local memory and its own operating system since none of these primitives provide for the exchange of information between machines. Messages don’t have this restriction. They allow us to synchronize processes (by waiting for messages) and exchange data among processes. Moreover, they can work across different threads and processes on the same as well as different machines.
Message passing is a form of interprocess communication that uses two primitives:
- send(destination, message)
- Sends a message to a given destination.
- receive(source, &message)
- Receives a message from a source. This call could block if there is no message.
When we use a network, we should be aware of certain issues:
Networks may be unreliable. What if a message gets lost? We can try to make communications reliable via acknowledgements and retransmissions. A receiver can be asked to send an acknowledgement message when it receives a message. If a sender doesn’t receive the acknowledgement in a certain amount of time, then it will retransmit the message. However, if the acknowledgement gets lost, then the sender will send two messages. We may consider tagging each message with a sequence number and have the operating system keep track of missing, redundant, or out-of-order messages.
Processes and machines need to be named unambiguously. How do you identify a process on a different machine?
We trust our operating system to do the right thing and provide a protection structure to keep our data private when we want it to be private. With a network, things get more complicated. Can you trust other operating systems on the network? How can you ensure that the message you received really came from where you thought it did?
Produced-consumer example with message passing
The producer-consumer example uses a messaging channel as a queue between producer and consumer threads/processes. That on its own would give us no way to control the size of the buffer since the producer could just keep sending more and more messages even if the consumer is slow to consume them. What we use instead is a bi-directional message channel. A producer can add an item only in response to receiving an empty message from the consumer. Each received empty message represents a slot in the buffer. The producer receives one such message whenever it has to add another item to the buffer. If there isn’t an empty message available then the producer blocks on receive and waits until the consumer consumes an item from the buffer and responds with an empty message.
Advantages of messages
The concept of messages is scalable from a single processor environment to a networked system of multiple processors, each with its own memory.
Disadvantages of messages
Even on a single processor system, it is possible that message passing may be slower than other methods due to the overhead of copying the message. Some systems, however, make local message passing efficient.
The example we just looked at assumed that the receiver blocked whenever a message was not ready for it and that the sender could just send a message and not be blocked; the message would get sent out and buffered by the operating system (of the receiving process if we’re going across a network).
A rendezvous is a variant of message passing that uses no message buffering. A sender blocks until a receiver reads the message. If a send is done before a receive, the sending process is blocked until a receive occurs. In an SMP (symmetric multiprocessor) environment, as opposed to a multi-computer environment, the message can be copied directly with no intermediate buffering. If a receive is done first, it blocks until a send occurs.
Advantage of rendezvous
It is easy and efficient to implement.
Disadvantage of rendezvous
It forces the sender and receiver to be tightly synchronized at these send/receive junctures.
Messages and rendezvous require the use of direct addressing, where the sending process must identify the receiving process. The receiving process can either specify the sender or may receive its identification as an incoming parameter from the receive operation. This messaging mechanism makes it easy to support a single sender/single receiver or multiple senders/single receiver models. If we want to support multiple receivers, say multiple processes on multiple computers that all want to grab messages for processing, things get complicated since the sending processes will have to have some way of figuring out which of several recipients should receive a given message.
A mailbox is an intermediate entity that is applied to messaging: a set of FIFO queues two which senders can send messages and from which readers can receive messages. It is an example of indirect addressing since neither the sender nor reader correspond directly with each other. Mailboxes make it easy to support multiple readers since they can all contact the same mailbox and extract items from the queue.
A process sends a message to a mailbox rather than to a specific other process and another process (or processes) reads messages from that mailbox. If the mailbox is full, a sending process is be suspended until a message is removed.
Advantage of mailboxes
They give us the flexibility of having multiple senders and/or receivers. Moreover, they do not require the sender to know how to identify any specific receiver. Senders and receivers just need to coordinate on a mailbox identifier.
Disadvantage of mailboxes
They may incur an extra level of data copying since data has to be first copied to the mailbox queue and then copied to the receiver. In the case of networked system, there is the question of where the mailbox should reside. Since senders and receivers can all be different computers, the mailbox becomes a distinct destination on the network: messages get sent to a mailbox and then retrieved from a mailbox. This act imposes an extra hop over the network for each message.
Whenever we create an environment where threads compete for exclusive access to resources, we run the risk of deadlock.
A deadlock is a condition in a system where a process cannot proceed because it needs to obtain a resource held by another process but it itself is holding a resource that the other process needs. More formally, four conditions have to be met for a deadlock to occur in a system:
- Mutual exclusion: a resource can be held by at most one process.
- Hold and wait: processes that already hold resources can wait for another resource.
- Non-preemption: a resource, once granted, cannot be taken away.
- Circular wait: two or more processes are waiting for resources held by one of the other processes.
We can express resource holds and requests via a resource allocation graph. An assignment edge means that a resource R1 is allocated to process P1. Since resources are exclusive, this means that P1 has a lock on the resource. A request edge means that a resource R1 is being requested by process P1. If process P1 cannot be granted access to the resource R1, it will have to wait. Deadlock is present when the graph has cycles.
We can consider a few strategies for dealing with deadlock.
- Deadlock prevention
- Ensure that at least one of the necessary conditions for deadlock cannot hold. This approach is sometimes used for transactional systems. Every transaction (process) is assigned a timestamp. For example, a transaction that wants to use a resource that an older process is holding will kill itself and restart later. This ensures that the resource allocation graph always flows from older to younger processes and cycles are impossible. It works for transactional systems since transactions, by their nature, are designed to be restartable (with rollback of system state when they abort). It is not a practical approach for general purpose processes.
- Deadlock avoidance
- Provide advance information to the operating system on which resources a process will request throughout its lifetime. The operating system can then decide if the process should be allowed to wait for resources or not and may be able to coordinate the scheduling of processes to ensure that deadlock does not occur. This is an impractical approach. A process is likely not to know ahead of time what resources it will be using and coordinating the scheduling of processes based on this information may not always be possible.
- Deadlock detection
- We allow deadlocks to occur but then rely on the operating system to detect the deadlock and deal with it. This requires that an operating system gets enough information to build a resource allocation graph. For instance, while an operating system will know which processes are blocked on a semaphore, it does not keep track of those that are not. After that, the operating system will need to decide what action to take. Do you kill any random process that is in the cycle? The youngest one? The oldest one? Or do you just warn the user? Operating systems avoid dealing with this.
- Ignore the problem
- By far the most common approach is simply to let the user deal any potential deadlock.
- Edsger W. Dijkstra, Cooperating sequential processes. Edsger W. Dijkstra’s lecture notes on the mutual exclusion problem and semaphores.
- Abraham Silberschatz, Peter B. Galvin, & Greg Gagne, Operating System Concepts Essentials, Wiley, 1st edition, 2010
- Abraham Silberschatz, Peter B. Galvin, & Greg Gagne, Operating System Concepts, Wiley, 8th edition, 2008
- Andrew S. Tanenbaum, Modern Operating Systems, Prentice Hall, 3rd edition, 2007
- Intel Corporation, IA–32 Intel Architecture Software Developer’s Manual, 2003
- Wikipedia. x86–64
- Michael Chynoweth & Mary R. LeeIntel Corporation, Implementing Scalable Atomic Locks for Multi-Core Intel EM64T and IA32 Architectures. Intel Corporation, November 2009
This is an updated version of the original document, which was written on September 21, 2010.