实话说，计操，我还没看完

操作系统（operating system，OS）是管理计算机硬件与软件资源的计算机程序，同时也是计算机系统的内核与基石。

图片来源：百度

一、操作系统的基本概念

1、概念（定义）

• 负责管理协调硬件、软件等计算机资源的工作
• 为上层用户、应用程序提供简单易用的服务
• 是一种系统软件

2、功能和目标

• 资源的管理者
  • 处理机管理
  • 存储器管理
  • 文件管理
  • 设备管理
• 向用户提供服务
  • 命令接口
    • 联机命令接口
    • 脱机命令接口
  • 程序接口
    • 由一组系统调用组成
  • GUI用户图形界面
• 对硬件机器的扩展
  • 扩充机器

3、特征

• 并发
  • 指两个或者多个事件在同一时间间隔内发生
  • 宏观上同时发生，微观上交替发生
• 共享（资源共享）
  • 互斥共享方式
    • 如：对摄像头设备的共享使用
  • 同时共享方式
    • 如：对硬盘资源的共享使用
• 虚拟
  • 空分复用技术
    • 如：虚拟存储技术
  • 时分复用技术
    • 如：虚拟处理器技术
• 异步

4、本部分重点：

• 理解并发和并行的区别
• 并发和共享互为存在条件
• 没有并发和共享，就谈不上虚拟和异步。因此，并发和共享为操作系统的两个最基本的特征

二、操作系统的发展和分类

1、手工操作系统

• 缺点：人机速度矛盾

2、批处理系统

• 单道批处理系统（引入脱机输入输出技术）
  • 优点：缓解人机速度矛盾
  • 缺点：资源利用率依然很低
• 多道批处理系统（操作系统开始出现）
  • 优点：多道程序并发执行，资源利用率高
  • 缺点：不提供人机交互功能

3、分时操作系统

• 优点：提供人机交互功能
• 缺点：不能优先处理紧急任务

4、实时操作系统

• 硬实时系统
  • 必须在绝对严格的规定时间内完成处理
• 软实时系统
  • 能接受偶尔违反时间规定
• 优点
  • 能优先处理紧急任务

5、网络操作系统

6、分布式操作系统

7、个人计算机操作系统

三、操作系统的运行机制和体系结构

1、运行机制

• 两种指令
  • 特权指令
  • 非特权指令
• 两种处理器状态
  • 核心态
  • 用户态
• 两种程序
  • 内核程序
  • 应用程序

2、操作系统内核

• 时钟管理
• 中断处理
• 原语
  • 一种特殊程序，其执行具有原子性
• 对系统的资源进行管理的功能
  • 进程管理
  • 存储器管理
  • 设备管理

3、操作系统的体系结构

• 大内核
  • 优点：高性能
  • 缺点：内核代码庞大，结构混乱，难以维护
• 微内核
  • 优点：内核功能少，结构清晰，方便维护
  • 缺点：需要频繁的在核心态和用户态之间切换，性能低

4、本部分重点

• 特权指令只在核心态下执行
• 内核程序只在核心态下执行
• 核心态与用户态之间的切换

四、中断和异常

1、中断机制的诞生

• 为实现多道程序并发执行而引入的一种技术

2、中断的概念和作用

• 发生中断，意味着需要操作系统介入展开管理工作，CPU会立即进入核心态
• “中断”是CPU从用户态进入核心态的唯一途径

3、中断的分类

• 内中断（也称异常，例外，陷入）
  • 自愿中断
    • 指令中断
  • 强迫中断
    • 硬件故障
    • 软件中断
• 外中断（中断）
  • 外部请求
  • 人工干预
• 通过“中断信号来自CPU外部还是内部”判断是内/外中断

4、补充

• 内中断的另一种分类方式
  • 陷阱，陷入（trap）
  • 故障（fault）
  • 终止（abort）

5、外中断的处理过程

• 每天指令执行结束后，cpu检查是否有外部中断信号
• 如有外部中断信号，则要保护被中断进程的CPU环境
• 根据中断信号类型转入相应的中断处理程序
• 恢复原进程的CPU环境并退出中断，返回原进程继续往下执行

