• Bilkent University

• CS 342

342 Spring 2012

Homework 3 Solutions

Assigned: 27.04.2012

Due date: 04.05.2012

Question 1. Assume we have a file system that is using i-nodes to store the attributes and

block addresses of files. Assume the block size is 8 KB in the file system. Assume the i-node

of a file can store 10 disk block addresses, one single indirect block address, one double

indirect block address, and one triple indirect block address. Assume a disk block address

occupies 8 bytes of storage. What is the approximate maximum size (in bytes) a file can have

in this system?

In a single block, we can have 8 KB / 8 = 1024 pointers.

Max file size = (10 + 1024 + 10242 + 10243) x 8192 bytes =~ 8.8 TB.

Question 2: Assume we have a small disk with a file system that is using FAT (file allocation

table) approach in keeping track of blocks allocated to files. Assume the following is the

status of the FAT currently.

012345

14

6 13

7 10

8 -

9

10 6

11 -

12 5

13 11

14 8

15

Assume there are two files created in the system: File A and File B. File A starts at disk block

12, and File B starts at disk block 7. Assume all disk blocks allocated to a file are full with file

data.

Assume disk block size is 4 KB (4096 bytes).

Answer the following questions based on this information.

a) What is the size of File A in Kilobytes (KB)? How many disk blocks are allocated to File

B?

4 blocks are allocated to file A. Its size is 16 KB.

5 blocks are allocated to file B.

1

b) On which disk block sits the Byte 11000 (this is file offset) of File B. What is the offset in

that disk block?

Block allocated file B are: 7 10 6 13 11.

11000 = 2 x 4096 + 2808. Relative block number is 2. It is on disk block 6. Hence the offset

11000 is disk block 6. The disk block offset is 2808.

c) Which disk blocks should be accessed if we want to access bytes 5000 to 15000 of file A?

File blocks allocated to file A are: 12 5 14 8.

5000 = 1x4096 + 904.

15000 = 3x4096 + 2712.

The following blocks and bytes in those blocks need to be accessed:

Disk block 5, bytes 904..4095

Disk block 14, bytes 0..4095

Disk block 8, bytes 0..2712

Question 3. Assume we have a disk of size 32 GB. The block size is 4 KB. There are 200000

files in the disk and the average file size is 11000 bytes (i.e, on the average a file has 3 data

blocks allocated). FCB size is 256 bytes. Directory entry size is fixed and is also 256 bytes.

Answer the followings questions based on this information. Assume a bitvector is kept to

keep track of the free blocks on the disk. You can assume that we have a single directory in

the system.

a) How many blocks are there in the disk?

32 GB / 4 KB = 235 / 212 = 223 = 8M blocks.

b) Approximately how many disk blocks are required to keep the bitvector (bitmap)?

223 / 8 / 4 KB = 223 / 215 = 28 = 256 disk blocks.

c) Approximately how many disk blocks are required to keeps the FCBs? Note that a

disk block can keep several FCBs.

There are 200000 files, hence that many FCBs. A block can hold 4 KB / 256 bytes = 16

FCBs. 200000 / 16 = 12500 disk blocks.

d) Approximately how many disk blocks are required to keep the directory information?

Note that a disk block is large enough to keep several entries.

A disk block can keep 4 KB / 256 bytes = 16 entries. There are 200000 entries required.

Hence we need 200000/16 = 12500 disk blocks required to keep directory information. We

are assuming that we have a single directory in the system.

e) Approximately how much disk space (in blocks and also in bytes) is free. What

percent of disk is full now?

Average file size is 11000 bytes, that means 3 blocks. There are 200000 files, hence they

occupy 600000 blocks.

Total number of used blocks is: 600000 + 256 + 12500 + 12500 = 625256 blocks.

That makes 625256 x 4096 = 2561048576 bytes = 2.38 GB.

Total number of blocks: 8 M = 8388608.

Full percentage = (625256 / 8388608) x 100 = ~ 7.5 % of the disk is full.

Question 4. Assume we have a 1024 KB memory space that can be used for dynamic storage

allocations. The allocation algorithms is Buddy System algorithm. What would be the state of

this memory after we allocate space for the following requests: 30 KB, 120 KB, 16 KB, 55