《现代操作系统》读书笔记——线程与进程

发布于 2020-06-06  535 次阅读


线程与进程

操作系统中最核心的概念是进程:这是对正在运行程序的一个抽象。

进程

进程是什么

在进程模型中,计算机上所有可运行的软件,通常也包括操作系统,被组织成若干顺序进程(sequentialprocess),简称进程(process)。一个进程就是一个正在执行程序的实例,包括程序计数器、寄存器和变量的当前值。从概念上说,每个进程拥有它自己的虚拟CPU。当然,实际上真正的CPU在各进程之间来回切换。但为了理解这种系统,考虑在(伪)并行情况下运行的进程集,要比我们试图跟踪CPU如何在程序间来回切换简单得多。正如在第1章所看到的,这种快速的切换称作多道程序设计

进程与程序

程序是静态的,进程是动态的,程序是存储在某种介质上的二进制代码,进程对应了程序的执行过程,系统不需要为一个不执行的程序创建进程,一旦进程被创建,就处于不断变化的动态过程中,对应了一个不断变化的上下文环境。

程序是永久的,进程是暂时存在的。程序的永久性是相对于进程而言的,只要不去删除它,它可以永久的存储在介质当中。

一个进程是某种类型的一个活动,它有程序、输入、输出以及状态。单个处理器可以被若干进程共享,它使用某种调度算法决定何时停止一个进程的工作,并转而为另一个进程提供服务。

进程的创建

有4种主要事件导致进程的创建:

  • 系统初始化。
  • 执行了正在运行的进程所调用的进程创建系统调用。
  • 用户请求创建一个新进程。
  • 一个批处理作业的初始化。

启动操作系统时,通常会创建若干个进程。其中有些是前台进程,也就是同用户(人类)交互并且替他们完成工作的那些进程。其他的是后台进程,这些进程与特定的用户没有关系。留在后台处理诸如电子邮件、Web页面、新闻、打印之类活动的进程称为守护进程(daemon)。

从技术上看,在所有这些情形中,新进程都是由于一个已存在的进程执行了一个用于创建进程的系统调用而创建的。

在UNIX系统中,只有一个系统调用可以用来创建新进程:fork。这个系统调用会创建一个与调用进程相同的副本。在调用了fork后,这两个进程(父进程和子进程)拥有相同的存储映像、同样的环境字符串和同样的打开文件。这就是全部情形。通常,子进程接着执行execve或一个类似的系统调用,以修改其存储映像并运行一个新的程序。

在UNIX中,子进程的初始地址空间是父进程的一个副本,但是这里涉及两个不同的地址空间,不可写的内存区是共享的。某些UNIX的实现使程序正文在两者间共享,因为它不能被修改,或者子进程共享父进程的所有内存,但是这种情况下内存通过写时复制(copy-on-write)共享,这意味着一旦两者之一想要修改部分内存,则这块内存首先要被明确的复制,以确保修改不会发生在私有内存区域。

进程的终止

终止的通常条件:

  • 正常退出(自愿的)。
  • 出错退出(自愿的)。
  • 严重错误(非自愿)。
  • 被其他进程杀死(非自愿)。(在UNIX中,这个系统调用是kill)

进程的状态

进程的三种状态:

  • 运行态(该时刻进程实际占用CPU)。
  • 就绪态(可运行,但因为其他进程正在运行而暂时停止)。
  • 阻塞态(除非某种外部事件发生,否则进程不能运行)。

image-20200606180425833

进程的三种状态之间有四种可能的转换关系,如图2-2所示。在操作系统发现进程不能继续运行下去时,发生转换1。在某些系统中,进程可以执行一个诸如pause的系统调用来进入阻塞状态。在其他系统中,包括UNIX,当一个进程从管道或设备文件(例如终端)读取数据时,如果没有有效的输入存在,则进程会被自动阻塞。

转换2和3是由进程调度程序引起的,进程调度程序是操作系统的一部分,进程甚至感觉不到调度程序的存在。系统认为一个运行进程占用处理器的时间已经过长,决定让其他进程使用CPU时间时,会发生转换2。在系统已经让所有其他进程享有了它们应有的公平待遇而重新轮到第一个进程再次占用CPU运行时,会发生转换3。调度程序的主要工作就是决定应当运行哪个进程、何时运行及它应该运行多长时间,这是很重要的一点,我们将在本章的后面部分进行讨论。已经提出了许多算法,这些算法力图在整体效率和进程的竞争公平性之间取得平衡。我们将在本章稍后部分研究其中的一些问题。

