一、操作系统的存储管理

1、内存空间的分配与回收

1）原因和作用

i、原因

• 早期计算机编程不需要过多的存储管理，不需要考虑
• 随着计算机和程序越来越复杂，存储管理成为必要

ii、作用

• 确保计算机有足够的内存处理数据
• 确保程序可以从可用内存中获取一部分内存使用
• 确保程序可以归还使用后的内存以供其他程序使用

2）分配和回收

i、内存分配过程

a、单一连续分配

• 单一连续分配是
  
  最简单的内存分配
  
  方式
• 只能在单用户、单进程的操作系统中使用

方式

：

将内存空间简单的划分为系统区和用户区，系统区存储系统，用户区存储用户的内容

b、固定分区分配

• 固定分区分配是
  
  支持多道程序的最简单
  
  存储分配方式

方式：

• 内存空间被划分为若干固定大小的区域
• 每个分区只提供给一个程序使用，互不干扰

c、动态分区分配

• 根据进程实际需要，动态分配内存空间
• 需要相关数据结构、分配算法

[1]方式：

1. 
   动态分区空闲表数据结构
   
   ：将内存中空闲和忙的区域标识出来

2. 
   动态分区空闲链数据结构
   
   ：将所有空闲区都首尾相连，连成一个链表，根据空闲区2、3相邻，空闲区5、6相邻，将节点2、3合并，节点5、6合并，节省节点，由于每个节点的大小不一，因此
   
   节点需记录可存储的容量
   
   
   

[2]动态分区分配算法

1. 
   首次适应算法(FF算法)
   

• 分配内存时从开始
  
  顺序查找适合进程的内存区
  
• 如果所有内存区都查找一遍后，没有合适的空闲区，则该次分配失败
• 
  缺点
  
  ：每次从头部开始，使得头部地址空间不断被划分，导致头部空闲区大多数呈碎片形式，到后面的进程每次查找内存都需要进行到最后才能找到
• 
  对策：循环适应算法
  
  ，每次不一定是从头部开始，这样可以将内存空间每个位置都作为一次开始进行顺序查找

2. 
   最佳适应算法(BF算法)
   

• 最佳适应算法要求
  
  首先将空闲区链表按照容量大小排序
  
• 
  然后遍历
  
  空闲区链表找到最佳合适空闲区
• 
  优点：避免空闲区大材小用
  
  ，将空闲区容量从小到大排列。

3. 
   快速适应算法(QF算法)
   

• 快速适应算法要求有
  
  多个空闲区链表
  
• 
  每个空闲区链表存储一种容量的空闲区
  
• 比如节点2-3和节点5-6的容量一样，存储在一个链表中，节点1和节点4容量一样，存储在一个链表中，
  
  根据容量选择链表去存储内容
  

ii、内存回收的过程

1. 
   空闲区与回收区相邻，回收区在空闲区后面
   

回收过程：

• 不需要新建空闲链表节点
• 只需要把空闲区1的容量增大为空闲区即可

2. 
   空闲区与回收区相邻，空闲区在回收区后面
   

回收过程：

• 将回收区与空闲区合并，使用同一个节点
• 新的空闲区使用回收区的地址

3. 
   回收区在两个空闲区之间，彼此相邻
   

回收过程：

• 将空闲区1、空闲区2和回收区合并
• 新的空闲区使用空闲区1的地址

4. 
   回收区前后都没有别的空闲区
   

回收过程：

• 为回收区创建新的空闲节点
• 将新创建的空闲节点插入到空闲链表中去

2、段页式存储管理

1）页式存储管理

i、页面

• 
  字块
  
  是相对物理设备的定义
• 
  页面
  
  是相对逻辑空间的定义

ii、页式存储管理方式

• 将进程逻辑空间等分成若干大小的页面
• 相应的把物理内存空间分成页面大小的物理块
• 以页面为单位把进程空间装进物理内存中分散的物理块

iii、存在问题

—–逻辑空间页面应该分配到具体的哪个物理块中

1. 页面大小应该适中，过大难以分配，过小内存碎片过多
2. 页面大小通常是512B~8K

iv、页表-记录进程逻辑空间与物理块的映射

页表：

页地址：

存在问题：


现代计算机系统中，可以支持非常大的逻辑地址空间(2

³²

~2

⁶⁴

),这样，页表就变得非常大，要占用非常大的内存空间，如：具有

32

位逻辑地址空间的分页系统，规定页面大小为4KB，则在每个进程页表中的页表项可达

