It's been a long time since I've had a chance to work on rCore, so God help me, I'd really like to learn how to do it.
introductory section
First things first.official document.
I decided to read it over and then formulate it myself (Wise General) .
Here repeatedly mentioned MMU, is because before learning MCU when there is a question, that is, why the MCU does not choose to run a Linux, then found the answer is because there is no MMU.
The full name of MMU is Memory Management Unit. At that time, I did not know why the hardware needs such a memory management unit, now we can find out.
Repeated references to him are a reminderVirtual and physical address translationis not implemented by the OS we write, but the OS writes an interface through which thecall (programming)The MMU implementation.
Then the most important thing isaddress spaceThis concept, with the address space, can be used in thekernel (computer science)for constructing the virtual and real address spaces in themap (math.)Mechanisms.
Here's what I understand about the diagram above.
P1~P3 is the address space of each application and the kernel is the address space of the operating system kernel. For each address space, the addresses are from the
0
late2^32-1
. And we utilize hardware mechanisms (e.g., MMU + page table lookup) to accomplish the mapping of these address spaces to physical addresses.
Before address virtualization
This section is very interesting. In particular, it mentions.
Later, to reduce the pointless CPU resource loss caused by waiting for I/O, multi-channel programs appeared. And to improve user interaction and productivity, time-sharing multitasking systems were born. They are characterized by the fact that the application starts with an additional "pause" state, which can be derived from it actively yielding CPU resources or from the kernel forcibly abandoning the processor after executing for a long enough period of time.
Isn't that part of what we learned in the last part?time-sharing multichannel programWhat? - I don't know.
So what did we do then?
In fact we are for all apps areincommunicadoA stack is opened, which has a higher memory loss.
At this point it is possible to read inside the text.
One memory-saving approach is that each application still occupies the same block of memory outside the kernel as it does in a batch system; when paused, the kernel is responsible for saving its code and data in external memory (e.g., a hard disk), then restoring the code and data from the external memory of the application that is about to be switched over to memory, and then only starting to execute the new application after all of this has been done.
Then this method is to occupy a separate segment of memory for each app'sOne of the solutions(i.e., saved in external memory.)
It is well known that hard disks do not read as fast as RAM, so this is a neat way to introduce something new to this section.
The final document summarizes the drawbacks of the previous chapter: the
- From an application development point of view, it is necessary for the application to decide which physical address it will be loaded to run at, requiring direct access to real physical memory. This requires the application developer to know more about the characteristics and usage of the hardware, incurring additional learning costs and inconvenience for application development and debugging.
- From the kernel's point of view, delegating direct access to physical memory to applications makes it difficult for it to effectively manage application accesses, and the existing privilege-level mechanisms do not prevent many malicious behaviors from applications.
Add a layer of abstraction to enhance memory management
Any problem in computer science can be solved with another layer of indirection.
This quote comes from a professor in the computer science department at the Massachusetts Institute of TechnologyButler Lampson..
Here are some additions to my half-guesses and half-understandings above, especially this oneIt doesn't have to be real.Very important.
Ultimately, the abstraction that is still widely used by operating system kernels today is called theaddress space (Address Space. In a way, it can be thought of as a huge butIt doesn't have to be real.of memory.
In each application's perspective, the operating system assigns the application a restricted range of addresses (very large capacity),monopolize(some of which is used by the operating system).limitationnot accessible, such as the virtual address space occupied by the kernel itself, etc.), so the application can plan its memory layout as it wishes in the address space allocated to it, and its segments can each be placed where it wishes in the address space (at the addresses that the operating system allows the application to access, of course).
Such addresses are calledvirtual address (Virtual Address) 。
#TODO
doMMU
cap (a poem)TLB
hardware mechanisms.
In fact, the privilege level mechanism is extended so that applications no longer have direct access to physical memory.
This is also related to the privilege level mechanism, check here too.RISC-V Reference BookTurn to 10.6.
- S-mode provides a traditional virtual memory system that divides memory into fixed-size pages for address translation and protection of memory contents.
- When paging is enabled, most addresses (both valid addresses for load and store and addresses in the PC)They're all virtual addresses.。
- coerceAccessing Physical Memory, they must be converted to real physical addresses, which is accomplished by iterating over a type of address known as theleaflet(used form a nominal expression)high base treeRealization.
- Page table in theleaf nodevirtual address (computing)Whether or not it has been mapped to a real physical page
- If yes, it indicates which permission modes and through which type of access this page can be manipulated.
- Access to unmapped pages or insufficient access rights can result in a page fault exception.
Benefits of address space abstraction
- Since each application occupies a single address space containing only its own segments, it can plan the distribution of its own segments without having to consider conflicts with other applications;
- Also given that the application can only read and write its own address space via virtual addresses, it is completely incapable of stealing or corrupting the data of other applications; after all, those segments are in the other application's address space, which is something it has no ability to access.
This is a guarantee of the security and stability of application execution by address space abstraction and concrete hardware mechanisms.
Add hardware-accelerated real-virtual address translation
This is a very good section, going to check out the content and the chart.Address Space - rCore-Tutorial-Book-v3 3.6.0-alpha.1 Documentation
This one makes perfect sense.
Just the left half, in the app's point of view.App0
By accessing avirtual addressVirtual Address
, accessed its address spaceAddress Space 0
, and correspondingly found the dataApp0 Data
:
Looking at the right-hand side, the access operation is actually performed by theOS
and hardware agents, through theMMU
isomerization (chemistry)Virtual Address
Physical addressPhysical Address
, which in turn accesses the physical address stored in thephysical memoryPhysical Memory
hit the nail on the headApp0 Data
:
Notice here how the graph in thisPhysical Memory
Partly, there are some interesting points to learn while you're at it.
-
Kernel Reserved
Part of the memory is occupied by the operating system's kernel - This side not only stores
App 0 Data
Also storedApp 1 Data
cap (a poem)App 2 Data
. In fact, it shows that inApp
perspective, the only thing it can see through virtual memory is its ownData
, and physical memory holds otherData
.
So back to the title of this sectionAdd hardware acceleration
The manual describes it as follows.
The operating system can design clever data structures to represent the address space. But if the operating system were to do all the real and virtual address translation required to convert each processor address access, theThat's a lot of money.up. This requires extended hardware features to accelerate the address translation process (recalling thecomputer composition principle in-class
MMU
cap (a poem)TLB
)。
This suggests that the implementation of virtual addresses relies on.
- Operating System DesignClever Data Structures
-
MMU
cap (a poem)TLB
hardware acceleration
This passage enhances our understanding of the operating system design concepts for thehardware resource abstraction:
Back when we introduced the kernel's abstraction of CPU resources - time division multiplexing, we mentioned that it creates the illusion that each application occupies the entire CPU, while hiding the reality that multiple applications share the CPU in time division. The same is true for the address space. An application only needs to see the illusion that it occupies the entire address space, but behind the scenes, the essence is that multiple applications share the physical memory, and their data is stored in different locations in the memory.
Segmented Memory Management
Segmented memory management was once a popular memory management method, and you can learn a lot about memory management by studying it.#TODO
Constant size memory + linear mapping
A segmented memory management scheme is shown in the figure.
As can be seen here very violently theMemory size per app(not the corresponding size for individual app settings) are all forced to be assigned to thebound
. At this point we tend to think of what we learned earlier in sections 16 and 17, that bycap (a poem)
link_app.S
Place the compiled.bin
The way files are linked into the kernel.
It seems that assigning each app aSlot It's not a very pleasant way of doing things, since we're compiling directly into the kernel, and it seems that the memory size is fixed.
Here's where we have to break the illusion.
- What we learned in verses 16 and 17, only
stack
and there are no dynamically allocatable memoryheap
- Apps at that stage didn't have dynamic memory allocators
- How can you implement flexible data structures such as dynamic arrays without a dynamic memory allocator?Create a very large array directly.
- The content learned in sections 16 and 17, including the content of the multi-channel program learned in section 22, requires the initial memory to be set up at compile time without having its ownmemory space,
- This decision was compiled well
.bin
Files can only be loaded into a fixed location- This makes the APP bothinsecurity(with access to physical memory) withoutversatile(dynamic memory cannot be used).
So continuing to look at the picture, we can seeAddress Space of App0
:
-
Code
paragraph 1 (b) and paragraph 2 (c) of the annex to the report of the Secretary-General on the work of the Organizationphysical memoryPerformance inequal, directly placed in a fixed location, except that the address of this location is no longer a physical address, but directly from the virtual address0x0
Starting. - and the global variables represented by the
Data
Paragraph. - Downwardly mobile
stack
, but note that an app'sstack
The maximum size is known after compilation. - It's possible to grow upwards
heap
. Variables that are only known at runtime are to be applied to theheap
Inside.
at this momentMMU
Just play abitmapand the role of the United Nations in the implementation of the Convention on the Elimination of All Forms of Discrimination against Women.
A bitmap is a binary array in which each bit (bit) represents a specific region of memory (e.g., a memory page or block). Each bit in a bitmap can be either a 0 or a 1. A 0 usually indicates that the corresponding region of memory is free, while a 1 indicates that it has been allocated.
When a program needs to allocate memory, the operating system examines the bitmap, finds a sufficient number of consecutive zeros (indicating free areas), and sets these bits to 1 to indicate that memory has been allocated.
When a program frees memory, the operating system resets the corresponding bits in the bitmap to 0, indicating that these memory areas become free again.
Then the problem is very simple, in fact, this part of our thinking is broken down into three steps.
- What does memory allocation look like now?
- What kind of work did MMU do in this
- How memory fragmentation occurs
That's where memory fragmentation comes in.
Here's a simple way to putUnutilized memory in already allocated memorybe known asinner fragment.
So this is the typical problem of internal fragmentation, where every allocation of memory is constantbound
So how many apps can be utilized just enough so that the utilization rate is very low.
segmentation strategy
Then in order to solve the aboveinner fragmentA strategy for segmented management has been found.
Still looking at the picture, solving the problem we talked about above.three questions.
can be seenMMUSeparately, the APP in thestage (of a process)Perform a linear mapping, where each part is astage (of a process).
Note thatExperimental guideOmitting a few details.
For simplicity's sake, we'll ignore some unnecessary details here. For example, when an application accesses an address space indexed by a virtual address, how does it know which segment the address belongs to so that the hardware can use the correct pair of base/bound registers to perform the legitimacy check and do the actual address translation.
Here it is actually easy to think again about theheap upof the question.Experimental guideMentioned in.
The heap may be a special case in that its size may grow at runtime, but that requires the application to request it from the kernel via a system call.
Not at this point.inner fragmentThe problem is.
Think Before You Learnbuddy-system
The problem of memory allocation is that the alignment between each segment is actually the same as that for theMinimum accessible memory sizerelated, using a segmented approach to memory management can result in all kinds ofNot available (cannot be distributed) The memory fragmentation, commonly calledshard. Of course, the outer fragments can still be put together in various ways.
If you want to allocate a larger block, you need to "put together" the disjointed outer fragments to form a large contiguous block. However, this is a very expensive thing to do, involving significant memory read/write overhead. Specifically, it is necessary to move and reposition some of the allocated memory blocks in physical memory in order to allow the small outer fragments to fit together to form a large free block. This operation can be minimized if the sequential memory allocation algorithm is properly chosen. The algorithms taught in operating systems classes, including the first-fit/worst-fit/best-fit or buddy system, have their own advantages and disadvantages, depending on the needs of the application.
Paging Memory Management
What comes to mind after reading this section is that there's a lot aboutdiffering perspectivesthinking, we can see that when segment memory is allocated, we are alwaysindulge sb (usu. a child)APP, always want our memory allocation system to go to thebecome man and wifeSome memory characteristics of APP .
But after reading this section, we can understand that actually splitting the app's memory management may be an unthought path.
Again, we're going to look at the pictures and talk.
As you can see, for each applicationaddress spacecarry outtab window (in a web browser etc).
Then each address space of thevirtual page numbercan all be converted by the MMU into aPhysical Page Number .
Such a chemicalization is actually equivalent to still using theAllocate a fixed size of memoryThe method ofSmaller particle size.
Each application has an address mapping relationship representing theleaflet (Page Table), which records which physical page frame in physical memory each virtual page in that application's address space is mapped to, i.e., where the data is actually placed by the kernel.
We can use the page number to represent the two, so if you look at the page table as a key-value pair, the type of the key is the virtual page number and the type of the value is the physical page number. When MMU performs address translation, the virtual address will be divided into two parts (virtual page number, in-page offset), MMU firstly finds the page number of the virtual page where the virtual address is located, then checks the page table of the current application, and finds the physical page number according to the virtual page number; finally, according to the in-page offset of the virtual address, it adds an offset to the start address of the physical page frame corresponding to the physical page number, and this will get the actual accessed physical address.
Here it is more precise, not only to correspond to the correspondingpage number, then for an exact memory address, there is also aoffset value.
Then there's another one in the chartProtevtion
The first paragraph, it is good to understand is added to the read and write protection, but we know that the so-called protection is in fact theLogic written in the OSSo how exactly is this accomplished (via thetrigger an exception ) are also important.
There is also a set of protection bits in the page table for virtual page numbers, which restricts the way an application can use the memory corresponding to the physical address obtained by translation. Typical examples are
rwx
,r
Indicates that the current application can read this memory;w
Indicates that the current application can write to this memory;x
This restriction means that the current application can take instructions from that memory and use them for execution. If this restriction is violated, an exception is thrown and caught by the kernel. With the appropriate settings, it is possible to check for obvious runtime errors such as applications modifying read-only code segments or fetching instructions from data segments for execution.