DEADLOCKS
Deadlock: Detailed Explanation
A deadlock is a condition in operating systems where a set of processes becomes permanently blocked
because each process is waiting for a resource that is held by another process in the same set. This
results in a cyclic dependency, preventing any process from proceeding. Deadlocks are critical issues
in multiprogramming systems where resource sharing is common.
Necessary Conditions for Deadlock (Coffman Conditions)
1. Mutual Exclusion: At least one resource must be held in a non-shareable mode, meaning only one
process can use the resource at a time.
2. Hold and Wait: A process is holding at least one resource and is waiting to acquire additional
resources currently held by other processes.
3. No Preemption: Resources cannot be forcibly taken away from a process; they must be released
voluntarily.
4. Circular Wait: A closed chain of processes exists where each process is waiting for a resource held
by the next process in the chain.
Deadlock Prevention
Deadlock prevention strategies aim to structurally negate at least one of the necessary conditions. For
example, mutual exclusion can be avoided by making resources sharable where possible. The
hold-and-wait condition can be prevented by requiring processes to request all resources at once. No
preemption can be avoided by forcibly reclaiming resources. Circular wait can be prevented by
imposing an ordering on resource acquisition.
Resource Allocation Graph
A Resource Allocation Graph (RAG) is a directed graph used to represent the allocation of resources to
processes. Nodes represent processes and resource types. Edges represent allocation and request
relationships. A cycle in the graph indicates a potential deadlock, especially in systems with
single-instance resources.
Deadlock Avoidance
Deadlock avoidance algorithms ensure that the system never enters an unsafe state. The system
dynamically examines resource allocation requests and decides whether granting them would lead to a
safe or unsafe state.
Banker's Algorithm
The Banker’s Algorithm is a deadlock avoidance technique that simulates resource allocation to ensure
that a safe sequence exists. It uses data structures such as Available, Max, Allocation, and Need
matrices. A safe state is one in which all processes can complete without leading to deadlock.
Deadlock Detection
Deadlock detection algorithms allow the system to enter a deadlock state and then detect it. For
single-instance resources, a cycle detection algorithm in a wait-for graph is used. For multiple-instance
resources, matrix-based detection algorithms are used.
MEMORY MANAGEMENT
Memory Management Overview
Memory management is a crucial function of an operating system responsible for managing primary
memory. It keeps track of each byte in memory and determines which process will use which portion.
Memory Hardware
Memory hierarchy includes registers, cache memory, main memory, and secondary storage. Each level
differs in speed, cost, and capacity.
Address Binding
Address binding can occur at compile time, load time, or execution time. Execution-time binding allows
dynamic relocation using hardware support like MMU.
Logical vs Physical Address
Logical address is generated by CPU and is also known as virtual address. Physical address refers to
the actual address in main memory.
Contiguous Memory Allocation
In contiguous allocation, each process occupies a single continuous block. Techniques include fixed
partitioning and dynamic partitioning.
Non-Contiguous Allocation
Non-contiguous allocation allows processes to be divided into parts and loaded into non-adjacent
memory locations. Paging and segmentation are key techniques.
Fragmentation
Internal fragmentation occurs when allocated memory is slightly larger than required. External
fragmentation occurs when free memory is divided into small blocks.
Paging
Paging eliminates external fragmentation by dividing memory into fixed-size pages and frames.
Address translation is performed using page tables.
TLB (Translation Lookaside Buffer)
TLB is a high-speed associative cache that stores recent translations of virtual to physical addresses,
reducing access time.
Page Table
Page tables maintain mappings between logical pages and physical frames. Multi-level page tables are
used for large address spaces.
Swapping
Swapping is the process of moving processes between main memory and backing store to free
memory.
Virtual Memory
Virtual memory allows processes to execute even if they are not entirely in main memory, providing an
abstraction of a large memory.
Demand Paging
Demand paging loads pages into memory only when they are required, reducing memory usage.
Page Replacement Algorithms
Algorithms include FIFO, LRU, Optimal, and Clock. These determine which page to replace when
memory is full.
Thrashing
Thrashing occurs when the system spends more time swapping pages than executing processes,
leading to performance degradation.
Belady’s Anomaly
Belady’s anomaly is a phenomenon where increasing the number of page frames results in an increase
in page faults in certain algorithms like FIFO.
DISK MANAGEMENT
Disk Structure
A disk consists of platters coated with magnetic material. Each platter has tracks divided into sectors.
Cylinders are sets of tracks aligned vertically.
Disk Scheduling Algorithms
Disk scheduling algorithms optimize seek time. Common algorithms include FCFS, SSTF, SCAN,
C-SCAN, LOOK, and C-LOOK.
Boot Block
Boot block contains the bootstrap loader that initializes the system and loads the operating system
kernel.
Bad Blocks
Bad blocks are defective disk sectors. They are handled using sector sparing or sector slipping
techniques.
FILE SYSTEM
File Attributes
File attributes include name, identifier, type, location, size, protection, timestamps, and owner
information.
File Operations
Basic file operations include create, open, read, write, reposition, close, delete, and truncate.
File Allocation Methods
Contiguous allocation provides fast access but suffers from fragmentation. Linked allocation removes
fragmentation but is slow. Indexed allocation uses an index block for efficient access.
Access Methods
Sequential access processes data in order, direct access allows random access, and indexed access
uses an index for efficient retrieval.