CMPS 111 - Fall 2005 Prof. Scott Brandt Final Exam Due Tuesday, December 6, 2005 at midnight (via submit) Name : Email : Student ID: Read ALL of the following before beginning the exam: 1. This is an open book, open note exam. You may use anything in your notes, the book, or on the class web page to answer the questions. You may also use other sources, including other books and the web, HOWEVER, the answers you submit must be 100% your own AND you must provide a full citation for any source you use beyond those directly associated with the class. 2. Exam rules apply. You may not discuss any of the questions or solutions with ANYONE and all of the work MUST be your own. Although the primary consequence of cheating is that you will receive a degree without learning to be a competent computer scientist or engineer, anyone caught cheating will also receive an F in the class and a letter will be sent to the provost of their college (who may impose additional sanctions). Although it is my hope that everyone gets an A, anyone doing suspiciously well on the exam may be required to take an oral exam to demonstrate that they actually understand their answers. 3. The exam is due on or before midnight on Tuesday, Dec. 6. Submit your solution in text format using the "submit" command. The assignment is "final". I suggest that you use "peek" to verify that you have correctly submitted your exam, as it will be difficult or impossible to accomodate anyone who does not submit their exam correctly or on time. Note that a subsequent submission will overwrite a previous one, so it is possible (and maybe a good idea) to submit a draft early and then submit revisions later. 4. You may email me with any questions you have but my response will probably be that I cannot answer the question. If I need to communicate with everyone, I will do so through the news section of the class web page, so check it occasionally. As always, if a question is ambiguous, you should make a reasonable assumption about what the question means, write it down, and answer the question accordingly. If your assumption is reasonable and your answer is correct under that assumption, you will receive full credit. Good luck. - Prof. Brandt ----- There are 12 questions each worth 10 points. --- 1. Early Intel processors such as the 8086 did not support dual-mode operation (user and supervisor modes). This had a fairly major impact on the type of system that could be implemented on these processors, and most did not support multi-user operation. a. Discuss two specific problems that could arise in trying to support multi-user operation on a processor that doesn't support dual-mode operation. b. Explain how the trap() instruction in modern systems supports multi-user operation, including a brief explanation of how it works. ----- 2. For each of the following operations, explain whether or not a system call is required, and why or why not. If a system call is required, explain which one. a. Creating a new process b. Killing a process c. Reading from a file d. Displaying something on the monitor e. Writing to memory ----- 3. We discussed how priority-based scheduling is in some sense the most general, because it can easily emulate other scheduling algorithms with appriately assigned priorities. Suppose that you have an operating system that implements priority-based scheduling, but lets the user specify how the priorities are assigned to his/her processes. Explain how the priorities should be set to implement each of the following scheduling algorithms. a. First-come first-served b. Shortest job next (non-preemptive) c. Round-robin (not exactly the same as FCFS) d. Multi-level feedback queues e. Earliest deadline first. This is a real-time scheduling algorithm where each process consists of a sequence of jobs, each job has a deadline -- a time when that job must complete -- and each job is put into the ready queue at the deadline of the previous job in the same task. ----- 4. Deadlock a) Name and briefly describe the four conditions that must hold for deadlock to occur b) Name and briefly describe the four strategies for dealing with deadlock ----- 5. Given four page frames and the memory reference string below, show what will be in each page frame after each reference using the following page replacement algorithms. Put a * above each page that causes a page fault. a) FIFO 2 1 3 4 0 2 4 1 1 3 0 4 2 5 5 3 P0 P1 P2 P3 b) LRU 2 1 3 4 0 2 4 1 1 3 0 4 2 5 5 3 P0 P1 P2 P3 c) Optimal 2 1 3 4 0 2 4 1 1 3 0 4 2 5 5 3 P0 P1 P2 P3 ----- 6. Most systems we use have specialized memory management hardware and software that pages portions of an applications address space in and out of memory. Explain: a) What the hardware is and what it does b) What the software is and what it does ----- 7. Disk requests come in to the disk driver for cylinders 40, 37, 19, 28, 40, 6, and 38, in that order. A seek takes 6 milliseconds per cylinder moved. Assuming that the read/write head starts at cylinder 18, how much seek time is required to satisfy all of these requests using: a) First-come-first-served b) Shortest seek time first c) SCAN d) C-LOOK ----- 8. In the original DOS operating system, disk blocks in a partition (both free and allocated) were managed by a File Allocation Table that implements a form of linked allocation. The FAT is a big table that has one entry per disk block. Free blocks are indicated by a special value (e.g., 0) in the appropriate entry in the FAT. The directory entry for a file contains the index of the first block of the file, and the index corresponds to both the entry in the FAT for that block and the block's logical address in the partition. The FAT entry for the first block of the file contains the index of the next block, and so on, until the entry for the last block, which contains a special value (e.g., -1) to indicate that there are no more blocks in the file. Briefly describe how to implement an efficient file system consistency checker for a FAT file system that verifies that a) only free blocks are marked free, b) only allocated blocks are marked allocated, and c) each allocated block is allocated to exactly one file. ----- 9. Modern high-performance storage systems stripe each file across many storage devices. In such systems, the I/O required to get the data off the storage system and to the processor(s) that need it can be considerable. Interestingly, the storage devices themselves may have a CPU capable of running some code in addition to servicing disk read and write requests. I have an idea: In order to reduce the I/O in the system, we could allow applications to send a small amount of code to the storage system(s) to operate on (pre-process?) the data in place. a) Discuss the benefits that this would provide. Give some examples of applications for such a mechanism. b) Discuss the potential problems that would arise from such a mechanism and, if possible, ways to address them. ----- 10. Magnetic RAM is a new type of non-volatile random-access memory (RAM). It is almost as fast as DRAM, but a bit more expensive and somewhat lower density. It would not currently be feasible to replace the system RAM with MRAM, but it would be possible to include some MRAM in a high-performance storage system. Based on what you have learned about memory hierarchies and storage systems in this class, describe two ways in which a moderate amount of MRAM (say, 512 MB) might be used to increase the performance of a file system. ----- 11. In a distributed storage system, metadata and data are often handled by different computers. That means that an application running on a client computer must first contact a metadata server to open a file (and get its permissions checked), and then contact the data servers to read or write the file. The problem is that the data server has no way of knowing if the client has permissions for the data -- the checking was done on the metadata server. Based on what you have learned about security, explain how the metadata server could provide a credential to the clients that the clients could subsequently provide to the data servers to prove that they have the permissions they claim to have. Assume that we don't trust the clients, and that the data servers and metadata servers never directly communicate. ----- 12. Assume that you have a partition with a FAT File system as described in Question #9 above, and that the FAT table is stored in the partition immediately before the data area of the partition, and is exactly the right size to represent all and only the blocks in the data area of that partition. Suppose that you wanted to expand the partition (and therefore the FAT file system) so that it contained more disk blocks by extending the end of the partition. Describe what steps would have to be done to successfully accomplish the expansion without destroying any user data.