Methods and apparatus for implementing a pseudo-LRU cache memory replacement scheme with a locking feature

In a computer system comprising master devices including a central processing unit (CPU), and a memory system comprising a main memory having a plurality of lines and a cache memory and a tag table associated with the cache memory, wherein a subset of the lines of main memory are stored in the cache memory for fast access by a master device issuing a request for access to said memory system, said tag table comprising tag bits, said tag bits identifying lines of main memory located in the cache memory, a method for securing selected lines of main memory in the cache memory comprising:

• providing at least one replacement bit for each cache line and at least one lock bit for each cache line of the cache memory in the tag table;
• combining the at least one replacement bit for each cache line and the at least one lock bit for each cache line with a logical OR to produce a composite bit for each cache line;
• controlling the state of the at least one replacement bit for each cache line and the state of the at least one lock bit for each cache line located in the tag table;
• monitoring the composite bit of each cache line to prohibit all composite bits from being set by clearing the at least one replacement bit for each cache line to avoid deadlock;
• and
• replacing a line of cache memory with a different line of memory, only if the cache memory line has a clear composite bit, said replacing a line of cache memory controlled such that by setting the corresponding at least one lock bit for a cache line in the tag table, lines of memory located in the cache memory are secured in the cache memory regardless of a cache replacement algorithm used, and by setting the corresponding at least one replacement bit for a cache line in the tag table, cache memory lines are not replaced regardless of the lock bit.

In a computer system comprising master devices including a central processing unit (CPU), and a memory system comprising a main memory having a plurality of lines and a cache memory wherein a subset of the lines of main memory are stored in the cache memory for fast access by a master device issuing a request for access to said memory system, an apparatus for securing selected lines of main memory in cache memory comprising:

• a tag table comprising tag bits for each cache line, at least one replacement bit for each cache line, and at least one lock bit for each cache line of the cache memory, said tag bits identifying the line of main memory located in cache memory;
• a composite bit for each cache line, each composite bit comprising a logical OR of said at least one replacement bit for a cache line and said at least one lock bit for a cache line;
• an operating system for issuing commands to set or reset the at least one lock bit for a cache line located in the tag table;
• and
• a cache controller to control the contents of the cache memory and the tag table, said cache controller executing a replacement algorithm to replace a line of memory located in the cache memory with a different line of memory and updating the tag table, said cache controller prohibited from replacing a line of memory in the cache if the corresponding composite bit for said line of memory in the cache in the tag table is set, said cache controller clearing said at least one replacement bit for each cache line if all of said composite bits are set, said cache controller controlled such that by setting the corresponding at least one lock bit for a cache line in the tag table, lines of memory located in the cache memory are secured in the cache memory regardless of a cache replacement algorithm used, and by setting the corresponding at least one replacement bit for a cache line in the tag table, cache memory lines are not replaced regardless of the lock bit.