操作系统

1、计算机系统概述

1.1 操作系统的基本概念

操作系统（OS）：控制和管理计算机系统的硬件与软件资源。

操作系统的特征：

  • 并发（最基本）

  • 共享（最基本）：互斥共享、同时访问。制约性。

  • 虚拟：虚拟处理器（多道程序设计技术）、虚拟存储器、虚拟设备。时分复用和空分复用。

  • 异步：多个程序并发执行，没有顺序性

操作系统的目标和功能：

  • 计算机资源的管理者：处理机（进程）管理、存储器管理、文件管理、设备管理。
  • 作为用户与计算机硬件系统之间的接口
    • 命令接口：联机命令接口（命令解释程序、shell、终端），脱机命令接口（批处理）
    • 程序接口：系统调用，操作系统为用户提供服务
  • 实现对计算机资源的扩充

1.2 操作系统发展历程

  • 手工操作阶段
  • 批处理阶段：主要问题是不能与用户交互
    • 单道批处理系统：自动性、顺序性、单道性
    • 多道批处理系统：多道、宏观上并行、微观上串行。多道程序设计技术。提高单机资源利用率，一个程序等待时可以去执行另一个程序。
  • 分时操作系统：同时性（多个终端使用一台计算机）、交互性、独立性、及时性（分时系统的目标是快速响应用户）
  • 实时操作系统
    • 硬实时系统：绝对保证。如飞行控制系统
    • 软实时系统：可以接受偶尔违反时间规定。如订票系统
  • 网络操作系统：网络中各种资源共享和计算机之间的通信
  • 分布式计算机系统：工作可以分布在多台计算机上并行执行

联机与脱机技术

联机是指IO设备直接与主机相连，类似终端，需要等待输入和输出，CPU与IO设备速度不匹配。脱机是指输入输出先到缓存（这部分不需要主机的控制，所以叫脱机），缓存满后再发送给主机或输出到外设，CPU与缓存打交道。脱机技术解决了独占设备的问题（多个设备都可以与缓存交互）。

甘特图画法：横坐标时间，纵坐标程序名；过横坐标的每个时间点作垂直的虚线；用不同的线（直线、波浪线、虚线）代表不同的资源占用，画出各程序的时间片。

1.3 操作系统运行环境

1.3.1 处理器运行模式

特权指令：不允许用户使用的命令。反之为非特权指令。

核心态（也称管态、内核态）可以执行所有指令，用户态（也称目态）只能执行非特权指令。

用户态和核心态之间的转换是通过硬件完成的（如通过置寄存器的某一位的值）。

  • 从用户态进入内核态：访管指令（非特权指令）。
  • 从内核态返回用户态：比如中断返回指令（特权指令）

内核态运行的指令：输入输出（IO一定在内核态，如DMA）、有关访问程序状态、存取特殊寄存器……

用户态运行的指令：可以用汇编语言完成的（读时钟、寄存器操作……）

内核：与硬件关联密切的模块（时钟、中断、设备驱动等）和运行频率较高的程序（进程管理、存储器管理、设备管理等）。内核常驻内存，操作系统的其余部分按需调入内存。如下是内核包括的几方面内容：

  • 时钟管理：提供系统时间、时间片轮转等。需要硬件支持（如计数器）
  • 中断机制：需要硬件支持（如中断隐指令）
  • 原语：具有原子性的一些公共小程序。关闭中断可以定义原语。
  • 系统控制的数据结构（进程控制块PCB、设备控制块等各种块、表、队列）及处理（进程、存储器、设备管理）：系统调用类

1.3.2 中断和异常

flowchart TD
	中断 --> 内部异常
	中断 --> 外部中断
	内部异常 --> 自陷
	内部异常 --> 故障
	内部异常 --> 终止
	外部中断 --> 可屏蔽中断
	外部中断 --> 不可屏蔽中断

外部中断，简称中断：中断信号来源于CPU外部，与当前执行的程序无关。如设备IO（鼠标键盘）、时钟中断、用户强行终止进程。

  • 可屏蔽中断：通过INTR线发出的中断，通过改变屏蔽字可以实现多重中断
  • 不可屏蔽中断：通过NMI线发出，通常是紧急硬件故障，如电源掉电

内部异常：来源于CPU内部，与当前执行的程序有关。

  • 自陷（Trap）：有意而为之的异常。如系统调用
  • 故障（Fault）：指令执行异常，可能被故障处理程序修复。如缺页、除0、运算溢出
  • 终止（Abort）：不可恢复的致命错误。如控制器出错、存储器校验错

软件中断：故障和自陷。程序导致。

硬件中断：终止和外部中断。硬件导致。

中断异常处理过程：

  1. 关中断（硬件）
  2. 保存断点（硬件）：保存PC和PSW
  3. 跳转到中断服务程序（硬件）：以上三步都是硬件完成，称为中断隐指令
  4. 保存现场和屏蔽字：后面都由操作系统完成
  5. 设置新的屏蔽字
  6. 开中断
  7. 执行中断服务程序
  8. 关中断
  9. 恢复现场和屏蔽字
  10. 开中断
  11. 中断返回，断点恢复

引起中断的程序可能是用户程序或OS程序（多重中断），但进入中断处理的程序一定是OS程序。

用户态到核心态的转换是通过硬件中断机制。

