Operating Systems
Lab Exam VIVA

Answer

The /proc file system is a virtual (pseudo) file system in Linux that provides a window into the kernel's internal data structures. It does not store real files on disk — it exists only in memory.

Key uses:

• /proc/cpuinfo – CPU details (cores, model, speed)
• /proc/meminfo – Memory usage (total, free, available)
• /proc/[PID]/status – Info about a specific process
• /proc/stat – System-wide statistics (context switches, processes)
• Track number of processes, context switches, running/blocked states

Answer

The ps (Process Status) command shows a snapshot of currently running processes. It displays:

• PID – Process ID
• TTY – Terminal associated with the process
• TIME – CPU time consumed
• CMD – Command name/path
• With ps aux: user, CPU%, MEM%, start time, status

Answer

The Process API in Linux consists of system calls to create and manage processes:

• fork() – Creates a child process (clone of parent)
• exec() / execvp() – Replaces process image with a new program
• wait() / waitpid() – Parent waits for child to finish
• exit() – Terminates a process
• getpid() – Returns PID of current process
• getppid() – Returns parent's PID

Answer

fork() creates a new (child) process that is an exact copy of the calling (parent) process. Both processes continue execution from the next line after fork().

Return values:

• Returns 0 in the child process
• Returns child's PID in the parent process
• Returns -1 on error

Answer

wait() suspends the parent process until one of its child processes terminates. It:

• Prevents zombie processes (processes that have finished but not been cleaned up)
• Allows the parent to retrieve the child's exit status
• Ensures proper synchronization between parent and child

Answer

IPC (Inter-Process Communication) is needed because:

• Processes have separate address spaces and cannot directly access each other's memory
• Enables data sharing between cooperating processes
• Allows synchronization and coordination
• Supports modular program design (separate processes for separate tasks)
• Examples: web server ↔ database, producer ↔ consumer

Answer

A pipe is a unidirectional communication channel between related processes (parent-child). Data flows in one direction only.

• Created using pipe(fd[2]) — fd[0]=read end, fd[1]=write end
• Anonymous pipe: only between related processes
• Named pipe (FIFO): can be used by unrelated processes
• Operates like a FIFO queue in kernel memory
• Blocking: read blocks if empty, write blocks if full

Answer

Shared Memory is the fastest IPC mechanism. A region of memory is mapped into the address space of multiple processes, allowing them to read/write directly.

Key functions (POSIX):

• shmget() – Create/get a shared memory segment
• shmat() – Attach segment to process address space
• shmdt() – Detach segment
• shmctl() – Control/remove the segment

Requires external synchronization (semaphores) to prevent race conditions.

Answer

A Message Queue is a linked list of messages stored in the kernel, allowing processes to send and receive typed messages asynchronously.

• msgget() – Create/access queue
• msgsnd() – Send a message
• msgrcv() – Receive a message (can filter by type)
• msgctl() – Control/remove queue

Unlike pipes, messages have type/priority, and receiver can pick specific types.

Answer

Virtual Memory is a memory management technique that gives each process the illusion of having a large, contiguous address space, even if physical RAM is limited.

• Allows programs larger than physical RAM to run
• Uses disk (swap space) as extension of RAM
• Provides isolation between processes
• Enables efficient memory sharing
• Implemented via paging or segmentation with page tables and MMU

Answer

Programs use logical (virtual) addresses which must be converted to physical addresses because:

• Each process thinks it has its own address space starting at 0
• Multiple processes can't all physically start at address 0
• OS needs to protect processes from accessing each other's memory
• Physical placement of a process may change (due to swapping)
• Allows relocation, sharing, and protection

Done by the MMU (Memory Management Unit) in hardware.

• Base and Limit Registers – Simple; physical addr = logical + base
• Paging – Divides memory into fixed-size pages; uses page table
• Segmentation – Divides into variable-size segments; uses segment table
• Hybrid (Paged Segmentation) – Each segment is paged; used in x86
• Inverted Page Table – One entry per physical frame (saves memory)
• TLB (Translation Lookaside Buffer) – Cache for fast page table lookups

Answer

The VFS (Virtual File System) provides a common interface layer between user applications and different underlying file systems (ext4, NTFS, FAT32, etc.).

