操作系统

Operating System

pdf 下载

一、计算机操作系统概念

管理系统资源、控制程序执行、改善人机界面、提供各种服务，并合理组织计算机工作流程和为用户方便有效的使用计算机体哦那个良好的运行环境的一种系统软件

• 方便用户使用
• 管理系统资源
• 提高系统效率
• 扩大机器功能
• 构筑开放环境

资源管理技术：

• 资源复用：解决物理资源数量的不足
  • 空分复用：该资源可以进一步分割成更多和更小的单位供进行使用，如内存空间
  • 时分复用：并不把资源进一步分割成更小的单位，进程可在一个时间段内独占使用整个物理资源，如 CPU
• 资源虚拟：解决物理资源不足，提高服务能力和水平
  • 是对资源进行转化，模拟或整合，把物理上的一个资源变成逻辑上的多个对应物，或把物理上多个变成逻辑上的一个
  • 空分复用分割实际存在的物理资源，虚拟实现虚构假象的虚拟同类资源
  • 资源虚拟的例子：虚拟设备，虚拟主存，虚拟文件，虚拟屏幕，虚拟信道
• 资源抽象：处理系统的复杂性，解决资源的易用性
  • 资源抽象用于处理系统的复杂性，重点解决资源的易用性
  • 资源抽象是指通过从创建软件来屏蔽硬件资源物理特性和接口细节，简化对硬件资源的操作，控制和使用的一类技术
  • 单机资源抽象与多级资源抽象

1.1 操作系统处理方式

1.1.1 批处理方式

特点：成批提交，成批处理

• 接受一批作业到外存，组织成作业流
• 自动控制一批作业的内存装入和运行过程
• 全部完成后再将结果反馈给用户

分类：

• 单道批处理程序

  

  • 成批提交：操作员集中一批用户提交的作业通过输入设备输入到磁带上
  • 单道装入：管理程序自动把磁带上的一个作业装入主存，并把控制权交给作业
  • 顺序运行：该作业执行完成后把控制权交回管理程序，管理程序再调入磁带上的下一个作业

• 多道批处理程序

  

  • 成批提交，多道装入
  • 系统资源利用率提高，系统吞吐量变大
  • 成批处理过程中无交互性，用户作业的等待时间长

1.1.2 分时处理方式

又叫会话型处理，是在多道程序设计基础上发展起来的一种处理方式，强调交互性，采用分时技术，即将 CPU 时间划分为多个时间片，每个时间片轮流执行为用户程序

基本特征：

• 同时性
• 交互性
• 独占性
• 及时性

1.1.3 实时处理方式

硬实时系统：对时间严格约束

软实时系统：对时间限制稍弱一点

软实时的常见系统：

• 过程控制系统
• 信息查询系统
• 事务处理系统

1.2 操作系统的功能组成

1.2.1 用户和接口管理

负责用户身份验证，操纵权限管理以及各种人机接口的实现

• 用户管理
• 用户组管理
• 联机接口管理
• 脱机接口管理
• 程序级接口管理

1.2.2 处理机管理

围绕 CPU 的调度，负责管理、控制用户程序的动态执行过程

• 进程控制和管理
• 进程同步和互斥
• 进程通信
• 进程思索

1.2.3 线程控制和管理

• 四级调度

1.2.4 存储管理

负责为正在运行的程序分配内存空间，并实现地址和空间有关的管理功能

• 内存分配
• 地址转换
• 存储保护
• 内存共享
• 存储扩充

1.2.5 设备管理

负责外存和 I/O 设备的分配、驱动和调度控制，以及实现外设读写的相关机制

• 设备的分配和回收
• 设备的驱动调度
• 实现逻辑设备到物理设备之间的映射
• 提供设备终端处理
• 提供缓冲区管理
• 实现虚拟设备

1.2.6 文件管理

负责文件的建立、存取、目录管理、共享保护以及文件存储空间的管理

• 提供文件的逻辑组织方法
• 提供文件的物理组织方法
• 提供文件的存取和使用发给发
• 实现文件的目录管理
• 实现文件的共享和安全性控制
• 实现文件的存储空间管理
• 网络与通信管理

1.2.1 内核

• 是作为可信软件来提供支持进程并发执行的基本功能和基本操作的一组程序，如始终管理，CPU 调度，内存分配等
• 内核通常驻留再内核空间，运行于核心态，具有访问硬设备和所有主存空间的权限
• 内核是由中断驱动的
• 内核是不可抢占的
• 内核可以在屏蔽中断状态下执行
• 内核可以使用特权指令

1.2.2 PC 机 DOS 操作系统启动过程

• 加电，CPU 执行 BIOS 程序模块，该模块中的 硬件诊断程序 投入运行，检查硬件配置和设备状态，并在屏幕上显示存储容量和各个设备的链接情况
• 外存储器上的 操作系统引导程序 被自动写入内存，立即投入运行，把操作系统的内核部分一一装入内存，将 CPU 控制权交给内核
• 内核运行做一些必要的初始化工作，比如内存分区，建立链表，创建必须的系统进程
• 系统安排停当后显示系统提示符，并执行 CPU 闲逛 程序，等待用户到来

1.3 操作系统的主要特征

1.3.1 并发性

在一个时间段内，多个程序处于宏观的运行状态，并发推进

优点：

• 在一个时间段内，多个程序（进程）并发推进，共享系统资源
• 发挥并发性能够消除系统中部件和部件之间的互相等待，有效地改善系统资源的利用率

必须解决的问题：

• 如何从一个进程切换到另一个进程
• 如何将各个进程隔离开，使之互不干扰
• 怎样让多个进程写作完成任务
• 多个进程共享文件数据时，如何保证数据的一致性
• 怎样协调多个进程对资源的竞争或共享

并发的实质:

• 并发的实质 是一个物理 CPU 在若干道程序之间多路复用
• 并发性 是指让有限物理资源实现多用户共享，以提高效率
• 共享性 指操作系统中的资源可被多个并发执行的进程所使用
  • 同时共享：同时具有使用权，如内存空间、磁盘空间，涉及透明资源共享（资源隔离与授权访问）
  • 互斥共享：轮流使用，如 CPU 、I/O 设备，涉及显示资源共享（临界资源与独占访问）
• 异步性 也被称为不确定性，指的是并发进程的推进速度不可预知
  • 每个进程在某一时刻所处的状态以及资源拥有情况，不是提前安排好的，而是系统动态运行过程中通过管理调度形成的
  • 异步性特征是并发和共享带来的结果
  • 异步性的表现：
    • 进程何时执行，何时暂停是随机的
    • 作业到达系统的类型和时间是随机的
    • 操作员发出命令或按按钮的时刻是随机的
    • 程序运行发生错误或异常的时刻是随机的
    • 各种各样的软硬件中断时间发生的时刻是随机的
  • 异步性给系统会带来潜在的危险，有可能导致与时间有关的错误
  • 操作系统的一个重要人物是必须确保捕捉任何一种随机时间，正确处理，否则将会导致严重后果
• 虚拟性 是指利用某种技术将少的物理资源演变为多的，逻辑上对应的资源，还包括将慢的虚拟成快的、容量小的虚拟成容量大的、不能共享的虚拟成能共享的。一方面虚拟扩充了系统资源，另一方面为用户使用系统带来了方便
  • 虚拟性的表现：
    • 虚拟存储器
    • 虚拟设备
    • 虚拟机

二、作业与作业管理概述

• 作业管理模块是操作系统中最外层的直接面对用户的模块
• 为用户提供系统接口，将用户需求提交系统，再见处理结果反馈用户
• 负责用户管理，核证用户合法性，管理用户使用资源及费用等情况

2.1 什么是作业

简单的说，就是用户提交给计算机系统的任务

• 作业有大有小，小作业可能只包含一个程序，大作业可能包含若干个程序

作业类别：

• 批处理作业：主要用于巨型机和大型服务器系统，成批提交以后，系统将所有作业组织成一个作业流，然后对它们逐一进行控制和调度，脱机
  • 批处理管理机制
  • 作业控制块（JCB）
  • 作业状态
  • 作业调度
  • 作业的装入和卸出
• 交互性作业：广泛用于各种系统，主要特点是用户可以独占一台终端机，对自己的作业实施交互控制，联机
  • 不经作业调度，直接进入内存，通过进程调度和进程控制管理
• 实时性：特指响应时间有实时需求的作业，用于实时系统。根据作业对响应时间严格性要求的不同，可细分为硬实时和软实时作业

2.1.1 用户管理

• 功能：创建新用户、删除老用户、验证用户身份、维护用户信息、配置各个用户的运行环境、为各用户设置使用权限、用户组的设置与管理
• 用途：既方便计费，又方便系统安全管理

2.1.2 接口管理

• 功能：为用户提供设置不同的用户接口，既分操作员接口、程序员接口，又分联机接口、脱机接口
• 用途：为用户使用计算机系统、运行不同类型的作业提供方便

2.1.3 批作业的管理控制与调度

• 功能：将批作业收容到外存的“作业输入井”中，建立“作业控制块”记录作业控制信息，通过作业调度选择后备作业装载入内存，并在作业完成后将作业卸出
• 要点：
  • 作业状态、作业控制块
  • 作业调度、作业的装载与卸出

2.2 操作系统接口

2.2.1 作业控制说明语言

• 批处理系统中，用户提交给系统的一个计算任务，就是一个作业
• 批作业 = 程序 + 数据 + 作业控制说明书
• 作业控制说明书由作业控制语言编写，也就是由一条条控制作业如何运行的命令组成
• 作业控制说明语言是由一组作业控制命令组成的集合，专门用于批处理系统

2.2.2 联机命令接口

终端用户使用的操作命令接口，主要实现人机交互。用户通过终端命令或者鼠标点击来控制作业的运行。该类接口涉及的服务程序：

• 终端处理程序
• 命令解释程序
• 鼠标点击事件响应程序

分类：

• 命令行方式此操作接口（键盘）
• 图形化界面（鼠标点击）

2.2.3 程序级接口

操作系统还提供一种适用于应用程序中的功能调用接口，叫做系统调用，允许用户在自己的应用程序中调用系统中提供的一些功能模块。简单地说，系统调用就是应用程序要调用系统程序。

系统调用是应用程序获得操作系统服务的唯一途径

• 特权指令是指那些直接管理控制系统资源和状态的指令，用错可能导致整个系统崩溃，比如：清内存、设置时钟等
• 只有系统程序才能执行特权指令，应用程序只能执行非特权指令

系统资源的分配、驱动、调度以及管理数据的检索、修改等操作，是不允许用户程序自行处理的，否则系统就无安全性及管理控制之说了

操作系统以系统调用的形式提供一系列的实现预定底层功能的内核函数，每个系统调用都有写好的服务历程，每个服务例程有其入口地址

2.2.4 CPU 的两种工作状态

• 管态（系统态）：执行系统程序的状态，允许执行所有指令
• 目态（用户态）：执行用户程序的状态，只允许执行非特权指令

2.3 系统调用

是操作系统提供的一种适用于应用程序中的功能调用接口，叫做系统调用，允许用户在自己的应用程序中调用系统中提供的一些功能模块

系统调用是应用程序获得操作系统服务的唯一途径

分类：

• 进程和作业管理类
• 文件操作类
• 设备管理嘞
• 主存管理嘞
• 信息维护类
• 通信类

系统调用：程序级接口，通过该接口用户程序可以调用操作系统提供的功能模块。系统调用的服务例程在管态下执行

API：系统提供的应用函数库，也称应用程序接口，将一些常用功能函数事先实现，供用户程序直接调用，其中一些 API 函数的是现场过程调用了一个或多个系统调用。**API 函数在目态下执行**

Linux 系统程序、系统调用、库函数、应用程序分层关系

系统调用的实现：

• 编写系统调用处理内核函数
• 设计一张系统调用入口地址表，每个入口地址都指向一个系统调用的处理内核函数，有的系统还包含系统调用自带参数的个数
• 陷入处理机制开辟现场保护区，以保存发生系统调用时的处理器现场

2.4 作业的管理控制

2.4.1 批作业的状态管理

• 后备状态**：已经提交到外存的“作业收容井”，等待调度装入
• 驻留状态：被作业调度选中，已经装入内存，处于宏观的运行状态
• 完成状态：作业相关代码已经执行结束，已不再占有内存空间和系统各种设备，正在等待卸出和数据缓输出

2.4.2 批作业控制块的描述和组织

• 为了掌握作业的有关情况，管理程序需要对作业进行必要的等级
• 作业管理模块设置一种数据结构，叫做作业控制块 JCB - Job Control Block ，用以记录作业的各项属性和管理信息

JCB 的内容

• 作业号
• 作业类别
• 用户名及用户账号
• 作业状态
• 提交到系统的时间
• 优先级
• 作业所在的外存位置
• 资源需求
• 运行长度
• 已经运行的时间
• 其他信息

2.4.3 不同的作业 I/O 方式

**联机 I/O**：这是一种早期的输入输出方式，主机连接 I/O 设备，在作业运行过程中，占用着 CPU 进行输入和输出过程。缺点是快速 CPU 等待慢速的 I/O 设备

**脱机 I/O**：

**假脱机 I/O**：这种方式又称作“在线外设并行访问”。简记为 Spooling。在这种方式中，不再单独设置的输入输出计算机，而是将输入输出功能从操作系统内核中分离出来，单独形成 I/O 进程，来完成用户的输入输出工作

