π Do your best and obey the destiny. I am a postgraduate student in Southeast University and a summer intern in Java background development in Ctrip. I love fitness and basketball, and I am willing to share what I have seen and gained related to technology. I follow the public account @flying Veal and get the update of the article as soon as possible
π This article has been included in the “CS-Wiki” Gitee official recommended project, has accumulated 1.7K + STAR, is committed to creating a perfect back-end knowledge system, in the road of technology to avoid detours, welcome friends to come to exchange and study
π If you do not have a good project, you can refer to a project I wrote “Open source community system Echo” Gitee official recommended project, so far has accumulated 800+ star, SpringBoot + MyBatis + Redis + Kafka + Elasticsearch + Spring Security +… And provide detailed development documents and supporting tutorials. Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo
Overview of memory management
To summarize what memory management is all about, here’s an excerpt from Modern Operating Systems, 3rd Edition:
The task of memory management is to manage memory efficiently by keeping track of which memory is being used correctly and which memory is free, allocating memory to processes when they need it, and freeing it when they run out.
As we all know, today’s computers are based on von Reumann stored program computers, programs and data need to be stored in memory for operation and use.
One of the important objectives of designing operating system is to improve the utilization of computer resources, and with the popularity of multi-core CPU, multi-channel programming technology becomes popular. Therefore, memory space must be properly managed so that as many processes/jobs can be placed in memory at the same time to improve CPU utilization.
In layman’s terms, memory management studies nothing more than the following three aspects:
- Take the Fetch
- Put a Placement
- Replace the Replacement
Fetching is the study of which process (or parts of a process) should be called from external memory (disk) into memory.
Putting studies how and where processes (or parts of processes) that are “fetched” from external memory (disk) are placed in memory.
Obviously, “dump” is the foundation of memory management, and the current “dump” techniques can be divided into two categories:
1) One is continuous allocation, that is, running programs and data must be placed in a contiguous space of memory.
Continuous allocation management includes single continuous allocation, fixed partition allocation, and dynamic partition allocation.
2) The other type is discontinuous allocation, that is, running programs and data can be placed in multiple non-contiguous blocks of memory.
Discontinuous allocation management includes basic paging management, basic segment management and basic segment page management.
If there were only “fetch” and “drop” operations, what would happen?
With the increase of user program functions, the memory space required by the process becomes larger and larger. The process space can easily exceed the actual size of physical memory, resulting in the process cannot run.
Therefore, in order to solve the problem of insufficient memory and alleviate the contradiction between large programs and small memory, it is imperative to expand the memory capacity.
We can consider expanding memory capacity from both physical and logical aspects. Physical expansion has no technical content. What we need to study is how to expand memory capacity logically.
Logical expansion means that the physical memory actually has the same capacity, but it can hold more stuff.
There are three main logical memory augmentation technologies: overlay technology, swap technology, and virtual memory. In fact, the core idea of all these logical augmentation techniques is the same, and I think it can be summed up in one word: “replace” :
A “replace” operation is the opposite of a “fetch” operation, which studies which process (or part of a process) is temporarily moved from memory to external storage (disk) to free up memory space for other processes (or parts of a process).
The first two logical augmentation technologies have become history, virtual memory technology is the current mainstream. So there are a lot of people to the memory management of the content directly divided into physical memory management and virtual memory management, at a glance.
Virtual memory management is based on discontinuous allocation management, including request paging management, request segment management and request segment page management. It’s easy to confuse these concepts with basic paging, basic segmentation, and basic segment-page management mentioned above.
In fact, it is easy to distinguish, remember this sentence OK, from Baidu Encyclopedia:
If there is no page replacement function, it is called basic paging management (or pure paging management), it does not support the implementation of virtual memory, it requires that each job (process) all loaded into memory before it can run.
The whole section of memory management is overviewed above, and this article, the first part of memory management, is only about physical memory management.
Continuous allocation management mode
In fact, in the early operating systems, the use of continuous memory allocation strategy. At that time, the concept of process was not introduced, memory allocation was still in the unit of jobs (equivalent to processes), and continuous allocation was the allocation of jobs to a contiguous memory space.
Continuous allocation management is not the focus of this article, and is not the focus of interviews, but in fact, these methods are useful for any form of memory allocation. Therefore, a brief understanding is necessary.
Continuous allocation management includes single continuous allocation, fixed partition allocation, and dynamic partition allocation.
Single continuous distribution
In the days before operating systems, the entire memory space was, of course, used by a single user. With the advent of operating systems, memory management emerged, and users could no longer monopolize memory resources.
At the time, memory management was very simple, dividing the memory space into two parts: system area (for operating system related data) and user area (for user process related data).
The operating system can be in the low address section or in the high address section, assuming the operating system is in the low address section, as shown in the figure:
The single contiguous allocation is a bit simplistic, with only one user program in memory, and the user program monopolizes the entire user area.
The disadvantages are obvious: it can only be used in single-user, single-task operating systems; Internal fragmentation (” internal fragmentation “if some portion of memory allocated to a process is not used); The memory usage is very low.
Fixed partition allocation
In the 1960s, multi-program support systems emerged. In order to load multiple programs into memory without interfering with each other, the entire user space was considered divided into several fixed-size partitions, and only one job was loaded into each partition. This resulted in one of the earliest and simplest forms of memory management that could run multiple programs.
There are different scenarios for whether these partitions need to be equal in size:
- Equal partition size: lack of flexibility. But it is suitable for a computer to control multiple occasions of the same object (for example, a steel plant has N identical furnaces, you can divide the memory space into N equal areas to store N steelmaking control programs)
- Partition sizes vary: Increased flexibility to meet the needs of processes of different sizes
Unfortunately, although fixed partition allocation supports multiple programs, it still generates internal fragmentation and memory utilization is still low. Therefore, dynamic partition allocation is introduced to improve the utilization of memory space by implementing dynamic partition of user area.
Dynamic partition allocation
Dynamic partition allocation is also called variable partition allocation. This allocation method does not pre-partition memory, but dynamically creates partitions according to the size of the process when loading memory, and makes the partition size exactly fit the needs of the process. Therefore, the size and number of system partitions are variable.
Dynamic partition allocation is complicated and requires special data structures to record memory usage, but I won’t go into the details here.
Discontinuous allocation management mode
It can be seen that continuous memory allocation has the advantages of easy to understand and high access efficiency. However, because it requires jobs (processes) to be placed in a contiguous area of memory, it is easy to have large chunks of contiguous memory that are not available because there is not enough room for jobs or processes. Therefore, a discontinuous allocation strategy is introduced to make full use of memory space resources.
Discontinuous allocation means that jobs (processes) can be placed in multiple non-contiguous blocks of memory.
Discontinuous allocation management includes page management, section management and section page management.
Before reading this paragraph, you need to understand the concept of virtual addresses (logical addresses) versus physical addresses. See this article: None of the addresses you see are real
Basic paging management
The so-called page management, we need to explain what is “page”?
First, the memory space is divided into equal size partitions, and each partition is called a page frame. Each page enclosure has a page enclosure ID (also known as the physical page enclosure ID and memory block ID). The page enclosure ID starts from 0.
The virtual address space of the process is also divided into partitions equal to the size of the page box, and each partition is called a “page” or “page”. Each page also has a number, the “page number” (also known as the virtual page number), which also starts at 0.
The operating system allocates memory space for each process on a page frame basis. Each page of the process is placed in a page box. That is, there is a one-to-one correspondence between the pages of a process and the page frames of memory. Pages do not need to be consecutively stored, can be placed in non-adjacent (discrete) each page box.
For example, in the following image, each page and page frame is 4KB in size. We have 64KB of virtual address space and 32KB of physical memory, so we can get 16 pages and 8 page frames:
As mentioned earlier, the actual execution of the instruction will eventually convert the virtual address to a physical address.
So, how to map virtual address (page) and physical address (page frame) in page management? In other words, how to calculate the physical address from the virtual address?
To do this, the operating system creates a page table for each process, a very important data structure! Page tables are usually stored in process control blocks (PCBS).
A process corresponds to a page table, and each page of a process corresponds to a page entry. Each page entry consists of a page number and a block number (page frame number), which records the mapping between process pages and actual memory blocks.
Mathematically, a page table is a function that takes a virtual page number and results in a physical page frame number.
Two important issues in page management
In any paging system, the following two issues are unavoidable:
- Problem 1: How to ensure that the translation of virtual addresses to physical addresses is fast enough – using fast tables
- Problem 2: How to solve the problem of large virtual address space, the page table will be large (more page table entries, naturally the page table will be large) – using multi-level page table solution
The first problem is that since every access to memory requires a translation from a virtual address to a physical address, it is necessary to perform one or two or more page table accesses per instruction, and the page table exists in memory.
So, since accessing the page table (memory) too many times is a performance bottleneck, why not find a way to make the address map access something much faster than memory instead of memory?
The computer’s designers came up with a solution that went something like this: they set up a small hardware device for the computer that mapped virtual addresses directly to physical addresses without having to access page tables. This device is the Translation Lookaside Buffer (TLB), also known as a fast table.
Why is he fast? Since TLBS are usually built into the CPU’s MMU (memory management unit), this access speed is not in the same league as memory. Page tables in memory are commonly referred to as slow tables.
So, with TLB, can you just give up page tables once and for all?
Of course not.
The TLB contains only a small number of entries. Each entry records information about a page. The table structure is as follows:
In fact, TLB is based on the phenomenon that most programs always make multiple visits to a small number of pages. As a result, only a few page table entries are read repeatedly, while others are rarely accessed.
The TLB stores page entries that are read repeatedly. In other words, the TLB holds a partial copy of the page table.
If the TLB hits, memory access is not required. If there is no target page entry in the TLB, you need to query the page table (slow table) in the memory, obtain the physical page frame address from the page table, and add the page table entry to the TLB.
So the question is, what if the TLB fills up?
When the TLB fills up and needs to register a new page, a page in the fast table will be eliminated according to a certain elimination strategy.
Turning to the second problem, most modern computer systems generally support very large virtual address Spaces, making the page table very large and requiring relatively significant memory space (more page table entries, more page table). If we assume that there is only one page table in the system, even if we are using only a small part of the virtual address space, the entire page table will always reside in memory.
A common way to compress a page table is to use a hierarchical page table.
Take the most common two-level page table as an example, let’s look at the processing idea of multi-level page table:
The page table is pagination and discrete storage, and then establish a page table to record the storage location of each part of the page table, known as “page directory table” (or outer page table, top page table).
If the page table is still long after being divided into two levels, the outer layer page table can be paginated to form a multi-level page table of more than three levels.
Multi-level page table technology not only breaks through the limitation that the page table must be stored continuously, but also can not allocate the corresponding page table space when a large virtual address space is not used, thus saving memory. In addition, multi-level page tables increase the fetch times, so the page entries of the outer page table should be kept in TLB as much as possible to reduce the fetch cost.
Basic section management
Although page management has the characteristics of high utilization of memory space and simple management method, it is not natural for users to divide memory space by page. Users view programs in terms of segments, such as main program segments, subroutine segments, data segments, and so on. If the user requests data protection, the basic unit to be protected is also a paragraph. For example, one paragraph can only be read, another can be executed, etc.
Paging, on the other hand, is entirely possible to put two pieces that are not part of the same paragraph on the same page. Page 4 contains both program segments (executable) and data segments (readable and writable) :
In other words, while page management improves memory utilization, the pages that page management divides are meaningless.
To this end, section management emerged.
A segment system is a system that divides the logical space according to the segments in the user’s job (process). For example, if a user job (process) consists of a main program, two subroutines, a stack, and a piece of data, the user job (process) can be divided into five segments. Obviously, the page is fixed length and the segments are not:
As can be seen from the figure, segments can be stored discontinuously, but the interior of a segment is still continuous.
In addition, like basic paging management, basic segmentation management requires a data structure to record the mapping between virtual and physical addresses, which is the segment table.
Basic section page management
If a segment is large, it may be inconvenient or even impossible to keep the entire segment in memory, hence the idea of paging it.
Support for paging segments, this is the basic idea of segment-page management.
In simple terms, the virtual address space is divided into segments, and then pages within each segment. For example, if the user process is composed of main program, subroutine and data segment, it will be divided by segment and page as shown in the figure:
References
- Operating System – 3rd Edition – Luo Yu
- Modern Operating Systems – 3rd Edition
- “Understanding Computer Systems in Depth – 3rd Edition”
| flying veal π pay close attention to the public, get updates immediately
- I am a postgraduate student in Southeast University and a summer intern in Java background development of Ctrip. I run a public account “Flying Veal” in my spare time, which was opened on 2020/12/29. Focus on sharing computer fundamentals (data structure + algorithm + computer network + database + operating system + Linux), Java technology stack and other related original technology good articles. The purpose of this public account is to let you can quickly grasp the key knowledge, targeted. Pay attention to the public number for the first time to get the article update, we progress together on the way to growth
- And recommend personal maintenance of open source tutorial project: CS-Wiki (Gitee recommended project, has accumulated 1.7K + STAR), committed to creating a perfect back-end knowledge system, in the road of technology to avoid detours, welcome friends to come to exchange learning ~ π
- If you don’t have any outstanding projects, you can refer to a project I wrote “Open source community System Echo” Gitee official recommended project, which has accumulated 800+ star so far. SpringBoot + MyBatis + Redis + Kafka + Elasticsearch + Spring Security +… And provide detailed development documents and supporting tutorials. Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo