Operating System Concepts Exercises 12
操作系统作业 12
- 12.1, 12.3, 12.4, 12.7, 12.8
- 12.10, 12.11, 12.15, 12.16, 12.19
每题最后一个引用块是老师提供的参考答案
Practice Exercises
12.1, 12.3, 12.4, 12.7, 12.8
12.1 Consider a file currently consisting of 100 blocks. Assume that the file-control block (and the index block, in the case of indexed allocation) is already in memory. Calculate how many disk I/O operations are required for contiguous, linked, and indexed (single-level) allocation strategies, if, for one block, the following conditions hold. In the contiguous-allocation case, assume that there is no room to grow at the beginning but there is room to grow at the end. Also assume that the block information to be added is stored in memory.
考虑一个目前由 100 个块组成的文件。假设文件控制块（和索引块，在索引分配的情况下）已经在内存中。计算一下，对于一个块，如果以下条件成立，连续、链接和索引（单级）分配策略需要多少次磁盘 I/O 操作。在连续分配的情况下，假设在开始时没有增长空间，但在结束时有增长空间。还假设要增加的区块信息存储在内存中。
a. The block is added at the beginning.
b. The block is added in the middle.
c. The block is added at the end.
d. The block is removed from the beginning.
e. The block is removed from the middle.
f. The block is removed from the end.
答：
| contiguous | linked | indexed | |
|---|---|---|---|
| a. The block is added at the beginning. | 201 | 1 | 1 |
| b. The block is added in the middle. | 101 | 52 | 1 |
| c. The block is added at the end. | 1 | 3 | 1 |
| d. The block is removed from the beginning. | 198 | 1 | 0 |
| e. The block is removed from the middle. | 98 | 52 | 0 |
| f. The block is removed from the end. | 0 | 100 | 0 |
12.3 Why must the bit map for file allocation be kept on mass storage, rather than in main memory?
为什么文件分配的位图必须保存在大容量存储器上，而不是保存在主存中？
答：
In case of system crash (or system reboot) the free-space list would not be lost as it would be if the bit map had been stored in main memory.
在系统崩溃（或系统重启）的情况下，自由空间列表不会丢失，因为如果位图被存储在主内存中就会丢失。
12.4 Consider a system that supports the strategies of contiguous, linked, and indexed allocation. What criteria should be used in deciding which strategy is best utilized for a particular file?
考虑一个支持连续、链接和索引分配策略的系统。在决定哪种策略最适合于某个特定文件时，应该使用什么标准？
答：
- 毗连 - 如果文件通常是按顺序访问的，如果文件相对较小。
- 链接 - 如果文件很大并且通常是按顺序访问。
- 索引的 - 如果文件很大，而且通常是随机访问。
12.7 Why is it advantageous for the user for an operating system to dynamically allocate its internal tables? What are the penalties to the operating system for doing so?
为什么操作系统动态地分配其内部表对用户是有利的？操作系统这样做会受到什么惩罚？
答：
Dynamic tables allow more flexibility in system use growth — tables are never exceeded, avoiding artificial use limits.
Unfortunately, kernel structures and code are more complicated, so there is more potential for bugs. The use of one resource can take away more system resources (by growing to accommodate the requests) than with static tables.
动态表允许在系统使用增长方面有更大的灵活性 - 表永远不会被超过，避免了人为的使用限制。
不幸的是，内核结构和代码更加复杂，所以有更多潜在的错误。与静态表相比，对一种资源的使用可以占用更多的系统资源（通过增长来适应请求）。
12.8 Explain how the VFS layer allows an operating system to support multiple types of file systems easily.
解释一下 VFS 层是如何让操作系统轻松支持多种类型的文件系统的。
答：
抽象去耦
VFS introduces a layer of indirection in the file system implementation. In many ways, it is similar to object-oriented programming techniques. System calls can be made generically (independent of file system type). Each file system type provides its function calls and data structures to the VFS layer. A system call is translated into the proper specific functions for the target file system at the VFS layer. The calling program has no file-system-specific code, and the upper levels of the system call structures likewise are file system-independent. The translation at the VFS layer turns these generic calls into file-system-specific operations.
VFS 在文件系统的实现中引入了一层间接性。在许多方面，它类似于面向对象的编程技术。系统调用可以通用地进行（与文件系统类型无关）。每个文件系统类型都向 VFS 层提供其函数调用和数据结构。一个系统调用在 VFS 层被翻译成目标文件系统的适当的特定功能。调用程序没有针对文件系统的代码，而系统调用结构的上层也同样与文件系统无关。在 VFS 层的翻译将这些通用调用变成了文件系统特定的操作。
Exercises
12.10, 12.11, 12.15, 12.16, 12.19
12.10 Contrast the performance of the three techniques for allocating disk blocks (contiguous, linked, and indexed) for both sequential and random file access.
对比一下三种分配磁盘块的技术（连续的、链接的和索引的）在顺序和随机文件访问方面的性能。
答：
Contiguous Sequential - works very well as the file is stored contiguously
Contiguous Random – works well
Linked Sequential - Works okay since you are following the links from one block to the next
Linked Random - This would be poor as you may need to traverse around the links
Indexed sequential - Works well as sequential access simply involves sequentially accessing each index
Indexed Random - Works well as it is easy to determine the index from the index blocks
毗连顺序–工作得很好，因为文件是毗连存储的。
毗连随机 - 工作良好
链接的顺序–工作得很好，因为你是按照从一个区块到下一个区块的链接进行的。
链接随机–这将是很差的，因为你可能需要绕过链接。
索引式顺序–工作得很好，因为顺序访问只涉及到对每个索引的顺序访问
索引式随机–效果很好，因为很容易从索引块中确定索引
12.11 What are the advantages of the variant of linked allocation that uses a FAT to chain together the blocks of a file?
使用 FAT 将文件块链在一起的链接分配的变体有什么优点？
答：
The advantage is that while accessing a block that is stored at the middle of a file, its location can be determined by chasing the pointers stored in the FAT as opposed to accessing all of the individual blocks of the file in a sequential manner to find the pointer to the target block. Typically, most of the FAT can be cached in memory and therefore the pointers can be determined with just memory accesses instead of having to access the disk blocks
其优点是，在访问存储在文件中间的块时，可以通过追逐存储在 FAT 中的指针来确定其位置，而不是以顺序的方式访问文件的所有单个块来找到目标块的指针。通常情况下，大部分的 FAT 可以被缓存在内存中，因此可以只通过内存访问来确定指针，而不必访问磁盘块。
12.15 Consider a file system on a disk that has both logical and physical block sizes of 512 bytes. Assume that the information about each file is already in memory. For each of the three allocation strategies (contiguous, linked, and indexed), answer these questions:
考虑一个磁盘上的文件系统，它的逻辑和物理块大小都是 512 字节。假设每个文件的信息已经在内存中。对于三种分配策略（连续的、链接的和索引的）中的每一种，回答这些问题：
a. How is the logical-to-physical address mapping accomplished in this system? (For the indexed allocation, assume that a file is always less than 512 blocks long.)
在这个系统中，逻辑到物理地址的映射是如何完成的？对于索引分配，假设一个文件的长度总是小于 512 块）。
b. If we are currently at logical block 10 (the last block accessed was block 10) and want to access logical block 4, how many physical blocks must be read from the disk?
如果我们目前在逻辑块 10（最后访问的是块 10），想要访问逻辑块 4，必须从磁盘上读取多少个物理块？
答：
Let Z be the starting file address (block number).
Contiguous. Divide the logical address by 512 with X and Y the resulting quotient and remainder respectively.
a. Add X to Z to obtain the physical block number. Y is the displacement into that block.
b. 1Linked (FAT approach). Divide the logical physical address by 512 with X and Y the resulting quotient and remainder respectively.
a. Chase down the linked list (getting X + 1 blocks). Y is the displacement into the last physical block.
b. 4Indexed. Divide the logical address by 512 with X and Y the resulting quotient and remainder respectively.
a. Get the index block into memory. Physical block address is contained in the index block at location X. Y is the displacement into the desired physical block.
b. 2设 Z 为起始文件地址（块号）。
毗连。用逻辑地址除以 512，X 和 Y 分别为所得商和余数。
a. 将 X 加到 Z，得到物理块的编号。Y 是进入该块的位移。
b. 1链接（FAT 方法）。将逻辑物理地址除以 512，X 和 Y 分别为所得的商和余数。
a. 向下追赶链接列表（得到 X+1 个块）。Y 是进入最后一个物理块的位移。
b. 4索引的。用逻辑地址除以 512，X 和 Y 分别为所得商和余数。
a. 在内存中获取索引块。物理块地址包含在索引块的位置 X，Y 是进入所需物理块的位移。
b. 2
12.16 consider a file system that uses inodes to represent files. Disk blocks are 8 KB in size, and a pointer to a disk block requires 4 bytes. This file system has 12 direct disk blocks, as well as single, double, and triple indirect disk blocks. What is the maximum size of a file that can be stored in this file system?
考虑一个使用 inodes 来表示文件的文件系统。磁盘块的大小为 8KB，一个磁盘块的指针需要 4 个字节。这个文件系统有 12 个直接磁盘块，以及单个、两个和三个间接磁盘块。在这个文件系统中，可以存储的最大文件大小是多少？
答：
(12 * 8 /KB/) + (2048 * 8 /KB) + (2048 * 2048 * 8 /KB/) +(2048 * 2048 * 2048 * 8 /KB) = 64 terabytes
12.19* Explain why logging metadata updates ensures recovery of a file system after a file-system crash.
**(不做要求)**解释为什么记录元数据更新可以确保文件系统崩溃后的恢复。
答：
For a file system to be recoverable after a crash, it must be consistent or must be able to be made consistent. Therefore, we have to prove that logging metadata updates keeps the file system in a consistent or able-to-be-consistent state. For a file system to become inconsistent, the metadata must be written incompletely or in the wrong order to the file system data structures. With metadata logging, the writes are made to a sequential log. The complete transaction is written there before it is moved to the file system structures. If the system crashes during file system data updates, the updates can be completed based on the information in the log. Thus, logging ensures that file system changes are made completely (either before or after a crash). The order of the changes is guaranteed to be correct because of the sequential writes to the log. If a change was made incompletely to the log, it is discarded, with no changes made to the file system structures. Therefore, the structures are either consistent or can be trivially made consistent via metadata logging replay.
为了使文件系统在崩溃后能够恢复，它必须是一致的，或者必须能够被变成一致的。因此，我们必须证明，记录元数据更新可以使文件系统处于一致或能够一致的状态。要使文件系统变得不一致，元数据必须被不完全地或以错误的顺序写入文件系统的数据结构中。有了元数据日志，写到了一个连续的日志。完整的事务在被转移到文件系统结构之前被写入那里。如果系统在文件系统数据更新期间崩溃，可以根据日志中的信息完成更新。因此，日志保证了文件系统的变化是完整的（无论是在崩溃之前还是之后）。由于对日志的顺序写入，变化的顺序被保证是正确的。如果对日志的修改不完整，它就会被丢弃，而对文件系统结构不做任何修改。因此，这些结构要么是一致的，要么是可以通过元数据日志重放来实现一致的，很简单。
注：
翻译：deepl
参考资料：
[1] Operating System Concepts – 9th Edition 及其答案