中断处理和子程序调用的区别：中断处理程序可能与被中断的程序无关，所以PC、程序状态字寄存器（PSW）、通用寄存器都要保存；而子程序的调用是用户的逻辑，用户就是要利用PSW，所以保存除PSW之外的。

中断时由硬件保护并更新PC，主要是正确可靠，提速是次要的。

初始化中断向量表由OS完成。

1.3.3 系统调用

也叫广义指令。

按功能分：设备管理、文件管理、进程控制（创建撤销等）、进程通信、内存管理。

用户通过陷入指令（访管指令、trap指令）发起系统调用。

调用可能发生在用户态，执行一定在核心态。

系统调用过程：

  1. 传递系统调用参数（如果有）！！！

  2. 执行陷入指令

  3. 执行服务程序

  4. 返回用户态

1.4 操作系统结构

  • 分层法：像计网一样。只能调用紧邻的低层功能，单向依赖。优：便于调试和验证，易扩充维护。劣：定义困难，效率低
  • 模块化：分成相对独立的模块（如进程管理、文件管理……）。用内聚性和耦合度来衡量。
  • 宏内核：windows等主流的操作系统都是。性能高
  • 微内核
    • 将操作系统分为微内核和多个服务器（如进程服务器），C/S架构。
    • 功能：进程管理、低级存储管理、中断和陷入处理
    • 机制与策略分离：机制指具体的执行机构；策略指在机制的基础上实现算法（就像系统调用和利用系统调用写软件）。微内核OS将机制放在微内核，策略放在服务器。
    • 优：可靠性、安全性、可移植性、扩展性灵活性、分布式计算 。劣：性能低（频繁切换用户态和核心态）

1.5 操作系统引导

  1. 激活CPU，读取ROM中的boot引导程序，跳转到BIOS的第一条指令。
  2. （BIOS先创建中断向量表和相应的服务程序，因为在后续的POST中要用到中断）硬件自检（POST，power-on self test）
  3. 加载带操作系统的硬盘。BIOS按boot sequence的顺序将存储设备的引导扇区加载到内存（如果不是可引导的，即非0x55AA，则加载下一个存储设备的），并跳转到其第一条指令。（加载的这个引导扇区就是下面的MBR）
  4. 加载主引导记录MBR。MBR是存储设备的第一个扇区，包含调用操作系统的机器码、硬盘分区表（最多4个主分区，记录了主分区的扇区位置等）、主引导记录签名（0x55AA就是主引导记录）
  5. 扫描硬盘分区表，加载活动分区（只有一个主分区是激活的）
  6. 加载分区引导记录PBR（活动分区的第一个扇区）
  7. PBR搜索活动分区中的启动管理器（如grub），加载启动管理器（也是引导程序）
  8. 加载操作系统

1.6 虚拟机

  • 第一类虚拟机管理程序：类似操作系统。它向上层提供若干虚拟机，可以运行不同的操作系统。上层的操作系统以为自己运行在内核态（其实是虚拟机管理程序的用户态），称为虚拟内核态。
  • 第二类虚拟机管理程序：就是一个普通进程，如VMware。虚拟机上的操作系统叫客户操作系统，本来的叫宿主操作系统。

2、进程与线程

2.1 进程与线程

2.1.1 进程的概念

进程实体（进程映像）：PCB、程序段、数据段

创建进程的实质是创建PCB，撤销进程的实质是撤销PCB。PCB是进程存在的唯一标志。

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

封闭性：进程执行的结果只取决于进程本身，不受外界影响。并发进程会失去封闭性，因为可能和其他进程共享资源，会影响当前进程的执行。

进程之间可能是无关的，也可能是交互的。

父进程与子进程：共享一部分资源，但不能共享虚拟地址空间。

2.1.2 进程的状态与转换

  • 创建态：正在被创建。申请PCB、填写PCB、分配资源。

  • 就绪态：一旦得到处理机，便可立即运行。

  • 运行态：单处理机每个时刻最多一个进程处于运行态（可能都阻塞）。

  • 阻塞态：因等待某一事件而暂停运行。如等待资源、等待IO。

  • 终止态：正常或异常结束。资源释放回收。

运行态→阻塞态：主动；阻塞态→就绪态：被动。

2.1.3 进程的组成

  • 进程控制块（PCB）：调度进程前从中查状态和优先级；调度后根据其中保存的状态恢复现场；运行中与其他进程同步、通信要访问PCB；暂停运行时将上下文环境保存到PCB。

    • 进程描述信息：进程标识符（PID）、用户标识符（UID）
    • 控制和管理的信息：状态、优先级、代码入口地址、程序外存地址……
      • 优先级：时间片用完时可以减少。被唤醒，长期处于就绪队列时可以增加。
    • 资源分配清单：代码段指针、数据段指针、堆栈指针、打开的文件、IO设备
    • 处理机相关信息（上下文）：通用寄存器、地址寄存器、控制寄存器、标志寄存器、状态字

    组织方式有链接方式和索引方式。

  • 程序段：可被多个进程共享。

  • 数据段

C语言程序中

  • .text段：代码、常量
  • .data段：赋值的全局变量
  • .bss段：未赋值的全局变量
  • 堆
  • 栈

2.1.4 进程控制

