Parallel Execution, Mutex, and Deadlocks in Operating Systems

Parbegin / Person Learns

Parbegin is a structure to indicate parallel execution, marking the beginning and end. Selection: A statement dividing sequential execution into parallel streams.

Its general form (Dijkstra):

parbegin Proposition1; Proposition2; Proposition n; person learns

Mutex

Mutex occurs when processes share data, preventing simultaneous access. It applies when a process accesses shared data, allowing concurrent execution of non-conflicting transactions.

Critical Sections

A process accessing shared data is in a critical section. When a process is in a critical section:

• All other processes are excluded from their critical sections.
• Other processes can execute outside their critical sections.
• When a process exits, the next waiting process can enter.
• A process has exclusive access to shared data, holding others.
• A program should not block in its critical section.
• Upon termination, the OS releases the mutex.

Deadlock

Deadlock occurs when a process waits for an event that won't happen, creating a standstill.

REVENGE: PROCEDURE OPTIONS (MAIN TASK), WAIT (EVENT); END REVENGE;

Traffic Deadlock

At a four-way intersection, cars yield to the right. With four cars, all wait, causing deadlock. If all proceed, each gets a quadrant but can't continue, leading to deadlock.

Simple Appeal Deadlock

Deadlocks arise from resource restraint:

• Resources used by one user at a time.
• Processes wait for each other to release resources.
• Resources are held until the other user releases theirs.
• Circular wait occurs.

Deadlock Detection

Identify processes and resources in a deadlock cycle. If cycles exist, deadlock occurs.

Indefinite Postponement

A process is kept waiting due to resource allocation decisions. Aging increases a waiting process's priority.

Interlock Spool Systems

Spool systems enhance capacity but are prone to deadlock. Lines are sent to a disk, stored until printed. Partially completed jobs can interlock if space fills. Recovery may involve restarting or losing jobs.

• Provide larger spool file space.
• Limit spoolers when 75% full.
• Modern systems allow printing before job completion.

Four Conditions for Deadlock (Coffman, Elphick, Shoshani)

• Mutual exclusion condition: Exclusive resource control.
• Wait for condition: Processes hold resources while waiting.
• Non-appropriativity condition: Resources can't be extracted.
• Circular wait condition: Circular chain of processes holding resources.

Deadlock Recovery

Recovery is hindered by:

• Uncertainty if the system crashed.
• Suspending and resuming processes is difficult.
• Overhead and operator attention are required.
• Large-scale deadlock requires significant effort.

Processes can be removed by priority, but priorities may be unclear or incorrect.