Chapter 6: Synchronization (2)

Question 1

What issue can arise from the concurrent or parallel execution of processes that share data?

Answer 1

It can contribute to issues involving the integrity of the shared data.

Question 2

In the bounded-buffer problem, what integer variable can be added to track the number of items in the buffer?

Answer 2

An integer variable, count, initialized to 0.

Question 3

In the shared circular buffer implementation, what does the in pointer indicate?

Answer 3

The in pointer indicates the next free position in the buffer.

Question 4

In the shared circular buffer implementation, what does the out pointer indicate?

Answer 4

The out pointer indicates the position of the earliest item in the buffer.

Question 5

What condition signifies that the shared bounded buffer is empty?

Answer 5

The buffer is empty when count == 0.

Question 6

What condition signifies that the shared bounded buffer is full?

Answer 6

The buffer is full when count == BUFFER_SIZE.

Question 7

In the producer process code, what is the purpose of the statement while (count == BUFFER_SIZE);?

Answer 7

It forces the producer to wait, doing nothing, until there is free space in the buffer.

Question 8

After placing a new item in the buffer, what two variables does the producer process update?

Answer 8

The producer updates the in pointer and increments the count variable.

Question 9

In the consumer process code, what is the purpose of the statement while (count == 0);?

Answer 9

It forces the consumer to wait, doing nothing, until an item is available in the buffer.

Question 10

After consuming an item from the buffer, what two variables does the consumer process update?

Answer 10

The consumer updates the out pointer and decrements the count variable.

Question 11

If count is 5, and a producer executes count++ concurrently with a consumer executing count--, what are the three possible resulting values for count?

Answer 11

The value of count may be 4, 5, or 6.

Question 12

Following the concurrent execution of count++ and count-- when count was initially 5, what is the only correct final value for count?

Answer 12

The only correct result is count == 5.

Question 13

The high-level instruction count++ could be implemented in machine language as a sequence of what three operations?

Answer 13

1. Load count into a register. 2. Increment the register. 3. Store the register’s value back into count.

Question 14

A situation where multiple processes manipulate the same data concurrently and the outcome depends on the order of access is called a _____.

Answer 14

race condition

Question 15

How can the race condition on the count variable be prevented?

Answer 15

By ensuring that only one process can manipulate the variable count at a time through synchronization.

Question 16

What is the term for the segment of code in a process that accesses and updates data shared with other processes?

Answer 16

A critical section.

Question 17

What is the key feature of a system regarding critical sections?

Answer 17

When one process is executing in its critical section, no other process is allowed to execute in its critical section.

Question 18

What is the goal of the critical-section problem?

Answer 18

To design a protocol that processes can use to synchronize their activity and cooperatively share data.

Question 19

What is the name of the code section where a process requests permission to enter its critical section?

Answer 19

The entry section.

Question 20

In the general structure of a process, what section may follow the critical section?

Answer 20

The exit section.

Question 21

What is the term for the code of a process that is not the entry, critical, or exit section?

Answer 21

The remainder section.

Question 22

A solution to the critical-section problem must satisfy what three requirements?

Answer 22

Mutual exclusion, progress, and bounded waiting.

Question 23

Define the ‘Mutual Exclusion’ requirement for a critical-section solution.

Answer 23

If a process is running in its critical section, then no other processes can be running in their critical sections.

Question 24

Define the ‘Progress’ requirement for a critical-section solution.

Answer 24

If no process is in its critical section and some wish to enter, the selection of the next process cannot be postponed indefinitely.

Question 25

Define the 'Bounded Waiting' requirement for a critical-section solution.

Answer 25

There must be a limit on the number of times other processes can enter their critical sections after a process has requested entry.

Question 26

In a single-processor environment, what simple method could solve the critical-section problem?

Answer 26

Preventing interrupts from occurring while a shared variable was being modified.

Question 27

Why is disabling interrupts not a feasible solution to the critical-section problem on multiprocessor systems?

Answer 27

It is time-consuming, as the message to disable interrupts must be passed to all processors.

Question 28

