JPS60123947A - Virtual memory - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

DETAILED DESCRIPTION OF THE INVENTION Field of the Invention This invention relates generally to computer memory systems, and more particularly to virtual memory systems. More particularly, 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 is stored somewhere in the system (i.e., cache/main memory/direct access storage (DASD)).
Attempts are frequently made to access data or code residing at some level in the storage hierarchy of a computer, or at a node in a distributed 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? Its location will determine what type of address (eg, a 24-bit main memory address, a sector address of a disk track, or a node address of a network) 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 line protocol for network access) is required to perform the access. etc.) should be used.

a-2) Is this data shared with other executable programs? If so, access cannot proceed unless some type of lock is released. And the changes that this program is trying to make to the data,
If no other program knows at this point,
A store command must be issued to a private address.

a-3) Should this data be recoverable? If so, some 1' 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.

Then, the following results will occur: b-1) If this program must be general-purpose.

Otherwise, access would be extremely slow even for the most frequently encountered "simple and safe" requests, ie, for private, non-recoverable data in main memory.

b-2) If the 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, voluminous, 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 uniformly distributed with an address size of 16-32 bits (typically for temporary computations). Addressable. These architectures can be converted to appropriate addresses (1ook-asi
de) When implemented in hardware, the vast majority of those addresses are executed at cache or main memory speeds.

And only when this address translation hardware fails (which happens less than 1 time out of 100) does the system go to the trouble of accessing the relocatable table structure. Additionally, when that relocatable table structure fails (i.e.
Only when the data is not in main memory does the system incur the overhead of page faults. Thus, in the system described above, penalties are only paid when they are actually needed, which would be the goal of a good architecture.

c-2) When data is to persist beyond the execution capabilities of this program, modern systems require an explicit request for an ``access method'' to be performed by the software instead of load/store/branch instructions. These access methods generally support data organized into fixed volumes called "records and files."

The "instructions" for access are commonly called "read/write" or "get/put."

This data is neither shared nor recoverable. This data can actually reside in main memory (somewhere in a buffer area). However, on every access, the program reads/@:writes these explicit parameters.
You must not have to pay the extra burden of demands. Such an access method, when properly configured, allows for less complex programs that can be used not only in rudimentary systems but also in more general systems.

However, the execution speed of these accesses is uniformly
storage scheme, and the accessed data must be organized into a suitable aggregate structure.

c-3) When data should be shared or recovered,
Modern systems require explicit requests to the database subsystem implemented by software. The speed of these accesses is generally slower than that of the access methods described above. This is not only due to the additional functionality of locking and journal management, but also because the types of data aggregation these subsystems support (e.g., data relationships, hierarchies, etc.) are themselves fairly complex. be.

That is, it may indeed be possible to structure the data more easily in buffers in main memory, but one would have to pay an overhead for each access request.

Additionally, systems are provided that provide a means called "checkpointing" to recover non-persistent data. A programmer attempting to create a recoverable application must then deal with three different functions: checkpointing computational data, explicit backups of files, and "commit" commands to the database.

The IBM System/38 is more advanced than other systems in providing at least a uniform address structure for all data. However, that system also achieves this at the cost of making all addresses larger, reducing access, increasing the storage and hardware required to implement the architecture, and... It still does not provide a uniform means for data sharing and recovery.

Additionally, various techniques have been developed in the past for allowing a single memory to be shared by multiple computer programs, whether executed by essentially a single unit or by multiple processing units. Are known. Sharing memory among multiple programs in this way requires an extremely large amount of family memory.

This required capacity is often much larger than the actual capacity of the memory. For example, if system 11 uses a 32-bit addressing scheme, 2 of 3
The virtual storage capacity of squared bytes becomes usable. 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 are not actual locations in main memory. Therefore, virtual segments and pages are typically randomly located throughout main memory and are swapped in and 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 characteristics are:

This means that a particular virtual address must be logically mapped to a memory location in a table containing the virtual address's corresponding real address (if any).

Functionally, 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 the lower bits include a specific virtual bit. If a specific virtual bit is included, a search is made to find out what 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, then each frame has a table of 16 pages and an entry specifying the particular set of individual page tables.
There will be a separate frame table.

However, these are thin descriptions, and there are many different ways of configuring address translation using page tables, starting from virtual addresses created by the CPU, etc. I want you to understand. In addition, in the description of preferred embodiments of the present invention to be described later,
A detailed description will be given of the hash address table (HAT) and the reverse page table (PT).

Now, when performing real address translation, a unique entry in the page/frame table is created, regardless of the details of the overall system configuration or the use of page tables.
The page table is accessed by using the current virtual address as an argument. 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 a desired real page address portion of a virtual address has been translated, that by-by-one portion is concatenated to a 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 Translation table (I) LAT) or address translation table (Translation Look
-aside Table (TLB)) is maintained in a specific set of fast-accessible tables or fast memory. Note that the above DLAT or TLB is also used in the present invention. These tables or buffers are
Generally, it is a particularly fast or fast-accessible memory, and can be accessed much faster than the page frame table described above. This therefore saves a great deal 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 that after the first access to a particular virtual page, there are numerous accesses to that same virtual page during the execution of a given program. It is affirmed based on the fact that Additionally, as mentioned above, subsequent accesses are made to different lines and bytes within a page, but the conversion from a virtual page to a real page is dependent on which lines and bytes are addressed. Regardless of the page, the page is the same.

That is, the use of TLBs reduces the translation circuitry that must be performed (in the page frame table), thus providing a significant benefit to the overall operation of the virtual memory system.

As previously mentioned, virtual memory systems have been known in computer technology for many years. It is also well known that a virtual address must be translated into a real address via some kind of location means or address translation means which must ensure that the virtual address can be translated into a real address.

Therefore, it is impossible to restore 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 is also useful for the present invention. , which the inventors believe is the closest technology known.

First, U.S. Patent No. 382,832 to Berglund et al.
No. 7 describes a storage control technique for expanding memory by adding the 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, Ilo (input/output) mode, etc. This patent relates to a memory expansion system that incorporates appropriate address translation hardware.

Next, 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 SIGPLANMOTI published April 1982
CES, Vo 1.17. “The
801 Minicomputer”
The paper by geRadin gives a general description of an experimental convenience store. The computers are those whose operating characteristics depend to a considerable extent on very high speed memory subsystems for which relocation mechanisms have specific uses.

US Pat. No. 4,050,094 to Bourke et al. discloses a memory organization with an address relocation translator having a stack segmentation register. The unique segmentation registers disclosed in this patent are utilized to store allocated real addresses of physical blocks in main memory, rather than the extended virtual addresses utilized in the present invention.