• Allows applications to use the same system calls (open, read, write) regardless of the actual file system
• Supports multiple file systems mounted simultaneously
• Abstraction layer → portability and flexibility
• Enables accessing network file systems (NFS) transparently

CPU Cores

Memory Details

In C code, open /proc/cpuinfo and count "processor" entries, or parse /proc/meminfo for MemTotal/MemFree lines.

Answer

A process tree represents the parent-child relationship between processes. All processes are descendants of init (PID 1) or systemd.

pstree command displays this hierarchy as a tree. Useful flags:

• pstree -p – Show PIDs
• pstree -u – Show usernames
• pstree -h – Highlight current process and its ancestors

1. Parent calls fork() system call
2. OS allocates a new PCB (Process Control Block) for child
3. Child gets a unique PID; PPID set to parent's PID
4. Parent's address space is copied to child (copy-on-write)
5. File descriptors are duplicated
6. Scheduling queues updated; both processes become runnable
7. fork() returns 0 to child, child-PID to parent
8. Both continue execution independently from the next instruction

Pipes use a kernel buffer. When write end is closed, read returns EOF. Data flows: Writer → kernel buffer → Reader. Pipes are FIFO and unidirectional.

Answer

A context switch is the process of saving the state (context) of a currently running process and loading the saved state of another process so it can run.

Steps:

1. Save CPU registers, PC, stack pointer of current process to its PCB
2. Update process state to ready/waiting
3. Select next process via scheduler
4. Load PCB of new process (registers, PC, stack)
5. Resume execution of new process

Occurs due to: time quantum expiry, I/O wait, higher-priority process arrival, system calls, interrupts.

Context switching is pure overhead — no useful work is done during a switch.

Round Robin – Each process gets a fixed time quantum (TQ=2ms)

Gantt Chart:

Problem

Multiple readers can read simultaneously, but a writer must have exclusive access. Problems: starvation of writers (reader priority) or readers (writer priority).

Reader Priority Solution (Semaphore-based)

Banker's Algorithm – Deadlock Avoidance

Data structures: Available[], Max[][], Allocation[][], Need[][] = Max – Allocation

Safety Algorithm:

1. Work = Available; Finish[i] = false for all i
2. Find process i where Finish[i]==false AND Need[i] ≤ Work
3. Work = Work + Allocation[i]; Finish[i] = true
4. Repeat step 2; if all Finish[i]==true → SAFE STATE

Resource Request Algorithm:

When process Pi requests resources: if Request ≤ Need AND Request ≤ Available → tentatively allocate → run safety check → if safe, grant; else rollback.

Detection Algorithm Steps:

1. Work = Available; Finish[i] = (Allocation[i]==0)
2. Find i where Finish[i]==false AND Request[i] ≤ Work
3. Work += Allocation[i]; Finish[i] = true
4. If any Finish[i]==false → those processes are DEADLOCKED

top is a dynamic real-time process viewer. It shows:

• Running processes sorted by CPU/memory usage
• System uptime, load average
• Total tasks: running, sleeping, stopped, zombie
• CPU usage breakdown (user%, kernel%, idle%)
• Memory and swap usage
• Useful keys: k=kill, r=renice, q=quit, P=sort by CPU

gdb (GNU Debugger) is a powerful debugging tool for C/C++ programs. It allows you to:

• Run a program step-by-step (step, next)
• Set breakpoints (break main)
• Inspect variables (print var)
• View stack trace (backtrace)
• Analyze core dumps from crashed programs
• Examine memory contents

file determines the type of a file by examining its content (magic bytes), not the extension. Examples:

time measures how long a command takes to execute. It reports:

• real – Wall clock time (actual elapsed time)
• user – Time spent in user-mode code
• sys – Time spent in kernel-mode (system calls)

fuser identifies which processes are using a file or socket. Useful for:

• Finding which process is using a port: fuser 80/tcp
• Finding which process is using a file: fuser /path/to/file
• Killing processes using a resource: fuser -k 80/tcp

A semaphore is an integer variable used for synchronization between processes/threads, accessed only through two atomic operations:

• wait(S) / P(S): while(S≤0); S--; — blocks if S=0
• signal(S) / V(S): S++; — wakes a blocked process

Used to control access to shared resources and prevent race conditions.

Thrashing occurs when a process spends more time paging (swapping pages in/out) than executing. Cause: too many processes, insufficient frames allocated.

