【笔记】操作系统组成原理知识点

前言

操作系统知识点

操作系统提供的功能

作为资源的管理者

• 处理机管理
• 存储器管理
• 文件管理
• 设备管理

向用户提供服务

• 命令接口
  • 联机命令接口
  • 脱机命令接口
• 程序接口
• GUI用户图形界面

操作系统的特征

• 并发：指两个或多个事件在同一时间间隔内发生。这些事件宏观上是同时发生的，但微观上是交替发生的
  • 操作系统的并发性，指的是计算机系统中同时存在着多个运行着的程序
• 共享
  • 互斥共享方式：系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源
  • 同时共享方式：系统中的某些资源，允许一个时间段内由多个进程“同时”对它们进行访问
• 虚拟
• 异步

操作系统的发展与分类

1. 手工操作阶段
2. 批处理阶段
3. 分时操作系统
4. 实时操作系统
5. 网络操作系统
6. 分布式操作系统
7. 个人操作系统

操作系统运行机制

• 指令
  • 特权指令
  • 非特权指令
• 处理器状态
  • 核心态
  • 用户态
• 程序
  • 内核程序
  • 应用程序

操作系统内核

• 时钟管理
• 终端处理
• 原语
• 对系统资源进行管理的功能（可选）
  • 进程管理
  • 存储器管理
  • 设备管理

操作系统的体系结构

大内核

• 优点：性能高
• 缺点：内核代码庞大，结构混乱，难以维护

微内核

• 优点：内核功能少，结构清晰，方便维护
• 缺点：需要频繁地在核心态和用户态之间切换，性能低

中断

• 中断可以使CPU从用户态切换为核心态，使操作系统获得计算机的控制权

• 内中断（又称为异常、例外、陷入）

• 外中断

系统调用

• 设备管理：完成设备的请求、释放、启动等功能
• 文件管理：完成文件的读、写、创建、删除等功能
• 进程管理：完成进程的创建、销毁、阻塞、唤醒等功能
• 进程通信：完成进程之间的消息传递、信号传递等功能
• 内存管理：完成内存的分配、回收等功能

进程

进程的组成

进程的组成实际上是进程实体（进程映像）的组成，因为进程是一个动态的概念，表示的是完成一次程序执行的过程，只不过我们通常将进程实体叫做进程

• 程序段
• 数据段
• PCB
  • 进程描述信息
    • 进程标识符PID
    • 用户标识符UID
  • 进程控制和管理信息
    • 进程当前状态
    • 进程优先级
  • 资源分配清单
    • 程序段指针
    • 数据段指针
    • 鼠标
    • 键盘
  • 处理机相关信息
    • 各种寄存器值

进程的组织方式

• 链接方式
• 索引方式

进程的特征

• 动态性：进程是程序一次执行过程，是动态地产生、变化、消亡的
• 并发性：内存中有多个进程实体，各进程可并发执行
• 独立性：进程是能独立运行、独立获得资源、独立接受调度的基本单位
• 异步性：各进程按各自独立的、不可预知的速度向前推进，操作系统要提供进程同步机制来解决异步问题
• 结构性：每个进程都会配置一个PCB。结构上看，进程由程序段、数据段、PCB段组成

进程的状态

• 运行态：占有CPU，并在CPU上运行
• 就绪态：已经具备运行条件，但由于没有空闲CPU，而暂时不能运行
• 阻塞态（等待态）：因等待某一事件而暂时不能运行

进程的控制

• 进程控制用原语实现
• 原语用开、关中断来实现
• 原语是一种特殊的程序
• 原语是原子性的

进程的创建

• 创建原语
  1. 申请空白PCB
  2. 为新进程分配所需资源
  3. 初始化PCB
  4. 将PCB插入就绪队列
• 引起进程创建的事件
  • 用户作业：分时系统中，用户登录成功，系统会为其建立一个新的进程
  • 作业调度：多道批处理系统中，有心的作业放入内存时，会为其建立一个新的进程
  • 提供服务：用户向操作系统提出某些请求时，会新建一个进程处理该请求
  • 应用请求：由用户进程主动请求创建一个子进程

进程的终止

• 撤销原语
  1. 从PCB集合中找到终止的PCB
  2. 若进程正在运行，立即剥夺CPU，将CPU分配给其他进程
  3. 终止其所有子进程
  4. 将该进程拥有的所有资源归还给父进程或操作系统
  5. 删除PCB
• 引起进程终止的事件
  • 正常结束
  • 异常结束
  • 外界干预

进程的阻塞

• 阻塞原语
  1. 找到要阻塞的进程对应的PCB
  2. 保护进程运行现场，将PCB状态信息设置为阻塞态，暂时停止进程运行
  3. 将PCB插入相应事件的等待队列
• 引起阻塞的事件
  • 需要等待系统分配某种资源
  • 需要等待相互合作的其他进程完成工作

进程的唤醒

• 唤醒原语
  1. 从事件等待队列中找到PCB
  2. 将PCB从等待队列移除，设置进程为就绪态
  3. 将PCB插入就绪队列，等待被调度
• 引起进程唤醒的事件
  • 等待的事件发生

进程切换

• 切换原语
  1. 将运行环境信息存入PCB
  2. PCB移入相应队列
  3. 选择另一个进程执行，并更新其PCB
  4. 根据PCB恢复新进程所需的运行环境
• 引起进程切换的事件
  • 当进程时间片到
  • 有更高优先级的进程到达
  • 当前进程主动阻塞
  • 当前进程终止

进程的通信

进程通信的方式

共享存储

• 两个进程对共享空间的访问必须是互斥的
• 基于数据结构的共享：共享空间里只能放一定大小的数据
• 基于存储区的共享：在内存中划出一块共享存储区，数据的形式、存放位置都又进程控制，而不是操作系统

管道通信

• 管道只能采用半双工通信，某一时间段内只能实现单项传输。如果要实现双向同时通信，则需要设置两个管道
• 各进程要互斥地访问管道
• 数据以字符流的形式写入管道，当管道写满时，写进程的write()系统调用将被阻塞，等待读进程将数据取走。当读进程将数据全部取走后，管道变空，此时读进程read()系统调用将被阻塞
• 如果没有写满，就不允许读；如果没有读空；就不允许写
• 数据一旦被读出，就从管道中抛弃，这就意味着读进程最多只能有一个，否则可能会有读错数据的情况

消息传递

• 进程间数据交换以格式化的消息为单位

• 进程通过操作系统提供的发送消息和接收消息两个原语进行数据交换

• 直接通信方式：把消息直接挂到接收进程的消息缓冲队列上

• 间接通信方式：消息要先发送到中间实体（信箱）中，因此也称信箱通信方式

线程

线程是什么

• 现成是一个基本的CPU执行单元，也是程序执行流的最小单位
• 引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内可以并发处理各种任务
• 引入线程后，进程只作为除CPU之外的系统资源的分配单元

线程的属性

• 线程是处理机调度的单位
• 多CPU计算机中，各个线程可以占用不通的CPU
• 每个线程都有一个线程ID，线程控制块（TCB）
• 线程也有就绪、阻塞、运行三种基本状态
• 线程几乎不拥有系统资源
• 同一进程的不同线程间共享进程的属性
• 由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预
• 同一进程中线程切换，不会引起进程切换；不同进程中的线程切换，会引起进程切换
• 切换同进程内的线程，系统开销很小；切换进程系统开销很大

线程的实现方式

用户级线程

• 用户级线程由应用程序通过线程库实现
• 所有的线程管理工作，都由应用程序负责
• 用户级线程中，现成切换可以在用户态下即可完成，无需操作系统干预
• 在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在

内核级线程

• 内核级线程的管理工作由操作系统内核完成。线程的调度、切换等工作都由内核负责，因此内核线程的切换必须在内核态下才能完成

多线程模型

多对一模型

• 多个用户级线程映射到一个内核级线程
• 优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
• 缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可再多核处理机上并行运行

一对一模型

• 一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程
• 优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行
• 缺点：一个用户级线程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大

多对多模型

• n个用户级线程映射到m个内核级线程（n>=m）。每个用户进程对应m个内核级线程
• 克服了多对一模型并发度不高的缺点，又克服了一对一模型中一个用户进程占用太多内核级线程开销太大的缺点

调度

• 当多道程序系统中，进程的数量往往是多于处理机的个数的，这样不可能同时并行地处理各个进程。处理机调度就是从就绪序列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程的并发执行

调度的三个层次

高级调度

• 高级调度（作业调度）按照一定的原则从外存上处于后备队列的作业中挑选一个（或多个）作业，给它们分配内存等必要资源，并建立相应的进程（建立BPC），以使它（们）获得竞争处理机的权利

• 高级调度是辅存（外存）与内存之间的调度。每次作业只调入一次、调出一次。作业调入时会建立相应的PCB，作业调出时才撤销PCB。高级调度主要是指调入问题，因为只有调入的时机需要操作系统来决定，但调出时机必然是作业运行结束才调出

中级调度

• 引入了虚拟存储技术后，可将暂时不能运行的进程调至外存等待，等它重新具备了运行条件且内存又稍有空闲时，再重新调入内存。这么做的目的是提高利用率和系统吞吐量。暂时调到外存等待的进程状态为挂起状态。值得注意的是，PCB并不会一起调到外存，而是常驻内存。PCB中会记录进程数据在外存中的存放位置，进程状态等信息，操作系统通过内存中的PCB来保持对各个进程的监控、管理。被挂起的进程PCB会被放到挂起队列中

• 中级调度（内存调度）是要决定哪个处于挂起状态的进程重新调入内存，一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高

低级调度

• 低级调度（进程调度），其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它

• 进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度的频率很高，一般几十毫秒一次

进程调度的时机

需要进行进程调度与切换的情况

• 当前运行的进程主动放弃处理机

  • 进程正常终止
  • 进程运行过程中发生异常而终止
  • 进程主动请求阻塞

• 当前运行的进程被动放弃处理机

  • 分给进程的时间片用完
  • 有更紧急的事需要处理
  • 有优先级更高的进程进入就绪队列

不能进行进程调度与切换的情况

• 在处理中断的过程中：中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换
• 进程在操作系统内核程序临界区中
• 在原子操作过程中（原语）：原子操作不可中断

进程调度的方式

非剥夺调度方式（非抢占方式）

• 只允许进程主动放弃
• 在进程运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态

剥夺调度方式（抢占方式）

• 当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要更紧迫的那个进程

调度算法的评价指标

CPU利用率

• CPU忙碌的时间占总时间的比例
• CPU利用率 = CPU忙碌时间 / 总时间

系统吞吐量

• 单位时间内完成作业的数量
• 系统吞吐量 = 总共完成的作业 / 总共花了的时间

周转时间

• 作业周转时间 = 作业完成时间 - 作业提交时间

  • 对于用户来说，更关心自己的单个作业的周转时间

• 平均周转时间 = 各作业周转时间之和 / 作业数

  • 对于操作系统来说，更关心系统的整体表现

• 带权周转时间 = 作业周转时间 / 作业实际运行时间 = (作业完成时间 - 作业提交时间) / 作业实际运行时间

• 平均带权周转时间 = 各作业带权周转时间之和 / 作业数

等待时间

• 等待时间是指进程（作业）处于等待处理机状态时间之和

进程等待时间

• 对于进程来说，等待时间就是指进程建立后等待被服务的时间之和

作业等待时间

• 对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中的等待时间

调度算法

FCFS（先来先服务算法）

• 主要从公平的角度考虑

• 按照作业（进程）的到达先后顺序进行服务

• 用于作业调度：考虑是哪个作业先到达后备队列

• 用于进程调度：考虑是哪个进程先到达就绪队列

• 非抢占算法

• 优点：公平、算法实现简单。不会导致饥饿

• 缺点：排在长作业（进程）后面的短作业（进程）需要等待很长时间，带权周转时间很大，对短作业（进程）用户体验不好

SJF（短作业优先算法）

• 追求最少的平均等待时间、最少的平均周转时间、最少的平均带权周转时间

• 最短的作业（进程）优先得到服务

• 用于作业（进程）调度：可用于作业调度，也可用于进程调度

• 抢占算法

• 优点：“最短”的平均等待时间、平均周转时间

• 缺点：不公平。对短作业有利，对长作业不利。可能产生饥饿现象

HRRN（高响应比优先算法）

• 要综合考虑作业（进程）的等待时间和要求服务的时间

• 在每次调度时先计算各个作业（进程）的响应比，选择响应比最高的作业（进程）优先为其服务

响应比 = (等待时间 + 要求服务时间) / 要求服务时间

• 非抢占的算法

• 优缺点：综合考虑了等待时间和运行时间。等待时间相同时，要求服务时间短的优先。要求服务时间相同时，等待时间长的优先。不会导致饥饿

时间片轮转调度算法

• 公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到相应

• 按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队

• 用于进程调度

• 抢占的算法

• 优点：公平。响应快，适用于分时操作系统。不会导致饥饿

• 缺点：由于高频率的进程切换，因此有一定开销。不区分任务的紧急程度

优先级调度算法

• 每个作业（进程）有各自的优先级，调度时选择优先级最高的作业（进程）

• 既可以用于作业调度，也可以用于进程调度

• 既有抢占式，也有非抢占式

• 优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业（进程）的偏好程度

• 缺点：若源源不断地有高优先级进程到来，可能会导致饥饿

多级反馈队列调度算法

• 对以上算法折中平衡

• 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大

• 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片，进程还未结束，则进程进入下一级队列队尾，如果已经是最下级的队列，则重新放回该队列队尾

• 只有当前级队列为空时，才会进行下一级进程的时间片分配

• 用于进程调度

• 抢占式算法

• 优点：对各类型进程相对公平（FCFS优点）。每个新到达的进程都可以很快就得到相应（RR优点）。短进程只用较少的时间就可以完成（SRF优点）。不必实现评估进程的运行时间（避免用户作假）。可灵活地调整对各类进程的偏好程度（优先级调度算法优点）

