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)S1Sn 表示该进程所需要的所有资源

  • 信号量集

    在 AND 型信号量的基础上增加 tit_idid_itit_i 表示资源的分配下限值,SitiS_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) S1S \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 ,可存储 1284 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. 《计算机操作系统》 汤小丹 梁红兵 哲凤屏 汤子瀛