C191-Terms-Chapter-5

Question 1

Concurrency

Answer 1

the act of multiple processes (or threads) executing at the same time. When multiple physical CPUs are available, the processes may execute in parallel.

On a single CPU, concurrency may be achieved by time-sharing.

When concurrent processes access a common data area, the data must be protected from simultaneous change by two or more processes. Otherwise the updated area may be left in an inconsistent state.

Question 2

critical section

Answer 2

a segment of code that cannot be entered by a process while another process is executing a corresponding segment of the code.

Question 3

A software solution to the CS problem.

Answer 3

Any solution to the critical section (CS) problem must satisfy the following requirements:
Guarantee mutual exclusion: Only one process may be executing within the CS.

Prevent lockout: A process not attempting to enter the CS must not prevent other processes from entering the CS.

Prevent starvation: A process (or a group of processes) must not be able to repeatedly enter the CS while other
processes are waiting to enter.

Prevent deadlock: Multiple processes trying to enter the CS at the same time must not block each other indefinitely.

Question 4

Process cooperation

Answer 4

many applications require the cooperation of processes to solve a common goal. A typical scenario is when one process produces data needed by another process.

The producer process must be able to inform the waiting process whenever a new data item is available.

In turn, the producer must wait for an acknowledgement from the consumer, indicating that the consumer is ready to accept the next data item.

Question 5

mutex lock

Answer 5

A mutual exclusion lock; the simplest software tool for assuring mutual exclusion.

We use the mutex lock to protect critical sections and thus prevent race conditions.

That is, a process must acquire the lock before entering a critical section; it releases the lock when it exits the critical section.

The acquire() function acquires the lock, and the release() function releases the lock.

A mutex lock has a boolean variable available whose value indicates if the lock is available or not. If the lock is available, a call to acquire() succeeds, and the lock is then considered unavailable.

A process that attempts to acquire an unavailable lock is blocked until the lock is released.

Question 6

contended

Answer 6

A term describing the condition of a lock when a thread blocks while trying to acquire it.

Locks are either contended or uncontended. A lock is considered contended if a thread blocks while trying to acquire the lock. If a lock is available when a thread attempts to acquire it

Question 7

uncontended

Answer 7

A term describing a lock that is available when a thread attempts to acquire it.

If a lock is available when a thread attempts to acquire it, the lock is considered uncontended.

Question 8

high contention

Answer 8

Contended locks can experience either high contention (a relatively large number of threads attempting to acquire the lock).

Question 9

low contention

Answer 9

a relatively small number of threads attempting to acquire the lock.

Question 10

short duration

Answer 10

Given that waiting on a lock requires two context switches—a context switch to move the thread to the waiting state and a second context switch to restore the waiting thread once the lock becomes available—the general rule is to use a spinlock if the lock will be held for a duration of less than two context switches.

Question 11

busy waiting

Answer 11

A practice that allows a thread or process to use CPU time continuously while waiting for something. An I/O loop in which an I/O thread continuously reads status information while waiting for I/O to complete.

While a process is in its critical section, any other process that tries to enter its critical section must loop continuously in the call to acquire().

This continual looping is clearly a problem in a real multiprogramming system, where a single CPU core is shared among many processes.

Busy waiting also wastes CPU cycles that some other process might be able to use productively.

Question 12

spinlock

Answer 12

A locking mechanism that continuously uses the CPU while waiting for access to the lock.

Spinlocks do have an advantage, however, in that no context switch is required when a process must wait on a lock, and a context switch may take considerable time.

In certain circumstances on multicore systems, spinlocks are in fact the preferable choice for locking.

If a lock is to be held for a short duration, one thread can “spin” on one processing core while another thread performs its critical section on another core.

On modern multicore computing systems, spinlocks are widely used in many operating systems.

Question 13

The software solution to the CS problem has several major shortcomings:

Answer 13

The solutions works only for 2 processes. When 3 or more processes need to share a CS, a different solution must be developed.

The solution is inefficient. While one process is in the CS, the other process must wait by repeatedly testing and setting the synchronization variables. The waiting process is only wasting CPU and memory resources without accomplishing any useful work.

The solution addresses only competition among processes. To address problems of process cooperation, entirely different solutions must be devised.

Question 14

Semaphores

Answer 14

general-purpose primitives that allow solving a variety of synchronization problems in a systematic manner.

A semaphore s is a non-negative integer variable that can be accessed using only two special operations, P and V.

V(s): increment s by 1
P(s): if s > 0, decrement s by 1, otherwise wait until s > 0

The implementation of P and V must guarantee that:
If several processes simultaneously invoke P(s) or V(s), the operations will occur sequentially in some arbitrary order.

If more than one process is waiting inside P(s) for s to become > 0 , one of the waiting processes is selected to complete the P(s) operation.

The selection can be at random but a typical implementation maintains the blocked processes in a queue processed in FIFO order.

Question 15

The CS problem using semaphores

Answer 15

A single semaphore, initialized to 1, is sufficient to solve the problem for any number of processes.

Question 16

The bounded-buffer problem

Answer 16

The bounded-buffer problem is a classic synchronization problem intended to illustrate process cooperation.

A producer process shares a buffer with a consumer process. The buffer has a fixed number of slots. The producer fills empty slots with data in increasing order.

The consumers follows the producer by removing the data in the same order. The buffer is called a circular buffer because, upon reaching the last slot, each process continues with the first slot (modulo n).
The solution must guarantee the following:

Consumers do not overtake producers and access empty slots.
Producers do not overtake consumers and overwrite full slots.

Question 17

The bounded-buffer problem using semaphores

Answer 17

Two semaphores are used to coordinate the processes. The semaphore f represents the number of full buffer slots and is incremented each time the producer places a new data item into the buffer and decremented each time the consumer removes an item from the buffer.

The semaphore e represents the number of empty slots and is modified by the producer and consumer analogously.

Question 18

test-and-set instruction (TS)

Answer 18

copies a variable into a register and sets the variable to zero in one indivisible machine cycle.

Test-and-set has the form TS(R, x) where R is a register and x is a memory location and performs the following operations:

• Copy x into R.
• Set x to 0.

Question 19

lock

Answer 19

a synchronization barrier through which only one process can pass at a time. TS allows an easy implementation of a lock.

Question 20

Binary semaphores

Answer 20

Many synchronization problems do not require the full power of a general semaphore.

A binary semaphore can take only the values 0 or 1. Pb and Vb are the simplified P and V operations that manipulate binary semaphores.

Pb and Vb on the binary semaphore sb can be implemented directly using the TS instruction:

Vb(sb): sb = 1

Pb(sb): do TS(R,sb) while R == 0

Question 21

Busy-waiting

Answer 21

is the act of repeatedly executing a loop while waiting for some condition to change. Busy-waiting consumes CPU resources and should be avoided whenever possible. The implementation of Pb(sb) using TS is very simple but suffers from the drawback of busy-waiting.

Question 22

Implementing P and V operations on general semaphores

Answer 22

A general semaphore s can be implemented using a regular integer variable manipulated by the functions P(s) and V(s). To guarantee that only one operation at a time can access and manipulate s, a binary semaphore is used.

The variable s serves a dual purpose:

When s is greater or equal 0, s represents the value of the semaphore.
Whenever s falls below 0, the value represents the number of processes blocked on the semaphore.

To avoid busy-waiting inside P(s) when s falls below 0, the process performs a blocking request, which places the process on a waiting list associated with s.

A V(s) operation increments s and reactivates one process if one or more are blocked on s.

Question 23

monitor

Answer 23

a high-level synchronization primitive implemented using P and V operations. Following the principles of abstract data types, a monitor encapsulates data along with functions through which the data may be accessed and manipulated.

Question 24

condition variable

Answer 24

a named queue on which processes can wait for some condition to become true.

Question 25

The implementation of a monitor must:

Answer 25

Guarantee that the functions are mutually exclusive. Thus only one process at a time may be executing inside a monitor.

Provide condition variables such that a process can step outside of the monitor while waiting for a condition and thus not prevent other processes from entering the monitor.

A condition variable c is accessed using two special operations:

c.wait causes the executing process to block and be placed on a waiting queue associated with the condition variable c.

c.signal reactivates the process at the head of the queue associated with the condition variable c.

Question 26

A monitor implementation of the bounded-buffer problem

Answer 26

