Department of Computer Science

Department information

 

Operating Systems, Fall 2008, Exercise 4

These homework exercises will be covered in practice sessions on week 39 (Thu 25.9. or Fri 26.9). 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:

1. Write (In Finnish or in English) a short (1/2 -1 page) answer to the question:

   What would happen if the bitmap or free list containing the information about free disk blocks was completely lost due to crash? Is there any way to recover from this disaster, or is it bye-bye disk? Discuss your answer for UNIX and the FAT-16 file system separately.

2. List the items or concepts you learned this week from the book, other material or the exercises?
3. List at least three items or concepts you would like to be covered more in the course in the future? (Items you found difficult or challenging)
4. 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)

Solved in advance for the class meeting:

1. Tan 08 Problem 3.21: Suppose that the virtual page reference stream contains repetitions of long sequences of page references followed occasionally by a random page reference. For example, the sequence: 0, 1, ..., 511, 431, 0, 1, ..., 511, 332, 0, 1, ... consists of repetitions of the sequence 0, 1, ..., 511 followed by a random reference to pages 431 and 332.
   1. Why won't the standard replacement algorithms (LRU, FIFO, Clock) be effective in handling this workload for a page allocation that is less than the sequence length?
   2. If this program were allocated 500 page frames, dcescribe a page replacement approach that would perform much better than the LRU, FIFO, or Clock algorithms.

2. Tan08 Problem 3.32: can a page be in two working sets at the same time? Explain.

3. Tan08 Problem 3.37: We consider a program which has the two segments shown below consisting of instructions in segment 0, and read/write data in segment 1. Segment 0 has read/execute protection, and segment 1 has read/write protection. The memory system is a demand-paged virtual memory system with virtual addresses that have a 4-bit page number and an 10-bit offset. The page tables and protection are as follows (all numbers in the table are in decimal):

   Segment 0		Segment 1
   Read/Execute		Read/Write
   Virtual Page#	Page frame#	Virtual page#	Page frame#
   0	2	0	On Disk
   1	On Disk	1	14
   2	11	2	9
   3	5	3	6
   4	On Disk	4	On Disk
   5	On Disk	5	13
   6	4	6	8
   7	3	7	12

   For each of the following cases, either give the real (actual) memory address which results from dynamic address translation or identify the type of fault which occurs (either page or protection fault).

   1. Fetch from segment 1, page 1, offset 3
   2. Store into segment 0, page 0, offset 16
   3. Fetch from segment 1, page 4, offset 28
   4. Jump to location in segment 1, page 3, offset 32

4. Linux memory management maps a continuous virtual memory area into a continuous block of physical frames.
   1. What is the gain with this approach?
   2. What problems does it cause?
   Consider general memory management policies as well as physical device usage.

5. File information
   1. Tan08 Problem 4.1: In early UNIX systems, executable files (a.out files) began with a very specific magic number, not one chosen at random. These files began with a header followed by the text and data segments, Why do you think a very specific number was chosen for executable files, whereas other file types had a more-or-less random magic number as the first word?
   2. Tan08 4.2 (modified): If the file system supports record-structured files, one of the file attributes is the record length. Why does the operating system care about this?

6. System calls
   1. Tan08 Problem 4.3: Is the open system call in UNIX absolutely essential? What would the consequences be of not having it?
   2. Tan08 Problem 4.5: 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?

   ---

   Tiina.Niklander@cs.helsinki.fi