进程控制用的程序段称为原语，不允许中断。

  • 创建原语：分配PID，申请空白PCB、分配资源、初始化PCB。
  • 终止原语：找到PCB，终止该进程及其子进程，归还资源，删除PCB。
  • 阻塞原语：找到PCB，保护现场，置为阻塞态，插入等待队列。
  • 唤醒原语：找到PCB，从等待队列移出，置为就绪态，插入就绪队列。

2.1.5 进程的通信

  • 共享存储
  • 消息传递：要用系统调用
    • 直接通信：直接发
    • 间接通信：发到某个中间体，信箱
  • 管道通信
    • 管道：两个进程按生产者-消费者方式通信，生产者写，消费者读。单向通信。
    • 数据读空则读阻塞，数据写满则写阻塞。
    • 管道是一个固定大小的缓冲区（Linux中4KB）。
    • 数据一旦读走便不存在了。

2.1.6 线程

“轻量级进程”，是系统独立调度和分派的基本单位，与同一进程的线程共享资源。

状态和进程一样。

线程不拥有系统资源（除一些必不可少、保证独立运行的资源）。

线程创建、撤销、切换的开销小。

线程控制块（TCB）

  • 线程标识符
  • 线程状态
  • 优先级
  • 程序计数器、通用寄存器、状态寄存器、专用的存储区等，保存现场
  • 堆栈指针

线程的实现方式：

  • 用户级线程（ULT）：用户空间完成，内核感受不到。多对一

    • 优：线程切换不需要内核；实现与操作系统无关。

    • 劣：访问内核时，一个线程阻塞，所有线程阻塞；不能发挥多处理机的优势。

  • 内核级线程（KLT）：一对一

    • 优：没有上面的缺点

    • 劣：线程切换需要在核心态进行

  • 组合方式：组合ULT和KLT。多对多

2.2 处理机调度

2.2.1 调度的层次

  • 高级调度（作业调度）：将作业从外存调入内存，分配资源，建立进程。
  • 中级调度（内存调度）：提高内存利用率，将暂时不能运行的进程挂起来（调至外存）。（处于作业调度和进程调度之间）
  • 低级调度（进程调度）

2.2.2 调度的指标

  • CPU利用率

  • 系统吞吐量：单位时间完成作业数量。

  • 周转时间：作业提交到作业完成的总时间。

    • 平均周转时间
    • 带权周转时间：周转时间/作业实际运行时间
    • 平均带权周转时间
    提交时间 开始时间 等待时间 完成时间 周转时间 带权周转时间
    8.8 11 2.2 11.5 2.7 5.4

  • 等待时间

  • 响应时间：提交到系统首次产生响应的时间。

2.2.3 调度的实现

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

  • 处理中断的过程中
  • 进程在操作系统内核的临界区（注意这里是内核，如果是使用打印机这种，则可以切换）
  • 其他原子过程：加锁、解锁、中断保护……

进程调度方式：

  • 非抢占调度（非剥夺）
  • 抢占调度（剥夺）：提高吞吐率和响应效率

闲逛进程：没有就绪的进程就调度闲逛进程运行，优先级最低。

2.2.4 调度算法

调度算法 适用于 是否可抢占 优 劣
先来先服务（FCFS） 批处理 非抢占 不利于短作业，不利于IO繁忙
短作业优先（SJF） 批处理 都可，默认非抢占；可抢占的也称最短剩余时间优先（SRTN） 平均等待、周转时间最少 长作业饥饿
高响应比优先 批处理，分时系统 都可，默认非抢占 兼顾长短 计算响应比有开销
优先级调度 作业、进程调度，实时系统 都可
时间片轮转（RR） 分时系统 抢占，作业到达马上就可以调度 兼顾长短 切换费时
多级反馈队列（MFQ） 通用 队列算法不同 兼顾长短

\[ \text{响应比}=\frac{\text{等待时间}+\text{要求服务时间}}{\text{要求服务时间}} \]

多级反馈队列

  • 多个就绪队列，队列优先级不同
  • 队列时间片不同，优先级越高时间片越小
  • 一个时间片未执行完，放入下一级队列
  • 仅当前面的队列都为空时，才调度这级队列。若前面突然有优先级高的会抢占

优先级

  • 静态优先级：优先级不变
  • 动态优先级：如I/O完成时，提高优先级；时间片用完时，降低优先级

优先级的设置

  • 系统进程>用户进程
  • 交互型进程>非交互型进程
  • IO型进程>计算型进程（IO越早开始越好）

做题时注意：时间片轮转算法中，第一次从就绪队列调入也有开销，也算一次调度！！！

2.3 同步与互斥

2.3.1 同步与互斥的基本概念

临界资源：一次仅允许一个进程使用的资源。

临界区：访问临界资源的代码。

同步：多个进程需要协调工作次序。

互斥：一个进程进入临界区，另一个进程要等待。

空闲让进，忙则等待，有限等待，让权等待（不忙等）

2.3.2 临界区互斥的方法

  • 软件实现：Peterson's Algorithm，turn解决饥饿现象，flag解决临界资源互斥访问。
  • 硬件实现
    • 中断屏蔽
    • 硬件指令
      • TestAndSet：读标志位并置真
      • Swap：交换两个字

互斥锁：缺点是忙等待

2.3.3 信号量

表示资源数目的整型量S。PV操作是低级进程通信原语。

  • wait(S)，即P操作：S--，如果S<0，则阻塞并加入等待队列
  • signal(S)，即V操作：S++，如果S<=0，则唤醒一个

