资源描述
第一章：引论操作系统是运行在内核态的软件，为程序猿提供资源集抽象以及管理硬件主要任务：记录那个程序在用什么资源，管理资源分配，评估使用代价，调节冲突1.操作系统必须知道所有的寄存器，以便中断时保存进度2.用户程序在用户态运行时，仅允许执行至灵级的一个子集，一般不能调用IO和内存保护指令3.陷阱：a. 用于执行系统调用b. 多数由硬件引起，用于警告异常4.超线程：无并行处理，线程切换纳秒级存储器1. 寄存器（和CPU一样快）-高速缓存（多级缓存）-主存（RAM ROM EEROM 闪存）上下文切换：多道程序系统中从一个程序切换到另一个程序1.3.51. 设备驱动程序：控制IO设备，与控制器对话并收发命令2. 设备存储器：映射到操作空间A优点：不需要特定IO指令B缺点：占地址空间（8088）3. 实现输入输出的方法：A 忙等待：设备驱动循环检查IOB 操作完成时中断C 使用特殊的直接存储器访问芯片DMA1. USB：通用串行总线，键盘鼠标等慢速设备启动1. 加电-BIOS检查硬件-BIOS查询启动设备（设备第一扇区用启动签名才可以作为启动设备）-硬盘第一区（MBR），分区表，超级块等进程1. 本质：正在执行的程序的实例，地址空间（core image 进程可读写，有数据和堆栈）。2. 相关：资源集（寄存器，报警，文件清单等）3. 容许运行一个程序所需要所有信息的容器4. UID与GID1. IO设备的分类：A块设备：硬盘，可随机读取B字符特殊文件：键盘鼠标2管道：虚文件，连接进程1.6系统调用1. 用户程序与操作系统交互：处理抽象2. 能进入内核的过程调用用户态切换到核心态三种方法：中断，异常，系统调用3.TRAP指令：副作用切换到内核态微内核1. 高可靠性，把操作系统划分成小的，定义良好的模块，只有微内核运行在内核，其他是普通用户程序2. 设备驱动：崩溃不会导致系统死机3. 机制与策略分离第二章：进程与线程2.1进程模型1. 多道程序设计：CPU在多个程序之间快速切换2. UNIX: 开始是相同，之后不同。Windows：一直不同。3. 进程退出的原因：1. 正常退出；2. 出错退出；（异常处理）3. 严重错误；（非法指令，引用错误内存，除零错误）4. 被杀死4. 进程层次Windows: 没有层次的概念，所有进程地位相同Linux：进程及进程的子女们组成进程组5. 进程的三种状态：1. 运行态（实际占用CPU）2. 就绪态（可运行）3. 阻塞态（等待外部事件）6. 进程表：储存进程状态（程序计数器，堆栈指针，内存分配状况，打开的文件状态。账号等）7. 中断向量：与每一个IO类关联1. 中断发生时，中断硬件程序将进程表中的重要数据压入堆栈，计算机跳到中断向量的地址2. 汇编语言设置新的堆栈（无法用C语言这类高级语言来描述）8. 多道程序设计1. 假设一个进程等待IO与停留在CPU的时间比为p，n个进程时，CPU使用率为使用率 = 1 pn2.2线程（ 进程与线程）1. 定义：传统操作系统中，每个进程有一个地址空间和一个控制线程2. 线程将应用程序分解成可以并行运行的多个顺序线程3. 使用多线程的原因：1. 并行实体共享同一个地址空间和所有可用数据的能力2. 线程更轻量级，所以他们比进程更快创建和撤销3. 同时需要大量IO和CPU计算时，多线程允许多个活动彼此重叠进行，从而加快执行速度4. 多核系统中，多线程可以真正实现并行5. 例子：多线程/单线程web服务器1. 第三种设计（有限状态机： 并行，非阻塞系统调用，【中断】）：唯一的线程对请求进行考察，如果需要IO，则启动一个非阻塞IO，服务器在表格里记录当前请求，然后处理下一个事项。6. 线程模型1. 进程：集中程序运行的相关资源（地址空间，全局变量等）2. 线程：程序计数器，寄存器，堆栈，共享的地址空间，多个线程的执行能力。7. 线程之间没有保护：1. 不可能2. 不需要（线程之间是合作关系）8. 每个线程都有自己的堆栈9. thread_yield：不同于进程，线程无法使用时钟中断强制线程让出CPU10. 线程引入的问题1. fork系统调用是否应该复制子线程2.共享文件冲突4 线程实现1. 用户空间实现1每个进程需要有其专门的线程表，由运行时系统管理2. 优点1. 可以在不支持线程的操作系统上实现多线程2. 线程切换速度快（调用运行时系统的过程，不需要刷新和上下文切换）3. 允许每个进程有自己定制的调度算法4. 有较好的拓展性（内核线程需要固定的表格空间和堆栈空间）3. 缺点1. 某个线程进行阻塞调用会引起所有其他线程阻塞1. 使用非阻塞系统调用2. 阻塞提前通知（select系统调用）2. 页面故障阻塞其他线程3. 除非线程放弃CPU，否则其他线程（包括调度线程）无法运行（没有时钟中断）1. 运行时系统也给与时钟中断：不好，不可能而且开销大2. 内核线程1. 内核有记录所有线程的线程表2. 使用环保方法回收线程3. 在线程级别使用调度算法：如果线程的操作比较多，会带来很大的开销4. 信号：是发给进程的。当多个线程注册时，会出问题3. 混合实现1. 使用内核级线程，将用户级线程与某些或全部内核线程多路复用（很灵活） 4. 调度机制1. 内核给每个进程安排一定数量的虚拟处理器并且让运行时系统分到线程上2. 进程被阻塞后，内核通知运行时系统（upcall）3. 根据中断决定是否继续5. 弹出式线程1. 一个消息的到达导致系统创造新的线程处理消息-弹出式线程2. 优点：没有历史，创建迅速6. 重写单线程代码1. 私有的全局变量2. 可重入的库1. 重写整个库2. 为每个过程提供wrapper，标志该库正在被使用中3. 信号：内核不知道用户级线程，因此不容易将信号发给正确的线程4. 堆栈管理：内核不了解线程，无法自动增长，可能会造成线程堆栈出错。2.3 进程间通信1. 三个基础问题1. 进程如何把信息传递给另一个2. 确保两个或多个进程在关键活动中不会交叉3. 进程执行的正确顺序2. 竞争条件：两个或多个进程读写共享数据，最后结果取决于进程执行的精确时序。3. 临界区：多个进程中访问共享区域的程序段1. 互斥：不能同时多个进程使用共享变量或者文件2. 临界区解决方案四个条件1. 任何两个进程不能同时处于临界区2. 不应对CPU的数量和速度有任何的假设3. 临界区外的程序不应阻塞其他程序4. 不能使程序无限期等待进入临界区3. 解决方案（基于忙等待：进程如不能进入互斥区，则会一直原地等待）缺点：1. 可能导致优先级反转问题2. 浪费CPU3. 用户级线程会一直忙等待，从而没用办法让拥有锁的线程运行1. 屏蔽中断：进程进入临界区之后屏蔽所有中断（CPU不会切换）评价：不好的方案1. 不能把屏蔽中断的权力交给用户进程（不打开中断则系统会终止）2. 多处理器时不能解决互斥2. 锁变量：共享锁，程序在进入临界区之前检查锁的值评价：无法解决临界区问题3. 严格轮换法评价：1. 可以解决，但为忙等待。只有有理由认为等待时间很短的情况下才使用忙等待（锁被称为自旋锁）2 在一个进程比另一个进程慢很多的情况下，不好（违反条件三）4. Peterson解法评价：可以解决，满足四大条件5. TSL指令（硬件解法）TSL RX LOCK：测试并加锁，把LOCK值读到RX并在LOCK上存入1。原子操作可以阻止所有处理器访问LOCK（屏蔽中断只能屏蔽本地处理器）4 睡眠唤醒方案（进程无法进入临界区时会阻塞）1. 原语：生产者消费者问题：一个发给未睡眠进程的信号丢失了2. 解决方案1. 唤醒等待位：唤醒时生产者置1，消费者睡眠前检查该位，若为1，则清除该位并继续保持清醒（不好，多进程时需多个等待位）2. 信号量（semaphore）：检查数值，修改变量等应为原子操作1. 在进入一个关键代码段之前，线程必须获取一个信号量；一旦该关键代码段完成了，那么该线程必须释放信号量。其它想进入该关键代码段的线程必须等待直到第一个线程释放信号量。2实现方法：操作系统在执行以上事务时屏蔽中断3. 另一种用途：互斥锁3. 互斥锁：只需要一个二进制位与忙等待差异：在未获得锁时，调用另外的线程4. 如何共享锁？a) 共享数据结构可以存放在内核并且只能用系统调用访问b) 让进程与其他的进程共享部分地址空间5. 条件变量1. 允许线程因为某些未达到的原因而阻塞2. 允许被阻塞而等待的线程原子性进行3. 经常与互斥量一起使用：让一个线程锁住一个互斥量，当他不能获得期待结果时等待一个条件变量。有另外一个线程发信号唤醒。4. 条件变量不会存在于内存（发出后丢失）5. 管程：一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据1. 任何一个时刻管程里只能有一个活动的进程2. 第二个进程将被挂起直到活跃进程离开3. 如果一个条件变量上有若干程序在等待，则执行signal操作以后，系统只能从中任选一个恢复4. 实现：JAVA synchronized关键字5. 劣势1操作系统是C写的，没有管程的概念2. 分布式系统无法避免6消息传递1. 使用系统调用send和receive2. 潜在问题：消息丢失，消息认证，消息传递速率低3. 编址方法1. 为每个进程分配一个唯一的地址2. 引入新的数据结构：信箱。消息发往信箱。（解决消费者生产者问题）7. 屏障：在每个阶段结尾安放屏障，当一个进程达到屏障时，它被屏障阻拦，直到所有进程都达到屏障24 调度1. 定义：多个进程就绪是，CPU选择下一个将要执行的进程的方法。2. 进程行为：IO密集型（web服务器）和CPU密集型（象棋软件）。越来越多的软件倾向于IO密集型，应该多运行这类进程以保持CPU使用率3. 何时调度：1. 创建新进程时，应该先调度父进程还是子进程2. 进程退出时3. 进程阻塞时（IO，信号量等）4. IO中断发生时4调度算法定义:1. 抢占式：挑选一个进程，并且让进程运行某个固定时段的最大值，之后挂起2. 非抢占式：挑选一个进程，让进程运行直到其阻塞或者自动释放CPU5. 调度算法目标（所有系统）：1. 公平：每个进程公平的CPU份额2. 策略强制执行：所宣布的策略执行3. 平衡：系统所有部分都忙碌6. 调度算法分类：1批处理：处理周期性作业，广泛的商业应用1. 调度算法目标：1. 吞吐量throughout：系统每小时完成的作业数量2. 周转时间turnaround time:从一个批处理作业提交时刻开始直到作业完成时刻位置的平均时间3. CPU利用率2. 具体调度算法：1. 先来先服务（first-come）优点：易于理解，便于实现缺点：同时运行IO密集型和CPU密集型程序时效率低下2. 最短作业优先（不可抢占）1. 计算公式：T=na+n-1b+n-2c+zn 其中abc.z2. 只有所有作业都可同时运行且运行时间可以预知的情况下才能使用3. 最短剩余时间优先：最短作业优先的抢占版1. 新作业到达时，整个时间与当前进程的时间做比较，运行剩余时间较少的作业2. 交互式系统1. 调度算法目标：1. 响应时间：发出指令到相应的时间2. 均衡性：满足用户的期望2. 具体调度算法1. 轮转调度：最古老，最简单，最公平，使用最广1每个进程被分配时间片，时间片结束时切换进程2. 时间片1过长：对短命令的交互请求时间变长2. 过短：过多进程切换，降低CPU效率2. 优先级调度：每个进程赋予优先级，优先级高的进程先执行1. 使IO进程良好运行的算法：进程优先级为1/f，其中f是进程在上一时间片中实际运行的比例（IO进程会得到较高优先级）2. 多优先级队列：低优先级可能出现饥饿现象3. 多级队列1. 实现方法：最高优先级的进程获得1个时间片，之后优先级下降并在下次运行时获得两倍的时间片4. 最短进程优先1. 根据过去进程运行时间预测并执行估计运行时间2老化算法：当前测量值和先前估计值进行加权平均（1/2比较好，右移一位即可）5. 保证调度：每个进程获得1/n的时间6彩票调度：向进程提供各种系统资源的彩票，某些进程可以协作获得更多彩票。不错的方法7公平分享调度：每个用户获得等量的CPU时间3. 实时系统1. 调度算法目标：1. 满足截止时间：避免丢失数据2. 可预测性：在多媒体系统中避免品质降低2. 分类硬实时：必须满足绝对的截止时间软实时：虽然不希望偶尔错失，但是可以容忍2. 周期性时间公式M个周期时间，事件i以周期Pi发生，需要用Ci的CPU时间，那么这个系统可调度的条件是i=1mCiPi17. 调度机制与策略：将调度机制与调度策略分离例子：系统使用优先级调度，但是把赋予优先级的行为委托给进程。8线程调度1. 用户级线程：内核不知道线程，用户进程调用专门定制的线程调度程序2. 内核级线程：时间片。2.5 经典IPC(Inter-Process Communication)问题1. 哲学家进餐1. 随机事件解法：可能因为不可靠的随机数字而失败2. 读者-写者问题：不能让写者无法写入数据第三章 存储管理3.1 无存储器抽象：程序直接访问物理内存1. 不能在内存里【同时】运行多个程序2. 实现并行可采用多线程编程：不现实3. 运行多道程序的方法1. 交换：保证一个时刻只有一个程序在内存里2. 特殊硬件：防止进程相互干扰缺点：不能直接使用绝对物理地址，装载器需要一定方法分别地址和常数4. 一些问题1. 用户系统如果可以寻址内存的每个字节，就有可能破坏操作系统2. 多道程序运行非常困难3.2 地址空间抽象1. 概念：一个进程可用于寻址内存的一套地址集合，一般独立与其他进程的地址空间，除某些情况下需要共享2. 解决方法1. 动态重定位：基址寄存器和界限寄存器缺点：，每次访问都需要加法和比较运算2. 交换技术：将一个进程完整调入内存，使其运行一段时间后再存回硬盘1. 换入后使用硬件重定位2产生空洞，需要内存紧缩3. 现代程序需要内存较多，但是硬盘速度慢，交换时间长4. 注意：进程大小如果增长，需要辅助手段。解决方案：移入时分配额外内存，再次交换出去时不交换额外的。3. 空闲内存管理1. 位图存储：每个字需要1位位图 优点：空间少 缺点：分配内存时需要在位图里寻找指定长度的0串，费时。2. 链表管理：维护一个记录已分配内存段和空闲内存段的链表，每个链表的节点或包含一个进程，或者两进程之间的空闲区优点：进程终止或者被换出是链表的更新非常直接具体分配方法：1. 首次适配first fit：沿列表搜索直到找到一个足够大的空间2. 下次适配next fit：首次适配之后，从上次结束的地方开始搜索。（性能略低于首次适配）3. 最佳适配best fit：搜索整个链表，找出能容纳进程的最小空闲区。（速度较慢，会产生大量无用的小空闲区）4. 最差适配worst fit：分配最大的空闲区（也不好）5. 为进程和空闲区保存单独链表a) 优点：提高分配算法速度b) 缺点：增加内存复杂度和内存释放速度变慢6. 快速适配quick fit：为常用大小的空闲去维护单独的链表3.3 虚拟内存1. 基本思想：每个程序拥有自己的地址空间，这个空间被分割成许多块，每一块称作一页page，page被映射到物理内存，但是只有某些页真正在内存中。操作系统调用不存在页面的时候，引发缺页中断2. 分页技术1. 有程序产生的地址被称为虚拟地址，它们被称为虚拟地址空间。地址空间里的单元成为页面，在物理内存对应的单元称为页框page frame。2. 是用虚拟内存时，地址不是送到内存总线，而被送到内存管理单元(memory management unit, MMU)MMU将虚拟地址映射成物理地址。内存对MMU一无所知例子：16位虚拟地址对应15位物理地址，输入的虚拟地址被分为4位页面和12位偏移量，在页表中查询，之后组成15位实际地址3. 页表1. 本质：一个把虚拟页面映射成页框的函数2. 页表项的结构1. 页框号2. 在/不在位3. 保护位4. 访问位和修改位5. 禁止高速缓存位：对映射到设备寄存器的页面非常重要3. 不在内存的页面的硬盘地址不是页表的一部分：缺页中断时，该页面的磁盘地址等信息保存在操作系统的内部软件上4. 加速分页1. 主要问题1. 虚拟地址到物理地址的映射必须非常快2. 如果虚拟地址很大，页表也会很大2. 极端解决方案1. 页表全部在寄存器里优点：简单，映射过程中不需要访问内存缺点：页表很大时代价高昂，每一次上下文切换都必须装载整个页表，性能低2. 页表全在内存里优点：上下文切换快缺点：每条指令执行都需要访问内存3. 现实解决方法1. 转换检测缓冲区translation lookaside buffer，TLB1本质：把虚拟地址直接映射成物理地址的小型硬件2. 使用：传入的虚拟页号并行匹配3. 未命中：MMU未检查到有效匹配项，则进行页表查询，从TLB淘汰一个表项，并用新页表项代替4. 软失效：页面不在TLB但是在内存：更新TLB，几纳秒 硬失效：页面不在内存：缺页中断，磁盘IO，几毫秒4. 大内存页表1. 多级页表：32位虚拟地址划分成页表1，页表2，偏移量三部分原因：避免全部页表一直在内存（一般程序只有少量的正文段，数据段和堆栈段，中间是大量空洞，访问空洞时强制缺页中断并发信号）2. 倒排页表（inverted page table，64位机器）：每一个页框对应一个页面优点：节省空间缺点：从虚拟地址到物理地址的转换困难（必须搜索整个表项来寻找（进程， 虚拟页面）对）解决方案：建立一张散列表，用虚拟地址来散列，相同hash值的表链在一起3.4 页面置换算法：缺页中断时，操作系统必须淘汰一个旧页面/web服务器淘汰一个高速缓存项1. 最优页面置换算法：用X条指令后才会用到来标记页面，置换X最大的页面优点：已知最好算法缺点：不可能实现2. 最近未使用页面置换算法（not resently used，NRU）：启动进程时，系统把页面的访问位(R)和修改位(M)置零，R位被定期清零，以区别最近是否访问过。页面分为4类：1没有被访问和修改2. 没有被访问，已修改3. 被访问，没有修改4. 访问修改NRU算法在类标号最小的非空集里挑选一个页面淘汰优点：简单易实现缺点：性能不是最好的3. 先进先出页面置换算法（FIFO）：淘汰最老页面，可能会淘汰很有用的，不单纯使用4. 第二次机会页面置换算法（second chance）：检查最老页面的R位，如果是0，置换之，否则清零并把该页面放到链表尾端。本质：找寻一个最近的时钟间隔以来没有被访问过的页面5. 时钟页面置换算法（clock）：第二次机会页面的时钟版6. 最近最少使用页面置换算法(LRU, Least Recently Used)实现方法：需要在内存里维护所有页面的链表，最近最多的使用的页面在表头，最近最少的页面在表尾缺点：每次访问内存都必须更新整个链表，费时特殊硬件实现方法：1. 64位计数器C，每个页表都有一个计数器，每次执行完以后加1，缺页中断时置换计数器最小的页面2. N*N矩阵。初值为0，访问页框k时，硬件首先把k行的位都设置成，再把k列的位都设置成0。任何时刻二进制数值最小的行对应页面会被置换7. 软件模拟的LRU1. 最不常用算法（NFU）：每个页面与软件计数器相连，每次时钟中断是操作系统扫描所有页面并将R位加到计数器上，置换计数器值最小的页面缺点：记忆太久，操作系统可能会置换有用的页面2. 老化算法aging：在R位加入之前，计数器右移一位（相当于过去访问次数*1/2）,然后把R加到计数器最左边。置换计数器值最小的页面。缺点：不能确定时钟滴答中哪个页面被先访问 计数器只有有限位数，限制了其对以往页面的记录（实际中一般够用）8. 工作集页面置换算法1定义：一个进程当前正在使用的页面的集合称为工作集2. 分页系统会设法跟踪工作集，在进程运行之前就预先调页3大多数进程不会均匀访问地址空间，而是一小部分页面4. 缺页中断时，淘汰不在工作集的页面。5. 近似：过去的t秒实际运行时间中进程所访问的页面的集合6. 算法：9. 工作集时钟页面置换算法：工作集算法的时钟版本10.小结：最好的算法是老化算法和工作集时钟算法3.5 分页系统的设计问题1. 局部分配策略与全局分配策略1局部算法可以有效地为每个进程分配固定的内存片段例子：工作集, FIFO, LRU2. 全局算法在可运行进程之间动态分配页面，通常工作更好。例子：FIFO, LRU1. 为进程分配相等的份额：不好，对大进程不公平，应该给每个进程分配最小的页框数2. PFF：监测缺页率，保证每个进程的PFF在可控范围内。2. 负载控制：换成进程时考虑其特性（IO密集或者CPU密集）3. 页面大小小页面：更多页面更大页表，更多缺页中断，内部碎片少，分配时效率高大页面：反之计算公式：P= 2 *s *e P页面，s进程平均大小，e每个页表项大小4. 分离的指令空间和数据空间：独立分页5. 共享页面1. 共享I空间页面2. 共享页面时，换出进程不应换出共享页面：使用专门的数据结构记录共享页面3. 共享数据：写时复制6. 共享库1. windows：DLL文件，连接器没有加载函数，而是一小段可以在运行时绑定函数的存根里程stub routine2. 优点：共享库中一个函数被修正：不需要重新编译程序3. 问题：编译共享库时，不产生使用绝对地址的指令7. 内存映射文件：进程发起一个系统调用，把一个文件映射到虚拟地址的一部分。映射共享页面时不会实际读入页面，而在其访问页面时才会每次一页的读入。8. 清除策略1. 分页守护进程：保证有足够空闲页框供给2. 实现方法：双指针时钟，前指针由分页守护进程控制9. 虚拟内存接口：允许程序员控制内存映射1. 可以允许两个或多个进程共享一部分内存2. 实现高性能的消息传递系统：发送进程清除映射，接收进程建立映射3.6 分页系统的实现1. 上下文切换：重置MMU，刷新TLB，装载页表2. 缺页中断处理1. 陷入内核，保存程序计数器2. 调用汇编例程保存其他寄存器3. 操作系统查看寄存器或者分析指令判断所缺页面4. 操作系统检查虚拟地址是否有效，若是则启动页面置换算法更换页面5. 如果页面被修改过，启动IO，标记该页面，上下文切换6. 启动IO装载缺失页面7. 页表更新，恢复堆栈和寄存器，重启被中断进程3. 指令备份：使用隐藏的内部寄存器，在每条指令执行之前，把程序计数器的内容复制过来4. 锁定内存页面：锁住正在进行IO的页面或者在内核缓冲区完成所有IO5. 后备存储1. UNIX：swap交换区：没有文件系统2. 进程启动前必须初始化交换区3. 实现方法1. 将整个进程复制到交换区：进程可能增长2. 直到换出时才分配交换区：内存中每个页面都要记录磁盘地址3. 交换分区：windows使用大文件4. 空间不足时抛弃程序正文或者共享库6. 策略与机制分离：更多的模块化代码和更好的适应性，更多的陷入内核1. 三部分：底层MMU处理程序，内核的缺页中断处理程序，用户空间的外部页面调度程序2. 问题：外部调度程序无权访问页面的R位和M位1. 把相应数据映射到或者传递给外部调度程序2. 把页面置换算法放在内核3.7 分段：在机器上提供多个独立的地址空间，长度从0到某个整数，可以动态改变1. 段是逻辑实体，不会同时包含不同类型的内容，不是定长的2. 1维地址中，修改过程会影响其他无关地址的起始地址3. 比较4. 纯分段的实现：可能会有碎片，需要内存紧缩5. 分页与分段结合1. 虚拟地址分为段号和段内地址，其中段内地址里有页号和页内偏移量2. 先找段-找页面-找虚拟地址3. 实例：奔腾处理器1. 虚拟内存的核心：局部描述符表LDT和全局描述符表GDT2. 利用选择子可以同时实现纯分页/分段和混合模式3. 保护环：越级调用第四章 文件系统4.1 文件1. 拓展名：UNIX任意，WINDOWS注册2. 二进制文件：魔数，放在二进制文件头3. 文件存取：顺序存取（磁带），随机存取（硬盘，seek）4. 文件操作：open：把文件属性和磁盘地址装进内存，方便后续的快速调用（fd）4.2 目录1. 软连接：目录的data block加一条记录，新生成一个文件（i节点，data block里是被链接目录的路径），可以链接目录，可以跨文件系统（转储时需要注意）2. 硬链接：目录的data block加一条记录，指向现有文件i节点。只能链接文件，不能跨文件系统4.3 文件系统的实现1. 磁盘0号扇区：MBR，引导计算机启动，之后分区表，之后superblock2. 文件的实现1. 连续分配：CD-ROM，DVD优势：实现简单，记录第一块的磁盘地址和块数即可；读操作性能好劣势：磁盘上会出现大量碎片；创建文件时必须知道文件大小2. 链表分配：每个块的第一个字作为下一块的指针优势：没有内部碎片劣势：随机读取非常慢，必须先读之前的n-1块；块的大小不再是2的整数次幂，降低系统运行效率3. 内存中采用表的链表分配（FAT，每个磁盘的指针字放在内存里）优势：加速随机存储劣势：必须把整个表放在内存里，对大硬盘不合适4. i节点（UNIX）：只有对应文件打开的时候，i节点才在内存中优势：占用内存较少劣势：需要磁盘块个数会超过i节点大小：i节点可以指向更多的i节点3. 目录的实现1. UNIX:文件属性在i节点里。Windows：文件属性在目录里2. 长文件名1. 长度限制：浪费大量目录空间2. 目录项固定部分：长度，数据项等。下一个进来的文件不一定符合空隙一个目录项可能分布在多个页面上，读取时会有页面故障3. 目录项固定长度，文件名在目录后的堆中优点：移走文件后，总有新文件可以加进来；文件名不需要从字边界开始缺点：管理堆+页面故障仍然存在3. 查找文件名：线性查找或者使用散列表1. 散列表：查找迅速，管理复杂（可以加入高速缓存）4. 共享文件5. 日志结构文件系统LFS1. 基础思想：将整个磁盘化成一个日志，每隔一段时间，缓存在内存中所有未进行的写操作都被放到一个独立的段中，并写到日志末尾（难以找到I节点）2清理线程：定期扫描日志进行磁盘压缩6. 日志文件系统：NTFS，ext31. 基本思想：保存记录文件系统下一步要做什么，防止崩溃导致的不一致2. 基本实现：日志文件系统先写一个日志，列出要进行的动作。然后进行操作，成功之后擦出日志。若系统崩溃，日志系统会重新开始行动。3. 写入日志的操作必须是幂等的：只要有必要，可以重复多次，不会带来破坏4. 原子事务7. 虚拟文件系统：建立初衷NFS1. 基本思想：抽象出所有文件系统都共有的部分，并且将这部分代码放在单独一层，该层调用底层的实际文件系统来具体管理数据2. 装新文件系统时，必须向VFS提供需要的函数地址的列表3. v节点：VFS在fdt中为调用进程创建一个入口，并指向一个新的v节点。之后VFS返回文件描述符。读文件时，VFS读v节点，然后功能指针，最后实际文件系统的入口函数4.4 文件系统的管理和优化1. 磁盘空间管理1. 块大小大块：浪费大量磁盘空间（低空间利用率）小块：多次寻道和旋转延迟，降低性能（低数据率）不存在合理的平衡方案。磁盘空间越来越大，应使用大块2. 记录空闲块1. 磁盘块链表，每个块含255个空闲块块号和指向下一个记录块的地址优化：记录连续空块问题：指针块满或者空的时候，小型读写操作会引起大量IO解决：拆分满了的指针快，保证内存里有一个半满的指针块2. 位图：磁盘块会比较紧密的聚集在一起，可以调进内存3. 磁盘配额：配额表2. 文件系统备份1. 问题：1. 备份整个文件系统还是只备份部分文件2. 增量储备？3. 压缩：单个坏点可能导致解压缩失败4. 活动系统的文件备份5. 其他非技术性问题2. 方案1. 物理转储：复制磁盘块，万无一失，简单快速1. 未使用的磁盘块无需备份2. 坏块不应转储3. 不能增量存储，不能恢复特定文件2. 逻辑转储：恢复一个或几个目录1. 转储通向修改过文件或目录的路径上的所有目录1. 为了能把转储的文件和目录整体恢复到新文件系统中2. 可以对单个文件进行增量恢复2. 算法实例第一阶段：检查所有目录项，标记所有的目录和每一个修改过的文件第二阶段：扫描目录树，若某个目录里没有修改过的文件或者目录，去除它第三阶段，转储所有被标记的目录和文件3. 问题1. 空闲块列表需要从0开始构造2. UNIX文件包含空洞，不应转储3. 特殊文件不应转储3. 文件系统一致性1. 块的一致性1. 方法：构造两张表，计数器都初始化为0，第一个表的计数器跟踪该块在文件中的出现次数，第二个跟踪该块在空闲表的出现个数。若一致，则对任意一块，其必只在一张表里的计数为1，一张为02. 不一致的解决方法1. 都是0：加回空闲表2. 空闲表出现多次：重新建立空闲表3. 文件中出现多次：分配一空闲块，复制该块内容，将其插入到文件中2. 文件的一致性1. 方法：构造一张表，计数器都初始化为0，计数器跟踪该文件在目录中的出现次数，对比其i节点个数。若文件系统一致，则统计数据也应一致2. 不一致的解决方法：把i节点连接计数设置正确4. 文件系统的性能1. 高速缓存：减少磁盘访问速度1. 常用管理算法：检查全部读请求，查看是否有相应块在高速缓存里2. 散列：加快寻找3. 与分页相比，访问不频繁，所以可以精确实现LRU（可能导致关键块没有被及时写回磁盘）4. Windows：高速缓存被修改的块被立即写回内存（通写高速缓存）5. UNIX：每30s写回一次2. 块提前读：需要用到之前提前写进高速缓存，提高命中率1. 只适用于顺序存储文件（可以跟踪文件行为判定）3. 减少磁盘臂运动1. 块簇技术：用连续块簇做分配单位，但读取和高速缓存时仍使用块，寻道次数减半2. 在磁盘中间储存i节点：平均寻道时间减半（没看懂point在哪里。）5. 磁盘碎片整理1. windows：把文件碎片整合，放在一个连续的空间以提高读取效率。2. linux：不需要4.5文件系统实例1. CD-ROM：不需要记录空闲块，不能删除1. ISO9660：16块前导，可放引导信息等。第17块存放基本卷描述符，不能使用大写字母，数字等2. Rock Ridge拓展(UNIX)：NM拓展，允许无限长名字，权限拓展域等3. Joliet拓展(Windows)：长文件名等2. MS-DOS文件系统：FAT1. 后面的数字代表磁盘地址位数（簇大小）3. UNIX V7:1. UNIX的i节点含文件大小，三个时间，所有者，所在组，保护信息，计数等信息2. 大文件使用多个连接块第五章：输入/输出5.1 I/O硬件原理1. IO设备1. 块设备：传输一块为单位，每个块可独立读写，可寻址2. 字符设备：以字符为单位，不可寻址2. 设备控制器1. 低层次接口，控制设备3. 内存映射IO1. IO端口，形成IO空间，操作系统使用特殊指令访问优缺点把下面反过来2. 把所有控制寄存器映射到内存空间，每一个寄存器有唯一内存地址，并且保证不会有内存被分配优点：1. 不需要特殊的IO指令来读写设备寄存器（C/C+没有实现IN或OUT的指令）2. 不需要特殊的保护机制阻止用户进程执行IO（只需要操作系统不把映射的地址空间交给用户）3. 可以引用内存空间的每一条指令都可以用在控制寄存器（TEST等）缺点：1. 硬件必须针对某个页面具有选择性禁用高速缓存的能力2. 所有内存和IO都必须检测所有的引用对于单独内存总线的解决方法：1. 全部引用发到内存，响应失败再给IO2. 内存总线放置探查设备，放过潜在指向所关注IO设备的地质3. 在PCI桥芯片中过滤地址（pentium的设计）3. 工作原理：CPU把地址放置在总线上，由内存或者IO设备来响应4. 直接存储器存取DMA：独立于CPU访问系统总线1. 结构：一个内存地址寄存器，一个字节计数寄存器，多个控制寄存器2. 没有DMA时的运作：控制器从磁盘把数据读入内部缓冲区，计算校验和，之后给操作系统中断，让操作系统把数据读入内存1. 内部缓冲使校验错误更早被发现2. 一旦硬盘开始工作，读入的数据是固定速率。块被放入内部缓冲区时，DMA启动之前不需要访问主线，简化控制器设计3. DMA运作1. CPU对DMA控制器进行编程2. DMA在总线上向磁盘发起读请求3. 磁盘控制器把数据写到内存4. 磁盘控制器发控制信号给DMA控制器，DMA决定是否继续读5. 读结束，DMA发中断给CPU，CPU从内存读数据4. DMA可以一次处理多路信号5. 周期窃取：DMA从CPU处偷走一个总线周期以读取一个字6. 突发模式：DMA发起一连串传送，阻塞CPU和其他设备优点：效率高缺点：可能阻塞很久7. DMA可以把数据复制到自己的缓冲区，再复制到内存优点：更加灵活，可以实现内存到内存缺点：需要两个总线周期8. 弊端：DMA比CPU慢，可能降低效率5. 中断1. 中断控制器置起信号，并在地址线上放置数字（指向中断向量），之后重开中断控制器并保存程序计数器和其他寄存器1. 保存在内部寄存器：中断控制器之后无法获得应答，直到所有信息被读出可能丢失中断或数据2. 保存在堆栈（大部分的做法）1. 用户堆栈：堆栈指针不合法，缺页错误等（此时无法进行缺页中断）2. 系统堆栈：涉及到MMU,TLB等，浪费时间2. 中断向量：新的中断表格的索引，开始中断服务例程3. 精确中断与不精确中断1. 原因：现代CPU的流水线和并行2. 精确中断：中断时将机器留在一个明确状态1. 程序计数器保存在已知位置2. 之前的所有指令都执行完毕，之后的指令都没有开始3. PC所指向的指令状态已知3. 不能满足要求的是不精确中断：需要记录大量内部状态，中断响应和恢复很慢4. 解决方法1. 某些类型的中断是精确的，或者用户可以强制精确缺点：日志，影子副本等操作降低性能2. 使用精确中断：牺牲芯片性能5.2 IO软件性能1. IO软件目标1. 设备独立性：命令执行不需要指定设备2. 统一命名：所有文件都是用路径名寻址3. 错误处理：尽可能在硬件层面解决4. 同步阻塞驱动与异步中断驱动：操作系统挂起IO程序使物理异步IO变成同步5. 缓冲：大量复制，影响性能6. 共享设备与独立设备：死锁2. 程序控制IO：操作系统轮询IO设备，忙等待（嵌入式系统中较好）优点：简单缺点：低效3. 中断驱动IO：等待IO设备时调用其他例程缺点：中断发生在每个IO操作上，浪费CPU时间4. DMA的IO优点：中断只发生在每次缓冲区操作缺点：DMA慢于CPU，可能降低效率5.3 IO软件的层次1. 中断处理程序1. 应该被深隐藏：将启动一个IO操作的驱动程序阻塞，直到IO完成且产生中断手段有：信号量上执行down，条件变量wait，信息上receive2. 具体执行：需要设置页表，MMU，TLB等2. 设备驱动程序：每个连接到计算机的IO设备都需要特定代码来驱动1. 通常必须是操作系统内核的一部分。（也可以不是：隔离内核与操作系统使内核不受干扰）2. 大多数操作系统都定义了一个所有设备都必须支持的标准接口3. 功能：初始化，电源管理，接受上方与设备无关的软件发出的抽象读写请求并执行之4. 具体实现1. 启动时检查输入参数2. 检查设备是否在用3. 将命令写到控制寄存器4. 命令发出后1 驱动程序阻塞自身之后中断到来解除阻塞2、 无延迟，不需要阻塞5. 操作完成后检查错误5. 驱动程序必须是可重入的6. 热插拔：内核重新分配资源，撤除旧资源，适当位置填入新资源3. 与设备无关的IO软件1. 设备驱动程序的统一接口：是所有IO和驱动设备看起来或多或少是相同的1. 实现：对于每一种设备，操作系统定义一组驱动程序必须支持的函数。通过表格调用这些函数2. 设备保护2. 缓冲1. 在用户空间里设置一个缓冲区优点：效率高缺点：缓冲区可能被调出分页；如果钉住，可用页面池会减小2. 在内核空间和用户空间里都设置一个缓冲区内核缓冲区填满的的时候，将包含用户缓冲区的页面调入内存优点：效率更高缺点：调入内存时无法缓冲数据3. 在用户空间设置两个缓冲区：解决所有问题4. 循环缓冲区5. 缺点：多次复制会降低效率3. 错误报告：许多错误是设备特定的并且必须由适当的驱动程序来处理1. 编程错误：返回错误代码给调用者2. 实际IO错误：由驱动程序决定做什么4. 分配与释放专有设备：某些设备在任意给定的时刻只能由一个进程使用1. 要求进程在代表设备的特殊文件直接执行open操作：如果不可用，open会失败2. 更复杂的方法：对请求和释放特殊设备有特殊的机制：试图得到不可用的设备可以将将被阻塞并放到一个特殊队列里5. 与设备无关的块大小：应该由与设备无关的软件隐藏并提供同一块大小4. 用户空间的IO软件：某些独立于内核的程序1. 系统调用通常是由库过程实现2. 假脱机：多道程序处理独占IO设备的方法守护进程与假脱机目录：进程打印文件时，首先要生成整个文件，并将其放在假脱机目录下，最后由守护进程打印5.4 盘1. 盘的硬件1. 磁盘：IDE与SATA1. 重叠寻道：控制器能否同时控制两个或多个驱动器寻道2. 隐藏细节：软件工作时仿佛存在x柱面，y磁头和z扇区，由控制器将请求实际硬件3. 逻辑块寻址：磁盘扇区从0开始编号，不管磁盘的几何规格2. RAID：独立磁盘冗余阵列1 基本思想：将一个装满了磁盘的盒子安装到计算机，用RAID控制器替换磁盘控制卡，将数据复制到整个RAID上以获得更好的性能和可靠性（并行操作）2. 0级RAID：将连续的条带以轮转方式写到全部驱动器上RAID控制器会把命令解析成单独的命令，以正确的顺序将命令对应四块磁盘中的一块且并行操作，最后在内存里正确装配数据优点：性能杰出，简单明了缺点：1. 对于每次请求一个扇区的操作系统，效率低 2. 可靠性比单块硬盘差3. 1级RAID：同0级原理一样，但是复制所有磁盘优点：读性能高了一倍；出色的容错性和恢复速度缺点：写操作性能下降4. 2级RAID：以字节为单位优点：巨大的数据率缺点：所有控制器旋转同步，单位时间内校验汉明码等5. 3级RAID：2级RAID的简化版，使用奇偶检验驱动器为每个数据字建立奇偶检验优点：巨大的数据率，奇偶校验码可以用来改正错误缺点：所有控制器旋转同步6. 4级RAID：使用条带，用独立的奇偶校验驱动器优点：损失的保护：崩溃的驱动器数据可以通过异或回复缺点：1. 对于微小更新性能较差：必须读取旧数据并计算更新校验值 2. 奇偶驱动器负担沉重7. 5级RAID：将奇偶检验条带分散到每一个驱动器优点：降低奇偶驱动器负担缺点：回复崩溃驱动器非常复杂3. CD-ROM：更高的记录密度1. 使用凹陷/凸起的过渡来记录1，平缓记录0。数据写在连续螺旋里2. 黄皮书：CD-ROM的标准主要是数据格式化与纠错能力3. 寻道：CD-ROM的寻道非常困难：软件计算一个近似位置，激光头在四周寻找前导区4. 绿皮书：补充了图形以及在相同扇区保存交错音频视频和数据的能力对多媒体CD-ROM非常重要4. CD-R：可刻录CD1. 激光光束遇到染料时破坏其化学键2. 橘皮书：允许CD-R逐渐增长式写入3. 防止盗版复制1. 将CD-R上所有文件的长度记录为几G字节2. 在挑选出来的扇区故意使用错误的ECC，期望CD复制程序会改正错误3. 使用非标准间隙5. CD-RW：可重写CD：三种激光使合金处于三种形态6. DVD：数字通用光盘1. 与CD的差别：容量提高7倍1. 更小的凹痕2. 更密的螺旋3. 红色激光（需要第二个激光器才能同时读取CD和DVD）2. 下一代DVD：HD DVD Vs Blu-ray DVD（蓝光DVD获胜，2009）2. 磁盘格式化1. 硬盘由一叠铝，合金或者玻璃组成2. 低级格式化1. 扇区由前导码，数据和ECC组成2. 前导码1. 以一定的位模式开始2. 包含柱面，扇区号和其他信息3. 柱面斜进cylinder skew：改善性能，一次读取多个磁道取决于驱动器的几何规模4. 结果：磁盘容量减小，取决于前导码，扇区间隙，ECC大小和备用扇区数量5. 单交错：为了给控制器时间以便完成校验及将数据从缓冲区复制到内存5. 双交错：单交错的进化3. 高级格式化：对分区执行，设置一个前导块，空闲存储管理，根目录和空文件系统。还要将一个代码放置在分区表项以指示文件系统。3. 磁盘臂调度算法：默认实际硬盘的虚拟几何规格和实际相同1. 读写时间影响因素1. 寻道时间（主导地位）2. 旋转延迟3. 实际数据传输时间2. 寻道时间优化算法1. 最短寻道优先SSF：处理与磁头最近的请求优点：效率高缺点：两边的区域请求得到的服务较差，不公平2. 电梯算法：磁盘臂向一个方向移动并处理沿途请求，到达尽头后转向优点：公平，且对于任意一组请求，移动长度的上界都是柱面数的两倍3. 电梯算法改：处理完最高编号的请求后磁盘臂移动到最低编号的请求并继续向上4. 如果软件可以检查磁头下方的扇区号：驱动程序发出请求读写下一次要
展开阅读全文