Module 3: Process Synchronization

What may the failure of the liveness criteria result in?

- Deadlock: Every process depends on one that is blocking (Thus, no progress)
- Starvation: Some processes wait indefinitely

What are all of the different approaches to synchronization?

- Busy Waiting (Using a 'spin lock')
- Messaging
- Monitors
- Barrier Synchronization
- Shadow Copies
- Semaphores & Mutexes (Software Locks)

Busy Waiting (Short Notes)

- Can be software or hardware based
- Accomplished using a "Spin Lock"

Monitors (Short Notes)

- Requires language support
- Signaling-type system

Which of the following synchronization approaches require OS support?
1. Busy Waiting
2. Monitors
3. Shadow Copies
4. Messaging
5. Barrier Synchronization
6. Semaphores & Mutexes

- Messaging
- Barrier Synchronization
- Semaphores & Mutexes

Naive Producer-Consumer solutions are prone to what?

Fatal race conditions

Barrier Synchronization (Short Notes)

- Requires OS support
- "All together now"

Naive Producer-Consumer solution (Code)

Problems with this solution include:

- Corrupted shared variables
- Double-write
- Double-read
- Read-write

Semaphores & Mutexes (Short Notes)

- Require OS support
- Use atomic operations facilitate lock (TSL)

True or False: Semaphores can help us solve the producer consumer problem?

True

We can avoid some locks by using

Shadow copies

A shadow copy is the same thing as a

Copy-on-write

Semaphores can help us prevent which issues with the Producer-Consumer problem?

- Variable corruption
- Double-read
- Double-write
- Read-write

What are the steps to a Shadow Copy approach?

1. If it is an atomic copy, no lock is necessary - Otherwise, utilize a read-only lock.
2. Make a copy of the original data
3. Update copy with new information
4. Change pointer to a new copy
5. Release old copy once all readers are done.

What is the caveat (issue) to solving the Producer-Consumer problem with a semaphore?

With multiple readers and writers, the critical region bottleneck becomes pronounced.

In the context of solving the Producer-Consumer problem with semaphores, instead of locking the entire buffer, we can

Lock individual entries instead. This is called marking entries.

________ is/are a language construct that use(s) "condition variables"

Monitors

True or False: Monitors can be implicit

True

Monitors guarantee at most _____ process(es) at a time?

One

In the Monitor approach, condition variables handle what?

blocking/unblocking

Marking allows

Multiple producers and consumers to act on the buffer

This approach is resolved semantically - no "variable" memory

Monitors

What is the Readers-Writers Problem?

In the readers-writers problem, we have one or more readers (which only read) and one or more writers (which may read and will write) working on a single database (data store) at the same time.

Which approach requires that all processes reach a certain specified point before they can continue?

Barriers

What is the difference between the producer-consumer problem and the readers-writers problem?

While in the producer-consumer problem, data are intended to be written and read exactly one time - as it is stored in temporary storage (a buffer) - in readers-writers, data is persistent (and can be read or written several times).

Real-world examples of the Readers-writers problem:

- Web portal database transactions
- Removable disk storage
- High-speed trading / banking balances

Both _______ and __________ are shared-memory variables

Mutexes (Mutual Exclusion Variables) and Semaphores

In the readers-writers problem, we distinguish between:

Read locks and write locks

Provided by OS as blocking-based locking mechanisms (No busy waiting)

Mutexes & Semaphores

What are the 3 categories of challenges in the Readers-Writers problem?

1. Concurrency
2. Safety
3. Liveness

What are the operations of a Mutex?

1. Lock
2. Unlock

In the context of the Readers-Readers problem, what are the challenges with: Concurrency

- Multiple readers may read the database at the same time
- No assumptions may be made about the speed of any process

Once a mutex is locked, which can unlock it?
A. The next thread in line
B. The locking Thread
C. Any thread/process that is run with Admin privileges
D. Any thread/process

B. Only the locking thread can unlock a locked Mutex.

In the context of the Readers-Readers problem, what are the challenges with: Safety

- Never may two writers write to the database at the same time
- Never may a reader read from the database while a writer is writing it

This approach is intended specifically for single-process-at-a-time critical regions

Mutex

In the context of the Readers-Readers problem, what are the challenges with: Liveness

- No process not currently using the database may prevent another from accessing it
- No process must wait indefinitely to obtain access to the database

What are the operations of a Sempahore?

1. Up (Increment)
2. Down (Decrement)

Who can increment or Decrement a Semaphore?
A. The next thread in line
B. The locking Thread
C. Any thread/process that is run with Admin privileges
D. Any thread/process with access

D. Any thread/process with access can increment or decrement a Semaphore.

________ can help us solve the readers-writers problem

Semaphores

True or False: A Mutex provides resource counting / tracking?

False. A Semaphore provides resource counting / tracking.

With the initial solution to the Readers-Writers problem using semaphores, what is a factor that limits efficiency?

Often writers need to do initial reads before writing, limiting efficiency

Which synchronization approach is tightly controlled?

A semaphore. The only operations are creation, up and down.

Creation Operation (Semaphore)

Semaphores can be created with a starting count

What is an Alpha Lock?

An alpha lock (tentative write lock( lets us signal intent to lock the database

Down Operation (Semaphore)

- If count > 0, decrement and continue
- Otherwise, block and add caller to this semaphores queue

Features of Alpha Locks

- Allow tentative reading while waiting for a write lock
- Prevents other writers from obtaining an alpha lock

How does a Semaphore know who it should allow access next?

By keeping a queue of those waiting.

Up Operation (Semaphore)

- If queue is empty, increment count and continue
- Otherwise, remove and unblock first process in the queue for this semaphore
- NOTE: The up operation never blocks!

Alpha locks can improve __________ by:

Concurrency; by beginning reads while readers are active.

With busy waiting, we could try to avoid excessive waits by indicating interest with what supplementary method?

Flagging Interest

Why can busy waiting with flagging interest fail?

Because the flagging and locking are not atomic

What does the Peterson Solution approach to Busy Waiting do?

It combines the flagging and alternation approach

Why do we want to avoid using spin locks?

Because spin locks (busy waiting) inefficiently use the CPU while waiting for a resource

What are the 2 instruction variants that perform atomic locking?

- Test-and-Set-Lock (TSL)
- Swap (XCHG)

Which approach employs a call instruction to yield the CPU?

Mutex

Messaging passing enables synchronization and can also be used for

Mutual exclusion

The dining philosophers problem demonstrates the pattern of what?

Circular deadlock. When several processes with a similar pattern require more than one lock to act.

Criteria of the Dining Philosophers problem?

- Concurrency
- Safety
- Liveness

Concurrency in regards to the Dining Philosophers problem

- Any two philosophers (or processes) that are not (logically) adjacent can eat (run its critical section) simultaneously.
- No assumptions may be made about how long any process eats or thinks (runs its non-critical sections)

Safety in regards to the Dining Philosophers problem

- No two adjacent philosophers can eat at the same time

Liveness in regards to the Dining Philosophers problem

- No philosopher that is not eating can prevent any other philosopher from eating

The key to solving the Dining Philosophers Problem

You have to relinquish (give up) resources if you can't eat (use) them.