利用信号量实现：

同步：同步信号量的初值一般设为0。先运行的进程V，后运行的进程P。

互斥：PV夹住临界区。互斥信号量的初值一般设为1。

2.3.4 管程

管程包括：

  • 管程名称
  • 局部于管程内部的共享数据结构说明
  • 对该数据结构进行操作的一组过程（如申请、释放）
  • 对管程内部的共享数据结构初始化

每次仅允许一个进程进入管程。

管程是被进程调用的，管程是语法范围，无法创建和撤销。（一个选项）

管程中的条件变量：表示阻塞的原因，每个条件变量中有等待队列、wait操作（插入等待队列）、signal操作（唤醒）。条件变量没有值，信号量有值；信号量反映剩余资源数，管程中用共享数据结构记录。

2.3.5 经典同步问题

互斥访问就用一个mutex，各自需要的资源分别用一个信号量。

  • 生产者、消费者

    semephore mutex=1;		// 用于互斥访问缓冲区
semephore empty=n;		// 生产者需要的资源：空缓冲区
semephore full=0;		// 消费者需要的资源：放了东西的缓冲区 
    
// 生产者
P(empty);
P(mutex);
;
V(mutex);
V(full);

// 消费者
P(full);
P(mutex);
;
V(mutex);
V(empty)；

  • 读者写者

    int count=0;			// 读者数量
semephore mutex=1;		// count互斥访问！！！
semephore write=1;		// 写资源

// 读者
P(mutex);
if (count == 0)
    P(write);
count++;
V(mutex);
;
P(mutex);
count--;
if (count == 0)
    V(write);
V(mutex);

// 写者
P(write);
;
V(write);

2.4 死锁

2.4.1 死锁的概念

死锁的必要条件：

  • 互斥条件
  • 不剥夺条件
  • 请求并保持条件：本身占有资源并要求其他资源
  • 循环等待条件：存在进程资源循环等待链
    • 资源分配图含圈不一定死锁，因为资源可能有多个
    • 如果每类资源都只有一个，则含圈是死锁的充要条件

2.4.2 死锁预防

破坏一些必要条件，让死锁不会发生。

  • 破坏互斥条件：不可行
  • 破坏不剥夺条件：不建议
  • 破坏请求并保持条件：进程运行前一次申请完所需要的全部资源
  • 破坏循环等待条件：给资源编号，进程必须按编号递增顺序请求资源

2.4.3 死锁避免

用算法防止系统进入不安全状态。

安全状态：系统按某种顺序为进程分配资源，使每个进程都能完成。

不安全状态并非马上死锁，只有当进程提出资源申请且全部进入阻塞态时才死锁。死锁一定不安全，安全一定不死锁。

银行家算法

  • 数据结构

    • 可利用资源向量（Available）

    • 最大需求矩阵（Max）

    • 分配矩阵（Allocation）：已分配的资源

    • 需求矩阵（Need）：Need = Max - Allocation

    • 请求向量（Request）

    • 工作向量（Work）：当前可以分配的资源

  • 算法

    • 进程\(P_i\)发出\(Request_i\)请求向量
    • 如果\(Request_i[j]\le Need[i,j]\)，则下一步；否则报错，因为他申请的资源超过Max了
    • 如果\(Request_i[j]\le Available[j]\)，则下一步；否则资源不够，阻塞
    • 试着把资源分给\(P_i\)，执行安全算法，若安全则分配；否则恢复原来的分配，阻塞

2.4.4 死锁检测和解除

资源分配图

  • 圆圈表示进程，框代表一类资源，框中的圆圈代表一类资源中的一个
  • 请求边：进程到资源的有向边
  • 分配边：资源到进程的有向边

死锁定理：当资源分配图不可完全化简则死锁

死锁解除：资源剥夺法、撤销进程法、进程回退法

3、内存管理

3.1 内存管理概念

3.1.1 程序运行基本原理

编译→链接→装入

链接

链接的本质就是合并相同的节（.text .data等）。链接时形成逻辑地址

  • 静态链接：在编译阶段直接把静态库加入到可执行文件中去，这样可执行文件会比较大
  • 动态链接：链接阶段仅仅只加入一些描述信息，而程序执行时再从系统中把相应动态库加载到内存中去
    • 装入时动态链接：边装入边链接
    • 运行时动态链接：程序执行中需要该模块时才链接

装入

  • 绝对装入：编译时将绝对地址写入目标代码，只适用于单道程序环境。
  • 可重定位装入（静态重定位）：在装入时修改地址。不能用于动态分区分配、页式、段式
  • 动态运行时装入（动态重定位）：内存中的地址是相对地址，真正执行时才转换

进程的内存映像

  • 代码段：包括.text段、只读数据
  • 数据段
    • .data：已初始化的全局变量和静态变量，在可执行文件中
    • .bss：未初始化以及初始化为0的全局变量和静态变量，不在可执行文件中，由操作系统分配
  • 堆：malloc
  • 栈
  • PCB

内存保护：保证不越界访问

  • 上下限寄存器
  • 基地址寄存器（重定位寄存器）用来加相对地址；限长寄存器（界地址寄存器），用于比较相对地址是否越界

覆盖技术可用于：单一连续分配、固定分区分配

