A deadlock occurs in a system when a set of processes • Banker's Algorithm (Deadlock Avoidance

are unable to proceed because each is waiting for a Algorithm)

resource held by another process in the set. There are
four necessary conditions for a deadlock to occur, • The Banker’s Algorithm is a deadlock
known as Coffman’s conditions: avoidance algorithm that ensures a system can
allocate resources safely without leading to
1. Mutual Exclusion – At least one resource must deadlock. It is named after a banking system
be held in a non-shareable mode (i.e., only where a bank never allocates all its available
one process can use the resource at a time). If cash, ensuring that it can satisfy future
another process requests the resource, it must requests.
wait.
•
2. Hold and Wait – A process holding at least one
resource is waiting for additional resources • Key Components of the Banker's Algorithm
held by other processes.
• Processes (P1, P2, ... Pn) – The set of
3. No Preemption – A resource cannot be processes requesting resources.
forcibly taken from a process; it must be
released voluntarily by the holding process. • Resources (R1, R2, ... Rm) – The types of
resources available.
4. Circular Wait – A set of processes must exist
where each process is waiting for a resource • Data Structures:
held by the next process in the chain, forming
a circular dependency. • Allocation Matrix: Resources currently
allocated to each process.
For a deadlock to occur, all four conditions must hold
simultaneously. Breaking any one of these conditions • Maximum Matrix: Maximum demand of each
can prevent or resolve a deadlock. process.

• Available Vector: Number of available

instances of each resource.
Fragmentation in Memory Management

Fragmentation occurs when memory is allocated

• Need Matrix: Remaining resources needed by
each process to complete.
inefficiently, causing wasted space. It is classified into
internal and external fragmentation.
• Need Matrix = Maximum – Allocation
1. Internal Fragmentation

• Occurs when a process is allocated more

memory than it actually needs.

• Happens in fixed-size partitioning or paging

when memory blocks are allocated in fixed
sizes.

• The unused memory within an allocated block

is wasted.

• Example: If a process needs 18 KB and is

allocated a 20 KB block, 2 KB is wasted as
internal fragmentation.

2. External Fragmentation

• Happens when free memory is divided into

small, non-contiguous blocks, preventing large
processes from being allocated memory, even
though the total free memory is sufficient.

• Occurs in dynamic memory allocation when

processes are allocated variable-sized memory
blocks.
Page Fault in Operating Systems Page Fault Handling Technologies

What is a Page Fault? To reduce page faults and improve system performance,
various page fault handling techniques are used:
A page fault occurs when a process tries to access a
page in memory that is not currently loaded in the main 1. Demand Paging
memory (RAM). This triggers an interrupt, and the
operating system (OS) must bring the required page • Pages are loaded only when needed (on-
from secondary storage (disk) into memory. demand) instead of loading the entire process
into memory.
Types of Page Faults
• Reduces initial memory load and improves
1. Minor Page Fault (Soft Page Fault) efficiency.
o The required page is not in the 2. Pre-Paging
process’s page table but is already in
memory (e.g., in the cache or • Anticipates future page accesses and loads
swapped but not mapped). multiple pages into memory before they are
needed.
o The OS only updates the page table
without disk access, making it fast. • Reduces the number of page faults but may
waste memory if unnecessary pages are
2. Major Page Fault (Hard Page Fault)
loaded.
o The required page is not in RAM and
3. Page Replacement Algorithms
must be loaded from disk, which is
slow. When RAM is full and a page fault occurs, the OS must
replace an existing page using these algorithms:
o The OS suspends the process,
fetches the page from disk, updates • FIFO (First In, First Out) – Replaces the oldest
the page table, and resumes page.
execution.
• LRU (Least Recently Used) – Replaces the least
3. Invalid Page Fault
recently accessed page.
o The process tries to access an illegal
• Optimal Page Replacement – Replaces the
page (e.g., accessing memory
page that will not be used for the longest time
outside its allocated space).
(theoretical).
o Results in a segmentation fault or
process termination. • Clock Algorithm (Second Chance) – Gives
pages a second chance before replacing them.

