进程管理

1.1 进程状态

运行态 ：
- 占有处理器正在运行。
就绪态 ：
- 具备运行条件，等待系统分配处理器以便运行。
等待态（阻塞态） ：
- 不具备运行条件，正在等待某个事件的完成。
一个进程在创建后将处于就绪状态。在执行过程中，每个进程任一时刻只会处于这3种状态之一。
运行态→等待态：处于运行状态的进程在运行的过程中需要等待某一事件发生后，才能继续运行，于是该进程由运行状态变成等待状态。例如等待 I/O 完成。
等待态→就绪态：处于等待状态的进程，假如其等待的事件已经发生结束。于是进程由等待状态变成就绪状态。
就绪态→运行态：当处于就绪状态的进程被进程调度程序选中后，就分配到处理器来运行，进程由就绪状态变成运行状态。
运行态→就绪态：处于运行状态的进程在运行的过程中，因分给它的处理器时间片已用完而不得不让出处理器，于是进程由运行状态变成就绪状态。

进程死锁

一个进程在等待的是一个不可能发生的事件，系统会将该进程死锁，若多个进程产生死锁，则系统自身会死锁

死锁的四个必要因素

互斥：至少有一个资源必须处于非共享模式，即一次只有一个进程可使用。如果另一进程申请该资源，那么申请进程应等到该资源释放为止。
占有并等待 ：一个进程应占有至少一个资源，并等待另一个资源，而该资源为其他进程所占有。
非抢占 ：资源不能被抢占，即资源只能被进程在完成任务后自愿释放。
循环等待 ：有一组等待进程{$P_0$ ，$P_1$ ，…，$P_n$ }，$P_0$等待的资源为$P_1$占有，$P_1$等待的资源为$P_2$占有，……，$P_{n-1}$ 等待的资源为$P_n$占有，$P_n$等待的资源为$P_0$占有。

解决死锁的策略

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

所谓银行家算法 ，是指在分配资源之前，先看清楚，如果资源分配下去后，是否会导致系统死锁。如果会死锁，则不分配，否则就分配。具体来说，银行家算法分配资源的原则总结如下：
1. 当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程。
2. 进程可以分期请求资源，但请求的总数不能超过最大需求量。
3. 当系统现有的资源不能满足进程尚需资源数时，对进程的请求可以推迟分配，但总能使进程在有限的时间里得到资源。
注意：
- 如果系统中有 N 个并发进程，若规定每个进程需要申请 R 个某类资源，则当系统提供 ==$K=N $\times$ （R-1）+1$== 个同类资源时，无论采用何种方式申请使用，一定不会发生死锁。

死锁检测 ：
- 前两者是事前措施，而死锁的检测则是判断系统是否处于死锁状态，如果是，则执行死锁解除策略。
死锁解除 ：
- 这是与死锁检测结合使用的，它使用的方式就是剥夺。即将某进程所拥有的资源强行收回，分配给其他的进程。

进程的同步与互斥

同步
- 进程同步也是进程之间直接的制约关系，是为完成某种任务而建立的两个或多个线程，这个线程需要在某些位置上协调他们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系来源于他们之间的合作。
- 比如说进程 A 需要从缓冲区读取进程 B 产生的信息，当缓冲区为空时，进程 B 因为读取不到信息而被阻塞。而当进程 A 产生信息放入缓冲区时，进程 B 才会被唤醒。
互斥
- 进程互斥是进程之间的间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待。只有当使用临界资源的进程退出临界区后，这个进程才会解除阻塞状态。
- 比如进程 B 需要访问打印机，但此时进程 A 占有了打印机，进程 B 会被阻塞，直到进程 A 释放了打印机资源，进程 B 才可以继续执行。

信号量与PV操作

信号量
- 信号量 S 可以直接理解成计数器，是一个整数。信号量的值仅能由 PV 操作来改变。通过 PV 操作控制信号量来实现进程的同步和互斥。
PV操作
- PV 操作：解决互斥和同步的问题。
- PV 操作是分开来看的：
- P 操作：使 S=S-1，若 S $\geq$ 0，则该进程继续执行，否则该进程排入等待队列。
- V 操作：使 S=S+1，若 S $\leq$ 0，唤醒等待队列中的一个进程。
- 在资源使用之前将会执行 P 操作，之后将会执行 V 操作。在互斥关系中 PV 操作在一个进程中成对出现，而在同步关系中则一定在两个或多个进程中成对出现。

存储管理

页式存储管理

页式存储管理是通过引入==进程的逻辑地址==，把进程地址空间与实际物理存储位置分离，从而增加存储管理的灵活性。我们把逻辑地址空间划分为一些相等的片，这些片称为页或页面。同样，物理地址空间也被划分为同样大小的片，称为块。这样用户程序进入内存时，通过页表就可以将一页对应存入到一个块中。这些物理块不必连续。所以内存利用率可以大大提高。
在页式系统中，指令所给出的逻辑地址分为两部分：逻辑页号和页内地址。其中页号与页内地址所占多少位，与主存的最大容量、页面的大小有关。
CPU 中的内存管理单元按逻辑页号查找页表（操作系统为每一个进程维护了一个从虚拟地址到物理地址的映射关系的数据结构，页表的内容就是该进程的虚拟地址到物理地址的一个映射）得到物理页号，将物理页号与页内地址相加形成物理地址。

页面置换算法

>当程序的存储空间要求大于实际的内存空间时，就使得程序难以运行了。虚拟存储技术就是利用实际内存空间和相对大得多的外部储存器存储空间相结合构成一个远远大于实际内存空间的虚拟存储空间，程序就运行在这个虚拟存储空间中，能够实现虚拟存储的依据是程序的局部性原理，即程序在运行过程中经常体现出运行在某个局部范围之内的特点。即在一段时间内，整个程序的执行仅限于程序中的某一部分。虚拟存储是把一个程序所需要的存储空间分成若干页，程序运行用到的页就放在内存里，暂时不用就放在外存中，当用到外存中的页时，就把它们调到内存，反之就把它们送到外存中。由于所有的进程页面不是一次性地全部调入内存，而是部分页面装入。

这就有可能出现下面的情况：要访问的页面不在内存，这时系统产生缺页中断。操作系统在处理缺页中断时，要把所需页面从外存调入到内存中。如果这时内存中有空闲块，就可以直接调入该页面；如果这时内存中没有空闲块，就必须先淘汰一个已经在内存中的页面，腾出空间，再把所需的页面装入，即进行页面置换。

先进先出法（FIFO）

FIFO 算法认为最早调入内存的页不再被使用的可能性要大于刚调入内存的页，因此，先进先出法总是淘汰在内存中停留时间最长的一页，即先进入内存的页，先被换出。
该算法会出现在内存块增加的情况下，缺页率不减反增
- 这种现象称为 贝拉迪Belady异常 ————当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。
- 只有FIFO算法会产生Belady异常。另外，FIFO算法==虽然实现简单，但是该算法与进程实际运行时的规律不适应==，因为先进入的页面也有可能最经常被访问。因此，算法性能差

最佳置换法（OPT）

最佳置换算法（OPT）在为调入新页面而必须预先淘汰某个老页面时，所选择的老页面应该以后不被使用，或者是在最远的以后时间才被访问。采用这种算法，能保证有最小缺页率。（缺页率=缺页次数/总共访问页面的次数）
==缺页时未必发生页面置换，有可能还有空闲的内存块等待使用==
是一种理想化算法，在实际应用中无法实现
最近最少使用置换法（LRU）
最近最少使用置换法（LRU）是选择在最近一段时间里最久没有使用过的页面予以淘汰。

文件管理

文件管理概念

wjgl

在树型目录结构中，树的根结点为根目录，数据文件作为树叶，其他所有目录均作为树的结点。系统在建立每一个目录时，都会自动为它设定两个目录文件，一个是“.”，代表该目录自己；另一个是“..”，代表该目录的父目录，也就是上级目录。
从逻辑上讲，用户在登录到系统中之后，每时每刻都处在某个目录之中，此目录被称作工作目录或当前目录。工作目录是可以随时改变的。
对文件进行访问时，需要用到路径的概念。路径是指从树型目录中的某个目录层次到某个文件的一条道路。在树型目录结构中，从根目录到任何数据文件之间，只有一条唯一的通路，从树根开始，把全部目录文件名与数据文件名依次用“/”连接起来，构成该数据文件的路径名，且每个数据文件的路径名是唯一的。这样，可以解决文件重名问题，不同路径下的同名文件不一定是相同的文件。例如，在图 2-5 中，根目录下的文件 f1 和/D1/W1目录下的文件 f1 可能是相同的文件，也可能是不相同的文件。

设备管理

程序查询方式
最简单的 I/O 控制方式是程序查询方式，要求 CPU 不断使用指令检测方法来获取外设工作状态。由于 CPU 的速度远远高于 I/O 设备，导致 CPU 的绝大部分时间都处于等待 I/O设备过程中，造成 CPU 的运行效率极低。CPU 和外围设备只能串行工作。但是它==管理简单，在要求不高的场合可以被采用==。
程序中断方式

某一外设的数据准备就绪后，它“主动”向 CPU 发出中断请求信号，请求 CPU 暂时中断目前正在执行的程序转而进行数据交换；当 CPU 响应这个中断时，便暂停运行主程序，自动转去执行该设备的中断服务程序；当中断服务程序执行完毕（数据交换结束）后，CPU又回到原来的主程序继续执行。
程序中断方式虽然大大提高了主机的利用率，但是它以字（节）为单位进行数据传送，每完成一个字（节）的传送，控制器便要向 CPU 请求一次中断（做保存现场信息，恢复现场等工作），仍然占用了 CPU 的许多时间。这种方式==对于高速的块设备的 I/O 控制显然不适合==。

DMA方式

DMA存取方式，是一种完全由硬件执行 I/O 数据交换的工作方式。它既考虑到中断的响应，同时又要节约中断开销。此时，DMA 控制器代替 CPU 完全接管对总线的控制，数据交换不经过 CPU，直接在内存和外围设备之间成批进行。
优点：==速度快==，CPU 不参加传送操作，省去了CPU取指令、取数、送数等操作，也没有保存现场、恢复现场之类的工作。
缺点：批量数据传送前的准备工作，以及传送结束后的处理工作，仍由 CPU 通过执行管理程序来承担，DMA 控制器只负责具体的数据传送工作。==CPU仍然摆脱不了管理和控制外设的沉重负担，难以充分发挥高速运算的能力==。

I/O通道控制方式

通道是==一个特殊功能的处理器==，代替 CPU 管理控制外设的独立部件。有自己的指令和程序，专门负责数据输入输出的传输控制，而 CPU 在将“传输控制”功能下放给通道后，只负责“数据处理”功能。通道与 CPU 分时使用主存，实现了 CPU 内部运算与 I/O 设备的并行工作。

输入输出处理机方式

采用专用的小型通用计算机，可完成 I/O 通道所完成的 I/O 控制，还可完成码制转换、格式处理、检错纠错等操作，具有相应的运算处理部件、缓冲部件，还可形成 I/O 程序锁必需的程序转移手段。输入输出处理机基本独立于主机工作。在多数系统中，设置多台外围处理机，分别承担 I/O 控制、通信、维护等任务。
目前单片机、微型机多采用程序查询、程序中断和 DMA 方式。通道方式和输入输出处理机方式一般用在大中型计算机中。

软考网络工程师