操作系统

一、概览

1. 操作系统：系统软件

• 功能
  • 管理CPU、存储器、文件、设备
  • 命令接口 ：用户可直接调用
    • 联机命令接口：交互式命令接口，说一句做一句
    • 脱机命令接口：批处理命令接口，说一堆做一堆
  • 程序接口：用户间接调用
  • GUI：图形用户接口

• 特征

  • 并发
  • 共享
    • 互斥共享：一个时间段只允许一个进程访问资源
    • 同时共享：一个时间段允许多个进程（并发、并行）访问
  • 虚拟：一个物理实体（实际存在）变为若干逻辑对应物（用户感受到的）
    • 空分复用：虚拟内存器
    • 时分复用：虚拟处理器
  • 异步：受资源有限，推进速度不可预知

    2. 运行机制

• 指令

  • 特权指令：不允许用户程序使用，如内存清零指令
  • 非特权指令：如普通运算指令
• 处理器状态：有程序状态字寄存器（PSW）中某标志位来标识，如 0 用户态，1 核心态
  • 用户态（目态）：CPU 只能执行非特权指令
  • 核心态（管态）：两种指令都行

• 内核程序、应用程序

  3. 体系结构

  

  二、中断和异常

• 中断：用户态转换为核心态，核心态转用户态通过执行特权指令将程序状态字（PSW）改为用户态

  • 中断后，CPU 进入核心态，当前进程暂停，由操作系统内核处理中断
• 内中断（异常）：信号来源 CPU 内部，和当前执行指令有关
  • 自愿中断：指令中断（系统调用）
  • 强迫中断：硬件故障（缺页中断）、软件中断（除 0 异常）

• 外中断：信号来源 CPU 外部，和当前执行指令无关

  • 外设请求（I/O 操作完成发出信号）、人工干预（用户强行终止进程）

    三、进程

    1. 进程实体（进程映像）

    创建、撤销一个进程就是创建、撤销进程实体的 PCB

• 进程控制块（PCB）

  • 进程描述信息
    • 进程标识符 PID：用于区分不同进程，可变
    • 用户标识 UID：程序安装就赋予，不变
  • 进程控制和管理信息
    • 进程当前状态
    • 进程优先级
  • 资源分配清单
    • 程序段指针
    • 数据段指针
    • 键盘、鼠标
  • 各种寄存器值：如程序计数器的值标识当前程序哪一句
• 程序段：程序代码存放位置

• 数据段：程序运行时使用、产生的数据

  2. 进程组织方式

• 链接方式

  • 按进程状态将 PCB 分为多个队列
  • 操作系统持有各队列指针

• 索引方式
  • 根据进程状态建立几张索引表
  • 操作系统持有各索引表指针

3. 进程特征

• 动态性：动态产生消亡
• 并发性：可并发执行
• 独立性：可独立运行，基本单位
• 异步性：推进速度不可预知

• 结构性：进程实体三部分

  4. 进程生命周期

• R，TASK_RUNNING：就绪态或运行态，就绪可以运行，但不一定正占有 CPU

• S，TASK_INTERRUPTIBLE：浅度睡眠，等待资源，可响应信号，一般是进程主动 sleep 进入
• D，TASK_UNINTERRUPTIBLE：深度睡眠，等待资源，不响应信号，如进程获取信号量阻塞
• Z，TASK_ZOMBIE：僵尸态，进程已退出或结束，但父进程不知道，没有回收时的状态

• T，TASK_STOPED：停止，调试状态，收到 SIGSTOP 信号进程挂起

  5. 进程状态

• 运行态：占有 CPU 运行

• 就绪态：具备运行条件，没有空闲 CPU
• 阻塞态：因某事暂时不能运行
• 创建态：进程正被创建，操作系统分配资源、初始化 PCB
• 终止态：进程从系统中撤销，操作系统回收所有资源，撤销 PCB
• 就绪挂起状态：挂起与阻塞相比都是暂时不能获得 CPU，挂起是调到外存，阻塞的进程映像还在内存
• 阻塞挂起状态

6. 进程操作

• 原语控制进程，执行期间不允许中断，使用开、关中断指令，需在核心态下执行
  • 更新 PCB 信息
    • 修改进程状态标志
    • 保存运行环境，剥夺当前运行进程 CPU 使用权
    • 恢复运行环境
  • 将 PCB 插入合适队列
  • 分配、回收资源
• 进程的创建

• 进程的终止

• 进程的阻塞和唤醒

• 进程的切换

7. 进程通信

• 共享存储：互斥，通过同步互斥工具（P、V 操作）
  • 基于数据结构：速度慢、限制多、低级通信
  • 基于存储区：速度更快，高级通信
• 消息传递，以格式化消息为单位
  • 发送、接收消息两个原语组成
  • 消息头：发送、接收进程 ID，消息类型、长度
  • 消息体：消息先发送到中间实体（信箱）
  • 直接通信：消息直接挂到接收进程的消息缓存队列
  • 间接通信

• 管道通信：固定大小的缓冲区，半双工，全双工要两个管道

  • 以字符流写入管道，管道写满后 write() 系统调用阻塞，当管道为空，read() 系统调用阻塞
  • 数据读走就没了，可能出现读错情况

    8. 线程

    • 轻量级进程，CPU 基本执行单位，程序执行流最小单位，提升并发度
    • 唯一的整数线程ID、栈、栈指针、PC、通用目的寄存器和条件码

• 属性

  • 多 CPU 计算机中，各个线程可占用不同 CPU
  • 每个线程有一个线程 ID、线程控制块（TCB）
  • 线程有就绪、阻塞、运行三种基本状态
  • 线程几乎不占有进程资源
  • 同一进程的线程共享进程资源，通信无干预，切换不会引起进程切换，切换系统开销小（切换不同进程系统开销大）
• 用户级线程
  • 由应用程序通过线程库实现，所有线程管理工作由应用程序负责（包括线程切换，在用户态下完成）
  • 用户看起来多线程，操作系统内核意识不到
• 内核级线程
  • 线程调度、切换等由操作系统内核完成，核心态
• 二者组合
  • 内核级线程才是处理机分配单位
  • 多对一模型：多个用户级线程映射到一个内核级线程
    • 优点：切换在用户空间完成，不需切换到核心态，线程管理开销小，效率高
    • 缺点：一个用户级线程阻塞后，整个进程阻塞，并发度不高，不能完全利用多核处理机
  • 一对一模型：一个用户级线程映射到一个内核级线程
    • 优点：并发能力强，可在多核处理机并行
    • 缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需切换到核心态，线程管理成本高，开销大
  • 多对多模型：n 个用户级线程映射到 m 个内核级线程，两者的折中

• 与进程资源对比

  • 进程
    • 私有：地址空间、堆、全局变量、栈、寄存器
    • 共享：代码段、公共数据、进程目录、进程ID
  • 线程
    • 私有：线程栈、寄存器、程序计数器
    • 共享：堆、地址空间、全局变量、静态变量

      9. fork

• 父子进程对内存资源（mm）的管理使用了 COW（Copy-On-Write，写时拷贝）技术：

  • fork 前，一片内存区对应一份物理地址和一份虚拟地址，内存区权限为 RW（Read Write）
  • fork 后，父子进程看到的内存区虚拟地址相同，物理地址也相同，父子进程使用同一片物理内存，未发生内存拷贝，操作系统将此内存区权限改为 RO（Read Only）
  • 父或子进程对内存区执行写操作将触发 PageFault，操作系统将内存区拷贝一份，父子进程看到的虚拟地址仍然一样，但物理地址不同。各进程虚拟地址到物理地址的映射由 MMU（Memory Management Unit，内存管理单元）管理

    10. 进程、线程调度

    Linux 默认调度器为 CFS（Completely Fair Scheduler）

• 内核默认提供 5 个调度器：

  • Stop 调度器（stop_sched_class）：优先级最高的调度类，可抢占其他进程，不能被其他进程抢占
  • Deadline 调度器（dl_sched_class）：使用红黑树把进程按绝对截止期限进行排序，选择最小进程进行调度运行
  • RT 调度器（rt_sched_class）：实时调度器，为每个优先级维护一个队列
  • CFS 调度器（cfs_sched_class）：完全公平调度器，采用完全公平调度算法，引入虚拟运行时间概念
  • IDLE-Task 调度器（idle_sched_class）：空闲调度器，每个 CPU 都有一个 idle 线程，当没有其他进程可以调度时，调度运行 idle 线程
• 线程库：为开发人员提供创建和管理线程的一套 API
  • 在用户空间中提供一个没有内核支持的库，其所有代码和数据结构都在用户空间，调用库内的一个函数只是导致了用户空间的一个本地函数的调用而不是系统调用
  • 实现由操作系统直接支持的内核级的一个库，库内代码和数据结构位于内核空间，调用库内的一个 API 函数相当于系统调用
• CPU 上下文切换：保存 CPU 寄存器和程序计数器在系统内核中（系统快照），重新调度执行再次加载
  • CPU 上下文：CPU 寄存器（容量小、速度极快）、程序计数器（存储 CPU 执行指令）
• 进程上下文切换：系统调用，发生 CPU 上下文切换
• 线程上下文切换：切换私有数据、寄存器，共享的进程堆栈不用切换

• 中断上下文切换：为快速响应硬件的事件，打断进程正常调度和执行，调用中断处理程序，响应设备事件

  四、处理机的调度

  1. 三种调度

