OS Definition · Evolution · OS Services · System Calls · Resource Manager · Kernel Architectures · Virtual Machines
fork(), exit(), exec(), wait().open(), read(), write(), close(), unlink().ioctl(), read(), write().time(), getpid(), alarm().pipe(), socket(), send(), receive(), msgrcv(), msgsnd().
| Feature | Batch | Multiprogrammed | Time-Sharing | Distributed | Real-Time |
|---|---|---|---|---|---|
| User Interaction | None | None | Direct | Indirect | Limited/None |
| CPU Utilization | Low | High | Very High | High | Depends |
| Resource Sharing | Sequential | Concurrent | Concurrent | Network-based | Concurrent |
| Response Time | Hours | Minutes | Seconds | Depends | Microseconds |
| Examples | Payroll | Mainframe OS | Unix, Linux | LOCUS | VxWorks, QNX |
| Aspect | Monolithic | Layered | Modular | Microkernel | Hybrid |
|---|---|---|---|---|---|
| Kernel Size | Large | Medium | Small core | Very Small | Medium |
| Performance | High | Low | High | Low | Medium-High |
| Stability | Low | Medium | Medium | High | High |
| Extensibility | Poor | Poor | Good | Excellent | Good |
| Debugging | Difficult | Easy | Moderate | Easy | Moderate |
| Security | Low | Medium | Medium | High | Medium-High |
| Portability | Low | Low | Medium | High | Medium |
| Examples | Linux, Unix | THE | Modern Linux | Minix, QNX | Windows NT, XNU |
Process Concept · PCB · Process States · Scheduling Queues · Schedulers · Context Switch · Threads · CPU Scheduling Algorithms · Scheduling Criteria · Starvation & Aging
| Criterion | Description | Minimize/Maximize |
|---|---|---|
| CPU Utilization | % of time CPU is busy | Maximize |
| Throughput | Processes completed per unit time | Maximize |
| Turnaround Time | Arrival to completion | Minimize |
| Waiting Time | Time in ready queue | Minimize |
| Response Time | First response time | Minimize |
| P1 | P2 | P3 |
0 6 10 12 16
Waiting Time: P1=0, P2=4, P3=6. Avg WT = (0+4+6)/3 = 3.33 msCritical Section Problem · Race Condition · Synchronization Requirements · Peterson's Solution · Semaphores · Classical Problems · Deadlock Conditions · Prevention · Avoidance · Banker's Algorithm · Recovery
flag[i] (process i wants to enter) and turn (whose turn it is). Works for two processes only.flag[i] (boolean, indicates process i wants to enter CS) and turn (indicates whose turn it is).
// Shared variables:
boolean flag[2]; // Initially false
int turn; // 0 or 1
// Process i (other process is j=1-i):
do {
flag[i] = true;
turn = j;
while (flag[j] && turn == j); // Wait
// Critical Section
flag[i] = false;
// Remainder Section
} while (true);
How it works:wait(S) (P) and signal(S) (V).
semaphore mutex = 1; // Mutual exclusion for buffer access
semaphore empty = n; // Number of empty slots in buffer
semaphore full = 0; // Number of filled slots in buffer
int buffer[n]; // Shared circular buffer
int in = 0, out = 0; // Buffer indices
// Producer Process:
do {
// Produce an item
item = produce_item();
wait(empty); // Wait for empty slot
wait(mutex); // Enter critical section
buffer[in] = item;
in = (in + 1) % n;
signal(mutex); // Exit critical section
signal(full); // Signal one item available
} while (true);
// Consumer Process:
do {
wait(full); // Wait for item to consume
wait(mutex); // Enter critical section
item = buffer[out];
out = (out + 1) % n;
signal(mutex); // Exit critical section
signal(empty); // Signal one empty slot
// Consume the item
consume_item(item);
} while (true);
Explanation:empty semaphore ensures producer doesn't overflow buffer.full semaphore ensures consumer doesn't underflow buffer.mutex ensures mutual exclusion for buffer access.
read_count. Last reader releases rw_mutex. Writer uses rw_mutex.service_queue mutex ensures FIFO order. Reader waits for both its turn and no pending writers.
semaphore chopstick[5]; // One semaphore per chopstick
void philosopher(int i) {
do {
think();
wait(chopstick[i]); // Pick up left chopstick
wait(chopstick[(i+1)%5]); // Pick up right chopstick
eat();
signal(chopstick[i]); // Put down left chopstick
signal(chopstick[(i+1)%5]); // Put down right chopstick
} while (true);
}
Deadlock possibility: If all philosophers pick up left fork simultaneously, all wait for right fork → deadlock!Available[m]: Available instances of each resource type.Max[n][m]: Maximum demand of each process.Allocation[n][m]: Current allocation to each process.Need[n][m]: Remaining needs. Need = Max - Allocation.Memory Hierarchy · Memory Allocation · Fragmentation · Paging · Page Table · TLB · Segmentation · Virtual Memory · Demand Paging · Page Replacement Algorithms · Thrashing · Working Set Model
| Algorithm | Page Faults |
|---|---|
| FIFO | ~9 |
| OPTIMAL | 8 |
| LRU | 9 |
Ref | F1 | F2 | F3 | Fault?
7 | 7 | | | Y (new)
0 | 7 | 0 | | Y
1 | 7 | 0 | 1 | Y
2 | 2 | 0 | 1 | Y (7 evicted - oldest)
0 | 2 | 0 | 1 | N (hit)
3 | 2 | 3 | 1 | Y (0 evicted)
0 | 2 | 3 | 0 | Y (1 evicted)
4 | 4 | 3 | 0 | Y (2 evicted)
2 | 4 | 2 | 0 | Y (3 evicted)
3 | 4 | 2 | 3 | Y (0 evicted)
0 | 0 | 2 | 3 | Y (4 evicted)
3 | 0 | 2 | 3 | N (hit)
2 | 0 | 2 | 3 | N (hit)
1 | 1 | 2 | 3 | Y (0 evicted)
2 | 1 | 2 | 3 | N (hit)
0 | 0 | 2 | 3 | Y (1 evicted)
1 | 1 | 2 | 3 | Y (0 evicted)
7 | 7 | 2 | 3 | Y (1 evicted)
0 | 0 | 2 | 3 | Y (7 evicted)
1 | 1 | 2 | 3 | Y (0 evicted)
Total Page Faults (FIFO, 3 frames): 15
| Algorithm | 3 Frames | 4 Frames |
|---|---|---|
| FIFO | 15 | 16 (Belady's Anomaly!) |
| OPTIMAL | 9 | 8 |
| LRU | 12 | 10 |
File Concept · File Attributes · File Types · Access Methods · Directory Structure · File Allocation Methods · Free Space Management · Disk Structure · Disk Scheduling Algorithms · Head Movement Calculation
| Feature | Contiguous | Linked | Indexed |
|---|---|---|---|
| External Fragmentation | Yes | No | No |
| Direct Access | Yes | No | Yes |
| File Growth | Difficult | Easy | Easy |
| Overhead | Minimal | Pointer per block | Index block |
| Reliability | High | Low (broken link) | Medium |
| Access Speed | Fast | Slow | Medium |
| Algorithm | Total Head Movement | % of FCFS |
|---|---|---|
| FCFS | 643 | 100% |
| SSTF | 239 | 37.2% |
| SCAN | 354 | 55.1% |
| C-SCAN | 385 | 59.9% |
| LOOK | 302 | 47.0% |
| C-LOOK | 325 | 50.5% |
| Method | Speed | Space Overhead | Complexity |
|---|---|---|---|
| Bitmap | Fast scan | Low (1 bit/block) | Simple |
| Linked List | Slow traversal | Low (1 pointer/block) | Simple |
| Grouping | Medium | Medium | Medium |
| Indexing | Fast | Medium | Complex |
| Algorithm | Total Movement | Avg Seek | Fairness | Starvation |
|---|---|---|---|---|
| FCFS | 643 | 80.4 | Excellent | None |
| SSTF | 239 | 29.9 | Poor | Possible |
| SCAN | 354 | 44.3 | Good | None |
| C-SCAN | 385 | 48.1 | Better | None |
| LOOK | 302 | 37.8 | Good | None |
| C-LOOK | 325 | 40.6 | Better | None |
| Formula | Description |
|---|---|
| Turnaround Time = Completion Time - Arrival Time | Total time in system |
| Waiting Time = Turnaround Time - Burst Time | Time spent waiting in ready queue |
| Response Time = First Response - Arrival Time | Time to first response (interactive) |
| CPU Utilization = CPU Busy Time / Total Time | Percentage of time CPU is busy |
| Throughput = Number of processes / Total time | Processes completed per unit time |
| Dispatch Latency = Context switch + Mode switch | Time to start a process |
| EMAT = m + α × m | Effective Memory Access Time with TLB |
| Formula | Description |
|---|---|
| Page Size = 2^n bytes | Always a power of 2 |
| Pages = Logical Address Space / Page Size | Number of pages in process |
| Frames = Physical Memory / Page Size | Number of frames in memory |
| Page Table Size = Pages × Page Table Entry Size | Memory needed for page table |
| Physical Address = Frame × Page Size + Offset | Address translation formula |
| EMAT = m + α × m | Effective access time (TLB hit = 1 mem access) |
| Page Fault Rate p = Page Faults / Total References | Frequency of page faults |
| Effective AT = (1-p) × m + p × page_fault_time | Avg memory access time |
| Formula | Description |
|---|---|
| Total Head Movement = Σ |Current - Next| | Sum of all seek distances |
| Average Seek = Total Head Movement / (n-1) | Average per request |
| Disk Access Time = Seek Time + Rotational Latency + Transfer Time | Complete disk access |
| Rotational Latency (avg) = (1/2) × (60/RPM) × 1000 ms | Average rotation delay |
| Transfer Time = (Bytes / Sector) / (Bytes per track × RPM) | Data transfer time |
| Bandwidth = Bytes Transferred / Total Time | Data transfer rate |
Kernel Architectures (Speed: High → Low):
Monolithic > Hybrid > Modular > Layered > Microkernel
Kernel Architectures (Stability: Low → High):
Monolithic < Hybrid < Modular < Layered < Microkernel
Thread Models (Performance: High → Low):
One-to-One > Many-to-Many > Many-to-One
CPU Scheduling (Preemptive):
SRTF, Round Robin, Priority (preemptive), Multilevel Feedback Queue
CPU Scheduling (Non-preemptive):
FCFS, SJF, Priority (non-preemptive), HRRN
Deadlock Approaches (Preventive → Reactive):
Prevention (no condition) → Avoidance (Banker's) → Detection & Recovery → Ignorance
Unit 1: Remember all OS types with examples. Know 5 system call categories. Monolithic vs Microkernel is a favorite 15M question. Virtual machines = hypervisor abstraction.
Unit 2: Always draw Gantt charts for scheduling problems. FCFS has convoy effect. SJF is optimal but requires burst time prediction. Round Robin performance depends on quantum. Starvation → Aging solution.
Unit 3: Peterson's algorithm works for 2 processes only. Producer-Consumer needs 3 semaphores. Banker's algorithm: Safety sequence is key. Deadlock conditions ALL must hold. Dining Philosophers deadlock = all pick left fork simultaneously.
Unit 4: Internal frag in fixed partition + paging. External frag in variable partition. Page fault count: OPTIMAL < LRU < FIFO generally. Belady's anomaly is FIFO-only. Thrashing prevention = Working Set or PFF. EMAT formula with TLB.
Unit 5: Contiguous = fast but external frag. Linked = no external frag but no direct access. Indexed = best compromise. SSTF is most efficient but unfair. C-SCAN gives most uniform wait. Disk structure: Platters → Tracks → Sectors → Cylinders.