3.1.2 连续分配管理方式

  • 单一连续分配：用户区仅有一道用户程序
  • 固定分区分配：将内存划分为固定大小的区域（分区大小可以相等或不同），每个分区只装入一道作业
    • 程序可能太大而放不进任何一个；程序太小时有内部碎片（分区内的碎片）
  • 动态分区分配（可变分区分配）：存在外部碎片（分区外部），可以通过紧凑技术解决。用空闲分区链表来存储。
    • 首次适应算法（First Fit）：最好最快。低地址部分碎片多
    • 邻近适应算法（Next Fit）：从上次查找的结束位置继续查找。尾部碎片多
    • 最佳适应算法（Best Fit）：性能差，碎片最多
    • 最坏适应算法（Worst Fit）：没有大内存块

3.1.3 分页存储管理

进程中的块：页；内存中的块：页框；磁盘中的块：盘块。

页表寄存器（PTR）：存放页表起始地址（多级的话存放顶级页表的起始地址）和页表长度。（只有1个）

页表项存储：块号（第几块物理页）、或其他信息

  • 基本页表

    每个进程一个页表，页表一般常驻内存。

    • 取出页号P，看页号是否越界（P与M比较）

    • \(\text{页表项地址}=\text{起始地址}F+\text{页号}P\times\text{页表项大小}\)，从该地址取出块号b

    • b拼接页内偏移W得到物理地址

  • 具有快表的页表

    快表（TLB）：相联存储器。快表中存页号和块号。

  • 两级页表

    • 顶级（一级）页表最多只能1一个页
    • 一级页表存二级页表的块号，二级页表存物理地址的块号

3.1.4 分段存储管理

分段由用户编程决定。页式系统，页号、页偏移量对用户透明；段式系统，段号、段内偏移由用户提供。

分段存储管理有利于程序的动态链接（都与逻辑结构相关）。

满足用户要求：方便编程、分段共享、分段保护、动态链接、动态增长。

段的共享：两个进程段表中的一项指向被共享的段。

段表存储：段长、基址

3.1.5 段页式管理

每个进程一张段表，每个分段一张页表。

段表存储：页表长度、页表始址

如果还有快表的话，快表项包括：段号、页号、块号、其他位

3.2 虚拟内存管理

3.2.1 虚拟内存基本概念

  • 多次性：作业运行无需一次性装入内存
  • 对换性：暂时不需要的换出，需要时换进
  • 虚拟性：扩充内存。最重要！

需要硬件支持：一定容量的内外存、页/段表机制、中断机构、地址变换机构

3.2.2 请求分页管理方式

页表项

  • （页号）
  • 物理块号
  • 状态位：是否调入内存
  • 访问字段/引用位（R，reference）：置换算法用
  • 修改位（M，modify）
  • 外存地址：供调页时参考

中断机构

缺页属内部异常中的故障。一条指令执行可能多次缺页。

驻留集：给一个进程分配的物理页框的集合

内存分配策略

  • 固定分配局部置换：为每个进程分配固定数量的物理块，只能从自己的页中置换

    固定分配如何将空闲块分给各个进程：

    • 平均分配
    • 按比例分配
    • 优先权分配

  • 可变分配全局置换：为进程分配的物理块可变，缺页时系统从空闲物理块队列中取出一块分给该进程

  • 可变分配局部置换：只能从自己的页中置换；如果频繁缺页，系统多分配一点，如果缺页特别低，适当减少

调入页面的时机

  • 预调页：一次调入若干相邻的页。可能用不到相邻的页。
  • 请求调页：需要的页不在内存再调。（多用）

从何处调入：外存分为文件区和对换区（IO速度快）

  • 对换区足够：进程运行前从文件区复制到对换区，之后内存都与对换区对换
  • 对换区不够：只读文件从文件区调（无需换出），可能修改的换出时调到对换区
  • UNIX方式：第一次都从文件区调，换出时调到对换区

3.2.3 页面置换算法

  • 最佳置换算法（OPT）：理想的，无法实现。置换将来最长时间内不再被访问的。

  • 先进先出置换算法（FIFO）

    • Belady异常：分配的物理块增加，缺页率反而增加。其他算法都没有。

  • 最近最久未使用置换算法（LRU）：置换最近最长时间未访问的页面。堆栈类算法。

  • 时钟置换算法（CLOCK）

    • 简单CLOCK置换算法（最近未用算法NRU）（二次机会算法）

      每块一位访问位，装入或访问时置1。替换时，若指针所指访问位为1则置0，指针++继续看下一个块；为0则替换该页，指针++。（每个页有一次不被换出的机会）

      与LRU的直观区别（个人理解）：LRU淘汰最久未使用的，NRU指针转一圈之后访问位为0的都算是最久未使用的，替换哪一个取决于当前指针的位置

    • 改进CLOCK置换算法

      还要看修改位，优先置换访问位=0且修改位=0的（类型1），其次访问位=0修改位=1的（类型2）

      算法：第一次扫描不改变访问位，看有没有类型1的；如果没有则第二次扫描，扫描过的访问位置0，如果有访问位为0的则替换；如果第二次还没找到，第三次扫描一定有

3.2.4 其他概念

抖动：频繁的页面调度行为。

工作集：最近一段时间内进程访问的页面集合。

驻留集：分配给进程的物理块集合。

