设备管理

• 设备名：逻辑设备名是用户指定的，可更改；物理设备名是系统提供的设备标准名，不可更改

• 两种设备独立性

• 程序独立于系统分配给它的设备

• 程序尽可能独立于它使用的IO设备类型

• 实现设备独立性

• 指派指令实现

• 软通道实现：

  • 用户不涉及物理设备，仅将逻辑设备指派给程序（使用open/write等函数）
  • 系统会自动创建一个逻辑设备描述符，并在程序请求设备时分配和连接真实设备

• 逻辑设备描述符ldd

• 放置在进程的pcb中

• 关闭逻辑设备实质上是进程不再使用该逻辑设备，进程pcb释放相应设备的ldd

• 设备控制块dcb

• 每个设备装入系统时都会创建一个

• 除了物理设备名、IO总线上的设备地址等信息外，还有设备的特性信息。

1. 设备分配

• 外部设备分为==独占与共享==两类
• 用静态分配处理独占设备，用动态分配处理共享设备
• 分配算法
• 先请求先服务FRFS
• 优先级最高者优先（依据进程发出请求的优先级）
• 静态分配：进程运行期间独占一些设备使用。设计简单，但设备使用率不高。
• 动态分配：进程申请使用，由设备管理模块分配，使用完立即归还。使用率较高。
• 虚拟分配

2. 虚拟分配

• 核心：让独占、慢速的设备，在逻辑上变成一个共享、快速的设备
• 虚拟设备：用外存来代替独占慢速的设备区域，这段外存就叫虚拟设备
• 虚拟分配：
• 直接往外存输入数据，独占设备一刻不停的处理外存的数据，并输出到外存中。
• 因此这个外存相当于独占设备的Buffer，由于Buffer可以共享和快速读取，所以这个外存就类似于一个虚拟的设备。

3. Spool假脱机系统

• 利用虚拟分配技术，如果进程在执行前，先将所有需要输入的内容全部写到外存
• 那么进程在执行中，就无需连接设备，直接与外存这个虚拟设备交互即可（交互时机由OS决定）

4. IO控制

与设备寄存器交互的方式：

• PIO：指定连接端口号，与设备寄存器直接连接。
• MMIO：将主存区域映射到设备寄存器中，CPU往主存对应区域写入，设备根据对应区域数据自动更新寄存器内容。

输入输出有四种方式：

• IO轮询方式（类似于spin-lock）：CPU/主存<->IO控制器(数据缓冲等reg)<->外部设备。

• 等待输入的进程会==循环检测==reg的完成位，直到完成位为1（外部输入完成），进程才将数据发往CPU/主存。

• IO中断方式（类似于mutex-lock）：CPU/主存<->IO控制器(数据缓冲等reg)<->外部设备。

• 等待输入的进程需要被睡眠，输入完成后会发送一次中断（中断位为1），去唤醒进程接收数据。

• 通道技术：CPU/主存<->不同特性的通道<->IO控制器(数据缓冲等reg)<->外部设备。

• 通道分为字节多路通道（并发慢速）、数组多路通道（并发中速）、选择通道（串行高速）

• 通道==几乎代替==CPU执行传输，外部数据输入后，通道会发送一个中断让CPU回来接收输入数据。

• DMA技术：CPU/主存<->IO控制器(数据缓冲等reg+DMA控制器)<->外部设备。

• 与通道类似，DMA控制器==完全代替==CPU执行传输任务，外部数据输入后，DMA自行控制输入数据的接收。

5. 缓冲技术

• 缓解传输双方的速度差异的方法：IO中断、通道技术和缓冲技术。
• 缓冲区实质是一块外存区域，这一点和虚拟设备类似，都是把外存当buffer用。
• 单缓冲：输入设备<->buf1<->用户进程
• 需要注意buf双方的同步关系（生产者消费者问题）
• 双缓冲：输入设备<->buf1/buf2<->用户进程
• buf1和buf2之间是互斥关系：当buf1满时，生产者才能使用buf2；同理，消费者当buf2空时，才能使用buf1。
• 环形缓冲
• 缓冲池BufferPool：可以作为高速缓存，保留最近访问过的物理块，减少相同访问时的磁盘查询。

文件系统

• 文件系统种类：磁盘、数据库、日志、网络/分布式、特殊（如管道）、虚拟文件系统。

1. 文件组织

