|
|
|
|
|
|
|
|
|
前趋图是一个有向无循环图，图由节点和节点间的有向边组成，节点代表各程序段的操作，而节点间的有向边表示两程序段操作之间存在的前趋关系（"→"）。两程序段Pi和Pj的前趋关系表示成Pi→Pj，其中Pi是Pj的前趋，Pj是Pi的后继，其含义是Pi执行完毕才能由Pj执行。
|
|
|
|
|
|
.顺序性。程序中的各程序段严格按照规定的顺序执行。
|
|
|
|
.封闭性。指程序运行时系统内各资源只受该程序控制，执行结果不受外界因素影响。
|
|
|
|
.可再现性。只要程序执行环境和初始条件相同，运行结果就相同。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
进程通常是由程序、数据及进程控制块（PCB）组成的。进程的程序部分描述了进程需要完成的功能，进程数据集合部分包括程序执行时所需的数据及工作区。
|
|
|
|
进程控制块是进程的描述信息和控制信息，是进程动态特性的集中反映，也是进程存在的唯一标志。进程控制块包含的主要内容有进程标志符、状态、位置信息、控制信息、队列指针、优先级、现场保护区及其他。PCB是操作系统中最主要的数据结构之一，既是进程存在的标志和调度的依据，又是进程可以被打断并能恢复运行的基础。操作系统通过PCB管理进程，一般PCB是常驻主存的，尤其是调度信息必须常驻主存。
|
|
|
|
|
|
|
|
三态模型中最基本的状态有3种，即运行、就绪和阻塞。
|
|
|
|
.运行。进程正在处理机上运行。对于单处理机系统，处于运行状态的进程只有一个。
|
|
|
|
|
|
|
|
在进程运行过程中，由于自身进展情况及外界环境的变化，这3种基本状态可以在一定的条件下相互转换。进程的状态及转换如下图所示。
|
|
|
|
|
|
|
|
|
|
五态模型在三态模型的基础上增加了新建态和终止态。新建态是一个进程刚刚被创建还没有被提交，并等待系统完成创建进程的所有必要信息状态。终止态是指当一个进程已经正常结束或异常结束，操作系统进行善后处理并且释放主存的状态。
|
|
|
|
|
|
由于进程的不断创建，系统资源特别是主存资源已不能满足所有进程的运行要求，这时就必须将某些进程挂起，放到磁盘对换区，暂时不参加调度，以平衡系统负载。具有挂起状态的进程状态包括活跃就绪、静止就绪、活跃阻塞、静止阻塞。
|
|
|
|
|
|
进程控制就是对系统中所有进程从创建到消亡的全过程实施有效的控制。为此，操作系统设置了一套控制机构，该机构的主要功能包括创建一个新进程，撤销一个已经运行完的进程，改变进程的状态，实现进程间的通信。进程控制是由操作系统内核中的原语实现的。内核是计算机系统硬件的首次延伸，是基于硬件的第一层软件扩充，它为系统对进程进行控制和管理提供了良好的环境。
|
|
|
|
原语是指由若干条机器指令组成的，用于完成特定功能的程序段。原语的特点是在执行时不能被分割，即原子操作——要么都做，要么都不做。内核中所包含的原语主要有进程控制原语、进程通信原语、资源管理原语以及其他方面的原语。属于进程控制方面的原语有进程创建原语、进程撤销原语、进程挂起原语、进程激活原语、进程阻塞原语以及进程唤醒原语等。不同的操作系统内核所包含的功能不同，但大多数操作系统的内核都包含支撑功能和资源管理的功能。
|
|
|
|
|
|
|
|
同步是合作进程间的直接制约问题，互斥是申请临界资源进程间的间接制约问题。
|
|
|
|
|
|
相互合作的进程需要在某些确定点上协调它们的工作，当一个进程到达这些点后，除非另一个进程已经完成某些操作；否则就不得不停下来等待这些操作结束。这就是进程间的同步。
|
|
|
|
|
|
在多道程序系统中，各进程可以共享各类资源，但有些资源一次只能供一个进程使用，称为临界资源。这就产生了进程间的间接制约问题——互斥。
|
|
|
|
|
|
临界区是进程中对临界资源实施操作的那段程序。互斥临界区管理的原则是：有空即进，无空则登；有限等待，让权等待。
|
|
|
|
|
|
信号量机制主要有整型信号量、记录性信号量、信号量集机制。
|
|
|
|
|
|
信号量是一个整型变量，根据控制对象的不同赋予不同的值。信号量可分为以下两类。
|
|
|
|
（1）公用信号量。实现进程间的互斥，初值为1或资源的数目。
|
|
|
|
（2）私用信号量。实现进程间的同步，初值为0或某个正整数。
|
|
|
|
信号量S的物理意义为：S≥0，表示某资源的可用数；S<0，其绝对值表示阻塞队列中等待该资源的进程数。P、V操作是实现进程同步与互斥的常用方法。
|
|
|
|
P操作定义：S:=S-1，若S≥0，则执行P操作的进程继续执行；否则，若S<0，则置该进程为阻塞状态，并将其插入阻塞队列。
|
|
|
|
V操作定义：S:=S+1，若S>0，则执行V操作的进程继续执行；否则，若S≤0，则从阻塞状态唤醒一个进程，并将其插入就绪队列，执行V操作的进程继续执行。
|
|
|
|
|
|
令信号量的初值为1，当进程进入临界区时执行P操作，退出临界区时执行V操作。则进入临界区的代码段如下。
|
|
|
|
|
|
|
|
进程的同步是由于进程间合作而引起的相互制约问题。要实现进程的同步，可用一个信号量与消息联系起来。当信号量的值为0时表示消息未产生，当信号量的值为非0时表示希望的消息已经存在。假定用信号量S表示某条消息，进程可以通过调用P操作测试消息是否达到，调用V操作通知消息已经准备好。
|
|
|
|
|
|
P、V操作是用来协调进程间关系的，编程较困难、效率低，通信对用户不透明，生产者每次只能向缓冲区放一个消息，消费者只能从缓冲区中取一个消息。所以交换的信息量多时要引入高级通信原语。进程高级通信的类型主要有以下几种。
|
|
|
|
（1）共享存储系统。相互通信的进程共享某些数据结构或存储区，以实现进程之间的通信。
|
|
|
|
（2）消息传递系统。进程间的数据交换以消息为单位，程序员直接利用系统提供的一组通信命令（原语）来实现通信，如Send(A)、Receive(A)。
|
|
|
|
（3）管道通信。管道是指用于连接两个进程之间的一个打开的共享文件（pipe文件）。向管道（共享文件）提供输入的发送进程（即写进程），以字符流的形式将大量的数据送入管道；而接收进程可从管道的另一端接收大量的数据。由于通信时采用管道，所以叫管道通信。
|
|
|
|
|
|
管程是由一些共享数据、一组能为并发进程执行的作用在共享数据上的操作集合、初始代码以及存取权组成的。
|
|
|
|
采用这种方式管理共享资源可以借助数据结构及在其上实施操作的若干过程来进行，对共享资源的申请和释放可以通过过程在数据结构上的操作来实现。
|
|
|
|
管程提供了一种允许多进程安全有效地共享抽象数据类型的机制，管程实现同步机制的基础是"条件结构"。为实现进程的互斥和同步，必须定义一些条件变量。这些条件变量只能被wait和signal访问。利用管程可以解决生产者-消费者问题。
|
|
|
|
|
|
在某些操作系统中，一个作业从提交到完成需要经历高、中、低3级调度。
|
|
|
|
（1）高级调度。又称"长调度""作业调度"或"接纳调度"。它决定处于输入池中的哪个后备作业可以调入主系统做好运行的准备，使其成为一个或一组就绪进程。系统中一个作业只需经过一次高级调度。
|
|
|
|
（2）中级调度。又称"中程调度"或"对换调度"。它决定处于交换区中的就绪进程哪个可以调入主存，以便使其直接参与对CPU的竞争。在主存资源紧张时，为了将进程调入主存，必须将主存中处于阻塞状态的进程调至交换区，以便为调入进程腾出空间。
|
|
|
|
（3）低级调度。又称"短程调度"或"进程调度"。它决定处于主存中的就绪进程哪个可以占用CPU，是操作系统中最活跃、最重要的调度程序，对系统的影响很大。
|
|
|
|
|
|
调度方式是指当有更高优先级的进程到来时如何分配CPU。调度方式分为可剥夺式和不可剥夺式两种。可剥夺式是指当有更高优先级的进程到来时，强行将正在运行的进程所占用的CPU分配给高优先级的进程；不可剥夺式是指当有更高优先级的进程到来时，必须等待正在运行的进程自动释放占用的CPU，然后将CPU分配给高优先级的进程。
|
|
|
|
|
|
常用的进程调度算法有先来先服务、时间片轮转、优先级调度和多级反馈调度算法。
|
|
|
|
|
|
先来先服务（FCFS）是按照作业提交或进程变为就绪状态的先后次序分配CPU。即每当进入进程调度时，总是将就绪队列队首的进程投入运行。FCFS主要用于宏观调度，其特点是比较有利于长作业，而不利于短作业；有利于CPU繁忙的作业，而不利于I/O繁忙的作业。
|
|
|
|
|
|
时间片轮转的基本思路是通过时间片轮转，提高进程并发性和响应时间，从而提高资源利用率。时间片轮转算法主要用于微观调度，其设计目标是提高资源利用率。
|
|
|
|
|
|
|
|
（1）静态优先级。进程的优先级是在创建时就已确定好了，直到进程终止都不会改变。
|
|
|
|
（2）动态优先级。在创建进程时赋予一个优先级，在进程运行过程中还可以改变，以便获得更好的调度性能。
|
|
|
|
|
|
多级反馈调度算法是在时间片轮转算法和优先级算法的基础上改进的。其优点是：照顾短进程，提高系统吞吐量，缩短平均周转时间；照顾I/O型进程以获得较好的I/O设备利用率和缩短响应时间；不必估计进程的执行时间，动态调节优先级。
|
|
|
|
|
|
（1）I/O型进程。让其进入最高优先级队列，以便能及时响应需要I/O交互的进程。通常执行一个小的时间片，在该时间片内，要求能处理完一次I/O请求的数据，然后转入阻塞队列。
|
|
|
|
（2）计算型进程。每次都执行完时间片，进入更低级序列。最终采用最大时间片来执行，减少调度次数。
|
|
|
|
（3）I/O次数不多而主要是CPU处理的进程。在I/O完成后，放回优先的I/O申请时离开的队列，以免每次都回到最高优先级队列后再逐次下降。
|
|
|
|
（4）为适应一个进程在不同时间段的运行特点，在I/O完成时，提高优先级；时间片用完时，降低优先级。
|
|
|
|
|
|
死锁是指两个以上的进程互相都因要求对方已经占有的资源，导致无法运行下去的现象。死锁是系统的一种出错状态，不仅浪费大量的系统资源，甚至会导致整个系统的崩溃，所以死锁是应该尽量预防和避免的。
|
|
|
|
|
|
|
|
|
|
|
|
（1）互斥条件。进程对其要求的资源进行排他性控制，即一次只允许一个进程使用。
|
|
|
|
（2）请求保持条件。零星地请求资源，即已获得部分资源后又请求资源被堵塞。
|
|
|
|
（3）不可剥夺条件。进程已获得资源在未使用完之前不能被剥夺，只能在使用完时由自己释放。
|
|
|
|
（4）环路条件。发生死锁时，在进程资源有向图中必构成环路，其中每个进程占有下一个进程申请的一个或多个资源。
|
|
|
|
|
|
进程资源有向图由方框、圆圈和有向边3部分组成。其中，方框表示资源，圆圈表示进程。
|
|
|
|
|
|
|
|
|
|
|
|
（1）死锁的预防。根据产生死锁的4个必要条件，只要使其中之一不能成立，死锁就不会出现。为此，可以采取下列预防措施，即预先静态分配法和资源有序分配法。
|
|
|
|
（2）死锁的避免。最著名的死锁避免算法是Dijkstra提出的银行家算法，其思想是：对于进程发出的每一个系统可以满足的资源请求命令加以检测，如果发现分配资源后，系统可能进入不安全状态，则不予分配；若分配资源后系统仍处于安全状态，则分配资源。与死锁预防策略相比提高了资源的利用率，但增加了系统的开销。
|
|
|
|
（3）死锁的检测。这种方法对资源的分配如不加限制，即允许死锁发生。但系统定时地运行一个"死锁检测"程序，判断系统是否发生死锁，若检测到有死锁，则设法加以解除。
|
|
|
|
（4）死锁的解除。检测到死锁发生后，常采用资源剥夺法和撤销进程法解除死锁。
|
|
|
|
|
|
|
|
线程是比进程更小的能独立运行的基本单位。在引入线程的操作系统中，线程是进程中的一个实体，是系统独立分配和调度的基本单位。线程自己基本上不拥有资源，只拥有一点在运行中必不可少的资源（如程序计数器、一组寄存器和栈），但它可与同属一个进程的其他线程共享该进程所占用的全部资源。一个线程可以创建和撤销另一个线程，同一个进程中的多个线程之间可以并发执行。线程也同样有就绪、等待和运行3种基本状态。
|
|
|
|
|
|
|
|
（1）用户级线程。不依赖于内核，该类线程的创建、撤销和切换都不利用系统调用实现。
|
|
|
|
（2）内核支持线程。依赖于内核，即无论是用户进程中的线程，还是系统中的线程，它们的创建、撤销和切换都利用系统调用实现。
|
|
|
|
|
|
|
|
|
|
（1）调度。将线程作为调度和分配的基本单位，进程作为拥有资源的基本单位。
|
|
|
|
（2）并发性。不仅进程之间可并发执行，而且同一个进程中的多个线程之间也可并发执行。
|
|
|
|
（3）拥有资源。进程是拥有资源的一个独立单位，线程不拥有系统资源，但可访问隶属于进程的资源。
|
|
|
|
（4）系统开销。在创建或撤销进程时，由于系统都要为之分配和回收资源，导致系统的开销明显地大于创建或撤销线程时的开销。
|
|
|
