[mit6.033] 第一部分 LEC 1-6 Operating Systems 笔记

2022-10-27 16:11:32 浏览数 (1)

这是我自学 MIT6.033 课程的第一部分：Operating Systems 的笔记。 该课程共分为 4 部分：Operating Systems、Networking、Distributed Systems、Security 课程详细介绍可以查阅：https://blog.miigon.net/posts/mit6033-computer-system-design/ 笔记为学习过程中随笔记录以及思考，未经整理，所以可能会比较零散。

LEC1 Enforced Modularity via Client/Server Organization

复杂度

复杂度使得构建系统变得困难。

使用模块化和抽象的方式，来解决复杂度。

  • 模块化：模块化的系统更容易理解、管理、改变、改进
  • 模块化减少了「命运共享」(fate-sharing)
  • 抽象使我们可以不指定具体实现的情况下进行交互（隐藏细节）
  • 好的抽象设计应当减少模块之间的连接（低耦合）

「强制实施(Enforced)」的模块性

  • 「软模块化」并不足够（eg. 面向对象，但是运行在同一程序内，即错误或崩溃会在模块间传播）
  • 一种强制实施模块化的方法是客户端/服务器模型（使得模块可以运行在物理隔离的机器上。或者多进程，此时模块化与错误隔离能力由操作系统提供。）

系统设计的其他目标

  • 除了降低复杂度，我们可能还希望有：可伸缩性（scalability）、容错性（fault-tolerance）、安全性（security）、性能（performance）等。
  • 好的模块化设计可以帮助我们实现这些特性。
  • 难以全部得到，多个之间有取舍。

LEC2 Naming

对模块的「命名」使得模块之间可以互相交互。

使用命名的好处

  • 方便检索
  • 共享（多个用户访问同一个名称）
  • 用户友好
  • 寻径（eg.IP地址、域名）
  • 隐藏具体细节（以及访问控制）
  • Indirection（间接，系统可以更换一个名字所指向的具体对象，而不需改动或通知客户端）

命名的 scheme 体现了我们希望系统通过命名来得到什么功能。（addressing, indirection, etc）

Naming Schemes

  1. namespace: 所有可能的名称集合 names
  2. 所有可能的值集合 values
  3. 从 name -> values 的映射/查找算法（name resolution）

需要思考的问题：

  • 名称的语法是什么？
  • 名称是否含有内部结构？（例如IP地址、域名）
  • 名称是全局名称还是依赖上下文的局部名称？
  • 系统的那一部分有权利来做「将一个名称绑定到一个值」这件事？（eg. nameserver）
  • 一个名称可以对应多个值吗？（负载均衡）
  • 名字对应关系是否可以随时间而改变？
  • 名称解析在哪里发生？

取舍：eg. 分布性、可伸缩性、委托（delegation）

Example: DNS

benefit（与上面的需要思考的问题对应）:

  • 用户友好
  • 负载均衡（一个名称对应多个值）
  • 单机多网站（一个值对应多个名称）
  • 名字对应关系可以随时间而改变
bad design 1

初期，在每一台主机都维护了一份 hosts 映射表，当新的主机加入网络的时候，新主机向所有现有主机发送更新：

问题：难以 scale，一旦主机多起来，难以使所有机器上的映射表保持最新。 （也许还有 proofing attack 风险？）

bad design 2

用中央的服务器维护唯一的一份 hosts 映射表，每次其他主机访问域名时，都与中央服务器请求对应的 ip

问题：解决了更新一致性问题，但是依然有 scale 问题，中央服务器需要处理成吨的请求

分布式的解决方法（DNS）

DNS 中，没有任何一个机器包含所有的映射关系。映射关系被分布在许多不同的机器上。

新问题：如何知道要访问的域名的映射关系存在哪一台机器上？ 方案：DNS 名称的「结构本身」

思想：分布式（distributed） 分层架构（hierarchical）

apple、google、mit 等自己管理自己的名称服务器（nameserver）。顶级域名 com、net、edu 管理的名称服务器只解析 apple.com、mit.edu 这种二级域名以及它们的名称服务器，而类似 eecs.mit.edu 这种三级域名的解析，由 mit.edu 自己的名称服务器提供。

