FIRST GRADER essay writing company is the ideal place for homework help. If you are looking for affordable, custom-written, high-quality and non-plagiarized papers, your student life just became easier with us. Click the button below to place your order.
Order a Similar Paper Order a Different Paper
FILE SYSTEMS EXERCISES 6.8
Assume we are using the Rhinopias disk drive discussed in Section 188.8.131.52. a) What is the maximum transfer rate for a single track? b) What is the maximum transfer rate for accessing fi ve tracks consecutively (assume head skewing)?
2. Explain why the typical transfer rate achieved on S5FS is far less than the maximum transfer rate of the disk.
3. How do block-based fi le systems differ from extent-based systems? What is block clustering?
4. Assume we’re using the Rhinopias disk drive. a) Suppose we are using S5FS and we’ve doubled the block size from 512 bytes to 1024 bytes. Is the maximum expected transfer rate roughly doubled? Explain. b) We’ve done the same with FFS. Is the maximum expected transfer rate roughly doubled? Explain. Assume that we’re using two-way block interleaving: when we allocate successive blocks on a track, one block is skipped. Thus, in the best case, every other block of a track is allocated to a fi le. c) Why should we care about the block size in FFS?
5. Explain what is meant by innocuous inconsistency. How does it differ from non-innocuous or real inconsistency?
6. The layout of disk blocks is an important factor in fi le-system performance. FFS uses the technique of block interleaving to reduce rotational delays. This technique provides a large improvement over the use of consecutive blocks. However, many of today’s most advanced fi le systems, such as WAFL and ZFS, do not use block interleaving. a) Explain how block interleaving helps FFS reduce the time required to read from disk. b) Explain how WAFL’s design provides fast access without the need for block interleaving
7. Would log-structured fi le systems (Section 184.108.40.206) have been feasible in the early 1980s when FFS was designed? Explain. (Consider the cost of the resources required.)
8. What approach did the original FFS use for crash tolerance? What impact did this have on performance? How has this been improved in recent versions?
9. Section 220.127.116.11 covers soft updates and mentions that FFS using soft updates may require more disk writes than Async FFS. Give an example in which more disk writes would occur with soft updates than with Async FFS.
0. One early application of shadow paging in a fi le system was in an FFS-like system. All operations between open and close of a fi le were treated as part of a single transaction. Thus if the system crashed before the fi le was closed, the effect was as if nothing had happened 6.8 EXERCISES * ** *to the fi le since the open. This was done by making a copy of the fi le’s intoed when it was opened, and applying all changes to copies of blocks being modifi ed (i.e., using copy-on-write techniques). When the fi le was closed, the reference to its inode in the directory it appeared in was replaced with a reference to the new, modifi ed inode. Thus in a single disk write, all modifi cations took effect at once. There are a few problems with this approach. It doesn’t handle files that appear in multiple directories. It also doesn’t handle concurrent access to the fi le by multiple processes. Let’s ignore both of these problems (they’re fi xable, but we won’t fi x them here!). There’s a performance problem: the original blocks of the fi le were allocated on disk so that the fi le could be accessed sequentially very quickly. But when we make copies of the disk blocks being modifi ed, these copies aren’t necessarily going to be near the original copies. Thus writing these blocks might incur long seek delays. For this reason shadow paging wasn’t used in fi le systems until relatively recently. How might these problems be fi xed?
11. NTFS does a combination of both redo and undo journaling. Section 6.6.4 explains why it’s useful to have undo journaling. Why is redo journaling also done
12. NTFS has a feature called data streams. Describe this feature and give an example of how it might be useful
13. Explain how renaming a fi le can be done using the consistency-preserving approach so that a crash will not result in the loss of the fi le. Be sure to take into account the link count stored in the fi le’s inode. Note that there may have to be a temporary inconsistency; if so, explain why it will not result in lost data.
14. A defragmenter is often used with NTFS to improve its performance. Explain how a similar tool might be devised for S5FS to improve its performance. Would the use of this tool bring S5FS’s performance up to acceptable levels?
1. Hashing is often used for looking up directories entries. Explain the advantages of extensible hashing over simple static hashing
2. Section 18.104.22.168 discussed extensible hashing. Show how deletions of directory entries can be implemented so that buckets are combined where possible, allowing the bucket and indirect bucket arrays to be reduced in size
1. RAID level 4, in handling a one-block write request, must write to both a data disk and the check disk. However, it need not read data blocks from the other data disks in order to recompute the check block. Explain why not.
2. We have an operating system whose only fi le system is S5FS. Suppose we decide to employ a RAID level 4 or RAID level 5 disk system. Can S5FS take advantage of all the features of these systems? Explain. Assume that the block size of S5FS is equal to the disk-sector size
1. Explain why Ext3 and NTFS use RAID level 5 rather than RAID level 4. Explain what features of WAFL make it particularly well suited for use with RAID level 4.
2. An issue with ZFS is reclamation of data blocks. With multiple snapshots in use for each fi le system, it’s not necessarily trivial to determine which blocks are actually free. For example, there might be, in addition to the current version of the fi le system, three snapshots of it. If we delete the snapshot that’s neither the most recent nor the least recent, how can we determine which blocks must be deleted and which must remain? To answer this question, let’s go through the following steps. a) Explain why reference counts are not part of the solution. ** ** ** * b) Suppose each block pointer, in addition to containing a checksum, also contains the time at which the block was created (note that blocks are never modifi ed in place, thus the creation time for a particular fi le-system block on disk doesn’t change). Explain how this information can be used to determine that a block was created after a particular snapshot. c) Suppose a block is freed from the current fi le system (but might still be referenced by a snapshot). Explain how it can be determined whether the most recent snapshot is referring to it. d) If such a block cannot be reclaimed because some snapshot is referring to it, a reference to it is appended to the fi le-system’s dead list. When a new snapshot is created, its dead list is set to be that of the current fi le system, and the current fi le-system’s dead list is set to empty. Let’s assume no snapshots have ever been deleted. We say that a snapshot is responsible for the existence of a block if the block’s birth time came after the creation of the previous snapshot and the block was freed before the birth time of the next snapshot (or of the fi le system if this is the most recent snapshot). In other words, the only reason the block cannot be reclaimed is because this snapshot exists. Are all such blocks in the next snapshot’s dead list (or in the current fi le system’s dead list if this is the most recent snapshot)? Explain. e) Suppose a snapshot is deleted (the fi rst one to be deleted). How can we determine which blocks to reclaim? f) We’d like this algorithm to work for subsequent deletions of snapshots. Part d describes an invariant: all blocks for which a snapshot is responsible appear in the next snapshot’s dead list (or in the dead list of the fi le system if it’s the most recent snapshot). What else must be done when a snapshot is deleted so that this invariant is maintained (and the algorithm continues to work)?