当进程等待的一个外部事件发生时(如一些输入到达),则发生转换4。如果此时没有其他进程运行,则立即触发转换3,该进程便开始运行。否则该进程将处于就绪态,等待CPU空闲并且轮到它运行。

image-20200606180609417

操作系统的最底层是调度程序,在它上面有许多进程。所有关于中断处理、启动进程和停止进程的具体细节都隐藏在调度程序中。实际上,调度程序是一段非常短小的程序。操作系统的其他部分被简单地组织成进程的形式。不过,很少有真实的系统是以这样的理想方式构造的。

进程的实现

为了实现进程模型,操作系统维护着一张表格(一个结构数组),即进程表(processtable)。每个进程占用一个进程表项。(有些作者称这些表项为进程控制块。)该表项包含了进程状态的重要信息,包括程序计数器、堆栈指针、内存分配状况、所打开文件的状态、账号和调度信息,以及其他在进程由运行态转换到就绪态或阻塞态时必须保存的信息,从而保证该进程随后能再次启动,就像从未被中断过一样。

image-20200606180722259

在了解进程表后,就可以对在单个(或每一个)CPU上如何维持多个顺序进程的错觉做更多的阐述。与每一I/O类关联的是一个称作中断向量(interruptvector)的位置(靠近内存底部的固定区域)。它包含中断服务程序的入口地址。假设当一个磁盘中断发生时,用户进程3正在运行,则中断硬件将程序计数器、程序状态字,有时还有一个或多个寄存器压入堆栈,计算机随即跳转到中断向量所指示的地址。这些是硬件完成的所有操作,然后软件,特别是中断服务例程就接管一切剩余的工作。

所有的中断都从保存寄存器开始,对于当前进程而言,通常是在进程表项中。随后,会从堆栈中删除由中断硬件机制存入堆栈的那部分信息,并将堆栈指针指向一个由进程处理程序所使用的临时堆栈。一些诸如保存寄存器值和设置堆栈指针等操作,无法用C语言这一类高级语言描述,所以这些操作通过一个短小的汇编语言例程来完成,通常该例程可以供所有的中断使用,因为无论中断是怎样引起的,有关保存寄存器的工作则是完全一样的。

image-20200606180812601

线程

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

线程的使用

人们需要多线程的主要原因是,在许多应用中同时发生着多种活动。其中某些活动随着时间的推移会被阻塞。通过将这些应用程序分解成可以准并行运行的多个顺序线程,程序设计模型会变得更简单。

  • 线程实现了并行实体共享同一个地址空间和所有可用数据的能力。

  • 线程比进程更轻量级,所以它们比进程更容易(即更快)创建,也更容易撤销。在许多系统中,创建一个线程较创建一个进程要快10~100倍。

  • 若多个线程都是CPU密集型的,那么并不能获得性能上的增强,但是如果存在着大量的计算和大量的I/O处理,拥有多个线程允许这些活动彼此重叠进行,从而会加快应用程序执行的速度。

  • 在多CPU系统中,多线程是有益的,在这样的系统中,真正的并行有了实现的可能。

一种困难的方式模拟了线程及其堆栈:每个计算都有一个被保存的状态,存在一个会发生且使得相关状态发生改变的事件集合,我们把这类设计称为有限状态机(finite-statemachine)

线程模型

进程用于把资源集中到一起,而线程则是在CPU上被调度执行的实体。

image-20200606181620000

传统进程一样(即只有一个线程的进程),线程可以处于若干种状态的任何一个:运行、阻塞、就绪或终止。

认识到每个线程有其自己的堆栈很重要,如图2-13所示。每个线程的堆栈有一帧,供各个被调用但是还没有从中返回的过程使用。在该帧中存放了相应过程的局部变量以及过程调用完成之后使用的返回地址。

image-20200606181843830

线程的实现-用户级别线程

有两种主要的方法实现线程包:在用户空间中和在内核中。

用户级别线程的一些优点:

  • 用户级线程包可以在不支持线程的操作系统上实现。
  • 线程切换至少比陷入内核要快一个数量级(或许更多)
  • 允许每个进程有自己定制的调度算法

用户级别线程的一些问题:

  • 单个线程阻塞导致整个进程阻塞
  • 如果一个线程开始运行,那么在该进程中的其他线程就不能运行,除非第一个线程自动放弃CPU。在一个单独的进程内部,没有时钟中断,所以不可能用轮转调度(轮流)的方式调度进程。

第一个,也是最明显的优点是,在用户空间管理线程时,每个进程需要有其专用的线程表(thread
table),用来跟踪该进程中的线程。这些表和内核中的进程表类似,不过它仅仅记录各个线程的属性,如每个线程的程序计数器、堆栈指针、寄存器和状态等。该线程表由运行时系统管理。当一个线程转换到就绪状态或阻塞状态时,在该线程表中存放重新启动该线程所需的信息,与内核在进程表中存放进程的信息完全一样。

image-20200606182114398

保存该线程状态的过程和调度程序都只是本地过程,所以启动它们比进行内核调用效率更高。另一方面,不需要陷阱,不需要上下文切换(这里仅仅是狭义上的上下文切换,广义上仍然需要上下文切换

上下文交换通常是计算密集型的,操作系统中的许多设计都是针对上下文交换的优化。在进程间切换需要消耗一定的时间进行相关的管理工作——包括寄存器和内存映射的保存与读取、更新各种内部的表等等。处理器或者操作系统不同,上下文交换时所涉及的内容也不尽相同。比如在Linux内核中,上下文交换需要涉及寄存器、栈指针、程序计数器的交换,但和地址空间的交换无关(虽然进程在进行上下文交换时也需要做地址空间的交换)[2][3]用户态线程之间也会发生类似的上下文交换,但这样的交换非常轻量。)

,也不需要对内存高速缓存进行刷新,这就使得线程调度非常快捷。

对于那些基本上是CPU密集型而且极少有阻塞的应用程序而言,使用多线程的目的又何在呢?由于这样的做法并不能得到任何益处,所以没有人会真正提出使用多线程来计算前n个素数或者下象棋等一类工作。

线程的实现-内核级别线程

内核的线程表保存了每个线程的寄存器、状态和其他信息。这些信息和在用户空间中(在运行时系统中)的线程是一样的,但是现在保存在内核中。这些信息是传统内核所维护的每个单线程进程信息(即进程状态)的子集。另外,内核还维护了传统的进程表,以便跟踪进程的状态。

由于在内核中创建或撤销线程的代价比较大,某些系统采取“环保”的处理方式,回收其线程。当某个线程被撤销时,就把它标志为不可运行的,但是其内核数据结构没有受到影响。稍后,在必须创建一个新线程时,就重新启动某个旧线程,从而节省了一些开销。

线程的实现-混合实现

采用这种方法,内核只识别内核级线程,并对其进行调度。其中一些内核级线程会被多个用户级线程多路复用。如同在没有多线程能力操作系统中某个进程中的用户级线程一样,可以创建、撤销和调度这些用户级线程。在这种模型中,每个内核级线程有一个可以轮流使用的用户级线程集合。

image-20200606183004686

通信

程间通信(Inter Process Communication,IPC),进程(线程)之间通信是为了解决多道程序开发中的可能会出现的与预期不相符的情形,这些情形出现的主要原因也是多进程(线程)之间没有正确的通信。

竞争条件

在一些操作系统中,协作的进程可能共享一些彼此都能读写的公用存储区。这个公用存储区可能在内存中(可能是在内核数据结构中),也可能是一个共享文件。

两个或多个进程读写某些共享数据,而最后的结果取决于进程运行的精确时序,称为竞争条件(racecondition)。调试包含有竞争条件的程序是一件很头痛的事。大多数的测试运行结果都很好,但在极少数情况下会发生一些无法解释的奇怪现象。多核增长带来的并行使得竞争条件越来越普遍。

临界区

阻止多进程读写共享数据的手段:互斥(mutual exclusion),即以某种手段确保当一个进程在使用一个共享变量或文件时,其他进程不能做同样的操作。

共享内存进行访问的程序片段称作临界区域(critical region)或临界区(critical section)。

保证使用共享数据的并发进程能够正确和高效地进行协作的四个条件:

  • 任何两个进程不能同时处于其临界区。
  • 不应对CPU的速度和数量做任何假设。
  • 临界区外运行的进程不得阻塞其他进程。
  • 不得使进程无限期等待进入临界区。

忙等待互斥

忙等待-乐观、阻塞-悲观

连续测试一个变量直到某个值出现为止,称为忙等待(busywaiting)。由于这种方式浪费CPU时间,所以通常应该避免。只有在有理由认为等待时间是非常短的情况下,才使用忙等待。用于忙等待的锁,称为自旋锁(spin lock)。

屏蔽中断

CPU只有发生时钟中断或其他中断时才会进行进程切换。

在单处理器系统中,最简单的方法是使每个进程在刚刚进入临界区后立即屏蔽所有中断,并在就要离开之前再打开中断。

