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):
This method stores the page table in main memory and the address of this table in the process control block, in a register 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:
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 number. 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 *)
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.