Data processing system with fast queue store interposed between

Abstract

A fast queue mechanism is provided which keeps a queue of changes (i.e. store actions) issued by each processor, which queue is accessible by all processors. When any processor issues a store action to a line of memory in the queue, the old data is overwritten with the new data. If the queue does not currently have a corresponding entry, a new entry is activated. Room for the new entry is made by selecting some existing entry, either the oldest or the least recently used, to be removed. An entry that is to be removed is first used to update the line corresponding to it in main memory. After the changes held in the entry to be removed are applied to the old value of the line (from main memory) and the updated value is put back into main memory, the entry in the queue is removed by marking it 'empty'. When a processor accesses a line of data not in its cache, a cache miss occurs and it is necessary to fetch the line from main memory. Such fetches are monitored by the queue mechanism to see if it is holding changes to the line being fetched. If so, the changes are applied to the line coming from main memory before the line is sent to the requesting processor. After a new entry is made in the queue mechanism, other store actions to the same entry by any processor may occur and usually a number of store actions will occur to the entry before it is removed to make room for another.