2.4.4 不同的作业控制方式

操作系统必须对用户作业的全过程实施控制，包括怎样将作业输入到计算机中去、怎样控制作业对玉兴、运行出现故障后如何进行处理以及作业运行结束后哪些内容输出等

脱机作业控制：这种管理方式一般适用于批处理系统中，所有作业的控制信息都由用户按照系统提供的作业控制语言来编制。用户提交作业之后，作业的运行完全脱离用户的干预

联机作业控制：是大多数分时系统和实时系统采用的一种作业控制方式，整个控制过程由用户使用操作系统提供的操作命令，与计算机通过交互会话方式来控制作业执行

2.5 作业调度

又称 高级调度

• 批处理系统中采用的一级调度
• 其主要功能是，从处于后备状态的作业中按照某种算法选择一道或几道作业装入内存
  • 选几道：单道系统只选一道，多道系统视内存容量决定
  • 选哪几道：由作业调度算法决定
• 作业调度主要解决的是作业与作业之间的自动转接问题，即免去作业控制中的人工操作的问题

什么时候执行作业调度程序：

• 有作业完成
• 新作业提交且内存有空闲
• 处理及利用率偏低

2.5.1 先来先服务 FCFS 调度算法

First Come First Serverd 选择最先进入后备队列的作业装入内存

优点：

• 比较容易实现

缺点：

• 不区分作业长短，对短小作业十分不利
• 不顾及轻重缓急
• 对事件要求紧迫的作业不能做到急事急办

2.5.2 最短作业优先 SJF 调度算法

Shortest Job First 从后备作业中选择运行时间最短的作业装入内存

优点：

• 照顾短作业用户的利益，提高系统吞吐量
• 让作业的平均周转时间降下来

缺点：

• 推迟长作业运行，可能出现饥饿现象
• 估计运行时间本身有可能不太准确

2.5.3 最高相应比优先 HRF 调度算法

Highest Response First

t_w ：作业的等待时间

t_s ：作业的估计运行时间

优点：折中考虑到作业进入系统的先后次序，又估计到作业的运行长度

缺点：每次调度都要计算每个作业的响应时间比，开销大

2.5.4 最高优先级 HPF 调度算法

Highest Priority First 该算法每次总是选择后备作业中优先级最高的作业装入内存。当一个作业进入系统，系统根据用户级别、用户租金、作业类别、作业运行时间要求等为作业赋予一个优先级。是一种比较灵活的调度算法，优先级可以根据需要灵活确定，经常作为基于作业运行紧迫性的一种调度方案

2.5.5 均衡调度算法

根据内存容量的限制，选择一组资源互补型的作业装入。

目的：在作业运行期间，尽可能提高 CPU 和各种设备之间的并行度

2.5.6 作业调度性能的衡量准则

• 系统吞吐量高，单位时间内系统完成的工作量称吞吐量。这是作业调度追求的第一目标

• Q 吞吐量与作业的平均周转时间 T 有 T 越小，Q 就越大 的关系

  • 作业的平均周转时间

  

  • t_fi 为第 i 个作业的完成时间
  • t_bi 为第 i 个作业的提交时间
  • n 为单位时间内的作业数量

• 对短作业优惠，这一准则主要是为了吸引中小用户使用计算机。为了描述系统对短小作业的优惠程度，可使用作业的平均带权周转时间 w 作为评价参数

  

  • t_si 为第 i 个作业的服务时间（运行时间），w 越小，说明系统对短小作业越优惠

• 处理及利用率高

• 响应时间有保证

• 优先权有保证

• 截止时间有保证

• 资源均衡利用

三、进程管理与处理机调度

3.1 初识进程

是造作系统最核心的概念之一，是操作系统要面对的最核心的管理对象，是占用 CPU 资源和其他资源的实体

• 用户的所有程序均通过进程的形式运行
• 操作系统给用户提供的各种服务也是以进程的形式运行
• 进程管理模块是操作系统中最核心的一个模块
• 学习操作系统内核从学习操作系统如何尽力、管理、调度进程开始

3.1.1 什么是进程

• 一个正在计算机上执行中的程序
• 一个能分配给处理器执行的实体
• 一个具有以下特征的活动单元
  • 一组指令序列的执行
  • 一个当前状态和相关的系统资源集

3.1.2 操作系统为什么要进入进程

一个程序的两次执行过程，在操作系统那里是两个相互独立的运行实体，所以操作系统需要引入进程

• 使用进程描述每一个程序的每一次动态执行
• 通过进程实体来管理控制每一个程序的每一次执行过程
• 操作系统需要引进子进程，使大程序的程序段可以并发，以加快程序推进且高 CPU 利用率

多道程序并发运行，共享 CPU 、内存、I/O 设备等资源

并发运行方式的基本特征：

• 异步特征
• 资源共享特征
• 相互制约特征
• 不可重现性特征

3.1.3 进程与程序、作业有何区别和联系

程序：

• 完成一件事情的代码序列
• 静态
• 只包含代码
• 程序是作业的组成部分

进程：

• 是一个程序的一次动态执行过程
• 进程对应一个程序的一次动态执行过程
• 动态
• 包括要运行的代码、代码要处理的数据、运行过程中的状态参数等

作业：

• 批作业 = 程序 + 数据 + 作业控制说明书
• 交互作业 = 程序 + 数据 + 交互命令
• 用户提交给系统的一个计算任务

程序 VS 进程：

• 进程是操作系统为了管理控制程序的运行而加设的一个概念和实体
• 程序不运行，就没有进程
• 一个进程是一个程序的一次执行过程
• 一个程序可能对应多个进程

3.2 进程与进程管理模块

3.2.1 进程的特征

• 动态特征：生命周期
• 并发特征：在一个时间段内都处在宏观的运行状态
• 独立特征：独立占有资源、独立参与 CPU 调度
• 异步特征：运行推进速度不可预知
• 结构特征：PCB + 进程体

**进程控制块 PCB**：

• 进程标识
  • 外部标识（也称作进程的外部名）：是进程的创建者提供的进程名字，通常由字符串组成
  • 内部标识（也称作进程的内部名）：是系统为进程命名的一个代码，通常是一个整型
• 调度信息
  • 进程优先数，描述进程紧迫性的信息
  • 进程状态信息，描述进程当前处于何种状态
  • 其它调度信息
• 处理机信息
  • 进程被中断时，该进程的 CPU 现场信息可以保存到自己的 PCB 中，一边该进程重新获得CPU 时可以从此处回复现场信息，继续运行
  • 通用寄存器的内容，包括数据寄存器，段寄存器
  • 程序状态字 PSW 的值
  • 程序计数器 PC 的值
  • 进程的堆栈指针等
• 进程控制信息
  • 程序代码和数据集所在的内存地址
  • 资源清单，记载进程请求资源和已经占有资源的情况
  • 同步与通信信息
  • 外存地址
  • 家族信息
  • 链接指针

3.2.2 进程管理模块的主要功能

进程管理模块时 OS 最重要的组成部分

功能分类：

• 进程控制

  管理控制一个进程的生命周期

  • 创建新进程，撤销结束进程
  • 阻塞或唤醒进程
  • 挂起或激活进程

  管理控制多个进程的并发

  • 进程同步和进程互斥
  • 进程通信

• 进程调度

  根据当前状态决定哪个进程获得 CPU

  将 CPU 分给进程

3.3 进程状态转换

3.3.1 进程的三种基本状态

• 运行状态（running）：进程获得 CPU 并投入运行的一种状态。在单 CPU 系统中，每个瞬间最多只能有一个进程在运行
• 就绪状态（ready）：进程尚未获得 CPU 使用权的一种状态。进程已经拥有除 CPU 以外其它全部所需资源
• 阻塞状态（blocked）：进程因某种要求得不到满足，只好等待，我们称之为运行“受阻”。处于阻塞状态的进程是无权获得 CPU 的

状态转换：

• 新建的进程都进入就绪状态，即 后备 to 就绪
• 当进程被选中分配 CPU，由 就绪 to 运行
• 如果这个进程运行一切顺利，则 运行 to 撤销
• 但当这个进程因为某些原因暂时不能继续往下，就 运行 to 阻塞
• 还有一种情况是当有优先级更高的进程进来，则 运行 to 就绪
• 而阻塞进程的受阻得到解决后，可 阻塞 to 就绪

挂起状态：把内存中当前某个尚不能运行的进程调到外存上去。腾出空间接纳更多的进程，这一处理称作挂起

Linux 2.4 版本的六种状态

3.4 进程的创建与撤销

进程从产生到消亡的整个过程都是由操作系统来控制的，操作系统中实现进程控制的功能程序叫 原语

3.4.1 什么是原语

机器指令构成的一种实现特定功能的小程序，它的运行具有不可分个性

特点：

• 贴近底层
• 最重要的
• 运行过程具有原子性
• 系统小程序

进程管理原语：

• 进程创建/撤销/阻塞/唤醒/挂起/激活/调度原语

其他类型的原语：

• 进程通信用的原语：用于实现进程之间的通信，如消息发送原语、消息接收原语
• 资源互斥与同步用的原语：解决资源互斥访问的，主要有 P 操作原语和 V 操作原语
• 资源管理用的原语：主要有请求资源的原语和释放资源的原语

3.4.2 进程创建原语

什么时候会被运行：

• 批作业调度
• 交互作业提交
• 系统提供服务
• 用户程序创建子进程

如何创建

• Create_Process()

• 索取一个空白的 PCB 块

• 填入进程信息

  • 填入进程标识
  • 填入优先级
  • 填入内存地址：请求分配内存或 JCB 或父进程的内存地址填入
  • 填入资源清单：请求分配设备或 JCB 或父进程资源填入
  • 填入家族信息：用户名或父进程名
  • 填入现场信息：初始状态数据
  • 填入进程状态：就绪

• 挂入就绪队列

• 若需要将进程代码和数据集装入内存，可启动加载程序

3.4.3 撤销进程

• 进程自行终止
• 用户或父进程的原因使进程终止
• 运行超时而终止
• 运行出错而终止

如何撤销

• Destroy (id_name)
• 根据 id_name 查找被终止进程的进程控制块 PCB
• 若该进程的状态是运行，则置调度标志为 true
• 回收 PCB 中登记的全部资源
• 将进程的 PCB 从所在的队列摘下来，等待其他程序来搜集信息
• 对于该进程的所有子进程 Sub，递归调用 End_Process(Sub)，将子进程终止
• 如果调度标志 = true ，启动进程调度程序

3.5 父进程与子进程

进程什么时候被创建：

• 批作业调度：操作系统创建用户进程
• 交互作业提交：操作系统创建用户进程
• 系统提供服务：操作系统创建系统进程
• 用户程序创建子进程：用户程序创建用户进程，通过 fork() 实现

进程家族树：

• 父进程：执行过程中创建了其他进程的进程
• 子进程：被父进程创建的进程
• .etc

3.5.1 fork() 说明

pid_t fork(void) 函数包含于头文件 unistd.sh

函数功能：

• 建立一个新的子进程。其子进程会复制父进程的数据与堆栈空间，并继承父进程的用户代码、组代码、环境变量、已打开的文件代码、工作目录和资源限制等
• 如果调用成功，则在父进程会返回新建立的子进程代码 PID，而在新建立的子进程中则返回 0

调用失败的原因：失败则直接返回 -1

• 系统内存不够
• 进程表满
• 用户的子进程太多，一般不超过 25 个

3.6 进程状态转换控制原语

3.6.1 阻塞原语

什么时候调用阻塞原语：

• 当正在运行的进程需要等待某一事件而发生运行受阻时，它通过中断请求系统服务
• 系统按照进程的需求进行适当处理后，启动“进程阻塞原语”将该进程阻塞起来

是么情况引起受阻：

• 等待 I/O
• 请求资源得不到满足
• 进程同步约束
• 服务进程无事可做

如何阻塞:

• 获取 PCB 的 id
• 从 running 队列中移除该 id 的 PCB
• 保存 PCB 的上下文
• 将 PCB 状态设置为阻塞
• 将进程插入阻塞队列
• 启动调度程序选择下一个被执行的进程
• 结束

3.6.2 唤醒原语

什么时候调用唤醒原语：

• 当系统发生某一个事件时，正在等待该事件的进程需要立即被唤醒，由 阻塞 变为 就绪 状态

什么情况下会唤醒：

• 所等的 I/O 操作已完成
• 请求的资源得到了满足
• 进程同步约束已撤销
• 服务进程收到新的任务

如何唤醒：

• 将当前进程的上下文保存到系统栈
• 从阻塞队列查找等待该事件的进程 PCB
• 将 PCB 从阻塞队列上摘下来
• 将其状态设置为 就绪，将 PCB 挂入就绪队列
• 弹出系统栈中的进程上下文，置入 CPU 让被中断的进程恢复运行
• 结束

3.6.3 挂起原语

什么时候会调用：

• 当前内存空间紧缺，部分进程优先运行
• 应用户的要求，将用户进程挂起
• 应父进程的要求，将其子进程挂起

如何挂起：

• 找到被挂起进程的 PCB ，获得其内存地址，将内存空间归还给存储管理模块
• 进程状态阻塞挂起为 挂起阻塞 ，或者就绪转为 挂起就绪，将 PCB 从原队列转入相应队列
• 森请外存交换区空间，换出进程，地址写入 PCB
• 结束

3.6.4 激活原语

什么时候会调用：

• 有进程运行完毕，当前内存空间不紧张
• 应用户要求，将其进程激活
• 应父进程的要求，将其子进程激活
• 进程自身设定的挂起周期已完成

如何激活：

• 扫描 挂起就绪队列 找到被激活进程的 PCB
• 将 PCB 从所在的队列上摘下来
• 按 PCB 等级的空间需求，申请内存，加载到内存中
• 归还外存交换区空间
• 将进程设置为 就绪，插入就绪队列
• 结束

2.7 进程调度

调度程序功能：从处于就绪状态的进程中，按照某种调度策略，选择一个进程切换给 CPU，使其状态从就绪转为运行

2.7.1 非抢占式调度

可能性：

• 进程运行完毕推出
• 运行受阻
• 运行出错，非正常终止
• 遇到不可挽回的故障

2.7.2 抢占式调度

也称剥夺式调度，一般用于有实时需求的系统

可能性：

• 主要指系统正常运转期间，如果某种事件出现，系统将迫使正在运行的进程停下来，将 CPU 控制权交给其他进程
• 其思想源于对高紧迫度作业的响应

3.7.3 进程调度算法

• FCFS：先进入就绪队列的进程先调度

• SPF：最短进程优先调度

• HPF：最高优先级调度

• HRF：最高相应比优先调度

• SRT

• RR：按时间片轮转调度，多用于分时系统

  • 进程轮流使用 CPU，各用一个时间片，时间片用完管理程序停止它的运行，并将它转入就绪队列尾部，调度下一个进程。进程失去 CPU 不是自愿的，而是被系统剥夺的
  • 启动时机：
    • 一个时间片运行结束
    • 当前进程运行结束
    • 正在运行的进程因运行受阻主动放弃控制权
  • 时间片确定的原则
    • 进程的刀数较多时，取小一点，反之大一点
    • 系统要求的响应时间比较苛刻时，取小一点，反之取大一点

• 多队列调度

  • 设置多个就绪队
  • 就绪对优先级不同，优先级高的队列优先调度
  • 优先级高的队列为空时，再调度低优先级队列

• 多级队列反馈调度

  • 设置 n 个队列 Q1，Q2，，，Qn
  • 记 Qi 的优先级为 Pi，有 P1 > P2 >，，，> Pn
  • 记 Qi 的时间片为 qi，有 q1 < q2 <，，，< qn
  • 新建进程进入 Q1 队
  • 只有 Qi 为空时，才调度 Qi+1 中的进程
  • 进程 p 在 Qi 中被调度执行，若时间片 qi 已到但尚未结束，则进程 p 转为就绪状态进入 Qi+1 队，进程 p 在 Qn 中被调度执行，若时间片已到但尚未结束，则进程转为就绪状态仍入 Qn 队

  终端型用户满意：终端型作业都是交互型，比较短，进入第一队列后优先调度，一般只要一个小时间片就可完成

  短的批处理作业用户满意：短的批处理作业开始时首先进入第一个队列，能即使被响应，若轮转一周不能完成的花，通常只需在第二乃至第三队列上各执行一个时间片就能完成，作业的周转时间仍比较短

  长的批处理作业用户满意：一个长的批处理作业进入系统后，将依次在 1，2，，，n -1 队列中各运行一个时间片，最后进入第 n 各队列进行轮转运行，一般不必担心受冷落，一旦进入后面的叫徐对，获得的时间片比较长，系统调度开销比较少

2.8 实时任务调度

• 实时任务是一类对时间要求较为严格的进程，支持这类任务运行的系统成为实时处理系统
• 实时系统分为硬实时系统和软实时系统
• 调度方法一般是剥夺式的

2.8.1 非周期实时任务的分类及调度方法

• 紧迫型实时任务调度

  • 多见于一些专用的、响应时间要求特别苛刻的数据采集和控制系统中，所要求的响应时间很短，一般是微秒级
  • 采用立即抢占的 HPF 调度算法

  

• 普通型的实时任务调度

  • 大多数自动控制系统对响应时间的要求都不是太高，一般是毫秒级的，它允许的相应时间长度与时钟中断的周期基本吻合

  • 采用基于时钟中断抢占的高优先级调度

    

• 宽松型的实时任务调度

  • 要求的响应时间比较长，一般可达数百毫秒，甚至数秒
  • 比如信息查询系统，这类任务的要求差异很大，通常又有很多不同的处理、
  • 采用非抢占的 HPF

  

  • RR 算法

  

2.8.2 周期性实时任务

信号检测和过程控制系统中呈现周期性运行规律的任务

• 最小剩余时间调度算法

  • 周期任务 A 在第 i 次运行前的剩余时间 FA(i) 是

  

  • TA 任务 A 的周期长度
  • TsA 为任务 A 每次执行时间长度
  • t 为系统的当前时间

2.9 线程的引入

操作系统中引入进程，目的是为了使多个程序并发执行，以改善资源使用率和提高系统效率

操作系统中再引入线程，则是为了减少程序并发执行时所付出的时空开销，使得并发粒度更细，并发性更好

2.9.1 线程是什么

• 线程是现代操作系统引入的一种执行实体
• 线程称 轻型进程，是进程的组成部分
• 进程是资源占有单位，线程只是 CPU 的调度单位
• 一个进程在运行过程中可以创建多个线程
• 线程共享所属进程的资源，自己只有 TCB 和很少的栈区

2.9.2 线程的实现

• 内核级线程：因为是系统创建的，所以对于操作系统来说每一个线程的信息都可见，管理、控制、调度都由系统完成

• 用户级线程：由用户程序自己创建、管理、调度。在用户空间可见

2.9.3 进程和线程的区别

进程：

• 进程是个独立的实体单位
• 独立占有资源：进程拥有对资源的控制权或所有权
• 独立参与调度/执行：进程是一个可被操作系统调度和分派的单位

线程：

• 线程仅是分派（调度运行）的单位
• 线程不是单独占有资源的单位，线程共享其所属进程的资源

2.10 处理机的四级调度

调度的主要目标：

• 选择哪个实体进入内存、选择哪个实体占用 CPU

调度的主要层次：

• 作业调度
• 中级调度
• 进程调度
• 线程调度

2.10.1 典型的三级调度

作业从进入系统成为后备作业开始，直到运行结束退出系统位置，需经历不同级别的调度，交互式作业不经过高级调度，直接进入内存

• 高级调度：
  • 又称作业调度，长程调度
  • 从处于后备状态的作业中选择一道或几道，装入内存
• 中级调度：
  • 又称中程调度
  • 优先从处于挂起就绪状态的进程之中选择一个或者几个，将之激活
• 低级调度：
  • 又称进程调度，短程调度
  • 从处于就绪状态的进程中选择一个，切换给 CPU 执行

2.10.2 线程调度

• 线程称 轻型进程 是进程的组成部分
• 进程是资源占有单位，线程是 CPU 的调度单位
• 线程共享所属进程的资源
• 线程分为用户级线程和内核级线程，调度方式不同
  • 用户级线程的调度
    • 操作系统进行进程调度
    • 用户进程自己进行线程调度
  • 内核级线程的调度
    • 操作系统直接进行线程调度

四、进程并发控制篇

4.1 互斥与同步的基本概念

操作系统在管理和控制资源分配与使用方面，应当保证进程对临界资源的访问满足以下 3 点

• 互斥访问要求
• 不至于产生死锁
• 不能有饥饿进程给

4.1.1 并发

• 单处理器多道程序设计系统中，多个进程交替执行
• 多个并发进程再一个时间段内都处于运行状态
• 共享系统资源
• 每个进程都走走停停
• 并发带来的异步性

4.1.2 并发带来的问题

• 并发进程的相对执行速度是不可预测的 ，取决于其他进程的活动、操作系统处理中断的方式以及操作系统的调度策略

4.1.3 互斥

• 当一个进程在临界区访问临界资源时，其他进程不能进入相关临界区访问该资源
• 临界资源一个时刻只允许一个进程使用
• 进程使用该临界资源的顺序没有约束
• 体现竞争关系

4.1.4 同步

• 两个进程或线程不仅不能同时访问同一个资源，连先后顺序也要做限制
• 体现协作关系

4.1.5 临界资源

• 也叫互斥资源
• 一种一次只能为一个进程服务的共享资

4.1.6 临界区

• 进程体中使用临界资源的代码段
• 使用同一临界资源的不同代码段叫做相关临界区
• 当一个进程已经再临界区中运行时，也就是已经在使用临界资源了，其他进程不能进入相关临界区

4.1.7 死锁

• 两个或两个以上的进程，因其中的每个进程都在等待其他进程做完某些事情而不能继续执行，所有进程都阻塞等待，而且得不到解决

4.1.8 活锁

• 两个或两个以上进程为了响应其他进程中的变化而持续改变自己的状态，但不做有用的工作

4.1.9 饥饿

• 一个可运行的进程被调度程序无限期的忽略，不能被调度执行的情形

4.1.10 原子操作

• 保证指令序列要么作为一个组来执行，要么都不执行

4.2 软件方法解决进程互斥

• 空闲让进
• 忙则等待
• 有限等待
• 让权等待

软件方法解决互斥问题失败的原因：

• 临界区前后所加代码越多，执行过程随时被打断的情况
• 所加的代码中的变量本身也是临界资源
• 没有考虑让权等待

4.3 信号量机制解决同步互斥问题

基本原理：

• 两个或多个进程通过简单的信号进行合作
• 任务复杂的和需求都可以通过适当的信号结构得到的满足

4.3.1 信号量机制实现要素

• 信号量（Semaphore 类型，内含一个阻塞队列）
• P 操作原语（wait）

• V 操作原语（signal）

4.3.2 记录型信号量

• 一个记录型信号量包含两个分量：信号量的值、信号量的等待队列指针

4.3.3 解决互斥问题

• 一种 CR 设置一个信号量
• 信号量的初值设置为系统初始状态 CR 的可用量
• P 操作用于临界区前，相当于进入 CS 之前申请 CR
• V 操作用于临界区后，相当于出临界区后释放 CR
• P、V 操作必须成对匹配

使用 semaphore mutex：这样声明的信号量 mutex 用于互斥问题

mutex.value：

• 目前 CR 有 mutex.value 个可用
• 目前 CR 没有可用的
• 目前有 |mutex.value| 个进程因等待该 CR 而阻塞

4.3.4 解决同步问题

• 一种同步信号设置一个信号量
• 信号量的初值设置问系统状态下信号的有无
• P 操作用于临界区前，相当于检查同步信号
• V 操作用于临界区后，相当于发出同步信号
• P、V 操作不成对匹配

使用 semaphore s：这样生命的信号量 s 用于同步问题

s.value：

• 目前有 s.value 个 s 对应的同步信号
• 目前没有 s 对应的同步信号
• 目前有 |s.value| 个进程因等 s 对应的同步信号而阻塞

4.3.5 互斥、同步解决方法之异同分析

• 信号量的设置
• 信号量的初值
• P、V 操作的含义
• P、V 操作的匹配

4.3.6 记录型信号量解决问题的步骤

• 分析问题中的进程、资源
• 分析进程间的关系
• 分别设置互斥、同步信号量
• 写出并发进程体，找出相关 CS
• 分别加 PV 操作并分析结果

4.4 生产者与消费者问题

• Sin 为可放入信号，初值为 n
• Sout 为可取信号，初值为 0

• 生产者：
  • 每放入一个产品，Sin = Sin - 1，Sout = Sout + 1
  • 可以看到，Sin 对应的是剩下空余空间的个数，Sout 是已放入的个数
• 消费者：
  • 每次取之前查看 Sout，若 Sout > 0 则取，否则 Sout-- 并等待生产者放入产品
  • Sout = Sout - 1
  • Sin = Sin + 1

4.4.3 经典生产者-消费者问题

• 系统里有若干个合作的进程互斥使用由 r（ r > 0）个缓冲块组成的缓冲环，其中 n（ n > 0 ）个缓冲块组成的缓冲环，m（ m > 0 ）个消费者进程
• 任何一个生产者进程都可以将自己的产品存入环内的一个缓冲块，任何一个消费者可以将环内的一个产品去除。生产者远远不断地生产并存入产品：消费者周而复始地从环中取出产品并消费掉

假定使用的约束条件是：

• 当环中有空闲缓冲块时，允许任意生产者进程把它的产品存入
• 当环中无空闲缓冲块时，则试图将产品存入缓冲区环的任何生产者进程必须阻塞等待
• 当环中尚有为取出的产品时，允许任意消费者进程把其中的一个产品取出
• 当环中没有未取出的产品时，试图从该环内取出产品的任何消费者进程必须阻塞等待

解决方案：

Var mutex: Semaphore: =1;

Var Sin,Sout: Semaphore: = n, 0;

先检查同步，如是否能放/取，再检查互斥，如是否有人在访问

• 生产者：

• 消费者：

4.5 读者写者问题

• 有一个数据块被多个用户共享，其中一部分用户是读者，另一部分是写着
• 我们规定：读者对数据块是只读的，而且允许多个读者同时读，写着对数据块只是写的，当一个写着正在向数据块些信息的时候，不允许其他用户使用

进程：读者和写者

资源：要操作的对象

写者：跟任何一个其他的进程都互斥

读者：读者之间不互斥，但与写者互斥

解决方案：

为了判断 reader 是不是第一/最后一个，引入 counter