• 文件的逻辑结构与物理结构：
• 逻辑结构是用户看到的，物理结构时物理存储器上的存储方式。
• 结构的操作单位：
• 逻辑记录：文件中最小操作的逻辑单位

• 物理记录：

  • 磁盘中读写的最小物理单位为扇区
  • 文件系统中读写的最小物理单位为块（1块=n扇区）
  • 文件系统中文件分配的最小物理单位为簇（1簇=x块=y扇区）

• 文件的逻辑结构：

• 无结构的流式文件
• 有结构的记录式文件（顺序文件、索引文件、索引顺序文件）
• 文件的物理结构：连续分配、链接分配（即串分配）、索引分配
• 记录特点：定长、不定长
• 存取方法：顺序存取、随机存取
• 存取方法由“物理结构+记录特点”决定

2. 记录式文件的结构（FAT表等结构）

• 基本数据结构
• 文件卷控制块：每个文件系统都有一个。记录文件系统的详细信息如块、块大小、空余快、计数、指针等，如Unix中的superblock
• 文件控制块FCB：每个文件一个，包括文件的详细信息如访问权限、拥有者、大小、数据块位置等，如Unix中的vnode
• 目录项：每个目录项一个（目录和文件），将目录项数据结构以及树形布局编码成数据结构，指向文件控制块、父目录、子目录。
• 基本数据结构均持久存入外存，需要时才加载进内存：
• 文件卷控制块：当文件系统挂载时进入内存
• 文件控制块：当文件被访问时进入内存
• 目录项：在遍历一个文件路径时进入内存

3. 连续分配

• 用线性表存储记录
• 连续结构
  • 存放在==磁盘的连续物理块==上
  • 文件目录->文件A目录项（文件信息+连续物理块长度+保存第一块的块号）->第一块、...、最后一块
• 逻辑记录大小 = 一个表项对应数据在物理块中的大小
• 存取连续文件：需要存取文件A中，记录号为$r_i$的记录。设记录长度为L，物理块大小为size。
• 一般假定物理块size与逻辑记录大小L相等，但注意有时可能不等
• 已知文件第一条记录的物理块号，求记录的绝对块号？
  • 文件A内，记录号为$r_i$相对第一条记录的逻辑地址：$$L\times i$$
  • 文件A内，记录号为$r_i$相对第一条记录的相对块号：$$b_i = \frac{L\times i}{size}$$（上一步到这一步其实==只是转换一个单位==）
  • 查找文件A第一条记录的物理块号：$B_0$
  • 则文件A中记录号为$r_i$的记录，的绝对块号为：$$B_0 + b_i$$

4. 链接分配（串分配）

• 用链表存储记录
• 串联结构
  • 文件目录->文件A目录项（文件信息+保存第一块的块号）->第一块（块内容+最后1B保存下一块的块号）->下一块
• 文件映照结构：文件映照表是一个以==磁盘块号为索引的列表==，元素间相互链接
  • 文件目录->文件A目录项（文件信息+保存第一块的索引a）->元素a（第一块的块号+最后1B保存下一块的索引b）->元素b

5. 索引分配

• 用索引表建立记录的映射：文件分为两个区，索引区存放索引表，数据区存放数据文件

• 逻辑记录大小 = 一个表项对应数据在物理块中的大小

• 索引表的结构及其计算

• 直接索引：索引表中表项顺序存储

  • $表项数=磁盘总大小/单位磁盘块大小$

  • $表项大小=存储表项数所需的二进制大小$（若有$540K(<1024K)$个表项，至少需要20bit来存储，因此表项大小为2.5Byte）

  • $$数据区大小 = 表项数\times逻辑记录大小$$

  • $$索引区大小 = 表项数\times表项大小$$

• 一级间接索引：利用一个磁盘块作为间接索引表

  • $$间接表项数 = \frac{索引表大小}{表项大小}=\frac{磁盘块大小}{表项大小}$$
  • $$数据区大小 = 0级表项数\times(1级表项数\times逻辑记录大小)$$
  • 文件大小 = 数据区
  • 总占用大小 = 数据区 + 0级索引区 + 1级索引区（等于一个物理块）

6. 文件管理（磁盘块分配）

• 空闲块表/空闲块链表
• 磁盘块分配算法：首次适应、最佳适应、最坏适应
• 位示图
• 是一个二维表（其中每一个bit就是一个块）
  • 0表示未分配，即空闲块；1表示已分配
• 列数固定为字长，若字长为16bit，列数为16，则一行是2Byte
• 块号= (字号,位号) = (行,列)