Group B — Medium / Descriptive Questions (5 Marks Each)

5-State Process Transition Diagram

A process in an operating system transitions through different states during its lifecycle, managed by the OS Process Manager.

• New: The process is being created and its Process Control Block (PCB) is initialized.
• Ready: The process is loaded in main memory and is waiting to be assigned to a processor by the short-term scheduler.
• Running: Instructions are being executed by the CPU. A single CPU can only have one running process at a time.
• Waiting (Blocked): The process cannot execute further until some event occurs (e.g., I/O completion, waiting for a signal).
• Terminated: The process has finished execution and the OS reclaims its allocated resources.

CPU Scheduling Criteria

Different CPU scheduling algorithms have different properties. To evaluate them, we use standard performance metrics:

• CPU Utilization: The percentage of time that the CPU is busy executing processes rather than being idle. We want this as close to 100% as possible.
• Throughput: The number of processes that complete their execution per time unit. A measure of overall system productivity.
• Turnaround Time (TAT): The total time taken from the submission of a process until its completion.
  Formula: \(TAT = \text{Completion Time (CT)} - \text{Arrival Time (AT)}\)
• Waiting Time (WT): The total time a process spends waiting in the Ready queue.
  Formula: \(WT = TAT - \text{Burst Time (BT)}\)
• Response Time (RT): The time taken from the submission of a request until the first response is produced (i.e., when the process gets the CPU for the very first time).

FCFS Scheduling Numerical

First-Come, First-Served (FCFS) is a non-preemptive algorithm where the process that requests the CPU first is allocated the CPU first.

Given: All processes arrive at \(T=0\). Burst Times: \(P1=6, P2=8, P3=7, P4=3\).

Gantt Chart

Calculations Table

• Average Turnaround Time: \((6 + 14 + 21 + 24) / 4 = 16.25 \text{ ms}\)
• Average Waiting Time: \((0 + 6 + 14 + 21) / 4 = 10.25 \text{ ms}\)

SJF vs SRTF Scheduling

Shortest Job First (SJF) scheduling allocates the CPU to the process with the smallest next CPU burst. It yields the minimum average waiting time for a given set of processes. SJF can be implemented in two modes:

1. Non-Preemptive SJF

• Once the CPU is assigned to a process, it cannot be preempted until that process completes its burst.
• If a new process arrives with a shorter burst time than the currently running process, the CPU will not switch until the current process finishes.

2. Preemptive SJF (Shortest Remaining Time First - SRTF)

• If a new process arrives in the Ready queue with a CPU burst length shorter than the remaining time of the currently executing process, the CPU is preempted.
• The current process is paused and placed back in the Ready queue, and the newly arrived shorter process begins execution immediately.
• Advantage: SRTF generally results in a lower average waiting time compared to non-preemptive SJF.
• Disadvantage: Higher context-switching overhead and risk of starvation for long processes.

Round Robin Scheduling & Time Quantum

Round Robin (RR) is a preemptive CPU scheduling algorithm designed specifically for time-sharing systems. The Ready queue is treated as a circular queue.

• Mechanism: The CPU scheduler goes around the Ready queue allocating the CPU to each process for a time interval of up to 1 Time Quantum (TQ) (or time slice).
• If a process's burst time is less than 1 TQ, it releases the CPU voluntarily.
• If the burst time is longer than 1 TQ, the OS timer interrupts the process after the quantum expires, context switches it to the back of the Ready queue, and dispatches the next process.

Impact of Time Quantum Size

• If TQ is too small: The algorithm causes too many context switches. The overhead of saving/loading registers degrades system performance significantly.
• If TQ is too large: The overhead decreases, but RR degenerates into First-Come-First-Served (FCFS) scheduling, resulting in poor response times for short interactive processes.
• Rule of Thumb: 80% of CPU bursts should be shorter than the time quantum.

The Critical Section Problem

