进程可简单理解为运行中的程序，程序是指令的有序集合，没有任何执行的含义，而进程则强调的是执行过程，它动态被创建、执行和消亡。不同的进程可以来自于同一程序，只要该程序所对应的数据集不同。

进程是运行程序的主要操作系统抽象。在任何时间点，进程都可以用它的状态来描述:地址空间中内存的内容，CPU寄存器的内容(包括程序计数器和堆栈指针等)，以及关于I/O的信息(如可读或可写的打开文件)。

虚拟化cpu的实现，通过让一个进程只运行一个时间片，然后切换到其他进程，提供存在多个虚拟cpu的假象（时分共享CPU技术，对应的磁盘空间是空分共享资源）

使用fork()创建子进程后常用exec系列的函数来将子进程替换为新的进程。 用指定的程序替换当前进程的映像。这意味着当前正在运行的程序被停止，而指定的新程序在相同的进程中启动执行，从而不会改变原有的进程ID。覆写当前进程。

貌似要重点关注书上32,33,34页？也可能是31 关于shell的实现

虚拟化带来了一些问题：

性能问题:如何在不给系统增加过多开销的情况下实现虚拟化? 第二个是控制权:我们如何在保持对CPU控制的同时高效地运行进程?

→受限直接执行

为什么不直接执行？

答：通过fork（），OS一旦把控制权交给用户进程可能就失去了控制（CPU和其他硬件），且若进程希望进行受限操作（如进行I/O操作或内存申请），如何进行？

使用一种”受保护的控制权转移“

用户程序只能通过OS的系统调用进入到内核态，使用特权操作：

用户要想访问内核空间，必须借助操作系统提供的 API 函数，执行内核提供的代码，让内核自己来访问，这样才能保证内核空间的数据不会被随意修改，才能保证操作系统本身和其他程序的稳定性。 用户态→核心态的三种方式：

重点介绍系统调用： 陷阱(trap):

程序执行特殊的陷阱（trap）指令。该指令跳入内核并将特权级别提升到内核模式。进入内核，系统就可以执行任何需要的特权操作（如果允许），从而为调用进程执行所需的工作。

完成后，操作系统调用一个特殊的从陷阱返回（return-from-trap）指令，该指令实现从内核态到用户态。

陷阱如何知道在 OS 内运行哪些代码？→陷阱表（trap table）：

内核通过在启动时设置陷阱表（trap table）来实现。当机器启动时，它在特权（内核）模式下执行，操作系统做的第一件事，就是告诉硬件在发生某些异常事件时要运行哪些代码。操作系统通常通过某种特殊的指令，通知硬件这些陷阱处理程序的位置。一旦硬件被通知，它就会记住这些处理程序的位置，直到下一次重新启动机器。

设置陷阱表是一项特权操作。

进程执行时，进程在CPU上运行，操作系统如何重获控制权?

实现在进程中的切换：

如果某个进程进入无限循环，并且从不进行系统调用，怎么办？

当确定要切换进程时需要→上下文切换（context switch）：

操作系统要做的就是为当前正在执行的进程保存一些寄存器的值（例如，到它的内核栈），并为即将执行的进程恢复一些寄存器的值（从它的内核栈）。这样一来，操作系统就可以确保最后执行从陷阱返回指令后，不是返回到之前运行的进程，而是继续执行另一个进程。（P43)

如果在系统调用期间发生中断或处理中断时发生中断怎么办？→第二部分并发 用锁等来保证原子，临界区思想等？

基本思想：

调度指标：

先进先出FIFO 先来的可能要执行很久

👇

最短任务优先（Shortest Job First, SJF） 后到的短任务还是得等长任务

👇

最短完成时间优先（Shortest Time-to-Completion Firsts, STCF/抢占最短作业优先PSJF） 在响应时间指标上表现不理想

轮转（Round-Robin，RR） 并未改善周转时间

RR 在一个时间片（time slice，有时称为调度量子，scheduling quantum）内运行一个工作，然后切换到运行队列中的下一个任务，而不是运行一个任务直到结束。它反复执行，直到所有任务完成。

当继续考虑I/O时

多级反馈队列（Multi-level Feedback Queue, MLFQ） 在没有工作长度的先验知识的情况下，尝试同时减少响应时间和周转时间

MLFQ拥有多级队列，优先级不同 规则：

存在一些配置问题：

比例份额（彩票或步长）：

比例份额算法基于一个简单的想法：调度程序的最终目标，是确保每个工作获得一定比例的 CPU 时间，而不是优化周转时间和响应时间。

彩票调度： 利用随机性

利用彩票占用的百分比来表示一个进程占用的cpu的份额，当举行抽奖时，彩票中奖，该进程执行。

彩票机制：彩票调度还提供了一些机制，以不同且有效的方式来调度彩票。

公平性：

分配给自己的工作。然而这种方案似乎什么也没有解决——还是没有给出具体的分配策略。因此对于给定的一组工作，彩票分配的问题依然没有最佳答案。

================================================

步长调度：确定性的公平分配算法

系统中的每个工作都有自己的步长，这个值与彩票数值成反比。

调度时，选择目前拥有最小行程值的进程，并且在运行之后将该进程的行程值增加一个步长。

总结：

彩票调度有一个步长调度没有的优势——不需要全局状态

这两种比例份额调度没有作为 CPU 调度程序被广泛使用。一个原因是这两种方式都不能很好地适合 I/O ，且比例份额不好确定

虚拟内存（VM）系统的一个主要目标:

malloc()调用

传入要申请的堆空间的大小，它成功就返回一个指向新申请空间的指针，失败就返回 NULL

free()调用

要释放不再使用的堆内存，程序员只需调用 free() 两者使用时容易出错，注意判断

内部碎片/内零头（internal fragmentation）已经分配的内存单元内部的未被利用的空间/分配给作业的存储空间（内存）中未被利用的部分

外部碎片/外零头（external fragmentation）系统中无法利用的小存储块

如何管理？

void free(void *ptr)函数接受一个指针，释放对应的内存块。在释放空间时，用户不需告知库这块空间的大小。因此，在只传入一个指针的情况下，库（库管理的空间称为堆）必须能够弄清楚这块内存的大小。 空闲列表（free list）

其需要具备分割与合并的功能：

已分配空间追踪

大多数分配程序考虑在分配的空闲块之前加一个信息头（header），用于保存分配空间的大小

magic提供完整性检查以及一些信息。

free时实际释放的空间是头块大小加上分配的空间大小

嵌入空闲列表

在内存分配库中，需要在空闲空间本身建立空闲空间列表P123

一些空闲空间管理的妙妙方式：

最优匹配：

遍历，找和请求的大小相近的 较高性能代价

最差匹配：

遍历，找最大的空闲块 会导致过量的外部碎片，高开销

首次匹配：

找第一个足够大的块 速度快，但容易让空闲列表头部有很多小块 需要合理管理列表顺序

下次匹配：

多维护一个指针，指向上一次查找的位置，将对空闲列表的查找扩散到整个列表 优化的首次匹配

分离空闲列表：

如果某个应用程序经常申请一种（或几种）大小的内存空间，那就用一个独立的列表，只管理这样大小的对象。通过拿出一部分内存专门满足某种大小的请求，碎片就不再是问题了。而且，由于没有复杂的列表查找过程，这种特定大小的内存分配和释放都很快。

提高了复杂度

伙伴系统：

释放时：查找伙伴（邻居节点）是否空闲，空闲时合并并向上递归查询，

重定位的进程使用了相同大小的物理内存，但由于该进程的栈区和堆区并不很大，导致这块内存区域中大量的空间被浪费。这种浪费通常称为内部碎片/内零头（internal fragmentation）

隐式方式中：硬件通过地址产生的方式来确定段。例如，如果地址由程序计数器产生（即它是指令获取），那么地址在代码段。如果基于栈或基址指针，它一定在栈段。其他地址则在堆段。

由于栈是先低地址方向生长，对其的引用有所不同：偏移量当成有符号数 偏移量的最高位表示是否反向增长。

操作系统做什么：

新问题，段模式会使得内存中出现很多未分配的小块，这些小块无法分配给新的段也影响了已有段的扩大，成为了外部碎片/外零头（external fragmentation）

ppt有一些错误判断

将一个进程的地址空间分割成固定大小的单元（页）

把物理内存看成定长槽块的阵列，称为页帧 ，每个页帧包含一个虚拟内存页

地址转化举例：

虚拟地址的两大部分：虚拟页面号（virtual page number，VPN）和页内的偏移量（offset）

通过虚拟页号VPN，可以检索页表，找到虚拟页所在的物理页面。

物理帧号（PFN）（有时也称为物理页号，physical page number 或 PPN）

页表中的页表项（page table entry)存什么？

以线性页表为例，需要存储期望的物理帧号PFN。还有一些位：

目前的分页模式太慢了，会导致机器变慢（有许多额外的内存访问来访问页表）和内存浪费（内存被页表塞满而不是有用的应用程序数据）。

地址转换旁路缓冲存储器（translation-lookasidebuffer，TLB）：是频繁发生的虚拟到物理地址转换的硬件缓存（cache）。因此，更好的名称应该是地址转换缓存（address-translation cache）。

