计算机四级操作系统原理

Posted on Edited on In

背景

阅读go教程时发现忘记了进程和线程相关知识,
刚好计算机四级的书还在身边,就复习一下.

另外备注,该书虽对照2017年考试内容,但书本身内可能依然是90年代的,
因此不包含后续的许多优化方案.
以至于一些内容在今天看起来是错误的.

  1. 如今的各种容量都大了许多.
  2. 一些管理方式发生了改变,管理用信息的数据结构发生了改变.

操作系统概论

操作系统组成

  • 硬件系统(CPU,内存等,硬盘,键鼠显示器等)
  • 软件系统
    • 系统软件(操作系统,编译器等)
    • 支撑软件(网络,数据库等)
    • 应用软件

操作系统任务

  • 资源管理(组织和管理硬件及软件资源)
    • 有效(提高CPU利用率)
    • 合理(不发生死锁与饥饿现象)
  • 控制程序执行(按照用户的意愿,向用户提供各种服务)

操作系统功能

功能要满足任务要求

  • 进程管理
    • 实质是对CPU进行管理
    • 引入进程概念以提高对CPU的利用率
    • 进程控制
      • 创建,状态转换,撤销,资源分配与回收
    • 进程同步
      • 进程间关系,同步和互斥
    • 进程间通信
      • 互相协作
    • 进程调度
      • 按照一定的算法决定CPU的执行顺序
  • 存储管理
    • 内存的分配与回收
      • 为进程分配有限的空间
      • 进程退出后,回收并重利用内存空间
    • 存储保护
      • 多个进程之间能够彼此隔离,互补侵扰
    • 内存扩充(虚拟内存等方式)
  • 文件管理
    • 文件存储空间管理(提高硬盘利用率,减少碎片)
    • 目录管理(建立目录,方便组织和管理)
    • 文件安全(合理的读写权限,保护文件不被非法访问)
  • 设备管理
    • 设备的分配,启动,故障处理
    • 处理设备间速度不匹配的问题(中断,通道,虚拟设备等)
  • 用户接口
    • 提供CLI,GUI等接口

操作系统特征

  • 并发性,同时存在着若干运行着的程序
  • 共享性,多个程序共用各种资源
    • 互斥共享
    • 同时共享(宏观上)
  • 随机性,要充分考虑各种各样的可能性

操作系统历史

  • 二战期间,手工操作(插板上连线,手动拨开关,顶多有01010的概念)
  • 195x早期,穿孔卡片(稍微自动化了一些)
  • 195x中期,汇编语言出现(让0101等变成单词,便于记忆),产生JOB概念
  • 195x晚期,单道批处理(为了能在多个JOB之间自动接续,专门制作了一个监督程序,操作系统的雏形)
  • 196x中期,多道批处理(躲过程序同时在内存之中,监督程序负责切换,演化为操作系统)
  • 196x晚期,分时系统(批处理不能交互,CPU不断切换)
  • 1969,UNIX通用操作系统(贝尔实验室的Ken Thompson和Dennis M. Ritchie,结合了分时系统和批处理系统的特点)
  • 1981,MS-DOS1.0,与硬件捆绑销售
  • 2003,Android

操作系统分类(按进程处理方式)

  • 批处理
    • 成批处理,资源利用率高,作业吞吐率高
    • 不能交互
    • 由于错误处理而衍生了CPU运行模式
      • 系统专用特权模式,管态,特权指令(输入输出,停机)
      • 用户模式,目态,一般指令(可以依靠系统调用完成功能)
  • 分时系统
    • 时间片轮转方式
    • 多路,交互,宏观上独占,及时响应
  • 实时系统
    • 硬实时系统(响应时间极严格,时间精度微秒以下)
      • 火箭,导弹等不处理就有严重后果
    • 软实时系统(响应时间在一定范围内)
      • 银行,视频等
    • 能力上要求
      • 时钟管理(定时任务+事件触发的任务)
      • 过载防护(迅速找到最重要的,抛弃或者延后次要的)
      • 高可靠性

操作系统分类(按用途)

  • 个人操作系统
  • 网络操作系统
    • 集中式模式
    • 分布式模式
  • 分布式操作系统
    • 所有主机使用同一个操作系统
    • 没有主从关系和特殊性,对用户屏蔽差异(对用户透明)
    • 资源深度共享(任务可以迁移到其他主机上)
    • 低成本的高性能
    • 高可靠性(一个坏了还有其他)
  • 嵌入式操作系统
  • 智能卡操作系统(片内操作系统)
    • 集成电路卡

操作系统分类(按结构)

  • 整体式结构/模块组合结构
    • 功能划分为模块
    • 模块间互相调用,耦合严重
    • 数据全局可用,限制了并发性
  • 层次式结构
    • 功能分层,模块放入各个层中,层之间的模块只能单向调用和依赖,事实上只能尽量减少循环
    • 可替换性好,方便维护
  • 微内核(S/C)结构
    • 内核只提供很少的一些功能(线程调度,虚拟存储,消息传递,设备驱动,中断处理)
    • 外部是若干独立的服务进程(文件服务,网络服务)
    • 用户层有用户的Client
    • Client->内核->服务进程->内核->Client
    • 耦合最为松散,可靠,灵活,适宜分布式环境
    • 效率较低

操作系统运行机制

CPU

操作系统依赖的硬件核心是CPU,CPU的核心则是运算器.
了解操作系统的工作,需要先了解操作系统是如何使用CPU的.
或者说,操作系统是如何利用CPU的工作方式,从而工作的.

  1. CPU结构

    CPU无非就是勤垦地执行它得到的指令.
    指令的执行过程与CPU的结构息息相关.

    CPU的结构:

    • 运算器,进行逻辑运算
    • 控制器,控制程序流程(取指令,维护CPU状态,CPU与内存交互,详见指令执行过程)
    • 寄存器,暂时存放一些数据,速度最快
    • 高速缓存,用于匹配内存与寄存器之间的速度差异

    其中寄存器下有分类

    • 用户可见寄存器,所有程序可用
      • 数据寄存器(通用寄存器),存放各种数据
      • 地址寄存器,存储各种地址,如数据的,指令的,指针的
      • 条件码寄存器,保存CPU操作结果的各种标记位,如溢出,符号,一般是只读的
    • 控制和状态寄存器,通常只有特权模式下才能使用
      • 程序计数器(PC),存放指令的地址
      • 指令寄存器(IR),最近取出的指令
      • 程序状态字(Program Status Word,PSW),记录处理器的运行模式信息等

    其中PSW通常包含以下flag

    • 标准条件位
      • CF: 进位
      • ZF: 结果为0
      • SF: 正负号
      • 0F: 溢出
    • 其他
      • TF: 陷阱
      • IF: 是否允许中断
      • VIF: 虚拟中断
      • VIP: 虚拟中断待决
      • IOPL: IO特权级别
      • 等等

  2. 指令正常执行过程

    1. 开始
    2. 取指
      1. 指令 = 内存[程序寄存器.指令地址]
      2. 程序寄存器.指令地址++ (增加一个指令长度,比如4字节)
      3. 指令 -> 指令寄存器
    3. 执行指令
      1. 指令经过译码电路,CPU了解如何操作
      2. 执行具体操作
    4. 取指
    5. 执行指令
    6. 取指
    7. 执行指令
    8. 结束

    其中指令的具体分类有

    1. 访问存储器指令,内存->寄存器 or 寄存器->内存
    2. IO指令,寄存器->IO or IO->寄存器
    3. 算术逻辑指令, 寄存器中数据±
    4. 控制转移指令,更改程序寄存器.指令地址
    5. 处理器控制指令,修改处理器状态

    举例

    1
    2
    3
    4
    地址            指令
    2000h:   MOVE   [3340h],  R1
    2004h:   ADD    R1,       1
    2008h:   MOVE   R1,       [3340h]

    具体过程是

    1. 取指令
      1. 程序计数器中地址为2000h,取出指令放入指令寄存器
      2. 程序寄存器中地址变为2004h
    2. 执行
      1. 指令寄存器中为MOVE指令,表示移动数据
      2. 将内存[3340h]处数据放入数据寄存器R1
    3. 取指令
      1. 从[2004h]取到IR中
      2. 变成[2008h]
    4. 执行
      1. IR中内容为ADD,表示运算
      2. 将寄存器R1中数据加1
    5. 取指令
      1. 从[2008h]取到IR中
      2. 变成[2012h]
    6. 执行
      1. IR中内容为MOVE,表示移动数据
      2. 将寄存器R1中数据移动到内存[3340h]处

  3. 区分系统与普通用户

    多道处理系统中,会运行许多不同的应用,为了能合理安排这些应用,
    操作系统必须时刻稳定.

    为了区分开操作系统与普通应用,以免普通应用做了危险操作导致机器停止运行,
    因此使用 CPU状态 x 指令分类 的正交方式来规划CPU能否执行一些指令

    CPU状态分为

    • 管态,特权态,特态,系统态
    • 目态,普通态,普态,用户态

    有的处理器比如intel,支持4个级别

    • R0(最高,相当于管态)
    • R1(权限逐渐降低)
    • R2
    • R3(最低,相当于目态)

    但多数系统只用到了R0和R3

    指令分为

    • 特权指令,目态下拒绝执行特权指令
      • 启动设备
      • 设置时钟
      • 控制中断屏蔽
      • 清理内存
      • 建立存储保护
    • 非特权指令,所有应用都能使用

    有时普通的应用也的确想完成一些特殊的功能,这个时候允许它委托操作系统来完成.
    具体详见系统调用.

存储

  1. 存储的体系

    速度越快的也造价越高

    1. 寄存器
    2. 高速缓存
    3. 内存
    4. 磁盘
    5. 光盘等

    解决方法: 常用的数据放在快的存储里面,以保证平均访问时间较短

  2. 存储的保护

    操作系统应防止正在运行的程序修改不相关程序的内容.
    必须依靠硬件.

    1. 界地址寄存器,当CPU访问内存时,判断要访问的地址是否在合理范围内,
      如果越界则产生程序中断(越界中断 or 存储保护中断)
      1. 法一: 下限寄存器 + 上限寄存器
      2. 法二: 基址寄存器 + 限长寄存器
    2. 存储键
      存储块可以保留一个存储保护键,在分配内存时,操作系统保留一份于PSW,
      相应的存储块们统一改变保护键值.
      每次CPU访问存储,则对比PSW于存储块中保存的值,不同则拒绝

CPU工作中的异常处理

操作系统要多个程序并行,切换时总是轮询太耗费性能,必须要有异步.
在操作系统领域,完成一个事件后通知CPU,这种机制称为 中断.

中断的实现是软硬件结合的结果.

  • 硬件中断装置
    • 中断逻辑线路,负责接收中断信号
    • 中断寄存器,包含若干中断位,1表示有信号,0表示没有信号
  • 中断处理软件

CPU任劳任怨地取指令,执行指令.
下一个取的指令在什么位置,是什么指令,什么时候跳转指令的位置,这些都是操作系统的任务.

  1. 相关概念

    • 中断事件,中断源: 引起中断的事件
    • 中断请求: 中断源发出的请求信号
    • 中断断点: 发生中断时正在处理的程序的暂停点
    • 中断处理程序: 处理中断事件的那段程序
    • 中断响应: 暂定当前程序,转而处理中断的过程
    • 中断返回: 处理结束后,恢复原先执行的过程
    • 中断字: 操作系统将各种中断赋予序号,存放在一个有序集合中,该集合
      • 通常PC的处理器最多处理256种中断
    • 中断向量表: 多少种中断就要对应多少种中断处理程序,这些中断处理程序的入口地址集合成一张表
    • 中断向量: 中断处理程序的入口地址

    中断与异常
    区别: 一开始中断异常不分家,数量多了以后,中断趋向于事件引发,异常趋向于正在执行的指令引发
    联系: 对于硬件来说处理机制相同

    中断的分类

    • 时钟中断,内部计时器产生,时间片到时,硬件时钟到时都会触发
    • IO中断,IO控制器产生,IO正常完成或发生错误时触发
    • 控制台中断,操作系统通过控制台发出的中断
    • 硬件故障中断,掉电,内存校验错误等时触发

    异常的分类

    • 程序性中断
      • 只能由操作系统处理,程序做了自己不能做出操作
        • 目态下执行特权指令
        • 越界访问
      • 程序自己能处理
        • 溢出
        • 除以0
    • 访管中断
      • 用户应用想调用系统完成功能

  2. 中断处理过程

    1. 接收中断信号
      1. 每条指令执行周期的最后时刻,扫描中断寄存器,可接收到中断向量代号
    2. 保存现场(保存正在执行程序的上下文),一般保存在专门的系统堆栈中
      1. 程序状态字PSW
      2. 程序计数器PC中的下一条指令的位置
      3. 一些寄存器的值
    3. CPU切换到管态
    4. 获取中断处理程序地址
      1. 根据中断代号查询中断向量表,得到中断处理程序入口地址
      2. 设置程序计数器PC的值为该地址
    5. 调用中断处理程序
    6. 中断处理完毕后,CPU收到中断返回指令
    7. 恢复现场
    8. CPU切换到中断前状态
    9. 开始执行新的指令周期,继续执行原先的程序

  3. 中断很忙

    中断常常有很多,因此会出现以下状况

    1. 正在处理一个不是特别重要的中断,来了一个重要的
    2. 正在处理重要中断,来了个不是很重要的
    3. 同一时间来了许多中断,该处理哪一个?

    因此出现了 中断优先级 和 中断屏蔽, 对应操作有

    1. 转去执行更高级别的中断
    2. 忽略级别低的中断
    3. 优先执行级别高的,如果级别相同,则
      1. 同样重要的也依然按照一些方式排好优先级,比如按离CPU的远近来排序
      2. 轮转法,依次响应

    中断划分优先级主要看紧急程度和重要性,有时也随意划分.

    中断屏蔽主要靠设置PSW来决定该程序能够屏蔽哪些中断信号.
    有时 中断屏蔽 也起到临时调整优先级顺序的功能.
    比如一般来说 光盘事件 < 硬盘事件
    但正读盘时,希望先读完,于是暂时屏蔽硬盘事件,造成 光盘事件 > 硬盘事件 的效果.
    有些中断不可屏蔽

    • 机器故障
      • 掉电
      • 内存校验出错

