操作系统

操作系统思维导图，内容有进程与线程、进程管理、内存管理、文件管理（外存管理）、设备管理，参考王道整理而成。

操作系统

• 进程与线程
  • 进程的基本概念：计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。它可以申请和拥有系统资源，是一个动态的概念，是一个活动的实体。它不只是程序的代码，还包括当前的活动，通过程序计数器的值和处理寄存器的内容来表示
  • 进程结构：由程序、数据和进程控制块（PCB）三部分组成
  • 进程状态
  • 进程控制功能：用于创建一个新进程，终止一个已完成的进程，或者去终止一个因出现某事件而使其无法运行下去的进程，还可负责进程运行中的状态转换
    • 引起创建进程的事件
      • 用户登录：在分时系统中，用户在终端键入登录命令后，如果是合法用户，系统将为该终端建立一个进程，并把它插入到就绪队列中
      • 作业调度：在批处理系统中，当作业调度程序按照一定的算法调度到某作业时，便将该作业装入到内存，为它分配必要的资源，并立即为它创建进程，再插入到就绪队列中
      • 提供服务：运行中的用户程序提出某种请求后，系统将专门创建一个进程来提供用户所需要的服务
      • 应用请求：在上述三种情况中，都是由系统内核为它创建一个新进程，而这一类事件则是基于应用进程的需求，由它创建一个新的进程，以便使新进程以并发的运行方式完成特定任务
    • 创建进程过程： 申请空白PCB、为新进程分配资源、 初始化进程控制块、将新进程插入就绪队列
    • 撤销进程过程
      • 从PCB集合中检索出被撤销进程的PCB
      • 若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。
      • 将被终止的进程所拥有的全部资源，或者归还给其父进程，或者归还给系统
      • 将被终止进程（它的PCB）从所在队列（或链表）中移出，等待其它程序来搜集信息
    • 阻塞进程过程：进程便通过调用阻塞原语block()把自己阻塞、停止执行进程、把进程控制块中的现行状态由执行改为阻塞、将PCB插入阻塞队列
    • 唤醒进程过程：把被阻塞的进程从等待该事件的阻塞队列中移出、将其PCB中的现行状态由阻塞改为就绪、将该PCB插入到就绪队列中
    • 进程切换过程：保存现场、更新PCB信息、把进程的PCB移入相应队列、选择执行另一个进程并更新其PCB、更新内存管理的数据结构、恢复现场
  • 进程通信功能：进程间的信息交换
    • 共享存储：相互通讯的进程有共享存储区.进程间可以通过直接读写共享存储区的变量来交互数据
    • 消息传递：通过操作系统的相应系统调用进行消息传递通讯
      • 直接通信：进程在发送和接收消息时直接指明接收者或发送者进程ID
      • 间接通信：以信箱为媒介进行传递，可以广播
    • 管道通信：一种信息流缓冲机构， UNIX系统中管道基于文件系统，在内核中通过文件描述符表示
  • 线程
    • 基本概念：操作系统能够进行运算调度的最小单位。它被包含在进程之中，是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流，一个进程中可以并发多个线程，每条线程并行执行不同的任务
    • 分类
      • 内核级线程：依赖于内核，由操作系统内核完成创建和撤销工作的线程
      • 用户级线程：不依赖操作系统核心，由应用进程利用线程库提供功能函数来控制的线程
    • 多线程模型
      • 多对一模型：将多个用户级线程映射到一个内核级线程上
      • 一对一模型：将内核级线程与用户级线程一一对应
      • 多对多模型：将多个用户级线程映射到多个内核级线程
