EXERCISE: CHAPTER 7: Virtual Memory

QUESTION:
Consider a computer with virtual memory system that has 4 frames for a virtual
space. Consider the following reference string :

1 2 3 1 4 5 1 6 2 1 3 7 5 2 5 3 4 7

Specify throughout the execution sequence which pages are present in a part of the
physical memory and the number of page faults using the following algorithms:
1. FIFO
2. OPTIMAL
3. LRU
4. MRU

SOLUTION:

Victim Pages are highlighted in Green Color

1. FIFO (First In First Out)

1 2 3 1 4 5 1 6 2 1 3 7 5 2 5 3 4 7
F1 1 1 1 1 1 5 5 5 5 5 3 3 3 3 3 3 3 3
F2 2 2 2 2 2 1 1 1 1 1 7 7 7 7 7 7 7
F3 3 3 3 3 3 6 6 6 6 6 5 5 5 5 5 5
F4 4 4 4 4 2 2 2 2 2 2 2 2 4 4
Fault page F F F F F F F F F F F F
Number of fault pages=.............12......................

2. OPTIMAL

1 2 3 1 4 5 1 6 2 1 3 7 5 2 5 3 4 7
F1 1 1 1 1 1 1 1 1 1 1 1 7 7 7 7 7 7 7
F2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 4 4
F3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
F4 4 5 5 6 6 6 6 6 5 5 5 5 5 5
Fault page F F F F F F F F F
A B C
Number of fault pages=.............9......................
A B C
1, 6 Not used 6 Not used 2, 3, 5 Not used
in future, so in future in future, so
apply FIFO. apply FIFO.
Choose 1 as Choose 2 as
Victim Page. Victim Page.

1
123145162137525347
 3. LRU (Least Recently Used)

1 2 3 1 4 5 1 6 2 1 3 7 5 2 5 3 4 7
F1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 7
F2 2 2 2 2 5 5 5 5 5 3 3 3 3 3 3 3 3
F3 3 3 3 3 3 6 6 6 6 7 7 7 7 7 4 4
F4 4 4 4 4 2 2 2 2 5 5 5 5 5 5
Fault page F F F F F F F F F F F F F

Number of fault pages=.................13............

4. MRU (Most Recently Used)

1 2 3 1 4 5 1 6 2 1 3 7 5 2 5 3 4 7
F1 1 1 1 1 1 1 1 6 6 6 6 6 6 6 6 6 6 6
F2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1
F3 3 3 3 3 3 3 3 3 3 7 7 7 7 7 7 7
F4 4 5 5 5 5 5 5 5 5 2 5 3 4 4
Fault page F F F F F F F F F F F F

Number of fault pages=..................12................

2
EXERCISE: CHAPTER 8: Mass Storage Structures
QUESTION:
Consider a secondary memory system (Hard Disk Drive) with 256 numbered tracks
in numbered from the inside to the outside (from 0 to 255). It is assumed that the
read /write head is now placed vertically on Track 97. The previous head position
was 28. Requests arrive for access to the following tracks:
55, 100, 85, 130, 25, 46, 147, 29, 158
What would be the total head movement after all requests have been satisfied using
the following disk scheduling algorithm
1. FIFO
2. SSTF
3. SCAN ( Elevator Algorithm)
a) Previous Head Position was 28 b) Previous Head Position was 110
4. C-SCAN
a) Previous Head Position was 28 b) Previous Head Position was 110

SOLUTION:
1) FIFO (First In First Out)
Queue: 55, 100, 85, 130, 25, 46, 147, 29, 158
Head starts at 97
Previous head position was 28

0 25 28 29 46 55 85 97 100 130 147 158 255

| | | | | | | | | | | | |
28(Previous Head Position)

97(Current Head Position)

55 100
85 130
25
46 147
29
158

Total Head Movement = |55-97| + |100-55| + |85-100| + |130-85| + |25-130| + |46-25| +

|147-46| + |29-147| + |158-29|
= 42 + 45 + 15 + 45 + 105 + 21 + 101 + 118 + 129
= 621
Ignore the movement of head from 28 to 97. Start from Current Head Position 97.

