标签：虚拟地址地址内存页表空闲页面

内存

1.存储体的存储结构

存储的分层思想被用来划分存储体的实际结构,这可以更加有效的管理程序

存储层次

容量：从上往下容量依次减小
访问速度：从下往上则越来越快

2.无存储体的存储结构

为什么要从无存储的存储结构去了解内存,老实讲,一上去就了解内存的分段分页机制,并不懂得这种设计方式,加上内存的封装,很多事就只是徒有表象了,了解其本质和设计理念对于内存才是最重要的.

最早的时候,一段程序的执行都是直接映射在物理内存到中的.
所以就会引发一定的问题,每一个程序都直接映射在物理内存当中,就会发生冲突:

进程冲突物理内存

这还是不包括操作系统级别的进程,如果还存在操作系统级别的进程,那就会存在一开始就有一段内存已经分配好了,于是就需要对内存结构进行进一步的划分

3.存储模型

了解ROM和RAM:

ROM（只读存储器）： ROM是一种只读的存储器，其内容在制造过程中被写入，通常无法被修改。ROM中的数据无法被普通用户或程序修改或删除。操作系统中的一部分通常被存储在ROM中，以确保其在计算机启动时可用，并提供基本的系统功能。这部分被存储在ROM中的操作系统被称为"固件"（firmware），它包含了计算机启动时所需的最基本的指令和设置。
RAM（随机访问存储器）： RAM是一种易变的存储器，用于临时存储数据和程序。它具有随机访问的特性，即可以任意读取和写入数据。RAM存储器通常用于存储计算机正在运行的操作系统、应用程序以及它们所使用的数据。当计算机处于开机状态时，操作系统和应用程序都会加载到RAM中，以便CPU可以快速访问和执行。RAM是一种临时存储器，当计算机关闭时，RAM中的数据将被清除。

于是,根据构思可以创建出操作系统的一片内存区域,和用来驱动硬件的一片内存区域,以及我们可以放置用户程序的一片区域.

内存模型.drawio

所以通常来说操作系统程序都会被加载到RAM区域运行，而ROM由于固件的原因，常常用来引导和加载程序，系统设置，初始化硬盘等和其他固定的区域，这片内存就很安全。
而RAM区域则是我们通常所了解的主存区域，如果操作系统级别的代码都加载到RAM区域运行
BIOS设置界面：一般就是我们ROM里面记载的一些硬件信息，比如设备的启动顺序，硬件配置，在开机过程中按下特定的键。

4.程序的地址冲突

例如：

 mov byte [0x100], 1  ; 将值1存储到地址0x100

像这样的代码段，如果我在多个程序中出现，就会发生的地址的冲突，当然，这个上文也说过，这里的地址由于没用虚拟地址的映射，因此我们的逻辑地址就是物理地址

或者：

 jmp 0x1000  ; 使用立即数0x1000作为跳转目标

地址冲突

如果同时存在多种跳转指令的代码，这意味着每次的逻辑转移都是实实在在的物理转移，这种内存的风险和转移代价实在太大

所以，如果每一个程序都意味着占用一段内存，而每段程序的起始地址和终止地址我们需要如何去决定，才能不窜台，也就意味着进程之间的隔离。

保护每一个程序的安全性，同时让程序拥有自己的内存地址。

5.地址空间

假设这是我们理想的内存情况

地址冲突2

第一个程序的逻辑地址与他的物理地址之间没有进行偏移，而第二个程序的初始逻辑地址和他的物理地址之间进行了偏移

因此,需要进行地址的重定位:

这里采用的是动态重定位的方式:在程序运行时进行的一种重定位方式,可执行程序的地址引用使用相对地址或偏移量，而不是绝对地址。在程序运行时，通过使用基址寄存器或运行时计算，将相对地址映射为实际的物理地址

来理解基址寄存器和变地寄存器:

基址寄存器:保存数据内存的起始位置
变址寄存器:存储程序的长度

可以联想到什么? 数组

是的,数组的内存空间是连续且递增的,如果用基址寄存器去保存数组的其实地址,而用变址寄存器来保存数组的长度,这样就可以通过基址的偏移量去访问数组里的内容了,而当我们将数组看成内存程序的开始位置.便能立刻解决地址偏移的问题了.

地址冲突3

