Input/Output Method

1. Technical Field

This invention relates to data processing and more particularly to an improved computer program method for performing overlapped input/output.

2. Description of the Prior Art

A task frequently performed in a computing center is to copy data from one input/output device to another in bulk quantity. For example, it is frequently necessary to copy the entire contents of a disc pack to magnetic tape. In many computing centers, a back-up copy of the contents of all disc storage is made periodically in order to permit the restoration of disc pack contents in the event of computer malfunction or human error.

For disc packs of large capacity, transferring the entire contents can consume significant amounts of time measured in minutes or perhaps even house, depending upon the average data transfer rate. The hardware design of the computer system places an upper limit on the maximum transfer rate. However, the effective average transfer rate is usually less than this hardware-imposed limit because of delays inherent in the computer program that performs the copy. It is desirable that this copy program be carefully designed to reduce copy delays.

In many computer systems, input/output ("I/O") devices are grouped for data transfer purposes under separate hardware controllers. Typically, for example, a number of disc storage devices is provided with a disc controller while a number of tape devices is provided with a separate tape controller. Some computer systems may have several disc controllers, or several tape controllers, each with its own group of associated I/O devices. Each controller typically transfers data directly into or out of main memory at a high transfer rate by direct memory access, each controller acting independently of the others so that I/O transfer by two or more controllers may occur simultaneously. In a case where two independent controllers are employed, as is generally the case for disc-to-tape or tape-to-disc copy, it is advantageous to use two data buffers in main memory in order to achieve time overlap of the read and the write operations. Data is being read into the first buffer area while data is simultaneously being written out from the second buffer area.

It is usually advantageous for the data buffers to be relatively large in size so that data transfer takes place in large segments. Since the copy program then is called upon to intervene less frequently, overhead associated with the copy program such as disc latency delays may be reduced.

In order to perform double-buffered overlapped I/O in the manner described, it is usually necessary that the computer system provide facilities for the copy program to issue asynchronous I/O requests. An asynchronous request is one which causes the requested I/O operation to begin, with control continuing in the requesting program while the requested operation is taking place. Given this facility, the copy program can proceed in the following straightforward prior art manner. The copy program issues a request to read from a first device into a first buffer area. This activity is begun, and control continues in the copy program which then issues a request to write to a second device from a second buffer area. Overlap of input and output has been achieved; control again continues in the copy program which then may proceed to other matters.

Performing asynchronous I/O requests and employing large amounts of memory for buffer space is generally not a problem when the copy program is in direct control of the hardware resources as is the case, for example, with a specialized stand-alone copy program. Asynchronous I/O is a facility generally provided by the computer system hardware, and the total available space in memory is typically adequate for two large data buffers. However, a stand-alone program for copying may displace a general purpose time-shared operating system that supplies service to a number of users. Generally, it is not desirable for the normal users of a computer system to halt their activities, even temporarily, while copying is done. In most installations it is a requirement that the copy program operate as a user program within the environment of the general purpose operating system. Then the copy program may be utilized by normal system users, and copying can take place contemporaneous with other user activity. However, the memory space available to a user program may restrict the buffer size. Further, many general purpose time-shared operating systems provide only synchronous I/O. Thus a read request will not return control to the user program until the read has been completed and the information read is in memory. Under these circumstances it may not be possible, in the prior art, to attain overlapped operation.

The present invention provides double-buffered overlapped I/O to rapidly copy data from one I/O device to another while using synchronous I/O commands. A novel computer program method is employed that operates within the confines of a user program in the environment provided by a time-shared operating system. This method utilizes two concurrently running computer programs ("processes"), each of which reads and writes the two I/O devices, but in a cooperative manner that avoids interference and achieves overlap of the read and write operations. Each of the two processes provides a data buffer within the memory space allotted to it by the operating system. This simplifies the operation of each process since each administers only a single buffer, while permitting the maximum size of each of the two buffers to approach the total memory space allotted to each single user process. To effect the needed cooperation, the two concurrently running processes communicate with one another upon completion of each buffer read or write step using interprocess communication facilities provided by the operating system.

FIG. 1 is a block diagram of a computer system operating with a prior art input/output method;

FIG. 2 is a flow chart of the prior art method used in FIG. 1;

FIG. 3 is a block diagram of a computer system operating with an illustrative embodiment of an input/output method according to the present invention;

FIG. 4 is a flow chart of the inventive method used in FIG. 3; and

