Operating Systems, Fall 2008, Exercise 5
These homework exercises will be covered in practice sessions on week 40 (Thu 2.10. or Fri 3.10). Each week one of the questions must be submitted on paper to the teacher.
You need (at least to try hard) to solve all of the questions in advance, that is before the meeting. In the meeting we will discuss about the questions and their solutions. There is no time to solve them there. Solutions to the homework are not provided afterwards.
The weekly meetings are important for your learning. They give you structure for the course and support you in learning the content. They also give you some hints about the exam.
During the meeting, you will also have possibility to ask about the parts you feld were difficult to understand. This is your opportunity to make sure that you master the material well.
This third week's homework covers memory management.
RETURN ON PAPER:
- Write (In Finnish or in English) a short (approximately 1 page) answer to the question:
The focus of this question is in the hardware-software interaction.
Newer Pentium processors include instruction counter that increments with the clock signal. In other words a continuosly increasing counter that could be used as a time stamp (and in fact Linux kernel uses it as a time keeping device when it is available because it is much more accurate than any other device available for the kernel). The processor also knows the format of the page table entry and could include a counter in the entry that would tell the latest access or modification time of the given page. Why does the processor NOT support this mechanism which would make ease implementing LRU algorithms for the memory management. Explain in details.
More information about the counter is on page http://en.wikipedia.org/wiki/RDTSC.
If you find it too difficult to think why not to use it, then please create a scenario where such a counter exists and walkthrough its usage in details. The key here is in details. How would you implement such a system. You should think about the cooperation of hardware and software, the architecture of the system and the way instructions are executed.
- List the items or concepts you learned this week from the book, other material or the exercises?
- List in a prioritized list items or concepts you would like to be covered/clarified at the last lecture.
- Based on your current experience, what grade would you give yourself at the moment about the course. (How well do you feel you master the content)
Solve in advance for the class meeting:
- Backups
- Tan08 Problem 4.22: Oliver Owl's night job at the university computing center is to change the tapes used for overnight data backups. While waiting for each tape to complete, he works on writing his thesis that proves Shakespeare's plays were written by extraterrestrial visitors. His text processor runs on the system being backed up since that is the only one they have. Is there a problem with this arrangement?
- Tan08 Problem 4.23: We discussed making incremental dumps in some detail in the text. In Windows, it is easy to tell when to dump a file because every file has an archive bit. This bit is missing in UNIX. How do UNIX backup programs know which files to dump?
- NFS
- Study the NFS system in general. What are the main differences between NFS versions 3 and 4?
- What external directories and where do the department's Linux classroom computer mount at boot?
- RAID
- Sta08 11.11: It should be clear that disk striping can improve the data transfer rate when the strip size is small compared to the I/O request size. It should also be clear that RAID 0 provides improved performance relative to a single large disk, because multiple I/O requests can be handled in parallel. However, in this latter case, is disk striping necessary? That is does disk striping improve I/O request rate performanre compared to a comparable disk array without striping?
- Sta08 11.12: consider a 4-drive, 200GB-per-driove RAID array. What is the available data storage capacity for each of the RAID levels 0, 1, 3, 4, 5, and 6?
- Which RAID level would be best for performance? How should one organize the data to maximize performance?
- Which RAID level would be best for reliability? How should one organize the data to maximize reliability?
- Tan08 5.24: Disk requests come in to the disk driver for cylinders
10, 22, 20, 1, 40, 6, and 38, in that order. A seek takes 6 msec per
cylinder moved. How much seek time is needed for
- Fist-come, first served.
- Closest cylinder next (a.k.a. shortest seek first).
- Elevator algorithm (initially moving upward).
- Disk capacity and transfer times
- Sta08 11.7: Calculate how much disk space (in sectors, tracks and surfaces) will be required to store 90,000 200-byte logical records if the disk is fixed-sector with 512 bytes/sector, 128 sectors per track, 130 tracks per surface, and 12 usable surfaces. Ignore any file header record(s) and track indices, and assume that a record cannot span two sectors.
- Sta08 11.8: Suppose that the above disk rotates at 1200 rpm. The disk controller can read a sector into its internal buffer in one revolution, and then interrupts the processor for each byt to be read by the operating system. If the interrupt service routine takes 1.8 usecs to process each interrupt, what is the expected transaction time to read one sector (disregard the seek time)? How much time can the operating system spend running other processes while the disk transaction is completing?
- Sta08 11.9: Consider again the same disk system, but suppose DMA is used between the disk controller and system memory over a 2Mbyte/sec bus. Now, what is the expected transaction time? How much of this can be used for running other processes?
- Rate Monotonic and Earliest Deadline First
Develop two scheduling diagrams (execution sequence in time line) for the following three processes, one using RM and the other using EDF scheduling of the processes. Assume the deadline for each period to be at the end of the period. You may also assume that on each period, the process will be ready to run immediately when the priod starts.
It is enough to simulate the execution from time 0 to time 100. After time 100 the schedule will repeate.
Process Period Execution time A 20 10 B 25 5 C 50 15