OS_Nov_2024.

pdf - Compiled Answers

PART A - (10 × 2 = 20 marks)
Answer any TEN questions each in 30 words.

1. What do you mean by state of a process?

The state of a process refers to its current condition, such as new, ready, running,
waiting, or terminated, based on its execution and resource usage in the OS.
2. What are the CPU-scheduling criteria?
CPU-scheduling criteria include turnaround time, waiting time, response time,
throughput, and fairness, used to optimize process execution and resource allocation.
3. List out the main resources of an operating system.
Main resources include CPU, memory, I/O devices, files, and network, managed by
the OS to ensure efficient system operation.
4. Define: “Deadlock”.
Deadlock is a situation where two or more processes are blocked indefinitely, each
waiting for resources held by the other, halting progress.
5. What is a thread?
A thread is the smallest unit of processing that can be scheduled by the OS, enabling
multitasking within a single process.
6. What are the functions of memory management?
Memory management allocates, deallocates memory, prevents overlap, manages
virtual memory, and optimizes usage for efficient process execution.
7. Define the term “File”.
A file is a named collection of data or information stored on a storage device,
managed by the OS for reading, writing, or execution.
8. Differentiate between the page and block.
A page is a fixed-size memory unit in virtual memory; a block is a storage unit on
disk, varying in size based on file system.
9. What is a virtual memory?
Virtual memory is a memory management technique that uses disk space as an
extension of RAM, enabling efficient multitasking and larger program execution.
10. What is critical section problem?
The critical section problem occurs when multiple threads access shared resources
concurrently, risking data inconsistency unless synchronized properly.
11. Write a note on kernel.
The kernel is the core of an operating system, managing CPU, memory, and I/O
devices, acting as a bridge between hardware and software.
12. Give any two functions of I/O hardware.
I/O hardware handles data transfer between devices and memory, and manages device
interrupts to signal the OS for processing tasks.
PART B - (5 × 5 = 25 marks)
Answer any FIVE questions, each in 200 words.

13. Elaborate the structure of the operating system.

