Mengzelev's Blog

操作系统期末复习笔记

Word count: 3,008 / Reading time: 11 min
2019/06/21 Share

这其实是jyy课程讲义摘抄

存储介质

维度:价格、容量、速度、可靠性

持久化存储介质统称Non-Volatile Memory

IO设备与驱动

设备:三种操作(发送命令、读取状态、传输数据)的集合

管理IO设备

查看系统IO设备:lspci,lsblk
(实现: open("/sys/bus/pci"))

Loop Back Device(回路设备):把一个文件模拟成一个块设备
a pseudo-device that makes a file accessible as a block device in Unix-like operating systems

IO设备类型众多、访问模式差距很大
解决:抽象层——设备驱动
设备驱动:操作系统对设备进行的额外抽象,使得更上层的部分(通常是文件系统)能够以统一的接口访问这些设备,i.e.把文件API翻译成设备命令

  • 设备驱动层帮助我们屏蔽了底层设备的具体实现细节
  • 使得创建“虚拟”设备非常容易(/dev/random,/dev/null)

I/O设备最主要的功能:input/output(read/write)
还有一些设备相关设置(ioctl)

DMA

解决中断没能解决的问题
一个完成CPU和设备之间数据传输的I/O设备
这样CPU可以在传送数据时做别的事

文件系统概念

存储设备虚拟化
虚拟磁盘:一个可以读写的动态字节序列
传统理解:文件系统是保存在持久存储上的数据结构(存储格式规范+允许的操作)

文件系统【以下是我能找到的所有描述】

  • 存储设备的虚拟化机制
  • 保存在持久存储上的数据结构
  • 文件名到虚拟磁盘的映射
  • 管理操作系统内部对象的中间层
  • 连接应用程序与设备驱动的桥梁
  • 管理操作系统中能够抽象成“虚拟磁盘”接口访问的任何数据

文件系统实现 = 数据结构的查询/修改操作
文件:可读写的数据对象,相当于一个虚拟磁盘
文件操作

  • 打开(返回文件描述符),关闭
  • 文件描述符操作:read,write,lseek,ioctl,mmap…

目录:文件和目录的集合
目录操作

  • 改变进程工作目录(没有/bin/cd)
  • 目录解析
  • 读取目录
  • 目录操作:link,unlink,rename

文件系统设计

文件(扩展):操作系统中的一个可读/写/控制的对象
文件描述符:指向操作系统对象的handle
管理操作系统对象的本质:传递数据的需求

为什么/proc不是进程树?-方便根据pid查找进程

虚拟文件系统:把read/write翻译成对操作系统对象(进程线程、文件目录、设备等)的读写

文件系统API

文件系统管理

挂载:mount -t type device dir
把一个设备和一个文件系统实现联系起来,在设备上创建一个文件系统实例,并且把创建的文件系统“放置”到文件系统中的一个路径里

chroot

切换根目录
只影响路径解析
如果持有外部文件描述符很容易越狱

目录管理

本质也是文件,只是操作系统在路径解析、目录遍历时对它的数据有特殊的解读

硬♂链接

  • 目标只能是文件(不能是目录)
  • 不能跨越文件系统

符号链接

  • 目标可以是任何相对/绝对路径
  • 只是一个路径解析提示

文件管理:打开文件

打开目录:得到一个指向文件系统某个位置的指针

文件操作:文件描述符

  • 避免每次操作都要重新打开文件
  • 帮助我们自动管理文件访问的偏移量

文件系统的同步

操作系统做了很多激进地缓存,所以多用sync

文件系统实现

实现文件系统需要考虑以下因素

  • 虚拟磁盘的数据结构(链表,树…)
  • 目录文件的数据结构
  • inode的表示和存储
  • balloc/bfree的实现

块设备

固定大小的block的数组
/sys/block里可以找到
块设备API:进程/线程向存储设备提交I/O request, request首先进入设备队列,经过调度器调度后执行设备上的I/O
操作系统不管Block I/O调度,只管进程尽可能公平地获得I/O操作和请求优化

虚拟磁盘

数据结构:链表/树,提供balloc/bfree
链表在文件小时表现较好,索引的lseek性能更好
block bitmap(联系L3)

文件应该有

  • 一个唯一的编号
  • 元数据信息(类型,大小,权限,访问时间、链接数量、索引)

目录文件

目录=文件名$\to$文件id的映射

Inode的存储

存储方式 好处 坏处
在磁盘用单独区域统一存储和管理 查找快速(可以快速计算出inode在磁盘中的位置) 容易被破坏(备份);浪费空间
存储在目录文件中(如FAT) 节约空间 不支持硬链接
存储在文件头部 容错性

