操作系统引论

操作系统定义

操作系统是一组控制和管理计算机软硬件资源、合理地对各类作业进行调度以及方便用户使用的程序集合。

操作系统是位于硬件层之上，所有其它系统软件层之下的一个系统软件，使得管理系统中的各种软件和硬件资源得以充分利用，方便用户使用计算机系统。

操作系统的目标

1. 方便性
2. 有效性
3. 开放性
4. 可扩充性

操作系统的作用

1. 用户与计算机硬件系统之间的接口处理机
2. 计算机资源的管理者
3. 扩充裸机资源的软件
4. 计算机工作流程的组织者

无操作系统时的计算机系统

• 人工操作方式
  特点：无任何软件、独占性、串行性
  缺点：用户独占全机，CPU等待人工操作
  待解决的问题：人机矛盾，CPU和I/O设备速度不匹配
  解决：脱机I/O、批处理
• 脱机输入输出方式
  解决了CPU和设备之间不匹配的矛盾

单道批处理系统

在内存中仅存一道作业区运行，运行结束 或出错，才自动调整另一道作业运行

1. 自动性
2. 顺序性
3. 单道性

优点：减少人工操作，解决了作业的自动接续
缺点：平均周转时间长，没有交互能力

多道批处理系统

在内存中存放多道作业运行，运行结束或出错，自动调度内存中的另一道作业运行

1. 多道性
2. 调度性
3. 无序性

优点：提高了CPU的利用率，提高内存和I/O设备利用率，增加系统吞吐率
缺点：平均周转时间长，没有交互能力

分时系统

1. 多路性
2. 独立性
3. 及时性
4. 交互性

产生原因：用户需要人机交互、共享主机，便于用户上机
实现方法：简单分时系统，前后台分时系统，多道分时系统

实时系统

计算机及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时设备和实时任务协调一致的运行

1. 多路性
2. 独立性
3. 及时性
4. 交互性
5. 可靠性

操作系统的基本特征

1. 并发（最重要的特征）
2. 共享（和并发同为操作系统最基本的特征，二者互为存在的条件）
3. 虚拟（以并发和共享为前提）
4. 异步（并发和共享的必然结果）

操作系统的功能

1. 处理机管理
2. 存储器管理
3. 文件管理
4. 设备管理
5. 提供友好的用户接口

处理机管理

主要是对处理机的分配和运行进行管理

1. 进程控制
2. 进程同步
3. 进程通信：共享存储器、消息、管道等。
4. 进程调度

存储器管理

主要是对多道程序的运行提供良好的环境

1. 内存分配
2. 内存保护
3. 地址映射
4. 内存扩充

设备管理

主要是完成用户的I/O请求

1. 缓冲管理
2. 设备分配
3. 设备处理

文件管理

主要是希望用户能方便、安全地使用各种信息资源

1. 文件存储空间的管理
2. 目录管理
3. 文件的读写管理和保护

提供友好的用户接口

主要是方便用户使用计算机

1. 命令接口
2. 程序接口
3. 图形用户接口

操作系统的结构设计

1. 整体式系统（无结构操作系统）
   缺陷：① 设计出的操作系统既庞大又杂乱，缺乏清晰的程序结构。 ② 编制出的程序错误很多，给调试工作带来很多困难；增加了维护人员的负担
2. 模块化结构
   优点：① 提高了OS设计的正确性、可理解性和可维护性。② 增强了0S的可适应性。 ③ 加速了OS的开发过程。
   缺点：① 对模块的划分及对接口的规定要精确描很困难 。 ② 从功能观点来划分模块时，未能将共享资源和独占资源加以区别；
3. 分层式结构
   每一层实现一组基本概念及其相关的基本属性，各层实现不依赖其以上各层所提供的概念及其属性，只依赖其直接下层所提供的概念及属性，每一层对其上各层隐藏其下各层的存在
4. 微内核结构
   优点：① 增强了系统的可扩展性 ② 增强了系统的可靠性，可移植性好 ③ 提供了对分布式系统的支持
   缺点：运行效率有所降低（消息传递开销+模式切换开销）

进程管理

程序的顺序执行

1. 顺序性
2. 封闭性
3. 可再现性

程序的并发执行

1. 间断性
2. 失去封闭性
3. 不可再现性

应用级并发是指若干应用程序的并发执行。
系统级并发是指操作系统自身软件的并发执行。

进程

引入进程的目的是为了使程序正确地并发执行
特征：
1. 结构特征
2. 动态性（基本特征）（程序是静态的）
3. 并发性
4. 独立性
5. 异步性

定义：
进程是进程实体的运行过程，它是系统进行资源分配和调度的一个独立单位。

为使程序（含数据）能独立运行，应为之配置一个专门的数据结构即进程控制块（PCB）
由程序段、相关的数据段和PCB三部分便构成了进程实体
创建进程 ，实质上是创建进程实体中的PCB；撤消进程 ，实质上是撤消进程的PCB

进程状态

1. 就绪
2. 执行
3. 阻塞
4. 挂起

进程状态转换

就绪 - 运行：进程调度
运行 - 就绪：高优先级任务抢占，时间片用完
运行 - 阻塞：I/O请求，等待资源/事件
阻塞 - 就绪：I/O完成，得到资源/触发事件
阻塞 - 挂起：终端用户请求，父进程请求，负荷调节需要，操作系统需要
挂起 - 就绪：**原语

特殊状态:
静止就绪，静止阻塞（上述的挂起）。
活动就绪/执行挂起得到静止就绪，静止就绪通过**原语得到活动就绪。
静止阻塞通过**原语得到活动阻塞，静止阻塞通过释放得到静止就绪。
状态转换

进程控制块

为使程序（含数据）能独立运行，应为之配置一个专门的数据结构即进程控制块（PCB）
PCB是进程存在的唯一标志

通常包含下列信息：
1. 进程标识符：内部标识符，外部标识符
2. 处理机状态：通用寄存器、PC、PSW、SP
3. 进程调度和控制信息

PCB的常用组织形式：线性方式、链接方式和索引方式。

进程同步

基本概念

1. 临界资源：一次仅允许一个进程访问的资源
2. 临界区：访问临界资源的那段代码

用来实现互斥的同步机制的准则

1. 空闲让进
2. 忙则等待
3. 有限等待
4. 让权等待

实现机制

1. 信号量机制
2. 管程

信号量机制

类型：
1. 整型信号量
2. 记录型信号量
3. AND型信号量（要么全部分配到进程，要么一个也不分配）
4. 信号量集（在每次分配时，采用信号量集来控制，可以分配多个单位的资源）

应用：
1. 用于实现前趋关系
2. 用于实现互斥

管程

管程是由一组局部的变量对局部变量进行操作的一组过程以及对局部变量进行初始化的语句序列构成的一个软件模块，它可用来实现进程同步。

进程通信

• 低级通信：进程之间的互斥和同步，由于其所交换的信息量少而被归结为低级通信
• 高级通信：是指用户可直接利用操作系统所 提供的一组通信命令高效地传送大量数据的 一种通信方式

进程通信的类型

常用的高级进程通信机制：
1. 共享存储器系统
（基于共享数据结构/共享存储区）
2. 消息传递系统
直接通信方式：对称寻址方式，非对称寻址方式
间接通信方式：信箱，消息缓冲队列通信机制
3. 管道通信
4. 客户机–服务器系统
套接字，远程过程调用和远程方法调用

线程

进程的两个特点：资源所有权，调度/执行。调度和分派的部分通常称为线程或轻便进程，而资源所有权的部分通常称为进程。

属性：
1. 轻型实体
2. 独立调度和分派的基本单位
3. 可并发执行
4. 共享进程资源

多线程OS中的进程属性：(1) 作为系统资源分配的单位。 (2) 可包括多个线程。 (3) 进程不是一个可执行的实体。

分类：
1. 用户级线程，用户级线程在用户空间实现，无需得到内核的支持，调度算法由线程库提供。
2. 内核支持线程，内核支持线程的TCB被它的保存在核心空间中，它的运行需获得内核的支持。
3. （用户级线程和核心级线程的结合，LWP）

