Unit 3 - Practice Quiz

Concurrent processes are defined as two or more processes whose execution overlaps in time. They don't have to be running at the exact same instant, but their lifetimes overlap.

Co-operating processes are those that can share data, messages, or other resources, allowing them to influence or be influenced by the execution of other processes.

The critical section is the specific part of a program where shared resources are accessed. Access to this section must be synchronized to prevent data inconsistencies.

Mutual exclusion is the property that ensures if one process is executing in its critical section, no other processes can be executing in their critical sections for the same shared resource.

A semaphore is a synchronization tool that acts as a protected integer variable. It is used to control access to a shared resource by multiple processes.

The wait() operation (or P) decrements the semaphore value, and the signal() operation (or V) increments it. These are the fundamental, indivisible operations used for synchronization.

The Producer-Consumer problem, also known as the bounded-buffer problem, is a canonical example used to illustrate issues and solutions related to process synchronization.

The producer's function is to create items (data) and add them to the shared buffer, which acts as a queue for the consumer process.

The main constraint of the problem is that multiple readers can read the data concurrently, but a writer must have exclusive access to prevent data corruption.

The problem models philosophers who need to acquire two chopsticks (one on their left and one on their right) to eat. The chopsticks represent the shared, limited resources.

Monitors are an abstract data type that encapsulates shared data and the procedures that operate on it, simplifying synchronization by automatically enforcing mutual exclusion.

A fundamental property of a monitor is that it ensures mutual exclusion. Therefore, only one process can be active within the monitor at any time.

The TestAndSet() instruction is an atomic (indivisible) hardware primitive that reads a value from memory and writes a new value in a single, uninterruptible operation, making it useful for building locks.

Peterson's solution is a well-known algorithm that correctly solves the critical-section problem for exactly two concurrent processes using shared memory.

Threads are called lightweight processes because they share the same address space and resources of their parent process, making them less resource-intensive to create and manage than separate processes.

Sharing resources like memory makes communication between threads much faster and more efficient than inter-process communication (IPC), which is a key benefit of multithreading.

The one-to-one model provides a direct mapping between a user thread and a kernel thread. This allows for better concurrency, as a blocking call by one thread does not block others.

Since all user-level threads are mapped to a single kernel thread, if one user thread makes a blocking call, the kernel blocks that single kernel thread, effectively pausing all other user threads in that process.

A precedence graph shows the execution order dependencies between processes or statements. An edge from to means must complete before can begin.

The process that performs the act of creation is termed the 'parent process,' and the newly created process is its 'child process,' forming a hierarchical relationship.

The semaphore S is used as a mutex (initialized to 1), ensuring that the operation count++ is atomic. This prevents race conditions. Since P1 increments the count 5 times and P2 increments it 3 times, and these increments are serialized by the mutex, the final value will be the sum of the increments, which is 0 + 5 + 3 = 8, regardless of the interleaving of the processes.

In Peterson's solution, flag[i] = true signals that process i is ready to enter its critical section. The while (flag[j] && turn == j); loop checks the other process. If both processes set their flags to true at the same time, the turn variable acts as a tie-breaker, allowing only one process to proceed, thus ensuring mutual exclusion while also guaranteeing progress and bounded waiting.

The key advantage of monitors is abstraction. They are a higher-level synchronization construct. Programmers don't need to explicitly code wait() and signal() calls to enforce mutual exclusion for the shared data. The compiler/runtime handles this, reducing the risk of common errors like forgetting to call signal(S) or calling wait(S) twice. Semaphores are more primitive and require careful management by the programmer.

The 'Hold and Wait' condition for deadlock occurs when a process holds at least one resource and is waiting to acquire additional resources held by other processes. By requiring a philosopher to pick up both chopsticks simultaneously (in an atomic operation), we ensure that they never hold one chopstick while waiting for the other. This directly prevents the 'Hold and Wait' condition from occurring.

In a readers-priority solution, as long as at least one reader is active, new incoming readers are allowed to start reading. If there is a continuous stream of readers, a writer might wait indefinitely to acquire the lock, leading to writer starvation. The lock will never be released to a writer if readers keep arriving.

In the many-to-one model, all user-level threads of a process are mapped to a single kernel thread. Since the kernel schedules kernel threads, only one thread from that process can execute at any given moment, regardless of how many CPU cores are available. This prevents true parallelism for that process, making the model inefficient for multi-core systems.

The key feature of TestAndSet() and other hardware primitives is atomicity. The entire operation of reading the target's value, setting the target to TRUE, and returning the old value is performed as a single, indivisible hardware instruction. This prevents any other process from interfering between the 'test' (reading *target) and the 'set' (writing to *target), which is essential for correctly implementing a lock.

