参考自 https://www.coursera.org/learn/os-pku/home/welcome

概述

作用

1. 管理资源
2. 提供简单方便的指令。用户通过终端命令和高级语言向系统提出服务请求。
3. 抽象硬件（CPU抽象为进程；内存抽象为进程地址空间；磁盘抽象为文件）

特征

1. 并发：宏观同时运行，微观顺序执行。
2. 共享
3. 虚拟
4. 随机： 随时对不可预测的次序发生的时间进行响应并处理。所以，无法预知进程的运行快慢，很难重现某一时刻的状态。

架构

Windows

应用 - 操作系统 - 硬件

Unix

硬件 - 内核 - 系统调用接口 - Unix命令

Linux

硬件 - 内核态 - 用户态

Android

分类

按年代

• 批处理
  【方法】用户把作业给操作员，启动，自动、依次执行每个作业，操作员把结果交给用户。【目的】提高资源利用率。【问题】慢速输入输出，浪费CPU。【相关】卫星机。单道批处理系统和多道批处理系统。SPOOLING（假脱机技术）系统：Atalas机，把I/O和计算真正并行。现代打印机仍然在使用SPOOLing技术（先到磁盘上对应打印队列的文件，再执行打印进程）
• 分时
  【相关】第一个交互系统。【目的】多个用户一起用一台机器，及时响应。【方法】以时间片为单位轮流为每个用户服务。
• 通用
  【方法】分时+批处理。分时优先（前台），批处理在后（后台）。
• 实时
  【目的】对外部请求在严格时间内响应，高可靠性。如汽车的操作系统。【相关】硬实时系统（汽车装配线：需要严格按时响应）和软实时系统（媒体播放：偶尔掉帧没事）。
• 个人计算机操作系统
  【目的】界面友好，软件丰富。
• 网络操作系统
  【目的】互相通信，资源共享。
• 分布式
  【目的】多个计算机协同工作。【问题】负载均衡、任务分配。
• 嵌入式
  【目的】为嵌入式设备（大设备的一部分）开发。【特点】

按类型（TANENBAUM)

大型机、服务器、个人、掌上、嵌入式、智能卡等。

• 智能卡
  包含有一块CPU芯片的卡片。存贮空间限制，资源保护和限制（电子支付机）。

运行环境

处理器

构成

运算器、控制器、寄存器、高速缓存
【寄存器】控制和状态寄存器控制处理器的操作。

• 程序计数器-PC：记录要取出的指令的地址。
• 指令寄存器-IR：记录最近取出的指令。
• 程序状态字-PSW：记录处理器运行状态。

中断与异常机制

改变了CPU的执行流程。

中断（外中断）

相当于汽车发动机或飞机引擎。
os是由中断（事件）驱动的，外部设备引发的。异步的

• I/O中断（按了键盘鼠标）
• 时钟中断（定时器、时间片到了）
• 硬件故障（没电了）
  【目的】及时的处理设备发来的请求。支持CPU和设备之间并行操作。
  【方法】暂停-转去处理-返回断点-继续执行。
  【特点】随机、自动、可恢复。

异常（内中断）

正在执行的指令引发的。CPU执行指令是本身出现的问题。同步的。

• 系统调用
• 页故障
• 保护性异常
• 断点指令（调试）
• 程序性异常（算术溢出等）

中断/异常的工作原理

硬件工作：响应，把CPU控制权给中断程序。中断寄存器，每个指令执行周期的最后时刻扫描中断寄存器，如果有中断，保存现象（PC+PSW），查中断向量表（存放了中断程序的地址），推入寄存器，执行程序。
软件工作：处理。
系统提前定义好中断程序，硬件去执行。

x86对中断的支持

实模式

保护模式

IDTR-IDT（中断描述符，偏移）- GDTR（端描述符，段基地址）
中断程序地址 = 偏移 + 段基地址

系统调用机制（SYStem call）

