Operating System (IT-501) - Unit 5 Short Notes

UNIT 5: OPERATING SYSTEM

I. OPERATING SYSTEM FUNDAMENTALS

Definition: An Operating System (OS) is system software that manages computer hardware and software resources, providing common services for computer programs and acting as an intermediary between users and hardware.

Major Objectives:

• Convenience & Efficiency

• Hardware abstraction

• Resource management (CPU, memory, I/O)

• Security & protection

Major Services:

• Program Execution: Load & run user programs.

• I/O Operations: Hide device specifics via drivers.

• File System Management: Organize, store, retrieve data.

• Communications: Inter-process & network communication.

• Error Detection & Handling: Ensure system integrity.

• Resource Allocation: Allocate resources to processes.

• Protection & Security: Prevent unauthorized access.

Types of OS:

OS Structure & Design:

• Modularity: Divide OS into separate, interchangeable modules.

• Layering: Hierarchical approach (e.g., THE OS). Easier to debug but can be inefficient.

• Microkernel: Minimal kernel (scheduling, memory, IPC). Services run in user space. More secure & portable but performance overhead.

System Calls: Interface between user programs and OS services (e.g., read(), fork()). They are the only way to request OS services from user mode.

Spooling (Simultaneous Peripheral Operations On-Line): Buffer data for I/O devices (e.g., printer spooler) to avoid CPU idle time.

Protection of Hardware Resources:

• I/O Protection: All I/O instructions are privileged (kernel mode only).

• Memory Protection: Base & limit registers, or paging segmentation, prevent process from accessing unauthorized memory.

[!TIP] Common Exam Question: "Explain OS structure issues." Focus on trade-offs: Layering is clean but slow; Microkernel is modular but has context-switch overhead.

II. PROCESS MANAGEMENT

Process: An executing program. It is an active entity with:

• Program counter, registers, stack, data section.

• Process Control Block (PCB): OS data structure containing all process info (PID, state, program counter, registers, memory limits, I/O status, scheduling info).

Process States & Transitions:

[New] → [Ready] → [Running] → [Waiting/Blocked] → [Terminated]

         ↑           ↓

         └──[Ready]←┘ (I/O complete)

• Suspend: Move process from Ready/Waiting to Suspended state (swapped to disk).

• Resume: Bring back from Suspended to Ready/Waiting.

CPU Scheduling Criteria:

Scheduling Algorithms:

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

   • Non-preemptive.

   • Processes served in arrival order.

   • Convoy Effect: Long jobs delay short ones.

   • Average waiting time often high.

2. Shortest Job First (SJF):

   • Non-preemptive: Pick shortest CPU burst next.

   • Preemptive (Shortest Remaining Time First - SRTF): Preempt if new job has shorter remaining time.

   • Optimal for minimizing average waiting time (provable).

   • Requires knowledge/estimation of next CPU burst.

3. Priority Scheduling:

   • Each process has priority (lower number = higher priority).

   • Preemptive: Preempt if higher priority arrives.

   • Non-preemptive: Wait until current finishes.

   • Starvation possible for low-priority processes (solution: aging - gradually increase priority).

4. Round Robin (RR):

   • Preemptive. Ready queue is circular.

   • Each process gets time quantum (q).

   • If burst > q, process is preempted and placed at end of ready queue.

   • Context switching overhead increases if q is too small.

   • Gantt Chart: Time slices shown as blocks.

Gantt Chart Construction:

• Timeline showing when each process uses CPU.

• Calculate:

  • Completion Time (CT) = End of process on chart.

  • Turnaround Time (TAT) = CT - Arrival Time.

  • Waiting Time (WT) = TAT - Burst Time.

  • Normalized TAT = TAT / Burst Time.

Ready State & CPUs:

• With n CPUs, maximum processes in Ready state = unlimited (ready queue can have more than n processes).

• But at any instant, at most n processes can be in Running state.

• Ready queue size is independent of CPU count; it's a software queue.

Algorithm Comparison (for average waiting time):

For same set of processes (arrive at same time): SJF (or SRTF) < RR (with optimal q) < Priority < FCFS

SJF is theoretically optimal, but impractical without burst time knowledge.

[!TIP] Exam Calculation Tip: For preemptive algorithms (SRTF, Preemptive Priority), redraw Gantt chart every time a new process arrives or a preemption occurs. Always list processes in order of execution with start/end times.

