TIP

《计算机操作系统》课程笔记

1 操作系统引论

配置在计算机硬件上的第一层软件

1.1 操作系统的目标和作用

1.1.1 操作系统的目标

• 方便性 避免用户书写机器语言
• 有效性 防止大部分设备处于空闲状态，在操作系统的调度下各部分的协调恰如其分
• 可扩充性 能方便地增添新的功能和模块
• 开放性 按照某些标准开发，以便软硬件的兼容等等

1.1.2 操作系统的作用

• OS 作为用户与计算机硬件系统之间的接口

• OS 作为计算机系统资源的管理者

  • 处理器上可执行的指令分为
    • 特权指令
    • 非特权指令
  • 处理器状态划分为
    • 管态（管理态）
    • 目态（用户态）

  处理器状态保证了特权指令的正确使用，把 OS 与用户程序区别开来

• OS 实现了对计算机资源的抽象

1.1.3 推动操作系统发展的主要动力

• 不断提高计算机资源利用率
• 方便用户
• 器件的不断更新换代
• 计算机体系结构的不断发展
• 不断提出新的应用要求

1.2 操作系统的发展过程

1.2.1 未配置操作系统的计算机系统

1. 人工操作方式

   人工装填纸带，CPU 大多数时间在等待，浪费了大量的资源

2. 脱机输入/输出（Off-Line I/O）方式

   在手工与 CPU 之间加上了一个磁带，以优化 I/O 与 CPU 速度不匹配的问题

1.2.2 单道批处理系统

• 单道批处理系统（Simple Batch Processing System）的处理过程

  用监督程序来解放装填纸带人员的双手，并进一步解决了 I/O 与 CPU 之间速度不匹配的问题

• 单道批处理系统的特征

  • 单道性 内存中仅有一道程序运行
  • 自动性
  • 顺序性

1.2.3 多道批处理系统

• 多道程序设计的基本概念

  用户提交的作业形成队列，按一定算法将若干作业调入内存

• 多道程序设计的优点

  • 提高 CPU 利用率
  • 提高内存和 I/O 设备利用率
  • 增加系统吞吐量

• 多道程序设计的缺点

  • 平均周转时间长
  • 依然无交互能力

1.2.4 分时系统

• 分时系统产生的动力

  • 人们亟需可以实现人机交互的处理机以便调试运行程序
  • 共享主机

• 分时系统实现中的关键问题

  • 及时接收 及时接收各个用户终端的输入
  • 及时处理 及时处理用户键入的命令

=> 分时系统，将 CPU 的时间分片，每个作业每次只能运行一个时间片

• 分时系统的特征

  • 多路性
  • 独立性 每个人都好像独占资源
  • 及时性
  • 交互性

1.2.5 实时系统

• 需求

  • 实时控制
  • 实时信息处理

• 实时任务

  • 按任务执行时是否呈现周期性来划分
    • 周期性实时任务
    • 非周期性实时任务
  • 根据对截止时间的要求来划分
    • 硬实时任务
    • 软实时任务

• 实时系统与分时系统特征的比较

  • 多路性
  • 独立性
  • 交互性
  • 及时性
  • 可靠性

1.2.6 微机操作系统的发展

1. 单用户单任务操作系统

   • CP/M
   • MS-DOS

2. 单用户多任务操作系统

   各种 Windows

3. 多用户多任务操作系统

   UNIX

   • Solaris
   • Linux ❤️

1.2.7 其它操作系统

• 网络操作系统
• 分布式操作系统 可独立也可协同，对用户来说相当于一个操作系统
• 嵌入式操作系统

1.3 操作系统的特征

1.3.1 并发性

并行和并发的区别，组原就有提到，并行是真的多处理器处理多数据，并发是利用时分技术实现的，其微观本质上还是串行

为了实现并发，引入了进程的概念，其作为资源分配的基本单位，可在系统中能独立运行

为了进一步提高并发程度，在进程内引入了线程，其作为独立运行和独立调度的基本单位，并不会拥有系统资源，开销就会小很多

1.3.2 共享性

• 互斥共享技术

  保证各个进程之间不会混淆

• 同时访问方式

  各个进程可以同时访问同一个设备，比如磁盘

1.3.3 虚拟技术

• 时分复用技术
  • 虚拟处理机技术
  • 虚拟设备技术
• 空分复用技术
  • 虚拟磁盘技术 磁盘分区
  • 虚拟存储器技术

1.3.4 异步性

各个进程停停走走……

1.4 操作系统的五大功能

1.4.1 处理机管理

• 进程控制
• 进程同步
• 进程通信
• 调度

1.4.2 存储器管理功能

• 内存分配
• 内存保护
• 地址映射
• 内存扩充

1.4.3 设备管理功能

• 缓存管理
• 设备分配
• 设备处理

1.4.4 文件管理功能

• 文件存储空间的管理
• 目录管理
• 文件的读/写管理和保护

1.4.5 操作系统与用户之间的接口

• 用户接口
• 程序接口

1.4.6 现代操作系统的新功能

• 系统安全
• 网络的功能和服务
• 支持多媒体

1.5 OS 结构设计

1.5.1 传统的操作系统结构

1. 无结构操作系统
2. 模块化结构操作系统 分解成一个一个模块
3. 分层式结构 OS 有序分层

1.5.2 客户/服务器（C/S）模式简介

便于集中管理，但会有瓶颈问题和不可靠性

1.5.3 面向对象的程序设计（OOP）简介

1.5.4 微内核 OS 结构

• 足够小的内核

  将操作系统中最基本的部分放入微内核，其他部分放在外面作为服务器

• 基于 C/S 模式

• 应用”机制与策略分离“原理

• 采用面向对象技术

2 进程管理

2.1 进程的基本概念

2.1.1 程序的顺序执行及其特征

• 程序的顺序执行是指程序可以保证其按照其顺序执行

• 特征

  • 顺序性
  • 封闭性
  • 可再现性

2.1.2 程序的并发执行及其特征

• 多道程序并发执行

• 特征

  • 间断性
  • 失去封闭性
  • 不可再现性 （资源共享，可能使用时被其他程序所修改）

2.1.3 进程的特征与状态

• 定义

  • 进程是程序的一次执行
  • 进程是一个程序及其数据在处理机上顺序执行时所发生的活动
  • 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位

• 特征

  • 结构性
  • 动态性
  • 并发性
  • 独立性
  • 异步性

• 状态

  • 活动进程的三种状态
    • 就绪
    • 执行
    • 阻塞
  • 另外两种状态
    • 创建
    • 终止
  • 挂起状态（将进程内存 $\to$ 外存）

  N 核 CPU ，共有 M 个进程

  • 就绪态用户进程最多几个？最少几个？
  • M-N, 0
  • 执行态用户进程最多几个？最少几个？
  • N, 0
  • 阻塞态用户进程最多几个？最少几个？
  • M, 0

2.1.4 进程控制块 PCB

