CS213 W4 LAB 2: Memory and Virtual Memory Solutions - Fall 2024

This document presents solutions to a homework assignment on memory and virtual memory concepts within an operating systems course (CS213). The solutions cover key topics such as calculating effective access time considering page fault rates, differentiating between fork() and vfork() system calls and the implications of incorrect usage, analyzing the impact of increasing the number of frames on page faults, and demonstrating page replacement algorithms (FIFO and Optimal) with detailed step-by-step solutions and hit/miss analysis. It also explores different memory allocation strategies, including equal and proportional allocation, and provides implementation details for Least Recently Used (LRU) page replacement. The document also addresses Belady’s anomaly, and provides code snippets to illustrate the algorithms.

Solution
Answer 1:
Effective Access Time= (1-p) x (80ns) + p (0.75) * (15ms) + (0.25) * (6ms)
= (1-p) x (0.080) + p (12,750,000)
= (1-p) x 80 + + p * 12,750,000
200 = 80+ 12,750,000 * p
120 = 12,750,000 * p
0.12749880% = p
Answer 2:
Fork() means that system call creates a child process that is a duplicate of its parent.
Vfork() means that the parent process is suspended, and the child process uses the address space of
the parent. So if one is to use vfork() be sure it must be used with caution to ensure that the child
process does not modify the address space of the parent.
Answer 3:
By observing graph of page faults versus number of frames, we can derive following conclusions.
1. If number of frame is 2 then number page faults is approaching 8 and if number of frame is 3 then
number page faults is approaching 6. From this observation we can say yes, it is worth to increase 2
frames to 3.
2. If number of frames is 6 then number page faults is approaching 4 and now it is going parallel to
horizontal axis, means for any number of page frame greater than 6, number of page fault will not
change. From this observation we can say yes, it is not worth to increase 6 frames to 7.
Answer 4:
SEQUENCE 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
2 2 3 3 4 4 4 0 0 0 1 2 2 2 7 7 7
1 1 1 2 2 3 3 3 4 4 4 0 1 1 1 2 2 2
0 0 0 0 1 1 2 2 2 3 3 3 4 0 0 0 1 1 1
STACKS 7 7 7 7 7 0 0 1 1 1 2 2 2 3 4 4 3 0 0 0
H/M M M M M H M H M H H M H H M M H H M H H
In above table, FIFO page replacement algorithm with this Reference String of processes and a frame size of
4 is demonstrated. First row is sequence of processes and last row shows hit or miss (page fault). Reaming
middle rows represent vertical queue (for four frames (FIFO)). Initially, there are four page faults on empty
frames. Then there is hit for 0, miss for 3 and so on as shown in table. By calculating total miss number of
page faults is 10.
There are processes 0 to 7 means total 8 processes and 4 frames half of the process are in frame after it gets
full. It means there will be 50% page faults. So for first for processes expected number page faults 4. And
for last sixteen processes expected number page faults 16/2=8. So expected number page faults was 4+8=12.

Given sequence of processes and algorithm does not suffer from Belady’s anomaly. By taking frame size
equals to 5 only following heighted processes will face page faults. And total is 9.
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
Answer 5:
In Optimal page replacement algorithm with this 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 process string,
number of page fault is 8. It is Demonstrated bellow.
1. Process 7, 0, 1 and 2 will face page fault initially. (Four page faults). Now frames:7,0,1,2
2. Process 0 will not face page fault. Now frames:7,0,1,2
3. Process 3 will face page fault. Now frames: 3,0,1,2. Seven replaced because it is which process will
come after longest time.
4. Process 0 will not face page fault. Now frames: 3,0,1,2
5. Process 4 will face page fault. Now frames: 3,0,4,2. One is replaced because it is process which will
come after longest time.
6. Processes 2, 3,0,3,2 will not face page fault. Now frames: 3,0,4,2
7. Process 1 will face page fault. Now frames: 1,0,4,2. Three is replaced because it is one of the
processes which will come after longest time.
8. Processes 2, 0, 1 will not face page fault. Now frames: 1,0,4,2
9. Process 7 will face page fault. Now frames 1,0,7,2. Four is replaced because it is one of the
processes which will come after longest time.
10. Processes 0, 1 will not face page fault. Now frames: 1,0,7,2
Expected page fault for this string of process was 8. Because there will be initial four page faults. And we
can avoid page fault for next three processes (frame size-1). So, out of sixteen processes four (max) will face
page faults. (16(one in four)/4=4)
Given sequence of processes and algorithm does not suffer from Belady’s anomaly. By taking frame size
equals to 5 only following heighted processes will face page faults. And total is 7.
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
Answer 6:
In page replacement algorithm with this Reference String of processes and a frame size of 4, following
frames will be there, shown below. There are total 8 page faults.
Process
es
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
Frames
,
CONT
ENTS
7-
--
7
0-
-
70
1-
70
12
71
20
12
03
12
30
23
04
30
42
04
23
42
30
42
03
40
23
02
31
03
12
31
20
32
01
20
17
21
70
27
01
H/M M M M M H M H M H H H H H M H H H M H H
Expected number of page fault was 12, similar to FIFO.
Given sequence of processes and algorithm does not suffer from Belady’s anomaly. By taking frame size
equals to 5 only following heighted processes will face page faults. And total is 7.
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
Answer 7:

There are two mechanisms that can be used to implement LRU.
1. One is implement queue (size equals to frame size) with doubly link list that enables faster move of
processes in frames to the end.
2. Second implementation can be done with hash table and doubly link list.
Answer 8:
16 frames would be allocated to each process with the equal allocation of frames where total frames = 64,
and 4 process with virtual memory sizes 2, 4, 8, 16. As in this type allocation it just divides the number
frames by number of process. So it is 64/4=16 to each process. However process will utilize only required
number of frames.
Answer 9:
By using following formulas for proportional allocation
Allocation to Pi= (Si/S)*M,
Where Pi is ith process, Si is size of ith process, S is total size of all process and M is number of
frames.
Let’s say P1 with 2KB, P2 with 4 KB, P3 with 8 KB and P4 with 16KB virtual memory.
Total virtual memory=S=2+4+8+16=30KB
Allocation to P1= (2/30)*64=4.26 =4
Allocation to P2= (4/30)*64=8.53 =9
Allocation to P3= (8/30)*64=17.06=17
Allocation to P4= (16/30)*64=34.13=34
Answer 10
In equal allocation both process will be given 32 frames (1KB each).
In proportional allocation, Total frames=64. Total size of processes=105+15=120. Thus, allocation to second
process = (105/120)*64=56. So, in proportional allocation second process will be given 56 frames.
So, 24 more frames will be allocated to the second process if a proportional allocation is used instead of
equal.