描述了一种多道程序设计系统，其中所有活动被划分为多个顺序过程。

这些顺序过程被放置在不同的层次结构级别，在每个层次结构级别中都实现了一个或多个独立的抽象。分层结构被证明对于验证设计的逻辑合理性及其实现的正确性至关重要。

关键词和短语：操作系统、多编程系统、系统层次结构、系统结构、实时调试、程序验证、同步原语、协作顺序进程、系统级别、输入输出缓冲、多编程、处理器共享、多处理

引言

为了响应明确要求“及时研究和开发工作”论文的号召，我提交了一份关于Eindhoven理工大学数学系多道程序设计工作的进度报告。

由于资源非常有限（即平均有六个人的时间可用性），并且希望为系统设计艺术做出贡献——包括构思、构建和验证的所有阶段——我们面临着如何获得必要经验的问题。为了解决这个问题，我们采用了以下三个指导原则：

（1）选择一个能想到的最先进的、能证明的最雄心勃勃的项目，希望把日常工作保持在最低限度；坚持反对所有压力，将这种系统扩展纳入其中，只会导致要完成的工作总量的纯粹数量增加。

（2） 选择具有良好基本特性的机器（例如，一个让人爱不释手的中断系统肯定是 一个鼓舞人心的功能）；从那时起，尽可能长时间地将系统预配配置的特定属性排除在考虑范围之外。

（3） 要意识到，经验绝不会自动导致智慧和理解；换言之，有意识地努力尽可能多地学习以前的经验。

因此，我将努力超越仅仅报告我们所做的和如何做的，我也将努力阐述我们所学到的。

为了完整起见，我想以两个简短的关于工作条件的评论来结束介绍。我不再强调这些问题。

有一种说法是，如果一个人与同时承担其他义务的兼职员工一起工作，生产速度就会严重放缓。这至少是四分之一；可能情况更糟。人们自己在转换中失去了时间和精力；整个团队失去了决策的速度，因为在需要时，讨论往往不得不推迟到所有相关人员都可以参加。

另一种说法是，该小组的成员（大多数是数学家）以前曾作为优秀学生接受过五到八年的大学培训，并且是硕士或博士水平。我明确提到这一点，因为至少我国总体上严重低估了系统设计所需的智力水平。我比以往任何时候都更加确信，这类工作非常困难，与最优秀的人以外的人一起做这项工作的每一次努力都注定会失败或以巨大的代价获得适度的成功。

工具和目标该系统是为Dutch机器EL X8（N.V.Electrologica，Rijswijk（ZH））设计的。我们的配置的特点是：

（1）核心存储器周期时间2.5usec，27位；目前为32K；

（2） 512K字的磁鼓，每磁道1024字，rev。时间40msec；

（3） 非常适合堆栈实现的间接寻址机制；

（4） 用于命令外围设备和控制中断的声音系统；

（5） 潜在的大量低容量通道；使用了其中10台（3台纸带阅读器，1000字符/秒；3台纸带冲床，150字符/秒，2台电传打印机；1台绘图仪；1台行式打印机）；

（6） 缺少一些不寻常、尴尬的特征。

该系统的主要目标是平稳地处理连续的用户程序流，为大学提供服务。选择多程序系统的目的如下：（1）缩短短时间程序的周转时间；（2）外围设备的经济使用；（3）自动控制将后备存储器与中央处理器的经济使用相结合，以及（4）将机器用于那些只需要通用计算机的灵活性，但（通常）不需要容量或处理能力的应用的经济可行性。

该系统不是一个多用户系统。独立用户之间没有通用的数据库进行通信：他们只共享配置和过程库（其中包括一个用复数扩展的ALGOL 60的翻译器）。系统不支持用机器语言编写的用户程序。

与更大的努力相比，我们可以说，量化的目标设定得与设备和其他资源一样温和。我担心，定性地说，随着工作的进展，我们变得越来越不谦虚。

进度报告

我们犯了一些常见的小错误（例如过于注重消除不是真正的瓶颈）和两个主要错误。

我们的第一个主要错误是，在很长一段时间里，我们将注意力集中在“完美安装”上；当我们考虑如何充分利用它时，一个外围设备出现故障，我们面临着严重的问题“比我们预想的要耗费更多的精力，而我们的一些麻烦是我们早期独创性的直接后果，即系统本可以自行处理的复杂情况。如果我们在设计的早期阶段就注意到了病理学，我们的管理规则肯定不会那么完善。”。