用户在编程时可以调用的操作系统功能。
用户态 --> 内核态。
接口类型：进程控制、进程通信、文件使用、目录操作、设备管理、信息维护。

• 库函数、API：间接使用系统调用内核函数，实现系统调用。
  系统调用号，系统调用表，陷入指令（在linux中，int $0x80引发系统调用)。
  通过通用寄存器传递参数。

进程和线程

进程

多道：单个PC（物理程序计数器）虚拟成多个PC。
并发：多个程序同时处于开始但尚未结束的状态，而且次序不定。

进程=任务

• 一次执行过程
• 一个CPU虚拟成多个CPU
• 资源以进程为单位分配资源
• 将CPU调度给需要的进程。

进程控制块PCB

记录一个进程的各种属性和变化过程。
进程表：所有PCB的集合，固定大小，所以有最大进程数。
PCB中包括：描述（ID、名字、用户、组），控制（状态、优先级等），使用资源（打开的文件等），CPU现场(寄存器值、PC、PSW)。
Linux中叫做：task_struct
Windows: Eprocess+...

进程状态

运行、就绪（由于时间片导致的，是正常进程轮换）、等待（或者叫阻塞、封锁、睡眠。由于同步导致的）。动态产生、动态消亡。

此外，创建、终止、挂起（就绪挂起、阻塞挂起）
不同状态不同进程队列（元素是PCB）。

进程控制

原语：完成某种特定功能的一段程序，不可中断（通过屏蔽中断）。

• 进程创建：PID+PCB，分配地址空间，插入进程队列:fork、exec
• 进程撤销：回收资源、回收PCB:exit
• 阻塞：进程正在等待的事件未发生时，进程自己执行阻塞原语，变为阻塞态：wait

Unix的几个基本操作（均为系统调用）

• fork：复制调用进程来建立新的进程。
• exec：用一段新的程序覆盖原来的地址空间，实现进程的代码转换。
• wait()
• exit()

fork

Unix一次一页的复制父进程地址空间，共享资源，设置为就绪，插入就绪队，子进程返回0，父进程返回子进程pid，从而实现父进程一分为二。

Linux的fork实现，采用了Copy-On-Write技术。

进程相关概念

分类

系统进程、用户进程。
前台进程、后台进程。
CPU密集进程、I/O密集型进程。

进程层次

Unix: init为根，根结束后，其他子进程必须结束。
Windows：也通过复制生成新进程，但是没有相互关系。

进程vs.程序

进程并发。进程动态。进程短暂的生命周期。一个程序多个进程。进程具有创建其他进程的能力。
例子：学生=CPU，课表=程序，每门课=进程。

进程地址空间

进程中的数据的地址是在当前进程的地址空间的位置，而不是物理内存的位置。

进程映像

对进程执行活动全过程的静态描述。用户栈+程序代买+进程控制块

上下文切换

CPU硬件状态从一个进程换到另一个进程。即PCB和CPU寄存器的切换（PC，PSW，通用寄存器等）

线程

共享进程的地址空间。字处理程序、web服务器程序、
并发：线程并发性更高
开销：线程创建简单、线程通信不需要内核介入，效率高。
性能：

和进程（资源拥有+CPU调度单位）相比，线程只是CPU的调度单位，是轻量级的进程。

线程属性

id，状态，保存寄存器，自己的栈指针
共享所在进程的地址空间和资源。

线程实现

用户级（UNIX)

• 优点：内核态只看到进程，线程切换不经过内核态，比较快。
• 缺点：线程的操作在内核态看来都是进程的操作。所以两个线程不能运行在多个CPU上；线程的系统调用大多阻塞的，所以单一线程的系统调用会导致统一进程的其他线程阻塞。

核心级（Windows）

混合型（Solaris）

处理器调度

相关概念

调度算法

调度时机：运行->终止，阻塞->就绪，运行->阻塞，运行->就绪。即内核返回用户态的时候。

调度过程：切换进程（全局页、内核栈和上下文）

例子，A下B上：