• 高级调度（作业调度）：辅存（外存）与内存之间的调度，按一定规则从外存处于后备队列的作业中选一个（多个）作业，分配给其内存等资源，建立 PCB，使其获得竞争处理机权利，每个作业只调入（建立 PCB）、调出（撤销 PCB）一次

• 中级调度：决定将哪个挂起状态进程重新调入内存，发送频率比高级调度高
  • 引入虚拟内存，将暂时不运行的进程调至外存等待（挂起状态，挂起队列，PCB 不会调到外存），提高内存利用率和系统吞吐量
• 低级调度：按某种方法、策略从就绪队列中选一个进程分配处理机，频率最高
  • 当前进程主动放弃处理机：非抢占式
    • 正常终止、异常终止
    • 进程主动请求阻塞（等待 I/O）
  • 当前进程被动放弃处理机：抢占式
    • 分给进程的时间片用完
    • 有更紧急的事（I/O 中断）
    • 有更高优先级进程进入就绪队列
  • 不能调度：
    • 处理中断复杂，难以切换进程
    • 进程在操作系统内核临界区中（互斥）
    • 在原子操作过程中（原语）

2. 调度指标

• CPU 利用率：CPU 忙碌时间占总时间比例
• 系统吞吐量：单位时间内完成作业的数量
• 周转时间：从作业提交给系统到完成的时间
• 等待时间：进程处于等待时间之和

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

  3. 调度算法

• 先来先服务（FCFS）：长作业友好，短作业不友好

  • 非抢占式，不会饥饿
  • 优点：公平、实现简单
  • 缺点：长进程后面的短进程需等待长时间，周转时间大
• 短作业优先（SJF）：短作业友好，长作业不友好
  • 追求最少等待时间、平均周转时间
  • SJF、短进程优先调度算法（SPF）非抢占式，最短剩余时间优先算法（SRN）抢占式
  • 优点：“最短”平均等待时间、平均周转时间
  • 缺点：不公平，可能饥饿
• 高响应比优先（HRRN）
  • 上面二者的折中，
  • 非抢占式，避免长作业饥饿
• 时间片轮转（RR）：轮流让各个进程执行一个时间片
  • 抢占式，不会饥饿
  • 优点：公平、响应快，适用分时操作系统
  • 缺点：高频率进程切换开销较大，不区分任务紧急程度
• 优先级调度：每个进程有各自优先级，调度时选择优先级最高的
  • 抢占式、非抢占式都有
  • 优先级
    • 静态优先级：创建进程时确定，之后不变
    • 动态优先级：创建时有初始值，之后动态调整（根据等待时间、占用处理机时间、频繁 I/O 操作）
  • 进程优先级对比
    • 系统进程 > 用户进程
    • 前台进程 > 后台进程
    • I/O 型进程（开销大） > 计算型进程
  • 优点：区分紧急程度，适用实时操作系统，可灵活调整
  • 缺点：若高优先级进程源源不断进来可能导致饥饿
• 多级反馈队列调度（折中）：设置多级就绪队列，各级队列优先级从高到低、时间片从小到大，新进程到达先进第一级队列，按先来先服务原则排队等待分配时间片，若时间片用完进入下一级队尾，若在最下级队列，放入该队尾，只有第 K 级队列为空，才会为 K+1 级（下一级）队头进程分配时间片
  抢占式，若 k 级队列进程运行中，上级队列进入一个新进程会抢占处理机，原来进程放回 K 级队尾
  • 优点：相对公平
  • 缺点：有可能导致饥饿

五、进程同步、互斥

• 进程同步：进程有异步性，为完成某任务建立多个进程，协调其工作次序而产生的制约关系（管道读数据必须在写数据前）
• 进程互斥：访问临界资源（打印机、摄像头、变量、数据、缓冲等）
  • 空闲让进
  • 忙则等待
  • 有限等待（不会饥饿）
  • 让权等待（进不了临界区就释放处理机，避免忙等）
• 互斥实现
  • 单标志法：违背“空闲让进”，如果 P0 可以访问临界区，但如果 P0 不运行，P1 也不能运行 ```c int turn = 0;

while(turn != 0); //P0 进程 //进入临界区 turn = 1;

while(turn != 0); //P1 进程 //进入临界区 tun = 0;

   - 双标志先检查法：设置 boolean[]，标记各进程进入临界区的意愿，进入前检查数组，没有为 true 的对应标志置 true，进入临界区
      -  违背“忙则等待”，检查和上锁这两步不是原子性的，有可能两者同时访问临界区
```c
boolean flag[2];
flag[0] = false;
flag[1] = false;
while(flag[1]);    //P0 进程
flag[0] = true;
//进入临界区
flag[0] = false;
while(flag[0]);    //P1 进程
flag[1] = true;
//进入临界区
flag[1] = false;

