原文出处：10+小故事揭秘高频「操作系统面试题」

面试的过程中，为了考察面试者的基础功力，除了算法以外，操作系统将会占比很大的权重，本文给大家分享我在面试过程中出现的非常高频的面试题，我基本上会从两个角度来阐述，一个是"官话"，一个是“大白话”。希望对即将面试的你有所帮助。

为什么有了进程，还要有线程呢？

为了提高系统资源的利用率和系统的吞吐量，通常进程可让多个程序并发的执行，但是也会带来一些问题

官话

基于以上的缺点，操作系统引入了比进程粒度更小的线程，作为并发执行的基本单位，从而减少程序在并发执行时所付出的时间和空间开销，提高并发性能。

举个例子：

小Q当年开发了一个聊天软件，给女朋友说：咋们以后不用什么qq，微信了，我写个聊天工具，咱两正儿八经的两人世界可好。

说干就干，小Q很快就完成了开发，然后开始测试，打电话让女朋友让她发个信息，小Q就等着，等啊等啊，怎么还没有发信息过来，没显示啊，一脸懵逼，单步调试吧，发现程序卡在了wati for user input不动了。

厉害，程序不输入就没办法执行后面的任务。咋搞？要不设置个1s，用户1s不输入直接跳过进行后面的接收阶段和显示阶段，牛皮牛皮，果然好使，好使个锤锤，这样用户输入信息不就很可能丢失，咋搞？

能不能将输入和显示这两个动作给分开，一个负责输入，发送消息，一个负责读信息和显示。不夸夸你自己吗，直接开干呈现两个窗口。

回来回来，这就是我们的多进程。不过多进程也还是有些问题需要注意，开多个窗口没问题，无脑开窗口撩骚直接被榨干(内存耗尽)，而且想要几个窗口交换个数据也是贼麻烦，这是为啥呢？

多进程的程序，每个进程都有自己的独立内存空间，都穿了衣服，不能相互乱看，要想通信就要接触系统层面来通信，所以肯定就会造成较多的资源消耗和时间浪费。怎么整？

几个进程为了方便，干脆商量一波，能不能开辟一块内存空间，共乐其中，这就是线程非常重要的意义，不过共享了不代表我们就是"裸"的，个人保密还是要做到，也不要吵架，可不可以通过锁的方式保密呢，这就涉及到了线程的同步。这样我猜测你应该了解进程和线程了吧。

简单说下你对并发和并行的理解？

官话从概念出发：

在一个时间段中多个程序都启动运行在同一个处理机中

假设目前A，B两个进程，两个进程分别由不同的 CPU 管理执行，两个进程不抢占 CPU 资源且可以同时运行，这叫做并行。

例子：

并发是指多个任务在一段时间内发生。比如今日成都某家老火锅店做活动，全场5折(这还是比较狠)，但是只有200个位置，但是来的人太多了，来了250个人，此时多出的50个人只好等待着或者去另外家火锅店。

那么火锅店老板对这250人的安排不是同一时刻安排而是一段时间去处理，其实这就是并发。这个例子好像整的不算生动，我们再来一个：

到了周末就是我们"开黑"的时光，奈何到了周一不迟到怎么对得起自己，但是迟到了被逮住就要被"BB"。好嘛，我们作为学生娃儿只好认怂，常规操作，两脚一登，起床，刷牙，上厕所，拿包包冲。

就是这样类似复读机的习惯操作是怎么回事？莫非我们就能同时干这么多事？其实不是的，我们大脑下达指令，起床，刷牙这些操作早形成了肌肉记忆，所以我们在这小段时间完成了这么多事儿，还可以多几分钟出来看看美女不香？

并发

平时玩儿电脑的时候，边写代码边听音乐，计算机同时处理了这么多任务。如果是单核 CPU，在我们看来这些事儿是同时发生的，其实那是因为底层 CPU切换的速度太快以致于我们完全感受不到它的切换，仅此为错觉而已。

但是如果是多核 CPU，各个 CPU 负责不同的进程，各个进程不抢占 CPU，这样同时进行，这就是真正意义上的并行。

并行

说了这么多，那并行和并发到底啥区别？

两者区别在于是否"同时"发生。是在一段时间同时发生还是多个事情在同一个时间点同时发生。

同步、异步、阻塞、非阻塞的概念

首先大家应该知道同步异步，阻塞非阻塞是两个不同层面的问题，一个是operation 层面，一个是 kernal 层面。同步异步最大的区别在于是否需要底层的响应再执行。阻塞非阻塞最大的区别在于是否立即给出响应。

官话

同步：当一个同步调用发出后，调用者要一直等待返回结果。通知后，才能进行后续的执行。

异步：当一个异步过程调用发出后，调用者不能立刻得到返回结果。实际处理这个调用的部件在完成后，通过状态、通知和回调来通知调用者。

阻塞：是指调用结果返回前，当前线程会被挂起，即阻塞。

非阻塞：是指即使调用结果没返回，也不会阻塞当前线程。

形象比喻：

进程和线程的相关题

官话：

进程：进程是系统进行资源分配和调度的一个独立单位，是系统中的并发执行的单位。

别背了，我知道你们都会背，举个例子：

计算机中的核心是 CPU，说它是我们的大脑一点不为过。在此用一个连锁火锅店举例，因为疫情的影响，今天到目前营业额一般，只好开一家店，其它疫情较为严重的店只好先关闭，这里涉及的含义：单个 CPU 一次只运行一个任务。

进程就类似这家火锅店，它代表 CPU 所能处理的单个任务，其他地方火锅店只能处于非运行状态。

一个火锅店有很多服务员，一起协同工作，将火锅店做的红红火火，那么线程就好比这些服务员，一个进程可有多个线程。

火锅店各个工作房间是共享的，所有服务员都可以进出，这意味着进程的内存空间共享，每个线程都可以使用这些共享内存。但是不是每个房间都可以容纳相同的人数，比如卫生间就只有一个人，其他人不能同时进去。

这意味着一个线程在使用共享内存的时候，其它线程需要等待结束才能使用这块内存。那怎么防止别人进入呢？很直接的办法就是进去之后记得关门(上锁)，上了锁，其他人想进来发现是上锁了，那就等锁打开后再进去，这就叫做互斥锁，防止多个线程同时读写某一块内存区域。

ok到这里，我们总结一波：

多线程与多进程的基本概念

不知道大家经历过食堂打菜的场景没有，如果学校食堂就开设一个窗口，打菜的阿姨也没办法，只好一个个给大家依次打菜，这就好比"单线程"，效率非常低(此处可以考虑为什么redis使用单线程却这么牛逼)。

为了提高效率，在食堂多加了几个窗口，这就类似"多线程"形式。

那么又想起一个问题，“多线程一定就比单线程效率高麦？”（ps Memcache是多线程模型而Redis是单线程模型)

貌似我们一提到高并发，分布式，就不得不想起多线程，那么多线程一定比单线程效率高？

上面说了采用多线程多核效果更好，但是多线程对 CPU，内存等都要求比较高，如果存在的上下文切换过于耗时，互斥时间太久，效率反而会低。

不一定。我不从专业术语来将，举个例子，假设目前接水房有四个水管可以接水，我如果用4个桶分别对应4个水管，那么就比较完美，如果少一个则闲置一个，多一个则会出现抢占。

如果此时我的水桶个数大于水管数，为了每个桶都有水，我们就需要切换水桶，这个过程实际上就是线程的上下文切换，代价一样不小。

多线程与多进程的应用场景

多线程的优点：

多进程的优点：

如何提升多线程的效率？

进程的状态转换

在Linux中，进程的状态有七种：

英文名词为TASK_RUNNING，其实这个状态虽然是RUNING，实际上并不一定会占有 CPU，可能修改TASK_RUNABLE会更妥当。TASK_RUNGING根据是否在在 CPU上运行分为RUNGING和READY两种状态。处于READY状态的进程随时可以运行，只不过因为此时 CPU 资源受限，调度器没选中运行。

可运行状态

我们知道进程不可能一直处于可运行的状态。假设A进程需要读取磁盘中的文件，这样的系统调用消耗时间较长，进程需要等待较长的时间才能执行后面的命令，而且等待的时间还是不可估算的，这样的话进程还占用 CPU 就不友好了，因此内核就会将其更改为其他的状态并从 CPU 可运行的队列移除。

