To Anne & Lynn Wheeler, if still observing...

[Chris M. Thomasson]

Can you tell me the full name of the guy who invented CAS? Its Charlie
from IBM, but I cannot find the other two initials. Some context:

https://groups.google.com/forum/?hl=en#!original/comp.arch/JkcTGC9X3lo/M4Vo_cXKEwAJ

Thanks.

[Bonita Montero]

> Can you tell me the full name of the guy who invented CAS? Its Charlie
> from IBM, but I cannot find the other two initials. Some context:
> https://groups.google.com/forum/?hl=en#!original/comp.arch/JkcTGC9X3lo/M4Vo_cXKEwAJ

It's rather unlikely that there was any Charlie that invented
CAS at IBM: https://bit.ly/2kjzbuM - Google directs almost any
relevant hits to this newsgroup; so it's likely to be a myth.

[Chris M. Thomasson]

I believe the Wheeler's. Their history here is very nice. Loaded with
information.

[Bonita Montero]

> It's rather unlikely that there was any Charlie that invented
> CAS at IBM: https://bit.ly/2kjzbuM - Google directs almost any
> relevant hits to this newsgroup; so it's likely to be a myth.

And: the name CAS simply was chosen because it fits to what
the operation does. And that the initials of the name of the
inventor also fit to this is 26 ^ 3 = 17.576 - like a moderate
lottery-prize.

[Chris M. Thomasson]

Still believe Lynn Wheeler. Why would he lie?

[Bonita Montero]

>> And: the name CAS simply was chosen because it fits to what
>> the operation does. And that the initials of the name of the
>> inventor also fit to this is 26 ^ 3 = 17.576 - like a moderate
>> lottery-prize.

> Still believe Lynn Wheeler. Why would he lie?

No, not knowingly.

[Chris M. Thomasson]

Well, perhaps, God willing, if he or his wife are still around, we can
get more context.

[Bonita Montero]

>> No, not knowingly.

> Well, perhaps, God willing, if he or his wife
> are still around, we can get more context.

I'm confident that if this would be known you would
find this in the most prominent place at the Wikipedia.

[Chris M. Thomasson]

Perhaps not.

[Terje Mathisen]

Ah Bonita!

I'd wish to be so young and certain you know (almost everything) again.

Lucky You!

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[Robert Wessel]

You might try the email address listed at:

https://www.garlic.com/~lynn/

[Bonita Montero]

>> I'm confident that if this would be known you would
>> find this in the most prominent place at the Wikipedia.

> Ah Bonita!
> I'd wish to be so young and certain you know (almost everything) again.

I'm not always confident, but such a basic issue like that
the initials of the inventor of CAS would match C.A.S. would
be documented in the first place.

[Alex McDonald]

Mr. Charles A Salisbury
Associate Director, IBM

IBM is particularly interested in Athena's combination of centralized
and distributed processing through file servers, says Charles A.
Salisbury, director of IBM's staff on the MIT campus,
https://tech-insider.org/unix/research/1987/0901.html

from
https://groups.google.com/forum/#!original/bit.listserv.ibm-main/KKfgnwZ_YHM/VROO4TXBAwAJ

This might be him;
http://valleypatriot.com/great-adventurer-charlie-salisbury-seeking-next-adventure/
as might this: https://www.linkedin.com/in/charlie-salisbury-4323398/.
Perhaps he'll respond to a mail, but like much of LinkedIn his entry
looks a little sparse.


--
Alex

[Bonita Montero]

I still have hard doubts: https://bit.ly/2lVyMPO

[Alex McDonald]

On 02-Sep-19 16:18, Bonita Montero wrote:
> I still have hard doubts: https://bit.ly/2lVyMPO

It wasn't my intention to remove them.

What in that paper are you referring to?

--
Alex

[Bonita Montero]

>> I still have hard doubts: https://bit.ly/2lVyMPO

> It wasn't my intention to remove them.
> What in that paper are you referring to?

The paper isn't relevant.
But the search-experession should give some definitive results.
There is simply nothing in the Web that confirms the "inventor"
of compare and swap.

[Alex McDonald]

His bio and an IBM SYSJ paper.

Charles A. Salisbury
Datu [sic] Processing Division, Cambridge, Massachusetts
Mr. Salisbury is a staff member in the operating systems technology
group at IBM's Cambridge Scientific Center. He joined IBM in 1964 at the
Kingston development laboratory, working in diagnostic engineering for
graphic devices. Subsequently he worked in time sharing, real-time
applications, and multiprocessing software as a systems engineer in Palo
Alto, California. Since his transfer to Cambridge in 1969, he has been
involved in the design and implementation of virtual machine systems on
the System/360 Model 67 and System/370. Mr. Salisbury received his B.S.
in electrical engineering from MIT in 1964.

https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5387991

@Article{Holley:1979:VAM,
author = "L. H. Holley and R. P. Parmelee and C. A. Salisbury
and D. N. Saul",
title = "{VM\slash 370} Asymmetric Multiprocessing",
journal = j-IBM-SYS-J,
volume = "18",
number = "1",
pages = "47--70",
year = "1979",
CODEN = "IBMSA7",
ISSN = "0018-8670",
bibdate = "Wed Jan 08 16:35:07 1997",
bibsource = "Compendex database;
http://www.math.utah.edu/pub/tex/bib/ibmsysj.bib",
abstract = "The design and implementation of VM\slash 370 attached
processor support is discussed from the point of view
of adding radical new function to an existing operating
system. Three major design decisions are described, and
performance is analyzed as it relates to those
decisions.",
acknowledgement = ack-nhfb,
classification = "722; 723",
journalabr = "IBM Syst J",
keywords = "computer systems, digital",
}

