Sarvast OS Notes

📘 UNIT I: Introduction & Memory Management

Operating System Basics

What is an Operating System?

An Operating System (OS) is a large collection of software that manages all the resources of a computer system, including memory, processor, file system, and input-output devices. It acts as an intermediary between users and computer hardware, providing an environment in which users can execute programs conveniently and efficiently.

Types of Operating Systems

1. Simple Batch Operating System:

In a simple batch operating system, users submit jobs to a computer operator, who then creates batches of jobs with similar requirements. These batches are executed sequentially without human intervention during processing. The system processes jobs one after another in the order they are received.

• Advantages: Reduces idle time of CPU, automatic job sequencing
• Disadvantages: No interaction with user during execution, slower processing compared to multiprogramming
• Examples: Early mainframe systems, payroll processing, bank statements

2. Multiprogrammed Batch Systems:

Multiprogramming OS allows multiple processes to execute simultaneously by monitoring their process states and switching between processes. The operating system loads several programs into memory and executes them concurrently to avoid CPU and memory underutilization. When one process is waiting for I/O, another process can use the CPU.

• Key Feature: Multiple programs in memory simultaneously
• Benefit: Better CPU utilization and faster processing
• Mechanism: Context switching between processes

3. Time-Sharing Systems:

Time-sharing is a form of multiprogrammed operating system that operates in interactive mode with quick response time. Multiple users can simultaneously share computer resources. The CPU time is divided into small time slices (quantum), and each user gets a turn to use the CPU. Users interact with the system through terminals, and the system provides immediate feedback.

• Features: Interactive, multiple users, short response time
• Time Slice: Each user gets small time quantum (10-100 milliseconds)
• Examples: UNIX, Linux, Windows Server

4. Personal Computer (PC) Systems:

PC operating systems are designed for single-user environments where one person uses the computer at a time. They provide a graphical user interface (GUI) and support multitasking, allowing multiple applications to run simultaneously.

• Characteristics: User-friendly, GUI-based, multitasking support
• Examples: Windows 10/11, macOS, Ubuntu Desktop

5. Parallel Systems:

Parallel operating systems are designed to speed up program execution by dividing programs into multiple segments that can run simultaneously on multiple processors. These systems use computer resources including single computers with multiple processors or several computers connected by a network.

• Architecture: Multiple CPUs, shared memory
• Types: Symmetric Multiprocessing (SMP), Asymmetric Multiprocessing
• Benefits: Increased throughput, fault tolerance

6. Distributed Systems:

In distributed systems, multiple autonomous computers communicate through a network to achieve a common goal. Each computer has its own processor and memory but appears as a single system to users.

• Features: Resource sharing, computation speedup, reliability
• Communication: Message passing, Remote Procedure Calls (RPC)
• Examples: Google's infrastructure, cloud computing platforms

7. Real-Time Systems:

Real-time operating systems execute programs with guaranteed upper bounds on task execution time. They are used where a large number of events (mostly external) must be accepted and processed within strict deadlines.

Hard Real-Time Systems:

• Strict timing guarantees - missing deadlines is not acceptable
• Deterministic and predictable response times
• High-priority tasks are always executed first
• Examples: Aircraft control systems, airbag deployment, medical monitoring devices
• Resource utilization is typically lower due to stringent requirements

Soft Real-Time Systems:

• Timing guarantees are not as strict - occasional deadline misses acceptable
• Response time varies based on system load
• Better resource utilization
• Examples: Multimedia streaming, online gaming, video conferencing
• More flexible and less costly to implement

Memory Management

Logical vs Physical Address

Address Translation: The Memory Management Unit (MMU) translates logical addresses to physical addresses using page tables or segment tables.

Swapping

Swapping is a memory management technique where a process can be temporarily moved from main memory to secondary storage (backing store) and then brought back to main memory for continued execution. This is done to free up memory for other processes.

Process of Swapping:

• Swap Out: Moving process from RAM to disk (backing store)
• Swap In: Moving process from disk back to RAM
• Context Switch: Saving process state before swapping out

When Swapping Occurs:

• When memory is full and a new process needs to be loaded
• In priority-based scheduling (swap out lower priority processes)
• In round-robin scheduling (swap after time quantum expires)

Backing Store: Fast disk large enough to accommodate copies of all memory images for all users. The system maintains a ready queue of processes on the backing store.

Contiguous Memory Allocation

In contiguous memory allocation, each process is allocated a single contiguous block of memory. The main memory is divided into two partitions: one for the operating system and one for user processes.

Allocation Strategies:

1. First Fit:

• Allocate the first available hole that is large enough
• Fast allocation
• May leave many small holes at beginning of memory

2. Best Fit:

• Allocate the smallest hole that is large enough
• Must search entire list unless ordered by size
• Produces smallest leftover holes
• Most efficient memory utilization

3. Worst Fit:

• Allocate the largest available hole
• Must also search entire list
• Produces largest leftover holes

Fragmentation

Internal Fragmentation:

Internal fragmentation occurs when memory allocated to a process is slightly larger than the requested memory, and the difference remains unused within the allocated partition. This happens in fixed-size partition allocation.

• Memory wasted inside allocated partitions
• Occurs in paging (last page may not be fully used)
• Solution: Use smaller page sizes (but increases page table size)

External Fragmentation:

External fragmentation occurs when there is enough total free memory to satisfy a request, but the available memory is not contiguous. Free memory is scattered in small blocks throughout memory.

• Free memory exists but is divided into many small non-contiguous blocks
• Occurs in variable-size partition allocation
• Solutions:
  • Compaction: Moving all processes to one end of memory, creating one large free block
  • Paging: Allows non-contiguous memory allocation
  • Segmentation with Paging: Combines benefits of both

Paging

Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory. It avoids external fragmentation and efficiently uses memory.

Key Concepts:

• Pages: Logical memory is divided into fixed-size blocks called pages (typically 4KB)
• Frames: Physical memory is divided into fixed-size blocks called frames (same size as pages)
• Page Table: Data structure that maps pages to frames, maintained by OS for each process
• Page Number: Index into page table
• Page Offset: Combined with frame base address to get physical address

Address Translation in Paging:

Logical Address = [Page Number | Page Offset]
Physical Address = [Frame Number | Page Offset]

Example:
Logical Address: 2054 (in decimal)
Page Size: 1024 bytes

Page Number = 2054 / 1024 = 2
Page Offset = 2054 % 1024 = 6

If Page 2 maps to Frame 5:
Physical Address = (5 × 1024) + 6 = 5126

Advantages of Paging:

• No external fragmentation
• Efficient memory utilization
• Easy to implement
• Allows non-contiguous memory allocation
• Protection through separate page tables

Disadvantages of Paging:

• Internal fragmentation in last page
• Page table consumes memory
• Increased access time (two memory accesses per instruction)
• Translation Lookaside Buffer (TLB) needed for performance

Segmentation

Segmentation is a memory management technique that divides a process into variable-sized logical segments based on the program structure. Each segment represents a logical unit such as main program, procedure, function, method, object, local variables, global variables, common block, stack, or symbol table.

Key Features:

• Variable-size segments (user-defined)
• Logical division of process
• Each segment has a name and length
• Segment table stores base address and limit of each segment

Segmentation vs Paging:

Virtual Memory

Concept of Virtual Memory

Virtual memory is a memory management technique that creates an illusion of a very large main memory by using secondary storage (disk) as an extension of RAM. It allows execution of processes that may not be completely loaded in the main memory.

Advantages of Virtual Memory:

• Large Address Space: Programs can be larger than physical memory
• Memory Protection: Each virtual address is translated to physical address through page table
• Efficient Use: Less I/O needed to load programs
• More Programs: More programs can run simultaneously
• Better CPU Utilization: Higher degree of multiprogramming
• Flexibility: Not all code needs to be in memory (error handlers, rarely used features)

Implementation Methods:

• Demand Paging: Most common method
• Demand Segmentation: Less commonly used

Demand Paging

Demand paging is a virtual memory implementation where pages are loaded into memory only when they are needed (demanded) during execution, not in advance. It is similar to a paging system with swapping.

How It Works:

• Process starts with no pages in memory
• When a page is referenced, if it's in memory, execution continues
• If page is not in memory, a page fault occurs
• OS loads the required page from disk to memory
• Page table is updated
• Instruction is restarted

Page Fault Handling:

1. Trap to OS (page fault interrupt)
2. Save user registers and process state
3. Determine if reference was valid
4. Find location of page on disk
5. Find free frame in memory
6. If no free frame, select victim page using page replacement algorithm
7. Read desired page from disk into free frame
8. Update page table
9. Restart instruction that caused page fault

Valid-Invalid Bit: Each page table entry has a bit to indicate if page is in memory (valid=1) or on disk (invalid=0).

Page Replacement Algorithms

When a page fault occurs and there are no free frames, a page must be replaced. The goal is to minimize page faults.

1. FIFO (First-In-First-Out):

The oldest page in memory is replaced. Simple to implement using a queue, but doesn't consider page usage patterns. Can suffer from Belady's Anomaly.

Belady's Anomaly: In FIFO, increasing the number of frames can sometimes increase the number of page faults (counterintuitive).

2. LRU (Least Recently Used):

