3. Implementation in GORDO

3.1 Introduction to GORDO

GORDO is a time-sharing system implemented on SDS Sigma 7. We outline below some of the characteristics relevant to our paper.

3.1.1 GORDO file system

The file system is page oriented. It is composed of files and directories. A file consists of a heading and a number of pages which compose the body of the file. A directory consists of a number of entries that point to either files or other directories.

3.1.2 GORDO process

• A process is a program (procedures and data) plus its logical environment. In other words a process is a program which is known and controlled by the GORDO scheduler.
• A user (a job) may have several processes as different as compiler, loader, editor, application program, etc. A process is created through a system call (FORK).
• The space a process can refer to is the Virtual Space of 128k word length. A part (8k) of it is reserved for the operating system, the other part (120k) is directly accessed by the user. This later may fill or modify its part of the virtual space upon 'coupling'. (See below: service calls) pages taken from different files. Figure 3 illustrates this coupling.
• A process can request for services by means of system calls. The system calls relevant to our paper are:

WAKE for awaking (set active) a sleeping process SLEEP for putting asleep another process (or itself) COUPLE for coupling a page from the file space to the virtual space.

• A process ordinarily runs in slave mode. However if it is set up as an I/O process it can access privileged instructions.
• Processes can share data through files attached to "mail box" directories.

Remark: Through this note the words process and program are used inter-changeably.

[Figure 3 - Virtual Space and Coupling - see PDF file]

3.2 Software Organization Overview

Figure 4 illustrates the overall organization.

The system is based upon two main programs: the "Network" and the "Handler".

The Handler is an I/O interrupt routine closely related to the IMP-HOST hardware interface. It serves the Network process in transmitting an receiving network messages.

The Network process carries out most of the work.

Its main function is to satisfy the users' requests for opening/closing connections and transmitting/receiving network messages. For so doing,

• it establishes, identifies, and breaks the links upon using the allocation tables (HOST, CONNECT, INPUT LINK; see 3.3.1.1)
• it is aware of the presence of new users upon exploring the Network mail box directory;
• it communicates with active users by means of shared pages through which messages and requests are exchanged (connection shared pages);
• it formats incoming/outgoing messages in a working page. This working page has an extension (emergency ring);
• it communicates with the Handler by means of a shared page (I/O communication page) which contains the I/O communication buffers.

[Figure 4 - Software organization overview - see PDF file]

3.3 Software Description

3.3.1 Data Structures

3.3.1.1 Allocation tables: HOST, CONNECT, INPUT LINK

The Network program establishes, identifies, and breaks links and connections upon using 3 tables:

A table sorted by remote HOST #.

A table sorted by connection #.

A table sorted by input link #.

(a) HOST table (see figure 5)

It is a bit table indicating the free outgoing links. It has the following characteristics:

• Location: Disc resident
• Coupling: Coupled to the Network process virtual space.
• Size: As many slots as remote HOST[s].
• Slot structure: As many bits as possible outgoing links to a remote HOST, i.e., 256.
• Access: Indexing. Each slot is accessed through a remote HOST #.
• Specific feature: Throughout the whole table no more than 64 bits can be turned on. This figure corresponds to the maximum number of outgoing links that can be activated at one time (No matter what is the number of remote HOST[s]).

(b) CONNECT table

This table keeps track of all the connections' environment.

It has the following characteristics:

• Location: Disc resident
• Coupling: Couples to the Network process virtual space
• Size: As many slots as connections in use.
• Slot structure: See figure 6. Each slot is 2 word length
• Access: Indexing. Each slot is accessed through a connection #. See 3.4 the way it is handled.
• Specific feature 1: The slot structure corresponding to a primary connection is not identical to that of an auxiliary connection (See figure 7). This because user identifications and requests are done through primary shared pages.
• Specific feature 2: This table is handled in parallel with the connection pages (See 3.3.2 (b))
• Specific feature 3: This table is mainly used for transmitting messages. (For each connection it contains the outgoing link # and remote HOST #, i.e., all the information required for transmitting a message.)

(c) INPUT LINK table

This table keeps track of all the incoming (input) links and so is closely related to the CONNECT table.

[Figure 5 - HOST table - see PDF file]

[Figure 6 - CONNECT table: Slot structure - see PDF file]

[Figure 7 - INSERT LINK table: Slot structure - see PDF file]

It has the following characteristics:

• Location: Disc resident.
• Coupling: Coupled to the Network process virtual space.
• Size: As many slots as incoming links, i.e., as connections
• Slot structure: See figure 7. Each slot is 1 word length
• Access: Hashing. The hashed key value is mainly based upon the incoming link # and the remote HOST #.
• Specific feature 1: This table is also used for momentarily memorizing the connection number while establishing the next connection. See 3.4 the way it is handled.
• Specific feature 2: This table is primarily used upon receiving messages. (For each incoming link it contains the corresponding connection #, i.e., indirectly the user identification to which the message should be passed along)

3.3.1.2 Buffer pages

All the pages that are now to be described contain two buffers (input and output). These buffers are used for either passing along or processing messages.

The size of each of these buffers should at least be equal to that of a message, i.e., 8095 bits. We have chosen a buffer size of 253 words (8096 bits) so that both of the buffers are included within one page (512 words). The 6 remaining words of the page are generally used for control.

A typical buffer page structure is identified on figure 8.

(a) I/O communication page

See figure 9.

This I/O communication page is used as an interface between the Handler and the Network program.

In the buffers of this page the messages are assembled (input) or de-assembled (output) word by word by the Handler, e.g., a "ready to go" message, sorted by the Network program in the output buffer, is shipped out word by word by the Handler.

Main characteristics:

• Location: Resident in core: Locked page
• Coupling: Coupled to the Network process virtual space
• Content: * Input buffer (253 words) for incoming messages Output buffer (253 words) for outgoing messages
  • Input control zone (6 half words)
  • Output control zone (6 half words)
• Structure: See figure 9.
• Specific feature: * The input buffer is filled by the Handler (read from hardware) and emptied by the Network program
  • Vice versa for the output buffer

(b) Connection shared pages (User-Network shared zone)

General features:

• There are as many shared pages as connections.
• These pages shared between the network and the user processes constitute a communication zone for (1) passing the messages back and forth, and (2) exchanging control information, e.g., a request for establishing new connections.

Main characteristics:

• Location: Disc resident
• Coupling: Coupled to both a user process virtual space and the network process virtual space.
• Content: - Input buffer (253 words) for incoming messages
  • Output buffer (253 words) for outgoing messages
  • Input control zone (6 half words)
  • Output control zone (6 half words)
• Structure: See figure 10.
• Specific feature 1: - The input buffer is filled by the Network and emptied by the user.
  • Vice versa for the output buffer.
• Specific feature 2: The control zone corresponding to a primary connection shared page differs from that of an auxiliary connection. This because it is via a "primary connection control zone" that auxiliary connection establishment requests are transmitted to the Network process.

(c) Working page

General feature:

• This page allows the Network and the Handler programs to work independently on different messages and so contributes to an overlapping. For instance, when the Handler is busy transmitting a message to the hardware, the Network program can format (leader, marking, etc.) the reset message to be shipped out, so that it can reinitiate the Handler as soon as it is free.

Main characteristics:

• Location: Disc resident
• Coupling: Coupled to the Network process virtual space
• Content: - Input buffer (253 words) for incoming messages
  • Output buffer (253 words) for outgoing messages

Remark:

During reception it may happen that a user program is not ready to accept a new message. In that case, to avoid clogging up the system, the Network stores momentarily the incoming message in one of the buffer of the emergency ring. (If this ring is full a help routine will be invoked.)

During emission all operations are synchronized with the RFNM[s], therefore such procedures need not be provided. (The Network program allows a user to re-emit only when having received the RFNM of the previous transmitted message.)

[Figure 8 - Typical buffer page - see PDF file]

[Figure 9 - I/O Communication page structure - see PDF file]

[Figure 10 - Connection shared page structure - see PDF file]

3.3.2 Programs

3.3.2.1 Handler program

General features:

It is an I/O interrupt routine which drives the IMP/HOST hardware interface in order to transmit or receive messages. Transmission and reception are carried out in a full duplex mode.

Main characteristics:

• Location: Core resident. The Handler is in the same memory zone as the operating system and can be considered as part of it.
• Initiation: By the IMP-HOST hardware interrupt. This interrupt is triggered either:
• during transmission when a message word is completely sent to the IMP
• during reception when a message word has been completely received from the IMP
• during idle time when the hardware received either a 'start input' or 'start output' order from the Sigma 7 CPU. Those orders are issued by the Network program for provoking interrupts back (consequently for indirectly initiating the Handler).
• Main functions: * Empties the output buffer upon transmitting its content (outgoing message to the IMP. This operation is carried out word by word (32 bits) and makes use of "Write" orders for driving the HOST-IMP hardware.
• Fills the input buffer with data received from HOST-IMP hardware (incoming message). This operation is also carried out word by word and makes use of "Read" orders for driving the HOST-IMP hardware.
• Wakes up the Network program when any of the previous operations is complete.

3.3.2.2 Network program

General features:

This program serves the user for opening/closing connections and transmitting/receiving messages. It uses the Handler as an aid for inter-facing with the hardware.

For the GORDO point of view it is a regular process and treated as such.

Main characteristics:

• Location: Disc resident. More precisely it is on disc when asleep and called in core when awakened by a program.
• Initiation: It is initiated through 'WAKE' service calls issued either by a user process or by the Handler.
• Main functions: * Establishes/deletes outgoing connections upon users' requests. For so doing it sends control messages (see 2.4.2) to remote HOST[s] in order to get links established/released; it then notifies back the users.
  • Insures the processing of incoming control messages (transmitted over control links), e.g., for contributing to establishments/deletions of connections (those requested by remote HOSTS).
• Prepares transmission of outgoing messages. It picks up text messages from shared pages (the messages are stored there by users), formats them (adds leader, marking, checksum..), and passes them along to the Handler for transmission.
• Insures delivery of incoming messages. It is the opposite of the above operation. The users to which the messages should be delivered are identified through the leaders.
• Virtual space configuration: See figure 11.
• Specific feature: It is integrated as an I/O process, so that it can access privileged instruction (RD/WD for indirectly initiating the Handler).

[Figure 11 - Network Process Virtual Space - see PDF file]

3.4 Software Procedures

The detailed software procedures are given on the flowcharts attached with Appendix A.

However, to get a quick understanding of the implementation we list below some typical software procedures.

3.4.1 Description of some typical sequences

Consider some of the transactions at user's disposal (See 2.4) and point out the basic software procedures they imply. For each case we will delineate (i) what the user program does and (ii) what the Network program does.

(a) Open a primary link (See also 2.4.2)

(i) What the user program does[1]:

• it stores in the Network mail box directory the name of a file, e.g., DATA;
• it couples the first page of this file to its virtual space;
• it stores information in this page (its job/process #, the remote HOST #, e.g., (i));
• it wakes up the Network process;
• it goes to sleep.

(ii) What the Network program does:

• it explores the Network mail box directory and accesses the file DATA;
• it couples the first page of this file to its virtual space (Shared Zone, see 3.3.1.2). Suppose this page to be kth in the shared zone; k is the internal connection #;
• it explores the ith slot of the new HOST table (See 3.3.1.1 (a)) and selects the first bit = 0, e.g., the (alpha)th bit; alpha corresponds to the outgoing link #;
• it stores information (job/process #, remote HOST # (i), outgoing link # (alpha)) in the kth slot of the CONNECT table (See 3.3.1.2).
• it momentarily stores the connection # (k) in the INPUT LINK table. This is carried out upon creating an entry in this table (Hashing the key value: "outgoing link # (alpha) + remote HOST # (i) + outgoing flag".);
• it prepares the message text ENQ PRIM 0 0 a and formats a complete message in adding leader, marking, checksum, etc.;
• it checks the Handler state (bit in I/O locked page). If the Handler is free, it stores the 'ready to go' control message in the output buffer of the I/O locked page, initiates the Handler, and goes to sleep. Else it goes to sleep.

After a while the Handler wakes up the Network process because it has received a complete message. We suppose this message be the control message sent by the remote HOST for acknowledging the establishment of the connection. The message text should be:

ACK ENQ PRIM 0 0 alpha 0 0 beta

where beta is the incoming link #. (See 2.4.2)

Let's see now what the Network program does when receiving the above control message:

• it retrieves the connection # previously stored in the INPUT LINK table upon re-hashing the same key value (See above). Also it deletes this entry;
• it creates an entry in the INPUT LINK table for the incoming link. For so doing it hashes the key value: "incoming link # (beta]) + remote HOST # (i) + "incoming flag". In this entry it stores the HOST # (i), the incoming link # (beta), and connection # (k);
• it updates the kth slot of the CONNECT table in storing the incoming link # (beta);
• it turns on the 'net-user' bit in the kth shared page (page corresponding to the primary connection that has just been opened) and wakes up the user process;
• it goes to sleep.

(b) Transmit a message over primary link

(i) What the user program does[1].

• it stores the message text in the output buffer of the primary connection shared page (see 3.3.1.2);
• it turns on the 'user-net' bit of this page and wakes up the Network process;
• it goes to sleep.

(ii) What the Network program does:

• it looks for user request, i.e., it explores in sequence the connection shared pages and selects the one that has its 'user-net' bit turned on. Suppose k be the selected page # on the shared list, K is the connection #;
• it determines the request type in testing the 'request bits' of the shared page k. It finds out that it is a request for transmitting a message.
• it takes the message text from the output buffer of the shared page k, formats it into a complete message and transmits to the Handler in a very similar way as above (See Open a primary link).
• it goes to sleep.

[1] Remark: In a first phase the user will directly write the network functions in his program. Later on subroutines will be put at user's disposal. These subroutines will be very close to those described in 2.4.