[面试直通版]操作系统核心之存储系统(下)

点击->操作系统复习的文章集<-点击

目录

页面置换算法

典型问题：

页面置换算法所需数据结构

缓存置换算法

Linux文件系统

典型问题：

常见文件系统

软链接-硬链接

磁盘冗余阵列

典型问题：

RAID是什么

RAID分级方案

---

• 页面置换算法

• 典型问题：

• 编程实现LRU算法
• 编程实现LFU算法

• 页面置换算法所需数据结构

• 实现常见的页面置换算法所需的数据结构是双向链表
• 单向链表
• 每个节点相互之间是独立的
• 每一个节点都有下一个节点的地址或引用
• 通过地址或引用就能把原来没有关联的节点给串联起来
• 双向链表
• 在单向链表的基础上加了一些东西
• 它存放的地址或引用是双向的
• 每一个节点都有上一个节点和下一个节点的地址或引用
• 好处：
• 可以快速找到一个节点的下一个节点
• 可以快速找到一个节点的上一个节点
• 可以快速去掉链表中的某一个节点

• 缓存置换算法

• 先进先出算法(FIFO)
• 最近最少使用算法(LRU)
• 最不经常使用算法(LFU)
• 先进先出算法(FIFO)
• 来个例子说
• 一个队列里有1~8的8块缓存
• 如果说要把9这块置换出来的话
• 就把最前面的1给置换出去
• 这样就能实现页面的置换
• 可以用双向链表实现
• 分别用2个指针指向头部和尾部
• 每往队尾插入一个节点时，就把队头往下移一位就可以实现了
• 最不经常使用算法(LFU)
• 优先淘汰最不经常使用的字块
• 需要额外的空间记录字块的使用频率
• 来个例子说
• 有1~8的8块缓存
• 使用了一个额外的频率字段来记录每一块的使用频率
• 第一次访问2
• 那么就更新对应频率+1
• 再访问6
• 也同样更新对应频率+1
• 经历了一段过程后
• 各块缓存频率都发生了变化
• 现在要把9这块缓存置换进来
• 这时就要挑出当前缓存里访问频率最低的那个，也就是最不经常使用的缓存
• 把它淘汰出去，然后将9这块缓存加进来
• 最近最少使用算法(LRU)
• 优先淘汰一段时间内没有使用的字块
• 有多种实现方法，一般使用双向链表
• 把当前访问节点置于链表前面(保证链表头部是最近使用的)
• 来个例子说
• 假设缓存4个字块
• 首先访问1字块，而容量为4，是不发生淘汰的
• 又访问了2字块，2放头部
• 又访问了4字块，4放头部
• 又访问了7字块，7放头部
• 再访问了5字块，5放头部，已经达到缓存的最大容量，这时淘汰队尾，也就是1
• 再访问了4字块，4又重新放到头部
• 可以看到置换的本质是淘汰一个，选入一个
• 关键的是淘汰的过程不同的算法淘汰的节点是不一样的

• Linux文件系统

• 典型问题：

• Linux软链接与硬链接有什么区别
• Linux文件系统的Inode节点是什么

• 常见文件系统

