Storage queue with adjustable level thresholds for cache invalidation systems in cache oriented computer architectures

Abstract

In a time-shared bus computer system with processors having cache memories, an adjustable invalidation queue for use in the cache memories. The invalidation queue has adjustable upper and lower limit positions that define when the queue is logically full and logically empty, respectively. The queue is flushed down to the lower limit when the contents of the queue attain the upper limit. During the queue flushing operation, WRITE requests on the bus are RETRYed. The computer maintenance system sets the upper and lower limits at system initialization time to optimize system performance under maximum bus traffic conditions.

We claim: 
     
       1. In a computer system having first and second memory systems, said second memory system being a cache memory system for storing data resident in said first memory system, addressable locations of said first memory system being overwritten in operation of said computer system thereby creating overwritten addressable locations, said cache memory system comprising spy means for monitoring when addressable locations of said first memory system are overwritten and for providing address signals representative of said overwritten addressable locations,   queue means responsive to said address signals for storing said address signals, thereby providing queued address signals, said queue means holding a number of said queued address signals,   invalidation means for withdrawing queued address signals from said queue means and marking locations of said cache memory system invalid in accordance therewith, said invalidation means being controllably operative to perform a queue flushing operation by continuously withdrawing queued address signals from said queue means and marking locations of said cache memory system invalid in accordance therewith,   upper limit determining means responsive to said number of said queued address signals for providing an upper limit signal when said number of said queued address signals reaches an adjustable upper limit,   lower limit determining means responsive to said number of said queued address signals for providing a lower limit signal when said number of said queued address signals reaches an adjustable lower limit,   said invalidation means being responsive to said upper and lower limit signals and operative to perform said queue flushing operation in response to said upper limit signal and to discontinue said queue flushing operation in response to said lower limit signal, and   setting means for setting said adjustable upper and lower limits,   said queue means having a maximum capacity,   said setting means being operative to set said adjustable upper limit at less than said maximum capacity so as to create a full-fill margin between said adjustable upper limit and said maximum capacity for accepting and storing address signals from said spy means when said queue flushing operation is being performed.   
     
     
       2. The cache memory system of claim 1 wherein said queue means comprises a FIFO. 
     
     
       3. The cache memory system of claim 1 further including a counter for providing a count signal representative of said number of said queued address signals, said counter being responsive to said spy means for incrementing said count signal when an address signal is entered into said queue means,   said counter being responsive to said invalidation means for decrementing said count signal when a queued address signal is withdrawn from said queue means.   
     
     
       4. The cache memory system of claim 3 wherein said upper limit determining means includes comparator means responsive to said adjustable upper limit and said count signal for providing said upper limit signal when said count signal reaches said adjustable upper limit. 
     
     
       5. The cache memory system of claim 3 wherein said lower limit determining means includes comparator means responsive to said adjustable lower limit and said count signal for providing said lower limit signal when said count signal reaches said adjustable lower limit. 
     
     
       6. The cache memory system of claim 1 wherein said first memory system comprises a main memory of said computer system, said computer system comprising a processor, said cache memory system being included in said processor,   an I/O system, and   bus means intercoupling said processor, said main memory and said I/O system.   
     
     
       7. The cache memory system of claim 6 wherein WRITE operations to said main memory are effected by issuing WRITE requests on said bus means, said processor further including RETRY means responsive to said upper and lower limit signals for issuing a RETRY signal to said bus means to cause RETRYing of said WRITE requests while said queue flushing operation is being performed.   
     
     
       8. The cache memory system of claim 6 wherein said setting means is operative for setting said adjustable upper and lower limits so as to minimize said issuing said RETRY signal to said bus means to enhance performance of said computer system. 
     
     
       9. The cache memory system of claim 8 wherein said setting means is operative for setting said adjustable upper and lower limits to 8 queued address signals and 4 queued address signals, respectively. 
     
     
       10. The cache memory system of claim 8 wherein said spy means comprises means for monitoring said bus means to detect said address signals representative of said overwritten addressable locations and to accept said address signals for transmission to said queue means for storage therein, said spy means being further operative in response to said upper and lower limit signals to disable acceptance of said address signals from said bus means while said queue flushing operation is being performed.