General Points

Given a segment S and a program R with read-only access to S it appears impossible to interpose a program E between S and R. (The 68010 supports this!)

By this we mean that we do not know how to construct a program E such that if E is given read access to S, E can construct a new capability that will satisfy R as well as S does. (When we have thought about this problem for a while we will try for read-write access.)

Although we fail to solve the general problem, the incomplete attempts described below are a source of ideas for specialized solutions.

General Points
As a concrete example we postulate a machine M1 with an operating system that supports shared read-write access to core memory. In M1 is a program W with write access to S and another program R with read-only access to S. W and R have been designed together but R was denied write access to S in order to prevent errors in R from impacting other functions of W and S. Neither W nor R make assumptions about the scheduling of W and R. W and R communicate only thru S.

We now wish to cause R to operate on a new machine M2. We assume that the operating system on M1 can support access to a communications facility by a program on M1. We assume that the operating system on M1 may not be extended beyond what we have now described.

We now wish to install a program E in M1 that is given read-only access to S and access to a communication link to M2. We can make any assumptions about the operating system in M2 that we know how to implement. How are we to design E and the operating system in M2 so that R may be executed in M2 without modification to R?

We shall impose a few performance restrictions on the problem as we go. If we were willing to cause M2 to simulate each instruction of R and request of E each storage location value as R was interpreted, R would run, but 5 orders of magnitude slower than on M1.

We shall ease some of the restrictions without coming to an entirely satisfactory solution.

In this section we present a tree of partial solutions. At the root of this tree {i.e., in common to all of the schemes} is the idea of a cache of pages at M2 that appear directly in R's address space. The program whose logic we are designing is able to add and remove pages from this cache and to gain control when R references a page that is absent from the cache.

Single Page Segment
Assume first that S consists of a single page. E must make a copy of S for transmission {otherwise the problem gets even harder}. Making a copy of S is an interruptible operation even on machines with a single command to copy a page. If E is interrupted after field i has been copied but before field j has been copied, W may run and change i and then j before E resumes the copying. In this case the old value of i is transmitted with the new value of j. The logic of R may observe the new value of j and thereby expect the new value of i. This logic would be correct if R were running in M1. We have thus not provided an environment in M2 like that in M1.

Multi-Page Segments
We could violate our rule and ask for a new operating system primitive in M1 to make an instantaneous copy of a page, but now the problem reappears for multipage segments. If a segment won't fit in core it is a bit much to ask the kernel of the operating system to make an instantaneous copy. We will discuss virtual {instantaneous} copies later.

Monitoring Reference Order at M2
The above scheme failed because of the order that R fetched values from the cache at M2. If we got our M1 RPQ to provide consistent pages and prohibited R from accessing pages in the cache except in the order that they were copied an interesting class of programs would run successfully. This means, in effect, that only one page of S is accessible to R at a time. When R refers to an earlier page it must be retransmitted, or ascertained that it has not changed. If an out of date image of S is to be tolerated and the sequence of page references to S can be anticipated by E, E might make instantaneous copies of pages in S in the anticipated order, record any changes (typically none) and signal M2 the results whereby M2 can allow R to proceed with this sequence of references. This scheme is of limited use due to the requirement of anticipating the order of references.

An immediate extension of this scheme allows R to run with n pages with the help of another M1 primitive to make instantaneous copies of n pages at once. This scheme works if the headway made by R between page faults is large compared with the cost of making the copies. Such is not always the case.

Cache Theory
The cache must present a consistent image of S at M2. We might or might not require the image to be up to date but we require it to be consistent unless we consider the program logic of R. The cache is consistent if it consists of a snap-shot of S between instructions of W. This means that all stores by W prior to some point of W's history have taken effect in the cache and that no subsequent stores have taken effect. {Actually the 370 manual allows itself more latitude than this even between programs running on 2 processors in one configuration. One program may see a partially completed store, but all parts of one store will precede all parts of a subsequent store by the same processor.} The above requirements are, of course, relative only to the pages in the cache. We can choose to delete the page from the cache in lieu of transmitting the changed data. This note concentrates on discovering that the change has in fact taken place. In order to purge the data E must discover that some page of S has changed. If E were infinitely faster than any other program in M1 it could notice all changes to S and the order in which they were made. E could signal M2 to purge obsolete pages and thus avoid inconsistent views of S at M2.

Except for performance it would suffice for E to be able to make an instantaneous copy of all pages at M1 that correspond to pages in the cache at M2. This effort is quadratic in the working set size however.

Another way of describing the difficulty is to note that having read access to S is not sufficient to sense the order of changes to S but this order must be preserved in the changing image of S maintained at M2.

Fancier “Read-Only Access”
We study here two elaborations of the concept “read-only”.

Page Versions

This scheme invents a strange new key, the (_page version key). There are two primitive operations associated with this facility; (_Record version) produces a page version key for a page that the caller designates. The caller must have read access to this page. (_Compare version) takes a page version key and determines whether it is still current. In this call the caller must present the page version key and designate the page again, to which he must still have read access. If anyone has exercised store access to this page between these calls the version key will not be current, otherwise the key will be current and can be used for another “compare version” call. An extension of this would be for the version key to function as a memory key while the page remains unchanged.

These primitives are strange and may be difficult to implement. But they provide no extra information to the holder of the capability that could have otherwise been considered as safely hidden. These functions can be provided to segments by segment keepers. This may not provide sufficient performance in the critical applications mentioned here.

One scheme that uses these primitives is as follows:

E keeps a page version key for each page in the cache at M2. Every time a new page is demanded at M2, E creates a page version key for that page, adds that to its list and then copies the page and transmits it. M2 incorporates the new page in the cache but R is not restarted yet. E then checks all page version keys (including the new one) and signals M2 to delete any that are not current. R may now be restarted. This scheme causes R at M2 to run on stale data but the changes to S that R sees are at least in the right sequence.

Elaborations on this scheme may limit the degree of time lag that R sees.

Prior Change Notification
General Points
The phrase “subject to change without notification” is symptomatic of our problem. If the reader could get prior notification of a change then E could signal M2 to purge a page just before it became invalid. The image at M2 would not only be faithful but up to date {as far as it goes}.

The ability to demand prior notification, however, is far more than the ability to read. If such an ability were replicated widely then the primitive page construct would find itself burdened with remembering a list of indefinite length of programs to notify. Further there is the dilemma of how to notify. Passive notification merely sets a bit and waits for the notifyee to notice it. This is clearly no better than the previous scheme. The other sense of notification is to wait for acknowledgment from the notifyee. If the notifyee is buggy or malicious the acknowledgment may never come. At this point we have allowed the reader enough power to entirely block the progress of the writer of the segment. This is only marginally less serious than destroying W.

Several schemes have been proposed to ameliorate these problems.

One Waiter
This is to limit the number of notifyees to 1. This convention is agreed upon by the holders of the capability. The capability to read a page would not be entirely duplicable. If such a capability were duplicated the users would have to coordinate among themselves to insure that only one of them was requiring prior notification at one time. This restriction is sufficiently severe that there appears to be no reason for duplicating such read access. On the other hand it appears possible to build programs that given such a read capability, can provide the effect of such a capability to several other programs that require such a read capability. This strategy has the drawback that such a program must be put in place each time a read capability of this kind is copied. This in turn leads to the situation that a copy of a copy ... of a copy of a read capability must involve n programs each time the prior notification function is invoked. Some of the resources of those intermediate programs may have disappeared, thereby canceling the access and killing the writer.

Time-Outs
The problem of blockage can be partly eliminated by installing time-outs. One way to do this is for the segment owner to provide an intermediate program that holds the real read capability and for this program to serve others who require a read capability. The extra program could enforce time-outs beyond which the acknowledgment would be declared lost and the writer could resume. The burden of choosing this time-out and contemplating the consequences of its breech are problems that the first solution does not have.

Certified Prompt
When prior notification is requested of a page, a start key is presumably provided. This start key is to be invoked before the page is allowed to change. One way of guarding against blockage is to restrict these to start keys to prompt programs. Such a restriction will limit the algorithms behind the gates. One particular scheme would be as follows:

A trusted program CPE (certified prompt keys) will produce on demand a start key that is widely trusted to be prompt. CPE always provides the code for the program behind the start key. The start key will only do a very small class of operations. One such operation might be the rescinding of a capability. Another might be to enqueue a short message on a communication link. These two types of prompt key support the cases that have motivated the design of the system.

A class of difficulty in this approach is in CPE determining that the capabilities handed to it are indeed quickly executed. For example a capability to rescind access may not be manifestly prompt to CPE. CPE might establish a time-out, but this is itself time consuming.

Another general problem is the qualities of any performance guarantee is a thing of many parameters. The caveats to the guarantee include: disk controller being up, schedulers (user replaceable?) doing what they advertise, etc.

Either of the two above schemes can be implemented with the help of a segment keeper if the station of the segment keeper has not been used for another function.

It turns out (we think) that the read-write access introduces only a few wrinkles to the read-only situation. We first examine some pathology that IBM allows its multiprocessor configurations to get away with (justifiably I think).

Imagine program 1 on processor 1: (STORE 10000; FETCH 20000) and program 2 on processor 2: (STORE 20000; FETCH 10000). We say that program 1 sees program 2 if 1's fetch from 20000 gets the value stored by 2's store. Likewise for 2 seeing 1. We might naïvely imagine three possible orders of execution: 1 sees 2 but 2 doesn't see 1, 2 sees 1 but 1 doesn't see 2, or 1 and 2 see each other. On a 370 it may be that neither sees the other. We believe that real 370's limit this effect to time scales of a few microseconds; the hardware caches never hold the only valid value for some real storage for more than a few microseconds.

It is possible to eliminate this effect by not running two processes with write access to the same page at once. We do not intend to judge whether the expense of this restriction is worthwhile, but merely to point out that programs may exist that assume that it will not occur. Such programs will work in multiprogrammed systems with a single processor and on multiprocessor systems if the delay between the store and fetch is larger than a few microseconds.

Some strategies for supporting distributed access to segments might take the same latitude as the 370 but allow much larger “skews” in time.

Such latitude merely says that stores of one program take place in the correct order as seen by any other program.

Programs written in strict accordance with the 370 design would work in this environment. But some programs that would work on any real 370 would fail in this environment.

This scheme requires trapping the 370 instructions that are designed to synchronize processes, CS, CDS, TS and the synchronizing NOP.

The alternative to taking this latitude is to say that conceptually only one program is allowed to have write access to the data at once. See (p3,synseg).

In Gnosis a segment may be created with a segment keeper. The segment keeper can: place any page of its choice in the segment, make a given page invalid, read-only or read-write. The segment keeper is activated when a page fault occurs by virtue of access to an invalid page of the segment or a store access to a read-only page. The segment keeper is in a position to implement any of the above strategies except trapping CDS, CS and TS. Any accessor of such a segment is at the mercy of the segment keeper with regards to being blocked. This fact does not solve the problem in general because the position of the segment keeper may be filled by a program responsible for some other function. Similarly the creator of the segment may not have anticipated the requirement when the segment was created.