Week 8: Concurrency

Concurrency

The act of multiple processes (or threads) executing at the same time

race condition

a situation where two threads/processes are trying to use the same resource, and the thread/process that gets to the resource first gets to use it first

CS

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

requirements for solutions to the CS problem

Guarantee mutual exclusion, prevent lockout, prevent starvation, and prevent deadlock

mutual exclusion

a situation when only one process is allowed to execute within the CS

lockout

a situation where a process not attempting to enter the CS prevents other processes from entering the CS

starvation

a situation where a process or group of processes repeatedly enters the CS while other processes are waiting to enter (and the waiting processes are "starved")

deadlock

a situation where multiple processes try to enter the CS at the same time and end up blocking each other indefinitely

semaphore

a non-negative integer variable that is accessed using only two special operations, P and V

V(s)

the operation that increments a semaphore, s, by 1

P(s)

the operation that decrements a semaphore, s, by 1 if s is greater than 0. If s is less than 0, it waits until s is greater than 0.

TS

test-and-set instruction; copies a variable into a register and sets the variable to one. Takes the form TS(R, x), where R is a register and x is a memory location.

lock

a synchronization barrier through which only one process can pass at a time

binary semaphore

a semaphore that can take only the values 0 or 1. Binary semaphores use Pb(sb) and Vb(sb) as simplified versions of P(s) and V(s).

busy-waiting

the act of repeatedly executing a loop while waiting for a condition to change. This consumes CPU resources and should generally be avoided.

monitor

a high-level synchronization primitive that encapsulates data and the functions that access data. A monitor can be thought of as a design pattern, which can be implemented using the P and V functions.

condition variable

a named queue in which processes can wait for a condition to become true

c.wait

a special operation that causes the executing process to block and be placed in a queue associated with the condition variable c

c.signal

a special operation that reactivates the process at the head of the queue associated with the condition variable c.

priority wait

a variation of c.wait that takes the form c.wait(p), where p is an integer that represents the priority in which processes blocked on c are reactivated

bounded-buffer problem

a classic synchronization problem where a producer process and a consumer process share a buffer with a fixed number of slots. The producer fills empty slots in an increasing order, and the consumer empties slots in the same order. The solution to this problem must guarantee that consumers do not overtake producers (by accessing empty slots) and that producers do not overtake consumers (by overwriting slots that are filled).

semaphore solution to the bounded-buffer problem

Two semaphores are used to coordinate the processes: semaphore f represents the amount of full buffer slots and semaphore e represents the number of empty slots. When slots are filled or emptied, f and e are adjusted accordingly.

the readers writers problem

An extension of the CS problem where two types of processes (readers and writers) are competing for access to a shared resource. Readers can enter concurrently, but writers have to enter one at a time. The goal is to ensure maximum concurrency of readers while preventing starvation of any process. The problem has two rules. First, a reader can join other readers already in the CS only if no writers are waiting, and a writer can enter the CS when the last reader exits it. Second, all readers that arrive while a writer is in the CS must enter before the next writer.

monitor solution to the readers-writers problem

Four functions are provided by a monitor: start_read, which a reader calls to get permission to read; end_read, which a reader calls to indicate it is done reading; start_write, which a writer calls to get permission to write; and end_write, which a writer calls to indicate it is done writing. Counters called reading and writing keep track of the number of readers and writers currently in the CS, and two condition variables (ok_to_read and ok_to_write) block readers and writers when necessary. A primitive count(c) returns the number of processes blocked on c.

the dining-philosophers problem

Five philosophers sit at a table (they each represent a concurrent process). Five forks are placed on the table in between the pairs of philosophers (these represent resources). Each philosopher alternates between thinking (which does not require resources) and eating (which requires using the two forks adjacent to the philosopher). The goal is to prevent deadlock while also enabling any pair of non-adjacent philosophers to eat at the same time as each other.

monitor solution to the dining philosophers problem

The state of the philosophers is tracked, and can be one of three things: thinking (doesn't want forks), hungry (will eat if forks are available), and eating (using forks). Philosophers who wish to eat must become hungry, and hungry philosophers can only begin eating if neither of their neighbors are eating. When philosophers finish eating, they change to thinking and notify their neighbors in case they are hungry.

the elevator problem

a storage disk consists of n number of concentric tracks that must be accessed by read/write requests that arrive in an unspecified order. The goal is to minimize travel distance between tracks while also preventing starvation. The storage disk mirrors an elevator that must go up and down between floors at the request of users.

the elevator algorithm

The elevator (read-write head of the disk) moves up or down for as long as requests exist in the direction it is already moving. For example, if the elevator is going up, it will keep going up and fulfilling requests until it has reached the highest floor it has a request for. It will then fulfill requests going down until it has reached the lowest floor it has a request for. It keeps reversing directions in this pattern.