U.S. Pat. No. 4,251,860 to Mitchell et al.
A memory address system with a virtual address device for realizing a large-sized virtual address memory is disclosed. This patent describes dividing a virtual access into a segment part and an offset part. But with that segment part.

The nine segment registers connected to it are used in the traditional way of dividing the address.
The operating state is completely different from the address translation scheme of the present invention.

U.S. Patent No. 4,037,215 to nirny et al.
No. 4,050,094 discloses a system very similar to that of the above-mentioned US Pat. No. 4,050,094. That is, in that system, a column of segmentation registers is used to specify a particular block of real memory. The patent further teaches the use of "read-only" valid bits connected to certain segmentation registers. But these bits are
There is little resemblance to the special purpose lock bits provided in the hardware of the glue location mechanism of this invention. No. 4,077,059 to Cords et al. discloses a hierarchical memory system with special controls to facilitate journaling and copyback. This patent describes multiple dual memories,
Therein, the current version of the data is maintained in one of the dual memories, and changes in the data are posted to the other of the dual memories, thereby facilitating subsequent journaling and copyback operations. The hardware and control means of this patent also bear little resemblance to the Rockbit system of the present invention.

No. 4,064,948 to No. 11ogan et al. discloses an address translation system. This system has means with a counter, its 11offma
n et al. U.S. Pat. No. 4,218,743 is IBM Systems/
This is one example of several features W1° that have been restored in connection with the 38-point location architecture. This patent describes a simplification of how ■/○ handles addressing operations in virtual memory computer systems. Other patents related to virtual memory systems include U.S. Patent No. 4,170,039.
No. 4251860, No. 4215402, etc.

U.S. Pat. No. 4,020,466 to Corde et al. also discloses a memory system that incorporates special measures to simplify journaling and copy pack 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 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.

Additionally, U.S. Pat. No. 4,215,402 is cited as an example of using various hash schemes to access the virtual memory translation mechanism.6 [Problem to be Solved by the Invention] The purpose of the present invention is to: Reduce the amount of hardware required to support translation operations from virtual memory addresses to real memory addresses by using a table that combines a hash address table and a reverse page table in a virtual storage device. There is a particular thing.

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 hash addresses formed from virtual addresses. The virtual address in the harasser response is then indexed for further access to the page table.

That is, the page table includes a virtual memory address that individually corresponds to each real memory address. The invention provides means for hashing a selected virtual address to create a hash address;
It provides a joined table. 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 planned initial virtual address consists 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 Conversion Structure FIG. 1 is a schematic block diagram of a virtual address-real address conversion mechanism according to an embodiment of the present invention. This conversion mechanism has a maximum of 1
It includes the logic circuitry necessary to interface with a 6MB storage device. 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 the end circuit 12 (CFE) to the common freon 1,
It consists of 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 from the storage channel to the address translation logic circuit 14 and the storage control logic circuit 16. All information data passing back and forth via the storage channel is transferred to this common front end circuit 12.
will be processed. 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, the address translation logic circuit 14 includes address translation buffers (T
LB). Furthermore, the address translation logic circuit 14
The TLB is retrieved from the main memory page table on demand.
Logic circuitry is provided to automatically reload the input terminals of the. Storage control logic circuit 16 provides an interface from address translation logic circuit 14 to a storage device. When a dynamic memory device is used, refresh control of the dynamic memory is also performed by the memory control logic circuit 16.

It should be noted that this invention is primarily concerned with the close structural combination and functional operation of well-known computer circuits, devices, and functional units; The problem lies not in the detailed structure of the structure. 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 I am illustrating this. 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 quite obvious to a person skilled in the art. This is because I think there will be. Additionally, various portions of these systems may be appropriately emphasized or functionally described to particularly emphasize pertinent 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 be sufficient to 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 very 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 is determined by the value of the translation mode pit (T bit) on the CPU storage channel (C8C). controlled by Each device that makes some request on the C8C will control the value of the conversion mode pit for each request. This conversion mode pit is taken from an appropriate area of a 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 I10 device. If the T bit is "1", the storage address (check instruction, data load, data store) is sent to the address conversion logic circuit 14. Also, T bit is i
If t Otz, 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 14.

However, reference and modification recording is valid for all storage requests regardless of whether the storage request is sent to address translation logic 14.

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 supports in the preferred embodiment disclosed herein: a) multiple independent virtual address spaces b) 4 Gbyte address space C) on-demand paging d) 2048 bytes or 4096 byte pages e) Memory protection mechanism f) Shared segment for instructions and data g) Journaling and locking of 12'8 byte lines h) Up to 16 Gbytes of real memory addressability i) References to each real page and change bit j) Load real address, invalidate address translation buffer (TLB) input,
The hardware backup storage for storage of exception addresses and exception addresses is treated as if mapped onto a single 40-bit address space consisting of 4096 segments of 256 Mbytes each. That is, a 32-bit address received from the CPU storage channel (C8C) is converted into a 40-bit address ("long") using the four highest bits 1- to select one of the 16 segment registers. virtual address”). This is the one that the selected segment register has.
This is a concatenation of the 2-bit content and the remaining 28 bits after removing the upper 4 bits from the 32 bits received from SO8. 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, only 4 GB of storage
That is, only 16 segments with a capacity of 256 Mbytes, which are designated as 16 segment registers, can be addressed once. This fact allows the operating system to create multiple independent virtual address spaces by loading appropriate values into the segment registers. According to this scheme, in a marginal case, it would be possible to create 256 completely independent 4 GB address spaces.

However, it is likely that some segments (such as core code) will be shared across multiple address spaces.

A storage protection mechanism similar to the IBM System 370 storage protection mechanism is also provided on a 2K or 4 byte page substrate. Memory protection and fetch protection are each 256
It is supported by protection keys (equivalent to the keys in the program status word of the IBM system 370) that are specified independently in M-byte segments.

Additionally, the persistent storage class is supported by a set of "lock bits" associated with each virtual page. This lockpit effectively extends the granularity of storage protection to "lines" of storage (2.128 bytes per page, or 4.256 bytes per page);
Allows the operating system to detect changes to retained variables and automatically journal those changes. Note that the protected storage class used here means storage that resides on disk file storage.

(B) Definitions of 4 terms used in this embodiment The following terms will be used throughout the explanation that follows, and will be defined here in advance to simplify the explanation.

