操作系统

• 1. 操作系统的概念和作用
• 2. 操作系统的发展过程
• 3. 操作系统的基本特性
• 4. 操作系统主要功能
• 5. 操作系统的运行环境
• 6. 进程描述与控制
  • 6.1. 前趋图(DAG Directed Acyclic Graph):
  • 6.2. 程序执行方式
  • 6.3. 进程
  • 6.4. 线程
  • 6.5. 进程控制
  • 6.6. 进程同步
  • 6.7. 进程通信
  • 6.8. 处理器调度
  • 6.9. 死锁
• 7. linux进程管理
  • 7.1. 进程的类型
  • 7.2. 进程的标记
  • 7.3. 操作linux进程的相关命令
• 8. 内存管理概述
• 9. 存储管理方式
  • 9.1. 多道程序环境下的对换技术(Swapping)
• 10. linux的存储管理
• 11. 虚拟存储器
  • 11.1. 虚拟存储器概述
  • 11.2. 虚拟存储管理方式
  • 11.3. 页面调入策略
  • 物理块分配策略
  • 11.4. 内存分配策略
  • 11.5. 页面置换算法(Page-Replacement Algorithms)
  • 11.6. 抖动与工作集
  • 11.7. 请求分段存储管理方式
• 12. 输入输出系统
  • 12.1. I/O设备分类
  • 12.2. I/O系统的基本功能
  • 12.3. I/O系统的层次结构和模型
• 13. I/O设备和设备控制器概述
  • 13.1. 设备寻址方式
  • 13.2. 设备控制器（分成控制字符设备的控制器和控制块设备的控制器）
  • 13.3. I/O通道
• 14. 中断机构和设备驱动程序
  • 14.1. 中断机构
  • 14.2. 设备驱动程序
  • 14.3. 与设备无关的I/O软件
  • 14.4. 用户层的I/O软件
  • 14.5. 假脱机（Spooling）系统（虚拟设备技术）：将独占设备改成共享设备的技术
  • 14.6. 缓冲区管理
• 15. 文件和文件系统
  • 15.1. linux文件系统
• 16. 文件的逻辑结构
• 17. 文件目录
• 18. 文件共享
• 19. 文件保护
• 20. 外存的组织方式(辅存的存储空间分配)
• 21. 文件存储空间的管理
• 22. 提高磁盘I/O速度的途径
• 23. 提高磁盘可靠性的技术
• 24. 数据一致性控制

1. 操作系统的概念和作用

• 操作系统概念：一组能有效组织和管理计算机硬件和软件资源并对各类作业进行调度的程序的集合/操作系统是指管理计算机硬件和软件资源的计算机程序（是软件）
• 原子操作:一个不可分割的基本单位，在执行过程中不允许被中断。在系统态下执行，常驻内存
• 原语操作:由若干条指令组成的，用于完成一定功能的过程，是一个原子操作
• 操作系统作用
  • 提供用户与计算机硬件之间的接口（用户通过命令、系统调用、和图标一窗口方式与系统通信并取得它的服务）
  • 管理系统资源（管理处理机、存储器、I/O设备和文件(数据和程序)等资源、协调用户对共享资源的使用）
  • 计算机资源的抽象（隐藏对硬件操作的具体细节，增强系统功能）
• 操作系统内核
  • 支撑功能：中断处理、时钟管理、原语操作
  • 资源管理功能：进程管理、存储器管理、设备管理

2. 操作系统的发展过程

• 操作系统发展历程
  • 人工操作方式
  • 脱机输入/输出(Off-Line I/O)方式
  • 单道批处理系统(Simple Batch Processing System)
  • 多道批处理系统(Multiprogrammed Batch Processing System)
  • 分时系统（人机交互）(Time Sharing System)
  • 实时系统(工业控制系统等)(Real Time System)
  • 微机操作系统
    • 单用户单任务操作系统(CP/M、MS-DOS)
    • 单用户多任务操作系统windows
    • 多用户多任务操作系统Linux

3. 操作系统的基本特性

• 并发(Concurrence)
  • 并行:多个事件在同一时刻发生、并发:多个事件在同一个时间发生、串行:多个事件按顺序执行
  • 并发性：一段时间内宏观上有多个程序同时运行，微观上多个程序分时运行
• 共享(Sharing)
  • 资源共享/复用:系统中的资源可供内存中多个并发进程共同使用
  • 互斥共享方式：一定时间内，只允许一个进程访问临界资源---物理设备、栈、变量和表格
  • 同时访问方式：多个进程同时访问资源---磁盘设备，文件
• 虚拟(Virtual)
  • 虚拟：将一个物理实体变为若干个逻辑上的对应物的功能
  • 时分复用技术：虚拟处理机技术、虚拟设备技术；
  • 空分复用技术：虚拟存储技术
• 异步(Asynchronism)
  • 异步性：进程以不可预知的速度向前推进
  • 同步机制：运行环境相同的情况下，作业多次运行得到相同的结果

4. 操作系统主要功能

• 处理机(进程)管理
  • 进程控制(进程创建、撤销及状态转换)
  • 进程同步(并发进程协调方式:进程互斥、进程同步)
  • 进程通信(进程间信息交换)
  • 进程调度(按算法进行处理器分配:作业调度、进程调度)
• 存储器管理
  • 内存分配和回收(按一定策略为每道程序分配内存:动态/静态分配内存)
  • 内存保护(保证各程序在自己的内存区域内运行而不相互干扰)
  • 地址映射(将地址空间中的逻辑地址转换为内存空间中与之对应的物理地址)
  • 内存扩充(借助虚拟存储技术增加内存达到运行大型作业的目的)
• 设备管理
  • 缓冲管理(解决CPU与IO设备速度不匹配问题)
  • 设备分配(按照一定的分配策略分配设备并回收)
  • 设备处理(CPU与设备控制器之间的通信)
• 文件管理
  • 文件存储空间管理(存储空间分配和回收)
  • 目录管理(文件检索、共享、存取)
  • 文件读/写管理和保护(存取控制)
• 操作系统与用户之间的接口
  • 用户接口(向作业发出命令以控制作业的运行)
  • 程序接口(取得操作系统服务的唯一条件)

5. 操作系统的运行环境

• 系统态(内核态/管态)：具有较高特权，执行一切特权指令，访问所有寄存器和存储区
• 用户态(目态)：较低特权的执行状态，仅能执行规定的指令，访问指定的寄存器和存储区
• 特权指令：包括时钟管理、中断机制、原语、系统控制的数据结构及处理
• (外)中断：CPU对I/O设备发来的中断信号的一种响应
• (内中断)陷入/异常：由CPU内部事件引起的中断
• 系统调用：操作系统提供的用户接口之一，为使诸进程能条不紊地使用I/O设备且保护设备的安全性，不允许运行的用户态的应用进程去直接调用运行在核心态的os过程，同时取得os所提供的服务。内核提供了一系列具备预定功能的内核函数，通过系统调用的接口呈现给用户
• 系统调用执行过程：当os捕获应用程序中的该系统调用后，便将CPU的状态从用户态转换到核心态，然后转向操作系统中相应过程，由该过程完成所需的I/O操作，执行完成后，系统又将CPU状态从核心态转换到用户态，返回到应用程序继续执行
• 操作系统的体系结构
  • 模块组合结构：将操作系统按功能划分为若干个具有一定独立性和大小的模块
  • 层次结构：将操作系统分成若干个层次，每层有若干个模块组成，各层之间值存在着单向的依赖关系
  • 微内核结构：将操作系统分成微内核和多个服务器

6. 进程描述与控制

6.1. 前趋图(DAG Directed Acyclic Graph):

• 描述程序执行先后顺序的有向无循环图(前趋图不允许有循环)
• 前趋:P1->P2,说明p1,p2存在前趋关系
• 直接前趋:P1是P2的直接前趋、直接后继:P2是P1的直接后继
• 初始节点:没有前趋的节点、终止节点:没有后继的节点
• 重量(weight):表示该节点所含有的程序量或程序执行时间

6.2. 程序执行方式

• 程序顺序执行: 顺序性、封闭性（独占资源，结果不受外界因素影响）、可再现性(环境和初始条件一样则运行结果一样)
• 程序并发执行：间断性(竞争系统资源造成的)、失去封闭性、不可再现性。只有不存在前趋关系的程序之间才有可能并发执行
• 程序:有序指令的集合

6.3. 进程

• 为什么需要进程?合理的隔离资源、运行环境、提升资源利用率
• 概念:由程序段、相关的数据段和PCB组成的进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
• 特征(了解)
  • 动态性:具有生命周期
  • 并发性:具有PCB才能在OS中并发执行
  • 独立性:获得资源的基本单位、(无线程情况下)独立运行和接收调度的基本单位
  • 异步性:进程按各自独立的、不可预知的速度以异步的方式运行，会产生结果的不可再现性
• 进程的层次结构(了解)
  • 进程关系:进程A创建了进程B，则A为父进程(Parent Process)，B为子进程(Progeny Process)
  • 子进程可以继承父进程所拥有的资源；子进程撤销时，应将资源归还给父进程；父进程撤销时，应撤销所有子进程
  • 在unix中，进程与其子孙进程组成进程家族；在windows中，进程间关系是获得句柄与否，控制与被控制的关系
  • 进程图(Process Graph):描述进程间关系的一颗有向树，创建父进程的进程称为祖先进程，树的根节点作为进程家族的祖先
• 基本状态
  • 创建状态:PCB初始化,申请除CPU以外的所有必要资源，进程不能被调度运行.操作系统提供fork函数接口创建进程.fork创建的进程初始化状态和父进程一样.系统会为fork的进程分配新的资源.fork系统调用无参数.返回两次，分别返回子进程id和0.返回子进程id的是父进程、返回0的是子进程
  • 就绪(Ready)状态:进程已分配除CPU以外的所有必要资源，只要获得CPU，便可立即执行.在一个系统中多个处于就绪状态的进程通常排成一个队列（就绪队列）
  • 执行(Running)状态:进程已获得CPU,其程序正在执行的状态
  • 阻塞(Block)状态:正在执行的进程发生某事件(I/O请求,申请缓冲区失败)暂时无法继续执行的状态，放弃CPU，不同阻塞原因的进程进入不同的阻塞队列
  • 终止状态:进程到达自然结束点、出现无法克服的错误、被操作系统终结、或者被其他由终止权的进程所终结的状态。此时系统清理或者归还PCB

• 进程控制块PCB(Process Control Block)----进程管理中的数据结构，进程的实体表现为一片存储空间
  • 概念:为进程定义的记录型数据结构，记录了操作系统用于描述进程的当前情况以及管理进程运行的全部信息
  • 作用:使程序成为在多道程序环境下独立运行的基本单位
  • 包含数据信息
    • 进程标识符：外部标识符(方便用户(进程)对进程的访问)、内部标识符(方便系统对进程的访问)
    • 处理机状态：通用寄存器、指令计数器(下一条指令地址)、程序状态字PSW、用户栈指针
    • 进程调度信息：进程状态、进程优先级、其他信息(如进程调度算法)、事件(阻塞原因)
    • 进程控制信息：程序和数据的地址、进程同步和通信机制、资源清单、链接指针(PCB队列中下一个进程的PCB首地址)
  • 多个PCB的组织方式
    • 线性方式：所有PCB放在线性表中，将该表的首地址放在内存的一个专用区域中
    • 链接方式：将具有相同状态进程的PCB分别通过PCB中的链接字链接成一个队列（就绪队列、阻塞队列、空白队列等）
    • 索引方式：按进程状态不同建立多张索引表，表目中记录PCB在PCB表中的地址，各索引表在内存的首地址记录在内存的一些专用单元中(就绪索引表、阻塞索引表等)

6.4. 线程

• 引入线程原因:减少程序在并发执行时所付出的时空开销
• 特点
  • 调度的基本单位：在引入线程的操作系统中作为调度和分派的基本单位
  • 并发性
  • 拥有资源：只拥有进程中一点必不可少的、能保证独立运行的资源，多个线程共享该进程拥有的资源
  • 独立性：独立性比进程低、多个线程共享了进程的内存地址空间和资源
  • 系统开销：系统开销比进程小
  • 支持多处理机系统:同一个进程的多个线程可以分配到多个处理机上运行
• 状态及其状态切换与进程一样
• 线程控制块TCB(了解)
  • 线程标识符
  • 一组寄存器(程序计数器PC、通用寄存器、状态寄存器的内容)
  • 线程运行状态
  • 优先级
  • 线程专有存储区(用于线程切换时存放线程保护信息和与该线程相关的统计信息等)
  • 信号屏蔽
  • 堆栈指针(将每次过程调用中使用的局部变量以及返回地址保存起来)
• 线程的实现
  • 内核级线程KTS(Kernel Supported Threads)：依赖内核完成创建和撤销工作的线程，线程阻塞时不影响其他线程运行
  • 用户级线程ULT(User Level Threads)：应用程序利用线程库的函数来控制的线程，当线程阻塞时，整个进程必须等待

	进程	线程
资源	资源分配基本单位	不拥有资源
调度	独立调度基本单位	独立调度的最小单位
系统开销	进程系统开销大	线程系统开销小
通信	进程IPC	读写同一进程数据通信

6.5. 进程控制