4. Copy-on-Write (COW)

• If multiple processes use the same page, a

copy is only made when one tries to modify it.

• Saves memory and reduces unnecessary page

faults.

5. Thrashing Control

• Thrashing occurs when excessive page faults

lead to constant swapping, slowing down the
system.

• The OS uses working set models and page

fault frequency algorithms to limit the number
of active pages per process.
Disadvantages of Paging in Operating Systems

While paging is widely used for memory management, it What is Demand Paging?
has several drawbacks:
Demand paging is a memory management technique
1. Internal Fragmentation where pages are loaded into RAM only when they are
needed, rather than loading the entire process into
• Fixed-size pages may not fully utilize allocated memory at once. This optimizes memory usage and
memory, leading to wasted space. reduces unnecessary disk I/O.

• Example: If a process needs 6 KB but the page How Demand Paging Works?
size is 4 KB, it will occupy two pages (8 KB
total), wasting 2 KB. 1. When a process is executed, only the essential
pages (e.g., the first instruction) are loaded
2. Increased Memory Access Time into memory.

• Paging adds an extra memory lookup because 2. If the process tries to access a page that is not
the OS must translate logical addresses to in RAM, a page fault occurs.
physical addresses using the page table.
3. The operating system (OS) fetches the missing
• This results in slower memory access page from secondary storage (disk) and loads
compared to contiguous allocation. it into RAM.

3. Page Table Overhead 4. The page table is updated, and the process
resumes execution.
• Each process requires a page table to map
logical pages to physical frames.
FIFO (First In, First Out) Page Replacement
• Large processes require large page tables,
Algorithm
consuming significant memory.
What is FIFO?
• To optimize, systems use multi-level paging or
TLB (Translation Lookaside Buffer), but this FIFO (First In, First Out) is a page replacement
algorithm used in virtual memory
increases complexity.
management. When a page needs to be
4. TLB Miss Penalty replaced, the oldest page (the one loaded
first) is removed from memory.
• The Translation Lookaside Buffer (TLB) speeds
up page translations, but if a TLB miss occurs,
the system must access the page table in How FIFO Works?
memory.
1. Pages are loaded into a queue in the order
• This increases the effective memory access they arrive.
time, reducing performance.
2. When a new page is needed and memory is
5. Page Replacement Overhead full, the oldest page (front of the queue) is
removed.
• If RAM is full, page replacement algorithms
(FIFO, LRU, etc.) must decide which page to 3. The new page is inserted at the end of the
remove. queue.

• This increases CPU overhead and can lead to

thrashing (excessive swapping).
 I/O Hardware in Computer Systems • . File Management is the process of
organizing, storing, and retrieving files on a
What is I/O Hardware?
computer or any storage device. It involves
Input/Output (I/O) hardware refers to the handling the creation, deletion, access, and
physical devices used for communication modification of files in a way that ensures data
between a computer system and the external is stored efficiently, securely, and in an easily
world. It includes input devices (e.g., accessible manner. File management is critical
keyboard, mouse), output devices (e.g., to operating systems as it allows users and
monitor, printer), and storage or applications to store and retrieve data
communication devices (e.g., hard drives, effectively.
network adapters).
Here are the main access methods used in file
management:

Types of I/O Hardware 1. Sequential Access

1. Input Devices Sequential access refers to accessing data in a file in a

linear order, starting from the beginning and reading or
Devices that send data into the computer. writing the data in sequence. This method is often used
Examples: for files where the data is processed in a specific order,
such as text files, log files, or media files like audio and
• Keyboard – For text input
video streams.
• Mouse/Trackpad – For pointer control 2. Direct (Random) Access

• Scanner – Converts physical documents into Direct or random access allows data to be read from or
digital format written to any part of the file without having to read the
entire file sequentially. This method provides more
• Microphone – Captures audio input flexibility and speed, especially when data retrieval or
modification doesn't need to follow a fixed order.
• Camera (Webcam) – Captures video input

