(NOT ON EXAM) OS CH6 - Process Synchronization

What is process synchronization?

Mechanisms to coordinate processes/threads to ensure orderly and safe access to shared resources, preventing race conditions.

Define critical section.

A code segment where shared resources are accessed, requiring mutual exclusion to prevent concurrent execution.

What is a race condition?

An unpredictable outcome caused by unsynchronized concurrent access to shared data (e.g., two threads modifying a counter).

Define mutual exclusion.

Ensuring only one process/thread executes in its critical section at a time.

What is Peterson's Solution?

A software-based algorithm for mutual exclusion between two processes using turn and flag[2] variables.

How does test_and_set work?

An atomic hardware instruction that sets a boolean to true and returns its previous value. Used for spinlocks.

Define compare_and_swap.

An atomic instruction that updates a value to new_value only if it matches expected, returning the original value.

What is a spinlock?

A mutex lock where threads busy-wait (loop) until the lock becomes available.

Define binary semaphore.

A semaphore with values 0 (locked) or 1 (unlocked), used for mutual exclusion.

What is a monitor?

A high-level synchronization construct that encapsulates shared data and procedures, ensuring only one thread executes within it at a time.

Define condition variable.

A mechanism in monitors allowing threads to wait (wait()) or signal (signal()) changes in state (e.g., resource availability).

What is priority inversion?

A lower-priority process blocks a higher-priority process by holding a shared resource. Solved via priority inheritance.

Describe the bounded-buffer problem.

Producers and consumers share a fixed-size buffer; synchronization ensures producers don't overflow and consumers don't underflow.

What is the readers-writers problem?

Managing concurrent access where multiple readers can read shared data simultaneously, but writers require exclusive access.

Define the Dining Philosophers Problem.

Philosophers sharing chopsticks (resources) may deadlock if all pick up one chopstick simultaneously.

What is deadlock?

Two or more processes wait indefinitely for each other to release resources (e.g., circular dependency).

Define starvation.

A process is indefinitely denied access to a resource due to unfair scheduling.

What is an atomic operation?

An operation that executes completely without interruption (e.g., test_and_set).

What is an adaptive mutex?

A lock in Solaris that spins if the holder is running on another CPU or blocks if the holder is inactive.

Define dispatcher objects.

Windows synchronization tools (e.g., mutexes, semaphores) that block threads in non-signaled state.

How are semaphores used in the bounded-buffer problem?

- mutex (1): Ensures mutual exclusion.
- full (0): Counts filled slots.
- empty (n): Counts empty slots.

Explain the semaphore use in readers-writers.

- rw_mutex (1): Protects writers.
- mutex (1): Protects read_count.
- read_count: Tracks active readers; first reader locks rw_mutex, last unlocks it.

How to prevent deadlock in Dining Philosophers?

1. Allow ≤4 philosophers at the table.
2. Use asymmetric picking (odd: left→right; even: right→left).
3. Acquire both chopsticks atomically.

How do monitors differ from semaphores?

Monitors encapsulate synchronization logic within an ADT, while semaphores require manual wait()/signal() calls.

How does priority inheritance resolve priority inversion?

The lower-priority process temporarily inherits the priority of the blocked higher-priority process.

Write pseudocode for a mutex lock using test_and_set.

do {
while (test_and_set(&lock)) ;
// Critical section
lock = false;
} while (true);

How is a semaphore implemented with blocking?

Use a waiting queue. wait() decrements value; if negative, block. signal() increments; if ≤0, wake a thread.

How does Linux handle synchronization in kernel 2.6+?

Uses preemptive kernel with spinlocks, semaphores, and atomic integers. Replaces spinlocks with preemption control on single-CPU.

What is the role of pthread_cond_wait()?

Blocks a thread until a condition is signaled, releasing the associated mutex atomically.

How does transactional memory work?

Groups memory operations into atomic transactions; if conflicts occur, the transaction aborts and retries.

Write an OpenMP directive to protect a critical section.

#pragma omp critical
{
// Critical section code
}

Why do functional languages reduce race conditions?

Variables are immutable; no shared state to modify concurrently (e.g., Erlang uses message passing).

What are turnstiles in Solaris?

Queues for threads waiting on locks. Implements priority inheritance to resolve inversion.

When does Windows use spinlocks?

On multiprocessor systems for short critical sections; avoids context-switching overhead.

What is atomic_t in Linux?

A data type for atomic operations (e.g., increment/decrement) without locking.

How can writers starve in readers-writers?

If readers continuously arrive, writers may never get access. Solutions include writer priority.

Compare monitor signaling strategies.

- Signal-and-Wait: Signaler waits until signaled thread exits.
- Signal-and-Continue: Signaler proceeds immediately.

List the three requirements for solving the critical-section problem.

Mutual exclusion, progress, bounded waiting.

How to initialize semaphores for the bounded-buffer problem?

- mutex = 1 (mutual exclusion).
- full = 0 (initial filled slots).
- empty = N (buffer size).

Are mutexes and binary semaphores interchangeable?

No. Mutexes include ownership (only the locking thread can unlock), while semaphores lack this.

Provide a semaphore deadlock example.

Process 1: wait(A); wait(B);
Process 2: wait(B); wait(A);

How is mutual exclusion enforced in monitors?

Only one thread can execute inside the monitor at a time; others queue at the entry.

What happens during x.wait() in a monitor?

The thread releases the monitor lock, blocks, and re-acquires the lock upon waking.

How does the ResourceAllocator monitor work?

Uses busy flag and x.wait(time) to prioritize resource requests based on time.

How is priority scheduling implemented in monitors?

Using x.wait(c) with priority number c; the lowest c (highest priority) resumes first.

How does Linux handle preemption in critical sections?

Disables kernel preemption during critical sections to prevent race conditions.

How does Java implement monitors?

Using synchronized methods/blocks, which enforce mutual exclusion and use wait()/notify().

What does a semaphore's negative value mean?

The magnitude indicates the number of blocked threads in the waiting queue.

How does the bounded-waiting solution using test_and_set work?

Uses waiting[i] flags and cyclic scanning to ensure no thread waits indefinitely.

How does OpenMP handle parallel execution?

Splits loop iterations across threads using #pragma omp parallel for, managed by the runtime.