内核支持线程

即无论 是用户进程中的线程，还是系统进程中的线程，他们 的创建、撤消和切换等，是依靠内核实现的。
在内核空间中为每一个内核支持线程设置了一个线 程控制块TCB，内核是根据该控制块而感知某线程的 存在的，并对其加以控制

优点

(1) 在多处理器系统中，内核能够同时调度同一进程中多 个线程并行执行；
(2) 如果进程中的一个线程被阻塞了，内核可以调度该进 程中的其它线程占有处理器运行，也可以运行其它进程 中的线程；
(4) 内核本身也可以采用多线程技术，可以提高系统的执 行速度和效率。

缺点

对于线程切换而言，其模式切换的开销较大，在同一个进程中，从一个线程切换到另一个线程时 ，需要从用户态转到内核态进行，这是因为用户进程的线程在用户态运行，而线程调度和管理是 在内核实现的，系统开销较大。

实现

在仅设置了内核支持线程的OS中，一种可能的线程控制方法是，系统在创建一个新进程时，便为它分配 一个任务数据区PTDA（Per Task Data area),其中包括若干个线程控制块TCB空间

用户级线程

用户级线程仅存在于用户空间中。对于这种线程的创建、撤消、线程之间的同步与通信等功能，都无须内核来实现。

• 由应用程序完成所有线程的管理
  通过线程库(用户空间)：一组管理线程的函数线程库来 提供一个线程运行管理系统（运行系统）
• 内核不知道线程的存在
• 线程切换不需要核心态特权
• 调度算法可以是进程专用的

优点

线程切换不调用内核
调度是应用程序特定的：可以选择最好的算法
可运行在任何操作系统上（只需要线程库），可以在一 个不支持线程的OS上实现

缺点

大多数系统调用会引起进程阻塞，并且是进程中所有线 程将被阻塞
内核只将处理器分配给进程，同一进程中的两个线程不 能同时运行于两个处理器上

实现

所有用户级线程都具有相同的数据结构，它们都运行在一个中间系统上
（1）运行时系统
是用于管理和控制线程的函数的集合，又称为线程库。
（2）内核控制线程

线程的同步

这种线程又称为轻型进程LWP（Light Weight Process ）
1. 互斥锁
2. 条件变量
3. 信号量机制

使用线程的优点

1. 在一个已有进 程 中 创 建 一 个 新 线 程 比 创 建 一 个全新进程所需的时间少。
2. 终止一个线程比终止一个进程花费的时间少 。
3. 线程间切换比进程间切换花费的时间少。
4. 线程提高了不同的执行程序间通信的效率 。同一个进程中的 线程共享存储空间和文件，它们无需调用内核就可以互相通信。

进程同步经典问题

处理机调度和死锁

调度的目标：
1、提高处理机的利用率
2、提高系统吞吐量
3、尽量减少进程的响应时间
4、防止进程长期得不到运行

调度方式和算法的选择，取决于操作系统的类型及其目标。

选择准则（面向系统）：
1. 系统吞吐量
2. 处理机利用率
3. 各类资源的平衡利用

选择准则（面向用户）：
1. 周转时间
2. 响应时间
3. 截止时间的保证
4. 优先权原则

三级调度

高级调度

又称为作业调度或长程调度，作业（JOB）是用户在一次算题过程中或一次事务处理中，要求计算机系统所做的工作的集合 。

批处理系统需要有作业调度，分时和实时系统无需此调度

多道程序度：即允许多少个作业同时在内存中运行。
周转时间：从作业被提交给系统开始，到作业完成为 止的这段时间间隔。
吞吐量：是指在单位时间内系统所完成的作业数

中级调度

它按一定的算法将外存中已具备运行条件的进程换入内存，而将内存中某些处于阻塞状态的某些进程换出至外存（阻塞->挂起）。

中级调度的目的是为了解决内存紧张问题。

低级调度

又称为进程调度或短程调度。是最基本的调度，在三种类型的操作系统中都必须配置它。（批处理、分时和实时）
分为：
1. 非抢占方式
2. 抢占方式，原则：1）优先权原则 2）短作业优先原则 3）时间片原则

三个基本原则：
（1）排队器
（2）分派器（调度程序）
（3）上下文切换机制

低级调度的功能：
(1)按某种算法选取进程（调度）。
(2)保存处理机的现场信息（上下文切换第一步骤）
(3) 把处理器分配给进程（上下文切换第二步骤）

调度算法

先来先服务-FCFS

按照作业/进程进入系统的先后次序，遵循先进入系统者先调度。
优点：
1. 有利于长作业/进程
2. 有利于CPU繁忙型作业/进程

缺点：
1. 不利于短作业/进程，尤其是来的较晚的短作业/进程
2. 不利于I/O繁忙型作业/进程

用于批处理系统，不适于分时系统

短作业/进程优先算法-SJF/SPF

按照运行时间长短进行调度，运行时间越短越优先调度。不可抢占。
优点：
1. 能有效降低作业/进程的平均等待时间
2. 提高系统的吞吐量

缺点：
1. 不利于长作业/进程
2. 未考虑作业/进程紧迫程度，不能保证紧迫作业/进程被及时处理
3. 运行时间无法准确估计，不能真正保证短作业/进程优先
4. 无法实现人机交互

高优先权优先算法-HPF

分类：
1. 静态优先权，简单易行，开销小，但是不够精确，还可能导致低优先权作业/进程长期得不到调度
2. 动态优先权，更好的调度性能，可防止长作业/进程长期垄断处理机

高响应比优先调度算法-HRRN

响应比/优先权=等待时间+要求服务时间要求服务时间=响应时间要求服务时间响应比/优先权=等待时间+要求服务时间要求服务时间=响应时间要求服务时间

此处的要求服务时间，准确来说是指剩余的需要服务的时间。

HRRN是介于FCFS和SJF/SPF之间的一种这种算法，相比于SJF/SPF有着更低的吞吐量和更高的系统开销。

对短作业有利，一定程度上是先来先服务，也对长作业有利，但由于计算响应比，会增加系统开销。

时间片轮转算法-RR

系统将所有就绪进程按先来先服务原则排成队列。
就绪进程直接置于队尾，若此时正处于某一进程的时间片，该进程是位于队首的

多级反馈队列调度算法-FB

原理：
1. 设置多个就绪队列，并为各个队列赋予不同的优先级
2. 一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度
3. 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行

调度过程：
1. 按优先级由高到低设置多个队列RQ0 ，RQ1 … RQn ，高优先级队列时间片小
2. 刚进入系统的进程按FCFS放入最高的RQ0中
3. 进程一次时间片没执行完，就降至下一级队列，以此类 推，降至最低优先级队列后，一直在此队列中不再下降
4. 系统优先调度高优先级队列中的进程，仅当RQ0 空闲时才调度RQ1 队列进程，以此类推
5. 如果是抢占式，当前时间片未用完时有进程进入高优先级队列时，将当前进程置于其所在队列的末尾，而后开始执行高优先级队列的时间片

实时调度

常用的调度方式：
1. 非抢占式轮转调度方式
2. 非抢占式优先权调度方式
3. 抢占式调度优先权调度方式
4. 立即抢占的优先权调度方式
由上往下，响应时间数量级逐个降低，要求更为严格，所需资源也更多。

常用的高优先权优先的实时调度算法：
1. 最早截止时间优先算法-EDF，截止时间越早越优先。
2. 最低松弛度优先算法-LLF，松弛度：截止时间-剩余所需时间-当前时间，主要用于可抢占调度方式，当松弛度为0时，必须立即抢占CPU。

产生死锁的原因

1. 竞争资源
2. 进程推进顺序非法

m个同类资源被n个进程共享，设一个进程最多可以请求多x个资源
m > n * (x-1) 时，系统不会发生死锁。

产生死锁的必要条件

1. 互斥条件
2. 请求与保持条件
3. 不剥夺条件
4. 环路等待条件

处理死锁的基本办法

预防死锁

