Concurrency and Deadlocks

Multiprogramming

Management of multiple processes within a uniprocessor system.

Multiprocessing

Management of multiple processes within a multiprocessor system.

Distributed processing

Management of multiple processes executing on multiple distributed computer systems.

Mutual Exclusion

The basic requirement to support concurrent processes.

Pertains to the ability to execute all other processes from a course of action while one (1) process is granted that ability.

Requirements for Mutual Exclusion

1. Only one process at a time is allowed in its critical section.

2. A process that halts in its noncritical section must not interfere with others.

3. No deadlock or starvation; processes must not be delayed indefinitely.

4. When no process is in a critical section, any requesting process must be allowed to enter without delay.

5. No assumptions about process speeds or number of processors.

6. A process must remain in the critical section for a finite time only.

Concurrency

Is an application performance technique that encompasses the ability to load and execute multiple runnable programs. Each of these programs may be an application process that does not necessarily execute on the central processing unit (CPU) at the same instance; even their runtimes may overlap.

Multiple applications

Structured applications

Operating system structure

(3) Contexts of Concurrency

Single-processor multiprogramming system

A system where processes are interleaved in time to yield the appearance of simultaneous execution, improving processing efficiency and program structuring despite no actual parallel processing.

Process Interaction Types

Competition

Independent processes unaware of each other, leading to mutual exclusion, deadlock, and starvation issues.

Cooperation by sharing

Processes indirectly aware of each other, sharing access to objects, with potential issues in mutual exclusion, deadlock, and data coherence.

Cooperation by communication

Processes directly aware of each other, designed to work jointly, with deadlock and starvation as potential issues.

OS Concerns with Concurrency

1. Track various processes using process control blocks.

2. Allocate and deallocate resources for each active process.

3. Protect data and physical resources from unintended interference.

4. Ensure output independence of processes relative to execution speed.

Counting Semaphore

An integer value used for signaling processes, allowing atomic operations: initialize, decrement, and increment.

Binary Semaphore

A semaphore that only takes values 0 (not available) and 1 (available

Mutual Exclusion (Mutex) Lock

Similar to a binary semaphore, but only the locking process can unlock it.

Condition Variable

Data type used to block a process until a specific condition is true.

Monitor

Programming construct encapsulating variables and access procedures, allowing only one process access at a time.

Event Flag

Memory word for synchronization, with each bit associated with specific application code.

Mailbox or Message Passing

Mechanism for two processes to exchange information and synchronize.

Spinlock

Mechanism where a process continuously checks a lock variable in an infinite loop until it becomes available.

Deadlock

Permanent blocking of a set of processes competing for system resources, with each blocked waiting for an event triggered by another blocked process.

Resource Categories

Reusable resources

Resource Allocation Graph

Is a useful tool in characterizing the allocation of resources to processes. Directed graph depicting the state of resource allocation, where processes and resources are nodes, and edges indicate requests and grants.

Richard Holt

Introduced the resource allocation graph.

Resource Allocation Graph

An edge directed from a process to a resource indicates a resource that has been requested by the process but not yet granted.

Resource Allocation Graph

A dot within the resource node represents an instance of a resource.

Resource Allocation Graph

An edge directed from a reusable resource node dot to a process indicates a request that has been granted, and one (1) unit of the resource has been assigned to the process.

Resource Allocation Graph

An edge directed from a consumable resource node dot to a process indicates the process is the procedure of that resource.

Deadlock

Can also be described as an unresolved circular wait.

Deadlock Conditions

Mutual Exclusion

At least one resource must be held in a non-sharable mode. This means that only one (1) thread at a time can use the resource. If another thread requests that specific resource, the requesting thread must be delayed until the resource has been released.

Hold and Wait

A thread must hold at least one resource while waiting to acquire additional resources that are currently being held by other threads.

No Preemption

Resources cannot be preempted. This means that a resource can only be released voluntarily by the thread holding it after that thread has completed its task.

Circular Wait

Closed chain of threads, each holding a resource needed by the next.

Deadlock Prevention

Disallows one of the four deadlock conditions to exclude deadlock possibilities.

Indirect method

Mutual Exclusion: Generally supported. Hold and Wait: Require all resources at once. No Preemption: Force release of resources on further requests.

Direct method

Circular Wait: Define a linear order of resource types.

Deadlock Avoidance

Strategy that allows resource allocation while ensuring that the system never enters a deadlock state.

Process initiation denial

Do not start processes that may lead to deadlock.

Resource allocation denial

Do not grant resource requests that may lead to deadlock.

Deadlock Detection

Grant resource requests when possible, but periodically check for deadlocks and recover.

Recovery methods

a. Abort all deadlocked processes. b. Roll back and restart processes from checkpoints. c. Abort processes successively until deadlock resolves. d. Preempt resources from processes until deadlock resolves.

Selection Criteria for Abortion

Least processor time consumed.

Least output produced.

Most estimated remaining time.

Least total resources allocated.

Lowest priority.

Deadlock

Circular wait

No deadlock

Resource is requested

Resource is held