五、进程和线程

1、进程的定义

• 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

2、进程的组成

• PCB
  • 进程描述的信息
  • 进程控制和管理信息
  • 资源分配清单
  • 处理机相关信息
• 程序段
  • 存放要执行的程序代码
• 数据段
  • 存放程序运行过程中处理的各种数据
• PCB是进程存在的唯一标志
• 进程的管理者（操作系统）所需要的数据都在PCB中
• 程序本身的运行所需要的数据在程序段、数据段中

3、进程的组织形式

• 链接方式
  • 按照进程状态将PCB分为多个队列
• 索引方式
  • 按照进程状态建立几张索引表，各表项指向一个PCB

4、进程的特征

• 动态性
  • 进程的最基本特征
• 并发性
• 独立性
  • 进程是系统进行资源分配、调度的独立单位
• 异步性
  • 各个进程以不可预知的速度向前推进，可能导致运行结果的不确定性
• 结构性

5、进程的状态

• 运行状态
  • CPU（√）；其它所需资源（√）
• 就绪状态
  • CPU（×）；其它所需资源（√）
• 阻塞状态
  • CPU（×）；其它所需资源（×）
• 创建状态
  • 操作系统为新进程分配资源，创建PCB
• 终止状态
  • 操作系统回收进程的资源，撤销PCB

6、进程的状态间转换

• 就绪态→运行态
  • 进程被调度
• 运行态→就绪态
  • 时间片到，或CPU被其他高优先级的进程抢占
• 运行态→阻塞态
  • 等待系统资源分配，或等待某事件发生（主动行为）
• 阻塞态→就绪态
  • 资源分配到位，等待的事件发生（被动行为）
• 创建态→就绪态
  • 系统完成创建进程相关的工作
• 运行态→终止态
  • 进程的运行结束，或运行过程中遇到不可修复的错误

7、进程控制

• 基本概念
  • 进程控制就是要实现进程状态的转换
  • 进程控制用原语实现
    • 原语用开/关中断实现
    • 原语是一种特殊的程序
    • 原语的执行必须一气呵成，不可中断
• 相关原语
  • 进程的创建
  • 进程的终止
  • 进程的阻塞
  • 进程的唤醒
  • 进程的切换
• 进程的阻塞和唤醒要成对出现

8、进程通信

• 共享存储
  • 设置一个共享空间
  • 要互斥地访问共享空间
  • 两种方式
    • 基于数据结构（低级）
    • 基于存储区的共享（高级）
• 管道通信
  • 设置一个特殊的共享文件（管道），其实就是一个缓冲区
  • 一个管道只能实现半双工通信
  • 实现双向同时通信要建立两个管道
  • 各进程要互斥访问管道
  • 写满时，不能再写；读空时，不能再读
  • 没写满，不能读；没读空，不能写
• 消息传递
  • 传递结构化的消息（消息头/消息体）
  • 系统提供“发送/接受原语”
  • 两种方式
    • 直接通信方式
      • 消息直接挂到接收方的消息队列里
    • 间接（信箱）通信方式
      • 消息先发到中间体（信箱）

9、线程、多线程模型

• 什么是线程，为什么要引入线程？
  • 线程可理解为“轻量级进程”
  • 可增加并发度，减少并发带来的开销
• 引入线程机制后，有什么变化？（和传统的进程机制对比）
  • 资源分配，处理机调度
  • 并发性
  • （实现并发的）系统开销
• 线程有哪些重要属性
  • 线程是处理机调度的单位，进程是资源分配的单位
  • 同一进程的各线程共享进程拥有的资源
  • 同一进程内的线程切换不会导致进程的切换
• 线程实现方式
  • 用户级线程
    • 从用户视角的线程
  • 内核级线程
    • 从操作系统视角看的进程（内核级线程才是处理机分配的单位）
  • 组合方式
    • 上述两种方式结合