• 缺点：如果源源不断有新的进程到达，有可能导致饥饿

进程同步

• 同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作

• 我们把一个时间段内允许一个进程使用的资源称为临界资源。对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源后，另一个进程才能去访问临界资源

对资源的互斥访问四个部分

• 进入区
• 临界区（临界段）
• 退出区
• 剩余区

互斥访问遵循的规则

• 空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
• 忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待
• 有限等待：对请求访问的进程，应保证在有限时间内进入临界区
• 让权全待：当进程不能进入临界区时，应立即释放处理机，防止进程处于忙等待状态

进程互斥的实现方法

软件实现方法

单标志法

• 两个进程在访问完临界区后会吧使用临界区的权限转让给另一个进程，也就是说每个进程进入临界区的权限只能被 另一个进程赋予

• 单标志法的问题：违背空闲让进原则

双标志先检查法

• 设置一个布尔数组，数组中各个元素用来标记各进程想进入临界区的意愿，每个进程在进入临界区之前先检查当前有没有进程想进入临界区，如果没有就把自身的标志改为true，之后开始访问临界区

• 双标志先检查法的问题：违背忙则等待原则

双标志后检查法

• 双标志先检查法的改版

• 先上锁后检查

• 双标志后检查法的问题：解决了忙则等待的问题，但是违背了空闲让进和有限等待的问题

Perterson算法

• 在双标志法基础上，主动让对方先使用临界区

• Perterson算法解决了进程互斥问题，遵循了空闲忙进、忙则等待、有限等待三个原则，但是依然未遵循让权等待原则

硬件实现方法

中断屏蔽法

• 利用开关中断指令实现

• 在某个进程开始访问临界区知道结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个进程同时访问临界区的情况

• 中断屏蔽法优点：简单、高效

• 中断屏蔽法的缺点：不适合与多处理机。只适用于操作系统内核进程，不适用于用户进程

TestAndSet指令

• TestAndSet指令简称TS指令

• 别称TestAndSetLock指令，简称TSL指令

• 执行的过程不允许被中断

• TestAndSet指令优点：实现简单。无需像软件实现方式一样严格检查是否有逻辑漏洞，适用于多处理机环境

• TestAndSet指令缺点：不满足让权等待原则。暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致忙等

Swap指令

• 别称Exchange指令

• 简称XCHG指令

• 执行的过程不允许被中断

• Swap指令优点：实现简单。无需像软件实现方式一样严格检查是否有逻辑漏洞，适用于多处理机环境

• Swap指令缺点：不满足让权等待原则。暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致忙>等

信号量机制

• 信号量其实就是一个变量，用于表示系统中某种资源的数量

• 使用原语操作信号量：

  • P（荷兰语：proberen）操作：wait(信号量)
  • V（荷兰语：verhogen）操作：signal(信号量)

• 信号量的操作只有三种：初始化、P操作、V操作

信号量的类型

整型信号量

• 用一个整数型的变量作为信号量，用来表示系统中某种资源的数量

• 缺点：不满足让权等待原则

记录型信号量

• 用记录型数据结构表示的信号量

• 优点：遵循了让权等待原则

信号量实现进程互斥

1. 分析并发进程的关键活动，划定临界区
2. 设置互斥信号量，初始值为1
3. 在临界区之前执行P操作
4. 在临界区之后执行V操作

信号量实现进程同步

1. 分析什么地方需要实现同步关系，即必须保证一前一后执行的两个操作
2. 设置同步信号量，初始值为0
3. 在必须先执行的操作之后执行V操作
4. 在必须后执行的操作之前执行P操作

信号量实现前驱关系

1. 要为每一对前驱关系各设置一个同步变量
2. 在必须先执行的操作之后对应的同步变量执行V操作
3. 在必须后执行的操作之前对应的同步变量执行P操作

管程

管程的组成

• 局部于管程的共享数据结构说明
• 对该数据结构进行操作的一组过程
• 对局部与管程的共享数据结构设置初始值的语句
• 管程有一个名字

管程的特征

• 局部于管程的数据只能被局部于管程的过程所访问
• 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
• 每次仅允许一个进程在管程内执行某个内部过程

死锁

• 死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象
• 饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象
• 死循环：某进程执行过程中一直跳不出某个循环的现象

死锁发生的条件

• 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁
• 不可剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放
• 请求和保持请求条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求被进程阻塞，但又对自己已有的资源保持不放

什么时候发生死锁

• 对资源的竞争
• 进程推进顺序非法
• 信号量的使用不当

死锁的处理策略

• 预防死锁：破坏死锁产生的四个表要填见中的一个活多个
• 避免死锁：用某种方法防止系统进入不安全状态，从而避免死锁
• 死锁的检测和解除：允许死锁的发生，不过操作系统会负责监测出死锁的发生，然后采取某种措施解除死锁

预防死锁

破坏互斥条件

• 如果吧只能互斥使用的资源改造为允许共享使用的资源，则系统不会进入死锁状态
• 例如使用SPOOLing技术把独占设备在逻辑上改造成共享设备

缺点

• 并不是所有的资源都可以改造成可共享使用的资源，为了系统的安全性很多地方还必须保护这种互斥性

破坏不剥夺条件

方案一

• 当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件

方案二

• 当某个进程需要的资源被其他进程所占有时候，可以由操作系统协助，将想要的资源强行剥夺（这种方式一般需要考虑各进程的优先级）

缺点

• 实现起来比较复杂
• 释放已获得的资源可能造成前一阶段工作的实效，因此这种方法只适用于易保存和易恢复状态的资源
• 反复地申请和释放资源会增加系统开销，降低系统吞吐量
• 若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一只发>生这样的情况，就会导致进程饥饿

破坏请求和保持条件

• 采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行，一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源

缺点

• 有些资源可能只需要用很短的时间，因此如果进程的运行期间一直都保持着所有资源，就会造成严重的资源浪费，资源利用率极低
• 有可能导致进程的饥饿现象

破坏循环等待条件

• 采用顺序资源分配法：首先给系统中的资源编号，规定每个进程必须按照编号递增的顺序请求资源，同类资源（编号相同的资源）一次申请完

缺点

• 不方便增加新的设备，因为可能需要重新分配所有的编号
• 进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费
• 必须按照次序申请资源，用户变成麻烦

避免死锁

银行家算法的步骤

1. 检查此次申请是否超过了之前生命的最大需求数
2. 检查此时系统剩余的可用资源是否还能满足这次请求
3. 试探着分配，更改各数据结构
4. 用安全性算法检查此次分配是否会导致系统进入不安全状态

安全性算法：检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，把该进程加入安全序列，并把该进程持有的资源全部回收，不断重复，看最终是否能让所有进程全部加入安全序列

死锁的检测和解除

死锁的检测

• 用某种数据结构来保存资源的请求和分配信息
• 提供一种算法，利用上述信息来检测系统是否已进入死锁状态

