一文详解操作系统进程管理

  • 1. 什么是进程
  • 2. 进程模型
    • 2.1 PCB
    • 2.2 进程状态
      • 2.2.1 五状态模型
      • 2.2.2 七状态模型
      • 2.2.3 进程切换
    • 2.3 进程组织
      • 2.3.1 线性表
      • 2.3.2 链表
      • 2.3.3 索引
  • 3. 线程
    • 3.1 线程结构
    • 3.2 线程状态
  • 4.进程调度
    • 4.1 几种调度方式
      • 4.1.1 长程调度
      • 4.1.2 中程调度
      • 4.1.3 短程调度
    • 4.2 进程调度算法
      • 4.2.1 先来先服务
      • 4.2.2 时间片轮转调度
      • 4.2.3 最短作业优先
      • 4.2.4 最短剩余时间优先
      • 4.2.5 优先级调度
      • 4.2.6 多级反馈队列调度
  • 5.进程间通信
    • 5.1 共享内存
    • 5.2 管道
    • 5.3 信号
    • 5.4 消息
    • 5.5 信号量
  • 6 总结
  • 7. 参考资料

1. 什么是进程

进程即正在运行的程序的一个实例

当启动一个程序,程序会从磁盘被读取到内存,CPU 再从内存中读取指令,对其解码,然后执行指令(比如两数相加,访问内存,检查条件,跳转函数等)。完成这条指令后,CPU 继续重复上述操作。这样子就可以实现一个 CPU 可以对一个进程,以一对一的形式进行指令读取与执行。

一文详解操作系统进程管理

我们把操作系统做某件事,抽象成一种概念,称之为一个任务。一个进程可以对应一个任务,也可以对应多个任务。

早期的计算机只有一个 CPU,多个任务需要运行怎么办?需要依次排队等待,串行执行,一个任务执行完毕,才能执行下一个。这种方式存在着明显的弊端,假设排在前面的 A 任务需要执行5小时,而排后面的B任务仅需要1分钟,那么 B 任务必须等待 A 任务5小时完成后,才能执行,这种方式显得极其不灵活。

后来就有了多任务系统,在CPU同一时间只能处理一个任务的前提下,每个任务有一定的执行时长,比如任务A执行0.001s,切换到任务B执行0.05s,再切换到任务C执行0.01s…不断循环。这种机制也就可以在一定程度上解决上述任务B需要长时间等待的问题。

一文详解操作系统进程管理

由于 CPU 速度非常快,这种多个任务不断切换,会给用户一种任务并行执行的错觉,这种也被称为是伪并行调度。既然有伪并行,那么也会有真并行。在现代计算机中,常见的CPU核数可以达到8核甚至更多,操作系统可将每一个核视为一个CPU,那么8核CPU就可以真并行执行8个任务。还有更进一步的,即一个计算机内,有多个CPU。至于多个CPU与多核的区别,感兴趣的读者可以参考多核 CPU 和多个 CPU 有何区别?。

那么我们继续基于伪并行进一步探讨。伪并行虽然可以解决上述任务等待的问题,但是依然还存在一系列未解之谜:
– 每个任务应该执行多长时间?
– 如何找到要执行的下一个任务?
– 有些任务涉及了资源操作,执行到一半,切换任务,那么这些资源怎么办?
……

为了解决上面一系列谜题,我们需要一种模型对任务进行详尽的描述记录。一个进程可以对应一个任务,也可以对应多个任务,当前还未涉及多线程,我们可以在此先把进程和任务当作是一对一的关系(这并不是为了理解而创造出来的一种暂时错误的假设)。下面我们将进一步探讨关于进程更详细的内容,这些内容将有助于解释上面的问题。

2. 进程模型

2.1 PCB

对于一个被执行的程序,操作系统会为该程序创建一个进程。进程作为一种抽象概念,可将其视为一个容器,该容器聚集了相关资源,包括地址空间,线程,打开的文件,保护许可等。而操作系统本身是一个程序,有一句经典的话 程序 = 算法 + 数据结构,因此对于单个进程,可以基于一种数据结构来表示它,这种数据结构称之为进程控制块(PCB),有一些教材也将其称为进程表。不同的操作系统,PCB中包含的信息存在差异,大体上都会包含这些信息(该图来自《现代操作系统》)。

一文详解操作系统进程管理