但是这样的改变,对于JMP 0x0003指令来说,他就需要通过ADD指令 1001+0003 = 1004了,这种方式的偏移就不如同

mov si, [BX+3]  ; 将BX寄存器中的值加上3作为偏移量，读取对应的内存值并存入SI寄存器
jmp si  ; 跳转到SI寄存器中存储的地址处执行

除此之外,还需要判断是否内存越界的问题,不然安全得不到保障就会越界其他程序,因此每一次内存的偏移都要去判断是否发生越界,也就是去cmp:

cmp bx, array_end ; 比较数组的长度

因此这种内存的排版,每次程序内部都需要去执行add和cmp,就意味着性能并不是最高的.

6.内存的交换

为什么会存在内存的交换

内存不足,假设我的内存空间足够多,能有几百个G的内存大小,如果按需装入,或许也是够的,但是目前计算机通常的主存空间都在8~32G内存空间左右(按个人Pc来算),如果将没有用的进程重新放回磁盘,就可以节省必要的空间,因为RAM的造价并不像磁盘的造假那么容易,这就导致了内存的空间其实十分的重要.
例如:一个简单的应用程序可能就需要几十MB的内存空间,而在操作系统启动之初,往往就需要占用几百MB甚至几GB的情况,这还是不算上用户进程的,甚至有一些服务驱动等程序也需要占用相当一部分内存空间.

因此,面对内存不足的第一种方式便是交换:

内存交换

注意:这里的A~D进程的数据指的是部分数据或者全部数据
性能上的缺点:磁盘和主存之间不断发生IO操作,对CPU的执行来说,过度耗费资源,且进程之间的切换,意味着寄存器等资源需要来回的该换,这种技术造成最明显的缺点就是内存的空间利用率没有很高,因为产生了内存碎片
内存碎片是什么:应用进程在进去内存的换入换出时,因进程被换出导致内存空闲,而需要被换出的空闲内存做分配空间时内存不足就会导致内存碎片.比如,上述图例中,A进程在最后换出,但换入了一个比A进程还大的应用进程,这时,A的换出的空闲内存就不能提供给此内存,即使有比A进程小的应用进程,这种内存的利用率也依然不能达到百分之一百,只会源源不断的造成内存的碎片问题.

解决内存碎片的办法:内存紧缩(内存紧凑)

内存紧缩

其实内存的紧缩在行为上也就如同数组元素的复制,这种代价也很高,相当于将这个进程重写到另外一个位置,如果此时B进程之上还有更多的进程,那就意味着都重写到另外一个位置.

7.段的定义

段的定义是面向谁的?

面向人和程序员,可以更好地组织和管理内存.也就是说计算机将每一个段都一视同仁地认为是一片内存区域而已

实际上在逻辑层次上段的划分是连续的,但是物理内存上并不是连续的

常见的段的划分:
- 代码段:用来存放指令,运行代码的一片内存空间,一般情况下属于只读
- 数据段:用来存放已初始化的全局变量和static变量的内存区域,生命周期是随着整个程序走,程序关闭,生命周期结束,可读可写
- BSS段:用来存放未初始化的全局变量和static变量,一般BSS段都紧跟数据段的后面
- rodata段:只读数据段,光听名字就知道只能读的数据段,这样的数据段内存放的一般都是常量,比如字符串常量,数字常量
- 栈段:用来存放一些局部变量,也就是一些运行时变量,生命周期随代码块的结束而结束.可读可写
- 堆段:运行时可动态分配的空间,堆中变量的生存空间随代码的具体实现而生成或者消亡.可读可写
为什么不将未初始化的变量放入数据段里,为什么需要BSS段?

通常来说未初始化的变量,都会赋予初值,而这个值一般来说都是0或者null值,也就是说放在BSS段里的变量内容基本都是0和null值,这样看上去更加规整,也利于操作系统进行管理,这个问题,其实是一种决策问题,如果直接放入数据段中,根据编译器的不同,也是有可能的,也可能是因为0和null值所占内存的空间大小相比于显示的值来说,更节省内存空间,程序的大小更低一些而考虑设计到.

以下是一个C语言样例分别展示常见的段:

#include <stdio.h>
#include <stdlib.h>

// 代码段（Code Segment）
void foo() {
    printf("This is the code segment.\n");
}

// 数据段（Data Segment）
int globalData = 10;

