BSc CSIT (TU) Science Operating System (BSc CSIT, CSC259) Question Paper 2079 Nepal

Contiguous Memory Allocation

In contiguous memory allocation, each process is loaded into a single, contiguous block of physical memory. The OS keeps the operating system in one part of memory (usually low memory) and user processes in the remaining space. Memory is allocated to a process as one unbroken region, so the logical addresses map to a contiguous range of physical addresses using a base (relocation) register and a limit register:

Memory can be managed using fixed (static) partitions or variable (dynamic) partitions. As processes are loaded and removed, free and used regions (holes) appear throughout memory, leading to fragmentation.

Internal vs External Fragmentation

Placement Strategies (Dynamic Partitioning)

When a process of size S must be placed and several free holes exist:

• First-Fit: Allocate the first hole (scanning from the start) that is large enough. Fast, but tends to leave fragments near the beginning of memory.
• Best-Fit: Allocate the smallest hole that is large enough. Minimizes leftover in that hole, but searches the whole list and produces many tiny unusable holes, increasing external fragmentation.
• Worst-Fit: Allocate the largest available hole. The leftover hole is large enough to remain useful, but it consumes big holes quickly and generally performs poorly in practice.

Example: Holes of 100K, 500K, 200K, 300K, 600K; request 212K.

• First-Fit → 500K hole (leftover 288K)
• Best-Fit → 300K hole (leftover 88K)
• Worst-Fit → 600K hole (leftover 388K)

Studies show First-Fit and Best-Fit are generally better than Worst-Fit in storage utilization and speed; First-Fit is usually fastest.

Thread

A thread is the smallest unit of execution (a lightweight process) within a process. It consists of a program counter, register set, and a stack, but shares the code section, data section, open files, and other OS resources with the other threads of the same process. A process with multiple threads can perform several tasks at once (multithreading).

Process vs Thread

User-Level Threads (ULT)

Managed entirely by a user-space thread library (e.g., POSIX pthreads at user level); the kernel is unaware of the threads and sees only the process.

• Advantages: Fast creation/switching (no kernel mode switch), portable, application-controlled scheduling.
• Disadvantages: If one thread makes a blocking system call, the whole process blocks; cannot exploit multiple CPUs (no true parallelism).

Kernel-Level Threads (KLT)

Managed directly by the operating system kernel; the kernel maintains a thread control block and schedules individual threads.

• Advantages: True parallelism on multiprocessors; if one thread blocks, others can run; kernel can schedule threads.
• Disadvantages: Slower — creation and switching require kernel intervention (mode switch).

Multithreading Models

The two are combined via mapping models: Many-to-One (many ULT → one KLT), One-to-One (each ULT → one KLT, e.g., Linux/Windows), and Many-to-Many (multiplex m user threads onto n kernel threads).

Structure of an Operating System

The OS structure defines how its components (process management, memory management, file system, I/O, etc.) are organized and how they interact. Major architectural approaches are monolithic, layered, and microkernel.

1. Monolithic Structure

The entire OS runs as a single large program in kernel (privileged) mode. All services — scheduling, memory management, file system, device drivers — reside in one address space and call each other directly (e.g., traditional UNIX, MS-DOS, Linux kernel).

• Merits: High performance (direct procedure calls, no message-passing overhead); good for hardware access.
• Demerits: Hard to maintain and extend; a bug/crash in any module can crash the whole system; poor isolation and reliability.

2. Layered Structure

The OS is divided into hierarchical layers, each built on top of the one below it. Layer 0 is the hardware; the top layer is the user interface. Each layer uses only the services of lower layers (e.g., THE system).

 Layer N : User interface
   ...
 Layer 1 : CPU scheduling
 Layer 0 : Hardware

• Merits: Modular, easy to debug and verify (one layer at a time), good abstraction.
• Demerits: Defining layers is difficult; performance overhead because a request may pass through many layers.

3. Microkernel Structure

Only essential, minimal functions (basic IPC, minimal process and memory management, low-level scheduling) run in the kernel. Other services — file system, device drivers, networking — run as user-space server processes that communicate via message passing (e.g., Mach, QNX, Minix).

• Merits: Highly reliable and secure (less code in kernel → smaller trusted base); easy to extend; a failing service does not crash the kernel; portable.
• Demerits: Performance overhead due to frequent message passing and mode switching between user and kernel space.

Summary

A program is a passive entity — a set of instructions stored on disk (an executable file). A process is an active entity — a program in execution, with its own program counter, registers, stack, data section, and resources allocated by the OS.

In short, a process is a program in execution together with its current activity and context.

System Call

A system call is the programmatic interface through which a user (application) program requests a service from the operating system kernel. It provides a controlled entry point into the kernel, causing a switch from user mode to kernel mode. Examples: read(), write(), fork(), open(), exec().

Types of System Calls

1. Process Control — create/terminate processes, load, execute, wait, allocate/free memory (fork, exit, wait, exec).
2. File Management — create, delete, open, close, read, write, reposition files (open, read, write, close).
3. Device Management — request/release a device, read/write/reposition device (ioctl, read, write).
4. Information Maintenance — get/set time, date, system and process attributes (getpid, time, getattr).
5. Communication — create/delete connections, send/receive messages, shared memory (pipe, send, recv, shmget).
6. Protection — control access to resources, set permissions (chmod, umask, set_permission).

Deadlock and starvation are both situations where processes fail to make progress, but they differ in cause and nature.

