进程

程序是一个指令序列

image-20220323152904999

早期计算机只支持单道程序,一道时间段仅有一个程序执行
内存里也只有一个固定的程序段和数据段

image-20220323153216819

多道程序技术引入后,内存里就有多个程序段数据段了

内存中同时放入多道程序,各个程序的代码、运算数据存放的位置不同。操作系统要怎么才能找到各程序的存放位置呢?
因此系统为每个运行的程序配置一个数据结构,称为进程控制块(PCB) ,用来描述进程的各种信息(如程序代码存放位置)

程序段、数据段、PCB三部分组成了进程实体(进程映像)。一般情况下,我们把进程实体就简称为进程,例如,所谓创建进程,实质上是创建进程实体中的PCB;而撤销进程,实质上是撤销进程实体中的PCB。

注意: PCB是进程存在的唯一标志!

引入进程实体的概念后,可把进程定义为:
进程是进程实体的运行过程,是系统进行资源分配和调度的一个独立单位。

PCB组成:

image-20220323153614377

如何管理PCB?

  • 链接方式:按照进程状态(执行,阻塞,就绪)将PCB分为多个队列,操作系统持有指向各个队列的指针

image-20220323153908078

  • 索引方式:根据进程状态的不同,建立几张索引表,操作系统持有指向各个索引表的指针

image-20220323154004761

进程状态

运行态(Running) 占有CPU,并在CPU上运行
就绪态(Ready) **已经具备运行条件,但由于没有空闲CPU,**而暂时不能运行
阻塞态(Waiting/Blocked, 又称:等待态) 因等待某一事件而暂时不能运行

注意:单核处理机环境下,每时刻最多只有一个进程处于运行(双核环境下可以同时有两个进程处于运行态)

创建态(New, 又称:新建态) 进程正在被创建,操作系统为进程分配资源、初始化PCB
终止态(Terminated, 又称:结束态) 进程正在从系统中撤销,操作系统会回收进程拥有的资源、撤销PCB

image-20220323154657521

进程控制

进程控制就是要实现进程状态转换

image-20220323155040115

进程状态的改变操作应该是不被打断的,应该要用原语实现进程控制。PCB放到一个队列中并且修改PCB的状态

学习技巧:进程控制会导致进程状态的转换。无论哪个原语,要做的无非三类事情:
1.更新PCB中的信息(如修改进程状态标志、将运行环境保存到PCB、从PCB恢复运行环境)
a.所有的进程控制原语一定都会修改进程状态标志
b.剥夺当前运行进程的CPU使用权必然需要保存其运行环境
c.某进程开始运行前必然要恢复期运行环境
2.将PCB插入合适的队列

3.分配/回收资源

进程通信

顾名思义,进程通信就是指进程之间的信息交换。
进程是分配系统资源的单位(包括内存地址空间),因此各进程拥有的内存地址空间相互独立

为了保证安全,一个进程不能直接访问另一个进程的地址空间。
但是进程之间的信息交换又是必须实现的。为了保证进程间的安全通信,操作系统提供了一些方法。

进程间的通信方式

  • 信号
  • 管道
  • 信号量
  • 共享内存
  • 消息队列
  • 套接字

对比:

方式 传输的信息量 使用场景 关键词
信号 少量 任何 硬件来源、软件来源 / 信号队列
管道 大量 亲缘进程间 单向流动 / 内核缓冲区 / 循环队列 / 没有格式的字节流 / 操作系统负责同步
命名管道 大量 任何 磁盘文件 / 访问权限 / 无数据块 / 内核缓冲区 / 操作系统负责同步
信号量 N 任何 互斥同步 / 原子性 / P 减 V 增
共享内存 大量 多个进程 内存映射 / 简单快速 / 操作系统不保证同步
消息队列 比信号多,但有限制 任何 有格式 / 按消息类型过滤 / 操作系统负责同步
套接字 大量 不同主机的进程 读缓存区 / 写缓冲区 / 操作系统负责同步

信号 Signal

信号是 Linux 系统响应某些条件而产生的一个事件,由操作系统事先定义,接收到该信号的进程可以采取自定义的行为。这是一种“订阅-发布”的模式。

信号来源分为硬件来源和软件来源。

  1. 硬件来源。如按下 CTRL+C、除 0、非法内存访问等等
  2. 软件来源。如 Kill 命令、Alarm Clock 超时、当 Reader 中止之后又向管道写数据,等等