屏蔽中断对于操作系统本身而言是一项很有用的技术,但对于用户进程则不是一种合适的通用互斥机制。

锁变量

作为第二种尝试,可以寻找一种软件解决方案。设想有一个共享(锁)变量,其初始值为0。当一个进程想进入其临界区时,它首先测试这把锁。如果该锁的值为0,则该进程将其设置为1并进入临界区。若这把锁的值已经为1,则该进程将等待直到其值变为0。于是,0就表示临界区内没有进程,1表示已经有某个进程进入临界区。

严格轮转法

在一个进程比另一个慢了很多的情况下,轮流进入临界区并不是一个好办法。

该方案要求两个进程严格地轮流进入它们的临界区,如假脱机文件等。任何一个进程都不可能在一轮中打印两个文件。尽管该算法的确避免了所有的竞争条件,但由于它违反了条件3,所以不能作为一个很好的备选方案。

Peterson解法

image-20200606184926407

TSL指令

可以在硬件 CPU 的支持下,保证锁变量的改变不被打断,使锁变量成为一种很好的解决进程互斥的方法。
目前大多数的计算机的 CPU,都支持 TSL 指令。

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

一个可替代TSL的指令是XCHG,它原子性地交换了两个位置的内容,例如,一个寄存器与一个存储器字。代码如图2-26所示,而且就像可以看到的那样,它本质上与TSL的解决办法一样。所有的Intel x8 CPU在
低层同步中使用XCHG指令。

睡眠与唤醒

原语的概念:

计算机进程的控制通常由原语完成。所谓原语,一般是指由若干条指令组成的程序段,用来实现某个特定功能,在执行过程中不可被中断。在操作系统中,某些被进程调用的操作,如队列操作、对信号量的操作、检查启动外设操作等,一旦开始执行,就不能被中断,否则就会出现操作错误,造成系统混乱。所以,这些操作都要用原语来实现 原语是操作系统核心(不是由进程,而是由一组程序模块组成)的一个组成部分,并且常驻内存,通常在管态下执行。原语一旦开始执行,就要连续执行完,不允许中断。

替代忙等(忙等消耗cpu)的睡眠唤醒机制。

信号量

它使用一个整型变量来累计唤醒次数,供以后使用。在他的建议中引入了一个新的变量类型,称作信号量(semaphore)。一个信号量的取值可以为0(表示没有保存下来的唤醒操作)或者为正值(表示有一个或多个唤醒操作)。

Dijkstra建议设立两种操作:down和up(分别为一般化后的sleep和wakeup)。对一信号量执行down操作,则是检查其值是否大于0。若该值大于0,则将其值减1(即用掉一个保存的唤醒信号)并继续;若该值为0,则进程将睡眠,而且此时down操作并未结束。检查数值、修改变量值以及可能发生的睡眠操作均作为一个单一的、不可分割的原子操作完成。保证一旦一个信号量操作开始,则在该操作完成或阻塞之前,其他进程均不允许访问该信号量。这种原子性对于解决同步问题和避免竞争条件是绝对必要的。所谓原子操作,是指一组相关联的操作要么都不间断地执行,要么都不执行。原子操作在计算机科学的其他领域也是非常重要的。

信号量的另一种用途是用于实现同步(synchronization)。

互斥量

如果不需要信号量的计数能力,有时可以使用信号量的一个简化版本,称为互斥量(mutex)。互斥量仅仅适用于管理共享资源或一小段代码。由于互斥量在实现时既容易又有效,这使得互斥量在实现用户空间线程包时非常有用。

快速用户区互斥量futex
pthread中的互斥量

管程

消息传递

一个分布式系统具有多个CPU,并且每个CPU拥有自己的私有内存,它们通过一个局域网相连,那么这些原语将失效。这里的结论是:信号量太低级了,而管程在少数几种编程语言之外又无法使用,并且,这些原语均未提供机器间的信息交换方法。所以还需要其他的方法。

上面提到的其他的方法就是消息传递(message passing)。这种进程间通信的方法使用两条原语send和receive,它们像信号量而不像管程,是系统调用而不是语言成分。因此,可以很容易地将它们加入到库例程中去。

屏障

最后一个同步机制是准备用于进程组而不是用于双进程的生产者-消费者类情形的。在有些应用中划分了若干阶段,并且规定,除非所有的进程都就绪准备着手下一个阶段,否则任何进程都不能进入下一个阶段。可以通过在每个阶段的结尾安置屏障(barrier)来实现这种行为。当一个进程到达屏障时,它就被屏障阻拦,直到所有进程都到达该屏障为止。屏障的操作如图2-37所示。

