Unit 4: Deadlock

1. Deadlock Characterization

Deadlock is a situation in a multi-programming environment where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process.

The Four Necessary Conditions (Coffman Conditions)

For a deadlock to occur, all four of the following conditions must hold simultaneously:

1. Mutual Exclusion: At least one resource must be held in a non-sharable mode. If another process requests that resource, the requesting process must be delayed until the resource has been released.
2. Hold and Wait: A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.
3. No Preemption: Resources cannot be preempted; that is, a resource can be released only voluntarily by the process holding it, after that process has completed its task.
4. Circular Wait: A set of waiting processes must exist such that is waiting for a resource held by , is waiting for a resource held by , ..., and is waiting for a resource held by .

Resource Allocation Graph (RAG)

• Vertices (): Partitioned into two types: (Processes) and (Resources).
• Edges ():
  • Request Edge (): Process requests Resource .
  • Assignment Edge (): Resource is allocated to Process .
• Analysis: If the graph contains no cycles, no deadlock exists. If the graph contains a cycle, deadlock may exist (depending on multiple instances of resources).

2. Handling of Deadlocks

There are four general strategies to deal with deadlock:

1. Deadlock Prevention: Ensure that at least one of the four necessary conditions cannot hold.
2. Deadlock Avoidance: The OS uses prior knowledge about resource usage to assess whether allocating a resource will leave the system in a safe state.
3. Deadlock Detection and Recovery: Allow deadlocks to occur, detect them, and take action to recover.
4. Ignore the problem (Ostrich Algorithm): Pretend deadlock never occurs. Used by Windows and UNIX/Linux for user processes (reliability is traded for performance).

3. Deadlock Prevention

Prevention involves restraining requests to negate one of the four necessary conditions.

• Mutual Exclusion: Cannot be denied for non-sharable resources (e.g., printers), but sharable resources (read-only files) do not require mutual exclusion.
• Hold and Wait: Guarantee that whenever a process requests a resource, it does not hold any other resources.
  • Protocol: Request all resources at the start. Disadvantage: Low resource utilization and starvation.
• No Preemption: If a process holding some resources requests another resource that cannot be immediately allocated, all currently held resources are released (preempted).
• Circular Wait: Impose a total ordering of all resource types. A process can only request resources in an increasing order of enumeration.

4. Deadlock Avoidance

Avoidance requires the system to have additional a priori information regarding the resources a process will need.

Safe State

A state is safe if the system can allocate resources to each process (up to its maximum) in some order and still avoid a deadlock. If a system is in a safe state no deadlock. If unsafe possibility of deadlock.

Banker's Algorithm

Designed for systems with multiple instances of each resource type.

• Data Structures:
  • Available: Vector of length .
  • Max: matrix.
  • Allocation: matrix.
  • Need: matrix ().
• Logic: When a request is made, the system pretends to allocate. It then runs a safety algorithm to see if a valid "safe sequence" exists. If yes, the request is granted; otherwise, the process waits.

5. Deadlock Detection and Recovery

Detection

• Single Instance of each resource: Use a Wait-for Graph (a variant of RAG where resources are removed and edges go directly Process Process). A cycle implies deadlock.
• Multiple Instances: Use an algorithm similar to Banker’s (Safety Algorithm) to check if the current allocation state can finish all processes.

Recovery

1. Process Termination:
   • Abort all deadlocked processes.
   • Abort one process at a time until the deadlock cycle is eliminated.
2. Resource Preemption:
   • Select a victim: Minimize cost.
   • Rollback: Return process to a safe state (or restart it).
   • Starvation: Ensure the same process isn't always picked as the victim.

6. Starvation

Starvation (Indefinite Blocking) occurs when a process waits indefinitely for a resource because other processes are continuously preferred over it.

• Difference: Deadlock is a circular wait where no one proceeds. Starvation is where the system is active, but specific low-priority processes never get the CPU/Resource.
• Solution: Aging (gradually increasing the priority of a process as it waits longer).

Protection and Security

1. Distinction and Need for Security

• Protection: Mechanisms used to control the access of system programs, processes, or users to the resources defined by a computer system. It focuses on internal constraints.
• Security: A broader concept that includes protection but also handles external threats (physical access, network attacks). It ensures the integrity, confidentiality, and availability of the system.

