操作系统
2024-06-17 19:46:49 #概述

操作系统

第一章

1.1

  • 资源管理者：有效地管理计算机软硬件资源
  • 扩展机器：为用户提供比实际机器更便于运用的抽象，包括进程、地址空间、文件等，提供接口。

1.2 操作系统发展史

  • 真空管和穿孔卡片
  • 晶体管和批处理系统
  • 集成电路和多道系统
  • 个人计算机，移动计算机

1.3 操作系统类型

  • 批处理系统

    • 单道

    • 多道

      • 优点：资源利用率高、系统吞吐量大、系统切换开销小
      • 缺点：无交互能力、作业平均轮转时间长
      • 多道程序设计是现代操作系统诞生的标志

  • 分时系统

    • N个用户 时间片q
    • 轮换法
    • 多路性、交互性、独占性、及时性
    • 分时系统更强调人机交互功能

  • 网络操作系统

  • 分布式操作系统

1.4 操作系统的功能

  • 资源管理者
    • 处理器管理
      • 进程控制
      • 进程同步
      • 进程通信
      • 调度
    • 内存管理
      • 内存分配
      • 内存保护
      • 地址映射
      • 内存扩充
    • 设备管理
      • 缓冲管理
      • 设备分配
      • 设备处理
    • 文件管理
      • 文件存储空间的管理
      • 目录管理
      • 文件的读/写管理
      • 文件保护
  • 扩展机器
    • 用户接口
      • 图形用户接口：GUI
      • 命令接口
      • 程序接口
  • 操作系统的特征
    • 并发性
    • 共享性
    • 虚拟性
    • 异步性

1.5 与操作系统相关的硬件基础

  • 处理器（CPU)
    • 控制部件
      • 控制器：指令控制、时序控制、总线控制、中断控制
      • 程序计数器PC
      • 地址寄存器AR：保存当前CPU所访问的内存单元的地址
      • 指令寄存器IR
      • 指令译码器ID
    • 运算部件
      • 算术逻辑单元ALU
      • 累加寄存器AC
      • 数据缓冲寄存器DR
      • 程序状态字寄存器PSW
    • 工作模式
      • 有PSW中的一个位控制
      • 用户态（目态）
      • 内核态（系统态、核心态、管态）
      • 内核态CPU可以执行其指令集中的每条指令，可使用硬件的各种功能。但是用户态CPU只能执行部分指令，执行时仅使用部分功能。
  • 存储系统
  • I/O子系统
  • 总线

1.6 基本概念

  • 进程(process)：可并发执行的程序在一个数据集合上的运行过程
    • 程序段（正文）
    • 数据段
    • 堆栈段
    • 进程表表项（进程控制块PCB)
    • 处于执行态的进程还有CPU现场
  • 用户接口–系统调用的步骤
    • 将参数压入用户栈，转标准库
    • 将系统调用号压入寄存器
    • 从用户态切换到内核态
    • 内核根据系统调用号找到系统调用处理程序进行处理
    • 从内核态返回用户态

第二章 进程与线程

  • 程序顺序执行
    • 顺序，封闭，可再现
  • 程序并发执行
    • 间断、失去封闭、未必可再现
  • 原语
    • 机器指令级：不允许中断
    • 功能级：不允许并发

2.1 进程

  • 定义：
    • 可以与其他程序并发执行的程序的一次执行
    • 可并发执行的程序在一个数据集合上的运行过程
    • 是系统进行资源分配和调度的一个独立单位
  • 一个程序可以生成不同的进程

进程的基本状态

1
2
3
4
就绪 -> 执行: 进程调度
执行 -> 就绪: 中断（时间片完）
执行 -> 阻塞: 等待某事件
阻塞 -> 就绪: 事件发生

20210708014430

进程表表项（PCB）

  • PCB的组织方式
    • 链接组织方式
      • 把具有同一状态的PCB链接成一个队列
      • 就绪队列、若干个阻塞队列、空队列
    • 索引组织方式
      • 建立相应的索引表
      • 就绪索引表、阻塞索引表等
  • 进程的控制
    • 进程创建
      • 创建原因
        1. 系统初始化
        2. 正在执行的进程调用创建进程的系统调用
        3. 用户请求创建一个进程
        4. 批处理作业的初始化
    • 进程阻塞
      • 阻塞原因
        1. 请求系统服务
        2. 启动某种操作
        3. 数据尚未到达
        4. 无新工作课做
    • 进程唤醒

