操作系统——进程间通信和调度

 

1.  进程间调度

进程经常需要与其他进程通信，就比如shell中的管道，一个进程的输出通过管道传给第二个进程。进程间通信简要来说，有三个问题，进程如何把信息传递给另一个，如何确保两个或更多的进程在关键活动中不会出现交叉，此外还需要保证进程执行的顺序性。

 

1.1  竞争条件

操作系统中协作的进程可能共享一些彼此都能够读写的公共存储区。这个公共存储区可能在内存中，也可能是一个共享文件。如果两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序，成为竞争条件（race condition）。

1.2     临界区

怎样避免竞争条件？凡涉及到共享内存、共享文件以及共享任何资源的情况都会引发竞争导致的错误，要避免这种错误，关键是要找出某种途径来阻止多个进程同时读写共享的数据。我们需要的是互斥，以某种手段来保证一个进程在使用一个共享变量时，其他进程不能做同样的操作。

 

我们把对共享内存访问的程序片段称作临界区域或临界区，如果我们能够适当地安排以使得两个进程不可能同时处于临界区中，就能够避免竞态条件。这样一个好的解决方案需要满足以下四个条件：

1. 任何两个进程不能同时处于其临界区；
2. 不应该对CPU的速度和数量作任何假设；
3. 临界区外运行的进程不得阻塞其他进程；
4. 不得使进程无限期等待进入临界区；

 

1.3        忙等待的互斥

本节中将会讨论几种实现互斥的方案。在这些方案中，当一个进程在临界区中共享更新共享内存时，其他进程将不会进入其临界区。

 

1.3.1屏蔽中断

单处理器系统中，最简单的方法是使每个进程刚刚进入临界区之后立即屏蔽所有中断，并在离开之前打开中断。屏蔽中断后，时钟中断也会被屏蔽。CPU只有在发生时钟中断或其他中断时才会进行进程切换。

 

这个方案并不好，把屏蔽中断的权利交给用户进程是不明智的。整个系统可能会因为某个进程不再次打开中断而导致终止，而且如果系统是多处理器，则屏蔽中断不会对其他的CPU有效。在一个多核系统中，屏蔽中断不会阻止其他CPU干预第一个CPU所做的操作。

 

另一方面，对内核来说，当它在更新变量或列表的几条指令期间将中断屏蔽是很方便的。所以结论是：屏蔽中断对于操作系统本身来说，是非常有用的一项技术，但对于用户进程则不是一种合适的通用互斥机制。

 

1.3.2锁变量

设想有一个共享变量，其初始值为0。当一个进程想要进入其临界区时，首先测试这把锁。如果该锁的值为0，则该进程将其设置为1并进入其临界区；如果该锁的值为1，则该进程等待直至该值变为0。

 

这种想法包含了与假脱机目录一样的疏漏。假设一个进程读出锁变量的值并发现它为0，而恰好在其值设置为1之前，另一个进程被调度运行，该锁变量变为1，则此时会存在两个进程进入同一个临界区。

 

1.3.3严格轮转法

下面的程序中，整型变量turn初始值是0，记录当前轮到哪个进程进入临界区，并检查或更新共享内存。开始时，a进程检查发现turn为0，于是进入临界区；进程b发现turn值为0，所以在一个等待的循环中不停测试turn直至该值变成1。

 

 

连续地测试直至某个值出现为止，称为忙等待，这种方式浪费CPU时间，应该避免。只有在有理由认为等待时间时非常短的情形下，才使用忙等待，用于忙等待的锁称为自旋锁。

 

该方案要求两个进程严格地轮流进入它们的临界区，该算法的确避免了所有的竞争条件，但是违反了条件3，不能作为一个很好的备选方案。

 

这种情况下违反了条件：进程被一个临界区之外的进程阻塞。

 

1.3.4Peterson解法

在使用共享变量（进入临界区）之前，各个进程使用其进程号0或1作为参数来调用enter_region，在需要时将使得进程等待，直到能够安全地进入临界区。完成对共享变量的操作之后，进程将调用leave_region，表示操作已经完成，其他希望进入临界区的进程现在可以进入。

 

 

该方案是如何工作的？一方面，没有任何进程处于临界区中，进程0调用enter_region，通过设置数组元素和将turn值设置成0标识希望进入临界区，由于进程1不想进入临界区，enter_region方法马上返回，如果进程1现在调用enter_region，进程1在此处挂起直到进程0退出临界区。

 

考虑两个进程几乎同时调用enter_region的情况，它们都将自己的进程号存入turn，但只有后被保存的进程号才有效，前一个被重写造成丢失。假设进程1是最后被写入的，则turn设置为1，当运行至while语句时，进程0将循环0次并进入临界区，而进程1则将不停地循环且不能进入至临界区，直到进程0退出临界区为止。

 