2.2 进程状态

那么什么原因会导致进程会被创建,从而生成PCB呢?常见的有以下几种
1. 系统初始化
2. 用户通过系统提供的API创建新进程
3. 批处理作业初始化 (什么是批处理作业)
4. 由现有进程派生子进程

一个进程,因为某种原因被创建了,那么它可以按照以下步骤进行一系列的初始化
1. 给新进程分配一个进程ID
2. 分配内存空间
3. 初始化PCB
4. 进入就绪队列

2.2.1 五状态模型

一文详解操作系统进程管理

如图,进入就绪队列,其状态就会变为就绪态。各个状态之间的关系描述如下:

就绪 -> 运行:当操作系统内存在着调度程序,当需要运行一个新进程时,调度程序选择一个就绪态的进程,让其进入运行态。

运行 -> 就绪:运行态的进程,会占有CPU(参照一开始的饼状图)。每个进程会被分配一定的执行时间,当时间结束后,重新回到就绪态。

运行 -> 阻塞:进程请求调用系统的某些服务,但是操作系统没法立即给它(比如这种服务可能要耗时初始化,比如I/O资源需要等待),那么它就会进入阻塞态。

阻塞 -> 就绪:当等待结束了,就由阻塞态进入就绪态。

运行 -> 终止:当进程表示自己已经完成了,它会被操作系统终止。

这便是对于单个进程,经典的五状态模型。当存在多个进程时,由于同一时间只能有一个进程在执行,那么如何去管理这一系列的处于阻塞态和就绪态的进程呢?一般来说,会使用就绪队列,和阻塞队列,让处于阻塞态和就绪态的进程进入队列,排队执行。下图是一个单一阻塞队列模型。

一文详解操作系统进程管理

基于此,还可以扩展出多个就绪队列,每个优先级对应一个队列,这样子操作系统在选择要调度哪一个进程时,可以有更大的灵活性。下面将进一步探讨队列与进程之间如何组织管理。也可以有多条阻塞队列,每一个事件对应一个阻塞队列,当事件发生时,该队列所有进程都进入就绪态。

2.2.2 七状态模型

上面所讲的进程状态存在一个前提:每个进程都必须完全载入内存。一旦排队的进程多了,对于有限的内存空间将会是极大的考验。为了解决内存占用问题,可以将一部分内存中的进程交换到磁盘中,这些被交换到磁盘的进程,会进入挂起状态,进一步还可细分为就绪/挂起,阻塞/挂起。对于单个进程的状态转换如下图。

一文详解操作系统进程管理

整体上对于挂起队列的转换关系,如下图。

一文详解操作系统进程管理


关于图中的几种调度,将会在下面第4章进一步描述。

2.2.3 进程切换

当一个正在运行中的进程被中断,操作系统指定另一个就绪态的进程进入运行态,这个过程就是进程切换,也可以叫上下文切换。

该切换过程一般涉及以下步骤:
1.保存处理器上下文环境:将CPU程序计数器和寄存器的值保存到当前进程的私有堆栈里
2.更新当前进程的PCB(包括状态更变)
3.将当前进程移到就绪队列或者阻塞队列
4.根据调度算法,选择就绪队列中一个合适的新进程,将其更改为运行态
5.更新内存管理的数据结构
6.新进程内对堆栈所保存的上下文信息载入到CPU的寄存器和程序计数器,占有CPU

2.3 进程组织

每一个PCB表示一个进程,多个进程同时存在时,需要一定的方式将这些PCB组织起来,便于操作系统访问。常见的组织方式有如下3种。

2.3.1 线性表

一文详解操作系统进程管理


所有的PCB存放于一张线性表中,每次查找时需要遍历线性表。比较适用于进程数量不多的情况,如果有几百上千个进程,每次操作都进行遍历,那将是十分耗时的。

2.3.2 链表

一文详解操作系统进程管理

上面提到的就绪队列和阻塞队列,他们可以以链表的形式组织。从图中可以看出就绪队列指向PCB1,PCB1右边的数字“2”表示链表指向的下一个节点PCB2。依此类推,PBC以如下链表形式串联起来。

执行指针 -> PCB4
就绪队列指针 -> PCB1 -> PCB2 -> PCB3 -> PCB5
阻塞队列指针 -> PCB7 -> PCB8 -> PCB6

优点:非常直观,进程调度查找起来方便。

