search
HomeWeb Front-endHTML TutorialPage replacement algorithm_html/css_WEB-ITnose

Optimal replacement algorithm


The optimal replacement algorithm is an idealized algorithm that has the best performance, but in reality It's not possible (yet).


The optimal replacement algorithm is a theoretical algorithm proposed by Belady in 1966. The pages it selects for elimination will never be used in the future, and may be pages that will no longer be accessed in the longest (future) time. Using the best replacement algorithm can usually guarantee the lowest page fault rate. However, since people currently cannot predict which page among the several pages of a process's memory will no longer be accessed for the longest time in the future, this algorithm cannot be implemented, but can use this algorithm to evaluate Other algorithms. Examples are given below.


Assume that the system allocates three physical blocks to a process, and consider the following page number reference string:
7, 0, 1, 2 , 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1


When the process is running, first change 7, 0 , 1 three pages are loaded into memory. Later, when the process wants to access page 2, will generate a page fault interrupt . At this time, the OS will eliminate selected page 7 based on the optimal replacement algorithm. This is because page 0 will be the 5th page visited, page 1 will be the 14th page visited, and page 7 will only need to be loaded on the 18th page visit. The next time page 0 is accessed, there is no need to generate a page fault interrupt because it is already in memory. When the process accesses page 3, it will cause page 1 to be eliminated; because, among the three existing pages 1, 2, and 0, it will be the latest to be accessed in the future. Figure 4-26 shows the permutation graph when using the optimal permutation algorithm. As can be seen from the figure, 6 page replacements occurred using the optimal replacement algorithm.



First in, first out (FIFO) page replacement algorithm


This is the earliest replacement algorithm. This algorithm always eliminates the page that enters the memory first, that is, it selects the page that has resided in the memory for the longest time and eliminates it. This algorithm is not compatible with the actual running rules of the process, because in the process, some pages are frequently accessed, and the FIFO algorithm cannot guarantee that these pages will not be eliminated.

We still use the above example, but use the FIFO algorithm for page replacement (as shown below). When the process accesses page 2 for the first time, page 7 will be swapped out because it is the first to be transferred into memory; when it accesses page 3 for the first time, page 0 will be swapped out because it is in Among the three existing pages 2, 0, and 1, it is the oldest page. As can be seen from Figure 4-27, when using the FIFO algorithm, 12 page replacements are performed, which is exactly twice as many as the optimal replacement algorithm.

Note: When 3 is replaced into the memory for the first time, it is replaced by 0 instead of 1 (although 0 has just been accessed before 3, the 0 in the memory is still Memory pages arriving earlier than 1)






Least recently used (LRU) replacement algorithm



The most recently unused (LRU) page replacement algorithm makes decisions based on the usage of the page after it is transferred into the memory. The LRU replacement algorithm selects the most recently unused pages and eliminates them. This algorithm gives each page a visit field, which is used to record the time t that has elapsed since a page was last visited. When a page needs to be eliminated, the existing page is selected The page with the largest t value, that is, the page that has not been used for the longest time, will be eliminated.

The result of page replacement using the LRU algorithm in the above example is shown in the figure. When the process accesses page 2 for the first time, page 7 is replaced because it has not been accessed for the longest time. When the process accesses page 3 for the first time, page 1 becomes the most recently unused page, so it is swapped out. The optimal replacement algorithm is based on the "backward-looking" perspective, that is, it is based on the future usage of each page; while the LRU algorithm is "forward-looking", that is, based on the previous usage of each page. There is no necessary connection between the past and future direction of the page.













This article was collected and modified by Cout_Sev

From "Computer Operating System (Third Edition)" (Xidian University Press),

Please indicate the source when reprinting.

Thank you!

Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
What are self-closing tags? Give an example.What are self-closing tags? Give an example.Apr 27, 2025 am 12:04 AM

Self-closingtagsinHTMLandXMLaretagsthatclosethemselveswithoutneedingaseparateclosingtag,simplifyingmarkupstructureandenhancingcodingefficiency.1)TheyareessentialinXMLforelementswithoutcontent,ensuringwell-formeddocuments.2)InHTML5,usageisflexiblebutr

Beyond HTML: Essential Technologies for Web DevelopmentBeyond HTML: Essential Technologies for Web DevelopmentApr 26, 2025 am 12:04 AM

