Help Requested in Defeating Ring Buffer Software Patent
Dave Goldblatt
[ I apologize for the wide distribution (especially if you've seen it before),
but as this could conceivably affect a wide number of people, I figure
it's worth it. Flames to email, please. ]
I am looking for information which could be used to invalidate
a patent which covers one of the most basic techniques in software:
the ring buffer. Specifically, the patent is on the idea of using two
circular buffers in commonly addressable memory to queue pointers to
messages (also in shared memory) between two processors. One buffer
contains messages going in one direction, and the other buffer
contains messages going in the other.
The allegedly inventive feature is having one of the
processors tell the other processor the size of the ring buffers.
I'm looking for code or references to this technique written
before October 5, 1981. An example of dual processor communication
would be ideal, however, inter-process communication via this method
could also prove useful. I know of at least one network adapter which
violates this patent, and also of an Ethernet controller which does as
well, but neither are before the required date. I've also heard that
the CDC 6x00 line used this method -- details would be appreciated.
Any information will be GREATLY appreciated! For better
results, email will be appreciated even more so.
Thanks!
-dg-
--
"We go out in the world and take our | Dave Goldblatt [da...@clearpoint.com]
chances / Fate is just the weight of | Subsystems Software Engineering
circumstances / That's the way that | Clearpoint Research Corporation
lady luck dances / Roll the bones.." - Rush
Howard Bussey
and 7000 series used a circular buffer for I/O. The control structure
was like:
struct CBUFFER {
int *first, *in, *out, *limit;
};
first and limit pointed to the first, and 1 past the last "words" in the
buffer (so the size of the buffer is (limit - first)).
in and out pointed to the next available word for writing and reading,
respectively.
in==out implied the buffer was empty. in+1 == out (in the equivalence
class implied by CBUFFER) meant the buffer was full.
The constraints were first <= {in|out} < limit.
This was used to allow a program to read or write data (even
continuously!). Most of the operating system ran in peripheral
processors (PPs). When an I/O operation was started, with the CIO
(Combined I/O) service, a PP was allocated to the request. It would
poll (yes, poll!) the CBUFFER structure. When (in != out), the PP would
transfer data. So the CBUFFERs were used for inter-processor
communication. Actually, the PPs were only 1 processor, which
time-multiplexed itself each microsecond among 10 or 20 different
contexts, resulting in what looked like 10 or 20 individual PPs (each
with 1 microsecond instruction cycle times).
The SCOPE/KRONOS/NOS operating system may have allowed several
simultaneous and independent transfers. I do know that tape-tape copies
could keep the tapes spinning continuously.
[N.B. IMHO, the 6600 was the first RISC machine! please, discussion
directly to me]
--------------------------------------------------------------
Howard Bussey <how...@thumper.bellcore.com>
Bellcore Room 2P-288/445 South Street/Morristown NJ 07962-1910
voice: +201 829 44 79; fax: +201 829 58 88
Clarence Wilkerson
Most interrupt drive io systems for Z80 's in the late 70's used ring bufferes of some kind. I'm
pretty sure the console io on the Heath-Zenith H89 used this, and the Mostek io modules did
also.
Clarence Wilkerson
Daan Sandee
and as comment on Howard Bussey's response.
Note I have set the followup to comp.sys.cdc, so we old CDC hands can go and
wallow in nostalgia without annoying the rest of the universe further.
There's still stuff that I don't know either that Dave would want to know,
i.e. the real first date, so this is a hint to Dave to keep reading this
newsgroup, as more details may turn up. -- Daan.
In article <8...@salt.bellcore.com>, how...@thumper.bellcore.com (Howard Bussey) writes:
|> The SCOPE (and later KRONOS and NOS) operating systems on the CDC 6000
|> and 7000 series used a circular buffer for I/O. The control structure
|> was like:
|>
|> struct CBUFFER {
|> int *first, *in, *out, *limit;
|> };
[ excellent description deleted ]
|> .............. Actually, the PPs were only 1 processor, which
|> time-multiplexed itself each microsecond among 10 or 20 different
|> contexts, resulting in what looked like 10 or 20 individual PPs (each
|> with 1 microsecond instruction cycle times).
(not quite relevant, and not quite correct either. With 20 PPs, there were
*two* PP chassis each acting as 10 logical PPs in a slot-and-barrel
arrangement. Only the 6000 series ; don't know about 7000 series ; Cyber 70's
were the same but optionally had 7 PPs per chassis ; Cyber 170s from Model D
onwards had real hardware individual PPs).
|> The SCOPE/KRONOS/NOS operating system ....
Well, there's SCOPE, later known as NOS/BE ; and KRONOS, later known as
NOS. That's two operating systems.
The fact that both Scope and Kronos had circular buffers means that the
feature must be *very* old. After 1970, they weren't talking to each other.
In fact, lots of the Scope and Kronos development consisted of the two sides
(re)inventing the same wheels, though in a different order.
|> ..... may have allowed several
|> simultaneous and independent transfers. I do know that tape-tape copies
|> could keep the tapes spinning continuously.
At least in SCOPE, the CPU-resident program could set up TWO of these structs
(called File Environment Tables, or FETs), one for reading, one for writing,
using the same buffer, then fire up one PP for reading and one for writing.
The read PP would move the IN pointer, and the write PP would move the OUT
pointer, and the CPU program could sit back and watch. This mechanism was known
as pointer chasing. In this manner a tape-to-tape copy would proceed at full
tape speed. If there was a hitch (say, error recovery on read) the write PP
would find the buffer empty and give up. The CPU program would regain control,
wait for data to be available, and fire up the write PP again.
|> --------------------------------------------------------------
|> Howard Bussey <how...@thumper.bellcore.com>
Dave's original request was for any code before Oct 81. Well, I can find code
which I *think* I wrote around 1976. But the basic principle was in CDC
operating systems *at least* in the very early 1970's. Before my time, anyway.
I first heard of this method in late 1973. (I wonder, do I still have the
SCOPE 3.4 Handbook, dated 1972 or 1973, which describes this?)
Is Greg Mansfield out there ? or Dave Cahlander ? Or Seymour Cray, for that
matter : I don't think he invented it, but I'm sure he knows who did.
Daan Sandee san...@think.com
Thinking Machines Corporation
Cambridge, Mass 02142
Gregg Townsend
When I bought an H19 terminal kit, I also ordered the ROM source code
(in printed form). I was quite surprised to find that the code,
attributed to R. N. Borchardt, very closely follows the KRONOS coding
standards. Each routine had a proper comments block giving name,
description, entry, exit, uses. There are some minor deviations from
the standard, but they are applied consistently.
The assembler even looks a lot like COMPASS. '*' in column one for
comments; no '*' needed for comments off to the right. It appears to
have TITLE, SUBTTL, and SPACE pseudo-ops; as per COMPASS, they don't
list, but the sequence numbers show a gap. Also (unusual for a Z80?)
the generated code is listed in octal, not hex. Everything is in upper
case, including comments, except for a few literals.
I have long appreciated the clarity and discipline provided by the KRONOS
(later NOS, later CYBER) coding standard. I still remember when, as a
SCOPE programmer, I saw my first example of a well-organized PP program.
It was DUD (Dynamic User Display), the console driver for CHESS 3.5
from Northwestern University; and it followed the KRONOS coding standard.
Gregg Townsend / Computer Science Dept / Univ of Arizona / Tucson, AZ 85721
+1 602 621 4325 g...@cs.arizona.edu 110 57 16 W / 32 13 45 N / +758m
(Former SCOPE, NOS/BE, NOS system programmer at ARIZ and SVL).
tane...@economics.adelaide.edu.au
> This in response to Dave Goldblatt's request on the history of circular buffers,
> and as comment on Howard Bussey's response.
> Note I have set the followup to comp.sys.cdc, so we old CDC hands can go and
> wallow in nostalgia without annoying the rest of the universe further.
>
> Well, there's SCOPE, later known as NOS/BE ; and KRONOS, later known as
> NOS. That's two operating systems.
And don't forget MACE, which is where Kronos came from. And SMM!
> The fact that both Scope and Kronos had circular buffers means that the
> feature must be *very* old. After 1970, they weren't talking to each other.
> In fact, lots of the Scope and Kronos development consisted of the two sides
> (re)inventing the same wheels, though in a different order.
Absolute rubbish! Kronos always lagged behind Scope, and usually copied it :-)
> Dave's original request was for any code before Oct 81. Well, I can find code
> which I *think* I wrote around 1976. But the basic principle was in CDC
> operating systems *at least* in the very early 1970's. Before my time, anyway.
Well, I started tinkering with the internals of CDC systems in 1969, and the
circular buffer stuff was old hat by then.
Come to think of it, I am sure that circular buffers were used on the CDC3x00
gear. But I never had much to do with them (apart from gazing at the console
at the flashing lights and numbers in awe -- those things really LOOKED like
computers, didn't they? :-)
> Is Greg Mansfield out there ? or Dave Cahlander ? Or Seymour Cray, for that
> matter : I don't think he invented it, but I'm sure he knows who did.
Don't forget STAR, that had it in hardware, I think.
..and I agree with Howard Bussey about the first RISC machine!
Tom Nemeth
Dick Dunn
appropriate in any case.
da...@prowler.clearpoint.com writes:
> I am looking for information which could be used to invalidate
>a patent which covers one of the most basic techniques in software:
...
> The allegedly inventive feature is having one of the
>processors tell the other processor the size of the ring buffers.
Interesting...as opposed to what, having a fixed size? (I assume inter-
processor telepathy is out. Pardon, I'm too cynical about this patent
stuff.)
Folks have pointed out the early CDC "CIO" interface, which seems to be
valid prior art since it involves multiple processors, and since it uses a
"ring buffer" concept--actually the effect is multiple buffers, with each
buffer being one addressable storage unit, because of the way it works.
This is a reduction (actually an improvement) to an optimal granularity.
> I'm looking for code or references to this technique written
>before October 5, 1981. An example of dual processor communication
>would be ideal...
The last bid I saw was in the late '70's, which is more than enough. How-
ever, patents last 17 years, so if we can get it back earlier than '74 we
have it nailed. I can get code I wrote to use the CDC mechanism circa
1969, and documentation of how to use it copyright 1966. I know I can
still be outbid (probably by someone in Boulder!:-), since I can only dig
back to an OS which is a "significant extension" of the original imple-
mentation.
I don't know what the patent really covers, but if it covers this stuff
dammit, folks should be able to sue for treble costs/damages. This pre-
dates me, and I'm an old fart.
--
Dick Dunn r...@raven.eklektix.com -or- raven!rcd
...Do you want software patents, or a software industry? Pick one.
Daan Sandee
|> In article <1991Sep29.1...@Think.COM>, san...@Think.COM (Daan Sandee) writes:
|>> This in response to Dave Goldblatt's request on the history of circular buffers,
|>> The fact that both Scope and Kronos had circular buffers means that the
|>> feature must be *very* old. After 1970, they weren't talking to each other.
|>> In fact, lots of the Scope and Kronos development consisted of the two sides
|>> (re)inventing the same wheels, though in a different order.
|>
|> Absolute rubbish! Kronos always lagged behind Scope, and usually copied it :-)
Well, yes. In fact, absolutely. But I guess I was just too polite to say so
*rightaway*. Now that you've given away the secret, I can only agree.
|> Come to think of it, I am sure that circular buffers were used on the CDC3x00
|> gear. But I never had much to do with them (apart from gazing at the console
|> at the flashing lights and numbers in awe -- those things really LOOKED like
|> computers, didn't they? :-)
|> Tom Nemeth
Not MSOS on the 3L00 ; there, the interface was called CIO as well, but it
was supposed to mean Central I/O, or Common I/O, or something. It didn't have
circular buffers : I was introduced to that first on the 6000.
I can't speak as to MASTER or 3U00 Scope.
I agree on the 3000 being a real computer. It had several thousand points of
light, and a console like a spaceship. It also had *real* parity, which means
that it stopped and put up all its lights. And a loudspeaker. And all of 32K
words of core memory, and *optional* floating point hardware.
Bill Gray
> and as comment on Howard Bussey's response.
> Note I have set the followup to comp.sys.cdc, so we old CDC hands can go and
Sorry, I didn't even know about this group.
> wallow in nostalgia without annoying the rest of the universe further.
> There's still stuff that I don't know either that Dave would want to know,
> i.e. the real first date, so this is a hint to Dave to keep reading this
It was already there when I joined CDC in 1968, but the first cdc machine
I dealt with was an early 6600 at Westinghouse. I believe that was in
1965 or 6. CDC was going to deliver an OS called SIPROS (CIPROS?), but
that project failed and they delivered a "productized" version of their
diagonostic system called SCOPE (Supervisory Control of Program Execution).
(This was all a long time ago; I'm old and memory is dim.)
The Circular Input/Output (CIO) program was there, I believe, at this
point. Somewhere, I have a SCOPE Internal Reference Specification from
around that era that could provide actual documentation.
>
> At least in SCOPE, the CPU-resident program could set up TWO of these structs
> (called File Environment Tables, or FETs), one for reading, one for writing,
Acutally, you could point as many FETs as you please at the same buffer, and
also at your peril. However, typically, reading and writing were done with
the same FET at the same control point. Two different control points would
use different FETs to (possibly) read the same file. A control point was
sort of like a process thread.
> using the same buffer, then fire up one PP for reading and one for writing.
> The read PP would move the IN pointer, and the write PP would move the OUT
This could be done, but typically, the CP program moved one pointer
while the PP program moved the other; This was the mechanism by which
the two independant processes (PP and CP) cooperated.
For a tape read, for instance, the CPU program could issue an I/O read
request; in response, the PPU (which talked to the tape controller) would
start a tape read and move the "IN" pointer in the CPU buffer. If the CP
program could chase the IN pointer with the "OUT" pointer fast enough
(that is, suck the data into the CP program and presumably use it), that
one initial read request would be sufficient to move the entire tape
(barring glitches like error recovery or somebody else getting the CPU).
> which I *think* I wrote around 1976. But the basic principle was in CDC
I know for a fact that I wrote literally hundreds of lines of circular I/O
code well before 1976; and I'd be willing to testify to that fact and prove
it.
> Is Greg Mansfield out there ? or Dave Cahlander ? Or Seymour Cray, for that
> matter : I don't think he invented it, but I'm sure he knows who did.
Don't forget Garner McCrossen. The last time I looked at 1AJ, BTW, there
were still COMMENTS entered by Seymour himself!!
Bill Gray UUCP: ...!uunet!inel.gov!whg
Idaho National Engineering Lab. INTERNET: w...@INEL.GOV
"The three branches of gov't: money, television and bull****" -PJ O'Rourke
========== long legal disclaimer follows, press n to skip ===========
Neither the United States Government or the Idaho National Engineering
Laboratory or any of their employees, makes any warranty, whatsoever,
implied, or assumes any legal liability or responsibility regarding any
information, disclosed, or represents that its use would not infringe
privately owned rights. No specific reference constitutes or implies
endorsement, recommendation, or favoring by the United States
Government or the Idaho National Engineering Laboratory. The views and
opinions expressed herein do not necessarily reflect those of the
United States Government or the Idaho National Engineering Laboratory,
and shall not be used for advertising or product endorsement purposes.
Daan Sandee
|> Is Greg Mansfield out there ? or Dave Cahlander ? Or Seymour Cray, for that
|> matter : I don't think he invented it, but I'm sure he knows who did.
I am happy to tell you that Greg Mansfield IS out there. He cannot post
himself, but he authorizes me to post the following information :
] The circular buffer code was in Seymour Cray's 6600 operating system in
] 1964. I first saw this in October 1964. The source for this system has
] been preserved by the wonders of the INTERNET. If you are interested, I
] can make it available to you.
So there. I was wrong in saying Seymour didn't invent it ; he did.
There you have it, as close to the horse's mouth as you can get.
Steve Gombosi
>This in response to Dave Goldblatt's request on the history of circular buffers,
>
>|> The SCOPE (and later KRONOS and NOS) operating systems on the CDC 6000
>|> and 7000 series used a circular buffer for I/O. The control structure
>|> was like:
>|>
>|> time-multiplexed itself each microsecond among 10 or 20 different
>|> contexts, resulting in what looked like 10 or 20 individual PPs (each
>|> with 1 microsecond instruction cycle times).
>
> (not quite relevant, and not quite correct either. With 20 PPs, there were
>*two* PP chassis each acting as 10 logical PPs in a slot-and-barrel
>arrangement. Only the 6000 series ; don't know about 7000 series ; Cyber 70's
They were ALWAYS independent on the 7000s. The PPUs (or FLPPs if you prefer)
had hardwired buffer areas in low SCM. Very different beasts, even IF they
ran very similar instruction sets.
>
>|> The SCOPE/KRONOS/NOS operating system ....
> Well, there's SCOPE, later known as NOS/BE ; and KRONOS, later known as
> NOS. That's two operating systems.
WELL, it probably ought to be:
SCOPE/NOSBE, MACE/KRONOS|TSOS/NOS - somehow COS ought to fit in there as
the ultimate ancestor, though...
> The fact that both Scope and Kronos had circular buffers means that the
> feature must be *very* old.
My first exposure was in Kronos common decks written in 1969. The feature
itself is
older. In addition, circular buffering was discussed in some detail in
data structures classes I took in the early/mid 70's.
> After 1970, they weren't talking to each other.
Sure they were...most of it wasn't printable, though ;-)
>At least in SCOPE, the CPU-resident program could set up TWO of these structs
>(called File Environment Tables, or FETs), one for reading, one for writing,
Also on KRONOS/NOS - this is how the COPYB utility worked.
>
>Dave's original request was for any code before Oct 81.
I have some of my old Kronos/NOS manuals - they significantly predate this
patent. I also (somewhere) have some old Cray Operating System manuals which
document the Circular I/O task - this code also predates this patent.
Come to think of it, I used to have a lising of the CPU common decks from
sometime around then...I wonder if it's still in a box somewhere...
I don't have the original post any more, but I'd be delighted to send
photocopies if 1)someone will send me a mailing address and 2) I can find
the time to sort through all my junk and find this stuff.
>Is Greg Mansfield out there ? or Dave Cahlander ?
They both work for CRI now.
>Or Seymour Cray, for that
>matter : I don't think he invented it, but I'm sure he knows who did.
He's HERE (as opposed to CRI), but he is, ummmmm, *BUSY*! ;-)
Steve Gombosi
s...@craycos.com
Steve Gombosi
>Clarence Wilkerson's reference to the H89 triggered this recollection:
>
>When I bought an H19 terminal kit, I also ordered the ROM source code
>(in printed form). I was quite surprised to find that the code,
>attributed to R. N. Borchardt, very closely follows the KRONOS coding
>standards.
Gee, I wish everybody did - CODING and DOCMENT were truly wonderful!
I still try to adhere to that standard!
>
>The assembler even looks a lot like COMPASS.
This is pretty interesting - back at Florida State in the early 70's,
we modified COMPASS to generate code for a MODCOMP we were using as
a multiplexor for TELEX! We (well, actually Larry Hughes, now at Integraph)
later developed a COMPASS-like assembler for the 8080 and Z-80. We ended
up using it to develop a TDM, a 200UT emulator, and a HASP terminal...
>comments; no '*' needed for comments off to the right. It appears to
>have TITLE, SUBTTL, and SPACE pseudo-ops; as per COMPASS, they don't
>list, but the sequence numbers show a gap. Also (unusual for a Z80?)
>the generated code is listed in octal, not hex.
I still have problems accepting 'F' as a number ;-)
>
>I have long appreciated the clarity and discipline provided by the KRONOS
>(later NOS, later CYBER) coding standard.
Me too! Assembly language written with a clarity and perspicuity in excess
of almost any "higher level language" code you see out there today. With
the well-developed set of common decks and macros, the coding standards,
and the uniform entry/exit conditions, systems programming was a hell of a
lot easier than it is on certain hacker-infested OS's we could all name ;-).
>I still remember when, as a
>SCOPE programmer, I saw my first example of a well-organized PP program.
>It was DUD (Dynamic User Display), the console driver for CHESS 3.5
>from Northwestern University; and it followed the KRONOS coding standard.
ALL the PP programs on KRONOS were well-organized (well, almost).
The neat thing about PP-s was the way they ENFORCED modularity! The BAD
THING, was of course, the necessity of self-modifying code :-(.
>
> (Former SCOPE, NOS/BE, NOS system programmer at ARIZ and SVL).
Former KRONOS/NOS systems programmer at FSU and NASA/Langley, former
Cyber stations "expert" at CRI - we all ought to have a reunion somewhere...
Steve
Walter Spector
describes the FET and circular buffers in detail. So the technique
even predates SCOPE on the 6000. Note that computer documentation is
typically a year or two behind the implementation (at least!)
Also, all versions of the (Cray) COS system also use this technique.
CRI calls it a DSP (DataSet Parameter block) instead of a FET, but it
still has the familiar (to *us* anyway) FIRST/IN/OUT/LIMIT pointers.
So CRI has been using the technique since the late '70s.
(I'm still looking for a copy of Thornton's "Design of the CDC 6600".
Anyone know of a lonely spare copy?)
Walt
--
Walt Spector RISC -
(w...@renaissance.cray.com) Really Invented by
Sunnyvale, California Seymour Cray
_._ _._ _.... _. ._.
Steve Jay
>Dave's original request was for any code before Oct 81. Well, I can find code
>which I *think* I wrote around 1976. But the basic principle was in CDC
>operating systems *at least* in the very early 1970's. Before my time, anyway.
>I first heard of this method in late 1973. (I wonder, do I still have the
>SCOPE 3.4 Handbook, dated 1972 or 1973, which describes this?)
>Is Greg Mansfield out there ? or Dave Cahlander ? Or Seymour Cray, for that
>matter : I don't think he invented it, but I'm sure he knows who did.
The "Circular I/O" technique being discussed here was in the original COS
(Chippewa Operating System) for the 6600 in 1964. It is described in
the COS Reference Manual. If someone's life depends on it, I know where
I can get a copy of that manual.
Steve Jay
s...@ultra.com ...ames!ultra!shj
Ultra Network Technologies / 101 Dagget Drive / San Jose, CA 95134 / USA
(408) 922-0100 x130 "Home of the 1 Gigabit/Second network"
Steve Suttles
IMHO, the patent referred to (I missed the original post) was invalid in
1971. My first reaction is that it is "intuitive and obvious" (a legal
phrasing) and therefore unpatentable with machines like the 6502 around.
However, lest the 6502 be brought under fire for patent infringment, if it's
date of manufacture does not precede 1971, here's additional proof:
Donald E. Knuth of Stanford (remember him), published a volume named
FUNDAMENTAL ALGORITHMS (it's volume one for those who do remember).
In the chapter entitled BASIC CONCEPTS, there is a section dealing
with INPUT AND OUTPUT. He devotes several pages to buffering, including
references to "a circle of buffers" with appropriate illustrations.
His work is copyrighted in 1968. My version is the second edition, copyrighted
in 1973. Recall that this was a school text.
In his bibliography, he credits the circles-of-buffers to Dijkstra's
doctoral thesis (1958) "Communication with an Automatic Computer" and
states that a buffer could contain a single character or number (sounds
pretty close so far, huh?) The paper "Input-Output Buffering and
FORTRAN", by David E. Ferguson, J. ACM 7 (1960) is also referenced
with regard to buffer circles.
I maintain that these dates precede 1971 significantly, and release the
concept into the public domain.
Incidentally, it is interesting to note that much of the arguments refer
to the CDC 650 and a few to the Univac. Both are mentioned in the book
and no doubt have much to do with Knuth's knowledge of this approach.
sas
MOO...@ibm.cl.msu.edu
Path: msuinfo!netnews.upenn.edu!widener!iggy.GW.Vitalink.COM!pacbell.com!mips!sw
From: s...@craycos.com (Steve Gombosi)
Newsgroups: comp.sys.cdc
Subject: Re: KRONOS Coding Standard in Heathkit ROM code
Message-ID: <1991Sep30....@craycos.com>
Date: 30 Sep 91 16:59:05 GMT
References: <20...@mentor.cc.purdue.edu> <78...@optima.cs.arizona.edu>
Organization: Cray Computer Corporation
Lines: 51
In article <78...@optima.cs.arizona.edu> g...@cs.arizona.edu (Gregg Townsend) writ
>Clarence Wilkerson's reference to the H89 triggered this recollection:
>
>When I bought an H19 terminal kit, I also ordered the ROM source code
>(in printed form). I was quite surprised to find that the code,
>attributed to R. N. Borchardt, very closely follows the KRONOS coding
>standards.
Gee, I wish everybody did - CODING and DOCMENT were truly wonderful!
I still try to adhere to that standard!
>
>The assembler even looks a lot like COMPASS.
This is pretty interesting - back at Florida State in the early 70's,
we modified COMPASS to generate code for a MODCOMP we were using as
a multiplexor for TELEX! We (well, actually Larry Hughes, now at Integraph)
later developed a COMPASS-like assembler for the 8080 and Z-80. We ended
up using it to develop a TDM, a 200UT emulator, and a HASP terminal...
And MSU wrote a set of macros (plus a few minor COMPASS mods) for the interdata
7/32.
>comments; no '*' needed for comments off to the right. It appears to
>have TITLE, SUBTTL, and SPACE pseudo-ops; as per COMPASS, they don't
>list, but the sequence numbers show a gap. Also (unusual for a Z80?)
>the generated code is listed in octal, not hex.
Actually, TITLE, SUBTTL, SPACE, and "*" for comments was in the assembler for
the 7090 and the COMPASS for CDC 3600. It may also have been in the 704
assembler.
I still have problems accepting 'F' as a number ;-)
>
>I have long appreciated the clarity and discipline provided by the KRONOS
>(later NOS, later CYBER) coding standard.
Me too! Assembly language written with a clarity and perspicuity in excess
of almost any "higher level language" code you see out there today. With
the well-developed set of common decks and macros, the coding standards,
and the uniform entry/exit conditions, systems programming was a hell of a
lot easier than it is on certain hacker-infested OS's we could all name ;-).
>I still remember when, as a
>SCOPE programmer, I saw my first example of a well-organized PP program.
>It was DUD (Dynamic User Display), the console driver for CHESS 3.5
>from Northwestern University; and it followed the KRONOS coding standard.
ALL the PP programs on KRONOS were well-organized (well, almost).
The neat thing about PP-s was the way they ENFORCED modularity! The BAD
THING, was of course, the necessity of self-modifying code :-(.
We always used SCOPE 3.3 PP routines as "before" examples in teaching coding
standards & the necessity for them.
John F Haugh II
>I trimmed down the distribution a whole bunch...but followup to somewhere
>appropriate in any case.
>da...@prowler.clearpoint.com writes:
>> I am looking for information which could be used to invalidate
>>a patent which covers one of the most basic techniques in software:
>>the ring buffer...[specifics deleted]
I don't have a colletion of old CACM's, but try this one out for
size -
Hoare, C. A. R., "Monitors: An Operating System Structuring
Concept", CACM Vol 17, No. 10. October 1974, pp 549-557.
I don't know what it says, but it is cited as the source of inspiration
in my college O/S text for a ring buffer example.
An older citation in the same text is
Courtois, P. J.; F. Heymans; and D. L. Parnas, "Concurrent
Control with Readers and Writers", CACM, Vol 14, No. 10.
October 1971, pp 667-668.
>Folks have pointed out the early CDC "CIO" interface, which seems to be
>valid prior art since it involves multiple processors, and since it uses a
>"ring buffer" concept--actually the effect is multiple buffers, with each
>buffer being one addressable storage unit, because of the way it works.
>This is a reduction (actually an improvement) to an optimal granularity.
Well, the example (which unfortunately is in a book written in 1984 ...)
does have a parameter for buffer size.
>> I'm looking for code or references to this technique written
>>before October 5, 1981. An example of dual processor communication
>>would be ideal...
I think the CDC examples people keep alluding to are going to be the
best ones.
--
John F. Haugh II | I am the NRA. | UUCP: ...!cs.utexas.edu!rpp386!jfh
Ma Bell: (512) 255-8251 | Shoot a friend today!| Domain: j...@rpp386.cactus.org
"I brought my wife 'cuz she's too ugly to kiss good-bye."
-- O. A. "Bum" Phillips
Ed de Moel
...
>
>(I'm still looking for a copy of Thornton's "Design of the CDC 6600".
>Anyone know of a lonely spare copy?)
>
Pages 166vv describe the Circular Buffer I/O.
In the preface of this book, Seymour Cray talks about development
in the early 60s (but there his emphasis is more on the hardware
than the software).
Ed de Moel.
SAIC/San Diego.
lance.norskog
It's not called "Ring Buffers", it's called:
Dekker's Algorithm
Dekker, a Dutch mathematician/computer scientist, published it in 1967.
Lance Norskog
A computer science education does help, you know. Crack those books!
Michael Thompson
>
>Dave's original request was for any code before Oct 81. Well, I can find code
>which I *think* I wrote around 1976. But the basic principle was in CDC
>operating systems *at least* in the very early 1970's. Before my time, anyway.
>I first heard of this method in late 1973. (I wonder, do I still have the
>SCOPE 3.4 Handbook, dated 1972 or 1973, which describes this?)
>Is Greg Mansfield out there ? or Dave Cahlander ? Or Seymour Cray, for that
>matter : I don't think he invented it, but I'm sure he knows who did.
Umm.. Not only was it used in operating systems, of course, but some people
who went to the University of Minnisota, or any of the California State
Universities between 1975/76 to 1983 might remember a program called $TALK.
This was a quite sofisticated "chat" program (I haven't seen any "chat" program
so well designed since), which used a circular-file for communication
between users. As an exercise, I wrote the same program from scratch in
pascal using this method in 1980.
The $DAYFILE (some sort of history file) was also a circular file.
-Michael Thompson
mic...@sinix.uucp
Steve Gombosi
>In article <1991Sep29.1...@Think.COM> san...@Think.COM (Daan Sandee) writes:
>>
>>Dave's original request was for any code before Oct 81. Well, I can find code
>>which I *think* I wrote around 1976. But the basic principle was in CDC
>>operating systems *at least* in the very early 1970's. Before my time, anyway.
>>I first heard of this method in late 1973. (I wonder, do I still have the
>>SCOPE 3.4 Handbook, dated 1972 or 1973, which describes this?)
>>Is Greg Mansfield out there ? or Dave Cahlander ? Or Seymour Cray, for that
>>matter : I don't think he invented it, but I'm sure he knows who did.
>
Over the weekend, I found my copy of the _Chippewa_Operating_System_Preliminary
_Reference_Manual_ for the 6600, dated 1965. It contains a detailed
specification of the original CIO interface. I'm going to send Dave a photo-
copy.
Steve