操作系统导论

🍮 第一章 关于本书的对话

1. OS 三个重要概念

  • 虚拟化 virtualization
  • 并发 concurrency
  • 持久化 persistence

🏀 第二章 操作系统介绍

1. 程序运行时会发什么

  • 处理器从内存中获取 (fetch)一条指令,对其进行节码(decode),然后执行(execute)它。完成这条指令后,处理器继续执行下一条指令,依此类推,直到程序最终完成。

2. 什么是操作系统 OS

  • 运行同时运行多个程序,允许程序共享内存,让程序能够与设备进行交互,负责确保程序易使用又正确运行

3. OS 如何将资源虚拟化

  • OS 通过哪些机制和策略来实现虚拟化?
  • OS 如何有效的实现虚拟化?
  • OS 虚拟化需要哪些硬件支持?

4. 虚拟化 CPU

  • 将单个 CPU 转换为看似无限数量的CPU,从而让许多程序看似同时运行

5. 虚拟化内存

  • 每个进程访问自己的私有虚拟地址,OS 以某种方式映射到机器的物理内存上

🐡 第四章 抽象:进程

1. 什么是进程

  • 计算机中的程序关于某数据集合上的一次运行活动,是系统进行资源分配和调度的基本单位,是操作系统结构的基础

2. 虚拟化CPU

  • 共享资源最基本技术

    • 时分共享

      • 运行资源有一个实体使用一小段时间,然后后另一个实体使用一小段时间,如此下去
    • 空分共享

      • 资源在空间上被划分给希望使用它的人

3. 进程的生命周期

  • 创建

    • 将代码和所有静态数据加载到内存中,加载到进程的地址空间。
  • 销毁

  • 等待
  • 其他控制
  • 状态

    • 运行
    • 就绪
    • 阻塞

4. 上下文切换

  • 寄存器上下文将保存其寄存器的内存。当一个进程停止时,它的寄存器将被存在到这个内存位置,通过恢复这些寄存器,操作系统就可以恢复改进程。

5. 僵尸进程

  • 进程处于已退出状态,但尚未清理最终状态。

🎃 第六章 机制:受限直接执行

1. 构建虚拟化机制存在的一些挑战

  • 性能

    • 如何在不增加系统开销的情况下实现虚拟化?
  • 控制权

    • 如何有限运行程序,同时保存对CPU的控制?

2. 受限直接执行

  • 概念

    • 只需直接在CPU上运行程序
  • 步骤

    • 在进程列表为其创建一个进程条目
    • 分配一些内存
    • 将程序代码加载到内存中
    • 找到入口点 main 或者类似其他的函数,跳转到那里,并运行起来

3. 受限直接执行协议 (limited direct execution )LDE

  • 阶段一

    • 内核初始化陷阱表,并且CPU记住位置,以供随后使用
  • 阶段二

    • 从陷阱返回值指令开始执行进程之前,内核设置了一些内容(分配内存),完成任务后退出内核。

4. 受限直接执行存在的问题

  • 问题一:如果只运行一个程序,如何保障它不做我们不希望做的事情?
  • 问题二:如果是运行一个进程,如何让其停下来,并切换至另一个进程,从而实现虚拟化 CPU 所需的时分共享

5. 问题一

  • 引入处理器模式

    • 用户模式

      • 不能完全访问硬件资源
    • 内核模式

      • 可以访问机器的全部资源
  • 提供陷入(trap)内核和从陷阱返回(renturn-from-trap)

    • trap

      • 跳入内核,并将特权级别提升至内核模式
    • return-from-trap

      • 跳出内核,将特权级别降会用户模式
  • 补充一下

    • 为何这两个指令看起来像过程调用,就像你要用就用,不要用就不用。其实是因为你在调用系统库的时候,你不用去写这两个指令,因为有人帮你写在了操作系统的库里面了。

