Jialong's Blog
沉潜 自由 追寻幸福
现代操作系统学习日志——进程与线程

0. 操作系统概念

进程

地址空间

文件

输入输出

保护

shell

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

进程

在任何多道程序设计系统中,CPU由一个进程快速切换至另一个进程,使得每个进程各运行几十至几百毫秒。在某一瞬间,CPU只运行一个进程,但在1秒内CPU可能运行多个进程。

进程模型

计算机上所有可运行的软件,通常也包括操作系统,被组织成若干顺序进程。一个进程就是一个正在执行程序的实例。

进程的创建

进程的终止

进程的层次结构

UNIX中进程和它的所有子进程及后裔共同组成一个进程组

UNIX启动时初始化自己的方式:一个称为init的特殊进程出现在启动映像中,开始运行时读入一个说明终端数量的文件,接着为每个终端创建一个新进程,这些进程等待用户登陆,如果有一个用户登录成功,该登录进程就执行一个shell准备接受命令,所接受的这些命令会启动更多进程。以此类推,在整个系统中,所有进程都是属于以init为根的一棵树。

Windows中没有进程层次的概念,所有进程都是低位相等的。

进程的状态

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

进程的实现

线程

每个进程有一个地址空间和一个控制线程;但是,经常存在同一个地址空间中准并行运行多个控制线程的情况,这些线程就像是分离的进程(除共享地址空间外)。

线程的使用

并行实体拥有共享同一个地址空间和所有可用数据的能力,而多进程模型的地址空间不同。

线程比进程更轻量级,更容易创建、也更容易撤销。

另外如果存在大量计算和I/O处理,多个线程允许这些活动彼此重叠进行,加快执行速度。

举例

  • 字处理软件:
    • 与用户交互线程
    • 格式处理线程
    • 处理磁盘备份线程

经典的线程模型

在同一个进程中并行运行多个线程,是对在同一台计算机上并行运行多个进程的模拟。前一种情形下,多个线程共享共享同一地址空间和其他资源,后一种情形中,多个进程共享物理内存、磁盘、打印机和其他资源。因此由于线程具有进程的某些性质,所以有时被称为轻量级进程。

多线程用来描述在同一个进程中允许多个线程的情形,一些CPU已经有直接硬件支持多线程,允许线程切换在纳秒级完成。

所有线程共享同一地址空间,意味着它们也共享同样的全局变量。各个线程可以访问进程地址空间中的每一个内存地址,所以一个线程可以读、写或清除另一个线程的堆栈。线程之间是没有保护的,因为同一个进程的多个线程是为了相互合作的。除了共享地址空间,所有线程还共享同一个打开文件、子进程、定时器及相关信号。

每个进程中的内容:

  • 地址空间
  • 全局变量
  • 打开文件
  • 子进程
  • 定时器
  • 信号与信号处理程序
  • 账户信息

每个线程中的内容:

  • 程序计数器
  • 寄存器
  • 堆栈
  • 状态

和传统进程一样,线程可以处于若干种状态的任何一个:运行、阻塞、就绪或终止。正在运行的线程拥有CPU并且是活跃的,被阻塞线程正在等待某个释放它的事件。

认识到每个线程有其自己的堆栈很重要。每个线程的堆栈有一个帧,供各个被调用但还没有从中返回的过程使用。在该栈帧中存放了响应过程的局部变量以及过程调用完后使用的返回地址。通常每个线程会调用不同的过程,从而有一个各自不同的执行历史,因此每个线程需要有自己的堆栈。

一个常见的系统调用:thread_yield,允许线程自动放弃CPU而让另一个线程运行。这样的调用很重要,因为不同于进程,线程库无法利用时钟中断强制线程让出CPU。所以设法使线程随着事件推移自动交出CPU,并让其他线程有机会使用,就非常重要。

POSIX线程

为实现可移植的线程程序,IEEE定义了线程的标准。它定义的线程包叫做pthread。大部分UNIX系统都支持该标准,这个标准定义了超过60个函数调用。所有pthread线程都有某些特性,每一个都含有一个标识符、一组寄存器和一个存储在结构中的属性。这些属性包括堆栈大小、调度参数以及其他线程需要的项目。

