April 29 2021

IT3072E Operating Systems: Exercises on memory management

1. Assume the base and limit registers contain the same value, 16,384.
Is this just an accident, or are they always the same? It is just an
accident, why are they the same in this case?
sol: It is an accident. The base register is 16,384 because the program
happened tobe loaded at address 16,384. It could have been loaded
anywhere. The limitregister is 16,384 because the program contains
16,384 bytes. It could have been any length. That the load address
happens to exactly match the program length is pure coincidence.
2. Assume contiguous memory allocation is used to allocate memory space
to processes and we have the current memory hole sizes of 10 MB, 4
MB, 20 MB, 18 MB, 7 MB, 9 MB, 12 MB, and 15 MB. The existence of
these holes are kept in a list in the same order. Which hole are taken
for successive processes of size 1) 12 MB; 2) 10 MB; 3) 9 MB given
the decision to allocate a hole is based on one of the following strategy
(each strategy seek a hole in the order of the list):
(a) First fit
(b) Worst fit
(c) Best fit
sol: First fit takes 20 KB, 10 KB, 18 KB. Best fit takes 12 KB, 10 KB,
and 9 KB. Worst fit takes 20 KB, 18 KB, and 15 KB.
3. Using the page table on slide 31 in the class notes, what are the physical
addresses of the logical addresses
(a) 4,096
(b) 2,062
(c) 8,949
(d) 11,266
4. A system implements a paged virtual address space for each process
using a one-level page table. The maximum size of an address space
is 16 megabytes. The page table for the running process includes the
following entries:

0 4
1 8
2 16
3 17
4 9
 The page size is 4KB and the maximum physical memory size of the
machine is 2 megabytes.

(a) How many bits are required for each page table entry?
sol: There are at most 221 /212 frames in memory, so a page table
entry will require 9 bits for a frame number and possibly other
bits for protection.
(b) What is the maximum number of entries in a page table?
sol: The size of a virtual address space is 224 , there the page table
could have up to 224 /212 = 212 entries.
(c) How many bits are there in a virtual address?
sol: The virtual address space has 24 bits.
(d) To which physical address will the virtual address 1524 translate
to?
sol: Virtual address 1524 lies on page 0 which resides in frame
4 with an offset of 1524. So, 1524 maps to physical address 4 ×
4096 + 1524 = 16384 + 1524 = 17908
(e) Assuming that frame 0 starts at the physical address 0, that con-
secutive frame numbers have consecutive physical addresses (the
first address of frame i + 1 follows immediately the last address
of frame i), then, which virtual address will translate to physical
address 65536?
65536/4096 = 16. Since addresses start at number ”0”, the ad-
dress 65536 is actually on frame 17 with offset 0. This frame has
been assigned to page 3 of the logical address, with offset 0, it is
the logical address 12288.

5. Consider a paging system with the page table stored in memory.

(a) If a memory reference takes 400ns, how long does it takes to fetch
data through the page table?
sol: Need to access memory twice, one to access the page table
and one for fetching the data: 2 × 400ns = 800ns
(b) If we add a TLB, and 85% of all page-table references are found
in the TLB (i.e. hit rate is 85%), what is the effective memory
reference time? (Assume that finding a page-table entry in the
associative registers takes zero time, if the entry is there.)
sol: Effective access time = (.85×400)+(.15×800) = 340+120 =
460ns

6. Consider a paging system with the page table stored in memory. As-
sume the overhead to read an entry in the page table is 5ns (access to
the page table is 5 ns). To reduce this overhead, a TLB is installed,
 where a look up in the TLB cost 1ns. What hit rate is needed to reduce
the average overhead to access the page table to 2ns?
sol: The effective instruction time is 1h + 5(1 − h), where h is the hit
rate. If we equate this formula with 2 and solve for h, we find that h
must be at least 0.75.

7. A system implements a paged virtual address space using a two-level

page table. The maximum size of a process address space is 227 bytes
(about 134 megabytes). The page table for a running process includes
the following entries:

Figure 1: Two levels page table

The frame size is 210 bytes (1KB) and the physical memory size is 216
bytes (65 KBs).

(a) How many bits are required for each page table entry?
The content of a page table entry is the address of a frame. The
physical memory is 216 bytes, assuming the memory is byte ad-
dressable, the size of the physical address space is 216 , we need 16
bits to address a frame in the physical memory, thus 16 bits of
memory (2 bytes) are required for each entry of the page table.
(b) What is the maximum number of entries in the inner page table?
The maximum size of a process is 227 . Page sizes are always equal
to the frame size of the computer which is 210 . Thus the maximum
number of pages a process can have is 227 /210 = 217 . The inner
page table has one entry for each page, thus the maximum number
of entries of the inner page table is 217 .
(c) How many bits there is in virtual addresses generated by the CPU?
The maximum size of a process is 227 , the virtually addressable
space is 227 bytes, thus addresses generated by the CPU have 27
bits.
 (d) What is the maximum number of entries of the inner page table
