Disk Scheduling Algorithms - Verified Solution

Given Data

• Request Queue: 35, 70, 45, 15, 65, 20, 80, 90, 75, 130
• Track range: 0 to 150
• Initial head position: 30
• Direction: Outward (toward higher tracks)

Sorted requests: 15, 20, 35, 45, 65, 70, 75, 80, 90, 130

1. SCAN

Head moves outward to 150, then reverses to service lower requests.

Order: 30 → 35 → 45 → 65 → 70 → 75 → 80 → 90 → 130 → 150 → 20 → 15

Total distance = (150 − 30) + (150 − 15) = 120 + 135 = 255 tracks

2. C-SCAN

Head moves outward to 150, jumps to 0, then continues servicing.

Order: 30 → 35 → ... → 130 → 150 → 0 → 15 → 20

Total = (150 − 30) + (150 − 0) + (20 − 0) = 120 + 150 + 20 = 290 tracks

(Equivalently, summing the individual steps: 5+10+20+5+5+5+10+40+20+150+15+5 = 290.)

3. LOOK

Head moves outward only to the last request (130), then reverses.

Order: 30 → 35 → ... → 130 → 20 → 15

Total = (130 − 30) + (130 − 15) = 100 + 115 = 215 tracks

4. C-LOOK

Head moves outward to last request (130), jumps to lowest request (15), continues outward.

Order: 30 → 35 → ... → 130 → 15 → 20

Total = (130 − 30) + (130 − 15) + (20 − 15) = 100 + 115 + 5 = 220 tracks

Summary

Memory Allocation: First Fit, Next Fit, Best Fit

Step 1 - Given Data

Holes in memory order:

Successive requests: (a) 10 MB, (b) 10 MB.

Step 2 - Solve

First Fit

Allocates the first hole large enough, scanning from the start each time.

(a) 10 MB: Hole 1 (15 MB) $\ge 10$ → allocate. Hole 1 leftover $= 15 - 10 = 5$ MB.

(b) 10 MB: Scan from start: Hole 1 (5) ✗, Hole 2 (2) ✗, Hole 3 (10) $\ge 10$ → allocate. Leftover $= 0$ MB.

Result: (a) Hole 1, (b) Hole 3.

Next Fit

Like First Fit but resumes scanning from the position of the last allocation.

(a) 10 MB: Start at Hole 1 (15) → allocate. Pointer at Hole 1, leftover 5 MB.

(b) 10 MB: Resume from Hole 1: (5) ✗, Hole 2 (2) ✗, Hole 3 (10) → allocate. Pointer at Hole 3.

Result: (a) Hole 1, (b) Hole 3.

(Since scanning resumes at the last hole which is now too small, next fit gives the same result as first fit here.)

Best Fit

Allocates the smallest hole that is large enough.

(a) 10 MB: Candidates $\ge 10$: Hole 1 (15, leftover 5), Hole 3 (10, leftover 0), Hole 6 (20, leftover 10). Smallest sufficient = Hole 3 (exact fit). Leftover 0 MB.

(b) 10 MB: Remaining candidates $\ge 10$: Hole 1 (15, leftover 5), Hole 6 (20, leftover 10). Smallest = Hole 1. Leftover 5 MB.

Result: (a) Hole 3, (b) Hole 1.

Final Comparison

File Structures

A file structure defines how data is organized and stored within a file. Different types of files have different internal structures depending on their purpose and the programs that use them.

Different File Structures

1. Regular Files (User Files)

Regular files contain user information. They are the most common type of file and are generally of two subtypes:

a) ASCII Files

• Consist of lines of text.
• Each line is terminated by a carriage return or newline character.
• Can be displayed and printed directly.
• Can be created and edited by any ordinary text editor.
• Example: .txt files, source code files.

b) Binary Files

• Consist of a sequence of bytes only.
• They have some internal structure known only to the programs that use them.
• Cannot be read directly as plain text.
• Example: Executable files (compiled programs), object files.

2. Directory Files