系统调用

  1. 相关概念

    • 访管中断: 一种中断,是用户程序为了调用操作系统的功能,发出的事件通知.
    • 系统调用: 特权指令的处理过程,最多由汇编语言调用,编程人员只能使用高级语言封装出的接口.
      系统调用允许有深度限制的嵌套调用.具体有什么调用,因系统而异.
    • 广义指令: 系统调用的别称.因扩大了编程人员的操作权限.
    • 访管指令: 能够引起访管中断的指令

    系统调用的分类(按使用者)

    • 系统自身需要
    • 提供给编程人员

    系统调用的分类(按功能)

    • 进程控制类
      • 创建/终止进程
      • 获得/设置进程属性
    • 文件操作类
      • 创建/删除文件
      • 打开/关闭文件
      • 读/写文件
      • 改变文件属性
      • 创建/移动目录
    • 进程通信类
    • 设备管理类
      • 启动设备
      • 请求设备
      • 释放设备
    • 信息维护类
      • 获得当前时间日期
      • 设置文件访问/修改时间
      • 了解系统当前用户数
      • 了解操作系统版本号
      • 了解空闲内存
      • 了解磁盘空间大小

  2. 处理过程

    事前条件:

    • 操作系统中已经准备好处理的子程序,入口地址表

    处理过程

    • 用户调用API,发起系统调用(有一个事先给定的功能号,用于匹配处理程序,还可以有其他参数)
    • 系统调用引起访管中断
    • 保存现场
    • CPU切换到管态
    • 找到并执行对应的处理程序
    • 恢复现场
    • CPU切换到之前状态

    其中传递参数也有几种方法

    1. 系统调用指令中自带参数,指令长度有限所以参数长度也有限
    2. 使用通用寄存器传递参数,长度也比较短
    3. 专用堆栈,够大

IO技术

IO结构也和存储结构一样,对计算机系统有重要的意义.
为了能让处理器在CPU处理和IO处理之间跳来跳去,IO系统也需要做自己的努力.

  1. 一些概念

    • 设备控制器: 外部设备上安装的,用于控制外部设备的结构
    • IO硬件结构: 设备控制器和CPU之间的结构

  2. 早期

    CPU与硬件控制器之间只有IO电路,直连设备,需要轮询硬件状态

  3. 通道

    又称IO处理机,位于CPU和设备控制器之间,代替CPU对IO操作进行控制.
    通道也处理不同外部设备访问内存的竞争过程.
    最大优点是外部设备在通道的控制下能够访问内存,与CPU并行运行.

  4. DMA技术

    Direct Memory Access
    类似通道?
    存在一个独立控制单元DMA,
    CPU向DMA发出指令(IO设备的地址,目的内存地址,需要传输的数据长度,是读还是写)
    DMA处理完后发起中断提醒CPU

    缺点:总线占用,DMA利用总线传输数据,处理器也想使用只能先等等(比如一个总线周期)

  5. 缓冲技术

    外部设备中设置一个数据的存储区域,称为 缓冲区.
    比如键盘先把数据存在缓冲区,输入完成后,CPU再读到用户工作区.
    有时候一个缓冲区不够(挤满了之后要CPU取完才能继续放),需要多个.
    可以与通道技术一起使用.

时钟

用途很广

  • 发现陷入死循环的进程
  • 辅助时间片轮转法
  • 产生正确的时间间隔
    • 有些实时系统中的设备需要间隔的信号
    • 一些事件需要定时唤醒
  • 计时器功能
    • 记录某事件发生的时间
    • 记录时间发生的间隔时间

分类(按设备性质)

  • 硬件时钟
    • 晶体振荡器,有一个脉冲,就让时钟寄存器+1
  • 软件时钟
    • 硬件不够,软件来凑,在内存里模拟出一个寄存器,+1或-1

分类(按用途)

  • 绝对时钟
    • 很准确
    • 关机也在运行
  • 相对时钟/间隔时钟
    • 操作员设置初始值>0
    • 每过一段时间-1
    • 到0后触发一个中断
    • 软硬件都可以实现,不过软件居多,不然是对硬件时钟的浪费

进程线程模型

顺序执行优点

  1. 顺序性
  2. 封闭性(资源专有)
  3. 结果的确定性
  4. 结果的可再现性

并行执行的优点

  1. 系统效率高

并行执行的其他特点

  1. 各程序间逻辑上的独立型
  2. 随机性(输入和执行的时间是随机的)
  3. 资源共享性

进程

  1. 引入和概念

    为了描述程序的并发执行而引入.

    进程和程序
    联系:
    进程的运行目标是它对应的程序
    区别:
    程序是静态的(永远存在),进程是动态的(有生命周期)

    其他特点:
    进程能够创建其他进程,因而有父子进程,构成进程家族

  2. 各种模型

    模型包括, 状态 和 状态转换机制

    1. 三状态模型

      状态:

      • 运行
      • 就绪
      • 等待/阻塞/封锁

      操作:

      • 调用
      • 超时
      • 等待事件
      • 事件出现

    2. 五状态模型

      状态:

      • 创建(正在创建,还不能运行,建立进程控制块,建立资源表格,分配资源,建立地址空间表)
      • 就绪
      • 运行
      • 阻塞/等待
      • 结束/退出(回收除进程控制块之外的其他资源,并且让其他进程从进程控制块中读取信息,
        比如将退出码传递给父进程)

      操作:

      • 创建进程
      • 提交(考虑性能,内存,系统会限制进程总数)
      • 调度
      • 超时(时间片用完)
      • 释放(异常退出的原因很多,执行超时(死循环),内存不够,非法指令或地址,IO操作失败,被其他进程终止)
      • 事件等待
      • 事件出现

    3. 七状态模型

      引入了虚拟内存技术后,进一步添加了一些状态和转换.
      低优先级进程可能会被换至外存.
      优点

      1. 减少就绪进程的数量(有一部分成了就绪挂起),处理机效率有一定提高
      2. 内存不够的福音
      3. 挂起进程后,可直接读写其地址空间,方便调试

      新状态:

      • 就绪
      • 阻塞
      • 阻塞挂起:在外存等待
      • 就绪挂起:只要进入内存,即可运行

      新操作:

      • 挂起(从内存放到外存),可能原因
        • 该进程不是就绪状态
        • 其他进程要更多内存
        • 有一个更高优先级的进程即将就绪(即使是阻塞状态)
        • 有更高优先级的进程从阻塞挂起进入了就绪挂起,那么正在运行的低优先级进程可能被挂起
      • 激活(从外存到内存),可能原因
        • 没有就绪状态的其他进程(排队排到了)
        • 优先级很高,被系统发现在就绪挂起状态等待
      • 事件出现(分针对内存的时间和针对外存的事件)

  3. 组成

    • 程序
    • 数据,躯体
    • 进程控制块(PCB, Process Control Block),灵魂,要调度和管理进程,首先要让进程能够被区分,因此有了PCB
      • 调度信息,供调度使用
        • 进程名
        • 进程号
        • 地址信息
        • 优先级
        • 当前状态
        • 资源清单
        • 家族关系
        • 消息队列指针
        • 进程队列指针
        • 当前打开文件
      • 现场信息
        • 可能会被其他进程改变的寄存器(程序状态子,时钟,界地址)的内容
      • PCB的内容随系统不同而不同

  4. PCB组织方式

    调度时当然会有算法,但也需要从将PCB放入一个资源池,一个一个挑选,这就有了各种组织方式

    1. 线性方式

      所有PCB不分状态,全放在一个连续表(称PCB表)中
      优点: 结构简单
      缺点: 每次都要遍历整个表
      适用: 进程不多的系统

    2. 索引方式

      按照状态分组,不过不同的组里放的不是PCB,而是PCB的指针.

      • 就绪表
      • 阻塞表
      • 等等

      运行就不必用表了,只需要有一个指针指向正在运行的PCB即可.

      PCB本身则不限制,放在线性表中也行.

    3. 链接方式

      按照状态分组,而且排序.
      PCB的指针们放在一个链表实现的队列中.

      • 就绪队列
      • 等待队列
      • 等

      特点

      • 同一状态的队列可以有多个,比如用来对应不同的原因
      • 排队的原则看情况而定

      现在的系统可能用队列的方式比较多,整体调度示意图如下

  5. 控制方式:原语

    在状态之间转换,需要有效的控制.
    进程的控制方式是 原语 (原子性的,不可分割和中断的若干条指令).

    为实现不被打断:

    1. 只以 管态 运行
    2. 常驻内存(太常用了,可能地址都是固定的,方便找到)
    3. 过程中屏蔽其他中断

    原语操作与之前 五状态模型 中的操作类似

    • 创建原语(用于创建进程,下略)
      • 申请空闲PCB域
      • 分配资源,填写PCB信息
      • 置进程状态(就绪)
      • PCB指针插入就绪队列
    • 撤销原语,实质是撤销PCB
      • 找到PCB并从队列中消除
      • 撤销该进程的子孙进程
      • 释放被进程占用的资源
      • 消去PCB,PCB撤销后,进程就亡了
    • 阻塞原语
      • 发起中断,停止CPU执行
      • CPU状态保存入PCB(现场信息)
      • 置进程状态(阻塞)
      • PCB指针插入等待队列
    • 唤醒原语
      • 找到PCB
      • 置进程状态(就绪)
      • 从等待队列中撤出并放入就绪队列

  6. 创建子进程的fork

    • 申请空闲的区域用于存放proc结构(进程描述符),相当于申请PCB
    • 赋予pid,相当于填写PCB信息
    • 复制父进程地址空间
    • 获得子进程能继承的共享资源的指针(如当前打开文件,当前工作目录),还在填写PCB信息
    • 子进程就绪,加入调度队列
    • 向父进程返回子进程的pid,向子进程返回0

    父子进程共用同一套代码,且子进程从fork()处开始运行.
    为了区分父子进程,需要使用pid的值来区分

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    int main() {
      pid_t pid;
      int x = 1;

      pid = fork();
      /* 父进程fork后继续运行,这里的pid不为0 */
      /* 子进程虽然不从头运行,但这里判断时为0 */
      if (pid == 0) {
        printf("child: x=%d\n", ++x); /* 此处为1 */
        exit(0);
      }

      printf("parent: x=%d\n", --x); /* 父子进程中x互不影响,此处为0 */
      exit(0);
    }
    /* 结果
    prent: x=0   父进程会优先一些
    child: x=2
     */

    父子进程共用同一套代码的更多例子

    1
    2
    3
    4
    5
    6
    7
    int main() {
      fork();                       /* 父创建子1 */   /* 子1不会从头运行 */
      fork();                       /* 父创建子2 */   /* 子1创建孙1 */
      printf("hello!\n");
      exit(0);
    }
    /* 共4个hello */

线程

  1. 引入和概念

    背景:
    196x年代提出进程后,一直使用到198x年中期,
    此时出现了线程,能够进一步提高系统效率.

    提高方式:

    1. 减少进程创建,切换,撤销时的时间和空间开销.
    2. 轻量的切换允许更高的并发量

    指导思想:

    1. 资源分配的单位与调度单位分离
    2. 进程作资源分配的基本单位
    3. 线程作独立调度的基本单位

    成品线程特点

    1. 与其他线程共享进程的资源(内存地址空间,打开的文件等)
    2. 自己只拥有一点必不可少的资源:程序计数器,一组寄存器,栈
    3. 能够创建和撤销另一个线程
    4. 基本状态类似进程:就绪,等待,运行(沿用调度对象的特点)

  2. 组成

    1. 唯一标识符
    2. 线程描述表(记录线程执行的现场状态)
      1. 寄存器
      2. 栈

  3. 相比进程

    1. 创建花费更小(不需要分配资源)
    2. 切换花费更小(不需要保存和回复PCB中的现场信息,但依然需要保存自己的寄存器内容)
    3. 通信更快更方便(可以基于共享的内存来通信,而无需调用系统内核,不过这种方式在现代看来并不好管理)

  4. 分类

    用户级线程(协程?)
    只用在用户态中,创建,撤销,切换,不通过系统调用实现.
    内核无法感知用户级线程的存在.内核看到的只是单线程的进程.
    实现方式: 在用户态,每个进程一个线程表,记录程序计数器,堆栈指针,寄存器状态等信息.
    优点: 可能会比陷入内核的方式快一个量级.调度算法有更大DIY空间.
    缺点: 调度单位是进程,可能会因为系统的调度,暂停执行一个线程.
    linux就支持用户级线程.

    内核级线程
    线程的创建,切换,撤销由内核实现,线程控制块保存在内核中.
    实现方式: 在内核中,单独有一个与进程无关的线程表.
    优点: 一个线程失效,内核可以检查进程是否有其他线程可以执行
    缺点: 频繁的线程操作,开销不算小.
    典型系统是windows.

    混合实现
    将一些用户线程,分配到系统的线程上.
    甚至用户及线程和内核级线程可以彼此多对多复用.
    Solaris可以.现代的其他操作系统应该也是可以的.

  5. 线程的软件实现

    Pthread包包含一些函数,用来创建,结束,等待,切换线程等等.

    • pthread~create~
    • pthread~exit~
    • pthread~join~
    • pthread~yield~

调度算法

调度本身分层次,不同层次有不同主要任务

  • 高级调度(作业调度),将磁盘中后备状态的作业创建为进程(批处理系统中也可以有调度)
  • 中级调度,将swap中的就绪进程调入内存,或者反之
  • 低级调度(进程调度,处理机调度),决定就绪队列中哪个获得CPU.使用最频繁,算法也最复杂.

以下内容也以低级调度为主.

  1. 主要工作

    1. 算法挑选
    2. 将PCB中的信息(PSW,通用寄存器内容等)送入处理器的相应寄存器

  2. 调度发生时机

    不可抢占的CPU下

    • 进程运行完毕
    • 进程自己调用了阻塞原语,进入了等待
    • 时间片用完

    抢占式CPU下

    • 就绪队列中的进程,比运行中的进程优先级高

  3. 一些思想

    针对目的,有不同思想

    1. IO型进程,IO比较多,考虑到磁盘性能差,可以让CPU优先处理,然后让磁盘尽量保持忙碌.
    2. 交互式应用中,需要有抢占的机制以防止一个进程霸占CPU.

  4. 算法目标

    不同环境下应该有不同目标,但也会有共同目标

    1. 公平
    2. 所有部分尽可能忙碌

  5. 指标

    批处理系统:

    1. 吞吐量(每小时完成的作业数量)
    2. 周转时间(作业提交到作业执行完毕所花时间的统计平均值)
    3. CPU利用率

    交互式系统

    1. 最小响应时间,发出命令到得到响应之间的时间
    2. 用户喜好

    实时系统

    1. 要满足截止时间

  6. 各种算法

    1. 先来先服务(FCFS,First-Come First-Serverd),非抢占式,易于理解
    2. 最短作业优先(SJF,Shortest Job First),非抢占式
      利好 周转时间 指标,甚至在所有作业一同到达的情况下,最短作业优先是最优
    3. 最短剩余时间优先(SRTN,Shortest Remaining Time Next),抢占式,
      要求作业是可预测的,的确能方便短作业的运行.
    4. 轮转法(RR,Round-Robin),时间片长度很重要
      过短,切换频繁
      过长,和先进先出没有太大区别,交互请求无法快速得到响应.
      如果只能固定时间片,以前的CPU,20~50ms通常比较合理
      后来可以根据优先级,分配不同的时间片
    5. 最高优先级(HPF,Highest Priority First),是一种思想,可以是抢占式的,或非抢占式的
      优先级可以是动态的,可以是静态的.都会根据用户的需求和任务性质来确定.
      表述上可以是优先数,优先数小的,优先级高.
    6. 多级反馈队列,缝合怪,优先级+时间片
      按照优先级别分多个就绪队列,级别高的分较小的时间片
      同一个队列内,或是先进先出,或是RR
      不同队列间,总是优先高级别的
      重新排队:
      时间片用完,进入低一级
      从等待到就绪,进入同级
      被别人抢占,进入低一级
      或许高级用完,会让其他进入高级一部分吧
    7. 最短进程优先,交互式系统中,参照批处理系统中SJF想出来的一种方式.
      基于过去花费时间,预测将来的可能用时.
      为过去的时间取加权和,特别过去的就给小权重,偏向于遗忘旧的.称 老化

  7. 实时系统专用调度算法

    1. 速率单调调度(RMS,Rate Monotonic Scheduling),
      依赖一些场景: 进程有规律(非事件出发),周期性,稳定地(每次的CPU使用时间相同)发生.且没有Deadline.
      进程的优先级正比于(有时甚至是1比1)事件发生的频率
      每秒20次则优先级20,每秒50次则优先级50
      运行优先级最高的就绪进程
    2. 最早最终时限优先(EDF,Earliest Deadline First)
      比较符合一般的实时系统的目的,不能有过Deadline的.

进程间交互

多个进程,关系多种多样

  • 无关进程: 不影响其他进程,且不受其他进程的影响,各自独立,肯定没有共享的变量.
  • 相关进程: 依赖其他进程的进展,或者影响其他进程的结果.

相关的进程之间需要能够进行交流

  • 控制信息(短暂的信号交流以协调执行顺序或对资源的使用权利)
  • 内容信息(大段的信息交流)

控制信息的任务

  • 同步: 协调多个进程的处理顺序(因为以不同顺序执行会有不同结果)
  • 互斥: 控制对共享资源的访问(不进行控制会造成超卖等结果)

互斥与同步的关系:

  1. 可用互斥实现一定程度的同步,比如A占用资源时,B不能使用,B也使用资源时,可保证B一定在A后发生.

完成同步和互斥,有各种方法,也各有各的优缺点

  • 平等协商
    • 软件方法
    • 硬件方法(还是性能不好,也有平等协商的局限性)
  • 引入管理者角色
    • 信号量方法(不够整体,容易写错)
    • 管程

同步和互斥问题,有许多经典的问题模型

  • 生产者消费者
  • 读者写者

进程间通信,即大量交换信息,也有不同的方法

  • 共享内存(利用同步与互斥)
  • 消息机制
  • 共享文件(管道通信)

临界资源

共享资源(硬件或软件资源)

  • 临界资源(尤其在写入,操作时,需要互斥使用)
  • 只读资源

资源的共享程度

  • 互斥
  • 死锁
  • 饥饿

为了方便研究,抽象出一个过程

  • 进入区(用于检查是否可以进入,比如:检查标志)
  • 临界区
  • 退出区(比如: 清理标志)
  • 剩余区

预期目标

  • 空闲则入
  • 忙则等待
  • 有限等待(不能死等)
  • 让权等待(进程应进入阻塞状态不要浪费CPU)

实现资源的互斥访问

  1. 软件方法

    考虑两个进程想要使用同一个临界资源

    1. 单标志

      单独一个标志turn.
      进入区: turn等于自己的pid,则可进入,否则等待
      退出区: 将turn设置为另一个进程的pid

      优点: 任何时刻只有一个进程在临界区
      缺点: 只能交替操作

    2. 双标志,先检查

      两个标志,[flag1, flag2]分别表示进程P1,进程P2 是否在 临界区内
      进入区: 进程P1检查flag2,如果在使用则等待,如果没有,则设置flag1为true并进入
      退出区: 进程P1将flag1设置为false

      优点: 能够不限于顺序
      缺点: 假设在P2检查flag1后允许进入,但还没来得及设置flag2为true的瞬间,
      P1做了检查,发现也能进入.
      那么两个进程就能同时进入.
      本质上还是因为 检查 和 设置 不能一步完成

    3. 双标志,后检查

      两个标志,[flag1, flag2]分别表示进程P1,进程P2 是否想 进入临界区
      进入区: 进程P1先设置自己的flag1为true,而后如果flag2为false,则可进入,否则等待
      退出区: 进程P1将flag1设置为false

      优点: 能够不限于顺序.
      由于进程进入临界区后,对应flag不会改变,因此另一个进程不会判断flag为false而挤入
      缺点: 两进程都想进入临界区,发现对方也想进入,双方会无限等待下去,发生死锁

    4. 结合起来,先修改,后检查,后修改者等着

      三个标志
      [flag1, flag2]依然表示进程P1,P2 是否想 进入临界区,
      turn表示最后一个修改flag的进程pid.

      进入区:

      1. P1设置flag1为true,设置turn为p1
      2. 判断flag2 && turn == p2,为真则等待
        1. 如果flag2为false,则进入
        2. 如果flag2为true,但turn为p1,则进入
        3. flag2为true,且turn为p2,则等待

      退出区:
      P1修改flag1为false.

      优点: 暂时能用了
      缺点: 进程变成三个以上时,方法无法通用
      本质上依然是检查和设置值无法同时完成

  2. 硬件方法

    解决软件方法的短板,让一些操作有原子性.
    硬件方法的优点很明显:

    1. 操作简单
    2. 多进程,多处理器,多临界区,实现方式都比较统一

    缺点:

    1. 等待时会一直循环,浪费CPU
    2. 两个进程多次battle,有可能其中一个总是输,需要个管理者角色来调整

     

    1. TS指令

      Test and Set.
      读取标志的同时,将标志设为true.

      实现上更加简单.
      一个资源有一个标志lock,true表示正被占用,false表示空闲,初始值为false.

      1. 进程P1会检查并修改为true
      2. 退出时再修改为false.
      3. 进程P2检查到lock值为true时表示正被占用,则等待

    2. SWAP或Exchange指令

      用于交换两个字的内容.

      实现上与TS指令的方式有差异.
      标志上不变,一个资源有一个标志lock,true表示正被占用,false表示空闲,初始值为false.

      1. 进程P1保存自己的bool型变量key,进入前设置为true.
      2. 与lock交换并判断拿到的值(即key),为false,则进入
      3. 退出时将lock修改为false
      4. 进程P2检查到lock值为true时表示正被占用,则等待

      对于状态,TS指令直接读出来,而SWAP则是换出来.
      对于lock,TS直接设置为true,SWAP则先搞一个值为true的key,再换进去.

  3. 信号量方法/PV原语方法

    引入操作系统这个管理者.
    不仅判断进程能够访问资源,
    同时也控制进程的状态(等待,就绪).
    不要浪费CPU.

    荷兰学者Dijkstra于1965年提出.
    P为proberen(荷兰语,英语意为test)
    V为verhogen(荷兰语,英语意为increment)
    让PV原语执行期间不允许发生进程调度,即不被打断.

    机制上

    1. 用一个数字s.count,表示空闲资源数,初值不妨为1.
    2. 用一个队列s.queue,保存想访问资源的进程们
    3. 资源数大于0表示空闲,小于0则表示有n个进程在等着使用
    4. P操作:
      1. count -= 1
      2. 若 count < 0, 则加入等待队列
      3. 若 count >= 0, 则允许访问资源
    5. V操作:
      1. count += 1
      2. 若 count <= 0, 表示队列长度大于1, 从队列中拿出来一个,设置为就绪状态

    优点:

    1. 能够实现让权等待
    2. 有机会让总是输的进程排队获取平等待遇

    缺点:

    1. 如果遗漏了P或V,后果严重
    2. 如果PV颠倒,后果也严重

  4. 管程

    PV虽然需要成对,但不要求在一个进程内成对,这导致

    1. 程序可读性差
    2. 不好写新的,也不好改旧的
    3. 代码写多了不敢保证正确性

    于是提出管程

    管程组成:

    1. 名称
    2. 共享用的数据
    3. 操作数据用的过程
    4. 对共享数据赋初值的语句

    设定:
    进程能且只能通过调用管程,来达到目的:
    使用过程(管程内的),改变数据结构(管程内的)
    管程本身在被多个进程调用时只放一个进来.
    搭配类似 wait until a == true 这样的语句,让一个不能进入管程的进程阻塞.
    在一个进程离开管程时发出信号,比如 message.send(a=true), 让阻塞的进程转为就绪.

    效果:
    同时只有一个进程在修改管程内的共享数据.

    特点:

    1. 模块化,可以单独编译出来,供外部调用
    2. 全新的类型,包含数据,还有操作数据的代码
    3. 信息隐蔽,外界只知道管程实现了一部分功能,但不知道是如何实现的.
      注: 共享变量在管程外部不可见.防止外部依赖数据的值做不恰当的判断和行为.
      只允许调用了管程后得到结果.
    4. C语言暂时不支持

    优点:

    1. 写代码的人无需关心互斥是如何实现的,只需要知道如何将一个共享变量用管程包起来即可.
    2. 即使忘了 wait, 只有 signal 也无所谓