• 进程的创建(Creation of Process)
  • 引起创建进程的事件
    • 用户登录:用户登录成功后，系统将为该用户建立一个进程并将它插入到就系队列中
    • 作业调度:调度作业进入内存，然后创建进程，并插入到就绪队列中
    • 提供服务:用户程序提出请求后，系统专门创建一个进程供用户所需要的服务
    • 应用请求:用户进程自己创建新进程，以便使新进程以同创建者进程并发运行的方式完成特定任务
  • 进程的创建过程
    • 申请空白PCB:为新进程申请获得唯一的数字标识符，并从PCB集合中索取一个空白PCB
    • 为新进程分配其运行所需的资源:包括各种物理和逻辑资源(所需内存、文件、I/O设备和CPU时间等)
    • 初始化进程控制块PCB
      • 初始化标识信息:将系统分配的标识符和父进程标识符填入新的PCB中
      • 初始化处理机状态信息:使程序计数器指向程序的入口地址,使栈指针指向栈顶
      • 初始化处理机控制信息:使进程的状态设置为就绪状态或静止状态
      • 初始化进程控制信息:对于优先级，通常是将它设置为最低优先级
    • 如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列
• 进程的终止(Termination of Process)
  • 引起进程终止的事件
    • 正常结束：进程的任务完成，准备退出运行
    • 异常结束：越界错、保护错、非法指令错、特权指令错、算术运算错、运行超时、等待超时、I/O故障
    • 外界干预：操作员或者操作系统干预、父进程请求、因父进程终止
  • 进程的终止过程
    • 根据终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态
    • 若被终止进程正处于执行状态，立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新调度
    • 若该进程还有子孙进程，还应将其所有子孙进程也都予以终止，防止它们成为不可控的进程
    • 将被终止进程所拥有的全部资源或者归还给父进程，或者归还给系统
    • 将被终止进程PCB从所在队列或链表中移出，等待其它程序来搜集信息
• 进程的阻塞与唤醒
  • 引起进程阻塞和唤醒的事件
    • 向系统请求共享资源失败
    • 等待某种操作的完成
    • 新数据尚未到达
    • 等待新任务的到达:网络发送数据包
  • 进程阻塞过程
    • 进程通过主动调用阻塞原语block将自己阻塞
    • 先立即停止执行。把进程控制块中的现行状态由"执行"改为阻塞，将PCB插入具有相同事件的阻塞队列
    • 转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换
  • 进程唤醒过程
    • 与阻塞进程相关的进程通过调用唤醒原语wakeup，将阻塞进程唤醒
    • 把被阻塞的进程从等待该事件的阻塞队列中移出
    • 将其PCB中的现行状态由阻塞改为就绪
    • 将其PCB插入到就绪队列中
• 进程的挂起和激活
  • 挂起过程:操作系统使用挂起原语suspend将进程或处于阻塞状态的进程挂起
    • 检查被挂起进程的状态，活动就绪则改为静止就绪;活动阻塞则改为静止阻塞;正在执行则转向调度程序重新调度
    • 把进程的PCB复制到指定的内存区域，方便用户或父进程考查该进程的运行情况
  • 激活过程:操作系统使用激活原语active将进程激活
    • 将进程从外存调入内存，检查该进程的现行状态。静止就绪改为活动就绪;静止阻塞改为活动阻塞
• 进程切换
  • 进程切换：CPU从一个进程的运行转到另一个进程的执行，进程的运行环境发生实质性变化
  • 进程切换的过程
    • 保存处理及上下文（程序计数器和其他寄存器）并更新PCB信息
    • 把进程的PCB移入相应队列（如就绪、某事件的阻塞队列等）并选择另一个进程执行，更新PCB。
    • 更新内存管理的数据结构并恢复处理器上下文

6.6. 进程同步

• 进程同步基本概念
  • 根源问题是：彼此相互之间没有通信
  • 主要任务:对多个程序的执行顺序、共享系统资源进行协调，使程序的执行具有可再现性
  • 多个进程制约关系
    • 间接相互制约关系(互斥):竞争临界资源(打印机、磁带机)
    • 直接相互制约关系(同步):相互合作的进程，例如：进程B的执行需要等待进程A的结果
  • 临界资源:进程必须互斥访问的资源(如打印机、磁带机等硬件资源或者程序中的变量)当有进程在使用临界资源时，其他进程必须依据操作系统的同步机制等待占用进程释放该资源才可重新竞争使用共享资源
  • 临界区(critical section):每个进程中访问临界资源的代码
  • 进入区(entry section):检查临界资源是否正被访问的代码
  • 退出区(exit section):临界区后面的代码，将临界区正被访问的标志恢复为未被访问的标志
  • 剩余区:上面三个区以外的代码
• 同步机制
  • 同步机制遵循的规则: 空闲让进、忙则等待、有限等待、让权等待(当进程不能进入临界区，则释放CPU,运行状态->阻塞状态)
  • 原子性是指一系列操作不可被中断的特性,要么全部执行完成，要么全部没有执行,不存在部分执行部分未执行的情况
  • 同步机制
    • 关中断:进程在临界区执行期间关闭中断
    • Test-and-Set指令(原语)
    • Swap(对换)/xchg指令:当临界资源忙碌时，其他访问进程必须不断进行测试，处于忙等状态(不符合让权等待原则)
    • 信号量机制
      • 整型信号量：定义一个用于表示资源数目的整型量S，只能通过wait(S)/P和signal(S)/V两个原子操作访问，当信号量S<=0时不断测试(不符合让权等待准则)
      • 记录型信号量：增加了链接所有等待进程链表指针list，只针对多个并发进程共享一个临界资源的情况。符合让权等待准则
      • AND型信号量：对多个临界资源的分配采取原子操作方式，要么把它所请求的资源全部分配到进程，要么一个不分配
      • 信号量集：当资源数量大于可分配的下限值才分配，避免每次只能对某类临界资源进行一个单位的申请或释放
    • 管程(Monitors)机制
      • 定义:一个能同步进程和改变管程中的数据结构的一组操作
      • 产生原因:信号量使大量同步操作分散在各个进程中，使用不当可能造成死锁
      • 组成:管程名称、局部于管程的共享数据结构说明及设置初始值的语句、对该数据结构进行操作的一组过程
      • 实现：设置同步工具(如wait和signal)和条件变量condition(满足多个条件解除挂起和阻塞，防止过长等待)
  • 进程间的同步方法
    • 消息队列
    • 共享存储:在某种程度上，多进程是共同使用物理内存的.共享存储允许不想关的进程访问同一片物理内存.共享内存时两个进程之间共享和传递数据最快的方式.共享内存未提供同步进制，需要借助其他机制管理访问.共享内存时高性能后台开发中最常用的进程同步方式.步骤：申请共享内存-》连接到进程空间-》使用共享内存-》脱离进程空间&删除
    • 信号量
    • Unix域套接字:Unix系统提供的套接字提供了网络套接字类似的功能（nginx）.提供了同步机制，不需借助其他机制管理访问.服务端：创建套接字-》绑定套接字-》监听套接字-》接收和处理信息.客户端：创建套接字-》连接套接字-》发送信息.提供了单机简单可靠的进程通信同步服务.只能在单机使用，不能跨机器使用
  • 线程同步方法
    • 互斥量(互斥锁),线程阻塞,互斥量可以保证先后执行,操作系统提供API->pthread_mutex_t
    • 读写锁:允许多个读者同时访问资源以提高读性能,对于写操作则是互斥的->pthread_rwlock_t,pthread_rwlock_rdlock（读锁）,pthread_rwlock_wrlock(写锁)
    • 自旋锁:线程会反复检查锁变量是否可用,自旋锁不会让出CPU，是一种忙等待状态（死循环等待锁被释放）,避免了线程或线程上下文切换的开销,不适合在单核CPU使用（死循环等待锁被释放）->pthread_spinlock_t
    • 条件变量:配合互斥量使用.条件变量允许线程睡眠，直到满足某种条件;当满足条件时，可以向该线程信号，通知唤醒.pthread_cond_t,pthread_cond_wait（等待条件满足）,pthread_cond_signal（等待被唤醒）
• 经典同步问题
  • 生产者-消费者问题
  • 科学家进餐问题
  • 读者-写者问题

6.7. 进程通信

• 进程通信:进程间的信息交换
• 进程通信的类型
  • 低级通信机制----进程的互斥和同步P、V原语:(效率低、通信对用户不透明、只能传送小部分数据)
  • 高级通信机制(对用户透明、高效传输大量数据)
    • 共享存储器系统(Shared-Memory System)：诸进程读写内存中的共享存储区域实现进程间信息交换
    • 管道(pipe)通信系统：发送进程和接收进程通过一个共享文件(pipe文件)以字符流的形式共享数据
    • 消息传递系统(Message passing system)：诸进程以消息为单位交换数据
      • 直接通信方式:发送进程利用操作系统原语，直接把消息发送给目标进程
      • 间接通信方式:发送和接收进程通过共享中间实体(邮箱)的方式进行消息的发送和接收
    • 客户机-服务器系统(主流)(Client-Server system)
      • 套接字(socket)
        • 概念:是一个通信标识类型的数据结构，是进程通信和网络通信的基本构件
        • 组成：通信的目的地址、通信使用的端口号、通信网络的传输层协议、进程所在的网络地址，以及针对客户或服务程序提供的不同系统调用(或API函数)
        • 基于网络型:在不同主机的网络环境下，一个套接字属于接收进程(服务端)，一个套接字属于发送进程(客户端)
      • 远程过程调用和方法调用RPC(Remote Procedure Call)
        • 概念:用于通过网络连接的系统的通信协议，允许运行于一台主机系统上的进程调用另外一台主机系统上的进程

6.8. 处理器调度

• 处理机调度的层次
  • 高级调度(长程/作业调度)：根据某种算法将外存上处于后备队列中的作业调入内存，为作业创建进程，并放入就绪队列
  • 中级调度(内存调度)：根据某种算法将外存上已具备运行条件的就绪进程重新调入内存，并修改状态为就绪状态(存储管理中的对换功能)
  • 低级调度(进程/短程调度)：根据某种算法将处理机分配给就绪队列中的进程，让进程执行
• 处理机调度算法的评价标准
  • CPU利用率 = CPU有效工作时间/(CPU有效工作时间+CPU空闲等待时间)
  • 公平性:使诸进程获得合理的CPU时间，不会发生进程饥饿现象
  • 策略强制执行:安全策略只要有需要，必须准确执行，即使造成某些工作的延迟也要执行
  • 平均周转时间(作业被提交给系统开始，到作业完成为止的这段时间间隔)短
  • 系统吞吐量高(单位时间内系统所完成的作业数)
• 作业调度
  • 作业(Job):批处理系统是以作业(程序、数据、作业说明书)为基本单位从外存调入内存的，系统根据该说明书对程序进行控制
  • 作业步(Job Step):作业运行期间若干个相对独立，又相互关联的顺序加工步骤
  • 作业控制块(Job Control Block JCB作业在系统中存在的标志)
    • 内容:作业标识、用户名称、用户账号、作业类型、作业状态、调度信息、资源使用情况等
    • 运行过程：
      • 作业进入系统时由作业注册程序为该作业建立一个作业控制块JCB。再根据作业类型放到相应的作业后备队列中等待调度。
      • 调度程序依据一定的调度算法来调度他们，被调度的作业将被装入内存，
      • 在作业运行期间，系统就按照JCB中的信息和作业说明书对作业进行控制。
      • 当一个作业执行结束进入完成状态时，系统负责回收已经分配给它的资源，撤销该作业控制块
  • 作业运行的是三个状态和阶段
    • 收容阶段:作业通过某种输入方式或SPOOLing系统输入到硬盘上，为作业建立JCB并把它放入作业后备队列中(后备状态)
    • 运行阶段:当作业被调度后将获得必要的资源和建立进程，并被放入就绪队列中。一个作业从第一次进入就绪状态开始，直到它运行结束前都处于运行状态
    • 完成阶段:当作业运行完成或发生异常情况而提前结束时(完成状态)
  • 作业调度的主要任务
    • 根据JCB中的信息，检查系统中的资源能否满足作业对资源的需求，并按照一定的调度算法，从外存的后备队列中选取某些作业调入内存，为它们创建进程、分配必要的资源。然后再将创建的进程排在就绪队列上等待调度(多道程序度确定一次接纳多少个作业、调度算法确定选择后备队列中的那些作业调入内存)
  • 调度算法
    • 先来先服务调度算法FCFS(First-come first-served)(等待时间最长的作业优先被调度)
    • 短作业优先算法SJF(short job first)(运行时间最短的作业)
    • 优先级调度算法PSA(priority-scheduling algorithm)(优先级/紧迫程度最高的作业)
    • 高响应比优先算法HRRN(Highest Response Ratio Next)
      • 考虑作业运行和等待时间 响应比 = 响应时间/要求服务时间 = (等待时间+要求服务时间)/要求服务时间
• 进程调度
  • 进程调度指计算机通过决策决定哪个就绪进程可以获得CPU使用权
  • 进程调度任务：保存处理机现场的信息(进程上下文)、按某种算法选取进程、把处理器分配给进程
  • 进程调度机制：排队器、分派器、上下文切换器
  • 进程调度方式：非抢占方式(Nonpreemptive Mode)(直到进程完成工作或因为IO阻塞才会让出处理器)、抢占方式(Preemptive Mode)
  • 引起进程调度事件：进程结束、进程阻塞、执行完系统调用后返回用户进程、被抢占、分时系统时间片用完
  • 不能进程调度的情况：处理中断过程中，在操作系统内核程序临界区中，其他需要完全屏蔽中断的原子操作过程中
  • 抢占式进程调度算法
    • 轮转(round robin,RR)调度算法
      • 就绪队列按FCFS排序，每隔一个时间片产生中断，把CPU分配给队首进程执行一个时间片（略大于一次典型交互所需要的时间）
      • 进程切换时机：进程提前完成；时间片用完时，计时器中断处理程序被激活
    • 优先级调度算法
      • 优先级调度算法类型:非抢占式优先级调度算法、抢占式优先级调度算法
      • 优先级类型:静态优先级（优先级创建时确定、整个运行期间不变）、动态优先级（优先级随进程推进或等待时间而改变）
    • 多队列调度算法：将不同类型或性质的进程固定分配在不同的就绪队列(不同队列采用不同的调度算法和不同优先级)
    • 多级反馈队列调度算法(公认)(multileved feedback queue)
      • 设置多个就绪队列，第一个队列优先级最高，时间片最小，往下优先级降低，时间片越大，
      • 每个队列采用FCFS算法，新进程放入第一队列末尾，i队列进程若在一个时间片未完成，将其转入i+1队列末尾中等待调度
      • 按队列优先级调度，当第i队列空闲才调度第i+1队列中的进程运行
    • 保证调度算法(保证性能:保证处理机分配的公平性，每个进程获得相同的处理机时间)
    • 公平分享调度算法(使所有用户获得相同的处理机时间)