Symptoms: CPU utilization drops sharply; paging device is constantly busy.

Solutions:

• Working Set Model – allocate frames based on locality
• Page Fault Frequency – add/remove frames based on fault rate
• Reduce degree of multiprogramming

A page fault occurs when a process accesses a page that is not currently in physical memory (RAM). The OS must:

1. Trap to OS (page fault interrupt)
2. Find the page on disk (swap space)
3. Find a free frame (evict if needed using replacement algorithm)
4. Load the page into the frame
5. Update page table
6. Resume the process

Setup

5 philosophers sit around a circular table. Between each pair is 1 chopstick (5 total). To eat, a philosopher needs both adjacent chopsticks. After eating, they think, then try to eat again.

Problem

If all philosophers simultaneously pick up their left chopstick → deadlock (everyone waits for right chopstick forever).

Solutions

• Allow only 4 philosophers to sit at once
• Reversed order for last philosopher (pick right first) — breaks circular wait
• Use a waiter (monitor) — only give both chopsticks together
• Semaphore-based: state machine (THINKING/HUNGRY/EATING)

Best average waiting time: SRTF/SJF (provably optimal for average waiting time).

Deadlock occurs if and only if all four conditions hold simultaneously (Coffman conditions):

1. Mutual Exclusion – At least one resource must be held in a non-shareable mode
2. Hold and Wait – A process holding resources can request more without releasing what it has
3. No Preemption – Resources cannot be forcibly taken; only voluntarily released
4. Circular Wait – A set of processes {P1,P2,...,Pn} where P1 waits for P2, P2 waits for P3, ..., Pn waits for P1

Prevention: Eliminate any one of the four conditions.

Belady's Anomaly: With FIFO, more frames can cause MORE page faults. LRU and OPT do not suffer from this.

OPT is used as a benchmark to evaluate other algorithms.

/proc is a virtual filesystem in RAM that exposes kernel internal state. No data is stored on disk.

In C: open("/proc/cpuinfo", O_RDONLY), parse lines starting with "processor".

All processes form a tree rooted at PID 1 (init/systemd). Each process has exactly one parent (except init). pstree displays this hierarchy graphically, showing which process created which others. Use pstree -p to see PIDs alongside names.

• top – Real-time dynamic view of CPU/memory usage of all running processes
• gdb – GNU Debugger; set breakpoints, inspect variables, trace execution of C programs
• time – Reports real/user/sys execution time of any command

IPC Mechanisms

IPC allows data exchange between processes. Main mechanisms: Pipes, Message Queues, Shared Memory, Sockets, Signals.

1. Mutual Exclusion – Resource held in non-shareable mode
2. Hold and Wait – Holding resources while requesting more
3. No Preemption – Resources released only voluntarily
4. Circular Wait – Circular chain of waiting processes

Data structures needed:

• Available[] – Currently available resources
• Allocation[][] – Resources currently allocated to each process
• Request[][] – Current resource requests of each process

Algorithm Steps:

1. Let Work = Available; For all i: if Allocation[i]≠0 then Finish[i]=false, else Finish[i]=true
2. Find index i such that: Finish[i]==false AND Request[i] ≤ Work
3. If found: Work = Work + Allocation[i]; Finish[i] = true; goto step 2
4. If Finish[i]==false for some i → process Pi is DEADLOCKED

Already covered above in Set 1 D1. Key: Banker's is avoidance (prevents deadlock) while detection finds existing deadlock. Safety check: find a sequence where each process can finish using available + previously released resources.

Need: When a page fault occurs and physical memory is full, the OS must evict (replace) a page to make room. Choice of which page to evict affects performance.

FIFO Page Replacement:

Evict the page that was loaded first (oldest page). Implemented with a queue. Simple but suffers from Belady's Anomaly.

Example: Reference string: 1,2,3,4,1,2,5,1,2,3,4,5 with 3 frames → 9 page faults with FIFO.

Logic Explained

• Thread 1: Matrix addition C[i][j] = A[i][j] + B[i][j]
• Thread 2: Matrix multiplication C[i][j] = Σ A[i][k] × B[k][j]
• Thread 3: Determinant of result matrix (cofactor expansion)

Sample Calculation (2×2):

See Set 1 Q1 and Internal Q1 above for full answer.