1.3.5TLS指令

某些计算机中都会有下面的指令：

TLS RX，LOCK

 

称为测试并加锁，它将一个内存字lock读到寄存器RX中，然后在该内存地址上存一个非零值。读字和写字保证是不可分割的，即该指令结束之前其他处理器均不允许访问该内存字。执行TSL指令的CPU将锁住内存总线，以禁止其他CPU在本指令结束之前访问内存。

 

锁住内存总线并不等于屏蔽中断，屏蔽中断并不能阻止其他处理器造成的影响。让第二个处理器远离内存直至第一个处理器完成的唯一方法就是锁住总线。

 

1.4        睡眠与唤醒

以上介绍的Peterson解法和TSL解法都是正确的，但它们都有忙等待的缺点，这些解法的本质上：当一个进程想进入其临界区，先检查是否可以进入，若不允许则该进程在原地等待直至允许为止。

 

这种方法不仅浪费CPU时间，还会引起其它例如优先级反转的问题：比如计算机中有两个进程H（优先级高）和L（优先级低）。调度规则规定，只要H处于就绪态它就可以运行。在某一时刻，L处于临界区中，此时H变为就绪态准备运行，现在H开始忙等待，但是由于当H就绪时L不会被调度，也就无法离开临界区，H将永远忙等待下去。

 

下面列举几条进程间通信原语，在无法进入临界区时将会阻塞而不是忙等待。sleep是一个将引起调用进程阻塞的系统调用，即被挂起，直到另外一个进程将其唤醒；wakeup调用有一个参数，即要被唤醒的进程。

 

在生产者——消费者问题模型中，两个进程共享一个公共固定大小的缓冲区，生产者将信息放入缓冲区中，消费者从缓冲区中取出消息。当缓冲区已满，如果此时生产者还想向其中放一个新的数据项，就让生产者睡眠，待消费者从缓冲区中取出一个或多个数据项时再唤醒它，同理对于消费者试图从一个空的缓冲区中取数据也是如此。

 

为了跟踪缓冲区的值，我们需要一个变量count来跟踪缓冲区中的数据项数。这里有可能会出现竞争条件，因为count的访问未加限制。sleep和wakeup原语之间可能会出现信号丢失，进而导致生产者与消费者都双双睡眠。一种快速的弥补手段就是加入唤醒等待位，实际就是wakeup信号的小仓库。但是当出现多个进程等待时，一个唤醒等待位就不够了，因此这并不能从根本上解决问题。

1.5        信号量

信号量使用一个整形变量来累计唤醒次数供以后使用。一个信号量的值可以为0（表示没有保存下来的唤醒操作）或者正值（一个或多个唤醒操作）。

 

信号量的提出者Dijsktra建议设置两种操作：down（sleep）和up（wakeup）。对一个信号量执行down操作，检查其值是否大于0。如果值大于0，则将其值减1并继续；如果值为0，则进程将睡眠，并且此时down操作并未结束，检查数值，修改变量值以及可能发生的睡眠操作均作为一个单一的、不可分割的原子操作完成。

 

up操作对信号量的值加1。如果一个或多个进程在该信号量上睡眠，无法完成先前的down操作，则由系统选择其中的一个并允许该进程完成其down操作。于是，对一个由进程在其上睡眠的信号量执行一次up操作之后，该信号量的值仍旧为0，信号量的值增1和唤醒一个进程同样也是不可分割的。不会有某个进程因执行up而阻塞。

 

用信号量解决丢失的wakeup问题，通常将up和down作为系统调用来实现，而且操作系统需要在执行以下操作时暂时屏蔽全部中断：测试信号量、更新信号量和需要时使某个进程睡眠。

 

该解决方案中，使用了三个信号量：full用来记录充满的缓冲槽数目；empty记录空的缓冲槽数目；mutex用来确保生产者和消费者不会同时访问缓冲区（二元信号量）。

 

信号量的另一种用途是用于实现同步，信号量full和empty用来保证某种事件的顺序发生或者不发生。生产者－消费者中，保证了当缓冲区满的时候生产者停止运行，已经当缓冲区空的时候消费者停止运行。

1.6        互斥量

如果不需要信号量的计数能力，可以使用信号量的简化版本，称为互斥量，仅仅适用于管理共享资源或一小段代码。互斥量是一个可以处于两种状态之一的变量：解锁和加锁。这样，只需要一个二进制位表示它，0表示解锁，其他所有值表示加锁。

 

2.   调度

计算机系统是多道程序设计系统，通常会有多个进程或线程同时竞争CPU。操作系统中，完成选择下一个进程执行的工作称作调度程序，使用的算法称作调度算法。很多适用于进程调度的处理方法同样适用于线程调度。

 

2.1       调度介绍

