Patent GB-1436488-A (GB)
Title: Data processing system
IPC: G06F12/12
Filed: 1974-06-12
Abstract: 1436488 Data processing INTERNATIONAL BUSINESS MACHINES CORP 12 June 1974 [2 Aug 1973] 25990/74 Heading G4A A data processing system operating as a paging machine, a programme being considered as a page reference string and having fast primary storage for m pages of a string and slow secondary storage for at least the remainder m-m of the page includes means for determining the minimum memory capacity (MMC) of the pages of the string. A first list of the pages of the programme weighted in accordance with a least recently used (LRU) criterion is maintained by assigning to each programme page one of the integers 1-n. The list is in two parts the first containing the pages in fast store assigned integers 1 to m and the second containing the pages in the slow store assigned integers m + 1 to n. A second list OPT from which the minimum memory capacity may be determined has a storage location for each location in the first list. When a page is addressed fast storage and is assigned the integer 1 (1#l#m) the second list is accessed at the location l. The address k (l#k#m) at which the lowest value MMC integer C(k) is held is ascertained and the series of addresses 1, 1 + a, 1 + b . . . between 1 and k-1 such that C(1+a)<C(1) &c. are marked. The smallest missing number between 2 and C max +1 where C max  is the largest value integer at addresses 2 to l-1 is then generated and after the contents of addresses 2 to l-1 have been shifted to addresses 3 to l the generated number is placed at address 2. The contents of the marked series of addresses are shifted to the next address in series, the contents of address k being discarded. The generated missing number is the MMC for the reference page. When the reference page is not in fast storage, i.e. a page exception occurs, a prgramme is effected for updating the second list to aliminate any duplicate integers that have arisen by accessing pages held in fast store. The page assigned integer m is transferred to secondary storage and to the second portion of the LRU list where it is assigned the integer m + 1 the contents of addresses between m + 1 and one less than the reference page being incremented. The name of the addressed page is placed in the first part of the LRR list and assigned at the integer 1. All subsequent pages with integers 1 to m-1 are incremented. The OPT list is then accessed at the address corresponding to the weighting of the reference page before it is transferred to the fast store and the operations effected when an accessed page was in the fast store are now carried out on the whole of the POT list to completely undate it. Apparatus for performing the operation is described the first portion of the first list and the associated portion of the second list comprising a stack of registers forming part of an associated memory. The secondary store may be a disc file. The waiting integers in the LRU list are stored in 1-out-of-n code so that incrementing may be effected by shifting. The smallest missing integer in the OPT list is found by comparing the contents of the relevant registers with the integers 2, 3 &c. until no match is found.