Byte Index: A number ranging from 0 to 2047 for a 2-byte page and from 0 to 4095 for a 4-byte page, which is the number of bytes within a page or page frame. It is used to identify.

This byte index is taken from the lower 11 bits of the effective address in the case of a 2-byte page, and from the lower 12 bits of the effective address in the case of a 4-byte page.

Jutoris Σ: One bit individually associated with each page frame, and whenever the next memory reference (write only) is made to that page frame, the modified bit is Set to II.

Effective Address: A 32-bit storage channel address generated by a device on the storage channel. This effective address is used by the host CPU in a fetch instruction,
It may also be an address output as a data load or a data address.

It may also be an address generated by an I10 device on the storage channel, such as a DMA (Direct Memory Access) address.

Line = 128-bit portion of a page on a 128-byte boundary. These 128 bits are lock bits (described later)
is the number of memories controlled by .

1-: One bit of a set of 16 bits connected to each page of the retention storage segment. Each lock pit is connected to one line of storage. Then, depending on the value of the 1 to run sequence (transaction identification signal), the write bit, and the lock pit on a certain line, it is determined whether to accept or deny the storage access request within the protected storage segment.

Page: A storage area with a capacity of 2048 bytes on a 2048-byte boundary, or 4 on a 4096-byte boundary
This is a storage area with a capacity of 096 bytes. "Page" actually refers to virtual memory, and "page frame" refers to real memory. However, the term "page" is conventionally used to refer to both virtual and real memory.

A storage area with a capacity of 2048 bytes on a boundary of 2048 bytes, or a storage area with a capacity of 4096 bytes on a boundary of 4096 bytes. The page exists in a page frame or on external storage (for example, a disk).

Page table: This is the content in main memory that combines 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 may be referred to as HAT/IPT hereinafter.

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 program status word key, except that it is provided for each segment individually rather than for all addressable memory as a whole.

Lost address: is the result obtained by the translation operation,
The lower 11 (or 12) bits of the effective address are concatenated with the 10 to 13 bits of the real page index (described later).

Page index 20~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 as little as 10 bits, which would limit the maximum amount of real storage to be supported to two byte pages of 2 Mbytes.

1 and Σ: One bit connected to each page frame. This reference bit is set to III I 11 whenever the next storage reference signal (read or write) is issued in a frame.

Segment ID: A number in the range 0 to 4095 (12 bits) for identifying a virtual storage segment of 256 MB by 1. The segment ID concatenated with the virtual page index individually specifies a page 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 associated with a unique page. This key is IBM System 37
It is similar in function to the storage keys linked to each memory page of 0.

TLB: Address translation buffer (Transla
tionLook-aside Buffer). This TLB is hardware with virtual-to-real mapping. Note that in some implementations, the TLB may include only a portion of this mapping at any given time. In addition to the mapping, the TLB may contain other information associated with the TLB, such as translation identification signals, storage keys, lock bits, and the like.

Transaction ID: A number in the range 0 to 255 (8 bits) for identifying the "owner" of the set of lock bits currently coded in the TLB.

Virtual Address: A 40-bit address formed by combining the segment ID and the lower 28 bits of the effective address to the lower 28 bits 1 of the address translation mechanism.

Idea page index = 2 to 0 for byte page
A number ranging from ~131,072 (17 bits), or from ~65,536 (16 bits) for a 4 byte page, to identify a page within a virtual memory segment. . The virtual page index will occupy 4 to 20 bits of the effective address when the range is 17 bits, and 4 to 19 bits of the effective address when the range is 16 bits.

(C) Hardware for Address Translation Machine We will 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 the TLB configuration are implementation dependent. At this time,
Two implementations are possible. That is, segment I
a content addressable memory (CAM) addressed by D;
It is a virtual page index with one content per real storage frame. The CAM index is then considered to be equal to the real page index. It is also considered that the associated set of TLBs are addressed by some lower bits of the virtual page index. Additionally, the real page index will be included within some field of the TLB content.

The contents of each TLB are then read by the CPU using the l0R (input/output read) instruction or l0W (input/output write) instruction.
can be read and written individually. The contents of the TLB include the following fields: First, the 32-bit effective address input (from the CPU or I10 device) is expanded to 40 bits by concatenating the segment identification address to this effective address. This virtual address is then transported to translation hardware and translated to an equivalent real address. Well then,
The process by which a virtual address is converted into a real address will be specifically shown below.

(D) Address/conversion operation The highest four bits of the input valid atris are given to the segment table as an index and used to select one of the 16 segments 1-. Referring now to FIG. 2, the 16 safety members 1- are sequentially allocated with entry numbers O to 15. As shown in the figure, a 12-bit segment (segment identification bit), 1 segment special bit, and 1 key bit are obtained from the selected segment register. Special segment bits and key pits are used for access verification as described below.

Next, referring to Figure 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, 2 contains the lower 11 bits for the page, and 4
For pages, the lower 12 bits are used as the byte address (byte index) for the selected real page. The remaining 29 bits (2 if there are 4 pages)
8 bits) is 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. Also, hardware is used to automatically update the contents of TL,B from the main memory page table when a new virtual address is brought into the TLB for translation. Note that the format of each TLB is shown in FIG.

The system in Figure 4 uses two TLBs, each TLB
The LB has 16 entries (contents), ie 16 congruence classes and a set of associative bidirectionalities.

The lower 4 bits of the virtual page index are both TLBs.
used to address in parallel. The address tag entry (indicated as "tough" in Figure 4) in each TLB contains the remaining bits of the virtual page index (25 bits if page 2, 24 bits 1 if page 4).
~) and the combined segment 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 ■ 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 (indicated as "RP N" in Figure 4.5) in the selected TLB entry is
Contains the number of the real page in main memory that maps to the given virtual address. If this number is not a special segment (see Figure 2), before access is granted,
A check is made on the access for a protection violation using the key bit from the TLB entry and the key pit from the segment register. Also, if this number is a special segment, as indicated by the special segment bit in the segment register (see FIG. 2), lock bit processing is performed before access is granted.

Now, the memory protection function will be explained next. This function is to handle special segments.

If access is permitted, the main memory is accessed and the reference bit REF connected to the page is accessed.
(Fig. 4) and change pins 1 to CHG (Fig. 4) are updated. The setting operation of reference pin 1- and change pin 1- will be explained later.

Also, if the two TLBs are compared and no match is found between them, address translation logic 14 will attempt to reload the contents of the erroneous TLB from the main memory page table. The main memory page table resides in real memory, and logically it is called the hash anchor table (H
It consists of two parts: AT). This HAT allows all virtual addresses to be mapped to real addresses by means of 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 has an associated page number.
) and a 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, to efficiently determine the real address for a given virtual address, hash collisions (Collisj, on
), it is necessary to map the virtual address to the chain of anchor points and entry contents. This will be well understood by those skilled in the art.