第二个主要错误是，我们构思并编程了系统的主要部分，而没有充分考虑对其进行调试的问题。我必须拒绝承认这一错误没有造成严重后果——相反！人们可能会认为这是事后的想法。

作为机组队长，我在制作处理实时中断的基本软件方面有着丰富的经验（可追溯到1958年），我从惨痛的经验中知道，由于中断时刻的不可再现性，程序错误可能会像偶尔的机器故障一样误导人。结果我非常害怕。由于担心调试的可能性，我们决定尽可能小心，预防胜于治疗，尽量防止讨厌的bug进入施工。

这一决定受到恐惧的启发，是我认为该组织对系统设计艺术的主要贡献的最底层。我们已经发现，设计一个完善的多道程序设计系统是可能的，它的逻辑可靠性可以被先验地证明，它的实现可以允许进行详尽的测试。测试过程中出现的唯一错误是微小的编码错误（每500条指令出现一个错误），每一个错误都位于机器10分钟（经典）检查范围内，并且每个错误都很容易纠正。在编写这篇文章时，测试还没有完成，但最终的系统保证是完美的。当系统交付时，我们不会永远担心系统脱轨仍可能在不太可能的情况下发生，例如可能由两个或多个关键事件的不幸“巧合”导致，因为我们将以严格和明确的方式证明系统的正确性，这在绝大多数数学证明中是不常见的。

系统结构概述

存储分配。在经典的yon Neumann机器中，信息由包含信息的存储位置的地址来标识。当我们开始考虑辅助存储的自动控制时，我们熟悉一个系统（即GmR ALGOL），其中所有信息都由其磁drum地址标识（如在经典的yon Neumann机器中），其中核心存储器的功能无非是使信息“逐页”可访问。

我们采用了另一种方法，结果证明，这是非常有利的。在我们的术语中，我们严格区分了存储单元（我们称之为“页面”，有“核心页面”和“drum页面”）和相应的信息单元（因为缺少更好的词，我们称其为“片段”），一个正好适合页面的片段。对于段，我们创建了一个完全独立的识别机制，其中可能的段标识符的数量远远大于主存储和辅助存储中的页面总数。段标识符提供了对核心中所谓“段变量”的快速访问，该变量的值表示段是否仍然为空，如果不是空，则可以在哪个页面中找到它。

作为这种方法的结果，如果必须将驻留在核心页中的信息段转储到drum上以使核心页可用于其他用途，则无需将该段返回到其最初来自的相同drum页。事实上，这种自由被利用了：在空闲的drum页面中，选择了具有最小延迟时间的鼓页面。

下一个后果是完全不存在drum分配问题：例如，一个程序应该占用连续的drum页面，这是没有任何原因的。在多道程序设计环境中，这非常方便。

处理器分配。我们已经充分认识到这样一个事实，即在一个单一的顺序过程中（例如，由顺序自动机执行），只有各种状态的时间序列具有逻辑意义，而不是执行顺序过程的实际速度。因此，我们将整个系统安排为一个连续过程的社会，以未定义的速度比前进。系统接受的每个用户程序对应一个顺序过程，每个输入外围设备对应一个连续过程（与输入命令的执行同步地缓冲输入流），每个输出外围设备对应顺序过程（与输出命令的执行同时地解缓冲输出流）；此外，我们还有与鼓相关的“段控制器”和与控制台键盘相关的“消息解释器”。

这使我们能够根据这些抽象的“顺序过程”来设计整个系统。它们的和谐合作是通过明确的相互同步声明来调节的。一方面，这种明显的相互同步是必要的，因为我们没有对速比进行任何假设；另一方面，这种相互同步是可能的，因为“暂时延迟进程的进程”永远不会对延迟的进程的内部逻辑有害。这种方法的基本结果——即明确的相互同步——是一组这样的连续过程的和谐合作可以通过离散推理来建立；因此，如果可用的处理器可以从一个过程切换到另一个过程，那么协作顺序过程的整个和谐社会与可用于执行这些过程的处理器的实际数量无关。

系统层次结构。整个系统允许严格的等级结构。

在0级，我们发现处理器分配给逻辑上允许动态进度的进程之一的责任（即，考虑到显式相互同步）。在这个级别上，实时时钟的中断被处理并引入，以防止任何进程垄断处理能力。在这一级别上，纳入了优先规则，以在需要时实现系统的快速响应。我们的第一个抽象已经实现；在0级以上，实际共享的处理器数量不再相关。在更高的层次上，我们发现不同顺序进程的活动，实际的处理器已经失去了它的身份，从图片中消失了。

在第1级，我们有所谓的“段控制器”，这是一个与鼓中断和更高级别上的顺序过程同步的顺序过程。在第1级，我们发现有责任满足自动备份存储产生的记账。在这个层次上，我们的下一个抽象已经实现；在所有更高级别上，信息的识别都是以片段的形式进行的，丢失了身份的实际存储页面已经从图片中消失。

在第2级，我们发现“消息解释器”负责控制台键盘的分配，通过该键盘可以执行操作员与任何更高级别进程之间的对话。消息解释器与操作员密切同步工作。当操作员按下一个键时，一个字符与一个中断信号一起发送到机器，以通知下一个键盘字符，而实际的打印是通过机器在消息解释器的控制下生成的输出命令完成的。（就硬件而言，控制台电传打印机被视为两个独立的外围设备：一个输入键盘和一个输出打印机。）如果其中一个进程打开了一个对话，它会在对话的开头句子中标识自己，以利于操作员。然而，如果操作员打开对话，他必须在对话的开头句子中识别他正在处理的过程，即，在知道对话要处理哪个过程之前，必须先解释这个开头句子！这里是为控制台电传打印机引入单独的顺序过程的逻辑原因，这一原因反映在其名称“消息解释器”中。

在级别2之上，每个进程都有自己的会话控制台。它们共享同一个物理控制台的事实被转化为“一次只能进行一次会话”的资源限制，这种限制通过相互同步来满足。在这个级别上，下一个抽象已经实现；在更高的级别，实际的控制台电传打印机失去了它的身份。

（如果消息解释器没有处于比段控制器更高的级别，那么实现它的唯一方法就是在核心中为其进行永久性保留；由于会话词汇可能会变大（一旦我们的操作员希望在花式消息中进行寻址），这将导致对核心存储的永久性需求过大。因此，表示消息的词汇表存储在段上，即作为也可以驻留在鼓上的信息单元。因此，消息解释器比段控制器高一级。）在第3级，我们发现与输入流缓冲和输出流解缓冲相关的顺序过程。在这个级别上，下一个抽象是有效的，即在这个级别分配给“逻辑通信单元”的实际使用的外围设备的抽象，根据这些逻辑通信单元在更高的级别上工作。与外围设备相关的顺序进程的级别高于消息解释器，因为它们必须能够与操作员对话（例如，在检测到故障的情况下）。有限数量的外围设备再次充当资源限制，使更高级别的进程能够通过它们之间的相互同步来满足。

在第4级，我们找到了独立的：用户程序，在第5级，我们发现了操作员（我们没有实现）。

系统结构已经详细描述，以便使下一节变得易懂。

设计经验

构思阶段花费了很长时间。在这段时间里，我们在上一节中概述了系统的概念。此外，我们还学习了推理的艺术，通过这种艺术，我们可以从需求中推断出流程应该通过其实际同步相互影响的方式，从而满足这些需求。（要求是在产生信息之前不能使用信息，外围设备不能同时设置为两个任务，等等）。最后，我们学会了推理的艺术，通过这种艺术，我们可以证明由相互同步的过程组成的社会在其时间行为中确实满足所有要求。

构建阶段相当传统，甚至可能是老式的，即简单的机器代码。由于规格变化而重新编程的情况很少见，这种情况肯定对“蒸汽法”的可行性起到了很大的作用。前两个阶段所花费的时间比计划的要长，这在某种程度上是由于机器交付的延迟所弥补的。

在验证阶段，我们让机器在短时间内完全可以使用；这些照片是我们在没有任何调试软件帮助的情况下使用一台机器的照片。从0级开始，系统进行测试，每次添加（一部分）下一级时，只有在前一级经过彻底测试之后。每个测试镜头本身都包含在要测试的（部分）系统之上的多个具有双重功能的测试过程。首先，他们必须迫使系统进入所有不同的相关状态；其次，他们必须验证系统是否继续按照规范做出反应。

我不会否认，这些测试程序的构建是一项重大的智力努力：说服自己没有忽视“相关状态”，并说服自己测试程序生成所有这些都不是简单的事情。令人鼓舞的是（据我们所知）这是可以做到的。

这一事实是等级结构带来的快乐后果之一。

测试级别0（实时时钟和处理器分配）意味着在它上面有许多测试顺序进程，一起检查在任何情况下处理器时间都是按照规则分配的。这是建立起来的，实施了连续的过程。

在第1级测试段控制器意味着所有“相关状态”都可以按照对核心页面产生（各种组合）需求的顺序过程来制定，这些情况可能由测试程序之间的显式同步引起。

