UGC NET Computer Science System Software and Operating System Syllabus

What is implicit threading and give two examples of its mechanisms.

Implicit threading shifts the creation and management of threads from application developers to compilers and run-time libraries. Examples: thread pools, fork-join frameworks, OpenMP, Grand Central Dispatch, and Intel Threading Building Blocks (TBB).

What semantics issues arise with fork() and exec() in multithreaded programs?

A key threading issue: when a thread calls fork(), should the new process duplicate all threads or only the calling thread? Most systems provide both versions; if exec() will be called immediately, duplicating only the calling thread is sufficient since exec() replaces the entire process image.

List the four CPU-scheduling criteria typically optimized.

CPU utilization (maximize), throughput (maximize processes completed per time), turnaround time (minimize), waiting time (minimize), and response time (minimize). Generally we maximize utilization/throughput and minimize turnaround, waiting, and response times.

Define turnaround time, waiting time, and response time.

Turnaround time = completion time − arrival time (total time from submission to completion). Waiting time = turnaround time − CPU burst time (time spent in the ready queue). Response time = time from submission until the first response/CPU allocation.

Compare FCFS, SJF, and Round Robin scheduling.

FCFS: non-preemptive, by arrival order; simple but causes convoy effect. SJF: picks the shortest next CPU burst; optimal for minimum average waiting time but needs burst prediction and may starve long jobs. Round Robin: preemptive with a time quantum; fair and good response time, performance depends on quantum size.

What is the formula for exponential averaging used to predict the next CPU burst in SJF?

τₙ₊₁ = α·tₙ + (1 − α)·τₙ, where tₙ is the actual length of the nth (most recent) CPU burst, τₙ is the previous prediction, and α (0 ≤ α ≤ 1) weights recent versus past history.

What is priority scheduling and how is starvation handled?

Priority scheduling assigns each process a priority and allocates the CPU to the highest-priority ready process (can be preemptive or non-preemptive). Low-priority processes may starve; the solution is aging—gradually increasing the priority of processes that wait a long time.

What approaches are used for multiple-processor (multiprocessor) scheduling?

Asymmetric multiprocessing (one master processor handles scheduling/system activities, others run user code) and symmetric multiprocessing/SMP (each processor self-schedules from a common or per-processor ready queue). Considerations include processor affinity, load balancing (push/pull migration), and NUMA effects.

Distinguish hard real-time from soft real-time scheduling.

Hard real-time: tasks must complete by their deadline; missing a deadline is a system failure. Soft real-time: critical tasks get priority over non-critical ones, but no absolute deadline guarantee—missing a deadline degrades quality but is tolerable.

State the rate-monotonic scheduling priority rule and its key property.

Rate-monotonic scheduling assigns static priorities inversely proportional to period: shorter period → higher priority. It is optimal among fixed-priority algorithms; n periodic tasks are schedulable if total CPU utilization ≤ n(2^(1/n) − 1), which approaches ln 2 ≈ 0.693 as n → ∞.

State the four necessary conditions for a deadlock to occur.

Mutual exclusion (resources non-shareable), Hold and wait (a process holds resources while waiting for more), No preemption (resources released only voluntarily), and Circular wait (a cycle of processes each waiting on a resource held by the next). All four must hold simultaneously.

What are the four methods for handling deadlocks?

