One, paging storage

  • Divide the memory into equal partitions. Each partition is a block of memory, called a page. Like an array, each partition is assigned a page number

1. Address structure:

  • Intra-page offset: 12 bits, which can represent 2^12 bytes, equivalent to 4K, which can represent every byte within 4KB
  • Page number: 20 digits, indicating 2^20 pages

2, page table

  • The operating system creates a page table for each process, which is copied when the parent forks the child process.

3, fast table

  • Access process when there is no fast table
    • Page number = logical address/page length
    • Offset = logical address % page length
    • Find the page table corresponding to the thread on the spot (first fetch) and load it into the CPU
    • From the page table, find the page number, offset, get the address, access the actual address of memory (second fetch)
  • Access when fast tables exist
    • Page number = logical address/page length
    • Offset = logical address % page length
    • Fast tables are stored in registers and do not need to be accessed
      • If yes, access the address directly
      • If not, continue to access the page table — “access main memory (two accesses)

4, secondary page table

  • Assume a 32-bit computer with a 32-bit logical address, paging management, and a page size of 4KB
  • So if you want to represent each byte, the offset needs to be 12 bits. On a 32-bit computer, the addressing length is 32 bits, so the previous page number is 20 bits, so the process can occupy up to 2^20 page numbers. 2^20 = 1M
  • The size of a page number is 32 bits, so storing 1M page numbers requires 1M * 4B = 2 ^ 22b,
  • A page can provide 4KB of storage so 2^ 22/2 ^ 12 = 2^10 page frames is equal to 1024 page frames, and it has to be contiguous to store, to have random access.
  • The page size is 4KB and the page number is 4B, so a page can hold 1024 page numbers,
  • For a process, the range of support for lookup is 2 ^ 32, a page size is 4KB, so you need to have 2 ^ 20 page numbers, divided by a page can only hold 1024, so you need to have 1024 consecutive memory blocks. If the size of memory is 4GB = 4 of 30 squares.
  • Due to the principle of locality, a process is likely to visit only a few pages at any given time, so there is no need to keep all pages in memory
  • At this point, it’s a little wasteful to use contiguous chunks of memory at once,

For these reasons, a secondary page table is created

In this way, the page table does not need to be continuously stored, and part of the page table can also be transferred to external storage, saving memory space.

  • Just a couple of little details
    • Use multi-level page tables, each page table size can not exceed one page,
    • Multilevel page table is used, which requires multiple accesses. The first level page table looks for the memory block number of the second level page table, and the memory of the second level page table looks for the next level quickly

Case study:

Second, segmented storage

Segmented storage is two-dimensional, paging is one-dimensional

1. Logical address structure

2, the segment table

3. Address calculation

  • When converted to (2,1024), the segment number is 2 and the intra-segment address is 1024
  • The base address of 2 is 40kB, plus 1024B, which is the address you need to access

Compare paging and segmentation

  • Paging addresses are one-dimensional: you only need to give a logical address, the logical address /4B is the page number, and the logical address %4B is the offset

  • Segment address is two-dimensional, need to give the segment number, and then give the offset within the segment

  • The paging size is fixed at 4B

  • The size of the segment is not fixed,

  • Pages are the physical unit of information; pagination is only determined by the system

  • An end is a logical unit of information, and an end usually contains a logical block of information

Section page storage

  • Divide the pages logically and then paginate them.

  • Similar to multi-level page tables, it also requires three fetches

4. Virtual memory

  • Virtual memory provides a consistent, private address space for each process, which gives each process the illusion that it is in exclusive main memory (each process has a contiguous, complete memory space).

  • People who don’t understand very well will think that virtual memory is just a technique of “using hard disk space to expand memory”, which is not true.

  • The significance of virtual memory is that it defines a continuous virtual address space, which makes the programming difficult.

  • In addition, the expansion of memory into hard disk space is a natural result of using virtual memory, which is stored on hard disk and cached (as needed). Some operating systems also put all memory of a process into hard disk space when they run out of memory. And read from the hard disk when switching to the process (this is also why Windows often faked death…). .

  • Function:

  • It treats main memory as a cache of virtual address space stored on hard disk, and caches active areas only in main memory (cache on demand).

  • It reduces the complexity of memory management for programmers by providing a consistent address space for each process.

  • It also protects the address space of each process from being corrupted by other processes.