1M(2

²⁰

)

个，如果每个页表项占用

1Byte

,故每个进程

仅仅页表

就要占用

1MB

的内存空间


详细计算过程：


32位系统进程的寻址空间为4G

4G/4KB=2

²⁰



解决方法：多级页表

v、多级页表

提出根页表的概念，每个根页表的字块指向的是二级页表，二级页表才指向进程真正存储的物理块空间，如果调用某个字块时发现没在二级页表中，此时再将二级页表加载在链表中，这样大大减小页表数，从而

解决页表所占空间较大的问题

根页表：

二级页表：

如果有一段连续的逻辑分布在多个页面中，将大大降低执行效率—段式存储管理

2）段式存储管理

• 将进程逻辑空间划分为若干段(非等分)
• 段的长度由连续逻辑的长度决定
• 段的内容有主函数MAIN、子程序段X、子函数Y等

i、段表

用来存储每段逻辑空间与物理空间的映射，基址为该段在内存中的起始地址，由于每段的长度不同，还会记录段长

段表：

段地址：

3）段页式存储管理

i、段式与页式存储管理的对比

相同点：


段式存储和页式存储都离散地管理了进程的逻辑空间


不同点：

• 页是物理单位，段是逻辑单位
• 分页是为了合理利用空间，分段是满足用户要求
• 页大小由硬件固定，段长度可动态变化
• 页表信息是一维的，段表信息是二维的

ii、段页式存储管理

a、段式、页式的优点结合

• 分页可以有效提高内存利用率(虽然说存在页内碎片)
• 分段可以更好满足用户需求
• 两者结合，形成段页式存储管理

b、段页式存储管理逻辑

1. 先将逻辑空间按段式管理分成若干段

页地址：

2. 再把段内空间按页式管理分成若干页

段地址：

段页地址：

c、三种存储方式的具体表现

页式存储管理：



段式存储管理：



段页式存储管理：

3、虚拟内存

1）虚拟内存概述

i、需要虚拟内存的原因

• 有些进程实际需要的内存更大，超过物理内存的容量
• 多道程序设计，使得每个进程可用物理内存更加稀缺
• 不可能无限增加物理内存，物理内存总有不够的时候

ii、技术

重要性：

• 虚拟内存是操作系统内存管理的关键技术
• 使得多道程序运行和大程序运行成为现实

技术：


把程序使用内存划分，将部分暂时不使用的内存放置在辅存中存储

2）程序的局部性原理

i、概念

指CPU访问存储器时，无论是

存取指令

还是

存取数据

，所访问的存储单元都

趋于聚集在一个较小的连续区域中

ii、逻辑分析

• 程序运行时，无需全部装入内存，装在部分即可
• 如果访问页不在内存，则发出缺页中断，发起页面置换
• 从用户层面看，程序拥有很大空间，即是虚拟内存

虚拟内存实际是对物理内存的扩充，速度接近于内存，成本接近于辅存

3）虚拟内存的置换算法

• 先进先出算法(FIFO)
• 最不经常使用算法(LFU)
• 最近最少使用算法(LRU)

i、缓存的替换时机

• 
  高速缓存的替换时机
  
  ：
  
  当CPU
  
  需要从高速缓存中获取数据时，
  
  发现高速缓存没有数据
  
  ，此时就是高速缓存的替换时机，
  
  从主存载入所需数据
  
• 
  主存页面的替换时机
  
  ：
  
  当主存缺页时
  
  ，就是主存页面的替换时机，
  
  从辅存载入页面数据
  

ii、不同替换时机的策略对比

• 替换策略发生在Cache-主存层次、主存-辅存层次
• Cache-主存层次的替换策略主要是为了解决
  
  速度问题
  
• 主存-辅存层次主要是为了解决
  
  容量问题
  

4、Linux的存储管理

1）Buddy内存管理算法(伙伴系统)

i、概述

• Buddy算法是经典的内存管理算法
• 算法基于
  
  计算机处理二进制的优势具有较高的效率
  
• 算法主要是为了
  
  解决内存外碎片的问题
  
  (其实将内存外碎片问题转换为内存内碎片问题)

a、页内碎片

页内碎片(内部碎片)是

已经被分配出去

(能明确指出哪个进程)的内存空间大于请求所需的内存空间，

不能被利用的内存空间就是内部碎片

b、页外碎片

外部碎片是指还没有被分配出去(不属于任何进程)，但是

由于大小而无法分配给申请内存空间的新进程的内存空闲块