• 多线程模型
  • 多对一
    • 优点：进程管理开销小，效率高
    • 缺点：一个线程阻塞会导致整个进程都被阻塞（并发度低）
  • 一对一
    • 优点：各线程可分配到多核处理机并发执行，并发度高
    • 缺点：进程管理开销大
  • 多对多
    • 集二者所长

六、处理机调度

1、基本概念

• 按照某种算法选择一个进程将处理机分配给它

2、三个层次

• 高级调度（作业调度）
  • 按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程
• 中级调度（内存调度）
  • 按照某种规则，从挂起队列中选择合适的进程将其数据调回内存
• 低级调度（进程调度）
  • 按照某种规则，从就绪队列中选择一个进程为其分配处理机

3、三层调度的联系、对比

• 高级调度
  • 外存→内存（面向作业）
  • 发生频率：最低
• 中级调度
  • 外存→内存
  • 发生频率：中等
• 低级调度
  • 内存→CPU
  • 发生频率：最高

4、补充知识

• 为减轻系统负载，提高资源利用率，暂时不执行的进程会被调到外存从而变为“挂起态”
• 七状态模型：在五状态模型的基础上加入了“就绪挂起”和“阻塞挂起”两种状态

5、进程调度的时机

• 什么时候需要进程调度？
  • 主动放弃
    • 进程正常终止
    • 运行过程中发生异常而终止
    • 主动阻塞（如：等待I/O）
  • 被动放弃
    • 分给进程的时间片用完
    • 有更紧急的事情需要处理（如：I/O中断）
    • 有更高优先级的进程加入就绪队列
• 什么时候不能进行进程调度？
  • 在处理中断的过程中
  • 进程在操作系统内核程序临界区中
  • 原子操作过程中（原语）

6、进程调度的切换与过程

• 狭义的“调度”和“切换”的区别
• 切换过程
  • 对原来运行进程各种数据的保存
  • 对新的进程各种数据的恢复
• 重要结论
  • 进程调度、切换是有代价的，并不是调度越频繁，并发度就越高

7、进程调度的方式

• 非剥夺调度方式（非抢占式）
  • 只能由当前运行的进程主动放弃CPU
• 剥夺调度方式（抢占式）
  • 可由操作系统剥夺当前进程的CPU使用权

8、调度算法的评价指标（理解，会计算）

• CPU利用率
  • 利用率=忙碌时间/总时间
• 系统吞吐量
  • 系统吞吐量=总共完成了多少道作业/总共花了多少时间
• 周转时间
  • 周转时间=作业完成时间-作业提交时间
  • 平均周转时间=各作业周转时间之和/作业数
  • 带权周转时间=作业周转时间/作业实际运行的时间
  • 平均带权周转时间=各作业带权周转时间之和/作业数
• 等待时间
  • 进程/作业等待被服务的时间之和
  • 平均等待时间即各个进程/作业等待时间的平均值
• 响应时间
  • 从用户提交请求到首次产生响应所用的时间

9、调度算法

• 先来先服务（FCFS，First Come First Serve）
  • 算法思想
    • 主要从“公平”角度考虑（类似生活中排队买东西）
  • 算法规则
    • 按照作业/进程到达的先后顺序进行服务
  • 用于作业/进程调度
    • 用于作业调度时，考虑的是哪个作业先到达后备队列
    • 用于进程调度时，考虑的是哪个进程先到达就绪队列
  • 是否可抢占？
    • 非抢占式算法
  • 优缺点
    • 优点：公平、算法实现简单
    • 缺点：对长作业有利，对短作业不利（如：排队买奶茶）
  • 是否会导致饥饿（某进程/作业长期得不到服务）
    • 不会