1. 保存A
2. 更新A的PCB
3. A移动到适当队列
4. B设置为运行态
5. B的PCB恢复上下文

上下文切换开销

直接+间接（缓存）

算法设计

用户：响应快
系统：公平

衡量指标

吞吐量、周转时间、响应时间，开销

设计需要考虑的问题

方法：抢占式、不可抢占式

批处理系统的调度算法

FCFS，SJF；SRTN，HRRN

交互系统的调度算法

时间片轮转（Round Robin）、虚拟轮转算法（VIRTUAL RR)、最高优先级算法

优先级反转问题：低优先级进程占用了高优先级进程的资源。

临界区：无法共享的资源，只能单独占用。

解决方案：

• 设置优先级上限
• 优先级继承
• 禁止中断

多级反馈队列调度算法(multilevel feedback)

• 多优先级，多队列，多时间片（级别低，时间片大）
• 各级队列按照时间片乱转来调度
• 新进程第一级队列
• 结束时间片进入下一级

设计原则

• 进程尽可能在同一个CPU执行
• 各个CPU负载均衡

Windows线程调度算法

• 提升优先级
• 增加时间片长度

解决“饥饿”现象：使用平衡级管理器。

同步机制

进程互斥

临界资源
临界区：对某个临界资源使用的代码段

进程互斥的软件方案

• Dekker算法
  解决After you问题，1963年，第一个，Dekker使用忙等待/busy waiting（强制轮流）。
• Peterson算法
  enter_region(), leave_region()
  1981年提出。

进程互斥的硬件方案

• 中断屏蔽（开关中断指令）
  简单，限制CPU并发能力，不适用于多处理器，不适用于用户进程。
• “测试并加锁”指令
  TSL指令，通过打开关闭总线。忙等待。
• “交换”指令
  XCHG指令

小结

忙等待：进程在得到临界区访问权之前，持续测试而不做其他事情。

自旋锁（多处理器）。切换处理器的开销大于忙等待开销。
优先级反转是由于临界区保护产生的。

进程同步

多个进程中的事件存在某种时序关系。A进程的运行依赖于B进程的信息，否则进入阻塞态，直到有了信息后进入就绪态。

生产者/消费者问题

或者叫有界缓冲区问题。生产者和消费者都读写buffer。
睡眠sleep()和唤醒wakeup(someone)操作。
SPOOLing中的生产者和消费者。

信号量和PV操作

1965，Dijkstra提出。

PV操作

信号量结构体：count和queue
semaphore s;
操作：init, P(test/up), V(increment/down)
P and V are called by process.
P和 V是原语操作（封中断执行）。
二元信号量到一般信号量。解决同步和互斥问题。

PV解决互斥问题

互斥量mutex（mutual exclusive）
解决同步：两个进程一个P一个V
解决互斥：在一个进程内执行P和V

porducer() {
  P(empty)
  P(mutex)
  insert_item()
  V(mutex)
  V(full)
}

读者和写者问题

读者优先；
写者和其他读者写者互斥；
Linux中的读写锁

管程

信号量有缺点（编写难、易出错）。
1973年提出。
在程序语言中引入高级同步机制。
管程：由关于共享资源的数据结构和在其上的操作的一组过程组成。
进程只能通过调用管程中的过程来间接访问管程中的数据结构，把同步和互斥的实现封装在相应的过程中，这样进程只需要调用过程即可，方便很多。

解决两个问题：

• 互斥
  管程是互斥进入的。管程是一个语言机制，由编译器保证。
• 同步
  条件变量和wait/signal操作。在条件变量上等待。
• 问题
  如果，A进程进入管程后，由于想要使用的过程（p1）的条件c1不满足而调用wait操作等待在c1上，此时会释放互斥权限。
  但是，如果此时B进程进入管程后，使得c1条件满足，则会唤醒(signal)A，那么A和B就会同时在管程中。

hoare管程

后面进程唤醒前面的进程，前面的执行，后面的等待，把后面的进入管程内的紧急等待队列（比管程外的优先级高）。

