Process Scheduling Solution

Given Data

Quantum for RR = 3

Formulas:

• $TAT = CT - AT$
• $WT = TAT - BT$

Why Do We Need to Schedule Processes?

• CPU utilization: keep the CPU busy in a multiprogramming environment.
• Throughput: maximize processes completed per unit time.
• Fairness: give each process a reasonable share of CPU.
• Minimize waiting, turnaround, and response times.
• Prevent starvation and manage resources efficiently.

1. FCFS

Execution order by arrival: P1, P2, P3, P4.

Gantt: |P1|P2|P3|P4| at 0-20-45-55-70

$$AWT = \frac{0+5+15+10}{4} = 7.5\text{ ms}$$ $$ATAT = \frac{20+30+25+25}{4} = 25\text{ ms}$$

2. SJF (Non-Preemptive)

• t=0: only P1 arrived → run P1 (0-20).
• t=20: only P2 arrived → run P2 (20-45).
• t=45: P3 (BT=10) and P4 (BT=15) available → pick P3 (45-55).
• t=55: run P4 (55-70).

Same schedule as FCFS.

$$AWT = 7.5\text{ ms},\quad ATAT = 25\text{ ms}$$

3. Round Robin (Quantum = 3)

Ready queue rule: on preemption, newly arrived processes are inserted before the preempted process.

Trace:

• 0-3: P1 (17). Queue: [P1]
• 3-6: P1 (14). Queue: [P1]
• 6-9: P1 (11). Queue: [P1]
• 9-12: P1 (8). Queue: [P1]
• 12-15: P1 (5). At t=15 P2 arrives. Queue after: [P2, P1]
• 15-18: P2 (22). Queue: [P1, P2]
• 18-21: P1 (2). Queue: [P2, P1]
• 21-24: P2 (19). Queue: [P1, P2]
• 24-27: P1 (2→0, runs 2 ms, done at 26).

Let me be precise. At 24-27 P1 has only 2 ms remaining, so:

• 24-26: P1 (2→0, P1 completes at 26). Queue: [P2]. At t=30 P3 arrives later.
• 26-29: P2 (16). Queue: [P2]
• 29-32: P2 (13). P3 arrives at t=30. Queue after: [P3, P2]
• 32-35: P3 (7). Queue: [P2, P3]
• 35-38: P2 (10). Queue: [P3, P2]
• 38-41: P3 (4). Queue: [P2, P3]
• 41-44: P2 (7). Queue: [P3, P2]
• 44-47: P3 (1). P4 arrives at t=45. Queue after: [P2, P4, P3]
• 47-50: P2 (4). Queue: [P4, P3, P2]
• 50-53: P4 (12). Queue: [P3, P2, P4]
• 53-54: P3 (1→0, P3 completes at 54). Queue: [P2, P4]
• 54-57: P2 (1). Queue: [P4, P2]
• 57-60: P4 (9). Queue: [P2, P4]
• 60-61: P2 (1→0, P2 completes at 61). Queue: [P4]
• 61-64: P4 (6). Queue: [P4]
• 64-67: P4 (3). Queue: [P4]
• 67-70: P4 (3→0, P4 completes at 70).

Completion times: P1=26, P2=61, P3=54, P4=70

$$AWT = \frac{6+21+14+10}{4} = \frac{51}{4} = 12.75\text{ ms}$$ $$ATAT = \frac{26+46+24+25}{4} = \frac{121}{4} = 30.25\text{ ms}$$

(Note: RR ordering conventions vary; results depend on insertion order.)

4. Shortest Remaining Time Next (SRTN, Preemptive SJF)

Preempt whenever a newly arrived process has less remaining time.

• 0-15: P1 runs (only process). At t=15 P1 remaining = 5, P2 arrives (25). P1(5) < P2(25) → continue P1.
• 15-20: P1 (5→0, P1 completes at 20).
• 20-30: P2 runs. At t=30 P2 remaining = 15, P3 arrives (10). P3(10) < P2(15) → preempt.
• 30-40: P3 (10→0, P3 completes at 40).
• 40-45: P2 runs (15→10). At t=45 P4 arrives (15). P2(10) < P4(15) → continue P2.
• 45-55: P2 (10→0, P2 completes at 55).
• 55-70: P4 (15→0, P4 completes at 70).

Completion times: P1=20, P2=55, P3=40, P4=70

$$AWT = \frac{0+15+0+10}{4} = \frac{25}{4} = 6.25\text{ ms}$$ $$ATAT = \frac{20+40+10+25}{4} = \frac{95}{4} = 23.75\text{ ms}$$

Summary

File Allocation Techniques: Contiguous and Linked List

1. Contiguous Allocation

In contiguous allocation, each file is stored as a contiguous run of disk blocks on the disk. The directory entry for each file records the starting block address and the length of the file.

Example:

• On a disk with 1-KB blocks, a 50-KB file is allocated 50 consecutive blocks.
• On a disk with 4-KB blocks, the same file would need 25 consecutive blocks.
• Each file begins at the start of a new block; any wasted space occurs only at the end of the last block.

Advantages

• Simple to implement -- the directory only needs to store the start address and length.
• Excellent read performance -- since blocks are consecutive, sequential and random access are both fast (minimal disk seeks).

Disadvantages

• External fragmentation -- over time, free space becomes scattered in small pieces, making it difficult to find a large contiguous area for new files.
• Difficult to extend files -- if a file needs to grow, there may be no free space immediately after its last block.
• Difficult to find space for new files when free blocks are fragmented.

2. Linked List Allocation

In linked list allocation, each file is stored as a linked list of disk blocks. The first word of each block is used as a pointer to the next block, and the remaining space in the block holds actual data.

Block 4        Block 7        Block 2        Block 9
[ptr=7|data]-->[ptr=2|data]-->[ptr=9|data]-->[EOF|data]

The directory entry stores only the address of the first block of the file; the chain of pointers leads to all subsequent blocks.

Variant: FAT (File Allocation Table)

• The pointers are moved out of the data blocks and stored in a separate table called the FAT.
• The entire block becomes available for data.
• The FAT is used as a linked list; the directory entry contains the block number of the first block, and the FAT is looked up to find the next block until a special end-of-file (EOF) value is reached.

Advantages

• Solves all problems of contiguous allocation -- no external fragmentation, files can grow easily by linking new blocks anywhere on disk.
• No need for compaction of free space.

Disadvantages

• Only efficient for sequential access -- random access is excessively slow because to reach block n, all n-1 preceding blocks must be traversed.
• Space overhead for pointers -- each block loses some bytes to store the next-block pointer.
• Each block access may require a disk seek, increasing access time.

Comparison Summary

Page Fault Calculation: FIFO and LRU

Given Data

• Reference string: 4, 7, 6, 1, 7, 6, 1, 2, 7, 2
• Number of frames: 3

1. FIFO (First In First Out)

Replace the oldest loaded page when frames are full.

FIFO Page Faults = 6, Hits = 4

2. LRU (Least Recently Used)

Replace the page not used for the longest time.

Let me recheck LRU at ref = 2 (step 8).

After processing 4,7,6,1,7,6,1 the recency order is: 1 (MRU), 6, 7 (LRU). On fault for page 2, replace 7 (LRU).

Frames now: 1, 6, 2. Recency: 2, 1, 6.

Recheck step 9 (ref = 7): recency order is 2 (MRU), 1, 6 (LRU). Replace 6 (LRU).

Frames now: 1, 2, 7. Recency: 7, 2, 1.

Corrected LRU trace:

LRU Page Faults = 6, Hits = 4

Summary

Both FIFO and LRU produce 6 page faults for this reference string with 3 frames.