破坏死锁必要条件的后三者之一，互斥条件因为一些资源固有特性的限制，难以破坏，对于打印机这样的设备可以通过SPOOLing技术对互斥条件予以破坏。
1. 破坏“请求与保持”条件，规定所有进程都必须一次性申请运行过程所需的全部资源，会造成资源浪费严重和更多更久的进程阻塞。
2. 破坏“不剥夺”条件，规定一个已经保持了某些资源的进程，在提出新的资源请求而不能立即得到满足时，必须释放它已经获得的所有资源，方法实现复杂且开销大。
3. 破坏“环路等待“条件，将系统资源按类型赋予不同的序号，当进程要获取多种资源时必须按序号逐个获取资源。会限制新设备类型的增加，由于有些进程使用资源的顺序与规定的顺序不同，会造成资源的浪费。

避免死锁

将系统状态分为安全状态和不安全状态，安全状态一定不会产生死锁，不安全状态可能会产生死锁。
允许进程动态申请资源，系统分配资源前进行安全性检查，若分配会导致系统进入不安全状态，则不予以分配。

银行家算法，根本思想：当某个进程提出资源请求，并请求资源小于等于它实际所需资源时，检查是否存在一条路径可以在资源分配后，剩余的进程仍然可以完全结束。
数据结构：
1. 可用资源向量 Available
2. 最大需求矩阵Max
3. 分配矩阵Allocation
4. 需求矩阵Need
5. 工作向量work
6. 工作向量Finish

死锁的检测与解除

系统定时进行死锁的检测，当判明将发生死锁或已经发生死锁时，进行死锁的解除。

死锁的检测：
1. 判断的现有的资源能否让现有的进程全部正常结束，不能则认为将发生死锁。
2. 周期性检测进程阻塞时间，当其超过某一时间后，认为该进程为死锁进程。

死锁的解除：
1. 剥夺资源
2. 撤销进程

存储器管理

三级存储：
1. 高速缓存cache
2. 内存RAM
3. 磁盘

五级存储：
1. 寄存器
2. 高速缓存
3. 内存
4. 磁盘缓存
5. 磁盘

存储分配的三种方式：
1. 直接指定
2. 静态分配方式
3. 动态分配方式

程序的装入

1. 绝对装入方式
   编译程序产生实际存储地址（绝对地址）的目标模块
   逻辑地址与实际内存地址完全相同
2. 可重定位装入方式
   重定位（地址映射/地址变换），根据地址变换进行的时间及采用技术手段不同，分为：
3. 静态重定位
   地址变化在装入内存时一次完成，优点：不需要硬件支持，可以装入有限多道程序。缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动，不易实现共享。
4. 动态重定位
   地址变换在程序执行时进行，在硬件地址变换机构的支持下，对每条指令或数据的访问自动进行地址变换。优点：主存使用更加灵活，几个作业共享一个程序段的单个副本比较容易，可以向用户提供一个比主存的存储空间大得多的地址空间而用户无需考虑覆盖结构。缺点：需要附加硬件支持，实现存储器管理的软件比较复杂。
5. 动态运行时装入方式

程序的链接

1. 静态链接
2. 装入时动态链接
3. 运行时动态链接

运行时动态链接是目前最常使用的链接方式

存储器管理的目的

1. 主存储器的分配和管理
2. 提高主存储器的利用率
3. “扩充”主存容量
4. 存储保护

存储器保护

1. 自动地址修改
2. 0页，1页寻址
3. 界限寄存器

连续分配方式

1. 单一连续分配方式
2. 分区式分配方式
3. 可重定位分区分配

单一连续分配方式

内存中仅驻留一道用户程序，整个用户区为一个用户独 占。 ?内存分为两个区域：系统区，用户区。
应用程序装入到用户区，可使用用户区全部空间。

分区式分配方式

算法复杂，回收分区时系统开销大。
1. 固定分区分配
（1）分区大小不等（2）分区大小相等
建立分区说明表，内存分配程序检索分区说明表，找出合适分区后修改分区状态。
优点：易于实现，开销小
缺点：内碎片造成浪费，分区总数固定，限制了并发执行的程序数目，存储空间的利用率太低。
2. 动态分区分配
1. 分区数目固定
2. 分区数目大小均不固定

数据结构：空闲分区表 / 空闲分区链

分区分配算法

基于顺序搜索：
1. 最佳适应算法
2. 最坏适应算法
3. 首次适应算法
4. 循环首次（下次）适应算法

基于索引搜素：
1. 快速适应算法
2. 伙伴系统

最佳适应算法

总是寻找其大小最接近作业所要求的存储区域。即使作业放入后剩下的零头最小。

优点：
遇到大作业到来时，作业要求的存储区域就比较容易得到满足。
缺点：
产生空白区较多，且空白区较小无法使用（可干脆将整个区域划分给申请的作业。
回收分区时插入到合适的位置较为费时。

为了加快查找速度，应将存储空间中所有的空白 区按其大小递增的顺序链接起来，组成一空白区链 (Free List)。

最坏适应算法

它在为作业选择存储区域时，总是寻找最大的空白区。在划分后剩下的空白区也是最大的，因而对以后的分配很可能仍然是有用的，这是该算法的一个优点。

但是，由于最大的空白块总是首先被分配而进行划分，当有大的作业时，其存储空间的申请往往得不到满足，这是该算法的一个缺点。

为了支持这个算法的实现，空白块应以大小递减的顺序链接起来。

首次适应算法

每个空白区按其在存储空间中地址递增的顺序链在 一起，即每个后继空白区的起始地址总是比前者的 大。在为作业分配存储区域时，从这个空白区链的 始端开始查找，选择第一个足以满足请求的空白块， 而不管它究竟有多大。
这个选择的空白区被分成两部分。 一部分与请求的大小相等，分配给作业；剩下的部分留在空白区链中。显然，这个算法倾向于优先利用存储空间中低址部分的空白区。

优点：
算法简单，查找速度快，大作业到来时也比较容易得到满足

缺点：
会留下较多无法使用的空白区，存储空间利用率不高。较小空白区集中在前端，较大空白区在尾端，导致找到合适的空白区的速度降低。

下次适应算法

我们把存储空间中空白区构成一个循环链。每次为存储请求查找合适的分区时，总是从上次查找结束的地方开始，只要找到一个足够大的空白区，就将它划分后分配出去。

优点：存储空间的利用更加均衡。

快速适应算法

将空闲分区根据其容量大小进行分类，对于每一 类具有相同容量的所有空闲分区，单独设立一个空闲分区链表。

在内存中设立一张管理分区类型，并记录 了该类型空闲分区链表表头的索引表，该表的每一个表项记录了对应类型空闲分区链表表头的指针。

在内存中设立一张管理分区类型，并记录了该类型空闲分区链表表头的索引表，该表的每一个表项记录了对应类型空闲分区链表表头的指针。

优点：
查找效率高。
该算法在进行空闲分区分配时，不会对任何分区产生 分割，所以能保留大的分区，满足对大空间的需求， 也不会产生内存碎片。（外碎片）

缺点：
在分区归还主存时算法复杂，系统开销较大。
该算法在分配空闲分区时是以进程为单位，一个分区 只属于一个进程，因此在为进程所分配的一个分区中 ，或多或少地存在一定的浪费。空闲分区划分越细， 浪费则越严重。（内碎片）

伙伴系统

进程请求大小为n的存储空间时，
首先计算一个 i 值，使 2 i－1 < n ≤ 2 i ；
在空闲分区大小为 2 i 的空闲分区链表中查找。 if 找到，即把该空闲分区分配给进程。 else 在分区大小为2 i＋1 的空闲分区链表中寻找; //表明长度为2 i 的空闲分区已经耗尽 if 找到大小为2 i＋1 的空闲分区 把该空闲分区分为相等的两个分区（一对伙 伴），其中一个用于分配，另一个加入分区大 小为 2 i 的空闲分区链表中。 else 查找大小为2 i＋2 的空闲分区……

哈希算法

利用哈希快速查找的优点，以及空闲分区在可利 用空间表中的分布规律，建立哈希函数，构造一 张哈希表，以空闲分区大小为关键字，每一个表 项记录了一个对应的空闲分区链表表头指针。

当进行空闲分区分配时，根据所需空闲分区大小， 通过哈希函数计算，即得到在哈希表中的位置， 从中得到相应的空闲分区链表，实现最佳分配策 略。

可重定位分区分配

紧凑

解决零头问题的办法，将内存中的所有作业进行移动，使它们全都相邻接，这样，可把原来分散的多个小分区合成一个大分区。这种技术称为存储器的“紧凑”。

动态重定位

在动态运行时装入的方式中，作业装入内存后的所有地址都仍然是相对地址，将相对地址转换为物理地址的工作，被推迟到程序指令要真正执行时进行。

动态重定位分区分配法是利用分区的“拼接”(对空白区而言)或“紧凑”(作业程序而言)技术 解决“零头”。

对换

对换指把内存中暂不能运行的进程或暂时不用和程序和数据，换到外存上，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的程序和数据，换入内存。

对换是系统行为，是提高内存的利用率的有效措施。
- 整体对换（进程对换）
- 页面对换（分段对换）

为实现对换，系统需要三方面的功能：
对换空间的管理
进程的换入
换出

对换空间的管理

外存被分为两部分， 文件区和对换区，文件区用于存放文件，它采取离散分配方式。 对换（续） 即一个文件可根据当前外存的使用情况 ， 被分成多块 ，分别存储到不邻接的多个存储区域中 ，用指针相连。 对换区存放从内存换出的进程 ，它们在外存的存放时间较短，换入 、换出频繁。对对换区的管理，采用连续分配方式 。

分配算法可以是首次适应算法、循环首次适应算 法和最佳适应算法。

进程的换出和换入

1、换出（swap out）
①选择：首先选择阻塞或睡眠状态的进程，若有多个，按优先级由低到高进行选择。若没有此状态进程，则选择就绪状态的，仍然按优先级由低到高进行选择。
②为避免某进程被频繁的换入换出，还应考虑进程在内存中的驻留时间，优先选择驻留时间长的进程。

2、换入（swap in）
①从 PCB集合中查找“就绪且换出”的进程，有多个，则选择换出时间最长的。
②根据进程大小申请内存，成功则读入，否则要先执行换出，再换入。
③若还有可换入进程，则转向①。直至无“就绪且换出”进程或无法获得足够内存空间为止。

离散分配方式

程序在内存中不一定连续存放。

1）离散的基础
? 分页(Pages)：将程序地址空间分页
? 分块(Frames)：将内存空间分块
2）离散分配的体现
? 内存一块可以装入程序一页
? 连续的多个页不一定装入连续的多个块中 ?
注：系统中页块的大小是不变的。

根据离散时的基本单位不同，可分为三种：
分页存储管理
分段存储管理
段页式存储管理

优点：没有外零头，仅有小于一个页面的内零头

分页存储管理

注意：
页面或页，是逻辑空间的概念
物理块或页框，是内存空间/物理空间的概念

页表，每个进程对应 1 个页表，描述该进程的各页面在内存中对应的物理块号。 包括页号、物理块号，存放在主存的系统专用区。（ 平时存于PCB中，要运行时才装入PTR中）

作业表，整个系统1张，记录作业的页表情况，包含进程号、页表长度、页表始址等信息。

空闲块表，整个系统1张，记录主存当前空闲块。

Δ" role="presentation" style="box-sizing: border-box; position: relative;">ΔΔ地址变换过程（非快表）

（1）根据逻辑地址,计算出页号和页内偏移量；
（2）从PTR中得到页表首址，然后检索页表，查找指定页面对应的页框号；
（3）用页框号乘以页面大小获得其对应的起始 地址，并将其送入物理地址的高端。
（4）将页内偏移量送入物理地址低端，形成完整的物理地址。

快表

为了提高地址变换速度，为进程页表设置一个专用的高速缓冲存储器，称为快表 TLB(Translation Lookaside Buffer)，或联想存储器（Associative Memory）。专门保存当前进程最近访问过的一组页表项。

Δ" role="presentation" style="box-sizing: border-box; position: relative;">ΔΔ地址变换过程（快表）

根据逻辑地址中的页号 ， 查找快表中是否存在对应的页表项。
若快表中存在该表项，称为命中（hit），取出其中的页框号， 加上页内偏移量 ，计算出物理地址。
若快表中不存在该页表项 ， 称为命中失败 ， 则再查找页表， 找到逻辑地址中指定页号对应的页框号。 同时， 更新快表， 将该表项插入快表中。并计算物理地址.

访问内存的有效时间 EAT

定义：从进程发出指定逻辑地址的访问请求，经过地址变换，再到内存中找到对应的物理单元并取出数据，所花费的总时间。

多级页表

存储大页表，① 采用离散分配方式来解决难以找到一块连续的大内存空间的问题，（即引入两级页表），② 只将当前需要的部分页表项调入内存， 其余的 页表项仍驻留在磁盘上，需要时再调入。

对于要求连续的内存空间来存放页表的问题：

可将页表进行分页，并离散地将各个页面分别存放在不同的物理块中，

同样也要为离散分配的页表再建立一张页表，称为外层页表(Outer Page Table)，在每个页表项中记录了页表分页的物理块号。

反置页表

（1）IPT是为主存中的每一个物理块建立一个页表项并按照块号排序；
（2）该表每个表项包含正在访问该物理块的进程标识、页号及特征位,用来完成主存物理块到访问进程的页号的转换。

地址转换过程（反置页表）

逻辑地址给出进程标识和页号,用它们去比较 IPT, 若整个反 置 页表中未能找到匹配的页表项 , 说明该页不在主存, 产生请求调 页中断 , 请求操作系统调入;否则，该表项的序号便是物理块号,块号加上位移，便形成物理地址。

Δ" role="presentation" style="box-sizing: border-box; position: relative;">ΔΔ分页存储管理的优点

• 减少碎片
• 程序不必连续存放，便于装入
• 便于管理
• 能实现动态链接

分页存储管理的缺点

• 程序必须全部装入内存，才可以运行
• 操作系统必须为每一个任务都维护一张页面，开销比较大，简单的页面结构已经不能满足要求，必须设计更复杂的结构，如：多级页表结构、哈希页表结构、反置页表

分段式存储管理

1. 方便编程
   模块化程序设计的分段结构
2. 分段共享
   段是信息的逻辑单位，可以为共享过程建立一个独立的段，更便于实现程序和数据的共享。
3. 分段保护
   对内存中的信息的保护，同样也是对信息的逻辑单位进行保护。
   采用分段存储管理，对实现保护，将是更有效和方便。
4. 动态链接
   程序运行时，先将主程序所对应的目标程序装入内存并启动运行，当运行过程中又需要调用某段时，才将该段调入内存并进行链接。
5. 动态增长
   在实际使用中，往往有些段，特别是数据段会随着程序的运行不断增大，而这种增长事先并不知晓会增长到多大，采用其它存储管理方式是难以应付的，而分段存储管理却能较好的解决这一问题。

分段系统的基本原理

1. 分段
   作业地址空间按逻辑信息的完整性被划分为若干个段；
   段内的地址空间是连续的。
   实现分段管理的关键在于，如何保证分段 (二维)地址空间中的一个作业在线性(一维)的存储空间中正确运行。也就是说，如何把分段地址结构变换成线性的地址结构，和分页管理一样，可采用动态重定位技术，即通过地址变换机构来实现。
2. 段表
   为每个分段分配一个连续的分区，而进程中的各个段可以离散地移入内存中不同的分区中。
   实现从逻辑段到物理内存区的映射。
   每个表项（段描述子）至少有三个数据项：段长、主存起始地址和存取控制。
3. ΔΔ地址变换机构
   ①根据段表寄存器的内容找到该作业的段表地址；
   ②利用有效地址中的段号2作为检索段表的索引，得到该段在主存的起始地址；
   ③将段的主存起始地址和位移量W相加， 即得访问主存的物理地址。

