期末复习重点总结
可移步专栏阅读查看其他相关内容
标题正文为学习要点，已省略。文本框详细内容为期末复习重点。
目录
- 期末复习重点总结
- 第1章-操作系统引论
- 1.1 操作系统的目标和作用
- P2 操作系统的目标：
- 1.2 操作系统的发展过程
- P9 OS定义：
- 1.3 操作系统的基本特性
- P15 四个基本特性：
- 1.4 操作系统的运行环境
- 1.5 操作系统的主要功能
- 第2章-进程的描述与控制
- 2.1 前趋图和程序执行
- P43 进程和程序的区别:
- 2.2 进程的描述
- P45 进程的基本状态与转换
- P48 PCB的作用
- 2.3 进程控制
- 2.5 线程的概念
- 第3章-处理机调度与死锁
- 3.1 处理机调度概述
- P74 三级调度
- 3.2 调度算法
- P79 短作业优先算法(SJF)、优先级调度算法(PR)、先来先服务优先算法(FCFS)
- 1） 短作业优先算法（非抢占式）
- 2） 短作业优先算法（抢占式）
- 3） 优先级调度算法：
- 4） 先来先服务优先算法
- 【补：多级反馈队列算法】
- 3.5 死锁概述
- P95 死锁定义，产生的必要条件
- 3.6 死锁预防
- 3.7 死锁避免
- 3.8 死锁的检测与解除
- P96 死锁的处理方法
- P99 资源分配安全状态
- P101 银行家算法
- 银行家算法的例子
- 第4章-进程同步
- 4.1 进程同步的基本概念
- 4.2 软件同步机制
- 4.3 硬件同步机制
- 4.4 信号量机制
- P117 信号量的定义
- 信号量的物理意义
- 利用信号量实现的前驱关系
- 4.6 经典的进程同步问题
以下是本篇文章正文内容
第1章-操作系统引论
1.1 操作系统的目标和作用
P2 操作系统的目标：
- 方便性
通过OS命令操纵计算机，方便用户- 有效性
提高系统资源的利用率 * 提高系统吞吐量- 可扩充性
OS必须具有很好的可扩充性
与OS的结构有紧密联系- 开放性
遵循世界规范标准。特别是开放系统互连OSI
1.2 操作系统的发展过程
P9 OS定义：
OS是一组能有效地组织和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序的集合。
1.3 操作系统的基本特性
P15 四个基本特性：
并发：
并行： 两个或多个事件在同一时刻发生。
并发： 两个或多个事件在同一时间间隔内发生。
在多道程序环境下，并发 是指在一段时间内宏观上有多个程序同时在运行,但在单处理机系统中，每一时刻仅能有一道程序执行，故在微观上这些程序只能分式交替执行。
共享：
系统中的资源可供那些中多个并发执行的进程共同使用。
互斥共享方式（临界资源）
同时访问方式
在一段时间内只允许一个进程访问的资源，称为临界资源（或独占资源）
虚拟：
时分复用技术：虚拟处理机、虚拟设备（提高时间上的利用率）
空分复用技术：虚拟存储（提高空间的利用率）
异步：
进程的异步性：进程是以人们不可预知的速度向前推进的
1.4 操作系统的运行环境
1.5 操作系统的主要功能
计算机操作系统（慕课版）第1章-操作系统引论
第2章-进程的描述与控制
2.1 前趋图和程序执行
P43 进程和程序的区别:
进程是指一个具有一定独立功能的程序关于某个数据集合的一次运行活动，是系统运行程序的基本单位，因此进程是动态的。
程序是指令的有序集合，被存储在磁盘或其他的数据存储设备中，是一个静态概念，其本身没有任何运行的含义。
1） 程序是静态的，进程是动态的。
2） 程序可以作为一种软件资料长期保存，进程是有一定生命周期，它能够动态的产生和消亡。
3） 进程是一个能独立运行的单位，能与其他进程并行活动
4） 进程是竞争计算机系统有限资源的基本单位，也是进行处理机调度的基本单位。
5） 进程与程序之间无一一对应关系。不同的进程可以包含同一程序，同一程序再执行中也可以产生多个进程。
6） 程序是记录在记录在介质上指令的有序集合，而进程是由程序、数据和进程控制块3部分组成。
2.2 进程的描述
P45 进程的基本状态与转换
3种基本状态
运行态：占有CPU，并在CPU运行。
就绪态：已具备运行的条件，但由于没有空闲的CPU而暂时不能运行。
阻塞态：因等待某一事件而暂时不能运行
_____________________________________________________________________________…
3种基本状态转换
创建态——>就绪态：系统完成创建进程的一系列工作。（处理机 × ，其他 √）
就绪态——>运行态：进程被调度。（处理机 √，其他 √）
运行态——>就绪态：时间片到货处理机被抢占。
运行态——>终止态：进程运行结束或运行遇到不可修复的错误。
运行态——>阻塞态：进程用“系统调用”的方式申请某种资源或请求等待某个事件发生。（处理机×，其他 ×）
阻塞态——>就绪态：申请的资源被分配或等待事件发生。
5种基本状态转换
P48 PCB的作用
PCB的作用是使一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位，即一个能与其它进程并发执行的进程。
PCB 已成为进程存在于系统中的唯一标志
1） 作为独立运行基本单位的标志，PCB是进程创建的唯一标准。
2） 实现间断性运行方式
3） 提供进程管理所需要的信息
4） 提供进程调度所需要的的信息
5） 实现与其他进程的同步与通信
【注：引起进程调度的原因】
1） 进程结束
2） 时间片用完
3） 被抢占
4） 调用原语被阻塞
5） I/O请求
2.3 进程控制
2.5 线程的概念
第3章-处理机调度与死锁
3.1 处理机调度概述
P74 三级调度
1）高级调度：
调度对象为作业。根据某种算法，决定将外存上处于后备队列中的作业调入内存，并为它们创建进程和分配必要的资源。然后，将新创建的进程排在就绪队列上等待调度。主要用于多道批处理系统中
2）中级调度：
将暂不运行的进程，调至外存等待;将处于外存上的急需运行的进程，调入内存运行。即“对换”功能
3）低级调度：
调度对象为进程。根据某种调度算法，决定就绪队列中的哪个进程应获得处理机。应用在于多道批处理、分时和实时OS。
3.2 调度算法
P79 短作业优先算法(SJF)、优先级调度算法(PR)、先来先服务优先算法(FCFS)
【☆记忆公式☆】
既要考虑到作业的等待时间，也要考虑作业的运行时间
优先级： 优先级=（等待时间+要求服务时间）/要求服务时间`
响应比： 响应比 =（等待时间+要求服务时间）/要求服务时间=响应时间/要求服务时间
如等待时间相同，运行时间越短，类似于SJF
如运行时间相同，取决于等待时间，类似于FCFS
长作业可随其等待时间的增加而提高，也可得到服务
缺点：每次调度之前，都需要计算响应比，增加系统开销
开始时间 = 前一个进程完成的时间
结束时间 = 前一个进程的完成时间+现在的进程的服务时间
周转时间 = 完成时间 – 到达时间
带权周转时间 = 周转时间/服务时间
1） 短作业优先算法（非抢占式）
2） 短作业优先算法（抢占式）
3） 优先级调度算法：
4） 先来先服务优先算法
【补：多级反馈队列算法】
非抢占
抢占
3.5 死锁概述
P95 死锁定义，产生的必要条件
死锁的定义：
如果一组进程中的每个进程都在等待仅由该组进程中的其他进程才能引发的事件发生，那么该组进程是死锁的。
产生死锁的原因:
（1）竞争资源 （2）进程间推进顺序非法
产生死锁的四个必要条件
（1）互斥条件
（2）请求和保持条件
（3）不可抢占条件
（4）循环等待条件
3.6 死锁预防
3.7 死锁避免
3.8 死锁的检测与解除
P96 死锁的处理方法
死锁处理的四个方法
（1）预防死锁
（2）避免死锁
（3）检测死锁
（4）解除死锁
【预防死锁就是破坏死锁的四个必要条件中的一个或多个】
P99 资源分配安全状态
所谓安全状态：
是系统能按某种进程推进顺序，为每个进程分配所需资源，知至满足每个进程对资源的最大需求，进而使每个进程都可以顺利完成的一种系统状态。
【资源竞争问题★★★★★（经典算法）】
假如有多个进程争夺一种资源，这个资源共有n个，每个进程需要这种资源m个，并且每个进程当得到某一个资源之后不会直到执行完成都不会释放这个占有的资源，只有这个进程的需求得到满足之后他才会执行完成，那么问最多有多少个这样的进程争夺这m个资源，一定不会发生死锁？
[分析]
这个问题的简化版本是哲学家问题，哲学家问题是说有n个餐具，每个哲学家需要2个餐具才能用餐，问最多可以有多少个哲学家，才能保证每个哲学家能够用餐完成。
我们可以考虑有m个哲学家围成一圈，按顺序给每个哲学家分一个餐具，假如每个哲学家都分到了一个餐具，这个时候餐具还有剩余，那么对于m个哲学家而言，他们一定能够用餐完成。
也就是说只要n > m * （2 – 1） ，那么对于这m个哲学家，他们一定能够用餐完成，当n < m * 1，的时候，有可能出现哲学家不能用餐完成，循环等待的情况，也就是说最多可以有n – 1个哲学家用餐。
【解答】
再回到题目的问题，假如餐具有n个，每个哲学家需要m个餐具，有t个哲学家，那么当n > t *（m – 1）的时候，不会出现循环等待，那么同理，当n % (m–1) !=0的时候，最多有n / (m–1)个哲学家，当n % (m–1) == 0的时候，最多有n / (m–1)–1个哲学家。
至少需要m个； m>4*(3-1)=8 即m最小是9 ；选择C
仅仅需要满足：8≤k*(3-1) 解得K=4；选择C
关于临界资源分配的一道题
P101 银行家算法
为了实现银行家算法，必须在系统中设置4个数据结构，分别描述：
系统中可利用的资源，所有进程对资源的最大需求、系统中的资源分配情况以及所有进程还需要多少资源：
1） 可利用资源向量Available。
这是一个含有m个元素的数组，其中的每一个元素代表一类可利用资源数目，其初值是系统中所配置的该类全部可用资源数目。该数目会随对应资源的分配和回收而动态改变。如果Available[j]=K,则表示系统中现有Rj类资源K个。
2）最大需求矩阵Max。
这是一个n×m的矩阵，它定义了系统中n个进程中的每个进程对m类资源的最大需求。如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K。
3） 分配矩阵Allocation。
这是一个n×m的矩阵，它定义了系统中每类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K,则表示进程i当前已分得Rj类自愿的数目为K。
4） 需求矩阵Need。
这是一个n×m的矩阵，用于表示每个进程尚需的各类资源数。如果Need[i,j]=K,则表示进程i还需要Rj类资源K个方能完成其任务。
上述3个矩阵间存在下列关系：
Need[i,j] = Max[i,j] – Allocation[i,j]。
银行家算法的操作流程：
设Requesti是进程Pi的请求向量，如果Request[j]=K,则表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统会按下列步骤进行检查。
（1） 如果Requesti[j]≤Need[i,j],则转向步骤（2）；否则认为出错，因为它所需要得资源数已超过它所宣布的最大值。
（2） 如果Requesti[j]≤Need[i,j],则转向步骤（3）；否则表示尚无足够资源，Pi须等待。
（3） 系统试探着把资源分配给进程Pi，并修改下列数据结构中的数值：
Available[j] = Available[j] – Requesti[j];
Allocation[i,j] = Allocation[i,j] + Requesti[j]
Need[i,j] = Need[i,j] – Requesti[j]
（4） 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。
若是，则正式资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。
银行家算法的例子
第4章-进程同步
4.1 进程同步的基本概念
人们把每个进程中访问临界资源的那段代码称为临界区。
4.2 软件同步机制
4.3 硬件同步机制
4.4 信号量机制
P117 信号量的定义
所谓信号量是一个确定的二元组( s,q），其中s是一个具有非负初值的整型变量，q是一个与s相关的队列。对信号量s除了赋初值以外，只能通过两个原子操作P、V操作来改变它的值。
信号量的物理意义
当信号星值大于等于零时，表示可用资源的数目;
当信号星值小于零时，其绝对值表示因请求该资源要求未被满足而被阻塞的进程数目。
利用信号量实现的前驱关系
设定初值为0的公用信号量S
对于每一对前驱关系
在直接后继的前面增加P(S)
在直接前驱的后面增加V(S)
补充：
4.6 经典的进程同步问题
设有一桌子上有个能盛下五个水果的空盘子。爸爸不停地向盘子中放苹果或桔子，儿子不停地从盘中取出桔子享用，女儿不停地从盘中取出苹果享用。规定三人不能同时从盘子中取放水果。请用信号量和P、V操作来实现爸爸、儿子、女儿这三个进程间的同步与互斥关系。
解答：苹果橘子问题
- Authors
- 杜小白