Make progress in English every day

preface

I’ve had a lot of feedback from readers, can I write a graphical operating system?

Since so many readers want to see it, I’ve been frantically revising my knowledge of operating systems.

It is true that operating system is a more difficult subject to study, at least I think much more difficult than computer networking, but I need not tell you how important it is.

The main pain of learning operating systems is that there are too many abstract words or concepts that are hard to understand and easy to discourage.

Even with full of enthusiasm to learn the operating system, but 3 minutes of sleep suddenly hit…

There’s still work to be done, there’s still work to be done, and here comes the much-anticipated “Illustrated Operating System” series.

This article tells you about memory management, memory management is still a relatively important link, understand it, at least for the entire operating system work has a preliminary outline, it is no wonder when the interview often asked memory management.

The job is done.

In this paper, an outline

The body of the

Virtual memory

If you are an electronics related major, you must have worked in the university microcontroller.

Microcontroller is no operating system, so every time to write the code, need to use tools to record the program, so that the program can run.

In addition, the SINGLE-chip CPU is the direct operation of memory “physical address”.

In this case, it is impossible to run two programs simultaneously in memory. If the first program writes a new value at 2000, it will erase everything the second program has stored in the same location, so running both programs at the same time simply won’t work, and both programs will crash immediately.

How does the operating system solve this problem?

The key problem here is that both programs reference absolute physical addresses, which is what we need to avoid most.

We can isolate the addresses used by processes by having the operating system assign a separate set of “virtual addresses” to each process. Everyone can play with their own addresses without interfering with each other. However, the premise is that each process cannot access the physical address. How the virtual address ends up in the physical memory is transparent to the process. The operating system already arranges this.

The middle layer of a process

The operating system provides a mechanism to map the virtual addresses of different processes to the physical addresses of different memory.

If the program wants to access the virtual address, the operating system translates it into a different physical address, so that different processes write different physical addresses, so that there is no conflict.

Thus, there are two concepts of addresses:

  • The memory address our program uses is calledVirtual memory address(Virtual Memory Address)
  • The space address that actually exists in the hardware is calledPhysical memory address(Physical Memory Address).

Virtual memory is introduced into the operating system. Virtual addresses held by processes are converted into physical addresses through the mapping of memory management units (MMUs) in the CPU chip, and then physical addresses are used to access memory, as shown in the following figure:

Virtual address addressing

How does the OPERATING system manage the relationship between virtual and physical addresses?

There are two main ways, respectively, memory segmentation and memory paging, segmentation is relatively early proposed, let’s take a look at memory segmentation.


The memory block

The program is composed of several logical segments, such as code segment, data segment, stack segment, heap segment. Different segments have different attributes. Therefore, these segments are separated by Segmentation.

How do virtual addresses and physical addresses map in segment mode?

The virtual address in segment mechanism consists of two parts, segment selectors and segment offsets.

Memory segmentation – way of addressing
  • The segment selectors are stored in the segment registers. The most important part of the segment selector is the segment number, which is used as the index of the segment table. The segment table stores the base address, segment boundaries, and privilege levels of the segment.

  • The in-segment offset in the virtual address should be between 0 and the segment limit. If the in-segment offset is legal, the segment base address is added to the in-segment offset to get the physical memory address.

The segment mechanism will divide the virtual address of the program into 4 segments. Each segment has an item in the segment table. Find the base address of the segment in this item, plus the offset, and then find the address in the physical memory, as shown in the figure below:

Memory segmentation – Virtual address vs. physical address

If we want to access the virtual address at offset 500 in segment 3, we can calculate the physical address as 7000 + offset 500 = 7500.

The segmented approach is a good solution to the problem that the program itself does not need to care about the specific physical memory location, but it has some disadvantages:

  • The first is memory fragmentation.
  • The second problem is the inefficiency of memory swapping.

Now, why are these two problems?

Let’s start by looking at why fragmentation is a problem.

Let’s look at an example. Assuming 1 gb of physical memory, the user executes multiple programs, where:

  • The game takes up 512MB of memory
  • The browser takes up 128MB of memory
  • Music takes up 256 MB of memory.

