Page Table and Mapping

Page table is a data structure used by a virtual memory  in a computer OS to store the mapping in-between virtual addresses and physical addresses.

It maps the page number to its frame number where that particular page is stored. CPU generates the logical address of page but main memory recognizes the Physical address. Then Page Table maps the logical address to Physical address.

Main characteristics of page Table

• When a process is loaded to execute then its page table is also loaded in main memory. Page table contains the information about every entry of page which is loaded into the frame of main memory.
• Size of page table varies from process to process. Having the more entries into page table greater the size will be and vice versa.
• Page size of process is always equal to frame size of main memory. If the page size is 2Bytes the size of frame is also 2Bytes because pages are loaded into frames of main memory.
• Each process has its unique independent table

Greater the number of entries in page table of a process then higher will be the size of page table. IF the size of page table is greater than frame size of main memory then Multi-level paging comes into picture. look at diagram of page table given below for more details.

Logical to Physical Address mapping through Page Table

There are four main steps for mapping the logical to physical address through page table.

1. Generation of logical address

CPU creates logical address for each page of process. This created address holds two things:

• page number: it tells the required page of process
• offset: it tells the specific byte from that page

2. Scaling

CPU use the page table base register to store the base address of page table. The value of page table base register is added to the page number. So that, the actual location of that page in the page table, can be obtained.

3. Generation of physical Address

When the required page is found in the page table then its corresponding value which is frame number is easily obtained. It is the physical address because it is the address of main memory where the actual data is present.

Physical address also has two parts

• Frame number: it is the address of main memory where the CPU request page is present.
• Offset: offset of the logical address is similar to offset of physical address. So, it will copy from the logical address to physical address.

4. Getting Actual Frame Number

Frame number and offset of the physical address are mapped to the main memory. So that, the actual byte or word address could be accessed.

Let explain Page Table and Mapping with example

Let process P1 and P2 having the size 10Bytes and 8Bytes respectively, exist in secondary memory. There are 5 pages of process 1 and 4 pages of process 2 but each page has size of 2bytes. Let suppose, 4 pages of process 1 and 4 pages of process 2 are exist in the main memory. But the page table contains the whole record of its pages whether they are loaded in main memory or not. Let suppose CPU request for the 2nd byte of 5th page of process 1 which exist in main memory.  Then the explanation with diagram is.

Step 1: Generation of Logical address:

1001 is the Logical address where page No is 100 and 1 is offset.

Step 2: Scaling

Base address registers value 000. Because page table base register value is 000.

By adding of page no and page table base register the result is 100. Then 100 is CPU required page .

Step 3: generation of Physical address

Corresponding frame of page 100 is 01001.

Copy the offset of logical address and add it to frame no. Then the result is 010011. So, 010011 is the required frame number in main memory.

Step 4: Getting actual page no.

So, 010011 is the actual physical address where the data of required page is present. Now CPU can get the required data easily.

In the very next lectures we will see the page table entries.

Page Table Entries 

Page table has page table entries and each page table entry contains a frame number and optional status like present/Absent bit, Protection, Reference, Caching and Dirty bit.

 

1. Frame Number:

It gives the frame number of main memory for required page.

2. Present/absent bit:

Present or absent bit tells about the presence or absence of particular page you are looking for in main memory. If required page is found then it is a case of Page Hit and denoted by 1. But If required page is not found then it is a case of Page Fault and denoted by 0. Page fault is control by OS, using virtual memory concept.

3. Protection bit:

Protection bit tells about the protection that you want to apply on that page. There are three permissions are available on any pages which are read, write and executes

4. Referenced Bit

Referenced bit tells whether this page has been accessed in the last clock cycle or not. If it accessed earlier then reference bit set to 1. If this page referred first time then reference bit set to 0.It is used in memory access algorithms like LRU etc.

5. Caching Enabled/Disabled

Cache is a memory which is faster and closer to CPU. Least Recently used information’s are stored in Cache. Cache can be enabled or disabled for pages.

Sometimes we need the fresh data (Dynamic). As If we use an account and our balance is dynamically change with the time then in such cases, keep cache disabled.

Sometimes we need the Static data as a video which we use again and again then for this type of tasks cache can be enabled.

6. Modified bit:

It is also called dirty bit. it tells whether the page has been modified or not. If the value of modified bit is 1 then it means the value of this page is updated in RAM by CPU with the permission of Process Write. And If dirty value=1, then OS will update the value of this page in hard disk. If dirty value=0, then it means no changing is performed in RAM by CPU.