TLB是MMU的一部分，TLB 处理器核心附近，设计的访问速度很快。

硬件缓存，无论是指令、数据还是地址转换（如 TLB），都利用了局部性（时间与空间），在小而快的芯片内存储器中保存一份内存副本。

TLB 这样的缓存这么好，为什么不做更大的缓存，装下所有的数据？

如何处理TLB未命中？ 硬件处理（复杂指令集计算机，CISC)：

硬件必须知道页表在内存中的确切位置（通过页表基址寄存器，page-table base register），以及页表的确切格式。发生未命中时，硬件会“遍历”页表，找到正确的页表项，取出想要的转换映射，用它更新 TLB，并重试该指令。

软件处理（精简指令集计算机，RISC):

TLB 未命中时，硬件系统会抛出一个异常,暂停当前的指令流，将特权级提升至内核模式，跳转至陷阱处理程序（trap handler），这个陷阱处理程序是操作系统的一段代码，用于处理 TLB 未命中。

这段代码在运行时，会查找页表中的转换映射，然后用特别的“特权”指令更新 TLB，并从陷阱返回。此时，硬件会重试该指令（导致 TLB 命中）。

TLB 的内容：VPN ｜ PFN ｜ 其他位

TLB 的有效位!=页表的有效位 →一个页表项（PTE）被标记为无效，就意味着该页并没有被进程申请使用，正常运行的程序不应该访问该地址；TLB 的有效位，只是指出 TLB 项是不是有效的地址映射。

地址空间标识符（Address Space Identifier，ASID）：可以把ASID 看作是进程标识符（Process Identifier，PID），但通常比 PID 位数少（PID 一般 32 位，ASID 一般是 8 位）。

全局位G,一致性位C,脏位D,有效位V

只有19位VPN? →事实上，用户地址只占地址空间的一半（剩下的留给内核）

TLB满了需要替换时：采用最少使用替换（least-recently-used，LRU）或随机替换

方案一：使用更大的页 →大内存页会导致每页内的浪费，内部碎片

方案二：分页与分段混用

为每个逻辑分段提供一个页表（段内页表）。

基址寄存器保存该段的页表的物理地址，界限寄存器用于指示页表的结尾（即它有多少有效页）。

→它仍然要求使用分段(它假定地址空间有一定的使用模式),如果有一个大而稀疏的堆，仍然可能导致大量的页表浪费；外部碎片再次出现

方案三：多级页表 时空的折中

留出页目录，页目录中有多个页目录项（Page Directory Entries，PDE）组成。PDE（至少）拥有有效位（valid bit）和页帧号（page frame number，PFN），类似于页表项PTE。

PDE的有效位如果为1，则意味着该项指向的页表（通过 PFN）中至少有一页是有效的，即在该 PDE 所指向的页中，至少一个 PTE，其有效位被设置为 1。（如果整页的页表项（PTE）无效，就完全不分配该页的页表） 如果 PDE 项无效（即等于零），则 PDE的其余部分没有定义

页目录应该占一个页的大小（页表的每个部分都可以整齐地放入一页中），指向的低级页表也是；页目录大小=页的大小/PTE的大小

→多级页表是有成本的。在 TLB 未命中时，需要从内存加载多次，才能从页表中获取正确的地址转换信息；另一个明显的缺点是复杂性。

方案四：反向页表 极端的空间节省

只保留一个页表，每一项代表一个物理页

页表项内容为：PID+页号（哪个进程在使用该页与哪个虚拟页映射到此页）

方案五：将页表交换到磁盘

我们需要支持更大的地址空间 → 硬盘

在硬盘上开辟一部分空间（交换空间）用于物理页的移入与移出

虚拟存储器：虚拟存储指仅把作业的一部分装入内存便可运行的存储管理系统，通过作业各部分的动态调入和置换，用户所感觉的存储空间比实际空间大，称之为虚空间。

页表PTE的存在位用来指示该页是否在物理内存中

页错误：访问不在物理内存中的页

页错误发生后，操作系统接过控制权，操作系统通过PTE得到硬盘地址，将页读取到内存中 PTE的PFN位用来存储硬盘地址（当该页不在物理内存而是在磁盘中时）

到目前，TLB未命中的情况如下：

什么时候发生交换？

操作系统倾向主动留一小部分空闲空间，高水位线（HW）与低水位线（LW），当少于LW个页可用时，后台专门的程序（交换守护进程）开始释放内存，直到有HW个可用物理页

方案一：最优替换策略

剔除在未来最远才将访问的页，这是面向未来的算法，无法实现，可作为对照

方案二：FIFO

先入先出，简单，但无法确定页的重要性

方案三：随机

基本同方案二，命中率看运气