A Critical Section is a segment of code where a process accesses and modifies shared resources (like common variables, files, or tables). To prevent data inconsistency and race conditions, a system must ensure that when one process is executing in its critical section, no other process is allowed to execute in its critical section.

Any solution to the Critical Section problem must satisfy three strict requirements:

1. Mutual Exclusion: The core requirement. If process \(P_i\) is executing in its critical section, then no other processes can be executing in their critical sections.
2. Progress: If no process is executing in its critical section and some processes wish to enter theirs, then only those processes that are not executing in their remainder sections can participate in deciding which will enter its critical section next. This selection cannot be postponed indefinitely (no deadlock).
3. Bounded Waiting: There exists a bound, or limit, on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted (no starvation).

Peterson's Solution

Peterson's Solution is a classic software-based algorithmic solution to the critical section problem specifically designed for two processes (\(P_0\) and \(P_1\)) that alternate execution.

Data Structures

• int turn; // Indicates whose turn it is to enter the CS.
• boolean flag[2]; // flag[i] = true indicates that \(P_i\) is ready to enter its CS.

Code for Process i (where j is the other process)

Proof of correctness: Mutual exclusion is preserved because both processes can be stuck in the while loop only if turn == 0 and turn == 1 simultaneously, which is impossible. Progress is met because a process only gets stuck if the other process intends to enter and has the turn.

Semaphores in OS

A Semaphore (S) is an integer variable used for process synchronization and controlling access to common resources in a concurrent system. Unlike pure software locks like Peterson's, Semaphores are managed by the OS and avoid busy waiting.

Semaphores can only be accessed via two indivisible (atomic) standard operations:

1. wait(S) or P(S) or down(S)

Used to acquire a resource. It decrements the semaphore value. If the value becomes negative, the process is blocked and placed in the semaphore's waiting queue.

2. signal(S) or V(S) or up(S)

Used to release a resource. It increments the semaphore value. If there are processes waiting in the queue (value \(\le 0\)), one of them is awakened.

Producer-Consumer Problem

The Producer-Consumer (Bounded Buffer) problem involves a Producer process that generates data and puts it into a fixed-size buffer, and a Consumer process that takes data out of the buffer. They must be synchronized so the producer doesn't insert into a full buffer, and the consumer doesn't remove from an empty buffer.

Semaphore Initialization

• mutex = 1; (Binary semaphore for mutual exclusion on the buffer)
• empty = N; (Counting semaphore counting empty slots, initially N)
• full = 0; (Counting semaphore counting filled slots, initially 0)

Producer Code

Consumer Code

Readers-Writers Problem

The Readers-Writers problem deals with situations where a database is shared among several concurrent processes. Some processes only want to read (Readers), while others want to update (Writers). We must ensure that:

1. Multiple readers can read simultaneously.
2. If a writer is writing, no other reader or writer can access the database (Exclusive access).

Semaphore Initialization

• mutex = 1; (Ensures mutual exclusion when updating the read_count variable)
• rw_mutex = 1; (Ensures mutual exclusion for the actual database writers)
• int read_count = 0; (Tracks how many readers are currently reading)

Writer Code

Reader Code

Dining Philosophers Problem

The Dining Philosophers Problem is a classic synchronization problem. Five philosophers sit around a circular table. Each has a plate of spaghetti. Between each pair of plates is one chopstick (total 5). To eat, a philosopher needs both the left and right chopsticks.

The Problem (Deadlock)

If all 5 philosophers simultaneously pick up their left chopstick, all 5 chopsticks are taken. When they reach for their right chopstick, it is held by their neighbor. Everyone waits indefinitely, causing a Deadlock.

Deadlock Avoidance Solutions

1. Resource Hierarchy (Asymmetric Solution): Number the chopsticks 1 to 5. Philosophers must always pick up the lower-numbered chopstick first. This breaks the circular wait condition.
2. Capacity Limitation: Allow at most 4 philosophers to sit at the table with 5 chopsticks. This guarantees at least one philosopher can get two chopsticks.
3. Both-or-Nothing (Monitor): A philosopher only picks up chopsticks if both are available simultaneously in a critical section.

