Acquiring multiple locks

Hi Folks -

I have an interesting little problem that can be trivially solved with
help from the VM but that I'm curious if there is a way of doing it from
Squeak directly. Here is the problem:

Given a set of N locks (semaphores), how can multiple processes acquire
subsets of those locks without deadlocking? E.g., it's fairly obvious
that if one process attempts to acquire lock A and B and another one
lock B and A that this leads to deadlock in a hurry. What's in
particular problematic for my use case is that I don't know which
semaphores are part of said set of locks and that I can't establish a
total order to make sure that lock A always gets acquired before lock B.

What I've been contemplating is to add a primitive which does the
following: It attempts to acquire all the locks given as argument and if
one of them cannot be acquired it immediately releases all the locks
acquired so far and leaves the process suspended on the "failing" lock.
The return value will indicate whether all the locks were acquired and
therefore one can write a loop like here to acquire all of the locks:

   [self primitiveAcquireAll: locks] whileFalse.

In other words, if all the locks can be acquired the code just marches
through. If it fails to acquire a lock the process will stay suspended
until that particular lock is released and then retry to acquire the locks.

Is it possible to do that without a VM change?

Cheers,
   - Andreas

Andreas,

I solved this problem in an interesting but very simple way.  Our solution
was within a database.  What we did was commit a lock to the database, then
query for the lock, if you get more then one lock back then you remove your
lock.  In your process you could fail all the way back to the beginning.
This has the effect of favoring everyone failing instead of a deadlock.  If
you can keep the locking time down to a small percentage of overall
processing time it should work.

For optimistic locking we did something else that caused a commit failure
and eliminated locking altogether.  If you are pretty sure that the locking
time is small and the chances of a conflict are small and the rework of a
commit failure is tolerable by the user then pushing the failure to the
commit works well.  It doesn't sound like that's what you are asking about
so if you want to know more let me know.

Ron Teitelbaum
[hidden email]

  Ron and Andreas,

> I solved this problem in an interesting but very simple way.  Our solution
> was within a database.  What we did was commit a lock to the database, then
> query for the lock, if you get more then one lock back then you remove your
> lock.  In your process you could fail all the way back to the beginning.
> This has the effect of favoring everyone failing instead of a deadlock.  If
> you can keep the locking time down to a small percentage of overall
> processing time it should work.

  I wonder if to "fail" (or rollback) is an option for Andreas.  If
so, the two phase locking protocol should work.  In such protocol,
each process is divided (over time) into two phases.  In the first
phase, the process acquires all locks it needs, and in the second
phase, it only releases locks but never acquire new ones.  If the
process finds unavailable lock, it aborts.

-- Yoshiki

Hi Andreas,

Why using a primitive ? Because you are sure that processes are mutually
excluded ?

In this case, why not using a GlobalMutex to get similar protection

Of course MutexSet cannot work due to deadlock... but this LockSet might:

Object subclass: #LockSet
    instanceVariableNames: 'array'
    classVariableNames: 'GlobalMutex'
    poolDictionaries: ''
    category: 'Kernel-Processes'

LockSet>>initialize
    array := Array new

LockSet>>withAll: locks
    array := locks

LockSet>>mutex
    "a global mutex with lazy initialization"
    GlobalMutex ifNil: [GlobalMutex := Mutex new].
    GlobalMutex

LockSet>>critical: aBlock
    "evaluate aBlock if we can acquire all locks"
    | indexFailed |
    [indexFailed := self mutex critical:
        [(1 to: array size) detect: [:i | (array at: iLock)
            acquireNoWait = false] ifNone:
                [aBlock value.
               1 to: array size do: [:i | (array at: i) signal].
                0]]].
    indexFailed = 0] whileFalse:
        [(1 to: indexFailed -1) do: [:i | (array at: i) signal].
 (array at: indexFailed) wait; signal].

Semaphore>>acquireNoWait
    | waitingProcess wakeupProcess ok |
    waitingProcess := Processor activeProcess.
    ok := true.
    wakeupProcess :=
        [Processor yield.
        ok := false.
        self resumeProcess: waitingProcess] fork.
    self wait.
    wakeupProcess terminate.
    ^ok

You can replace wait by acquireLock, signal by releaseLock and acquireNoWait
by acquireLockNoWait and replace Semaphore with your own Lock class...

I did not try it cause it's late but maybe you will.

Nicolas


Le Mardi 27 Juin 2006 00:12, Andreas Raab a écrit :

Folks -

I've never run a server in Squeak (or anything else for that matter
(of course)).  I thought it would be easiest to start with a Swiki,
get it going, understand it, and then subvert it to the real purpose
I have in mind.

