File System Implementation

Question 1

What are the 4 layers in the big picture of the file system?

Answer 1

Top: file-system interface
VFS interface
Local/Remote file system
Disk/network

Question 2

There are ___ aspects for implementing a file system

Answer 2

two

Question 3

The two aspects for implementing a file system are _____ ________ and ______ _______

Answer 3

data structures, access methods

Question 4

For file system data structures, there can be ________ data structures or _________ structures

Answer 4

On-disk, in-memory

Question 5

On-disk data structures hold the directory ______, number of ______, _______ of free blocks, _____ information, etc

Answer 5

structure, blocks, location, boot

Question 6

In-memory structures are for _______ file system at run-time and ________

Answer 6

managing, caching

Question 7

Access methods handle ____ made by processes to open, close, read, write, etc

Answer 7

calls

Question 8

We organize the disk by dividing it into ______

Answer 8

blocks

Question 9

Disk block sizes are ______

Answer 9

fixed

Question 10

Disk blocks are addressed from 0 to ____

Answer 10

N-1

Question 11

What are the two types of disk blocks?

Answer 11

Data blocks and metadata blocks

Question 12

Data blocks file actual ____

Answer 12

data

Question 13

Metadata blocks ________ data

Answer 13

manage

Question 14

What are example of metadata blocks?

Answer 14

inode, superblock, bitmaps, etc

Question 15

What are data regions?

Answer 15

It reserves blocks to store user data

Question 16

The file system has to track which data blocks track _____, size of ____, the file’s ______, etc

Answer 16

files, files, owner

Question 17

The file system has to reserve some space for a ______ table

Answer 17

inode

Question 18

An inode table is an _____ of on-disk inodes

Answer 18

array

Question 19

If the inode table occupies 5 4kb blocks, and the inode size is 256 byte, how many inodes does the file system contain?

Answer 19

80

Question 20

We can use ______ to track whether inodes or data blocks are free or allocated

Answer 20

bitmaps

Question 21

In a bit map, a 0 indicates ______ and 1 indicates _____

Answer 21

free, in-use

Question 22

A _____ bitmap tracks data regions and an ______ bitmap tracks inode regions

Answer 22

data, inode

Question 23

What does a superblock contain? Give examples

Answer 23

Necessary information for the particular file system. number of inodes, begin location of inode table, etc

Question 24

When mounting a file system, the OS will read the _________ first to initialize information

Answer 24

superblock

Question 25

Each inode is referred to by an inode _______

Answer 25

number

Question 26

We can calculate where the inode is on the disk with the inode _______

Answer 26

number

Question 27

To get the inode location, what two steps do we do?

Answer 27

1. Calculate offset into the inode region (inode #) * sizeof(inode) 2. Add start address of the inode table

Question 28

Disks are not byte addressable, but ______ addressable

Answer 28

sector

Question 29

On disk, the address advances by ______ size, which is typically ____ bytes

Answer 29

sector, 512

Question 30

If we need to fetch something at 20kb, the sectorSize would be __

Answer 30

40

Question 31

An inode contains ______ that stores information about actual file data

Answer 31

metadata

Question 32

The indoe may contain direct _______ to data blocks belonging to the file

Answer 32

pointers

Question 33

Since inode size is limited, the number of _______ is limited, and the ____ ____ is limited

Answer 33

pointers, file size

Question 34

Why do we use a multi-level index?

Answer 34

To store larger files

Question 35

REVIEW MULTI-LEVEL INDEX SLIDES

Answer 35

REVIEW MULTI-LEVEL INDEX SLIDES

Question 36

Contiguous allocation has each file occupy a set of contiguous _______

Answer 36

blocks

Question 37

In contiguous allocation, we only need the _____ _______ and length

Answer 37

start address

Question 38

What are two pros of contiguous allocation?

Answer 38

- Simple | - Efficient sequential and random access

Question 39

What are three cons of contiguous allocation?

Answer 39

- External fragmentation - Files may not be able to grow - Compaction is possible but expensive

Question 40

In linked allocation, a file is a _______ _____ of blocks

Answer 40

linked list

Question 41

In linked allocation, blocks can be anywhere and each block has a _______ to the next block

Answer 41

pointer

Question 42

In linked allocation, we need the _____ and ____ block and we must traverse the chain to reach the ________ block

Answer 42

start, end, desired

Question 43

What are three pros of linked allocation?

Answer 43

- Simple (only need 2 addresses) - Doesn't waste space - Support dynamically growing files

Question 44

What are two cons of linked allocation?

Answer 44

- Expensive random access | - Reliability

Question 45

What is the process that happens when we do open("/foo/bar")?

Answer 45

* Traverse the pathname and thus locate the desired inode * Begin at the root of the file system (/) * In most Unix file systems, the root inode number is 2 * Filesystem reads in the block that contains inode number 2 * Look inside of it to find pointer to data blocks (contents of the root) * By reading in one or more directory data blocks, It will find “foo” directory * Traverse recursively the path name until the desired inode(“bar”) * Check file permissions, allocate a file descriptor for this process and returns file descriptor to user

Question 46

When the inode is consulted for a read, we need to update the ______ _________ time and the file ______

Answer 46

last accessed, offset

Question 47

When we close a file, we need to _______ file descriptor, and use _____ to persist file data

Answer 47

deallocate, fsync

Question 48

Closing a file does not perform any disk ____

Answer 48

I/O

Question 49

write() may allocate new _______

Answer 49

blocks

Question 50

write() needs to update the data ______ and data _______

Answer 50

block, bitmap

Question 51

write() needs what 5 I/O operations?

Answer 51

1 to read data bitmap 1 to write to the bitmap 2 to read and then write the inode 1 to write the block itself

Question 52

In addition to the five I/Os required for write(), there could be more I/O required for file _______ and space allocation for _______ entry

Answer 52

creation, directory