The semaphore full tracks the number of slots in the buffer that are filled with items. Initially, the buffer is empty, so full is initialized to 0. The producer signal(full) after adding an item, and the consumer wait(full) before removing an item. Conversely, the semaphore empty is initialized to n and tracks the number of empty slots.

A precedence graph shows the execution dependencies. S2 depends on S1 (b needs a). S4 depends on S2 and S3 (d needs b and c). S5 depends on S4. There is no dependency between S1 (a=1) and S3 (c=3). Therefore, they can be executed in any order relative to each other, or concurrently, before S4 is executed.

The Many-to-Many model (often implemented as a Two-Level model) multiplexes many user-level threads to a smaller or equal number of kernel threads. This model overcomes the limitations of the other two: it allows for true parallelism (unlike many-to-one) and doesn't have the overhead of creating a kernel thread for every user thread (unlike one-to-one). It provides a good compromise, which is why it's the basis for threading libraries in most modern OSes.

Co-operating processes can affect each other's execution. Without synchronization, a race condition can occur. P2 might read the shared memory while P1 is in the middle of writing to it, resulting in a partial or invalid value. Synchronization primitives (like semaphores or mutexes) are needed to enforce an order, ensuring that the read operation happens only after the write operation is complete.

The Bakery algorithm is significant because it solves the critical section problem for n processes using only shared memory that does not require atomic read-modify-write instructions like TestAndSet. While it assumes atomic reads and writes of primitive types (like integers), it does not need a more complex hardware-level atomic primitive. This makes it a pure software solution.

Threads within the same process share most of their resources, including the code segment, data segment (global variables), heap, and operating system resources like open files. However, each thread must have its own separate stack to manage its local variables, function calls, and execution state. This is fundamental to allowing threads to execute independently.

In a common implementation of counting semaphores, the integer value represents the number of available resources. If the value is negative, its magnitude (|-2| = 2) represents the number of processes waiting for the resource. When a new process executes wait(S), it first decrements S (from -2 to -3) and then, because the result is negative, it blocks and is added to the wait queue. There are now 3 processes waiting.

When a process within a monitor calls wait() on a condition variable, it does two things: 1) it suspends its own execution and is placed in the condition variable's wait queue, and 2) it releases the mutual exclusion lock on the monitor. This is crucial because it allows another process to enter the monitor, potentially change the state, and signal the waiting process to continue.

TestAndSet can only set a value to TRUE. CompareAndSwap (CAS) is more general. It checks if the current *value is equal to an expected value. Only if they match does it update *value to new_value. This atomic 'check-then-update' operation can be used to implement not just locks, but also lock-free data structures (like atomic counters or linked-list insertions) by ensuring an update only happens if the state hasn't changed since it was last read.

Scheduler activations act as a bridge for the many-to-many model. When a kernel thread is about to block (e.g., on I/O), the kernel makes an 'upcall' to the user-level thread library via a scheduler activation. This upcall informs the library that a kernel thread is no longer available. The library can then schedule another runnable user thread onto a different available activation (kernel thread), thus preventing the entire process from blocking and maintaining concurrency.

An orphan process is a running process whose parent has terminated. In UNIX-like systems, such processes are 'adopted' by a special system process, typically init (process ID 1), which then becomes their new parent. This ensures the process doesn't remain in the system without a parent to eventually collect its exit status.

This is a key distinction. Concurrency is a logical concept about the structure of a program dealing with multiple tasks at once. It can be implemented on a single CPU core via time-slicing (interleaving). Parallelism is a physical concept where multiple tasks are literally running at the same instant in time, which requires multiple processing units (e.g., CPU cores).

In a single-threaded iterative server, if one client connection involves a long-running task (like a large file download or slow network), the entire server is blocked and cannot accept new connections or service other clients. By dispatching each connection to a separate worker thread, the master thread can immediately go back to listening for new connections. This allows the server to handle many clients concurrently, significantly improving throughput and responsiveness.

1. Initial State: S = 1, x = 0.
2. P2 starts: Executes signal(S). State becomes S = 2, x = 0.
3. P2 continues: Executes x = x * 2. State remains S = 2, x = 0 * 2 = 0.
4. P2 is preempted. Current state: S = 2, x = 0.
5. P1 runs to completion:
   • wait(S): S becomes 1. (S > 0, no block).
   • x = x + 1: x becomes 1.
   • wait(S): S becomes 0. (S > 0, no block).
   • x = x + 5: x becomes 6.
   • signal(S): S becomes 1.
6. P1 completes. Current state: S = 1, x = 6.
7. P2 resumes:
   • signal(S): S becomes 2.
   • x = x - 2: x becomes 6 - 2 = 4.
   • wait(S): S becomes 1. (S > 0, no block).
8. P2 completes. Final state: x = 4.