请求解析的时候，向根服务器发出请求，请求一层层代理委托至最终的名称服务器，得到 ip 地址。

解析 blog.miigon.net 的过程：

代码语言：javascript复制
root nameserver
-> NS of net is at 192.14.171.193

net nameserver (192.14.171.193)
-> NS of miigon.net is at 58.247.212.48

miigon.net nameserver (58.247.212.48)
-> blog.miigon.net A-record 185.199.108.153

blog.miigon.net is at 185.199.108.153

每一级向上一级/下一级请求的过程，如果由客户端完成，则为 iterative DNS，如果由每一级服务器代为完成，则为 recursive DNS。

root nameserver 的地址直接硬编码在机器中。

  • 每一层解析，更接近最终的结果：这里体现了 delegation 委托，即根服务器不能直接给出查询结果，但是可以将请求委托给下一级名称服务器去完成。

类比：文件系统路径的分层结构 对比：对象存储服务，所有文件路径都只是扁平的键，没有分层结构 （体现的是另一种设计选择与取舍：低复杂度，高访问速度，但无法做目录遍历，也就是难以实现类似 ls 指令的功能）

依然有问题：

  • 性能问题：解析需要许多请求，尤其是对根服务器
  • 可靠性问题：名称服务器失效或（安全问题）被攻击

总结

  • 「模块化」与「抽象」能降低复杂度。
  • 「客户/服务器模型」使得我们可以通过将模块放在物理隔离的机器上，从而增加模块性
  • 「命名」使得模块之间可以交互，同时提供了如间接性、用户友好等其他特性
  • DNS 是一个很好的命名实例，同时展示了如分层（hierarchy）、可伸缩（scalability）、代理委托（delegation）、去中心化（decentralization）
REC3: DNS
  • 递归（recursive）请求的好处是什么？
    • 相比 iterative，简化客户端设计，只需要请求一个名称服务器，名称服务器代为完成整个请求过程。
    • 容易实现 cache，如果请求的某一级服务器已经有完整记录，则可直接返回，而对于客户端来说是无感知的。
  • DNS 分层架构的好处是什么？有什么缺点吗？
    • 每一层只需管理/维护该层的映射关系，将工作量分摊到不同的层上的不同主机，避免了单主机处理所有请求
    • 由每个名称服务器管理自己的域内的名称，无需担心更新时需要向某个中央服务器汇报导致难以 scale 的问题
    • 依然不是完全分布式，依然有 single point of faliure（根服务器）
  • 应该由谁控制 DNS 根服务器？

LEC3 Virtual Memory

操作系统

操作系统通过「虚拟化（Virtualization）」和「抽象（Abstraction）」，保证单机上的模块性

为了实现单机器上的模块性，操作系统需要实现的目标：

  1. 程序不应该可以访问和修改其他程序的内存（隔离） => virtual memory（今天话题）
  2. 程序之间应该可以互相通信（通信机制）
  3. 程序应该可以和其他程序共享 CPU

主要实现这些目标的手段：虚拟化 操作系统对硬件的不同部分进行虚拟化，让程序以为自己访问的是完整的物理硬件。

虚拟内存

让程序寻址整个地址空间，MMU 负责将虚拟地址转换为物理地址。

  • Virtual Memory 也是一种 Naming Scheme，为我们提供了隐藏（隐藏其他程序的内存）、间接性（虚拟地址指向的实际地址可以随时改变，而不需要显式地告知程序）、访问控制（页表控制位，R/W）等特性。
Ideas
  1. 储存所有物理地址对应关系，使用整个虚拟地址作为 index
    • 问题：表太大
  2. 页表：分页映射，虚拟地址前 p 位作为页 index，后 q 位作为页内偏移
    • 体积小很多
  3. 虚拟内存是否真的能阻止程序访问其他程序的内存？（只有系统可以修改页表， 权限位，当程序尝试破坏这一模块性的时候，系统捕获exception，防止发生）
  4. 在这里会出现什么性能问题？（每次内存访问都有查表开销，缓解：TLB 快表作为 cache，潜在问题 consistency）