2. Output Devices
• .

3. Indexed Access
Devices that send data out of the computer.
Examples: Indexed access is a method that uses an index or a
lookup table to locate and access data in a file. The file
• Monitor (Display Screen) – Shows visual
system stores an index (a data structure, like an array or
output
tree) that maps logical data addresses to the actual
• Printer – Produces hard copies of digital physical locations on the storage device.
documents 4. Hashed Access
• Speakers – Output sound Hashed access uses a hash function to calculate an index
that determines where data is stored in a file. In this
3. Storage Devices
method, the file is divided into a number of buckets or
Devices used to store data permanently or locations, and the hash function maps a key value
temporarily. Examples: (usually a piece of data) to a specific location in the file.

• Hard Disk Drive (HDD)/Solid-State Drive (SSD) 5. Contiguous Access

– Long-term storage Contiguous access is related to how files are allocated on
the storage medium. When a file is stored contiguously,
• USB Flash Drive – Portable storage
its data blocks are stored in consecutive sectors or blocks
• CD/DVD Drive – Optical storage on the storage device.

6. Multi-level Access
• Memory Cards (SD Cards) – Used in cameras,
phones Multi-level access is a more complex access method that
involves multiple levels of indexing or pointers to
Examples:
manage large, complex files. This method is often used
in systems like databases or large file systems.
Free space management is essential for efficiently
tracking and allocating free blocks of storage on a disk or
file system. Three commonly used methods for free
space management are bit vector (bitmap), linked list, Disk Scheduling Algorithms
and grouping. Let's explore each of these methods in
detail: There are several algorithms used for disk scheduling,
each with its own advantages and trade-offs in terms of
1. Bit Vector (Bitmap) efficiency and complexity. The most common disk
A bit vector, also known as a bitmap, is one of the most scheduling algorithms are:
efficient ways to manage free space. It uses a bit array 1. First-Come, First-Served (FCFS)
where each bit represents a fixed-size block or sector on
the disk. If a bit is set to 1, the corresponding block is • Description: This is the simplest disk
occupied; if the bit is set to 0, the block is free. scheduling algorithm. Requests are processed
in the order they arrive, without any
Linked List (Free List)
reordering.
In the linked list method of free space management, the
free blocks on the disk are maintained in a linked list.
• How it works: If request 1 arrives before
request 2, the disk will handle request 1 first,
Each free block contains a pointer to the next free block,
then request 2, and so on.
creating a chain of free blocks. When a block is
allocated, it is removed from the linked list, and when a
•
block is freed (deleted), it is added back to the list.
2. Shortest Seek Time First (SSTF)
Grouping
• Description: This algorithm selects the request
Grouping is an optimization of the linked list method,
that is closest to the current position of the
where groups of free blocks are maintained in a list, and
disk head.
each group points to the first free block in the group.
The idea is to reduce the overhead of traversing • How it works: For every incoming request, the
individual blocks by managing groups of blocks together. disk will choose the request that minimizes the
distance the disk head must travel.

SCAN (Elevator Algorithm)

Disk management refers to the process of managing the • Description: In SCAN, the disk arm moves in
storage space on a computer’s disk (hard disk, solid-state one direction (either from the outermost to
drive, or other storage devices). It involves organizing, the innermost track or vice versa), servicing
allocating, and maintaining the storage medium to requests along the way. Once it reaches the
ensure efficient and reliable storage of data. Disk end, it reverses direction.
management is crucial for the operating system (OS) to
handle file storage, improve performance, ensure data • How it works: When the disk arm reaches one
integrity, and manage space utilization. end of the disk, it reverses direction and
continues servicing requests on its return trip.
Disk management includes several important activities
such as disk partitioning, disk scheduling, storage C-SCAN (Circular SCAN)
allocation, managing free space, handling I/O
• Description: Similar to SCAN, but in C-SCAN,
operations, and implementing error recovery
the disk arm only moves in one direction
mechanisms.
(either outward or inward) and jumps back to
Disk reliability refers to the ability of a disk storage the beginning once it reaches the end.
system (such as a hard disk drive (HDD) or solid-state
drive (SSD)) to consistently perform its intended • How it works: After servicing all requests in
function over time without failure. Reliability is crucial one direction, the arm jumps to the other end
for ensuring data integrity, availability, and the overall of the disk and starts moving in the same
performance of a system that depends on disk storage. direction again.
. Processes Preemptive Scheduling

