16. Memory usage and segmentation

【README】

1. The content of this paper is summarized from B standing 《 operating system - Li Zhijun, teacher of Harbin Institute of technology 》, The content is great , Wall crack recommendation ;

---

【1】 Memory usage

【1.1】 The program is loaded into memory

1） Memory usage ： Put the program in memory ,PC The register points to the start address ;
2） Load the program into memory ;

【 The illustration 】

• _entry The address of the entry program is 0;
• Call 40 Indicates that the call offset is 40 Function of ;

problem ：

• The above code is stored on disk ; After loading into memory ,call 40 If the call offset is 40 The function of is problematic , Because the operating system program in memory from 0 Address start , therefore call 40 Call will report an error ;

resolvent ：

• call 40 Medium 40 It's the relative address , Need to change to call entry Base address +40, Such as entry The base address is 1000, Then change to call 1040 （ The above operation of modifying the memory address in the program is called relocation ）;

3） The process of loading a program into memory
Need to find a free memory , Its base address is A, Load the program on the disk into this memory , Execute relocation to modify the memory address in the program （ The specific method of relocation is to add all memory offsets in the loaded program to the base address of free memory A）;
Then the program fetches and executes , The program runs normally , Memory is also used smoothly ;

4） When to complete the relocation ？

• 1． Compile time ： For embedded systems, relocation can be completed at compile time , But not flexible ;
• 2． Onload ： When the program is loaded into memory , More flexible （ Non embedded systems generally use load time relocation ）; Such as when the program is loaded from disk to memory , Memory address in the program （ Address offset ） Add the base address of the program ;

4.1） Relocation advantages and disadvantages ：

• The program relocated at compile time can only be placed in a fixed location in memory （ rigid , When compiling, you need to determine the base address of the free memory storing the program ）;
• Once the program relocates during loading is loaded into memory, it cannot move （ flexible , When loading, the base address of the free memory storing the program is determined ）;

  Add ：

• Add 1：40 Is the logical memory address , Is the memory relative address , and 1040 Is the physical memory address , Is the absolute address of memory ;
• Add 2： Whether relocating at compile time or relocating at load time , Once the relocation operation , The memory address offset of program instruction operation cannot be modified ;
• This introduces new problems ： Many times, after the program is loaded into memory , It will still move ; That is, the business scenario is when the program is running , The memory address offset of its operation needs to change ; Such as the swap in and swap out operation of the memory page where the program is located ;

5） An important concept ： In exchange for swap

  Initial state ：

memory base address	Memory loaded process	Disk storage process
2000	process 2	process 3
1000	process 1

The first 1 Time Swap after ：

memory base address	Memory loaded process	Disk storage process
2000	process 2	process 1
1000	process 3

The first 2 Time Swap after ：

memory base address	Memory loaded process	Disk storage process
2000	process 1	process 2
1000	process 3

 Swap It means ：

• Small memory space , Big disk space . When the memory cannot hold the process 3 when , Will first put the process 1 Change out to disk , Then put the process on the disk 3 Switch into memory ;
• In short swap It refers to the operation that the process switches in and out between memory and disk ;
• Alignment process 1 Multiple exchange out and exchange in operations , Its memory address （ Or base address ） It's bound to change , This will cause the inland address of program instruction operation to change , Therefore, relocating at compile time or load time will lead to swap Process execution error after ;

So it should be runtime relocation , Instead of relocating at compile time or load time ;

---

【1.2】 Runtime relocation  

1） Runtime relocation definitions ： refer to Only when executing instructions , Add the memory offset of the instruction to the base address to get the memory address of the operand ; No matter how many times it is done swap, The inland addresses relocated at runtime are all correct ;

2） Address translation （ Also called relocation ）：

• Runtime relocation , Also called address translation ; The physical address must be calculated from the logical address for each instruction executed ;
• Every time swap after , The memory base address of the process will be modified , Modified memory base address base Stored in the process structure PCB Inside ; That is, the process in the initial state 1 Of base be equal to 1000, The first 2 Time swap Post process 1 Of base be equal to 2000; In this way, the absolute physical address corresponding to the memory address offset in the instruction can be calculated correctly ;
• Add ： When the process is running ,pcb The base address of the process stored in base It will be sent to the base register for storage , For subsequent calculation ;

3） Summary ： How the program uses memory ？

• step 1： Find a free memory in memory , And locate the base address base（ The starting address of this free memory ）, And send it into the process pcb For storage ;
• step 2： Put the program into the step 1 In the requested free memory , With base Is the starting address ;
• step 3： When process scheduling or context switching ,pcb Inside base The base address will be sent to the base register for storage ;
• step 4： Every time an instruction is executed , Address translation （ relocation ）, That is, add the memory address offset to the base address base Get the actual physical memory address , This physical memory address either stores program instructions or program operands ;

