进程

程序是如何运行的？

• 程序编译链接形成可执行文件存储在硬盘
• 程序运行前把程序放入内存
• 程序开始运行前，操作系统创建对应的进程，建立PCB
• 指令序列读入内存——程序段
• 内存中存放运行中产生的数据——数据段
• CPU从内存中取出指令开始运行

进程实体的组成

PCB是给操作系统用的，PCB是进程存在的唯一标识; 程序段、数据段是给进程自己用的。

进程的状态，及其状态的转化

创建态——系统完成创建进程的一系列工作

就绪态——万事俱备，只欠处理机，进程被调度——>运行态

运行态——万事俱备，也拥有处理机
1、进程用系统调用的方式申请某种系统资源，或请求等待某个事件发生——>阻塞态（主动行为）
2、进程运行结束，或运行中遇到不可修复的错误——>终止态
3、时间片到，或处理机被抢占——>就绪态

阻塞态——万事无，处理机无
申请的资源被分配，或等待的事情发生（不包括对处理机的期待）——>就绪态（被动行为）

终止态——进程结束，释放资源

进程控制

进程控制就是要实现进程状态转换，用原语实现“一气呵成”地转换状态，相当于原语具有原子性。

在操作系统内核中，有一组程序专门用于完成对进程的控制，这些原语至少需要包括创建新进程原语，阻塞进程原语，唤醒进程原语，终止进程原语。

• 进程创建原语：从PCB集合中申请一个空白的PCB，将调用者参数（如进程外部标识符，初始CPU状态，进程优先数，初始内存及申请资源清单）添入该PCB，设置记账数据。置新进程为“就绪”态。
• 终止进程原语：用于终止完成的进程，回收其所占资源。包括消去其资源描述块，消去进程的PCB。
• 阻塞原语：将进程从运行态变为阻塞态。进程被插入等待事件的队列，同时修改PCB中相应的表项，如进程状态和等待队列指针。
• 唤醒原语：将进程从阻塞态变为就绪态。进程从阻塞队列移出，插入就绪队列，等待调度，同时修改PCB中相应的表项，如进程状态。

进程通信

进程通信的方法

• 共享存储（大布袋）
• 管道通信（读进程最多只能有1个，数据一旦被读取，就从管道中被抛弃）
• 消息传递（写信）

线程

重点：操作系统只看得见内核级线程，因此只有内核级线程才是处理机分配的单位。

三种线程模型

每一种线程模型的实现我们都围绕四个话题展开：

线程的管理工作由谁来完成?
线程切换是否需要CPU变态?
操作系统是否能意识到用户级线程的存在?
这种线程的实现方式有什么优点和缺点?

多对一模型

多对一模型：多个用户级线程映射到一个内核级线程。且一个进程只被分配一个内核级线程。

多对一模型特点：

• 用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责(包括线程切换)
• 用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预。
• 在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在。“用户级线程”就是“从用户视角看能看到的线程”

优缺点：

• 优点:用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
• 缺点:当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。

一对一模型

大多数现代操作系统都实现了内核级线程，如 应用 Windows、Linux。

一对一模型: 一个用户级线程映射到一个内核态核级线程。每个用户进程有与用户级线程同数量的内核级线程。

一对一模型特点：

• 内核级线程的管理工作由操作系统内核完成；
• 线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成；
• 操作系统会为每个内核级线程建立相应的 TCB(Thread Control Block，线程控制块)， 通过TCB对线程进行管理。“内核级线- 程”就是“从操作系统内核视角看能看到的线程”；

优缺点：

• 优点:当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
• 缺点:一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

值得注意的是，一对一模型由于每创建一个用户线程就要创建一个相应的内核线程，由于创建内核线程的开销会影响应用程序的性能，所以这种模型的大多数实现限制了系统支持的线程数量。

参考：Java使用的就是一对一线程模型。

多对多模型

多对多模型：n个用户级线程映射到m个内核级线程(n >= m)。每个用户进程对应 m 个内核级线程。

多对多模型特点：

• 克服了多对一模型并发度不高的缺点(一个阻塞全体阻塞)，又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点；
• 内核级线程中可以运行任意一个有映射关系的用户级线程代码，只有两个内核级线程中正在运行的代码逻辑都阻塞时，这个进程才会阻塞；
• 虽然多对多模型允许开发人员创建任意多的用户线程，但是由于内核只能一次调度一个线程，所以并未增加并发性。
• 当一个用户线程执行阻塞系统调用时，内核可以调度另一个用户线程来执行。
• 区别于一对一模型，它的进程里的所有用户线程并不与内核线程一一绑定，而是可以动态绑定内核线程， 当某个内核线程因为其绑定的用户线程的阻塞操作被内核调度让出CPU时，其关联的进程中其余用户线程可以重新与其他内核线程绑定运行。

