OS学习笔记---（二）存储器

OS学习笔记---（二）存储器

概述

访问数据的有效时间TA计算

TA=A*TC+（1-A）*TM

(TC访问cache，TM访问内存)

内存的分配与回收

数据结构：主存资源信息块、空闲队列、等待队列、分配程序

相关策略：分配策略、放置策略（选择一个空闲区）、调入策略、淘汰策略

内存共享与保护

内存共享：共享程序或数据、可以实现通信、节省空间

内存保护：进程互不影响（界地址保护）

界地址保护包括

• 上下界（定义地址区间
• 基地址限长（差不多

地址映射

将逻辑地址映射到相应的物理地址的过程

物理地址：真实地址

主存空间：物理地址的集合

逻辑地址（相对地址、虚地址）：用户程序地址

程序地址空间：所有逻辑地址集合对应的空间

地址的映射可以在多个场合：

• 编程或者编译时
• 程序装入过程中（载入内存时）发生映射---静态地址映射
• 程序运行时（指令或者数据访问：malloc等）---动态地址映射

内存扩充

主存容量不足

实现方法：

• 全部代码和数据放入辅存
• 当前执行步骤涉及的部分代码放入主存
• 所需数据不在时，从辅存调入信息

虚拟存储器

由于主存和辅存之间的动态调度，使存储器比主存的容量大很多，这个存储器可以称为虚拟存储器

核心思想：

• 分离逻辑地址和物理地址
• 分离存储空间和虚地址空间
• 提供地址变换（映射）

程序的二维地址结构：若干段组成

（代码段、数据段、堆栈段）

连续存储管理方式

固定分区

物理内存被分为大小和数量固定的分区

且每个分区只能装一个程序（分区大小其实可以不固定）

动态分区分配

可变分区的大小、数量都可变

分配时按需分配，回收时可以合并成较大分区

分配算法

1. 首次适应算法

   将程序装入主存足够且地址最低的空闲区（低地址往高处遍历，找到刚好满足的空闲区）

   尽量保证在高地址保留大空闲区

2. 最佳适应算法

   将程序装入主存中大小接近的空闲区（大一点点）

   空闲区由小到大排序

   尽量保存大的空闲区

3. 最坏适应算法

   将程序装入差距最大的空闲区（程序大小和空闲区大小差距最大）

   空闲区由大到小排序

   尽量保证空闲区内的剩余部分较大

回收算法

BG：存在碎片问题，多个分散小内存空间碎片，穿插在主存空间

将碎片空间移到一侧连成较大空闲区

分页存储

页面：程序地址空间被分成2^k个片段（虚页）

页框：物理内存被分为等大的片（实页）

页号位数决定了页面总数、页面大小决定了页内地址的位数

逻辑地址的具体位置：

页号：逻辑地址/页内地址位数

页内地址：逻辑地址%页内地址位数

相当于改变进制（10进制改成16进制也是这么算）

页表（PTE）：映射页号到物理块号

• 存储页号和块号（实际上只存块号）

• PTE的个数由分页大小和PTE大小决定：分页大小/PTE大小

如果页表存储在内存中，会增加访存时间，可以采用以下办法解决：

在缓冲存储器中存放当前使用的快表

快表存储着当前用到的页号和对应的块号

段式存储管理

段式逻辑地址构成：

段表：段号+段长+基地址

段页式存储管理

分段：信息的逻辑划分、段长可变

分页：信息的物理划分、页大小固定

段页式将两者相结合，逻辑地址结构如下：

虚拟存储系统

利用外存的空余空间，逻辑上对内存容量进行扩充的存储系统

页式系统：

• 简单页式系统：装入程序的全部页面才能运行
• 请求页式系统：装入一个程序的部分页面即可

（扩充页表=页号+物理块号+状态位+访问字段（状态）+修改位+外存地址）

缺页处理：

就是执行指令时开始地址转换，（没越界的话）使用页号检索表检索

如果不在页表内，则产生缺页中断，请求调页：

