File Systems

Question 1

File Systems

[12pts] Choose 3 file layouts and show how each would represent a 44KB file in a system of 4KB blocks.

Answer 1

(a) Contiguous allocation - stores the beginning sector and a length of 44 kb

(b) FFS (fast file system)
10 direct pointers to 4kb of data each
One indirect pointer that has a reference to one more direct pointer to the last 4kb of data

(c) Direct allocation - stores 11 direct pointers to 11 different blocks from the inode itself.

Question 2

File Systems
You buy a new hard drive and format it as a Fast File System.

1. [4pts] Describe the layout of the disk before user files are added.

Answer 2

(a) Master Boot Record
(b) Partition Table
(c) Partitions

Each partition has:

(a) boot block
(b) key parameters of the file system (type, etc.)
(c) super block
(d) free space management
(e) inode bitmap
(f) root

Question 3

You buy a new hard drive and format it as a Fast File System.

2. [4pts] List the steps necessary to create a user file.

Answer 3

(1) Get the root inode
(2) Traverse the path from the root to the end directory
(3) Allocate a sector from the freemap and update the freemap
(4) Create the inode
(5) Update the inode bitmap
(6) Add the file entry to the end directory.

Question 4

File Systems
In class, we studied the Fast File System and NTFS.

1. NTFS is implemented as a flexible tree with extents.
   (a) [4pts] What is an extent?

Answer 4

An extent is a range of sectors belonging to a file

Question 5

(b) [6pts] Describe three ways in which the NTFS flexible tree can be used to represent files.

Answer 5

(a) Data is resident in the record
(b) Data is not resident in the record and there is use of records.
(c) The attribute list is not resident (extents are stored in a different records)

Question 6

2. The Fast File System is implemented as a multilevel indexed file system, which can efficiently access small files while also supporting larger files.

(a) [4pts] How does FFS store small files? You may assume a small file has a size of 40KB or
Less.

Answer 6

Stores them in the 10 direct blocks

Question 7

(b) [4pts] A file size limit is inherent in the design of FFS. Why?

Answer 7

The depth of the triply indirect block is what limits the file size in FFS.

Question 8

1. [3pts] Name three pieces of file metadata, stored in the file header.

Answer 8

Owner name, File Size, File Permissions

Question 9

2. Which filesystem(s) we studied (specific or type accepted):
   (a) [2pts] suffers from external fragmentation?

Answer 9

Contiguous

Question 10

2. Which filesystem(s) we studied (specific or type accepted):
   (b) [2pts] can hold a file large enough to fill the entire disk, no matter the disk’s size?

Answer 10

NTFS

Question 11

2. Which filesystem(s) we studied (specific or type accepted):
   (d) [2pts] writes all metadata changes to a log?

Answer 11

Journaling File System

Question 12

2. Which filesystem(s) we studied (specific or type accepted):
   (e) [2pts] uses direct and indirect pointers?

Answer 12

FFS

Question 13

2. Which filesystem(s) we studied (specific or type accepted):
   (f) [2pts] has a rigid file structure?

Answer 13

FFS

Question 14

2. Which filesystem(s) we studied (specific or type accepted):
   (g) [2pts] uses block groups?

Answer 14

FFS

Question 15

2. Which filesystem(s) we studied (specific or type accepted):
   (h) [2pts] copies data to a new location when that data changes on disk?

Answer 15

Copy-on-write file systems

Question 16

File Systems
1. File systems use a data structure called a file header.

(a) [3pts] What is the purpose of a file header?

Answer 16

Store metadata for the file

Question 17

(c) [2pts] What is a file header called in FFS?

Answer 17

Inode

Question 18

(d) [2pts] What is a file header called in NTFS?

Answer 18

File Record

Question 19

2. [3pts] Name another metadata structure in the file system.

Answer 19

Inode bitmap

Question 20

3. [4pts] Assume that the user has just saved her file page.c, and that save requires another data block to be appended to the file. What steps are required to append a data block to a file?

Answer 20

(1) Allocate a slot from the freemap
(2) Data block is allocated
(3) Data block is filled with data
(4) File header is updated and written back to disk

Question 21

4. [4pts] Assume a crash occurs during the steps of problem 3. Is there a possibility of a file
   system inconsistency? Defend your answer.
5. [4pts] Assume that the user has just saved her file page.c, and that save requires another data block to be appended to the file. What steps are required to append a data block to a file?

Answer 21