wait(c), 紧急队列非空，唤醒等待者；否则释放管程互斥权，同时自己进入c链末尾。

signal(c), c链为空，则相当于空操作；否者唤醒第一个等待着，同时自己进入紧急等待队列。

管程的应用

实现：直接构造（高效）或者间接构造（使用已有机制PV等）。

解决生产者消费者问题

C/C++没有管程，JAVA中有实现。

MESA管程

1980年提出。

• Hoare的缺点：两次额外的进程切换。
• 解决：signal -> notify

notify:当一个正在管程中的进程执行notify(c)时，它使得c条件队列得到通知，发信号的进程继续执行。

结果：使得位于条件队列头的 进程在将来合适的时候执行。由于不是立刻执行，所以不能保证条件满足。所以将来唤醒前，需要重新检查（用while循环代替if语句）。

• mesa缺点
  多了对c的一次额外检测。
• 改进
  • 添加监视计时器，防止饥饿现象。
  • broadcast：全部激活。一个进程不知道有多少个进程被激活或者应该激活哪一个。

MESA一般认为优于Hoare。
PThread 是一个MESA过程。

进程间通信IPC

【目的】解决PV和管程不能传递大量信息的问题 。
管程不能适用于多处理器。

消息缓冲区

陷入内核 ，复制消息（到缓冲区），消息入队，复制消息（到接收）

共享内存

管道通信方式

存储管理

地址重定位

• 程序要进内存
• 多道程序设计模型
• 每个进程有独立的地址空间（不能互相访问）
  解决：如何把进程地址空间 合理装入 内存

代码段、数据段、堆-（共享库、内存映射文件等）-栈

所以进程中的地址不是最重的物理地址，进程运行之前无法计算出物理地址。
需要地址重定位的支持。

• 逻辑地址（相对地址、虚拟地址）：首地址为零，其余地址都是相对于首地址的编址。
• 物理地址（绝对地址，实际地址）
  地址重定位：逻辑->物理

静态重定位：（软件实现）

动态重定位：执行过程中逐条指令执行时完成转换（硬件）

MMU：内存地址单元（将虚拟的内存地址翻译成实际的物理地址）

空闲内存管理

• 等长划分：bitmap
• 不等长划分：空闲区表、已分配表。空闲区链表。

内存分配算法

• 首次适配：每次都从表头
• 下次适配：
• 最佳适配：找到最小的合适的
• 最差适配：找到最大的合适的。

然后：把该分配区分成两部分：一部分给程序；剩下的重新分配。

回收内存算法

主要考虑合并：上相邻、下相邻、上下都相邻、都不相邻

伙伴系统（Linux底层管理内存的方案）

最佳适配。
分配时检查大小，小于一半则分成伙伴；
合并时检查伙伴是否空闲，空闲则合并。

内存管理方案

进程是基本加载单位。

单一连续区

【特点】一段时间内只有一个进程在内存。简单，但是内存利用率低。

固定分区

分区大小不同。不同大小的进程进入不同的区的链表。（最早的手机）

可变分区

根据内存需要，分给进程，剩余的成为新的空闲区（洞）。
【问题】外碎片，导致内存利用率下降。
【解决方案】紧缩（压缩、搬家、紧致）技术：在内存中移动进程。

• 系统开销：少搬家。
• 移动时机：比如正在I/O的进程不能搬家。

以上三种传统的方案一个进程占据内存中的一块连续区域，以下三种则进入内存中若干不连续区域。

页式

用户进程地址分块，称为页/页面
内存空间按同样大小分块，称为叶框。
分配时，逻辑相邻，但是物理不一定相邻。
典型页面大小：4K/4M
逻辑地址：页号+页内偏移。（自动划分）

• 页表：记录映射关系。页表项。一个进程一张表，放在内存。页表的起始地址放在那里呢？我们知道一个进程上CPU，这个CPU的若干个寄存器就要给这个进程使用。所以页表首地址推送到某个寄存器中。下CPU后，保存在PCB中。CPU用页号查页表，得到叶框号，再与页内偏移拼接成物理地址。

