软考（二）：操作系统

记录操作系统中知识点

考点

进程
- 进程的基本概念以及状态变化
- 进程死锁
- 进程同步、复制，信号量，前趋图，PV原语
存储
其他细节

进程

进程三态图 * 就绪状态：进程已得到运行所需资源，只等待CPU的调度便可运行； * 运行状态：进程已得到运行所需资源，并且得到了CPU的调度； * 等待状态：不具备运行条件、等待时机的状态。另：等待状态也称阻塞状态；

进程五态图 * 挂起：把该进程从内存中搬到外存上。 * 激活：又叫唤醒或恢复，操作是一样的，只是叫法不一样而已，该操作是把外存上的某个进程弄到内存上。

为什么要引入挂起和激活操作呢？

用户的需要。用户调试一个程序的时候，运行该程序一多半了，但是，忽然发现该程序此时有Bug，用户想停下来修改，但是修改后，用户又不想从头开始运行该程序，此为一因。
操作系统的需要。操作系统管理着资源的分配，它无法忍受那些占着资源而不运行的程序，另外，这些进程也会妨碍系统的运行速度，此为一因。等等。

进程的死锁

进程管理师操作系统的核心，但如果设计不当，就会出现死锁的问题。如果一个进程在等待一个不可能发生的事，则进程就死锁了。而如果一个或多个进程产生死锁，就会造成系统死锁

例如：系统有3个进程：A、B、C。这三个进程都需要5个系统资源。如果系统有13个资源，则不可能发生死锁。

死锁发生的必要条件

互斥条件：即一个资源每次只能被一个进程使用，在操作系统中这是真实存在的情况。
保持和等待条件：有一个进程已经获得了一些资源，但因请求其他资源被阻塞时，对已获取的资源保持不放。
不剥夺条件：有些系统不可资源是不可剥夺的，当某个进程已获得这种资源后，系统不能强行收回，只能由进程使用完时自己释放。
环路等待条件：若干个进程形成环形链，每个都占用对方要申请的下一个资源。

解决死锁的策略

死锁预防：例如：要求用户申请资源时一起申请所需的全部资源，这就破坏了保持和等待条件；将资源分层，得到上一层资源后，才能够申请下一层资源，它破坏了环路等待条件。预防通常会降低系统的效率。
死锁避免：避免是指进程在每次申请资源时判断这些操作是否安全，典型算法是「银行家算法」。但这种算法会增加系统的开销。
死锁检测：
死锁解除

银行家算法

著名的银行家算法，最早是由Dijkstra提出来的。它是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。

银行家算法最重要的就是判断是可用资源和仍需资源之间的关系，如果可用资源数大于人需资源数，那么我们认为这个进程就是可以执行的，也是安全的，反之，便是不安全的。所以重中之重的是找到各种资源数。

对进程的判断遵循以下步骤: 1. 计算系统开始时所有的资源数,即开始的可用资源数; 2. 在仍需资源数和可用资源数中作比较,找到符合条件的进程,最后修改进程执行完毕时系统的可用资源数; 3. 继续比较剩余进程和可用资源数,找到下边可以执行的进程; 4. 依次类推;

【例】假设系统中有3类互斥资源R1、R2、R3，可用资源分别是9、8、5,。在T0时刻系统中有P1、P2、P3、P4和P5五个进程，这些进程对资源的最大需求量和已分配资源数如下表所示，则进程如何执行是安全的。

这里需要强调的是，无论题目中给出何种条件，我们只要找到以下信息便可从容应对各种变化：

【注】：

可用资源：表示相应的进程执行完毕（即释放该进程占用的资源）以后可用的资源，满足公式可用资源=可用资源+已分配资源，（因为已分配的资源将会在进程执行完毕以后释放，所以可用资源会不断增多，进程执行完毕便会全部释放）同时它也是下一个进程执行时可用的资源。

**需要说明的是根据进程执行情况的不同，每次填入表格中的可用资源也不会相同（因为每个进程分配的资源是有差异的），那么执行顺序也会有所差异，合理即可。

仍需资源：仍需资源数=最大需求量-已分配资源数，据此公式可以求得R1、R2、R3在不同的进程时仍需的资源数，如上表中所示。

按照之前所讲的步骤，实现如下：

R1已分配的总资源数为1+2+2+1+1=7
R2已分配的总资源数为2+1+1+2+1=7
R3已分配的总资源数为1+1+0+0+3=5
则R1 R2 R3可用资源数分别为
R1=9-7=2
R2=8-7=1
R3=5-5=0

开始有的资源数R1 R2R3分别为2、1、0,所以从仍需资源中查找(需要说明的是查找的时候以最少资源数作为限定条件能够较快地找出结果),只有P2进程符合条件,此时可用资源变为4、2、1；
接下来在在其余的进程中查找符合条件的进程,只能执行P4,此时可用资源变为5、4、1,以此类推,按照以上的步骤即可找到所有进程执行的顺序P2->P4->P5->P1->P3；