Linux中存在两种睡眠状态，分别为：可中断的睡眠状态和不可中断的状态。两者最大的区别为是否响应收到的信号，那么从可中断的睡眠的进程是如何返回到可运行的状态呢？

处于此状态的进程，收到信号会返回EINTR给用户空间。开发者通过检测返回值的方式进行后续逻辑处理

但是对于不可中断的睡眠状态，就只有一种方式返回到可运行状态，即等待事情发生了继续运行。

上图中为什么出现个 TASK_UNINTERRUPTIBLE状态，主要是因为内核中的进程不是什么进程都可以被打断，假设响应的是异步信号，程序在执行的过程中插入一段用于处理异步信号的而流程，原来的流程就会被中断。

所以当进程在和硬件打交道的时候，需要使用 TASK_UNINTERRUPTIBLE状态将进程保护起来，从而避免进程和设备打交道的过程中被打断导致设备处于不可控的状态。

那么TASK_UNINTERRUPTIBLE状态会出现多久呢？

其实 TASK_UNINTERRUPTIBLE 状态是很危险的状态，因为它刀枪不入，你无法通过信号杀死这样一个不可中断的休眠状态，正常情况，TASK_UNINTERRUPTIBLE状态存在时间很短，但是不排除存在此状态进程比较持久的情况，真的刀枪不入了？可不可以进行提前的预防？

可以的，早就考虑了。内核提供了hung task机制，它会启动一个khungtaskd内核线程对TASK_UNINTERRUPTIBLE状态进行检测，不能让它失控了。khungtaskd会定期的唤醒，如果超过120s都还没有调度，内核就会通过打印警告和堆栈信息。当然，不一定就是120s，可以通过下面选项进行定制：

sysctl kernel.hung_task_timeout_secs

说了这么多，我们怎么知道到底有没有出现这个状态，哪里看？可以通过/proc和ps进行查看。

不管是上面提到的可中断的睡眠进程还是不可中断的睡眠进程，都离不开一种数据结构---队列。

假设进程A因为某某原因需要休眠，为啥要休眠，等待的资源迟迟拿不到或者等待的事件总是不来，没法进行下一步操作，这个时候内核来了，"行吧，我不会抛弃你，我一定会想办法让你和等待的资源(事件)扯上关系"，只要等待的时机到来我就唤醒你，这采用的方法即"等待队列"。

TASK_STOPPED状态属于比较特殊的状态，可以通过SIGCONT信号回复进程的执行

TASK_STOPPED

TASK_TRACED是被跟踪的状态，进程会停下来等待跟踪它的进程对它进行进一步的操作

当进程储于这两种的任意一种，就可以宣布"死亡" 。

三状态

就绪 —> 执行：准备就绪，调度器满足了的需求，给我一种策略，我就可从就绪变为执行的状态；

执行 —> 阻塞：不是每个进程都是那么一帆风顺，就像我们每次考试，不管是中考，高考还是考研，难免都会出现磕磕绊绊，遇到了可能暂时会阻挡我们前行的小事儿，可是要相信不会一直的阻挡我们，只要我们有恒心坚持，时机到来，你也准备好了，那就美哉。

回到这里，对于进程而言，当需要等到某个事情发生而无法执行的时候，进程就变为阻塞的状态。比如当前进程提出输入请求，如进程提出输入/输出请求，进程所申请资源（主存空间或外部设备）得不到满足时变成等待资源状态，进程运行中出现了故障（程序出错或主存储器读写错等）变成等待干预状态等等；

阻塞 —> 就绪：处于阻塞状态的进程，在其等待的事件已经发生，如输入/输出完成，资源得到满足或错误处理完毕时，处于等待状态的进程并不马上转入执行状态，而是先转入就绪状态，然后再由系统进程调度程序在适当的时候将该进程转为执行状态；

执行 —> 就绪：正在执行的进程，因时间片用完而被暂停执行，或在采用抢先式优先级调度算法的系统中,当有更高优先级的进程要运行而被迫让出处理机时，该进程便由执行状态转变为就绪状态。

进程间的通信方式有哪些？

管道

学习软件工程规范的时候，我们知道瀑布模型，在整个项目开发过程分为多个阶段，上一阶段的输出作为下一阶段的输入。各个阶段的具体内容如下图所示：

最初我们在学习Linux基本命令使用的时候，我们经常通过多个命令的组合来完成我们的需求。比如说我们想知道如何查看进程或者端口是否在使用，会使用下面的这条命令：

netstat -nlp | grep XXX

这里的"|"实际上就是管道的意思。"|"前面部分作为"|"后面的输入，很明显是单向的传输，这样的管道我们叫做"匿名管道"，自行创建和销毁。既然有匿名管道，应该就有带名字的管道"命名管道"。如果你想双向传输，可以考虑使用两个管道拼接即可。

创建命名管道的方式

mkfifo test

test即为管道的名称，在Linux中一切皆文件，管道也是以文件的方式存在，咋们可以使用ls -l 查看下文件的属性，它会"p"标识。

下面我们向管道写入内容：

echo "666" > test

此时按道理来说咋们已经将内容写入了test，没有直接输出是因为我们需要开启另一个终端进行输出(可以理解为暂存管道)。

cat < test

ok，我们发现管道内容被读出来，同时echo退出。

那么管道这种通信方式有什么缺点？我们知道瀑布模型的软件开发模式是非常低下的，同理采用管道进行通信的效率也很低，因为假设现在有AB两个进程，A进程将数据写入管道，B进程需要等待A进程将信息写完以后才能读出来，所以这种方案不适合频繁的通信。

那优点是什么？

最明显的优点就是简单，我们平时经常使用以致于都不知道这是管道。鉴于上面的缺点，我们怎么去弥补呢？接着往下看。

消息队列

管道通信属于一股脑的输入，能不能稍微温柔点有规矩点的发送消息？

答：可以的。消息队列在发送数据的时候，按照一个个独立单元(消息体)进行发送，其中每个消息体规定大小块，同时发送方和接收方约定好消息类型或者正文的格式。

在管道中，其大小受限且只能承载无格式字节流的方式，而消息队列允许不同进程以消息队列的形式发送给任意的进程。

但是当发送到消息队列的数据太大，需要拷贝的时间也就越多，所以还有其他的方式？继续看。

共享内存

使用消息队列可以达到不错的效果，但是如果我们两个部门需要交换比较大的数据的时候，一发一收还是不能及时的感知数据。能不能更好的办法，双方能很快的分享内容数据，答：有的，共享内存。

我们知道每个进程都有自己的虚拟内存空间，不同的进程映射到不同的物理内存空间。

那么我们可不可以申请一块虚拟地址空间，不同进程通过这块虚拟地址空间映射到相同的屋里地址空间呢？这样不同进程就可以及时的感知进程都干了啥，就不需要再拷贝来拷贝去。

我们可以通过 shmget 创建一份共享内存，并可以通过 ipcs 命令查看我们创建的共享内存。此时如果一个进程需要访问这段内存，需要将这个内存加载到自己虚拟地址空间的一个位置，让内核给它一个合法地址。使用完毕接触板顶并删除内存对象。

那么问题来了，这么多进程都共享这块内存，如果同时都往里面写内容，难免会出现冲突的现象，比如A进程写了数字5，B进程同样的地址写了6就直接给覆盖了，这样就不友好了，怎么办？继续往下看。

信号量

为了防止冲突，我们得有个约束或者说一种保护机制。使得同一份共享的资源只能一个进程使用，这里就出现了信号量机制。

信号量实际上是一个计数器，这里需要注意下，信号量主要实现进程之间的同步和互斥，而不是存储通信内容。

信号量定义了两种操作，p操作和v操作，p操作为申请资源，会将数值减去M，表示这部分被他使用了，其它进程暂时不能用。v操作是归还资源操作，告知归还了资源可以用这部分。

信号

从管道----消息队列-共享内存/信号量，有需要等待的管道机制，共享内存空间的进程通信方式，还有一种特殊的方式--信号。

我们或许听说过运维或者部分开发需要7 * 24小时值守(项目需要上线的时候)，当然也有各种监管，告警系统，一旦出现系统资源紧张等问题就会告知开发或运维人员，对应到操作系统中，这就是信号。

在操作系统中，不同信号用不同的值表示，每个信号设置相应的函数，一旦进程发送某一个信号给另一个进程，另一进程将执行相应的函数进行处理。也就是说把可能出现的异常等问题准备好，一旦信号产生就执行相应的逻辑即可。