2.2 线程

线程是轻量级的进程，是一个进程内的基本调度单位，有自己的程序计数器，寄存器及堆栈。共享进程的资源

  • 进程是资源管理的基本单位
  • 线程是调度的基本单位

线程实现

实现方式

  • 在用户空间中实现线程
    • 优点
      • 可以在不支持线程的操作系统中实现多线程编程
      • …
    • 缺点
      • 实现阻塞系统调用困难，如何避免被阻塞线程影响其他线程
      • …
  • 在内核中实现线程
    • 优点：
      • 线程阻塞时，可以运行同一进程中的另一线程或其他进程的线程
      • 在阻塞系统调用和处理缺页问题更有优势
    • 缺点：
      • 创建和终止线程代价较大
  • 混合实现

2.3 进程间通信

进程间通信需要解决的三个问题：

  1. 如何确保多个进程在关键活动中不会冲突
  2. 如何确保多个合作进程的有序进行
  3. 进程间如何传递信息

基本概念

  • 临界资源（竞争条件）：一次只允许一个进程使用的软硬件资源
  • 临界区：在每个进程中，访问临界资源的部分
  • 两种形式制约关系
    • 间接相互制约：源于进程对资源的竞争共享 互斥
    • 直接相互制约：源于进程间的合作 同步
  • 进程互斥：一个进程正在访问临界资源，另一个要访问该资源的进程必须等待。
  • 进程同步：合作完成同一个任务的多个进程，再执行速度或某些时序点上必须相互协调的合作关系

解决进程互斥

并发进程互斥执行准则：

  • 不假设各并发进程的相对执行速度
  • 处于临界区外的进程不能阻止其他进程进入临界区
  • 任何时刻只允许一个进程处于临界区中
  • 不能使进程在临界区外永远等待

屏蔽中断：每个进程进入临界区后先关中断，离开前开中断

缺点：

  • 简单粗暴，效率低
  • 系统可能终止
  • 多CPU时无用

加锁法：用锁变量来表示临界区是否可用

缺点：

  • 不断循环测试，CPU费时
  • 不能实现绝对互斥（lock不是原子操作）

严格轮换法

Peterson解决方案

TSL指令：需要硬件支持

信号量（灯）机制

  • 信号量（semaphore）：OS中用于表示资源的实体，其值仅有down，up原语改变

  • down = P

  • up = V

  • 设s为semaphore信号量，则：

    • 当s >= 0时，表示可供并发进程使用的资源数
    • 当s < 0时，**|s|**表示等待使用s资源的进程数

信号量解决进程互斥

1
2
semaphore mutex;
mutex = 1;

对mutex执行P、V操作

信号量解决进程同步

  • 有哪些临界资源？
  • 有哪些并发执行的进程？
  • ……

信号量机制总结

  • 统一信号量S的P、V操作必须成对出现，有一个**P(S)操作就一定有一个对应的V(S)**操作
    • 进程互斥时，它们处在同一进程
    • 进程同步时，它们不在同一进程
  • 一个同步P操作与一个互斥P操作在一起时，同步P操作在互斥P操作前

2.5处理机调度

调度概述

  • 进程调度

  • 功能：

    • 记录系统中所有进程的执行情况
    • 选择占有处理机的进程
    • 进程上下文切换

  • 时机：

    • 正常执行结束
    • 进程阻塞等待
    • 执行了某些原语（P，V）
    • 从系统态返回用户态
    • 在抢占式调度中，高优先级进程进入就绪队列
    • 分时系统中，分配的时间片用完

  • 进程上下文切换步骤

  • 调度方式：

    • 非抢占式：进程一直执行下去，直到完成本次CPU周期
    • 抢占式：强行剥夺正在执行进程的CPU，并将CPU分配给另一进程

  • 调度的基本准则

  • 作业或进程调度的主要性能评价指标

    • 面向系统的指标：

      • 系统吞吐量——指在单位时间内完成的作业数
      • 处理机利用率
      • 各类资源的平衡利用率

    • 面向用户的指标：

      • 平均周转时间T：

      • image-20210707223837426
        $$
        T = \frac{作业完成时间}{作业数}
        $$

      • 平均带权周转时间**T’**：
        $$
        T_i’ = \frac{T_i}{t_i（实际运行时间）}
        $$

        $$
        T’ = \sum_{i=1}^n T’_i
        $$

      • 平均等待时间W（主要针对进程而言）：
        $$
        {W}_i = {T}_ip-{T}_ir
        $$

        $$
        W = \sum_i^{n}Wi
        $$