FIG. 5 is a timing diagram illustrating the overlapped input/output of the illustrative embodiment.

An attached APPENDIX shown an illustrative computer program that operates in accordance with the present invention.

FIG. 1 is a block diagram of a computer system that performs double buffered overlapped input/output according to the prior art. Disc controller 10 transfers data from disc into buffer 1, an area of computer memory 12, by direct memory access. Simultaneously, tape controller 14 transfers data by direct memory access from buffer 2 to tape. Alternately, controller 10 writes into buffer 2 while controller 14 is reading from buffer 1. As one buffer is being filled, the other buffer is being emptied permitting overlapped operation by the two controllers.

Copying from disc to tape takes place under control of a computer program that occupies a portion of memory 12. This copy program may be stand-alone, that is, the sole occupant of memory 12 with direct control over controllers 10 and 14, or the copy program may be one process administered by a time-shared operating system that occupies a major portion of memory 12. Such an operating system is a permanent resident of memory 12 that serves multiple users by scheduling multiple processes and allocating resources such as controllers 10 and 14, among the processes. In the environment of a multi-process time-shared operating system the copy process exerts control over controllers 10 and 14 indirectly by issuing requests to the operating system. It is in this time-shared environment that the present invention finds its greatest utility.

In the present context, a computer program process or simply "process" is a term of art meaning an individual instance of an operating computer program that is performing a function. For example, a computer system may have a single program that prints payroll checks. However, in the time-shared environment the check printing program may be invoked three times, giving rise to three different processes that simultaneously and independently print payroll checks for employees with names in three different parts of the alphabet.

FIG. 2 is a flow diagram that details the prior art single-process computer program method used in FIG. 1. Read and write requests are asynchronous so that return to the process is immediate and the process must explicitly wait for completion.

The process of FIG. 2 begins by waiting for both disc and tape controllers to finish prior activity and to be in a ready condition. The process requests a read of data from disc to buffer 1 and a write from buffer 2 to tape, and waits for both to complete. In a stand-alone program, the central processor may stand idle by executing completion tests repeatedly. In a time-shared operating system, more typically, the process would be placed on a wait queue while other tasks are performed. In any event, the process waits for both disc and tape completion since transfer can proceed no faster than the slower of the two devices. After both are ready, the process issues a read from disc to buffer 2 and a write from buffer 1 to tape followed by another wait for disc and tape ready. The process loops and repeats as necessary until all data are transferred. Certain details are omitted from FIG. 2 such as initialization, end-of-file and termination.

FIG. 3 is a computer system that operates in accordance with the present invention under control of two concurrently running processes in a time-shared operating system environment providing synchronous input/output requests. Process 1 in computer memory 12 issues requests to read from disc through disc controller 10 into its single buffer area, and issues requests to write from the buffer to tape via tape controller 14. Similarly, independent concurrent process 2 issues disc read requests and tape write requests for its own buffer area. To keep order and prevent interference with one another, each process notifies the other of read and write completion by means of interprocess communication provided by the operating system. In the present embodiment, this is provided by two "pipes". A pipe is a facility by which a process may issue an ordinary synchronous write of data to be read by a second process using an ordinary synchronous read without incurring the delay of actual input and output. The operating system provides buffer space and administers the first-in-first-out data transfer between the reading and writing processes within computer memory.

In alternative embodiments, the required interprocess communication may be implemented by any of a variety of facilities. One such facility is a common memory area accessible to both processes. Each process writes information intended for the other process into a previously agreed upon memory area where it is found by the other process. Another such facility entails the use of semaphores. A semaphore is a memory location that contains a numerical value administered by the operating system. The numerical value of the semaphore may be tested by a process, or the process may arrange to be notified by the operating system when the semaphore takes on certain values. Still other interprocess communication mechanisms may be employed in the present invention without departing from the scope of the invention, as will be evident to those skilled in the art.

FIG. 4 is a flow diagram showing the procedures followed by the two concurrently running processes of FIG. 3. Process 1 first waits for disc controller 10 to be idle so that process 1 can read from disc into its buffer area. The wait for disc ready is not an explicit test for an idle condition of disc controller 10 but is instead a synchronous read of a first pipe that is written by process 2 when its read of disc is completed. Since the read of pipe 1 is synchronous, the read request returns to process 1 only after process 2 has signaled disc ready. Process 1 then reads from disc to buffer 1. This synchronous read returns to process 1 only after buffer 1 has been filled so that the disc is ready. Process 1 then signals disc ready by writing an appropriate control character to a second pipe. Process 1 is now ready to write to tape, and waits for tape ready by reading pipe 1 for a control character placed there by process 2 after its write to tape. Following the receipt of tape ready, process 1 writes buffer 1 to tape, then signals tape ready by writing an appropriate control character on pipe 2 to be read by process 2 before writing buffer 2 to tape. Process 1 then completes the loop, reiterating the above steps.