4 Necessary Conditions for Deadlock

A deadlock situation can arise if and only if the following four conditions hold simultaneously in a system (known as Coffman conditions):

1. Mutual Exclusion: At least one resource must be held in a non-sharable mode. If another process requests that resource, the requesting process must be delayed until the resource has been released.
2. Hold and Wait: A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.
3. No Preemption: Resources cannot be preempted; that is, a resource can be released only voluntarily by the process holding it, after that process has completed its task.
4. Circular Wait: There must exist a set \(\{P_0, P_1, \dots, P_n\}\) of waiting processes such that \(P_0\) is waiting for a resource held by \(P_1\), \(P_1\) is waiting for a resource held by \(P_2\), \(\dots\), and \(P_n\) is waiting for a resource held by \(P_0\).

Resource Allocation Graph (RAG)

A Resource Allocation Graph (RAG) is a directed graph used to visually model the state of an OS, showing which processes hold which resources and which processes are requesting resources. It helps in deadlock detection.

• Vertices (V): Two types: Processes (\(P = \{P_1, P_2, \dots\}\) represented as circles) and Resources (\(R = \{R_1, R_2, \dots\}\) represented as rectangles with dots indicating instances).
• Edges (E):
  • Request Edge (\(P_i \rightarrow R_j\)): Process \(P_i\) requests an instance of \(R_j\).
  • Assignment Edge (\(R_j \rightarrow P_i\)): An instance of \(R_j\) is allocated to \(P_i\).

Cycle Detection and Deadlock

• If the RAG contains no cycles, then no process is deadlocked.
• If the RAG contains a cycle:
  1. If each resource type has exactly one instance, a cycle implies a Deadlock has definitely occurred.
  2. If each resource type has multiple instances, a cycle does not necessarily imply a deadlock (it is a necessary but not sufficient condition).

Deadlock Prevention vs Deadlock Avoidance

Banker's Safety Algorithm

The Safety Algorithm (part of Banker's Algorithm) determines if a system is in a "safe state" where all processes can finish without deadlocking. It uses three matrices: Allocation, Max, and Need (where \(Need = Max - Allocation\)), and a vector Available.

Algorithm Steps:

1. Initialization:
   Let Work and Finish be vectors of length \(m\) (resources) and \(n\) (processes).
   Initialize: Work = Available
   Initialize: Finish[i] = false for \(i = 0, 1, \dots, n-1\).
2. Find a candidate process:
   Find an index \(i\) such that both:
   a) Finish[i] == false (Process has not finished)
   b) Need[i] ≤ Work (System can satisfy its needs)
   If no such \(i\) exists, go to Step 4.
3. Simulate execution:
   The system temporarily grants resources to \(P_i\). When \(P_i\) finishes, it returns all its held resources to the system.
   Work = Work + Allocation[i]
Finish[i] = true
   Go back to Step 2.
4. Check Status:
   If Finish[i] == true for all \(i\), then the system is in a Safe State. The order in which processes finished is the Safe Sequence.
   If any Finish[i] == false, the system is in an Unsafe State (deadlock possible).

Paging Architecture

Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory. It avoids external fragmentation by breaking memory into fixed-sized blocks.

• Logical Address Space is divided into blocks of the same size called Pages.
• Physical Memory is divided into fixed-sized blocks called Frames (where Page Size == Frame Size).

Address Translation

The CPU generates a Logical Address divided into two parts: Page Number (\(p\)) and Page Offset (\(d\)). The OS uses a Page Table to map \(p\) to a Physical Frame Number (\(f\)). The physical address is \(f\) concatenated with \(d\).

Segmentation Architecture

Segmentation is a memory management scheme that supports the user's view of memory. A logical address space is a collection of variable-sized segments (e.g., main program, functions, stack, symbol table). Unlike paging where all pages are the same size, segments have variable lengths based on logical program units.

Address Translation

