InterviewGuide 操作系统面试高频题 41-60 详解：内存分布、页面置换算法与死锁处理全解析

教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载本文整理自《阿秀的学习笔记》InterviewGuide 开源仓库校招/社招八股文系列之操作系统 41-60 题覆盖内存布局与分配、虚拟内存与交换、磁盘调度、字符编码、原子操作、并发并行、页面置换算法以及死锁处理等高频考点。读完本文你将掌握一套可以直接用于面试作答的完整知识框架既能说清楚 Linux/Windows 下进程内存如何分布、栈与堆的大小由谁决定也能独立推导 OPT/FIFO/LRU/CLOCK 页面置换算法的手算过程还能用代码复现死锁并讲清死锁的检测、预防、避免与银行家算法。41、Windows 和 Linux 环境下内存分布情况无论是校招还是社招面试官几乎都会让候选人画出进程在虚拟内存中的布局。以 Linux 为例用户空间内存从低地址到高地址依次可以分为 7 种不同的内存段程序文件段包括二进制可执行代码即代码段text已初始化数据段包括静态常量、已初始化的全局变量与静态变量data未初始化数据段包括未初始化的静态变量bss堆段包括动态分配的内存malloc/new 所得从低地址开始向上增长文件映射段包括动态库、共享内存等映射区域从低地址开始向上增长具体位置与硬件和内核版本有关栈段包括局部变量和函数调用的上下文等。栈的大小是固定的一般是8 MB系统也提供了参数以便自定义大小。补充记忆要点栈向下增长、堆向上增长二者相向而行中间是文件映射段与空洞代码段、数据段位于整个地址空间的最低位。面试时除了背出 7 段名称最好再补充一句“内核空间位于最高地址用户空间不可直接访问”。42、一个由 C/C 编译的程序占用的内存分为哪几个部分C/C 程序的内存从逻辑上分为五大区域栈区stack地址向下增长由编译器自动分配释放存放函数的参数值、局部变量的值等操作方式类似于数据结构中的栈先进后出。堆区heap地址向上增长一般由程序员分配释放若程序员不释放程序结束时可能由 OS 回收。注意它与数据结构中的堆是两回事分配方式倒是类似于链表。全局区静态区static全局变量和静态变量存放在一起初始化的全局变量与静态变量在一块区域未初始化的全局变量与未初始化的静态变量在相邻的另一块区域程序结束后由系统释放。文字常量区常量字符串存放在这里程序结束后由系统释放。程序代码区text存放函数体的二进制代码。作答时可以顺带说明与第 41 题的对应关系第 41 题是“操作系统视角的地址空间分段”本题是“C/C 语言视角的内存分区”两者底层是同一套虚拟内存布局只是划分粒度不同。43、一般情况下在 Linux/Windows 平台下栈空间的大小Linux 环境下由操作系统决定一般是8 MB8192 KB可通过ulimit命令查看与修改Windows 环境下由编译器决定VC 6.0 默认是1 MB。LinuxLinux 下栈的大小不是由编译器决定而是由操作系统环境决定默认是8192 KB8M。而在 Windows 平台下栈的大小被记录在可执行文件中由编译器设置。也就是说Windows 下可以由编译器决定栈大小而 Linux 下是由系统环境变量控制栈大小的。在 Linux 下通过如下命令可查看和设置栈的大小$ ulimit -a # 显示当前栈的大小 ulimit为系统命令非编译器命令 $ ulimit -s 32768 # 设置当前栈的大小为32M说明ulimit是 shell 内置的系统命令不是编译器命令ulimit -s后面的数字单位是 KBulimit -s 32768即把栈上限临时设置为 32 MB。WindowsWindows 下程序栈空间的大小由编译器决定VC 6.0 默认的栈空间是1 MB。VC 6.0 中修改堆栈大小的方法选择 Project-Setting选择 Link选择 Category 中的 Output在 Stack allocations 中的 Reserve: 中输入栈的大小感谢网友勘误原仓库 issue #122021.09.03 已改正早期版本曾误写为编译器决定栈大小实为 Linux 下由系统环境控制、Windows 下由编译器决定。44、程序从堆中动态分配内存时虚拟内存上怎么操作的页表是一个存放在物理内存中的数据结构它记录了虚拟页与物理页的映射关系。在进行动态内存分配时例如malloc()函数或其他高级语言中的new关键字操作系统会在硬盘中创建或申请一段虚拟内存空间并更新到页表——分配一个页表条目PTE使该 PTE 指向硬盘上这个新创建的虚拟页通过 PTE 建立虚拟页和物理页的映射关系。理解本题的关键是malloc/new在虚拟内存层面“立即成功”真正的物理内存通常是在程序首次访问该页时由缺页异常触发按需调页demand paging才真正分配。因此面试时可以补充一句动态内存分配首先是虚拟内存的映射关系建立物理页的分配往往延迟到首次访问时发生。45、常见的几种磁盘调度算法读写一个磁盘块的时间的影响因素有旋转时间主轴转动盘面使磁头移动到适当的扇区上寻道时间制动手臂移动使磁头移动到适当的磁道上实际的数据传输时间。其中寻道时间最长因此磁盘调度的主要目标是使磁盘的平均寻道时间最短。1. 先来先服务FCFS按照磁盘请求的顺序进行调度。优点是公平和简单缺点也很明显因为未对寻道做任何优化使平均寻道时间可能较长。2. 最短寻道时间优先SSTF优先调度与当前磁头所在磁道距离最近的磁道。虽然平均寻道时间比较低但是不够公平——如果新到达的磁道请求总是比一个在等待的磁道请求近那么等待的请求会一直等待下去也就是出现饥饿现象两端的磁道请求更容易出现饥饿。3. 电梯扫描算法SCAN电梯算法和电梯的运行过程类似总是保持一个方向运行直到该方向没有请求为止然后改变运行方向总是按一个方向来进行磁盘调度直到该方向上没有未完成的磁盘请求然后改变方向。因为考虑了移动方向因此所有的磁盘请求都会被满足解决了 SSTF 的饥饿问题。延伸记忆SCAN 之后还有循环扫描C-SCAN与 LOOK/C-LOOK 等变体面试常以“电梯算法”为起点追问其优缺点。46、交换空间与虚拟内存的关系交换空间Linux 中的**交换空间Swap space在物理内存RAM**被充满时被使用。如果系统需要更多的内存资源而物理内存已经充满内存中不活跃的页就会被移到交换空间去。虽然交换空间可以为带有少量内存的机器提供帮助但是这种方法不应被当作对内存的取代——交换空间位于硬盘驱动器上它比进入物理内存要慢。交换空间可以是一个专用的交换分区推荐的方法、交换文件或两者的组合。交换空间的总大小应该取“计算机内存的两倍”和“32 MB”这两个值中较大的一个但不能超过2048 MB2 GB。虚拟内存虚拟内存是文件数据交叉链接的活动文件即 Windows 目录下的一个WIN386.SWP文件这个文件会不断地扩大和自动缩小。就速度而言CPU 的 L1 和 L2 缓存速度最快内存次之硬盘再次之。虚拟内存使用的是硬盘空间为什么我们要用速度最慢的硬盘来做虚拟内存呢因为电脑中所有运行的程序都需要经过内存来执行如果执行的程序很大或很多就会导致内存消耗殆尽文中以 256M/512M 内存为例而硬盘空间动辄几十 G 上百 G。为解决这个问题Windows 中运用了虚拟内存技术即拿出一部分硬盘空间来充当内存使用。47、抖动你知道是什么吗它也叫颠簸现象刚刚换出的页面马上又要换入内存刚刚换入的页面马上又要换出外存这种频繁的页面调度行为称为抖动或颠簸thrashing。产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数分配给进程的物理块不够。为进程分配的物理块太少会使进程发生抖动现象为进程分配的物理块太多又会降低系统整体的并发度、降低某些资源的利用率。为了研究应该为每个进程分配多少个物理块Denning 提出了**进程工作集working set**的概念——工作集即进程在一段时间内频繁访问的页面集合若分配给进程的物理块数小于其工作集大小就会持续缺页从而引发抖动。48、从堆和栈上建立对象哪个快考察堆和栈的分配效率比较从两方面来考虑1、分配和释放堆在分配和释放时都要调用函数malloc/free比如分配时会到堆空间去寻找足够大小的空间因为多次分配释放后会造成内存碎片这些都会花费一定的时间具体可以看看 malloc 和 free 的源码函数做了很多额外的工作而栈却不需要这些——栈的分配只是移动栈指针。2、访问时间访问堆的一个具体单元需要两次访问内存——第一次取得指针第二次才是真正的数据而栈只需访问一次。另外堆的内容被操作系统交换到外存的概率比栈大栈一般是不会被交换出去的。结论栈上创建对象更快这也是为什么局部变量、函数参数都倾向于放在栈上。49、常见内存分配方式有哪些1从静态存储区域分配内存在程序编译的时候就已经分配好这块内存在程序的整个运行期间都存在例如全局变量、static 变量。2在栈上创建在执行函数时函数内局部变量的存储单元都可以在栈上创建函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中效率很高但是分配的内存容量有限。3从堆上分配动态内存分配程序在运行的时候用malloc或new申请任意多少的内存程序员自己负责在何时用free或delete释放内存。动态内存的生存期由我们决定使用非常灵活但问题也最多。50、常见内存分配内存错误1内存分配未成功却使用了它编程新手常犯这种错误因为他们没有意识到内存分配会不成功。常用解决办法是在使用内存之前检查指针是否为 NULL如果指针 p 是函数的参数在函数的入口处用assert(p ! NULL)进行检查如果是用malloc或new申请内存应该用if(p NULL)或if(p ! NULL)做防错处理。2内存分配虽然成功但是尚未初始化就引用它犯这种错误主要有两个起因——一是没有初始化的观念二是误以为内存的缺省初值全为零导致引用初值错误例如数组。内存的缺省初值究竟是什么并没有统一的标准尽管有些时候为零值宁可信其无不可信其有。所以无论用何种方式创建数组都别忘了赋初值即便是赋零值也不可省略。3内存分配成功并且已经初始化但操作越过了内存的边界例如在使用数组时经常发生下标“多 1”或者“少 1”的操作特别是在 for 循环语句中循环次数很容易搞错导致数组操作越界。4忘记了释放内存造成内存泄露含有这种错误的函数每被调用一次就丢失一块内存刚开始时系统内存充足看不出错误终有一次程序突然挂掉系统提示“内存耗尽”。动态内存的申请与释放必须配对程序中malloc与free的使用次数一定要相同否则肯定有错误new/delete同理。5释放了内存却继续使用它常见于以下三种情况程序中的对象调用关系过于复杂难以搞清楚某个对象究竟是否已经释放了内存此时应重新设计数据结构从根本上解决对象管理的混乱局面函数的 return 语句写错了注意不要返回指向“栈内存”的“指针”或者“引用”因为该内存在函数体结束时被自动销毁使用free或delete释放了内存后没有将指针设置为 NULL导致产生“空悬指针野指针”。51、内存交换中被换出的进程保存在哪里保存在磁盘中也就是外存中。具有对换功能的操作系统中通常把磁盘空间分为文件区和对换区两部分文件区主要用于存放文件主要追求存储空间的利用率因此对文件区空间的管理采用离散分配方式对换区空间只占磁盘空间的小部分被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度因此对换区空间的管理主要追求换入换出速度通常对换区采用连续分配方式学过文件管理章节后即可理解。总之对换区的 I/O 速度比文件区的更快。52、在发生内存交换时有些进程是被优先考虑的你可以说一说吗可优先换出阻塞进程可换出优先级低的进程为了防止优先级低的进程在被调入内存后很快又被换出有的系统还会考虑进程在内存的驻留时间……注意PCB 会常驻内存不会被换出外存。这一点经常作为追问点出现。53、ASCII、Unicode 和 UTF-8 编码的区别ASCIIASCII 只有 127 个字符表示英文字母的大小写、数字和一些符号。但其他语言用 ASCII 编码表示字节不够——例如常用中文需要两个字节且不能和 ASCII 冲突中国定制了 GB2312 编码格式其他国家的语言也各有属于自己的编码格式。Unicode由于每个国家的语言都有属于自己的编码格式在多语言编辑文本中会出现乱码Unicode 应运而生——它将各种语言统一到一套编码格式中。通常两个字节表示一个字符而 ASCII 是一个字节表示一个字符因此如果文本是全英文的用 Unicode 编码比 ASCII 编码需要多一倍的存储空间在存储和传输上十分不划算。UTF-8为解决上述问题出现了把 Unicode 编码转化为“可变长编码”的 UTF-8 编码。UTF-8 将 Unicode 字符按数字大小编码为1-6 个字节英文字母被编码成一个字节常用汉字被编码成三个字节。如果文本是纯英文的用 UTF-8 就会非常节省空间并且ASCII 码也是 UTF-8 的一部分向后兼容。三者之间的联系现代计算机系统通用的字符编码工作方式可以总结为在计算机内存中统一使用 Unicode 编码当需要保存到硬盘或者需要传输的时候就转换为 UTF-8 编码。用记事本编辑的时候从文件读取的 UTF-8 字符被转换为 Unicode 字符到内存里编辑完成后保存的时候再把 Unicode 转换为 UTF-8 保存到文件。浏览网页的时候服务器会把动态生成的 Unicode 内容转换为 UTF-8 再传输到浏览器54、原子操作是如何实现的处理器使用基于对缓存加锁或总线加锁的方式来实现多处理器之间的原子操作。首先处理器会自动保证基本的内存操作的原子性处理器保证从系统内存中读取或者写入一个字节是原子的即当一个处理器读取一个字节时其他处理器不能访问这个字节的内存地址。Pentium 6 和最新的处理器能自动保证单处理器对同一个缓存行里进行的 16/32/64 位操作是原子的但复杂的内存操作处理器不能自动保证其原子性比如跨总线宽度、跨多个缓存行和跨页表的访问。此时处理器提供总线锁定和缓存锁定两个机制来保证复杂内存操作的原子性。1使用总线锁保证原子性如果多个处理器同时对共享变量进行读改写操作i就是经典的读改写操作那么共享变量会被多个处理器同时操作读改写操作就不是原子的操作完之后共享变量的值会和期望的不一致。举个例子如果i1我们进行两次i操作期望的结果是 3但有可能结果是 2CPU1 CPU2 i1 i1 i1 i1 i2 i2原因可能是多个处理器同时从各自的缓存中读取变量 i分别进行加 1 操作然后分别写入系统内存中。想要保证读改写共享变量的操作是原子的就必须保证 CPU1 读改写共享变量的时候CPU2 不能操作缓存了该共享变量内存地址的缓存。处理器使用总线锁来解决这个问题所谓总线锁就是使用处理器提供的一个LOCK#信号当一个处理器在总线上输出此信号时其他处理器的请求将被阻塞住那么该处理器可以独占共享内存。2使用缓存锁保证原子性在同一时刻我们只需保证对某个内存地址的操作是原子性即可但总线锁定把CPU 和内存之间的通信锁住了这使得锁定期间其他处理器不能操作其他内存地址的数据所以总线锁定的开销比较大。目前处理器在某些场合下使用缓存锁定代替总线锁定来进行优化。频繁使用的内存会缓存在处理器的 L1、L2 和 L3 高速缓存里那么原子操作就可以直接在处理器内部缓存中进行并不需要声明总线锁。在 Pentium 6 和目前的处理器中可以使用“缓存锁定”的方式来实现复杂的原子性所谓缓存锁定是指内存区域如果被缓存在处理器的缓存行中并且在 Lock 操作期间被锁定那么当它执行锁操作回写到内存时处理器不在总线上声言LOCK#信号而是修改内部的内存地址并允许它的缓存一致性机制来保证操作的原子性。因为缓存一致性机制会阻止同时修改由两个以上处理器缓存的内存区域数据当其他处理器回写已被锁定的缓存行的数据时会使缓存行无效。如上例所示当 CPU1 修改缓存行中的 i 时使用了缓存锁定那么 CPU2 就不能使用同时缓存 i 的缓存行。但是有两种情况下处理器不会使用缓存锁定当操作的数据不能被缓存在处理器内部或操作的数据跨多个缓存行cache line时处理器会调用总线锁定有些处理器不支持缓存锁定。对于 Intel 486 和 Pentium 处理器就算锁定的内存区域在处理器的缓存行中也会调用总线锁定。55、内存交换你知道有哪些需要注意的关键点吗交换需要备份存储通常是快速磁盘它必须足够大并且提供对这些内存映像的直接访问为了有效使用 CPU需要每个进程的执行时间比交换时间长影响交换时间的主要是转移时间转移时间与所交换的内存空间大小成正比如果换出进程要确保该进程的内存空间大小合适原文表述为“确保该进程的内存空间成正比”交换空间通常作为磁盘的一整块且独立于文件系统因此使用就可能很快交换通常在有许多进程运行且内存空间吃紧时开始启动而系统负荷降低就暂停普通交换使用不多但交换策略的某些变种在许多系统中如 UNIX 系统仍然发挥作用。56、系统并发和并行分得清吗并发是指宏观上在一段时间内能同时运行多个程序而并行则指同一时刻能运行多个指令。并行需要硬件支持如多流水线、多核处理器或者分布式计算系统。操作系统通过引入进程和线程使得程序能够并发运行。一句话总结并发是“看起来同时”单核通过时间片轮转也能实现并行是“真的同时”需要多核/多流水线硬件支撑。57、可能是最全的页面置换算法总结1、最佳置换算法OPT最佳置换算法OPTOptimal每次选择淘汰的页面将是以后永不使用或者在最长时间内不再被访问的页面这样可以保证最低的缺页率。最佳置换算法可以保证最低的缺页率但实际上只有在进程执行的过程中才能知道接下来会访问到的是哪个页面操作系统无法提前预判页面访问序列因此最佳置换算法是无法实现的——它只能作为衡量其他算法优劣的“理论标杆”。2、先进先出置换算法FIFO先进先出置换算法FIFO每次选择淘汰的页面是最早进入内存的页面。实现方法把调入内存的页面根据调入的先后顺序排成一个队列需要换出页面时选择队头页面队列的最大长度取决于系统为进程分配了多少个内存块。Belady 异常当为进程分配的物理块数增大时缺页次数不减反增的异常现象。只有 FIFO 算法会产生 Belady 异常而 LRU 和 OPT 算法永远不会出现 Belady 异常。另外FIFO 算法虽然实现简单但是该算法与进程实际运行时的规律不适应——先进入的页面也有可能最经常被访问较早调入的页往往是经常被访问的页这些页在 FIFO 算法下被反复调入和调出因此算法性能较差并且有 Belady 现象。3、最近最久未使用置换算法LRU最近最久未使用置换算法LRULeast Recently Used每次淘汰的页面是最近最久未使用的页面。实现方法赋予每个页面对应的页表项中用访问字段记录该页面自上次被访问以来所经历的时间 t该算法的实现需要专门的硬件支持虽然算法性能好但是实现困难、开销大。当需要淘汰一个页面时选择现有页面中 t 值最大的即最近最久未使用的页面。LRU 性能较好但需要寄存器和栈的硬件支持。LRU 是堆栈类算法理论上可以证明堆栈类算法不可能出现 Belady 异常。手算技巧在手动做题时若需要淘汰页面可以逆向检查此时在内存中的几个页面号在逆向扫描过程中最后一个出现的页号就是要淘汰的页面。4、时钟置换算法CLOCK最佳置换算法性能最好但无法实现先进先出置换算法实现简单但算法性能差最近最久未使用置换算法性能好、最接近 OPT 算法性能但实现需要专门的硬件支持、算法开销大。所以操作系统的设计者尝试了很多算法试图用比较小的开销接近 LRU 的性能这类算法都是 CLOCK 算法的变体——因为算法要循环扫描缓冲区、像时钟一样转动所以叫 CLOCK 算法。时钟置换算法是一种性能和开销较均衡的算法又称 CLOCK 算法或最近未用算法NRUNot Recently Used。简单 CLOCK 算法的实现方法为每个页面设置一个访问位再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时其访问位置为 1。当需要淘汰一个页面时只需检查页的访问位如果是 0就选择该页换出如果是 1则将它置为 0、暂不换出继续检查下一个页面。若第一轮扫描中所有页面都是 1则将这些页面的访问位依次置为 0 后再进行第二轮扫描第二轮扫描中一定会有访问位为 0 的页面因此简单的 CLOCK 算法选择一个淘汰页面最多会经过两轮扫描。5、改进型的时钟置换算法简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上如果被淘汰的页面没有被修改过就不需要执行 I/O 操作写回外存只有被淘汰的页面被修改过时才需要写回外存。因此除了考虑页面最近有没有被访问过之外操作系统还应考虑页面有没有被修改过在其他条件都相同时应优先淘汰没有修改过的页面避免 I/O 操作。这就是改进型时钟置换算法的思想。修改位 0表示页面没有被修改过修改位 1表示页面被修改过。为方便讨论用访问位修改位的形式表示各页面状态如 (1, 1) 表示一个页面近期被访问过且被修改过。改进型的 CLOCK 算法需要综合考虑某一内存页面的访问位和修改位来判断是否置换该页面。在实际编写算法过程中同样可以用一个等长的整型数组来标识每个内存块的修改状态。访问位 A 和修改位 M 可以组成以下四种类型的页面。算法规则将所有可能被置换的页面排成一个循环队列。第一轮从当前位置开始扫描到第一个 (A0, M0) 的帧用于替换。表示该页面最近既未被访问、又未被修改是最佳淘汰页。本轮扫描不修改任何标志位。第二轮若第一轮扫描失败则重新扫描查找第一个 (A0, M1) 的帧用于替换。本轮将所有扫描过的帧访问位设为 0。表示该页面最近未被访问但已被修改并不是很好的淘汰页。第三轮若第二轮扫描失败则重新扫描查找第一个 (A0, M0) 的帧用于替换。本轮扫描不修改任何标志位。表示该页面最近已被访问但未被修改该页有可能再被访问。第四轮若第三轮扫描失败则重新扫描查找第一个 (A1, M1) 的帧用于替换。表示该页最近已被访问且被修改该页可能再被访问。由于第二轮已将所有帧的访问位设为 0因此经过第三轮、第四轮扫描一定会有一个帧被选中所以改进型 CLOCK 置换算法选择一个淘汰页面最多会进行四轮扫描。按优先级归纳即为优先级页面状态A, M含义第一(0, 0)最近没访问且没修改第二(0, 1)最近没访问但修改过第三(1, 0)最近访问过但没修改第四(1, 1)最近访问过且修改过6、总结算法算法规则优缺点OPT优先淘汰最长时间内不会被访问的页面缺页率最小性能最好但无法实现FIFO优先淘汰最先进入内存的页面实现简单但性能很差可能出现 Belady 异常LRU优先淘汰最近最久没访问的页面性能很好但需要硬件支持算法开销大CLOCK (NRU)循环扫描各页面。第一轮淘汰访问位0 的并将扫描过的页面访问位改为 1。若第一轮没选中则进行第二轮扫描。实现简单算法开销小但未考虑页面是否被修改过改进型 CLOCK改进型 NRU若用访问位修改位的形式表述则第一轮淘汰 (0,0)第二轮淘汰 (0,1) 并将扫描过的页面访问位都置为 0第三轮淘汰 (1,0)第四轮淘汰 (1,1)算法开销较小性能也不错58、共享是什么共享是指系统中的资源可以被多个并发进程共同使用。有两种共享方式互斥共享和同时共享。互斥共享的资源称为临界资源例如打印机等在同一时刻只允许一个进程访问需要用同步机制来实现互斥访问。59、死锁相关问题大总结超全死锁是指两个多个线程相互等待对方数据的过程死锁的产生会导致程序卡死不解锁程序将永远无法进行下去。1、死锁产生原因举个例子两个线程 A 和 B两个数据 1 和 2。线程 A 在执行过程中首先对资源 1 加锁然后再去给资源 2 加锁但是由于线程的切换导致线程 A 没能给资源 2 加锁。线程切换到 B 后线程 B 先对资源 2 加锁然后再去给资源 1 加锁由于资源 1 已经被线程 A 加锁因此线程 B 无法加锁成功当线程切换回 A 时A 也无法成功对资源 2 加锁由此就造成了线程 A、B 双方相互对一个已加锁资源的等待死锁产生。理论上认为死锁产生有以下四个必要条件缺一不可互斥条件进程对所需求的资源具有排他性若有其他进程请求该资源请求进程只能等待。不剥夺条件进程在所获得的资源未释放前不能被其他进程强行夺走只能自己释放。请求和保持条件进程当前所拥有的资源在进程请求其他新资源时由该进程继续占有。循环等待条件存在一种进程资源循环等待链链中每个进程已获得的资源同时被链中下一个进程所请求。2、死锁演示通过代码的形式进行演示需要两个线程和两个互斥量#include iostream #include vector #include list #include thread #include mutex //引入互斥量头文件 using namespace std; class A { public: //插入消息模拟消息不断产生 void insertMsg() { for (int i 0; i 100; i) { cout 插入一条消息: i endl; my_mutex1.lock(); //语句1 my_mutex2.lock(); //语句2 Msg.push_back(i); my_mutex2.unlock(); my_mutex1.unlock(); } } //读取消息 void readMsg() { int MsgCom; for (int i 0; i 100; i) { MsgCom MsgLULProc(i); if (MsgLULProc(MsgCom)) { //读出消息了 cout 消息已读出 MsgCom endl; } else { //消息暂时为空 cout 消息为空 endl; } } } //加解锁代码 bool MsgLULProc(int command) { int curMsg; my_mutex2.lock(); //语句3 my_mutex1.lock(); //语句4 if (!Msg.empty()) { //读取消息读完删除 command Msg.front(); Msg.pop_front(); my_mutex1.unlock(); my_mutex2.unlock(); return true; } my_mutex1.unlock(); my_mutex2.unlock(); return false; } private: std::listint Msg; //消息变量 std::mutex my_mutex1; //互斥量对象1 std::mutex my_mutex2; //互斥量对象2 }; int main() { A a; //创建一个插入消息线程 std::thread insertTd(A::insertMsg, a); //这里要传入引用保证是同一个对象 //创建一个读取消息线程 std::thread readTd(A::readMsg, a); //这里要传入引用保证是同一个对象 insertTd.join(); readTd.join(); return 0; }语句 1 和语句 2 表示线程 A 先锁资源 1、再锁资源 2语句 3 和语句 4 表示线程 B 先锁资源 2、再锁资源 1具备死锁产生的条件。3、死锁的解决方案保证上锁的顺序一致即所有线程都按相同的次序获取锁破坏循环等待条件。4、死锁必要条件互斥条件进程对所需求的资源具有排他性若有其他进程请求该资源请求进程只能等待。不剥夺条件进程在所获得的资源未释放前不能被其他进程强行夺走只能自己释放。请求和保持条件进程当前所拥有的资源在进程请求其他新资源时由该进程继续占有。循环等待条件存在一种进程资源循环等待链链中每个进程已获得的资源同时被链中下一个进程所请求。5、处理方法主要有以下四种方法鸵鸟策略死锁检测与死锁恢复死锁预防死锁避免鸵鸟策略把头埋在沙子里假装根本没发生问题。因为解决死锁问题的代价很高因此鸵鸟策略这种不采取任何措施的方案会获得更高的性能。当发生死锁时不会对用户造成多大影响或发生死锁的概率很低可以采用鸵鸟策略。大多数操作系统包括 Unix、Linux 和 Windows处理死锁问题的办法仅仅是忽略它。死锁检测与死锁恢复不试图阻止死锁而是当检测到死锁发生时采取措施进行恢复。1、每种类型一个资源的死锁检测上图为资源分配图其中方框表示资源圆圈表示进程。资源指向进程表示该资源已经分配给该进程进程指向资源表示进程请求获取该资源。图 a 可以抽取出环如图 b它满足了环路等待条件因此会发生死锁。每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现的从一个节点出发进行深度优先搜索对访问过的节点进行标记如果访问了已经标记的节点就表示有向图存在环也就是检测到死锁的发生。2、每种类型多个资源的死锁检测上图中有三个进程、四个资源每个数据代表的含义如下E 向量资源总量A 向量资源剩余量C 矩阵每个进程所拥有的资源数量每一行都代表一个进程拥有资源的数量R 矩阵每个进程请求的资源数量进程 P₁ 和 P₂ 所请求的资源都得不到满足只有进程 P₃ 可以满足。让 P₃ 执行之后释放 P₃ 拥有的资源此时 A (2 2 2 0)P₂ 可以执行执行后释放 P₂ 拥有的资源A (4 2 2 1)P₁ 也可以执行。所有进程都可以顺利执行没有死锁。算法总结如下每个进程最开始时都不被标记执行过程有可能被标记当算法结束时任何没有被标记的进程都是死锁进程。寻找一个没有标记的进程 Pᵢ它所请求的资源小于等于 A如果找到了这样一个进程那么将 C 矩阵的第 i 行向量加到 A 中标记该进程并转回 1如果没有这样一个进程算法终止。6、死锁恢复利用抢占恢复利用回滚恢复通过杀死进程恢复7、死锁预防在程序运行之前预防发生死锁。破坏互斥条件例如假脱机打印机技术允许若干个进程同时输出唯一真正请求物理打印机的进程是打印机守护进程。破坏请求和保持条件一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。破坏不剥夺条件允许抢占资源。破坏循环请求等待给资源统一编号进程只能按编号顺序来请求资源。8、死锁避免在程序运行时避免发生死锁。1、安全状态图 a 的第二列 Has 表示已拥有的资源数第三列 Max 表示总共需要的资源数Free 表示还有可以使用的资源数。从图 a 开始出发先让 B 拥有所需的所有资源图 b运行结束后释放 B此时 Free 变为 5图 c接着以同样的方式运行 C 和 A使得所有进程都能成功运行因此可以称图 a 所示的状态是安全的。定义如果没有死锁发生并且即使所有进程突然请求对资源的最大需求也仍然存在某种调度次序能够使得每一个进程运行完毕则称该状态是安全的。安全状态的检测与死锁的检测类似因为安全状态必须要求不能发生死锁。下面的银行家算法与死锁检测算法非常类似可以结合着做参考对比。2、单个资源的银行家算法一个小城镇的银行家他向一群客户分别承诺了一定的贷款额度。算法要做的是判断对请求的满足是否会进入不安全状态如果是就拒绝请求否则予以分配。上图 c 为不安全状态因此算法会拒绝之前的请求从而避免进入图 c 中的状态。3、多个资源的银行家算法上图中有五个进程、四个资源。左边的图表示已经分配的资源右边的图表示还需要分配的资源最右边的 E、P 以及 A 分别表示总资源、已分配资源以及可用资源。注意这三个为向量而不是具体数值例如 A(1 0 2 0) 表示 4 个资源分别还剩下 1/0/2/0。4、检查一个状态是否安全的算法如下查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行那么系统将会发生死锁状态是不安全的假若找到这样一行将该进程标记为终止并将其已分配资源加到 A 中重复以上两步直到所有进程都标记为终止则状态是安全的。如果一个状态不是安全的需要拒绝进入这个状态。60、为什么分段式存储管理有外部碎片而无内部碎片为什么固定分区分配有内部碎片而不会有外部碎片分段式分配是按需分配而固定式分配是固定分配的方式。分段式存储管理按进程实际需要分配连续的内存空间分配大小刚好满足需求因此不会产生内部碎片但随着进程的换入换出内存中会出现许多难以利用的小空闲区即外部碎片。固定分区分配把内存预先划分为固定大小的分区进程被装入不小于自身大小的分区中分区内未被使用的剩余空间即为内部碎片由于分区边界固定、每次分配都发生在整块分区上因此不会产生外部碎片。本题与第 61-80 题中的“内部碎片与外部碎片”详细推演含 100M 内存、10M 分区的具体算例是同一知识点的不同侧面可对照阅读。延伸阅读本文为 InterviewGuide《阿秀的学习笔记》校招八股文操作系统 41-60 题部分建议结合仓库内同一系列文档系统复习操作系统面试题 01-20进程线程与协程、调度算法等操作系统面试题 21-40死锁、并发与互斥等操作系统面试题 61-80碎片整理、多进程多线程、虚拟内存等操作系统学习路线基础学科篇赞分享教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载相关推荐InterviewGuide 操作系统面试精讲4160 题内存布局、磁盘调度、页面置换与死锁全解InterviewGuide 操作系统面试精讲4160 题内存布局、磁盘调度、页面置换与死锁全解 本篇基于 InterviewGuide 仓库中阿秀整理文档教程知识库InterviewGuide 操作系统高频面试题精讲01–20进程线程模型、调度算法与内存管理全解析InterviewGuide 操作系统高频面试题精讲01–20进程线程模型、调度算法与内存管理全解析 本文基于《InterviewGuide》开源仓库中的教程CS-Notes 技术面试必备操作系统内存管理完全指南虚拟内存、分页地址映射与页面置换算法CS Notes 技术面试必备操作系统内存管理完全指南虚拟内存、分页地址映射与页面置换算法 本指南以 CS Notes 仓库 计算机操作系统 内存管理 h知识库文档教程上一篇Flexbox Froggy用户测试A/B测试不同界面设计方案下一篇掌握QMUI_iOS版本管理从规范到发布的完整指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考