文章目录
[隐藏]

内容主要摘录自《操作系统与设计原理》中文版第二部分:进程,详细内容请参考原文。

1 进程描述和控制

1.1 定义

进程定义:包含程序代码和代码相关联的数据集的两个基本元素所组成的实体,如果处理器开始执行这个程序代码,称这个执行实体为进程。

也有以下的几个定义:

  • 正在执行的程序;
  • 正在计算机上执行的程序示例;
  • 能分配给处理器并由处理器执行的实体;
  • 一组指令序列执行、一个当前状态和相关的系统资源集。

进程的组成元素包括:

  • 标识符;
  • 状态;
  • 程序计数器;
  • 上下文数据;
  • I/O状态信息;
  • 记账信息;

这些信息存放在进程控制块中,可以说进程是由程序代码和相关数据的进程控制块组成。

1.2 进程状态

  • 两状态进程模型

一个进程处于运行和未运行状态。操作系统利用某种方式跟踪进程,创建未运行状态的新进程时,未运行的进程保存在某种类型的队列中,并等待他们的执行时机,当前运行的进程不断被中断,操作系统中的分派器选择一个新进程运行,前一个进程从运行态转换到未运行态,另一个进程转换到运行态。

 

  • 五状态进程模型

对“两状态模型”进行改进,无论哪种进程行为模型,进程生存期总围绕进程的创建和终止,首先增加新建和终止这两个状态,其次,考虑到单个进程队列和分派器不适合处于阻塞状态进程的选择,将非运行状态拆分成就绪态和阻塞态。

进程创建场景:新的批处理作业、交互登录、操作系统提供一项新的服务、现有进程派生新进程。

进程终止场景:正常完成、超时、无可用内存、内存越界、错误访问受保护的资源、算术错误、I/O失败、无效指令、特权指令、数据误用、管理员或操作系统干涉、父进程终止、父进程请求终止子进程……

非运行状态拆分成就绪态和阻塞态:在两状态模型的单进程队列中存在就绪态等待执行的进程,也存在处于阻塞状态等待I/O操作结束的进程,利用FIFO策略,分派器永远筛选最老的进程,如果该最老进程被阻塞,后面未被阻塞的比较老的进程会卡在被阻塞的进程后面,事实上分配应该查找队列中未被阻塞并且在队列中时间最长的进程。解决该问题的方式是将非运行态拆分成就绪和阻塞状态。

注:就绪->退出 阻塞->退出状态图上未标出(父进程终止子进程的情况)。

对于分派改进策略是:维护就绪和阻塞两个队列,当一个正在运行的进程被移除处理器时,要么被终止,要么被放置在就绪或阻塞队列中,当一个事件发生时(如I/O),所有位于阻塞队列中等待这个事件的进程都被换到就绪队列中。如果在大型系统中,阻塞队列中进程比较多时,事件发生时进程搜索比较低效,可以按照事件维护多个阻塞队列,一个事件对应一个队列。另外,以上情况没有考虑到进程的优先级,如果按照进程优先级方案分派进程,维护多个优先级不同的队列,操作系统很容易确定就绪队列中优先级最好并且等待时间最长的进程。

  • 增加挂起状态的进程

交换的必要性:上一个模型中所有队列中的所有进程都必须驻留在内存中,但由于CPU计算速度比I/O操作快很多,内存中会存在大量的进程都在等待I/O,无论在单道程序设计还是多道程序设计中,大多数时候处理器仍处于空闲状态,一种解决方案是增大内存以容纳更多的进程,但这中方案一方面是内存价格增加的问题,另一方面是程序对内存空间需求的增加速度比内存价格下降(现在内存便宜发展速度仍赶不上应用对内容容量需求),现实是更大内存往往导致更大的进程而不是更多的进程,所以这个解决方案无法从根本上解决该问题;另一个解决方案是交换,OS将被阻塞的进程交换到硬盘中“挂起队列”中,即在硬盘中创建被挂起的进程队列。然后OS接下来可以取出挂起队列中的另一个进程(最老或优先级最高),或接受一个新进程。这里便引入了进程的“挂起”状态,见下图a)。

进一步细化位于外存中“挂起状态”,拆分为“阻塞/挂起”和“就绪/挂起”两种状态,详细如下

  • 阻塞/挂起:进程在外存中等待一个事件;
  • 就绪/挂起:进程在外存中,但只要被载入内存就可以执行。

新的进程状态转换模型如上图b)所示,以下为个别的状态转换说明:

  • 阻塞/挂起->就绪/挂起:如果等待事件发生,发生此转换;
  • 就绪/挂起->就绪:如果内存中没有就绪态的进程,操作系统需要调入一个进程继续执行,如果就绪/挂起态的进程比任何就绪态的优先级都要高时,发生次状态转换;
  • 就绪->就绪/挂起:通常,操作系统倾向于挂起阻塞态进程而不是就绪态进程,因为就绪态进程可以立即执行,并且阻塞态进程占用了空间去不能执行。但当释放一个就绪态进程可以得到足够的内存空间时,就会发生此转换。

挂起进程的特点:

  • 进程不能立即执行;
  • 进程可能是在等待一个事件,如果是,阻塞条件不依赖与挂起条件,阻塞事件的发生不会使进程立即执行;
  • 为阻止进程执行,可以通过代理把这个进程至于挂起状态,代理可以是进程自己,也可以是父进程和操作系统;
  • 除非代理显示地命令系统进行状态转换,否则进程无法从这个状态中转移。