At this point, if we close the browser, we have 1024-512-256 = 256MB free memory.

If the 256MB was not contiguous and was split into two 128MB segments, there would be no room to open another 200MB program.

Memory fragmentation problem

There are two problems with memory fragmentation:

  • External memory fragmentation, that is, the creation of multiple discontinuous small physical memory, resulting in new programs cannot be loaded;
  • Internal memory fragmentation, where all of the program’s memory is loaded into physical memory, but some of the program’s memory may not be used very often, which also leads to memory waste.

For the above two types of memory fragmentation problems, the solution will be different.

The solution to the problem of external memory fragmentation is swapping.

The 256MB of memory used by the music program can be written to the hard disk and then read back from the hard disk into memory. But when we read back, we can’t load it back to its original location, but just follow the 512MB memory that has already been used. This creates a contiguous 256MB space so that new 200MB programs can be loaded in.

This memory Swap space, commonly known as Swap space in Linux, is a partition of the hard disk, used for memory and hard disk swaps.

Why does segmentation cause memory swapping to be inefficient?

On a multi-process system, memory fragmentation is very easy to generate in a segmented manner. If memory fragmentation is generated, the memory area has to be re-swap, which can cause performance bottlenecks.

Because hard disk access is much slower than memory, each memory swap requires a large contiguous chunk of memory data to be written to the hard disk.

So, if you swap memory, and you swap a program that takes up a lot of memory, the whole machine will be stuck.

In order to solve the problem of memory fragmentation and low efficiency of memory swapping, memory paging appears.


paging

The advantage of segmentation is that it creates contiguous memory space, but the problem is that there is too much space for fragmentation and swapping.

To solve these problems, it is necessary to figure out a way to reduce memory fragmentation. In addition, when swapping is required, you can solve the problem by having less data that needs to be swapped to write or load from disk. This approach is known as Paging.

Paging is the cutting of the entire virtual and physical memory space into fixed size segments. Such a continuous and fixed size memory space is called a Page. Under Linux, each page is 4KB in size.

Virtual addresses and physical addresses are mapped through the page table, as shown in the following figure:

The memory mapping

The page table is actually stored in the CPU’s memory management unit (MMU), so the CPU can go directly to the MMU to find the physical memory address to actually access.

When the virtual address accessed by the process cannot be found in the page table, the system will generate a page missing exception, enter the system kernel space to allocate physical memory, update the process page table, and finally return to the user space to resume the process running.

How does paging solve the problem of fragmentation and low efficiency of memory swap?

Since the memory space is pre-partitioned, it does not create very small gaps like fragmentation, which is why fragmentation can occur. With paging, memory is freed on a per-page basis, so there is no memory that is too small for the process to use.

If the memory space is insufficient, the operating system will free the “recently unused” memory pages of other running processes, that is, temporarily write them to the hard disk, called Swap Out. When it is needed, it is loaded In again, called a Swap In. Therefore, only a few pages or pages are written to disk at a time, which does not take too much time, and memory swapping is relatively efficient.

In out

Furthermore, paging eliminates the need to load programs into physical memory all at once. We can map pages from virtual memory to physical memory without actually loading the pages into physical memory, but only loading them into physical memory when the program is running and needs instructions and data from the corresponding virtual memory pages.

How are virtual and physical addresses mapped under paging?

Under paging, the virtual address is divided into two parts, the page number and the in-page offset. The page number acts as an index to the page table, which contains the base address of physical memory for each page of the physical page. This base address is combined with the in-page offset to form the physical memory address, as shown in the figure below.

Memory paging addressing

To summarize, there are three steps for a memory address translation:

  • Divide the virtual memory address into page numbers and offsets.
  • Query the corresponding physical page number from the page table according to the page number.
  • Just take the physical page number and add the preceding offset to get the physical memory address.

As an example, pages in virtual memory are mapped to pages in physical memory through a page table, as shown below:

Mapping of virtual pages to physical pages

This may seem innocuous, but in a real operating system, this simple paging is bound to be problematic.

