type
status
date
slug
summary
tags
category
icon
password
Property
早期系统
从内存来看，早期的机器并没有提供多少抽象给用户，基本上机器的物理内存看起来如下：
操作系统曾经是一组函数（实际上是一个库），在内存中（从物理地址开始），然后有一个正在运行的程序（进程），目前在物理内存中（从物理地址 开始），并使用剩余的内存。这里几乎没有抽象，用户对操作系统的要求也不多。
多道程序和时分共享
由于机器昂贵，人们开始更有效地共享机器，多道程序系统时代开启，多个进程在给定时间准备运行，比如当有一个进程在等待I/O 操作的时候，操作系统会切换这些进程，这样增加了CPU 的有效利用率。
但很快，人们开始对机器要求更多，分时系统的时代诞生了。一种实现时分共享的方法，是让一个进程单独占用全部内存运行一小段时间，然后停止它，并将它所有的状态信息保存在磁盘上（包含所有的物理内存），加载其他进程的状态信息，再运行一段时间，这就实现了某种比较粗糙的机器共享。
遗憾的是，这种方法有一个问题：太慢了，特别是当内存增长的时候。虽然保存和恢复寄存器级的状态信息（程序计数器、通用寄存器等）相对较快，但将全部的内存信息保存到磁盘就太慢了。因此，在进程切换的时候，我们仍然将进程信息放在内存中，这样操作系统可以更有效率地实现时分共享。
type
status
date
slug
summary
tags
category
icon
password
Property
在实现CPU 虚拟化时，遵循受限直接访问，让程序运行的大部分指令直接访问硬件，只在一些关键点（如进程发起系统调用或发生时钟中断）由操作系统介入来确保”在正确时间，正确的地点，做正确的事”。
在实现虚拟内存时，追求类似的战略，在实现高效和控制的同时，提供期望的虚拟化。
- 高效决定了要利用硬件的支持
- 控制意味着操作系统要确保应用程序只能访问它自己的内存空间，要保护应用程序不会相互影响，也不会影响操作系统
- 最后，对虚拟内存还有一点要求，灵活性，希望程序能以任何方式访问它自己的地址空间，从而让系统更容易编程
如何实现高效的内存虚拟化？如何提供应用程序所需的灵活性？如何保持控制应用程序可访问的内存位置，从而确保应用程序的内存访问受到合理的限制？
利用了一种通用技术，有时被称为基于硬件的地址转换（hardware-based address translation），简称为地址转换。它可以看成是受限直接执行这种一般方法的补充。利用地址转换，硬件对每次内存访问进行处理（即指令获取、数据读取或写入），将指令中的虚拟（virtual）地址转换为数据实际存储的物理（physical）地址。在每次内存引用时，硬件都会进行地址转换，将应用程序的内存引用重定位到内存中实际的位置。
type
status
date
slug
summary
tags
category
icon
password
Property
如果需要管理的空间被划分为固定大小的单元，就很容易。在这种情况下，只需要维护这些大小固定的单元的列表，如果有请求，就返回列表中的第一项。
如果要管理的空闲空间由大小不同的单元构成，管理就变得困难。这种情况出现在用户级的内存分配库（如
malloc()和free()），或者操作系统用分段的方式实现虚拟内存。在这两种情况下，出现了外部碎片的问题：空闲空间被分割成不同大小的小块，成为碎片，后续的请求可能失败，因为没有一块足够大的连续空闲空间，即使这时总的空闲空间超出了请求的大小。
上面展示了，全部可用空闲空间是20 字节，但被切成两个10 字节大小的碎片，导致一个15字节的分配请求失败
要满足变长的分配请求，应该如何管理空闲空间？什么策略可以让碎片最小化？不同方法的时间和空间开销如何？
假定基本的接口就像
malloc()和free()提供的那样。void * malloc(size t size)需要一个参数size，它是应用程序请求的字节数。函数返回一个指针，指向这样大小的一块空间。对应的函数void free(void *ptr)函数接受一个指针，释放对应的内存块。在释放空间时，用户不需告知库这块空间的大小。因此，在只传入一个指针的情况下，库必须能够弄清楚这块内存的大小。该库管理的空间由于历史原因被称为堆，在堆上管理空闲空间的数据结构通常称为空闲列表（free list）。该结构包含了管理内存区域中所有空闲块的引用。当然，该数据结构不一定真的是列表，而只是某种可以追踪空闲空间的数据结构。
type
status
date
slug
summary
tags
category
icon
password
Property
操作系统有两种方法，来解决大多数空间管理问题
- 第一种是将空间分割成不同长度的分片，就像虚拟内存管理中的分段。遗憾的是，这个解决方法存在固有的问题。将空间切成不同长度的分片以后，空间本身会碎片化，随着时间推移，分配内存会变得比较困难。
- 因此，值得考虑第二种方法：将空间分割成固定长度的分片。在虚拟内存中，称这种思想为分页，可以追溯到一个早期的重要系统，Atlas。分页不是将一个进程的地址空间分割成几个不同长度的逻辑段（即代码、堆、段），而是分割成固定大小的单元，每个单元称为一页。相应地，把物理内存看成是定长槽块的阵列，叫作页帧（pageframe）。每个这样的页帧包含一个虚拟内存页。
下图展示了一个只有64字节的小地址空间，有4 个16 字节的页（虚拟页0、1、2、3）。物理内存，也由一组固定大小的槽块组成：
type
status
date
slug
summary
tags
category
icon
password
Property
之前一直假定地址空间非常小，能放入物理内存。
但是，为了支持更大的地址空间，操作系统需要把当前没有在用的那部分地址空间找个地方存储起来。一般来说，这个地方有一个特点，那就是比内存有更大的容量，也更慢。在现代系统中，硬盘（hard disk drive）通常能够满足这个需求。因此，在存储层级结构中，大而慢的硬盘位于底层，内存之上。
操作系统如何利用大而慢的设备，透明地提供巨大虚拟地址空间的假象？
交换空间
要做的第一件事情就是，在硬盘上开辟一部分空间用于物理页的移入和移出。在操作系统中，一般这样的空间称为交换空间（swap space），将内存中的页交换到其中，并在需要的时候又交换回去。
假设操作系统能够以页大小为单元读取或者写入交换空间。为了达到这个目的，操作系统需要记住给定页的硬盘地址。
一个4 页的物理内存和一个8 页的交换空间：
type
status
date
slug
summary
tags
category
icon
password
Property
一般，一个程序只有一个执行点（一个程序计数器，用来存放要执行的指令），但多线程（multi-threaded）程序会有多个执行点（多个程序计数器，每个都用于取指令和执行）。换一个角度来看，每个线程类似于独立的进程，只有一点区别：它们共享地址空间，从而能够访问相同的数据。
单个线程的状态与进程状态非常类似。线程有一个程序计数器（PC），记录程序从哪里获取指令。每个线程有自己的一组用于计算的寄存器。所以，如果有两个线程运行在一个处理器上，从运行一个线程（T1）切换到另一个线程（T2）时，必定发生上下文切换（context switch）。线程之间的上下文切换类似于进程间的上下文切换。对于进程，我们将状态保存到进程控制块（Process Control Block，PCB）。现在，我们需要一个或多个线程控制块（Thread Control Block，TCB），保存每个线程的状态。但是，与进程相比，线程之间的上下文切换有一点主要区别：地址空间保持不变（即不需要切换当前使用的页表）。
线程和进程之间的另一个主要区别在于栈。在简单的传统进程地址空间模型 [单线程（single-threaded）进程] 中，只有一个栈，通常位于地址空间的底部
然而，在多线程的进程中，每个线程独立运行，当然可以调用各种例程来完成正在执行的任何工作。不是地址空间中只有一个栈，而是每个线程都有一个栈。假设有一个多线程的进程，它有两个线程，结果地址空间看起来不同。
所有位于栈上的变量、参数、返回值和其他放在栈上的东西，将被放置在有时称为线程本地（thread-local）存储的地方，即相关线程的栈。
多个栈也破坏了地址空间布局的美感。以前，堆和栈可以互不影响地增长，直到空间耗尽。多个栈就没有这么简单了。幸运的是，通常栈不会很大（除了大量使用递归的程序）。
线程创建
线程创建API：
type
status
date
slug
summary
tags
category
icon
password
Property
在源代码中加锁，放在临界区周围，保证临界区能够像单条原子指令一样执行
假设临界区像这样，典型的更新共享变量：
为了使用锁，给临界区增加了这样一些代码：
锁就是一个变量，因此需要声明一个某种类型的锁变量，才能使用。这个锁变量（简称锁）保存了锁在某一时刻的状态。它要么是可用的，表示没有线程持有锁，要么是被占用的，表示有一个线程持有锁，正处于临界区。我们也可以保存其他的信息，比如持有
锁的线程，或请求获取锁的线程队列，但这些信息会隐藏起来，锁的使用者不会发现。
调用
lock()尝试获取锁，如果没有其他线程持有锁（即它是可用的），该线程会获得锁，进入临界区。这个线程有时被称为锁的持有者（owner）。如果另外一个线程对相同的锁变量（mutex）调用lock()，因为锁被另一线程持有，该调用不会返回。这样，当持有锁的线程在临界区时，其他线程就无法进入临界区。锁的持有者一旦调用
unlock()，锁就变成可用了。如果没有其他等待线程（即没有其他线程调用过lock()并卡在那里），锁的状态就变成可用了。如果有等待线程（卡在lock()里），其中一个会（最终）注意到（或收到通知）锁状态的变化，获取该锁，进入临界区。 type
status
date
slug
summary
tags
category
icon
password
Property
通过锁可以使数据结构线程安全（thread safe）
并发计数器
计数器是最简单的一种数据结构，使用广泛而且接口简单。一个非并发的计数器：
没有同步机制的计数器很简单但无法拓展，但如何让它线程安全？
这个并发计数器简单、正确。实际上，它遵循了最简单、最基本的并发数据结构中常见的数据模式：它只是加了一把锁，在调用函数操作该数据结构时获取锁，从调用返回时释放锁。这种方式类似基于
观察者（monitor）的数据结构，在调用、退出对象方法时，会自动获取锁、释放锁。现在，有了一个并发数据结构，问题可能就是性能了。如果这个结构导致运行速度太慢，那么除了简单加锁，还需要进行优化。
type
status
date
slug
summary
tags
category
icon
password
Property
在很多情况下，线程需要检查某一条件满足之后，才会继续运行。例如，父线程需要检查子线程是否执行完毕（这常被称为
join()）。这种等待如何实现呢？期望能看到这样的输出：
可以尝试用一个共享变量
这种解决方案一般能工作，但是效率低下，因为主线程会自旋检查，浪费CPU 时间。我们希望有某种方式让父线程休眠，直到等待的条件满足（即子线程完成执行）。
线程可以使用
条件变量（condition variable），来等待一个条件变成真。条件变量是一个显式队列，当某些执行状态（即条件）不满足时，线程可以把自己加入队列，等待（waiting）该条件。另外某个线程，当它改变了上述状态时，就可以唤醒一个或者多个等待线程（通过在该条件上发信号），让它们继续执行。Dijkstra 最早在“私有信号量”中提出这种思想。Hoare 后来在关于观察者的工作中，将类似的思想称为条件变量。要声明这样的条件变量，只要像这样写：
pthread_cond_t c;，这里声明 c 是一个条件变量（注：还需要适当的初始化）。条件变量有两种相关操作：wait()和 signal()。线程要睡眠的时候，调用 wait()。当线程想唤醒等待在某个条件变量上的睡眠线程时，调用 signal()。 type
status
date
slug
summary
tags
category
icon
password
Property
可以使用信号量作为锁和条件变量
信号量是有一个整数值的对象，可以用两个函数来操作它。在POSIX标准中，是
sem_wait()和sem_post()。因为信号量的初始值能够决定其行为，所以首先要初始化信号量，才能调用其他函数与之交互：信号量初始化之后，可以调用
sem_wait()或sem_post()与之交互sem_wait()要么立刻返回（调用sem_wait()时，信号量的值大于等于1），要么会让调用线程挂起，直到之后的一个post操作。当然，也可能多个调用线程都调用sem_wait()，因此都在队列中等待被唤醒。sem_post()并没有等待某些条件满足。它直接增加信号量的值，如果有等待线程，唤醒其中一个当信号量的值为负数时，这个值就是等待线程的个数
二值信号量（锁）
信号量的第一种用法：用信号量作为锁。
type
status
date
slug
summary
tags
category
icon
password
Property
非死锁缺陷
违反原子性缺陷
两个线程都要访问thd结构中的成员
proc_info。第一个线程检查proc_info非空，然后打印出值；第二个线程设置其为空。显然，当第一个线程检查之后，在fputs()调用之前被中断，第二个线程把指针置为空；当第一个线程恢复执行时，由于引用空指针，导致程序奔溃。违反原子性的定义是：“违反了多次内存访问中预期的可串行性（代码段本意是原子的，但在执行中并没有强制实现原子性）”。
proc_info 的非空检查和fputs()调用打印proc_info是假设原子的，当假设不成立时，代码就出问题了。这种问题的修复通常很简单，只要给共享变量的访问加锁，确保每个线程访问
proc_info 字段时，都持有锁（proc_info_lock）。当然，访问这个结构的所有其他代码，也应该先获取锁。