进程被挂起的原因:

  • 内存交互:操作系统需要释放足够多的内存空间,以调入并执行就绪态的进程;
  • 其他OS原因:操作系统可能挂起后台进程或工具程序进程,或者被华裔导致问题的进程(比如死锁);
  • 交互式用户请求:用户可能希望挂起一个程序的执行,目的是为了调试或与一个资源的使用进行连接;
  • 定时:一个进程可能会周期性的执行,而且可能是在等待下一个时间间隔时被挂起;
  • 父进程请求:父进程可能会希望挂起后代进程的执行,以检查或修改挂起的进程,或者协调不同后代进程之间的行为。

1.3 进程描述

操作系统控制计算器系统内部的事件,它为处理器执行进程进行调度和分派,给进程分配资源,并响应用户程序的基本服务请求。那么操作系统为了控制进程和管理资源需要哪些信息呢?

操作系统为了管理进程和资源,必须掌握关于每个进程和资源当前状态的信息,并维护每个实体的信息表,主要包括内存、I/O、文件和进程四类信息表,如下图所示:

操作系统维护着内存表、I/O表、文件变和进程表。这四种表以某种方式链接起来或交叉引用。

进程控制结构:一个进程至少包括足够的内存空间、保存该进程的程序和数据,另外,程序执行通常设计用于跟踪过程调用和过程间参数传递的栈,与每个进程相关联的还有操作系统用于控制进程的许多属性,通常,属性的集合成为进程控制块(Process control block)。程序、数据、栈和属性集合(进程控制块)合称为进程映像(Process image)。

进程属性:

  • 标识符:PID、父进程PID和用户ID;
  • 用户可见寄存器:处于用户态的处理器执行的机器豫园可以访问的寄存器;
  • 控制和状态寄存器:程序计数器、条件码、状态信息;
  • 栈指针:每个进程有一个或多个与之相关联的后进先出(LIFO)系统栈,栈用于保存参数和过程调用或系统调用的地址,栈指针指向栈顶;
  • 调度和状态信息:进程状态、优先级、调度相关信息和事件;
  • 数据结构:进程可以以队列、环或者别的结构形式与其他进程进行链接,进程控制块为支持这些结构需要包含只想其他进程的指针;
  • 进程间通信:与两个独立进程间的通信相关联的各种标记、信号和信息。进程控制块中维护着某些或者全部此类信息;
  • 进程特权:进程根据其可以访问的内存空间以及可以执行的指令类型被赋予各种特权,特权还用于系统实时程序和服务的使用;
  • 存储管理:包括执行描述分配给该进程的虚拟内存空间的段表和页表的指针;
  • 资源的所有权和使用情况:进程控制的资源信息,调度器会使用这些信息。

处理器状态信息:包括处理器寄存器的内容,当一个进程正在进行时,器信息当然在寄存器中。当进程被中断时,所有的寄存器信息必须保存起来,使得进程恢复执行时的这些信息都可以被恢复。所涉及的寄存器的种类和数目取决于处理器的设计。通常,寄存器组包括用户可见寄存器、控制和状态寄存器和栈指针。

进程控制块的作用:进程控制块是操作系统中最重要的数据结构。每个进程控制块包含操作系统所需要的关于进程的所有信息。实际上,操作系统中的涉及调度、资源分配、中断处理、性能监控和分析的每个模块都可能修改进程控制块。在操作系统中很多例程都需要访问进程控制块中的信息时,一个重要的问题是如何保护它,主要原因是:

  • 一个例程中有错误,可能会破坏进程控制块,进而破坏了系统对受影响进程的管理能力;
  • 进程控制块的结构或语义的设计变化可能会影响到操作系统中的许多模块。

以上问题可以通过操作系统中所有例程都通过一个处理例程来专门处理,处理例程的任务仅仅是保护进程控制块,它是读写进程控制块的唯一的仲裁程序。使用这类进程,需要权衡性能问题和对系统软件剩余部分正确性的信任程度(?)。

1.4 进程控制

处理器的执行模式:大多数处理器至少支持两种执行模式,内核态(又称特权态、系统态、控制态)和用户态(非特权态)。

  • 内核态:某些指令只能在特权态下运行,包括读取或改变诸如程序状态字之类控制寄存器的指令、原始I/O指令和内存管理相关的指令。此外,有部分内存区域仅在特权态下可以被访问到;
  • 用户态:用户程序通常在该模式运行,不能访问内核态运行的一些资源。

使用这两种模式可以保护操作系统和重要的操作系统表(如进程控制块)不受用户程序的干涉,另外,内核态下,一些具有对处理器以及所有指令、寄存器和内存的控制能力,这一级的控制对用户程序是不需要的,为了安全起见限制用户程序进行访问。

处理器如何知道它在什么模式下执行以及如何改变这一模式呢?程序状态字中有一位表示执行模式,某些时间发生时这个标识位会发生改变。当用户调用一个操作系统服务或中断触发系统例程执行时,执行模式被设置成内核态,当从系统服务返回到用户进程时,执行模式被设置成用户态。

进程创建步骤:

  • 给新进程分配一个唯一的进程标识符;
  • 给进程分配空间;
  • 初始化进程块;
  • 设置正确的连接;
  • 创建或扩充其他数据结构。

进程切换的三个问题:何时发生进程切换?模式切换与进程切换有什么区别?为实现切换,操作系统必须对它控制的各种数据结构执行哪些操作?

(1)何时切换进程:进程切换可以在操作系统从当前正在运行的进程中获取控制权的任何时刻发生。进程执行中的中断机制包括:中断、陷阱和系统调用。

