How can I use a page table to convert a virtual address into a physical one?

Question

Lets say I have a normal page table:

Page Table (Page size = 4k)

      Page #:  0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15          
Page Frame #:  3  x  1  x  0  x  2  x  5  x   7   4   6   x   x   x

How can I convert an arbitrary logical address like 51996 into a physical memory address?

---

If I take log base 2 (4096), I get 12. I think this is how many bits I'm suppose to use for the offset of my address.

I'm just not sure. 51996 / 4096 = 12.69. So does this mean it lay on page#12 with a certain offset?

How do I then turn that into the physical address of "51996"?

Poised

Answer 1

To determine the page of a given memory address, take the first P bits (of the N bit) number.

P = lg2(numberOfPages)
In your example, P=lg2(16)=4

So the first 4 bits of a given memory address will tell us the page. That means the rest should be the offset from the start of that page.

Your example address, 51996, is 1100101100011100 in binary. I.e. [1100:101100011100].

1100 (12 in decimal) is the page number
101100011100 (2844 in decimal) is the offset

Now we need to find where page 12 is in memory.
Looking at your frame table, it appears that page 12 is resident in the 6th frame. In a system where all memory is pageable (i.e. no memory mapped IO) the 6th page frame will be at (entriesPerPage*frameNum)-1

In this case, 4000*6-1 = 23999 (The "-1" is needed since memory is 0-indexed.)

In this case, 4096*6-1 = 24575 (The "-1" is needed since memory is 0-indexed.)

Now all we have to do is add the offset and we have the physical memory address:

23999 + 2844=26843 = 0x68DB

24575 + 2844 = 27419 = 0x6B1B

Done!

Hope this (edit) was helpful XD

Edit: Thanks to Jel for catching my mistake :) Thanks to user8 for catching my other mistake! (frameNum instead of pageNum).

Authoritarian

Does your answer mean that the virtual address is variable in length for different processes? For example, if there are two processes, one has 16 pages, and the other has just 1 page, then the bits used to indicate page number will be different, so the final length for the virtual address will be different. – Kappenne

@cheng: Addresses are of fixed length across processes, so if a process has just one page, all of its addresses will start with the same value. In the example above with 16 pages, the first four bits of a single-page process will be 0b0000. – Authoritarian

Why are you multiplying by 4000 instead of 4096 in the second to last step? – Osbert

@Jel: Good catch! It should be 4096. I'm guessing that when I originally read the question I assumed 4k===4000, though the question clearly mentions 4096 more than once. Thanks! – Authoritarian

in your formula (entriesPerPage*pageNum)-1 pageNum should be frameNum – Ablebodied

Answer 2

If I understand your question correctly (I probably don't), you want to know how to find the physical address from the virtual address using the page table structures. In that case, pretend you are the processor. Use the 10 most significant bits of the address to find the page table in the page directory (the top level page table). The next 10 bits are the index into the page table (the lower level page table). Use the address in that page table entry to find the physical page address. The last ten bits are the byte address into the page.

By the way, you would probably find a lot more people who would understand this type of question at an OS oriented site such as OSDev. I couldn't really go into much detail in this answer because I haven't done this type of stuff in years.

Rimola

Answer 3

This is might help:

    import java.util.Arrays;
    import java.util.Scanner;

    public class Run {

        private static Scanner input = new Scanner(System.in);

        public static void main(String[] args) {

            System.out.println("////////// COMMANDS //////////");
            System.out.println("Snapshot: S(enter)r, S(enter)m, S(enter)x, S(enter)p, S(enter)d, S(enter)c");
            System.out.println("time: t");
            System.out.println("Terminate: T#");
            System.out.println("Kill: K#");
            System.out.println("Start process: A");
            System.out.println("Quit program: quit");
            System.out.println("Deletes device: delete");
            System.out.println ("//////////////////////////////");
            OS myComputer;
            int hdd, cdd, printer, cpu, mem, page;
            hdd = cdd = printer = cpu = 20;
            mem = 1;
            page = 1;
            System.out.println("");
            System.out.println("|||| SYS GEN ||||");
            System.out.println("");
            mem = 0;
            System.out.println("Number of Hard-Drives:");
            while (hdd > 10) {
                String inpt = input.next();
                while (Asset.isInt(inpt) == false)
                    inpt = input.next();
                hdd = Integer.parseInt(inpt);
                if (hdd > 10)
                    System.out.println("Try something smaller (less than 10)");

            }

            System.out.println("Number of CD-Drives: ");
            while (cdd > 10) {
                String inpt = input.next();
                while (Asset.isInt(inpt) == false)
                    inpt = input.next();
                cdd = Integer.parseInt(inpt);
                if (cdd > 10)
                    System.out.println("Try something smaller (less than 10)");
            }

            System.out.println("Number of Printers:");
            while (printer > 10) {
                String inpt = input.next();
                while (Asset.isInt(inpt) == false)
                    inpt = input.next();
                printer = Integer.parseInt(inpt);
                if (printer > 10)
                    System.out.println("Try something smaller (less than 10)");
            }

            System.out.println("Amount of Memory:");
            while (mem <= 0) {
                String inpt = input.next();
                if (Asset.isInt(inpt))
                    mem = Integer.parseInt(inpt);
                if (mem<=0)
                    System.out.println("The memory size must be greater than zero.");
                else
                    break;
            }

            Integer[] factors = Asset.factors(mem);
            System.out.println("Enter a page size: "+Arrays.toString(factors));
            while (true) {
                String inpt = input.next();
                while (Asset.isInt(inpt) == false)
                    inpt = input.next();
                if (Asset.inArray(factors, Integer.parseInt(inpt))) {
                    page = Integer.parseInt(inpt);
                    break;
                } else {
                    System.out.println("Page size must be one of these -> "+Arrays.toString(factors));
                }
            }

            System.out.println("Number of CPUs (max10):");
            while (cpu > 10) {
                String inpt = input.next();
                while (Asset.isInt(inpt) == false)
                    inpt = input.next();
                cpu = Integer.parseInt(inpt);
                if (cpu > 10)
                    System.out.println("Try something smaller (less than 10)");
            }
            myComputer = new OS(cpu, hdd, cdd, printer, mem, page);
            myComputer.Running();
        }

    }

Moderate

it's in java but it should help – Moderate

Answer 4

first step : 51996 / 4000 = 12 -> p , remain= 3996 -> d (offset).

now look at the table p(12) = 6

second step : (6*4000) + 3996 : 27996

the physical address is 27996.

Hydrophilic

Answer 5

The following page table is for a system with 16-bit virtual and physical addresses and with 4,096-byte pages. The reference bit is set to 1 when the page has been referenced. Periodically, a thread zeroes out all values of the reference bit. A dash for a page frame indicates the page is not in memory. The page-replacement algorithm is localized LRU, and all numbers are provided in decimal.

Page Page Frame Reference Bit 0 9 0 1 1 0 2 14 0 3 10 0 4 - 0 5 13 0 6 8 0 7 15 0 8 0 0 9 - 0 10 5 0 11 4 0 12 - 0 13 3 0 14 - 0 15 2 0 a. Convert the following virtual addresses (in hexadecimal) to the equivalent physical addresses (provide answers in hexadecimal AND decimal). Also set the reference bit for the appropriate entry in the page table. (3) i. 0xBC2C ii. 0x00ED iii. 0xEA14 iv. 0x6901 v. 0x23A1 vi. 0xA999

Meridethmeridian