方案四：利用历史数据 “最不经常使用”（Least-Frequently-Used，LFU）—>从频率上，替换使用次数最少的 “最少最近使用”（Least-Recently-Used，LRU）—>从时间上，替换最久未被访问的

优先保留最近加入的和最近使用的，利用局部性原理（频率（frequency）：如果一个页被访问了很多次，也许它不应该被替换，因为它显然更有价值；页更常用的属性是访问的近期性（recency），越近被访问过的页，也许再次访问的可能性也就越大。）

抖动（Thrashing）是操作系统中的一种现象，发生在计算机的物理内存（RAM）被过度使用时，导致系统花费大部分时间在交换页面（从内存到硬盘和从硬盘到内存的过程）上，而非执行实际的应用程序或进程。

引入线程后存在线程间的竞争 —> 原子操作（多个操作要么都执行或都不执行） 要求硬件提供指令→ synchronization primitives（同步原语）

进程同步指两个以上进程基于某个条件来协调它们的活动

锁变量（简称锁）保存了锁在某一时刻的状态。它要么是可用的 （available， unlocked， free），表示没有线程持有锁，要么是被占用的（acquired， locked， held），表示有一个线程持有锁，正处于临界区。

POSIX 库将锁称为互斥量（mutex），因为它被用来提供线程之间的互斥。即当一个线程在临界区，它能够阻止其他线程进入直到本线程离开临界区。 使用时需要初始化；获取与释放时检查错误代码

通常大家会用不同的锁保护不同的数据和结构，从而允许更多的线程进入临界区（细粒度的方案）

评价锁：

单标志算法

双标志、先检查算法

双标志、后检查算法

Peterson算法

让turn表示谁应该等着，turn不可能同时为1，解决了相互谦让的饥饿

面包店算法（Bakery Algorithm） （n个进程）

为什么两个不同的进程可能会取得相同的ticket?是否可以去掉choosing数组？

中断问题

不合时宜的中断容易构造出两个线程都将标志设置为 1，都能进入临界区的场景。

最早提供的互斥解决方案之一，就是在临界区关闭中断。这个解决方案是为单处理器系统开发的。没有中断，线程可以确信它的代码会继续执行下去，不会被其他线程干扰。（但是带来了恶意程序 不支持多处理器 中断丢失等问题） 某些情况下操作系统本身会采用屏蔽中断的方式，保证访问自己数据结构的原子性，或至少避免某 些复杂的中断处理情况。因为在操作系统内部不存在信任问题，它总是信任自己可以执行特权操作

以下四个都是指令

Test-And-Set（测试并设置，原子交换）

自旋锁（spin lock）：这是最简单的一种锁，一直自旋，利用 CPU 周期，直到锁可用。在单处理器上，需要抢占式的调度器（preemptivescheduler，即不断通过时钟中断一个线程，运行其他线程）。否则，自旋锁在单 CPU 上无法使用，因为一个自旋的线程永远不会放弃 CPU。

自旋锁一次只允许一个线程进入临界区。因此，这是正确的锁。 自旋锁没有公平性，可能会导致饿死。 在单 CPU 的情况下，性能开销相当大； 多CPU 上，自旋锁性能不错（如果线程数大致等于 CPU 数）

Compare-And-Swap

是检测 ptr 指向的值是否和 expected 相等；如果是，更新 ptr 所指的值为新值。否则，什么也不做。不论哪种情况，都返回该内存地址的实际值

Load-Linked and Store-Conditional（LL/SC) 链接的加载和条件式存储指令

Fetch-And-Add

yield 的方法

考虑许多线程（例如 100 个）反复竞争一把锁的情况。在这种情况下，一个线程持有锁，在释放锁之前被抢占，其他 99 个线程分别调用 lock()，发现锁被抢占，然后让出 CPU。假定采用某种轮转调度程序，这 99 个线程会一直处于运行—让出这种模式，直到持有锁的线程再次运行。虽然比原来的浪费 99 个时间片的自旋方案要好，但这种方法仍然成本很高，上下文切换的成本是实实在在的，因此浪费很大。

休眠队列

显式地施加某种控制，决定锁释放时，谁能抢到锁。

park调用之前，线程被切换，另一个拥有锁的线程执行（随后释放了锁），这时被切换出去的线程随后park时，可能会永久睡眠（因为没有线程从临界区出来后执行unlock中的unpark）

二阶段锁

两阶段锁意识到自旋可能很有用，尤其是在很快就要释放锁的场景。 阶段锁的第一阶段会先自旋一段时间，希望它可以获取锁。 但是，如果第一个自旋阶段没有获得锁第二阶段调用者会睡眠，直到锁可用。

