Operating System -2018

---

Section-A (Very Short Answer Questions)

(Each question carries 3 marks)

---

1. What is an operating system? Discuss the various services of the OS.

What is an Operating System?

An Operating System (OS) is system software that manages hardware and software resources on a computer. It provides a user interface and acts as an intermediary between the user and the computer hardware.

Services of an OS:

1. Process Management:

   • Manages process execution, multitasking, process scheduling, and synchronization.

2. Memory Management:

   • Allocates and deallocates memory to processes. Ensures efficient utilization of memory and prevents memory leaks.

3. File System Management:

   • Provides a structured way to store, retrieve, and manage files on storage devices. Handles file creation, deletion, and access permissions.

4. Device Management:

   • Manages input/output devices using device drivers. Ensures smooth communication between hardware devices and software.

5. Security and Protection:

   • Protects data and resources from unauthorized access through user authentication and access control mechanisms.

6. Error Detection and Handling:

   • Monitors the system for errors and takes corrective actions to maintain system stability.

7. User Interface:

   • Provides interfaces such as command-line interfaces (CLI) or graphical user interfaces (GUI) for user interaction.

---

2. Difference between time-sharing system and real-time system.

Time-Sharing System:

1. Definition:

   • A system where multiple users can interact with the computer simultaneously by sharing system resources (e.g., CPU time).

2. Objective:

   • Maximizes resource utilization and ensures response times are fast but not guaranteed.

3. Example:

   • Unix/Linux multi-user systems.

4. Key Features:

   • Relies on time-slicing for process execution.
   • Non-critical response time requirements.

---

Real-Time System:

1. Definition:

   • A system designed to respond to events or inputs within a strict time limit.

2. Objective:

   • Ensures tasks are completed within predictable time frames.

3. Example:

   • Air traffic control systems, medical equipment.

4. Key Features:

   • Hard real-time systems have strict deadlines.
   • Soft real-time systems allow some flexibility in response time.

---

3. Difference between physical address and logical address.

Logical Address:

1. Definition:

   • The address generated by the CPU during program execution.

2. View:

   • A virtual address that the user/program sees.

3. Conversion:

   • Translated to a physical address by the Memory Management Unit (MMU).

---

Physical Address:

1. Definition:

   • The actual address in the physical memory (RAM).

2. View:

   • Invisible to the user and managed by the OS.

3. Direct Access:

   • Refers to the location in memory hardware.

---

4. Explain the demand paging and cache memory.

Demand Paging:

1. Definition:

   • A memory management technique where pages are loaded into memory only when they are needed during program execution.

2. Advantages:

   • Reduces memory wastage and improves performance for large applications.

3. Example:

   • Virtual memory systems.

---

Cache Memory:

1. Definition:

   • A high-speed memory located between the CPU and RAM that stores frequently accessed data.

2. Purpose:

   • Reduces the average time to access data from memory.

3. Benefits:

   • Speeds up data retrieval and improves system performance.

---

5. Explain the various attributes of a file.

Attributes of a File:

1. Name:

   • The human-readable identifier of a file.

2. Type:

   • Indicates the file format (e.g., .txt, .exe, .jpg).

3. Location:

   • Path to the file on the storage device.

4. Size:

   • The total amount of storage occupied by the file.

5. Permissions:

   • Specifies who can read, write, or execute the file.

6. Timestamps:

   • Information about file creation, modification, and last access.

7. Owner/Group:

   • Indicates who owns the file and the group it belongs to.

---

Section-B (Short Answer Questions)

(Each question carries 7½ marks)

---

6. Describe the critical section problem with a suitable example.

What is the Critical Section Problem?

• A critical section is a segment of code in which a process accesses shared resources like data or files. The critical section problem arises when multiple processes access shared resources simultaneously, leading to inconsistencies.

Conditions for Solution (Mutual Exclusion, Progress, Bounded Waiting):

