Operating Systems, Fall 2007, Homework 5
This homework will be covered in practise session on Thursday 4.10.2007 (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 Friday November, 2.
The exercises are based on chapters 7 and 8.
- 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 the following placement algorithms:- First-fit
- Best-fit
- Next-fit. Assume the most recently added block is at the beginning of the memory.
- Worst-fit
- Problem 7.6 from course book [Stal05]: (The problem is not available in the 4th edition.)
- 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 the buddy system.- 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.
- Show the binary tree representation following Return B.
- Problem 7.7 from course book [Stal05]: (The problem is not available
in the 4th edition.)
- Paging and segmentation
- 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.- How many bits are in a logical address?
- How many bytes in a frame?
- How many bits in the physical address specify the frame?
- How many entries in the page table?
- How many bits in each page table entry? Assume each page table entry includes a valid /invalid bit.
- 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:
For each of the following logical address, determine the physical address or indicate if a segmentation fault occurs:Starting address Length (bytes) 660 248 1752 422 222 198 996 604 - 0, 198
- 2, 156
- 1, 530
- 3, 444
- 0, 222
- Problem 7.12 from course book [Stal05]. The problem is not available in the 4th edition.
- Paged virtual memory
- Problem 8.2 from course book [Stal05]. The problem is not available in the 4th edition.
Consider a paged virtual memory system with a 32-bit virtual addresses and 1 K-byte pages. Each page table entry requires 32 bits. It is desired to limit the page table size to one page.- How many levels of page tables are required?
- What is the size of the page table at each level?
Hint: One page table size is smaller. - This smaller page size could be used at the top level or the bottom level of the page table hierarchy. Which strategy consumes the least number of pages?
- Inverted Page Table
- Problem 8.3 from course book [Stal05]. The problem is not available in the 4th edition.
- How much memory space is needed for the user page table of Figure 8.4?
- Assume you want to implement a hashed inverted table for the same addressing scheme as depicted in Figure 8.4, using a hash function that maps the 20-bit page number into a 6-bit hash value. The table entry contains the page number, the frame number, and a chain pointer. If the page table allocates space for up to 3 overflow entries per hashed entry, how much memory space does the hashed inverted table take?