CS 481: Solution for Assignment #6

Problem 17.9.

• Yes, it is possible to have two file systems on a single disk drive. The mapping between a file system and a collection of disk blocks can easily be made to "see" only a part of the disk blocks on the drive, with the others being "seen" only by the other file system.
• Yes, it is possible to have a file system span two physical drives. Again, the mapping between a file system and a collection of blocks can include the drive ID along with the usual per-drive information (cylinder, surface, sector, etc.).
• A file not in a file system is entirely possible, but somewhat misleading. Such "files" tend to be superspecialized; an example is the boot block, a one-block "file" to be found at the front of a designated device from which the system tries to boot; another is the swap area.
• Is there a directory descriptor? Generally, no, because a directory is just another file, so that the descriptor for it is simply a normal file descriptor. A directory file may look very different from other data files, but the OS treats it at the highest level like any other file, with a file descriptor attached to it.
• Can a file span two file systems (the original file and the one mounted within it)? I confess that I am not sure I understand the question asked here. Clearly, we cannot have a single file that resides in part in one system and in part in another, which would seem to be what is implied by "span". The directory in which the new system is "grafted" will have an entry added to it, but it can hardly be said to "span" file systems.

Problem 17.19. This problem has 3 questions in all, each with two instances (the system described and the Unix system). Before tackling the questions, let us look at the two systems. The Unix file organization to be used is depicted in Figure 17.14; the file system described in the exercise differs in two respects: for very small files, it can store data in the first block, whereas the first block in Unix never stores data; and, for larger files, the system described in the exercise uses linked blocks, whereas Unix uses a forest of increasingly deep trees. For a lark, I'll take the values given in the text as exact...

• For 100 bytes, the exercise system uses just one block, with no pointers. Unix uses two blocks, one to contain the 100 bytes of data and another with the file descriptor and a pointer to the data block. So the exercise system saves one block over Unix---a 50% gain.

  For 10,000 bytes, the exercise system uses 9 blocks for data, all addressed in the header block, which thus stores 1024-64-36=924 bytes of data; the remaining 10,000-924=9,076 bytes are stored in 9 data blocks, the last of which is not quite full. Unix uses 10 blocks for data (9 blocks would only store 9216 bytes) and one block as descriptor with 10 pointers to the 10 blocks. So the exercise system saves one block over Unix---a 10% gain.

  For a million bytes, the exercise system needs 977 data blocks, the last only about half full. To address these many blocks, we need a chain of 4 blocks: the first addresses 239 blocks, the next three address 255, 255, and 228 (an incomplete pointer block), respectively. Thus 981 blocks in all. Unix gets 10 direct pointers to data blocks in its header block, storing 10,240 bytes in these 10 blocks, uses its 11th pointer for a block of 256 block addresses, storing another 262,144 bytes in 256 data blocks, then needs 711 more data blocks, which require a two-level structure, with one second-level block holding pointers to three first-level address blocks, the first two fully used and the third using only 199 of its 256 pointers. The total is thus 977 data blocks, a header block, and 5 pointer blocks, hence 983 blocks in all. The exercise structure saves two blocks over Unix ---a 2% gain.

  For one hundred million bytes, we will need 97,657 data blocks in either system. The exercise system uses 382 blocks for that purpose, in addition to the header block. The header block stores 339 pointers to data blocks, the next 381 blocks in the chain each store 255 pointers, and the last block in the chain stores 163 pointers. The total is thus 98,040 blocks. Unix gets 10 data blocks at the first level, 256 at the second level, and 65,536 at the third level, for a total of 65,802 data blocks, using the header block, a first-level address block, and a tree with one second-level address block and 256 first-level address blocks. This leaves another 31,855 data blocks that get addressed through a 3-level tree of address blocks. This tree needs 125 first-level blocks, and thus 1 second-level block (with 125 addresses) and one third-level block (with just one address). This is somewhat wasteful, but Unix files are built from the "small end". The total is 97,657 data blocks, a header block, and (1+1+256+1+1+125)=385 address blocks, for a total of 98,043 blocks. Thus the exercise system saves 3 blocks over Unix---a 0.003% gain.

• To read the whole file, both systems end up reading each disk block exactly once. Thus the number of disk reads is the number of disk blocks calculated in the previous part.
• To read the last byte of the file, the exercise system must traverse its chain of address blocks to the last block in the chain, then read the last block index in that chain. Unix must follow the last pointer in the header file; if that is a multi-level pointer, it follows by another disk block read from the last pointer in the previously read block, until it reads the data block. Thus, for the 100 bytes file, the exercise system takes 1 disk read and Unix takes 2---one more than the exercise system; for the 10,000 bytes file, both systems use 2 disk reads: the header block and a pointer to a data block; for the million-bytes file, the exercise system traverses a chain of 4 blocks and finishes by reading the data block, while Unix reads the header block, a second-level pointer block, a first-level pointer block, and the data block, for a total of 4 disk reads---one less than the exercise system; finally, for the 100-million-bytes file, the exercise system traverses a chain of 383 blocks (including the header) before reading the data block and so needs 384 disk reads, while Unix reads the header, a third-level address block, a second-level one, a first-level one, and the data block, for a total of 5 disk reads---a huge gain over the exercise system.

  We can conclude that the exercise system is roughly equivalent to the Unix system in storage except for very small files (less than 900 bytes), but loses in direct adressing (including addressing for appending, the most common operation to grow a file) on files larger than about a million bytes---losing very badly indeed on really large files.

Problem 19.13. The text describes its answer to this question on the bottom of page 795. It does not comment on Unix: but it is pretty clear that Unix has no mechanism for protection domain: the closest it comes to this is groups: a user can be a member of different groups and, as such, has the capabilities associated with each group. The problem is that a user has all of the capabilities of *all of the groups* to which she belongs... There is no way in Unix for a user to move from one group to another under controlled circumstances. The only real way to mimic this is to create multiple users for a single one; the user can then logout from his current identity and login in a new identity with different access privileges. That is, of course, clumsy and also insufficient: we still need groups to allow the various identities of the same user to share access to certain resources/files and we have no way to prevent "leaks" between the various identities, because altering privileges is automatically possible for any user that has write privilege on the file.