套接字

上面的几种方式都是单机情况下多个进程的通信方式，如果我想和相隔几千里的小姐姐通信怎么办？

这就需要套接字socket了。其实这玩意随处可见，我们平时的聊天，我们天天请求浏览器给予的响应等，都是这老铁。

小结

分享了一下几种进程间通信方式，希望大家能知其然并知其所以然，机械式的记忆容易忘记哦。

进程的调度算法有哪些？

调度算法是指：调度程序是内核的重要组成部分，决定这下一个要运行的进程。那么根据系统的资源分配策略所规定的资源分配算法。常用的调度算法有：先来先服务调度算法、 时间片轮转调度法、短作业优先调度算法、最短剩余时间优先、高响应比优先调度算法、优先级调度算法等等。

先来先服务让我们想起了队列的先进先出特性，每一次的调度都从队列中选择最先进入队列的投入运行。

先来先服务

先来理解轮转，假设当前进程A、B、C、D，按照进程到达的时间排序，而且每个进行都有着同样大小的时间片。如果这个进程在当前的时间片运行结束，啥事儿没有，直接将进程从队列移除完事儿。

如果进程在这个时间片跑完都没有结束，进程变为等待状态，放在进程尾部直到所有进程执行完毕。

为什么进程要切换，切换无外乎是时间片够用或者不够用。如果时间片够用，那么进程可以运行到结束，结束后删除启动新的时间片。

如果时间片不够用，对不起，暂时只能完成一部分任务(变为等待状态)，过后再等待 CPU 的调度。网上开源的代码太多，怎么实现，大家可以参照加深影响。

短作业优先调度算法，从名称可以清晰的知道「短作业」意味着执行时间比较短，「优先」代表执行顺序。结合就是"短者吃香"。那么多短吃香？进程不可能都短，也有需要执行时间比较长的进程怎么办？

一直等待，直到饿死麦？而且有些进程比较紧急，能够得到先执行？这些都是此算法所出现的问题，然后出现下面的一些算法。

最短剩余时间是针对最短进程优先增加了抢占机制的版本。在这种情况下，进程调度总是选择预期剩余时间最短的进程。

当一个进程加入到就绪队列时，他可能比当前运行的进程具有更短的剩余时间，因此只要新进程就绪，调度程序就能可能抢占当前正在运行的进程。像最短进程优先一样，调度程序正在执行选择函数是必须有关于处理时间的估计，并且存在长进程饥饿的危险。

什么是高响应比，有响应之前应该会有请求，相当于是请求+响应+优先，算是一种综合的调度算法。也就是它结合了短作业优先，先来先服务以及长作业的一些特性。ok，那么这三种是如何体现出来的：

首先来说短作业优先。等待时间我们假设相等，服务时间很短，这样的话短作业就会有更高的优先权。

再来看先来先服务。假设服务时间相同，先来的自然等待时间较长，优先级越高。

上面说长作业很可能因为等待时间过长，容易饿死。在这里不会，仿佛像医生的这个职业，工作越久资历越老，优先级越来越高，越来越吃香。

优先级调度算法每次从后备作业队列中选择优先级最髙的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。在进程调度中，优先级调度算法每次从就绪队列中选择优先级最高的进程，将处理机分配给它，使之投入运行。

什么是死锁？

死锁，顾名思义就是导致线程卡死的锁冲突，例如下面的这种情况：

死锁

线程 1 已经成功拿到了互斥量 1，正在申请互斥量 2，而同时在另一个CPU 上，线程 2 已经拿到了互斥量 2，正在申请互斥量 1。

彼此占有对方正在申请的互斥量，结局就是谁也没办法拿到想要的互斥量，于是死锁就发生了。

资源占用

稍微复杂一点的情况：

存在多个互斥量的情况下，避免死锁最简单的方法就是总是按照一定的先后顺序申请这些互斥量。

还是以刚才的例子为例，如果每个线程都按照先申请互斥量 1 ，再申请互斥量 2 的顺序执行，死锁就不会发生。

有些互斥量有明显的层级关系，但是也有一些互斥量原本就没有特定的层级关系，不过没有关系，可以人为干预，让所有的线程必须遵循同样的顺序来申请互斥量。

产生死锁的原因？

由于系统中存在一些不可剥夺资源，而当两个或两个以上进程占有自身资源，并请求对方资源时，会导致每个进程都无法向前推进，这就是死锁。

例如：系统中只有一台打印机，可供进程 A 使用，假定 A 已占用了打印机，若 B 继续要求打印机打印将被阻塞。

系统中的资源可以分为两类：

  1. 可剥夺资源：是指某进程在获得这类资源后，该资源可以再被其他进程或系统剥夺， CPU 和主存均属于可剥夺性资源；

  2. 不可剥夺资源，当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放，如磁带机、打印机等。

  3. 进程推进顺序不当

例如：进程 A 和 进程 B 互相等待对方的数据。

死锁产生的必要条件？

互斥

要求各个资源互斥，如果这些资源都是可以共享的，那么多个进程直接共享即可，不会存在等待的尴尬场景。

非抢占

要求进程所占有的资源使用完后主动释放即可，其他的进程休想抢占这些资源。原因很简单，如果可以抢占，直接拿就好了，不会进入尴尬的等待场景。

要求进程是在占有（holding）至少一个资源的前提下，请求（waiting）新的资源的。由于新的资源被其它进程占有，此时，发出请求的进程就会带着自己占有的资源进入阻塞状态。假设 P1，P2 分别都需要 R1，R2 资源，如果是下面这种方式：

P1:          P2:
request(R1)  request(R2)
request(R2)  request(R1)

如果 P1 请求到了 R1 资源之后，P2 请求到了 R2资源，那么此后不管是哪个进程再次请求资源，都是在占有资源的前提下请求的，此时就会带着这个资源陷入阻塞状态。P1 和 P2 需要互相等待，发生了死锁。

换一种情况：

P1:          P2:
request(R1)  request(R1)
request(R2)  request(R2)

如果 P1 请求到了 R1 资源，那么 P2 在请求 R1 的时候虽然也会阻塞，但是是在不占有资源的情况下阻塞的，不像之前那样占有 R2。

所以，此时 P1 可以正常完成任务并释放 R1，P2 拿到 R1 之后再去执行任务。这种情况就不会发生死锁。

要求存在一条进程资源的循环等待链，链中的每一个进程占有的资源同时被另一个进程所请求。

发生死锁时一定有循环等待（因为是死锁的必要条件），但是发生循环等待的时候不一定会发生死锁。这是因为，如果循环等待链中的 P1 和 链外的 P6都占有某个进程 P2 请求的资源，那么 P2 完全可以选择不等待 P1 释放该资源，而是等待 P6 释放资源。这样就不会发生死锁了。

解决死锁的基本方法？

如果我们已经知道死锁形成的必要条件，逐一攻破即可。

通过与锁完全不同的同步方式CAS，CAS提供原子性支持，实现各种无锁的数据结构，不仅可以避免互斥锁带来的开销也可避免死锁问题。

如果一个线程已经获取到了一些锁，那么在这个线程释放锁之前这些锁是不会被强制抢占的。但是为了防止死锁的发生，我们可以选择让线程在获取后续的锁失败时主动放弃自己已经持有的锁并在之后重试整个任务，这样其他等待这些锁的线程就可以继续执行了。这样就完美了吗？当然不。

这种方式虽然可以在一定程度上避免死锁，但是如果多个相互存在竞争的线程不断的放弃重启放弃循环，就会出现活锁的问题，此时线程虽然没有因为锁冲突被卡死，但是仍然会因为阻塞时间太长处于重试当中。

怎么办？

方案1：给任务重试部分增加随机延迟时间，降低任务冲突的概率。

在实践的过程中，采用破坏环路等待的方式非常常见，这种技术叫做"锁排序"。很好理解，我们假设现在有个数组A，采用单向访问的方式(从前往后)，依次访问并加锁，这样一来，线程只会向前单向等待锁释放，自然也就无法形成一个环路了。

说到这里，我想说死锁不仅仅出现在多线程编程领域，在数据库的访问也是非常的常见，比如我们需要更新数据库的几行数据，就得先获取这些数据的锁，然后通过排序的方式阻止数据层发生死锁。

这样就完美了？当然没有，那会出现什么问题？