6. 问题二

  • 操作系统重获 CPU 控制权

    • 协作方式,等待系统调用,在 CPU 运行时间太长,操作系统会直接抛弃掉
    • 执行非法操作,操作系统重获 CPU 控制权
    • 时钟中断(time interrupt)操作系统预先配置中断处理程序,当中断处理程序运行时,操作系统重获 CPU 控制权
  • (保存和恢复上下文)上下文切换

    • 发生时钟中断(time interrput),用户寄存器由硬件隐式保存或者恢复
    • 操作系统从 A 切到 B 进程,内核寄存器会被操作系统保存,存在该进程的进程结构内存中

🍄 第七章 进程调用:介绍

1. 如何开发调度策略

  • 什么是关键假设?
  • 哪些指标非常重要?
  • 哪些方法已经在早期的操作系统使用?

2. 一些假设

  • 每个工作运行时间相同
  • 所有工作同时达到
  • 一旦开始,每个工作保存运行直至完成
  • 所有工作只能用 CPU 完成
  • 所有工作只能用 IO 完成
  • 每个工作的时间都是已知的

3. 调度指标

  • 周转时间

    • T 周转 = T 完成 - T到达
  • 性能

  • 公平性
  • 响应时间

    • T响应 = T首次运行 - T 到达

4. 调度方法

  • 先进先出 (first in first out)FIFO / 先到先服务 (first come first served)FCFS

    • 谁先来谁先服务
  • 最短任务优先(shortest job first)SJF

    • 先运行最短任务,然后是次短的,依次类推
  • 最短完成时间优先 (shortest time-to-completion first)stcf

    • 抢占式最短任务优先,在剩下的任务中谁的剩余时间最短就执行谁
  • 轮转 (Round-Robin) RR

    • 在一个时间片内运行一个任务,然后切换运行队列的下一个任务
    • 缺点

      • 如果指标是以响应时间为主,则是一个优先的调度方法,以周转时间来看,总共时间加上了上下文切换时间

🐮 第八章 调度:多级反馈队列

1. 多级反馈队列(Multi-level Feedback Queue)MLFQ 需要解决的问题

  • 优化周转时间
  • 降低响应时间

2. MLFQ 基本规则

  • 有许多独立的队列 queue
  • 每个队列有不同优先级 priority level
  • 任何时刻,一个任务只能存在一个队列中
  • 总是优先执行优先度高的工作

3. 实际过程的规则

  • 如果 A 优先度大于 B

    • 运行A
  • 如果 A 优先度等于 B

    • 轮转运行
  • 如何改变优先级

    • 工作进入系统时,放在最高优先度,(队列最上层)
    • 工作用完整个时间片后,降低其优先度(移入下一个队列)
    • 如果工作在其时间片内主动释放CPU 优先度不变
  • 提高优先度

    • 经过一段时间 S,就将所有任务放进最高级别的队列(解决饥饿问题)

      • 存在如何配置好这个时间 S 的问题(巫毒常量问题)

        • 只有魔法才能打败魔法....(暂时无解,直接给管理人配置,适合自己才是最好的)
  • 计时方式

    • 一旦工作用完某一层的时间配额(无论中间放弃多少次 CPU),都会降低其优先度(解决欺骗调度程序问题)

4. 缺点

  • 饥饿问题

    • 如果太多交互的工作,可能导致优先级别低或者是长时间的工作得不到 CPU,这些工作任务无法完成
  • 欺骗调度程序问题

    • 一些开发者可能会重写软件,利用规则欺骗调度程序,从而独占整个 CPU
  • 巫毒常量问题

    • S 设置太高,长工作饥饿问题
    • S 设置太低,交互工作无法获取到合适的CPU 时间

🎳 第九章 调度:比例份额

1. 目的

  • 确保每个工作都能获取到一定比例的 CPU 时间,而不是优化周转时间和响应时间

2. 彩票数表示份额

  • 假设进程A、B,A拥有 1-75 数字的彩票,B拥有 76 - 100的彩票,通过随机(1-100)出的数字来决定这个时间片运行哪个进程
  • 优点

    • 轻量,几乎不需要记录任何状态
    • 决策快
  • 缺点

    • 次数越多越接近伪随机(只有自然界的随机才是真随机)
    • 彩票分配问题

3. 彩票货币

  • 拥有彩票货币的进程,可以自由兑换成全局彩票货币,然后举行抽奖,决定哪个工作运行

