Return-Path: <P.H.Welch@ukc.ac.uk>
Date: Tue, 17 Dec 96 11:11:16 GMT
From: Peter Welch <P.H.Welch@ukc.ac.uk>
Message-Id: <9612171111.AA07018@mint.ukc.ac.uk>
To: occam-com@ukc.ac.uk
Subject: Distributed shared channels (via SEMAPHOREs)
status: RO
Dear All,
Here's how to implement a SHARED channel over a distributed-memory system (such as a network of workstations or transputers) using SEMAPHOREs.
Here is an example SHARED channel in occam3:
CHAN TYPE COMMS
RECORD
CHAN OF REQUEST request:
CHAN OF REPLY reply:
:
SHARED COMMS c:
The SHARED channel has two components: the REQUEST field carries information from a client to the server and the REPLY field carries answers. [In general, occam3 permits a SHARED channel any number of components; in practice, given occam2 variant PROTOCOLs, only two are ever necessary.]
In occam2.1, we don't have the CHAN TYPE and have to declare separate channels:
CHAN OF REQUEST c.request:
CHAN OF REPLY c.reply:
Now, SHARED channels connect any number of client processes to a single server process. Clients have to queue for exclusive access to the server.
In a distributed system, clients may be placed on many processors and the trick is to maintain a distributed queue. If the processors do not share a unified memory space, we need to do some work ... though not too much. In the (late lamented) T9000 transputer, the `distributed' queue is held entirely on the processor containing the server of the SHARED channel (as a queue of RESOURCE channels, one for each client process). We are going to do it with SEMAPHOREs and the queue really is distributed.
Consider a processor containing some of the clients of the SHARED channel. For simplicity, suppose it only contains such clients:
PROC client.processor (VAL INT my.processor, n.clients, SHARED COMMS c)
--{{{
PAR n = 0 FOR max.clients.per.processor
IF
n < n.clients
client (n + 1, my.processor, c)
TRUE
SKIP
--}}}
:
The above is occam3 code for placing on a remote processor. The code allows the easy creation of remote processors carrying different numbers of clients (which happen, in this example, to be identical). We have to set a compiler known `max.clients.per.processor' for the usual reasons. The `n + 1' and `my.processor' values are passed on to the clients for information and have nothing to do with the operation of the SHARED channel.
For the SEMAPHORE implementation of the distributed SHARED channel, we need one (virtual) link from each processor-with-clients to the processor holding the server. The clients on a remote processor queue up on a local SEMAPHORE to gain access to this virtual link. Here is the occam2.1 version of the code for the remote client processor:
PROC client.processor (VAL INT my.processor, n.clients,
CHAN OF REQUEST request, -- the SHARED
CHAN OF REPLY reply) -- channel-pair
--{{{
#PRAGMA SHARED request
#PRAGMA SHARED reply
SEMAPHORE s: -- local SEMAPHORE on which local clients queue
#PRAGMA SHARED s -- to use the shared request-reply channels
SEQ
initialise.semaphore (s, 1)
PAR n = 0 FOR max.clients.per.processor
IF
n < n.clients
client (n + 1, my.processor, s, request, reply)
TRUE
SKIP
--}}}
:
To follow the behaviour of the client, we need to know the PROTOCOLs. Suppose:
PROTOCOL REQUEST
CASE
string; BYTE::[]BYTE; INT -- any number of these
integer; INT; INT -- in any order.
end.transaction -- finish with this
:
PROTOCOL REPLY IS BOOL: -- returned by server after each string/integer
Each client makes periodic CLAIMs on the SHARED channel. An occam3 example is:
PROC client (VAL INT n, my.processor, SHARED COMMS c)
--{{{
INT logical.time:
SEQ
logical.time := 0
WHILE TRUE
SEQ
... wait n seconds
CLAIM c
--{{{ transact business with server
BOOL any:
SEQ
c[request] ! integer; logical.time; 0
c[reply] ? any
... further possible business
--}}}
--}}}
:
In occam2.1, we make one difference to the implementation of the CLAIM from that described for the non-distributed SHARED channel. The CLAIM body now opens with an extra output, signaling (to the other side) that we are ready for the start of play:
PROC client (VAL INT n, my.processor,
SEMAPHORE s, -- this is
CHAN OF REQUEST request, -- the SHARED
CHAN OF REPLY reply) -- channel-pair
--{{{
INT logical.time:
SEQ
logical.time := 0
WHILE TRUE
SEQ
... wait n seconds
--{{{ claim the shared channel
claim.semaphore (s)
--}}}
--{{{ start-of-play signal
CHAN OF INT request RETYPES request:
request ! 0
--}}}
--{{{ transact business with server
BOOL any:
SEQ
request ! integer; logical.time; 0
reply ? any
... further possible business
--}}}
--{{{ release the shared channel
release.semaphore (s)
--}}}
--}}}
:
Note that this `start-of-play' signal just needs an output component of the SHARED channel and is independent of its protocols. This would be no bad thing to include in any case for a non-distributed CLAIM - since it makes the generated code independent of distribution and guarantees a signal that always enables the server to ALT (even if the transaction proper opens with a communication from the server to the client).
On the processor containing the server, there will be an array of external (virtual) channel-pairs - one from each processor that holds clients. These channel-pairs are handled directly (one at a time, of course) by the server, but only after the server has been granted access by one of an array of small `client.proxy' processes. These proxies also handle the (incoming) virtual channels, but not (of course) at the same time as the server. The sharing of an incoming virtual channel between its managing proxy and the server is managed by normal channel synchronisation and not by a SEMAPHORE.
Here is occam2.1 code for a processor containing only the server for a single distributed SHARED channel:
PROC server.processor ([]CHAN OF REQUEST request, -- the SHARED
[]CHAN OF REPLY reply, -- channel-pair
CHAN OF BYTE out)
--{{{
#PRAGMA SHARED request -- shared between the proxies and the server
-- (note: this sharing is not controlled by
-- a SEMAPHORE, but by taking turns that
-- are synchronised through normal channel
-- communications)
SEMAPHORE grant.s: -- controls access to the grant channel
#PRAGMA SHARED grant.s -- between the local proxies
CHAN OF INT grant: -- this is the SHARED channel between the
#PRAGMA SHARED grant -- local proxies and the server
SEQ
initialise.semaphore (grant.s, 1)
PAR
--{{{ local proxies
PAR n = 0 FOR n.client.processors
CHAN OF INT request RETYPES request[n]:
client.proxy (n, request, grant, grant.s)
--}}}
--{{{ server
server (grant, request, reply, out)
--}}}
--}}}
:
A picture helps:
_______________________________________________________
| |
| || |
| ----------->----------|| |
| | -------->----------|| |
| | | || grant |
| | | -->----------|| |
| | | | _____||_____ |
| _______ | | | | | |
| -->-| proxy |-->-- | | | | |
| | |_______| | | | | |
rr[0] | | | | | | |
-<-->----------------------------|-----|------| | |
| | | | | |
| _______ | | | | |
| -->-| proxy |-->----- | | | |
| | |_______| | | | |
rr[1] | | | | | | out
-<-->----------------------------------|------| server |---------->--
| | | | |
| . | | | |
| . | | | |
| . | | | |
| _______ | | | |
| -->-| proxy |-->----------- | | |
| | |_______| | | |
rr[n-1] | | | | |
-<-->-----------------------------------------| | |
| | | |
| |____________| |
| server.processor |
|_______________________________________________________|
Note that the proxies are local clients to the server via a (non-distributed) SHARED channel called `grant'. Hence, they need a local `grant.s' SEMAPHORE.
Note also that each proxy is attached only to the incoming external channel and that it is independent of PROTOCOL. This means that these proxies are generic for *any* kind of SHARED channel. They are also very simple:
PROC client.proxy (VAL INT n, CHAN OF INT request, grant, SEMAPHORE s)
--{{{
WHILE TRUE
INT signal:
SEQ
request ? signal -- remote claim
claim.semaphore (s) -- queue up for the server
grant ! n -- tell server where client is located
grant ! n -- wait until server has dealt with client
release.semaphore (s) -- let others get the server
--}}}
:
Initially, `client.proxy' listens to the external `request' and the `server' does not. The `server' is either listening on the `grant' channel or dealing with a client on a line from another processor.
When a signal arrives on the `request' line, this indicates that there is a client on the processor at the other end ready to transact business with our `server'. The `client.proxy' queues up (with other proxies) on the SEMAPHORE guarding the SHARED `grant' channel. When it acquires this SEMAPHORE, it sends its index (supplied as a parameter) down the `grant' channel to the `server'.
The `server' uses this index to commence its transaction on the indicated pair of `request'/`reply' external channels. At this point, the `client.proxy' is not listening on the `request' line (which would cause an error), but is trying to repeat its `grant' communication. This causes it to wait until the `server' has completed its transaction with the remote client, only after which does it accept this second message. The `server' is no longer listening to `request', so it is safe for the `client.proxy' to release the `grant' SEMAPHORE (letting other proxies get at the `grant' channel) and resume listening on `request'.
Here is the `server' code:
PROC server (CHAN OF INT grant, -- this is
[]CHAN OF REQUEST request, -- the SHARED
[]CHAN OF REPLY reply, -- channel-pair
CHAN OF BYTE out)
--{{{
WHILE TRUE
INT processor:
SEQ
grant ? processor -- the server may freely ALT on this shared channel
service (request[processor], reply[processor], out)
grant ? processor -- return control of `request[processor]' to the proxy
--}}}
:
where we have abstracted the actual transaction code into a procedure.
The code for setting up the `server' and the `client.proxy' processes is not user-written, but would be generated by the compiler/configurer. The `server' may, therefore, trust the `processor' value supplied down its `grant' channel.
Note that the `server' listens to an ordinary software channel (`grant'), which tells it on which virtual link lies the processor containing the remote client. Therefore, ALTing over SHARED channels is immediately possible.
Note also that, during the actual transaction, the remote client and server are in direct communication over a single virtual link - there are no intermediate processes slowing things down. The `client.proxy' only gets involved when starting up and shutting down a transaction. The overheads of this are very small and, probably, negligible in comparison to those involved in the remote communication.
For completeness, here is a `service' procedure for a single client-server transaction:
PROC service (CHAN OF REQUEST request, CHAN OF REPLY reply, CHAN OF BYTE out)
--{{{
--{{{ COMMENT note
--This performs a single client-server transaction. It is application specific.
--It is a 2-way transaction just to demonstrate that we can do it.
--}}}
BOOL transacting:
SEQ
transacting := TRUE
WHILE transacting
request ? CASE
BYTE size:
[255]BYTE s:
INT field:
string; size::s; field
SEQ
out.string ([s FOR INT size], field, out)
reply ! TRUE
INT i:
INT field:
integer; i; field
SEQ
out.number (i, field, out)
reply ! TRUE
end.transaction
SEQ
out.string ("*n", 0, out)
transacting := FALSE
--}}}
:
Finally, here are the occam3 equivalents of the above routines. The process that sits on the server processor itself is a bit boring if it only contains the server:
PROC server.processor (SHARED COMMS c, CHAN OF BYTE out)
--{{{
server (c, out)
--}}}
:
The server itself is not that much more interesting:
PROC server (SHARED COMMS c, CHAN OF BYTE out)
--{{{
WHILE TRUE
GRANT c
service (c, out)
--}}}
:
The service procedure is much the same as the occam2.1 version and only given here in outline:
PROC service (COMMS c, CHAN OF BYTE out)
--{{{
--{{{ COMMENT note
--This performs a single client-server transaction. It is application specific.
--It is a 2-way transaction just to demonstrate that we can do it.
--}}}
BOOL transacting:
SEQ
transacting := TRUE
WHILE transacting
c[request] ? CASE
... as before but with `c[reply]' replacing `c.reply'
--}}}
:
Notice that its COMMS parameter is no longer SHARED.
A distributed system demonstrating this SHARED channel may be user-configured through the following table:
VAL INT max.clients.per.processor IS 10:
VAL []INT n.clients IS [4, 2, 8, 5, 3, 4]: -- number of clients per processor
VAL INT n.client.processors IS SIZE n.clients:
and defined with:
[n.client.processors]CHAN OF REQUEST link.request:
[n.client.processors]CHAN OF REPLY link.reply:
PAR
PAR n = 0 FOR n.client.processors
client.processor (n, n.clients[n], link.request[n], link.reply[n])
server.processor (link.request, link.reply, screen)
which occam3 would reduce to:
SHARED COMMS link:
PAR
PAR n = 0 FOR n.client.processors
client.processor (n, n.clients[n], link)
server.processor (link, screen)
The occam2.1 version emulates this distributed system on a single processor and runs immediately under KRoC on its released targets. It produces quite a pleasing display.
It will also run on real distributed systems such as T9000 networks (with the general KRoC "semaphore.inc"), the multi-processor Alpha platforms made by Alpha-Data Parallel Systems Ltd (<URL:http://www.alphadata.co.uk/>) and (when we release it :-) networks of workstations.
Client processes on a remote processor queue on a local SEMAPHORE to access the virtual link connecting its processor to the server processor. When a client has accessed its local SEMAPHORE, it first signals down the virtual link to a proxy process that will be waiting at the server end. Then, it tries to transact its business over the virtual channel, but will be held up until ...
The proxy process, after receiving the signal from the remote client, queues up on a local SEMAPHORE in the server processor to tell the actual server process (using a locally shared `grant' channel) about the remote client. Still holding the SEMAPHORE, the proxy tries to tell it again, which causes it to sleep until ...
The client and server complete their transaction directly with each other. When the server finishes, it clears the signal from the waiting proxy (which releases the `grant' SEMAPHORE and goes back to listening on its virtual link) and listens on the `grant' channel for further work. When the client finishes, it releases its local SEMAPHORE, allowing sibling clients to access the virtual link to the server processor.
So, client processes queue up on a distributed `queue' for the distributed shared channel. The `queue' is made up from real FIFO queues (one in each processor containing clients) that are processed through another real FIFO (of client proxies in the processor containing the server).
Locally, clients are serviced in a FIFO manner (with respect to other clients on the same processor). Globally, clients are guaranteed service ... but not necessarilly a `fair' one and not FIFO.
Consider the service guaranteed to a client on a remote processor. If there are n clients altogether on that processor and p processors overall, service will be obtained, at worst, after (n*p) server-cycles from the client making its CLAIM on the SHARED channel. Note that, if there are more clients than average on this remote processor, (n*p) will be larger than the total number of clients in the system.
Thus, all clients get service guarantees, but clients on processors that are lightly loaded will get a better guarantee than clients on the heavily loaded ones. It's quite possible for a client on the latter to make a CLAIM before a client on the former ... but for the later client (on the former) to be serviced before the earlier client (on the latter). I guess that reflects real life!
A T9000 transputer network could implement a SHARED channel using a combined SEMAPHORE and RESOURCE mechanism.
Remote clients could share one virtual link to the server processor using the SEMAPHORE mechanism described above.
The virtual link at the server end would be mapped on to a RESOURCE channel. That way, we get back to only having one virtual link per remote client processor -- rather than one virtual link per remote client as required by a pure RESOURCE implementation.
Since the T9000 has both SEMAPHORE and RESOURCE instructions, this looks like the best bet. The RESOURCE mechanism at the server end would have slightly lower overheads than the proxy processes and their SEMAPHORE ... but it would be close.
For KRoC, we are a little reluctant to make the effort of modifying the kernel to check channels to see if they are marked as RESOURCE ones (which will add a tiny overhead on normal channel communications) ... given that SEMAPHOREs can do the job and don't need any changes to the kernel. Further, to allow a server process to ALT over SHARED channels, we would have to implement two extra instructions (`enable.grant' and `disable.grant') and get them to work on both real and virtual RESOURCE channels. With SEMAPHOREs, we get ALTing over SHARED channels (real and virtual) for free.
[Has anyone ever tried the T9000 RESOURCE instructions to see if they work?]
In this directory is a set of 9 files for KRoC programs that demonstrate this distributed SHARED channel. There is a README file giving instructions. It includes an extra variation that configures some client processes on the server processor as well as on remote processors. The `server' code needs minimal adjustment to deal with the local clients (which come in over a local request/reply channel-pair alongside the array of virtual ones). You will need to supply "semaphore.inc" and the standard "utils" library from the KRoC release.
Peter.