var mutex, Rmutex: semaphore: = 1, 1;

var counter: integer: = 0;

Parbegin Writeri(); Readerj(); Parend;

4.6 理发师问题

有一位理发师，一把理发椅和 n 把供等候理发的顾客坐的等候椅。如果没有顾客，理发师便在理发椅子上睡觉；当一个顾客到来时，唤醒理发师进行理发。如果理发师正在理发时又有新顾客到来，有空椅子可坐，他就坐下来等。如果没有空椅子，就立即离开。

进程：理发师、顾客

资源：理发椅、等候椅

同步：理发师、顾客、理发椅

互斥：顾客、顾客、等候椅

如果单纯的设置 mutex 为椅子的数量，当 P(mutex) 为 -1 时，进程会进入阻塞状态，与直接离开不符，故设置临界资源 chairs 来进行判断，当没有椅子，直接结束进程

var comming: somaphore: = 0;

var calling: somaphore: = 0;

var cutting: somaphore: = 0;

var finished: somaphore: = 0;

var chairs: integer: = n;

var mutex: semaphore: = 1;

客户：

理发师：

4.7 哲学家就餐问题

进程：哲学家

资源：筷子

4.7.1 错误算法

如果所有哲学家同时饿了想吃面，则每个人都只拿到一只，进入阻塞状态，形成死锁

4.7.1 算法一

控制同时能吃面的人数

4.7.2 算法二

给椅子编号，奇数上的先拿左筷子，偶数位的先拿右筷子

奇数位：

偶数位：

4.7.4 算法三

要么两根一起拿，要么一根也不拿，设新的信号量机制：**[ AND型 ] 信号量集机制**

信号量集机制：

• 用一个 P 操作，可以同时申请到两个或多个临界资源
• 用一个 V 操作，可以释放两个或多个临界资源

信号量集机制设计需求：

• P 原语具有同时给多个信号量减 1 的功能
• 只有各个信号量都是绿灯才减 1 进入临界区
• 任意信号量是红灯，进程都要让权等待
• 并将 P 原语的第一条指令作为断电地址，保存到该进程的 PCB 中，等回复运行时重新执行 P 原语

4.8 管程机制

管程是由局部数据结构、多个处理过程和一套初始化代码组成的模块

• 这是一种具有面向对象程序设计思想的同步机制
• 它提供了与信号量机制相同的功能

特征：

• 管程内的数据结构只能被管程内的过程访问，任何外部访问都是不允许的
• 进程可通过调用管程的一个过程进入管程
• 任何时间只允许一个进程进入管程，其他要求进入管程的进程统统被阻塞到等待管程的队列上

要素：

• 条件变量：关联一个阻塞队列
• P：当遇到同步约束，将执行该操作的进程阻塞在条件变量关联的阻塞队列上
• V：从条件变量关联的阻塞队列上唤醒一个进程，让他恢复运行，若队列上没有进程在等待，就什么也不做

4.8.1 管程解决生产者与消费者问题

• 定义一个数组 buffer：表示用于传递产品的缓冲区环
• 定义局部变量 in、out：表示在缓冲区环中生产者放的文职、消费者取的位置
• 定义变量 counter：记录缓冲区环中产品的数量
• 定义 full：生产者的条件变量。当一个试图存放产品的生产者发现缓冲区环已满时，执行 P(full) 将之组赛道 full 的关联队列上
• 定义 empty：消费者的条件变量。当一个试图取产品的消费者发现缓冲区环已空时，执行 P(empty) 将之阻塞到 empty 的关联队列上

解决方案：

• 定义管程

• PUT()

• GET()

• 生产者与消费者

4.9 死锁的发生与描述

一组相互竞争系统资源或者进行通信的进程间的永久性阻塞

4.9.1 现象

• 每个进程获得了一部分资源，又申请另外的资源，得不到而转入阻塞
• 若无外力作用，这些进程会一直阻塞下去

4.9.2 死锁的危害

• 陷入死锁圈的进程无限期阻塞等待
• 陷入死锁圈的资源被浪费
• 更多进程卷入死锁
• 甚至系统死机

4.9.3 产生死锁的原因

• 动态资源分配策略
• 资源可用数量少于需求数量
• 进程并发过程的偶然因素

4.9.4 必要条件

• 互斥条件：进程请求的资源属于临界资源，每一瞬间只能由一个进程使用，其他申请该资源的进程等待
• 不可剥夺条件：进程获得某资源后，便一直占有她，知道用完为止才释放，其他进程不可剥夺
• 请求和保持条件：允许一个进程在保持已有资源不放弃的情况下，进一步请求新资源，被阻塞时也不会释放已有的资源
• 环路等待条件：一组进程的占有资源情况与请求资源情况构成一个环形链，比如 P1 等待 P2 的资源，P2 等待 P3 的资源，P3 等待 P1 的资源

4.9.5 资源请求分配图

4.9.6 资源请求分配矩阵

• 若有 n 个进程，m 类资源，则首先设置三个 n × m 的二维矩阵

  • 需求总量矩阵 Max[][]
  • 资源占有矩阵 Allocation[][]
  • 尚需矩阵 Need[][]
  • 如，Need[i][j] 标识进程 i 尚需第 j 类资源的数量为 k 个

• 另设几个一维数组

  • 资源总量数组 Total[]
  • 可用（剩余）资源数组 Available[]
  • 申请资源数组 Request[]

4.9.7 死锁的解决方法

• 事前处理：针对性采取措施，让死锁没有机会发生
  • 死锁预防
  • 死锁避免
• 事后处理：及时检测、及时解除
  • 死锁检测
  • 死锁解除

4.10 死锁的预防

通过破坏死锁的必要条件，只要有一个不满足，就不会发生死锁

• 互斥条件：互斥条件共享资源不能改成同时共享，破坏该条件行不通
• 不可剥夺条件：互斥共享资源被剥夺后，进程需要重新执行，破坏该条件行不通
• 请求和保持条件：进程运行整个过程中所需资源要申请就一次性全部申请，要不就不申请
  • 静态资源分配策略
    • 两个关键字：
      • 一次性
      • 全部
    • 两个要点：
      • 在进程运行开始前，一次性申请全部所需资源
      • 在进程运行结束时，一次性释放全部所占资源
    • 缺点：
      • 资源有效利用率会降低
      • 进程并发推进的速度会降低
    • 优点：
      • 进程一定不会发生死锁
• 环路等待条件：给资源排一个序号，按照从小到大或从大到小的顺序申请资源
  • 按序资源分配策略：即要用某个资源时，在后期还会用到另一个资源，序号比这个小或大，则先申请后面所需的，再来申请当前想要的，如果后面所需的没有获取到，也不会去申请当前想要的

4.11 死锁避免

在每个进程的每次提出动态资源申请时，加设银行家算法，以决定是否满足该请求

4.11.1 银行家算法的思路

• 银行家拥有一笔周转资金，客户申请贷款
• 检查客户信用，了解客户投资前进，判断有无出现呆账坏账的危险
• 确无危险，才贷出

前提是系统采用动态资源分配策略，每个进程提出资源申请时加一道检查，假设分配，检查系统是否安全，安全则实施分配，不安全则不分配，进程阻塞等待

何谓安全

• 安全状态不是死锁状态
• 安全状态是没有死锁危险的状态
• 死锁状态是不安全状态
• 不是所有不安全状态都是死锁状态

如何判断

• 在当前状态下至少能找到一个安全序列即为安全状态
• 当前状态下没有安全序列
• 安全序列：各进程能依次满足资源需求并运行完成的一个序列

4.11.2 银行家算法的数据结构

• 需求总量矩阵 Max[][]
• 资源占有矩阵 Allocation[][]
• 尚需矩阵 Need[][]
• 资源总量数组 Total[]
• 可用资源数组 Available[]
• 申请资源数组 Request[]
• 安全检查过程中记录 Available[] 的变化
• 安全检查过程中记录各个进程是否能完成 Finished[]

4.11.3 银行家算法的步骤

• 检查请求是否合法
• 检查系统可用资源是否足够
• 再假定分配，检查系统是否有发生死锁的危险，无危险则分配，有危险则不分配，让进程阻塞等待

4.11.4 银行家算法的应用

设系统有 3 类资源，5 个活跃的进程 Total=(10,5,7)

• 问：当前系统是否安全？

  • 求出 Need[]

  

  • 通过系统本来的资源数量 - 已分配出去的资源数量 的到系统当前可用为 [3,3,2]

  

  • 最后可找出安全序列

• 若某一进程提出请求，该如何调用银行家算法：

  • 如果 request > Need，该进程的本次请求超过了它所宣布的最大值，系统拒绝分配，出错返回 Return(ERROR)
  • 如果 request > Available，表明系统当前的可用资源不能满足该进程的请求，应推迟分配，将该进程阻塞等待
  • 做假定
    • Available = Available - request;
    • Allocation = Allocation + request;
    • Need = Need - request
  • 调用安全算法，测试系统是否为安全状态，如果返回 TRUE，则表示安全，进行分配，否则将第三步的作废，回复第三步之前的状态，让该进程阻塞等待

五、存储管理篇

5.1 存储管理概述

目标：

• 内存的合理分配使用
• 提高内存利用率
• 程序、数据在内存中顺利读写
• 小内存运行大程序

功能：

• 内存的分配和回收
• 地址重定位
• 地址共享和保护
• 地址扩充

5.1.1 内存的分配和回收

5.1.2 地址重定位

• 将逻辑地址转换为物理地址
• 物理地址：存储单元的实际物理单元地址
• 逻辑地址：用户空间中使用的相对地址

分类：

• 静态重定位
  • 地址转换工作在进程执行前一次完成
  • 无需硬件支持，易于实现，但不允许程序在执行过程中移动
• 动态重定位
  • 地址转换推迟到最后的可能时刻，即进程执行时才完成
  • 允许程序在主存中移动过，便于主存共存，主存利用率高

5.1.3 地址共享与保护

共享的含义：

• 共享内存储器资源，让多个进程同时进入内存区域，共享一个存储器
• 共享内存储器的某些区域，即允许两个或多个进程访问内存中的同一段程序或数据

保护的含义：

• 用户进程不能访问或修改系统区
• 用户进程不能访问或修改其他进程的用户区

保护的方法：

• 存储键保护：

  • 系统将主存划分为大小相等的若干存储块，并给每个存储块都分配一个单独的保护键（锁）
  • 在程序状态字 PSW 中设置有保护键字段，对不同作业赋予不同的代码（钥匙），钥匙和锁相匹配才允许访问

• 界限寄存器：

  • 上下界防护：硬件为分给用户作业的连续的主存空间设置为一对上下界，分别指向该存储空间的上下界
  • 基址、限长防护：基址寄存器存放当前正执行着的程序地址空间所占分区的始址，限长寄存器存放该地址空间的长度

5.1.4 地址扩充

内存容量是有限的，当内存资源不能满足用户作业需求时，就需要对内存进行扩充，内存扩充不是硬件上的扩充，而是用存储管理软件来实现的逻辑扩充

• 覆盖技术
• 对换技术
• 虚拟存储技术

5.1.5 存储管理方法

• 连续存储管理
  • 单一连续区方式：内存用户区的全部空间只存放一个进程
  • 多分区方式：内存被分为多个分区，每个分区存放一个进程
    • 固定多分区
    • 动态多分区
• 非连续存储管理
  • 分页方式：内存被划分为多个等长的存储块，每个进程占用其中若干块，整个内存允许有多个进程同时驻留
  • 分段方式：对分段结构的应用程序，按照段长度分别为之分配内存空间
  • 段页方式：在分段管理的基础上加分页式管理形成的管理方式

5.2 程序的编译链接与地址重定位

地址重定位：又叫地址转换，将逻辑地址转换称物理地址

静态重定位：

• 地址转换工作在进程执行前一次完成
• 无需硬件支持，易于实现，但不允许程序在执行过程中移动

动态重定位：

• 地址转换推迟到最后的可能时刻，即进程执行时才完成
• 允许程序在主存中移动，便于主存共存，主存利用率高

5.3 连续分区存储结构

实质特点：一个进程装入连续的一块内存空间

5.3.1 单分区方式

• 内存用户区的全部空间只存放一个进程

5.3.2 多分区方式

内存被分为多个分区，每个分区存放一个进程。每个瞬间可有多个进程驻留在内存的不同分区中

• 固定多分区
• 动态多分区

5.3.3 主存分配表

Memory Allocation Table (MAT)

• 分区号：每个分区都有一个编号，用以区别不同分区
• 起始地址：分区的起始地址，即首地址
• 长度：分区的总长，一般以 KB 为单位
• 占用标志：记录分区的使用状态，若占用标志为 0，表明该分区空闲，可进行分配

MAT 表

空闲分区链：是 MAT 的子表，只包含空闲分区

• 分配：通过空闲分区链快速搜索内存的空闲区，从中找出最合适的分区分配出去，将该节点从链上删除
• 回收：按其地址或者大小在链中找到合适的位置，插入一个新节点，若存在相邻的空闲区，则需要的花可将相邻空闲区合并

5.3.4 主存分配算法

• 首次适合算法 First_Fit
  • 也称最早适应算法，系统将内存分区按地址递增顺序登记到内存分配表或其他数据结构中
  • 每次进行内存分配时，系统根据进程申请空间的大小，从头到尾顺序扫描内存分配表，从中找到的第一块能够满足要求的空闲区，就立即分配出去