如果系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时是不会阻塞的，可以顺利地执行下去。
如果这个进程执行结束了，把资源归还系统，就可能使某些正在等待的进程被激活，并顺利地执行下去。
相应的，这些被激活的进程执行完了之后又会归还一些资源，这样可能又会激活另外一些阻塞的进程

如果按照上述过程分析，最终能消除所有边，就称这个图是可完全简化的，此时一定没有发生死锁；如果最终不能消除所有边，那么此时就是发生了死锁，最终还连着变的进程就是处于死锁状态的进程

• 死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁

死锁的解除

资源剥夺法

• 暂时挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程
  • 但是应防止被挂起的进程长时间得不到资源而饥饿

撤销进程法（终止进程法）

• 强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源

进程回退法

• 让一个或多个死锁进程回退到足以避免死锁的地步
  • 这就要求系统要记录进程的历史信息，设置还原点

从写程序到程序运行

• 源代码
• 编译：由源代码文件生成目标模块
• 链接：由目标模块生成装入模块，链接后形成完整的逻辑地址
  • 静态链接：装入前链接成一个完整装入模块
  • 装入时动态链接：运行前边转入边链接
  • 运行时动态链接：运行时需要目标模块才装入并链接
• 装入：将装入模块装入内存，装入后形成物理地址
  • 绝对装入：编译时产生绝对地址
  • 可重定位装入：装入时将逻辑地址转换为物理地址
  • 动态运行时装入：运行时将逻辑地址转换为物理地址，需设置重定位寄存器

内存

• 内存是用于存放数据的硬件，程序执行前需要先放到内存才能被CPU处理

内存装入（地址转换）

绝对装入

• 编译时产生绝对地址

可重定位装入

• 装入时逻辑地址转换为物理地址

动态运行时装入

• 运行时将逻辑地址转换为物理地址，需设置重定位寄存器

内存保护

方法一

• 在CPU中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，CPU检查是否越界

方法二

• 采用重定位寄存器（又称基址寄存器）和界地址寄存器（又称限长寄存器）进行越界检查
  • 重定位寄存器中存放的是进程的起始物理地址
  • 界地址寄存器存放的是地址的最大逻辑地址

内存空间的扩充

覆盖技术

• 内存中分为一个固定区和若干个覆盖区
• 需要常驻内存的段放在固定区中，调入后就不再调出（除非运行结束）
• 不常用的段放在覆盖区，需要用到时调入内存，用不到时调出内存

交换技术

• 交换技术又称对换技术
• 内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）
• 磁盘分为文件区和对换区，换出的进程放在对换区

内存空间的分配与回收

连续分配管理方式

• 连续分配是指用户进程分配的必须是一个连续的内存空间

单一连续分配方式

• 在单一连续分配方式中，内存被分为系统区和用户区

  • 系统区通常位于内存的低地址部分，用于存放操作系统相关数据
  • 用户区用于存放用户进程相关数据

• 内存中只能有一道用户程序，用户程序独占整个用户区空间

固定分区分配

• 位了能在内存中装入多道程序，且这些程序之间又不会相互干扰，于是将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业，这样就形成了最道的、最简单的一种可运行多道程序的内存管理方式
  • 分区大小相等策略：缺乏灵活性，但很适用于用一台计算机控制多个相同对象的场合
  • 分区大小不相等的策略：增加了灵活性，可以满足不同大小进程的需求
    • 这种策略操作系统需要建立一个分区说明表数据结构来实现各个分区的分配与回收，每个表项对应一个分区，通常按照分区大小排列，每个表项包括对应分区的大小、起始地址、状态

动态分区分配

• 又称可变分区分配

• 这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要，因此系统分区的大小和数目是可变的

• 采用的数据结构

  • 空闲分区表：每个空闲分区对应一个表项，表项中包含分区号、分区大小、分区起始地址等信息
  • 空闲分区链：每个分区的起始部分和末尾部分分别设置前向指针和后向指针，起始部分处还可记录分区大小等信息

• 把一个新作业装入内存时，需按照一定的动态分区分配算法，从空闲分区表或空闲分区链中选出一个分区分配给该作业。由于分配算法对系统性能有很大影响，因此人们对它进行了广泛的研究

动态分区分配算法

• 首次适应算法

每次都从低地址开始查找，找到第一个能满足大小的空闲分区。空闲分区以地址递增的次序排列，每次分配内存时顺序查找空闲分区表或空闲分区链，找到大小能满足要求的第一个空闲分区

• 最佳适应算法

由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域，因此为了保证大进程到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区域，即优先使用更小的空闲区域

• 最坏适应算法

又称最大适应算法
为了解决最佳适应算法的问题——留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便实用。空闲分区按容量递减次序链接，每次分配内存时顺序查找空闲分区表或空闲分区链，找到大小能满足要求的第一个空闲分区

• 临近适应算法

首次适应算法每次都从链头开始查找，这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。空闲分区以地址递增的顺序排列（可排成一个循环链表），每次分配内存时，从上次查找结束的位置开始查找空闲分区表或空闲分区链，找到大小能满足要求的第一个空闲分区

非连续分配管理方式

• 为用户进程分配的可以时一些分散的内存空间

• 将内存空间分为一个个大小相等的分区，每个分区就是一个页框（或称页帧、内存块、无力块），每个页框有一个编号，即页框号（或内存块号、页帧号、物理块号），页框号从0开始

• 将用户进程的地址空间分为与页框大小相等的一个个区域，成为页（或称页面），每个页面也有一个编号，即页号，页号也是从0开始

• 操作系统以页框为单位为各个进程分配内存空间，进程的每个页面分别放入一个页框中，也就是说，进程的页面与内存的页框有一一对应的关系。各个页面不必连续存放，也不必按先后顺序来，可以放到不相邻的各个页框中

地址转换原理

1. 算数逻辑地址对应的页号
2. 知道该页号对应页面在内存中起始地址
3. 算出逻辑地址在页面内的偏移量
4. 物理地址 = 页面地址 + 页内偏移量

页号 = 逻辑地址 / 页面长度
页内偏移量 = 逻辑地址 % 页面长度
页面在内存中的起始位置 = 操作系统需要用某种数据结构记录进程各个页面的起始位置

分页式存储管理

• 为了能知道进程的每个页面在内存中存放的位置，操作系统为每个进程建立一张页表

• 一个进程对应一张页表

• 进程的每一页对应一个页表项

• 每个页表项由页号和块号组成

• 页表记录进程页面和实际存放的内存块之间的对应关系

单级页表

基本地址变换机构

• 基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址
• 通常会在系统中设置一个页表寄存器（PTR），存放页表在内存中的起始地址和页面长度，程序未执行时，页表的起始地址和页面长度放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把它们放到页表寄存器中

地址转换

1. 根据逻辑地址计算出页号和页内偏移量
2. 判断页号是否越界
3. 查询页表，找到页号对应的页表项，确定页面存放的内存块号
4. 用内存块号和页内偏移量得到物理地址
5. 访问目标内存单元

具有快表的地址变换机构

• 快表，又称联想寄存器（TLB），是一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应的内存中的页表称为慢表

地址变换

1. CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与块表中的所有页号进行比较
2. 如果找到匹配的页号，说明要访问的页表项在块表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后访问该物理地址对应的内存单元

• 因此，若快表命中，则访问某个逻辑地址仅需一次访存即可

3. 如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后访问该物理地址对应的内存单元

• 因此，若快未命中，则访问某个逻辑地址需要两次访存
  • 在找到页表项后，应同时将其存入快表以便后面可能的再次访问
  • 如果快表已满，则必须按照一定的算法对旧的页表项进行替换

多级页表

地址转换

1. 按照地址结构将逻辑地址拆分成三部分
2. 从PCB中读出页目录表始地址，再根据一级页号查页目录表，找到下一级页表在内存中的存放位置
3. 根据二级页号查表，找到最终想访问的内存块号
4. 结合页内偏移量得到物理地址

基本分段式存储管理

• 基本分段式存储管理与分页式存储管理的最大区别：离散分配时所分配地址空间的基本单位不同

分段

• 进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名，每个段从0开始编址

• 段号的位数决定了每个进程最多可以分几个段

• 段内地址位数决定了每个段的最大长度是多少

段表

• 为了保证程序能正常运行，就必须能从物理地址找到各个逻辑段存放位置，为此需为每个进程建立一张映射表，简称段表

• 每个段对应一个段表项，其中记录了该段在内存中的起始位置（又称基址）和段的长度

• 各个段表项的长度是相同的

地址转换

1. 根据逻辑地址得到段号、段内地址
2. 判断段号是否越界
3. 查询段表，找到对应的段表项
4. 检查段内地址是否超过段长
5. 计算物理地址
6. 访问目标内存单元

段叶式存储管理

• 分页和分段的结合，先分段再分页

• 段号的位数决定了每个进程最多可以分几个段

• 页号位数决定了每个段最大有多少页

• 页内偏移量决定了页面大小、内存块大小是多少

地址转换

1. 根据逻辑地址得到段号、页号、页内偏移量
2. 判断段号是否越界
3. 查询段表，找到对应的段表项
4. 检查页号是否越界
5. 根据页表存放块号、页号查询页表，找到对应页表项
6. 根据内存块号、页内偏移量得到最终的物理地址
7. 访问目标内存单元

虚拟内存

• 基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。在程序执行过程中，所访问的信息不在内存时，由操作系统将所需信息从外存调入内存，然后继续执行程序。若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。在操作系统的管理下，在用户看来似乎有一个比实际内存大的多的内存，这就是虚拟内存

虚拟内存的特征

• 多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存
• 对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出
• 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际容量

虚拟内存的实现

请求分页式存储管理

缺页中断机构

• 在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断程序处理中断。此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列

  • 如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项
  • 如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。为修改过的页面不用写回外存

• 缺页中断时因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断

地址转换

1. 找到页表项检查页面是否在内存中
2. 若页面不在内存中，需要请求调页
3. 若内存空间不够，还需换出页面
4. 页面调入内存后，需要修改相应页表项

请求分段式存储管理

最佳置换算法（OPT）

• 每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率

• 最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面，操作系统无法提前预判页面访问序列，因此最佳置换算法是无法实现的

先进先出置换算法（FIFO）

• 每次选择淘汰的页面是最早进入内存的页面

Belady异常：当为进程分配的物理块数增大时，缺页次数不减反增的异常现象

• 只有先进先出置换算法会产生Belady异常
• 先进先出置换算法虽然简单，但是该算法与进程实际运行时间规律不适应，因此先进入的页面有可能最经常被访问，因此先进先出置换算法性能最差

最近最久未使用置换算法（LRU）

• 每次淘汰的页面时最近最久未使用的页面

• 最近最久未使用算法虽然性能很好，但是需要专门的硬件支持，实现困难大，开销大

时钟置换算法（CLOCK）

• 时钟置换算法时一种性能和开销较均衡的算法，又称最近未用算法（NRU）

• 为每个页面设置一个访问位，将内存中的页面都通过链接指针链接成一个循环队列，当某页面被访问时，其访问位置为1，当需要淘汰一个页面时，只需要检查页的访问位，如果是0，就选择该页换出，如果1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描

改进型的时钟置换算法

• 简单的时钟置换算法仅考虑到一个页面最近是否被访问过，事实上如果被淘汰的页面没有被修改过，就不需要执行IO操作写回外存，只有被淘汰的页面被修改过，才需要写回外存，因此除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过，在其他条件都相同时，应优先淘汰没有修改过的页面，避免IO操作

算法规则

1. 第一轮扫描，从当前位置开始扫描到第一个(0,0)的帧用于替换
2. 若第一轮扫描失败，进入第二轮扫描，查找第一个(0,1)的帧用于替换，本轮将所有扫描过的帧访问位设为0
3. 若第二轮扫描失败，进入第三轮扫描，查找第一个(0,0)的帧用于替换
4. 若第三轮扫描失败，进入第四轮扫描，查找第一个(0,1)的帧用于替换

页面分配、置换策略

• 驻留集：指请求分页存储管理中给进程分配的物理块的集合

• 固定分配：操作系统为每个进程分配一组固定树木的物理块，在进程运行期间不再改变

  • 即驻留集大小不变

• 可变分配：纤维每个进程分配一定数目的物理块，再进程运行期间，可根据情况做适当的增加或减少

  • 即驻留集大小可变

• 局部置换：当发生缺页时只能选进程自己的物理块进行置换

• 全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程

固定分配局部置换

• 系统为每个进程分配一定数量的物理块，在整个运行期间都不改变，若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面

可变分配全局置换

• 刚开始会为每个进程分配一定数量的物理块，操作系统会保持一个空闲物理块队列，当某进程发生缺页时，从空闲物理块中取出一块分配给该进程，若已无空闲物理块，则可选择一个未锁定的页面换出外存，再将物理块分配给缺页的进程

• 采用这种策略时，只要某进程发生缺页，都将获得新的物理块，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出，被选择调出的页可能时系统中任何一个进程中的页，因此这个被选中的进程拥有物理块会减少，缺页率会增加

可变分配局部置换

• 刚开始会为每个进程分配一定数量的物理块，当某个进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存，如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度，反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块

调入页面策略

预调页策略

• 根据局部性原理，一次调入若干个相邻的页面可能比一次调入一个页面更高效，但如果体现调入的页面中大多数都没被访问过，则又时低效的，因此可以预测不久之后可能访问到的页面，将它们预先调入内存，但目前预测成功率只有50%，故这种策略主要用于进程的首次调入

请求调页策略

• 进程在运行期间发现缺页时才将所缺页面调入内存

调入页面的位置

系统拥有足够的对换区空间

页面的调入、调出都是在内存与对换区之间进行，这样可以保证页面的调入、调出速度很快，在进程运行前，需要将进程相关的数据从文件区复制到对换区

系统缺少足够的对换区空间

• 对于不会被修改的数据，都直接从文件区调入，由于这些页面不会被修改，因此换出时不必写回磁盘，下次需要时再从文件区调入即可
• 对于可能被修改数据，换出时需要写回磁盘对换区，下次需要时再从对换区调入

UNIX方式

• 运行之前进程有关的数据全部放在文件区，故未使用过的页面，都可以从文件区调入，若被使用过的页面需要换出，则写回对换区，下次需要时从对换区调入

抖动现象（颠簸现象）

• 刚刚换出的页面马上又换入内存、刚刚换入的页面马上又换出内存，这种频繁的页面调入行为成为抖动或颠簸

• 产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块

• 引入工作集解决抖动问题

工作集：在某段时间间隔里，进程实际访问页面的集合

文件管理

文件包含的信息（以Windows操作系统为例）

• 文件名：由创建文件的用户决定文件名，主要是为了方便用户找到文件，同一目录下不允许有重名文件

• 标识符：一个系统内的各文件标识符唯一，对用户来说毫无可读性，因此标识符只是操作系统区分各个文件的一种内部名称

• 类型：指明文件的类型

• 位置：对于用户来说是文件存放的路径，对于操作系统来说是文件在外存的地址

• 大小

• 创建时间

• 上次修改时间

• 文件所有者信息

• 保护信息：对文件进行保护的访问控制信息

文件的逻辑结构

无结构文件

• 又称流式文件
• 文件内部的数据就是一系列二进制流或字符流

有结构文件

• 又称记录式文件

• 由一组相似的记录组成，每条记录又由若干个数据项组成，每条记录又一个数据项可作为关键字，作为识别不同记录的编号

• 根据各条记录长度，又可分为定长记录和可变长记录

顺序文件

• 文件中的记录一个接一个地顺序排列，记录可以是定长的或可变长的，各个记录在物理上可以是顺序存储或链式存储

• 串结构：记录之间的顺序与关键字无关

• 顺序结构：记录之间的顺序按关键字顺序排列

链式存储

• 无论是定长还是可变长，都无法实现随机存取，每次只能从第一个记录开始依次往后查找

顺序存储

• 可变长记录：无法实现随机存取，每次只能从第一个记录开始依次往后查找
• 定长记录
  • 可实现随机存取
  • 若采用串结构，无法快速找到某关键字对应的记录
  • 若采用顺序结构，可以快速找到某关键字对应的记录

索引文件

• 建立一个索引表以加快文件检索速度，每条记录对应一个索引项

索引顺序文件

• 索引顺序文件是索引文件和顺序文件思想的结合
• 索引顺序文件中，同样会为文件剑流一张索引表，但索引表并不是每个记录对应一个索引项，而是一组记录对应一个索引项

多级索引顺序文件

• 为顺序文件建立多极索引表

文件目录

• 目录文件中的一条记录就是一个文件控制块（FCB）
• FCB的有序集合称为文件目录
• 一个FCB就是一个文件目录项

目录结构

单级目录

• 单级目录实现了按名村去，但是不允许文件重名

两级目录结构

• 早起的多用户操作系统，采用两级目录结构，分为主目录（MFD）和用户目录（UFD）

• 主文件目录记录用户名及相应用户文件目录的存放位置

• 允许不同用户的文件重名，文件名虽然相同，但是对应的起始是不同的文件

• 两级目录结构允许不同用户的文件重名，也可以在目录上实现访问限制，但是两级目录结构依然缺乏灵活性，用户不能对自己的文件进行分类

多级目录结构

• 又称树形目录结构

• 用户要访问文件时，要用文件路径名标识文件，文件路径名是一个字符串，各级目录之间用/隔开

  • 从根级目录出发的路径称为绝对路径
  • 从当前目录出发的路径称为相对路径

• 树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够高效地进行文件的管理和保护，但树形结构不便于实现文件共享

无环图目录结构

• 在树形目录结构的基础上增加一些指向同一节点的有向边，使整个目录称为一个有向无环图，可以更方便地实现多个用户间的文件共享
  • 共享文件不同于复制的文件，由于各用户指向的同一个文件，因此只要其中一个用户修改了文件数据，那么所有用户都可以看到文件数据的变换
  • 每个共享节点设置一个共享计数器，每次删除操作，计数器减1，当计数器为0时才真正删除节点

索引节点

• 为了提高检索效率，可以创建索引节点表，索引节点表存放文件名和索引节点指针，索引节点指针中存放索引节点，将所有除了文件名以外的信息存放到索引节点

文件块、磁盘块

• 在内存管理中，进程的逻辑地址空间被分为一个个页面，同样地，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个个文件块，于是文件的逻辑地址也可以表示为(逻辑块号,块内地址)的形式

文件的物理结构（文件分配方式）

连续分配

• 每个文件在磁盘上占有一组连续的块

• 优点：支持顺序访问和直接访问（即随机访问），连续分配的文件在顺序访问时速度最快

• 缺点：我呢就不方便文件拓展，存储空间利用率低，会产生磁盘碎片

链接分配

• 链接分配采取离散分配方式，可以为文件分配离散的磁盘块

隐式链接（缺省值）

• 目录中记录了文件存放的起始块号和结束块号

• 优点：方便文件拓展，不会有碎片问题，外存利用率高

• 缺点：只支持顺序访问，不支持随机访问，查找效率低

显式链接

• 目录中只需记录文件起始块号，用于链接文件各物理块的指针显式地存放在一张文件分配表（FAT）中

• 一个磁盘仅设置一张FAT，开机时，FAT的各个表项在物理上连续存储，且每一个表项长度相同，因此物理块号字段可以式隐含的

• 优点：既支持顺序访问，也支持随机访问，由于块号转换的过程不需要访问磁盘，因此相比于隐式链接来说，访问速度快很多，不会产生外部碎片，也可以很方便地对文件进行拓展

• 缺点：文件分配表的需要占用一定的存储空间

索引分配

• 索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块，索引表存放的磁盘块称为索引块，文件数据存放的磁盘块称为数据块

• 优点：支持随机访问，容易实现文件拓展

• 缺点：索引表需要占用一定的存储空间

多级索引

• 建立多层索引，使第一层索引块指向第二层索引块，最后一层索引块指向实际数据

混合索引

• 多种索引分配方式的结合
• 例如一个文件的顶级索引表中，既包含直接地址索引，又包含一级间接索引

存储空间管理

空闲表法

• 适用于连续分配方式

• 分配：可采用首次适应算法、最佳适应算法、最坏适应算法来决定要为文件分配哪个区间

• 回收：

  • 回收区的前后都没有相邻空闲区：在空闲表新增一个表项
  • 会收取的前后都是空闲区：把前后表项和当前表项合并为一个表项
  • 回收区前面是空闲区：把前表项和当前表项合并为一个表项
  • 回收区后面是空闲区：把后表项和当前表项合并为一个表项

空闲链表法

• 操作系统保存着链头、链尾指针