🚌 第十章 多处理器调度(高级)

1. CPU 缓存一致性问题

  • 当CPU 1 修改内存地址A,并更新 CPU 1 缓存为新值D,由于操作系统中断该程序的运行,交给其他CPU 重新读取地址A的数据,这时候其他CPU的缓存没有地址值,而去读取地址A,得到旧值 D
  • 解决方案

    • 通过监控内存访问,硬件可以保证获得正确的数据,并保证共享内存的唯一性

2. 应用层面的一致性

  • 使用互斥原语(比如锁)

3. 缓存亲和度

  • 当在某一个CPU运行过,会在该CPU的缓存维护许多状态,下次该进程在相同的CPU运行时,由于缓存中的数据而执行的更快

4. 单队列多处理器调度(Single Queue Multiprocessor Scheduling)SQMS

  • 问题

    • 缺乏可扩展性
    • 缓存亲和度
  • 缺点

    • 锁可能带来巨大的性能消耗

5. 多队列多处理器调度(Multi-Queue Multiprocessor Scheduling)MQMS

  • 解决

    • 解决了 SQMS 可扩展性问题
    • 天生具有良好的缓存亲和度
    • 工作的跨 CPU 迁移(解决CPU 负载不均问题)
  • 缺点

    • CPU 负载不均
    • 检查队列是否迁移配置问题(依然是巫毒常量问题,只有魔法才能打败魔法)

      • 如果太频繁

        • 带来较高的开销,可扩展性不好
      • 如果太低

        • CPU 负载不均

👽 第十三章 抽象:地址空间

1. 什么是地址空间

  • 出现的原因

    • 早期硬件设施非常昂贵,需要共享一些物理内存
  • 提供一个易用的物理地址抽,即虚拟内存空间

2. 地址空间内存分布

  • 程序代码 code

3. 目的

  • 建立一个可靠系统,实体与实体之间相互不影响,从而防止相互造成伤害

4. 虚拟内存 VM

  • 目标

    • 透明性 transparency

      • 程序不应该感知到内存被虚拟化事实,相反,程序的行为就好像它拥有自己的私有物理内存
    • 高效性 efficiency

      • 追求虚拟化尽可能高效,包括时间和空间上
    • 保护性 protection

      • 确保进程收到保护,不会受到其他进程的影响,操作系统本身也不会受到影响

😼 第十四章 插叙:内存操作API

1. 什么是内存泄漏 memory leak

  • 申请了内存,但是忘记释放内存,这是一个缓慢的过程,长时间的泄露内存从而导致内存不足。另外,由于忘记释放内存,就仍然拥有对某块内存的引用,那么垃圾收集器就不会释放它
  • // 说下个人理解 java 为例

    • 各种的 IO 操作,没有及时的关闭管道,就存在这种现象。比如 IO 连接没有关闭,连接池没有及时关闭等。

2. 什么是内存溢出 memory overflow

  • 没有分配足够的内存,而导致内存不足
  • // 说下个人理解 java 为例

    • 初始化分配 100M 的空间,然后new 一个超过 100M 的对象等。

🤔 第十五章 机制:地址转换

1. 意义

  • 它可以看成受限直接执行 LDE 的补充,利用地址转换,硬件对每次虚拟内存的访问进行处理转为实际存储的物理内存地址

2. 目的

  • 让每一个程序都以为自己拥有私有的物理内存(实际上是虚拟内存),存放自己的代码和数据

3. 关键问题

  • 如何提供应用程序所需的灵活性?
  • 如何保持控制应用程序可访问内存位置?从而确保应用程序的内存访问受到合理的限制
  • 如何高效的实现这一切?
  • 如何高效的实现内存虚拟化?

