操作系统-存储管理

管理对象

主存储器

存储器结构

register
cache
primary storage
secondary storage

• 地址空间

  flowchart LR;
  A[Source Code];B[Compile];C[Link];D[Target];
  A-->|符号名地址|B-->C-->|"相对（逻辑）地址空间"|D;
• 存储空间
  • 物理地址的集合
• 逻辑地址空间
  • 逻辑地址的集合

地址重定位

flowchart LR;
A[/Virtual Address/];B[redirect];C[/physical Address/];
A-->B-->C;

• 静态重定位
  • 作业在装入主存前地址就已确定
• 动态重定位
  • 依赖于硬件地址变换机构，程序在运行时可以转入、转出主存。

管理方案

解决多用户使用主存的问题

分其存储管理

• 固定分区
  • 🙂 分区大小固定不变
  • 🙃 产生空间碎片
• 可变分区
  • 最佳适应算法
    • 🙂 提前分区，按照作业需求选择最合适的分区
    • 🙃 产生无法再分的空间碎片（外碎片）
  • 最差适应算法
    • 🙂 提前分区，总是把作业分到最大分区
  • 首次适应算法
    • 总是从主存低地址开始分配
  • 循环首次适应算法
    • 从刚分配的空白区寻找空间
• 可重定位分区
  • 移动已分配的分区，使他们连续
• 分区保护
• 防止未经核准的用户访问分区
• 上界下界寄存器保护
  • {roof:作业装入地址,floor:作业装入地址}
• 基址限长寄存器保护
  • `{base:作业装入地址,限长:作业长度}

纯分页存储管理

分页/分块原理

flowchart LR;
    AS[Address Space];AP((p1));BP((p2));CP(("..."));DP((pn));
    PS[Primary Space];AB((b1));BB((b2));CB(("..."));DB((bn));
    subgraph 1 [Pagenation]
    direction TB
    AS--->AP;AS--->BP;AS--->CP;AS--->DP;
    end
    subgraph 2 [Register]
    direction LR
    1--->PT[[page table]]--->3;
    end
    subgraph 3 [Chunking]
    direction TB
    PS--->AB;PS--->BB;PS--->CB;PS--->DB;
    end

逻辑地址结构

$$\boxed{\underbrace{000000000000000000000}_{\text{页号}}}\boxed{\underbrace{000000000000}_{\text{页内地址}}}$$

• 可以表示$2^{20}=1048576(b)=1Mb$页
• 每页容量$2^{12}=4096(b)=4k$
• 则一个进程的页表大小$1Mb\cdot32b=32Mb=4MB$

页表寄存器结构

$$\boxed{\text{页表起始地址}}\boxed{\text{页表长度}}$$

页表项结构

$$\text{页地址}=\text{页表起始地址}+\text{页号}$$

$$\boxed{\text{页地址}}\boxed{\text{物理块号}}$$

内存访问

sequenceDiagram
    participant P as Process
    participant AT as Address Translator
    participant PT as Page Table Register
    participant PS as primary Storage
    P->>AT:logical addrress
    AT->>PT:pagenation
    PT->>AT:Page Address
    AT->>PS:Page Address+Inner Address
    PS->>AT:Physical Address
    AT->>P:Physical Address
    opt if indirect Address
      P->>PS:indirect Address
      PS->>P:direct Address
    end
    P->>PS:access
    PS->>P:resource

快表

原理

基于分页存储管理，在地址转换结构上加入一个高速存储缓存热点块号从而减少主存访问次数。

内存访问

sequenceDiagram
    participant P as Process
    participant AT as Address Translator
    participant PT as Page Table Register
    participant PS as primary Storage
    P->>AT:logical addrress
    opt if cache
      AT-->>P:Physical address
    end
    AT->>PT:pagenation
    PT->>AT:Page Address
    AT->>PS:Page Address+Inner Address
    PS->>AT:Physical Address
    AT->>P:Physical Address
    opt if indirect Address
      P->>PS:indirect Address
      PS->>P:direct Address
    end
    P->>PS:access
    PS->>P:resource

两级页表

原理

减少页表占用的连续空间，建立外层页表对页表进行分页

虚拟地址结构

$$\boxed{\text{外层页号}}\boxed{\text{外层页内地址}}\boxed{\text{页内地址}}$$

外层页表寄存器结构

$$\boxed{\text{外层页号起始地址}}\boxed{\text{外层页长}}$$

外层页表项结构

$$\text{外层页地址}=\text{外层页表起始地址}+\text{外层页号}$$

$$\boxed{\text{外层页地址}}\boxed{\text{页起始地址}}$$

页表项结构

$$\text{页地址}=\text{外层页表起始地址}+\text{外层页内地址}$$

$$\boxed{\text{页地址}}\boxed{\text{物理块号}}$$

分段地址结构

$$\boxed{\underbrace{00000000000000000}_{\text{段号}}}\boxed{\underbrace{0000000000000000}_{\text{段内地址}}}$$

段表寄存器结构

$$\boxed{\text{段表起始地址}}\boxed{\text{段表长度}}$$

• 每个作业最多有$2^{16}=64k$段
• 每段容量$2^{16}=64k$

段表项结构

$$\boxed{\text{基址}}\boxed{\text{段长}}$$

• 则一个作业段表占主存$64kb\cdot32b=2Mb=0.25MB$

段页式存储管理

段页式地址结构

$$\boxed{\text{段号}}\boxed{\text{段内页号}}\boxed{\text{页内地址}}$$

段表寄存器结构

$$\boxed{\text{段表起始地址}}\boxed{\text{段表长度}}$$

段表项结构

$$\boxed{\text{页表始址}}\boxed{\text{页表长}}$$

页表项结构

$$\text{页地址}=\text{页表始址}+\text{段内页号}$$

$$\boxed{\text{页地址}}\boxed{\text{物理块号}}$$

虚拟存储管理

允许作业部分装入主存，在运行期间动态调入和置换作业的局部

请求分页系统

在纯分页基础上增加了请求调页和页面置换功能

缺页中断

• 要访问的页面不在主存发生缺页中断
• 发生缺页中断，返回到被中断指令的开始处

页面置换

如果发生缺页中断，但是主存无空闲块，需要用页面置换算法选择一个内存块调出主存

• 最佳置换算法
• 先进先出置换算法
• 最近最少未使用
• 最近未用

工作集

请求分段系统

请求段页式系统