OPERATING SYSTEM

[Link] CSE | Sem-4 | Complete Study Notes

Previous Year Questions | Most Repeated Topics | Detailed Answers

Subject Code: BTCS-401 / BTCS-402-18

Max Marks: 60 | Time: 3 Hours
EXAM PATTERN & MARKING SCHEME
Section Questions Marks Each Attempt Total Marks
Section A 10 Short 2 Marks All 10 20 Marks
Questions (Compulsory)
Section B 5 Questions 5 Marks Any 4 20 Marks
Section C 3 Questions 10 Marks Any 2 20 Marks
Total 60 Marks

MOST REPEATED TOPICS (Frequency Analysis)

Topic Times Asked Section
Disk Scheduling (FCFS, SSTF, 8+ times B&C
SCAN, C-SCAN)
Page Replacement Algorithms 7+ times B&C
(FIFO, LRU, Optimal)
Process Control Block (PCB) 7+ times A&B
Deadlock - Definition, 7+ times A&B
Conditions, Prevention
Virtual Memory 6+ times A&B
CPU Scheduling Algorithms 6+ times B&C
(FCFS, SJF, Priority, RR)
OS Structures (Layered, 5+ times B&C
Monolithic, Microkernel)
Semaphores & Synchronization 5+ times A&B
Paging vs Segmentation 5+ times A&B
Producer-Consumer Problem 4+ times B&C
File Allocation Methods 4+ times B&C
Banker's Algorithm 4+ times B&C
Internal vs External 4+ times A
Fragmentation
Process States 4+ times A&B
Linux OS / UNIX 4+ times B&C
SECTION - A: SHORT ANSWER QUESTIONS (2-3 Marks
Each)
These questions are compulsory. Write concise, clear answers.

Q1. Define Operating System Services

An Operating System (OS) provides a set of services to users and programs to make computing easier
and more efficient. These services act as an interface between user programs and hardware.
Main OS Services:
• Program Execution: OS loads programs into memory and runs them.
• I/O Operations: OS manages input/output between programs and devices.
• File System Manipulation: OS allows programs to read, write, create and delete files.
• Communication: OS enables processes to communicate with each other (IPC).
• Error Detection: OS detects errors in CPU, memory, I/O devices and corrects them.
• Resource Allocation: OS allocates CPU, memory, and I/O devices among processes.
• Accounting: OS keeps track of which users use how many resources.
• Protection and Security: OS ensures that only authorized users access resources.

Q2. What is a System Call?

A system call is a mechanism through which a user-level program requests a service from the
operating system's kernel. It is the interface between a running program and the OS.
When a program needs to perform privileged operations (like reading a file, creating a process, or
accessing hardware), it cannot do so directly. Instead, it makes a system call, which transfers control to
the OS kernel.
Common Examples of System Calls:
• fork() - Creates a new process
• exec() - Executes a new program
• read() / write() - File I/O operations
• open() / close() - File management
• exit() - Terminates a process
• wait() - Waits for a child process to finish
Note: System calls are also called 'software interrupts' or 'traps' because they cause a trap into the OS kernel.

Q3. What is Context Switching?

Context switching is the process of saving the state (context) of a currently running process and loading
the saved state of a new process so that the CPU can switch from one process to another.
Steps in Context Switching:
1. The OS saves the current process state (registers, program counter, etc.) into its PCB.
 2. The scheduler selects the next process to run.
3. The OS loads the state of the new process from its PCB into the CPU registers.
4. The new process resumes execution from where it left off.
Overhead: Context switching is pure overhead — no useful work is done during the switch. The time
taken is called context switch time.
Used in: Multiprogramming and Time-sharing systems use context switching extensively.

Q4. What is CPU Scheduling? State its Objectives.

CPU Scheduling is the process of deciding which process in the ready queue gets the CPU next. Since
the CPU can only run one process at a time, the OS must schedule processes efficiently.
Objectives of CPU Scheduling:
• Maximum CPU Utilization: Keep the CPU busy as much as possible (ideally 100%).
• Maximum Throughput: Execute as many processes per unit time as possible.
• Minimum Turnaround Time: Reduce time from process submission to completion.
• Minimum Waiting Time: Reduce the time a process spends waiting in the ready queue.
• Minimum Response Time: For interactive systems, reduce time from request to first response.
• Fairness: Every process should get a fair share of CPU time.

Q5. Define Mutual Exclusion

Mutual Exclusion is a property that ensures only ONE process can access a shared resource (like a
critical section) at a time. If one process is inside the critical section, all other processes must wait until
it exits.
It is one of the four necessary conditions for deadlock (along with Hold and Wait, No Preemption, and
Circular Wait).
Example: If two processes try to print at the same time, the output will be mixed up. Mutual exclusion
ensures only one process uses the printer at a time.
Implementation: Achieved using semaphores, mutex locks, monitors, or hardware instructions like
Test-and-Set.

Q6. What is a Semaphore?