The logical address consists of two parts: Segment Number (\(s\)) and Offset (\(d\)). Address translation is done using a Segment Table. Each entry in the segment table has:

• Base: Contains the starting physical address where the segment resides in memory.
• Limit: Specifies the length of the segment.

Internal vs External Fragmentation

Translation Lookaside Buffer (TLB)

Because the Page Table is stored in main memory, every data access requires two memory accesses: one for the page table, one for the actual data. This slows down the system by a factor of 2. To solve this, OS uses a Translation Lookaside Buffer (TLB).

The TLB is a small, fast hardware associative cache built directly into the MMU. It stores the most recently used Page-to-Frame translations.

• TLB Hit: Page number is found in TLB. Physical address is generated immediately.
• TLB Miss: Page number not in TLB. Must look up in main memory Page Table, then load it into TLB for future use.

Effective Access Time (EAT)

EAT calculates the average time to access memory given the hit ratio (\(\alpha\)), TLB lookup time (\(\epsilon\)), and memory access time (\(m\)).

Where \((\epsilon + 2m)\) is the penalty for a TLB miss (one memory access for page table, one for data).

Demand Paging and Page Fault Handling

Demand Paging is a virtual memory technique where pages are loaded from the disk into main memory only when they are explicitly demanded (i.e., referenced) during program execution, rather than loading the entire program at once.

Page Fault Handling Process

If a process tries to access a page that was not brought into memory (invalid bit in page table), it causes a Page Fault trap to the OS.

1. The OS intercepts the trap and checks an internal table to see if the memory reference was valid (but page is on disk) or invalid (segmentation fault).
2. If valid, the OS finds a free frame in physical memory. (If no free frame exists, a Page Replacement Algorithm like LRU runs).
3. The OS schedules a disk I/O operation to read the required page into the newly allocated free frame.
4. Once the disk read completes, the OS updates the Page Table, marking the page as valid and mapping it to the new frame.
5. The OS restarts the instruction that was interrupted by the trap, allowing the process to access the page seamlessly.

FIFO Page Replacement & Belady's Anomaly

First-In, First-Out (FIFO) is the simplest page replacement algorithm. It maintains a queue of all pages in memory. When a page fault occurs and a page must be replaced, the oldest page (the one at the front of the queue) is chosen for replacement.

• Pros: Very easy to understand and implement using a standard FIFO queue.
• Cons: Its performance is generally poor because it replaces the oldest page, which might still be heavily used by the program.

Belady's Anomaly

Generally, one expects that increasing the number of physical frames in memory will result in fewer page faults. However, Belady's Anomaly is a phenomenon where increasing the number of page frames increases the number of page faults for certain page reference strings when using the FIFO algorithm.

This happens because FIFO does not possess the stack property (unlike LRU or Optimal), meaning the set of pages in memory with \(N\) frames is not necessarily a subset of the pages in memory with \(N+1\) frames.

LRU Page Replacement Algorithm

Least Recently Used (LRU) page replacement replaces the page that has not been used for the longest period of time. It relies on the heuristic that pages heavily used in the recent past will likely be used again in the near future.

LRU is considered an excellent algorithm because it does not suffer from Belady's Anomaly, but it requires significant hardware support to implement efficiently. Two common implementations are:

1. Counters (Time-of-Use)

• Every page table entry has a "time-of-use" register.
• The CPU is equipped with a logical clock or counter that increments on every memory reference.
• Whenever a page is referenced, the clock value is copied into the page's register.
• On a page fault, the OS searches the page table for the page with the smallest time value and replaces it. (Requires searching the whole table).

2. Stack Implementation

• Maintain a stack (typically a doubly linked list) of page numbers.
• Whenever a page is referenced, it is removed from its current position and pushed to the top of the stack.
• On a page fault, the page at the bottom of the stack is chosen for replacement. (Requires updating pointers on every memory access).

Optimal Page Replacement (OPT)

The Optimal Page Replacement Algorithm has the lowest possible page fault rate of all algorithms and does not suffer from Belady's Anomaly.