内存映射文件：将磁盘的部分或全部与进程虚拟地址空间的某个区域建立映射关系。可用于共享内存。

虚拟存储器影响性能的因素：页面大小、分配给进程的物理块数、写回磁盘的频率（页缓冲队列：将要写回的页面连成队列，一起写入）、程序的局部性

虚拟存储器的最大容量是由计算机的地址结构决定的。

4、文件管理

4.1 文件系统基础

数据项→记录→文件

文件控制块（FCB）

文件目录：FCB的有序集合。

索引结点：和文件名分开，保存文件的描述信息。UNIX系统中叫i结点（iNode），UNIX文件目录的目录项仅由文件名和指向i结点的指针构成。

文件的打开（open系统调用）：根据文件名搜索目录，将其磁盘iNode复制到活动iNode表中（将文件的目录项复制到内存的指定区域），为文件分配用户打开文件表表项和系统打开文件表表项，将文件描述符fd返回。

open系统调用需要文件名；read不需要文件名，只需要文件描述符。

文件保护：访问控制列表（ACL）。精简的访问列表：拥有者、组、其他。加密保护安全性高，灵活性不好；访问控制灵活性高，安全性一般。

  • 文件的逻辑结构：从用户观点看文件的组织。

    • 无结构文件：流文件
    • 有结构文件
      • 顺序文件：查找得从头顺序查找，当然可以排序后二分
      • 索引文件：将每条记录的信息（指针、长度等）存到索引表中。索引中记录的地址是逻辑地址。
      • 索引顺序文件：结合上面两个，先根据索引找到一组，再在一组中顺序查找
      • 直接文件（散列文件）

  • 文件的物理结构：文件在存储器上的组织结构

    • 连续分配

    • 链接分配

      • 隐式链接：目录项含有第一块和最后一块的指针，除最后一块每个盘块都含有下一个盘块的指针。只能顺序访问
      • 显式链接：有一张文件分配表（FAT），每个表项的指针指向下一个盘块号，没有下一块则为-1，空闲块为-2。文件目录中存第一块的块号。（类似啊哈算法中的邻接表）FAT不仅记录了各个块的链接关系，还标记了空闲磁盘块。

    • 索引分配：将一个文件的盘块号放在一起，形成索引块。解决索引块无法支持大文件，有以下方案：

      • 链接方案：将多个索引块链接起来

      • 多层索引

      • 混合索引：小文件直接从FCB中获得盘块地址；中文件单级索引；大文件多级索引

        UNIX系统中：索引结点有13个地址项。10个直接地址40KB（如每个块4KB）；1个一次间接地址1024*4KB=4MB（每个块存1024项）；1个二次间接地址4G；1个三次间接地址4T。

    连续分配和索引分配都可以直接存取（随机存取）。

对一个文件的访问，常由用户访问权限和文件属性共同限制。

做题时问磁盘块访问次数，读一块、写一块都算一次访问。链接分配得一块一块找，连续分配和索引分配可以从目录项中读。

4.2 目录

目录管理的要求：实现“按名存取”；提高检索速度；为方便文件共享，提供访问控制信息；允许不同用户对不同的文件采用相同的名字。

目录结构

  • 单级目录
  • 两级目录
  • 树形目录：绝对路径、相对路径
  • 无环图目录：方便实现文件共享，指针指向共享结点，共享结点有共享计数器，当其值为0时才能删除该结点。

目录的实现：线性列表、哈希表（少）

文件共享

  • 硬链接（基于索引节点的共享）：文件目录中只包含文件名和指向索引节点的指针，多个文件的指针指向同一个索引节点，索引节点中有链接计数器。
  • 软链接（符号链接）（利用符号链实现文件共享）：软链接文件中只包含被链接文件F的路径，当使用该文件时，根据路径去找F。只有F才有指向索引节点的指针。（软连接时，引用计数值直接复制，之后F的计数值变了它也不变，因为它不知道）。

整个系统只有一个打开文件表。共享一个文件时不同用户的打开文件表不一定相同，比如读写指针位置不同。

4.3 文件系统

组成：文件管理软件、被管理的文件、所需数据结构

4.3.1 文件系统的结构

\[ \text{应用程序}\Leftrightarrow\text{逻辑文件系统}\Leftrightarrow\text{文件组织模块}\Leftrightarrow\text{基本文件系统}\Leftrightarrow I/O\text{控制}\Leftrightarrow\text{设备} \]

  • I/O控制：包括设备驱动程序、中断处理程序。
  • 基本文件系统：向设备驱动程序发送通用命令。内存缓冲区。
  • 文件组织模块：将逻辑地址转换成物理地址
  • 逻辑文件系统：管理目录结构，文件保护

4.3.2 文件系统布局

  • 文件系统在磁盘中的结构：一个磁盘的结构
    • 主引导记录（MBR）
      • 分区表：其中一个分区是活动分区
    • 分区：
      • 引导块：启动操作系统
      • 超级块：文件系统的关键信息（块的数量、大小，空闲块、FCB数量、指针……）
      • 空闲块信息
      • （可能有iNode、根目录等）
      • 文件和目录
  • 文件系统在内存中的结构
    • 安装表：已安装文件系统分区信息
    • 目录缓存
    • 系统的打开文件表
    • 每个进程的打开文件表：包含指向系统打开文件表条目的指针

