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

Operating system memory management

Memory management includes memory management and virtual memory management.

Memory management includes concepts such as program loading, exchange technology, continuous allocation management and discontinuous allocation management (paging, segmentation, segment page).

Virtual memory management includes virtual memory concept, request paging management, page replacement algorithm, page allocation strategy and working set.

Let's first take a look at what memory is:

Memory is an important part of computer system, only programs in memory can be executed by CPU, and the data and program running space needed by CPU are obtained from memory, so the performance of memory directly affects the performance of our computer.

When it comes to memory, we can talk about the classification of memory:

According to functional allocation, memory can be divided into cache memory (cache), main memory (memory), and external memory (external memory):

Cache memory (cache): cache is divided into first-level cache and second-level cache. The first-level cache is the memory located inside the CPU, which is responsible for storing and transmitting the required data and instructions to the CPU. The second-level cache is located between the CPU and the main memory (DRAM). The role of the second level is to store the data that need to be used in CPU processing and cannot be stored by the first-level cache. When CPU reads data, it first looks for it in the first-level cache, then looks for it in the second-level cache, and sometimes needs to find it in the third-level cache. What they have in common is that reading speed is slower than CPU and faster than memory, memory capacity is small, and the price is high. The emergence of cache is mainly to solve the contradiction between CPU operation speed and memory read and write speed, because CPU operation speed is much faster than memory read and write speed, which will make CPU spend a long time waiting for data to arrive or write data to memory.

Main memory (memory): the running memory of our mobile phone or computer is the main memory. When the program is running, it will exchange the data in the external memory into the main memory. The main memory stores a large amount of data that may be needed when CPU is running. It is characterized by faster reading and writing speed and smaller size. It is generally the size of 4G-8G.

External memory (external memory): external memory is what we often call hard disk, which is responsible for storing system programs and large data files and databases, characterized by large capacity and low speed.

According to the type of memory, we can be divided into the following categories:

RAM

RAM (random access memory, random access memory). The contents of the memory unit can be taken out or stored at will, and the speed of access is independent of the location of the memory unit. This kind of memory will lose its storage content when the power is off, so it is mainly used to store programs used for a short time. According to the different storage information, random access memory is divided into static random access memory (Static RAM,SRAM) and dynamic random access memory (Dynamic RAM,DRAM).

SRAMS

RAM (Static RAM, static random access memory), does not need to refresh the circuit, data will not be lost, and is generally not column address reuse. But its integration is relatively low, so it is not suitable to do a large amount of memory. It is generally used in the processor cache.

SRAM is actually a very important memory, which has a wide range of uses. SRAM is very fast and maintains data integrity during fast reads and refreshes. SRAM uses bistable circuit to store data. So the circuit structure of SRAM is very complex. It is much more expensive to make SRAM of the same capacity than DRAM. It is precisely because of this that its development is limited. Therefore, currently, SRAM is basically only used for first-level cache within CPU and built-in second-level cache. Only a small number of network servers and routers can use SRAM.

DRAM

Dynamic RAM, dynamic random access memory, refreshes the data at regular intervals in order to save the data. And row and column addresses are reused, and many have page mode. SDRAM is one of them.

SDRAM

SDRAM (Synchronous DRAM, synchronous dynamic random access memory), that is, the reading and writing of data needs clock to synchronize. The memory cells are not arranged linearly, but are paginated.

The capacity of DRAM and SDRAM is larger than that of SRAM due to the problem of implementation process. But the reading and writing speed is not as fast as SRAM.

Most embedded products use SDRAM in their memory. Computer memory is also used in this kind of RAM, called DDR SDRAM, its integration is very high, because it is dynamic, so there must be refresh circuit, every once in a while must refresh data.

ROM

Read-Only Memory, the general name of read-only memory.

In the early days of the development of microcomputers, BIOS was stored in ROM (Read Only Memory). The internal data of ROM is recorded in a special way in the factory during the manufacturing process of ROM, and the contents can only be read and not changed. Once burned, the user can only verify whether the written data is correct and cannot make any further changes. If you find any errors in the information, you have no choice but to abandon it and order a new copy. ROM is produced on the production line, and because of its high cost, it is only used in large quantities of applications.

PROM

Programmable read-only memory can only be written once, but it has to be scrapped if it is written wrong. now it is rarely used, as if this kind of memory is used in the relatively low-cost OPT single-chip microcomputer.

EPROM

EPROM (Erasable Programmable ROM, erasable programmable ROM) chip can be erased and written repeatedly, which solves the disadvantage that PROM chip can only write once.