I don't have an IEEE membership and my weakened google-fu can't find a
PDF (it's my dinner time); the article is here
https://ieeexplore.ieee.org/abstract/document/5387986

--
Alex

[Bonita Montero]

> https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5387991
> http://www.math.utah.edu/pub/tex/bib/ibmsysj.bib",

At least those two sources aren't really confirming or even
lead into that direction.

[Alex McDonald]

Thanks Robin.

--
Alex

[EricP]

Google patents:

Shared data controlled by a plurality of users, 1973
Inventor: Paul J Brown, Ronald M Smith
Current Assignee: International Business Machines Corp
https://patents.google.com/patent/US3886525A/en

which says part way in
"The new instruction, called Compare and Swap"

[Bonita Montero]

> Google patents:
> Shared data controlled by a plurality of users, 1973
> Inventor: Paul J Brown,  Ronald M Smith
> Current Assignee: International Business Machines Corp
> https://patents.google.com/patent/US3886525A/en
> which says part way in
> "The new instruction, called Compare and Swap"

And where can I find the name "Sailsbury"?

[EricP]

I didn't say it had it - that could be a red herring.
This would seem to put to rest the
idea that CAS is the inventors initials
unless there is a second CAS invention.

[Bonita Montero]

The above paper mentions "Paul J Brown" and "Ronald M Smith"
as the inventors.

[Alex McDonald]

Good hit!

The second post by the Wheelers doesn't claim he invented it, but rather
"aka Charlie's initials are CAS ... part of the effort was to choose
mnemonic (compare-and-swap) that were Charlie's initials
http://www.garlic.com/~lynn/subtopic.html#smp"

But the first is quite clear: "charlie had invented compare-and-swap
when he was doing fine-grain multiprocessing locking for cp67 at the
science center ..."

And the post isn't super clear about which Charlie either, but a process
of following the breadcrumbs gets you to the Charles A Salisbury.

https://groups.google.com/forum/#!original/bit.listserv.ibm-main/KKfgnwZ_YHM/FzjfJXSvAwAJ

I'm voting for misremembered conflation unless someone pings CAS for
details and gets a story to the contrary.

--
Alex

[Alex McDonald]

By doing a search with it spelled correctly.

--
Alex

[Bonita Montero]

This is the paper Alex McDonald couldn't find:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.4506&rep=rep1&type=pdf
This paper was written by Charles A. Salisbury and someone else
and it is about CAS, but it is dated five years later than the
patent-filing.

[Alex McDonald]

On 02-Sep-19 18:50, Bonita Montero wrote:

>
> This is the paper Alex McDonald couldn't find:
> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.4506&rep=rep1&type=pdf

Thanks. All this VM/370 big iron stuff brings back happy memories.

>
> This paper was written by Charles A. Salisbury and someone else
> and it is about CAS, but it is dated five years later than the
> patent-filing.

The date doesn't indicate precedence. The vol IBM SYSJ vol 18 1979
journal was a review of VM/370 and obviously drew on much earlier work.

Volume 18, Number 1, 1979
Love H. Seawright, Richard A. MacKinnon:
VM/370 - A Study of Multiplicity and Usefulness. 4-17
Richard A. MacKinnon:
The Changing Virtual Machine Environment: Interfaces to Real Hardware,
Virtual Hardware, and Other Virtual Machines. 18-46
L. Howard Holley, Richard P. Parmelee, Charles A. Salisbury, David N.
Saul:
VM/370 Asymmetric Multiprocessing. 47-70
Richard M. Jensen:
A Formal Approach for Communication Between Logically Isolated Virtual
Machines. 71-92
C. Richard Attanasio:
Virtual Control Storage - Security Measures in VM/370. 93-110
Edson C. Hendricks, Timothy C. Hartmann:
Evolution of a Virtual Machine Subsystem. 111-142
Walter J. Doherty, Richard P. Kelisky:
Managing VM/CMS Systems for User Effectiveness. 143-163
William H. Tetzlaff:
State Sampling of Interactive VM/370 Users. 164-180

The paper focusses on asymmetric processing; but locking is discussed in
the context of a discussion of general principles. I don't think it
advances or retards the argument around the naming of CAS at all.

--
Alex

[Bonita Montero]

> The paper focusses on asymmetric processing; but locking is discussed in
> the context of a discussion of general principles. I don't think it
> advances or retards the argument around the naming of CAS at all.

Maybe, but we're at a final point because the patent names two different
people as the inventors.

[EricP]

Alex McDonald wrote:

> On 02-Sep-19 18:16, EricP wrote:
>>
>> Google patents:
>>
>> Shared data controlled by a plurality of users, 1973
>> Inventor: Paul J Brown, Ronald M Smith
>> Current Assignee: International Business Machines Corp
>> https://patents.google.com/patent/US3886525A/en
>>
>> which says part way in
>> "The new instruction, called Compare and Swap"
>>
>
> Good hit!
>
> The second post by the Wheelers doesn't claim he invented it, but rather
> "aka Charlie's initials are CAS ... part of the effort was to choose
> mnemonic (compare-and-swap) that were Charlie's initials
> http://www.garlic.com/~lynn/subtopic.html#smp"
>
> But the first is quite clear: "charlie had invented compare-and-swap
> when he was doing fine-grain multiprocessing locking for cp67 at the
> science center ..."
>
> And the post isn't super clear about which Charlie either, but a process
> of following the breadcrumbs gets you to the Charles A Salisbury.
>
> https://groups.google.com/forum/#!original/bit.listserv.ibm-main/KKfgnwZ_YHM/FzjfJXSvAwAJ
>
>
> I'm voting for misremembered conflation unless someone pings CAS for
> details and gets a story to the contrary.
>

Maybe its how Brown and Smith pitched it to the boss...

B&S: "Oh, and and it's your initials too Chuck..."
CAS: "Authorized! Make it so."

[Bakul Shah]

See https://www.garlic.com/~lynn/93.html#0 for some context. It seems Wheeler was intimately involved in the whole process.

[Bonita Montero]

>> No, not knowingly.

> See https://www.garlic.com/~lynn/93.html#0 for some context. It seems Wheeler was intimately involved in the whole process.

This patent ...
https://patents.google.com/patent/US3886525A/en
... doesn't mention C.A. Salisbury as one of the inventors.
So there's nothing more to discuss.

[Alex McDonald]

On 02-Sep-19 19:31, Bonita Montero wrote:

Oh, OK. We'll all leave now. Thanks for deciding for us what the facts
might be, we're indebted to you.

--
Alex

[Bonita Montero]

>> This patent ...
>> https://patents.google.com/patent/US3886525A/en
>> ... doesn't mention C.A. Salisbury as one of the inventors.
>> So there's nothing more to discuss.

> Oh, OK. We'll all leave now. Thanks for deciding for us what
> the facts might be, we're indebted to you.

I didn't make any decisions about that.
The above paper simply says who invented CAS.
It's not C.A. Salisbury.

[Alex McDonald]

It says nothing about who invented CAS; it tells us who patented it. You
might find this useful;
https://en.wikipedia.org/wiki/First_to_file_and_first_to_invent.

--
Alex

[Bonita Montero]

>> I didn't make any decisions about that.
>> The above paper simply says who invented CAS.
>> It's not C.A. Salisbury.

> It says nothing about who invented CAS; it tells us who patented it.

"_Inventor_ Paul J Brown Ronald M Smith"

[David Brown]

That tells us who is credited as the "inventor" on the patent, not who
invented it. In a perfect world, it would be the same thing - the
patent world is very far from perfect.

[paul wallich]

As Alex McDonald is trying to tell you politely, the correlation between
who an observer would call an "inventor" and who gets listed on the
inventor line on a patent is nowhere near 1:1. Even before you get to
cases of near-simultaneous invention. (I don't know this particular
instance, but I do know that it's from the days before most software was
patentable, so among other things it's plausible that influenced the
list on the patent application.)

paul

[Ivan Godard]

Having done quite a few patents I can say that it can be quite difficult
to decide who should be on the inventor line of an application. In
reality, few ideas spring like Athena from a single head; there is
always some collaboration involved. Yet the degree of collaboration can
be fuzzy: do you include the intern? How about the management-type who
kept on track the technical meetings that refined the idea? And so on.

There are legal and personal issues too. Candidates have to sign off on
the application; they may have departed, or even be deceased. Those with
new jobs may have signed NDA/assignment agreements when hired that gives
everything they ever thought of to the new employer. And so on.

At Mill the policy is to ask everyone who ever had contact with the
filed material whether they wanted to be on the application, and let
them decide. I expected people to shade toward adding their name,
because a few patents can burnish a resume, but that hasn't happened.
Instead people seem to downplay their own contribution, and we've
occasionally had to kick bashful engineering butts to get them on the
list where deserved.

I *hate* doing patents.

[Anne & Lynn Wheeler]

Bonita Montero <Bonita....@gmail.com> writes:
> "_Inventor_ Paul J Brown Ronald M Smith"

re:
https://www.garlic.com/~lynn/93.html#0

Padegs and Ron Smith were two people in the 370 architecture group
that we dealt with ("owned" the 370 architecture "red book" ... done in CMS
script, conditional script parameter would format/print either
the full "red book" or the "principles of operation" subset.)
https://people.cs.clemson.edu/~mark/architects.html

US Patent 3,787,891 "Signal Processor Instruction for
Non-Blocking Communication Between Data Processing Units" ,
issued January 22, 1974. Inventors: Brian B. Moore, Andris Padegs, and
Ronald M. Smith.
https://patents.google.com/patent/US3787891

--
virtualization experience starting Jan1968, online at home since Mar1970

[Alex McDonald]

Parker v. Flook, 1978. Even prior to that, it was close to impossible to
get software patents; Gottschalk v. Benson, 1972, and amusingly given
the discussion recently here, on the subject of binary conversion to BCD.

--
Alex

[chris.m.t...@gmail.com]

I think so.

[chris.m.t...@gmail.com]

This is very interesting. Lore and Legend... ;^)