Are there any drawbacks to simple paging?

There is a spatial defect.

Because an operating system can run many processes simultaneously, this does not mean that the page table will be very large.

In a 32-bit environment with a total of 4GB of virtual address space, assuming a page size of 4KB (2^12), this would require approximately 1 million (2^20) pages, with each “page entry” requiring 4 bytes of storage. The entire 4GB mapping would require 4MB of memory to store the page table.

At 4MB, the page table doesn’t look very large. But keep in mind that each process has its own virtual address space, i.e. its own page table.

So, 100 processes would require 400MB of memory to store page tables, which is a lot of memory, let alone in a 64-bit environment.

Multistage page table

To solve the above problem, a solution called multi-level Page Table is needed.

As we saw earlier, in a 32-bit and 4KB environment, a process’s page table would need to hold more than 1 million “page table entries,” and each page entry would take up 4 bytes, which is equivalent to 4MB of space per page table.

We pagination the single-level page table of more than 1 million “page table entries”, divide the page table (first-level page table) into 1024 page tables (second-level page table), and each table (second-level page table) contains 1024 “page table entries”, forming second-level page. As shown below:

The secondary paging

You may ask that mapping 4GB of address space requires 4KB (level 1 page table) + 4MB (level 2 page table) memory, which is more space.

Of course, if all 4GB of virtual addresses are mapped to physical memory, secondary paging takes up more space, but we tend not to allocate that much memory for a single process.

We should actually look at it from a different Angle, remember the ubiquitous principle of locality in the constitution of computers?

Each process has 4 gb virtual address space, and obviously for most applications, the use of space is far from 4 gb, because there are part of the corresponding page table entries are empty, there is no allocation, for assigned page table entries, if there is a certain time recently did not visit the page table, under the condition of the physical memory tension, The operating system paged the page out to hard disk, meaning no physical memory was used.

If secondary paging is used, the primary page table can cover the entire 4GB virtual address space, but if the page table entry of a primary page table is not used, there is no need to create the secondary page table for that page table entry, that is, the secondary page table can be created as needed. To do a simple calculation, assuming that only 20% of the first level page table entries are used, the memory footprint of the page table is only 4KB (first level page table) + 20% * 4MB (second level page table) = 0.804MB. Is this a huge savings compared to 4MB for the single level page table?

So why can’t a non-hierarchical page table save as much memory? From the nature of the page table, the page table stored in memory is responsible for translating virtual addresses into physical addresses. If the virtual address does not have a corresponding page entry in the page table, the computer system will not work. Therefore, the page table must cover the entire virtual address space. A non-hierarchical page table needs more than 1 million page entries to map, while a two-level page only needs 1024 page entries (at this point, the first level page table covers the entire virtual address space, and the second level page table is created as needed).

When we extend two-level paging to multi-level page tables, we find that page tables take up less memory, thanks to the full application of the locality principle.

On 64-bit systems, two levels of paging are definitely not enough, so there are four levels of directories, respectively:

  • Global page directory entry PGD (Page Global Directory);
  • Upper page directory entry PUD (Page Upper Directory);
  • Middle page directory entry PMD (Page Middle Directory);
  • Page entry PTE (Page Table Entry);
Level 4 directory

TLB

Although multi-stage page table solves the problem of space, the conversion of virtual address to physical address requires several more conversion procedures, which obviously reduces the speed of the conversion of the two addresses, that is, brings time overhead.

Programs are local, that is, the execution of the entire program is limited to one part of the program for a period of time. Accordingly, the storage that execution accesses is limited to a memory region.

Locality of the program

We were able to take advantage of this property to store the most frequently accessed page entries on faster hardware, so computer scientists added a special Cache to the CPU chip for the most frequently accessed page entries of the program. This Cache is Translation Lookaside Buffer (TLB), commonly known as page table Cache, address bypass Cache, fast table, etc.

Address translation

In the CPU chip, the Memory Management Unit is encapsulated, which is used to complete address translation and TLB access and interaction.

With TLB, the CPU will look for TLB when addressing, and if it doesn’t find it, it will continue to look for regular page tables.

