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

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?

closed as unclear what you're asking by brhans, Daniel Grillo, pipe, Neil_UK, jmsOct 9 '16 at 20:59

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• What system are you talking about? This sounds like total nonsense with no context. Also smells like homework. – Daniel Oct 3 '16 at 20:30
• Homework that has been finished months ago* (I got all solutions and now trying to understand it for exam). Is the first table total nonsense for you as well? What is known about the system: A computer that realizes virtual memory by paging. – cnmesr Oct 3 '16 at 20:33
• This is a question about an operating system, not about a CPU. It's the operating system that assigns physical pages to virtual pages (and stores this in the page table). – immibis Oct 4 '16 at 6:53

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.

$$\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.

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.)

• Wow thanks a lot for your answer, so long and detailled, very nice of you! I have understood the LRU now, also how page and offset are made up, how virtual to physical is done. But I still don't understand the order of the second table. I mean, the professor gives you the second table but it will be empty. Then he tells you to fill the table. How do you fill it in the exact same way? Why do we start with 11 first, then 00 right after,..? I will soon edit my post and make my second table so you see how I would have made it. – cnmesr Oct 4 '16 at 8:00
• Awesome, got it!!! Thanks so so much to both of you for helping me, I'm so happy at the moment :)) – cnmesr Oct 4 '16 at 16:02

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.

• Thank you very much for answer! I didn't give down vote and I don't know why someone did that... But what I still don't understand is, why we first start with 11, then 00, then 10.. and so on? Why? Please tell me if you know :) – cnmesr Oct 3 '16 at 21:19
• @cnmesr I was the one that somehow messed up with the downvote. It was accidental (mouse problem?) and I'd intended to upvote it. That's been corrected, I think. – jonk Oct 3 '16 at 21:20
• Hi jonk, maybe you can help me with my problem pls? I don't understand why second table we start with 11, then 00, 10. Where do these numbers come from? I would have started with 00, 01, 10,.. instead. – cnmesr Oct 3 '16 at 21:23
• I edited my answer in the hope of making it clearer, and corrected a mistake. Sorry for the poor formatting, but I don't have time to learn the markup now. Note that the page table entries are not filled in from top to bottom, but in the order that the memory references happen. Does that remove your confusion? – Mike Spivey Oct 3 '16 at 21:31
• I will be here tomorrow I need sleep because it's very late and I should already be in bed for 2 hour ago. Sorry but thank a lot for your answer and time for me!You here tomorrow so I can ask if I don't understand pls? – cnmesr Oct 3 '16 at 21:45