Replaces the page that has not been used for the longest time. Based on the principle of locality - pages used recently are likely to be used again soon.

Implementation Methods:

• Counter: Each page has a timestamp, replace page with oldest timestamp
• Stack: Keep stack of page numbers, most recently used on top

3. Optimal Page Replacement:

Replaces the page that will not be used for the longest period of time in the future. This gives the lowest possible page fault rate but requires future knowledge, making it impractical to implement. Used as a benchmark to compare other algorithms.

4. Second Chance (Clock Algorithm):

An improvement on FIFO that gives pages a "second chance" before replacement. Uses a reference bit:

• If reference bit = 0, replace the page
• If reference bit = 1, give it a second chance (set bit to 0, move to next page)
• Circular queue implementation

Thrashing

Thrashing is a serious performance problem that occurs when a system spends more time paging (swapping pages in and out) than executing actual processes. The CPU utilization drops drastically.

Causes of Thrashing:

• Process allocated too few frames
• Degree of multiprogramming too high
• Too many processes competing for limited memory
• Each process keeps causing page faults
• CPU scheduler loads more processes thinking CPU is idle
• This creates a vicious cycle

Prevention Techniques:

• Working Set Model: Monitor the working set (actively used pages) of each process
• Page Fault Frequency: Monitor page fault rate, if too high, allocate more frames
• Decrease Multiprogramming: Swap out some processes
• Local Page Replacement: Each process replaces only its own pages

Working Set Model: The working set of a process is the set of pages it is currently using. The working set changes over time as the process moves from one locality to another.

❓ Unit I: Solved Questions

Reference String: 1, 2, 3, 4, 2, 1, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6

Frame 1: 1  1  1  1  1  1  6  6  6  6  6  7  7  7  7  1  1  1  1
Frame 2: -  2  2  2  2  2  2  2  2  2  2  2  6  6  6  6  6  6  6
Frame 3: -  -  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3
Frame 4: -  -  -  4  4  4  4  4  4  4  4  4  4  4  2  2  2  2  2
         PF PF PF PF H  H  PF H  H  H  PF PF PF H  PF PF H  H  H

PF = Page Fault, H = Hit

Total Page Faults (LRU) = 9

Reference String: 1, 2, 3, 4, 2, 1, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6

Frame 1: 1  1  1  1  1  1  1  1  1  1  1  7  7  7  7  1  1  1  1
Frame 2: -  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2
Frame 3: -  -  3  3  3  3  3  3  3  3  3  3  6  6  6  6  6  6  6
Frame 4: -  -  -  4  4  4  6  6  6  6  6  6  6  3  3  3  3  3  3
         PF PF PF PF H  H  PF H  H  H  H  PF H  PF H  PF H  H  H

Total Page Faults (Optimal) = 7

Process  Arrival Time  Burst Time
P1       0 ms          12 ms
P2       1 ms          15 ms
P3       2 ms          11 ms
P4       3 ms          21 ms
Time Quantum = 2 ms

Gantt Chart (with actual finish times):
0-2:P1  2-4:P2  4-6:P3  6-8:P1  8-10:P4  10-12:P2  12-14:P3  14-16:P1
16-18:P4  18-20:P2  20-22:P3  22-24:P1  24-26:P4  26-28:P2  28-30:P3
30-32:P1  32-34:P4  34-36:P2  36-38:P3  38-40:P1(f)
40-42:P4  42-44:P2  44-45:P3(f)  45-47:P4  47-49:P2  49-51:P4  51-52:P2(f)
52-54:P4  54-56:P4  56-58:P4  58-59:P4(f)

Completion Times:
P1: 40 ms,  P2: 52 ms,  P3: 45 ms,  P4: 59 ms

Turnaround Time (TAT) = Completion - Arrival
P1: 40 - 0 = 40 ms
P2: 52 - 1 = 51 ms
P3: 45 - 2 = 43 ms
P4: 59 - 3 = 56 ms

Waiting Time (WT) = TAT - Burst
P1: 40 - 12 = 28 ms
P2: 51 - 15 = 36 ms
P3: 43 - 11 = 32 ms
P4: 56 - 21 = 35 ms

Average Waiting Time = (28 + 36 + 32 + 35) / 4 = 131 / 4 = 32.75 ms
Average Turnaround Time = (40 + 51 + 43 + 56) / 4 = 190 / 4 = 47.5 ms

Q4. What is Thrashing? Explain causes and solutions

📘 UNIT II: Processes & CPU Scheduling

Process Concept

What is a Process?

A process is a program in execution. It is the basic unit of work in a modern operating system. When we write a computer program in a text file and execute it, it becomes a process that performs all the tasks mentioned in the program.

Process vs Program:

• Program: Passive entity stored on disk (executable file)
• Process: Active entity with program counter, registers, and resources
• One program can create multiple processes (e.g., opening multiple browser windows)

Process Memory Layout:

A process is divided into four sections when loaded into memory:

• Stack: Contains temporary data (function parameters, return addresses, local variables). Grows and shrinks dynamically during function calls.
• Heap: Dynamically allocated memory during process runtime (malloc, new). Grows upward.
• Data Section: Contains global and static variables. Initialized data (initialized global variables) and uninitialized data (BSS - Block Started by Symbol).
• Text Section: Contains the program code (machine instructions). Read-only, contains the compiled program code.

Process States

As a process executes, it changes between different states. A process can be in one of the following five states at any time:

Process State Transitions:

       NEW
        |
        ↓ (admitted)
      READY ←------------------+
        |                      |
        ↓ (scheduler dispatch)  |
      RUNNING                  |
        |  |                   |
        |  ↓ (I/O or event)    |
        |  WAITING ------------+ (I/O complete)
        ↓ (exit)
    TERMINATED

Process Control Block (PCB)

The Process Control Block (PCB), also called Task Control Block, is a data structure maintained by the OS for every process. It contains all information needed to manage the process.

Components of PCB:

• Process ID (PID): Unique identifier for the process (integer value)
• Process State: Current state (new, ready, running, waiting, terminated)
• Program Counter (PC): Address of the next instruction to be executed
• CPU Registers: Contents of all processor registers (accumulator, index registers, stack pointers, general-purpose registers)
• CPU Scheduling Information: Process priority, pointers to scheduling queues, scheduling parameters
• Memory Management Information: Base and limit registers, page tables, segment tables
• Accounting Information: CPU time used, time limits, process numbers, account numbers
• I/O Status Information: List of open files, list of I/O devices allocated to process
• Pointers: Pointer to parent process, pointers to child processes

PCB Operations:

• PCB is created when process is created
• Updated during process execution
• Used during context switching
• Deleted when process terminates
• All PCBs are kept in a memory area reserved for OS

Context Switching

Context switching is the mechanism where the CPU switches from one process to another. When this occurs, the system must save the state of the old process and load the saved state for the new process.

Context Switch Steps:

1. Save Context: Save PCB of currently running process (CPU registers, program counter, process state)
2. Update PCB: Update process state to ready or waiting
3. Move PCB: Move PCB to appropriate queue (ready queue or waiting queue)
4. Select New Process: Scheduler selects next process from ready queue
5. Load Context: Load PCB of new process (restore registers, program counter)
6. Resume Execution: Start executing new process

Context Switch Time:

• Pure overhead - no useful work done during switch
• Time dependent on hardware support
• Typical time: microseconds to milliseconds
• More registers = longer context switch time
• Some systems have special hardware to speed up context switching

Process Scheduling

Scheduling Queues

The OS maintains several queues to manage processes efficiently:

• Job Queue: Set of all processes in the system (both in memory and on disk)
• Ready Queue: Set of all processes in main memory, ready and waiting to execute. Typically a linked list with header containing pointers to first and last PCB.
• Device Queues: Set of processes waiting for a specific I/O device. Each device has its own queue.

Processes migrate among these various queues based on their state transitions.

Types of Schedulers

1. Long-Term Scheduler (Job Scheduler):

• Selects which processes should be brought into the ready queue from job pool
• Controls the degree of multiprogramming (number of processes in memory)
• Invoked infrequently (seconds, minutes) - can be slow
• Selects a good process mix of I/O-bound and CPU-bound processes
• Not present in time-sharing systems

2. Short-Term Scheduler (CPU Scheduler):

• Selects which process from ready queue should execute next on CPU
• Invoked very frequently (milliseconds) - must be fast
• Makes fine-grained decisions about which process runs next
• Can be preemptive or non-preemptive

3. Medium-Term Scheduler:

• Handles swapping - removes processes from memory to reduce multiprogramming
• Swaps out processes to disk and swaps them back in later
• Improves process mix or frees memory
• Can reintroduce process into memory later

Process vs CPU Bound

• I/O-Bound Process: Spends more time doing I/O than computations. Many short CPU bursts. Examples: text editors, database queries.
• CPU-Bound Process: Spends more time doing computations. Few very long CPU bursts. Examples: scientific calculations, video encoding.

A good process mix should include both types for optimal system performance.

CPU Scheduling Algorithms

Scheduling Criteria

Different CPU scheduling algorithms have different properties. To compare algorithms, we use several criteria:

• CPU Utilization: Keep CPU as busy as possible (0% to 100%). Goal: maximize.
• Throughput: Number of processes completed per time unit. Goal: maximize.
• Turnaround Time: Time from process submission to completion. Includes waiting time, execution time, I/O time. Goal: minimize.
• Waiting Time: Total time process spends waiting in ready queue. Goal: minimize.
• Response Time: Time from request submission until first response is produced. Important for interactive systems. Goal: minimize.

Important Formulas:

Turnaround Time = Completion Time - Arrival Time
Waiting Time = Turnaround Time - Burst Time
Response Time = Time of First CPU Allocation - Arrival Time

1. First-Come, First-Served (FCFS)

The simplest CPU scheduling algorithm. Processes are executed in the order they arrive in the ready queue. It is non-preemptive.

Characteristics:

• Easy to understand and implement
• Uses FIFO queue
• Non-preemptive
• Poor performance - high average waiting time
• Convoy effect: short processes wait for long process to complete

Convoy Effect: When a CPU-bound process gets CPU first, all I/O-bound processes must wait, leading to poor I/O device utilization.

2. Shortest Job First (SJF)

Associates each process with its next CPU burst length. When CPU is available, assign it to the process with smallest next CPU burst. If two processes have same burst time, FCFS is used to break the tie.

Two Variants:

• Non-Preemptive SJF: Once CPU given to process, it cannot be preempted until burst completes
• Preemptive SJF (SRTF - Shortest Remaining Time First): If new process arrives with shorter burst than remaining time of current process, preempt current process

Characteristics:

• Optimal - gives minimum average waiting time
• Difficulty: knowing the length of next CPU burst
• Can be estimated using exponential averaging of previous bursts
• Can cause starvation of long processes

3. Priority Scheduling

A priority is associated with each process. CPU is allocated to the process with highest priority. Equal-priority processes are scheduled in FCFS order.

Priority Assignment:

• Internally defined: time limits, memory requirements, number of open files
• Externally defined: importance of process, funds paid, political factors

Two Variants:

• Preemptive: New process with higher priority can preempt current process
• Non-Preemptive: Higher priority process waits in ready queue

Problem - Starvation: Low priority processes may never execute. Solution: Aging - gradually increase priority of processes that wait for long time.

4. Round Robin (RR)

Designed for time-sharing systems. Each process gets a small unit of CPU time (time quantum or time slice), usually 10-100 milliseconds. After time quantum expires, process is preempted and added to end of ready queue.

Characteristics:

• Preemptive version of FCFS
• Fair allocation of CPU
• Performance depends heavily on time quantum size
• No starvation
• Higher context switch overhead if quantum too small

Time Quantum Selection:

• Too large: Becomes FCFS
• Too small: Too many context switches, overhead increases
• Rule of thumb: 80% of CPU bursts should be shorter than quantum

Preemptive vs Non-Preemptive Scheduling

Process Synchronization

Critical Section Problem

A critical section is a segment of code where a process accesses shared resources (variables, files, etc.) that must not be accessed by more than one process at a time. The critical section problem is to design a protocol that processes can use to cooperate.

General Structure of Process:

do {
    // Entry Section
    // Request permission to enter critical section
    
    // CRITICAL SECTION
    // Access shared resources
    
    // Exit Section  
    // Release critical section
    
    // Remainder Section
    // Other code
} while (true);

Requirements for Solution:

1. Mutual Exclusion:
   • Only one process can be in critical section at a time
   • If process Pi is executing in critical section, no other process can execute in critical section
2. Progress:
   • If no process is in critical section and some processes want to enter, only those processes not in remainder section can participate in decision
   • Selection of next process cannot be postponed indefinitely
   • Deadlock-free
3. Bounded Waiting:
   • There must exist a bound on number of times other processes can enter critical section after a process has requested entry
   • Ensures no starvation
   • Every process gets a turn eventually

Semaphores

A semaphore is an integer variable that provides a sophisticated way to synchronize processes. It can only be accessed through two atomic operations:

Operations:

wait(S) {        // Also called P() or down()
    while (S <= 0)
        ; // busy wait
    S--;
}

signal(S) {      // Also called V() or up()
    S++;
}

Types of Semaphores:

1. Binary Semaphore (Mutex):

• Value can be 0 or 1 only
• Used for mutual exclusion
• Initialized to 1
• Also called mutex lock

// Using binary semaphore for mutual exclusion
Semaphore mutex = 1;

Process Pi:
    wait(mutex);
        // Critical Section
    signal(mutex);

2. Counting Semaphore:

• Value can range over unrestricted domain
• Used to control access to resource with multiple instances
• Initialized to number of available resources

// Example: 5 printers available
Semaphore printers = 5;

Process Pi:
    wait(printers);  // Get a printer
        // Use printer
    signal(printers); // Release printer

Classical Synchronization Problems

1. Producer-Consumer Problem (Bounded Buffer):

Producer process produces information consumed by consumer process. They share a fixed-size buffer.

• Producer must not add item when buffer is full
• Consumer must not remove item when buffer is empty
• They must not access buffer simultaneously

Semaphore mutex = 1;      // Binary semaphore for mutual exclusion
Semaphore empty = n;      // Count of empty slots
Semaphore full = 0;       // Count of full slots

Producer:
    while (true) {
        // Produce item
        wait(empty);      // Wait for empty slot
        wait(mutex);      // Enter critical section
            // Add item to buffer
        signal(mutex);    // Exit critical section
        signal(full);     // Increment full count
    }

Consumer:
    while (true) {
        wait(full);       // Wait for full slot
        wait(mutex);      // Enter critical section
            // Remove item from buffer
        signal(mutex);    // Exit critical section
        signal(empty);    // Increment empty count
        // Consume item
    }

2. Dining Philosophers Problem:

5 philosophers sit at circular table with 5 chopsticks (one between each pair). Each philosopher thinks and occasionally gets hungry. To eat, philosopher needs both chopsticks.

Problem: Prevent deadlock and starvation while allowing maximum concurrency.

Simple (but flawed) solution:

Semaphore chopstick[5] = {1, 1, 1, 1, 1};

Philosopher i:
    while (true) {
        think();
        wait(chopstick[i]);
        wait(chopstick[(i+1) % 5]);
        eat();
        signal(chopstick[i]);
        signal(chopstick[(i+1) % 5]);
    }
// Problem: Deadlock if all pick up left chopstick simultaneously

Solutions to prevent deadlock:

• Allow at most 4 philosophers at table simultaneously
• Pick up chopsticks only if both are available (atomic operation)
• Odd philosophers pick left first, even pick right first

❓ Unit II: Solved Questions

           +---------+
           |   NEW   |  ← Process is being created
           +---------+
                |
                | (admitted)
                ↓
           +---------+
      +--->|  READY  |<---+  ← Process waiting for CPU
      |    +---------+    |
      |         |         |
      |         | (scheduler dispatch)
      |         ↓         |
      |    +---------+    |
      |    | RUNNING |----+  ← Process executing on CPU
      |    +---------+    |
      |         |         |
      |         | (interrupt)
      |         ↓         |
      |    +---------+    |
      +----|  WAIT/  |----+  ← Waiting for I/O or event
           | BLOCKED |
           +---------+
                |
                | (exit)
                ↓
           +---------+
           |TERMINATED| ← Process has finished
           +---------+

Process  Arrival Time  Burst Time
P1       0            24
P2       1            3
P3       2            3

Gantt Chart:
P1          | P2  | P3  |
0          24  27  30

Waiting Time:
P1 = 0 - 0 = 0
P2 = 24 - 1 = 23
P3 = 27 - 2 = 25

Average Waiting Time = (0 + 23 + 25) / 3 = 16 ms

Order: P2 (3), P3 (3), P1 (24)

Gantt Chart:
P2  | P3  | P1                    |
0   3   6                        30

Waiting Time:
P2 = 0 - 1 = -1 (arrived at 1, started at 0, so we adjust)
Actually: P2 waits from 1 to 3 = 2
P3 = 3 - 2 = 1  
P1 = 6 - 0 = 6

Wait calculation with arrivals:
P1: 6 - 0 = 6
P2: 0 - 1 = 0 (started immediately after arrival adjust)
P3: 3 - 2 = 1

Average WT = (6 + 2 + 1) / 3 = 3 ms

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

Timeline:
0-1: P1 runs (remaining: 7)
1: P2 arrives (4 < 7), preempts P1
1-5: P2 runs to completion
5: P4 has shortest remaining (5), runs
5-10: P4 runs to completion
10: P1 resumes (remaining: 7)
10-17: P1 runs to completion
17-26: P3 runs to completion

Process  Burst  Priority
P1       10     3
P2       1      1  (highest)
P3       2      4
P4       1      5
P5       5      2

Order: P2, P5, P1, P3, P4

Problem: Starvation of low priority processes
Solution: Aging - increase priority over time

Process  Burst
P1       24
P2       3
P3       3

Gantt Chart:
P1 |P2 |P3 |P1 |P1 |P1 |P1 |P1 |P1 |
0  4  7  10 14 18 22 26 30

P1: 4, 10-14, 14-18, 18-22, 22-26, 26-30
P2: 4-7 (completes)
P3: 7-10 (completes)

Good for time-sharing, fair to all processes