以上便是有关银行家算法的计算过程。

前趋图

前趋图（Precedence Graph）是一个有向无循环图，记为DAG（Directed Acyclic Graph），用于描述进程之间执行的前后关系。途中的每个节点可用于描述一个程序段或进城，乃至一条语句；节点间的有向边则用于表示两个节点之间存在的偏序（Partial Order）或前驱关系（Precedence Relation）「→」

如果\(P_i\)必须在\(P_j\)之前完成，可写成\(P_i \rightarrow P_j\)，称\(P_i\)是\(P_j\)的直接前驱，而称\(P_j\)是\(P_i\)的直接后继。在前驱图中，把没有前驱的节点称为初始节点（Initial Node），把没有后继的节点称为终止节点（Final Node）。

同步问题

生产者-消费者问题

生产者-消费者（producer-consumer）问题是一个著名的进程同步问题。它描述的是：有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个缓存区的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中：消费者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式运行的，但他们之间必须保持同步，即不允许消费者进程到一个空缓冲区去取产品；也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。

临界资源诸进程间需要互斥方式对其进行共享的资源，如打印机、磁带机等。
临界区每个进程中访问临界资源的那段代码称为临界区

在操作系统中，进程之间经常会存在互斥（都需要共享独占性资源时）和同步（完成异步的两个进程的协作）两种关系。为了有效地处理这两种情况，W·Dijkstra在1965年提出信号量和PV操作。

信号量：是一种特殊的变量。
P操作：也称为down（）、wait（）操作，使S=S-1，若S<0，进程暂停执行，放入信号量的等待队列；
V操作：也称up（）、signal（）操作，使S=S+1,若S<=0，唤醒等待队列中的一个进程。
缺点
1. 易读性差，因为要了解对于一组共享变量及信号量的操作是否正确，则必须通读整个系统或者并发程序；
2. 不利于修改和维护，因为程序的局部性很差，所以任一组变量或一段代码的修改都可能影响全局；
3. 正确性难以保证，因为操作系统或并发程序通常很大，要保证这样一个复杂的系统没有逻辑错误是很难的。

存储

考点1：实存管理
考点2：虚存管理

程序的装入（重定位）

静态重定位：静态重定位是在虚空间程序执行之前由装配程序完成地址影射工作。
动态重定位：动态重定位是在程序执行过程中，在 CPU 访问内存之前，将要访问的程序或数据地址转换为内存地址。

实存管理

存储管理的任务是存储空间的分配与回收。在现代操作系统中通常有单一连续分配、固定分区分配、可变分区分配三种分配方法：

分配办法	单一连续分配	固定分区分配	可变分区分配
分配类型	静态分配法	静态分配法	动态分配法
分配特点	不分区，所有用户空间给某个进程或作业	分成大小不等的区域，区域分完后固定不变	分成大小不等的区域，根据用户要求动态分配

在可变分区分配方式中，当有新作业申请分配内存时所采用的存储分配算法有以下四种：

最佳适应法：选择等于或最接近作业需求的内存自由区进行分配。这种方法可以减少碎片，但同时也可能带来更多小得无法再用的碎片。
首次适应法：从主存低地址开始，寻找第一个可用（即大于等于作业需求的内存）的自由区。这种方法可实现快速分配，缩短查找时间。
最差适应法：选择整个主存中最大的内存自由区。
循环首次适应算法：是首次适应法的一个变种，也就是不再是每次都从头开始匹配，而是连续向下匹配。

虚存管理

页式存储组织

优点：利用率高，产生的内存碎片小，内存间分配及管理简单。
缺点：要有相应的硬件支持，增加了系统开销；请求调页的算法如选择不当，有可能产生抖动现象。

段式存储组织

优点：便于多道程序共享内存，便于对存储器的保护，各段程序修改互不影响。
缺点：内存利用率低，内存碎片浪费大。）

段页式存储组织

优点：空间浪费小、存储共享容易、存储保护容易、能动态连接。
缺点：由于管理软件的增加，复杂性和开销也随之增加，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降。

页面置换算法

最优（Optimal, OPT）算法
先进先出（FIF0) 算法
最近最少使用（LRU）算法

局部性原理

时间局部性
空间局部性 ## 作业管理作业由三部分构成，即程序、数据和作业说明书，它是用户在完成项任务过程中要求计算机系统所做工作的集合。作业的状态有后备状态、运行状态和完成状态三种。

作业状态及其转换
作业调度算法

先来先服务（FCFS)
最短作业优先（SJF)
最高响应比优先算法
定时轮转
优先数

作业周转时间单个作业的周转时间：==\(T_i\)=\(T_{ei}\) - \(T_{si}\)== ==\(T_i\)=\(T_{wi}\) + \(T_{ri}\)== 其中 \(T_{ei}\)为作业的完成时间，\(T_si\)为作业的提交时间。作业平均周转时间：T= (Ti+T2+… +Tn) / In