4.3.3 外存空闲空间管理

卷：包含文件系统的分区。卷可以是磁盘的一部分、整个磁盘、多个磁盘（RAID）。卷中的目录区和文件区分离。

  • 空闲表法：类似内存的动态分配，首次适应、最佳适应……

  • 空闲链表法

    • 空闲盘块链：以盘块为单位，分配回收简单，效率低
    • 空闲盘区链：一个盘区包含若干盘块，分配回收复杂，效率高

    空闲表和空闲链表法不适用于大型文件系统。

  • 位图法

  • 成组链接法：UNIX系统

4.3.4 虚拟文件系统（VFS）

  • 超级块对象
  • 索引节点对象
  • 目录项对象：在磁盘上没有对应的数据结构，是为了切换目录方便而设计的
  • 文件对象

4.3.5 分区和安装

一个磁盘可以有多个分区，每个分区都可以有单独的文件系统和操作系统。

5、输入/输出管理

5.1 I/O管理概述

按信息交换单位分类

  • 块设备：以块为传输单位的设备，每个块可以独立于其他块进行读写。例如：硬盘、CD-ROM、U盘等
  • 字符设备：以字符为单位发送或者接收字符流的设备，不可寻址。例如：打印机、网卡、鼠标等

设备控制器：参见计组中的图。由CPU与控制器接口（有数据、状态、控制寄存器，没有地址寄存器）、I/O逻辑、控制器与设备接口组成。

IO控制方式：四种参见计组笔记，操作系统中补充了通道控制。

I/O软件层次结构

  • 用户层IO软件：IO库函数
  • 设备独立性软件（与设备无关的软件）：提供和设备驱动程序的统一接口、缓冲、错误报告、设备分配。逻辑设备和物理设备转换。解析命令交给下层。
  • 设备驱动程序：与硬件相关，每类设备配置一个设备驱动程序。针对不同的设备把命令解析成不同的指令
  • 中断处理程序：解析完毕后，发起中断，开始IO

数据结构

  • 设备控制表（DCT, Device Control Table）：每个设备一张，描述设备特性和状态。反映设备的特性、设备和控制器的连接情况。
  • 控制器控制表（COCT, COntroller Control Table）：每个设备控制器一张，描述I/O控制器的配置和状态。如DMA控制器所占用的中断号、DMA数据通道的分配。
  • 通道控制表（CHCT, CHannel Control Table）：每个通道一张，描述通道工作状态。
  • 系统设备表（SDT, System Device Table）：系统内一张，反映系统中设备资源的状态，记录所有设备的状态及其设备控制表的入口。

共享设备是指一段时间内允许多个进程同时访问的设备。（不是同一时间！！！）

共享设备必须是可寻址和可随机访问的设备。

虚拟设备是指把一个物理设备变换成多个对应的逻辑设备。

字节多路通道用作连接大量的低速或中速IO设备。

区分硬件和识别设备的代号称为设备的绝对号。

5.2 设备独立性软件

设备独立性软件：执行所有设备公有操作的软件。

5.2.1 磁盘高速缓存

利用内存中的存储空间来暂存从磁盘中读出的盘块信息。磁盘高速缓存逻辑上属于磁盘，物理上属于内存。

5.2.2 缓冲区

（除了硬件缓冲器，）一般位于内存。

目的：解决速度不匹配；放宽CPU对中断响应时间的限制；解决数据单元不匹配；提高CPU和IO的并行

设：T为磁盘输入一块数据到缓冲区的时间；M为操作系统将缓冲区的数据传送到用户区（工作区）的时间；C为CPU处理时间。

每块数据的处理时间：假设一种初始状态，下一次到达同样状态所需的时间。

  • 单缓冲：TC并行，M和TC串行。每块数据处理时间为：\(max(C,T)+M\)

  • 双缓冲：设初始状态为缓冲区一个满一个空，工作区空。每块数据处理用时为：\(max(C+M,T)\)

  • 循环缓冲：每个缓冲区有一个指针指向下一个缓冲区，最后一个指向第一个。

  • 缓冲池

    • 三个队列：空缓冲队列、输入队列（装满输入数据的缓冲队列）、输出队列
    • 输入时，从空缓冲队列摘下一个空缓冲区，用来收容输入数据，装满后挂到输入队列尾；进程需要输入数据时，从输入队列取下一个缓冲区提取数据，用完后挂到空缓冲队列尾。输出同理。

可以使用缓冲技术的：鼠标、磁带驱动器、磁盘驱动器、显卡……

5.2.3 设备分配与回收

三种设备：独占设备、共享设备、虚拟设备（SPOOLing）

静态分配：系统一次性分配所需的全部设备

动态分配：需要时通过系统调用请求分配

独占设备多静态分配（动态也可），共享设备一般动态分配。

逻辑设备表（LUT）：将逻辑设备名映射为物理设备名。

5.2.4 SPOOLing技术（假脱机技术）

把独享设备转变成具有共享特征的虚拟设备，从而提高设备利用率。例如：打印机设备（独享）和打印机管理器管理的打印作业队列（共享）

联机：直接输入输出到CPU

脱机：\(IO\text{设备}\Leftrightarrow\text{外围机}\Leftrightarrow\text{磁盘}\Leftrightarrow CPU\)

假脱机：虚拟化外围机，物理设备连着主机，但逻辑上脱离