Process 2 executes a sequence of operations similar in all respects to that of process 1 except that process 2 reads from pipe 2 and writes on pipe 1 in order to communicate with process 1. Also, of course, process 2 has its separate buffer area.

Omitted from FIG. 4 are the initialization steps performed by the processes prior to entering the main copying loop as well as the termination steps undertaken after copying is complete. Also omitted are end-of-file tests within the main loops of process 1 and process 2 to determine when copying is complete.

FIG. 5 is an illustrative timing diagram that shows time overlap of the read and write operations. The top horizontal line corresponds to read and write activities undertaken by process 1. FIG. 5 shows the case where the write operation is of longer duration than the read operation and illustrates that copying can take place no faster than the slower operation permits. Thus process 1 writes, then process 2 writes, then process 1 writes and so forth. Alternating reads by the two processes overlap the writes. Brief periods of delay appear between each read and write operation by the same process. These account for delays incurred by program execution time, disc latency, tape inter-record gap creation, and so forth. At the end of each read and write operation a vertical arrow shows the time and direction of the interprocess "ready" signal that provides notification to the other process.

The illustrative embodiment set forth in the figures shows copying from disc to tape. However, the present invention is not limited to this application, but may be employed to copy data from any source to any destination or from any device to any other such as from tape to disc, disc to disc, punch card to printer, paper tape to display screen, low speed memory to high speed communication line, or any other similar or dissimilar I/O devices wherein double buffered overlapped I/O may be desirable.

The APPENDIX contains a computer program embodiment illustrative of the present invention. The program is complete and is written in the C programming language (See The C Programming Language, by Kerninghan and Ritchie, Prentice-Hall, 1978). It may be executed under any of several time-shared operating systems commercially available including, for example, an operating system available from American Telephone and Telegraph Company under the tradename UNIX. Suitable computer system hardware is commercially available from Digital Equipment Corporation, ("DEC") marketed under the tradename PDP 11/70.

The computer program in the APPENDIX may be typed directly into the system and stored in a file given the name "program.c". This program then may be compiled using the C language compiler by giving the command line:

which causes the operating system to compile the program and place the executable result in an output file named "program". The program may then be executed by giving the command line:

which causes the operating system to execute the program appearing in the file named "program" while using a device named "/dev/rrp0" as input (typically a disc device, e.g. DEC Model RP06) and a device named "/dev/rmt0" as output (typically a tape device, e.g. DEC Model TE16). Execution will result in two concurrently running processes that will copy from disc to tape in the manner described above. The program will not be described in detail.

Line 1 reserves a buffer area of 25,600 characters.

Lines 2 and 3 reserve four integer storage locations with names pipe1.sub.-- r, etc.

Line 4 reserves two integer locations for the storage array yyy.

Line 5 reserves four integer storage locations with the names process.sub. id, etc.

Line 6 begins the main program which extends from line 7 to line 43.

Line 8 is the first executable statement of the program. Line 8 is a request to the operating system to create a first pipe, pipe 1, which will later be used for interprocess communication. Identification numbers called file descriptors will be returned in the two locations of array yyy.

Line 9 obtains the file descriptor of the read side of the first pipe from array yyy and stores it in storage location pipe1.sub.-- r. Line 10 obtains the file descriptor for the write side of the first pipe and stores it away in the storage location pipe1.sub.-- w.

Line 11 is a request to the operating system to create a second pipe, pipe 2. Lines 12 and 13 store away the read and write file descriptors of the second pipe in storage locations pipe2.sub.-- r and pipe2.sub.-- w, respectively.

Line 14 is a request to the operating system to write two characters into pipe 1, a first character "r" followed by a second character "r". These two characters indicate, respectively, that the input device is ready for reading and that the output device is ready for writing, thereby initiating the first copy operation of the main loop of process 1.

Lines 15 and 16 assign the values 0 and 1 to the variable storage locations "input" and "output", respectively, The variable "input" is used as the file descriptor for the standard input in the read statements appearing in lines 23 and 35--a disc device having the name dev/rrp0 in the above suggested use. The contents of the variable "output" are used as the file descriptor for the standard output in the write statements at lines 26 and 38--a tape device having the name /dev/rmt0 in the above suggested use.