ii、使用的原则

努力让内存分配与相邻内存合并能快速进行

a、内存分配原则

• 为每个进程分配内存时，
  
  向上取整为2的幂大小
  
  (比如需要70k=2
  
  ⁶
  
  +6，给它128k=2
  
  ⁷
  
  )

b、伙伴系统

• “伙伴”指的是内存的“伙伴”
• 一片连续内存的“伙伴”是
  
  相邻的另一片大小一样的连续内存
  

iii、算法的具体流程

• 创建一系列空闲块链表，每一个链表大小都是2的幂
• 假设存储空间有1M大小，空闲块链表大小为1kb,2kb,4kb…1MB,并且只有1MB空闲块链表有节点
• 假设需要分配100k内存给某个进程
  • 分配内存
  1. 100k向上取2的幂=128k
  2. 查询是否有128k的空闲内存块？
  3. 没有！ 查询是否有256k的空闲内存块？
  4. 没有！ 查询是否有512k的空闲内存块？
  5. 没有！ 查询是否有1M的空闲内存块？
  6. 有，摘下1M空闲内存块，分配出去，这时1M的空闲块就没有节点了
  7. 拆下512k放在512的空闲链表，其余的分配出去，这时判断512k是否满足需求
  8. 不满足，拆下256k放在256k的空闲链表，其余的分配出去，并判断256K是否满足需求
  9. 不满足，拆下128k放在128k的空闲链表，其余的分配出去，并判断是否满足需求
  10. 满足，分配完毕
  • 回收刚才分配的内存
  1. 判断刚才分配的内存伙伴在空闲链表上嘛？
  2. 在！移除伙伴，合并为256k空间内存，判断它的内存伙伴在空闲链表上嘛？
  3. 在！移除伙伴，合并为512k空闲内存，判断它的内存伙伴在空闲链表上嘛？
  4. 在！移除伙伴，合并为1M空闲内存，判断它的内存伙伴在空闲链表上嘛？
  5. 不在！将1M的内存插入1M空闲链表，回收完成

2）Linux交换空间

i、概述

• 交换空间(Swap)是
  
  磁盘的一个分区
  
• Linux物理内存满时，会把一些内存交换到Swap空间，来赢得更多物理空间
• Swap空间是
  
  初始化系统时配置的
  

查看交换空间：top


Mem:物理内存

Sawp:交换空间


但是不推荐频繁使用交换空间，因为交换空间在磁盘中，运行速度很慢，因此避免使用交换空间

ii、作用

• 
  冷启动内存依赖
  
  (一些大程序在启动时需要很大的内存空间，但是在使用时需要的内存很小，因此可将交换空间用作启动时的内存)
• 
  系统睡眠依赖
  
  (Linux系统在睡眠状态时，会将所有进程保存在交换空间，下次启动时再将进程转换到内存中，提高启速度)
• 
  大进程空间依赖
  
  (一些大进程使用时需要很大的内存空间，将暂时不用的内存暂时保存在交换空间，需要使用时再进行交换，由此来保证进程的正常进行)

iii、虚拟内存和Linux交换空间的对比

Swap空间

• Swap空间存在于磁盘
• Swap空间与主存发生置换
• Swap空间是
  
  操作系统概念
  
• Swap空间
  
  解决系统物理内存不足问题
  

虚拟内存

• 虚拟内存存在于磁盘
• 虚拟内存与主存发生置换
• 虚拟内存是
  
  进程概念
  
  (一般指某个进程的虚拟内存)
• 虚拟内存
  
  解决进程物理内存不足问题
  

二、操作系统的文件管理

1、文件的逻辑结构

1）逻辑结构的文件类型

i、有结构文件

文本文件、文档、媒体文件

• 文件内容由
  
  可定长记录和可变长记录组成
  
• 
  定长记录
  
  存储文件格式、文件描述等结构化数据项(比如PNG文件标记)
• 
  可变记录
  
  存储文件具体内容(比如PNG数据块)

ii、无结构文件

二进制文件、链接库（比如exe文件、dll文件、so文件）

• 也称为
  
  流式文件
  
• 文件内容
  
  长度以字节为单位
  

2）顺序文件

• 顺序文件是指
  
  按顺序存放
  
  在存储介质中的文件
• 磁带的存储特性使得磁带文件只能存储顺序文件
• 顺序文件是所有逻辑文件当中
  
  存储效率最高
  
  的

但是无法完成增删改查操作

3）索引文件

