GATE CSE 1997 | Question: 74

Question

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

• A. $F$ contains unblocked records and $P$ does not use buffering?

• B. $F$ contains unblocked records and $P$ uses one buffer (i.e., it always reads ahead into the buffer)?

• C. 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?

Comments

in part (a) ....why we access 1000 times device D.why not only one time.

i mean P=10+1000*3+4000 msec ????? 

---

(I am talking in regard to part C of question) I didn't able to understand that what is meaning of "P uses one buffer" ,according to my thinking it means that we can store one next record while current record is processed by cpu. But according to @Ayush sir's answer, we can store even next two records in buffer (i am saying it because according to @Ayush sir, during 6ms when cpu is processing two records consecutively, next records keep buffering in P. Time taken to buffer one record is 4ms, so in 6ms time, next 2nd record is also start buffering in P ).  

Please clarify my doubt. @Ayush sir, @Arjun sir, @Bikram sir, @Sachin sir and @Ankitgupta1729 sir.

Answer 1

• $1000$ consecutive records
• Size of $1$ record $= 3200$ Bytes
• Access Time of device $D = 10$ms
• Data Transfer Rate of device $D = 800\ast 10^3$ Bytes per second.
• CPU time to process Each record $= 3$ms.
• Time to transfer $1$ record $(3200 \;\text{Bytes})=\frac{3200\;\text{Bytes}}{800\ast 10^3} = 4$ms

(A) Unblocked records with No buffer. Hence, each time only when a record is fetched in its full entirety it will be processed.

Time to fetch $=$ Access Time for $D($Every time you'll access the device. This is also known as device latency$) +($Data transfer time)

$=10\text{ms} + 4\text{ms} = 14\text{ms}$

Total time taken by CPU for each record $=$ fetch $+$ execute $=14\text{ms} + 3\text{ms} = 17\text{ms}$

Total time for program $p=1000\ast 17\text{ms} = 17\text{sec}$ 

(B) Unblocked records and $1$ buffer. Records will be accessed one by one and for each record fetched into the buffer, the device delay has to be taken into account.

Time to bring one record into buffer $=10 + 4 = 14$ms.

Now let us see how the program goes.

• At $t=0$ms, the program starts and the buffer is empty.
• At $t=14$ms, $R_1$ fetched into the buffer and CPU starts processing it.
• At $t=17$ms, cpu has processed $R_1$ and waiting for more records.
• At $t=28$ms, buffer gets filled with $R_2$ and CPU starts processing it.

To get the Total time of the program we think in terms of the last record because when it is processed, all others would already have been processed too!.

Last record $R_{1000}$ would be fetched at $t=0+14\ast 1000=14000$ms and $3$ms will be taken by CPU to process this.

So, total elapsed time of program $P=14000+3=14003\text{ms} = 14.003\text{sec}$

(C) Each disk block contains $2$ records and Assuming buffer can hold $1$ disk block at a time.

So, $1$ Block Size $=2\ast 3200=6400$Bytes

Time to read a block $=\frac{6400}{800\ast 10^3} = 8$ms.

Each block read you have to incur the device access cost.

So, the total time to fetch one block and bring it into buffer $= 10 + 8 = 18$ms.

We have $1000$ files and so we need to read in $500$ blocks.

Each block has two records and therefore CPU time per block $= 6$ms.

Again to count the program time $P,$ we think in terms of the last Block.

Last block would be fetched at $t=0+(18\ast 500)=9000$ms.

After this $6$ ms more to process $2$ records present in the $500^{\text{th}}$ block.

So, program time $P=9000+6=9006\text{ms} = 9.006\text{sec}$.

Comments

Best Answer

---

The below diagram can help in understanding how buffer works here:

---

phenomenal approach .

Answer 2

here Access time $= 10ms$
     Process each Record $= 3ms$
     Transfer time $= 3200/800 \times 10^3 = 4ms$

• A. Elapsed time $=$ ( Access time $+$ Transfer time $+$ processing time) $\times$ number of records
                    $(10+4+3)\times 1000 =17000 \ ms = 17 \ sec$
• B. In this case $P$ uses one ' Read ahead' buffer the processing and transferring of records can be overlapped
     "Processing time is less than transfer time."
                  Elapsed time $=$ ( Access time $+$ Transfer time) $\times$ number of records
                               $= (10+4)\times 1000 = 14 \ sec$
• C. In this case each block contain two records so we can access $500$ time to transfer $1000$ records.
                  Elapsed time $=$ ( Access time $+$ Transfer time) $\times$ number of records
                               $= (10+4+4) \times 500 = 9 \ sec$

Comments

For part (b)

Say, at t=0, fetching for R1 begins

At t=4msec, R1 is fetched into the buffer and sent to CPU immediately for processing.

At t=4+3=7msec, R1 is processed and CPU is idle.

At t=4+4=8msec, R2 is fetched into the buffer and now sent to CPU for processing.

At t=8+3=11 msec finally, all records of the file processed.

Similarly, for part (b) last 3msec should be added to answer to get 14.003 sec.

For part (c)

Say at t=4+4= 8 msec, 1st block of the file is fetched into the buffer and sent to CPU for processing.

At t=8+(2*3)=14msec, 1st block of the file processed successfully and CPU is idle.

At t=8+(4*2)=16msec, the second block of file fetched into the buffer and sent to CPU.

At t=16+6=22msec, finally, all records processed.

So similarly last 6msec should be added to the final answer to get 9.006msec as the answer.

---

nice explanation @umang raman

---

@Bikram

 

in B part why we are not  add first  processing time . first time buffer not using 

according to  me 14sec + 3ms