Yes, assuming there is no journaling, it’s possible that a spot could be allocated in the free map, but the system crashes and no data actually resides there

Question 22

Disks and File Systems

1. NTFS and FFS (and all of its descendents) have been carefully designed and optimized to
   take advantage of the technology that has been prevalent for most of their lifetimes: spinning,
   magnetic disks.
   (a) [4pts] Name two design features of FFS that exploit characteristics of the spinning disk.

Answer 22

Block groups,

Presents user with a smaller disk than is actually available

Question 23

(b) [2pts] Name one design feature of NTFS that exploits characteristics of the spinning disk.

Answer 23

Extents: exploit low cost of transfer time on continuous chunks of data

Question 24

2. One of the file systems we discussed (albeit briefly) was the copy-on-write file system.
   (a) [4pts] Why is this file system well-suited to an SSD? Give two reasons.

Answer 24

(a) By nature of writing all updates to new locations on the SSD, it does wear leveling automatically.
(b) Transforms random writes to sequential writes, offset cost of block erasure
(c) “COW techniques used to virtualize block addresses and redirect writes to cleared erasure blocks”

Question 25

(b) [4pts] One of the troubles of a copy-on-write file system is finding metadata, such as inodes.

Devise a strategy to find inodes on disk for a copy-on-write file system. You may assume that memory is plentiful.

Answer 25

Keep an inode table that keeps track of where all the inodes are

Question 26

Files and Directories

1. Some modern file systems store file data in extents.
   (a) [2pts] What is the benefit of an extent on a spinning disk?

Answer 26

Exploit low cost of transfer time on continuous chunks of data

Question 27

(b) [2pts] What is the benefit of an extent on a solid state drive?

Answer 27

Store less data in a files header

Question 28

2. Consider a file of size 512 bytes in an NTFS system, which has file records of size 1KB.
   (a) [3pts] How might that file data and metadata be stored if the metadata consists of 256
   Bytes?

Answer 28

The file data and metadata would be stored inside the file record itself (resident)

Question 29

(b) [3pts] How might that file data and metadata be stored if the metadata consists of 1,282
Bytes?

Answer 29

The data would be non-resident and stored in an extent

Question 30

3. Consider a directory in any filesystem.

(a) [2pts] Where is directory metadata stored?

Answer 30

In the directory file header

Question 31

(b) [2pts] How do you locate a file’s metadata in a directory, assuming you already have the data of the containing directory?

Answer 31

Lookup the sector associated with the target file name in the directory’s data.

Question 32

2. [4pts] You are a new hire in Lovely Software Development, Inc. On your first day of work, you
   are asked to choose a file system for the company server that will work well even in the presence of frequently created and deleted files. Which file system do you choose? Defend your answer.

Answer 32

FFS due to block groups and file headers being located in the same set of tracks as their data

Question 33

3. [4pts] You’ve done well on your first task and your manager is testing you with another task
   before they determine whether or not you should get a promotion. Your second task is to decide
   on what file system to use if you only need to support lots of very small files (approximately
   512 bytes) and desire the best possible performance. What would you choose? Defend your
   Answer.

Answer 33

NTFS, the very small files means the data could be in resident in the file record itself.

Question 34

4. Your manager is still not sure about your promotion, and so now she wants you to protect
   against an inconsistent filesystem.
   (a) [2pts] What makes a file system inconsistent?

Answer 34

When the system crashes and metadata structures are not in agreement over the data updates

Question 35

(b) [4pts] What would you do to prevent an inconsistent filesystem? Describe your algorithm.

Answer 35

Implement a journaling filesystem (write updates to a log on disk and commit) to help make sure data stays consistent (can roll back the log if needed)

Question 36

File Systems

1. [2pts] What is the name of the file metadata structure?

Answer 36

File header

Question 37

3. [4pts] Assume that a FFS-like file system is using 4KB blocks to store its files. In that system, a user writes an 11KB file. How many blocks would be allocated to the file? How would the system store the locations of those blocks?

Answer 37

3 direct pointers to data blocks

Question 38

4. [4pts] When this 11KB file was initially created, what steps did the OS complete in the create() system call to accomplish that task? You may assume that no data was initially allocated.

Answer 38

The create() system call allocates space for the file header, creates the new file header (metadata) for the file and updates the directory entry of the parent.

Question 39

5. [4pts] Now assume that create() chose inode 26 for this file, which is named foo bar.txt. What does this file’s directory entry look like?

Answer 39

[26 foo_bar.txt]