Department of Computer Science

Department information

 

Operating Systems, Fall 2008, Exercise 3

These homework exercises will be covered in practice sessions on week 38 (Thu 18.9. or Fri 19.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:

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

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)

Covered in the class, but solved in advance:

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 foru 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	Last ref.	R	M
   0	126	1	0
   1	230	0	1
   2	140	0	0
   3	110	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?

   Corrected: one column added
   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

---

Tiina.Niklander@cs.helsinki.fi