Since the monitor guarantees mutual exclusion, the functions to deposit and to remove data automatically become critical sections. Consequently, the solution works for multiple producers and multiple consumers.

The condition notfull is used by the producer to wait when all buffer slots are full. Analogously, the condition notempty is used by the consumer to wait when all buffer slots are empty.

A counter, full_slots, initially set to 0, is used to keep track of how many slots are full. The counter is incremented by the producer and decremented by the consumer during each call to the monitor.

Question 27

Monitors with priority waits

Answer 27

Normally a queue associated with a conditional variable is processed in FIFO order. Some applications require additional control over the order of process reactivation.

A priority wait has the form c.wait(p), where c is a conditional variable and p is an integer specifying a priority according to which processes blocked on c are reactivated.

Question 28

Implementation of a monitor

Answer 28

A compiler or preprocessor uses P and V operations on semaphores to enforce the different features of a monitor.

A semaphore mutex (initialized to 1) is used to enforce mutual exclusion among the functions.

A semaphore c (initialized to 0) is used for each condition variable c to allow a process to block itself on the condition.

A semaphore urg (initialized to 0) is used to block a process executing a signal operation.

Associated with each semaphore c is a counter c_cnt, which keeps track of the number of processes blocked on c.

Associated with the semaphore urg is a counter urg_cnt, which keeps track of the number of processes blocked on urg.

Question 29

The readers-writers problem

Answer 29

an extension of the critical section problem where two types of processes, readers and writers, compete for access to a common resource. Readers are allowed to enter the critical section (CS) concurrently but only one writer is allowed to enter at a time.

The main challenge is to guarantee maximum concurrency of readers while preventing the starvation of either type of process. Specifically, two rules must be enforced:

A reader is permitted to join other readers currently in the CS only when no writer is waiting. When the last readers exits the CS, the writer is allowed to enter.

All readers that have arrived while a writer is in the CS must be allowed to enter before the next writer.

Rule 1 guarantees that writers cannot starve.

Rule 2 guarantees that readers cannot starve.

Jointly the two rules guarantee maximum concurrency of readers.

Question 30

A monitor solution to the readers-writers problem

Answer 30

The monitor provides 4 functions:

start_read is called by a reader to get a permission to read.

end_read is called by a reader when finished reading.

start_write is called by a writer to get a permission to write.

end_write is called by a writer when finished writing.

Two counters, reading and writing, are used to keep track of the number of readers and the number of writers currently in CS, respectively.

Two condition variables, ok_to_read and ok_to_write, are used to block readers and writers, respectively.

To avoid maintaining separate counters of processes blocked on a condition c, a primitive count(c) is provided, which returns the number of processes blocked on c. Ex: count(ok_to_read) returns the number of processes blocked on ok_to_read.

Question 31

The dining-philosophers problem

Answer 31

The dining-philosophers problem is representative of situations where multiple processes compete for shared resources but each process needs more than one resource at a time.

The main challenge is to prevent deadlock while guaranteeing that any two nonadjacent philosophers can always eat concurrently.

Several approaches exist to avoid the problem:

Approach 1: Request both forks at the same time in a critical section.

Approach 2: One philosopher picks up the forks in the opposite order from all other philosophers.

Question 32

A monitor solution to the dining philosophers problem

Answer 32

Each of the 5 philosophers, p[i], can be in one of 3 states: thinking, hungry, or eating. Thinking does not require any forks. Hungry is a state where the philosopher is blocked because one or both forks are not available. In the eating state the philosopher is holding both forks and is executing.

Question 33

The elevator algorithm

Answer 33

A storage disk consists of n concentric tracks that need to be accessed by read/write requests arriving in some unspecified order. The goal is to minimize the travel distance between tracks while preventing starvation.

The elevator algorithm mimics the behavior of an elevator in an n-story building. The elevator (representing the read-write head of the disk), maintains a direction of motion, up or down, for as long as requests for floors (representing disk tracks) exist, in the current direction. When moving up and no more requests for higher floors exist, the elevator reverses direction and services all requests in descending order. When the request for the lowest floor is serviced, the elevator again reverses direction and proceeds moving up.

Question 34

Peterson’s solution

Answer 34

A historically interesting algorithm for implementing critical sections.