6.9. 死锁

• 死锁(Deadlock):如果一组进程中的每一个进程都在等待仅有该组进程中的其他进程才能引发的事件，那么该组进程就是死锁的
  。死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象。若无外力作用，他们都将无法推进下去，此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程
• 资源分类
  • 可重用性资源(I/O)
    • 进程使用顺序：请求资源-使用资源-释放资源，对资源的请求和释放通常都是利用系统调用来实现的
    • 这类资源单元数目是相对固定的，不允许多个进程共享，进程在运行期间不能创建也不能删除
  • 可消耗性资源(临时性资源)：这类资源单元数目在进程运行期间是不断变化的，由进程动态创建和消耗
  • 可抢占性资源：某进程获得这类资源后，该资源可以被其它进程或系统抢占
  • 不可抢占性资源：某进程获得这类资源后，系统不能强行收回，只能在进程用完后自行释放
• 死锁原因：竞争不可抢占性资源、竞争可消耗性资源、进程推进顺序不当
• 死锁必要条件
  • 互斥条件:进程持有的资源后，其他请求该资源的进程只能等待该进程释放该资源
  • 请求和保持条件:保持至少保持一个资源同时又申请新资源,新资源被占用，请求被阻塞。被阻塞的进程不释放自己保持的资源
  • 不可抢占条件:进程已获得的资源在未使用完之前不能被抢占，只能等待使用完释放
  • 循环等待条件
• 处理死锁方法
  • 预防死锁(破坏死锁的条件)(效率最低)
    • 破坏"请求和保持"条件：进程得到运行初期所需的资源就运行，逐步请求新资源和释放已得到的用完的资源
    • 破坏"不可抢占"条件：请求新资源失败则释放已得到的资源(实现复杂)
    • 破坏"循环等待"条件：对系统所有资源类型赋予不同序号并线性排序，按序号递增的顺序请求资源，请求序号低的资源时必须释放大于等于请求序号的资源
  • 避免死锁(资源分配过程中，防止系统进入不安全状态)(常用)
    • 系统安全状态(系统能按某种进程推进顺序为每个进程分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利完成，称此时的进程树为安全序列，如果系统无法找到这样一个安全序列，则系统处于非安全状态)
    • 银行家Dijkstra算法
  • 检测死锁(通过检测死锁的发生，解除死锁)
    • 资源分配图(Resource Allocation Graph)
    • 死锁(定理)的充分条件:当且仅当资源分配图是不可完全简化（不能让所有的节点都成为孤立的点）时
  • 解除死锁(效率最高)
    • 抢占资源给死锁进程
    • 终止或撤销进程（终止所有死锁进程或按一定规则逐个终止进程）
      • 付出最小代价的死锁解除算法(一次算出逐个进程终止后付出的代价，每次终止付出代价最小的进程，循环计算)

7. linux进程管理

7.1. 进程的类型

• 前台进程：
  • 正在运行并且占用终端的进程
  • 终端Shell 前台进程就是具有终端，可以和用户交互的进程
• 后台进程
  • 没有占用终端的就是后台进程
  • 后台程序基本上不和用户交互，优先级比前台进程低
  • 将需要执行的命令以“&” 符号结束
• 守护（daemon）进程：特殊的后台进程
  • 很多守护进程在系统引导的时候启动，一直运行直到系统关闭
  • 进程名字以“d”结尾的一般都是守护进程（如crond、httpd、sshd、mysqlId）

7.2. 进程的标记

• 进程ID
  • 进程的唯一标记，每个进程拥有不同的ID,表现为一个非负整数，最大值由操作系统限定
  • 操作系统提供fork函数接口创建进程
  • 进程的父子关系可以通过pstree命令查看
    • id为0的进程为idle进程，是系统创建的第一个进程
    • id为1的进程为init进程，是0号进程的子进程，完成系统的初始化。init进程是所有用户进程的祖先进程
• 进程的状态标记
  • map ps （和上面的进程的状态一样）

状态符号	状态说明
R	(TASK_RUNNING),进程处于运行状态
S	(TASK_INTERRUPTIBLE),进程处于睡眠状态
D	(TASK_UNINTERRUPTIBLE),进程正处IO等待的睡眠状态
T	(TASK_STOPPED),进程处于暂停状态
Z	(TASK_READ or EXIT_ZOMBIE),进程正处于退出状态，或僵尸进程

7.3. 操作linux进程的相关命令

• ps命令：常用于显示当前进程的状态，配合aux参数或ef参数和grep命令检索特定进程
  • ps -aux 列出进程信息
  • ps -u 用户名 查看用户名的进程
  • ps -aux | grep '进程名' 查看特定进程
  • ps -ef --forest 查看进程树（父子进程）
  • ps -aux --sort=-pcpu 按cpu使用频率排序CPU进程
  • ps -aux --sort=-pmem 按内存使用频率排序CPU进程
• top命令：查看进程状态
  • us 用户空间占用CPU百分比
  • 1.0%sy 内核空间占用CPU百分比
  • 0.0% ni 用户进程空间内改变过优先级的进程占用CPU百分比
  • 98.7%id 空闲CPU百分比
  • 0.0% wa 等待输入/输出的CPU时间百分比
• kill命令：发送指定信号给进程
  • kill -l 查看操作系统支持的信号
  • kill -9 进程id 删除进程 无条件终止进程

8. 内存管理概述

• 多层结构的存储器系统
  • 层次越高(越接近CPU，存储介质访问速度越快，价格越高，存储容量越小)
  • 寄存器、主存、磁盘缓存属于操作系统存储管理范畴，可通过指令访问，掉电后存储的信息不存在，固定磁盘和可移动存储介质属于设备管理范畴，通过I/O设备访问，掉电后信息存在,耗费更多时间
    
• 用户程序从用户编写的源文件到内存运行的步骤
  • 编译:由编译程序(Compiler)对用户源程序进行编译，形成若干个目标模块(Object Module)
  • 链接:由链接程序(Linker)将编译后形成的一组目标模块以及它们所需要的库函数链接在一起，形成一个装入模块(Load Module)
    • 静态链接方式(程序运行前将目标模块和库函数链接成一个完整的装配模块)
    • 装入时动态链接(目标模块装入内存时，采用边装入边链接的链接方式)
    • 运行时动态链接(将某些模块的链接推迟到程序执行时才进行)
  • 装入:由装入程序(Loader)将装入模块装入内存
    • 绝对装入方式(将目标模块装入时按照在编译时给出的内存的物理地址装入到内存)
    • 可重定位装入方式(将目标模块装入时按照内存情况将装入到内存合适位置，但不允许程序运行时在内存中移动位置)
    • 动态运行时的装入方式(将模块的所有逻辑地址装入内存后，在程序真正执行时才将逻辑地址转换为物理地址)
• 逻辑地址(源代码码经过编译后，目标程序采用的地址)：由程序产生的与段相关的偏移地址部分，是目标程序使用的地址，相对于0开始
• 物理地址(出现在CPU外部地址总线上的寻址物理内存的地址信号)：从逻辑地址到物理地址的转换过程由硬件自动完成
• 内存保护；界限寄存器方法(上、下界寄存器方法、基址和限长寄存器方法)、存储保护键方法

9. 存储管理方式