中断发生在当前正在运行的进程无关的某种类型的事件时的异步响应,包括如下:

  • I/O操作:操作系统确定是否发生了I/O活动,如果I/O活动是一个或多个进程正在等待的事件,操作系统就把所有相应的阻塞进程转化为就绪态,并决定是继续执行当前处于运行态的进程,还是让具有高优先级的就绪态进程抢占这个进程;
  • 时钟中断:操作系统确定当前正在运行的进程的执行时间是否已经超过了最大允许的时间片,如果超过了,进程必须切换到就绪态,调入另外一个进程;
  • 内存失效:处理器访问一个虚拟内存地址,并且此地址不在内存中,操作系统必须从外存中把这个引用的内存块调入内存中。

对于陷阱,发生在与当前指令相关的,操作系统会处理一个错误或异常条件,如果当前错误或异常条件致命,当前正在运行的进程被转换到退出状态,并发生进程切换;如果不致命,操作系统的动作取决于错误的种类和操作系统的设计,其行为可以是试图恢复或通知用户,操作系统可能会进行一次进程切换或者继续执行当前正在运行的进程。

对于系统调用,操作系统可能被来自正在执行的程序的系统调用激活。例如,一个用户正在运行,并且正在执行一条请求I/O操作的指令,如打开文件,这个调用导致转移到为操作系统代码的一部分的一个例程上执行。通常,使用系统调用会导致把用户进程置为阻塞态。

(2)模式切换

用户态到内核态之间的模式切换途径主要靠中断、异常和系统调用。中断阶段是指令周期的一部分。在中断阶段,处理器检查是否发生了任何中断,这通过中断信号来表示。如果没有未处理的中断,处理器继续取指令周期,即取当前进程中的下一条指令,如果存在一个未处理的中断,处理器需要做以下工作:

  • 把程序计数器置成中断程序的开始地址;
  • 从用户态切换到内核态,使得中断处理代码可以包含有特权的指令;

处理器现在继续取指阶段,并取中断处理程序的第一条指令,它将中断提供服务。此时,被中断的进程上下文保存在被中断程序的进程控制块中。那么保存上下文环境包括哪些信息呢?包括所有中断处理可能改变的信息和恢复中断程序所需要的信息。因此,必须保存称做处理器状态信息的进程控制块部分,这包括程序计数器、其他处理器寄存器和栈信息。中断处理器程序通常是执行一些与中断相关的基本任务的小程序。

进程控制块中其他信息如何处理?如果中断之后是切换到另一个应用程序,则需要做一些工作,但是,在大多数操作系统中,中断的发生并不是必须伴随进程切换的。可能是中断处理器执行之后,当前正在进行的进程继续执行。在这种情况下,所需要做的是当中断发生时保存处理器的状态信息,当控制返回给这个程序使恢复这些信息,在典型情况下,保存和恢复功能有硬件实现。

与进程切换的区别:发生模式切换可以不改变正在处于运行台的进程状态,保存上下文环境和以后恢复上下文环境只需要很少的开销。但是,如果当前正在运行的进程被转换到另一个状态(就绪、阻塞等),则操作系统必须使其环境产生是指性的变换。进程切换涉及到状态变化,因此比模式切换需要做更多的工作。(???)

(3)进程状态的变化

完成的进程切换步骤如下:

  • 保存处理器上下文环境,包括程序计数器和其他寄存器;
  • 更新当前处于运行态进程的进程控制块,包括将进程的状态改变到另一个状态(就绪态、阻塞态、就绪/挂起态或退出态)。还必须更新其他相关域,包括离开运行态的原因和记账信息;
  • 将进程的进程控制块移到相应的队列(就绪、在某事件处阻塞、就绪/挂起);
  • 选择另外一个进程执行,这方面的内容将进程的状态变为运行态;
  • 更新内存管理的数据结构,这取决于如何管理地址切换;
  • 恢复处理器在被选择进程的最近一次切换出运行状态时的上下文环境,这可以通过载入程序计数器和其他寄存器以前的值来实现。

2 进程和线程

2.1 线程概念

首先来看进程的两个特点:

  • 资源所有权:一个进程包括一个存放进程映像的虚拟地址空间;一个进程总是拥有对资源的控制或所有权,这些资源包括内存、I/O通道,I/O设备和文件。操作系统执行保护功能,以防止进程之间发生不必要的与资源相关的冲突;
  • 调度/执行:一个进程进程沿着通过一个或多个程序的一条执行路径执行。其执行过程可能与其他进程的执行过程交替进行。因此,一个进程具有一个执行状态和一个分配的优先级,并且是一个可悲操作系统调度和分派的实体。

以上两个特点是独立的,操作系统应该能够独立的处理他们。近期开发的操作系统已经可以这么做了。为了区分这两个特点,分派的单位通常称做线程或者轻量级进程,而拥有资源所有权的单位通常仍称做进程或任务。

2.2 多线程

多线程是指操作系统在单个进程内支持多个并发执行路径的能力,每个进程中只有一个线程在执行的传统方法成为单线程方法。

在多线程环境中,进程被定义为资源分配的单位和一个被保护的单位,与进程相关联的有:

  • 存放进程影响的虚拟地址空间;
  • 受保护地对处理器、其他进程(用于进程间通信)、文件和I/O资源(设备和通道)的访问。

在一个进程中,可能有一个或多个线程,每个线程有:

  • 线程执行状态(运行、就绪等);
  • 在未运行时保存的线程上下文,从某种意义上看,线程可以被看作进程内的一个被独立地操作的程序计数器;
  • 一个执行栈;
  • 用于每个线程局部变量的静态存储空间
  • 与进程内的其他线程共享的对进程的内存和资源的访问

