【操作系统】进程和线程

damion 收录于操作系统

发布于 2020-12-04

进程基本概念

1. 进程的定义

进程的定义方式有多种，常见的几种定义如下：

进程是程序的一次执行过程。
进程是一个程序及其数据在处理机上顺序执行时所发生的活动。
进程是具有独立功能的程序在数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位。

2. 进程的组成

进程由三部分组成：

进程控制块PCB。
程序段。
数据段。

系统根据PCB感知进程的存在，PCB是进程存在的唯一标志。PCB的组成部分通常为：

进程标识符PID。每个进程都有唯一的标识符。
进程当前状态。作为进程调度程序分配CPU的依据。
进程队列指针。指向PCB队列中，下一个PCB的地址。
程序和数据地址。进程程序段和数据段的地址。
进程优先级。
CPU现场保护区。保存CPU的现场信息，如指令寄存器、状态寄存器、通用寄存器等。
通信信息。进程执行过程中，与别的进程发生的信息交换情况。
家族联系。进程可以创建子进程，从而形成一个进程家族树。
占有资源清单。记录了所需资源和已分配资源。

3. 进程的特点

动态性：

进程是程序在处理器上的一次执行过程，因而是动态的。
并发性：

多个进程可以同时存在于内存，在一段时间内同时运行。
独立性：

进程是一个能独立运行的基本单位。也是资源分配和调度的独立单位。
异步性：

进程以独立的、不可预知的速度向前推进。
结构性：

每个进程都是由程序段、数据段和一个进程控制块组成。

4. 进程和程序的区别

进程是动态的，程序是静态的。程序是有序代码的集合，进程是程序的执行。
进程是暂时的，程序是永久的。进程是一个状态变化的过程，程序可长久保存。
进程和程序的组成不同。进程包括程序、数据和进程控制块（即进程状态信息）。
通过多次执行，一个程序可以产生多个进程；通过调用关系，一个进程可以执行多个程序。
进程可以创建其他进程，程序不能形成新的程序。

5. 什么是进程实体

程序段、数据段和进程控制块PCB，三部分组成了进程实体，也叫进程映像。

进程实体是静态的。进程是动态的，进程是进程实体的运行过程。

6. 常见寄存器

程序状态寄存器PSW。
程序计数器PC。存放下一条指令的地址。
指令寄存器IR。存放当前正在执行的指令。
通用寄存器。可存放计算的中间结果。

进程状态

进程具备5种基本状态：

运行态
就绪态
阻塞态
创建态
终止态

1. 运行态

占有CPU，并在CPU上运行。

单核环境中，同时只有一个进程处于运行态。

双核环境中，同时可以有两个进程处于运行态。

2. 就绪态

已经具备运行条件，但由于没有CPU，暂时不能运行。

3. 阻塞态

用系统调用请求系统资源时，或者等待某一事件发生时，暂时不能运行。

4. 创建态

又称新建态。

进程正在被创建。

操作系统会为进程分配资源、初始化PCB。

5. 终止态

又称结束态。

进程正在从系统中撤销。

操作系统会回收进程拥有的资源，并且撤销PCB。

6. 进程状态转换

进程初始处于创建态。

就绪态 -> 运行态：进程被调度。
运行态 -> 就绪态：时间片到，或CPU被其它高优先级进程抢占。
运行态 -> 阻塞态：通过“系统调用”等待系统资源分配、或等待某事件发生（主动）。
阻塞态 -> 就绪态：资源分配到位，等待的事件发生（被动）。
创建态 -> 就绪态：系统完成创建。
运行态 -> 终止态：运行结束，或发生不可修复错误。

进程控制

1. 什么是进程控制

进程控制，是指对系统中的所有进程实施有效的管理。包含进程创建、进程撤销、以及进程状态转换等功能。

进程控制依靠原语来实现。

2. 原语

原语是一种特殊的程序。它的执行具有原子性，即执行期间不允许被中断。

原子性的实现，需要依靠“关中断指令”和“开中断指令”。

3. 进程创建原语

申请空白PCB
为进程分配所需资源
初始化PCB
将PCB插入就绪队列

4. 进程撤销原语

找到终止进程的PCB。
若进程正在运行，则立即剥夺CPU，将CPU分配给其他进程。
终止其所有子进程。
将该进程资源归还给父进程或操作系统。
删除PCB。

5. 进程阻塞原语

