Synchronization
Table of Contents
1. Yielding
To run a thread, we:
- Load its state (registers, PC, stack pointer) into the CPU
- Load environment (virtual memory space, etc.)
- Jump to the PC
This gives control of processor to user code. For the kernel to get control back, we rely on either internal events or external events.
1.1. Internal Events
Several internal events gives control back to the OS:
- Blocking on I/O: requesting I/O implicitly yields the CPU
- Waiting on a “signal” from another thread: threads asks to wait and thus yields the CPU
- Thread executies a
yield(): thread volunteers to give up CPU
Yield traps into the kernel, where kernel_yield runs to tell us to run_new_thread. This then picks the new thread to run, at which point we switch to the new thread.
1.2. External Events
If the thread never does any I/O, never waits, and never yields control, we still need a way for the kernel to gain control. The solution is to use external events like interrupts and timers. For example, we can use a timer interrupt to force scheduling decsisions at a given interval.
2. Atomic Operations
An atomic operation is an operation that always runs to completion or not at all: it is indivisible, which means it cannot be stopped in the middle and its state cannot be modified by someone else in the middle. For example, on most machines loads and stores of words are atomic.
Synchronization is using atomic operations to ensure cooperation between threads. Mutual exclusion is ensuring that only one thread does a particular thing at a time. Finally, a critical section is a block of code that can only be executed by one thread at a time. A threaded program is considered correct if it works for all interleavings of thread instruction sequences.
3. Locks
A lock prevents someone else from doing something. Generally, you lock before entering a critical section or accessing shared data, and then unlock when leaving. The key idea here is that all synchronization involves waiting.
Locks provide two atomic operations:
acquire(&lock)— wait until lock is free, then mark it as busyrelease(&lock)— mark lock as free
Acquire either acquires the lock successfully, or sees that it is busy and puts the current thread on a wait queue sleeping. Release then checks the wait queue upon release and wakes up the next thread waiting to acquire the lock.
3.1. Disabling Interrupts
One way to implement locks is to disable interrupts. Recall that the scheduler gets control either through internal events (controlled by the thread), or external events (hardware interrupts). Therefore, if we disable interrupts when we acquire a lock, and then re-enable interrupts when we release the lock, then nothing external can run while our thread holds the lock.
However, this means that we allow the user to disable interrupts, which is a bad idea. Instead, we can maintain a lock variable and impose mutual exclusion only during operations on that variable. This way, even if we get stuck in a loop while holding a lock, interrupts can still run at that time:
acquire() {
disable interrupts;
if (value == BUSY) {
put thread on wait queue;
sleep();
} else {
value = BUSY;
}
enable interrupts;
}
Sleep disables interrupts, so it is the responsibility of the next thread to re-enable interrupts.
3.2. Atomic Read-Modify-Write Instructions
The problem with disabling interrupts is that it doesn’t work very well on a multiprocessor chip. Disabling interrupts on all processors requires messages and would be very time consuming. An alternative are atomic read-modify-write instructions, which are atomic operations that read a value and write a new value:
test_and_set(&address) {
result = M[address]; // return result from address and
M[address] = 1; // set value at address to 1
return result;
}
We can implement a lock using test_and_set():
acquire(int *thelock) {
while(test_and_set(thelock));
}
4. Semaphores
Semaphores are a kind of generalized lock: they have a non-negative integer value and supports the following operations:
- Sets value when you initialize
down()orp(): an atomic operation that waits (sleeps) for the semaphore to become positive, then decrements it by 1up()orv(): an atomic operation that increments the semaphore by 1, waking up a waitingp(), if any
Technically, examining the value after initialization is not supported. In this way, semaphores are like non-negative integers except the only operations allowed are the atmoic p() and v() operations (can’t read or write, except initially).
The semaphore comes from the railway analogy:
Semaphores can be very powerful. We can implement mutual exclusion by initializing the semaphore to 1. We can also use v() to signal another thread sleeping via p() when the semaphore is initialized to 0.
5. Monitors
A monitor is a lock and zero or more condition variables for managing concurrent access to shared data. A condition variable is a queue of threads waiting for something inside a critical section. We can do the following operations on a monitor:
wait(&lock): atomically release lock and go to sleep; reacquire lock later before returningsignal(): wake up one waiter, if anybroadcast(): wake up all waiters
The rule is that we must hold the lock while doing condition variable operations.
5.1. Hoare Monitors
A paradigm of using monitors where the signaler, after signaling, gives up the lock immediately and passes the CPU to the waiter. This allows the waiter to use an if instead a while so that it does not need to check the condition again before running.
However, these semantics become complicated since it interferes with the work of the scheduler.
5.2. Mesa Monitors
This paradigm is used much more in modern operating systems. After signaling, the signaler keeps the lock and the waiter is placed on the ready queue with no special priority. Therefore, with this paradigm, the waiter must check the condition again after wait.
6. Readers-Writer Locks
Readers-writer locks (RW locks) are synchronization primitives that let multiple “reader” threads access a critical section, or one “writer” thread only. There are three operations on a RW lock:
read(): atomically acquires the lock in read modewrite(): atomically acquires the lock in write modeunlock(): release the lock
The key idea is that a thread holding the lock in read mode should not do anything that could cause a race condition with other threads also holding the lock in read mode.
7. Futexes
The problem with many implementations of locks is that it requires a syscall, which means a context switch into the kernel even if there is no contention A futex (fast userspace mutex) allows the user program to sleep until a condition becomes true where most of the logic occurs in userspace:
futex(int *uaddr, int operation, int val);
The futex compares the value at uaddr with val, and does an operation depending on if they are equal or not. The operation can either be FUTEX_WAIT or FUTEX_WAKE:
FUTEX_WAIT: Atomically checks if*uaddrequalsval. If so, puts the calling thread to sleep; otherwise, returns immediately.FUTEX_WAKE: Wakes up tovalthreads currently sleeping onuaddr.