The Strategy: Replace the page that will not be used for the longest period of time in the future.

• If the OS knows the exact sequence of upcoming page references, it can look ahead in the string.
• It selects the page currently in memory whose next reference is furthest away in the future sequence.

Why is it used?

In practice, OPT is impossible to implement because the OS cannot predict the future memory references of a program. It is solely used as a benchmark to evaluate the performance of other algorithms (like LRU and FIFO). If LRU performs within a few percent of OPT, it is considered highly efficient.

Thrashing & Working Set Model

Thrashing

Thrashing occurs when a system spends more time paging (swapping pages in and out of the disk) than executing actual instructions. It happens when a process does not have "enough" physical frames to hold its actively used pages. The CPU utilization plummets because processes are constantly blocked waiting for page faults.

The Working Set Model

The OS uses the Working Set Model to prevent thrashing. It is based on the concept of locality of reference.

• Working Set Window (\(\Delta\)): A fixed number of most recent page references.
• Working Set (\(WS\)): The set of distinct pages actually referenced in the most recent \(\Delta\) accesses. This represents the pages the process is currently actively using.
• Working Set Size (\(WSS_i\)): The total number of pages in the working set for process \(i\).

Prevention: The OS calculates the total demand \(D = \sum WSS_i\). If the total demand \(D\) exceeds the total available physical memory frames (\(m\)), thrashing will occur. In this case, the OS suspends one or more processes to free up frames and stabilize the system.

File Allocation Methods

Directory Structures

• Single-Level Directory: The simplest structure. All files from all users are contained in the same single directory.
  • Pros: Easy to support and understand.
  • Cons: Naming collisions (no two files can have the same name system-wide) and poor grouping for multiple users.
• Two-Level Directory: Each user has their own separate User File Directory (UFD). A Master File Directory (MFD) points to all UFDs.
  • Pros: Solves name collision between different users. Supports user isolation.
  • Cons: Users cannot easily share files or group files into logical sub-categories.
• Tree-Structured Directory: Generalizes the two-level directory into an arbitrary tree. Users can create subdirectories within subdirectories.
  • Pros: Excellent for logical grouping and organization. Absolute and relative path naming. Currently used by Windows, Linux, macOS.
  • Cons: Does not allow sharing of files (a file cannot exist in two different directories simultaneously unless linked).

Disk Scheduling Algorithms

Disk scheduling optimizes the movement of the read/write head (seek time) to serve pending I/O requests.

• FCFS (First-Come, First-Served): Processes requests strictly in the order they arrive.
  Pros: Fair. Cons: Extremely inefficient, causes wild head swings across the disk.
• SSTF (Shortest Seek Time First): Selects the request closest to the current head position.
  Pros: Minimizes seek time significantly. Cons: Can cause starvation for requests far from the current head position.
• SCAN (Elevator Algorithm): The head starts from one end, moves towards the other end servicing requests, and when it hits the end, it reverses direction.
  Pros: Solves starvation. Cons: Unequal wait times (requests near the edge wait longer when the head reverses).
• C-SCAN (Circular SCAN): Like SCAN, but when the head reaches one end, it immediately returns to the beginning without servicing requests on the return trip.
  Pros: Provides a much more uniform waiting time for all cylinders.

UNIX Inode Structure

In UNIX file systems, every file is represented by an Inode (Index Node). An inode contains metadata about the file (permissions, owner, size, timestamps) and, most importantly, pointers to the data blocks on the disk.

To support files of vastly different sizes while keeping the inode small, UNIX uses a multi-level index pointer structure:

1. Direct Pointers (Usually 12 or 15): Point directly to disk blocks containing the file's data. Sufficient for small files.
2. Single Indirect Pointer: Points to a disk block that contains an array of direct pointers. Used when the file grows beyond the direct pointers.
3. Double Indirect Pointer: Points to a block containing pointers to single-indirect blocks. Allows for very large files.
4. Triple Indirect Pointer: Points to a block containing pointers to double-indirect blocks. Allows for enormous files (terabytes in size).

