JPH0332092B2 - - Google Patents

Description

[Detailed description of the invention]

INDUSTRIAL APPLICATION FIELD OF THE INVENTION This invention relates generally to computer memory systems, and more particularly to virtual memory systems. To explain in more detail, this invention:
The present invention relates to an apparatus for converting virtual addresses to real memory addresses and performing certain control functions within a memory hierarchy. [Prior Art] In modern computer systems, when a program is executed, it must be executed somewhere in the system (i.e., at some level of the cache/main memory/direct access storage (DASD) storage hierarchy, or on a distributed network). Attempts are frequently made to access data or code residing on nodes in the network. For example, consider what a program must understand to make this access in the most rudimentary system: (a-1) Where is the data (or code) located? The location will determine what type of address (eg, a 24-bit main memory address, a disk track sector address, or a network node address) must be used for access. Also, depending on the location of the data, what type of instruction (e.g. load/store/branch for main memory access, command word for disk access, or command word for network access) is required to perform the access. line protocols) should be used. (a‐2) Is this data used in conjunction with other executable programs? If so, access cannot proceed unless some type of lock is removed. If no other program can see at this point the changes that this program is attempting to make to the data, a store command must be issued to the private address. (a‐3) Should this data be recoverable? If so, some "journaling" strategy must be taken so that the previous constant state of the data can be retrieved when needed. Now suppose that in this very rudimentary system, a program is actually required to perform the above identification operation on every access. The following consequences would then arise: (b-1) If this program must be general-purpose, it must be able to handle the most frequently occurring "simple and safe" requirements, i.e., for private use of main memory. access will be extremely slow even for non-recoverable data. (b-2) If a program is to run well, it will be locked into one access mode. Then the program will not work correctly on data with different characteristics. (b-3) The program will be complex, large, and error-prone. Modern computer systems therefore address the above problems to varying degrees. For example: (c-1) Relocatable architectures typically allow private, non-recoverable, non-persistent data and programs to be stored with address sizes of 16 to 32 bits (typically for temporary computations). It becomes uniformly addressable. When these architectures are implemented with proper look-aside hardware, the vast majority of these addresses are executed at cache or main memory speeds. And only when this address translation hardware fails (which happens less than 1 in 100 times) does the system go to the trouble of accessing the relocatable table structure. Furthermore, only when the relocatable table structure fails (ie, when the data is not in main memory) does the system incur page fault overhead. Thus, in the system described above, penalties are paid only when they are actually needed, which would be the goal of good architecture. (c-2) When the program must persist data beyond its execution capabilities, modern systems require explicit instructions on the ``access method'' performed by the software instead of load/store/branch instructions. Access is required based on specific requests. These access methods generally support data organized into certain fixed volumes called "records and files." The “instructions” for access are commonly referred to as read/writes or “gets/puts.” This data is neither shared nor recoverable; it is effectively However, for each access, the program must pay the overhead of these explicit “read/write” requests. Such access methods are When configured, they result in less complex programs that can be used on more general systems as well as rudimentary systems. However, the execution speed of these accesses is uniformly slower than the load/store method, and Accessed data must be organized into a suitable aggregate structure. (c-3) When data is to be shared or recovered, modern systems require a “database subsystem” implemented by software. An explicit request is required.The speed of these accesses is generally slower than that of the above access methods, not only because of the additional functionality of lock and journal management. , because the types of data aggregation these subsystems support (e.g., data relationships, hierarchies, etc.) are themselves fairly complex. It may be possible to make the data non-persistent, but you will have to pay the overhead for each access request.In addition, systems are in place to recover non-persistent data using a method called "checkpointing." A programmer attempting to create a recoverable application must deal with three different functions: checkpointing data in a computation, explicitly backing up files, and "commit" commands to the database. IBM System/38 is more advanced than other systems in providing at least a uniform address structure for all data.However, that system also makes all addresses large, reduces access, and reduces architecture. This is accomplished at the expense of increasing the storage and hardware required to achieve this, and even providing a uniform means for data sharing and recovery. There are also various techniques that allow a single memory to be shared by multiple computer programs, whether executed by essentially a single unit or by multiple processing units. has been known for a long time. Sharing memory among multiple programs in this way requires an extremely large amount of parent memory.
This required capacity is often much larger than the actual capacity of the memory. For example, if a system uses a 32-bit addressing scheme, 2^32 bytes of virtual storage capacity is available. This virtual storage space is conventionally thought of as being divided into a predetermined number of regions or segments. Each of these regions or segments is then further divided into pages, each page having a predetermined number of lines with a predetermined number of bytes. Thus, the designations or addresses of segments and pages allocated to virtual storage space are arbitrarily programmed designations and not their actual locations in main memory.
Therefore, virtual segments and pages are typically randomly located throughout main memory and are swapped in or out between secondary storage and main memory as needed. In order to randomly arrange segments and pages in main memory, virtual addresses are converted to real addresses using a set of address translation tables, conventionally called page frame tables, located in main memory. things are necessary. In large virtual systems, a large number of such translation tables are used. There are several different ways to configure these, but the essential feature is that a particular virtual address is associated with a memory location in the table that contains the real address (if any) that corresponds to that virtual address. This means that it must be mapped logically. Mechanically, the operation of such an address translation table is as follows: The most significant bit of a particular virtual address is used to access a particular section of the translation table. This conversion table is related to a specific frame or segment, and in this conversion table, a search is performed to see whether or not a specific virtual bit is included in the lower bits. If a specific virtual bit is included there, a further search is made to find out what kind of real address corresponds to that virtual address. Each page table specified by a virtual frame address contains the real locations of all pages in one of the frames.
Therefore, if a particular frame is divided into, say, 16 pages, there will be a separate frame table with a 16-page table for each frame, and an entry specifying the particular set of individual page tables. will exist. However, these are generalized descriptions;
It should be appreciated that there are many different ways of configuring address translation using page tables, starting from virtual addresses created by the CPU, and so on. In the description of the preferred embodiment of the present invention, which will be described later, the hash address table (HAT) and the inverse page table (IPT) will be described in detail. Now, when performing a real address translation, regardless of the details of the overall system configuration or the use of page tables, a unique entry is created in the page/frame table, and the page table uses the current virtual address as an argument. accessed by The desired entry into the page table is then typically found after accessing multiple memories. At this point, a check is made to determine whether all system protocols are being followed, and if so, the real address of the requested page in storage is accessed from the page table. The byte portion of a virtual address is essentially a relative address, which is the same in real and virtual addresses. Thus, once the desired real page address portion of the virtual address has been translated, that byte portion is concatenated to the real page address location to create a real byte address in main memory. By the way, as is well known in modern virtual memory systems, in order to avoid having to translate virtual addresses every time memory is accessed, the table for translating virtual addresses to real addresses is now stored in a directory. Translation table (DLAT) or address translation table (Translation Look-aside Table: TLB)
A specific set of fast-accessible tables called or maintained in fast memory. Furthermore, the above
DLAT or TLB are also used in the present invention.
These tables or buffers are generally particularly fast or fast-accessible memories, and can be accessed much faster than the page frame tables described above. This therefore saves a lot of computer execution time since frequently used virtual addresses are stored in this table for fast access. The effectiveness of such a TLB address translation system is due to the fact that after the first access to a particular virtual page, there will be a very large number of accesses to that same virtual page during the execution of a given program. It is affirmed based on. Also,
As mentioned earlier, subsequent accesses are to different lines and bytes within a page, but the conversion from a virtual page to a real page is independent of which lines and bytes are addressed. First, the pages are the same. That is, the use of a TLB reduces the translation circuitry that must be performed (in the page frame table), thus providing a significant effect on the overall operation of the virtual memory system. As previously mentioned, virtual memory systems have been well known in computer technology for many years. Also,
It is also well known that virtual addresses must be translated into real addresses via some kind of relocation means or address translation means which should ensure the translatability of virtual addresses into real addresses.
Therefore, it is impossible to list here all the patents and papers related to virtual storage devices, but the following prior art is sufficiently illustrative as a typical address translation mechanism, and the present invention The inventors believe this is the closest known technology for . First, U.S. Pat. No. 3,828,327 to Berglund et al. describes a storage control technique for expanding memory by adding a most significant bit to an address. The most significant bit is not part of the program's apparent address, but is controlled by different system modes such as interrupt mode, I/O (input/output) mode, etc. This patent relates to a memory expansion system that incorporates appropriate address translation hardware. Second, U.S. Pat. No. 4,042,911 to Bourke et al. discloses a system for expanding main memory, which system apparently includes address translation means. However, none of these patents disclose the concept of virtual address extension or the provision of special lock bits to both the TLB and page frame table. ACM SIGPLAN published April 1982
MOTICES, Vol.17, No.．． “The 801” described in 4.
A paper by George Radin titled ``Minicomputer'' gives a general description of an experimental computer, a computer whose operating characteristics are such that the relocation mechanism has a specific purpose. U.S. Pat. No. 4,050,094 to Bourke et al. discloses a memory arrangement with an address relocation converter having a stack segmentation register. The unique segmentation registers disclosed are utilized to store allocated real addresses of physical blocks in main memory, rather than the extended virtual addresses utilized in the present invention.Mitchell Another US Pat. No. 4,251,860 discloses a memory addressing system with a virtual addressing device for realizing a large addressing memory.
This patent describes dividing a virtual address into a segment part and an offset part. However, the segment portion and the segment register connected thereto are used in the conventional method of dividing addresses, and their operating state is completely different from the address translation scheme of the present invention. US Pat. No. 4,037,215 to Birney et al. discloses a system very similar to that of US Pat. No. 4,050,094, discussed above. That is, in that system, columns of segmentation registers are used to specify particular blocks of real memory. The patent further teaches the use of "read-only" valid bits connected to certain segmentation registers.
However, these bits bear little resemblance to the special purpose lock bits provided in the hardware of the relocation mechanism of the present invention. No. 4,077,059 to Corde et al. discloses a hierarchical memory system with special controls to facilitate journaling and copyback. This patent describes a plurality of dual memories in which the current version of the data is held in one of the dual memories, changes in the data are signaled to the other of the dual memories, and in which This facilitates subsequent journaling and copyback operations. The hardware and control means of this patent also bear little resemblance to the lock bit system of the present invention. U.S. Pat. No. 4,064,948 to Hogan et al. discloses an address translation system. The system has means with counters, each having an entry into a Direct Translation Table (DLAT). U.S. Pat. No. 4,218,743 to Hoffman et al. constitutes one example of several patents previously listed relating to the relocation architecture of the IBM System/38. This patent is
This describes a simplification of how I/O handles addressing operations in virtual memory computer systems. Other patents related to virtual memory systems include U.S. Patent Nos. 4170039 and 4251860.
No. 4215402, etc. U.S. Pat. No. 4,020,466 to Corde et al. also discloses a memory system that incorporates special means to simplify journaling and copyback procedures. However, this patent has no bearing on the lock bit control means of the present invention. Lowlor, US Pat. No. 3,942,155, discloses a scheme for partitioning segments of a certain shape in a virtual memory system. However, the segmentation scheme employed in this patent is quite different from the segmentation scheme of this invention used to extend virtual addresses. Also, cite U.S. Pat. No. 4,215,402 as an example of the use of various hashing schemes to access virtual memory translation mechanisms. [Problems to be Solved by the Invention] An object of the present invention is to solve the problem from a virtual memory address to a real memory address by using a table that combines a hash address table and a reverse page table in a virtual storage device. The goal is to reduce the amount of hardware required to support the conversion operation. SUMMARY OF THE INVENTION The present invention relates to a combined table used in a system for converting virtual memory addresses to real memory addresses. This combined table utilizes hashed addresses formed from virtual addresses. The virtual address in the hash address is then indexed for further page table access. That is, the page table includes a virtual memory address that individually corresponds to each real memory address. The present invention provides a means and associated table for hashing a selected virtual address to create a hashed address. This combined table consists of a first list of individual virtual addresses for each memory address, and a second list that binds each hash address to its expected initial virtual address. The scheduled initial virtual address is comprised of a concatenated group of virtual addresses that, when hashed, create a combined hashed address. The system of the invention further includes means for searching each concatenated group in the table until a selected virtual address is located from the first list in response to the location of the virtual address. and means for accessing the real memory address of the located virtual address. [Embodiment] (A) Overview of virtual address-real address translation mechanism FIG. 1 is a schematic block diagram of a virtual address-real address translation mechanism according to an embodiment of the present invention. The conversion mechanism includes the logic necessary to interface with up to 16 Mbytes of storage. At this time, the storage device may be either interleaved or non-interleaved, and may be either static or dynamic. This conversion mechanism is functionally divided into three parts. That is, in FIG. 1, logic circuit 1 as a CPU storage channel (CSC) interface
0 is common front end circuit 12 (CFE)
, an address conversion logic circuit 14 , and a storage control logic circuit 16 . Among these, the common front end circuit 12 is for supplying an appropriate protocol to the address translation logic circuit 14 and the storage control logic circuit 16 from the storage channel. All information data passing back and forth via the storage channel will be processed by this common front end circuit 12. Address translation logic 14 also serves to translate virtual addresses received from the storage channel into real addresses used to access the storage device. To this end, address translation logic 14 includes address translation buffers (TLBs) configured as a collection of 16 mutually congruent, bidirectional classes. Furthermore, the address translation logic circuit 14 is provided with a logic circuit for automatically reloading the page table of the main memory into the input terminal of the TLB in response to a request. Storage control logic circuit 16 is for interfacing address translation logic circuit 14 to a storage device. When a dynamic memory is used as a storage device, refresh control of the dynamic memory is also performed by the storage control logic circuit 16. At this time, it is important to note that
This invention resides primarily in the general structural combination and functional operation of well-known computer circuits, devices, and functional units, and not in the specific detailed structure thereof. That's true. Therefore, the structures, control means, and arrangements of these well-known circuits, devices, and blocks will be illustrated using block representations and functional diagrams for ease of understanding, and only those portions that are closely related to this invention will be described in detail. Please understand that the diagram is shown below. This is because a detailed description of the structure would obscure the focus of this invention, and well-known parts that are not the focus of this invention are only functional descriptions and are not very obvious to a person skilled in the art. This is because I think there will be. Furthermore, various parts of these systems are
Appropriate emphasis or functional description has been placed to emphasize particularly relevant features of the invention. The following description will enable those skilled in the art to appreciate the possibilities and capabilities of the disclosed memory system, and the disclosure will enable those skilled in the art to apply and implement the memory system of the present invention in a variety of computer architectures. I believe it is sufficiently detailed. Now, let's return to the explanation of the embodiment. Whether an address is translated (that is, treated as a virtual address) or as a real address in the system of Figure 1 depends on the value of the translation mode bit (T bit) on the CPU storage channel (CSC). controlled. Each device that makes some request on the CSC will control the value of the conversion mode bit for each request. This conversion mode bit is taken from the appropriate area of the memory access instruction issued by the CPU. A T-bit value is created by the attached adapter in response to a storage access command issued by an I/O device. If the T bit is “1”, the memory address (check instruction, data load, data store)
is sent to the address translation logic circuit 14. Furthermore, if the T bit is "0", the storage address is treated as a real address. Note that within the scope of the architecture disclosed herein, storage protection is not enabled for storage requests that have not been sent to address translation logic circuit 14. However, the recording of references and changes
It is valid for all storage requests regardless of whether the storage request is sent to address translation logic 14 or not. Now, regarding the address sent to the address translation logic circuit 14, the translation operation proceeds as follows. Although described below as a process that proceeds strictly logically and sequentially, portions of these functions may be performed in parallel by various execution operations. The address translation mechanism of the present invention employs a "single level storage" address structure. This address translation mechanism provides support for the following in the preferred embodiment disclosed herein: (a) multiple independent virtual address spaces (b) 4 Gbyte address space (c) on-demand paging (d ) 2048-byte or 4096-byte pages (e) Storage protection mechanism (f) Shared segments for instructions and data (g) 128-byte line journaling and locking (h) Up to 16 GB real memory addressability ( i) references and modified bits for each real page; (j) hardware assistance for loading real addresses, invalidating address translation buffer (TLB) inputs, and storing exception addresses;
It is treated as if it were mapped onto a single 40-bit address space consisting of 2 segments. That is, the 32-bit address received from the CPU storage channel (CSC) is
The four most significant bits are used to convert to a 40-bit address (a "long virtual address") to select one of the 16 segment registers. This includes the 12-bit contents of the selected segment register and the 32-bit contents received from the SCS.
Remaining 28 bits after removing the top 4 bits
This is a concatenation of bits. This 40-bit virtual address is translated into a real address by an address translation mechanism to access the storage device. Note that it is easy to see that the size of the virtual address varies somewhat depending on the hardware. Now, at any given moment, we have only 4 GB of storage, i.e. 256 MB of capacity, designated as 16 segment registers.
Only 16 segments are addressable.
This fact allows the operating system to create multiple independent virtual address spaces by loading appropriate values into the segment registers. According to this method, in the marginal case, completely independent
We can create 256 4GB address spaces. But (like the core code)
Often some segments will be shared across multiple address spaces. A storage protection mechanism similar to the IBM System 370 storage protection mechanism is also provided on the 2K or 4K byte page substrate. Storage and fetch protection is supported by protection keys (equivalent to the keys in the IBM System 370's program status word) that are independently specified for each 256 Mbyte segment. Additionally, the persistent storage class is supported by a set of "lock bits" associated with each virtual page. This lock bit increases the granularity of storage protection (128 bytes for a 2K page or 256 bytes for a 4K page).
It effectively extends to a "line" of memory, allowing the operating system to detect changes to retained variables and automatically journalize the changes. Note that the protected storage class used here means storage that resides on disk file storage. (B) Definition of special terms used in this example The following terms will be used throughout the following explanation, and will be defined here in advance to simplify the explanation. Byte Index: A number ranging from 0 to 2047 for 2K byte pages and 0 to 4095 for 4K byte pages that identifies a byte within a page or page frame. It is for the purpose of
For a 2K byte page, this byte index starts from the lower 11 bits of the effective address.
In the case of a 4K byte page, it is taken from the lower 12 bits of the effective address. Modified bit: One bit associated with each page frame individually.The modified bit is set to “1” whenever the next memory reference (write only) is made to that page frame. Ru. Effective Address: A 32-bit storage channel address generated by a device on the storage channel. This effective address may be the address output by the host CPU for a fetch instruction, a data load, a data store, or even a DMA (direct memory access) address.
The address may be an address generated by an I/O device on a storage channel, such as an address. Line: A 128-bit portion of a page on a 128-byte boundary. These 128 bits are the number of memories controlled by lock bits (described later). Lock Bit: One bit of a set of 16 bits connected to each page of a retained storage segment. Each lock bit is connected to one line of storage. The values of the transaction ID, write bit, and lock bit in a given line then determine whether to accept or deny a storage address request within the protected storage segment. Page: A storage area with a capacity of 2048 bytes on a 2048-byte boundary, or a storage area with a capacity of 4096 bytes on a 4096-byte boundary. “Page” correctly refers to virtual memory,
A “page frame” indicates real memory. but,
The term "page" is conventionally used to refer to both virtual and real memory. Page frame: 2048 on a 2048 byte boundary
A storage area with a capacity of 4096 bytes, or a storage area with a capacity of 4096 bytes on a 4096-byte boundary. The page exists in a page frame or on external storage (for example, a disk). Page table: Contents in main memory that are a combination of a hash anchor table and a reverse page table. This page table is used to translate virtual addresses to their corresponding real addresses. Note that the page table is sometimes referred to as HAT/IPT. Protection Key: A one-bit value in each segment register that indicates the privilege level of the currently executing process with respect to accessing data within a given segment. This protection key is similar in function to the IBM System 370's program status word key, except that it is provided for each segment individually rather than for all addressable memory as a whole. Real address: This is the result obtained from the conversion operation, and the lower 11 (or 12) bits of the effective address contain the real page index (described later) 10 to 13.
It is a concatenation of bits. Actual page index: 0 to 8192 (13 bits)
This is a number in the range of , and is used to identify page frames in real storage. In some embodiments, the 13-bit value may be limited to about 10 bits, which would limit the maximum amount of real memory to be supported to 2K byte pages of 2M bytes. Reference bit: One bit connected to each page frame. This reference bit is set to "1" whenever the next storage reference signal (read or write) is issued in a frame. Segment ID: A number in the range of 0 to 4095 (12 bits) for identifying a 256 MB virtual storage segment. Segment IDs concatenated with virtual page indexes specify individual pages within the 40-bit virtual address space. Storage key: A 2-bit value in the contents of each TLB (described later), which indicates the level of storage protection linked to a unique page. This key is similar in function to the storage keys associated with each memory page in the IBM system 370. TLB: Address translation buffer (Translation)
Look-aside Buffer). This TLB is virtual-
This is hardware with real mapping.
Note that in some embodiments, the TLB may include only a portion of this mapping at any given time. In addition to the mapping, the TLB may also contain other information associated with the TLB, such as translation identification signals, storage keys, lock bits, and the like. Transaction ID: 0 to 255 (8 bits)
is a number in the range , to identify the ``owner'' of the set of lock bits currently loaded into the TLB. Virtual address: The segment ID and the lower 28 bits of the effective address are converted into the lower 28 bits of the address translation mechanism.
It is a 40-bit address formed by combining with 28 bits. Virtual page index: A number ranging from 0 to 131072 (17 bits) for a 2K byte page, or 0 to 65536 for a 4K byte page.
(16 bits) to identify a page within a virtual memory segment. When the virtual page index is 17 bits long, the effective address range is 4 to 4.
20 bits, or if the range is 16 bits, it will occupy 4 to 19 bits of the effective address. (C) Hardware for the address translation mechanism Let's now explain the hardware required to support the address translation mechanism. First, the TLB has an arbitrary number of contents, and each of these contents is for controlling translation of a virtual address of one page into a real address. The details of TLB configuration are implementation dependent.
Two implementations are then possible. a content addressable memory (CAM) addressed by segment ID, and a virtual page index with one content per real storage frame. The CAM index is considered to be equal to the real page index. Also,
A federated set of TLBs may be considered addressed by some low order bits of the virtual page index. Additionally, the real page index will be contained within a field with the content of the TLB. The contents of each TLB can be read and written individually by the CPU using an IOR (input/output read) instruction or an IOW (input/output write) instruction. The contents of the TLB include the following fields: First, the 32-bit effective address input (from the CPU or I/O device) is expanded to 40 bits by concatenating the segment identification address to this effective address. . This virtual address is then transferred to translation hardware and translated to an equivalent real address. Now, let us describe the process by which a virtual address is translated into a real address.
I will show it in detail below. (D) Address conversion operation The highest four bits of the input valid address are given to the segment table as an index and are used to select one of the 16 segments. Now, referring to Figure 2,
The above is the sequential allocation of entry numbers 0 to 15.
There are 16 segments. As shown in the figure,
From the selected segment register, a 12-bit segment ID (segment identification bit) and
One segment special bit and one key bit are obtained. Special segment bits and key bits are used for access verification described below. Next, referring to FIG. 3, the 12-bit segment ID is combined with the 28-bit address from the 4th bit to the 31st bit of the input effective address to form a 40-bit virtual address. Of this effective address, the lower 11 bits for a 2K page and the lower 12 bits for a 4K page are used as a byte address (byte index) for the selected real page. The remaining 29 bits (28 bits for 4K pages) are then transferred to the conversion hardware. Referring now to FIG. 4, the address translation system shown in this figure uses an address translation buffer (TLB) to perform translations of frequently used virtual addresses. Additionally, hardware is used to automatically update the contents of the TLB from the main memory page table when a new virtual address is brought into the TLB for translation. The format of each TLB is shown in FIG. The system of Figure 4 uses two TLBs, each with 16 entries (content), ie, a set of 16 congruent classes and associative bidirectionalities. The lower four bits of the virtual page index are used to address both TLBs in parallel. The address tag entry (labeled "tag" in Figure 4) in each TLB is a segment that is combined with the remaining bits of the virtual page index (25 bits for 2K pages, 24 bits for 4K pages). Compare with ID. Then, if the segment ID and address tag entry are equal and the contents of the TLB are valid (as indicated by the valid bit V in Figure 5), then the federated TLB contains the translation information corresponding to the given virtual address. It will have . Now, the real page number field (“RPN” in Figures 4 and 5) in the selected TLB entry.
) contains the number of the real page in main memory that is mapped to the given virtual address. if,
If this number is not a special segment (see Figure 2), the key bit from the TLB entry and the key bit from the segment register are used to determine whether storage protection has been violated before access is allowed. A check is made on the access. In addition, the special segment bit of the segment register (see Figure 2)
If this number is a special segment, lock bit processing is performed before access is granted, as shown by . Now, the memory protection function will be explained next.
This function is to handle special segments. If access is allowed, the main memory is accessed and the reference bits REF (Figure 4) and change bits CHG linked to the page are accessed.
(Fig. 4) is updated. The operation of setting reference bits and change bits will be explained later. Furthermore, if two TLBs are compared and no match is found, the address translation logic circuit 14 indicates that an error has been made from the main memory page table.
An attempt will be made to reload the contents of the TLB.
Main memory page tables reside in real memory,
Logically, it consists of two parts: the hatch anchor table (HAT). this
The HAT allows all virtual addresses to be mapped to real addresses using a hashing function. Also, an inverse page table (IPT) is for indicating the virtual address associated with each real page frame (if any). The reverse page table is organized as an array of contents indexed by real page number, each of which includes an associated segment ID and virtual page index. By the way, determining a virtual address for a given real address is easy. This is because the IPT is indexed by real page number. On the other hand, in order to efficiently determine the real address for a given virtual address, it is necessary to map the virtual address to an anchor point and a chain of entry contents to resolve hash collisions. be. This will be well understood by those skilled in the art. Although the Hatch Anchor Table (HAT) is physically integrated into the Inverse Page Table (IPT) for reasons of hardware efficiency, it is logically separate from the IPT. As shown in FIG. 6, the hash function first converts the virtual address to an index of an entry in the HAT. And this
A HAT index specifies the first part of a chain of IPT entries (real pages) with the same index as the HAT index. Searching for a chain of IPT entries that match a virtual address will either yield the IPT index (i.e., the real address) corresponding to the desired virtual address, or the search will terminate with no match (if the page is (not mapped).
In this example, for each page of real memory,
One HAT entry corresponds to one IPT entry. The translation of a virtual address to a real address consists of the selected lower bits of the effective address and the segment
This is done by exclusive ORing with the bits of the ID. This "hatched" address is used to index into the HAT. The contents of the selected HAT also serve as a pointer to the starting point of the list of IPT entries to be searched for a given virtual address. The contents in the list of IPT entries to be searched are interconnected by pointers in each entry that specify the next IPT entry to be searched. There is a flag bit in the IPT entry that is used to indicate the end point of the search chain. Note that there may be multiple virtual address contents within one IPT chain to be searched. This is because the hashing function may generate the same HAT address for different valid addresses. Now, as mentioned earlier, for reasons of hardware efficiency, the HAT and IPT are combined into a single structure that is addressable by a single index structure. That is, for each page of real memory, this combined HAT and
There is one entry in the IPT. For example, 1MB of real storage organized as 2KB pages requires 512 entries,
512K bytes of real storage organized as 4K byte pages requires 128 entries.
The format of this combined HAT and IPT page entry is shown in FIG. 7th
A page entry in the figure represents one page of real memory. HAT/IPT has an area of 16 bytes for each page entry,
Start at an address that is a multiple of the size of the table. The first word of each page entry contains an address tag formed by combining the segment ID and the virtual page index.
The address tag is 29 bits for a 2K byte page, and 29 bits for a 4K byte page.
Note that it is 28 bits. That is, if a 4K byte sized page is used, a 28 bit long address tag is stored in bits 3-30 of the first word, with the second bit reserved. This first word includes two key bits for memory protection, which will be described later. The second word contains the HAT pointer, the IPT pointer, and a valid bit for each pointer called the empty bit (E) and the last bit (L). The uses of these fields will be described later. The third word contains a write protect bit, a lock bit, and a TID (transaction ID) for each special segment. The uses of these fields will also be described later. The 4th word is TLB (address translation buffer)
It is not used for reloading, but is reserved for possible future use. The base address of the HAT/IPT is a field in the translation control register (see Figure 12),
Used to calculate the start address of the main memory page table. This base address of the HAT/IPT is multiplied by the value in the table (shown immediately below) depending on the storage capacity and page size to obtain the value of the start address of the main memory page table. The table also shows the HAT/IPT size for each storage capacity and page size.

[Table] (E) Address generation for hash address table (HAT) As already mentioned, the HAT index is based on the exclusive logic between selected bits of the segment ID and multiple bits of the effective address. Calculated by taking the sum. The number of bits used at this time is chosen such that the index generated selects one of the n entries of the HAT/IPT. This hashing operation is shown in FIG. Also,
The bits used to generate the HAT index are listed in the table (shown immediately below). The storage address of the selected HAT entry is calculated by [HAT/IPT base address] + [HAT index]. The selected HAT entry is then accessed and the empty bit E (FIG. 6) is checked to detect whether the IPT search chain is empty. If the empty bit is “1”, it means that there is no page mapped to the given virtual address, so as explained later,
A “page fault” is reported. Also, if the empty bit is “0”, it means that an entry exists in the IPT search chain, so IPT
The entries inside are searched. The HAT pointer field of the selected HAT entry is then used as the pointer to the origin of the IPT search chain.

[Table] Shows do.
Previously accessed HAT pointers are IPT
used as a starting point index. And the storage address of the first IPT entry is
[HAT/IPT base address] + [HAT pointer]
Calculated by The first entry in the IPT is then accessed and its address tag is compared to the given virtual address. If the address tag and virtual address are equal, the real page allocated to that virtual address is located, allowing the faulting TLB entry to be reloaded. Also, if the address tag and the virtual address are not equal, the IPT
The IPT search continues by accessing the pointer. The value of that IPT pointer is
[HAT/IPT base address] + [HAT pointer]
Calculated by The IPT pointer is then accessed and the last bit L (FIG. 7) is checked to see if there are any more entries in the IPT search chain.
And if the final bit is “0”, this means there are other entries, so
The search process continues. Also, if the final bit is "1", it means that there is no IPT entry to be searched, and a "page fault" is reported. If there is an IPT entry to search, the address of the next IPT entry to search is
[HAT/IPT base address] + [IPT pointer]
Calculated by This address is used to access the next entry in the IPT search chain and the address tag contained in that selected entry is compared to the given virtual address. If the address tag and the virtual address are equal, the real page allocated to that virtual address is located and the folded TLB entry can be reloaded. Also, if the address tag and the virtual address are not equal, the search process continues by accessing the pointer to the next entry to search. The address of the pointer to the next entry is [HAT/
IPT base address] + [IPT pointer]. Next, this load (in Figure 7,
(word containing HAT pointer and IPT pointer)
is accessed and the final bit L (FIG. 7) is checked to detect if there are any more entries in the IPT search chain. If the final bit is "1", it means that there are no more IPT entries to check, and a "page fault" is reported. Also, if the final bit is “0”,
This means there are more IPT entries left, so the search process can continue. The IPT pointer at this point is used to access subsequent entries by executing the process described above;
This continues until a final bit indicates that either the address tag in the entry is equal to the given virtual address or no match is found and there are no more entries in the search chain. Here is an overview of the steps that must be performed to convert a virtual address to an index of an IPT entry (and its corresponding real address): Step (a): Select the lower 13 bits of the virtual page number. . These 13 bits are valid addresses 7 to 19 if 4K byte pages are used.
If 2K byte pages are used, it will occupy 8 to 20 bits of the effective address. Step (b): Next, 12 of the segment register specified by bits 0 to 3 of the effective address.
Select the bit content. A 13-bit field is formed by connecting a "0" bit to the left end of the 12 bits. Step (c): Exclusive OR the 13-bit fields obtained in step (a) and step (b) above to create a 13-bit hash anchor table number. Step (d): Shift the value obtained in step (c) 4 bits to the left. This allows the desired
This means that a byte offset of the starting point of the IPT entry that physically contains the HAT entry has been performed. Step (e): Calculate the address of the HAT/IPT entry. This calculation is performed by adding the result obtained in step (d) to the starting address of the IPT. If the IPT is bound to start on a preferred squared byte boundary, then instead of doing the "addition" above,
You can also perform an OR or combine two values. Step (f): Here, it is checked whether the IPT chain is empty. For that purpose, HAT/
Examine the "E" (empty) bit (see Figure 7) in the IPT entry. If E=1, it means that the IPT chain is empty (HAT pointer is invalid), and the search ends in failure. That is, virtual pages are not mapped. Step (g): If the IPT chain is not empty, from the addressed HAT/IPT entry
Select HAT pointer. This 13 bit
The value of the HAT pointer (see Figure 7) becomes the index of the first IPT entry in the chain of entries with the same hash value (see step (c)). Step (h): Move the IPT index value to the left by 4
Bit shift. This means that the byte offset of the starting point of the IPT entry whose match with the virtual address is to be checked has been performed. Step (j): Calculate the address of the IPT entry. This is done by adding the result obtained in step (h) to the starting address of the IPT. If the IPT is constrained to start on a suitable squared byte boundary, instead of doing the "addition" described above, one may perform a logical OR or combine the two values. Step (k): Compare to check for match with virtual address. i.e. in segment id
The value obtained by combining the virtual page number obtained from the IPT entry is compared with the value obtained by combining the virtual page number in the effective address with the contents of the segment register specified by the effective address. Step (l): If both match as a result of the comparison in step (k), the search ends successfully. The entry at this time corresponds to the desired virtual address, and its index number is equal to the requested real page number. Step (m): If the result of the comparison in step (k) is that they do not match, check whether it is the last in the chain. To do this, check the "L" (last) bit in the IPT entry. If L=1, indicating this is the last IPT entry in the chain, the search ends unsuccessfully. That is, virtual pages are not mapped. Step (n): If it is not the last chain, select the IPT pointer field from the IPT entry. This 13-bit value becomes the index of the next IPT entry to examine. Step (p): Return to step (h). Now, the significance of combining HAT and IPT into a single table structure is that it enables addressing using a single index structure. This will be better understood with reference to Figure 7A. That is, FIG. 7A represents the structure of a memory having seven representative page entries. Each page entry has the same structure as the single page entry shown in FIG. These 7 page entries are 7 pages of real memory: 10, 20,
Represents 30, 40, 50, 60 and 70. It can be assumed that there are hundreds to thousands of such pages in real memory. However, indexing and addressing of data such as HAT pointers and IPT pointers in selected page entries is done based on information stored in a single base address register 72. still,
This register 72 is equivalent to the HAT/IPT field, ie, the base address register, described below in connection with the translation control register of FIG. At this point, the present invention may be better understood by considering how real memory pages are located for individual virtual addresses using the memory organization of FIG. 7A. By the way, it should be noted that the functions and operations of the processing procedures that will be developed later in connection with FIG. 7A have already been explained in connection with FIGS. 6 and 7. Therefore, we will now provide a step-by-step explanation of how these functions are used to locate real page addresses within a memory structure. The virtual address is now hashed in the hashing function means 71 in the manner described above to create a hashed address. This basing address is supplied to table entry address calculation means 75. The table entry address calculation means 75 is for calculating the offset from the base address of the register 72 to a specific page entry containing the HAT pointer to be accessed. So, this
Assume that a HAT pointer is included in page entry 50. Then, the table entry address calculation means 75 accesses the page entry 50 via the pointer means 73. Then HAT on page entry 50
A pointer is fetched and applied via bus 74 to table entry address calculation means 75. Then, the table entry address calculation means 75 calculates an appropriate offset from the base address for accessing the specific page entry specified by the pointer on the page 50. Let us now assume that page entry 20 has been specified. This means that when a hash address is supplied from the hash function means 71, the first page of a group of virtual addresses (represented by address tags) generates the same hash address. This means that page 20 is page 20. Next, does this first page entry contain the sought virtual address (the address tag of the sought virtual address is compared with the address tag of the virtual address added to the hash function means 71)? It will be decided whether And if there is no match for this virtual address of page 20, then the IPT pointer in page entry 20 is used as. This is accomplished by sending the hashed pointer information via bus 74 to table entry address calculation means 75. That is, the table entry address calculation means that receives the hashed pointer information calculates the offset from the base address to the next connected page entry (corresponding to page entry 30 in FIG. 7A). A comparison is then made between the address tag in page entry 30 and the address tag of the added virtual address. And if they do not match, the IPT pointer in page entry 30 is used to access the next concatenated page entry, as described above.
In other words, the IPT pointer is used to concatenate the next page entry in which one of a group of virtual addresses with the same hash address is found.
This procedure continues, as previously described, until a match is found between the added virtual address and an address in the particular page being accessed, or else it is determined that no match exists. Therefore, let us assume that there is a match on page entry 30. Then the page
It becomes the real address of the virtual address with 30 added. The use of a combined HAT and IPT table in the present invention is shown in FIG. It can be seen from Figure 7A that significant hardware savings can be achieved compared to systems used. Further, since the memory structure of FIG. 7A uses a single association table, only one base address register and one table entry address calculation means are required. However, if this is not the case, as shown in Figure 6, the HAT and
If the IPT is separate, a separate base address register and table entry calculation means are required for each table. Also,
Separate pointer and fetch means are also required for each table. (E) TLB Reload If an IPT entry equal to the given virtual address is found for the address field, the faulted TLB entry is reloaded. This reload procedure consists of electing the most recently used TLB entry for the congruent class of virtual addresses in fault, and the selected entry for that given virtual address tag field, real page number. and loading key bits.
If this IPT entry is a special segment, as indicated by the special segment bit in the segment register (Figure 2), the write bit (W), transaction
ID (TID) and lock bits are also reloaded. Hardware is used to determine which TLB entry was most recently used in each congruence class. Since the congruence glass is determined by the lower bits of the virtual address, it is only necessary to determine which TLB is replacing the selected entry. The most previously referenced entry in a given congruence class is then
One of the TLBs is selected based on which TLB it has. Once the most recently used TLB entry for a given congruence class is determined, the selected TLB entry can be reloaded.
At this time, the address tag field and key bits are reloaded from the IPT entry stored in main memory. The address of this IPT entry was previously calculated in the IPT lookup process. Then, the search process calculated
Since the IPT index is equal to the real page number, this value is used to reload the real page number field in the TLB. If this value is a special segment as indicated by the special segment bit in the segment register, the transaction ID and lock bit are also reloaded. Furthermore, this transaction
The ID and lock bits are reloaded by accessing the third word (see Figure 7) in the selected IPT entry. (F) Storage Access Control The address translation mechanism of this embodiment includes two access control means. The first access control means is applied to non-special segments and provides read/write protection for each page of real storage. The second access control means applies exclusively to special segments and is used to support connected data. Note that these access control means are applied only to conversion type access. When a violation of the regulations is detected by one of the access control means, access to the storage device is stopped.
However, there are exceptions to this, which will be discussed later. (G) Memory protection processing Memory protection processing is applied only to non-special segments. That is, once the correspondence between real and virtual addresses is determined by the TLB, the requested access is verified to ensure proper access authority. This verification means makes it possible to mark each page with information such as no access, read only, read/write, etc. Access control is a function of a 1-bit protection key in the selected segment register, a 2-bit key in the TLB entry, and whether the access is a load or store. Access is controlled as shown in the following table:

[Table] If the access is not allowed, the address translation operation is terminated and a memory protection exception is reported to the CPU. (H) Lock Bit Processing Lock bit processing applies only to the special segment indicated by the special segment bit in the selected segment register. Lockbit processing allows the operating system to automatically monitor and journal changes to persistent variables, and lockbit processing also creates shadow pages to help maintain the database. Also perform other necessary processing. In addition, lockbits provide 128 or 128 or more pages of 2K or 4K byte resolution
Extends to 256-byte line memory protection.
In other words, a 2K byte page is given a resolution of 128 bytes, a 4K byte page is given a resolution of 256
The resolution in bytes is given. That is, the lock bits of an individual line are selected by the 21st to 24th valid bits for a 2K byte page, and by the 20th to 23rd valid bits for a 4K byte page. selected. This means that the access control is based on the selected TLB
The result of comparing the 1-bit write bit in the entry, the value of the lock bit of the selected line, the transaction ID in the TLB and the current transaction ID, and whether the access is in load or store operation mode. is a function of Access is then controlled like a table.

[Table] Data storage exceptions are used to flag violations of lockbit rules. Violation of this rule does not necessarily result in an error. This is because it merely indicates to the operating system that it should process the newly modified line. Now, each page of real memory is provided with reference bits and change bits. These bits are arranged outside the address translation mechanism of this embodiment, and the values of these bits are updated when necessary in response to accesses to real memory. A reference bit is set to "1" when the corresponding real system is accessed for reading or writing. Also, the changed bits are
It is set to "1" when the corresponding page is written. Reference bits and modified bits can be accessed by I/O read instructions (IOR) and write instructions (IOW) from the CPU. The reference bits and change bits corresponding to each real memory are stored in the I/O
I/O specified by base address register
The starting point is the address plus X'1000'. The I/O address of reference bits and modified bits for any page is given by the following formula: [I/O address] = [address specified by I/O base address register] + X'1001' + [ Page Number] Each I/O address includes reference bits and change bits corresponding to each page of real memory. The format of this reference bit R and change bit C is shown in FIG. That is, the data transferred to reference bits and modified bits upon access is defined as follows: Bits 0 to 29: Zero Bit 30: Reference bit. Set to "1" when the corresponding real page is accessed for a read or write operation. Bit 31: Change bit. Set to "1" when the corresponding real page is accessed for a write operation. Note that the reference bit and change bit are not initialized by hardware. These bits are initialized and cleared by system software IOW instructions. Since reference bits and changed bits can be set by executing a program to set or clear those bits, those bits must be set or cleared before reading data from the reference bits and changed bits. This does not necessarily mean that the same data that was written is read when the data is written. (J) Control Register Group A plurality of control registers are provided for setting the memory configuration, page table address, and I/O base address. These registers are initialized (loaded) by system software via I/O read (IOR) and I/O write (IOW) instructions from the CPU. The structure and format of each register is shown in FIGS. 9 through 18.3. These registers are only accessible in supervisor state. An I/O base address (FIG. 9) that specifies the I/O address of the 64K block is assigned to the address translation system. This I/
The value of the O base address is 65536 (X'10000') stored in the I/O base address register.
is equal to the value multiplied by . The format of the I/O base address register is as shown in FIG. The I/O base address register is defined as follows: Bits 0-23: Reserved Bits 24-31: I/O base address. This 8
The value of the bit sets which block of 64K byte I/O addresses within the I/O addresses known by the address translation system will be allocated to the address translation system. That is, these 8 bits are the most significant 8 bits. (J-1) RAM specification register The register shown in Figure 10 is the "RAM specification register." This RAM specification register is used to set the RAM size, RAM starting address, refresh rate, and whether parity check or error correction code (ECC) is used.
Note that the parity check and ECC are outside the scope of the present invention and will not be further explained here. The RAM specification register has the format shown in Figure 10 and is set as follows: Bits 0 to 10: Reserved Bits 11 to 19: Refresh speed. This 9
The bit sets the refresh cycle speed. The refresh cycle rate is equal to the value stored in bits 10-18 times the CPU clock frequency. Setting the value of bits 10 to 18 to zero disables the refresh operation. The refresh rate value determines the required memory refresh rate.
It can be calculated by dividing by the CPU clock frequency. For example, 2m for 128 lines
In a system with dynamic memory that requires refresh every s, the refresh interval for each row is 2ms ÷ 128 = 15.6μs.
It is. And the CPU clock cycle is 200ns
If so, the refresh rate count is
15.6μs/200ns, or 78(X'04E'). This value loads the refresh rate of X'04E'. Note that this refresh rate is initialized to X'01A' as part of the program operation sequence. Bits 20-27: RAM start address. This 8-bit field sets the starting address of the RAM for both translation and non-translation accesses. Bits 28-31: RAM size. This 4-bit field sets the size of the RAM currently allocated to the address translation system. (J-2) ROS specification register Here, ROS refers to Read Only Storage, that is, a read-only storage device. The abbreviation ROS is also used in Figure 1. Now, the ROS specification register is used to set the start address of ROS, the size of ROS, and whether or not parity is provided by ROS, and its format is shown in Figure 11. That's right. Note that ROS can be accessed in both conversion mode and non-conversion mode. The ROS specification register is set as follows: Bits 0-19: Reserved Bits 20-27: ROS start address. This 8-bit field allows for both conversion and non-translation accesses.
The starting address of ROS is set. Bits 28-31: ROS size. This 4-bit field sets the size of the ROS assigned to the address translation system. (J-3) Conversion control register The conversion control register (TCR) stores the size of each page (2K bytes or 4K bytes), the start address of the main memory page table (combination of HAT and IPT), and the next hardware address.
This is used to specify whether or not an interrupt occurs during TLB reloading, and whether or not parity is used on the reference array and modified array, and its format is as shown in FIG. The conversion control register is set as follows: Bits 0-20: Pending Bit 21 (Figure 12R): Interrupt enable on successful TLB reload. This bit is used to enable reporting of a successful TLB reload by the hard ear. When this bit R is set to "1", an exception response is issued due to successful reloading of the TLB by the hardware, and the TLB reload bit T in the storage exception register (see Figure 13 below) is set to "1". is set to Also, when this bit R (FIG. 12) is set to "0", the next reload by the hardware of an entry in the TLB will not be reported. The functionality of this bit can be used to measure TLB operation by software. Bit 22 (Figure 12P): Parity enable for reference array and modified array. This bit is used to indicate whether parity is used on the external reference and modification arrays. If this bit is set to ``1'', parity is being used on the reference array and the modified array. Also, if this bit is set to ``0'', parity is not used on the reference array and the modified array. Bit 23 (S in Figure 12): Page size.
The value “0” is used for 2K byte pages and the value “1” is used for 4K byte pages.
is used. Bits 24-31: HAT/IPT base address.
This 8-bit field is stored in main memory.
Used to specify the starting address of a HAT/IPT entry. The value stored in this field is multiplied by a constant determined by the real memory and its page size, and this value specifies the starting address of the HAT/IPT entry. For a 2KB page,
The base address is specified by bits 24-31 of this conversion control register, and in the case of a 4K byte page, the base address is specified by bits 25-31 of this register. Please refer to the table above for constant values for various values of storage size and page size. (J-4) Storage Exception Register The Storage Exception Register (SER) is used to report errors in the conversion process and system errors during storage accesses. That is, individual bits are provided to report each error condition detected by the conversion system. If multiple errors occur, each error is reported by setting the appropriate bit assigned to it. Note that the bit set by the previous error will not be reset by any subsequent error. This storage exception register (SER) is initialized to zero by the program operation sequence (POR). Once an exception is reported, the system software is responsible for clearing the SER after the exception is handled. The format of this storage exception register (SER) is as shown in FIG. Bits 0 to 21: Hold Bit 22 (T in Figure 13): TLB reload successful. This bit is set to ``1'' when the interrupt on successful entry of the TLB is successfully reloaded. Bit 23 (Figure 13R): Parity error between reference array and modified array. This bit is set to "1" when a parity error is detected in the reference array and the modified array. Bit 24 (Figure 13 W): Attempted ROS
writing to. This bit is set to "1" when a write is attempted to an address contained in the ROS address space. Bit 25 (Figure 13 I): IPT specification error.
This bit is set to "1" when an infinite loop is detected in the IPT search chain.
Infinite loops can occur when a system software error causes an incorrect IPT pointer value to be specified. If an infinite loop occurs in the IPC search chain, the IPT pointer will point to the previous entry in the IPT search chain. Bit 26 (Figure 13E): External device exception. This bit is set to “1” when an exception is caused by an external device.
is set to Bit 27 (M in Figure 13): Multiple exceptions. This bit is set to ``1'' when two or more exceptions (IPT specification error, page fault, storage protection, or data) occur before the exception indication is cleared in the storage exception register. This bit usually indicates that the system software failed to handle the exception. However, if the exception was caused by a load multiple (LM) or store multiple (STM) instruction, this bit may be set. This is because before a load or store multiple instruction terminates with an exception,
This is because it is considered that an attempt is made to load or store all registers specified by the instruction. Bit 28 (Figure 13F): Page fault. This bit is set to "1" when the translation operation is completed because the translation address corresponding to the virtual address is not included in the TLB entry or the main memory page table. Bit 29 (Figure 13 S): Designation. This bit allows two
Set to ``1'' when a translation operation is completed because a TLB entry was found. Bit 30 (Figure 13P): Memory protection. This bit is set to ``1'' when the conversion operation ends because the storage protection process for the non-special segment has determined that access to the storage is not allowed. Bit 31 (Figure 13D): Data. This bit is set to ``1'' when the conversion operation ends because it is determined that access to memory is not allowed by transaction ID/lock bit processing for the special segment.
is set to (J-5) Storage exception address register The storage exception address register (SEAR) is
It is used to store valid storage addresses. This valid storage address causes an exception to load and store requests from the CPU, and the exception is registered in the storage exception register (SER).
Reported by. Note that SEAR is not loaded for fetch instructions or exceptions caused by external devices. The format of this storage exception address register is
As shown in Figure 4. The storage exception address register is defined as follows: Bits 0-31: Storage exception address. This 32
A bit valid storage address will cause an exception to be reported by the storage exception register. If multiple errors occur (bit 27 of the storage exception register is set to "1"), the address stored in the storage exception address register is the address of the oldest exception. (J-6) Translated real address register The translated real address register (TRAR) is
It is used to store the real storage address determined by the real address arithmetic operation. This real address arithmetic function is used to determine whether a virtual address is currently mapped in real memory and, if so, to determine its corresponding real address. The real address calculation function will be described later. The format of the real address register to be converted is as shown in FIG. The translated real address register is defined as follows: Bit 0 (Figure 15I): Invalid bit. This bit is set to "1" when address translation fails and is set to "0" when address translation is successful. Bits 1-7: Zero. These 7-bit fields are always zero. Bits 8-31: Real memory address. If the address translation is successful, this 24-bit field contains the real memory address that maps to the given virtual address. This field is also set to zero if the address translation fails. (J-7) Transaction identification register Transaction identification register (TID)
contains 8-bit data for identifying the task currently set as the "owner" of the special bit. That is, if a segment is set as a special segment by a special bit in the selected segment register, the lock bit processing described above is applied to that memory access. Lock bit processing is a transaction
It uses the value contained in the ID and compares it against the transaction ID entry in the TLB to determine whether the storage access is allowed. Determine whether transaction identification access is allowed. The format of the transaction identification register is as shown in FIG. The transaction identification register is defined as follows: Bits 0-23: Pending. Bits 24-31: Transaction ID. This 8-bit value is the “owner” of the special program.
This is for specifying. (J-8) Segment Register There are 16 segment registers with the same format, and only one of them is shown here. segment register is segment
Consists of ID, special bits, and key bits.
The 12-bit segment ID specifies one of 4096 virtual storage segments, each 256 Mbytes in size. The special bit indicates that the segment in which this bit is set is a special segment and lock bit processing is applied to it. The key bits are intended to indicate the access privilege level for the currently executing task related to storage access within a given segment.
The segment register format is 17th.
As shown in the figure. The contents of each segment register are defined as follows: Bits 0-17: Reserved. Bits 18-29: Segment ID. This 12-bit value results in 4096
One of the virtual storage segments is specified. Bit 30 (S in Figure 17): Special bit. This bit is set to “1” for special segments and “0” for non-special segments.
is set to Bit 31 (Figure 17K): Key bit. This bit determines the level of access authority currently in effect for access within a given segment. The use of this bit for storage access control is discussed, for example, in connection with FIG. By the way, in the embodiment disclosed here, each of the two TLBs has 16 entries, and these entries provide the translation and control information necessary to translate a virtual address into a real address. It will be done. In addition, each TLB entry also contains information used for storage access control. Furthermore, since the contents of the TLB are automatically updated from the main memory page table by hardware, even if a TLB entry is written and then read, the same data that was written will not necessarily be read. moreover,
Changing a TLB entry destroys the correspondence between virtual addresses and real addresses, which can lead to unpredictable results. That is, access to the contents of the TLB should only be made for diagnostic purposes and only in non-translation mode. If you then write to a TLB entry in non-translation mode, disabling all other translation accesses, and then read it, you will read the same data that was written. (K) TLB entry Each TLB entry has 66 logical bits (excluding reserved bits), and the 66 bits consist of 25 bits for the address tag and 25 bits for the real page number.
13 bits, valid bit is 1 bit, key bit is 2 bits, write bit is 1 bit, transaction ID is 8 bits, lock bit is
It is 16 bits. Each TLB entry is partitioned into three fields, which are individually addressable. This TLB
The format of each field in the entry is
Figure 8. 1 to 18.3. First, let's call the field in Figure 18.1 the TLB address field. This TLB address tag field contains a segment ID and a virtual page index. The stored data is the upper 25 bits of the segment ID and virtual page index for a 2K byte page, and the upper 24 bits of the segment ID and virtual page index for a 4K byte page. The TLB address tag field is defined as follows: Bits 0-2: Reserved. Bits 3 to 27: Address tag. This field contains the segment for a 2KB page.
Contains the ID and the top 25 bits of the virtual page index. Note that for a 4K byte page, the address tag is [bits 3 to 26]. Bits 28-31: Hold. Next, let's call the field in Figure 18.2 the TLB actual page number field. This TLB real page number field stores a real page number, a valid bit (V), and a key bit (KEY). The real page number is the number assigned to the virtual address contained in the address tag field of the TLB entry. A valid bit (V) is a bit that indicates that a given TLB entry has valid information. Furthermore, a key bit (KEY) is used to indicate the necessary access authority for a given page. The real page number field is defined as follows: Bits 0-15: Reserved. Bits 16-28: Actual page number. This 13-bit field specifies one of 8192 real pages. If the actual page you use is
If there are fewer than 8129, only the lower bits need to be used to access the actual page being used. Bit 29 (Figure 18.2 V): Valid bit. This bit becomes "1" when the selected TLB entry has valid information, and becomes "0" if the TLB entry has invalid information. Bits 30-31 (Figure 18.2 KEY): Key bits. This 2-bit field sets access authority for each page. Next, let's call the field in Figure 18.3 the TID lock bit field. The TID lock bit field contains a write bit, a transaction ID, and a lock bit. If the TLB entry is for a special bit, the lock bit is assigned to the virtual address contained in the TLB's address tag field. The contents of the TID lock bit field are defined as follows: Bits 0-6: Hold. Bit 7 (Figure 18.3 W): Write bit. This bit sets access privileges for each page corresponding to the special segment. Bits 8-14: Transaction ID. This 8-bit field sets the task that currently owns the selected page within the special segment. The use of these bits during lock bit processing has already been discussed. Bits 15-31: Lock bits. This 16-bit field supports 2K bits that correspond to special bits.
Access privileges are set for each “line” within a byte page or 4K byte page.
One line is 128 for a 2KB page
bytes, or 256 bytes for a 4KB page. The use of these bits during lock bit processing has already been discussed. In the address translation mechanism of this embodiment, frequently requested translation functions are supported by hardware. This hardware has the ability to selectively invalidate TLB entries and perform a "real address load" function similar to that found in the IBM Systems/370 family. Additionally, when changes to virtual address mapping are made, system software must synchronize the contents of the TLB with the contents of the page table in main memory. Then, the entries in the TLB and the page frame table must be invalidated so that mapping information that has already been used will not be used during subsequent address translations. Now, regarding the above synchronization, the system of this embodiment has three functions to support synchronization of TLB entries with page tables in main memory. These features are
Can be used to invalidate all or selected TLB entries. These functions are also invoked by an I/O write instruction (IOW) directed to a particular I/O address within a 64-byte block of I/O addresses recognized by the system. Note that the allocation of addresses to each of these functions will be given to the system as necessary. (L) Various functions for TLB (L-1) Disabling the entire TLB The “Disabling all TLB” function
This invalidates the entry. As a result, the contents of the TLB are updated from the page table in the main memory corresponding to the next address translation. An I/O write instruction to the address associated with this function causes all TLB
The entry will be invalidated. Note that at this time, the data transferred by the I/O write command is not used. (L-2) Invalidating TLB entries in a specific segment The “Invalidating TLB entries in a specific segment” function invalidates all TLB entries related to a specific segment ID.
Use this segment ID. Subsequent address translation operations update the contents of the TLB from the page table in main memory. An I/O write instruction to an address associated with this function invalidates the TLB entry for a particular segment ID.
The data of bits 0 to 4 transferred by the I/O write command is the segment ID.
used to select. That is, all TLB entries including the selected segment ID are invalidated. The following address translations for valid addresses within the invalidated segment update the contents of the TLB from the page table in main memory. (L-3) Invalidating TLB entries for specific valid addresses The "Invalidating TLB entries for specific valid addresses" function invalidates TLB entries for specific valid addresses. The contents of the TLB are then updated from the page table in the main memory by performing address translation on a certain effective address within the page that includes the specific effective address. An I/O write instruction to an address associated with this function invalidates the TLB entry for a particular valid address.
At this time, the data of bits 0 to 31 transferred by the I/O write command is used as a valid address. The normal address translation process is applied by using the contents of the segment registers included in the address translation mechanism of this embodiment. (L-4) Real Address Arithmetic The “Real Address Arithmetic” function allows system software to determine (i) whether a given virtual address is currently mapped in real memory, and (ii) if so, which one. Used to determine whether a real address is assigned to a virtual address. If the virtual address is not mapped, use of the real address arithmetic function will cause a page fault. This page fault information may be important to system routines operating with interrupts disabled. This is because most I/O operations are performed using real storage addresses, and therefore system I/O routines also require the result of converting virtual addresses to real addresses. A real address arithmetic function is called by an I/O write instruction to an address associated with this function. Bits 0--of the data transferred by the I/O data write command
31 is used as a valid address. This effective address will be used for the normal translation process, except when the address translation result is loaded into the translated real address register (FIG. 15) rather than a storage access.
As previously mentioned, the translated real address register contains a bit to indicate whether the address translation was successful and the corresponding real storage address if the address translation was successful. Normal memory protection processing and lock bit processing are executed when there is an indication of successful address translation. The result obtained by the real address arithmetic function is read by the I/O read instruction of the real address register to be translated. A block of I/O addresses consisting of 64K bytes is allocated to the address translation mechanism. This 64K byte block starts at the I/O address specified by the I/O base address register. The I/O base address is
It is set on a 64K byte boundary. Table 4
The I/O address assignments listed in
This is the displacement within the specified 64K byte block. At this time, the absolute I/O address is equal to the I/O base address plus the displacement.

【table】

Claims (1)

[Scope of Claims] 1. A hierarchical memory having a plurality of page frames; a central processing unit for supplying virtual addresses; a hashing means for hashing a given virtual address to create a hashed address; and a hashing means for hashing a given virtual address to create a hashed address; A first table that associates virtual addresses with real addresses, and each hash address,
a second table for binding to a scheduled virtual address of a group of concatenated virtual addresses that are different from each other, and for creating the combined hash address when each of the virtual addresses of the group is hashed; a binding table in said hierarchical memory, combining said virtual addresses in said binding table; searching means for searching for a location of a given virtual address within said group of concatenated virtual addresses in said binding table; A virtual storage device comprising: access means for accessing a real storage address corresponding to the found virtual address from the first table in response to the position of the found virtual address. 2. The virtual converter according to claim 1, wherein the conversion means includes means for storing a base address that is a combination of the base address of the first table and the base address of the second table. Storage device.