The operating system (OS) structure is designed to manage hardware and software
resources efficiently. It typically consists of several layers. The lowest layer interfaces
directly with hardware, including device drivers and interrupt handlers, ensuring
proper communication. Above this is the kernel, the core component, which manages
critical tasks like process scheduling, memory allocation, and I/O operations. The
kernel can be monolithic (all services in one module) or microkernel (minimal
functions, with services in user space). The next layer includes system services, such
as file management and network support, providing APIs for applications. The top
layer comprises user interfaces (e.g., command-line or graphical) and application
programs. Modern OS structures, like Linux, use a modular approach, allowing
dynamic loading of components. The structure ensures security, stability, and efficient
resource utilization. For example, a layered design isolates hardware issues from user
applications, enhancing reliability. Diagrams often depict this as a stack, with
hardware at the base and user applications at the top, illustrating the hierarchical
control flow.
14. What are the methods for handling for deadlock? Explain.
Deadlock handling involves strategies to prevent, avoid, detect, or recover from
situations where processes are indefinitely blocked. Prevention ensures conditions like
mutual exclusion, hold-and-wait, or circular wait are avoided, e.g., by pre-allocating
resources. Avoidance uses algorithms like the Banker’s algorithm, which analyzes
resource requests against available resources to ensure safe allocation, preventing
deadlock. Detection involves periodically checking for cycles in the resource
allocation graph; if found, the system identifies deadlocked processes. Recovery
methods include process termination (killing one or more processes) or resource
preemption (temporarily seizing resources from a process). Prevention is proactive
but may reduce resource utilization, while avoidance requires advance knowledge of
resource needs. Detection and recovery are reactive, suitable for dynamic systems, but
risk data loss or delays. For instance, in a banking system, the Banker’s algorithm
ensures loans (resources) are granted only if no deadlock risk exists, maintaining
system stability.
15. Write down the use of semaphore operation.
Semaphores are synchronization tools used to control access to shared resources in a
multitasking environment. They maintain a counter to track resource availability, with
two primary operations: wait (P) and signal (V). The wait operation decrements the
counter; if it becomes negative, the process is blocked until resources are freed. The
signal operation increments the counter, unblocking a waiting process if any. This
ensures mutual exclusion, preventing race conditions in critical sections. For example,
in a printer-sharing system, a semaphore limits access to one process at a time,
avoiding conflicts. Binary semaphores (0 or 1) act as locks, while counting
semaphores handle multiple resources. Semaphores are widely used in multithreaded
applications, like database transactions, to maintain consistency. They are simple yet
powerful, though misuse (e.g., forgetting a signal) can lead to deadlocks. Modern
OSs, like UNIX, implement semaphores in the kernel, enhancing concurrency control
and system reliability.
16. Describe the contiguous memory allocation with neat diagram.
Contiguous memory allocation assigns a process a single, continuous block of
memory. The OS divides memory into partitions, and each process is loaded into one.
This method includes fixed partitioning (predefined sizes) and dynamic partitioning
(adjusted at runtime). Advantages include fast memory access due to locality and
simplicity in implementation. However, it suffers from internal fragmentation (unused
space within allocated blocks) and external fragmentation (scattered free spaces too
small to use). A diagram would show memory as a linear strip, with partitions labeled
(e.g., P1, P2) and free spaces between. The OS uses a first-fit, best-fit, or worst-fit
strategy to allocate space. For instance, if a 100KB process needs 80KB, a 90KB
block might be assigned, leaving 10KB wasted. This method is used in early systems
like MS-DOS but is less common today due to fragmentation issues. Compaction can
mitigate external fragmentation by rearranging memory, though it’s resource-
intensive.
17. Explain the difference between internal and external fragmentation.
Internal and external fragmentation are memory management issues in allocation
schemes. Internal fragmentation occurs when allocated memory is larger than
requested, leaving unused space within the block. For example, in contiguous
allocation, a 100KB block for an 80KB process wastes 20KB. This happens because
memory is assigned in fixed or rounded units, common in paging or contiguous
methods. External fragmentation arises when free memory exists but is non-
contiguous, with blocks too small to satisfy new requests. In dynamic partitioning,
after processes terminate, scattered free spaces (e.g., 10KB and 15KB gaps) cannot
accommodate a 25KB process. Internal fragmentation is predictable and manageable
with better sizing, while external fragmentation requires compaction or
defragmentation, which is costly. Paging reduces external fragmentation by using
fixed-size pages, but internal fragmentation persists. Swapping or virtual memory
techniques further address these, with modern OSs like Windows using demand
paging to minimize both, ensuring efficient memory use.
18. Differentiate between the protection and security.
Protection and security are related but distinct concepts in operating systems (OS),
focusing on resource management and system integrity. Protection refers to
mechanisms within the OS to control access to resources (e.g., memory, files) among
processes or users. It ensures that each process operates within its authorized domain,
preventing unauthorized interference. For instance, the OS uses access control lists
(ACLs) or capabilities to restrict a process from accessing another’s memory,
enforced by the kernel. Protection is internal, dealing with legitimate users or
processes, and is implemented through hardware (e.g., memory segmentation) and
software (e.g., permissions). Security, conversely, addresses external threats, such as
malware, hackers, or unauthorized users attempting to breach the system. It
encompasses authentication (e.g., passwords), encryption, firewalls, and intrusion
detection to safeguard data and resources. While protection operates within a trusted
environment, security extends to untrusted external entities. For example, a protected
file system might prevent a user from deleting a file, but security measures would
block a hacker from gaining access. Modern OSs like Linux integrate both, with
SELinux enhancing security and protection through mandatory access controls,
ensuring a robust defense against internal and external risks.
19. Explain the structures used in file-system implementation.
File-system implementation relies on several key structures to manage data storage
and retrieval efficiently. The boot control block (e.g., boot sector in FAT) contains
startup code and partition details, ensuring the OS loads correctly. The partition
control block or superblock (e.g., in UNIX) stores metadata like file-system size, free
space, and block size, providing an overview of the structure. Inodes (in UNIX-like
systems) or File Control Blocks (FCBs) in others store file-specific information, such
as ownership, permissions, size, and pointers to data blocks, enabling quick access.
Directories organize files hierarchically, mapping file names to inodes or FCBs,
implemented as tables or trees. Data blocks hold the actual file content, allocated
contiguously or non-contiguously (e.g., via linked lists or indexes). Additional
structures like free-space bitmaps or lists track unallocated blocks for efficient
allocation. For example, NTFS uses a Master File Table (MFT) combining inode and
directory functions, while FAT uses a File Allocation Table for chain tracking. These
structures ensure reliability (via journaling), performance (caching), and scalability,
with modern file systems like ext4 optimizing through multi-level indexing, adapting
to diverse storage needs.