详细见S081。

多级页表（Hierarchical）

单级页表的设计依然需要使用许多空间，解决方法：多级页表，每一级存储指向下一级的地址，仅在使用到时分配。

tradeoff：

  • 优点：更离散化的存储（利用零散内存页），占用更小空间
  • 缺点：查询速度（多级查找而不是一级），更多的缺页异常
抽象（abstraction）

对于不可虚拟化的资源（磁盘、网络）（ps其实还是可以虚拟化的hhhhhh），系统提供抽象（系统调用），使得这些东西更加可移植。

LEC4 Bounded buffers and locks

操作系统（again）

操作系统通过「虚拟化（Virtualization）」和「抽象（Abstraction）」，保证单机上的模块性

为了实现单机器上的模块性，操作系统需要实现的目标：

  1. 程序不应该可以访问和修改其他程序的内存（隔离） => virtual memory
  2. 程序之间应该可以互相通信（通信机制） => 有界缓冲区与锁同步（今日话题）
  3. 程序应该可以和其他程序共享 CPU

Bounded buffers & locks (concurrency)

例子：unix pipe（consumer/producer）

考虑 consumer/producer 问题，如果可以用一个整数数值来描述资源剩余数量，比如剩余的 bounded buffers 空间，则可以用「信号量Semaphore」来同步。 如果资源可用条件较为复杂，无法使用整数描述，则应该使用「条件变量Condition variable」来同步（利用其较高的自由度，自定义唤醒条件） [唤醒丢失问题 & 条件变量 vs 信号量 the lost wakeup problem & condition variable vs semaphore]

本质：都是利用互斥锁同步。

Atomic actions

原子操作的粒度？

  • 过粗：性能变低（根本原因是并行性受到了限制，体现为“锁竞争严重”）
  • 过细：意外行为

tip：将锁的作用理解为「保护不变量」。在不变量被暂时破坏时保护数据结构，以不被外部察觉。在释放锁之前，operation 应该恢复该不变量。 [锁的作用 Ways to think about what locks achieve]

例子：文件系统中的锁

文件移动：

  • 粗粒度锁：锁整个文件系统，问题：性能低，不能同时移动两个文件
  • 细粒度锁：更好的性能，但是更难正确
    • 例子：将 file1.txt 从 A 移动到 B，同时将 file2.txt 从 B 移动到 A （死锁，拿A锁等B锁，拿B锁等A锁）
    • 例子解决方法：确保获取锁顺序，阻止环路形成。（例如强行要求先拿小inode号的目录的锁）

结论：一些系统中的锁问题以及锁设计，需要有全局观地去思考锁与锁之间的交互，而不能只考虑锁对局部代码的影响。

LEC5 Threads

操作系统（again again）

操作系统通过「虚拟化（Virtualization）」和「抽象（Abstraction）」，保证单机上的模块性

为了实现单机器上的模块性，操作系统需要实现的目标：

  1. 程序不应该可以访问和修改其他程序的内存（隔离） => virtual memory
  2. 程序之间应该可以互相通信（通信机制） => bounded buffers & locks
  3. 程序应该可以和其他程序共享 CPU => 虚拟化CPU（抢占式多线程 threads）

线程thread：一个虚拟的处理器（包装了一个程序的运行状态） 线程切换：将当前程序的运行状态换出，将另一个程序的运行状态换入（suspend/resume，或context switching）

  • 线程需要包含的信息：所有的寄存器、所有的内存（利用页表切换实现）
  • 何时挂起/恢复一个线程？（定期，yield()）

线程主动放弃CPU：yield()

放弃当前线程的CPU执行权，保存当前线程的信息（栈、页表寄存器、callee-saved registers，不需要保存pc，因为在栈中的return address已经有），找到另一个可以运行的线程，并恢复新线程的运行状态（恢复栈指针、页表、callee-saved registers，ret指令返回到新线程之前yield后的位置）

这一部分在s081中有更详细展开：https://cloud.tencent.com/developer/article/2142305

