OS 2

Concurrency Multiple Applications

Invented to allow processing time to be shared among active applications.

Concurrency Structured Applications

Extension of modular design and structured programming.

Concurrency Operating System Structure

OS themselves implemented as a set of processes or threads.

Atomic Operation

A sequence of instructions that cannot be read or interrupted by other programs.

Critical Section

A section of code that requires access to shared resources and must not be executed when another process is in a corresponding section of code.

Deadlock

A situation in which two or more processes are unable to proceed because each is waiting for one of the others to do something.

Livelock

A situation in which two or more processes continuously change their states in response to changes in the other process(es) without doing any useful work.

Mutual Exclusion

The requirement that when one process is in a critical section, no other process may access a critical section.

Race Condition

A situation in which multiple processes read and write a shared data item, whose result depends on who wrote it last.

Starvation

A situation in which a process is indefinitely held back by the scheduler.

Principles of Concurrency:

Interleaving & overlapping
Uniprocessor

Difficulties of Concurrency:

Sharing of global resources.
Difficult for the OS to manage the allocation of resources optimally.
Difficult to locate programming errors as results are not deterministic or reproducible.

Concurrency Operating System Concerns:

Multiprogramming
Memory Mangement
Data Protection
I/O independent of processing speed.

Resource Competition

When concurrent processes come into conflict when competing for the same resources.

Resource Control Problems:

Mutual Exclusion
Deadlock
Starvation

Requirements for Mutual Exclusion:

Must be enforced.
Stopped processes must not halt others.
No deadlock or starvation.
Processes cannot be denied a critical section when no other process is using it.
No assumptions made about relative process speeds or number of processes.
A process remains inside its critical section for a finite time only.

Hardware Mutual Exclusion Disadvantages:

Efficiency of execution is noticeably degraded.
Doesn’t work with a multiprocessor architecture.

Given an address i, test_and_set(i) will:

Return 1 if that address has been set, 0 otherwise.
This function is atomic.

Given addresses a and b, compare_and_swap(a, b) will:

Swap a and b if the values are the same.

Special Machine Instruction Advantages:

Applicable to any number of processes on single or multiple processors.
Simple and easy to verify.
Supports multiple critical sections.

Special Machine Instruction Disadvantages:

Busy-waiting is employed.
Starvation and deadlock is possible.

Semaphore

An integer value used for signaling among processes.
There is no one to inspect or manipulate a semaphore outside of its three operations.

Semaphore Atomic Operations:

Initialize
Increment
Decrement

Binary Semaphore

Semaphore that takes on the value 0 or 1.

Mutex

A binary semaphore, but the process that sets the value to 0 must be the one to set it to 1.

Condition Variable

A data type that is used to block a process until a particular condition is true.

Mailboxes/Messages

A means for two processes to exchange information.
Can be used for synchronization.

Spinlocks

Mutual exclusion mechanism in which a process executes in an infinite loop waiting for a lock variable.

Producer

A program that produces data.

Consumer

A program that consumes data.

Monitor

A programming language construct that provides equivalent functionality to that of semaphores and is easier to control.

Monitor Characteristics:

Local variables only accessible through monitor procedures.
Processes enter the monitor by invoking one of its procedures.
Only on process may be executing in the monitor at a time.

Synchronization

Achieved by the use of condition variables that are contained and accessible only in the monitor.

Blocking Send, Blocking Receive

A receiver cannot continue until it has received its request.
A sender cannot continue until the receiver confirms its arrival.

Readers/Writers Conditions:

Any number of readers may simultaneously read a file.
Only one writer may write to a file at a time.
If a writer is writing to a file, no reader may read it.