EPROM chip has a very obvious feature, in its front of the ceramic package, there is a glass window, through which you can see its internal integrated circuit, ultraviolet light through the hole to illuminate the internal chip can erase its data, to complete the chip erase operation to use EPROM eraser.

EEPROMEEPROM (Electrically Erasable Programmable ROM, electrically erasable programmable read-only memory) is a memory chip that does not lose data after power-off. EEPROM is a user-modifiable read-only memory that can be erased and reprogrammed (rewritten) by a higher-than-normal voltage, that is, existing information can be erased and reprogrammed on a computer or on a special device. Unlike the EPROM chip, the EEPROM can be modified without being removed from the computer. It is a more commonly used memory, such as the EEPROM of the 24CXX series.

In an EEPROM, when the computer is in use, it can be reprogrammed frequently, and the life of EEPROM is a very important design consideration.

Flash memory (Flash)

Flash memory (FLASH) is a kind of non-volatile memory, that is, power-off data will not be lost. Because flash memory does not rewrite data in bytes like RAM (random access memory), it cannot replace RAM.

Flash memory card (Flash Card) is a memory that uses flash memory (Flash Memory) technology to store electronic information. It is generally used as a storage medium in digital cameras, PDAs, MP3 and other small digital products, so it is small and compact, like a card, so it is called flash memory card. According to different manufacturers and different applications, flash memory cards probably include USB disk, SmartMedia (SM card), Compact Flash (CF card), MultiMediaCard (MMC card), Secure Digital (SD card), Memory Stick (memory stick), XD-Picture Card (XD card) and micro hard disk (MICRODRIVE). Although these flash memory cards have different appearance and specifications, their technical principles are all the same.

Both NAND FLASH and NOR FLASH are non-volatile flash memories that are widely used today.

The execution process of the program

The executor loads the program and data into memory. Changing a user's source program into a program that can be executed in memory usually requires the following steps:

Compilation: the compiler compiles the user's source code into several target modules. Linking: a set of compiled target modules and required library functions are linked together by the linker to form a complete loading module. Load: the load module is loaded into memory by the loader.

The links to the program are divided into the following categories:

Static linking: the program links each module and the library functions they need into executable files before execution. Dynamic linking at load time: the program gets a set of target modules after compilation, which are linked together when loading memory. Run-time dynamic linking: the program is discrete before running, linking the modules needed to run together at run time.

The loading of programs is divided into the following categories:

Absolute loading: at compile time, if you know that the program will reside somewhere in memory, the compiler will produce object code with an absolute address. The absolute loader loads the program and data into memory according to the address in the load module. Because the logical address in the program is exactly the same as the actual memory address, there is no need to modify the address of the program and data. Relocatable loading: in a multiprogramming environment, the starting address of multiple target modules usually starts from 0, and other addresses in the program are relative to the starting address, so relocatable loading should be used. According to the current situation of the memory, load the module into the appropriate location of the memory. The process of modifying instructions and data in the target program during loading is called relocation, and address conversion is usually completed at one time during loading, so it is also called static relocation. The characteristic of static relocation is that when a job is loaded into memory, all the required memory space must be allocated, and if there is not enough memory, the job cannot be loaded. In addition, once the job is in memory, it cannot be moved in memory throughout the run, nor can it apply for memory space. Dynamic runtime loading, also known as dynamic relocation: if a program moves in memory, it needs to be loaded dynamically. After loading the loading module into memory, the loader does not immediately convert the relative address in the loaded module to an absolute address, but defers this address translation until the program is really about to be executed. Therefore, all addresses loaded into memory are relative addresses. This approach requires the support of a relocation register. The characteristic of dynamic relocation is that the program can be allocated to discontinuous storage areas; before the program runs, only part of its code can be loaded to run, and then during the program running, dynamically apply for memory allocation as needed; to facilitate the sharing of program segments, you can provide users with an address space that is much larger than the storage space.

System partition

Memory is divided into two areas, one is used to store the operating system, the other is used to store user processes, when the process is called into memory, we need to allocate a piece of memory space for it, here we use continuous memory allocation, a process is stored in a continuous section of memory space.

Memory protection

Memory protection is to prevent the user process from affecting the operating system or the user process affecting other processes. The operating system realizes this protection by using the relocation register and the boundary address register. The relocation register contains the lowest physical address. The boundary address register contains the lowest logical address, and the logical address of each process must be smaller than the boundary address register. The memory management unit dynamically compares the logical address with the boundary address, and if it does not cross the boundary, then add the address value in the relocation register to find the physical address, and then send it to the memory unit.