• 内碎片：比如一个需要5页+1条指令的进程，由于这个内存管理方案模型的局限性，也需要分配给6页。

段式

用户地址空间，按照程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名。
内存空间，被分成长度不等的区域，称为物理段。

逻辑地址：段号+段内偏移。（手动划分）

• 段表

段页式存储

交换技术

内存不足怎么办？大地址空间装入小内存。

覆盖技术

把不会同时执行的程序段共享同一块内存（程序员自己声明，即所谓的对用户不透明），用于早期系统。

交换技术

交换到外存。

• 交换内容：动态创建修改的内容，主要是栈和堆。
• 交换位置：交换区。包含了一部分连续磁道。(windows: 页文件）
• 交换时机：内存不够时。
• 考虑进程的属性

进程增长问题：预留空间

虚拟存储技术

• 进程的一部分代码和数据装入内存，另一部分留在磁盘。
• 所以采用虚存技术的操作系统，进程的地址空间称为虚拟地址空间。
• 虚存空间在哪里呢？
  一部分在内存，一部分在磁盘。
• 计算机的存储体系：寄存器-Cache-内存-磁盘
• 虚存的大小受到计算机体系的限制，32位机最大2^{32，64位机最大2}64。
• 地址保护
• 虚拟页式存储。
• 请求调页
• 预先调页

页表和页表项的设计

• 页表项（由硬件设计的）

  • 叶框好
  • 有效位：内存还是磁盘上？
  • 访问位：1表示最近访问过，定期清零
  • 修改位：是否被修改过？
  • 保护位：读写权限

• 页表
  单一进程的页表页太大，无法一次性放入内存。如果页表页在内存中不连续皴法，则需要引入页表页的索引表，即页目录。多级页表。
  Core I7是4级页表。可以表示2^48的内存地址空间。

• 反转页表
  为了解决页表太大的问题，我们从物理地址出发，系统建立一张页表。
  页表项记录了进程i的某虚拟地址（虚页号）和页框号的映射关系。
  多用于64位机子，PowerPC/UltraSPARC/IA-64等的体系结构。
  查找通过hash实现。

MMU

地址转换

快表

• 加快地址映射的速度。
• 程序访问的局部性原理，引入快表（TLB-Translation Look-aside Buffers)
• 在CPU中引入高速缓存（Cache），可以解决CPU和内存的速度矛盾。
• 并行查找。利用硬件接线逻辑，能按照特定的匹配标志，在一个存储周期内对所有的字同时进行比较。
• 容量有限。保存正在运行的页表的子集。

页故障

• 地址转换中，硬件产生了异常。
• 缺页异常（虚拟页面还没有调入内存）
• 违反权限
• 错误的访问地址

缺页异常

• 空闲内存够则填入。
• 内存不够则置换。

软件策略

• 驻留集
  给每个进程多少个叶框
• 置换问题
  固定分配或者可变分配
  局部置换或者全局置换
• 置换策略
  置换最近最不可能访问的页。但太精细会导致软硬件开销大。
  被锁定的叶框不能置换，添加锁定位。
• 清除策略
  虚拟页式系统的最佳工作状态：发生缺页异常时，系统中有大量的空闲页框。
  设计一个分页守护进程，定期唤醒检查内存的状态，维护一个空闲叶框集。保证空闲叶框是“干净”的。
  页缓冲技术。定期写入磁盘，减少I/O同时，如果进程需要使用页缓冲中的页框，也可以很容易的拿到。

置换算法

• 最佳页面置换算法
  【原理】置换以后不再需要或者最远的将来才会用到的页面。
  【问题】需要知道算法的流程。
• FIFO
  【原理】置换驻留时间最长的页。
  【实现】页面链表。
• 第二次机会算法（SCR）
  【原理】先FIFO，然后检查访问位。
• 时钟算法（CLOCK)
  【原理】环形链表
