现代操作系统
本文是《现代操作系统》第 4 版的笔记。
第 1 章 引论
为了使用一个SATA硬盘，它参考书超过 450 页，太复杂了，所以人们创造了 硬盘驱动 disk driver 这样一种软件来和硬件交互，它提供了读写硬盘块的接口，而不用深入了解硬件细节。但就算在这个层面，对于应用程序来说还是太底层了，所以操作系统使用驱动程序再一次抽象出文件这一概念。程序能够创建、读写文件，而不用处理驱动的细节。
启动计算机:
计算机加电后，
BIOS(Basic Input Output System)第一个运行，负责检查RAM个数、键盘和其他设备是否正常安装并且响应，接着扫描ISA与PCI总线并且找出连接到上面的所有设备。之后
BIOS读取CMOS存储器中的启动列表(硬盘、CD-ROM、USB 闪存、软盘等)，按照次序找到第一个存在的设备，从里面加载第一个扇区MBR，根据MBR的指示，加载存储在分区中的操作系统引导程序（比如grub2）grub2负责读入操作系统操作系统询问
BIOS索要各种设备的信息，将各种设备的驱动程序调入内核，然后初始化系统，创建各种守护进程，并启动用户登录程序或GUI
第 2 章 进程与线程
一个进程就是一个正在执行的程序的实例，包含程序计数器、寄存器和变量的当前值。每个进程可以理解为有它自己的虚拟CPU，当然实际情况时是 CPU 在一段时间内快速在多个进程间切换。这也是多道程序设计、分时系统的意思。
如下图所示，实际只有一个物理程序计数器，每个进程内部保存自己的逻辑程序计数器，每次切换到它运行时，逻辑程序计数器被装入物理程序计数器中，切换出运行态时，物理程序计数器再写回逻辑程序计数器。在任意一个给定的时刻，都只有一个进程在执行。
UNIX中，一个进程和它的所有后代共同组成一个进程组，键盘产生的信号发送给与键盘关联的进程组中的所有成员，每个进程都可以捕获到这个信号。
进程的状态
UNIX系统中，一个进程从管道或者设备文件读取数据时，如果没有有效的输入存在，则进程会被自动阻塞。
进程的实现
每个进程都是独立的实体，有自己的程序计数器和内部状态。内核维护了一张进程表，每个进程占据一条记录，每条记录被称为PCB 进程控制块。它存储的信息如下:
进程从运行态转换到就绪态/阻塞态时，将它执行时的信息保存在PCB中，用于恢复运行现场，从而保证它再次进入运行态时，就像从未被中断过一样。
中断过程:
硬件压入堆栈程序计数器等信息
硬件从中断向量装入新的程序计数器
保存寄存器值(汇编语言)
设置新的堆栈(汇编语言)
中断服务例程运行(C 语言)，读取和缓冲输入
调度程序决定下一个将运行的进程
开始运行新的进程(汇编语言)
线程
一个进程通常只有一块内存空间，以及一个控制线程。如果希望在同一个地址空间中并行地运行多个控制线程呢？
进程中需要多线程的理由是：一个应用中同时发生着多种活动，某些活动会阻塞(比如等待用户输入、读取磁盘等)，而渲染、计算等活动则可以一直使用CPU，如果这个应用可以分解成可以并行运行的多个顺序线程，程序设计模型将会变得简单。
如果应用的所有线程都是计算密集型，那么多线程并不能带来性能上的增强；但是如果应用包含了大量的计算和大量的I/O处理，则多个线程分别处理这两种情况，则可以加快应用程序的执行。
比如Word程序使用的线程:
交互线程:与用户交互,监控着鼠标与键盘，当用户有操作文本内容时，立刻通知格式化线程
格式化线程:计算并重新排版内容
自动备份线程:使用定时器，每一分钟自动保存整个文本到磁盘
再来看一个多线程的Web服务器:
其实可以用三种方式实现Web服务器：
单线程进程:
Web服务器的主循环获得请求，检查请求，并且在取下一个请求之前完成整个工作。这里有个问题，就是当I/O操作时，进程是阻塞的，CPU空转，并且无法处理下一个请求。所以这种实现方式，每秒钟只能处理很少的请求。
单线程+非阻塞 I/O:
请求到来时，线程对请求进行考察:
如果能够及时处理，则处理
如果需要
IO操作，则使用非阻塞I/O如果能直接读取到数据，则继续处理
如果不能读取到数据，则直接返回
-1，不阻塞进程，然后将这次请求以及它的状态保存下来，然后继续处理下一个请求
当某个保存的请求的I/O操作的数据准备好可以读取时，进程收到一个中断或者信号(由内核发送的)，打断当前的程序执行，进程保存下工作现场后，转而去处理中断信号，这时候就可以将该请求以及它状态取出，然后读取I/O数据，计算处理后，返回给前端。
通过这种方式，也可以每秒钟接收大量请求，保存请求以及处理中断事件，会打断程序执行流，导致理解困难，且编程实现复杂。
多线程+阻塞 I/O
多线程使得程序执行流不会被打断，单个线程使用阻塞I/O被阻塞后，不会影响到其他线程(尤其时主线程)的执行，所以每秒钟(主线程)可以接收大量请求，然后分配给其他线程处理。
总结起来就是，阻塞I/O调用使得程序顺序执行，编程变得简单容易，但是也是由于阻塞，导致每秒钟能处理的请求不多。而多线程可以使得主线程接收请求，不处理I/O永远不会堵塞，然后分配工作线程去处理请求，工作线程的IO堵塞并不会影响到主线程，从而既可以处理大量请求，又可以使用阻塞IO，让编程变得简单。
进程与线程的不同:
进程将相关的资源集中在一起，其中包括打开的文件、子进程、即将发生的警报、信号处理程序、账号信息等。
线程处于进程中，共享进程的一切。
但线程则拥有独立的程序计数器，用以记录接着要执行的指令
拥有独立寄存器，来保存当前线程的工作变量
还拥有一个栈，用于记录线程自身的局部变量。
线程是CPU上被调度执行的实体。现代CPU能直接硬件支持线程切换，在纳秒级就可完成。
POSIX线程规范:
线程库的实现一般有两种方式:
在用户空间中，内核对线程一无所知。在内核看来，就是按单线程进程在处理这些线程。进程内部保存了它内部所有线程的记录表，当进程中的某个线程执行阻塞操作时，进程内部切换成另一个就绪状态的线程，继续运行。这样子实现的进程切换，比陷入内核态实现的线程切换，要快一个数量级。
在内核中实现
线程切换:实际操作是将进程当前的堆栈指针和程序计数器，更换为线程表中将要执行的线程的堆栈指针和程序计数器，就是切换的意思了。
进程间通信
多个进程读写某些共享数据，最后的结果取决于程序运行的次序(进程的调度运行导致运行次序不可预测)，称为竞争条件。如果程序存在竞争条件，则大多数情况下，测试运行结果都运行良好，但在极少数情况下，会发生一些无法解释结果的奇怪情况。
涉及到共享内存、共享文件、以及任何共享资源的情况下，都会引发不可预测的修改，导致结果不可预测。要避免这种情况，必须找到一种方法阻止多个进程同时读写共享的数据。即我们需要互斥操作，一个进程在操作共享内存时，其他进程不能做同样的操作。
我们把对共享内存进行访问的程序片段称为临界区,如果我们通过适当安排，使得两个进程不可能同时处于临界区中，就能够避免竞争条件。
第 3 章 存储管理
最开始存储器是没有抽象的，每一个程序直接访问物理地址。这种情况下，同时运行两个程序时不可能的，因为无法防止一个程序修改另一个程序的内存。
只存在操作系统和一个用户进程的情景下，内存组织方法:
这种情况，模拟同时运行多个程序的方法是，把当前进程的内存所有内容保存到磁盘文件，然后把下一个程序读入内存再运行。
地址空间的概念
要保证多个应用程序同时处于内存中且并不相互影响，需要解决两个问题:保护和重定位。
地址空间是一个进程可使用的一套内存地址集合，每个进程都有一个自己的地址空间，并且这个地址空间独立于其他进程的地址空间。
实现这个地址空间的方法:
基址寄存器于界限寄存器:
交换技术:把一个进程完整调入内存，运行一段时间后将它存回磁盘。空闲进程主要存储在磁盘上，当它们不运行时就不会占用内存。
虚拟内存:该策略使得程序可以在只有一部分被调入内存的情况下运行。
分页技术:虚拟内存和物理内存都划分成4K大小的页，内核使用页表将正在使用的物理内存页 与 对应的虚拟内存页 的映射记录下来。
如果程序运行中，要执行一个指令，这个指令访问到了一个虚拟内存地址，而这个虚拟内存地址时没有处于映射表中的，这时内核就会发生一次缺页中断，促使内核从物理内存中选出一个未使用的(或者将一个已使用的物理内存页空出来，该页的内容交换到磁盘上)，将这个物理内存页映射给该指令的虚拟内存地址所在的页。然后中断返回到该进程的指令处，执行该指令。
在分页系统的设计与实现时，需要考虑:
虚拟地址到物理地址的映射必须非常快
如果虚拟地址空间很大，那么页表也会非常大，每个进程都需要自己的页表
第 4 章 文件系统
长期存储:
能够存储大量信息
使用信息的进程终止时，信息仍旧存在
必须能够使多个进程并发存取有关信息
磁盘支持:
读取块
写入块
设计问题:
如何找到信息?
如何防止一个用户读取另一个用户的数据？
如何知道哪些块时空闲的?
文件是对磁盘的抽象，是进程创建的信息逻辑单元。操作系统中处理文件（构造、命名、访问、使用、保护、实现和管理）的部分称为文件系统。
文件类型:
普通文件
文本文件
二进制文件，具有一定的内部结构，只有使用二进制文件的程序才了解这种结构
目录，是管理文件系统结构的系统文件
字符特殊文件
块特殊文件
文件访问:
顺序访问，早期操作系统只支持这种访问，进程必须从头按顺序读取文件的全部字节或记录，不能跳过，或者返回到起点，因为存储介质是磁带
随机访问，磁盘支持不按顺序读取文件中的字节或记录，能够以任何次序读取其中字节(
seek操作)
文件系统的实现
磁盘的 0 号扇区称为Master Boot Record主引导记录MBR,用来引导计算机。MBR的结尾时分区表，该表给出了每个分区的起始和结束地址。计算机被引导时，BIOS读入并执行MBR，第一件事就是确定活动分区，读入它的第一个块，称为引导块,执行引导块加载活动分区的操作系统。
文件存储实现的关键问题是:记录各个文件分别用到哪些磁盘块。
连续分配
链表分配
i 节点
日志结构文件系统LFS:
日志文件系统NTFS ext3:
虚拟文件系统VFS:
一个Linux系统可以用ext2作为根文件系统，ext3分区装载在/usr下，另一块采用ReiserFS文件系统的硬盘装载在/home下，以及ISO 9660的CD-ROM临时装载在/mnt下，从用户视角来看，只有一个文件系统层级。
Unix系统采用Vitrual File System虚拟文件系统将多个文件系统统一成一个有序的结构，并封装出统一的Posix接口:open、read、write、lseek等。
文件系统管理优化
磁盘空间管理
块大小
如何记录跟踪空闲块:使用位图
磁盘配额
文件系统备份
第 6 章 死锁
资源的定义:
可抢占资源:可以从拥有它的进程中抢占，而不会产生任何副作用。比如物理内存，一个获得时间片要运行的进程可以将别的进程正在使用内存换出到磁盘，然后使用它
不可抢占资源:抢占后会导致不可预计后果的资源。比如刻录机正在被 A 进程使用，刻录 A 进程的内容；如果 B 进程将它抢占，那么将会输出 B 进程的内容到光盘上，导致刻录在光盘上的内容混乱
死锁发生在不可抢占资源上。
使用一个资源可以抽象表示为:请求资源->使用资源->释放资源。
process_A()
{
get( &resource_1 )
get( &resource_2 )
use_both_resourcess()
free( &resource_2 )
free( &resource_1 )
}
process_B()
{
get( &resource_2 )
get( &resource_1 )
use_both_resources()
free( &resource_1 )
free( &resource_2 )
}多个进程 A 运行或者多个进程 B 运行都不会发生死锁，但是如果进程 A 与进程 B 都运行的话，则可能发生死锁。
死锁发生的必要条件:
资源不可抢占,已经分配给 A 进程的资源，只能由Ａ进程显式释放
资源互斥状态，资源要么已经分配给了一个进程，要么就是可用的
进程同时占有多个资源，进程 A 获取资源 1 后，未释放仍然还可以再获取资源 2
等待资源可用环路，死锁发生时，一定存在两个以上进程组成一条等待对方释放资源的环路
上述条件一定是同时满足，才会发生死锁，换句话说，只要破坏上述任意一个条件，死锁就不会发生。
死锁建模图:
圆形表示进程，方形表示资源。
一个死锁的例子:
一个避免了死锁的例子:
资源分配图可以作为一种死锁分析工具，考察对一给定的请求/释放序列是否会引起死锁。
资源轨迹图:
通过资源轨迹图，了解一下安全的概念。如上图所示，A 与 B 是两个进程，横轴与纵轴是它们运行时执行的指令序列。p->q是 A 程序在运行，q->r是 B 程序在运行。阴影区域表示不允许出现的情况，即 A 进程与 B 进程不可能同时使用打印机或绘图仪。
现在讨论这么一种情况，A 进程走完了r->s，即占用了打印机，然后 B 进程走了s->t，在t这个点，CPU 执行下一个指令，可上可右。
在t点，如果往上走，那么 CPU 指令执行一定会走到l2与l6的交叉点，这个点就是死锁:A 进程想继续向右走，需请求绘图仪(被 B 占用)，B 进程想继续往上走，需请求打印机(被 A 占用)。
所以，在t点就只有一个走法:向右走，一直走到l4，也就是 A 进程一直运行，直到放弃打印机与绘图仪资源。
安全状态与非安全状态的解释:
总共有 10 个资源，和 A、B、C 三个进程:进程运行完成所需求的资源数分别是 9、４、7。安全状态的定义为:当系统进程运行到某一时刻时，如果仍然可以找到某个调度次序能够让每一个进程运行完毕，则当前该状态称为安全状态，否则为不安全状态。
上图a)即为安全状态，可以通过上图的调度，让所有进程执行完毕。
但是，如果a)状态下，如果 A 进程再占有了一个资源，那么就成为了不安全状态，因为再也没有次序能够让每一个进程都运行完毕。图示如下:
d)中，即使所有空闲资源给 C 进程，也不够。
所以对于在a)状态下，对于 A 进程申请再占有一个资源这样的请求，系统通过分析计算得出会陷入"不安全状态"，就应该拒绝掉。这即是银行家算法。
死锁预防
我们从死锁的 4 个必要条件入手，破坏它们，只要有一个不成立，那么死锁就不会产生。
破坏互斥条件
资源被分配给了一个进程，但它仍然时可用的，依然能被别的进程请求。
怎么做到?
比如一个物理打印机，两个进程同时使用会产生混乱，那么我将物理打印机虚拟一下，成为一个打印机守护进程，整个系统中唯有它可以使用物理打印机。其他进程使用打印资源时，就向守护进程发起请求。守护进程接收了 A 的请求，将要打印的内容记录下来，如果此时 B 进程到来，那么守护进程依然可以处理请求，记录 B 的打印内容。当某个进程的打印内容记录完整后，守护进程才会实际去调用物理打印机。
破坏资源不可抢占条件
上述打印机守护进程就是破坏了资源不可抢占，守护进程在服务Ａ进程的过程中，被 B 进程抢占了。
但是不是所有的资源都可以进行虚拟化，比如数据库系统中的表记录。
破坏拥有一个资源后再去请求其他资源条件
可以从程序策略上规定，所有进程检查好它需要的全部资源，如果都能获取到，则一次性全部获取。而不是获取了一个，再去获取另一个。
另一种策略是:规定所有进程在获取一个资源时，先释放掉它获取的所有资源，然后再一次性获取所需的全部资源。
破坏环路等待条件
对资源进行编号，所有进程必须依照编号次序获取所需资源，比如必须先获取打印机，然后再获取磁带机。所有进程都按此次序和规则获取资源，则系统中一定不会出现环状图。
但是由于资源的编号次序，很难让所有人满意，并且潜在的资源数目会非常大，所以这种编号方法无法在系统级别使用。
其他死锁相关的
一般来说，在系统级别预防和避免死锁，基本上时不可能实现的。但是在一些特殊的应用方面，有很多专门的算法来应对死锁。
两阶段加锁
在数据库系统中，经常要对一些记录加锁，更新完所有记录后，再释放锁。当多个进程在同时运行时，就会出现死锁的危险。
为处理这种情况，两阶段段加锁被发明出来了。
第一阶段，程序对需更新的记录依次试图加锁，如果所有锁都添加成功，则开始第二阶段，完成更新操作，然后释放锁。
如果第一阶段中，某次加锁失败了，那么释放掉所有它已经添加的锁，然后重新开始第一阶段。
这种方式类似于“破坏拥有一个资源后再去请求其他资源条件”，让进程一次性拥有所有所需的资源。
通信死锁
A 进程向 B 进程发送一条消息，然后阻塞等待 B 进程的回复，而 B 进程一直等待 A 的消息，由于该消息在网络上丢失了，所以 A 与 B 一直相互等待。
其实，每个进程因为要等待另一个进程引发的事件而产生的阻塞，就是一种死锁。
上诉死锁，可以通过超时重传机制来解锁。
活锁
当进程意识到它不能获取所需要的下一个资源时，它会礼貌性的放弃已经获取的资源，然后等待1ms，再尝试获取其所需的所有资源。但是，当两个死锁进程在相同的时候都做了同样的事时，就像两个人同时给对方让路，并且步调一致时，导致双方都无法继续前进。
还有一种可能是，两个进程互换了被锁住的资源，然后轮流互换下去。
这种情况被称为活锁。
饥饿
在动态运行的系统中，策略决定了谁在什么时候获得什么资源，有些进程虽然不是死锁阻塞进程，但是永远得不到服务，这就是饥饿。
在一些繁忙的系统中，饥饿经常发生。比如打印文件，策略是:小文件优先打印，当小文件非常多时，大的文件永远也得不到打印机资源，
第 7 章 虚拟化与云
虚拟机管理程序需要实现:
安全性，虚拟机管理程序应该完全掌控虚拟资源
保真性，虚拟机上执行的指令应该和裸机上执行的指令相同
高效性，虚拟机中运行的大部分代码应不受虚拟机管理程序的干涉
两类虚拟机管理程序:
技术介绍:
全虚拟化:的目标是呈现出一个与底层硬件一模一样的虚拟机。
半虚拟化:目标是提供一层类似物理机器的软件接口，显式暴露自身是一个虚拟化的环境，提供一层虚拟化调用hypercall,客户机向虚拟机管理程序发送显示的请求（修改页表等）执行特权操作，就像系统调用为应用程序提供服务一样。性能非常好，但是要求客户机操作系统的实现需要参考虚拟机提供的接口。
第 8 章 多处理机系统
第二种:
存储转发包交换机制
节点之间的每条完整的消息都被分解为有最大长度限制的块，称为包packet，由源节点向网络下一个节点发送第一个包开始，收到这个包后，节点依据包里的地址信息，继续转发给下一个节点，直到目标节点收到这个包。
网卡中的RAM:
现代的网卡基本上都可以自己将接收到的包存储在自己的RAM上，等时机合适再通过总线复制到操作系统的RAM上。
对于应用层的软件来说，操作系统将下层的包机制隐藏了起来，提供了两个系统调用方法:
发送消息:语句执行后，程序将会阻塞，直到操作系统将mptr中的内容发送出去。
send( dest, &mptr );接收消息:addr指明了要监听的端口，语句执行后，程序将会阻塞，直到消息到达，操作系统将收到的消息复制到mptr缓冲区。
receive( addr, &mptr );