经典同步问题与解决

  1. 简单生产者-消费者问题

    生产者进程P可以向缓冲区放产品
    消费者进程Q可以从缓冲区拿产品
    缓冲区只能放一个

    包含了同步和互斥两个问题
    同步: 需要先放,才能再拿;容量有限时,需要先拿,才能继续放
    互斥: 暂不明显

    解决方案

    1. 信号量empty,表示空位数量,初值1
    2. 信号量full,表示满位数量,初值0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    /* 生产者 */
    while (true) {
        P(empty);                   // 空位减少
        // 生产产品
        // 送到缓冲区
        V(full);                    // 满位增加,若full为1,缓冲区已满,会一直等待消费者调用P(full)
    }

    /* 消费者 */
    while (true) {
        P(full);                      // 满位减少
        // 拿出产品
        V(empty);                     // 空位增加
        // 消费产品
    }

    如果只用一个信号量,可能会发现,生产者试图放产品,但缓冲区已满.反之类似.
    使用两个信号量,能够让两者各自等待一些时机的出现再执行动作.
    这样能保证P一定能放,Q一定能取.

  2. 多个生产者-消费者问题

    缓冲区容量扩大到k个,且位置有关(已经放过的格子中不能再放,并不忽略位置)

    同步: 空了不能取,满了不能放
    互斥: 同一时间,一个格子只能由P或Q单独操作.否则就会导致一个格子被放了许多产品.

    解决方案,基本不变

    1. 信号量empty表示空位数量,初值k
    2. 信号量full表示满位数量,初值0
    3. 信号量mutex,初值为1,用于表述临界区的互斥
    4. 另设置i,j两个指针,i指向空格,j指向满格.初值为0

    算法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    /* 生产者 */
    i = 0;
    while (true) {
        // 生产产品;
        P(empty);
        P(mutex);
        // 向buffer[i]中放产品
        i = (i + 1) mod k;
        V(mutex);
        V(full);
    }

    /* 消费者 */
    j = 0;
    while(true) {
        P(full);
        P(mutex);
        // 从buffer[j]中拿产品
        j = (j + 1) mod k;
        V(mutex);
        V(empty);
        // 消费产品;
    }

  3. 读者-写者问题

    一个能被多个进程操作的文件F.
    读者: 读文件的进程
    写者: 写文件的进程
    设定:

    1. 可以同时读
    2. 有人在写,不允许其他进程操作,读也不行
    3. 正在读时不允许写

    互斥: 写与写之间,写与读之间

    解决方案

    1. 计数器read~count~,表示正在读的进程数,初值0
    2. 信号量mutex,表示是否能修改read~count变量~,初值1
    3. 信号量write,表示是否能写文件,初值为1
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    /* 读者 */
    while(true){
        P(mutex);
        read_count += 1;
        if (read_count == 1) P(write); /* 第一个读者与写者的信号量write有互斥关系 */
        V(mutex);

        // 读文件

        P(mutex);
        read_count -= 1;
        if (read_count == 0) V(write); /* 第一个读者也是最后一个离开的,需要以V原语告知写者 */
        V(mutex);
    }

    /* 写者 */
    while(true){
        P(write);
        // 写文件
        V(write);
    }

    由于设定的关系,第一个读者比较紧要:

    1. 其他读者看到有第一个读者出现,也敢跟着读.
    2. 写者与第一个读者有互斥关系.

  4. 其他练习

  5. Pthread对互斥和同步的实现

    pthread~mutexinit~ 创建互斥量
    pthread~mutexlock~ 加锁,类似P原语?
    pthread~mutexunlock~ 释放锁,类似V原语?

    在pthread里,还需要手动管理进程/线程的阻塞状态
    pthread~condwait~ 阻塞以等待一个信号
    pthread~condsignal~ 向一个线程发送信号
    pthread~condbroadcast~ 广播信号

    多个生产者,消费者的问题

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    #include<stdio.h>
    #include<pthread.h>

    #define MAX 100

    pthread_mutex_t the_mutex;
    pthread_cond_t condc, condp;
    int buffer = 0;

    void* producer( void* ptr) {
      int i;
      for (i = 1; i <= MAX; i++) {
        pthread_mutex_lock(&the_mutex);   // 相当于P(mutex);
        while( buffer != 0) pthread_cond_wait(&condp, &the_mutex);
        buffer = i;                       // 生产第n个产品
        pthread_cond_signal(&condc);
        pthread_mutex_unlock(&the_mutex); // 相当于V(mutex)
      }
      pthread_exit(0);
    }

    void* consumer(void* ptr) {
      int i;
      for (i = 1; i <= MAX; i++) {
        pthread_mutex_lock(&the_mutex);   // 相当于P(mutex);
        while( buffer != 0) pthread_cond_wait(&condc, &the_mutex);
        buffer = 0;                       // 将第n个产品消费掉,变成0
        pthread_cond_signal(&condp);
        pthread_mutex_unlock(&the_mutex); // 相当于V(mutex)
      }
      pthread_exit(0);
    }

    // 声明两个线程
    pthread_t pro, con;
    // 初始化信号量
    pthread_mutex_init(&the_mutex, 0);
    // 初始化条件变量
    pthread_cond_init(&condc, 0);
    pthread_cond_init(&condp, 0);

    // 创建并运行线程
    pthread_create(&con, 0, consumer, 0);
    pthread_create(&pro, 0, producer, 0);

    // 在主线程内等待两个线程各自结束
    pthread_join(pro, 0);
    pthread_join(con, 0);

    // 资源清理,销毁条件变量与信号量
    pthread_cond_destroy(&condc);
    pthread_cond_destroy(&condp);
    pthread_mutex_destroy(&the_mutex);

进程间通信

  1. 共享内存

    设想:

    1. 在内存中设置一个公共区域
    2. 使用读写者的模式操作同步和互斥关系,维护稳定

    需要解决的问题

    1. 如何提供共享内存(操作系统可以提供)
    2. 如何同步和互斥(开发人员自行书写)

    这样看来go的多个协程间的通信是多么的方便,
    不需要加锁,不需要原语.

  2. 消息机制

    一种方法类似 生产者-消费者问题,
    A进程在内存中开辟公共消息缓冲区,写入信息,
    将缓冲区的地址以其他方式通知B进程
    B进程从缓冲区中读取信息后,
    将缓冲区还给系统.

    另一种方法是对上述方法的改进
    A给B发信息的单位不是一次,变成一箱(箱内可以包含多次信息)
    这就让A可以发多次,而B可以暂时不读.

  3. 管道

    首先出现在unix系统中,
    两个进程打开一个共享的文件,专门用于通信.

    1. 不需要在意何时发送何时接收
    2. 不需要在意发送多长,接收多长
    3. 发送时的顺序和接收时的顺序相同
    4. 数据量可以很大
    5. 基于文件系统,速度可能会慢

内存管理

管谁,目标,怎么管

计算机系统有完整的存储体系

  1. 高速缓存
  2. 内存
  3. 外存

高速的又小又贵,容量大的便宜却低速.

操作系统应当对体系中的存储单元做管理,不过这里只讲内存管理.
而内存中通常分为两部分

  1. 系统区,操作系统占据
  2. 用户区,用户程序使用

因此内存管理范围再次缩小到对用户使用的部分进行管理.

内存管理的目标有

  1. 充分共享内存硬件,为多道程序提供存储基础
  2. 尽可能方便用户使用
    1. 操作系统自动装入用户程序
    2. 用户不必考虑细节
  3. 系统能够解决溢出问题
  4. 程序在执行时的长度应能动态伸缩
  5. 速度要快
  6. 存储保护与安全
  7. 共享与通信
  8. 资源的使用情况应该及时了解
  9. 实现目的所花费代价应合理

内存管理面临的问题有

  1. 内存管理方法
    1. 分配和释放算法
      1. 比如用表来记录哪些是空闲的,哪些是已分配了的,分配和回收时改表
      2. 分配上也有静态和动态等做法
    2. 地址如何变换
      1. 分配给不同程序,必然面临地址转换问题
    3. 数据的保护和共享
      1. 不希望多个程序间互相干扰,因此需要保护
        1. 地址越界
        2. 权限问题
      2. 如果多个程序间希望通信,那么也需要共享
  2. 如何扩充
    1. 覆盖技术
    2. 交换技术
    3. 虚拟存储技术
      1. 内存和外存之间数据如何流动
    4. 其他技术

共同问题:地址转换

假设内存容量n,那么就有0,1,2,(n-1)等n个地址.称 绝对地址, 或物理地址.对应空间称 物理地址空间.
写好的程序每次都希望使用固定的一些地址,但现实中不大可能每次都分配到相同的.
办法是让程序使用虚拟的,中间再加一层转换.
程序使用的地址称 逻辑地址, 对应 逻辑地址空间.

将逻辑地址空间映射到物理地址空间,称 地址重定位 或 地址转换 或 地址映射.
方式主要有 静态 和 动态 两种

  1. 静态重定位

    装入程序时,即程序执行前,将程序的逻辑地址全部转换成绝对地址.之后不再转换.
    通常为了简单,加一个定值即可.

  2. 动态重定位

    程序执行的过程中,
    每一条指令都经过硬件的地址转换机构,将逻辑地址转成绝对地址.

    通常的方式:
    基址寄存器 + 地址转换线路
    同时基址寄存器只有一个,因此PCB中要保留基址寄存器中的数值,方便进程切换后的恢复工作.

    即使运行中被改变了存放区域,依然能正确执行.
    还称这样的系统,支持 程序浮动, 称这样的程序是 可浮动的.

内存管理方案概述

大概的方案有

  1. 单一分区管理
    (基本不管理)
    实现简单,什么的不用考虑
    内存利用率低
  2. 分区管理
    又有细分
    1. 固定分区
    2. 可变分区
      1. 思想
      2. 如何移动
      3. 如何实现
      4. 如何分配
      5. 如何回收
      6. 如何保护
      7. 优缺点
  3. 页式管理
    1. 基本思想
    2. 分配与回收
    3. 如何转换以及如何提高效率
  4. 段式管理
    1. 物理段
    2. 与可变分区方案的比较
  5. 段页式管理
    1. 介绍

不同的方案都需要解决一些问题

  1. 如何分配和回收
  2. 如何更充分地使用
  3. 如何提高效率(地址转换的效率,分配的效率等)

连续区管理

一段时间内,只有一个用户进程在内存.
每次都能装入到固定地址.物理地址的计算可以选择在编译,链接,装入,执行的任意阶段
不必记录使用情况.

特点:

  1. 简单
  2. 开销小
  3. 内存利用率低
  4. 缺乏灵活性

分区存储方案

