Problems

[Page 607 (continued)]

1.	NTFS uses Unicode for naming files. Unicode supports 16-bit characters. Give an advantage of Unicode file naming over ASCII file naming.
2.	Some files begin with a magic number. Of what use is this?
3.	Fig. 5-4 lists some file attributes. Not listed in this table is parity. Would that be a useful file attribute? If so, how might it be used?
4.	Give 5 different path names for the file /etc/passwd. (Hint: think about the directory entries "." and "..".)
5.	Systems that support sequential files always have an operation to rewind files. Do systems that support random access files need this too?
6.	Some operating systems provide a system call rename to give a file a new name. Is there any difference at all between using this call to rename a file, and just copying the file to a new file with the new name, followed by deleting the old one?
7.	Consider the directory tree of Fig. 5-7. If /usr/jim/ is the working directory, what is the absolute path name for the file whose relative path name is ../ast/x?
	[Page 608]
8.	Consider the following proposal. Instead of having a single root for the file system, give each user a personal root. Does that make the system more flexible? Why or why not?
9.	The UNIX file system has a call chroot that changes the root to a given directory. Does this have any security implications? If so, what are they?
10.	The UNIX system has a call to read a directory entry. Since directories are just files, why is it necessary to have a special call? Can users not just read the raw directories themselves?
11.	A standard PC can hold only four operating systems at once. Is there any way to increase this limit? What consequences would your proposal have?
12.	Contiguous allocation of files leads to disk fragmentation, as mentioned in the text. Is this internal fragmentation or external fragmentation? Make an analogy with something discussed in the previous chapter.
13.	Figure 5-10 shows the structure of the original FAT file system used on MS-DOS. Originally this file system had only 4096 blocks, so a table with 4096 (12-bit) entries was enough. If that scheme were to be directly extended to file systems with 232 blocks, how much space would the FAT occupy?
14.	An operating system only supports a single directory but allows that directory to have arbitrarily many files with arbitrarily long file names. Can something approximating a hierarchical file system be simulated? How?
15.	Free disk space can be kept track of using a free list or a bitmap. Disk addresses require D bits. For a disk with B blocks, F of which are free, state the condition under which the free list uses less space than the bitmap. For D having the value 16 bits, express your answer as a percentage of the disk space that must be free.
16.	It has been suggested that the first part of each UNIX file be kept in the same disk block as its i-node. What good would this do?
17.	The performance of a file system depends upon the cache hit rate (fraction of blocks found in the cache). If it takes 1 msec to satisfy a request from the cache, but 40 msec to satisfy a request if a disk read is needed, give a formula for the mean time required to satisfy a request if the hit rate is h. Plot this function for values of h from 0 to 1.0.
18.	What is the difference between a hard link and a symbolic link? Give an advantage of each one.
19.	Name three pitfalls to watch out for when backing up a file system.
20.	A disk has 4000 cylinders, each with 8 tracks of 512 blocks. A seek takes 1 msec per cylinder moved. If no attempt is made to put the blocks of a file close to each other, two blocks that are logically consecutive (i.e., follow one another in the file) will require an average seek, which takes 5 msec. If, however, the operating system makes an attempt to cluster related blocks, the mean interblock distance can be reduced to 2 cylinders and the seek time reduced to 100 microsec. How long does it take to read a 100 block file in both cases, if the rotational latency is 10 msec and the transfer time is 20 microsec per block?
	[Page 609]
21.	Would compacting disk storage periodically be of any conceivable value? Explain.
22.	What is the difference between a virus and a worm? How do they each reproduce?
23.	After getting your degree, you apply for a job as director of a large university computer center that has just put its ancient operating system out to pasture and switched over to UNIX. You get the job. Fifteen minutes after starting work, your assistant bursts into your office screaming: "Some students discovered the algorithm we use for encrypting passwords and posted it on the Internet." What should you do?
24.	Two computer science students, Carolyn and Elinor, are having a discussion about i-nodes. Carolyn maintains that memories have gotten so large and so cheap that when a file is opened, it is simpler and faster just to fetch a new copy of the i-node into the i-node table, rather than search the entire table to see if it is already there. Elinor disagrees. Who is right?
25.	The Morris-Thompson protection scheme with the n-bit random numbers was designed to make it difficult for an intruder to discover a large number of passwords by encrypting common strings in advance. Does the scheme also offer protection against a student user who is trying to guess the superuser password on his machine?
26.	A computer science department has a large collection of UNIX machines on its local network. Users on any machine can issue a command of the form machine4 who and have it executed on machine4, without having the user log in on the remote machine. This feature is implemented by having the user's kernel send the command and his uid to the remote machine. Is this scheme secure if the kernels are all trustworthy (e.g., large timeshared minicomputers with protection hardware)? What if some of the machines are students' personal computers, with no protection hardware?
27.	When a file is removed, its blocks are generally put back on the free list, but they are not erased. Do you think it would be a good idea to have the operating system erase each block before releasing it? Consider both security and performance factors in your answer, and explain the effect of each.
28.	Three different protection mechanisms that we have discussed are capabilities, access control lists, and the UNIX rwx bits. For each of the following protection problems, tell which of these mechanisms can be used. (a) Ken wants his files readable by everyone except his office mate. (b) Mitch and Steve want to share some secret files. (c) Linda wants some of her files to be public. For UNIX, assume that groups are categories such as faculty, students, secretaries, etc.
29.	Can the Trojan horse attack work in a system protected by capabilities?
30.	The size of the filp table is currently defined as a constant, NR_FILPS, in fs/const.h. In order to accommodate more users on a networked system you want to increase NR_PROCS in include/minix/config.h. How should NR_FILPS be defined as a function of NR_PROCS?
31.	Suppose that a technological breakthrough occurs, and that nonvolatile RAM, which retains its contents reliably following a power failure, becomes available with no price or performance disadvantage over conventional RAM. What aspects of file system design would be affected by this development? [Page 610]
32.	Symbolic links are files that point to other files or directories indirectly. Unlike ordinary links such as those currently implemented in MINIX 3, a symbolic link has its own i-node, which points to a data block. The data block contains the path to the file being linked to, and the i-node makes it possible for the link to have different ownership and permissions from the file linked to. A symbolic link and the file or directory to which it points can be located on different devices. Symbolic links are not part of MINIX 3. Implement symbolic links for MINIX 3.
33.	Although the current limit to a MINIX 3 file size is determined by the 32-file pointer, in the future, with 64-bit file pointers, files larger than 232 1 bytes may be allowed, in which case triple indirect blocks may be needed. Modify FS to add triple indirect blocks.
34.	Show if setting the (now-unused) ROBUST flag might make the file system more or less robust in the face of a crash. Whether this is the case in the current version of MINIX 3 has not been researched, so it may be either way. Take a good look at what happens when a modified block is evicted from the cache. Take into account that a modified data block may be accompanied by a modified i-node and bitmap.
35.	Design a mechanism to add support for a "foreign" file system, so that one could, for instance, mount an MS-DOS file system on a directory in the MINIX 3 file system.
36.	Write a pair of programs, in C or as shell scripts, to send and receive a message by a covert channel on a MINIX 3 system. Hint: A permission bit can be seen even when a file is otherwise inaccessible, and the sleep command or system call is guaranteed to delay for a fixed time, set by its argument. Measure the data rate on an idle system. Then create an artificially heavy load by starting up numerous different background processes and measure the data rate again.
37.	Implement immediate files in MINIX 3, that is small files actually stored in the i-node itself, thus saving a disk access to retrieve them.