4. 动态(基于硬件)重定位

  • 目的

    • 确保地址空间放在任何位置上,同时又能够保证进程只能访问自己的地址空间
  • 硬件寄存器支持

    • 基址(base)寄存器

      • 记录起始地址
      • 该进程所有产生的内存引用,都会通过处理器转为物理地址:physical address = virtual address + base
    • 界限(limit)寄存器

      • 确保进程地址空间范围
      • 确保进程产生的所有地址,都在这个寄存器内,也就是这个界限内
  • 硬件 CPU 支持

    • 内存管理单元 MMU

      • 负责地址转换
  • 操作系统支持

    • 在进程创建时,操作系统必须采取行动,为进程空间找到可用内存空间
    • 在进程终止时,操作系统必须回收它所有的内存,给其他进程或者操作系统使用
    • 在上下文切换时,操作系统必须恢复和保存基址寄存器和界限寄存器
    • 操作系统必须提供异常处理程序,或者一些调用异常处理函数
  • 硬件支持:总结

    • 特权模式

      • 以防用户模式的进程执行特性操作
    • 基址/界限寄存器

      • 每个 CPU 需要一对寄存器来支持地址转换和界限检查
    • 能够转换虚拟地址并检查是否越界

      • 电路检查来完成转换和检查界限
    • 修改基址/界限寄存器的特权指令

      • 在让用户程序起来前,操作系统必须能够设置这些值
    • 注册异常处理程序的特权指令

      • 操作系统必须能告诉硬件,如果发生了异常,需要执行哪些代码
    • 能够触发异常

      • 如果进程试图使用特权指令或者越界内存,就必须要触发异常
  • 操作系统:总结

    • 内存管理

      • 需要为新进程分配内存,需要从终止进程回收内存,需要通过空闲列表(free list)管理内存
    • 基址/界限管理

      • 必须在上下文切换时正确设置基址/界限寄存器
    • 异常处理

      • 当异常发生时执行的代码,可能是终止犯错进程

5. 静态(基于软件)重定位

  • 加载程序(loader)的软件接收将要运行的可执行程序,将地址重写到物理内存的期望偏移位置
  • 缺点

    • 不提供访问保护
    • 一旦完成,很难将内存空间重定位到其他位置上
    • 错误地址,可能导致非法访问系统内存

😎 第十六章 分段

1. 简单的基址/界限寄存器

  • 缺点

    • 无法提供连续区域来防止完整的地址空间
    • 无法高效利用物理内存

2. 什么是分段机制(解决了简单的基址/界限寄存器存在的问题)

  • 给每个地址空间内的逻辑段,这个段只是在地址空间里的一个连续定长区域

3. 意义

  • 使得操作系统能够将不同的段放到不同的物理内存区域,从而避免虚拟地址空间未使用部分占用了物理内存

4. 如何知道需要引用哪个段

  • 在基址/界限寄存器的基础上新增一个寄存器,段寄存器

5. 段寄存器

  • 告诉操作系统需要引用哪个段,而进行段内偏移

6. 分段机制的改进

  • 新增保护位

    • 支持共享

7. 存在的问题

  • 操作系统在上下文切换的时候应该要做什么?

    • 各个段寄存器中的内存也必须保存和恢复
  • 怎么管理物理内存的空闲空间?或者稀疏空间怎么管理?

    • 紧凑物理内存,重新安排原有的段
    • 利用空闲列表管理算法,保留大的内存块用于分配

🗻 第十七章 空闲空间管理

1. 问题的诞生

  • 碎片化问题,导致物理内存许多未被使用的空闲空间,即物理内存空闲空间,因此需要对物理内存空闲空间进行管理

2. 关键问题

  • 如何满足自由的分配空闲空间请求?
  • 什么策略可以让碎片最小化?
  • 不同方法的时间和空间开销如何?

3. 分配程序通用机制(解决自由分配空间大小问题)

  • 分割和合并

    • 找到满足请求的空闲空间,将其分割,第一块返回给请求用户,第二块留在空闲空间
    • 释放空间的内存,如果附近有相邻的空闲空间块,则与之合并成一块更大的空闲空间
  • 追踪已分配空间大小

    • 添加魔数来提供完整的信息检查

      • 分配空间大小
      • 魔数(猜测这个应该是做唯一性检查)
  • 空闲空间变成空闲列表

