Memory management paging and page fault calculation_html/css_WEB-ITnose

1. What is a missing page?

To put it bluntly: Page fault is defined as all memory blocks are initially empty, so the page used for the first time will generate a page fault, that is, if the page number to be entered does not exist in the memory, it will occur. Missing pages. After understanding this, it becomes easier to solve the problem of page missing calculation.

2. First-in, first-out scheduling algorithm (FIFO)

This scheduling algorithm always eliminates the latest page entered into the main memory. This scheduling algorithm is very simple. It arranges the pages into a page number queue in the order in which they are loaded into the main memory. Whenever a page fault is entered, the page that enters the earliest is eliminated.

For example: For example, the page numbers to be accessed in sequence are: 0 1 2 3 2 1 3 2 5 2 3 6 2 1 4 2. Now there are only three main memories available. If FIFO scheduling is used, Please simulate the scheduling process and calculate the number of page fault interrupts?

0 enters, a page fault interrupt occurs (1 time), the page number in the memory at this time: 0
1 enters, a page fault interrupt occurs (1 time), the page number in the memory at this time: 01
2 enters, a page fault interrupt occurs (1 time), the page number in the memory at this time: 012
3 enters, 0 is eliminated, a page fault interrupt occurs (1 time), 3 replaces the position of 0, and the memory Page number in: 12３
2 Enter, there is no page fault interrupt, because page number 2 already exists in the memory, the page number in the memory is still: 12３
1 Enter, page number 1 exists in the memory, no A page missing interrupt occurs. At this time, the page number in the memory is: 12３
３Enter, the same as above, no page missing interrupt occurs, the page number in the memory is: 12３
３Enter, the same as above, no page missing interrupt occurs , the page number in the memory is: 123
5 enters. At this time, the longest time for 312 is: 1, so 5 replaces 1, and a page fault interrupt occurs (1 time). At this time, the page in the memory No.: 2３５
６Enter, there is no page missing interrupt, the page number in the memory: ３３５
６Enter, there is a page missing interrupt (1 time), the eliminated page is No. 2, the page number in the memory is 356
2 Enter, a page missing interrupt occurs (1 time), the eliminated page number is 3, the page number in the memory is 5６62
1 Enter, a page missing interrupt occurs (1 time), the eliminated page number is 5 No., the page number in the memory is 621
4 enters, a page fault interrupt occurs (1 time), the eliminated page number is 6, the page number in the memory is 214
2 enters, no page fault interrupt occurs , the page number in the memory is 214

Therefore, if the first-in-first-out scheduling algorithm is used, a total of 8 page fault interrupts will occur, and the memory simulation situation is as follows:

Enter Time	0	1	2	３	2	1	３	2	５	2	３	６	2	1	４	2
Morning	0	0	0	1	1	1	1	1	2	2	２	３	５	６	2	2
中		1	1	2	2	2	2	2	３	３	３	５	６	2	1	1
Late			２	３	３	３	３	３	５	５	５	６	2	1	４	４
Whether missing page	is	is	is	Yes	Not	No It’s not	It’s	It’s not	It’s not	is	is	Yes	Yes	No

*The red number is the latest page number entered into the memory
For the first-in-first-out simulation process, it is not difficult to find the following characteristics:
1. First If it enters the memory for the first time, there must be a page fault;
2. If there is no page fault, the consecutive columns are the same;
3. The eliminated page is the one that has stayed in the memory the longest;

3. The most recently unused scheduling algorithm (LRU)

The most recently unused scheduling algorithm believes that pages that have been frequently used recently may be accessed soon, so they cannot be called out. On the contrary, if there are pages that have not been visited in the past period, they may not be visited in the near future. Therefore, when you need to load a new page, you should select the page that has not been used for the longest time in the recent period.

Still taking the above example, using LRU scheduling,
First, 0 enters, and the page is missing (1 time). At this time, the page numbers in the memory are in the order of frequency of use: 0
1 Enter, page missing (1 time), the page numbers in the memory are in the order of frequency of use: 01
2 Enter, page is missing (1 time), the page numbers in the memory are in the order of frequency of use: 012
３Enter, page missing (1 time), the longest unused page number is 0, replaced by 3. At this time, the page numbers in the memory are in the order of frequency of use: 12３
2Enter, no page missing, At this time, the page numbers in the memory are in the order of frequency of use: 132
1 Enter, there is no page shortage, the page numbers in the memory are in the order of frequency of use: 321
3 Enter, there is no page shortage, and the memory is at this time The order of page number usage frequency: 213
2 Enter, there is no page missing, the page number usage frequency order in the memory at this time: 1３32
5 Enter, page missing (1 time), the longest unused page The page number is No. 1 and is eliminated. At this time, the order of page number usage frequency in the memory is: 32５
３Enter, there is no page shortage. At this time, the order of page number usage frequency in the memory is: 352
３Enter , there is no page missing. At this time, the page number usage frequency sequence in the memory is: 52３
６Enter, page missing (1 time), at this time the page number usage frequency sequence in the memory is: 2３６
2 Enter, There is no page shortage. At this time, the order of page number usage frequency in the memory: 362
1 enters, page missing (1 time), the page number that has not been used for the longest time is 3, at this time, the order of page number usage frequency in the memory : 621
4 entry, page missing (1 time), the page number that has not been used for the longest time is 6, the order of page number usage frequency in the memory at this time: 214
2 entry, no page missing, the memory at this time The order of page number usage frequency: 1４2

Therefore, using the most recent scheduling algorithm that has not been used for a long time, its number of page misses: 8 times

Its scheduling simulation in memory is as shown in the table below Display:

Use frequency	0	1	2	３	2	1	３	2	５	2	３	６	２	1	４	２
Long time No use	0	0	0	1	1	３	2	1	３	３	５	2	３	６	2	1
中		1	1	2	３	2	1	３	2	５	2	３	６	2	1	４
Recently Used			2	３	2	1	３	2	５	２	３	６	２	1	４	2
Yes Missing page	Yes	Yes	Yes	Yes	No	No 🎜>Not	Not	是	不是	不是	是	不是	Yes	Yes	No

四、小结

　　多拿笔画画～～～