把内存划分成若干个连续区域,称为分区,每个分区装一个程序.

  1. 固定分区

    有比较早期的固定分区方案:

    1. 开机就把内存划分成若干个固定的区域.

    2. 为照顾不同程序的不同需求,区域大小可以不同.

    3. 管理使用情况时,使用一张表,结构类似

      区号 大小 起始地址 状态
      1 8K 16K 占用
      2 16K 24K 空闲

    4. 程序申请时提供最大使用量,
      系统查找空闲的,符合要求的区域,并分配给程序.
      程序允许完后通知系统收回.

    缺点:

    1. 依然不够灵活,程序的大小被限制
    2. 依然不能充分利用

  2. 可变分区

    于是有改进的可变分区方案:

    1. 不预先划分
    2. 应用想用时自己申请
    3. 应用结束后空出来,如果两个相连的区域都空闲,则合并
    4. 会产生不连续的碎片(每一个碎片都比新作业小,但合并后就比新作业大),用移动技术处理

    优点:

    1. 相比固定分区要灵活

    缺点:

    1. 还是有难以解决的碎片问题,毕竟需要各种移动碎片,浪费处理能力.
    2. 分配的是内存,无法继续扩充.
    3. 程序一开始就需要声明最大使用量,但如果程序的需求是动态的,程序自己也不好判断.

  3. 可变分区的实现

    基址寄存器: 存放起始地址
    限长寄存器: 存放程序所占分区的长度

    逻辑地址 小于 限长寄存器,
    则 绝对地址 等于 基址寄存器 加 逻辑地址
    否则 越界中断

    已分配分区表: pid,起始地址,长度
    空闲分区表: 空闲标志,起始地址,长度
    个人认为同样的数据结构,完全应该组合成同一张表,操作起来也方便.

    有了表,就应该有什么时候,如何查找和修改表中条目的问题,即分配和回收算法

  4. 分配算法

    • 最先适应算法(顺序分配法)
      顺序查找分区标,找到的第一个满足申请长度的空闲区,将其分割并分配.
      找不到则等待资源.
    • 最优适应算法
      找到能满足需求的 最小 空闲区.
      优点是节约空间,
      缺点是会形成很多碎片
    • 最坏适应算法
      找到满足需求的 最大 空闲区
      优点是碎片较少
      缺点是遇到较大的程序可能装不下
    • 下次适应算法
      保留查找的进度,下次查找时从本次分配的位置开始查找

  5. 回收算法

    先将相邻的空闲区合并.
    过程中,一个空闲区域有上/下,两个相邻区域,
    上下各自有空闲/占用两个状态.于是有四种情况.分别考虑即可.
    不过上下临分区没有那么好判断,需要不断遍历表并计算表中的start+length.
    可能需要一些其他算法来降低复杂度.

  6. 移动技术

    可变分区使用过一段时间后,内存中就会产生许多不连续的空闲区域,没法直接利用,称为碎片.
    应对方式上,需要碎片整理.
    技术上称为 移动技术, 紧凑技术, 紧缩技术

    问题有

    1. 适当的时刻
      1. 太频繁增大系统负担(修改进程控制块,修改内存分配表)
      2. 太稀少导致新作业无法及时开始
      3. 进程与外设交流时,不能移动位置,否则外设汇报信息位置出错
    2. 适当的移动方法,A靠近B,还是B靠近A
      1. 减少移动的作业数
      2. 减少移动的信息量(移动较小的那个)

页式管理

分区管理中,造成碎片的原因是程序必须使用连续的区域.
如果分散到不连续的区域中,需要解决不连续时的使用问题,但 移动, 碎片 就可以不再考虑.
需要硬件支持, MMU, Memory Management Unit. 存储管理部件.

大概方式

  1. 硬件内存分成许多大小相等的区域,称为 块
  2. 逻辑地址也相应划分成大小一致的区域,称为 页
  3. 真正使用时,一页占一块.
  4. 用一个二维数组模拟这些块的集合,同时记录哪些块已经分配,哪些空闲,当前还有多少空闲的块.
    1. 称内存分配表.
    2. 有多个行,每行的列数相同,用 行数*一行的列数+当前块的列数 表示当前块的块号
    3. 比如用0表示空闲,用1表示占用
    4. 表示空闲块总数的数据,可以放在最后一行的第一列
  5. 程序内部使用 页号+页内地址 来定位逻辑地址.
    1. 不过依然可以像连续地址一样使用,比如一个地址 yyyynnnn, 用 yyyy 表示页号, nnnn 表示页内地址.
    2. 这要求页号是连续的.
  6. 分配给程序前,查看一下空间的所有块够不够程序的需求.够则分配,不够则等待资源.
  7. 程序会得到一个记录页的 页表 (页号 映射到 块号)
  8. 程序结束后,按照块号找到分配表中的位置,并标记为空闲

地址转换的硬件支持

  1. 要单独为页表申请一块连续的区域,将开始地址和长度存入PCB.
    (由于页的数量不一定,因此页表的长度也不一定)
  2. 进程运行时,硬件上有
    1. 页表起始地址寄存器
    2. 页表长度寄存器(指定页号超出时,要给出中断)

页表的改进

  1. 多级页表
    想要灵活,页要足够小,比如4kb,但这样导致页数太多,页表太大,页表本身就需要很大空间
    于是采用多级页表,保存页表所在地址的称 页表页
  2. 散列页表
    64位计算机中,如果一个页4k,就算用二级页表,还是很大,
    如果用二级以上页表,则查到最终物理地址要访问内存多次,时间上太慢.
    于是用散列值来映射页号与块号,如果散列的结果相同,则以链表保存.不过这种概率不大.
    通常就计算一次来得到物理地址,特殊情况下沿着链表找找就行,不怕找不到.
  3. 反置页表
    既然有了二级页表,那么最底层的页表就不必要完全有序了,可以和块保持同一顺序
    不过缺点也是有的,每次计算物理地址都需要花费比较多的时间,不能忍
  4. 快表
    页表保存在内存中,为了找到物理地址,第一次读页表页,第二次读页.查找空间大但效率低.
    可以让页表或者页表的一部分,保存在CPU的高速缓存中.让原本2倍的时间,变得接近1.1倍,还挺好的.

段式管理

  1. 把物理内存划分成 大小不等 的 物理段,起始地址称 段首址, 段内有 段内地址
  2. 程序使用的是 大小不等 的 逻辑段, 简称 段,每个部分(主程序,子程序)可以占据一个段.
  3. 程序所用的段靠编号,称 段号,段内也有 段内地址
  4. 分配时一个物理段对应一个逻辑段,逻辑段连续而物理段可以不连续
  5. 系统可以为程序提供段表用于记录逻辑段和物理段的对应关系(逻辑段号-物理段基址-物理段长度)
  6. 地址的转换上,可以借助硬件(一对寄存器),也可以使用类似快表的技术来加速

相对于可变分区方案,内存空间中的区域可以分配给程序的一部分而不是程序的整体.

段页式管理

块式管理碎片少,
段式管理使用方便(没看出来比页表方便在哪儿).
于是结合特点出现了段页式管理.
程序仍然以段为单位划分,但物理内存以块为单位划分,
分配时,每个逻辑段都有自己的页表.
这样程序就有了段表和页表.
看起来和二级页表区别不是很大.

内存的扩展

将一部分数据存到外存中.以扩充有限的内存空间.

  1. 覆盖技术

    早期的系统使用.

    程序一部分装在内存,一部分装在外存.需要的时候调入内存.
    内存中有一个区域专门用于让外存的部分装进来.
    这个区域在进程结束前都归这个进程所有,该进程需要自己覆盖自己.

    优点:

    1. 初步实现不需要全部装入内存才能用的模式
    2. 不需要操作系统的支持,可以在用户级别解决
      1. 手动划分成几个部分,每个部分依次都是 外存 -> 内存, 定好顺序和覆盖方式即可.
      2. 或者专门写一个编译器,让写代码时候省事一些

    缺点:

    1. 用户依然需要自己实现,比较麻烦.
    2. 用户最好只管好自己,不要乱覆盖别人的区域.
    3. 程序切分的单位依然受到硬件的制约.
      内存太小时,就得把程序切得更小一些,但有时候又不能再切得更小.

  2. 交换技术

    也称对换技术,小型分时系统可以使用.

    需要操作系统支持,将处于一些特定状态的进程,整体或一部分,调到外存的swap区域.
    需要的时候换进来.

    面临的问题有

    1. 将内存中进程换到swap时,换哪个(一般是让阻塞队列中优先级最低的那个先出去,或者系统评估后认为不会马上就被使用)
    2. 什么时候交换
      1. 内存完全足够显然不需要换出去
      2. 怎样定义内存快不够了是个问题
      3. 换回来也需要看时机,当CPU空闲时,就绪状态的进程最好要在内存,而不是swap中.
    3. swap那么大,一段程序具体放在什么位置,碎片问题怎样解决.(好在和内存问题相似,也能解决)
      1. 固定进程每次换出去时的位置
      2. 动态决定进程每次换出去时的位置
    4. 换回到内存时的位置(是否一定要是原来的位置?PCB中的基址寄存器的值如何处理)
    5. 复制大量内存数据的CPU时间
      1. 也类似DOM的问题,可以在swap中保存副本,差分修改
        1. 注意差分修改的方式仅限于代码没有在运行时被改动
        2. 如果代码改动,即使外存内容没有任何修改,拿回来也可能会造成错误

    优点:

    1. 有了系统支持,用户无需关心具体实现方式.也能让不同进程之间互相覆盖.
    2. 交换也只是一种思想,后续催生了 虚拟存储技术

  3. 虚拟内存技术

    虚拟内存技术中最为知名的是 虚拟页式存储管理方案

    本质上是 交换技术+页式管理技术
    交换技术中,被移动和置换的是整个进程.
    页式管理技术出现后,被移动的单位成了页.

    因此能够支持更细化的操作,即使程序比内存大,只要不比内存+虚拟内存大,就还能跑起来.

    相对于仅仅管理内存,在需要同时管理外存的情况下,需要对现有方案做修改.

    页表需要加入其他的信息才能被管理

    1. 原先的内容
      1. 页号
      2. 页框号(块号)
      3. 修改flag(用于差分对比与虚拟内存中有无修改,减少数据复制的量)
    2. 访问位(用于标记是否被访问过,可以是flag,可以是数字)
      (是否放入快表,是否将该页换出到外存等行为都可以使用),也称引用位,参考位
    3. 有效flag(表示该页是否在内存),也称驻留位,存在位,中断位
    4. 保护flag(是否能读/写/执行)
    5. 禁止缓存flag(当CPU与外设交互时,不允许内容移动到外存)

    需要一个新的中断,这样对于程序来说就,整个处理过程就是透明的.
    缺页中断: CPU要使用一个页,但查询页表后发现有效flag为0(不在内存中),发起一个中断
    中断处理:

    1. 如果在空闲的块,直接将页从外存调到内存
    2. 如果没有空闲的块,则选另外一个页,调入外存腾出地方
      1. 如果修改flag为0,说明没修改过,那更好
      2. 否则就写磁盘
    3. 修改页表,内存分配表等
    4. 恢复现场,程序继续执行

    页面需要被调度(何时何处等问题),良好的调度能够避免抖动问题
    抖动/颠簸: 常见于内存不足,需要将一页内容调到外存,
    但这页内容刚出去就又被需要,又重新调回来.
    不幸的是再次被选中调出.
    如此反复横跳,极大消耗时间,表面看起来就是处理速度变慢.

    调度策略分三个方面

    1. 调入策略,何时从外存调到内存中
      1. 请求调页,请求到时才放入内存中,可能导致需要的调用次数很多,产正抖动现象
      2. 预调页,请求时一次调入该页和相邻的一些页,可能减少IO次数,当然也可能造成浪费
    2. 置页策略,从外存中调入后,放在什么地址
      1. 应尽量让快表内容不发生过大变化
    3. 置换策略,即将哪一页从内存中移出
      1. 进程移动自己的页,进程需要外存的某一页时,只能将自己在内存中的某一页换出去.
        进程占有的块数保持不变.称 固定分配.
        只在进程自己的范围内替换,称 局部置换
      2. 系统安排,拆东补西.系统有空闲块时,就分配给应用.
        若没有则任意取一块(可能来自该应用,也可能来自其他应用)给应用.
        应用占有的块数可以变,称 动态分配
        块能够在整个系统的不同应用间流动,称 全局置换
      3. 进程优先自行解决,缺页中断率太高则求助系统多分配块,知道缺页中断率降低到合适范围.
        称 可变分配,局部置换

    策略解决移动谁的(应用自己的,还是其他应用的),但不解决谁先谁后的问题,还是不好解决抖动.因此需要置换算法.

    优化目标: 缺页中断率. 在A词访问页面中,有F此发生了缺页中断. f=F/Af=F/A
    影响因素

    1. 分配的块数
      如果块数无穷大,当然不需要缺页中断.
      极限情况下每个应用只分配一个内存块,依靠虚拟内存的确能运行,不过效率低下.
      通常内存有限时,经验得出,分配总需求块数的一半比较好.
    2. 页面的大小
      如果页很大,程序所需都在一个页中,自然也不需要缺页中断.
      不同的系统提供不同的页大小,甚至页大小可以改变.
      不过通常页大小处于 292^9 到 2142^14 字节之间.
    3. 代码的写法.
      如果内存只能放得下数组的一行,那么如果以列遍历数组,
      则导致每次都要重新读取新的页面到内存.
      如果以行遍历则没有问题
    4. 页面置换算法

    置换算法有:

    1. 理想算法(OPT)
      即马后炮,运行完了再评估如果能xx,则缺页中断率最低
      理想,但无法实现,只用用作比对标准,评估其他算法如何.
    2. 先进先出(FIFO, First-In First-Out)
      装入内存的页排队,队首的换对外存.
      优点:简单,缺点:常用的页可能被换了出去.需要考虑使用频率.
      缺页中断率大概是理想的3倍
    3. 最近最少使用(LRU, Least Recently Used)
      最长时间未被使用的页被替换.
      需要在页的信息中加上距离上次访问的计时器来实现,
      遍历一次页表选出最长的那个,同时还把所有页表的计时器清零(感觉一次循环做不到)
      缺点:实现起来消耗大
    4. 最近最不常用(LFU, Least Frequently Used)
      最不常使用的页被替换.
      需要在页的信息中加上被访问的次数,访问一次就加一,
      不想数字太大,则定义一个周期T,如果周期内没有发生缺页中断,则所有计数器归零.
      缺点:同样需要遍历加一,同样消耗大.
    5. 最近未使用(NRU, Not Recently Used)
      页增加Read,Modify两个标志位.
      针对Read,Modify两个标志位总共4中不同状况,采取不同策略.
      0类,R0,M0
      1类,R0,M1,因R位常常因为T周期内没有中断而被清零
      2类,R1,M0
      3类,R1,M1
      在一定时间范围内,比如20ms,随即选择一个级别低的(比如0类)置换出去.
      性能虽然不是最好,但足够.
    6. 第二次机会
      FIFO的变形,队首的如果R为0,又老又没用,则置换.
      队首如果R为1,则R清零并放入队尾,类似重新开始.
      如果一个队列全是1,且最近全部不会有Read发生,则原先的队首会在第二次成为队首时淘汰.
      当然此时也退化成FIFO算法.
      比较合理,但如果队列是用链表实现的,移动元素不是很方便.
    7. 时钟
      第二次机会的改版,不用直链表,用环形链表.
      不用队首,用检查指针
      由于环形队列形似时钟而得名.

    解决抖动还有一个方法:工作集模型
    t−δt-\delta 到 tt 时刻之间访问的所有页面的集合,称为 工作集
    δ\delta 称为 工作集窗口
    通常一个应用分配的物理块太少,缺页中断一定很多.
    存在一个临界值.超过后,即便分配块,缺页中断的下降也不明显了.
    通常这个临界值就是工作集中页面的数量.
    操作系统可以为每个进程保持一个工作集,并分配相同数量的块.
    工作集随时间变化,因此分配到的块数也能动态调整.