从下图的单线程和多线程的进程模型中可以看出:进程的表示包括进程控制块和用户地址空间,以及在进程执行中管理调用/返回行为的用户栈和内核栈。当进程正在运行时,处理器寄存器将被该进程所控制,当进程不运行时,这些处理器寄存器的内容将被保存。在多线程环境中,进程仍然只有一个与之关联的进程控制块和用户地址空间。但是每个线程都有一个独立的栈,还有独立的控制块用于包含寄存器值、优先级和其他与线程相关的状态信息。

因此,进程中所有线程共享该进程的状态和资源,他们驻留在同一款地址空间中,并且可以访问到相同的数据。

从性能角度来看性能的优点:

  • 在一个已有的进程中创建一个新线程比创建一个全新进程所需的时间要少很多;
  • 终止一个线程比终止一个耗时少;
  • 同一个进程内线程间切换比进程间切换耗时少;
  • 线程提高了不同的执行程序间通信的效率,这是因为大多数OS中,独立进程间通信需要内核介入,用以提供保护和通信所需要的机制,但由于在同一个进程中线程共享内存和文件,无需调用内核进行通信。

服务器会处理很多请求(比如文件服务器),并将在短期内创建和销毁许多线程。如果服务器具有多个处理器,那么同一个进程中的多个线程可以同时在不同处理器上执行。如果进程或线程共享文件数据,操作系统需要系统它们的行为,使用线程和共享内存比使用进程和消息传递要快。

在单用户多处理器系统上使用线程的4个例子:

  • 前后台工:用户输入并回显;
  • 异步处理:比如文档编辑器的定时保存;
  • 执行速度:文件拷贝时计算传输速度;
  • 模块化程序结构:涉及多种活动或者多种输入输出的源和目的地的程序更易于用线程设计和实现。

在支持线程的操作系统中,调度和分派是在线程基础上完成的;因此大多数与执行相关的信息可以保存在线程级的数据结构中。但有些活动影响着进程中所有线程,操作系统必须在进程一级对它们进行管理。

2.3 线程功能特性

和进程一样,线程具有执行状态,并且可以相互之间进行同步。

(1)线程状态

和进程一样,线程的关键状态具有运行态、就绪态和阻塞态。

有4种与线程状态改变相关的基本操作:

  • 派生:通常,在派生一个新进程时,同时也为该进程派生一个线程。随后,进程中的线程可以在同一个进程中派生另外一个线程,并未新线程提on个指令指针和参数,新线程拥有自己的寄存器上下文和栈空间,且被放置在就绪队列中;
  • 阻塞:当线程需要等待一个事件时,它将被阻塞(保存它的用户寄存器、程序计数器和栈指针),此时处理器转而执行另外一个处于同一进程中或不同进程中的就绪线程;
  • 解除阻塞:当阻塞一个线程事件发生时,该线程被转移到就绪队列中。
  • 结束:当一个线程完成时,其寄存器上下文和栈都被释放。

为了不丧失线程的某些灵活性和能力,一个线程阻塞不会导致整个线程阻塞,也不会阻止其他线程的运行。

(2)线程同步

当一个进程中所有线程共享同一个地址空间和其他资源时,一个线程对资源的任何修改都会影响同一个进程的其他线程的环境,这时,需要同步同步各种线程的活动,从而避免线程间互不干涉且不破坏数据结构,线程同步带来的问题和使用的同步技术通常与进程同步相同,这些问题参考互斥同步、死锁及饥饿章节。

2.4 用户级和内核级线程

线程分为用户级线程和内核级线程,其中内核级线程又称为内核至此的线程或轻量级进程。

(1)用户级线程

在一个纯粹的用户级线程软件中,有关线程管理的所有工作都由应用程序完成,内核意识不到线程的存在,图4.6 a)展示一个纯粹的用户级线程的方法。任何应用程序都可以通过使用线程库设计成多线程程序。线程库是用于用户级线程管理的一个例程包,它包含了用于创建和销毁线程的代码,在线程间传递消息和数据的代码、调度线程执行的代码以及保存和恢复线程上下文的代码。

在默认情况下,应用程序从单线程开始,并在该线程中开始运行。该应用程序和它的线程被分配给一个由内核管理的进程。在应用程序正在运行的任何时刻,应用程序都可以派生一个在相同进程中运行的新线程。派生线程是通过调用线程库中的派生例程完成的。通过过程调用,控制权被传递给派生例程。线程库为新线程创建一个数据结构,然后使用某种调度算法,把控制权传递给该进程中处于就绪态的一个线程。当控制权被传递给线程库时,需要保存当前线程的上下文,然后当控制权从线程库中传递给一个线程时,将恢复那个线程的上下文。上下文实际上包括用户寄存器的内容、程序计数器和栈指针。

纯粹用户级的活动发生在用户空间,并且发生在一个进程内,内核并不知道这些活动,内核继续以进程为单位进行调度,并且给进程指定一个执行状态。下面通过一个例子说明图线程调度和进程调度的关系。

假设进程B在它的线程2中执行,进程和作为进程一部分的两个用户级线程1、2的状态如图4.7 a)所示,则可能发生以下任何一种情况:

  • 线程2中执行的应用程序进行系统调用,阻塞了进程B。例如,进行一次I/O调用。这导致控制转移到内核,内核启动I/O操作,把进程B置于阻塞状态,并切换到另一个进程。在此期间,根据线程库维护的数据结构,进程B的线程2仍处于运行状态,值得注意的是,从在处理器执行的角度看,线程2实际上并不处于运行状态,但从线程库的角度看,它处于运行状态,相应的状态图4.7 b);
  • 时钟中断把控制传递给内核,内核确定当正在运行的进程B已经用完了它的时间片,内核把进程B置于就绪态并切换到另一个进程。同时,根据线程库维护的数据结构,进程B的线程2处于运行态。相应的状态图如图4.7 c)所示;
  • 线程2运行到需要进程B的线程1执行到某些动作的一个点。此时,线程2进入阻塞态,而线程1从就绪态换到运行态,进程自身保留在运行态。相应的状态图如图4.7 d)s所示。

