4341 LRU Circuits for TLB
The IBM 370 model 4341 had a fully associative eight entry TLB.
I believe that it could not load a TLB entry during an instruction and some instructions could reference 8 pages.
(The architecture decreed that an instruction could not produce any side effects unless it could produce them all.)
The machine allocated hardware 28 bits, one for each pair of distinct TLB entries.
The bit was on if the lower of those two entries had been more recently used.
Each use of an entry would unconditionally turn off some bits and turn on others, which bits depending only on which entry.
The circuitry to determine which entry was least recently used is not immediately obvious but fast, I think, at worst for each entry a 7 way and of some of those bits or their negation.
This was a perfect LRU.