Homework 4, released on Nov 7, 2000. CS414 FA2000 Due in class Nov 16, 2000

Please hand in your answers as follows: not handwritten (except drawings), 11-pt Times or 10-pt Courier font, minimum of .5" margins. Problems must be grouped (1-2, 3-4, 5, 6, 7) on separate sheets of paper (total 5 sheets). Your name and id should be written on each sheet of paper you submit. Please write the question numbers in the sheet in bold. Every item is worth 5 points, unless otherwise marked.

Late homeworks accrue 10% penalty for the first 24 hours, 15% if handed in before 4pm on Friday, 25% if handed in on Monday before 10am, 35% on Tuesday in class. Homeworks will not be accepted after that. Collaboration is permitted in groups of at most 2 people for this homework. Add both names to answer sheets in case of a group. Late homeworks are to be handed to Tammy Howe in 4119C.

 

PAGE REPLACEMENT

  1. Why is LRU difficult to implement in hardware? What is a good approximation (mention it by name and describe the scheme briefly)?

  2. Why does LRU or any other page replacement algorithm depend on hardware? Describe the role of the MMU (memory management unit) hardware in paging and page replacement systems.

    3.  

    I/O SYSTEMS

  3. When is interrupt-driven I/O or polling I/O better? State your metric and explain your answer. This question is in the spirit of book question 12.5. If you use the example in question 12.5 or the network interface card example given in class, you will still need to generalize and give a different example.

  4. Depending on the system component interconnection, DMAs may increase or decrease the performance of the system. Explain in which situations DMA increases system performance, and why. Include the system architecture (that is, mention how components are connected) in your answer.

  5. 10 points How would you implement a keyboard interrupt handler and the echo onto the screen? Assuming that these are the only two hardware devices you have to worry about, what would be your design? Mention whether there is need for masking or not, where the interrupt handler is located, how data is handled, whether it is a block or character device, etc. If the system devices include disk, clock, CD-ROM, microphone, what would the relative interrupt level/number be, with respect to these other devices?

    6.  

    FILE SYSTEMS

  6. Consider a hierarchical (tree-like, Unix-based) system of character files with root directory "root". Files are allocated contiguously. The block size of the file system is 1000 bytes (a character occupies one byte). Assume that the main memory initially holds no file system information. Main memory is very large. The file "root/mydir/myfile" contains 10500 characters.

    1. 10 points A process wishes to Open "root/mydir/myfile". Assuming each I/O operation retrieves a single block or a single inode from the disk, how many I/O operations are needed to perform this Open command. Describe what each I/O operation retrieves from the disk.

    2. After opening the file, the process wishes to Read characters 5300 to 7200 from the file. Since main memory is large, all of the data retrieved while "myfile" was being opened are still in it. How many I/O operations are required for this Read, and what does each operation retrieve from disk?

    3. After reading "myfile", the process wishes to open another file, called "root/mydir/myotherfile". Main memory is very large, so all data retrieved while "myfile" was being opened and read are still in it. How many I/O operations are needed to open "myotherfile", and what does each operation retrieve? Do not worry about mutual exclusion: the operating system will do the mutual exclusion, if needed.

    4. What file organization would be best suited for the I/O operations described in items b. and c. (among contiguous, linked, indexed, etc)

  7. Files are written and read and modified throughout their lifetimes in the system. In programs that read, update, and write back contents, some file systems provide a read pointer and a write pointer, to allow for flexibility. Where will these pointers be kept, why, and what is the overhead of providing this service? Describe what happens to the read pointers when the file is written (for example, if some data is inserted in the middle of the file) and justify your choice? What if a user would like to have more than a single read or write pointer? How can this be accommodated in your design?