Operating System 4th sem - 2019

 

Section-A 

---

1. Discuss virtual memory and its benefits.

Virtual Memory:
Virtual memory is a memory management technique where secondary storage (e.g., a hard disk) is used as if it were part of the main memory (RAM). This allows a system to run applications that require more memory than is physically available.

Benefits:

• Increased Efficiency: Allows more processes to run simultaneously by using disk space as an extension of RAM.
• Multitasking: Supports running multiple large applications without running out of memory.
• Isolation: Provides process isolation, preventing one process from interfering with another.
• Simplified Programming: Allows developers to write programs without worrying about physical memory constraints.

---

2. Explain directory structure.

Directory Structure:
A directory structure is a way of organizing files in a computer system. It enables users to store and retrieve files efficiently. There are several types of directory structures:

1. Single-Level Directory:

   • All files are stored in a single directory.
   • Simple but inefficient for large numbers of files.

2. Two-Level Directory:

   • Each user has their own directory.
   • Resolves issues of name collisions in the single-level directory.

3. Hierarchical/Tree-Structured Directory:

   • Directories are organized in a tree structure.
   • Supports subdirectories and is commonly used in modern systems.

4. Acyclic Graph Directory:

   • Allows directories to share files or subdirectories.
   • Useful for collaborative work.

5. General Graph Directory:

   • Can have cycles.
   • Needs additional mechanisms to handle loops.

---

3. What is Process Control Block (PCB)? Design a basic framework of PCB.

Process Control Block (PCB):
A PCB is a data structure used by the operating system to store information about a process. It acts as a repository for all data needed to manage a process.

Information in a PCB:

1. Process ID (PID): Unique identifier for the process.
2. Process State: Current state (ready, running, waiting, etc.).
3. Program Counter: Address of the next instruction to execute.
4. CPU Registers: Stores the CPU's current state for the process.
5. Memory Management Information: Includes page tables, base and limit registers.
6. I/O Status Information: List of I/O devices assigned to the process.
7. Priority: Process priority for scheduling.
8. Accounting Information: Tracks CPU usage, time limits, etc.

Basic Framework of PCB:

----------------------------
| Process ID               |
| Process State            |
| Program Counter          |
| CPU Registers            |
| Memory Management Info   |
| I/O Status Info          |
| Priority                 |
| Accounting Info          |
----------------------------

---

4. Differentiate multiprogramming and time-sharing operating systems.

Multiprogramming Operating System:

• Multiple programs are loaded into memory and executed concurrently.
• Goal: Maximize CPU utilization.
• Users do not directly interact with the system.
• Example: Batch systems.

Time-Sharing Operating System:

• Allows multiple users to interact with the computer simultaneously.
• Goal: Provide a quick response to user commands.
• Uses time slices to share CPU among users.
• Example: Unix, Linux.

Key Difference:
Time-sharing focuses on user interaction and quick responses, while multiprogramming focuses on CPU efficiency.

---

5. Name the different file access methods and describe them in brief.

File Access Methods:

1. Sequential Access:

   • Data is accessed in a sequential manner (one record after another).
   • Example: Reading a text file.

2. Direct Access:

   • Data can be accessed directly using its location or index.
   • Example: Accessing records in a database.

3. Indexed Access:

   • Uses an index table to locate specific records.
   • Example: Files with an index, like a book index.

4. Random Access:

   • Any part of the file can be accessed randomly without following a sequence.
   • Example: Multimedia files.

---

Section-B of the Operating Systems exam paper:

---

6. What is the Fragmentation Problem? Describe external and internal fragmentation.

Fragmentation Problem:
Fragmentation occurs when memory is allocated in a way that leaves unusable gaps. These gaps prevent efficient memory utilization and degrade system performance.

Types of Fragmentation:

1. Internal Fragmentation:

   • Occurs when a fixed-sized memory block is allocated, but the process does not use the entire block.
   • The unused portion inside the block is wasted.
   • Example: Allocating 8 KB for a 6 KB process leaves 2 KB wasted.

2. External Fragmentation:

   • Occurs when free memory is divided into small, scattered blocks that cannot accommodate processes.
   • Example: Even if 10 KB of total free memory exists, a 6 KB process may not fit if the memory is fragmented.