• 进程管理
  • 进程-资源管理表示方法
    • 进程-资源图：由若干代表进程与资源的图形、表示进程与资源间关系的箭头构成，若箭头由资源指向进程则表示资源分配完成，若箭头由进程指向资源则表示进程正在申请该资源（即申请一直未得到响应，属于死锁状态）
  • 处理器调度
    • 按照功能分类
      • 高级调度（作业调度）：用于确定把后备队列上的哪些作业调入内存,并为之建立进程,分配其所需的资源,然后将它挂在就绪队列上
      • 中级调度（中程调度/交换调度）：把进程从内存移到外存，当内存有足够空间时，再将合适的进程换入内存，等待进程调度
      • 低级调度（进程调度）：决定就绪队列中的哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作
        • 记录系统中所有进程的有关情况以及状态特征
        • 选择获得处理器的进程
        • 处理器分配
    • 按照算法分类
      • 可同时调度作业与进程
        • 先来先服务(FCFS)：按照作业提交或进程变为就绪状态的先后次序，分派CPU
        • 短作业优先调度算法：把处理器分配给最快完成的作业或进程
        • 优先级调度算法：系统从后备作业队列中选择若干个优先级最高的，且系统能满足资源要求的作业装入内存运行，或将把处理机分配给就绪进程队列中优先级最高的进程
          • 抢占式优先级调度算法：进程调度程序把处理机分配给当时优先级最高的就绪进程，使之执行。一旦出现了另一个优先级更高的就绪进程时，进程调度程序就停止正在执行的进程，将处理机分配给新出现的优先级最高的就绪进程
          • 非抢占式优先级算法：在这种调度方式下，系统一旦把处理机分配给就绪队列中优先级最高的进程后，该进程就能一直执行下去，直至完成；或因等待某事件的发生使该进程不得不放弃处理机时，系统才能将处理机分配给另一个优先级高的就绪进程
      • 只能调度进程
        • 时间片轮转调度算法：让每个进程在就绪队列中的等待时间与享受服务的时间成正比例，分配的执行时间称为时间片
        • 多级队列调度算法：根据性质类型将就绪队列分为若干个独立的队列，每个队列采用一种调度算法
        • 多级反馈队列调度算法：设置多个就绪队列并赋予不同的优先级和时间片，第一个队列优先级最高，时间片最小。新创建的进程挂到第一优先级的队列后，然后按先来先服务原则排队等待调度。当轮到其执行时，如果能在时间片内完成则撤离系统，否则被挂入第二级队列之后。仅当第一级队列空闲时，调度程序才调度第二级队列的进程运行。新进程可抢占低级进程的处理机
      • 只能调度作业
        • 高响应比优先调度算法：把CPU分配给就绪队列中响应比最高的进程，既考虑作业的执行时间也考虑作业的等待时间，综合了先来先服务和最短作业优先两种算法的特点。响应比=（等待时间+估计运行时间）/估计运行时间
  • 同步与互斥
    • 进程间制约关系
      • 资源共享关系：多进程共享资源，由系统统一分配，每次只允许一个进程使用一段时间该资源，等该进程使用完毕后再将该资源分配给其它进程，这种使用原则称为互斥使用，这类资源称为临界资源
      • 相互合作关系：例如一个程序的输入、计算、打印三个程序段作为三个进程并发执行，由于这三个进程间存在着相互合作的关系，即先输入再计算、最后再打印的关系，所以这三个进程在并发执行时推进序列受到限制，要保证其合作关系正确，进程间这种关系称为同步关系
    • 同步/互斥实现
      • 临界区法
        • 临界区访问原则：空闲让进、忙则等待、有限等待、让权等待
        • 临界区访问操作：进入区、临界区、退出区（、剩余区）
      • 信号量法
        • 基本概念：一个确定的二元组（s，q），其中s是一个具有非负初值的整型变量，表示系统中某类资源的数目，q是一个初始状态为空的队列
        • 基本操作
          • P（s）操作：执行s=s-1，若s≥0则该进程继续运行，否则阻塞该进程
          • V（s）操作：执行s=s+1，若s＞0则该进程继续执行，否则从该信号量等待队列中移出第一个进程，使其变为就绪状态并插入就绪队列，然后再返回原进程继续执行
      • 管程法
        • 基本概念：由局部于自己的若干公共变量（如临界区、P/V操作）及其说明和所有访问这些公共变量的过程所组成的软件模块，一切来访者串行通过管程访问共享资源
        • 基本操作
          • wait：将调用在此函数的进程阻塞在与该条件变量相关的队列中，并允许其他进程进入管程
          • signal：选择唤醒在该条件变量上阻塞的进程（无阻塞进程则什么都不做）
  • 死锁
    • 基本概念：两个或两个以上的进程在执行过程中，若所有进程都拥有若干数量的某一资源，而所有进程都未能满足对该资源的最大需求进而未能执行的情况，称为死锁
    • 产生的必要条件
      • 互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放
        • 无法预防
      • 请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放
        • 预防方法：预先静态分配法，资源未满足分配量前不投入运行
      • 不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放
        • 预防方法：已经占有资源的进程提出的新请求无法满足时，释放已占有资源
      • 环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源
        • 预防方法：有序资源分配法：提出请求资源Ri后，以后的请求只能请求排在其后的资源
    • 解决方案
      • 死锁避免
        • 基础概念
          • 安全状态：系统能按某种顺序来为每个进程分配其所需资源，直到最大需求，使每个进程都可顺序完成
          • 不安全状态：系统不存在这样一个安全序列，则称系统处于不安全状态
        • 避免方法：银行家算法
          • 当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配
      • 死锁检测
        • 死锁定理：当且仅当资源分配图不可简化会发生死锁
        • 死锁检测算法：获得某时刻系统中各类可利用资源的数目向量，对于一组进程，找出资源需求小于可用数目的进程，并满足其需求。运行结束后释放资源，将此类进程加入到可运行结束的进程序列中，对剩下的进程再进行上述考察，若一组进程中存在不属于该序列的进程则会发生死锁
      • 死锁解除
        • 剥夺资源
        • 撤销进程
        • 进程回退（回退时自愿释放资源而非被掠夺）
    • 解决方案并发性
      • 死锁检测＞银行家算法＞资源预分配
      • 原因：死锁检测允许死锁出现，即允许进程最大限度地申请并分配资源，直至出现死锁，再由系统解决；银行家算法允许进程自由申请分配，并在安全状态下分配资源；资源预分配要求进程在执行前申请所需资源，这样会使许多进程因申请不到资源而无法开始，得到资源的进程也并不是同时需要所占的全部资源，因此导致资源的浪费
