Official PYQ · 1997Q74I/O SchedulingNAT1 mark

GATE CS 1997 Q74 — I/O Scheduling

A program $P$ reads and processes $1000$ consecutive records from a sequential file $F$ stored on device $D$ without using any file system facilities. Given the following

Size of each record $= 3200$ bytes
Access time of $D = 10$ msecs
Data transfer rate of $D = 800 \times 10^3$ bytes/second
CPU time to process each record $= 3$ msecs

What is the elapsed time of $P$ if

$F$ contains unblocked records and $P$ does not use buffering?
$F$ contains unblocked records and $P$ uses one buffer (i.e., it always reads ahead into the buffer)?
records of $F$ are organized using a blocking factor of $2$ (i.e., each block on $D$ contains two records of $F$ ) and $P$ uses one buffer?

View worked solution

Answer: 9.006

First, let us calculate the basic parameters for a single record:

Record size: $3200$ bytes
Transfer rate: $800 \times 10^3$ bytes/sec = $800,000$ bytes/sec
Transfer time for 1 record: $\frac{3200}{800,000} = 0.004\text{ seconds} = 4\text{ ms}$
Access time: $10\text{ ms}$
Total I/O time for 1 record: $10\text{ ms} + 4\text{ ms} = 14\text{ ms}$
CPU processing time for 1 record: $3\text{ ms}$

Now, we evaluate each case:

Case A: Unblocked records, no buffering
Since there is no buffering, I/O and CPU processing happen sequentially for each of the $1000$ records:
$\text{Total time} = 1000 \times (14\text{ ms} + 3\text{ ms}) = 17,000\text{ ms} = 17\text{ seconds}$

Case B: Unblocked records, one buffer (read-ahead)
With one buffer, the CPU processes the current record while the next record is being read in parallel:
$\text{Total time} = \text{Read 1st record} + 999 \times \max(\text{Read time}, \text{CPU time}) + \text{Process last record}$
$\text{Total time} = 14\text{ ms} + 999 \times \max(14, 3)\text{ ms} + 3\text{ ms} = 14 + 999 \times 14 + 3 = 14,003\text{ ms} = 14.003\text{ seconds}$

Case C: Blocking factor of 2, one buffer
Each block contains $2$ records.

Number of blocks: $\frac{1000}{2} = 500$ blocks
Block size: $2 \times 3200 = 6400$ bytes
Transfer time for 1 block: $\frac{6400}{800,000} = 8\text{ ms}$
Total I/O time for 1 block: $10\text{ ms} + 8\text{ ms} = 18\text{ ms}$
CPU processing time for 1 block (2 records): $2 \times 3\text{ ms} = 6\text{ ms}$