CS 537 - Introduction to Operating Systems Fall 2019
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CS 537 - Introduction to Operating Systems
Fall 2019
Exam 3 — Final Exam: Persistence
File System API (6 points)
Consider the following commands sent to a UNIX-based system:
Line 1: echo ’hello’ >> file1
Line 2: ln file1 file2
Line 3: cat file2
Line 4: rm file1
Line 5: cat file2
Line 6: echo ’more’ >> file1
Line 7: cat file2
Ignore any problems with whitespace or capitalization. Assume ; shows text separated across multiple lines in the shown output.
1. What will be the output from Line 3?
A. hello
B. more
C. more ; hello
D. hello ; more
E. ERROR: No such file or directory
2. What will be the output from Line 5?
A. hello
B. more
C. more ; hello
D. hello ; more
E. ERROR: No such file or directory
3. What will be the output from Line 7?
A. hello
B. more
C. more ; hello
D. hello ; more
E. ERROR: No such file or directory
Assume the ln command in Line 2 is changed to ln -s.
4. What will be the output from Line 3?
A. hello
B. more
C. more ; hello
D. hello ; more
E. ERROR: No such file or directory
5. What will be the output from Line 5?
A. hello
B. more
C. more ; hello
D. hello ; more
E. ERROR: No such file or directory
6. What will be the output from Line 7?
A. hello
B. more
C. more ; hello
D. hello ; more
E. ERROR: No such file or directory
File System Images (16 points)
These questions ask you to understand how different file system operations lead to different file system data structures being modified on disk. You do not need to consider journaling or crash consistency in these questions. This part is
based on the available homework simulations.
This file system supports 7 operations:
| 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)
The state of the file system is indicated by the contents of four different data structures:
| inode bitmap - indicates which inodes are allocated (not shown, because not needed for questions) | inodes - table of inodes and their contents
| data bitmap - indicates which data blocks are allocated (not shown)
| data - indicates contents of data blocks
The inodes each have three fields: the first field indicates the type of file (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 have the address of the data block set to -1, or one block in size, which would have a non-negative 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].
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.
Empty inodes and empty data blocks may not all be shown.
An entire file system is thus depicted as follows:
inodes
data
[d a:0 r:6] [f a:1 r:1] [f a:-1 r:1] [d a:2 r:2] [] . . .
[( . ,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.
For the following questions, begin by assuming you have a file system image in the following state:
inodes [d a:0 r:5] [d a:1 r:2] [f a:-1 r:1] [f a:-1 r:1] [] [] [] [] data [( . ,0) ( . . ,0) (g,1) (q,2) (u,3)] [( . ,1) ( . . ,0)] [] [] [] [] [] []
7. What is /g?
A. File
B. Directory
C. Does not exist in this file system image
D. Not enough information to determine
E. None of the above
8. What is /q?
A. File
B. Directory
C. Does not exist in this file system image
D. Not enough information to determine
E. None of the above
9. What is /g/d?
A. File
B. Directory
C. Does not exist in this file system image
D. Not enough information to determine
E. None of the above
Assume you now execute the command link(‘‘/u’’, ‘‘/x’’);
10. What could be the resulting state of the file system image for inodes?
A. No change (includes if the operation was invalid)
B. [d a:0 r:6] [d a:1 r:2] [f a:-1 r:2] [f a:-1 r:1] [] [] [] []
C. [d a:0 r:6] [d a:1 r:2] [f a:-1 r:1] [f a:-1 r:2] [] [] [] []
D. [d a:0 r:5] [d a:1 r:2] [f a:-1 r:1] [f a:-1 r:1] [f a:-1 r:1] [] [] []
E. None of the above
11. What could be the resulting state of the file system image for data blocks?
A. No change (includes if the operation was invalid)
B. [( . ,0) ( . . ,0) (g,1) (q,2) (u,3) (x,3)] [( . ,1) ( . . ,0)] [] [] [] [] [] []
C. [( . ,0) ( . . ,0) (g,1) (q,2) (u,3) (x,4)] [( . ,1) ( . . ,0)] [] [] [] [] [] []
D. [( . ,0) ( . . ,0) (g,1) (q,2) (u,3)] [( . ,1) ( . . ,0) (x,4)] [] [] [] [] [] []
E. None of the above
Now, assume you have a different file system image:
inodes
data
[d a:0 r:4] [d a:1 r:3] [f a:-1 r:2] [] [] [] [] []
[( . ,0) ( . . ,0) (e,2) (o,1)] [( . ,1) ( . . ,0) (s,2)] [] [] [] [] [] []
12. For this file system image, which two pathnames can be used to access the same file?
A. /o and /s
B. /o and /e/s
C. /e and /o
D. /e and /o/s
E. None of the above OR more than one of the above
Assume you now execute the following commands:
fd=open(‘‘/e’’, O_WRONLY|O_APPEND); write(fd, buf, BLOCKSIZE); close(fd);
13. What could be the resulting state of the file system image for inodes?
A. No change (includes if the operation was invalid)
B. [d a:0 r:4] [d a:1 r:3] [f a:-1 r:3] [] [] [] [] []
C. [d a:0 r:4] [d a:1 r:3] [f a:1 r:2] [] [] [] [] []
D. [d a:0 r:4] [d a:1 r:3] [f a:2 r:2] [] [] [] [] []
E. None of the above OR more than one of the above
14. What could be the resulting state of the file system image for data blocks?
A. No change (includes if the operation was invalid)
B. [( . ,0) ( . . ,0) (e,2) (o,1)] [( . ,1) ( . . ,0) (s,2) (e,1)] [] [] [] [] [] []
C. [( . ,0) ( . . ,0) (e,2) (o,1)] [( . ,1) ( . . ,0) (s,2)] [a] [] [] [] [] []
D. [( . ,0) ( . . ,0) (e,2) (o,1)] [( . ,1) ( . . ,0) (s,2)] [( . ,1) ( . . ,0)] [] [] [] [] []
E. None of the above OR more than one of the above
File System Data Structures (16 points)
This question asks you about the read and write operations that a file system like FFS must send to disk to update its meta-data and data blocks. You should make the following assumptions:
| Disk blocks are 4 KB
| Nothing begins in the file system buffer cache
| All modified data must be written to the disk (and not just the buffer cache)
| All directory data always fits within 4 KB
| No needed inode is ever in the same block as another needed inode
| No timestamps are updated
| The operations cause no errors (e.g., specified directories exist, files to be created do not already exist) | There is no journaling or other mechanisms for crash consistency
Assume that you would like to create a new (empty) file bar with the pathname /dir/dir2/bar. Think about the read and write operations that will be required; it may be useful to write them all out to answer the following questions.
15. How many disk blocks will be read to create the file?
A. 5 B. 6 C. 7 D. 8 E. None of the above
16. How many disk blocks will be written to create the file?
A. 3 B. 4 C. 5 D. 6 E. None of the above
How must the disk blocks containing each of the following file system data structures be accessed to create the file? Possible options are the block A) must only be read, B) must only be written, C) must be both read and written,
D) does not need to be accessed. There is no E) option.
17. The block containing the data for dir must be:
A. read only B. written only C. read and written D. nothing
18. The block containing the inode for dir2 must be:
A. read only B. written only C. read and written D. nothing
19. The block containing the data for dir2 must be:
A. read only B. written only C. read and written D. nothing
20. The block containing the inode for bar must be:
A. read only B. written only C. read and written D. nothing
21. The block containing the data for bar must be:
A. read only B. written only C. read and written D. nothing
22. A block containing a portion of the inode bitmap must be:
A. read only B. written only C. read and written D. nothing
23. A block containing a portion of the data bitmap must be:
A. read only B. written only C. read and written D. nothing
Assume that you would now like to open an existing file foo with the pathname /dir/dir2/foo; to open the file, you must read the file’s inode into memory. Again, assume nothing begins cached in the file system buffer cache. Think about the read and write operations that will be required; it may be useful to write them all out to answer the following questions.
24. How many disk blocks will be read to open the file?
A. 4 B. 5 C. 6 D. 7 E. None of the above
25. How many disk blocks will be written to open the file?
A. 1 B. 2 C. 3 D. 4 E. None of the above
How must the disk blocks containing each of the following file system data structures be accessed to open the file?
26. The block containing the inode for dir2 must be:
A. read only B. written only C. read and written D. nothing
27. The block containing the data for dir2 must be:
A. read only B. written only C. read and written D. nothing
28. The block containing the inode for bar must be:
A. read only B. written only C. read and written D. nothing
29. The block containing the data for bar must be:
A. read only B. written only C. read and written D. nothing
30. A block containing a portion of the inode bitmap must be:
A. read only B. written only C. read and written D. nothing
31. A block containing a portion of the data bitmap must be:
A. read only B. written only C. read and written D. nothing
Data Journaling with Barriers (10 points)
You are using a journaling file system (such as Linux ext3) in full data-journaling mode without the checksum performance optimization (i.e., the transaction commit block does NOT contain a checksum over the blocks of that transaction).
As described in class, each transaction is composed of a single transaction header block (also called transaction descriptor block), multiple meta-data and data blocks in the transaction, and a single transaction commit block; there is also an in-place checkpoint region on the disk.
As you know, some of the transaction blocks and some blocks to the checkpoint region can be written out concurrently to disk. Other blocks cannot be written concurrently: to guarantee crash consistency, the file system must ensure that particular blocks (e.g., A), are persisted to disk before others (e.g., B). Thus, the file system flushes A to disk and sends a barrier operation to the disk before sending B.
What crash consistency errors could occur if the journaling file system does not send a barrier to the disk between the following types of blocks for A and B? Note that a barrier may not be needed between A and B. In each question, assume all other barriers are inserted correctly; that is, each question is independent. Ignore any performance problems.
32. A = Transaction header block; B = First transaction meta-data/data block
A. No correctness problem occurs
B. Could replay garbage located in transaction to checkpoint region
C. Could partially overwrite in-place checkpoint data and not replay transaction
D. Other correctness problem
33. A = First meta-data/data block in transaction; B = Other meta-data/data blocks in transaction
A. No correctness problem occurs
B. Could replay garbage located in transaction to checkpoint region
C. Could partially overwrite in-place checkpoint data and not replay transaction
D. Other correctness problem
34. A = Last meta-data/data block in transaction; B = Transaction commit block
A. No correctness problem occurs
B. Could replay garbage located in transaction to checkpoint region
C. Could partially overwrite in-place checkpoint data and not replay transaction
D. Other correctness problem
35. A = Transaction commit block; B = Blocks to in-place checkpoint region
A. No correctness problem occurs
B. Could replay garbage located in transaction to checkpoint region
C. Could partially overwrite in-place checkpoint data and not replay transaction
D. Other correctness problem
36. A = Blocks to in-place checkpoint region; B = Transaction commit block
A. No correctness problem occurs
B. Could replay garbage located in transaction to checkpoint region
C. Could overwrite in-place checkpoint data and not replay transaction
D. Other correctness problem
Distributed File Systems (20 points)
The next questions explore the cache consistency behavior of AFS and NFS.
The next two pages show two identical traces; you should use one trace for answering how NFS behaves and one trace for answering how AFS behaves.
Each trace contains two clients that each generate file opens, reads, writes, and closes on a single file. The 2 columns show the actions being taken on each of the two clients, c0 and c1. Time increases downwards in seconds. Assume the time required to send/receive messages over the network and for the server to respond is negligible.
Opening a file returns a file descriptor which would be used for each call to read, write, and close, but is not shown because only a single file is involved. The file contains multiple blocks. The arguments to read and write show the block number of the file that is being accessed. Note that it does not matter what data is actually read or written.
For each protocol, assume that the server and clients have sufficient memory and disk space such that no operations are performed unless required by the protocol. NFS Hint: Every interaction with the server returns the current attributes for the requested file.
NFS
Time (s) |
c0 |
c1 |
0.0 1.0 2.0 3.0 10.0 11.0 12.0 13.0 14.0 15.0 16.0 17.0 18.0 19.0 20.0 21.0 22.0 23.0 24.0 25.0 26.0 27.0 |
open read(1) read(2) read(3) read(2) read(3) write(3)
read(1) read(3) write(3)
close |
open read(3) read(1) write(1) close
open read(3) close open read(3) close |
At the time in question, what operation must the NFS client perform?
For the read and open operations, your choices are:
A. Operations performed locally on client machine (i.e., no interaction with server)
B. Send getattr()/stat() request to server; then use local copy of data
C. Send getattr()/stat() request to server; then obtain block from server
D. Obtain block from server (do not need to first send getattr()/stat() request)
E. Obtain whole file from server (do not need to first send getattr()/stat() request) For the write and close operations, your choices are:
A. Write local copy of block (with no interaction with server)
B. Write local copy of block and also send block to server
C. Send all file changes (or whole file) to server
D. No writing of local copy and no interacting with server
2022-08-09