缺点:查找的时候需要从链表的头部开始进行遍历。如果进程状态发生变化,那么链表中进程节点的指针指向需要发生变动。

2.3.3 索引

一文详解操作系统进程管理

优点:基于链表的方式进行进一步的优化,通过索引查找进程,可以将查找的时间复杂度由O(n)优化到O(1)。如果进程状态发生变化,只需要操作索引表,相比于操作整个链表更便捷。

缺点:建立了索引表,需要额外的内存空间。相当于是利用空间去换取时间。

3. 线程

3.1 线程结构

基于前面所描述,进程包含了两大特点:
1. 资源所有权:进程是一个容器,聚集了内存,I/O 设备,文件等资源,拥有这些资源的控制或所有权。
2. 调度/执行:具有执行状态(运行,就绪,阻塞等),可被操作系统的调度程序所调度。

早期的操作系统中,一般一个进程内只有一个线程,即为单线程进程模型。如下图,其中所包含的用户栈和内核栈,用于管理调度和返回的行为。当进程不运行的时候,CPU的寄存器中的内容将被保存起来,以便于下一次运行该进程时,恢复当时的状态。

一文详解操作系统进程管理

那么为什么需要多线程?

  1. 许多应用同时发生着多种活动,其中一些活动会被阻塞,将进程进一步分解为多个线程,可以更灵活地处理各种类型的活动。
  2. 线程更加轻量级,创建和终止速度更快,且线程之间切换的速度会比进程切换更快。
  3. 对于一些 I/O 密集型任务,多个线程允许这些并排执行,加快整体的速度。对于CPU密集型任务多线程没这个优势,因为本质上CPU同一时间只做一件事(什么是CPU密集型、I/O密集型?)。
  4. 线程间通信的效率会高于进程间通信。一般进程间通信需要内核介入,而同一进程内的线程间共享该进程的内存和文件,不需要调用内核就可以实现通信。
一文详解操作系统进程管理

上图为多线程进程模型,其中线程控制块,也被称为TCB(Thread Control Block)。

对于进程来说,进程 = 线程+资源。

我们一开始提及过,操作系统底层存在调度程序,调度程序可调度任务,而单线程进程,每个进程可以对应一个任务。现在,对于多线程的进程,每一个线程最终对于调度程序来说,都是一个任务,如下图(Linux系统)。因此也有一种流行的说法“线程是CPU调度的基本单位

一文详解操作系统进程管理

3.2 线程状态

和进程状态模型类似,线程的状态也有新建,运行,就绪,阻塞,终止。与进程状态相似,终止线程时将进入终止状态。但是区别于进程的是当一个进程被终止了,其内部的所有线程都会被终止。由于线程之间的并行关系,同一进程内,一个线程被阻塞了,不会影响到其他线程。

4.进程调度

处理器调度,按照相对时间长短,可以分为长程调度,中程调度,短程调度。(常见调度还有I/O调度,但不属于处理器调度)。几种调度和进程的状态转换关系如下图

一文详解操作系统进程管理

4.1 几种调度方式

4.1.1 长程调度

长程调度又称为高级调度,作业调度。
它控制系统的并发度,决定着哪一个批处理作业或者用户程序可以进入系统中处理,一旦运行进入,批处理作业或者用户程序就会变成进程,进入就绪队列。

4.1.2 中程调度

中程调度又称交换调度,中级调度。
核心思想是将进程从内存或CPU竞争中移出,之后进程能重新被调入内存,通过这种方式可控制内存中进程数量。如图中,从就绪队列中挂起的进程进入就绪挂起队列,从阻塞队列中挂起的进程进入阻塞挂起队列。就绪挂起队列中的进程激活,则进入就绪队列。

4.1.3 短程调度

短程调度又称为低级调度,大部分时候讲的进程调度都是特指短程调度,短程调度将就绪队列中的进程调度到CPU中执行。其中按照一定策略将CPU分配给一个就绪状态的进程,分为抢占式调度和非抢占式调度。

非抢占式调度:
非抢占式调度,就是挑选一个进程,将CPU分配给它,该进程一直运行到终止或者因为等待事件进入阻塞状态(图中红字标注)。显然这种调度方式存在一个硬伤:正在运行的进程如果需要运行很长时间,那么排在它后面的进程,只能一直等,直到它结束或阻塞。