Q3. Calculate Average Waiting Time using SRTF (Shortest Remaining Time First)

Process  Arrival Time  Burst Time
P1       0            2
P2       1            5
P3       2            1
P4       3            2
P5       3            3
P6       6            6

Time 0: P1 arrives (BT=2), execute P1
Time 1: P2 arrives (BT=5), P1 has 1 left, continue P1
Time 2: P1 completes, P3 arrives (BT=1)
        Compare: P2(5), P3(1) → Execute P3
Time 3: P3 completes, P4(BT=2), P5(BT=3) arrive
        Compare: P2(5), P4(2), P5(3) → Execute P4
Time 5: P4 completes
        Compare: P2(5), P5(3) → Execute P5
Time 8: P5 completes, P2(5) remaining, P6(6) arrived at 6
        Execute P2
Time 11: (Actually time 8+3=11 for P2 to complete)

Detailed Timeline:
0-2: P1 executes (completes at 2)
2-3: P3 executes (completes at 3)
3-5: P4 executes (completes at 5)  
5-8: P5 executes (completes at 8)
8-13: P2 executes (actually time 8, remaining 5, so 8 to 13)
But P6 arrived at 6, with BT=6

Let me recalculate:
Time 5: P4 done, compare P5(3), P2(5) → P5
Time 6: P6 arrives(6), P5 has 2 left, P2 has 5
       Compare: P5(2), P2(5), P6(6) → continue P5
Time 8: P5 done, compare P2(5), P6(6) → P2
Time 13: P2 done, P6 executes
Time 19: P6 done

Waiting Times:
P1: 0 (started immediately)
P2: Waited from 1 to 8 = 7 - 5 (BT) = 2? 
    Actually: (13-1) - 5 = 7
P3: (2-2) = 0
P4: (3-3) = 0  
P5: (5-3) = 2
P6: (13-6) - 6 + 6 = 7

Correct Calculation:
Wait Time = (Completion - Arrival) - Burst

P1: (2-0)-2 = 0
P2: (13-1)-5 = 7
P3: (3-2)-1 = 0
P4: (5-3)-2 = 0
P5: (8-3)-3 = 2
P6: (19-6)-6 = 7 (arrived 6, started 13, wait=7)

Actually simpler: Started-
Arrival-Burst

Waiting Time = Start Time - Arrival Time
P1: 0-0 = 0
P2: 8-1 = 7  
P3: 2-2 = 0
P4: 3-3 = 0
P5: 5-3 = 2
P6: 13-6 = 7

Average Waiting Time = (0+7+0+0+2+7)/6 = 16/6 = 2.67 ms

📘 UNIT III: Deadlocks

Introduction to Deadlocks

What is a Deadlock?

A deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process. None of the processes can proceed because they are all waiting for resources held by other processes in the set.

Real-World Analogy: Imagine a narrow bridge where two cars approach from opposite directions. Each car occupies half the bridge and waits for the other to back up. Neither can proceed, creating a deadlock.

Simple Example:

Process P1:
    1. Acquire Resource R1
    2. Acquire Resource R2
    3. Release R2
    4. Release R1

Process P2:
    1. Acquire Resource R2
    2. Acquire Resource R1
    3. Release R1
    4. Release R2

If P1 acquires R1 and P2 acquires R2 simultaneously,
both will wait forever for the other resource → DEADLOCK

System Model

A system consists of a finite number of resources distributed among competing processes. Resources are categorized into different types:

• Resource Types: R1, R2, ..., Rm (CPU cycles, memory space, I/O devices, files)
• Resource Instances: Each type Ri has Wi instances
• Example: If system has 2 CPUs, then CPU is resource type with 2 instances

Resource Utilization Pattern:

1. Request: Process requests resource (if unavailable, process waits)
2. Use: Process uses the resource (performs operation)
3. Release: Process releases the resource (becomes available for others)

Deadlock Characterization

Necessary Conditions for Deadlock (Coffman Conditions)

Deadlock can arise if and only if all four of the following conditions hold simultaneously in a system:

1. Mutual Exclusion:

• At least one resource must be held in non-sharable mode
• Only one process can use the resource at a time
• If another process requests the resource, it must wait
• Example: Printer - only one process can print at a time

2. Hold and Wait:

• A process must be holding at least one resource
• AND waiting to acquire additional resources held by other processes
• Process doesn't release resources it already holds while waiting
• Example: Process holds file A, waiting for file B held by another process

3. No Preemption:

• Resources cannot be forcibly taken away from a process
• Resources can only be released voluntarily by the process holding them
• After the process has completed its task
• Example: Cannot forcibly take printer from a process that's printing

4. Circular Wait:

• A set of processes {P0, P1, ..., Pn} exists such that:
• P0 is waiting for resource held by P1
• P1 is waiting for resource held by P2
• ...
• Pn-1 is waiting for resource held by Pn
• Pn is waiting for resource held by P0
• Forms a circular chain of waiting processes

Important Note: If ANY ONE of these four conditions does not hold, deadlock cannot occur. All four must be present simultaneously.

Resource Allocation Graph (RAG)

A Resource Allocation Graph is a directed graph used to represent the state of a system in terms of processes and resources. It helps in detecting deadlocks.

Components:

• Vertices (Nodes):
  • Process nodes: Represented by circles (P1, P2, ...)
  • Resource nodes: Represented by rectangles (R1, R2, ...)
  • Dots inside rectangles represent instances of that resource
• Edges (Arrows):
  • Request Edge: Pi → Rj (process Pi requesting resource Rj)
  • Assignment Edge: Rj → Pi (resource Rj allocated to process Pi)

Deadlock Detection using RAG:

• If graph contains no cycles: No deadlock
• If graph contains a cycle:
  • If only one instance per resource type → Deadlock exists
  • If multiple instances per resource type → Deadlock may exist (need further analysis)

Example RAG (Deadlock scenario):

P1 --requests--> R1
 ↑               |
 |          allocated to
 |               |
R2 <--requests-- P2
 |
allocated to
 |
 ↓
P1

This forms a cycle: P1 → R1 → P2 → R2 → P1 (DEADLOCK!)

Methods for Handling Deadlocks

There are four main approaches to deal with deadlock problems:

Deadlock Prevention

Prevention ensures that at least one of the four necessary conditions cannot hold, thus making deadlock impossible.

Breaking Each Condition:

1. Breaking Mutual Exclusion:

• Make resources sharable when possible
• Problem: Some resources inherently cannot be shared (printers, tape drives)
• Example Solution: Read-only files can be shared, use spooling for printers
• Limitation: Not applicable to all resource types

2. Breaking Hold and Wait:

• Protocol 1: Process must request all resources at once before execution
  • Grant resources only if all available
  • Disadvantage: Low resource utilization, starvation possible
• Protocol 2: Process can request resources only when it has none
  • Must release all currently held resources before requesting new ones
  • Disadvantage: May need to release and re-acquire same resources

3. Breaking No Preemption:

• If a process requests a resource that cannot be immediately allocated:
  • Release all resources currently held
  • Process restarts only when it can acquire all needed resources
• Alternative: Preempt resources from waiting processes
  • Give to requesting process
  • Preempted process added to waiting list
• Applicable to: Resources whose state can be saved and restored (CPU registers, memory)
• Not applicable to: Printers, tape drives (state cannot be easily saved)

4. Breaking Circular Wait:

• Impose total ordering on all resource types
• Assign unique number to each resource: F(R1) = 1, F(R2) = 2, ..., F(Rn) = n
• Rule: Process can request resources only in increasing order of enumeration
  • Process requests Ri, then can only request Rj if F(Rj) > F(Ri)
• Alternative: If process needs Ri, must release all Rj where F(Rj) >= F(Ri)
• Proof: Cannot form circular chain if resources requested in order

Example of Breaking Circular Wait:
Resource Ordering: F(R1)=1, F(R2)=2, F(R3)=3

Process P1:
    Request R1 (F=1) ✓
    Request R2 (F=2) ✓ (2 > 1)
    Request R3 (F=3) ✓ (3 > 2)

Process P2:
    Request R2 (F=2) ✓
    Request R1 (F=1) ✗ NOT ALLOWED (1 < 2)
    Must release R2 first before requesting R1

Deadlock Avoidance

Avoidance requires that the system has additional a priori information about which resources a process will request and use during its lifetime. The system decides for each request whether or not the process should wait to avoid potential deadlock.

Safe State

A state is safe if the system can allocate resources to each process (up to its maximum) in some order and still avoid deadlock. A safe sequence of processes exists.

Safe Sequence: A sequence is safe if for each Pi, the resources that Pi can still request can be satisfied by:

• Currently available resources, PLUS
• Resources held by all Pj where j < i

Key Concepts:

• Safe State: At least one safe sequence exists → No deadlock possible
• Unsafe State: No safe sequence exists → Deadlock may occur (but not guaranteed)
• Deadlock State: Subset of unsafe state → Deadlock has occurred

State Diagram:
[Safe State] → [Unsafe State] → [Deadlock State]
     ↓
  No deadlock        May lead to       Deadlock
  guaranteed         deadlock          exists

Banker's Algorithm

