Paging storage management, segmented storage management, segmented page storage management, two-level page table

Table of contents:
Paged storage management
Basic address storage mechanism
Address storage mechanism with fast table
two-level page table
Segmented storage management
Segment page management method

Paging storage management (key)

First review, logical address and physical address.
Why introduce paging storage management?
Utilize all discrete pieces under the physical address, that is, they appear to be stored continuously in the logical address, but in fact they are discretely stored corresponding to the physical address.

The concept of pages and pages and blocks

In the logical address, we divide the logical storage space into multiple small strips. We call these multiple small strips pages. In the small strips, we need to store an address composed of several bits. The inside of the strip is called page. Divide the physical address space of the memory into several blocks
In physical addresses, storage does not have to be continuous, either in storage space or storage logic.

The concept of page frames

In the memory, it is also stored in the form of a small strip. The address corresponding to the page is also stored inside this small strip in the memory. The inside of this small strip is called page frame.So, page frame length = page length.

Concepts of page tables and page table entries

We have already understood the concepts of pages and pages in logical addresses. How do we know which page frame number (physical block number) in the physical address corresponding to our page is? We have a table of page corresponding block numbers, which is It is called page table, and each corresponding relationship is called a page table entry. The page table entry stores the page number and physical block number, and the page number does not occupy storage space. Page numbers have a default order and are implicit.

1. One process corresponds to one page table
2. Each page of the process corresponds to a page table entry
3. Each page table entry consists of a "page number" and a "block number"
4. The page table records the mapping relationship between process pages and actual stored memory blocks.

How to calculate physical address using logical address?
Through the logical address, the page and intra-page offset are calculated. The intra-page offset is the specific position of the page in a certain page.
By looking up the table, the corresponding physical block number is obtained.
Physical block number + page offset = physical address

Basic address storage mechanism

A set of hardware mechanisms that implement conversion from logical address to physical address.
Since there is a one-to-one correspondence between the page address and the physical address, no conversion is required. Therefore, the task of the address conversion mechanism is actually just to convert the page number in the logical address into the physical block number in the memory.
Usually a Page Table Register (PTR) is set up in the system to store the starting address F of the page table in memory and the page table length M code>. When the process is not executed, the starting address and page table length are placed in the process control block (PCB). When the process is scheduled, the operating system kernel will place them in the page table register.

Address transformation process

1. Calculate the page number and page offset based on the logical address
2. Legality check of page number (compared with page table length)
3. If the page number is legal, find the corresponding page table entry based on the page table starting address and page number.
4. Obtain the final physical address based on the memory block number and page offset recorded in the page table entry.
5. Access the memory unit corresponding to the physical memory

Number of memory accesses: 2 times, once to query the page table, and once to access the memory after checking.

Example question:
Example: If the page size L is 1K bytes and the memory block number b=8 corresponding to page number 2, convert the logical address A=2500 to the physical address E. Equivalent description: A certain system is addressed by bytes. In the logical address structure, the page offset occupies 10 bits, and the memory block number corresponding to page number 2 is b= 8. Convert logical address A=2500 to physical address E.

Address storage mechanism with fast table

A new basic address storage mechanism, fast table, is introduced to reduce the number of memory accesses and make the address conversion process faster.

Fast table, also known as translation lookaside buffer (TLB), is a cache that accesses much faster than memory (TLB is not memory code>!), used to store a copy of the recently accessed page table entry, which can speed up address transformation. Correspondingly, the page table in memory is often called slow table.

Address transformation process

Number of memory accesses: Fast table hit, only one memory access required
The fast table misses and requires two memory accesses.

1. Calculate the page number and offset within the page
2. Check the legality of the page number
2. Check the quick form. If it hits, you can know the memory block number where the page is stored, and you can proceed directly to step 5; if it misses, proceed to step 4.
4. Look up the page table to find the memory block number where the page is stored, and copy the page table entry to the fast table
5. Obtain the physical address based on the memory block number and page offset
6. Access the target memory unit

Two-level page table

Two-level page table-solve the problems of single-level page table

How to solve the problem of single-level page table? The page table is too large. The page table must be stored continuously and takes up too much space.
Split the original large page table into several small page tables, several small page tables, and then form a page table, called page directory table, by querying the page directory table , find the location of the memory block that stores the small page table

Basic segmented storage management

The address space of the process: According to the program’s own logical relationship, it is divided into several segments. Each segment has a segment name (in low-level languages, programmers use segments (name to program), Each segment is addressed starting from o
Memory allocation rules: Allocate in units of segments. Each segment occupies a continuous space in the memory, but the segments may not be adjacent.

Composition

The logical address structure of the segmented system consists of the segment number (segment name> and the segment address (intra-segment offset>). For example:
The number of digits in the segment number determines the maximum number of segments each process can be divided into
The number of address bits in a segment determines the maximum length of each segment.

Segment table

Similar to page table

Comparison of segmentation and paging management

A page is a physical unit of information. The main purpose of paging is to achieve discrete allocation and improve memory utilization. Paging is only a need for system management and is completely a system behavior. It is invisible to users.

A segment is a logical unit of information. The main purpose of segmentation is to better meet user needs. A segment usually contains a set of information belonging to a logical module. Segments are visible to users, and users need to explicitly give the segment name when programming.

The page size is fixed and determined by the system. The length of the segment is not fixed and depends on the program written by the user.

The address space of the user process of paging is one-dimensional, and the programmer only needs to give a mnemonic to represent an address.
The segmented user process’s address space is two-dimensional. When identifying an address, the programmer must give both the segment name and the address within the segment.

Section page management method

Introduction: Both paging and segmentation have advantages and disadvantages, how to choose the best?

Segment table and page table in segment paging

Divide the address space into several segments according to the logical relationship of the program itself, and then divide each segment into pages of equal size.
Divide the memory space into memory blocks equal to the page size, and the system allocates memory to the process in units of blocks.
Logical address structure: (segment number, page number, offset within page)

The number of memory accesses required to access a logical address

• The first time – look up the segment table, the second time – look up the page table, the third time – access the target unit
• The fast table mechanism can be introduced, and the fast table can be queried using the segment number and page number as keywords to directly find the final target page storage location. After the fast table is introduced, only one memory access is required