在这个阶段，实时时钟的存在——尽管一直在中断——是如此的无关紧要，以至于一位测试人员确实忘记了它的存在！到那时，我们已经对来自实时时钟和磁鼓的（相互不同步的）中断执行了正确的反应。如果我们没有引入单独的0级和1级，如果我们没有创建一种可以丢弃时钟中断的存在的内部结构（即相当抽象的顺序过程），而是尝试采用非层次结构，使中央处理器直接对这两个中断的任何奇怪的时间序列做出反应，“相关州”的数量会激增，达到一个高度，彻底的测试将是一种幻觉。（除此之外，我们是否有能力将它们全部生成，鼓和钟的速度超出了我们的控制范围，这是值得怀疑的。）

为了完整起见，我必须提到一个更令人高兴的结果。如前所述，在级别1以上，核心和鼓页面已经失去了它们的身份，因此输入和输出流的缓冲（在级别3）以段的形式出现。在2级或3级测试时，鼓轮通道硬件故障了一段时间，但测试通过将段的数量限制在核心中可以容纳的数量来进行。如果建立行式打印机输出流被实现为“转储到滚筒上”，而实际打印被实现为从滚筒上打印”，那么我们将失去这一优势。

结论

就程序验证而言，我没有提出任何实质性的新内容。在测试一个通用对象（无论是一块硬件、一个程序、一台机器或一个系统）时，我们不能将其置于所有可能的情况下：对于计算机来说，这意味着我们向它提供所有可能的程序！因此，必须使用一组相关的测试用例对其进行测试。只要人们将机制视为一个黑匣子，就无法决定什么是相关的，什么是不相关的；换句话说，决策必须基于待测试机制的内部结构。设计师似乎有责任以这样一种方式构建自己的机制。e、 如此有效的结构化——在测试过程的每个阶段，相关测试用例的数量都将非常少，以至于他可以尝试所有测试用例，并且所测试的内容将非常清晰，以至于他不会忽略任何情况。我对我们的系统进行了一次调查，因为我认为这是这种结构可能采取的形式的一个很好的例子。

根据我的经验，我很抱歉地说，工业软件制造商对系统的反应往往是复杂的。一方面，他们倾向于认为我们做了一种模范工作；另一方面，他们表示怀疑所使用的技术是否适用于大学的庇护环境之外，并表示我们之所以成功，只是因为整个项目的范围很小。我无意低估处理一项更大的工作所需的组织能力，因为有更多的人，但我想大胆地说，项目越大，结构就越重要！五个逻辑级别的层次结构很可能会被证明具有适度的深度，特别是当一个人比我们更有意识地设计系统时，其目的是软件可以平滑地适应（可能是剧烈的）配置扩展。

附录

同步基本体

并行顺序进程的显式相互同步是通过所谓的“信号量”实现的。它们是在进程嵌入的宇宙中分配的专用整数变量；它们在并行进程本身开始之前被初始化（值为0或1）。在初始化之后，并行进程将仅通过两个非常特定的操作（即所谓的同步原语）访问信号量。由于历史原因，它们被称为P操作和V操作。

例如，执行操作“P（sem）”的进程“Q”将称为“sem”的信号量的值减少1。如果相关信号量的结果值为非负，则进程Q可以继续执行其下一条语句；然而，如果结果值为负，则进程Q被停止并被登记在与相关信号量相关联的等待列表中。在进一步通知之前（即，在同一信号量上进行V操作），进程Q的动态进程在逻辑上是不允许的，并且不会向其分配任何处理器（参见上文“系统层次结构”，级别0）。

例如，执行操作“V（sem）”的进程“R”将称为“sem”的信号量的值增加1。如果相关信号量的结果值为正，则所讨论的V操作没有进一步的影响；然而，如果相关信号量的结果值是非正的，则在其等待列表中预订的进程之一将从该等待列表中删除，即。它的动态进程在逻辑上也是允许的，并且在适当的时候将为它分配一个处理器（同样，请参见上面的“系统层次结构”，级别0）。

COROLLARY 1.如果信号量值是非正的，则其绝对值等于在其等待列表中预订的进程数。

COROLLARY 2。P操作表示潜在延迟，互补V操作表示消除障碍。

注1.P-和V-操作是“不可分割的动作”；即如果它们在并行过程中“同时”发生，则它们不会相互干扰，因为它们可以被视为一个接一个地执行。