[chris.m.t...@gmail.com]

Excellent point Alex. Thank you.

[chris.m.t...@gmail.com]

Well, maybe not so fast... ;^)

[Bonita Montero]

> That tells us who is credited as the "inventor" on the patent, not who
> invented it.

Wrong.

[Bonita Montero]

>> That tells us who is credited as the "inventor"
>> on the patent, not who invented it.

> Wrong.

https://ocr.yale.edu/faculty/frequently-asked-questions/what-definition-inventor-patent-and-who-determines

[Alex McDonald]

On 03-Sep-19 05:51, Bonita Montero wrote:
>>> That tells us who is credited as the "inventor"
>>> on the patent, not who  invented it.
>
>> Wrong.

Sigh.

>
> https://ocr.yale.edu/faculty/frequently-asked-questions/what-definition-inventor-patent-and-who-determines
>

It tells us nothing about the contribution of the people that weren't
noted as inventors. People here who do patents have told you this already.


--
Alex

[Bonita Montero]

>> https://ocr.yale.edu/faculty/frequently-asked-questions/what-definition-inventor-patent-and-who-determines

> It tells us nothing about the contribution of the people that weren't
> noted as inventors. People here who do patents have told you this already.

"An inventor is someone who has made an _intellectual_contribution_
to the claimed invention"

[Terje Mathisen]

In particular, the US Patent system might be the most broken in the
western world.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[Alex McDonald]

When I first started out on IBM mainframes, I worked with a slightly
older guy called Heimir Hauksson, who hailed from Iceland and looked and
sounded every part an Icelander.

On the team was Cunningham Baird, a much older guy, ex Indian Army,
handlebar moustache, white brushed back hair, always immaculately
dressed in a blazer and regimental tie. He told me with a straight face
that Heimir had written the IBM sort program; the evidence was in the
name.

//SORT EXEC PGM=ICEMAN

Iceman! Incontrovertible evidence. Heimir confirmed Cunningham's story;
yes, he'd written ICEMAN and named it after himself. I actually believed
this for a while; I mean, who disagrees with an ex-regimental sergeant
major or a 6 foot plus Viking?

To be fair to my older self, it was such a great story. If he'd worked
for IBM, I suspect the story might have gained some traction in the
retelling.

Perhaps the invention of CAS by Charles follows the same pattern. My
position: I think that it's unlikely that one Charles A Salisbury
contributed to the invention of CAS; perhaps it was a story told that
was taken at face value.

Anyhow, back to this post of yours. It's not good lawyering. The
opposite of what you quote is not true. An intellectual contribution to
the claimed invention doesn't mean you have to be, want to be or are
able to be noted as an inventor. Again, people here who do patents have
told you this already.

So you and I can't be 100% sure. You're probably right, but not
absolutely so. I would not hang a man on this evidence.

--
Alex

[EricP]

IANAL
The reason the patent office manual cites so many court cases
is because it is not always obvious who the inventor is.
A lot of these decisions are subjective and context dependent.

A patent lawyer would, I assume, be expected to know and understand
at least all of the important cases listed in the manual.

[an archived manual version but good enough for our purpose]
Manual of Patent Examining Procedure
2138.04 "Conception" [R-5]
https://mpep.uspto.gov/RDMS/MPEP/e8r9#/e8r9/d0e207607.html

Inventor (patent)
https://en.wikipedia.org/wiki/Inventor_(patent)

Who gets royalties being one reason people argue about such things.
Just because I mention my anti-gravity device on comp.arch doesn't
entitle you to a piece of the pie.
Or does it? Oh... rats!

[Terje Mathisen]

That definition is perfectly fine.

It says absolutely nothing about any connection between the listed
inventors and who are/were the actual inventors by the same definition.

[Bonita Montero]

>> "An inventor is someone who has made an _intellectual_contribution_
>> to the claimed invention"

> That definition is perfectly fine.
> It says absolutely nothing about any connection between the listed
> inventors and who are/were the actual inventors by the same definition.

If C.A. Salisbury would be the inventor he would have been named
in the patent. And further it is unrealistic that much poople are
involved in such a simple invention.

[Alex McDonald]

To your first point; no, as you've been told several times now.

To your second. This patent has 16 inventors.
https://patents.google.com/patent/US5509140. It was challenged in court
on the basis that it had too many inventors. "Nu-Kote asserts that the
presence of sixteen named inventors casts sufficient doubt on the
validity of the patent, such that the burden of going forward shifted to
Canon." https://caselaw.findlaw.com/us-federal-circuit/1128983.html

They lost. Were you their lawyer by any chance?

As to your third assertion -- "such a simple invention" -- you're making
yourself look remarkably arrogant and stupid.

--
Alex

[Bakul Shah]

We don’t know what the case is with CAS so we can only speculate but
I wouldn’t be so sure that everyone involved in its invention is credited.

I know that on one of my patents more people should’ve been added.
No idea why they weren’t. I found out the patent existed years after
the company had ceased to exist! The idea had evolved collaboratively.
Often the key is the idea and its implementation is pretty straightforward.

