操作系统

基本概念

操作系统是计算机硬件、软件资源的管理者，

为用户和软件提供服务，
是系统软件

操作系统的特征

• 并发(基本)

  • 注意并发和并行的区别

• 共享(基本)

  • 互斥共享方式（临界资源）

  • 同时访问方式（并发访问）

• 虚拟

  • 时分复用技术：虚拟处理器

  • 空分复用技术：虚拟存储器

• 异步

  • 不同程序以不可预知的速度前进

操作系统的目标：安全、高效

操作系统的功能

• 处理机管理（进程管理）

  • 进程控制、进程同步、进程通信、死锁处理、处理机调度

• 存储器管理（内存管理）

• 文件管理

• 设备管理

操作系统接口

• 命令接口（用户）

  • 联机命令接口（交互式命令接口）

  • 脱机命令接口（批处理命令接口）

• 程序接口（程序）

  • 系统调用（广义指令）

    • 过程：传参、陷入、中断处理、返回应用程序

    • 系统调用的过程

      • (1)传参：程序传入系统调用的相关参数

      • (2)陷入：程序执行陷入指令（用户态）

      • (3)中断处理：由操作系统根据参数处理相应系统调用程序（内核态）

      • (4)中断返回：返回应用程序

  • 如：图形接口（图形用户界面GUI）通过调用程序接口实现
    注：图形接口不是操作系统的一部分

裸机&扩充机器（虚拟机）

• 裸机：没有任何软件支持的计算机

• 扩充机器（虚拟机）：覆盖了软件的机器

发展历程

• 手工操作阶段（无操作系统）

  • 缺点：

• 用户独占

• CPU利用率低

• 批处理阶段

  • 单道批处理系统

    • 优点

      • 解决人机矛盾及CPU与IO设备速率不匹配问题

    • 特点

自动性

		- 顺序性

		- 单道性

			- 内存中仅有一道程序

- 多道批处理系统

	- 开始运用多道程序技术

	- 特点

		- 多道性

		- 宏观上并行

		- 微观上串行

	- 优点： 资源利用率高、系统吞吐量大

	- 缺点：用户响应时间较长

、不提供人机交互能力

- 分时操作系统

	- 应用分时技术

		- 用户可以同时与主机进行交互而互不干扰，并得到及时的响应

	- 特点

		- 同时性（多路性）

		- 交互性

			- 人机交互

		- 独立性

			- 多用户独立

		- 及时性

- 实时操作系统

	- 分类

		- 硬实时系统

			- 必须绝对在规定时间内，如飞行控制系统

		- 软实时系统

			- 可以偶尔违反时间规定，如订票系统

	- 特点

		- 及时性

		- 可靠性

处理器的运行模式

• 用户态（目态）

  • 非特权指令

    • 仅可访问用户地址空间

  • 通过访管指令（trap陷入指令）主动进入内核态

    • 根据仿管指令的操作数，执行对应仿管中断处理程序

• 内核态（管态）

  • 特权指令

    • 中断返回指令，可以返回用户态

• 中断机制

  • 引入中断机制的初衷是提高多道程序运行环境中CPU的利用率

  • 中断机制中只有一小部分功能属于内核（保护和恢复中断现场信息、转移控制权到相关处理程序）

  • 引发中断和异常时，CPU从用户态进入核心态，是由硬件实现的

  • 中断处理过程

    • 见机组

  • 中断和异常

    • 异常（内中断）

      • 故障（Fault）：软件中断、不可屏蔽

      • 自陷（trap）：软件中断、不可屏蔽

      • 终止（Abort）：硬件中断、不可屏蔽

    • 中断（外中断）

      • 可屏蔽中断

      • 不可屏蔽中断

• 原语

操作系统的结构

• 分层法

  • 每层只能调用紧邻的底层服务

  • 优点

    • 便于系统的调试和验证

    • 易扩充和易维护

  • 缺点

    • 难以合理定义各层，依赖关系不够灵活

    • 效率较差（逐层调用）

• 模块化（按功能划分）

  • 内核 = 主模块 + 可加载模块（驱动程序）

  • 优点

提高系统设计的正确性、可理解性、可维护性

	- 适应性强，动态装载模块

	- 系统开发过程并行

	- 效率高（调用其他模块）

- 缺点

	- 模块相互依赖，难以验证

• 按内核架构划分

  • 宏内核

    • 主流，具有性能优势

  • 微内核

    • 定义

1.足够小的内核

2.基于客户/服务器模式

3.应用“机制与策略分离”原理

4.采用面向对象技术

	- 基本功能

		- 

1.进程(线程)管理

2.低级存储器管理

3.中断和陷入处理

	- 适合放在微内核中的服务

		- - 进程间通信机制

• 低级I/O

• 低级进程管理和调度

• 中断和陷入处理

    - 优点
  
    	- 1.扩展性和灵活性
  

2.可靠性和安全性

3.可移植性

4.分布式计算

	- 缺点：

性能问题（运行模式频繁切换）

• 外核

  • 对机器进行分区，每个用户可运行自己的操作系统，并独立使用已获得分配的资源

  • 优点

    • • 减少了映射层

• 分离多道程序与操作系统代码

  • 缺点

• 降低了一致性

• 更复杂

虚拟机

• 第一类虚拟机管理程序

  • 层次：硬件=》虚拟机管理程序=》虚拟机（操作系统和用户进程）

  • 注：

1. 虚拟机管理程序运行在核心态

2. 虚拟机实际运行在用户态，但虚拟机操作系统认为自己运行在内核态

3. 当虚拟机操作系统执行敏感指令时，实际上转为对虚拟机管理程序的调用

• 第二类虚拟机管理程序

  • 层次：硬件=》宿主操作系统（Host OS）=》虚拟机管理程序=》客户操作系统

  • 如：VMware WorkStation

  • 虚拟机管理程序运行在用户态/核心态，
    虚拟机发出的系统调用被VMM截获，转为对Host的调用

