Synchronization and Semaphores Lecture Notes

Comprehensive practice questions covering thread synchronization, race conditions, atomic operations, and semaphore implementations based on the week eight lecture.

What is the primary objective of synchronization in multi-threaded programming?

To manage communication between multiple threads and coordinate their activities so they do not interfere with each other.

According to the lecture, what are the key topics for assignment two and assignment three?

Assignment two focuses on processes, fork, and exec, while assignment three requires knowledge of networking, threading, and semaphores.

When is assignment two due?

3 PM, Thursday, May 7.

Why did the program $race1.c$ fail to reach the expected total of $1,200,000$ increments?

The increment operation was not atomic, meaning multiple threads performed a read-modify-write cycle simultaneously, overwriting each other's work.

What does it mean for an operation to be "atomic"?

The operation is indivisible and cannot be broken down into smaller pieces or interrupted halfway through.

Approximately how many x86 assembly instructions are generated for a pointer dereference increment operation like $*p++$?

Five assembly language instructions.

Why did the custom lock implementation in $race2.c$ fail to prevent race conditions?

The process of taking the lock was itself non-atomic; multiple threads could simultaneously see the lock was zero and attempt to grab it at the same time.

What are the two main issues identified with the $race2.c$ program?

It failed to ensure mutual exclusion and it utilized inefficient busy waiting.

What is "busy waiting"?

A technique where a thread uses CPU time to repeatedly check a condition in a loop without adding value to the program.

Name a software-only algorithm mentioned for achieving mutual exclusion.

Peterson's algorithm.

What is a semaphore?

An opaque type, essentially an integer, that supports atomic weight and post operations for synchronization.

Describe the atomic behavior of the $semWait$ operation.

If the semaphore value is greater than zero, it is decremented by one; if the value is zero, the thread is suspended until the value becomes greater than zero.

What happens when $semPost$ is called while multiple threads are waiting on a semaphore with a value of zero?

The semaphore value is incremented by one, and only one of the waiting threads is unblocked.

What is "starvation" in the context of semaphores?

A scenario where a thread never gets a turn to access a resource because other threads are always prioritized by the operating system.

In the function $sem\_init(sem\_t *sem, int pshared, unsigned int value)$, what does the $pshared$ argument indicate?

If set to zero, the semaphore is shared between threads of a single process; if nonzero, it is shared between processes and must reside in shared memory.

Why might a program using semaphores like $race3.c$ run slower than a version without synchronization?

Making system calls like $sem\_wait$ and $sem\_post$ is expensive; the lecture noted over two seconds of CPU time were spent on $1,200,000$ such operations.

What is the restriction regarding passing semaphores between functions?

Semaphores are tied to their memory address and cannot be copied; you must pass the address of the semaphore instead.

Explain the Producer-Consumer pattern using semaphores.

The consumer starts with a semaphore at value zero and blocks on $semWait$, while the producer performs its task and then calls $semPost$ to unblock the consumer.

How can semaphores be used to limit the maximum number of active threads?

Initialize the semaphore to the maximum allowed number; each spawning thread calls $semWait$ before creation, and each exiting thread calls $semPost$.

What was the most efficient solution presented in $race3a.c$ to avoid race conditions and synchronization overhead?

Designing tasks to be independent by giving every thread its own counter and summing them only at the very end.

Describe the "Dining Philosophers" problem.

A classic deadlock scenario where philosophers sitting at a round table each need two forks to eat, but each only has access to one fork to their left and one to their right.

What is the difference between deadlock and livelock?

Deadlock is when threads are blocked waiting for something that will never happen; livelock is when threads are busy trying to recover from a situation but are not accomplishing any useful work.

What is a simple way to avoid deadlock when multiple resources are required?

Ensure that every thread requests the necessary resources in the same predefined order.

How does $sem\_trywait$ differ from $sem\_wait$?

$sem\_trywait$ does not block the thread; if the resource is unavailable, it returns an error code immediately.

What is unique about the timeout provided to $sem\_timedwait$?

It must be an absolute time (a specific timestamp) rather than a relative duration of time.

What is a named semaphore?

A semaphore that can be used between processes by utilizing the file system via $sem\_open$, rather than shared memory.

What is the purpose of a $pthread\_rwlock\_t$ (Read-Write Lock)?

It allows multiple threads to read shared memory simultaneously while ensuring only one writer can access the memory at a time.

What is a condition variable ($pthread\_cond\_t$) used for?

It is used for waiting for a specific condition to occur, such as a variable changing value, without busy waiting.