在很多情况下，线程需要检查某一条件（condition）满足之后，才会继续运行。例如，父线程需要检查子线程是否执行完毕 [这常被称为 join()]。这种等待可以通过条件变量实现。

条件变量是一个显式队列，当某些执行状态（即条件，condition）不满足时，线程可以把自己加入队列，等待（waiting）该条件。另外某个线程，当它改变了上述状态时，就可以唤醒一个或者多个等待线程（通过在该条件上发信号），让它们继续执行。

条件变量是用来等待而不是用来上锁的。条件变量用来自动阻塞一个线程，直到某特殊情况发生为止。通常条件变量和互斥锁同时使用。

pthread_cond_t c; 创建一个条件变量 pthread_cond_wait:将释放锁并将调用线程置于睡眠状态。等待其他线程向它发出信号 pthread_cond_signal:解除阻塞条件变量上阻塞的至少一个线程。被唤醒的线程重新持有锁

快速总结：

用while而不是if 防止虚假唤醒 生产者与消费者用不同的条件变量：使用一个条件变量时→可能生产者（缓冲已满时）唤醒生产者，消费者（缓冲区以空时）唤醒消费者 外层的for循环是生产者线程生产loops次，消费者线程消费loops次。

考虑多个消费者要消费不同的量，有些消费者可能被唤醒但是无法消费（内存分配，未达到需求） →使用pthread_cond_broadcast() （广播）代替上述代码中的pthread_cond_signal()，唤醒所有的等待线程。

它能覆盖所有需要唤醒线程的场景（保守策略）。成本是太多线程被唤醒，

信号量的数据结构：

P和V操作原语定义：

父进程wait，子进程post，初值为0

P.V操作必须成对出现，有一个P操作就一定有一个V操作

当为互斥操作时，它们同处于同一进程 当为同步操作时，则不在同一进程中出现

如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要,一个同步P操作与一个互斥P操作在一起时，同步P操作在互斥P操作前，（避免死锁，循环等待）两个V操作顺序无关紧要

制约条件分析：

1、允许多个进程同时读文件（读－读允许）；

2、不允许在进程读文件时让另外一进程去写文件；有进程在写文件时不让另外一个进程去读该文件（“读-写”互斥）；

3、不允许多个写进程同时写同一文件（“写-写”互斥）。 读者优先：容易导致写者饥饿

写者优先

公平竞争

这里的p操作先比较减减

违反原子性（atomicity violation）缺陷

解决方法：加锁

错误顺序（order violation）缺陷

解决方式：通过强制顺序来修复这种缺陷。正如之前详细讨论的，条件变量（condition variables）就是一种简单可靠的方式，

发生条件：

预防方式：

循环等待：

获取锁时提供一个全序（total ordering）。假如系统共有两个锁（L1 和 L2）， 那么我们每次都先申请 L1 然后申请 L2，就可以避免死锁。这样严格的顺序避免了循环等待

持有并等待：

非抢占：

trylock()函数会尝试获得锁，或者返回−1，表示锁已经被占有。你可以稍后重试 一下

互斥：

通过强大的硬件指令，构造出不需要锁的数据结构.

通过调度来避免死锁：

检验并恢复：

允许死锁偶尔发生，检查到死锁时再采取行动。 → 重启

当进程申请一个有效的资源的时候，系统必须确定分配后是安全的。 如果存在一个安全序列，系统处于安全态。 对于进程序列< P1, P2, …, Pn >，如果每个Pi 对资源的请求都能够由当前有效地资源加上Pj（j < i）释放的资源来满足，那么这个序列是安全的。在这种情形下，如果Pi 的资源需求不能够立即得到满足，那么它可以等到Pj 结束。当它们结束时，Pi 可以获得所需的全部资源，完成指定的工作，返回获取的资源并结束运行。

（1)如果Request[i]≤Need[i]，跳到第2步，否则出错； （2)如果Request[i]≤Available，跳到第3步,否则挂起进程等待； （3)根据进程的资源请求,先把资源试探性分配给它。 （4)执行安全性检查算法，如果安全状态则承认试分配，否则抛弃试分配，进程Pi等待。 （5)假定系统当前满足申请条件：则按以下方式修改状态 Available= Available- Request[i]; Allocation[i]= Allocation[i]+Request[i]; Need[i]=Need[i]-Request[i];

大概就是分配一下,检查一下，检查不安全就不这样分配，等着

进程很难在运行前知道其所需资源的最大值。 系统中各进程之间必须是无关的，即没有同步要求，无法处理有同步关系的进程。 进程的数量和资源的数目是固定不变的，无法处理进程数量和资源数目动态变化的情况。

一个简化的标准设备：

