这是一篇来自美国的关于分为磁盘读取和回收数据块等4个方面的CS代写作业案例
- [20%] RAID level 5, in handling a one-block write request, must write to both a data disk and the check disk for that stripe. However, it need not read data blocks from the other data disks in order to recompute the check block. Explain why not. Assume that the check block is the exclusive-or of the data blocks. [Hint: the exclusive-or operation is commutative and, under exclusive-or, each element is its own inverse].
- [40%] An issue with ZFS is reclamation of data blocks. With multiple snapshots in use for each file 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 file 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 should be deleted and which must remain? To answer this question, let’s go through the following steps. Note that putting reference counts on file-system blocks is not part of the solution: if reference counts were used, then each block’s reference count would have to be incremented on each snapshot operation — greatly adding to the cost of creating the snapshot.
[All questions have fairly short answers.]
a.[4%] Suppose each block pointer, in addition to containing a checksum, also contains the time at which the block was created, known as the block’s creation time (note that blocks are never modified in place, thus the creation time for a particular file-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. (Hint: might timestamps be associated with snapshots as well?)
b.[8%] Suppose a block is freed from the current file system (but might still be referenced by a snapshot). Explain how it can be determined whether there exists a snapshot that is referring to it.
c.[12%] When a block is freed, we can’t simply get rid of it if it is referred to by some snapshot. So, rather than get rid of it, we maintain a list of blocks we’d like to get rid of, a list we call the retired list. Thus, if a block being freed cannot be reclaimed because some snapshot is referring to it, a reference to it is appended to the file-system’s retired list. When a new snapshot is created, we create a retired list for it that’s a copy of the file system’s retired list, and then set the file-system’s retired list 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 creation time is later than the creation time of the previous snapshot, and the block was freed before the creation time of the next snapshot (or of the file 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 blocks for which a snapshot is responsible listed in the next snapshot’s retired list (or in the current file system’s retired list if this is the most recent snapshot)? Explain.
d.[8%] Suppose a snapshot is deleted (it is the first one to be deleted). How can we determine which blocks to reclaim?
e.[8%] We’d like this reclamation algorithm to work for subsequent deletions of snapshots.
Part c describes an invariant: all blocks for which a snapshot is responsible appear in the next snapshot’s retired list (or in the retired list of the file 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?
- [20%] It’s been argued that the pattern of creating a new process by doing a combination of fork and exec is too expensive for some applications. We’re going to examine the cost of this combination. Let’s assume we are using the (32-bit) x86 architecture, with two-level paging and a page size of 4K. Each address space is represented by a one-page page-directory table containing 1024 (210) 4-byte entries, each of which may refer to a one-page page table containing 1024 4-byte entries, each of which may refer to a page of physical memory. We consider a process that has one read-only region of memory (containing executable code and constants) and two readwrite regions of memory (one containing BSS, data, and dynamic storage, the other containing the stack). Assume that mmap is not used. Assume that the stack region occupies 16 kilobytes (214 bytes) and the other regions are one megabyte (220 bytes) each. The first two (i.e., the larger) regions are at the low end of the address space, the stack region is at the high end (just below the kernel). Furthermore, assume that esp, the stack pointer register, points to a location that is 512 bytes from the low-addressed end of the stack (the stack grows from high addresses down to low addresses). Assume that it takes two microseconds (2 × 10-6 seconds) to copy one page of primary memory (or a fraction thereof).
a.[4%] Recall that the effect of executing a fork system call is to create an exact copy of the calling process. Let’s assume that our system does nothing to optimize the making of this copy, i.e., that it does not employ copy on write and that all the pages of the parent process are copied to create the child. How long would it take to copy all relevant memory when creating the child? (Note: page tables are included in relevant memory.
They must be copied, then modified; we won’t include the cost of modifying them.)
b.[2%] Early Unix systems employed the vfork system call as an optimization of fork when the call to fork was to be followed by a call to exec. In this optimization, the child process executes in the parent’s address space (on the same stack as the parent) until it calls exec,then a new address space is created for it. How long would it take to copy all relevantmemory as part of the implementation of vfork?
c.[4%] Weenix (and other Unix-based systems) optimize fork by using copy-on-write techniques. In particular, the child process’s initial address space is virtually identical to that of the parent, but copy-on-write techniques are used to avoid copying any memory.(Note that new page tables and a new page directory are created.) How long would it take to copy all relevant memory as part of this optimized fork?
d.[4%] Continuing with this optimized version of fork, suppose our process makes a few changes to file descriptors and then calls exec. Though nothing is modified in the first read-write region of memory, a maximum of 256 bytes of memory are pushed onto the stack. In addition to the cost of storing new items to the stack, how much time is spent copying relevant memory?
e.[4%] We’d like to improve the optimization used in part c. What might we do to do so? (Hint: consider using copy on write on additional data structures, perhaps some used for address translation.) With your new optimization, how long would it take to copy all relevant memory as part of the fork implementation and then place its call to exec?
f.[2%] There’s a relatively new system call known as posix_spawn that has the effect of combining fork and exec into a single system call (it has all the arguments used by exec, as well as additional arguments indicating how file descriptors should be modified). If it were implemented optimally (with respect to the copying of the parent process’s address space), how much cheaper would it be for our process than the optimized version of fork (followed by exec) used in part d?
- [20%] Section 7.3.3 of the text discusses the use of shadow objects.
a.[10%] Give an example showing how the chain of shadow objects may grow arbitrarily long.
b.[10%] Describe the circumstances under which such a chain may be made shorter.
Trivia Questions
- The VAX-11 computer had a diagnostic register that was called “fubar”, which, the manufacturer said, stood for “failed unibus address register”. However, the term “fubar” was often used, sort of as a nonsense word, in computer circles, and was often misspelled “foo bar”. What is the origin of this word and what did it originally stand for? (It is an acronym.) The word “snafu” has a similar history, though it was not used in computer circles. What does it stand for?
- Each of the following abbreviations would have been familiar to you if you were a tech-savvy person at the appropriate time and place. What does each of them stand for?
a.EBCDIC
b.PCMCIA
c.TWAIN
d.SCSI
e.HIPPI
f.BRUNET
e.USB
程序辅导定制C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: vipdue@outlook.com 微信号:vipnxx
如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。