这种方案也存在它的缺点，比如在大型系统当中，不同模块直接解耦和隔离得非常彻底，不同模块开发人员不清楚其细节，在这样的情况下就很难做到整个系统层面的全局锁排序了。

在这种情况下，我们可以对方案进行扩充，例如Linux在内存映射代码就使用了一种锁分组排序的方式来解决这个问题。锁分组排序首先按模块将锁分为了不同的组，每个组之间定义了严格的加锁顺序，然后再在组内对具体的锁按规则进行排序，这样就保证了全局的加锁顺序一致。

在Linux的对应的源码顶部，我们可以看到有非常详尽的注释定义了明确的锁排序规则。

这种解决方案如果规模过大的话即使可以实现也会非常的脆弱，只要有一个加锁操作没有遵守锁排序规则就有可能会引发死锁。

不过在像微服务之类解耦比较充分的场景下，只要架构拆分合理，任务模块尽可能小且不会将加锁范围扩大到模块之外，那么锁排序将是一种非常实用和便捷的死锁阻止技术。

怎么预防死锁？

破坏请求条件：一次性分配所有资源，这样就不会再有请求了；

破坏请保持条件：只要有一个资源得不到分配，也不给这个进程分配其他的资源；

破坏不可剥夺条件：当某进程获得了部分资源，但得不到其它资源，则释放已占有的资源；

破坏环路等待条件：系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反。

怎么避免死锁？

当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。

当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请资源数之和是否超过了该进程对资源的最大需求量。

若超过则拒绝分配资源。若没超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若满足则按当前的申请量分配资源，否则也要推迟分配。

是指系统能按某种进程推进顺序（P1, P2, P3, …, Pn），为每个进程 Pi 分配其所需要的资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺序地完成。

这种推进顺序就叫安全序列【银行家算法的核心就是找到一个安全序列】。

如果系统能找到一个安全序列，就称系统处于安全状态，否则，就称系统处于不安全状态。

怎么解除死锁？

什么是缓冲区溢出？有什么危害？

官话

缓冲区溢出是指当计算机向缓冲区内填充数据时超过了缓冲区本身的容量，溢出的数据覆盖在合法数据上。

举个例子：

一个两升的杯子，你如果想导入三升，怎么做？其它一升只好流出去，不是打湿了电脑就是那啥。

物理地址、逻辑地址、线性地址

我们平时的应用程序都是通过和逻辑地址打交道，至于分页，分段机制对他们而言是透明得。逻辑地址也称作虚拟地址

在Intelk 80386中地址空间容量为4G，各个进程地址空间隔离，意味着每个进程独享4G线性空间。多个进程难免出现进程之间的切换，线性空间随之切换。基于分页机制，对于4GB的线性地址一部分会被映射到物理内存，一部分映射到磁盘作为交换文件，一部分没有映射，通过下面加深一下印象。

分页与分段的区别？

我们知道计算机的五大组成部分分别为运算器，存储器，存储器 ，输入和输出设备。我们的数据或者指定都需要存放内存然后给 CPU大哥拿去执行。

我们平时写的代码不是直接操作的物理地址，我们所看到的地址实际上叫做虚拟地址，通过相应的转换规则将虚拟地址转换为物理地址。

那么虚拟地址是怎么转换为物理地址的呢？

第一种方式，采用一个映射表代表虚拟地址到物理地址的映射，在计算机中我们叫做页表。页表将内存地址分为页号和偏移量，举个例子：

我们将高位部分称为内存地址的页号，后面的低位叫做内存地址的偏移量。我们只需要保存虚拟地址内存的页号和物理内存页号之间的映射关系即可。

这样说了，也就是三部曲：

这样的方法，在32位的内存地址，页表需要多大的空间？

在一个32位的内存地址空间，页表需要记录2^20个物理页面的映射关系，可以想象为要给数组。那么一个页号是完整的4字节。这样一个页表就是4MB。

再来，我们知道进程有各自的虚拟内存空间，也就是说每个进程都需要一个这样的页表，不管此进程是只有几KB的程序还是需要GB的内存空间都需要这样的页表，用这样的结构保存页面，内存的占用将非常的大，那其他方式是怎么样的呢

多级页表

同样的虚拟内存地址，偏移量部分和上面方式一样，但是我们将页号部分拆分为四段，从高到低分成4级到1级的4个页表索引：

二级索引

这样一来，每个进程将有4级页表。通过4级页表的索引找到对应的条目。

通过这个条目找到3级页表所在位置，4级的每一个条目可能有多个3级的条目，找到了3级的条目后找到对应3级索引的条目，就这样到达1级页表。

1级对应的则为物理页号。最终通过物理页号+偏移量的方式获取物理内存地址。

为什么使用多级页表

这样一来，随着虚拟地址空间的增大，需要存放页表所需的连续空间也就越来多大。如果使用多级页表，我们只需要一页存放目录项，页表存放在内存其他位置即可，下面有例子进一步讲解。

举个例子：

假设虚拟地址空间为4G，A进程只是用 4M 的内存空间。对于一级页表，我们需要 4M 空间存放这4GB 虚拟地址对应的页表，然后找到进程真正的 4M 内存空间。这样的话，A进程本来只使用 4MB 内存空间，但是为了访问它，我们需要为所有的虚拟地址空间建立页表，岂不是很浪费。

对于二级页表而言，使用一个页目录就可定位 4M 的内存，存放一个页目录项需要 4k，还需要一页存放进程使用的 4M，4M=1024*4k，也就相当于 1024 个页表项就可以映射4M的内存空间，那么总共就只需要4k(页表)+4k(页目录)=8k来存放进程需要的 4M 内存空间对应页表和页目录项。这样看来确实剩下不少的内存。

那使用多级页表有啥缺点？

还是有的，咋们使用一级页表的时候，只需要访问两次内存，一次是访问页表项，一次是访问需要读取的一页数据。如果是二级页表，就需要访问三次，第一次访问页目录，第二次访问页表项，第三次访问读取的数据。访问次数的增加以为访问数据所花费的总时间也增加。

页面置换算法有哪些？

请求调页，也称按需调页，即对不在内存中的“页”，当进程执行时要用时才调入，否则有可能到程序结束时也不会调入。而内存中给页面留的位置是有限的，在内存中以帧为单位放置页面。

为了防止请求调页的过程出现过多的内存页面错误（即需要的页面当前不在内存中，需要从硬盘中读数据，也即需要做页面的替换）而使得程序执行效率下降，我们需要设计一些页面置换算法，页面按照这些算法进行相互替换时，可以尽量达到较低的错误率。常用的页面置换算法如下：

先进先出，即淘汰最早调入的页面。

选未来最远将使用的页淘汰，是一种最优的方案，可以证明缺页数最小。

即选择最近最久未使用的页面予以淘汰

时钟置换算法也叫最近未用算法 NRU（Not RecentlyUsed）。该算法为每个页面设置一位访问位，将内存中的所有页面都通过链接指针链成一个循环队列。

书籍/视频学习推荐

书籍

视频

原文出处：进程和线程，我只问这19个问题

下面隆重推出我呕心沥血，耗时半个月完成的精心力作：

01什么是进程？

标准定义：进程是一个具有一定独立功能的程序在一个数据集合上依次动态执行的过程。进程是一个正在执行程序的实例，包括程序计数器、寄存器和程序变量的当前值。

简单来说进程就是一个程序的执行流程，内部保存程序运行所需的资源。

在操作系统中可以有多个进程在运行，可对于CPU来说，同一时刻，一个CPU只能运行一个进程，但在某一时间段内，CPU将这一时间段拆分成更短的时间片，CPU不停的在各个进程间游走，这就给人一种并行的错觉，像CPU可以同时运行多个进程一样，这就是伪并行。

02 进程和程序有什么联系？

一个进程是某种类型的一个活动，它有程序、输入、输出以及状态。单个处理器可以被若干进程共享，它使用某种调度算法决定何时停止一个进程的工作，并转而为另一个进程提供服务。

03进程和程序有什么区别？

进程是动态的，程序是静态的：程序是有序代码的集合，进程是程序的执行。

进程是暂时的，程序是永久的：进程是一个状态变化的过程，程序可长久保存。

进程和程序的组成不同：进程的组成包括程序、数据和进程控制块（进程状态信息）。

04 进程有什么特点？

动态性：可动态的创建和结束进程