注2。如果Voperation产生的信号量值为负值，则其等待列表最初包含多个进程。它是未定义的。e、 然后从等待列表中删除哪个等待进程在逻辑上无关紧要。

注3.上述机制的一个结果是，允许动态进程的进程只能通过实际进程（即通过对初始值为非正的信号量执行P操作）来解除此状态。

在系统构思过程中，我们以两种完全不同的方式使用信号量。这种差异是如此显著，以至于回过头来看，人们会怀疑，将这两种方式作为非常相同的原语的使用来呈现是否真的公平。一方面，我们有用于互斥的信号量，另一方面，有专用信号量。

互斥在下面的程序中，我们指出了两个平行的循环过程（在括号“parbegin”和“parend”之间），它们在周围的宇宙被引入并初始化之后开始起作用。

由于对“互斥体”的P-和V-操作，标记为“关键部分”的动作在时间上相互排斥；给出的方案允许直接扩展到两个以上的并行进程,如果我们有n个并行进程，互斥体的最大值等于1，最小值等于$-（n-1）$。

关键部分始终使用，并且仅用于明确检查和修改描述系统当前状态的状态变量（在周围宇宙中分配）（只要需要调节各个过程之间的密切合作）。

专用信号量

每个顺序进程都与许多专用信号量相关联，没有其他进程会对它们执行P操作。宇宙用等于0的值初始化它们，它们的最大值等于1，最小值等于-1。

每当一个进程达到动态进程依赖于状态变量当前值的阶段时，它遵循以下模式：P（互斥）；“检查和修改状态变量，包括条件V（专用信号量）”；V（互斥）；P（专用信号量）。

如果检查得知所讨论的进程应该停止，它将执行操作“V（私有信号量）”——信号量值随后从0变为1——其他~4se，将跳过此V操作，让其他进程有义务在适当的时刻执行此V操作。离开关键部分时，状态变量的finM值反映了该义务的缺失或存在。

每当一个进程到达一个阶段，由于进程的进展，一个（或多个）被阻止的进程现在应该获得继续的权限时，它遵循以下模式：

P（互斥）；

“修改和检查状态变量，包括对其他进程的专用信号量进行零或更多V操作”；

V（互斥）。

通过引入适当的状态变量和关键部分的适当编程，可以实现分配外围设备、缓冲区等的任何策略。

通过观察发现，在上述两个互补的关键部分中，可以通过引入“一个完整的评估”的概念来执行相同的检查，例如一个自由的重新排序器和一个需要读者的过程，从而大大减少了编码和推理的量。每当出现不稳定的情况时，它都会在创建它的关键部分中删除（包括一个或多个专用信号灯上的V操作）。

证明非协调合作

系统东部的顺序过程都被重新定义为循环过程，在循环过程中，可以标记某个中性点，即所谓的“归位”，在“归位位置”中，当系统处于静止状态时，所有过程都处于该位置，。

当循环进程离开其归位位置时，“它接受任务”；当任务已经执行而不是更早时，进程返回到其初始位置。每个线路过程都具有特定的任务处理能力（例如，执行用户程序或解开打印机输出的一部分等）。

协调合作主要表现在三个阶段。

（1） 事实证明，尽管执行任务的过程可以为其他过程生成有限数量的任务，但单个初始任务不能产生无限数量的任务生成。证明很简单，因为流程只能为层次结构较低级别的流程生成任务，从而排除了循环性。（如果需要从卷筒中提取段的进程为段控制器生成了一个任务，则已采取特殊预防措施，以确保请求的段至少在请求进程有效访问相关段之前保持在核心中。如果没有这种预防措施，有限任务可能会被强制生成无限数量的段控制器任务系统可能陷入无效的页面抖动。）（2） 事实证明，当系统中的某个地方仍在等待一个生成但未接受的任务时，所有进程都不可能返回到它们的鸣笛位置。（这通过上述情况的不稳定性得到了证明。）

（2） 事实证明，当系统中的某个地方仍在等待一个生成但未接受的任务时，所有进程都不可能返回到它们的鸣笛位置。（这是通过刚才描述的情况的不稳定性来证明的。）

（3）证明了在接受初始任务之后，所有进程最终将（再次）处于其归位。在任务执行过程中受阻的每个进程都依赖于其他进程来消除障碍。本质上，所讨论的证明是对“循环等待”缺失的证明：过程P等待过程Q等待过程R等待过程P（循环等待的常用术语是“致命拥抱”）。A. N. Habermann在他的博士论文中展示了这一点。

---煤油灯科技victorlamp.com翻译整理---