1. 保留CPU现场

2. 得到页面外存地址

3. 如果内存没满，就分配内存块，读入缺页

   如果满了，就选择一页换出（该页没被修改）

   该页如果被修改了，就先将该页写回外存

4. 修改页表重新执行

tips：保留现场就是保留上下文：保留处理器状态、程序计数器、寄存器、标志位等

主存和辅存之间频繁置换会出现颠簸（抖动）

页面置换策略、算法

可变分配全局置换、固定分配局部置换、可变分配局部置换

（可变指分配的内存数量、局部指只影响单个进程空间）

置换算法：

• 最佳置换算法（理论算法，进程的页面走向是未知的，无法预知）

• 先进先出（容易实现，但存在Belady现象：内存块增多，缺页率上升）

• LRU（最近最久未使用）

• LFU（最近最少使用）

• 时钟算法（NRU）最近未使用算法，循环检查

  

循环扫描过程：

页面缓存置换算法

简单描述：放一个缓冲区存放被置换的页面，方便快速恢复访问（从而避免缺页中断）

注意：缓冲区本身也是会满的，也要有对应的页面置换策略（算法）

具体流程：

1. 选择页面：当需要替换一个页面时（例如，当发生缺页中断并且所有的内存帧都已被占用时），算法首先选择一个页面进行置换。这个选择可以基于FIFO（先进先出）、LRU（最近最少使用）或其他页面置换策略。
2. 使用缓冲区：被选中的页面不会立即从物理内存中删除，而是移动到一个缓冲区。这个缓冲区是内存中的一个特殊区域，用于临时存放被置换的页面。
3. 重新访问检查：如果被置换的页面很快再次被访问（在它仍然在缓冲区内时），它可以快速被恢复到物理内存中，而不需要从硬盘上重新加载，从而避免了一次缺页中断。

Linux内存管理机制

虚拟地址空间：

32位系统是2^32=4GB，这里的位指一位可以决定一字节（字节编址）

每个进程的虚拟地址空间都是独立的

Linux内存采用分页机制，采用四级页表（PGD、PUD、PMD、PTE）

（分别对应，全局，上级，中间，页表）四种目录项结构都定义在 page.h中

内核空间在系统启动的过程中加载了操作系统的内核

用户空间的管理采用的是伙伴系统，实现对内存页框的分配和回收，页框是管理的最小单位（页面装入页框，页框是内存分配的基本单位）

使用slab机制处理小于页框的页面：

1. 缓存层次：Slab分配机制引入了一个缓存层次，这个缓存层次由一系列的“caches”组成。每个cache专门用于管理一定大小的内存块。
2. Slab的概念：每个cache被分割成多个“slab”，一个slab是一组连续的页框（通常是一个或多个连续的物理页）。每个slab又被进一步分割成特定大小的内存块，用于满足小于一个页框大小的分配请求。

将四级页表中间表项数量设置为1即可当作二级页表使用

一致内存访问UMA：内存连续，CPU可以一致访问

非一致内存访问NUMA：每个CPU访问本地比较快，访问其他CPU会比较慢

内存以节点为其实，每个节点关联一个CPU（pg_data_t) 可以穿起来构成单向链表

伙伴系统

每次分一半给你（好伙伴！）

内核虚拟地址空间：3：1（3是全局的进程虚拟地址空间）

（有点看不下去了，下次看linux源码的时候再补充吧）

接下来是刷题时间

ID：53

还是动态规划，我一直以为判断条件是加上这个数会不会变大，

没有考虑到，如果我前面加了这么多，还不如新的大，不如重新开始加

下面的评论说的很好：

answer:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n=nums.size();
        if(n==1)return nums[0];
        int tmp=nums[0];
        int i=1;
        int ans=nums[0];
        while(i<n){
            tmp=max(tmp+nums[i],nums[i]);
            ans=max(tmp,ans);
            i++;
        }
        return ans;
    }
};

唉，今天的面试比较稀碎，有点难受

复习去了，下次加油吧