“This article has participated in the call for good writing activities, click to view: the back end, the big front end double track submission, 20,000 yuan prize pool waiting for you to challenge!”

Memory basics

What is memory?

The most intuitive, we buy mobile phones, computers, memory bars, will indicate how much memory, such as the way 8G, 16G, 128G refer to the size of memory, in addition to support domestic products, support Huawei.

We’ve probably all heard of RAM memory, which is a semiconductor memory device. RAM is a contraction of the English word Random, meaning “Random”. So RAM memory is also called “random access memory”.

So what does RAM memory have to do with memory? Memory is a collection of RAM memories, a circuit board that integrates many RAM memories together. The advantage of RAM memory is fast access and easy to read and write, so of course the speed of memory is also fast.

What does it do?

Operating system history

Anyone who knows a little about the history of operating systems knows the development of bare machines without operating systems -> single-channel batch systems that can only run one program at a time -> multi-channel batch systems -> time-sharing systems.

Bare machine age

It is mainly manual operation. The programmer will load the perforated paper tape (or card) of the application program and data into the input machine, and then start the input machine to input the program and data into the computer memory, and then start the program to run against the data through the console switch; After the calculation, the printer outputs the calculation results; The user takes the results and removes the tape (or card) before letting the next user on.

Man-machine contradiction: sharp contradiction is formed between the slow speed of manual operation and the high speed of computer. Manual operation mode has seriously damaged the utilization rate of system resources (make the utilization rate of resources drop to a few percent, or even lower), which cannot be tolerated. The only solution is to get rid of manual operation and realize automatic transition of operation. This is where batch processing comes in.

Single channel batch system

The feature is that only one process can be run at a time, only after the next process can be loaded into the memory, so the process data are directly placed in the physical memory, so the CPU is directly operating the physical address of the memory, this time there is no virtual logical address, because only one program can be run.

Contradiction: Only one job is stored in the host memory at a time. When the host sends input/output (I/O) requests during its running, the high-speed CPU waits for the low-speed I/O to complete, resulting in idle CPU.

Multichannel batch system

To the later development of multi-programming system, it requires the existence of multiple processes in the computer, the processor needs to switch between multiple processes, when a program is suspended because of I/O requests, the CPU will immediately switch to run another program.

The question is, what if there are so many processes running out of memory? What if each process overwrites each other when running at the same time?

When linking to an executable file, the linker always defaults to the starting address of the program to 0x0, but there is only one 0x0 address in physical memory. You might say, “Never mind, we can dynamically change the address again when the program is loaded into memory.” Okay, I’ll take it. But what if I only have 1 gigabyte of physical memory, and now a program needs more than 1 gigabyte? Can you explain that in the same way?

The development of the operating system, including the later time-sharing system, is actually to solve the contradiction of the speed mismatch in each link of coordination.

The CPU is much faster than the disk

The function and association between the memory layers is pyramid shape, CPU can not directly control the disk, is to control the memory to work, because the disk speed is far less than the CPU speed, can not keep up with, need the middle memory layer buffer.

How memory speeds faster than hard disks: Memory speeds faster than hard disks (not a little faster, but a lot faster) because they are not stored and read in the same way.

Hard disks are mechanical structures that read data through the rotation of magnetic heads. A typical desktop hard disk is 7200 revolutions per minute, while a laptop hard disk is 5400 revolutions per minute.
Memory, on the other hand, has no mechanical structure. It accesses data electronically.

Memory accesses data electrically, essentially because RAM memory stores data electrically. But because they store their data electrically, they are lost when power goes out. Therefore, memory is only a temporary space for data to linger, while hard disk is permanent, data will not disappear after power failure.

Summary: programs need to be stored in memory before they can be processed by the CPU. Therefore, the main function of memory is to ease the speed contradiction between CPU and hard disk.

Program running procedure

In a multiprogram environment, the system will have multiple programs running concurrently, that is, the data of multiple programs need to be placed in memory at the same time. So, how do you tell where data is stored in each program?

Solution: Address the storage unit of memory.

The running process of the program is as follows:

Compilation: Translating high-level languages into machine languages;

Link: a set of target modules and required library functions are linked together by the link program to form a complete load module;

Load: loading a module into memory by a loader;

Three ways to link

Static link

