操作系统、网络与分布式系统

复习32个大学层次的系统概念:进程、并发与虚拟内存;TCP、DNS、HTTP与TLS;以及分布式共识、事务与缓存。需具备基本的编程和计算机网络知识。涉及相关条件时,会说明协议版本及故障假设。

Category
Computer Science
Level
intermediate
Languages
zh → zh
Cards
32
Markdown
操作系统、网络与分布式系统 (.md)

Flashcards (32)

#Front (Term / Question)Back (Definition / Answer)ExampleMultiple-Choice Options
1资源死锁所需的四个 Coffman 条件是什么?互斥、占有并等待、不可抢占资源、循环等待。在经典的可重用资源模型中,破坏任一条件都能防止这类死锁。允许这些条件存在,并不意味着每次执行都必然发生死锁。
2两阶段提交(2PC)的准备阶段和决策阶段分别做什么?每个参与者只有在持久保存准备状态后才投 YES;若无法提交则投 NO。协调者仅在所有参与者都投 YES 后才持久记录 COMMIT;否则,可在尚未决定提交时决定 ABORT。随后协调者通知决策。参与者准备完成后的超时,不赋予它单方面中止的权利。
3全局锁顺序如何防止循环等待死锁?为锁规定一致的严格顺序,并要求每个线程在持有其他锁时,只能按递增顺序获取新锁。若形成环,就要求顺序不断增加后又回到起点,这是不可能的。所有相关的加锁路径都必须遵守此规则。
4Raft 如何选举领导者?随机选举超时起什么作用?选举超时后,跟随者成为候选者,增加任期号,投票给自己并请求其他节点投票。候选者需要多数票;每台服务器每个任期最多投一票,并检查日志是否足够新。随机超时可减少反复分票,但不保证每次选举都成功。
5基于环的一致性哈希如何减少节点变化时的键重新分配?将键和节点哈希到环上,把每个键分配给顺时针方向的下一个节点。加入节点会分割一个区间,删除节点则把其区间交给后继。若分布足够均匀,改变 N 个节点中的一个,K 个键中需要重新分配的数量的期望值为 O(K/N);这不是最坏情况保证。虚拟节点有助于均衡。
6网络分区期间,CAP 要求复制数据服务作出什么取舍?它不能同时保证可线性化的读写,以及发往未故障节点的每个请求都成功完成。为保持可线性化,有些请求可能必须等待或失败;为在分区两侧继续服务,就必须弱化某项一致性保证。CAP 不是正常运行时无条件的“任意选两项”规则。
7旁路缓存(cache-aside)如何处理读取?应用先检查缓存。命中时返回缓存值;未命中时读取后端存储,填充缓存并返回值。由于缓存数据可能过时,仍需设置过期和失效策略。
8普通的未缓存 DNS 名称查询如何完成?客户端询问递归解析器。必要时,解析器沿着转介从根服务器到顶级域服务器,再到权威服务器,取得 A、AAAA 等记录。它返回答案,并可按 TTL 缓存;已有的转介或答案缓存可省去部分步骤。
9最终一致性承诺什么?冲突处理机制起什么作用?若更新停止,且更新或修复最终能够到达各副本,副本应按照系统的协调规则收敛。向量时钟可识别因果顺序和并发版本,但自身不解决冲突。兼容的 CRDT 合并或“最后写入者获胜”等确定性策略可以协调状态,不过后者可能丢弃更新。
10在典型操作系统中,进程和线程有什么区别?进程是资源与保护的容器,拥有自己的虚拟地址空间。同一进程中的线程共享该空间以及已打开文件等资源,但各自拥有执行状态,包括寄存器、程序计数器和栈。不同进程也可以显式共享内存。
11什么是竞态条件?为什么临界区需要同步?当正确性取决于并发操作的时机或交错次序时,就存在竞态条件。临界区访问共享状态,而该状态的不变量必须受到保护。互斥是常用方法,可确保同一时刻只有一个线程执行相关临界区。
12在 RFC 5681 的经典 TCP 模型中,慢启动和拥塞避免如何增大 cwnd?低于慢启动阈值时,ACK 驱动的增长大致呈指数型,cwnd 每个往返时间可能约翻一倍。在拥塞避免阶段,每个往返时间大约增加一个最大报文段大小。ACK 行为会影响增长;其他 TCP 拥塞控制算法不一定遵循这一模式。
13互斥锁与计数信号量有什么区别?互斥锁提供基于所有权的互斥,应由持有它的线程释放。计数信号量没有这种所有权规则;成功的等待操作消耗一个许可,post 操作增加一个许可。若初始有 N 个许可,且获取与释放配对,它可将同时使用资源的用户数限制为 N。
14直写缓存(write-through)和异步回写缓存(write-behind)有何区别?直写将后端存储写入作为写操作的一部分,在完成后才确认成功。异步回写先确认缓存更新,再于之后写入后端,从而降低即时写延迟。若没有持久保护,待写数据可能因故障丢失;持久性取决于系统,而不只取决于模式名称。
15TCP 和 UDP 提供的服务有何不同?TCP 提供面向连接、可靠、有序的字节流,具有重传、流量控制和拥塞控制;连接仍可能失败。UDP 保留数据报边界,但自身不保证交付、顺序或重传。使用 UDP 的应用可以自行添加这些机制。
16从底层到顶层,OSI 七层和常见 TCP/IP 四层分别是什么?OSI:物理层、数据链路层、网络层、传输层、会话层、表示层、应用层。常见 TCP/IP 四层:链路层、网际层、传输层、应用层。这是不同的体系结构模型,层次并非严格一一对应。
17什么是 Belady 异常?为什么 LRU 不会出现这种异常?对于相同的页面引用序列,FIFO 等某些置换策略在获得更多页框后反而可能产生更多页故障。LRU 具有栈性质:使用 N 个页框时保留的页面集合,是使用 N+1 个页框时的子集。因此,增加其页框数不会增加该序列的页故障次数。
18两阶段提交为什么可能阻塞?已投 YES 的参与者必须保留准备状态,直到得知决策。若协调者故障,且没有可联系的参与者能够确定决策,它可能需要持有锁等资源等待恢复。阻塞是可能的结果,并非每次协调者故障后的必然结果。
19为何会发生页故障?操作系统可能如何处理?若访问所需的地址映射不存在,或权限不允许访问,就会触发页故障。合法访问可能需要延迟分配、写时复制,或从文件、交换区读入页面;操作系统更新映射后重试指令。非法访问则引发错误,常表现为向进程发送信号。并非每次页故障都需要磁盘 I/O。
20TCP 主动关闭方为何通常要在 TIME-WAIT 中等待两倍的最大报文段生存时间?如果最后的 ACK 丢失,TIME-WAIT 允许关闭方确认重传的 FIN,也让旧报文段在相同连接标识被重新使用前失效。通常等待 2×MSL。这有助于安全关闭连接,并不保证 ACK 永远不会丢失。
21熔断器的 closed、open 和 half-open 状态分别做什么?Closed(闭合)允许调用并记录故障。达到设定的故障阈值后,open(断开)快速拒绝调用。等待一段时间后,half-open(半开)允许有限的探测调用;恢复正常则闭合,再次失败则重新断开。该模式限制对故障服务的重复调用,并不会修复服务本身。
22PACELC 框架在 CAP 的基础上补充了什么?若出现分区(P),考虑可用性与一致性之间的取舍(A/C);否则(E),考虑延迟与一致性之间的取舍(L/C),尤其是在副本需要协调时。PACELC 用于讨论设计选择,并非断言每个操作都有同一种固定、普遍适用的取舍。
23轮转调度如何使用时间片?有什么取舍?每个可运行任务最多运行一个时间片,然后排到就绪队列末尾;它也可能提前阻塞、让出 CPU 或结束。时间片短可改善响应性,但会增加切换开销。若时间片长于连续使用 CPU 的时段,其行为就接近先来先服务调度。
24不携带数据的普通 TCP 三次握手包括哪些消息?客户端发送初始序列号为 x 的 SYN。服务器发送序列号为 y、确认号为 x+1 的 SYN+ACK。客户端再发送确认 y+1 的 ACK。每个 SYN 占用一个序列号;纯 ACK 不占用序列号。
25CPU 上下文切换时会保存和恢复哪些状态?操作系统保存被换出任务的执行状态,如寄存器、程序计数器和栈指针,并恢复被换入任务的状态。需要时才改变地址空间状态;同一进程内的线程切换不一定需要改变页表根。具体保存哪些状态取决于体系结构和实现。
26Raft 的日志匹配性质是什么?如何修复跟随者的冲突日志?若两份日志在相同索引处具有相同任期的条目,则截至该索引的前缀完全相同。AppendEntries 检查前一个索引和任期;领导者重试直至找到匹配前缀,再以自己的条目替换跟随者的冲突条目。正确的 Raft 绝不会丢弃已提交条目。
27什么是缓存请求风暴(cache stampede)?如何缓解?大量请求同时未命中同一个已过期或不存在的缓存项,并同时重新计算或读取它,导致后端服务过载。按键合并请求、正确管理锁,或提前/概率性刷新可以缓解突发负载。效果取决于时序和故障处理。
28HTTP/2 如何多路复用请求?还可能出现什么队头阻塞?HTTP/2 在一条 TCP 连接上交错传送不同流的二进制帧,并用 HPACK 压缩字段区段。这避免了 HTTP/1.1 流水线要求响应按顺序返回的限制。但 TCP 仍按序交付字节,因此丢失一个 TCP 报文段可能延迟多个流的数据。
29TCP 接收窗口 rwnd 和拥塞窗口 cwnd 如何限制发送?接收方通告 rwnd,限制自己准备接收的数据量;发送方维护 cwnd,限制对网络施加的负载。正常运行时,已发送但尚未确认的数据量受 min(rwnd, cwnd) 限制。两者分别针对接收方容量和网络拥塞。
30什么是分页和地址转换后备缓冲器(TLB)?分页通过页表将虚拟内存页映射到物理页框。TLB 缓存近期的地址转换及相关访问权限信息,减少页表查询。系统可能支持多种页大小;TLB 缓存的是转换,不是页面数据。
31典型的基于证书认证的 TLS 1.3 连接由哪些机制保护?证书验证和握手签名认证对端身份;临时(EC)DHE 建立共享密钥材料;AEAD 保护应用数据的机密性和完整性。TLS 1.3 也支持预共享密钥模式,因此不能假定每种模式或 0-RTT 数据都使用证书并具有前向保密性。
32基于 QUIC 的 HTTP/3 如何减轻传输层队头阻塞?QUIC 在 UDP 上承载相互独立的可靠流,因此一个流缺失数据不一定阻止另一个流交付。丢失恢复和拥塞控制仍作用于整个连接。QUIC 支持一次往返握手;对于符合条件的恢复连接,还可选用存在重放风险的 0-RTT 数据。