非实时调度算法

  • 先来先服务算法（FCFS）：按到来的先后次序进行调度

    • 特点：执行时间短的进程或作业等待时间将长

  • 最短作业/进程有限算法（SJF/SPF）：选择估计需要执行时间最短的投入运行

    • 特点：吞吐量大
    • 对不断有作业进入的系统，长作业将得不到执行

  • 响应比高有限调度算法（HRN）：选择响应比最大的运行
    $$
    R=\frac{等待时间+要求服务时间}{要求服务时间}=\frac{响应时间}{要求服务时间}
    $$

    • 特点：介于FCFS与SJF之间，吞吐量减少，增加了系统开销

  • 轮转调度算法（RR）（适用于进程调度）：将CPU时间划分成时间片，每个进程轮流使用时间片

    • 特别适合于分时系统的可抢占方式的调度算法
    • 时间片q从几ms~几百ms
    • 决定因素
      • 系统对相应时间的要求：T = Nq
      • 就绪队列中进程的数目
      • 系统的处理能力

  • 优先级调度：选择优先级高的进程执行

  • …

实时调度算法

  • 硬实时任务：系统必须完全满足任务的时限要求

  • 软实时任务：允许系统对任务的时限要求有一定的延迟

  • 时限调度算法：选择时限要求最近的任务优先占有处理机

  • 频率单调调度算法：周期长（频率低）的任务优先级越低（适用于周期性实时任务）

    • 实时系统可调度条件：对n个周期不同的任务，周期为Ti，执行时间为ti

    • image-20210707223814477
      $$
      \frac{t_1}{T_1}+\frac{t_2}{T_2}+…+\frac{t_n}{T_n} <= n(2^\frac{1}{n}-1)
      $$

线程调度

第三章 死锁

3.1 资源

  • 可抢占资源
  • 不可抢占资源
  • 使用一个资源的顺序
    1. 请求资源
    2. 使用资源
    3. 释放资源
    4. 若请求失败，有的系统进程将自动被阻塞，资源可用时唤醒；有的系统会返回一个错误代码，请求进程等待一段时间后重试

3.2 死锁概述

  • 死锁定义：如果一个进程集合中的每个进程都在等待只能由该进程集合中的其他进程才能引发的事件，那么，该进程集合是死锁的。
  • 事件是指释放该进程集合中其他进程所占有的资源——资源死锁
  • 该集合中没有任何进程会：运行、释放资源、被唤醒
  • 四个必要条件
    • 互斥条件
    • 占有和等待
    • 不可抢占条件
    • 环路等待条件
  • 死锁建模
  • image-20210706230209431
  • 圆圈表示进程
  • 方框表示资源
  • 四种处理死锁的策略
    • 忽略该问题（鸵鸟算法）
    • 检测死锁并恢复（解除死锁）
    • 仔细对资源进行分配，动态地避免死锁
    • 通过破坏引起死锁的四个条件之一，防止死锁的发生
  • 假设有m个进程，每个进程需要n个同类资源，最容易发生死锁时是(n-1,n-1,n-1…,n-1)时，每个进程请求最后一个。
  • 即，最少需要m * (n-1) + 1个资源

3.3 鸵鸟算法

  • 假装没有问题发生
  • 适用条件
    • 死锁发生的频率很小
    • 预防死锁会付出很大的代价