Continuous memory allocation management

In order to load the program into memory, it must be allocated a certain amount of memory space. Continuous allocation is the earliest memory allocation method, which allocates a continuous memory space to user programs, that is, the logical address of the program code or data is adjacent, which is reflected in the adjacency of the physical address when the memory space is allocated. Continuous allocation can be divided into four categories: single continuous, fixed partition allocation, dynamic partition allocation and relocatable partition allocation (compact) algorithm.

Single continuous distribution. At this time, the memory is divided into the system area and the user area, the system area is only allocated to the operating system, usually in the low address part; the user area is provided for users. There is only one program in memory and there is no need for memory protection. There are no external fragments but internal fragments, and the memory is inefficient. Fixed partition allocation. The memory space is divided into several fixed-size areas, and each partition can only be loaded into one job. When there is a free partition, you can select jobs of the appropriate size from the backup job queue of external memory to load the area. It is divided into (partition size is equal and partition size is not equal) there are no external fragments but there are internal fragments (there is a waste of space inside the partition), and memory efficiency is inefficient, but there can be multiprogramming, which is the simplest memory allocation method for the concurrent execution of multiprograms. Dynamic partition allocation. It is also known as variable partition allocation, which does not partition memory in advance, but dynamically establishes partitions according to the size of the process when the process loads memory, and makes the size of the partition exactly meet the needs of the process, and the number and size of its partitions are variable. But with the passage of time, it is easy to produce external fragmentation, which refers to the dynamic partition allocation algorithm in which the storage space outside the partition is wasted based on sequential search: the first adaptation algorithm, in which free partitions are linked by increasing addresses. When allocating memory, look for it sequentially and find the first free partition of the required size, which is usually the fastest, best and simplest. Http://www.daiqiyang.com optimal adaptation algorithm, free partition with increasing capacity to form a partition chain, to find the first free partition to meet the requirements, in fact, the new energy is not good, because each optimal allocation usually leaves very small blocks of memory that are difficult to use, resulting in external fragments. The worst adaptation algorithm, also known as the maximum adaptation algorithm, free partitions form a partition chain with decreasing capacity, and find the first free partition that meets the requirements, that is, the performance of the largest partition is poor. because the algorithm overhead is also a part of the proximity adaptation algorithm that needs to be considered, also known as the loop first adaptation algorithm, which evolved from the first adaptation algorithm, the difference is that It has poor performance to continue searching from the location where the last search ended.

Segmentation and paging mechanism

To understand segmentation and paging, we first need to know why segmentation and paging appear.

First of all, we need to know that segmentation and paging are for better management of computer resources-memory.

Before the segmentation technology comes out, the program always looks for a continuous address space from memory before it runs. For example, if our program A needs 10m, then it is necessary to find 10m address space from the memory space, and then load An into it. If no continuous space is found, it will not be allocated.

From this we can see the shortcomings of the previous memory allocation.

The address space is not isolated. If our two programs, An and B, are stored in the memory space of 0x000001~0x0000999 and B in the space of 0X0001000~0x0001100, then if we miswrite the operation address 0x0000500 of An as 0x0001050, then we not only do not implement the correct operation on A, but also affect the execution of program B. The uncertainty of the program address, because we all operate on the memory address directly, so our program needs to write the address of a certain memory that we want to operate on, but if we want to 0x0000001000 the address we want to operate, we have to write the address we want to operate on 0x0000001000, but the problem is that the address of memory when our program runs may be different at different times. For example, for the first time, our address in memory may be 0x0000000001~0x00000100000. Then we may have no problem with the first operation, but the second run may change his address in memory to 0x000000100000~0x00000110000, so the second run is the address we want to operate in the memory occupied by the basic program, and we may mismanipulate the data of other programs. Memory utilization is low. If our memory size is 70m, we have three A B C programs that continuously occupy 20m 10m 30m address space in memory. When our B is replaced, there is 10m memory space between An and C, and then we have a 11m program D that wants to load memory, and then it looks for a 11m contiguous address space from memory, and then I find two 10m address spaces. But they are not contiguous, so the program cannot be loaded into memory and can only be loaded until An or C is finished, so the 20m free memory address is not used.

In order to solve these problems, people went to find a way to solve it, so the segmentation technology came out:

In order to realize the segmentation technology, people introduce the concept of virtual address space, what is the virtual address space, that is, this space does not really exist, but a concept that we introduce in order to better operate the physical address. to put it simply, before our program runs, its operations are all virtual addresses. For example, the virtual address space of program An is 0x00000100~0x100000200. At this time, we not only need a continuous physical memory to store A, but also need to map the virtual address of A to the physical address space. Maybe the virtual address space of An is mapped from 0x00000100~0x100000200 to the physical address space 0x00000000~0x00000100.

