Storage Allocation Mechanism
Original Publication Date: 1975-Feb-01
Included in the Prior Art Database: 2005-Feb-28
AbstractThis storage allocation mechanism minimizes the amount of traffic back and forth between primary storage and auxiliary storage in a virtual storage data processing system, by minimizing the number of pages of virtual storage actually in use. This is accomplished by filling up all partially filled virtual storage pages before using any additional virtual storage pages.
Storage Allocation Mechanism
This storage allocation mechanism minimizes the amount of traffic back and forth between primary storage and auxiliary storage in a virtual storage data processing system, by minimizing the number of pages of virtual storage actually in use. This is accomplished by filling up all partially filled virtual storage pages before using any additional virtual storage pages.
Fig. 1 represents a portion of a virtual storage address space 10. The address space 10 is divided into pages of fixed size and each page is subdivided into a fixed number of equal size storage locations 12. Each storage location 12 is capable of storing a block of data which contains a fixed number of bytes, where a byte is the smallest unit of addressable data in the system. Typically, the size of a storage location represents the size of the bundle of data which is accessed during any single read-in or read-out operation. In Fig. 1, pages 1 and 3 are indicated as being partially filled with data blocks, while page 2 is indicated as being completely full. Page 0 contains the customary header type information.
When additional data is to be stored in the system, the objective is to fill up all partially filled pages currently in use before starting any new pages. This is accomplished by maintaining a list of partially filled pages and by first consulting this list whenever a new block of data is to be placed in storage. For sake of a name, this list will be called the "free list". If no partially filled pages are available, then and only then will the address space be extended to bring in a new page or pages. A page is also added to the free list when it reverts from a completely filled status to a partially filled status.
The free list is a chain type structure. The header portion of the address space 10 includes a data field 13 called "FREELIST", which points to the first partially filled page on the list. Each of the remaining pages in the address space 10 includes a storage location 14 which is reserved for use in maintaining the free list, and for locating any unused or unallocated storage locations on its page. These storage locations 14 constitute storage location "use blocks". The bit mask field in each such use block 14 contains one bit for each storage location on its page.
The mask bit for a particular storage location is turned off if that storage location is in use or is allocated for use by a data block. The mask bit is turned on if the storage location is available for use by new data blocks. The "NEXT PAGE LINK" field of each storage location use block 14 contains the address of the storage location use block for the next page on the free list, with the exception that the NEXT PAGE LINK field is zero for the last page on the list.
The example represented by the directed lines shown to the right of the address space 10, indicates that the address in FREELIST field 13 is the address of the use block 14 of page 3, the address...