Automatic Locking
Automatic LockingOne of the ways of having a minimal amount of thread-safety in a language is to make all objects monitors by default and to block any call to a method which already has an activation on that object.
Now, what happens when you want recursion, or multiple concurrent reads? That's really simple. You still can't enter into the same method on the same object, so what you do is you clone the method when it's called.
That way, instead of having multiple activations of the same method, with a lock on the method, you have unique activations of multiple copies of the same method, each with their own lock. And of course, the compiler notices that the lock is unique to the activation so it optimizes it away.
As a result, you can create an infinite number of threads everywhere you go, and unless you're a total nitwit (ie, you create multiple primitive writing methods without using a locking method) then your code will be perfectly ThreadSafe.
Instead of having to make your code detect and avoid collisions between threads everywhere you go, the language should prevent collisions in the first place, and threads should go to extra effort to collide with each other. What you have to do everywhere should be done automatically for you. This is just common sense, so of course it is beyond the grasp of programmers. (Observe the lack of GarbageCollection in Cee/CeePlusPlus).
Observation: ThreadSafe threads replace CallWithCurrentContinuation. Continuations are basically threads, and vice versa, except that with threads you don't need to explicitly pass continuations around. This seems analogous to Monads (see MonadicProgramming ed.), which obviate the need to explicitly pass the world around.
Further observation: the difference between creating multiple activations from a method and copying an existing activation, is that between class-based languages like SmalltalkLanguage and prototype-based languages like SelfLanguage.
An OO programming language that automatically locks the target object on every method call is useless from the ConcurrentProgramming point of view.
Here's an example:
ObjectAObjectB ------------------ methodOfA() methodOfB() ... .... ObjectX.SetX1(2)ObjectY.setY1(3) .... .... ObjectY.methodY1(4) ObjectX.setX1(5)It is easy to see that the two executions interfere with each other regardless of setX1 and setY1 being automatically locked on X, respectively Y.
So what? At least with automatic locks, it's a lot easier to reason about thread safety. That's far from "useless".
It is useless because it lowers the level of abstraction with regards to concurrency to individual objects. It is harmful because it detracts the programmer from the bigger picture. Thread safety is about preserving correctness properties of the whole program on concurrent execution. That is if a set of computations are correct with regards to their specification when executed serially (one after another ), if the code is thread safe, then it will be correct on any concurrent execution. You haven't established any relation whatsoever between AutomaticLocking and thread safety.
Furthermore the practical evidence of Java programs tends to show (reference: Doug Lea's "Concurrent Programming in Java") that when programmers want to achieve thread safety by synchronizing all methods without thinking, they only dig themselves into a deeper hole, leading to programs that deadlock suddenly, may be unresponsive, and often time are not correct, therefore they are far from being thread safe.
The relation between locking and thread safety should be obvious.
Yep, too often when you can provide reason you may claim instead that it's obvious. Critical sections are but one means to structure concurrent programs. Therefore some thread-safe programs use locks to achieve thread safety, that's trivial. Having more locks than necessary is certainly not helpful. But more importantly, there are higher level abstractions than locks for dealing with concurrency. Locks are but one primitive element that can (please continue)
Yes, automatic locking creates more locks. Besides computer architecture and/or VM implementation automatically locks at the level of writing a word to memory.
Is putting the two together non-obvious to you?
Yes, it is bloody obvious:
I never reason about what locks to take away or what locks to put in, and I do actually write concurrent programs, and as far as I can tell they are correct. That's not how one should go about with designing concurrent programming. You typically use locks to implement higher level abstractions (the simplest example that you can think of are concurrent queues), and use those compositionally to create a concurrent system with desired properties, as opposed to sprinkling your locks all over in your object model and hoping for the best. If I was doing the later, than I might adhere to your proposal. A little bit of reading on ConcurrentProgramming wouldn't hurt you.
[I've done a little bit of reading. One thing I have read, for example, is Dijkstra, Lamport, et, al's "An exercise in cooperation". What they do there could be considered to be reasoning about "what locks to take away or what locks to put in", couldn't it? They start out with locks around larger sections of code, develop a coarse-grained solution, and then refine it to a finer-grained solution by reasoning about how the can take out the locks on the larger sections and move them in to smaller sections. This seems to be to some degree the methodology that is vaguely alluded to here. But they do not start with "all objects automatically locked". It is not even clear what it would mean in such a case where the only objects are individual storage cells. Where are the "objects" to lock? It is really a matter of making sure that certain relations are always kept true between the elements of the data structure, not of "locking objects" and "preventing two threads from accessing the same object at once". In order to keep these relations true, certain portions of code must be executed as critical sections. This may implicitly create some notion of "object" but I am not sure how.]
Because the fact that an all-synchronized program isn't correct is uninteresting.
Is the fact that an all synchronized program is more likely to deadlock and/or have some threads suffer from starvation equally uninteresting ?
Did you think I meant anything else?
All-unsynchronized programs have bad failure modes too. The interesting question isn't whether all-synchronized or all-unsynchronized are better since both suck. Rather, the interesting question is which gets you more easily to some kind of appropriate middle ground. Moreover, if I have to chose between one of the two extremes then I prefer all-synchronized because it lets one think in terms of objects rather than forcing one to think in terms of threads. I think this is more natural and appropriate for an OO language.
[Only it doesn't. You always have to think of threads in terms of threads. Whether you're adding locks or removing them, you've got to think of them in the context of multiple threads encountering them in every possible order. The problem with automatic locking is that you'll need to remove far more locks than you add, so the code will be more cluttered with threading details.]
Questions:
#feedsFrom: aPerson aPerson loses: 20 pints.! | lowerClass upperClass | upperClass feedsFrom: lowerClass.!In the above, lowerClass can't be fed on simultaneously by multiple members of upperClass, and no member of the upperClass can simultaneously feed on more than one person, of course.
And here's composition of locks. Since locks are just any methods, composition of locks is just method composition, surprise fucking surprise;
#suck: aNumberOfPints from: aVictim
aNumberOfPints isNegative ifTrue: [self lost: aNumberOfPints]
ifFalse: [aVictim suck: (aNumberOfPints negated) from: self.
self guzzled: aNumberOfPints.]!
| lowerClass upperClass |
upperClass suck: 20 from: lowerClass.!
No need for semaphores. No need for explicit locking. No need for anything except the single uniform concept of locks applied everywhere.
If methods => locks, and you don't have a method handy that lives as long as you want your lock to live, then just create a method that lives that long. That's it, that's all, end of story.
I think I didn't explain myself very well. Surely you don't mean that to synchronize access to multiple objects you have to implement double/triple/quadruple/... dispatch! Firstly, that would rapidly get out of hand due to combinatorial explosion. Secondly, it means that every object that is potentially used by multiple threads must know about every possible way that multiple threads might use it. That scatters implicit synchronization logic all around the code (in confusing double/triple/quadruple/... dispatch methods if I understand you correctly) instead of keeping it explicit and encapsulated in a single module, such as a monitor.
What does it mean to clone a method?
If cloning only copies the instructions, what's the point? It won't prevent data collisions. One copy of the instructions is just the same as any other copy of the instructions.
The point of cloning is to FORCE collisions! You only clone when you want a collision to occur and you can handle the consequences. So for example, if you want multiple readers.
Copying instructions has no effect on thread safety. If thread A is interrupted by thread B in the middle of updating data X, it won't make any difference if thread A is executing a different instance of the instructions than thread B. They both modify the same data. I don't think you understand thread safety at all.
"Cloning" a method is notional. In practice, the only thing it does is clone the lock on the method so that more than one thread can enter it simultaneously. And even that is notional because once the compiler sees the lock is useless, it should optimize it away.
Cloning a method removes the lock which comes with all methods by default.
Cloning a method when it's called is what ALLOWS the compiler to optimize away the lock. Making sure a lock is never used is the same thing as removing it. But in no case is this "doing nothing".
Making a copy of the method every time it's called allows the compiler to optimize away the lock on that method, because it knows the lock is useless. Does this result in thread safety? No, it doesn't. On the contrary, it's meant to do the exact opposite. But the compiler itself changes nothing with this optimization.
Making a copy of the instructions doesn't allow the compiler to optimize away the lock, at least not in a thread safe manner.
The difference is that you have locks on everything BY DEFAULT, instead of NOT HAVING ANY LOCKS by default. And that's the only difference since any really smart implementation will mark the "multiple copies of each method's instructions" as copy-on-write and so they won't actually exist until needed.
But even when they (the cloned instructions) exist they have no impact on thread safety. The addresses of the instructions don't matter. The addresses of the operands are what matter.
Method == Lambda == Code + State: It's not about cloning the instructions, it's about cloning the instructions and the state.
[RK explicitly said that state was not copied, only instructions. I hope we can all agree that making copies of code has no relation to thread safety.]
Can't you see these boys are fighting? Don't distract them with technical detail. [lol... just figured I'd take some of the credit for it]
I am sorry, I really don't understand the proposal here at all. All this fancy talk about objects and methods is confusing me, I guess, perhaps because I am an idiot.Can it be explained in the following terms? I assume the processes in question have shared memory. So there are set of variables that can be changed. Some of these are actually parts of larger variables (such as elements of arrays, for example), but we will consider variables to be the items at the smallest level of changeability. So I assume the idea is that each smallest item that can be changed has a lock around it. Okay, fine. But what is this "cloning stuff". Say I have a variable "totalServed", which is incremented whenever someone is served. How can you "clone" this variable if it is locked by one process when another wants to increment it? It will then become a totally separate variable and neither the clone nor the original will contain the correct values. Obviously I must be missing something.
Java already has this behaviour (apart for long and double values, but that's not important right now) and it's not sufficient to ensure thread safety. Atomic updates of data values, or even groups of related data values in a single object, is not enough. Thread safety involves much more than this one, trivial issue, as Costin has already explained rather well elsewhere. Thread safety involves coordinating the behaviour of multiple threads, not isolating each thread from the others.
Oh, and semaphores are not used for locking small objects (apart from binary semaphores, which are a degenerate case). They are used for coordinating the activity of threads.
Consider what cloning the method (activation, more accurately) actually entails... getTotalServed() would have a cloned version of that counter: the counter will likely remain constant in that space. If you call getTotalServed() again, after the counter has been incremented, you will have another counter, which will again remain constant, but will be different from the first activation. The point is that this would not be the default behaviour like it is in most other languages.
If we ignore RK's claim that cloning only copies instructions, consider a logChange() method. It adds a message to a shared change log. Two threads call logChange() at the same time so each gets a private copy of the log. Each thread may add several changes. How does the program reconcile these changes? How does it determine their order? How does it know to combine them at all?
Also, totalServed probably isn't on getTotalServed()'s stack. It might be in the same object. It might not. totalServed could be in another object or in a database. Is the language going to clone all data referenced by a method, and all data referenced by that data, ad infinitum, every time it clones a method? How can any data be shared between threads in this scheme? And if data can't be shared, why use threads? Why not use processes?
Two threads call logChange() at the same time, and the second one blocks. Why? Because that's the semantics that have been proposed and explained repeatedly over and over ad nauseum. The first thread executes logChange() and only after it has exited its activation will the second thread have an activation created for it. This is exactly what you'd do manually, except with AutomaticLocking it gets done, wait for it, automatically.
Now, of course it's entirely possible for a programmer to specify that when logChange() gets called, it will copy the method before entering it. This sidesteps the automatic lock on logChange() completely, and results in the same behaviour as you get in languages without automatic locking. The difference is that a programmer has to go to extra effort to sidestep a lock, instead of going to extra effort to create locks.
But it doesn't result in the same behavior as other languages. It either copies the instructions alone, resulting in no change in behavior, or it copies the instructions and all the data referenced by those instructions, leaving two copies of the data that have to somehow be combined.
I trust that it isn't easy to discern that the above is a) a deadlock waiting to happen, and b) if the language requires that all objects be synchronized (simulated in Java with the synchronized keyword in the class definition)--there isn't any good way to avoid it. (It can be avoided - define a locking order, say A before B, and require explicit synchronization when needed to preserve the locking order. Which brings us back to the start - with the user having to synchronize stuff manually.)
First of all, if all object's methods get synchronized then you can easily sidestep it by copying methods before executing them. Then you're no longer dealing with the same method. So you can sidestep the synchronization.
And we have come back full circle, back to your inability to understand why "everything unlocked" is a stupid default in a threaded environment, why anyone would want "everything locked" by default, and why there is a difference between the two. That last bit seems to be pretty basic stuff, but apparently many people here are just too dumb to get it.
[Can all these people be too dumb to get this? It seems hard to believe. Perhaps it is not being explained very well. Is there somewhere these less intelligent, but perhaps not "too dumb to get it" people can be sent to read a more careful explanation, at their less high level (but still not a level so low that they are "too dumb to get it"? What is the point of saying they are "too dumb to get it"?]
The point is to declare very loudly and publicly that this discussion is over, that the other participants are beneath contempt and undeserving of interaction, and that they are trolls / butchers / vandals whose actions on this page will be watched from this point forward.
It is extremely suspicious when some asshole asks for an explanation to a blatantly obvious question then another of those assholes deletes the response. Whence comes the suspicion that no mass of evidence would ever be sufficient to make these trolling assholes "understand" what's being proposed on this page. Only a gun might.
[Is what is being proposed totally new? If so, is it not reasonable that people may have trouble understanding it? If not, can a reference please be given to a place that explains it in more detail? This does not seem like an unreasonable request.]
Automatic locking doesn't seem new; it seems bloody obvious. It took me exactly zero seconds and zero effort to "come up" with them. It didn't come in as a flash of insight or realization. It was just the way I imagined monitors did work in any language that supports them. Automatic locking is all based on a misconception that the endless talks by AlanKay and DavidUngar about how objects are these little independent units were meant seriously.
(Note the wide dissonance between many people's "What the fuck are you even talking about?" and CostinCozianu's casual "This is all useless because it bears no relation to anything else in ConcurrentProgramming.")
And no, it is not at all reasonable for people to be unable to understand automatic locking. It's been explained on this page three or four times, in excruciating detail. Automatic locking is a terribly obvious idea, worth one or two papers in some obscure journal at best.
[The only way I can make sense of "what is being proposed" here is to presume it is something very trivial, and only handles cases where some function is not thread-safe because two different invocations of it use the same temporary storage so that if one is interrupted before completion, the second may corrupt it. If this sort of stuff is automatically "cloned" before being used, then one possible source of corruption will be eliminated. Maybe that is all that is intended to be addressed by this proposal]
No, that's not it at all. Automatic locking is utterly trivial but you still don't understand what it does, how it does it, or what it's good for.
Read some papers on Self. Read the stuff at Jecel's Merlin web site and wiki. They might expand your mind enough to understand what's being proposed.
In the current crop of programming languages, locks are always manually implemented and method activation is always automatic. So you got the dumb idea that what we're proposing is ... to manually implement locks and automatically implement method activation??? Well, that's not it.
The idea is to automatically place locks on all method / object pairs and to change the semantics of automatic method activation so they stay sane; a thread that calls a locked method blocks on that method's lock. From that default, it would be possible for a programmer to effectively take away the locks on a method by manually doing screwy things to method activation.
I've read lots of papers on Self. I've implemented a prototype based language. I've written libraries for CSP-like concurrent programming in C++ and Java. I've written several middleware platforms for concurrent and distributed programming. I've designed a language for specifying interactions between concurrent objects that integrate process calculi into the language so that its possible to prove that the interactions are deadlock/livelock free. And I still cannot understand exactly how your "cloning method" scheme will help with concurrent programming one bit.
Can you give me references to the Self papers that describe how Self manages concurrency.
Note: I know how Self dispatches methods and implements method activations and it doesn't clone methods. It implements stack frames as objects and has a prototype object for each lexical scope that it clones when it needs to create an environment for that scope.
I think that we could understand a great deal more if you gave us a concrete example. Can you show us how you would implement a bounded queue (also known as a channel) that can be used to transfer values (let's say integers for simplicity) from a producer to a consumer? This is an example that is used in all introductory concurrent programming textbooks, so it would let us compare your approach against existing approaches.
I'll start, using a Java-ish syntax:
Here's the shared queue. It can hold up to 10 items.
queue = new Queue(10);
Here's the producer thread:
int value = 0;
do {
queue.put(value);
value = value + 1;
}
Here's the consumer thread:
for(;;) {
int value = queue.get();
print("got " + value);
}
Here's the skeleton of the queue class.
class Queue {
int[] items;
int head;
int size;
public Queue( int capacity ) {
items = new int[capacity];
head = 0;
size = 0;
}
public void put( int item ) {
// block while size == items.length.
HOW DO YOU DO THIS IN YOUR APPROACH?
items[(head+size) % items.length ] = item;
size = size + 1;
// wake any waiting consumer threads
HOW DO YOU DO THIS IN YOUR APPROACH?
}
public int get() {
// block while size == 0.
HOW DO YOU DO THIS IN YOUR APPROACH?
size = size - 1;
int result = items[(head+size) % items.length];
// wake any waiting producer threads
HOW DO YOU DO THIS IN YOUR APPROACH?
return result;
}
}
Any answers for this?
After reading this page, seems at least half of the discussion could've been avoided by stating the concepts more clearly, and restraining to the topic.
This is my take, but feel free to add/remove/modify:
Object Orientation
This proposal (or feature/theory/?) is not necessarily about object oriented languages. It's about locking a method that modifies an object, but could be applied equally to a function/process that mutates data in any way.
Automatic Locking:
The basic idea is to lock every method on a call. It's difference from an explicit locking mechanism is just that it's implicit, and automatic for every method (or function/...). If you don't do anything to avoid it, you can't call a method that didn't finish a previous execution.
Also there's no way to avoid the method or function from locking when being called.
Method cloning:
Some times you need to allow a call to a method that might be locked. As an example: a recursive method, which starts a new execution of itself before finishing and unlocking. For that, the mechanism proposed is:
Make a clone of the method, that will have a new lock. It's just a way to bypass the lock (it's NOT to give thread safety, but rather unsafe execution).
About call/cc
Ignore that part. It's not really significant to the topic, it's a whole topic on to itself, and would actually be best to discuss it elsewhere. Would be nice to see that page, though!.
fs.
And it still sounds like a bad idea. In the multi-threaded code I write, I've only wanted the locks under discussion when writing logging functions. Most functions would need to be cloned and it appears that I would need to say that at every point that I called it. That sounds like a real pain. Furthermore, it doesn't help in what I've found to be the more common case, protecting data from changes made by different functions. (See the bounded queue example above.) In short, it adds a lot of overhead when writing the code and provides very little in the way of benefits.
EditText of this page
(last edited February 28, 2014)
or FindPage with title or text search