DATA PROCESSING SYSTEM HAVING IMPROVED PROGRAM ALLOCATION AND SEARCH TECHNIQUE

摘要

1491692 Data processing HONEYWELL INFORMATION SYSTEMS Inc 8 Nov 1974 [8 Nov 1973] 48398/74 Heading G4A A data processing system comprises a main memory 108 (Fig. 1) containing routines, each consisting of a sequence of commands to be carried out in response to an instruction received on line 100 and a search table 106 containing, for each routine, an entry identifying the routine and including an address in main memory. If no entry is found for an instruction, the routine with the lowest activity is replaced by the requested routine. The six most significant bits of the instruction are fed by mask 102 to a start table point 104 which has 64 locations each with an address for entry in the table 106 (which has more than 64 locations). The entries are queued so that most recently used and least recently used entries are at opposite ends. Each entry in table 106 includes 5 parameters, (1) a search argument 110; (2) a P-pointer 111; (3) a link pointer 112; (4) H-pointer 113, and (5) a T-pointer 114. The search argument is used to indicate if there is a "hit" between an instruction received and the addressed entry. If there is the P-pointer is used to address the program memory 108. The link pointer indicates the next entry in a linked family of entries, the last member of the family having a zero link pointer. The H- and T- pointers indicate respectively the next more recently and the next less recently used entries. Head and tail pointers 118, 116 indicate the most recently used and least recently used entries in the table. If there is no hit and if the link pointer of the access entry is not zero the entry indicated by the link pointer is accessed to see if there is a hit, in which case its address is put in the table 104 of the initial address link family. This process is continued if there is no hit until the link pointer is zero when an entry is inserted in table 106 of the address indicated by the tail pointer unless the associated program is still active, the head pointer then being up-dated to indicate this entry.