Solution for Assignment 4 


1. Consider a swapping system in which memory consists of the following hole sizes in memory order: 10K, 4K, 20K, 18K, 7K, 9K, 12K, and 15K. Which hole is taken for successive segment requests of: 

for first fit? Now repeat the question for best fit, worst fit, and next fit.

 

    First fit takes 20K, 10K, 18K.

    Best fit takes 12K, 10K, 9K.

    Worst fit takes 20K, 18K, and 15K.

    Next fit takes 20K, 18K, and 9K.


2. If an instruction takes 1 microsec and a page fault takes an additional n microsec, give a formula for the effective instruction time if page faults occur every k instructions.

 

    A page fault every k instructions adds an overhead of n/k microsec to the average.  The average instruction takes 1 + n/k microsec.

 

 

3.  A computer with a 32-bit address uses a two-level page table. Virtual addresses are split into a 9-bit top-level page table field, and 11-bit second-level page table field, and an offset. How larege are the pages and how many are there in the virtual address space?

    20 bits used for virtual page numbers, leaving 12 for the offset.  So, page size is 4K.  So we have 220 pages in the virtual address space.

 

 

4. A machine has 48-bit virtual addresses and 32-bit physical addresses. Pages are 8K. How many entries are needed for a conventional page table? For an inverted page table?

    For conventional page table, the number of entries is 248 / 213 is 235.   For IPT, we need only the number of page frames, 232 / 213 is 219, that is 524,288.

 

 

5.Explain for both paging and segmentation, how address translation from virtual address to
physical address happens. 

    Show figures from the slides.  Slide #14 and #30.

 

 

6.  In modern operating systems, mention all the ways of determining the resident set size of a
process. 

In case of fixed-allocation policy, it size get determined at load time.

In case of variable-allocation:

    - Working set strategy.  

    - Monitoring page faults.

 

 

 

7.  If FIFO page replacement is used with four page frames and eight pages, how many page faults will occur with the reference string 0172327103 if the four frames are initially empty? Now repeat this for LRU.

    6 page faults for FIFO.

    7 page faults for LRU.

 

 

8. Assume that virtual address space of a virtual memory system is 10MB, and page size is 1KB. 
Each entry in the page table is 4 bytes. How much memory is required for page tables of 10
processes? Assume no swapping occurs for page tables.

    page table size = 10 M/ 1K * 4 = 40 K bytes

    For 10 processes we have a size of 400 k bytes.

    (Assuming the maximum size of page table is allocated for a process. )

 

9. Consider the following page-reference string: 1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6.  How many page faults would occur for the following replacement alogorithms, assuming one, two, three, four, five, six, or seven frames?  Remember that all frames are initially empty, so your first unique pages will all cost one fault each. 1) LRU replacement 2) FIFO replacement 3) Optimal replacement.

10. What is the cause of thrashing? How does the system detect thrashing?  Once it detects thrashing, what can the system do to eliminate this problem?

Thrashing is caused by underallocation of the minimum number of pages required by a process, forcing it to continuously page fault. The system can detect thrashing by evaluating the level of CPU utilization as compared to the level of multiprogramming. It can be eliminated by reducing the level of multiprogramming.

 11. A computer has four page frames.  The time of loading, time of last access, and the R (Reference/Use bit) and M(Modified bit) for each page are shown below (the times are in clock ticks):

Page Loaded Last Referenced R M
0 126 279 0 0
1 230 260 1 0
2 120 272 1 1
3 160 280 1 1

 a) Which page will FIFO replace?    b) Which page will LRU replace?    c) Which page will second chance replace?

FIFO removes 2.
LRU removes 1.
Second chance removes 0.