Instruc!ons
You can take this quiz mul”ple “mes and the highest score will be kept. It must be completed before the due date for credit.
In this homework, you will study how file system state changes as various opera”ons take place. The file system begins in an empty state, with just a root directory. As the simula”on takes place, various opera”ons are performed, thus slowly changing the on-disk state of the file system.
The possible opera”ons are:
– mkdir() – creates a new directory
– creat() – creates a new (empty) file
– open(), write(), close() – appends a block to a file – link() – creates a hard link to a file
– unlink() – unlinks a file (removing it if linkcnt==0)
To understand how this homework func”ons, you must first understand how the on-disk state of this file system is represented. The state of the file system is shown by prin”ng the contents of four different data structures:
inode bitmap – indicates which inodes are allocated inodes – table of inodes and their contents
data bitmap – indicates which data blocks are allocated data – indicates contents of data blocks
The bitmaps should be fairly straigh$orward to understand, with a 1 indica”ng that the corresponding inode or data block is allocated, and a 0 indica”ng said inode or data block is free.
The inodes each have three fields: the first field indicates the type of file (e.g., f for a regular file, d for a directory); the second indicates which data block belongs to a file (here, files can only be empty, which would have the address of the data block set to -1, or one block in size, which would have a non-nega”ve address); the third shows the reference count for the file or directory. For example, the following inode is a regular file, which is empty (address field set to -1), and has just one link in the file system:
[f a:-1 r:1]
If the same file had a block allocated to it (say block 10), it would be shown as follows: [f a:10 r:1]
If someone then created a hard link to this inode, it would then become:
[f a:10 r:2]
Finally, data blocks can either retain user data or directory data. If filled with directory data, each entry within the block is of the form (name, inumber), where “name” is the name of the file or directory, and “inumber” is the inode number of the file. Thus, an empty root directory looks like this, assuming the root inode is 0:
[(.,0) (..,0)]
If we add a single file “f” to the root directory, which has been allocated inode number 1, the root directory contents would then become:
[(.,0) (..,0) (f,1)]
If a data block contains user data, it is shown as just a single character within the block, e.g., “h”. If it is empty and unallocated, just a pair of empty brackets ([]) are shown.
An en”re file system is thus depicted as follows:
inode bitmap 11110000
inodes [d a:0 r:6] [f a:1 r:1] [f a:-1 r:1] [d a:2 r:2] [] … data bitmap 11100000
data [(.,0) (..,0) (y,1) (z,2) (f,3)] [u] [(.,3) (..,0)] [] …
This file system has eight inodes and eight data blocks. The root directory contains three entries (other than “.” and “..”), to “y”, “z”, and “f”. By looking up inode 1, we can see that “y” is a regular file (type f), with a single data block allocated to it (address 1). In that data block 1 are the contents of the file “y”: namely, “u”. We can also see that “z” is an empty regular file (address field set to -1), and that “f” (inode number 3) is a directory, also empty. You can also see from the bitmaps that the first four inode bitmap entries are marked as allocated, as well as the first three data bitmap entries.
A!empt History
A”empt KEPT A!empt 2
LATEST A!empt 2 A!empt 1
Take the Quiz Again
Time
less than 1 minute less than 1 minute 3 minutes
Score
12 out of 12 12 out of 12 6 out of 12
Score for this a!empt: 12 out of 12 Submi!ed Apr 19 at 2:42am
This a!empt took less than 1 minute.
Ques!on 1
2 / 2 pts
Assume the ini”al state of the file system is:
inode bitmap 10000000 inodes [d a:0 r:2] [] [] [] [] [] [] [] data bitmap 10000000
data [(.,0) (..,0)] [] [] [] [] [] [] []
If the file system transi”ons to:
inode bitmap 11000000
inodes [d a:0 r:3] [d a:1 r:2] [] [] [] [] [] [] data bitmap 11000000
data [(.,0) (..,0) (t,1)] [(.,1) (..,0)] [] [] [] [] [] []
What opera”on must have been performed?
create(“/t”); fd=open(“/t”); write(fd); link(“/t”, “/”); mkdir(“/t”);
Correct!
Ques!on 2
2 / 2 pts
What opera”on must be performed next for the file system to transi”on to:
inode bitmap 11100000
inodes [d a:0 r:4] [d a:1 r:2] [f a:-1 r:1] [] [] [] [] [] data bitmap 11000000
data [(.,0) (..,0) (t,1) (y,2)] [(.,1) (..,0)] [] [] [] [] [] []
mkdir(“/y”); create(“/y”); mkdir(“/t/y”); create(“/t/y”);
Correct!
Ques!on 3
2 / 2 pts
What opera”on must be performed next for the file system to transi”on to:
inode bitmap 11100000
inodes [d a:0 r:4] [d a:1 r:3] [f a:-1 r:2] [] [] [] [] [] data bitmap 11000000
data [(.,0) (..,0) (t,1) (y,2)] [(.,1) (..,0) (c,2)] [] [] [] [] [] []
mkdir(“/t/c”); create(“/t/c”); link(“/y”, “/t/c”); link(“/y”, “/c”); create(“/c”);
Correct!
Ques!on 4
2 / 2 pts
What opera”on must be performed next for the file system to transi”on to:
inode bitmap 11100000
inodes [d a:0 r:4] [d a:1 r:3] [f a:2 r:2] [] [] [] [] []
data bitmap 11100000
data [(.,0) (..,0) (t,1) (y,2)] [(.,1) (..,0) (c,2)] [o] [] [] [] [] []
fd=open(“/t/c”); write(fd); fd=open(“/t/y”); write(fd); link(“/t”, “/t/c”); create(“/t/c”); mkdir(“/t/c”);
Correct!
Ques!on 5
1 / 1 pts
What opera”on must be performed next for the file system to transi”on to:
inode bitmap 11110000
inodes [d a:0 r:5] [d a:1 r:3] [f a:2 r:2] [d a:3 r:2] [] [] [] []
data bitmap 11110000
data [(.,0) (..,0) (t,1) (y,2) (v,3)] [(.,1) (..,0) (c,2)] [o] [(.,3) (..,0)] [] [] [] []
create(“/v”);
link(“/”, “/v”); fd=open(“/y”); write(fd); mkdir(“/v”);
Correct!
Ques!on 6
1 / 1 pts
What opera”on must be performed next for the file system to transi”on to:
inode bitmap 11111000
inodes [d a:0 r:6] [d a:1 r:3] [f a:2 r:2] [d a:3 r:2] [d a:4 r:2] [] [] []
data bitmap 11111000
data [(.,0) (..,0) (t,1) (y,2) (v,3) (j,4)] [(.,1) (..,0) (c,2)] [o] [(.,3) (..,0)] [(.,4) (..,0)] [] [] []
mkdir(“/t/j”); mkdir(“/j”); create(“/j”); create(“/t/j”);
Correct!
Ques!on 7
2 / 2 pts
What opera”on must be performed next for the file system to transi”on to:
inode bitmap 11111000
inodes [d a:0 r:6] [d a:1 r:2] [f a:2 r:1] [d a:3 r:2] [d a:4 r:2] [] [] []
data bitmap 11111000
data [(.,0) (..,0) (t,1) (y,2) (v,3) (j,4)] [(.,1) (..,0)] [o] [(.,3) (..,0)] [(.,4) (..,0)] [] [] []
mkdir(“/t”); create(“/t/c”); unlink(“/t”); unlink(“/t/c”);
Correct!