Department of Computer Science

Department information

 

Operating Systems, Fall 2009, Exercise 3

These homework exercises will be covered in practice sessions on week 39 (Finnish Tue 22.9 and English Fri 25.9.). Each week answers to one special question must be submitted on paper to the teacher.

Study the material and solve the questions before the meeting. In the meeting you can get answers to all unclear issues.

This third week's homework covers memory management.

SPECIAL QUESTION (return on paper):

1. Write (In Finnish or in English) a short (1/2 -1 page) answer to the question and return it on paper in the class.

   Give a simple example of a page reference sequence where the first page selected for replacement will be different for the clock and least recently used (LRU) page replacement algorithms. Assume that a process is allocated 3 frames, and the reference string contains page numbers from the set 0,1,2,3. Explain carefully why the algorithms make a difference selection.

WEEKLY QUESTIONS (covered in class only):

1. Tan 08 Problem 3.3: In this problem you are to compare the storage needed to keep track of free memory using bitmap versus using a linked list. The 128-MB memory is allocated in units of n bytes. For the linked list, assume that memory consists of an alternating sequence of allocated segments and holes, each 64 KB. Also assume that each node in the linked list needs a 32-bit memory address, a 16-bit length, and a 16-bit next-node field. How many bytes of storage is required for each method? Which one is better?

2. Tan08 Problem 3.4: Consider a swapping system in which memory consists of the following hole sizes in memory order: 10 KB, 4 KB, 20 KB, 18 KB, 7 KB, 9 KB, 12 KB, and 15 KB. Which hole is taken for successive segment requests of a) 12 KB, b) 10 KB, and c) 9 KB for first fit? Now repeat the question for best fit, worst fit and next fit.

3. Tan08 Problem 3.5: For each of the decimal virtual address, compute the virtual page number and offset for a 4-KB page and for 8-KB page: 20000, 32768, 60000.

4. Tan08 Problem 3.10: Suppose that a machine has 48-bit virtual addresses and 32-bit physical addresses.
   1. if pages are 4 KB, how many entries are in the page table if it has only a single-level? Explain.
   2. Suppose this same system has a TLB (Translation Lookaside Buffer) with 32 entries. Furthermore, suppose that a program contains instructions that fit into one page and it sequentially reads long integer elements from a array that spans thousands of pages. How effective will the TLB be for this case?

5. Tan08 Problem 3.14: A computer has 32-bit virtual addresses and 4-KB pages. The program and data together fit in the lowest page (0-4095). The stack fits in the highest page. How many entries are needed in the page table if traditional (one-level) paging is used? How many page table entries are needed for two-level paging, with 10 bits in each part?

6. Tan08 Problem 3.28: A computer has four page frames. The time of loading, time of last access, and the R and M bits for each page are as shown below (the times are in clock ticks):

   Page	Loaded	Last ref.	R	M
   0	126	280	1	0
   1	230	265	0	1
   2	140	270	0	0
   3	110	285	1	1

   1. Which page will NRU replace?
   2. Which page fill FIFO replace?
   3. Which page will LRU replace?
   4. Which page will second chance replace?
   5. Which page will clock replace?

---

Tiina.Niklander@cs.helsinki.fi