• 为了将用户程序装入内存，必须为它分配一定大小的内存空间
• 存储器分配管理方式
  • 连续分配方式:为一个用户程序分配一个连续的内存空间，程序中代码或者数据的逻辑地址相邻，内存分配时物理地址相邻
    • 单一连续分配(在单道程序环境下，内存分成os使用的系统区和用户程序独占的用户区)
    • 固定分区分配(将整个用户空间划分为若干个固定大小不等的区域，在每个分区中只装入一道作业)
    • 动态分区分配(根据进程的实际需要，动态地为之分配内存空间)
      • 动态分区分配的数据结构
        • 空闲分区表:每个空闲分区占一个项，表中包括分区号、分区大小和分区始址等数据项
        • 空闲分区链:每个分区的起始部分和尾部设置链接各分区的前向指针和后向指针。将所有的空闲分区链接成一个双向链
      • 动态分区分配算法
        • 基于顺序搜索(依次搜索空闲分区链上的空闲分区，去寻找一个大小满足要求的分区并分割。易产生碎片)
          • 首次适应算法(FF first fit)：将空闲分区链按地址递增的次序链接
          • 循环首次适应算法(NF next fit)：将空闲分区链按地址递增的次序链接，每次从上一次找到的空闲分区的下一个空闲分区开始循环查找
          • 最佳适应算法(BF best fit)：空闲分区按容量从小到大的次序链接
          • 最坏适应算法(WF worst fit)：空闲分区按容量从大到小的次序链接，总是挑选最大的空闲区
        • 基于索引搜索(解决大系统搜索空闲分区速度太慢问题)
          • 快速适应算法(quick fit)
            • 为每一类具有同容量的所有空闲分区单独设立一个空闲分区链表，同时在内存中设立一张管理索引表，每个索引对应一种空闲分区类型和该类型空闲分区链表表头的指针；空闲分区的分类按进程的常用的空间大小进行划分，分配时不做分割，满足对大空间的需求，0碎片
          • 伙伴系统(buddy system)(linux)
            • 解决内存外碎片的问题，将内存内碎片问题转化为外存内碎片问题
            • 内部碎片是已经被分配出去(能明确指出属于哪个进程)的内存空间大于请求所需的内存空间，不能被利用的内存空间
            • 外部碎片：还没有被分配出去(不属于任何进程)，但是由于大小而无法分配给申请内存空间的新进程的内存空闲块
            • 已分配分区和空闲分区大小均为2^k，2^m是整个可分配内存的大小，对具有相同大小的所有空闲分区单独设立一个空闲分区双向链表，不同大小的空闲分区形成了k个空闲分区链表
            • 当需要为进程分配长度为n的存储空间时，先找2^i-1 <= n <= 2^i，满足条件后将2^i分成2个相等的分区，这两个分区称为伙伴，将其中一个用于分配，一个加入到2^i-1的空闲分区链表中，找不到则递增找2^i+1，此时要分割i+1次，在最坏的情况下，可能对2^k的空闲分区进行k次分割才能得到所需分区
            • 当回收大小为2^i的空闲分区时，将其与伙伴分区合并成大小为2^i+1的空闲分区，若事先已存在2^i+1，则继续合并为2^i+2的空闲分区，在最坏的情况下，可能对2^k的空闲分区进行k次合并
          • 哈希算法：建立以分区大小为关键字的哈希表，通过哈希函数计算，得到相应的空闲分区链表表头指针
          • 动态重定位分区分配算法
            • 紧凑: 通过移动内存中作业的位置，把原来多个分散的小分区拼接成一个大分区，频繁使用降低系统效率
            • 相比动态分区分配算法，增加了紧凑功能：当该算法不能满足用户需求时，且当所有的小的空闲分区总和大于用户的要求时，必须进行紧凑，把最大空闲分区分配给用户，不满足则分配失败
        • 分配和回收
          • 设请求分区大小u.size，每个空闲分区链/表中的大小为m.size，不可再切割的剩余分区的大小为size
            
            
  • 离散分配方式（为了解决连续分配产生碎片并使用紧凑后的开销太大的问题）内存分配时物理地址不相邻
    • 分页存储管理方式
      • 页面：将进程的逻辑地址空间分成若干页并编号，从0开始，如第0页、第1页等，页面大小应是2的幂，通常为1-8KB(过小难以分配，过大碎片太多)
      • 物理块：将内存的物理地址空间分成若干块并编号，从0开始，如#0块、#1块等，
      • 页内碎片：分配内存时以块为单位,将进程中的若干页分别装入到多个可以不相邻接的物理块中，进程的最后一页经常装不满一块，形成不可利用的碎片
      • 缺点：有一段连续的逻辑分布在多个页面中，将大大降低执行效率
      • 地址结构：32位，包括页号P，页内地址W。若逻辑地址A，页面大小L，则页号P=INTA/L，页内地址W=[A]MOD L(取余)
      • 页表：为了实现页号到物理块号的地址映射，为每个进程建立一张页面映像表，在进程地址空间内所有页(0-n),依次在表中有一页表项，每个页表项记录了页号和页号的物理块号，页表存放在寄存器或内存中
      • 地址变换机构：实现从逻辑地址到物理地址的转换，实际只是将逻辑地址中的页号转换为内存中的物理块号
        • 基本的地址变换机构：程序被调度后，将本进程的PCB中页表始址F和页表长度M((页表长度M：指的是一共有多少页。页表项长度L：指的是一页占多大内存)放入页表寄存器PTR中。分页地址变换机构会自动地将有效地址寄存器中的有效地址分为页号P和页内地址W两部分，先将页号P与页表长度L进行比较，如果页号大于或等于页表长度，则产生地址越界中断。若未出现越界错误，则再以页号为索引去检索页表，查找操作由硬件执行，将页表始址F与页号P和页表项的长度L的乘积相加，得到该表项在页表中的位置，从页表项中得到该页的物理块号b，将之装入物理地址寄存器中。再将有效地址寄存器中的页内地址W送入物理地址寄存器的块内地址字段中，物理块号b和物理块大小/页面大小/页表项长度L的乘积和页内地址W组合得到物理地址E
        • 具有快表(16-512个页表项)的地址变换结构
          • 解决CPU存取数据时访问两次内存导致计算机处理速度降低的问题(第一次访问页表，第二次从物理地址中存取数据)
          • 访问数据的过程:在CPU给出有效地址后，由地址变换机构自动将页号P送入高速缓冲寄存器（联想寄存器/快表），并将此页号与高速缓存中的所有页号进行比较，若有匹配的页号，可直接读出物理块号，若没有匹配的页号，还需从页表中读出的物理块号，同时将此页表项存入快表
      • 访问内存的有效时间ETA(Effective Access Time)：从进程发出指定逻辑地址的访问请求，经过地址变换到内存中找到对应的实际物理地址单元并取出数据所花费的总时间
      • 两级和多级页表(解决找到大的连续的内存空间存放页表的问题)
        • 现代计算机系统可以支持非常大的逻辑地址空间（2^32-2^64）页表变得非常大，要占用非常大的内存空间如，具有32位逻辑地址空间的分页系统，规定页面大小为4kb。则在每个进程页表中的页表项可达1M（2^20）个，如果每个页表项占用1Byte。故每个进程仅仅页表就要占用1MB的内存空间
        • 将页表再进行分页，使每个页面的大小与内存物理块的大小相同，并编号0#页、1#页...然后离散地将各个页面分别存放在不同的物理块中，同样要为离散分配的页表再建立一张页表(外层页表)，在每个页表项中记录了页表页面的物理块号
        • 在内层页表项存放的是进程的某页在内存中的物理块号，而在外层页表项中存放某个页表分页的首址
        • 增加设置一个外层页表寄存器，用于存放外层页表的始址，并利用逻辑地址中的外层页号作为外层页表的索引，从中找到指定页表分页的始址，再利用外层页内地址作为指定分页的索引，找到指定页表项，其中含有该页在内存的物理块号，用该块号P和页内地址d即可构成访问的内存物理地址
        • 32位机器使用两级页表，64位使用三级页表结构比较好
      • 反置页表（为了减少页表占用的内存空间，）
        • 为每个物理块设置一个页表项(页号和其所隶属进程的标识符)，并将它们按物理块的编号排序，同时为每个进程建立一个外部页表（包含各个页在外存的物理位置），利用反置页表进行地址变换时，是根据进程标识符和页号，去检索反置页表，如果检索到与之匹配的页表项，则该页表项中的序号i便是该页所在的物理块号，可用该块号与页内地址一起构成物理地址送内存地址寄存器，找不到则表示此页未装入内存，此时需要检索外部页表
    • 分段存储管理方式
      • 段：将进程的逻辑地址空间分为长度不等的若干段，每个段使用一段连续的地址空间并从0开始编址，段的长度由相应的逻辑信息组的长度决定，逻辑地址由段号和段内地址组成
      • 段表：为每个进程建立一张段映射表，每个段表项记录了段号、段的起始地址F和段的长度M，段表存放在寄存器或内存中
      • 段地址结构：段号，段内偏移
      • 地址变换机构（实现从逻辑段到物理内存区的映射）
        • 系统将逻辑地址中的段号S与段表长度TL比较，若S>TL，产生越界中断信号；若未越界，则根据段表寄存器的始址F和该段的段号S，F+S*段长SL计算出该段对应的段表项的位置，从中读出该段在内存的起始地址b，若段内地址W>段长SL，发出越界信号，若未越界，则将该段的基址b与段内地址W相加，得到访问内存的物理地址E
        • 与分页系统一样，都要访问两次内存，也可以增设联想寄存器保存最近常用的段表项
      • 分页和分段的主要区别
        • 页是信息的物理单位，分页仅仅是系统管理上的需要，段是逻辑单位，段是一组意义相对完整的信息，更好的满足用户的需要
        • 页的大小固定且由系统决定，段的长度不固定且由用户编写的程序决定
        • 分页地址空间是一维的，属于单一的线性地址空间，分段地址空间是二维的，标识一个地址需要给出段名和段内地址
      • 信息共享：分页系统需要给每个进程设置对应的页表项存放数据，分段系统只需为进程设立一个段表项存放数据，进程内共享
    • 段页式存储管理方式
      • 既具有分段系统便于实现、分段可共享、易于保护、可动态连接优点，更好满足用户需求。又能像分页系统解决内存的外部碎片问题。提高内存利用率
      • 段页：将进程逻辑空间分成若干段，再把每个段分成若干页，需要配置段表和页表，段表内容为页表起始址和页表长度
      • 地址结构：段号S、段内页号P和页内地址W(配置一个段表寄存器，存放段表起始址F和段长TL)
      • 地址变换过程：首先利用段号S，与段长TL比较，若S<TL，未越界，利用段表起始址F加段号S乘段长TL求出该段对应的段表项在段表中的位置，从中得到该段的页表长度C页表始址d，若页号P>C，则产生越界中断，若未越界则利用逻辑地址中的段内页号P乘以页表项长度加上页表始址d获得对应页的页表项位置，从中得出该页所在的物理块号b，再利用块号b和页内地址W来构成物理地址E
      • 三次访存获得指令或数据：访问内存中的段表，获得页表始址；访问内存中的页表，获得页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；从第二次访问所得的地址中取出指令或数据。可以增设高速缓冲寄存器

9.1. 多道程序环境下的对换技术(Swapping)

• 对换:把内存中暂时不能运行的进程或暂时不用的程序和数据换出到外存上，再把已具备运行条件的进程或进程所需要的程序和数据换入内存
• 对换时机：当许多进程在运行时经常发生缺页且出现内存紧张时启动对换程序，缺页率明显减少，吞吐量下降时，暂停对换程序
• 对换类型
  • 进程/整体对换:处理机的中级调度（存储器的对换功能）
    • 对换空间的管理（磁盘空间分为文件区和对换区）文件区采用离散分配的方式、对换区采用连续分配的方式
      • 数据结构：采用空闲分区表或空闲分区链，空闲分区表每个表目包含对换区的首址及其大小，分别用盘块号和盘块数表示
      • 对换空间的分配与回收：与动态分区方式一样
    • 进程的换出和换入
      • 选择被换出的进程(处于阻塞或睡眠状态的进程\优先级低的进程)(只能换出非在用的非共享的程序和数据段)
      • 进程换出过程:先申请对换空间，成功则启动磁盘，将该进程的程序和数据传送到磁盘的对换区上，回收该进程所占用的内存空间。并对该进程控制块和内存分配表等数据结构进行相应的修改，一直换出到无阻塞进程为止
      • 选择被换入的进程(处于就绪状态但已换出的进程\换出时间最久的进程)
      • 进程换入过程:申请内存，成功则直接从外存调入内存，失败则换出某些进程，腾出足够内存后，再将进程调入，一直换入到无就绪且换出状态的进程或者无足够的内存为止.
  • 页面（分段）/部分对换:以进程的一个页面或分段单位进行的对换，请求分页和请求分段存储管理（虚拟存储系统）

10. linux的存储管理

• 伙伴系统
• linux交换空间：（Swap）是磁盘的一个分区（速度慢，不能频繁使用）。linux物理内存满时，会把一些内存交换至Swap空间。Swap空间是初始化系统时配置的
• 作用
  • 冷启动内存依赖（把少用的内存放这。释放更多物理内存）
  • 系统睡眠依赖（系统睡眠内存数据）
  • 大进程空间依赖（物理内存不够时）

Swap空间	虚拟内存
存在于磁盘	存在于磁盘
与主存发生置换	与主存发生置换
操作系统概念	进程概念
解决系统物理内存不足问题	解决进程物理内存不足问题

11. 虚拟存储器

11.1. 虚拟存储器概述

• 虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。
• 引入虚拟内存的原因：存储管理难以满足大作业需要大内存的需求(一个游戏几十G，物理内存只有4G，游戏怎么运行)
• 传统存储管理特征：一次性(作业全部装入内存才能开始运行)、驻留性(作业常驻内存直到运行结束)
• 局部性原理：在较短的时间内，程序的执行仅局限于某个部分，相应的，它所访问的存储空间也局限在某个区域
• 虚拟存储器：在原有存储系统基础上，具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储系统。其逻辑容量由内存容量和外存容量决定，运行速度接近于内存，每位成本接近外存
• 虚拟存储器的特征
  • 多次性：一个作业只需将当前需要运行的那部分程序和数据装入内存即可开始运行，每当运行到尚未调入的那部分程序时，再将它调入
  • 对换性：作业在运行期间可以换入、换出
  • 虚拟性：能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量
• 程序运行时，无需全部装入内存，装载部分即可.如果访问也不在内存，则发出缺页中断，发起页面置换

11.2. 虚拟存储管理方式

• 请求分页存储管理方式
  • 请求分页的页表机制：请求页表，基本作用仍是将用户地址空间中的逻辑地址映射为内存空间中的物理地址，页表项包括
    • 页号、物理块号
    • 访问字段A：记录本页在一段时间内被访问的次数或最近已有多长时间未被访问，供置换算法在选择换出页面时参考
    • 修改位M：标识该页在调入内存后是否被修改过。M位供置换页面时参考；如果被修改，则要写回到外存上，没被修改则不需要操作
    • 状态为/存在位/位字P：只有一位，表示该页是否调入内存，供程序访问时参考
    • 外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考
  • 缺页中断机构：每当所要访问的页面不在内存时，便产生缺页中断，请求OS将所缺之页调入内存；与一般中断的区别：在指令执行期间产生和处理中断信号，一条指令在执行期间可能产生多次缺页中断
  • 地址变换机构
    

11.3. 页面调入策略

• 何时调入页面
  • 预调页策略：将预计不久后便会被访问的页面先调入内存
  • 请求调页策略：一个页面只有在被用到时才被调入内存中，否则放在外存中
• 何处调入页面
  • 系统有足够对换空间：全部从对换区调入所需页面，以提高调页速度，在进程运行前，便将与该进程有关的文件从文件区拷贝到对换区
  • 系统缺少足够的对换空间：不会修改的文件，从文件区调入，当换出这些页面时，不必重写到磁盘，需要仍从文件区调入，但对于可能被修改的部分，换出时调到对换区，需要时再从对换区调入
  • UNIX方式：由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于被放在对换区，因此下次调入时应从对换区调入。由于UNIX系统允许页面共享，为此，某进程所请求的页面有可能已被其他进程调入内存，此时也无需再从对换区调入
• 页面调入过程
  • 每当程序所要访问的页面未在内存时（存在位为0），便向CPU 发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后转入缺页中断处理程序，该程序通过查找页表得到该页在外存的物理块后，如果此时内存能容纳新页，则启动磁盘I/O，将所缺之页调入内存，然后修改页表，如果内存已满，则需先按照某种置换算法，从内存中选出一页准备换出，如果该页未被修改过（修改为为0），可不必将该页写回磁盘，但如果此页被修改（修改位为1），则必须将它写回磁盘，然后再吧所缺的页调入内存，并修改页表中相应的页表项，置其存在位为1，并将页表项写入快表中。在缺页调入内存后，利用修改后的页表形成所要访问数据的物理地址，再去访问内存数据。
• 缺页率
  • 进程访问页面(在内存中)成功次数S，失败次数(页面不在内存中，需要从外存调入)F，则该进程总访问次数A=S+F，缺页率=F/A
  • 缺页率与页面大小（反比）和进程所分配物理块的数目（反比）、页面置换算法、程序固有特性有关

物理块分配策略

• 最小物理块数(保证进程正常运行所需的最小物理块数)的确定:与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式
• 物理块分配算法
  • 平均分配算法：将系统所有可供分配的物理块平均分配给各个进程
  • 按比例分配算法：根据进程的大小按比例分配物理块（每个进程所能分到的物理块数=该进程的页面数*物理块总数/页面总数）
  • 考虑优先权的分配算法：根据个进程的优先权分配，为高优先权的进程适当增加相应份额

11.4. 内存分配策略

• 固定分配局部置换策略
  • 固定分配：为每个进程分配一组固定数目的物理块，在进程运行期间不再改变
  • 局部置换：进程缺页时只能从分配给该进程的页面中选出一页换出，再调入一页以保证分配给该进程的内存空间不变
• 可变分配全局置换策略
  • 可变分配：先为每个进程分配一定数目的物理块，在进程运行期间根据情况做改变
  • 全局置换：进程缺页时从空闲物理块队列取出一块分配给进程，或从所有进程的所有物理块中选择一块换出并将缺页调入
• 可变分配局部置换策略

11.5. 页面置换算法(Page-Replacement Algorithms)

• 页面置换算法：选择换出页面的算法.替换策略发生在缓存-主存层次、主存-辅存层次
• 最佳(Optimal)置换算法：选择以后永不使用的、最长(未来)时间内不再被访问的页面淘汰，缺页率最低，无法实现，评价标准
• 先进先出（FIFO）页面置换算法：选择在内存中驻留时间最久的页面淘汰，实现简单，只需把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面
• LRU最近最久未使用算法（LRU Least Recently Used）：选择最近最久未使用的页面淘汰、实现，赋予每个页面一个访问字段，用来记录上次被访问以来所经历的时间t，当要淘汰一个页面时，选择现有页面中其t值最大的淘汰。硬件支持：移位寄存器，栈
• 最少使用置换算法（LFU Least Frequently Used）：选择在最近使其最少使用的页面淘汰、硬件支持：移位寄存器
• CLOCK置换算法/最近未用算法(NRU Not Recently Used)（无需硬件支持，成本低）
  • 简单的CLOCK算法：选择页面换出条件：未使用过
    • 只需为每页设置一位访问位，再将内存中所有页面通过链接指针链成一个循环队列。页面被访问时，访问位置为1。置换算法在选择一页淘汰时，只需检查页的访问位。如果是0，就选择该页换出，若为1，则置为0，暂不换出，给予该页第二次驻留内存的机会，在按照FIFO算法检查下一个页面，当检查到队列中的最后一个页面时，若其访问位仍为，则再返回到队首去检查第一个页面
  • 改进的CLOCK算法：选择页面换出条件：未使用过和未被修改过的页面
    • 访问位A和修改位M可以组合成1类（A=0，M=0）、2类（A=0，M=1）、3类（A=1，M=0）、4类（A=1，M=1）页面
    • 从指针所指示的位置开始，扫描循环队列，将第一个1类页面作为选中的淘汰页。扫描期间不改变访问位A；第二轮扫描寻找2类页面，将第一个2类页面作为淘汰页，所有扫描过的页面的访问位置都置为0；第三轮扫描将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步寻找1类页面，失败时再重复第二步寻找2类页面，此时就一定能找到被淘汰的页
• 页面缓冲算法(PBA Page Buffering Algorithm)（解决页面换进换出开销过大的问题）
  • 影响页面换进换出效率的因素：页面置换算法、写回磁盘的频率、读入内存的频率
  • 主要特点：显著降低页面换进、换出的频率、采用简单的置换策略如FIFO算法
  • 在内存中设置一个空闲页面链表，用于分配给频繁发生缺页的进程，降低进程的缺页率。进程需要读入页面时，利用空闲块链表中的第一个物理块装入该页，当一个未被修改的页要换出时，把它挂在空闲链表的末尾，用到再取出这些页表
  • 在内存中设置修改页面链表，当进程需要将一个已修改的页面换出时，把它挂在修改页面链表末尾。降低将已修改页面写回磁盘的频率，降低将磁盘内容读入内存的频率

11.6. 抖动与工作集

8.PNG

• 抖动(Thrashing)：淘汰页在短时间内被频繁调入调出，以致一个进程在运行中把大部分时间都花费在页面置换工作上的现象
• 缺页率与物理块数成反比，超过一定数量时，增加物理块数对缺页率影响不大
• 产生抖动的原因：请求分页系统中每个进程只能分配到所需全部内存空间的一部分
• 工作集：在某段时间间隔Δ里，进程实际所要访问页面的集合。Δ称为工作集的窗口尺寸
• 抖动的预防方法
  • 采用局部置换策略
  • 把工作集算法融入到处理机调度中
  • 利用"L=S"准则调节缺页率（L是缺页的平均时间，S是平均缺页服务时间）
  • 选择暂停的进程（优先级低，不重要，但较大的进程）

11.7. 请求分段存储管理方式

• 请求分段的段表机制
  • 段名、段长、段基址(段在内存中的起始地址)
  • 存取方式：只执行、只读和允许读/写
  • 访问字段A：用于记录该段被访问的频繁程度，提供置换算法在选择换出页面时参考
  • 修改位M：标识该页在调入内存后是否被修改过。供置换页面时参考
  • 存在位P：指示本段是否已调入内存，供程序访问时参考
  • 增补位：表示本段在运行过程中中是否做过动态增长
  • 外存地址：指示本段在外存中的起始地址，即起始盘块号
• 缺段中断机构
  
• 地址变换机构
  
• 分段的共享
  • 共享段表：在系统中配置一张共享段表，所有各共享段表中占有一个表项。
    • 共享的段号、段长、内存地址、状态（存在位）、外存始址以及共享计数
    • 共享进程计数count：记录该段被多少个进程共享，count为0的时候，才由系统回收该段所占内存区
    • 存取控制字段：对于一个共享段，应为不同的进程赋予不同的存取权限
    • 段号：对于一个共享段，在不同进程中可以有不同的段号，每个进程可以用自己进程的段号去访问该共享段
  • 共享段的分配和回收
    • 共享段的分配：对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程段表的相应项中，还需在共享段表中增加一表项，填写请求使用该共享段的进程名、段号和存取控制等有关数据，把count置为1，当又有其他进程需要调用该共享段时，由于该共享段已被调入内存，故此时无须再为该段分配内存，而只需调用进程的段表中增加一表项，填写该共享段的物理地址。在共享短的段表中增加一个表项，填上调用进程的进程名，该共享段在本进程的段号、存取 控制等，在执行count=count+1操作，以表明两个进程共享该段。以后，凡有进程需要访问此共享段的，都按上述方式在共享段的段表中增加一个表项
    • 共享段的回收，当共享此段的某进程不需要该段时，应将该段释放，包括撤销在该进程段表中共享段所对应的表项，以及执行count=count-1操作，若结果为0，则须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项，表明此时已经没有进程使用该段，否则，只是取消调用者进程在共享段表中的有关记录
• 分段保护
  • 越界检查：利用地址变换机构完成
  • 存取控制检查：以段为基本单位进行，在段表的每个表项设置了一个存取控制字段(只读、只执行、读/写)
  • 环保护机构：一个程序可以访问驻留在相同环或较低特权环中的数据、可以调用驻留在相同环或者较高特权环的服务

12. 输入输出系统

12.1. I/O设备分类

• 广义的IO设备：对CPU而言，凡是对CPU进行数据输入/输出的都是输入/输出设备
• 按使用特性分类
  • 存储设备：U盘，内存，磁盘
  • 交互设备：键盘，显示器，鼠标
• 按信息交换的单位分类
  • 块设备：磁盘，SD卡
  • 字符设备：打印机，Shell终端
• 按设备的共享属性分类；独占设备，共享设备，虚拟设备
• 按传输速率分类：低速设备，中速设备，高速设备

12.2. I/O系统的基本功能

• 隐藏物理设备的细节(通过对设备加以适当的抽象、隐藏物理设备的实现细节)
• 与设备的无关性(可使用抽象的I/O命令和抽象逻辑设备名使用设备、提高OS的可移植性和易适应性)
• 提高处理机和I/O设备的利用率(尽量使处理机和I/O设备并行操作)
• 对I/O设备进行控制(对I/O设备控制方式：轮询的可编程I/O方式、中断的可编程I/O方式、直接存储器访问方式、I/O通道方式)
• 确保对设备的正确共享(独占设备：进程互斥访问这类设备、共享设备：一段时间内允许多个进程同时访问的设备)
• 错误处理(持久性错误和临时性错误处理)

12.3. I/O系统的层次结构和模型

• 用户层I/O软件：向用户提供与I/O操作相关的库函数(产生I/O请求、格式化I/O、Spooling)
• I/O系统接口：向上层提供对设备进行操作的抽象的I/O命令
• 块设备接口(数据的存取和传输都是以数据块为单位的设备)接口：用于控制块设备的输入或输出，将抽象命令映射为底层操作
• 流设备接口(数据的存取和传输时以字符为单位的设备(不可寻址))接口：用于控制字符设备的输入或输出
• 网络通信接口
• 设备独立性软件：设备命名、保护、分配和释放等，同时为设备管理和数据传送提供必要的存储空间(映射、保护、分块、缓冲、分配)
• 设备驱动程序：用于具体实现系统对设备发出的操作指令，驱动I/O设备工作的驱动程序（设置设备寄存器、检查状态）
• 中断处理程序：用于保存被中断进程的CPU环境，转入相应的中断处理程序进行处理，处理完毕再恢复现场后，返回到被中断的进程
• 软件/硬件(RW/HW)接口：
  

13. I/O设备和设备控制器概述

• I/O设备由执行I/O操作的机械部分（一般的I/O设备）和执行控制I/O的电子部件(设备控制器或适配器)组成。

13.1. 设备寻址方式

• 利用特定的I/O指令：为每个控制寄存器分配一个I/O端口和特定的I/O指令，访问内存和访问设备需要两种不同的指令
• 内存映像I/O：内存单元地址和设备控制器的寄存器地址都采用k，k处于0-n-1时是内存地址，若k大于n时是某个控制器寄存器地址

13.2. 设备控制器（分成控制字符设备的控制器和控制块设备的控制器）

• 基本功能
  • 接收和识别CPU命令：能接受并识别处理机发来的多种命令。对所接收的命令进行译码，其控制寄存器存放接收的命令和参数
  • 数据交换：通过数据总线和数据寄存器实现CPU与控制器之间、控制器与设备之间的数据交换。
  • 标识和报告设备的状态：通过状态寄存器记录设备状态供CPU查询
  • 地址识别：通过地址译码器能够识别器所控制的每个设备的地址。
  • 数据缓冲区：I/O设备的速率较低，而CPU和内存的速率较高
  • 差错控制：检测I/O设备传送的数据并向CPU报告，出错时，CPU将作废错误数据并重传
• 组成
  • 设备控制器与CPU的接口：实现了CPU与设备控制器之间的通信，含有地址线、数据线、控制线三类信号线；数据线通常与两类寄存器相连：1.数据寄存器，存放设备送来的数据或者CPU送来的数据；2.控制/状态寄存器，存放从CPU送来的控制信息或设备的状态信息
  • 设备控制器与设备的接口：具有多个设备接口，每个接口中都存在数据、控制和状态三种类型的信号
    • 数据信号线：对于输入设备：由外界输入的信号经过转换器转换后的数据暂存缓存器，当数据量达到一定比特(字符)后，再通过一组数据信号线传送给设备控制器；对于输出设备：将从设备控制器经过数据信号线传送来的一批数据先暂存于缓冲器中，井转换器适当转换后，逐个字符输出
    • 控制信号线：传送规定了设备将要进行操作的控制信号
    • 状态信号线：传送设备当前状态的状态信号
  • I/O逻辑：用于实现对设备的控制，启动设备时，cpu利用控制线向控制器发送启动命令，通过地址线发送地址，由控制器的I/O逻辑对地址进行译码，在根据所译出的命令对所选设备进行控制

15.PNG

13.3. I/O通道

• 当主机所配置的外设很多时，CPU和设备控制器之间增设了I/O通道（特殊的处理机，只能执行与I/O操作有关的指令，无内存，通道与CPU共享内存，使I/O操作更加独立）
• CPU只需向I/O通道发送一条I/O指令，通道便从内存中取出本次要执行的通道程序执行，当通道完成I/O任务后，才向CPU发中断信号
• 通道类型，根据交换信息方式
  • 字节多路通道：多个非分配型子通道分别连接一台I/O设备，子通道按时间片轮转方式共享主通道，不适用于连接高速设备
  • 数组选择通道：一个分配型子通道连接多台高速设备，在一段时间内控制一台设备执行一通道程序和数据传送，通道利用率低
  • 数组多路通道：含有多个非分配型子通道连接多个高速设备，数据传输率高，通道利用率高，其数据传送按数组方式进行
• 瓶颈(通道价格昂贵，数量少于设备，一旦被其他设备占用，无法启动设备)问题：通过增加设备到主机间的通路而不增加通道来解决

14. 中断机构和设备驱动程序

14.1. 中断机构

• 中断/外中断：CPU对I/O设备发来的中断信号的一种响应。
• 陷入/内中断：由CPU内部事件引起的中断。
• 中断向量表：在中断向量表中为每种设备相应的中断处理程序设置一个表项，包括中断号和该设备中断处理程序的入口地址，当设备发来中断请求信号时，由中断控制器根据该设备的中断号去查找中断向量表，取得该设备中断处理程序的入口地址，转入中断处理程序执行
• 中断优先级：每个中断源对服务要求的紧急程度并不相同
• 对多中断源的处理方式
  • 屏蔽(禁止)中断：所有中断按顺序依次处理，简单，不能用于对实时性要求高的中断请求
  • 嵌套中断：CPU优先处理优先级高的中断请求，高优先级的中断请求可以抢占正在运行的低优先级中断处理机
• 中断处理程序的处理过程
  • 测定是否有未响应的中断信号：程序每当执行完当前指令后，处理机都要测试是否有未响应的中断信号
  • 保护被中断进程的CPU环境：保存从中断现场恢复到当前进程运行所需要的信息，把被中断进程的CPU现场信息压入中断栈中
  • 转入相应的设备处理程序：由处理机对各个中断源进行测试。确定本次中断的I/O设备并发送确认信号，将相应的设备中断处理程序的入口地址装入到程序计数器中
  • 中断处理：不同设备有不同的中断处理程序
  • 恢复CPU现场并退出中断

14.2. 设备驱动程序

• 主要任务：接收上层软件发来的抽象I/O请求，转换为具体要求后，发送给设备控制器，启动设备去执行；反之，将由设备控制器发来的信号传送给上层软件
• 由于驱动程序与硬件密切相关，每一类设备配置一种驱动程序
• 功能
  • 接收由与设备无关的软件发来的命令和参数，并将命令中的抽象要求转换为与设备相关的底层操作序列
  • 检查用户I/O请求的合法性，了解I/O设备状态，传递与I/O设备操作有关的参数，设置设备的工作方式
  • 发出I/O命令，如果设备空闲，便立即启动I/O设备，完成指定的I/O操作；如果设备忙碌，则将请求者的请求块挂在设备队列上等待
  • 及时响应由设备控制器发来的中断请求，并根据其中断类型，调用相应的中断处理程序进行处理
• 特点
  • 驱动程序是与设备无关的软件和设备控制器之间通信和转换的程序。
  • 驱动程序与设备控制器和I/O设备的硬件特性紧密相关。
  • 驱动程序与I/O设备所采用的I/O控制方式紧密相关。
  • 由于驱动程序与硬件紧密相关，因而其中的一部分必须用汇编语言编写。
  • 驱动程序应允许可重入，一个正在运行的驱动程序常会在一次调用完成前被再次调用。
• 设备处理方式
  • 为每一类设备设置一个进程，专门用于执行这类设备的I/O操作
  • 在整个系统中设置一个I/O进程，专门用于执行系统中所有各类设备的I/O操作。也可以设置一个输入进程和一个输出进程
  • 不设置专门的设备处理进程，只为各类设备设置相应的设备驱动程序，供用户或程序进程调用（常用）
• 设备驱动程序的处理过程
  • 将抽象要求转为具体要求
  • 检查I/O请求的合法性
  • 检查设备的状态：状态寄存器
  • 传送必要的参数：在确定设备处于就绪状态后，便可向控制器的相应寄存器传送数据及控制本次数据传输有关的参数
  • 启动I/O设备：驱动程序向控制器中的命令寄存器传送相应的控制命令
• 及时响应由设备控制器发来的中断请求，并根据其中断类型，调用相应的中断处理程序进行处理，并传送给上层软件
• 对I/O设备的控制方式
  • 使用轮询的可编程I/O方式（CPU绝大部分时间都处于等待I/O设备完成数据I/O的循环测试中，造成对CPU极大的浪费）
  • 使用中断的可编程I/O方式(以字(节)为单位进行中断)CPU与I/O设备并行工作。仅当I/O完成才需CPU做中断处理
  • 直接存储器访问方式(以数据块为单位进行中断)
    • 传送的数据是从设备直接送入内存的，或者相反，仅在传送一个或多个数据块的开始和结束时，才需CPU干预。，数据传送是在控制器下完成的
    • DMA控制器的组成
      • 主机与DMA控制器的接口（DMA控制器必须包含四类寄存器）
        • 命令/状态寄存器CR，存放I/O命令，控制信息，设备状态
        • 内存地址寄存器MAR：存放数据从设备传送到内存的起始目标地址或由内存到设备的内存源地址
        • 数据寄存器DR：暂存从设备到内存或从内存到设备的数据
        • 数据计数器DC：存放本次CPU要读或写的字数
      • DMA控制器与块设备的接口
      • I/O控制逻辑
    • DMA工作过程

- I/O通道控制方式(以一组数据块的读写及有关的控制和管理为单位的干预、实现CPU、通道和I/O设备三者并行操作)
- 通道是通过执行通道程序并与设备控制器共同实现对I/O设备的控制的。由一系列通道指令所构成的
- 通道指令包含以下信息
- 操作码：规定了指令所执行的操作
- 内存地址：标明字符送入内存和从内存取出时的内存首址
- 计数：本指令所要读或写的数据的字节数
- 通道程序结束位P：表示通道程序是否结束，为1表示本条指令是通道程序的最后一条指令
- 记录结束标志R：0表示本通道指令与下一条指令所处理的数据同属一个记录，1表示处理某记录的最后一条指令

14.3. 与设备无关的I/O软件

• 设备无关性：应用程序中所使用的设备，不局限于使用某个具体的物理设备
• I/O重定向：用于I/O操作的设备可以更换(重定向)，不必改变应用程序
• 设备分配
  • 设备分配中的数据结构
    • 设备控制表DCT：每个设备配一张设备控制表，记录设备的特性以及I/O控制器的连接情况
      • 设备类型：type
      • 设备标识符：deviceid
      • 设备状态：等待/不等待 ，忙/闲
      • 设备队列队首指针
      • 发生错误的重复执行次数或时间
      • 与设备连接的控制器表指针
    • 控制器控制表COCT：每个控制器配一张记录控制器情况的控制表，反映设备控制器使用状态
    • 通道控制表CHCT：每个通道配置一张通道控制表，反映通道情况
    • 系统设备表SDT：记录系统中全部设备的情况，每个设备占一个表目(设备类型、设备标识符、设备控制表、设备驱动程序入口)
  • 设备分配时考虑的因素
    • 设备的固有属性
      • 独占设备：进程得到设备后，只能等待该进程完成释放才可以继续分配
      • 共享设备：可以同时分配给多个进程使用，须注意这些进程访问该设备的先后次序
      • 虚拟设备：可以同时分配给多个进程
    • 设备分配算法: 先来先服务、优先级高者优先
    • 设备分配中的安全性
      • 安全分配方式：一旦进程已经获得某种设备后便阻塞，不能再请求任何资源，而它阻塞时又不保持任何资源
      • 不安全分配方式：进程发出I/O请求后需要时又发出I/O请求。仅当进程所请求的设备已被占用时，才进入阻塞状态
    • 独占设备的分配程序
      • 基本的设备分配程序（分配设备、分配控制器、分配通道）
      • 设备分配程序的改进：首先从SDT中找出第一个该类设备的DCT、若该设备忙，又查找第二个该类设备的DCT，仅当所有该类设备都忙时，才吧进程挂载该类设备的等待队列上，而只有一个该类设备可用，系统便进一步计算分配该设备的安全性并分配设备
  • 逻辑设备名到物理设备名映射的实现
    • 逻辑设备表LUT(Logical Unit Table)：每一项包括：逻辑设备名、物理设备名、设备驱动程序的入口地址；在整个系统或为每个用户设置一张LUT

14.4. 用户层的I/O软件

14.5. 假脱机（Spooling）系统（虚拟设备技术）：将独占设备改成共享设备的技术

• Spooling技术：将一台物理I/O设备虚拟为多台逻辑I/O设备，同样允许多个用户共享一台物理I/O设备。
• SPOOLing系统组成
  • 输入井和输出井：磁盘上开辟的两个存储区域，输入井模拟脱机输入时的磁盘，用于收容设备输入的数据，输出井模拟脱机输出的磁盘，用于收容用户程序的输出数据。输入输出井中的数据一般以文件的形式组织管理（井文件）。一个文件仅存放某个进程的输入或输出数据，所有进程的输入输出文件链接成为一个输入输出队列
  • 输入缓冲区和输出缓冲区：内存中开辟两个缓冲区
  • 输入进程和输出进程：输入进程用于模拟脱机输入时的外围控制机、输出进程模拟脱机输出时的外围控制机
  • 井管理程序：控制作业与磁盘井之间的信息交换，当作业执行过程中向某台设备发出启动输入或输出请求时，由操作系统调用井管理程序，由器控制从输入井读取信息或将信息输出至输出井
• 关于慢速字符设备如何与计算机主机交换信息的一种技术，利用高速共享设备将低速的独享设备模拟为高速的共享设备，逻辑上，系统为每一个用户都分配了一台独立的高速独享设备
  • 把同步调用低速调用改为异步调用，在输入、输出之间增加了排队存储环境（输入井、输出井）
  • SPOOLing负责输入输出井与低速设备之间的调度
  • 逻辑上，进程直接与高速设备交互，减少了进程的等待时间
    

14.6. 缓冲区管理

• IO设备的缓存区（CPU与IO设备速率不匹配），减少CPU处理IO请求的频率，提高CPU与IO设备之间的并行性
• 一个存储区域，由专门的硬件寄存器组成或者利用内存
• 引入原因
  • 缓和CPU与I/O设备间的速度不匹配矛盾
  • 减少对CPU中断的频率，放宽对CPU中断响应时间的限制
  • 解决数据粒度不匹配问题：解决生产者和消费者之间交换的数据粒度不匹配的问题
  • 提高CPU和I/O设备之间并行性、提高系统的吞吐量和设备利用率
• 单缓冲区：每当用户进程发出一I/O请求时，操作系统便在主存中为之分配一缓冲区
• 双缓冲区：解决了生产者和消费者在使用缓冲区必须互斥的问题，即生产者必须等到消费者取走缓冲区的数据才能继续生产
• 环形缓冲区(一组内存块的链表)
  • 组成
    • 多个大小相同的缓冲区，作为输入的多缓冲区可以分为：用于装输入数据的空缓冲区R、已装满数据的缓冲区G以及计算进程正在使用的现行工作缓冲区C三种类型
    • 三个指针：指示下一个可用缓冲区G的指针Nextg、指示输入进程下次可用的空缓冲区R的指针Nexti，用于指示计算进程正在使用的缓冲区C的指针Current
  • 环形缓冲区的使用：Getbuf、Releasebuf过程
  • 进程之间的同步问题
    • Nexti指针追赶上Nextg指针：输入进程输入数据的速度远大于计算进程处理数据的速度，已把全部可用的空缓冲区装满，再无缓冲区可用。此时，输入进程应阻塞，直到计算进程吧某个缓冲区中的数据全部提取完，使之成为空缓冲区R，并调Releasebuf过程将它释放时，才将输入进程唤醒，这种情况被称为系统受计算限制
    • Nextg指针追赶上Nexti指针：输入数据的双速度地狱计算进程处理数据的速度，使全部装有数据的缓冲区都被抽空，再无装有数据的缓冲区提供计算进程提取数据。这时计算进程只能阻塞，直至输入进程有装满某个缓冲区，并调用Releasebuf过程将它释放时，才去唤醒计算进程，这种情况被称为系统受I/O限制
• 缓冲池(Buffer Pool)(常用)(包含了一个管理的数据结构及一组操作函数的管理机制，用于管理多个缓冲区)
  • 缓冲池的组成：每个缓冲区缓冲首部（包括缓冲区号、设备号、设备上的数据块号、同步信号量以及队列链接指针）以及用于存放数据的缓冲体
  • 一般将缓冲池中具有相同类型的缓冲区链接成一个队列
    • 空白缓冲队列emq：由空白缓冲区所链成的队列，队首指针和队尾指针分别指向该队列的首缓冲区和尾缓冲区
    • 输入队列inq：由装满输入数据的缓冲区所链接成的队列，队首指针和队尾指针分别指向该输入队列的队首和队尾缓冲区
    • 输出队列outq：由装满输出数据的缓冲区所链接成的队列，队首指针和队尾指针分别指向该输出队列的队首和队尾缓冲区
    • 收容输入数据的工作缓冲区，提取数据输入的工作缓冲区，收容输出数据的工作缓冲区，提取输出数据的工作缓冲区
  • Getbuf过程和Putbuf过程：为了保证进程同步使用缓冲区和缓冲池队列，为每一队列设置一个互斥信号量MS，资源信号量RS
  • 缓冲区的工作方式：收容输入、提取输入、收容输出、提取输出
• 磁盘存储器的性能和调度
  • 磁盘的类型：固定头磁盘：移动头自拍
  • 磁盘访问时间：寻道时间、旋转延迟时间、传输时间
  • 磁盘调度算法
    • 先来先服务算法（FCFS）：根据进程访问磁盘的先后次序进行调度
    • 最短寻道时间优先（SSTF）：要求访问的磁道与当前磁头所在的磁道最近，以使每次寻道时间最短
    • 扫描SCAN算法：考虑欲访问磁道与当前磁道间的距离和磁头当前的移动方向
    • 循环扫描（CSCAN）算法：规定磁头单向移动
    • NStepSCAN算法
      • 避免有一个或几个进程对某一磁道有较高的访问频率，垄断了整个磁盘设备的磁臂粘着，N步SCAN算法将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列，而每处理一个队列时又是按SCAN算法，对一个队列处理完后，再处理其他队列，当在处理某子队列时，新请求放入其他队列，避免出现粘着现象
    • FSCAN算法
      • 将NStepSCAN磁盘请求队列分成两个子队列。一个是由当前所有请求磁盘I/O的进程形成的队列，由磁盘调度按SCAN算法进行处理。另一个是在扫描期间将新出现的所有请求磁盘I/O的进程放入等待处理的请求队列。所有的新请求都将推迟到下一次扫描时处理

15. 文件和文件系统

• 文件和文件系统
  • 文件数据组成
    • 数据项
      • 基本数据项/字段：描述一个对象的某种属性的字符集，最小逻辑数据单位，数据项名字和类型组成数据类型，数据称为"值"
      • 组合数据项/组项：由若干个基本数据项组成的
    • 记录：一组相关数据项的集合，表述一个对象在某方面的属性，关键字：唯一地标识一个记录的一个或几个数据项的集合
    • 文件：由创建者所定义的、具有文件名的一组相关元素的集合。最大的数据单位，一个对象集
  • 文件的属性：文件类型、文件长度(字节、字或块)、文件物理位置(文件所在的设备及所在设备中地址的指针)、建立/最后一次修改时间
  • 文件名和扩展名(文件名后面的若干个用于指示文件的类型的附加字符)
  • 文件类型
    • 按用途分类
      • 系统文件：由系统软件构成的文件
      • 用户文件：由用户的源代码、目标文件、可执行文件或数据等所构成的文件
      • 库文件：有标准子例程及常用的例程等所构成的文件
    • 按文件中的数据形式分类
      • 源文件：由源程序和数据构成文件
      • 目标文件：源程序经过编译程序编译过的目标代码所构成的文件.obj
      • 可执行文件：把编译后所产生的目标代码经过链接程序链接后所形成的文件.exe
    • 按存取控制属性分类：只执行文件、只读文件、读写文件
    • 按组织形式和处理方式分类
      • 普通文件：由ASCII码或二进制码组成的字符文件，用户的源程序文件、数据文件以及操作系统自身代码文件、使用程序等都
      • 目录文件：由文件目录组成的文件
      • 特殊文件：特指系统中的各类I/O设备
• 文件系统的层次结构
  • 文件管理系统的管理对象及其属性
    • 文件：不同类型的文件都是文件管理的直接对象
    • 目录：目录的目录项中含有文件名、对文件属性的说明，以及改文件所在的物理地址或指针
    • 磁盘（磁带）存储空间：文件和目录必须占用存储空间
  • 对对象操纵和管理的软件集合（核心）
    • I/O控制层/设备驱动程序层：文件系统最底层，由磁盘驱动程序等组成，可称为
    • 基本文件系统层：处理内存和磁盘间数据块的交换
    • 基本I/O管理程序：完成与磁盘I/O有关的事务
    • 逻辑文件系统：处理与记录与文件相关的操作
  • 文件系统的接口
    • 命令接口：用户与文件系统直接交互的接口，用户可以通过键盘中断键入命令取得文件系统的服务
    • 程序接口：用户程序与文件系统的接口，用户程序可通过系统调用取得文件系统的服务

15.1. linux文件系统

• 文件系统概览
  • FAT（File Allocation Table），FAT16、FAT32等，微软Dos/Windows使用的文件系统。使用一张表保存盘块的信息
  • NTFS（new Technology File System）WindowsNT环境的文件系统，NTFS对FAT进行了改进，取代了旧的文件系统
  • EXT2/3/4（数字表示第几代）EXT(Extended file system):扩展文件系统。linux文件系统
• EXT文件系统
  • Boot Sector：启动扇区，安装开机管理程序
  • Block Group：块组，存储数据的实际位置，Boot Sector包含多个Block Group，blockGroup包含多个Superblock
  • Superblock：记录整个文件系统相关信息的地方，Block和Inode的使用情况，时间信息，控制信息等
    • 文件系统描述
    • innode table：存放Innode的地方，每个文件（目录）都有一个Inode，是每个文件（目录）的索引节点
      • Inode 文件名不是存放在Inode节点上的，而是存放在目录的Inode节点，列出目录文件的时候无需加载文件的Inode，每个文件或者文件夹都有一个Inode，Inode可以理解为是文件或文件夹的“身份证”，Inode存储着文件索引节点编号、文件类型、文件权限、文件物理地址的关键信息。包括：索引节点编号，文件类型，文件权限，文件物理地址，文件长度。文件连接计数，文件存取时间，文件状态，访问计数，链接指针
    • Inode bitmap：Inode的位示图，记录已分配的Inode和未分配的Inode
    • data block:存放文件内容的地方，每个block都有唯一的编号，文件的block记录在文件的Inode上
    • block bitmap：功能与Innode bitmnap类似，记录Data block的使用情况

16. 文件的逻辑结构

• 文件的结构类型（影响对文件的检索速度）
  • 逻辑结构/文件组织：用户观察并操作的由一系列的逻辑结构记录组成的文件组织形式，文件的逻辑记录是能够被存取的基本单位
  • 物理结构/存储结构：用户不能看见的文件在外存上所形成的一种存储组织形式，与存储介质的存储性能和外存分配方式有关
• 文件的逻辑结构类型
  • 按文件是否有结构分类
    • 有结构文件/记录式文件(文本文件，文档，媒体文件)：由一个以上的相关记录构成的文件，各记录都用于描述实体集中的一个实体
      • 定长记录：各记录长度相同，各项数据项在记录中具有相同的位置、顺序和长度，文件的长度用记录数目表示。存储文件格式、文件描述等结构化数据项
      • 变长记录：各记录长度不同，各项数据项在记录中的长度不相同。存储文件具体内容
    • 无结构文件/流式文件（如源程序、可执行文件、库函数、二进制文件、链接库）
      • 由字符流构成的文件，文件长度以字节为单位，访问时利用读、写指针指出下一个访问的字符，一个记录仅有一个字节。文件内容以字节为单位
  • 按文件的组织形式分类
    • 顺序文件(Sequential File)：由一系列记录按某种顺序排列所形成的文件，可以是定长记录或者是变长记录。按顺序存放在存储介质中的文件
      • 串结构排列方式：记录按存入时间先后进行排序，检索时从头开始逐个记录查找
      • 顺序结构排列方式：记录按关键字来排序，利用算法提高检索效率
      • 对文件中的记录进行批量存取时，存取效率高，查找或修改单个记录性能差、 增加或删除记录困难
    • 索引文件(变长记录文件)(Index File)：为可变长记录文件建立一张索引表，为每个记录设置一个表项，加快检索速度
      • 建立一个以每个记录为表项的索引表，记录指向记录的指针（逻辑地址空间的首址）以及记录的长度L并按关键字建立索引并排序
      • 查找、插入和删除记录快，但增加了存储开销
    • 索引顺序文件(Index Sequential File)；为一组记录建立一个索引表项
      • 相比顺序文件，引入了文件索引表和溢出文件（记录新增加的、删除的和修改的记录）
      • 一级索引顺序文件：将文件中的所有记录分成若干组并建立索引表，每一项为每组中的第一个记录的关键字和指向记录的指针
      • 两级索引顺序文件：为索引文件再建立一张索引表
    • 直接文件：根据关键字直接获得指定记录的物理地址，由关键字到记录物理地址的转换称为键值转换。
    • 哈希(Hash)文件(直接文件的一种)
      • 用哈希函数将关键字转为相应记录的地址(由hash函数求得指向某一目录表相应表目的指针（内容指向记录所在的物理块))