• 短作业优先（SJF，Shortest Job First）
  • 算法思想
    • 追求最少的平均等待时间、平均周转时间、平均带权周转时间
  • 算法规则
    • 最短的作业/进程优先得到服务（“最短”：服务时间最短）
  • 用于作业/进程调度
    • 用于进程调度时称为“短进程优先（SPF，Shortest Process First）算法”
  • 是否可抢占？
    • SJF和SPF是非抢占式算法。
    • 但是也有抢占式版本：最短剩余时间优先（SRTN，Shortest Remaining Time Next）算法
  • 优缺点
    • 优点：“最短的”平均等待时间、平均周转时间
    • 缺点：不公平。对短作业有利，对长作业不利
  • 是否会导致饥饿（某进程/作业长期得不到服务）
    • 会。如果有源源不断的作业/进程到来，可能使长作业/进程长时间得不到服务，产生“饥饿”现象。如果一直得不到服务，则称为“饿死”
• 高响应比优先（HRRN，Highest Response Ratio Next）
  • 算法思想
    • 综合考虑作业/进程的等待时间和要求服务的时间
  • 算法规则
    • 在每次调度时先计算各个作业/进程的响应比
    • 响应比=（等待时间+要求服务时间）/要求服务时间；响应比>=1
    • 选择响应比最高的作业/进程为其服务
  • 用于作业/进程调度
    • 即可用于作业调度，也可用于进程调度
  • 是否可抢占？
    • 非抢占式算法
  • 优缺点
    • 优点：综合考虑了等待时间和运行时间（要求服务时间）。
  • 是否会导致饥饿
    • 不会
• 时间片轮转（RR，Round-Robin）
  • 算法思想
    • 公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
  • 算法规则
    • 按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如：100ms）。
    • 若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队
  • 用于作业/进程调度
    • 用于进程调度（只有作业放入内存建立了相应的进程后，才会被分配处理机时间片）
  • 是否可抢占？
    • 抢占式算法
    • 由时钟装置发出时钟中断来通知CPU时间片已到
  • 优缺点
    • 优点：公平，响应快，适用于分时操作系统
    • 缺点：由于高频率进程切换，有一定开销，不区分任务的紧急程度
  • 是否会导致饥饿
    • 不会
• 优先级调度
  • 算法思想
    • 根据紧急程度来决定处理顺序
  • 算法规则
    • 调度时选择优先级最高的作业/进程
  • 用于作业/进程调度
    • 即可用于作业调度，也可用于进程调度。甚至，还能用于I/O调度
  • 是否可抢占？
    • 抢占式/非抢占式都有
  • 优缺点
    • 优点：用优先级区分紧急程度、重要程度，适用于实时操作系统，可灵活调整对各种作业/进程的偏好程度
    • 缺点：若源源不断的有高优先级进程到来，可能导致饥饿
  • 是否会导致饥饿
    • 会
• 多级反馈队列
  • 算法思想
    • 对其他调度算法的折中权衡
  • 算法规则
    • 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
    • 新进程到达时先进入1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列。则重新放回该队列队尾
    • 只有第k级队列为空时，才会为k+1级队头进程分配时间片
  • 用于作业/进程调度
    • 用于进程调度
  • 是否可抢占？
    • 抢占式算法
  • 优缺点
    • 优点：集合FCFS、RR、SPF的优点于一身
  • 是否会导致饥饿
    • 会

七、进程同步

1、同步、互斥

• 进程同步
  • 并发性带来了异步性，有时需要通过进程同步解决这种异步问题
  • 有的进程之间需要相互配合完成工作，各进程的工作推进需要遵循一定的先后顺序
• 进程互斥
  • 对临界资源的访问，需要互斥的进行。即同一时间段内只能允许一个进程访问资源
  • 四个部分
    • 进入区
      • 检查是否可进入临界区，若可进入，需要“上锁”
    • 临界区
      • 访问临界资源的那段代码
    • 退出区
      • 负责“解锁”
    • 剩余区
      • 其余代码部分
  • 需要遵循的原则
    • 空闲让进
      • 临界区空闲时，应该允许一个进程访问
    • 忙则等待
      • 临界区正在被访问时，其它试图访问的进程需要等待
    • 有限等待
      • 要在有限时间内进入临界区，保证不会饥饿
    • 让权等待
      • 进不了临界区的进程，要释放处理机，防止忙等

2、进程互斥的软件实现方法