评价文件系统

  • 性能
    • 存在超大文件、超大目录时各个操作的性能表现
    • 在各种类型workload的读写(顺序/随机,读/写分布)、目录操作比例下的性能表现
    • 多进程并发时的文件系统表现
  • 可靠性
    • 在系统可能意外崩溃时文件系统实现的正确性
    • 在磁盘可能损坏的前提下文件系统的可靠性

FAT和ext2

File Allocationg Table

链表实现文件,为每个block维护一个next block
文件分配表:集中存储next

PBR(Partition Boot Record):存储在分区头部

缺陷

  • 读写序列不够连续
  • FAT容易被枪毙(一般都有两个备份)
  • 文件系统可能碎片化(巨大的文件可能散落在磁盘的各个角落)
  • 不支持链接只是因为手册里没写
  • FAT32最大文件只有4GB(因为是从小磁盘时代过来的)

磁盘碎片整理:使文件尽可能在磁盘中占有连续的块

ext2

索引实现文件:混合多种存储方式
inodes单独管理:支持硬链接
inodes连续存储:提高文件访问的局部性
相比于FAT空间浪费比较多

分组

  • 分配分成了两级(组级、块级)
    • 不用管理全局的bitmap
  • 一定程度的性能优化
    • 尽量把相近的文件分配在同一个组里
    • 尽量把同一个文件的数据块分配在同一个组里
  • 使磁盘大小容易动态调整

持久数据的可靠性

RAID

如何把虚拟磁盘映射到物理磁盘块

RAID-0

没有冗余

  • 方案1
Block 磁盘1 磁盘2
#0 0 3
#1 1 4
#2 2 5
  • 方案2
Block 磁盘1 磁盘2
#0 0 1
#1 2 3
#2 4 5
方案一 方案二
顺序读写速度 1X 2X
随机读写速度 2X 2X

实际使用中对目录访问较多(顺序读写),方案2中磁盘2等于没有

毫无容错

RAID-1 镜像

维护两块数据完全一样的磁盘实现容错

Block 磁盘1 磁盘2
#0 0 0
#1 1 1
#2 2 2
#3 3 3

RAID-4

Block 磁盘1 磁盘2 磁盘3 磁盘4 磁盘P
#0 0 1 2 3 $0\oplus1\oplus2\oplus3$
#1 4 5 6 7 $4\oplus5\oplus6\oplus7$
#2 8 9 10 11 $8\oplus9\oplus10\oplus11$
#3 12 13 14 15 $12\oplus13\oplus14\oplus15$
  • 顺序读:4X
  • 顺序写:4X
  • 随机读:4X
  • 随机写:X/2(校验盘是性能瓶颈)

RAID-5

RAID-4升级版

Block 磁盘1 磁盘2 磁盘3 磁盘4 磁盘P
#0 0 1 2 3 P
#1 4 5 6 P 7
#2 8 9 P 10 11
#3 12 P 13 14 15
  • 随机写可以并发

带宽分析

见OSTEP

RAID硬件

  • 缓冲&日志
  • 奇偶校验电池
  • 保证数据写回

崩溃恢复与日志

磁盘上的数据结构

读磁盘的请求:

  • 读一个已经写过的块,可以不从磁盘读取
  • 读一个未被访问过的块,必须从磁盘读取(等待)

写磁盘的请求:

  • 原则上可以无限排队,让磁盘的读请求先行
  • 但同时最终应当被写入磁盘

原子性的丧失

崩溃=缓存数据丢失

简单的workload: 追加写

  1. $FAT[b’]\leftarrow EOF$
  2. $data[b’]\leftarrow$ 数据
  3. $FAT[f_{end}]\leftarrow b’$

一下考虑所有可能的崩溃情况

  • $FAT[b’]\to$❌ (dead block/leak)
  • $data[b’]\to$❌ (random writes, 写到了没办法再读到的地方)
  • $FAT[f{end}]\to$❌ (corrupted FAT, inconsistency)
  • $data[b’]\to FAT[f_{end}]\to$❌ (random writes + corrupted FAT)
  • $FAT[b’]\to data[b’]\to$❌ (dead block * 2)
  • $FAT[b’]\to FAT[f_{end}]\to$❌ (corrupted file, incorrect data)
  • $FAT[f_end’]\to FAT[b’]\to data[b’]$ ✅

dead block不是个很大的问题所以$FAT[b’]\to FAT[f_{end}]\to data[b’]$是个相对可以接受的方案,但这只是追加写,一般情形就很困难了

文件系统一致性

当磁盘上的数据结构不合法或不满足文件操作的语义,文件系统就处于不一致的状态,e.g.

  • 链接成环
  • FAT指向未被分配数据块
  • 两个文件的索引共享数据块

FSCK

File System Checking
在崩溃后扫描磁盘进行补救

缺陷:

  • 为了一点小事扫描整个磁盘,太花时间了
  • 没人能证明这么做一定能回到一个一致的状态
  • fsck的时候也会崩溃

