Section
Notes - 2/13/03
Section Outline:
- Review VM
- Group work on questions
First Problem
A computer system has a 36-bit virtual
address space with a page size of 8K, and 4 bytes per page table entry.
- How many pages are in the virtual address space?
- What is the maximum size of addressable physical memory in this
system?
- If the average process size is 8GB, would you use a one-level,
two-level, or three-level page table? Why?
Solution:
- A 36 bit address can
address 2^36 bytes in a byte addressable machine. Since the size of a page
8K bytes (2^13), the number of addressable pages is 2^36 / >2^13 = 2^23
- With 4 byte entries
in the page table we can reference 2^32 pages. Since each page is 2^13 B
long, the maximum addressable physical memory size is 2^32 * 2^13 = 2^45
B (assuming no protection bits are used).
- 8 GB = 2^33 B
We need to analyze
memory and time requirements of paging schemes in order to make a decision.
Average process size is considered in the calculations below.
1 Level Paging
Since we have 2^23 pages in each virtual address space, and we use 4 bytes
per page table entry, the size of the page table will be 2^23 * 2^2 = 2^25.
This is 1/256 of the process' own memory space, so it is quite costly. (32
MB)
2 Level Paging
The address would be divided up as 12 | 11 | 13 since we want page table
pages to fit into one page and we also want to divide the bits roughly equally.
Since the process'
size is 8GB = 2^33 B, I assume what this means is that the total size of
all the distinct pages that the process accesses is 2^33 B. Hence, this process
accesses 2^33 / 2^13 = 2^20 pages. The bottom level of the page table then
holds 2^20 references. We know the size of each bottom level chunk of the
page table is 2^11 entries. So we need 2^20 / 2^11 = 2^9 of those bottom
level chunks.
The total size of
the page table is then:
//size
of the outer page table |
//total
size of the inner pages |
|
1 *
2^12 * 4 |
+
2^9 * 2^11 * 4 |
=
2^20 * ( 2^-6 + 4) ~4MB |
3 Level Paging
For 3 level paging we can divide up the address as follows:
8 | 8 | 7 | 13
Again using the same
reasoning as above we need 2^20/2^7 = 2^13 level 3 page table chunks. Each
level 2 page table chunk references 2^8 level 3 page table chunks. So we
need 2^13/2^8 = 2^5 level-2 tables. And, of course, one level-1 table.
The total size of
the page table is then:
//size
of the outer page table |
//total size of
the level 2 tables |
//total size of
innermost tables |
|
1 *
2^8 * 4 |
2^5 * 2^8 *4 |
2^13 * 2^7 * 4 |
~4MB |
As easily seen, 2-level
and 3-level paging require much less space then level 1 paging scheme. And
since our address space is not large enough, 3-level paging does not perform
any better than 2 level paging. Due to the cost of memory accesses, choosing
a 2 level paging scheme for this process is much more logical.
Second Problem (Didn't make it this far in either section)
In a 32-bit
machine we subdivide the virtual address into 4 pieces as follows:
8-bit 4-bit
8-bit 12-bit
We use a 3-level
page table, such that the first 8 bits are for the first level and so on.
Physical addresses are 44 bits and there are 4 protection bits per page.
Answer the following questions, showing all the steps you take to reach the
answer. A simple number will not receive any credit.
- What
is the page size in such a system? Explain your answer (a number without
justification will not get any credit).
- How
much memory is consumed by the page table and wasted by internal fragmentation
for a process that has 64K of memory starting at address 0?
- How much memory is consumed by the page
table and wasted by internal fragmentation for a process that has a code segment
of 48K starting at address 0x1000000, a data segment of 600K starting at
address 0x80000000 and a stack segment of 64K starting at address 0xf0000000
and growing upward (towards higher addresses)?
Solution:
- 4K. The last 12 bits
of the virtual address are the offset in a page, varying from 0 to 4095.
So the page size is 4096, that is, 4K.
- 2912 or 4224 bytes
for page tables, 0 bytes for internal fragmentation.
Using the subdivision above, the 1st level page table contains 256 entries,
each entry pointing to a 2nd level page table. A 2nd level page table contains
16 entries, each entry pointing to a 3rd page table. A 3rd page table contains
256 entries, each entry pointing to a page. The process's address space consists
of 16 pages, thus we need 1 third-level page table. Therefore we need 1 entry
in a 2nd level page table, and one entry in the first level page table. Therefore
the size is: 256 entries for the first table, 16 entries for the 2nd level
page table, and 1 3rd level page table containing 256 entries.
Since physical addresses
are 44 bits and page size is 4K, the page frame number occupies 32 bits.
Taking the 4 protection bits into account, each entry of the level-3 page
table takes (32+4) = 36 bits. Rounding up to make entries byte (word) aligned
would make each entry consume 40 (64) bits or 5 (8) bytes. For a 256 entry
table, we need 1280 (2048) bytes.
The top-level page
table should not assume that 2nd level page tables are page-aligned.
So, we store full physical addresses there. Fortunately, we do not need control
bits. So, each entry is at least 44 bits (6 bytes for byte-aligned, 8 bytes
for word-aligned). Each top-level page table is therefore 256*6 = 1536 bytes
(256 * 8 = 2048 bytes).
Trying to take advantage
of the 256-entry alignment to reduce entry size is probably not worth the
trouble. Doing so would be complex; you would need to write a new memory
allocator that guarantees such alignment. Further, we cannot quite fit a
table into a 1024-byte aligned region (44-10 = 34 bits per address, which
would require more than 4 bytes per entry), and rounding the size up to the
next power of 2 would not save us any size over just storing pointers and
using the regular allocator.
Similarly, each entry
in the 2nd level page table is a 44-bit physical pointer, 6 bytes
(8 bytes) when aligned to byte (word) alignment. A 16 entry table is therefore
96 (128) bytes. So the space required is 1536 (2048) bytes for the top-level
page table + 96 (128) bytes for one second-level page table + 1280 (2048)
bytes for one third-level page table = 2912 (4224) bytes. Since the process
can fit exactly into 16 pages, there is no memory wasted by internal fragmentation.
- 5664 or 8576 bytes
for page tables, 0 bytes.
First, the stack, data and code segments are at addresses that require having
3 page table entries active in the first level page table, so we have 3 second-level
page tables. For 48K, you need 12 pages or 1 third-level page table; for
600K, you need 150 pages, or 1 third-level page table and for 64K you need
16 pages or 1 third-level page table.
So the space required
is 1536 (2048) bytes for the top level page table + 3 * 96 (3 * 128) bytes
for 3 second-level page tables + 3 * 1280 (3 * 2048) for 3 third-level page
table = 5664 (8576) bytes.
As the code, data,
stack segment of the process fits exactly into 12, 150, 16 pages respectively,
there is no memory wasted by internal fragmentation.
note: questions borrowed from Mike Dahlin's Intro to OS class at U Texas:
http://www.cs.utexas.edu/users/dahlin/Classes/UGOS/
|