Shell, System Call, and Disk Scheduling

Part 1: Definitions

Shell

A shell is a command interpreter that provides the interface between the user and the operating system kernel. It accepts user commands, interprets them, and hands them to the OS for execution. It also lets users run programs, manage files, and control processes. Examples: Bash, sh, csh, zsh.

System Call

A system call is the programmatic interface through which a user process requests a service from the OS kernel. It transfers control from user mode to kernel mode for privileged operations. Examples: fork(), exec(), read(), write(), open().

Part 2: Disk Scheduling

Given data:

• Cylinders: 201 (numbered 0 to 200)
• Head start: 95
• Queue (arrival order): 82, 170, 43, 140, 24, 16, 190

1. FCFS

Order: $95 \to 82 \to 170 \to 43 \to 140 \to 24 \to 16 \to 190$

$$|95-82|+|82-170|+|170-43|+|43-140|+|140-24|+|24-16|+|16-190|$$ $$= 13+88+127+97+116+8+174 = \boxed{623}$$

2. SSTF

Order: $95 \to 82 \to 43 \to 24 \to 16 \to 140 \to 170 \to 190$

$$13+39+19+8+124+30+20 = \boxed{253}$$

3. SCAN (moving up toward 200)

Sorted: $16, 24, 43, 82, [95], 140, 170, 190$

Order: $95 \to 140 \to 170 \to 190 \to 200 \to 82 \to 43 \to 24 \to 16$

$$45+30+20+10+118+39+19+8 = \boxed{289}$$

Total = $(200-95) + (200-16) = 105 + 184 = 289$ ✓

4. C-SCAN (moving up toward 200, then wrap to 0)

Order: $95 \to 140 \to 170 \to 190 \to 200 \to 0 \to 16 \to 24 \to 43 \to 82$

$$45+30+20+10+200+16+8+19+39 = \boxed{387}$$

Summary

Answer

Two Demerits of Disabling Interrupts for Mutual Exclusion

According to the notes, the following are two demerits of disabling interrupts to achieve mutual exclusion:

1. Unsafe to give power to user processes: It is unwise to give user processes the power to turn off interrupts. If a user process disables interrupts and never re-enables them, the entire system could come to a halt. This makes the approach unsuitable for general user-level processes.

2. Not appropriate for user processes: Disabling interrupts is only a useful technique within the operating system itself. It is not appropriate for user processes because a malfunctioning or malicious process could permanently disable interrupts, causing the system to stop functioning correctly.

Fixed and Variable Partitioning

In a multiprogramming environment, several programs reside in primary memory at the same time and the CPU switches control between them. One way to support multiprogramming is to divide main memory into several partitions, each allocated to a single process. Depending on how and when partitions are created, there are two types:

(i) Fixed Partitioning (Static Partitioning)

• Memory is divided into several fixed-size partitions before execution begins.
• Each partition can accommodate only one program at a time.
• The number of programs residing in memory is bounded by the number of partitions.
• When a program terminates, its partition is freed for another program waiting in the queue.
• When a job arrives, it is placed in the input queue for the smallest partition large enough to hold it.

Demerit: Since partitions are fixed in size, any unused space within a partition cannot be used by other jobs and is simply wasted while that job runs. This is known as internal fragmentation.

(ii) Variable Partitioning (Dynamic Partitioning)

• Partitions are not fixed in advance; they are created dynamically at the time a process is loaded into memory.
• Each process is allocated exactly as much memory as it requires, so there is no internal fragmentation.
• As processes finish and leave memory, holes (free blocks) are created at various places in memory.
• Over time, memory becomes fragmented into many small holes scattered throughout, which is known as external fragmentation.
• Techniques such as compaction may be used to combine these holes into one large free block.

Demerit: External fragmentation occurs over time, making it difficult to allocate contiguous memory to new processes without compaction.

Comparison Table

SRTN and SJF Scheduling - Average Waiting Time

STEP 1 - Given Data

All required data present.

STEP 2 - SOLVE

Part 1: SRTN (Shortest Remaining Time Next) - Preemptive

At each new arrival, compare remaining times and run the smallest.

Execution Trace

• t=0: Only P0. Run P0.
• t=2: P1 arrives (4). P0 remaining = 5. Since 4 < 5, run P1. (P0 rem = 5)
• t=4: P2 arrives (1). P1 remaining = 2. Since 1 < 2, run P2. (P0=5, P1=2)
• t=5: P2 finishes. P3 arrives (4). Ready: P1=2, P3=4, P0=5. Run P1.
• t=7: P1 finishes. Ready: P3=4, P0=5. Run P3.
• t=11: P3 finishes. Run P0 (5 remaining).
• t=16: P0 finishes.

Note: at $t=4$ the remaining time for P1 is $4 - 2 = \mathbf{2}$ units, since P1 ran from $t=2$ to $t=4$.

Gantt Chart

| P0 | P1 | P2 | P1 | P3 | P0  |
0    2    4    5    7   11   16

Waiting Time (WT = Completion - Arrival - Burst)

$$\text{Average WT (SRTN)} = \frac{9 + 1 + 0 + 2}{4} = \frac{12}{4} = \boxed{3.0 \text{ ms}}$$

Part 2: SJF (Shortest Job First) - Non-Preemptive

• t=0: Only P0 arrived. Run P0 to completion → finishes at 7.
• t=7: P1(4), P2(1), P3(4) all arrived. Shortest = P2. Run P2 → finishes at 8.
• t=8: P1(4), P3(4). Tie broken by arrival → P1. Finishes at 12.
• t=12: P3 runs → finishes at 16.

Gantt Chart

| P0      | P2 | P1     | P3     |
0         7    8       12      16

Waiting Time

$$\text{Average WT (SJF)} = \frac{0 + 6 + 3 + 7}{4} = \frac{16}{4} = \boxed{4.0 \text{ ms}}$$

Summary