Network Security Internet Technology Development Database Servers Mobile Phone Android Software Apple Software Computer Software News IT Information

In addition to Weibo, there is also WeChat

Please pay attention

WeChat public account

Shulou

Example Analysis of operating system Page replacement and Redis memory obsolescence

2025-01-28 Update From: SLTechnology News&Howtos shulou NAV: SLTechnology News&Howtos > Internet Technology >

Share

Shulou(Shulou.com)06/01 Report--

Editor to share with you about the operating system page replacement and Redis memory elimination example analysis, I believe that most people do not know much about it, so share this article for your reference, I hope you will learn a lot after reading this article, let's go to know it!

Why does the operating system need page replacement? because there is not enough physical memory to load all the required data pages at the same time, only the memory pages that are being or recently to be used can be loaded. The goal of page replacement is to replace memory pages that are no longer in use or are no longer in use for a period of time, otherwise it will easily trigger a page fault interrupt, which is expensive and involves loading from disk, so page replacement is not a casual matter.

In order to reduce the number or probability of subsequent page faults, people have designed a variety of page replacement algorithms, which can be divided into fair algorithms and unfair algorithms.

Fair algorithm: random algorithm, FIFO algorithm, clock algorithm.

Unfair algorithms: NRU algorithm, LRU algorithm, working set algorithm.

Random algorithm

This is a simple random selection for page replacement, needless to say, simple and rude.

FIFO algorithm

This is a first-come, first-come, you can use the linked list to record the order of page allocation, elimination according to the order can be eliminated, it is also very simple and rude.

Clock algorithm

The pages in use in memory are checked according to the logical shape of the clock. When the pages are eliminated, they are checked in the order of the clock. If the pages are not accessed (each page corresponds to an access ID, which is set to 0 when not accessed), they will be replaced directly; if they have been accessed, the access bit will be set to 0 to facilitate the next elimination. The clock logic diagram is as follows:

NRU algorithm

Recently, we have not used an algorithm to replace pages that have not been visited recently. This choice is based on the spatio-temporal locality of program access. According to the locality of time and space, a page that has not been visited recently is unlikely to be visited in the following time, and the implementation of NRU is realized by using the visit and modification bits of the page.

The limitation of time and space is reflected in many programming ideas, such as page cache caching recent read and write message data in rocketmq.

LRU algorithm

LRU is an improvement on the NRU algorithm, which takes into account the most recently used frequency rather than whether it has been used recently. The implementation of the LRU algorithm must somehow record the number of times each page has been visited. The simple way is to add a count field to the entry of the page table. If a page is visited once, the value of the counter will be increased by 1; or use the linked list structure to move the page to the link header each time it is visited.

Working set algorithm

Considering the implementation of the LRU algorithm, it needs to keep some records for each page, and update these records at each page visit or periodically, resulting in high time and space costs. The concept of working set comes from the spatio-temporal locality of program access, and the pages accessed by the program will be limited to a set of pages over a period of time.

For example, if the most recent K visits have occurred on some m pages, then m is the working set when the parameter is k. The number of pages involved in k visits at time t is represented by w (k, t). Obviously, with the growth of k, the value of w (k, t) will increase. After k increases to a certain value, the growth of w (k, t) will be very slow or even nearly stagnant, and will be maintained for a period of time.

Working set algorithm is an embodiment of the limitations of the operating system, for a period of time, the data of CPU operations are mostly concentrated on a small amount of data, so we can apply the working set algorithm to replace pages.

Memory obsolescence in Redis

The above analysis of the operating system page replacement algorithm, in a broader sense, page replacement is memory elimination, the operating system page replacement algorithm may not directly let developers feel, after all, this is the OS level. The following will take the Redis commonly used in actual development as an example to analyze the Redis memory elimination strategy in order to deepen the understanding of memory elimination.

Redis's memory elimination strategy refers to how to deal with data that requires new writes and requires additional space when Redis runs out of memory for caching. Currently, there are several memory elimination strategies for Redis:

Noeviction: when there is not enough memory to hold new write data, the new write operation reports an error.

Allkeys-lru: when there is not enough memory to hold newly written data, remove the least recently used key in the key space.

Allkeys-random: when there is not enough memory to hold newly written data, a key is randomly removed in the key space.

Volatile-lru: when there is not enough memory to hold newly written data, remove the least recently used key from the key space where the expiration time is set.

Volatile-random: when there is not enough memory to hold newly written data, a key is randomly removed from the key space where the expiration time is set.

Volatile-ttl: when there is not enough memory to hold newly written data, key with an earlier expiration time is removed first in the key space where the expiration time is set.

For LRU (Least Recent Used), to eliminate the least frequently used, LRU can be implemented through hashMap + two-way linked list. If Redis is also implemented based on hashMap + two-way linked list, it obviously needs to make great changes to the current data structure. In order to pursue space utilization, Redis adopts a tradeoff: Redis will select a fixed number of key based on server.maxmemory_samples configuration, and then compare their lru access time. Then the larger the value of eliminating the most recently unaccessed key,maxmemory_samples, the closer the approximate LRU algorithm of Redis is to the strict LRU algorithm, but the corresponding consumption becomes higher, which has a certain impact on performance, and the sample value defaults to 5.

From the point of view of the implementation scheme of memory elimination of Redis, although it follows the idea of LRU, it does not copy completely, and trade-off is carried out according to the actual application scenario.

The above is all the contents of the article "example Analysis of operating system Page replacement and Redis memory obsolescence". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.

Views: 262

*The comments in the above article only represent the author's personal views and do not represent the views and positions of this website. If you have more insights, please feel free to contribute and share.

Share To

Internet Technology

Wechat

© 2024 shulou.com SLNews company. All rights reserved.

12
Report