以下是一些线程调用举例:

  • pthread_create:创建新线程并返回标识符,线程标识符为了让其他线程引用该线程
  • pthread_exit:结束调用的线程
  • pthread_join:等待一个特定线程的推出
  • pthread_yield:释放CPU来运行另一个线程
  • pthread_attr_init:创建并初始化一个线程的属性结构
  • pthread_attr_destroy:删除一个线程的属性结构

在用户空间中实现线程

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

把整个线程包放在用户空间时,内核对线程包一无所知。从内核的角度看就相当于单线程进程。

第一个优点是用户级线程包可以在不支持线程的操作系统上实现。可以用函数库实现线程。

线程是在一个运行时系统的上层运行,该运行时系统是一个管理线程的过程的集合。前面已经介绍过pthread_create、pthread_exit等过程。

用户空间管理线程时,每个进程需要有其专用的线程表,用来跟踪该进程中的线程。线程表与内核中的进程表类似,不过只记录每个线程的属性。该线程表由运行时系统管理。

用户线程的优点:

  • 线程切换要比陷入内核快一个数量级,保存线程状态的过程和调度程序都是本地过程,启动它们比进行内核调用效率高
  • 允许每个进程有自己的调度算法。同时用户级i安城具有较好的可扩展性。

缺点:

如何实现阻塞系统的问题。使用线程的一个主要目的:要允许每个线程使用阻塞调用,还要避免被阻塞的线程影响其他线程。发生缺页的故障时,在对所需的指令进行定位和读入时,相关进程就被阻塞。一个线程引起页面故障时,内核由于不知道有线程存在,通常会把整个进程阻塞直到磁盘I/O完成为止,尽管其他线程可以正常运行。

另一个问题是单独的一个进程内部没有时钟中断,只能等一个线程自动放弃CPU时其他线程才能使用。

在内核中实现线程

此时无需运行时系统,并且每个进程中也没有线程表。在内核中有用来记录系统中所有线程的线程表。当某个线程希望创建一个新线程或撤销一个已有线程时,它进行一个系统调用,这个系统调用通过对线程表的更新完成线程创建或撤销工作。

所有能阻塞线程的调用都以系统调用的形式实现,这与运行时系统相比,代价十分可观。当一个线程阻塞时,内核根据其选择,可以运行同一个进程中另一个线程(若有一个就绪线程)或运行另一个进程中的线程。而在用户级线程中,运行时系统始终运行自己进程中的线程,直到内核剥夺其CPU。

内核线程不需要任何新的、非阻塞系统调用。如果某个进程中的线程引起了页面故障,内核可以方便地检查该进程是否有其他就绪的线程,如果有就将其运行。这样做的缺点是系统调用的代价较大

混合实现

多个内核级线程和用户级线程多路复用。一些内核级线程被多个用户级线程多路复用,如同进程的用户级线程一样。每个内核级线程有一个可以轮流使用的用户级线程的集合。

调度程序激活机制

内核级线程在一些关键点上优于用户级线程,但速度远慢于用户级线程。人们设计了调度程序激活,来模拟内核线程的功能

弹出式线程

用来处理到来的消息,例如服务请求。

使单线程代码多线程化

进程间通信

0. 基本概念

消息传递小节以前介绍的内容都是共享存储相关的内容,主要是来实现同步和互斥机制。消息传递是第二种通信方式,使用send和receive原语进行传递,它们是系统调用,需要进入内核态。

IPC(Inter Process Communication)。以下有一些进程间通信有关的问题:

  • 一个进程如何把信息传递给另一个(共享存储、消息传递)
  • 确保两个或更多的进程在关键活动中不会出现交叉(互斥)
  • 正确的顺序(同步)

第一个问题对线程比较容易,因为它们共享同一个地址空间。另外两个问题同样适用于线程。

竞争条件

竞争条件是指两个或多个进程读写某些共享数据,最后的结果取决于进程运行的精确时序。多核增长带来的并行使得使得竞争条件越来越普遍。

临界区

涉及共享内存、共享文件及共享任何资源的情况都会引发与前面(竞争条件)类似的错误,我们要通过某种途径来阻止多个进程同时读写共享的数据,即我们需要的是互斥。用一种手段确保当一个进程在使用共享变量或文件时,其他进程不能做同样的操作。

我们把对共享内存进行访问的程序片段称为临界区,通过适当安排,使两个进程不可能同时处于临界区中,就能避免竞争条件。

这样的要求避免了竞争条件,但它不能保证使用共享数据的并发进程能够正确和高效地进行协作。一个好的解决方案需要满足:

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

