操作系统原理笔记（2）

操作系统第三第四章知识点总结

第三章:处理机调度与死锁

处理机调度算法的目标

处理机调度的层次

1. 高级调度
   • 称为长程调度或者作业调度，调度对象是作业
2. 低级调度
   • 称为进程调度或者短程调度
3. 中级调度
   • 称为内存调度，用于提高内存利用率和系统吞吐量

进程调度的频率最高而且10mms~100ms进行一次进程调度，所以称为短程调度。作业调度周期最长所以称为长程调度。

处理机调度算法的共同目标

• 资源利用率:CPU的利用率=CPU有效工作时间/(CPU有效工作时间+CPU空闲等待时间)
• 公平性
• 平衡性
• 策略强制执行

批处理系统的目标

• 平均周转时间短
• 系统吞吐量高
• 处理机利用率高

分时系统的目标

• 响应时间快
• 均衡性

实时系统目标

• 截止时间的保证
• 可预测性

作业与作业调度

批处理中的作业

1. 作业
   • 作业不仅包含程序和数据，还配有一份作业说明书，系统根据说明书对程序的运行进行控制。批处理系统是以作业为单位从外存掉入内存的。
2. 作业步（JobStep）
   • 作业步，每个作业都必须经过若干相对独立，有相互关联的顺序步骤才能得到结果。每一个步骤就是一个作业步。
3. 作业控制块（Job Control Block,JCB）
   • 为每个作业设置一个JCB，保存了对作业管理调度的全部信息。是作业存在的标志。
4. 作业运行的三个阶段
   1. 收容阶段：把用户提交的作业通过某种输入方式或者SPOOLing系统输入到硬盘，建立JCB，并把它放入作业后备队列
   2. 运行阶段：作业被选中后，为它分配必要的资源和建立进程，并放入就绪队列，直到运行结束前，都属于运行状态
   3. 完成阶段：当作业运行完成或者发生异常而提前结束，作业会进入完成阶段。系统回收作业的作业控制块和所有资源，并将结果信息输出

作业调度的主要任务

每次执行作业调度是，需要做出以下决定3

• 接纳多少个作业
• 接纳哪些作业

先来先服务(first–come first–served，FCFS)调度算法

• 比较有利于长作业，而不利于短作业。
• 有利于CPU繁忙的作业，而不利于I/O繁忙的作业

短作业优先(short job first，SJF)的调度算法

• 优点
  • 比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；
  • 提高系统的吞吐量；
• 缺点
  • 必须预知作业的运行时间
  • 对长作业非常不利，长作业的周转时间会明显地增长
  • 在采用SJF算法时，人–机无法实现交互
  • 该调度算法完全未考虑作业的紧迫程度，故不能保证紧迫性作业能得到及时处理

优先级调度算法(priority–scheduling algorithm，PSA)

选择优先级最高的作业装入内存

高响应比优先调度算法(Highest Response Ratio Next,HRRN)

• 原理
  • 在每次选择作业投入运行时，先计算此时后备作业队列中每个作业的响应比RP然后选择其值最大的作业投入运行
  • 优先权=(等待时间+要求服务时间)/要求服务时间=响应时间/要求服务时间=1+等待时间/要求服务时间
• 特点
  • 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而类似于SJF算法，有利于短作业
  • 当要求服务的时间相同时，作业的优先权又决定于其等待时间，因而该算法又类似于FCFS算法
  • 对于长时间的优先级，可以为随等待时间的增加而提高，当等待时间足够长时，也可获得处理机

进程调度

进程调度的任务、机制和方式

1. 进程调度的任务
   1. 保存处理机的现场信息
   2. 按某种算法选取进程
   3. 把处理器分配给进程
2. 进程调度机制
   1. 排队器
   2. 分配器
   3. 上下文切换器
3. 进程调度方式
   1. 非抢占方式
   2. 抢占式

轮转调度算法

基于时间片的轮转，让就绪队列上每个进程每次获得一个时间片。

优先级调度算法

• 优先级调度算法类型
  • 非抢占式
  • 抢占式
• 优先级类型
  • 静态优先级
  • 动态优先级

多队列调度算法

基于公平原则的调度算法

实时调度(HRT和SRT任务)

实现实时调度的基本条件

• 提供必要信息
  • 就绪时间
  • 开始截止时间和完成截止时间
  • 处理时间
  • 资源要求
  • 优先级
• 系统处理能力强
  • ∑(Ci/Pi)≤1
  • N个处理机:∑(Ci/Pi)≤N
• 采用抢占式调度机制
• 具有快速切换机制
  • 对中断的快速响应能力
  • 快速的任务分派能力

实时调度算法的分类

• 非抢占式调度算法
  • 非抢占式轮转调度算法
  • 非抢占式优先调度算法
• 抢占式调度算法
  • 基于时钟中断的抢占式优先级调度算法
  • 立即抢占的优先级调度算法

最早截止时间优先EDF(Earliest Deadline First)算法

• 根据任务的开始截至时间来确定任务的优先级
  • 截至时间越早，优先级越高
• 非抢占式调度方式用于非周期实时任务
• 抢占式调度方式用于周期实时任务

最低松弛度优先LLF(Least Laxity First)算法

• 类似EDF
• 算法根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高， 以使之优先执行。
• 松弛度例子
  • 例如，一个任务在200ms时必须完成，而它本身所需的运行时间就有100ms，因此，调度程序必须在100 ms之前调度执行，该任务的紧急程度(松弛程度)为100 ms

优先级倒置(Priority inversion problem)

• 优先级倒置的形成
  • 高优先级进程被低优先级进程延迟或阻塞。
• 优先级倒置的解决方法
  • 简单的:假如进程P3在进入临界区后P3所占用的处理机就不允许被抢占
  • 实用的:建立在动态优先级继承基础上的

死锁概述

资源问题

• 可重用性资源
  • 一个可重用资源只能给一个进程使用
  • 按照顺序：请求资源->使用资源->释放资源
  • 每一类可重用资源的单元数目相对固定，
• 可消耗性资源
  • 数据，消息等，由生产者进程创建，消费者进程消耗
• 可抢占性资源
  • 不引起死锁
  • CPU，内存
• 不可抢占性资源
  • 光驱，打印机

计算机系统中的死锁

• 竞争不可抢占性资源引起死锁
• 竞争可消耗资源引起死锁
• 进程推进顺序不当引起死锁

死锁的定义，必要条件和处理方法

• 定义:如果一组进程中的每一个进程都在等待仅由该进程中的其他进程才能引发的事件，那么该组进程是死锁的
• 产生死锁的必要条件（四个缺一不可）
  • 互斥条件
  • 请求和保存条件
  • 不可抢占条件
  • 循环等待条件

预防死锁

静态方法，在进程执行前采取的措施，通过设置某些限制条件，去破坏产生死锁的四个条件之一，防止发生死锁。

破坏”请求和保存”条件

• 第一种协议
  • 所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源
  • 优点:简单，易行，安全
  • 缺点
    • 资源被严重浪费，严重地恶化了资源的利用率
    • 使进程经常会发生饥饿现象
• 第二种协议
  • 它允许一个进程只获得运行初期所需的资源后，便开始运行。进程运行过程中再逐步释放已分配给自己的，且已用毕的全部资源，然后再请求新的所需资源

破坏”不可抢占”条件

当一个已经保存了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请

破坏”循环等待”条件

• 对系统所以资源类型进行线性排序，并赋予不同的序号
• 例如令输入机的序号为1，打印机序号为2，磁盘机序号为3等。所有进程对资源的请求必须严格按资源序号递增的次序提出。

避免死锁

动态的方法，在进程执行过程中采取的措施，不需事先采取限制措施破坏产生死锁的必要条件，而是在进程申请资源时用某种方法去防止系统进入不安全状态，从而避免发生死锁。如银行家算法

系统安全状态

• 安全状态
  • 某时刻，对于并发执行的n个进程，若系统能够按照某种顺序如<p1,p2…pn>来为每个进程分配所需资源，直至最大需求，从而使每个进程都可顺利完成，则认为该时刻系统处于安全状态，这样的序列为安全序列
• 安全状态之例
• 由安全状态向不安全状态的转换

利用银行家算法避免死锁

含义:每一个新进程在进入系统时，它必须申明在运行过程中，可能需要每种资源类型的最大单元数目，其数目不应超过系统所拥有的资源总量。当进程请求一组资源时，系统必须首先确定是否有足够的资源分配给该进程。若有，再进一步计算在将这些资源分配给进程后，是否会使系统处于不安全状态。如果不会，才将资源分配给它，否则让进程等待

• 银行家算法中的数据结构
  • 可用资源向量 Available[m]：m为系统中资源种类数，Available[j]=k表示系统中第j类资源数为k个。
  • 最大需求矩阵 Max[n,m]：n为系统中进程数，Max[i,j]=k表示进程i对j类资源的最大需求数为中k。
  • 分配矩阵 Allocation[n，m]:它定义了系统中每一类资源当前已分配给每一进程资源数， Allocation[i,j] = k表示进程i已分得j类资源的数目为k个。
  • 需求矩阵 Need[n,m]：它表示每个进程尚需的各类资源数，Need[i,j]=k 表示进程i 还需要j类资源k个。Need[i,j]=Max[i,j] - Allocation[i,j]
• 银行家算法
• 安全性算法

死锁的检测与解除

死锁的检测

• 资源分配图
  • 简化步骤
    • 选择一个没有阻塞的进程p
    • 将p移走，包括它的所有请求边和分配边
    • 重复步骤1，2，直至不能继续下去
• 死锁定理
• 死锁检测中的数据结构（比如银行家算法）

死锁的解除

• 抢占资源，从一个或多个进程抢占足够的资源分配给死锁进程
• 终止(或撤销)进程，直至打破循环
• 终止进程的方法
  • 终止所有死锁进程
  • 逐个终止进程
    • 代价最小
      • 进程的优先级的大小
      • 进程已执行了多少时间，还需时间
      • 进程在运行中已经使用资源的多少，还需多少资源
      • 进程的性质是交互式还是批处理的
• 付出代价最小的死锁解除算法
  • 使用一个有效的挂起和解除机构来挂起一些死锁的进程

课后题

高级调度与低级调度的主要任务是什么？为什么要引入中级调度？

高级调度的主要任务是根据某种算法，把外存上处于后备队列中的那些作业调入内存。
低级调度是根据某种算法决定就绪队列中的进程获得处理机，再把处理器分配给被选中的进程。
引入中级调度的主要目的是为了提高内存利用率和系统吞吐量。使那些暂时不能运行的进程不再占用内存资源，将它们调至外存等待，把进程状态改为就绪驻外存状态或挂起状态。

在批处理系统、分时系统和实时系统中，各采用哪几种进程（作业）调度算法？

批处理系统的调度算法：短作业优先、优先级、高响应比优先、多级反馈队列调度算法
分时系统的调度算法：基于时间片的轮转调度
实时系统：最早截止时间优先EDF、最低松弛度优先LLF算法

为什么在实时系统中，要求系统（尤其是CPU）具有较强的处理能力？

实时系统中通常有着多个实时任务。若处理机的处理能力不够强，有可能因为处理机忙不过来而使某些实时任务得不到及时处理，导致发生难以预料的后果。

何谓死锁？产生死锁的原因和必要条件是什么？

死锁指多个进程同时争夺资源而等待其他进程造成的一种僵局。
产生死锁的原因为竞争资源和进程间推进顺序非法。其必要条件是：互斥条件、请求和保持条件、不可抢占条件、循环等待条件。

简答题

1、处理机调度的层次和调度算法的目标
描述：作业可能要经历多级处理机调度
（1）处理机调度层次
①高级调度（长程调度/作业调度）
对象是作业、决定将外存中处于后备队列的作业调入内存.创建进程和分配资源.并放入就绪队列、主要存在于多道批处理系统，分时和实时系统不设置高级调度
②低级调度（进程调度/短程调度）
对象是进程（/内核级线程）、决定就绪队列哪个进程获得处理机、多道批.分时和实时都要配置
③中级调度（内存调度）
对象是暂时不能运行的进程、把这些进程调到外存.设为挂起状态、一有条件.稍微有空就变为就绪状态
★分级按运行频率划分
（2）处理机调度算法的目标
①共同目标
提高资源利用率、公平、平衡、策略强制执行
②批处理系统目标
处理机利用率高、平均周转时间短、系统吞吐量高
③分时系统目标
响应时间快、均衡性
④实时系统目标
截止时间保证、可预测性

2、作业与作业调度
（1）批处理系统中的作业
①作业和作业步
作业：包括程序.数据和作业说明书、在批处理系统.作业是基本单位从外存调入内存
作业步：独立步骤
②作业控制块（JCB）
包括作业标识、用户名称、用户账号、作业类型、作业状态、调度信息、资源需求、资源使用情况等
流程：进入系统→创建JCB→根据类型放到后备队列等待调度→入内存→根据JCB和作业说明书控制→完成→回收资源.撤销JCB
③作业运行的三个阶段和三种状态
收容阶段-后备状态、运行阶段-运行状态、完成阶段-完成状态
（2）作业调度的主要任务
也叫：接纳调度
考虑：接纳多少作业、接纳哪些作业
（3）先来先服务FCFS和短作业优先SJF调度算法
①先来先服务
就这样.完成或阻塞才分配到其他进程、实际中和其他算法结合使用
②短作业优先
实际用得多、要预知作业运行时间、长作业、紧迫作业不利、无人机交互
（4）优先级调度算法和高响应比优先调度算法
①优先级调度算法
外部赋予作业优先级
②高响应比优先调度算法
集SJF.FCFS的优点.兼顾长作业、但要做相应比计算.增加系统开销（Exp.做过类似）

3、进程调度
（1）进程调度的任务、机制和方式
①进程调度的任务
保存处理机的现场信息、按某种算法选取进程、把处理器分配给进程
②进程调度机制
排队器：插入就绪队列
分配器：从就绪队列取出.分配处理机
上下文切换器：保存、装入新的
③进程调度方式
非抢占方式：只有完成或因某事无法继续运行、I/O、执行了原语操作如block，才会引起进程调度
优点：简单、开销小、适用大多数批处理系统
抢占方式：对分时系统而言.有人机交互、对实时系统而言.能满足任务需求
主要原则：优先权原则、短进程优先原则、时间片原则
（2）轮转调度算法
①轮转法（RR）的基本原理
按FCFS策略排成就绪队列，每隔一定时间就产生一次中断
②进程切换时机
时间片未用完就完成：马上调度队首进程.启动新时间片
时间片完还没完成：中断.进程被调到就绪队列队尾
③时间片大小的确定
太短有利于短进程、太长退化为FCFS算法.要计算平均周转时间（带权周转时间）
（3）优先级调度算法
①优先级调度算法的类型
非抢占式和抢占式
②优先级的类型
确定优先级的依据：
静态优先级：进程类型、进程对资源的需求、用户需求
动态优先级：先赋予优先级，随着进程推进或等待时间增加而改变
（4）多队列调度算法
将一条就绪队列拆分成多条，各有各调度算法
（5）多级反馈队列调度算法
①调度机制
多条就绪队列、队列内使用FCFS算法.一个时间片未完成就放到下一个队列的末尾.最后一个队列用RR方式、按队列优先级调度.前队列空才到本队列运行
②调度算法的性能
终端型用户、短批处理作业用户、长批处理作业用户
（6）基于公平原则调度算法
①保证调度算法
保证处理机公平分配
功能：跟踪进程已经执行的处理时间、该时间除以n、计算实际处理时间和应获得时间之比、比较比率、比率最低的获得处理机
②公平分享调度算法
考虑多用户

4、实时调度
描述：实时系统有两种实时任务——HRT和SRT
（1）实现实时调度的基本条件
①提供必要信息
就绪时间、开始截止和完成截止时间、处理时间、资源要求、优先级
②系统处理能力强
（处理时间i/周期时间i）总和 ≤ 1. 未考虑任务切换花费的时间还应该留有余地
提高系统处理能力的途径：单处理机系统增强处理能力.显著减少每个任务的处理时间、多处理机系统.就变成（处理时间i/周期时间i）总和 ≤ N
③采用抢占式调度机制
执行完关键程序和临界区后，能及时将自己阻塞起来，以释放处理机
④具有快速切换机制
对中断的快速响应能力、快速的任务分派能力
（2）实时调度算法的分类
根据任务性质：H/S
根据调度方式：非抢占式/抢占式
①非抢占式调度算法
轮转、优先调度
②抢占式调度算法
基于时钟中断的抢占式优先级调度算法：等待时钟中断发生才剥夺当前任务的执行
立即抢占优先调度算法：好快好快.只要任务未处于临界区.就立即剥夺当前任务执行
（3）最早截止时间优先EDF算法
非抢占式调度方式用于非周期实时任务：开始截止时间早的排前
抢占式调度方式用于周期实时任务：最早截止时间优先算法
（4）最低松弛度优先LLF算法
松弛度？？？
（5）优先级倒置
①优先级倒置的形成
②优先级倒置的解决方法
继承动态优先级的方法：P3继承P1的优先级.一方面避免P2抢占处理机、另一方面释放mutex资源

5、死锁概述
（1）资源问题
指互斥资源、不可被抢占的资源
①可重用性资源和消耗性资源
可重用性资源：一个只能分配给一个进程使用、顺序为请求.使用.释放、数目相对固定.运行期间不能创建或删除
可消耗性资源：在进程运行中树木不断变化.可为0、可以不断创建.放入缓冲区、可以由进程创建.使用并不再返回资源类
②可抢占性资源和不可抢占性资源
可抢占性资源：可以被其他进程抢占.如CPU和主存
不可抢占性资源：一旦分配给进程就不能强制收回.要做到底
（2）计算机系统中的死锁
①竞争不可抢占性资源引起死锁
我要你的，你要我的，形成环路，死锁
②竞争可消耗资源引起死锁
譬如消息通信机制.先读后写.就会死锁
③进程推进顺序不当引起死锁
竞争不可抢占性资源引起死锁的翻版.多画了一个图
（3）死锁的定义、必要条件和处理方法
①死锁的定义
这组死锁进程都在等其他进程释放所占资源
②产生死锁的必要条件
互斥条件：一段时间只被一个进程占用
请求和保持条件：进程已经保持至少一个条件.但有提出新资源请求
不可抢占条件：只能在进程用完才能释放
循环等待条件：存在循环链
③处理死锁的方法
预防死锁：设置限制条件.破坏产生死锁四个必要条件来预防
避免死锁：在资源动态分配时.用防止系统进入不安全状态
检测死锁：通过检测机构及时检测死锁.采取适当措施以解脱
解除死锁：撤销进程.回收资源.分配给处于阻塞的进程
防范逐渐减弱.但资源利用率提高.进程因资源因素而阻塞的频度下降

6、预防死锁
（1）破坏“请求和保持”条件
保证：进程请求资源时，不持有不可抢占资源
第一种协议：一次性全部申请，从而破坏“请求条件”、缺点是资源被严重浪费.进程饥饿
第二种协议：先释放资源.再请求新资源
（2）破坏“不可抢占”条件
当保持了某些不可抢占资源后.提出新资源请求不得满足.就必须释放已经保持的资源.等需要时再申请
缺点：增加周转时间、增加系统开销、降低系统吞吐量
（3）破坏“循环等待”条件
总有一个进程占据了较高序号的资源.此后它继续申请的资源必然是空闲的

7、避免死锁
（1）系统安全状态
①安全状态
计算一个资源分配的安全性.如果分配不会导致不安全状态.才可将资源分配给进程
②安全状态之例
③由安全状态向不安全状态的转换

（2）利用银行家算法避免死锁
①银行家算法中的数据结构
Availalbe、Max、Allocation、Need
②银行家算法
睇wiki“银行家算法”条目
声明：Request是请求向量
Request ≤ Need, 否则出错
Request ≤ Available, 否则P等待
系统试探分配资源给P, 并执行Availalbe -= Requeset; Allocation+= Request; Need -= Request

8、死锁的检测与解除
（1）死锁的检测
①资源分配图
圆圈代表进程、方格代表一类资源、边代表资源分配
②死锁的定理
简化资源分配图.如果不能完全简化.就会死锁
③死锁检测中的数据结构
类似于银行家算法？？？

（2）死锁的解除
常用两种方法：抢占资源、终止/撤销进程
①终止进程的方法
终止所有死锁进程：会功亏一篑
逐个终止进程：找到代价最小.考虑优先级、已执行时间.还需的时间、已用资源、交互式还是批处理式
②付出代价最小的死锁解除算法
很不实际

第四章:存储器管理

存储器的层次结构

多层结构的存储系统

• 存储器的多层结构
  • CPU寄存器
  • 主存
  • 辅存
• 可执行存储器
  • 寄存器和主存的总称
  • 访问速度快，进程可以在很少的时钟周期内用一条load或store指令完成存取。

主存储器与寄存器

高速缓存和磁盘缓存

程序的装入和链接

步骤

• 编译
  • 源程序 -> 目标模块（Object modules）——–Compiler
    • 由编译程序对用户源程序进行编译，形成若干个目标模块
• 链接
  • 一组目标模块 -> 装入模块 （Load Module）———-Linker
    • 由链接程序将编译后形成的一组目标模板以及它们所需要的库函数链接在一起，形成一个完整的装入模块
• 装入
  • 装入模块 -> 内存 ——–Loader
    • 由装入程序将装入模块装入内存

程序的装入

• 绝对装入方式
  • 在编译时，如果知道程序将驻留在内存中指定的位置。编译程序将产生绝对地址的目标代码。
• 可重定位装入方式
  • 在可执行文件中，列出各个需要重定位的地址单元和相对地址值。当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换(一般在装入内存时由软件完成)。
  • 优点：不需硬件支持，可以装入有限多道程序。
  • 缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动。不易实现共享。
• 动态运行时的装入方式
  • 动态运行时的装入程序在把装入模块装入内存后，并不立即把装入模块中的逻辑地址转换为物理地址，而是把这种地址转换推迟到程序真正要执行时才进行
  • 优点：
    • OS可以将一个程序分散存放于不连续的内存空间，可以移动程序，有利用实现共享。
    • 能够支持程序执行中产生的地址引用，如指针变量（而不仅是生成可执行文件时的地址引用）。
  • 缺点：需要硬件支持，OS实现较复杂。
  • 它是虚拟存储的基础。

程序的链接

• 静态链接(Static Linking)方式(lib)
• 装入时动态链接(Load-time Dynamic Linking)
• 运行时动态链接(Runtime Dynamic Linking)(dll)

连续分配存储管理方式

单一连续分配(DOS)

固定分区分配

最早出现的方法，会浪费很多空间，划分分区方法

• 分区大小相等：缺乏灵活性，程序小浪费空间，程序大于分区导致无法运行。只适合于多个相同程序的并发执行（处理多个类型相同的对象）。
• 分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。
• 优点：无外碎片、易实现、开销小。
• 缺点：
  • 存在内碎片，造成浪费
  • 分区总数固定，限制了并发执行的程序数目。
  • 通用Os很少采用，部分控制系统中采用

动态分区分配

• 分区分配操作
  • 分配内存
  • 运行完成时回收内存

基于顺序搜索的动态分区分配算法

• 首次适应（firstfit, FF）算法
  • 顺序找，找到一个满足的就分配，但是可能存在浪费
  • 这种方法目的在于减少查找时间。
  • 空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序
• 循环首次适应（nextfit, NF）算法
  • 相对上面那种，不是顺序，类似哈希算法中左右交叉排序
  • 空闲分区分布得更均匀，查找开销小
  • 从上次找到的空闲区的下一个空闲区开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。
• 最佳适应（best fit, BF）算法
  • 找到最合适的，但是大区域的访问次数减少
  • 这种方法能使外碎片尽量小。
  • 空闲分区表（空闲区链）中的空闲分区要按大小从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。
• 最坏适应（worst fit, WF）算法
  • 相对于最好而言，找最大的区域下手，导致最大的区域可能很少，也造成许多碎片
  • 空闲分区按大小由大到小排序

基于索引搜索的动态分区分配算法

• 快速适应
• 伙伴系统
• 哈希算法

动态重定向分区分配

• 紧凑
• 动态重定位
  • 动态运行时装入，地址转化在指令执行时进行，需获得硬件地址变换机制的支持
  • 内存地址=相对地址+起始地址
• 动态重定位分区分配算法
  • 1、在某个分区被释放后立即进行紧凑，系统总是只有一个连续的分区而无碎片，此法很花费机时。
  • 2、当“请求分配模块”找不到足够大的自由分区分给用户时再进行紧凑，这样紧缩的次数比上种方法少得多，但管理复杂。采用此法的动态重定位分区分配算法框图如下：
• 优点：没有内碎片。
• 缺点：外碎片。

基址寄存器：程序的最小物理地址
界限寄存器：程序的逻辑地址范围
物理地址 = 逻辑地址 + 基址
内碎片：占用分区之内未被利用的空间
外碎片：占用分区之间难以利用的空闲分区（通常是小空闲分区）

对换(了解)

系统把所有的作业放在外存，每次只调用一个作业进入内存运行，当时间片用完时，将它调至外存后备队列上等待，在从后备队列调入另一个作业进入内存运行。

分页存储管理方式

分页存储管理的基本方式

• 页面
  • 将一个进程的逻辑地址空间分成若干个大小相等的片
• 页框（frame）
  • 内存空间分成与页面相同大小的存储块
• 由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”
• 地址结构
  • 页号P+位移量W(0-31)
• 页表
  • 在分页系统中，允许将进程的各个页离散地存储在内存在内存的任一物理块中，为保证进程仍然能够正确地运行，即能在内存中找到每一个页面所对应的物理块，系统又为每个进程建立了一张页面映像表，简称页表
  • 页表的作用是实现从页面号到物理块号的地址映射

地址变换机构

• 基本的地址变换机构
  • 要访问两次内存
  • 页表大都驻留在内存中
  • 为了实现地址变换功能，在系统中设置页表寄存器（PTR），用来存放页表的始址和页表的长度。
  • 在进程未执行时，每个进程对应的页表的始址和长度存放在进程的PCB中，当该进程被调度时，就将它们装入页表寄存器。
• 具有快表的地址变换机构
  • 提高了效率，此处会有计算题
  • 如果页表存放在内存中，则每次访问内存时，都要先访问内存中的页表，然后根据所形成的物理地址再访问内存。这样CPU存一个数据必须访问两次内存，从而使计算机的处理速度降低了1/2。
  • 为了提高地址变换的速度，在地址变换机构中增设了一个具有并行查询功能的特殊的高速缓冲存储器，称为“联想存储器”或“快表”，用以存放当前访问的那些页表项。
  • 地址变换过程为：
    1、CPU给出有效地址
    2、地址变换机构自动地将页号送入高速缓存，确定所需要的页是否在快表中。
    3、若是，则直接读出该页所对应的物理块号，送入物理地址寄存器；
    4、若快表中未找到对应的页表项，则需再访问内存中的页表
    5、找到后，把从页表中读出的页表项存入快表中的一个寄存器单元中，以取代一个旧的页表项。

两级和多级页表

• 主要是有的时候页表太多了，要化简
• 格式：外层页号P1+外层页内地址P2+页内地址d
• 基本方法：将页表进行分页，每个页面的大小与内存物理块的大小相同，并为它们进行编号，可以离散地将各个页面分别存放在不同的物理块中。

反置页表

• 反置页表为每一个物理块（页框）设置一个页表项，并按物理块排序，其内容则是页号和其所属进程的标识。

• 优点：

  • 没有外碎片，每个内碎片不超过页大小。
  • 一个程序不必连续存放。
  • 便于改变程序占用空间的大小。即随着程序运行而动态生成的数据增多，地址空间可相应增长。