PART C - (3 × 10 = 30 marks)
Answer any THREE questions, each in 500 words.

20. What are the CPU-scheduling algorithms? Explain.

CPU scheduling algorithms determine the order in which processes are executed by
the CPU, optimizing resource utilization and system performance. The operating
system (OS) uses these algorithms to manage the process queue, especially in
multitasking environments. Key algorithms include:

 First-Come, First-Served (FCFS): Processes are executed in the order of arrival. It’s
simple but can lead to the “convoy effect,” where short processes wait behind long
ones, increasing average waiting time. For example, if processes P1 (10ms), P2 (5ms),
and P3 (8ms) arrive sequentially, P1 finishes at 10ms, P2 at 15ms, and P3 at 23ms,
with P2 waiting 10ms unnecessarily.
 Shortest Job Next (SJN) or Shortest Process Next (SPN): The process with the
shortest execution time is scheduled next. It minimizes waiting time but requires prior
knowledge of process length, which is impractical. For instance, with P1 (5ms), P2
(10ms), and P3 (2ms), P3 runs first (2ms), P1 (7ms), then P2 (17ms), reducing total
wait time.
 Round Robin (RR): Each process gets a fixed time slice (quantum), and the CPU
switches to the next process after the slice expires. It’s fair and prevents starvation but
can increase context-switching overhead if the quantum is too short. With a 4ms
quantum, P1 (10ms), P2 (5ms), and P3 (8ms) might cycle as P1 (4ms), P2 (4ms), P3
(4ms), P1 (6ms), P2 (1ms), P3 (4ms), and so on.
 Priority Scheduling: Processes are assigned priorities, and the highest-priority
process runs first. Preemptive versions allow higher-priority tasks to interrupt lower
ones. It’s effective but can cause starvation if low-priority processes are indefinitely
delayed, mitigated by aging (gradually increasing priority).
 Multilevel Queue Scheduling: Processes are divided into queues (e.g., system,
interactive, batch) with different scheduling algorithms per queue. Higher-priority
queues get more CPU time, ensuring responsiveness for interactive tasks.
 Multilevel Feedback Queue (MFQ): Extends multilevel queues by allowing process
movement between queues based on behavior (e.g., long CPU bursts move to lower
queues). It adapts dynamically, balancing fairness and efficiency.

These algorithms are evaluated using metrics like turnaround time, waiting time, and
throughput. FCFS suits simple systems, while RR and MFQ are common in modern OSs like
Linux, which uses a variant of MFQ with the Completely Fair Scheduler (CFS). The choice
depends on workload and system goals, with preemptive algorithms (e.g., RR) enhancing
responsiveness in real-time systems.

21. Discuss the deadlock detection with an example.

Deadlock detection identifies when a set of processes are indefinitely blocked, each
waiting for resources held by another, forming a circular wait. The operating system
periodically checks for this condition using a resource allocation graph or matrix-
based algorithms, ensuring system recovery if detected.

