# virtual memory

• 11-05-2004
sweets
virtual memory
I am studying for my OS finals and there is something I just cant understand. The question is as follows:

Consider a virtual memory system with the following parameters:
- 32 bit virtual address
- 16 kbyte virtual page size
- 2 level page table
- 32 bit page table entry

Draw a diagram of the 32 bit address showing the length and placement of all bit fields (i.e offset in the page, primary page table offset and the secondary page table offset.

The answer is :

Code:

```-----------------------------------------------------------------                   32 bit Virtual Address                        | ------------------|-----------------|---------------------------| 9 bit PT1 field  | 9 bit PT2 field |    14 bit offset          | ------------------|-----------------|---------------------------| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -----------------------------------------------------------------```
Why is this the case? How do they come up with this result?????

If anyone can help, I would greatly appreciate it.

Thanks
• 11-05-2004
VirtualAce
So what you mean is this:

32 bit virtual address:

16 kilobytes allowed per page - IE 16,384 bytes or 2^14 - hence you need 14 bits to represent the 16KB max per page. I'm assuming based on your model that any size up to 16 KB is allowed thus the reason for putting the actual size into the virtual address.

The two level page table is fairly simple. It simply means there are two page tables - but again I'm not familiar with your implementation so anything is possible. Since they are using 9 bits to represent the table offset I'm assuming that each table is only 2^9 bytes in size which gives 2*(2^9) or 512*2 or 1024 bytes. However each ENTRY in the page table...each address stored in the page table is 32-bits.

The page table entry size has little or nothing to do with the virtual address contents. So this means that since each page table is 512 bytes in size and each address entry is 4 bytes that the max amount of entries is (512/4) or 128.

You can store 128 entries in each page table for a max of 256 entries.

Page table 1: - 32 bit entries, 128 - 32-bit entries allowed
Entry 0 0xFFFFFFFF
Entry 1 0x1234567
Entry 2 .................
...
...
Entry 127 0x00000000

Again this is a lot of guesswork on my part because I'm not in the class. But I'm extremely familiar with page table's, virtual memory, and virtual addresses.

Note that these are the max values. If the page table size decreases it must decrease by a factor of 4 bytes since each entry is 32-bits or 4 bytes and it makes no sense to have half an entry in the table. So as the page table size decreases, so does the high order information in your virtual address as well as the low order page table information.

I'm assuming that one virtual address then is stored in both tables which, correct me from above, means you can only have 128 entries in the entire system using the constructs you have specified. If it is only stored in one table then IMO the second nine bit field is a waste of space. It does not make sense to store two un-aligned page tables in memory. If they were aligned then you could only store the first nine bit page table address and use that value to index into the second page table. This also would allow you to increase the max size of each virtual page since you have freed up 8 bits of information. This amounts to a lot more space on each page.

But given your constructs here is the breakdown of one virtual address:

1. The page table address(index) where the entry resides in the first page table.
2. The page table address(index) where the entry resides in the second page table.
3. The size of the page table(s). Again this must refer to both tables since there is not a field to specify the size of the second table. If there were two diff sizes then each virtual address would have to be 32-bits larger in size, thus 64-bit virtual addresses.
• 11-05-2004
sweets
- How did you figure out that 16 kbytes was 2^14? :blush:

- I dont know why they are using 9 for the page table offset. I was hoping someone could tell me that

The question has other parts, such as translating virtual addresses (no prob's there), but then there is another part to the question which Im also stuck on.

Question: What is the maximum number of memory accesses and disk accesses for a single memory reference in this system?

Answer: Max memory accesses = 3 and Max disk accesses = 2

How do they get that??
• 11-05-2004
VirtualAce
16 KB = 16 *1024 = 16384 = 2^14

Because the page table only has 2^9 available bytes in it.

Quote:

The two level page table is fairly simple. It simply means there are two page tables - but again I'm not familiar with your implementation so anything is possible. Since they are using 9 bits to represent the table offset I'm assuming that each table is only 2^9 bytes in size which gives 2*(2^9) or 512*2 or 1024 bytes. However each ENTRY in the page table...each address stored in the page table is 32-bits.

The page table entry size has little or nothing to do with the virtual address contents. So this means that since each page table is 512 bytes in size and each address entry is 4 bytes that the max amount of entries is (512/4) or 128.

You can store 128 entries in each page table for a max of 256 entries.

Page table 1: - 32 bit entries, 128 - 32-bit entries allowed
Entry 0 0xFFFFFFFF
Entry 1 0x1234567
Entry 2 .................
...
...
Entry 127 0x00000000
I'm assuming they mean each disk access and memory access is a 32-bit fetch. But w/o more info I cannot answer your second question.
• 11-05-2004
sweets
Where did you figure out the page table offsets to be 2^9? Is it because it is 2 pages, so you just divided the remaining 18 bits???
• 11-06-2004
VirtualAce
Because the virtual address only has room for 9 bits for either page. This means that the page table is 512 bytes in size because you can only fit 512 bytes in 9 bits. The max value then is 512. Divide this by 4 since 32-bits is 4 bytes and you get a max of 128 entries. It would not make sense to have a virtual address that could only reference part of a table so I'm assuming that the tables both have a max entry number of 128.
• 11-06-2004
sweets
Gotcha....thanks for everything

Great feedback ;)