Operating Systems 1

Tutorial 8 solutions

1. Name one problem with storing files as linked lists of blocks.

   • Random access is impossible (only suitable for serial access).
   • Blocks are no longer a round size. (For example, if blocks were 512 bytes on underlying device, and pointer size were 32-bits, effective size of disk blocks in a linked-list scheme is now 512-4 = 508 bytes, which is awkward.)

2. Name one problem with representing the free blocks on a disk as a linked list (free chain). And nominate an alternative approach.

   Problem: Chain is difficult to maintain in order, so it easily becomes fragmented (in the sense of 'not in order of block address', not in the sense of internal or external fragmentation). Thus when file blocks are allocated from the free chain, the files themselves become badly fragmented.

   Alternative approach: Store a bitmap on disk of free blocks. Can easily be used to identify unused blocks. Blocks are naturally allocated in order of block address, and so file fragmentation becomes less severe.

3. What is the overhead of a file allocation table (FAT) scheme of disk block allocation, as compared to the overhead of the simple linked list approach?

   Exactly the same space overhead (one pointer per block).

4. A particular 720K floppy uses 512byte blocks, and a FAT-based file system, with 12-bit FAT entries. How big will the FAT be in Kbytes? How many disk blocks will it occupy?

   Number of blocks = 720K ÷ ½K = 1440 blocks
   => size of FAT = #blocks × FAT entry size
   = 1440 × 12 bits
   = 17280 bits
   = 17280 bits ÷8 bits/byte = 2160 bytes = ~2.1Kbytes

   Occupies 2160÷512 = ~4.2 blocks
   => require 5 disk blocks to hold FAT.

5. Describe briefly how an indexed block allocation scheme works.

   With indexed block allocation scheme one stores a table which maps logical blocks in the file to physical blocks on the disk, (analagously to a page table, mapping virtual pages to physical frames in a paged memory system).

   One approach is to store the table directly in the directory entry/inode ('direct block index'). Alternatively the table may be stored in a disk block by itself ('indirect block index'), with the directory entry/inode referring to the index block.

   Two or more levels of indirection are also possible. UNIX uses a combined approach, with direct blocks for small files, and single, double or triple indirection for larger files.

6. A disk uses 2K blocks, 32-bit block pointers, and is formatted with a UNIX filesystem which makes use of double indirect blocks. To how much of a file (in bytes) may a double-indirect block refer? If each inode has room for 4 double indirect block pointers (only), what is the maximum size of a file in this system?

   Pointer size = 32÷ 8 bits/byte = 4bytes.
   # pointers per block = 2K ÷ 4 = 512 pointers/block.

   => Single indirect block references 512 × 2KB = 1MB

   => Double indirect block references 512 × 1MB = 512MB

   => 4 double indirect blocks reference 4 × 512MB = 2GB

7. What is the essential difference between a 'hard link' and a 'soft (symbolic) link'?

   Hard links are based on inode number. With hard links, essentially there are many directory entries refering to the same file (represented by an inode). The file is not deleted, for example, until all hard links to it have been deleted.

   Soft links are based on file name. A soft link is a file which contains only a reference to another file. The 'other file' is the original. It may be deleted, leaving the soft link pointing at a non-existant file.