Search code examples
cachingmemorycpupaginglru

Understanding relationship between Physical and Logical addresses and use of LRU

The CPU of a computer which realises memory by paging generates the following logic addresses (in decimal):

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

  • 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

512 Byte page size means 2^9 Bytes, so the offset of the logic address will be made up with 9 Bits. We got length of 12 Bits in total, so 12 - 9 = 3, so the first 3 Bits will be used for the page!

That's all for the logic address which I understand completely. But what about the physical address? The offset of the physical address is same as the offset of the logical address. But the page is different and I don't understand why it is? I also don't see pattern, at beginning first page is 00, then 01.. etc. why?

The only additional info the task gave: If all page frames are in use the LRU will be applied...

enter image description here

Solution

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