Recently, I read the computer operating system and Linux kernel and felt it deeply. I don't think it's so important for the programming language.
Basic segmented storage management
As we all know, an executable file is generally stored on disk, but the address space of the process needs to be occupied by memory
Generally speaking, when an executable file is not running, it is a file stored on disk, but it must be put into memory when it is running. This is called a process
Process address space: the address space of the process: it is divided into several 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
"Addressing each segment from 0" here is a relative concept, not an absolute address
Memory allocation rule: allocate in segments. Each segment occupies a continuous space in memory, but each segment can not be adjacent.
The general section can be divided into:
- Code segment: binary machine code. The code segment is read-only and can be shared by multiple processes;
- Data segment: stores initialized variables, including global variables and initialized static variables;
- Uninitialized data segment: stores uninitialized static variables, that is, BSS segments;
- Heap: used to store dynamically allocated variables;
- Stack: used for function calls, saving function return values, parameters, etc;
Coverage and switching technologies have to be mentioned here
In traditional computers, when an executable file is executed, it is generally directly put the executable file into memory for execution, but when the size of the executable file is larger than the memory, the memory will be full, which is obviously not feasible. Therefore, coverage and switching technology are produced.
Coverage technology: the program is divided into multiple segments (multiple modules). The commonly used segments are resident in memory, and the infrequently used segments are transferred into memory when needed. Memory is generally divided into fixed area (the segment put into the resident memory) and several coverage areas.
This method must be declared by the programmer, and the operating system completes the automatic coverage. Disadvantages: opaque to users, increasing the programming burden. Therefore, switching technology is produced
The design idea of exchange (SWAP) technology: when the memory space is tight, the system will temporarily replace some processes in the memory out of the external memory, and replace some processes in the external memory that have run conditions into the memory (the processes are dynamically scheduled between the memory and the disk)
These are two ways to expand memory.
There are also several modes for memory management.
Single continuous allocation: in the single continuous allocation mode, memory is divided into system area and user area. The system area is usually located in the low address part of the memory, which is used to store operating system related data; The user area is used to store user process related data.
There can only be one user program in memory, and the user program monopolizes the whole user area space.
- Advantages: simple implementation; No external debris; Memory can be expanded by using Overlay Technology; Memory protection is not necessary (eg: early PC operating system MS-DOS).
- Disadvantages: it can only be used in single user and single task operating systems; Internal debris; Memory utilization is extremely low.
Fixed partition allocation: in the 1960s, a system supporting multi-channel programs appeared. In order to load multi-channel programs in memory without mutual interference, the whole user space was divided into several fixed size partitions, and only one job was loaded in each partition, thus forming the earliest The simplest memory management method that can run multi-channel programs.
pattern:
- Equal partition size: lack of flexibility, but it is very suitable for controlling multiple identical objects with one computer (it may lead to overtalent)
- Unequal partition sizes: increased flexibility to meet the needs of processes of different sizes. Divide according to the size of jobs that often run in the system (for example, divide multiple small partitions, moderate partitions and a small number of large partitions)
The operating system needs to establish a data structure - a partition description table to realize the allocation and recycling of each partition. Each table item corresponds to a partition, which is usually arranged according to the partition size. Each table item includes the size, starting address and status of the corresponding partition (allocated or not).
When a user program is to be loaded into memory, the operating system kernel program retrieves the table according to the size of the user program, finds an unallocated partition that can meet the size, allocates it to the program, and then changes the status to "allocated".
- Advantages: simple implementation, no external fragments.
- Disadvantages: a. when the user program is too large, all partitions may not meet the requirements. At this time, coverage technology has to be adopted, but this will reduce the performance; b. Internal fragmentation will occur and memory utilization is low.
Dynamic partition allocation: dynamic partition allocation is also called variable partition allocation. This allocation method does not divide the memory partition in advance, but dynamically establishes the partition according to the size of the process when the process loads the memory, and makes the size of the partition just meet the needs of the process. Therefore, the size and number of system partitions are variable.
Dynamic partition allocation has no internal fragments, but has external fragments.
- Internal fragments are allocated to the memory area of a process. If some parts are not used.
- External fragmentation means that some free partitions in memory are too small to be used.
The above cases are stored in a continuous way, that is, a process occupies a whole block of continuous space in memory, but it lacks flexibility. The following describes the discontinuous allocation method
Basic paging storage management: divide the memory space into partitions of equal size (for example, 4KB per partition). Each partition is a "page frame", or "page frame", "memory block" and "physical block". Each page frame has a number, i.e. "page frame number" (or "memory block number", "page frame number", "physical block number"). The page frame number starts from 0.
The address space of the user process is also divided into areas equal to the size of the page box, which is called "page" or "page". Each page also has a number, namely "page number", which also starts from 0.
The operating system allocates memory space for each process in page boxes. Each page of the process is put into a page box. In other words, the page of the process has a one-to-one correspondence with the page box of memory.
Each page does not need to be stored continuously or in order. It can be placed in non adjacent page boxes.
After paging the process address space, how should the operating system realize the conversion from logical address to physical address?
The relocation register stores the starting position of the loading module. The "starting address" of the module in the memory + the "offset" of the target memory unit relative to the starting position
In order to know the location of each page of the process in memory, the operating system should establish a page table for each process.
The quick table and two-level mapping table are not explained here. Those who are interested can view them by themselves.
Back to the original problem, basic segmented storage management
Segment table: the program is divided into multiple segments, and each segment is loaded into memory discretely. In order to ensure the normal operation of the program, the storage location of each logical segment must be found from the physical memory. For this purpose, it is necessary to establish a segment mapping table for each process, referred to as "segment table". (similar to paging storage management)
According to the above, each segment is addressed from 0, but how is it mapped to memory? According to the segment number!
The logical address structure of the segmentation system consists of segment number (segment name) and intra segment address (intra segment offset). For example:
Segment table and page table are generally stored in memory. When a process runs, a segment table register will be passed in to identify where the segment table of the process is. To map memory
Segmentation is easier to share and protect information than paging
Code that cannot be modified is called pure code or reentrant code (not a critical resource). Such code can be shared. Modifiable code cannot be shared (for example, there are many variables in a code segment, and the concurrent access of each process may cause data inconsistency).
The contemporary computer generally adopts the segment page storage management mode
Segment page storage management
The logical address structure of the segment page system consists of segment number, page number and on page address (on page offset). For example:
Corresponding segment table and page table
Let's talk about virtual memory
Principle of Locality:
- Time locality: if an instruction in the program is executed, it is likely to be executed again soon; If a data has been accessed, it is likely to be accessed again soon. (because there are a lot of loops in the program)
- Spatial locality: once a program accesses a storage unit, the nearby storage unit is likely to be accessed soon. (because many data are stored continuously in memory, and program instructions are stored sequentially in memory)
Therefore, it is based on cache memory
Is an associative memory
The idea of cache technology: put the data that will be accessed frequently in the near future into higher speed memory, and the data that cannot be used temporarily into lower speed memory.
Based on the principle of locality, when the program is loaded, the part that will soon be used in the program can be loaded into memory, and the part that cannot be used temporarily can be left in external memory, so that the program can start to execute.
In the process of program execution, when the accessed information is not in memory, the operating system is responsible for transferring the required information from external memory to memory, and then continue to execute the program.
If the memory space is insufficient, the operating system is responsible for changing out the temporarily unused information in the memory to external memory.
Under the management of the operating system, it seems to users that there is a memory much larger than the actual memory, which is virtual memory
As an embodiment of the virtualization of the operating system, the actual physical memory size has not changed, but has been logically expanded.
Virtual memory has the following three main characteristics:
- Multiplicity: it is not necessary to load all the memory at one time when the job is running, but it is allowed to be divided into multiple calls into memory.
- Interchangeability: the job does not need to be resident in memory all the time when the job is running, but allows the job to be swapped in and out during the job running.
- Virtualization: it logically expands the memory capacity, so that the memory capacity seen by the user is much larger than the actual capacity.
Virtual memory technology allows a job to be called into memory multiple times. If continuous distribution is adopted, it will be inconvenient to realize. Therefore, the implementation of virtual memory needs to be based on the memory management mode of discrete allocation.
demonstration:
Create a new source file
#include<stdio.h>
int main() {
printf("Hello World\n");
return 0;
}
compile
gcc 02.c -o he ./he Hello World
Let's take a look at this file
readelf -a he
Basic information of the file and some related parameters
# Basic information of the file ELF Header: Magic: 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00 Class: ELF64 Data: 2's complement, little endian Version: 1 (current) OS/ABI: UNIX - System V ABI Version: 0 Type: DYN (Shared object file) Machine: Advanced Micro Devices X86-64 Version: 0x1 Entry point address: 0x1060 Start of program headers: 64 (bytes into file) Start of section headers: 14712 (bytes into file) Flags: 0x0 Size of this header: 64 (bytes) Size of program headers: 56 (bytes) Number of program headers: 13 Size of section headers: 64 (bytes) Number of section headers: 31 Section header string table index: 30
section table (what we call page table)
Section Headers:
[Nr] Name Type Address Offset
Size EntSize Flags Link Info Align
[ 0] NULL 0000000000000000 00000000
0000000000000000 0000000000000000 0 0 0
[ 1] .interp PROGBITS 0000000000000318 00000318
000000000000001c 0000000000000000 A 0 0 1
[ 2] .note.gnu.propert NOTE 0000000000000338 00000338
0000000000000020 0000000000000000 A 0 0 8
[ 3] .note.gnu.build-i NOTE 0000000000000358 00000358
0000000000000024 0000000000000000 A 0 0 4
[ 4] .note.ABI-tag NOTE 000000000000037c 0000037c
0000000000000020 0000000000000000 A 0 0 4
[ 5] .gnu.hash GNU_HASH 00000000000003a0 000003a0
0000000000000024 0000000000000000 A 6 0 8
[ 6] .dynsym DYNSYM 00000000000003c8 000003c8
00000000000000a8 0000000000000018 A 7 1 8
[ 7] .dynstr STRTAB 0000000000000470 00000470
0000000000000082 0000000000000000 A 0 0 1
[ 8] .gnu.version VERSYM 00000000000004f2 000004f2
000000000000000e 0000000000000002 A 6 0 2
[ 9] .gnu.version_r VERNEED 0000000000000500 00000500
0000000000000020 0000000000000000 A 7 1 8
[10] .rela.dyn RELA 0000000000000520 00000520
00000000000000c0 0000000000000018 A 6 0 8
[11] .rela.plt RELA 00000000000005e0 000005e0
0000000000000018 0000000000000018 AI 6 24 8
[12] .init PROGBITS 0000000000001000 00001000
000000000000001b 0000000000000000 AX 0 0 4
[13] .plt PROGBITS 0000000000001020 00001020
0000000000000020 0000000000000010 AX 0 0 16
[14] .plt.got PROGBITS 0000000000001040 00001040
0000000000000010 0000000000000010 AX 0 0 16
[15] .plt.sec PROGBITS 0000000000001050 00001050
0000000000000010 0000000000000010 AX 0 0 16
[16] .text PROGBITS 0000000000001060 00001060
0000000000000185 0000000000000000 AX 0 0 16
[17] .fini PROGBITS 00000000000011e8 000011e8
000000000000000d 0000000000000000 AX 0 0 4
[18] .rodata PROGBITS 0000000000002000 00002000
0000000000000010 0000000000000000 A 0 0 4
[19] .eh_frame_hdr PROGBITS 0000000000002010 00002010
0000000000000044 0000000000000000 A 0 0 4
[20] .eh_frame PROGBITS 0000000000002058 00002058
0000000000000108 0000000000000000 A 0 0 8
[21] .init_array INIT_ARRAY 0000000000003db8 00002db8
0000000000000008 0000000000000008 WA 0 0 8
[22] .fini_array FINI_ARRAY 0000000000003dc0 00002dc0
0000000000000008 0000000000000008 WA 0 0 8
[23] .dynamic DYNAMIC 0000000000003dc8 00002dc8
00000000000001f0 0000000000000010 WA 7 0 8
[24] .got PROGBITS 0000000000003fb8 00002fb8
0000000000000048 0000000000000008 WA 0 0 8
[25] .data PROGBITS 0000000000004000 00003000
0000000000000010 0000000000000000 WA 0 0 8
[26] .bss NOBITS 0000000000004010 00003010
0000000000000008 0000000000000000 WA 0 0 1
[27] .comment PROGBITS 0000000000000000 00003010
000000000000002a 0000000000000001 MS 0 0 1
[28] .symtab SYMTAB 0000000000000000 00003040
0000000000000618 0000000000000018 29 46 8
[29] .strtab STRTAB 0000000000000000 00003658
0000000000000200 0000000000000000 0 0 1
[30] .shstrtab STRTAB 0000000000000000 00003858
000000000000011a 0000000000000000
Segment table
Program Headers:
Type Offset VirtAddr PhysAddr
FileSiz MemSiz Flags Align
PHDR 0x0000000000000040 0x0000000000000040 0x0000000000000040
0x00000000000002d8 0x00000000000002d8 R 0x8
INTERP 0x0000000000000318 0x0000000000000318 0x0000000000000318
0x000000000000001c 0x000000000000001c R 0x1
[Requesting program interpreter: /lib64/ld-linux-x86-64.so.2]
LOAD 0x0000000000000000 0x0000000000000000 0x0000000000000000
0x00000000000005f8 0x00000000000005f8 R 0x1000
LOAD 0x0000000000001000 0x0000000000001000 0x0000000000001000
0x00000000000001f5 0x00000000000001f5 R E 0x1000
LOAD 0x0000000000002000 0x0000000000002000 0x0000000000002000
0x0000000000000160 0x0000000000000160 R 0x1000
LOAD 0x0000000000002db8 0x0000000000003db8 0x0000000000003db8
0x0000000000000258 0x0000000000000260 RW 0x1000
DYNAMIC 0x0000000000002dc8 0x0000000000003dc8 0x0000000000003dc8
0x00000000000001f0 0x00000000000001f0 RW 0x8
NOTE 0x0000000000000338 0x0000000000000338 0x0000000000000338
0x0000000000000020 0x0000000000000020 R 0x8
NOTE 0x0000000000000358 0x0000000000000358 0x0000000000000358
0x0000000000000044 0x0000000000000044 R 0x4
GNU_PROPERTY 0x0000000000000338 0x0000000000000338 0x0000000000000338
0x0000000000000020 0x0000000000000020 R 0x8
GNU_EH_FRAME 0x0000000000002010 0x0000000000002010 0x0000000000002010
0x0000000000000044 0x0000000000000044 R 0x4
GNU_STACK 0x0000000000000000 0x0000000000000000 0x0000000000000000
0x0000000000000000 0x0000000000000000 RW 0x10
GNU_RELRO 0x0000000000002db8 0x0000000000003db8 0x0000000000003db8
0x0000000000000248 0x0000000000000248 R 0x1
Mapping between segment table and page table
Section to Segment mapping: Segment Sections... 00 01 .interp 02 .interp .note.gnu.property .note.gnu.build-id .note.ABI-tag .gnu.hash .dynsym .dynstr .gnu.version .gnu.version_r .rela.dyn .rela.plt 03 .init .plt .plt.got .plt.sec .text .fini 04 .rodata .eh_frame_hdr .eh_frame 05 .init_array .fini_array .dynamic .got .data .bss 06 .dynamic 07 .note.gnu.property 08 .note.gnu.build-id .note.ABI-tag 09 .note.gnu.property 10 .eh_frame_hdr 11 12 .init_array .fini_array .dynamic .got
Others are specific mappings and are not summarized.
Let's verify another correlation:
As we know, executable files are stored in the segmented storage mode of memory image. When the process is running, pages and segments are stored in the memory in the page storage mode of the mapping table, but logically they are still placed in the memory in the segmented mode.
Let's look at the occupancy of segmented storage (each segment is addressed from 0)
nm -C he
0000000000004010 B __bss_start
0000000000004010 b completed.8060
w __cxa_finalize@@GLIBC_2.2.5
0000000000004000 D __data_start
0000000000004000 W data_start
0000000000001090 t deregister_tm_clones
0000000000001100 t __do_global_dtors_aux
0000000000003dc0 d __do_global_dtors_aux_fini_array_entry
0000000000004008 D __dso_handle
0000000000003dc8 d _DYNAMIC
0000000000004010 D _edata
0000000000004018 B _end
00000000000011e8 T _fini
0000000000001140 t frame_dummy
0000000000003db8 d __frame_dummy_init_array_entry
000000000000215c r __FRAME_END__
0000000000003fb8 d _GLOBAL_OFFSET_TABLE_
w __gmon_start__
0000000000002010 r __GNU_EH_FRAME_HDR
0000000000001000 t _init
0000000000003dc0 d __init_array_end
0000000000003db8 d __init_array_start
0000000000002000 R _IO_stdin_used
w _ITM_deregisterTMCloneTable
w _ITM_registerTMCloneTable
00000000000011e0 T __libc_csu_fini
0000000000001170 T __libc_csu_init
U __libc_start_main@@GLIBC_2.2.5
0000000000001149 T main
U puts@@GLIBC_2.2.5
00000000000010c0 t register_tm_clones
0000000000001060 T _start
0000000000004010 D __TMC_END__
Operating system memory management, such as terror.