04 - Synchronisation Flashcards
Mutual Exclusion
If a process is executing in its critical section, then no other processes can be executing in their critical sections
Critical Section
Segment of code where:
process may be changing common variables, updating table,
writing file, etc.
Critical-Section problem
Protocol that ensures safe access to shared resources by multiple threads or processes, preventing race conditions and ensuring data integrity during concurrent access to critical sections.
Progress
If no process is executing in its critical section and there are processes that want to enter their critical section, the selection of the process that will enter next can’t be postponed indefinitely
Bounded Waiting
A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section before that request is granted
Peterson’s Solution
Two Process Software Solution
Ensures mutual exclusion by providing a way for processes to take turns accessing a shared resource while preventing race conditions.
se of two shared variables, flags, and turn, along with careful synchronisation using atomic operations such as test-and-set or compare-and-swap.
Peterson variables
‘turn’
indicates whose turn it is
‘flag[i]’
indicates if process Pi is ready
Petersons Process Pi
‘flag[0] = true; turn =1;’
Enters critical section if Pj is not ready and turn is its own.
Petersons Process Pj
‘flag[1] = true; turn =0;’
Enters critical section if Pi is not ready and turn is its own.
Memory Barrier
Instruction ensuring changes in memory are visible to all processors
Memory Models
Guarantee memory behaviours in computer architectures
Strongly Ordered
Immediate visibility of memory modifications across processors
Weakly Ordered
Delayed visibility of memory modifications across processors
Memory Barrier Instruction
Ensures completion of loads and stores before subsequent operations
__sync_synchronize():
C function ensuring no memory operands move across the operation, backward or forward
Hardware Intructions
Special hardware instructions for testing and modifying data
test_and_set
Atomically sets a boolean variable to true and returns its original value.
Example:
shared boolean lock = false
while test_and_set(&lock) == true:
print(“Thread 1 is printing”)
lock = false
compare_and_swap
Atomically compares the value of a variable with an expected value and swaps it if they match.
Example:
shared integer counter = 0
new_value = counter + 1
compare_and_swap(&counter, counter, new_value)
Atomic Variables
Variables providing uninterruptible updates on basic data types (integers and booleans)
Increment()
Example: increment(&sequence) ensures uninterrupted incrementing of sequence.
Implementation: increment() function ensures atomic incrementing of an atomic integer variable.
Mutex Locks
Software mechanism for controlling access to critical sections
Uses a boolean variable to indicate availability of the lock
Acquire lock before entering critical section, release afterward
Semaphore
Synchronization primitive controlling access to shared resources
wait(S)
Operation that decrements semaphore S;
if S <= 0, process blocks.
signal(S)
Operation that increments semaphore S;
wakes up blocked process if any.
Binary Semaphore
Semaphore with two states (0 or 1), typically used for mutual exclusion.
Counting Semaphore
Semaphore with non-negative integer value, used for controlling access to multiple resources.
Busy Waiting
A synchronization technique where a process repeatedly checks for a condition rather than blocking.
The process continuously executes a loop, checking the condition until it becomes true.
Often used in spinlocks and semaphore implementations.
Dining Philsophers Problem:
N philosophers at a round table
Alternating between thinking and eating
Shared data: Bowl of rice, Semaphore chopstick[5] initialized to 1
Philosopher i:
wait(chopstick[i]);
wait(chopstick[(i + 1) % 5]);
eat for awhile
signal(chopstick[i]);
signal(chopstick[(i + 1) % 5]);
think for awhile
Deadlock
A situation where two or more processes are unable to proceed because each is waiting for the other to release a resource.
Hold and Wait
Processes hold resources while waiting for others, causing resource utilisation inefficiency
Deadlock: Mutal Exclusion
Resources cannot be simultaneously shared, leading to exclusive access.
No Preemption
Resources cannot be forcibly taken from a process; they must be released voluntarily.
Circular Wait
A circular chain of processes exists, where each process holds a resource needed by the next process in the chain.
Deadlock Example
Example: Two processes, P1 and P2, each holding one resource and waiting for the other resource held by the other process.
Requirements: Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait.
Deadlock Prevention
Ensure at least one of the necessary conditions for deadlock does not hold. For example, using resource allocation strategies like deadlock avoidance or deadlock detection with resource allocation graphs.
Banker’s Algorithm
Resource allocation algorithm to prevent deadlock and ensure safe resource usage.
Requirements:
Multiple resource instances, processes claiming maximum resource use a priori, and possible waiting for resource requests.
Data Structures:
-Available: Vector indicating available instances of each resource type.
-Max: Matrix specifying maximum resource needs for each process.
-Allocation: Matrix indicating currently allocated resources for each process.
-Need: Matrix representing remaining resource needs for each process.
Calculation:
Need[i,j] =
Max[i,j] - Allocation[i,j]