• These are system files used for maintaining the structure of the file system.
• A directory file keeps track of the files contained within it, storing their names, identifiers, and locations.
• They form the hierarchical tree structure of the file system.

3. Character Special Files

• Related to Input/Output (I/O) operations of the computer.
• Used to model serial I/O devices such as terminals, printers, and network interfaces.
• They do not store data permanently; instead, they represent device streams.

Summary Table

Conclusion

Different file structures serve different purposes in an operating system. Regular files (ASCII and binary) store user data, directory files organize the file system hierarchy, and character special files provide an interface to hardware I/O devices. Understanding these structures is essential for effective file system management.

Priority Scheduling (Non-Preemptive) - Average WT and TAT

Step 1 - Extract: Given Data

Priority 1 = highest. Assume non-preemptive priority scheduling.

Step 2 - Solve

Execution Order

• t = 0: Only A available → A runs 0 to 3.
• t = 3: Ready = B (P3), C (P2), D (P1). Highest priority = D → D runs 3 to 5.
• t = 5: Ready = B (P3), C (P2). Higher priority = C → C runs 5 to 9.
• t = 9: Only B remains → B runs 9 to 11.

Gantt Chart

| A | D |  C  | B |
0   3   5     9  11

Completion, Turnaround, Waiting Times

TAT = CT − AT, WT = TAT − BT

Averages

$$\text{Avg TAT} = \frac{3 + 9 + 6 + 2}{4} = \frac{20}{4} = 5 \text{ ms}$$

$$\text{Avg WT} = \frac{0 + 7 + 2 + 0}{4} = \frac{9}{4} = 2.25 \text{ ms}$$

Final Result

Short Notes: Virtual Memory and Race Condition

a. Virtual Memory (2.5 marks)

Virtual Memory is a memory management technique in which the operating system uses a portion of the hard disk as an extension of RAM, thereby increasing the effective size of usable memory beyond the physical RAM available.

Key Concepts:

• When the kernel needs memory for a new process but RAM is full, it writes the contents of a currently unused block of memory to the hard disk. This process is called swapping out.
• When the original contents are needed again, they are read back into memory (swapped in).
• The portion of the hard disk used for this purpose is called swap space.

Working Mechanism:

1. A segment number is used to find the segment descriptor.
2. A check is made whether the segment's page table is in memory; if not, a segment fault occurs.
3. The page table entry for the requested virtual page is examined; if the page is not in memory, a page fault is triggered.
4. If the page is in memory, the main memory address is extracted from the page table entry.
5. The offset is added to the page origin to give the final main memory address, and the read/write takes place.

Advantages and Disadvantages:

In Linux, swap space can be a swap partition (faster) or a swap file within the normal file system.

b. Race Condition (2.5 marks)

A Race Condition is a situation that occurs when two or more processes (or threads) read or write some shared data concurrently, and the final result depends on the precise order in which the processes execute.

Key Points:

• Race conditions typically occur inside a critical section, where multiple threads access shared resources.
• The result of execution differs according to the order in which threads or processes run, making the output unpredictable and incorrect.

Example Scenario:

• Two processes share a common variable (e.g., a counter).
• Process A reads the value, and before it writes back the updated value, Process B also reads the same old value.
• Both processes write their result, and one update is lost, producing an incorrect final value.

Illustration:

Shared variable: count = 5

Process A: reads count (5), computes count+1 = 6
Process B: reads count (5), computes count+1 = 6   <-- reads before A writes
Process A: writes count = 6
Process B: writes count = 6   <-- should be 7, but is 6 (incorrect!)

Prevention:

Race conditions can be prevented using synchronization mechanisms such as:

• Mutex locks
• Semaphores
• TSL (Test and Set Lock) instruction -- a shared lock variable is set to 1 before entering the critical section and reset to 0 after leaving, ensuring mutual exclusion.

In summary, race conditions arise due to uncontrolled concurrent access to shared data, and must be carefully managed to ensure correctness of programs.