文件管理

重要性

  1. 操作系统的功能都可以看作文件的管理: 数据存储(文件存储),数据处理(文件处理),数据管理(文件管理)
  2. 文件系统,是操作系统的重要子系统

对信息存储的要求

  1. 容量要大
  2. 保存时间要长
  3. 能方便共享

早期打孔方式,三个要求都不能满足
磁盘,磁带等的出现提供了物质基础,才导致了文件系统的出现

文件

带标识的(比如文件名),逻辑上有完整意义的,信息项的序列.

  1. 有的系统比如MS-DOS只支持8个字符作为文件名,还定死要有点和3个字符的扩展名
  2. 文件的具体意义由建立者和使用者解释.windows还定死了扩展名的具体含义
  3. 信息项通常是基本单位,读指针指到当前,下一个,下一个.

文件是一个抽象概念,它需要提供一种方法让信息保存在介质上的同时,用户还不需要关心细节.

文件分类

  1. 按用途
    1. 系统文件,只能通过系统调用来访问(仅限执行),
    2. 库函数文件,只读,不允许修改
    3. 用户文件,所有者和被授权者都能按权限使用,各种源程序等
  2. 按组织形式
    1. 普通文件
    2. 目录文件(文件的目录也是信息,也需要以文件的形式保存)
    3. 特殊文件(比如linux系统看设备就是文件)
  3. 按组织角色
    1. 逻辑文件(用户看来的组织)
      1. 流式文件
      2. 记录式文件
    2. 物理文件(在介质上的组织)
      1. 顺序文件
      2. 链接文件
      3. 索引文件
  4. 按保护方式
    1. 只读文件
    2. 读写文件
    3. 可执行文件
    4. 无保护文件
  5. 按信息的流向
    1. 输入文件
    2. 输出文件
    3. 输入输出文件
  6. 按存放时限
    1. 临时文件
    2. 永久文件
    3. 档案文件
  7. 按介质
    1. 磁盘文件
    2. 磁带文件
    3. 等等

文件系统

操作系统中管理信息资源的一种软件.
通常需要提供的功能有

  1. 系统角度
    1. 存储,管理存储空间,实施分配与回收
    2. 检索,统一文件名与物理地址空间的映射,能够让用户按名存取
    3. 更新,为用户提供方便的读写修改等接口
    4. 共享,让不同用户,或让不同进程读取
    5. 保护
    6. 维护及向用户提供有关信息,比如使用了多少空间等等
  2. 用户角度
    1. 新建
    2. 读
    3. 写
    4. 修改
    5. 复制
    6. 删除

实现一个文件系统需要考虑的问题有

  1. 以什么样的数据结构来管理
  2. 该数据结构下,如何分配与回收资源
  3. 小文件希望做一些特殊对待防止资源浪费
  4. 如何共享文件,同时又如何保护
  5. 如何优化性能

好在管理内存问题时已经有大量的经验可以参考,甚至磁盘容量巨大,许多方案还有妥协余地.

FCB

File Control Block,文件控制块.
系统为管理文件的方便,为每个文件准备一个数据结构.
让用户按文件名就找到文件而不必了解具体物理地址.

几乎包含了管理文件所需的所有信息

  1. 文件名
  2. 文件号(内部id)
  3. 用户名
  4. 文件物理位置
  5. 文件长度
  6. 记录大小
  7. 文件类型,使用意义方面
  8. 文件属性,权限方面
  9. 共享说明
  10. 文件逻辑结构
  11. 文件物理结构
  12. 建立时间
  13. 最后访问时间
  14. 最后修改时间
  15. 口令(输入口令才能访问文件,但硬盘上没有做加密)
  16. 保存期限

目录

FCB的有序集合,构成文件目录.
文件目录本身也是文件,记录式的文件.

  1. 目录的结构

    1. 一级目录

      全系统就一个表,包含(文件名,FCB,文件地址指针)
      该表放在存储设备的固定位置,系统启动后就读入内存.
      然后增删改查
      添加文件: 申请一行的空间,存入新文件的信息
      删除文件: 删除一行
      更新文件: 更新一行
      查找文件: 遍历并查找表,要么找到,要么找不到就报错

      优点:

      1. 简单,容易实现

      缺点:

      1. 无法让不同用户创建相同名称的文件
      2. 检索文件需要遍历查找,耗时长

    2. 二级目录结构

      第一级: 主文件目录(Main File Directory),包含(用户名,子目录指针)
      第二级: 用户文件目录(User File Directory),包含(文件名,FCB,地址指针)

      优点:

      1. 解决了不同用户新建文件不能重名的问题
      2. 降低了查找时间
      3. 能够解决文件共享的问题,只需要在多个用户下创建一个指向被共享文件的指针即可

      缺点:

      1. 系统开销稍大

    3. 树形目录

      推广二级目录得来,也算是多级目录.
      页节点指向文件而其他节点全指向目录.
      路径上的全部分支组成一个全路径名.

      优点:

      1. 层次清楚
      2. 查找速度比二级目录再快一些

      缺点:

      1. 若每个目录都放在硬盘,查找一个文件则需要多次访问硬盘,影响速度
        1. 目录项分解法,
          假设一个块只能放4个文件项(文件名体积占10%,FCB90%),共10个块
          分解前平均查找次数(最好只找1个块就能找到+最坏需要找完所有10个块)/2=5.5次
          现分解目录的存储方式,全40个文件项中的文件名,总共占1块,剩余FCB占9块
          分解后平均查找次数:
          单查找文件名,最好最坏都是上面的1块 +
          找到文件名后再计算出对应的FCB所在块,读取这1块并最找找到文件 = 2次
      2. 每次指定一个全路径访问文件,比较麻烦
        1. 可以引入 当前目录, 相对路径 概念以解决.

      对于目录的操作

      • create
      • delete
      • opendir
      • closedir
      • readdir
      • rename
      • link
      • unlink

FD

文件描述符
linux系统一切皆文件,当打开一个文件时,内核返回一个非负整数,作为指向被打开的文件的指针,
该整数称 文件描述符.

  1. 每个fd对应一个打开的文件
  2. 不同的fd可能对应相同的文件

进程拥有fd表,使用fd找到文件指针
文件指针指向系统级打开文件表,从而找到I节点指针
利用I节点指针找到具体的文件位置

文件的存取

文件是信息项的序列.对序列的访问方式不同,造就了不同的存取方式

  • 顺序存取
    依次访问文件的信息项
  • 随机存取
    按照任意次序,直接存取任意一个信息项

具体能以什么样的方式存取,
主要受到存储介质,文件的物理结构,甚至文件的逻辑结构的制约.

存储介质

一般特点

  1. 容量大
  2. 速度慢
  3. 成本低
  4. 断电后还能保存

硬件上通常包括

  1. 介质(比如光盘的盘),也可以 卷 称呼, 更好地表达作为信息容器的比喻.
  2. 驱动(比如光驱)

通常会为介质的物理块编号,讨论物理结构时使用.
而且由于磁盘的使用最为广泛,通常会优先讨论一个物理结构,在磁盘上会如何.

  1. 磁盘

    盘面,磁道,扇区.
    柱面,则是不同盘的相同磁道.

    通常让每个扇区作为一个物理块.

    访问磁盘的时间

    1. 寻道时间(最长)
    2. 旋转定位时间
    3. 数据传输时间

  2. 磁带

    只能顺序存取
    结构简单,耗电低,价格低廉
    介质稳定
    用于保存一些档案

文件的结构

  1. 逻辑结构

    设计原则

    1. 易于操作
    2. 查找快捷(时间尽可能短)
    3. 修改方便(使磁层的存储变动尽可能少)
    4. 空间紧凑(管理用的部分尽量少占用,不要有浪费等)

     

    1. 流式文件

      基于字符,不需要复杂结构.也可称 无结构字符流文件
      基本单位是字符,有开头,有结尾
      操作方便.
      若查找,则复杂度O(N)
      代码等都是流式文件结构.

    2. 记录式文件

      基本单位是记录,记录中包含(键,属性,值)
      可按键查找.
      目录文件就是记录式的.

      1. 定长记录文件
        方便计算记录的逻辑地址,知道记录号i与记录长度L即可
      2. 不定长记录树
        由于不定长,且为树状,查找时可能需要遍历一些节点

  2. 物理结构

    1. 顺序结构

      也称 连续结构
      文件的信息存放在连续编号的物理块中.
      优点:

      1. 知道了起始块号与长度,逻辑地址与物理地址变换简单
      2. 寻道次数和寻道时间最少.

      缺点:

      1. 不能动态增长(想增长时块已经被占用了,指定最大大小则一方便不好指定,另一方面造成浪费)
      2. 为新文件分配存储空间不容易,总是需要找到连续n个空闲的块.
      3. 随着文件的新增和删除,会出现许多磁盘碎片

    2. 链接结构

      使用链表,每一块中保存下一块的地址.
      FCB中保存首指针即可.

      代价: 用于指向下一个块的指针稍占空间,通常是0.x%的级别,完全可以忍受.

      优点: 不连续存放

      1. 有利于动态扩充
      2. 碎片少利用率高
      3. 为新文件分配块更方便.

      缺点:(恰巧windows的FAT文件系统就是这样的结构,可见系统多么烂)

      1. 因必须要遍历链表,只能顺序读写,速度慢
      2. 寻道次数多,时间长,效率低
      3. 可靠性难以言表,一个块损坏,整个文件找不到了
        1. 使用双向链表来提高可靠性,但空间利用率降低,处理速度也变慢
        2. 每个块都存储文件名和文件内相对块号,浪费空间,悲剧情况下还需要遍历所有块来找到一个文件.

    3. 索引结构

      把所有块的地址都放在一个 索引表 中.FCB中保存索引表的指针.
      索引表的第i个条目指向文件的第i块.访问第i块,找第i个指针即可.

      对于大文件,索引表可能一个块放不下.于是需要考虑索引表所在块的物理结构

      1. 连续结构不适合,不利于动态增加
      2. 链表结构不适合,稳定性短板
      3. 也用索引结构,构成多级索引算是理想方案.一般二级足够.

      代价: 同样是指针需要占已经空间,大文件情景下通常可以忍受

      优点:

      1. 不连续存放的所有优点
      2. 指针是集中存放的,因此能够随机存取.

      缺点:

      1. 不连续存放的缺点之寻道次数和时间.
      2. 为找某文件的某块,
        先找一级索引(访问磁盘一次),
        再找二级索引(访问磁盘两次),
        最终找到文件所在块(访问磁盘3次),
        存取速度慢
        1. 索引表读到内存,能够加速查找文件块,但耗一些内存空间
        2. 索引表一部分0级指针,一部分1级指针,这样至少打开文件的首行会快些
      3. 小文件有可能还没索引表大,有点浪费

    4. I节点(优化的索引结构)

      文件使用的索引表改名为 I节点

      1. I节点定长,可记录15个指针
      2. 前12个直接链接到文件的块,称 直接盘块
      3. 后3个指向下级I节点,称 间接盘块
        1. 第13个指向 一重间接盘块
        2. 第14个指向 二重间接盘块
        3. 第15个指向 三重间接盘块
        4. 或许以后出现超大文件,可以有第16个指针?

      优点:

      1. 小文件也有不错的空间利用率,灵活性强

