操作系统进程管理

进程的组成：进程控制块PCB（唯一标志）、程序（描述进程要做什么）、数据（存放进程执行时所需数据）。

进程基础的状态是下左图中的三态图。需要熟练掌握左下图中的进程三态之间的转换。

• 就绪状态。当进程已分配了除 CPU 以外的所有必要的资源后，只要能再获得处理机，便能立即执行，把这时的进程状态称为就绪状态。在一个系统中，可以有多个进程同时处于就绪状态，通常把它们排成一个队列，称为就绪队列。
• 运行状态指进程已获得处理机，其程序正在执行。在单处理机系统中，只能有一个进程处于执行状态。
• 阻塞状态指进程因发生某事件（如请求 I/O、申请缓冲空间等）而暂停执行时的状态，亦即进程的执行受到阻塞，故称这种暂停状态为阻塞状态，有时也称为“等待”状态，或“睡眠”状态。通常将处于阻塞状态的进程排成一个队列，称为阻塞队列。

前趋图

前趋图是一个由结点和有向边构成的有向无循环图。该图通常用于表现事务之间先后顺序的制约关系。图中的每个结点可以表示一个语句、一个程序段或是一个进程，结点间的有向边表示两个结点之间存在的前趋关系。前驱图用来表示哪些任务可以并行执行，哪些任务之间有顺序关系，具体如下图：可知，ABC可以并行执行，但是必须ABC都执行完后，才能执行D，这就确定了两点：任务间的并行、任务间的先后顺序。

进程资源图

进程资源图用来表示进程和资源之间的分配和请求关系，如下图所示：

P代表进程，R代表资源，R方框中有几个圆球就表示有几个这种资源，在上图中，R1指向P1，表示R1有一个资源已经分配给了P1，P1指向R2，表示P1还需要请求一个R2资源才能执行。

阻塞节点：某进程所请求的资源已经全部分配完毕，无法获取所需资源，该进程被阻塞了无法继续。如上图中P2。

非阻塞节点：某进程所请求的资源还有剩余，可以分配给该进程继续运行。如上图中P1、P3。

当一个进程资源图中所有进程都是阻塞节点时，即陷入死锁状态。

进程资源图的化简方法：先看系统还剩下多少资源没分配，再看有哪些进程是不阻塞的，接着把不阻塞的进程的所有边都去掉，形成一个孤立的点，再把系统分配给这个进程的资源回收回来，这样，系统剩余的空闲资源便多了起来，接着又去看看剩下的进程有哪些是不阻塞的，然后又把它们逐个变成孤立的点。最后，所有的资源和进程都变成孤立的点。

进程同步与互斥

进程互斥定义为：一组并发进程中一个或多个程序段，因共享某一共有资源而导致必须以一个不允许交叉执行的单位执行。也就是说互斥是要保证临界资源在某一时刻只被一个进程访问。

进程同步定义为：把异步环境下的一组并发进程因直接制约而互相发送消息而进行互相合作、互相等待，使得各进程按一定的速度执行的过程称为进程同步。也就是说进程之间是异步执行的，同步即是使各进程按一定的制约顺序和速度执行。

信号量

各进程间需要以互斥方式对其进行访问的资源，也就是一次仅允许一个进程使用的资源称为临界资源。把一个进程访问临界资源的那段程序代码称为临界区。

信号量可以有效地实现进程的同步和互斥。在操作系统中，信号量是一个整数。当信号量大于等于 0 时，代表可供并发进程使用的资源实体数，当信号量小于零时则表示正在等待使用临界区的进程数。建立一个信号量必须说明所建信号量代表的意义和设置初值，以及建立相应的数据结构，以便指向那些等待使用该临界区的进程。

信号量有两种：

• 互斥信号量：对临界资源采用互斥访问，使用互斥信号量后其他进程无法访问，初值为1。
• 同步信号量：对共享资源的访问控制，初值一般是共享资源的数量。

对信号量只能施加特殊的操作：P 操作和 V 操作。P 操作和 V 操作都是不可分割的原子操作，也称为原语。因此，P 原语和 V 原语执行期间不允许中断发生。

P操作：申请资源，S＝S-1，若s>=0，则执行P操作的进程继续执行；若S＜0，则置该进程为阻塞状态（因为无可用资源），并将其插入阻塞队列。

V操作：释放资源，S＝S＋1，若S＞0，则执行V操作的进程继续执行；若S＜＝0，则从阻塞状态唤醒一个进程，并将其插入就绪队列（此时因为缺少资源被P操作阻塞的进程可以继续执行），然后执行v操作的进程继续。

进程调度

进程调度即处理器调度（又称上下文转换），它的主要功能是确定在什么时候分配处理器，并确定分给哪一个进程，即让正在执行的进程改变状态并转入就绪队列的队尾，再由调度原语将就绪队列的队首进程取出，投入执行。

进程调度方式是指当有更高优先级的进程到来时如何分配CPU。分为可剥夺和不可剥夺两种，可剥夺指当有更高优先级进程到来时，强行将正在运行进程的CPU分配给高优先级进程；不可剥夺是指高优先级进程必须等待当前进程自动释放CPU。

在某些操作系统中，一个作业从提交到完成需要经历高、中、低三级调度。

1. 高级调度。高级调度又称“长调度”“作业调度”或“接纳调度”，它决定处于输入池中的哪个后备作业可以调入主系统做好运行的准备，成为一个或一组就绪进程。在系统中一个作业只需经过一次高级调度。
2. 中级调度。中级调度又称“中程调度”或“对换调度”，它决定处于交换区中的哪个就绪进程可以调入内存，以便直接参与对CPU的竞争。
3. 低级调度。低级调度又称“短程调度”或“进程调度”，它决定处于内存中的哪个就绪进程可以占用CPU。低级调度是操作系统中最活跃、最重要的调度程序，对系统的影响很大。

进程调度的算法是服务于系统目标的策略，对于不同的系统与系统目标，常采用不同的调度算法：

1. 先来先服务FCFS：先到达的进程优先分配CPU。用于宏观调度。
2. 时间片轮转：分配给每个进程CPU时间片，轮流使用CPU，每个进程时间片大小相同，很公平，用于微观调度。
3. 优先级调度：每个进程都拥有一个优先级，优先级大的先分配CPU。
4. 多级反馈调度：时间片轮转和优先级调度结合而成，设置多个就绪队列1,2,3...n，每个队列分别赋予不同的优先级，分配不同的时间片长度；新进程先进入队列1的末尾，按FCFS原则，执行队列1的时间片；若未能执行完进程，则转入队列2的末尾，如此重复。

死锁

当一个进程在等待永远不可能发生的事件时，就会产生死锁，若系统中有多个进程处于死锁状态，就会造成系统死锁。死锁是系统的一种出错状态，它不仅会浪费大量的系统资源，甚至还会导致整个系统的崩溃，所以死锁是应该尽量预防和避免的。

死锁产生的四个必要条件是资源互斥、每个进程占有资源并等待其他资源、系统不能剥夺进程资源、进程资源图是一个环路。死锁产生后，解决措施是打破四大条件，有下列方法：

• 死锁预防：采用某种策略限制并发进程对于资源的请求，破坏死锁产生的四个条件之一，使系统任何时刻都不满足死锁的条件。
• 死锁避免：一般采用银行家算法来避免，银行家算法，就是提前计算出一条不会死锁的资源分配方法，才分配资源，否则不分配资源，相当于借贷，考虑对方还得起才借钱，提前考虑好以后，就可以避免死锁。
• 死锁检测：允许死锁产生，但系统定时运行一个检测死锁的程序，若检测到系统中发生死锁，则设法加以解除。
• 死锁解除：即死锁发生后的解除方法，如强制剥夺资源，撤销进程等。

死锁资源计算：系统内有n个进程，每个进程都需要R个资源，那么其发生死锁的最大资源数为n*(R-1)。其不发生死锁的最小资源数为n*(R-1)+1。

线程

传统的进程有两个属性：可拥有资源的独立单位；可独立调度和分配的基本单位。

引入线程的原因是进程在创建、撤销和切换中，系统必须为之付出较大的时空开销，故在系统中设置的进程数目不宜过多，进程切换的频率不宜太高，这就限制了并发程度的提高。引入线程后，将传统进程的两个基本属性分开，线程作为调度和分配的基本单位，进程作为独立分配资源的单位。用户可以通过创建线程来完成任务，以减少程序并发执行时付出的时空开销。

线程是进程中的一个实体，是被系统独立分配和调度的基本单位。线程基本上不拥有资源，只拥有一点运行中必不可少的资源(如程序计数器、一组寄存器和栈)，它可与同属一个进程的其他线程共享进程所拥有的全部资源，例如进程的公共数据、全局变量、代码、文件等资源，但不能共享线程独有的资源，如线程的栈指针等标识数据。