3.4 死锁检测和死锁恢复

  • 四种数据结构

    • 现有资源矩阵E
    • 可用资源矩阵A
    • 当前分配矩阵C
    • 请求矩阵R

  • 死锁检测方法：

    1. 找到一个C矩阵中的一行向量C_i（一个进程），它可以被可用资源矩阵A满足，标记该向量
    2. C_i释放资源，矩阵A加上C_i释放的资源
    3. 继续寻找下一个向量
    4. 如果最终有没有被满足的向量，系统将进入死锁

  • 例子

    20210706230211

  • 死锁恢复

    • 通过抢占恢复
    • 通过回滚恢复
    • 通过杀死进程恢复

3.5 死锁避免

  • 在资源的动态分配中，用某种方法防止系统进入不安全状态
  • 安全状态：现有的进程资源占有情况下，各进程按某种推进顺序仍然可以使每个进程得到资源最大需求。

避免死锁——银行家算法

  • 和死锁检测有类似的地方，不同点在于：

    • 没有现有资源矩阵，只有可用资源矩阵（Available）
    • 没有请求矩阵（Request），只有需求矩阵（need）
    • 加入最大需求矩阵（Max）

  • 数量关系：

  • $$
    Max[i] = Allocation[i] + Need[i]
    $$

  • 试探性分配后进行安全状态判断

3.6 死锁预防——破坏必要条件

  • 破坏互斥条件
    • 避免分配不必要的资源
    • 尽可能少的进程真正申请
    • 比如打印机的假脱机技术
  • 破坏占有且等待条件
    • 一次性获取所需的全部资源
  • 破坏不可抢占条件
  • 破坏环路等待条件

3.7 其他问题

  • 活锁
    • CPU总是被消耗完
    • 原因是轮询可进入临界区或获取资源
  • 饥饿
    • 由于分配资源的算法导致某些进程得不到服务
    • 原因是系统总是让短进程先执行，短进程源源不断
    • 解决办法是通过先来先服务分配资源

第四章 存储管理

序言

  • 存储管理器（memory manager）
    • 内存分配与回收
    • 内存空间管理
    • 地址映射（重定位）
    • 存储保护
    • 处理内存超载
  • 内存分配方式
    • 连续分配
      • 单一连续分配
      • 固定分区分配
      • 动态分区分配
    • 离散分配
      • 分页
      • 分段
      • 段页
  • 程序链接
    • 静态链接
      • 装入前链接成为一个完整模块
    • 装入时动态链接
      • 运行前边装入边链接
    • 运行时动态链接
      • 运行时需要目标模块才进行链接装入
  • 地址映射（地址重定位 ）
    • 用户程序装入内存时，对目标程序有关指令和数据的地址部分的修改
    • 逻辑地址–>物理地址
    • 地址映射的方式
      • 静态重定位（可重定位装入）
        • 为程序分配内存时，必须分配全部内存空间
      • 动态重定位（动态运行时装入）
        • 需要重定位寄存器支持
        • 地址转换推迟在程序真正要执行时才进行
  • 存储保护：保存在内存中的多道程序，只能在给定的存储区域内活动并互补产生干扰
    • 防止地址越界
    • 防止越权
    • 使用基址寄存器（重定位寄存器）和届地址寄存器（界限寄存器）实现
  • 内存超载：所有进程所需的内存空间总和通常超出物理内存实际能够支持的范围
    • 交换技术
    • 覆盖技术
    • 虚拟内存

4.1 无存储器抽象

  • 程序直接访问物理内存

    20210707134238

  • 多道系统

    • 采用连续分区分配方式，需要解决存储保护和重定位问题
    • 保护键技术：内存每块一个4位保护键，通过保护键和PSW中对应的4位码来防止进程间的互相干扰
    • 静态重定位：程序在装入内存时，由装载器对相关地址进行一次性映射（物理地址=逻辑地址加上偏移量）

  • 由于将物理地址完全暴露给用户进程，所以

    • 用户进程可能破坏操作系统
    • 多道程序设计困难

  • 所以需要进行存储器抽象

4.2 存储器抽象 地址空间

  • 进程可用于寻址内存的一套地址集合
  • 本质：内存空间（物理地址空间）的一部分
  • 每个进程有独立于其他进程的自己的地址空间
  • 通过动态重定位实现
  • 硬件支持
    • 基址寄存器
    • 界限寄存器

