GATE IT 2005 | Question: 63

Question

In a computer system, four files of size $11050$ bytes, $4990$ bytes, $5170$ bytes and $12640$ bytes need to be stored. For storing these files on disk, we can use either $100$ byte disk blocks or $200$ byte disk blocks (but can't mix block sizes). For each block used to store a file, $4$ bytes of bookkeeping information also needs to be stored on the disk. Thus, the total space used to store a file is the sum of the space taken to store the file and the space taken to store the book keeping information for the blocks allocated for storing the file. A disk block can store either bookkeeping information for a file or data from a file, but not both.
What is the total space required for storing the files using $100$ byte disk blocks and $200$ byte disk blocks respectively?

• A. $35400$ and $35800$ bytes
• B. $35800$ and $35400$ bytes
• C. $35600$ and $35400$ bytes
• D. $35400$ and $35600$ bytes

Comments

Good question!
Had me stumped for 15 minutes since I had to verify my answers with options every single time and reach the answer somehow.

---

Oil independent from reddit 😺

---

@pranesh2003 Lol yeah.

Answer 1

for $100$ bytes block:

$11050 = 111$ blocks requiring $111 \times 4 = 444$ bytes of bookkeeping info which requires another $5$ disk blocks. So, totally $111 + 5 = 116$ disk blocks. Similarly,
$4990 = 50 + (50\times 4)/100 = 52$
$5170 = 52 + (52 \times 4)/100 = 55$
$12640 = 127 + (127 \times 4/100) = 133$
-----
$356 \times 100 = 35600$ bytes

For $200$ bytes block:

$56 + (56 \times 4/200) = 58$
$25 + (25 \times 4 / 200) = 26$
$26 + (26 \times 4 / 200) = 27$
$64 + (64 \times 4 / 200) = 66$
-----
$177 \times 200 = 35400$

So, (C) option.

Comments

We can not combine file data information and bookkeeping information together but we can combine all bookkeeping information combine together like

111*4=444

50*4=200

52*4=208

127*4=498

Now add up 444+200+208+498=1350/100=13.5=14

14 block use for bookkeeping

111+50+52+127+14=354*100=35400

The advantage of bookkeeping information combine together is there is no waste of space in block so why we can't solve in this way?

Please explain sir

---

@nihalSihare Your doubt is answered in the comments of the question itself. A block can have bookkeeping info of only one file but not more.Your reasoning is correct though that we will save some space.

---

While calculating number of 200 B blocks required for file of size 11050 B,the book keeping information is 224 B.number of 200 B blocks needed should be 3 .please explain.

Answer 2

"A disk block can store either bookkeeping information for a file or data from a file, but not both."

This means we must calculate the data blocks and the bookkeeping blocks completely separate from each other for each individual file.

Let us first set up the direct proportional mapping for Case 1, where the disk block size is 100 bytes.

A single data block contains only raw file data payload, giving a direct 1:1 capacity ratio:

$$1 \text{ data block} \longrightarrow 100 \text{ bytes of file data}$$

Using this ratio, the number of data blocks needed for each file size is calculated using $\lceil \frac{\text{File Size}}{100} \rceil$:

File 1 (11050 B): $\lceil 11050 / 100 \rceil = 111 \text{ blocks}$

File 2 (4990 B): $\lceil 4990 / 100 \rceil = 50 \text{ blocks}$

File 3 (5170 B): $\lceil 5170 / 100 \rceil = 52 \text{ blocks}$

File 4 (12640 B): $\lceil 12640 / 100 \rceil = 127 \text{ blocks}$

$$\text{Total Data Blocks} = 111 + 50 + 52 + 127 = 340 \text{ blocks}$$

Every individual data block requires 4 bytes of bookkeeping info. Since one tracking block can hold a maximum of 25 entries ($100 \text{ B} / 4 \text{ B}$), we establish our second proportional mapping:

$$1 \text{ bookkeeping block} \longrightarrow 25 \text{ data blocks tracked}$$

Dividing the data block count of each file by 25 gives the required dedicated bookkeeping blocks ($\lceil \frac{\text{Data Blocks}}{25} \rceil$):

File 1: $\lceil 111 / 25 \rceil = 5 \text{ bookkeeping blocks}$

File 2: $\lceil 50 / 25 \rceil = 2 \text{ bookkeeping blocks}$

File 3: $\lceil 52 / 25 \rceil = 3 \text{ bookkeeping blocks}$

File 4: $\lceil 127 / 25 \rceil = 6 \text{ bookkeeping blocks}$

$$\text{Total Bookkeeping Blocks} = 5 + 2 + 3 + 6 = 16 \text{ blocks}$$

Summing both block groups and multiplying by the 100-byte block capacity yields the total disk footprint for Case 1:

$$\text{Total Space (100B)} = (340 + 16) \times 100 \text{ bytes} = 35600 \text{ bytes}$$

Now let us apply the same direct proportional mapping for Case 2, where the disk block size is 200 bytes.

A single data block contains only raw file data payload:

$$1 \text{ data block} \longrightarrow 200 \text{ bytes of file data}$$

Using this ratio, the number of data blocks required is calculated using $\lceil \frac{\text{File Size}}{200} \rceil$:

File 1 (11050 B): $\lceil 11050 / 200 \rceil = 56 \text{ blocks}$

File 2 (4990 B): $\lceil 4990 / 200 \rceil = 25 \text{ blocks}$

File 3 (5170 B): $\lceil 5170 / 200 \rceil = 26 \text{ blocks}$

File 4 (12640 B): $\lceil 12640 / 200 \rceil = 64 \text{ blocks}$

$$\text{Total Data Blocks} = 56 + 25 + 26 + 64 = 171 \text{ blocks}$$

One tracking block can hold a maximum of 50 entries ($200 \text{ B} / 4 \text{ B}$):

$$1 \text{ bookkeeping block} \longrightarrow 50 \text{ data blocks tracked}$$

Dividing the data block counts by 50 gives the dedicated bookkeeping block counts ($\lceil \frac{\text{Data Blocks}}{50} \rceil$):

File 1: $\lceil 56 / 50 \rceil = 2 \text{ bookkeeping blocks}$

File 2: $\lceil 25 / 50 \rceil = 1 \text{ bookkeeping block}$

File 3: $\lceil 26 / 50 \rceil = 1 \text{ bookkeeping block}$

File 4: $\lceil 64 / 50 \rceil = 2 \text{ bookkeeping blocks}$

$$\text{Total Bookkeeping Blocks} = 2 + 1 + 1 + 2 = 6 \text{ blocks}$$

Summing both block groups and multiplying by the 200-byte block capacity yields the total disk footprint for Case 2:

$$\text{Total Space (200B)} = (171 + 6) \times 200 \text{ bytes} = 35400 \text{ bytes}$$

Correct Option: C

Answer 3

answer is C