一个（简化的）设备接口包含 3 个寄存器：一个状态（status）寄存器， 可以读取并查看设备的当前状态；一个命令（command）寄存器，用于通知设备执行某个具 体任务；一个数据（data）寄存器，将数据传给设备或从设备接收数据。通过读写这些寄存 器，操作系统可以控制设备的行为

第 1 步，操作系统通过反复读取状态寄存器，等待设备进入可以接收命令的就绪状态。我们称之为轮询（polling）设备（基本上，就是问它正在做什么）。 第 2 步，操作系统下发数据到数据寄存器。例如，你可以想象如果这是一个磁盘，需要多次写入操作，将一个磁盘块（比如 4KB）传递给设备。如果主 CPU 参与数据移动（就像这个示例协议一样），我们就称之为编程的 I/O(programmed I/O，PIO)。 第 3 步，操作系统将命令写入命令寄存器；这样设备就知道数据已经准备好了，它应该开始执行命令。最后一步， 操作系统再次通过不断轮询设备，等待并判断设备是否执行完成命令（有可能得到一个指示成功或失败的错误码）

轮询简单但是浪费了cpu 中断有效利用了CPU但浪费了时间和算力 如果设备的速度未知，或者时快时慢，可以考虑混合（hybrid）策略，先尝试轮询一小段时间，如果设备没 有完成操作，此时再使用中断。 →DMA(Direct Memory Access)可以协调完成内存和设备间的数据传递，不需要 CPU 介入。

通过了解“数据在内存中的位置，要复制多少数据”在内存中复制数据。完成后，DMA引发中断，I/O开始在磁盘上进行。

设备交互：直接IO指令与内存映射指令

文件系统（包括在其之上的应用程序）完全不清楚它使用的是什么类型的磁盘。它只需要简单地向通用块设备层发送读写请求即可，块设备层会将这些请求发送给对应的设备驱动，然后设备驱动来完成真正的底层操作。

驱动器由大量扇区（512 字节块）组成，每个扇区都可以读取或写入。在具有 n 个扇区的磁盘 上，扇区从 0 到 n−1 编号。因此，我们可以将磁盘视为一组扇区，0 到 n−1 是驱动器的地址空间（address space）。 许多文件系统一次读取或写入 4KB（或更多数据）。但是， 在更新磁盘时，驱动器制造商唯一保证的是单个 512 字节的写入是原子的（atomic，即它将完整地完成或者根本不会完成）。

磁道的编号是按从内向外的顺序进行的，通常从0开始。

寻道时间与转速无关

在写入时，驱动器面临选择：回写（write back，在数据更新时只写入缓存Cache。只在数据被替换出缓存时，被修改的缓存数据才会被写到后端存储）和透写（write through，在数据更新时，同时写入缓存Cache和后端存储）。

寻道延迟+旋转延迟+传输延迟

随机（random）工作负载，它向磁盘上的随机位置发出小的（例如 4KB） 读取请求。随机工作负载在许多重要的应用程序中很常见，包括数据库管理系统。 顺序（sequential）工作负载，只是从磁盘连续读取大量的扇区，不会跳过。

IO计算 随机工作负载:向磁盘上的随机位置发出4KB的读取，

顺序工作负载:从磁盘连续读取100MB（这里的4KB和100MB即下文的传输大小size）

对于随机工作负载在 Cheetah 上：

平均寻道时间（4ms）就采用制造商报告的平均时间。请注意，完全寻道（从表面的一端到另一端）可能需要两到三倍的时间。 平均旋转延迟直接根据 RPM 计算。15000 RPM 等于 250 RPS（每秒转速）。因此，每次旋转需要 4ms。平均而言，磁盘将会遇到半圈旋转，因此平均时间为 2ms。 传输时间就是传输大小size除以峰值传输速率。4KB/125MB=32μs

我感觉计算结果有点小问题，但是思路看懂了，可能是我算的时候省略了μs级

按柱面组织数据：寻道时间占平均块访问时间的一半，如果我们选择在一个柱面上连续的读取所有块，那么我们只需要考虑一次寻道时间，而忽略其它时间。这样，从磁盘上读写数据的速度就接近于理论上的传输速率。 使用多个磁盘：如果我们使用多个磁盘来替代一个磁盘，只要磁盘控制器、总线和内存能以 n 倍速率处理数据传输，则使用 n 个磁盘的效果近似于 1 个磁盘执行了 n 次操作。因此使用多个磁盘可以提高系统的性能。 磁盘调度：提高磁盘系统吞吐率的另一个有效方法是让磁盘控制器在若干个请求中选择一个来首先执行。 预取数据：在一些应用中，我们是可以预测从磁盘请求块的顺序的。因此我们就可以在需要这些块之前就将它们装入主存。