4. 策略(优化碎片化问题)

  • 最优匹配

    • 原理

      • 选择最接近用户请求大小的空闲块,尽可能的节省空间
    • 缺点

      • 可能需要遍历完整个空闲空间,较高的性能代价
  • 最差匹配

    • 原理

      • 尝试找最大的空闲块,分割并满足用户请求的空间大小,剩余的块放回空闲列表
    • 缺点

      • 分割次数可能较多,产生过量的碎片
      • 和最优匹配一样需要遍历完,才知道,开销较大
  • 首次匹配

    • 原理

      • 找到第一个满足请求大小的空闲空间块
    • 缺点

      • 空闲列表开头可能会产生许多碎片化
    • 优点

      • 开销较小
  • 下次匹配

    • 原理

      • 从上次查找结束的空闲空间位置开始查询空闲空间块
    • 缺点

      • 较为复杂,可能需要维护更多的状态来记录
    • 优点

      • 性能和首次匹配差不多
  • 分离空闲列表

    • 原理

      • 单独一个列表,只管理一种或者几种大小相同的内存空间,其他大小的请求交给更通用的内存分配程序
    • 缺点

      • 复杂性较高,如何分配大小相同的空间块需要多少,如何配置,存在问题
    • 优点

      • 特定的内存空间分配和释放速度都很快
  • 伙伴系统

    • 原理

      • 空间被看成 2 N次幂大的空间,每次请求空闲空间都会被递归成两部分,一部分给用户,一部分归还空闲空间,直到满足请求大小形成的 2 的N 次幂大小空间
    • 缺点

      • 存在内部碎片化

🐝 第十八章 分页:介绍

1. 什么是分页

  • 在虚拟内存中,将空间分割成固定长度的分片

2. 关键问题

  • 如何通过页实现虚拟内存?
  • 基本技术是什么?
  • 良好的运行前提,如何尽可能的减少时间和空间开销?

3. 页表(解决虚拟内存问题)

  • 为地址空间的每个虚拟页面保存地址转换,从而让我们知道物理内存的位置(实现虚拟内存)

🐯 第十九章 分页:快速地址转换(TLB)

1. 关键问题

  • 如何加快虚拟地址转换?
  • 需要什么硬件支持?
  • 操作系统怎么支持?

2. 地址转换旁路缓冲存储器(translation lookaside buffer)TLB

  • 目的

    • 频繁发生在虚拟到物理地址转换的硬件缓存(使用缓存来加快虚拟地址转换)
  • 算法流程

    • 首先从虚拟地址提取页号(VPN),然后检查TLB 是否又该 VPN 的转换映射,如果有则命中 TLB 命中,该页映射成功,如果没有则硬件访问页表来找转换

🍣 第二十章 分页:较小的表

1. 关键问题

  • 如何让页表更小?(上面我们之前提过,TLB 是一种硬件缓存,缓存的话受限硬件,不可能无限大)
  • 关键思路时什么?
  • 有什么新的数据结构,可以代替列表?

2. 解决方案

  • 使用更大页

    • 使用更大的页(页指的是虚拟内存划分的块,而页表指的是虚拟页保存的地址转换,一种映射,大概就是字典和目录的关系),更大页,则页表就不需要保存更多的地址转换信息
    • 缺点

      • 大内存页会导致每页内的内存浪费,过多的内部碎片
  • 分页和分段混用

    • 由于页表是一种线性结构,采用分段的思想,设置一个基址、界限、限制等寄存器,来告诉这个段有多大,从缩小页表大小
    • 缺点

      • 大而稀疏的空间,可能导致大量页表被浪费
  • 多级页表

    • 将线性页转成类似树)的结构,页目录管理页表,同时页目录只将页表的第一页和最后一页标记有效,有效的页面就会驻留进内存,这样就不会包括全部,剩下交换到磁盘里,而节省页表大小
    • 缺点

      • 复杂度较高
      • 当 TLB 未命中,需要查两次(页目录、页表),消耗高

🎉 第二十一章 超越物理内存:机制

1. 关键问题

  • 如何提供一个透明的、巨大的虚拟地址空间的假象?

2. 为什么要提供一个巨大的地址空间

  • 方便和易用性,你不必担心数据结构是否有足够的空间,只需要根据需求分配内存