交换技术（swapping）

  • 处理内存超载的简单方法

  • 空闲内存的管理：跟踪内存情况

  • 位图：如图

    20210707140307

  • 链表：如图

    20210707140502

  • 内存分配算法–动态分区分配方式（动态分区存储管理）

    • 首次适配算法（first fit）
    • 下次适配算法（next fit）：对首次适配进行调整，记录上一次搜索停止位置，下一次从此开始
    • 最佳适配算法（best fit）：找到能够容纳的最小空闲区
    • 最坏适配算法（worst fit）：找到能够容纳的最大空闲区
    • 最快适配算法（quick fit）

  • 为进程结点和空闲区结点建立独立的链表

    • 搜索速度提高，但复杂度增加且内存回收慢

  • 如果空闲链表按地址递增排序

    • 首次适配：低地址区碎片多，每次从低地址区查找增加开销
    • 下次适配：空闲区分布均匀，减少查询空闲分区的开销，但缺乏大的空闲分区
    • 最佳适配：查找开销大，能够避免大量难利用的碎片
    • 最差适配：查找开销大，避免留下大量难利用的碎片,但缺乏大的空闲分区

  • 为增加搜索速度

    • 最佳适配：空闲区按空间大小递增排序
    • 最差适配：空闲区按空间大小递减排序

覆盖技术（overlay）

  • 解决程序大小超过物理内存总和问题
  • 发生在同一进程或作业内

思想：将程序分为多个段（模块），常用段常驻内存，不常用段需要时调入内存

内存中分配一个固定区和若干个覆盖区

常用段调入固定区后不再调出

不常用段需要时调入覆盖区，不需要时调出

缺点：

  • 对用户不透明，增加编程负担

分页

快表（TLB)

局部性原理：

  • 时间局部性：如果执行了程序中的某个指令，在不久后这条指令很有可能再次执行；访问了程序中的某个数据，不久后该数据可能再次被访问
  • 空间局部性：访问了某个存储单元，不久后可能会访问该存储单元附近的存储单元

快表，又称联想寄存器（TLB），是一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以及加速地址变换的过程。与此对应，内存中的页表被称为慢表

  • 快表命中，一次访存
  • 快表未命中，两次访存

多级页表

  • 页表必须连续存放，当页表很大时，需要占用多个连续的页框

4.3 虚拟内存

  • 处理内存超载的最重要技术
  • 内存管理单元（MMU）完成地址映射
  • 页表：放在内存中，把虚拟页面映射为页框，即给出虚拟地址与物理地址的映射关系
    • 有多个页表项组成
    • 每一个页面对应一个页表项
  • 页框：内存
  • 页面：进程

4.4 页面置换算法

  • 一般原则：
    • 已修改的页面必须首先保存（需要写回磁盘），未修改的页面直接由新页面覆盖（已经是最新的）
    • 尽可能不要选择频繁使用的页面置换出内存，很可能很短时间内又要被调入内存
  • 物理块（页框）分配与置换策略
    • 固定分配局部置换
      • 进程占据的内存页框数不变
      • 缺页时，只能与该进程在内存的页面置换
      • 由进程类型、程序员确定每个进程分得的物理块数
      • 但分配时，难以确定某个进程的页框数
    • 可变分配全局置换
      • 最易实现，空闲页框由OS管理——空闲物理块队列
      • 先为进程分配一定物理块
      • 缺页时，从系统空闲物理块队列中取一块
      • 空闲物理块取完时，与内存中的一页置换
    • 可变分配局部置换
      • 先为进程分配一定物理块
      • 缺页时，只与该进程在内存的一页置换
      • 缺页率较高时调整页框数
  • 固定和可变：即进程占据的页框数是否会发生变化
  • 全局和局部：即进程缺页时置换只在该内存中进行叫做局部置换，可能置换其他进程的页面叫做全局置换
  • 最优（OPT）
  • 最近未使用（NRU[not recently used]）：当页面被访问或修改时，设置访问位R和修改位M
    • 0：R = 0， M = 0；
    • 1：R = 0， M = 1；
    • 2：R = 1， M = 0；
    • 3：R = 1， M = 1（时钟中断R清0，变成1类）；
    • 从编号最小的开始淘汰，即没访问没修改–>修改了没访问–>访问了没修改–>访问了修改了
  • 先进先出（FIFO）：OS维护一个内存中页面的链表，按照进入内存顺序组织，置换
    • FIFO的Belady现象：当分配给进程的物理页面数增加时，缺页次数反而增加
  • 第二次机会（SCR）
    • 对FIFO算法的修改，置换时先看访问位R是否为0，为0置换，否则置为0放入队尾
  • 时钟（clock）
    • 避免SCR中移动页面，组织一个环形链表，检查表针指向的页面，R为0置换，否则指针后移
  • 最近最少使用（LRU）：选择最近最少使用的页淘汰
    • 根据过去预测未来
    • 最近最多使用在表头，最近最少使用在表尾
    • 每次访问时更新链表
  • 最不常用（NFU）：将每个页面和计时器相关联，初值为0，每次时钟中断将R位加到计数器，淘汰计数器值最小的
    • 和LRU粗略近似

