|
|
|
在单用户多任务的操作系统中，或者多用户多任务的操作系统中，系统同时运行多个程序，这些程序的并行运行势必形成对系统资源的竞争使用。因此，操作系统必须能够处理和管理这种并行运行的程序，使之对资源的使用按照良性的顺序进行。
|
|
|
|
|
|
进程是一个程序关于某个数据集的一次运行。进程是程序的一次运行活动，是一个动态的概念，而程序是静态的概念，是指令的集合。进程具有动态性和并发性，程序是进程运行所对应的运行代码，一个进程对应于一个程序，一个程序可以同时对应于多个进程。在操作系统中进程是进行系统资源分配、调度和管理的最小单位（注意，现代操作系统中还引入了线程（thread）这一概念，它是处理器分配资源的最小单位）。从静态的观点看，进程由程序、数据和进程控制块（Process Control Block，PCB）组成；从动态的观点看，进程是计算机状态的一个有序集合。
|
|
|
|
PCB是进程存在的唯一标志，PCB描述了进程的基本情况。其中的内容可分成为调度信息和执行信息两大部分。调度信息供进程调度使用，包括进程当前的一些基本属性；执行信息即现场，刻画了进程的执行情况。PCB随着进程的建立而产生，随着进程的完成而撤销。
|
|
|
|
一个进程从创建而产生至撤销而消亡的整个生命周期，可以用一组状态加以刻画，为了便于管理进程，把进程划分为几种状态，分别有三态模型和五态模型。
|
|
|
|
|
|
按照进程在执行过程中的不同状况，至少可以定义三种不同的进程状态：
|
|
|
|
|
|
（2）就绪态：具备运行条件，等待系统分配处理器以便运行。
|
|
|
|
（3）等待态（阻塞态）：不具备运行条件，正在等待某个事件的完成。
|
|
|
|
一个进程在创建后将处于就绪状态。每个进程在执行过程中，任一时刻当且仅当处于上述三种状态之一。同时，在一个进程执行过程中，它的状态将会发生改变。如下图所示为进程的状态转换。
|
|
|
|
|
|
|
|
运行状态的进程将由于出现等待事件而进入等待状态，当等待事件结束之后等待状态的进程将进入就绪状态，而处理器的调度策略又会引起运行状态和就绪状态之间的切换。引起进程状态转换的具体原因如下：
|
|
|
|
（1）运行态→等待态：等待使用资源，如等待外设传输；等待人工干预。
|
|
|
|
（2）等待态→就绪态：资源得到满足，如外设传输结束；人工干预完成。
|
|
|
|
（3）运行态→就绪态：运行时间片到；出现有更高优先权进程。
|
|
|
|
（4）就绪态→运行态：CPU空闲时选择一个就绪进程。
|
|
|
|
|
|
在三态模型中，总是假设所有的进程都在内存中。事实上，可能出现这样一些情况，例如由于进程的不断创建，系统的资源已经不能满足进程运行的要求，这个时候就必须把某些进程挂起，对换到磁盘镜像区中，使之暂时不参与进程调度，起到平滑系统操作负荷的目的。引起进程挂起的原因是多样的，主要有：
|
|
|
|
（1）系统中的进程均处于等待状态，处理器空闲，此时需要把一些阻塞进程对换出去，以腾出足够的内存装入就绪进程运行。
|
|
|
|
（2）进程竞争资源，导致系统资源不足，负荷过重，此时需要挂起部分进程以调整系统负荷，保证系统的实时性或让系统正常运行。
|
|
|
|
（3）把一些定期执行的进程（如审计程序、监控程序、记账程序）对换出去，以减轻系统负荷。
|
|
|
|
（4）用户要求挂起自己的进程，以便根据中间执行情况和中间结果进行某些调试、检查和改正。
|
|
|
|
（5）父进程要求挂起自己的后代子进程，以进行某些检查和改正。
|
|
|
|
（6）操作系统需要挂起某些进程，检查运行中资源使用情况，以改善系统性能；或当系统出现故障或某些功能受到破坏时，需要挂起某些进程以排除故障。
|
|
|
|
下图给出了具有挂起进程功能的系统中的进程状态。在此类系统中，进程增加了两个新状态：静止就绪态和静止阻塞态。为了区别，而把三态模型中的等待态改名为活跃阻塞态，就绪态改名为活跃就绪态。静止就绪态表明进程具备运行条件但目前在二级存储器（外存储器、外存、辅存）中，只有当它被对换到内存才能被调度执行。静止阻塞态则表明进程正在等待某一个事件且在二级存储器中。
|
|
|
|
|
|
|
|
|
|
（1）活跃阻塞态→静止阻塞态：如果当前不存在活跃就绪进程，那么至少有一个等待态进程将被对换出去成为静止阻塞态；操作系统根据当前资源状况和性能要求，可以决定把活跃阻塞态进程对换出去成为静止阻塞态。
|
|
|
|
（2）静止阻塞态→静止就绪态：引起进程等待的事件发生之后，相应的静止阻塞态进程将转换为静止就绪态。
|
|
|
|
（3）静止就绪态→活跃就绪态：当内存中没有活跃就绪态进程，或者静止就绪态进程具有比活跃就绪态进程更高的优先级，系统将把静止就绪态进程转换成活跃就绪态。
|
|
|
|
（4）活跃就绪态→静止就绪态：操作系统根据当前资源状况和性能要求，也可以决定把活跃就绪态进程对换出去成为静止就绪态。
|
|
|
|
（5）静止阻塞态→活跃阻塞态：当一个进程等待一个事件时，原则上不需要把它调入内存。但是，当一个进程退出后，内存已经有了一大块自由空间，而某个静止阻塞态进程具有较高的优先级并且操作系统已经得知导致它阻塞的事件即将结束，此时便发生了这一状态变化。
|
|
|
|
不难看出：一个挂起进程等同于不在内存的进程，因此挂起的进程将不参与进程调度，直到它们被对换进内存。一个挂起进程具有如下特征：
|
|
|
|
|
|
（2）挂起进程可能会等待一个事件，但所等待的事件是独立于挂起条件的，事件结束并不能导致进程具备执行条件。
|
|
|
|
（3）进程进入挂起状态是由于操作系统、父进程或进程本身阻止它的运行。
|
|
|
|
（4）结束进程挂起状态的命令只能通过操作系统或父进程发出。
|
|
|
|
（5）阻塞态：进入阻塞态通常是因为在等待I/O完成或等待分配到所需资源。
|
|
|
|
|
|
对于本知识点的考查，重点在于理解信号量与PV操作的基本概念，能够正确地理解在互斥、同步方面的控制应用，并能够灵活地运用，相对来说是个难点。
|
|
|
|
在操作系统中，进程之间经常会存在互斥（都需要共享独占性资源时）和同步（完成异步的两个进程的协作）两种关系。为了有效地处理这两种情况，W. Dijkstra在1965年提出信号量和PV操作。
|
|
|
|
（1）信号量：是一种特殊的变量，表现形式是一个整型S和一个队列。
|
|
|
|
（2）P操作：S=S-1，若S<0，进程暂停执行，进入等待队列。
|
|
|
|
（3）V操作：S=S+1，若S≤0，唤醒等待队列中的一个进程。
|
|
|
|
|
|
互斥控制是为了保护共享资源，不让多个进程同时访问这个共享资源，换句话说，就是阻止多个进程同时进入访问这些资源的代码段，这个代码段称为临界区，而这种一次只允许一个进程访问的资源称为临界资源。为了实现进程互斥地进入自己的临界区，代码可以写为：
|
|
|
|
|
|
由于只允许一个进程进入，因此信号量S的初值应该为1。该值表示可以允许多少个进程进入，当S<0时，其绝对值就是等待使用临界资源的进程数，也就是等待队列中的进程数。而当一个进程从临界区出来时，执行V操作（S=S+1），如果等待队列中还有进程（S≤0），则调入一个新的进程进入（唤醒）。
|
|
|
|
|
|
最简单的同步形式是进程A在另一个进程B到达L2以前，不应前进到超过点L1，这样就可以使用如下程序：
|
|
|
|
|
|
因此，要确保进程B执行V操作之前，不让进程A的运行超过L1，就要设置信号量S的初值为0。这样，如果进程A先执行到L1，那么执行P操作（S=S-1）后，则S<0，就停止执行。直到进程B执行到L2时，将执行V操作（S=S+1），唤醒A以继续执行。
|
|
|
|
|
|
生产者-消费者是一个经典的问题，它不仅要解决生产者进程与消费者进程的同步关系，还要处理缓冲区的互斥关系，因此通常需要3个信号量来实现，如下表所示。
|
|
|
|
|
|
|
|
如果对缓冲区的读写无须进行互斥控制的话，那么就可以省去mutex信号量。
|
|
|
|
|
|
信号量与PV操作的概念比较抽象，在历年的考试中总是难倒许多考生，其实主要还是没有能够正确地理解信号量的含义。
|
|
|
|
（1）信号量与PV操作是用来解决并发问题的，而在并发问题中最重要的是互斥与同步两个关系，也就是说只要有这两个关系存在，信号量就有用武之地。因此，在解题时，应该先从寻找互斥与同步关系开始。这个过程可以套用简单互斥、简单同步、生产者-消费者问题。
|
|
|
|
（2）通常来说，一个互斥或一个同步关系可以使用一个信号量来解决，但要注意经常会忽略一些隐藏的同步关系。例如，在生产者-消费者问题中，就有两个同步关系，一个是判断是否还有足够的空间给生产者存放产物，另一个是判断是否有足够的内容让消费者使用。
|
|
|
|
（3）信号量的初值通常就是表示资源的可用数。而且通常对于初始为0的信号量，会先做V操作。
|
|
|
|
（4）在资源使用之前，将会使用P操作；在资源用完之后，将会使用V操作。在互斥关系中，PV操作是在一个进程中成对出现的；而在同步关系中，则PV操作一定是在两个进程甚至是多个进程中成对出现的。
|
|
|
|
|
|
在考试时，可能会出现一些需要综合应用的问题，需要考生根据基本的概念，结合实际问题进行解答。
|
|
|
|
例如，在某并发系统中，有一个发送进程A、一个接收进程B、一个环形缓冲区BUFFER、信号量S1和S2。发送进程不断地产生消息并写入缓冲区BUFFER，接收进程不断地从缓冲区BUFFER取消息。假设发送进程和接收进程可以并发地执行，那么，当缓冲区的容量为N时，如何使用PV操作才能保证系统能够正常工作。发送进程A和接收进程B的工作流程如下图所示。请在下图中的①~④处填写正确的操作。
|
|
|
|
|
|
|
|
根据题意，很显然，这是一个“生产者-消费者”问题，根据该问题的特性，通常需要3个信号量来实现：两个用来管理缓冲区同步，信号量empty表示空闲缓冲区数量，初值为缓冲区最大数N，信号量full表示已填充缓冲区数量，初值为0；一个用于管理互斥，由信号量mutex保证只有一个进程在写缓冲区，初值为1。但在本题中，进程A和进程B允许并发地访问缓冲区，因此无须管理互斥，就不需要使用信号量mutex了。因此只需定义两个信号量：S1和S2，初值为N的S1在此承担的是信号量empty的功能，初值为0的S2在此则承担的是信号量full的功能。
|
|
|
|
通过这样的分析，不难得出结论：①处应该是P（S1），将空闲缓冲区数量减1；②处应该是V（S2），将已填充的缓冲区数量加1；③处则是P（S2）；④处为V（S1）。
|
|
|
在这个例子的基础上，如果系统中有多个发送进程和接收进程，进程间的工作流程如下图所示，其中空①~④的内容与上图相同。发送进程产生消息并顺序地写入环形缓冲区BUFFER，接收者进程顺序地从BUFFER中取消息，且每条消息只能读取一次。为了保证进程间的正确通信，增加了信息量SA和SB。请说明信息量SA和SB的物理意义，在下图中的⑤和⑥处填入正确的内容，并从下图的 ~①中选择4个位置正确地插入P（SA）、V（SA）、P（SB）和V（SB）。
|
|
|
|
|
|
|
|
上图所涉及的问题在普通的“生产者-消费者”问题上增加了一些复杂度：“系统中有多个发送进程和接收进程”，根据题意，我们可以得知它要完成的控制是：发送进程顺序写入，接收进程顺序读取，而且每条消息都只能够读取一次。这显然是两个互斥的问题，即多个发送进程在写缓冲区时是互斥关系，多个接收进程读缓冲区也是互斥关系。因此，信号量SA和SB分别实现这两个用来完成两个进程的互斥控制。
|
|
|
|
（1）SA：初值为1，表示允许同时对缓冲区进行写操作的进程数量。
|
|
|
|
（2）SB：初值为1，表示允许同时对缓冲区进行读操作的进程数量。
|
|
|
|
当然，两个对调也是可以的。在发送进程和接收进程中分别有一组信号量SA和SB的PV操作。因此，接下来的问题就是找插入点。互斥控制的要点在于判断出临界区的范围，也就是哪部分程序必须互斥进入，否则将出现问题。根据这一点，可以进行如下分析。
|
|
|
（1）发送进程：在进程产生消息之后准备写入缓冲区时，这时就需要进行互斥判断，因此在位置 应插入P（SA）；而直到完成“i=（i+1）mod N”操作后，才完成缓冲区操作，因此必须在位置 插入V（SA）。
|
|
|
（2）接收进程：由于接收进程是负责读数据的，如果数据区是空的则应该等待，因此必须先完成P（S2）操作，来决定其是否需要阻塞。如果没有阻塞时，再进入临界区，因此应该在位置 处操作P（SB）；而“对读取的消息进行处理”已显然在临界区之外，因此应该在位置 插入V（SB）。
|
|
|
|
|
|
死锁是指多个进程之间互相等待对方的资源，而在得到对方资源之前又不释放自己的资源，这样，造成循环等待的一种现象。如果一个进程在等待一个不可能发生的事件，则进程就死锁了。如果一个或多个进程产生死锁，就会造成系统死锁。
|
|
|
|
|
|
产生死锁的根本原因在于系统提供的资源个数少于并发进程所要求的该类资源数。产生死锁有4个必要条件：互斥条件、不可抢占条件、保持与等待条件（部分分配条件）、循环等待条件。
|
|
|
|
（1）互斥条件：即一个资源每次只能被一个进程使用。
|
|
|
|
（2）保持与等待条件：有一个进程已获得了一些资源，但因请求其他资源被阻塞时，对已获得的资源保持不放。
|
|
|
|
（3）不可抢占条件：有些系统资源是不可抢占的，当某个进程已获得这种资源后，系统不能强行收回，只能由进程使用完时自己释放。
|
|
|
|
（4）循环等待条件：若干个进程形成环形链，每个都占用对方要申请的下一个资源。
|
|
|
|
|
|
银行家算法是指在分配资源之前先看清楚资源分配后是否会导致系统死锁。如果会死锁，则不分配，否则就分配。
|
|
|
|
按照银行家算法的思想，当进程请求资源时，系统将按如下原则分配资源：
|
|
|
|
（1）当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程。
|
|
|
|
（2）进程可以分期请求资源，但请求的总数不能超过最大需求量。
|
|
|
|
（3）当系统现有的资源不能满足进程尚需资源数时，对进程的请求可以推迟分配，但总能使进程在有限的时间里得到资源。
|
|
|
|
（4）当系统现有的资源能满足进程尚需资源数时，必须测试系统现存的资源能否满足该进程尚需的最大资源数，若能满足则按当前的申请量分配资源，否则也要推迟分配。
|
|
|
|
对于这些内容，关键在于融会贯通地理解与应用，为了帮助考生更好地理解，下面，我们通过一个例子来说明银行家算法的应用。
|
|
|
|
假设系统中有三类互斥资源R1、R2和R3，可用资源数分别是9、8和5。在T0时刻系统中有P1、P2、P3、P4和P5五个进程，这些进程对资源的最大需求量和已分配资源数如下表所示。进程按照P1→P2→P4→P5→P3序列执行，系统状态安全吗？如果按P2→P4→P5→P1→P3的序列呢？
|
|
|
|
|
|
|
|
在这个例子中，我们先看一下未分配的资源还有哪些？根据试题给出的条件，从上表中可以看出，很明显，还有2个R1未分配，1个R2未分配，而R3全部分配完毕。
|
|
|
|
按照P1→P2→P4→P5→P3的顺序执行时，首先执行P1，这时由于其R1、R2和R3的资源数都未分配够，因而开始申请资源，得到还未分配的2个R1，1个R2。但其资源仍不足（没有R3资源），从而进入阻塞状态，并且这时所有资源都已经分配完毕。因此，后续的进程都无法得到能够完成任务的资源，全部进入阻塞，死锁发生了。
|
|
|
|
而如果按照P2→P4→P5→P1→P3的序列执行时：
|
|
|
|
（1）首先执行P2，它还差1个R2资源，系统中还有1个未分配的R2，因此满足其要求，能够顺利结束进程，释放出2个R1、2个R2、1个R3。这时，未分配的资源就是：4个R1、2个R2、1个R3。
|
|
|
|
（2）然后执行P4，它还差一个R3，而系统中刚好有一个未分配的R3，因此满足其要求，也能够顺利结束，并释放出其资源。因此，这时系统就有5个R1、4个R2、1个R3。根据这样的方式推下去，会发现按这种序列可以顺利地完成所有的进程，而不会出现死锁现象。
|
|
|
|
从这个例子中，我们也可以体会到，死锁的4个条件是如何起作用的。只要打破任何一个条件，都不会产生死锁。
|
|
|
|
|
|
|
|
（1）死锁预防：破坏导致死锁必要条件中的任意一个就可以预防死锁。例如，要求用户申请资源时一次性申请所需要的全部资源，这就破坏了保持和等待条件；将资源分层，得到上一层资源后，才能够申请下一层资源，它破坏了环路等待条件。预防通常会降低系统的效率。
|
|
|
|
（2）死锁避免：避免是指进程在每次申请资源时判断这些操作是否安全，例如，使用银行家算法。死锁避免算法的执行会增加系统的开销。
|
|
|
|
（3）死锁检测：死锁预防和避免都是事前措施，而死锁的检测则是判断系统是否处于死锁状态，如果是，则执行死锁解除策略。
|
|
|
|
（4）死锁解除：这是与死锁检测结合使用的，它使用的方式就是剥夺。即将某进程所拥有的资源强行收回，分配给其他的进程。
|
|
|
|
|
|
管程由管程名、局部子管程的变量说明、使用共享资源并在数据集上进行操作的若干过程，以及对变量赋初值的语句等4个基本部分组成。每一个管程管理一个临界资源。当有几个进程调用某管程时，仅允许一个进程进入管程，其他调用者必须等待，也就是申请进程必须互斥地进入管程。方法是通过调用特定的管程入口进入管程，然后通过管程中的一个过程使用临界资源。当某进程通过调用请求访问某临界资源而未能满足时，管程调用相应同步原语使该进程等待，并将它排在等待队列上。当使用临界资源的进程访问完该临界资源并释放之后，管程又调用相应的同步原语唤醒等待队列中的队首进程。为了表示不同的等待原因，设置条件变量，条件变量是与普通变量不同的变量，条件变量不能取任何值，只是一个排队栈。
|
|
|
|
线程是进程的活动成分，是处理器分配资源的最小单位，它可以共享进程的资源与地址空间，通过线程的活动，进程可以提供多种服务（对服务器进程而言）或实行子任务并行（对用户进程而言）。每个进程创建时只有一个线程，根据需要在运行过程中创建更多的线程（前者也可称“主线程”）。显然，只有主线程的进程才是传统意义下的进程。内核负责线程的调度，线程的优先级可以动态地改变。采用线程机制的最大优点是节省开销，传统的进程创建子进程的办法内存开销大，而且创建时间也长。
|
|
|
|
在多线程系统中，一个进程可以由一个或多个线程构成，每一线程可以独立运行，一个进程的线程共享这个进程的地址空间。有多种方法可以实现多线程系统，一种方法是核心级线程，另一种方法是用户级线程，也可以把两者组合起来。
|
|
|
|
多线程实现的并行避免了进程间并行的缺点：创建线程的开销比创建进程要小，同一进程的线程共享进程的地址空间，所以线程切换（处理器调度）比进程切换快。例如，Windows Server内核采用基于优先级的方案选定线程执行的次序。高优先级线程先于低优先级线程执行，内核周期性地改变线程的优先级，以确保所有线程均能执行。
|
|
|
