操作系统知识点整理笔记（二）

CPU利用率：指CPU忙碌的时间占总时间的比例。
系统吞吐量：单位时间内完成作业的数量（ $\frac{ 总共完成了多少道作业}{总共花了多少时间}$ ）。
周转时间：从作业被提交给系统开始，到作业完成为止的这段时间间隔。它包括四个部分：作业在外存后备队列上等待作业调度（高级调度）的时间、进程在就绪队列上等待进程调度（低级调度）的时间、进程在CPU上执行的时间、进程等待I/O操作完成的时间。后三项在一个作业的整个处理过程中，可能发生多次。
- 作业周转时间=作业完成时间-作业提交时间。
- 平均周转时间= $\frac{各作业周转时间之和}{作业数}$ 。
- 带权周转时间= 。
  - 对于周转时间相同的两个作业，实际运行时间长的作业在相同时间内被服务的时间更多，带权周转时间更小，用户满意度更高。
  - 对于实际运行时间相同的两个作业，周转时间短的带权周转时间更小，用户满意度更高。
  - 带权周转时间必然大于或等于1，带权周转时间与周转时间都是越小越好。
- 平均带权周转时间= $\frac{ 各作业带权周转时间之和}{作业数}$ 。
等待时间：指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低。

响应时间：指从用户提交请求到首次产生响应所用的时间。
早期的批处理系统中使用的3种调度算法：
- 先来先服务（FCFS，First Come First Serve，非抢占式），：按照作业/进程到达的先后顺序进行服务；用于作业调度，考虑的是哪个作业先到达后备队列（在外存中）；用于进程调度时，考虑的是哪个进程先到达就绪队列（在内存中）。
  - 优点：公平、算法实现简单。
  - 缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即FCFS算法对长作业有利，对短作业不利。不会导致饥饿（某进程/作业长期得不到服务）。
- 短作业优先（SJF，Shortest Job First）：最短的作业/进程优先得到服务（所谓“最短”，是指要求服务时间最短。）用于作业调度，也可以用于进程调度。用于进程调度时称为“短进程优先（SPF，Shortest Process First）算法”。SJF和SPF是非抢占式的算法。但是也有抢占式的版本--最短剩余时间优先算法（SRTN，Shortest Remaining Time Next）
  - 优点：“最短的”平均等待时间、平均周转时间。
  - 缺点：不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先。
  - 会导致饥饿。若源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生饥饿现象。若一直得不到服务，则称为饿死。
- 高响应比优先（HRRN，Highest Respose Ratio Next）：在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务。
  - 响应比= $\frac{等待时间+要求服务时间}{要求服务时间} \ge$ 1
  - 既可以用于作业调度，也可以进程调度。
  - 不会导致饥饿。非抢占式的算法。因此只有当运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比。
  - 优点：综合考虑了等待时间和运行时间（要求服务时间）：等待时间相同时，要求服务时间短的优先（SJF的优点）。要求服务时间相同时，等待时间长的优先（FCFS的优点）。对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题。

先来先服务算法

短进程优先算法

最短剩余时间优先算法

若题目中为未特别说明，短作业/进程优先算法默认是非抢占式的。
在所有进程同时可运行或者在所有进程都几乎同时到达时，采用SJF调度算法的平均等待时间、平均周转时间最少。
抢占式的短作业/进程优先调度算法（最短剩余时间优先，SRNT算法）的平均等待时间、平均周转时间最少。
虽然严格来说，SJF的平均等待时间、平均周转时间并不一定最少，但相比于其他算法（如FCFS），SJF依然可以获得较少的平均等待时间、平均周转时间。

高响应比优先算法

交互式系统的3种调度算法：
- 时间片轮转（RR，Round-Robin，不会导致饥饿）：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如100ms）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。
  - 用于进程调度，只有作业放入内存建立了相应的进程后，才能被分配处理机时间片。
  - 若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知CPU时间片已到。
  - 若时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间（比如：系统中有10个进程在并发执行，若时间片为1s，则一个进程被响应可能需要等待9s，即若用户在自己进程的时间片外通过键盘发出调试命令，可能需要等待9s才能被系统响应）。因此，时间片不能太大。
  - 若时间片太小，会导致进程切换过于频繁（一般来说，设计时间片时要让切换进程的开销占比不超过1%），系统会花大量的时间来处理进程切换。
  - 优点：公平；响应快，适用于分时操作系统。
  - 缺点：由于高频率的进程切换，因此有一定的开销；不区分任务的紧急程度。
- 优先级调度算法（会导致饥饿）：各个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程。既可用于作业调度，也可用于进程调度。
  - 抢占式、非抢占式都有。两者的区别：非抢占式只需在进程主动放弃处理机时进程调度即可，而抢占式还需在就绪队列发生变化时，检查是否会发生抢占。就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以把优先级高的进程排在更靠近队头的位置。
  - 根据优先级是否动态，分为静态优先级和动态优先级两种：
    - 静态优先级：创建进程时确定，之后一直不变。
    - 动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级。
    - 通常，系统进程优先级高于用户进程；前台进程优先级高于后台进程；操作系统更偏好I/O 型进程（或称为I/O繁忙型进程）。I/O设备和CPU可以并行工作。若优先级让I/O繁忙型进程优先运行的话，则越有可能让I/O设备尽早地投入工作，则资源利用率、系统吞吐量都会得到提升。注意：与I/O型进程相对的是计算机型进程（或称CPU繁忙型进程）
  - 优点：用优先级区分紧急程度，重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。
  - 缺点：若源源不断地有高优先级进程到来，则可能导致饥饿。
- 多级反馈队列调度算法 （会导致饥饿）：①设置多级就绪队列，各级队列优先级从高到低，时间片从小到大；②新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。若此时已经是最下级的队列，则重新放回该队列队尾；③只有第k级队列为空时，才会有k+1级队头的进程分配时间片。
  - 用于进程调度。
  - 抢占式算法。在k级队列的进程运行过程中，若更上级的队列（1~(k-1)级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾。
  - 优点：对各类型进程相对公平（FCFS的优点）；每个新到达的进程都可以很快得到响应（RR的优点）；短进程只用较少的时间就可完成（SPF的优点）；不必实现估计进程的运行时间（避免用户作假）；可灵活地调整对各类进程的偏好程度，比如：CPU密集型进程，I/O密集型进程。（可以将因I/O而阻塞的进程重新放回原队列，这样I/O型进程就可以保持较高优先级）

时间片轮转调度算法

非抢占式优先级调度算法

抢占式的优先级调度算法

多级反馈队列调度算法

进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

进程互斥

临界区（临界段）是进程中访问临界资源的代码段；进入区和退出区是负责实现互斥的代码段。
为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：
- 空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。
- 忙则等待：当已有进程进入临界区时，其它试图进入临界区的进程必须等待。
- 有限等待：对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）
- 让权等待：当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。
进程互斥的软件实现方法：
- 单标志法：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程，即每个进程进入临界区的权限只能被另一个进程赋予。可以实现同一时刻最多只允许一个进程访问临界区。
- 双标志先检查：设置一个布尔数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，如：flag[0]=true意味着0号进程 $P0$ 现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界，若没有，则把自身对应的标志flag[i]设为true，之后开始访问临界区。
- 双标志后检查：前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。
- Peterson算法：若双方都争着想进入临界区，则可让进程尝试“孔融让梨”，主动让对方先使用临界区。该算法解决了进程互斥的问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。

单标志法

双标志先检查法

双标志后检查法

Peterson算法

进程互斥的软件实现方法

进程互斥的硬件实现方法：
- 中断屏蔽方法：利用开/关中断指令实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况）。优点：简单高效。缺点：不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令若能让用户随意使用则会很危险）
- TestAndSet，TS指令/TestAndSetLock，TSL指令：用硬件实现，执行的过程中不允许被中断，只能一气呵成。
- Swap指令（XCHG指令）：用硬件实现，执行的过程不允许被中断，只能一气呵成。

TestAndSet指令

Swap指令

用户进程可通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便地实现进程互斥、进程同步。
一对原语：wait(S)原语和signal(S)原语，形式：函数名(参数)。其常简称为P(S)、V(S)操作（来自荷兰语proberen和verhogen）。
信号量机制：
- 整形信号量：用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。与普通整数变量的区别，对信号量的操作只有三种：①初始化；②P操作；③V操作。

整型信号量

记录型信号量

记录型信号量例子

信号量机制实现进程互斥

信号量机制实现进程同步

信号量机制实现前驱关系

信号量机制

生产者与消费者问题分析

生产者与消费者伪代码

不能改变相邻的P、V操作

在生产者-消费者问题中，若缓冲区大小为1，则有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。实现互斥的P操作一定要在实现同步的P操作之后，否则可能引起“死锁”。

多生产者-多消费者问题

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：①允许多个读者可以同时对文件执行操作；②只允许一个写者往文件中写信息；③任一写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作前，应让已有的读者和写者全部退出。

读者优先

读写公平法

哲学家进餐问题

哲学家就餐解决方案

管程是一种特殊的软件模块（类比于Java中的synchronized关键字的使用），有这些部分组成：
- 局部于管程的共享数据结构说明；
- 对该数据结构进行操作的一组过程；
- 对局部于管程的共享数据设置初始值的语句；
- 管程有一个名字。
管程的基本特征：
- 局部于管程的数据只能被局部于管程的过程所访问；
- 一个进程只有通过调用管程内的过程才能进入管程访问共享数据；
- 每次仅允许一个进程在管程内执行某个内部过程。

