Does TM == super strong cache-coherency and incompetent programmers?
Chris Thomasson
coming out of college these days. This makes be start to think of the
effects that Transactional Memory will have on the classroom. STM will
prevent any student from learning the fundamentals' of shared memory. Heck,
it seems that if you even mention the phrase "shared mutable data-structure"
around a student these days they start to shriek, panic, hyperventilate and
crap all over themselves. IMO, STM it only going to make the get worse and
worse. How are the Professors going to address the "Concurrency Revolution"
in their classrooms? Are they going to lead their students right off a cliff
with transactional memory? I hope to GOD that STM is not as dangerous as I
think it is... It could lead to a generation of incompetent multi-thread
programmers who are so inept that they can't even begin to think about how
they would use locks without deadlocks.
I also think of the negative effects that TM will have on the hardware. The
cache coherency mechanism that could properly support a robust transactional
memory scheme would have to be really strict IMHO... Think of scenarios in
which there could be lots of reader threads iterating over large shared
linked data-structures in parallel... The transactional coherency system
could potentially wind up having to track all of those many thousands of
reads transactions' that will be generated my the frequently reading
threads... It would die from livelock; ahh the explicit contention manager
to the rescue! So, when the times get tough for TM, it basically is forced
to fold under its security blanket, and wait for things to cool way down for
a while... This is because TM is kind of like obstruction free algorithms...
One small trivial interference from another thread, and the operations dies
and asks the contention manager if it can retry. I am all for very weak
cache-coherency and crystal clear memory model documentation. I am not for
super strong cache that TM will require...
Any thoughts?
Joe Seigh
> I am saddened by the apparent lack of multi-threading experts there are
> coming out of college these days. This makes be start to think of the
> effects that Transactional Memory will have on the classroom. STM will
> prevent any student from learning the fundamentals' of shared memory. Heck,
> it seems that if you even mention the phrase "shared mutable data-structure"
> around a student these days they start to shriek, panic, hyperventilate and
> crap all over themselves. IMO, STM it only going to make the get worse and
> worse. How are the Professors going to address the "Concurrency Revolution"
> in their classrooms? Are they going to lead their students right off a cliff
> with transactional memory? I hope to GOD that STM is not as dangerous as I
> think it is... It could lead to a generation of incompetent multi-thread
> programmers who are so inept that they can't even begin to think about how
> they would use locks without deadlocks.
I don't think anyone is an expert in anything coming out undergrad
programs. To the extent that they do teach multi-threading, they
probably screw up the students more than they help them with some
of their notoriously bad examples, the producer/consumer solution
using a circular queue being one of them.
Although deadlock can be a problem in multi-threading, it didn't get to
be a serious problem until they combined multi-threading with OO with
some really bad choices of design patterns. And it didn't and doesn't
really help that the architects of these systems had/have the attitude
that you can do fundamental infrastructure design as if multi-threading
doesn't exist. Single threaded design doesn't translate into a multi-threaded
environment very well. There used to be this term applied to old fashioned
obsolete thinking, punch card mentality. Well, single-threaded
mentality is the new punch card mentality.
>
> I also think of the negative effects that TM will have on the hardware. The
> cache coherency mechanism that could properly support a robust transactional
> memory scheme would have to be really strict IMHO... Think of scenarios in
> which there could be lots of reader threads iterating over large shared
> linked data-structures in parallel... The transactional coherency system
> could potentially wind up having to track all of those many thousands of
> reads transactions' that will be generated my the frequently reading
> threads... It would die from livelock; ahh the explicit contention manager
> to the rescue! So, when the times get tough for TM, it basically is forced
> to fold under its security blanket, and wait for things to cool way down for
> a while... This is because TM is kind of like obstruction free algorithms...
> One small trivial interference from another thread, and the operations dies
> and asks the contention manager if it can retry. I am all for very weak
> cache-coherency and crystal clear memory model documentation. I am not for
> super strong cache that TM will require...
>
> Any thoughts?
>
You're talking about hardware support for TM. I don't think they're anywhere
near that point. STM still has to prove its value. And if its value is
only with certain classes of applications, there may never be enough
justification to put it in hardware.
The obstruction-free will be a problem since it pushes that issue into the
application developer's hands where there's no control over things. So
instead of people coming on c.p.t. asking if there are any tools to detect
deadlock, they'll be asking for tools to detect potential lack of forward
progress.
One observation about the video. Simon and Tim somehow implied that with STM you
don't have to deal with locks and condvars. That's not true. You still need
atomic blocks/functions wherever you needed locks, and you need retry's wherever
you used condvars. The main difference being you don't have deadlock, and
with retry's you get rid of that problem where someone may not realize some
subroutine does a condvar wait and releases a lock temporarily. With retries
your global invariants that the subroutine may not be aware of will still hold.
That's kind of nice.
To net it out, I think STM and lock-free are trying to solve two different
problems. STM is about avoiding deadlock and lock-free, as I see it, is
more about scalability, although some lock-free is useful for its async safety,
lock-free queues for example. So they can be complementary -- as long as
somebody doesn't start a war with STM. :)
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software.
Chris Thomasson
news:Huydnftz88M7bPfY...@comcast.com...
> Chris Thomasson wrote:
>> I am saddened by the apparent lack of multi-threading experts there are
>> coming out of college these days.
[...]
> I don't think anyone is an expert in anything coming out undergrad
> programs.
Well, yeah thats true...
> To the extent that they do teach multi-threading, they
> probably screw up the students more than they help them with some
> of their notoriously bad examples, the producer/consumer solution
> using a circular queue being one of them.
;^(...
>> It could lead to a generation of incompetent multi-thread programmers who
>> are so inept that they can't even begin to think about how they would use
>> locks without deadlocks.
>
> Although deadlock can be a problem in multi-threading, it didn't get to
> be a serious problem until they combined multi-threading with OO with
> some really bad choices of design patterns. And it didn't and doesn't
> really help that the architects of these systems had/have the attitude
> that you can do fundamental infrastructure design as if multi-threading
> doesn't exist. Single threaded design doesn't translate into a
> multi-threaded
> environment very well. There used to be this term applied to old
> fashioned
> obsolete thinking, punch card mentality. Well, single-threaded
> mentality is the new punch card mentality.
Indeed :^)
>> I also think of the negative effects that TM will have on the hardware.
[...]
> You're talking about hardware support for TM. I don't think they're
> anywhere
> near that point.
I think SUNS Rock processor might have some TM or KCSS stuff in it... Not
sure..
> STM still has to prove its value. And if its value is
> only with certain classes of applications, there may never be enough
> justification to put it in hardware.
>
> The obstruction-free will be a problem since it pushes that issue into the
> application developer's hands where there's no control over things. So
> instead of people coming on c.p.t. asking if there are any tools to detect
> deadlock, they'll be asking for tools to detect potential lack of forward
> progress.
I guess are answer will have to be drop STM, or code a better explicit
contention manager.
:^)
> One observation about the video. Simon and Tim somehow implied that with
> STM you
> don't have to deal with locks and condvars.
I believe they compared them to bananas or something...
> That's not true. You still need
> atomic blocks/functions wherever you needed locks, and you need retry's
> wherever
> you used condvars. The main difference being you don't have deadlock, and
> with retry's you get rid of that problem where someone may not realize
> some
> subroutine does a condvar wait and releases a lock temporarily. With
> retries
> your global invariants that the subroutine may not be aware of will still
> hold.
> That's kind of nice.
Well, I have to agree. However, the overhead involved is IMHO, just too
much.
> To net it out, I think STM and lock-free are trying to solve two different
> problems. STM is about avoiding deadlock
When ever I hear a programmer complain about deadlock, I want to point them
to David Butenhofs book... If they can't get locks right, perhaps they
should learn how before blindly attaching themselves to STM... Humm... Need
to think more on this... Humm...
> and lock-free, as I see it, is
> more about scalability, although some lock-free is useful for its async
> safety,
> lock-free queues for example. So they can be complementary --
I guess you can use STM strictly in the writer-side of a lock-free reader
pattern. But, I am not too sure how I would do such a thing. Seems that if I
wanted to do this, I would have to create the STM from scratch. I don't want
my reader pattern to be in C, and not in the same room as a GC, so that
pretty much eliminates all of the existing STM implementations'. I guess I
can resurrect some of my old STM stuff, but this probably won't be good
enough for the STM diehards... I asked one of them if he would consider
using a minimalist STM in C, and he basically said that C is useless and
Haskell is the one true GOD.
;^(...
> as long as somebody doesn't start a war with STM. :)
<rant>
The main thing that pisses me off when ever I hear somebody spewing their
marketing hype on STM is when they start to imply that any program that uses
threads and shared memory is equal to building a bridge with banana peels
held together by spit and toothpicks. The video mentions some of this...
That's implies that all of the multi-threaded shared memory programs we have
create must be fragile, unstable, unworkable, whatever... I get very
angry...
It also pisses me off when "they" start acting like threads are far too
complicated for any programmer to use, and if you do use it you must be
insane. The "threads are insane" defense was used here:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/b192c5ffe9b47926
Yikes!
</rant>
;^)
Ben Pfaff
> I don't think anyone is an expert in anything coming out undergrad
> programs. To the extent that they do teach multi-threading, they
> probably screw up the students more than they help them with some
> of their notoriously bad examples, the producer/consumer solution
> using a circular queue being one of them.
I'm in charge of the programming projects for an introductory
operating systems course, in which we attempt to teach
multithreading to some extent. I'd like to hear your (and
others') opinions on how concurrency should be presented to
students who are seeing it for the first time. Bear in mind that
the course is not primarily about concurrency.
We do provide a brief producer/consumer example using a circular
queue, to illustrate the usage of the condition variable
primitives we provide:
http://www.stanford.edu/class/cs140/projects/pintos/pintos_6.html#SEC101
Chris Thomasson wrote:
> I am saddened by the apparent lack of multi-threading experts there
> are coming out of college these days. This makes be start to think
> of the effects that Transactional Memory will have on the
> classroom. STM will prevent any student from learning the
> fundamentals' of shared memory. Heck, it seems that if you even
> mention the phrase "shared mutable data-structure" around a student
> these days they start to shriek, panic, hyperventilate and crap all
> over themselves. IMO, STM it only going to make the get worse and
> worse. How are the Professors going to address the "Concurrency
> Revolution" in their classrooms? Are they going to lead their
> students right off a cliff with transactional memory? I hope to GOD
> that STM is not as dangerous as I think it is... It could lead to a
> generation of incompetent multi-thread programmers who are so inept
> that they can't even begin to think about how they would use locks
> without deadlocks.
For what it's worth, I haven't been planning to add anything
about STM to the project curriculum. It's not a mainstream
operating system kernel concurrency technique yet, as far as I
know.
--
Ben Pfaff
email: b...@cs.stanford.edu
web: http://benpfaff.org
Chris Thomasson
> I guess you can use STM strictly in the writer-side of a lock-free reader
> pattern. But, I am not too sure how I would do such a thing. Seems that if
> I wanted to do this, I would have to create the STM from scratch.
> I don't want my reader pattern to be in C, and not in the same room as a
> GC, so that
^^^^^^^^^^^^^^^^^
should be
I definitely want my reader pattern to be in C, and not in the same room as
a GC, so that
> pretty much eliminates all of the existing STM implementations'.
sorry for any confusion... Man, I have got to go right now... I am late for
a meeting!
DAMN!
Joe Seigh
> Joe Seigh <jsei...@xemaps.com> writes:
>
>
>>I don't think anyone is an expert in anything coming out undergrad
>>programs. To the extent that they do teach multi-threading, they
>>probably screw up the students more than they help them with some
>>of their notoriously bad examples, the producer/consumer solution
>>using a circular queue being one of them.
>
>
> I'm in charge of the programming projects for an introductory
> operating systems course, in which we attempt to teach
> multithreading to some extent. I'd like to hear your (and
> others') opinions on how concurrency should be presented to
> students who are seeing it for the first time. Bear in mind that
> the course is not primarily about concurrency.
>
> We do provide a brief producer/consumer example using a circular
> queue, to illustrate the usage of the condition variable
> primitives we provide:
> http://www.stanford.edu/class/cs140/projects/pintos/pintos_6.html#SEC101
>
I think the attractiveness of producer/consumer w/ circular queue is
that it appears to kill two birds with one stone. You get to teach
two concepts at once. The problem is that a lot of students end up
permanently conflating the two. Later on they want to do something
slightly different and in some cases try to do something totally
innapropiate with that implementation, or just end up totally
confused since they were never clear on the concepts in the first place.
Some of them end up on c.p.t. where we get to try to undo some of the
damage.
What might help is to abstract out the api to the producer/consumer problem
and do several implementations to make the distinction between interface
and implementation. So for example, in Java you could define an interface
and provide two implementations, one using GC to collect dequeued nodes and
one using a circular queue to recycle them. The circular queue can be
implemented two ways at least, an array or a linked list. Use one as an
example and the other as a programming assignment. You can do the same
with C++, I just used Java as an example.
Mitch...@aol.com
Chris Thomasson wrote:
> Any thoughts?
TM (in either hardware or software) implementations are for the vast
majority of
programmers who just want synchronization-like-stuff to 'work', and (at
least
initially) don't care about the performance so much. Where 'work' means
with robustness, without odd failure cases, without deadlock,...
For those select few who can manage the intellectual complexity of the
space
of nonBlocking, waitFree, lockFree algorithms and achieve performance,
without
loosing robustness; TM is no panacea. The sum total of these
programmers
is well under 1% of the total number of actual programmers.
Joe Seigh
> Chris Thomasson wrote:
>
>>Any thoughts?
>
>
> TM (in either hardware or software) implementations are for the vast
> majority of
> programmers who just want synchronization-like-stuff to 'work', and (at
> least
> initially) don't care about the performance so much. Where 'work' means
> with robustness, without odd failure cases, without deadlock,...
You still have to know how to use locks properly. Deadlock isn't high
on the list of problems we deal with on c.p.t. but maybe we don't get
a representative sampling of real world problems. But if you can get
rid of the potential for deadlock and still manage to scale (a big if)
that would be nice.
>
> For those select few who can manage the intellectual complexity of the
> space
> of nonBlocking, waitFree, lockFree algorithms and achieve performance,
> without
> loosing robustness; TM is no panacea. The sum total of these
> programmers
> is well under 1% of the total number of actual programmers.
>
I'm not sure what that number has to do with anything. It's the percentage
of programmers who know how to avoid deadlock using conventional synchronization
that matters. And to the best of my knowlege there isn't any shortage of
programmers with those skills. There are severe shortages of programmers
with those skills and the improbable combination of other skills that some
employers seem to want these days. But all that proves is that some employers
are reality challenged. The HR departments are seemingly filled with idiots
who think the probability of 10 heads out of 10 coin tosses is 50%.
Which boils down to what STM is really about. It's a market opportunity to
exploit customers who don't know to to manage multi-threaded programming
projects properly. Hi-tech will save them from their stupidity.
Terje Mathisen
> Ben Pfaff wrote:
>> Joe Seigh <jsei...@xemaps.com> writes:
>>
>>
>>> I don't think anyone is an expert in anything coming out undergrad
>>> programs. To the extent that they do teach multi-threading, they
>>> probably screw up the students more than they help them with some
>>> of their notoriously bad examples, the producer/consumer solution
>>> using a circular queue being one of them.
>>
>>
>> I'm in charge of the programming projects for an introductory
>> operating systems course, in which we attempt to teach
>> multithreading to some extent. I'd like to hear your (and
>> others') opinions on how concurrency should be presented to
>> students who are seeing it for the first time. Bear in mind that
>> the course is not primarily about concurrency.
>>
>> We do provide a brief producer/consumer example using a circular
>> queue, to illustrate the usage of the condition variable
>> primitives we provide:
>> http://www.stanford.edu/class/cs140/projects/pintos/pintos_6.html#SEC101
>>
>
> I think the attractiveness of producer/consumer w/ circular queue is
> that it appears to kill two birds with one stone. You get to teach
The particular sample shown in the Stanford link happens to be broken:
It will only work until the index variables first wrap around, unless
you guarantee that the buffer size is an integer fraction of the index
range, i.e. effectively it has to be a power of two.
[snip]
> What might help is to abstract out the api to the producer/consumer problem
> and do several implementations to make the distinction between interface
> and implementation. So for example, in Java you could define an interface
> and provide two implementations, one using GC to collect dequeued nodes and
> one using a circular queue to recycle them. The circular queue can be
> implemented two ways at least, an array or a linked list. Use one as an
> example and the other as a programming assignment. You can do the same
> with C++, I just used Java as an example.
Sounds like a good idea.
Terje
--
- <Terje.M...@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching"
Ben Pfaff
>> Ben Pfaff wrote:
>>> http://www.stanford.edu/class/cs140/projects/pintos/pintos_6.html#SEC101
> It will only work until the index variables first wrap around, unless
> you guarantee that the buffer size is an integer fraction of the index
> range, i.e. effectively it has to be a power of two.
Good point. I'll add a comment to this effect.
Terje Mathisen
> For those select few who can manage the intellectual complexity of the
> space
> of nonBlocking, waitFree, lockFree algorithms and achieve performance,
> without
> loosing robustness; TM is no panacea. The sum total of these
> programmers
> is well under 1% of the total number of actual programmers.
A small fraction of 'programmers' deserve the title, the rest is more or
less rubbish.
This seems to be another example of Sturgeons Law.
Stefan Monnier
>> problems. STM is about avoiding deadlock
I think you have to be careful not to mix things up too much.
Haskell's STM stuff has two sides:
1 - an implementation, based on optimistic "lock-free" techniques.
2 - a semantics based on atomicity annotations.
I believe what people like about it is the use of atomicity annotations,
which could also be provided by an implementation that uses locks (although
it may require slightly different semantics and annotations, or at least
more intensive compile-time analysis of the code to figure out which locks
to use where).
Locks, monitors, and friends have traditionally been used to provide
atomicity, so being able to specify atomicity directly is a great
improvement, because it eliminates a whole class of bugs. Also atomicity
annotations can be directly used by the compiler to allow traditional
optimizations within the atomic section, oblivious to parallelism, in
contrast to the delicate memory model issues we've seen with Java.
Yes, it's higher level so it introduces the usual problems with higher-level
constructs: performance tuning issues, trade-offs between different
implementation techniques, etc...
Stefan
Joe Seigh
>>>To net it out, I think STM and lock-free are trying to solve two different
>>>problems. STM is about avoiding deadlock
>
>
> I think you have to be careful not to mix things up too much.
> Haskell's STM stuff has two sides:
> 1 - an implementation, based on optimistic "lock-free" techniques.
> 2 - a semantics based on atomicity annotations.
>
> I believe what people like about it is the use of atomicity annotations,
> which could also be provided by an implementation that uses locks (although
> it may require slightly different semantics and annotations, or at least
> more intensive compile-time analysis of the code to figure out which locks
> to use where).
There's no difference between atomicity notations and locks except the
former can't deadlock.
>
> Locks, monitors, and friends have traditionally been used to provide
> atomicity, so being able to specify atomicity directly is a great
> improvement, because it eliminates a whole class of bugs. Also atomicity
> annotations can be directly used by the compiler to allow traditional
> optimizations within the atomic section, oblivious to parallelism, in
> contrast to the delicate memory model issues we've seen with Java.
You're going to have to explain a little more here. AFAIK atomic sections
have the same optimization restrictions that locked sections have. There
is some difference if you have a compiler that's aware of what variables
are non-shared local and what ones are shared global like the version of
Haskell involved, but the optimizations in that case would be the same
for both atomic and locked sections.
>
> Yes, it's higher level so it introduces the usual problems with higher-level
> constructs: performance tuning issues, trade-offs between different
> implementation techniques, etc...
>
That must be where the optimistic part comes in.
peter koch
Mitch...@aol.com skrev:
> Chris Thomasson wrote:
> > Any thoughts?
>
> TM (in either hardware or software) implementations are for the vast
> majority of
> programmers who just want synchronization-like-stuff to 'work', and (at
> least
> initially) don't care about the performance so much. Where 'work' means
> with robustness, without odd failure cases, without deadlock,...
>
/Peter
David Gay
Joe Seigh <jsei...@xemaps.com> writes:
> Stefan Monnier wrote:
>>>>To net it out, I think STM and lock-free are trying to solve two different
>>>>problems. STM is about avoiding deadlock
>>
>>
>> I think you have to be careful not to mix things up too much.
>> Haskell's STM stuff has two sides:
>> 1 - an implementation, based on optimistic "lock-free" techniques.
>> 2 - a semantics based on atomicity annotations.
>>
>> I believe what people like about it is the use of atomicity annotations,
>> which could also be provided by an implementation that uses locks (although
>> it may require slightly different semantics and annotations, or at least
>> more intensive compile-time analysis of the code to figure out which locks
>> to use where).
>
> There's no difference between atomicity notations and locks except the
> former can't deadlock.
An atomicity notation is a declarative specification of a goal, a lock is
one of several ways of achieveing that goal. Doesn't sound like the same
thing to me.
A couple of comments on Stefan's (hi!) posting:
- some recent STMs use locks (or equivalents) for objects being updated,
see "Compiler and Runtime Support for Efficient Software Transactional
Memory" and "Optimizing Memory Transactions" from PLDI'06:
http://portal.acm.org/citation.cfm?id=1133985&coll=portal&dl=ACM&CFID=7305866&CFTOKEN=80253681
http://portal.acm.org/citation.cfm?id=1133984&coll=portal&dl=ACM&CFID=7305866&CFTOKEN=80253681
(no pdf's there if you don't have an ACM subscription, but I suspect
google can find them without too much trouble)
- We wrote a paper on explicitly using programmer-specified lock
annotations to implement atomic sections: "Autolocker: synchronization
inference for atomic sections"
http://portal.acm.org/citation.cfm?id=1111068&coll=portal&dl=ACM&CFID=7305866&CFTOKEN=80253681
Available from
http://berkeley.intel-research.net/dgay/pubs/06-popl-autolocker.pdf
One significant drawback of this work is that it requires a whole-program
analysis to pick a lock order.
>> Locks, monitors, and friends have traditionally been used to provide
>> atomicity, so being able to specify atomicity directly is a great
>> improvement, because it eliminates a whole class of bugs. Also atomicity
>> annotations can be directly used by the compiler to allow traditional
>> optimizations within the atomic section, oblivious to parallelism, in
>> contrast to the delicate memory model issues we've seen with Java.
>
> You're going to have to explain a little more here. AFAIK atomic sections
> have the same optimization restrictions that locked sections have. There
> is some difference if you have a compiler that's aware of what variables
> are non-shared local and what ones are shared global like the version of
> Haskell involved, but the optimizations in that case would be the same
> for both atomic and locked sections.
Hmm, no. The fact that you're in a piece of code that holds at least one
lock doesn't mean that all the data you're accessing is protected by the
held locks. So what optimisations you can perform is still limited by
the memory models of the language and hardware. Conversely, in an
STM-style atomic section, you can pretend that no other threads exist
and not worry about memory model issues until the end of the section.
--
David Gay
dg...@acm.org
Joe Seigh
> Joe Seigh <jsei...@xemaps.com> writes:
>
>>Stefan Monnier wrote:
>>
>>>I believe what people like about it is the use of atomicity annotations,
>>>which could also be provided by an implementation that uses locks (although
>>>it may require slightly different semantics and annotations, or at least
>>>more intensive compile-time analysis of the code to figure out which locks
>>>to use where).
>>
>>There's no difference between atomicity notations and locks except the
>>former can't deadlock.
>
>
> An atomicity notation is a declarative specification of a goal, a lock is
> one of several ways of achieveing that goal. Doesn't sound like the same
> thing to me.
fix. Locked sections vs. atomic sections.
>
>
>>>Locks, monitors, and friends have traditionally been used to provide
>>>atomicity, so being able to specify atomicity directly is a great
>>>improvement, because it eliminates a whole class of bugs. Also atomicity
>>>annotations can be directly used by the compiler to allow traditional
>>>optimizations within the atomic section, oblivious to parallelism, in
>>>contrast to the delicate memory model issues we've seen with Java.
>>
>>You're going to have to explain a little more here. AFAIK atomic sections
>>have the same optimization restrictions that locked sections have. There
>>is some difference if you have a compiler that's aware of what variables
>>are non-shared local and what ones are shared global like the version of
>>Haskell involved, but the optimizations in that case would be the same
>>for both atomic and locked sections.
>
>
> Hmm, no. The fact that you're in a piece of code that holds at least one
> lock doesn't mean that all the data you're accessing is protected by the
> held locks. So what optimisations you can perform is still limited by
> the memory models of the language and hardware. Conversely, in an
> STM-style atomic section, you can pretend that no other threads exist
> and not worry about memory model issues until the end of the section.
>
That's the compiler support for shared data. So you get the compiler to
enforce no access to shared data except in a locked section. If the
implementation only accessed shared data via smart pointers you could
prevent updates to shared data unless it was in a locked section.
It might be better to compare the C++ version of STM with locking in C/C++.
More of an apples to apples comparison. And they mentioned in the video
that you had to be a little more careful with the C++ version.
Chris Thomasson
news:87r6vo6...@blp.benpfaff.org...
> Joe Seigh <jsei...@xemaps.com> writes:
>
>> I don't think anyone is an expert in anything coming out undergrad
>> programs. To the extent that they do teach multi-threading, they
>> probably screw up the students more than they help them with some
>> of their notoriously bad examples, the producer/consumer solution
>> using a circular queue being one of them.
>
> I'm in charge of the programming projects for an introductory
> operating systems course, in which we attempt to teach
> multithreading to some extent. I'd like to hear your (and
> others') opinions on how concurrency should be presented to
> students who are seeing it for the first time. Bear in mind that
> the course is not primarily about concurrency.
[...]
Well, if your doing an OS course I would first make sure my students
understood the basics of an OS. They would not even worry about concurrency
in this phase... Just turn off interrupts, and let them get that out of the
way...
After the students understand the OS basics, I would introduce them to
Petersons Algorithm and the SPARC. I would dedicate some resources to this
phase because its the most critical part IMHO... Teach them the algorithm
first... Don't mention anything about memory model or anything like that.
Alls you have to do it drill them on the fact that the algorithm has to be
executed in order; say that and nothing else. Test them on the algorithm and
make sure they know how, and can prove, that it works. Test them and make
sure they that the algorithm won't work if any of its operations are not in
a precise order.
After all of that, then teach them that the SPARC has a way to enforce the
order. You create an atomic operations API for the OS you teach. You get it
running on the SPARC. You teach your students exactly how the SPARC
maintains order of the Petersons Algorithm. You drill down on the lock
acquisition part of the algorithm needs to be executed before the lock
testing part starts. Explain how the lock acquisition is made up of stores.
Explain how the lock testing is made up of loads. So, the students already
know the order. Give them a simple two question test:
"Okay students... You know that the order of the algorithm has to be
precise. You know that the lock acquisition is stores, and the lock test is
loads. What SPARC instruction would you use to ensure the lock acquisition
is executed before the loads:
A. membar #LoadLoad
B. membar #LoadStore
C. membar #StoreStore
D. membar #StoreLoad
Where would you place the instruction
A. Before the lock acquisition
B. After the lock acquisition, and after the loads
C. After the lock acquisition, and before the loads
"
If you can get your students to pass the test, your well on your way to
creating some threading experts IMHO...
Any thoughts?
Chris Thomasson
[...]
the announcement of a transaction has to have #StoreLoad, and the commit of
a transaction has a #StoreLoad.
thats boatloads of overhead.
Ben Pfaff
[on introducing multithreading concepts to students in an OS
course]
> After the students understand the OS basics, I would introduce them to
> Petersons Algorithm and the SPARC. I would dedicate some resources to this
> phase because its the most critical part IMHO... Teach them the algorithm
> first... Don't mention anything about memory model or anything like that.
> Alls you have to do it drill them on the fact that the algorithm has to be
> executed in order; say that and nothing else. Test them on the algorithm and
> make sure they know how, and can prove, that it works. Test them and make
> sure they that the algorithm won't work if any of its operations are not in
> a precise order.
[...]
> If you can get your students to pass the test, your well on your way to
> creating some threading experts IMHO...
>
>
> Any thoughts?
I think your suggestion is a good one, but it is not well
supported by textbooks. At least, I'm not aware of a textbook
that does a good job of covering these concepts. We currently
use _Operating System Concepts_ (the "dinosaur book"), which does
not talk about non-blocking synchronization at all.
Of course, this just means that we would have to create or obtain
some supplementary materials that talk about memory models. Do
you happen to know of any good presentation of this material?
_Unix Systems for Modern Architectures_ is about the only book I
know that does a reasonable job, but it's too much to ask the
students to buy that book as well as _Operating System Concepts_.
Currently, we don't talk about load/store ordering or anything
like that in the lectures, although nonblocking synchronization
is briefly addressed in a couple of lecture slides. If you're
curious about what we do say in lectures about synchronization,
you (and anyone else) can take a look at lectures 3, 4, and 5 on
the course notes page:
http://www.stanford.edu/class/cs140/lectures/fall0607/
Feedback welcome.
--
"Writing is easy.
All you do is sit in front of a typewriter and open a vein."
--Walter Smith
柑\/b
>Any thoughts?
siete prodighi di parola ma per quanto riguarda esempi ==0
Markus Elfring
> lock doesn't mean that all the data you're accessing is protected by the
> held locks. So what optimisations you can perform is still limited by
> the memory models of the language and hardware. Conversely, in an
> STM-style atomic section, you can pretend that no other threads exist
> and not worry about memory model issues until the end of the section.
Will the proposed key word "atomic" (for the Haskell programming language)
prevent any headaches like they were introduced with the key word "synchronized"
in Java?
http://www-128.ibm.com/developerworks/library/j-jtp02244.html?ca=dgr-lnxw07JMMP1
Are there still any open issues in visibility details and fixing of memory
models for the target environments?
Regards,
Markus
Joe Seigh
From a user's point of view, no. Atomic is effectively a mandatory
lock as opposed to an advisory lock. You can't access shared memory
except inside an atomic region. Access outside of an atomic section
is done by copy by value so there is no memory barrier issues a user
has to be aware of.
You can get the same effect with locks by making them mandatory and
only copying by value in and out of a locked section. No moving
references in and out of a locked section.
From an implmentation point of view you'd have the same issues with
both atomic and locked, you'd need acquire and release semantics.
But the user won't really notice that.
mike
| A small fraction of 'programmers' deserve the title, the rest is
more or
| less rubbish.
|
| This seems to be another example of Sturgeons Law.
|
| Terje
Several years ago IBM did a study on programmer productivity. They
sent a common problem with test data tapes to several hundred
programmers. They found an absolutely huge gap between the average
and the best. It has been many years and my memory may be failing
but I recall something like 26 to 1. In another study they also found
a strong correlation between music and mathematics as educational
backgrounds and success in programming.
In spite of these supporting facts your comment is way too harsh and
worse leads to poor use of scarce resources.
With hardware price performance growing in accordance with Moore's law
over several decades the need for analysis, design and coding of new
systems far out strips any realistic estimate of available programming
talent. While almost any programming task will be done better and
faster by the best people some problems are pretty simple and can be
adequately solved by the mediocre programmer. Further, there remains
a great deal of room for improved education, better project
management, better languages and better tools to help improve the work
product of mediocre programmers.
One area were I think we will agree is that the range of programmer
salaries needs to expand to reflect actual productivity and not be
restricted to some socialist cap.
Mike Sicilian
Terje Mathisen
> | A small fraction of 'programmers' deserve the title, the rest is
> more or
> | less rubbish.
> |
> | This seems to be another example of Sturgeons Law.
> |
> | Terje
>
>
> Several years ago IBM did a study on programmer productivity. They
> sent a common problem with test data tapes to several hundred
> programmers. They found an absolutely huge gap between the average
> and the best. It has been many years and my memory may be failing
> but I recall something like 26 to 1. In another study they also found
> a strong correlation between music and mathematics as educational
> backgrounds and success in programming.
>
> In spite of these supporting facts your comment is way too harsh and
> worse leads to poor use of scarce resources.
OK, I think we probably agree here as well...
>
> With hardware price performance growing in accordance with Moore's law
> over several decades the need for analysis, design and coding of new
> systems far out strips any realistic estimate of available programming
> talent. While almost any programming task will be done better and
> faster by the best people some problems are pretty simple and can be
> adequately solved by the mediocre programmer. Further, there remains
Sure.
> a great deal of room for improved education, better project
> management, better languages and better tools to help improve the work
> product of mediocre programmers.
Good tools help great programmers as well. Personally I'm only competent
most of the time, then I have these nice flashes which touch on
greatness just to let me know what it's like. :-)
> One area were I think we will agree is that the range of programmer
> salaries needs to expand to reflect actual productivity and not be
> restricted to some socialist cap.
Not in Norway. :-(
Joe Seigh
>
> With hardware price performance growing in accordance with Moore's law
> over several decades the need for analysis, design and coding of new
> systems far out strips any realistic estimate of available programming
> talent. While almost any programming task will be done better and
> faster by the best people some problems are pretty simple and can be
> adequately solved by the mediocre programmer. Further, there remains
> a great deal of room for improved education, better project
> management, better languages and better tools to help improve the work
> product of mediocre programmers.
>
> One area were I think we will agree is that the range of programmer
> salaries needs to expand to reflect actual productivity and not be
> restricted to some socialist cap.
>
What? I thought salaries were driven by supply and demand. There's
some question about the alleged shortage of skilled programmers since
salaries haven't exactly been taking off. What exactly is causing
this is subject to debate, but communist conspiracy is as good as
any I've heard. :)
There is a subtext of the industry wanting to turn programming from
a skilled trade into a rote occupation, kind if like what they did
to the manufacturing trades, turning skilled craftsmen into assembly
line automata. They would like more software engineering successes
like the one with spreadsheets which literally anyone can "program".
Something like 80% of spreadsheet programs have errors. Of course
concurrency is a much simpler concept for many people to get their
head around than arithmetic, so I'm sure we won't have any problems
there.
Chris Thomasson
I guess you can contact Maurice Herlihy:
http://www.cs.brown.edu/people/mph/home.html
to see what reference materials' he is using for a class he teaches on
distributed computing:
http://www.cs.brown.edu/courses/cs176/
That should help...
> _Unix Systems for Modern Architectures_ is about the only book I
> know that does a reasonable job, but it's too much to ask the
> students to buy that book as well as _Operating System Concepts_.
>
> Currently, we don't talk about load/store ordering or anything
> like that in the lectures, although nonblocking synchronization
> is briefly addressed in a couple of lecture slides. If you're
> curious about what we do say in lectures about synchronization,
> you (and anyone else) can take a look at lectures 3, 4, and 5 on
> the course notes page:
> http://www.stanford.edu/class/cs140/lectures/fall0607/
> Feedback welcome.
Sure. I will take a look.
:^)
Chris Thomasson
>
> http://www.cs.brown.edu/people/mph/home.html
>
>
> to see what reference materials' he is using for a class he teaches on
> distributed computing:
>
> http://www.cs.brown.edu/courses/cs176/
>
>
> That should help...
Ahh, the textbook is going to be published next year... However, all of the
chapters seem to be downloadable now... Humm...
;^)
Chris Thomasson
model... It also contains some of that nice livelock-laced, or should I say
obstruction-free?, universal lock-free magic from Herlihy...
Ben Pfaff
> I guess you can contact Maurice Herlihy:
>
> http://www.cs.brown.edu/people/mph/home.html
>
>
> to see what reference materials' he is using for a class he teaches on
> distributed computing:
>
> http://www.cs.brown.edu/courses/cs176/
Wow, what a nice resource. Thanks for pointing it out.
--
God leaned close as mud as man sat up, looked around, and spoke. Man blinked.
"What is the purpose of all this?" he asked politely. "Everything must have a
purpose?" asked God. "Certainly," said man. "Then I leave it to you to think
of one for all this," said God. And He went away. --Vonnegut, _Cat's Cradle_
mike
My point about Moore's law was that lower hardware costs create new
opportunities to use computers that were not previously economically
feasible. Further, at one time hardware costs dominated every
system, software costs are now the dominant portion of most systems
and the ratio continues to grow. Indeed I have read that software is
more than half the total $120 million cost of the F22 Raptor, the
latest U.S. air superiority fighter.
With the terrible quality of system design that created the Y2K
problem, we saw a temporary peak in demand to fix it. Y2K had the
additional impact of jump starting the 3rd world outsource market and
that resulted in today's 1st world programmers competing in cost with
3rd world programmers. The apparent lag in salaries and programming
jobs is not the result of a drop in total demand for programming but
just a movement to lower cost suppliers. I am fairly confident that
the total world market for programmer man hours continues to grow year
by year.
| There is a subtext of the industry wanting to turn programming from
| a skilled trade into a rote occupation, kind if like what they did
| to the manufacturing trades, turning skilled craftsmen into assembly
| line automata. They would like more software engineering successes
| like the one with spreadsheets which literally anyone can "program".
| Something like 80% of spreadsheet programs have errors. Of course
| concurrency is a much simpler concept for many people to get their
| head around than arithmetic, so I'm sure we won't have any problems
| there.
| --
| Joe Seigh
The evolution from craftsmanship to an engineering discipline is a
good thing!
Current practices result in far too many failed projects, horrendous
cost over runs and ugly, unreliable and insecure systems. With
computers as the foundation of our modern economy, anything that
addresses these problems will yield major improvements to the general
standard of living just as the last industrial revolution did.
This is not to say that the transition will be pleasant for the
participants of this news group. However, even the most died in the
wool programmer should want an advanced AI based programmer assistant
that is smarter in this knowledge domain than any of us or even all of
us put together.
There is no reason to accept that spread sheets built by the great
un-washed need to have errors. Imagine a world where projects as
large and complex as Microsoft's new Vista OS could be done in an
afternoon and be error free! This may exceed your imagination but how
would you describe your PC to Thomas Edison?
Mike Sicilian
Elcaro Nosille
recocgnition for your IT-biases. Do something real that's needed
by the industry and get this recognition.
Joe Seigh
By definition, wouldn't we idiots be incapable of knowing what the
real needs of the industry are? What would these real needs be?
I'm assuming scalability isn't one of them, but I could be wrong.
Chris Thomasson
news:4574d025$0$30322$9b4e...@newsspool1.arcor-online.net...
> Chris, you're an idiot. You're frustrated that you can't get any
> recocgnition for your IT-biases. Do something real that's needed
> by the industry and get this recognition.
I hope the "industry" realizes the power of shared memory multi-threading.
Sounds like the trend is, "shared mutable data" is too advanced for any
programmer to even begin to think about addressing.
What say you?