Operating Systems

15-Mark Question Bank — Complete Answers

Q1. Functions of OS / Open System Interface between User and Hardware

1. Definition of Operating System

An Operating System (OS) is system software that acts as an intermediary between computer
hardware and application programs. It manages hardware resources and provides services to user
programs.

2. Functions of an Operating System

• Process Management: Creates, schedules, and terminates processes. Handles CPU
scheduling (FCFS, SJF, Round Robin, Priority). Manages PCB (Process Control Block) for each
process.
• Memory Management: Allocates and deallocates memory to processes. Implements
techniques like paging, segmentation, and virtual memory. Prevents unauthorized memory
access.
• File System Management: Organizes data into files and directories. Controls access
permissions (read/write/execute). Manages free space and disk allocation.
• I/O Device Management: Uses device drivers to communicate with hardware. Manages I/O
scheduling via spooling and buffering. Handles interrupts from devices.
• Security & Protection: Enforces user authentication and authorization. Prevents unauthorized
process access to resources. Manages access control lists (ACL).
• Networking: Manages network connections and protocols (TCP/IP). Supports inter-process
communication over networks.
• Error Detection & Handling: Detects hardware faults, arithmetic errors, and I/O failures. Takes
corrective action or alerts the user.

3. OS as Interface (Layered View)

Layer Description

User / Application User programs, shells, GUIs

System Call Interface API between user programs and OS kernel

OS Kernel Core — process, memory, file, I/O managers

Hardware Abstraction Layer Drivers abstracting physical devices

Hardware CPU, RAM, Disk, I/O devices

4. Types of System Calls (Interface Mechanism)

• Process Control: fork(), exec(), exit(), wait()
• File Management: open(), read(), write(), close(), create()
• Device Management: ioctl(), read(), write()
• Information Maintenance: getpid(), alarm(), sleep()
• Communication: pipe(), shmget(), mmap(), socket()
Q2. Different Operating Systems

1. Batch Operating System

Jobs with similar requirements are grouped into batches and processed together. No direct user
interaction during execution. Example: IBM OS/360.

• Advantage: High throughput for repetitive tasks.

• Disadvantage: High turnaround time; no interactivity.

2. Time-Sharing (Multitasking) OS
CPU time is shared among multiple users simultaneously using time slices (quantum). Each user
gets the illusion of a dedicated system. Example: UNIX, Linux, Windows.

• Advantage: Fast response, multiple users.

• Disadvantage: Security issues; complex design.

3. Distributed Operating System

Manages a group of networked computers, making them appear as a single coherent system.
Resources are distributed across nodes. Example: Google's distributed systems, Amoeba OS.

4. Real-Time Operating System (RTOS)

Processes data within strict time constraints (deadlines). Used in embedded and critical systems.

• Hard RTOS: Missing deadline = system failure. E.g., pacemakers, aircraft controls.
• Soft RTOS: Occasional deadline miss tolerated. E.g., video streaming, VoIP.

5. Network Operating System

Provides features to connect computers and share resources over a network. Example: Windows
Server, Novell NetWare.

6. Mobile OS
Designed for mobile devices. Manages touch input, GPS, sensors, battery. Examples: Android (Linux
kernel), iOS (XNU kernel).

7. Embedded OS
Specialized OS for embedded systems with limited resources. Example: FreeRTOS, VxWorks,
Contiki.

Comparison Table
Type User Interaction Examples Use Case

Batch None IBM OS/360 Payroll, billing

Time-Sharing Yes (multi-user) UNIX, Linux General computing

Distributed Transparent Amoeba Cloud computing

RTOS Minimal FreeRTOS Embedded, control

Mobile Touch/Voice Android, iOS Smartphones

Q3. Critical Section Problem

1. Definition
A critical section is a code segment where shared resources (variables, files, memory) are
accessed. When one process executes its critical section, no other process should execute its critical
section — this is the mutual exclusion requirement.

2. Structure of a Process
do {
// Entry Section — request permission
critical_section();
// Exit Section — release permission
remainder_section();
} while (true);

3. Requirements for a Valid Solution

• Mutual Exclusion: Only one process in critical section at a time.
• Progress: If no process is in CS and some want to enter, selection cannot be postponed
indefinitely.
• Bounded Waiting: A limit must exist on how many times other processes enter CS after a
process has made a request.

4. Peterson's Solution (Software — 2 processes)

int turn; // whose turn it is
bool flag[2]; // flag[i]=true: Pi wants to enter CS

// Process Pi:
flag[i] = true;
turn = j;
while (flag[j] && turn == j); // busy wait
/* CRITICAL SECTION */
flag[i] = false;

Peterson's solution satisfies all three requirements but works only for 2 processes and requires busy
waiting.

5. Hardware Solutions
• Test-and-Set: Atomically reads and sets a boolean lock variable. Ensures mutual exclusion but
may cause starvation.
• Compare-and-Swap (CAS): Atomically compares and exchanges values. Used in modern
lock-free algorithms.
• Disabling Interrupts: Simple on single-processor; dangerous on multi-processor systems.

6. Race Condition Example

Two processes executing counter++ concurrently: both read counter=5, both compute 6, both write 6
— net result is 6 instead of 7. This is a race condition, solved by protecting the critical section.
Q4. Apply Semaphore in Synchronization

1. What is a Semaphore?
A semaphore is an integer variable accessed only through two atomic operations: wait() (also called
P or down) and signal() (also called V or up), introduced by Dijkstra.

2. Operations
wait(S): signal(S):
while S <= 0; S++;
S--;

3. Types of Semaphores
• Binary Semaphore (Mutex): Value is 0 or 1. Used like a lock for mutual exclusion.
• Counting Semaphore: Value ranges over unrestricted domain. Used to control access to a
resource with multiple instances (e.g., 3 printers → initialized to 3).

4. Mutual Exclusion using Semaphore

Semaphore mutex = 1;

Process Pi:
wait(mutex); // acquire lock
critical_section();
signal(mutex); // release lock
remainder_section();

5. Synchronization (Ordering) using Semaphore

Ensure S2 in P2 executes only after S1 in P1:
Semaphore sync = 0;

P1: P2:
S1; wait(sync);
signal(sync); S2;

6. Counting Semaphore — Bounded Buffer

Semaphore empty = N; // free slots
Semaphore full = 0; // filled slots
Semaphore mutex = 1;

Producer: Consumer:
wait(empty); wait(full);
wait(mutex); wait(mutex);
add_to_buffer(); remove_from_buffer();
signal(mutex); signal(mutex);
signal(full); signal(empty);

7. Limitations
• Busy Waiting: Wastes CPU in the while loop (spin-lock). Solved by blocking semaphores.
• Deadlock: Incorrect order of wait() calls can cause deadlock.
• Priority Inversion: High-priority process waits for low-priority one.
Q5. Frame Allocation Strategies

1. Introduction
In virtual memory systems, physical memory is divided into frames and logical memory into pages.
Frame allocation determines how many frames are given to each process.

2. Minimum Frame Allocation

A process must have a minimum number of frames to avoid thrashing. The minimum is determined
by the instruction set architecture (e.g., indirect addressing may need 6 frames minimum).

3. Equal Allocation
If there are m frames and n processes, each process gets m/n frames (integer division). Remaining
frames can be kept as free frame buffer.

Example: 100 frames, 5 processes → each gets 20 frames. Simple but ignores process size.

4. Proportional Allocation
Frames are distributed based on the size of each process relative to total virtual memory.

si = size of process Pi
S = sum of all process sizes
m = total frames
Frames for Pi = (si / S) * m

Example: P1=10 pages, P2=90 pages, m=100 frames

f1 = (10/100)*100 = 10 frames
f2 = (90/100)*100 = 90 frames

