Description
Notes: This is an individual assignment. Bring the hard copy to the exam and submit a soft copy through blackboard. No late assignment will be accepted. This assignment is worth 10% of your total grade.
Problem 1
(12 points) Consider the memory management methods of contiguous allocation, paging, and segmentation. Compare these methods with respect to the following: external fragmentation and code sharing among processes.
Problem 2
(10 pts) Suppose a computer that supports virtual memory and has 32-bit virtual addresses and uses page size of 8KB. If a process uses 100 pages of its virtual address space, how much space does its page table require if a single-level page table is used? Assume each table entry occupies 4 bytes.
Problem 3
(18 points) Consider the following page reference string:
1,2,3,4,2,1,5,6,2,1,2,3,7
How many page faults would occur for the page replacement algorithms: LRU, FIFO, Opti-mal in the following cases? Explain your answer. Remember all frames are initially empty, so your rst unique pages will all cost one fault each.
-
5 frames are allocated for the process
-
6 frames are allocated for the process
Problem 4
(10 points) Consider a system where for each frame we keep track of how many pages are associated with that frame by using a counter. When we need to replace pages, our page replacement algorithm searches for a frame with the smallest number of pages associated with it.
Initially all the counters are set to zero for all frames. When a new page is associated a frame, its counter is incremented.
1
COMP 304- Operating Systems ( Spring 2020): Assignment 3 PROBLEM 7
Show how the number of page faults for this page replacement algorithm given the following reference string of a process with four frames in memory? Is this a good algorithm for page replacement?
1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2.
Problem 5
(6+6 points)
Consider a le system developed by one of the KU graduates for Unix-based systems. In this le system, when a le is deleted, its disk space is reclaimed but links to that le can still exist.
-
What problems can arise if a new le is created with the same absolute path name?
-
How can you avoid the problem related to links? Explain your solution.
Problem 6
(6+5+5 points) Consider the working-set model with the working set window being 7. Given the following system with 3 independent processes and their corresponding reference strings as shown below:
|
Time |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
P1 |
2 |
5 |
7 |
4 |
4 |
1 |
2 |
3 |
7 |
3 |
3 |
|
P2 |
1 |
1 |
1 |
3 |
3 |
4 |
4 |
3 |
5 |
6 |
7 |
|
P3 |
4 |
9 |
3 |
2 |
9 |
8 |
7 |
7 |
7 |
1 |
2 |
-
According to the given data above, what is the working set and working set size for each process at time 9 (inclusive)?
-
Does the system su er from trashing at time 9 (inclusive) if there are total 10 frames in the physical memory? Why or why not? Show your work for credit.
-
How many frames should be in the physical memory so that the system doesn’t su er from trashing at time 7 (inclusive)? Show your work for credit.
Problem 7
(6+6 points) Assume page size is 1024 words and each row is stored in one page. int A[][] = new int[1024][1024];
If the OS allocates 512 frames for a program and uses LRU page replacement algorithm
Student Name: Page 2 of 3
COMP 304- Operating Systems ( Spring 2020): Assignment 3 PROBLEM 8
Program 1
for (j = 0; j < A.length; j++)
… for (i = 0; i < A.length; i++)
…… A[i][j] = 0;
Program 2
for (i = 0; i < A.length; i++)
… for(j = 0; j < A.length; j++)
…… A[i][j] = 0;
How many page faults does each program experience?
Problem 8
(5+5 points)
-
On a system with paging, a process cannot access memory that it does not own. Why?
-
How could the operating system allow a process to access to other memory? (give a max 2 sentence answer)
Student Name: Page 3 of 3