抢占式调度:
抢占式调度就是允许进程执行到一半时,将进程停下,CPU分配给其它进程。

4.2 进程调度算法

常见的进程调度算法有:

  • 先来先服服务
  • 时间片轮转
  • 最短作业优先
  • 最短剩余时间优先
  • 优先级调度
  • 多级反馈队列调度

由于篇幅有限,每一种调度算法本文只做精要的介绍,想更进一步了解,可以根据最后的参考资料。

4.2.1 先来先服务

先来先服务(First Come First Serverd, FCFS)。先进就绪队列,则先被调度,先来先服务是最简单的调度算法。

一文详解操作系统进程管理


先来先服务存在上面谈论过的问题:当前面任务耗费很长时间执行,那么后面的任务即使只需要执行很短的时间,也必须一直等待。属于非抢占式

4.2.2 时间片轮转调度

时间片轮转调度,即上面第一章所描述的方式。
每一个进程会被分配一个时间片,表示允许该进程在这个时间段运行,如果时间结束了,进程还没运行完毕,那么会通过抢占式调度,将CPU分配给其他进程,该进程回到就绪队列。这是一种最简单最公平的调度算法,但是有可能会存在问题。由于进程的切换,需要耗费时间,如果时间片太短,频繁进行切换,会影响效率。如果进程时间片太长,有可能导致排后面的进程等待太长时间。因此时间片的长度,需要有大致合理的数值。(《现代操作系统》的观点是建议时间片长度在20ms~50ms)。

4.2.3 最短作业优先

最短作业优先(Shortest Job First, SJF),顾名思义即进程按照作业时间长短排队,作业时间段的排前面先执行,如 下图。

一文详解操作系统进程管理

4.2.4 最短剩余时间优先

最短剩余时间优先(Shortest Remaining Time Next),从就绪队列中选择剩余时间最短的进程进行调度。该算法可以理解最短作业优先和时间片轮转的结合。如果没有时间片,那么最短剩余时间其实就是最短作业时间,因为每个进程都是从头执行到尾。

4.2.5 优先级调度

假设就绪队列中有如下进程

进程执行时间优先级P151P223P332

按照优先级调度,执行顺序为p1->p3->p2。如果多个进程优先级相同,则按照先来先服务的方式依次执行。

优先级调度可以进一步细分为抢占式和非抢占式。

非抢占式:和上面提及的非抢占式类似,一旦该进程占有CPU就将一直执行到结束或者阻塞。

抢占式:进程执行期间,一旦有更高优先级的进程进入就绪队列,那么该进程就会被暂停,重回就绪队列,让更高优先级的进程执行。但是为了防止最高优先级进程一直执行,每个进程依然有自己的时间片,每次时间片结束后,会根据一定规则降低该进程优先级,避免某些最高优先级长作业进程一直占用CPU。

4.2.6 多级反馈队列调度

多级反馈队列调度基于时间片轮转和优先级调度,设置多个就绪队列,赋予每个就绪队列优先级,优先级越高的队列进程的时间片越短。如下图,第1级就绪队列优先级最高,进程的时间片长度最短,第2级就绪队列次之,以此类推。

一文详解操作系统进程管理

当有新的进程创建时,先进入第1级就绪队列,时间片结束之前就运行完毕,则终止,否则进入第2级队列等待下一次调度。在n级队列之前,进程按照先到先服务规则依次调度,到了第n级队列(最后一级)采用时间片轮转调度。仅当第1级队列为空时,才调度第2级队列的进程,如果第i级队列的进程正在运行,此时有一个更高优先级的进程进入,则会停下第i级的进程,让它回到第i级队列尾部,转而执行更高优先级的进程,即满足优先级调度算法的原则。

5.进程间通信

进程间通信目的一般有共享数据,数据传输,消息通知,进程控制等。以 Unix/Linux 为例,介绍几种重要的进程间通信方式:共享内存,管道,消息,共享内存,信号量,信号

5.1 共享内存

多个进程可以读写同一块内存区域,是效率最高的进程间通信方式。

一文详解操作系统进程管理


由于多个进程都可以读写内存,所以需要一定的同步机制来保证数据读写安全问题,关于这种机制,需要花费较大篇幅,这里读者可根据文章末尾提供的参考资料查看,笔者后续也会再另起一篇专门介绍。

5.2 管道