4.5 分页系统中的设计问题

  • …
  • 页面大小：
    • 小页面
      • 更少的内部碎片
      • 更加灵活，适合各种程序结构和数据段
      • 减少内存中局部执行没用的程序
      • 缺点：进程需要更多页面，更大页表
    • 大页面
      • 页表小
      • 缺点：小页面的优点

4.7 分段

  • 分页缺点：虚地址空间是一维的，不利于动态增长
  • 解决：根据逻辑关系分段
  • 20210707214634

第五章 文件系统

序言

  • 文件的根本目标：长期存储信息
  • 文件的存储介质：磁盘、光盘、磁带等
  • 文件
    • 文件是进程创建的信息逻辑单元
    • 文件是磁盘上的一种地址空间
  • 文件系统
    • 文件是由操作系统管理，操作系统中处理文件的部分叫做文件系统

5.1 文件

5.1.1 文件命名

  • 文件名.扩展名

5.1.2 文件结构

  • 字节序列
  • 记录序列
  • 数

5.1.3 文件类型

  • 普通文件
    • ASCII文件
    • 二进制文件
    • Unicode文件
  • 目录
    • 管理文件系统结构的系统文件

5.1.4 文件存取

  • 顺序存取
  • 随机存取

5.1.5 文件属性

  • 除了文件名和数据，还会保存文件属性（元数据）

5.2 目录

  • 目录或文件夹管理的基本要求
    • 实现”按名存取“
    • 提高对目录的检索速度
    • 文件共享
    • 允许文件重名
  • 目录项
    • 目录的基本组成元素，文件控制块（FCB）
    • 内容：存放了管理文件所需的所有有关信息，包含文件名、存储地址等基本信息
    • 目录项是文件存在的标志：目录项和文件一 一对应
  • 文件目录（目录）
    • 把文件的目录项（FCB）组织在一起，就构成了文件目录

5.3 文件系统的实现

20210707225439

20210707225443

文件存储的实现

  • 外存三种主要分配方式
    • 连续分配——顺序式文件结构
    • 链接分配——链接式文件结构
    • 索引分配——索引式文件结构

显示链接

  • 这样的表整磁盘仅设一张，称为文件分配表（FAT）

5.4 文件系统管理与优化

磁盘空间管理

  • 盘块
    • 盘块大小
      • 太大，小文件浪费空间
      • 太效，大文件访问效率低
    • 记录空闲盘块
    • 盘块配额
  • 磁盘访问时间 = 寻道时间 + 旋转延迟时间 + 传输时间
  • 20210707231453

第六章 IO

  • IO层次
    • 用户级I/O软件
    • 与设备无关的OS软件
    • 设备驱动程序
    • 中断处理程序
    • 硬件
  • 20210707234756

磁盘调度算法

  • 先来先服务（FCFS)
  • 最短寻道优先（SSF）
  • 电梯算法（SCAN）
  • 循环扫描（S-SCAN)
上一页
2024-06-17 19:46:49 #概述
下一页