3. 交换空间

  • 目的

    • 在硬盘上开辟一部分空间用于物理页的移入和移出
  • 做法

    • 将页(即虚拟内存划分的块)中的页表设置存在位,标识是否存在物理内存还是硬盘。这样就可以把页存进硬盘中

4. 页错误

  • 什么是页错误

    • 访问不到物理内存的页,即访问不到虚拟内存
  • 产生的原因

    • TLB 未命中,(你也可以说成页未命中,虚拟地址找不到)
  • 补救措施

    • 预先留一些即将要交换入的新页位置
    • (内存不足)选择哪些页被交换或者替代

🐰 第二十二章 超越物理内存:策略

1. 问题的诞生

  • 由于存在内存不足的问题,迫使 OS 换出一些页,为常用页腾出空间。即确定要踢出哪一个页

2. 关键问题

  • 如何决定从内存中剔出哪一页?
  • 替换策略有什么?
  • 替换策略会遵循哪一通用原则?

3. 缓存管理

  • 本质还是虚拟内存页的缓存管理,即需要为这个虚拟内存页选择替换策略
  • 缓存指标

    • 计算平均内存访问时间 (Average Memory Access Time) AMAT (决定内存踢出哪一页的计算)

      • AMAT = (P hit T m)+(P miss T d)
      • P hit

        • 缓存中找到数据的概率(命中缓存的概率)
      • T m

        • 访问内存的成本
      • P miss

        • 缓存中找不到数据的概率(未命中缓存的概率)
      • T d

        • 访问磁盘的成本
    • 通过指标可以选择一些聪明的策略

4. 替换策略

  • 最优替换策略

    • 原理

      • 替换内存中在最远将来才会被访问到的页
    • 缺点

      • 未来的访问是无法知道的,也就意味着为通用 OS 实现最优策略(无法实现,只能比较或者接近这个)
  • FIFO 策略 即先进先出的替换策略

    • 原理

      • 简单地放入一个队列中。当发生替换的时候,队列尾部先进去的,先被踢掉
    • 缺点

      • 无法确认页的重要性
  • 随机替换策略

    • 原理

      • 内存满时随机选择一个页进行替换
    • 缺点

      • 取决运气,不够智能
  • LRU 策略 即最近最少使用替换策略

    • 原理

      • 最近最少使用的被替换
    • 缺点

      • 近乎最优替换策略

5. 补充一下

  • 这章一直在说页的缓存,我重新看了前 20 章,终于理解了什么是页的缓存,其实就是说 TLB 也就是页表,转换物理转虚拟地址缓存的那个,但是本章的中文翻译把我看蒙了,一直说页。我认识中的页就是虚拟内存,虚拟内存哪里来的缓存?只有一个地方有缓存就是 TLB 也就是 页表。不理解的,建议还是画个图,把物理地址、虚拟地址(页)、页表关系理一理。如果说的不对,可以通过右上角的邮件说下,非常感谢

🐞 第二十三章 VAX/VMS 虚拟内存系统

1. 关键问题

  • VAX/VMS 虚拟内存系统如何做到通用性?

2. VAX/VMS 操作系统的虚拟内存管理器

  • 为每一个进程提供一个 32 位的虚拟地址空间,分 512 页,即 2 的9次幂大小。因此虚拟地址有 23 位的VPN 以及9位偏移组成。此外,VPN 的高两位用于区分页所在的段,因此该系统架构是分页分段的混合体

🚜 第二十六章 并发:介绍

1. 线程

  • 程序的执行点(程序计数器,用来存放要执行的顺序命令流)。
  • 共享地址空间,从而能够访问相同的数据
  • 有线程控制块 (Thread Control Block)TCB,保存每个线程的状态,完成上下文的切换
  • 有线程本地(thread-local)存储与线程相关的东西(返回值、参数、变量)

2. 临时区

  • 多线程可能导致竞争状态的代码块,或者说访问共享资源的代码片段

3. 竞争状态

  • 出现多个执行线程同时进入了临时区,它们都试图更新共享资源,导致不同的计算结果

4. 核心问题

  • 不可调度

    • 发生上下文切换的时候(竞争状态),(临时区,获取到了共享资源)得到不同的计算结果