III. PROCESS SYNCHRONIZATION

Critical Section Problem:

• Critical Section: Code segment accessing shared resource (variable, file, device).

• Requirements for Solution:

  1. Mutual Exclusion: Only one process in CS at a time.

  2. Progress: If no process in CS and others want to enter, decision cannot be postponed indefinitely.

  3. Bounded Waiting: There exists a bound on number of times other processes can enter CS after a request.

Semaphores:

• Synchronization variable with integer value.

• Binary Semaphore (Mutex): Values 0 or 1. Used for mutual exclusion.

• Counting Semaphore: Integer ≥ 0. Used for resource counting.

• Operations (must be atomic):

  • wait(S) or P(S): S = S - 1. If S < 0, block process & add to S's queue.

  • signal(S) or V(S): S = S + 1. If S ≤ 0, unblock a process from S's queue.

• Atomicity: P and V must execute without interruption. Implemented via disabling interrupts or using hardware instructions like TestAndSet.

TestAndSet Instruction:

boolean TestAndSet(boolean *lock) {

    boolean old = *lock;

    *lock = true;

    return old;

}

Used to implement busy-waiting mutex:

void wait(boolean *lock) {

    while (TestAndSet(lock)) ; // busy wait

}
void signal(boolean *lock) {

    *lock = false;

}

Minimal busy waiting: Use a queue of blocked processes instead of spinning (as in classic semaphore definition).

Semaphore Value Calculation:

Given sequence of P and V operations, initial value S must be such that at least one P blocks.

• Key: P decrements, V increments.

• Block occurs when S becomes negative during a P.

• Find minimum S such that after all operations, S_final ≥ 0 but at some point S < 0.