• 对比

  • 第一类虚拟机管理程序

    • • 资源分配：直接控制、分配物理资源；

• 性能：更好

• 支持数量：更多

• 可迁移性：更差

• 运行模式：核心态（拥有最高级特权指令）

  • 第二类虚拟机管理程序

    • • 资源分配：由Host OS分配，磁盘实际上是一个文件；

• 性能：更差

• 支持数量：更少

• 可迁移性：更好

• 运行模式：用户态/核心态

进程与线程

进程的相关概念

• 进程&进程实体

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

  • 进程实体（进程映像）是运行时的一张“快照”

    • 程序段

    • 数据段

    • 进程控制块PCB

      • 进程存在的唯一标志

      • 组织方式：链式、索引

      • 内容

  • 进程映像是静态的，进程是动态的

• 进程的特征

  • 动态性（最基本）

    • 进程是一个执行过程，具有生命周期

  • 并发性

  • 独立性

    • 独立运行、独立获得资源和独立[接受调度]的基本单位

    • 注：引入线程后不再是接受调度的基本单位

  • 异步性

  • 结构性

    • 程序段、数据段、PCB

• 进程的状态与转换

  • 五状态模型

    • 创建态

    • 就绪态[基本]

    • 运行态[基本]

    • 阻塞态[基本]

    • 结束态

  • 七状态模型

    • 就绪挂起态

    • 阻塞挂起态

  • 引起状态转变的事件

    • 就绪->运行：处理机调度

    • 运行->就绪：失去处理机（时间片耗尽、CPU被剥夺）

    • 运行->阻塞：进程【主动】发起系统调用，请求系统资源

    • 阻塞->就绪：等待的事件发生【被动】

• 进程控制

  • 进程的创建

    • 事件

      • 登录系统、作业调度、系统提供服务、
        用户程序的应用请求等

    • 创建原语

1.申请一个空白PCB
2.分配资源
3.初始化PCB
4.进程插入就绪队列，等待调度（进入就绪态）

- 进程的终止（撤销）

	- 事件

		- 正常结束、异常结束、

外界干预（操作系统、父进程干预）

	- 终止原语

		- 1.检索到进程PCB

2.终止进程的执行（若在执行），将处理机分配给其他进程
3.终止所有子孙进程（若有）
4.回收分配的资源
5.将PCB从所在队列中删除

- 进程的阻塞

	- 状态

		- 运行->阻塞

	- 事件

		- 处于运行态的进程主动发起系统调用

	- 阻塞原语

		- 1.找到PCB

2.将运行环境（PSW、PC）存入PCB，状态改为阻塞态
3.将PCB移入相应事件的等待队列

- 进程的唤醒

	- 状态

		- 阻塞->就绪

	- 事件

		- 阻塞进程等待的事件发生

	- 唤醒原语

		- 1.从等待队列中找到PCB

2.将PCB移出等待队列，置为就绪态
3.将PCB插入就绪队列，等待处理机调度

- 进程的切换

	- 状态

		- 运行->就绪

就绪->运行

	- 事件

		- 1.进程时间片用完

2.高优先级抢占
3.当前进程主动阻塞
4.当前进程终止

	- 切换原语

		- 1.将运行环境(PSW、PC)存入PCB

2.将PCB移入相应队列
3.选择一个就绪的进程执行，并更新PCB
4.根据PCB恢复运行环境

	- 进程上下文

		- 系统级上下文

			- 进程标识信息

			- 进程现场信息

				- PC、PSW

			- 进程控制信息

			- 系统内核信息

		- 用户级上下文

			- 用户堆栈

			- 用户数据块

			- 用户程序块

			- 共享地址空间

• 进程通信

  • 低级通信方式

    • PV操作

  • 高级通信方式

    • 共享存储

      • 由操作系统提供共享存储空间和同步互斥工具，用户进程通过系统调用对共享空间进行读写

      • 1.低级：基于数据结构的共享
        2.高级：基于存储区的共享

    • 消息传递

      • 通过操作系统提供的“发送消息”和“接收消息”原语进行；以格式化的消息为单位

      • 1.直接通信方式：将消息挂在消息缓冲队列上
        2.间接通信方式：借助中间实体“信箱”

      • 应用：多处理机系统、分布式系统、计算机网络；微内核系统中微内核与服务器之间的消息传递机制

    • 管道通信

      • 通过共享文件(pipe)，以字符流的形式写入数据。
        管道机制需提供：互斥、同步、确定对方存在

      • 注意：
        1.管道是一个固定大小的缓冲区。
        2.管道采用半双工通信，即数据是单向流动的；可以通过两个管道实现父子进程的互动通信。
        3.一个管道允许多个写进程和一个读进程，读写进程可以同时进行。
        4.管道写满后，写进程会被阻塞；管道读空后，读进程会被阻塞。
        5.读管道数据是一次性操作，读取即会释放空间

线程的相关概念

• 线程

  • 线程是基本的CPU执行单元，也是程序执行流的最小单元。

  • 线程不拥有独立的系统资源，但可共享进程资源（线程间共享堆但不共享栈）

  • 一个线程可以创建和撤销另一个线程

  • 线程具有运行、就绪、阻塞三种基本状态，状态的转换与进程基本一致

  • 线程终止后不立即释放资源

    • 其他线程重新调用被终止线程（资源尚未释放），可以重新恢复运行

    • 其他线程执行分离函数，则被终止线程才与资源分离（释放资源）

• 线程控制块TCB

  • TCB中的内容是线程私有的，线程间不共享

  • ①线程标识符
    ②一组寄存器（PC、PSW、通用寄存器）
    ③线程运行状态
    ④优先级
    ⑤线程专有存储区（保存现场）
    ⑥堆栈指针（过程调用时保存局部变量和返回地址）