Peterson's solution is a classic software-based solution to the critical-section problem for how many processes?

Answer 28

It is restricted to two processes.

Question 29

Peterson's solution requires two processes to share what two data items?

Answer 29

An integer `turn` and a boolean array `flag[2]`.

Question 30

In Peterson's solution, what does the variable `turn` indicate?

Answer 30

It indicates whose turn it is to enter its critical section.

Question 31

In Peterson's solution, what does the `flag` array indicate?

Answer 31

The `flag` array indicates if a process is ready to enter its critical section.

Question 32

In the entry section of Peterson's solution for process $P_i$, what are the first two actions taken?

Answer 32

First, it sets `flag[i] = true`, and then it sets `turn = j` (where j is the other process).

Question 33

In Peterson's solution, what is the condition in the `while` loop that forces process $P_i$ to wait?

Answer 33

The process waits while `flag[j] && turn == j`.

Question 34

What action does a process take in the exit section of Peterson's solution?

Answer 34

It sets its own flag to false (e.g., `flag[i] = false`).

Question 35

In Peterson's solution, if both processes try to enter their critical section at the same time, what determines which one goes first?

Answer 35

The eventual value of the `turn` variable, determined by which process's assignment to `turn` happens last.

Question 36

What is the primary reason Peterson's solution is not guaranteed to work on modern computer architectures?

Answer 36

Processors and/or compilers may reorder read and write operations that have no dependencies to improve performance.

Question 37

For a multi-process application with shared data, what is a potential negative consequence of instruction reordering?

Answer 37

The reordering of instructions may lead to inconsistent or unexpected results.

Question 38

In the example with shared variables `flag` and `x`, how could instruction reordering cause Process 1 to print 0 instead of 100?

Answer 38

The processor could reorder Process 2's instructions, setting `flag = true` before executing `x = 100`.

Question 39

How can instruction reordering specifically break Peterson's solution?

Answer 39

If the assignments to `flag[i]` and `turn` in the entry section are reordered.

Question 40

What is the critical consequence if instruction reordering breaks Peterson's solution?

Answer 40

It is possible that both processes may be active in their critical sections at the same time, violating mutual exclusion.

Question 41

FREE CARD DIVIDER (start of 6.2)

Question 42

Peterson's solution is not guaranteed to work with modern computer _____.

Answer 42

architectures

Question 43

What can be utilized at a low level to solve the critical-section problem on modern systems?

Answer 43

Hardware support.

Question 44

What are the three forms of hardware solutions mentioned for solving the critical-section problem?

Answer 44

Memory barriers, hardware instructions, and atomic variables.

Question 45

One form of hardware support for synchronization involves creating _____ to ensure memory visibility between processors.

Answer 45

memory barriers

Question 46

A second form of hardware support for synchronization provides special _____ that execute as a single, uninterruptible operation.

Answer 46

hardware instructions

Question 47

A third form of hardware support for synchronization, _____, ensures that operations like increments and decrements are performed without interruption.

Answer 47

atomic variables

Question 48

What are two ways that hardware-level synchronization solutions can be utilized?

Answer 48

They can be used directly as tools or as a foundation for more abstract synchronization mechanisms.

Question 49

Why are hardware-based solutions to the critical-section problem generally inaccessible to application programmers?

Answer 49

Because they are complicated to use correctly.

Question 50

Who typically builds higher-level software tools to solve the critical-section problem for application programmers?

Answer 50

Operating-system designers.

Question 51

What is considered the simplest of the higher-level software tools for solving the critical-section problem?

Answer 51

The mutex lock.

Question 52

The term 'mutex' is short for what phrase?

Answer 52

Mutual exclusion.

Question 53

What is the primary function of a mutex lock?

Answer 53

To protect critical sections and thus prevent race conditions.

Question 54

What must a process do before entering a critical section when using a mutex lock?

Answer 54

It must acquire the lock.

Question 55

What must a process do when it exits a critical section protected by a mutex lock?

Answer 55

It must release the lock.

Question 56

The function that obtains a mutex lock is typically called _____.

Answer 56

acquire()

Question 57

The function that lets go of a mutex lock is typically called _____.

Answer 57

release()

Question 58

A simple mutex lock implementation uses a boolean variable, often named _____, to indicate if the lock is free.

Answer 58

available

Question 59

What is the result of a process calling `acquire()` on a mutex lock that is currently available?

Answer 59

The call succeeds, and the lock is then considered unavailable.

Question 60

What happens to a process that attempts to acquire a mutex lock that is already held by another process?

Answer 60

The process is blocked until the lock is released.

Question 61

The implementation of the `acquire()` and `release()` functions for a mutex lock must be performed as an _____ unit.

Answer 61

atomic (or uninterruptible)

Question 62

How can the atomicity required for `acquire()` and `release()` operations be achieved?

Answer 62

It can be achieved via hardware support.

Question 63

In the simple implementation `acquire() { while (!available) ; available = false; }`, what is the purpose of the `while` loop?

Answer 63

To wait until the lock becomes available (busy waiting).

Question 64

What is the primary action of the simple `release()` function?

Answer 64

It sets the `available` variable to true.

Question 65

What is the main disadvantage of a mutex lock implementation that uses a `while (!available)` loop?

Answer 65

It requires busy waiting.

Question 66

When one process is in its critical section, any other process trying to enter must loop continuously in the call to `acquire()`. This is known as _____.

Answer 66

busy waiting

Question 67

Why is busy waiting particularly problematic in a single-core multiprogramming system?

Answer 67

It wastes CPU cycles that another process could have used productively.

Question 68

What is the term for a mutex lock where a process 'spins' in a loop while waiting for the lock to become available?

Answer 68

A spinlock.

Question 69

What is the primary advantage of a spinlock over a locking mechanism that blocks processes?

Answer 69

No context switch is required when a process must wait on a lock.

Question 70

Why is avoiding a context switch sometimes advantageous?

Answer 70

Because a context switch may take a considerable amount of time.

Question 71

On what type of systems are spinlocks considered a preferred choice for locking under certain circumstances?

Answer 71

On multicore systems.

Question 72

Under what condition is a spinlock particularly effective on a multicore system?

Answer 72

When a lock is expected to be held for only a short duration.

Question 73

Where are spinlocks widely used in modern computing?

Answer 73

In many operating systems on modern multicore computing systems.

Question 74

What more robust synchronization tool can behave like a mutex lock but also provide more sophisticated synchronization?

Answer 74

A semaphore.

Question 75

A semaphore is an integer variable that is accessed only through what two atomic operations, apart from initialization?

Answer 75

wait() and signal().

Question 76

The semaphore operation `wait(S)` decrements the semaphore S, but only after ensuring that _____.

Answer 76

S is greater than 0

Question 77

The semaphore operation `signal(S)` performs what action on the semaphore S?

Answer 77

It increments the value of S (S++).

Question 78

A critical requirement for all modifications to a semaphore's value in `wait()` and `signal()` is that they must be executed _____.

Answer 78

atomically

Question 79

What does it mean for a semaphore modification to be atomic?

Answer 79

When one process modifies the semaphore value, no other process can simultaneously modify that same semaphore value.

Question 80

In the `wait(S)` operation, which two parts must be executed without interruption as a single unit?

Answer 80

The testing of the integer value of S (S ≤ 0) and its possible modification (S--).

Question 81

What are the two main types of semaphores?

Answer 81

Binary semaphores and counting semaphores.

Question 82

A _____ semaphore is an integer whose value can only range between 0 and 1.

Answer 82

binary

Question 83

A binary semaphore is functionally similar to what other synchronization tool?

Answer 83

A mutex lock.

Question 84

On systems that do not provide mutex locks, what can be used instead to provide mutual exclusion?

Answer 84

Binary semaphores.

Question 85

A _____ semaphore is an integer whose value can range over an unrestricted domain (or from 0 to N).

Answer 85

counting

Question 86

What is a primary use case for counting semaphores?

Answer 86

To control access to a finite number of resources.

Question 87

When using a counting semaphore to manage a set of resources, what should its initial value be?