• 双标志后检查法：先上锁后检查，解决“忙则等待”，违背“空闲让进”、“有限等待”，可能死锁 ```c boolean flag[2]; flag[0] = false; flag[1] = false;

flag[0] = true; //P0 进程 while(flag[1]); //进入临界区 flag[0] = false;

flag[1] = true; //P1 进程 while(flag[0]); //进入临界区 flag[1] = false;

   - Peterson 算法：如果双方争临界区，主动让，解决互斥问题，未遵循“让权等待”，没有阻塞排队机制，忙等
```c
boolean flag[2];
int turn = 0;
flag[0] = true;    //P0 进程
turn = 1;
while(flag[1] && turn == 1);
//进入临界区
flag[0] = false;
flag[1] = true;    //P1 进程
turn = 0;
while(flag[0] && turn == 0);
//进入临界区
flag[1] = false;

六、信号量

• P（使用前加锁）、V（使用后解锁） 操作成对出现，顺序设计复杂
• 整形信号量：表示系统中某资源数量，检查上锁原子性，但没有解决忙等（让权等待） ```c int S = 1;

void wait(int S){ //wait 原语 while(S <= 0){ S = S - 1; } }

void signal(int S){ //signal 原语 S += 1; }

- 记录型信号量：记录数据结构表示，遵循“让权等待”，避免忙等
```c
typedef struct{
    int value;            //剩余资源数
    struct process *L;    //等待队列
} semaphore;
void wait(semaphore S){
    S.value--;
    if(S.value < 0){
        block(S.L);        //进程挂到信号量 S 的等待队列
    }
}
void signal(semaphore S){
    s.value++;
    if(S.value <= 0){
        wakeup(S.L);    //唤醒等待队列一个进程
    }
}

七、管程

• 管程中的数据只能由管程内的函数修改访问
• 每次只允许一个进程在管程执行某个内部过程

• 相当于封装，java 的 synchronized

  八、死锁

  各进程互相等待对方的资源，各个线程阻塞，无法推进

• 产生条件

  • 互斥：争抢
  • 不剥夺：不能强行剥夺资源
  • 请求和保持：持有资源又请求别的资源
  • 循环等待
• 发生死锁
  • 竞争不可剥夺资源
  • 请求和释放资源顺序不当
  • 信号量使用不当
• 死锁预防：破坏四条件
  • 互斥：SPOOLing 技术，独占设备改为共享设备，不用阻塞等待
  • 不剥夺：请求资源时释放持有资源，或操作系统强行剥夺
    • 缺点：实现复杂，增加系统开销、降低吞吐量，可能导致饥饿
  • 请求和保持：静态分配（运行前一次性申请全部资源）
    • 缺点：资源浪费，利用率低，可能饥饿
  • 循环等待：顺序资源分配法（资源编号，编号相同一次性申请，占有大编号资源不能申请小编号资源），破坏循环等待链
    • 缺点：不方便新增设备，资源浪费，编程麻烦
• 死锁避免：避免进入不安全状态
  • 安全序列：分配资源每个进程能顺利完成
  • 银行家算法：假设系统 n 个进程、m 个资源，用 n*m Max 矩阵表示所有进程对所有资源的最大需求，同理用分配矩阵 Allocation 表示对所有资源的分配情况，两者相减为 Need 矩阵表示还需多少资源，另外用一个 m 长度的一维数组 Available 表示剩余资源，用一个 m 长度的一维数组 Reques 表示本次申请的资源
    • 若 Request_i[j] <= Need[i,j]（0<=j<=m），转下式，否则认为出错
    • 若 Request_i[j] <= Available[j]（0<=j<=m），转下式，否则表示尚无足够资源，进程必须等待
    • 系统试着把资源给进程，并修改响应数据（不是真正分配，而是预判）：
      Available = Available - Request_i
      Allocation[i,j] = Allocation[i,j] + Request_i[j]
      Need[i,j] = Need[i,j] - Request_i[j]
    • 操作系统执行安全性算法，检查资源分配后是否处于安全状态，安全才分配，否则阻塞
• 死锁检测与解除：允许发生，系统负责检测与解除
  • 死锁检测：用某种数据结构（图）保存资源的请求和分配信息
    • 进程结点：对应一个进程
    • 资源结点：对应一类资源，可能有多个
    • 进程结点 -> 资源结点边：进程想申请几个资源
    • 资源结点 -> 进程结点边：已为进程分配多少资源
    • 检测死锁：如果能化简消除所有边，称可完全简化，此时一定没有死锁（能找到安全序列），不能消除所有边，则发生死锁，连着边的进程是死锁进程
  • 解除死锁：
    • 资源剥夺法：挂起某些死锁进程，抢占其资源，分配给其他死锁进程
    • 撤销进程法：强制撤销部分、全部死锁进程，剥夺其资源，实现简单，代价较大
    • 进程回退法：一个或多个死锁进程回退到能够避免死锁的地步，要求记录历史消息

      九、内存

      更快速的存放数据的硬件，程序执行前先放到内存中，才能被 CPU 处理