Before the program runs, the target modules and their required library functions are linked into a complete executable file (load module), that is, to get a complete logical address, and then no longer open.

Load time dynamic linking

The link method of loading side links before running.

Runtime dynamic linking

The target module is linked only when it is run, and unused modules do not need to be loaded into memory. Its advantages are easy to modify and update, easy to realize the sharing of the target module.

You can see runtime dynamic linking. Instead of loading all modules into memory at once, you can dynamically connect them when needed at runtime. This provides a solution to the problem of running out of memory, or linking them when needed.

Three loading methods

1. Absolute loading

When compiling or assembling, the absolute address, namely the physical address of memory, is directly stored to the corresponding physical address.

Single-channel processing systems manipulate physical addresses directly, so absolute loading is only suitable for single-channel programming environments.

Static relocation loading

Also known as relocatable load, here the introduction of logical address, load the relocation of logical address into physical address, the use of multi-channel batch system.

Static relocation is characterized by the fact that when a job is loaded into memory, all of its required memory space must be allocated, and if there is not enough memory, the job cannot be loaded. Once a job is in memory, it cannot be moved or allocated for memory during runtime.

Dynamic relocation loading

Also known as dynamic runtime loading, the runtime converts a logical address relocation into a physical address. This approach requires the support of a relocation register, which is of course used by modern operating systems.

The logical addresses all start at 0, assuming the start physical address of the load is 100, and the dynamic relocation load is shown as follows:

Memory management responsibilities

Responsibilities of memory management – allocation and reclamation of memory space – continuous allocation management mode

Continuous distribution mode

In a single continuous allocation, memory is divided into system areas and user areas. The system area is usually located in the low address part of the memory, which is used to store the operating system-related data. The user area stores data related to user processes. There can be only one user program in memory, and the user program occupies the entire user area space.

Advantages: simple implementation; No external debris;

Disadvantages: Can only be used in single-user, single-task operating system; There are internal fragments; Memory utilization is extremely low.

Fixed partition allocation

One of the earliest and simplest forms of memory management that can run multiple programs is to divide the entire user space into several fixed-size partitions and load only one job into each partition.

The operating system needs to establish a data structure, partition description table, to achieve the allocation and reclamation of each partition. Each entry corresponds to a partition and is usually arranged by partition size. Each entry contains the size, start address, and status (allocated or not) of the corresponding partition, as shown in the following figure.

When a user program wants to load memory, the operating system kernel program retrieves the table according to the size of the user program, finds an unallocated partition that meets the size, allocates it to the program, and then changes the state to “allocated.”

Advantages: Simple implementation, no external fragmentation.

Disadvantages: Internal fragmentation and low memory utilization.

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. (eg: Suppose the memory size of a computer is 64MB, the system area is 8MB, and the user area is 56MB…)

Three problems arise:

What data structure does the system use to record memory usage?

If many free partitions can meet the requirements, which partition should be allocated?
How do I allocate and reclaim partitions?

Disadvantages: Dynamic partition allocation has no internal fragmentation, but external fragmentation.

Internal fragmentation: An area of memory allocated to a process that is not used.

External fragmentation: Some free partitions in memory that are too small to be utilized.

If the sum of free space in memory could meet the requirements of a process, but the process needs a contiguous chunk of memory space, these “fragments” cannot meet the requirements of the process. External debris can be resolved by Compaction.

Dynamic partition allocation algorithm

First time to adapt algorithm: each time from the low address to find the first free partition that can meet the size.
Optimal adaptive algorithm: Since dynamic partition allocation is a continuous allocation method, the space allocated for each process must be a continuous whole area. Therefore, in order to ensure continuous large areas of space when the “big process” arrives, it is possible to leave as many large free areas as possible, that is, use smaller free areas first
Worst adaptive algorithm: In order to solve the problem of the best adaptive algorithm — that is, leaving too many small fragments that are difficult to use, the largest continuous free area can be preferentially used during each allocation, so that the remaining free area after allocation will not be too small and more convenient to use.
Adjacency adaptation algorithm: the first adaptation algorithm starts from the head of the chain every time. This can result in many small, free partitions in the low-address portion that are passed through each allocation lookup, thus increasing the lookup overhead. You can solve this problem if you start each search from where the last search ended.

Responsibilities of memory management – allocation and reclamation of memory space – discontinuous allocation management