多数时间内只有一个活动进程，同CPU是稀缺资源时的年代相比，现在计算机速度极快，个人计算机的多数程序受到的是用户输入速率的限制，而不是CPU处理速率的限制。

 

几乎所有的进程的I/O请求或计算都是交替突发的，典型地，CPU不停顿地运行一段时间，然后发出一个系统调用以便读写文件。

 

典型的计算密集型进程具有较长时间的CPU集中使用和较小频度的I/O请求等待，I/O密集型进程具有较短时间的CPU集中使用和较长时间的I/O请求等待，随着CPU变得越来越快，更多的进程倾向于I/O密集型，这也意味着需要多运行一些这类进程以保持CPU的充分利用。

 

何时进行调度决策，需要调度处理的各种情形。第一，在创建一个新进程后，调度程序可以合法选择先运行父进程还是子进程；第二，在一个进程退出时必须做出调度决策，选择另外某个进程；第三，当一个进程阻塞在I/O和信号量上或由于其他原因阻塞时，必须选择其他进程运行；第四，在一个I/O中断发生时，必须做出调度决策。

 

非抢占式调度算法挑选一个进程，然后让该进程运行直至被阻塞，或者直到该进程自动释放CPU；抢占式调度算法挑选一个进程，并且让该进程运行某个固定时段的最大值，如果在该时段结束时，进程仍在运行就被挂起，而调度程序挑选另一个进程运行。

 

不同的环境需要不同的调度算法，不同的领域有着不同的目标，总体来说划分出三种环境：批处理，交互式，实时。

 

 

批处理系统中，不会有用户不耐烦地在终端等待请求的快速响应，因此，非抢占式算法，对每个进程都有长时间周期的抢占式算法是可以接受的，减少了进程的切换，改善性能。

 

交互式用户环境中，为了避免某个进程霸占CPU拒绝为其他进程服务，抢占是必需的，服务器也归于此类，通常它们要服务多个突发的远程用户请求。

 

在实时限制的系统中，抢占有时是不需要的，实时系统与交互式系统的差别是，实时系统只运行那些用来推进现有应用程序，而交互式系统是通用的，可以运行任意的非协作甚至是有恶意的程序。

 

考虑什么是一个好的调度算法，某些目标取决于环境，这取决于使用情形。在所有的情形中，公平是非常重要的，相似的进程应该得到相似的服务，不同的进程采取不同方式处理；另一个共同的目标是保持系统的所有部分都尽可能忙碌。

 

运行大量批处理作业的大型计算中心的管理者们为了掌握其系统的工作状态，通常检查三个指标：吞吐量、周转时间和CPU利用率；对于交互式系统，最重要的是最小响应时间，即从发出命令到得到响应之间的时间；对于实时系统，特点是或多或少必须满足截止时间。

 

2.2       批处理系统中的调度

在所有的调度算法中，最简单的是非抢占式的先来先服务算法。进程按照它们请求CPU的顺序使用CPU，有一个就绪进程的单一队列，第一个作业进入系统，就立即开始并允许运行它所期望的时间，不会中断该作业，其他作业进入时，被安排到队列的尾部。当正在运行的进程被阻塞时，队列中的第一个进程就接着运行，被阻塞的进程变成就绪时，就像新来的作业一样排到队列的末尾。

 

算法易于理解并且便于在程序中运行，但是当CPU密集型和I/O密集型一起进行调度时会出现问题。

 

当输入队列中有若干个同等重要的作业被启动时，调度程序应该使用最短作业优先算法。只有在所有的作业都可同时运行的情形下，最短作业算法才是最优化的（考虑作业的到达时间）。

 

最短作业优先的抢占式版本时最短剩余时间优先算法，调度程序总是选择剩余运行时间最短的那个进程运行，有关运行时间必须提前掌握，当一个新的作业到达时，其整个时间同当前进程的剩余时间做比较。如果新的进程比当前运行进程需要更少的时间，当前进程就被挂起，运行新的进程，这种方式可以使新的短作业获得良好的服务。

2.3        交互式系统中的调度

交互式系统中的调度在个人计算机、服务器和其他类系统中都是常用的。

 

2.3.1轮转调度

一种最古老、最简单、最公平且使用最广的算法是轮转调度。每个进程被分配一个时间段，称为时间片，即允许该进程在该时间段中运行。如果在该时间片结束时该进程还在运行，则将剥夺CPU并分配给另一个进程。如果该进程在时间片结束前阻塞或结束，则CPU立即进行切换。时间片轮转调度很容易实现，调度程序所要做的就是维护一张可运行进程列表，当一个进程用完它的时间片后，就被移到队尾的末尾。

 

