Synchronization

Definitions

• Critical Regions: Regions of code that can only have one thread enter at a time, or risk a data race
• Atomic Operations: Operations where the architecture guarantees the read and write to the memory will not have something run in between

Dangers

• Data Races
  • Two concurrently running threads are in a data race if they
    • access some shared data,
    • at least one access is a write,
    • and the result depends on who goes first.
  • Can be avoided using mutual exclusive accesses (critical regions)
• Loss of liveness
  • Deadlock: Occurs when all processes block, with each process waiting on the next. In this condition, no progress is made
  • Starvation: Occurs when at least one process waits indefinitely

Approaches

1. Mutual Exclusion (locks)
2. Thread local data (__thread)
3. Thread specific data (pthread_getspecific)
4. Parameters

Mutex

• A data structure for achieving mutual exclusion
  • A flag denoting availability
  • A queue of threads that are waiting to acquire it
• Operations
  • Acquire/lock a mutex (atomic operation, may block)
    • If the mutex is available, set it to unavailable and return
    • If the mutex is not available, add the calling thread to the queue and block that thread
  • Release/unlock a mutex (anomic operation, no blocking)
    • If the queue is empty, set to available
    • If the queue is not empty, select one of the threads in the queue and unblock it

Condition Variables

• Denotes the occurrence of a possible synchronization event
• Let the threads wait or sleep on a specific condition variable and upon wake up/signaling explicitly check the conditions and decide to go back to sleep or continue with the mutual exclusive updates
• All checks need to employ mutual exclusion to avoid data races
  • A condition variable is associated with a mutual exclusion lock to avoid data races
• Implemented using a queue of thread ids
• Functions
  • pthread_cond_wait(pthread_cond_t *c, pthread_mutex_t *mutex)
    • Block the current thread
    • Inserts the id of the calling thread to the queue of c, unlocks mutex, and blocks the calling thread
  • pthread_cond_signal(c)
    • Wakes up a single thread
    • If the queue of c is not empty, removes a thread T from the queue, unblocks it, and T tries to acquire the mutex
  • pthread_cond_broadcast(c)
    • Wakes up everyone
    • If the queue of c is not empty, removes all the waiting threads form the queue, unblocks them, and each thread tries to acquire the mutex

Semaphores

• Array of locks, counter
• Queue: List of processes waiting for resources
• Operations
  • Creation
    • Created with a starting count
    • The count is the capacity that it is able to support
  • Down (decrement)
    • Call when you want access
    • If count > 0, decrement and continue
    • Otherwise, block and add caller to the queue
  • Up (increment)
    • Call when you are done with access
    • If the queue is empty, increment count and continue
    • Otherwise, dequeue and unblock that process
• Any thread with access to the semaphore can increment or decrement
• A binary semaphore is similar to a mutex but can be unlocked by any thread
• semaphore.h
  • sem_wait decrements
  • sem_post increments

Busy Waiting

• Infinite loop that keeps checking that a lock is available until it is
• Very inefficient because it hogs resources doing nothing
• Types
  • Strict Alternation
    • Round robin of access
    • Issue: Processes cannot have to wait for the other process to lock and unlock before locking again
  • Flagging Interest
    • Aims to avoid excessive waits by having processes indicate wanting to enter before giving access
    • Issue: If both processes flag before one gets access, there is a deadlock
  • Peterson Solution
    • Combines the flagging and alternation approaches
    • If both are interested at the same time, take turns
• Implementation: Atomic Locking with a Spin Lock

; Test and Set Lock
busy_lock:  
	tsl register, lock   ; Copy lock, reg; set lock = 1
	cmp register, #0     ; Was lock zero?
	jnz busy_lock        ; If not zero, jump to busy_lock
	ret                  ; Return (critical region entered)
 
busy_unlock:  
	move lock, #0        ; Unlock
	ret                  ; Return (critical region exited)

Shadow Copies

• Copy on Write
• Necessary when one process is writing to a shared structure and other processes are reading
• Process
  1. Make original data read-only (read-only lock)
  2. Make a copy of the original data
  3. Update copy with new information
  4. Change pointer to new copy (new reads will see the copy)
  5. Release old data (delete) once all readers are done

Barriers

• Require all processes to reach a specific point before they can continue
• Can be implemented in a language or manually using other synchronization primitives (such as condition variables)

Monitors

• Type of lock
  • Locks a thread until another thread notifies it to continue
  • Guarantee that at most one process enters the critical region at a time
• Implementation
  • Require language support
  • Can be explicit or implicit within a language
  • Not based on shared memory to lock
  • Use conditional variables provided by the programming language

Messaging

• Message passing enables synchronization
• Have a single server that manages locks, and clients that request it
• Used by distributed operating systems

Problems

Dining Philosophers

• Demonstrates the pattern of circular deadlock
• Setup
  • Philosophers sitting around a table. They can all be thinking, eating, or waiting.
  • Each philosopher gets one chop stick, but they need to borrow a chop stick from a thinking neighbor to be able to eat
  • Deadlock occurs when each philosopher is waiting on the next, and no one is able to eat
• Challenges
  • Concurrency: No assumptions may be made about how long any process eats (runs critical section) or thinks (runs non-critical section)
  • Safety: Any two philosophers (processes) that are not (logically) adjacent can eat (run its critical section) simultaneously
  • Liveness: A philosopher that is not eating cannot prevent another philosopher from eating

Solution 1: Break the circularity

• Impose a total order
• So chopstick 1 must be acquired before chopstick 2 which must be acquired before chopstick 3, etc.
• So two cannot be waiting on the same resource
• Easiest solution

Solution 2: Acquiring all resources at once

• Either get both chopsticks or do not get any (do not just hold onto one and wait for the second)
• Must know about the state of the resources

mutex critical;
semaphore philo[N](0); // binary semaphores
 
enum philo_state { HUNGRY, THINKING, EATING } state[N];
 
void doPhilosophy(int philoIdx) {  
	while (isPhilosophizing) {  
		thinkDeeply();
		takeBoth(philoIdx);
		eat();
		dropBoth();
	}
}
 
void takeBoth(int philoIdx) {
	mutex_lock(&critical);
	state[philoIdx] = HUNGRY;
	testEats(philoIdx);
	mutex_unlock(&critical);
 
	// after unlock so other blocked processes can immediately be unlocked 
	sem_wait(philo[philoIdx]);
}
 
void dropBoth(int philoIdx) {  
	mutex_lock(&critical);
	state[philo] = THINKING;
	
	// run test eats for the surrounding philos
	// to unblock them if they are waiting
	testEats(leftIdx(philoIdx));
	testEats(rightIdx(philoIdx));
	
	mutex_unlock(&critical);
}
 
void testEats(int philoIdx) {  
	if (
		state[philoIdx] == HUNGRY &&
		state[leftIdx(philoIdx)] != EATING &&
		state[rightIdx(philoIdx)] != EATING
	) {  
		state[philoIdx] = EATING;  
		sem_post(philo[philoIdx]);  
	}
}
 
int leftIdx(i) { return (i + N – 1) % N; }
int rightIdx(i) { return (i + 1) % N; }

Producer-Consumer

• When one or more producers and one or more consumers act on the same finite data buffer
• Producers place data (write) in the buffer. Consumers remove data (read) from the buffer
• Challenges
  • Concurrency
    • Producers and consumers act in parallel
    • Multiple producers/consumers should be able to read buffers at the same time
    • No assumptions may be made about the speed of any process
  • Safety
    • Never can two producers write to the same entry at the same time
    • Never can two consumers read from the same entry at the same time
    • Never can a consumer read from an entry while a producer is writing to it
  • Liveness
    • No process not currently writing to or reading from an entry may prevent another process from finding an entry
    • No process must wait indefinitely to obtain access to an entry as long as entries are available
  • Correctness
    • No entry shall be overwritten with a new item before the previous item is removed
    • No empty entry shall be read by a consumer
• Solution
  • Lock entire buffer using semaphores
    • Prevents corrupt shared variables, double-write, double-read, etc.
    • However, the critical regions cause a bottleneck (which becomes more pronounced with multiple producers/consumers```
  • Marking entries using semaphores
    • Instead of locking entire buffer, lock individual entries
    • Critical section is only for finding the next entry instead of also writing it (which is much quicker)

void producerThread() {  
	dataType item;  
	int entry;  
	while (isProducing) {  
		item = produceItem();  
		entry = getEmpty();  
		buffer.insert(entry, item);  
		alertFull(entry);  
	}  
}
 
void consumerThread() {  
	dataType item;  
	int entry;  
	while (isConsuming) {  
		entry = getFull();  
		item = buffer.remove(entry);  
		alertEmpty(entry);  
		consumeItem(item);  
	}  
}
 
semaphore critical(1), empty(MAX_ENTRIES), full(0);
 
int getEmpty() {  
	int entry;  
	empty.down();  
	critical.down();  
	entry = buffer.findEmpty();  
	buffer.markBusy(entry);  
	critical.up();  
	return entry;  
}  
 
int getFull() {  
	int entry;  
	full.down();  
	critical.down();  
	entry = buffer.findFull();  
	buffer.markBusy(entry);  
	critical.up();  
	return entry;  
}
 
void alertFull(int entry) {  
	critical.down();  
	buffer.markFull(entry);  
	critical.up();  
	full.up();  
}  
 
void alertEmpty(int entry) {  
	critical.down();  
	buffer.markEmpty(entry);  
	critical.up();  
	empty.up();  
}

Reader-Writers

• One or more readers (which only read) and one or more writers (which may read before writing) working on a single database concurrently
• Difference from producer-consumer: only the writer modifies the data structure instead of both
• Challenges
  • Concurrency
    • Multiple readers may read the database at the same time
    • No assumptions about speed
  • Safety
    • Never two or more writers can write at the same time
    • Never may a reader read from the database while a writer is writing it
  • Liveness
    • No process not currently using the database may prevent another from accessing it
    • No process not currently using the database may prevent another from accessing it
• Solution
  • Use semaphores to allow multiple readers and then start writing when none are reading
  • Uses alpha locks (tentative write lock)
    • Allow a writer to read while waiting for a write lock
    • Prevents other writers from obtaining an alpha lock

semaphore_t rm; // reader lock
semaphore_t wm; // writer lock
 
void read() {
	sem_wait(rm);
	numReaders++;
	if (numReaders == 1)
		sem_wait(wm);
	sem_post(rm);
	
	/* read */
	
	sem_wait(rm);
	numReaders--;
	if (numReaders == 0)
		sem_post(wm);
	sem_post(rm);
}
 
void write() {
	sem_lock(wm);
	/* write */
	sem_unlock(wm);
}