Question

Consider an empty 1 Gbyte disk with the block size of 4096 bytes. When the disk is formatted blocks 0 is occupied for system-related information. The system always allocated free blocks starting st the lowest numbered block, and it uses non-contiguous allocation.

Question 6 (2, 4) Consider an empty 1 Gbyte disk with the block size of 4096 bytes. When the disk is formatted blocks 0 is occupied for system-related information. The system always allocates free blocks starting at the lowest numbered block, and it uses non-contiguous allocation. The following activities take place: 1. 2. 3. 4. File A is written, using 6 blocks File B is written, using 7 blocks File C is written, using 4 blocks File B is deleted a. Assuming that the free space on disk is maintained using a bitmap, this bitmap will at first look as follows: 1000 0000 0000 0000 0000... 0000 Show the bitmap after each of the activities 1- 4. b. Assuming that the free space on disk is maintained as a linked list show the entries for the first 10 free block after each of the activities 1- 4. Each entry should contain the following fields: block number, pointer to the next entry (expressed as the entry number) and pointer to the previous entry (also expressed as a number).

Answer 1

Disk size is 1GB =2^30 bytes and 4096 bytes = 2^12 bytes. Therefore the number of blocks available = 2^30/2^12 = 2^18 blocks(262144 blocks)

a. File a is written in 6 blocks. The first block0 is occupied for storing system-related information and the remaining blocks are free for allocation.

The bitmap 1000 0000 0000 0000 0000.....0000 denotes, for each block a bit is used to represent whether the block is occupied or free. If the bit is '1' then that block is occupied. If the bit is '0', then that block is free and available for allocation.

Therefore for the first activity : File A written using 6 blocks.

The bit map:

1111 1110 0000 0000 0000.....0000

The bits corresponding to blocks starting from 1 to 6 are made 1 in bitmap, as those blocks are occupied because of writting the file A in those blocks.

Second activity: File B written using 7 blocks

The bit map:

1111 1111 1111 1100 0000.......0000

The bits corresponding to blocks starting from 7 to 13 are made 1 in bitmap, as those blocks are occupued because of writting the file B in those blocks.

Third activity: File C written using 4 blocks

The bit map:

1111 1111 1111 1111 1100.......0000

The bits corresponding to blocks starting from 14 to 17 are made 1 in bitmap, as those blocks are occupied because of writting the file C in those blocks.

Fourth activity: File B is deleted

The bit map:

1111 1110 0000 0011 1100......0000

The bits corresponding to blocks starting from 7 to 13 are made 0 in bitmap, as those blocks are freed because of deleting the file B.

b. when free space on disk maintained as a linked list:

The first 10 free blocks after each activity:

First activity : File A written, using 6 blocks. Blocks 1 to 6 are used as shown above. Each entry correspond to each free block:

Block number	Next Entry	Previous Entry
7	8	-
8	9	7
9	10	8
10	11	9
11	12	10
12	13	11
13	14	12
14	15	13
15	16	14
16	17	15

Second activity: File B written using 7 blocks, blocks from 7 to13 are occupied in this activity

The first 10 free blocks after this activity starts from block 14 upto 23

Block Number	Next entry	previous entry
14	15	-
15	16	14
16	17	15
17	18	16
18	19	17
19	20	18
20	21	19
21	22	20
22	23	21
23	24	22

Third Activity: File C written using 4 blocks. The blocks 14 to 17 are used. Thus first 10 free blocks are from block 18 to 27.

Block number	Next Entry	Previous Entry
18	19	-
19	20	18
20	21	19
21	22	20
22	23	21
23	24	22
24	25	23
25	26	24
26	27	25
27	28	26

Fourth Activity: File B deleted. Thus blocks from 7 to 13 are freed. Therefore the first 10 free entries after this activity:

Block number	Next entry	Previous entry
7	8	-
8	9	7
9	10	8
10	11	9
11	12	10
12	13	11
13	18	12
18	19	13
19	20	18
20	21	19