• 缺点：程序全部装入内存。

分段存储管理方式

分段存储管理方式的引入

• 方便编程
• 信息共享
• 动态增长
• 动态链接

在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段是一组完整的逻辑信息，每个段都有自己的名字，都是从零开始编址的一段连续的地址空间，各段长度是不等的。
内存空间被动态的划分为若干个长度不相同的区域，称为物理段，每个物理段由起始地址和长度确定。

分段系统的基本原理

• 分段
  • 格式：段号+段内地址
• 段表
  • 段表实现了从逻辑段到物理内存区的映射。
• 地址变换机构

和分页的区别

• 页是信息的物理单位
• 页的大小固定且由系统固定
• 分页的用户程序地址空间是一维的
• 通常段比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。
• 分页是系统管理的需要，分段是用户应用的需要。一条指令或一个操作数可能会跨越两个页的分界处，而不会跨越两个段的分界处。

信息共享

这是分段最重要的优点，分页系统中对程序和数据的共享远不如分段系统方便

段页式存储管理方式

• 基本原理
  • 格式：段号（S）+段内页号（P）+页内地址（W）
• 地址变换过程
  • 需要三次访问过程
• 在段页式系统中，为了获得一条指令或数据，需三次访问内存：第一次访问内存中的段表，从中取得页表始址；第二次访问内存中的页表，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问才是真正根据所得的物理地址取出指令或数据。

课后题

可采用哪几种方式将程序装入内存？它们分别适用于何种场合？？

（1）绝对装入方式，当系统很小，仅能运行单道程序时，能知道程序驻留在内存的什么位置，可采用绝对装入方式
（2）可重定向装入方式，适用于多道程序
（3）动态运行时装入方式，适用于多道程序环境；不允许程序运行时在内存中移位置。

为什么要引入动态重定位？如何实现？

因为在程序执行过程中，每当访问指令或数据时，需要将要访问的程序或数据的逻辑地址转换成物理地址，所以引入了动态重定位；
具体实现方法是在系统中增加一个重定位寄存器，用来存放程序在内存中的起始地址，程序执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加之和，从而实现动态重定位。

分区存储管理中常用那些分配策略？比较它们的优缺点。

分区存储管理中的常用分配策略：首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法。
首次适应算法优缺点：保留了高址部分的大空闲区，为后来的大作业分配创造条件；低址部分不断被划分，留下许多难以利用的小空闲区，每次查找都从低址开始增加了系统查找空闲分区的开销。
循环首次适应算法优缺点：内存空闲分区分布均匀，减少了查找系统开销；缺乏大空闲分区，导致不能装入大型作业。
最佳适应算法优缺点：每次分配给文件的都是最适合该文件大小的分区，内存中留下许多难以利用的碎片空间。
最坏适应算法优缺点：剩下空闲区不太小，产生碎片的可能性最小，对中小型文件分配分区操作有利；存储器中缺乏大空闲区，对大型文件分区分配不利。

在以进程为单位进行对换时，每次是否都将整个进程换出？为什么？

在以进程为单位进行对换时，并非每次都将整个进程换出。因为：
(1)从结构上讲，进程由程序段、数据段和进程控制块组成的，其中进程控制块总有部分或全部常驻内存，不被换出。
(2)程序段和数据段可能正被若干进程共享，此时它们也不能换出。

在具有快表的段页式存储管理方式中，如何实现地址变换？

在CPU给出有效地址后，由地址变换机构自动将页号P送入高速缓冲寄存器，并将此页号与高速缓存中的所有页号比较，若找到匹配页号，表示要访问的页表项在快表中。可直接从快表读出该页对应物理块号，送到物理地址寄存器中。如快表中没有对应页表项，则再访问内存页表，找到后，把从页表项中读出物理块号送地址寄存器；同时修改快表，将此页表项存入快表。但若寄存器已满，则OS必须找到合适的页表项换出。

简答题

1、存储器的层次结构
（1）多层结构的存储器系统
CPU寄存器；
高速缓存Cache、主存储器RAM、磁盘缓存；
固定磁盘、可移动存储介质
（2）可执行存储器
就是CPU寄存器和主存.访问很快
（3）主存储器与寄存器
①主存储器
又叫主存or内存.相比CPU执行速度.它还是很慢.所以引入寄存器和高速缓存
②寄存器
完全与CPU协同工作.但好贵
（4）高速缓存和磁盘缓存
①高速缓存
备份主存中较常用的数据.以减少CPU对主存储器的访问次数
②磁盘缓存
因为磁盘I/O速度远低于主存访问速度.所以设置磁盘缓存来暂存频繁使用的一部分磁盘数据和信息

2、程序的装入和链接
用户程序要在OS中运行.要先装入内存.再转换为一个可执行程序：编译、链接、装入
（1）程序的装入
①绝对装入方式
当OS很小.且仅能运行单道程序时.完全有可能知道程序驻留在内存的位置.那么就可以产生绝对地址的目标代码
②可重定位装入方式（静态重定位）
多道程序下.逻辑地址和物理地址不同.要加上起始地址.但只在进程装入时一次完成.故称为静态重定位.可装到内存任何允许位置
③动态运行时的装入方式
需要重定位寄存器
（2）程序的链接
①静态链接方式
要解决：对相对地址进行修改（子程序的相对地址）、变换外部调用符号（生成可执行文件后不再拆开.又叫静态链接方式）
②装入时动态链接
便于修改和更新（各模块分开存放）、便于实现对目标模块的共享（静态每个应用模块必有目标模块的拷贝.无法共享.但动态可以一个目标链接多个应用模块）
③运行时动态链接
运行时发现没有.就由OS去找这个模块内功加快程序装入过程和节约大量内存空间

3、连续分配存储管理方式
（1）单一连续分配
分系统区和用户区.单用户.单任务操作系统
（2）固定分区分配
划分分区的方法：大小相等（一台计算机控制多台相同冶炼炉）和大小不等
内存分配：通常按大小排队.建立分区使用表.如果找不到大小足够的分区.就拒绝分配内存
（3）动态分区分配
动态分区分配中的数据结构
动态分区分配算法：之后介绍4种分配算法和3中索引搜索算法
分区分配操作：分配内存、回收内存
（4）基于顺序搜索的动态分区分配算法
首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法
（5）基于索引搜索的动态分区分配算法
快速适应算法、伙伴系统、哈希算法
（6）动态可重定位分区分配
紧凑、动态重定位、动态重定位分区分配算法

4、对换
（1）多道程序环境下的对换技术
①对换的引入
避免内存全部被阻塞.外存却有很多作业无法进入内存
②对换的类型
整体对换、页面对换
（2）对换空间的管理
①对换空间管理的主要目标
文件区管理主要目标：提高文件存储空间的利用率.提高对文件的访问速度
对换空间管理的主要目标：提高换入换出的速度
②对换区空闲盘块管理中的数据结构
与内存的相似
③对换空间的分配与回收
与内存分配和回收雷同
（3）进程的换出与换入
①进程的换出
选择被换出的进程
进程换出过程
②进程的换入
如果发现许多进程运行时缺页且内存紧张.才启动对换程序.将部分进程调至外存
如果缺页率明显减少.系统吞吐量已下降.则可以暂停运行对换程序

5、分页存储管理方式
其实分三种：分页、分段、段页式
（1）分页存储管理的基本方法
①页面和物理块
页面：页号
页面大小：太小.进程占用较多页面、太多.碎片多、适中.1kB~8kB
②地址结构
页号：P
页内地址（偏移量）：d
两个都有公式计算
③页表
从页号到物理块号的映射
（2）地址变换机构
①基本的地址变换机构
如果发现页号≥页表长度.就引发越界中断；否则页表始址+页号页表项长度=物理块号
②具有快表的地址变换机构
有个快表在高速缓存
（3）访问内存的有效时间
EAT = t +t = 2t
EAT = aλ+(t+λ)(1-a)+t = 2t+ λ - t* a
（4）两级和多级页表
①两级页表
②多级页表
（5）反置页表
①反置页表的引入
②地址变换

6、分段存储管理方式
（1）分段存储管理的基本方法
①方便编程
逻辑地址是由段名（段号）和段内偏移量（段内地址）决定的
②信息共享
段是信息的逻辑单位。简化共享过程
③信息保护
就是可以加个标识。不允许读写
④动态增长
可以解决这个问题
⑤动态链接
4.2.2
（2）分段系统的基本原理
①分段
每个段有一个段号
②段表
实现从逻辑段到物理内存区的映射
③地址变换机构
段表项数目比页表项数目少.其所需的联想存储器相对较少.减少存取数据的时间
④分页和分段的主要区别
页是信息的物理单位.分页是系统管理上的需要
while 段是存储管理方式中的逻辑单位.分段目的在于更好满足用户的需要
页大小固定.段大小不固定
分页的用户程序地址是一维的.分段是二维的
（3）信息共享
①分页系统中对程序和数据的共享
每个进程都有页表.也都指向相同的物理块号
②分段系统中的程序和数据的共享
可重入代码是一种不允许任何进程对它进行修改的代码
配以局部数据区.把执行中可能改变的部分拷贝到该数据区.这样执行时只需对该数据区中的内容修改即可
（4）段页式存储管理方式
分段→分页.每段一个段名
段号.比较.加法算段表段号→得到页号.(比较).加法算页表页号→得到物理块号.加页内地址→得物理地址