Patent GB-1314140-A (GB)
Title: Storage control unit
IPC: G06F12/122
Filed: 1971-09-25
Abstract: 1314140 Digital data storage INTERNATIONAL BUSINESS MACHINES CORP 25 Sept 1971 44776/71 Heading G4C A storage system includes a control unit comprising an associative store which contains a look-up function table which is used to determine the degree of usage of a page of data stored in the system. The degree of usage depends both on the frequency and time of use of the page. The storage system includes a virtual memory comprising a small capacity fast access main memory, which is normally full, and a large capacity slow access back-up memory. Data words are transferred between the main memory and a processor. The processor supplies a logical (or virtual) address specifying a page of data to which the data word to be transferred belongs and the location of the word in the page. The logical address is fed over line 18 to a control unit, Fig. 2 which determines the physical address of the page and controls transfer of the required page from the back-up memory to the main memory, if necessary, and transfer of a page, normally that with the least degree of usage, from the main memory to the back-up memory, if necessary. The control unit comprises two associative stores 22, 24 and a control store 26, e.g. a read only store or a loadable associative store. Field 27 of store 22 holds the logical addresses of groups of pages which are not in the main memory and the logical addresses of pages which are in the main memory. If the processor supplies the logical address of a page currently in the main memory the address acts as a search argument to determine the corresponding physical address in field 28, and the degree of usage (or usage count) in field 30. In a second cycle an exclusive- or look-up table XOR in store 24 is used to form the partial sum of the usage count with a reference count VMRC in field 33. The reference count is the number of times the processor has accessed the virtual memory. The partial sum is stored in register 38. In a third cycle a carry is added to the partial sum, if necessary, by reference to an add-carry table ADC in store 24. The ADC table provides a 1-bit right shift to generate an up-dated usage count which is half of the sum of the usage count and the reference count. The reference count is now incremented, and on the next cycle store 22 stores the updated usage count in field 30. Because only one of the stores 22, 24 is used in each cycle operations on different usage counts can be interleaved, there being two I/O registers for both stores. If the processor supplies the logical address of a page not currently in the main memory a marker bit from field 29 of store 22 indicates this fact. In consequence control store 26 orders the processor to access the back-up memory map held in main storage to determine the physical address of the required page in the back-up memory. An algorithm is now used to determine the page which has the lowest usage count in field 30 and which is also not involved in an input-output operation since such an operation may involve a long wait for signals from a slow peripheral unit. Because more than one page in the main memory may have the same lowest usage count it is then necessary to determine which of these pages has the lowest physical address. If a further marker bit in field 29 indicates that the selected lowest usage count page has had a word written in to it this page must be transferred to the back-up memory. If no word has been written in the page can merely be over-written by the page called for by the processor and read in to the main memory from the back-up memory. When a page is transferred to the main memory its logical address is placed in field 27 and a usage count is placed in field 30, the count selected being high enough to prevent the page shortly being transferred back to the back-up memory (or over-written).