5. Priority-Based Allocation
High-priority processes get more frames. If process Pi has higher priority than Pj, it gets more frames
even if they have equal sizes. Can combine with proportional allocation.

6. Global vs. Local Allocation

Aspect Global Replacement Local Replacement

Frame pool All frames (any process) Only own frames

Flexibility High Low

Isolation None — one process affects others Full isolation

Throughput Generally higher More predictable

Used in Most systems (Linux) Embedded, RTOS

7. Thrashing
If a process doesn't have enough frames, it constantly page-faults → OS spends more time paging
than executing → system throughput collapses. This is thrashing. Working Set Model and Page
Fault Frequency strategies help avoid it.
Q6. Paging vs. Segmentation

1. Paging
Paging divides both logical memory into fixed-size pages and physical memory into fixed-size
frames. The CPU generates a logical address split into a page number (p) and page offset (d). The
page table maps p → frame number f, giving physical address = f * frame_size + d.

• No external fragmentation (fixed sizes fit perfectly).

• Internal fragmentation possible (last page may not be full).
• Page size typically 4 KB. Supported by hardware TLB for fast translation.

2. Segmentation
Segmentation divides a program into variable-sized logical units called segments (code, data, stack,
heap). A logical address is a pair (segment number s, offset d). The segment table stores base
address and limit for each segment.

• No internal fragmentation (segments sized to exact need).

• External fragmentation occurs over time.
• Matches programmer's view of memory (functions, arrays, objects).

