作者： 小洛

虚拟存储系统的基本概念

实存管理技术特点
 在作业运行时，整个作业的逻辑地址空间必须全部装入主存；
 当作业尺寸大于主存可用空间时，该作业就无法运行。
虚拟存储器：一种实际上并不以物理形式存在的虚假的存储器；
把被运行进程访问的地址同主存的物理地址区别开来；
一个程序被编译连接后产生目标程序，该目标程序所限定的地址的集合称为逻辑地址空间，目标程序中指令和数据放置的位置称相对地址或逻辑地址；
而CPU能直接访问的主存称为物理地址空间或实存地址空间；

虚拟地址：运行进程访问的地址；
实地址：处理器可直接访问的主存地址；
虚拟地址空间：运行进程可以访问的虚地址的集合；
实地址空间：计算机的主存；
由动态地址映象机构来完成虚地址到实地址的转换；
虚实地址的区分，为使进程的虚拟地址空间大于主存实地址空间创造了条件，也为作业大小可大于主存空间创造了条件。

虚存管理技术

在虚拟存储系统中，用户认为机器具有无穷大的存储空间，并且只有这一个用户在使用机器；
用户只使用了物理主存的很少部分；
原因：操作系统内核只把进程当前要用的部分放在主存中，不仅能减少进程启动和滚进滚出的开销，而且主存中也可以同时容纳大量的进程，提高了系统多道程度和并行性；
代价：
主存管理要为地址转换表和其他一些数据结构付出额外的主存开销；
地址转换增加了每条指令的执行时间。
常用虚存管理技术
分页技术（paging）
分段技术（segmentation）
分段加分页技术（segmentation with paging）

分页系统中的地址映象技术

分页系统主要目的：让程序能在它的虚拟地址空间中运行并实现由虚拟地址到主存物理地址的转换；
几种地址转换方法
直接映象的页地址转换
多级页表的地址转换
反向页表的地址转换
快表的地址转换

直接映象的页地址转换

实现过程
当进程被调度到处理器上运行时，操作系统自动将该进程的页表起始地址装入页表地址寄存器中；
当该进程要访问某个虚地址时，分页的地址映象硬件自动按页面大小将地址场从某位起截成页号和页内地址两部分；
以页号为索引查找页表（查找工作由硬件自动进行），得到页架号，进而得到实际主存的绝对地址。
该映象技术对系统效能的影响
影响了处理器执行指令的速度，使速度降低为原来的一半；
原因：CPU至少要访问两次主存才能存取到所要数据，第一次查页表以找出对应的页架号，第二次真正访问所需数据。

多级页表的地址转换

因为大页表不能全放在主存中，所以对页表本身也采取分页措施，把页表本身按固定大小分成一个个页面；
通过二级页表的地址映射访问主存存取数据需要三次访问主存，所需时间是原来的三倍；
一次页目录
一次页表
数据所在的物理地址

反向页表的地址转换

实现过程
当给出进程的虚地址后，存储管理单元通过一个哈希定位表数据结构，把虚页号经哈希函数转换为一个哈希值；
以该哈希值为索引，它指向反向页表中的一个表目；
由该表目中的虚页号得到相应的页架号，再与偏移量拼接成物理地址，访问主存。

快表的地址转换

把一部分常用页表表目放入高速缓冲中，通过快表进行地址映射，快表中只包含一些最近使用的页表的表目；
快表的访问速度比主存的访问速度高一个数量级；
快表的表目中包含：虚页号以及该虚地址属于哪个进程、物理页架号、页面保护权限等。

当运行进程要访问虚地址v，于是硬件将地址v截成页号p和页内地址d；
地址转换机构首先以页号p和快表中各表目同时进行比较，以便确定该页是否在快表中；
 若在其中，则快表即送出相应的页架号与页内地址一起拼接成绝对地址，并按此地址访问主存；
 若该页不在快表中，则使用直接映象方法查找进程的页表，找出其页架号p’与页内地址拼接成绝对地址，并访问主存；同时将该页的页号及对应的页架号一起送入快表的空闲表目中去；若无空表目，通常把最先装入的那个页的有关信息淘汰掉，腾出表目位置。