The TLB hit rate is actually quite high, because there are only a few pages that a program accesses most often.


Segment-page memory management

Memory segmentation and paging are not opposites. they can be used together in the same system, and when combined, they are often referred to as segmented memory management.

Segment-page address space

Segment-page memory management is implemented in the following ways:

  • First, the program is divided into multiple logical sections, which is the previously mentioned segmentation mechanism;
  • Then each section is divided into multiple pages, that is, the continuous space divided by sections, and then divided into fixed size pages;

In this way, the address structure consists of the segment number, the page number within the segment and the page displacement within the page.

The data structure used for segment-page address transformation is a segment table for each program, and a page table is established for each segment. The address in the segment table is the start address of the page table, and the address in the page table is the physical page number of a page, as shown in the figure:

The relationship between segment table, page table and memory in segment-page management

Three memory accesses are required to obtain the physical address in segment page address transformation:

  • Access the segment table for the first time, get the start address of the page table;
  • Access the page table a second time to get the physical page number;
  • For the third time, combine the physical page number with the in-page displacement to get the physical address.

In this way, although the hardware cost and system overhead are increased, the utilization rate of memory is improved.


Linux Memory Management

So how does the Linux operating system manage memory?

To answer that question, we need to look at the history of Intel processors.

Early Intel processors starting with the 80286 used segment memory management. However, it soon became clear that segment memory management without page memory management was not enough, making its X86 family uncompetitive in the market. As a result, paged memory management was implemented in the 80386 shortly after. That is to say, 80386 not only completes and improves the segment memory management from 80286, but also realizes the page memory management.

However, the 80386 page memory management is not designed to bypass the segment memory management, but based on the segment memory management, which means that the function of page memory management is to add a layer of address mapping mapped by the segment memory management.

Since the address mapped by segment memory management is no longer a “physical address”, Intel calls it a “linear address” (also known as a virtual address). Thus, segment memory management maps logical addresses to linear addresses, and page memory management maps linear addresses to physical addresses.

Intel X86 logical address parsing process

Here are the logical and linear addresses:

  • Addresses used by programs are usually addresses not mapped by segment memory management, called logical addresses.
  • Addresses mapped by segmental memory management are called linear addresses or virtual addresses.

The logical address is the address before the “segment memory management” conversion, and the linear address is the address before the “page memory management” conversion.

Now that we know the history of Intel processors, how does Linux manage memory?

Linux memory mainly uses page memory management, but it also inevitably involves a segment mechanism.

This is mainly due to the Intel processor history above, because Intel X86 cpus generally map the addresses used in programs in segments before performing page mapping. Given the HARDWARE architecture of the CPU, the Linux kernel is subject to Intel’s choice.

But in fact, the Linux kernel has taken the approach of making the process of segmental mapping virtually useless. In other words, there are policies at the top and countermeasures at the bottom.

On Linux, each segment is the entire 4GB of virtual space (32-bit) starting at address 0, meaning that all segments start at the same address. This means that Linux code, both operating system code and application code, faces linear address Spaces (virtual addresses), which is equivalent to masking the concept of logical addresses in the processor, and segments are used only for access control and memory protection.

Let’s take a look at how Linux’s virtual address space is distributed.

In Linux, the virtual address space is divided into kernel space and user space. The range of address space varies with different bits. For example, the most common 32-bit and 64-bit systems are as follows:

User space versus memory space

It can be seen from here:

  • 32Bit system kernel space footprint1GIs at the top, and the rest3GIs user space;
  • 64The kernel space and user space of a bit system are both128T, occupying the highest and lowest parts of the entire memory space respectively, leaving the middle part undefined.

Again, the difference between kernel space and user space:

  • In user mode, a process can only access user space memory.
  • Only after entering the kernel state, can access the kernel space memory;

Although each process has its own virtual memory, the kernel address in each virtual memory is actually associated with the same physical memory. In this way, the process can easily access kernel space memory after switching to kernel mode.

The kernel space of each process is consistent