系统是根据进程的 PCB 感知到该进程的存在的,PCB 是进程存在的唯一标志，因此系统总是通过 PCB 对进程进行控制的

• PCB 中的信息

  • 进程标识信息
    • 内部标识号 PID ，操作系统分配
    • 外部标识号 由字母数字组成的，创建者提供
  • 处理机状态信息
    • 通用寄存器
    • 指令计数器
    • 程序状态字 PSW
    • 用户栈指针
  • 进程调度信息
    • 进程状态
    • 进程优先级
    • 进程调度所需的其它信息
    • 事件
  • 进程控制信息
    • 程序和数据的地址
    • 进程同步和通信机制
    • 资源清单
    • 链接指针（当然，索引方式应该是没有的）

• PCB 组织方式

  • 链接方式 组织成链表

  • 索引方式 额外建立一个索引表，更快，但是额外消耗一部分内存

2.2 进程控制

通过原语来实现

原语是原子操作，是不可分割的基本单位，要么全做、要么全不做

2.2.1 进程的创建

• 进程图

  是一种树状的家族关系，子进程继承父进程资源，如 UNIX

  Windows 不是这种关系，Win 的各个进程之间是平等的，并不是层次关系，进程之间的关系是通过获取句柄来调节的

• 引起创建进程的事件

  • 用户登录
  • 作业调度
  • 提供服务
  • 应用请求

• 进程的创建原语（Create）

  • 申请空白 PCB
  • 为新进程分配资源
  • 初始化 PCB
  • 将新进程插入就绪队列

2.2.2 进程的终止

• 引起进程终止的事件

  • 正常结束
  • 异常结束
    • 越界错
    • 保护错
    • 非法指令
    • 特权指令错
    • 运行超时
    • 等待超时
    • 算术运算错
    • I/O 故障
  • 外界干预
    • 操作员或操作系统干预
    • 父进程请求
    • 父进程中止

• 进程的终止原语（termination）

  • 根据被终止进程的标识符，检索出 PCB ，读取进程状态
  • 若处于执行状态，则立即终止
  • 若还有子孙进程，则递归终止
  • 将资源归还其父进程或者系统
  • 将被终止进程 PCB 从所在队列中移出

2.2.3 进程的阻塞与唤醒

• 引起进程阻塞和唤醒的事件

  • 请求系统服务
  • 启动某种操作
  • 新数据尚未到达
  • 无新工作可做

• 进程阻塞原语（block）

• 进程唤醒原语（wakeup）

2.2.4 进程的挂起和激活

• 进程挂起原语（suspend）
• 进程激活原语（active）

2.3 进程同步

本章节 Python 实现 (opens new window)

2.3.1 进程同步的基本概念

• 两种形式的制约关系
  • 间接相互制约关系（互斥） 多个进程共享系统资源
  • 直接相互制约关系（同步） 多个进程之间共同访问缓冲区

问题的根源就在于 临界资源

• 临界资源 就是发生冲突的部分 比如共享的系统资源（硬件临界资源）、共享的缓冲区（软件临界资源）

• 临界区 每个进程中访问临界资源的那段代码，我们将一个访问临界资源的循环进程描述如下

  while (TRUE) {
     进入区（entry section）
     临界区（critical section）
     退出区（exit section）
     剩余区（remainder section）
  }
  

  各进程对自己的临界区访问是互斥的

• 同步机制应遵循的规则

  • 空闲让进
  • 忙则等待
  • 有限等待
  • 让权等待

2.3.2 硬件同步机制

• 关中断 但是会引发一系列问题
• 利用 Test-and-Set 指令实现互斥 将“测试并建立”作为一条原语
• 利用 Swap 指令实现进程互斥 使用 lock 和 key 两个变量

他们虽然都实现了互斥，但是都有一个很大的问题，就是尝试访问资源是连续测试的（如 while TS(&lock);），仍然浪费 CPU 资源，不符合“让权等待”原则

2.3.3 信号量机制

• 整型信号量

  wait(S) {
      while (S <= 0);
      S--;
  }
  signal(S) {
      S++;
  }
  

  问题当然是，还是不符合“让权等待”原则

• 记录型信号量

  typedef struct {
      int value;
      struct process_control_block *list;
  } semaphore;
  wait (semaphore *S) {
      S->value--;
      if (S->value < 0) block(S->list);
  }
  signal(semaphore *S) {
     S->value++;
     if (S->value <= 0) wakeup(S->list);
  }
  

  与前面不同的是，我们现在定义了一个数据结构，增加了一个列表，这个列表干嘛呢？

  由于我们要在无法获取资源的时候将 CPU 资源让出去，所以 while 轮询是不可行的了，我们可以使用 block 原语将自己阻塞起来，等到有资源的时候让别人唤醒自己，当然，为了保证别人能唤醒自己，就要把自己存储到一个列表中，就是我们新的数据结构中的那个列表啦

  另外，我们可以将 value 当做资源数，初始化的数量就是资源的总数量

• AND 型信号量

  当一个进程需要多个资源才能执行怎么办呢？比如进程一二都需要资源一二，进程一请求资源一成功，进程二请求资源二成功，这时候进程一继续请求资源二，把自己阻塞起来了，进程二请求资源一，也把自己阻塞起来了，结果……死锁了……

  如何解决？如果我们将某个进程请求一系列资源作为一个原语就可以啦，这样就不需要担心请求一部分另一部分没请求到的问题啦，这时候使用 Swait(S1, S2, ..., Sn) 和 Ssignal(S1, S2, S3, ..., Sn) ， S1 到 Sn 表示该进程所需要的所有资源

• 信号量集

  在 AND 型信号量的基础上增加 $t_i$ 和 $d_i$ ，$t_i$ 表示资源的分配下限值，$S_i \geq t_i$ 才予以分配，$d_i$ 表示资源的需求量，对应格式变为 - $Swait(S_1, t_1, d_1, \cdots, S_n, t_n, d_n)$ - $Ssignal(S_1,d_1, \cdots, S_n, d_n)$

  有以下几个特殊用法：

  • Swait(S, d, d) 每次申请 d 个资源，低于 d 个不予申请
  • Swait(S, 1, 1) 一般的记录型信号量
  • Swait(S, 1, 0) $S \geq 1$ 时，允许多个进程进入特定区， $S = 0$ 时，将阻止任何进程进入特定区

  有个细节需要注意下，就是 Swait 结束后被唤醒并不能直接进入临界区，还需要重新尝试请求资源，因为这个时候并不能保证所有资源都就绪，而 wait 只需要一个资源，这就保证了被唤醒后资源一定全部就绪，所以可以直接进入临界区

2.3.4 信号量的应用

• 使用信号量实现互斥

  （两个进程为例）使用 mutex 作为互斥信号量，它可以取 {-1, 0, 1} ，初始化为 1

  • mutex = 1，表示两个进程均未进入临界区
  • mutex = 0，表示一个进程进入临界区
  • mutex = -1，表示一个进程进入临界区，另一个尝试进入临界区失败，阻塞并存入队列

  为了实现互斥，就需要两个进程进入临界区前调用 wait(mutex) ，出临界区后调用 signal(mutex)，否则会引发错误

