本文将讲解操作系统内存分配与回收策略、段页式存储管理、虚拟内存技术、Linux内存管理算法、交换空间、文件管理、linux文件操作命令行、文件系统、设备管理等内容

存储管理

内存分配与回收

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

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

内存分配的过程

1. 单一连续分配 已过时
   • 将内存分为系统区和用户区，每个区使用连续分配方式
   • 只能在单用户、单进程的操作系统中使用
2. 固定分区分配
   • 是支持多道程序的最简单存储分配方式
   • 内存空间被划分为若干固定大小的区域
   • 每个分区只提供给一个程序使用，互不干扰
3. 动态分区分配
   • 根据进程实际需要，动态分配内存空间
   • 需要使用双向链表数据结构及分配算法
   • 

内存动态分区分配相关算法

标题	描述	优点	缺点
FF首次适应算法	分配内存时从开始顺序查找适合内存区 若没有合适的空闲区，则该次分配失败	-	每次从头部开始，使得头部地址空间不断被划分，效率降低
循环适应算法	对首次适应算法进行优化，从上一次结束位置查找内存	解决了FF算法效率降低的问题	内存碎片化
BF最佳适应算法	最佳适应算法要求空闲区链表按照容量大小排序 遍历空闲区链表找到最佳合适空闲区	避免大才小用的情况	-
QF快速适应算法	快速适应算法要求有多个空闲区链表 每个空闲区链表存储一种容量的空闲区	比BF算法更快找到适合的内存区	空间换时间

内存回收的过程

使用链表记录空闲区信息， 回收时会合并相邻的空闲区

段页式存储管理

操作系统是如何管理进程的空间呢？

• 页式存储管理
• 段式存储管理
• 段页式存储管理

页式存储管理

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

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

如何知道 进程的某一个页面分配到具体的哪一个字块里呢？

• 需要页表来记录

多级页表
现代计算机系统中，可以支持非常大的逻辑地址空间（2^32~2^64），这样，页表就变得非常大，要占用非常大的内存空间，如，具有32位逻辑地址空间的分页系统，规定页 面大小为4KB，则在每个进程页表中的页表项可达1M(2^20)个，如果每个页表项占用1Byte，故每个进程仅仅页表就要占用1MB的内存空间。

• 32位系统进程的寻址空间为4G 4G/4KB=2^20

页式存储管理总结

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

缺点： 有一段连续的逻辑分布在多个页面中，将大大降低执行效率

段式存储管理

• 将进程逻辑空间划分成若干段（非等分）
• 段的长度由连续逻辑的长度决定
• 主函数MAIN、子程序段X、子函数Y等

段式存储和页式存储异同

• 都离散地管理了进程的逻辑空间
• 页式物理单位，段式逻辑单位
• 分页为了合理的利用空间，分段式满足用户需求
• 页的大小由硬件固定，段的长度可动态变化
• 页表信息式一维的，段表信息式二维的

段页式存储管理

思路

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

具体实现

• 先将逻辑空间按段式管理分成若干段
• 再把段内空间按页式管理等分成若干页

虚拟内存

思考
一个游戏几十G，物理内存只有4G，那么这个游戏是怎样运行的？

虚拟内存概述

背景：

1. 有些进程世纪需要的内存很大，超过物理内存的容量
2. 多到程序设计，使得每个进程可用物理内存更加稀缺

不可能无限增加物理内存，物理内存总有不够的时候

虚拟内存是操作系统内存管理的关键技术

• 把程序使用内存划分，将部分暂时不使用的内存放置在辅存
• 使得多道程序运行和大程序运行成为现实

程序的局部性原理

局部性原理是指CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。

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

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

虚拟内存置换算法

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

Linux存储管理

• Buddy内存管理算法
• 交换空间

Buddy内存管理算法

• Buddy算法是经典的内存管理算法， 是目前linux系统正在使用的算法
• 算法基于计算机处理二进制的优势具有极高的效率
• 算法主要是为了解决内存外碎片的问题

学习buddy算法前，先来了解一下内存碎片

• 页内碎片
  • 内部碎片是已经被分配出去（能明确指出属于哪个进程）的内存空间大于请求所需的内存空间，不能被利用的内存空间就是内部碎片。
• 页外碎片
  • 外部碎片是指还没有分配出去（不属于任何进程），但是由于大小而无法分配给申请内存空间的新进程的内存空闲块。

Linux交换空间

• 交换空间(Swap)是磁盘的一个分区
• Linux物理内存满时，会把一些内存交换至Swap空间
• Swap空间是初始化系统时配置的 (装系统时会提示 需不需要，需要多大)

top命令可以查看系统交换空间信息