• 循环首次适应算法 Circle_First_Fit
  • 该算法的思想是，每次存储分配总是从上次分配的位置开始，向尾部查找，查到的第一块可满足用户需求的空闲空间，分配给用户。当查到尾部仍没有合适的，转到头部继续
  • 为什么要从上次分配的位置开始？
    • 因为在一些需求不大的系统上，高序号的地址长期得不到调用，如果长时间不用，故障率会长时间提高。
• 最佳适应算法 Best_Fit
  • 在内存分配时，从空闲分配去找到一块满足进程需求的最小空闲区分配给他
  • 这种做法减少了将大空闲区进行多次分割造成的空间浪费，但容易形成一些很小的碎片无法使用，同样不能提高内存利用率。另外，每次分配时都要对整个内存区进行从头到尾的搜索，系统开销大
• 最坏适应算法 Worst_Fit
  • 在内存分配时，从空闲分区表中找到一个满足长度要求的最大空闲区进行分配
  • 这种算法部分缓解了由外碎片引起的浪费，适合于中小作业的运行，但对大作业的运行是不利的。与最佳适应算法一样，每次分配需要搜索一遍内存，效率会受到一定影响

5.4 固定多分区存储管理

5.4.1 单分区存储管理

这种存储管理非常简单，适用于单用户单任务系统

基本原理：把内存的用户区视为一个独立的连续存储区，任何时刻只将他分给一个作业使用

缺点：

• 因为任何时刻最多只有一个程序独占内存，无论在该程序执行过程中，还是 CPU 等待 I/O 时都不能让其他用户使用
  • CPU 利用率不高
  • 外设利用率低
• 进入系统运行的作业所要求的存储空间较小时，剩余较大的空白区未被利用，只能白白浪费

5.4.2 固定多分区存储管理

基本原理：

• 将内存用户区划分成多个大小相等或不等的固定分区，每一个分区可以装入一个进程。这样，内存中可同时容纳若干个进程
• MAT 表可以用静态数组实现

分区要求：

• 分区大小可以相等，也可以不等
• 每个分区的起始地址和长度时固定的

有可能出现的问题：

• 大的进程无法装入
• 效地进程装入大分区出现内部碎片

解决方法：

• 主存分配采用 Best_Fit
• 地址重定位采用 静态重定位，因为固定多分区不许迁移
• 地址保护可以用 上下限，也可以采用 基址限长

缺陷：

• 分区数目实现确定，限制了系统中活动进程的数目
• 分区大小在系统生成阶段实现设置，大作业有可能无法装入，小进程不能有效地利用分区空间
• 内碎片 现象降低了内存有效利用率

5.4.3 动态多分区存储管理（可变分区）

基本原理：

• 系统不预先划分固定分区，而是在装入进程时根据进程的实际需求量划分出一个分区给他使用
• MAT 表需要用动态数组实现

分配方式：将一个存储容量为 n 的内存空间，根据进程所需容量 x，划分成 x、n - x 两部分，x 部分分配给进程，n - x 部分记为未分配

回收方式：将多个连续的空闲分区组合在一起

• 主存分配采用 Worst_Fit
• 地址重定位采用动态重定位

5.5 基本分页存储管理

基本原理：

• 内存呢被划分成大小固定相等的块（Frame帧/页框/主存块）且块相对比较小
• 每个进程装入时被分成同样大小的页（Page）一页装入一帧
• 整个进程被离散装入到多个不连续的帧

总结：

• 离散存储，利于大进程装入
• 只有很少的页内碎片，提高内存利用率
• DS：位示图、页表：动态地址重定位
• 页面共享不易实现

5.5.1 位视图

• 通过在位视图中查找值为 0 的帧
• 设 i 为字，j 为位，k 为帧，L 为字长
  • k = i * j;
  • i = k / L;
  • j = K % L;

5.5.2 页表

为了保证程序的正确运行，分页管理机制应为每个进程一个数据结构——页表，页表中等级进程各页面对应的帧号，供地址映射使用

页面分配算法：

• 计算请求者需要的总帧数 N
• 查位图，若找不到足够的空闲帧，编制分配失败报告返回
• 索取一个空闲页表
• 从位图中找出 N 个为 0 位，计算出对应的帧号，填入 PT
• 位示图中将这些位改为 1
• 将 PT 起始地址填入进程 PCB
• 结束

地址划分：

• 进程装入之前，逻辑地址是一维的
• 进程装入之后，逻辑地址分为两维
• 例题：若机器的地址码是 16 位，页面长度是 1KB
  • 求划分结果
    • 总长度 16 位，每页 1KB，即每页需要 10 个二进制位来表示
    • 总共 16 位，其中 10 位拿来表示页内地址，那么还剩 6 位作为页号
    • 6 位做也好也就是说总共可以分 2 ⁶ = 64 页
  • 求允许进程最大空间
    • 64 页，每页 1KB，则说明最大 64KB

5.5.3 地址重定位

• 页表寄存器：寄存当前正在 CPU 执行的进程的起始地址和页表的长度（分页数）
• 转换：根据逻辑地址的页号取出对应的帧，然后与偏移量放在一起表示物理地址
• 内存保护：
  • 在根据页号取帧之前进行第一次，查看该页号是不是合法页号，即有没有在页表的行之内
  • 在偏移量与帧相加时对偏移量进行第二次，查看该偏移量是不是合法的长度，即有没有在页表的列之内
  • 在二者相加之后进行第三次，查看要做的操作，地址合不合法

5.6 基本分段存储管理

• 段是一个逻辑单位，是进程的一个组成部分。如主程序段、子程序段、数据段
• 在结构程序设计中，进程自然分段
• 用户源程序使用的符号地址是二维的：<段名，变量名>
• 翻译之后的逻辑地址是二维的：<段号，段内地址>

原理：

• 进程的程序和其相关的数据按逻辑分段
• 段有一个最大长度限制，但不要求所有程序的所有段的长度都相等
• 一段占用一块连续存储区
• 各段占用不连续分区

总结：

• 离散存储，一段连续装，各段不连续
• 内存仍然按分区管理，会产生外碎片
• DS：MAT、段表，动态地址重定位
• 分段共享非常方便

5.6.1 按逻辑分段

在分段机制中，一个进程的地址空间可以包含以下不同的段

• 代码段
• 数据段
• 堆栈段
• 内存共享段

5.6.2 记录内存使用情况的数据结构

• MAT
  • VS 动态多分区中的 MAT
  • 相同点：
    • MAT 的一个表项，对应内存一个分区
  • 不同点：
    • 动态多分区中，一个分区存放一整个进程
    • 分段存储中，一个分区存放进程的一个段
    • 一个进程离散分成多个段装入多个不连续的分区
• 空闲分区表/链
• 段表 ST：为每个进程设置一张段表，用来记录各个段地址的映射关系

5.6.3 地址重定位

• 提取逻辑地址中的段号
• 比较段号与段表控制寄存器中的段长度，如果超出段表长度，则返回 内存定位错误，终止进程，否则继续向下执行
• 从段表控制寄存器中给出的段表首地址开始，以段号为索引查找该进程对应的段表，得到欲访问段的首地址
• 用欲访问段的首地址，加上逻辑地址中的偏移量得到物理地址

5.6.4 分段保护

• 第一级保护是防止进程发生超出存储空间的访问
• 第二级保护是组织进程超出访问权限的读写

步骤：

5.6.7 分段共享

如果多个用户进程需要共享内存中的某些代码段或数据段时，可将内存中共享段的起始地址及长度，填入这些进程的段表当中，就可以共享一个逻辑上完整的段信息

**共享段表 SST**：

为了实现段的共享，系统设一个 共享段表，记载各个共享段的使用情况，任何一个进程调用共享段时，系统都将访问该表

5.7 基本段也是存储管理

5.7.1 分段 VS 分页

• 分页存储利于大津城装入，内存利用率高
• 但是页是物理页，页面共享不易实现
• 段是逻辑段，方便实现分段共享
• 但是外碎片的存在降低内存使用效率，且整理消除外碎片加大系统开销

5.7.2 基本原理

把分页和分段两者结合起来

• 内存划分成大小相等的页框
• 用户的地址空间被程序员划分成许多段，每个段一次划分成许多固定大小的页，页的长度等于内存中页框的大小

5.7.3 数据结构

• 系统设一张位示图，记录内存各帧占用与否
• 内存为一个含有多分段的进程建立段表，记录各个分段对应段内页表的地址和长度
• 一个分段有一个段内页表，记录该段划分为多少也，每页分配的帧号是多少

段表和段内页表：

5.7.4 地址形式

系统的硬件支持是在处理及内部设有段表控制寄存器及地址生成逻辑

• 程序中的逻辑地址仍是二维地址 <段号，偏移量>
• 每段装入时分页，地址部分被当作三维地址来处理 <段号，页号，页内偏移>

5.7.5 地址重定位

5.7.6 地址保护

5.7.7 段页式地址字结构的计算

5.8 多级页表相关计算

5.8.1 例题

题一：

题二：

5.8.2 多级页表的地址重定位

处理及中要设有外部页表寄存器，存放当前进程的外部页表首地址。系统根据指令给出逻辑地址

• 用逻辑地址中的外层页号查找外层页表，得到内层页表首地址
• 用逻辑地址中的内层页号查找内层页表，得到数据帧号
• 将数据帧的首地址加上偏移地址得到物理地址

5.9 快表

• 存储在高速缓存
• 内容为页表中最近使用的页表项

5.9.1 地址变换过程

• 硬件逻辑中，将逻辑地址中的页号送入高速缓存，与快表中的所有页号进行比较，若找到相匹配的页号，读出该页面对应的帧号，与偏移量合成一个物理地址
• 若在快表中没有找到，系统需要再在访问内存中的页表，在页表中找到该页的帧号，与偏移量共同合成访问内存的物理地址
• 同时系统自动更新快表。快表中总是存放那些刚刚访问过的页表项

设一次快存访问时间为 t1，一次内存访问时间为 t2

• 如果查询快表能找到所用页，我们称作命中，此时的有效访存时间 t 为
  • t = t1 + t2
• 如果查询快表没有找到所用页，称作没有命中，此时有效访存时间 t 将是
  • t = t1 + 2t2

设查询快表的命中率为 p，则平均内存有效访问时间 T 大约是

• T = p * (t1 + t2) + (1 - p) * (t1 + 2t2)

六、虚拟存储管理篇

6.1 主存扩充技术

• 覆盖技术
• 交换技术
  • 交换整个作业
  • 交换整个进程
  • 交换页面/段面
• 虚拟存储技术
  • 交换页面/段面

6.1.1 实质

目的：将小的实存储器扩充为大的虚存储器

实质：将磁盘空间虚拟成内存使用

结果：将进程的一部分装入内存即可运行

6.1.2 局部性原理

• 最近访问过的程序代码和数据结构很快又被访问（时间局部性）
• 某存储单元被使用之后，其相邻的存储单元也很快被使用（空间局部性）

程序在执行过程中的一个较短时间内，所执行的指令地址或操作数地址分别局限于一定的存储区域中

实际上，在许多情况下不需要将整个程序放到内存，如：

• 处理异常错误条件的代码
• 主程序先后调用的多个子进程

所以可知，虚拟内存也是可行的

虚拟内存：

允许进程的执行不必完全在内存中，程序可比物理内存大

• 程序不再受现有的物理内存空间限制
• 更多程序可同时执行，CPU 利用率相应增加

6.1.3 覆盖技术

程序在运行过程中，在不同时刻把同一存储区分配给不同程序段或数据段，实现存储区共享的一种内存分配技术

覆盖技术通常与单一连续区分配、固定多分区分配和动态多分区分配等存储管理技术配合使用

每一个用户程序被分成若干段：

• 非覆盖段：是经常要用的基本部分，作为常驻段
• 可覆盖段：不经常使用，可以让他们在需要时临时装入，不同时使用的段可组为一组可覆盖段

6.1.4 交换技术

将内存中某进程暂时不用的程序和数据写入外存交换区中，腾出来的内存空间供其他进程使用。待需要时或内存有空闲空间时，再将它从外存交换区装入内存

磁盘交换区时一个数据的暂存处。系统可根据内存的拥挤程度将信息调往交换区或者从交换区调入

于是磁盘就被分成文件区和交换区

• 二者存储方式不同：文件区信息以文件形式存放，为了提高空间利用率，一般采取离散存储方式，交换区信息按字节流动方式存放，多采用连续存储方式
• 二者访问速度不同：为了提高检索效率一般通过建立目录，对文件实现访问，也就是间接地址访问，而交换区空间较小，可按外存地址直接访问，因此访问速度快
• 二者存储时间不同：文件区适合于长久的数据存储，而交换区作为临时数据的存放处，只存放短期的数据

交换方式：

• 交换整个作业——用于单道系统（单道模拟多道）
• 交换整个进程——用于连续分区存储管理（进程挂起、激活，中级调度）
• 交换页面/段面——用于分页、分段存储管理技术（虚拟存储技术）

6.1.5 虚拟存储技术

一个进程运行时，可不必将其全部装载到内存区中，只需把当前运行的部分程序和可能访问的数据块装入内存即可，随着进程运行的不断推进，其余部分程序和数据可随时装入，这样做可实现小内存运行大程序的设想

采用虚拟存储技术以后，从逻辑上说，系统拥有一个容量很大的存储器，这就是常说的虚拟存储器

