Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
1995-06-05
2001-12-18
Gossage, Glenn (Department: 2759)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S217000, C711S156000
Reexamination Certificate
active
06332185
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to digital data processing and, more particularly, to paging data and related information to and from secondary storage devices.
High-speed physical storage space on computer systems is limited. Programs that run on those systems often require access to more data than that which can fit into the high-speed stores, referred to as random access memory, or RAM. Sometimes the programs themselves—not just the data they process—consume more memory than available on the system.
Early programs managed excess data by moving it directly between memory and secondary storage devices, e.g., magnetic disk drives, as needed. This required little memory—just the space needed to store the data currently being processed—but slowed processing by requiring frequent disk accesses. Some gains were obtained by accessing data in blocks, reading large amounts of data from disk into arrays, processing those arrays, then writing them back out to disk.
With the advent of virtual memory management systems, data management functions have been taken over by the computer operating system software. Programs written for use with these systems reference large amounts of data as if it were stored entirely in memory. Often it is not: the virtual memory system itself moves data back and forth between physical memory and disk.
Conventional operating systems, while effective for paging data per se, do not effectively retain “out of band” information. That is, information that pertains to the data, but which is not stored in logical memory structures common to it.
This is of particular concern in paging data within a multiprocessor systems of the type disclosed by Frank et al, U.S. patent application Ser. No. 136,930, filed Dec. 22, 1987, now U.S. Pat. No. 5,055,999, issued Oct. 8, 1991. There a digital data processing system comprises a plurality of processing cells, each including a central processing unit and a memory element, arranged in a hierarchy of rings. The memory elements can each include a directory element that maintains a list of descriptors reflecting the identity and state of each datum stored in the corresponding memory. While one portion of each descriptor “identifies” the associated datum (e.g., providing its system address), the other portion represents the datum's access state, governing the manner in which the local central processing unit (and the other processing cells) may utilize the datum.
One access state utilized in the disclosed system is the “atomic” state. A datum in that state can only be accessed by the owning central processing unit. All other cells are prohibited from accessing the datum until it is released by its owner. Because the atomic state information, in particular, and the descriptor information, in general, is retained separately from the associated datum, that information is considered to be out-of-band.
While the Frank et al system provides data movement and paging mechanisms, still further advances in this area are desirable. In view of the foregoing, an object of this invention is to provide an improved digital data processing system.
More particularly, an object is to provide an improved apparatus and method for paging data that is associated with out-of-band information.
Still another object is to provide an improved system of the type described above operating under UNIX™ or a UNIX-like operating system.
A further object is to provide a computer operating system having a paging mechanism the effectively handles attributes reflecting that data is associated with a specific processors and cannot be accessed by the other processors.
SUMMARY OF THE INVENTION
These and other objects are attained by the invention, which provides in one aspect a digital data processing system that transfers out-of-band information to and from a status file when paging data to a data file. The invention has applicability, inter alia, in storing out-of-band data access information on UNIX-type operating systems.
More generally, the invention provides an improved digital data processing apparatus of the type having (i) a memory element that stores data for access by one or more processes, and (ii) a secondary storage element, e.g., a disk drive, for non-volatile data storage. A paging mechanism, e.g., the operating system, selectively transfers sets of data between the memory and associated data file on the disk.
In one aspect, the improvement is characterized by a directory that stores “atomic” signals, or bits. Each such bit reflects an attribute, or state, of one or more data in the set. By way of example, these signals can reflect an access state of the associated data.
The paging mechanism includes a page-out element that stores data from a subset of the set to the associated data file. During paging, that element responds to data in the subset which are associated with the atomic state—as reflected by the atomic bit—for storing to an associated status file, on the disk, signals representing the attributes of the paged data. Those signals can be, for example, the atomic bits themselves.
According to another aspect of the invention, the page-out element stores attribute-representative signals to the status file during paging, regardless of whether any data in the subset being paged is in the atomic state. This occurs, for example, where a status file associated with the data file has already been created and stores attribute-representative signals for other data in the set.
In still another aspect of the invention, the page-out element tracks a range, or window, of the addresses of data in the set for which the attribute, e.g., the access restrictions, have been changed by a process. When paging a data subset falling outside the window, the page-out element does not determine whether any data in that subset is associated with the attribute, e.g., the atomic state.
According to this aspect, a process executing on the digital data processor can request allocation of a new datum within the set. A memory manager responds to that request by allocating the requested datum. Where the address of that datum falls outside the window, the manager disables a process from associating that datum with the attribute—that is, for example, preventing the process from claiming exclusive access to the datum.
When a process attempts to make the datum atomic, the manager generates a trap, while at the same time enabling atomic association and setting the atomic bit for that datum. The page-out element responds to the trap for expanding the window to include the address of that datum.
In a related aspect of the invention, the paging mechanism immediately enables atomic state association for data whose addresses lie within the window.
In still another aspect, the paging mechanism includes a page-in element for restoring data to the set from the associated data file. The page-in elements responds to data in the data file which is associated with the attribute-representative signal for placing that data, upon being restored in the set, in the atomic state.
Particularly, upon restoring from the disk a datum associated with the attribute-representative signal, the page-in element generates a GET signal, to which the memory manager responds for placing that datum in atomic state. This is the same signalling mechanism utilized by processes for setting the atomic bit.
These and other aspects of the invention are evident in the attached drawings and in the description which follows.
REFERENCES:
patent: Re. 28811 (1976-05-01), Pierce
patent: 3713096 (1973-01-01), Comfort et al.
patent: 3723946 (1973-03-01), Alvarez et al.
patent: 3731002 (1973-05-01), Pierce
patent: 3735362 (1973-05-01), Ashany et al.
patent: 3748647 (1973-07-01), Ashany et al.
patent: 3800291 (1974-03-01), Cocke et al.
patent: 4011545 (1977-03-01), Nadir
patent: 4031512 (1977-06-01), Faber
patent: 4077059 (1978-02-01), Cordi et al.
patent: 4141067 (1979-02-01), McLagan
patent: 4240143 (1980-12-01), Besemer et al.
patent: 4245306 (1981-01-01), Besemer et al.
patent: 4293910 (1981-10-01), Flusche
Kaufman Mark A.
Oliveira Fernando
Conley Rose & Tayon PC
Gossage Glenn
Kivlin B. Noäl
Sun Microsystems Inc.
LandOfFree
Method and apparatus for paging data and attributes... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for paging data and attributes..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for paging data and attributes... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2595243