The resource allocation graph represents processes as nodes and resources as edges. A cycle
indicates a potential deadlock. For example, consider three processes (P1, P2, P3) and two
resources (R1, R2). P1 holds R1 and requests R2, P2 holds R2 and requests R1, and P3 is
idle. If P1 and P2 enter this state simultaneously, a cycle forms (P1 → R2 → P2 → R1 →
P1), signaling a deadlock. The OS uses a wait-for graph, derived by collapsing resource
nodes, to confirm the cycle.

Alternatively, the Banker’s algorithm (for a single resource type) tracks allocated and
available resources. With processes P1 (needs 3, holds 1), P2 (needs 2, holds 1), and 2 units
available, if P1 requests 2 more and P2 requests 1, the system checks if granting either leaves
enough for the other. If both requests create an unsafe state (no safe sequence to complete
all), a deadlock is detected.

Recovery involves process termination (e.g., killing P1) or resource preemption (e.g., seizing
R1 from P1). In a database system, if two transactions lock tables A and B circularly,
detection triggers a rollback of one, resolving the deadlock. Modern OSs like Windows use
timeout mechanisms alongside graph-based detection, balancing overhead and accuracy.

22. What are the various techniques used for mapping virtual addresses to real
addresses under paging? Explain.
Paging is a memory management technique that maps virtual addresses to physical
(real) addresses using a page table, enabling efficient memory utilization and
protection. Virtual memory is divided into fixed-size pages, and physical memory into
frames, with mapping techniques ensuring seamless translation.

 Single-Level Page Table: Each process has a page table mapping virtual page
numbers (VPNs) to physical frame numbers (PFNs). The virtual address splits into a
page number and offset. The CPU’s Memory Management Unit (MMU) uses the page
table base register to locate the table, indexing the VPN to find the PFN, then adds the
offset. For example, a 32-bit address with 4KB pages has 20 bits for the VPN and 12
for the offset. This is simple but memory-intensive for large address spaces.
 Multi-Level Page Table: For large virtual spaces, a hierarchical structure (e.g., two-
level in x86) reduces memory use. The VPN is split into multiple indices (e.g., page
directory and page table indices), each pointing to the next level. The final level yields
the PFN. This is efficient for sparse memory but adds lookup overhead.
 Inverted Page Table: Instead of one entry per virtual page, it has one entry per
physical frame, using a hash of the VPN to locate the mapping. It saves space in
systems with many processes but requires collision resolution.
 Translation Lookaside Buffer (TLB): A hardware cache stores recent VPN-to-PFN
mappings. On a TLB hit, translation is fast; on a miss, the page table is consulted, and
the entry is cached. TLBs significantly boost performance, with hit rates often
exceeding 90%.

Modern OSs like Linux use multi-level paging with TLBs, supporting 64-bit architectures.
For instance, x86-64 uses four-level paging, handling vast virtual spaces (up to 2^48 bytes)
while minimizing memory overhead. These techniques ensure flexibility, security (via page
permissions), and efficient memory sharing.

23. What are the different accessing methods of a file? Explain.

File access methods determine how data is read from or written to files stored on a
storage device, managed by the operating system (OS) to optimize performance and
usability. These methods cater to different application needs, such as sequential
processing or random access. The primary accessing methods are:

 Sequential Access: Data is accessed in a linear, consecutive order, starting from the
beginning of the file. Each read or write operation moves the file pointer to the next
record. This method is efficient for files processed in order, such as logs or audio
streams. For example, reading a text file line by line using a tape drive (historically)
or a sequential file in a program relies on this. The OS maintains a current position
pointer, advancing it with each operation. While simple and fast for ordered data, it’s
inefficient for non-sequential access, requiring rewinding or fast-forwarding, which
can be time-consuming on mechanical devices.
 Direct Access (Random Access): Data can be accessed at any position without