SCAN电梯调度（双向的电梯） 当到达另一端时，磁头改变移动方向

LOOK：磁头只移动到一个方向上最远的请求为止。接着，它马上回头，而不是继续到磁盘的尽头。

在这里就是scan但是不到0，14之后直接去65

C-SCAN(单向/循环扫描算法）

当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少。这是由于这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求等待的时间较长。

C-LOOK：磁头只移动到一个方向上最远的请求为止。接着，它马上回头，而不是继续到磁盘的尽头。

同时使用多个磁盘来构建更快、更大、更可靠的磁盘系统。 对于主机系统来说，RAID就像一个大磁盘（RAID提供接口）

性能和容量:并行使用多个磁盘 可靠性:RAID可以容忍一个磁盘的丢失。

RAID内部包括： 一个微控制器，运行固件以指导 RAID 的操作。 包括 DRAM 这样的易失性存储器，在读取和写入时缓冲数据块。 在某些情况下，还包括非易失性存储器，安全地缓冲写入可能包含专用的逻辑电路，来执行奇偶校验计算。

RAID性能分析：

假设磁盘可以在连续工作负载下以 S MB/s 传输数据，并且在随机工作负载下以 R MB/s 传输数据。一般来说，S 比 R 大得多。 举例：平均大小为 10MB 的连续传输，平均为 10KB 的随机传输 平均寻道时间 7ms ，平均旋转延迟 3ms ，磁盘传输速率 50MB/s

可以选择大块大小，在一个磁盘上方n个块，然后再移动到下一个磁盘

较小的大块意味着许多文件将跨多个磁盘进行条带化，增加了对单个文件的读取和写入的并行性。但是，跨多个磁盘访问块的定位时间会增加，因为整个请求的定位时间由所有驱动器上请求的最大定位时间决定 较大的大块大小减少了这种文件内的并行性，因此依靠多个并发请求来实现高吞吐量。但是，较大的大块大小减少了定位时间 性能分析：

容量：完美。 ·分条可提供相当于N个磁盘的可用容量。 条带化：性能优异。 ·所有磁盘通常是并行使用的。 可靠性：差。 ·任何硬盘故障都会导致数据丢失。

稳态吞吐量：吞吐量等于N乘以S(N·SMB/S)。对于大量的随机l/ O，我们可以再次使用所有磁盘，从而获得N·RMB/s

对于 N 个磁盘，镜像的有用容量为 N/2。

读取块时，RAID 有一个选择：它可以读取任一副本。 写入块时，RAID 必须更新两个副本的数据，以保持可靠性。

顺序读取时：(N/2) · S MB/s

顺序写入时，每个逻辑写入必定导致两个物理写入，镜像阵列期间读获得的最大带宽是 (N/2) · S MB/s ，即峰值带宽的一半。也就是说连续写入时，无法并行。

随机读取是镜像 RAID 的最佳案例。在这种情况下，我们可以在所有磁盘上分配读取数据，从而获得完整的可用带宽。因此，对于随机读取，RAID-1 提供 N·R MB/s。 随机写入时，每个逻辑写入必须变成两个物理写入，因此在所有磁盘都将被使用的情况下，客户只会看到可用带宽的一半，因此随机写入的性能: (N/2) ·R MB/s.

异或，奇数的1时，结果为1；在数据块的每一位上执行按位 XOR。

容量：Disk n专门方校验码，所以容量为N-1

可靠性：RAID-4只允许出现一个磁盘故障。如果不止一个磁盘丢失，没有办法重建丢失的数据。

连续读取：可以利用除奇偶校验磁盘以外的所有磁盘，因此可提供（N−1）·S MB/s

顺序写入：将大块数据写入磁盘时，RAID-4 可执行简单优化，称为全条带写入（full-stripe write）：大块数据写入磁盘时（N−1）·S MB/s

随机读取：一组 1 块的随机读取将分布在系统的数据磁盘上，而不是奇偶校验磁盘上。因此，有效性能是：（N−1）·R MB/s。 随机写入，在写入数据的同时必须更新奇偶校验值 第一种称为加法奇偶校验（additive parity）

为了计算新奇偶校验块的值，并行读取条带中所有其他数据块并与新块（刚写入的）进行异或。结果是新的校验块。以将新数据和新奇偶校验写入其各自的磁盘，也是并行写入。 在较大的 RAID 中，需要大量的读取来计算奇偶校验。

第二种减法奇偶校验（subtractive parity）方法

使用减法方法。对于每次写入，RAID 必须执行 4 次 物理 I/O（两次读取和两次写入）。 读旧值和旧校验值，写入新值与新校验值 在一个随机写的时候，数据盘和校验盘可以并行读和写，先读再写，所以是R/2

对与小写入时，奇偶校验成为瓶颈

在这个图中要更新4和13，可以对disk0和disk1进行并行访问，但是不能对disk4进行并行访问 问题在于：可以并行访问数据磁盘，奇偶校验磁盘也不会实现任何并行

RAID-4 中的 I/O 延迟

单次读取（假设没有失败）只映射到单个磁盘，因此其延迟等同于单个磁盘请求的延迟。 单次写入：需要两次读取， 然后两次写入,读操作可以并行进行，写操作也是如此→总延迟大约是单个磁盘的两倍。（有一些差异，因为我们必须等待两个读取操作完成，所以会得到最差的定位时间，但是之后，更新不会导致寻道成本，因此可能是比平均水平更好的定位成本。）

在4的基础上，块驱动器旋转奇偶校验块：消除了奇偶校验瓶颈

容量依旧是N-1，但是只允许一个磁盘出错

对于顺序读写：（N-1)*S 和Raid4一致 随机读取：比4要好一点，可以利用所有磁盘：N*R

