{'fraction_non_alphanumeric': 0.02966432474629196, 'fraction_numerical': 0.00312256049960968, 'mean_word_length': 4.907834101382488, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Competitive Cache Replacement Strategies for Shared Cache Environments

We investigate cache replacement algorithms (CRAs) at a cache shared by several processes under different multicore environments. For a single shared cache, our main result is the first CRA, GLOBAL-MAXIMA, for fixed interleaving under shared full knowledge [1], where any data can be accessed by any process, and each process has full knowledge about its future request sequence. We establish that GLOBAL-MAXIMA has competitive ratio within a constant factor of optimal. This answers the major open question in [1]. We also present RR-PROC-MARK, a CRA for the disjoint full knowledge case, which is very simple and efficient, and achieves a better competitive ratio than the algorithms in [2], [1]; it is in fact optimal except when the number of processes sharing the cache is small. We then consider a cache hierarchy, both for a single process and when shared by several processes. We present CRAs for three types of caching models commonly used at a higher level cache: inclusive, exclusive, and partially-inclusive, and we establish that several of our CRAs have optimal competitive ratio. Our results for a cache hierarchy are new even in the traditional no knowledge case and even for a single process.