• 记录寻址
  • 隐式寻址方式：读指针Rptr（指向下一个记录的首址）+定长记录长度L或者变长记录长度Li
  • 显式寻址方式：通过文件中记录的位置或关键字实现对定长记录的随机访问

17. 文件目录

• 文件目录
  • 概念：用于标识系统中的文件以及物理地址的数据结构，供检索时使用，文件控制块的集合，一个文件控制块就是一个文件目录项
  • 目录管理要求：实现按名存取、提高对目录的检索速度、文件共享、允许文件重名
  • 文件控制块（File Control Block FCB）：描述和控制文件的数据结构，文件管理程序利用文件控制块中的信息对文件操作
    • 基本信息类：文件名、文件物理位置、文件的逻辑结构、文件的物理结构
    • 存取控制信息类：文件主的存取权限、核准用户的存取权限、一般用户的存取权限
    • 使用信息类：建立时间、上一次修改时间，当前使用信息等
• 索引节点
  • 在UNIX系统中，文件描述信息单独形成索引节点，文件目录的目录项仅由文件名和指向该文件所对应的索引结点的指针构成
  • 磁盘索引结点：存放在磁盘上的索引结点，每个文件有唯一一个磁盘索引结点，包括
    • 文件主标识符：拥有该文件的个人或小组的标识符
    • 文件类型：正规文件、目录文件或特别文件
    • 文件存取权限：各类用户对该文件的存取权限
    • 文件的物理地址
    • 文件长度：以字节为单位的文件长度
    • 文件连接技术，本文件系统中所有指向该文件名的指针计数
    • 文件存取时间：本文件最近被进程存取的时间、最近被修改的时间及索引结点最近被修改的时间
  • 内存索引结点：当文件被打开时，要将磁盘索引结点拷贝到内存的索引结点中，便于搜索，增加了以下内容
    • 索引结点编号：标识内存索引结点
    • 状态：指示i结点是否上锁或被修改
    • 访问计数：每当有一进程要访问此i结点时，访问计数+1，访问完-1
    • 文件所属文件系统的逻辑设备号
    • 链接指针，设置有分别指向空闲链表和散列队列的指针