2. Security Vulnerabilities

Buffer Overflow

A condition where a program writes data beyond the buffer boundary and overwrites adjacent memory locations.

• Mechanism: Attackers often overwrite the Return Address on the stack to point to malicious shellcode injected into the buffer.
• Consequence: Allows execution of arbitrary code with the privileges of the compromised program.

Trapdoors (Backdoors)

A secret entry point into a program that allows someone who is aware of the trapdoor to gain access without going through the usual security access procedures. Often left by developers for debugging.

Cache Poisoning

Malicious data is introduced into a cache (like DNS cache or ARP cache) so that legitimate requests are redirected to a malicious destination (e.g., a phishing site).

3. Authentication

Password-based Authentication

The most common method where the user provides a secret string.

• Vulnerabilities: Brute force, Dictionary attacks, Shoulder surfing, Sniffing.

Password Maintenance & Secure Communication

• Salting: Adding a random string (salt) to the password before hashing. This prevents Rainbow Table attacks and ensures two users with the same password have different hashes.
• Hashing: Passwords should never be stored in plain text. Use strong algorithms (SHA-256, bcrypt).
• One-Time Passwords (OTP): Valid for only one session.

4. Application Security: Program Threats and Viruses

Program Threats

• Trojan Horse: A code segment that misuses its environment. It appears useful (e.g., a free game) but contains hidden malicious code.
• Logic Bomb: Code embedded in a legitimate program that "explodes" (executes malicious action) when specific conditions are met (e.g., a specific date).
• Stack/Buffer Overflow: (described above).

Viruses

A code fragment embedded in a legitimate program that is self-replicating.

• Boot Sector Virus: Infects the master boot record and executes when the system boots.
• Macro Virus: Written in macro languages (e.g., for Word/Excel).
• Polymorphic Virus: Changes its own signature (binary pattern) every time it replicates to evade antivirus detection.

5. Protection Mechanisms

Goals of Protection

1. Prevent malicious misuse of the system.
2. Ensure resources are used only in consistent/defined ways.
3. Error containment (preventing a bug in one subsystem from crashing others).

Principles of Protection

• Principle of Least Privilege: A program/user should operate with the minimum set of privileges necessary to complete the task.
• Need-to-Know: A process should only have access to resources it currently needs.

Domain of Protection

A Domain implies a set of (object, rights) pairs.

• A process operates within a protection domain.
• Structure:
  • User/Supervisor Mode: Two domains.
  • Rings: Multics/x86 architecture uses rings (0 to 3), where Ring 0 is the kernel (most privileged) and Ring 3 is user space.

Access Matrix

A general model of protection.

• Rows: Domains ().
• Columns: Objects (Files, Printers, Hardware).
• Entry access[i,j]: Defines the set of operations (Read, Write, Execute, Print) that a process executing in Domain can invoke on Object .

Implementation of Access Matrix

Since the matrix is sparse (mostly empty), storing it as a 2D array is inefficient.

1. Global Table: Ordered triples <Domain, Object, Rights>. Slow to search.
2. Access Control Lists (ACLs): Store columns with the object. Each object has a list of domains and their rights. (Used in Windows/Unix).
   • Example: File A
3. Capability Lists: Store rows with the domain. Each domain has a list of objects and rights it possesses. (Like a "keychain").

6. System and Network Threats

System Threats

• Worms: Standalone malware that replicates itself to spread to other computers. Unlike viruses, worms do not need to attach to a host program. They consume system resources (bandwidth, CPU).
• Port Scanning: Automated detection of open ports on a target system to identify running services and vulnerabilities.
• Denial of Service (DoS): Flooding a system with requests to make it unavailable to legitimate users.

Examples of Attacks

1. Man-in-the-Middle (MitM): Attacker secretly relays and possibly alters the communication between two parties who believe they are communicating directly.
2. Phishing: Fraudulent attempt to obtain sensitive information (usernames, passwords) by disguising as a trustworthy entity in electronic communication.
3. SQL Injection: Injecting malicious SQL commands into input fields to manipulate the backend database.