• 实现方式

  • 用户级线程（ULT）

    • 多对一模型（多个用户级线程映射到一个内核级线程）

    • 应用程序使用线程库管理用户线程

    • 优点

      • 1.线程切换不需要转换到内核空间
        2.进程可以采用自己的线程调度算法
        3.实现与操作系统无关，由用户程序管理

    • 缺点

      • 1.线程的阻塞引起整个进程的线程全部阻塞
        2.不能发挥多处理机的优势

  • 内核级线程（KLT）

    • 一对一模型
      （每个用户级线程映射到一个内核级线程）

    • 优点

      • 1.能发挥多处理机优势
        2.一个线程被阻塞，内核可以调度该进程的其他线程占用处理机
        3.线程切换快、开销小
        4.内核本身也可以采用多线程技术，提高效率

    • 缺点

      • 同一进程的线程切换，也需要转到核心态，开销大（线程在用户态运行，而线程调度和管理在内核实现）

  • 组合（ULT+KLT）

    • 多对多模型（将n个用户级线程映射到m个内核级线程，n≥m）

    • 注：内核级线程是处理机调度的最小单位，当所有内核级线程被阻塞时才称这个进程被阻塞。

处理机调度

• 调度层次

  • 高级调度（作业调度）

    • 作业由外存调入内存，并建立进程。
      每个作业只调入一次、调出一次。

  • 中级调度（内存调度）

    • 将进程挂起或激活（在外存、内存之间调度）

    • 目的：提高内存利用率和系统吞吐量

  • 低级调度（进程调度）

    • 分配处理机给进程

    • 频率最高，是最基本、不可或缺的调度

• 性能指标

  • CPU利用率 = 工作时间/（工作时间+空闲时间）

  • 系统吞吐量 = 单位时间内完成的作业数量

  • 周转时间 = 作业完成时间 - 作业开始时间
    = 等待时间+运行时间+IO操作时间

  • 带权周转时间 = 作业周转时间/作业实际运行时间

    • =1

  • 等待时间

    • 对于进程，IO时间不计入

    • 对于作业，要考虑在外存后备队列的等待时间

  • 响应时间

    • 从用户提交请求到首次产生响应的时间

• 调度实现

  • 调度时机

    • 调度器的触发时机

      • • 创建新进程

• 进程退出

• 运行进程阻塞

• IO中断

• (抢占式)每k个时钟中断

    - 不能进行调度的情况
  
    	- 中断处理过程中
  
    	- 进程运行在系统内核临界区中（进程在[普通]临界区时可以调度，如访问临界资源打印机）
  
    	- 原子操作过程中
  

  • 调度方式

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

      • 只有进程阻塞或退出时调度

      • 适用于早期批处理系统

    • 抢占式（剥夺方式）

      • 根据优先权、短进程优先、时间片原则等

      • 适用于分时、实时操作系统

  • 闲逛进程

    • 优先级最低

    • 不需要CPU之外的资源，不会被阻塞

  • 广义的进程调度

    • 进程调度

      • 决策：确定资源分配给哪个进程

    • 进程切换

      • 执行：实际分配行为

• 调度算法

  • 先来先服务（FCFS）

    • 非抢占式

    • 特点

      • 算法简单，但效率低

      • 对长作业有利，对短作业不利

      • 有利于CPU繁忙型，不利于IO繁忙型

  • 短作业/进程优先（SJF/SPF）

    • 非抢占式

      • 抢占式版本：SRTN最短剩余时间优先算法

    • 饥饿现象：可能导致长作业“饥饿”

    • 未考虑作业紧迫程度

    • （所有作业同时可运行时）平均等待时间、平均周转时间最少

      • 没有前提，则SRTN比SJF更少

  • 优先级调度算法

    • 适合实时操作系统

    • 饥饿现象：低优先级作业长时间不被调度

    • 分类[能否抢占]

      • 非抢占式优先级调度算法

      • 抢占式优先级调度算法

    • 分类[优先级能否改变]

      • 静态优先级

      • 动态优先级

        • 调整依据

          • 运行进程占用CPU时间
            就绪进程等待CPU时间

    • 优先级原则

      • 1）系统进程 > 用户进程
        2）交互型进程 > 非交互型进程
        3）IO频繁型进程 > 计算频繁型进程

  • 高响应比优先（HRRN）

    • 非抢占式+动态优先级

    • 主要用于作业调度

    • 响应比

    • 综合了FCFS和SJF

      • 先来等待时间更长（FCFS）

      • 短作业要求服务时间越短（SJF）

      • 克服了SJF中长作业的饥饿现象

  • 时间片轮转（RR）

    • 抢占式

    • 适用于分时系统

    • 时间片过大

      • 退化为FCFS算法

    • 时间片过小

      • 进程频繁切换，处理机开销大

  • 多级队列调度算法

    • 根据进程类型，设置多个不同的就绪队列，每个队列可以应用不同的算法

    • 不同队列的优先级可以不同，
      每个队列内不同进程间的优先级也可以不同

  • 多级反馈队列调度算法

    • 综合了：优先级调度+时间片轮转

    • 算法思想：
      1）多级队列，优先级越高，时间片越小
      2）队列内按照FCFS排队，时间片用完被动剥夺则进入下一级队列，进程主动阻塞回到当前队尾
      3）高优先级队列可以抢占低优先级队列

    • 优点：短作业优先、照顾IO型进程

    • 缺点：有饥饿现象

同步与互斥

• 基本概念

  • 临界资源

    • 访问过程

      • 1）进入区
        2）临界区
        3）退出区
        4）剩余区

    • 临界区访问准则

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

  • 同步（直接制约关系）

    • 两个进程之间直接的合作

  • 互斥（间接制约关系）

    • 由于互斥访问临界资源产生的间接制约

    • 互斥机制必须实现：
      1）空闲让进
      2）忙则等待
      3）有限等待
      不一定要实现让权等待

