User’s View of a Program

Segmentation

• Memory-management scheme that supports user view of memory.
• A program is a collection of segments.  A segment is a logical unit such as:

                    main program,

                    procedure,

                    function,

                    method,

                    object,

                    local variables, global variables,

                    common block,

                    stack,

                    symbol table, arrays

Shared Pages

• Shared code

1. One copy of read-only (reentrant) code shared among processes (i.e., text editors, compilers, window systems).
2. Shared code must appear in same location in the logical address space of all processes.

• Private code and data

1. Each process keeps a separate copy of the code and data.
2. The pages for the private code and data can appear anywhere in the logical address space.

Inverted Page Table

• One entry for each real page of memory.
• Entry consists of the virtual address of the page stored in that real memory location, with information about the process that owns that page.
• Decreases memory needed to store each page table, but increases time needed to search the table when a page reference occurs.
• Use hash table to limit the search to one — or at most a few — page-table entries.

Hashed Page Tables

• Common in address spaces > 32 bits.
• The virtual page number is hashed into a page table. This page table contains a chain of elements hashing to the same location.
• Virtual page numbers are compared in this chain searching for a match. If a match is found, the corresponding physical frame is extracted.

Address-Translation Scheme

• Address-translation scheme for a two-level 32-bit paging architecture
• 
  
• 
• 
  
• 
  

Two-Level Page-Table Scheme

Two-Level Paging Example

• A logical address (on 32-bit machine with 4K page size) is divided into:

1. a page number consisting of 20 bits.
2. a page offset consisting of 12 bits.

• Since the page table is paged, the page number is further divided into:

1. a 10-bit page number.
2. a 10-bit page offset.

Hierarchical Page Tables

• Break up the logical address space into multiple page tables.
• A simple technique is a two-level page table.

Page Table Structure

• Hierarchical Paging
• Hashed Page Tables
• Inverted Page Tables

Valid (v) or Invalid (i) Bit In A Page Table

Memory Protection

• Memory protection implemented by associating protection bit with each frame.
• Valid-invalid bit attached to each entry in the page table:

1. “valid” indicates that the associated page is in the process’ logical address space, and is thus a legal page.
2. “invalid” indicates that the page is not in the process’ logical address space.

Effective Access Time

• Associative Lookup = e time unit
• Assume memory cycle time is 1 microsecond
• Hit ratio – percentage of times that a page number is found in the associative registers; ration related to number of associative registers.
• Hit ratio = a
• Effective Access Time (EAT)

                        EAT = (1 + e) a + (2 + e)(1 – a)

                               = 2 + e – a

Paging Hardware With TLB

Associative Memory

• Associative memory – parallel search
• Address translation (A´, A´´)

1. If A´ is in associative register, get frame # out.
2. Otherwise get frame # from page table in memory

Implementation of Page Table

• Page table is kept in main memory.
• Page-table base register (PTBR) points to the page table.
• Page-table length register (PRLR) 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/instruction.
• The two memory access problem can be solved by the use of a special fast-lookup hardware cache called associative memory or translation look-aside buffers (TLBs)

Free Frames

Paging Example

Paging Example

Address Translation Architecture