跳到主要内容

3. GORDO 中的实现

3.1 GORDO 简介​

GORDO 是在 SDS Sigma 7 上实现的分时系统。下面概述与本文有关的若干特性。

3.1.1 GORDO 文件系统​

该文件系统是面向页的。它由文件和目录组成。一个文件由标题和若干页组成，这些页构成文件的正文。一个目录由若干目录项组成，这些目录项指向文件或其他目录。

3.1.2 GORDO 进程​

  • 进程是一个程序（过程与数据）加上其逻辑环境。换言之，进程是一个为 GORDO 调度程序所知并受其控制的程序。
  • 一个用户（一个作业）可以拥有若干进程，它们可以各不相同，如编译程序、装入程序、编辑程序、应用程序等。进程通过系统调用 (FORK) 创建。
  • 进程可以引用的空间是长度为 128k 字的虚拟空间。其中一部分（8k）保留给操作系统，另一部分（120k）由用户直接访问。后者可以在「耦合」时用取自不同文件的页填充或修改其在虚拟空间中的那一部分。（见下文：服务调用）图 3 说明了这种耦合。
  • 进程可以通过系统调用请求服务。与本文有关的系统调用有：

WAKE 用于唤醒（置为活动）一个睡眠进程 SLEEP 用于使另一个进程（或自身）睡眠 COUPLE 用于把文件空间中的一页耦合到虚拟空间。

  • 进程通常以从属模式运行。然而，如果它被设置为 I/O 进程，则可以访问特权指令。
  • 进程可以通过挂在「信箱」目录下的文件共享数据。

备注：在本备忘录中，进程与程序这两个词可互换使用。

[图 3 - 虚拟空间与耦合 - 见 PDF 文件]

3.2 软件组织概览​

图 4 说明了整体组织。

该系统基于两个主要程序：网络程序 (Network) 与处理程序 (Handler)。

处理程序是一个与 IMP-主机硬件接口密切相关的 I/O 中断例程。它协助网络进程发送和接收网络报文。

网络进程承担了大部分工作。

其主要功能是满足用户打开/关闭连接以及发送/接收网络报文的请求。为此，

  • 它利用分配表（HOST 表、CONNECT 表、INPUT LINK 表；见 3.3.1.1）建立、标识和断开链路
  • 它通过探查网络信箱目录来获知新用户的存在；
  • 它借助共享页与活动用户通信，报文和请求通过这些共享页交换（连接共享页）；
  • 它在工作页中格式化入站/出站报文。该工作页有一个扩展部分（应急环）；
  • 它借助一个共享页（I/O 通信页）与处理程序通信，该页包含 I/O 通信缓冲区。

[图 4 - 软件组织概览 - 见 PDF 文件]

3.3 软件说明​

3.3.1 数据结构​

网络程序利用 3 张表来建立、标识和断开链路与连接：

一张按远程主机号排序的表。

一张按连接号排序的表。

一张按输入链路号排序的表。

(a) HOST 表（见图 5）​

它是一张位表，指出空闲的出站链路。它具有以下特性：

  • 位置：驻留磁盘
  • 耦合：耦合到网络进程的虚拟空间。
  • 大小：槽数与远程主机数相同。
  • 槽结构：位数与到一台远程主机的可能出站链路数相同，即 256。
  • 访问：索引。每个槽通过远程主机号访问。
  • 特殊之处：整张表中至多有 64 位可以被置位。这一数字对应于同一时刻可以激活的最大出站链路数（无论远程主机的数目是多少）。
(b) CONNECT 表​

这张表记录所有连接的环境。

它具有以下特性：

  • 位置：驻留磁盘
  • 耦合：耦合到网络进程的虚拟空间
  • 大小：槽数与在用连接数相同。
  • 槽结构：见图 6。每个槽为 2 字长
  • 访问：索引。每个槽通过连接号访问。其处理方式见 3.4。
  • 特殊之处 1：对应于主连接的槽结构与辅助连接的不相同（见图 7）。这是因为用户标识和请求是通过主共享页完成的。
  • 特殊之处 2：这张表与连接页并行处理（见 3.3.2 (b)）
  • 特殊之处 3：这张表主要用于发送报文。（对每条连接，它包含出站链路号和远程主机号，即发送一条报文所需的全部信息。）

这张表记录所有入站（输入）链路，因此与 CONNECT 表密切相关。

[图 5 - HOST 表 - 见 PDF 文件]

[图 6 - CONNECT 表：槽结构 - 见 PDF 文件]

[图 7 - INSERT LINK 表：槽结构 - 见 PDF 文件]

它具有以下特性：

  • 位置：驻留磁盘。
  • 耦合：耦合到网络进程的虚拟空间。
  • 大小：槽数与入站链路数相同，即与连接数相同
  • 槽结构：见图 7。每个槽为 1 字长
  • 访问：散列。散列键值主要基于入站链路号和远程主机号。
  • 特殊之处 1：在建立下一条连接期间，这张表还用于暂时记住连接号。其处理方式见 3.4。
  • 特殊之处 2：这张表主要在接收报文时使用。（对每条入站链路，它包含相应的连接号，即间接地包含报文应被传递给哪个用户标识）

3.3.1.2 缓冲区页​

下面将要描述的所有页都包含两个缓冲区（输入和输出）。这些缓冲区用于传递或处理报文。

这些缓冲区每个的大小至少应等于一条报文的大小，即 8095 位。我们选择了 253 字（8096 位）的缓冲区大小，这样两个缓冲区都能包含在一页（512 字）之内。该页剩余的 6 个字一般用于控制。

典型的缓冲区页结构如图 8 所示。

(a) I/O 通信页​

见图 9。

这个 I/O 通信页用作处理程序与网络程序之间的接口。

在该页的缓冲区中，处理程序逐字地组装（输入）或拆解（输出）报文，例如，由网络程序排入输出缓冲区的一条「就绪待发」报文，由处理程序逐字发送出去。

主要特性：

  • 位置：驻留内存：锁定页
  • 耦合：耦合到网络进程的虚拟空间
  • 内容：* 用于入站报文的输入缓冲区（253 字）用于出站报文的输出缓冲区（253 字）
    • 输入控制区（6 个半字）
    • 输出控制区（6 个半字）
  • 结构：见图 9。
  • 特殊之处：* 输入缓冲区由处理程序填充（从硬件读取），由网络程序取空
    • 输出缓冲区则相反
(b) 连接共享页（用户-网络共享区）​

一般特性：

  • 共享页的数目与连接的数目相同。
  • 这些在网络进程与用户进程之间共享的页构成一个通信区，用于 (1) 来回传递报文，以及 (2) 交换控制信息，例如建立新连接的请求。

主要特性：

  • 位置：驻留磁盘
  • 耦合：同时耦合到用户进程的虚拟空间和网络进程的虚拟空间。
  • 内容：- 用于入站报文的输入缓冲区（253 字）
    • 用于出站报文的输出缓冲区（253 字）
    • 输入控制区（6 个半字）
    • 输出控制区（6 个半字）
  • 结构：见图 10。
  • 特殊之处 1：- 输入缓冲区由网络填充，由用户取空。
    • 输出缓冲区则相反。
  • 特殊之处 2：对应于主连接共享页的控制区与辅助连接的不同。这是因为辅助连接的建立请求正是通过「主连接控制区」传递给网络进程的。
(c) 工作页​

一般特性：

  • 这一页使网络程序与处理程序能够独立地处理不同的报文，从而有助于实现重叠。例如，当处理程序忙于向硬件发送一条报文时，网络程序可以格式化（首部、标记等）下一条待发报文，以便在处理程序一空闲时就重新启动它。

主要特性：

  • 位置：驻留磁盘
  • 耦合：耦合到网络进程的虚拟空间
  • 内容：- 用于入站报文的输入缓冲区（253 字）
    • 用于出站报文的输出缓冲区（253 字）

备注：

在接收期间，可能出现用户程序尚未准备好接受新报文的情况。此时，为避免系统堵塞，网络会把入站报文暂时存放在应急环的某个缓冲区中。（如果该环已满，将调用一个求助例程。）

在发送期间，所有操作都与 RFNM 同步，因此无需提供这类过程。（网络程序只允许用户在收到上一条已发送报文的 RFNM 之后才重新发送。）

[图 8 - 典型缓冲区页 - 见 PDF 文件]

[图 9 - I/O 通信页结构 - 见 PDF 文件]

[图 10 - 连接共享页结构 - 见 PDF 文件]

3.3.2 程序​

3.3.2.1 处理程序​

一般特性：

它是一个 I/O 中断例程，驱动 IMP/主机硬件接口以发送或接收报文。发送和接收以全双工方式进行。

主要特性：

  • 位置：驻留内存。处理程序与操作系统位于同一存储区，可以视为操作系统的一部分。
  • 启动：由 IMP-主机硬件中断触发。该中断在以下任一情况下触发：
  • 发送期间，当一个报文字被完整地发送给 IMP 时
  • 接收期间，当一个报文字已从 IMP 完整接收时
  • 空闲期间，当硬件从 Sigma 7 CPU 收到「启动输入」或「启动输出」命令时。这些命令由网络程序发出，用以引发回送中断（从而间接启动处理程序）。
  • 主要功能：* 在发送时取空输出缓冲区的内容（发往 IMP 的出站报文）。这一操作逐字（32 位）进行，并使用「写」命令来驱动主机-IMP 硬件。
  • 用从主机-IMP 硬件接收到的数据（入站报文）填充输入缓冲区。这一操作同样逐字进行，并使用「读」命令来驱动主机-IMP 硬件。
  • 当上述任一操作完成时，唤醒网络程序。

3.3.2.2 网络程序​

一般特性：

该程序为用户服务，用于打开/关闭连接以及发送/接收报文。它借助处理程序来与硬件接口。

从 GORDO 的角度看，它是一个普通进程，并按普通进程对待。