// BSS段（Block Started by Symbol）
int globalBSS;

// rodata段（Read-Only Data Segment）
const char* message = "This is the rodata segment.";

int main() {
    // 栈段（Stack Segment）
    int stackVariable = 20;
    
    // 堆段（Heap Segment）
    int* heapVariable = (int*)malloc(sizeof(int));
    *heapVariable = 30;

    foo();
    
    printf("Global Data: %d\n", globalData);
    printf("Global BSS: %d\n", globalBSS);
    printf("Message: %s\n", message);
    printf("Stack Variable: %d\n", stackVariable);
    printf("Heap Variable: %d\n", *heapVariable);

    free(heapVariable);
    
    return 0;
}

8.内存的分配

一个进程被分配一个内存，这个大小是固定的吗？

以前的程序,我们可以说是固定的,但现在固定的程序基本不可能满足我们,所以说,基本都是动态分配内存

如果通过内存交换技术,动态分配意味着什么?

根据上述对数据进行拆分成不同的段,假如堆段要进行增长,意味着内存的分配不能再是连续的了,而是可能要多分配出一部分空间.

固定分配：预先分配一块大小的内存空间，如果空间不足，则需要分配更大的内存空间，这种分配方式直接，但弊端很明显，是固定的空间大小，空间利用率不确定。
增量分配：逐步增加内存的大小，当空间不足时，会先分配一块比较小的，然后再逐渐增加，但是弊端依然很明显，执行的次数和操作就很多。
按需分配：根据实际的需求增加内存的大小，初始可能会分配很小的内存，根据需求调制内存大小的分配，同样，内存的分配频率也很高。

动态内存分配

在不涉及虚拟内存技术的时候，预留的内存空间其实会面临很多问题：

越界问题
内存过少分配
内存碎片

9.内存的管理

在进行动态的内存分配时，操作系统必须加以管理

目标：有效的管理内存，以满足内存的分配需求，高效地利用内存

空闲内存块的跟踪：操作系统需要跟踪哪些内存块是当前可用的，即没有被分配给任何进程的内存块。这可以通过使用数据结构（如位图、链表、树等）来记录内存块的状态和位置来实现。每当有内存块被分配或释放时，相应的数据结构会进行更新。
内存分配算法：当进程请求分配内存时，空闲内存管理模块会使用特定的分配算法来选择合适的空闲内存块。常见的内存分配算法包括首次适应、下次适应、最佳适应和最坏适应等。这些算法根据不同的策略选择合适大小的内存块，以尽量避免碎片化和提高内存利用率。
空闲内存合并与分割：在内存块被释放时，空闲内存管理模块可能需要将相邻的空闲内存块进行合并，以创建更大的连续空闲内存块。相反，在分配内存时，如果没有足够大的连续空闲内存块，可以将一个大的空闲内存块分割成多个较小的内存块，以满足进程的需求。
内存回收与释放：当进程终止或释放内存时，空闲内存管理模块需要回收被释放的内存块，并将其标记为可用状态，以便后续的内存分配请求可以使用。这确保了内存可以被有效地重复利用。

位图：本身是一种数据结构，第一次听到这个脸都白了……，其实就是一种映射关系的数据结构，也有人说是bitmap，bit是比特的意思，1位的意思，而map就是一种映射关系，既然用来追踪这块内存是否空闲，那换一种方式去追踪位图这样的数据结构就可以知道那片内存是否空闲了。
- 再不济，举个例就明白了，假如有一片连续的内存区域，每个内存块大小为4个字节，共有16个内存，那需要的位图就是16位，2个字节，每一位表示对应索引的内存块是否空闲，因为是根据比特判断，1则表示有数据了，0则表示空闲。

可以看出其实位图本身也具备一定的内存空间，但是这种内存的空间开销其实非常小了，还能够提供高效的的内存管理方式，这种关联是通过索引的方式建立的。

链表：就是用链表的每一个节点去表示内存的空闲状况，H表示空闲的意思，P表示进程，也就是有占用情况意思，可以将每一个节点拿出来分开看就是内存的空闲状况，起始地址，内存的大小。
- 当需要分配内存时，操作系统会遍历空闲列表，查找满足分配要求的空闲内存块。一旦找到合适的内存块，操作系统将其分配给请求的进程，并更新空闲列表，删除或调整相应的节点，以反映内存块的分配情况。

