A deadlock is a situation in a multi-process system where two or more processes are unable to proceed because each is waiting for a resource held by another, forming a cycle of dependencies.
2. Define Critical Section
A critical section is a part of a program where shared resources are accessed and modified, and which must be executed by only one process or thread at a time to avoid race conditions.
3. Define Logical Address and Physical Address
Logical Address:
A virtual address generated by the CPU during program execution, which does not correspond to a physical location in memory. Physical Address:
The actual location in the main memory where data or instructions reside.
4. Define Swapping
Swapping is a memory management technique where a process is temporarily moved from main memory to secondary storage (disk) to free up space for other processes.
5. Define Race Condition
A race condition occurs when the behavior of software depends on the relative timing of events such as thread execution order, leading to unpredictable and erroneous results.
6. Define Monitor
A monitor is a synchronization construct that allows safe access to shared resources by ensuring that only one thread can execute a critical section at a time, using mechanisms like mutexes and condition variables.
7. List Different Methods of Handling Deadlock?
Deadlock Prevention: Altering system design to ensure at least one of the Coffman conditions for deadlock cannot occur.
Deadlock Avoidance: Using algorithms like Banker's Algorithm to avoid unsafe states.
Deadlock Detection and Recovery: Allowing deadlocks to occur, detecting them using techniques like resource allocation graphs, and recovering from them by terminating or rolling back processes.
Answer any two questions (2 x 5 = 10)
1. Explain Dining Philosopher Problem of Synchronizing with Diagram
The Dining Philosopher Problem is a classic synchronization problem introduced by Edsger Dijkstra. It is used to illustrate the challenges of allocating limited resources among multiple processes without causing deadlocks.
Problem Description:
There are five philosophers sitting around a circular table.
Each philosopher alternates between thinking and eating.
There are five forks on the table, one between each pair of adjacent philosophers.
A philosopher needs both adjacent forks to eat.
Challenges:
If every philosopher picks up the fork to their right at the same time, all of them will wait indefinitely, leading to a deadlock.
Solution:
To solve this problem, various synchronization techniques can be applied:
Resource Hierarchy Solution: Assign a unique number to each fork. Philosophers pick up the lower-numbered fork first and the higher-numbered fork second.
Arbitrator Solution: Use a mediator (a waiter) who ensures that a philosopher can pick up both forks before starting to eat.
Deadlock prevention involves designing the system in such a way that at least one of the necessary conditions for deadlock (Coffman conditions) is violated. The Coffman conditions are:
Mutual Exclusion: Resources are held exclusively by one process.
Hold and Wait: Processes holding resources can request additional resources.
No Preemption: Resources cannot be forcibly taken away from processes.
Circular Wait: A circular chain of processes exists, each waiting for a resource held by the next process in the chain.
Prevention Techniques:
Mutual Exclusion: Not applicable for resources that must be shared.
Hold and Wait: Require processes to request all resources they need before starting execution.
No Preemption: Allow the system to preempt resources from a process if it is waiting for others.
Circular Wait: Impose a strict ordering of resources and ensure that each process requests resources in increasing order.
3. Explain Paging in Detail with Diagram
Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory. This helps to avoid fragmentation and makes the use of memory more efficient. How Paging Works:
Logical Address Space: Divided into fixed-size pages.
Physical Address Space: Divided into fixed-size frames, each frame size is the same as the page size.
Translation Process:
The CPU generates a logical address.
The logical address is divided into two parts: the page number and the offset.
The page number is used to index into a page table.
The page table contains the base address of each page in physical memory.
The base address is added to the offset to get the physical address.
Easy to allocate memory as any free frame can be used.
Disadvantages:
May suffer from internal fragmentation if processes don't fully use the allocated pages.
Requires additional memory to store the page table.
4. Explain Deadlock Characterization
Deadlock Characterization refers to the conditions that must hold simultaneously for a deadlock to occur. These are known as the Coffman conditions:
Mutual Exclusion: Only one process can use a resource at a time.
Hold and Wait: A process holding at least one resource is waiting to acquire additional resources held by other processes.
No Preemption: Resources cannot be forcibly taken from a process; they must be released voluntarily.
Circular Wait: A set of processes exists such that each process is waiting for a resource held by the next process in the set, forming a circular chain.
Example:
Process P1 holds Resource R1 and requests Resource R2.
Process P2 holds Resource R2 and requests Resource R1.
Both processes cannot proceed, leading to a deadlock.
Prevention Strategies:
Mutual Exclusion: Make resources sharable if possible.
Hold and Wait: Require processes to request all resources at once.
No Preemption: Allow the system to preempt resources if necessary.
Circular Wait: Impose a linear ordering of resource types and ensure each process requests resources in an increasing order of enumeration.
These strategies aim to prevent the system from entering a deadlock state by ensuring that at least one of these conditions cannot hold.
