04 - Synchronisation Flashcards
(36 cards)
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.