虚拟存储器的特性：

• 离散性
• 多次性
• 对换性
• 虚拟性

实现技术：

• 基于分页的虚拟存储：页面换入换出
• 基于分段的虚拟存储：段面换入换出
• 基于段页的虚拟存储：页面换入换出

6.2 请求分页存储管理基本原理

6.2.1 要点

• 内存分成大小相等的帧
• 进程按照帧的大小被分成若干页
• 进程仅装入部分页面即开始执行
• 在执行过程中访问的页若已存在，进行动态的地址重定位，执行指令
• 在执行过程中访问的页未装入内存时，产生缺页中断，进程阻塞，等待从磁盘动态装入页面
• 缺页装入以后，进程转入就绪，可参与调度继续执行
• 内存无空闲可用帧时，暂时不用的页面可换出到交换区
• 通过页面的换入换出实现小内存运行大进程

6.2.2 页的位置

• 内存
• 外存
• 交换区

6.2.3 数据结构

页表：

• 为一个进程设置一张页表，记录该进程分了多少页、每一页是否已装入内存、内/外存地址、访问权限等相关管理信息
• 与基本分页存储管理的页表相比，扩充页表的内容，增加驻留标志位和页面辅存的地址等信息

6.2.4 地址重定位

当一个进程调度时，系统将其页表首地址装入 CPU 中的页表控制寄存器。运行中用相对地址的高端部分作为页号区检索页表，看该页是否已在内存，如果存在则就绪，否则发生缺页中断，进程转入阻塞等待系统将所缺的页装入之后重新执行

6.3 缺页中断与缺页中断处理过程

缺页中断是指令执行过程中产生的中断，而非在一条指令执行完成后产生的

6.3.1 缺页中断的断点压入

• 当 CPU 执行指令希望访问一个不在内存的页面时，将产生缺页中断，系统开始运行中断处理程序
• 此时指令计数器的值尚未来得及增加就被压入堆栈，因此压入的断电必然是本次被中断的地址，而非下一条指令的地址

6.3.2 缺页中断处理过程

• 保留上下文
• 判断内存是否有空闲可用帧，有则获取一个帧号 No，转第四点，启动 I/O 过程，若无继续第三点
• 腾出一个空闲帧
  • 调用置换算法，选择一个淘汰页 PTj
  • PTj = 0 // 驻留位置0
  • No = PTj(F) // 取该页帧号
  • 若该页曾被修改过
    • 请求外存交换区上的一个空闲区 B
    • PTj(D) = B // 记录外存地址
    • 启动 I/O 管理程序，将该页写到外存上
  • 按页表中提供的缺页外存位置启动 I/O，将缺页装入空闲帧 No
  • 修改页表中该页的驻留位和内存地址 PTi(S) = 1; PT(i) = No
  • 结束

6.4 页面分配算法与分配策略

• 实践证明，如果一个进程在内存中分配的帧数比较少，尽管有局部性原理，缺页率仍然相对较高
• 给特定进程分配的内存空间超过一定的大小后，由于局部性原理，该进程的缺页率没有明显的变化
• 分配给一个进程的帧数越多，在任何时候驻留在内存中的进程数就越少，从而降低了操作系统至少找到一个就绪进程的可能性，降低了 CPU 的利用率

6.4.1 给特定进程分配合理的内存帧数

目前流行的支持多字节指令的计算机系统中，一条指令需要对源操作数和目的操作数进行处理，那么一个进程的运行空间最好不小于 6 个页面

请求分页系统中的页面分配应当以减少缺页率位目标

需要考虑的因素：

• 指令格式
• 寻址方向
• 程序长度
• 页面走向
• 程序的工作集尺寸
• 多道并发度

6.4.2 平均分配法

系统的可用空间平均分配给所有进程，让他们都占有相等数量的帧

• 这样分配对短作业来说时很有利的
• 对较大进程，缺页率必然居高不下

6.4.3 优先权分配法

考虑进程的优先运行权，给高优先的进程分配较多的帧，使它的缺页率相对少一些

这里我们可把优先权理解为高响应比、高优先级、最短剩余时间优先等

6.4.4 比例分配法

这种分配方法比较公平，小进程分配小空间，大进程分配大空间

• 当可用空间为 M 帧，系统当前的进程数为 n，每个进程的页面数为 si，那么按比例分配发，应当分配给进程 i 的页数 pi 为：

6.4.5 页面分配策略

• 固定分配策略：为一个进程在内存中分配固定数目的页框用于执行时使用
• 可变分配策略：允许分配给一个进程的帧的数目在该进程的生命周期中不断地法神变化，缺页率高可增加分配地帧，缺页率很低时可适当减少分配的帧

6.5 页面置换算法概述

6.5.1 页面置换

是指在内存空间没有空闲可用真而又要装入新页时，必须按某种算法将内存中的某页置换为一个新页

• 换出的：从内存到外存（磁盘交换区或文件区）
• 换入的：从外存（磁盘交换区或文件区）换到内存

6.5.2 页面置换策略

• 局部置换策略：尽在产生这次缺页的进程的驻留页中选择并置换
• 全局置换策略：把内存中所有未被锁定的页都作为置换的候选页，不管他们属于哪一个进程

	局部置换	全局置换
固定分配	- 分配给一个进程的页框数是固定的 - 从分配给该进程的页框中选择被置换的页	无此方案
可变分配	- 分配给一个进程的页框数可以变化 - 从分配给该进程页框中选择被置换的页	- 从内存中所有页框中学则被置换的页 - 这导致进程驻留集大小不断变化

6.5.3 页面置换要点

• 策略前提：固定分配 + 局部置换
• 发生背景：发生缺页中断 + 内存无空闲可用帧
• 完成功能：从进程自己的驻留页中选择一页作为淘汰对象换出，然后换入所缺页
• 选择策略：页面置换算法

6.5.4 常见的页面置换算法

• OPT
• FIFO
• LRU
• CLOCK
• 改进的 CLOCK

6.5.5 OPT 最佳置换算法

该算法选择以后不再使用、或者要隔最长时间才能使用的页面予以淘汰

OPT 算法尽量避免刚调出去又要立即调入，是一种理想化了的页面置换算法

• OPT 算法在实际系统中不易实现
• OPT 算法用于衡量实际页面置换算法的性能

6.5.6 FIFO 先进先出页面置换算法

• 系统选择驻留在内存中时间最长的页面作为被淘汰的对象
• 这种算法的出发点是局部性原理，但没有考虑现状如内存者有可能是主程序常驻模块

• 最先装入的不一定是以后不用的
• FIFO 算法容易理解和实现，性能并不总是很好

6.5.7 LRU 最近最久未用算法

• 系统选择内存中上次使用距当前最远的页予以淘汰
• 根据程序局部性原理，在较长时间里未被使用的页面，可能不会马上使用到
• 实现时通常使用栈来组织各个驻留页，通过调整、维护栈来记录各驻留页被访问的先后顺序

• 优点：缺页中断率接近 OPT
• 缺点：几乎每一次页面访问都要调整栈，系统开销大

6.5.8 Clock 算法

• 这是一个建立在循环检查基础上的 LRU 近似算法，试图以较小的开销获得接近 LRU 的性能
• 该算法中将驻留页组织成一个循环对，并设一个循环移动指针

步骤：

• 初始时，该指针指向循环队的头部
• 指针顺序搜索各页面，若页面访问位为 1，则将之改为 0
• 找到的第一个访问位为 0 的页面，淘汰，新换入的页面访问位置为 1

分析：

• Clock 是近似的 LRU，理论上的缺页中断率肯定高于 LRU，但实际系统应用起来系统开销少，效果要由于 LRU

问题：

• 驻留页有被修改过的，也有未被修改过的，这两种页面被换出时的操作开销大为不同

6.5.9 改进的 Clock 算法

除了访问位 A 之外为每个帧增设一个关联的修改位，记作 M

• 如果 M = 1 表示该帧中的页面被修改了，淘汰他意味着必须将之写到外存
• 如果 M = 0 表示该帧中的页面没有被修改，淘汰他意味着什么都不用做

过程：

• 从指针当前位置开始，循环扫描候选帧，遇到的第一个 A = 0 且 M = 0 的帧，将该帧中的页面置换后返回
• 若循环一周没有找到可置换的帧，则继续循环扫描第二周，遇到的第一个 A = 0 且 M = 1 的帧，将该帧中的页面置换后返回。在这个过程中，没跳过一个镇就将他的访问位 A 设置为 0
• 若第二圈仍没有找到可置换的帧，则循环扫描第三圈，操作同第一圈
• 若第三圈没有找到可置换的帧，则循环扫描第四圈，操作同第二圈，必将找到一个可置换的帧

6.6 关于页面调入的进一步讨论

6.6.1 页面什么时候调入？

在页面动态装入过程中有两个页面调入策略

• 随用随调：法僧缺页中断时，缺哪页便调入哪页
• 预调页：使用第一页，发生缺页中断，在调入第一页时连同第二、三。。。页一起调入
  • 优点：
    • 一次读多个连续的页面，可以减少磁头移动的时间，对系统效率提高有很大的好处
    • 当发现缺页已在内存时，当前进程不必让出控制权，仅仅将缺页转移到用户区，修改页表后就可继续运行

6.6.2 页面从哪儿调入？

• 从磁盘交换区调入
• 从磁盘文件区调入
• 从磁盘缓冲区调入

6.6.3 页面调入需要多长时间？

• 从磁盘交换区调入
  • 调入时间主要是读磁盘扇区的时间，由磁盘寻道时间，盘片旋转延迟时间和数据传送时间三部分组成
  • 通常调入时间约为数百微秒至数十毫秒
• 从磁盘文件区调入
  • 对文件区的访问需要检索文件目录，找到文件以外的外存地址后再都磁盘扇区
  • 其调入时间将数倍于从磁盘交换区中调入缺页的耗时，几十甚至几百毫秒
• 从磁盘缓冲区调入
  • 系统允许采用提前读的访问策略时，用户程序运行中产生的缺页有可能已经驻留在内存的磁盘缓冲区内
  • 从该缓冲区内调入缺页的时间大体为数百纳秒

6.7 页面访问时间

6.7.1 进程执行过程中要访问的页面有几种情况？

6.7.2 访问页面需要多长时间？

• 在基本分页存储管理中，所有页面已在内存里
  • 进行地址重定位
  • 设 t1 为访问一次快存的时间，t2 为访问一次内存的时间，p 是访问快表命中率，则有效访存时间为
    • t = (1 - p) * (t1 + 2t2) + p * (t1 + t2)
• 在请求分页存储管理中，页面分两种情况计算
  • 在请求分页存储管理中，不发生缺页时的这个访存时间 t 称为一个内存周期为 ma
    • ma = t = (1 - p) * (t1 + 2t2) + p * (t1 + t2)
  • 假定系统的一个内存周期为 ma，调入缺页的时间为 la，缺页率为 p，那么
    • T = (1 - p) * ma + p * (la + ma)
    • T = ma - p * ma + p * la + p * ma
    • T = ma + pa * la

6.8 驻留集，工作集与抖动的预防

6.8.1 驻留集

• 进程已装入内存的页面的集合——与系统采用的页面装入和页面置换算法有关

驻留集尺寸：

• 进程驻留在内存中的页面数量——与系统采用的页面分配策略有关

6.8.2 工作集

• 在某一段时间间隔内进程运行所需访问的页面的集合
• 一个进程的工作集 W(i, t) 表示在时间 i - t 到 i 之间进程引用的一串页面，工作集的尺寸记作 s(i, t)，指的是 W(i, t) 中的页面数
• 在进程执行期间可以很容易的确定该进程对存储空间的需求，也就是它的工作集尺寸
• 操作系统可以用这种方法决定给谁分配更多的帧，以及哪个进程应当让出一些帧
• 工作集可用于指导驻留集的大小

策略：

• 监视每个进程的工作集
• 周期性地从一个进程地驻留集中移去那些不在它的工作集中的页
• 只有当一个进程的工作集在内存中时，才可以执行

优点：

• 通过工作集调整驻留集，可降低缺页率
• 通过工作集尺寸调整驻留集尺寸，可提高内存利用率
• 优先调度工作集包含于驻留集的进程，提高 CPU 利用率

缺点：

• 根据过去预测将来的不准确性
• 为每个进程真实的测量工作集是不实际的
• t 的最优值是未知的，并且它在任何 情况下都会变化

6.8.3 抖动

又称颠簸，指刚调出去的页需要马上被调回，刚调回不久又要被调出。频繁调入调出，使系统的大部分时间都花费在内存和外存之间的来回折腾上

抖动主要表现为磁盘 I/O 极度繁忙，而处理及大量时间空闲，CPU 有效利用率降低

预防措施：

• 在处理机调度中引入工作集策略
• 采用局部置换策略防止抖动扩散
• 挂起部分进程
• L = S 准则（L 是产生缺页的平均时间，S 是系统处理缺页的平均时间，理论证明，当 L = S 时处理及的利用率最高，在实际系统中很难实现）

6.9 请求分段与请求段页式存储管理

6.9.1 请求分段存储管理的基本原理

• 进程按照逻辑结构分段，每一段装入内存一块连续存储区，各段离散存储
• 每个进程装入部分段面，即可以开始运行
• 运行过程中，发生缺段，进程阻塞，通过缺段中断动态调入所缺段，进程转入就绪可参与调度继续之心