并发性：可以被独立的调度并占用处理机并发运行

独立性：不同进程的工作不相互影响

制约性：因访问共享资源或进程间同步而产生制约

05 进程如何创建？

有什么事件会触发进程的创建呢？

系统初始化：当启动操作系统时，通常会创建很多进程，有些是同用户交互并替他们完成工作的前台进程，其它的都是后台进程，后台进程和特定用户没有关系，但也提供某些专门的功能，例如接收邮件等，这种功能的进程也称为守护进程。计划任务是个典型的守护进程，它每分钟运行一次来检查是否有工作需要它完成。如果有工作要做，它就会完成此工作，然后进入休眠状态，直到下一次检查时刻的到来。

正在运行的程序执行了创建进程的系统调用：在一个进程中又创建了一个新的进程，这种情况很常见。

用户请求创建一个新进程：这种情况相信每个人都见过，用电脑时双击某个应用图标，就会有至少一个进程被创建。

一个批处理作业的初始化：这种情形不常见，仅在大型机的批处理系统中应用，用户在这种系统中提交批处理作业，在操作系统认为有资源可运行另一个作业时，它创建一个新的进程，并运行其输入队列中的下一个作业。

归根到底：在UNIX系统中，只有fork系统调用才可以创建新进程，使用方式如下：

#include <stdio.h>

进程创建之后，父子进程都有各自不同的地址空间，其中一个进程在其地址空间的修改对另一个进程不可见。子进程的初始化空间是父进程的一个副本，这里涉及两个不同地址空间，不可写的内存区是共享的，某些UNIX的实现使程序正文在两者间共享，因为它是不可修改的。

还有一种写时复制共享技术，子进程共享父进程的所有内存，一旦两者之一想要修改部分内存，则这块内存被复制确保修改发生在当前进程的私有内存区域。

06 进程为何终止？

有什么事件会触发进程的终止呢？

正常退出（自愿）：进程完成了工作正常终止，UNIX中退出进程的系统调用是exit。

出错退出（自愿）：进程发现了错误而退出。可以看如下代码：

#include <stdio.h>

严重错误（非自愿）：进程发生了严重的错误而不得不退出，通常是程序的错误导致，例如执行了一条非法指令，引用不存在的内存，或者除数是0等，出现这些错误时进程默认会退出。而有些时候如果用户想自行处理某种类型的错误，发生不同类型错误时进程会收到不同类型的信号，用户注册处理不同信号的函数即可。

被其它进程杀死（非自愿）：其它进程执行kill系统调用通知操作系统杀死某个进程。

07操作系统如何进行进程管理？

这里就不得不提到一个数据结构：进程控制块（PCB），操作系统为每个进程都维护一个PCB，用来保存与该进程有关的各种状态信息。进程可以抽象理解为就是一个PCB，PCB是进程存在的唯一标志，操作系统用PCB来描述进程的基本情况以及运行变化的过程，进程的任何状态变化都会通过PCB来体现。

PCB包含进程状态的重要信息，包括程序计数器、堆栈指针、内存分配状况、所打开文件的状态、账号和调度信息，以及其它在进程由运行态转换到就绪态或阻塞态时必须保存的信息，从而保证该进程随后能再次启动，就像从未中断过一样。后一小节会具体介绍PCB。

提到进程管理，有一个概念我们必须要知道，就是中断向量，中断向量是指中断服务程序的入口地址。一个进程在执行过程中可能会被中断无数次，但是每次中断后，被中断的进程都要返回到与中断发生前完全相同的状态。

中断发生后操作系统最底层做了什么呢？

  1. 硬件压入堆栈程序计数器等；
  2. 硬件从中断向量装入新的程序计数器；
  3. 汇编语言过程保存寄存器值；
  4. 汇编语言过程设置新的堆栈；
  5. C中断服务例程运行（典型的读和缓冲输入）；
  6. 调度程序决定下一个将运行的进程；
  7. C过程返回到汇编代码；
  8. 汇编语言过程开始运行新的当前进程。

08进程控制块中存储了什么信息？

进程标识信息：如本进程的标识，本进程的父进程标识，用户标识等。

处理机状态信息保护区：用于保存进程的运行现场信息：

进程控制信息：

09 进程如何进行生命周期管理？

进程创建：

创建进程有三个主要事件：

进程运行：内核选择一个就绪的进程，让它占用处理机并运行，这里就涉及到了进程的调度策略，选择哪个进程调度？为什么选择调度这个进程呢？（莫慌，下面会介绍哈）

进程等待：

在以下情况下进程会等待（阻塞）：

注意：进程只能自己阻塞自己，因为只有进程自身才能知道何时需要等待某种事件的发生。

进程唤醒：

进程只能被别的进程或操作系统唤醒，唤醒进程的原因有：

进程结束：

在以下四种情况下进程会结束：

10进程都有什么状态？

不同系统设置的进程状态是不同的，多数系统中的进程在生命结束前有三种基本状态，进程只会处于三种基本状态之一：

运行状态：进程正在处理机上运行时就处在运行状态，该时刻进程时钟占用着CPU；

就绪状态：万事俱备，只欠东风，进程已经获得了除处理机之外的一切所需资源，一旦得到处理机就可以运行；就绪态中的进程其实可以运行，但因为其它进程正在占用着CPU而暂时停止运行；

等待状态（阻塞状态）：进程正在等待某一事件而暂停运行，等待某个资源或者等待输入输出完成。除非某种外部事件发生，否则阻塞态的进程不能运行；

进程状态变化图如下：

在操作系统发现进程不能继续运行下去时，进程因为等待输入而被阻塞，进程从运行态转换到阻塞态！

调度程序选择了另一个进程执行时，当前程序就会从运行态转换到就绪态！

被调度程序选择的程序会从就绪态转换到运行态！

当阻塞态的进程等待的一个外部事件发生时，就会从阻塞态转换到就绪态，此时如果没有其他进程运行时，则立刻从就绪态转换到运行态！

某些系统设置下进程还会有其它状态：

创建状态：进程正在被创建还没被转到就绪状态之前的状态；

结束状态：进程正在从系统中消失时的状态。

有些与进程管理相关的系统调用读者有必要了解一下：

pid=fork(); // 创建一个与父进程一样的子进程
pid=waitpid(); // 等待子进程终止
s=execve(); // 替换进程的核心映像
exit(); // 终止进程运行并返回状态值
s=sigaction(); // 定义信号处理的动作
s=sigprocmask(); // 检查或更换信号掩码
s=sigpending(); // 获得阻塞信号集合
s=sigsuspend(); // 替换信号掩码或挂起进程
alarm(); // 设置定时器
pause(); // 挂起调用程序直到下一个信号出现

11 什么是进程挂起？为什么会出现进程挂起？

进程挂起就是为了合理且充分的利用系统资源，把一个进程从内存转到外存。进程在挂起状态时，意味着进程没有占用内存空间，处在挂起状态的进程映射在磁盘上。进程挂起通 常有两种状态：

有什么与进程挂起相关的状态转换？

进程挂起可能有以下几种情况：

阻塞到阻塞挂起：没有进程处于就绪状态或就绪进程要求更多内存资源时，会进行这种转换，以提交新进程或运行就绪进程；

就绪到就绪挂起：当有高优先级阻塞进程或低优先级就绪进程时，系统会选择挂起低优先级就绪进程；

运行到就绪挂起：对于抢占式分时系统，当有高优先级阻塞挂起进程因事件出现而进入就绪挂起时，系统可能会把运行进程转到就绪挂起状态；

阻塞挂起到就绪挂起：当有阻塞挂起进程有相关事件出现时，系统会把阻塞挂起进程转换为就绪挂起进程。

有进程挂起那就有进程解挂：指一个进程从外存转到内存，相关状态有：

就绪挂起到就绪：没有就绪进程或就绪挂起进程优先级高于就绪进程时，就会进行这种转换；

阻塞挂起到阻塞：当一个进程释放足够内存时，系统会把一个高优先级阻塞挂起进程转换为阻塞进程。12 什么是进程调度？操作系统对于进程调度都有什么策略？

当系统中有多个进程同时竞争CPU，如果只有一个CPU可用，那同一时刻只会有一个进程处于运行状态，操作系统必须要选择下一个要运行的是哪个进程，在操作系统中，完 成选择工作的这部分称为调度程序，该程序使用的算法称作调度算法。