• 实现方法

  • 基本软件实现

    • 单标志法

      • 两进程严格交替，可能违背“空闲让进”

    • 双标志先检查

      • 两进程可能同时进入临界区（违背“忙则等待”）

    • 双标志后检查

      • 两进程可能互相谦让，导致饥饿

    • 皮特森算法

      • 解决了“饥饿”现象；没有满足让权等待

  • 基本硬件实现

    • 中断屏蔽方法

      • （关中断）

    • 硬件指令方法
      (不会被中断)

      • TestAndSet(TSL)

        • 读标志并置为True

      • Swap(Exchange/XCHG)

        • 交换两个字的内容

      • 优点：适用于任意数目的进程，支持多个临界区（每个临界区设置一个布尔变量）

      • 缺点：不能实现让权等待（忙等）；可能导致“饥饿”现象（不保证有限等待）

  • 互斥锁

    • 进入临界区应获得锁（acquire）
      退出临界区则释放锁（release）
      进程acquire失败，会被阻塞，直到锁被释放

    • acquire和release是原子操作，
      互斥锁通常采用硬件机制实现

    • ？与上面矛盾了

      • 缺点：忙等，acquire连续循环检测锁是否可用，占用处理机资源

  • 信号量（PV）

    • P操作：原语wait(S)
      V操作：原语signal(S)

    • 分类

      • 整型信号量

        • 整型变量S为可用资源数目

        • 进程不断测试，未遵循“让权等待”，可能“忙等”

      • 记录型信号量

        • S={整型变量value，进程链表L}

        • 无资源时(S.value<0)，进程block，进入等待队列S.L（遵循“让权等待”）

        • signal后，若S.value<=0，则调用wakeup原语

    • 应用

      • 同步问题

      • 互斥问题

      • 前驱关系问题

  • 管程

    • 定义：代表共享资源的数据结构及一组访问共享数据结构的过程所组成的资源管理程序

    • 组成

      • 1. 管程的名称

2. 共享数据结构说明（局部于管程内部）

3. 对数据结构的一组操作过程（函数）

4. 共享数据结构的初始化语句

    - 特性（互斥）
   
    	- 管程把对共享资源的操作封装起来；
   

进程通过调用管程内的过程才能访问共享资源；
每次仅允许一个进程进入管程

	- 条件变量（同步）

		- 一个管程拥有多个条件变量，每个条件变量定义了一个阻塞原因，并保存一个等待队列

		- 当x条件不满足时，进程调用x.wait操作

			- 将进程插入x条件的等待队列

		- 当x条件发生了变化时，调用x.signal操作

			- 唤醒一个因x条件而阻塞的进程

• 经典同步问题

  • 生产者-消费者问题

  • 读者-写者问题

  • 哲学家进餐问题

  • 吸烟者问题

死锁

• 死锁时：所有进程处于阻塞态；
  饥饿时：进程处于阻塞或就绪态；
  死循环：进程处于运行态

• 产生原因

  • 系统资源的竞争

  • 进程推进顺序非法

• 必要条件

  • 互斥条件

  • 不剥夺条件

  • 请求并保持条件

  • 循环等待条件

• 充分必要条件

  • 前提：每类资源只有一个；
    在前提下，资源分配图中含圈是死锁的充要条件

• 死锁处理策略

  • 死锁预防

    • 破坏互斥条件

      • 共享系统资源，如Spooling技术共享打印机资源

    • 破坏不剥夺条件

      • 主动释放、被动剥夺（按优先级）

      • 释放资源可能导致前一阶段的工作失效，适用于状态易于保存和恢复的资源，如CPU的寄存器及内存资源

    • 破坏请求并保持条件

      • 预先静态分配方法，一次申请所需全部资源

      • 缺点：资源浪费；“饥饿”现象

    • 破坏循环等待条件

      • 顺序资源分配法

      • 缺点：限制了新类型设备的增加；容易资源浪费

  • 死锁避免

    • 处于安全状态，可避免进入死锁状态；
      进入不安全状态时，便可能进入死锁

    • 银行家算法

      • 通过安全性算法检测状态是否安全

        • 安全性算法举例

          • 安全序列：{P1, P3, P4, P2, P0}

      • 先预分配，检测安全性，再决定是否分配

  • 死锁检测和解除

    • 死锁检测

      • 化简资源分配图

    • 死锁解除

      • 资源剥夺法

        • 挂起死锁进程，抢占其资源

      • 撤销进程法

      • 进程回退法

        • 设置还原点

内存管理

主要功能

• 空间分配与回收

• 地址转换

• 内存空间扩充（虚拟存储技术）

• 内存保护

  • 确保每个进程拥有单独的内存空间

程序装入过程

• 编译

  • *.c（源代码） --> *.o（目标模块）

• 链接

  • 静态链接

    • 程序运行前，链接成装配模块
      1.修改相对地址（形成逻辑地址）
      2.变换外部调用符合

  • 装入时动态链接

    • 装入内存时，边装入边链接

    • 便于修改和更新，便于共享目标模块

  • 运行时动态链接

    • 执行中使用到模块时才链接和装入内存

    • 加快程序的装入过程，节省内存空间

• 装入

  • 绝对装入

    • 只适用于单道程序环境，编译时就知道程序在内存中的绝对地址，装入程序不需要修改程序地址

  • 可重定位装入（静态重定位）

    • 装入时对地址进行一次修改（重定位）

    • 适用于单一连续分配或固定分区分配；
      装入时一次分配全部的内存空间；
      运行期间不能在内存中移动

  • 动态运行时装入（动态重定位）

    • 装入内存后的所有地址仍然为相对地址，
      程序运行时才转换为绝对地址（重定位寄存器）

    • 程序可以分配到不连续的存储区，
      程序可以在内存中移动，
      部分装入即可运行；
      运行期间动态分配内存；
      便于程序段共享

内存保护

• 设置一对上下限寄存器

• 采用重定位寄存器（基地址寄存器）和界地址寄存器（限长寄存器）

