Browse Prior Art Database

Low-Synchronization Translation Lookaside Buffer Consistency Algorithm

IP.com Disclosure Number: IPCOM000102535D
Original Publication Date: 1990-Nov-01
Included in the Prior Art Database: 2005-Mar-17
Document File: 6 page(s) / 273K

Publishing Venue

IBM

Related People

Rosenburg, BS: AUTHOR

Abstract

Operating systems for many current shared-memory multiprocessors must maintain translation lookaside buffer (TLB) consistency across processors. This article presents an efficient TLB consistency algorithm that can be implemented on multiprocessors that satisfy a small set of straightforward architectural constraints.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 24% of the total text.

Low-Synchronization Translation Lookaside Buffer Consistency Algorithm

       Operating systems for many current shared-memory
multiprocessors must maintain translation lookaside buffer (TLB)
consistency across processors.  This article presents an efficient
TLB consistency algorithm that can be implemented on multiprocessors
that satisfy a small set of straightforward architectural
constraints.

      In page-structured virtual memory architectures, page tables
de- scribe address spaces.  If several independent threads of control
are to share a single address space, they must all use the same page
table.  On a shared-memory multiprocessor, therefore, the processors
that execute those threads must share a single page table if the
threads are to run concurrently.  Most virtual memory architectures
include a translation lookaside buffer, that caches a portion of the
currently active page table.  In most of the shared-memory processors
that exist today, each processor has its own TLB, but the processor
hardware does not maintain the TLB consistently with the page table
it caches.  Furthermore, a given processor's TLB is not accessible
from other processors.  Therefore, when a processor makes a change to
a shared page table, it must flush the outdated information from its
own TLB and it must force the other processors sharing the page table
to flush the old entries from their TLBs.  In the TLB consistency
algorithm presented here, all locking and syncronization delays are
confined to the single processor that wants to change a shared page
table.  The other processors that share the page table must
participate in the algorithm, but the cost of their participation is
small and constant.

      The TLB consistency algorithm presented here can be used on
multiprocessor architectures that satisfy the following constraints:
    The hardware must not spontaneously modify page tables as a side
effect of normal processing.  In particular, it must not rewrite
entire page table entries in order to set individual page-usage bits.
    The hardware must provide an interprocessor interrupt whose
priority is greater than that of any device, including the clock.
    The hardware must provide atomic fetch&add, fetch&or, fetch&and,
and fetch&store operations.
    The hardware page table format must be such that individual page
table entries can be modified with atomic memory operations,
including fetch&op operations.

      The disclosed TLB consistency algorithm is illustrated in the
figure.
    For each processor:
          A set of currently active page tables.
          A pair of shared 32-bit counters: requests and
           updates.  Requests counts the number of TLB
           invalidation requests that have been sent to the
           processor, and updates counts the number of
           requests the processor has satisfied.
    For each page table:
 ...