Synchronization

What is process synchronization?

Coordinating concurrent processes so they access shared resources correctly and in an appropriate order.

Why is process synchronization needed?

To ensure correct results when processes share resources and to help the system use CPU time efficiently.

What is a shared resource?

A resource that can be accessed or used by multiple processes, such as data, a file, or a printer.

Why can concurrent access to shared resources be dangerous?

Processes may interfere with one another, corrupt data, or produce incorrect output.

How does process synchronization differ from interprocess communication (IPC)?

IPC helps processes exchange information; synchronization coordinates their access to resources and the order in which operations occur.

What is a race condition?

A situation in which the correctness of the outcome depends on how the steps of concurrent processes are interleaved.

Why are race conditions difficult to debug?

They may occur infrequently and can be difficult to reproduce because they depend on execution timing.

What is interleaved execution?

Execution in which steps from different processes occur in an alternating or mixed order.

Why is x = x + 1 not necessarily an atomic operation?

It may involve multiple machine instructions, such as reading x, incrementing a register, and writing the result back.

What does atomic mean in synchronization?

An operation appears to happen indivisibly, without another process observing or interfering with its intermediate steps.

What can happen when two processes increment the same shared variable without synchronization?

Both may read the same old value and overwrite one another's updates, causing lost increments.

What is mutual exclusion?

A property that ensures only one process at a time enters a protected critical section for a shared resource.

What is a critical section?

A section of code that accesses or modifies shared data and must be executed under appropriate synchronization.

What is a lock?

A synchronization mechanism that allows a process to execute a critical section in isolation from other processes using the same lock.

What are the two basic lock operations?

Acquire and release.

What does acquire lock do?

It obtains the lock if it is available; otherwise, the process must wait until it can obtain the lock.

What does release lock do?

It releases the lock so another process can acquire it.

Where should lock acquisition and release occur around a critical section?

Acquire the lock before entering the critical section and release it after leaving the critical section.

What is one advantage of locks?

They are relatively easy to use to protect shared data and manage concurrency.

What are disadvantages of locks?

They can reduce performance by serializing critical sections and can contribute to deadlocks.

What is deadlock?

A situation in which processes are stuck waiting for one another or for resources, so the required progress cannot occur.

What is livelock?

A situation in which processes continue executing steps but make no useful progress.

How does deadlock differ from livelock?

In deadlock, processes are stuck waiting; in livelock, processes remain active but repeatedly fail to make progress.

What is the dining philosophers problem?

A synchronization problem in which five philosophers share chopsticks, and each needs both neighboring chopsticks to eat.

What are the rules of the dining philosophers problem?

Each philosopher alternates between thinking and eating, uses only the two neighboring chopsticks, and each chopstick can be used by at most one philosopher at a time.

Why is the dining philosophers problem useful?

It illustrates how processes competing for multiple shared resources can experience deadlock, starvation, or limited concurrency.

What is the first lock-based solution to the dining philosophers problem in the slides?

Protect all chopsticks with a single lock so only one philosopher can use chopsticks at a time.

What is the disadvantage of using one global lock in the dining philosophers problem?

It prevents neighboring philosophers from interfering, but also prevents non-neighboring philosophers from eating concurrently.

What is a deadlock-prone solution to the dining philosophers problem?

Each philosopher independently acquires one chopstick and then waits for the other, allowing a circular wait.

How can deadlock be avoided in the dining philosophers problem by breaking symmetry?

Have one philosopher acquire the chopsticks in the opposite order from the others.

What is mutual exclusion in the dining philosophers problem?

No two neighboring philosophers may eat at the same time because they share a chopstick.

What is starvation freedom?

Every process that continues requesting a resource eventually gets an opportunity to proceed.

How does starvation freedom differ from deadlock freedom?

Starvation freedom requires every hungry process eventually to eat; deadlock freedom only requires that some hungry process can eventually eat.

What is concurrency in the dining philosophers problem?

Allowing multiple non-neighboring philosophers to eat at the same time when their resource needs do not conflict.

What is the producer-consumer problem?

A synchronization problem in which producers create items and consumers remove or use those items through a shared buffer.

What is the producer's role?

Create items and place them in the shared buffer.

What is the consumer's role?

Remove items from the shared buffer and consume or use them.

Why is a buffer useful in the producer-consumer problem?

It stores items temporarily and helps accommodate differences in producer and consumer speeds.

What happens if the producer is faster than the consumer?

Items accumulate in the buffer, which can become full.

What happens if the consumer is faster than the producer?

The consumer may find the buffer empty and must wait for an item.

What is a bounded buffer?

A shared buffer with a fixed maximum capacity.

What is one difference between array-based and linked-list-based buffers?

An array-based buffer has a fixed size; a linked-list-based buffer can grow dynamically, subject to available resources.

Why must access to a shared buffer be synchronized?

Concurrent modifications can corrupt the buffer or cause incorrect insertions and removals.

What is the purpose of a mutex in a producer-consumer solution?

It provides mutual exclusion when a process accesses or modifies the shared buffer.

Why can checking buffer availability and then acquiring a lock be unsafe?

Another process may change the buffer state between the check and the operation, creating a time-of-check-to-time-of-use (TOCTOU) bug.

What does TOCTOU stand for?

Time of check to time of use.

What is a TOCTOU bug?

A bug in which a condition changes after it is checked but before the program uses that condition to perform an operation.

Why can a solution that works with one producer and one consumer fail with multiple producers or consumers?

Multiple processes may race between checking a condition and modifying the shared state, so the check and action are not safely coordinated.

What synchronization features are needed for a robust bounded-buffer solution?

Mutual exclusion for the buffer and conditional synchronization to wait when the buffer is full or empty.

What is a semaphore?

A synchronization primitive associated with an integer counter and operations that allow processes to coordinate access to resources.

Who proposed semaphores, and when?

Edsger Dijkstra proposed them in 1962.

What are the two classic semaphore operations?

P and V.

What does P(s) do in the semaphore model presented in the slides?

It decrements the semaphore value and blocks the invoking process if the resulting value is negative.

What does V(s) do in the semaphore model presented in the slides?

It increments the semaphore value and can wake a process waiting on the semaphore.

What are alternative names for P and V?

P is also called wait or down; V is also called signal or up.

Why should a semaphore's value be manipulated only through P and V?

The operations preserve the synchronization rules and prevent processes from bypassing the semaphore's coordination mechanism.

How can a lock be implemented using a semaphore?

Initialize a semaphore to 1, use P to acquire the lock, and use V to release it.

How do locks and semaphores differ?

A lock primarily provides mutual exclusion; a semaphore can provide mutual exclusion and coordinate access to a limited number of resources or signal conditions.

What is a counting semaphore?

A semaphore whose integer value tracks available units of a resource or permits.

What is a binary semaphore?

A semaphore whose state is represented by a Boolean value, typically used to represent two states such as available and unavailable.

Do counting and binary semaphores have the same synchronization power in the slides?

Yes. The slides demonstrate that either type can be implemented using the other.

What is the purpose of the mutex semaphore in the producer-consumer solution?

It ensures that only one process at a time manipulates the shared buffer.

In a bounded-buffer semaphore solution, what does vacant represent?

The number of empty buffer slots.

In a bounded-buffer semaphore solution, what does filled represent?

The number of occupied buffer slots.

If a buffer has capacity N, what is the initial value of vacant?

N, because all buffer slots are initially empty.

If a buffer starts empty, what is the initial value of filled?

0, because there are no items in the buffer.

How does a producer use vacant and filled semaphores?

It waits for a vacant slot, inserts an item under mutual exclusion, then signals that a slot is filled.

How does a consumer use vacant and filled semaphores?