1. 程序运行

• 编译：高级语言翻译为机器语言
• 链接：模块生成装入模块，形成完整逻辑地址
  • 静态链接：程序运行前将各模块及库函数链接成完整可执行文件
  • 装入时动态链接：模块装入时边装入边链接
  • 运行时动态链接：程序执行需要模块时才链接，便于修改、更新、共享

• 装入：模块装入内存，形成物理地址

  • 绝对装入：编译时知道程序存放内存位置，编译程序将产生绝对地址的目标代码，按照模块地址装入，适用单道程序环境
  • 静态重定位：编译、链接后装入模块的地址从 0 开始，指令、数据存放的地址都是相对起始地址而言的逻辑地址，根据内存当前情况装入时“重定位”，逻辑地址变成物理地址（装入时必须分配全部内存空间）
  • 动态重定位：编译、链接后装入模块的地址从 0 开始，装入时仍是逻辑地址，当程序真正执行时才“重定位”，需要重定位寄存器支持（可以分配不连续内存，装入部分代码即可运行，便于维护，可以向用户提供比存储空间更大的地址空间）

    2. 内存管理

• 负责内存空间的分配和回收（连续的，非连续：分页、分段、段页）

  • 单一连续分配：内存分为系统区（内存低地址，存操作系统数据）、用户区（只有一道用户程序）
    • 优点：实现简单，无外部碎片（内存空闲分区太小不能利用），可用覆盖技术扩充
    • 缺点：适用单任务单用户，存储器利用率极低，有内部碎片（分配给进程的内存有些没用到）
  • 固定分区分配：用户空间划分若干固定大小分区，每个分区一个作业，多道程序管理
    • 建立分区说明表，对于一个分区，表项对于分区大小、起始地址、状态（是否分配）
    • 优点：实现简单，无外部碎片
    • 缺点：当用户程序太大只能用覆盖技术解决，降低性能，有内部碎片，内存利用率极低
  • 动态分区分配：进程装入内存时动态建立分区
    • 空闲分区表、空闲分区链
    • 有外部碎片（紧凑技术解决）、无内部碎片
• 能够对内存空间进行扩充

• 负责逻辑地址和物理地址的转换（三种装入方式）

  3. 内存保护与扩充

• 内存保护

  • CPU 设置一对上、下限寄存器，存放进程的上下限地址，不允许越界
  • 重定位寄存器（基址寄存器）存放进程起始地址，界地址寄存器（限长寄存器）存放进程最大逻辑地址

• 内存扩充

  • 覆盖技术：程序分为多模块，常用的常驻内存（固定区），不常用的在需要时调入内存（覆盖区）
  • 交换技术：内存紧张时（缺页率高）将某些进程（阻塞进程，优先级低进程）暂时换出外存（PCB 还是常驻内存），外存中具备运行条件的进程换入（中级调度）
    • 磁盘分对换区（存换出进程数据、追求速度、连续分配）、文件区（存文件、追求利用率、离散分配）

      4. 动态分区算法

• 首次适应：每次从低地址查找，找到第一个满足的分区

  • 空闲分区地址递增排序，维护空闲分区链（表）
• 最佳适应：动态分区分配是连续分配，优先使用小空闲区
  • 空闲分区容量递增排序，维护空闲分区链（表）
  • 缺点：会留下越来越多、小的空闲内存，产生很多外部碎片
• 最坏适应：解决最佳适应碎片多，优先使用大空闲区
  • 空闲分区容量递减排序，维护空闲分区链（表）
  • 缺点：导致较大连续空闲分区迅速用完
• 邻近适应：从上次查找结束位置开始查找
  • 空闲分区地址递增排序，维护循环空闲分区链（表）
  • 缺点：高地址部分大分区被划分为小分区

十、分页存储管理

• 将内存空间划分为一个个相等的分区（如 4KB），每个分区是页框，有一个页框号，从 0 开始
• 将用户进程地址空间划分为与页框相等的若干区域，每个区域是页，有一个页号，从 0 开始
• 以页框为单位存放页面，不必连续、先后顺序

• 地址转换：物理地址 = 页面地址 + 页内偏移地址（逻辑地址（低位）% 页面长度）
  • 页号 = 逻辑地址（高位）/ 页面长度
• 页表：记录进程页面和实际存放内存卡之间的对应关系
  • 一个进程一个页表
  • 一个页表项对应一页，由页号、块号组成，页表项长度一样，页号隐含（页表存放起始地址、页表项长度推算各页号对应页表项存放位置）
