[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

RE: The history of the term "to block on a channel"

On yield


âYieldâ implies to give way and that one person/process therefore has priority over another.


Norway, in driving, has an additional yield concept that doesnât exist in other places (and certainly not the UK) â the inverted Y sign which instructs drivers to merge (yield) in turn where two lanes turn into one. So I donât know if Oyvind thinks of âyieldâ as being symmetric whereas in the UK there is more of a nuanced âpriorityâ in the concept of yield.


Occam channels are a synchronisation point, but that doesnât mean they are synchronous â there is no clock tick â they are asynchronous in that the communication takes place at some point when both ends of the communication are ready, and it is not determined in advance which one is ready first.


I was in Zurich the last couple of days and it was pointed out to me that Swiss politics are based on consensus; Occam channels strike me more as âconsensusâ than âyieldâ. Consensual Communications, maybe?



Tony Gore


Aspen Enterprises Limited email  tony@xxxxxxxxxxxx

tel +44-1278-761000  FAX +44-1278-760006  GSM +44-7768-598570 URL: www.aspen.uk.com


Registered in England and Wales no. 3055963 Reg.Office Aspen House, Burton Row, Brent Knoll, Somerset TA9 4BW.  UK





From: Marc Smith [mailto:mlsmith@xxxxxxxxxx]
Sent: 26 September 2014 13:29
To: Teig, Oyvind BIS
Cc: Kerridge, Jon; tony; occam-com@xxxxxxxxxx; Ãyvind Teig (oyvind.teig@xxxxxxxxxxx); David May (dave@xxxxxxxxxxxxx)
Subject: Re: The history of the term "to block on a channel"


Hi Oyvind,


I think you have hit upon a significant language barrier when we discuss channel communications outside of our CSP community. Even though I have heard the phrase "to block on a channel" I never really thought of it as blocking. Not to add another term to the mix -- but what you describe as yielding, I thought of as synchronizing. Every communication over a 1-to-1 channel is a synchronization between two processes. When one process reads what another process has written to a channel, they are synchronizing on that event. 


To communicate is to synchronize. We already use the term synchronous to describe our channels. What I like about synch'ing versus yielding is a little nuanced. To yield is an intentional act ("after you...", "no, after you...", etc.), which may take away from the intentional act of reading or writing. Yielding is something that may happen to a process if it attempts to read or write, and the process on the other end isn't ready to reciprocate. 


On the other hand, when I think of synchronization, I think of it as what happens as a matter of course when a process attempts to read or write to a channel. The synchronization is built-in, by definition of communicating over a synchronous channel.


So that's the difference to me between yielding and synch'ing. It is admittedly a nuanced difference, and I don't know that I ever articulated it before, to myself, or anyone else. So, thank you for that.  :-)


The term blocking never bothered me because I just understood it in the sense of synch'ing. But I see your point about impressions this terminology unintentionally makes on the rest of the concurrency community. 




On Fri, Sep 26, 2014 at 7:41 AM, Teig, Oyvind BIS <Oyvind.Teig@xxxxxxxxxxxxxxxx> wrote:

Good idea!


         So wait and signal are pairs by Dijkstra

         But send and receive would be the word-pairs of channels, and block an extra dimension.

         So to call this wait, as suggested by Roger, I donât know. It interferes with the Dicjkstraâs name space. But that may be ok, of course. Language isnât that rigid. And Dijstra is dead

         But I still keep yield/wait in a 6/4 liking!?




Fra: occam-com-request@xxxxxxxxxx [mailto:occam-com-request@xxxxxxxxxx] PÃ vegne av Kerridge, Jon
Sendt: 26. september 2014 13:18
Til: tony; Teig, Oyvind BIS; occam-com@xxxxxxxxxx
Kopi: 'Ãyvind Teig (oyvind.teig@xxxxxxxxxxx)'; 'David May (dave@xxxxxxxxxxxxx)'
Emne: [External] RE: The history of the term "to block on a channel"



Of course if we go back even further there were semaphores to which Dijkstra gave the names P and V for the operations on semaphores and as I understand it P and V were the first letters of the Dutch words for wait and signal.


Just a thought.


Any way in my book which is about to be published I have the following description of channel communication between processes: 


"A channel is the means by which a process communicates with another process.  A channel is a one-way, point-to-point, unbuffered connection between two processes.  One process writes to the channel and the other reads from the channel.  Channels are used to transfer data from the outputting (writing) process to the inputting (reading) process.  If we need to pass data between two processes in both directions then we have to supply two channels, one in each direction.  Channels synchronise the processes to pass data from one to the other.  Whichever process attempts to communicate first waits, idle, using no processor resource until the other process is ready to communicate.  The second process attempting to communicate will discover this situation, undertake the data transfer and then both processes will continue in parallel, or concurrently if they were both executed on the same processor.  It does not matter whether the inputting or outputting process attempts to communicate first the behaviour is symmetrical.  At no point in a channel communication interaction does one process cycle round a loop determining whether the other process is ready to communicate.  The implementation uses neither polling nor busy-wait-loops and thus does not incur any processor overhead."



Don't worry I will tell every one when the book is actually available!










Professor Jon Kerridge
School of Computing
Edinburgh Napier University
Merchiston Campus
Edinburgh EH10 5DT


0131 455 2777


From: occam-com-request@xxxxxxxxxx [occam-com-request@xxxxxxxxxx] on behalf of tony [tony@xxxxxxxxxxxx]
Sent: 26 September 2014 09:19
To: Teig, Oyvind BIS; occam-com@xxxxxxxxxx
Cc: 'Ãyvind Teig (oyvind.teig@xxxxxxxxxxx)'; 'David May (dave@xxxxxxxxxxxxx)'
Subject: RE: The history of the term "to block on a channel"

Hi Oyvind


I think it was a common term in use by April 1986 when I joined Inmos. I think some terms in common use were used a bit loosely. A channel that was waiting for the other end of the communication to become ready âblockedâ the process from proceeding. Thus my recollection is that âblocking on a channelâ was commonly used to describe a process that couldnât proceed until the communication could proceed.


I think you have to remember that at the time the transputer came out, lots of people got their hands on it and started parallel programming. Many of these were engineers, without computer science backgrounds, and so made up the terminology as they went along.


In my own case, I had been programming real time systems (engine controllers, antilock braking etc) in assembler and having graduated in 1975 with a degree in electronic engineering and physical oceanography, the only formal computer education I had was a 3 day course from the Maths department at university where they had the foresight to teach the engineers Algol instead of Fortran, and some timeshare Basic I had picked up as I went along in order to do a few assignments.


So when I got to Inmos, I came across terms like âcritical sectionsâ and realised that I had been implementing these things in assembler but without knowing the terms or the formal principles behind them. For me, suddenly in Occam I had a language that described pretty much what I wanted to do. It was my observation that engineers found Occam easier than computer scientists because the CSP model was so similar to engineering â black boxes and wires, glitches, race conditions etc.


When I moved to Inmos France, I had to find out what people used commonly to describe transputer and Occam related terms in French because they had yet to reach any (computing) dictionary.


So I think that in answer to your question, there are a raft of âformalâ terms that were described in the books, but there is also a second group of âinformalâ terms that people used to describe things â some are synonyms (equivalent words) to the âformalâ terms, but others had slightly different meanings.


This is actually common practice in English â one of the reasons the English language has such a large vocabulary is that English frequently adopts words from other languages (maybe Anglifying them in the process) to express a slightly different meaning to a word we already have. Over time, that meaning may well change. This is why, when the English are learning French, there are so many words we class as âfaux amisâ â false friends â because they sound/look like a French word so we think that it has the same meaning in French. (see http://www.oxfordlanguagedictionaries.com/Public/PublicResources.html?direction=b-fr-en&sp=S/oldo/resources/fr/Difficulties-in-French-fr.html for some examples)


So I cannot give a direct answer to your question, but hope that this information might point you or others into pinning down the origin or original meaning.


Best regards



Tony Gore


Aspen Enterprises Limited email  tony@xxxxxxxxxxxx

tel +44-1278-761000  FAX +44-1278-760006  GSM +44-7768-598570 URL: www.aspen.uk.com


Registered in England and Wales no. 3055963 Reg.Office Aspen House, Burton Row, Brent Knoll, Somerset TA9 4BW.  UK




From: occam-com-request@xxxxxxxxxx [mailto:occam-com-request@xxxxxxxxxx] On Behalf Of Teig, Oyvind BIS
Sent: 26 September 2014 07:27
To: occam-com@xxxxxxxxxx
Cc: 'Ãyvind Teig (oyvind.teig@xxxxxxxxxxx)'; 'David May (dave@xxxxxxxxxxxxx)'
Subject: The history of the term "to block on a channel"




When was the phrase âblocking on a channelâ introduced and by whom? Hoare does not use it in his 1985 book. Roscoe almost does not use it, or I would say, he does not use it at all in this context in his version of the book thatâs PDFed. If this group does not know this, none will.


I am suggesting using âto yield on a channelâ rather than âto block on a channelâ. I have a blog note about it [1] and there is a discussion thread on golang-nuts [2]. I include the figure here (and the intro text in golang-nuts):

Figure 2

Readers of golang-nuts know that âblocking is fine in Goâ. But often, when I talk with other programmers I would hear that âblocking is evilâ. I suggest that we go over to saying that âyielding on a channel is fineâ. Iâll explain: 


The literate meaning of blocking is about something we donât want. It means I want to go somewhere but am stopped or delayed so I arrive too late. Or a door is blocked, in which case we must unblock it, hopefully without a bulldozer. Since this semantics outnumbers the people who understand CSP-based channel semantics we have an explanation problem.


With an explanation problem follows a mission problem.


Tell a basically single-thread programmer in C++ that blocking is good and you ask for much. His attention to try to understand something rather new, even if heâs used to linux select. Because often the code that does this linux select also does other rather independent matters. And itâs in his spec that these other matters also need to complete. And when you block on one matter itâs easy to see blocking as something evil. Because he or she is right in their own mind.


So which âblockingâ do you mean?

1.     âBlocking on a channelâ or some shared resource controlled by a non-blocking algorithm. I believe these may be in the same group, ref. the Wikipedia page about Non-blocking algorithm

2.     âBlockingâ away other required functionality

3.     âBlockingâ as in deadlock, where the system cannot proceed, where there is a cycle in the dependency tree

We already have good words for 2. = blocking as is, and 3 = deadlock. But we reuse blocking for 1.) which is not optimal. As said, I suggest 1. = yielding. This is an implicit yield that the application doesnât have control of. Not the explicit yield that some operating systems would supply in the API. The channel semantics as implemented in the scheduler does it for us.


What do you think of this? If we start to write âto yield on a channelâ or âyielding on a channelâ it could slowly creep into our language. And the C/C++ (and even Scala or Erlang) people would give us an ear. Especially if we agree with them that blocking is evil.


(I alse dare take comments on the idea.. Here, there or there)


[1] - http://www.teigfam.net/oyvind/home/technology/092-not-so-blocking-after-all/

[2] - https://groups.google.com/forum/#!topic/golang-nuts/OSBU8wjlES8


Med vennlig hilsen / Best regards

Ãyvind Teig

Senior utviklingsingeniÃr, siv.ing. / Senior Development Engineer, M.Sc.
Autronica Fire and Security AS
Research and Development 

UTC Building and Industrial Systems
Phone: +47 735 824 68
(Also work-related)