Can someone please...

1.  Point me at good documentation.

2.  Suggest which Squeak release would the best combination of being
relatively up to date, and yet having the least bit rot (if there is
any) in the server code.

3.  (If it isn't obvious from (1)) Hum a few bars about how you can
run the server on the same machine as you use it from, either in the
same Squeak, or in two separate copies.

Thanks much in advance

        - Dan

Hi Dan,

1)
A swiki would be a nice place to start, but if you haven't
looked into it yet, you really owe it to yourself to spend
a bit of time with Seaside. There is some good documentation
starting at http://seaside.org, and a couple of hours downloading
it and tinkering with the demos is time well spent. It's really
a nice piece of work.

2)
Squeak 3.8 is probably a comfortable choice.

3)
Two separate copies are probably what you'll want, but to get
started just use one. You can access the "server application"
through a web browser, and just use the normal Squeak display
to tinker with the server. There are various ways to connect
to the image when it's running as a headless server, depending
in part on what OS you prefer to use. Ian's VNC server seems
to be popular, and there is a web-accessible Squeak brower
included with the Seaside demos that you will probably find
interesting.

Dave

On Mon, Jun 26, 2006 at 05:58:10PM -0700, Dan Ingalls wrote:

Hi Dan!

Feel free to ask more - below follows a "get into the water" recipe for
building web apps (which I presume you want to do).

Dan Ingalls <[hidden email]> wrote:
> Folks -
>
> I've never run a server in Squeak (or anything else for that matter
> (of course)).  I thought it would be easiest to start with a Swiki,
> get it going, understand it, and then subvert it to the real purpose
> I have in mind.

Some words about the "real purpose" would make it a bit easier to give
advice. :)
 
> Can someone please...
>
> 1.  Point me at good documentation.

Ehrm, are we talking about a web app? Or some custom socket stuff? Or a
wiki implementation?
Swiki itself (the original implementation) is a bit cryptic and if you
aren't specifically interested in building a wiki-wiki, then I would not
start looking there.

If you want to start doing simple web stuff and get going quickly
without needing to understand the Magic of Seaside then I think
HttpView2 is very simple to get started and play with. It has a few
small examples and "Hello world" as a web app is a *single method* in *a
single class* started as a server with *a single line*.

> 2.  Suggest which Squeak release would the best combination of being
> relatively up to date, and yet having the least bit rot (if there is
> any) in the server code.

We who build web apps typically use 3.8 (or even 3.7) today. Note: If
you use 3.7/3.8 you could also install FastSocketStream (a new
implementation of class SocketStream) from SM and change the references
to use it instead of the standard SocketStream class. In 3.9 that
implementation of class SocketStream is default.

> 3.  (If it isn't obvious from (1)) Hum a few bars about how you can
> run the server on the same machine as you use it from, either in the
> same Squeak, or in two separate copies.

I always run it in the same image as you develop in, no problem. The
best way to *get started really quickly* if you want to grok the basics
is IMHO to:

1. Get Squeak 3.8, install these using the SqueakMap Package Loader
under the open... menu:
        - DynamicBindings   (this is a "thread locals" implementation by
Stephen Pair, it is used in KomHttpServer but is generally useful)
        - KomServices (a services framework, mainly Tcp, but also other stuff,
is used by other packages too)
        - KomHttpServer (the web server itself, has competition these days and
will eventually probably be merged with Swazoo but time, time...)
        - HTMLBuilder (a HTML generation library derived from Seaside and
HttpView. Seaside has now a newer model so it is only used in HttpView2
AFAIK)
        - HttpView2 (a very small simple web "framework" which simply maps
URL directories into methods in a neat way, used by SqueakMap for
example)

        ...and if you want to use the "newest" SocketStream now used in 3.9,
install FastSocketStream and change the reference in class HttpAdaptor
to use it.

2. Look in category HV-examples, read the class comments and methods.
Use the debugger - put a self halt in there, use your Firefox, and
examine the call stack inside the debugger all the way up to the Socket
communication.

Then, if HV2 doesn't fit your bill - it is best in simple apps or apps
where you want total control over URLs and state management (since it is
so much hands on and hackable) - Seaside is the way to go for more
advanced apps, but it adds quite a bit of magic so it is not as easy to
see how things work IMHO. But for advanced web apps Seaside blows HV2
out of the water. It also builds HTML using Smalltalk etc but uses
continuations etc to maintain all state on the server side - so you
don't need to muck about with URL parameters and all the other tricks to
keep track of your state. It also uses a better HTML rendering model
these days (the WACanvas classes).

> Thanks much in advance
>
> - Dan

regards, Göran

[hidden email] wrote:

> We who build web apps typically use 3.8 (or even 3.7) today. Note: If
> you use 3.7/3.8 you could also install FastSocketStream (a new
> implementation of class SocketStream) from SM and change the references
> to use it instead of the standard SocketStream class. In 3.9 that
> implementation of class SocketStream is default.

It is actually in the 3.8.1 updates. Which never really got agreed on to
become official...
I think I was waiting on some SM2 fixes? :-)

