The final exam will take place on Thursday May 9, 2:00 - 3:50 in room 703, Main Building. It will be closed book and closed notes. It will be cumulative, covering material from the entire course, but emphasizing more the material from the second half (since the first half was already tested in the midterm.)
The following are some sample questions that might be asked about the material in the second half of the course. This is NOT a sample exam; the real exam will have some questions from the first half, and fewer questions from the second half.
Answer: 11, 15, 16, 8, 3, 1
`T', `h', `r', `e', `e', Delete key, Delete key, Delete key, `e', `r', `e', Carriage return.If keyboard input is in raw mode, how many characters are passed to the user program? What if it is in cooked mode?
Answer: Raw mode: 12. Cooked mode: 6 including the carriage return.
File name | First block | Size in bytes --------------------------------------- AA 5 1350 BB 7 2200(The other information in the directory is omitted.) The current state of the FAT is
0 -- FREE 1 -- FREE 2 -- -1 3 -- 4 4 -- -1 5 -- 2 6 -- FREE 7 -- 3 8 -- FREEThe system uses a block size of 1 Kbyte. What is the last block of file BB? How many bytes of that block are used? (Useful fact: 1K=1024).
Answer: The blocks of BB are 7, 3, 4. Since BB has length 2200 and blocks 7 and 3 hold 2048 bytes, there are 152 bytes used in block 4.
A. 3*1024+50 = 3122.
B. Any virtual address between 2048 and 3071 or between 4096 and 5119.
For example, suppose that the page size is 1Kbyte, and the program contains routines ``main'' of 750 bytes; ``a'' of 1000 bytes; ``b'' of 1200 bytes; and ``c'' of 200 bytes. Ordinarily, the linker would place ``main'' in bytes 0-749; ``a'' in 750-1749; ``b'' in 1750-2949; and ``c'' in 2950-3150. However, a linker sensitive to paging might put ``main'' in 0-749; ``c'' in 750-950; ``a'' in 1024-2023; and ``b'' in 2048-3247. (Note: 1K = 1024; 2K = 2048; 3K = 3072.)
Name one advantage and one disadvantage of this placement scheme.
Answer: Advantage: Assuming that the program counter tends to stay in the program text of one routine at a time, this should reduce the number of page faults. Disadvantage: More pages are required due to greater internal fragmentation. This may lead to more page faults, if several routines are in the working set at once.
Answer: (Note: this is a lot more detail than I would expect on an exam answer. Also, the exact steps and the division of the steps among components of the system can vary a lot from one system to another.)
The device-independent software passes to the device driver the number of bytes to be read, the address in user space to read them into, and the file pointer. It then traps to the kernel. The kernel blocks the process and calls the device driver from the top. The device driver determines that the next byte is on a block B not in memory. It finds the address of B from the i-node (presumably in memory). It issues a request to the device controller to read B into memory. The device controller translate the block number of B into a set of consecutive sectors on a track, and instructs the actual disk to read those sectors. The disk moves the arm to the correct track, waits for the disk to rotate to the proper sectors, and reads the information, putting the output into the disk controller's buffer. The disk controller issues a interrupt. The interrupt handler in the kernel sends control to the bottom of the disk driver. The disk driver transfers the block of data from the disk contoller's buffer to the file cache, and transfers the byte of data to the specified address in user space. The kernel unblocks the process and schedules it to run. The device-independent software finds its data where it expects, and returns control to the user process.
1. Implementing non-contiguous memory (i.e. paging) for core memory effectively is difficult, as address translation must be performed very efficiently more than once per instruction cycle. Highly specialized hardware is required, and this is not always available. By contrast for disk addressing, translation from a byte number to a block number need only be done when the block is read in or out which is much more infrequent.
2. Using contiguous memory always raises the problem of external fragmentation. In core memory, though this problem is serious, it is not catastrophic; a process can be kept suspended on disk until space opens up for it in core, or until the kernel decides to swap some other processes out to make room for it. These options are not available in disk; there is nowhere else off the disk to keep a file while waiting for space to open up on the disk.
Answer: The TLB is used to improve the efficiency of a paging system. It is a very fast associative memory that holds pairs of the form < page number, frame number > for recently used pages of the current process. Each time the process generates a virtual address, the hardware first checks the TLB to see if the frame for that page is recorded there; if not, it goes to the relatively slow page table.
Answer: The R bit is 1 if the page has been referenced since the last clock tick. The M bit is 1 if the page has been modified since it was read in. At each machine instruction, the R bit for any page of any virtual address referenced is set to 1. The M bit is set to 1 if the process writes to that page. The R bit is reset to 0 at each clock tick. The M bit is reset to 0 when the page is written out to disk. In the NRU algorithm, pages are divided into 4 categories: