Announcements

• this is not part of the exam on oct 23
• exam next week thurs
• exercise 3 released

Synchronization Tools

• The problem: in a multithreaded or multiprocess system, your concurrent process can access shared data - and can lean to data inconsistency
• The goal is synchronization: to provide mechanisms that ensure the orderly execution of cooperating processes to ensure data consistency is maintained
• Key focus: the critical section problem, software/hardware solutions, advanced synchronization primitives like semaphores and monitors

Background and the Critical-Section Problem

• Race Condition: several processes try to access and manipulate the same data
  • same memory variable, in the same location, concurrently ("at the same time")
  • the outcome of the execution varies on what order the process accesses the data
  • a bank debit/credit operation where the final balance is incorrect due to interleaved updates
• Critical Section: the segment of code where a process or thread accesses and modifies shared data
• The Critical-Section Problem: designing a protocol that processes can use to cooperate
  • this protocol must guarantee that when one process is executing in its critical section, no other processes is allowed to execute in its critical section

this might not be copied properly

// g++ critical_sec.cpp -o critical_sec.exe
#include <iostream>
#include <thread>
#include <mutex>
#include <random>
#include <chrono>

// a mutex to protect the shared 'count' variable and
// ensure that the output is not jumbled
std::mutex mtx;

// global variable to be incremented by multiple threads
int counter = 0;

// this is the function that each thread will execute
// it takes an integer 'id' to identify the thread
void print_numbers(int id, int iteration) {
	thread_local std::mt19937 generatorrandom_device{}() + id;
	std::uniform_int_distribution<int> distribution (1, 1000);
	
	for (int i=0; (i < iteration); i++) {
		int local_count;
		//lock the mutex to ensure exclusive access to the shared resources
		// std::unique_lock<std::mutex> lock(mtx);
		// mtx.lock();
		std::cout << "Thread " << id << ": " << counter << std::endl;
		// THIS IS THE START OF THE CRITICAL SECTION !!!!!!!!!!!!!!
		local_count = counter;
		local_count++; // equivalent to local_count = local_count+1;
		// machine code equivalent is 
		// load register, local_count
		// add register, 1
		// store local_count, register 
		int random_num = distribution(generator);
		std::this_thread::sleep_formilliseconds(random_num);
	}
	
	// unlock the mutex when the scope ends
	// mtx.unlock();
	// THIS IS THE END OF THE CRITICAL SECTION !!!!!!!!!!!!!!
	std::this_thread::sleep_formilliseconds(100);
}

int main() {
	// create two threads, passing the print_numbers function
	// and a unique ID for each thread
	
	std::cout << "Initial value of counter is " << counter << std::endl;

	std::thread thread1(print_numbers, 1, 20);
	std::thread thread2(print_numbers, 2, 20);
	
	// wait for both threads to finish their execution
	thread1.join();
	thread2.join();
	
    std::cout << "all threads have finished" << std::endl;
    std::cout << "Final value of counter is " << counter << std::endl;
    return 0;
}

• i have no idea why this prints 0 only
• machine code is - most of the time - an atomic operation compared to high-level code

The Critical-Section Problem (Solution Requirements - So what do you do?)

any solution to the critical-section problem must satisfy three requirements