主要特性：

  • 位置：驻留磁盘。更确切地说，它睡眠时位于磁盘上，被程序唤醒时调入内存。
  • 启动：它通过由用户进程或处理程序发出的「WAKE」服务调用启动。
  • 主要功能：* 应用户请求建立/删除出站连接。为此，它向远程主机发送控制报文（见 2.4.2），以建立/释放链路；随后它回过来通知用户。
    • 确保对入站控制报文（经控制链路传输）的处理，例如协助建立/删除连接（由远程主机请求的那些）。
  • 准备出站报文的发送。它从共享页中取出正文报文（报文由用户存放在那里），对它们进行格式化（加上首部、标记、校验和……），并把它们交给处理程序去发送。
  • 确保入站报文的投递。这与上述操作相反。报文应投递给哪些用户，是通过首部来识别的。
  • 虚拟空间配置：见图 11。
  • 特殊之处：它被集成为 I/O 进程，从而可以访问特权指令（RD/WD，用于间接启动处理程序）。

[图 11 - 网络进程虚拟空间 - 见 PDF 文件]

3.4 软件过程​

详细的软件过程见附录 A 所附的流程图。

不过，为了快速理解其实现，下面列出一些典型的软件过程。

3.4.1 一些典型序列的说明​

考察用户可以使用的一些事务（见 2.4），并指出它们所隐含的基本软件过程。对每种情形，我们将描述 (i) 用户程序做什么，以及 (ii) 网络程序做什么。

(a) 打开主链路（另见 2.4.2）​

(i) 用户程序做什么[1]:​
  • 它把一个文件的名称存入网络信箱目录，例如 DATA；
  • 它把该文件的第一页耦合到自己的虚拟空间；
  • 它把信息存入这一页（其作业/进程号、远程主机号，例如 (i)）；
  • 它唤醒网络进程；
  • 它进入睡眠。
(ii) 网络程序做什么：​
  • 它探查网络信箱目录并访问文件 DATA；
  • 它把该文件的第一页耦合到自己的虚拟空间（共享区，见 3.3.1.2）。假设这一页在共享区中是第 k 页；k 即内部连接号；
  • 它探查新 HOST 表的第 i 个槽（见 3.3.1.1 (a)），并选出第一个为 0 的位，例如第 (alpha) 位；alpha 对应于出站链路号；
  • 它把信息（作业/进程号、远程主机号 (i)、出站链路号 (alpha)）存入 CONNECT 表的第 k 个槽（见 3.3.1.2）。
  • 它把连接号 (k) 暂时存入 INPUT LINK 表。这是在向该表创建表项时完成的（对键值「出站链路号 (alpha) + 远程主机号 (i) + 出站标志」进行散列。）；
  • 它准备报文正文 ENQ PRIM 0 0 a，并通过加上首部、标记、校验和等来格式化一条完整的报文；
  • 它检查处理程序的状态（I/O 锁定页中的位）。如果处理程序空闲，它把「就绪待发」控制报文存入 I/O 锁定页的输出缓冲区，启动处理程序，然后进入睡眠。否则它进入睡眠。

过一会儿，处理程序因收到一条完整报文而唤醒网络进程。我们假设这条报文是远程主机为确认连接建立而发送的控制报文。报文正文应为：

ACK ENQ PRIM 0 0 alpha 0 0 beta

其中 beta 是入站链路号。（见 2.4.2）

现在看看网络程序在收到上述控制报文时做什么：

  • 它通过对同一键值重新散列，取回先前存入 INPUT LINK 表的连接号（见上文）。同时它删除该表项；
  • 它为入站链路在 INPUT LINK 表中创建一个表项。为此，它对键值「入站链路号 (beta]) + 远程主机号 (i) + 「入站标志」」进行散列。在该表项中，它存入主机号 (i)、入站链路号 (beta) 以及连接号 (k)；
  • 它通过存入入站链路号 (beta) 来更新 CONNECT 表的第 k 个槽；
  • 它置位第 k 个共享页（即刚刚打开的主连接所对应的页）中的「网络-用户」位，并唤醒用户进程；
  • 它进入睡眠。

(b) 通过主链路发送一条报文​

(i) 用户程序做什么[1]。​
  • 它把报文正文存入主连接共享页的输出缓冲区（见 3.3.1.2）；
  • 它置位该页的「用户-网络」位，并唤醒网络进程；
  • 它进入睡眠。
(ii) 网络程序做什么：​
  • 它查找用户请求，即依次探查各连接共享页，并选出其「用户-网络」位已置位的页。假设 k 是共享列表中被选中的页号，K 是连接号；
  • 它通过检测共享页 k 的「请求位」来确定请求类型。它查明这是一个发送报文的请求。
  • 它从共享页 k 的输出缓冲区中取出报文正文，格式化为一条完整报文，并以与上文非常相似的方式发送给处理程序（见「打开主链路」）。
  • 它进入睡眠。

[1] 备注：在第一阶段，用户将直接在自己的程序中编写网络功能。以后将提供子程序供用户使用。这些子程序将与 2.4 中描述的非常接近。