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

Claim 2

The apparatus as set forth in claim 1, wherein said tag table further comprises at least one replacement bit for each line in the cache, said replacement bit indicating usage of the line in the cache and is used by the replacement means to determine the line in the cache to replace.

Claim 3

The apparatus as set forth in claim 2, wherein said replacement bit indicates recent usage of the line in the cache, said replacement means executing a least-recently-used (LRU) replacement algorithm to determine the line of the cache to replace.

Claim 4

The apparatus as set forth in claim 2, wherein said replacement means logically ORs the replacement bit and lock bit to generate a composite value used to determine the line of the cache to replace.

Claim 5

The apparatus as set forth in claim 1, wherein said means for controlling the state of the lock bit bit further comprises a monitoring means to monitor the number of lock bits set in the tag array to prohibit all lock bits from being set.

Claim 6

The apparatus as set forth in claim 1, wherein said means for controlling the state of the lock bit further comprises means for identifiying at least one predetermined line of the cache as non-lockable such that deadlock is avoided.

Claim 7

The apparatus as set forth in claim 1, wherein said replacement means comprises a cache controller.

Claim 8

The apparatus as set forth in claim 1, wherein said means for controlling the state of the lock bit comprises instructions issued by the master device.

Claim 9

The apparatus as set forth in claim 8, wherein said means for controlling the state of the lock bit comprises instructions issued by an application process executing on the computer system.

Claim 10

The apparatus as set forth in claim 9, wherein said instructions are processed by an operating system of the computer system to issue commands to a cache controller to set the lock bit.

Claim 11

The apparatus as set forth in claim 1, wherein said means for controlling the state of the lock bit comprises a compiler to compile a program to generate compiled code to be executed, said compiler evaluating the program and inserting commands to set/reset the lock bit in the compiled code.

Claim 12

In a computer system comprising master devices including a central processing unit (CPU), and a memory system comprising a main memory, a faster 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 memory, said tag table comprising tag bits, said tag bits identifying the line of main memory located in cache wherein said tag bits are compared to determine if access to memory is provided by providing the line from the cache, a method for securing selected lines of main memory in cache memory comprising the steps of: providing at least one lock bit associated with each line of the cache in the tag table; controlling the state of the lock bit for each line of the cache located in the tag table; and replacing a line of memory located in the cache with a different line of memory, such that lines of the cache having an associated lock bit which is set are not replaced; wherein by setting the corresponding lock bit in the tag table, lines of memory located in the cache are secured in the cache regardless of the cache replacement algorithm.

Claim 13

The method as set forth in claim 12, wherein said tag table further comprises at least one replacement bit associated with each line of the cache, said step of replacing a line of the cache referencing the replacement bit and the lock bit to determine the line of the cache to replace.

Claim 14

The method as set forth in claim 13, wherein said step of replacing logically ORs the replacement bit and the lock bit to generate a composite mask used to determine the line of the cache to replace.

Claim 15

The method as set forth in claim 13, wherein said step of replacing utilizes a least-recently-used algorithm to determine the line of the cache to replace.

Claim 16

The method as set forth in claim 12, wherein the step of controlling the state of the lock bit comprises providing instructions to set/reset the lock bit in the application process executing in the computer system.

Claim 17

The method as set forth in claim 16, wherein the step of controlling the state of the lock bit further comprises issuing commands to set/reset the lock bit in the tag table when an instruction in the application program to set/reset the lock bit is executed.

Claim 18

The method as set forth in claim 12, wherein the lock bits are set/reset during the execution of a program on the computer system, said method further comprising the step of compiling the program into compiled code to be executed, said step of compiling comprising: evaluating the program to determine when lock bits are to be set/reset for certain lines of memory placed in the cache; inserting commands to set/reset lock bits in the cache into the compiled code; and generating compiled code comprising the program and commands to set/reset the lock bits.

Claim 19

In a computer system comprising master devices including a central processing unit (CPU), and a memory system comprising a main memory and a faster 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 memory, an apparatus for securing selected lines of main memory in cache memory comprising: a tag table comprising tag bits, at least one replacement bit and at least one lock bit for each line of the cache, said tag bits identifying the line of main memory located in cache wherein said tag bits are compared to determine if access to memory is provided by providing the line from the cache; an operating system for issuing commands to set/reset the lock bits located in the tag table; and a cache controller to control the contents of the cache and the tag table, said cache controller executing a replacement algorithm to replace a line of memory located in the cache 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 lock bit in the tag table is set; wherein by setting the corresponding lock bit in the tag table, lines of memory located in the cache are secured in the cache regardless of the cache replacement algorithm.

Claim 20

The apparatus as set forth in claim 19, wherein said operating system communicates the command to set/reset the lock bits to the cache controller which performs the setting/resetting of the lock bits.