So what are the segments?

The segmentation mechanism is to organize virtual memory into memory units called segments with variable length, and manage these segments through a segment table. Each segment defines a set of logical information, and each program can have multiple segments, such as data segments, code segments, etc., each segment is a continuous address space, and the length of each segment is determined by the size of the program, so the length of each segment is different, so the address space of each segment is two-dimensional. It consists of the first address and the length of the segment.

What is the function of segmentation?

Sharing and protection of segments: here we talk about the protection mechanism of segments. The protection mechanism of segments is divided into cross-boundary checking and permission checking. Cross-boundary checking is that the segment table information is stored in the segment table register, including the starting address of the segment and the length of the segment. during storage access, first compare the segment number of the logical address space with the length of the segment table, if the segment number is equal to or greater than the length of the segment table. An address cross-boundary interrupt signal will be sent, and then it will be checked whether the address in the segment is greater than the length of the segment, and if it is greater than the length of the segment, an out-of-boundary interrupt signal will be generated to ensure that each process can only run in its own address space. Permission check is that in each table item of the segment table, the 'access control' field is set to specify the access method to the segment, which is usually read-only, execute-only, read / write. The problem of the influence of one program on other programs can be solved through segment protection and sharing.

Segment address translation mechanism: segment management can provide logical address to physical address translation, logical address to physical address through the address mapping table, so only the virtual address has not changed, then we do not need to care about the physical address of the program in memory, so through the segment address mapping mechanism can solve problem 2.

But our problem 3 is still unsolved, and the utilization of memory is still not solved, so we lead to paging management.

Paging management divides the main memory space into equal and fixed blocks, and the size of the block is small. as the basic unit of main memory, the page table stores the basic information of these pages, and each process corresponds to a page table. (the block in the process is called a page, the block in main memory is called a page frame, and the block in external memory is called a block. When executing, the process applies for a block to main memory, resulting in an one-to-one correspondence between the page and the page frame.) as shown in the figure:

How to use the paging mechanism to solve the external fragmentation? we use the paging unit to map a set of discontinuous free page frames to contiguous linear addresses, so that they are physically discontinuous but logically continuous. This is to effectively solve the problem of external fragmentation.

In linux, the famous partner algorithm is used to solve the external fragmentation problem. All free page frames are grouped into 11 block linked lists, each of which contains a block linked list of size 1, 2, 4, 4, 8, 16, 64, 124, 256, and 512, respectively. The maximum request for 1024 page frames corresponds to a contiguous RAM of 4MB size (each page size is 4KB), and the physical address of the first page frame of each block is an integral multiple of the block size, for example, a block of 16 page frames with a starting address of 162 * 2 ^ 12.

Let's use an example to illustrate how the partner algorithm works. Suppose you want to request a 1MB with 256 page frames. The algorithm steps are as follows:

Check the linked list of 256 page frames to see if there is a free fast, if not, look for the next larger block, and if so, the request is satisfied.

Check if there is a free block in the linked list of 512 page frames, and if so, divide the free blocks of the 512 page frames into two parts, the first to satisfy the request and the second to link to the linked list of 256 page frames. If there is no free block, continue to look for the next larger block. As shown in the figure:

The inverse process of the above process is the release process of the page frame block and the origin of the name of the algorithm. The kernel tries to merge a pair of idle partner blocks of size B into a single 2B block, and the two blocks that meet the following conditions are called partners:

Both blocks have the same size http://www.daiqiyang.com

Their physical addresses are consecutive.

The physical address of the first page frame of the first block is 2 B 2 ^ 12.

The algorithm is recursive, and if it successfully merges B, it attempts to merge 2B to try again to form a larger block.

There is a difference between segmentation and paging:

1. The paging mechanism uses fixed-size blocks of memory, while segmentation management uses variable-size blocks to manage memory.

2. Paging using fixed-size blocks is more suitable for managing physical memory, and segmentation mechanism using variable-size blocks is more suitable for dealing with logical partitions of complex systems.

The segment table is stored in the linear address space, while the page table is stored in the physical address space.

4, the paging job address space is one-dimensional, that is, a single linear space, the programmer only needs to use a memory character (hexadecimal representation of the linear address) to represent an address.

The segmented job address space is two-dimensional. When identifying an address, programmers need to give not only the segment name (such as data segment, code segment and stack segment, etc.), but also the address within the segment.

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.