Chapter 1: Operating System Overview
Define the terms shell and system call. How is it handled? Illustrate with a suitable example. (2079)
1 What is a system call? Describe the transition between different states of a process. (2079)
2 When does a request switch from user mode to kernel mode? Give an answer with an example. (2078)
3 What is a system call? Discuss the process of handling system calls briefly. (2078)
4 What are two modes of OS? Discuss different OS structures briefly. (2076)
5
Chapter 2: Process Management
Explain the Sleeping Barber problem. Illustrate how it can be solved. (2081)
6 Calculate the average waiting time and turnaround time using the priority algorithm (Priority 1 being the highest) for the given scenario. (2081)
7 Explain how a semaphore solves the problem of a critical section. (2081)
8 Explain Inter-Process Communication in Linux. (2081)
9 9 Define the term race condition. Justify that a race condition leads to data loss or incorrect data. (2080)
10 How do you distinguish between deadlock and starvation? (2080)
11 Find the average waiting time and average turnaround time for the following set of processes using FCFS, SJF, RR (Quantum = 3), and the shortest remaining time next. (2080)
12 When does race condition occur in inter-process communication? What does busy waiting mean and how can it be handled using sleep and wakeup strategy? (2079)
13 Distinguish between starvation and deadlock. How does the system schedule a process using multiple queues? (2079)
14 For the following dataset, compute the average waiting time for SRTN and SJF. (2079)
15 What kind of problem arises with the sleep and wakeup mechanism of achieving mutual exclusion? Explain with a suitable code snippet. (2078)
16 How do you recognize a critical section? Why do we need to synchronize it? (2078)
17 Can deadlock occur in the case of preemptive resources? List the conditions for deadlock. Define the allocation graph with an example. (2078)
18 Find the average waiting time and turnaround time for the process scheduling algorithms FCFS, Priority, and RR (Quantum = 2) in the following given dataset. (2078)
19 What is a lock variable? Discuss its working and problems associated with it in detail. (2078)
20 Discuss the concept of SJF and SRTN scheduling algorithms with a suitable example. (2078)
21 What is the problem associated with semaphores? Explain the concept of monitors in brief. (2076)
22 What are the main goals of interactive system scheduling? Discuss priority scheduling along with its pros and cons. (2080)
23 When are threads better than processes? Explain the concept of user-level threads in detail. (2076)
24 Differentiate between multi-programming and monoprogramming. What will be the CPU utilization with 6 processes with 60% I/O waiting time in memory? (2076)
25 How can you manage free disk space? Explain the linked list approach of managing free disk space with an example. [Repeated: 2078, 2076]
26 Define interactive system goals? List various interactive scheduling algorithms. Consider the following process data and compute average waiting time and average turnaround time for RR(quantum 10) and priority scheduling algorithms. (2076)
27 What makes a thread different from a process? Draw the transition diagram between the states of a process. [Repeated: 2080]
28 How threads differ from processes? Explain thread usages. [Repeated: 2080]
29 What is the main purpose of disk scheduling algorithms? Which disk scheduling technique is best but impractical? Explain the algorithm with an example. (2080)
30 List any two demerits of disabling interrupts to achieve mutual exclusion. Describe about fixed and variable partitioning. (2079)
31 When does a page fault occur? Give a structure of a page table. [Repeated: 2080]
32
Chapter 3: Process Deadlocks
How do you think deadlock can be avoided? Explain. (2081)
33 Illustrate the term safe and unsafe state in deadlock prevention with a scenario. (2079)
34 How starvation differs from deadlock? Consider the following situation of processes and resources: (2080)
35 What will happen if process P3 requests 1 resource? (2080)
36 What will happen if process P4 requests 1 resource? (2080)
37 How unsafe state differs from a deadlocked state? Consider the following initial state and identify whether the request is granted or denied for the given cases. (2078)
38 What will happen if process D requests 1 resource? (2078)
39 What will happen if process A requests 1 resource? (2078)
40 What is a resource allocation graph? Explain the process of detecting deadlocks when there is a single instance of each resource with a suitable example. (2078)
41 Differentiate between deadlock and starvation? Discuss the process of detecting deadlocks when there are multiple resources of each type. (2076)
42 Is the system in a safe state? (2079)
43 If P1 requests (0,4,2,0) can the request be granted immediately? (2079)
44
Chapter 4: Memory Management
Explain the translation of a logical address into a physical address using a segment table with a necessary diagram. (2081)
45 List advantages and disadvantages of segmentation. (2081)
46 Explain microkernels and exokernels. (2081)
47 Consider a swapping system in which memory consists of the following hole sizes in memory order: 15 MB, 2 MB, 10 MB, 6 MB, 8 MB and 20 MB. Which hole is taken for successive segment requests of: (a) 10 MB and (b) 10 MB for first fit, next fit and best fit. (2081)
48 Explain memory-mapped I/O. (2081)
49 Explain the working mechanism of TLB. (2080)
50 Why do we need virtual memory? Describe the structure of a page table. (2079)
51 Find the number of page faults using FIFO and LRU for the reference string 4, 7, 6, 1, 7, 6, 1, 2, 7, 2 with a frame size of 3. (2079)
52 Define working set. How does the clock replacement algorithm work? (2079)
53 What are the physical addresses for the following logical addresses? (2080)
54 a. 0,430 (2080)
55 b. 1,10 (2080)
56 c. 1,11 (2080)
57 d. 2,500 (2080)
58 When a page fault occurs and how it is handled? Demonstrate the second chance and LRU page replacement algorithm for memory with three frames and the following reference string: 1,3,7,4,5,2,3,6,4,5,7,8,5,1,4. (2080)
59 Consider the request for the page references 7,0,1,2,0,3,0,4,2,3,0,3,2. Find the number of page faults for FIFO and LRU with 4 page frames. (2078)
60 Explain different memory allocation strategies. (2078)
61 Differentiate between paging and segmentation. (2078)
62 What does Belady's anomaly mean? What are the benefits of multiprogramming over uniprogramming? (2078)
63 How can we achieve mutual exclusion? Describe. (2078)
64 Why OPR is the best but not a practically feasible page replacement algorithm? Calculate the number of page faults for OPR, LRU, and Clock page replacement algorithm for the reference string: 1, 3, 4, 2, 3, 5, 4, 3, 1, 2, 4, 6, 3, 2, 1, 4, 2. Assume the memory size is 3. (2078)
65 Differentiate between internal and external fragmentation? Suppose that we have a memory of 100 KB with 5 partitions of size 150 KB, 200 KB, 250 KB, 100 KB, and 300 KB. Where the processes A and B of size 175 KB and 125 KB will be loaded, if we use Best-Fit, and Worst-Fit Strategy? (2078)
66 How Second Chance page replacement algorithm differs from FIFO page replacement policy? Discuss the concept of Belady’s anomaly with a suitable example. (2076)
67 Why program relocation and protection is important? Explain the technique of achieving program relocation and protection. (2076)
68 Consider the page references 7,0,1,2,0,3,0,4,2,3,0,3,2. Find the number of page faults using OPR and FIFO, with 4 page frames. (2079)
69 Why do we need the concept of locality of reference? List the advantages and disadvantages of the Round Robin algorithm. (2079)
70
Chapter 5: File Management
Q1: List different file structures and explain them.
Solution:
A file structure defines how data is organized and stored inside a file.
It determines how the system reads, writes, and manages the file efficiently.
Different applications use different file structures based on their data access needs.
Types of File Structures:
Sequential File Structure:
Data is stored one after another in a specific order.
Suitable for applications that process data sequentially (from start to end).
Example: Payroll processing, where records are read in sequence.
Advantages: Simple and easy to implement.
Disadvantages: Slow for searching or updating specific records.
Illustration:
Record1 → Record2 → Record3 → Record4
Indexed File Structure:
Uses an index table to quickly locate records in the file.
Each record has an associated index value (like a key).
Example: Database systems use indexes to access data faster.
Advantages: Faster access compared to sequential files.
Disadvantages: Extra storage needed for index.
Illustration:
Index: [1 → Record1], [2 → Record2], [3 → Record3]
Hashed File Structure:
A hash function converts a record’s key into an address where it’s stored.
Provides direct access to records.
Example: Used in situations requiring fast lookups, like symbol tables.
Advantages: Very fast access for known keys.
Disadvantages: Collisions can occur when two keys map to the same address.
Illustration:
Hash(Key) → Address → Record
Conclusion:
Different file structures — Sequential, Indexed, and Hashed — are chosen based on the speed, access method, and storage requirements of an application.
Q2: Discuss about contiguous and linked list file allocation technique.
Solution:
File Allocation refers to the method used by the operating system to store and manage files on disk blocks.
It determines how file data is organized and accessed efficiently.
Two common file allocation techniques are Contiguous Allocation and Linked Allocation.
1. Contiguous File Allocation:
In Contiguous Allocation, each file occupies a set of contiguous (adjacent) blocks on the disk.
The directory stores the starting block address and the length (number of blocks).
Example:
If a file needs 5 blocks and starts at block 10 → blocks 10, 11, 12, 13, 14 are allocated.
Advantages:
Fast access – Supports direct and sequential access easily.
Simple to implement – Only starting address and length are stored.
Good read performance – As blocks are physically adjacent.
Disadvantages:
External fragmentation – Free space gets scattered over time.
Difficult to grow files – If adjacent space isn’t available.
Requires knowing file size in advance.
2. Linked List File Allocation:
In Linked Allocation, each file is stored in non-contiguous disk blocks linked together using pointers.
Each block contains data and a pointer to the next block.
Example:
A file is stored in blocks 5 → 13 → 9 → 20, each pointing to the next block.
Advantages:
No external fragmentation – Any free block can be used.
Easy file growth – New blocks can be added anywhere.
Efficient space utilization.
Disadvantages:
Sequential access only – Random access is slow.
Pointer overhead – Each block must store a pointer.
Risk of broken links – If a pointer is lost or damaged.
Q3: Why do we need a hierarchical directory system? Explain the structure of a disk.
Solution:
A hierarchical directory system organizes files in a tree-like structure with directories and subdirectories.
It allows better management, access, and organization of files in large systems.
Disk structure defines how data is physically stored and accessed on storage devices.
1. Need for Hierarchical Directory System:
Avoid Name Conflicts:
Multiple files can have the same name in different directories, preventing conflicts.
Organized File Storage:
Files are grouped logically using directories and subdirectories.
Efficient File Access:
Searching for a file is easier with a tree-like structure than a single flat directory.
Security and Access Control:
Permissions can be applied at the directory level, enhancing security.
Scalability:
Handles large numbers of files efficiently as the system grows.
2. Structure of a Disk:
A disk is a storage medium that stores data magnetically or electronically in blocks.
Disk structure defines the physical and logical organization of data for access.
Components:
Disk Surface:
The disk has one or more platters, each with two surfaces that store data magnetically.
Tracks:
Each surface is divided into concentric circles called tracks.
Each track stores a sequence of blocks.
Sectors:
Tracks are divided into small arcs called sectors.
Each sector holds a fixed-size block of data (e.g., 512 bytes).
Cylinders:
A cylinder is a set of tracks aligned vertically across platters.
It helps in faster data access by reducing head movement.
Blocks:
Basic unit of storage, often equal to a sector.
Files are stored in one or more blocks.
Disk Head:
Read/write heads move radially to access data on tracks.
Q4: Explain directory implementation techniques employed in operating systems briefly.
Solution:
A directory is a structure that stores file names, attributes, and pointers to their data.
Directory implementation determines how files are organized, accessed, and managed.
Efficient directory structures help in fast file search and management.
Directory Implementation Techniques:
Single-Level Directory:
All files are stored in one directory.
Advantages: Simple and easy to implement.
Disadvantages: Cannot handle large number of files; name conflicts may occur.
Example: Early MS-DOS systems.
Illustration:
Directory → [File1, File2, File3, …]
Two-Level Directory:
Each user has a separate directory under the main directory.
Advantages: Resolves name conflicts between users.
Disadvantages: Cannot handle nested file organization.
Example: UNIX early versions.
Illustration:
Main Directory
├─ User1: [File1, File2]
└─ User2: [File1, File3]
Hierarchical (Tree-Structured) Directory:
Files are organized in a tree structure with directories and subdirectories.
Advantages: Supports nested directories; efficient file organization.
Disadvantages: More complex to implement.
Example: Modern Windows, Linux file systems.
Illustration:
Root
├─ Dir1
│ ├─ File1
│ └─ File2
└─ Dir2
└─ File3
Acyclic-Graph Directory:
Files and directories can have multiple parent directories.
Advantages: Supports file sharing between directories.
Disadvantages: Needs careful handling of cycles to avoid infinite loops.
General Graph Directory:
Directories can form a general graph with links.
Advantages: Supports advanced file sharing and links.
Disadvantages: Complex structure; requires cycle detection.
Q5: What is an I-node? Why is it superior to other file allocation approaches? Consider a 20-GB disk with an 8-KB block size. How much memory space will be occupied if contiguous, and File Allocation Table is used for file allocation? Assume that each FAT entry takes 4 bytes.
Solution:
An I-node (Index Node) is a data structure in Unix/Linux file systems that stores metadata about a file.
It does not store file data, but contains information needed to access the file.
Each file has a unique I-node number in the file system.
Components of an I-node:
File type: Regular, directory, etc.
File size in bytes.
File permissions and access control information.
Timestamps: Creation, modification, last access.
Link count: Number of directory entries pointing to the file.
Pointers to data blocks: Direct, indirect, and double/triple indirect pointers.
Why I-node is Superior:
Efficient file access:
Direct and indirect pointers allow fast access to file data.
Supports large files:
Uses multi-level indexing, handling large files efficiently.
No fragmentation issues:
Unlike contiguous allocation, blocks need not be consecutive.
Simplifies metadata management:
All file metadata is stored separately from data blocks.
Supports hard links:
Multiple directory entries can point to the same I-node, enabling file sharing.
Q6: Discuss contiguous and linked list file allocation techniques.
Solution:
File allocation determines how files are stored on disk blocks.
Different techniques help in efficient storage, access, and management of files.
1. Contiguous File Allocation:
All blocks of a file are stored sequentially on disk.
Advantages:
Fast access: Sequential reading/writing is efficient.
Simple structure: Easy to calculate block addresses.
Disadvantages:
External fragmentation: Finding large contiguous space can be difficult.
File size limitation: Extending a file may require moving it if contiguous space is unavailable.
Example: If file A needs 5 blocks, it is stored in blocks 10–14.
2. Linked List File Allocation:
Each file block contains a pointer to the next block.
Advantages:
No external fragmentation, as blocks can be anywhere on disk.
Easy to extend a file by adding more blocks.
Disadvantages:
Sequential access only: Random access is slow.
Pointer overhead: Each block stores extra pointer information.
Example: File B has blocks 3 → 8 → 15 → 22 (each pointing to the next).
Conclusion:
Contiguous allocation is fast but inflexible, while linked list allocation is flexible but slower for random access.
Choice depends on file size, access patterns, and storage availability.
Q7: What is meant by file attributes? Discuss any one technique of implementing directories in detail.
Solution:
File attributes are metadata or information about a file.
Purpose: Help the operating system manage, identify, and protect files.
Common File Attributes:
Name: Unique identifier of the file.
Type: File type (text, binary, executable, etc.).
Location: Pointer(s) to the disk blocks storing the file.
Size: File length in bytes or blocks.
Protection/Permissions: Read, write, execute rights for users.
Timestamps: Creation, modification, and last access times.
Other attributes: Owner ID, group ID, number of links.
Directory Implementation Technique – Single-Level Directory:
All files are listed in one single directory.
Structure:
Directory contains file names and pointers to their locations on disk.
Example Table:
File Name Pointer to Disk Block
file1.txt 120
file2.doc 125
Advantages:
Simple to implement.
Easy to locate a file by name.
Disadvantages:
Name conflicts if multiple users use the same file name.
Not suitable for large number of files.
Conclusion:
File attributes store essential metadata for file management.
Single-level directory is simple but limited in handling multiple users or large file systems.
Q8: What approaches are used for managing free disk spaces? Explain the linked list approaches with an example.
Solution:
Free space management keeps track of unallocated disk blocks.
It helps the OS find free blocks efficiently when storing new files.
Efficient management reduces fragmentation and improves disk utilization.
1. Approaches for Managing Free Disk Space:
Bit Vector (Bitmap):
Each block is represented by a bit (0 = free, 1 = allocated).
Easy to find consecutive free blocks.
Requires memory proportional to the number of blocks.
Linked List:
All free disk blocks are linked together.
Each free block contains a pointer to the next free block.
Grouping:
A block stores addresses of several free blocks together.
Reduces number of disk accesses.
Counting:
Stores the starting block number and count of consecutive free blocks.
Useful for contiguous free space allocation.
2. Linked List Approach (Explanation):
In this method, each free block contains a pointer to the next free block on the disk.
The OS maintains a head pointer to the first free block.
When a block is allocated, the pointer is updated to the next free block.
Example:
Suppose there are free blocks: 5, 8, 12, 15
The linked list will look like:
[Block 5] → [Block 8] → [Block 12] → [Block 15] → NULL
Head Pointer = 5 (points to first free block).
When block 5 is allocated, the head moves to 8.
Advantages:
Simple and easy to implement.
No need for a large in-memory table.
Disadvantages:
Accessing free blocks is sequential, so searching can be slow.
Pointer storage in each block reduces usable space slightly.
Q9: Discuss the advantages and disadvantages of implementing a file system using a Linked List.
Solution:
In the Linked List file allocation, each file is stored in non-contiguous blocks on the disk.
Every block contains data and a pointer to the next block of the same file.
The directory holds the address of the first block of the file.
Structure Example:
File A → [Block 5] → [Block 9] → [Block 13] → NULL
Each block contains the address of the next block.
The last block pointer is NULL, marking the end of the file.
Advantages:
Efficient Disk Utilization:
Eliminates external fragmentation, as blocks can be stored anywhere.
Dynamic File Size:
Files can grow or shrink easily by adding or removing blocks.
Simple Management:
No need to pre-allocate space for files.
Sequential Access Efficiency:
Suitable for sequential file access, as pointers provide direct linkage.
Disadvantages:
Slow Random Access:
Accessing the n-th block requires traversing all previous blocks, which is slow.
Pointer Overhead:
Each block must store a pointer, reducing usable disk space.
Reliability Issues:
If a pointer is lost or damaged, the entire file chain breaks.
Complex Recovery:
Harder to recover files after system crashes.
Q10: What is the task of a disk controller? List some drawbacks of segmentation.
Solution:
A disk controller is a hardware component that manages the communication between the CPU and disk drives.
It acts as an interface that controls data transfer, error detection, and disk access operations.
2. Tasks of a Disk Controller:
Command Interpretation:
Interprets commands from the CPU such as read, write, or seek.
Data Transfer Management:
Transfers data between main memory and disk blocks efficiently.
Error Detection and Correction:
Detects and corrects read/write errors using checksums or ECC codes.
Seek and Rotational Control:
Controls the movement of the read/write head to the correct track and sector.
Buffering and Caching:
Uses internal buffers to store data temporarily for faster access.
Scheduling:
Handles multiple I/O requests to improve performance and reduce waiting time.
3. Drawbacks of Segmentation:
External Fragmentation:
Free memory is divided into small segments, causing unused gaps.
Complex Memory Management:
Tracking and maintaining multiple variable-sized segments increases management overhead.
Slow Access:
Address translation (segment number + offset) takes more time than simple paging.
Limited Segment Size:
Programs that exceed the maximum segment size must be divided, complicating execution.
Swapping Overhead:
Moving variable-sized segments between memory and disk is inefficient.
Q11: Discuss about single level and two level directory systems.
Solution:
A directory system organizes and manages files in an operating system.
It helps in storing, locating, and accessing files efficiently.
Single-level and two-level directory systems are the basic types used in file organization.
1. Single-Level Directory System:
All files are kept in one single directory shared by all users.
Structure:
Root Directory
├── File1
├── File2
└── File3
Advantages:
Simple to Design: Easy to implement and understand.
Easy Searching: All files are in one location.
Disadvantages:
Name Conflicts: Two users cannot have files with the same name.
Poor Organization: Difficult to manage large numbers of files.
No User Privacy: All users share the same directory space.
2. Two-Level Directory System:
Each user has a separate directory under a master directory.
Structure:
Master Directory
├── User1 Directory
│ ├── FileA
│ └── FileB
└── User2 Directory
├── FileC
└── FileD
Advantages:
Avoids Name Conflicts: Different users can have files with the same name.
Better Security: Each user’s files are kept separate.
Improved Organization: Files are grouped under user directories.
Disadvantages:
Limited Grouping: Users cannot share files easily.
More Complex Management: Slightly harder to maintain than a single-level system.
Chapter 6: Device Management
Q1: Find the seek time using SCAN, C-SCAN, Look and C-Look disk scheduling algorithms for processing the following request queue: 35, 70, 45, 15, 65, 20, 80, 90, 75, 130. Suppose the disk has tracks numbered from 0 to 150 and assume the disk arm to be at 30 and moving outward.
Solution:
Q2: How DMA operation is performed? Consider a disk with 200 tracks and the queue has random requests from different processes in the order: 45, 48, 29, 17, 80, 150, 28 and 188. Find the seek time using FIFO, SSTF and SCAN. Assume the initial position of the head as 100.
Solution:
DMA (Direct Memory Access) is a method that allows I/O devices to directly transfer data to or from main memory without the continuous involvement of the CPU.
It improves system performance by freeing the CPU during data transfer operations.
A special hardware component called the DMA Controller (DMAC) manages this process.
Steps in DMA Operation:
DMA Request:
An I/O device (like a disk or network card) sends a DMA request (DRQ) signal to the DMA controller when it needs to transfer data.
CPU Grants Control:
The CPU temporarily suspends its control of the system bus and sends a DMA acknowledgment (DACK) signal to the DMA controller.
The CPU then enters an idle state or performs other tasks.
DMA Takes Over the Bus:
The DMA controller takes control of the address bus, data bus, and control bus.
It acts as a bus master for the duration of the data transfer.
Data Transfer:
The DMA controller transfers data directly between the I/O device and main memory.
The CPU is not involved in the actual transfer process.
Completion and Interrupt:
Once the transfer is complete, the DMA controller releases the system bus back to the CPU.
It then sends a DMA interrupt to notify the CPU that the data transfer is finished.
Q3: Suppose a disk has 201 cylinders, numbered from 0 to 200. At the same time, the disk arm is at cylinder 10, and there is a queue of disk access requests for cylinders 30, 85, 90, 100, 105, 110, 135, and 145. Find the total seek time for the disk scheduling algorithm FCFS and SSTF. Assume the head is moving inward.
Solution:
Q4: What are the advantages of using interrupts? Describe.
Solution:
An interrupt is a signal from hardware or software when a process needs immediate attention, alerting the processor to a high-priority process.
It allows the CPU to respond quickly to important or time-critical tasks.
After servicing the interrupt, the CPU resumes its previous task.
Advantages of Using Interrupts:
Efficient CPU Utilization:
The CPU does not waste time continuously checking (polling) for events.
It performs other tasks and responds only when needed.
Fast Response to Events:
Interrupts ensure immediate attention to important events like I/O completion or hardware faults.
Useful in real-time systems.
Better System Performance:
Interrupts allow parallel processing — CPU executes programs while I/O devices work independently.
Reduces idle time of both CPU and devices.
Improved I/O Handling:
Interrupts simplify I/O operations by signaling the CPU only when data is ready.
Eliminates the need for constant status checking.
Support for Multitasking:
Interrupts enable the OS to switch between processes efficiently.
Allows preemptive scheduling in multitasking systems.
Error Handling and Recovery:
Hardware and software interrupts help detect and handle errors like memory faults or divide-by-zero.
Q5: Why the concept of disk interleaving is important? Explain with a suitable example.
Solution:
Disk Interleaving is a technique used to improve disk I/O performance by arranging data sectors on a disk in a specific sequence.
It helps match the speed of the CPU and the disk’s data transfer rate, preventing data loss or waiting time.
It ensures that the CPU has enough time to process one sector before the next sector arrives.
Need / Importance of Disk Interleaving:
Speed Mismatch Handling:
Disk rotates continuously, but the CPU or controller may not be fast enough to read consecutive sectors immediately.
Interleaving gives the CPU time to process data before the next sector comes under the read head.
Efficient Data Transfer:
Prevents skipping of sectors due to slow data handling by the CPU.
Ensures smooth, continuous reading or writing of data.
Reduced Latency:
Minimizes the waiting time for the next required sector to rotate under the read/write head.
Improved System Performance:
Increases the effective data transfer rate and overall system efficiency.
Example:
Let’s assume a disk has 8 sectors (0–7) arranged sequentially.
Without Interleaving (1:1):
Sectors are arranged as: 0, 1, 2, 3, 4, 5, 6, 7
After reading sector 0, the CPU takes time to process it.
By the time it’s ready for sector 1, the disk has already rotated past it → CPU must wait one full rotation.
With Interleaving (2:1):
Sectors arranged as: 0, 2, 4, 6, 1, 3, 5, 7
After reading sector 0, while CPU processes it, sector 1 moves into position just in time.
No waiting → Faster continuous reading.
Q6: What is the main objective of disk scheduling algorithms? why SSTF is not practically feasible? Assume that we have a disk with 100 tracks and currently the head is at track number 35. What will be the seek time for the algorithms SCAN and LOOK for processing IO requests queue: 52, 67, 27, 11, 43, 85, 18, 75, 92, 8?
Solution:
Disk Scheduling Algorithms determine the order in which I/O requests are serviced on a disk.
Since disk access time depends on the movement of the read/write head, efficient scheduling minimizes the total head movement.
Main Objectives of Disk Scheduling Algorithms:
Minimize Seek Time:
Reduce the total movement of the read/write head to reach different track locations.
Reduce Average Response Time:
Ensure that requests are serviced as quickly as possible.
Increase Throughput:
Maximize the number of I/O requests handled per unit time.
Ensure Fairness:
Prevent starvation (no request should wait indefinitely).
Optimize System Performance:
Improve overall efficiency of the disk subsystem and CPU utilization.
Why SSTF (Shortest Seek Time First) is Not Practically Feasible:
SSTF selects the I/O request closest to the current head position, minimizing the next seek time.
Problems / Limitations:
Starvation (Unfairness):
Requests that are far from the current head position may never get serviced if closer requests keep arriving.
High Variability in Response Time:
Response time may vary greatly depending on request positions, causing unpredictable performance.
Complex Implementation:
Continuously recalculating the nearest request adds processing overhead.
Poor Performance Under Heavy Load:
When many requests are present, SSTF may repeatedly serve nearby tracks, ignoring others.
Q7: When is programmed I/O suitable than other I/O handling techniques? Explain the process of I/O handling using DMA.
Solution:
Programmed I/O (PIO) is an I/O technique where the CPU directly controls data transfer between an I/O device and memory.
The CPU continuously checks (polls) the device’s status to know whether it is ready for data transfer.
Situations Where Programmed I/O is Suitable:
Simple and Low-Speed Devices:
Ideal for devices like keyboards, mice, and simple sensors where data transfer rate is low.
Small Amount of Data Transfer:
Efficient for short, infrequent I/O operations that don’t require high-speed data movement.
No Need for Complex Hardware:
Suitable in systems where hardware simplicity and low cost are preferred over performance.
Real-Time or Embedded Systems:
Used where deterministic control by the CPU is needed, and interrupts or DMA add unnecessary complexity.
Limitations of Programmed I/O:
CPU remains busy waiting during the entire I/O operation.
Wastes CPU time and reduces system efficiency for large data transfer.
Process of I/O Handling Using DMA (Direct Memory Access)
DMA allows data to be transferred directly between I/O devices and memory without continuous CPU intervention.
The process is controlled by a DMA Controller (DMAC).
Steps in DMA I/O Handling:
Steps in DMA Operation:
DMA Request:
An I/O device (like a disk or network card) sends a DMA request (DRQ) signal to the DMA controller when it needs to transfer data.
CPU Grants Control:
The CPU temporarily suspends its control of the system bus and sends a DMA acknowledgment (DACK) signal to the DMA controller.
The CPU then enters an idle state or performs other tasks.
DMA Takes Over the Bus:
The DMA controller takes control of the address bus, data bus, and control bus.
It acts as a bus master for the duration of the data transfer.
Data Transfer:
The DMA controller transfers data directly between the I/O device and main memory.
The CPU is not involved in the actual transfer process.
Completion and Interrupt:
Once the transfer is complete, the DMA controller releases the system bus back to the CPU.
It then sends a DMA interrupt to notify the CPU that the data transfer is finished.
Example:
In disk-to-memory transfer, the OS instructs DMA to move a data block.
DMA performs the transfer automatically, and the CPU is free to execute other processes.
Q8: Suppose a disk has 201 cylinders, numbered from 0 to 200. At the same time the disk arm is at cylinder 95, and there is a queue of disk access requests for cylinders 82,170,43,140,24,16 and 190. Calculate the seek time for the disk scheduling algorithm FCFS, SSTF, SCAN and C-SCAN.
Solution:
Q9: Describe the working mechanism of DMA.
Solution:
Steps in DMA Operation:
DMA Request:
An I/O device (like a disk or network card) sends a DMA request (DRQ) signal to the DMA controller when it needs to transfer data.
CPU Grants Control:
The CPU temporarily suspends its control of the system bus and sends a DMA acknowledgment (DACK) signal to the DMA controller.
The CPU then enters an idle state or performs other tasks.
DMA Takes Over the Bus:
The DMA controller takes control of the address bus, data bus, and control bus.
It acts as a bus master for the duration of the data transfer.
Data Transfer:
The DMA controller transfers data directly between the I/O device and main memory.
The CPU is not involved in the actual transfer process.
Completion and Interrupt:
Once the transfer is complete, the DMA controller releases the system bus back to the CPU.
It then sends a DMA interrupt to notify the CPU that the data transfer is finished.
Q10: Write the structure and advantages of TLB.
Solution:
TLB (Translation Lookaside Buffer) is a special high-speed cache used in the memory management unit (MMU).
It stores the most recently used page table entries (PTEs) to speed up the virtual-to-physical address translation process.
It reduces the time required to access memory in systems using paging.
Structure of TLB:
Tag (Virtual Page Number – VPN):
Identifies which virtual page the entry corresponds to.
Frame Number (Physical Page Number – PPN):
The actual physical frame in memory where the page is stored.
Valid Bit:
Indicates whether the entry in the TLB is valid (1) or invalid (0).
Protection / Control Bits:
Store access rights such as read, write, or execute permissions.
Address Mapping:
Each TLB entry maps a virtual page to its corresponding physical frame.
Working of TLB:
When a CPU generates a virtual address, the MMU first checks the TLB.
If the page is found (TLB hit) → Physical address is obtained quickly.
If not found (TLB miss) → The page table in main memory is accessed, and the new mapping is loaded into the TLB.
Advantages of TLB:
Faster Address Translation:
Reduces the number of memory accesses needed for page table lookups.
Improved System Performance:
Speeds up instruction execution since address translation is faster.
Reduced Memory Access Time:
Avoids repeated access to the slower main memory for page table entries.
Efficient Use of CPU Time:
Minimizes CPU idle time caused by frequent memory translations.
Supports Virtual Memory Systems:
Makes paging and segmentation practical and efficient in modern operating systems.
Chapter 7: Linux Case Study
Q1: Explain Inter-Process Communication in Linux.
Solution:
Inter-Process Communication (IPC) is a mechanism that allows processes to exchange data and synchronize their actions in Linux.
Since processes in Linux run independently with separate memory spaces, IPC provides a way to share information and coordinate tasks among them.
IPC is essential for multi-processing, client-server communication, and parallel computing.
Types of Inter-Process Communication in Linux:
Pipes (|)
Used for unidirectional communication between related processes.
Example: ls | grep txt → Output of ls is input to grep.
Named Pipes (FIFOs)
Similar to pipes but can be used for communication between unrelated processes.
Created using the command mkfifo filename.
Message Queues
Allow processes to send and receive structured messages via a queue.
Support prioritized communication and are asynchronous.
Shared Memory
The fastest IPC mechanism.
Multiple processes share a common memory segment for direct data exchange.
Synchronization is handled using semaphores.
Semaphores
Used for synchronization between processes accessing shared resources.
Prevents race conditions by allowing controlled access.
Sockets
Enable communication between processes over a network (local or remote).
Used in client-server models, like web servers or chat applications.
Q2: Discuss the concept of SJF and SRTN scheduling algorithms with a suitable example.
Solution:
CPU Scheduling determines which process gets the CPU next when multiple processes are ready to execute.
Two popular CPU scheduling algorithms are Shortest Job First (SJF) and Shortest Remaining Time Next (SRTN).
Shortest Job First (SJF) Scheduling:
SJF is a non-preemptive scheduling algorithm.
The process with the smallest burst time (CPU time required) is selected next for execution.
It minimizes the average waiting time and turnaround time.
Advantage: Reduces average waiting time.
Disadvantage: Requires prior knowledge of burst time (not always possible).
Type: Non-preemptive.
Shortest Remaining Time Next (SRTN) Scheduling:
SRTN is the preemptive version of SJF.
The process with the shortest remaining burst time is always executed first.
If a new process arrives with a shorter burst time than the current one, CPU is preempted and assigned to the new process.
Advantage: Provides better average turnaround time than SJF.
Disadvantage: Frequent context switches increase overhead.
Type: Preemptive.
Q3: Write short notes on Linux Scheduling.
Solution:
Linux scheduling is the process of deciding which process will use the CPU next to ensure fairness and efficiency.
Purpose:
To share CPU time among processes, improve system performance, and ensure responsiveness.
Features:
Uses preemptive multitasking — higher priority process can interrupt a lower one.
Supports time-sharing — all processes get fair CPU time.
Maintains multiple queues for different process types (real-time, normal, idle).
Ensures efficient CPU utilization with minimum waiting time.
Types of Linux Schedulers:
O(1) Scheduler: Used in older Linux versions, made scheduling decisions in constant time.
Completely Fair Scheduler (CFS): Used in modern Linux; allocates CPU fairly based on each process’s virtual runtime (vruntime).
Scheduling Classes:
Real-Time Scheduling: Uses FIFO and Round Robin.
Normal Scheduling: Handled by CFS.
Idle Scheduling: Runs only when no other process is ready.
Conclusion:
The Linux scheduler ensures fairness, responsiveness, and efficient CPU utilization, with CFS as the default scheduler in modern kernels.
Q4: Write short notes on the Linux File System.
Solution:
The Linux File System is a method used by Linux to store, organize, and manage data on storage devices like hard drives or SSDs.
Structure:
It follows a hierarchical directory structure starting from the root (/) directory.
Important Directories:
/bin → Essential command binaries.
/etc → Configuration files.
/home → User home directories.
/var → Variable files like logs.
/tmp → Temporary files.
/dev → Device files.
File Types:
Regular files
Directories
Links
Device files
Pipes/Sockets
Key Features:
Case-sensitive file names.
File permissions for access control (read, write, execute).
Uses inodes to store metadata of files.
Supports mounting to connect devices to the main directory tree.
Common File Systems:
ext2, ext3, ext4 (standard Linux file systems).
XFS, Btrfs (advanced file systems for large storage).
Conclusion:
The Linux File System provides an efficient, secure, and hierarchical way to manage files, ensuring flexibility and performance.