交换技术

• 覆盖

  • 用于单一连续或固定分区分配

  • 用户空间分成一个固定区和若干覆盖区

  • 覆盖技术对用户和程序员不透明

• 交换（对换）

  • 换出、换入（中级调度采用的是交换技术）

内存分配管理方式

• 连续分配管理方式

  • 单一连续分配

    • 内存分为系统区和用户区；
      仅有一道用户程序，独享整个用户区

    • 优点：无外部碎片，无须内存保护

    • 缺点：只能用于单任务，有内部碎片，存储区利用率极低

  • 固定分区分配

    • 用户空间划分固定大小区域

• 分区大小相等

• 分区大小不等

    - 需要一张分区使用表
  
    - 程序太大：放不进任何分区，需要覆盖技术
  

程序太小：浪费内部空间，即产生内部碎片

- 动态分区分配（可变分区分配）

	- 没有内部碎片，存在外部碎片（紧凑技术解决）

	- 分配策略

		- 首次适应算法(First Fit)

			- 最好、最快

			- 问题：碎片集中在低地址，每次分配都要经过

		- 邻近适应算法(Next Fit)

			- 循环首次适应算法

			- 性能不如首次适应算法

		- 最佳适应算法(Best Fit)

			- 性能很差，会产生很小的难以利用的碎片，

会产生最多的外部碎片

		- 最坏适应算法(Worst Fit)

			- 性能非常差

	- 需要空闲分区链（表）

		- 考察内存回收的四种情况

• 基本分页存储管理

  • 进程块（Page）：页、页面
    内存块（Page Frame）：页框、页帧
    外存块（Block）：块、盘块

  • 逻辑地址结构

  • 页表项结构

    • 页号（隐含）+ 内存块号

  • 页表映射

    • 逻辑地址---(查页表)--->物理地址

  • 页表寄存器：存放页表在内存中的起始地址

  • 快表

    • 相联存储器TLB

  • 多级页表

    • 顶级页表（页目录）最多只能占用1个页面

• 基本分段存储管理

  • 逻辑地址结构

  • 段表项结构

  • 段表映射

    • 注意检查是否越界（段内偏移量应小于段长）

  • 段的共享和保护

    • 可共享纯代码（可重入代码）和不能修改的数据

    • 存取控制保护、地址越界保护

• 段页式管理

  • 分段VS分页

    • 页表的页号和页内偏移对用户是透明的；
      段表的段号和段内偏移需要用户显式提供

    • 分段管理容易产生外部碎片；
      分页的内存利用率高

    • 分段反映程序的逻辑，有利于共享和保护

    • 分页的地址空间是一维的；
      分段的地址空间是二维的

    • 都需要硬件支持：地址变换机构

  • 逻辑地址结构

  • 关于快表、页表、段表的数量

    • 整个计算机（单核）只有一个TLB（进程切换时会清除）

    • 分段/分页管理，一个进程拥有一张页表/段表

    • 段页式管理：
      每个进程拥有一张段表，每个分段有一张页表

• 虚拟内存管理

  • 应用对换技术，增加了请求调页和页面置换功能

  • 分类：请求分页、请求分段、请求段页式管理

  • 请求分页管理方式

    • 页表项

    • 地址变换过程

    • 页框分配与调页策略

      • 驻留集：分配给某个进程的页框集合
        工作集：某段时间内进程要访问的页面集合

        • 为了防止抖动（频繁的页面调度行为）
          一般驻留集>工作集

      • 内存分配策略

        • 固定分配：进程分配的物理块大小不会改变
          可变分配：进程运行过程中，物理块大小可变

        • 局部置换：仅从分配给进程的物理块中置换
          全局置换：可从空闲物理块中取出一块分配（必为可变分配）

        • 组合成三种策略：

1. 固定分配全局置换

2. 可变分配全局置换（动态增加物理块）

3. 可变分配局部置换（根据缺页频率动态改变驻留集大小）

    	- 调页策略
   
    		- 调页时机
   
    			- 预调页策略
   
    				- 一次调入若干相邻页
   
    			- 请求调页策略
   
    				- 缺页时，请求系统调页（仅调入一页）
   
    		- 调页位置
   
    			- 外存分为文件区和对换区
   
    				- 对换区连续分配；文件区离散分配
   
    			- 对换区空间足够
   
    				- 运行前，将与进程有关文件全部复制到对换区；
   

所有调换都发生在对换区

				- 对换区空间不足

					- 不会被修改的文件：从文件区调入，不必调出

需要修改的部分：在调换区调入调出

				- UNIX方式

					- 第一次调入从文件区；换出后再调入从对换区

					- 已被其他进程调入内存的共享页面，无须再调入

	- 页面置换算法

		- 最佳置换算法OPT

			- 理论最佳，无法实现

		- 先进先出FIFO

			- 存在Belady异常：物理块数增大而缺页故障数不降反增

		- 最近最久未使用LRU

			- 需要寄存器和栈的支持

		- 时钟置换CLOCK

			- 简单CLOCK置换算法

				- 又称最近未使用算法（NRU）

				- 检查访问位（1->0->换出），最多两轮扫描

				- 调入页的访问位置为1

			- 改进型CLOCK置换算法

				- 检查访问位A和修改位M

调入页（A=1，M=0）

				- 最多4轮扫描：

1. 第一轮找A=0,M=0

2. 第二轮找A=0,M=1，同时A:1->0
   重复上面两轮

    				- 淘汰顺序（A/M）：
   

0/0、0/1、1/0、1/1

内存映射文件

• 磁盘文件映射到进程的虚拟地址空间，便可通过地址直接访问文件，而不必执行IO

• 多个进程允许并发地内存映射同一文件，以便允许数据共享

文件管理

文件基本概念

• 文件结构

  • 有结构文件》记录》数据项

    • 基本数据项

    • 组合数据项=多个基本数据项

  • 无结构文件

    • 字符流