• 最近未使用算法
  检查R和M位。
• 最近最少使用算法（LRU）
  【原理】选择最后一次访问时间距离当前时间最长的页面并置换。即置换未使用时间最长的一页。
  【方法】时间戳，所以开销大。性能接近OPT
• 最不经常使用算法（NFU）
• 老化算法（AGING）
• BELADY现象
  FIFO算法，叶框多，反倒导致缺页数增加。
• 工作集算法
  影响缺页次数的因素：算法、页面大小、程序编制；分配给进程的叶框数量。
  颠簸（抖动）：虚存当中，调度时间大于进程实际运行时间。
  页面尺寸：Intel 80x86/Pentium: 4096 or 4M
  最优页面大小
  工作集：一个进程 当前 正在使用的页框集合
  工作集的大小受到：工作集窗口个大小的影响。
  windows中，定时运行页面监测程序，如果遇到异常，调用工作集算法进行置换。

其他相关技术

内存映射文件

由于虚存包括内存+磁盘，所以实际在操作文件时，可以把文件的一部分映射到虚存中。然后对文件的操作就相当于对内存的操作。

写时复制技术

文件

概述

进程是对CPU的抽象，地址空间是对内存的抽象，文件是对磁盘的抽象。
名字空间映射到磁盘空间

• 文件分类
  普通文件、目录文件、特殊（设备）文件

把各种设备抽象为文件有利于提供一个统一的I/O接口，如字符设备文件或者块设备文件。

• 文件逻辑结构
  • 流式文件：单位是字符
  • 记录文件：单位是记录

存储介质

磁盘物理地址的形式：磁头号（盘面号）、磁道号（柱面号），扇区（512bytes）号
扇区：标题（10bytes)、数据（512）、ECC纠错信息（12-16)
访盘过程：寻道（沿半径移动找到磁道）、旋转（磁盘旋转找到扇区）、传输
SSD只有传输过程。

磁盘空间管理

• 位图
  一个物理块对应一位
• 空闲块表
• 空闲块链表

系统启动后，专用块在内存中。

文件控制块和文件目录

文件目录有目录项（FCB）组成。

文件的物理结构

• 顺序结构（快，但容易有碎片，不能增长）
• 链接结构（利于插入删除，但存取速度慢，不适用于随机存取，链接指针占用一定空间）
• FAT（文件分配表）
  表项的值有三种：0（空），下一块号，-1（最后）
  文件的起始块号：在FCB中，后面的通过链来找。
• 索引结构
  索引表是地址数组。第i个条目指向文件的第i块。
  由于大小不一样，不宜放在FCB中。
  所以把索引表所在的块号放在FCB中。
  优点：技能顺序存取，也能随机存取。可以动态增长。
  缺点：寻道次数多，开销大。
  索引表的组织方式：链接方式、多级索引、综合模式。
• UNIX是三级综合索引模式。
  • 每个文件主索引表有15项，每项两个字节。
  • 前12个存放文件的物理块号（直接寻址）。
  • 接下来一个是指向了一级索引表（256个块号）；
  • 还不够，第14个指向二级索引表，每个指向256个一级；
  • 还不够第15个指向三级，每个指向256个二级，每个二级又指向256个一级索引表。

文件系统的实现

• 磁盘分区
• 文件卷：逻辑分区，同一个文件卷使用同一份管理数据。由若干块构成，包括文件系统信息、一组文件、未分配空间。
• 格式化：在一个文件卷上建立一个文件系统。

磁盘上内容

• 引导区
• 卷信息
• 目录文件
• 用户文件

UNIX文件系统

• FCB=目录项+i节点
• 每个文件由FCB和若干磁盘块构成
  读文件过程：根目录区 -- I节点 - 磁盘块中的文件内容

文件系统 II

FAT16