• 空闲盘块链：以盘块为单位组成一条空闲链

  • 分配：从链头开始依次摘下指定个数的盘块分配，并修改空闲链的链头指针
  • 回收：回收的盘块依次挂到链尾，并修改空闲链的链尾指

• 空闲盘区链：以盘区为单位组成一条空闲链

  • 分配：采用首次适应算法、最佳适应算法，从链头开始检索，按照算法规则，找到大小符合要求的空闲盘区，分配给文件，如果没有合适的空闲块，也可以将不同盘区的盘块同时分配给一个文件，不过要注意分配后可能要修改相应的链指针、盘区大小等数据
  • 回收：如果回收和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中，如果回收区没有和任何空闲区相邻，则将回收区作为单独的一个空闲盘区挂到链尾

位示图法

• 连续分配、离散分配都适用

• 位示图：每个二进制位对应一个盘块，可以用(字号,位号)对应一个盘块号

• 分配：

  • 顺序扫描位示图，找到为0的位置
  • 根据字号、位号算出对应的盘块号，将相应盘块分配给文件
  • 将相应二进制位设置为1

• 回收：

  • 根据回收的盘块号计算出对应的字号、位号
  • 将相应二进制位设置为0

成组链接法

• 空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大，UNIX系统中采用成组链接法对磁盘空闲块进行管理

• 文件卷的目录区中专门用一个磁盘块作为超级块，当系统启动时需要将超级块读入内存，并且保证内存与外存中的超级块数据一致

• 超级块：记录下一组空闲盘块数和每个空闲块号

• 分配：检查第一个分组的空闲块数是否足够，如果足够就直接分配

• 回收：

  • 如果下一组空闲盘块数没满，则直接回收一块
  • 如果下一组空闲盘块数满了，则将超级块中的数据复制到新回收的块中，并修改超级块的内容，让心回收的块称为第一个分组

文件的基本操作

创建文件

• 提供的参数
  • 所需的外存空间大小
  • 文件存放路径
  • 文件名

1. 在外存中找到文件所需的空间
2. 根据文件存放路径的信息找到该目录对应的目录文件，在目录文件中创建该文件对应的目录项，目录中包含了文件名、文件在外存中的存放位置等信息

删除文件

• 提供的参数
  • 文件存放路径
  • 文件名

1. 根据文件存放路径找到对应的目录文件，从目录中找到文件名对应的目录项
2. 根据该目录记录的文件在外存的存放位置、文件大小等信息，回收文件占用的磁盘块
3. 从目录中删除文件对应的目录项

打开文件

• 提供的参数
  • 文件存放路径
  • 文件名
  • 对文件的操作类型

1. 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项，并检查用户是否有指定操作的权限
2. 将目录项复制到内存中的打开文件表中，并将对应表目的编号返回给用户，之后用户使用打开文件表的编号来指明要操作的文件

关闭文件

1. 将进程的打开文件表相应表项删除
2. 回收分配给该文件的内存空间等资源
3. 系统打开文件表的打开计数器减1，计数器若结果为0，则删除对应表项

读文件

• 提供的参数
  • 指明文件
  • 指明读入多少数据
  • 指明读入的数据要放在内存中的什么位置

写文件

• 提供的参数
  • 指明文件
  • 指明写入多少数据
  • 写回外存的数据在内存中的什么位置

文件共享

基于索引结点的共享方式（硬链接）

• 由于检索文件时只需要用到文件名，因此可以将除了文件名之外的其他信息放到索引结点中，这样目录项就只需要包含文件名、索引结点指针

基于符号链的共享方式（软链接）

• 并不是把自己的目录项直接指向文件的索引结点，而是创建了一个新的link型文件，link型文件中记录了文件的存放路径，操作系统通过这个文件路径找到共享的文件

文件保护

口令保护

• 为文件设置一个口令，用户请求访问该文件时必须提供口令

• 优点：保存口令的空间开销小，验证口令的时间开销也小

• 缺点：正确的口令存放在系统内部，不够安全

加密保护

• 使用密码对文件进行加密，在访问文件时需要提供正确的密码才能对文件进行正确的解密

• 优点：保密性强，不需要在系统中存储密码

• 缺点：加密解密需要花费一定时间

访问控制

• 在每个FCB中增加一个访问控制表，该表记录了各个用户可以对文件执行哪些操作

文件系统的层次结构

1. 用户接口
2. 文件目录系统
3. 存取验证模块（存取控制验证层）
4. 逻辑文件系统与文件信息缓冲区
5. 物理文件系统
6. 设备管理程序模块
7. 辅助分配模块

磁盘

磁盘

• 磁盘的表面由一些磁性物质组成，可以用这些磁性物质来记录二进制数据

磁盘的物理地址

• 可以用(柱面号,盘面号,扇区号)来定位任意一个磁盘块

扇区的读写

1. 根据柱面号移动磁臂，让磁头指向柱面
2. 激活指定盘面对应的磁头
3. 磁盘旋转的过程中，指定的扇区会从磁头下面划过

磁盘的分类

• 根据磁头分类

  • 固定头磁盘
  • 移动头磁盘

• 根据盘面分类

  • 固定盘磁盘
  • 可换盘磁盘

磁盘调度算法

• 优化移动磁头所画的时间

先来先服务算法（FCFS）

• 根据进程请求访问磁盘的先后顺序进行调度

最短寻找时间优先算法（SSTF）

• 优先处理的磁道是与当前磁头最近的磁道

扫描算法（SCAN）

• 又称电梯算法
• 在最短寻找时间优先算法基础上，只有磁头移动道最外侧磁道的时候才能往内移动，移动到最内侧的时候才能往外移动

LOOK调度算法

• 在扫描算法基础上，如果在磁头移动方向上没有别的请求，就可以立即改变磁头方向

循环扫描算法（C-SCAN）

• 在扫描算法基础上，规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端，不处理任何请求

C-LOOK调度算法

• 在循环扫描算法和LOOK调度算法的基础上，如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回，而且磁头只需要返回到有磁道访问请求的位置即可

延迟时间

• 物理上相邻的扇区在读取过程中，每读完一个扇区，会有一段时间处理数据，此时会错过下一个扇区的读取，只得再转一圈，这再转一圈的时间就是延迟时间

交替编号

• 为了解决延迟时间，可以采用交替编号的策略，让逻辑上相邻的扇区在物理上有一定的间隔，可以使读取连续的扇区所需要的延迟时间更小

错位命名

• 为了解决多盘面间的延迟，可以采用错位命名的策略，让不同盘面的扇区编号错开一位

磁盘初始化

1. 进行低级格式化，将磁盘的各个磁道划分为扇区
2. 将磁盘分区，每个分区由若干柱面组成
3. 进行逻辑格式化，创建文件系统

引导块

• 计算机开机时需要进行一系列的初始化工作，这些初始化工作是通过执行初始化程序（自举程序）完成的

• ROM中只存放很小的自举装入程序，开机时计算机先运行自举装入程序，通过执行该程序就可吵到引导块，并将完整的自举程序读入内存，完成初始化

坏块管理