Δ" role="presentation" style="box-sizing: border-box; position: relative;">ΔΔ分段存储管理的优点

1. 没有内碎片，外碎片可以通过内存紧缩来消除
2. 便于改变进程占用空间的大小

分段存储管理的缺点

1. 进程全部装入内存

Δ" role="presentation" style="box-sizing: border-box; position: relative;">ΔΔ分页与分段的主要区别

1. 可见与不可见
   ? “分页”是系统活动，用户无法介入，页的大小 固定；
   ? “分段”是用户可见的，段大小可变。
2. 物理单位与逻辑单位
   ? 页是信息的物理单位，不是完整的逻辑单位；
   ? 段是完整的逻辑信息单位。
3. 地址空间
   ? 分页的用户程序地址空间是一维的，是单一线性 空间；
   ? 分段的用户程序地址空间是二维的。
4. 分页是为了提高内存利用率，或者说是系统管理的需要。分段是为了更好地满足用户需求。
5. 分页，用户不关心，页的长度由机器地址结构。分段，用户或编辑程序确定，段的最大长度由位移量字段的位数决定。

Δ" role="presentation" style="box-sizing: border-box; position: relative;">ΔΔ信息共享

分页系统实现段的共享比较困难
分段易于实现段的共享和段的保护

分段的共享是通过两个作业段表的相应表目都指向 COS过程的同一物理副本来实现的

段页式存储管理方式

1. 分页管理内存管理效率高
   没有外零头
   内零头小
2. 分段管理符合模块化思想
   每个分段都具备完整的功能
   方便代码共享、保护

原理：分段和分页相结合。

内存划分：按页式存储管理方案。
内存分配：以页为单位进行离散分配。
由于段页式系统给作业地址空间增加了另一级结构，现在 地址空间是由段号S、段内页号P和页内相对地址(位移量 )W构成。

地址变换：
设置段表、段内页表
① 首先，从段表寄存器从获得进程段表的起始地址，根据该地址，查找进程的段表。
② 然后，根据逻辑地址指定的段号检索段表，找到对应段的页表起始地址。
③ 再根据逻辑地址中指定的页号检索该页表， 找到对应页所在的物理块号。
④ 最后，用物理块号加上逻辑地址中指定的页内偏移量，形成物理地址。

一个段就是一个页表

在段页式存储管理方式中，每访问一 次数据，需访问三次内存。
第一次访问内存中的段表
第二次访问内存中的页表
第三次访问相应数据。大大降低了访问速度。
解决方法： 可以设置快表，表项应包括段号、页号、物理 块号。

综合了分段和分页技术的优点，既能有效地利用存储空间，又能方便用户进行程序设计。
但是，实现段页式存储管理系统需要增加硬件成本，系统的复杂度和管理开销也大大增加。
因此，段页式存储管理技术适合于大、中型计算机系统，不太适合小型、微型计算机系统。

如何提高内存利用率

离散分配、对换机制、动态链接、虚拟存储器、存储器共享

虚拟存储器

物理上扩充内存：
增加硬件投入，收机器自身和成本的限制

从逻辑上扩充内存：
对换技术（解决了“驻留性”问题）
覆盖技术（解决了“一次性”问题）
虚拟存储器技术（依据程序执行的局部性原理）

程序的执行总是局部性的，表现在时间局部性和空间局部性

定义

虚拟存储器：是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。

限制

1. 指令中地址的字长
2. 外存的容量（对换区）

特征

1. 多次性
   多次性是指一个作业被分成多次调入内存运行。
2. 对换性
   虚拟性是以多次性和对换性为基础的；而多次性和对换性又必须建立在离散分配的基础上。
3. 虚拟性
   虚拟性是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。

典型问题

如果系统花费大量的时间把程序和数据频繁地换入和换出内存而不是执行用户指令，那么，称系统出现了抖动。出现抖动现象时，系统显得非常繁忙， 但是吞吐量很低，甚至产出为零。

根本原因：选择的页面或段不恰当。

实现方式

1. 请求分页存储管理系统
2. 请求分段存储管理系统
3. 请求段页式存储管理系统

请求分页存储管理系统

请求分页存储管理方式是在纯分页系统的基础上，增加 了部分页装入、请求调页、页面置换功能。

实现请求页式存储管理系统，需要一定的硬件支持。除了需要一定容量的内存和外存对换区之外，还需要请求页表机制、缺页中断机构和地址变换机构。

地址变换机制：
在纯分页系统的基础上，为实现虚拟存储器增加了某些功能：
某页在外存的情况（状态位＝0），需要增加产生和处理缺 页中断、请求调页和页面置换的功能。
访问某页时，还应修改其访问位；对某页如果执行写操作， 还应设置修改位为1。

1. 确定最小物理块数
   最小物理块数：是指能保证进程正常运行所需的最少物理块 数。若系统为某进程所分配的物理块数少于此值时，进程将 无法运行。
2. 内存分配策略
   固定分配：指为每个进程分配固定物理块数，进程在整个运行期间不变。
   局部置换：指进程运行过程中若发生缺页，只能从进程本身所拥有的物理块中选择一页换出，再调入所需页。
   全局置换：指若空闲队列已空，而又发生缺页中断时，从内存空间中的任意进程所拥有的物理块中选择一页换出。
   固定分配，局部置换
   可变分配，全局置换
   可变分配，局部置换
3. 物理块分配算法
   平均分配算法
   按比例分配
   考虑优先权的分配算法（部分）

页面调入策略

1. 请求调页策略
   缺页中断时，由系统将所缺的页调入内存。但每次请求 只调入一页。
   优点：容易实现。
   缺点：对外存I/O次数多，开销较大，容易产生抖动现象。
2. 预调页策略
   将预计不久之后会被访问的程序或数据所在的页面，提先调入内存。 缺页中断时，系统为进程装入指定的页面以及与之相临的多个页面。
   优点：提高调页的I/O效率。
   缺点：若局部性很差，预先装入的很多页面不会很快被引用，并会占用大量的内存空间，反而降低系统的效率。预调页的成功率仅约50％。常用于首次调入时，由程序员指出应该先调入的页面。

外存要分为文件区和对换区。对换区为取得较快的速度，采用连续分配方式，且对换区所规定盘块较大。

1. 系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页的速度。
2. 系统缺少足够的对换区空间，这时凡是不会被修改的 文件，都直接从文件区调入；
   而当换出这些页面时，由于它们未被修改而不必再将它 们重写到磁盘（换出），以后再调入时，仍从文件区直 接调入。
   但对于那些可能被修改的部分，在将它们换出时，便须 调到对换区，以后需要时，再从对换区调入。
3. UNIX方式。
   由于与进程有关的文件都放在文件区，故凡是未运行 过的页面，都应从文件区调入。 对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。

页面置换算法

把未来不再使用的或短期内较少使用的页面调出，通 常只能在局部性原理指导下依据过去的统计数据进行预测。 要避免“抖动”（Thrashing）（又称颠簸）

1. 最佳置换算法
   选择永不再用或者在最长时间内不再被访问的页面换出。
   优点：缺页率最低，性能最好。
   缺点：依赖于对将来页面访问序列的了解，因此无法实 现。所以此算法只是一 个理想的算法，或称为“目标”， 只能用来评价其它算法的优劣。
2. 先进先出算法
   选择最先进入内存，即在内存中驻留时间最久的页面换出。
   优点：实现简单；
   缺点：不考虑程序的动态性，与进程实际运行的规律不 相适应。
3. 最近最久未使用算法
   选择最近一段时间内最久不用的页面予以淘汰。性能接近最佳算法。页表的访问字段，用以记录自上次访问以来所经历的时间T。 每次都选择现有页面中T值最大的页面置换。
   为了记录页面使用时间的先后关系，引入硬件支持：
   寄存器，为每个在内存中的页面配置一个移位寄存器，当进程 访问它时，将其寄存器的最高位置1。且定时信号每隔一 定时间将寄存器右移一位。 具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。栈，利用栈保存当前（最近）使用的各个页面页面号。 若栈中有该页号则将其从原位置移出，压入栈顶；若栈中没有该页号且栈满，则将栈底页号对应页置换出，将新页号压入栈顶。