• 文件系统的数据记录在“引导扇区”中（UNIX在超级扇区中）
• 文件分配表：描述醋的分布和下一块。
• FAT16中，每个表项2个字节（16位）
• 目录项：32字节
• FAT16中，根目录大小固定
• 主引导记录 - 0号扇区（MBR）
• 每个分区的引导扇区（DBR），关键是BIOS参数块
• 在FAT中，FCB = 目录项

FAT32

• 根目录大小不固定
• 支持UNICODE
• 长文件名的实现
  • 可变长目录项
  • 固定长度目录项：每个目录项通过指针指向堆中存放的文件名
• FAT32中，通过占据多个目录项（一短+多长）实现。

文件操作

• 创建文件
  创建目录项、填写内容，分配空间，具体：1、检查参数合法性；2、申请空闲目录项；3、为文件申请磁盘；4、返回
• 打开文件
  在文件目录中检索，读入内存，建立相应的数据结构，返回文件描述符/文件句柄。具体：1、查找目录项（树形结构）；2、系统打开文件表；3、根据打开方式，检查操作合法性；4、用户打开文件表
• 指针定位
  每次操作后，修改定位指针。
• 读文件
  1、得到文件描述符，确认合法性；2、将文件的逻辑块号转换为物理块号。3、申请缓冲区；4、启动磁盘I/O操作，把磁盘块内容读入缓冲区，再传入指定的内存区。5、反复进行。
• 如何通过系统调用直接rename（比使用基本的文件操作搭建更快）
  1、查找目录项；2、直接修改目录项（FCB）

文件系统的可靠性

• 坏块问题

• 备份
  全量转储 + 增量转储

• 文件系统的不一致
  磁盘块 - 内存 - 写回磁盘块
  UNIX中， 使用两张表，每块对应一个表中的计数器。（在文件/空闲块表中出现的次数）

文件的保护机制

• 身份验证
  口令、密码、指纹、虹膜
• 访问机制
  访问控制表（文件） + 能力表（用户）

UNIX中的文件访问控制

• 用户身份识别
• 操作识别

文件系统的性能

磁盘访问是瓶颈。

• FCB分解法、当前目录、磁盘碎片整理等已经介绍过。

• 块高速缓存
  利用局部性原理，在内存中为磁盘设置缓冲区，保存了若干块副本（逻辑上属于磁盘）。
  如何实现：双向链表，使用后挂到链尾。快速查找则利用hash。
  如何置换：cache manage。

• 合理分配磁盘空间
  把有可能顺序存取的块放在一起，减少磁臂移动。
  例如，UNIX中把i节点区分成几部分，放在各个柱面组。

• 磁盘调度
  多个访盘请求等待时，采取策略调整顺序，降低平均磁盘服务时间。
  一次访盘时间：寻道+旋转延迟+传输数据
  FCFS：简单公平；但是效率低，容易反复寻道。
  最短寻道时间优先：改善平均服务时间；但是容易饥饿。
  扫描算法（电梯算法）
  单项扫描算法：减少新请求的延迟
  N步扫描算法：多个队列，克服磁头臂粘性
  FSCAN策略：两个队列
  旋转调度算法：根据延迟时间。用扇区号，扇区一样的话，第二个比好意思，等一圈之后在最后来处理。

• 信息优化分布

• 记录的成组与分解

• RAID技术
  独立磁盘冗余阵列，多个盘构成一个存储空间（逻辑卷）。数据可以跨盘并行存放（数据分条）
  简单：镜像
  复杂：块交错校验
  RAID 0：条带化，性能最快
  RAID 1：镜像：最大限度保存数据安全。
  RAID 4：交错块奇偶校验

I/O系统

概述

特点

• 系统性能瓶颈
• 造成OS复杂庞大
  • 速度差异大
  • 接口复杂
• 与其他功能相关

设备分类

• 按数据
  块设备，字符设备

• 按资源分配
  独占设备，共享设备（硬盘），虚设备（SPooling）

目标

• 控制设备的各种操作，完成I/O设备与内存的数据交换
  设备分配和回收，执行设备驱动程序、设备中断处理、缓冲区管理