5. 原子性

  • 作为一个单元,全部执行,或者都没有执行,不会有中间状态

6. 关键问题

  • 同步原语,需要从哪些硬件支持?
  • 需要从操作系统获取到什么支持?
  • 如何正确邮箱的构建这些原语?
  • 程序如何使用它们(原语)来获得期望结果?

🗽 第二十八章 锁

1. 什么是锁

  • 放在临界区周围,保证临界区能够像单条原子指令一样执行

2. 关键问题

  • 如何构建一个高效的锁?
  • 需要什么硬件支持?
  • 需要什么操作系统支持?

3. 评价锁的好坏

  • 提供互斥功能,最基本的功能
  • 公平性,保证每个锁都有机会抢到锁
  • 性能开销

4. 互斥解决方案

  • 控制中断

    • 在其他线程进入临界区之前关闭中断
    • 效率低,需要重新去唤醒
  • 自旋锁

    • 设置标志位,死循环检查标志位是否可以进入临界区
    • 单个 CPU 开销较大,自旋线程一直持有 CPU 资源。多个 CPU 效果良好,没有浪费 CPU 周期
  • 比较并交换

    • 硬件层面提供比较并交换的指令,比较旧值相同才执行交换,更新新值
    • 等价自旋锁

5. 如何避免自旋过多

  • 在自旋的时候,放弃CPU
  • 使用队列保存线程,被调用的时候才唤醒,其他时候休眠
  • 两阶段锁,第一阶段先自旋,希望能获取锁,如果第一阶段没有获取锁,第二阶段调用者会睡眠

🐠 第二十九章 基于锁的并发数据结构

1. 关键问题

  • 如何加锁才能让数据结构功能正确?
  • 给数据结构加锁的同时,怎么保证并发访问?

2. 懒惰计数器

  • 核心线程想增加计数器,那么就增加局部计数器,访问这个局部计数器时通过对应的局部锁同步,同时还有一个全局计数器,局部计数器会定期转移给全局计数器,然后将局部计数器变为0,完成更新

3. 并发链表

  • 获取锁以及释放锁只围绕在插入数据的代码那块。其他方法实际不需要上锁。因为只有插入的代码才是真正的临界区

4. 并发队列

  • 两把锁,一把锁队列头,一把锁队列尾,这样出队列、入队列的时候可以并发操作。入队列的时候只能访问 tail 锁,出队列的时候只能访问 head 锁

😸 第三十一章 信号量

1. 关键问题

  • 信号量代替锁和条件变量?
  • 什么是信号量?
  • 什么是二值信号量?
  • 用锁和条件变量来实现信号量是否简单?
  • 如何实现信号量?

2. 信号量

  • 一个整数值的对象,标记是否上锁,或者未上锁

😀 第三十二章 常见并发问题

1. 非死锁缺陷

  • 违反原子性缺陷

    • 代码段本意是原子的,但是实际执行中没有实现原子性
  • 违反顺序缺陷

    • 两个内存访问的预期顺序被打破

2. 死锁缺陷

  • 什么是死锁

    • 线程 1 持有锁 L1 ,等待另一个锁 L2,而线程 2 持有 L2 锁,等待 L1 锁,两个线程相互等待,这时就会产生死锁
  • 死锁产生的条件

    • 互斥

      • 线程对于需要的资源进行互斥请求,(例如一个线程抢锁)
    • 持有并等待

      • 线程持有了资源,同时又等待其他资源(例如,需要获取锁)
    • 非抢占

      • 直线获得资源,不能被抢占
    • 循环等待

      • 线程之间存在一个环路,环路上每个线程都额外持有一个资源,而这个资源又是下一个线程需要申请的
    • 以上四个条件同时触发,即产生死锁

  • 预防

    • 循环等待

      • 顺序申请锁
    • 持有并等待

      • 任何线程在抢占锁的时候,先抢全局的锁
    • 非抢占

      • 抢占锁失败后,需要释放资源
    • 互斥

      • 使用硬件访问方面的指令完成更新值(比较并交换这样的指令)
Copyright © Sinsy Note 2021            updated 2021-08-10 00:20:51

results matching ""

    No results matching ""