12 什么时候进行调度？操作系统对于进程调度都有什么策略？

  1. 系统调用创建一个新进程后，需要决定是运行父进程还是运行子进程
  2. 一个进程退出时需要做出调度决策，需要决定下一个运行的是哪个进程
  3. 当一个进程阻塞在I/O和信号量或者由于其它原因阻塞时，必须选择另一个进程运行
  4. 当一个I/O中断发生时，如果中断来自IO设备，而该设备现在完成了工作，某些被阻塞的等待该IO的进程就成为可运行的就绪进程了，是否让新就绪的进程运行，或者让中断发生时运行的进程继续运行，或者让某个其它进程运行，这就取决于调度程序的抉择了。

调度算法可以分类：

非抢占式调度算法：挑选一个进程，然后让该进程运行直至被阻塞，或者直到该进程自动释放CPU，即使该进程运行了若干个小时，它也不会被强迫挂起。这样做的结果是，在时钟中断发生时不会进行调度，在处理完时钟中断后，如果没有更高优先级的进程等待，则被中断的进程会继续执行。简单来说，调度程序必须等待事件结束。

非抢占方式引起进程调度的条件：

抢占式调度算法：挑选一个进程，并且让该进程运行某个固定时段的最大值。如果在该时段结束时，该进程仍在运行，它就被挂起，而调度程序挑选另一个进程运行，进行抢占式调度处理，需要在时间间隔的末端发生时钟中断，以便CPU控制返回给调度程序，如果没有可用的时钟，那么非抢占式调度就是唯一的选择。简单来说，就是当前运行的进程在事件没结束时就可以被换出，防止单一进程长时间独占CPU资源。下面会介绍很多抢占式调度算法：优先级算法、短作业优先算法、轮转算法等。

调度策略：不同系统环境下有不同的调度策略算法。调度算法也是有KPI的，对调度算法首先提的需求就是：

但是因为不同的应用有不同的目标，不同的系统中，调度程序的优化也是不同的，大体可以分为三种环境：

批处理系统

批处理系统的管理者为了掌握系统的工作状态，主要关注三个指标：

调度算法：

1.先来先服务

先来后到嘛，就像平时去商店买东西需要排队一样，使用该算法，进程按照它们请求CPU的顺序来使用CPU，该算法最大的优点就是简单易于实现，太容易的不一定是好的，该算法也有很大的缺点：平均等待时间波动较大，时间短的任务可能排队排在了时间长的任务后面。举个生活中的例子，排着队去取快递，如果每个人都很快取出来快递还好，如果前面有几个人磨磨唧唧到快递柜前才拿出手机打开app，再找半分钟它的取件码，就会严重拖慢后面的人取快递的速度，同理排着队的进程如果每个进程都很快就运行完还好，如果其中有一个得到了CPU的进程运行时候磨磨唧唧很长时间都运行不完，那后面的进程基本上就没有机会运行了！

2.最短作业优先

该调度算法是非抢占式的算法，每个进程执行期间不会被打断，每次都选择执行时间最短的进程来调度，但问题来了，操作系统怎么可能知道进程具体的执行时间呢，所以该算法注定是基于预测性质的理想化算法，而且有违公平性，而且可能导致运行时间长的任务得不到调度。

3.最短剩余时间优先

该调度算法是抢占式的算法，是最短作业优先的抢占版本，在进程运行期间，如果来了个更短时间的进程，那就转而去把CPU时间调度给这个更短时间的进程，它的缺点和最短作业优先算法类似。

交互式系统

对于交互系统最重要的指标就是响应时间和均衡性啦：

调度算法：

1.轮转调度

每个进程被分配一个时间段，称为时间片，即CPU做到雨露均沾，轮流翻各个进程的牌子，这段时间宠幸进程A，下一段时间宠幸进程B，再下一段时间宠幸进程C，确保每个进程都可以获得CPU时间，如果CPU时间特别短的话，在外部看来像是同时宠幸了所有进程一样。那么问题来了，这个时间片究竟多长时间好呢？如果时间片设的太短会导致过多的进程切换，频繁的上下文切换会降低CPU效率，而如果时间片设的太长又可能对短的交互请求的响应时间变长，通常将时间片设为20-50ms是个比较合理的折中，大佬们的经验规则时维持上下文切换的开销处于1%以内。

2.优先级调度

上面的轮转调度算法是默认每个进程都同等重要，都有相同优先级，然而有时候进程需要设置优先级，例如某些播放视频的前台进程可以优先于某些收发邮件的后台守护进程被调度，在优先级调度算法中，每个优先级都有相应的队列，队列里面装着对应优先级的进程，首先在高优先级队列中进行轮转调度，当高优先级队列为空时，转而去低优先级队列中进行轮转调度，如果高优先级队列始终不为空，那么低优先级的进程很可能就会饥饿到很久不能被调度。

3.多级队列

多级队列算法与优先级调度算法不同，优先级算法中每个进程分配的是相同的时间片，而在多级队列算法中，不同队列中的进程分配给不同的时间片，当一个进程用完分配的时间片后就移动到下一个队列中，这样可以更好的避免上下文频繁切换。举例：有一个进程需要100个时间片，如果每次调度都给分配一个时间片，则需要100次上下文切换，这样CPU运行效率较低，通过多级队列算法，可以考虑最开始给这个进程分配1个时间片，然后被换出，下次分给它2个时间片，再换出，之后分给它4、8、16、64个时间片，这样分配的话，该进程只需要7次交换就可以运行完成，相比100次上下文切换运行效率高了不少，但顾此就会失彼，那些需要交互的进程得到响应的速度就会下降。

4.最短进程优先

交互式系统中应用最短进程优先算法其实是非常适合的，每次都选择执行时间最短的进程进行调度，这样可以使任务的响应时间最短，但这里有个任务，还没有运行呢，我怎么知道进程的运行时间呢？根本没办法非常准确的再当前可运行进程中找出最短的那个进程。有一种办法就是根据进程过去的行为进行预测，但这能证明是个好办法吗？

5.保证调度

这种调度算法就是向用户做出明确的可行的性能保证，然后去实现它。一种很实际的可实现的保证就是确保N个用户中每个用户都获得CPU处理能力的1/N，类似的，保证N个进程中每个进程都获得1/N的CPU时间。

6.彩票调度

彩票调度算法基本思想是为进程提供各种资源（CPU时间）的彩票，一旦需要做出调度决策时，就随机抽出一张彩票，拥有该彩票的进程获得该资源，很明显，拥有彩票越多的进程，获得资源的可能性越大。该算法在程序喵看来可以理解为股票算法，将CPU的使用权分成若干股，假设共100股分给了3个进程，给这些进程分别分配20、30、50股，那么它们大体上会按照股权比例（20：30：50）划分CPU的使用。

7.公平分享调度

假设有系统两个用户，用户1启动了1个进程，用户2启动了9个进程，如果使用轮转调度算法，那么用户1将获得10%的CPU时间，用户2将获得90%的CPU时间，这对用户来说公平吗？如果给每个用户分配50%的CPU时间，那么用户2中的进程获得的CPU时间明显比用户1中的进程短，这对进程来说公平吗？这就取决于怎么定义公平啦？

实时系统

实时系统顾名思义，最关键的指标当然是实时啦：

调度算法分类：

1.硬实时

必须在deadline之前完成工作，如果delay，可能会发生灾难性或发生严重的后果；

2.软实时

必须在deadline之前完成工作，但如果偶尔delay了，也可以容忍。

调度算法：

1.单调速率调度

采用抢占式、静态优先级的策略，调度周期性任务。

每个任务最开始都被配置好了优先级，当较低优先级的进程正在运行并且有较高优先级的进程可以运行时，较高优先级的进程将会抢占低优先级的进程。在进入系统时，每个周期性任务都会分配一个优先级，周期越短，优先级越高。这种策略的理由是：更频繁的需要CPU的任务应该被分配更高的优先级。

2.最早截止时间调度

根据截止时间动态分配优先级，截止时间越早的进程优先级越高。

该算法中，当一个进程可以运行时，它应该向操作系统通知截止时间，根据截止时间的早晚，系统会为该进程调整优先级，以便满足可运行进程的截止时间要求。它与单调速率调度算法的区别就是一个是静态优先级，一个是动态优先级。

3.如何配置调度策略？