• 基本地址变换机构：
  • 页表寄存器（PTR），存页表在内存中的起始位置 F 和页表长度 M，进程未执行时，两者放在 PCB 中，进程被调度时操作系统内核将其放在页表寄存器

• 具有快表（TLB）的地址变换机构
  • 时间局部性：某条指令（数据）多次执行（访问），循环
  • 空间局部性：访问某个存储单元，其附近的存储单元也有可能被访问
  • 快表（联想寄存器）：访问速度比内存快很多的高速缓冲存储器

• 两级页表
  • 单级页表问题
    • 页表必须连续存放，分配占用很多页框
    • 进程一段时间内可能只访问几个页面
  • 为页表建立一张表（页目录表）
    • 从 PCB 读出页目录表起始，根据一级页号查页目录表，找到二级页表在内存的位置
    • 根据二级页号查表，找到最终想访问的内存块号
    • 结合页内偏移量得到物理地址
• 基本分段存储管理
  • 分段：按进程自身逻辑（函数、局部变量等）划分为若干个段（低级语言用段名编程），每个段有段名，每段从 0 开始编址
  • 逻辑地址 = 段号 + 段内地址（段内偏移量）
  • 段表：每个进程一个，每个段对应一个段表项（长度固定），记录段号（可以隐含）、段长、基址
    • 寻址和页表类似
  • 分页、分段管理区别：
    • 页：信息物理单位，离散分配，对用户不可见
    • 段：信息逻辑单位，对用户可见
    • 分段更容易实现信息共享和保护
    • 都需要两次访存，访页表/段表，访内存单元
• 段页式管理：进程先分段、再分页
  • 每段对应一个段表项（长度相同），段号（隐含）、页表长度、页表存放块号（页表起始地址）
  • 每页对应一个页表项（长度相同），页号（隐含）、页面存放内存块号

十一、虚拟内存

• 用户看来有一个比实际内存大的内存（逻辑上扩充）
• 虚拟内存最大容量：计算机地址结构（CPU 寻址范围）决定
• 虚拟内存实际容量：min(内外存容量和, CPU 寻址范围)

• 特征

  • 多次性：作业分多次调入内存
  • 对换性：作业运行无需常驻内存，允许换入换出
  • 虚拟性：逻辑上扩充内存容量

    1. 请求分页存储管理

• 与基本分页存储管理对比：程序执行中访问信息不在内存，由操作系统从外存调入，若内存空间不够，操作系统将内存中暂不用信息调出外存

• 页表机制：
  • 内存块号
  • 状态号：是否调入内存
  • 访问字段：记录访问过几次、或上次访问时间，供置换算法参考
  • 修改位：页面调入后是否被修改过
  • 外存地址：页面在外存存放地址
• 缺页中断机构：内中断，访问页面不存在触发，缺页进程阻塞，放入阻塞对列，调页完成后唤醒，放入就绪队列

• 地址变换机构

  2. 页面置换算法

• 最佳置换：每次淘汰的页面是以后永不使用或最长时间段内不被访问，无法实现（无法预测）

• 先进先出法：每次淘汰页面是最早进入的，实现简单，性能差
  • Belady 异常：当为进程分配物理块数增大时缺页次数不减反增
• 最近最久未使用置换：每次淘汰的页面是最近最久未使用的，访问字段记录自上次访问以来经历的时间
  • 性能好，实现困难，开销大
• 时钟置换：性能、开销均衡，为每个页面设置一个访问位，用链接指针连接成循环队列，当页面被访问，访问位置 1，淘汰一个页面只需检查其访问位，若第一轮扫描所有页面都是 1，则依次置 0，第二轮扫描
• 改进时钟置换：只有淘汰的页面被修改过才需写回外存，设修改位 0 表示没有修改过
  • 第一轮扫描找到一个未修改过，未访问过的页面用于替换
  • 若失败，第二轮扫描查找一个修改过、未访问过的页面用于替换，本轮所有扫描过的页面访问位设为 0
  • 若失败，第三轮扫描找到一个未修改过，未访问过的页面用于替换
  • 若失败，第四轮扫描找到一个修改过、未访问过的页面用于替换

3. 页面分配策略

• 驻留集：请求分页存储管理中给进程分配的物理块集合
• 工作集：某段时间间隔里进程实际访问页面的集合
• 分配置换策略
  • 固定分配：一开始设置好，驻留集大小不变（只有局部置换）
  • 可变分配：运行时驻留集大小可变（两种置换都有）
  • 局部置换：缺页只能选择自己的物理块置换
  • 全局置换：可将操作系统保留的空闲物理块分配给缺页进程，将别的进程持有的物理块置换到外存再分配给缺页进程