发送信号的机制:

  1. /bin/kill 程序发送信号
  2. 从键盘发送信号,比如按下 Ctrl+C 发送 SIGINT 信号、按下 Ctrl+Z 发送 SIGTSTP 信号
  3. kill 函数发送信号
  4. alarm 函数向自己发送 SIGLALRM 信号

一般的信号是都是由一个错误产生的。以除 0 为例。在 x86 机器上 DIV 或 IDIV 指令除数为 0 时,会引发 0 号中断,编号 #DE(Divide Error),即所谓除零异常。这是一个硬件级中断,会导致陷入内核,执行操作系统预定义在 IDT 中的中断处理程序。而操作系统处理这个异常的方法,就是**向进程发送一个信号 SIGFPE**。如果进程设置了相应的 signal handler,就执行进程的处理方法。否则,执行操作系统的默认操作,一般这种信号的默认操作是杀死进程。

同理,溢出、非法内存访问(越界)、非法指令等也都属于硬件中断,由操作系统处理。操作系统会将这些硬件异常包装成“信号”发送给进程。如果进程不处理这几个异常信号,那么默认的行为就是挂掉。

但是,信号也可以作为进程间通信的一种方式,明确地由一个进程发送给另一个进程。

进程如何发送信号?

  • 操作系统提供发送信号的系统调用(int kill(pid_t pid, int sig);int raise(int sig);,unsigned int alarm(unsigned int seconds)
  • 该系统调用会将信号放到目标进程的信号队列中
  • 如果目标进程未处于执行状态,则该信号就由内核保存起来,直到该进程恢复执行并传递给它为止。如果一个信号被进程设置为阻塞,则该信号的传递被延迟,直到其阻塞被取消时才被传递给进程

进程如何接收信号?

  • 每个进程有一个信号队列,放其他进程发给它、等待它处理的信号
  • 进程在执行过程中的特定时刻,检查并处理自己的信号队列。如从系统空间返回到用户空间之前
  • 发送信号时,必须指明发送目标进程的号码。一般用在具有亲缘关系的进程之间

用户进程对信号的处理过程有三种:

  1. 处理信号。定义信号处理函数,当信号发生时,执行相应的处理函数
  2. 忽略信号。当不希望接收到的信号对进程的执行产生影响,而让进程继续执行时,可以忽略该信号,即不对信号进程作任何处理
  3. 不处理也不忽略。执行默认操作,linux 对每种信号都规定了默认操作

有的信号,用户进程是无法处理也无法忽略的,比如SIGSTOPSIGKILL 等。

关于信号的更详细的内容,可以查看这篇文章

管道 Pipe

每个进程各自有不同的用户地址空间,任何一个进程的全局变量在另一个进程中都看不到,所以进程之间要交换数据必须通过内核,在内核中开辟一块缓冲区,进程A把数据从用户空间拷到内核缓冲区,进程B再从内核缓冲区把数据读走,内核提供的这种机制称为进程间通信。

不同进程间的通信本质:进程之间可以看到一份公共资源;而提供这份资源的形式或者提供者不同,造成了通信方式不同,而 pipe就是提供这份公共资源的形式的一种。

1
2
#include <unistd.h>
int pipe (int fd[2]);//返回:成功返回0,出错返回-1

fd参数返回两个文件描述符,fd[0]指向管道的读端,fd[1]指向管道的写端。fd[1]的输出是fd[0]的输入。

管道如何实现进程间的通信

(1)父进程创建管道,得到两个⽂件描述符指向管道的两端

(2)父进程fork出子进程,⼦进程也有两个⽂件描述符指向同⼀管道。

(3)父进程关闭fd[0],子进程关闭fd[1],即⽗进程关闭管道读端,⼦进程关闭管道写端(因为管道只支持单向通信)。⽗进程可以往管道⾥写,⼦进程可以从管道⾥读,管道是⽤环形队列实现的,数据从写端流⼊从读端流出,这样就实现了进程间通信。

image-20220323161354903

管道读取数据的四种的情况

(1)读端不读,写端一直写
这里写图片描述
(2)写端不写,但是读端一直读
这里写图片描述

(3)读端一直读,且fd[0]保持打开,而写端写了一部分数据不写了,并且关闭fd[1]。
这里写图片描述

如果一个管道读端一直在读数据,而管道写端的引⽤计数⼤于0决定管道是否会堵塞,引用计数大于0,只读不写会导致管道堵塞。

(4)读端读了一部分数据,不读了且关闭fd[0],写端一直在写且f[1]还保持打开状态。

这里写图片描述

管道的特点

  • 1.管道只允许具有血缘关系的进程间通信,如父子进程间的通信。

  • 2.管道只允许单向通信。

  • 3.管道内部保证同步机制,从而保证访问数据的一致性。

  • 4.面向字节流

  • 5.管道随进程,进程在管道在,进程消失管道对应的端口也关闭,两个进程都消失管道也消失。

命名管道 FIFO

Linux 管道包含匿名管道和命名管道。上面说的是匿名管道,只能用在亲缘进程中,管道文件信息保存在内存里。

命名管道(FIFO)可用于没有亲缘的进程间。Pipe 和 FIFO 除了建立、打开、删除的方式不同外,二者几乎一模一样。

通过 mknode() 系统调用或者 mkfifo() 函数建立命名管道。一旦建立,任何有访问权的进程都可以通过文件名将其打开和进行读写,而不局限于父子进程。

建立命名管道时,会在磁盘中创建一个索引节点,命名管道的名字就相当于索引节点的文件名。索引节点设置了进程的访问权限,但是没有数据块。命名管道实质上也是通过内核缓冲区来实现数据传输。有访问权限的进程,可以通过磁盘的索引节点来读写这块缓冲区。

当不再被任何进程使用时,命名管道在内存中释放,但磁盘节点仍然存在。

信号量 Semaphore

信号量是一种特殊的变量,对它的操作都是原子的,有两种操作:V(signal())和 P(wait())。V 操作会增加信号量 S 的数值,P 操作会减少它。

  • V(S):如果有其他进程因等待 S 而被挂起,就让它恢复运行,否则 S 加 1
  • P(S):如果 S 为 0,则挂起进程,否则 S 减 1

P、V 来自于荷兰语:Probeer (try)、Verhoog (increment)。

如果信号量是一个任意的整数,通常被称为计数信号量(Counting semaphore),或一般信号量(general semaphore);如果信号量只有二进制的 0 或 1,称为二进制信号量(binary semaphore)。在 Linux 系统中,二进制信号量又称互斥锁(Mutex)。信号量可以用于实现进程或线程的互斥和同步。

信号量在底层的实现是通过硬件提供的原子指令,如 Test And SetCompare And Swap 等。比如 golang 实现互斥量就是使用了 Compare And Swap 指令(github)。

共享内存 Shared Memory

共享内存顾名思义,允许两个或多个进程共享同一段物理内存。不同进程可以将同一段共享内存映射到自己的地址空间,然后像访问正常内存一样访问它。不同进程可以通过向共享内存端读写数据来交换信息。

一个进程可以通过操作系统的系统调用,创建一块共享内存区;其他进程通过系统调用把这段内存映射到自己的用户地址空间中;之后各个进程向读写正常内存一样,读写共享内存。共享内存区只会驻留在创建它的进程地址空间内。

共享内存的优点是简单且高效,访问共享内存区域和访问进程独有的内存区域一样,原因是不需要系统调用,不涉及用户态到内核态的转换,也不需要对数据不必要的复制。

比如管道和消息队列,需要在内核和用户空间进行四次的数据拷贝(读输入文件、写到管道;读管道、写到输出文件),而共享内存则只拷贝两次:一次从输入文件到共享内存区,另一次从共享内存到输出文件(图示)。此外,消息传递的实现经常采用系统调用,也就经常需要用户态和内核态互相转换;而共享内存只在建立共享内存区域时需要系统调用;一旦建立共享内存,所有访问都可作为常规内存访问,无需借助内核。

共享内存的缺点是存在并发问题,有可能出现多个进程修改同一块内存,因此共享内存一般与信号量结合使用。

Linux 的 2.2.x 内核支持多种共享内存方式,如 mmap() 系统调用,Posix 共享内存,以及系统 V 共享内存。

mmap() 系统调用的主要作用是将普通文件映射到进程的地址空间,然后可以像访问普通内存一样对文件进行访问,不必再调用 read(),write() 等操作。mmap() 不是专门用来共享内存的,但是多个进程可以通过 mmap() 映射同一个普通文件,来实现共享内存。

系统 V 则是通过映射特殊文件系统 shm 中的文件实现进程间的共享内存。通过 shmget 可以创建或获得共享内存的标识符。取得共享内存标识符后,通过 shmat 将这个内存区映射到本进程的虚拟地址空间。

有关 mmap() 系统调用、系统 V 共享内存的详细介绍,以及两者的对比,可以进一步查看这两篇文章:

消息队列 Message Queue

消息队列是一个消息的链表,保存在内核中。消息队列中的每个消息都是一个数据块,具有特定的格式。操作系统中可以存在多个消息队列,每个消息队列有唯一的 key,称为消息队列标识符。

消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。和信号相比,消息队列能够传递更多的信息。与管道相比,消息队列提供了有格式的数据,但消息队列仍然有大小限制。

消息队列允许一个或多个进程向它写入与读取消息。消息的发送者和接收者不需要同时与消息队列交互。消息会保存在队列中,直到接收者取回它。也就是说,消息队列是异步的,但这也造成了一个缺点,就是接收者必须轮询消息队列,才能收到最近的消息。

操作系统提供创建消息队列、取消息、发消息等系统调用。

操作系统负责读写同步:若消息队列已满,则写消息进程排队等待;若取消息进程没有找到需要的消息,则在等待队列中寻找。

消息队列和管道相比,相同点在于二者都是通过发送-接收的方式进行通信,并且数据都有最大长度限制。不同点在于消息队列的数据是有格式的,并且取消息进程可以选择接收特定类型的消息,而不是像管道中那样默认全部接收。

套接字 Socket

  • 不同的计算机的进程之间通过 socket 通信,也可用于同一台计算机的不同进程
  • 需要通信的进程之间首先要各自创建一个 socket,内容包括主机地址与端口号,声明自己接收来自某端口地址的数据
  • 进程通过 socket 把消息发送到网络层中,网络层通过主机地址将其发到目的主机,目的主机通过端口号发给对应进程

操作系统提供创建 socket、发送、接收的系统调用,为每个 socket 设置发送缓冲区、接收缓冲区。

线程

image-20220102115022061

image-20220102115400652

image-20220102115707254

image-20220102224351270

调度

当有一堆任务要处理,但由于资源有限,这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序,这就是“调度”研究的问题。

多道程序系统中,进程的数量往往是多于处理机的个数的,这样不可能同时并行地处理各个进程。处理机调度,就是从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行,以实现进程的并发执行。

高级调度

由于内存空间有限,有时无法将用户提交的作业全部放入内存,因此就需要确定某种规则来决定将作业调入内存的顺序。

高级调度(作业调度)。按一定的原则从外存上处于后备队列的作业中挑选一个(或多个)作业,给他们分配内存等必要资源,并建立相应的进程(建立PCB),以使它(们)获得竞争处理机的权利。

高级调度是辅存(外存)与内存之间的调度。每个作业只调入一次,调出一次。作业调入时会建立相应的PCB,作业调出时才撤销PCB。高级调度主要是指调入的问题,因为只有调入的时机需要操作系统来确定,但调出的时机必然是作业运行结束才调出。

中级调度

引入了虚拟存储技术之后,可将暂时不能运行的进程调至外存等待。等它重新具备了运行条件且内存又稍有空闲时,再重新调入内存。
这么做的目的是为了提高内存利用率和系统吞吐量。
暂时调到外存等待的进程状态为挂起状态。值得注意的是,PCB并不会一起调到外存, 而是会常驻内存。PCB中会记录进程数据在外存中的存放位置,进程状态等信息,操作系统通过内存中的PCB来保持对各个进程的监控、管理。被挂起的进程PCB会被放到的挂起队列中。

低级调度

低级调度(进程调度),其主要任务是按照某种方法和策略从就绪队列中选取一个进程,将处理机分配给它。

进程调度是操作系统中最基本的一种调度,在一般的操作系统中都必须配置进程调度。
进程调度的频率很高,一般几十毫秒一次。

image-20220102120441152

进程切换

什么时候进程切换?

image-20220323172118940

不能进行进程调度和切换的情况:

  • 1.在处理中断的过程中。中断处理过程复杂,与硬件密切相关,很难做到在中断处理过程中进行进程切换。
  • 2.进程在操作系统内核程序临界区中。
  • 3.在**原子操作过程中(原语)**。原子操作不可中断,要一气呵成(如之前讲过的修改PCB中进程状态标志,并把PCB放到相应队列)

“狭义的进程调度”与“进程切换”的区别:
狭义的进程调度指的是从就绪队列中选中一个要运行的进程。(这 个进程可以是刚刚被暂停执行的进程,也可能是另一一个进程,后一种情况就需要进程切换)
进程切换是指一个进程让出处理机,由另一个进程占用处理机的过程

广义的进程调度包含了选择一个进程和进程切换两个步骤。

进程切换的过程主要完成了:
1.对原来运行进程各种数据的保存
2.对新的进程各种数据的恢复
(如:程序计数器、程序状态字、各种数据寄存器等处理机现场信息,这些信息一般保存在进程控制块)

注意:进程切换是有代价的,因此如果过于频繁的进行进程调度、切换,必然会使整个系统的效率降低,使系统大部分时间都花在了进程切换上,而真正用于执行进程的时间减少。

调度算法

批处理系统

批处理系统没有太多的用户操作,在该系统中,调度算法目标是保证吞吐量和周转时间(从提交到终止的时间)。

1.1 先来先服务 first-come first-serverd(FCFS)

非抢占式的调度算法,按照请求的顺序进行调度。

有利于长作业,但不利于短作业,因为短作业必须一直等待前面的长作业执行完毕才能执行,而长作业又需要执行很长时间,造成了短作业等待时间过长。

1.2 短作业优先 shortest job first(SJF)

非抢占式的调度算法,按估计运行时间最短的顺序进行调度。

长作业有可能会饿死,处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来,那么长作业永远得不到调度。

1.3 最短剩余时间优先 shortest remaining time next(SRTN)

最短作业优先的抢占式版本,按剩余运行时间的顺序进行调度。 当一个新的作业到达时,其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少,则挂起当前进程,运行新的进程。否则新的进程等待。

交互式系统

交互式系统有大量的用户交互操作,在该系统中调度算法的目标是快速地进行响应。

2.1 时间片轮转

将所有就绪进程按 FCFS 的原则排成一个队列,每次调度时,把 CPU 时间分配给队首进程,该进程可以执行一个时间片。当时间片用完时,由计时器发出时钟中断,调度程序便停止该进程的执行,并将它送往就绪队列的末尾,同时继续把 CPU 时间分配给队首的进程。

时间片轮转算法的效率和时间片的大小有很大关系:

  • 因为进程切换都要保存进程的信息并且载入新进程的信息,如果时间片太小,会导致进程切换得太频繁,在进程切换上就会花过多时间。
  • 而如果时间片过长,那么实时性就不能得到保证。

img

2.2 优先级调度

为每个进程分配一个优先级,按优先级进行调度。

为了防止低优先级的进程永远等不到调度,可以随着时间的推移增加等待进程的优先级。

2.3 多级反馈队列

一个进程需要执行 100 个时间片,如果采用时间片轮转调度算法,那么需要交换 100 次。

多级队列是为这种需要连续执行多个时间片的进程考虑,它设置了多个队列,每个队列时间片大小都不同,例如 1,2,4,8,..。进程在第一个队列没执行完,就会被移到下一个队列。这种方式下,之前的进程只需要交换 7 次。

每个队列优先权也不同,最上面的优先权最高。因此只有上一个队列没有进程在排队,才能调度当前队列上的进程。

可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

img

实时系统

实时系统要求一个请求在一个确定时间内得到响应。

分为硬实时和软实时,前者必须满足绝对的截止时间,后者可以容忍一定的超时。

进程同步与互斥

临界区

对临界资源进行访问的那段代码称为临界区。

为了互斥访问临界资源,每个进程在进入临界区之前,需要先进行检查。

1
2
3
// entry section
// critical section;
// exit section

同步与互斥

  • 同步:多个进程因为合作产生的直接制约关系,使得进程有一定的先后执行关系。
  • 互斥:多个进程在同一时刻只有一个进程能进入临界区。

信号量

信号量(Semaphore)是一个整型变量,可以对其执行 down 和 up 操作,也就是常见的 P 和 V 操作。

  • down : 如果信号量大于 0 ,执行 -1 操作;如果信号量等于 0,进程睡眠,等待信号量大于 0;
  • up :对信号量执行 +1 操作,唤醒睡眠的进程让其完成 down 操作。

down 和 up 操作需要被设计成原语,不可分割,通常的做法是在执行这些操作的时候屏蔽中断。

如果信号量的取值只能为 0 或者 1,那么就成为了 互斥量(Mutex) ,0 表示临界区已经加锁,1 表示临界区解锁。

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef int semaphore;
semaphore mutex = 1;
void P1() {
down(&mutex);
// 临界区
up(&mutex);
}

void P2() {
down(&mutex);
// 临界区
up(&mutex);
}

生产者-消费者

image-20220102164910506

  • 生产者每次要消耗(P)一个空闲缓冲区,并生产(V)一个产品。
  • 消费者每次要消耗(P)一个产品,并释放一个空闲缓冲区(V)。
  • 往缓冲区放入/取走产品需要互斥。

每个PV对应于一个信号量,因此需要三个信号量。而且生产者是看缓冲区满没满,消费者是看缓冲区空不空。生产者和消费者的信号量是不一样的!!!

1
2
3
semaphore mutex = 1;     //互斥信号量,实现对缓冲区的互斥访问.
semaphore empty = n; //同步信号量,表示空闲缓冲区的数量
semaphore full = 0; //同步信号量,表示产品的数量,也即非空缓冲区的数量

PV操作题目的解题思路:

  1. 关系分析。找出题目中描述的各个进程,分析它们之间的同步、互斥关系。
  2. 整理思路。根据各进程的操作流程确定P、V操作的大致顺序。
  3. 设置信号量。设置需要的信号量,并根据题目条件确定信号量初值。 (互斥信号量初值一-般为1,同步信号量的初始值要看对应资源的初始值是多少)

生产者消费者问题是一一个互斥、同步的综合问题。
对于初学者来说最难的是发现题目中隐含的两对同步关系。
有时候是消费者需要等待生产者生产,有时候是生产者要等待消费者消费,这是两个不同的“一前一后问题”,因此也需要设置两个同步信号量。.

image-20220102165557940

image-20220102165755092

多生产者-多消费者

多是指多类别

image-20220102171346301

image-20220102171632098

image-20220102172230628

image-20220102172247539

总结:在生产者-消费者问题中,如果缓冲区大小为1,那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。当然,这不是绝对的,要具体问题具体分析。

image-20220102172330699

吸烟者问题

image-20220102172523937

image-20220102172810308

image-20220102172834956

image-20220102173047966

读者-写者问题

image-20220102173926992

image-20220102173848260

image-20220102174326753

读者-写者问题为我们解决复杂的互斥问题提供了一个参考思路。其核心思想在于设置了一个计数器count用来记录当前正在访问共享文件的读进程数。我们可以用count的值来判断当前进入的进程是否是第一个/最后 一个读进程,从而做出不同的处理。另外,对count变量的检查和赋值不能一气呵成导致了一-些错误,如果需要实现“一气呵成”,自然应该想到用互斥信号量。最后,还要认真体会我们是如何解决“写进程饥饿”问题的。

哲学家吃饭问题

image-20220102174535334

image-20220102174633530

image-20220102174949003

如何防止死锁的发生呢?

  1. 可以对哲学家进程施加一些限制条件,比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的
  2. 要求奇数号哲学家先拿左边的筷子,然后再拿右边的筷子,而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭,那么只会有其中一个可以拿起第一只筷子, 另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况。

更准确的说法应该是:各哲学家拿筷子这件事必须互斥的执行。这就保证了即使一个哲学家在拿筷子拿到一半时被阻塞,也不会有别的哲学家会继续尝试拿筷子。这样的话,当前正在吃饭的哲学家放下筷子后,被阻塞的哲学家就可以获得等待的筷子了。

管程

信号量编写程序比较复杂困难,因此就引入了管程

管程是一种特殊的软件模块,有这些部分组成:

  • 1.局部于管程的共享数据结构说明;
  • 2.对该数据结构进行操作的一组过程(函数);
  • 3.对局部于管程的共享数据设置初始值的语句;
  • 4.管程有一个名字。

Tips:“过程”其实就是“函数”
管程的基本特征:

  • 1.局部于管程的数据只能被局部于管程的过程所访问;
  • 2.一个进程只有通过调用管程内的过程才能进入管程访问共享数据;
  • 3.每次仅允许一个进程在管程内执行某个内部过程。

由编译器负责实现各个进程互斥地进入管程的过程

  1. 需要在管程中定义共享数据(如生产者消费者问题的缓冲区)
  2. 需要在管程中定义用于访问这些共享数据的“入口”– -其实就是一-些函数(如生产者消费者问题中,可以定义一个函数用于将产品放入缓冲区,再定义一个函数用于从缓冲区取出产品)
  3. 只有通过这些特定的“入口”才能访问共享数据
  4. 管程中有很多“入口”,但是每次只能开放其中一个“入口”,并且只能让一个进程或线程进入(如生产者消费者问题中,各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区。注意:这种,互斥特性是由编译器负责实现的,程序,员不用关心)
  5. 可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待(此时,该进程应先释放管程的使用权,也就是让出“入口”) ;可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。

死锁

死锁概念

image-20220102194745837

image-20220102194939626

预防死锁

image-20220102195346012

image-20220102195510108

image-20220102195652118

image-20220102195749906

image-20220102200005954

避免死锁

image-20220102201344457

image-20220102201200283

死锁处理

image-20220102201430026

image-20220102202428864

资源结点:表示进程想申请几个资源(每条边代表一个)
进程结点:表示已经为进程分配了几个资源(每条边代表一个)

注意上图中蓝色边表示请求边,绿色边表示申请边。

image-20220102202352288

进程是一个拥有资源执行任务的单元体。进程拥有的资源包括:内存空间中的代码、数据等;I/O 资源;文件;处理机等。

线程是一个执行任务的单元体。线程只拥有处理机,线程之间共享进程的资源,如内存、I/O 等。

对比:

进程 线程
资源 进程是一个拥有资源执行任务的单元体。 线程是一个执行任务的单元体,不拥有资源,线程之间共享地址空间
切换开销 开销很大 开销很小
通信 IPC 共享内存
健壮性 健壮,多个进程之间不会互相干扰 不健壮,一个线程出错会终止整个进程

为什么需要线程

进程切换是一个开销很大的操作。进程切换的开销主要包括:

  • 处理机的上下文切换:保存和恢复相关寄存器的内容
  • 与进程相关的数据结构更改:存储管理有关的记录信息(如页表)、文件管理有关数据(如文件描述符)、进程控制块中的各种队列(如阻塞队列、就绪队列、通信队列)等

进程的处理机资源和其他资源是一起分配的,进程切换的时候会整体切换,开销很大。如果我们只切换必需的、与处理机相关的信息,就可以有效减少开销。这种情况下,处理机分配的单位和其他的资源分配的单位不能再是一个实体。

由此引入线程:把一个进程分为多个执行任务的单元体,只为其分配处理机,这些执行任务的单元体就是线程。

线程的上下文切换过程

线程有自己的寄存器和栈。当上下文切换的时候,正在运行的线程会将寄存器的状态保存到 TCB(Thread Control Block)里(进程是 PCB,Process Control Block),然后恢复另一个线程的上下文。

img

图 1:单线程与多线程的示意图

和进程的区别是,线程只需要切换处理机执行的上下文,不会改变地址空间。这意味着:

  1. 不需要重新加载页表,切换开销少,提高效率
  2. 多个线程共享地址空间,有利有弊

线程的优缺点

优点:

  • 提高效率:切换开销小
  • 通信方便,共享内存;进程必须通过进程间通信 IPC

缺点:

  • 一个线程出错,操作系统会结束整个进程,不够健壮;而多进程就没有这个问题
  • 同一进程中的多个线程共享内存,会有并发问题

同一进程中的线程共享与独占的资源

共享资源:

  • 内存空间
    • 代码
    • 公共数据(全局变量、静态变量)
  • 文件描述符
  • 信号处理器
  • 进程 ID / 进程组 ID

独占资源,以及为什么需要独占:

  • 线程 ID:在本进程中唯一,进程用来标识此线程
  • 一组寄存器的值
  • 栈:每个线程中的函数调用过程是独立的,因此需要有独立的栈
  • 错误返回码:系统调用或库函数发生错误时,会设置全局变量 errno,各个线程的错误返回码应该是独立的
  • 信号屏蔽码:每个线程所感兴趣的信号不同,所以线程的信号屏蔽码应该由线程自己管理;但每个线程都共享本进程的信号处理器

可以参考图 1。

线程的实现方式

线程也像进程一样有多个状态:运行、就绪、阻塞…

从 Linux 内核的角度来看,线程和进程并没有被区别对待。无论线程还是进程,都是用 task_struct 结构表示的,只不过线程的 mm(内存空间)和 files(打开的文件)结构体是共享的,见进程、线程和文件描述符 - labuladong

线程实现的方式有三种:

  • 在内核实现
  • 在用户空间实现
  • 混合方式实现

每种实现方式的优缺点:TODO