在上面第一种和第二种情况中,当内核将控制权为切换到进程B时,线程2会恢复执行,还需注意进程在执行线程库中的代码时可以被中断,或者是由于它的时间片用完了,或者是由于被一个更高优先级的进程所抢占。因此在中断时,进程可能处于线程切换的中间时刻,即正在从一个线程切换到另外一个线程。当该进程被恢复时,线程库得以继续运行,并完成线程切换并把控制权转移给进程中到另一个线程。

使用用户级线程而不是内核级线程既有优点,也有缺点。

优点:

  • 所有线程管理的数据结构都维护在一个进程的用户地址空间中,线程不需要内核态特权。减少了从用户态到内核态和从内核态到用户态的转换开销;
  • 可以做到为应用程序定制适合的调度算法而不受制于底层操作系统的调度程序;
  • 用户级线程可以在任何操作系统中运行,不需要对底层内核进行修改以支持用户级线程。线程库是一组供所有应用程序共享的应用程序级别的函数。

缺点:

  • 在典型的操作系统中,许多系统调用都会引起阻塞。因此,当用户级线程执行一个系统调用时,不仅这个线程会被阻塞,进程中所有线程都会被阻塞;
  • 在纯粹的用户级策略中,一个多线程应用程序不能利用多处理技术。内核一次只把一个进程分配给一个处理器,因此一个进程中只有一个线程可以执行。

克服缺点的方法:

  • 可以通过将应用程序写成一个多进程程序(会增加进程间切换的系统开销);
  • 采用jacketing技术:目标是把一个产生阻塞的系统调用转化成一个非阻塞的系统调用。

(2)内核级线程

在一个纯粹的内核线程软件中,有关线程的所有工作都是有内核完成的,应用程序部分没有进行线程管理的功能代码,只有一个到内核线程设施的应用程序编程接口(API)。Windows是这样方法的典型例子。

图4.6 b)中显示了纯粹的内核级线程。内核为进程机器内部的每个线程维护上下文信息。调度是由内核基于线程完成的。该方法可以克服用户级线程的两个缺点。但内核级线程的自身缺点是:在把控制从一个线程传送到同一个进程内的另一个线程时,需要到内核的状态切换。

一般的,使用内核级线程的多线程技术会比使用单线程的进程有明显的速度提升,使用用户级线程比内核级线程又有额外的提高。不过这个额外的提高是否真的能够达到,在实际情况中取决于应用程序的性质。如果应用程序的大多数线程切换都需要内核态的访问,那么基于用户级线程的方案不会比基于内核级线程的方案好多少。

(3)组合方案

如图4.6 c)所示,某些操作系统提供了一种组合的用户级线程/内核级线程设施。在组合的系统中,线程的创建完全在用户空间中完成,线程的调度和同步也是在应用程序中进行。一个应用程序中的多个用户级线程被映射到一些(小于或等于用户级线程的数目)内核级线程上。程序员可以为特定的应用程序和处理器调节内核级线程的数目,从而达到整体最佳的效果。

在组合方法中,同一个应用程序中的多个线程可以在多个处理器上并行的运行,某个会引起阻塞的系统调用不会阻塞整个进程。如果设计正确,该方法将会组合两个方法的优点,同时减少他们的缺点。

3 对称多处理SMP

随着计算机技术的发展和硬件价格的下降,计算机的设计越来越多的并行化,在微操作级别,同一个时间会有多个控制信号产生,指令流水线可以将取指操作和执行操作重叠起来,从而达到并行执行的效果。

3.1 SMP体系结构

4类不同结构的计算机系统:

  • 单指令单数据(SISD)流:单处理器执行单个指令流,对保存在单个内存中的数据进行操作;
  • 单指令多数据(SIMD)流:一个机器指令控制许多处理器部件一致地同时执行。每个处理器部件都有一个相关的数据内存,因此,每个指令由不同的处理器在不同的数据集合上执行。向量和阵列处理器都属于这一类(???);
  • 多指令单数据(MISD)流:一系列数据被传送到一组处理器上,每个处理器执行不同的指令程序。这个结构从未实现过。
  • 多指令多数据(MIMD)流:一组处理器同时在不同的数据集上执行不同的指令序列。

在MIMD结构中,处理器是通用的,处理器能够处理执行相应的数据转换所需的所有指令。MIMD可以根据处理器的通信方式进一步的细化。如图4.8所示:每个处理器都有一个专用内存,那么每个处理器部件都可以被看做一个独立的计算机。计算机键的通信或者借助于固定的路径,或者借助与某些网络设施,这类系统称做集群(cluster),或者多计算机系统。如果处理器共享一个共用内存,每个处理器都访问保存在共享内存中的程序和数据,处理器中间通过内存互相访问,则这类系统称为共享内存的多处理器系统。

共享内存的多处理器系统的一个常用分类是基于如何将进程分配给处理器。最基本的两种方法是主从(Master-Slave)和对称(Symmetrical Multi-Processing)。

在主从结构中,操作系统的内核总是在某个特定的处理器上运行,其他处理器主要用于执行用户程序,还可能执行一些操作系统的实用程序。主处理器负责调度进程和线程。但一个进程或线程活跃时,如果从处理器需要服务(如一次I/O调用),它必须给主处理器发送请求,,并等待服务的执行。这个方法优点是设计非常简单,只需要对单处理多道程序操作系统做少许改进。一个处理器控制了所有的内存和I/O资源,可以简化冲突的解决方案。该方法的缺点是:

  • 主处理器的失效将导致整个系统失败;
  • 由于主处理器必须单独完成所有的调度和进程管理,可能会造成性能瓶颈。