4. clock置换算法（轮转算法）
   该算法只考虑某页是否已经使用过，未考虑使用的时间，称为“最近未用算法”
   当某页被访问时，其访问位被置为1。
   置换算法寻找访问位=0的页面作为被置换页。
   指针经过的访问位为1的页重新置0，最后指针停留在被置换页的下一个页。
   若查找一遍后没有访问位是0的页面，则返队首。

改进：考虑置换代价。选择换出页面时，既要是未使用过的页面， 又要是未被修改过的页面。把同时满足两条件的页面作为首选淘汰的页。
5. 最不常用算法
最少使用置换算法LFU（Least Frequently Used)选择 到当前时间为止被访问次数最少的页面被置换。
6. 页面缓冲算法

有效访问时间

设内存读写周期为t，查找快表时间为λ，缺页中断处理时间为?，引入快表命中率为α，缺页中断率为f，则有效访问内存时间为：

EAT=λ+αt+(1?α)[f(t+?+λ)+(1?f)(t+λ)+t]EAT=λ+αt+(1?α)[f(t+?+λ)+(1?f)(t+λ)+t]

抖动

1. 局部抖动
2. 全局抖动

产生原因：
进程分配的物理块太少
置换算法选择不当
全局置换使抖动传播

消除抖动的办法：
采取局部置换策略
基于工作集的物理块分配策略
L=S准则
挂起若干进程

输入输出系统

基本功能：
? 1、隐藏物理设备的细节
? 2、与设备的无关性
? 3、提供处理机和I/O设备的利用率（并行操作）
? 4、对I/O设备进行控制（四种控制方式）
? 5、确保对设备的正确共享（设备的共享属性）
? 6、错误处理

总体设计目标是高效性和通用性。
(1)I/O设备与CPU的并发性；
(2)简单抽象、清晰而统一的接口。

I/O系统接口

1. 块设备接口
   信息的存取以数据块为单位，有结构设备。如磁盘
2. 流设备接口
   基本单位是字符，无结构设备。 如交互式终端、打印机。
3. 网络通信接口

I/O设备和设备控制器

I/O系统：用于实现数据输入、输出及数据存储的系统。

I/O设备

类型

(1)按设备的使用特性分类
存储设备
输入/输出设备

(2)按传输速率分类
低速设备
中速设备
高速设备

(3)按设备的共享属性分类
独占设备(临界资源 )
共享设备
虚拟设备

设备与控制器之间的接口

三种信号：
（1）数据信号：双向，有缓存
（2）控制信号：控制器发给设备；要求其完成相 关操作
（3）状态信号：传送指示设备当前状态的信号；

设备控制器

设备控制器是一个可编址的设备，可控制多个设 备并为它们编址,以实现I/O设备和计算机之间的 数据交换，减轻CPU的负担。

设备控制器可分为控制块设备的控制器和控制字 符设备的控制器两类。

功能：接收CPU命令，控制I/O设备工作，解放CPU

组成：设备控制器与处理机的接口，设备控制器与设备的接口和I/O逻辑

I/O通道

是一种特殊处理机，专门负责输入/输出工作，具有 执行I/O指令的能力。主要目的是为了建立独立的 I/O操作，使有关对I/O操作的组织、管理及其结束 处理也独立于CPU。

总线系统

中断机构和中断处理程序

把引起中断的事件称为“中断源”
对出现的事件进行处理的程序称为 “ 中断处理程序”

CPU在每条指令执行周期的最后时刻扫描中断寄存器， 询问是否有中断信号

处理过程

中断处理过程
–唤醒被阻塞的驱动程序进程
–保护被中断进程CPU环境
–转入相应的设备处理程序
–中断处理(特性)
–恢复被中断进程的现场

设备驱动程序

设备驱动程序功能：
(1)接收由I/O进程发来的命令和参数, 并将命令中的抽象 要求转换为具体要求。
(2)检查用户I/O请求的合法性,了解I/O设备的状态,传递有 关参数,设置设备的工作方式。
(3)发出I/O命令并检查设备状态。
(4)及时响应由控制器或通道发来的中断请求并处理。

设备驱动程序的特点：
(1)驱动程序主要是指在请求I/O的进程与设备控制器之间 的一个通信和转换程序。
(2)驱动程序与设备控制器和I/O设备的硬件特性紧密相关 ,因而对不同类型的设备应配置不同的驱动程序。
(3)驱动程序与I/O设备所采用的I/O控制方式紧密相关， 常用中断驱动和DMA方式。
(4)由于驱动程序与硬件紧密相关,因而其中的一部分必须 用汇编语言书写。
(5)驱动程序允许可重入。

设备处理方式：
(1)为每一类设备设置一个进程,专门用于执行这类设 备的I/O操作 。
(2)在整个系统中设置一个I/O进程,专门用于执行系统 中所有各类设备的I/O操作。
(3)不设置专门的设备处理进程,而只为各类设备设置 相应的设备处理程序(模块),供用户进程或系统进程调用

I/O控制方式：

• 程序I/O方式 (programmed I/O) CPU and Device can not work in parallel
• 中断方式 (interrupt) CPU and device can work in parallel, too many interrupts for CPU
  中断I/O比程序I/O方式高效，但以字/字节为传输单位。 每完成一个字/字节的传输，设备均要向CPU请求一次中断
• 直接存储器访问方式 (DMA) DMA controller in charge of block i/o
  数据传输的基本单位是数据块
  DMA控制器的组成： 1. 主机与DMA控制器的接口； 2. DMA控制器与块设备的接口； 3. I/O控制逻辑。
• 通道方式 (channel)
  CPU仅在I/O操作的开始和结束时花费少量时间处理与I/O 有关的工作。
  实现CPU、通道和I/O设备三者的并行操作，从而更有效 地提高整个系统的资源利用率

设备独立性

含义：应用程序独立于具体使用的物理设备，即是指用 户在编程序时所使用的设备与实际设备无关。

引入逻辑设备和物理设备这两个概念。
在应用程序中,使用逻辑设备名称来请求使用某类设备;而系统在实际执行时,还必须使用物理设备名称。

设备独立性的优点
(1)设备分配时的灵活性
(2)易于实现I/O重定向

设备独立性软件主要功能：
(1)执行所有设备的公有操作
(2)向用户层(或文件层)软件提供统一接口

设备分配

（1）设备控制表DCT
（2）控制器控制表、通道控制表和系统设备表

虚拟设备是利用某种技术把独占设备改造成可由多个进程共享的设备。

用户层的I/O软件

用户程序通过调用对应的库函数使用系统调用。

SPOOLing技术将一台物理I/O设备虚拟为多台逻辑I/O 设备，同样允许多个用户共享一台物理I/O设备。
(1)脱机输入、输出技术
(2) 在主机的直接控制下，实现脱机输入、输出功能，此时的外围操作与CPU对数据的处理同时进行。

SPOOLing技术

SPOOLing技术将一台物理I/O设备虚拟为多台逻辑I/O 设备，同样允许多个用户共享一台物理I/O设备。

组成

输入井和输出井
输入缓冲区和输出缓冲区(内存中)
输入进程SPi 和输出进程SP0
井管理程序

输出：（打印） a.进程n请求——>SPo为进程n在输出井中分配空间——> 将数据由进程缓冲区转到输出井——>生成一打印请求 表挂打印请求队列。 b.打印机空——>查打印请求表中的任务——> 取输出井 中对应的数据——>输出缓冲区——>打印

缓冲区管理

(1)缓和CPU与I/O设备间速度不匹配的矛盾。
(2)减少对CPU的中断频率,放宽对CPU中断响应 时间的限制。
(3)解决数据粒度不匹配的问题。
(4)提高CPU和I/O设备之间的并行性。

提前读，延后写，操作系统中介绍的都是软件缓冲区

单缓冲

一个缓冲区，CPU 和外设轮流使用， 一方处理完之后接着等待对方处理