A Semaphore is an integer variable used for process synchronization. It is used to control access to
shared resources and prevent race conditions.
A semaphore supports two atomic operations:
• wait(S) or P(S): Decrements the semaphore value. If value < 0, the process is blocked.
• signal(S) or V(S): Increments the semaphore value. If processes are waiting, one is woken up.
Types of Semaphores:
• Binary Semaphore (Mutex): Value is either 0 or 1. Used for mutual exclusion.
• Counting Semaphore: Value can be any non-negative integer. Used to control access to a
resource pool with multiple instances.
Note: Semaphores were introduced by E.W. Dijkstra. The P() and V() operations are always atomic (indivisible).
Q7. Define Deadlock
Deadlock is a situation where two or more processes are permanently blocked (waiting forever), each
waiting for a resource that is held by another process in the set.
Example: Process P1 holds Resource R1 and waits for R2. Process P2 holds R2 and waits for R1.
Neither can proceed — this is deadlock.
Four Necessary Conditions for Deadlock (all four must hold simultaneously):
• Mutual Exclusion: Resources are non-shareable (only one process can use at a time).
• Hold and Wait: A process holds at least one resource and waits for more.
• No Preemption: Resources cannot be forcibly taken from a process.
• Circular Wait: A circular chain of processes exists where each waits for the next.

Q8. What is Internal Fragmentation?

Internal Fragmentation occurs when memory is allocated to a process but the allocated memory is
larger than what the process actually needs. The unused space within the allocated block is wasted.
Example: A process needs 18 KB. The OS allocates 20 KB (next fixed block size). The remaining 2 KB
inside the allocated block is wasted — this is internal fragmentation.
Difference from External Fragmentation:
Aspect Internal Fragmentation External Fragmentation
Location of wasted memory Inside allocated block Outside allocated blocks
Cause Fixed-size allocation Variable-size allocation
Found in Paging Segmentation, Dynamic
allocation
Solution Smaller block sizes Compaction, Paging

Q9. What is a Device Driver?

A Device Driver is a special software program that acts as an interface between the operating system
and a hardware device. It translates OS commands into device-specific instructions.
Functions of Device Drivers:
• Translates OS I/O requests into hardware-specific commands.
• Manages communication between the OS and the device.
• Handles device-specific error conditions.
• Controls device initialization and configuration.
Examples: Printer driver, graphics card driver, keyboard driver, network adapter driver.
Note: Device drivers run in kernel mode and have direct access to hardware registers.
Q10. What is Virtual Memory?
Virtual Memory is a memory management technique that allows a process to use more memory than is
physically available in RAM. It creates an illusion of a very large main memory by using secondary
storage (hard disk) as an extension of RAM.
Key Concepts:
• Pages that are currently needed are loaded into RAM.
• Pages not currently needed are stored on disk (in the swap space).
• When a needed page is not in RAM, a page fault occurs and it is loaded from disk.
Advantages of Virtual Memory:
• Allows running of programs larger than physical memory.
• Multiple programs can run simultaneously even with limited RAM.
• Increases multiprogramming degree.
• Provides memory protection and isolation between processes.

Q11. Differentiate between Multiprogramming and Time Sharing

Aspect Multiprogramming Time Sharing
Goal Maximize CPU utilization Minimize response time for
users
Mechanism One job runs until it waits for I/O CPU switches rapidly between
jobs
User Interaction No direct interaction Interactive - user gets fast
response
Switching Only when process waits for I/O Switched at fixed time intervals
(quantum)
Example Batch processing systems Unix, Linux time-sharing
systems

Q12. What is a Process and Process States?

A Process is a program in execution. A program is a passive entity (code on disk), while a process is an
active entity (program loaded in memory with resources).
Process States:
• New: Process is being created.
• Ready: Process is loaded in memory, waiting for CPU.
• Running: Process is currently executing on CPU.
• Waiting/Blocked: Process is waiting for I/O or an event to complete.
• Terminated: Process has finished execution.
Q13. What is Thrashing?
Thrashing is a situation where the OS spends more time swapping pages in and out of memory than
actually executing processes. It causes severe performance degradation.
Cause: When too many processes are in memory and each process has fewer frames than needed,
processes keep causing page faults. The CPU is mostly idle while pages are being swapped.
Solutions to Thrashing:
• Reduce the degree of multiprogramming (reduce number of active processes).
• Use the Working Set Model to determine how many frames each process needs.
• Use Page Fault Frequency (PFF) algorithm to control frame allocation.

Q14. What is IPC (Inter-Process Communication)?

IPC refers to mechanisms that allow processes to communicate and synchronize with each other. Two
main models:
• Shared Memory: Processes share a region of memory and communicate by reading/writing to it.
Faster but requires synchronization.
• Message Passing: Processes communicate by sending and receiving messages via the OS.
Simpler but slower due to OS involvement.
Common IPC mechanisms: Pipes, Sockets, Semaphores, Shared Memory, Message Queues, Signals.

Q15. What is the difference between Kernel and Shell?

Aspect Kernel Shell
Definition Core of the OS that manages Interface between user and
hardware resources kernel
Type Software (runs in kernel mode) Software (runs in user mode)
Function Process, memory, I/O Interprets and executes user
management commands
Access Direct hardware access No direct hardware access
Examples Linux kernel, Windows NT Bash, Zsh, CMD, PowerShell
kernel

Q16. What is Caching?

Caching is the process of storing frequently used data in a faster storage (cache) so that future
requests for that data can be served faster. Cache is smaller but much faster than main memory.
• CPU Cache (L1, L2, L3): Stores frequently accessed data/instructions close to CPU.
• Disk Cache: Stores frequently accessed disk blocks in RAM.
• Web Cache: Stores web pages to reduce network access time.
Q17. What is a Process Control Block (PCB)?
A PCB is a data structure maintained by the OS for each process. It contains all information needed to
manage a process.
Contents of PCB:
• Process ID (PID): Unique identifier for the process.
• Process State: Current state (new, ready, running, waiting, terminated).
• Program Counter: Address of the next instruction to execute.
• CPU Registers: Values of all CPU registers (for context switching).
• CPU Scheduling Information: Priority, scheduling queue pointers.
• Memory Management Information: Page tables, segment tables, base/limit registers.
• I/O Status Information: List of I/O devices allocated, open files.
• Accounting Information: CPU time used, time limits, account numbers.