6.9.2 请求分段存储管理的数据结构

• MAT 表
• 空闲分区表
• 段表：为了是实现段的动态管理，为每个进程设置一个段表，并在段表中设置一些 控制位 记录该段的控制信息

6.9.3 请求分段存储管理的地址重定位

6.9.4 缺段中断机制

缺段中断也是指令执行过程中产生的中断，进程执行一条产生缺段中断时，压入堆栈的断电是当前指令的地址。当缺段被装入内存后，该段变成了 实段，进程再次恢复运行时，CPU 将重新执行这条指令

6.9.5 缺段中断处理程序

当第 i 段时一个缺段，则缺段中断处理过程为：

• 阻塞进程
• Length = STi（长度）
• 检索内存分配表，若存在 一个独立的内存块长度 > Length，则：
  • 将该内存块分配给进程
  • 首地址计入 B0，转第六点
• 若 内存可用空间总和 < Length，则：
  • 调用某种置换算法，选择一个内存中的段
  • 若该段被修改过，则将它写回外存
  • 修改内存分配表、段表等数据结构
  • 转第三步
• 内存各进程浮动，拼接出一个足够大的内存空间，将该内存块分配给进程，首地址 B0
• 从外存读入缺段，存入 B0
• STi(B) = B0，STi(S) = 1
• 修改内存分配表
• 唤醒进程
• 结束

6.9.6 请求段页式存储管理基本原理

• 请求分段加请求分页，把段划分为若干个页面进行离散存储，系统将一个段的当前页调入内存，其余的仍驻留在外存上，随时需要随时通过缺页中断装入

硬件支持：处理机中设有段表控制寄存器参与地址映射，存放的内容时段表起始地址和段表长度。在地址结构方面，页面长度和分段长度由系统对控制寄存器的安排来决定

软件支持：在请求段页式管理系统中，缺页置换算法是必须的，而且与纯粹请求分页管理机制中采用的算法相同

6.9.7 请求段页式地址重定位

6.9.8 请求段页式存储管理的优缺点

优点：具有虚拟存储器的功能，并保持了段页式管理的优点，既体现段的独立性，又纳入了页的离散分配，使系统更加灵活

缺点：增加了硬件的成本，系统复杂性提高，而且段表和页表的存储与检索问题突出，对处理机的运行速度影响较大

6.10 与地址有关的计算

6.10.1 题一

6.10.2 题二

6.10.3 题三

6.10.4 题四

• 页内偏移 10 位，页号 3 位，故空一填 13
• 32块物理地址，需 5 位表示帧号，帧内偏移还是 10 位，故空二填 15

6.10.5 题五

• 一
• 二

6.10.6 题六

页表：

0	1	2	3
2	3	1	6

• 1011
  • 页号：1011 / 1024 = 0
  • 偏移：1011 % 1024 = 1011
  • 按页号查找帧，并计算出物理地址
  • 2 * 1024 + 1011 = 3059
• 2148
  • 页号：2148 / 1024 = 2
  • 偏移：2148 % 1024 = 100
  • 按页号查找帧，计算出物理地址
  • 1 * 1024 + 100 = 1240
• 5012
  • 页号：5012 / 1024 = 4
  • 不存在 4 号页

6.10.7 题七

6.10.8 题八

• 1052
  • 页号：1052 / 1024 = 1
  • 偏移：1052 % 1024 = 28
  • 按页号找到对应帧，并计算出物理地址
  • 7 * 1024 + 28

七、设备管理篇

7.1 设备管理概述

在计算机系统中，用来担负数据输入输出的部件称作外部设备，它们是计算机与外部世界进行信息沟通的桥梁

7.1.1 分类

• I/O 设备
  • 人可读
  • 机器可读
  • 通信
• 外存储设备
  • 数据速率
  • 应用
  • 控制的复杂性
  • 传送单位
  • 数据表示
  • 错误条件

按数据传输单位分

按共享特性分：

• 独享设备
  • 输入输出速度比较低，在使用的某个环节中需要人工进行干预
  • 在多进程并发运行的系统中，独享设备一般由一个作业独占，知道改作业使用完为止
  • 常见的独享设备有打印机、绘图仪、终端机，以及早期计算机上使用的卡片输入输出机、穿孔机和广电阅读机等
  • 从工作方式上说，大部分独享设备的输入输出操作都是按字符的方式进行传送的，因此这种设备又称为字符设备
• 共享设备
  • 操作速度较快，允许多个作业以共享方式使用
  • 共享设备可以供多个进程共同进行存入和读出，一次传输若干数据，也被称作块设备
  • 磁盘是最常见的共享设备

7.1.2 设备管理目标

• 方便用户使用
• 提高设备利用率
• 通过管理调度提高 I/O 效率
• 通过软件方法扩充设备的功能

7.1.3 设备管理功能

• 设备分配、回收
• 设备无关性（设备独立性）
• 缓冲区的设置和管理
• 设备的驱动与调度
• 设备的虚拟扩充

7.1.4 设备管理系统的构成

• 逻辑 I/O 层
• 设备 I/O 层
• 设备调度与驱动控制器

分别指：一般 I/O 设备系统、网络系统、文件系统

7.1.5 逻辑外部设备

逻辑 I/O 层

• 负责设备的分配和回收，通过设置和维护数据结构，对设备数据进行登记和管理
• 负责对用户的访问需求进行合法性检查，若此次访问不合法将拒绝访问
• 负责随时接受下层的处理结果，整理后反馈给用户，处理结果中包含成功或失败信息

物理 I/O 层

• 管理内存中的设备缓冲区，负责缓冲区的分配和回收
• 实现数据的装入与提取，比如从上层软件送来的一行数据填入缓冲区或者从缓冲区取出一行数据送给用户。同时要实现诸多用户对缓冲区访问的并发控制
• 根据用户请求产生一个具体的 I/O 任务快 IOB，挂到相关设备的任务队列上，并启动下层软件
  • IOB块
    • 是一种动态数据结构
    • 每个 IOB 用于描述一项输入输出任务
    • 当系统收到一个 I/O 请求时就构造一个 IOB，并按 IOB 的信息进行传输控制

设备调度与驱动层

• 设备调度，如磁盘 I/O 调度
• 构造通道程序
• 启动 I/O 设备完成输入输出
• 对于设备 I/O 的情况进行收集并交给上层软件

7.2 设备的分配

7.2.1 设备分配对象

• 共享设备是允许多用户穿插访问的设备，此类设备不能分给某个用户独占
• 设备分配时用户对独享设备的使用方式，用户分得一台共享设备后可以自由的使用，直到使用完毕将设备释放为止

7.2.2 设备分配

• 当用户请求进行 I/O 操作时，不但要分配设备，还要分配有关的数据传输通路，也就是分配通道和控制器

7.2.3 系统设备分配表 SDT

• 系统设置一张 SDT，登记系统拥有的所有设备类型，一行等级一类设备的管理信息

7.2.4 设备控制表 DCT

• 系统设置一张 DCT，登记所有外部设备，一行登记一台设备的管理信息

7.2.5 控制器控制表 CCT

7.2.6 通道控制器 CHT

7.2.7 逻辑设备映射表 LUT

上述的分配结果记入每个进程的 PCB，称作 LUT

• 逻辑设备名
• 物理设备标识

7.2.8 设备分配过程

• 根据用户提出的逻辑设备名称，从 SDT 中找到相应类型的逻辑设备，并获取该类型设备的可用数量 N，据此进行安全检测（银行家算法），如果检验不通过，则将进程阻塞
• 从 SDT 中取出 DCT，找到一台可用的外部设备，将设备分配给进程，在该进程的 PCB 中建立一个设备映射表 LUT，将用户的逻辑设备名称和对应的物理设备标识对应起来

7.2.9 设备无关性

又称设备独立性，指的是应用程序所涉及的逻辑设备与系统中具体使用的物理设备是互相无关的

用户写程序时使用逻辑设备名，执行时由系统分配物理设备

优点：

• 设备分配的灵活性提高，进程使用逻辑设备名提出请求，系统可以从当前空闲的物理设备中任选一台分给用户
• 易于实现 I/O 重定向，系统可以在不更改应用程序代码的前提下，让程序中 I/O 命令所涉及的逻辑设备名映射到另外的物理设备上

7.3 缓冲区的设置与管理

7.3.1 什么是缓冲区

是位于内存中的一块临时存储区，作为内存呢和外部设备之间数据传送的桥梁

7.3.2 设置缓冲区的目的

• 改善中央处理器与外围设备之间速度不匹配的矛盾
• 协调逻辑记录大小与物理记录大小不一致
• 提高 CPU 和 I/O 设备的并行性

特点：

• 减少设备驱动次数
• 可以缓解 I/O 操作对缺页置换策略的干扰
• 缓解 CPU 与外部设备速度不匹配的矛盾，使数据处理的速度提高

过程

• 进程执行写操纵输出数据时，向系统申请一个缓冲区，若为顺序写请求，则不断把数据填到缓冲区，知道被装满
• 此后进程继续它的计算，系统将缓冲区内容 I/O 设备上
• 在输出数据时，只有在系统还来不及腾空缓冲而进程又要写数据时，它才需要等待
• 大部分时间，进程的计算和输出是可以并行的

7.3.4 设置缓冲区的方法

单缓冲：

双缓冲：

多缓冲：

7.3.5 缓冲池

当一个进程要写数据时，向缓冲池申请一个缓冲块

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

四个系统进程

• 收容输入
• 提取输入
• 收容输出
• 提取输出

7.4 磁盘读写速度分析

7.4.1 性能参数

**寻道时间 ts**：将磁头臂移到指定刺刀所需要的时间

**旋转延迟时间 tr**：将磁盘的待访问地址区域旋转到读/写磁头可访问的位置所需要的时间

**传输时间 ti**：读或写操作的数据传输所需的时间

T = t s + t r + t i

7.5 磁盘调度算法

衡量算法的性能：

磁盘调度程序的目标是指定一种访问策略，使磁头臂移动较少的距离就可完成磁盘访问

对于 r 次磁盘访问请求 q1，q2，...，qr 应用某种磁盘调度算法得到一个依次满足各次请求的顺序，期间磁臂总共跨越的道数为 n

平均寻道长度 = n / r

7.5.1 先来先服务 FCFS

按磁盘访问请求到来的先后顺序进行服务

优点：比较公平，实现简单

缺点：不考虑调用效率

7.5.2 最短寻道优先 SSTF

从当前磁头位置选择最短寻道时间的请求，即选择与当前磁头位置最近的待处理请求

优点：较 FCFS 提高了性能

缺点：有可能出现 粘着 现象，系统比较繁忙时，可能出现饥饿现象，且磁臂转向也需要时间开销

7.5.3 扫描算法 SCAN

又成为电梯调度，沿磁臂当前移动方向由近及远一次满足此怕能访问请求，至当前方向再无请求时磁盘转向，继续由近及远一次满足访问请求

优点：较 SSTF 大大减少了磁臂转向次数，尽管平均寻道时间长度增大，但在实际系统中效率较好

缺点：系统比较繁忙时，仍可能出现饥饿现象

7.5.4 循环扫描算法 CSCAN

在一个移动方向上，随着移动不断处理请求，反向时空档返回，知道最远请求，然后转向移动时再处理请求

优点：较之 SCAN 算法减少了现象的出现

缺点：空档返回增加了平均寻道时间

7.6 通道控制下的 I/O

计算机系统中的 I/O 控制是与硬件的配置紧密相关的

• 程序查询控制方式
• 中断控制方式
• DMA 控制方式
• 通道控制方式

7.6.1 中断类别

自愿性中断：

• 访管中断
• 人为设置中断

非自愿性中断：

• I/O 中断
• 硬件故障置中断
• 程序出错中断
• 外部事件中断

7.6.2 中断处理程序的处理过程

• 关中断
• 保护进程上下文
  • 被中断的程序，除了 PSW 和 PC 中的信息已被硬件机制压栈，其余寄存器中尚有一部分残留数据
  • 而中断处理程序运行时可能要用到其中一部分寄存器，因此需要将中断程序中涉及到的寄存器内容保存起来，通常也压入系统栈中
• 设备中断处理（不同的设备有不同的设备中断处理程序）
  • 在处理期间，处理机要检查相关设备控制器的状态，判断本次传输是否正常完成。
  • 若正常完成，可将设备传送来的数据转交到用户区，并唤醒等待该数据的进程，或者将下一批要传送出去的数据传送到设备控制器中，重新启动设备，若为非正常完成，可根据发生的情况进行异常处理
• 恢复被中断的程序
  • 首先将保存在栈中的寄存器内容弹出来，置入处理机的相关寄存器中。然后从栈中弹出 PSW 和 PC 的值，置入处理机中。这就意味着，被中断的程序又恢复了运行
• 开中断

7.6.3 通道

I/O 处理机，处理 I/O 过程的指令，通常被置于内存的约定地址中，作为实施数据传送控制的依据，通道程序的编制主要依赖 SDT、DCT、IOB 中的信息

7.7 虚拟设备

操作系统的设备管理模块通过软件方法扩充设备功能，获得虚拟设备

包括：

• 将一台设备虚拟成多台设备
• 将低速设备虚拟成快速设备
• 将不能共享的设备虚拟成共享设备

7.7.1 Spooling 技术

Spooling 是 联机外设并行访问 (Simultaneous Peripheral Operations On Line) 的缩写，是指将磁盘空间虚拟成 I/O 设备的一种技术

