Department of Computer Science

Department information

 

Operating Systems, Fall 2006, Homework 5

This homework will be covered in practise session on Thursday 5.10.2006 (week 40).

The homework and practice sessions will follow the normal department's practise. The homework is solved and done in advance, that is before the practise session. You may solve the problems alone or in a small group. The practise session is used to discuss about different solutions.

The team task for part 2 is available from the course page. The deadline for the team task in Frdiay November, 3.

The exercises are based on chapters 7 and 8.1.

1. Dynamic partitioning
   • Problem 7.6 from course book [Stal05]: (The problem is not available in the 4th edition.)
     A dynamic partitioning scheme is being used, and the following is the memory configuration at a given point of time: (A - allocated, F - free)
     A 20M, F 20M, A 40M, F 60M, A 20M, F 10M, A 60M, F 40M, A 20M, F 30M, A 40M, F 40M
     The next three memory requests are for 40M, 20M and 10M. Indicate the starting address for each of the three blocks using hte followin placement algorithms:
     1. First-fit
     2. Best-fit
     3. Next-fit. Assume the most recently added block is at the beginning of the memory.
     4. Worst-fit

2. Buddy system
   • Problem 7.7 from course book [Stal05]: (The problem is not available in the 4th edition.)
     A 1-Mbyte block of memory is allocated using tthe buddy system.
     1. Show the results of the following sequence in a figure similar to the Figure 7.6: Request 70; Request 35; Request 80; Return A; Request 60; Return B; Return D; Return C.
     2. Show the binary tree representation following Return B.

3. Paging and segmentation
   1. Problem 7.12 from course book [Stal05]. The problem is not available in the 4th edition.
      Consider a simple paging system with the following parameters: 2 to the power 32 bytes of physical memory; page size of 2 to the power of 10 bytes; 2 to the power of 16 pages of logical address space.
      1. How many bits are in a logical address?
      2. How many bytes in a frame?
      3. How many bits in the physical address specify the frame?
      4. How many entries in the page table?
      5. How many bits in each page table entry? Assume each page table entry includes a valid /invalid bit.
   2. Problem 7.14 from course book [Stal05]. The problem is not available in the 4th edition.
      Consider a simple segmentation system that has the following segment table:

      Starting address	Length (bytes)
      660	248
      1752	422
      222	198
      996	604

      For each of the following logical address, determine the physical addresses of indicate if a segmentation fault occurs:
      1. 0, 198
      2. 2, 156
      3. 1, 530
      4. 3, 444
      5. 0, 222

4. Paged virtual memory
   • Problem 8.10 from course book [Stal05]. (Problem 8.8. in [Stal01])

---

Tiina.Niklander@cs.helsinki.fi