It waits for a filled slot, removes an item under mutual exclusion, then signals that a slot is vacant.

What is a monitor?

A synchronization construct that encapsulates shared data and the operations used to access or modify it.

How does a monitor provide mutual exclusion?

Only one process at a time can execute an operation inside the monitor.

What are two important features of monitors?

They provide implicit mutual exclusion and explicit signaling through condition variables.

Why can monitors be easier to use than semaphores?

They encapsulate shared data and synchronization operations in one construct, reducing the need to manage synchronization separately.

What is a condition variable?

A monitor mechanism that lets a process wait for a condition to become true and lets another process signal that condition.

What does wait do on a condition variable?

It blocks the invoking process and releases control of the monitor so another process can enter.

What does signal do on a condition variable?

It wakes one process waiting on that condition variable, if one exists.

Why must a process release the monitor when it waits on a condition variable?

Otherwise, another process could not enter the monitor to change the state and signal the waiting process.

Why should item generation or consumption usually occur outside the monitor?

Performing lengthy work inside the monitor would unnecessarily prevent other producers or consumers from entering and reduce concurrency.

Why do monitor solutions often use while instead of if when checking a condition?

After waking, a process must recheck the condition because the required state may no longer hold.

What are the two condition variables commonly used in a monitor-based producer-consumer solution?

notFull and notEmpty.

What does notFull represent in a producer-consumer monitor?

The condition that the buffer has space for another item.

What does notEmpty represent in a producer-consumer monitor?

The condition that the buffer contains at least one item to remove.

What is Peterson's algorithm?

A software algorithm for implementing mutual exclusion between two processes using shared variables and simple read and write operations.

How many processes does the original Peterson's algorithm support?

Two processes.

What shared variables does Peterson's algorithm use?

An array of flags indicating each process's intent to enter and a turn variable that resolves contention.

What does flag[i] mean in Peterson's algorithm?

Process i is indicating that it wants to enter the critical section.

What is the purpose of the turn variable in Peterson's algorithm?

It helps resolve simultaneous requests by giving one process priority when both want to enter.

What properties does the correct Peterson's algorithm satisfy in the slides?

Mutual exclusion and starvation freedom.

Why are the earlier attempts at Peterson's algorithm insufficient?

Using only intent flags can cause deadlock; using only a turn variable can allow both processes to enter the critical section.

How can Peterson's algorithm be extended to more than two processes in the slides?

Use a tournament tree in which each internal node contains a Peterson lock and each process is assigned to a leaf.

What is a read-modify-write (RMW) instruction?

A hardware-supported operation that reads a memory location and modifies it as one indivisible operation.

Why are special machine instructions useful for synchronization?

They provide atomic operations that help implement locks correctly under concurrent execution.

What is Test-And-Set (TAS)?

An atomic instruction that sets a memory location to true and returns its previous value.

How can Test-And-Set implement a lock?

A process repeatedly applies TAS to the lock until it observes that the lock was previously free and successfully acquires it.

What is busy waiting or spinning?

Repeatedly checking a condition in a loop while waiting for it to become true.

What is Fetch-And-Increment (FAI)?

An atomic instruction that increments a memory location and returns its previous value.

How can Fetch-And-Increment be used to implement a lock?

Processes obtain ticket numbers atomically and wait until the turn variable matches their ticket.

What is the purpose of a ticket-based lock?

It provides an ordered way for processes to wait for their turn to enter the critical section.

What is the main difference between Peterson's algorithm and RMW-based synchronization?

Peterson's algorithm uses software coordination with shared reads and writes; RMW-based approaches rely on special atomic hardware instructions.

What does it mean for counting and binary semaphores to have equivalent synchronization power?

Each type can be implemented using the other without losing the synchronization capabilities represented in the slides.

Why must semaphore implementations using other semaphores protect their internal state?

Concurrent P and V operations must not corrupt the counter or cause incorrect wakeups and blocking behavior.