进程是操作系统提供的最古老的也是最重要的抽象概念之一。即使CPU只有一个,但它们也具有支持(伪)并发操作的能力,它们将一个单独的CPU变换成多个虚拟的CPU。没有进程的抽象,现代计算机将不复存在。

进程模型:

进程模型中,计算机上所有可运行的软件,通常也包括操作系统,被组织成若干顺序进程(sequential  process),简称进程。一个进程就是一个正在执行程序的事例,包括程序计时器、寄存器和变量的当前值。

进程和程序间的区别是很微妙的,但非常重要。用一个比喻可以更容易理解这一点。想象一位有一手好厨艺的计算机科学家正在为他的女儿烘制生日蛋糕。他有做生日蛋糕的食谱,厨房里有所需的原料:面粉、鸡蛋、糖、香草汁等。在这个比喻中,做蛋糕的食谱就是程序(即用适当形式描述的算法),计算机科学家就是处理器(CPU), 而做蛋糕的各种原料就是输人数据。进程就是厨师阅读食谱、取来各种原料以及烘制蛋糕等系列动作的总和。

进程的创建:
4种主要时间会导致进程的创建

1)系统初始化。

2)正在运行的程序执行了创建进程的系统调用。 

3)用户请求创建一个新进程。 

4)一个批处理作业的初始化。

进程的终止:
进程迟早会终止,通常由下列条件引起

1)正常退出(自愿的)

2)出错退出(自愿的)

3)严重错误(非自愿)

4)被其他进程杀死(非自愿)
                                             

进程的层次结构:

某些系统,当进程创建了另一个进程后,父进程和子进程就以某种形式继续保持联系。子进程自身可以创建更多的进程,组成一个进程的层次结构。进程只有一个父进程(但可以有零个、一个、两个或多个子进程)。

进程的状态:

1)运行态(该时刻进程实际占用CPU

2)就绪态(可运行,但因为其他进程正在运行而暂时停止)

3)阻塞态(除非某种外部时间发生,否则进程不能运行)

前两种状态在逻辑上是类似的。处于这两种状态的进程都可以运行,只是对于第二种状态暂时没有CPU分配给它。第三种状态与前两种装态不同,处于该状态的进程不能运行,即使CPU空闲也不行。

进程的实现:

为了实现进程模型,操作系统维护着一张表格(一个结构数组),即进程表。每个进程占用一个进程选项。(有些称这些表项为进程控制块)

线程:

传统操作系统中,每个进程有一个地址空间和一个控制线程,事实上,这几乎就是进程的定义。不过,经常存在在同一个地址空间中准并行运行多个控制线程的情形,这些线程就像(差不多)分离的进程(共享地址空间除外)。

进程间通信:

例如在一个shell管道中,第一个进程的输出必须传送给第二个进程,这样沿着管道传递下去。因此进程之间需要通信,而且是一种结构良好的方式而不要使用中断。

  1. 竞争条件:即两个或多个进程读写某些共享数据,而最后的结果取决于进程运行的精神时序。称为竞争条件。
  2. 临界区:一个进程的一部分时间做内部计算或另外一些不会引发竞争条件的操作。在某些时候进程可能需要访问共享内存或共享文件,或执行另外一些会导致竞争的操作。把对内存进行访问的程序片段称作临界区域或临界区。
  3. 忙等待的互斥:在下面方案中,当一个进程在临界区中更新共享内存时,其他进程将不会进入其临界区,也不会带来任何麻烦。
    1)屏蔽中断
    2)锁变量
    3)严格轮换法
    4)Peterson解法
    5)TSL指令
  4. 睡眠与唤醒:举个例子,生产者-消费者(producer-consumer)问题,也称有界缓冲区(bouded-buffer)问题。两个进程共享一个公共的=固定大小的缓冲区。其中一个时生产者,将信息放入缓冲区;另一个是消费者,从缓冲区中取出信息。问题在于当缓冲区已满,而此时生产者还想向其中放入一个新的数据项的情况。其解决办法是让生产者睡眠,待消费者从缓冲区中取出一一个或多 个数据项时再唤醒它。同样地,当消费者试图从缓冲区中取数据而发现缓冲区为空时,消费者就睡眠,直到生产者向其中放入一些数据时再将其唤醒。
  5. 信号量:E.W.Dijkstra在1965年提出的一种方法,一个信号量的取值可以为0(表示没有保存下来的唤醒操作)或者为正值(表示有一个或多个唤醒操作)。
  6. 互斥量:如果不需要信号量的计数能力,有时可以使用信号量的个简化版本, 称为互斥量(mutex)。互斥量仅适用于管理共本资源或一小爱代码。 由于互斥量在实现时既容易又有效,这使得互斥量在实现户空间线程包时非常有用。
  7. 管程:为了更易于编写正确的程序,Brinch Hansen (1973)和Hoare (1974) 提出了一种高级同步原语,称为管程(monitor)。在下面的介绍中会发现,他们两人提出的方案略有不同。一个管程是一个由过程、 变量及数据结构等组成的一个集合,它们组成一个特殊的模块或软件包。进程可在任何需要的时候调用管程中的过程,但它们不能在管程之外声明的过程中直接访问管程内的数据结构管程有一个很重要的特性,即任一时刻管程中只能有一个活跃进程,这特性使管程能有效地完成互斥。
  8. 消息传递:这种进程通信的方法使用两条原语send和receive,它们像信号量而不像管程,是系统调用而不是语言成分。
  9. 屏障:在有些应用划分了若干阶段,并且规定,除非所有的进程都就绪准备着手下一个阶段,否则任何进程都不能进入下一个阶段。 可以通过在每个阶段的结尾安置屏障(barrier) 来实现这种行为。当一个进程到达屏障时,它就被屏障阻拦,直到所有进程都到达该屏障为止。屏障可用于一组进程同步。
  10. 避免锁:读-复制-更新

调度:

当计算机系统是多道程序设计系统时,通常就会有多个进程或线程竞争CPU。只要有两个或更多的进程处于就绪状态,这种情形就会发生。如果只有一个CPU可用,那么就必须选择下一个要运行的进程。操作系种中,完成选择工作的这一部分称为调度程序,该程序使用的算法叫调度算法

在早期以磁带上的卡片作为输入的批处理系统,那时调度算法很简单:一次运行磁带上的每一个作业。对于多道程序设计系统,调度算法复杂一些,因为有多个用户等候服务。

批处理系统的调度:

  1. 先来先服务:使用该算法,进程按照它们请求CPU的顺序使用CPU。
  2. 最短作业优先:一种适用于运行时间可以预知的另一个非抢占式的批处理调度算法。
  3. 最短剩余时间优先:使用这个算法,调度程序总是选择剩余运行时间最短的哪个进程运行。

交互式系统中的调度:

  1. 轮换调度:一种最古老、最简单、最公平且使用最广的算法是轮换调度(round robin)。每个进程被分配一个时间段,称为时间片(quantum),即允许该进程在该时间段中运行。如果在时间片结束时该进程还在运行,则将剥夺CPU并分配给另一个进程。
  2. 优先级调度:每个进程被赋予一个优先级,运行优先级最高的可运行进程先运行。
  3. 多极队列
  4. 最短进程优先
  5. 保证调度:一个完全不同的调度算法是向用户作出明确的性能保证,然后区实现它。
  6. 彩票调度:为进程提供各种系统资源(如CPU时间)的彩票。一旦需要做出一项调度决策时,就随机抽出一种彩票,拥有该彩票的进程获得该资源。
  7. 公平分享调度

实时系统中的调度:

实时系统是一种时间起着主导作用的系统,实时系统通常可以分为硬实时(hard real time)和软实时(soft real time),前者的含义是必须满足绝对的截止时间,后者的含义是虽然不希望偶尔错失截止时间,但是可以容忍。