A process is an instance of a program in execution. It is a Preemptive scheduling is a type of scheduling where the
running program that has its own memory space, operating system can interrupt a running process to
registers, and other resources needed to execute the assign the CPU to another process. This interruption can
instructions of the program. A process has a well-defined occur at any point in the execution of a process, based
lifecycle, including creation, execution, and termination. on certain conditions like time slices (quantum) or
priority changes.
2. Process Control Block (PCB)
Key Characteristics of Preemptive Scheduling:
A Process Control Block (PCB) is a data structure that
contains important information about the process. The • Process Interruption: The OS can forcibly
PCB is used by the operating system to manage suspend a running process, even in the middle
processes. Each process in the system has its own PCB, of its execution, to give CPU time to another
which is created when the process is initialized and process.
destroyed when the process terminates.
• Fairness: Preemptive scheduling ensures that
Threads all processes get a fair share of CPU time. This
is particularly useful in time-sharing systems
A thread is the smallest unit of execution within a
where many processes run concurrently.
process. A process may consist of one or more threads.
Each thread within a process shares the same memory • Responsive: It is more responsive, as higher-
space and resources but has its own execution context priority tasks can preempt lower-priority tasks.
(e.g., program counter, registers).
• Context Switching: Preemption requires the
Process Scheduling
OS to perform a context switch, saving the
Process scheduling refers to the method by which the state of the currently running process and
operating system decides which process or thread to loading the state of the new process.
execute at any given time. Scheduling is important to
ensure that the CPU is used efficiently and that each Non-Preemptive Scheduling
process gets a fair share of the CPU time.
Non-preemptive scheduling is a type of scheduling
Key components of process scheduling: where the operating system does not forcibly interrupt a
running process. Once a process starts executing, it runs
• CPU Scheduling: Determines which process or to completion (or until it voluntarily releases the CPU,
thread gets to use the CPU. such as when it performs I/O operations or terminates).

• I/O Scheduling: Determines which process or Key Characteristics of Non-Preemptive Scheduling:

thread gets access to I/O devices, such as disks
or network interfaces.
• No Process Interruption: A running process
will continue to execute until it voluntarily
• Rate-Monotonic Scheduling (RM)
yields the CPU (e.g., by blocking for I/O or
• Rate-Monotonic Scheduling (RM) is a terminating).
priority-based preemptive scheduling
algorithm for real-time tasks, where tasks with
• Simplicity: Non-preemptive scheduling is
simpler to implement compared to preemptive
shorter periods are assigned higher priorities.
scheduling because the OS doesn’t need to
In RM, each task is periodically executed, and
manage the complexity of context switching
the system must ensure that the tasks meet their
and handling preemptions.
deadlines based on the priority assigned to
them. • Inefficiency in Time-Sharing: In systems with
many processes, non-preemptive scheduling
can lead to inefficiencies since a long-running
Earliest Deadline First (EDF) process could monopolize the CPU, preventing
other processes from executing.
Earliest Deadline First (EDF) is a dynamic priority • Fairness: Since the OS cannot forcibly take
scheduling algorithm where the priority of a task is control from a process, there is no guarantee
determined by its deadline. The task with the earliest that each process will get a fair share of CPU
deadline is given the highest priority at any point in
time, especially if one process monopolizes it.
time. EDF is used in real-time systems where •
tasks have deadlines and may not necessarily be periodic.