Although the hash anchor table (HAT) is physically incorporated into the inverse page table (IPT) for reasons of hardware efficiency, it is logically integrated into the IPT.
Separated from PT.

As shown in FIG. 6, the hash function first converts the virtual address to an index of an entry in the HAT. And this HAT index is
Specifies the first part of the IPT entry (real page) chain with the same index as index. IPT corresponding to that desired virtual address by searching for a chain of IPT entries that match the virtual address.
It will either result in an intex (ie, a real address) or the search will end with no matches (no pages mapped). In addition, in this embodiment, HAT is applied to each page of real memory.
One entry corresponds to each entry of IPT.

Conversion of a virtual address to a real address is performed by exclusive ORing selected lower bits of the effective address with bits of the segment ID. This "hashed" address is used to index into the HAT. Also, the contents of the selected HAT are the IPT to be searched for a given virtual address.
Points to the start of the list of entries. 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 engine that is used to indicate the end of the search chain. Note that there may be multiple virtual address contents within one IPT chain to be searched. I mean,
This is because the hash function may generate the same HAT address for a plurality of different valid addresses.

Now, as previously mentioned, for reasons of hardware efficiency, the HAT and IPT are combined into a single structure addressable by a single index structure.

That is, there is one entry in the combined HAT and IPT corresponding to each page of real memory. For example, 1 Mbyte of real storage organized as 2 byte pages requires 512 entries, and 512 bytes of real storage organized as 4 byte pages requires 128 entries. . This combined HA
The format of the T and IPT page entries is shown in FIG. The page entry in FIG. 7 occupies one page of real memory.

The HAT/IPT has an area of 16 bytes for each page entry, starting at an address that is a multiple of the table size.

The first word of each Pehejetonri contains an address tag formed by combining the segment ID and the virtual page index. Note that the address tag is 29 bits for a 2 byte page and 28 bits for a 4 byte page. That is, if a 4 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 a HAT pointer, an 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.
D) is included. The uses of these fields will also be described later.

The fourth word is not used for reloading the TLB (Address Translation Buffer) and is reserved for possible future use.