I’d give more credence to Lynn Wheeler’s account, patent notwithstanding.

Also note that often an idea is obvious and simple only in hindsight.

[Bonita Montero]

> As to your third assertion -- "such a simple invention" -- you're
> making yourself look remarkably arrogant and stupid.

1. When you know something better than others you might easly
seem arrogant to others.
2. CAS and its use for mutexes, condvars or monitors is simple.
More complex are only its application for lock-free programming.
But this wasn't invented at this 1971.

[Bonita Montero]

> We don’t know what the case is with CAS so we can only speculate but
> I wouldn’t be so sure that everyone involved in its invention is credited.

Maybe not everyone, but for sure those that had the basic idea.
CAS and its basic applications are very simple and this is a
trivial-patent, something that should never been patented.

[EricP]

Salisbury might have had the original idea and passed
it to Brown & Smith in his dept. to do all the work.
That would not qualify him as one of the inventors.

from Manual of Patent Examining Procedure

2138.04 "Conception" [R-5]
https://mpep.uspto.gov/RDMS/MPEP/e8r9#/e8r9/d0e207607.html

"An inventor may consider and adopt ideas, suggestions and materials
derived from many sources: a suggestion from an employee,
a hired consultant or a friend even if the adopted material proves
to be the key that unlocks the problem so long as the inventor
"maintains intellectual domination of the work of making the
invention down to the successful testing, selecting or rejecting…."
Morse v. Porter, 155 USPQ 280, 283 (Bd. Pat. Inter. 1965);"

As a nod to him, the accredited inventors name it after him
because they know the original idea came from him.

Why is this so mysterious to you?

[Ivan Godard]

Simplicity is not a bar to patent, obviousness is, and these are not the
same. In fact, some of the very best ideas are really simple - once you
see them - relativity for an example. But the fact that no one had
previously used the idea suggests that it wasn't obvious.

[Bonita Montero]

> Salisbury might have had the original idea and passed
> it to Brown & Smith in his dept. to do all the work.
> That would not qualify him as one of the inventors.

Proof?

> from Manual of Patent Examining Procedure
> 2138.04 "Conception" [R-5]
> https://mpep.uspto.gov/RDMS/MPEP/e8r9#/e8r9/d0e207607.html
> "An inventor may consider and adopt ideas, suggestions and materials
> derived from many sources: a suggestion from an employee,
> a hired consultant or a friend even if the adopted material proves
> to be the key that unlocks the problem so long as the inventor
> "maintains intellectual domination of the work of making the
> invention down to the successful testing, selecting or rejecting…."
> Morse v. Porter, 155 USPQ 280, 283 (Bd. Pat. Inter. 1965);"

He might put several ideas together to a new idea.
But how should CAS be derived from other ideas; that's if
we've found the patent for adding numbers and you tell that
it is composed of some other basic ideas.

[Bonita Montero]

>> Maybe not everyone, but for sure those that had the basic idea.
>> CAS and its basic applications are very simple and this is a
>> trivial-patent, something that should never been patented.

> Simplicity is not a bar to patent, obviousness is, and these
> are not the same.

They usually go hand in hand.

[Alex McDonald]

On 03-Sep-19 17:33, Bonita Montero wrote:
>> As to your third assertion -- "such a simple invention" -- you're
>> making  yourself look remarkably arrogant and stupid.
>
> 1. When you know something better than others you might easly
>    seem arrogant to others.

Arrogance is about communication, not knowledge.


--
Alex

[Bonita Montero]

>>> As to your third assertion -- "such a simple invention" -- you're
>>> making  yourself look remarkably arrogant and stupid.

>> 1. When you know something better than others you might easly
>>     seem arrogant to others.

> Arrogance is about communication, not knowledge.

Read what you told above. You said that I assesed CAS a simple
invention makes me arrogant. This is knowledge; the social com-
parison ([*]) which is part of the communication is the result
of this.

[*] https://en.wikipedia.org/wiki/Social_comparison_theory

[Ivan Godard]

Not in my experience.

I distinguish "complex" from "complicated" in a way that may be subtle
to those not native English speakers. I call something "complex" if it
has wide ranging consequences but is itself derived from a few simple
rules regularly applied; Copernican mechanics for example. I call
something "complicated" if it is an agglomeration of special cases;
Ptolemaic mechanics for example.

The mark of something really brilliant and novel is that it is
blindingly obvious - but only in hindsight - and that it reduces
something complicated to a much smaller something else that is complex.
Things that are obvious a priori tend to be little additions to
something already complicated, retaining the complication.

So if the world's patent offices refused to patent simple things, they
would as a result discard much of what is truly novel.

I grant you that most patents are trivial, even venal. But simplicity is
neither a necessary nor sufficient condition for triviality.

[Chris M. Thomasson]

On 9/2/2019 2:51 PM, Anne & Lynn Wheeler wrote:

> Bonita Montero <Bonita....@gmail.com> writes:
>> "_Inventor_ Paul J Brown Ronald M Smith"
>

> re:
> https://www.garlic.com/~lynn/93.html#0
>
> Padegs and Ron Smith were two people in the 370 architecture group
> that we dealt with ("owned" the 370 architecture "red book" ... done in CMS
> script, conditional script parameter would format/print either
> the full "red book" or the "principles of operation" subset.)
> https://people.cs.clemson.edu/~mark/architects.html
>
> US Patent 3,787,891 "Signal Processor Instruction for
> Non-Blocking Communication Between Data Processing Units" ,
> issued January 22, 1974. Inventors: Brian B. Moore, Andris Padegs, and
> Ronald M. Smith.
> https://patents.google.com/patent/US3787891
>


Thanks for the history. Iirc, Joe Seigh, who worked at IBM:

https://patents.google.com/patent/US5295262

Once told me on this group that IBM had a candy cane striped book that
said the CS and CDS instructions had some sort of livelock prevention
build into it. I cannot find the damn post right now. It was buried in a
long thread. Wondering if you heard anything about that? Thanks Lynn.

[Chris M. Thomasson]

Iirc, Lynn Wheeler mentioned that Charlie had to come up with a concrete
use case. The double width, or CDS, instruction was used for a lock-free
LIFO. Heck, its still in Appendix A under Free-Pool Manipulation:

A-48 in:

https://www-01.ibm.com/support/docview.wss?uid=isg23f570d52b991b62e85256ed2006374c6&aid=1

A-44 describes the CS and CDS instructions. CDS, or DWCAS, operates on
two adjacent words.

With to Charlie and CAS, Lore and Legend, I don't know for sure. But I
appreciate all of the Wheeler's posts. Thanks.

[Chris M. Thomasson]

On 9/3/2019 10:58 AM, Ivan Godard wrote:
> On 9/3/2019 9:53 AM, Bonita Montero wrote:
>>>> Maybe not everyone, but for sure those that had the basic idea.
>>>> CAS and its basic applications are very simple and this is a
>>>> trivial-patent, something that should never been patented.
>>
>>> Simplicity is not a bar to patent, obviousness is, and these
>>> are not the same.
>>
>> They usually go hand in hand.
>
> Not in my experience.

[...]

> The mark of something really brilliant and novel is that it is
> blindingly obvious - but only in hindsight -

Excellent! This works.

[...]

[Rick C. Hodgin]

On 9/3/2019 1:58 PM, Ivan Godard wrote:
> The mark of something really brilliant and novel is that it is blindingly

> obvious - but only in hindsight...


That's certainly true with transistors and lasers at least.

--
Rick C. Hodgin

[Anne & Lynn Wheeler]

"Chris M. Thomasson" <chris.m.t...@gmail.com> writes:
> Iirc, Lynn Wheeler mentioned that Charlie had to come up with a
> concrete use case. The double width, or CDS, instruction was used for
> a lock-free LIFO. Heck, its still in Appendix A under Free-Pool
> Manipulation:
>
> A-48 in:
>
> https://www-01.ibm.com/support/docview.wss?uid=isg23f570d52b991b62e85256ed2006374c6&aid=1
>
> A-44 describes the CS and CDS instructions. CDS, or DWCAS, operates on
> two adjacent words.
>
> With to Charlie and CAS, Lore and Legend, I don't know for sure. But I
> appreciate all of the Wheeler's posts. Thanks.

Ron Smith was one of the people in POK that managed the 370 architecture
(we dealt with Padegs and Smith).

Charlie "invented" compare&swap when he was working on CP/67 fine-grain
kernel locking at the science center (aka virtual machine CP/40 was done
at the science center, including 360/40 hardware modifications for
virtual memory, CP/40 morphs into CP/67 at the science center when
360/67 standard with virtual memory became available). Taking it to
Padeqs & Smith for inclusion in 370 ... they came back that the POK
favorite son operating system people claimed that (360) test&set was
more than sufficient.

At the time, POK OS/360 MVT 65MP used a (test&set) spin-lock (for
entering the kernel supervisor code, no fine-grain locking). We were
told that in order to get compare&swap justified for 370 archicture, had
to come up with more uses (than just kernel locking uses). Thus was
born the uses for (interrupt enabled) multi-threading applications (like
large DBMS) ... which was appicable whether they ran single processor or
multi-processor environments (the examples still included in present day
mainframe principles of operation) ... aka eliminating lots of
application kernel API calls for lock/unlock.

Ron Smith was involved in taking "compare&swap" and turning it into two
instructions CS (compare&swap single word) and CDS (compare doubleword &
swap).


--
virtualization experience starting Jan1968, online at home since Mar1970

[Terje Mathisen]

Wow!

Talk about not getting it. :-(

Pretty much a definition of a really great idea is something that is so
simple, and so elegant, that in hindsight you really wish:

"Why didn't I think of that?

[EricP]

Terje Mathisen wrote:
>
> Pretty much a definition of a really great idea is something that is so
> simple, and so elegant, that in hindsight you really wish:
>
> "Why didn't I think of that?
>
> Terje

Also CAS looks like a Fundamental Patent aka Pioneer Patent,
something that you can't work around, like IBM disk drive,
Xerography or Polaroid instant pictures.
In that case, the simpler the better.
You license it or find a different business (or see Xerox vs IBM :-) )

[Chris M. Thomasson]

That's a good one. Another one is, imvho:

https://en.wikipedia.org/wiki/SCO%E2%80%93Linux_disputes

;^)

[Chris M. Thomasson]

Iirc, Joe Seigh said he had to testify in that mess.

[Anne & Lynn Wheeler]

One of the reasons that the POK crowd didn't come with CAS (and thot
test&set was sufficient) was that they were just doing global kernel
spin-lock ... in part because of their global kernel spin-lock they
advertized a two-processor MP having 1.2-1.3 times the throughput of
single processor (aka, only one processor in the kernel at a time).

mid-70s,, after failure of "Future System" (during which 370 projects
were being killed off because FSS was totally different than 370 and
totally replace 370), there was mad rush to get stuff back into 370
product pipelines. Part of this was 3033 (map of 168-3 logic to 20%
faster chips) and 3081 were kicked off in parallel.

we started a 16-way SMP multiprocessor project and con'ed the 3033
processor engineers to work on it in their spare time ... a lot more
interesting than 168-3 remap. Initially, everbody thot it was great
... until somebody told the head of POK that it could be decades before
the POK favorite son operating system had effective 16-way support. Head
of POK then invited some of us to never visit POK again ... and told the
3033 processor engineers to focus totally on 3033 (and don't get
distracted).

POK doesn't ship 16-way product until Dec2000 (z900) ... nearly
25years later.

[Andy Valencia]

Alex McDonald <al...@rivadpm.com> writes:
> >>> That tells us who is credited as the "inventor"
> >>> on the patent, not who  invented it.
> >> Wrong.

> Sigh.

> It tells us nothing about the contribution of the people that weren't
> noted as inventors. People here who do patents have told you this already.

Of course, you have to be careful here. Inequitable conduct is one
of the ways you attack a patent, and not crediting someone who was,
in fact, an inventor, is a commonly pursued avenue of attack. There
is a real incentive to make sure you name the inventors.

-----------------
Andy Valencia
Home page: https://vsta.org/andy/
Contact: https://vsta.org/contact/andy.html

[Anne & Lynn Wheeler]

don't remember for sure ... possible compare&swap aha moment was the
free storage subpool work. Fine-grain kernel locking work went from
individual kernel routine locking (instead of the POK favorite son MVT
global kernel spin lock), and then shorter instructions sequences within
modules and then data structures ... that may involve multiple different
instruction sequences.

CP/67 kernel storage management was becoming increasingly larger percent
of kernel time ... as pathlengths were cut in other areas and CP/67
loads scaled up. Storage management was single threaded list of
available storage with current size. Allocating storage required running
the threaded list and looking for best fit, and then possibly larger
block that was then split. Releasing storage required running the
threaded list inserting in real storage address order ... possibly
merging adjacent blocks into single larger block. The threaded list was
growing to hundreds of blocks that needed to be run. MIT Lincoln Labs
had gotten "Search List" instruction added to 360/67 ... which optimized
some of the instruction loop time for running list ... but still was
left with all the storage fetches for each block, running the list (with
several hundred items and increasing).

Storage management subpool work involved detailed study of storage sizes
and lifetimes and found nearly all calls to allocate/deallocate storage
involving small number of different small areas sizes (frequently with
very short lifetimes). Things were already rounded up to double word
boundary ... with a little more rounding up of sizes could come up with
very few storage sizes that accounted for nearly all storage
allocation/deallation requests. For the subpool work it defined each
subpool storage size managed with a push/pop single threaded list
... kernel storage management then went from a rapidly growing percent
of all kernel time to almost unmeasurable percent ... basically all
calls done in 14instructions (including call, registers saved, registers
restore and return). There was then relatively infrequent garbage
collection work done cleaning subpools. Compare&swap then could easily
be seen as natural for popping top member off subpool list, or pushing new
member onto subpool list (w/o having to lock sequences of instructions).

[Bonita Montero]

> Also CAS looks like a Fundamental Patent aka Pioneer Patent, ...

> something that you can't work around, like IBM disk drive,
> Xerography or Polaroid instant pictures.
> In that case, the simpler the better.

The patentability should depend on the simplicity as well.

[already...@yahoo.com]

On Wednesday, September 4, 2019 at 1:21:39 AM UTC+3, Anne & Lynn Wheeler wrote:
>
> POK doesn't ship 16-way product until Dec2000 (z900) ... nearly
> 25years later.
>

That still one full year ahead of the first big SMP machine from the POWER side of IBM business (pSeries 690).

[Tim Rentsch]

Terje Mathisen <terje.m...@tmsw.no> writes:

>> [.. rules for patenting ..]
>
> In particular, the US Patent system might be the most broken in the
> western world.

Not that I disagree, but what would you say are the most important
things wrong with it? As compared to those in other countries, I
mean. Disclaimer: I am nearly completely ignorant of patent laws
in any country other than the US, so naming specific countries
would probably help me.

[Bonita Montero]

I think patents should be only a protection of an investment that
would otherwise not be made. F.e. development of new medication
wouldn't have been done if the sales wouldn't finance the develop-
ment. By far most patents are too trivial for that and there should
be no patent granted.

[Terje Mathisen]

Primarily the patent doorstep instead of a patent bar.

Secondarily the imbalance in resources between patent lawyers and patent
examiners.

Finally the way the legal system allows blackmail by patent.

I.e. being sued is so expensive that only your blue print country of the
UK might be worse, it leads to settlements in patent cases with no or
very low merit.

[EricP]

Anne & Lynn Wheeler wrote:
>

> <snip>

>
> Compare&swap then could easily
> be seen as natural for popping top member off subpool list, or pushing new
> member onto subpool list (w/o having to lock sequences of instructions).

Earlier I found various patent references to compare and swap.
The patents themselves are unimportant but they cited documents,
none of which is available online,
whose titles indicate how CAS was being used in 1973-75:

Compare and Swap Implementation of Task Logic
by Kinkade, Jr.,
IBM TDB, vol. 16, No. 2, Jul. 1973, pp. 474-476

Locking architecture in a multiple virtual memory multiprocessing system
by P.H. GUM et al.
IBM TECHNICAL DISCLOSURE BULLETIN,
vol. 16, no. 7, December 1973, pages 2420-2422

First-in/first-out Queuing Technique Using Compare and Swap
by Taradalsky, IBM Tech. Discl. Bull.,
vol. 18, No. 5, Oct. 1975, pp. 1547-1548.

Share Locking without a Lock
by Taradalsky, IBM Tech. Discl. Bull.,
vol. 18, No. 5, Oct. 1975, p. 1546.

Spin queues
by W.W. COLLIER et al.
IBM TECHNICAL DISCLOSURE BULLETIN,
vol. 18, no. 6, November 1975, pages 1953-1954

[Anne & Lynn Wheeler]

already...@yahoo.com writes:
> That still one full year ahead of the first big SMP machine from the
> POWER side of IBM business (pSeries 690).

I've frequently said that John did a lot of simplification stuff in
801/risc in reaction to the horrible complexity he saw in (failed)
Future System and the significant cycle time costs in the 2-way 370
cache machines of the 70s.

801/risc didn't have cache consistancy even between I&D caches ... made
a point of arguing about it at small conference wheree 801/risc was
presented in 1976,

I got roped into doing high available rs/6000 (HA/6000) but quickly
changed the name to HA/CMP when started doing technical cluster scaleup
with national labs and commercial clsuter scaleup with RDBMS vendors.
Problem was that RIOS (still) didn't have any cache consistency and
cluster was the only way of getting any scaleup.

When I was doing HA/CMP, the executive I reported to, then went over to
head up Somerset .. the Apple, IBM, Motorola (he had previously came
from Motorola) effort to do single chip 801 ... and I've semi-facetious
claimed incorporate M88k cache consistency/multiprocessor (he then left
to be president of MIPs ... after bought by SGI).

IBM mainframe had 2-way from 60s and we were on our way to do 16-way
less than decade later when it got shutdown (we presented 16-way at same
confererence that 801/risc was presented) ... another 25yrs to became
16way ... 801/risc didn't even get started on cache consistency for
multiprocessor until somerset.

trivia: old post about Jan1992 meeting in Ellison's conference
room on 128-way cluster
http://www.garlic.com/~lynn/95.html#13

Within a couple weeks (of the Ellison meeting), cluster scaleup was
transferred, announced as an IBM supercomputer (for technical/scientific
*ONLY*) and we were told we couldn't work on anything with more than
four processors. A few months later we leave IBM. We conjectured part of
it was mainframe DB2 (RDBMS) were complaining that if we were allowed to
go ahead (on commercial cluster scaleup), it would be way ahead of them.

At the time, IBM didn't have non-mainframe RDBMS and it wasn't portable
code. The major unix RDBMS vendors had portable code that included
VAX-cluster in same source base. I did a cluster distributed lock
manager that supported VAX-cluster semantics with a lot of input from
the RDBMS vendors about short comings in VAX-cluster scaleup (I had also
done work earlier on the original sql/relational IBM, mainframe,
implementation, System/R).

for all I know (after leaving), (commmercial) IBM mainframe also applied
pressure on 801/risc side of the hosue ... about shipping large power
SMP ... they sure kneecapped us for cluster scaleup.

[Anne & Lynn Wheeler]

subpool work on (360/67) CP67 (and charlie's work on CP/67 fine-grain
multiproceessor locking in the same period) predates 370 and the
availability of compare&swap ... web search turns up a number of books
at google referencing supbool work published in IBM Systems Journal,
v10n4 (1971). I believe IBM has moved all the journals behind IEEE
paywall.

in any case, the subpool implementation would have been an ideal
condidate for compare&swap (push/pop single threaded list).

[Alex McDonald]

On 04-Sep-19 20:24, Anne & Lynn Wheeler wrote:
>
> subpool work on (360/67) CP67 (and charlie's work on CP/67 fine-grain
> multiproceessor locking in the same period) predates 370 and the
> availability of compare&swap ... web search turns up a number of books
> at google referencing supbool work published in IBM Systems Journal,
> v10n4 (1971). I believe IBM has moved all the journals behind IEEE
> paywall.

Yes, they have. There are few articles still available without payment
on the intertubes; but very few. At $33 a pop, they are eye-wateringly
expensive.

>
> in any case, the subpool implementation would have been an ideal
> condidate for compare&swap (push/pop single threaded list).
>


--

Alex

[Tim Rentsch]

Terje Mathisen <terje.m...@tmsw.no> writes:

> Tim Rentsch wrote:
>
>> Terje Mathisen <terje.m...@tmsw.no> writes:
>>
>>>> [.. rules for patenting ..]
>>>
>>> In particular, the US Patent system might be the most broken in the
>>> western world.
>>
>> Not that I disagree, but what would you say are the most important
>> things wrong with it? As compared to those in other countries, I
>> mean. Disclaimer: I am nearly completely ignorant of patent laws
>> in any country other than the US, so naming specific countries
>> would probably help me.
>
> Primarily the patent doorstep instead of a patent bar.
>
> Secondarily the imbalance in resources between patent lawyers and
> patent examiners.
>
> Finally the way the legal system allows blackmail by patent.
>
> I.e. being sued is so expensive that only your blue print country of
> the UK might be worse, it leads to settlements in patent cases with no
> or very low merit.

Okay, thanks. It might be interesting to say more but it's
clearly off topic in this group so I'll just leave it there.

[Chris M. Thomasson]

Agreed. "Why didn't we think of that, damn it!", well... That should be
the sound resounding, in a sense.

[Bakul Shah]

That is not a requirement. Not should it be. It must be novel, non-obvious (perhaps except in hindsight) and useful.

[Chris M. Thomasson]

The hindsight aspect would the horn resounding blasting right in the
ear(s) of a smart person reading somebody's ideas that make perfect
sense, in hindsight of course... In fact, the horn is heard by many
people. Novel, novel, n... ov... el...> Why did I not think of that:
damn it! ;^o

[Terje Mathisen]

Like I wrote previously, a large percentage of all really great ideas
(i.e. definitely worthy of patents) are of the "obvious in hindsight/why
didn't I think of that?" type.

Patents are supposed to be useful, but that is NOT an actual requirement.

[paul wallich]

Or "Why didn't I think of that earlier?" Pretty much every smart person
learning a new technical field will come up with "brilliant" ideas for
improvement or innovation only to find that someone else thought of it 5
or 10 or 40 years ago. (That's often a sign that their thinking is on
the right track.)

paul

[Ivan Godard]

Oh boy has that been me! You feel so smug with this great idea - and so
dashed when you find that it's well known to everyone but you.

But it's not a matter of "smart". Over a relatively low minimum,
creative != smart; it seems to be more an aspect of personality than any
raw computational capacity. Of course, you can have both, but that's a
multiplicative probability.

[Bakul Shah]

On Monday, September 9, 2019 at 2:50:53 AM UTC-7, Terje Mathisen wrote:
> Chris M. Thomasson wrote:
> > On 9/9/2019 1:10 AM, Bakul Shah wrote:
> >> On Monday, September 9, 2019 at 1:02:21 AM UTC-7, Chris M. Thomasson
> >> wrote:
> >>> On 9/3/2019 9:48 PM, Bonita Montero wrote:
> >>>>> Also CAS looks like a Fundamental Patent aka Pioneer Patent, ...
> >>>>> something that you can't work around, like IBM disk drive,
> >>>>> Xerography or Polaroid instant pictures.
> >>>>> In that case, the simpler the better.
> >>>>
> >>>> The patentability should depend on the simplicity as well.
> >>>>
> >>>
> >>> Agreed. "Why didn't we think of that, damn it!", well... That should be
> >>> the sound resounding, in a sense.
> >>
> >> That is not a requirement. Not should it be. It must be novel,
> >> non-obvious (perhaps except in hindsight) and useful.
> >>
> >
> >
> > The hindsight aspect would the horn resounding blasting right in the
> > ear(s) of a smart person reading somebody's ideas that make perfect
> > sense, in hindsight of course... In fact, the horn is heard by many
> > people. Novel, novel, n... ov... el...> Why did I not think of that:
> > damn it! ;^o
>
> Like I wrote previously, a large percentage of all really great ideas
> (i.e. definitely worthy of patents) are of the "obvious in hindsight/why
> didn't I think of that?" type.

Again, "greatness" is not necessary for something worth patenting.
A better mousetrap may certainly be worth patenting but it isn't exactly
a *great* idea (unless you really dilute the meaning of great). And not
all great ideas are obvious in hindsight. Edison & his assistants tested
thousands of materials before coming up with a filament derived from
bamboo that lasted 1000+ hours.

> Patents are supposed to be useful, but that is NOT an actual requirement.

It is. At least in the US Law. See the fourth requirement here:
https://www.uspto.gov/web/offices/pac/mpep/s2104.html

[Terje Mathisen]

To repeat what I said: It is NOT an actual requirement, there are simply
too many counterexamples. :-)

Alternatively, useful only for exceedingly small values of useful.

[Bakul Shah]

On Monday, September 9, 2019 at 9:01:55 AM UTC-7, Terje Mathisen wrote:
> Bakul Shah wrote:
> > On Monday, September 9, 2019 at 2:50:53 AM UTC-7, Terje Mathisen wrote:
> >> Patents are supposed to be useful, but that is NOT an actual requirement.
> >
> > It is. At least in the US Law. See the fourth requirement here:
> > https://www.uspto.gov/web/offices/pac/mpep/s2104.html
> >
> To repeat what I said: It is NOT an actual requirement, there are simply
> too many counterexamples. :-)
>
> Alternatively, useful only for exceedingly small values of useful.

Er... There is a long discussion of the utility requirement here: https://www.uspto.gov/web/offices/pac/mpep/s2107.html#d0e198469a
Quoting from it:
A claimed invention must have a specific and substantial utility.
This requirement excludes “throw-away,” “insubstantial,” or
“nonspecific” utilities, such as the use of a complex invention as
landfill, as a way of satisfying the utility requirement of 35 U.S.C. 101.

So it is an actual requirement but granted that the system is abused in
many ways and the patent office doesn't/can't always verify all claims.

[Anne & Lynn Wheeler]

comp.arch Fine-grained locking ... 1999 (20yrs ago) in response to Andy Grew
https://groups.google.com/forum/#!topic/comp.arch/AQABTm7iA54

[Chris M. Thomasson]

On 10/12/2019 1:30 PM, Anne & Lynn Wheeler wrote:
>
> comp.arch Fine-grained locking ... 1999 (20yrs ago) in response to Andy Grew
> https://groups.google.com/forum/#!topic/comp.arch/AQABTm7iA54
>

When did you first see hash based locking, as in hashing the address of
an object into a static table of locks? I was wondering when it first
came out. I did a crude impl here:

https://groups.google.com/d/msg/comp.lang.c++/sV4WC_cBb9Q/Ti8LFyH4CgAJ

[a...@littlepinkcloud.invalid]

Chris M. Thomasson <chris.m.t...@gmail.com> wrote:
> On 10/12/2019 1:30 PM, Anne & Lynn Wheeler wrote:
>>
>> comp.arch Fine-grained locking ... 1999 (20yrs ago) in response to Andy Grew
>> https://groups.google.com/forum/#!topic/comp.arch/AQABTm7iA54
>>
>
> When did you first see hash based locking, as in hashing the address of
> an object into a static table of locks? I was wondering when it first
> came out. I did a crude impl here:

We used Hans Boehm's hash locking in gcj, and that would have been in
the late 90s. Maybe 97-98?

Andrew.

[winden]

I recall hash locking was used in Solaris too, so maybe it came before that?

[Chris M. Thomasson]

On 10/31/2019 10:43 AM, winden wrote:
> I recall hash locking was used in Solaris too, so maybe it came before that?
>

It had to. Fwiw, I was just messing around with some locking code, and
said to myself: Why not simply hash the address of an object into a
static table of locks that never die? Well, this can be used to
implement a lot of things, C++ atomics wrt a zero value for all of the
following defines:

https://en.cppreference.com/w/cpp/atomic/atomic_is_lock_free

This is nice because an object does not need a lock for its address
hashes into a lock. Also, these locks stay around and never perish.

Well, my little idea cannot be new at all. Its so basic. Well, there is
a nice aspect where my experiment can allow threads to take a series of
locks in an atomic deadlock free operation by removing duplicates and
sorting a threads hashed locks:
_________________
// pseudo-code

mtx_table lock_table;


// some vars
int a = 3;
short b = 6;
double x = 1.234;

// a thread
{
locker locks(lock_table); // our hashed locks
locks.push(&a);
locks.push(&x);
locks.push(&b);

locks.lock();
// a, x, and b are all locked!
locks.unlock();
}
_________________


Then again, sorting these thread local locks cannot be new as well. Here
is a C++11 program, that should compile right up in GCC:
____________________________
/*
The Multex, simple deadlock free locking abstraction
By Chris M. Thomasson
____________________________________________________________*/


#include <iostream>
#include <functional>
#include <algorithm>
#include <mutex>
#include <thread>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <vector>


#define THREADS 7
#define N 123456


// Allows one to lock multiple addresses
// at once, and never hit a deadlock.
// It is an experiment.
namespace ct_multex
{
// A table of locks
struct mutex_table
{
std::vector<std::mutex> m_locks;

mutex_table(std::size_t size) : m_locks(size) { assert(size >
0); }

// totally contrived simple hash...
std::size_t hash(void const* ptr)
{
std::uintptr_t ptr_uint = (std::uintptr_t)ptr;
return (std::size_t)(((ptr_uint << 9) * 103) %
m_locks.size());
}
};

// A threads local indices into a table of locks
struct local_locks
{
std::vector<std::size_t> m_lock_idxs;
mutex_table& m_mtx_tbl;

local_locks(mutex_table& mtx_tbl) :
m_lock_idxs(), m_mtx_tbl(mtx_tbl) {}

// Add an address to be locked
void push_ptr(void const* ptr)
{
std::size_t idx = m_mtx_tbl.hash(ptr);
m_lock_idxs.push_back(idx);
}

// Deadlock free, baby! ;^)
void ensure_locking_order()
{
// sort and remove duplicates...
std::sort(m_lock_idxs.begin(), m_lock_idxs.end());
m_lock_idxs.erase(std::unique(m_lock_idxs.begin(),
m_lock_idxs.end()), m_lock_idxs.end());
}

// Take all of the locks
void lock()
{
// there can be a flag to minimize this...
ensure_locking_order();

std::size_t n = m_lock_idxs.size();

for (std::size_t i = 0; i < n; ++i)
{
m_mtx_tbl.m_locks[m_lock_idxs[i]].lock();
}
}

// Unlock everything
void unlock()
{
std::size_t n = m_lock_idxs.size();

for (std::size_t i = 0; i < n; ++i)
{
m_mtx_tbl.m_locks[m_lock_idxs[n - i - 1]].unlock();
}
}
};


// RAII scoped lock: Allows a thread to actualy take the locks
// It locks a threads local lock indices
struct scoped_lock
{
local_locks& m_locks;

scoped_lock(local_locks& locks) : m_locks(locks)
{
m_locks.lock();
}

~scoped_lock() throw()
{
m_locks.unlock();
}
};
}




// Test program...
//______________________________________

// Shared data
struct ct_shared
{
ct_multex::mutex_table& m_multex;

ct_shared(ct_multex::mutex_table& multex)
: m_multex(multex), data_0(1), data_1(2), data_2(3), data_3(4) { }

unsigned long data_0;
unsigned long data_1;
unsigned long data_2;
unsigned long data_3;
};



// a thread
void ct_thread(ct_shared& shared)
{
// Create our local locks
ct_multex::local_locks locks(shared.m_multex);

// Add some addresses
locks.push_ptr(&shared.data_2);
locks.push_ptr(&shared.data_0);

// Do some work
for (unsigned long i = 0; i < N / 2; ++i)
{
{
ct_multex::scoped_lock slock(locks);
// locked for data_0 and data_2
shared.data_0 += i;
shared.data_2 += i;
}

std::this_thread::yield();

{
ct_multex::scoped_lock slock(locks);
// locked for data_0 and data_2
shared.data_0 -= i;
std::this_thread::yield(); // for fun...
shared.data_2 -= i;
}
}

// Add some other addresses
locks.push_ptr(&shared.data_1);
locks.push_ptr(&shared.data_3);

// Do some more work...
for (unsigned long i = 0; i < N / 2; ++i)
{
{
ct_multex::scoped_lock slock(locks);
// locked for data_0, data_1, data_2 and data_3
shared.data_0 += i;
std::this_thread::yield(); // for fun...
shared.data_1 += i;
shared.data_2 += i;
shared.data_3 += i;
}

std::this_thread::yield();

{
ct_multex::scoped_lock slock(locks);
// locked for data_0, data_1, data_2 and data_3
shared.data_0 -= i;
shared.data_1 -= i;
shared.data_2 -= i;
std::this_thread::yield(); // for fun...
shared.data_3 -= i;
}
}
}


int main(void)
{
{
// Our mutex table
ct_multex::mutex_table multex_tbl(42);

// Our shared data
ct_shared shared(multex_tbl);

// Launch...
{
std::thread threads[THREADS];

// Create threads...
for (unsigned long i = 0; i < THREADS; ++i)
{
threads[i] = std::thread(ct_thread, std::ref(shared));
}

std::cout << "processing...\n\n";
std::cout.flush();

// Join threads...
for (unsigned long i = 0; i < THREADS; ++i)
{
threads[i].join();
}
}

// Verify the shared data...
std::cout << "shared.data_0 = " << shared.data_0 << "\n";
std::cout << "shared.data_1 = " << shared.data_1 << "\n";
std::cout << "shared.data_2 = " << shared.data_2 << "\n";
std::cout << "shared.data_3 = " << shared.data_3 << "\n";

assert(shared.data_0 == 1);
assert(shared.data_1 == 2);
assert(shared.data_2 == 3);
assert(shared.data_3 == 4);
}

std::cout << "\n\nfin!\n\n";

return 0;
}
____________________________