Q18. Differentiate Seek Time vs Rotational Latency

Aspect Seek Time Rotational Latency
Definition Time to move disk arm to Time for disk to rotate to correct
correct track sector
Controlled by Disk scheduling algorithm Disk rotation speed (RPM)
Average value 3-15 ms typically Half of rotation time
Optimization Using SSTF, SCAN algorithms Cannot be directly optimized by
OS
SECTION B & C: DETAILED ANSWERS (5-10 Marks)

TOPIC 1: Operating System Structures (Layered, Monolithic, Microkernel)

An OS can be designed using different architectural approaches. The three main structures are:

1. Monolithic Structure (Simple/Traditional)

In a monolithic OS, the entire operating system is a single large program running in kernel mode. All
OS services (process management, file system, memory management, device drivers) are in one big
block of code.
Working:
• All OS services run in kernel space.
• Any part of the kernel can directly call any other part.
• No separation between different components.
Advantages:
• Very fast — direct communication between components, no message passing.
• Simple to design initially.
Disadvantages:
• Very difficult to maintain and debug — a bug anywhere can crash the entire system.
• Not modular — hard to modify one component without affecting others.
• Poor reliability and security — no isolation between components.
Examples: MS-DOS, early versions of UNIX, Linux (modified monolithic)

2. Layered Structure
The OS is divided into a number of layers (levels), each built on top of the lower layers. The bottom
layer (layer 0) is the hardware, and the top layer (layer N) is the user interface.
Layer Structure:
• Layer 0: Hardware (CPU, memory, I/O devices)
• Layer 1: CPU Scheduling
• Layer 2: Memory Management
• Layer 3: I/O Device Management
• Layer 4: File Management
• Layer 5: User Interface (Shell)
Working: Each layer only uses services of the layer directly below it. Layer N can call Layer N-1 but
NOT Layer N-2 directly.
Advantages:
• Easy to debug — test each layer independently from bottom to top.
• Modular design — easy to modify one layer without affecting others.
• Easy to verify correctness layer by layer.
Disadvantages:
• Slower than monolithic — requests must pass through multiple layers.
• Difficult to define what belongs in each layer.
• Performance overhead due to multiple layer crossings.
Examples: THE OS (Dijkstra), MULTICS

3. Microkernel Structure
In a microkernel approach, the kernel is kept as small as possible. Only essential services (memory
management, CPU scheduling, IPC) run in the kernel. All other services (file system, device drivers,
network) run as user-space processes called servers.
Services in Microkernel (Kernel Space):
• Inter-process Communication (IPC)
• Basic Memory Management
• Basic CPU Scheduling
Services in User Space (Servers):
• File System Server
• Device Driver Servers
• Network Protocol Server
Advantages:
• Very reliable — if a server crashes, it does not crash the kernel.
• More secure — services run in user mode with limited privileges.
• Easier to extend — add new services without modifying the kernel.
• Better portability — small kernel is easier to port to new hardware.
Disadvantages:
• Slower performance — communication between user-space servers and kernel requires
message passing (IPC overhead).
• More complex IPC mechanisms needed.
Examples: MINIX, QNX, macOS/Darwin, Windows NT (hybrid)

Feature Monolithic Layered Microkernel

Size of Kernel Very large Medium Very small
Performance Fastest Moderate Slowest (IPC
overhead)
Reliability Low Medium High
Extensibility Difficult Moderate Easy
Security Low Medium High
Example Linux, UNIX THE OS MINIX, QNX, macOS
TOPIC 2: Process States and Process Control Block (PCB)

Process States
A process goes through different states during its lifetime:
• New: The process is being created. Resources are being allocated.
• Ready: The process is loaded in memory and waiting for CPU. Multiple processes can be in
ready state simultaneously (stored in ready queue).
• Running: The process is currently being executed by the CPU. In a single-CPU system, only
ONE process can be in running state at a time.
• Waiting/Blocked: The process is waiting for some event (I/O completion, signal, semaphore). It
cannot use CPU even if CPU is free.
• Terminated/Exit: The process has finished execution. OS deallocates its resources.

State Transitions:
• New -> Ready: Process creation complete, admitted to ready queue.
• Ready -> Running: CPU scheduler dispatches the process.
• Running -> Waiting: Process requests I/O or waits for event.
• Running -> Ready: Process preempted (time quantum expired, higher priority process arrives).
• Waiting -> Ready: I/O or event completes, process moves back to ready queue.
• Running -> Terminated: Process finishes execution.

Process Control Block (PCB)

The PCB is the 'identity card' of a process. It is a data structure maintained by the OS to store all
information about a process. When a context switch happens, the current process's state is saved in its
PCB.
Fields stored in PCB:
• Process ID (PID): Unique number identifying the process.
• Process State: Current state (ready/running/waiting/terminated).
• Program Counter (PC): Address of the next instruction to be executed.
• CPU Registers: Contents of all CPU registers — accumulator, index registers, stack pointer, etc.
• CPU Scheduling Info: Process priority, scheduling queue pointers, scheduling algorithm
parameters.
• Memory Management Info: Base/limit registers, page tables, segment tables.
• Accounting Info: CPU time used so far, wall-clock time, time limits, user account number.
• I/O Status Info: List of I/O devices allocated, list of open files, pending I/O operations.
Role in Context Switching: When process P1 is being replaced by P2, P1's entire state is saved into
P1's PCB. Then P2's state is loaded from P2's PCB. This allows P1 to resume exactly where it stopped.
TOPIC 3: CPU Scheduling Algorithms
CPU Scheduling determines which process in the ready queue gets the CPU next. Key algorithms:

1. FCFS (First Come First Served)

The process that arrives first gets the CPU first. It is non-preemptive — once started, a process runs
until it finishes or blocks.
Example: Consider processes with burst times:
Process Arrival Time Burst Time
P1 0 24 ms
P2 1 3 ms
P3 2 3 ms

Gantt Chart: P1 (0-24) | P2 (24-27) | P3 (27-30)

• Waiting Time: P1=0, P2=23, P3=25
• Average Waiting Time = (0+23+25)/3 = 16 ms
• Problem: Convoy effect — short processes wait behind a long process.

2. SJF (Shortest Job First)

The process with the smallest burst time is scheduled next. Gives minimum average waiting time —
optimal for minimizing waiting time.
• Non-preemptive SJF: Once CPU is given, process runs to completion.
• Preemptive SJF (SRTF - Shortest Remaining Time First): If a new process arrives with smaller
burst time than remaining time of current process, current process is preempted.
Problem: Cannot always know the burst time in advance — must be estimated.

3. Priority Scheduling
Each process is assigned a priority number. The process with the highest priority (usually lowest
number = highest priority) gets the CPU.
• Can be preemptive or non-preemptive.
• Problem: Starvation — low priority processes may never get CPU if high priority processes keep
arriving.
• Solution: Aging — gradually increase the priority of waiting processes over time.

4. Round Robin (RR)

Each process gets the CPU for a fixed time interval called time quantum (q). After q milliseconds, the
process is preempted and sent to the end of the ready queue.
• Designed for time-sharing systems.
• If quantum is large, RR behaves like FCFS.
 • If quantum is too small, context switching overhead becomes significant.
• Ideal quantum: 80% of CPU bursts should be shorter than quantum.
Advantage: Good response time for interactive systems. Fair — every process gets CPU regularly.

5. Multilevel Queue Scheduling

The ready queue is divided into multiple queues based on process type:
• System processes (highest priority)
• Interactive processes
• Interactive editing processes
• Batch processes (lowest priority)
Each queue has its own scheduling algorithm. Processes cannot move between queues.

6. Multilevel Feedback Queue Scheduling

Similar to Multilevel Queue but processes CAN move between queues based on their behavior:
• A process using too much CPU time is moved to a lower priority queue.
• A process waiting too long is moved to a higher priority queue (aging).
• This is the most complex but most flexible scheduling algorithm.
• Used in modern OS like Unix, Windows.
TOPIC 4: Deadlock - Definition, Conditions, Prevention, and Banker's
Algorithm

Deadlock Definition
Deadlock is a state where a set of processes are permanently blocked because each process is waiting
for a resource that is held by another process in the set.

Four Necessary Conditions for Deadlock

ALL four conditions must hold simultaneously for deadlock to occur:
• 1. Mutual Exclusion: At least one resource must be held in a non-shareable mode — only one
process can use it at a time.
• 2. Hold and Wait: A process must be holding at least one resource and waiting to acquire more
resources held by other processes.
• 3. No Preemption: Resources cannot be forcibly taken away from a process. A process must
voluntarily release a resource.
• 4. Circular Wait: A circular chain of processes exists P1->P2->P3->...->Pn->P1, where each Pi
waits for a resource held by P(i+1).

Deadlock Handling Methods