忙等待的互斥

这里将会讨论几种互斥方案。当一个进程在临界区中更新共享内存时,其他进程将不会进入其临界区。

屏蔽中断

最简单的方法是每个进程刚刚进入临界区后立即屏蔽所有中断,并在离开前打开中断。

这个方案并不好,把屏蔽中断的权力交给用户是不明智的。若一个进程屏蔽中断后不再打开,系统可能终止。

另一方面,对内核来说,当其在更新变量或列表的几条指令期间将中断屏蔽很方便。

在多核系统中,屏蔽一个CPU中断不会阻止其他CPU干预第一个CPU所做的操作,因此我们需要更加复杂的计划。

锁变量

即408中学习的单标志法。是一种软件实现方法。

严格轮换法(自旋锁)

进程连续测试一个变量直到出现某个值为止,称为忙等待,这种方式浪费CPU时间,通常应该避免。用于忙等待的锁,称为自旋锁。该方案要求两个进程严格地轮流进入他们的临界区,任何一个进程都不可能在一轮中打印两个文件。

Peterson解法

防止两个进程进行无限等待,又设置了一个变量turn,每个变量在先设置自己的标志flag后再置turn标志。这时再同时检测另一个进程状态标志和允许进入标志,保证两个进程同时要求进入临界时只允许一个进程进入。该算法解决了饥饿现象。该算法是1和3的结合,利用flag实现临界资源的互斥访问,利用turn解决饥饿现象。

TSL指令

该指令需要硬件支持。

TSL RX, LOCK

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

为了使用TSL指令,要使用已给共享变量lock协调对共享内存的访问。当lock为0时任何进程都可以使用TSL指令将其设置为1,并读写共享内存。操作结束时,进程用一条普通move指令将lock的值重新设置为0.

睡眠与唤醒

Peterson和TSL或XCHG方法都正确,但有忙等待的缺点。

现在来考虑几条进程间通信原语,他们在无法进入临界区时将阻塞,而不是忙等待。最简单的时sleep和wakeup。

信号量

semaphore。P操作和V操作。对于信号量的操作都是单一的、不可分割的原子操作

用信号量问题解决生产者、消费者问题。

信号量可以用来实现同步、互斥操作。详见408笔记内容。

互斥量(mutex锁)

mutex。信号量的简化版本。互斥量是一个可以处于两态之一的变量:解锁和加锁。只需要一个二进制位表示。实际上常用一个整型量,0表示解锁,其他所有制表示枷锁。

互斥量使用两个过程。当一个进程或线程需要访问临界区时,调用mutex_lock,如果该互斥量当前是解锁的(临界区可用),则此调用成功,调用线程可以自由进入该区域。另外如果该互斥量已经加锁,则调用线程被阻塞,直到在临界区中的线程完成并调用mutex_unlock。

条件变量与互斥量

管程

一种高级同步原语。一个管程是一个由过程、变量即数据结构组成的一个集合,共同组成一个特殊的模块或软件包。进程可以任何需要的时候调用管程中的过程,但它们不能再管程之外声明的过程中直接访问管程内的数据结构。

任一时刻管程中只能有一个活跃的进程,这一特性使得管程能有效地完成互斥。

消息传递

这种方法使用两条原语send和receive,它们是系统调用。

调度

其他进程调度算法详见408相关内容。

线程调度

线程调度中考虑支持的是用户级线程还是内核级线程。

用户级线程

用户级线程的调度由运行时系统决定,一般使用轮转调度和优先级调度。局限是缺乏一个时钟中断运行过长的线程,但由于线程间的合作关系,也不算是问题。

内核级线程

用户级线程的切换只需要少量的机器指令,而内核级线程需要完整的上下文切换,修改内存映射,使高速缓存失效,导致了若干数量级的延迟。

另一方面使用内核级线程时,一旦线程阻塞在I/O上就不需要像在用户级线程中那样将整个进程挂起。

从进程A的一个线程切换到进程B的一个线程的代价高于运行进程A的第二个线程(必须修改内存映像,修改高速缓存的内容),内核对此是了解的,可以运用这些信息做出决定。

另一个因素是用户级线程可以使用专为应用程序定制的线程调度程序,内核线程不了解每个线程的作用,一般而言,应用定制的线程调度程序能够比内核更好地满足应用的需要。

经典IPC问题

哲学家就餐问题

读者-写者问题


最后修改于 2021-12-07