随机写入： RAID-4 的随机写入性 能明显提高。想象一下写入块 1 和写入块 10，这将变成对磁盘 1 和磁盘 4（对于块 1 及其奇偶校验）的请求以及对磁盘 0 和磁盘 2（对于块 10 及 其奇偶校验）的请求。因此，它们可以并行进行。事实上，我们通常可以假设，如果有大量的随机请求，我们将能够保持所有磁盘均匀忙碌。如果是这样的话，那么我们用于小写入的总带宽将是 N/4 *R MB/s。4 倍损失是由于每个 RAID-5 写入仍然产生总计4个 I/O 操作

存储虚拟化中的两个关键抽象

File:文件就是一个线性字节数组，每个字节都可以读取或写入 ．每个文件都有低级名称作为inode号 ．用户不知道这个名称。 Directory:目录通常是一个列表，列表中每个条目(用户可读名字，inode)，每个条目是一个文件或其他目录的入口，例如目录有一个条目(“foo”, “10”)

fsync()以确保立即强制写入磁盘

重命名

stat fstat用于显示元数据

rm调用unlink()进行文件删除

mkdir()：创建目录

rmdir()：删除目录，只允许用来删除空目录，安全

link(old pathname, new one)

将新文件名链接到旧文件名 创建另一种方式来引用同一个文件。 命令行链接程序:ln

在创建文件的硬链接之后，在文件系统中，原有文件名（file）和新创建的文件名（file2） 之间没有区别。实际上，它们都只是指向文件底层元数据的链接

当文件系统取消链接文件时，它检查 inode 号中的引用计数（reference count）。该引用计数（有时称为链接计数，link count）允许文件系统跟踪有多少不同的文件 名已链接到这个 inode。

调用 unlink()时，会删除可读的名称（正在删除的文件）与给定 inode 号之间的“链接”，并减少引用计数。只有当引用计数达到零时，文件系统才会释放 inode 和相关数据块，从而真正“删除”该文件。

·符号链接比硬链接更有用。 ·硬链接无法创建目录(为了防止出现环) ·硬链接不能创建文件到其他分区。 因为inode号只在一个文件系统内是唯一的。ln -s filename

符号链接本身实际上是一个不同类型的文件。(软链接文件类似于Windows的快捷方式)

在软连接中，文件实际上是一个文本文件，其中包含的有另一文件的位置信息

符号链接保存被链接文件的路径名作为链接文件的数据。

悬空引用（Dangling reference）：删除原始文件后，符号链接指向不存在的路径名

没看懂

运行mount

连续分配

存在的问题

为新文件找空间比较困难（类似于内存分配中的连续内存分配方式）；文件很难增长

基于扩展的连续分配

该方法开始分配一块连续空间，当空间不够时，另一块被称为扩展的连续空间会添加到原来的分配中。文件块的位置就成为开始地址、块数、加上一个指向下一扩展的指针。

链接分配

优点：

.简单 － 只需起始位置

.文件创建与增长容易

缺点：

.不能随机访问

.块与块之间的链接指针需要占用空间(簇：将多个连续块组成簇，磁盘以簇为单位进行分配)

.存在可靠性问题

把FAT提前放到内存里

索引分配

优点: ·保持了链接结构的优点，又解决了其缺点: .即能顺序存取，又能随机存取 ·满足了文件动态增长、插入删除的要求 ·能充分利用外存空间,无外部碎片 缺点: 索引表本身带来了系统开销 ·如:内外存空间，存取时间

这里-3减去的是三个间接指针（一次。二次。三次）

后面好杂不想记了

最后还是得看ppt例题