• ps – Shows snapshot of current processes (PID, TTY, TIME, CMD). ps aux shows all processes for all users.
• strace – Traces all system calls made by a program. Shows what kernel services a process uses (open, read, write, fork, etc.) and their arguments/return values. Useful for debugging.

Paging Address Translation

A virtual address is split into two parts:

• VPN (Virtual Page Number) = Virtual Address ÷ Page Size
• Offset = Virtual Address mod Page Size

The page table maps VPN → Frame Number (FN). Physical Address = FN × Page Size + Offset.

See Set 1 D1 for full Banker's Algorithm explanation. The safety algorithm checks if there exists a sequence of processes that can all complete given the currently available resources, releasing resources as they complete.

A race condition occurs when multiple processes/threads access shared data simultaneously and at least one modifies it, causing incorrect results.

Semaphore prevents it via mutual exclusion:

Operations: wait(S): atomically check and decrement (block if S=0). signal(S): atomically increment S (wake blocked process if any).

Gantt Chart:

SSTF (Shortest Seek Time First) – Total: 236

Always service the request nearest to current head position.

LOOK – Total: 299

Like SCAN but reverses direction without going to disk ends. Goes to highest request, then sweeps back.

• gdb – GNU Debugger: breakpoints, step execution, variable inspection, backtrace
• objdump – Displays information about object files. Shows disassembly (-d), section headers (-h), symbols (-t). Useful for low-level debugging and understanding compiled code.

In segmentation, a virtual address has two parts: Segment Number (s) and Offset (d).

The Segment Table has entries with: Base (physical start address) and Limit (length of segment).

Translation: If offset d < Limit[s] → Physical Address = Base[s] + d; else → Segment Fault (protection violation).

Key Idea to Break Circular Wait

All philosophers (0–3) pick left chopstick first, then right. Philosopher 4 picks right first, then left. This breaks the circular dependency.

• od (octal dump) – Displays file contents in octal (default), hex (-x), decimal, or ASCII. Used to inspect binary files.
• xxd – Creates a hex dump with ASCII representation side by side. Also can reverse (convert hex back to binary). Useful for examining binary/executable files, reversing patches.

Execution Order (shortest first): P3 → P2 → P4 → P1

Page miss: If frame number is -1 in page table → output "PAGE TABLE MISS! Page not in physical memory."

• time – Measures real/user/sys time of a command execution
• top – Real-time dynamic display of processes (CPU%, MEM%, load average)

In hybrid (paged segmentation), each segment has its own page table.

Virtual address: [Segment # | Page # | Offset]

1. Use Segment # → get segment's page table base
2. Use Page # → get Frame Number from that page table
3. Physical Address = Frame # × Page Size + Offset

Benefits: logical grouping (segmentation) + fixed-size allocation (paging), no external fragmentation.

See Set 1 Q4. Key calls: fork() – create child, exec() – replace image, wait() – sync, exit() – terminate, getpid()/getppid() – get PIDs.

See Set 1 Q12 for process vs thread table.

Multithreading Models

• Many-to-One: Many user threads → 1 kernel thread. Simple but no parallelism. If one blocks, all block.
• One-to-One: Each user thread → 1 kernel thread. True parallelism. More overhead. (Linux, Windows use this)
• Many-to-Many: M user threads → N kernel threads (N≤M). Best of both. Complex to implement.

FIFO – Evict oldest loaded page. Result: 7 faults

LRU – Evict least recently used page. Result: 5 faults

• New – Process is being created
• Ready – Process is waiting to be assigned to CPU
• Running – Process is being executed on CPU
• Waiting/Blocked – Process is waiting for I/O or event
• Terminated – Process has finished execution

Transitions: New→Ready (admitted), Ready→Running (scheduled), Running→Waiting (I/O request), Waiting→Ready (I/O complete), Running→Ready (preempted), Running→Terminated (exit).

Shared memory maps the same physical memory region into multiple processes' address spaces, allowing direct read/write.

shmget() – Creates or gets a shared memory segment by key. Returns shmid.
shmat() – Attaches the segment to the calling process's address space. Returns pointer.

No preemption occurs here (no shorter job arrives mid-execution):

See Set 1 C2 for the complete semaphore-based solution with reader priority.

See Set 3 Impl for the reversed-order-last-philosopher solution using semaphores.