在对称多处理系统(SMP)中,内核可以在任何处理器上执行,并且通常每个处理器从可用的进程或线程池中进行自己的调度工作。内核可以由多进程和多线程构成,允许部分内核并行执行。SMP方法增加了操作系统的复杂性,它必须确保两个处理器不会选择同一个进程,并且确保进程不会由于某种原因从队列中丢失,因此必须采用相关技术以决定和同步对资源的占用声明。

3.2 SMP系统的组织结构

SMP的一般组织结构如下图所示,SMP中有多个处理器,每个都含有它自己的控制单元、算术逻辑单元和寄存器;每个处理器都可以通过某种形式的互联机制访问一个共享内存和I/O设备;共享总线就是一个通用方法。处理器可以通过内存(留在共享地址空间中的消息和状态信息)互相通信,还可以直接交换信号。内存通常被组织成允许同时有多个对内存不同独立部分的访问。

现代计算机的处理器通常至少具有专用的一级高速缓存。高速缓存的使用带来了新的设计问题。由于每个本地高速缓存包含一部分内存的映像,如果修改了高速缓存中的一个字,就需要将缓存中字设置为无效。为了避免这一点,当发生更新时,别的处理器必须被告知发生了更新,该问题是高速缓存的一致性问题,通常用硬件解决而不是有操作系统解决。

3.3 多处理器操作系统的设计总结

SMP操作系统管理处理器和其他计算机资源,使用户可以把整个系统看做是与多道程序单处理器系统相同形式。用户可以构造使用多进程和多线程的应用程序,而无需考虑用到一个处理器还是多个处理器。因此,多处理器操作系统必须提供多道程序系统的全部功能,另外再加上适用多个处理器的附加功能。关键设计问题如下:

  • 同时的并发进程或线程:为允许多个处理器同时执行相同的内核代码,内核例程必须是可重入大的(reentrant)。多个处理器执行内核的相同或不同部分,必须对内核表和管理结构进行合适的管理。以避免死锁或非法操作;
  • 调度:调度可以由任何处理执行,因此必须避免冲突。如果使用了内核级多线程,则可能出现在多个处理器上同时从同一个进程中调度多个线程的机会。
  • 同步:因为多个活动进程都可能访问共享地址空间或共享I/O资源,因而需要注意提供有效的同步。同步是保证互斥和事件排序的机制,锁是多处理器操作系统中一个通用的同步机制。
  • 存储管理:多处理器上的存储管理必须处理在单处理器机器上发现的所有问题,另外,为了达到最佳性能,操作系统需要尽可能的利用硬件并行性,如多端口内存,还必须协调不同处理器上的分页机制,以保证当多个处理器共享页或段时页面的一致性。以及决定页面置换的策略。
  • 可靠性和容错:当处理器失效时,操作系统应该提供适当的功能降低。调度程序和操作系统的其他部分必须知道处理器失效的情况,并且据此重新组织管理表。

多处理器操作系统设计问题的解决方案是在解决多道程序单处理器的设计问题的解决方案扩展而来的。

3.4 微内核

微内核是一个小型的操作系统核心,它由模块化扩展提供基础。

早期操作系统的设计由于缺乏对于大型软件系统的经验,并且对由于互相依赖和交互产生的问题估计过低,在这些单体结构的操作系统中,任何过程实际上都可以调用任何别的过程。当操作系统规模变大时,这种缺乏结构的设计方法就无法支持庞大的系统设计。这时需要模块化程序设计来解决软件开发规模的问题,这是就出现了分层的操作系统。

但分层方法也存在问题,典型的是一层中大的变化可能会对相邻层中的代码产生巨大影响,这些影响跟踪起来比较困难,在基本操作系统上很难通过增加或减少一些功能实现一个定制的版本。另外,由于相邻层之间的很多交互,也难以保证安全。

微内核的基本原理是,只有最基本的操作系统才能放在内核中。非基本的服务和应用程序在微内核之上构造,并且在用户态下执行。许多传统上属于操作系统一部分的功能都不在微内核中,包括设备驱动程序、文件系统、虚存管理程序、窗口系统和安全服务,他们可以与内核交互,也可以互相交互。

如下图所示,微内核结构用一个水平分层的结构代替了传统的纵向分层的结构。在微内核外部的操作系统部件被当作服务器进程实现,它们可以借助于通过微内核传递消息来实现相互之间的交互。因此,微内核起着验证信息、部件间喘息消息并授权访问硬件等信息交换的作用。微内核还执行保护功能:除非允许交换,否则它阻止信息传递。

微内核的优点:

  • 接口一致性:进程无需区分内核级服务还是用户级服务,所有服务全部通过消息传递提供;
  • 可扩展性:对新的硬件设别和新的软件技术友好,允许增加新的服务以及在同一个功能区域中提供多个服务;
  • 灵活性:不仅可以增加功能,还可以根据实际需要删减现有的功能;
  • 可移植性:在微内核中,所有或者至少大部分处理器专用代码都在微内核中。当把系统移植到一个处理器上时只需要很少的改变;
  • 可靠性:模块化的设计增加了大型软件产品的可靠性。小的微内核可以被严格的测试。少量API提供高质量的代码。
  • 分布式系统支持:如果分布式系统被配置为所有的进程和服务都具有唯一的标识符,那么实际上在微内核级别上可以看做只有一个单独的系统映像;
  • 面向对象操作系统环境:许多微内核设计都朝着面向对象的方向发展。例如Windows把面向对象的原理融入到微内核的设计中。