Deadlock prevention (negate one of the four necessary conditions), deadlock avoidance (use advance info, e.g., Banker's algorithm, to stay in safe states), deadlock detection and recovery (allow deadlocks, detect, then recover), and ignore the problem (the ostrich approach used by many OSes).

How does deadlock prevention work for each necessary condition?

Mutual exclusion: make resources shareable where possible (not always feasible). Hold-and-wait: require requesting all resources at once or releasing before requesting. No preemption: preempt held resources if a request can't be granted. Circular wait: impose a total ordering on resource types and request in increasing order.

What is a safe state in the Banker's algorithm, and why does avoidance rely on it?

A safe state is one in which there exists a sequence of all processes (a safe sequence) such that each can obtain its maximum needed resources from currently available plus those released by predecessors. Deadlock avoidance grants a request only if the resulting state remains safe, guaranteeing no deadlock (unsafe state may lead to deadlock).

How are deadlocks detected and what are the recovery options?

Detection: for single-instance resources, look for a cycle in the wait-for graph; for multiple instances, use a detection algorithm similar to the Banker's safety check. Recovery: abort processes (all deadlocked or one at a time until the cycle breaks) or preempt resources (selecting a victim, rolling back, and avoiding starvation).

What is external fragmentation and how does it relate to contiguous memory allocation?

External fragmentation occurs when free memory is broken into many small non-contiguous holes so that, although total free space is sufficient, no single hole is large enough for a request. It afflicts contiguous allocation and can be reduced by compaction or by using paging/segmentation.

Compare first-fit, best-fit, and worst-fit allocation strategies.

First-fit: allocate the first hole large enough (fast). Best-fit: allocate the smallest hole that fits (minimizes leftover but leaves tiny fragments and is slower). Worst-fit: allocate the largest hole (leaves a usable large remainder). First-fit and best-fit generally outperform worst-fit in storage utilization.

What is swapping in memory management?

Swapping temporarily moves an entire process (or pages) out of main memory to a backing store (swap space on disk) and brings it back later, allowing the total physical memory used by all processes to exceed actual RAM. It increases the degree of multiprogramming at the cost of swap overhead.

Explain how paging translates a logical address to a physical address.

The logical address is split into a page number p and an offset d. The page number indexes the page table to obtain the frame number f; the physical address is then f × frame_size + d. A TLB caches recent page-table entries to speed translation.

What is the effective memory access time formula with a TLB?

EAT = h·(t_TLB + t_mem) + (1 − h)·(t_TLB + 2·t_mem), where h is the TLB hit ratio, t_TLB is TLB lookup time, and t_mem is memory access time. (On a hit: TLB + one memory access; on a miss: TLB + page-table access + the actual access.)

Compare paging and segmentation.

Paging divides memory into fixed-size pages/frames; it is invisible to the programmer and causes internal fragmentation but no external fragmentation. Segmentation divides memory into variable-size logical units (code, data, stack) reflecting the program's structure; it causes external fragmentation but supports protection/sharing at the logical level.

What is demand paging and what is a page fault?

Demand paging loads pages into memory only when they are referenced (lazy loading), using a valid/invalid bit in the page table. A page fault is the trap raised when a process references a page not in memory; the OS then locates it on disk, brings it into a free frame, updates the page table, and restarts the instruction.

Describe the FIFO, Optimal, and LRU page-replacement algorithms.

FIFO replaces the oldest-loaded page (simple, suffers Belady's anomaly). Optimal (OPT/MIN) replaces the page that will not be used for the longest future time (lowest fault rate but unrealizable—needs future knowledge). LRU replaces the page least recently used (good approximation of optimal, needs hardware support like counters/stack).

What is Belady's anomaly?

Belady's anomaly is the counterintuitive phenomenon where increasing the number of allocated frames causes the page-fault rate to increase (rather than decrease) for certain reference strings. It occurs with FIFO replacement but not with stack algorithms like LRU or OPT.

What is thrashing and how can it be controlled?

Thrashing is a state of high paging activity where a process spends more time paging than executing because it lacks enough frames for its working set, causing CPU utilization to collapse. It is controlled using the working-set model or the page-fault frequency (PFF) scheme to allocate frames appropriately and limit multiprogramming.

What is the working-set model?

The working set is the set of pages a process has referenced in the most recent Δ (working-set window) page references; it approximates the process's locality. The OS allocates each process enough frames to hold its working set; if the sum of all working sets exceeds available frames, it suspends a process to prevent thrashing.

Compare contiguous, linked, and indexed file allocation methods.

Contiguous: file occupies consecutive blocks—fast sequential/direct access but external fragmentation and growth problems. Linked: each block points to the next—no external fragmentation, good for sequential access but poor random access and pointer overhead. Indexed: an index block holds all data-block pointers—supports direct access without external fragmentation, at the cost of index-block overhead.

What free-space management techniques does a file system use?

Bit vector/bitmap (one bit per block, easy to find contiguous free blocks but needs memory), linked list of free blocks (no waste but slow traversal), grouping (first free block stores addresses of n free blocks), and counting (stores address of first free block plus a count of contiguous free blocks).

List common disk-scheduling algorithms and the goal they optimize.

FCFS, SSTF (shortest seek time first), SCAN (elevator), C-SCAN, LOOK, and C-LOOK. They aim to minimize total seek time / head movement and improve disk throughput; SCAN/C-SCAN provide more uniform wait times and avoid the starvation possible with SSTF.

Compare RAID levels 0, 1, and 5.

RAID 0: striping, no redundancy—high performance, no fault tolerance. RAID 1: mirroring—full redundancy (duplicate copies), high reliability but 50% storage overhead. RAID 5: block-level striping with distributed parity—tolerates one disk failure with lower overhead (one parity block per stripe), good read performance with a write penalty due to parity updates.

In OS protection, what is an access matrix and what are its rows and columns?

The access matrix is a model of protection where rows represent domains (subjects) and columns represent objects (resources); entry access[i,j] lists the operations domain i may perform on object j. It is implemented practically via access control lists (by column) or capability lists (by row).