Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reissue Patent
1991-12-20
2001-07-31
Lane, Jack A. (Department: 2751)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S206000, C711S208000, C711S216000
Reissue Patent
active
RE037305
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to computer memory subsystems and more particularly to such a memory subsystem organized into what is known in the art as a virtual memory. Still more particularly, the invention relates to an apparatus for converting virtual addresses into real memory addresses and for effecting certain unique control functions within the memory hierarchy.
In most modern computer
system
systems
, when a program is executing, it frequently attempts to access data or code which resides somewhere in the system (that is, in some level of the cache/main store/Direct Access Storage Device (DASD) storage hierarchy or even at another node in a distributed system network). For the most primitive system, consider what the program must understand in order to make this access.
Where is the data (or code)? The location will generally determine what kind of address must be used for the access (e.g. main storage address of 24 bits, or sector address on a disk track, or node address in a network). The location will also determine what kinds of instructions must be used to accomplish the access (e.g. Load/Store/Branch for main storage accesses, channel command words for disk accesses, communication protocols for network accesses).
Is this data shared with our program executions? If it is, the access cannot proceed unless certain locks are held. If the changes which this program is about to make to data are not to be seen by others at this time, the Store instruction must be to some private address.
Is this data to be recoverable? If it is, some “journalling” strategy must be implemented so that a consistent prior state of the data can be retrieved when necessary.
Suppose, in this very primitive system, the program was in fact required to make these distinctions at each access. Then the following would result:
If the program is to be generally applicable the accesses would be very slow, even for the most frequent occurrences of “trivial, safe” requests, namely, for private, unrecoverable data in main storage.
If the program were to perform well it would be locked into one accessing mode, so that it would not run correctly against data with different characteristics.
The program would be complex, large and prone to error.
Modern systems have addressed these problems in varying degrees. For instance:
Relocate architectures generally allow private, unrecoverable, nonpersistent data and programs to be addressed uniformly, with an address size of 16 to 32 bits—(usually adequate for temporary computational requirements). When these architectures are implemented with proper “look-aside” hardware, the vast majority of such accesses are accomplished at cache or main storage speeds. Only when this look-aside hardware fails (less than one in one hundred attempts) does the system pay the cost of accessing the relocation table structure. And only when the relocation tables fail (i.e. the data is not in main storage) does the system pay the significant “page fault” overhead. Thus the penalties are paid only when they are really necessary, which is surely the goal of a good architecture and implementation.
When the data is to persist beyond this execution of this program, most modern systems require that, instead of Load/Store/Branch instructions, access be made by explicit requests to software-implemented “access methods.” These access methods generally support data which are organized into certain defined aggregates, called “records” and files.” The “instruction” to access are usually called “read/write” or “get/put.”
This data is not shared or recoverable. It may in fact be in main storage (in some buffer area). But for every access, the program must pay the overhead of these explicit “read/write” calls. Thus access methods, when suitably defined, have resulted in programs which are less complex and more generally usable than in primitive systems, but the performance of these accesses are uniformly poorer than Load/Store, and the data accessed must have been structured into the appropriate aggregate type.
When the data is to be shared or recovered, most modern systems require that explicit requests be made to software-implemented “data-base subsystems.” These accesses are generally much slower than those for access methods, not only because of the additional functions of lock and journal management, but also because the kinds of aggregates which these subsystems support (e.g. relations, hierarchies) are themselves more complex.
Again, the data may in fact be more simply structured and in a buffer in main storage, but the overhead must be paid on every access request.
Some systems support the recovery of non-persistent data with a facility called “checkpointing.” Now the programmer who wishes to write a recoverable application must deal with three different facilities—checkpointing for computational data, explicit backup for files, and “commit” instructions for data base.
The IBM System/38 has gone farther than most systems in providing at least a uniform addressing structure for all data. But it has done this at the cost of making all addresses very large, many accesses very slow, much storage and hardware required to implement the architecture, and has not yet provided a uniform approach to sharing or recovery.
Various techniques are known in the art whereby a number of computer programs, whether executed by a single essential processing unit or by a plurality of such
a
processing units, share a single memory. The memory being shared by programs in this manner requires an extremely large parent storage capacity, which capacity is often much larger than the actual capacity of the memory. If, for example, a system employs a 32-bit addressing scheme, 2
32
addressable bytes of virtual storage are available. This virtual storage space is conventionally thought of as being divided into a predetermined number of areas or segments each of which is in turn divided into pages with each page consisting of a predetermined number of lines each in turn having a predetermined number of bytes. Thus segment and page designations or addresses assigned to virtual storage are arbitrary programming designations and are not actual locations in main storage. Therefore, virtual segments and pages are usually randomly located throughout main storage and swap in and out of main storage from backing stores as they are needed.
The random location of segments and pages in main storage necessitates the translation of virtual addresses to actual or real addresses using a set of address translation tables that are located in main storage conventionally referred to as page frame tables. In a large virtual system a great many such address translation tables are employed. These may be organized in a number of different ways. The essential feature of any such organization is that the particular virtual address must logically map to a memory location in said tables which will contain the real address for said virtual address (if one exists).
Functionally, the operation of such address conversion tables is as follows: the high order bits of the particular virtual address are used to access a specific section of said translation tables, which relate to a particular frame or segment, where upon a search is then performed on the lower bits to see if a particular virtual address is contained therein and, if so, what real address is associated therewith. Each page table pointed to by a virtual frame address contains the real locations of all of the pages in one of the frames. Therefore if a particular frame is divided into for example, 16 pages there would be 16 page tables, for each frame, and a separate frame table which would have the entries pointing to a particular set of individual page tables. It should be understood that the above description is generalized in nature and that there are many different ways of organizing the address conversion utilizing the page tables, as well as the means for addressing same, starting with the CPU produc
Chang Albert
Cocke John
Mergen Mark F.
Radin George
International Business Machines - Corporation
Lane Jack A.
Sughrue Mion Zinn Macpeak & Seas, PLLC
LandOfFree
Virtual memory address translation mechanism with controlled... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Virtual memory address translation mechanism with controlled..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Virtual memory address translation mechanism with controlled... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2506347