The Banker's Algorithm is a deadlock avoidance algorithm developed by Edsger Dijkstra. It tests for safety by simulating allocation for predetermined maximum possible amounts of all resources, then makes a "safe state" check to test for possible deadlock activities.

Data Structures (n processes, m resource types):

• Available[m]: Number of available instances of each resource type
  • Available[j] = k means k instances of resource Rj are available
• Max[n][m]: Maximum demand of each process
  • Max[i][j] = k means process Pi may request at most k instances of Rj
• Allocation[n][m]: Currently allocated resources
  • Allocation[i][j] = k means Pi is currently allocated k instances of Rj
• Need[n][m]: Remaining resource need
  • Need[i][j] = Max[i][j] - Allocation[i][j]

Safety Algorithm:

1. Initialize:
   Work = Available (working copy of available resources)
   Finish[i] = false for all i (all processes unfinished)

2. Find an index i such that:
   a) Finish[i] == false (process not finished)
   b) Need[i] <= Work (process needs can be satisfied)
   
   If no such i exists, go to step 4

3. Simulate execution:
   Work = Work + Allocation[i]  (process finishes, releases resources)
   Finish[i] = true
   Go to step 2

4. If Finish[i] == true for all i:
      System is in SAFE state
   Else:
      System is in UNSAFE state

Resource Request Algorithm:

When process Pi requests resources (Request[i]):

1. If Request[i] <= Need[i]:
      Go to step 2
   Else:
      Error (process exceeded maximum claim)

2. If Request[i] <= Available:
      Go to step 3
   Else:
      Pi must wait (resources not available)

3. Pretend to allocate (tentative allocation):
   Available = Available - Request[i]
   Allocation[i] = Allocation[i] + Request[i]
   Need[i] = Need[i] - Request[i]

4. Run Safety Algorithm:
   If SAFE state:
      Grant request (make allocation permanent)
   Else:
      Deny request (restore old state, Pi waits)

Deadlock Detection

If a system does not employ deadlock prevention or avoidance, deadlocks may occur. The system must provide:

• An algorithm to examine the state and determine if deadlock has occurred
• An algorithm to recover from deadlock

Detection Algorithm

For Single Instance Resources:

• Use Resource Allocation Graph (RAG)
• If cycle exists → Deadlock exists
• Can use cycle detection algorithms (DFS-based)
• Time complexity: O(n²) where n is number of processes

For Multiple Instance Resources:

Use algorithm similar to Banker's but without Need matrix (don't need maximum requirements):

Data Structures:
- Available[m]: Available instances of each resource
- Allocation[n][m]: Currently allocated resources
- Request[n][m]: Current request of each process

Detection Algorithm:
1. Initialize:
   Work = Available
   Finish[i] = false if Allocation[i] != 0
   Finish[i] = true if Allocation[i] == 0

2. Find i such that:
   Finish[i] == false AND Request[i] <= Work
   If no such i, go to step 4

3. Work = Work + Allocation[i]
   Finish[i] = true
   Go to step 2

4. If Finish[i] == false for some i:
      Deadlock exists (those processes are deadlocked)
   Else:
      No deadlock

When to Invoke Detection?

• Every time a request cannot be granted: High overhead but quick detection
• At regular intervals: Balance between overhead and detection delay
• When CPU utilization drops below threshold: May indicate deadlock

Deadlock Recovery

Once deadlock is detected, several options exist for breaking it:

1. Process Termination

Option A: Abort all deadlocked processes

• Simple and guaranteed to break deadlock
• High cost - all processes lose their work
• Must restart processes from beginning

Option B: Abort one process at a time until deadlock cycle is eliminated

• After each abort, run detection algorithm to check if deadlock broken
• Overhead of repeated detection
• Selection criteria for victim process:
  • Priority of the process
  • How long process has computed and how much longer to completion
  • Resources the process has used and needs
  • How many processes will need to be terminated
  • Is process interactive or batch?

2. Resource Preemption

Successively preempt resources from processes and give them to other processes until deadlock cycle is broken.

Issues to Consider:

a) Selecting a Victim:

• Which resources and processes to preempt?
• Minimize cost (CPU time used, number of resources held, etc.)

b) Rollback:

• Return process to some safe state, restart from that state
• Total Rollback: Abort process, restart from beginning (simple but loses all work)
• Partial Rollback: Rollback only as far as necessary (requires checkpoints)

c) Starvation:

• Same process may always be picked as victim
• Solution: Include number of rollbacks in cost factor (limit number of times same process can be victim)

Combined Approach

Real systems often combine approaches:

• Partition resources into hierarchical ordered categories
• Use most appropriate technique for each category
• Example:
  • Internal resources (PCB, page tables): Prevention via ordering
  • Main memory: Prevention via preemption
  • Job resources (files, databases): Avoidance
  • Swappable space: Pre-allocation

❓ Unit III: Solved Questions

Three processes and three resources:

P1 holds R1, wants R2
P2 holds R2, wants R3  
P3 holds R3, wants R1

Circular chain: P1 → R2 (held by P2) → R3 (held by P3) → R1 (held by P1)

This forms a cycle: P1 → P2 → P3 → P1

Total Resources in System: A=10, B=5, C=7

Current State:
           Allocation      Max         Available
           A   B   C     A   B   C     A  B  C
    P0     0   1   0     7   5   3     3  3  2
    P1     2   0   0     3   2   2
    P2     3   0   2     9   0   2
    P3     2   1   1     2   2   2
    P4     0   0   2     4   3   3

Step-by-Step Solution:

Step 1: Calculate Need Matrix
Need = Max - Allocation

           Need
           A   B   C
    P0     7   4   3     (7-0, 5-1, 3-0)
    P1     1   2   2     (3-2, 2-0, 2-0)
    P2     6   0   0     (9-3, 0-0, 2-2)
    P3     0   1   1     (2-2, 2-1, 2-1)
    P4     4   3   1     (4-0, 3-0, 3-2)

Step 2: Apply Safety Algorithm
Available = [3, 3, 2]

Iteration 1: Find a process whose Need <= Available
- P0: Need[7,4,3] > Available[3,3,2] ✗
- P1: Need[1,2,2] <= Available[3,3,2] ✓ CAN COMPLETE

Execute P1:
- P1 finishes and releases resources
- Available = Available + Allocation[P1]
- Available = [3,3,2] + [2,0,0] = [5,3,2]
- Mark P1 as finished

Iteration 2: Available = [5,3,2]
- P0: Need[7,4,3] > Available[5,3,2] ✗
- P2: Need[6,0,0] > Available[5,3,2] ✗
- P3: Need[0,1,1] <= Available[5,3,2] ✓ CAN COMPLETE

Execute P3:
- Available = [5,3,2] + [2,1,1] = [7,4,3]
- Mark P3 as finished

Iteration 3: Available = [7,4,3]
- P0: Need[7,4,3] <= Available[7,4,3] ✓ CAN COMPLETE

Execute P0:
- Available = [7,4,3] + [0,1,0] = [7,5,3]
- Mark P0 as finished

Iteration 4: Available = [7,5,3]
- P2: Need[6,0,0] <= Available[7,5,3] ✓ CAN COMPLETE

Execute P2:
- Available = [7,5,3] + [3,0,2] = [10,5,5]
- Mark P2 as finished

Iteration 5: Available = [10,5,5]
- P4: Need[4,3,1] <= Available[10,5,5] ✓ CAN COMPLETE

Execute P4:
- Available = [10,5,5] + [0,0,2] = [10,5,7]
- Mark P4 as finished

All processes finished successfully!

Safe Sequence: 

CONCLUSION: System is in SAFE STATE
Deadlock will NOT occur.

Current Request from P1: Request[1, 0, 2]

Check 1: Request <= Need?
Request[1,0,2] <= Need[1,2,2]? YES ✓

Check 2: Request <= Available?
Request[1,0,2] <= Available[3,3,2]? YES ✓

Simulate allocation:
New Available = [3,3,2] - [1,0,2] = [2,3,0]
New Allocation[P1] = [2,0,0] + [1,0,2] = [3,0,2]
New Need[P1] = [1,2,2] - [1,0,2] = [0,2,0]

Run Safety Algorithm with new state:
Available = [2,3,0]

Try to find safe sequence:
- P0: Need[7,4,3] > Available[2,3,0] ✗
- P1: Need[0,2,0] <= Available[2,3,0] ✓
- P2: Need[6,0,0] > Available[2,3,0] ✗
- P3: Need[0,1,1] > Available[2,3,0] ✗ (C insufficient)
- P4: Need[4,3,1] > Available[2,3,0] ✗

Only P1 can proceed, but after P1:
Available = [2,3,0] + [3,0,2] = [5,3,2]

Now check remaining:
- P3: Need[0,1,1] <= [5,3,2] ✓
Continue...

If safe sequence found: GRANT REQUEST
If no safe sequence: DENY REQUEST (rollback to previous state)

Q3. Differentiate between Deadlock Prevention and Deadlock Avoidance

📘 UNIT IV: Device Management

Device Management Overview

What is Device Management?

Device management is one of the crucial functions of an operating system. It involves managing all I/O devices connected to the computer system, including their allocation, deallocation, and efficient utilization. The OS controls the way data is transferred between devices and processes, handles device interrupts, and provides a uniform interface for device access.