• 单标志法
  • 在进入区只做“检查”，不“上锁”
  • 在退出区把临界区的使用权转交给另一个进程（相当于在退出区即给另一进程“解锁”，又给自己“上锁”）
  • 主要问题：不遵循“空闲让进”原则
• 双标志先检查
  • 在进入区先“检查”后“上锁”，退出区“解锁”
  • 主要问题：不遵循“忙则等待”原则
• 双标志后检查
  • 在进入区先“加锁”后“检查”，退出区“解锁”
  • 主要问题：不遵循“空闲让进、有限等待”原则，可能导致“饥饿”
• Peterson算法
  • 在进入区“主动争取-主动谦让-检查对方是否想进、己方是否谦让”
  • 主要问题：不遵循“让权等待”原则，会发生“忙等”

3、进程互斥的硬件实现方法

• 中断屏蔽方法
  • 使用“开/关中断”指令实现
  • 优点：简单高效
  • 缺点：只适用于单处理机、操作系统内核进程
• TestAndSet（TS指令/TSL指令）
  • old记录是否已被上锁
  • 再将lock设为true
  • 检查临界区是否已被上锁（若已上锁，则循环重复前几步）
  • 优点：实现简单，适用于多处理机环境
  • 缺点：不满足“让权等待”
• Swap指令（XCHG指令）
  • 逻辑上同TSL

4、信号量机制

• 整型信号量
  • 用一个整型变量作为信号量，数值表示某种资源数
  • 整型信号量与普通整型信号量的区别：对信号量只能执行初始化、P、V三种操作
  • 整型信号量存在的问题：不能满足让权等待原则
• 记录型信号量
  • S.value表示某种资源数，S.L指向等待该资源的队列
  • P操作中，一定是先S.value--，之后可能需要执行block原语
  • V操作中，一定是先S.value++，之后可能需要执行wakeup原语
  • 注意：要能够自己推断什么条件下需要执行block或wakeup
  • 可以用记录型信号量实现系统资源的“申请”和“释放”
  • 可以用记录型信号量实现进程互斥、进程同步
• 注意：若出现P(S)、V(S)的操作，除非特殊说明，否则默认S为记录型信号量
• 实现进程互斥
  • 分析问题，确定临界区
  • 设置互斥信号量，初值为1
  • 临界区之前对信号量执行P操作
  • 临界区之后对信号量执行V操作
• 实现进程同步
  • 分析问题，找出哪里需要实现“一前一后”的同步关系
  • 设置同步信号量，初值为0
  • 在“前操作”之后执行V操作
  • 在“后操作”之前执行P操作
• 实现进程的前驱关系
  • 分析问题，画出前驱图，把每一对前驱关系都看成一个同步问题
  • 为每一个前驱关系设置同步信号量，初值为0
  • 在每个“前操作”之后执行V操作
  • 在每个“后操作”之前执行P操作

5、生产者-消费者问题

• 一个互斥、同步的综合问题
• 隐含了两对同步关系
  • 有时候是消费者需要等待生产者生产，有时候生产者需要等待消费者消费，这是两个不同的“一前一后问题”。因此需要设置两个同步信号量
• 实现“一前一后”需要“前V后P”

6、多生产者-多消费者问题

• 关键在于理清复杂的同步关系
• 在分析同步问题（一前一后问题）时，不能从单个进程行为角度来分析，要把“一前一后”发生的事情看成是两种“事件”的前后关系

7、吸烟者问题

• 可为我们解决“可以生产多个产品的单生产者”问题提供一个思路
• 精华
  • “轮流让各个吸烟者吸烟”必然需要“轮流的在桌上放上组合一、二、三”，如何用一个整形变量i实现这个“轮流”的过程
• 若一个生产者要生产多种产品（或会引发多种前驱事件），那个各个V操作应该放在各自对应“事件”发生之后的位置

8、读者-写者问题

• 为我们解决复杂的互斥问题提供一个参考思路
• 核心思想
  • 设置一个计数器count来记录当前正在访问共享文件的读进程数。
  • 用count的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理
  • 对count变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现“一气呵成”，自然应该想到用互斥信号量
  • 体会如何解决“写进程饥饿”问题