找到进程对应PCB。
保护进程运行现场，将PCB状态信息设置为阻塞态，暂时停止进程运行。
将PCB插入相应事件的等待列表。

6. 进程唤醒原语

从事件等待队列中找到PCB。
将PCB从等待队列移除，设置进程为就绪态。
将PCB插入就绪队列，等待被调度。

7. 进程切换原语

进程切换是指，从运行态到就绪态，或者从就绪态到运行态。

将运行环境存入PCB。
PCB移入相应队列。
选择另一个进程执行，并更新其PCB。
根据PCB恢复进程所需的运行环境。

进程通信

各进程拥有的内存地址空间相互独立。

为了安全，一个进程不能直接访问另一个进程的地址空间，从而诞生了各种进程通信的方法。

常见的进程通信方法有：

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

1. 管道

包括管道和命名管道。

2. 共享内存

Unix操作系统（包括linux）中有Posix内存共享库：shmem。

实现原理是以虚拟文件系统的形式，从内存中划分出一块区域，供两个进程共同使用。

速度快，但是程序实现复杂。

3. 消息队列

有本地消息队列，如mqueue。或者基于网络请求实现的消息队列，如kafka，rabbitmq等。

4. 网络请求

是套接字方法的一种实现，基于TCP/IP协议或者建立在这之上的通信协议。

5. 远程调用

是套接字方法的一种实现，RPC的过程为：

客户端调用函数或者方法。
客户端stub将函数调用封装为请求。
客户端socket发送请求，服务端socket接受请求。
执行服务端方法。
返回结果给服务端stub。
服务端stub将结果封装为返回数据。
服务端socket发送返回数据，客户端socket接受返回数据。
客户端socket将数据传递给客户端stub。
客户端stub把返回数据转义成函数返回值。

线程

线程是一个基本的CPU执行单位，也是程序执行流的最小单位。

进程是除CPU之外的系统资源的分配单位。

1. 线程特点

线程具有如下特点：

在多核CPU中，线程可以占据不同的CPU。
每个线程都有一个线程ID和一个线程控制块TCB。
线程也有就绪、阻塞和运行状态。
线程几乎不拥有系统资源。
同一进程的不同线程共享进程资源。
同一进程的线程切换，不会引起进程切换。
不同进程的线程切换，会引起进程切换。
同一进程内的线程切换，系统开销很小。
进程切换的系统开销较大。

2. 用户级线程

用户级线程介绍：

由应用程序通过线程库实现。
所有的线程管理工作都由应用程序负责（包括线程切换）。
用户线程之间的切换在用户态下完成，无需操作系统的干预。
用户线程对用户不透明，对操作系统透明。
用户线程就是用户视角能看到的线程。

优点：

线程管理的系统开销小，效率高。

缺点：

当一个用户级线程被阻塞后，整个进程都会被阻塞，并且多个用户级线程不可在多核处理机上并行运行，并发度不高。

3. 内核级线程

内核级线程介绍：

管理工作由操作系统内核完成，如线程调度、切换等。
内核级线程的切换，必须在内核态下才能完成。
内核级线程就是从操作系统内核视角能看到的线程。
内核级线程才是处理器分配的单位。

优点：

当一个线程被阻塞后，别的线程还可以继续执行，并且多线程可以在多核处理机上并行执行。

缺点：

线程切换由操作系统完成，因此线程管理成本高，开销大。

多线程模型

在用户级线程和内核级线程并存的系统中，几个用户线程映射到几个内核级线程的问题，称为“多线程模型”问题。

1. 多对一模型

多个用户级线程映射到一个内核级线程。

优点：

用户级线程的切换在用户空间即可完成，不需要切换到和心态，线程管理开销小，效率高。

缺陷：

当一个用户线程被阻塞，整个进程都会被阻塞，并发度不高。
多个线程不可在多核处理机上并行运行。

2. 一对一模型

一个用户级线程映射到一个内核级线程。

优点：

当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。
多线程可在多核处理机上并行执行。

缺点：

一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需切换到和心态，线程管理成本高，开销大。

3. 多对多模型

n个用户级线程映射到m个内核级线程(n >= m)。

调度

1. 三层调度

高级调度

也称作业调度。按照某种规则，从后备队列中，选择合适的作业，将其调入内存，并为其创建进程。

进程状态变化：无->创建态->就绪态。
中级调度

