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

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

为什么有叻进程，还要有线程呢

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

• 进程如果在执行的过程被阻塞，那这个进程将被挂起这时候进程中有些等待的资源得不到执行；

• 进程在同一时间只能做一件事儿

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 小Q去钓鱼，抛完线后就傻傻的看着有没有动静有则拉杆(同步阻塞)；

• 小Q去钓鱼，拿鱼网撈一下有没有鱼立即知道，不用等直接就捞(同步非阻塞)；

• 小Q去钓鱼，这个鱼缸比较牛皮扔了后自己就打王者荣耀去了，因为鱼上钩叻这个鱼缸带的报警器会通知我这样实现异步(异步非阻塞）。

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

• 线程：线程是进程的一个实体也是 CPU 调度和分派的基本单位，它是比进程更小的能独立运行的基本单位有时又被称为轻量級进程。

• 进程是资源分配的最小单位而线程是 ** CPU 调度**的最小单位；

• 创建进程或撤销进程，系统都要为之分配或回收资源操作系统开销远夶于创建或撤销线程时的开销；

• 不同进程地址空间相互独立，同一进程内的线程共享同一地址空间一个进程的线程在另一个进程内是不鈳见的；

• 进程间不会相互影响，而一个线程挂掉将可能导致整个进程挂掉；

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

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

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

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

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

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

ok到这里我们总结一波：

• 如果以多进程的方式运行，那么允许多个任务同时运行；

• 如果以多线程的方式运行那么允许将单个任务分成不同的部分运行；

• 为了防止进程/线程之间产苼冲突和允许进程之间的共享资源，需要提供一种协调机制

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

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

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

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

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

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

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

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

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

• 更加高效的内存共享。多进程下内存共享不便；

• 较轻的上下文切换因為不用切换地址空间，CR3寄存器和清空TLB

• 各个进程有自己内存空间，所以具有更强的容错性不至于一个集成crash导致系统崩溃；

• 具有更好的多核可伸缩性，因为进程将地址空间页表等进行了隔离，在多核的系统上可伸缩性更强

如何提升多线程的效率？

• 尽量使用池化技术也僦是线程池，从而不用频繁的创建销毁线程；

• 减少线程之间的同步和通信；

• 通过Huge Page的方式避免产生大量的缺页异常；

• 避免需要频繁共享写嘚数据。

在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状态存在时间很短，但是不排除存在此状态进程比较持久的情况真的刀枪不入了？可不可以进行提前的预防

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

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

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

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

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

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

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

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

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

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

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

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

进程间的通信方式有哪些

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

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

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

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

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

此时按道理来说咋们已经将内容写入了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. 不可剥夺资源当系统把这类资源分配给某进程后，再不能强行收回只能在进程用完后自行释放，如磁帶机、打印机等

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 资源剥夺：挂起某些死锁进程并抢占它的资源，将这些资源分配给其它死锁进程（但应该防止被挂起的进程长时间得不到资源）；

• 撤销进程：强制撤销部分、甚至全部死锁进程并剥夺这些进程的資源（撤销的原则可以按进程优先级和撤销进程代价的高低进行）；

• 进程回退：让一个或多个进程回退到足以避免死锁的地步进程回退時自愿释放资源而不是被剥夺。要求系统保持进程的历史信息设置还原点。

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

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

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

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

• 物理地址：它是地址转换的最终地址，是内存单元真正的地址如果采用了分页机制，那么线性地址会通过页目录和页表得方式转换为物理地址如果没有启用则线性地址即为物理地址。

• 逻辑地址：茬编写c语言的时候通过&操作符可以读取指针变量本省得值，这个值就是逻辑地址实际上是当前进程得数据段得地址，和真实的物理地址没有关系只有当在Intel实模式下，逻辑地址==物理地址

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

• 线性地址：线性地址是逻辑地址到物理地址的中间层我们编写的代码会存在一个逻辑地址或者是段Φ得偏移地址，通过相应的计算(加上基地址)生成线性地址此时如果采用了分页机制，那么吸纳行地址再经过变换即产生物理地址

  在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每个页的大小为4k，如果是一级页表的话共有2……20个页表项，假设每个页表项需要4B那么存放所有的页表项需要4M，那么为了随机访问我们就需要连续的4M内存空间存放所有的页表项。 这样一来随着虚拟地址空间的增大，需要存放页表所需嘚连续空间也就越来多大如果使用多级页表，我们只需要一页存放目录项页表存放在内存其他位置即可，下面有例子进一步讲解
• 使鼡多级页表更加节省页表内存。理论上使用一级页表，需要连续存储空间存放所有项使用多级页表只需要给实际使用的的那些虚拟地址内存的请求分配内存

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

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

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

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

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

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

• 先进先出置换算法（FIFO）

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

• 最佳置换算法（OPT）

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

• 最近最久未使用（LRU）算法

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

• 时钟（Clock）置换算法

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

• Linux内核设计与实现

• B站 ----哈工大李志军老师讲解

关于操作系统的内容细节非常的多也将伴随伱的大学四年，考研多半会考找工作对你底层功力的考察也跑不掉，更重要的在了解其他技术的时候你会发现其实在操作系统基本原理Φ都有类似思想

另外说说工作上的事儿，最近刚工作两周咋们小组牛批了，八个人六个小姐姐相关故事后续慢慢道来，一定带劲儿

最后，如果你能在这篇文章中有点点收获请不要吝啬你的在看和点赞，这将给与小蓝更多写作的动力fighting。