• 内存管理
  • 功能
    • 内存分配与回收
      • 连续分配管理方式
        • 单一连续分配：将内存分为两个连续区域，一个固定地分配给操作系统，另一个给用户作业使用
        • 固定分区分配：将内存空间划分为若干个固定大小的分区，每个分区中可装入一道程序
        • 动态分区分配：作业进入主存时，根据其大小动态地建立分区
          • 算法
            • 首次适应(First Fit)算法：空闲分区以地址递增的次序链接
            • 最佳适应(Best Fit)算法：空闲分区按容量递增形成分区链，找到第一个能满足要求的空闲分区
            • 最坏适应(Worst Fit)算法：又称最大适应(Largest Fit)算法，空闲分区以容量递减的次序链接。找到第一个能满足要求的空闲分区
            • 邻近适应(Next Fit)算法：又称循环首次适应算法，由首次适应算法演变而成。不同之处是分配内存时从上次查找结束的位置开始继续查找
          • 分区回收：回收区应与相邻的空闲分区合并为一个新分区，若相邻分区非空闲则单独建立表项
          • 分区的动态管理（实现非连续碎片空间的连续利用）
            • 拼接技术：把存储器中所有已分配分区移动到主存的一端形成一个大的空闲区
            • 动态重定位分区分配技术：动态分区分配技术+拼接技术
      • 非连续分配管理方式
        • 基本分页存储管理方式
          • 基本概念：将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从0开始，如第0页、第1页等。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)，也同样为它们加以编号，如0#块、1#块等等。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中
          • 页表
            • 基本概念：内存中实现从页号到物理块号的地址映射的映射表
            • 两级/多级页表：将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入
              • 逻辑地址结构（以二级为例）：页目录号+页表索引号+页内偏移量，其中页目录号+页表索引号部分为虚页号，若虚页号有n位二进制数，则2^（n）为虚拟空间大小即页表大小
              • 多级页表级数计算：虚页号位数/每页可容纳的页项数的指数，之后对运算结果取上限整数（如结果为8.5，则取9）
            • 地址变换：当进程要访问某个逻辑地址中的数据时，分页地址变换机构会自动地将有效地址(相对地址)分为页号页内地址两部分，再以页号为索引去检索页表。查找操作由硬件执行。在执行检索之前，先将页号与页表长度进行比较，如果页号大于或等于页表长度，则表示本次所访问的地址已超越进程的地址空间。于是，这一错误将被系统发现并产生一地址越界中断。若未出现越界错误，则将页表始址与页号和页表项长度的乘积相加，便得到该表项在页表中的位置，于是可从中得到该页的物理块号，将之装入物理地址寄存器中。与此同时，再将有效地址寄存器中的页内地址送入物理地址寄存器的块内地址字段中
          • 快表（TLB）
            • 基本概念：为了提高地址变换速度，在地址变换机构中增设一个具有并行查找功能的高速缓冲存储器，将部分页表项放在这个高速缓冲存储器中
            • 地址变换：在CPU给出有效地址后，由地址变换机构自动地将页号P送入高速缓冲寄存器，并将此页号与高速缓存中的所有页号进行比较，若其中有与此相匹配的页号，便表示所要访问的页表项在快表中。于是，可直接从快表中读出该页所对应的物理块号，并送到物理地址寄存器中。如在块表中未找到对应的页表项，则还须再访问内存中的页表，找到后，把从页表项中读出的物理块号送地址寄存器；同时，再将此页表项存入快表的一个寄存器单元中，亦即，重新修改快表。但如果联想寄存器已满，则OS必须找到一个老的且已被认为不再需要的页表项，将它换出
          • 共享方式：使共享用户地址空间中的页指向相同的物理块
        • 基本分段存储管理方式
          • 基本概念：作业的地址空间被划分为可不等长的若干个段，每个段定义了一组逻辑信息，用一个段号来代替段名，每个段都从0开始编址，并采用一段连续的地址空间
          • 段表
            • 基本概念：内存中实现从页号到物理块号的地址映射的映射表
            • 地址变换：为了实现从进程的逻辑地址到物理地址的变换功能，在系统中设置了段表寄存器，用于存放段表始址和段表长度TL。在进行地址变换时，系统将逻辑地址中的段号与段表长度TL进行比较。若S>TL，表示段号太大，是访问越界，于是产生越界中断信号；若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存的起始地址，然后，再检查段内地址d是否超过该段的段长SL。若超过，即d>SL，同样发出越界中断信号；若未越界，则将该段的基址d与段内地址相加，即可得到要访问的内存物理地址
          • 共享方式：使多个作业中的段表中相应表项都指向被共享段的同一个物理副本
        • 基本段页式存储管理方式
          • 基本概念：先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名
          • 地址变换：为了便于实现地址变换，须配置一个段表寄存器，其中存放段表始址和段表长TL。进行地址变换时，首先利用段号S，将它与段表长TL进行比较。若S<TL，表示未越界，于是利用段表始址和段号来求出该段所对应的段表项在段表中的位置，从中得到该段的页表始址，并利用逻辑地址中的段内页号P来获得对应页的页表项位置，从中读出该页所在的物理块号b，再利用块号b和页内地址来构成物理地址
        • 保护措施
          • 地址越界保护、访问控制保护（访问时比较控制字段）
    • 地址变换
      • 名地址→逻辑地址
      • 逻辑地址→物理地址：硬件完成，物理地址=基址寄存器内容+逻辑地址
    • 扩充内存
      • 覆盖技术：把一个大的程序划分为一系列覆盖，程序执行时不要求同时装入内存的覆盖组成一组，称为覆盖段，将覆盖段分配到同一个存储区域，称为覆盖区
      • 交换技术：把暂时不用的某个程序及数据部分从内存移到外存，或把指定的程序或数据从外存读到相应的内存中，并将控制权转给它，让其在系统上运行的一种内存扩充技术
    • 存储保护
      • 有界限寄存器法
        • 上、下界寄存器法：采用上、下界寄存器分别存放作业的结束地址与开始地址，运行时将每一个访问内存的地址与两个寄存器的内容比较，超出范围则保护性中断
        • 基址和限长寄存器法：运行时将每一个访问内存的相对地址与重定位寄存器中的值相加，形成作业的物理地址；限长寄存器与相对地址进行比较，若超出范围则保护性中断
      • 存储保护键法：为主存的每一块配一个键，称为存储键。为了打开这个锁,必须有钥匙，称为访问键。访问键赋予每道程序，并保存在该道程序的状态寄存器中。当数据要写入主存的某一块时，访问键要与存储键相比较。若两键相符，则允许访问该页，否则拒绝访问
  • 虚拟内存管理
    • 基本种类
      • 请求分页式存储管理方式=请求分页+请求调页+页面置换
      • 请求分段式存储管理方式
    • 页面置换算法
      • 最佳置换算法（OPT）：每次都淘汰以后不再使用的或以后最迟被使用的页面，具有最低的缺页率，但仅存于理论中事实上无法实现
      • 先进先出算法（FIFO）
      • 最近最少使用算法（LRU）
      • 时钟置换算法（CLOCK)
        • 原版：LRU与FIFO的折中算法，初始访问位全为0，初次占满内存后访问位全为1，接下来若访问的值与待调入值等则访问位置1不处理，不等的话若访问位为0则替换之后置1，为1则不处理置0
        • 改进型：增加修改位
      • 最不常用置换算法（LFU）
      • 页面缓冲算法（PBA）：使用缓冲区减少系统的I/O消耗
    • 异常现象
      • 抖动
        • 定义：如果分配给进程的存储块数量小于进程所需要的最小值，进程的运行将很频繁地产生缺页中断，这种频率非常高的页面置换现象称为抖动，发生于先进先出（FIFO）页面置换算法
        • 解决方案
          • 工作集理论：基于局部性原理，是最近n次内存访问的页面的集合（即预测程序在某段时间内要访问哪些页面并提前调入内存）
      • Belady现象：采用页面置换FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，但缺页率反而提高的异常现象
      • 缺页
        • 定义：要访问的页不在主存，需要操作系统将其调入主存后再进行访问
        • 解决方案
          • 页面分配策略
            • 固定分配局部置换：为每个进程分配一定数目的物理块，当某进程有页面需要换入到内存中时，只能从该进程目前己在内存中的页面中选择一页淘汰
            • 可变分配全局置换：操作系统维护一个空闲物理块队列，每次有进程缺页时都从其中取下一块进行分配，若无空闲块则调出内存中的任一页
            • 可变分配局部置换：为每个进程分配一定量的物理块后，若发生缺页且无空闲块，则只能调出该进程在内存的某一页
          • 页面调入策略
            • 请求调页：一个页面只有被用到时才被调入内存
            • 预调页策略
          • 调页位置策略
            • 系统拥有足够的对换区空间：全部从对换区调入所需页面，以提高调页速度
            • 系统对换区空间不足：不会被修改的文件直接从文件区调入，可能被修改的部分使用对换区
            • UNOX方式：已运行过的使用对换区，未运行过的使用文件区。由于该方式允许页面共享，有可能所需页面已被其他进程调入内存，则无需使用上述两区
  • 管理实例：应用程序的编译、链接、装入
    • 经过编译程序将源代码编译为若干目标模块（源程序，名地址）
    • 通过链接程序将编译好的目标模块以及所需库函数链接在一起（目标程序，逻辑地址）
      • 静态链接：程序运行前，先把各个目标模块及所需库链接为一个完整的可执行程序，以后不再拆开
      • 装入时动态链接：将应用程序编译后所得到的一组目标模块装入内存时边装入边链接
      • 运行时动态链接：直到程序运行过程中需要一些模块时，才对这些模块进行链接
    • 通过装入程序将这些模块装入内存并执行（可执行程序，物理地址）
      • 绝对装入：在编译时就知道物理地址，编译程序含有物理地址的目标代码
      • 可重定位装入：将装入模块装入到内存适合位置后不再改变，也称静态重定位
      • 动态运行装入：允许程序运行时在内存中移动位置，也称动态重定位