• 目录结构分类
  • 单级文件目录：只建立一张目录表，每个文件占一个目录项
    • 简单、按名存取，但查找速度慢、不允许重名、不便于实现文件共享，只适用于单用户环境
  • 两级文件目录
    • 建立一个每个用户目录文件都占有一个目录项的主文件目录MFD，目录项中包含用户名和指向该用户目录文件UFD的指针
    • 再为每个用户建立一个由该用户所有文件的文件控制块组成的用户文件目录UFD
    • 提高了检索目录速度、不同用户目录允许重名且可以共享文件，将多个用户隔开，但当多个用户合作去完成大任务时隔离成为缺点
  • 树形目录（windows linux）
    • 每个文件目录只能有一个根/主目录，每个文件和目录都只能有一个父目录，把数据文件称为树叶，其它的目录均作为树的节点/子目录
    • 路径名：从树的根开始，把全部目录文件名与数据文件依次用/连接起来，构成该数据文件唯一路径名
    • 当前目录：进程对各个文件的访问都相对于当前目录进行，从当前目录开始直到数据文件为止所构成的路径名称为相对路径名
    • 绝对路径名：从树根开始的路径名
    • 查询速度更快、层次结构更信息，更加有效进行文件的管理和保护
• 目录查询技术
  • 访问文件过程：首先利用用户提供的文件名对目录进行查询，找出文件控制块或对应的索引结点中记录的文件地址（盘块号），
    换算出文件在磁盘上的物理地址，再通过磁盘驱动程序将所需文件读入内存
  • 线性/顺序检索法：在单级目录中，按顺序从文件目录中找到与文件名匹配的目录项，在树形目录中，需对多级目录进行查找
  • 哈希Hash方法：将用户提供的文件名变换为文件目录的索引值，再利用该索引值到目录中去查找
    • hash冲突：不同文件名转换为相同hash值
      • 在利用hash法索引查找目录时，如果目录表中相应的目录项是空的，则表示系统中并无指定文件
      • 若目录项中的文件名与指定文件名相匹配，可从中找到该文件所在的物理地址
      • 若目录项中的文件名与指定文件名不匹配（冲突），则将hash值加上一个常数（与目录长度值互质）形成新索引值，重新找