1. Mutual Exclusion: Only one process can be in the critical section at a time.
2. Progress: If no process is in the critical section, others waiting must decide among themselves who enters next.
3. Bounded Waiting: A process must not wait indefinitely to enter its critical section.

Example:

• Consider two processes, P1 and P2, sharing a variable count:

  // Critical Section Example:
  count = count + 1;
  

• If both processes execute this line simultaneously, count may produce incorrect results due to a race condition.

Solutions:

1. Peterson’s Algorithm: A software-based solution ensuring mutual exclusion.
2. Semaphore: Using wait and signal operations to control access to critical sections.

Diagram or Pseudocode for Semaphore-Based Solution:

semaphore S = 1;

wait(S);
   // Critical Section
signal(S);

Question 7: Write the five UNIX and DOS commands with cross-reference and function.

Introduction

UNIX and DOS are two different operating systems with distinct command-line interfaces. Many commands in UNIX and DOS perform similar functions but have different syntax. Here's a detailed comparison of five important commands from both systems.

---

1. Display Files and Folders

• UNIX Command: ls

  • Function: Lists files and directories in the current directory.
  • Example:

    ls -l
    

    Displays detailed information, such as file permissions, owner, size, and modification date.

• DOS Command: dir

  • Function: Lists files and directories in the current directory.
  • Example:

    dir /p
    

    Displays directory contents one page at a time.

---

2. Copy Files

• UNIX Command: cp

  • Function: Copies a file from one location to another.
  • Example:

    cp source.txt destination.txt
    

    Copies source.txt to destination.txt.

• DOS Command: copy

  • Function: Copies a file from one location to another.
  • Example:

    copy source.txt destination.txt
    

    Copies source.txt to destination.txt.

---

3. Delete Files

• UNIX Command: rm

  • Function: Deletes files.
  • Example:

    rm file.txt
    

    Removes the file file.txt.

• DOS Command: del

  • Function: Deletes files.
  • Example:

    del file.txt
    

    Removes the file file.txt.

---

4. Rename Files

• UNIX Command: mv

  • Function: Renames or moves files.
  • Example:

    mv oldname.txt newname.txt
    

    Renames oldname.txt to newname.txt.

• DOS Command: rename

  • Function: Renames files.
  • Example:

    rename oldname.txt newname.txt
    

    Renames oldname.txt to newname.txt.

---

5. View File Contents

• UNIX Command: cat

  • Function: Displays the content of a file.
  • Example:

    cat file.txt
    

    Outputs the content of file.txt.

• DOS Command: type

  • Function: Displays the content of a file.
  • Example:

    type file.txt
    

    Outputs the content of file.txt.

---

Conclusion

The commands in UNIX and DOS share similar functionality but differ in syntax and additional options. UNIX commands generally provide more flexibility, while DOS commands are simpler but limited in functionality.

---

Question 8: Explain how memory can dynamically be allocated using first fit, best fit, and worst fit strategies.

Introduction

Dynamic memory allocation involves assigning memory blocks to processes at runtime. Three common strategies for allocating memory dynamically are First Fit, Best Fit, and Worst Fit.

---

1. First Fit Strategy

• Definition: Allocates the first available memory block that is large enough to fulfill the process's request.
• Steps:
  1. The memory blocks are searched sequentially.
  2. The first block large enough is allocated.
• Advantages:
  • Fast and simple.
  • Low overhead.
• Disadvantages:
  • Can lead to external fragmentation.
• Example: Memory Blocks: [100 KB, 500 KB, 200 KB, 300 KB]
  Process Request: 150 KB
  Allocation: Allocates the 200 KB block (first block large enough).

---

2. Best Fit Strategy

• Definition: Allocates the smallest available memory block that is sufficient to fulfill the process's request.
• Steps:
  1. Searches the entire memory list to find the block that fits the request most closely.
  2. Allocates the smallest block that meets the requirement.
• Advantages:
  • Reduces wasted memory within blocks.
• Disadvantages:
  • Slower than First Fit due to exhaustive search.
  • Can increase fragmentation.