• 调页策略
  • 预调入策略：一次调入若干个相邻页面比一次调入一个页面高效，成功率 50%，运行前调入
  • 请求调页策略：运行期间缺页才调入内存，I/O 开销大

• 抖动现象：换出的页面马上要换入内存或相反

  十二、文件管理

  1. 文件

• 向上提供功能： 创建、删除、读、写、打开、关闭

  • 系统打开表：系统一张，打开计数器（删除时需文件无打开）
  • 进程打开表：进程一份
  • 关闭时打开表对应表项删除，回收内存等资源，打开计数器 -1，若为 0，删除对应表项
• 存储：外存会分为一个个磁盘块，文件逻辑地址也可分为一个一个块

• 逻辑结构

  • 无结构文件（.txt）：一系列二进制流或字符串组成
  • 有结构文件（定长记录、可变长记录）：由一组相似的记录组成，每条记录由若干个数据项组成（数据库表文件），每条记录有一个数据项作为关键字
  • 顺序文件：文件记录逻辑上顺序排序
    • 串结构：记录间顺序与关键字无关
    • 顺序结构：记录间顺序按关键字排序
    • 定长记录可随机存取（物理顺序存储）、可变长不可
  • 索引文件：定长记录的顺序文件，按关键字顺序排列可以按照关键字折半查找，检索速度快
  • 多级索引顺序文件

    2. 文件目录

• 文件控制块（FCB）：目录文件的一条记录，包含文件基本信息（文件名，物理地址，逻辑地址，物理结构等），存取控制信息（是否可读写，禁止访问的用户等），使用信息（文件建立时间，修改时间）

• 单级目录结构：只建立一张目录表，每个文件占一个目录项，按名存取，不允许重名
• 两级目录结构：主文件目录（记录用户名及相应目录存放位置）、用户文件目录（用户文件 FCB 组成），允许不同用户文件重名
• 多级目录结构：各级目录用“/”隔开，绝对路径（从根目录开始），相对路径（从当前目录开始，”./“） ，不方便实现共享
• 无环图目录结构：多级目录结构基础上增加指向同一节点的有向边，每个共享结点设置有一个共享计数器，共享计数器为 0 才删除节点

• 索引结点（FCB 的改进）：目录项只包含文件名和索引结点指针（索引结点包含除文件名外所有信息）

  • 目录项长度减少，检索 I/O 次数少，每个磁盘块可放更多目录项

    3. 文件分配方式

• 连续分配：文件在磁盘上占有一组连续的块

  • 优点：顺序读/写速度最快，支持顺序访问和直接访问（随机访问）
  • 缺点：不方便扩展，存储空间利用率低，产生磁盘碎片
• 链接分配：采取离散分配
  • 隐式链接：支持顺序访问，不支持随机访问，便于扩展，没有碎片问题，外存利用率高
  • 显式链接：链接文件各物理块的指针显式存放在文件分配表（FAT）中，支持顺序访问和直接访问（查询 FAT 表），便于扩展，没有碎片问题，文件访问效率更高

• 索引分配：索引块存放索引表，数据块存放文件数据

  • 索引表存放逻辑块号（隐含）和物理块号
  • 如果索引表太大，可将多个索引块链接起来，查找效率低
  • 多级索引，K 层索引结构要读取 K+1 次磁盘，即使小文件也要多次读磁盘
  • 混合索引，直接地址索引和一级间接索引、二级间接索引表

    4. 文件存储空间管理

• 磁盘分区（C盘 D盘），每个区内划分为目录区（FCB、磁盘空间信息）、文件区

• 空闲表法：记录空闲盘
  • 采用首次适应、最佳适应、最坏适应等算法为文件分区
  • 回收：表项合并
• 空闲链表法：以盘块为单位、以盘区为单位
  • 回收：表项合并
  • 离散分配、连续分配都适用，为一个文件分配多个盘块时效率高
• 位示图法：每个二进制位对应一个盘块，字号、位号转换
  • 分配：扫描 0，根据字号、位号转换对应盘块号分配，相应位置 1

• 成组链接法（UNIX）：

  • 文件卷目录区有个磁盘块为超级块，内存与外存中超级块数据一致
  • 分配：检查第一个分组块数，足够就分配，若刚刚好，则将下一组的信息复制给超级块，然后分配
  • 回收：分组未满，加入分组，分组已满，超级块信息复制给该回收块，分组指向该回收块

    5. 文件共享和保护

• 文件共享

  • 基于索引结点的共享方式（硬链接）：索引结点中设置一个计数变量，表示链接到本索引结点的用户目录项数，删除只是文件对应目录项删除，计数减一，计数为 0 时删除文件
  • 基于符号链的共享方式（软链接）：Link 文件记录文件存放路径（类似快捷方式）
