Yuchen You

Relational Algebra 选择 (Selection), FROM 符号: S/σ\sigmaσ (sigma), Scondition(relation)S_{\text{condition}}(\text{relation})Scondition​(relation) 用法: 从关系中选择满足特定逻辑条件的行(元组)的子集; 条件构成: 条件是 bool combitation (∧\wedge∧ 表示 AND,∨\vee∨ 表示 OR)的项;每个项的形式为 Attr1 <oper> Attr2 或 Attr <oper> value, 其中 <oper> 包括 {>, ≥\ge≥, =, ≤\le≤, <}; 示例: $\sigma_{country=‘USA’ ∧\wedge∧ sport=‘gymnastics’}(Athlete): 从 Athlete 关系中选择国家为 ‘USA’ 且运动为 ‘gymnastics’ 的运动员; 对应的SQL语句示例: SELECT * FROM Athlete WHERE s ...

这篇论文是 VMware 的基石论文 历史背景和硬件 在上世纪 90 年代, 硬件设计已经非常厉害了, 但是多个商业系统跑在一个硬件机器上非常困难, 因此这篇论文设计了一个模式: 在 hardware 和 os 之间添加一个中间层, 类似 于一个 vmm 来进行隔离 这里的硬件背景: Stanford FLASH shared memory multiprocessor experimental cache coherent non-uniform memory architecture (ccNUMA) 传统的不足 硬件的革新需要 significant OS changes OS 本体代码量过大并不适合修改来适配硬件 buggy/incompatible system software can significantly impact the success of such machines commodity OS system software 具有 constraints + inflexibility 的缺点 关键词 scalable: 设计的系统可以适配不同的( ...

Mach System 硬件平台 (Hardware) Mach 最初运行在 DEC VAX 系列机器上, 后来被移植到 IBM RT PC, Sun-3 (68k), Encore Multimax, Sequent Symmetry 等多处理器系统; 这些平台通常配备 数 MB 到数十 MB 的内存 (RAM), 数百 MB 到数 GB 的磁盘存储, 以当时标准算是中高端配置; 通过这些硬件, Mach 展示了良好的可移植性和对对称多处理器 (SMP) 的支持, 并能在有限资源下探索虚拟内存与分布式操作系统的先进机制; 抽象: 任务与线程 (Task and Thread Abstraction) Mach 将传统 UNIX 中"进程=资源+执行"的模型拆分为两个正交概念: Task: 资源容器, 包含虚拟地址空间和端口集合, 不直接执行代码; Thread: 执行单元, 在 Task 的地址空间内运行, 是调度的基本单位; 这种设计降低了开销, 并更好地支持多核并行和灵活的资源共享; 虚拟内存设计与实现 (Virtual Memory Design and ...

On μ\muμ-Kernel Construction 传统观点是, 微内核是 inefficient 和 not sufficiently flexible 的, 但是本文说明相反观点, 并展示微内核可以达到 macro kernel 的 efficiency 以及为什么当前已有的 measurement 很难说明这一点 设计目标 微内核支持 modular 外部系统可以使用 micro kernel 提供的 mechanism 微内核系统更加 flexible 和 tailorable 明确 target 决定整个 μ\muμ-kernel 的能力的不应该是 performance, 而应该是 functionality 也就是说尽量不要把指令放进内核, 除非纯外部执行无法完成指定任务 系统应该能支持 protection independence principle: 不同 sub system 之间不应该有任何互相影响和 corruption 这里的子系统指的是进程, 也就是用户态的资源分割单位 integrity principle: 不同子系统之间应 ...

Exokernel: An Operating System Architecture for Application-Level Resource Management “Dawson R. Engler, M. Frans Kaashoek, and James O’Toole Jr. M.I.T. Laboratory for Computer Science” (Engler 等, p. 251) (pdf) Motivation 传统的 general OS kernel 只能提供给最广泛的用户态程序一个中庸的最优解，然而随着软件界的发展，越来越需要一种对各种不同的软件有各自 customized 方案的特殊化优化 并且作者观察到 原语的级别越低，它的实现效率越高，并且它赋予高级抽象实现者更大的自由度 一个系统的目的应该是： OS (包括 microkernel + server):= protection + abstraction exokernel := 内核只负责 protection/security (mechanisms), 让 libOS 来负责 ab ...

Plan 9 System (Bell Lab) 硬件设备 目标环境: 便宜的小型机(办公室个人使用)+ 集中管理的大型服务器(file server, cpu server) 分布式环境设计, 强调网络互联和资源共享 UTF-8 /proc rfork 硬件存储抽象 软件文件系统抽象 包括网络的分布式一致性 创新点 设计目标 maintainence: 分布式的个人 pc 进行 administer 一个系统的开销太大太困难了 也就是通过 centralized administration 来实现集中管理 统一接口: 一切皆文件, 通过 9P 协议访问 每个进程拥有独立的命名空间, 可通过 bind 和 mount 重新组合 支持透明分布式: 远程资源与本地资源无差别 简洁内核, 核心任务是 9P 消息的 multiplex/demultiplex File System 层次化文件系统 (hierarchical file system): 所有资源挂入统一目录树 9P 协议: 核心协议, 提供 attach/walk ...

Motivation 和论文目标 守旧派往往认为, 第一代 μ\muμ-kernel 微内核具有非常低的 performance/flexibility, 但是本文希望能测试第二代微内核的性能和灵活性, 实验手段是测试一些老的系统性能测试以及加上一些新的有针对的测试 微内核的优点之一是, 内核小巧, 部件坏的概率小 微内核只提供 mechanism 但是不提供 policy, 但是也需要上面一层安全控制的 pager, FS 等资源, 这些往往依赖于 UNIX Server 实现 Introduction L4 kernel 本身是一个第二代微内核, 拥有 lean & fast 的特性 最初的 L4 kernel 是开发于 Pentium Platform 的, 但是为了证明这个内核抽象能够独立于硬件平台, 所以本文将 L4 在 Alpha21164 平台上重新完整实现了一次并且保留了传统 L4 的接口 (interface); L4 当下是支持 Pentium, Alpha 和 MIPS 三个架构, 后两者为新开发的功能 Pentium 内存空间优化 L4/Pentium ...

Goroutine 在 java/c++ 中我们要实现并发编程的时候, 我们通常需要自己维护一个线程池, 并且需要自己去包装一个又一个的任务, 同时需要自己去调度线程执行任务并维护上下文切换, 这一切通常会耗费程序员大量的心智;那么能不能有一种机制, 程序员只需要定义很多个任务, 让系统去帮助我们把这些任务分配到 CPU 上实现并发执行呢? goroutine 的概念类似于线程, 但 goroutine 是由 Go 的运行时(runtime)调度和管理的;Go 程序会智能地将 goroutine 中的任务合理地分配给每个 CPU; 它在语言层面已经内置了调度和上下文切换的机制 在 Go 语言编程中你不需要去自己写进程, 线程, 协程, 你的技能包里只有一个技能–goroutine, 当你需要让某个任务并发执行的时候, 你只需要把这个任务包装成一个函数, 开启一个 goroutine 去执行这个函数就可以了, 就是这么简单粗暴; 用法 只需要在调用函数的时候在前面加上 go 关键字, 就可以为一个函数创建一个 goroutine; 一个 goroutine 必定对应一个函数, 可以创建多 ...

什么是分布式系统? 一个分布式系统, 从物理上说是 用户 -network- 多台服务器主机 形成的一个特殊的系统 如果对这个模型进行抽象, 其实就是 单个terminal 和 多个 process 之间的通信, 其中, 这些 process 空间上分离, 通过网络进行通信, 不应该存在明显延迟, 并且命运不同(一台主机挂了不应该影响其他主机) 从上面的抽象系统目标, 我们还可以更加抽象出分布式系统的设计目标: High availability: 整体的分布式系统应当永远可用 Low latency: 用户请求的响应时间应当足够低 Scalability: 系统支持同时服务多个用户 … 银行后端为例 分布式系统设计的困难可以分为以下几个难点: concurrency: 多个 process 之间的并发控制, 但是之间的网络不可靠, 主机状态不可靠 inconsistency: 数据交换一定会存在可见延迟 ambiguity: 一个存款请求需要等待下游主机反馈 ACK, 但是如果没有收到, 如何判断是哪一步出了问题? 存款是否成功? channel 管道实现的同步 rendez ...

DBMS (Database Management System) A software package designed to store and manage databases. Often loosely called a database. 传统的数据管理, 往往是结合 csv 格式文件来将数据存储起来, 并且允许通过各种约束条件查找, 但是假设存在一个学生数据库系统, 包括 姓名, 年龄, id, 成绩等字段, 如果原始数据的存储方式是分成两个 文件, 一个存储 姓名到 id 的映射, 另一个存储 id 到成绩的映射, 那么采用传统的 c++ 等语言来查找数据, 会存在很多问题, 例如, atomic 的操作, 很难在确保 performance 的前提下能保证 consistency 因此, 为了避免上述问题, 需要一个软件系统来管理数据的存储和访问,确保有以下设计目标: Data Independence: 即客户端需要看到的只是数据的逻辑结构而非实际存储结构 Efficiency Centralized Management Security adn integri ...