• 可变长文件不适合使用顺序文件格式存储
• 索引文件是为了
  
  解决可变长文件存储而发明的一种文件格式
  
• 索引文件需要配合
  
  索引表
  
  完成存储的操作

举例：


索引表：

逻辑地址对应的值表：

2、辅存的存储空间分配

1)辅存的分配方式

i、连续分配

按照空闲内存按照顺序分配

– 顺序读取文件内容非常容易，速度很快

– 对存储要求高，要求满足容量的连续空间

ii、 链接分配

• 链接分配可以将文件存储在离散的盘块中
• 需要额外的存储空间存储文件的盘块链接顺序
• 根据额外存储的盘块的不同，将链接分配分为
  
  隐式链接和显式链接
  

假设一个文件存储需要5个盘块：2、9、7、18、16

a、隐式链接

• 隐式分配的
  
  下一个链接指向
  
  存储
  
  在当前盘块内
  
• 隐式分配
  
  适合顺序访问
  
  ，
  
  随机访问效率很低
  
  (因为不管随机访问哪个盘块，都需要从第一个盘块开始，顺序访问到指定的盘块)
• 
  可靠性差
  
  ，任何一个链接出问题都影响整个文件

b、显式链接分配

• 显式分配的下一个链接指向另外存储在一个表FAT(File Allocation Table)中

• 
  不支持高效的直接存储
  
  (在查找空闲盘块时，由于
  
  FAT记录项多
  
  ，耗费时间较长)
• 
  检索时FAT表占用较大的存储空间
  
  (检索时，
  
  需要将整个FAT加载到内存
  
  )

iii、索引分配

• 把文件的所有盘块集中存储(索引)
• 读取某个文件时，将文件索引读取进内存即可

之前的例题：


会有一个额外盘块12存储盘块的索引

在内存中：




优点：

• 每个文件拥有一个索引块，记录所有盘块信息
• 索引分配方式支持直接访问盘块
• 文件较大时，索引分配方式具有明显优势

2）存储空间管理

i、空闲表

• 空闲盘块的分配与内存分配类似
• 首次适应算法、循环适应算法等
• 回收过程也与内存回收类似

ii、空闲链表

• 空闲链表法把所有空闲盘区组成一个空闲链表
• 每个链表节点存储空闲盘块和空闲的数目

iii、位示图

位示图：

列表示磁道，行表示盘块，0表示空闲，1表示被占用


优点：

• 位示图维护成本很低
• 位示图可以非常容易找到空闲盘块
• 位示图使用0/1比特位，占用空间很小

3、目录管理

1）目录树

目录：





文件：





目录树：





特性：任何文件或目录都只有唯一路径


例如：文件M的路径为A/D/M

三、Linux文件

1、Linux文件的基本操作

1）Linux目录

Linux一切皆文件

i、目录描述

• /bin：可执行的二进制文件
• /etc：存放常用的配置文件，以conf结尾的文件
• /home：用户的主目录
• /usr：存放系统应用目录
  • 其中/usr/local存放管理员安装的软件目录
  • /usr/bin存放软件安装的二进制文件
  • /usr/etc存放用户安装的软件的配置的目录
• /proc：存放虚拟文件系统，
  • 是系统内存映射，
  • 可以根据目录访问系统信息(CPU信息，内存信息)
  • 有许多数字的文件夹，是进程文件夹
• /dev：存放设备的目录(终端、鼠标、键盘……)
• /boot：存放系统引导时使用的各个文件
• /lib：存放系统启动时或运行时用到的动态库文件

ii、相对路径、绝对路径

相对路径：相对于当前的操作目录，文件位于哪个目录

绝对路径：从根目录开始的路径

2）Linux文件常用操作

(目录/文件)

• 创建：touch(创建)/vim(创建并编辑) file
• 查看：cat file
• 删除：rm file
• 创建文件夹：mkdir file
• 删除文件夹：rm -r file

3）Linux文件类型

• 套接字 (s)
• 普通文件 (-)
• 目录文件 (d)
• 符号链接 (l)
• 设备文件 (b块设备、c字符设备)
• FIFO §

2、Linux的文件系统

1)文件系统概览

i、FAT

• FAT(File Allocation Table)
• FAT16、FAT32等，
  
  微软Dos/Windows使用的文件系统
  
• 
  使用一张表保存盘块的信息
  

ii、NTFS

• NTFS（New Technology File System）
• 
  WindowsNT(7、10、XP)环境的文件系统(也可用于Linux系统)
  