• Largest initial S for which at least one P blocks: S_initial = (#P operations - #V operations) - 1? Actually, we need the maximum S that still causes a block. If #P > #V, then any S_initial ≤ (#P - #V - 1) will cause block. Largest such S is (#P - #V - 1).

• Example: 20 P, 12 V. Net change = -8. To have at least one block, we need S_initial + (cumulative P - V) < 0 at some point. The largest S that still causes a block is when the minimum cumulative sum is exactly -1. So S_initial + min_cumulative_sum = -1 → S_initial = -1 - min_cumulative_sum. But simpler: If total P > total V, then the largest S that causes blocking is (total P - total V - 1). Here, 20-12-1 = 7. So S=7 will cause at least one block? Check: Start S=7. After 20P and 12V in worst order (all P first), S becomes 7-20 = -13, so blocks. But if order is mixed, maybe not. Actually, we need guaranteed block for some order? The question says "during an execution, 20 P and 12 V are issued in some order. Find the largest initial value of S for which at least one P will remain blocked." This means: we want S such that there exists some order of operations that causes a block. The worst-case order for blocking is all P first. So if S_initial - 20 < 0 → S_initial < 20. But we also have V's that can increase S. To ensure at least one block in some order, we can arrange all P first. Then condition: S_initial - 20 < 0 → S_initial ≤ 19. But is S=19 valid? Start 19, do 20 P: after 19th P, S=0; 20th P makes S=-1 → block. So S=19 causes block. But what about S=20? Start 20, 20 P: S=0, no block. So largest S causing block is 19. But wait, we have 12 V's that could be interleaved. If we interleave V's early, S might never go negative. But the question says "in some order" meaning we can choose the order to maximize chance of block? Actually, it says "during an execution, 20 P(S) operations and 12 V(S) operations are issued in some order." It doesn't say we control order. We need S such that no matter the order, at least one P blocks? Or there exists an order where at least one P blocks? The phrasing "for which at least one P(S) operation will remain blocked" suggests we want S where it's possible for a P to block. That is, there is some sequence that causes block. Then largest S is when even in worst case (all P first) we get block: S_initial < total P. So largest integer S is total P - 1 = 19. But if we consider that V's can be used to avoid block, we need to ensure that even if V's are used as late as possible? Actually, to guarantee a block for all orders, we need S_initial < total P - total V? Because if V's are placed before some P's, they increase S. The condition for guaranteed block (for all orders) is S_initial + min_cumulative_sum < 0. The min cumulative sum occurs when all P come before all V: cumulative sum after k P's = -k. So min = -total P. So condition: S_initial - total P < 0 → S_initial < total P. So for S=19, in order all P first, block occurs. But in order where V's are early, maybe no block. So if we want at least one P blocked in the given execution (order fixed but unknown), we need to consider the worst order for blocking? The question likely expects: Largest S such that it's possible for a P to block is total P - 1 = 19. But many textbooks solve: Let initial value = x. After all operations, final value = x + 12 - 20 = x - 8. For a P to block, at some point S must go negative. The maximum x that allows this is when the minimum value during execution is -1. The minimum occurs if all P are before V: min = x - 20. Set x - 20 = -1 → x = 19. So answer is 19. This matches typical semaphore problems.

Use of Semaphores for Synchronization:

• Producer-Consumer problem (bounded buffer).

• Readers-Writers problem (priority variations).

• Dining Philosophers.

IV. DEADLOCK

Deadlock vs Starvation:

Necessary Conditions (all must hold simultaneously):

1. Mutual Exclusion: Resources non-shareable.

2. Hold and Wait: Process holds at least one resource and waits for another.

3. No Preemption: Resources cannot be forcibly taken.

4. Circular Wait: Circular chain of processes each waiting for resource held by next.

Deadlock Handling:

1. Prevention: Ensure at least one condition never holds.

   • Eliminate Mutual Exclusion? Only for sharable resources (e.g., read-only files).

   • Eliminate Hold and Wait: Require processes to request all resources at once (low utilization) or release held resources before requesting new ones.

   • Eliminate No Preemption: Preempt resources if possible (costly, state save/restore).

   • Eliminate Circular Wait: Impose total ordering on resource types; request in increasing order.

2. Avoidance: Allow conditions but ensure system never enters unsafe state.

   • Safe State: There exists a sequence (safe sequence) of processes such that each can get its max need from currently available + resources of all previous (finished) processes.

   • Unsafe State: No such sequence exists; deadlock may occur.

   • Banker's Algorithm (for single resource type or multiple):

     • Need Matrix: Need[i][j] = Max[i][j] - Allocation[i][j].

     • Safety Algorithm:

       1. Let Work = Available, Finish[i] = false for all i.

       2. Find i such that Finish[i]=false and Need[i] ≤ Work.

       3. If found: Work = Work + Allocation[i], Finish[i]=true, go to 2.

       4. If all Finish[i]=true → safe state; order of i is safe sequence.

     • Resource Request Algorithm:

       • If Request[i] ≤ Need[i] and Request[i] ≤ Available, then pretend allocate (update Available, Allocation, Need) and run safety check. If safe, grant; else, process waits.

3. Detection & Recovery:

   • Detection: Use Resource Allocation Graph (RAG) for single instance resources. Cycle → deadlock. For multiple instances, use variant of Banker's (wait-for graph).

   • Recovery:

     • Process termination (all or one by one).

     • Resource preemption (rollback to safe state).

Resource Allocation Graph (RAG):

• Vertices: Processes (circles) & Resource Types (squares). Each resource type may have multiple instances (dots inside square).

• Edges:

  • Claim Edge (dashed): Process may request resource (future request).

  • Assignment Edge (solid): Resource allocated to process.

  • Request Edge (solid): Process currently requesting resource.

• Deadlock Detection:

  • For single instance resources: Cycle in RAG → deadlock.

  • For multiple instances: Convert to Wait-For Graph (processes only, edge Pi→Pj if Pj holds resource Pi needs). Cycle → deadlock.

• Adding New Edge: If adding a request edge creates a cycle (single instance), deadlock occurs.

[!TIP] Banker's Algorithm Tip: Always compute Need matrix first. In safety check, find a process whose Need ≤ Work (vector comparison). Update Work by adding that process's Allocation.

V. MEMORY MANAGEMENT

Memory Management Techniques:

Dynamic Allocation Algorithms (given memory holes & process size):

• First-Fit: Allocate first hole that is big enough. (Fast, but may cause external fragmentation at front).

• Best-Fit: Allocate smallest hole that is big enough. (Minimizes leftover, but many small holes, slower).

• Worst-Fit: Allocate largest hole. (Aims to leave large holes, but can cause fragmentation quickly).

Paging:

• Logical Address = Page number + Page offset.

• Physical Address = Frame number + Page offset.

• Page Table: Maps page number → frame number. Stored in memory.

• Translation Lookaside Buffer (TLB): Fast associative cache for page table entries.

• Effective Access Time (EAT) with TLB:

$$EAT = (TLB_{hit} \times (TLB_{access} + memory_{access})) + (TLB_{miss} \times (TLB_{access} + 2 \times memory_{access} + page\ table\ lookup))$$

Usually simplified: $$\displaystyle EAT = (hit\_ratio \times (t_{TLB} + t_{mem})) + ((1-hit\_ratio) \times (t_{TLB} + 2t_{mem})) $$

where $$\displaystyle t_{mem} $$ is memory access time.

Demand Paging:

• Pages loaded only when needed (on page fault).

• Page Fault: Required page not in memory.

• Page Fault Service Time = Time to read page from disk + swap out if needed + context switch overhead.

• EAT with Page Fault Probability (p):

$$EAT = (1-p) \times t_{mem} + p \times (t_{page\_fault} + t_{mem})$$

where $$\displaystyle t_{page\_fault} $$ is major (disk access ~ ms).

Page Replacement Algorithms (when no free frame):

• FIFO: Replace oldest page. Belady's anomaly: more frames → more faults possible.

• LRU: Replace least recently used page. Near-optimal, but needs hardware support (reference bits, stack) or software approximation.

• Optimal (Belady's Optimal): Replace page that will not be used for longest time in future. Theoretical minimum faults, but future knowledge impossible (used for comparison).

Reference String Example:

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

Compute faults for 3 frames:

• FIFO: Start empty. 1,2,3 (faults). 4 replaces 1 (fault). 3,4 hit. 2 replaces 2? Actually after 4, frames: [2,3,4]. Then 2 hits? Wait, reference after 4 is 2. 2 is in frame? Yes, so hit. Then 1 fault (replace oldest, say 3? Need to track properly). Use table.

• LRU: Replace least recently used.

• Optimal: Look ahead.

Thrashing:

• Cause: High page fault rate due to insufficient frames for working set. CPU spends most time paging, not executing.

• Prevention: Working Set Model (track pages used in recent time interval), Page Fault Frequency control (adjust frames allocated), Local vs Global Replacement.

Page Allocation Policies:

Advanced Paging Schemes:

• Segmented Paging: Each segment has its own page table. Allows variable-size segments with paging benefits. But multi-level lookup.

• Hashed Page Tables: For 64-bit address spaces. Hash page number to bucket; bucket contains chain of PTEs. Avoids huge linear tables.

Protection in Paging:

• Page table entries include protection bits (read, write, execute).

• Invalid page number or protection violation → trap to OS (segmentation fault).

VI. I/O AND DISK MANAGEMENT

Disk Structure:

• Track: Circular path on platter.

• Sector: Smallest addressable unit (e.g., 512B).

• Cylinder: Set of tracks aligned vertically across platters.

• Platter: Physical disk surface.

Disk Performance Metrics:

• Seek Time: Time to move head to target track.

• Rotational Latency (Delay): Time for disk to rotate to target sector (average = ½ rotation time).

• Transfer Time: Time to read/write data once head is positioned.

• Access Time = Seek Time + Rotational Latency + Transfer Time.

Disk Scheduling Algorithms:

Given request queue and initial head position.

1. FCFS: Serve in arrival order. Fair but high head movement.

2. SSTF: Serve closest request to current head. Reduces movement but may starve distant requests.

3. SCAN (Elevator): Head moves in one direction servicing requests until end, then reverses.

4. C-SCAN: Head moves in one direction servicing requests; when reaching end, jumps to beginning (no service on return). More uniform wait time.

5. LOOK: Like SCAN but only goes as far as last request in direction, then reverses.

Total Head Movement Calculation:

• List requests in order served.

• Sum absolute differences between consecutive positions (including from initial head to first request).

Example (from Nov 2022): Requests: 86,1470,913,1774,6,948,1509,1022,1750,130; Head at 143.

• FCFS: |143-86| + |86-1470| + ...

• SSTF: At each step, pick closest to current head.

• SCAN: Assume direction (e.g., increasing). Go to max (1774) servicing all in between, then reverse to min (6).

• LOOK: Go to max request (1774) then reverse to min (6).

Disk Load Time Calculation:

Given: seek time t_s, rotation time t_r (full rotation), track capacity C bytes, page size p bytes.

• Time to load one page = t_s + (t_r / 2) + (p / (C / t_r))? Actually transfer time = (page size) / (track capacity) × rotation time.

• If pages spread across disk (no two on same cylinder), seek time incurred for each page.

• Total time = number_of_pages × (seek_time + avg_rotational_latency + transfer_time_per_page).

Free-Space Management (Disk Blocks):

• Bit Vector: 1 bit per block. Free block = 1. Simple, but large disk → large bit map.

• Linked List: Free blocks linked together; each block contains pointer to next free block.

• Grouping: First free block contains addresses of many free blocks.

• Counting: Keep list of (contiguous free blocks, count). Efficient for contiguous allocation.

Variable Block Size Allocation:

• File system may allocate space as one large block (e.g., 4KB) or multiple small blocks (e.g., eight 512B).

• Performance Improvement: For large files, fewer large blocks reduce metadata overhead and seek time. For small files, small blocks reduce internal fragmentation.

• Modifications to Free-Space Management:

  • Bit Vector: Need to track block size; maybe multiple bitmaps per size class.

  • Linked List: Block header must indicate size; free list may become fragmented by size.

  • Buddy System: Allocate in power-of-two sizes; split/merge blocks. Natural support for variable sizes.

VII. FILE SYSTEMS

File Attributes:

• Name, Identifier (inode number), Type, Location, Size, Protection (permissions), Timestamps (create, access, modify), Owner ID.

File Operations:

• Create, Delete, Open, Close, Read, Write, Append, Seek, Get/Set Attributes.

File Access Methods:

1. Sequential Access: Read/write in order (most common).

2. Direct (Random) Access: Read/write at arbitrary position (e.g., lseek()). Efficient for databases.

3. Indexed Access: Build index for keys (e.g., ISAM). Fast for key-based lookup.

File Allocation Methods:

File Allocation for DBMS:

• Preferred: Indexed allocation (e.g., B+ trees).

• Justification: DBMS requires fast random access by key. Indexed allocation provides direct access via index structure, minimizing disk seeks. Contiguous allocation would cause massive external fragmentation; linked allocation too slow for random access.

File Removal & Free List Issues:

• Problem: When file removed, its blocks added to free list. This can cause external fragmentation (many small holes) and free list fragmentation (free list becomes long, scattered).

• Solutions:

  • Compaction: Periodically move files to consolidate free space (expensive).

  • Grouping: Keep blocks of same file together (but removal leaves hole).

  • Block Reallocation Policy: Try to allocate new files in same area as old file (coalescing on delete).

  • Use indexed allocation so file blocks not necessarily contiguous; free list management simpler.

Applications Requiring Random Access to Indexed Files:

• Database Management Systems (e.g., MySQL, Oracle) using B-tree indexes.

• File Systems themselves (directory structures are indexed).

• Virtual Memory (page tables are indexed).

\boxed{\text{Key Formulas}}

1. Effective Access Time with TLB:

$$EAT = (hit\_ratio \times (t_{TLB} + t_{mem})) + ((1 - hit\_ratio) \times (t_{TLB} + 2t_{mem}))$$

2. Effective Access Time with Page Faults:

$$EAT = (1 - p) \times t_{mem} + p \times (t_{page\_fault} + t_{mem})$$

3. Banker's Need Matrix:

$$Need[i][j] = Max[i][j] - Allocation[i][j]$$

4. Disk Access Time for Page (pages spread):

$$T_{page} = t_{seek} + \frac{t_{rotation}}{2} + \frac{page\_size}{track\_capacity} \times t_{rotation}$$

5. Normalized Turnaround Time:

$$N\_TAT = \frac{Turnaround\_Time}{Burst\_Time}$$

[!TIP] Final Exam Strategy:

• Scheduling: Practice Gantt charts for all 4 algorithms with given process table. Always compute WT, TAT, N_TAT.

• Banker's: Compute Need first, then run safety algorithm step-by-step.

• RAG: Draw carefully; claim edges (dashed), assignment edges (solid). Cycle detection for single instance.

• Page Replacement: Use reference string; simulate frame contents for FIFO (queue), LRU (stack/age), Optimal (look ahead).

• Disk Scheduling: Draw head movement diagram; sum absolute differences.

• Semaphore: For initial value problem, think: S_initial + (cumulative P - V). Block occurs when <0. Largest S causing block = total P - 1 if all P before V.