空闲链表

无论是位图还是空闲链表的这种方式,其要求都是内存连续,也就是连续的内存分配管理

内存分配算法:
- 首次适应（First Fit）：该算法在空闲列表中找到第一个满足要求的空闲内存块。它是一种简单且快速的算法，但可能会导致碎片化问题。
- 最佳适应（Best Fit）：该算法在空闲列表中找到大小最接近所需内存的空闲内存块。它可以最小化内存碎片化，但需要更多的搜索时间。
- 最差适应（Worst Fit）：该算法在空闲列表中找到大小最大的空闲内存块，以容纳当前分配请求。它可以减少外部碎片化，但可能导致空闲内存块无法有效利用。
- 下次适应（Next Fit）：该算法从上次分配的位置开始搜索空闲内存块，以减少搜索时间。它适用于连续的内存分配请求。
- 快速适应（Quick Fit）：该算法维护多个不同大小的空闲链表，根据所需内存的大小选择相应的链表。它可以快速找到满足要求的空闲内存块，但可能需要更多的内存开销。

10.虚拟内存

10.1实模式

从8086模式谈起内存的分段机制

前面了解到段的定义是面向程序员的,内存的分段其实对于物理层次的地址空间上来说也是连续的
在8086模式中,由于16位的寄存器无法传输在20位的地址总线,所以选择用两种寄存器组合的形式去表示,即段基址寄存器+段偏移寄存器,这种设计的理念就是段一开始的设计思想.
- 例如:CS寄存器存储了当前正在执行的代码所在的段的起始地址。在执行指令时，CS:IP（指令指针寄存器）组合给出了下一条指令的物理地址。
- DS寄存器存储了默认的数据段的起始地址。当程序需要访问数据时，数据地址由DS:偏移量（数据在段中的偏移量）组合给出。
- SS寄存器存储了栈段的起始地址。栈是一种特殊的数据结构，用于存储局部变量、函数调用信息等。当程序执行函数调用时，栈用于保存返回地址和局部变量等信息。
```
ORG 1000h ; 指定代码段的起始地址

CODE SEGMENT
    START:
        MOV AX, 100h ; 将值0x100存储在寄存器AX中
        ADD AX, 200h ; 将值0x200添加到AX中
        MOV BX, AX   ; 将AX的值移动到BX寄存器中
        JMP END      ; 跳转到END标签
CODE ENDS

DATA SEGMENT
    VALUE DW 1234h ; 定义一个16位的变量VALUE，赋值为0x1234
DATA ENDS

END START       ; 定义程序结束点
```

cs_ip地址

这类情况所描述的就是实模式情况下的内存的管理形式,通过段的定义去主动将内存划分为多个段.

10.2保护模式

从80386的内存的分页机制开始了解起

内存的分段仅仅是程序员的视图来讲,他并没有节省或者提高内存的利用率,内存的实际占用情况是不会根据段改变的,所以在386的保护模式引入了一种新的内存基址,就是分页
- 分页需要什么?
  
  页表
页表是什么?

数据结构
页表是一种什么样的数据结构:

用来映射逻辑地址和物理地址的关系
其中80386中第一级为页目录表,第二级为页表,如果有多级页表,就是多级N表被命名为,可以这样理解,高一级页表管理下一级页表.
- 页表项是什么？
  
  可以理解为页表的基本单位
页表的分配位置:既然是种数据结构,其本身也需要相应的空间去存放,这个空间就是主存
- 页表项里面包含了什么?
  
  至少包含虚拟页号和物理页框号(指物理内存中的物理地址)

所以,我们不得不谈起,虚拟内存

虚拟内存的本质就是本身不属于真正的内存,那他属于什么?这个问题其实困扰了我很久,但是只有两个字就是机制
- 不理解,没关系,再来说虚拟地址是什么?
  
  虚拟地址是逻辑上的地址,也就是我们的逻辑地址,之所以称之为虚拟,是因为不真实.
  - 为什么要设计这种不真实的地址?
    
    为了让我们的程序足够自由,而不会因为真实地址发生冲突,简单点就是独立,自由.

#include <stdio.h>