Under Mesa semantics, signal() moves a waiting thread from the condition queue to the ready queue for the monitor lock, but the signaling thread (T2) retains the lock and continues execution. By the time the waiting thread (T1) reacquires the lock, the state may have been changed by T2 or even another thread that entered the monitor in the interim. Therefore, T1 cannot assume the condition is true. It must re-check the condition, which is why condition waits in Mesa-style monitors are always enclosed in a while loop (e.g., while(!condition) cond.wait();).

This solution correctly prevents deadlock because a philosopher never holds one fork while waiting for another, thus breaking the circular wait condition. Mutual exclusion is maintained. Livelock is not the primary issue. However, starvation is still possible. Consider a scenario where philosopher P2 and P4 are alternatingly eating. Their neighbor, P3, will always find one of its required forks busy whenever it tries to pick them up. If the scheduler consistently favors P2 and P4 over P3, P3 can wait indefinitely (starve) without ever getting a chance to eat.

This scenario describes the classic ABA problem.

1. Thread T1 reads head which points to node B (value A). Let's say its address is 0x100. T1 is preempted.
2. Another thread pops B, pops A, then pushes a new node B' (value A again). B' might be allocated at the same address 0x100.
3. T1 resumes. Its CAS operation compares the current head (0x100) with its old value (0x100). The comparison succeeds.
4. T1 then incorrectly swings the head pointer to its stored next_ptr, which pointed to the original A, corrupting the stack. The CAS succeeds because the values (addresses) are the same (A -> A), but the underlying state they represent has changed (B -> B').

Writer-preference solutions are designed to prevent writers from being starved by a continuous stream of readers. When a writer (W1) is waiting, any newly arriving readers (R2, R3) are blocked. Any newly arriving writers (W2, W3) are queued up. Once the current read operation (R1) is complete, the lock is passed to the waiting writers. The algorithm will ensure that all writers who were waiting when the lock became free are serviced before any of the waiting readers get a chance. Therefore, W1, W2, and W3 will all execute before R2 and R3.

In the many-to-many model, user-level threads need a kernel-level thread to execute on the CPU. When a user thread makes a blocking system call, the kernel thread it is mapped to also blocks in the kernel. If all available kernel threads for that process become blocked, the remaining user-level threads have no available kernel threads to run on. Even if they are ready to run and the user-level scheduler picks one, there is no underlying execution context in the kernel, so they are effectively stalled.

The core innovation of scheduler activations is the bidirectional communication between the kernel and the user-level thread library. A standard kernel provides no information to the user-level scheduler about blocking events. An upcall is a message from the kernel up to the user-level library. It informs the library about an event, such as 'the user thread you were running on kernel thread K just blocked on I/O'. This notification allows the user-level scheduler to intelligently save the context of the blocked thread and schedule a different, ready-to-run user thread onto the now-available execution context (the activation).

Let's trace the dependencies:

1. P1 signals S1 and S3. This allows P2 (waiting on S1) and P4 (waiting on S3) to start.
2. P2 must wait for P1 (wait(S1)). After it runs, it signals S2.
3. P4 must wait for P1 (wait(S3)). After it runs, it signals S4.
4. P3 must wait for both S2 and S4 (wait(S2); wait(S4);).
   This means P3 cannot proceed until P2 has signaled S2 AND P4 has signaled S4. This creates a 'join' point where P3's execution is dependent on prior actions from both P2 and P4.

The flaw is the order of wait(mutex) and wait(empty). Here's the deadlock scenario:

1. The buffer is full. empty semaphore is 0.
2. The producer process runs. It executes wait(mutex), successfully acquiring the lock on the buffer. mutex is now 0.
3. It then executes wait(empty). Since the buffer is full, empty is 0, and the producer process blocks.
4. Crucially, the producer is now blocked while still holding the mutex lock.
5. No consumer can enter its critical section to remove an item from the buffer because it will block on wait(mutex).
6. The producer is waiting for a consumer to signal empty, but no consumer can run to do so. This is a classic deadlock.

The process of picking a ticket number is not atomic. A process first sets choosing[i] = true, then calculates its number, and finally sets choosing[i] = false. If were to read number[j] while is in this critical phase, it might read an old (or zero) value for number[j] and incorrectly assume it has priority. The while (choosing[j]) loop forces to wait until has finished picking and writing its new ticket number, ensuring that makes its decision based on up-to-date information, thus preventing a violation of mutual exclusion.

In many common implementations of counting semaphores, the integer value has a specific meaning. If the value is positive, it represents the number of available resources or signal calls that can be absorbed by wait calls without blocking. If the value is zero, no resources are available. If the value is negative, its absolute value represents the number of processes that are currently blocked on that semaphore's wait queue. Therefore, a value of -4 means exactly four processes are blocked, waiting for signal(S) to be called.

In a non-preemptive uniprocessor system, a process runs until it voluntarily yields the CPU (e.g., for I/O) or terminates. It cannot be forcibly interrupted by the scheduler to run another user process. Therefore, if a process enters its critical section, it is guaranteed to finish it without another user process interfering. However, hardware interrupts can still occur at any time. If an interrupt service routine (ISR) accesses the same shared data as the user process, a race condition can still exist between the process and the ISR. So, mutual exclusion is solved at the process level but not globally.

This question tests the understanding that file descriptors are private to each process. Each process has its own file descriptor table. The integer 5 is just an index into this table. The parent's fd=5 points to a kernel file table entry for its file. The child's fd=5 points to a completely different kernel file table entry for its file. The two are independent. The child's actions (opening, using, or closing its fd=5) have no effect on the parent's fd=5. Therefore, the parent's write operation proceeds as normal.

Under Hoare semantics, cond.signal() immediately transfers the monitor lock and CPU control to a waiting thread. The signaling thread is suspended. When the awakened thread finishes its work and exits the monitor (or waits again), it must return the lock and control back to the original signaling thread so it can continue its work. This results in two context switches. A common optimization pattern (signal-and-exit) is for the signaler to perform the signal as its very last action, which allows the awakened thread to proceed without needing to switch back to the now-finished signaler, saving a context switch.

A simple TestAndSet lock continuously performs an atomic write operation. In a cache-coherent system, each write attempt invalidates the cache line holding the lock in all other cores' caches, causing a storm of traffic on the bus. TTAS improves this by first spinning in a tight loop that only reads the lock's value (the first 'Test'). A read can be satisfied by a local cache copy without generating bus traffic. Only when the read shows the lock is free does the process attempt the expensive atomic TestAndSet write operation. This drastically reduces bus contention.

Creating and destroying threads, especially kernel-level threads, are expensive operations. They involve significant overhead in allocating kernel memory (for the stack and TCB), interacting with the scheduler, and cleanup. For a server handling many short-lived requests, this overhead can become the main performance bottleneck. A thread pool pre-allocates a fixed number of worker threads. When a request arrives, it is dispatched to an idle thread from the pool. When the request is complete, the thread is returned to the pool, ready for the next request. This re-use of threads amortizes the creation cost, leading to much better throughput and lower latency.

1. signal(S0) starts the system. P1 runs, prints "A", and signals S1 and S2.
2. P2 and P3 are now unblocked. They can run in any order.
3. P2 runs, waits on S1, prints "B", and then signals S0. This allows P1 to run again, creating an 'AB' cycle.
4. P3 runs, waits on S2, and prints "C". After printing, it loops back and immediately waits on S2 again.
5. The crucial flaw is that no process ever signals S2 a second time. P1 signals it once at the beginning. After P3 consumes that signal, S2 will remain 0 forever. Therefore, P3 will print "C" once and then block permanently on its second wait(S2) call. The P1-P2 interaction can continue, producing a sequence of 'A's and 'B's.

The 'Progress' principle states that if no process is in its critical section and some processes wish to enter, the selection of the next process cannot be postponed indefinitely. In this strict alternation scheme, the processes are tightly coupled. If turn is 2, P1 is blocked, waiting for P2 to run, enter its critical section, and set turn to 1. If process P2 is currently in its non-critical remainder section and has no desire to enter its critical section, P1 is blocked unnecessarily. The decision to let P1 proceed is dependent on the unrelated activity of P2, which violates progress.

When philosopher i puts down their forks, they change their state from EATING to THINKING. This action is a state change that could resolve the waiting condition for a neighbor. For example, philosopher i-1 might have been in the HUNGRY state, waiting for philosopher i to finish. By calling test() on its neighbors, the putdown operation proactively checks if the resource release has enabled any neighbor to proceed. If a neighbor can now eat, the test function will signal them, waking them up and allowing them to acquire the forks.

1. flag[0]=false, flag[1]=false.
2. P0 executes while(flag[1]). The condition is false.
3. P0 is preempted before it can set flag[0]=true.
4. P1 runs. It executes while(flag[0]) (false), enters its critical section. But it hasn't set its flag yet. This is not the standard faulty algorithm. The question's algorithm is set flag, then check. Let's re-trace THAT one:
5. flag[0]=false, flag[1]=false.
6. P0 sets flag[0] = true.
7. P0 is preempted.
8. P1 sets flag[1] = true.
9. P1 checks while(flag[0]). It's true. P1 spins.
10. P0 checks flag[1] (false). Is preempted.
11. P1 checks flag[0] (false). Enters CS.
12. P0 resumes, also enters CS. Mutual Exclusion violation. The provided option perfectly describes the interleaving for a check-then-set algorithm. Given the choices, this is the intended answer, pointing out a classic software synchronization bug. Let's assume the prompt's flag[i]=true; while(flag[j]) is flawed and the provided answer points to the correct failure trace for such algorithms in general. The turn variable in Peterson's solution is what solves this race.