9、哲学家进餐问题

• 关键在于进程死锁
• 这些进程之间只存在互斥关系，但之前接触的互斥关系不同的是，每个进程都需要同时持有两个临界资源，因此就有“死锁”的隐患

八、管程

1、为什么要引入管程？

• 解决信号量机制编程麻烦、易出错的问题

2、组成

• 共享数据结构
• 对数据结构初始化的语句
• 一组用来访问数据结构的过程（函数）

3、基本特征

• 各外部进程/线程只能通过管程提供的特定“入口”才能访问共享数据
• 每次仅允许一个进程在管程内执行某个内部过程

4、补充

• 各进程必须互斥访问管程的特性是由编译器实现的
• 可在管程中设置条件变量及等待/唤醒操作以解决同步问题

九、死锁

1、死锁的概念

• 什么是死锁
  • 各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进
• 死锁、饥饿、死循环的区别
  • 死锁
    • 至少是两个进程一起死锁，死锁进程处于阻塞态
  • 饥饿
    • 可以只有一个进程饥饿，饥饿进程可能阻塞也可能就绪
  • 死循环
    • 可能只有一个进程发生死循环，死循环的进程可上处理机
  • 死锁和饥饿是操作系统要解决的问题，死循环是应用程序员要解决的问题
• 死锁产生的必要条件
  • 互斥条件
    • 对必须互斥使用的资源的争抢才会导致死锁
  • 不剥夺条件
    • 进程保持的资源只能主动释放，不可强行剥夺
  • 请求和保持条件
    • 保持着某些资源不放的同时，请求别的资源
  • 循环等待条件
    • 存在一种进程资源的循环等待链
    • 循环等待未必死锁，死锁一定有循环等待
• 什么时候会发生死锁
  • 对不可剥夺资源的不合理分配，可能导致死锁
• 死锁的处理策略
  • 预防死锁
    • 破坏死锁产生的四个必要条件
  • 避免死锁
    • 避免系统进入不安全状态（银行家算法）
  • 死锁的检查和解除
    • 允许死锁发生，系统负责检测出死锁并解除

2、预防死锁

• 破坏互斥条件
  • 将临界资源改造为可共享使用的资源（如：SPOOLing技术）
  • 缺点
    • 可行性不高，很多时候无法破坏互斥条件
• 破坏不剥夺条件
  • 方案一
    • 申请的资源得不到满足时，立即释放拥有的所有资源
  • 方案二
    • 申请的资源被其他进程占用时，由操作系统协助剥夺（考虑优先级）
  • 缺点
    • 实现复杂
    • 剥夺资源可能导致部分工作失效
    • 反复申请和释放导致系统开销大
    • 可能导致饥饿
• 破坏请求和保持条件
  • 运行前分配好所有需要的资源，之后一直保持
  • 缺点
    • 资源利用率低
    • 可能导致饥饿
• 破坏循环等待条件
  • 给资源编号，必须按照编号从小到大的顺序申请资源
  • 缺点
    • 不方便增加新设备
    • 会导致资源浪费
    • 用户变成麻烦

3、避免死锁

• 数据结构
• 银行家算法步骤
• 安全性算法步骤
• 系统处于不安全状态未必死锁，但死锁一定处于不安全状态
• 系统处于安全状态一定不会死锁

4、死锁的检测和解除

• 如何检测
  • 数据结构：资源分配图
    • 两种结点
      • 进程结点
      • 资源结点
    • 两种边
      • 进程结点→资源结点（请求边）
      • 资源结点→进程结点（分配边）
  • 死锁检测算法
    • 依次消除与不阻塞进程相连的边，直到无边可消
    • 注：所谓不阻塞进程是指其申请的资源数还足够的进程
    • 死锁定理
      • 若资源分配图是不可完全简化的，说明发生了死锁
• 如何解除
  • 资源剥夺法
  • 撤销进程法（终止进程法）
  • 进程退回法