实际上，直接映象和快表同时进行，当快表成功，就自动停止直接映象工作。

缺页中断处理流程

简单分页

前述固定分区和可变分区存储技术存在着一定的缺点；
分页技术思想的由来；
分页存储管理技术中的基本作法；
 等分主存；（页架、页框、帧）
 用户逻辑地址空间的分页；（页）
 逻辑地址的表示。（数对（p, d））
主存分配原则；
 分页情况下，系统以页架为单位把主存分给进程，分给一个进程的各页架不一定是相邻和连续的；
 页表—指出每个进程的各页放在主存的哪些页架中；
 分页系统中的地址结构—分为两部分；
 页面尺寸应是2的幂—可以省去除法运算，拆分地址场中的数即可。

地址转换过程：
首先将逻辑地址左边表示页号部分的页号抽取出来；
以页号作为索引查找该进程页表，找出该页存放的主存页架号；
用此页架号（二进制形式）取代逻辑地址的左边部分，并与右边的页内地址合并成相应的物理地址去访问主存。
简单分页方法的优点：
它基本没有页内碎片，只是在每个进程的最后一页中，会有页内碎片；也不会有小到不可再用的页外碎片，主存的利用率高；
不管采用哪种数据结构（空闲页架表、位图、空闲页架链表等），分配和释放存储都很快；
管理简单（类似于固定分区的情况）。

简单分段

为什么需要按段分配主存？
 事先将用户逻辑地址空间连接成一维线性地址空间，既费时又不便于作业的执行，尤其不便于共享；
 因此，人们希望按照程序模块来划分段，并按这些段来分配主存；
 段，就是一组逻辑信息的集合，如子程序、数组和数据区等。
分段存储管理的基本概念
进程的逻辑地址空间（二维的，用段名和段内地址两个成分来描述）
程序的地址结构
主存分配
段表（每个进程一个段表，用来指出进程的某段放在主存中的何处，以及该段的长度等信息）
段的地址转换（把逻辑地址左边段号部分提取出来，作为索引，查找进程的段表，将段内地址与段的长度比较，如果大于段的长度，则引起非法访问中断，即越界访问，如果访问合法，就将段的起始地址与段内地址相加，就得到所要访问的物理地址。）

简单分段的优点是没有段内碎片，只有外部碎片；
简单分段也是基于多重分区技术的进一步发展而来的；
简单分段对用户是可见的，而且分段需要用户提供支持，用户也需要知道系统的最大段长度限制；
当进程被交换出主存时，它的页表或段表也需随进程一起撤出主存。

分段和分页的比较

分段是信息的逻辑单位，由源程序的逻辑结构所决定，用户可见，段长可根据用户需要来规定，段起始地址可以从任何主存地址开始；在分段方式中，源程序(段号，段内位移)经连结装配后仍保持二维结构。

分页是信息的物理单位，与源程序的逻辑结构无关，用户不可见，页长由系统确定，页面只能以页大小的整倍数地址开始。在分页方式中，源程序(页号，页内位移)经连结装配后变成了一维结构。

固定分区存储管理

把主存分成若干个固定大小的存储区（又称存储块），每个存储区分给某一个作业使用，直到该作业完成后才把该存储区归还系统；
分单道作业和多道作业两种情况；
 单用户、单道作业情况
 多道作业情况
• 操作系统区、用户使用的分区；
• 主存中分区的区数是固定不变的，每区的大小也是固定不变的；
• 分给每个作业一块大于或等于作业大小的主存分区，不允许两个作业同时放于同一个分区中；
• 问题：分区中常有未用的、剩下的空闲部分，即存储碎片，降低了主存的利用率；
• 存储分块表：主存分区情况说明信息，存储区的使用状况信息，包括大小、位置和状态三项信息。