Otherwise I'll just make the updates available today or so.

Michael

Hi Michael!

Michael Rueger <[hidden email]> wrote:
Perhaps you were. :) Yes, the upgrade to 2.1, right. Darnit. Ok, I will
see if I can hack it tonight (for the 11th time).

> Otherwise I'll just make the updates available today or so.
>
> Michael

Hang on for a day or two. Perhaps someone else has something really
sweet to add to that update buying me some time?! :)

regards, Göran

[hidden email] puso en su mail :

> If you want to start doing simple web stuff and get going quickly
> without needing to understand the Magic of Seaside then I think
> HttpView2 is very simple to get started and play with. It has a few
> small examples and "Hello world" as a web app is a *single method* in *a
> single class* started as a server with *a single line*.
Dan:
I cook all my web needs on top of HttpView2  in a made to need .image.
Could have also Seaside if your needs requires and IMHO best combination is
Squeak server and Firefox browser.

The Ani Ani Web swiki is easy to setup and nice to look
http://201-212-99-13.cab.prima.net.ar:8888/ani

http://201-212-99-13.cab.prima.net.ar:8888 (Swikis) (regular swikis)

http://201-212-99-13.cab.prima.net.ar:9000/seaside/blog/SummerTeam/
http://201-212-99-13.cab.prima.net.ar:9000/seaside/blog/SqueakLightChronicle
s /
(Seaside )

http://201-212-99-13.cab.prima.net.ar:8085 (Server info, here you could see
if any other HttpView2 example is running)

All this run in hand made image and I could do same (or suit) to your needs,
only need send mail with your wishes.

Edgar



               
______________________________________________________
Yahoo! Autos. Más de 100 vehículos vendidos por día.
¿Qué esperás para vender el tuyo?
Hacelo ahora y ganate un premio de Yahoo!
http://autos.yahoo.com.ar/vender/

[hidden email] wrote:

> Perhaps you were. :) Yes, the upgrade to 2.1, right. Darnit. Ok, I will
> see if I can hack it tonight (for the 11th time).

ok

> Hang on for a day or two. Perhaps someone else has something really
> sweet to add to that update buying me some time?! :)

You should have plenty, now that you don't have to watch soccer anymore
;-) But too bad you guys got kicked out, had hoped in case you won the
championship IKEA would offer a week of free shopping ;-)

Michael

Michael Rueger <[hidden email]> wrote:
Grrrrrr. ;) Yeah, it was an alltogether painful experience. But it will
be very interesting to see you guys take on the wizards from
Argentina...

regards, Göran

PS. Sweden is better than the game against Germany showed - but alas, it
was just not meant to be.

[hidden email] puso en su mail :

> Grrrrrr. ;) Yeah, it was an alltogether painful experience. But it will
> be very interesting to see you guys take on the wizards from
> Argentina...

With more pray like this and if Referee is not like Italy vs Australia ,
maybee...

And waiting the code releare Goran...


edgar



       
       
               
___________________________________________________________
1GB gratis, Antivirus y Antispam
Correo Yahoo!, el mejor correo web del mundo
http://correo.yahoo.com.ar 

"Lic. Edgar J. De Cleene" <[hidden email]> wrote:
Right, I will try to do it tonight. But it will be "as it is". :)

regards, Göran

If you always aquire the locks in the same order you
will not deadlock, skipping lock acquisition is ok.

So, instead of a set of locks you should have an ordered
collection of locks. Acquisition of multiple locks must
proceed from low index to high index.

Terry
 
===========================================================
Terry Raymond       Smalltalk Professional Debug Package
Crafted Smalltalk
80 Lazywood Ln.
Tiverton, RI  02878
(401) 624-4517      [hidden email]
<http://www.craftedsmalltalk.com>
===========================================================

Many thanks to all who responded!  It's great to experience the
newbie support here.

In return I'll try to collect all the useful pointers along with my
experience somewhere on the swiki.  More than that, if things work
out, I'll post some stuff to play with.

Thanks again

        - Dan

dan if you donwload Pier (aka wiki + seaside) all the packages loads  
automatically :)

Stef

On 27 juin 06, at 19:21, Dan Ingalls wrote: