零、绪论

操作系统的基本概念

$\overset{Operating\enspace System}{操作系统}$是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充，其主要作用是管理好这些设备，提高它们的利用率和系统的吞吐量，并为用户和应用程序提供一个简单的接口，便于用户使用。具有

操作系统的主要目标为方便性、有效性、可扩充性和开放性。

其作用有：

  • OS作为用户与计算机硬件系统之间的接口
    • OS处于用户与计算机硬件系统之间，为用户提供方便易用的服务。
    • 分为：用户接口（联机用户接口/交互式命令接口、脱机用户接口/批处理命令接口、图形用户接口）和程序接口（系统调用）
  • OS作为计算机系统资源的管理者
    • 计算机系统资源有处理机、存储器、I/O设备和文件
  • OS实现了对计算机资源的抽象：安装多层系统软件，增强了系统功能，隐藏了对硬件操作的细节
    • 第一层次抽象：在裸机上覆盖一层I/O设备管理软件。
    • 第二层次抽象：在第一层软件上再覆盖文件管理软件。

其主要的特征有：

  • $\overset{Concurrency}{并发}$，最基本
  • $\overset{Sharing}{共享}$
  • $\overset{Virtual}{虚拟}$
  • $\overset{Asynchronism}{异步}$

操作系统的发展过程

发展动力：

  • 不断提高计算机资源的利用率
  • 方便用户
  • 器件的不断更新换代

  • 计算机体系结构的不断发展

  • 无操作系统的计算机系统
    • 人工操作方式：用户直接与硬件进行交互。
      • 缺点：用户独占全机、CPU等待人工操作（资源空闲）。
      • 矛盾：人工操作方式与机器利用率的矛盾、CPU与I/O设备之间速度不匹配的矛盾
    • 单道批处理系统：作业合成一批输入到外存上，监控将作业逐个送入内存并运行。
      • 特征：自动性、顺序性、单道性。
      • 缺点：某些作业来说，CPU必须等待I/O的完成使机器的利用率很低。
  • 多道批处理系统（操作系统出现）：
    • 特征：多道性、无序性、调度性
    • 缺点：平均周转时间长、无交互能力
  • 分时系统：计算机以时间片为单位轮流为各个用户/作业服务，通过终端交互。
    • 特征：多路性、独占性、及时性、交互性
    • 缺点：不能优先处理一些紧急任务
  • 实时系统：及时（或即时）响应外部事件的请求
    • 优点：优先响应一些紧急任务。
  • 新型操作系统：
    • 微机操作系统/个人计算机操作系统
    • 网络操作系统：有机结合网络中的计算机，实现数据传送等功能、网络中各种资源的共享
    • 分布式操作系统：任务处理和控制进行分散/分布的系统
      • 特点：分布性、并行性

操作系统结构

内核

  • 无结构操作系统/整体系统结构：过程的集合
    • 缺点：系统的结构关系不清晰，难于修改；循环调用，系统的可靠性降低
  • 模块化结构OS：按功能精心地划分为若干个具有一定独立性和大小的模块
    • 优点：正确性、可理解性和可维护性、可适应性、加速开发过程。
    • 缺点：接口规定很难满足实际需求、各模块的设计无序
  • 分层式结构OS：分层组织模块开发
    • 优点：易保证系统的正确性、易扩充和易维护性
    • 缺点：效率降低
  • 微内核OS：最核心功能作为内核
  • 宏内核OS

外核

提供对硬件资源的应用程序级别的管理。每个极小的内核为应用程序导出了相应硬件资源的底层次接口。实现资源保护与管理的分离。

系统引导

  • BIOS法
    • BOIS自检、加载引导扇区
    • MBR引导、启动硬盘
    • 引导分区
    • 操作系统初始化
  • UEFI法

虚拟化

一台物理机器虚拟化为多台独立运行一个操作系统的虚拟机器。

本质：

  • 分区：在单一物理服务器上同时运行多个虚拟机
  • 隔离：在同一服务器上的虚拟机之间相互隔离
  • 封装：整个虚拟机都保存在文件中，而且可以通过移动和复制这些文件的方式来移动和复制该虚拟机
  • 相对于硬件独立：无需修改即可在任何服务器上运行虚拟机

分为：

  • 寄居虚拟化
    • 简单、易于实现
    • 依赖宿主，开销大
  • 裸金属虚拟化
    • 不依赖宿主、性能好
    • 开发难度大

程序运行环境

内核态与用户态

CPU有两种状态：

  • 内核态/核心态/管态：运行内核程序，执行特权指令与非特权指令
  • 用户态/目态：运行应用程序，只能执行非特权指令

通过$\overset{PSW}{程序状态字寄存器}$区分：

  • 切换至用户态：执行特权指令，修改PSW的标志位为“用户态”，操作系统主动让出CPU使用权
  • 切换至内核态：
    • 系统调用：申请操作系统资源，主动切换到内核态；
    • 异常：发生了一些没有预知的异常，切换到处理此异常的内核相关进程；
    • 中断：外围设备发出中断信号，cpu暂停执行即将执行的指令，切换到处理中断信号的内核相关进程；

系统调用

能完成特定功能的子程序。每当应用程序要求OS提供某种服务（功能）时，便调用具有相应功能的系统调用。只能通过程序代码间接使用。

作用：

  • 保证系统的稳定性和安全性；
  • 防止用户进行非法操作；
  • 使编程更加容易；
  • 提高了程序的可移植性。

与$\overset{API}{应用程序接口}$的相关：

  • 联系：
    • 调用形式一致；
    • 关注的都是函数名、参数类型及返回代码的含义；
    • API可能调用零个或多个系统调用、调用相同的系统调用
  • 区别：
    • API是一组函数定义，获得一个给定的服务；系统调用是通过软中断向内核发出一个明确的请求；
    • 系统调用的实现是在内核完成的，API的实现是在函数库完成的。

中断

用于实现多道程序设计，分为：

  • （外）中断；与当前指令无关，可以屏蔽
  • 异常/陷入/内终端：与当前指令有关，不可屏蔽
    • 执行$\overset{trap}{陷入}$指令

中断优先级：中断的优先程度

  • 为提高资源利用率高速，设备的中断优先级应当高；
  • 交互式系统考虑用户响应满意优先原则；
  • 实时系统中实时设备优先。

依赖中断向量表：存放中断处理程序入口地址和程序运行所需处理机状态字的内存单元。

中断处理流程：

  • 保存现场
  • 分析中断、执行中断处理程序
  • 考虑中断嵌套
  • 恢复现场

程序运行

  • 编译
  • 装入：将程序调入内存
    • 绝对装入方式（单道程序环境）：逻辑地址与实际内存地址相同、由绝对装入程序装入、只能装入内存中事先指定的位置
    • 可重定位方式：进行静态地址重定位（装入内存时对有关指令的地址部分全部一次修改，不允许程序运行时在内存中移动位置）
    • 动态运行时装入：进行动态地址重定位（程序执行时每次访问内存之前，将要访问的程序地址转换为内存地址，依靠硬件地址变换机构一个$\overset{BR}{基地址寄存器}$和若干$\overset{VR}{程序虚拟地址寄存器}$，允许改变其在内存中的位置）
  • 链接：多个程序模块组成一个装入模块
    • 静态链接方式：事先进行链接，形成一个完整的装入模块
    • 装入时动态链接：装入时，若存在外部模块调用，由装入程序找出相应外部模块，并装入内存和修改相对地址。便于修改、更新、便于共享模块
    • 运行时动态链接：程序执行时：若存在外部模块调用，由操作系统找出相应外部模块，并装入内存和修改相对地址。加快装入，节省内存
  • 运行

进程管理

进程的基本概念

定义

进程是具有独立功能的程序在某个数据集合上的一次运行活动，是系统进行资源分配（和调度）的独立单位。

组成

  • 程序
    • 进程是动态的，程序是静态的；
    • 进程是暂时的，程序是永久的；
    • 进程的组成更广；
    • 进程可以调用多个程序、一个程序可被多次执行。
  • 数据
  • $\overset{Process Control Block}{进程控制块}$：在内存中处于核心段，是存放进程的管理和控制信息的数据结构，记录进程的外部特征，描述进程的运动变化过程。
    • 作用：进程的唯一标志；进程的状态转换、推进以PCB体现。
    • 组成：
      • 进程描述信息：
        • $\overset{Process IDentifier}{进程标识符}$：唯一，一个整数，方便系统使用。
        • $\overset{User IDentifier}{用户标识符}$：由创建者提供，在访问该进程时使用；
      • 处理机状态，均为寄存器：通用寄存器、指令计数器、$\overset{PSW}{程序状态字}$、用户栈指针
      • 进程调度信息：进程状态、进程优先级、进程调度所需的其它信息、事件
      • 进程控制信息：程序和数据的地址、进程同步和通信机制、资源清单、链接指针

组织起来、存放在内存的固定区域的PCB称为PCB表，其大小决定了系统中最多可同时存在的进程个数，称为系统的并发度。

特征

  • 并发性
  • 动态性
  • 独立性
  • 异步性
  • 结构性

分类：

按地位：

  • 系统进程：分配一个初始的资源集合，包含独占/最高优先级的资源；在内核态下运行
  • 用户进程：通过请求竞争使用资源；不能直接做I/O操作；在用户态下运行。 按功能：计算进程、I/O进程等。

表示

进程树（图）描述了进程的家族关系。

进程树

进程基本管理

状态

  • $\overset{New}{创建}$：创建PCB等。
  • $\overset{Ready}{就绪}$：具备运行条件，但未运行。
  • $\overset{Ready Suspend}{就绪挂起}$：具备运行条件，但未运行，且被对换至外存。
  • $\overset{Running}{运行}$：占有CPU，正在运行。
  • $\overset{Blocked}{阻塞}$：等待事件的发生而暂时不能运行。
  • $\overset{Blocked Suspend}{阻塞挂起}$：等待事件的发生而暂时不能运行，且被对换至外存。
  • $\overset{Terminating}{终止}$：结束运行，等待回收。

转换

11

组织（即PCB的组织）

  • 链接方式：把具有相同状态的PCB，用其中的链接字，链接成一个队列。
  • 索引方式：根据进程状态建立索引表以存储PCB在PCB表中的位置，记录索引表的首地址于专用文件。

系统中的进程队列根据进程状态分为：

  • 就绪队列：整个系统一个；
  • 等待队列：每个等待事件一个；
  • 运行队列：单机系统中整个系统一个。

控制

系统使用具有特定功能的程序段（原语）来创建、撤销进程以及完成各进程状态间的转换，从而达到多进程高效率并发执行和协调，实现资源共享的目的。

原语要么全做，要么全不做，不允许中断。

原语名 引发事件 功能
create 用户登录，作业调度，提供服务，应用请求 申请空白PCB，为新进程分配资源，初始化PCB，将新进程插入就绪队列
destroy 进程的正常结束，异常结束，外界干预（外界终止、父进程请求或终止） 终止进程且置调度标志为真，子进程终止，归还资源给其父进程或系统，从PCB队列中移出PCB
block 请求系统服务而得不到满足、新数据尚未到达 停止执行、保护现场，修改PCB为阻塞状态，加入阻塞队列
wakeup 引起进程阻塞的事件已发生，新数据已到达 修改PCB为阻塞状态，加入就绪队列
进程调度/切换 进程终止，进程阻塞，有优先级更高的进程到来，进程的时间片用完 保存当前进程运行环境，将PCB加入相应队列，调度新进程上CPU，恢复新进程运行环境

进程间通信

即进程之间的信息交换，分为：

  • 低级通信：进程之间控制信息的交换，传送少量信息。
  • 高级通信：利用操作系统所提供的一组通信命令，传送大量数据。

实现上有：

  • $\overset{Shared-Memory\enspace System}{共享存储器系统}$：共享某些数据结构或共享存储 区
    • 基于共享数据结构的通信方式，属于低级通信
    • 基于共享存储区（共享内存）的通信方式，属于高级通信。流程：进程在物理内存上开辟一块共享内存，将共享内存挂接到它们自己的进程地址空间中，进程通过虚拟地址和页表的映射找到共享内存读写，互斥访问共享内存。
  • $\overset{Message-Passing\enspace System}{消息传递系统}$：以格式化的消息，将通信的数据封装在消息中并利用操作系统提供的一组原语通信：send/receive。属于高级通信。
    • 直接通信法：直接把消息挂在接收进程的消息缓冲队列上。缺点：必须指定接收进程ID，两个进程都要存活。
    • 间接通讯法：发送到某个中间实体（信箱，即消息队列），接收进程从中取得消息。要求发送消息时消息队列不为满，接受消息时消息队列不为空。
  • $\overset{Pipe}{管道}$：连接一个读进程和多个写进程的文件，以字符流的形式进行先进先出的单向通信。属于高级通信。要求互斥、同步且对方进程必须存活。

线程的概念

定义

线程是实施处理机调度和分配的基本单位。

组成：$\overset{Thread Control Block}{线程控制块}$

  • 两个堆栈指针，指向用户栈和向系统栈
  • 一个私用的现场保护区，存放现场保护信息

优势

  • 同一进程的线程共享同一个用户地址空间，切换开销要少；
  • 同一进程的线程共享程序和资源，线程的创建和销毁无需进行资源分配和回收、资源访问无需切换；
  • 同一进程的线程可以直接通过访问共享的进程地址空间进行通讯；
  • 同一进程的线程之间并发，提升了系统的并发度。

线程的状态和转换

同进程一致

线程的实现方式

  • $\overset{User\enspace Level\enspace Threads}{用户级线程}$：由线程库实现，在用户空间中的，与内核无关。
    • 优点：线程切换不需要转换到内核空间；调度算法可以是进程专用的；用户级线程的实现与OS平台无关
    • 缺点：系统调用的阻塞问题；多线程应用不能利用多处理机进行多重处理。
  • $\overset{Kernel\enspace Level\enspace Threads}{内核级线程}$：由操作系统实现，在内核的支持下运行。
    • 优点：内核能够同时调度同一进程中的多个线程并行执行；在一个线程阻塞时，其他线程不受影； 内核支持线程具有很小的数据结构和堆栈，线程的切换比较快，切换开销小。
  • 组合方式

CPU调度

定义及分类

因为资源的有限性，多个进程必须按照一定的原则选择进程（请求）来占用资源。分为：

  • 高级调度/作业调度/长程调度：外存上处于后备队列中的哪些作业调入内存并创建、分配必要资源、排在就绪队列。
    • 每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB。
    • 需要决定：接纳多少个作业 ，取决于多道程序度；接纳哪些作业 ，取决于调度算法
  • 中级调度/中程调度/对换调度：决定哪些进程参与竞争处理器资源。
    • 进行对换。缓解内存资源的紧张状态
    • 每个进程可能多次。
  • 低级调度/处理机调度/分派调度：决定驻在内存中的哪一个就绪进程可以占用CPU。
    • 执行频率最高。

调度目标

  • 资源利用率：使系统中的资源都尽可能地保持忙碌状态。
  • 公平性：诸进程都获得合理的CPU 时间，不会发生进程饥饿现象。
  • 平衡性：使系统中的CPU和各种外部设备都能经常处于忙碌状态。
  • 策略强制执行：只要需要，就必须予以准确地执行，即使会造成某些工作的延迟也要执行。

调度指标

  • 周转时间：$作业完成时间 – 作业提交时间$
  • 平均周转时间：$\frac{总周转时间}{作业数}$
  • 带权周转时间：$\frac{周转时间}{实际运行时间}$
  • 平均带权周转时间：$\frac{总带权周转时间}{作业数}$
  • 系统吞吐量：$\frac{完成作业数}{完成作业时间}$
  • 资源利用率：$\frac{某资源有效工作时间}{某资源总工作时间}$

调度方式

  • 不可剥夺/不可抢占调度：一个进程在获得处理机后，除非自己放弃处理机，否则就可以一直运行下 去。
  • 可剥夺方式：在某些条件下系统可以强制剥夺正在运行中的进程使用处理机的权利。

调度时机

  • 进程主动放弃处理机：执行完毕，或因发出I/O请求、等待事件、请求资源进入阻塞状态而加入等待队列。
  • 可剥夺进程调度下：进程因中断处理完成、资源申请完成、事件等待完成等原因从其它状态变成就绪状态。
  • 为支持轮流占用处理机：进程时间片到，进程的优先级发生变化。

进程切换过程

  • 保存处理机现场，包括程序计数器PC、处理机状态字PS、其它寄存器等。
  • 修改当前运行进程的进程控制块内容，包括将进程状态从运行态改成其它状态。
  • 按照调度算法选择一个进程。
  • 修改被调度进程的进程控制块，包括把其状态改变到运行态。
  • 恢复被选进程的处理机现场，按原保护的程序计数器值重置程序计数器PC，运行新选进程。

调度算法

  • 先来先服务（FCFS）调度算法：按照作业（进程）进入系统的先后次序进行调度。非抢占式算法。
    • 有利于长作业
    • 没考虑进程的优先级
  • 短作业（进程）优先调度算法：按照估计运行时间最短的作业（进程）进行调度。非抢占式算法。
    • 对长作业不利，出现饥饿现象
    • 未考虑作业的紧迫程度
    • 无法真正预估运行时间
  • 最短剩余时间优先调度算法SRTF：进入就绪状态的新进程，如果估计运行时间比现在运行进程的剩余估计时间短，则进行调度。抢占式算法。
    • 可以用于分时系统
    • 系统开销增加（保存进程的运行情况记录，比较其剩余时间大小）、抢占本身也要消耗处理机时间
  • 高响应比优先调度算法：按照所有就绪进程的响应比进行调度。非抢占式算法。
    • 相应比=$\frac{周转时间}{运行时间} = 1+\frac{等待时间}{运行时间}$
    • 综合考虑了等待时间和运行时间，避免了长作业饥饿。
  • 时间片轮转法（RR）：时间片轮转给每个进程运行。抢占式算法。
  • 优先级调度法：把处理机分配给就绪队列中优先权最高的进程。可以进行抢占，可以动态改变优先级。
    • 适用于实时操作系统。
    • 若源源不断地有高优先级进程到来，则可能导致饥饿。
  • 多级反馈队列算法（MLFQ）：多个队列，优先级从高到低，时间片从短到长。队列间抢占，队列内FCFS执行一个时间片，若未仍执行完则放入下一个队列，最后一个队列采用RR。

进程同步

基本概念

同步：进程需要相互合作，引起相互等待对方消息或信号的协调关系。

互斥：进程因为争夺（共享的）临界资源而互斥执行。其中临界资源指一段时间内只允许一个进程访问的资源。

临界区：与临界资源操作相关的程序段。Dijkstra 1965年提出的设计原则为：

  • 至多有一个进程处于临界区
  • 有限时间内使一进程进入临界区
  • 进程临界区内逗留有限的时间

同步的准则为：

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

实现方法

软件方法

进入临界区之前要申请，获得批准方可进入；退出临界区之后要声明，以便其他进程进入。

  • 单标志检查法：定义单个全局变量，每个值标志某进程可进入
    • 不符合空闲让进
  • 双（多）标志检查法：为每个进程定义全局布尔变量标志其可进入，检查其他进程是否可进入。
    • 进入前修改自己变量，违背忙则等待。
    • 进入后修改自己变量，不能实现互斥、违背忙则等待。
  • Peterson算法：为每个进程定义全局布尔变量标志其欲进入，并定义全局变量标志允许进入进程。
    • 进入前修改自己变量为欲进入，设置全局布尔变量为他人进入（谦让），若对方欲进入且能进入则等待。退出后修改自己变量为不欲进入。
    • 违反让权等待。

硬件方法

  • 屏蔽中断：在进入临界区前禁止中断，在退出临界区后允许中断。即不发生进程切换。
    • 简单
    • 用户进程不应当使用、不适用于多处理机。
  • Test_and_Set指令：返回原始情况并上锁。
    • 简单，适用于多处理机。
    • 不满足让权等待。
  • Swap指令：返回原始情况并通过交换上锁。同Test_and_Set指令。

锁机制

使用一个标志或一个变量来代表临界资源的状态。系统提供一对在锁位W上进行操作的上锁原语Lock(W)和开锁原语UnLock(W)。

  • Lock：测试W的值，若W=1，表示资源正在使用，继续反复测试；若W=0，则设置W=1（上锁）。
  • Unlock：设置W=0（开锁）。

进入临界区的进程执行上锁原语，退出临界区时再执行开锁原语。

信号量机制

将一类资源抽象成一个信号量。分为：

  • 整型信号量：用一个整数来表示信号量的值。若大于零，则表示资源可用的个数，若小于等于零，则表示资源不可用，共挂起进程数目。
  • 记录型信号量：同时附加一个挂起进程队列。

只能进行P、V操作。

  • P操作（申请资源）：信号量减1，若信号量小于0，则进程挂起。
  • V操作（释放资源）：信号量加1，若信号量大于0，则唤醒首先挂起的进程。

要求：

  • 必须置一次且只能置一次初值。
  • 初值只能为非负整数，实现互斥时初值为1。
  • 只能执行P、V操作，且P、V操作成对出现。

管程机制

由若干公共变量和所有访问这些变量的过程所组成的一个特殊的模块或软件包。组成：

  • 管程名称
  • 局部变量：包括条件变量和普通变量。
  • 操作
  • 初始化语句

管程的特征：模块化、抽象数据类型、信息掩盖

优点：安全、互斥、等待机制

局限性：是编程语言的组成部分

和进程的区别

  • 设置目的不同：管程是对共享资源进行管理，进程是资源分配的基本单位。
  • 数据结构不同：管程定义公用数据结构，进程定义私有数据结构。
  • 存在方式不同：进程有生命周期，管程是操作系统固有的部分，没有生命周期。
  • 执行方式不同：管程被进程调用，没有并发性，进程具有并发执行性。

死锁

基本概念

是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象。

产生原因

  • 竞争临界资源：
    • 可剥夺和非剥夺性资源
    • 永久性和临时性资源
  • 进程推进顺序不当

必要条件

  • 互斥
  • 占有并请求
  • 不可剥夺
  • 循环等待

解决

预防

  • 静态资源分配法（摒弃“占有并请求条件”）：一次性地申请其在整个运行过程所需的全部资源。
    • 简单、安全、易实现
    • 资源被严重浪费；进程延迟运行。
  • 摒弃“不可剥夺条件”：需要资源时提出请求，不能满足则全部释放。
    • 实现起来比较复杂，且要付出很大的代价；进程的周转时间较长，系统开销大
  • 有序资源使用法（摒弃“循环等待条件”）：按预先给定的顺序申请资源。
    • 安全且资源利用率比静态资源分配法有所提高
    • 实现较困难；仍有一定的资源浪费现象

避免

对进程提出的每一次资源请求进行动态检查。

系统的安全状态：若在某一时刻，系统中存在某种进程序列，按此序列一次为每个进程分配其所需的所有资源并顺利完成。则称此时系统的状态为安全状态，称这样的一个进程序列为安全序列。

银行家算法：Dijkstra提出，要求进程预先提出自己的最大资源请求，并且假设系统拥有固定的资源总量：

  • 数据结构包括：可利用资源向量Available、最大需求矩阵Max、已分配矩阵Allocation和进程请求矩阵Need。
  • 安全性检查算法：不断检查是否有一个进程的请求可被满足，有则分配执行，并维护可用资源向量Available。如果每个进程都被满足则系统是安全的，否则是不安全的。
  • 整体算法：当进程发出资源请求后，检查时候满足
    • Request 小于等于 Need 且 Request 小于等于 Available
    • 尝试分配、维护矩阵，进行安全性检查，如果安全则正式分配，否则该进程等待。

银行家算法的实质：保证系统动态分配资源后不进入不安全状态。但缺乏使用价值（所需资源的最大值、进程数均不确定）

检测

资源分配图：存在进程节点、资源节点、从进程到资源的申请边、从资源到进程的分配边。

资源分配图的化简：执行存在边但不被阻塞的进程，移除其所有边。完全化简：移除了所有边。

死锁定理：S状态为死锁状态的充分条件是当且仅当S状态的资源分配图是不可完全简化的。

解除

  • 最小撤消进程法：计算死锁进程的撤消代价，然后依次选择撤消代价最小的进程，直至死锁不复存在。
  • 挂起进程法 （剥夺资源）：挂起/激活机构挂起一些进程，剥夺它们的资源以解除死锁。
  • 进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程。

进程的选择：进程优先级低、已运行时间短、距离结束时间长、使用资源多、非交互式。

内存管理

基本概念

物理地址/绝对地址：主存的真实地址，存储控制部件能够识别的主存单元编号。 逻辑地址/相对地址：相对于某个基准量（通常用0）编址时所使用的地址，常用于程序编写和编译过程中。

内存的分配与回收

连续分配（与回收）管理方式

单一连续分配

内存分为系统区:（供OS使用，通常放在低址部分）和用户区（系统区以外的全部内存空间，单一用户程序独占整个用户区空间）

实例CP/M，MS-DOS，RT-11

优点：实现简单；无外部碎片；可以采用覆盖技术扩充内存；无需存储保护。

缺点：只能用于单用户、单任务的操作系统中；有内部碎片；存储器利用率极低。

固定分区分配

内存用户空间划分成若干分区，每个分区中只装入一道作业。

  • 分区大小相等：缺乏灵活性，用于控制多个相同对象的系统
  • 分区大小不等：多个较小分区、适量中等分区、少量大分区

将分区按大小或地址排序，建立分区使用表——起址、大小、状态，装入时由内存分配程序检索找到符合要求的分区，并进行标记。

优点：易于实现，开销小，无外部碎片。

缺点：有内部碎片，造成浪费；分区总数固定，限制了并发执行的程序数目；当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能；

动态分区分配

在系统初启时，除了操作系统中常驻内存部分之外，只有一个空闲分区。进程的处理过程中建立分区，且其大小可随进程对内存的要求而改变。

数据结构：

  • 空闲分区表
  • 空闲分区双向链表

具体的分配算法有：

  • 首次适应算法（first fit, FF）：地址递增的次序组织空闲区表（链），逐次检查空闲区表，直到找到合适的空闲区，划出申请大小。
    • 优先使用内存中低址部分的小空闲区，有利于大作业
    • 低址部分形成许多难以利用的小空闲分区，每次又从低址开始查找，增加时间开销。
  • 循环首次适应算法（next fit）：地址递增的次序组织空闲区循环表（链），逐次从上次检查的位置开始检查空闲区表，直到找到合适的空闲区，划出申请大小。
    • 使空闲分区分布均匀，减少查找开销
    • 缺乏大空闲分区，不利于大作业
  • 最佳适应算法（best fit）：大小递增的次序组织空闲区表（链），逐次检查空闲区表，直到找到合适的空闲区，划出申请大小。
    • 尽量使用小空闲区，保留大空闲区
    • 形成许多难以利用的碎片
  • 最坏适应算法（worst fit）：大小递减的次序组织空闲区表（链），逐次检查空闲区表，直到找到合适的空闲区，划出申请大小。
    • 防止产生碎片，空间浪费最少,有利于中、小作业，查找效率很高
    • 缺乏大的空闲分区
  • 快速适应算法(QF,分类搜索法)：按进程常用空间大小对空闲分区进行划分，形成多类分区链表，并设立一张分区管理索引表。
    • 查找效率高，可满足大空间需求；
    • 但分区归还算法复杂、空间开销大。

回收算法为：

  • 标记为空闲分区；
  • 与相邻空闲分区合并，否则加入空闲分区表（链）；

可重定位分区分配

通过“拼接”或“紧凑”“碎片”小分区形成大块分区。

  • 消除了“碎片”，提高了内存利用率，同时提高了系统效率。
  • 需要动态重定位机构支持，增加了系统成本，并轻度降低了程序执行速度，增加了系统开销。

不连续分配方式

分页存储管理方式

提高系统资源利用率

把用户程序的地址空间划分成若干大小相等的页。内存空间划分成若干和页大小相同的页框。以页为单位分配至页框。页面大小由硬件地址结构决定。

“页内碎片”：最后一页装不满而形成的碎片，不可利用。

逻辑地址结构：页号、页内地址。

求页内地址：$逻辑地址 \% 页大小$

每个进程的页表组织每个页面在内存中对应的页框，实现页号到物理块号的地址映射。

地址变换机构：

  • 基本地址变换机构：
    • 页表寄存器PTR存放页表始址和长度。
    • 地址变换处理：将页号查询到的页框号与页内地址拼接即为物理地址。
    • 额外越界保护：查页表前，将页号与PTR中的页表长度比较
  • 具有快表的地址变换机构：
    • 增设一个联想寄存器（快表），每次地址变换时，先在快表中查找，快表中找不到，再访问内存中的页表，并将页表项存入快表，若快表已满，应换出最老的页表项。

多级页表：页表和页面一样也进行分页，不需要占用连续的内存空间。

优点：存在页内碎片，但碎片相对较小，内存利用率较高；实现了离散分配，消除了程序浮动。

缺点：需要专门的硬件支持，尤其“快表”；内存访问的效率下降。

分段存储管理方式

满足用户（程序员）的需求

程序按逻辑关系划分为若干个程序段。内存空间被动态的划分为若干个长度不相同的物理段，每个物理段由起始地址和长度确定。

逻辑地址结构：段号、段内地址。

地址变换机构：

  • 段表
  • 将段号查询到的物理段号与段内地址拼接即为物理地址。
  • 额外越界保护：查段表前，将段号与段表长度比较

段页式存储管理方式

用户作业先分段，每段内分页。内存分页。

逻辑地址结构：段号、段内页号、页内地址。

地址变换机构：先查段表得到页表，再查页表得到物理地址。

优点：同时具备分段和分页管理的优点，分散存储，内存利用率较高；便于代码或数据共享，支持动态链接等。

缺点：访问效率下降，一次访问转换成了三次访问。

内存保护

防止越界访问：限制进程只能访问自身的地址空间，避免访问到其他进程的空间造成破坏，也避免被其他进程破坏。

实现方法：

  • 设置一对上、下限寄存器，访问某个地址时， CPU检查是否越界。
  • 采用重定位寄存器/基址寄存器（存放起始物理地址）和界地址寄存器/限长寄存器（存放进程的最大逻辑地址）。

内存扩充

覆盖技术

作业之间或作业内部的若干个程序段共享主存。通过令

  • 常驻内存的段调入后直至运行结束就不再调出
  • 不常用的段需要用到时调入内存， 用不到时调出内存

必须由程序员声明覆盖结构，操作系统完成自动覆盖。对用户不透明，增加了用户编程负担。 覆盖技术只用于早期的操作系统中。

对换技术

对换：把内存中暂时不能运行/不用的程序（和数据）调出到外存，以腾出空间供具备运行条件的进程或其程序数据调入内存运行。用于解决内存不足的问题。