Solution to Fragmentation:

• Compaction: Combine scattered free spaces into a single large block (useful for external fragmentation).
• Paging/Segmentation: Divide memory into fixed or variable-size units, which can reduce both types of fragmentation.

---

7. Write the name of disk scheduling algorithms. Write the method and explain the working of any two algorithms.

Common Disk Scheduling Algorithms:

1. FCFS (First Come, First Serve)
2. SSTF (Shortest Seek Time First)
3. SCAN (Elevator Algorithm)
4. C-SCAN (Circular SCAN)
5. LOOK
6. C-LOOK

Explanation of Two Algorithms:

1. FCFS (First Come, First Serve):

   • Requests are processed in the order they arrive.
   • Advantages: Simple to implement.
   • Disadvantages: May result in high seek time for scattered requests.

   Example:
   Disk queue: [98, 183, 37, 122, 14, 124, 65, 67]
   Initial head position: 53
   Seek Sequence: 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67
   Total head movement = 640 cylinders.

2. SSTF (Shortest Seek Time First):

   • The request closest to the current head position is served next.
   • Advantages: Reduces total seek time.
   • Disadvantages: May cause starvation for far-off requests.

   Example:
   Disk queue: [98, 183, 37, 122, 14, 124, 65, 67]
   Initial head position: 53
   Seek Sequence: 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183
   Total head movement = 236 cylinders.

---

8. Consider the following reference string: 1, 2, 3, 4, 2, 6, 5, 1, 2, 7, 6, 3, 2, 1, 3, 6.

• Number of frames: 5
• Determine page faults using:
  • (i) LRU (Least Recently Used)
  • (ii) FIFO (First In, First Out)

Solution:

Assumptions:

• The memory initially has 5 empty frames.
• A page fault occurs when a required page is not in memory.
• When a page fault occurs, one page is replaced if the frames are full.

---

(i) LRU (Least Recently Used) Algorithm

Explanation:

• LRU replaces the page that has not been used for the longest time.
• The OS keeps track of the usage history of pages.

---

Step-by-Step Calculation:

1. Initial empty frames: []
2. Process the reference string and update the frames step by step:

Step	Reference String	Frames	Page Fault?
1	1	[1]	Yes
2	2	[1, 2]	Yes
3	3	[1, 2, 3]	Yes
4	4	[1, 2, 3, 4]	Yes
5	2	[1, 2, 3, 4]	No
6	6	[6, 2, 3, 4]	Yes
7	5	[6, 2, 5, 4]	Yes
8	1	[1, 2, 5, 4]	Yes
9	2	[1, 2, 5, 4]	No
10	7	[1, 2, 7, 4]	Yes
11	6	[1, 6, 7, 4]	Yes
12	3	[3, 6, 7, 4]	Yes
13	2	[3, 2, 7, 4]	Yes
14	1	[1, 2, 7, 4]	Yes
15	3	[3, 2, 1, 4]	Yes
16	6	[6, 2, 1, 3]	Yes

---

Total Page Faults (LRU): 12

---

(ii) FIFO (First In, First Out) Algorithm

Explanation:

• FIFO replaces the oldest page in memory.
• The OS maintains a queue to track the order of pages loaded into memory.

---

Step-by-Step Calculation:

1. Initial empty frames: []
2. Process the reference string and update the frames step by step:

Step	Reference String	Frames	Page Fault?
1	1	[1]	Yes
2	2	[1, 2]	Yes
3	3	[1, 2, 3]	Yes
4	4	[1, 2, 3, 4]	Yes
5	2	[1, 2, 3, 4]	No
6	6	[6, 2, 3, 4]	Yes
7	5	[6, 5, 3, 4]	Yes
8	1	[1, 5, 3, 4]	Yes
9	2	[2, 5, 3, 4]	Yes
10	7	[7, 5, 3, 4]	Yes
11	6	[6, 5, 3, 4]	Yes
12	3	[6, 5, 3, 4]	No
13	2	[2, 5, 3, 4]	Yes
14	1	[1, 5, 3, 4]	Yes
15	3	[1, 5, 3, 4]	No
16	6	[6, 5, 3, 4]	Yes

---

Total Page Faults (FIFO): 10

---

Section-C 