To build a website with powerful functions and good user experience, HTML alone is not enough. The following technology is also required: JavaScript gives web page dynamic and interactiveness, and real-time changes are achieved by operating DOM. CSS is responsible for the style and layout of the web page to improve aesthetics and user experience. Modern frameworks and libraries such as React, Vue.js and Angular improve development efficiency and code organization structure.

What are boolean attributes in HTML? Give some examples.What are boolean attributes in HTML? Give some examples.Apr 25, 2025 am 12:01 AM

Boolean attributes are special attributes in HTML that are activated without a value. 1. The Boolean attribute controls the behavior of the element by whether it exists or not, such as disabled disable the input box. 2.Their working principle is to change element behavior according to the existence of attributes when the browser parses. 3. The basic usage is to directly add attributes, and the advanced usage can be dynamically controlled through JavaScript. 4. Common mistakes are mistakenly thinking that values ​​need to be set, and the correct writing method should be concise. 5. The best practice is to keep the code concise and use Boolean properties reasonably to optimize web page performance and user experience.

How can you validate your HTML code?How can you validate your HTML code?Apr 24, 2025 am 12:04 AM

HTML code can be cleaner with online validators, integrated tools and automated processes. 1) Use W3CMarkupValidationService to verify HTML code online. 2) Install and configure HTMLHint extension in VisualStudioCode for real-time verification. 3) Use HTMLTidy to automatically verify and clean HTML files in the construction process.

HTML vs. CSS and JavaScript: Comparing Web TechnologiesHTML vs. CSS and JavaScript: Comparing Web TechnologiesApr 23, 2025 am 12:05 AM

HTML, CSS and JavaScript are the core technologies for building modern web pages: 1. HTML defines the web page structure, 2. CSS is responsible for the appearance of the web page, 3. JavaScript provides web page dynamics and interactivity, and they work together to create a website with a good user experience.

HTML as a Markup Language: Its Function and PurposeHTML as a Markup Language: Its Function and PurposeApr 22, 2025 am 12:02 AM

The function of HTML is to define the structure and content of a web page, and its purpose is to provide a standardized way to display information. 1) HTML organizes various parts of the web page through tags and attributes, such as titles and paragraphs. 2) It supports the separation of content and performance and improves maintenance efficiency. 3) HTML is extensible, allowing custom tags to enhance SEO.

The Future of HTML, CSS, and JavaScript: Web Development TrendsThe Future of HTML, CSS, and JavaScript: Web Development TrendsApr 19, 2025 am 12:02 AM

The future trends of HTML are semantics and web components, the future trends of CSS are CSS-in-JS and CSSHoudini, and the future trends of JavaScript are WebAssembly and Serverless. 1. HTML semantics improve accessibility and SEO effects, and Web components improve development efficiency, but attention should be paid to browser compatibility. 2. CSS-in-JS enhances style management flexibility but may increase file size. CSSHoudini allows direct operation of CSS rendering. 3.WebAssembly optimizes browser application performance but has a steep learning curve, and Serverless simplifies development but requires optimization of cold start problems.

HTML: The Structure, CSS: The Style, JavaScript: The BehaviorHTML: The Structure, CSS: The Style, JavaScript: The BehaviorApr 18, 2025 am 12:09 AM

The roles of HTML, CSS and JavaScript in web development are: 1. HTML defines the web page structure, 2. CSS controls the web page style, and 3. JavaScript adds dynamic behavior. Together, they build the framework, aesthetics and interactivity of modern websites.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Dreamweaver Mac version

Dreamweaver Mac version

Visual web development tools

SecLists

SecLists

SecLists is the ultimate security tester's companion. It is a collection of various types of lists that are frequently used during security assessments, all in one place. SecLists helps make security testing more efficient and productive by conveniently providing all the lists a security tester might need. List types include usernames, passwords, URLs, fuzzing payloads, sensitive data patterns, web shells, and more. The tester can simply pull this repository onto a new test machine and he will have access to every type of list he needs.

mPDF

mPDF

mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),

SublimeText3 English version

SublimeText3 English version

Recommended: Win version, supports code prompts!

VSCode Windows 64-bit Download

VSCode Windows 64-bit Download

A free and powerful IDE editor launched by Microsoft