干货）"/>
操作系统复习2（超级干货）
复习资料一：操作系统复习1（超级干货）
目录
五、 调度
5.1 调度概述
5.1.1 调度类别
5.1.2 调度队列
5.1.3 CPU调度
5.1.4 调度度量（Metric）
5.2 调度算法
5.2.1 先来先服务(FCFS)
5.2.2 短作业优先(SJF)
5.2.3 优先级(PR)
5.2.4 时间片轮转(RR)
5.2.5 多级队列(MLQ)
六、 进程同步
6.1 同步机制
6.1.1 同步和互斥
6.1.2 信号量
6.2 经典同步问题
6.2.1 生产者-消费者问题
6.2.2 读者写者问题
6.2.3 哲学家就餐问题
七、 死锁
7.1 死锁概念
7.2 死锁预防
7.3 死锁避免
7.4 死锁检测恢复
五、 调度
5.1 调度概述
根据调度的粒度大小和路径长短，可以分为长程调度和短程调度。
5.1.1 调度类别
- 长程调度：又称作业调度、高级调度。将进程从“新建”状态转换到“就绪”状态。
- 短程调度：又称CPU调度、低级调度。调度程序选择下一个执行进程。
Tips : 长程与短程调度比较
| 短程 | 长程 | |
| 切换频率 | 切换频率高(milliseconds，切换快) | 切换频率低(seconds/minutes，切换慢) |
| 切换开销 | 开销小 | 开销大 |
| OS应用 | 必需 | 可选 |
- 中程调度： 又称交换，将进程在内存和外存之间换进和换出。可以节省内存空间。
5.1.2 调度队列
- 作业队列：系统中所有进程的集合。
- 就绪队列：在主内存中处于就绪状态并等待执行的所有进程集合。
- 设备队列：等待某一I/O设备的进程队列。
进程的执行过程实际上就是进程在各种队列之间的迁移。
5.1.3 CPU调度
CPU调度主要涉及进程调度或线程调度，是多任务操作系统的基础。通过多道程序设计可以得到CPU的最高利用率。进程的执行包括进程在CPU上执行和等待I/O。
CPU调度过程：
- 调度程序（Scheduler）：选择内存中的就绪进程，并分配CPU，一个CPU运行一个内存。
- 分派程序（Dispatcher）：将CPU控制权转交进程，切换上下文，切换到用户态。
分派程序过程存在分派延迟(Dispatch latency）即分派程序终止一个进程的运行并启动另一个进程运行所花的时间。
CPU调度方式：运行进程是否自愿放弃CPU
- 非抢占式调度(nonpreemptive)：一旦把CPU分配给某进程后，系统不可以抢占已分配的CPU并分配给其它进程。
优点： 易实现，调度开销小，适合批处理系统。
缺点：响应时间长，不适合交互式系统。
- 抢占式调度(preemptive): 调度程序可根据某种原则暂停某个正在执行的进程，将已分配给它的CPU重新分配给另一进程.
优点： 可防止单一进程长时间独占CPU。
缺点：系统开销大。
5.1.4 调度度量（Metric）
基本度量：
- CPU利用率 – 固定时间内CPU运行时间的比例
- 吞吐量 – 单位时间内运行完的进程数
- 周转时间 – 进程从提交到运行结束的全部时间
- 等待时间 – 进程等待调度（不运行）的时间片总和
- 响应时间 – 从进程提交到首次运行[而不是输出结果]的时间段，也就是第一段的等待时间
周转时间 = 等待时间 + 运行时间
响应时间 <= 等待时间
优化目标：
- 最大的CPU利用率、吞吐量
- 最短的周转时间、等待时间、响应时间
5.2 调度算法
5.2.1 先来先服务(FCFS)
按进程请求CPU的先后顺序使用CPU
| 进程 | P1 | P2 | P3 |
| 区间长度 | 24 | 3 | 3 |
Gantt图1
周转时间：P1：24; P2：27; P3：30；平均周转时间： (24 + 27 + 30)/3 =27
等待时间：P1：0; P2：24; P3：27； 平均等待时间: (0 + 24 + 27)/3 = 17
响应时间：P1：0; P2：24; P3：27； 平均等待时间: (0 + 24 + 27)/3 = 17
Gantt图2
周转时间: P1: 30; P2: 3; P3: 6，平均周转时间: 13
等待时间: P1: 6; P2: 0; P3: 3，平均等待时间: 3
响应时间：P1: 6; P2: 0; P3: 3，平均响应时间: 3
算法特点：
- 实现简单，可使用FIFO队列实现
- 非抢占、公平
- 对长CPU脉冲的进程有利，对短CPU脉冲的进程不利
- 适用于长程调度、后台批处理系统的短程调度
5.2.2 短作业优先(SJF)
关联到每个进程下次运行的CPU区间长度，调度最短的进程。属于非抢占式调度。
* 抢占式调度 – 发生在有比当前进程剩余时间片更短的进程到达时，也称最短剩余时间优先调度 (SRTF)
| 进程 | P1 | P2 | P3 | P4 |
| 到达时间 | 0 | 2 | 4 | 5 |
| 区间时间 | 7 | 4 | 1 | 4 |
非抢占式SJF Gantt图1
平均周转时间 = (7+10+ 4+ 11)/4 = 8
平均等待时间 = (0 + 6 + 3 + 7)/4 = 4
抢占式SJF Gantt图2
平均周转时间 = (16+ 5 +1+ 6)/4 = 7
平均等待时间 = (9 + 1 + 0 +2)/4 = 3
平均响应时间 = (0+ 0 +0+ 2)/4 = 0.5
算法特点：
- 具有最短的平均等待时间
- 存在饥饿问题
5.2.3 优先级(PR)
基于进程的紧迫程度，由外部赋予每个进程相应的优先级，CPU分配给最高优先级的进程。每个进程都有一个优先数，优先数为整数。默认小优先数具有高优先级。
| 进程 | P1 | P2 | P3 | P4 | P5 |
| 优先级 | 3 | 1 | 3 | 4 | 2 |
| 区间时间 | 10 | 1 | 2 | 1 | 5 |
PR Gantt图1
平均等待时间 = (6 + 0 + 16+18+1)/5 =8.2
优先级类型
- 静态优先级:进程创建时确定，在运行期间不变。
- 动态优先级:进程创建时的优先级随进程推进或等待时间增加而改变。
算法特点：
- 实现简单，考虑了进程的紧迫程度；灵活，可模拟其它算法。
- 饥饿 – 低优先级的进程可能永远得不到运行。可以视进程等待时间的延长提高其优先数。
5.2.4 时间片轮转(RR)
专为分时系统设计，类似于FCFS，但增加了抢占。为每个进程分配不超过一个时间片的CPU。时间片用完后，该进程将被抢占并插入就绪队列末尾，循环执行
时间片：小单位的CPU时间，通常为10-100毫秒。
假定就绪队列中有n个进程、时间片为q, 则任何一个进程的等待时间不会超过 (n-1) * q
| 进程 | P1 | P2 | P3 | P4 |
| 区间时间 | 23 | 17 | 46 | 24 |
RR Gantt图(时间片为20)
平均等待时间：(57+20+64+80)/4 = 55.25
平均响应时间: (0+20+37+57)/4= 28.5
RR的平均周转时间比SJF长，但响应时间要短
5.2.5 多级队列(MLQ)
以上算法存在局限性，如SJF有利短进程而不利长进程，RR系统开销大。所有进程采用同一策略，不合理。不同类型的进程需要不同策略，交互进程需要短的响应时间，批处理进程需要短的等待时间。多级队列调度设定系统中存在多个就绪队列，每个队列有自己的调度算法。
组成要素：队列数 | 每一队列的调度算法 | 决定新进程将进入哪个队列的方法
比如windows 系统，前台队列采用RR，后台队列采用FCFS。
六、 进程同步
当多个进程并发或并行执行时，可能存在以下两个问题。
- 每个进程可在任何时候被中断，导致仅仅进程的部分代码片段可连续执行
- 由于进程间共享数据并发/并行访问，导致数据不一致性，又称不可再现性，即同一进程在同一批数据上多次运行的结果不一样
为了解决这两个问题，OS引入了同步(互斥)机制。
6.1 同步机制
6.1.1 同步和互斥
同步：协调进程的执行次序，使并发进程间能有效地共享资源和相互合作，保证数据一致性。
互斥：互斥访问独占资源，进程排他性地运行某段代码，任何时候只有一个进程能够运行。
临界资源（Critical resource）又称互斥资源、独占资源或共享变量
一次只允许一个进程使用的资源。许多物理设备都属于临界资源，如输入机、打印机、磁带机等。
临界区(critical section)
涉及临界资源的代码段，临界区是进程内的代码，每个进程有一个或多个临界区。
若能保证诸进程互斥进入关联的临界区，可实现对临界资源的互斥访问。
Tips : 临界区使用准则
- 互斥(Mutual Exclusion) : 假定进程Pi在某个临界区执行，其他进程将被排斥在该临界区外
- 有空让进(Progress) : 临界区内无进程执行，不能无限期地延长下一个要进临界区进程的等待时间
- 有限等待(Bounded Waiting) : 每个进程进入临界区前的等待时间必须有限
6.1.2 信号量
信号量特点：
- 保证两个或多个代码段不被并发调用
- 在进入关键代码段前，进程必须获取一个信号量，否则不能运行
- 执行完该关键代码段，必须释放信号量
- 信号量有值，为正说明它空闲，为负说明其忙碌
信号量操作：
- P执行的是信号量-1；V执行的是信号量+1
- P(S)：申请一个资源（阻塞）；V(S)：释放一个资源（唤醒）
- P、V操作成对出现
int S = 1; //S必须置一次且只能置一次初值,除了初始化，只能通过执行P、V操作来访问S
wait(S): //P(S)while s<=0: do no-op;S--;
signal(S): //V(S)S++;
信号量类型：
- 计数信号量：没有限制的整型值0-N，计数信号量=同步信号量。
- 二值信号量：仅限于0和1的信号量，二值信号量=互斥信号量
6.2 经典同步问题
进程同步主要可分为三个内容：共享有限缓冲区、数据读写操作、资源竞争。
三个内容分别对应：生产者-消费者问题、读者写者问题、哲学家就餐问题。
6.2.1 生产者-消费者问题
问题描述：生产者（M个）：生产产品，并放入缓冲区。消费者（N个）：从缓冲区取产品消费。
如何实现生产者和消费者之间的同步和互斥？
互斥分析：
| 生产者 | 消费者 | |
| 目标 | 把产品放入指定缓冲区 | 从指定缓冲区取出产品 |
| 临界资源操作 | in:所有的生产者对in指针需要互斥 counter：所有生产者消费者进程对counter互斥 | out:所有的消费者对out指针需要互斥 counter：所有生产者消费者进程对counter互斥 |
同步分析：
- 生产者：把产品放入指定缓冲区（关键代码C1）
- 消费者：从满缓冲区取出一个产品（关键代码C2）
缓冲区空时：先C1后C2；缓冲区满时：先C2后C1；其余时刻，C1C2可以并发执行。
semaphore *full, *empty, *m; //full:满缓冲区数量 empty：空缓冲区数量
//初始化
full->value = 0；
empty->vaule = N;
m->vaule = 1；def producer{...生产一个产品...wait(empty); //当empty大于0时，表示有空缓冲区，继续执行；否则，表示无空缓冲区，当前生产者阻塞wait(m);...C1：把产品放入指定缓冲区...signal(m);signal(full); //把full值加1，如果有消费者等在full的 队列上，则唤醒该消费者
}def consumer{wait(full)；//当full大于0时，表示有满缓冲区，继续执行；否则，表示无满缓冲区，当前消费者阻塞wait(m);...C2：从指定缓冲区取出产品...signal(m);signal(empty); //把empty值加1，如果有生产者等在empty的队列上，则唤醒该生产者...消费取出的产品...
}6.2.2 读者写者问题
问题描述：两组并发进程，共享一组数据区进行读写。要求满足允许多个读者同时读；不允许读者、写者同时读写；不允许多个写者同时写。
原则：读者优先
读者：无写者，读者可读；有写者等，读者可读。有写者写，读者等
写者：有读者，写者等。有写者，新写者等。
Semephore *W; //W为内容
W->value=1;int rc = 0; //读者计数器rc，设置初始值为0
int M = 1; //互斥信号量M，设置初始值为1；def readers{P(M); //开始读，M-1rc++; //计数器+1if (rc==1) P(W); //第一个读者V(M); //释放区域，M+1读P(M);rc--;If (rc==0) V(W); //最后离开的读者V(M);
}def writer{P(M); //开始写，M-1写V(M); //释放区域，M+1
}6.2.3 哲学家就餐问题
问题描述：n个哲学家、n根筷子，每个哲学家左右各有一根筷子，每个哲学家只有拿起左右两个筷子才能吃饭。
每个哲学家同时执行P，拿起左边筷子，导致死锁。
解决措施：
方法1：最多允许4个哲学家同时坐在桌子周围
方法2：仅当一个哲学家左右两边筷子都可用时，才允许他拿筷子
方法3：给所有哲学家编号，奇数号哲学家必须首先拿左边筷子，偶数号哲学家则反之
//方法1-最多4个哲学家入座
semephore *chopstick[5]; //初始值为1
semaphore *seat; //初始值为4def philosopher{P(seat); //看看4个座位是否有空P(chopStick[i]); //拿左边筷子P(chopStick[(i + 1) % 5]); //拿右边筷子吃饭V(chopStick[i]); //放下左边筷子V(chopStick[(i + 1) % 5]); //放下右边筷子V(seat); //释放占据的位置
}//方法2 –同时拿筷子
int *state={Thinking, hungry, eating}; //哲学家分为3个状态
semaphore *ph[5]; //设置5个信号量，对应5个哲学家,初始值为0void test(int i);{if (state[i] == hungry) && //是否饿了(state[(i+4)%5]!=eating) && //左边哲学家是否在吃饭(state[(i+1)%5]!=eating) //右边哲学家是否在吃饭{state[i]=eating; //设置哲学家状态为eatingV(ph[i]); //ph[i]设置为1} }
七、 死锁
7.1 死锁概念
一组等待的进程，其中每一个进程都持有资源，并且等待着由这个组中其他进程所持有的资源。
死锁原因：竞争互斥资源、进程推进不当
Tips ： 死锁特征
- 互斥：一次只有一个进程可以使用一个资源
- 占有并等待：一个至少持有一个资源的进程等待获得额外的由其他进程所持有的资源
- 不可抢占：一个资源只有当持有它的进程完成任务后，自由的释放
- 循环等待：等待资源的进程之间存在环 {P0, P1, …, P0}。P0 等待P1占有的资源, P1等待P2占有的资源, …, Pn–1等待Pn占有的资源, Pn等待P0占有的资源
资源申请方式：
- 资源动态申请：在进程运行过程中申请资源
- 资源静态申请：在进程运行前一次申请所有资源
资源分配图
一个顶点的集合V和边的集合E
V被分为两个部分
- P = {P1, P2, …, Pn}, 含有系统中全部的进程
- R = {R1, R2, …, Rm}, 含有系统中全部的资源
- 请求边：有向边Pi -> Rj
- 分配边：有向边Ri -> Pj
| 含义 | 进程 | 有四个实例的资源类型 | Pi 请求一个Rj的实例 | Pi 持有一个Rj的实例 |
| 图例 |
如果图没有环，那么不会有死锁。
如果图有环：
- 每一种资源类型只有一个实例，那么死锁发生。
- 如果一种资源类型有多个实例，可能死锁。
处理死锁的方法
-
确保系统永远不会进入死锁状态：死锁预防、死锁避免
-
允许系统进入死锁状态检测并恢复：死锁检测、死锁恢复
7.2 死锁预防
死锁预防抑制死锁发生的必要条件，即确保至少一个必要条件（互斥、占有并等待、非抢占、循环等待）不成立。
1.破坏互斥：
- 共享资源，不涉及死锁
- 非共享资源（互斥资源），必须要有互斥条件
- 现代操作系统中的虚拟化技术，将互斥资源改造为共享资源
如系统存在互斥资源，不能改变这个条件来预防死锁。
2.破坏占有并等待：
- 静态分配策略
- 要求进程在执行前一次性申请全部的资源，只有没有占有资源时才可以分配资源
3.破坏非抢占：
- 如果一个进程的申请没有实现，它要释放所有占有的资源
- 先占的资源放入进程等待资源列表中
- 进程在重新得到旧的资源的时候可以重新开始
4.破坏循环等待 ：
- 对所有的资源类型排序进行总排序，并且要求进程按照递增顺序申请资源。
7.3 死锁避免
死锁避免建立在系统进程整体信息上，具体要求如下：
- 要求每一个进程声明它所需要的资源的最大数
- 死锁避免算法动态检查资源分配状态以确保循环等待条件不可能成立
- 资源分配状态定义为可用的与已分配的资源数，和进程所需的最大资源量所决定
如果一个系统在安全状态，就没有死锁。如果一个系统不是处于安全状态，就有可能死锁。死锁避免确保系统永远不会进入不安全状态。
单实例资源：使用资源分配图法
假设 Pi 申请资源 Rj，请求能满足的前提是：把请求边转换为分配边后不会导致环存在。
多实例资源：银行家算法
| Available | 长度为m的向量。 如果available[j]=k,那么资源Rj有k个实例有效 |
| Max | n x m 矩阵 如果Max[i,j]=k,那么进程Pi最多可以请求k个资源Rj的实例 |
| Allocation | n x m 矩阵 如果Allocation[i,j]=k,那么进程Pj当前分配了k个资源Rj的实例 |
| Need | n x m 矩阵 如果Need[,j]=k,那么进程Pj还需要k个资源Rj的实例 |
| Need [i,j] = Mx[i,j] – Allocation [i,j] | |
// 定义全局变量
int Available[m]; // 系统中可用资源向量，m是资源类型数目
int Allocation[n][m]; // 已分配资源矩阵，n是进程数目，m是资源类型数目
int Need[n][m]; // 需求资源矩阵，n是进程数目，m是资源类型数目
int Requesti[m]; // 进程 Pi 的资源请求向量// 是否满足进程Pi的资源请求算法
bool requestResource(int Pi) {// Step 1: 检查请求是否合理bool validRequest = true;for (int j = 0; j < m; j++) {if (Requesti[j] > Need[Pi][j]) {validRequest = false;break;}}if (!validRequest) {// 进程请求超出了其声明的最大值，报错return false;}// Step 2: 检查系统是否有足够资源可供分配bool enoughResources = true;for (int j = 0; j < m; j++) {if (Requesti[j] > Available[j]) {enoughResources = false;break;}}if (!enoughResources) {// 资源不足，进程 Pi 必须等待return false;}// Step 3: 分配资源给进程 Pifor (int j = 0; j < m; j++) {Available[j] -= Requesti[j];Allocation[Pi][j] += Requesti[j];Need[Pi][j] -= Requesti[j];}// 检查系统是否安全if (isSafe()) {return true; // 资源分配成功} else {// 系统不安全，恢复原有的资源分配状态for (int j = 0; j < m; j++) {Available[j] += Requesti[j];Allocation[Pi][j] -= Requesti[j];Need[Pi][j] += Requesti[j];}return false; // 资源分配失败}
}bool Finish[n]; // 完成状态数组，n是进程数目// 安全算法定义
bool isSafe() {int Work[m];for (int i = 0; i < m; i++) {Work[i] = Available[i];}for (int i = 0; i < n; i++) {Finish[i] = false;}for (int i = 0; i < n; i++) {if (Finish[i] == false && checkNeedWork(i, Work)) {for (int j = 0; j < m; j++) {Work[j] += Allocation[i][j];}Finish[i] = true;i = -1; // 重新从第一个进程开始检查}}for (int i = 0; i < n; i++) {if (Finish[i] == false) {return false; // 存在未完成的进程，系统处于不安全状态}}return true; // 所有进程都完成，系统处于安全状态
}bool checkNeedWork(int i, int Work[]) {for (int j = 0; j < m; j++) {if (Need[i][j] > Work[j]) {return false; // 进程 i 的需求大于可用资源，无法分配}}return true; // 进程 i 可以完成
}7.4 死锁检测恢复
维护等待图: 节点是进程 ; Pi->Pj表明Pi在等待Pj。
定期调用算法来检查是否有环。一个检查图中是否有环的算法需要n2的操作来进行，n为图中的节点数。以下为检测算法的实现：
// 初始化向量
int Work[m]; // m 是资源类型数目
bool Finish[n]; // n 是进程数目// (a) Work = Available
for (int i = 0; i < m; i++) {Work[i] = Available[i];
}// (b) 设置 Finish[i] 标志
for (int i = 0; i < n; i++) {if (Allocation[i] != 0) {Finish[i] = false;} else {Finish[i] = true;}
}// 死锁检测，找到满足死锁的下标i，算法需要m x n^2 次操作来判断是否系统处于死锁状态
int i = 0;
while (i < n) {if (Finish[i] == false && checkRequestWork(i)) {// (a) Requesti <= Workfor (int j = 0; j < m; j++) {Work[j] += Allocation[i][j];}// (b) Finish[i] = trueFinish[i] = true;i = 0; // 重新从第一个进程开始检查} else {i++;}
}// 检查是否存在死锁
bool deadlock = false;
for (int i = 0; i < n; i++) {if (Finish[i] == false) {deadlock = true;break;}
}if (deadlock) {// 存在死锁// 标记相应的进程 Pi 为死锁
}
死锁恢复：
- 人工恢复：通知操作员，人工处理
- 自动恢复：终止进程抢占资源，可以选择一个牺牲品或者回滚到安全状态
- 进程终止：中断所有的死锁进程或者一次中断一个进程直到死锁环消失
复习资料三：操作系统复习3
复习资料四：操作系统复习4
更多推荐
操作系统复习2（超级干货）
发布评论