存储分块表
大小：指出该存储块的大小，以字节为单位；
位置：指出该存储块在主存中的起始地址；
状态：表明该存储块是否已被使用。
存储保护功能
一对“界地址寄存器”，如果处理器要访问主存某单元时，系统硬件自动将该单元地址与界限寄存器的内容进行比较，以判断此次访问是否合法。
优点：简单，要求的硬件支持只是一对界地址寄存器，软件算法简单；
缺点：主存利用率不高。

可变分区存储管理

所谓可变分区，是指主存事先并未划分成一块块分区，而是在作业进入主存时，按该作业的大小建立分区，分给作业使用；
特点：
分区个数是可变的，每个分区的大小也是不固定的；
主存中分布着个数和大小都是变化的空闲分区或碎片，这些空闲分区有些可能
相当大，而有些则相当小。

数据结构的组织方法

存储分块表
 这种存储分块表存在两个缺点：
• 由于分区个数是变化的，所以表长不好确定，造成表格管理上的困难，若给该表留的空间不足，又无法登记各分区的情况，若留的空间过大，造成浪费；
• 分配主存时，为查找一块合适的空闲分区所需扫描的表目增加了，查找速度变慢了。
分开设置两个存储管理表
 用已使用分区表（UBT）和空闲分区表（FBT）分别登记和管理系统中的已分分区和空闲分区；
减少存储分配和释放时查找表格的长度，提高查找速度。
空闲存储块链
使用链指针把所有的空闲分区链结在一起，构成一条空闲存储块链；
实现方法：把每个空闲存储块的起始若干个字节分成两部分，前一部分作为链指针，指向下一空闲存储块的起始地址，后一部分指出本空闲存储块的大小，用一固定单元作为空闲存储链的头指针用以指出该链中的第一块空闲存储块的起始地址，最后一块空闲存储块的链指针中放着链尾标志；
这种方法使得数据基的管理和维护比较简单。

存储分配算法

最佳适应法
从所有未分配的分区中挑选一个最接近作业尺寸且大于或等于作业大小的分区分给要求的作业；
尽量多保留大的分区，使被选中分区剩下尽可能小的未用碎片；
使系统中产生了许多小得无法再用的碎片。
最先适应法
按分区序号从存储分块表的第一个表目起查找该表，把最先找到的且大于或等于作业大小的未分配分区分给要求的作业；
尽可能地缩短了存储分配时间；
对空闲块的管理采取不同的办法：表格法、空闲存储块链法、位图法。
最坏适应法
从所有未分配的分区中挑选最大的且大于或等于作业大小的分区分给要求的作业；
可用于可变分区分配技术中。
保证分配后剩下的分区足够大，以便满足后续要求。

碎片问题和存储器的紧缩

由于各作业请求和释放主存块的结果，产生很多小的碎片，碎片的存在降低了多
道的程度，造成了主存空间的大量浪费；

解决碎片问题：
 把程序分成几部分装入不同的分区中去，改变一直把程序作为一个连续的整体在主存中存放的要求；
• 改善了碎片问题，但却增加了程度管理和执行的复杂性；
 把小碎片集中起来使之成为一个大分区；
• 移动各用户分区中的程序，使它们集中于主存的一端，使碎片集中于另一端，从而连成一个完整的大分区，即存储器的“紧缩”或“澄清”。

动态重定位

动态重定位：是指程序的重定位时机不是在程序执行前进行，而是在程序执行过程中才进行
地址转换，更确切地说是在每次访问主存单元前才进行地址转换；
重定位过程：
首先将用户按相对地址编址的目标程序原封不动地装入主存中分给该用户使用的分区中；
当该用户程序被调度到处理器上执行时，操作系统自动将该用户作业的起址由作业表中取出，并将分区起始地址减去用户目标程序的相对基地址，然后将其减得值装入定位寄存器中；
当处理器要访问主存时，地址转换硬件自动将程序中的相对地址与定位寄存器中的内容相加，并按相加的和作为主存绝对地址去访问数据。