Next, to learn more about the partition of virtual space, user space and kernel space are divided differently, not to mention the distribution of kernel space.

Let’s look at the distribution of user space. Using a 32-bit system as an example, I’ve drawn a graph to show the relationship:

Virtual memory space partition

As you can see from this graph, there are seven different memory segments in user space, from lowest to highest:

  • Program file segment, including binary executable code;
  • Initialized data segment, including static constants;
  • Uninitialized data segments, including uninitialized static variables;
  • Heap segments, including dynamically allocated memory, grow upward from low addresses;
  • File mapping segments, including dynamic libraries, shared memory, and so on, grow from low addresses upwards (depending on hardware and kernel version);
  • Stack segment, including local variables, function call context, etc. The stack size is fixed, usually8 MB. Of course, the system also provides parameters so that we can customize the size;

Among the seven segments, memory for the heap and file mapping segments is allocated dynamically. For example, using the C standard library’s malloc() or mmap(), you can dynamically allocate memory in the heap and file mapping segments, respectively.


Total summary”

To in a multi-process environment, making the process between the memory address is not affected, isolated, then the operating system independent distribution of a set of virtual address space for each process, each program only CARES about its own virtual address can, in fact everyone’s virtual address is the same, but the distribution to the physical address of memory is not the same. As a program, you don’t have to worry about physical addresses.

Each process has its own virtual space, the physical memory is only one, so when you enable a lot of process, the physical memory is bound to be very nervous, so the operating system through memory switching technology, the rarely used temporarily to hard disk memory (in), in need of loading back to physical memory (in).

Now that you have a virtual address space, you have to “map” the virtual address to the physical address, which is usually maintained by the operating system.

So for the mapping relationship between virtual address and physical address, there can be segmentation and paging, and both can be combined.

Memory segment is divided into stack segment, heap segment, data segment, code segment, etc., according to the logic point of view of the program. In this way, segments with different attributes can be separated, and at the same time, it is a contiguous space. However, the size of each segment is not uniform, which leads to memory fragmentation and inefficient memory swapping.

Thus, memory paging occurs, dividing virtual and physical space into fixed pages, such as 4KB each on Linux systems. Since the pages are split, there is no small memory fragmentation. At the same time, only one or several pages can be written to the hard disk during memory swapping, which greatly improves the efficiency of memory swapping.

In order to solve the problem of large page tables caused by simple pagination, multi-level page tables are introduced. They solve the space problem, but cause the CPU to have many layers of tables in the process of addressing, which increases the time overhead. Therefore, according to the principle of program locality, TLB is added into THE CPU chip, which is responsible for the cache of the recently frequently accessed page table items, greatly improving the speed of address conversion.

Linux mainly uses paging management, but due to the history of Intel processors, Linux cannot avoid segmenting management. Linux sets the base address of all segments to 0, which means that the address space of all programs is a linear address space (virtual address). This eliminates the concept of CPU logical addresses, so segments are used only for access control and memory protection.

In addition, virtual space distribution in Linxu system can be divided into user state and kernel state. The distribution of user state is code segment, global variable, BSS, function stack, heap memory and mapping area.


nagging

The 300-page “Graphic Network” PDF has been published for some time now, and has recently received a lot of errata feedback from readers, most of which are typos and missing words, etc. Thank you very much to those readers who perused the PDF.

One of them, a very hardcore reader, corrected nearly 9W words of PDF typos.

And very detailed. How detailed is that? There are too many details about Spaces, incorrect punctuation, the difference between “zai” and “re” and so on.

Let’s see how many bugs Kobayashi wrote…

That string of red is the record that this reader corrects, thanks again to this hardcore and attentive reader. To tell the truth, there are such readers, Xiao Lin or quite proud ha ha.

Kobayashi also reorganized the PDF, you can download the corrected “Graphic network V2.0”, reply “network” on the official account to get the download address link.

If you find any incomprehension or mistakes in the reading process, please feel free to give feedback and communicate with Xiao Lin.

The public account replies to “network” to obtain the download address

Kobayashi is a tool man for you. Goodbye, see you next time!