3
 the following tracks:
55, 100, 85, 130, 25, 46, 147, 29, 158

the following tracks:

55, 100, 85, 130, 25, 46, 147, 29, 158
 the following tracks:
55, 100, 85, 130, 25, 46, 147, 29, 158

the following tracks:

55, 100, 85, 130, 25, 46, 147, 29, 158
2) SSTF
Queue: 55, 100, 85, 130, 25, 46, 147, 29, 158
Head starts at 97
Previous head position was 28

0 25 28 29 46 55 85 97 100 130 147 158 255

| | | | | | | | | | | | |
28(Previous Head Position)
97(Current Head Position)
100
46 55 85
29
25 130 147 158

Ignore the movement of head from 28 to 97. Start from Current Head Position 97.
Shortest Seek Time is highlighted in Green Color
97-85=12, 100-97=3
100-85=15, 130-100 =30
85-55=30, 130-85=45
55-46=9, 130-55 = 75
46-29 =17, 130-46=84,
29-25=4, 130-29=101

Total Head Movement = |100-97| + |85-100| + |55-85| + |46-55| + |29-46| + |25-29| +

|130-25| + |147-130| + |158-147|
= 3 + 15 + 30 + 9 +17 + 4 + 105 + 17 +11
= 211

4
3) SCAN: Elevator algorithm
a) Queue: 55, 100, 85, 130, 25, 46, 147, 29, 158
Head Starts at 97
Previous Head Position was 28
So the Direction is right

0 25 28 29 46 55 85 97 100 130 147 158 255

| | | | | | | | | | | | |
28(Previous Head Position)
97(Current Head Position)
100
130 147
158 255
55 85
29 46
25

Total Head Movement = |100-97| + |130-100| + |147-130| + |158-147| + |255-158| +

|85-255| + |55-85| + |46-55| + |29-46| + |25-29|
= 3 + 30 + 17 + 11 + 97 + 170 + 30 + 9 + 17 + 4
= 388

b) Queue: 55, 100, 85, 130, 25, 46, 147, 29, 158
Hear Starts at 97
Previous Head Position was 110
So the Direction is Left

0 25 28 29 46 55 85 97 100 110 130 147 158 255

| | | | | | | | | | | | | |
110(Previous Head Position)

85 97(Current Head Position)

55
29 46
25
0 100 130 147 158

Total Head Movement = |85-97| + |55-85| + |46-55| +|29-46| + |25-29| + |0-25| +

|100-0| + |130-100| + |147-130| + |158-147|
= 12 + 30 + 9 + 17 + 4 + 25 + 100 + 30 + 17 + 11
= 255

5
4) C-SCAN
a) Queue: 55, 100, 85, 130, 25, 46, 147, 29, 158
Head Starts at 97
Previous Head Position was 28
So the Direction is right

0 25 28 29 46 55 85 97 100 130 147 158 255

| | | | | | | | | | | | |
28(Previous Head Position)
97(Current Head Position)
100
130 147
158 255
0

25 29 46 55 85

Total Head Movement = |100-97| + |130-100| + |147-130| +|158-147| +|255-158|

+|0-255| +|25-0| +|29-25| +|46-29|+|55-46|+ |85-55|
= 3 + 30 + 17 + 11 +97 + 255 + 25 + 4 + 17+ 9 +30
= 498

b) Queue: 55, 100, 85, 130, 25, 46, 147, 29, 158
Hear Starts at 97
Previous Head Position was 110
So the Direction is Left

0 25 28 29 46 55 85 97 100 110 130 147 158 255

| | | | | | | | | | | | | |
110(Previous Head Position)

85 97(Current Head Position)

55
29 46
25
0 255
100 130 147 158

Total Head Movement = |85-97| + |55-85| + |46-55| +|29-46| + |25-29| + |0-25| +

|255-0| + |158-255| + |147-158| + |130-147| +|100-130|
= 12 + 30 + 9 + 17 + 4 + 25 + 255 + 97 + 11 + 17 + 30
= 507