• 利用信号量实现前趋关系

  如何保证一个进程运行到命令 B 的时候另一个进程已经将命令 A 运行完了？比如一个进程要读取另一个进程写完的文件，怎么保证在这之前另一进程写操作已经完成？

  仍然使用这个套路，不过将 mutex 初值置为 0 ，我们在后继任务前调用 wait(mutex) ，在前趋任务完成后调用 signal(mutex) ，这样就可以保证后继任务先到达的话会阻塞，而前趋任务完成后，就会“通知”后继任务可以开始做啦

• 管程机制

  是使用面向对象将共享变量、条件变量以及各种方法等等封装起来，同时只能有一个进程进入管程，这就保证了对临界资源的访问是互斥的

  当调用管程的进程被阻塞时，其它进程也就不能进入管程使用资源，为了解决该问题，管程内设了条件变量，当进程因为条件 x 而发生阻塞时，进程调用 x.wait 方法，将自己加入阻塞队列，直到条件 x 发生了变化，其它进程（当时正在管程内的进程）调用 x.signal 将队列 x 下的进程唤醒

2.4 经典进程的同步问题

2.4.1 生产者-消费者问题

PC.py (opens new window)

• 使用记录型信号量解决该问题

  • 生产者先后使用 wait(empty) wait(mutex) signal(mutex) signal(full)
  • 消费者先后使用 wait(full) wait(mutex) signal(mutex) signal(empty)

  注意 wait 的先后顺序，如果 wait(mutex) wait(empty) 可以想象下满了或者空的情况，会出现死锁……

• 利用 AND 信号量解决该问题

  • 生产者先后使用 Swait(empty, mutex) Ssignal(mutex, full)
  • 消费者先后使用 Swait(full, mutex) Ssignal(mutex, empty)

  解决死锁问题

• 利用管程解决该问题

  定义好管程内要做的，生产者用 PC.put(x)， 消费者用 PC.get(x) 即可

一些变体

• 缓冲区无限大，那么我们就不需要 wait(empty) signal(empty) 了
• 生产者生产者互斥、消费者消费者互斥，但生产者消费者不互斥，我们只需要设两个互斥信号量即可

2.4.2 哲学家进餐问题

The_Dining_Philosophers.py (opens new window)

• 利用记录型信号量解决该问题

  防止他们同时拿起左侧筷子造成的死锁，需要有一定的改进方案

• 利用 AND 信号量机制解决该问题

  很容易想到这个方法解决上述问题

2.4.3 读者-写者问题

Writer_and_Reader.py (opens new window)

需要注意的是，当一个 Writer 进程在写的时候，不允许任何 Reader 进程和 Writer 进程访问该对象

但是要怎么实现呢？

• 写者的话，直接用一个互斥信号量 wmutex 就好了
• 读者需要考虑的比较多
  • 首先，读者之间是不互斥的，我们是要解决读者使写者不能读的问题，所以当读者在读的时候， wait(wmutex)
  • 但是，如果直接 wait(wmutex) 的话，所有“者”都互斥了，可是多个读者是可以同时读的
  • 我们判断下是否已经有人在读了，当无人在读的情况下也就是第一个读者才 wait(wmutex)，相应地，最后一个读者才 signal(wmutex)
  • 为了判断读者数量，额外引进了一个变量，这个变量会成为临界资源，所以需要使用 rmutex 包裹，以保证读者读写该变量时互斥

另外，可以利用信号量集以更巧妙的方法实现（注意 Swait(S, 1, 0)，只检查资源，不消耗）

Writer_and_Reader.py (opens new window)

2.4.4 其他问题（习题）

• 购物问题 Shopping.py (opens new window)
• 进程同步 Processes.py (opens new window)
• 独木桥问题 Single-plank_Bridge.py (opens new window)

2.5 进程通信

• 共享存储器系统

  • 基于共享数据结构的通信方式
  • 基于共享存储区的通信方式 中等信息传递，用户解决同步问题

• 管道(pipe)通信系统 大量信息传递，系统解决同步问题

• 消息传递系统 少量信息传递，系统解决同步问题

• 客户机-服务器系统

  • socket
  • RPC

2.6 线程的基本概念

2.6.1 线程与进程的对比

• 调度的基本单位 切换开销小
• 并发性 线程之间也可以并发执行
• 拥有资源 并不拥有系统额外分配的资源，享有父进程的资源，故创建开销小
• 独立性 同一进程的不同线程之间可以共享资源，独立性不明显
• 系统开销 创建与切换都远比进程快
• 支持多处理机系统 一个进程的多个线程可在多个核心上运行，这使得多个线程之间实现了真的并行，大大提高了该进程的完成速度

2.6.2 线程的状态和线程控制块

• 线程的三个状态 和进程一样 执行、就绪、阻塞
• 线程控制块 TCB 类似于 PCB

2.7 线程的实现

2.7.1 线程的实现方式

• 内核支持线程 KST

  内核所“承认”的线程，可获得内核分配的 CPU 时间片，也可在多核 CPU 上实现并行

  • 优点
    • 更轻量的结构
    • 进程中一个线程阻塞后，其余线程可正常运行
    • 多核心可并发执行

• 用户级线程 ULT

  使用函数库就可以实现，内核并不知道用户级线程的存在，所以内核给它分配的时间片是按其父进程分配的，各个线程将争夺进程的时间片执行

  • 优点
    • 线程切换不需要到内核空间（不需要用户态与核心态的切换）
    • 调度算法可以是进程专用的
    • 用户级线程的实现与 OS 平台无关

• 组合方式

  用户级线程与内核支持线程的组合（多对一、一对一、多对多）

3 处理机调度与死锁

3.1 处理机调度的层次

调度程序	调度对象	分配资源	调度频率	适宜的调度算法
长程调度（作业）	后备作业	内存、设备	低	资源搭配、先进先出、优先数、短作业优先、最高响应比优先
中程调度（交换）	就绪进程、等待进程	内存、外存	中	优先算法、FIFO
短程调度（进程）	就绪进程、就绪线程	CPU	高	轮转法、多级反馈

3.1.1 高级调度

• 作业 = JCB + 作业说明书 + 程序 + 数据

• 作业步 作业的各个相对独立步骤

• 作业控制块 JCB

• 调度算法

  • 先来先服务算法
  • 短作业优先调度算法
  • 响应比高者优先的调度算法 综合考虑上面两种算法
  • 基于作业优先级的调度算法

3.1.2 低级调度

• 基本机制

  • 排队器
  • 分派器
  • 上下文切换机制 （两对上下文切换操作）

• 进程调度方式

  • 非抢占方式
  • 抢占方式（按一定原则抢占 CPU）
    • 优先权原则
    • 短作业（进程）优先原则
    • 时间片原则

3.1.3 中级调度

将内存上的进程转换到外存上或相反的过程，也就是进程的挂起与唤醒，提高了内存的利用率