18. 文件共享

• 基于索引节点：通过不同用户目录项指向同一个索引结点实现共享，节点增加链接计数count:表示链接到本索引结点上的用户目录项的数目
• 基于符号链接：创建一个LINK类型新文件F写到链接父目录中，F包含被链接文件的路径名(符号链)，共享时通过路径名找到共享文件读写
  • 允许一个文件或子目录有多个符号链接方式连接的父目录和一个主父目录，属主结构仍然是简单树，文件的删除、查找都更为方便
  • 不会发生文件主删除一共享文件后留下一悬空指针的情况每次访问共享文件时都要读盘，开销大；每增加一条链接就增加一个文件名，要为每个共享用户建立一条符号链，消耗存储空间

19. 文件保护

• 影响文件的安全性：人为因素、系统因素：系统异常、自然因素：随着时间的推移，放在磁盘上的数据会逐渐丢失
• 确保系统安全性措施
  • 通过存取控制机制：防止人为因素造成的文件不安全性
  • 采取系统容错技术：防止系统部分的故障造成文件的不安全性
  • 建立后备系统：防止由自然因素造成不安全性
• 访问权:一个进程对某对象执行操作的权力，可以用一个有序对（对象名、权集）表示
• 保护域(Protection Domain)：进程对一组对象访问权的集合，规定了进程能访问的对象和能执行的操作，进程只能在指定域内执行操作
• 进程和域间的静态联系：进程只与一个域有关，进程的运行全过程都受限于同一个域，会使赋予进程的访问权超过实际需要
• 进程和域间的动态联系：进程与多个域有关，进程根据实际需要规定在每个阶段所能访问的对象
• 访问矩阵：描述一个系统的访问控制的矩阵，矩阵中的行代表域，列代表对象，矩阵中的每一项由一组访问权组成的。
  • 域切换权：当进程具有切换权时可以将进程从一个保护域切换到另一个保护域；
  • 拷贝权：某个域i对对象j具有拷贝权*，则可以将对对象j的访问权拷贝到其他域中，但拷贝权本身不能复制（同一列）
  • 所有权：某个域i对对象j具有所有权O，则可以给其他域增减或删除对对象j的访问权（同一列）
  • 控制权：某个域i对对象j具有控制权Control，则可以给增减或删除本域中对其他对象的访问权（同一行）

• 访问矩阵的实现
  • 访问控制表(ACL Access Control List)：将访问矩阵按列(对象)划分，为每一列建立一张由一有序对（域、全集）组成
  • 访问权限表(Capabilities)：将访问矩阵按行(域)划分，为每一行建立一张由一个域对每一个对象可以执行的一组操作组成
• 文件保护的实现
  • 当一个进程第一次试图去访问一个对象时先查询访问控制表是否具有对对象的访问权，无权访问则由系统拒绝进程的访问，并构成一例外（异常）事件，有权访问便允许进程对该对象进行访问，并为该进程建立一访问权限，将之连接到该进程。之后便可直接利用这一返回的权限去访问该对象，快速验证访问合法性，当进程不再需要对该对象进行访问时，便可撤销该访问权限

20. 外存的组织方式(辅存的存储空间分配)

• 外存组织方式
  • 连续组织方式：给文件分配一片连续的磁盘空间(顺序式的文件结构)
    • 文件目录项的文件物理地址字段记录该文件第一个记录所在的盘块号和以盘块为单位的文件长度
    • 优点：保证了逻辑文件中的记录顺序与占用盘块的顺序一致性、顺序访问容易、访问速度快
    • 缺点：
      • 要求为一个文件分配连续的存储空间，产生许多碎片(可以使用紧凑解决)，严重降低外存空间利用率
      • 必须事先知道文件的长度，估算错误造成存储空间浪费
      • 不能灵活删除和插入记录、对于那些动态增长的文件，由于事先很难知道文件的最终大小，很难分配空间
  • 链接组织方式：给文件分配非连续的磁盘空间，通过链接指针将一个文件的所有盘块链接在一起(链接式文件结构)需要额外的存储空间存储文件的盘块链接顺序
    • 优点：消除磁盘的外部碎片，提高外存的利用率
      • 对插入、删除和修改记录都非常容易
      • 能适应文件的动态增长，无需事先知道文件的大小
    • 隐式链接
      • 文件目录的每个目录项都含有指向链接文件的第一个盘块和最后一个盘块的指针，每个盘块都含有一个指向下一个盘块的指针
      • 只适合顺序访问，随机访问低效，只通过链接指针将一大批离散的盘块链接起来，可靠性差.任何一个链接出问题都影响整个文件
      • 改进：链接文件、分配盘块以簇(几个盘块)为单位，缩小查找指定块的时间，减少指针所占用的存储空间，但增加了内部碎片
    • 显式链接
      • 把用于链接文件各物理块的指针显式地存放在内存的一张链表（文件分配表FAT）中，表的序号是物理块号，从0-n-1，，每一项存放链接指针（下一个盘块号）所有文件的第一个盘块号作为文件地址被填入相应文件的FCB的物理地址字段中.
      • 检索过程在内存中进行，速度变快，减少访问磁盘的次数.FAT不支持高效存储（FAT记录项多）检索是FAT表占用较大的存储空间（需要将整个FAT加载到内存）
  • 索引组织方式：形成索引式文件(ext文件)
    • 引入原因：连续组织方式不支持高效的直接存取、FAT需要占用较大的内存空间
    • 单级索引组织方式
      • 新建文件时，将分配给文件的所有盘块号记录在一个索引块（表）中。目录项记录指向该表索引块的指针，读取某个文件时，将文件索引读取进内存即可
      • 优缺点：支持直接访问盘块，适用于大文件；对小文件采用索引分配方式时，索引块的利用率极低
    • 多级索引组织方式
      • 如果文件较大时，可以为索引块再建立一个索引，作为第一级索引的索引块，一次类推
      • 优缺点：加快对大型文件的查找速度；访问盘块所需启动磁盘的次数与索引级数成正比，对于小文件也是
    • 增量式索引组织方式
      • 对于小文件直接寻址：从文件控制块FCB（索引结点）中直接读出每一个盘块地址
      • 对于中文件采用单级索引、对于大文件采用多级索引