首先简单介绍一下什么是生产者/消费者问题。一个或多个生产者,生产一些数据,将其放置到共享缓冲区中,由消费者从缓冲区中取走数据。同一个缓冲区同一时间内只允许生产者或者消费者一方访问,不能同时访问。当缓冲区满了,生产者不再向其中添加数据,当缓冲区空了,消费者不再向其读取数据。

管道就是基于生产者/消费者模型来实现通信的,最基本的管道通信由一端的读进程,管道,还有另一端的写进程构成,通信的介质是共享文件,也称为管道文件。管道可以分为匿名管道和命名管道,此处主要介绍命名管道。管道有一个特点:数据一旦被读取了,就从管道中删除,以释放空间便于写入更多数据。如下图

一文详解操作系统进程管理

如果需要实现双端通信,则需要两个管道,如下图。

一文详解操作系统进程管理

这里有一个注意点:第二个图是半双工通信,即虽然通信可以双向,但是同一时间只能单向传输。管道可以理解为一种共享存储(是磁盘存储而不是内存存储)的优化方式,保证同一缓冲区的数据,只能一端写入,一端读取,无法多端同时进行写操作。

5.3 信号

信号一般用于一些异常情况下的进程间通信,是一种异步通信,它的数据结构一般就是一个数字,比如Unix就提供了如下信号(摘自《操作系统精髓与设计原理》第6版 6.7.5章节)

01SIGHUB阻塞:内核认为进程正在做无用工作时发送给该进程02SIGINT中断03SIGQUIT停止:由用户发送,引发进程停止并产生信息转存

进程需要为信号设置相应的监听处理,当收到特定信号时,执行相应的操作,类似很多编程语言里的通知机制。

5.4 消息

消息可以作为两个不相关进程传递数据的方式,至少由一对原语构成

send(destination,message)
receive(source,message)

什么是原语:由若干条指令构成的程序段,用以执行特定的操作。消息通信可以分为直接通信和间接通信。

直接通信:发送进程直接发消息发给接收进程,把消息挂在接收进程的消息队列中,接收进程从消息队列中获取消息,是一种一对一的通信关系。

间接通信:消息不直接发送给接收者,而是发送到一个共享数据结构,该结构是一种消息队列,也称为信箱。这种方式相对于直接通信更加灵活,可以一对一,一对多,多对一,多对多。

一文详解操作系统进程管理

通过消息格式中指定的id来确保进程的识别,如下是一种常见的消息数据格式(来自《操作系统精髓与设计原理》5.5.3)

一文详解操作系统进程管理

消息在消息队列中,按照先进先出的原则。如果有消息比较紧急,发送者可以指定消息的类型,接收者在查询消息队列时,可以根据消息类型读取,不一定完全按照先进先出顺序。

消息相对于管道,有如下区别:

  • 在传输中,管道基于字节流,消息基于格式文本。
  • 介质上管道是文件,消息是内存
  • 管道只能按照先进先出的顺序,消息不一定,它可以根据消息类型选择性接收处理,更加灵活。

5.5 信号量

信号量本质是一个计数器,当多进程共享内存时,用于保护共享内存,确保共享内存在同一时刻只有一个进程独享。

信号量需要初始化为某个值,当有进程对共享内存进行访问时,信号量减1,如果信号量值不为负数,则访问共享内存。当此时其新进程也要访问共享内存时,再次将信号量减一,如果信号量的值为负数,则新进程阻塞等待。

一文详解操作系统进程管理

6. 总结

进程是操作系统最重要的概念之一,有比较多的细节点可以介绍,每一点还可以横向纵向再展开。笔者翻阅了大部分主流操作系统的书中关于进程管理的章节,总结出了本篇入门介绍,其中用户进程,内核进程,调度算法评价指标,进程和内存管理等内容这里受限于篇幅没有讨论。同步,并发,锁这几部分相对复杂且重要的内容打算后面另起章节单独描述。感谢阅读,如有疏漏或错误,还请指正 。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

您正在使用您的 WordPress.com 账号评论。 登出 /  更改 )

Google photo

您正在使用您的 Google 账号评论。 登出 /  更改 )

Twitter picture

您正在使用您的 Twitter 账号评论。 登出 /  更改 )

Facebook photo

您正在使用您的 Facebook 账号评论。 登出 /  更改 )

Connecting to %s