• 文件属性

  • 名称、类型、创建者、所有者、位置、大小、保护、创建时间

• 文件控制块（FCB）

  • FCB是文件目录项
    文件目录就是FCB的有序集合

  • 内容

    • 基本信息

    • 存取控制信息

    • 使用信息

• 索引结点（i结点）

  • 文件的描述信息

  • 文件目录项=文件名+指向i结点的指针

  • 分类

    • 磁盘索引结点

      • 每个文件有唯一一个

      • 内容（略）

    • 内存索引结点

      • 文件打开后，在内存中的索引结点

      • 由磁盘索引结点复制到内存中

      • 内容（略）

文件操作

• 创建文件

  • 分配外存空间，创建目录项

• 写文件

• 读文件

• 文件定位

• 删除文件

  • 检索目录项，释放文件空间，删除目录条目

• 截断文件

  • 删除文件内容，长度置0，释放空间

• 打开/关闭文件

  • 打开文件表

    • 两级结构

      • 系统的打开文件表

        • 文件指针

        • 文件打开计数

        • 文件磁盘位置

      • 进程的打开文件表

        • 条目指向系统打开文件表中的条目

        • 文件的访问模式

          • 创建、只读、读写、添加等

  • 打开过程

    • 0.用户通过open系统调用
      1.根据文件名搜索目录，找到文件
      2.将文件复制到内存，在打开文件表中增加条目
      3.将条目编号（索引）返回给用户

  • 关闭过程

    • 0.用户close系统调用
      1.打开计数器递减
      2.若计数器为0，则从打开文件表中删除条目

  • 打开文件表的索引，也称文件描述符（UNIX）或文件句柄（Windows）

文件保护

• 口令保护

  • 时间、空间开销少；
    口令直接存在系统内部，不安全

• 加密保护

  • 文件加密，使用密钥才能解密

  • 保密性强，节省存储空间；
    编码、译码需要时间

• 访问控制

  • 访问类型

    • 读/写/执行/添加/删除/列表清单

  • 访问控制列表

    • 精简的访问列表：拥有者、组、其他

  • 访问控制由文件访问权限和文件属性共同限制

文件目录

• FCB的有序集合，一个FCB就是一个文件目录项

• 目录结构

  • 单级目录结构

    • 按名存取，查找速度慢、不允许重名、不便文件共享，仅适用单用户系统

  • 两级目录结构

    • 主文件目录（MFD）：记录用户文件目录的位置

    • 用户文件目录（UFD）

    • 不同用户的文件可以重名，保护了文件的安全

  • 树形目录结构（多级目录结构）

    • 绝对路径：从根目录出发

    • 相对路径：从当前目录（工作目录）出发

      • 每个用户都有各自的“当前目录”

    • 不便于实现文件共享

  • 无环图目录结构

    • 便于文件共享

    • 为每个共享结点设置一个共享计数器

• 文件共享方式

  • 共享索引结点（硬链接）

    • 多个指针指向同一个索引结点（并计数）

  • 符号链实现（软链接）

    • 快捷方式记录共享文件的路径

文件的逻辑结构

• 用户视角的结构，由用户设计，操作系统不关心

• 无结构文件（流式文件）

• 有结构文件（记录式文件）

  • 三个维度

    • 定长记录VS可变长记录

    • 顺序存储VS链式存储

  • 顺序文件（定长记录）

    • 串结构

      • 记录按存入时间排列，与关键字无关

    • 顺序结构

      • 记录按关键字排序，可折半查找

  • 索引文件

    • 解决变长记录文件只能顺序查找的问题

    • 索引表的表项：记录的指针（地址），长度

    • 索引表本身是定长记录的顺序文件，支持对索引表的随机检索

  • 索引顺序文件

    • 组内无序，组间有序

    • 索引表有序，每个表项指向一个组

    • 索引表项：键值 -->组首地址

    • 类似于分块查找算法

  • 直接文件/散列文件

    • 根据关键字的散列函数值决定物理地址，会引起冲突

文件的物理结构

• 操作系统视角，对用户透明

• 文件的分配方式（非空闲块）

  • 连续分配

    • 顺序读写时，速度最快；
      支持顺序访问和随机访问

    • 优点：实现简单、存取速度快；
      缺点：文件长度不宜动态增加；删除和插入记录需要移动相邻记录；反复增删容易产生外部碎片

    • 适用于长度固定的文件

  • 链接分配

    • 隐式链接（默认）

      • 只适合顺序访问；链表指针丢失会导致数据丢失

      • 按簇分配可以减少查找时间，但增加了内部碎片

    • 显式链接

      • 文件分配表FAT

        • 一个磁盘仅一张，在系统启动时读入内存

        • 文件分配表类似静态链表

        • 记录了各盘块的下一盘块号（-1表示文件的最后一块，-2可表示空闲块）

        • 查找文件分配表在内存中进行，减少了访问磁盘的次数，支持对磁盘的随机访问

  • 索引分配

    • 每个文件拥有一个索引块

      • 相当于进程的页表

      • 索引表项：逻辑块号(隐含) --> 物理块号

    • 索引目录：所有文件的索引块的起始地址

      • 相当于页目录表

    • 优点：支持直接访问，没有外部碎片；
      缺点：增加了存储空间开销

    • 支持大文件的方案

      • 链接方案

        • 多个索引块链接（隐式链接）起来，需要顺序访问索引块，开销较大

      • 多层索引

        • 相当于多级页表

        • k层索引需要访问k+1次磁盘

  • 混合索引分配

    • 全面照顾小、中、大、特大型文件

    • 小文件：直接索引（直接寻址）；
      中文件：单级索引（一次间址）；
      大/特大文件：二级/三级索引

• 文件存储空间管理（空闲块）

文件系统

