�ݺ�ߣ

PAGE TABLES,
TRANSLATION
LOOKAHEAD BUFFERS
Submitted by
Tejal vinod kasture
Me[2nd year][1st sem]

Page Table
• Page Table Definition
• Implementation of Page Table
• Hardware Support
• Paging Hardware with TLB
• Memory Protection
• Page Table Structure
• Hierarchical Paging
• Shared Pages

Page Table Definition
A Page Table is the data
structure used by a virtual memory
system in a computer operating
system to store the mapping
between virtual address and
physical address.
Page
0
Page
1
Page
2
Page
3
Logical
memory
Page
0
Page
2
Page
1
Page
3
Physical
memory
Frame
number
1
4
3
7
Page
table

Two Concern to Discuss
• Implementation of Page Table concerning about the access time
of page table and load to main memory.
• Page table structure concerning about the page table size and
structure implementation

Implementation of Page Table (Hardware
Support)
• The hardware implementation of the page table can be done in
several ways.
• In the simplest case, the page table is implemented as a set of
dedicated registers. These registers should be built with very high
speed logic to make the paging address translation efficient .
• Problem with page size.
• Page table is kept in main memory.
• Page table base register (PTBR) indicates size of the page table.
• In this scheme every data/instruction access requires two memory
accesses. One for the page table and one for the data/instructions.
• Problem with access time.

Paging Hardware With TLB
• The CPU's memory management unit (MMU) stores a cache of
recently used mappings from the operating system's page table.
This is called the translation look a side buffer (TLB).

Memory Protection
•Memory protection implemented by
associating protection bit with each frame.
- One bit can define a page to be read-Write or read-only
•Valid-invalid bit attached to each entry in
the page table:
• “valid” indicates that the associated page is in the process’ logical address
space, and is thus a legal page.
• “invalid” indicates that the page is not in the process’logical address
space.
• page-table length register (PTLR), to indicate the size of the page table.

Page Table Structure
• Most modern computer systems support a large logical address
space(2^32 to 2^64). In such an environment, the page table
itself becomes excessively large. For example, consider a
system with a 32-bit logical address space. If the page size in
such a system is 4 KB (212 ), then a page table may consist of
up to 1 million entries (2^32/2^12). Assuming that each entry
consists of 4 bytes, each process may need up to 4 MB of
physical address space for the page table alone.

Hierarchical Page Tables
• Knowing as Multilevel Paging
• The page table might be too big to fit in a contiguous space, so
we may have a hierarchy with several levels
• Break up the logical address space into multiple page tables.
• A simple technique is a two-level page table, three-level page
table.

Two-Level Paging Example
• A logical address (on 32-bit machine with 4K page size) is
divided into:
• a page number consisting of 20 bits.
• a page offset consisting of 12 bits.
• Since the page table is paged, the page number is further divided
into:
• a 10-bit page number.
• a 10-bit page offset.
• Thus, a logical address is as follows:
where pi is an index into the outer page table, and p2 is the
displacement within the page of the outer page table.
page number page offset
pi p2 d
10 10 12

Three-Level Paging Example
A logical address (on 64-bit machine with 4K page size) is
divided into:
The next step Would be a four-level paging scheme.

Shared Pages
• Shared code
• One copy of read-only (reentrant) code shared among processes (i.e., text
editors, compilers, window systems).
• Shared code must appear in same location in the logical address space of
all processes.
• Private code and data
• Each process keeps a separate copy of the code and data.
• The pages for the private code and data can appear anywhere in the logical
address space.

Translational look ahead buffer
• What is Translational look aside buffer.
• Use of Translational look aside buffer.
• How it works.
• Content addressable memory (CAM)
• Page walk.
• Structure of TLB.

What is Translational look aside buffer (TLB)
The translation look aside buffer (TLB) is a cache for page table
entries. It works in much the same way as the data cache: it stores
recently accessed page table entries. It also relies on locality of
reference
Use of TLB
It is cumbersome and time consuming to calculate the physical
address from linear address for every memory location. A
Translation Look-aside Buffer (TLB) simplifies the process.
TLB is a page table cache, which stores the 32 recently accessed
page table entries.

How it work’s
The paging unit receives a 32-bit linear address from the
segmentation unit. The upper 20 bits of the linear address is
compared with all 32-entries in the translation look-aside buffer
(TLB) to check if it matches with any of the entries. If it matches,
the 32-bit physical address is calculated from matching TLB
entry and placed on the address bus.

Content addressable memory and page walk
The TLB is sometimes implemented as content-addressable
memory (CAM). The CAM search key is the virtual address and
the search result is a physical address. If the requested address is
present in the TLB, the CAM search yields a match quickly and
the retrieved physical address can be used to access memory. This
is called a TLB hit. If the requested address is not in the TLB, it
is a miss, and the translation proceeds by looking up the page
table in a process called a page walk.

Page walk
The page walk is an expensive process, as it involves
reading the contents of multiple memory locations and
using them to compute the physical address. After the
physical address is determined by the page walk, the
virtual address to physical address mapping is entered into
the TLB.

Structure of TLB
TLB has 4 sets of eight entries each. Each entry consists of a
TAG and a DATA. Tags are 24 bit wide. They contain 20 upper
bits of linear address, a valid bit and three attribute bits. The Data
portion of each entry contains higher 20 bits of the Physical
address.

�ݺ�ߣ

Ppt

Recommended

More Related Content

Similar to Ppt (20)

Recently uploaded (20)

Ppt

Editor's Notes