调度算法有很多种，各有优缺点，操作系统自己很少能做出最优的选择，那么可以把选择权交给用户，由用户根据实际情况来选择适合的调度算法，这就叫策略与机制分离，调度机制位于内核，调度策略由用户进程决定，将调度算法以某种形式参数化，由用户进程来选择参数从而决定内核使用哪种调度算法。

13操作系统怎么完成进程调度？

进程的每次变化都会有相应的状态，而操作系统维护了一组状态队列，表示系统中所有进程的当前状态；不同的状态有不同的队列，有就绪队列阻塞队列等，每个进程的PCB都 根据它的状态加入到相应的队列中，当一个进程的状态发生变化时，它的PCB会从一个状态队列中脱离出来加入到另一个状态队列。

注意图中同一种状态为什么有多个队列呢？因为进程有优先级概念，相同状态的不同队列的优先级不同。

14 什么是线程？

线程是进程当中的一条执行流程，这几乎就是进程的定义，一个进程内可以有多个子执行流程，即线程。可以从两个方面重新理解进程：

15 为什么使用线程？

因为要并发编程，在许多情形中同时发生着许多活动，而某些活动有时候会被阻塞，通过将这些活动分解成可以准并行运行的多个顺序流程是必须的，而如果使用多进程方式进行并发编程，进程间的通信也很复杂，并且维护进程的系统开销较大：创建进程时分配资源建立PCB，撤销进程时回收资源撤销PCB，进程切换时保存当前进程的状态信息。所以为了使并发编程的开销尽量小，所以引入多线程编程，可以并发执行也可以共享相同的地址空间。并行实体拥有共享同一地址空间和所有可用数据的能力，这是多进程模型所不具备的能力。

使用线程有如下优点：

但也有缺点：

16 什么时候用进程、线程？

  1. 进程是资源分配单位，线程是CPU调度单位；
  2. 进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈；
  3. 线程同样具有就绪阻塞和执行三种基本状态，同样具有状态之间的转换关系；
  4. 线程能减少并发执行的时间和空间开销：
  5. 线程的创建时间比进程短
  6. 线程的终止时间比进程短
  7. 同一进程内的线程切换时间比进程短
  8. 由于同一进程的各线程间共享内存和文件资源，可直接进行不通过内核的通信

结论：可以在强调性能时候使用线程，如果追求更好的容错性可以考虑使用多进程，google浏览器据说就是用的多进程编程。在多CPU系统中，多线程是有益的，在这样的系统中，通常情况下可以做到真正的并行。

C/C++中如何使用多线程编程？

POSIX使用如下线程封装函数来操作线程：

pthread_create               创建一个新线程
pthread_exit                 结束调用的线程
pthread_join                 等待一个特定的线程退出
pthread_yield                释放CPU来运行另外一个线程
pthread_attr_init            创建并初始化一个线程的属性结构
pthread_attr_destroy         删除一个线程的属性结构

后两个函数是有关线程属性的调用。pthread_attr_init建立关联一个线程的属性结构并初始化成默认值，这些值（优先级等）可以通过修改属性结构中的对应值来改变；pthread_attr_destroy会删除一个线程的属性结构，释放它占用的内存，它不会影响调用它的线程，线程依然会继续存在。

C++中有std::thread和async，可以很方便的操作多线程，示例代码如下：

void F() {
        cout << "a" << endl;
    }

    int main() {
        std::thread r(F);
        r.detach();
        std::this_thread::sleep_for(std::chrono::seconds(20));
        return 0;
    }

想了解更多关于C++线程相关的知识点可以看：

c++11新特性，所有知识点都在这了！

17 线程是如何实现的？

线程的实现可分为用户线程和内核线程：

用户线程：在用户空间实现的线程机制，它不依赖于操作系统的内核，由一组用户级的线程库函数来完成线程的管理，包括进程的创建终止同步和调度等。

用户线程有如下优点：

但用户线程也有缺点：

内核线程：是指在操作系统的内核中实现的一种线程机制，由操作系统的内核来完成线程的创建终止和管理。

特点：

tips

由于在内核中创建或撤销线程的代价比较大，某些系统采取复用的方式回收线程，当某个线程被撤销时，就把它标记不可运行，但是内核数据结构没有受到任何影响，如果后续又需要创建一个新线程时，就重新启动被标记为不可运行的旧线程，从而节省一些开销。

注意

尽管使用内核线程可以解决很多问题，但还有些问题，例如：当一个多线程的进程创建一个新的进程时会发生什么？新进程是拥有与原进程相同数量的线程还是只有一个线程？在很多情况下，最好的选择取决于进程计划下一步做什么？如果它要调用exec启动一个新程序，或许一个线程正合适，但如果它继续运行，那么最好复制所有的线程。

轻量级进程：它是内核支持的用户线程模型，一个进程可以有多个轻量级进程，每个轻量级进程由一个单独的内核线程来支持。

在Linux下是没有真正的线程的，它所谓的线程其实就是使用进程来实现的，就是所谓的轻量级进程，其实就是进程，都是通过clone接口调用创建的，只不过两者传递的参数不同，通过参数决定子进程和父进程共享的资源种类和数量，进而有了普通进程和轻量级进程的区别。 18 什么是上下文切换？

上下文切换指的是操作系统停止当前运行进程（从运行状态改变成其它状态）并且调度其它进程（就绪态转变成运行状态）。操作系统必须在切换之前存储许多部分的进程上下文，必须能够在之后恢复他们，所以进程不能显示它曾经被暂停过，同时切换上下文这个过程必须快速，因为上下文切换操作是非常频繁的。那上下文指的是什么呢？指的是任务所有共享资源的工作现场，每一个共享资源都有一个工作现场，包括用于处理函数调用、局部变量分配以及工作现场保护的栈顶指针，和用于指令执行等功能的各种寄存器。

注意

这里所说的进程切换导致上下文切换其实不太准确，准确的说应该是任务的切换导致上下文切换，这里的任务可以是进程也可以是线程，准确的说线程才是CPU调度的基本单位，但是因为各个资料都这么解释上下文切换，所以上面也暂时这么介绍，只要读者心里有这个概念就好。

19 进程间通信有几种方式？

由于各个进程不共享相同的地址空间，任何一个进程的全局变量在另一个进程中都不可见，所以如果想要在进程之间传递数据就需要通过内核，在内核中开辟出一块区域，该区域对多个进程都可见，即可用于进程间通信。有读者可能有疑问了，文件方式也是进程间通信啊，也要在内核开辟区域吗？这里说的内核区域其实是一段缓冲区，文件方式传输数据也有内核缓冲区的参与（零拷贝除外）。

如何开辟这种公共区域来进行进程间通信呢？

匿名管道

匿名管道就是pipe，pipe只能在父子进程间通信，而且数据只能单向流动（半双工通信）。

使用方式：

1）父进程创建管道，会得到两个文件描述符，分别指向管道的两端；

2）父进程创建子进程，从而子进程也有两个文件描述符指向同一管道；

3）父进程可写数据到管道，子进程就可从管道中读出数据，从而实现进程间通信，下面的示例代码中通过pipe实现了每秒钟父进程向子进程都发送消息的功能。

#include <stdio.h>
#include <string.h>
#include <unistd.h>

int main() {
    int _pipe[2];
    int ret = pipe(_pipe);
    if (ret < 0) {
        perror("pipe\n");
    }

    pid_t id = fork();

    if (id < 0) {
        perror("fork\n");
    } else if (id == 0) {  // 子进程
        close(_pipe[1]);
        int j = 0;
        char _mesg[100];
        while (j < 100) {
            memset(_mesg, '\0', sizeof(_mesg));
            read(_pipe[0], _mesg, sizeof(_mesg));
            printf("%s\n", _mesg);
            j++;
        }
    } else {  // 父进程
        close(_pipe[0]);
        int i = 0;
        char *mesg = NULL;
        while (i < 100) {
            mesg = "父进程来写消息了";
            write(_pipe[1], mesg, strlen(mesg) + 1);
            sleep(1);
            ++i;
        }
    }
    return 0;
}

我们平时也经常使用关于管道的命令行：

ls | less

该命令行的流向图如下：

1：创建管道

2：为ls创建一个进程，设置stdout为管理写端

3：为less创建一个进程，设置stdin为管道读端

高级管道