也称内存调度。按照某种规则，从挂起队列中，选择合适进程，将其数据调回内存。

为了提高资源利用率，暂时不执行的进程会被调到外存，从而成为“挂起态”。有“就绪挂起”和“阻塞挂起”。

进程状态变化：阻塞挂起->阻塞态，或者，就绪挂起->就绪态。
低级调度

也称进程调度。按照某种规则，从就绪队列中，选择合适进程，为其分配处理机。

进程状态变化：就绪态->运行态。

2. 进程调度的时机

主动放弃处理机：

进程正常终止。
进程发生异常而终止。
进程主动请求阻塞。

被动放弃处理机：

分给进程的时间片用完。
有更紧急的事情，如IO中断。
有更高优先级的进程进入就绪队列。

不能调度的时机：

处理中断时。
进程在操作系统内核程序临界区中。
在原子操作过程中。

临界资源：

一个时间段内，只允许一个进程使用的资源。各进程需要互斥的访问临界资源。

临界区：

用来访问临界资源的那段代码。

3. 进程调度的方式

抢占式调度

只允许进程主动放弃CPU。

实现简单，但是无法及时处理紧急任务。
非抢占式调度

可以优先处理更紧急的进程。

也可以让各进程按时间片轮转。

适合于分时操作系统、实时操作系统。

4. 进程切换过程

狭义的进程调度，指的是从就绪队列中选中一个要运行的进程。

进程切换，指一个进程让出处理器，由另一个进程占用处理器的过程。

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

进程切换过程如下：

保存原来运行进程的数据
恢复新进程的各种数据

缺陷：

进程切换有代价。
调度、切换过于频繁，会使得整个系统效率降低。

调度算法

先来先服务
短作业优先
最短剩余时间算法
高响应比优先
时间片轮转调度算法
优先级调度算法
多级反馈队列调度算法

1. 先来先服务算法

思想：按照到达的先后顺序进行服务
是否可抢占：非抢占式
优点：公平，实现简单
缺点：排在长作业/进程后面的短作业/进程要等待很久
是否会导致饥饿：不会

2. 短作业优先算法

用于进程时，称为短进程优先。

思想：用时最短的最先得到服务
是否可抢占：是非抢占式算法，但是也有抢占式版本（最短剩余时间优先算法）
优点：更短的平均等待时间和平均周转时间
缺点：对短作业有利，对长作业不利，可能产生饥饿现象；运行时间是用户提供，并不一定能做到真正的短作业优先
是否会导致饥饿：会，长作业可能会长时间得不到服务。

3. 最短剩余时间优先算法

就绪队列改变时、或者一个进程完成时，进行调度。

如果有新进程剩余时间比当前运行进程剩余时间短，则由新进程抢占处理机，当前进程回到就绪队列。

最短剩余时间优先算法，有最少的平均等待时间，和平均周转时间。

有的书中会说，短作业优先有着最少的平均等待时间，和平均周转时间，其实是不严谨的。

4. 高响应比优先

响应比计算公式：

1

响应比 = （等待时间 + 要求服务时间）/（要求服务时间）

思想：每次调度时，计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务。
是否可抢占：非抢占式
优点：综合考虑了等待时间和运行时间；对于长作业来说，等待时间越长响应比也会越大，从而避免了饥饿问题
是否会导致饥饿：不会

5. 时间片轮转算法

思想：按照进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如100ms）。如果一个时间片内未执行完，则剥夺处理机，重新放入就绪队列末尾。
是否可抢占：抢占式，由时钟中断来通知
优点：公平，响应快，适合分时操作系统
缺点：进程切换会有一定开销，不区分任务紧急程度
是否会导致饥饿：不会

注意：时间片不能太大，也不能太小

6. 优先级调度算法

思想：调度时选择优先级最高的作业/进程。
是否可抢占：抢占式和非抢占式都有。非抢占式在进程主动放弃处理器时进行调度；抢占式还在就绪队列发生变化时，发生调度。
优点：用优先级区分紧急程度，可灵活调整对各进程的偏好程度；适用于实时操作系统
缺点：低优先级进程可能一直得不到执行
是否会导致饥饿：会

通常，系统进程优先级高于用户进程，前台进程优先级高于后台进程，操作系统更偏好IO繁忙型进程。

7. 多级反馈队列调度算法