that can be stored in one frame?
We need 2 bytes to address a frame. Thus a frame can store
210 /2 = 29 = 512 entries of the inner page table.
(e) How many frames are needed to store a maximum size process?
The maximum number of pages a process may have is 217 , thus
the maximum number of entries in the inner page table is 217 . One
frame can store 29 entries of the page table, thus the number of
frames needed to store the inner page table is 217 /29 = 28 = 256
frames.
(f) How many entries there will be in the outer page table?
To store the inner page table we need 28 frames. The outer page
table must contain one entry for each frame of the inner page
table. Consequently the outer page table will have 28 entries.
(g) To which physical address will the virtual address 9812 translate
to?
A virtual address has 27 bits. 9812 in binary on 27 bits is 00000000
000001001 1001010100. The first 8 bits of the binary representa-
tion of 9812 are all zeros, they refer to entry 0 of the outer page
table. Entry 0 of the outer page table has the address of the fifth
frame holding the inner page table.
The next 9 bits 000001001 of the virtual address index into entry
9 of the fifth inner page table in Figure 1.
Entry 9 index into frame 16. Frame 16 starts at the address
16384 (16 × 1024). The last 10 bits of the virtual address 9812,
1001010100 = 596, give us the physical address of the virtual ad-
dress: 16384 + 596 = 16980.
(h) Assuming that frame 0 starts at the physical address 0, that con-
secutive frame numbers have consecutive physical addresses (the
first address of frame i + 1 follows immediately the last address
of frame i), then, which virtual address will translate to physical
address 33768?
33768/1024 = 32.976 = frame 33. As we don’t know from Figure
1 which entry of the page table index into this frame, we cannot
tell the logical address of the above physical address.

8. Figure 2 below represents the tree organization of page tables in Linux.

pgd is the first level of the outer page table, it is constituted by a single
node in the tree. pmt is the second level of the outer page table which
has several nodes. pte is the inner page table again with several nodes.
Typically, each node in the tree occupies one frame and thus contains
a fixed number of entries.
 Figure 2: Linux three levels page table

(a) Assume the physical memory is on 64 bits addressable. Each frame

is 16 KB or 214 bytes. We have a process of 232 bytes.
i. How many pages there are in this process? sol: 232 −214 = 218
or 262144 pages.
ii. How many bits is needed to address the physical memory?
sol: 64 bits
iii. How many bytes is needed for an entry in the page table?
sol: 8 bytes
iv. How many entries of the page table there are in one node the
PTE level, i.e. the inner page table?
sol: 214 /26 = 28 or 256 entries
v. An address x in the process has 32 bits. The last bits of x are
the index into a frame that complete the physical address of
the virtual address x, how many of the last bits of x are used
to index in the frame?
sol: 14 bits since a frame has 214 bytes
vi. How many bits of x are used to index into a node of the PTE
level?
sol: 8 bits since PTE nodes have 256 entries, i.e. they refer to
256 different frames of the physical memory level where the
process is stored
vii. How many entries of the page table there are in one node the
pmd level, i.e. the inner page table?
sol: 214 /26 = 28 or 256 entries, since the pmd level stores
addresses of frames where the pages of the next level of the
inner page table are stored
viii. How many bits of x are used to index into a node of the pmd
level?
 sol: 8 bits since pmd nodes have 256 entries, i.e. they refer to
256 different frames of the physical memory level where pages
of the pge table are stored
ix. How many bits of x are used to index into a node of the pgd
level?
sol: 2 bits
x. How many entries is there in the pgd table?
22 = 4 entries
xi. How many nodes the pmd level has?
sol: 4 nodes since the node the pgd level has 4 entries, each
one referring to a frame where one page of the next page table
level is stored
xii. How many nodes the PTE level has?
sol: 1024. Each node of the pmd level has 256 entries, there
are 4 nodes at the pmd level
xiii. How much physical memory is used to store this page table?
sol: One node of the page table is stored in one frame. There
are 1024 nodes at the PTE level, 1024 = 210 ×214 = 224 . There
are 4 nodes at the pmd level: 24 × 214 = 216 and 1 node at
the pgd level. So 224 + 216 + 214 = 16, 859, 136 bytes. Had the
page table stored linearly in contiguous memory, the amount
of memory would have been 224 , so slightly more physical
memory in order to split the page table across available frames
in main memory

9. Assume the physical memory is 64 bits addressable. Each frame is 16

KB or 214 bytes. We have a process of 264 bytes.
(a) How many levels the page table must have?
sol: 1- 64-14= 50, 2- 50 - 8 = 42, 3- 42 - 8 = 34, 4- 34 - 8 = 26,
5- 26 - 8 = 18, 6- 18 - 8 = 10, 7- 10 - 8 = 2, i.e. 7 levels
(b) How many entries there are in the outermost level of the page
table? sol: 4 entries
10. Assume the physical memory is 64 bits addressable. Each frame is 16
KB or 214 bytes. We have a process of 264 bytes. The total number of
pages in the process is 264 /214 = 250 . Rather than using a multilevel
page table, we will use a hashed page table. The hashed page table has
214 entries.
(a) What is the size of the hashed table?
sol: the contain of the hashed page table are pointers to link
lists. Since the physical address space is 64 bits, and pointers are
addressed, so there is 8 bytes per entry in the hashed table, thus
214 × 23 = 217
(b) How many bits of a virtual address are used to address in the
hashed page table?
sol: 50 bits
(c) Assume the bits of a virtual address that are used to index into
the hashed table convert into the integer 337,656,234. What is
the corresponding entry in the hash table? 14762, i.e. 337,656,234
modulo 16384