The base address of the HAT/IPT is the translation control register (
(see FIG. 12) and is 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 corresponding to each storage capacity and page size.

Table I: HAT/IPT Base Address Multiplier Value (E) HAT It is calculated by taking the exclusive OR with multiple pins.The number of bits used at this time is such that the generated index selects one of the n entries of HA T/IPT. This hash operation is illustrated in Figure 6. The bits used to generate the HAT index are also listed in Table 1 (shown immediately below). The storage address of [HAT/IPT base address co+[HAT
Calculated by indexco.

The selected H AT 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 111'', it means that there is no page mapped to the given virtual address, so a ``page fall 1-'''' is reported as described below. If it is ++, there is an entry in the iPT search chain.This means that the IPT
The entries inside are searched. Then the selected HAT
The entry's HAT pointer field is used as a pointer to the origin of the IPT search chain.

Table n: HAT/IPT index generation source field *The display n:m (n and m are integers) in Table 2 indicates the field 1 between the n-th bit and the m-th bit.

The previously accessed H AT pointer is used as the origin index into the IPT. And the first I
The memory address at the end of Pl'En1 is [HA Go/
I P l'' base 1mA14 and calculated by l + [HAT pointer].

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 search continues by accessing the IPT pointer.

The value of the IPT pointer is calculated by [HAT/IPT base] + [HAT pointer]. The II)T pointer is then accessed and the final pins 1-L (FIG. 7) are checked to see if there are any more entries in the IPT search chain. And if the last bit is "0", this means that there are other En1 helicopters, so the search process continues. Also, if the final pitch is 1-
If "1" means that there is no IPT entry to be searched, a "page fault" is reported.

If there is an IPT entry to be searched, what is the address of the next IPT entry to search for?

[HAT/IPT Base Address Base Address Calculated by Cointaco. This address is used to access the next entry in the IPT search chain,
The address tag contained in the selected entry is compared to the given virtual address. If the access tag and the virtual address are equal, the real page allocated to the virtual address is located, and the TLB entry in the folded state 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 address to search. The address of the pointer to the next entry is [H
AT/IPT base address] + [IPT pointer]. Next, this word (in Figure 7, HA
The word containing the T pointer and the IPT pointer) is accessed, and the last bit L (the 7th word) is accessed to detect whether there are any more entries in the IPT-search chain.
The check shown in Figure) is performed. And if the final pitch I
If - is "1", it means that there is no more IPT engine to check, so 6 pages fall 1-" is reported. Also, if the last bit is II Q II, other Since there are still IPT entries left in the IPT entry, the search process continues.
The PT pointer is used to access a subsequent entry by executing the process described above, which means that II) if the address tag in the entry points to a given virtual The search continues until the last bit indicates that there are no more entries in the search chain.

Let us now outline the steps to be performed in order 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 occupy valid 71 to 7 to 19 bits of the response if a by 1-page is used for 4.
If a byte page is used for 2, it will occupy 8 to 20 bits of effective address.

Step b) Second, select the contents of the 12 bits of the segment register specified by bits 0-3 of the effective address. By combining the "OI+ bit" with the left end of the 12 bits, a 13-bit field is formed.

Step c) 2 Exclusively OR the 13-bit fields obtained in steps a) and b) above to create a hash anchor table number of 13 bits 1 to 1.

Step d) Shift the value obtained in Step C) to the left by 4 points. This allows the desired II A T
This means that the byte offset of the starting point of the IPT entry that physically includes the en-1 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 constrained to start on the preferred squared byte boundary, then instead of doing the -] double "add", we may do a logical OR or combine the two values.

Step f): Here, a check is made whether the IPT chain is empty. For this, HAT/11) 1lET+ (empty) bit in U'en1- (see Figure 7)
Find out. If E=1, the IPT chain is empty (HΔT
(pointer is invalid), the search was unsuccessful. That is, virtual pages are not mapped.

Step g): If the IPT chain is not empty, select a HAT pointer from the addressed HAT/IPT entry. This 13-bit HAT pointer (7th
The value of (see figure) 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 4 pips to the left.
- shift. This means that the byte offset of the starting point of the IPT entry to be checked for coincidence with the virtual address has been performed.

Step j): Calculate the address of the Ipr entry.

This is done by adding the result obtained in step h) to the starting address of the IPT. If I
If PT 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): Perform a comparison to check for a match with the virtual address. That is, the value obtained by combining the segment ID with the virtual page number obtained from the ■PT entry is compared with the value obtained by combining the contents of the segment register specified by the effective address with the virtual page number in the effective address.

Step Q): If the result of the comparison in step k) is a match, the search ends successfully. The entry then corresponds to the desired virtual address, and its index number is equal to the requested real page number.

Step m): If the results of the comparison in step k) do not match, check whether it is the last in the chain. For that, I in the IPT entry
Examine the ILI+ (last) bit. 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 not the final chain, IPT
Select the IPT pointer field from En1.

This 13-bit value is the next IP address to be examined.
It becomes an index of ~ri.

Return to step p) and step h).

Now, the significance of combining the HAT and IPT into a single table structure is that it allows addressing through a single index structure. This will be better understood with reference to Figure 7A. That is, FIG. 7A shows 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 seven page entries correspond to seven pages of real memory: 10.20.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 a selected page en 1 hemisphere is based on information stored in a single base address register 72. Furthermore, 'this register 72
is H, which will be described later in connection with the conversion control register in FIG.
It is equivalent to the AT/IPT field, ie, the base address register.

At this point, using the memory configuration of Figure 7A, we can see how real memory pages are located for individual virtual addresses.
1. The present invention may be better understood if we consider how it is done. 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. 7Δ have already been explained in connection with FIG. 6.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 Pansure 1z reply is table entry address i! The signal is supplied to the IW means 75. The table en 1-read address calculation means 75 is
HA to be accessed from the base address of register 72
This is to calculate the offset to a specific page end including the T pointer.
Assume that the '1' pointer is included in page entry 50. Then, the table entry address calculation means 75 reads the page entry 50 via the pointer means 73.
will be accessed. next.

The HAT pointer on page entry 50 is fetched and applied via bus 74 to table entry 1 - rear address calculation means 75 . Then, the table entry address calculation means 75 calculates an appropriate offset for accessing the specific page entry specified by the pointer on the page 50 from the base address. here,
Assume that page entry 20 is specified. This means that when a hash address is supplied from the hash function means 71, the first page among a group of virtual addresses (represented by address tags) that generates the same hash address is a page. It means that it is 20.

Next, does this first page entry contain a claimed virtual address (the address tag of the claimed virtual address is compared with the address tag of the virtual address added to the hash function means 71)? What happens is judged. Then, if there is no match for this virtual address of page 2o, then the JP in page entry 2o is
A T pointer is used as a basis. This is accomplished by sending the hashed pointer information via bus 74 to full entry address calculation means 75. That is, the table entry 1-readdress calculation means that received the hashed pointer information calculates the address from the base address to the next connected page entry 1 (7th A).
In the figure, offset I~ is calculated up to page en l-I 730 (which corresponds to it in the figure).

Next, a comparison is made between the address tag in page entry 2o and the address tag of the added virtual 71-res. If these do not match, Page En1-
The IPT pointer in file 3o is used to access the next concatenated page entry, as previously described. In other words, the IPT pointer is used to concatenate the next page entry in which one of a group of virtual addresses sharing 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. So, let's assume that there is a match on page entry 30. Then, the virtual address becomes the real address to which page 30 is added.

Although the use of a combined HAT and IPT table in the present invention is shown in FIG.
It can be seen from FIG. 7A that significant hardware savings can be achieved compared to systems using IPT and IPT. Furthermore, since the memory structure of FIG. 7A uses a single association table, only one base address register and one table en 1-read address calculation means are required. However, if this is not the case and the HAT and IPT are separated as shown in FIG. 6, a separate base address register and table entry calculation means are required for each table. Separate pointers and fetch means are also required for each table.

(E) TLB Load If an IPT entry equal to the given virtual address is found for the address tag field, fall 1.
- State TLB entries are rerotated. This reload procedure consists of selecting the most recently used TLB entry for a congruent class of faulted virtual addresses and selecting the selected entry 1-1 for that given virtual address tag field. This consists of loading the real page number and the keypad I-. If this IPT en 1 is the special segment register 1 in the segment register (special segment 1 indicated by 21H), the write bit (W) shown in FIG.
, transaction ID (TID) and lock bits are also reloaded.

Barware is used to determine which TLB engine was used most recently in each congruence class. And 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.

One TLB is then selected based on which of the two TLBs has the most previously referenced entry in a given congruence class.

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 pick 1- are stored in the main memory.
Reloaded from T entry. This IPT address was previously calculated in the IPT search process. Then, the IPT calculated in the search process
Since the index is equal to the real page number, this value is T
Used to reload the real page number field in the LB. If this value is the special segment 1- indicated by the special segment bit in the segment 1- register, the transaction I+) and the lock bit are also reloaded. In addition, this 1-Ranzaku John ID
and lock bits are reloaded by accessing the third word (see Figure 7) in the selected TPT entry.

(F) IIE access control The address conversion 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 persistent data.

Note that these access control means are applied only to conversion type access. When a violation of the rule is detected by one of the access control means, access to the storage device is stopped. However, there are some exceptions to this, and I will discuss those exceptions later.

(G) Seikai Hiro 1 The memory protection process 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 privileges. 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 the 1-bit protection key in the selected segment register, and whether the key and access to 2 bits 1 in the TLB entry is in the load state (load state) or whether the access is in the read state or not.

Access is controlled as shown in the following table: Table 1: Protection Key Processing If access is not allowed, the address translation operation is terminated and a storage exception is reported to the CPU.

(11) The rectangular lock bit processing is applied only to the special segment indicated by the special segment bit in the selected ceramic register. This lock bit processing allows
In addition to allowing the operating system to automatically monitor and journal changes to persistent variables, lockbit processing also uses hidden pages (
ShadowPage) and performs other processing necessary to maintain the database.

Additionally, lock bits extend 2K or 4 byte resolution page protection to 128 or 256 byte line protection.

In other words, a 2-byte page is given a resolution of 128 bytes, and a 4-byte page is given a 256-byte resolution. That is, the lock bits of individual lines are selected by the valid bits from 21st bit 1st to 24th bit 1st for 2 by 1 to pages, and by 4 by 1 to 24 bits 1 to 24 bits. Valid pitch 1-20
It is selected by the 1st to 23rd bits.

This means that access control is based on the 1-bit write bit in the selected TLB entry, the value of the lock bit on the selected line, and the transaction I in the TLB.
This is a function of the comparison result between D and the current 1-transaction ID, and whether the access is in a load or store operation mode. Access is then controlled as shown in Table 1v.

Table ■■: LockBit Processing 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 simply tells the operating system that it should process the newly changed line.

Now, each page of real memory is provided with reference bits 1 to 1 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 storage. The reference bit is set to rr when the corresponding real page is accessed for reading or writing.
I Set to I+. Also, the change bit is set to “1” (−) when the corresponding page is written.
The 6 reference pins 1- and the modified bits include the I10 read instruction (IOR) and write instruction (IO
W). The reference bit and change bit corresponding to each real memory are
The starting point is the address with 0' added. Then, the reference bit for any page and the I10 address to change pin 1 are given by the following formula: [I10 address] = [address specified by I/○ base address register] +X '1001'+
[Page Number] Each I10 address includes reference bits 1 to 1 and change bits corresponding to each page of real memory. The format of this reference bit I-R and change bit C is shown in FIG. That is, data transferred to reference bits and change pins upon access is defined as follows: Pits 1 to 0 to 29: Zero bit 30: Reference bit. 1 when the corresponding real page is accessed for a read or write operation
” is set.

Pip 1-31: Change bit. Sera 1 to 1” when the corresponding real page is accessed for a write operation.
be done.

Note that the reference bit and change bit are not initialized by hardware. These bits are initialized and cleared by system software IOW instructions. The reference bits 1- and change bits can be set by executing a program to set or clear those bits, so before reading data from the reference bits and change pins 1-,
This does not necessarily mean that when writing to set or clear ~, the same data that was written cannot be read.

(J) Control register group Now, the memory configuration, page table address, I10
A plurality of control registers are provided for setting the base address. These register groups are used for processing/reading (10R) and writing (IOW) from the CPU.
Initialized (loaded) by system software via instructions. The structure and format of each register are shown in FIGS. 9 to 18.3. These registers are only accessible in supervisor state.

A base address (FIG. 9), which specifies the I10 address of the block at 64, is assigned to the address translation system. The value of this work/○ base address is 65536, which is the value stored in the I10 base address register.
(X '10000'). I10
The format of the base address register is as shown in FIG.

The I10 base address register is defined as follows: Bin l-0-23: Pending pins 1-24-31: i10 base address. This 8-pi1 value sets which block of 64-byte I10 addresses within the I10 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.

The register shown in FIG. 10 is a "RAM designation register." This RAM specification register specifies the RAM size and R
It is used to set the AM start address, refresh rate, and whether parity check or error correction code (FCC) is used. Furthermore, since the parity check and FCC are outside the scope of the present invention,
I will not explain it further here.

The RAM command register has format 1 in FIG. 10 and is set as follows: Bits 0-10: Reserved bits 11-19: Refresh rate. These 9 bits set the refresh cycle speed. The refresh cycle rate is equal to the value contained in pins 1-10 through 18 times the CPU clock frequency. Setting the value of bits 10 to 18 to zero disables the refresh operation. The refresh rate value can be calculated by dividing the required memory refresh rate by the CPU clock frequency. for example,
In a system with dynamic memory that requires 128 rows to be refreshed every 2 ms, the refresh interval for each row is 2 ms/128=16.6 μs.

And if the CPU clock period is 200ns,
The refresh rate count is 15.6μs/200
n s, 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
The starting address of the RAM is set for both translation access and non-translation access by field 1~.

Bits 28-31: RAM size. This 4-bit field sets the size of the RAM currently allocated to the address translation system.

(, 1-2) foot □ q bottom 1 big gap 2 no j - Here, ROS refers to Read Only Storage, that is, a read-only storage device. The abbreviation ROS is also used in FIG.

Now, the RO8 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 as shown in Figure 1. It is. Furthermore, R
The OS can be accessed in either conversion mode or non-conversion mode.

The RO3 designation register is set as follows: Bits O-19: Reserved bits 20-27: Starting address of ROS. This 8-pi1- field sets the start address of R, O5 in both conversion access and non-conversion access.

Pi 1-28-31: Size of ROS. 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) is the size of each page (2
bytes or 4 bytes), main memory page table (
ti A-r and IPT combination) start address,
for specifying whether the next hardware TLB reload is interrupted and whether parity is used on the reference array and the modified array;
Its format is as shown in FIG.

The conversion control register is set as follows: P1
-0 to 20: Pending pin l-21 (Figure 12R): Interrupt enable for "TLB reload successful". This bit is used to enable reporting of successful reload of 1'LB by hard ear. When this bit R is set to “1”, an exception response is issued due to a successful re-row of the TLB by the hardware, and the storage exception register (described later)
(See Figure 13) Medium TL B rerotation pitch 1~1"
is set to

Also, this pin 1-R (Fig. 12) is set to “0”.
, the next hardware rerotation of the TLB entry is not reported. The function of this bit is T L
13 can be used to measure the behavior 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 II I II
If set to , parity is used on the reference and modified arrays. Also, if this bit is 0'
'', parity is not used on the reference and change arrays.

Bit 23 (Figure 12S) Two page size. The value "O" is used for a 2 byte page and the value "1" is used for a 4 byte page.

Pits 1-24 to 31: HAT/IPT base address. This 8-bit field is the HAT/
Used to specify the starting address of IPT en 1-1. 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 engine.

For 2 byte pages, the base address is specified by bits 24-31 of this translation control register, and 4
In the case of pi 1 to page, the base address is specified by pi 25 to 31 of this register. Note that constant values for various values of storage size and page size are listed in Section I above.

(,1-4') The storage exception register (SER) is used to report errors in memory accesses, errors in the conversion process, and system errors; i.e., individual Pi1~ is
Provision is made for reporting each error condition detected by the conversion system. If a plurality of errors occur, each error is reported by setting appropriate bits assigned to each error.

Note that the bit that was set to 1 due to the previous error will not be reset due to a subsequent error.

This storage exception register (SER) is initialized to zero by the program operation sequence (FOR). Then, when a certain exception is reported, the system rough 1~ware takes on the role of clearing the SER after the exception operation is processed.

The format of this storage exception register (sER) is as shown in FIG.

Bits Q~21: Pending bit 22 (T in Figure 13): TLB reload successful. T.L.
This bit is set to 1'' when the interrupt on successful entry of B 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 modified array.
- to be done.

Bit 24 (W in FIG. 13): This bit is set to "1" when a write is attempted to RO8 or to an address included in the ROS address space.

Bit 25 (Figure 13 I): IPT specification error.

When an infinite loop is detected in the IPT search chain, this pin 1~ is set to "1". An infinite loop may occur when the value of the IPT pointer is incorrectly specified due to an error in the system software. If an infinite loop occurs in the IPC search chain, the IPT pointer will point to the previous entry in the IPT search chain. Pitch 26 (Figure 13E): External device exception.

This bit is set to "1" when an exception is caused by an external device.

Pih27 (Figure 13M): Quadruple exception. If two or more exceptions (ll"i' specification error, page fault, memory protection, or data) occur before the exception indication is cleared in the storage exception register, this pin 1- or l1-
．． Set to 1''.

This error usually indicates that the system software failed to handle the exception. However, multiple
This bit can be set to 1 if the exception was caused by a store (LM) or store multiple (STM) instruction. This is because a multiple load or multiple store instruction will attempt to load or store all registers specified by the instruction before terminating with an exception.

Bit 28 (Figure 13F) Two 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.
is set to

Pitch 1-29 (Fig. 13 S): Designation. This bin 1 contains “
Set to 1''.

Bit 30 (Figure 13P): Memory protection. This bit is
It is set to "1" when the conversion operation ends because the storage protection process for a 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 2 conversion operation is completed because it is determined that access to the memory is not permitted due to the transaction ID/lock pi 1 processing for the special segment 1-.

(J-5) g Self-memory exception address register storage exception 71-
The address register (SEAR) is for storing a valid storage address. This valid storage address causes an exception to load and store requests from the CPU, and the exception is reported by the storage exception register (SER). Note that S E A R is not loaded for fetch instructions or exceptions caused by external devices.

The format of this storage exception address register is L4.
As shown in the figure.

The storage exception address register is defined as follows:Pill-0-31: Storage exception address. This 32 pics 1
~A valid storage address will cause an exception to be reported by the storage exception register. If multiple errors occur (
If bit 27 of the storage exception register is set to 1''), the address contained 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 for storing a real memory address determined by a 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. Format 1 of real address register to be converted
- is as shown in FIG.

The translated real address registers are defined as follows: Bit O (Figure 15 1): Invalid bit. This bit is set to "1" when address translation fails and is set to LLOI+ when address translation is successful.

Bits 1-7: Zero. These 7-bit fields are always zero.

Pits 1-8 to 31: Real memory address. If the address translation is successful, this 24-bit field contains the real storage address that maps to the given virtual address. This field is also set to zero if the address translation fails.

The transaction identification register (TID) is currently q'η
Contains 8-bit data for identifying the task that is set as the "owner" of the special task. That is,
If a segment 1 is set as special segment 1 by a special bit in the selected segment register, the lock bit processing described above is applied to that storage access. Lock bit processing is 1
-RunSakusion II Uses the value stored in I) and compares the value against the 1-RunSex ID entry in the TLB to determine whether the storage access is allowed. Determine whether transaction identification access is allowed. The format of the I-ranzaktion identification register is as shown in FIG.

The transaction identification register is defined as follows: Bits O-23: Pending.

Bits 24-31 Nidoranzaku Jiyon ID. This 8-bit value is for specifying the "owner" of the special segment.

(J-8) Segment register The segment register has the same format 1- as 1
There are six, and only one of them is shown here. The segment register consists of a segment ID, special bits, and key bits. The segment ID of 12 pins 1- is 2 each.
It is used to specify one of 4096 virtual storage segments each having 56 Mbytes. The special bit indicates that segments 1 through 1 for which this bit is set are special segments, and lock bit processing is applied to them. The key pit is for indicating the access privilege level for the currently executing task related to storage access within a given segment 1-. The format 1 of the segment register is as shown in FIG.

The contents of each segment register are defined as follows: Bins I-0 to 17: Pending.

Pit 1-18-29: 0 from segment 12 pitsu 1
The value of ~ specifies one of 4096 virtual storage segments 1- each having 256 Mbytes.

Pih30 (Fig. 17s): Special bit. This pic 1~
is set to LL I II for special segment 1- and to 1104' for non-special segment 1.

Bins 1-31 (Fig. 17K): Keypit. This pin is for determining 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, two T
Each of the LBs has 16 entries, which provide the translation and control information necessary to translate virtual addresses to real addresses. In addition, each TLB entry also contains information used for storage access control. Further, since the contents of the TLB are automatically updated by hardware from the main memory page chill, even if a TLB entry is written and then read, the same written data is not necessarily read. Furthermore, changing the TLB entry destroys the correspondence between virtual addresses and real addresses, which may 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 TLB en 1 in non-translation mode, disabling all other translation accesses, and then read from it, you will read the same data that was written. Dew.

(K) 'lI' LB En 1 - 6 '1' LB En 1 edge is logically 66 bits (
(excluding reserved bits), and the breakdown of the 66 bits is as follows:
The address tag is 25 bits, and the actual page number is 13 bits.
~． Valid bit is 1 bit, key bit is 2 bits 1~,
Write bit 1- is 1 bit, transaction 11.
) is 8 bits, and the lock bit is 16 bits l-. 8
The TLB En1 edge is partitioned into three fields, which are individually addressable.

The format of each field of this TLB entry is as shown in Figures 18.1 to 18.3.

First, let's call the field in Figure 18.1 TLB address field 1-. The segment ID and virtual page index are stored in this TLB address tag field 1~. This stored data is 2 by 1-
For a page, it is the upper 25 bits of segment 1] and the virtual page index, and for pages 4 and 1 to 1 to 4, it is the L position 24 of them.

The TLB address tag field is defined as follows: Bits O-2: Reserved.

Pits 1-3 to 27: Address tag. This field contains the segment l-ID for the 2 byte page and the upper 25 bits of the virtual page index. still,
For pages 4 and 1 to pie, the address tag is bits 3 to 26.

Pitch 1-28-31: Hold.

Next, let us call the field in Figure 18.2 the TLB real page number field. The TI and B real page number fields contain a real page number, a valid bit (v), and a key pit (KEY). What is the actual page number?TL
This is the number assigned to the virtual address contained in the address tag field of the B entry. Valid bit (
V) is a bit to indicate that a given TLB entry has valid information. Further, the key pit (KEY) is used to indicate the necessary access authority to a given page.

The real page number field is defined as follows: Bit 1-0~15: Suspended.

Gila 1-16-28: Actual page number. This 13-bit field specifies one of 8192 real pages. If fewer than 8129 real pages are used, only the lower bits need to be used to access the real pages used.

Bit 29 (Figure 8.2 V): Valid bit.

This pin 1~ becomes HI II- when the selected 1' T,, B en 1-ri has valid information, and if TL
If the B entry contains invalid information, it becomes rr OII.

Bits 30-31 (Figure 18.2 KEY): Key Pip 1~. This 2-bit field sets access authority for each page. 'Next, let's call the field in Figure 18.3 the TID Lock Pi 1 field. This TID LockPi1~ field has a write bit, a transaction Il), and a LockPi1~ field.

If the TLB entry is for a special bit, the lock bit is assigned to the virtual address contained in the address tag field of the TLB.

The contents of the TID lock bit field are defined as follows: Bits O-6: Reserved.

Bit 7 (Figure 18.3 W): Write bit.

This bit sets the access rights for each page corresponding to the special segment.

Bits 8-14 Nidoranzaktion ID: This 8-bit field establishes the task that currently owns the selected page within the special segment. The use of these bits during lock bit processing has already been described.

Bits 15-31: Lock bits. This 16-bit field sets access authority for each "line" within a 2-byte page or a 4-byte page that corresponds to a special bit.

A line is 128 bytes for a 2 byte page and 256 bytes for a 4 byte page. The use of these bits during lock pit 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 "parallel address load" function similar to the functionality possessed by the IBM System/370 family.

Also, 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. and,
Entries in the TLB and entries in the page frame table must be invalidated so that mapping information that has already been used is not used during subsequent address translation.

Now, regarding the above synchronization, the system of this embodiment has three functions to support synchronization with the TLB entry/1' page table in the main memory. These functions can be used to invalidate all or selected TLB entries.

Additionally, these functions are recognized by the system.
A specific I10 within a 64-byte block of 10 addresses.
Invoked by an I10 write command (IOW) commanded to an address. Note that the allocation of addresses to each of these functions will be given to the system as necessary.

“The all TLB invalidation 2 function invalidates all TLB entries.This allows the TLB entry to be deleted from the page table in main memory corresponding to the next address translation.
The contents of will be updated.

An I10 write instruction to the address associated with this function will invalidate all TLB entries. Note that at this time, the data transferred by the I10 write command is not used.

(L-2) No TLB entry in special segment''
The "Invalidate TLB Entries in a Specific Segment" function invalidates all TLB entries related to a specific segment. This segment ID is used. Subsequent address translation operations cause the contents of the TLB to be transferred to the page tape in main memory. Updated from take.

An I10 write instruction to the address associated with this function disables the TLB edge for a particular segment. The data in bits 0-4 transferred by the I10 write instruction is then
Used to select D. That is, all the rLB 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 main memory page table.

(L-3) TLB entry for address ``Invalidate TLB entry for specific effective address'' function invalidates the TLB entry for the specific effective address. Then, the contents of the TLB are updated from the page table in the main memory by performing address translation next on a certain effective address within the page that includes the specific effective address.

An I10 write instruction to an address associated with this function invalidates the TLB entry for the particular valid address. At this time, the data of bits 0 to 31 transferred by the I10 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 is used by system software to determine i) whether a given virtual address is currently mapped in real memory, and...) if so, which real address. Used to determine whether an I-nos 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 I10 operations are performed using real memory addresses, and therefore the system I10 routine also requires the result of converting virtual addresses to real addresses.

The real address arithmetic function is invoked by an I10 write instruction to the address associated with this function. I
Bits 0-31 of the data transferred by the 10 data write command are used as effective addresses. 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 includes 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 performed when there is an indication of successful address translation.

The result obtained by the real address arithmetic function is read by the I10 read instruction of the real address register to be translated.

A block of I10 addresses consisting of 64 bytes is allocated to the address translation mechanism.

This block of 64 bytes starts at the I10 address specified by the I10 base address register. I
Ten base addresses are set on 64 byte boundaries. ■The assignment of the 10 addresses listed in Table 4 is as follows:
The specified 64 is the displacement within the block of bytes. In this case, the absolute I10 address is equal to the I10 base address plus the displacement6 Table 4 (1'/4) Table 4 (2/4) Table 4 (3/4) Table 4 (4/4) [Invention [Effect] As described above, according to the present invention, HAT (hash address table) and IPT (inverse page table) are combined into a single combined table in the virtual storage device, so that the base address register, The hardware required for table entry address calculation means, address pointers, etc. is half of that of the conventional method, which has the effect of reducing the amount of hardware required. Particularly in large-sized computers, since a large number of the above-mentioned registers are used, application of the present invention can reduce an extremely large amount of hardware.

[Brief explanation of drawings]

FIG. 1 is a block diagram of the main parts of the address translation system and access control system according to the present invention, FIG. 2 is a diagram showing the format of the segment register used in the address translation mechanism of the present invention, and FIG. FIG. 4 is a block diagram and data flow diagram of a system for converting an effective address into a virtual address; FIG. 4 is a block diagram and data flow diagram of a system for converting an effective address into a real address; FIG. 5 is a diagram showing the configuration of an address translation buffer used in the address translation mechanism of the present invention, and FIG. 6 is a block diagram of a combination table of a hash anchor table and a reverse page table, and FIG. 7 is a diagram showing the structure and contents of the actual hash anchor table/reverse page table as stored in memory; FIG. 7A is a block diagram illustrating the memory organization for multiple combined HAT/IPT table entries, each representing a page of real memory; FIG. 8 is the format of the reference and modification bits used for each I10 address; FIG. 9 is a diagram showing the format of the I10 base address register. FIG. 10 is a diagram showing the format of the RAM designation register. FIG. 11 is a diagram showing the format of the RO8 designation register. is a diagram showing the format 1- of the conversion control register, FIG. 13 is a diagram showing the format 1- of the storage exception register, FIG. 14 is a diagram showing the format of the storage exception address register, and FIG. A diagram showing the format of the real address register to be converted. , 48.2 FIG. , 18.3

Claims (2)

[Claims] (1) A hierarchical memory having a plurality of page frames, a central processing unit for supplying virtual addresses, and a virtual address supplied from the central processing unit that is smaller than the virtual address in the page frame. A virtual storage device having 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, and a virtual memory address for each real address. A first table in which addresses are associated, and each hashed address is combined with a scheduled virtual address of a different group of concatenated virtual addresses, and when each of the virtual addresses of the group is hashed; is a combination table in the hierarchical memory that combines the second table for creating the combined hash address; a search means for searching the position of the virtual address of the virtual address; and a real memory corresponding to the virtual address found from the first table in response to the position of the virtual address found by the search means. A virtual storage device comprising: access means for accessing an address. (2) Claim (1) wherein the conversion means comprises 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. The virtual storage device described in .