• 文件管理（外存管理）
  • 文件
    • 基本概念：由创建者所定义的一组相关信息的集合
    • 分类
      • 按用途分类：系统文件、库文件、用户文件
      • 按保护级别分类：只读文件、读写文件、执行文件（不允许读写）、不保护文件
      • 按信息流向分类：输入文件、输出文件、输入输出文件
      • 按数据形式分类：源文件、目标文件、可执行文件
      • 按逻辑结构分类
        • 有结构的记录式文件
          • 顺序文件:从相应文件的FCB中得到分配给该文件的起始物理盘块号，通过总偏移量计算其所在盘块号及在盘块号内的偏移量
          • 链式文件
            • 显式链接：从文件的FCB块中得到分配给该文件的起始物理盘块号，用于链接物理块的指针显式放在内存的一张链接表中(FAT)，访问某一盘块时要从首块开始一一将指针读出，直至读到目标盘块
            • 隐式链接：每个盘块留出4B的空间（通常为最后的4B）存放下一盘块的块号，从FCB中可获得分配给该文件的起始物理盘块号
            • 根据其总偏移量计算出块内偏移量
          • 索引文件：从相应文件的FCB中获得索引表的地址，根据总偏移量计算出其在索引表内的项数、项内偏移量
          • 索引顺序文件：将顺序文件中的所有记录分为若干个组，为顺序文件建立一张索引表，并为每组中的第一个记录在索引表中建立一个索引项
          • 直接文件：建立关键字与相应记录物理地址之间的对应关系，散列文件（Hash）是典型的直接文件，通过散列函数对关键字进行转换
        • 无结构的流式文件
      • 按物理结构分类：连续分配文件、链接分配文件、索引分配文件
    • 基本组成：基本数据项→组合数据项→记录（数据项的集合）→文件
    • 文件管理角度下的文件组成
      • 文件控制块：操作系统为文件设置的用于描述和控制文件的数据结构
      • 文件体
    • 文件目录
      • 基本概念：计算机系统建立文件的索引，即文件名和文件物理位置之间的映射关系
      • 索引节点技术：检索目录时，只用到了文件名，匹配之后才需要读出物理地址，因此某些系统采用文件名与文件描述信息分开的办法，将文件描述信息单独形成一个索引节点存于外存（如磁盘）
        • 基本操作
          • 检索信息：检索目录→检索磁盘找齐目录内缺失的内容
          • 用户共享文件：用户只要掌握欲共享文件的路径即可实现共享，如 /…/…/D/F表示该用户的上一级目录的上一级目录的下级目录D，D所包含的文件F
          • 设置访问权限：修改某文件的存取控制表，在其访问权限的用户列表中增删用户即可
          • 减少磁盘启动次数：将根目录项设置为离目标目录项更近的目录项，即可缩短路径，减少磁盘启动次数
          • 增加目录项：直接在某一目录项下增加成为子目录项即可，但同一双亲目录下的同级目录项之间不可同名
          • 重命名目录项：将目录项读入（并非直接取走，而是复制到内存）内存指定区域，将目录项重命名之后写回，之后删除原目录项即可
          • 插入记录
            • 对顺序文件：由于是顺序文件，不需要检索插入位置，直接将插入位置前的n个记录前移（后者插入位置后的记录后移），需要访盘2n次（从磁盘读出再存回磁盘），而后将目标记录插入目标位置，需要访盘1次
            • 对链式文件：找到需要插入的位置n，需要检索n-1次即访盘n-1次，之后将第n-1块的下地址赋给新块（包括新块从磁盘存回内存、修改内存中第n-1块的下地址）并将新块插入（从内存返回磁盘），需要访盘2次
        • 磁盘启动次数
          • 根目录读取其下属目录时，只需要启动一次磁盘，而非根目录读取下属目录或下属文件时，则可能因为尚未检索到目的目录或目的文件而进行多次启动磁盘直至检索成功并读取
          • 顺序文件在检索目录完成后，只需要一次启动就能读取，而链式文件在检索目录完成后，需要从首盘块一次一次往下读直至读到目标盘块，所以需要启动数为读盘数
        • 最大文件长度
          • 顺序文件：盘块数*单个磁盘大小
          • 索引文件：索引表项数*单个磁盘大小
          • 链式文件
            • 显式链接：[2^(FAT簇号所占位数)]*单个簇的大小
            • 隐式链接：[2^(下地址部分所占位数)]*单个块的大小
      • 分类
        • 单级目录结构：只建立一张目录表
        • 二级目录结构：将文件目录分为主文件目录（包含用户名以及对应指针）和用户文件目录
        • 树形目录结构（多级）
        • 图形目录结构：在树形目录结构基础上增加了一些指向同一节点的有向边，使整个目录成为一个有向无环图
      • 实现方式
        • 线性表
        • 散列表：散列表根据文件名得到一个值，并返回一个指向线性表中元素的指针
    • 文件共享
      • 硬链接：基于索引节点的共享方式
        • 基本概念:让多个不在或者同在一个目录下的文件名，同时能够修改同一个文件，其中一个修改后，所有与其有硬链接的文件都一起修改了
        • 实现方式：将目录项中的指针指向同一个索引节点
      • 软链接：利用符号链实现文件共享
        • 创建一个称为链接的新目录项
    • 文件保护
      • 限制访问类型
      • 访问控制：访问控制矩阵、访问控制表、用户权限表、口令（空灵直接存储在系统内部）、密码
  • 文件系统及实现
    • 文件系统概念：操作系统中与文件管理有关的软件和数据的集合
    • 文件系统层次结构
    • 文件物理结构的实现
      • 外存分配方式
        • 连续分配：要求为每一个文件分配一组相邻接的盘块
        • 链接分配（离散分配方式）
          • 隐式链接：在文件目录的每个目录项中，都需含有指向链接文件第一个盘块和最后一个盘块的指针
          • 显式链接：把链接文件各物理块的指针，显式地存放在内存的一张链接表中
        • 索引分配：系统在文件分配表(FAT)中为每一个文件分配一个表目，指出该文件的索引表所在的物理块
      • 文件存储空间管理：为每个文件分配必要的外存空间
        • 空闲表法：系统为外存上的所有空闲区建立一张空闲表，为每个文件分配一块连续的存储空间
        • 空闲链表法：将所有空闲盘区拉成一条空闲链
        • 位示图法：利用二进制的一位来表示磁盘中一个盘块的使用情况
        • 成组链接法：在UNIX系统中，将空闲块分成若干组，每100个空闲块为一组，每组的第一空闲块登记了下一组空闲块的物理盘块号和空闲块总数
  • 磁盘组织与管理
    • 调度算法
      • 先来先服务(FCFS)算法、最短寻道时间算法
      • 扫描算法（SCAN或电梯调度算法）：由里向外地访问，直至再无更外的磁道需要访问时，才将磁臂换向，由外向里移动
      • 循环扫描算法：在扫描算法的基础上规定磁头单向移动来提供服务，回返时直接快速移动至起始端而不服务任何请求
    • 磁盘管理
      • 格式化：在物理驱动器（磁盘）的所有数据区上写零的操作过程，同时对硬盘介质做一致性检测，并且标记出不可读和坏的扇区
    • 启动磁盘（系统磁盘）：运行操作系统需要自举程序作为启动程序，一般只在ROM中保存很小的自举装入程序，而将完整的自举程序保存在磁盘一个固定位置，称为启动块，拥有启动分区的磁盘称为系统磁盘
  • 设备管理
    • I/O管理
      • 任务与功能
        • 缓冲管理：为达到缓解CPU和I/O设备速度不匹配的矛盾，达到提高CPU和I/O设备利用率，提高系统吞吐量的目的，许多操作系统通过设置缓冲区的办法来实现
        • 设备分配：设备分配的基本任务是根据用户的I/O请求，为他们分配所需的设备。如果在I/O设备和CPU之间还存在设备控制器和通道，则还需为分配出去的设备分配相应的控制器和通道
        • 设备处理：设备处理程序又称设备驱动程序。其基本任务是实现CPU和设备控制器之间的通信
        • 设备独立性和虚拟设备：用户向系统申请和使用的设备与实际操作的设备无关，应用程序独立于具体使用的物理设备
      • I/O控制
        • 设备控制器：控制一个或多个I/O设备，以实现I/O设备和计算机之间的数据交换，是CPU与I/O设备之间的接口，它接收从CPU发来的命令，并去控制I/O设备工作，以使处理机从繁杂的设备控制事务中解脱出来
        • 控制方式
          • 程序直接控制方式：利用I/O测试指令测试设备的闲忙。若设备不忙，则执行输入或输出指令；若设备忙，则I/O测试指令不断对该设备进行测试，直到设备空闲为止
            • 优点：控制简单，不需要很多硬件支持
            • 缺点：CPU与外设间只能串行工作，适用于执行速度较慢且外设少的系统
          • 中断控制方式：每当设备完成I/O操作，便以中断请求方式通知CPU，然后进行相应处理
            • 优点：能实现CPU与设备、设备与设备间的并行工作
            • 缺点：中断次数多，消耗大量CPU时间
          • 直接内存存取（DMA）方式：使用专门的DMA控制器，采用窃取总线程控制权的方法，由DMA控制器送出内存地址和发出内存读、设备写或者设备读、内存写的控制信号完成内存与设备之间的直接数据传送，而不用CPU干预。当本次DMA传送的数据全部完成时才产生中断，请求CPU进行结束处理
            • 优点：在一批数据传送完成后中断CPU，减少中断次数
            • 缺点：对外设的管理与某些操作仍需由CPU控制，且多个DMA控制器也不经济
          • 通道控制方式：通道是一个用来控制外部设备工作的硬件机制，相当于一个功能简单的处理机。通道是独立于CPU的、专门负责数据的输入输出传输工作的处理器，它对外部设备实统一管理，代替CPU对I/O操作进行控制，从而使I/O操作可以与CPU并行工作
            • 字节多路通道：连接多个慢速的和中速的设备，这些设备的数据传送以字节为单位
            • 数组选择通道：连接高速传输设备，一次只能对一个设备进行传输
            • 数组多路通道：以数组(数据块)为单位在若干高速传输操作之间进行交叉复用
            • 优点是CPU利用率高且一个通道可以控制多台设备，缺点是价格昂贵
      • I/O软件层次结构
    • I/O核心子系统：设备控制的各类方法
      • I/O调度：确定一个好的顺序来执行I/O请求，可改善计算机效率
      • 缓冲技术
        • 设置缓冲区的目的：缓和CPU与I/O设备之间速度不匹配的矛盾；减少中断CPU的次数；提高CPU与I/O设备之间的并行性
        • 缓冲方式
          • 单缓冲：在设备和处理机之间设置一个缓冲器
          • 双缓冲：输入设备先装填第一个缓冲区，在满了之后，操作系统可以将第一个缓冲区的数据传送到用户区供处理器进行计算，而输入设备可以继续装填第二个缓冲区
          • 循环缓冲：包含多个大小相等、依次链指针指向下一个缓冲区的缓冲区
          • 缓冲池：把多个缓冲区连接起来统一管理，既可用于输入又可用于输出的缓冲结构
      • 设备分配
        • 设备分配的数据结构：DCT、COCT、CHCT、SDT
        • 设备分配算法：先来先服务、优先级高者优先
        • 设备分配程序
          • 单通路I/O系统的设备分配：分配设备-分配设备控制器-分配通道
          • 多通路I/O系统的设备分配：检索系统设备控制表找空闲设备并检测安全性后分配-检索设备控制器控制表找到空闲设备控制器并分配-查找相邻的空闲通道并分配
      • 设备回收：当进程使用完对应的I/O设备后，释放所占有设备、设备控制器、通道，系统进行回收，修改对应的数据结构，以便下次使用
      • 假脱机技术（SPOOLing）
        • 基本概念
          • 脱机：不连网访问以前缓存中的网页
          • 假脱机：关于慢速字符设备如何与计算机主机交换信息的一种外设同时联机操作技术，由主机和相应的通道共同承担作业的输入输出工作，利用磁盘作为后援存储器，实现外围设备同时联机操作
        • 基本结构
          • 内存部分：输入缓冲区+输出缓冲区，输入进程+输出进程
          • 磁盘部分：输入井+输出井
        • 基本原理：预先从低速的输入型独占设备上将程序运行需要的数据传送到磁盘的输入井中，当用户程序运行时，可以直接从输入井中将数据读入内存。由于磁盘是共享设备，多个用户进程可以共享使用输入井。这样，就将输入型独占设备改造成了可共享使用的虚拟设备。改造输出型独占设备的方法同上
        • 基本过程：输入井与输出井在磁盘内共享一个存储空间max（即i+o≤max）。只要输入井有数据块，输入进程会读入、处理，并产生结果数据，写到输出井；只要输出井有数据块，输出进程会输出它。为了保证不出现死锁，还应满足i≤max-1