Line 17 is a request to the operating system to fork and return a process identifier in the variable location process.sub.-- id. A "fork" system request causes the operating system to create a new, concurrently operating process virtually identical in all respects to the process that requests the fork. After the execution of line 17 there are two independent concurrent processes in operation, two independent instances of the program shown in the APPENDIX. The only important difference between the two processes is the contents of the location process.sub.-- id. Each process can read and write the same files and the same pipes using the same file descriptors. As a result of the common file descriptors, a sequence of read requests by the two processes yields a sequence of data in the order it appears in the input file. Each process has its own copy of each storage location, as well as its own area reserved for a 25,600 character buffer.

Line 18 tests the process.sub.-- id to determine if it is equal to 0. For the newly created (child) process, process.sub.-- id will contain 0. As a result, the child process (process 1 in FIG. 4) will execute the statements appearing in lines 19 through 29.

Line 30 is an "else" statement, the companion to the "if" statement of line 18. In the original process (parent), process.sub.-- id contains a non-zero value. Therefore, the parent (process 2 in flow chart of FIG. 4) will skip from line 18 to the statement at line 31 and execute the program statements appearing at lines 31 through 41.

Lines 19 and 20 are requests to the operating system to close pipe 1 for writing and pipe 2 for reading, respectively. These two lines are executed only in process 1. Process 1 will send signals to process 2 by writing to pipe 2 and will receive signals from process 2 by reading from pipe 1. The unused means of access to these two pipes are closed off.

Lines 31 and 32 close pipe 1 for reading and close pipe 2 for writing. These two lines are executed only in process 2. Process 2 will signal process 1 by writing to pipe 1 and will receive signals from process 1 by reading from pipe 2. The unused means of access to these pipes are closed off.

Line 21 is executed only in process 1. The "while" statement is an iteration statement that causes the statements at lines 22 through 27 to be executed in sequence and then repeated over and over. This is the main copy loop of process 1.

Line 33 is executed only in process 2. This iteration statement causes the statements at lines 34 through 39 to be executed repeatedly to form the main copy loop of process 2.

The six read and write statements appearing at lines 22 through 27 correspond to the six steps of the flow diagram for process 1 appearing in FIG. 4. The six read and write statements appearing at lines 34 through 39 correspond to the six steps in the flow diagram for process 2 of FIG. 4. The read statement of line 23 is enclosed by an "if" statement which is the end-of-file test for termination of the copy operation. If the read statement in line 23 returns a value less than or equal to zero the end-of-file condition of the "if" statement is met and the "break" statement is executed. This causes control to drop out of the "while" loop and proceed to line 29.

Line 29 is a request to the operating system to terminate the current process, process 1, after closing all open files, thus providing a graceful exit for process 1 when data to be copied from the input device has been exhausted.

Similarly, line 35 contains an "if" statement that causes a "break" upon end-of-file for process 2. Line 41 is executed on end-of-file and process 2 is terminated after all open files are closed.

Line 22 reads one character from pipe 1 and places it in location xxx. During the first execution of the copy loop the first character read is the first "r" placed in pipe 1 by the statement at line 14. During subsequent iterations of the copy loop, the character read by line 22 is the "r" written by the statement at line 36 by process 2 upon completion of the read at line 35.

Line 23 includes a read statement that reads 25,600 characters into the buffer area of process 1 from the standard input.

Line 24 is executed after the completion of line 23 and writes a single character into pipe 2 to signal read completion. This character is read by process 2 at line 34 which reads a single character from pipe 2 and places it in location xxx. This character signals process 2 to begin the read at line 35.

Line 25 reads a character from pipe 1 and places it in location xxx. The first time statement 25 is executed, the character read is the second "r" placed in pipe 1 by the write statement at line 14. During subsequent iterations line 25 reads a character placed in pipe 1 by process 2 by the write statement of line 39 upon the completion of the write statement at line 38.

Line 26 writes 25,600 characters from the buffer of process 1 to the standard output.

Line 27 then writes a single character to pipe 2 to indicate write completion. This character is read by process 2 with the statement at line 37, and signals process 2 to begin the write at line 38.

It is understood that the above-described embodiment is merely illustrative of the principles of my invention; other arrangements may be devised by those skilled in the art without departing from the spirit and scope of the invention.