• 对于简单的磁盘，可以在逻辑格式化时对整个磁盘进行坏块检查，标明哪些扇区是坏扇区

• 对于复杂的磁盘，磁盘控制器会维护一个坏块链表，在磁盘出厂前进行低级格式化时，就将坏块链进行格式化

IO设备

• IO设备就是可以将数据输入道计算机、将计算机的数据输出到外部的设备

设备管理分配

静态分配

• 进程运行前为其分配全部所需资源，运行结束后归还资源

动态分配

• 进程运行过程中动态申请设备资源

设备分配管理的数据结构

设备控制表（DCT）

• 系统为每个设备配置一张设备控制表，用于记录设备情况

设备控制表的字段

• 设备类型
• 设备标识符
• 设备状态
• 指向控制器表的指针
• 重复执行次数或时间
• 设备队列的队首指针

控制器控制表（COCT）

• 每个设备控制器都会对应一张控制器控制表，操作系统根据控制器控制表的信息对控制器进行操作和管理

控制器控制表的字段

• 控制器标识符
• 控制器状态
• 指向通道表的指针
• 控制器队列的队首指针
• 控制器队列的队尾指针

通道控制表（CHCT）

• 每个通道都会对应一张通道控制表，操作系统根据通道控制表的信息对通道进行操作和管理

通道控制表的字段

• 通道标识符
• 通道状态
• 与通道连接的控制器表首地址
• 通道队列的队首指针
• 通道队列的队尾指针

系统设备表（SDT）

• 记录了系统中全部设备的情况，每个设备对应一个表目

系统设备表的字段

• 表目
  • 设备类型
  • 设备标识符
  • 设备控制表（DTC）
  • 驱动程序入口

设备分配的步骤

1. 根据进程请求的物理设备名查找SDT
2. 根据SDT找到DCT

• 设备忙碌，则将进程PCB挂到设备等待队列中
• 设备不忙碌，则将设备分配给进程

3. 根据DCT找到COCT

• 控制器忙碌，则将进程PCB挂到控制器等待队列中
• 控制器不忙碌，则将控制器分配给进程

4. 根据COCT找到CHCT

• 通道忙碌，则将进程PCB挂到通道等待队列中
• 通道不忙碌，则将通道分配给进程

设备分配步骤的改进

1. 根据进程请求的逻辑设备名查找SDT
2. 查找SDT，找到用户进程指定类型的、并且空闲的设备，将其分配给该进程，操作系统在逻辑设备表中新增一个表项
3. 根据DCT找到COCT

• 控制器忙碌，则将进程PCB挂到控制器等待队列中
• 控制器不忙碌，则将控制器分配给进程

4. 根据COCT找到CHCT

• 通道忙碌，则将进程PCB挂到通道等待队列中
• 通道不忙碌，则将通道分配给进程

缓冲区

• 缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可以用内存作为缓冲区
  • 使用硬件作为缓冲区的成本较高，容量也较小，一般仅用在对速度要求非常高的场合
  • 一般情况下使用内存作为缓冲区

缓冲区管理策略

单缓冲

• 若采用单缓冲的策略，操作系统会在主存中为其分配一个缓冲区

当缓冲区数据非空时，不能往缓冲区冲入数据，只能从缓冲区把数据传出
当缓冲区为空时，可以往缓冲区冲入数据，但必须把缓冲区充满以后，才能从缓冲区把数据传出

双缓冲

• 若采用双缓冲策略，操作系统回在主存中为其分配两个缓冲区

循环缓冲区

• 将多个大小相等的缓冲区链接成一个循环队列

缓冲池

• 缓冲池由系统中共用的缓冲区组成

• 按使用状况可以分为

  • 空缓冲队列
  • 装满输入数据的缓冲队列（输入队列）
  • 装满输出数据的缓冲队列（输出对垒）

• 按实际运算中扮演的功能可以分为

  • 用于收容输入数据的工作缓冲区（hin）
  • 用于提取输入数据的工作缓冲区（sin）
  • 用于收容输出数据的工作缓冲区（hout）
  • 用于提取输出数据的工作缓冲区（sout）

I/O控制器

• I/O设备的机械部件主要用来执行具体I/O操作
• I/O设备的电子部件通常是一块插入主板扩充槽的印刷电路板

I/O控制器的组成

• CPU与控制器的接口
• I/O逻辑
• 控制器与设备的接口

I/O控制方式

程序直接控制方式

• CPU干预的频率：很频繁，I/O操作开始之前、完成之后需要CPU介入，并且在等待I/O完成的过程中CPU需要不断地轮询检查

• 数据传送的单位：每次读写1个字

• 数据的流向

  • 读操作（数据输入）：I/O设备->CPU->内存
  • 写操作（数据输出）：内存->CPU->I/O设备

• 主要优缺点

  • 优点：实现简单
  • 缺点：CPU和I/O设备只能串行工作，CPU需要一直轮询检查，长期处于忙等状态，CPU利用率低

中断驱动方式

• CPU干预频率：每次I/O操作开始之前、完成之后需要CPU介入。等待I/O完成的过程中CPU可以切换到别的进程执行

• 数据传送的单位：每次读写一个字

• 数据的流向

  • 读操作（数据输入）：I/O设备->CPU->内存
  • 写操作（数据输出）：内存->CPU->I/O设备

• 主要优缺点

  • 优点：与程序直接控制相比，在中断驱动方式中。I/O控制器回通过中断信号主动报告I/O已完成，CPU不再需要不停地轮询。CPU和I/O可并行工作，CPU利用率得到明显提升
  • 缺点：每个字在I/O与内存之间的传输，都需要经过CPU，而频繁的中断处理会消耗较多的CPU时间

直接存储区存取方式（DMA方式）

• CPU干预的频率：仅在传送一个货多个数据块的开始和结束时，才需要CPU干预

• 数据传送的单位：每次读写一个或多个连续块

• 数据的流向

  • 读操作（数据输入）：I/O设备->内存
  • 写操作（数据输出）：内存->I/O设备

• 主要优缺点

  • 优点：数据传输以块为单位，CPU介入频率进一步降低。数据的传输不再需要先经过CPU再写入内存，数据传输效率进一步增加。CPU和I/O设备的并行性得到提升
  • 缺点：CPU每发出一条I/O指令，只能读写一个或多个连续的数据块。如果需要读写多个离散存储的数据块，或者要将数据分别写到不同的内存区域时，CPU要分别发出多条I/O指令，进行多次中断处理才能完成

通道控制方式

• CPU干预的频率：极低，通道会根据CPU的指示执行响应的通道程序，只有完成一组数据块的读写后才需要发出中断信号，请求CPU干预

• 数据传送的单位：每次读写一组数据块

• 数据的流向

  • 读操作（数据输入）：I/O设备->内存
  • 写操作（数据输出）：内存->I/O设备

• 主要优缺点

  • 优点：CPU、通道、I/O设备可并行工作，资源利用率很高
  • 缺点：实现复杂，需要专门的通道硬件支持

完成

参考文献

哔哩哔哩——王道论坛