User-Level vs Kernel-Level Threads

UNIX Process Control System Calls

• fork(): Creates a new process (the child). The child is an exact clone of the parent's memory space.
  • Returns 0 to the child process.
  • Returns the child's PID to the parent process.
• exec(): Replaces the entire memory space (code, data, heap, stack) of the calling process with a brand new program loaded from disk. It never returns unless there's an error. Typically called by the child after a fork().
• wait(): Called by the parent process to pause its execution until one of its child processes terminates. It also retrieves the exit status of the child and prevents the child from becoming a zombie.
• exit(): Terminates the calling process gracefully. It flushes I/O buffers, closes files, and deallocates memory, passing an exit status back to the parent (via wait()).

Free Space Management

The OS must keep track of available (free) blocks on the disk to allocate space to new files.

1. Bit Vector (Bit Map)

The free space list is implemented as a bitmap. Each block on the disk is represented by 1 bit. If the block is free, the bit is 1. If the block is allocated, the bit is 0.

• Advantage: Very simple and extremely fast for finding contiguous free blocks (the OS searches for sequences of 1s using bitwise CPU instructions).
• Disadvantage: Requires extra memory to store the bitmap. For a 1TB disk with 4KB blocks, the bitmap requires 32MB of main memory to be kept resident for good performance.

2. Linked List

The OS links all free disk blocks together, keeping a pointer to the first free block in a special location on disk. The first block contains a pointer to the next free block, and so on.

• Advantage: No waste of space. The pointers are stored directly inside the free blocks themselves.
• Disadvantage: Extremely inefficient to traverse. Finding a large number of free blocks requires reading multiple disk sectors sequentially, which is very slow.

Memory Allocation Strategies

When a process requests memory in a contiguous allocation system, the OS must choose a free "hole" from the list of available memory blocks.

• First-Fit: Allocates the first hole that is big enough.
  • Pros: Fastest algorithm, minimal search time.
  • Cons: Can leave many small fragments near the beginning of memory.
• Best-Fit: Allocates the smallest hole that is big enough. Requires searching the entire list (unless sorted by size).
  • Pros: Minimizes the size of the leftover fragment.
  • Cons: Slowest. Tends to create tiny, useless holes (external fragmentation) that cannot satisfy any future requests.
• Worst-Fit: Allocates the largest hole available. Requires searching the entire list.
  • Pros: Leaves a large leftover hole, which might be useful for a subsequent large process.
  • Cons: Generally performs worse than First-Fit and Best-Fit in terms of storage utilization.

Inverted Page Table

In traditional paging, each process has its own page table, which maps logical pages to physical frames. For systems with large 64-bit address spaces, traditional page tables become gigabytes in size per process, which is unmanageable.

An Inverted Page Table solves this by having exactly one page table for the entire system, containing one entry for every physical frame of memory.

Architecture

• Each entry in the table represents a physical frame and contains the pair: [Process ID (PID), Page Number (p)].
• When a process references logical page \(p\), the CPU searches the inverted table for a match on [Current PID, p].
• If found at index \(i\), the physical frame number is \(i\).

Pros: Dramatically reduces the memory needed to store the page table (size is proportional to physical memory, not logical space).

Cons: Lookup is slower because the table is sorted by physical frame, not logical page. Finding a match requires searching the entire table, so a hash table is typically used to speed up the search.

Inter-Process Communication (IPC)

IPC mechanisms allow cooperating processes to exchange data and synchronize their actions.

Hardware Synchronization Instructions

To implement software synchronization tools like Mutexes efficiently, OS designers rely on special hardware instructions provided by modern CPUs. These instructions execute atomically (as one uninterrupted unit).

1. TestAndSet (TAS)

The TestAndSet instruction reads a boolean variable and sets it to true in a single, indivisible hardware cycle.

2. Swap (Compare-And-Swap)

The Swap instruction atomically swaps the contents of two memory variables.

