Part A This problem explores the differences in memory utilization between pagin
ID: 3767456 • Letter: P
Question
Part A
This problem explores the differences in memory utilization between paging and segmentation. Consider a system that has 64Kbytes of RAM dedicated to the storage of user programs during their execution. The following three programs are being run concurrently on the system. Program A: 20Kbytes; Program B: 31Kbytes; Program C: 17Kbytes.
Scenario 1: The system implements virtual memory using paging. The page size is 16Kbytes. At a particular moment, the page tables of the 3 programs look like this:
Program A
Program B
Program C
Page
Frame
Page
Frame
Page
Frame
A0
0
B0
1
C0
-
A1
2
B1
-
C1
3
Compute the unused space in the RAM that is wasted due to internal fragmentation.
Scenario 2: The system implements virtual memory using segmentation. At a particular moment, the segment tables of the 3 programs look like this:
Program A
Program B
Program C
Seg-ment
Size
Start location
Seg-ment
Size
Start location
Seg-ment
Size
Start location
A0
10K
0
B0
24K
16K
C0
7K
53K
A1
10K
40K
B1
7K
-
C1
10K
-
Compute the unused space in the RAM. Can this unused space be allocated to any program segment that is not already in memory?
Consider a 2-level memory hierarchy with parameters T1=5, T2=100. The hit rate h is known to be 0.8. Find the EAT of this system if the access strategy is:
Parallel;
Sequential.
Part B
[Total 3 pts] Consider a system that implements instruction level pipelining, supported by a 2-level memory hierarchy using the sequential access strategy, with level-1 access time T1, and level 2 access time T2. Let h be the hit rate at level 1. Suppose the synchronous pipeline stalls when data fetch is not successful in the level-1 memory.
[1pt] In terms of the number of instructions processed, how frequently does the pipeline stall due to data access? Explain.
[1pt] In terms of time, how much does the stall cost? Explain.
[1pt] What is the minimum stage length of the pipeline? Explain.
[Total 5 pts + 4] Read the article “The working set model for program behavior” by Denning 1968, and answer the following questions.
[0.5 pt] What are the two constituents of the system demand of a computation? (from 1.Introduction)
[0.5 pt] What is the meaning of the working set of a program? (from 3.Working Set Model)
[1 pt] When using the working set for memory allocation, what memory requirement must be met before a program can be run? (from the end of 3.Working Set Model)
[3 pts] Explain the definitions of the following symbols, either using the author’s words, or using your own terminologies. Be as precise as possible.
W(t, r) and w(t, r)
{tn}n>=0 and {xn}n>=1
Fx(a)
A, T and M
l(r), j(r) and F(r)
s(r)
Here are some examples:
t denotes an instant of time
r denotes the length of a time interval preceding t, over which the working set of a program is studied, and it is called the working set parameter
x denotes the process-time interval between successive references to the same page.
[2 bonus pts] At time t, suppose a process p has referenced pages 1, 2, 8, 12, 16 and 21 in the time interval r that just passed. Over the next time interval a, where a<r, pages 1 and 8 are evicted and page 9 is loaded into the memory. Find W(t, r), and W(t+a, r).
[2 bonus pts] Describe the four properties of a working set W(t, r)?
Program A
Program B
Program C
Page
Frame
Page
Frame
Page
Frame
A0
0
B0
1
C0
-
A1
2
B1
-
C1
3
Explanation / Answer
Scenario 1:
Since the page size is 16Kbytes and RAM is of size 64Kbytes,
The main memory is split into 4 fixed blocks (4 pages)
Since program A is of size 20Kbytes it requires two pages. Page A0( 16 K bytes) and Page A1(4 Kbytes)
Since program B is of size 31Kbytes it requires two pages. Page B0( 16 K bytes) and Page B1(15 Kbytes)
Since program C is of size 17Kbytes it requires two pages. Page C0( 16 K bytes) and Page C1(1 Kbytes)
From the page table, the following pages are loaded into main memory:
PageA0, PageA1, Page B0 and Page C1
Total program A is stored into main memory and it occupies 2 frames(32Kbytes).
But the size of the program A is only 20 K bytes.
Thus 12 K bytes are unused due to internal fragmentation.
Only page B0 of program B is loaded into main memory and page B0 occupies 1 frame (16Kbytes).
Thus there is no unused memory.
Only page C1 of program C is loaded into main memory and it occupies 1 frame.
But actual size of page C1 is 1Kbyte only.
Thus 15Kbytes are unused due to internal fragmentation.
Therefore total unused space due to internal fragmentation is 12 + 15=37 K bytes
Scenario 2:
From segment table:
The main memory will be
0K
A0
9K
10k
6K Un used
15K
16K
B0
39K
40K
A1
49K
50K
3K un used
52K
53K
C0
59K
60K
4K un used
63K
The total un used space = 6+3+4=13Kbytes
There are two segments that are not loaded into main memory are
Segment B1(7K) and segment C1(10K)
But the no un used spaces are useful to load these two segments.
Sequential:
EAT= (1-Pmiss)* thit+ Pmiss * tmiss
= (1-0.2)* 5+0.2* 100
=4+20
=24 nano seconds
Parallel:
Hit = 0.8
T1= 5 nano seconds to look up TLB (thit)
T2=100nano seconds to access page in main memory (if fault) (tmiss)
Effective Access Time(EAT) = (t1+t2)*hit +(t1+2*t2)*(1-hit?)
=(5+100)*0.8+(5+200)*0.2
=84+41
=125 nano seconds
0K
A0
9K
10k
6K Un used
15K
16K
B0
39K
40K
A1
49K
50K
3K un used
52K
53K
C0
59K
60K
4K un used
63K