用管程解决生产者消费者问题

死锁：在并发环境下，各进程因竞争资源而造成的一种相互等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象。发生死锁后若无外力干涉，这些进程都将无法向前推进。
饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。比如：短进程优先（SPF）算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程“饥饿”。
死循环：某进程执行过程中一直跳不出某个循环的现象。

死锁、饥饿、死循环的区别

死锁产生的四个必要条件：
- 互斥：只有对必须互斥使用的资源进行争抢才会导致死锁（如哲学家的筷子、打印机设备）。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）。
- 不剥夺：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
- 请求和保持：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
- 循环等待：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。
- 注意：发生死锁时一定有循环等待，但是发生循环等待时未必发生死锁，即循环等待是死锁的必要不充分条件。若同类资源数大于1，则即使有循环等待，也未必发生死锁。若系统中每类资源都只有1个，则循环等待就是死锁的充分必要条件了。
什么时候会发生死锁？
- 对系统资源的竞争：各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源（CPU）的竞争是不会引起死锁的。
- 进程推进顺序非法：请求和释放资源的顺序不当，也同样会导致死锁。例如：并发执行的进程P1、P2分别申请并占有了资源R1，R2，之后进程P1又紧接着申请资源R2，而进程P2又申请资源R1，两者会因为申请的资源被对方占有而阻塞，从而发生死锁。
- 信号量的使用不当：如生产者-消费者问题中，若实现互斥的P操作在实现同步的P操作之前，就有可能导致死锁。
死锁的处理策略：
- 预防死锁：破环死锁产生的四个必要条件之一即可。
  - 破环互斥条件：若把只能互斥使用的资源改为允许共享使用，则系统不会进入死锁状态。比如：SPOOLing技术。操作系统可以采用SPOOLing技术把独占设备在逻辑上改造成共享设备，如：用SPOOLing技术将打印机改造成共享设备等。
    - 缺点：并不是所有的资源可以改造成可共享使用的资源，并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件。
  - 破坏不剥夺条件：
    - 方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。
    - 方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级（比如：剥夺调度方式：将处理机资源强行剥夺给优先级更高的进程使用）
      - 缺点：①实现起来比较复杂；②释放已获得的资源可能造成前一阶段工作的失效。因此，这种方法一般仅适用于易保存和恢复状态的资源，如CPU；③反复地申请和释放资源会增加系统开销，降低系统吞吐量；④若采用方案一，意外着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。若一直发生这样的情况，则会导致进程饥饿。
  - 破坏请求和保持条件：可以采用静态分配的方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源。
    - 缺点：有些资源可能需要用很短的时间，因此若进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。另外，该策略也有可能导致某些进程饥饿。
  - 破坏循环等待条件：可采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（即编号相同的资源）一次申请完。
    - 原理分析：一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源，按此规则，已持有大编号资源的进程不可能逆向地回来申请小编号地资源，从而就不会产生循环等待地现象。
    - 缺点：①不方便增加新的设备，因为可能需要重新分配所有的编号；②进程实际使用的资源顺序可能和编号递增顺序不一致，会导致资源浪费；③必须按规定按次序申请资源，用户编程麻烦。
- 避免死锁：用银行家算法防止系统进入不安全状态。
  - 安全序列：若系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。若系统处于安全状态，则一定不会发生死锁。若系统进入不安全状态，就可能发生死锁（处于不安全状态未必就是发生了死锁，但发生死锁时一定是处于不安全状态）因此，在分配资源之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这就是银行家算法的核心思想。
- 死锁的检测和解除：允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁。
  - 检测死锁的算法：
    - 在资源分配图中，找出既不阻塞又不是孤立点的进程Pi（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量），消去它所有的请求边和分配边，使之成为孤立的节点；
    - 进程Pi所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。在进行一系列简化后，若能消去图中所有边，则称该图是可完全简化的，此时一定没有发生死锁，相当于能找到一个安全序列。若最终不能消除所有边，则此时就是发生了死锁，最终还连着边的那些进程就是处于死锁状态的进程。
  - 解除死锁的主要方法：
    - 资源剥夺法：挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
    - 撤销进程法（终止进程法）：强制撤销部分，甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，或者接近结束了，一旦被终止则功亏一篑，以后还得从头再来。
    - 进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步，这就要求系统要记录进程的历史信息，设置还原点。

破坏请求和保持条件可能导致饥饿现象

银行家算法来避免死锁的发生

重要知识点：银行家算法

死锁的检测