1. CPU addressing

  • Physical addressing: Memory can be compared to an array of equal bytes. Each location in the array has a unique address. As an index of the array, CPU access memory can be accessed by bytes from the physical address

  • Virtual addressing: The CPU needs to translate virtual addresses into physical addresses to access real physical memory

  • The MMU (memory management unit) converts virtual addresses into physical addresses. The MMU queries the mapping between virtual addresses and physical addresses using the page table stored in the memory.

2, page table

Page table: A data structure stored in physical memory that records the mapping between virtual pages and physical pages

  • Virtual memory: Space is organized as an array of M contiguous byte units stored on hard disk. Each byte has a unique virtual address that serves as an index to the array (this is actually the same as physical memory).

The operating system divides Virtual memory into fixed-size blocks as the transfer unit between disk and memory. This block is called Virtual Page (VP). The size of each Virtual Page isP=2^pBytes. Physical memory is also split into Physical pages (PP) in this way, also of sizePbyte

After obtaining a virtual address, the CPU needs to translate the virtual address into a physical address through the MMU. In the process of translation, we also need to use the page table, which is a data structure stored in physical memory, which records the mapping between virtual pages and physical pages.

A Page Table is a collection of Page Table entries (PTE), and each virtual Page has a PTE at a fixed offset in the Page Table. The following is a PTE page table structure with only one significant bit marker that indicates whether the virtual page is cached in physical memory.

Virtual pages VP 0, VP 4, VP 6, and VP 7 are cached in physical memory. Virtual pages VP 2 and VP 5 are allocated in the page table, but not cached in physical memory. Virtual pages VP 1 and VP 3 are not allocated.

When performing dynamic memory allocation, such as the malloc() function or the new keyword in other high-level languages, the operating system creates or allocates a virtual memory space on disk and updates it to a page table (allocates a PTE pointing to the newly created virtual page on disk).

Since the CPU needs to pass through the PTE every time it does address translation, if you want to control access to the memory system, you can add some extra permission bits (such as read and write permissions, kernel permissions, etc.) to the PTE, so that any instruction that violates these permission conditions will trigger a general protection failure. Pass control to the exception handler in the kernel. Such exceptions are generally called Segmentation faults.

Page hit

  • As shown in the figure above, the MMU is addressed in the page table based on the virtual addressPTE 4, the significant bit of the PTE is 1, indicating that the virtual page has been cached in physical memory. Finally, MMU obtains the physical memory address in THE PTE (pointing toPP 1).

Missing page

  • As shown in the figure above, the MMU is addressed in the page table based on the virtual addressPTE 2, the significant bit of the PTE is 0, indicating that the virtual page is not cached in physical memory.A virtual page that is not cached in physical memory (a cache miss) is called a page miss.

  • When a PAGE is missing, the CPU triggers the page missing exception and transfers the control to the operating system kernel. The kernel calls the page missing exception handler to handle the page missing exception. In this case, the CPU selects a page from the memory.

    • If there are free blocks in memory, a free block is allocated to the process, the missing pages are placed in the current block, and the page entry information corresponding to the page table is modified
    • If there is no free block in the memory, the page replacement algorithm needs to select the page for elimination, if the page is modified, it needs to write back to external memory, if the page has not been modified, it does not need to

  • When the page missing exception handler returns, it restarts the instruction that caused the page missing, which resends the virtual address that caused the page missing to the MMU. Since the page miss exception has now been successfully handled, the end result is a page hit and the physical address is retrieved.

  • This transfer of pages between disk and memory is called paging: pages are swapped from disk to memory and from memory to disk. The policy of paging into memory only when a page missing exception occurs is called Demand paging, which is basically used by all modern operating systems.

  • Virtual memory, like CPU caching (or any other technology that uses caching), relies on the principle of locality. While dealing with the consumption of missing page performance a lot (after all, still want to read from the hard disk), and the application in different virtual reference in the process of running the total number of pages may exceed the size of the physical memory, but local principle ensures that at any moment, the program will tend to be in a smaller activities page (active page) on the collection, This set is called a working set. According to the principle of spatial locality (a memory address is accessed and its peripheral memory address will have a great chance to visit again) principle of locality and time (after a accessed memory addresses in there is a big chance to be accessed again), as long as the working set are cached in physical memory, then the address translation request high risk in it, This reduces the amount of extra hard drive traffic.

  • If a program does not have good locality, the size of the working set expands until it exceeds the size of physical memory, resulting in a state called thrashing, in which pages are constantly moving in and out of the program. Therefore, to write an efficient program, the first step is to ensure the time locality and space locality of the program.

Virtual memory system in Linux

  • Linux maintains a separate virtual address space for each process. Virtual address space is divided into kernel space and user space. User space includes code, data, heap, shared library, and stack. Kernel space includes code and data structures in the kernel. Some areas of kernel space are mapped to physical pages shared by all processes.
  • Linux also maps a contiguous set of virtual pages (size equal to total memory) to a corresponding contiguous set of physical pages, which provides a convenient way for the kernel to access any particular location in physical memory.

  • Linux organizes virtual memory into collections of regions (also known as segments), a concept that allows gaps in the virtual address space. An area is a contiguous chunk of allocated virtual memory that already exists. For example, code segments, data segments, heaps, shared library segments, and user stacks all belong to different regions, and each existing virtual page is stored in a region. Virtual pages that do not belong to any region do not exist and cannot be referenced by processes.

The kernel maintains a separate task structure (task_struct) for each process in the system. The elements in the task structure contain or point to all the information the kernel needs to run the process (PID, pointer to user stack, name of executable object file, program counter, and so on).

  • Mm_struct: describes the current state of virtual memory. PGD points to the base address of the level 1 page table (PGD is stored in the CR3 control register, or page table base register, when the kernel runs this process), and Mmap points to a linked list of VM_AREA_structs, each of which describes an area of the current virtual address space.

  • Vm_starts: points to the start of this area.

  • Vm_end: points to the end of this area.

  • Vm_prot: Describes the read and write permissions for all pages contained in this area.

  • Vm_flags: Describes whether pages in this area are shared with other processes or are private to the process, and other information.

  • Vm_next: points to the next region structure of the linked list.

1. Memory mapping

  • Linux initializes the contents of a virtual memory area by associating it with a file on a hard disk, a process called Memory mapping. This method of integrating the virtual memory system into the file system makes it simple and efficient to load programs and data into memory.

  • A region can be mapped to contiguous portions of a normal hard disk file, such as an executable object file. The section is divided into page-sized slices, each containing the initial content of a virtual page. Due to the policy of on-demand page scheduling, these virtual pages are not actually swapped into physical memory until the virtual address referenced by the CPU is within the range of that area. If the area is larger than the file area, fill the rest of the area with zeros.

  • A region can also be mapped to an anonymous file, which is created by the kernel and contains all binary zeros. When the CPU first references a virtual page in such an area, the kernel finds an appropriate sacrifice page in physical memory, writes it back to disk if it has been modified, and then overwrites the sacrifice page with binary zero and updates the page table, marking the page as cached in memory.

  • To put it simply:

    • Normal file mapping is to map a file to a block of memory. IO operations on the file can be performed directly in user mode, bypassing the kernel (user mode reads and writes the file in the virtual address area).

    • Anonymous file mapping When the user space needs to allocate a segment of memory to store data, the kernel creates an anonymous file and maps it to the memory. Then the user mode can manipulate the virtual address to manipulate the memory. The most familiar application scenario for anonymous file mapping is dynamic memory allocation (malloc()).

The Shared object

  • Memory mapping provides a mechanism for sharing objects to avoid wasting memory resources. An object is mapped to a region of virtual memory, either as a shared object or as a private object.
  • Changes to shared objects trigger copy-on-write techniques

  • A typical example is the fork() function, which is used to create child processes. When fork() is called by the current process, the kernel creates all the necessary data structures for the new process and assigns it a unique PID. To create virtual memory for the new process, it copies the current process’s mm_struct, VM_AREa_struct, and as-is copies of the page table. Each page of both processes is marked as read-only, and each region in both processes is marked as private (copy at write time).

  • The virtual memory space of the parent and child is exactly the same, and only when either process writes, copy-on-write is used to keep the abstraction of the virtual address space private for each process.

reference

  • Juejin. Cn/post / 684490…