微内核的设计:必须包括直接依赖与硬件的功能,以及那些支持服务程序和应用程序在用户态的功能,这些功能可以分为以下几类:低级存储管理、进程间通信(IPC)以及I/O和中断管理。

  • 低级存储管理:控制硬件概念上的地址空间,使得操作系统可以在进程级别上实现保护。微内核只要负责把每个虚拟页映射到一个物理页框,而存储管理的大部分功能,包括保护一个进程的地址空间免于另一个进程的干涉,页面置换算法以及其他分页逻辑都可以在内核外实现。
  • 进程间通信:微内核操作系统之间或线程之间进行通信的基本形式是消息。一般情况下,进程间通信基于与进程相关联的端口。
  • I/O和中断管理:在微内核结构中,可以做到以消息的方式处理硬件中断和把I/O端口包含到地址空间中。微内核可以识别中断但不处理中断,它产生一条消息给该中断相关联的用户级进程。

4 并发性:互斥和同步

操作系统的核心设计问题是关于进程和线程的管理:

  • 多道程序设计技术:管理单个处理器系统中的多个进程;
  • 多处理技术:管理多个处理器系统中的多个进程;
  • 分布式处理技术:管理多台分布式计算机系统中的多个进程的执行,典型例子是集群。

并发是所有问题的基础,也是操作系统的设计基础。并发包含的设计问题有:进程间通信、资源共享与竞争(如内存、文件、I/O访问等)、多个进程活动的同步、分配给进程的处理器时间等。这些问题既出现于多处理器环境和分布式处理器环境中,也会出现于单处理器的多道程序设计中。

并发会在以下三种不同的上下文中出现:

  • 多个应用程序:多道程序设计允许在多个活动的应用程序间动态共享处理器时间;
  • 结构化应用程序:作为模块化设计和结构化程序设计的扩展,一些应用程序可以被有效的设计成一组并发程序;
  • 操作系统结构:同样的结构化程序设计可用于系统程序员,操作系统自身常作为一组进程和线程来实现。

4.1 并发原理

在单处理多道程序设计系统中,如图2.12a),进程交替进行,呈现出貌似同时并行执行的外部特征,虽然没有实现真正的并行处理,并且在进程间切换也需要一定的系统开销,但这种交替执行在处理效率和程序结构上仍带来了重要的好处。在多处理器系统中,不仅可以交替执行进程,而且可以重叠执行进程,如图2.12b所示。

从表面上看,交替和重叠代表了完全不同的执行模式和不同的问题。实际上,这两种技术都是并行处理的实例,都代表了同样的问题。在单处理的情况下,这些问题源于多道程序设计系统的一个基本特征:进程的相对执行数度不可预测,它取决于其他进程的活动、操作系统处理中断的方式以及操作系统的调度策略。这带来了以下问题:

  • 全局资源的共享充满了危险;
  • 操作系统很难对资源进行进行最优化分配;
  • 定位程序设计错误是非常困难的。

上述的问题同样存在域多处理器中,这样的系统中进程执行的相对速度同样不可预测。多处理系统还必须处理多个进程同时执行所引发的问题。从根本上说,这些问题和单处理器系统中是相同的。

即使在单处理系统下,共享全局变量被多个进程访问时,如果共享全局变量的保护做的不好,原因是中断可能会在进程中任何地方停止指令的执行,这是会发生并发问题。在多处理器系统中,同样存在保护共享资源的问题,不仅同单处理器一样的条件下会引发并发问题,而且当两个进程同时执行并且都试图访问同一个全局变量时,也会引发并发问题。这两类问题的解决方案是相同的:控制对共享资源的访问。

竞态条件发生在多个进程或线程读写数据时,其最终的结果是依赖与多个进程的指令执行顺序。

并发所带来的操作系统设计与管理的问题,主要有:

  • 操作系统必须能够记住每个活跃进程,这可以通过进程控制块来实现;
  • 操作系统必须为每个活跃进程分配和释放各种资源,有时,多个进程都想访问相同的资源,这些资源包括:
    • 处理器时间
    • 存储器
    • 文件
    • I/O设备
  • 操作系统必须保护每个进程的数据和物理资源,避免其他进程的无意干涉,这涉及与存储器、文件和I/O设备相关的技术。
  • 一个进程的功能和输出结果是必须与执行速度无关。

如何解决与执行速度无关的问题,首先需要考虑进程间交互的方式。进程之间相互知道的程度有三种,据此对进程间交互进行分类:

  • 进程之间相互不知道对方的存在:一些独立的进程,例如多个独立进程的多道程序设计,可以批处理作业,也可以是交互式会话。尽管这些进程不一起工作,但操作系统需要知道它们对资源的竞态情况,例如操作系统必须控制两个无关的应用程序同时想访问同一个磁盘、文件或打印机;
  • 进程间接知道对方的存在:这些进程并不需要知道对方的进程ID、但它们共享某些对象,如一个I/O缓冲区。这类进程在共享同一个对象时表现出合作行为;
  • 进程直接知道对方的存在:这些进程可以通过进程ID互相通信,用于合作完成某些活动。同样,这类进程表现出合作行为。

实际条件并不像以上那么清晰,几个进程可能既表现出竞争,有表现出合作。然而,对操作系统而言,需要分别检查以上每一种情况,并确定它们的本质。

(1)进程间的资源竞争:竞争资源包括I/O设备、存储器、处理器时间和时钟。竞争进程面临三个控制问题:互斥、死锁和饥饿。

假设两个或 更多的进程访问一个不可共享的资源,在执行过程中,每个进程都会给这个资源发送命令、接受资源的状态信息,发送数据和接收数据,我们把这类资源称为临界资源,使用该资源的那一部分程序称为程序的临界区。一次只有一个程序在临界区中。