• Windows常见：
• FAT NTFS
• Linux常见：
• ext2/3/4
• 文件系统是操作系统用于明确存储设备或分区上的文件的方法和数据结构
• 即在存储设备上组织文件的方法
• 操作系统中负责管理和存储文件信息的软件机构称为文件管理系统，简称文件系统
• FAT文件系统
• FAT(File Allocation Table)
• FAT16，FAT32等，微软DOS/Windows使用的文件系统
• 它使用一张表来保存盘块的信息
• 来个例子来说
• 一个完整的文件分为5块(分别是2,9,7,18,16)来存储
• FAT如何索引文件信息？
• 首先它有一个完整的表，如从1~20
• 然后每一文件有一个单独的链表来保存文件的所有盘块
• 比如说2,9,7,18,16就是通过链表的形式连接
• 这样就可以索引到文件的所有信息
• 包括物理块以及它的下一盘块
• NTFS文件系统
• NTFS(New Technology File System)
• Windows NT环境的文件系统
• NTFS对FAT进行了改进，取代了旧的文件系统
• EXT文件系统
• EXT(Extended file system)：扩展文件系统
• Linux的文件系统
• EXT2/3/4数字表示第几代
• 主要有以下几个结构：
• Boot Sector
• 启动扇区，安装开机管理程序
• Block Group
• 块组，存储数据的实际位置
• 每一块组又会保存以下信息
• Inode table
• 存放文件Inode的地方
• 每一个文件(目录)都有一个Inode
• 是每一个文件(目录)的索引节点
• Inode和文件有关，保存了文件的很多信息
• 注意：
• 文件名不是存放在文件的Inode节点上的，而是存放在目录的Inode节点上
• 所以列出目录文件的时候无需加载文件的Inode，只需目录的Inode就可以把所有目录文件都加载出来
• Inode bitmap
• Inode的位示图
• 记录已分配的Inode和未分配的Inode
• Data block
• Data block是存放文件内容的地方
• Superblock，文件系统描述，Inode bitmap，Block bitmap还有Inode table都是存放的块组源信息
• 只有Data block才是具体存放文件的地方
• 每个block都有唯一的编号
• 文件的block记录在文件的Inode上
• Block bitmap
• 功能与Inode bitmap类似
• 记录Data block的使用情况，即标记已分配和未分配
• Superblock
• 记录整个文件系统相关信息的地方
• Block和Inode的使用情况
• 时间信息，控制信息等等

• 软链接-硬链接

• 通过之前的介绍知道了
• Linux文件是由Inode和block这2部分组成
• Inode保存的是文件的源信息
• block保存的是文件的数据
• 2者是分开的独立的
• 硬链接直接指向源文件的Inode
• 软链接它会有完整的文件包括Inode和block
• 但是它的block存储的是源文件的路径
• 具有相同Inode节点号的文件互为硬链接文件
• 删除硬链接文件或者删除源文件任意之一，文件实体并未被删除
• 创建硬链接命令：ln 源文件 硬链接文件
• 软链接类似Windows系统的快捷方式
• 软链接里面存放的是源文件的路径，指向源文件
• 删除源文件，软链接依然存在，但无法访问源文件内容

• 磁盘冗余阵列

• 典型问题：

• 什么是服务器的RAID存储？
• RAID 0,RAID 1,RAID 5有什么区别？

• RAID是什么

• RAID(Redundant Array of Independent Disks):磁盘冗余阵列
• 利用虚拟化存储技术把多个硬盘组合起来，成为一个或多个硬盘阵列组
• 目的为提升性能或减少冗余，或是两者同时提升

• RAID分级方案

• RAID 0
• 把磁盘组成一个大的冗余阵列
• 每一个block都是独立的
• 优：
• 因为每个磁盘都是独立的，所以性能为单块磁盘的N倍(有10个磁盘，N就是10)
• 缺：
• 它不提供数据校验和数据冗余
• 因为每个磁盘都是独立的，相互之间没有复制和冗余
• 所以某块磁盘损坏，数据直接丢失且无法恢复
• 应用：读写要求高
• RAID 1
• 与RAID 0非常类似，但是它的数据是做了个完整的冗余的
• 它的数据无差别双写工作磁盘和镜像磁盘
• 所以也可以算出性能为单块磁盘的N/2倍
• 数据可靠性强，只要不是同时损坏，都可以恢复
• 应用：数据安全/容易恢复
• RAID 5
• 引入了校验码，并且会把校验信息存放在不同的磁盘阵列上
• 它是数据中心最常见的RAID等级
• 提供纠错海明码实现数据冗余校验
• 有了纠错海明码它的利用率是远远大于之前RAID 1的50%
• 分散校验盘，提高写性能，降低校验盘出错概率
• 应用：兼顾经济性/数据安全
• RAID 10
• 是RAID 0和RAID 1的结合体
• 既保证了数据冗余又保证了读写效率
• 但是磁盘空间存储冗余，浪费严重
• 应用：数据安全/容易恢复