int main() {
    int num = 10;
    int *ptr = &num;  // 指针ptr指向变量num的地址

    printf("num 的虚拟地址：%p\n", &num);
    printf("ptr 存储的虚拟地址：%p\n", &ptr);
    printf("ptr 指向的虚拟地址：%p\n", ptr);

    return 0;
}

指针用来表示某个变量的存储地址,当我们输出时,这个地址自然是虚拟的

再来讨论80386的虚拟地址范围

由于地址线32位:因此最多可以支持2^32（4,294,967,296）个虚拟地址,也就是4GB,大概的意思就是,我有那个想法,却没有真正落脚实现的空间,因此虚拟空间也是不存在的,而为了保证虚拟地址能够真正地被映射到物理地址上,采用了页表,这一过程的实现机制就被称为虚拟内存.

因此CPU会将虚拟地址发送给MMU(内存管理单元),交由MMU处理,而MMU使用页表来进行地址的转换,他们的职责大概就是:

页表记录了虚拟地址和物理地址之间的映射关系
MMU通过查找页表来实现地址转换。

虚拟地址被划分为页号和偏移量,虚拟地址本身是可见的,指向的地址空间是不存在的,他会随程序的运行去动态分配这个具体的数值.

虚拟地址

具体是如何划分的:

例如，虚拟地址为0x12345678。拆分后，高20位（页号）为0x12345，低12位（偏移量）为0x678。

在页表中，我们使用页号作为索引来查找对应的页表项。如果页表项大小为4字节（32位），则可以将页号乘以4来得到页表项的偏移地址。假设页表的基地址为0x80000000，则页号0x12345对应的页表项的地址为0x80000000 + (0x12345 * 4)。

那我们的偏移量用来干什么?

定位具体的物理地址,而页表则用来定位具体的物理页框地址(通常也叫页)
前面说过,虚拟地址的存在其实就是为了地址的不冲突,也就是专门用一块内存去保存远超物理地址上限的地址,例如32位地址情况下,可产生4GB的虚拟地址,用前20位来表示虚拟页号就会存在2²⁰ = 1,048,576 那么多个虚拟页号,一个虚拟页号意味着一个页表项.意味着1,048,576个页表项,而每个页表项通常在4字节左右(实际上甚至可能不止4字节),因为页表其实还包括许多标志字段,比如权限的字段,当然都是用位来进行标识,但这个页表至少也会是2²⁰ * 2² = 4MB(2²⁰ = 1MB)
- 但是!!!!!,这仅仅是一个进程的页表.为什么这么说?
- 我们说过虚拟地址是为了隔离冲突,当然一个进程分配一个完整的虚拟地址,如果还不够明白

页的映射问题

至于其中偏移量的细节没有画出,不过依然能看出来不同进程之间其实是可能存在相同地址,就比如两个C语言程序,分别去测试指针变量所保存的地址,那么这个我们虚拟地址也是有可能相同的,只不过通过页表映射到物理内存当中便不同了

这里还有一个非常重要的问题?使用了虚拟内存技术,也就是现在的内存分页机制,避免了物理内存的内存碎片吗?

没有,也就是段的机制和页的机制依旧没有解决内存碎片（内碎片）的问题

为什么?

例如,页A被进程B占用,其中0-3kb被B全部占用,而剩余的1kb则被浪费了.

当然，内存的释放是根据页释放的，所以也就不会产生小的内存无法提供给进程。

但同样存在页面合并,页面置换等策略来减少内存碎片的问题,这个先放一边,上面的问题依旧没有解决

4KB一个进程的页表,那100个进程,就是400MB,嗯,我点开任务管理器,一看压根不止100个,好了,内存本来就不充裕,一下子放了那么多页表,进程之间是享受了,但是又开始抢物理内存了,因此需要优化这种页表结构.

多级页表

它的设计思想是这样：原本的页表为了保证需要的4G的虚拟地址内存空间，所以将原本的页表变为二级页表，而用一级页表来映射到二级页表，大致是这样的：
这里的二级页表就是之前我们设计页表的雏形，假如有2²⁰ 个页表项,这里的二级页表理论上也需要具备这么多个页表项,因为一级页表每个页表项也是4KB(一级页号对应的页号索引就是2¹⁰,另外需要二级页表地址的索引也是2¹⁰ ),因此通过二级页表地址索引和二级页号就是2¹⁰ * 2¹⁰ 就又恢复到了2²⁰ 个虚拟地址了,地址即使索引的可选范围之内,但是通过一级页号去查找页表再通过一级页表中的二级页表索引地址去和二级页号去组合查找二级页表的页表号,感觉显得有点多此一举,且多引入了一个一级页表,这样不是梗浪费空间了.
- 我们来观察一级页表