时间片轮转调度中唯一有趣的一点是时间片的长度，从一个进程切换到另一个进程是需要一定时间进行管理事务处理的——保存和装入寄存器值及内存映像，更新各种表格，清楚和重新调入内存高速缓存等。假如进程切换，有时称为上下文切换，CPU时间会消耗一定时间浪费在管理开销上。

 

如果CPU时间片设置过长，浪费在管理开销上的时间会减少，但是如果当前一段非常短的时间出现多个请求时，假设所有其他进程都用足了它们的时间片的话，最不幸的最后一个进程在获得运行机会之前等待很长的时间。

 

时间片设置得过短会导致过多的进程切换，降低了CPU效率；而设置得过长又可能引起对短的交互请求的响应时间变长。

2.3.2优先级调度

轮转调度做了一个隐含的假设，即所有的进程同等重要，但一些外部因素可能会导致优先级调度，其基本思想很清楚：每个进程被赋予一个优先级，允许优先级更高的可运行进程先运行。

 

为了防止高优先级进程无休止地运行下去，调度程序可以在每个时钟中断降低当前进程的优先级。如果这个动作导致该进程的优先级低于次高优先级的进程，则进行进程切换。一个可用的方法是，每个进程被赋予一个允许运行的最大时间片，时间片用完，下一个次高优先级的进程获得机会运行。

 

可以很方便地将一组进程按优先级分成若干类，并且在各类之间采用优先级调度，而在各类进程的内部采用轮转调度，还需要偶尔对优先级进行调整，以避免低优先级进程产生饥饿现象。

 

2.3.3多级队列

为CPU密集型进程设置较长的时间片比频繁地分给它们很短的时间片要更高效，长时间片的进程又会影响响应时间，解决方法是设立优先级类，最高优先级类的进程运行一个时间片，属于次高优先级类的进程运行两个时间片，依此类推。当一个进程用完分配的时间片之后，被移到下一类。

 

2.3.4最短进程优先

对于批处理系统，由于最短作业优先常常伴随着最短响应时间，可以将其用于交互进程，交互进程遵循以下模式：等待－执行命令，如果我们能够将每一条命令的执行看作是一个独立的作业，我们通过首先运行最短的作业来使响应时间变短，唯一的问题就是如何从当前可运行进程中找出最短的那个进程。

 

2.3.5保证调度

一种完全不同的调度算法是向用户做出明确的保证，然后去实现它，比如若用户工作有n个用户登录，则用户将获得CPU处理的1/n，类似地作用于n个进程运行的单用户系统，每个进程分配相同的CPU时间。

 

为了实现所做的保证，系统必须跟踪各个进程自创建以来已使用多少CPU时间，然后计算进程应该获得的时间。

 

2.3.6彩票调度

给用户一个保证，然后实现它，这是个好想法，但是很难实现。有一个既可给出类似预测结果又有简单的实现方法的算法，称为彩票调度。其基本思想是，向进程提供各种系统资源的彩票，一旦需要做出一项调度决策时，随机抽出一张彩票，拥有这张彩票的进程获得调度。

 

2.3.7公平分享调度

以上我们考虑的都是各个进程自身，并不关注其所有者是谁，如果用户1启动9个进程，而用户2启动1个进程，那么用户1将得到90%的CPU时间。为了避免这种情况的发生，某些系统在调度处理之前考虑谁拥有进程这一重要因素。

2.4       实时系统的调度

实时系统是一种时间起着主导作用的系统。外部的一种或多种物理设备给了计算机一个刺激，计算机必须在一个确定的时间范围内做出响应。实时系统可以分为硬实时和软实时，前者的含义是必须满足绝对的截止时间，后者的含义是可以做出一定的容忍。

 

实时系统的调度可以是静态的或动态的，前者在系统开始运行之前作出调度决策；后者在运行过程中进行调度决策，只有在可以提前掌握所完成的工作以及必须满足的截止时间等全部信息时，静态调度才能工作，而动态调度不需要这些限制。

 

2.5     线程调度

当若干进程都有若干线程时，就存在两个层次的并行：进程和线程。这样的系统中调度处理有本质的差别，取决于使用用户级线程还是内核级线程。

 

用户级线程中，由于内核并不知道有线程的存在，内核还是与之前一样工作，选取一个进程，通过进程中的线程调度程序来决定具体哪个线程该执行，多道线程并不存在时钟中断，这个线程可以按照其意愿任意运行多长时间，直到时间片耗尽。

 

内核级线程中，内核选择一个特定的线程运行，不用考虑该线程属于哪个进程，对被选择的线程赋予一个时间片，超出则直接挂起该线程。

 

用户级线程和内核级线程之间的差别在于性能，用户级线程的线程切换需要少量的机器指令，而内核级线程需要完整的上下文切换；另一方面，在使用内核级线程中，一旦线程阻塞到I/O上就不需要像在用户级线程中那样将整个进程挂起。