---

9. Write short notes on the following:

(a) File Allocation Methods

1. Contiguous Allocation:

   • Files are stored in contiguous blocks of memory.
   • Advantages: Simple and fast sequential access.
   • Disadvantages: External fragmentation and resizing difficulty.
     Example: A file requiring 5 blocks will occupy blocks 10-14 if the starting block is 10.

2. Linked Allocation:

   • Each file block contains a pointer to the next block.
   • Advantages: No external fragmentation and dynamic file resizing.
   • Disadvantages: Slower direct access due to pointer traversal.
     Example: Block 10 → Block 25 → Block 30 → End.

3. Indexed Allocation:

   • An index table contains pointers to all file blocks.
   • Advantages: Fast direct access.
   • Disadvantages: Overhead of maintaining the index table.
     Example: An index block points to file blocks 10, 25, 30, and 40.

---

(b) Swapping

• Swapping is a memory management technique where a process is temporarily moved from main memory to secondary storage (swap space) to free up memory.
• Advantages: Allows the system to run processes larger than available memory.
• Disadvantages: High disk I/O overhead.
  Example: If Process A is waiting for I/O, it is swapped to the disk, allowing Process B to use the memory.

---

(c) Disk Structure

• A disk is organized into tracks, sectors, and cylinders.
  Key components:
  • Platters: Circular disks for data storage.
  • Tracks: Concentric circles on the platter.
  • Sectors: Divisions of tracks containing fixed-sized data blocks.
    Example: Data retrieval involves finding the cylinder, track, and sector.

---

(d) Contiguous Memory Allocation

• This method allocates a single contiguous section of memory to a process.
• Advantages: Simple and fast access.
• Disadvantages: External fragmentation and difficulty resizing.
  Example: If a process requires 10 KB, a 10 KB free block is allocated.

---

(e) Threads

• A thread is the smallest unit of CPU execution.
• Types:
  • User-Level Threads: Managed by user-level libraries.
  • Kernel-Level Threads: Managed directly by the OS.
• Advantages: Faster context switching than processes.
• Example: A web browser uses multiple threads for rendering, user input, and network requests.

---

10. What is Deadlock? Explain four necessary conditions for deadlock and methods to prevent it.

Definition of Deadlock:

• A deadlock occurs when a set of processes are unable to proceed because each process is waiting for a resource held by another process.

Four Necessary Conditions for Deadlock (Coffman’s Conditions):

1. Mutual Exclusion: Only one process can use a resource at a time.
2. Hold and Wait: A process holding resources can request additional resources.
3. No Preemption: Resources cannot be forcibly taken from a process.
4. Circular Wait: A set of processes form a circular chain, each waiting for a resource held by the next.

Methods to Prevent Deadlock:

1. Avoid Circular Wait: Impose an ordering on resource allocation to avoid cycles.
2. Eliminate Hold and Wait: Require processes to request all resources at once.
3. Resource Preemption: Allow the OS to preempt resources from processes.
4. Mutual Exclusion Handling: Use spooling for sharable resources like printers.

Example of Deadlock Prevention:
The Banker’s Algorithm checks resource availability to ensure safe execution without causing deadlock.

---

11. What basic functions does an operating system perform as a resource manager?

Functions of an OS as a Resource Manager:

1. CPU Management:

   • Manages process scheduling to ensure efficient CPU usage.
   • Techniques: Round Robin, Priority Scheduling.

2. Memory Management:

   • Allocates and deallocates memory for processes.
   • Techniques: Paging, Segmentation.

3. Storage Management:

   • Organizes and controls access to files.
   • Techniques: File systems like NTFS, FAT32.

4. I/O Device Management:

   • Controls input/output devices using drivers.
   • Example: Printing a document.

5. Security and Protection:

   • Ensures safe access to system resources.
   • Techniques: User authentication, access control.

Disk Structure:

• To calculate total disk capacity:
  Formula:
  $\text{Capacity} = \text{Number of Cylinders} \times \text{Number of Tracks per Cylinder} \times \text{Number of Sectors per Track} \times \text{Bytes per Sector}$

---

12(a). Under what circumstances does a page fault occur?

A page fault occurs when a process attempts to access a page that is not currently loaded in main memory. This can happen under the following circumstances:

1. Page Not in Memory (First Access):

   • When a program references a page for the first time, it may not be in memory yet. This is common when loading new processes.
   • Example:
     • A program has a large dataset divided into multiple pages. When it accesses a new part of the dataset for the first time, the corresponding page may not yet be in memory.

2. Page Swapped Out:

   • When the main memory is full, pages may be swapped out to disk to make space for new pages. If the process needs a swapped-out page, a page fault occurs.
     Example:
     • In a paging system, the least recently used (LRU) page is swapped out, and the program suddenly requests that page again.

3. Invalid Page Access:

   • A process might try to access a page that is invalid (e.g., accessing memory outside its allocated range). This causes an exception, and the OS handles it appropriately.
     Example:
     • A program attempts to read beyond the allocated memory, leading to an invalid page fault.

---

12(b). Describe the actions taken by the operating system when a page fault occurs.

When a page fault occurs, the operating system takes the following steps to resolve it:

1. Interrupt Generation:

   • The CPU detects the page fault and generates a trap (an interrupt signal) to the operating system.

2. Determine Validity of the Access:

   • The OS checks whether the memory reference is valid:
     • If the reference is invalid (e.g., illegal memory access), the process is terminated.
     • If valid, the OS continues the fault handling process.

3. Locate the Page on Disk:

   • The OS determines the location of the required page in secondary storage (swap space or disk).

4. Allocate a Frame in Memory:

   • If memory is full, the OS selects a page to replace (based on a page replacement algorithm like FIFO or LRU).
   • The chosen page is swapped out to disk if it has been modified.

5. Load the Page into Memory:

   • The OS reads the required page from disk into the allocated frame in memory.

6. Update Page Table:

   • The page table is updated with the new frame number and the page is marked as "present" in memory.

7. Restart the Process:

   • The OS restarts the interrupted instruction, and the process continues execution as if the page fault never occurred.

Example:

• A process requests page 5, but it is not in memory. The OS loads the page from the disk into a free frame and updates the page table. The instruction is re-executed, and the process continues.

---

13. What are the different types of files? What are the tasks of the file management system?

Different Types of Files:

1. Text Files:

   • Contain human-readable characters.
   • Example: .txt, .log files.

2. Binary Files:

   • Contain machine-readable data.
   • Example: Executables (.exe), images (.jpg), and compiled programs.

3. Directory Files:

   • Special files that store information about other files.
   • Example: Folder structures in operating systems.

4. Special Files:

   • Used for input/output operations with devices like printers and terminals.
   • Example: /dev/null in UNIX.

5. Regular Files:

   • Standard data files containing user information.
   • Example: Database files (.db), documents (.docx).

6. Pipe Files:

   • Used for inter-process communication.
   • Example: Pipes in UNIX.

---

Tasks of the File Management System:

1. File Organization:

   • Organizes data into a structured format for efficient access.
   • Example: Hierarchical file structures like directories and subdirectories.

2. File Allocation:

   • Assigns space for files on disk.
   • Techniques: Contiguous allocation, linked allocation, indexed allocation.

3. Access Control:

   • Manages file permissions to ensure only authorized users can access or modify files.
   • Example: Read, write, execute permissions.

4. File Naming:

   • Provides a unique identifier (name) for each file.
   • Example: File extensions like .txt, .jpg.

5. Storage Management:

   • Keeps track of free and used space on the disk.
   • Allocates and deallocates storage efficiently.

6. File Backup and Recovery:

   • Ensures data protection against accidental deletion or corruption.
   • Example: Periodic backups and restore points.

---

File System Commands in UNIX:

1. Basic Commands:

   • ls: List directory contents.
   • cat: Display file content.
   • rm: Delete files.
   • mv: Move/rename files.

2. Permission Commands:

   • chmod: Change file permissions.
   • chown: Change file ownership.

---

Security in File Systems:

1. Authentication:

   • Verifies user identity before granting file access.

2. Encryption:

   • Protects data by converting it into unreadable formats for unauthorized users.

3. Access Control Lists (ACLs):

   • Define which users or groups have specific permissions for a file.

4. Data Integrity:

   • Ensures files are not tampered with during storage or transfer.
   • Example: Checksums and hashes.

---