Note: every deadlock causes the involved processes to starve, but starvation does not imply deadlock. Starvation is commonly solved by aging (gradually increasing the priority of long-waiting processes).

Context Switching

A context switch is the procedure by which the CPU saves the state (context) of the currently running process and loads the saved state of another process so that execution can be switched between processes. The context (state) is stored in the Process Control Block (PCB) and includes the program counter, CPU registers, memory-management information, and process state.

Steps:

1. Save the context of the current process into its PCB.
2. Update its PCB and move it to the ready/waiting queue.
3. Select the next process (scheduler / dispatcher).
4. Load the saved context of the new process from its PCB and resume it.

Context switches occur on interrupts, system calls, time-slice expiry (in preemptive scheduling), or I/O requests.

Overhead

Context switching is pure overhead — during the switch the system does no useful work for any process. Costs include:

• Time to save and restore registers and PCB contents.
• Cache and TLB flushing/reloading, causing cache misses afterward.
• Memory and scheduler bookkeeping.

Its duration depends on hardware support (e.g., multiple register sets). Excessive context switching (e.g., very small time quantum) reduces CPU efficiency, so the quantum must be balanced against switch cost.

Producer-Consumer Problem

The producer-consumer (bounded-buffer) problem is a classic process-synchronization problem. A producer process generates data and places it into a shared bounded buffer, while a consumer process removes (consumes) data from the buffer. They run concurrently and share the buffer, so access must be synchronized to avoid race conditions and inconsistent data.

Constraints:

• The producer must not add to a full buffer.
• The consumer must not remove from an empty buffer.
• Only one process may access the buffer at a time (mutual exclusion).

Semaphore Solution

Three semaphores are used:

• mutex = 1 → mutual exclusion on the buffer
• empty = n → counts empty slots
• full = 0 → counts filled slots

// Producer
wait(empty); wait(mutex);
   add item to buffer;
signal(mutex); signal(full);

// Consumer
wait(full); wait(mutex);
   remove item from buffer;
signal(mutex); signal(empty);

This ensures the producer blocks when the buffer is full, the consumer blocks when it is empty, and the buffer is never accessed by both simultaneously.

Dining Philosophers Problem

The Dining Philosophers problem is a classic synchronization problem illustrating deadlock and resource allocation among concurrent processes.

Setup: Five philosophers sit around a circular table. Between each pair of philosophers lies one chopstick (fork) — five chopsticks total. A philosopher alternates between thinking and eating. To eat, a philosopher needs both the left and the right chopstick. Each chopstick is a shared resource that only one philosopher can hold at a time.

Naive semaphore solution: represent each chopstick by a semaphore chopstick[i] = 1.

do {
   wait(chopstick[i]);            // pick left
   wait(chopstick[(i+1) % 5]);    // pick right
      // eat
   signal(chopstick[i]);
   signal(chopstick[(i+1) % 5]);
      // think
} while (true);

Problem — Deadlock: if all five philosophers pick up their left chopstick simultaneously, each waits forever for the right one (circular wait).

Solutions to avoid deadlock:

1. Allow at most four philosophers at the table at once.
2. Pick up both chopsticks only if both are available (atomically).
3. Asymmetric rule — odd philosophers pick left first, even philosophers pick right first.

Thrashing

Thrashing is a condition in a virtual-memory (paging) system where a process spends more time paging (swapping pages in and out of memory) than executing useful instructions. It occurs when processes do not have enough frames to hold their working set, so page faults occur almost continuously.

Cause: With too many processes (high degree of multiprogramming), each gets too few frames → high page-fault rate → CPU utilization drops → the OS adds more processes thinking the CPU is idle → page faults worsen → CPU utilization collapses.

Prevention / Handling

1. Working-Set Model: Keep each process's working set (pages used recently within a window) in memory; suspend processes if total demand exceeds available frames.
2. Page-Fault Frequency (PFF) control: Monitor each process's fault rate — if too high, allocate more frames; if too low, take frames away.
3. Reduce the degree of multiprogramming: Swap out (suspend) some processes to give others enough frames.
4. Use local page-replacement (a process steals frames only from itself, not others) and provide more physical memory.

A logical (virtual) address is the address generated by the CPU during program execution; the program references memory using logical addresses. A physical address is the actual address seen by the memory unit (RAM) — i.e., the location in physical memory.

The set of all logical addresses of a program is its logical address space; the set of all corresponding physical addresses is the physical address space. The mapping from logical to physical is done at run time by the Memory Management Unit (MMU), typically by adding the contents of a relocation/base register:

In compile-time and load-time binding the two are identical; in run-time binding they differ, enabling relocation and protection.

Segmentation

Segmentation is a memory-management scheme that supports the user's view of memory: a program is seen as a collection of variable-length logical units called segments — e.g., code (main), function, stack, heap, global variables, symbol table. Each segment has a name (number) and a length.

Address Translation

A logical address in segmentation is a two-part address:

The OS maintains a segment table; each entry stores a base (starting physical address) and a limit (length of the segment):

1. Use s to index the segment table → get base and limit.
2. Check that offset d satisfies $0 \le d < \text{limit}$ (else a trap/segmentation fault).
3. Physical address $= \text{base} + d$.

Characteristics

• Advantages: Matches the logical structure of programs; eases sharing (e.g., shared code segment) and protection (per-segment read/write/execute permissions).
• Disadvantage: Because segments are variable-sized, it suffers from external fragmentation and needs compaction.

Modern systems often combine segmentation with paging to get the benefits of both.