通过popen将另一个程序当作一个新的进程在当前进程中启动，它算作当前进程的子进程，高级管道只能用在有亲缘关系的进程间通信，这种亲缘关系通常指父子进程，下面的GetCmdResult函数可以获取某个Linux命令执行的结果，实现方式就是通过popen。

std::string GetCmdResult(const std::string &cmd, int max_size = 10240) {
    char *data = (char *)malloc(max_size);
    if (data == NULL) {
        return std::string("malloc fail");
    }
    memset(data, 0, max_size);
    const int max_buffer = 256;
    char buffer[max_buffer];
    // 将标准错误重定向到标准输出
    FILE *fdp = popen((cmd + " 2>&1").c_str(), "r");
    int data_len = 0;
    if (fdp) {
        while (!feof(fdp)) {
            if (fgets(buffer, max_buffer, fdp)) {
                int len = strlen(buffer);
                if (data_len + len > max_size) {
                    cout << "data size larger than " << max_size;
                    break;
                }
                memcpy(data + data_len, buffer, len);
                data_len += len;
            }
        }
        pclose(fdp);
    }
    std::string ret(data, data_len);
    free(data);
    return ret;
}

命名管道

匿名管道有个缺点就是通信的进程一定要有亲缘关系，而命名管道就不需要这种限制。

命名管道其实就是一种特殊类型的文件，所谓的命名其实就是文件名，文件对各个进程都可见，通过命名管道创建好特殊文件后，就可以实现进程间通信。

可以通过mkfifo创建一个特殊的类型的文件，参数读者看名字应该就了解，一个是文件名，一个是文件的读写权限：

int mkfifo(const char* filename, mode_t mode);

当返回值为0时，表示该命名管道创建成功，至于如何通信，其实就是个读写文件的问题！

消息队列

队列想必大家都知道，像FIFO一样，这里可以有多个进程写入数据，也可以有多个进程从队列里读出数据，但消息队列有一点比FIFO还更高级，它读消息不一定要使用先进先出的顺序，每个消息可以赋予类型，可以按消息的类型读取，不是指定类型的数据还存在队列中。本质上MessageQueue是存放在内核中的消息链表，每个消息队列链表会由消息队列标识符表示，这个消息队列存于内核中，只有主动的删除该消息队列或者内核重启时，消息队列才会被删除。

在Linux中消息队列相关的函数调用如下：

// 创建和访问一个消息队列
int msgget(key_t, key, int msgflg);
// 用来把消息添加到消息队列中
int msgsend(int msgid, const void *msg_ptr, size_t msg_sz, int msgflg);
// msg_ptr是结构体数据的指针，结构第一个字段要有个类型：struct Msg {
    long int message_type;
    // 想要传输的数据
};
// 从消息队列中获取消息
int msgrcv(int msgid, void *msg_ptr, size_t msg_st, long int msgtype, int msgflg);
// 用来控制消息队列，不同的command参数有不同的控制方式
int msgctl(int msgid, int command, struct msgid_ds *buf);

示例代码如下：

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/msg.h>

#include <chrono>
#include <iostream>
#include <thread>

using namespace std;
#define BUFFER_SIZ 20

typedef struct {
    long int msg_type;
    char text[BUFFER_SIZ];
} MsgWrapper;

void Receive() {
    MsgWrapper data;
    long int msgtype = 2;
    int msgid = msgget((key_t)1024, 0666 | IPC_CREAT);
    if (msgid == -1) {
        cout << "msgget error \n";
        return;
    }
    while (true) {
        if (msgrcv(msgid, (void *)&data, BUFFER_SIZ, msgtype, 0) == -1) {
            cout << "error " << errno << endl;
        }
        cout << "read data " << data.text << endl;
        if (strlen(data.text) > 6) {  // 发送超过6个字符的数据，结束
            break;
        }
    }
    if (msgctl(msgid, IPC_RMID, 0) == -1) {
        cout << "msgctl error \n";
    }
    cout << "Receive ok \n";
}

void Send() {
    MsgWrapper data;
    long int msgtype = 2;
    int msgid = msgget((key_t)1024, 0666 | IPC_CREAT);
    if (msgid == -1) {
        cout << "msgget error \n";
        return;
    }
    data.msg_type = msgtype;
    for (int i = 0; i < 10; ++i) {
        memset(data.text, 0, BUFFER_SIZ);
        char a = 'a' + i;
        memset(data.text, a, 1);
        if (msgsnd(msgid, (void *)&data, BUFFER_SIZ, 0) == -1) {
            cout << "msgsnd error \n";
            return;
        }
        std::this_thread::sleep_for(std::chrono::seconds(1));
    }
    memcpy(data.text, "1234567", 7);
    if (msgsnd(msgid, (void *)&data, BUFFER_SIZ, 0) == -1) {
        cout << "msgsnd error \n";
        return;
    }
}

int main() {
    std::thread r(Receive);
    r.detach();
    std::thread s(Send);
    s.detach();
    std::this_thread::sleep_for(std::chrono::seconds(20));
    return 0;
}


输出：root@iZuf64idor3ej648ciairaZ:~## ./a.out
read data a
read data b
read data c
read data d
read data e
read data f
read data g
read data h
read data i
read data j
read data 1234567
Receive ok

代码中为了演示方便使用消息队列进行的线程间通信，该代码同样用于进程间通信，消息队列的实现依赖于内核的支持，上述代码可能在某些系统（WSL）上不能运行，在正常的Ubuntu上可以正常运行。

消息队列VS命名管道

1. 消息队列>命名管道

1）消息队列收发消息自动保证了同步，不需要由进程自己来提供同步方法，而命名管道需要自行处理同步问题；

2）消息队列接收数据可以根据消息类型有选择的接收特定类型的数据，不需要像命名管道一样默认接收数据。

2. 消息队列<命名管道

消息队列有一个缺点就是发送和接收的每个数据都有最大长度的限制。

共享内存

可开辟中一块内存，用于各个进程间共享，使得各个进程可以直接读写同一块内存空间，就像线程共享同一块地址空间一样，该方式基本上是最快的进程间通信方式，因为没有系统调用干预，也没有数据的拷贝操作，但由于共享同一块地址空间，数据竞争的问题就会出现，需要自己引入同步机制解决数据竞争问题。

共享内存只是一种方式，它的实现方式有很多种，主要的有mmap系统调用、Posix共享内存以及System V共享内存等。通过这三种“工具”共享地址空间后，通信的目的自然就会达到。

信号

信号也是进程间通信的一种方式，信号可以在任何时候发送给某一个进程，如果进程当前并未处于执行状态，内核将信号保存，直到进程恢复到执行态再发送给进程，进程可以对信号设置预处理方式，如果对信号设置了阻塞处理，则信号的传递会被延迟直到阻塞被取消，如果进程结束，那信号就被丢弃。我们常用的CTRL+C和kill等就是信号的一种，也达到了进程间通信的目的，进程也可以对信号设置signal捕获函数自定义处理逻辑。这种方式有很大的缺点：只有通知的作用，通知了一下消息的类型，但不能传输要交换的任何数据。

Linux系统中常见的信号有：

信号量

想必大家都听过信号量，信号量就是一个特殊的变量，程序对其访问都是原子操作，每个信号量开始都有个初始值。最简单最常见的信号量是只能取0和1的变量，也叫二值信号量。

信号量有两个操作，P和V：

P：如果信号量变量值大于0，则变量值减1，如果值为0，则阻塞进程；

V：如果有进程阻塞在该信号量上，则唤醒阻塞的进程，如果没有进程阻塞，则变量值加1

Q: 信号量和信号有什么关系？

A: 没有任何关系，完全是不同的东西。

Q: 信号量与互斥量有什么区别？

A: 互斥量用于互斥，信号量用于同步，互斥指的是某一资源同一时间只允许一个访问者访问，但无法限制访问顺序，访问是无序的，而同步在互斥的基础上可以控制访问者对资源的顺序。

套接字：就是网络传输，不用多说，网络通信都可以多机通信呢，更不用说进程间通信啦，你能看到程序喵的文章也是套接字的功劳。

文件：显而易见，多个进程可以操作同一个文件，所以也可以通过文件来进行进程间通信。关于进程和线程的知识点介绍就到这里，程序喵为了写本文花费了半月以上时间，相信你弄懂这19个问题，面试不用愁！

关于进程和线程的知识点介绍就到这里，程序喵为了写本文花费了半月以上时间，相信你弄懂这19个问题，面试不用愁！

参考资料