操作系统概览
操作系统是一套控制应用程序执行的程序，它是应用程序与计算机硬件之间的接口，是计算机资源的管理者。
操作系统的特征： 并发、共享、虚拟、异步 。 其中 并发、共享 是最基本的两个条件。
并发：交替发生，宏观上同时发生。
并行：同时发生，微观上同时发生。
共享: 系统中的资源可被多个进程共同使用。
1.互斥共享: 摄像头
2.同时共享: 网卡、硬盘
并发 和 共享 相辅相成。
虚拟: 把物理上的实体映射为逻辑上的。比如虚拟内存， 虚拟技术中的 “时分复用技术”。
异步：在多道程序下，由于资源有限，进程无法一直执行到底，以不可预知的速度向前推进，这就是异步行。
操作系统的发展和分类
1.手工操作阶段，串行执行：
`问题`： IO 太慢 CPU 太快，用户独占权。只能 1 个用户2.单道批处理程序
把 IO 预先存进一个磁带（快一些），然后降低速度差异。
问题：还是单用户。
3.多道批处理程序
引入了中断机制，操作系统正式诞生，实现了并发执行
问题：无人机交互，中途不能控制自己的作业（分时操作系统解决了这个问题）
4.分时操作系统
计算机以时间片为单位轮流服务用户，有人机交互。
问题： 有些任务比较紧急，无法调度。
4.实时操作系统
对有些重要的进程给与 优先权。可以优先响应紧急任务。
1.硬实时，时间固定 （导弹）
2.软实时，时间不固定 （火车票预订）
系统调用
系统调用是 操作系统为用户和硬件之间设计的接口，向上提供服务，分为 命令接口、程序接口。
通过使用 系统调用 使用的资源是安全的，是被操作系统支配的。
系统调用需要进入 核心态。 通过中断指令来完成。比如 Linux Int 2 （ 2 号内中断） 代表创建一个进程。
系统调用的中断是在 用户态 执行的，中断 之后就进入 核心态， 核心态唯一 不能执行 的就是 中断指令
系统调用与一般函数库的区别：库函数比较高级，有的会调用系统调用，它是对系统调用的封装。
操作系统的运行机制
指令与数据在内存都是一样。
特权指令， 必须在 核心态（管态） 内核程序都运行在核心态。
一般指令， 用户态（目态） 一般程序执行在用户态。
宏内核 （大内核） 许多操作在核心态完成，效率高。 不切换状态性能好。
微内核（小内盒） 如系统过于庞大 WIndows ，微内核易维护。 不断地在 用户态和核心态切换，性能低
中断
分时操作系统通过中断来实现并发，只要中断发生，就意味着需要操作系统介入，展开管理工作。
中断发生，进入核心态。（切换到核心态的 唯一途径 ）
中断发生，当前进程暂停，操作系统内核介入。
中断发生,对于不同的中断信号，操作系统内核给与不同的处理。
进程
进程实体是静态的 进程是动态的。
程序就是一个指令序列， PCB + 程序段 + 数据段 组成了 进程实体（进程映像）， PCB 石金成存在的唯一标志。
1.进程是程序的一次执行过程
2.进程是程序和数据在处理机上按顺序发生的活动
3.进程是操作系统调度的一个单位，是具有独立功能的运行的过程
执行指针唯一，指向正在执行
就绪队列指针，
阻塞指针，
动态性，进程是程序执行的一次过程，是动态的产生并消亡的。
并发性，内存中同时存在多个实体。个进程轮流使用CPU 资源
独立性，个进程资源独立，进程是接受资源的最基本单位
异步行，各进程推进速度不可预知
结构性，必须有 PCB
进程的状态转换：
1.运行态（每核唯一）、
2.就绪太、 具备运行的可能，等待 CPU 分配时间，就差 CPU 了。
3.阻塞太（等待态）、 等待某种资源。
-
创建态、操作系统为其分配资源。
- 终止态 回收，移除 PCB。
从运行态 -> 阻塞态 是主动行为。
阻塞态 -> 就绪态 资源到位
就绪态不能直接到阻塞态，因为需要CPU 资源才能将其转为阻塞态。
· 进程如何切换：
进程状态写在 PCB 中，修改进程 PCB 用的是 原语，进行中无法被中断。
原语使用 开中断、关中断。 不可屏蔽中断。 运行在核心态。
1.进程控制原语一定会改变程进程的状态标志。
2.需要保存被剥夺CPU 资源的进程的运行环境 到 PCB
3.新进程开始要回复他的环境。。
进程通信
共享方式：互斥的。 （P、V 操作）
管道方式： 半双工通信， 各进程互斥使用管道。
写不满不能读，读不空不能写 （阻塞）
消息队列传递：
总结：
线程
线程控制块 TCB 也有，线程没有系统资源。
APP 发展比较复杂，一个软件 需要 多种功能。 资源 如 打印机 是分配给进程的，但 CPU 时间 可以按线程分配。
线程可以理解为 “轻量级的” 进程。
进程是操作系统分配资源的单位，但如果有多线程，CPU 轮流为线程服务。
没有线程 进程是最小单位，有了线程，线程是最小。
线程 2 分两种， 用户级线程、内核级线程。
用户级线程是通过应用程序来调度的，不用切换至内核态。
重点！ 内核级别线程 才是操作系统分配的单位。
内核级别线程 可以映射 到用户级别线程上。
1：N 或者 N:M
1:N 的问题，当一个用户线程被阻塞后，他的内核线程也会被阻塞，并行度不高。
考点：
处理机调度
调度的目的是 合理的分配资源。必行不是平均分配的，
从 就绪队列中按照一定算法 ，选择一个进程，并送给 CPU 执行。
高级调度， （作业调度） 创建、销毁时的调度。（当一次载入了很多作业，并不是所有作业都能立即创建进程参与竞争资源）。
中级调度， （内存调度） 内存空间有限， 不能将所有任务都放入内存，一般讲挂起的放入外存。 会发生多次。
低级调度，（进程调度） 就绪队转为执行状态。
挂起是说进程被送入外存， 就绪态 和 阻塞态 都很有可能转为 挂起。
低级调度（进程调度）
主动放弃，被动放弃
进程在 操作系统内核临界区临界区时，不能调度 。内核程序的临界区 有可能访问的是一种内核数据结构比如就绪队列，当访问前要上锁。如果这时候切换了，无法进行下去。
普通进程在临界区内 是可以调度的。
广义的进程调度，包括选择一个进程 和切换一个进程 2 部分。
非剥夺式（非抢占式） 只允许进程主动放弃处理机。
剥夺式 （抢占式）
调度算法
- cpu 利用率
cpu 忙碌的时间 / 总时间
- 系统吞吐量
单位时间内完成了多少作业
总作业 / 总时间
- 周转时间
作业被提交后，到被处理完毕的时间
作业完成时间 - 提交时间
平均周转时间
作业时间之和 - 作业数量
带权周转时间
作业周转时间 / 实际的运行时间
（作业完成时间 - 作业提交时间） / 作业实际运行时间
- 等待时间
作业被等待的时间之和。
- 响应时间
从用户提交请求，到被响应的时间
调度算法
- 先来先服务 （FCFS） 常作业有利，短作业不利。
- 短作业优先 （SJF） （非抢占）
2.1 剩余最短时间优先 （默认抢占） 每当新任务来临，从新排序所有任务的剩余时间，按第一个取。
- 高响应比 （非抢占式）
（等待时间 + 处理时间）/处理时间
高响应比越大 越优先处理
以上 3 中一般适用于早期的 批处理系统
交互式调度算法
- 时间片轮转算法 （RR）
公平轮流的的为每个进程服务，分时操作系统。 时间片结束，放入 就绪队列 队头。
时间片太大，退化 先来先服务
时间片太小，进程切换负担比例太重。
- 优先级调度算法 （带有 优先级）
有抢占式，也有非抢占式，
非抢占式 当进程结束时，查看任务队列中那个任务优先级最高。
抢占式，当新进程进入，立即判断是否有比目前进程更高优先级的进程
优先级 静态优先 动态优先。
- 多级反馈队列
新来的进程 放入 1 队列，如果 n 次 都运行不完，则越来越靠后。
管程 （V、P）
在管程以前，使用信号量实现同步，或互斥。
1.局部与管程的共享数据说明
2.对数据机构的一组过程
3.设置初始化。
4.名字
进程同步
同步，也称为 直接制约关系， 要确定工作顺序。
临界资源：互斥的，每次只能一个进程来访问。
临界区资源访问的代码。
进入、退出 区 负责实现互斥。
1.空闲让进
2.忙则等待
3.有限等待 、不饿死
4.让权等待、不能进临界区，应该立刻释放处理机
进程互斥 （软件实现）
1.单标志法。
在进入临界区后，会把权限交给另一个进程，也就是说，每个进程进入临界区的权限只能被另一个进程赋予。
单标志法：违背了 空闲让进，如果 P0 不上处理机，则 P1 饥饿。
- 双标志先检查 （先检查 后上锁）
保存数组，保存进程是否想要进入临界区的 意愿 。
双标志先检查：违背 忙则等待。 （进程切换）
- 双标志后检查 （先上锁 后检查）
双标志后检查：违背 饥饿
- 皮特森算法
如果双方都想进入临界区，则优先让别人进入。
皮特森算法：违背 让权等待，必须一致 while 循环卡在那。
进程互斥的硬件实现 （硬件实现）
1.中断屏蔽方法 （适用于内核进程、高危指令）
利用开关中断，原语就是如此方式。单处理及使用。
简单高效。
但多核机器不行
- Test And Set (TSL)
TSL 指令是硬件实现的 不允许被中断。
不满足 让权等待。
- swap Exchange 指令
同上，也是硬件实现，不能中断。
信号量机制
一个信号量，可以表示某种资源的数量。
原语：操作系统提供的，不能被中断的程序。
wait、signal 原语 简称 P、V 操作
- 整形信号量
用一个整数表示某种资源数量。 问题是忙等
- 记录型型号量，解决了忙等。 重点
总结：
信号量互斥
资源为 1 时，可以实现互斥。
同步：有执行顺序要求。 反过来使用 VP 操作可实现。
设置一个 0 的信号量,
生产者消费者
缓冲区是临界资源，只能一个进程访问。
缓冲区满，生产者阻塞。 缓冲区空，消费者阻塞。
互斥的 P 一定在在 同步的 P 之后。
多生产者，多消费者：
如果资源大于 1 则必选配一个 互斥信号量。
吸烟者问题：
文件读写：
哲学家吃饭问题:
死锁 银行家算法
安全序列，系统分配资源，能够找出一个 安全序列 ，使得每个进程都可以完成，则系统是安全状态 安全序列 可能有多个。
不安全状态。
死锁的检测和解决
1.检测死锁：
用一种数据结构保存资源分配信息
提供一种算法，检测是否进入死锁状态。
解决死锁：
-
资源剥夺法： 剥夺进程的资源，
-
撤销进程法： 高成本
-
进程回退法： 需要记录
死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。
饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。比如：在短进程优先（SPF）算法 中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程“饥饿”。
死循环：某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑 bug 导致的，有时是 程序员故意设计的。
死锁产生的条件
互斥、不剥夺、请求和保持、循环等待。
发生死锁一定有循环等待，发生循环等待不一定发生死锁。
什么时候发生死锁：
-
对系统资源的竞争。各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资 源（CPU）的竞争是不会引起死锁的。
-
进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程P1、 P2 分别申请并占有了资源 R1、R2，之后进程P1又紧接着申请资源R2，而进程P2又申请资源R1， 两者会因为申请的资源被对方占有而阻塞，从而发生死锁。
- 信号量的使用不当也会造成死锁。如生产者-消费者问题中，如果实现互斥的P操作在实现同步的 P操作之前，就有可能导致死锁。（可以把互斥信号量、同步信号量也看做是一种抽象的系统资 源）
死锁的处理策略：
-
预防死锁。破坏死锁产生的四个必要条件中的一个或几个。
-
避免死锁。用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）
- 死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措 施解除死锁。
解决：
- 破坏互斥条件 SPOOLing 技术，将设备改造成共享设备。
不安全，且不是所有设备都能改造
- 破坏不剥夺条件。
- 破坏请求保持。 饥饿
- 破坏循环等待