应避免系统使用操作空间，因为磁盘的存取速度远低于内存的存取速度

交换空间的作用

• 冷启动内存依赖（大型应用程序启动时要使用很大内存，但启动后很少使用）
• 系统睡眠依赖 （linux系统休眠时会将数据保存到swap空间，下次启动再重新加载）
• 大进程空间依赖

文件管理

文件的逻辑结构

• 有结构文件
  • 文件内容由定长记录和可变长记录组成
  • 定长记录存储文件格式、文件描述等结构化数据项
  • 可变长记录存储文件具体内容
• 无结构文件
  • 也称为流式文件
  • 文件内容长度以字节为单
  • exe文件 dll文件 so文件

顺序文件

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

索引文件

• 可变长文件不适合使用顺序文件格式存储
• 可变长文件不适合使用顺序文件格式存储
• 索引文件需要配合索引表完成存储的操作

辅存的分配方式

• 连续分配 （分配连续的扇区）
  • 顺序读取文件内容非常容易，速度很快
  • 对存储要求高，要求满足容量的连续存储空间
• 链接分配
  • 分为 隐式链接 和 显示链接
  • 链接分配可以将文件存储在离散的盘块中
  • 需要额外的存储空间存储文件的盘块链接顺序
  • 隐式链接
    • 隐式分配的下一个链接指向存储在当前盘块内
    • 隐式分配适合顺序访问，随机访问效率很低
    • 可靠性差，任何一个链接出问题都影响整个文件
  • 显示链接
    • 对隐式链接的改进，使用一个表存储文件的盘块及顺序， 这个表即FAT
    • 不支持高效的直接存储（FAT记录项多，磁盘越大，记录越多）
    • 检索时FAT表占用较大的存储空间（需要将整个FAT加载到内存）
• 索引分配
  • 把文件的所有盘块集中存储（索引）
  • 读取某个文件时，将文件索引读取进内存即可
  • 
  • 每个文件拥有一个索引块，记录所有盘块信息
  • 索引分配方式支持直接访问盘块
  • 文件较大时，索引分配方式具有明显优势 （主流文件系统都采用该方案）

辅存的空间管理

• 空闲表
• 空闲链表
• 位示图

空闲表

空闲链表

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

位示图

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

目录管理

目录树

• 作用： 任何文件或目录都只有唯一路径

文件的描述信息

• 文件标识符
• 文件类型
• 文件权限
• 文件物理地址
• 文件长度
• 文件链接记数
• 文件存取时间
• 索引节点编号
• 文件状态
• 访问计数
• 链接指针

Linux目录

• 相对路径
• 绝对路径

linux中一切皆是文件

使用ls -l 可以查看当前文件夹下的文件类型

文件类型

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

linux的文件系统

• FAT
  • 前面 将辅存的显示链接分配方式提过，它不支持高效的直接存储
• NTFS
  • WindowsNT环境的文件系统
  • NTFS对FAT进行了改进，取代了旧的文件系统
• EXT2/3/4
  • EXT(Extended file system)：扩展文件系统
  • Linux的文件系统
  • 数字表示第几代

EXT文件系统

• Inode Table
  • 存放文件Inode的地方
  • 每一个文件（目录）都有一个Inode
  • 是每一个文件（目录）的索引节点
• Inode
  • Inode包含以下信息
  • 索引节点编号
  • 文件类型
  • 文件权限
  • 文件物理地址
  • 文件长度
  • 文件连接计数
  • 文件存取时间
  • 文件状态
  • 访问计数
  • 链接指针
  • 。。。
• Inode bitmap
  • 记录已分配的Inode和未分配的Inode
• Data block
  • Data block是存放文件内容的地方
  • 每个block都有唯一的编号
  • 文件的block记录在文件的Inode上
• Block bitmap
  • 功能与Inode bitmap类似 记录Data block的使用情况
• Superblock
  • 记录整个文件系统相关信息的地方
  • Block和Inode的使用情况
  • 时间信息、控制信息等

• df -T 列出挂在的磁盘
• dumpe2fs /dev/sda2 查看文件系统的Inode信息
• stat [文件名] 查看文件的具体信息

设备管理

• 广义的IO设备
• IO设备的缓冲区
• SPOOLing技术

广义的IO设备

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

按照使用特性分类

IO设备的缓冲区

与高速缓存的作用一样，也是为了解决CPU与IO设备的速率不匹配问题

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

IO设备的缓冲池

• 专用缓冲区只适用于特定的IO进程
• 当这样的IO进程比较多时，对内存的消耗也很大
• 操作系统划出可供多个进程使用的公共缓冲区，称之为缓冲池

SPOOLing技术

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

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