You are given this info:
- page size is 512 Byte
- CPU generates logic addresses with length of 12 Bit
- main memory is addressable bytewise and it can receive 4 pages in total
A number of things can be derived from this:
- Pages are 512 bytes, and main memory has 4 pages total. 4 * 512 = 2048. That means there are 2048 bytes of physical main memory (2^11 bytes = 4 * 2^9).
- Top 2 bits (vale 0 to 3) of the physical address also represent the physical page number
- Logical addresses are 12 bit which is 8 512 byte pages or 4096 bytes (2^12 bytes).
- The top 3 bits (0-7) of a logical address represent the logical page number.
My assumptions:
- If there are free physical pages (not mapped to any logical page), assume that the lowest numbered physical page is used first.
So you have 4096 bytes of logical memory but only have 2048 bytes of physical memory. So you can't have every logical page in memory at the same time. You can have 4 pages at a time. That is where Least Recently Used (LRU) algorithm comes in. When a logical address is found not to be in memory and all the physical pages are full, then you find the least recently used physical page and evict it from memory; associate a new logical page with that physical page. Usually an OS will swap a page to disk (backing store) if it is evicted from memory and if need be loads it back in when it is needed again.
So we are given the Logical addresses:
777, 2047, 1199, 1100, 546, 129, 3201
If we convert those logical addresses to 12 bit binary we have:
777 = 001 100001001
2047 = 011 111111111
1199 = 010 010101111
1100 = 010 001001100
546 = 001 000100010
129 = 000 010000001
3201 = 110 010000001
Assume that at the start all 4 of the physical pages 0(00), 1(01), 2(10), and page 3(11) are empty to begin with. Rest of answer uses page numbers in binary for convenience:
Page 00 = empty, page 01 = empty, page 10 = empty, page 11 = empty
Assume the processor gets a request for each of the logical addresses above in order - it must translate them to a physical address, and if the physical pages are all filled use LRU to find a page to get rid of, and associate it with the new logical page.
777 = 001 100001001
Look to see if our logical page 001 is mapped to a physical page. If not, find an empty physical page (use the first one). Physical page 00 is free. Associate logical page number 001 with physical page 00. Therefore when finished this translation we have:
Page 00 = 001, page 01 = empty, page 10 = empty, page 11 = empty
Logical address: 001 100001001 equals physical address 00 100001001
2047 = 011 111111111
Look at the physical pages to see if logical page 011 is in memory. It isn't. We find the next available physical page which is 01. We associate physical page 01 with logical page 011.
Page 00 = 001, page 01 = 011, page 10 = empty, page 11 = empty
Logical address: 011 111111111 equals physical address 01 111111111
1199 = 010 010101111
Look at the physical pages to see if logical page 010 is in memory. It isn't. We find the next available physical page which is 10. We associate physical page 10 with logical page 010.
Page 00 = 001, page 01 = 011, page 10 = 010, page 11 = empty
Logical address: 010 010101111 equals physical address 10 010101111
1100 = 010 001001100
Look at the physical pages to see if logical page 010 is in memory. It is. Page 10 already has logical page 010! Nothing to do. Reorder the list so physical page 10 is most recently used. It was already last used so nothing needs to be done.:
Page 00 = 001, page 01 = 011, page 10 = 010, page 11 = empty
Logical address: 010 001001100 equals physical address 10 001001100
546 = 001 000100010
Look at the physical pages to see if logical page 001 is in memory. It is. Page 00 already has logical page 001! Nothing to do. Reorder the list so physical page 00 is most recently used, so move it to the end of our list:
Page 00 = 001, page 01 = 011, page 10 = 010, page 11 = empty
becomes:
page 01 = 011, page 10 = 010, Page 00 = 001, page 11 = empty
Logical address: 001 000100010 equals physical address 00 000100010
129 = 000 010000001
Look at the physical pages to see if logical page 000 is in memory. It isn't. We find the next available physical page which is 11. We associate physical page 11 with logical page 000.
page 01 = 011, page 10 = 010, Page 00 = 001, page 11 = 000
Logical address: 000 010000001 equals physical address 11 010000001
Note: All our physical pages are now full at this point.
3201 = 110 010000001
Look at the physical pages to see if logical page 110 is in memory. It isn't. We look for the next available physical page - but no such free page exists. Using LRU we look at the least recently used entry (which will always be on the left of this list):
page 01 = 011, page 10 = 010, Page 00 = 001, page 11 = 000
Page 01 is on the left so it is the least recently use. We evict logical page 011 from physical page 01 and replace it with 110:
page 01 = 110, page 10 = 010, Page 00 = 001, page 11 = 000
Now since physical page 01 is most recently used move it to the end of the list:
page 10 = 010, Page 00 = 001, page 11 = 000, page 01 = 110
Logical address: 110 010000001 equals physical address 01 010000001
Observation
How does the above compare to the answer/solution in the table you gave? If you take all the lines above starting with Logical address: you'd get.
Logical address: 001 100001001 equals physical address 00 100001001
Logical address: 011 111111111 equals physical address 01 111111111
Logical address: 010 010101111 equals physical address 10 010101111
Logical address: 010 001001100 equals physical address 10 001001100
Logical address: 001 000100010 equals physical address 00 000100010
Logical address: 000 010000001 equals physical address 11 010000001
Logical address: 110 010000001 equals physical address 01 010000001
Compare that with the table you were given and they should be equivalent if I haven't made an error. The one thing we also know from the method above is that after the last logical address is translated we have these pages in physical (main) memory:
page 10 = 010, Page 00 = 001, page 11 = 000, page 01 = 110
Your question was probably designed to be as much about a student understanding LRU as it was about understanding physical and logical memory.
