操作系统
    内存管理

    内存管理

    地址空间

    解决保护和重定向的问题 当一个进程运行时，程序的起始物理地址装载到基址寄存器，长度加载到界限寄存器 动态重定向：通过把访问内存的指令重解释，加上基址寄存器的值，检查如果地址超越界限，会产生错误并终止访问 缺点：需要加法和比较运算，没有特殊电路会较慢

    内存超载

    交换技术：空闲进程存在磁盘上，不运行就不会占内存 虚拟内存：只有一部分被调入内存的情况下运行

    空闲内存管理

    通过维护一个记录已分配内存段和空闲内存段的链表，链表中的节点或者包含一个进程或者是两个进程间的空闲区域

    首次适配：扫一遍链表，除非大小一样否则将空闲区劈成两半来给一个用 下次适配：记录下扫描过的空闲区的位置 最佳适配：从头扫到尾，找到能容纳进程的最小空闲区

    虚拟内存

    将进程的地址空间分割成多个页，每一页有连续的地址范围 当程序等待它的一部分读入内存的时候，CPU可以交给其他进程使用

    虚拟地址：虚拟页号(高位，用作页表索引)+偏移量(低位) 虚拟页号 -> 页表中的页表项 -> 页框号 -> 替换掉虚拟页号 == 真实物理地址 在使用虚拟地址的情况下，进程使用指令读取内存的时候，虚拟地址会先被送到 MMU（内存管理单元维护页表）映射成物理地址，找不到（页表项中的标志位为0），就会发生缺页中断；如果找到，再发送物理地址到内存总线

    物理内存分成页框，虚拟地址空间分成页面，页框和页面通常是一样大的，与磁盘的交换是以整个页面为单位进行的

    虚拟地址的页表越来越大，容易产生性能问题，因此引入了 TLB 作为页表的局部缓存，现代操作系统可以装载 TLB 缓存，当缓存能存放的表项够多的时候已经够用

    软失效：在内存但是不在 TLB 中，更新 TLB 即可，不用访问磁盘 硬失效：不在内存也不在TLB，从磁盘读取页面到内存 32位地址空间的操作系统会使用多级页表，64位的操作系统可以将 TLB设计成一个散列表，hash值相同的虚拟页表会在一个桶里，值为页框号

    页面置换算法

    LRU 缺页中断发生时，置换未使用时间最长的页面 c++实现

    class LRUCache 
{ 
    // store keys of cache 
    list<int> dq; 
  
    // store references of key in cache 
    unordered_map<int, list<int>::iterator> ma; 
    int csize; //maximum capacity of cache 
  
public: 
    LRUCache(int); 
    void refer(int); 
    void display(); 
};

LRUCache::LRUCache(int n) 
{ 
    csize = n; 
}

void LRUCache::refer(int x) 
{ 
    // cache 中没有
    if (ma.find(x) == ma.end()) 
    { 
        // 满了，删除链尾元素 
        if (dq.size() == csize) 
        { 
            //删掉链尾（即长时间未用的） 
            int last = dq.back(); 
            dq.pop_back(); 
            ma.erase(last); 
        } 
    } 
  
    // cache中有也删掉
    else
        dq.erase(ma[x]); 
  
    // 从头部插入，并更新引用 
    dq.push_front(x); 
    ma[x] = dq.begin(); 
}

    分离数据空间和指令空间

    分别对数据空间和指令空间分页，通过链接器来判别什么时候需要使用哪个空间，能使可用的地址空间翻倍 共享页面：分离的地址空间可以更好地让多个进程共享只读的程序页面 避免释放共享的页表：让进程拥有自己的页表，但是指向相同的页表集合 如果要往只读的部分写，会启动操作系统的写时拷贝机制，创建副本

    动态链接

    链接：扫描 .a 文件，在文件中寻找程序未定义的外部函数，找到后加载到二进制文件中 静态链接会浪费大量的内存空间，因为系统不知道它可以共享这些库 动态链接的编译过程会加载能够在运行时动态绑定被调用函数的 stub 存根，如果运行的时候其他进程装载了这个库，就可以共享一个库，避免静态链接的重复加载 而且 DLL的重新下发不需要客户重新编译程序 多个进程共享同一个库可以通过编译时产生相对地址的指令来解决，或者使用 mmap将文件映射到其虚拟地址空间的一部分，进程间可以通过这种共享内存来进行通信

    虚拟地址空间的分段

    每一个段构成一个独立的地址空间，程序必须提供段号和段内地址，这样使得堆栈段可以自由地伸缩，提高空间利用率，有助于保护和共享

    分段与分页结合

    X86中，CS寄存器保存代码段的选择子，DS保存数据段的选择子。段又分为局部段（程序的段）和全局段（系统段包括操作系统本身），可以启用分页或者禁止分页，线性地址的组成 == 目录， 页面， 偏移量

    • 程序段 (Text Segment)：可执行文件代码的内存映射
    • 数据段 (Data Segment)：可执行文件的已初始化全局变量的内存映射
    • BSS段 (BSS Segment)：未初始化的全局变量或者静态变量（用零页初始化）
    • 堆区 (Heap) : 存储动态内存分配，匿名的内存映射
    • 栈区 (Stack) : 进程用户空间栈，由编译器自动分配释放，存放函数的参数值、局部变量的值等
    • 映射段(Memory Mapping Segment)：任何内存映射文件

    栈与堆的区别

    栈：由编译器自动分配释放，存放函数的参数值，局部变量的值等。其
    操作方式类似于数据结构中的栈 堆：一般由程序员分配释放，若程序员不释放，程序结束时可能由OS回
    收

    函数的本质

    函数指针的值是该函数机器代码表示中第一条指令的地址 一个函数调用需要：传递控制（函数指针），传递数据（通过寄存器传递6个参数，超过就放在栈帧上），记录函数返回后的下一条指令的地址，分配空间（栈指针往低地址移动）

    进程深入理解计算机系统笔记