其实可以很明显地观察出,一级页号与二级页表地址的关系是绑死的,例如一级页号根据虚拟地址的前10位划分,可表示的范围是0~1023,那无论取哪个值,这种映射关系其实是确定好的,就比如一级页号是1023,而二级页表是1000,这种映射关系一般就确定下来了,一般情况下,不会出现一级页号是1023,而二级页表变成了其他数值的情况,也正因为这种映射关系,确定了内存的分配,既然这种映射关系被绑定,所以二级页表就不会存在100%的使用情况

什么意思?

二级页表

既然这种映射关系确定好的,而二级页表地址和二级页号(虚拟地址中间10位)就确定了唯一一个二级页表

为什么这么说?

因为一个虚拟地址被拆分成一级页号索引和二级页号索引,其中一级页号确定了页表项中的位置,而页表项中映射关系又是确定好的,二级页号和二级地址组和生成的二级页表中的索引地址就是一定的.这种映射关系就是确定下来的,也就是说一个虚拟地址对应映射在二级页表中的索引位置也是确定下来的,除非他换了一个虚拟地址.也就是说一级页表的索引位置由虚拟地址的一级页号决定,而二级页表中的索引位置由虚拟地址的二级页号决定,三级页表的索引位置由.....

试想一下二级页表的创建是否在需要范围内的所有虚拟地址都有一个相应的页表项?

有了一级页表就意味着高10位的范围被确定下来了,至于中间10位所定位到的二级页表的位置,其实这并不重要,需要的时候再用就行,唯一的动态变量就成了虚拟地址的中间10位,这样二级页表的真正占用内存情况就不需要那么高,图中,一些一级页表项没有被使用到,就不必去分配二级页表项,这样空间的节省就大大节省了,因为一级页表也就仅仅4KB而已,而二级页表则是按项分配,根据实际情况内容分配.

应该会有人问多级页表按需分配二级页表,那一级页表就不可以吗?

实际上,一级页表可以进行按需分配页表项,但是与多级页表相比,一级页表的查找是通过线性查找,而多级页表是通过索引的方式,从效率上来说,多级页表效率更高,且这种分层的管理,更适合对内存进行管理,更加灵活.

以上就是80386的内存分页的实现内容,其中页表内容不仅仅物理页框号,还有着其他内容,比如一些标志位,用来判断读写的权位,或者是用户级别系统级别的位,还有些表示此页是否被访问过.记载了页的一些具体信息,

TLB:快表(转测缓冲区)

为什么存在TLB?

为了减少对页表的查找(也就是虚拟地址和物理地址的映射),内存地址的访问频率其实是存在一定情况的,因为实际的虚拟内存地址并不会使用过多,也就意味着多个页表项不会被少量访问的情况其实较少,而是少个页表项被多次访问

同样快表的页表结构也是类似于页表的结构,只不过是通过硬件实现,而不是通过内存实现,每次在进行虚拟地址映射到物理地址的时候,MMU都会去先查找TLB,当需要的页表项也就是映射关系在其TLB中,就会直接通过快表映射.

什么是缺页异常？

当程序试图访问尚未分配实际物理内存的虚拟内存页面时，操作系统就会引发缺页异常。

思考一下不采用多级页表的情况下,只有简单的一级页表去映射虚拟内存和物理内存的关系会发生缺页异常吗?

通常来说,在不涉及任何页面的调度下,直接通过映射关系查找物理地址的方式,并不会产生缺页异常

例如:二级索引对应的二级页表就可能发生缺页异常

一级页表是必须的,他管理着二级页表,因此,假设虚拟内存是4G的情况下,物理内存1G,意味着10位用来表示一级索引,10位用来表示二级索引

因此缺页率其实是一个衡量内存性能的标准,其实缺页就是按需分配内存页表所导致的一个必然事件,但是根据程序的局部性原理

大部分程序在一段时间都会访问相同的页表(这里的局部性是指时间和空间上)