• 文件系统层次结构

  • I/O控制

    • 设备驱动程序、中断处理程序

    • 负责在内存和磁盘之间传输信息

  • 基本文件系统

    • 向设备驱动程序发送通用命令

    • 管理内存缓冲区（传输前分配缓冲区等）

  • 文件组织模块

    • 将逻辑块地址转换成物理块地址

    • 空闲空间管理器（跟踪未分配的块）

  • 逻辑文件系统

    • 管理元数据信息

      • 元数据包括文件系统的所有结构（目录结构）

      • 可以根据文件名为文件组织模块提供信息

    • 通过FCB维护文件结构

    • 负责文件保护

• 文件系统布局

  • 在磁盘（外存）中的结构

    • 主引导记录MBR

      • 用于引导计算机

    • 分区表

    • 磁盘分区
      （逻辑卷）

      • 引导块（分区引导扇区）

        • 负责启动该分区的操作系统

        • 每个分区都从引导块开始，即使不包含可启动的操作系统

      • 超级块

        • 包含文件系统的所有关键信息

        • 文件系统首次使用时，超级块会被载入内存

        • 包括分区的块的数量、块大小、空闲块的数量和指针、空闲的FCB数量、FCB指针等

      • 空闲空间管理

        • 空闲块信息，如位示图

      • i结点

        • 索引结点

      • 根目录

      • 其他文件和目录

  • 在内存中的结构

    • 安装表

    • 目录结构缓存

    • 系统的打开文件表

      • 特有信息：打开计数

    • 进程的打开文件表

      • 特有信息：打开方式

  • 物理盘和逻辑卷的关系

    • 一个物理盘可以划分成多个分区（逻辑卷）

    • 一个逻辑卷可以包含多个物理盘

    • 每个分区（逻辑卷）拥有单独的文件系统，
      并且目录区和文件区是分离的

  • 操作系统的引导过程

    • ①激活CPU，开始执行BIOS

      • BIOS指令位于ROM（自举装入程序）

    • ②硬件自检

    • ③加载操作系统所在硬盘

      • BIOS指令根据启动顺序加载排序第一的存储设备

    • ④加载主引导记录MBR

      • MBR位于启动盘

    • ⑤扫描硬盘分区表

      • 记录于MBR中

    • ⑥加载分区引导记录PBR

      • 位于活动分区的第一个扇区（引导扇区），用于寻找并激活引导操作系统的程序（启动管理器）

    • ⑦加载启动管理器

    • ⑧加载操作系统

• 外存空闲空间管理

  • 空闲表法

    • 类似于内存的动态分区分配方式

    • 空闲盘块表：序号、第一个盘块号、空闲盘块数

    • 分配算法：首次适应算法、最佳适应算法等

  • 空闲链表法

    • 空闲盘块链

      • 适合离散分配

      • 空闲盘块链会很长

    • 空闲盘区链

      • 与空闲表法类似，但是按链式存储

      • 适合离散、顺序分配

  • 位示图法

    • 离散、顺序分配方式都适用

  • 注：文件分配表FAT（文件的显式链接分配方式）也可以用来管理空闲外存空间

  • 成组链接法

    • 适合大型文件系统

      -  
    
      -  
    

虚拟文件系统VFS

• 功能

  • 向上提供统一接口

    • 为用户屏蔽了不同文件系统的差异

  • 向下要求实现统一接口

    • 新的文件系统只要支持并实现这些接口，即可安装和使用

  • 每打开一个文件，建立一个对应的Vnode

    • 打开文件 -->inode读入内存 -->VFS中建立vnode

    • VFS采用统一的数据结构vnode
      而不同的文件系统采用的数据结构inode不同

    • vnode包含函数功能指针，指向下层文件系统实现的函数功能接口

• 面向对象思想

  • 超级块对象

    • 表示一个已挂载的特定文件系统

  • 索引结点对象

    • 表示一个特定的文件

  • 目录项对象

    • 表示一个特定的目录项

  • 文件对象

    • 表示一个进程相关的已打开文件

• VFS只存在于内存中，随着系统启动而建立，系统关闭而消亡

• 文件系统挂载（安装）

  • 1.在VFS中注册文件系统。在挂载表中记录了各文件系统的相关信息

  • 2.新挂载的文件系统，向VFS提供一个函数地址列表

  • 3.将文件系统加到挂载点，挂载到某个父目录下

I/O管理

I/O软件层次结构

• 1）用户层I/O软件

  • 用户直接调用IO操作库函数

  • 用户层软件通过系统调用方式获取操作系统服务

• 操作系统内核部分
  （IO系统）
  （IO核心子系统）

  • 2）设备独立性软件

    • 也称设备无关性，应用程序独立于具体的物理设备，使用逻辑设备名来请求设备

    • 使用逻辑设备名的好处

      • 增加设备分配的灵活性

      • 易于实现I/O重定向

    • 主要功能

      • 向用户层提供统一接口

      • 对设备进行保护

      • 差错控制

      • 对设备的分配与回收

      • 缓冲管理

      • 将逻辑设备名映射到物理设备名

    • 映射过程

      • 通过LUT（逻辑设备表）将逻辑设备名映射到：
        物理设备名 + 驱动程序地址

  • 3）设备驱动程序

    • 每类设备配置一个设备驱动程序，与硬件直接相关，负责对具体设备发出操作指令

    • 将抽象要求转换为具体要求

    • 检查用户I/O的合法性

    • 与IO控制器之间传递参数：IO状态、IO操作命令，启动IO控制器

    • 响应通道发来的中断请求，根据中断类型调用中断处理程序；构造通道程序

  • 4）中断处理程序

    • 读控制器状态--> IO正常结束？ -->(正常)读取数据，(异常)异常处理

• 5）硬件（机械部件、电子部件）

  • 如I/O控制器

    • 控制IO设备的IO操作

用户层软件