• 设备管理
  • I/O管理
    • 任务与功能
      • 缓冲管理：为达到缓解CPU和I/O设备速度不匹配的矛盾，达到提高CPU和I/O设备利用率，提高系统吞吐量的目的，许多操作系统通过设置缓冲区的办法来实现
      • 设备分配：设备分配的基本任务是根据用户的I/O请求，为他们分配所需的设备。如果在I/O设备和CPU之间还存在设备控制器和通道，则还需为分配出去的设备分配相应的控制器和通道
      • 设备处理：设备处理程序又称设备驱动程序。其基本任务是实现CPU和设备控制器之间的通信
      • 设备独立性和虚拟设备：用户向系统申请和使用的设备与实际操作的设备无关，应用程序独立于具体使用的物理设备
    • I/O控制
      • 设备控制器：控制一个或多个I/O设备，以实现I/O设备和计算机之间的数据交换，是CPU与I/O设备之间的接口，它接收从CPU发来的命令，并去控制I/O设备工作，以使处理机从繁杂的设备控制事务中解脱出来
      • 控制方式
        • 程序直接控制方式：利用I/O测试指令测试设备的闲忙。若设备不忙，则执行输入或输出指令；若设备忙，则I/O测试指令不断对该设备进行测试，直到设备空闲为止
          • 优点：控制简单，不需要很多硬件支持
          • 缺点：CPU与外设间只能串行工作，适用于执行速度较慢且外设少的系统
        • 中断控制方式：每当设备完成I/O操作，便以中断请求方式通知CPU，然后进行相应处理
          • 优点：能实现CPU与设备、设备与设备间的并行工作
          • 缺点：中断次数多，消耗大量CPU时间
        • 直接内存存取（DMA）方式：使用专门的DMA控制器，采用窃取总线程控制权的方法，由DMA控制器送出内存地址和发出内存读、设备写或者设备读、内存写的控制信号完成内存与设备之间的直接数据传送，而不用CPU干预。当本次DMA传送的数据全部完成时才产生中断，请求CPU进行结束处理
          • 优点：在一批数据传送完成后中断CPU，减少中断次数
          • 缺点：对外设的管理与某些操作仍需由CPU控制，且多个DMA控制器也不经济
        • 通道控制方式：通道是一个用来控制外部设备工作的硬件机制，相当于一个功能简单的处理机。通道是独立于CPU的、专门负责数据的输入输出传输工作的处理器，它对外部设备实统一管理，代替CPU对I/O操作进行控制，从而使I/O操作可以与CPU并行工作
          • 字节多路通道：连接多个慢速的和中速的设备，这些设备的数据传送以字节为单位
          • 数组选择通道：连接高速传输设备，一次只能对一个设备进行传输
          • 数组多路通道：以数组(数据块)为单位在若干高速传输操作之间进行交叉复用
          • 优点是CPU利用率高且一个通道可以控制多台设备，缺点是价格昂贵
    • I/O软件层次结构
  • I/O核心子系统：设备控制的各类方法
    • I/O调度：确定一个好的顺序来执行I/O请求，可改善计算机效率
    • 缓冲技术
      • 设置缓冲区的目的：缓和CPU与I/O设备之间速度不匹配的矛盾；减少中断CPU的次数；提高CPU与I/O设备之间的并行性
      • 缓冲方式
        • 单缓冲：在设备和处理机之间设置一个缓冲器
        • 双缓冲：输入设备先装填第一个缓冲区，在满了之后，操作系统可以将第一个缓冲区的数据传送到用户区供处理器进行计算，而输入设备可以继续装填第二个缓冲区
        • 循环缓冲：包含多个大小相等、依次链指针指向下一个缓冲区的缓冲区
        • 缓冲池：把多个缓冲区连接起来统一管理，既可用于输入又可用于输出的缓冲结构
    • 设备分配
      • 设备分配的数据结构：DCT、COCT、CHCT、SDT
      • 设备分配算法：先来先服务、优先级高者优先
      • 设备分配程序
        • 单通路I/O系统的设备分配：分配设备-分配设备控制器-分配通道
        • 多通路I/O系统的设备分配：检索系统设备控制表找空闲设备并检测安全性后分配-检索设备控制器控制表找到空闲设备控制器并分配-查找相邻的空闲通道并分配
    • 设备回收：当进程使用完对应的I/O设备后，释放所占有设备、设备控制器、通道，系统进行回收，修改对应的数据结构，以便下次使用
    • 假脱机技术（SPOOLing）
      • 基本概念
        • 脱机：不连网访问以前缓存中的网页
        • 假脱机：关于慢速字符设备如何与计算机主机交换信息的一种外设同时联机操作技术，由主机和相应的通道共同承担作业的输入输出工作，利用磁盘作为后援存储器，实现外围设备同时联机操作
      • 基本结构
        • 内存部分：输入缓冲区+输出缓冲区，输入进程+输出进程
        • 磁盘部分：输入井+输出井
      • 基本原理：预先从低速的输入型独占设备上将程序运行需要的数据传送到磁盘的输入井中，当用户程序运行时，可以直接从输入井中将数据读入内存。由于磁盘是共享设备，多个用户进程可以共享使用输入井。这样，就将输入型独占设备改造成了可共享使用的虚拟设备。改造输出型独占设备的方法同上
      • 基本过程：输入井与输出井在磁盘内共享一个存储空间max（即i+o≤max）。只要输入井有数据块，输入进程会读入、处理，并产生结果数据，写到输出井；只要输出井有数据块，输出进程会输出它。为了保证不出现死锁，还应满足i≤max-1