• Example: Memory Blocks: [100 KB, 500 KB, 200 KB, 300 KB]
  Process Request: 150 KB
  Allocation: Allocates the 200 KB block (smallest sufficient block).

---

3. Worst Fit Strategy

• Definition: Allocates the largest available memory block to the process.
• Steps:
  1. Searches the entire memory list.
  2. Allocates the largest block to maximize the remaining space.
• Advantages:
  • Leaves large chunks of memory free for future processes.
• Disadvantages:
  • Results in wasted memory in large blocks.
• Example: Memory Blocks: [100 KB, 500 KB, 200 KB, 300 KB]
  Process Request: 150 KB
  Allocation: Allocates the 500 KB block (largest block).

---

Comparison of Strategies

Strategy	Efficiency	Fragmentation	Search Time
First Fit	Fast	High external fragmentation	Low
Best Fit	Moderate	Low external fragmentation	High
Worst Fit	Least efficient	High fragmentation	High

---

Section-C (Detailed Answer Questions)

(Each question carries 15 marks)

---

9. (a) What is page frame and page fault?

Page Frame:

• A page frame is a fixed-sized block of physical memory into which pages from virtual memory are loaded.
• Physical memory is divided into these page frames, and each frame has the same size as a page.

Page Fault:

• A page fault occurs when a program tries to access a page that is not currently in memory (i.e., it's on the disk).
• The OS handles page faults by:
  1. Suspending the process.
  2. Loading the required page from disk into a free frame.
  3. Resuming the process.

---

9. (b) Solve using FIFO and LRU algorithm and calculate page faults:

Page Reference String:
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
Number of Frames: 3

First In First Out (FIFO):

• Replace the oldest page in memory.
• Steps:
  • Start with empty frames.
  • Load pages one by one.
  • Replace pages in the order they were loaded.

Result:
Total Page Faults = 15

Least Recently Used (LRU):

• Replace the page that has not been used for the longest time.
• Steps:
  • Track page usage history.
  • Replace the least recently used page.

Result:
Total Page Faults = 12

---

10. Explain the performance criteria for scheduling algorithms.

Performance Criteria:

1. CPU Utilization:

   • Percentage of time the CPU is actively executing processes. Higher is better.

2. Throughput:

   • Number of processes completed per unit time.

3. Turnaround Time:

   • Time from process submission to its completion.

4. Waiting Time:

   • Total time a process spends waiting in the ready queue.

5. Response Time:

   • Time between process submission and its first response.

---

10 (b) Solve for SJF Preemptive and Non-Preemptive Scheduling:

Processes:

Process	Arrival Time	Burst Time
P1	0 ms	8 ms
P2	1 ms	4 ms
P3	2 ms	9 ms
P4	3 ms	5 ms

Preemptive SJF:

• Shortest job executes first; preempts if a shorter job arrives.

Non-Preemptive SJF:

• Shortest job executes first; completes execution before switching.

---

11. Define the following terms:

1. Fragmentation:

   • Wasted memory due to inefficient allocation.
   • Types:
     • Internal: Unused space within allocated memory blocks.
     • External: Free memory blocks scattered, making them unusable.

2. Paging:

   • A memory management scheme dividing memory into equal-sized pages.
   • Eliminates external fragmentation.

3. Process State:

   • The current status of a process (e.g., ready, running, waiting, terminated).

4. Segmentation:

   • Divides memory into variable-sized segments based on logical divisions (e.g., code, data).

5. Memory Management System:

   • Manages memory allocation, deallocation, and access permissions..

---

---

Q12: What is Deadlock? Explain Four Necessary Conditions for Deadlock to Occur with Examples. Describe the Different Methods for Prevention and Avoidance of Deadlocks.

Definition of Deadlock:

• A deadlock is a situation in a multi-process system where two or more processes are unable to proceed because each is waiting for the other to release a resource. It results in an indefinite wait, effectively halting system operation.

---

Four Necessary Conditions for Deadlock to Occur:

1. Mutual Exclusion:

   • At least one resource must be held in a non-shareable mode.
   • Example: A printer is being used by Process P1, and P2 also requires it. Only one process can use the printer at a time.

2. Hold and Wait:

   • A process holding at least one resource is waiting to acquire additional resources held by other processes.
   • Example: Process P1 holds a printer and requests a scanner held by P2. Meanwhile, P2 holds a scanner and requests the printer held by P1.

3. No Preemption:

   • Resources cannot be forcibly removed from a process holding them; they must be released voluntarily.
   • Example: A process holding a lock on a file cannot be interrupted to free the resource for another process.

4. Circular Wait:

   • A set of processes {P1, P2, ..., Pn} exists such that P1 is waiting for a resource held by P2, P2 is waiting for a resource held by P3, and so on, with Pn waiting for a resource held by P1.
   • Example: P1 → P2 → P3 → P1 (circular dependency).

---

Deadlock Prevention Methods:

To prevent deadlocks, at least one of the four necessary conditions must be eliminated:

1. Mutual Exclusion:

   • Make resources shareable whenever possible.
   • Example: Implement spooling for printers, allowing processes to queue print jobs.

2. Hold and Wait:

   • Ensure processes acquire all required resources simultaneously or none at all.
   • Example: Pre-allocate resources during process initialization.

3. No Preemption:

   • Allow resource preemption where feasible.
   • Example: If a process is holding a resource and another process needs it, suspend the first process and reallocate the resource.

4. Circular Wait:

   • Impose an ordering on resources and ensure processes request them in increasing order.
   • Example: Require that processes request CPU → memory → I/O in a specific sequence.

---

Deadlock Avoidance Methods:

1. Banker’s Algorithm:

   • Ensures that the system remains in a safe state by analyzing resource allocation before granting requests.

2. Resource Allocation Graph (RAG):

   • Represents processes and resources as nodes, with edges showing allocation and request relationships. Cycles in the graph indicate potential deadlocks.

---

---

Q13: Explain the Linked Allocation Method for Files. List the Merits and Drawbacks of This Method. How Does Indexed Allocation Solve the Problems of Linked Allocation?

Linked Allocation Method:

• Definition:
  • In the linked allocation method, a file is stored as a linked list of blocks, where each block contains:
    1. Data.
    2. A pointer to the next block.

---

How It Works:

1. File Structure:

   • The file starts at a specific block called the head block.
   • Each block contains the address (pointer) of the next block, forming a chain.

2. Accessing File Blocks:

   • To access the file, the system starts at the head block and follows the pointers sequentially.

---

Example:

Block	Content	Pointer
10	File Data (Block 1)	20
20	File Data (Block 2)	30
30	File Data (Block 3)	NULL

---

Merits of Linked Allocation:

1. No External Fragmentation:

   • Files occupy only as many blocks as they need, regardless of their size.

2. Dynamic File Size:

   • Files can grow or shrink easily by adding or removing blocks.

3. Efficient Use of Space:

   • Free blocks are utilized effectively.

---

Drawbacks of Linked Allocation:

1. Sequential Access Only:

   • Random access is inefficient, as all blocks must be accessed sequentially.

2. Pointer Overhead:

   • Each block reserves space for a pointer, reducing effective storage capacity.

3. Pointer Corruption:

   • If a pointer is corrupted, the file becomes inaccessible or partially readable.

---

Indexed Allocation (Solution to Drawbacks):

1. Definition:

   • Stores all pointers to the file's blocks in a separate index block, eliminating the need for pointers in each block.

2. How It Works:

   • The index block contains an array of block addresses.
   • Each file has a unique index block.

3. Advantages Over Linked Allocation:

   • Random Access: Files can be accessed directly by using the index block.
   • No Pointer Overhead: File blocks store only data.
   • Resilience: Corruption in one block doesn’t affect others.

---

Example of Indexed Allocation:

Index Block	Data Block
0	Block 10
1	Block 20
2	Block 30

To access the 2nd block, simply use the index (1).

---