Three main approaches to handle deadlock:
• 1. Deadlock Prevention: Ensure at least one of the four conditions cannot hold. (Most restrictive
method)
• 2. Deadlock Avoidance: Use algorithms (like Banker's) to ensure system never enters unsafe
state.
• 3. Deadlock Detection and Recovery: Allow deadlock to occur, then detect and break it.

Deadlock Prevention (Eliminating Each Condition)

• Eliminate Mutual Exclusion: Make resources shareable where possible (e.g., read-only files).
Not always possible.
• Eliminate Hold and Wait: Require processes to request all resources at once before starting. OR
release all held resources before requesting new ones. Disadvantage: low resource utilization
and starvation.
• Allow Preemption: If a process requests a resource not available, preempt all its held resources.
Works for resources like CPU registers but not for printers.
• Eliminate Circular Wait: Impose a total ordering on resource types. Each process must request
resources only in increasing order of resource type number. Circular wait cannot form.
Banker's Algorithm (Deadlock Avoidance)
The Banker's Algorithm was developed by Dijkstra. It is used for deadlock avoidance. The OS checks
before allocating resources whether doing so will leave the system in a safe state. If not, the process
must wait.
Key Concepts:
• Safe State: A state is safe if there exists a sequence of all processes such that each process
can get the resources it needs using currently available resources + resources held by
processes that come before it in the sequence.
• Unsafe State: A state from which deadlock is possible (not guaranteed).

Data Structures used:

• n = number of processes, m = number of resource types
• Available[m]: Number of available instances of each resource type.
• Max[n][m]: Maximum demand of each process for each resource type.
• Allocation[n][m]: Resources currently allocated to each process.
• Need[n][m] = Max[n][m] - Allocation[n][m]: Remaining resource need of each process.

Example of Banker's Algorithm:

Suppose we have 5 processes (P0-P4) and 3 resource types (A=10, B=5, C=7 total instances):
Process Allocation A,B,C Max A,B,C Need A,B,C
P0 0,1,0 7,5,3 7,4,3
P1 2,0,0 3,2,2 1,2,2
P2 3,0,2 9,0,2 6,0,0
P3 2,1,1 2,2,2 0,1,1
P4 0,0,2 4,3,3 4,3,1

Available = (10-7, 5-2, 7-5) = (3, 3, 2)

Safe Sequence: P1 -> P3 -> P4 -> P0 -> P2
The system is in a safe state since a safe sequence exists.
TOPIC 5: Producer-Consumer Problem and Process Synchronization

Critical Section Problem

A critical section is a part of a program where shared resources (variables, files, data) are accessed. If
multiple processes enter their critical sections simultaneously, a race condition occurs, leading to
incorrect results.
Requirements for a Critical Section Solution:
• 1. Mutual Exclusion: Only one process can be in its critical section at a time.
• 2. Progress: If no process is in critical section, the decision about who enters must be made in
finite time.
• 3. Bounded Waiting: There must be a bound on the number of times other processes can enter
their critical sections after a process has requested entry.

Producer-Consumer Problem
The Producer-Consumer problem (also called Bounded Buffer problem) is a classic synchronization
problem.
Setup:
• Producer: Generates data items and puts them in a shared buffer.
• Consumer: Takes data items from the buffer and processes them.
• Buffer: Has a fixed size (bounded buffer). Can hold N items.
Problems to solve:
• Producer must not add to a full buffer (wait if buffer full).
• Consumer must not take from an empty buffer (wait if buffer empty).
• Producer and Consumer must not access the buffer simultaneously.

Solution using Semaphores:

• mutex (binary semaphore, initial value = 1): Ensures mutual exclusion on buffer access.
• empty (counting semaphore, initial value = N): Counts empty buffer slots.
• full (counting semaphore, initial value = 0): Counts filled buffer slots.

Producer Code:
while(true) {
produce item;
wait(empty); // wait for empty slot
wait(mutex); // lock buffer
add item to buffer;
signal(mutex); // unlock buffer
signal(full); // signal item added
}
Consumer Code:
while(true) {
wait(full); // wait for filled slot
wait(mutex); // lock buffer
 remove item from buffer;
signal(mutex); // unlock buffer
signal(empty); // signal empty slot
consume item;
}

Dining Philosophers Problem

Five philosophers sit around a table. Each philosopher needs two forks (shared with neighbors) to eat.
A philosopher alternates between thinking and eating.
Problem: All philosophers pick up their left fork simultaneously — deadlock! No one can get the right
fork.
Solution: Allow at most 4 philosophers to sit at the table at once, OR use an odd-even strategy — odd
philosophers pick left fork first, even pick right fork first.
TOPIC 6: Memory Management - Paging and Segmentation

Paging
Paging divides physical memory into fixed-size blocks called frames and logical memory into same-size
blocks called pages. Any page can be placed in any free frame — no external fragmentation.
Key Concepts:
• Page Size: Fixed (e.g., 4 KB). Page size = Frame size.
• Page Table: A table maintained for each process that maps page numbers to frame numbers.
• Logical Address = Page Number (p) + Page Offset (d)
• Physical Address = Frame Number (f) + Page Offset (d)
• Internal Fragmentation: Last page may not fill a complete frame. Average waste = half a page
per process.
• No External Fragmentation: Any free frame can be used for any page.

Segmentation
Segmentation divides logical memory into variable-size segments based on the logical structure of a
program (code, data, stack, heap).
Key Concepts:
• Each segment has a name/number and a length.
• Segment Table: Maps segment numbers to base address and limit (size) in physical memory.
• Logical Address = Segment Number (s) + Offset (d)
• Physical Address = Base[s] + d (if d < limit[s])
• External Fragmentation: Variable-size segments cause holes in memory.
• No Internal Fragmentation: Segments are exactly the size needed.

Feature Paging Segmentation

Block size Fixed (pages) Variable (segments)
Logical view No relation to program structure Matches program's logical
structure
Internal fragmentation Yes (last page) No
External fragmentation No Yes
Address Page# + Offset Segment# + Offset
User visibility Not visible to programmer Visible to programmer
Table used Page Table Segment Table

Virtual Memory - Detailed

Virtual memory allows execution of processes that may not be completely in memory. The portion of
the process not in memory is stored on disk (swap space or page file).
Demand Paging: Pages are loaded into memory only when they are needed (on demand), not in
advance.
• Page Fault: Occurs when a process tries to access a page that is not in memory. The OS must
load the page from disk.
• Page Fault Handling: Save process state -> find page on disk -> find free frame -> load page
into frame -> update page table -> restart the instruction.
Advantages of Virtual Memory:
• Programs can be larger than physical memory.
• More processes can be in memory simultaneously (higher multiprogramming).
• Less I/O needed to load or swap processes.
• Faster process creation using copy-on-write.
TOPIC 7: Page Replacement Algorithms
When a page fault occurs and there are no free frames, the OS must replace an existing page. The
choice of which page to replace is made by a page replacement algorithm.

1. FIFO (First In First Out)

The page that has been in memory the longest is replaced first. Simple to implement using a queue.
• Suffers from Belady's Anomaly: Adding more frames can sometimes increase page faults!
Example: Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 with 3 frames:
FIFO gives 15 page faults for this string.

2. Optimal (OPT) Page Replacement

Replace the page that will NOT be used for the longest time in the future. This gives the minimum
number of page faults — it is theoretically optimal.
• Problem: Cannot be implemented in practice because we cannot predict future page references.
• Used as a benchmark to compare other algorithms.
For reference string 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 with 3 frames, OPT gives 9 page faults.

3. LRU (Least Recently Used)

Replace the page that has not been used for the longest time (least recently used). This uses the
recent past as an approximation of the near future.
• LRU performs close to Optimal in practice.
• Does NOT suffer from Belady's Anomaly.
Implementation: Can use a counter (timestamp each page access, replace with oldest timestamp) or a
stack (page number moved to top on access; bottom page is LRU).
For reference string above with 3 frames, LRU gives approximately 12 page faults.

Algorithm Basis for Belady's Practical? Performance

Replacement Anomaly
FIFO Oldest page in Yes (suffers) Yes Poor
memory
Optimal Page used No No (theoretical) Best
farthest in future
LRU Page used least No Yes Good
recently

Belady's Anomaly
Belady's Anomaly is a phenomenon where increasing the number of page frames results in an
INCREASE in page faults for certain reference strings when using FIFO replacement. This seems
counterintuitive — more memory causes more faults. LRU and Optimal algorithms do not suffer from
this anomaly.
TOPIC 8: Disk Scheduling Algorithms
Disk scheduling determines the order in which disk I/O requests are serviced. Goal: Minimize seek time
and total head movement.
Terms:
• Seek Time: Time for disk arm to move to the correct track.
• Rotational Latency: Time for disk to rotate so correct sector is under the head.
• Transfer Time: Time to actually transfer data.
• Access Time = Seek Time + Rotational Latency + Transfer Time

Example Setup for All Algorithms

Head starts at position 53. Queue of pending requests: 98, 183, 37, 122, 14, 124, 65, 67.

1. FCFS (First Come First Served)

Requests are served in the order they arrive. Simple but generally not optimal.
Order: 53 -> 98 -> 183 -> 37 -> 122 -> 14 -> 124 -> 65 -> 67
Total head movement = |53-98|+|98-183|+|183-37|+|37-122|+|122-14|+|14-124|+|124-65|+|65-67|
= 45+85+146+85+108+110+59+2 = 640 cylinders
• Advantage: Simple, fair, no starvation.
• Disadvantage: Wild swings across the disk — high seek time, poor performance.

2. SSTF (Shortest Seek Time First)

Select the request that requires the least head movement from the current position.
Order: 53 -> 65 -> 67 -> 37 -> 14 -> 98 -> 122 -> 124 -> 183
Total head movement = 12+2+30+23+84+24+2+59 = 236 cylinders
• Advantage: Better throughput than FCFS, lower average seek time.
• Disadvantage: Starvation of requests far from current position. Not truly optimal.

3. SCAN (Elevator Algorithm)

The disk arm moves in one direction, servicing requests, until it reaches the end of the disk. Then it
reverses direction and services requests in the other direction.
Head moving towards 0: 53 -> 37 -> 14 -> 0 (end) -> reverse -> 65 -> 67 -> 98 -> 122 -> 124 -> 183
Total movement = (53-0) + (183-0) = 53 + 183 = 236 cylinders
• Advantage: Better than SSTF for uniform load. No starvation.
• Disadvantage: Requests at middle of disk are served more often — slight unfairness.
4. C-SCAN (Circular SCAN)
Like SCAN but only services requests in ONE direction. When the head reaches the end, it immediately
jumps back to the beginning without servicing on the way back.
Head moves: 53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> end -> 0 (jump) -> 14 -> 37
Total movement = (183-53) + 183 + 37 = 130 + 183 + 37 = 350 cylinders
• Advantage: More uniform wait time for all cylinders compared to SCAN.
• Disadvantage: More total head movement than SCAN.

5. LOOK and C-LOOK

LOOK is an improvement of SCAN: The arm goes only as far as the last request in each direction, not
to the physical end of the disk.
C-LOOK is to C-SCAN as LOOK is to SCAN: Arm goes to last request, jumps back to first request.
• LOOK is more efficient than SCAN as it avoids going to disk edges unnecessarily.

Algorithm Total Movement Starvation? Fairness

(example)
FCFS 640 cylinders No Perfect (request order)
SSTF 236 cylinders Yes Poor (far requests
starve)
SCAN 236 cylinders No Good
C-SCAN 350 cylinders No Best (uniform)
LOOK Similar to SCAN No Good
C-LOOK Less than C-SCAN No Good
TOPIC 9: File Allocation Methods
File allocation methods determine how disk space is allocated to files. Three main methods:

1. Contiguous Allocation
Each file occupies a set of contiguous (adjacent) blocks on disk.
• Directory entry contains: starting block address and length of file.
• Advantage: Very fast for sequential access (read file in one pass). Also supports direct/random
access.
• Disadvantage: External fragmentation. Difficult to grow files. File size must be known in
advance.

2. Linked Allocation
Each file is a linked list of disk blocks. Each block contains a pointer to the next block.
• Directory entry contains only the address of the first block.
• Advantage: No external fragmentation. Files can grow easily. No need to know file size in
advance.
• Disadvantage: Only sequential access (must follow pointers). One pointer overhead per block.
Reliability problem — if one pointer is corrupted, rest of file is lost.
• FAT (File Allocation Table): Variation where pointers are stored in a separate table in memory
— faster access.

3. Indexed Allocation
Each file has an index block that contains pointers to all data blocks of the file.
• Directory entry points to the index block.
• Advantage: Supports direct access efficiently. No external fragmentation.
• Disadvantage: Overhead of index block. Small files waste an entire index block. For very large
files, multiple index blocks needed (multi-level index).

Feature Contiguous Linked Indexed

Sequential Access Excellent Good Good
Random/Direct Access Excellent Poor (O(n)) Good
External Fragmentation Yes No No
Internal Fragmentation No No Yes (index block)
Growing files Difficult Easy Easy
Example OS IBM OS/360 FAT file system Unix (inode)
TOPIC 10: Types of Operating Systems

1. Batch Operating System

Jobs with similar requirements are batched together and executed one by one without user interaction.
Early computers used this approach.
• Operator collects similar jobs, inputs them as a batch.
• Advantage: Good CPU utilization for large jobs. No user interaction means no idle time.
• Disadvantage: High turnaround time. Debugging is difficult. No real-time interaction.
• Examples: Payroll processing, bank statement generation.

2. Multiprogramming OS
Multiple programs are loaded in memory simultaneously. When one process waits for I/O, CPU is given
to another process.
• Goal: Maximize CPU utilization.
• Advantage: Better CPU utilization, reduced idle time.
• Disadvantage: Requires memory management, process scheduling.

3. Time Sharing (Multitasking) OS

Multiple users interact with the computer simultaneously. CPU time is shared among users using time
slicing (quantum).
• Each user gets a time slice. When time expires, next user gets CPU.
• Goal: Minimize response time for interactive users.
• Advantage: Fast response, good user experience, multiple users simultaneously.
• Examples: Unix, Linux, Windows.

4. Real-Time OS (RTOS)
Used when time constraints are critical. The system must respond to inputs within a defined time
deadline.
• Hard RTOS: Missing deadline causes catastrophic failure. (e.g., aircraft control systems,
pacemakers)
• Soft RTOS: Missing deadline causes performance degradation but not system failure. (e.g.,
multimedia streaming, VoIP)
• Examples: VxWorks, QNX, FreeRTOS, RTLinux.

5. Distributed OS
Multiple independent computers connected by a network appear as a single coherent system to users.
Resources are shared across the network.
• Advantages: Resource sharing, reliability, scalability, speed (parallel computation).
• Challenges: Network failures, security, synchronization, data consistency.
 • Examples: Google's distributed systems, Apache Hadoop clusters.

6. Network OS
Provides features to connect computers and devices into a network and share resources (files,
printers). Users are aware they are connected to a network.
• Examples: Novell NetWare, Windows Server.

7. Multiprocessor OS
OS that manages multiple CPUs in a single computer. Multiple processors share memory and work in
parallel.
• Symmetric Multiprocessing (SMP): All CPUs are equal and run the same OS.
• Asymmetric Multiprocessing: One master CPU controls others (slaves).
• Advantage: Greater throughput, reliability (if one CPU fails, others continue).
TOPIC 11: Linux Operating System

Overview of Linux
Linux is a free, open-source, Unix-like OS. Created by Linus Torvalds in 1991. The Linux kernel is the
core, and distributions (like Ubuntu, RedHat, CentOS) add tools and packages on top.

Features of Linux
• Open Source: Source code is freely available.
• Multi-user: Multiple users can use the system simultaneously.
• Multitasking: Multiple programs run simultaneously.
• Portable: Can run on a wide variety of hardware.
• Secure: Strong permission model, user accounts, and file permissions.
• Stable: Rarely crashes, uptime of months/years without restart.
• Hierarchical File System: Everything is a file, organized in a tree structure.

Linux Architecture
• Hardware Layer: Physical hardware components.
• Kernel: Core of Linux — manages processes, memory, I/O, device drivers.
• Shell: Command-line interface to interact with kernel. (bash, zsh, sh)
• Application Layer: User programs and utilities.

Common Linux Commands

Command Function Example
ls List directory contents ls -la
cd Change directory cd /home/user
pwd Print current working directory pwd
mkdir Create directory mkdir mydir
rm Remove file/directory rm -rf mydir
cp Copy file/directory cp file1 file2
mv Move or rename file mv old new
cat Display file contents cat [Link]
grep Search for pattern in file grep 'hello' [Link]
chmod Change file permissions chmod 755 [Link]
ps Display running processes ps aux
kill Terminate a process kill -9 PID
Command Function Example
man Display manual for command man ls

Differences: Linux vs Windows vs UNIX

Feature Linux UNIX Windows
Source Code Open source (free) Proprietary Proprietary
Cost Free Expensive Paid
Security Very high Very high Moderate
File System ext4, XFS, Btrfs UFS, ZFS NTFS, FAT32
Kernel Monolithic (modular) Monolithic Hybrid (NT kernel)
CLI Bash, Zsh sh, ksh CMD, PowerShell
Stability Very stable Very stable Less stable
Use Case Servers, desktops, Enterprise servers Desktop, enterprise
embedded
TOPIC 12: I/O Systems and Device Management

I/O Hardware
I/O devices include storage devices (disks, USB), transmission devices (network cards, modems), and
human-interface devices (keyboard, mouse, display).
Each device controller has a buffer, registers, and status flags. The CPU communicates with device
controllers via:
• Polling (Busy Waiting): CPU continuously checks device status. Wastes CPU cycles.
• Interrupts: Device signals CPU when ready. CPU continues other work and responds to
interrupt.
• DMA (Direct Memory Access): DMA controller transfers data between device and memory
without involving CPU for each byte. CPU only sets up the transfer and is notified when done.

Kernel I/O Subsystem

The kernel provides several services for I/O:
• I/O Scheduling: Order I/O requests to improve efficiency (like disk scheduling).
• Buffering: Store data temporarily while transferring between two devices with different speeds.
• Caching: Keep a copy of frequently used data in faster storage for quick access.
• Spooling: Hold output for a device that cannot accept interleaved data streams (e.g., printer
spool — multiple print jobs stored and printed one at a time).
• Error Handling: Handle errors from devices gracefully.

I/O Traffic Controller

The I/O traffic controller manages the flow of information between processes and devices. It:
• Maintains status of each I/O device.
• Decides which process gets access to which device.
• Manages queues of I/O requests for each device.
• Provides an interface between the OS and device drivers.
TOPIC 13: Protection and Security

Protection
Protection refers to mechanisms that control access of processes or users to resources defined by the
computer system.
Goals of Protection:
• Prevent deliberate violations of access restrictions.
• Ensure each program uses system resources only as intended.
• Detect latent errors at interfaces between components.
Methods: Access Control Lists (ACL), Access Matrix, Capability Lists, Roles.

Security
Security involves defending the computer system from external and internal attacks. While protection
deals with internal users, security deals with threats from outside.
Types of Security Threats:
• Viruses: Self-replicating programs that attach to legitimate programs.
• Worms: Self-replicating programs that spread through networks without user action.
• Trojan Horses: Programs that appear legitimate but perform malicious actions.
• Denial of Service (DoS): Flooding a system to make it unavailable.
• Man-in-the-Middle: Intercepting communication between two parties.
Difference from Protection:
Aspect Protection Security
Scope Internal (processes, users) External (attackers, viruses)
Goal Control resource access Defend against threats
Mechanism Access control, capabilities Encryption, firewalls,
authentication
Concern Who can access what Preventing unauthorized
access/damage
TOPIC 14: Distributed and Multiprocessor Operating Systems

Distributed OS
A distributed OS manages a collection of independent computers, making them appear to users as a
single coherent system.
Key Features:
• Transparency: Users need not know where resources are located.
• Resource Sharing: Resources (files, printers, processors) shared across network.
• Fault Tolerance: System continues working even if some nodes fail.
• Scalability: Easy to add more nodes.
Main Design Issues:
• Network Communication: Handling delays, failures, and bandwidth.
• Process Management: Scheduling across multiple machines.
• Naming and Location: Finding resources across the network.
• Synchronization: Ensuring consistency when multiple nodes access shared data.
• Deadlock: Distributed deadlock detection is harder than single-system deadlock.
• Security: Protecting data transmitted across the network.

Multiprocessor OS
Manages multiple CPUs (processors) sharing the same memory in a single system.
Types:
• Symmetric Multiprocessing (SMP): All processors are equal, share the same memory and OS.
Any processor can run any process. Examples: Modern PCs, servers.
• Asymmetric Multiprocessing: One master processor controls the system, slaves execute tasks
assigned by master.
Advantages:
• Increased throughput — tasks executed in parallel.
• Reliability — if one processor fails, others continue.
• Economy — shared memory and peripherals.

TOPIC 15: File System Architecture and Structure

Layered File System Architecture

File systems are organized in layers, each providing services to the layer above:
• Application Programs: Users and applications that use files.
• Logical File System: Manages metadata — file names, directory structures, permissions, file
control blocks.
• File Organization Module: Maps logical blocks to physical blocks; manages free space.
 • Basic File System: Issues commands to device drivers (read block N, write block N).
• I/O Control: Device drivers and interrupt handlers — actual hardware communication.
• Devices: Physical storage devices (hard disk, SSD).

Logical File System

The logical file system manages all file metadata. It maintains a File Control Block (FCB) or inode for
each file.
FCB/inode contains: file permissions, dates (created, modified), owner, size, data block pointers.

Directory Structure
• Single-Level Directory: All files in one directory. Simple but no organization.
• Two-Level Directory: Separate directory for each user.
• Tree-Structured Directory: Hierarchical tree of directories (used in Unix/Linux/Windows).
• Acyclic-Graph Directory: Allows sharing of files and directories via links (hard links, symbolic
links).
QUICK REVISION: MOST REPEATED EXAM QUESTIONS

Question Key Answer Points Marks

Define deadlock & 4 conditions Permanent blocking; Mutual 2-5
Excl, Hold & Wait, No Preempt,
Circular Wait
What is PCB? Data structure with PID, state, 2-5
PC, registers, memory info, I/O
info
FIFO vs LRU vs Optimal FIFO-oldest, LRU-least recent, 5-10
Optimal-farthest future; Belady's
anomaly in FIFO
Disk Scheduling FCFS (arrival order), SSTF 5-10
(nearest), SCAN (elevator), C-
SCAN (one direction)
OS Structures Monolithic (one block), Layered 5
(levels), Microkernel (minimal
kernel)
Banker's Algorithm Check safe state before 5
allocating; Need=Max-Allocated;
find safe sequence
Virtual Memory Illusion of large memory; 2-5
demand paging; page fault
handling
Producer-Consumer Bounded buffer; semaphores: 5
mutex, empty, full; wait/signal
operations
Paging vs Segmentation Fixed vs variable; internal vs 2-5
external fragmentation; page
table vs segment table
CPU Scheduling FCFS, SJF, Priority, RR, 5-10
Multilevel Queue; calculate
waiting/turnaround time

Best of Luck for Your Exams!

Operating System | [Link] Sem 4 | Complete Notes