3. Address Translation
PAGING:
Logical: [page# | offset] → Page Table → [frame# | offset] = Physical

SEGMENTATION:
Logical: [seg# | offset] → Seg Table (base, limit)
if offset < limit: Physical = base + offset else: TRAP

4. Comparison Table
Feature Paging Segmentation

Division unit Fixed-size pages Variable-size segments

Logical view Physical, uniform Logical (code, data, stack)

Fragmentation Internal only External only

Address format (page#, offset) (seg#, offset)

Hardware Page table + TLB Segment table

Protection Per-page bits Per-segment (r/w/x)

Sharing At page granularity At segment granularity

Example OS Linux, Windows Intel x86 (segmented)

5. Segmentation with Paging (Combined)

Modern systems (Intel x86-64) combine both: segments provide logical protection and paging
provides physical memory management. A logical address is first segmented, then paged to get the
physical address.
Q7. Life Cycle of a Process with State Diagram

1. Process States
• New: Process is being created (PCB initialized, resources assigned).
• Ready: Process is loaded in main memory, waiting for CPU. Sits in the ready queue.
• Running: CPU is currently executing this process's instructions.
• Waiting (Blocked): Process is waiting for an I/O event or resource. Moves to ready when event
completes.
• Terminated (Exit): Process has finished execution. Resources are released; PCB is deleted.
• Suspended Ready / Suspended Wait: (Extended 7-state model) Process swapped out to disk
to free memory.

2. State Diagram (Text Representation)

admitted
[NEW] ■■■■■■■■■■■■■■■■■■→ [READY]
↑ ↑
I/O done / | | scheduler dispatch
event done | ↓
[RUNNING] ■■→ exit ■■→ [TERMINATED]
|
I/O wait / event wait
↓
[WAITING]

3. Transitions
Transition Cause

New → Ready Process loaded into memory (admitted)

Ready → Running CPU scheduler selects process (dispatch)

Running → Ready Timer interrupt / preemption

Running → Waiting I/O request, sleep(), wait() call

Waiting → Ready I/O completion, event occurs

Running → Terminated Process calls exit() or is killed

4. Process Control Block (PCB)

The OS represents each process by a PCB containing: Process ID, Process State, Program Counter,
CPU Registers, Memory Management Info, I/O Status, Accounting Info.
Q8. Dining Philosophers Problem

1. Problem Statement
Five philosophers sit around a circular table. Between each pair is one chopstick (5 total). Each
philosopher alternates between thinking and eating. To eat, a philosopher needs both left and right
chopsticks. This is a classic synchronization problem involving mutual exclusion and deadlock
avoidance.

2. Naive Solution (leads to Deadlock)

Semaphore chopstick[5] = {1,1,1,1,1};

Philosopher i:
think();
wait(chopstick[i]); // pick left
wait(chopstick[(i+1)%5]); // pick right → DEADLOCK if all pick left!
eat();
signal(chopstick[i]);
signal(chopstick[(i+1)%5]);

If all 5 philosophers pick their left chopstick simultaneously, all wait for the right → circular wait →
deadlock.

3. Solutions
• Allow at most 4 philosophers to sit at the table simultaneously (use a semaphore initialized to
4).
• Asymmetric solution: Odd-numbered philosophers pick left then right; even-numbered pick
right then left. Breaks circular wait.
• Monitor-based solution: A philosopher picks up chopsticks only if both are available (checked
atomically inside a monitor).

4. Monitor Solution (Pseudo-code)

enum State { THINKING, HUNGRY, EATING };
State state[5];
Condition self[5];

pickup(i):
state[i] = HUNGRY;
test(i); // try to eat
if state[i] != EATING: self[i].wait();

putdown(i):
state[i] = THINKING;
test((i+4)%5); test((i+1)%5); // notify neighbors

test(i):
if state[(i+4)%5]!=EATING && state[i]==HUNGRY
&& state[(i+1)%5]!=EATING:
state[i]=EATING; self[i].signal();

This avoids deadlock and starvation. A philosopher eats only when both neighbors are not eating.
Q9. Contiguous Memory Allocation (with Numerical Problems)

1. Concept
Each process occupies a single contiguous section of memory. The OS maintains a table tracking
allocated and free (hole) partitions. When a process arrives, a suitable hole is selected.

2. Allocation Strategies
• First Fit: Allocate the first hole that is big enough. Fast; may leave large holes fragmented at the
beginning.
• Best Fit: Allocate the smallest hole that is big enough. Minimizes wasted space but slow
(searches entire list); creates many tiny unusable holes.
• Worst Fit: Allocate the largest hole. Idea: leaves largest remaining hole. In practice performs
worst.

3. Numerical Example
Memory holes (free blocks) in order: 100 KB, 500 KB, 200 KB, 300 KB, 600 KB

Processes requesting: P1=212 KB, P2=417 KB, P3=112 KB, P4=426 KB

Holes: 100, 500, 200, 300, 600 KB

FIRST FIT:
P1=212 → Hole 500 (500-212=288 remaining)
P2=417 → Hole 288? No. Hole 600 (600-417=183)
P3=112 → Hole 100? No(too small). Hole 288 (288-112=176)
P4=426 → No hole fits → FAIL

BEST FIT:
P1=212 → Best: 300 (300-212=88 remaining)
P2=417 → Best: 500 (500-417=83 remaining)
P3=112 → Best: 200 (200-112=88 remaining)
P4=426 → Best: 600 (600-426=174 remaining)

WORST FIT:
P1=212 → Largest: 600 (600-212=388)
P2=417 → Largest: 500? No(417<500, but now 388<417). Fail for P2

4. Fragmentation
• External Fragmentation: Total free memory is enough but not contiguous. Solved by
compaction (relocating processes).
• Internal Fragmentation: Allocated memory slightly larger than requested; wasted inside
partition. Common with fixed-size partitions.
• 50% Rule: On average with first fit, 1/3 of memory is lost to fragmentation — for every 2
allocated partitions, 1 hole.
Q10. Demand Paging

1. Concept
In demand paging, pages of a process are loaded into memory only when needed (on demand),
not all at once. This supports virtual memory — a process can be larger than physical memory. A
lazy swapper (pager) loads pages only when referenced.

2. Valid-Invalid Bit
Each page table entry has a valid-invalid bit. Valid (v): page is in memory. Invalid (i): page is not in
memory (either not used or on disk).

3. Page Fault Handling Sequence

• 1. Process references a page → CPU checks page table.
• 2. If bit = invalid → page fault trap to OS.
• 3. OS checks internal table: is reference valid? If not → terminate process.
• 4. Find a free frame (or use page replacement if none available).
• 5. Schedule disk I/O to read page into frame.
• 6. Update page table: set frame number, bit = valid.
• 7. Restart the faulting instruction.

4. Effective Access Time (EAT)

EAT = (1 - p) * memory_access + p * page_fault_time

Example:
Memory access = 200 ns
Page fault service = 8,000,000 ns (8 ms)
p = page fault rate

EAT = (1-p)*200 + p*8,000,000

For EAT < 220 ns: p < 0.0000025 (less than 1 fault per 400,000 accesses)

5. Page Replacement Algorithms

• FIFO: Replace oldest page. Simple but may exhibit Belady's anomaly (more frames → more
faults).
• Optimal (OPT): Replace page not used for the longest time in future. Theoretical best; not
implementable.
• LRU (Least Recently Used): Replace page not used for the longest time in past. Good
performance; requires hardware support (stack or counters).
• LRU Approximation (Clock/Second-Chance): Uses reference bit; practical hardware
implementation.

6. Numerical — FIFO (3 frames, reference string: 7,0,1,2,0,3,0,4,2,3,0,3,2)

Frames: 3 Reference String: 7 0 1 2 0 3 0 4 2 3 0 3 2
Page 7 0 1 2 0 3 0 4 2 3 0 3 2
F1 7 7 7 2 2 2 2 4 4 4 0 0 0
F2 - 0 0 0 0 3 3 3 2 2 2 2 2
F3 - - 1 1 1 1 0 0 0 3 3 3 3
Fault F F F F - F F F F F F - -
Total Page Faults = 9
Q11. Apply System Calls in Process Control & File Management

1. What are System Calls?

System calls are the programmatic interface between user programs and the OS kernel. They switch
execution from user mode to kernel mode via a software interrupt/trap.

2. Process Control System Calls

System Call Description Example

fork() Create a child process (duplicate parent) pid = fork()

exec() Replace process image with a new program execvp("ls", args)

exit() Terminate current process exit(0)

wait() Parent waits for child to finish wait(&status)

getpid() Get current process ID pid_t id = getpid()

kill() Send signal to a process kill(pid, SIGTERM)

nice() Change process priority nice(-5)

3. fork() + exec() Example

pid_t pid = fork();
if (pid == 0) {
// Child process
execlp("/bin/ls", "ls", NULL);
} else if (pid > 0) {
// Parent process
wait(NULL); // wait for child
printf("Child finished\n");
} else {
perror("fork failed");
}

4. File Management System Calls

System Call Description

open(path, flags) Open/create a file; returns file descriptor (fd)

read(fd, buf, n) Read n bytes from fd into buffer

write(fd, buf, n) Write n bytes from buffer to fd

close(fd) Close file descriptor

lseek(fd, offset, whence) Move file pointer to offset

unlink(path) Delete a file

stat(path, &buf) Get file metadata (size, permissions, timestamps)

mkdir(path, mode) Create a directory

opendir() / readdir() Open and read directory entries

5. File Operation Example

int fd = open("[Link]", O_RDWR | O_CREAT, 0644);
if (fd < 0) { perror("open"); exit(1); }

char buf[] = "Hello, OS!";

write(fd, buf, strlen(buf));

lseek(fd, 0, SEEK_SET); // go back to beginning

char rbuf[20];
int n = read(fd, rbuf, sizeof(rbuf)-1);
rbuf[n] = '\0';
printf("%s\n", rbuf);

close(fd);
Q12. Producer-Consumer & Reader-Writer Problem

PART A: Producer-Consumer Problem

Also called the Bounded-Buffer Problem. A producer generates data and places it in a shared
buffer. A consumer removes data from the buffer. The buffer has a fixed size N. The problem
requires: (1) producer must not produce when buffer is full, (2) consumer must not consume when
buffer is empty, (3) only one process accesses buffer at a time.

Solution using Semaphores

int n = BUFFER_SIZE;
Semaphore mutex = 1; // mutual exclusion
Semaphore empty = n; // free slots (initially all free)
Semaphore full = 0; // filled slots (initially 0)

PRODUCER: CONSUMER:
do { do {
produce item; wait(full);
wait(empty); wait(mutex);
wait(mutex); item = remove_from_buffer();
add_to_buffer(item); signal(mutex);
signal(mutex); signal(empty);
signal(full); consume(item);
} while(true); } while(true);

• empty counts free slots; full counts filled slots.

• Deadlock avoided by always acquiring mutex AFTER empty/full.

PART B: Reader-Writer Problem

Multiple readers can read a shared database simultaneously. A writer must have exclusive access
(no readers/writers allowed). Two variants: First Readers-Writers (readers have priority — writers
may starve) and Second Readers-Writers (writers have priority — readers may starve).

Solution (First R-W — readers priority)

Semaphore rw_mutex = 1; // exclusive access for writer
Semaphore mutex = 1; // protect read_count
int read_count = 0; // # active readers

WRITER: READER:
wait(rw_mutex); wait(mutex);
write_database(); read_count++;
signal(rw_mutex); if(read_count==1)
wait(rw_mutex); // first reader locks writer
signal(mutex);
read_database();
wait(mutex);
read_count--;
if(read_count==0)
signal(rw_mutex); // last reader unlocks
signal(mutex);
• First reader blocks writers; last reader unblocks writers.
• Multiple readers can be in critical section simultaneously.
• Writer starvation is possible — fixed by Second Readers-Writers or using queues.
Q13. Process Creation & Termination using System Calls

1. Process Creation — fork()

The fork() system call creates a new process. The child is an exact copy of the parent (copies
address space, file descriptors, registers). The return value distinguishes parent and child.

#include
#include
#include
#include

int main() {
pid_t pid = fork();

if (pid < 0) {
perror("fork failed");
return 1;
} else if (pid == 0) {
// ■■ CHILD PROCESS ■■
printf("Child PID: %d, Parent PID: %d\n",
getpid(), getppid());
// Replace child with a new program:
execlp("/bin/ls", "ls", "-l", NULL);
// Only reached if exec fails:
perror("exec failed");
exit(1);
} else {
// ■■ PARENT PROCESS ■■
printf("Parent PID: %d, Child PID: %d\n",
getpid(), pid);
int status;
waitpid(pid, &status;, 0); // wait for child
if (WIFEXITED(status))
printf("Child exited with code %d\n",
WEXITSTATUS(status));
}
return 0;
}

2. fork() Return Value

Return Value Process Meaning

<0 Parent fork() failed (no resources)

== 0 Child This is the child process

>0 Parent PID of the newly created child

3. Process Termination — exit()

A process terminates by calling exit(status) or returning from main(). The OS releases all resources:
memory, file descriptors, I/O devices. The process enters Zombie state temporarily until the parent
calls wait().

// Normal termination
exit(0); // success
exit(1); // failure

// Abnormal termination (by parent or signal)

kill(child_pid, SIGKILL); // force kill
kill(child_pid, SIGTERM); // request terminate

4. Zombie and Orphan Processes

• Zombie Process: Child has exited but parent has not yet called wait(). The PCB remains to
hold exit status. Cleared when parent calls wait().
• Orphan Process: Parent exits before child. The child is re-parented to init (PID 1) / systemd,
which calls wait() periodically.

5. exec() Family
exec() replaces the process image with a new program. The PID remains the same. Variants:

execl("/bin/ls", "ls", "-l", NULL); // path + args list

execv("/bin/ls", argv); // path + args array
execlp("ls", "ls", "-l", NULL); // search PATH
execvp("ls", argv); // search PATH + array
execve("/bin/ls", argv, envp); // explicit env vars

— End of Question Bank —