Page table - I don't understand how this table has been made [closed]

Question

CPU has generated this sequence of logic addresses (in decimal):

777, 2047, 1199, 1100, 546, 129, 3201

page size is 512 Byte, CPU generates logic addresses, 12 Bit length, main memory has 4 pages.

I understand the following table: We just converted the decimal addresses to binary. The total address length is 12 Bit. From task we know that page size is 512 Byte, so 2^9 Byte = 9 Bit for offset. 12 Bit - 9 Bit = 3 Bit for page. So first 3 Bits are page and the other remaining 9 Bit are offset. Easy so far.

But here comes the second part of the task and I don't understand how the table was made...

Make a table that illustrates the content of the table above (called MMU) after each finished memory access in the same order shown above. You only need to specify the necessary entries (so if there is same page twice, ignore the duplicate). At the beginning, all page frames are unassigned and they are used with an ascending page number. If all page frames are in use, the LRU replacement takes place.

Here is the solution of the table but I don't understand... That's my question, how was this table created? I don't get the logic.

Edit: For second table I can see task said 4 pages. So we have 00, 01, 10, 11(so in decimal 0, 1, 2, 3) but why they did it in that order in the table? That's what I don't understand.

Edit: I don't understand the order of the second table. Why did we start with 11, then 00, then 10 etc. It doesn't make sense for me...

Here is how I would have filled the table:

What do you think?

Answer 1

You have four physical pages of memory and eight virtual pages. All of the physical pages start out unallocated for any particular purpose. The virtual table of eight entries starts out with all the virtual pages being invalid.

That's the starting situation. One more detail may be useful here -- defining HOW new physical pages will be allocated. Given the results, I think it's clear that the allocation method starts out by allocating physical page 0, first. Then physical page 1. Etc. Once all the physical pages have been allocated at least once, this is when the LRU (least recently used) algorithm comes into play.

So that sets up the process.

One more thing might be useful to consider adding. This is how the LRU itself gets handled. Think of this as a stack of eaight cards. One card representing each virtual page. So let's call the cards: 0, 1, 2, 3, etc., for obvious reasons. The deck always has eight cards in it. Initially, the deck starts out as 01234567 (or any other order you like.) When allocating a new page, we always take the top card (which will be the left-most digit here) from the deck, use whatever physical page it indicates, and then place that card back at the bottom of the deck. So, for example, if we were to need a new physical page we'd go to this initial deck of "0123", pull the top card (which is "0"), allocate that physical page, then place that card back into the deck at the bottom. So the new deck would be "1230" after we were done with this step. Every time a physical page is accessed, we find its card in this deck and move it to the bottom, too.

To summarize the LRU deck: When we need a new physical page, we always take the top card and use whatever page is indicated by the value there and then move that card to the bottom of the deck. Whenever we access a physical page, we always find the card associated with that page and move it to the bottom of the deck.

That's it. I'll show the deck along with each step taken.

Now all you have to do is "act like the computer" and do the work by hand, running down the list of successive addresses in order. It's just simple hand work.

Each virtual address has a page and an offset. The offset value is the low-order 9 bits of the virtual address and the page is the upper 3 bits of the virtual address. The logic is as follows:

If the virtual table entry is invalid, then allocate a page from a list of free physical pages. But if there are no free physical pages left, then from a search of valid virtual table entries allocate the physical page from the virtual table entry holding the least recently used page. Also, in this case, mark the found virtual table entry as invalid because the physical page it owns is being re-allocated now. Then take this physical page and place it into the current virtual table entry and mark it as valid. Finally, pull this virtual table entry to the top of the LRU list, indicating it is very recently used.

If the virtual table entry is marked as valid, then pull this virtual table entry to the top of the LRU list, again indicating it is very recently used.

The above algorithm is repeated over and over for each of your virtual addresses, in sequence order. It ignores the details of forming the full 11-bit physical memory address. But I don't need to worry about that part of it, because your question isn't about that but instead about how that table got into the condition it was in. So I'm neglecting that detail to avoid excess detail here.

Here are the steps with your addresses, in order:

$$ \begin{array}{lrllll} \underline{\textrm{Step}} & {\underline{~~~~~~~~~~~~~~~~~~~~\textrm{Action}~~}} & \underline{\textrm{Free}} & \underline{\textrm{LRU}} & \underline{\textrm{Valid}~~~~~~~~~~~} & \underline{\textrm{Frame}~~~~} \\ & & 0123 & & \textrm{FFFFFFFF} & \textrm{oooooooo} \\ & \textbf{new address 1:265} & & & & \\ (1) & alloc = free & 123 & & \textrm{FFFFFFFF} & \textrm{oooooooo} \\ (2) & frame_1 = alloc & 123 & & \textrm{FFFFFFFF} & \textrm{o0oooooo} \\ (3) & valid_1 = true & 123 & & \textrm{FTFFFFFF} & \textrm{o0oooooo} \\ (4) & LRU(1) & 123 & 1 & \textrm{FTFFFFFF} & \textrm{o0oooooo} \\ & \textbf{new address 3:511} & & & & \\ (1) & alloc = free & 23 & 1 & \textrm{FTFFFFFF} & \textrm{o0oooooo} \\ (2) & frame_3 = alloc & 23 & 1 & \textrm{FTFFFFFF} & \textrm{o0o1oooo} \\ (3) & valid_3 = true & 23 & 1 & \textrm{FTFTFFFF} & \textrm{o0o1oooo} \\ (4) & LRU(3) & 23 & 31 & \textrm{FTFTFFFF} & \textrm{o0o1oooo} \\ & \textbf{new address 2:175} & & & & \\ (1) & alloc = free & 3 & 31 & \textrm{FTFTFFFF} & \textrm{o0o1oooo} \\ (2) & frame_2 = alloc & 3 & 31 & \textrm{FTFTFFFF} & \textrm{o021oooo} \\ (3) & valid_2 = true & 3 & 31 & \textrm{FTTTFFFF} & \textrm{o021oooo} \\ (4) & LRU(2) & 3 & 231 & \textrm{FTTTFFFF} & \textrm{o021oooo} \\ & \textbf{new address 2:76} & & & & \\ (4) & LRU(2) & 3 & 231 & \textrm{FTTTFFFF} & \textrm{o021oooo} \\ & \textbf{new address 1:34} & & & & \\ (4) & LRU(1) & 3 & 123 & \textrm{FTTTFFFF} & \textrm{o021oooo} \\ & \textbf{new address 0:129} & & & & \\ (1) & alloc = free & & 123 & \textrm{FTTTFFFF} & \textrm{o0o1oooo} \\ (2) & frame_0 = alloc & & 123 & \textrm{FTTTFFFF} & \textrm{3021oooo} \\ (3) & valid_0 = true & & 123 & \textrm{TTTTFFFF} & \textrm{3021oooo} \\ (4) & LRU(0) & & 0123 & \textrm{TTTTFFFF} & \textrm{3021oooo} \\ & \textbf{new address 6:129} & & & & \\ (1) & alloc = frame_{LRU} & & 012 & \textrm{TTTFFFFF} & \textrm{3021oooo} \\ (2) & frame_6 = alloc & & 012 & \textrm{TTTFFFFF} & \textrm{3021oo1o} \\ (3) & valid_6 = true & & 012 & \textrm{TTTFFFTF} & \textrm{3021oo1o} \\ (4) & LRU(6) & & 6012 & \textrm{TTTFFFTF} & \textrm{3021oo1o} \\ \end{array} $$

You should be able to match up the last entry above with your table, I think. The only trick here is to note that the LRU virtual table entry is '3' but the physical page owned by that virtual table entry is physical page '1'. The virtual table entry for '3' is marked false, but the alloc variable is set to 1, since that is the physical page that was assigned there.

EDIT: To your question:

I don't understand the order of the second table. Why did we start with 11, then 00, then 10 etc. It doesn't make sense for me...

We didn't start with 11. That column is the physical page number. Clearly, we didn't allocate the physical page 3 (11 binary) right off the bat. Instead, it just turns out that when address 0:129 came along, there was only one free physical page left -- page 3. But that goes into virtual page table row 0, of course! Because the virtual page referenced by 0:129 is row 0 in the virtual table. But the physical page (frame) is 3. So 3 is stored there (11 binary.)

Answer 2

The addresses given in the first table are virtual addresses in a 12-bit address space, and the purpose of the page table is to map these to physical addresses. Because pages are 512 bytes and there are 4 physical pages, the physical addresses are 11 bits, made up of a 2-bit frame number and a 9-bit offset. The page table has eight slots, one for each page in the virtual address space. (This is, of course, all completely impractical, but that's the nature of textbook problems.)

According to the hypothesis of the question, the page table starts empty with valid=0 in each slot. Following the sequence of memory references in the first table, the first reference is to page 1. That is a page fault, because the valid bit in slot 1 is of course 0. So we bring in page 1 from the disk, put it in physical page 0, and update the page table with

1: frame=0, valid=1

The next reference (2047) is to page 3 -- again a miss. So we put virtual page 3 in physical page 1, and update the page table with

3: frame=1, valid=1

At this point (just to be clear), the page table contains

0:          valid=0
1: frame=0, valid=1
2:          valid=0
3: frame=1, valid=1
4:          valid=0
5:          valid=0
6:          valid=0
7:          valid=0

so that for each virtual page number we have used, the page table shows the corresponding physical page number. That organisation makes the hardware-implemented translation from virtual to physical address simple and fast.

Next is page 2, in physical page 2. Page table entry:

2: frame=2, valid=1

The next reference is to virtual page 2 again, so that does not cause a page fault. Then virtual page 1 again, also with no fault. Next is virtual page 0, which goes in physical page 3

0: frame=3, valid=1

The final reference is to virtual page 6, which we haven't seen before. We need to allocate a page frame, but at this point all 4 of them are in use, so that means evicting an existing page to make room. To choose the victim, we follow a replacement policy that is implemented in software -- and we're told to use the Least Recently Used policy. So we look for the resident page that hasn't been used for the longest time, and that's page 3. We evict that page, bring in page 6, and update the page table to read

3: (frame=1), valid=0
6: frame=1, valid=1

The frame field of slot 3 doesn't matter, but we may as well leave it as 1. Putting all the entries together, you get the page table shown in your second table. The frame numbers are, naturally enough, shown in binary there.