reading preceding content, using an offset or record number. This is ideal for
databases or indexed files where specific records (e.g., a customer record by ID) are
retrieved. The OS uses file allocation tables (e.g., FAT) or inodes to locate blocks
directly. For instance, in a disk file, the OS calculates the physical block address from
the offset, enabling instant jumps. Modern systems like NTFS support this with
efficient indexing, though it requires more complex file system management and can
lead to fragmentation if not handled properly.
 Indexed Access: An index table maps keys (e.g., record IDs) to file locations,
allowing rapid access to specific records. Common in database systems, the index acts
as a lookup mechanism, stored separately or within the file. For example, a library
catalog might use an indexed file to find a book by ISBN, jumping directly to its
storage location. The OS maintains the index, updating it with file modifications. This
method balances speed and flexibility but increases overhead due to index
maintenance and storage.
 Keyed Access: A variation of indexed access, it uses keys (e.g., names or numbers) to
locate data, often in hierarchical or B-tree structures. Used in advanced file systems or
databases, it supports complex queries. For instance, a payroll system might access
employee records by name via a B-tree index. The OS ensures index integrity, making
it suitable for large, dynamic datasets, though it requires significant computational
resources.

These methods are implemented differently across file systems. UNIX uses inodes for direct
access, while Windows supports random access via the Master File Table (MFT). The choice
depends on application needs—sequential for streaming, random for databases. Modern OSs
optimize these with caching and prefetching, enhancing performance. For example, Linux’s
ext4 uses extent-based allocation to improve direct access speed, adapting to diverse
workloads.

24. Illustrate the functions of Kernel I/O subsystem.

The kernel I/O (Input/Output) subsystem is a critical component of the operating
system (OS) kernel, responsible for managing communication between the CPU,
memory, and peripheral devices like disks, keyboards, and networks. It ensures
efficient, reliable, and secure data transfer, abstracting hardware complexities for user
applications. The primary functions include:

 Device Management: The subsystem identifies and initializes devices during boot,
maintaining a device table with details like type, status, and drivers. For example, it
detects a USB drive and loads the appropriate driver, ensuring compatibility across
diverse hardware.
 I/O Scheduling: It prioritizes and schedules I/O requests to optimize performance
and fairness. Algorithms like FCFS (First-Come, First-Served) or Shortest Seek Time
First (SSTF) for disk I/O minimize latency. For instance, in a multi-user system, it
queues print jobs, preventing resource contention.
 Buffering: Data is temporarily stored in buffers to handle speed mismatches between
devices and the CPU. For example, when reading from a slow disk, the kernel buffers
data in memory, allowing the CPU to process it without waiting, improving
throughput.
 Caching: Frequently accessed data is cached in memory (e.g., disk blocks in the page
cache) to reduce I/O operations. The kernel manages cache consistency, flushing
changes to devices as needed, enhancing performance in systems like Linux.
 Interrupt Handling: The subsystem processes hardware interrupts generated by
devices, signaling completion or errors. For instance, a keyboard interrupt triggers the
kernel to read input, ensuring real-time responsiveness.
 Error Handling: It detects and manages I/O errors (e.g., disk failure or network
drop), retrying operations or notifying users. This ensures system reliability, with logs
maintained for diagnostics.
 Device Driver Interface: The kernel provides a standardized interface for device
drivers, abstracting hardware specifics. Drivers translate OS commands into device-
specific instructions, as seen in graphics card drivers for rendering.
 Synchronization: It coordinates I/O operations among multiple processes, using
semaphores or locks to prevent race conditions. For example, two processes writing to
a printer are serialized to avoid data corruption.
 Security and Access Control: The subsystem enforces permissions, ensuring only
authorized processes access devices. For instance, it restricts raw disk access to
privileged users, enhancing system integrity.

Modern OSs like Windows and Linux implement these via layered architectures, with the
kernel I/O subsystem interacting with user-space libraries (e.g., POSIX I/O). For example,
Linux’s VFS (Virtual File System) layer unifies I/O across devices, while device files (/dev)
provide a uniform interface. This subsystem is vital for multitasking, supporting real-time
systems (e.g., automotive controllers) and high-performance computing, adapting to evolving
hardware like SSDs with tailored scheduling.