需要将外存分出对换区：用于存放从内存换出的进程，需要提高进程换入和换出的速度。采取连续分配方式。

分为：整体对换（以进程为单位的对换）和部分对换（以“页”或“段”为单位的对换）。

换出流程：选择处于阻塞状态且优先级最低的进程，将该进程的程序和数据传送到磁盘的对换区上，回收内存空间，修改该进程的PCB。

换入流程：定时查看进程状态，将处于就绪态的换出时间最久的进程换入内存。

PCB 会常驻内存，不会被换出外存。

正常时并不启用对换，内存紧张时，启用对换，把部分进程调出，缓解紧张状况后，暂停对换程序。

虚拟内存

基本概念

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

这是由于程序执行的局部性原理；相应地，它所访问的存储空间也局限于某个区域。

特征：离散性、多次性、对换性、虚拟性。

请求分页存储管理方式

页表项为页号、物理块号、状态位P（是否调入内存）、访问字段A（访问次数）、修改位M（调入后是否修改过）、外存地址

缺页中断机构：访问的页不在内存时引起。阻塞缺页的进程，调入页后唤醒。

  • 如果内存中有空闲块，为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。
  • 否则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。然后按上述执行。

地址变换机构：

  • 首先检索快表，若找到，修改页表项中的访问位，然后利用页表项中给出的物理块号和页内地址，形成物理地址。
  • 如果在快表中未找到相应的页表项，检索内存中的页表，查看页表中的状态位，若该页已经调入内存，填写快表，当快表满时，应淘汰一个页表项。
  • 若该页尚未调入内存，产生缺页中断，请求操作系统把该页调入，修改页表内容；若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存，并修改页表内容。

物理块/页框分配算法：

  • 最小物理块数的确定：保证进程正常运行所需的最小物理块数。
  • 物理块的分配策略：
    • 固定分配局部置换：运行期间都不再改变，只能换出自己的内存页。
    • 可变分配全局置换：为每个进程分配一定数目的物理块，页面的置换范围是任一个进程。
    • 可变分配局部置换：为每个进程分配一定数目的物理块，只能换出自己的内存页。
  • 物理块的分配算法：平均分配算法、按比例分配算法、考虑优先权的分配算法

缺页率：缺页次数/总访问次数

调页策略：

  • 预调页：一次调入该页以及相邻的几个页。
    • 提高调页的I/O效率。
    • 若调入的页在以后很少被访问，则效率低。常用于程序装入时的调页。
  • 请求调页：只调入发生缺页时所需的页面。
    • 容易实现。
    • 对外存I/O次数多，开销较大

调页优化：

  • 对换空间充足：进程装入时，将其全部页面复制到对换区，以后总是从对换区调入。调入速度快。
  • 凡是不会被修改的页面，都直接从文件区读入，而被对换时不需调出；已被修改的页面，被对换时需调出到对换区，以后从对换区调入。节省对换区空间。

具体的页面置换算法：

  • 先进先出（FIFO）：最早调入的页面最先被调出。
    • 实现简单
    • 与进程实际的运行不相适应
  • 最佳(Optimal)置换算法：被淘汰页面，将是以后永不使用的，或是在最长(未来)时间内不再被访问的页面。
    • 实现简单，与进程实际的运行不相适应
    • 无法预知
  • 最近最久未使用置换算法（LRU）：最近一段时间最久未被使用（访问）的页淘汰
    • 性能较好
    • 实现复杂，需要硬件支持（每页配置一个寄存器或栈），增加系统负担。
  • Clock置换算法/最近未用算法NRU：组织为环形缓冲区，从上次扫描结束位置开始，依次扫描缓冲区，直到找到（最近）未使用过的页面
  • 改进型Clock置换算法：按最近未被访问也未被修改——最近未被访问但已被修改——最近未被访问但已被修改——最近已被访问且被修改顺序查找。

虚拟存储器性能“抖动”：当CPU的利用率达到某一峰值后，若继续增加多道程度，将产生抖动，CPU利用率急剧下降。原因：

  • 页面置换算法不合理
  • 分配给进程的物理页面（驻留集）数太少
  • 进程多，缺页频繁

工作集：指在某段时间间隔里，进程实际访问页面的集合。

内存映射文件I/O

将文件中的一部分连续的区域映射成一段进程逻辑地址空间中的内存。由页面调度算法自动进行物理内存分配，根据虚拟内存的页面调度算法，按需调入数据文件中的内容，必要时淘汰（可能需要写入）内存页面。

优点：比使用read，write方式速度更快；提供了多个独立启动的进程共享内存的一种手段