Go through the above steps , The program is executed ;

【 example 】 Multi process execution time base address switching

• step 1： Initial state , process 1 The base site of 2000, process 2 The base site of 1000;

• step 2：cpu Execution process 1, process 1 Of pcb Base address of storage 2000 Send to the base register ;PC Register addressing to instruction mov ax,[100] And send it to IR register ;
• step 3： Execution instruction mov ax,[100] when , hold 100 Offset and base address 2000 Add to get the physical memory address of the operand （ Base addressing ）;

• step 4：cpu From process 1 Switch to process 2 （switch）;
  • After switching , process 2 Of pcb Stored base address 1000 Send to the base register ; In this way, the base address of the operand address of the subsequent instructions is modified to 1000 了 , After process switching The logical address can be correctly translated into the purpose of physical address ;

 

---

【2】 Memory segmentation

1） A program consists of several parts （ paragraph ） form , Each paragraph has its own characteristics , Such as main program , Variable sets , function library , The dynamic array , Stack, etc. ;
2） The memory address offset of the program in each part or segment is the relative address relative to the segment base address of the segment ;
3） How to locate specific instructions or data ： < Segment number , Offset within segment >

【 example 】mov [es:bx], ax
We need to put es Is the base address of the segment ,bx Translate the logical address of the offset into the physical memory address ;

 4） The benefits of program segmentation for storage （ Segmented storage adopts Divide and conquer thoughts ）

• benefits 1： Instead of putting the whole program into memory , Instead, put each segment into memory separately , Improve memory utilization ;
• benefits 2： Doing it swap when , Not to switch the whole process in or out , Instead, a segment of the process is swapped in or out , Improved swap efficiency ; And reduced swap frequency ;
• benefits 3： Program segments or code segments are read-only ;（ Variable sets ） Data segments are writable ; Segmented storage can avoid the scenario of code being written by mistake ;

 
5） After the program is stored in sections , Each segment has its own base address ;
So the process pcb It is necessary to store the segment base address of multiple segments of the corresponding program ; As shown in the process segment table ：
                                 surface 1 Process segment table

Segment number	Base address	length	Protect
0	180K	150K	R
1	360K	60K	R/W
2	70K	110K	R/W
3	460K	40K	R

  Add ： paragraph 0 The offset 30 And segment 1 The offset 30 The translated physical memory address is different , Because their base sites are different ;

6）GDT And LDT
You can think of the operating system as a process , The corresponding segment table is called GDT, The structure is the same as that in table 1 similar ;
Each process also has its own segment table （ Used to store the base address of multiple segments of the program ）, As shown in the table 1 Shown , The corresponding structure is LDT;

Summary ： Steps to use memory in case of program segmentation ;

• step 1： Divide the program into segments , Including code snippets , Data segments, etc ;
• step 2： Each segment finds a free memory in memory , And put the base address of this section of memory （ Initial address ） Send in LDT Table is stored （ As shown in the table 1 structure ）;LDT The table stores the segment base addresses of multiple segments of the program ;
• step 3： hold LDT The table is assigned to the corresponding process PCB; At this point, the program has been loaded into memory ;
• Last ：PC Register according to pcb Set the initial value , Fetch execution fetch execution , Every time an instruction is executed , All query LDT Table finds the segment base address , Add the base address of this segment to the address offset to get the physical memory address , For subsequent addressing operations ;
• Add ： ldt The base address of the table is sent ldtr register ;

【 example 】 Address translation based on segment base address
1） process 1 Of LDT Table data

Segment number	Section base address
1	1000
0	3000

2） process 2 Of LDT Table data

Segment number	Section base address
1	7000
0	5000

3） Instructions

• process 1 Of mov [cs:40], ax, among cs The value of the code segment register is 0, From ldt The addressing subscript is 0 Section base address of （3000）; therefore cs:40 The physical address obtained is 3000+40=3040;
• process 2 Of mov [cs:40], ax, among cs The value of the code segment register is 0, From ldt The addressing subscript is 0 Section base address of （5000）; therefore cs:40 The physical address obtained is 5000+40=5040;

Because when cpu From process 1 Switch to process 2 when , First pcb from pcb1 Switch to pcb2, therefore pcb Stored ldt The base address will also be switched to ldt2 And send it to ldtr Register storage ;
So once ldtr Given a new value , Then the segment base address will be transferred from the process 1 Change to process 2 Section base address of , Achieve the purpose of multi process switching operation ;