golang的goroutine和C#的task

Golang 的 Goroutine 和 C# 的 Task 都是用于实现并发和并行执行的轻量级线程，但它们在设计、使用和特性上有一些区别和共同点。

共同点

• 轻量级线程：Goroutine 和 Task 都比操作系统线程更轻量级，可以创建更多的并发实体。
• 异步编程模型：两者都提供了一种基于回调或 Future/Promise 的异步编程模型，使得并发代码可以像同步代码一样编写。
• 任务调度：两者都有自己的任务调度器，负责分配任务给实体执行。

区别

• 调度器：Goroutine 由 Go 运行时环境（runtime）调度，通常使用 M:N 调度器模型（M个操作系统线程对应N个Goroutine）。Task 由 .NET 的线程池（ThreadPool）调度，可以灵活地使用 1:1，M:N 或其他模型。
• 资源消耗：虽然两者都是轻量级线程，但 Goroutine 的启动和销毁开销更小，因为它是为这个目的而优化的。相比之下，Task 的开销相对较大，因为它是基于线程池的。
• 并发模型：Go 语言中的 Goroutine 是并发原语，在 Go 中编写并发程序几乎总是使用 Goroutine。而 C# 中的 Task 是基于同步原语（如 async/await）的，使用 Task 是异步编程的一种方式。

CPU的调度

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

高级调度（作业调度）
1、作业：一个具体的任务
用户向系统提交一个作业=用户让操作系统启动一个程序来处理一个具体任务
2、高级调度：因为内存空间有限，不能将用户提交的作业全部放入内存，当外存的作业后备队列中有好几个作业需要启动，先把哪个作业调入内存，就将相应的作业从外存的作业后备队列中选中调入内存，并创建进程（PCB），每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB。作业进入内存后变成进程。

中级调度（内存调度）
因为内存资源有限，当内存中就绪队列中的进程过多时，可以将某些进程的数据调出到外存，等内存空闲或者需要运行时再重新调入内存。进程调出到外存仍是进程。处于挂起状态，组成挂起队列。中级调度：决定将哪个处于挂起状态的进程重新调入内存。

低级调度（进程/处理机调度）
因为内存中会存在很多进程处于就绪队列中，而处理机只能允许分配给一个进程，当就绪队列中有多个进程，应该先给哪一个进程分配处理机资源, 内存->CPU, 发生频率高

CPU的上下文切换

如今的OS几乎都支持"同时"运行远大于CPU数量的任务，OS会将CPU轮流分配给它们使用。这就要求OS必须知道从哪里加载任务，以及加载后从哪里开始运行，而这些信息都保存在CPU的寄存器中，其中即将执行的下一条指令的地址被保存在程序计数器（PC）这一特殊寄存器上。我们将寄存器的这些信息称为CPU的上下文，也叫硬件上下文。

OS在切换运行任务时，将上一任务的上下文保存下来，并将即将运行的任务的上下文加载到CPU寄存器上的这一动作，被称为CPU上下文切换。

CPU上下文属于进程上下文的一部分，我们常说的进程上下文由如下两部分组成：

• 用户级上下文：包含进程的运行时堆栈、数据块、代码块等信息。
• 系统级上下文：包含进程标识信息、进程现场信息（CPU上下文）、进程控制信息等信息。

这涉及到两个问题：（1）上一任务的CPU上下文如何保存下来？（2）什么时候执行上下文切换？

问题1: 上一任务的CPU上下文如何保存下来？

CPU上下文会被保存在进程的内核空间（kernel space）上。OS在给每个进程分配虚拟内存空间时，会分配一个内核空间，这部分内存只能由内核代码访问。OS在切换CPU上下文前，会先将当前CPU的通用寄存器、PC等进程现场信息保存在进程的内核空间上，待下次切换时，再取出重新装载到CPU上，以恢复任务的运行。

问题2: 什么时候执行上下文切换？

OS要想进行任务上下文切换，必须占用CPU来执行切换逻辑。然而，用户程序运行的过程中，CPU已经被用户程序所占用，也即OS在此刻并未处于运行状态，自然也无法执行上下文切换。针对该问题，有两种解决策略，协作式策略与抢占式策略。

