Synchronization Items

Question 1

What are synchronization problems?

Answer 1

Programing problems that arise when you create multithreaded code or a program that exchanges data with other programs.

Question 2

What synchronization hazards do you know?

Answer 2

Race condition and deadlock.

Question 3

What is a shared resource?

Answer 3

A shared resource is a resource that can be accessed by multiple threads or processes simultaneously. Examples include variables, data structures, files, and hardware devices. Access to shared resources must be carefully managed to prevent conflicts and ensure data consistency.

Question 4

What is a race condition (a.k.a. data race)?

Answer 4

A race condition occurs when two computer program processes, or threads, attempt to access the same resource at the same time and cause problems in the system.

A race condition occurs when the behavior and outcome of a program depend on the relative timing of events, such as the order in which threads or processes execute. This can lead to unpredictable and erroneous results if two or more threads modify shared data concurrently without proper synchronization.

Question 5

Explain how a race condition can happen.

Answer 5

At the assembly/CPU level, a race condition can happen when two or more threads or processes execute instructions that access and modify the same memory location simultaneously. For example, consider two threads incrementing a shared variable:

Thread 1 reads the variable's value into a register.
Thread 2 reads the same variable's value into a register.
Thread 1 increments the register's value and writes it back to memory.
Thread 2 increments the (old) register's value and writes it back to memory.
As a result, the variable is only incremented once, even though both threads attempted to increment it.

Question 6

Can a race condition happen if only one party modifies the data and others are just reading? Can a race condition happen if everybody is just reading?

Answer 6

A race condition can happen if only one party modifies the data and others are just reading, as readers might get inconsistent or partially updated data. However, if everybody is just reading, a race condition cannot happen because reading does not change the state of the shared resource, so there are no conflicting updates.

Question 7

What are the three properties of a good solution to the critical section problem?

Answer 7

Mutual Exclusion: Ensures that only one process can be in the critical section at a time.
Progress: If no process is in the critical section, and some processes wish to enter, one of the waiting processes must be allowed to enter.
Bounded Waiting: Guarantees that each process will get a chance to enter the critical section within a bounded number of turns.

Question 7

What is the critical section problem?

Answer 7

The critical section problem involves ensuring that when multiple threads or processes access shared resources, at most one is executing in the critical section at any given time. A critical section in computer programming is a part of a multi-process program that must not be concurrently executed by more than one process.

Question 8

Explain the idea of locking shared resources.

Answer 8

Locking shared resources involves using synchronization mechanisms, such as locks, to control access to shared resources. A lock can be acquired by a thread before entering the critical section and released after exiting it, ensuring that only one thread can access the shared resource at a time.

Question 9

What does it mean to have an atomic function?

Answer 9

An atomic function is an operation that is indivisible, meaning it is executed completely without interruption. Two parts of the definition are:

It is performed as a single, uninterruptible step.
No other operations can observe the function in a partially completed state.

Question 10

What does it mean if the function is hardware implemented?

Answer 10

If a function is hardware implemented, it means there is no program code for it, and no general CPU instructions are written in memory. Instead, the function is implemented with hardware circuitry and called with a single special CPU instruction. This often makes the function faster and ensures atomicity at the hardware level.

Question 11

What is test_and_set instruction and what does it do?

Answer 11

The test_and_set instruction is an atomic operation used in synchronization to achieve mutual exclusion. It tests the value of a variable and sets it to a new value (usually true) in one indivisible operation. If the variable was previously false, it returns false and sets the variable to true. If it was already true, it returns true.

Question 12

Simple solution of the critical section problem using test_and_set instruction. What is suboptimal in this solution?

Answer 12

A simple solution using test_and_set involves each process repeatedly calling test_and_set in a loop (busy waiting) until it successfully enters the critical section.
Suboptimal Aspect: It doesn’t have the “bounded waiting” property, meaning it is not starvation-free. A process may wait indefinitely if other processes repeatedly access the critical section.

Question 13

Solution of the critical section problem using test_and_set instruction with the “bounded waiting” property.

Answer 13

A solution with bounded waiting can be implemented using additional variables to ensure that each process gets a chance to enter the critical section. One common approach is Peterson’s algorithm, which uses two shared variables (flags and turn) to achieve mutual exclusion with bounded waiting.

Here’s a conceptual implementation in pseudocode:

cpp

bool flag[n]; // Array of flags for each process
int turn; // Shared variable indicating whose turn it is

void enter_critical_section(int i) {
flag[i] = true;
turn = i;
while (flag[(i + 1) % n] && turn == i) { /* busy wait */ }
}

void exit_critical_section(int i) {
flag[i] = false;
}

Question 14

What does busy waiting mean? Why is it inefficient? When is it still good?

Answer 14

Busy Waiting: A synchronization technique where a process repeatedly checks a condition in a loop until it becomes true.
Inefficient: It consumes CPU cycles unnecessarily, as the process does nothing useful while waiting.
Still Good: When expected wait times are short and the overhead of performing a context switch to another process is higher than the cost of busy waiting.

Question 15

What is mutex? What does a process do if it needs a mutex that is busy?

Answer 15

Mutex: A mutual exclusion object used to protect critical sections, ensuring that only one thread can access the resource at a time.
Busy Mutex: If a process needs a mutex that is busy, it typically pauses (e.g., by entering a waiting state or using a condition variable) until the mutex becomes available.

Question 16

Using C++ std::mutex to protect critical sections of code.

Answer 16

Example:

cpp

std::mutex mtx;

void critical_section() {
std::lock_guard<std::mutex> lock(mtx);
// Critical section code here
}

std::mutex mutex;
void critical_section() {
mutex.lock();
mutex.unlock();
}

Question 17

Producer-Consumer problem (a.k.a. Bounded Buffer problem) // and its solution.

Answer 17

The problem describes two processes, the producer and the consumer that share a common fixed-size buffer and use it as a queue. The producer’s job is to generate data, put it into the buffer, and start again.

What is the Actual Problem?

Given the common fixed-size buffer, the task is to make sure that the producer can’t add data into the buffer when it is full and the consumer can’t remove data from an empty buffer. Accessing memory buffers should not be allowed to producers and consumers at the same time.

Solution of Producer-Consumer Problem

The producer is to either go to sleep or discard data if the buffer is full. The next time the consumer removes an item from the buffer, it notifies the producer, who starts to fill the buffer again. In the same manner, the consumer can go to sleep if it finds the buffer to be empty. The next time the producer transfer data into the buffer, it wakes up the sleeping consumer.

Question 18

Readers-Writers problem and its solution.

Answer 18

The problem involves synchronizing access to a shared resource with multiple readers and writers.

Solution: Use mutexes and condition variables to allow multiple readers or one writer at a time.

cpp

std::mutex mtx;
std::condition_variable cv;
int reader_count = 0;
bool writer_active = false;

void reader() {
std::unique_lock<std::mutex> lock(mtx);
cv.wait(lock, [] { return !writer_active; });
reader_count++;
lock.unlock();

// Read from shared resource

lock.lock();
reader_count--;
if (reader_count == 0) cv.notify_all();
lock.unlock(); }

void writer() {
std::unique_lock<std::mutex> lock(mtx);
cv.wait(lock, [] { return !writer_active && reader_count == 0; });
writer_active = true;
lock.unlock();

// Write to shared resource

lock.lock();
writer_active = false;
cv.notify_all();
lock.unlock(); }

Question 19

Describe Dining Philosophers problem. What do philosophers represent? What do chopsticks represent?

Answer 19

The Dining Philosophers problem is a classic synchronization problem. It involves philosophers sitting around a table with one chopstick between each pair. Philosophers alternate between thinking and eating, and need both chopsticks to eat.
Philosophers: Represent processes or threads.
Chopsticks: Represent shared resources that need mutual exclusion.

Question 20

What is deadlock?

Answer 20

A deadlock is said to occur when two or more processes are waiting for each other to release a resource.

Deadlock is a state where a set of processes or threads are unable to proceed because each is waiting for a resource held by another, forming a cycle of dependencies.

Question 21

Name 3 approaches to solving the Dining Philosophers problem.

Answer 21

Resource Hierarchy Solution: Assign a partial ordering to resources and ensure that each philosopher picks up resources in order.
Chandy/Misra Solution: Allow philosophers to pick up chopsticks only if both are available, preventing circular wait.
Waiter (Arbitrator) Solution: Use a waiter to control access to chopsticks, ensuring that only a certain number of philosophers can pick up chopsticks at any given time.