34. Short Answer Questions_Final Flashcards
We have described (at least) two places where the data structure used by the OS presents a tradeoff between desirable properties. Identify one (1 point), describe what it is for (2 points) and describe the tradeoff (2 points).
- Page tables.
Process page tables map process virtual addresses to page table entries (PTEs), which may contain the physical address (if the page is in memory), a disk location (if it is swapped out), or other information.
Page tables present a size versus mapping speed tradeoff.
Compact page tables (such as a linked list of PTEs) make mapping speed scale poorly as the size of the address space grows, while the O(1) page table (an array) is way too large.
Multi-level page tables or lists of segments with their own lists of PTEs are both compromises between space and speed.
- Inode to data block mapping.
Allows filesystems to locate the ordered list of data blocks associated with a file starting from the inode structure.
Presents pretty much the same size v speed tradeoff as page tables, with the additional considerations that:
(1) files should be able to grow to arbitrary sizes (as opposed to fixed-size address spaces) and
(2) traversing large on-disk data structures may involve multiple read operations that require seeks and are, therefore, slow on spinning disks.
The use of (double, triple, quadruple) indirect blocks was another compromise that both allows files to grow to extremely large sizes while reflecting the fact that many files are small.
Describe the difference between full virtualization and paravirtualization (2 points), and how one way that the guest OS manipulates the virtual machine is handled differently by the two approaches (3 points).
Full virtualization attempts to present a virtual machine abstraction that is identical to the physical machine, which allows running unmodified guest operating systems.
Paravirtualization presents a modified virtual machine abstraction that is easier for the hypervisor to support, but requires changes to the guest OS.
One example difference is the approach to handling instructions that are not classically virtualizable and cannot be supported via ‘trap and emulate’.
Full virtualization approaches must detect when the guest OS is attempting to use them and rewrite them to save instruction sequences at runtime.
In contrast, paravirtualization allows the guest OS to be rewritten to not use such instructions, which simplifies the runtime process of providing the virtual machine abstraction.
Another example is how the guest OS interacts with the MMU.
In full virtualization, attempts to manipulate the MMU must trap through the host OS (since the guest OS is running without kernel privilege) and be handed to the virtual machine monitor which checks the operation for safety and updates its internal state if appropriate.
In paravirtualization, the guest OS is rewritten to use an interface provided by the hypervisor to update the MMU, which can reduce the overhead of the process.
State Amdahl’s Law and describe how it guides the process of performance improvement.
The impact of any effort to improve system performance is constrained by the performance of the parts of the system not targeted by the improvement
OR
Ignore the thing that looks the worst and fix the thing that is doing the most damage.
The corollary: The more you improve one part of a system, the less likely it is that you are still working on the right problem!
Amdah’ls Law informs performance improvement in a variety of ways. It says that if you aren’t working on the right problem, you aren’t going to accomplish much, meaning that it’s essential to figure out what the right problem is.
It also implies that once you’ve made an improvement, you need to reassess because another part of the system may now be your bottleneck.
Recall that in RAID level 1 (RAID 1) array, both drives store identical contents. (Assume the drives are spinning disks.) First, explain why you would expect to see a significant performance difference between reads and writes to and from a RAID 1 array (3 points). Second, describe how to coordinate RAID 1 reads to further improve performance (2 points).
Because both drives store identical contents, RAID 1 reads can come from either mirror, allowing both disks to be processing separate reads simultaneously.
In contrast, writes must complete on both disks before they can be considered completed. This accounts for the performance difference.
A simple coordination strategy monitors both disks and uses some metric to determine which disk to send each read to.
One way to do this is to monitor the head position of both disks and send the read to the disk where the head has the shortest distance to travel to perform the read.
However, this may not work given that if operations are queued at the disk and heads may be repositioned several times before the location of the last read in the disk queue, assuming it processes them in FIFO order.
A similar approach just monitors the read queue length on both disks and sends the read to the disk with the shorter queue - producing a simple form of load balancing.
Now that you’ve implemented the OS/161 system calls, let’s improve their performance. Mighta s well start with getpid(), since it’s simple. First, briefly explain the overhead of performing a call to getpid() (1 point). Second, propose a way to reduce this overhead by exploiting properties of the getpid() system call (2 points). Finally, will this improve performance? If so, why? If not, why not? Justify your answer (2 points)
The overhead of getpid() is usual user-kernel transition overhead involving saving state on the way into the kernel, incurred by every system call.
The way to avoid this is to note that each process ID is set during fork() and doesn’t change during the life of the process.
So there is no need for the process to enter the kernel repeatedly when asking for it.
Instead, the C library could simply cache the answer, or the kernel could write a copy of the process ID to an agreed-upon memory location during fork() and then getpid() could be modified to retrieve it using a single load, which would be much more efficient than trapping into the kernel.
Will this improve overall process performance? Of course not. Apply Amdahl’s Law. most processes rarely if ever retrieve their process ID, and if they do they probably cache it using a local (or global) variable for the same reasons we just described.
What are 6 ways that file systems compensate for or are designed around specific properties of spinning disks.
- Data transfer limitations
- Rotational effects
- Seek times
- Cylinder groups
- Log-structured file systems
- Journaling
Describe how filesystems compensate for or are designed around data transfer limitations of spinning disks.
FFS worked around bus-speed limitations of early disks by not writing data to consecutive blocks, since doing so would cause the disk buffer to fill and force it to stall and make a complete rotation before it could continue reading.
Instead, it wrote files to alternate blocks as intervals allowing it to match the disk transfer speed.
Describe how filesystems compensate for or are designed around rotational effects of spinning disks.
We mentioned that many filesystems try to put frequently-accessed content at the outer edge of the disk - or at least start filling the disk at that edge - because constant disk density combined with longer tracks on the outer edge makes data transfer higher to and from that part of the disk
Describe how filesystems compensate for or are designed around seek times of spinning disks.
We discussed many different attempts to reduce the impact of seek times, including
(1) utilizing a buffer cache
(2) locating inodes and file content close to each other
(3) locating data blocks from the same file close to each other
(4) locating related files close to each other - where distance is measured on the disk in terms of the time needed to seek the heads from one track to another
Describe how filesystems compensate for or are designed around cylinder groups of spinning disks.
FFS also used cylinder groups to locate related files and file metadata close to each other on the disk, specifically at places where they could be read and written from multiple platters without moving the heads (very far).
This exploits the fact that disks are created of multiple platters but the disk arm positions all heads in the same location at the same time.
The idea of effectively breaking the filesystem into smaller filesystems, each with its own inodes and data blocks, is preserved by modern filesystems such as ext4.
The goal is the same: reduce seeks between file metadata (i.e., inodes) and file contents (i.e., data blocks) by structuring the file system so that they are nearby on disk
Describe how log-structured filesystems compensate for or are designed around seek times of spinning disks.
LFS tried to address seek time limitations in a different way by performing as many disk operations as possible to one location on the disk: the end of the append-only log.
This works as long as a large buffer cache soaks up all or most reads, leaving only writes to be performed by the disk.
Describe how filesystems compensate for or are designed around reliability issues of spinning disks.
Journaling. This works around disk reliability problems by exploiting the atomicity of operations to single disk blocks.
If the filesystem can succinctly describe what it was attempting to do when that operation spans multiple disk blocks, then it is easier to identify and either complete or abort unfinished operations when recovering from a sudden failure.
Describe each step in the process of translating the path /home/trinity/os161 to an inode number in an FFS-like filesystem (1 point each step).
- Use the hardcoded value to map the root path component to an inode number. (Let’s say it’s 2)
- Open the directory with inode number 2.
- Look for the “home” pathname component in directory 2 and map it to the next inode number, say 3.
- Open the directory with inode number 3.
- Look for the “trinity” pathname component in directory 3 and map it to the next inode number, say 4.
- Open the directory with inode number 4.
- Look for the “os161” pathname component in directory 4 and map it to the final inode number, say 5.
If at any point one of the pathnames was not a directory, the mapping would fail.