实质：

利用高速共享设备（通常是磁鼓或者磁盘）将低速的独享设备模拟为高速的共享设备，这样从逻辑上将，计算机系统为每一个用户都配备了一台高速独享设备

• 是操作系统用于管理低速外部设备的一种实用技术
• 是将独享设备模拟成共享设备的一种技术

要点：

• 外存上设输入井、输出井
• 内存设输入缓冲区、输出缓冲区
• 系统设与输入程序和缓输出程序
• 对于输入输出井的使用，系统设四个系统进程
  • 收容输入：负责启动输入设备，将数据从输入设备都进来，在文件管理系统的支持下，把数据存放到外存的输入井上
  • 提取输入：从输入井上提取数据，送入内存的用户区，供进程使用
  • 收容输出：将用户进程需要输出的数据从其用户区取出来，送到输出井
  • 提取输出：到外存上取出输出井上的数据，输出到设备上

输入过程

输出过程

八、文件管理篇

8.1 文件与文件管理概述

8.1.1 什么是文件

• 文件是在逻辑上具有完整意义的一组相关信息的集合
• 它可以使一组相关的字符流集合，也可以是一组相关的记录集合
• 通常被保存在外存储器上

8.1.2 文件的内部形式

8.1.3 文件管理系统 FMS

• FMS 是操作系统的一个组成部分
• 负责实现文件管理有关功能的管理模块
• 管理对象：文件、目录、文件存储空间、用户

8.1.4 文件管理系统的目标

• 方便用户
• 提高磁盘空间利用率
• 文件操作便捷且存取效率高
• 实现逻辑文件与物理文件的组织和转换

8.1.5 文件管理系统的管理功能

• 按名存取
• 文件组织（逻辑文件与物理文件的转换）
• 存储空间管理
• 文件共享和保护
• 文件操作

8.1.6 公认一个好的 FMS 应具有以下特点

• 使用的方便性：按名存取的实现，使文件的物理结构和存放的物理位置对于用户都成了透明的
• 数据的安全性：提供有效的保护措施，以保证文件信息的安全
• 接口的统一性：用户可以使用统一的广义指令或系统调用来存取各种介质上的文件，这样做简单、只管，而且摆脱了对存储介质特性的依赖以及使用 I/O 指令所作的繁琐处理
  • 操作员接口，如各种菜单命令
  • 程序员接口，如 fopen() 等文件操作系统调用

8.2 文件、目录、文件目录、目录文件

目录与文件：

• 目录也是文件
• 目录是一种特殊的文件
• 目录的内容是另一些文件的管理信息

目录文件与文件目录：

• 目录是文件的一种，叫目录文件
• 文件目录是目录文件中记录的一条信息

8.2.1 DOS 目录文件

8.2.1 Unix 目录文件

为什么要引入索引节点：

• 在多级目录结构中，目录也是以文件形式存储在磁盘上
• 如果目录项内容比较多，则目录文件要占用大量的盘块
• 查找文件要先查找它所在的目录
• 目录文件太大，查找效率就会比较低

8.3 文件的逻辑结构

指呈现在用户面前的文件结构，是文件逻辑上的组织形式

• 流式结构
• 记录式结构

8.3.1 流式文件

是指文件内的数据是一个完整的字符流，不可以进一步细分

例如：

• 源程序文件
• 可执行文件
• 文本文件
• 图片文件
• 音频文件
• .etc

对流式文件，用户常常以长度来指定所需存取的信息，也可以通过插入特殊符号来标识存取的界限

8.3.2 记录式文件

在逻辑上可看成是一组记录的集合，每个记录由彼此相关的若干个数据项组成

例如：

• 统计表文件
• 数据库文件
• .etc

8.4 文件的物理结构

指文件在存储介质上的存储结构，是文件在外存空间上的组织形式

• 顺序结构
• 链式结构
• 索引结构

分类：

• 连续存储结构：文件体在磁盘上占用连续的存储空间
• 非连续存储结构：文件体在磁盘上占用不连续的存储空间
  • 链接存储
    • 显示链接存储
    • 隐式链接存储
  • 索引存储

文件的存取方式

• 文件的顺序存取：按照文件的逻辑地址顺序存取。在记录式文件中，这种操作体现为按照记录的排列顺序来进行存取
• 文件的随机存取：随机存取是指允许用户按照记录编号或者某一数据项的值随机存取任意记录

8.4.1 顺序存储结构

• 文件信息占用一组连续的盘块，文件在外存上顺序存放
• 文件目录中登记起始盘块和所占块数

顺序存储的文件称为连续文件，这种文件不仅在逻辑上是连续的，在外存上存放的空间也是连续的

优点：

• 管理简单
• 存取速度快
• 既适合顺序存取，也适合随机存取

缺点：

• 外存空间利用率低
• 必须预先知道文件的长度
• 不便于文件的扩展

8.4.2 隐式链式存储结构

每个文件占用不连续的盘块，文件目录只登记起始盘块和末盘块号，其他盘块好均由链接指针记录

优点：

• 采用离散分配方式
• 易于文件增长或收缩
• 减少了外存空间出现外碎片的现象

缺点：

• 只能顺序存取
• 该指针本身需占用存储空间
• 链接指针的可靠性是个问题

8.4.3 显式链接存储方式

将用于链接文件各个盘块的指针显示的存放在外存的一张链接表中

该表在整个磁盘仅设置一张，登记了分配给文件的所有盘块的链接关系，故将该表称为文件分配表 FAT

优点：

• 采用离散存储方式
• 易于文件增长或收缩
• 减少了外存空间出现外碎片的现象
• 既可以顺序存取，又可以随机存取

缺点：

• FAT 表占用较大的存储容量
• FAT 表使用时，占用较大内存空间
• FAT 表的读取、维护加大了系统开销

8.4.4 索引存储结构

为每个文件分配一个索引块，在索引块中登记其各个逻辑块与外存物理块的对应关系，并在文件 FCB 中登记该文件索引块的地址

优点：

• 离散存储
• 既适合顺序存取，也方便随机存取
• 索引结构容易实现记录的增删

缺点：

• 索引块实际是存储开销
• 一个索引块能存放的盘快好有限，所以一级索引存储限制了文件的容量

假设一个盘块号用 4 个字节标识，盘块尺寸为 4KB，那么一个索引块可存放多少个文件块块号

4KB / 4B = 1K

8.4.5 二级索引存储结构

将索引表离散存储，即：将索引表本身分为若干个逻辑块，存储在若干物理盘块中，将索引表所占的个盘块记入另一个索引表——索引表的索引表

这种结构就称二级索引结构

一级索引：

多级索引：

8.4.6 多级混合索引结构

它将直接寻址、一级索引、二级索引和三级索引融为一体，规定每个文件的索引节点使用 13 个地址登记项

• 前 10 个登记项直接指出存放文件信息的盘块号，属直接寻址
• 前 11 个登记项指向一级索引块，内含若干一级索引存储块
• 第 12 个登记项和第 13 个登记项分别实现二、三级索引

8.4.7 Unix 中的一个文件

8.5 文件目录的管理与查询

是一种数据结构，由若干目录项组成，每个目录项对应其中一个文件的 FCB 包括：

• 文件的存取控制信息
• 文件的结构信息
• 文件的管理信息

8.5.1 文件目录内容

• 文件存取控制信息：用户名、文件名、文件类型、文件访问权限 .etc
• 文件结构信息：文件的逻辑结构、物理结构、文件位置、长度 .etc
• 文件管理信息：文件的建立日期、被修改的日期、保留日期、记账信息 .etc

8.5.2 文件目录管理的主要目的

• 合理组织目录结构，提高对目录的检索速度
• 允许文件重名
• 实现按名存取
• 允许文件共享以节约外存空间

8.5.3 单级文件目录

每个系统只设置一张文件目录表，集中存放文件存储器上所有文件的 FCB

8.5.4 两级文件目录

• 主文件目录 MFD
• 用户文件目录 UFD

8.5.5 多级文件目录

优点：

• 层次清楚，便于文件分类
• 提高了文件检索速度
• 解决了重名问题
• 便于进行存取权限的控制

8.6 文件存储空间的管理

文件存储空间——磁盘，是系统与多个用户共享的

用户对文件只要求按名存取，不需要关心文件在外存上具体的存放位置、存取如何实现

文件存储空间的管理由文件存储管理模块负责

8.6.1 具体功能

• 数据结构：记录磁盘空间使用情况
• 分配：查找空闲的磁盘空间分配给文件
• 回收：将文件占用的磁盘空间交还给系统

• 盘片：两个盘面
• 磁道：柱面
• 扇区：最小存储单位
• 磁盘块：相邻的扇区
• 簇：相邻的盘块

8.6.2 分配和回收

• 创建文件或者文件动态增长的时候，查找空闲的盘块，分配给文件
• 删除文件内容或者删除整个文件时，将文件所占盘块回收

哪些盘块是空闲可分配的，回收回来的盘块又记录在哪里，FMS 需要建立和为何相应的数据结构来描述磁盘空间使用情况

8.6.3 空闲区表/链

磁盘上连续的空闲盘块组成一个空闲区，系统为磁盘上所有的空闲区建立一张 空闲区表，每个空闲区对应一个表项。若各空闲区使用链，链接起来，称之为 空闲链区

8.6.4 空闲块链

建立一个链表，将文件存储空间中所有空闲块顺序链接在一起，链中每一节点记录一个空闲块的物理块号，同时记录下一空闲块的指针，称为 空闲块链

8.6.5 位示图

系统划出若干字节，为每个文件存储设备建立一张位示图，位示图中的一个位对应文件存储空间的一个物理块，若该位为 1，表示对应块被占用，若该位为 0，表示对应物理块空闲

• k = i * L + j
• i = [k / L]
• j = k % L

8.6.6 成组链接存储方式

以 内存 + 外存 的混合方式设计数据结构，用于记录和管理磁盘上的空闲盘块

• 磁盘文件区中的所有空闲盘块，100 个盘块为一组，被分成若干组
  • 假设文件区上共有 4999 个盘块，则被分成 50 个组，N001N100 为第一组，N101N200 为第二组，以此类推，N4901~N5000 为第50组
• 每一组的最后一个盘块，记录着下一组 100 个空闲盘块的盘块号。这样各组的最后一个盘块就链接成一个链表
• 盘块 N4900 中记录最后一组 99 个盘块的盘块号，剩余的一个表项存放 0，作为空闲盘块链的结束标志
• 分配时内存中设置空闲盘块号栈，将第一组空闲盘块的盘块数和盘块号记入其中，作为当前可供分配的盘块号

分配：从空闲盘块号栈顶开始，依次分配，分配到栈底盘块即一组的最后一个盘块时，将下一组空闲盘块号以及盘块数写入空闲盘块号栈，继续从栈顶分配

回收：回收的盘块号依次入栈，当栈满即一组集满 100 块时，将这一组盘块号写入写一个回收来的盘块，清空空闲盘块号栈，刚刚写入内容的盘块号入栈，作为占地，也就是下一组的第一个盘块

8.7 文件共享、保护与保密

• 共享：指允许不同的用户共同使用同一个文件
• 保护：指防止文件被有意或无意地破坏
• 保密：指防止文件未经授权而被非法窃取

8.7.1 静态共享

多个用户共享同一个物理文件，通过信息文件指针地链接实现。不同用户、不同文件名，但其 FCB 中的物理地址都是相同的，都指向文件存储空间中相同的物理信息

实现方法

• 绕弯路法

  • 当前目录为 program：./AA/f3
  • 当前目录为 AA：./f3
  • 当前目录为 document：http://narpro.top/program/AA/f3

  

• 基于索引结点共享法

• 基于基本目录共享法

• 基于符号链共享法：基于符号链的文件共享是建立一种特殊的链接文件，内容为需要共享的文件的路径和名字，访问该文件时，根据路径找到共享的文件

8.7.2 动态共享

多个进程并发的访问同一文件，这种共享关系只有当用户进程存在时才可能存在，一旦用户进程消亡，其共享消息也就自动消失

• 指系统中不同的用户或同一用户的不同进程并发地访问同一文件
• 多个进程对已打开文件的共享
• 这种共享关系只有当用户进程存在时才可能存在，一旦用户进程消亡，其共享关系也就自动消失

8.7.3 文件保护

• 防止系统故障造成破坏，常采用的措施

  • 定时转储
  • 建立副本
  • 后备系统
  • 磁盘容错技术
    • 一级容错：写后读校验
    • 二级容错：磁盘镜像
    • 三级容错：磁盘双工

• 防止人为因素造成破坏

  • 设置基于目录的存取权限

  • 建立基于文件的存取权限

  • 存取控制矩阵

    

8.7.4 文件保密

• 文件保密是指防止文件未经授权而被非法窃取
• 文件保护只要求文件信息不被破坏，而文件保密则要求文件不仅不被破坏，而且害不能被非法盗用
• 规定文件的使用权限可以实现文件保护，也可以在一定程度上起到文件保密的作用。但是文件使用权限可以由用户设定或修改，因而单靠这一方法不足以保障文件安全

常用保密措施

• 设置口令
• 隐藏文件目录
• 加密与解密技术

8.7.5 系统安全

• 系统级：登录、注册
• 用户级：不同用户级别享有不同权限
• 目录级：使用权限设在目录级上
• 文件级：使用权限设在文件级上