时间局部性（Temporal Locality）：如果一个内存位置被访问，那么在不久的将来它很可能再次被访问。即程序的访问模式在时间上存在重复性。这种时间局部性可以体现为循环结构、子程序调用和指令流中的顺序性等。通过利用时间局部性，系统可以将频繁访问的数据或指令保留在高速缓存（Cache）中，减少对主存的访问时间，提高程序的执行效率。
空间局部性（Spatial Locality）：如果一个内存位置被访问，那么与它相邻的内存位置很可能也会被访问。即程序的访问模式在空间上存在集中性。这种空间局部性可以体现为数组、矩阵等数据结构的连续存储访问，以及指令流中的顺序性等。通过利用空间局部性，系统可以预取相邻的数据或指令，提前将其加载到高速缓存中，减少主存访问的延迟。

所以地址的具体产生过程是怎样的?

逻辑地址 --> 线性地址 --> 物理地址
我们理解的虚拟内存则是一种机制,一种映射关系,而这种关系根据实际的场景会有所不同,比如保护模式下,这种映射就是线性地址与物理地址的映射

逻辑地址 --分段机制>线性地址 --分页机制>物理地址

这样层次结构就很清晰了,在实模式下,分段机制就是通过段基址与偏移来进行运算,那在保护模式下,是否也是这样呢?

保护模式下的分段机制:
- 在80386模式下,逻辑地址被分为两部分,一部分是段选择符和偏移部分.其中段选择符16位,偏移部分为16位,
  1. 这里我们着重来了解段选择符:

这意味着第二个比特位表示段描述符的位置,表示在哪个描述符表里,什么是段描述符表?,你可以直接理解为我们的段表,而段表里的信息正是我们所需要的,既然一个比特可以表示0和1,这意味着段表有两种.

全局描述符表(GDT)和局部描述符表(LDT)

而为了管理或指定段表的具体位置,我们引入了GDTR 和 LDTR 两个寄存器

GDTR寄存器（GDTR register）：存储GDT的起始地址和大小。
LDTR寄存器（LDTR register）：存储当前任务或进程的LDT的选择符。

描述符寄存器

其中GDTR 0 ~15表示限长, 16 ~ 47 表示全局描述符表的基址,这样就可以根据全局描述符寄存器确定全局描述符表的地址了,而LDTR中3 ~ 15位则用来索引局部描述符表的位置,具体的操作则是根据全局描述符表里的描述符来定位,因此可以这么认为,每一个进程都有一个单独的局部描述符表,也就是段表

下面展示一个具体的实例,便能够明白了:
第一眼看到可能会爆炸,但这没有关系,我们前面了解过段选择符总共16位,有着特殊的1位来代表所选择的段表.如果那位是0,则表示是用了全局描述符表,如果是1,则表示用的是局部描述符表(当然,哪种方式其实都得走全局描述符表).而至于前13位则被用来表示位索引值
- 索引值用来干什么
  
  定位描述符表中的哪一项,也就是找到那个描述符
在前面我们也了解到了全局描述寄存器保存了GDT的基址,因此我们可以根据基址在GDT中查找相应的描述符,而描述符则保存着我们所需段的基址信息,也就是说段描述符如同页表中的页表项.

至此,我们便查找到了我们程序所需要的段,但逻辑地址的另一部分偏移量,则用来定位最后段的偏移,至此,就找到了最后的地址(图中没画出,嫌太丑).

如果TI位是1,则需要通过LDTR来定位局部描述符的位置,此时,我们的LDTR里面的索引会保存着描述符的映射关系,因此仍然需要通过全局描述表去查找相应的描述符,只不过这次的描述符与之有关的是根据LDTR寄存器里的13位(如果是根据段选择符,也是前13位,这就保证了数据位长的一致性原则),因此就可以定位到自己程序的局部描述符表,而此时段选择符就需要来找到LDT中的相应的描述符,此后的流程就如同上面一样了.

需要注意的是:如今这种分段方式已经不在被采用了.但理解其实现过程可以理解这种其设计思想.这种设计方式更加灵巧,且具备扩展性,可以提供更多的段信息,而不是直接的划分段,并通过寄存器直接寻址.

11.页面置换算法

什么叫页面置换?

通常来讲,一个程序占着不止一个页(物理页面),而页面置换就是置换实际的内存页,这种情况常常发生在内存不足,程序需要新的页放入内存中,就需要一些页被换出.

