基于事件驱动的并发

基于事件驱动的并发模式出现在 GUI 应用程序中,还有某些服务器编程中,比如说 node-js,但它们的根基还在基于 Unix 系统提供的底层功能构建起来的。

多线程编程有两个问题,第一个是编写正确的多线程程序是个很有挑战的事情,第二个是多线程环境下编程者没有权力控制线程的调度、线程的调度依赖底层 OS。这可能并不能如编程者所愿。

最基本的 Idea:事件循环

The approac......

信号量 Semaphores

Semaphores 这个概念也是由迪杰斯特拉发明的。在这节你将会看到,信号量可以用来实现锁和条件变量。

定义

A semaphore is an object with an integer value that we can manipulate with two routines;

这两个 routines 在 POSIX 中分别叫是 sem_wait 和 sem_post。......

条件变量

现实中,我们经常会碰到一种场景,那就是希望等待某个条件满足的时候被通知。

条件变量的概念就从此来了。这篇的分析也比较长,请大家耐心。

定义

A condition variable is an explicit queue that threads can put themselves on when some state of execution (i.e., some condi......

基于锁的数据结构

上篇笔记介绍了锁的实现大概是怎样的,这篇笔记我们讲解一些基于锁的数据结构。

给某些数据结构可以使得数据结构支持多线程环境下使用,让这些数据结构变得 线程安全(thread-safe)。

当然文中也不会记录所有的数据结构,这得要成千上万篇论文的篇幅去讲述,这里还是抛砖引玉。

Concurrent Counter

A Counter Without Locks

typedef......

本篇将会探讨锁的实现,篇幅相比之前的笔记有点长,大家见谅。

锁的基本概念

锁其实一个变量,我们在里面保存了一些重要的信息(包括锁的状态),比如说当前是哪个线程拥有了这把锁,或者是一个想请求这把锁的队列,但这些信息是存在 lock_t 里的。(熟悉 C 语言的盆友可以猜出,这是个结构体)

锁提供给程序员最小化调度机制。

道理就是,具体选择哪个进程、线程执行代码是有操作系统控制的......

并发 - 引言

通过前面的一大节,我们了解了操作系统是如何给进程提供一个独占 CPU 、独占大部分地址空间的虚拟假象。

这部分,书中重点发关注另外一个虚拟抽象,线程(Thread)。

前面的文章我们都是的执行流都只有一个,想要另外一个执行流,唯有多进程的方式。而多线程程序,运行一个进程拥有多个执行流。不同的是,进程是独立的,线程是共享所属进程的资源的。

线程的并发执行当然涉及到上下文切换。......

VMM 虚拟机器监控

引言

很多年前,IBM 在售卖它们及其昂贵的大型机给大小组织机构。一个共同的需求在客户中提出,如果客户想要同时在这些硬件上运行不同的操作系统怎么办?还有,有些应用程序部署在某种 OS 上,另外些应用程序需要部署在另外的 OS 上。

IBM 为此种需求提供了一个解决方案,那就是 Virtual Machine Monitor ( VMM ),也被叫做 hypervisor (这个名字可能更......

超越物理内存限制的内存管理策略

对于一个虚拟内存管理器来说,当有很多空闲内存时,任务是很轻松的。但是生活不会这样。

有很多的限制会迫使 OS 把内存页换出内存中。决定哪个页面被换出去是个极大的挑战。

Cache 管理

在进入具体的策略分析之前,OS 得要知道,换出一个页面对系统的整体影响的指标是什么,决定了这个页面被换出,对系统的影响是怎样的。

引用的一篇论文提出的一个指标:AMAT,Average Mem......

超越物理内存限制的内存管理机制

没有为止,我们讨论的都是基于一个重要假设:每个进程的地址空间都能被 load 进内存。

这个假设是不现实的,因为内存永远都有被用完的一天,就跟人的一生生一样,我们必须考虑在有限的空间和时间里,让更多进程得到内存被分配的机会。

交换空间 Swap Space

内核会保留一些磁盘用于把内存页换出去,我们通常把这些磁盘空间叫做 交换空间(swap space)。

操作系统还必须记住......

缩小页表

上一篇 《TLB - 加速地址翻译》 介绍了加速虚拟地址翻译的机制和策略,但是还有个问题没有很好的解决,那就页表很占内存的问题。

一个 32-bit 的虚拟地址空间(2^32),有着 4KB(2^12) 的页大小,则可能有 2^20=2^(32 - 12) 个(大约 100 多万)个 PTE,假设每个 PTE 4 字节大小,则这个进程的整个页表可能高达 4MB,假设有 100 个进程在操作......

TLB - 加速地址翻译

上一篇《页式内存管理 - 简介》 介绍了页式内存管理的机制,留下了一个问题,那就是 慢,因为多访问了一次内存。

有没有办法减少内存访问次数的办法呢?

有。那就是 Cache,TLB (Translation Lookaside Buffer)——一小块集成在 MMU 中的芯片。

在每一次内存访问里,硬件先看下 TLB 中是否已经有想要的 Page Entry——如果有,那就......

页式内存管理

这是 《Operating System: Three Easy Pieces》 的第 7 篇读书笔记。

有关 页式内存管理 介绍 。

主要介绍的是一种常见的内存管理方式。

操作系统几乎会采取两种方式来应对空间管理的问题。第一种是把空间切成大小完全相等的碎片,第二种就是把空间切分成大小相等的碎片。

第一种方式如前面两篇笔记提到的,所带来的外部碎片管理问题让人头疼,......

空闲内存管理

这是 《Operating System: Three Easy Pieces》 的第 6 篇读书笔记。

上篇笔记 介绍了管理内存的一种方式:分段式内存管理,它可以更灵活的分配和管理内存。

本章将讨论内存管理中另一个相当基础的部分——空闲内存的管理,无论是 glibc 的 malloc 库,还是操作系统自身。

当内存切片都是固定大小的时候,分配会比较简单些,只要保存一个数组......

段式内存管理

这是 《Operating System: Three Easy Pieces》 的第 5 篇读书笔记。

上篇笔记 介绍了管理内存的一种简单实现方式,基于 base register 和 bound register 实现的 虚拟地址翻译、内存管理方式。

这种方式简单直观,但是缺点也是明显的——太浪费内存空间了,每个进程的 堆内存 和 栈内存 之间有很大的空隙是不被使用的,但是还是......

内存地址翻译

这是 《Operating System: Three Easy Pieces》 的第 4 篇读书笔记。

有关 虚拟内存地址的翻译机制( Mechanism )。

OS 对内存的掌控意味着 OS 会确保 一个运行中的应用程序只能访问得到属于它自己的内存,不能访问其他应用程序的内存 。

关键点:如何高效灵活地虚拟化内存?

关键点分解:

How can we ......

内存管理相关的 API

这是 《Operating System: Three Easy Pieces》 的第 3 篇读书笔记。

有关 内存管理的 API 。

主要介绍的是基于 Unix 系列系统的内存管理相关的 API。

关键点:如果分配和管理内存?

在 Unix里,或者说 C 程序里,理解如何分配和管理内存对于构建健壮和可靠的软件是非常关键的。

那么,哪些接口是经常使用的呢?......

CPU 调度策略

这是 《Operating System: Three Easy Pieces》 的第 2 篇读书笔记。

接上篇笔记《Mechanisms on Virtualizing the CPU》,上篇文章介绍了操作系统在虚拟化CPU方面需要的基础机制/设施(Mechanisms),主要是与硬件协作共同提供给上层应用一个安全实用的抽象,本篇主要记录操作系统在调度CPU方面的策略(Policies)......

CPU 虚拟化的机制

这是 《Operating System: Three Easy Pieces》 的第 1 篇读书笔记。

关于 CPU Virtualization。

Synopsis on virtualizing the CPU

Turning a single CPU(or small set of them) into seemingly infinite number of CPUs an......