实现崩溃一致性

Key idea: 使磁盘上的状态能推导出某个过去时刻的文件系统状态
借助sync()保证数据写入磁盘后才返回

日志(Journaling)

把操作以append only的方式记下来:写入TXbegin和数据→sync→写入TXEND→sync
用一个额外的指针维护journal完成的时刻

崩溃恢复:从指针开始向后重做journal中记录的操作
优化:合并log,只对metadata做journaling(但可能导致应用程序丢失数据)

期末复习

I/O设备模型

传输数据、发送命令、读取状态这三种操作的集合

设备驱动:操作系统对设备进行的额外抽象,使得更上层的程序能够以统一的接口访问这些设备

main函数之前的故事

hello的第一条指令:ld.so_start

hello的main函数执行之前

  1. 加载器(ld.so)把hello进程的地址空间加载进来
  2. 加载器的_start加载libc到hello进程的地址空间
  3. 进入hello自己的_start, 调用__libc_start_main

线程安全的printf

复习条件变量和信号量

文件系统的实现

FAT

  • 维护了(可能不止)一份文件分配表,记录每个文件中每一个block的下一个block的编号,位于文件系统头部、super block之后
  • block被称为sector的cluster
  • 文件的元数据(inode)保存在目录项里,不支持链接,目录项按顺序存储在文件中
  • 缺陷:lseek困难,FAT块容易被枪毙,文件系统碎片化

ext2

  • 多级索引
  • inode单独管理,提高了文件访问的局部性
  • 目录项顺序存储inode编号、该目录项长度、类型、文件名
  • 分组:不用管理全局的bitmap,性能优化,简化磁盘大小动态调整

保护数据不受损害

RAID

RAID lv. 容量 容错 顺序读 顺序写 随机读 随机写
0 $n$ 0 $n$ $n$ $n$ $n$
1 $n/2$ $1…n/2$ $>n/2$ $n/2$ $n$ $n/2$
4 $n-1$ 1 $n-1$ $n-1$ $n-1$ $1/2$
5 $n-1$ 1 $n-1$ $n-1$ $n$ $n/4$

fsck

崩溃之后的补救措施

  • 扫描inodes里所有数据块,检查bitmap的一致性
  • 检查inode数据是否看起来合法,否则删除
  • 检查链接情况,没有链接的inode被移到lost+found目录

缺陷:没事儿就扫描整个磁盘开销太大;也不一定能把文件系统恢复成一致的状态;fsck的时候崩溃了就完蛋了

日志

  • 记录所有操作
  • 维护一个指针,指向已经完成的checkpoint
  • 崩溃后从指针处开始重做所有操作,向后恢复
  • 优化:批处理;metadata journaling
CATALOG
  1. 1. 存储介质
  2. 2. IO设备与驱动
    1. 2.1. 管理IO设备
    2. 2.2. DMA
  3. 3. 文件系统概念
    1. 3.1. 文件系统设计
  4. 4. 文件系统API
    1. 4.1. 文件系统管理
      1. 4.1.1. chroot
    2. 4.2. 目录管理
      1. 4.2.1. 硬♂链接
      2. 4.2.2. 符号链接
    3. 4.3. 文件管理:打开文件
    4. 4.4. 文件操作:文件描述符
    5. 4.5. 文件系统的同步
  5. 5. 文件系统实现
    1. 5.1. 块设备
    2. 5.2. 虚拟磁盘
    3. 5.3. 目录文件
      1. 5.3.1. Inode的存储
      2. 5.3.2. 评价文件系统
  6. 6. FAT和ext2
    1. 6.1. File Allocationg Table
      1. 6.1.1. 缺陷
    2. 6.2. ext2
      1. 6.2.1. 分组
  7. 7. 持久数据的可靠性
    1. 7.1. RAID
      1. 7.1.1. RAID-0
      2. 7.1.2. RAID-1 镜像
      3. 7.1.3. RAID-4
      4. 7.1.4. RAID-5
      5. 7.1.5. 带宽分析
      6. 7.1.6. RAID硬件
  8. 8. 崩溃恢复与日志
    1. 8.1. 磁盘上的数据结构
    2. 8.2. 原子性的丧失
      1. 8.2.1. 简单的workload: 追加写
    3. 8.3. 文件系统一致性
    4. 8.4. FSCK
    5. 8.5. 实现崩溃一致性
      1. 8.5.1. 日志(Journaling)
  9. 9. 期末复习
    1. 9.1. I/O设备模型
    2. 9.2. main函数之前的故事
    3. 9.3. 线程安全的printf
    4. 9.4. 文件系统的实现
      1. 9.4.1. FAT
      2. 9.4.2. ext2
    5. 9.5. 保护数据不受损害
      1. 9.5.1. RAID
      2. 9.5.2. fsck
      3. 9.5.3. 日志