• 建立方便、统一独立的设备接口
  用户使用逻辑设备，操作系统操作物理设备
• 提高CPU与设备、设备与设备之间的并行工作能力。
  并行性、均衡性。
• 保护

组成

• 机械部分
• 电子部分
• 设备接口--控制器
  将命令写到控制器的接口寄存器，实现输入/输出，并从接口寄存器读取状态信息或者结果信息。
  控制器可独立CPU运行，命令完成，产生中断。
  控制器与设备之间通常是低级借口。
  按位组装成字节块，校验，然后复制到内存中。
• I/O端口地址
  寄存器的地址；I/O端口空间。
• I/O独立编址
  与内存完全独立
• 内存映像编制
  和内存统一编址。
  优点：内存指令可以用于控制寄存器。
  缺点：不能对控制寄存器高速缓存。

I/O控制方式

• 可编程I/O（轮询）
• 中断驱动I/O
• DMA
  直接内存存取（专门控制器，无需CPU干预）

I/O软件

• 分层设计
  外部设备：逻辑 - 驱动 - 调度 - 硬件
  文件系统：目录管理 - 文件系统逻辑结构 - 物理磁盘组织 - 驱动- 调度- 硬件
• 设备独立性
  用户编写的程序可以访问任何I/O设备，无需事先制定设备。

I/O缓冲技术

凡是数据到达和离去速度不匹配的地方都采取缓冲技术
提高并行化能力

• 分类
  硬缓冲：由硬件寄存器实现（显卡缓存）
  软缓冲：在内存中开辟空间。
• 管理
  单缓冲、双缓冲、缓冲池
• 例子：键盘驱动程序
  任务一：收集字符
  公共缓冲池（驱动程序中）
  终端数据结构缓冲

I/O设备管理的数据结构

死锁

基本概念

进程进入了等待状态

• 可重用资源：可抢占（CPU）、不可抢占（打印机）
• 可消耗资源：中断、消息、信号灯

活锁

如果是轮询类的算法，进程有机会上CPU（不阻塞），但是没有进展。（如peterson算法）

饥饿

资源费配策略导致的。

死锁发生的必要条件

• 互斥使用
  资源独占
• 占有且等待
  进程新申请资源同时对原来资源的占有
• 不可抢占
  进程不能抢占
• 循环等待

资源分配图（RAG）

使用有向图描述系统资源和进程状态
节点是进程或者资源
边：分配边或者申请边

死锁定理

资源分配图中没有环路，就没有死锁
有环路，可能存在死锁。
但是，如果只有一个资源实例，则变为充分必要条件。

解决死锁

不理

死锁预防（静态）

破坏四个必要条件之一

• 把独占资源变为共享资源（打印机的SPOOLing技术）。
• 一次性申请所有资源、一次性分配；进入阻塞之前，放弃所有资源。
• 操作系统帮助进程抢占资源。
• 定义资源类型的线性顺序实现。把资源编号，有序分配。经常使用的资源放前面，偶尔使用的放后面。（哲学家就餐问题）

避免（动态）

对资源申请进行动态检查。分成几个区域。（系统）安全状态和（进程）安全序列。
安全状态没有死锁。
不安全状态一定会导致死锁发生。

银行家算法（Dijkstra提出）

检测和解除

允许死锁发生， 但是系统不断监视死锁发生了没有。一旦发生，解除死锁。

• 检测时机
  进程进入等待（开销大）。
  定时检测。
  资源率太低了。
• 简单监测算法
  资源分配表+进程等待表。
• 解除
  撤销所有死锁进程；进程回退再启动；逐一撤销死锁进程；逐一抢占资源。

哲学家就餐问题

5个哲学家，5支筷子。
回忆对比读者/写者问题和生产者/消费者问题。

解决

• 最多允许4个哲学家。
  引入额外的信号量限制最多4个哲学家。
• 仅当两边都有筷子时才允许拿筷子。
• 编号，奇数先拿左边，偶数先拿右边。