Device Management Techniques

1. Dedicated Devices

A dedicated device is assigned to one process for its entire duration until the process releases it. No other process can use the device during this time.

Characteristics:

• Allocated to a single process at a time
• Process has exclusive access
• Remains allocated until process completes or explicitly releases
• Simple to manage but may lead to inefficiency

Advantages:

• Simple allocation mechanism
• No interference from other processes
• Predictable performance for the process
• Suitable for devices that cannot be shared (e.g., tape drives)

Disadvantages:

• Device may remain idle while allocated
• Poor resource utilization
• Can lead to deadlock if not managed properly
• Other processes must wait even if device is idle

Examples: Tape drives, plotters, older printers, CD/DVD writers

2. Shared Devices

Shared devices can be used by multiple processes concurrently or in an interleaved manner. The operating system manages access to ensure proper synchronization.

Characteristics:

• Multiple processes can access simultaneously or through time-sharing
• Requires synchronization mechanisms
• Better utilization than dedicated devices
• OS scheduler manages access

Advantages:

• Better resource utilization
• Higher system throughput
• Reduced waiting time for processes
• Cost-effective (fewer devices needed)

Disadvantages:

• Complex management and synchronization required
• Potential for conflicts between processes
• Overhead of context switching between requests
• Security and privacy concerns

Examples: Hard disks, network cards, USB ports, modern printers (with spooling)

3. Virtual Devices

Virtual devices are a combination of dedicated and shared device techniques. A dedicated device is transformed into a shared device through spooling.

Spooling (Simultaneous Peripheral Operations OnLine):

Spooling is a technique where data is temporarily held in a buffer (spool) on disk. The device reads from or writes to this spool, allowing processes to continue without waiting for slow I/O devices.

How Spooling Works:

Process 1 --> |        |
Process 2 --> | SPOOL  | --> Device (Printer)
Process 3 --> | (Disk) |
Process n --> |________|

1. Process sends output to spool file on disk
2. Process continues execution immediately
3. Spooler daemon reads from spool and sends to device
4. Device processes requests one at a time

Advantages of Virtual Devices:

• Processes don't wait for slow devices
• Better CPU utilization
• Dedicated devices can be shared effectively
• Improves overall system performance

Disadvantages:

• Requires disk space for spooling
• Additional overhead for spool management
• Delayed output (not immediate)

Examples: Print spooling, batch processing systems

I/O Devices

Types of I/O Devices

1. Block Devices:

• Store information in fixed-size blocks
• Each block has its own address
• Can read/write blocks independently
• Support random access
• Examples: Hard disks, SSDs, USB drives, CD-ROMs

2. Character Devices:

• Deliver or accept a stream of characters
• Not addressable, no seek operation
• Sequential access only
• Examples: Keyboards, mice, serial ports, printers, network cards

Storage Devices

Disk Structure

Modern disk drives are addressed as large one-dimensional arrays of logical blocks. The disk controller manages the mapping between logical blocks and physical sectors.

Physical Structure:

• Platter: Circular disk coated with magnetic material
• Track: Concentric circles on a platter
• Sector: Subdivision of a track (typically 512 bytes or 4KB)
• Cylinder: Same track number on all platters
• Read/Write Head: Mechanism that reads/writes data

Disk Scheduling Algorithms

The operating system is responsible for using hardware efficiently. For disk drives, this means having fast access time and high disk bandwidth. Disk scheduling algorithms determine the order in which disk I/O requests are serviced.

Performance Metrics:

• Seek Time: Time to move read/write head to desired track (most significant)
• Rotational Latency: Time for desired sector to rotate under head
• Transfer Time: Time to actually transfer data
• Access Time: Seek Time + Rotational Latency + Transfer Time

1. First-Come, First-Served (FCFS) Disk Scheduling:

Requests are serviced in the order they arrive, just like FCFS process scheduling.

Advantages: Simple, fair (no starvation)

Disadvantages: May cause long seek times, inefficient

Example:

Request Queue: 98, 183, 37, 122, 14, 124, 65, 67
Initial head position: 53
Total tracks: 0-199

Service order: 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67

Total head movement:
|98-53| + |183-98| + |37-183| + |122-37| + |14-122| + |124-14| + |65-124| + |67-65|
= 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2
= 640 tracks

2. Shortest Seek Time First (SSTF):

Selects the request with minimum seek time from the current head position. Similar to SJF in process scheduling.

Advantages: Better throughput than FCFS, reduces average seek time

Disadvantages: Can cause starvation of far requests, not optimal

Example (same queue):

Start: 53
Closest to 53: 65 (distance 12)
From 65, closest: 67 (distance 2)
From 67, closest: 37 (distance 30)
From 37, closest: 14 (distance 23)
From 14, closest: 98 (distance 84)
From 98, closest: 122 (distance 24)
From 122, closest: 124 (distance 2)
From 124, closest: 183 (distance 59)

Service order: 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183

Total: 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236 tracks

3. SCAN (Elevator Algorithm):

The disk arm moves in one direction, servicing all requests in its path, until it reaches the end of the disk. Then it reverses direction and services requests in the opposite direction.

Advantages: No starvation, predictable, uniform wait time

Disadvantages: May service recently arrived requests immediately while older requests wait

Example:

Start: 53, Direction: towards 0
Requests: 98, 183, 37, 122, 14, 124, 65, 67

Service order (going towards 0 first):
53 → 37 → 14 → 0 (end) → 65 → 67 → 98 → 122 → 124 → 183

Total: |37-53| + |14-37| + |0-14| + |65-0| + |67-65| + |98-67| + |122-98| + |124-122| + |183-124|
= 16 + 23 + 14 + 65 + 2 + 31 + 24 + 2 + 59
= 236 tracks

4. C-SCAN (Circular SCAN):

Similar to SCAN, but instead of reversing direction at the end, the head returns to the beginning of the disk and starts servicing from there. Treats the disk as circular.

Advantages: More uniform wait time than SCAN, fairer

Disadvantages: Longer seek time than SCAN

Example:

Start: 53, Direction: towards 199
Requests: 98, 183, 37, 122, 14, 124, 65, 67

Service order:
53 → 65 → 67 → 98 → 122 → 124 → 183 → 199 (end) → 0 (return) → 14 → 37

Total: |65-53| + |67-65| + |98-67| + |122-98| + |124-122| + |183-124| + |199-183| + |199-0| + |14-0| + |37-14|
= 12 + 2 + 31 + 24 + 2 + 59 + 16 + 199 + 14 + 23
= 382 tracks

5. LOOK Algorithm:

Similar to SCAN but the arm only goes as far as the last request in each direction, then reverses. Doesn't go all the way to the end of the disk.

6. C-LOOK Algorithm:

Similar to C-SCAN but only goes to the last request, not the end of disk.

Buffering

What is Buffering?

A buffer is a memory area that stores data temporarily while it is being transferred between two devices or between a device and an application. Buffering compensates for the speed difference between producer and consumer of data.

Types of Buffering

1. Single Buffering:

• One buffer is used to hold data
• While user process consumes data from buffer, OS fills another block in system memory
• Simple but process must wait if buffer is being filled

2. Double Buffering:

• Two buffers are used
• While one buffer is being filled, the other can be processed
• Allows overlap of I/O and processing
• Better performance than single buffering

3. Circular Buffering (Buffer Pool):

• Multiple buffers arranged in a circular manner
• Provides greatest flexibility
• Used when data transfer is continuous
• Examples: Video streaming, audio playback

Advantages of Buffering:

• Compensates for speed mismatch between devices
• Allows processes to continue while I/O occurs
• Supports copy semantics (changes to data don't affect I/O)
• Reduces context switches

Disadvantages:

• Requires memory overhead
• Complex buffer management needed
• Can introduce latency

❓ Unit IV: Solved Questions

Disk Request Queue: 95, 180, 34, 119, 11, 123, 62, 64
Initial head position: 50
Total tracks: 0-199

Service Order: 50 → 95 → 180 → 34 → 119 → 11 → 123 → 62 → 64

Head Movement Calculation:
50 to 95:   |95 - 50|  = 45 tracks
95 to 180:  |180 - 95| = 85 tracks
180 to 34:  |34 - 180| = 146 tracks
34 to 119:  |119 - 34| = 85 tracks
119 to 11:  |11 - 119| = 108 tracks
11 to 123:  |123 - 11| = 112 tracks
123 to 62:  |62 - 123| = 61 tracks
62 to 64:   |64 - 62|  = 2 tracks

Total Head Movement (FCFS) = 45 + 85 + 146 + 85 + 108 + 112 + 61 + 2
                            = 644 tracks

    0                                             199
    |-----|-----|-----|-----|-----|-----|-----|
         11    34  50  62  64    95    119  180
                                        123

Path: 50 → 95 → 180 → 34 → 119 → 11 → 123 → 62 → 64
      (lots of back-and-forth movement)

Starting at: 50
Pending requests: 95, 180, 34, 119, 11, 123, 62, 64

Step 1: From 50, find nearest
Distances: |95-50|=45, |180-50|=130, |34-50|=16, |119-50|=69, 
           |11-50|=39, |123-50|=73, |62-50|=12, |64-50|=14
Nearest: 62 (distance 12)
Move: 50 → 62 (12 tracks)
Remaining: 95, 180, 34, 119, 11, 123, 64

Step 2: From 62, find nearest
Distances: |95-62|=33, |180-62|=118, |34-62|=28, |119-62|=57,
           |11-62|=51, |123-62|=61, |64-62|=2
Nearest: 64 (distance 2)
Move: 62 → 64 (2 tracks)
Remaining: 95, 180, 34, 119, 11, 123

Step 3: From 64, find nearest
Distances: |95-64|=31, |180-64|=116, |34-64|=30, |119-64|=55,
           |11-64|=53, |123-64|=59
Nearest: 34 (distance 30)
Move: 64 → 34 (30 tracks)
Remaining: 95, 180, 119, 11, 123

Step 4: From 34, find nearest
Distances: |95-34|=61, |180-34|=146, |119-34|=85, |11-34|=23, |123-34|=89
Nearest: 11 (distance 23)
Move: 34 → 11 (23 tracks)
Remaining: 95, 180, 119, 123

Step 5: From 11, find nearest
Distances: |95-11|=84, |180-11|=169, |119-11|=108, |123-11|=112
Nearest: 95 (distance 84)
Move: 11 → 95 (84 tracks)
Remaining: 180, 119, 123

Step 6: From 95, find nearest
Distances: |180-95|=85, |119-95|=24, |123-95|=28
Nearest: 119 (distance 24)
Move: 95 → 119 (24 tracks)
Remaining: 180, 123

Step 7: From 119, find nearest
Distances: |180-119|=61, |123-119|=4
Nearest: 123 (distance 4)
Move: 119 → 123 (4 tracks)
Remaining: 180

Step 8: Last request
Move: 123 → 180 (57 tracks)

Service Order: 50 → 62 → 64 → 34 → 11 → 95 → 119 → 123 → 180

Total Head Movement (SSTF) = 12 + 2 + 30 + 23 + 84 + 24 + 4 + 57
                            = 236 tracks

FCFS Total:  644 tracks
SSTF Total:  236 tracks

Improvement: 644 - 236 = 408 tracks saved (63% reduction!)

SSTF is much more efficient than FCFS for this request pattern.

Q2. Differentiate between Dedicated, Shared, and Virtual Devices

📘 UNIT V: Information Management & File Systems

File System Concepts

What is a File?

A file is a named collection of related information recorded on secondary storage (disk). It is the smallest allotment of logical secondary storage - the OS doesn't write to disk unless it's going to a file.

File Characteristics:

• Name: Symbolic identifier, human-readable (only info kept in human-readable form)
• Identifier: Unique tag (number) identifying file within file system
• Type: Information about file format (text, binary, executable, etc.)
• Location: Pointer to device and location on device
• Size: Current file size (in bytes, words, or blocks)
• Protection: Access control information (who can read, write, execute)
• Time, Date, User ID: Data for protection, security, usage monitoring

File Types

Files can be classified based on their content and usage:

File Operations

The operating system provides system calls to perform various file operations:

• Create: Allocate space, make entry in directory
• Write: Write data to file at current position, update write pointer
• Read: Read data from file at current position, advance read pointer
• Reposition (Seek): Move read/write pointer to specific location
• Delete: Remove directory entry, release file space
• Truncate: Erase contents but keep attributes
• Open: Load file attributes and locations into memory
• Close: Free up memory space used by file attributes

File Access Methods

1. Sequential Access

Information in the file is processed in order, one record after another. This is the simplest access method.

How it works:

• Read all bytes/records from the beginning
• Cannot skip around - must read sequentially
• File pointer automatically advances after each read/write
• To access record N, must first access records 1 through N-1

Operations:

• read_next() - read next portion and advance pointer
• write_next() - write next portion and advance pointer
• reset() - go back to beginning

Advantages:

• Simple implementation
• Suitable for tape drives
• Efficient for processing entire file
• Natural for many applications (log files, batch processing)

Disadvantages:

• Slow for accessing specific records
• Inefficient if only small portion of file needed
• Cannot skip or jump to arbitrary positions easily

Examples: Compilers reading source code, text editors, log file processing

2. Direct Access (Random Access)

File is viewed as numbered sequence of blocks or records. Can read/write blocks in any order, no sequential access needed.

How it works:

• Each record/block has a logical address (number)
• Can directly access any record by specifying its number
• No need to search from beginning
• File pointer can be moved to any position

Operations:

• read(n) - read block n
• write(n) - write block n
• seek(n) - position to block n

Advantages:

• Fast access to any part of file
• Efficient for databases and large files
• No need to read unwanted data
• Supports random access patterns

Disadvantages:

• More complex implementation
• Requires disk or random-access storage
• Not suitable for sequential media (tapes)

Examples: Databases, indexed files, virtual memory swap files

3. Indexed Access

Uses an index (like a book's index) to access records. The index contains pointers to various blocks in the file.

How it works:

• Separate index file contains key-pointer pairs
• To find a record, first search the index for the key
• Index gives pointer to actual record location
• Follow pointer to access the record

Structure:

Index File:
Key    | Pointer
-------|--------
"John" | Block 5
"Mary" | Block 12
"Sam"  | Block 3

Data File:
Block 3: Sam's record
Block 5: John's record
Block 12: Mary's record

Advantages:

• Very fast searching by key
• Efficient for large files
• Can have multiple indexes on same file
• Direct access without scanning entire file

Disadvantages:

• Extra space required for index
• Index must be maintained (overhead on insertions/deletions)
• More complex than direct access

Examples: Database management systems, library catalog systems

Directory Structure

What is a Directory?

A directory is a container that holds information about files. It provides a mapping between file names and their actual file structures. Directories themselves are special files maintained by the OS.

Types of Directory Structures

1. Single-Level Directory:

The simplest directory structure - all files are contained in the same directory.

Root Directory
    |
    |-- file1.txt
    |-- file2.exe
    |-- file3.doc
    |-- program.c

Characteristics:

• All files in one directory
• Simple naming scheme
• Easy to implement and understand

Advantages: Simple, easy to support, fast file access

Disadvantages:

• Naming problem - all files must have unique names
• Difficult to remember file names as number grows
• No grouping capability
• Not suitable for multiple users

2. Two-Level Directory:

Separate directory for each user. Each user has their own User File Directory (UFD).

Master File Directory (MFD)
    |
    |-- User1 (UFD)
    |     |-- file1.txt
    |     |-- file2.c
    |
    |-- User2 (UFD)
    |     |-- file1.txt  (different from User1's file1.txt)
    |     |-- prog.exe
    |
    |-- User3 (UFD)
          |-- data.dat
          |-- report.doc

Characteristics:

• MFD (Master File Directory) at top level
• Each entry in MFD points to a UFD for a user
• Files are addressed: user-name/file-name
• Different users can have same filename

Advantages:

• Solves naming problem - each user has separate namespace
• Efficient searching (search only user's directory)
• Isolates users from each other

Disadvantages:

• No grouping within user directory
• Difficult to share files between users
• Still limits organizational capability

3. Tree-Structured Directory (Hierarchical):

Most common structure. Allows arbitrary tree structure - directories can contain files and subdirectories.

Root (/)
    |
    |-- home/
    |     |-- user1/
    |     |     |-- documents/
    |     |     |     |-- report.doc
    |     |     |     |-- letter.txt
    |     |     |-- programs/
    |     |           |-- test.c
    |     |           |-- a.out
    |     |
    |     |-- user2/
    |           |-- data.txt
    |
    |-- bin/
    |     |-- ls
    |     |-- cat
    |
    |-- etc/
          |-- config.sys

Characteristics:

• Unlimited depth of directories
• Directories are special files
• Each process has current (working) directory
• Paths can be absolute (from root) or relative (from current)

Path Names:

• Absolute Path: /home/user1/documents/report.doc (starts from root)
• Relative Path: documents/report.doc (from current directory)

Advantages:

• Efficient file organization and grouping
• Easy navigation
• Natural hierarchical structure
• Current directory concept simplifies naming

Disadvantages:

• More complex implementation
• File sharing still limited
• Path names can become long

4. Acyclic Graph Directory:

Extension of tree structure that allows shared subdirectories and files. Same file can appear in multiple directories via links.

Root
    |
    |-- user1/
    |     |-- doc/
    |     |     |-- file1.txt
    |     |     |-- shared --> (link to user2/data)
    |     |
    |     |-- programs/
    |
    |-- user2/
          |-- data/  <-- shared by user1 via link
                |-- common.dat
                |-- info.txt

Implementation Methods:

• Hard Links: Multiple directory entries point to same file (same inode in UNIX)
• Symbolic Links: Special file that contains path to another file

Advantages:

• Flexible file sharing
• Avoids file duplication
• Consistency (one copy of shared file)

Disadvantages:

• Complex to implement
• Deletion becomes complicated (reference counting needed)
• Possible dangling pointers with symbolic links

5. General Graph Directory:

Most flexible - allows cycles in directory structure. Can have links that create loops.

Problem: Cycles can cause issues:

• File search may loop infinitely
• Traversal algorithms become complex
• Deletion is very complicated

Solutions:

• Garbage collection to detect cycles
• Restrict to acyclic graph (most common)
• Use reference counting

File Protection and Access Control

Why Protection?

Files need protection because:

• Multi-user systems have many users accessing files simultaneously
• Need to prevent unauthorized access
• Maintain data integrity and confidentiality
• Control what operations different users can perform

Types of Access

Different operations that can be performed on files:

• Read: View file contents
• Write: Modify file contents
• Execute: Load and run program file
• Append: Add data to end (but not modify existing)
• Delete: Remove file from system
• List/Attributes: View file name and attributes
• Rename: Change file name
• Copy: Make duplicate of file

Access Control Methods

1. Access Control List (ACL):

Each file has a list of users and their permitted access types.

File: report.doc
ACL:
    User: John    - Read, Write, Execute
    User: Mary    - Read
    User: Admin   - Read, Write, Execute, Delete
    User: Guest   - Read

Advantages:

• Fine-grained control
• Flexible - can specify exact permissions per user
• Easy to determine who has access to a file

Disadvantages:

• Can become very long for many users
• Difficult to determine all files a user can access
• More space required

2. Group-Based Access (UNIX Model):

Users are divided into groups. Each file has three sets of permissions:

• Owner: User who created the file
• Group: Set of users who share the file
• Others/World: All other users

Permissions (3 bits each):

• r (read) = 4
• w (write) = 2
• x (execute) = 1

Example: -rwxr-xr--
    - : Regular file (d for directory)
    rwx : Owner can read, write, execute (7)
    r-x : Group can read and execute (5)
    r-- : Others can only read (4)

Numeric representation: 754

Advantages:

• Compact representation (9 bits)
• Simple and efficient
• Easy to understand and manage
• Widely used (UNIX, Linux)

Disadvantages:

• Less flexible than ACL
• Only three categories of users
• Cannot specify individual user permissions easily

3. Password Protection:

Each file has a password. Users must provide password to access file.

Advantages: Simple, compact

Disadvantages:

• Password must be remembered
• Same password for all users (or many passwords needed)
• Difficult to revoke access
• Security risk if password shared or written down

File System Models

1. Simple File System Model

Basic file system with minimal features. Files are stored sequentially on disk with simple directory structure.

Characteristics: Single-level directory, sequential allocation, simple naming

2. General File System Model

More sophisticated, supports multiple levels of abstraction and various access methods.

Layers:

• Application programs
• Logical file system (manages metadata)
• File organization module (translates logical to physical blocks)
• Basic file system (issues generic commands to device driver)
• I/O control (device drivers and interrupt handlers)
• Devices (physical hardware)

3. Symbolic File System Model

Uses symbolic names and provides abstraction from physical storage. Focus on logical organization.

4. Logical File System

Manages file metadata (name, type, location, size, protection). Maintains directory structure. Provides file operations interface to users.

5. Physical File System

Manages physical blocks on storage device. Handles allocation, deallocation, and free space management. Translates logical block numbers to physical block addresses.

File Allocation Methods

1. Contiguous Allocation

Each file occupies a set of contiguous blocks on disk.

Directory Entry: Contains start block and length

Example:
File: test.txt
Start Block: 5
Length: 3 blocks

Disk: [...][test][test][test][...]
           5     6     7

Advantages:

• Simple implementation
• Excellent read performance (sequential and direct access)
• Minimal seek time for sequential access
• Only starting location needed

Disadvantages:

• External fragmentation
• Difficult to grow files (need to find larger contiguous space)
• Must know file size at creation time
• Compaction needed to reclaim space

2. Linked Allocation

Each file is a linked list of disk blocks. Blocks can be scattered anywhere on disk.

Directory entry points to first block
Each block contains pointer to next block

File: example.txt
Start: Block 5

Block 5: [data][ptr→9]
Block 9: [data][ptr→2]
Block 2: [data][ptr→11]
Block 11: [data][NULL]

Advantages:

• No external fragmentation
• Easy to grow files (just allocate new block and update last pointer)
• Simple free space management
• No need to know file size in advance

Disadvantages:

• Poor random access (must follow chain from beginning)
• Space overhead for pointers
• Reliability - broken link loses rest of file
• Slow access time

FAT (File Allocation Table) - Variation:

• Links stored in separate table (FAT) instead of blocks
• FAT kept in memory for faster access
• Used by MS-DOS, Windows 95/98

3. Indexed Allocation

Each file has an index block containing pointers to all blocks of the file.

Index Block (Block 10):
    [ptr→5][ptr→9][ptr→2][ptr→11]

Data Blocks:
    Block 5: [file data]
    Block 9: [file data]
    Block 2: [file data]
    Block 11: [file data]

Advantages:

• Supports direct access (no sequential scan needed)
• No external fragmentation
• Easy to grow files (update index block)
• Fast random access

Disadvantages:

• Overhead of index block (wasted space for small files)
• Index block size limits file size
• Extra disk access to read index block

Solutions for Large Files:

• Linked Scheme: Index block points to other index blocks
• Multilevel Index: Index of index blocks (like paging)
• Combined Scheme (UNIX inode): Direct blocks + indirect blocks + double indirect + triple indirect

❓ Unit V: Solved Questions

read_next()    - Read next record and advance pointer
write_next()   - Write next record and advance pointer
reset()        - Move pointer back to beginning
skip_forward(n) - Skip n records (by reading and discarding)

read(n)     - Read record number n
write(n)    - Write to record number n
position(n) - Move file pointer to record n

Index File:
Key     | Pointer
--------|--------
1001    | Block 5
1002    | Block 5
2001    | Block 12
2002    | Block 12
3001    | Block 20

Data File (Sequential):
Block 5:  Records with keys 1001, 1002
Block 12: Records with keys 2001, 2002
Block 20: Records with key 3001

┌─────────────────────────────┐
│    Root Directory           │
├─────────────────────────────┤
│  file1.txt                  │
│  program.exe                │
│  data.dat                   │
│  report.doc                 │
│  photo.jpg                  │
│  music.mp3                  │
└─────────────────────────────┘

All files in one flat list

┌────────────────────────────────┐
│  Master File Directory (MFD)   │
└────────────┬───────────────────┘
             │
    ┌────────┼────────┬────────┐
    │        │        │        │
 ┌──▼──┐ ┌──▼──┐ ┌──▼──┐ ┌──▼──┐
 │User1│ │User2│ │User3│ │User4│
 │ UFD │ │ UFD │ │ UFD │ │ UFD │
 └──┬──┘ └──┬──┘ └──┬──┘ └──┬──┘
    │       │       │       │
 ┌──▼──┐ ┌──▼──┐ ┌──▼──┐ ┌──▼──┐
 │file1│ │file1│ │data │ │prog │
 │prog │ │doc  │ │file1│ │text │
 └─────┘ └─────┘ └─────┘ └─────┘

Path: user-name/file-name
Example: user1/file1.txt

                    Root (/)
                      │
        ┌─────────────┼─────────────┐
        │             │             │
      home/          bin/          etc/
        │             │             │
    ┌───┴───┐         │         config.sys
    │       │         │
  user1/  user2/     ls
    │       │       cat
    │       │
┌───┴───┐  data.txt
│       │
docs/  programs/
│       │
│    test.c
│    a.out
│
report.doc
letter.txt

Paths:
Absolute: /home/user1/docs/report.doc
Relative (from /home/user1): docs/report.doc

        Root
          │
    ┌─────┼─────┐
    │           │
  user1/      user2/
    │           │
 ┌──┴──┐     ┌─┴─┐
 │     │     │   │
docs/ pgm/  data/ work/
 │     │     │     │
 │   test.c shared → (link to user2/data)
 │          │
file1    common.dat
         info.txt

Links allow shared access:
user1/docs/shared → user2/data
Both users see same actual directory/file

     dir1
     /  \
    /    \
  dir2   file1
   |      |
   |      |
  dir3 ←──┘
   |
   └──→ dir1  (creates cycle!)

Q3. Explain file protection mechanisms and access control methods

File: ProjectReport.doc
Access Control List:
┌─────────────┬─────────────────────────┐
│ User        │ Permissions             │
├─────────────┼─────────────────────────┤
│ Alice       │ Read, Write, Delete     │
│ Bob         │ Read, Write             │
│ Charlie     │ Read                    │
│ Admin       │ Full Control            │
│ Guest       │ None                    │
└─────────────┴─────────────────────────┘

Each category has 3 bits: r w x

r = read (4)
w = write (2)
x = execute (1)

Example: -rwxr-xr--
│││││││││
││││││││└─ Others: read (4)
│││││││└── Others: no write (0)
││││││└─── Others: no execute (0)
│││││└──── Group: read (4)
││││└───── Group: no write (0)
│││└────── Group: execute (1)
││└─────── Owner: read (4)
│└──────── Owner: write (2)
└───────── Owner: execute (1)

Numeric: 754
Owner: 7 (rwx)
Group: 5 (r-x)
Others: 4 (r--)

777 (rwxrwxrwx) - Everyone has full access
755 (rwxr-xr-x) - Owner full, others read+execute
644 (rw-r--r--) - Owner read+write, others read only
600 (rw-------) - Only owner can read+write
700 (rwx------) - Only owner has full access