• SPOOLing技术

  • 提高了I/O速度
    将独占设备改造为共享设备；
    实现了虚拟设备功能

  • 输入井&输出井

    • 位于磁盘

    • 存放用户程序要输入或输出的数据

  • 输入缓冲区&输出缓冲区

    • 位于内存

    • 存放设备要输入或输出的数据

  • 输入/输出进程

    • 模拟脱机输入/输出时的外围控制机

  • SPOOLing技术属于用户层软件

应用程序I/O接口

（IO系统与高层接口）

• 字符设备接口

  • 字符设备

    • 键盘、打印机等

    • 特征：传输速率低、不可寻址

    • 采用中断驱动方式

  • 用户接口：get、put方式从缓冲区存取数据

• 块设备接口

  • 块设备

    • 磁盘

    • 特征：传输速率高、可寻址

    • 常采用DMA方式

  • 用户接口：隐藏磁盘的二维结构，将抽象命令映射为低层操作

• 网络设备接口

  • 网络套接字接口（socket）

• 阻塞/非阻塞IO

  • 阻塞I/O（大多数）

    • 用户进程调用IO操作时，进程就被阻塞

  • 非阻塞I/O

    • IO操作返回一个错误的返回值，通常进程需要通过轮询的方式来查询IO操作是否完成

设备独立性软件

（设备无关性）

• 设备分配与回收

  • 设备按特性分类

    • 独占设备

      • 打印机等

      • 通常采用静态分配方式

    • 共享设备

      • 磁盘等

      • 通常采用动态分配方式

      • 必须是可寻址的、可随机访问的

    • 虚拟设备

      • SPOOLing方式

      • 把一个物理设备变换成多个对应的逻辑设备

  • 相关数据结构

    • 设备控制表DCT

      • 代表一个设备

      • 表项：设备的各属性，指向COCT的指针，等待该设备的进程PCB队列（队首指针）

    • 控制器控制表COCT

      • 代表一个设备控制器

        • 一个设备控制器可以控制一个或多个设备

      • 表项：设备控制器的属性，指向CHCT的指针，等待的进程PCB队列（队首/队尾指针）

    • 通道控制表CHCT

      • 代表一个通道

      • 表项：通道的属性，指向COCT集合的指针，等待的进程PCB队列（队首/队尾指针）

    • 系统设备表SDT

      • 整个系统只有一张，记录所有物理设备的情况

      • 一个设备占用一个表目，表目中有指向DCT的指针

    • 逻辑设备表LUT（设备映射表DMT）

      • 表项：逻辑设备名、物理设备名、设备驱动程序入口地址

      • 进程通过逻辑设备名请求设备，系统分配物理设备，并在LUT中建立一个表目。
        之后，进程对该设备的访问可通过逻辑设备名，系统查找LUT表映射到对应的物理设备和驱动程序

      • 两种方式

        • 整个系统LUT

          • 适合单用户系统，不允许逻辑设备重名

        • 每个用户LUT

          • 类似两级目录

  • 设备分配过程

    • 0）进程根据逻辑设备名请求申请设备

    • 1）查找SDT，找到对应设备类型的一个DCT，建立逻辑映射关系（LUT中），将设备分配给进程

      • 若DCT状态忙，将PCB挂到其等待队列

    • 2）根据DCT，找到对应的COCT，分配给进程

      • 若COCT状态忙，将PCB挂到其等待队列

    • 3）根据COCT，找到对应CHCT，分配给进程

      • 若CHCT忙，将PCB挂到其等待队列

    • 4）进程拥有了通道、IO控制器、IO设备的使用权限，设备分配完成

  • 设备分配方式

    • 静态分配

      • 一次性分配作业所需的全部设备、控制器

      • 不会出现死锁，效率低；通常独占设备采用

    • 动态分配

      • 进程通过系统调用请求分配设备，系统根据算法策略分配，使用完成后立即释放

      • 设备利用率高，单容易出现死锁。通常共享设备采用

      • 设备分配算法

        • 先请求先分配、优先级高者先分配等

        • 参考处理机分配

  • 设备分配的安全性

    • 安全分配方式

      • 破坏请求和保持条件

      • 发出IO请求后就阻塞，直到IO完成

      • 安全，但CPU和IO设备是串行工作的

    • 不安全分配方式

      • 可以发出多个IO请求，仅当所请求的设备被占用时，才进入阻塞

      • 优点：可同时操作多个设备，速度快
        缺点：容易死锁

• 缓冲管理

  • 磁盘高速缓存（Disk Cache）

    • 逻辑上属于磁盘，物理上是属于内存中的盘块

  • 缓冲区（Buffer）

    • 缓冲区作用

      • 缓和CPU和IO设备之间速度不匹配的矛盾

      • 减少IO中断频率

      • 解决基本数据单元大小不匹配的问题

      • 提高CPU和IO设备之间的并行性

    • 缓存区分类

      • 单缓冲

        • 缓冲区不能同时输入和输出

        • 用时：max(C,T)+M

      • 双缓冲

        • 用时：max(C+M,T)

      • 循环缓冲

        • 多个缓冲区构成循环队列，需要in和out指针

      • 缓冲池

        • 三个队列

          • 空缓冲队列、输入队列、输出队列

        • 四个工作缓冲区

          • 外存存入输入数据的缓冲区

          • 内存提取输入数据的缓冲区

          • 内存存入输出数据的缓冲区

          • 外存提取输出数据的缓冲区

  • 对比

    • 高速缓存Cache

      • 存放的是可能要访问的数据的复制，命中则访问，不命中仍要访问低速设备

    • 缓冲区Buffer

      • 是高速、低速设备之间传输数据的必经之路，磁盘上不一定有该数据的备份

驱动程序接口

• 操作系统定义一组要求驱动程序支持的函数

• 驱动程序提供函数指针表（指向所实现的功能）

• 装载驱动程序：操作系统记录函数指针表的地址

• 调用函数：操作系统通过函数指针表来间接调用函数

中断处理和设备控制器

• 见计算机组成原理部分