Feedback to HW8

Aurora December 1, 2016

In this solution, denote Int1 with i1 and Int2 with i2.

1. Harolds Personal Files

   1. Least blocks accessed

      Fetch inode of root dir → content block of root dir

      → Fetch inode of 1st dir → content block of 1st dir

      → Fetch inode of 2nd dir → content block of 2nd dir

      …

      → Fetch inode of i1 mod 3 + 2-th dir → content block of i1 mod 3 + 2-th dir

      → Fetch inode of file → first block of file # Total blocks = (i1 mod 3 + 4) · 2

   2. Most blocks accessed

      # Total blocks = (i1 mod 3 + 3) · 5 + 2

2. Fat Fast File System

   1. Largest file with direct pointers

      12 + i1 mod 3 direct pointer: 12 + i1 mod 3 blocks; File size:

      (12 + i1 mod 3) · (8 + (i2 mod 4))K

   2. Max file size supported

      12 + i1 mod 3 direct pointer: 12 + i1 mod 3 blocks;

      2 indirect pointer: 2 · (8 + (i2 mod 4)) · 1024/8 = 28 · (8 + (i2 mod 4)) blocks

      2 double indirect pointer: 2 · ((8 + (i2 mod 4)) · 1024/8)2 = 215 · (8 + (i2 mod 4))2 blocks 2 triple indirect pointer: 2 · ((8 + (i2 mod 4)) · 1024/8)3 = 222 · (8 + (i2 mod 4))3 blocks

      1 quadruple indirect pointer: ((8 + (i2 mod 4)) · 1024/8)4 = 228 · (8 + (i2 mod 4))4 blocks Total number of blocks:

      12 + i1 mod 3 + 28 · (8 + (i2 mod 4)) + 215 · (8 + (i2 mod 4))2

      + 222 · (8 + (i2 mod 4))3 + 228 · (8 + (i2 mod 4))4

      ”within %1”: ((8 + (i2 mod 4)) · 1024/8)4 = 228 · (8 + (i2 mod 4))4 blocks

      Total size of file: 228 · (8 + (i2 mod 4))5 KB = 256 · (8 + (i2 mod 4))5 GB

      Approximation:

      i2 mod 4 = 0: 28 · 85 = 8 PB

      i2 mod 4 = 1: 28 · 95 = 14.4 PB

      i2 mod 4 = 2: 28 · 105 = 24.4 PB

      i2 mod 4 = 3: 28 · 115 = 39.3 PB

3. Wasted Space

   1. Internal fragmentation

      folder name	#entries
      animal	3
      felidae	1
      rodent	2
      primate	2
      hominidate	1
      code-monkey	2
      hacker	1
      unknown	1

      Exp. i2 = 2, then block size is 10K bytes. Then fragmentation of folder:

      fragFolder = Σ (10 · 1024)B − number of entries in folder · 16B

      folders

      = 8 · 10 · 1024 − 16 · (3 + 1 + 2 + 2 + 1 + 2 + 1 + 1)

      = 81712B

      Fragmentation of file:

      fragFile = Σ internal fragmentation of each file

      files

      = 8K + 0 + 0 + 0 + 0 + 0

      = 8192B

      Total fragmentation: (bytes)

      81712 + 8192 = 89904

   2. Internal fragmentation with double block size

Exp. i2 = 2, then block size is 20K bytes.

Then fragmentation of folder:

fragFolder = Σ (10 · 1024)B − number of entries in folder · 16B

folders

= 8 · 20 · 1024 − 16 · (3 + 1 + 2 + 2 + 1 + 2 + 1 + 1)

= 163632B

Fragmentation of file:

fragFile = Σ internal fragmentation of each file

files

= 8K + 10K + 0 + 10K + 0 + 0

= 28672B

Total fragmentation: (bytes)

163632 + 28672 = 192304