Answer 87

The number of resources available.

Question 88

To use a resource controlled by a counting semaphore, a process must perform a _____ operation on the semaphore.

Answer 88

wait()

Question 89

Performing a `wait()` operation on a resource-counting semaphore has what effect on its value?

Answer 89

It decrements the semaphore's value.

Question 90

When a process releases a resource controlled by a counting semaphore, it performs a _____ operation.

Answer 90

signal()

Question 91

Performing a `signal()` operation on a resource-counting semaphore has what effect on its value?

Answer 91

It increments the semaphore's value.

Question 92

When a counting semaphore used for resource management reaches a value of 0, what does this signify?

Answer 92

All available resources are currently being used.

Question 93

What happens to a process that performs a `wait()` operation on a counting semaphore whose value is 0?

Answer 93

The process will be blocked until the semaphore value becomes greater than 0.

Question 94

What is the general structure of a process using a semaphore to access a limited resource?

Answer 94

An infinite loop containing `wait()`, followed by resource use, followed by `signal()`.

Question 95

Besides mutual exclusion, semaphores can be used to solve various _____ problems.

Answer 95

synchronization

Question 96

Consider two processes, P1 and P2. How can a semaphore ensure that statement S2 in P2 executes only after statement S1 in P1 has finished?

Answer 96

By having P1 and P2 share a common semaphore initialized to 0.

Question 97

To enforce that S1 runs before S2, what should the initial value of the shared semaphore `synch` be?

Answer 97

0

Question 98

To enforce that S1 runs before S2, process P1 should execute `S1;` followed by what semaphore operation?

Answer 98

`signal(synch);`

Question 99

To enforce that S1 runs before S2, process P2 should execute what semaphore operation before `S2;`?

Answer 99

`wait(synch);`

Question 100

Why does initializing `synch` to 0 ensure P2 waits for P1?

Answer 100

Because P2's call to `wait(synch)` will block until P1 executes `signal(synch)` after S1 is complete.

Question 101

What is a significant risk when programming with semaphores?

Answer 101

Using them incorrectly can result in subtle and difficult-to-detect errors.

Question 102

What happens if a programmer incorrectly interchanges the order of `wait()` and `signal()` when implementing mutual exclusion?

Answer 102

The mutual-exclusion requirement is violated, and several processes may be in their critical sections simultaneously.

Question 103

Which order of operations, `signal(mutex); ... wait(mutex);`, violates mutual exclusion?

Answer 103

Calling `signal(mutex)` before the critical section and `wait(mutex)` after it.

Question 104

What higher-level synchronization construct was proposed to address the error-prone nature of semaphores?

Answer 104

Monitors.

Question 105

Monitors are described as language-specific _____ constructs.

Answer 105

synchronization

Question 106

What is the fundamental guarantee that a monitor provides?

Answer 106

Only one process may be active within the monitor at any given time.

Question 107

At what level of the system must monitors be implemented?

Answer 107

At the compiler or language level.

Question 108

Whose responsibility is it to enforce a monitor's mutual exclusion property?

Answer 108

The compiler.

Question 109

In the monitor construct, where is the critical section of code placed?

Answer 109

Inside the monitor.

Question 110

What is the first step a process must take to execute a critical section protected by a monitor?

Answer 110

The process must enter the monitor.

Question 111

What happens if a process attempts to enter a monitor that is already occupied by another process?

Answer 111

The process must wait in an entry queue.

Question 112

What event allows the next waiting process to enter a monitor?

Answer 112

The process currently inside the monitor leaves.

Question 113

The diagram of a monitor shows processes waiting to enter in a structure called the _____.

Answer 113

entry queue

Question 114

Who determines the specific implementation details of how a monitor enforces mutual exclusion?

Answer 114

The compiler, language, or system.

Question 115

The behavior of a monitor, where only one process can be inside at a time, is similar to what other concept in synchronization?

Answer 115

A critical section.

Question 116

When a process finishes its task inside a monitor, what must it do?

Answer 116

It must leave the monitor, allowing another process to enter.