在 bounded buffer 的 send 遇到缓冲区不足时，进程调用 yield 来主动放弃 CPU，但是进程可能在缓冲区出现空闲之前被再次调度唤醒，然后立刻又进入睡眠。

我们希望能够实现「yield，然后直到 buffer 中有空闲位置之前都不要再次唤醒该线程」（减小无意义唤醒）——操作系统提供条件变量机制来实现这一功能（condition variable）

条件变量（condition variable）

程序可以等待（wait）一个条件（condition）的发生，并且在该条件发生的时候收到通知。 另一进程可以在一个条件变为真的时候，使用 notify() 通知所有正在等待该条件的进程。

more on [唤醒丢失问题 & 条件变量 vs 信号量 the lost wakeup problem & condition variable vs semaphore] （https://blog.miigon.net/posts/the-lost-wakeup-problem-cond-var-vs-semaphore/）

问题：lost wakeup 唤醒丢失

进程 A 在完成 release(bb.lock) 之后，但是进入 wait(bb.has_space) 之前，另一个进程 B 可能会执行 receive，从而尝试唤醒正在等待 has_space 条件变量的进程。而此时唤醒的进程中不会包括进程 A。这时候进程 A 继续执行，然后才进入到 wait(bb.has_space) 中，而不会收到来自进程 B 的唤醒。

从而，进程 A “丢失” 了进程 B 发出的这一次唤醒。

唤醒丢失的后果轻者可能是使得进程 A 需要等待下一次条件为真时才能被唤醒，对于一些十分关键的条件变量，A 可能永远都不会再收到通知，从而陷入永久的沉睡。

解决方法：wait() 进入等待的同时，原子性地放弃锁。在被唤醒之后，原子性地重新获得锁，然后再从 wait 返回到用户代码。

即：

代码语言：javascript复制
# pseudo-code
def wait(cond_var, mutex):
	release(mutex)
	currentthread.state = WAITING
	currentthread.waiting_on = cond_var
	yield_wait()
	acquire(mutex)

注意 wait 整个操作必须是原子的，这一原子性可以通过给 wait 加一个额外的锁 tlock 实现。

问题：yield_wait 死锁

这里的 yield_wait 有一个很细微的死锁问题：

这里寻找可运行的线程的循环，由于 yield_wait 被调用时持有 t_lock，假设当所有其他线程都处于等待/不可运行状态，则该循环不会找到可运行的线程，并且更糟糕的是由于该循环执行时持有 t_lock，而其他 CPU 需要首先进行 yield 才能运行线程，而 yield 所要求的 t_lock 被 yield_wait 所在 CPU 持有着，则其他 CPU 无法推进任何线程的状态，该循环永远找不到可运行线程，整个系统进入死锁。这种情况在普通的 yield 中是不会出现的，因为普通的 yield 无论如何都至少会有切换前的原线程是 RUNNABLE 的，所以循环必然会终止（而对于 yield_wait 来说不是这样）。

这里是一个 CPU 持有 t_lock 去等待「有可运行线程出现」这一条件，而可运行的线程在出现前又需要获取 t_lock，造成环路等待。

解决方法比较简单，循环中需要间断性主动放弃 t_lock，破坏环路等待，使得其他 CPU 可以推进，从而使得「可运行线程出现」，解除死锁。

问题：两个 CPU 共用同一线程栈导致栈损坏

这里还有一个小细节，由于 yield_wait 此时使用的还是原线程的栈，此时放弃 t_lock 允许其他线程执行的时候，其他 CPU 可能会执行到该线程，而此时 yield_wait 的循环依然可能需要用到栈。从而导致有两个 CPU 使用同一个线程的栈，导致栈内容损坏。

这一情况比较稀有，但是依然可能出现，解决方法就是在进入 yield_wait 循环之前，将栈切换到其他地方，比如 CPU-specific 的栈，从而避免两个 CPU 共用一个线程栈。

如果线程不主动放弃 CPU 呢？抢占（preemption）。

使用时钟中断，定期中断 CPU 执行流，并强行调用 yield。

