ACM通信
IT专业
Atlas的里程碑
图片来源:曼彻斯特大学
虚拟内存是一种计算机系统架构技术，它与计算机学术科学一样古老，并影响着许多计算机专业人士的职业生涯。我们借此机会将其作为计算领域的一个里程碑来庆祝，最近的IEEE里程碑奖被授予了曼彻斯特大学，它是1958年在这里发明的。
首先,一些背景。IEEE是世界上最大的技术协会，在160个国家拥有43万多名会员。IEEE里程碑项目成立于1983年，旨在表彰推动全球电气和电子行业发展的巨头们所取得的成就。每一个IEEE里程碑都会被安装在成就位置的铜匾所识别。IEEE网站列出了自1977年以来获得的224个里程碑，其中35个里程碑与计算有关。一个
2022年6月，两块具有里程碑意义的牌匾落成，一块为“曼彻斯特大学婴儿计算机及其衍生产品1948-1951”，一块为“阿特拉斯计算机和虚拟存储器的发明1957-1962”。后一个牌匾的图像出现在这里。
阿特拉斯计算机
Atlas架构(参见图1)合并了大量当时的新功能:异步流水线操作、并行算法、128个索引寄存器、索引寄存器的双地址修改、extracodes(模拟附加硬件指令的软件序列)、中断、交错的主核心存储、多编程，以及最重要的一级存储系统2这就是后来的虚拟内存。虚拟内存需要新的软件和硬件，这导致了一种名为Atlas Supervisor的操作系统的创建。3.该主管还包括一个Atlas Autocode的编译器，这是一种类似于Algol 60的高级语言。
图1。阿特拉斯的体系结构。
Atlas包含了多种存储，包括主存(磁芯)、辅存(旋转磁鼓)、固定存储(今天固件保存额外指令的前身)和V-Store(今天内存映射外设的前身)。需要这些不同类型的存储来优化CPU必须执行的不同存储访问任务。Atlas处理器(CPU)由累加器(称为a寄存器)及其相关的浮点算术单元、索引寄存器(称为b寄存器)和控制部分组成。
最初被称为一级存储，2Atlas虚拟内存系统通过在一个小而快速的主核心存储和一个大而慢得多的磁鼓之间自动传输代码和数据，给每个用户一种拥有一个非常大的主内存的错觉。在此之前，在早期的曼彻斯特机器上，程序员花了大量的时间用“叠加序列”来扩充基本算法——在辅助存储器上调用来将页面(标准大小的数据块)转移到有限的主存储器中。Kilburn相信单层存储机制将消除人工叠加，并估计程序员的工作效率将提高至多3倍。
Atlas允许每个程序通过一个20位的虚拟地址寻址1M个单词。然而，这产生了一个问题。吉尔伯恩写道2在通用高速数字计算机中，必须有一个大容量的快速访问主存储器。虽然把所有的存储器都设置为一种类型可以使计算机更有效地运行，但这一步骤对于现在正在考虑的存储容量来说几乎是不切实际的。例如，在Atlas上可以解决106字在主店。在实践中第一次安装在曼彻斯特大学共10个5游戏提供了单词，但尽管在一个关卡中创造单词在技术上是可行的，但提供一个核心存储(1.6万个单词)和一个鼓(9.6万个单词)的组合更经济。”
然而，事情远不止如此。在以前的机器中，页面传输是由程序员直接控制的。在Atlas中，磁鼓与处理器访问时间的比率约为2,700:1，b因此，为了避免在页面传输期间处理器长时间处于空闲状态，多个程序共同驻留在核心存储中对用户隐藏的位置。当一个程序停止进行页传输时，处理器切换到另一个驻留程序。Kilburn对这些问题的解决方案是让用户程序地址变成虚拟地址，并让计算机自己决定虚拟地址和真实地址之间的映射。实现这一概念的系统是操作系统软件和硬件的组合，称为分页。
很明显，从虚拟地址到真实地址的转换必须在硬件上完成，否则会有巨大的时间损失。此外，它只能移动信息块或页面，而不是单个单词，在鼓和核心存储之间。因此使用了一组关联(内容可寻址)寄存器，即Page Address寄存器(参见图2)．PAR保存在关联的内存页帧中加载的页的页码。为包含挂起作业页面的par设置锁定位。选择的页面大小为512个单词，核心store的16K个单词跨越了32个页面，因此需要32个par。因此，20位的虚拟地址被分为11位的页面地址和9位的行地址。页面地址同时呈现给所有的页面地址寄存器，在大多数情况下，其中一个寄存器将指示与所呈现的地址匹配。然后对par的输出进行编码，形成一个5位的页帧地址，该地址与9位的行地址连接，形成要发送到核心存储的真实地址。所有这些地址映射都是在内存周期的一小部分中完成的，对程序员来说是不可见的。
图2。页面地址寄存器。
如果没有PAR匹配，就会生成一个页面错误中断。操作系统的页面错误处理程序介入，找到了鼓上缺失的页面，将其移动到主存储的空白页帧中，然后用它现在包含的页码更新该帧的PAR。当所有这些都完成后，操作系统随后恢复中断的程序，该程序现在可以继续运行，因为它的最后一次内存访问现在映射到主存。在后来的虚拟内存中，不能提供足够的par来覆盖整个主存;PAR数组被替换为一个翻译后备缓冲区和一个页表。
Atlas一级商店被誉为计算机系统架构的重大突破，并很快被构建其他系统的工程师采用。
现在还有另一个问题需要处理:在内存中维护一个空白页帧，以便下一页错误有一个可用的帧来接收丢失的页。这是通过一种被称为“学习算法”的替代策略实现的。作为处理页面错误的一部分，操作系统将使用学习算法从其他31个页面中选择一个进行替换，并启动一个交换，将该页面复制回鼓。该学习算法是世界上第一个替代政策。
该学习算法假设程序的所有页面都包含在循环中。通过监视使用位，它可以测量使用和不使用的间隔，并计算每个页面循环的周期。然后，它选择替换在未来很长一段时间内不会被重用的页面。这个原则，今天被称为“MIN原则”，是最优的，如果确实所有页面都在固定循环中。这种假设并不总是符合的，并导致了1962年以后构建的虚拟内存的性能问题。我们将在下文中讨论这个问题。
虚拟内存性能
Atlas一级商店被誉为计算机系统架构的重大突破，并很快被构建其他系统的工程师采用。这些系统很快就遇到了两个重要的性能问题。其一，最好的替换算法往往需要大量的开销——Atlas“学习算法”就是这类算法——而开销低的算法会导致过多的分页。另一个问题是抖动，在多程序系统中，当加载的作业数量超过一个不可预测的阈值时，整个系统会意外崩溃。这些问题将虚拟内存的整个项目置于云之下。一台价值数百万美元的计算机如果因为寻呼而陷入困境，性能可能会不可预测地崩溃，这有什么好处呢?
在一项经典的研究(1966)中，IBM的Les Belady在各种工作负载下对大量可能的替代算法进行了测试。他总结说，几乎零开销的FIFO(先进先出)策略比其他大多数策略产生了更多的分页，而高开销的LRU(最近最少使用)通常优于其他大多数策略。他还测试了一种最优算法MIN，该算法提供了尽可能少的分页量，但不能实时实现，因为它需要未来的知识。他感到失望的是，包括LRU在内的大多数策略的性能都明显低于MIN。似乎没有希望看到性能接近最优的分页策略是可行的。
当这些基本算法扩展到多道编程时，操作系统需要为每个作业分配一个内存区域，例如，N乔布斯每人得到1/N的内存。如果N如果设置过高，所有作业都将被推入高分页状态，这意味着每个作业都不能非常频繁地使用CPU，并且随着作业“分页到死”，整体吞吐量会崩溃。没有办法确定门槛在哪里N是因为这取决于每项工作的细节。
1966年，工作集的概念取得了突破。1工作集是程序的内在内存需求—如果驻留，将生成非常低级别的分页。工作集是通过观察作业在最后一个向后查看窗口中访问了哪些页面来度量的T内存访问。多道编程的工作集策略为每个作业的工作集提供足够的页面。这意味着有一小部分称为FREE的内存未被使用。当出现页面错误时，工作集将从FREE中增加一个页面。当一名侍从不再是工作的一部分T-窗口，它将被驱逐，并返回免费。这样，就不会有页面错误从另一个工作集中窃取页面，从而影响它的性能。如果调度程序的工作集大于FREE，它就不会加载新作业。工作集策略不可能发生抖动。
利用局部性原理给出了性能难题的最后一块——最优吞吐量。这一原则认为，程序在相对较长的阶段中访问其地址空间的小子集，程序的整个执行可以描述为一系列阶段，其中每个阶段连续使用一组局部页面。如果操作系统能够检测局部集并加载它们，那么大多数作业在各个阶段几乎不会产生分页。大多数分页是由于向新的局部集的相对不频繁的相变造成的。证明这样的政策近乎最优并不困难——没有任何其他政策，包括那些具有前瞻性的政策，能够产生显著更高的吞吐量。1
工作集策略就是这样做的，因为工作集度量在它的时候看到的是精确的局部集T-window包含在一个阶段中。相同的局部集和相位在广泛的范围内被观察到T值。由工作集管理的本地化程序通常在1%-3%的最佳范围内运行。
现在很容易看到，虚拟内存和工作集管理是一个完美的团队，可以从虚拟内存中获得尽可能好的、无抖动的性能。
安全内核问题
有些人认为虚拟内存已经过时了，因为内存已经变得如此便宜，我们可以分配一个任务所需的所有实际内存。这样就没有分页，这种机制就变得多余了。
有些人认为虚拟内存已经过时了，因为内存已经变得如此便宜，我们可以分配一个任务所需的所有实际内存。
虽然大多数作业都可以完全加载到主存中，但这并不意味着虚拟内存就会消失。总有一些作业对于可用内存来说太大了。虚拟内存使得运行这样的作业成为可能。
然而，更重要的是，虚拟内存的地址映射保证了作业的完全隔离。作业只能访问链接到其页表的页帧，两个作业之间不能共享任何页帧。因此，任何作业都不能访问其他作业占用的内存。这种默认隔离是操作系统安全内核的基础。即使叠加问题不需要自动解决方案，虚拟地址映射提供的逻辑分区也是安全计算的基础。
吉尔本的发明是多么伟大的遗产啊。
数字图书馆是由计算机协会出版的。版权所有©2022 ACM股份有限公司
没有发现记录