屏障可以用于一组进程的同步。

image-20200606190516840

避免锁:读-复制-更新

调度

调度简介

为了选取正确的进程运行,调度程序还要考虑CPU的利用率,因为进程切换的代价是比较高的。首先用户态必须切换到内核态;然后要保存当前进程的状态,包括在进程表中存储寄存器值以便以后重新装载。在许多系统中,内存映像(例如,页表内的内存访问位)也必须保存;接着,通过运行调度算法选定一个新进程;之后,应该将新进程的内存映像重新装入MMU;最后新进程开始运行。除此之外,进程切换还要使整个内存高速缓存失效,强迫缓存从内存中动态重新装入两次(进入内核一次,离开内核一次)。总之,如果每秒钟切换进程的次数太多,会耗费大量CPU时间,所以有必要提醒注意。

image-20200607090625380

进程行为

典型的计算密集型(compute-bound)进程具有较长时间的CPU集中使用和较小频度的I/O等待。I/O密集型(I/O-bound)进程具有较短时间的CPU集中使用和频繁的I/O等待。它是I/O类的,因为这种进程在I/O请求之间较少进行计算,并不是因为它们有特别长的I/O请求。

有必要指出,随着CPU变得越来越快,更多的进程倾向为I/O密集型。这种现象之所以发生是因为CPU的改进比磁盘的改进快得多,其结果是,未来对I/O密集型进程的调度处理似乎更为重要。这里的基本思想是,如果需要运行I/O密集型进程,那么就应该让它尽快得到机会,以便发出磁盘请求并保持磁盘始终忙碌。

进程调度的时机

  • 在创建一个新进程之后,需要决定是运行父进程还是运行子进程。
  • 在一个进程退出时必须做出调度决策。一个进程不再运行(因为它不再存在),所以必须从就绪进程集中选择另外某个进程。如果没有就绪的进程,通常会运行一个系统提供的空闲进程。
  • 当一个进程阻塞在I/O和信号量上或由于其他原因阻塞时,必须选择另一个进程运行。
  • 在一个I/O中断发生时,必须做出调度决策。如果中断来自I/O设备,而该设备现在完成了工作,某些被阻塞的等待该I/O的进程就成为可运行的就绪进程了。是否让新就绪的进程运行,这取决于调度程序的决定,或者让中断发生时运行的进程继续运行,或者应该让某个其他进程运行。
  • 如果硬件时钟提供50Hz、60Hz或其他频率的周期性中断,可以在每个时钟中断或者在每k个时钟中断时做出调度决策。

调度的目标

image-20200607090918359

交互系统中的调度

轮转调度

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

image-20200607091029725

假如进程切换(process switch),有时称为上下文切换(context switch),需要1ms,包括切换内存映像、清除和重新调入高速缓存等。再假设时间片设为4ms。有了这些参数,则CPU在做完4ms有用的工作之后,CPU将花费(即浪费)1ms来进行进程切换。因此,CPU时间的20%浪费在管理开销上。

时间片设得太短会导致过多的进程切换,降低了CPU效率;而设得太长又可能引起对短的交互请求的响应时间变长。将时间片设为20ms~50ms通常是一个比较合理的折中。

优先级调度
最短进程优先

策略和机制

调度机制(scheduling mechanism)与调度策略(scheduling policy)分离(著名的原则,Levin等人,1975),也就是将调度算法以某种形式参数化,而参数可以由用户进程填写。我们再来看一下数据库的例子。假设内核使用优先级调度算法,但提供一条可供进程设置(并改变)优先级的系统调用。这样,尽管父进程本身并不参与调度,但它可以控制如何调度子进程的细节。在这里,调度机制位于内核,而调度策略则由用户进程决定。

线程调度

当若干进程都有多个线程时,就存在两个层次的并行:进程和线程。在这样的系统中调度处理有本质差别,这取决于所支持的是用户级线程还是内核级线程(或两者都支持)。

image-20200607091613559

用户级线程和内核级线程之间的差别在于性能。用户级线程的线程切换需要少量的机器指令,而内核级线程需要完整的上下文切换,修改内存映像,使高速缓存失效,这导致了若干数量级的延迟。另一方面,在使用内核级线程时,一旦线程阻塞在I/O上就不需要像在用户级线程中那样将整个进程挂起。

经典IPC问题

哲学家就餐问题

读者-写者问题


面向ACG编程