Operating System Study Notes (4) Save Paging Management Method

Posted on 2021-12-05 Edited on 2024-11-19 In OS Waline:

After several mornings of fighting, I finally introduced the sentence of paging memory management to read it clearly, and quickly summarized it.

In fact, there are many knowledge points of memory management, such as why memory management, paging, segmentation, fast table, etc. The reason why paging management summary is singled out is because it is the foundation and the most difficult for me to understand.

Basic concept understanding

Word, byte, bit

In a computer, a bit is called a bit, abbreviated as b, which represents a 0 or a 1, and then 8 bits are called a byte (Byte), abbreviated as B, and a word is made up of two bytes

What does the address length represent?

We often say that 32-bit operating systems and 64-bit operating systems refer to the length of the address, which is the root number of the address bus, which determines the maximum range of system addressing, such as 32-bit systems, the addressing range of memory is from 0 to 2 to the 32nd power

What is addressing in bytes

The 32-bit address length mentioned above can represent 32 addresses from 0 to 2, but the Memory Space represented by an address can be one bit or one byte, that is to say, whether we need to read memory data bit by bit, or read memory with an integer multiple of bytes every time. If it is the latter, it is in byte bit addressing units.

Several concepts of paging storage

Page and page size

The block in the process is called ** page (Page) **, and the block in memory is called ** page frame (Page Frame, or page frame) **. External memory is also divided in the same unit, directly called block (Block). The process needs to apply for main memory space when executing, that is, to allocate available page frames in main memory for each page, which results in a one-to-one correspondence between pages and page frames.

In order to facilitate address translation, the page size should be an integer power of 2. At the same time, the page size should be moderate. If the page is too small, the number of pages in the process will be too large, the page table will be too long, taking up a lot of memory, and it will also increase the overhead of hardware address translation and reduce the efficiency of page swapping in/out; if the page is too large, it will increase the fragmentation in the page and reduce the utilization rate of memory.

Address structure

The address structure is divided into two parts, the former part is the page number P, the latter part is the in-page offset W, the address length is 32 bits, if 0-11 bits are the in-page address, then the size of each page is 4KB, that is, 2 The 12th power B (note that this is 4KB in bytes); 12-32 bits are the page number, and the address space allows up to 2 to the 20th power pages

Page table

In order to facilitate the physical block corresponding to each page in each process in memory, the system establishes a page table for each process, which records the physical block number corresponding to the page in memory, and the page table is generally stored in memory.

Page table is composed of page table entries, beginners easy to confuse the page table entry and address structure, both of which are composed of two parts, and the first part is the page number, but the second part of the page table entry is the page number corresponding to the physical address block number, and the second part of the address structure is the offset in the physical block.

The second part of the page table entry the second part of the concatenated address is the real physical address.

** The address structure is divided into two parts, which is true that each occupies a certain length, but the content of the page table entry is only the physical block number **

Basic address translation mechanism

The task of the address translation mechanism is to translate logical addresses into physical addresses in memory. Address translation is achieved with the help of page tables.

Set a page table register (PTR) in the system to store the starting address F and page table length M of the page table in memory.

When the process is not executed, the page table start address and page table length are stored in the process control block. When the process is executed, the page table start address and length are stored in the register.

Let the page size be L, and the process from logical address A to physical address E is as follows:

Calculate page number P = A/L, and in-page offset W = A% L
Compare the relationship between page number P and page table length M. If P > = M, an out-of-bounds interrupt will be generated, otherwise continue execution
The page table entry address corresponding to the page number P in the page table = F + P * page table entry length, and then extract the content b of the page table entry, that is, the physical block number. (Pay attention to distinguish between the page table length and the page table entry length. The page table length refers to how many pages are in total, and the page table entry length refers to how much space the page address occupies, which is the address length of the physical block number)
E = b * L + W

Page management only need to give an integer can be determined corresponding to the physical address, because the page size L is determined, so the page management address space is one-dimensional.

How to determine the size of page table entries

This paragraph is the most difficult to understand, understand this paragraph, you can basically understand the page management.

The function of the page table entry is to find the position of the page in memory. Taking the 32-bit logical address space, the byte addressing unit, and a page of 4KB as an example, the address space is a total of (2 to the power of 32 B/4KB) = 2 20 Pages to the power = 1M pages, you need (the logarithm of 1M at the bottom of 2, that is, 20) bits to accommodate so many pages, that is to say, the length of the ** physical block number ** should be at least 20, this 20 refers to the address length, which actually requires 20 b to store in the computer, but because we are based on If the byte is the addressing unit, and one byte is equal to 8 b, then the length of our physical block number should be greater than or equal to an integer of 20/8, that is, at least 3B (24 b, that is, the length of the physical block number is 24).).

Of course, you can also choose a larger page table entry to make a page just enough to accommodate an integer number of page table entries, so as to facilitate storage (such as taking 4B, a page size is 4KB, just enough to fit 1K page table entries).

Another point to note is that the above discussion does not mention the physical address length. The default is that the logical address length and the physical address length are the same, but in fact they may not be the same at all.

For example, the logical address is 32 bits, the upper 20 bits are the block number, the lower 12 bits are the offset, the length of the page table entry, that is, the length of the physical block number may be 10, then the physical address length may be 10 + 12 = 22.

Two topics

The first one.

Page storage management allows users to have 32 pages of programming space (1KB per page) and 16KB of main storage. If a user program is 10 pages long and the page table is as follows at a certain time:
Logical page number, physical block number
0 8
1 7
2 4
3 10

The address 0AC5H, what is the corresponding physical address.

The page size is 1KB, so the lower 10 bits of the logical address are the in-page offset address;
The user address space is 32 pages, that is, the top 5 digits are the page number;
The main memory is 16 pages, that is, the high 4 bits of the physical address are the physical block number;

0AC5H binary is 000101011000101, the page number is 00010, that is, 2, the corresponding physical block number is 4, that is, 0010 (because the physical block number is 4 bits), then the actual physical address is 01001011000101.

The second one.

A host main memory is addressed in bytes, both logical and physical addresses are 32 bits, and the page table entry size is 4B.

The upper 20 bits of the logical address are the page number, and the lower 12 bits are the in-page offset

What is the page size in bytes? How many bytes does the page table occupy at most?

Because the in-page offset length is 12 bits, the page size is 2 to the 12th power B, which is 4KB.

The length of the page number is 20, then it can represent 2 to the 20th power pages, the maximum length of the page table is 2 to the 20th power, and the size of a page table entry is 4B, that is, the maximum page table is 2 to the 20th power * 4B.

The physical address length should theoretically be the physical block number length + in-page offset length = page table entry size + offset length = 4B + 12b = 32b + 12b = 44b, that is, 44 bits, but the actual physical address is It is 32 bits, that is to say, the high 44-32 bits are all 0, which is invalid.