文件目录

文件控制块FCB的内容和信息
管理方式有不同

  1. 一级目录结构
  2. 二级目录结构
  3. 树形结构

目录相关操作

  1. 当前目录
  2. 目录检索
  3. 创建
  4. 删除
  5. 链接等等

存储空间的分配与回收

基础认识: 以块为单位分配与回收.
如何登记管理,有4中方案

  1. 位示图

    一个布尔型二维矩阵,
    以行表示磁道,列表示该磁道上的扇区.
    空闲为0,占有为1.

    分配块时将对应元素置1,释放块时将对应元素置0,
    优点:

    1. 描述能力强
    2. 地址计算很方便.因此使用起来容易.
    3. 占空间小,能够放在内存中做大规模的查找.
    4. 由于经过抽象,查找n个连续的空闲块变得相对容易.

  2. 空闲块表

    类似内存的分区管理.一个表有如下列
    序号,首空闲块号,空闲块个数

    建立新文件时可尝试优先分配连续的块.
    当有两个相邻的空闲区域时则合并成一个大的区域.

  3. 空闲块链表

    每个空闲块中放一个指针,指向下一个空闲块.
    而第一个空闲块则由一个特殊的指针(也不知道存在哪儿好)指示.

    虽然省内存,但效率低,稳定性差,还占位置.仅仅存在于理论中.

  4. 成组链接

    对链表的一种改进.
    每1块里都有指针指向一个块,改为
    n个块为一组,每一组的第一个块中,集中放置着一堆指针,指向下一组的每个块.
    最初的一个组的指针们,放在一个特殊的块,称 专用块 中.
    该块放在哪里不知道,但登记时一定先读到内存中.

    分配: 专用块中减少一个指针(从后向前,保证保存指针的那一块最后才被分配)
    若已经是最后一个,则读出被指向的那一组的第一个块,作为专用块的内容.然后将该块分配.
    若遇到一个组,还剩两个指针时发现即将读的指针指向块号0,说明是最后一个组.已分配完.
    回收: 专用块中增加一个指针,
    若已满,将专用块内的所有指针,放在归还的块中.后将该块的指针,替换掉专用块中的指针们.

表目

文件不仅仅像内存一样存储在介质上,还多出来打开与关闭的状态.
为了管理这些状态,在内存里保存一些打开文件的信息,
信息聚在一起,称为 表目,
有多种表目.

  1. 系统打开文件表
    (FCB,文件号,共享计数,修改标志)等
  2. 用户打开文件表
    (文件描述符,打开方式,读写指针,系统打开文件表条目指针)
    多个用户共享同一个文件的方式,可以是让指针指向 系统打开文件表 的同一行.

记录的成组与分解

小文件大小不足一块,如果单独放一块则

  1. 浪费空间
  2. 查找效率不高

考虑到最终使用时能够先放到内存中,因此只要缩小存放的范围,减少寻道即可.即 挤 在一个块中.
放入的过程称 记录的成组.
取出其中一个的过程称 记录的分解

代价方面仅仅是添加了一个不大的缓冲区.能接受.

  1. 成组

    将每个文件的内容拿到,称为 记录,统一放在内存的缓冲区中,而后将缓冲区写到块上.
    每个记录的形式可以是

    1. 定长
    2. 不定长,则需要在记录里对长度进行说明,方便分解时切割内容

    一个块上所放不同文件的数量,称 块因子.
    块因子有助于计算缓冲区的大小,可以是 最大的记录*块因子

  2. 分解

    读到缓冲区中,
    根据长度信息分解.
    返回指定的记录

文件的共享

共享形式有许多

  1. 多个用户同时使用一个文件
  2. 能够共享,但不允许同时使用
    1. 一个用户关闭后,下一个用户才能打开
  3. 指针的共享
    1. 多个程序分别用自己的读写指针
    2. 多个程序共享读写指针

实现方法

  1. 链接法,最简单,共享文件放在公共目录中,每个用户建立指向该文件的链接
    1. 允许链接到目录或文件上,可能造成环路,麻烦多
    2. 只允许链接到文件上,比较安全一些

文件的保护

方案要看保护的原因

  1. 天灾型
    1. 副本,缺点在于修改文件后,每个副本都要改
    2. 定时转储,转储到其他介质上
  2. 人祸型
    1. 权限
    2. 保密
      1. 隐藏
      2. 设置访问密码
      3. 加密

权限方面

  1. 一级存取控制矩阵: 文件m个*用户n个,每人都有r,w,x.共3mn个元素.
    用户比较多时矩阵太大.希望优化,
    文件多,没办法
  2. 二级存取控制: 用户分组,文件m个*组n个,每个组有r,w,x.共3mn个元素,
    通常组比用户数不多.

提高文件系统的性能

  1. 使用块高速缓存提高块的读写速度
    1. 要查找的块正好在缓存中,则读写很快.
    2. 缓存可以在内存中,不过现在都在硬盘中.
    3. 要定期写回硬盘中,过程中不幸掉电,可能会引起文件系统一致性问题.
      当被影响的块包含I节点,目录文件,空闲块表等信息时尤为严重.
  2. 需要合理分配空间才能减少零碎的寻址
    放在同一个柱面,的确能让磁头减少移动.
  3. 信息的分布还可以优化
    让信息连续存储(比如12345678),效率并非更好,
    因读取需要时间,数据传输完后,可能已经跳过一些扇区,
    此时磁头所在的地方放第二个块正合适.
    因此分布上可以是(14725836)
  4. RAID技术
    1. RAID0 多个磁盘并行以提高读写速度
    2. RAID1 磁盘镜像,提高可靠性
    3. RAID2/RAID3 以字节或位作为并行单位
    4. RAID4 以块为并行单位,同时为了提高可靠性,会有校验码机制,校验码独立存放
    5. RAID5 类似RAID4,但校验码被认为是数据块的一种,随机存放
    6. 其他RAID通常是以上方法的组合,也意味着可以组合使用以上方法
    7. 比如通常的RAID0+1,RAID5
  5. 要合理调度磁盘,有各种算法
    1. FCFS,先来先服务,简单但效率不高,磁头被左右忽悠
    2. SSTF,最短寻道时间优先,贪婪地优先满足最短寻道时间的任务,可能会导致某个任务饥饿,不公平.
    3. SCAN,扫描算法,也称电梯算法,尽量在一个方向的运行中完成许多任务.相对公平,效率也高.
    4. C-SCAN,循环扫描算法.扫描算法中,中间位置的磁道得到服务更加及时,不够公平.
      若要求磁头只能在一个方向移动时执行任务,回送时不执行,则更公平.
    5. 旋转调度,若磁头不需移动.不同任务需要不同的扇区,先读谁?
      通常应该考虑转速,以及执行任务的序列造成的影响
      假设一个磁道8个扇区,转速合适(刚好每次至少转6格),
      依次读扇区号1,7(1+6),5(7+6mod8),3(5+6mod8),转4下刚好
      应该好过1,7(1+6),3(7+12mod8),5(3+10mod8),转5下以上

FAT文件系统

File Allocation Table
简单,适用于小容量磁盘.
磁盘容量增大后只是修修补补,
从FAT-12,到FAT-16,FAT-32.

一个卷的区域可以划分成

  1. MBR(Master Boot Record),主引导记录,用于加载操作系统
  2. FAT1
  3. FAT2,简单的FAT系统不能太过简单,至少让文件分配表多一个备份以防止被破坏
  4. 其他目录和文件

UNIX文件系统

一开始就考虑了多用户的场景.
并且支持巨量的不同文件系统.
众多发行版有默认文件系统,比如ext3/ext4.
而Arch Linux则足够自由,没有预先规定.

IO设备管理

概念:
IO设备,也称外部设备,外设,设备.
包括CPU和内存以外的所有.

分类上

  • 按使用特性
    • IO设备(键鼠网卡显示器打印机)
    • 存储设备(磁盘,光盘等)
  • 按信息组织方式
    • 字符设备(键盘,打印机)
    • 块设备(磁盘)
  • 按共享属性
    • 共享设备(一段时间内允许多个进程使用,比如磁盘)
    • 独占设备(一段时间内只允许一个进程使用,比如打印机)
    • 虚拟设备(为了让打印机加快效率,采取的一些技术引进的设备)

重要性:

  1. CPU于计算机如同大脑于人,IO设备如同四肢.
  2. IO设备通常是系统瓶颈,决定操作系统的整体性能

设备管理的任务:

  1. 要消解IO慢的矛盾
  2. 要让用户能够统一管理
  3. 要保证安全和保密

IO硬件组成

逻辑结构: 由内而外的体系结构

  • CPU
  • 总线
  • 适配器/接口部件
  • 设备控制器
    • 控制寄存器(写入数据就能控制设备)
    • 状态寄存器(读取数据以了解设备状态)
    • 数据寄存器(交流数据使用)
    • 其他设备
  • 设备

其中设备控制器上的寄存器,有必要有个地址,以供CPU通信用.
该地址称 IO端口地址 或 IO端口号
编址方法有两种

  1. 内存映射编址,把寄存器看作存储器的一种,用同一套方法编址.大多数系统都这样.
  2. IO独立编址,使用不同的方法编址,同时也要求CPU使用专门的IO指令来执行操作

物理结构: 根据技术不同,结构略有不同.
不过通常都连在总线上,只是互相不怎么通信.

全部连总线

设备连通道,通道连总线

IO数据传输和控制方式

随着IO的发展,出现了许多新的技术来解决IO的问题.
有的仅仅是观念更改,
有的直接影响着硬件的结构.

  1. 直接控制(只能串行)

    也称 忙-等方式, 轮询方式, 循环测试方式
    用户进程直接控制 内存/CPU 与 外设 之间的消息传送.

    输入:

    • 发出指令: CPU写设备的控制寄存器(比如启动位置1)
    • 检查状态: 读设备的状态寄存器(比如完成位为1)
    • 读取数据: 读设备的数据寄存器

    输出:

    • 发出指令
    • 检查状态
    • 写数据

    优点: 简单,不靠硬件,不靠操作系统
    缺点:

    1. 效率低
    2. 若过程中出现外部事件,CPU正忙,无法处理

    适合CPU较慢,外设少的系统,比如单片机

  2. 中断控制(初步实现并行,但CPU很忙)

    CPU不再轮询检查状态,发出指令后便做其他工作,CPU与外设并行运行.

    这需要一定的硬件支持.

    • 设备控制器中
      • 中断请求触发器
      • 中断屏蔽触发器
    • CPU中
      • 中断判优电路

    CPU指令的后续过程

    1. 外设准备好,置中断请求触发器
    2. 若中断屏蔽触发器为非屏蔽状态,则触发中断
    3. CPU接收中断,并由中断判优电路决定优先级最高的,给予响应
    4. CPU执行中断处理程序

    优点:

    1. 能够并行工作
    2. 能够处理其他异常,系统稳定性提高
    3. 具有实时响应能力,实时系统也能采用如此方式

    缺点:

    1. 中断本身没有错,但在中断处理过程中,需要让高速的CPU和低速的设备交换数据,CPU还是被拖慢.

  3. DMA方式(一定程度上解放CPU)

    DMA, Direct Memeroy Access
    由DMAC(DMA controller)负责数据的交换,把外设的数据预先放在内存中.
    高速的CPU直接访问较慢的内存,不需要和外设打交道.

    DMA的工作:

    1. 对外设
      1. 协调设备数据传到内存什么位置
      2. 对传送字进行计数
      3. 执行数据传输
    2. 对CPU
      1. 接收指令以开始相应操作
      2. 对CPU发起中断请求以报告操作结束

    处理过程

    1. CPU的IO指令实际上操作DMAC,初始化并启动之
    2. 外设准备好后发送DMA请求
    3. CPU接到请求后允许DMA操作内存.
    4. DMA完成数据传输
    5. DMA发起中断,让CPU进行处理

    优点:

    1. 操作由硬件电路实现,快
    2. CPU仅仅在开始和结束时参与
    3. 适合传送成组的数据

    缺点:

    1. 依然需要CPU进行初始化和结束时的操作,对CPU的分担不彻底
    2. 根本原因在于,想要完成更多的功能,就需要有自己的指令和程序.

  4. 通道方式(更大程度解放CPU)

    通道: 特殊功能的处理器.有自己的指令和程序.

    通道的功能(看起来和DMA差不多)

    1. 接收CPU的指令
    2. 给设备控制器和设备发送各种指令(与DMA的不同)
    3. 组织外设和内存之间的数据传输
    4. 将设备的,自身的中断请求,报告给CPU

    通道通常可以有三种

    1. 选择通道
      一个通道连接多个设备,但同一时间只能有一个在工作.即只能选择一个工作
      传输速率高,以数据块为单位.
      利用率低.
    2. 数组多路通道
      选择通道的改进,使用特别的程序,让通道能在一些场景下先断开某个设备并服务其他设备.
      速率依然高,依然以数据块为单位.而且还能并行操作.
      但控制复杂.
    3. 字节多路通道
      连接多个中低速设备.
      每个设备轮流占用一个很短的时间片,
      并以字节为单位交流数据.
      能够并行工作.

    通常三个通道一起使用

    1. 选择通道,连接高速的磁盘
    2. 数组多路通道,连接磁带等
    3. 字节多路通道,连接终端,键盘等

