TIP

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

# 1 操作系统引论

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

# 1.1 操作系统的目标和作用

# 1.1.1 操作系统的目标

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

# 1.1.2 操作系统的作用

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

    OS01

  • 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 模式

    OS02

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

  • 采用面向对象技术

# 2 进程管理

# 2.1 进程的基本概念

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

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

  • 特征

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

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

  • 多道程序并发执行

  • 特征

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

# 2.1.3 进程的特征与状态

OS04

  • 定义

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

  • 特征

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

  • 状态

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

    OS03

    N 核 CPU ，共有 M 个进程

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

# 2.1.4 进程控制块 PCB

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

  • PCB 中的信息

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

  • PCB 组织方式

    • 链接方式 组织成链表

      OS05

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

      OS06

# 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）
}
    1
    2
    3
    4
    5
    6

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

  • 同步机制应遵循的规则

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

# 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++;
}
    1
    2
    3
    4
    5
    6
    7
    8

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

  • 记录型信号量

    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);
}
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14

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

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

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

  • AND 型信号量

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

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

  • 信号量集

    在 AND 型信号量的基础上增加 tit_i 和 did_i ，tit_i 表示资源的分配下限值，Si≥tiS_i \geq t_i 才予以分配，did_i 表示资源的需求量，对应格式变为 - Swait(S1,t1,d1,⋯,Sn,tn,dn)Swait(S_1, t_1, d_1, \cdots, S_n, t_n, d_n) - Ssignal(S1,d1,⋯,Sn,dn)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≥1S \geq 1 时，允许多个进程进入特定区， S=0S = 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 其他问题（习题）

# 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 平台无关

  • 组合方式

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

OS07

# 3 处理机调度与死锁

# 3.1 处理机调度的层次

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

# 3.1.1 高级调度

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

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

  • 作业控制块 JCB

  • 调度算法

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

# 3.1.2 低级调度

  • 基本机制

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

  • 进程调度方式

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

# 3.1.3 中级调度

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

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

# 3.2.1 调度队列模型

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

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

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

    OS08

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

  • 面向用户的原则

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

  • 面向系统的准则

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

# 3.3 调度算法

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

# 3.3.1 先来先服务算法

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

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

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

# 3.3.3 高优先权优先调度算法

  • 优先权调度算法的类型

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

  • 优先权的类型

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

  • 高响应比优先调度算法

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

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

  • 时间片大小的确定

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

# 3.3.5 多队列调度算法

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

OS09

# 3.3.6 多级反馈队列调度算法

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

# 3.4 实时调度

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

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

# 3.4.2 实时调度算法的分类

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

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

# 3.5.1 产生死锁的原因

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

    OS10

  • 进程间推进顺序非法

# 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 (mm)
    • 最大需求矩阵 Max (n×mn \times m)
    • 分配矩阵 Allocation (n×mn \times m)
    • 需求矩阵 Need (n×mn \times m)

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

# 3.8 死锁的检测与解除

# 3.8.1 死锁的检测

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

  • 资源分配图

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

OS11

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

# 3.8.2 死锁的解除

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

作业 (opens new window)

# 4 存储器管理

# 4.1 存储器的层次结构

# 4.1.1 多级存储器结构

OS12

# 4.1.1 主存储器与寄存器

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

# 4.1.2 高速缓存和磁盘缓存

  • 高速缓存 Cache

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

  • 磁盘缓存

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

# 4.1.3 内存管理

（概述，后面详细阐述）

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

# 4.2 程序的装入和链接

# 4.2.1 程序的装入

即上面的三种分配方式

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

# 4.2.2 程序的链接

OS13

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

# 4.3 连续分配方式

# 4.3.1 单一连续分配

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

# 4.3.2 固定分区分配

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

# 4.3.3 动态分区分配

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

  • 数据结构

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

  • 分区分配算法

    • 首次适应算法 从头找，能放下该作业就放
    • 循环首次适应算法 使用一个指针，这样就不会每次都从头找啦
    • 最佳适应算法 每次找满足条件的最小分区
      • 易形成碎片
    • 最坏适应算法 每次找最大的分区，分割出一部分分配给该作业使用
      • 使得存储器中缺乏大的空闲分区
      • 查找效率高
      • 产生碎片少
  • 内碎片 分区内部未利用的空间
  • 外碎片 分区之间未利用的空间
  • 分区回收算法
    • 看上下有没有空闲区咯，有的话当然要合并~

# 4.3.4 可重定位分区分配

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

# 4.4 基本分页存储管理方式

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

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

# 4.4.1 页面与页表

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

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

# 4.4.2 地址变换机构

  • 基本的地址变换机构

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

    OS14

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

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

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

    OS15

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

# 4.4.3 两级和多级页表

OS16

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

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

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

# 4.4.4 页式管理的分配与回收

OS17

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

# 4.4.5 页式管理的特点

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

# 4.5 分段存储管理方式

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

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

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

那么分段有什么优点呢？

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

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

# 4.5.2 分段系统的基本原理

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

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

# 4.5.3 信息共享

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

OS18

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

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

OS19

# 4.5.4 段式管理的特点

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

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

# 4.5.5 段页式存储管理方式

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

OS20

  • 共享的实现

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

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

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

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

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

# 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 单缓冲和双缓冲

  • 单缓冲 OS21
  • 双缓冲 OS22

# 5.3.3 循环缓冲

OS23

# 5.3.4 缓冲池

OS24

# 5.4 I/O 软件

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

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

OS25

# 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， 每通道一张）：通道状态、等待序列

OS26

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

  • 设备的固有属性

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

  • 设备分配算法

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

# 5.5.3 独占设备的分配程序

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

# 5.5.4 SPOOLing 技术

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

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

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

# 5.6 磁盘存储器的管理

# 5.6.1 磁盘性能简述

OS28

  • 数据的组织和格式

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

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

  • 磁盘的类型

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

  • 磁盘访问时间

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

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

# 5.6.2 磁盘调度

  • 先来先服务 FCFS

  • 最短寻道时间优先 SSTF

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

  • 扫描 SCAN

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

# 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 啦）操作实际是将该文件的索引表加载到内存中

    OS29

    • 优点

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

    • 缺点

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

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

        OS30

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

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

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

# 6.2.4 文件的存储设备

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

# 6.3 文件目录管理

# 6.3.1 文件控制块与文件目录

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

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

    OS33

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

# 6.3.2 目录结构

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

# 6.4 文件存储空间管理

# 6.4.1 空闲表法

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

OS34

# 6.4.2 空闲链表法

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

  • 空闲盘块链

    OS35

  • 空闲盘区链

# 6.4.3 位示图

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

OS36

# 6.4.4 成组链接法

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

# 6.5 文件的共享

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

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

# 6.6.1 文件的存取控制

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

# 6.6.2 文件的保密

  • 口令
  • 密码

# Experiment

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

# References

  1. 杨志豪老师课程及其配套课件 (opens new window)
  2. 《计算机操作系统》 汤小丹 梁红兵 哲凤屏 汤子瀛