Skip to main content
GameDev.net gamedev.net
🔒 Locked

[Scheme] Concurrency

Started by Ezbez Apr 6, 2009 at 3:56 PM 5 replies 2.2k views
Original Post
Ezbez
Ezbez
So I'm working slowly through Structure and Interpretation of Computer Programs, but I've really hit a stumbling block on this concurrency section (section 3.4). Take, for example, exercise 3.42. I don't see any difference (logically, that is. I do see what code has been changed) between the code in the exercise and the code in the reading. Why would doing Bitdiddle's suggestion be wrong? I assume that it actually *is* wrong only because the reading would have correct code and Ben Bitdiddle has a history of incorrectness. Continuing from there: exercise 3.44. Am I correct here to say that no, there is no need for a more complicated function here? So long as the withdrawal and the deposit are successful, there is no room for further error. All actions on any bank account are completely serialized. 3.45: Okay, I have no clue why this is wrong, but I suspect that this misunderstanding goes back to the same thing as exercise 3.42. Well, while writing this I just had the idea that perhaps the problem in 3.42 would be deadlock caused by exchange acquiring the mutex and then trying to have withdraw and deposit acquiring the same mutex. But since that's not discussed until later, is that really the right answer? Thanks in advance!
SamLowry
SamLowry
Here I am again, wouldn't want to let you down :)

Exercise 3.423.41
I'd say that Ben's suggestion is correct, for once. Serializing is only necessary when there's more than one step involved in the computation, but since executing "balance" is already atomic, there's no need to perform any kind of synchronization.

Exercise 3.44
My guess is that Louis is being paranoid.

Exercise 3.45
Quote:

Serialization implements the following idea: Processes will execute concurrently, but there will be certain collections of procedures that cannot be executed concurrently. More precisely, serialization creates distinguished sets of procedures such that only one execution of a procedure in each serialized set is permitted to happen at a time. If some procedure in the set is being executed, then a process that attempts to execute any procedure in the set will be forced to wait until the first execution has finished.

So, when executing serialized-exchange, we have the following sets:
{ a1.withdraw, a1.deposit, exchange }
{ a2.withdraw, a2.deposit, exchange }
First, exchange is activated, meaning that both sets have one active function and hence no withdraw or deposit function can be called. However, this is exactly what exchange tries to do. So, execution should block somewhere here:
(define (exchange account1 account2)  (let ((difference (- (account1 'balance)                       (account2 'balance))))    ((account1 'withdraw) difference)    ((account2 'deposit) difference)))

I'd say the main problem is the fact that the serialization is too conservative: a single process should be able to have more than one function inside the same serialization set active at the same time.

[Edited by - SamLowry on April 7, 2009 4:51:56 AM]
Ezbez
Ezbez
Thanks again, SamLowry! I'm good now on 3.44 and 3.45, but I don't understand your response to 3.42. It seems that you're actually answering 3.41 not 3.42. Could you elaborate?
SamLowry
SamLowry
You are absolutely right, my mistake.

Exercise 3.42, second try
I first thought that it'd make no difference, but as you said, it's Ben, and they keeping using the old version... so I doubted and even changed my mind.

I believe Ben's version could be wrong. The only piece of information about how serializers work comes from the paragraph above describing those sets, i.e. that only one element in that set can be active at any one time. Let's consider two processes A and B calling withdraw which we know shouldn't be allowed to happen concurrently.

Using the normal version, the set contains two different withdraw instances: the first one will be used by process A, second by process B. Because of the set-rules, it is guaranteed that if A is busy withdrawing, B will have to wait, and vice versa, which is exactly what we want.

Using Ben's version, the set only contains one withdraw, which is called by both A and B. Applying the set-rules in a strict way tells me that it'd then be ok for both A and B to execute withdraw concurrently as only one element in the set is active.

So, instead of thinking of "atomicized functions" we should be thinking about "atomicized function calls".

I'm not 100% certain, but I think it makes sense :)

[Edited by - SamLowry on April 7, 2009 5:53:21 AM]
Ezbez
Ezbez
Makes sense to me, at least. [smile]

Thanks.
pshin05
pshin05
I've also wondered about Exercise 3.42 and Sam's explanation makes sense to me as well.

So, if I understand this correctly ...

If I have some object A created by (define A (make-account 10))
And if A happened to have several worker threads each of the calling protected-withdraw, then
these calls of protected-withdraw may not be serialized.

Correct?
SamLowry
SamLowry
Quote:
Original post by pshin05
I've also wondered about Exercise 3.42 and Sam's explanation makes sense to me as well.

So, if I understand this correctly ...

If I have some object A created by (define A (make-account 10))
And if A happened to have several worker threads each of the calling protected-withdraw, then
these calls of protected-withdraw may not be serialized.

Correct?

Yes: using exercise 3.42's version of protected-withdraw, I do think that calls made by different processes will not be serialized and thus happen concurrently, which is Bad.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.