• Mutual Exclusion: if the process is executing in its critical section, then no other processes can be executing in their critical sections (as long as they're using the same global/memory variable)
  • if another process wants to execute their critical section but access another global variable then it should be ok
• Progress: if no process is executing in its critical section, and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder sections can participate in deciding which will enter next
  • this selection cannot be postponed indefinitely
• Bounded Waiting: there must be a limit on the number of times that other processes are allowed to entire their critical sections after a process has made a request to enter its critical section, and before that request is granted

Peterson's Solution

A classic software-based solution to the critical -section problem for two processes and

• Mechanism: uses 2 shared variables
  • turn: an integer variable indicating whose turn it is to enter the critical section
  • flag[2]: a Boolean array where flag[i] = true means its ready to enter the critical section
• Proof: Peterson's solution satisfies all 3 requirements: Mutual Exclusion, Progress, and Bounded Waiting
• Limitation: it is limited to only 2 processes and does not work well on modern computer architectures where memory access is optimized and reordered; though this can be expanded to more than 2 processes.

The Protocol for Process:

do {
	flag[i] = true; // indicate i want to enter
	turn = j; // give permission to the other process
	while (flag[j] && turn == j);
	// wait if other process wants in AND its their turn
	// CRITICAL SECTION
	flag[i] = false; // exit
	// REMAINDER SECTION
} while (true);

The solution...

• enforces mutual exclusion
• uses only simple shared variables (does not use special instructions such as Test-and-Set)
• uses 2 flag variables: c1 for process P1, c2 for process P2
• a flag value = 1 indicates that the process wants to enter the critical section
• a variable turn holds the ID of the process whose turn it is
• entrance to the critical section is granted for process P1 if P2 does not want to enter its critical section or if P2 has given priority to P1 by setting turn to 1

sample trace in slides

Synchronization Hardware

• Hardware Solutions: modern computer architectures provide special atomic (uninterruptable) hardware instructions to simplify the critical-section problem and increase efficiency
• Atomic Operation: an operation that is executed as a single, uninterruptable unit
• TestAndSet() Instruction: atomically tests the value of a memory word and sets it to true/1
• CompareAndSwap() Instruction (CAS): atomically compares the value of a memory word with an executed value, and if they match, swaps the memory word with a new value
• Mutex Locks using Hardware: these atomic instructions can be used to implement simple locks (called mutex locks in operating systems) to ensure mutual exclusion

some high-level code/not machine code

boolean TestAndSet(boolean *target) {
	booleanrv = *target;
	*target = true;
	return rv;
}

boolean CompareAndSwap(int *value, int expected, int new_value) {
	int temp = *value;
	if (*value == expected) { *value = new_value }
	return temp;
}

Mutex Locks

• Mutex (Mutual Exclusion) Lock: the simplest and most common synchronization tool
• a process must acquire() the lock before entering a critical section and release() the lock upon exiting
• State: a mutex lock has a Boolean variable, available, indicating if the lock is held (false) or not (true)
• Acquire and Release Operations
  • Busy Waiting (Spinlock): the process wishing to acquire the lock continuously loops until the lock is available
    • wastes CPU cycles if the critical section is long
    • a lock that uses busy waiting is called a spin lock
• Benefit of Spinlocks: useful in multicore systems, because no context switch is required when a thread waits for a lock, which is advantageous if the waiting time is expected to be very short

code edit at 52:10

Semaphores

a synchronization primitive that provides a more sophisticated tool than simple mutex locks (a mutex lock but you can put a number on it)

• an integer variable that is accessed only through two atomic operations: wait() and signal()
• wait() or P: decrements the semaphore value. if the value becomes negative, the process is blocked
• signal() or V: increments the semaphore value. if the value ≤ 0, a waiting (blocked) process is unblocked
  types:
• Counting Semaphore: the integer value can range over an unrestricted domain; used to control access to a resource pool with multiple instances
• Binary Semaphore: the integer value can only be 0 or 1; functions identically to a mutex lock
• Solving Busy Waiting: Semaphores solve the busy-waiting problem by associating a waiting queue with the semaphore. when a process executes a wait() operation and finds the semaphore value, it is placed into this queue and its state is changed to blocked.

Classic Synchronization Problems

used as benchmarks to test the efficiency and correctness of new synchronization tools:

• Bounded-Buffer Problem
• Readers-Writers Problem

Bounded-Buffer Problem (Producer-Consumer)

• Goal: synchronize a producer (who produces items) and a Consumer (who consumes items) using a finite-sized buffer
• if there's one thread that produces data that the other thread is consuming

Semaphores used:

• mutex: Binary Semaphore for mutual exclusion (initial value=1)
• empty: Counting semaphore for the number of empty slots (initial value=Buffer size N)
• full: Counting semaphore for the number of occupied slots (initial value=0)

Readers-Writers Problem

• note just to read the data
• Goal: allow multiple processes to concurrently read shared data, but only one process can write to the data at a time
• Priority: two variations
  • prioritizing readers (no reader waits for a writer to finish)
  • prioritizing writers (no new readers can start if a writer is waiting)

Monitors

a high-level synchronization construct that is designed to simplify concurrent programming and avoid common errors associated with semaphores

• Encapsulation: a monitor is an abstract data type that contains:
  • a set of programmer-defined operations (methods)
  • an encapsulated set of shared variables
• Synchronization mechanism: condition variables are built into the structure
• Mutual Exclusion Guarantee: the monitor construct guarantees that only one process can be active within the monitor at any given time
  • this built-in mutual exclusion greatly simplifies programming
• Condition Variables: used within a monitor to allow a process to wait for a specific condition to become true. the two operations:
  • wait() suspends the calling process until another process invokes signal()
  • signal()resumes one suspended process. if no process is waiting, the operation has no effect

Deadlocks and Starvation

• Deadlock: a condition where 2 or more processes are waiting indefinitely for an event that can only be caused by one of the waiting processes
  • ex. 2 processes, and each hold a resources and wait for the other process to release the resource
• Starvation (Indefinite Blocking): a process may wait indefinitely within a semaphore's waiting queue, even though other processes are repeatedly entering and leaving the critical section
  • unlike deadlock, the system is still making progress, just not for the starved process
  • solution: ensure that a process waiting in the queue for a resource is eventually served