04 - Synchronisation

Question 1

Mutual Exclusion

Answer 1

If a process is executing in its critical section, then no other processes can be executing in their critical sections

Question 2

Critical Section

Answer 2

Segment of code where:
process may be changing common variables, updating table,
writing file, etc.

Question 3

Critical-Section problem

Answer 3

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.

Question 4

Progress

Answer 4

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

Question 5

Bounded Waiting

Answer 5

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

Question 6

Peterson’s Solution

Answer 6

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.

Question 7

Peterson variables

Answer 7

‘turn’
indicates whose turn it is

‘flag[i]’
indicates if process Pi is ready

Question 8

Petersons Process Pi
‘flag[0] = true; turn =1;’

Answer 8

Enters critical section if Pj is not ready and turn is its own.

Question 9

Petersons Process Pj
‘flag[1] = true; turn =0;’

Answer 9

Enters critical section if Pi is not ready and turn is its own.

Question 10

Memory Barrier

Answer 10

Instruction ensuring changes in memory are visible to all processors

Question 11

Memory Models

Answer 11

Guarantee memory behaviours in computer architectures

Question 12

Strongly Ordered

Answer 12

Immediate visibility of memory modifications across processors

Question 13

Weakly Ordered

Answer 13

Delayed visibility of memory modifications across processors

Question 14

Memory Barrier Instruction

Answer 14

Ensures completion of loads and stores before subsequent operations

Question 15

__sync_synchronize():

Answer 15

C function ensuring no memory operands move across the operation, backward or forward

Question 16

Hardware Intructions

Answer 16

Special hardware instructions for testing and modifying data

Question 17

test_and_set

Answer 17

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

Question 18

compare_and_swap

Answer 18

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)

Question 19

Atomic Variables

Answer 19

Variables providing uninterruptible updates on basic data types (integers and booleans)

Question 20

Increment()

Answer 20

Example: increment(&sequence) ensures uninterrupted incrementing of sequence.

Implementation: increment() function ensures atomic incrementing of an atomic integer variable.

Question 21

Mutex Locks

Answer 21

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

Question 22

Semaphore

Answer 22

Synchronization primitive controlling access to shared resources

Question 23

wait(S)

Answer 23

Operation that decrements semaphore S;

if S <= 0, process blocks.

Question 24

signal(S)

Answer 24

Operation that increments semaphore S;

wakes up blocked process if any.

Question 25

Binary Semaphore

Answer 25

Semaphore with two states (0 or 1), typically used for mutual exclusion.

Question 26

Counting Semaphore

Answer 26

Semaphore with non-negative integer value, used for controlling access to multiple resources.

Question 27

Busy Waiting

Answer 27

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.

Question 28

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

Answer 28

Philosopher i:
wait(chopstick[i]);
wait(chopstick[(i + 1) % 5]);
eat for awhile
signal(chopstick[i]);
signal(chopstick[(i + 1) % 5]);
think for awhile

Question 29

Deadlock

Answer 29

A situation where two or more processes are unable to proceed because each is waiting for the other to release a resource.

Question 30

Hold and Wait

Answer 30

Processes hold resources while waiting for others, causing resource utilisation inefficiency

Question 31

Deadlock: Mutal Exclusion

Answer 31

Resources cannot be simultaneously shared, leading to exclusive access.

Question 32

No Preemption

Answer 32

Resources cannot be forcibly taken from a process; they must be released voluntarily.

Question 33

Circular Wait

Answer 33

A circular chain of processes exists, where each process holds a resource needed by the next process in the chain.

Question 34

Deadlock Example

Answer 34

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.

Question 35

Deadlock Prevention

Answer 35

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.

Question 36

Banker’s Algorithm

Answer 36

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]