思想：
- 设置多级就绪队列，优先级从高到低，时间片从小到大；
- 新进程先进入第一级队列，按照先到先服务原则被分配时间片；
- 如果时间片用完还未结束，则进入下一级队列，如果位于最后一级，则重新进入该队列尾部；
- 第K级队列为空时，才会为K+1级队列分配时间片。
- 被抢占处理机的进程，重新放回该队列队尾。
是否可抢占：抢占式算法。当K级队列进程运行时，如果前几级队列加入了新进程，新进程会抢占处理机，原来的进程放回原队列的末尾。
是否会导致饥饿：会

同步和互斥

1. 什么是同步

异步性，并发执行的进程，以各自独立的、不可预知的速度向前推进。

同步，也称直接制约关系，是协调各进程工作次序而产生的制约关系。

2. 什么是互斥

互斥，也称间接制约关系，指一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。

临界资源，是一个时间段内只允许一个进程访问的资源，对临界资源的访问必须互斥的进行。

对临界资源的互斥访问，可在逻辑上分为如下四个部分：

进入区：检查是否可以进入临界区，如果可以进入，则设置正在访问临界资源的标志（上锁），以阻止其他进程同时进入临界区。
临界区：用来访问临界资源的代码。
退出区：解除正在访问临界资源的标志（解锁）。
剩余区：做其他处理。

3. 进程互斥原则

空闲让进：临界区空闲时，允许进程进入临界区。
忙则等待：已有进程进入临界区时，其他试图进入临界区的进程必须等待。
有限等待：对请求访问的进程，保证能在有限时间内进入临界区。
让权等待：当进程不能进入临界区，应立即释放处理机。

4. 信号量

信号量机制是实现进程互斥、同步的有效方法。

信号量是一个变量（可以是整数，也可以是记录型变量），用来表示系统中某资源的数量。用户进程可以使用操作系统提供的一对原语，来对信号量进行操作。

这对原语为wait原语和signal原语，wait原语和signal原语常简称为P、V操作。

wait原语用于占用资源，signal用于释放资源，资源不够时，wait原语会进行等待。

资源不够时，整型信号量存在“忙等”问题，不满足“让权等待”。

资源不够时，记录型信号量会让进程变为阻塞态，资源足够时，会被唤醒变为就绪态。

死锁

死锁、饥饿、死循环

死锁：

并发环境下，各进程互相等待对方手里的资源，导致进程都阻塞，无法向前推进的现象。

如果有死锁现象，至少是两个或以上进程发生死锁。

死锁一定处于阻塞态。
饥饿：

进程长期得不到想要的资源，从而无法向前推进的现象。

可能只有一个进程发生饥饿。

既可以是阻塞态，也可以是就绪态。
死循环

某进程执行过程中一直跳不出某个循环的现象。

可以处于运行态。

死锁产生条件

必须同时满足下列四个条件：

互斥条件：只有对互斥资源发生争抢才会导致死锁。
不可剥夺：资源不能被夺走，只能主动释放。
请求和保持：进程持有至少一个资源，但是又提出新的资源请求，该资源又被其他进程持有，于是请求进程被阻塞，持有资源又不会释放。
循环等待：存在进程资源的循环等待链，每一个进程获得的资源同时被下一个进程请求。

死锁处理

预防死锁：破坏死锁产生条件。
避免死锁：防止系统进入不安全状态（银行家算法）。
死锁检测和解除：操作系统检测死锁的发生，然后解除死锁。

预防死锁

将互斥资源改为允许共享使用。通常难以实现。
释放持有的资源，以后再重新申请；或者强行剥夺其他进程资源。实现复杂。
运行前一次性申请完所需的资源，运行后这些资源就归它所有。资源利用率低。
给资源编号，进程必须按照编号递增的顺序请求资源。资源利用率低且编程麻烦。

避免死锁

安全序列：系统如果按照这种序列分配资源，则每个进程都能顺利完成。
安全状态：只要能找到一个安全序列，系统就是安全状态。
银行家算法：进程提出资源申请时，先预判这次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让进程阻塞等待。

死锁检测和解除

死锁检测：

用某种数据结构保存资源的请求和分配信息
用某种算法，根据资源信息判断是否进入了死锁状态

解除死锁：

资源剥夺法：将进程挂起到外存，并抢占它的资源。
撤销进程法：撤销死锁进程，并抢占它的资源。
进程回退法：将死锁进程回退到足以避免死锁的地步。

目录