Access Control Matrix & ACLs

Security in an OS is managed by tracking which Subjects (Users/Processes) have which access rights (Read, Write, Execute) to which Objects (Files, Devices, Memory).

Access Control Matrix

This is a conceptual table where rows represent domains (subjects) and columns represent objects. Each cell contains the access rights.

• If the matrix is large, it becomes very sparse (most cells are empty), wasting a huge amount of space if stored directly as a 2D array.

Access Control List (ACL)

Instead of storing the empty matrix, the OS implements it column-by-column. An Access Control List is attached to each Object.

• For a specific file, the ACL lists all the users and their specific permissions.
• Example ACL for file1.txt: (UserA: RW), (UserB: R), (GroupX: RX)
• Advantage: Easy to see who has access to a specific file. Easy to revoke access to an object. (This is how Windows NTFS and Linux permissions work).

RAID (Redundant Array of Independent Disks)

RAID is a technology that combines multiple physical disk drives into a single logical unit to improve performance, data redundancy, or both.

• RAID 0 (Striping): Data is split into blocks and distributed across all disks in the array simultaneously.
  • Performance: Excellent (read/write speeds are multiplied by the number of disks).
  • Reliability: Zero. If one disk fails, all data is completely lost.
• RAID 1 (Mirroring): Data is written identically to two (or more) disks.
  • Performance: Good read speeds, normal write speeds.
  • Reliability: High. If one disk fails, the other acts as an exact backup. Costly (50% storage efficiency).
• RAID 5 (Striping with Parity): Data is striped across disks, and "Parity" blocks are distributed across all disks.
  • Performance: Good read speeds, slight penalty on writes (parity calculation).
  • Reliability: Can survive exactly 1 disk failure. If a disk dies, missing data is mathematically reconstructed using the parity blocks on the surviving disks.

Monolithic Kernel vs Microkernel

Type 1 vs Type 2 Hypervisors (Virtualization)

A Hypervisor (or Virtual Machine Monitor - VMM) is software that creates and runs virtual machines (VMs), allowing multiple operating systems to share a single hardware host.

Type 1 Hypervisor (Bare-Metal)

• Placement: Installs directly on the physical hardware of the host machine, bypassing the need for a host operating system. The hypervisor is the OS.
• Performance: Extremely high performance and low latency, as VMs have direct access to hardware resources.
• Use Case: Enterprise data centers and cloud computing servers.
• Examples: VMware ESXi, Microsoft Hyper-V, Xen.

Type 2 Hypervisor (Hosted)

• Placement: Installs as a standard software application on top of an existing host operating system (like Windows or macOS).
• Performance: Slower. Hardware requests from the guest OS must pass through the hypervisor, then through the host OS, before reaching the CPU.
• Use Case: Desktop virtualization, software testing, running Linux on a Windows laptop.
• Examples: Oracle VirtualBox, VMware Workstation, Parallels Desktop.

Real-Time CPU Scheduling

Real-Time Systems (like autopilot avionics or medical pacemakers) have strict deadlines. The scheduler must guarantee that critical tasks complete before their deadline expires.

1. Rate-Monotonic Scheduling (RMS)

• Type: Static priority, preemptive algorithm.
• Rule: Priorities are assigned based on the period of the task. The shorter the period (the more frequently the task occurs), the higher its priority.
• Properties: Very stable and predictable. If the system is overloaded, it is guaranteed that the lowest priority tasks will miss their deadlines first. However, it cannot guarantee utilization up to 100% (the upper bound for schedulability is approx 69% for many tasks).

2. Earliest Deadline First (EDF)

• Type: Dynamic priority, preemptive algorithm.
• Rule: Priorities are assigned dynamically according to deadlines. The task with the earliest (closest) deadline gets the highest priority.
• Properties: More efficient than RMS. It can theoretically achieve 100% CPU utilization while meeting all deadlines. However, if the system becomes overloaded, it behaves unpredictably, and multiple tasks might miss their deadlines simultaneously (a domino effect).