• NTFS对FAT进行了改进，取代了旧的文件系统

iii、EXT2/3/4

• EXT(Extended file system)：扩展文件系统
• 
  Linux的文件系统
  
• EXT2/3/4 数字表示第几代，现在大多数使用EXT4

2）Ext文件系统

i、EXT文件系统：

如果对一个Linux文件格式的U盘格式化后，它的文件系统为：

• Boot Sector：
  
  启动扇区，安装开机管理程序
  
• Block Group：
  
  块组，存储数据的实际位置
  

ii、Block Group

• 
  Inode Table:存放文件Inode的地方
  
  • 每一个文件(目录)都有一个Inode
  • 是每一个文件（目录）的
    
    索引节点
    
• 
  Inode：存放每个文件的信息
  
  • 索引节点编号：
    
    文件的唯一索引
    
    ，文件类型、文件权限、文件物理地址、文件长度、文件连接计数、文件存取时间、文件状态、访问计数、链接指针
  • 
    文件名不是存放在Inode节点上的，而是存放在目录的Inode节点
    
  • 列出目录文件的时候
    
    无需加载文件的Inode
    
• 
  Inode bitmap:Inode的位示图
  
  • 当Linux文件系统初始化后，Inode节点数目就固定了，使用位示图，
    
    记录已分配的Inode和未分配的Inode
    

• 
  Date block：存放文件内容的地方
  
  • 每个block都有唯一的编号
  • 
    文件的block记录在文件的Inode上
    
    (文件物理地址即文件的block记录)
• 
  Block bitmap：记录Date block的使用情况
  
• 
  Superblock：记录整个文件系统相关信息的地方
  
  • 记录Block和Inode的使用情况
  • 包括文件系统的时间信息、控制信息等
  • 块的大小一般均为1024个字节

3）实际操作

• 
  访问Inode信息(指定某个文件)
  
  ：dumpe2fs 文件
• 
  查看某个文件的具体信息
  
  ：stat 文件名
• 
  重命名文件
  
  ：mv 旧 新

四、操作系统的设备管理

1、广义的IO设备

• 对CPU而言，凡是
  
  对CPU进行数据输入的都是输入设备
  
• 对CPU而言，凡是
  
  对CPU进行数据输出的都是输出设备
  

1）按使用特性分类

i、存储设备

U盘、内存、磁盘

ii、交互IO设备

键盘、显示器、鼠标

2）按信息交换的单位分类

i、块设备(block)

磁盘、SD卡

ii、字符设备(char)

打印机、Shell终端

3）按设备的共享属性分类

有

独占设备、共享设备、虚拟设备

4）按传输速率分类

可以分为低速设备、中速设备、高速设备

2、IO设备的缓冲区

1）解决的问题

为了

解决CPU与IO设备的速率不匹配问题

(存储器的层次结构也这个问题是为了解决)

• 减少CPU处理IO请求的频率
• 提高CPU与IO设备之间的并行性

2）如何操作

将程序与IO设备之间需要进行

多次交互

的方式

改变为只进行一次

，在程序和IO设备间

添加一个缓冲区

，

存放需要交互的信息

i、IO设备的缓冲区

• 
  专用缓冲区
  
  只适用于
  
  特定的IO进程
  
• 当这样的IO设备进程比较多时，对
  
  内存的消耗也很大
  
• 操作系统划出
  
  可供多个进程使用的公共缓冲区
  
  ，称之为
  
  缓冲池
  
• 当需要使用某个缓冲区时，从缓冲池中取出使用，使用完后再将缓冲区归还给缓冲池

3、SPOOLing技术

1）概念

• 是关于
  
  慢速字符设备如何与计算机主机交换信息
  
  的一种技术
• 利用
  
  高速共享设备将低速的独享设备模拟为高速的共享设备
  
• 使用该技术后，
  
  逻辑上
  
  ，系统为
  
  每一个用户都分配了一台独立的高速独享设备
  
  —虚拟设备技术

2）如何操作

比如三个进程需要使用打印机：

将进程的输出以队列的形式存放到一个磁盘中–

输出井

，然后使用SPOOLing技术将输出内容(文件等)交给打印机，执行打印机操作


SPOOLing技术把同步调用低速设备改为异步调用

• 在输入、输出之间
  
  增加了排队转储环节
  
  （输入井、输出井）
• 
  SPOOLing负责输入(出)井与低速设备之间的调度
  
• 逻辑上，
  
  进程直接与高速设备交互
  
  ，减少了进程的等待时间