C和T可并行，M和C或M和T不能并行，因此处理一块数据时间：Max(C,T)+M
（C为工作区处理数据，M为缓冲区传送到工作区，T为I/O设备输入到缓冲区）

双缓冲

两个缓冲区，CPU和外设都可以连续处理而无需等待对方。要求CPU和外设的速度相近。

? 效率有所提高，且进一步平滑了传输峰值。
? 系统处理一块数据的时间约为：MAX(C,T) ? 收发可双向同时传送。

循环缓冲

增加缓冲区的数量以改善系统性能，这就是多缓冲区方式。
多个I/O缓冲区常常被组织成一个环形队列，称为循环缓冲。

缓冲池

上述三种缓冲区的组织形式仅适用于某种特定的 I/O进程和计算进程，属于专用缓冲。
为了提高缓冲区的利用率，可以采用公共缓冲池
其中的缓冲区可为多个设备和进程服务

两种缓冲池：分别用于块型设备和字符型设备。

公用缓冲池，含有以下三种类型的缓冲区： ①空(闲)缓冲区； ②装满输入数据的缓冲区； ③装满输出数据的缓冲区。

为了管理上的方便，可将相同类型的缓冲区链成 一个队列，于是可形成以下三个队列：
（1）空缓冲队列emq。 这是由空缓冲区所链成的队列。
（2）输入队列inq。 这是由装满输入数据的缓冲区所链成的队列。
（3）输出队列outq 这是由装满输出数据的缓冲区所链成的队列。

磁盘存储器的性能和调度

1、数据组织和格式：
?磁道号——磁头号——扇区——字节

2、类型
1）固定头磁盘： –每个磁道上有一个磁头，快
2）移动头磁盘： –每个盘面仅有一个磁头，慢

? 信息记录在磁道上，多个盘片，正反两面都用来记 录信息，每面一个磁头
? 所有盘面中处于同一磁道号上的所有磁道组成一个 柱面
? 每个扇区大小为600字节（数据512字节）
? 物理地址形式： –柱面号 –磁头号 –扇区号

访问过程

由三个动作组成：
– 寻道 ：磁头移动定位 到指定磁道
– 旋转延迟：等待指定 扇区从磁头下旋转经过
– 数据传输：数据在磁 盘与内存之间的实际传输

磁盘访问时间

磁盘访问时间：
1）寻道时间：TS=m?n+sTS=m?n+s m：常量，n：磁道数，s：磁臂启动时间。 对一般的磁盘， 其寻道时间将随寻道距离的增加而 增大， 大体上是5-30 ms。
2）旋转延迟时间： 指定扇区旋转到磁头下所需时间。 设每秒r转，则Tr＝1/2rTr＝1/2r（均值） 对于7200转/分，平均延迟时间为4.2ms
3）数据传输时间：Tt＝b/rNTt＝b/rN b：读写字节数 N：每道上的字节数

访问时间：Ta=Ts+1/2r+b/rNTa=Ts+1/2r+b/rN

磁盘调度算法

• 先来先服务FCFS
  ? 按访问请求到达的先后次序服务
  ? 优点：简单，公平；
  ? 缺点：效率不高，相邻两次请求可能会造成 最内到最外的柱面寻道，使磁头反复移动， 增加了服务时间，对机械也不利
• 最短寻道时间优先SSTF
  优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先
  ? 优点：改善了磁盘平均服务时间；
  ? 缺点：造成某些访问请求长期等待得不到 服务
  对 SSTF 算 法 略 加 修 改 后 所 形 成 的 SCAN 算法， 即可防止老进程出现“饥饿”现象。
• 扫描算法SCAN
  克服了最短寻道优先的缺点，既考虑了距离，同时 又考虑了方向
  当设备无访问请求时，磁头不动； 当有访问请求时，磁头按一个方向移动，在移动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描； 否则改变移动方向，并为经过的访问请求服务，如此反复
  当磁头刚从里向外移动而越过了某一磁道时，恰好又 有一进程请求访问此磁道，这时，该进程必须等待， 待磁头继续从里向外，然后再从外向里扫描完所有要 访问的磁道后，才处理该进程的请求，致使该进程的 请求被大大地推迟。为了减少这种延迟，推出CSCAN 算法，规定磁头单向移动。
  ? 优点： SCAN 算法既能获得较好的寻道性能，又能防止“饥饿” 现象，故被广泛用于大、中、小型机器和网络中的磁盘 调度。
  ? 问题： –当磁头刚从里向外移动而越过了某一磁道时，恰好又 有一进程请求访问此磁道，这时，该进程必须等待， 待磁头继续从里向外，然后再从外向里扫描完所有要 访问的磁道后，才处理该进程的请求，致使该进程的 请求被大大地推迟。 –为了减少这种延迟，推出CSCAN 算法，规定磁头单向 移动。
• 循环扫描算法CSCAN
  ? 电梯算法杜绝了饥饿，但当请求对磁道的分布是 均匀时，磁头回头，近磁头端的请求很少（因为 磁头刚经过），而远端请求较多，这些请求等待 时间要长一些。
  ? 总是自里向外移动。移动臂到达最后个一个柱面 后，立即带动读写磁头快速返回到最里的欲访问 磁道。返回时不为任何的等待访问者服务。返回 后可再次进行扫描

有一个或几个进程对某一磁道有较高的访 问频率， 即这个(些)进程反复请求对某一磁道的I/O操作，从而垄断了整个磁盘设备。 我们把这一现象称为“磁臂粘着”(Armstickiness)。

实际系统相当普遍采用最短寻道时间优先算法， 因为它简单有效，性价比好。

磁盘高速缓存

…

文件管理

文件系统的功能：
有效地管理文件的存储空间；
管理文件目录；
完成文件的读/写操作；
实现文件共享与保护；
为用户提供交互式命令接口和程序调用接口。

文件系统

定义：
操 作 系 统 中 的 各 类 文件、 管 理 文 件 的 软件， 以 及 管 理 文 件 所 涉 及 到 的 数据结 构等信息的集合

文件系统模型

分为三个层次：
1. 文件系统接口
2. 对对象操纵和管理的软件集合
3. 对象及其属性

文件类型

1. 用途
   系统文件
   用户文件
   库文件
2. 文件中的数据形式
   源文件
   目标文件
   可执行文件
3. 存取控制属性
   只执行文件
   只读文件
   读写文件
4. 组织形式和处理方式
   普通文件
   目录文件
   特殊文件

文件的逻辑结构与访问

对于任何一个文件，都存在着以下两种形式的结构：
文件的逻辑结构(File Logical Structure),又称 为文件组织，是用户可以直接处理的数据及其 结构。
文件的物理结构， 又称为文件的存储结构， 是指文件在外存上的存储组织形式。

文件逻辑结构的类型

1. 有结构文件 记录有定长和不定长两种
   1）顺序文件：按某种顺序排列的定长纪录文件
   2）索引文件：按索引表查询的不定长纪录文件
   3）索引顺序文件：以上两者的结合
2. 无结构文件
   其长度以字节为单位。 可以把流式文件看作是记录式文件的一个特例。

顺序文件

第一种是串结构， 各记录之间的顺序与关键字无关。 通常的办法是由时间来决定，即按存入时间的先后排列。

第二种情况是顺序结构，指文件中的所有记录按关键字 (词)排列。是最常用的文件组织方式。

顺序文件的优缺点
常 用 于 批 量 数 据 处 理 ， 这 时 文 件 的 访 问 效 率最高。
是唯一、 同 时 适 合 在 磁 盘 和 磁 带 中 存 储 的 文件。
访问效率比堆文件高。当文件较小，可以将文件全部装入内存，利用某种快速的查找算法，如折半查找法、插值查找法等快 速查找指定的记录。

索引文件

可为变长记录文件建立一张索引表，对主文件中的每个记录，在索引表中设有一个相应的表项， 用于记录该记录的长度L及指向该记录的指针(指 向该记录在逻辑地址空间的首址)。
由于索引表是按记录键排序的，因此，索引表本身是一个定长记录的顺序文件，从而也就可以方便地实现直接存取。