那么这种分配内存页的策略有哪些呢?
1. 最佳置换算法（OPT）：选择最长时间内不再被访问的页面进行替换，理论上能够获得最佳的性能，但实际上很难实现，因为需要预测未来的页面访问模式。
2. 先进先出算法（FIFO）：选择最早进入物理内存的页面进行替换，简单易实现，但可能导致"先来先服务"的缺点，无法充分利用页面的访问模式信息。
3. 最近最少使用算法（LRU）：选择最长时间没有被使用的页面进行替换，根据过去的访问历史来推断未来的使用情况，相对比较接近最佳置换算法。
4. 时钟置换算法（Clock）：使用一个类似时钟的数据结构来维护页面的访问情况，通过访问位（或称引用位）来判断页面是否被使用，选择未被使用的页面进行替换。
5. 最不经常使用算法（LFU）：根据页面被访问的频率选择最不经常使用的页面进行替换。

11.1最佳置换算法

这个算法要预测未来.理论上很难实现,其设计思想就是不知道剩下的页未来的使用情况,也就是未来最长时间不在被使用的页.

11.2先进先出算法

先进入内存的页面,先被置换出来

例如:页面访问序列：A, B, C, D, E, F, A, B

物理内存容量：3个页面

页面访问	页面加载到物理内存	置换的页面	页面置换后的状态
A	A	-	A
B	A, B	-	A, B
C	A, B, C	-	A, B, C
D	B, C, D	A	B, C, D
E	C, D, E	B	C, D, E
F	D, E, F	C	D, E, F
A	E, F, A	D	E, F, A
B	F, A, B	E	F, A, B

11.3最近最少使用算法

它基于程序的局部性原理，假设最近被访问的页面在未来也可能被频繁访问，因此选择最近最长时间未被使用的页面进行置换。

页面访问序列：A, B, C, D, A, B, E, F, D

物理内存容量：3个页面

页面访问	页面加载到物理内存	页面置换	页面置换后的状态
A	A	-	A
B	A, B	-	A, B
C	A, B, C	-	A, B, C
D	B, C, D	A	B, C, D
A	C, D, A	B	C, D, A
B	D, A, B	C	D, A, B
E	A, B, E	D	A, B, E
F	B ,E, F	A	B ,E, F
D	E, F, D	B	E, F, D

11.4时钟页面置换算法

也称为二次机会算法（Second-Chance Algorithm），是一种常用的页面置换算法。它基于时钟指针的思想来选择被置换的页面

我们上述讲的FIFO算法,其实他并不能保证出去的页使用频率是很少的,换言之先换进去的页面如果在页满需要被换出前的情况下多次调用,那么他被调用的频率就是很高的,显然这种算法并不合理,而LRU算法也有着一个巨大的劣势,就是实现这种算法需要一种链表,而为了保证最近最少使用,为了确定追踪页面的访问顺序,每当页面需要访问时,则需要更新链表中的位置(因为一个页面访问可能不止一次,访问顺序就需要全部遍历来寻址需要换出的访问页),这种开销是比较大的

因此采用时钟页面置换算法可以一劳永逸地解决这两个问题

因此,我们检查对于最老的页面,看看他是否被使用,而这一位就是我们页表项中存在的控制位字段,也叫R位(访问位),当他访问的页面R位为0时则淘汰,为1则保留并且修改为0,

时钟置换算法

顺时针旋转

既然是时钟,这种算法的数据结构实现,则是通过双向队列实现的,队头指针和队尾指针分别指向各自的位置,队头指针用来查找要换出的页

11.5最不常用算法

指某个页面使用的次数最少,意味着他最不重要,从使用频率的角度看,而最近最少使用则还需要考虑时间因素

也就是每一个页表项里加入计数器,每一次访问,就进行+1,但是计数器加到每一个页表项中,这种负担过大,他可不是比特的存储量,而是数的累计,这种累计牵扯到算术运算,加上程序中可能经常存在换入换出,置换页面情况的发生,这种计算基本是时时刻刻发生的,所以性能十分低下,具体的实例,只需要参考哪个页面次数最小就换掉就行.

标签：虚拟地址,地址,内存,页表,空闲,页面
From： https://www.cnblogs.com/looktheworld/p/17450279.html

内存与地址

内存