其他典型IO技术

  1. 缓冲

    CPU直接写设备的数据控制器.
    改为
    CPU写入缓冲,然后就忙其他,设备慢慢取走缓冲中的数据.

    经典的以空间换时间.
    只要 缓冲剩余容量+设备能消耗的数量>CPU产生数据的数量, CPU就能持续工作.
    缓冲满后,CPU相当于直接和设备交流.

    缓冲可以

    1. 硬件实现(打印机中常有)
    2. 软件实现(放在内存中)

    缓冲形式上可以有

    1. 单缓冲
    2. 双缓冲(输出一个,输入一个,全双工)
    3. 多缓冲(输入多个,输入多个)
    4. 缓冲池(单独一个缓冲,输入方面需要就服务输入,输出方面需要就服务输出)

  2. 设备分配技术

    硬件提供可能性,软件实施具体细节.
    管理硬件,即管理各种信息,然后靠判断信息进行分配,然后还要维护信息.

    涉及4张表

    1. 系统设备表SDT(System Device Table)
      一个系统只有一张,全面反应了系统总体的资源情况,对于每个设备,包含
      • 设备类型
      • 设备标识
      • 获得设备的进程号
      • DCT指针
    2. 设备控制表DCT(Device Control Table)
      每个设备可以有一条,记录设备信息的同时,记录每个设备控制器的情况.
      • 设备类型
      • 设备标识
      • 设备忙/闲标记
      • COCT指针
      • 等待队列的首/尾指针
    3. 控制器控制表COCT(Controller Control Table)
      每个控制器可以有一条,用于记载控制器的分配状况和通道状况
      • 控制器标识
      • 控制器忙/闲标记
      • CHCT指针
      • 控制器等待队列首/尾指针
    4. 通道控制表CHCT(Channel Control Table)
      每个通道可以有一条,反映通道的状况
      • 通道标识
      • 通道忙/闲标记
      • COCT指针
      • 通道等待队列首/尾指针

    有了信息要考虑一些分配的原则和算法
    原则:

    1. 提高使用效率
    2. 避免不合理的分配造成死锁
    3. 方便用户
    4. 考虑设备的特性和安全性

    一些具体分配策略(按安全性分)

    1. 安全分配:资源自进程出生就全部分配,直到进程结束才回收,不会有死锁,但效率低
    2. 不安全分配: 进程需要设备就申请,使用完就释放,效率虽高,可能死锁,需要思考更多控制方式以减少死锁危害

    其他策略

    1. 先来先服务
    2. 高优先级策略

  3. SPOOLing假脱机技术

    Simultaneous Peripheral Operation On Line 外围设备同时联机操作.
    以打印机举例

    SPOOLing的行为

    1. 在磁盘上申请一个空闲区作为缓冲
    2. 接收用户请求,将数据放在磁盘,磁盘是共享的
    3. 将请求放入队列,让打印机逐个处理,打印机处理时读磁盘

    用户的行为

    1. 不能真正分配到打印机
    2. 将打印请求发送至SPOOLing

IO软件

以层的观点看待IO软件

  1. 设备驱动

    知道设备如何操作,有什么寄存器,用什么参数,如何指令.
    有通用驱动和厂商驱动.

    1. 从上一层软件读取抽象的请求
    2. 如果驱动空闲则立即执行请求
      1. 转换为更具体的形式(计算地址,检查硬件位置,指令移动等)
      2. 有些一次只能执行一个命令,有些可以并行执行
    3. 如果不空闲就放入队列

  2. 设备无关的系统软件

    设备有共同的特点,和共同的功能需求,比如

    • 命名
      比如unix系统中采用与文件系统相同的命名方法
    • 保护
      比如防止用户进程直接访问设备,unix系统同样采取文件系统的权限方式
    • 设备无关的逻辑
      屏蔽设备本身的存储大小,向上级提供统一的逻辑尺寸
    • 缓冲
      内部要提供一个缓冲区,以方便设备速度的匹配.
    • 分配和释放
      • 存储设备的块分配
        管理磁盘的空闲块状态,哪些空闲,哪些占有,给新的请求分配哪个.
        块只是一个抽象的概念,再由驱动转换成盘区,扇区等.
      • 独占设备的分配和释放
        如果设备被占用,则拒绝其他的使用请求等.
    • 错误处理
      许多错误处理可以让驱动来完成.(一次找不到可以重试,多次重试失败可以放弃)
      但其余错误处理(放弃后再如何)可以由高一级的程序来处理.
    • 其他

    有些功能理应由操作系统来实现.并面向上层,提供统一的接口.
    但也有弱鸡系统不提供,比如MS-DOS.

  3. 用户空间软件

    通常是一些库文件里面包含的程序片段,对外提供接口,对内有各种细节处理.
    好比 print() 内部会调用 count=write(fb,buffer,nbytes)

    还有一类,比如SPOOLing就是创建一些特殊的进程.
    让这些进程模拟出虚拟的设备.
    一方面效果上增加可操作设备的数量,
    另一方面由专门的进程直接操作硬件,可以减少一些使用硬件时的抢占和冲突.

  4. 层次总结

    1. 用户空间软件
    2. 与设备无关的系统软件
    3. 设备驱动程序
    4. 中断处理程序
    5. 硬件

IO问题总结

总的来说是性能问题.解决方法通常是大杂烩

  1. 使用缓冲
  2. DMA与通道等,分担劳力
  3. 异步等待
  4. 虚拟设备,以提高独占设备利用率

死锁

死锁现象

  1. A要开锁,不开不能拿证件,B要证件,不拿证件不能开锁
  2. A让B先,B让C先,C让A先

其他现象

  1. 活锁: 短暂时间内,A,B都没有死等,只是隔一段时间就看一次,
    但长期看,A,B每次的询问都以继续等待告终.
  2. 饥饿: 系统偏爱小任务,大任务迟迟分配不到资源

死锁发生的条件

  1. 资源有限
  2. 互斥(资源是独占的,且排他使用)
  3. 不可剥夺(A无法从B手里抢到资源,只能等B自己释放)
  4. 在占有资源时申请新资源(请求保持,部分分配,占有申请)
  5. 循环等待(存在等待的环路,如例2,例1)

死锁的危害:

  1. 必然导致其他需要这个资源的进程也一并死锁
  2. 死锁得多了,系统可能会瘫痪

解决方法

  • 鸵鸟(什么都不干)
  • 预防(对资源的分配增加明确的限制,而破坏死锁发生的条件,主要着眼于2345条件)
  • 避免(对资源的分配使用柔和的限制,着眼于条件1,资源有限)
  • 检测和解除(主要是预防和避免都会导致效率低,还不如让发生了再修)

  1. 鸵鸟

    权衡危害与解决危害的付出

  2. 预防

    破坏各种死锁条件

    1. 破坏 互斥,只允许特殊的进程操作设备,而不允许普通的用户进程占有和操作.
    2. 破坏 不可剥夺,进程得不到资源就等待,并剥夺处于等待状态的进程的资源.
      该方法代价通常很大,数据面临频繁的申请和释放,极端时导致一直在申请,迟迟不能执行
      适合即使被剥夺也能轻易恢复的资源: CPU(寄存器信息保存在PCB中),内存(保存在外存中)
      使用即使被剥夺也能不报错继续运行的进程,需要进程本身做一些工作(存档点等)
    3. 破坏 请求保持
      要么进程一次申请后不能再申请(静态分配,简单安全资源利用率低)
      要么拥有一种资源时不让继续申请
      (说起来容易做起来难,主动放弃一种资源可能需要先做许多工作,且多次放弃资源本身消耗时间)
    4. 破坏 循环等待,资源有序分配.
      资源编号,越稀缺,编号越大,
      进程只有得到较小的资源,才能申请较大的.
      释放时也应不允许先释放编号小的.

    预防方法总体上对资源分配有硬性的要求,
    与操作系统尽量提高利用率的目标背逆.

  3. 避免

    着眼于资源不够.资源不够是个很宽泛的概念.
    实际资源拥有量,低于进程所需求的总量,并不一定是不够.

    术语上区分出 安全状态, 不安全状态

    安全状态: 系统能在有限时间内得到全部资源.
    即任何一个进程都有盼头.
    C用上系统剩余资源,能够完毕
    C完毕后空出来的资源能让B完毕.
    B完毕后空出来的资源能让A完毕.
    整体都能完毕.

    不安全状态: 走到一个状态时已经穷途末路,无论如何安排都不能让所有进程正常结束.
    A多占用了资源,导致系统剩余资源已经无法满足C,进而无法满足B,A.

    刚进入不安全状态时不一定死锁,但之后一定死锁.

    实现上:

    1. 进程申请资源
    2. 模拟申请后状况,查看是否会变得不安全
    3. 如果是则拒绝申请(此处看出来的确不能充分发挥系统的效率)

    算法上有: 银行家算法(Dijkstra和Habermann)

    即使是死锁避免,还是对资源分配有限制,不能充分发挥系统的效率.

  4. 检测

    大致的方法

    1. 进程和资源分别编号
    2. 有一个资源分配表,什么资源分配给了什么进程
    3. 有一个进程等待分配表,哪个进程想要什么资源
    4. 适当的时机(进程P申请一个已经被占用的资源r时)
      用适当的算法(基于图的算法)反复查找资源分配表和进程等待表,
      确定是否形成环路.

  5. 解除

    解除意味着资源被剥夺,进程被牺牲.
    目标是伤害最小化.

    思考的问题有

    1. 牺牲谁
    2. 怎样保证不总薅一只羊
    3. 如何能让一个被剥夺的进程恢复原先的状态,稍微回退一点也行
    4. 如何让回退的开销最小

    影响的因素有

    1. 进程优先级
    2. 进程已经运行了多长时间,距离完成任务还要多久
    3. 距离完成任务还要多少资源
    4. 进程使用资源的种类和数量,通常容易恢复的资源意味着能简单剥夺
    5. 总共需要撤销多少进程
    6. 该进程已经被剥夺的次数

    解除的方法通常有

    1. 剥夺资源,每次剥夺后再次检测死锁,不够则继续剥夺.
    2. 撤销进程,一次撤销所有进程,或一个个撤销,
      一个个撤销虽好,但次序是个问题.
      优点在于简单明了,缺点在于可能会误杀不引起死锁的进程.

    让进程可以被剥夺的一些技术

    1. 设法恢复撤销前的结果和状态
    2. 建立存档点,被撤销则回退到存档点继续运行,实时系统常用.

研究方法:资源分配图和死锁判定

系统资源分配图(SRAG, System Resource Allocation Graph)
SRAG=(V,E)
V: 顶点集合,包含P(进程集合)与R(资源集合)
E: 边集合,
<Pi, ri>表示进程Pi想使用资源ri,称 请求边
<ri, Pi>表示资源ri已经分配给进程Pi,称 分配边

画成图则可以是

  1. 圆圈表示进程Pi
  2. 方框表示资源ri,可以用方框中的多个点来表示有多个该类资源的实例
  3. 有申请则画请求边(请求边搭在框上),有分配则把请求边改为分配边(分配边搭在点上)
  4. 有释放则删除分配边

判断算法:

  1. 看图中是否有环路.
    鉴于某类型资源ri可能有多个实例.
    出现环路是死锁的必要条件,但不一定充分.
  2. 具体问题具体分析
    1. 找一个非等待,非孤立的进程Pi(不请求,又得到了分配边)
    2. 消去这个Pi的分配边
    3. 将剩余的ri分配给某个请求边
    4. 不断重复,直到所有进程全部变成孤立的,称可化简的,反之称不可化简的.
      可证明:
      1. 不同的化简方法,可导致相同的不可化简结果图.
      2. 若不可化简,则一定导致死锁(充分条件)

综合方法:

资源分级,不同级别采取最适合该级别的不同方案

  1. 内部资源(如PCB表),资源编号,进程编号,破坏条件
  2. 内存,破坏条件,抢占内存,毕竟被抢占的能先换到外存
  3. 作业资源(如设备和文件),统筹资源,死锁避免.
  4. swap空间,静态分配,互补干扰.毕竟空间较大.

参考