做法：
1破坏互斥条件：只有对必须互斥使用的资源争抢才会导致死锁（操作系统用SPOOLING 技术将改成共享设备）
这种策略的缺点：并不是所有的资源都可以改造成可共享使用的资源，并且为了系统安全🔐，很多地方还必须保护这种互斥性
2破坏不剥夺条件：
方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请，也就是说，即使某些资源尚未用完，也需要主动释放，从而破坏不可剥夺条件
方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺（剥夺调度放式，就是将处理机资源强行剥夺各个，优先级更高的进程使用）
缺点：
1实现起来比较复杂。
2反复的申请释放资源会增加系统开销，降低吞吐量
3一般只适用于易于保存和恢复状态的资源
4放弃已经获得某个资源，以后再重新申请，可能导致后续进程饥饿
破坏请求和保持条件
采用静态分配的方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源为满足前，不让它投入运行，一旦投入运行后，这些资源一直归它所有，该进程就不会再请求别的任何资源
该策略实现起来简单，但也有明显的缺点：造成资源浪费，资源利用率极低，也可能导致某些进程饥饿
破坏循环等待条件
给资源编号，必须按照编号从小到大的顺序申请资源
缺点：不方便增加新设备，会导致资源浪费，用户编程麻烦
Dijkstra
银行家算法
1检查此次申请是否超过了之前声明的最大需求数
2检查此时系统剩余的可用资源是否还能满足这次请求
3试探分配，更改各数据结构
4用安全性算法检查此次分配是否会导致系统进入不安全状态
安全性算法步骤：
检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程拥有的资源全部回收
不断重复上述过程，看最终是否能让所有进程都加入安全序列
系统处于不安全状态未必死锁，但处于死锁状态必定不安全，安全状态一定不会死锁
死锁定理：（查文献？如何证明死锁？）
如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁
解除死锁的方法：
1资源剥夺法。挂起（暂放在外存）某些死锁进程，并抢占资源，将这些资源分配给其他死锁进程，但是应该防止被挂起的进程长时间得不到资源而饥饿
2撤销进程法（终止进程法）强制撤销部分，或者全部的死锁进程，并剥夺这些进程的资源。优点是简单，代价很大，有的进程可能快要结束，最后被终止了，还要再从头再来一次。
3进程回退法。让一个或者多个死锁进程回退到足以避免死锁的地步，这就要求系统记录进程的历史信息，设置还原点
检测死锁
数据结构：资源分配图，
两种结点，进程结点，资源结点
两种边，请求边，分配边
检测算法：依次消除与不同阻塞进程相连的边，直到无边可消
操作系统之考研高频考点（二）
内存
相对地址又称逻辑地址
绝对地址又称物理地址
逻辑地址到物理地址的转化
三种装入方式
绝对装入：只适用于单道批程序
静态重定位：在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业。作业一旦进入内存后，在运行期间就不能再移动，也不能再申请内存空间
动态重定位：并且可以将程序分配到不连续的存储区中，在程序运行前只需装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态分配内存，便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间
内存管理
1操作系统负责内存空间大分配与回收
2操作系统需要提供某种技术从逻辑上对内存空间进行扩充
3操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换
4操作系统需要提供内存保护功能。保证各进程在各自存储空间内运行，互不干扰。
内存保护可采取两种方法：
1在CPU中设置一对上下限寄存器，存放进程的上下限地址。进程的指令要访问某个地址时，CPU检查是否越界。
2采用重定位寄存器和地址寄存器进行越界检查。重定位寄存器中存放的是进程的起始物理地址。界地址寄存器中存放的是进程的最大逻辑地址。
内存空间的扩充
覆盖技术
思想：将程序分为多个段（多个模块）。常用的段常驻内存，不常用的段就在需要时载入内存。
内存中分为一个固定区和若干覆盖区。需要常驻内存的段放在固定区，调入后就不在调出
必须由程序员声明覆盖结构，操作系统完成自动覆盖，
缺点：对用户不透明，增加用户编程负担
交换技术
设计思想：
内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程载入内存
连续分配管理方式
1单一连续分配
在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存低地址部分，用于存放操作系统相关数据，用户区用于存放用户进程相关数据。
内存中只能有一道用户程序，用户程序独占整个用户区空间。
优点：实现简单，无外部碎片，可以采用覆盖技术扩充内存，不一定需要采取内存保护机制
缺点：只能用于单用户，单任务的操作系统，有内部碎片，存储器利用率低
2固定分区分配
3动态分区分配
采用两种常用的数据结构记录内存使用情况
空闲分区表，空闲分区链
动态内存分配没有内部碎片，但是有外部碎片
内部碎片，分配给某个进程的内存区域中，如果有些部分没有用上。
外部碎片，是指内存中的某些空闲分区由于太小而难以利用。
可以通过拼凑（compaction）技术来解决外部碎片
动态分区分配算法
1首次适应算法
思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
实现：空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链，找到大小能满足要求的第一个空闲分区
2最佳适应算法
思想：尽可能多地留下大片空闲分区，优先使用更小的空闲分区
实现：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链，找到大小能满足要求的第一个空闲分区。
缺点：每次都选最小的分区进行分配，会留下越来越多的很小的难以利用的内存块，会产生很多外部碎片
3最坏适应算法
思想：优先使用最大的连续空闲分区，这样分配后的剩余空闲分区就不会太小，更方便使用
实现：空闲分区按照容量递减次序链接。每次分配内存时顺序查找空闲分区链，找到大小能满足要求的第一个空闲分区
缺点：如果有大进程到达，就无法使用
3邻近适应算法
思想：空闲分区以地址递增次序排列
实现：由首次适应算法演变而来，每次从上次查找结束的位置开始查找
不用每次都从低地址的小分区开始检索。算法开销小，
缺点：会使得高地址的大分区也被用完
非连续分配管理方式
1分页存储管理的基本概念
将内存空间分为一个个大小相等的分区，页框号从0开始
将用户进程的地址空间也分为与页框大小相等的一个个区域，称页面，每个页面也有一个编号，即页号，也是从0开始
基本地址变换机构
基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址
具有快表的地址变换机构
快表，又称联想寄存器(TLB)，是一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，内存中的页表常称为慢表
基本分段存储管理方式
分段系统的逻辑地址结构由段号和段内地址组成，段号的位数决定了每个进程最多可分几个段，段内地址位数决定了每个段的最大长度是多少
页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。
段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。
页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。
分页的用户进程地址空间是唯一的，程序员只需要给出一个记忆符即可表示一个地址，g分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址
分段比分页更容易实现信息的共享和保护。
段页式管理
分段+分页
1将地址空间按照程序自身的逻辑关系划分为若干个段，再将各段分为大小相等的页面
2将内存空间分为与页面大小相等的一个个内存块，系统以块为单位为进程分配内存
3逻辑地址结构：段号，页号，页内偏移量
段表+页表
每个段对应一个段表项。各段表项长度相同，由段号，页表长度，页表存放地址组成
每个页对应一个页表项。各页表项长度相同，由页号，页面存放的内存块号组成
地址变换，
1由逻辑地址得到段号，页号，页内偏移量
2段号与段表寄存器中的段长度比较，检查是否越界
3由段表始址，段号找到对应段表项
4根据段表中记录的页表长度，检查页号是否越界
5由段表中的页表地址，页号得到查询页表，找到相应页表项
6由页面存放的内存块号，页内偏移量得到最终的物理地址
7访问目标单元
访存次数
第一次查段表，第二次查页表，第三次访问目标单元
可引入快表机构，以段号和页号为关键字查询快表，即可直接找到最终的目标页面存放位置，引入快表后仅需要一次访存
虚拟内存
定义：
基于局部性原理，在程序载入时，可以将程序中很快会用到的部分载入内存，暂时用不到的部分就在外存
在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的信息从外存调入内存，然后继续执行程序
若内存空间不够，由操作系统将内存中暂时用不到的信息换出外存
在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存
虚拟内存的最大容量是由计算机的地址结构（CPU 寻址范围）确定的
虚拟内存的实际容量=min（内存和外存容量之和，CPU寻址范围）
特征：
多次性：无需在作业运行时一次性全部载入内存，而是允许被分成多次载入内存
对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入，换出。
虚拟性：从逻辑上扩充了内存容量，使用户看到的内存容量远大于实际容量
虚拟内存与传统内存的区别：
在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序，即：操作系统要提供请求调页调段功能
若内存空间不足，由操作系统负责将内存中暂时用不到的信息换出到外存，即：操作系统提供页面置换或段置换的功能
请求分页管理方式
页表机制
1与基本分页管理相比，请求分页管理中，为了实现请求调页，操作系统需要一个，每个页面是否已经调入内存；如果还没调入，那么也需要知道该页面在外存中存放的位置
2当内存空间不够时，要实现页面置换，操作系统要通过某些指标来决定到底换出哪个页面，有的页面没有被修改过，就不用再浪费时间写回外存。有的页面修改过，就需要将外存中的旧数据覆盖，因此操作系统需要记录每个页面是否被修改的信息
请求页表项增加了四个字段
状态位——是否已调入内存
访问字段——可记录最近被访问过几次，或记录上次访问的时间，供置换算法选择换出页面时参考
修改位——页面调入内存后是否被修改过
外存地址——页面在外存中的存放位置
页面置换算法
1最佳置换算法（OPT）
每次选择淘汰的页面将以后永不使用，或者在最长时间内不再被访问的页面，这样就可以保证最低的缺页率。
最佳置换算法可以保证最低的缺页率，但是实际上，只有进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的
2先进先出置换算法（FIFO）
每次选择淘汰的页面是最早进入内存的页面
实现方法：把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块。
Belady异常——当为进程分的物理内存块增大时，缺页次数不减反增的异常现象。
只有FIFO算法会产生Belady异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行的规律不适用，因为先进入的页面也有可能最经常被访问。因此，算法性能差
3最近最久未使用置换算法（LRU，least recently used）
每次淘汰的页面是最近最久未使用的页面
实现方法：赋予每个页面对应的页面项中，用访问字段记录该页面自上次被访问以来所经历的时间t，当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面
该算法的实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大
4时钟⏰置换算法（CLOCK）
又称为最近未用算法（NRU，Not Recently Used ）
这是一种性能和开销都比较均衡的算法
实现方法：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需要检查页的访问位。如果是0，就选择该页换出，如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置位0，再进行第二轮扫描（在第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK 算法选择一个淘汰页面最多会经过两轮扫描）
改进型的时钟置换算法
简单时钟置换算法仅仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行IO操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。
因此，除了考虑一个页面最近有没有被访问过，操作系统还应该考虑页面有没有被修改过。在其他条件都相同的时候，应优先淘汰没有修改过的页面，避免IO操作。这就是改进型的时钟置换算法思想。
修改位=0，表示页面没有被修改过，修改位=1，表示页面被修改过。
用（访问位，修改位）表示各页面状态
算法规则：
将所有可能被置换的页面排成一个循环队列
第一轮：从当前位置开始扫描到第一个（0，0）的帧用于替换。本轮扫描不修改任何标识位
第二轮：若第一轮扫描失败，则重新扫描，查找第一个（0，1）的帧用于替换。本轮将所有扫描过的帧访问位设为0
第三轮：若第二轮扫描失败，则重新扫描，查找第一个（0，0）的帧用于替换。本轮扫描不会修改任何标志位
第四轮：若第三轮扫描失败，则重新扫描，查找第一个（0，1）的帧用于替换。
由于第二轮已将所有帧的访问位设为0，因此经过第三轮，第四轮扫描一定会有一个帧被选中，因此改进型CLOCK 置换算法选择一个淘汰页面最多进行四轮扫描
第一轮：最近没访问，且没修改的页面
第二轮：最近没访问，但修改过的页面
第三轮：最近访问过，但没修改的页面
第四轮：最近访问过，且修改过的页面
页面分配策略
驻留集：指请求分页存储管理中给进程分配的物理内存块的集合。
在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。
若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少，驻留集太大，又会导致多道程序并发度下降，资源利用率降低，所以应该选择一个合适的驻留集大小
固定分配：操作系统为每个进程分配一组固定数目的物理内存块，在进程运行期间不再改变。即，驻留集大小不变
可变分配：先为每个进程分配一定数目的物理内存块，在进程运行期间，可根据情况适当的增加或减少。即，驻留集大小可变
局部置换：发生缺页时只能选进程自己的物理块进行置换
全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理内存块置换到外存，再分配给缺页进程
局部置换 全局置换
固定分配 ✅ ❌
可变分配 ✅ ✅
可变分配全局置换：只要缺页就给分配新的物理块
可变分配局部置换：要根据发生缺页的频率来动态地增加或减少减少进程的物理块
何时调入页面
1预调页策略：根据局部性原理，一次调入若干个相邻的页面可能比一次调入一个页面更高效。主要用于进程的首次调入，进程运行前调入
2请求调页策略：进程在运行期间发现缺页时才将缺页的页面调入内存。IO操作开销大
，进程运行时调入
从何处调入页面
抖动（颠簸）现象
刚换出的页面马上又换入内存，刚换入的页面马上又换出外存，这种频繁的页面调度行为被称为抖动，原因是分配给进程的物理块不够
工作集：指某段时间间隔里，进程实际访问页面的集合
操作系统之考研高频考点（三）
文件管理
属性：
文件名
标识符
类型
位置
大小
创建时间，上次修改时间
文件所有者信息
保护信息
文件的逻辑结构
按照文件是否有结构分类，可以分为无结构文件，有结构文件。
无结构文件：文件内部的数据就是一系列二进制流或字符流组成。又称流式文件，如. txt文件
有结构文件：由一组相似的记录组成，又称记录式文件。每条记录由若干个数据项组成。如：数据库表文件。一般来说，每条记录有一个数据项可作为关键字。根据各条记录的长度是否相等，又可分为定长记录和可变长记录两种
顺序文件：文件中的记录一个接一个地顺序排列，记录可以是定长的或可变长的。各个记录在物理上可以顺序存储或链式存储
1链式存储——无论是定长/可变长记录，都无法实现随机存取，每次只能从第一个记录开始依次往后查找
2顺序存储——可变长记录，无法实现随机存储
——定长记录，可实现随机存取。
若采用串结构，无法快速找到某关键字对应的记录
若采用顺序结构，可以快速找到某关键字对应的记录（如折半查找）
索引文件
建立一张索引表，每个记录对应一个表项。各记录不用保持顺序，方便增删改查
索引表本身就是定长记录的顺序文件，一个索引表项就是一条定长记录，因此索引文件可支持随机存取
若索引表按关键字顺序排列，则可支持快速检索
解决了顺序文件不方便增删改查的问题，同时让不定长记录的文件实现了随机存取。但索引表可能占用很多空间
索引顺序文件
建立多级索引表
文件目录
目录本身就是一种有结构文件，由一条条记录组成。每条记录对应一个在该放在该目录下的文件
目录结构：
单级目录结构
两级目录结构——主文件目录（MFD Master File Directory ）和用户文件目录（UFD User File Directory ）
多级目录结构（树形目录结构）——不便于实现文件共享
相对路径的检索会减少磁盘IO启动的次数
绝对路
无环图目录结构
文件的物理结构（文件分配方式）
对磁盘管理：
对非空闲磁盘块的管理（存放了文件数据的磁盘块）
对空闲磁盘块的管理
磁盘块的大小与内存块，页面大小相等
在内存管理中，进程的逻辑地址空间被分为一个一个页面
同样，在外存管理中，文件的逻辑地址空间也被分为了一个一个的文件块
可表示为（逻辑块号，块内地址）
操作系统为文件分配存储空间都是以块为单位的
用户通过逻辑地址来操作自己的文件，操作系统要负责实现从逻辑地址到物理地址的映射
文件分配
连续分配方式
要求每个文件在磁盘上占有一组连续的块。因此物理上采用连续分配的文件不方便扩展，存储空间利用率低，会产生难以利用的磁盘碎片，可以用紧凑来处理碎片，但需要耗费很大的时间代价
支持顺序访问和随机访问
链接分配
采用离散分配方式，可以为文件分配离散的磁盘块。分为隐式链接和显式链接
采用链式分配的方式只支持顺序访问，不支持随机访问，查找效率低。另外，指向下一个盘块的指针也需要耗费少量的存储空间。
文件扩展很方便，所有的空闲磁盘块都可以被利用，不会有碎片问题，外存利用率高
显示分配
把用于链接文件各物理块的指针显式地存放在一张表中。即文件分配表（FAT，File Allocation Table）
优点：很方便文件扩展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接，地址变换时不需要访问磁盘，因此文件的访问效率高
缺点：文件分配表的需要占用一定的存储空间。
索引分配
允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块
支持随机访问和文件扩展
索引表需要占用一定的空间
1链接方案：如果索引表太大，一个索引表装不下，那么可以将多个索引块链接起来存放
2多层索引：建立多层索引（类似多级页表）
3混合索引
文件存储空间管理
磁盘分区：将物理磁盘划分为一个个文件卷（逻辑卷，逻辑盘，如C盘D盘E盘）
盘又分为目录区，文件区
目录区主要存放文件目录信息（FCB），用于磁盘存储空间管理的信息
文件区用于存放文件数据
存储空间管理——空闲表法
如何分配磁盘块：与内存管理中的动态分区分配类似，为一个文件分配连续的存储空间。同样可采用首次适应，最佳适应，最坏适应算法来决定为文件分配哪个区间。
如何回收：与内存管理中的动态分区分配类似，当回收某个存储区时需要有四种情况
1回收区前后都没有相邻空闲分区
2回收区前后都是空闲分区
3回收区前是空闲分区
4回收区后是空闲分区
空闲链表法
空闲盘块链——以盘块为单位组成一条空闲链
空闲盘区链——以盘区为单位组成一条空闲链
回收：修改链头，链尾指针
位示图法（考点）
成组链接法：unix 采用的策略，适合大型文件系统。（不作为考点）
文件的基本操作
创建文件（create ）
1在外存中找到文件所需的空间
2根据文件存放的路径的信息找到该目录对应的目录文件，在目录中创建该文件对应的目录项
删除文件（delete ）
1 根据文件存放的路径的信息找到该目录对应的目录文件
2回收文件占用的磁盘块
3从目录表中删除目录项
打开文件（open ）
1操作系统存放路径找到对应的目录文件，从目录中找到文件名对应的目录项，并检查用户是否有指定的操作权限
2将目录项复制到内存的打开文件表中。并将对应表目的编号返回给用户。之后用户使用打开文件表的编号来指明要操作的文件
关闭文件（close ）
读文件（read ）
写文件（write ）
点击保存后，调用了操作系统的写文件，将文件数据从内存写到外存
文件共享
基于索引结点的共享方式（硬链接）
1各个用户的目录项指向同一个索引结点
2索引结点中需要有链接计数器count
3某用户想删除文件时，只是删除用户的目录项，且count–
4只有count=0才能删除文件数据和索引结点，否则会导致指针悬空
基于符号链的共享方式（软链接）
1在一个Link 型的文件中记录共享文件的存放路径
2操作系统根据路径一层层查找目录，最终找到共享文件
3即使软链接指向的共享文件已被删除，Link型文件依然存在，只是通过Link型文件中的路径去查找共享文件会失败
4用软链接的方式访问共享文件时要查询多级目录，会有多次磁盘IO，
注意⚠️：多个用户共享同一份文件，意味着操作系统中只有一份文件数据。并且只要某个用户修改了该文件的数据，其他用户也可以看到文件数据的变化。
如果是多个用户都复制了同一个文件，那么系统中会有好几份文件数据。其中一个用户修改了自己的那份数据，其他用户的文件数据没有影响。
文件保护
口径保护
口径一般存放在文件对应的FCB或索引结点中。用户访问文件前需要先输入口令，操作系统会将用户提供的口令与FCB中存储的口令进行对比，如果正确，则允许访问
优点：保存口令的空间开销不多，验证口令的时间开销小
缺点：口令放在操作系统内部，不安全
加密保护
优点：保密性强，不需要在系统中存储密码
缺点：加密/解密需要花费一定时间
访问控制
在每个文件的FCB（或索引结点）中增加一个访问控制列表（Access Control List ）该表中记录了各个用户可以对该文件执行哪些操作
文件系统的层次结构
1用户接口
文件系统需要向上层的用户提供一些简单易用的功能接口。这层就是用于处理用户发出的系统调用请求（read write open close ）
2文件目录系统
用户通过文件路径来访问文件的，因此这一层需要根据用户给出的文件路径找到相对应的FCB或索引结点。所有的目录和目录项相关的管理工作都在本层完成
3存取控制模块
为了操作，文件数据的安全，还需要验证用户是否有访问权限，这一层主要完成了文件保护相关功能。
4逻辑文件系统与文件信息缓冲区
用户指明想要访问文件记录号，这一层需要将记录号转换为对应的逻辑地址
5物理文件系统
把逻辑地址转换成物理地址
6辅助分配模块
负责文件存储空间的管理，即负责分配和回收存储空间
6设备管理模块
直接与硬件交互，如：分配设备，分配设备缓冲区，磁盘调度，启动设备，释放设备
磁盘的结构
磁盘
磁道
扇区
一个磁道又被划分为一个个扇区，每个扇区就是一个磁盘块。各扇区存放的数据量相同，最内侧磁道上的扇区面积最小，因此数据密度最大
磁盘的物理地址
一个盘片可能会有两个盘面
每个盘面对应一个磁头
所有磁头都连在同一个磁臂上的
所有盘面中相对位置相同的磁道组成柱面
可用（柱面号，盘面号，扇区号）来定位任意一个磁盘块。
读取地址连续的磁盘块时，采用（柱面号，盘面号，扇区号）的地址结构可以减少磁头移动消耗的时间
磁盘分类
活动头磁盘：磁臂可以来回伸缩来带动磁头定位磁道
固定头磁盘：磁盘中每个磁道有一个磁头
可换盘磁盘：
固定盘磁盘：
磁盘调度算法
一次磁盘读写操作需要的时间
寻找时间（寻道时间）：
启动磁头臂耗时s ，移动磁头，每跨越一个磁道耗时m，共需要跨越n个磁道，则寻道时间为s+mn
延迟时间：
通过旋转磁盘，使磁头定位到目标扇区所需时间。设磁盘转速为r，则T=1/（2r）
传输时间：
从磁道读出或写入数据经历的时间，设磁盘转速r，此次读写的字节数为b，每个磁道上的字节数N，则T=b/（rN）
延迟时间和传输时间都与磁盘转速线性有关，因此无法优化。
用调度算法来优化寻到时间
1先来先服务算法（FCFS）
2最短寻找时间优先（SSTF）：
优先处理与当前磁头最近的磁道，可能产生饥饿
3扫描算法：只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动
优点：不会产生饥饿
缺点：
1只有到达最边上的磁道时才能改变磁头移动方向
2对于各个位置的磁道响应频率不平均
4LOOK调度算法：边移动边观察
5循环扫描算法（C-SCAN）
6C-LOOK算法
减少磁盘延迟时间的算法
磁头读取一个扇区数据后需要一小段时间处理，如果逻辑上相邻的扇区在物理上也相邻，则读入几个连续的逻辑扇区，可能需要很长的延迟时间
交替编号：让逻辑上相邻的扇区在物理上有一定间隔，
错位命名：
磁盘管理
初始化
设备管理
IO控制器
功能：
1接受和识别CPU发出的命令
2向CPU报告设备的状态
3数据交换
4地址识别
组成：
1CPU与控制器之间的接口（实现控制器与CPU之间的通信）
2IO逻辑（负责识别CPU发出的命令，并向设备发出命令）
3控制器与设备之间的接口（实现控制器与设备之间的通信）
两种寄存器编址方式
内存映射IO
寄存器独立编址
IO控制方式
程序直接控制方式
1完成一次读写操作（轮询）
2CPU干预频率，很频繁，在IO操作开始之前，完成之后需要CPU介入，并且在等待IO完成的过程中CPU需要不断地轮询检查
3数据传送的单位每次读写一个字
4数据流向
读操作（数据输入）：IO设备→CPU→内存
写操作（数据输出）：内存→CPU→IO设备
5优缺点
优点：实现简单。在读写指令之后加上实现循环检查的一系列指令即可
缺点：CPU和IO设备只能串行工作，CPU需要一直轮询检查，长期处于忙等状态，CPU利用率低
中断驱动方式
DMA方式（Direct Memory Access）
直接存储器存取
1数据的传送单位是块，不再是一个字一个字的传送（注意，每次读写的只能是连续的块，且这些块读入内存后在内存中也必须是连续的）
2数据的流向是从设备直接放入内存，或者从内存直接到设备（不需要经过CPU）
3仅在传送一个或多个数据块的开始和结束时才需要CPU干预。
4优点：数据传输以块为单位，CPU介入频率进一步降低。CPU和IO设备的并行性得到提升
缺点：CPU每发出一条IO指令，只能读写一个或者多个连续的数据块
通道控制方式
1CPU干预的频率极低，通道会根据CPU的指示执行相应的通道程序，只有完成一组数据块的读写后才需要发出中断信号，请求CPU干预
2数据传送单位：每次读写一组数据块
3数据流向：
读操作（数据输入）：IO设备→内存
写操作（数据输出）：内存→IO设备
4缺点：实现复杂，需要专门的通道硬件支持
优点：CPU 通道IO设备可并行工作，资源利用率极高
IO软件的层次
用户层软件：实现与用户交互的接口，向上提供方便易用的库函数
假脱机技术（SPOOLING 技术）
设备独立性软件：
1向上层提供统一的调用（如read write 系统调用）
2设备的保护
3差错处理
4设备的分配与回收
5数据缓冲区管理
6建立逻辑设备名到物理设备名的映射关系
IO调度，设备保护，设备分配与回收，缓冲区管理
设备驱动程序：设备设备寄存器，检查设备状态
中断处理程序：进行中断处理
假脱机技术SPOOLING
作用：缓解设备与CPU的速度矛盾，实现预输入，输出
用软件的方式模拟脱机技术
输入井和输出井——模拟脱机输入输出时的磁带
输入进程和输出进程——模拟脱机输入输出时的外围控制机
输入缓冲区和输出缓冲区——内存中的缓冲区，输入，输出时的中转站
设备的分配与回收
设备的固有属性：独占设备，共享设备，虚拟设备
设备的分配算法：
先来先服务
优先级高的优先
段任务优先
设备分配的安全性：
安全分配方式和不安全分配方式
为进程分配一个设备后就将进程阻塞，
静态分配与动态分配
静态分配：进程运行前为其分配全部所需资源，运行结束后归还资源
动态分配：进程运行过程中动态申请设备资源
设备分配管理中的数据结构：
设备控制表（DCT）每个设备对应一张DCT，关键字段：类型/标识符/状态/指向COCT的指针/等待队列指针
控制器控制表（COCT）每个控制器对应一张COCT，关键字段：状态/指向CHCT的指针/等待队列指针
通道控制表（CHCT）每个控制器对应一张CHCT，关键字段：状态/等待队列指针
系统设备表（SDT）记录整个系统中所有设备的情况，每个设备对应一个表目，关键字段：设备类型/标识符/DCT/驱动程序入口
一个通道控制多个控制器，一个控制器控制多个设备
设备分配的步骤：
1根据进程请求的物理设备名查找SDT，
2根据SDT找到DCT并分配设备，
3根据DCT找到COCT并分配控制器
4根据COCT找到CHCT并分配通道
只有设备，控制器，通道三者都分配成功时，这次设备分配才算成功，之后便可以启动IO设备进行数据传送
缺点：用户编程时必须使用物理设备名，若换了一个物理设备，则程序无法运行，若进程请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻塞等待
设备分配步骤的改进
用户编程时使用逻辑设备名申请设备，操作系统负责实现从逻辑设备名到物理设备名的映射（通过LUT）
逻辑设备表的设置问题
整个系统只有一张LUT：各用户所用的逻辑设备名不允许重复
每个用户一张LUT：各个用户的逻辑设备名可重复
缓冲区管理
一般利用内存作为缓冲区
作用：
1缓和CPU与IO设备之间速度不匹配的矛盾
2减少对CPU的中断频率，放宽对CPU中断响应时间的限制
3解决数据粒度不匹配的问题
4提高CPU与IO设备之间的并行性
单缓冲
双缓冲
循环缓冲：多个缓冲区链接成循环队列，in指针指向第一个空缓冲区，out指针指向第一个满缓冲区
缓冲池：三个队列：空缓冲队列，输入队列，输出队列
四种工作缓冲区：用于收容输入数据的工作缓冲区，用于提取输入数据的工作缓冲区，用于收容输出数据的工作缓冲区，用于提取输出数据的工作缓冲区