死锁:两个进程P1和P2,两个资源R1和R2,假设每个进程执行部分功能都需要访问这两个资源,那么出现死锁的情况是:操作系统把R1分配给P2,把R2分配给P1,每个进程都在等待另一个资源,且在获得其他资源并完成前,谁都不会释放自己已经拥有的资源。

饥饿:假设三个进程P1、P2、P3周期性访问一个资源R,如果操作系统只P1、P2轮流访问资源R,P3无限期的拒绝访问资源,尽管没有发生死锁,但P3一直处于饥饿状态。

(2)进程间的通过共享合作:通过共享进行合作的情况,包括进程间在互相访问不确切指导对方情况下进行交互。例如,多个进程可能访问一个共享变量、共享文件或数据库,进程可能使用并修改共享变量而不涉及其他进程,但知道其他进程也可能访问同一个数据。因此,进程必须合作,以确保他们共享的数据得到正确的管理。控制机制必须确保共享数据的完整性。

由于数据保存在资源中,因此同样涉及到互斥、死锁和饥饿等控制问题。此外,还有一个新需求:数据一致性。

(3)进程间通过通信合作:在前两种情况下,每个进程都有自己的独立环境,不包括其他进程,进程间交互是间接的,并且都存在共享。当进程通过通信合作时,各个进程都与其他进程进行连接,通信提供了同步和协调各种活动的方法。一般情况下,通信可由各种类型的消息组成,发送消息和接受消息的原语由程序设计语言提供,或者由操作系统的内核提供。由于传递消息的过程没有共享任何对象,因而这类合作不需要互斥,但仍然存在死锁和饥饿的问题。

死锁:两个进程都可能被阻塞,每个都在等待来自对方的通信,这时发生死锁。

饥饿:假设三个进程P1、P2和P3。P1不断尝试与P2、P3通信,P2和P3都视图与P1通信,如果P1和P2不断的交换信息,而P3一直被阻塞,等待与P1通信,由于P1一直是活跃的,因此虽然不存在死锁,但P3一直处于饥饿状态。

4.2 互斥

为了提供对互斥的支持,互斥的要求主要有:

  • 必须强制互斥:在与相同资源或共享对象的临界区有关的所有进程中,一次只允许一个进程进入临界区;
  • 一个在非临界区停止的进程不能干涉其他进程;
  • 绝不允许出现需要访问临界区的进程被无限延迟的情况,即不会产生死锁或饥饿;
  • 当没有进程在临界区中时,任何需要进入临界区的进程必须立即进入;
  • 对相关进程的执行速度和处理器数目没有任何的要求和限制;
  • 一个进程驻留在临界区中的时间必须是有限的。

有许多方法可以满足这些互斥条件,一种方法是让由并发执行的进程担负这个责任,这类进程,不论是系统程序还是应用程序,都需要与另一个进程合作,而不需要程序设计语言或操作系统提供任何支持来实施互斥,这种是软件方法,尽管会增加开销或缺陷,但通过分析这类方法,可以更好的理解并发处理的复杂性。第二种方法是设计专门的机器指令,这种方法的优点是可以减少开销,但很难成为一种通用的解决方案。

硬件支持的互斥:

  • 中断禁用:在单处理器中,并发进程不能重叠,只能交替。此外,一个进程将一直运行,直到他调用了一个系统服务或被中断。因此为保证互斥,只需要保证一个进程不被中断就可以,这可以通过系统内核为启用和禁用中断定义的原语来提供。由于临界区不能被中断,所有可以保证互斥,但这个方法使处理器被限制只能交替执行程序,因此执行的效率将会有明显的降低,另外,该方法不能用于多处理器结构中。当一个计算机系统包含多个处理器时,一般会有多个进程同时执行,禁用中断是无法保证互斥的;
  • 专用的机器指令:在多处理器配置中,几个处理器是共享内存的。这种情况下,不存在主从关系,处理器间的行为是无关的,表现出一种对等关系,处理器之间没有支持互斥的中断机制。在硬件级别上,对存储单元的访问排斥对相同单元的其他访问。基于这一点,处理器的设计者提出了一些转悠机器指令,用于保证两个动作的原子性,如在一个指令周期中对一个存储器单元的读和写或者读和测试。在该指令执行过程中,任何其他指令访问内存都将被阻止,而且这些动作在一个指令周期中完成(???)。比较和交换指令是两种常见的交换指令。 机器指令的方法特点如下:
    • 适用于在单处理器或共享内存的多处理器上的任何数目的进程;
    • 非常简单且易于证明
    • 可用于支持多个临界区,每个临界区可以用它自己的变量定义。
    • 使用了忙等待:当一个进程正在等待进入临界区时,它会继续消耗处理器时间
    • 可能饥饿:当一个进程离开一个临界区并且有多个进程正在等待时,选择哪一个等待进程是任意的,因此,某些进程可能是被无限制的拒绝进入
    • 可能死锁:考虑单处理中的下列情况,进程P1执行专门指令并进入临界区,然后P1被中断并把处理器让给具有更高优先级的P2,如果P2试图使用同一资源,由于互斥机制,它将被拒绝访问。因此,它会进入忙等待循环。但是P1比P2的优先级低,它将永远不会被调度执行。

前面满足互斥的软件和硬件方法都存在缺陷,需要寻找其他机制。

4.3 信号量

4.4 管程

4.5 消息传递

4.6 读者-写者问题

5 并发:死锁和饥饿

5.1 死锁的原理

5.2 死锁的预防

5.3 死锁的避免

5.4 死锁的检测

5.5 一种综合的死锁策略

5.6 哲学家就餐问题