采用动态重定位后，由于目标程序装入主存后不需要修改地址指针及所有与地址有关的项，因而程序可在主存中随意浮动而不影响其正确执行，从而可以方便地进行存储器紧缩，较好地解决了碎片问题。

多重分区/多对界地址管理

单对界地址管理技术：
每个用户只占据主存的一个分区，存储保护只需使用一对界地址寄存器；
弊病：
• 首先，解决碎片问题时，移动程序进行存储器紧缩时需要硬件支持；
• 其次，不便于在进程之间共享数据。

多对界地址管理技术：
系统中设置多对界地址寄存器，并且在为每个作业或进程分配主存时，可按界地址寄存器对的个数为其分配多个不相邻接的空闲分区；
该技术既可以改善碎片情况，又便于共享；
但是，在实存管理技术中，多重分区的多重程度不宜过多，否则会增加管理的复杂性。

计算机系统存储器层次

主存储器管理功能

主存分配
 可以使多个程序同时驻留在主存中，以提高CPU利用率；
 保证系统的高性能，提高存储利用率和主存的分配和释放(回收)速度，以加快任务的执行。
地址转换和重定位
 程序不必事先约定存放地址，可在执行过程中移动；
 可以运行只装入了一部分的程序，缩短程序的启动时间；
 研究和使用各种有效的地址转换技术以及相应的地址转换机构。
存储保护和主存共享
 如何保护各存储区中信息不被破坏和偷窃；
 由于许多不同的任务可能要执行同一个程序，进程中多个合作进程要访问相同的数据结构，所以存储保护机制要提供进程对某些主存区共享的灵活性。
存储扩充
 使用有效的存储管理技术来实现逻辑上的扩充——即虚拟存储技术；
 运行的程序应不受主存大小的限制，理想情况下应能运行任意大小的程序。

地址映射

首先，在多用户共享主存时，需要由系统分配主存；
一般情况下，一个作业程序分配到的存储空间和它的地址空间是不一致的；
因此作业的相应进程在处理器上运行时，所要访问的指令和数据的实际地址和地址空间中的地址是不同的；
所以，处理器在执行指令时，必须把逻辑地址转换为绝对地址后，方能访问信息。

地址映射方式

编程或编译时确定地址映射关系
 如果虚——实地址间的对应关系是在程序编写或者程序编译时实现的，则结果为一个不能浮动的程序模块，它必须被放在主存某一确定的地址中，而且永不会改变，因为它所包含的全部地址都是主存地址，在这种情况下，把这样一个程序装入主存，就必须在申请主存时，具体地提出申请的主存容量和主存地址，因此主存分配程序在分配时将没有什么活动余地。
静态地址映射
动态地址映射

单种资源的银行家算法

问题：研究一个银行家如何将其总数一定的现金，安全地借给若干个顾客，使这些顾客既能满足对资金的要求又能完成其交易，也使银行家可以收回自己的全部现金不至于破产。
操作系统在若干个并行进程间分配单位数量一定的某共享资源就是这样一个问题，既要使每个进程均能满足其对资源的要求，使之完成其运行任务，同时又要使整个系统不会产生死锁。
假如银行家能使他当前的全部顾客在有限的时间内完成他们的交易（也归还了他们的借款），那么当前的状态是安全的，反之状态就是不安全的。

多种资源的银行家算法

定义两个向量和两个矩阵：
 系统资源向量：表示系统中拥有每类资源的数量；
 系统当前可用资源向量：表示系统中尚未分给进程的每类资源的数量；
 各进程当前对资源的请求矩阵；
 当前资源分配矩阵。

即，如果将所有已被指派的资源j的数量和所有可供使用的资源数相加，结果就获得该类资源的总数。

死锁模型—有向图

可通过画有向图来判断是否发生了死锁

从死锁恢复

剥夺法恢复
 将某一资源从一个进程强占过来给另一个进程使用，并在不影响原进程执行的情况下返回，这种作法取决于该资源的特性；
 用这种方法恢复通常比较困难或者说不太可能，因为选择中止某进程很大程度上取决于哪一类资源比较容易被收回；

