Back to Study Material GATE Exam

Last Minute Notes Operating Systems

For last-minute OS revision, start with scheduling formulas since they are the most mechanical to apply. Turnaround time equals completion time minus arriv...

Last Minute Notes Operating Systems

Quick Revision: Scheduling and Synchronization

For last-minute OS revision, start with scheduling formulas since they are the most mechanical to apply. Turnaround time equals completion time minus arrival time. Waiting time equals turnaround time minus burst time. Response time equals time of first CPU allocation minus arrival time. Memorize these definitions because GATE sometimes asks for turnaround time when students are thinking about waiting time and vice versa.

FCFS is non-preemptive, optimal for minimizing context switches, worst for average waiting time under varying burst lengths. SJF minimizes average waiting time among non-preemptive algorithms. SRTF (preemptive SJF) minimizes average waiting time overall. Round Robin provides the best response time for equal-priority processes in a time-sharing environment.

For synchronization, the critical section requires mutual exclusion, progress, and bounded waiting. Peterson's solution uses a turn variable and a flag array to achieve all three for two processes. Software solutions like Peterson's are valid but not used in practice because modern compilers and hardware may reorder instructions — full barriers are needed.

Semaphore signal and wait are atomic. Key rule: always decrement (wait) before the critical section, always increment (signal) after. For multiple semaphores, incorrect ordering of waits can cause deadlock. A dining philosophers deadlock occurs when all five philosophers simultaneously pick up their left fork — a perfect circular wait.

For the readers-writers problem, readers can share access concurrently, but a writer needs exclusive access. The first readers-writers solution (readers get priority) can starve writers. The second solution (writers get priority) can starve readers. A fair solution alternates access. GATE may ask you to trace this solution with a specific arrival schedule and identify whether a writer starves.

Deadlock four conditions: mutual exclusion, hold and wait, no preemption, circular wait. Remove any one condition to prevent deadlock. Banker's Algorithm ensures the system stays in a safe state by computing a safe sequence before granting resource requests.

Quick Revision: Memory Management and File Systems

Memory allocation strategies for contiguous allocation: first-fit allocates the first hole large enough — fast, tends to leave small holes at the front. Best-fit allocates the smallest sufficient hole — minimizes wasted space per allocation but creates many tiny unusable fragments. Worst-fit allocates the largest hole — leaves larger fragments but wastes large free regions. External fragmentation occurs in all three; compaction is the remedy but is costly. Internal fragmentation occurs in fixed-size allocation schemes like paging.

Page table stores the frame number for each virtual page. For a 32-bit virtual address space with 4 KB pages (12-bit offset), the page number is 20 bits, yielding a page table with 2 raised to 20 equals about one million entries. At 4 bytes each, a single flat page table occupies 4 MB — one per process. Two-level paging divides the page number into two 10-bit fields, so only the outermost page directory (4 KB) and the accessed inner tables need to reside in memory, reducing memory overhead.

TLB dramatically reduces effective memory access time. Without TLB, each memory access requires two physical accesses (page table lookup plus data). With TLB hit rate h and TLB access time t, memory access time m: effective access time equals h times (t plus m) plus (1 minus h) times (t plus 2m). Simplified: t plus m plus (1 minus h) times m. For h = 0.9, t = 20 ns, m = 100 ns: effective access time = 20 + 100 + 0.1 times 100 = 130 ns.

Page replacement quick summary: FIFO — replace oldest loaded page; LRU — replace least recently used page; Optimal — replace page used farthest in the future. Only FIFO exhibits Belady's Anomaly.

I-node structure for GATE: with 12 direct pointers, 1 single-indirect (1024 blocks), 1 double-indirect (1024 squared blocks), and 1 triple-indirect (1024 cubed blocks) for 4 KB blocks: maximum file size equals (12 + 1024 + 1024 squared + 1024 cubed) times 4 KB, approximately 4 TB.

Quick Revision: Key OS Definitions and Tricky Points

Processes versus threads: a process has its own address space, file descriptors, and PCB. Threads within the same process share code, data, and heap but have individual stacks and registers. Context switching between threads of the same process is cheaper than between processes because the address space does not change. GATE may ask what is shared and what is private among threads.

User-level threads versus kernel-level threads: user-level threads are managed by a user-space library; the kernel sees only one thread per process. A blocking system call blocks the entire process. Kernel-level threads are managed by the OS; each can block independently. Hybrid models (two-level) map M user threads to N kernel threads.

Spooling stands for Simultaneous Peripheral Operations On-Line. It queues output for a slow device (like a printer) in a fast intermediate storage (disk buffer), allowing the process to continue without waiting for the physical device. This is distinct from buffering, which holds data in memory temporarily to smooth speed mismatches between producer and consumer.

Monolithic kernel versus microkernel: monolithic kernels run all OS services (scheduling, file system, device drivers) in kernel mode — fast but less fault-tolerant. Microkernels move most services to user space, communicating via message passing — more modular and fault-tolerant but slower due to IPC overhead. Linux is monolithic; Mach is a microkernel.

Thrashing: a process spends more time paging than executing because it has fewer frames than its working set requires. The OS detects thrashing via high page-fault frequency and responds by suspending some processes to free their frames for others.

Counting semaphore initialized to n allows n processes to enter a critical section simultaneously — useful for resource pools. Binary semaphore initialized to 1 allows exactly one process — a mutex. Signal on a semaphore with value zero and a waiting process: the waiting process is unblocked, semaphore value remains at zero (or is sometimes described as incrementing to 1 and then immediately decremented — implementation-dependent, but the net effect is one waiting process unblocks).