3.2 调度队列模型和调度准则

3.2.1 调度队列模型

• 仅有进程调度的调度队列模型

• 具有高级和低级调度的调度队列模型

• 同时具有三级调度的调度队列模型

3.2.2 选择调度方式和调度算法的若干原则

• 面向用户的原则

  • 周转时间快 （使用平均周转时间评估）
  • 响应时间快
  • 截止时间的保证
  • 优先权准则

• 面向系统的准则

  • 系统吞吐量高
  • 处理机利用率好
  • 各类资源的平衡利用

3.3 调度算法

• 周转时间：作业等待的时间
• 带权周转时间：周转时间 / 服务时间

3.3.1 先来先服务算法

很明显， FCFS 的周转时间会很长

3.3.2 短作业（进程）优先调度算法

SJF 算法极大地提高了系统吞吐量，但是会出现长作业长期不被调度（饿死）的情况

3.3.3 高优先权优先调度算法

• 优先权调度算法的类型

  • 非抢占式优先权算法
  • 抢占式优先权调度算法

• 优先权的类型

  • 静态优先权 不可改变的
  • 动态优先权 可随着进程的等待时间而改变，我们可以规定，在就绪队列的进程，随其等待时间的增长，其优先权以速率 a 提高

• 高响应比优先调度算法（HRP）

  优先权 = (等待时间 + 要求服务时间) / 要求服务时间

• 最短剩余时间调度算法（SRT）

  与 SJF 相似，但是抢占式的，选择预期剩余时间最短的进程

3.3.4 基于时间片的轮转调度算法

• 时间片大小的确定

  • 时间片太大会使得算法退化，时间片太小会增大切换上下文的开销，故可以取略大于一次典型交互所需要的时间作为时间片

3.3.5 多队列调度算法

分成不同的队列，为不同就绪队列设置不同的调度算法

3.3.6 多级反馈队列调度算法

• 设置多个就绪队列
• 为每个队列设置一个优先级
• 仅当优先级高的队列空闲时才能调度优先级低的队列

3.4 实时调度

3.4.1 实现实时调度的基本条件

• 提供必要的信息 就绪时间等等
• 系统处理能力强
• 采用抢占式调度机制
• 具有快速切换机制

3.4.2 实时调度算法的分类

• 非抢占式调度算法
  • 非抢占式轮转调度算法
  • 非抢占式优先调度算法 将实时任务放在队首
• 抢占式调度算法
  • 基于时钟中断的抢占式优先权调度算法 时钟周期的整数倍时刻才能抢占
  • 立即抢占的优先权调度算法

3.5 产生死锁的原因和必要条件

3.5.1 产生死锁的原因

• 竞争资源（竞争非剥夺性资源） 资源数量不足需求 形成环路

• 进程间推进顺序非法

3.5.2 产生死锁的必要条件

• 互斥条件
• 请求和保持条件 所需资源使用完之前不释放已有资源
• 不剥夺条件 只能主动释放资源，其他人不可抢占
• 环路等待条件 发生死锁时，必然存在资源的环路链

3.5.3 处理死锁的基本方法

• 预防死锁
• 避免死锁
• 检测死锁
• 解除死锁

3.6 预防死锁

由于死锁时必要条件一定满足，所以破坏了死锁的必要条件就可以防止死锁，当然，互斥条件我们不应该破坏，因为我们需要它来保证进程的同步问题

3.6.1 摒弃“请求和保持”条件

由动态分配改为静态分配，在所有进程运行之前一次性将所有所需资源申请下来

但是，这大大降低了资源的利用率

3.6.2 摒弃“不剥夺”条件

新的资源请求会剥夺已占有的资源

很复杂很复杂，打印机写一半怎么处理呢？增加了系统开销

3.6.3 摒弃“环路等待”条件

资源有序分配，将各个资源标号，每次申请资源都要按序号递增的次序来申请，避免了环路的产生

比如一个进程已经拥有了一个序号比较高的资源，此时想申请序号比较低的资源的话，必须先释放序号比较高的资源

相比前两种是比较好的策略，但仍有一些不足，比如序号的分配等等问题

3.7 避免死锁

3.7.1 系统安全状态

如果为进程分配资源后系统会进入不安全状态，那么就不给它分配资源

所谓安全状态，就是指系统存在某种进程顺序来为每个进程分配其所需资源，使得所有进程都能顺利完成，否则即为不安全状态

当然，不安全状态只是不安全，可能发生死锁，并不是一定发生死锁，而安全状态保证了不会发生死锁

• Example

  进程号	总共需求	已分配	还需	剩余
  P1	10	5	5	3
  P2	4	2	2
  P3	9	2	7

  很明显，存在安全序列 <P2, P1, P3> 使得进程全部执行完毕

  那么，P3 申请一个资源的话，我们要不要给呢？

  首先，假如分配的话，会变成如下状态

  进程号	总共需求	已分配	还需	剩余
  P1	10	5	5	2
  P2	4	2	2
  P3	9	3	6

  嗯，找不出来那样的一个序列了，也就是系统会进入不安全状态，所以，拒绝！不给分配！

3.7.2 利用银行家算法避免死锁

（万能的 Dijkstra）

• 银行家算法中的数据结构

  n 为进程数， m 为资源数

  • 可利用资源向量 Available ($m$)
  • 最大需求矩阵 Max ($n \times m$)
  • 分配矩阵 Allocation ($n \times m$)
  • 需求矩阵 Need ($n \times m$)

具体算法的话，就是上面例子里的一个资源换成多个资源就好啦

3.8 死锁的检测与解除

3.8.1 死锁的检测

由于死锁的预防的资源利用率太低，而死锁的避免又消耗了大量的计算资源来实现，所以在死锁发生的并不频繁的情况下，可以使用死锁的检测 + 解除，当然，我们可以选择在 CPU 利用率比较低的时候才检测，以降低对 CPU 的使用

• 资源分配图

与前面的环路图是一样的，只不过这里资源结点可以代表多个资源，进程指向资源仍旧代表进程请求资源，资源指向进程仍旧代表资源以分配给该进程，只不过每条线代表一个资源

我们可以尝试通过对资源分配图进行简化来判断是否发生死锁，非死锁情况下资源分配图可简化为各个独立的结点

3.8.2 死锁的解除

• 剥夺资源 从其他进程剥夺足够数量的资源给死锁进程
• 撤销进程 kill 掉死锁进程

作业 (opens new window)

4 存储器管理

4.1 存储器的层次结构

4.1.1 多级存储器结构

4.1.1 主存储器与寄存器

嗯……就是主存储器和寄存器……

4.1.2 高速缓存和磁盘缓存

• 高速缓存 Cache

  解决 Memory 与 CPU 速度不匹配的问题

• 磁盘缓存

  解决磁盘 I/O 与 Memory 速度不匹配的问题，使用 Memory 部分空间作为磁盘的缓存区，用于暂存频繁使用的磁盘数据

4.1.3 内存管理

（概述，后面详细阐述）

• 内存的分配与回收
  • 直接分配 程序内地址为固定值
  • 静态分配 作业装入内存后地址固定不变
  • 动态分配 作业装入内存后地址可变
• 地址转换
  • 逻辑地址：源程序内的变量等地址经过编译或汇编后生成逻辑地址
  • 物理地址：程序由操作系统装入内存后所指的真实内存地址
• 内存保护
  • 防止进程的数据被非法访问
  • 防止越界
    • 上下界寄存器
    • 基址、限长寄存器
• 内存共享
  • 多个进程共享内存中的同一段信息
• 内存扩充
  • 覆盖 让常用功能常驻内存，非常用功能按需装入
  • 对换 挂起不用的程序段
  • 虚拟存储器 利用程序的局部性原理，将部分程序装入

4.2 程序的装入和链接

4.2.1 程序的装入

即上面的三种分配方式

• 绝对装入方式 直接
• 可重定位装入方式
  • 静态重定位 程序执行之前地址转换完毕
  • 动态重定位 程序执行期间进行地址转换

4.2.2 程序的链接

• 静态链接 程序运行前链接
• 装入时动态链接 运行前将所有可能需要运行的模块装入链接
  • 便于修改和更新
  • 便于实现对目标模块的共享
• 运行时动态链接 运行时按需装入链接（如 dll）

4.3 连续分配方式

4.3.1 单一连续分配

单用户、单任务，只需要考虑系统区和用户区，用户区也只有一个任务……

4.3.2 固定分区分配

一个分区一道作业，所以就需要划分分区咯

4.3.3 动态分区分配

根据进程的实际需要，动态地为之分配内存空间

• 数据结构

  • 空闲分区表
  • 空闲分区链 （就是个链表）

• 分区分配算法

  • 首次适应算法 从头找，能放下该作业就放
  • 循环首次适应算法 使用一个指针，这样就不会每次都从头找啦
  • 最佳适应算法 每次找满足条件的最小分区
    • 易形成碎片
  • 最坏适应算法 每次找最大的分区，分割出一部分分配给该作业使用
    • 使得存储器中缺乏大的空闲分区
    • 查找效率高
    • 产生碎片少

• 内碎片 分区内部未利用的空间
• 外碎片 分区之间未利用的空间

• 分区回收算法
  • 看上下有没有空闲区咯，有的话当然要合并~

4.3.4 可重定位分区分配

依赖于 4.1.3 中提到的动态分配技术，这样分区就可以移动啦，然后我们就可以将分区进行拼接、使之紧凑起来

4.4 基本分页存储管理方式

将内存分为好多好多页，支持不连续分配，使用页表形成地址映射，每个进程一个页表

• 可实现虚存
• 避免移动
• 避免外部碎片

4.4.1 页面与页表

• 页面就是将逻辑地址空间分为大小相等的片，其大小应为 $2^n$
• 物理块是物理地址空间对应的与页面大小相同的存储块
• 页表就是将页（面）号与（物理）块号对应起来的映射表

当然，现在寻址的话需要两部分地址号了，一部分是页号，一部分是页内号（位移量），一般情况下页内大小为 $4K$ ，故页内号需要使用 $12bit$ 的地址，如果是 $32bit$ 系统的话，那么剩下 $20bit$ 就是页号地址空间啦，即最多 $1M$ 个页

4.4.2 地址变换机构

• 基本的地址变换机构

  那么我们如何将逻辑地址转换成物理地址呢？

  首先，获取页号和偏移量，然后根据页表寄存器中的页面始址与页号获得该页的实际物理地址（开始位置），然后再加上页内的偏移量就得到了要找的物理地址

  但是，我们的页表已经非常大了，寄存器是肯定放不下了，需要放到内存中去，也就是说，我们每次访存需要先访问内存中的页表，然后据此再得到真正想要访问的地址，也就是访存次数多了一倍，效率大大降低……

• 具有快表的地址变换机构

  根据局部性原理，我们增加一个快表（联想寄存器），存储最近访问过的页表项，据统计，快表命中率可达 90% 以上，大大降低了页表方式带来的效率降低影响

4.4.3 两级和多级页表

我们的页表方式实现了非连续存储，但是我们的页表本身却也是放在内存里的，而且其大小也超过了一页的大小（$1K$），这样问题就来了，页表到底是要如何存储呢？

回到最初，我们是如何将离散存储的内存页组织起来的？很明显是通过页表，但是现在要求连续存储的页表也要离散存储了，我们如何将其组织起来呢？那就再加一层页表咯，这就形成了两级页表

事实上，在 $64bit$ 系统下，三级页表都是不够的，但是我们事实上也用不上那么大的地址空间（等内存能那么大得多少年后啊……），所以暂时使用三级页表也是能满足现在的需求的

4.4.4 页式管理的分配与回收

根据位示图进行分配与回收即可

4.4.5 页式管理的特点

• 优点
  • 分配与回收简单
  • 消除外碎片
  • 可实现虚存、共享
• 缺点
  • 页面划分不考虑程序的逻辑结构
  • 共享受限
  • 二次访内，速度慢

4.5 分段存储管理方式

分页实现了对内存的高效利用，消除了外碎片，但是其对于用户来说仍然只是取某个地址，然后操作系统根据后 $12bit$ 作为页内地址，前 $20bit$ 为页号，实际过程对用户并不可见，用户只需要按原来的方式取某个地址就好

所以说，分页存储可以说是在底层的一种管理实现方式，大多是与硬件相耦合的，可以做到对内存的更高效利用

引入本节的分段存储方式，并不是说分页存储不好，因为它们根本是在两种层级上的问题，后面会介绍它们相互结合的方式——段页式存储——就很好地结合了两者的优点，在底层仍然使用分页式存储，上层逻辑存储使用分段式存储，但是这里，我们底层仍然使用的是连续存储方式哦

那么分段有什么优点呢？

4.5.1 分段存储管理方式的引入

• 方便编程 我们可以为某一段程序（比如一个函数）分配一段连续的空间，这样就可以很方便地使用段内的偏移量进行编程了
• 信息共享 我们很容易分出一个段来供进程来共享
• 信息保护
• 动态增长
• 动态链接

4.5.2 分段系统的基本原理

既然逻辑空间仍然划分为不等长的几段，这几段也是分别放在不同的位置，所以，我们还是需要一个表建立索引关系，只不过这次我们需要记录的有段号、段长、基址（某段的首地址）三个信息，因为我们现在每段不等长了，形成的表格称为段表，也放在内存内

相应地，我们现在给出的地址必须由段号和段内偏移两部分组成（真的是二维的寻址方式，而分页仍然使用一维寻址，两个号由操作系统自动计算得出），当然，我们仍然是两次访存，想要快点也是要建立快表

4.5.3 信息共享

比如一个多用户操作系统运行一个文本编辑进程，但多个用户每人一个数据区，如果是分页式是如何的呢？

emmm 虽说共用一个进程吧，但是每个页表都要记录该进程的各个页

相对来说，下面的分段式就很好看啦~

4.5.4 段式管理的特点

缺点的话，就是连续式存储的一些缺点，但这个的话我们下面的段页式可以解决

优点就不用说了，前面介绍好久了都~

4.5.5 段页式存储管理方式

使用分段的逻辑存储方式，加之以底层分页式存储方式，每个进程建立一个段表，每个段建立一个页表，当然，我们现在需要三次访存咯，不建立快表没法用的说

• 共享的实现

  段页式和分段式是同样容易实现共享的，因为我们在逻辑层面上使用相同的段存储一段共享数据，在段表内只需要一项，而页表内也没有重复的，只需要该段与实际存储地址之间的映射关系

很好地结合了两者的优点，所以说，两者根本不冲突嘛，他们是两种层级上的方案，或者我们这么看

逻辑\物理	连续	分页
不分段	连续分配	分页式
分段	分段式	段页式

嗯，我们所学的四种，大概就是这样的关系~

只不过逻辑分段与物理分页有着相似的实现方式，所以我们可能会认为他们是相同层级的方式，从原因与涉及的层面来看，它们并无太大关系

4.6 虚拟存储器的基本概念

前面所述的存储方式虽然实现了非连续存储，进而提高了内存的利用率，但每次都还是将整个进程装入内存，下面有个更逆天的方式，极大地提高内存利用率，那就是虚拟存储器

为什么需要虚拟存储器？因为我们的整个程序往往是很大的，很容易就将内存撑爆了，根据局部性原理，我们可以只将当前运行的部分调入内存，这样就可以大大降低内存臃肿的状态啦

4.6.1 虚拟存储器的引入

• 局部性原理

  • 时间局部性
  • 空间局部性

• 虚拟存储器定义

  基于局部性原理，应用程序在运行之前，没有必要全部装入内存，仅需将那些单前要运行的少数页面或段先装入内存便可运行，其余部分暂留在盘上

  • 请求调页 如果要访问的页（段）在内存则直接执行；否则需要发生请求调页中断
  • 页面置换 若内存已满，则将暂时不用的页调入硬盘

• 虚拟存储器特征

  • 多次性 多次调入
  • 对换性
  • 虚拟性 从逻辑上扩充内存容量

4.7 请求分页存储管理方式

需要扩展页表以支持请求分页存储

页号	物理块号	状态位 P	访问字段 A	修改位 M	外存地址
0	10	1	1	0	120
1	14	1	0	0	123
2	15	1	2	0	134
3	-	0	-	-	135

4.7.1 请求分页中的硬件支持

• 页表机制

  其中各字段说明：

  • 状态位 P ：该页是否调入内存
  • 访问字段 A ： 本页在一段时间内被访问的次数，作为选择换出页面参考
  • 修改位 M ： 记录调入内存后是否被修改过，如果被修改过，换出时需要重新写入内存
  • 外存地址

• 缺页中断机构

  请求分页时，需要的页不在内存时，产生缺页中断

  与一般中断的区别

  • 在指令执行期间产生和处理中断信号
  • 一条指令在执行期间可能产生多次缺页中断，比如该指令本身跨两个页，所需要的两个数据块分别又跨两个页，共产生 6 次缺页中断

• 地址变换机构

4.7.2 内存分配策略和分配算法

• 最小物理块数的确定

  保证进程正常运行的最小物理块数

• 内存分配策略 分配策略分为固定和可变分配策略，而置换时还有全局置换和局部置换两种置换策略

  • 固定分配局部置换

    每个进程分配固定数量的物理块

  • 可变分配全局置换

    进程的物理块数可动态调整，当所需页不在内存时，从空闲内存或者其他进程内存选择一块换出，即该进程内存空间会增加

  • 可变分配局部置换

    进程物理块数仍可动态调整，发生缺页中断从该进程内存中选择一页换出，当频繁发生缺页中断时，才可以为该进程增加物理块数，反之，若缺页率特别低，则可适当减少该进程物理块数

• 物理块分配算法

  • 平均分配算法 所有进程分配的物理块数一样，很明显不公平
  • 按比例分配算法 按照进程大小按比例分配
  • 考虑优先权的分配算法 在按比例分配算法基础上考虑重要的紧急的任务，可为该类任务额外分配物理块以使之更快地完成任务

4.7.3 调页策略

• 调入页面的时机

  • 预调页策略 额外调入连续的几页
  • 请求调页策略 当发现不在内存时，调入该页

• 确定从何处调入页面

  TIP

  外存分为

  • 文件区 离散的分配方式，读写慢
  • 对换区 连续的分配方式，读写快
  • 系统拥有足够的对换区空间，可全部从对换区调入所需页面
  • 系统缺少足够的对换区空间，需要修改的放到对换区，以便需要时从对换区调入
  • UNIX 方式，未运行的从文件区调入，运行过换出到对换区，下次可直接从对换区调入（甚至可能已经被其他进程调入内存）

• 页面调入过程

  访问需考虑是否缺页、换出需考虑是否修改过

• 缺页率

4.8 页面置换算法

4.8.1 最佳置换算法和先进先出算法

• 最佳（Optimal）置换算法

  每次换出的页应该是以后永不使用的或在最长（未来）时间内不再被访问的页面，很明显，我们并无法得知这样的页面是哪个，所以该算法仅仅是理论上的算法，虽然无法实现，但可以据此评估其他算法

• 先入先出（FIFO）页面置换算法

  顾名思义，每次换出在内存中驻留时间最久的页面，可以为内存中的页面设置一个链表很容易地实现

4.8.2 最近最久未使用（LRU）置换算法

选择最近最久未使用的页面予以淘汰，可为每个页面赋予一个访问字段进行实现

• 硬件支持
  • 寄存器 用位记录最近访问行为，每次右移，若该次访问了则将最左位置 1 ，故每次只需淘汰值最小的即可
  • 栈 用于记录访问页面，访问之后放到栈顶，置换时从栈底置换

4.8.3 Clock 置换算法

• 简单的 Clock 置换算法

  LRU 算法的一种近似算法，在页表内设一个访问位，另外设一替换指针，以免每次从头扫描

  • 访问页面后，将该页面访问位置 1
  • 缺页导致需要扫描时，从替换指针向后扫描，若该页面访问位为 1 ，则将其置 0，若为 0 ，则替换出去

• 改进型 Clock 置换算法

  由于修改过的页需要写回磁盘，所以置换修改过的页代价相对会高些，所以该算法在考虑访问位的基础上，考虑到了修改位，在访问位一致的情况下，优先淘汰修改位为 0 的页面

  具体实现就是多扫描几次，开销增大不少

4.9 请求分段存储管理方式

类似于请求分页，但是有少许的区别，该方式会更容易实现共享与保护

4.9.1 分段的共享与保护

• 共享

  可使用共享段表来实现，可内记录共享段以及相应进程信息

• 保护

  • 越界检查
  • 存储控制检查 在段表表项中设存取控制字段

作业 (opens new window)

5 设备管理

5.1 I/O 系统

I/O 很容易成为系统性能的瓶颈，而且多而杂，甚至一个操作系统的 2/3 代码都是 I/O 相关代码

5.1.1 I/O 设备

• 分类
  • 按设备的使用特性分类
    • 存储设备
    • 输入/输出设备
  • 按传输速率分类
    • 低速设备
    • 中速设备
    • 高速设备
  • 按信息交换的单位分类
    • 字符设备 以字节为单位，如打印机
    • 块设备 以块为单位，如磁盘
  • 按设备的共享属性分类
    • 独占设备（临界资源）
    • 共享设备
    • 虚拟设备

5.2 I/O 控制（数据传输）方式

• 四种 I/O 控制方式（计组里讲的那些）
  • 程序 I/O 方式（循环等待，Polling）
  • 中断驱动 I/O 方式（Interrupts）
  • 直接存储器存取（DMA）
  • I/O 通道控制方式（Channel）

5.3 缓冲管理

5.3.1 缓冲的引入

• 缓和 CPU 与 I/O 设备间速度不匹配的矛盾
• 减少对 CPU 的中断频率，放宽对 CPU 中断响应时间的限制
• 提高 CPU 和 I/O 设备之间的并行性

5.3.2 单缓冲和双缓冲

• 单缓冲
• 双缓冲

5.3.3 循环缓冲

5.3.4 缓冲池

5.4 I/O 软件

5.4.1 I/O 软件的设计目标和原则

• 与具体设备无关 上层的操作不应该考虑底层到底是什么设备
• 统一命名 对设备进行统一逻辑命名
• 对错误的处理 低层软件能够解决的错误就不让高层软件感知
• 缓冲技术 向高层提供相同大小的数据块或字符单元
• 设备的分配和释放 进程管理问题，防止死锁的发生
• I/O 控制方式 I/O 软件应向高层软件提供统一的操作接口

5.4.2 用户层的 I/O 软件

需要通过系统调用获得操作系统服务（可通过库函数实现）

5.4.3 设备独立性软件

应用程序独立于具体使用的物理设备

• 在应用程序中，使用逻辑设备名称来请求使用某类设备
• 系统在实际执行时，还必须使用物理设备名称

这就需要操作系统能够完成这种转换功能

这可以带来以下好处

• 设备分配时的灵活性
• 易于实现 I/O 重定向

设备独立性软件功能主要有

• 执行所有设备的公有操作
• 向用户层（或文件层）软件提供统一接口

逻辑设备名到物理设备名映射的实现

使用逻辑设备表（LUT），内含逻辑设备名、物理设备名、设备驱动程序的入口地址

5.4.4 设备驱动程序

I/O 进程与设备控制器之间的通信程序

功能：

• 接收由设备独立性软件发来的命令和参数
• 检查用户 I/O 请求的合法性
• 发出 I/O 命令
• 及时响应由控制器或通道发来的中断请求
• 对于设置有通道的计算机系统，驱动程序还应能够根据用户的 I/O 请求，自动地构成通道程序

特点：

• 设备驱动程序主要是指在请求 I/O 的进程与设备控制器间的一个通信和转换程序
• 驱动程序与设备控制器和 I/O 设备的硬件特性紧密相关，因而对不同类型的设备一个配置不同而驱动程序
• 驱动程序与 I/O 设备所采用的 I/O 空盒子方式紧密相关
• 由于驱动程序与硬件紧密相关，因而其中的一部分必须用汇编语言书写

5.4.5 中断处理程序

• 唤醒被阻塞的驱动（程序）进程
• 保护被中断进程的 CPU 环境
• 转入相应的设备处理程序
• 中断处理
• 恢复被中断进程的现场

5.5 设备分配

5.5.1 设备分配中的数据结构

• 系统设备表（SDT， 整个系统一张）：设备名、设备控制块指针
• 设备控制块（DCT， 每设备一张）：设备状态、分配状态、等待队列、控制器控制块指针
• 控制器控制块（COCT， 每控制器一张）：控制器状态、等待队列、通道控制块、指针
• 通道控制块（CHCT， 每通道一张）：通道状态、等待序列

5.5.2 设备分配时应考虑的因素

• 设备的固有属性

  • 独占性（是否是临界资源）
  • 共享性
  • 可虚拟设备

• 设备分配算法

  • 先来先服务
  • 优先级高者优先

5.5.3 独占设备的分配程序

• 基本的设备分配程序
  • 分配设备
  • 分配控制器
  • 分配通道
• 设备分配程序的改进
  • 增加设备的独立性 使用逻辑设备名而非物理设备名
  • 考虑多通路情况

5.5.4 SPOOLing 技术

为了缓和 CPU 的高速性与 I/O 设备低速型之间的矛盾而引入了脱机输入、脱机输出技术，使用专门控制的外围机将低速 I/O 设备上的数据传送到高速磁盘上

SPOOLing 技术由脱机输入输出技术发展而来，使用输入进程和输出进程替代其中的输入处理器和输出处理器

• 组成
  • 输入井和输出井
  • 输入缓冲区和输出缓冲区
  • 输入进程 $SP_I$ 和输出进程 $SP_O$
• 特点
  • 提高了 I/O 的速度
  • 将独占设备改造为共享设备
  • 实现了虚拟设备功能

5.6 磁盘存储器的管理

5.6.1 磁盘性能简述

• 数据的组织和格式

  • 每个磁盘片分一个或两个存储面
  • 每个磁盘面被组织成若干个同心环，这种环称为磁道（同一半径的磁道总和称为柱面）
  • 每条磁道又被逻辑上划分为若干个扇区

  当然，这样的话，就会有一个三维的物理地址 $(c, h, s)$ 与一维的块号 $b$ 之间的转换关系，简单的进制转换算法，不赘述

• 磁盘的类型

  • 固定头磁盘 每个磁道一个磁头，不需移臂
  • 移动头磁盘 只在每个盘面配有一个磁头，需要移臂

• 磁盘访问时间

  地址：柱面号、磁头号、扇区号

  • 柱面定位时间 花费时间最多
  • 旋转延迟时间
  • 数据传送时间

5.6.2 磁盘调度

• 先来先服务 FCFS

• 最短寻道时间优先 SSTF

  每次都找离当前磁头最近的磁道

• 扫描 SCAN

  为避免 SSTF 所带来的“饥饿”现象，使用类似于电梯的算法，每次都先沿一个方向走到最后一个（并非尽头），然后再改变方向

• 循环扫描 CSCAN

  SCAN 对两端的磁道不公平，为此规定磁头只能单向移动，一旦该方向无新的请求，则直接回到起点一端，继续沿该方向扫描

• N-STEP-SCAN

  将请求分为 N 个长度为 M 的队列，队间用 FCFS 处理，队内用 SCAN 处理

  • M=1 -> FCFS
  • N=1 -> SCAN
  • N=2 -> FSCAN

• FSCAN

  就是上面的 N=2 的特例，将磁盘请求队列分成两个子队列，一个是由当前所有请求磁盘 I/O 的进程形成的队列，由磁盘调度按 SCAN 算法进行处理。在扫描期间，将新出现的所有请求磁盘 I/O 的进程，放入另一个等待处理的请求队列。这样，所有的新请求都将被推迟到下一次扫描时处理

5.6.3 磁盘高速缓存

• 磁盘高速缓存的形式

  将内存上的一部分存储空间作为磁盘的 Cache 使用，会缓存一些最近用过的从磁盘中取出的盘快，逻辑上属于磁盘、物理上是驻留在内存中的盘块

• 数据交付方式

  • 缓存中有，则从缓存中取
  • 若无，则从盘中取出，并存入缓存

• 置换算法 类似于请求调页算法中的置换算法，比如 LRU，下面列举一些不同点

  • 访问频率 对联想寄存器的访问频率远远高于对高速缓存的访问频率
  • 可预见性 高速缓存中对于哪些数据是会再次访问是有一定的可预见性的
  • 数据的一致性 出现问题时使得缓存与磁盘之间未同步的问题
  • 周期性地写回磁盘 按照 LRU 算法，经常使用的数据块是不会写回磁盘的，如果此时发生了故障，数据是会丢失的，所以我们可以周期性地写回磁盘以避免该问题

5.6.4 提高磁盘 I/O 速度的其他方法

• 提前读 当要读取文件的时候，由于大多采用顺序访问，故可提前读取下一个盘块数据
• 延迟写 有很大概率在不久之后再次访问
• 优化物理块的分布

6 文件管理

6.1 文件与文件系统

6.1.1 文件的概念

• 定义

  文件是计算机系统中信息存放的一种组织形式

• 文件的属性

  用于系统对文件进行管理，常见属性如下

  • 保护信息
  • 创建者
  • 只读标志位
  • 隐藏标志位
  • 系统标志位
  • 创建时间、最后访问时间、最后修改时间
  • 文件长度

6.1.2 文件的类型

• 以文件的性质和用途分类
  • 系统文件
  • 库文件
  • 用户文件
• 按文件的存取控制属性分类
  • 只读文件
  • 读写文件
  • 执行文件
• 按文件的组织形式分类

  UNIX 依此组织文件

  • 普通文件
  • 目录文件 由文件目录项组成的文件
  • 特别文件 将设备作为文件进行管理

6.1.3 文件的操作

• 建立文件
• 打开文件
• 读文件
• 写文件
• 关闭文件
• 删除文件
• 文件指针定位

6.1.4 文件系统

OS 中负责处理文件相关事宜的程序和数据结构，包括文件的查找、存放、保护、共享、命名、文件常用操作的实现以及文件存储器的管理等等

6.2 文件结构与存储设备

6.2.1 文件的逻辑结构

• 流式文件（无结构文件） 基本信息单位是字节或字，其长度是所含字节的数量

  UNIX 中，所有的文件都被看做是流式文件，即便是有结构文件，也被视为流式文件，系统不对文件进行格式处理

• 记录式文件（有结构文件） 是一种结构文件，由若干个记录组成
  • 定长记录 处理方便，开销小
  • 变长记录

6.2.2 文件的存取方法

• 顺序存取
• 随机存取（直接存取）
• 按键存取 使用 Hash 进行索引存取

6.2.3 文件的物理结构

• 连续结构 文件的全部信息存放在外存的一片连续编号的物理块中

  • 优点 简单，支持顺序存取和随机存取
  • 缺点 文件不易动态增长，预留空间浪费，不利于文件的插入和删除，存在外部碎片问题

• 串联结构（链接结构） 非连续的结构，存放文件信息的每一物理块中有一个指针，指向下一个物理块

  • 优点

    • 提高了磁盘空间利用率
    • 有利于文件插入和删除
    • 有利于文件动态扩充

  • 缺点

    • 存取速度慢，不适合随机存取
    • 链接指针占用一定的空间
    • 可靠性问题，如指针出错

• 索引结构 文件信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构——索引表，并将这些块的块号存放在索引表中

  注意，索引表也是存在物理块中的，我们使用 open （比如 C 啦， Python 啦）操作实际是将该文件的索引表加载到内存中

  • 优点

    • 保持了链接结构的优点又解决了其缺点，能顺序存取，又能随机存取
    • 满足了文件动态增长，插入删除的要求
    • 能充分利用外存空间

  • 缺点

    • 索引表本身带来了系统开销，如：内外存空间，存取时间开销等

      当索引表本身很大时，可考虑建立多级索引

• 混合索引结构（多重索引，UNIX 采用）

  首先假设一个磁盘块 512 Bytes ，可存储 128 个 4 Bytes 的索引号，我们将主索引表分为以下区域

  • 直接地址 使用 10 个直接地址项，如果文件小于 10 * 512 Bytes ，就用不到后面的啦
  • 一次间接地址 当超过十个直接地址项所能索引的大小时，一次间接地址指向一个磁盘块，将其作为索引表，很明显，我们又可以索引 128 个磁盘块，此时最大索引 10 + 128 个磁盘块
  • 多次间接地址 上述地址不足，则需要继续使用更高级的索引表……

6.2.4 文件的存储设备

磁带、磁盘、光盘、闪存 ……

6.3 文件目录管理

6.3.1 文件控制块与文件目录

• 目录项（文件控制块，FCB） 用于记录文件相关信息

  将真正的文件属性存储在 iNode 中，更容易实现文件共享的操作

  如果只有根目录 inode 在内存，那么还需要读取根目录的目录文件，s1 i_node ，s1 目录的目录文件，...，经过 6 次磁盘读取得到 file1 i_node ，之后需要读取 5 次磁盘，即最多共 11 次，如果 file1 i_node 已经在内存，只需要读取 5 次磁盘即可

6.3.2 目录结构

• 单级目录结构
• 二级目录结构
• 多级目录结构 树形

6.4 文件存储空间管理

6.4.1 空闲表法

每个文件分配一块连续的存储空间，外存的所有空闲区建立一张空闲表

6.4.2 空闲链表法

用链表来表示磁盘的空闲空间列表

• 空闲盘块链

• 空闲盘区链

6.4.3 位示图

以位示图来表征空闲区，可分配连续的区域，但是占用额外的空间

6.4.4 成组链接法

UNIX 内采用的方法，使用空闲盘块号栈进行分配回收

6.5 文件的共享

• 外存共享 （用户）
• 内存共享 （进程）

6.6 文件的保护、保密与安全

6.6.1 文件的存取控制

• 存取控制矩阵 存储占用大，验证费时
• 存取控制表

6.6.2 文件的保密

• 口令
• 密码

Extends

• 本课程配套实验 (opens new window)
• rCore Tutorial (opens new window)

References

1. 杨志豪老师课程
2. 李建明老师课程
3. 《计算机操作系统》 汤小丹 梁红兵 哲凤屏 汤子瀛