MCS-203 Final Revision Notes (PYQ-Based Topics)
Topic 1: Deadlock
Definition:
Deadlock is a condition in which two or more processes wait for each other to release resources, but none
can proceed.
Necessary Conditions (All must be true for a deadlock to occur):
1. Mutual Exclusion Only one process can use a resource at a time.
2. Hold and Wait A process holding one resource waits for another.
3. No Preemption Resources can't be forcibly taken away.
4. Circular Wait Each process is waiting for a resource held by the next in a circular chain.
Diagram (Example):
P1 -> R1
^ v
R2 <- P2
Solutions:
- Avoidance (e.g., Banker's Algorithm)
- Prevention (Break any of the 4 conditions)
- Detection & Recovery
Topic 2: CPU Scheduling
Definition:
CPU Scheduling is the process of determining which process in the ready queue is to be allocated the CPU.
Algorithms:
1. FCFS (First Come First Serve)
2. SJF (Shortest Job First)
3. Round Robin (Equal time slot to each process)
Key Formulas:
- Turnaround Time = Completion Time - Arrival Time
- Waiting Time = Turnaround Time - Burst Time
Gantt Chart Example (FCFS):
Process | Arrival | Burst
P1 |0 |5
P2 |1 |3
P3 |2 |2
| P1 | P2 | P3 |
0 5 8 10
Topic 3: Semaphore & ProducerConsumer Problem
Definition:
A semaphore is a synchronization tool used to control access to a shared resource using atomic operations:
wait() and signal().
Types:
1. Binary Semaphore
2. Counting Semaphore
ProducerConsumer Problem:
Shared buffer is accessed by both producer and consumer.
Variables:
- mutex = 1
- full = 0
- empty = n (buffer size)
Algorithm:
Producer:
wait(empty);
wait(mutex);
// Add item
signal(mutex);
signal(full);
Consumer:
wait(full);
wait(mutex);
// Remove item
signal(mutex);
signal(empty);
Topic 4: Page Replacement Algorithms
Definition:
When a page is needed but memory is full, the OS replaces a page using page replacement algorithms.
Algorithms:
1. FIFO Remove the oldest page
2. LRU Remove least recently used page
3. OPT Remove page used farthest in future
Example:
Reference string: 1, 2, 3, 4, 2, 1, 5
Frames: 3
FIFO step-by-step:
[1] miss
[1,2] miss
[1,2,3] miss
[2,3,4] miss
[2,3,4] hit
[2,3,1] miss
[3,1,5] miss
Total Page Faults: 6
Topic 5: Virtual Memory & Demand Paging
Definition:
Virtual Memory is a memory management technique that gives an application the illusion of having more
memory than physically available by using disk space as RAM.
Demand Paging:
Pages are loaded into memory only when required.
Terms:
- Page: Logical memory block
- Frame: Physical memory block
- Page Table: Maps pages to frames
- Page Fault: Occurs when a page is not in memory
Diagram:
Program Pages -> Page Table -> Memory Frame
If not present -> Page Fault -> Load from disk
Topic 6: Disk Scheduling Algorithms
Definition:
Disk scheduling refers to the way the operating system handles read/write requests to the disk by optimizing
the movement of the disk arm.
Key Terms:
- Seek Time: Time taken to move the head to the desired track.
- Head Movement: Total distance covered by the head.
- Track: Circular paths where data is stored on the disk.
Important Algorithms:
1. FCFS (First Come First Serve): Serve requests in the order they arrive.
2. SSTF (Shortest Seek Time First): Serve request closest to current head.
3. SCAN: Move in one direction serving all requests, then reverse.
4. C-SCAN: Move in one direction, jump to start, and continue.
Example:
Initial Head Position: 50
Request Queue: [98, 183, 37, 122, 14, 124, 65, 67]
FCFS Movement:
50 -> 98 -> 183 -> 37 -> 122 -> 14 -> 124 -> 65 -> 67
Total Head Movement = |98-50| + |183-98| + ... = 640