回退法恢复
 系统设计人员以及主机操作员周期性地对进程进行检查，在检查点将进程的状态写入文件以备重启，文件中不仅包括内存图象，还包括了资源状态，既哪些资源对应哪些进程；
 一旦检测到死锁，恢复时，进程会回滚到较早的检查点，该检查点后做的所有工作都丢失了；

杀死进程来恢复
 杀掉环中的一个进程；
 将一个环外的进程作为牺牲品放入环中以释放被死锁的资源。

防止死锁的发生

防止死锁的发生，根本办法是使必要条件之一（或多个条件）永不存在，即破坏其必要条件使之永不成立，如果有一条或若干条不具备，那么死锁就不会产生；
 破坏互斥条件，允许多个进程同时访问资源；（但不太实际）
 破坏不可抢占条件，强迫进程暂时把资源释放出来给其他进程；（考虑到资源在进程间转移的开销和对资源的有效利用，必须小心地控制破坏该条件）
 破坏部分分配条件；
 破坏循环等待条件。

预先静态分配法

是针对部分分配条件的策略；
在进程开始运行前，一次分配给其所需的全部资源，若系统不能满足，则进程阻塞，直到系统满足其要求；
将导致严重的资源浪费；
改进策略：把程序分成几个相对独立的“程序步”来运行，并且资源分配以程序步为单位来进行，而不以整个进程为单位来静态地分配资源；
可以得到较好的资源利用率，减少资源浪费，但增加了应用系统的设计和执行的开销；
而且，为满足一个进程所需的全部资源，要逐渐积累，造成资源的浪费。

有序资源使用法

针对循环等待条件的；
系统设计者把系统中所有资源类都分给一个唯一的序号，并且要求每个进程均应严格按照递增的次序请求资源；
这样，系统中不可能形成几个进程对资源的环行请求链，破坏了循环等待条件；
把各进程经常用到的、比较普通的资源安排成低序号，而把比较贵重或稀少的资源安排成高序号，可能使最有价值的资源的利用率大为提高，但也有可能造成低序号资源的空闲等待浪费现象；
存在的问题：
 各类设备的资源序号一经安排，不宜经常地随意加以改动，至少应该维持一个较长的时期，在此期间，若要添置一些新设备，就必须重新改写已经存在的程序和系统；
 资源序号的安排要反映大多数进程实际使用资源的正常顺序，对于与此序号相匹配的进程，资源能得到有效利用，否则，资源浪费现象虽然有所改善，但仍然存在。

死锁：在系统中的一组进程，由于竞争系统资源或由于彼此通信而永远阻塞，称
这些进程处于死锁状态；

资源

资源：分可抢占资源和不可抢占资源
可抢占资源是指虽然资源占有者进程任然需要使用该资源，但另一个进程却可以强行把资源从占有者进程处抢过来，归自己使用
不可抢占资源是指除非资源占有者进程不再需要使用该资源而主动释放资源，否则其他进程不得在占有进程使用资源的过程中强行抢占
一个资源是否属于可抢占的资源，完全依赖于资源的属性
CPU、主存属于可抢占资源
打印机、读卡器等资源属于不可抢占资源

死锁的必要条件

互斥条件：一个资源一次只能被一个进程所使用；
不可抢占条件：一个资源仅能被占有它的进程所释放，而不能被别的进程强行抢占；
请求又保持（部分分配）条件：一个进程已占有了分给它的资源，但仍然要求其他资源；
循环等待条件：在系统中存在一个由若干进程形成的环形请求链，其中的每一个进程均占有若干种资源中的某一种，同时每一个进程还要求（链上）下一个进程所占有的资源。

调度的层次