索引顺序文件

将顺序文件中的所有记录分为若干个组(例 如，50 个记录为一个组)；
为顺序文件建立一张索引表.
在索引表中为每组中的第一个记录建立一 个索引项，其中含有该记录的键值和指向该记录的指针。

直接和哈希文件

直接文件
对于直接文件，则可根据给定的关键字值，直 接获得指定记录的物理地址。
关键字值本身就决定了记录的物理地址。
这种由关键字值到记录物理地址的转换被称为键值转换。

文件目录

文件目录也是一种数据结构，用于标识系统中的 文件及其物理地址，供检索时使用。

文件控制块（FCB）

文件控制块是操作系统为管理文件而设置的数据结构，存放了管理文件所需的所有信息（文件属性）
1）基本信息类
文件名：文件标识符；
物理位置：存放文件的设备名 起始盘块号 文件长度（盘块数或字节数）
逻辑结构：有结构文件、无结构文件
物理结构：顺序文件、链式文件、索引文件
2）存取控制信息类
文件主的存取权限
核准用户的存取权限
一般用户的存取权限
3）使用信息类
文件的建立日期和时间
文件上一次修改的日期和时间
当前使用信息（进程数、是否修改等）

文件目录：把所有的FCB组织在一起，就构成 了文件目录，即文件控制块的有序集合。
目录项：构成文件目录的项目（目录项就是 FCB）
目录文件：为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外存，这个文件就叫目录文件。

索引结点

将文件的描述信息单独形成称为索引结点的数据结构，即 i 结点

1. 磁盘索引节点
   指存放在磁盘上的索引结点
   包括：
   文件主标识符
   文件类型
   文件存取权限
   文件物理地址
   文件长度
   文件链接计数
   文件存取时间
2. 内存索引节点
   指存放在内存的索引结点
   比磁盘索引节点增加了：
   索引结点编号
   状态
   访问计数
   文件所属文件系统的逻辑设备号
   链接指针

目录结构

1. 单级目录结构
2. 二级目录结构
   主文件目录（MFD）
   用户文件目录（UFD）
3. 树型目录结构
   把三级或三级以上的目录结构称树型目录
   优点：层次结构清晰，便于管理和保护，有利于文件分类，解决重名问题，提高文件检索速度，能进行存取权限的控制
   缺点：查找一个文件按路径名逐层检查，由于 每个文件都放在外存，多次访盘影响速度

目录查询技术

查询目录有两种方法：
线性检索法
Hash 方法

文件共享

实现文件共享的方式：
基于索引结点的共享方式
利用符号链实现文件共享

利用URL实现文件共享

文件保护

存取控制机制
系统容错技术（第八章）
后备系统（第八章）

存取控制机制

保护域
访问矩阵
访问矩阵的修改
访问矩阵的实现
分级安全管理

磁盘存储器的管理

外存的组织方式

Δ" role="presentation" style="box-sizing: border-box; position: relative;">ΔΔ连续分配

连续分配(Continuous Allocation)要求为每一 个文件分配一组相邻接的盘块。一组盘块的地址 定义了磁盘上的一段线性地址。

把逻辑文件中的数据顺序地存储到物理上邻接的各个数据块中，这样形成的物理文件可以进行顺序存取。

连续分配的主要优点：
顺序访问容易。
顺序访问速度快。
连续分配的主要缺点：
要求有连续的存储空间。
必须事先知道文件的长度。
不能灵活地插入和删除记录
不适应动态增长的文件

该 分 配 方 案 可 能 会 导 致 磁 盘 碎 片 ， 严 重 降 低外存空间的利用率。
解 决 方 法 之 一 ， 系 统 定 期 或 不 定 期 采 用 紧 凑 技术， 将 小 分 区 合 并 为 大 的 、 连 续 分 区 ， 将文件占用空间合并在一起。

Δ" role="presentation" style="box-sizing: border-box; position: relative;">ΔΔ链接分配

如果在将一个逻辑文件存储到外存上时，并不要 求为整个文件分配一块连续的空间，而是可以将 文件装到多个离散的盘块中。

采用链接分配方式时，可通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，把这样形成的物理文件称为链接文件。

1. 隐式链接
2. 显式链接

问题：
(1) 不能支持高效的直接存取
(2) FAT需占用较大的内存空间

Δ" role="presentation" style="box-sizing: border-box; position: relative;">ΔΔ索引分配

1. 单级索引分配
2. 两级索引分配

设文件系统采用两级索引分配方式，如果每个盘块的大小为1KB，每个盘块号占4B，则单个文件的最大长度是多少？ 解：1个盘块可有1KB/ 4B=256个索引项，则两级索引下单个文件最大长度： 256*256*1KB=64MB

文件存储空间的管理

存储空间的基本分配单位是磁盘块。
其分配方法与内存的分配有许多相似之处，即同样可采取连续分配方式或离散分配方式。

动态跟踪磁盘上的空闲块数目和块号，形成空闲块登记表。
空闲块登记表是盘块分配和回收的依据。
空闲块登记表有四种实现方案：

• 空闲表
  系统为外存上的所有空闲区建立一张空闲表， 每个空闲区对应于一个空闲表项
  适合于可变大小分区的连续分配方式
• 空闲链表
  这种空闲空间组织方法适合于非连续存储文件。
  空闲盘块链：
  将磁盘上的所有空闲空间，以盘块为单位拉成一条链。空闲盘区链：
  将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条链。
• 位示图法
  利用二进制位0、1表示存储空间中存储块的使用状态
  盘块的分配：顺序扫描位示图，从中找出一个值为“0”的二进制位（空闲位），将所找到的空闲位号转换成与之相应的空闲块号： b=n*(i-1)+j b为对应的空闲块的块号 n为位示图中每行的位数 i、j分别为空闲位在位示图的行号、列号，修改位示图：令map[i,j]＝1
  盘块的回收：将回收盘块的盘块号转换成位示图中的行 号和列号 i=(b-1)DIV n+1 j=(b-1)MOD n+1，修改位示图：令 map [i,j]＝0
• 成组链接法

操作系统接口

• 用户接口
  联机用户接口
  脱机用户接口
• 程序接口
  又称应用编程接口API，允许运行程序调用操作系统的服务和功能。
  程序接口由一组系统调用（SystemCall)） 组成，用户程序使用“系统调用”就可获得操作系统的底层服务，使用或访问系统的各种软硬件资源。
  库函数的目的是隐藏访管指令细节， 使系统调用更象过程调用，但一般地说，库函数属于用户程序而非系 统程序。

联机命令接口

分时系统或个人计算机中，操作系统 向用户提供了一组联机命令，用户可以 通过终端键入命令，以取得操作系统的 服务，并控制自己作业的运行，这样的 接口称为联机命令接口 。

联机命令接口应由终端处理程序、命令解释程序及一组联机命令构成。

Shell命令语言

Shell是UNIX与用户的交互接口,是操作系统的最外层,称为外壳
Shell既是一种命令语言,也是一种程序设计语言
Shell不是UNIX的核心程序,运行在用户态

系统调用

系统调用指系统为用户程序调用操作系统所提供的子程序。 它与一般的函数调用不同，系统调用是通过中断方式转向相应子程序的，它工作在核心态 （即特权方式），而一般函数调用，仍仅在用户态下的地址转移 。

系统调用与一般过程调用的区别：

1. 运行在不同的系统状态
   一般过程调用，其调用程序和被调用程序 都运行在相同状态：核心态或用户态
   系统调用：调用程序在用户态，被调用程 序在系统态
2. 状态的转换
3. 返回问题
   一般过程调用在被调用过程执行完后，回调用过程。
   抢占式调度的系统中，被调用过程执行完后，系统将对所有要求运行的进程进行优先级分析。如果调用进程仍有最高优先级，则返回到调用进程执行，否则，引起重新调度，让优先级最高的进程 优先执行。此时，系统把调用进程放入就绪队列。
4. 嵌套调用
   系统调用也允许嵌套调用，即在一被调用过程执行期间，可再利用系统调用命令调用另一系统调用，最大深度为