代码语言：javascript复制
def timer_interrupt():
	push PC
	push ALL registers 
	
	yield() # will further save stack pointer,
			# page table register and callee-saved registers

	# since this is an interrupt, must restore all registers,
	# instead of just the callee-saved ones.
	pop ALL registers
	pop pc

总结

  • 「线程」虚拟化了 CPU，使得一个 CPU 可以在多个程序之间共享。
  • 「条件变量」为线程提供了一个更高效的等待其他线程事件发生的 API
  • 「抢占」使得一个进程能被中断并强制其放弃CPU，使得不需要依赖程序员主动调用 yield 来放弃 CPU（抢占式多线程以及协作式多线程）
  • 操作系统中为用户程序提供模块化的三个不同方面：内存、通信、CPU；机制看起来不同，但都是虚拟化思想的应用（虚拟化环境，使得上层应用/模块可以运行在自己独立的环境中而与其他模块互不干扰）。
  • 单机上的模块化（模块之间互相隔离）的保证，需要来自操作系统以及硬件的支持。
  • 我们成功的利用操作系统的虚拟内存机制、通信机制、虚拟化CPU机制，保证了单机上的模块性。

LEC6 OS structure, Virtual Machines

另一种 virtualization 的应用：虚拟机

目标：在同一机器上同时运行多个系统

限制：兼容性。因为我们不希望需要修改内核的代码（否则称为半虚拟化）。

操作系统考虑的是如何将程序与程序之间隔离。虚拟机的任务是退后一步，也就是如何将操作系统与操作系统之间隔离。

内核中负责运行虚拟机的模块，称为 virtual machine monitor VMM （Linux kernel 中的实现为 KVM，windows 下为 hyperv）。

VMM 需要负责分配资源以及分发事件，这里重点考虑如何处理客户系统中执行的，需要与实际硬件交互的指令。

虚拟化 CPU

尝试方案1：模拟每一条客户系统执行的指令。问题：慢（内存比寄存器要慢100倍左右，仅仅是用内存去模拟寄存器这一步就会将性能降低两个数量级） 尝试方案2：用户系统直接在真实 CPU 上运行指令。问题：特权指令的处理

VMM 负责处理特权指令，当子系统执行特权指令的时候，会引发宿主系统的中断，并允许宿主系统处理这一特权指令。

方式：

  1. 通过将客户系统运行在用户态使得特权操作触发中断（trap-and-emulate）。但是有一些特权操作（如写入 U/K 位切换用户/内核态）本身就不会触发中断，需要修改客户系统或进行指令替换；
  2. 通过硬件提供的支持，如 Intel VT-x
虚拟化内存
  • 方法1：将客户系统的页表内存设为只读，捕获每一个客户系统对页表的修改，并将其与宿主机的页表结合，生成一个合并页表，作为 CPU 实际使用的页表。
  • 方法2：现代 CPU 含有对虚拟化的支持，CPU 同时知道客户系统以及宿主系统的页表的存在，并会在客户系统尝试访问内存时，依次查询两个页表。（拓展：嵌套虚拟化，CPU 会需要知道并查找 n 层页表）

内核架构

宏内核：

  • Linux 内核，内核内部没有模块化与隔离，一个bug可以使整个系统崩溃。
  • 由于复杂度，bug 容易出现 微内核：
  • 将子系统——文件系统、设备驱动——运行为用户态程序。
  • 更好的模块性，更少的 bug，bug 更不容易将整个系统带垮。
  • 模块间接口设计更复杂，模块间通信性能可能受影响。

性能

一个选择宏内核而不是微内核的理由是性能。

测量性能的指标：吞吐量 throughput、延迟 latency。 提升性能的通用手段：批处理 batching、缓存 caching、并发 concurrency、调度 scheduling

会在后续的网络章节继续讲延迟与吞吐的话题。6.033 重点在于讨论系统设计中「通用的提升性能手段」，而不是如复杂度优化这一类场景相关的具体优化手段。

总结

在 Operating System 的 Lecture 结束后，已经理解了系统中单台机器上的模块化以及工作。后续讨论多机系统中机器之间互相交流必不可少的部分：网络。

dns 虚拟化 lock virtual wait

0 人点赞