长期调度（又称作业调度）：主要功能是按照某种原则从磁盘某些盘区的作业队列和交互作业中选取作业进入主存，并为作业做好运行前的准备工作和作业完成后的善后工作。
中期调度：决定哪些进程被允许参与竞争处理器资源；
主要起到短期调整系统负荷的作用，以平顺系统的操作。
短期调度（又称处理器调度）：主要功能是按照某种原则将处理器分配给就绪进程或线程。

作业状态

作业在每一阶段中所处的状况称为作业的状态；
系统中的作业通常分为四种状态：
 提交状态（动态的，作业录入，提交给系统）
 后备状态（静态的，提交完成）
 运行状态（动态的，从后备队列挑选运行）
 完成状态（静态的，运行完成后）

作业状态及其转换

作业的调度

按照某种调度算法从后备队列中挑选作业进入主存中运行
作业调度程序
作业调度程序要完成以下工作：
 按照某种调度算法从后备作业队列中挑选作业；
 为选中的作业分配主存和外设资源；（前期准备工作）
 为选中的作业建立相应的进程；（前期准备工作）
 构造和填写作业运行时所需的有关表格；（前期准备工作）
 作业结束时完成该作业的善后处理工作，如收回资源，输出必要的信息，撤消该作业的全部进程和作业控制块。
通常在一个作业完成或处理器空闲时调入一个或多个作业。

作业控制块（ JCB ）

• 作业名：由用户提供，经系统登记在JCB中；
• 估计执行时间：指作业完成计算所需的时间，由用户根据经验估计的；
• 最迟完成时间：用户要求完成该作业的截止时间；
• 要求的主存量：该作业执行时所需占用的主存数量；
• 外设类型及台数：指作业执行时所需的外设类型及每类设备的台数；
• 要求的文件量和输出量：指本作业将存储在文件空间的文件信息总量，和将输出数据的总量；
• 进入系统时间：该作业的全部信息进入主存，其状态转变为后备状态的时间；
• 开始执行时间：该作业被作业调度程序选中，其状态由后备状态转变为执行状态的时间；
• 主存地址：指分配给该作业的主存区开始地址；
• 外设台号：分配给该作业的外设实际台号；
• 控制方式：有联机和脱机两种；
• 作业类型：指系统根据作业运行特性所规定的类型，可分三类：占CPU时间偏多的作业、I/O量偏大的作业以及使用CPU和I/O比较均衡的作业；
• 优先级：反映这个作业运行的紧急程度，可由用户自己指定，也可由系统根据作业类型、要求的资源、要求的运行时间与系统当前状况动态地给定；
• 状态：指本作业当前所处的状态，它可为后备状态、执行状态或完成状态中的任一种状态。
• 作业运行结束后，在释放了该作业所使用的全部资源后，作业调度程序调用存储管理程序，收回该作业的JCB空间，从而撤消了该作业。

单机系统的处理器调度

调度算法
先进先出调度算法
优先级调度算法——非抢占的、可抢占的
时间片轮转算法
最短进程优先调度算法
最短剩余时间优先调度算法
最高响应比优先调度算法
多级反馈队列调度算法

#假设处理完前处理器资源不会被剥夺 #假设单处理器

调度性能的衡量

通常采用平均周转时间和平均带权周转时间来衡量作业调度算法性能的好坏
周转时间：从作业提交完成到完成所经历的事件（运行时间+等待时间）
带权周转时间：周转时间除以执行时间

先进先出调度算法

按作业来到的先后次序进行调度，优先考虑在系统中等待时间最长的作业，而不管它要求执行时间的长短；
算法容易实现，但效率较低
对短作业不利，因为短作业执行时间很短，若令它等待较长时间，则带权周转时间会很高。

最短作业优先调度算法

按作业执行时间长短调度，优先考虑作业预期执行之间的长短
对先来的长作业不利

最高响应比优先调度算法

先进先出调度算法只考虑作业的等候时间而忽略了作业的执行时间；
最短作业优先调度算法只考虑用户估计的作业执行时间而忽略了作业的等待时间；
最高响应比优先调度算法是介于上述两算法之间的一种折衷算法，既照顾了短作业，又不使长作业的等待时间过长。