• 文件保护：
  • 口令保护：为文件设置一个口令，用户请求文件需提供口令
    • 优点：空间小，时间快
    • 缺点：口令存放在系统内部，不够安全
  • 加密保护：使用密码加密文件，访问需提供密码
    • 异或加密
    • 优点：保密性强，不需存储系统中
    • 缺点：编码/译码花费一定时间
  • 访问控制：每个文件的 FCB 中增加一个访问控制列表（ACL），记录用户可以对文件执行的操作
    • 优点：实现灵活，可实现复杂文件保护功能

      十三、磁盘结构

      磁盘：盘面划分为一个一个同心圆（磁道），一个磁道又划分为几个扇区（数据量一样）

1. 磁盘调度算法

• 先来先服务
  • 优点：公平
  • 缺点：若请求磁道分散，性能很差
• 最短寻找时间优先
  • 优点：性能较好
  • 缺点：可能饥饿
• 扫描算法：磁头移到最外侧磁道才能往内，到最内侧磁道才能往外
  • 优点：性能较好，不会饥饿
  • 缺点：只有达到最边上的磁道才能改变方向，对各个位置磁道响应不均
• LOOK 调度算法：如果在磁头移动方向上没有别的请求可以立即改变方向
  • 优点：比扫描算法时间进一步缩短
• 循环扫描算法：磁头向某方向移动时才会处理请求，而返回到起始端不处理请求
  • 优点：比扫描算法各磁道响应频率平均
  • 缺点：只有到达边上才能改变方向

• C-LOOK 调度算法：LOOK 调度和循环扫描算法

  • 优点：比循环扫描算法时间进一步缩短

    2. 磁盘管理

• 减少延迟

  • 交替编号：让逻辑上相邻的扇区有一定间隔进行处理使读取延迟时间短
  • 错位命名：不同盘面对应编号错开有一定间隔进行处理使读取延迟时间短

• 磁盘管理：

  • 初始化：
    • 低级格式化，划分扇区
    • 磁盘分区，分区由若干柱面组成
    • 逻辑格式化，创建文件系统
  • 引导块：开机时进行初始化程序，放在 ROM（只读存储器）
  • 坏块处理：建立文件系统时检查整个磁盘，坏了的扇区在 FAT 表上标明（对操作系统不透明），有备用扇区用于替换坏块

    十四、I/O 设备

    外部设备，UNIX 将外设抽象为一种文件

• I/O 控制器：CPU 通过控制其控制设备

  • 控制寄存器：存放命令
  • 状态寄存器：设备状态
  • 数据寄存器：存放暂时数据

    1. I/O 控制方式

• 程序控制方式

  • 一次读/写操作（轮询）
  • CPU 干预频率（CPU 也需要轮询）
  • 读写需要 CPU 参与
  • 每次读/写一个字
  • 优点：实现简单
  • 缺点：只能串行运行，CPU 需要一直轮询等待，长期处于忙等，利用率低
• 中断驱动方式：将等待的进程阻塞，完成后向 CPU 中断信号，CPU 保存当前运行环境处理中断，恢复运行环境继续运行
  • 优点：CPU 不用轮询，利用率提升
  • 缺点：频繁中断消耗 CPU 时间
• DMA 方式（直接存储器存取）
  • 数据传输单位是块
  • 不需要 CPU，仅在开始结束才需要 CPU 干预
  • DR（数据寄存器）：暂存设备数据
  • MAR（内存地址寄存器）：数据存储内存位置，输出数据在内存的位置
  • DC（数据计数器）：剩余要读/写字节数
  • CR（命令/状态寄存器）：存放 CPU 指令或设备状态
  • 优点：CPU 介入频率降低，并行性提升，传输数据提升
  • 缺点：读/写多个离散数据块要多条指令，多次中断
• 通道控制：一种硬件，弱鸡版 CPU，执行指令单一，与 CPU 共享内存
  • 优点：并行工作，资源利用率高
  • 缺点：实现复杂，需要专门硬件支持

2. I/O 层次结构

• 用户层软件：实现与用户交互的接口，用户请求翻译成格式化的请求，请求系统内核服务
• 设备独立性软件：
  • 向上提供接口
  • 设备的保护（文件的保护）
  • 差错处理
  • 设备分配与回收
  • 数据缓冲区管理
  • 建立逻辑设备名到物理设备名的映射，并调用相应驱动程序（逻辑设备表 LUT）
• 设备驱动程序：负责对硬件设备具体控制，将上层命令转译为设备可执行操作
• 中断处理程序：直接和硬件打交道，完成任务发出中断信号，系统会调用相应中断处理程序执行

• 硬件

  3. 假脱机技术

• 脱机技术：脱离主机控制进行输入/输出操作

• 假脱机技术（SPOOLing）：用软件模拟脱机技术，将独占式设备改造为共享设备