协作式策略依赖用户程序主动让出CPU，比如执行系统调用（System Call）或者出现除零等异常。但该策略并不靠谱，如果用户程序没有主动让出CPU，甚至是恶意死循环，那么该程序将会一直占用CPU，唯一的恢复手段就是重启系统了。

抢占式策略则依赖硬件的定时中断机制（Timer Interrupt），OS会在初始化时向硬件注册中断处理回调（Interrupt Handler）。当硬件产生中断时，硬件会将CPU的处理权交给来OS，OS就可以在中断回调上实现CPU上下文的切换。

几种调度算法

FIFO：先进先出
FIFO（First In First Out，先进先出）调度算法以原理简单，容易实现著称，它先调度首先到达的任务直至结束，然后再调度下一个任务，以此类推。

SJF：最短任务优先
从相同到达时间的多个任务中选取运行时长最短的一个任务进行调度，接着再调度第二短的任务，以此类推。

STCF：最短时间完成优先
SJF算法的基础上，加上抢占式调度算法，就演变成了STCF算法，调度原理是当运行时长较短的任务到达时，中断当前的任务，优先调度运行时长较短的任务。

RR：基于时间片的轮询调度
RR（Round Robin，轮训）算法给每个任务分配一个时间片，当任务的时间片用完之后，调度器会中断当前任务，切换到下一个任务，以此类推。

MLFQ：多级反馈队列
算法比较复杂, 这里略了

CFS：Linux的完全公平调度
我们一个平时打交道最多的调度算法，Linux系统下的CFS（Completely Fair Scheduler，完全公平调度）。与上一节介绍的MLFQ不同，CFS并非以优化周转时间和响应时间为目标，而是希望将CPU公平地均分给每个任务。大部分调度算法都是基于固定时间片来进行调度，而CFS另辟蹊径，采用基于计数的调度方法，该技术被称为virtual runtime。

CFS给每个任务都维护一个vruntime值，每当任务被调度之后，就累加它的vruntime。比如，当任务A运行了5ms的时间片之后，则更新为vruntime += 5ms。CFS在下次调度时，选择vruntime值最小的任务来调度。

进程同步与互斥

进程同步: 讨论具有合作关系的两个进程的顺序问题
互斥概念: 讨论共享某种资源（临界资源）的两个进程的访问方式问题

进程互斥的软件实现方法

软件实现方法: 单标志法, 双标志先检查, 双标志后检查, Peterson算法

进程互斥的硬件实现方法

硬件实现方法: 中断屏蔽法, TestAndSet（TS指令/TSL指令）, Swap指令（XCHG）指令

信号量机制

信号量机制是一种卓有成效的实现进程互斥、同步的方法。信号量是一个变量（可以是一个整数，也可以是一个记录型变量），用来表示系统中某种资源的数量, 通过wait（S）/P（S）和signal（S）/V（S）原语对信号量进行操作。

整型信号量: 用一个整数变量，标识系统中某种资源的数量, 只能有三种操作：初始化、P操作、V操作。
记录型信号量: 用一个记录型数据结构表示的信号量, 整型剩余资源数、指针指向等待队列, 如果信号量值小于0，说明此时有进程在等待这种资源，绝对值为当前等待队列中的进程数。

管程

管程将同步互斥复杂的细节隐藏在管程定义的“过程”（函数）中，对外提供简单的调用接口。

为什么引入管程

信号量机制存在的问题，编写程序困难，易出错。例如需要关注PV操作的顺序。管程是一种高级的同步机制。

管程的基本特征

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

死锁

死锁：多个进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象。（进程处于阻塞态）

死锁产生的必要条件

• 互斥条件：只有对必须互斥使用的资源争抢才会导致死锁
• 不剥夺条件：不能由其他进程强行夺走
• 请求和保持条件：自己占了资源，又申请新的资源
• 循环等待条件：存在一种进程资源的循环等待链

死锁的处理策略

• 预防死锁（破坏四条件）
• 避免死锁（银行家算法）
• 死锁的检测和解除

扩展阅读

操作系统之进程管理(上)
操作系统之进程管理，同步互斥死锁高并发问题
《操作系统》——进程管理（上）
《操作系统》——进程管理（中）
《操作系统》——进程管理（下）死锁

最后更新于  2024-01-17 09:29:39  并被添加「」标签，已有 1278 位童鞋阅读过。

本站使用「署名 4.0 国际」创作共享协议，可自由转载、引用，但需署名作者且注明文章出处