《王道考研 · 操作系统》
写在前面
参考书目 & 课程：王道考研 · 操作系统
在刷课的时候为了保持注意力集中写的一些简单记录，尤其记录了一些不熟悉的部分。在描述的过程中用的是通俗的语言，因此可读性可能没有那么强。
仅作为个人学习记录，便于遗忘之后快速回忆。并不推荐作为教学内容阅读。
1 开篇
操作系统：1）控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源分配；2）以提供给用户和其他软件的接口和环境；3）是计算机系统中最基本的系统软件。
功能和目标：1）作为系统资源管理者，负责处理机、存储器、文件和设备的管理；2）作为用户和硬件之间的接口，提供命令接口（联机/脱机）、程序接口、GUI；3）作为最接近硬件的层次，实现对硬件机器的拓展。
联机命令接口，即交互式命令接口，例如在cmd中执行代码。
脱机命令接口，即批处理命令接口，例如运行.bat文件。
程序接口，例如调用.dll文件，由一组系统调用组成，只能通过用户程序间接使用。
四个特征：并发、共享、虚拟、异步。
并发：两个或多个事件在同一时间间隔内发生，宏观上同时发生，微观上交替发生。（单核多进程）
并行：两个或多个事件在同一时刻发生。（多核多进程）
共享：系统中的资源可供内存中多个并发进行的进程同时使用。分为互斥共享与同时共享。
虚拟：把一个物理上的实体变为若干个逻辑上的对应物。分为空分复用与时分复用。
异步：允许多个程序并发执行，但由于资源有限，进程执行的速度不可预知。
运行机制和体系结构
中断和异常
发生中断就意味着需要操作系统介入，CPU切换到核心态进行，当前进程暂停运行由操作系统内核对中断进行处理（比如进程切换、分配I/O设备等）。
CPU从用户态切换到核心态是通过中断实现的，并且中断是唯一途径。（通过执行特权指令修改程序状态字PSW的标识位）
系统调用：
应用程序通过低通调用请求操作系统的服务，凡是与资源有关的操作都需要向系统提出请求，可以保证系统的稳定性和安全性。
传递系统调用参数 -> 执行陷入指令（用户态） ->执行系统调用相应服务程序（核心态） -> 返回用户程序
陷入指令是唯一一个能在用户态执行的特权指令。
进程
进程实体 = PCB + 程序段 + 数据段
PCB进程控制块，用来描述进程的信息，是进程存在的唯一标志
进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
包括执行指针、就绪表指针、阻塞表指针。链接方式与索引方式不同就在于指向的是队列还是索引表。
进程的状态与转换
进程控制 - 实现进程状态转换
状态转换需要修改PCB，通过原语实现，确保控制不被中断。
原语功能：1.更新PCB信息 2.将PCB插入合适队列 3. 分配/回收资源
进程通信
进程是分配系统资源的单位，因此各进程拥有的内存地址空间相互独立。为保证安全，一个进程不能直接访问另一个进程的地址空间。因此需要进程通信。
1. 共享存储
2. 管道通信
管道只能采用半双工通信。如果要实现双向同时通信，则需要两个管道。
各进程互斥地访问管道。
数据以字符流的形式写入管道，当管道写满时，写进程的write()系统调用将被阻塞。当读进程将数据全部取走后管道变空，此时读进程的read()系统调用将被阻塞。
没写满不允许读；没读空不允许写。
数据一旦被读出就从管道中被抛弃，因此读进程最多只能有一个。
3. 消息传递
以格式化的消息为单位，通过“发送消息/接收消息“两个原语进行数据交换。
线程
线程：是一个基本的CPU执行单元，是程序执行流的最小单位。
引入线程后，进程只作为除CPU之外的系统资源的分配单元。进程是资源分配的基本单位，线程是调度的基本单位。
同一进程内的线程切换不需要切换进程环境，系统开销小。
通过TCB来控制线程，进行就绪、阻塞、运行的状态转换。
线程几乎不拥有系统资源，同一进程的不同线程之间共享进程的资源。
分为用户级线程（线程管理由应用程序负责，在用户态下即能完成线程切换），内核级线程（线程管理由操作系统内核负责，在核心态下完成）
注意：操作系统只能看到内核级线程，因此只有内核级线程才是处理机分配的单位。
调度的三个层次
1.高级调度（作业调度），按一定原则从外存上处于后被队列的作业中挑选，分配资源，并建立进程，使其获得竞争处理机的权利（外存 – 内存）
2.中级调度（内存调度），决定将挂起状态的进程重新调入内存。（系统将暂时不能运行的进程调至外存等待（挂起），等它具备运行条件且内存空闲时再重新调入内存。为了提高内存利用率和系统吞吐量。注意PCB会常驻内存，放入挂起队列。）
3.低级调度（进程调度），从就绪队列中选取进程，分配处理机。
进程调度
临界资源：一个时间段内只允许一个进程使用的资源。
临界区：访问临界资源的那段代码。
内核程序临界区一般是用来访问某种内核数据结构的（例如进程的就绪队列）。内核程序临界区访问的临界资源应当尽快释放，保证其他工作，因此访问期间不能进行调度与切换。
调度算法的评价指标：
1）CPU利用率 = 忙碌时间 总时间
2）系统吞吐量 = 总完成作业数 / 总耗时
3）周转时间 = 作业完成时间 – 作业提交时间
带权周转时间 = 作业周转时间 / 作业实际运行事件
4）等待时间，指处于等待处理机状态时间之和。对进程来说，就是建立后等待被服务的时间之和；对作业来说，不仅要考虑上述等待时间，还要加上再外存后被队列中等待的时间。
5）响应时间，从提交请求到首次响应所用时间
调度算法
抢占式的短作业优先算法（最短剩余时间优先算法）：每当有进程加入就绪队列改变时（或进程完成时）就需要调度，若新到达进程剩余时间更短，则新进程抢占处理机。
以上三种适用于早期的批处理系统。
抢占式优先级调度算法：每次调度时选择当前已到达且优先级最高的进程。
优先级：1. 系统进程 > 用户进程 2. 前台进程 > 后台进程 3. I/O繁忙型进程 > CPU繁忙型进程
设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。
进程互斥
对临界资源的互斥访问，逻辑上分为进入区（上锁）、临界区、退出区（解锁）、剩余区。
原则：1.空闲让进（临界区空闲时，应允许一个进程访问） 2.忙则等待（临界区正被访问时，其他进程需等待） 3.有限等待（不会饥饿） 4.让权等待（进不了临界区的进程要释放处理机）
软件实现方法：
1）单标志法。两个进程在访问完临界区后会把权限转交给另一个进程。
一定是按照P0 -> P1 ->P0 ->P1 …
如果P0一直不进入临界区（例如CPU一直被分配给其他进程），则P1一直拿不到权限，违背了空闲让进原则。
2） 双标志先检查法。利用数组元素来标记各进程进入临界区的意愿。
若按1 5 2 6 3 7…的顺序执行，则P0和P1将会同时访问临界区。违背忙则等待原则。
原因在于它的检查和上锁不是原子操作，中间可能发生进程切换。
3）双标志后检查法。
若按照1 5 2 6 …顺序执行，则P0和P1都无法进入临界区。违背空闲让进和优先等待原则。
4）Peterson算法。
但是仍然未遵循让权等待的原则。
硬件实现方法：
1）中断屏蔽方法
利用“开/关中断指令“实现。
简单高效；单不适用于多处理机，只适用于操作系统内核进程，不适用于用户进程。
2）TestAndSet指令（TS指令或TSL指令）
用硬件实现上锁并检查的原子过程。
实现简单，适用于多处理机；不满足让权等待原则。
3）Swap指令（Exchange指令或者XCHG指令） - 类似TS。
信号量机制
信号量其实是一个变量，可以用一个信号量来表示系统中某种资源的数量。用PV原语来对信号量进行操作。
1）整型信号量
可以进行初始化、P操作、V操作。类似双标志法，但是是原语。不满足让权等待。
2）记录型信号量
block原语是从运行态转换为阻塞态，主动放弃CPU；wakeup原语唤醒等待队列中的第一个进程，从阻塞态转换为就绪态。
实现进程互斥：
1）分析并发进程的关键活动，划定临界区
2）设置互斥信号量mutex，初值为1
3）在临界区前执行P(mutex)；在临界区后执行V(mutex)
注意对不同的临界资源设置不同的互斥信号量。
实现进程同步：
1）分析什么地方需要实现同步关系
2）设置同步信号量S，初值为0
3）在“前操作”之后执行V(S)
4）在“后操作”之后执行P(S)
实现前驱关系：
生产者消费者问题
多生产者多消费者问题
原因在于本题的缓冲区大小为1，任何时刻三个同步信号量中最多只有一个是1。如果缓冲区大于1，则必须设置mutex来互斥。
吸烟者问题
读者-写者问题
1）允许多个读者可以同时对文件执行读操作
2）只允许一个写者往文件中写信息
3）任一写者在完成写操作之前不允许其他读者或写者工作
4）写者执行写操作前，应让已有的读者和写者全部退出
用mutex来实现count的检查和赋值一气呵成完成。
为了解决写进程“饿死”的问题，修改代码如下：
哲学家进餐问题
解决方案1：添加限制条件，例如最多允许四个哲学家同时进餐
解决方案2：要求奇数号哲学家先拿左边筷子，偶数号哲学家相反。
解决方案3：
管程
管程：由编译器实现各进程互斥地进入管程中的过程。
1）局部于管程的共享数据结构说明
2）对该数据结构进行操作的一组过程
3）对局部于管程的共享数据设置初始值语句
4）管程有一个名字
基本特征：
1）局部于管程的数据只能被局部于管程的过程所访问
2）一个进程只有通过调用管程内的过程才能进入管程共享数据
3）每次仅允许一个进程在管程内执行某个内部过程
死锁
死锁：各进程相互等待对方手里的资源，导致阻塞无法推进
产生条件：互斥条件、不剥夺条件、请求和保持条件、循环等待条件
注意：发生循环等待时未必死锁，发生死锁一定有循环等待
处理策略：预防死锁（破坏必要条件）、避免死锁（防止进入不安全状态，例如银行家算法）、检测和解除（发生后处理）。
1）预防死锁（静态策略）
a）破坏互斥条件。改为允许共享使用，例如SPOOLing技术，把独占设备改成共享设备。但很多时候无法破坏互斥条件。
b）破坏不剥夺条件。例如主动释放/操作系统剥夺调度。但较复杂、可能造成前阶段工作的失效，降低系统吞吐量，可能导致饥饿。
c）破坏请求和保持条件。例如采用静态分配方法（一次申请完所有资源）。资源利用率低，可能导致饥饿。
d）破坏循环等待条件。例如顺序资源分配法（给资源编号，同类资源一次申请完）。不方便增加新设备，若实际使用顺序和编号递增顺序不一致可能导致资源浪费，编程麻烦。
2）避免死锁（动态检测）- 银行家算法
安全序列：按这种序列分配资源，每个进程都能顺利完成。
如果系统进入不安全状态，可能发生死锁。
3）检测和解除
a）检测：
如果能消除所有边，则这个图是可完全简化的。若图不可完全简化，就一定发生了死锁。
b）解除：根据进程优先级、已执行时间、还有多久完成、已使用多少资源、交互式还是批处理式来决定接触哪个死锁进程。
资源剥夺法。挂起某些进程并抢占资源。注意防止挂起进程饥饿。
撤销进程法。强制撤销部分、甚至全部死锁进程，并剥夺资源。可能付出较大代价。
进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。记录进程历史信息，设置还原点。
内存
链接：
1）静态链接，程序运行前链接，之后不再拆开。
2）装入时动态链接，边装入边链接。
3）运行时动态链接，程序执行中需要目标模块时才进行链接，便于修改和更新，便于实现对目标模块的共享。
内存管理
连续分配管理方式：
1）单一连续分配
内存被分为系统区和用户区。系统区常位于内存低地址部分。内存中只能有一道用户程序，独占整个用户区空间。
优点无外部碎片，可采用覆盖技术扩充内存，不一定需要采用内存保护。缺点只适用于单用户、单任务，有内部碎片，存储器利用率极低。
2）固定分区分配
将用户空间划分为固定大小的分区，每个分区只能装入一道作业，分区大小可以相等/不等。
分区大小相当时，缺乏灵活性，但适合一台计算机控制多个相同对象；分区大小不等时，增加了灵活性，可满足不同大小进程需求。
需要建立分区说明表，来记录分区大小、起始地址、状态。
优点无外部碎片。缺点若程序太大所有分区都无法满足时，不得不采用覆盖技术，会降低性能；会产生内部碎片，内存利用率低。
3）动态分区分配（可变分区分配）
根据进程大小动态地建立分区。采用空闲分区表、空闲分区链来记录内存的使用情况。使用一定动态分区分配算法来进行分配。没有内部碎片，有外部碎片。可以通过紧凑技术来解决外部碎片，但时间代价高。
动态分区分配算法：
非连续分配管理方式：
1）基本分页存储管理
将内存空间分为大小相等的页框（页帧/内存块/物理块），页框号从0开始。
将用户进程的地址空间分为与页框大小相等的页（页面），页号从0开始。
物理地址 = 页面始址 + 页面偏移量
页号 = 逻辑地址 / 页面长度（取整）
页内偏移量 = 逻辑地址 % 页面长度
计算机对二进制数进行处理，页面大小往往为2^n，因此会呈现出逻辑地址低n位表示页内偏移量，余下高位表示页号。
为了得知页面的起始地址，系统为每个进程建立了页表。因此首先根据地址计算出页号，然后查询页表获得块号，起始地址 = 块号 * 内存块大小。
注意每个页表项的长度是相同的，可以通过内存大小和页面大小得到页表项的大小。
基本地址变换机借助页表将逻辑地址转为物理地址，通常用页表寄存器PTR存放页表在内存中的起始地址F和页表长度M。进程未执行时，F和M存放在PCB中，在进程被调度时，会被放入PTR。
具有快表的地址变换机构：时间局部性、空间局部性。因此引出快表（联想寄存器TLB）。
两级页表：单级页表必须连续存放，且没必要让整个页表常驻内存，因此引入两级页表。
因为没有必要让整个页表常驻内存，因此在页表项中添加标志位表明是否调入内存即可。
注意：若采用多级页表，则各级页表大小不能超过一个页面。注意两级页表的访存次数分析。
2）基本分段存储管理
按程序自身逻辑划分为若干段，每段从0开始编址；以段为单位分配内存，各段之间可以不相邻。
逻辑地址 = 段号（段名）+ 段内地址（段内偏移量）
段号的位数决定了每个进程最多可以分几段，段内地址位数决定了每段的最大长度。
页是信息的物理单位，对用户是不可见的；段是信息的逻辑单位，对用户是可见的。
分段比分页更容易实现信息的共享和保护。
不能被修改的代码（纯代码/可重入代码，不属于临界资源）是可被共享的。
3）段页式存储管理
分段对用户是可见的，需要显式给出段号、段内地址；系统会自动根据段内地址划分页号和页内偏移量。
从逻辑上对内存空间扩充
1）覆盖技术：解决程序大小超过物理内存总和的问题。将程序分为多个段，常用的段常驻内存，不常用的段在需要时调入内存。缺点是对用户不透明，需要由程序员声明覆盖结构。
2）交换技术：进程在内存与磁盘间动态调度。
通常把磁盘空间分为文件区和对换区。文件区主要存放文件，追求存储空间利用率，采用离散分配方式；对换区存放被换出的进程数据，追求换入换出速度，采用连续分配方式。
在多进程进行且内存吃紧时进行交换。
可优先换出阻塞进程；可换出优先级低的进程；可考虑进程在内存的驻留时间。注意PCB会常驻内存。
3）虚拟内存技术
传统存储管理（连续分配/非连续分配）作业必须一次性全部装入内存才能开始运行，这会导致大作业无法运行或多道程序并发度下降；驻留性，会一直驻留内存知道作业运行结束。
局部性原理（时间+空间）指出，刚访问过的、临近的存储单元很可能在不久后被访问（因为循环和数据连续存放），因此会有高速缓冲技术、快表机制等应用。
基于局部性原理，可以将很快会用到的部分装入内存；当访问的信息不在内存时，OS负责调入；当内存空间不够，OS负责将暂时不用的信息换出。
虚拟内存的最大容量是由计算机的地址结构（CPU寻址范围）确定的。
虚拟内存的实际容量 = min {内存+外存，CPU寻址范围}
特征：多次性、对换性、虚拟性。
a）请求分页存储管理：
缺页中断机构：当请求的页面不再内存时，产生一个缺页中断，缺页的进程阻塞，调页完成后再唤醒。如果内存中有空闲块则分配；若无则由页面置换算法淘汰一个页面。
注意换入/换出操作都需要启动I/O操作。
页面调入内存后，需要修改慢表，同时也要将表项复制到快表。
页面置换算法：
a）最佳置换算法OPT：即快表满时，往后看（当前内存块中的页号）哪个是最后出现的。
b）先进先出置换算法FIFO：每次淘汰最早进入内存的页面。Belady异常，当为进程分配的物理块数增大时，缺页次数不减反增。
c）最近最久未使用置换算法LRU。在页表项中用访问字段记录该页面自上次被访问以来所经历的时间t，每次淘汰t最大的页面。手动做题时，可以逆向扫描淘汰最后一个出现的页号。
d）时钟置换算法CLOCK（最近未用算法NRU）。
页面分配策略：
驻留集：请求分页存储管理中给进程分配物理块的集合。
因此针对驻留集的大小，产生固定分配和可变分配两种分配策略。同时还有局部置换（缺页时只能选进程自己的物理块）和全局置换（可以将OS保留的空闲物理块分配给缺页进程，也可将别的进程持有物理块置换到外存再分配给缺页进程）两种置换策略。
固定分配局部置换：缺点是难以确定为每个进程分配多少物理块才合理。
可变分配全局置换：只要缺页就分配新的物理块。缺点是被选中的进程物理块减少，缺页率增加。
可变分配全局置换：一开始为每个进程分配一定数量物理块，缺页时只允许淘汰该进程自己的物理块；若出现频繁缺页，系统会为进程多分配物理块，直到缺页率趋势适当；若缺页率极低，则适当减少分配给该进程的物理块。
何时调入页面：
预调页策略：预测不久后可能访问的页面，预先调入内存，但目前成功率仅50%，主要用于进程的首次调入，由程序员指出。
请求调页策略：运行期间发现缺页才进行调入。缺点是I/O开销较大。
从何处调入页面：
（对换区空间足够/不足）
（UNIX方式）
抖动（颠簸）现象：页面反复出入内存，主要原因是进程频繁访问的页面数目高于可用的物理块数。由此提出工作集的概念：指某段时间间隔内，进程实际访问页面的集合（因为重复访问，大小可能小于窗口尺寸）。由工作及大小来确定驻留集大小（驻留集 >= 工作集，否则会抖动）
b）请求分段存储管理
c）请求段页式存储管理
地址转换（逻辑地址->物理地址）
1）绝对装入，编译时产生绝对地址的目标代码。只适用于单道程序环境。
2）静态重定位（可重定位装入），由装入程序进行地址变换。一个作业装入时，必须分配要求的全部内存空间；一旦作业进入内存，运行期间就不能再移动，也不能再申请内存空间。
3）动态重定位（动态运行时装入），程序真正要执行时才进行地址转换。需要重定位寄存器的支持，允许程序在内存中发生移动。
内存保护
设置一对上下限寄存器，或采用重定位寄存器和界地址寄存器。
文件管理
文件属性：文件名（同一目录下不允许重名文件）、标识符、类型、位置、创建时间、上次修改时间、文件所有者信息、保护信息。
逻辑结构：
无结构文件（由二进制或字符流组成）
有结构文件（由一组相似记录组成，记录是一组相关数据项集合，数据线是文件系统中最基本的数据单位）。一般来说每条记录都有一个数据项作为关键字。可分为定长记录、可变长记录。
索引文件：为文件建立索引表，每个记录对应一个索引表项
索引顺序文件：为文件建立索引表，但是一组记录对应一个索引表项
多级索引文件：
文件目录
文件控制块：FCB包含了文件的基本信息，一个FCB就是一个文件目录项，实现了文件名到文件之间的映射。
目录结构：
1）单级目录结构。整个系统只建立一张目录表，实现了“按名存取”，但不允许文件重名
2）两级目录结构。分为主文件目录MFD和用户文件目录UFD，允许不同用户的文件重名。
3）树形目录结构。不同目录下的文件可以重名。但不便于实现文件共享。
4）无环图目录结构。可以用不同的文件名指向同一个文件/目录，方便实现多用户间文件共享。
索引结点（FCB的改进）：简化信息，保留文件名，将其他信息都放入索引结点中。存放在外存中的为磁盘索引结点，存放入内存为内存索引结点。
文件的物理结构
1）连续分配：每个文件在磁盘上占有一组连续的块。物理地址 = 逻辑块号 + 起始块号(FCB) + 块内地址。支持顺序访问和随机访问；且顺序访问最快（磁头移动少）；不方便拓展；存储空间利用率低，会产生磁盘碎片。
2）链接分配：隐式链接，在FCB中存储起始/结束块号，每个磁盘块保存了指向下一块的指针；显示连接，将链接物理块的指针显示存放在文件分配表FAT（一个磁盘只有一张），支持顺序访问/随机访问（因为查询的时候不需要访问磁盘）。
3）索引分配：为每个文件建立一张索引表。从目录中找到文件对应索引块，就能找到索引表。支持随机访问，容易进行文件拓展。若文件过大导致一个磁盘块装不下文件整张索引表，可以通过链接/多级索引/混合索引解决。
链接方案：将多个索引块链接起来存放。
多级索引。
混合索引：既包括直接地址索引，又包含一级间接索引、二级简洁索引。
文件存储空间
划分与初始化：将物理磁盘划分为文件卷，，初始化进一步划分为目录区和文件区。
存储空间管理
1）空闲表法：记录空闲盘块号和空闲盘块数。可采用首次适应/最佳适应/最坏适应来为文件分配。
2）空闲链表法：分为空闲盘块链、空闲盘区链
3）位示图法
0代表空闲，1代表已分配。
注意盘块号 = 字长 * i + j
4）成组链接法（UNIX采用）
在文件卷的目录区中专门用一个磁盘块作为“超级块”，系统启动时将超级块读入内存，且保证内存外存中的“超级块”数据一致。
分配空闲块时，检查第一个分组的块数，进行分配。
如果需要的空闲块数较多，要注意一定有一块（图中的300号块）中存放了再下一组的信息，需要将其复制后再分配。
文件共享
1）基于索引结点的共享方式（硬链接），不同用户的目录下文件名可以不一样。
2）基于符号链的共享方式（软链接），用Link型的文件记录共享文件的存放路径，OS根据路径查找。即使所指共享文件已被删除，Link型文件依然存在。
文件保护
口令保护：口令存放如FCB或索引结点中。时间空间开销都小，但存在系统中不够安全。
加密保护：需要密码解密。保密性强，但需要编码/译码。
访问控制：在FCB或索引节点中增加访问控制列表ACL。
文件系统层次结构
磁盘的结构
一个扇区就是一个磁盘块，每个扇区存放的数据量相同。
最内侧磁道上的扇区面积最小，数据密度最大。
每个盘面对应一个磁头，所有磁头连在同一个磁臂上。所有盘面中相对位置相同的磁道组成柱面。因此可以用<柱面号，盘面号，扇区号>定位磁盘块。
一次磁盘读/写操作时间 = 寻道时间（Ts= 启动磁头臂 + 移动磁头） + 延迟时间（即转动磁盘到目标扇区所需时间，平均Tr = 1/2r）+ 传输时间（Tt = b/rN）
r为磁盘转速，b为读写字节数，每个磁道上字节数为N。
减少磁盘延迟时间的方法
由于磁头读入扇区数据后需要处理时间，如果逻辑上相邻的扇区在物理上相邻，会导致需要很多时间才能读入（多转几圈）。
1）交替编号：逻辑上相邻的扇区在物理上有一定间隔。
2）错位命名：相邻盘面之间的错位。
磁盘管理
1）低级格式化。划分扇区，一个扇区分为头、数据、尾三个部分。头尾包括管理扇区的各种数据结构，包括奇偶校验、CRC循环冗余校验码etc
2）磁盘分区，每个分区由若干柱面组成
3）逻辑格式化，创建文件系统（包括根目录、初始化存储空间管理所用数据结构）
引导块：开机时进行一系列初始化工作，通过执行ROM中的初始化程序完成。因为需要更新自举程序，现在ROM中只存放很小的“自举装入程序”，将完整的自举程序放在磁盘的启动块上。
坏块的管理（硬件故障），在逻辑格式化时对整个磁盘进行检查，在FAT表中进行标明（坏块对操作系统不透明）。或者会保留一些“备用扇区”用于替换坏块（坏块对操作系统透明）。
I/O
I/O控制器：接受识别CPU的命令（用控制寄存器存放命令和参数），向CPU报告设备状态（用状态寄存器记录），数据交换（用数据寄存器暂存），地址识别（区分CPU要操作哪个寄存器）
注意：一个I/O控制器可能对应多个设备；数据/控制/状态寄存器可能有多个（内存映像/寄存器独立编址）
I/O控制方式
1）程序直接控制方式（轮询）。CPU频繁干预，每次读/写一个字。
2）中断驱动方式。CPU在每次I/O操作开始、完成之后介入，其他时间切换到别的进程。每次读/写一个字。
3）DMA方式（直接存储器存取）。传送单位是“块”，数据直接在内存和设备间流动，不需要CPU中介。旨在传送一个或多个数据块的开始或结束时，才需要CPU干预。
注意每次读写只能是连续的多个块，读入内存后也必须是连续的。
4）通道控制方式（一种硬件，可以识别并执行一系列通道指令）。通道与CPU共享内存，可执行的指令单一。
I/O软件层次结构
设备独立性软件：提供接口、保护设备（权限）、差错处理、设备的分配回收、数据缓冲区管理、建立逻辑设备名到物理设备名的映射关系，根据设备类型调用相应驱动。
I/O核心子系统
I/O核心子系统（上述设备独立性软件+设备驱动程序+中断处理程序）：
1）SPOOLing技术（假脱机技术） - 用户层软件（408将它归入了I/O核心子系统）
脱机技术：批处理阶段引入，用磁带完成。
假脱机技术：用软件模拟脱机技术。
2）I/O调度，用算法确定一个好的顺序来处理I/O请求
3）设备保护，在UNIX中设备被看作特殊的文件，因此设置FCB
4）设备分配与回收
设备分配时考虑的因素：设备的固有属性（独占/共享/虚拟）、设备分配算法、设备分配中的安全性（安全分配 – 分配设备就阻塞，完成后才唤醒。不会死锁，但一个进程中CPU和I/O只能串行/不安全分配 – 只有I/O得不到满足才阻塞）。
设备控制表DCT，设备类型、设备标识符、设备状态、指向控制器表的指针、重复执行次数或事件、设备队列的队首指针。
控制器控制表COCT，控制器标识符、控制器状态、指向通道表的指针、控制器队列的队首队尾指针
通道控制表CHCT，通道标识符，通道状态，与通道连接的控制器表首址，通道队列的队首对尾指针
系统设备表SDT，记录了全部设备的情况，每个设备对应一个表目。
5）缓冲区管理
使用硬件作为缓冲区，成本较高，容量较小。一般更多用内存作为缓冲区。
a）单缓冲：请求某种块设备读入若干块数据，在主存中分配一个缓存区。注意，当非空时不能冲入只能传出，为空时可以冲入数据，但必须充满后才能把数据传出。
b）双缓冲，分配两个缓冲区。
平均耗时 = max {T, M+C}
c）循环缓冲区
d）缓冲池
写在后面
小累家人们（。）
文案/排版：咸
特别鸣谢：王道考研