SPOOLing系统组成：

  • 输入井和输出井：磁盘上开辟的两块空间，模拟脱机中的磁盘
  • 输入缓冲区和输出缓冲区：内存中开辟的缓冲区，暂存输入设备的输入数据或输出井的输出数据
  • 输入进程和输出进程：模拟脱机时的外围控制机

特点：

  • 提高IO速度，将访问低速设备转化为访问磁盘
  • 将独占设备改造成共享设备
  • 虚拟设备，对每个进程而言都好像它们独占了设备

SPOOLing系统由预输入程序、井管理程序、缓输出程序管理。

构成SPOOLing系统要有高速大容量、可随机存取的外存支持，还要有SPOOLing软件。

5.3 磁盘和固态硬盘

5.3.1 磁盘

磁道：所有盘片位置相同的磁道组成柱面

扇区（盘块）：最小可寻址单位

簇（Linux中称块）：多个相邻的扇区。一簇只能存放一个文件的内容，文件占用的空间是簇的整数倍。

磁盘地址：柱面号·盘面号·扇区号。为什么是柱面号在前？连续读磁盘块时先遍历盘面号，最后才遍历柱面号，减少磁头移动消耗时间。

簇号转换成磁盘物理地址由磁盘驱动完成。

RAID（廉价磁盘冗余阵列）

  • RAID-0：提高了磁盘I/O速度，无冗余校验。至少1块磁盘
  • RAID-1：镜像磁盘冗余阵列，将每一数据块重复存入镜像磁盘；读操作可以使用任意副本，性能翻倍。至少2块磁盘
  • RAID-2：海明码，将数据位交叉写入几个磁盘中，多个磁盘来存放海明校验码信息；并行存取
  • RAID-3：奇偶校验，数据位交叉，只有一个校验盘
  • RAID-4：独立传送磁盘阵列（在RAID3中，一次磁盘访问将对磁盘阵列中的所有磁盘进行操作），数据块交叉，一个校验盘
  • RAID-5：独立传送磁盘阵列，数据块交叉，分布的冗余校验，数据和校验都分布在各个磁盘中。至少3块磁盘
  • RAID-6：双维校验独立存取盘阵列，数据块交叉，检、纠错信息均匀分布在所有磁盘上，存储开销是RAID5的两倍（多一个冗余盘），更好的可靠性。至少4块磁盘

总结：RAID-0提速无容错，RAID-1磁盘镜像，RAID-2海明码多校验盘，RAID-34单校验盘，RAID-56校验分布在各个盘，RAID-456以数据块为单位

5.3.2 磁盘管理

磁盘初始化和分区

  • 低级格式化（物理格式化）：为空白磁盘划分扇区，以便能读写。为每个扇区采用特别的数据结构，包括校验码
  • 分区：将磁盘分为由一个或多个柱面组成的分区，C盘、D盘
  • 高级格式化（逻辑格式化）：创建文件系统，将文件系统数据结构存储到磁盘，包括空闲和已分配的空间、初始为空的目录

坏块：用某种机制使系统不使用坏块

磁盘空间管理：见4.3.3

5.3.3 磁盘调度算法

  • 寻道时间（占用最长）：磁臂启动时间+跨越n条磁道的时间，\(T_s=m\times n+s\)
  • 旋转延迟时间：即旋转半周的时间。转速r，\(T_r=\frac{1}{2r}\)
  • 传输时间：读写字节数b，一个磁道N字节，\(T_t=\frac{b}{rN}\)。读一个扇区的时间即划过一个扇区的时间

数据传输速率：转速*单个磁道大小

磁盘调度算法（减少寻道时间）：

  • 先来先服务（FCFS）：按顺序寻道
  • 最短寻道时间优先（SSTF）：选择离当前磁头最近的磁道。有饥饿现象
  • 扫描算法（SCAN）（电梯调度算法）：像电梯一样来回扫描（扫描时要移动到两边的端点）。不利于远离磁头一端的访问
  • 循环扫描算法（C-SCAN）：只向一个方向扫描，到底后回到起点。消除了两端磁道请求的不公平

在SCAN和C-SCAN中，磁头严格从盘面一端到另一端，可以优化为到达最远端的请求即可返回，改进之后的算法分别称为LOOK和C-LOOK调度。（实际做题时默认SCAN、C-SCAN就是LOOK、C-LOOK）

减少延迟时间：

  • 对盘面扇区交替编号
  • 对不同盘面错位命名

寻道和延迟时间可以通过方法削减，传输时间不能

提高磁盘IO速度的方法：

  • 提前读
  • 延迟写
  • 虚拟盘：用内存空间仿真磁盘

5.3.4 固态硬盘

由多个闪存芯片和闪存翻译层组成。

一个闪存有多块，一块有多页。数据以页为单位读写，但只有这一页所属的块整个被擦除后才能写一页。

随机写比读慢（但还是比磁盘快）。

磨损均衡：动态磨损均衡（自动选择较新的块）、静态磨损均衡（更先进，就算没有数据写入也会自动检测）

固态硬盘相对磁盘的主要优势是随机存取速度，不是连续存取速度。

课程笔记
#考研 #操作系统
操作系统
https://shuusui.site/blog/2023/08/29/os/
作者
Shuusui
发布于
2023年8月29日
更新于
2023年11月29日
许可协议