21. 文件存储空间的管理

• 磁盘分配表(Disk Allocation Table)：记录可供分配的存储空间的情况
• 文件存储空间的管理方法(数据结构)
  • 空闲表法 (连续分配方式\分配速度快，可减少访问磁盘的I/O频率，分配和回收与内存的动态分配类似)
    • 系统为外存上所有的空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息，再按其起始盘块号递增的次序排列
  • 空闲链表法-将所有的空闲盘块拉成一条空闲链
    • 空闲盘块链
      • 将磁盘上的所有空闲以盘块为单位拉成一条链，其中每个盘块都有指向后继盘块的指针。当用户因创建文件而请求分配存储空间时，系统从链首开始，一次摘下适当数目的空闲盘块分配给用户，当用户因删除文件而释放存储空间时，系统将回收的盘块依次挂在空闲盘块链的末尾
      • 分配和回收过程简单；文件分配盘块时可能需要重复操作多次，效率低，以盘块为单位，相应的空闲盘块链长
    • 空闲盘区链
      • 将磁盘上所有的空闲盘区（每个盘区可包含若干个盘块）拉成一条链，在每个盘区上含有用于指示下一个空闲盘区的指针和本盘区大小的信息，分配方法与内存的动态分配类似
      • 分配和回收过程复杂，但效率高。每次为文件分配多个连续块，且空闲盘区链较短
  • 位视图法
    • 由所有盘块对应的位（0/1表示盘块是否分配）组成的集合称为位示图，有mXn个位数构成，并使mXn等于磁盘的总块数
    • 盘块分配：找出空闲的二进制位并转成盘块号b=n(i-1)+j（i行j列，n每行位数）同时令map(i,j)=1
    • 盘块回收：将盘块号转成行号j=(b-1)DIV n+1 和列号i=(b-1)MOD n+1同时令map(i,j)=0
    • 优点：从位示图中容易查找一个或一组相邻接的空闲盘块快，位视图占用空闲小
  • 成组链接法（UNIX）大型文件系统
    • 空闲盘块的组织
      • 空闲盘块号栈：存放当前可用一组空闲盘块号和空闲盘块号数N（栈顶指针），还设置了锁
      • 文件区的所有空闲盘块被分成若干组，每n个为一组
      • 将每一组含有的盘块总数N和该组所有的盘块号计入前一组的第一个盘块的0到n-1中
      • 将第一租的盘块总数和所有的盘块号计入空闲盘块号栈中，作为当前可供分配的空闲盘块号
      • 最末一组只有n-1个盘块，其盘块号分别计入前一组的1到n-1中，在0中存放“0”，作为空闲盘块链结束的标志
    • 空闲盘块的分配与回收
      • 检查盘块号栈是否上锁，未上锁则从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，将栈顶指针下移一格
      • 若盘块号已经是栈底（当前栈中最后一个可分配的盘块号），该盘块号所对应的盘块中记有下一组可用的盘块号，调用磁盘的读过程将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去（其中有用的数据已读入栈中），然后再分配一相应的缓冲区，最后把栈中的空闲盘块数减1并返回
      • 系统回收盘块时，调用盘块回收过程进行回收，将回收盘块的盘块号计入空闲盘块号栈的顶部，并执行空闲盘块数加1的操作。当栈中空闲盘块数目达到100时（栈满），将现有栈中的100盘块号计入新回收的盘块中，再将盘块号作为新栈底

22. 提高磁盘I/O速度的途径

• 提高对文件的访问速度方法
  • 改进文件的目录结构以及检索目录的方法减少对目录的查找时间
  • 选取好的文件存储结构，提高对文件的访问速度
  • 提高磁盘的I/O速度，将文件中的数据快速地从磁盘送入到内存中，或者相反
• 磁盘高速缓存（Disk Cache）：在内存中为磁盘块设置一个缓冲区，在缓冲区中保存了一些盘块的副本
  • 当出现一个访问磁盘的请求时，由核心先去查看磁盘高速缓冲器，看所请求的盘块内容是否已在盘高速缓存中，如果在，则从磁盘高速缓存中去获取，省去了启动磁盘操作，不在则需要启动磁盘，将所需的盘块读入，并把所需盘块内容送给磁盘高速缓存，以便以后又需要访问该盘块的数据时，便可直接从高速缓存中提取
  • 设计磁盘高速缓存时需要考虑的问题（了解）
    • 如何提高磁盘高速缓存中的数据传送给请求进程(数据交付方式：将高速缓存中的数据传送给请求者进程)
      • 数据交付：直接将高速缓存中的数据传送到请求者进程的内存工作区中
      • 指针交付：直向高速缓存中某区域的指针交付给请求进程，节省了数据从磁盘高速缓存到进程的内存工作区的时间（快）
    • 采用什么样的置换策略（置换算法）
      • 最近最久未使用
      • 访问磁盘高速缓存频率
      • 可预见性：哪些数据可能很快就被访问
      • 数据的一致性
    • 已修改的盘块数据在何时被写回磁盘（周期性地写回磁盘）
      • 根据LRU算法，经常被访问的盘块数据可能会一直保留在高速缓存中，不会被写回磁盘。
      • UNIX设置了修改程序，周期性地调用一个系统调用SYNC，强制性地将所有在高速缓存中已修改的盘块数写回磁盘
• 提前读：顺序访问方式对文件进行访问，读当前块的同时将下一个盘块读入缓冲区
• 延迟写：先将缓存区的数据挂到空闲缓存区队列的末尾，随着空闲缓冲区的使用，缓冲区也缓缓往前移动，直至移到空闲缓冲队列之首，当再有进程申请到该缓冲区时，才将该缓冲区中的数据写入磁盘，而把该缓冲区作为空闲缓冲区分配出去。
• 优化物理块分布：对于盘块位置的优化，应在为文件分配盘块时进行
• 虚拟盘：用内存空间模仿真磁盘，但易丢失数据。通常只放置临时文件，内容完全由用户控制，而磁盘高速缓存中的内容则是由os控制的
• 廉价磁盘冗余阵列（RAID）
  • 利用一台磁盘阵列控制器统一管理和控制一组磁盘驱动器，组成一个大型磁盘系统。
  • 并行交叉存取：系统将每个盘块中的数据分为若干个子盘块数据，再把每一个子盘块的数据分别存储到各个不同磁盘中的相同位置上，当要将一个盘块的数据传送到内存时，采用并向传输的方式，将各个盘块中的子盘块数据同时向内存中传输

23. 提高磁盘可靠性的技术

• 磁盘容错技术通过增加冗余的磁盘驱动器、磁盘控制器等的方法提高系统可靠性的一种技术
• 磁盘容错技术的分级
  • 第一级容错技术SFT-1：防止因磁盘表面缺陷造成的数据丢失
    • 双份目录和双份文件分配表FAT：在不同磁盘上或在磁盘的不同区域中分别建立主目录表、主FAT、备份目录、备份FAT
    • 热修复重定向：将小部分磁盘容量作为热修复重定向区，存放磁盘有缺陷时的待写数据，并对写入该区的所有数据进行登记
    • 写后读校验：将数据写入磁盘再读出与内存缓冲区中的数据进行校验，一致则表示成功，不一致则盘块数据写入到热修复重定向区
  • 第二级容错技术SFT-ii：防止磁盘驱动器和磁盘控制器故障导致系统不能正常工作
    • 磁盘镜像：同一磁盘控制器下增设一个完全相同的磁盘驱动器，写数据时主磁盘和备份磁盘都需要写数据
    • 磁盘双工：将两台磁盘驱动器分别接到两个磁盘控制器上，使这两台磁盘镜像成对，写数据时主磁盘和备份磁盘都需要写数据
  • 基于集群技术的容错功能
    • 双机热备份模式
      • 系统中备有处理能力相同的主服务器，备份服务器，平时主服务器运行，备份服务器则时刻监视着主服务器的运行，一旦主服务器出现故障，备份服务器便成为系统的主服务器，修复后的服务器再作为备份服务器，分别给服务器安装一块网卡，通过一条镜像服务链路MSL将两台服务器连接起来
    • 双机互为备份模式
      • 两台服务器均为在线服务器，各自完成自己任务，每台服务器内部配置两台硬盘，一个用于装载系统程序和应用程序，另一个用于接收由另一台服务器发来的备份数据，作为该服务器的镜像盘
    • 公用磁盘模式：将多台计算机连接到一条公共的磁盘系统上，公共磁盘被划分为若干个卷，每台计算机使用一个卷
• 后备系统：把不需要但有用的数据，存放在后备系统中保存起来，防止系统发生故障或病毒感染
  • 磁带机:只适合存放顺序文件，存取速度慢，容量大，价格便宜，
  • 硬盘:移动磁盘，速度高，脱机保存方便，保存时间长，但位价高，体积小；固定硬盘驱动器：大中型系统
  • 光盘驱动器：可读写光盘驱动器/刻录机

24. 数据一致性控制

• 数据一致性:多个文件中的同一数据，在任何情况下都必须能保障相同
• 事务：用于访问和修改各种数据项的一个程序单位
  • 托付/提交操作：对分布在不同位置的同一数据进行读写操作全部完成时确认事务的变化
  • 夭折/回滚/取消操作：操作中有一个操作失败，必须执行回滚操作
  • 事务原子性：一个事务在对一批数据执行修改操作时，要么全部成功，要么全部失败
  • 事务一致性：事务在完成时，必须使所有的数据保持一致的状态
  • 事务隔离性：对一个事务对数据所作的修改，必须与任何其他与之并发事务相隔离
  • 事务持久性：事务完成之后，他对系统的影响是永久性的
  • 事务记录表：记录事务运行中的重要事务操作，其中运行记录（Log）包含字段：事务名\数据项名\旧值\新值
• 恢复算法：防止系统故障造成数据丢失
  • undo(Ti)过程:把所有被事务修改过的数据恢复为修改前的值，在Log中只有开始没有提交操作的数据
  • redo(Ti)过程:把所有被事务修改过的数据设置为新值，在Log中既有开始又有提交操作的数据
• 新的恢复算法
  • 检查点：对事务记录表中的事务记录的清理工作经常化，将内存中的当前事务记录表中的所有记录输出到稳定存储器中，内存中所有已修改数据输出到稳定存储器中，然后将事务记录表中的检查点输出到稳定存储器中，每当出现一个检查点记录时，执行恢复算法
  • 首先查找事务记录表，确定在最近检查点之前执行的最后事务Ti,返回去搜索事务记录表，找到第一个检查记录，恢复历程便从该检查点开始返回搜索各个事务的记录，并利用redo和undo过程对它们进行处理
• 并发控制：用于实现事务顺序性的技术
  • 事务顺序性：事务的原子性决定了只有在一个事务执行完后，才允许另一事务执行，事务对各数据项修改是互斥的
  • 互斥锁仅允许一个事务对相应对象执行读或写操作
  • 共享锁允许多个事务对相应的对象执行读操作，但不允许其中任何一个事务对对象执行写操作
• 重复数据的一致性问题
  • 重复文件的一致性
    • UNIX的文件目录中的每个目录项中含有一个ASCII码的文件名和一个指向索引结点的索引结点号
      当有重复文件时，一个目录项可由一个文件名和若干个索引结点号组成，每个索引结点号都是指向各自的索引结点
    • 当有重复文件时，如果一个文件的拷贝被修改，则其他文件也要被修改，修改方法
      • 当一个文件被修改后查找文件目录得到其他几个拷贝的索引结点号并找到各拷贝的物理位置，然后对这些拷贝做同样的修改
      • 为新修改的文件建立几个拷贝，并用新拷贝去取代原来的文件拷贝
  • 链接数一致性检查
    • 在UNIX类型的文件目录中，共享文件的索引结点号出现次数与其索引节点中的链接计数count应该一致
    • 配置一张计数器表，为每个文件建立一个表项，其中含有该索引结点号的计数值，记录目录中遇到该文件索引结点号的数量与该文件中的索引结点中的链接技术count值比较判断是否出错。若索引结点中的链接技术count大于计数器表中相应的索引结点号的计数值，表明没用户共享此文件，count仍不为0，此文件仍留在磁盘上，浪费存储空间，只需重新赋正确值即可。若索引结点中的链接技术count小于计数器表中相应的索引结点号的计数值，导致某些用户不能共享到文件，只需重新赋正确值即可