Paging and Address Translation

Introduction

This shows the function used to map a logical address to a physical address for some paging schemes.  Throughout 
this handout, an address in virtual memory is a pair (logical_page, offset) where logical_page is the page number 
within the logical address space and offset the offset into that page.  Also, page_size is the size of the page (which is a 
multiple of 2). We will assume the entire program is in memory, so no error handling is given; were this assumption 
false, the situation where the requested address were not in memory would need to be handled (by generating a page 
fault and loading the necessary page):

Paging Address Translation by Direct Mapping

This method stores the page table in main memory and the address of this table in the process control block, in a reg-
ister called the page table base register.  Let the page table base register be called pt_base_register, and let memory 
represent the main store of the computer. Then:

function NL_map((logical_page, offset)): physical_address;

begin

	NL_map := memory[pt_base_register + logical_page] * page_size + offset;

end (* NL_map *)

In pictures, here is what is going on:

Paging Address Translation by Associative Mapping

In this algorithm, assoc_page_table represents an associative memory.  This function can check a type of memory 
called "associative memory" (or "cache" or "lookaside memory") which stores both a frame number and a page num-
ber.  The search is done in parallel, and is much faster than a linear (or binary) search.  The function returns the frame 
number associated with its argument:

function NL_map((logical_page, offset)): physical_address;

begin

	NL_map := assoc_page_table(logical_page) * page_size + offset;

end (* NL_map *)	

Paging Address Translation with Combined Associative and Direct Mapping

This combines the above two methods.  The array page_table is a small associative store that can hold only a few 
page numbers; there is also a page table kept in memory.  For this method, we shall assume that if there is no entry for 
logical_page in the associative memory, assoc_page_table returns -1.  Taking everything else as in the previous two 
sections:

function NL_map((logical_page, offset)): physical_address;

var	frame_number: integer;

begin

	frame_number := assoc_page_table(logical_page);

	if frame_number = -1 then						(* not in associative memory *)

		NL_map := memory[pt_base_register + logical_page]

							* page_size + offset;

	else

		NL_map := frame_number * page_size + offset;

end (* NL_map *)	

This is the most common method, and is used in modern computers with paging.