Continuous allocation: The user process must be allocated a contiguous memory space.

Discontinuous allocation: User processes can be allocated some scattered memory space.

Paging – What is basic paging storage

Divide the memory space into equal size partitions (e.g., 4KB each), and each partition is a “page frame” (page frame = page frame = memory block = physical block = physical page). Each page enclosure has a page enclosure ID (Page Enclosure ID = Page frame ID = Memory block ID = Physical block ID = Physical page ID). The page enclosure ID starts from 0.

The logical address space of the process is also divided into sections equal in size to the page box, each called a “page” or “page.” Each page also has a number, the “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 stored consecutively, but can be placed in non-adjacent page boxes.

Note: The last page of the process may not be as large as a page box. In other words, 16K-1 memory, paging storage has the potential to generate internal fragmentation, so the page frame should not be too large, otherwise it may generate too large internal fragmentation and become wasteful.

Paging – Page table

To know where each page of a process is stored in memory, the operating system creates a page table for each process. The page table is usually stored in a PCB(process control block).

Paging – Address translation after paging

Page number = logical address/page length (integer part of division)

In-page offset = logical address % page length (remainder of division)

Basic address shuffling:

The basic address shuffling mechanism translates logical addresses into physical addresses with the help of a process’s page table. Typically, a page table register (PTR) is set up on the system to hold the starting address F of the page table in memory and the page table length M. When the process is not executing, the start address and length of the page table are placed in the process control block (PCB), which the operating system kernel puts into the page table register when the process is scheduled.

Introduce fast table address transformation:

A fast table, also known as translation lookaside Buffer (TLB), is a cache that accesses much faster than memory (TLB is not memory!). To store a copy of the most recently accessed page entry and speed up address shuffling. Correspondingly, page tables in memory are often referred to as slow tables.

Note: Difference between TLB and normal Cache – TLB only has copies of page entries, while normal Cache may have copies of various other data

How much faster is the express watch?

Example: a system uses basic paging storage management and uses address shuffling mechanism with fast table. It takes 1us to access the fast table and 100us to access the memory. If a fast table has a 90% hit ratio, what is the average time it takes to access a logical address?

(1+100) * 0.9 + (1+100+100) * 0.1 = 111 us some systems support both fast and slow table lookup. If this is the case, the average time should be (1+100) * 0.9 + (100+100) * 0.1 = 110.9 us

If the fast table mechanism is not adopted, it takes 100+100 = 200us to access a logical address. Obviously, the speed of accessing a logical address is much faster after the fast table mechanism is introduced.

Paging – A two-level page table

Problems with single-level page tables:

Problem 1: Query the page table according to the page number: The storage position of the page table entry corresponding to page NUMBER K = the start address of the page table + K * 4. The page table must be stored continuously. Therefore, when the page table is large, it needs to occupy many consecutive page frames.

Problem two: It is not necessary to have the entire page table resident in memory, because the process may only need to access a few specific pages at a time.

Solution: pagination and discrete storage of the page table, and then set up a page table to record the storage location of each part of the page table, called the page directory table, or called the outer page table, or called the top page table.

Paging – Multilevel page tables

Take a look at multi-level page table paging.

Sectioning. – What is sectioning

The address space of a process: divided into segments according to the logical relationship of the program itself, each segment has a segment name (in low-level languages, programmers use segment names to program), and each segment is addressed from 0.

Memory allocation rule: Memory is allocated in units of segments. Each segment occupies contiguous space in memory, but the segments are not contiguous.

Segment – segment table

Segment-address translation

Segmentation VS paging

Page 1.1 is the physical unit of information. The main purpose of paging is to achieve discrete allocation and improve memory utilization. Paging is just a system administration necessity, completely a system behavior, invisible to the user.

A 1.2 paragraph is the logical unit of information. The main purpose of segmentation is to better meet user needs. A segment usually contains a set of information belonging to a logical module.

2.1 Segments are visible to the user, and the segment name needs to be explicitly given by the user during programming.

2.2 Page sizes are fixed and determined by the system. The length of the segment is not fixed, depending on the program written by the user.

3.1 Paged user process address space is one-dimensional, programmer only need to give a memory to represent an address.

3.2 The address space of segmented user process is two-dimensional. When identifying an address, the programmer should give both the segment name and the in-segment address.

4.1 It is easier to share and protect information in sections than in pages. Code that cannot be modified is called pure code or reentrant code (not a critical resource), and such code can be shared. Modifiable code cannot be shared (for example, if there are many variables in a code segment that are accessed concurrently by different processes at the same time, data may be inconsistent)

Segmented summary

The biggest difference from paging is the basic unit of the address space allocated in discrete allocation.

Section of the page type

Advantages and disadvantages of segmentation and paging:

Split-page – What is split-page

Each segment corresponds to a segment entry. Each segment entry consists of the segment number, page table length, and page table storage block number (start address of the page table).

Each segment entry has the same length, and the segment number is implied.

Memory Each page corresponds to a page entry. Each page entry consists of a page number and a memory block number. Each page entry is of equal length and the page number is implied.

Segment table type page table

Segment-page address translation

Paragraph page summary

Expansion of memory space

Many games are over 60GB in size, and the game program would normally need to put all 60GB of data into memory before running. However, I only have 8GB of ram on my computer, and I have wechat browser open and other processes running, but why does this game work?

Leveraging virtuality (virtuality of operating systems)

Time locality: if an instruction in a program is executed, it is likely to be executed again shortly thereafter; If some data has been accessed, it is likely to be accessed again shortly thereafter. (because there are so many loops in the program);

Spatial locality: Once a program accesses a storage unit, it is likely that nearby storage units will also be accessed shortly thereafter. (Because much of the data is stored consecutively in memory, and the program’s instructions are stored sequentially.)

What is the virtual memory size?

The maximum capacity of virtual memory is determined by the address structure of the computer (CPU addressing range). The actual capacity of virtual memory = min(sum of memory and external memory capacity, CPU addressing range)

For example, the address structure of a computer is 32 bits, addressed in bytes, the memory size is 512MB, and the external memory size is 2GB.

The maximum virtual memory capacity is 2^32 B = 4GB;

The actual capacity of the virtual memory = min (232B, 512MB+2GB) = 2GB+512MB;

Implementation of virtual memory

Request paging management

The main differences between request paging storage management and basic paging storage management are:

Request paging: During the execution of a program, when the information accessed is not in memory, the operating system is responsible for bringing the required information from external memory into memory and then continuing the program.
Page replacement: If memory space is insufficient, the operating system is responsible for the temporarily unavailable information out of memory into external storage.

Request pagination – Missing pages interrupted

Page-missing interrupt is generated because the target page that the executing instruction wants to visit is not called into memory. Therefore, it belongs to internal interrupt. During the execution of an instruction, multiple page-missing interrupts may occur. (For example, copy A to B, that is, copy the data from logical address A to logical address B, but A and B belong to different pages, there may be two interrupts)

Request pagination – address translation

Only write instructions need to modify the modify bit. In general, only the data in the fast table needs to be modified, and only the data in the slow table needs to be written back to the memory to delete the fast table. This can reduce the number of visits.
As with normal interrupt processing, page-missing interrupt processing still requires the CPU to be on-site.
Some sort of “page replacement algorithm” is needed to determine a paged page (next section)
Paging in and out of pages requires slow I/O operations, which can be costly if paging in and out too often.
After the page is loaded into the memory, you need to modify the slow table and copy entries to the fast table.

Request pagination – page replacement

Paging in and out of pages requires disk I/O and can be expensive, so a good page replacement algorithm should aim for fewer page misses

Optimal Permutation Algorithm (OPT)
First in first Out Replacement algorithm (FIFO)
Most recently not used permutation algorithm (LRU)
CLOCK replacement algorithm
Improved clock replacement algorithm

Memory management responsibilities – address translation

To make programming easier, programmers should only care about the logical addresses of instructions and data when writing programs. The conversion of logical addresses to physical addresses (a process called address relocation) is the responsibility of the operating system, which ensures that programmers write programs without having to worry about physical memory.

The specific address translation mode is described as follows.

Memory management responsibilities – storage protection

The operating system (OS) must provide memory protection. Ensure that each process runs in its own storage space without interfering with each other.

Operating system is programmer internal work, training good internal work to go further ah, is also my technology this week to share the content. Like you can follow my public account “Forrest Gump’s Code Road”, focus on back-end technology sharing.

See materials: Wikipedia, Baidu Encyclopedia, Wang Dao teacher course

Operating system storage management, chew over the people are super god!!