Thread: RE: [Algorithms] Locking without atomic operations
Brought to you by:
vexxed72
From: Carsten O. <car...@se...> - 2006-05-30 06:33:09
|
Well, I suspected there's some order of execution that breaks. That's why I'm asking for advice ;-) Carsten Orthbandt Founder + Development Director SEK SpieleEntwicklungsKombinat GmbH http://www.sek-ost.de Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt =20 > -----Original Message----- > From: gda...@li...=20 > [mailto:gda...@li...] On=20 > Behalf Of Joerg Wagner > Sent: Tuesday, May 30, 2006 8:27 AM > To: gda...@li... > Subject: Re: [Algorithms] Locking without atomic operations >=20 > Mhmmm, what about successive interuptions (or bad interleaving): >=20 > Thread1: > if(ReadA()!=3D0) > abort; > if(ReadB()!=3D0) > abort; >=20 > Thread2: > if(ReadA()!=3D0) > abort; > if(ReadB()!=3D0) > abort; >=20 > Thread1: > WriteA(myID1); > if(ReadB()!=3D0) > WriteA(0) > abort; > if(ReadA()!=3DmyID1) > abort; >=20 > Thread2: > WriteA(myID2); > if(ReadB()!=3D0) > WriteA(0) > abort; > if(ReadA()!=3DmyID2) > abort; >=20 > Thread1: > WriteB(myID1); > done. > Thread2: > WriteB(myID2); > done. >=20 > So both have written and aquired the lock :/ >=20 > Joerg >=20 >=20 >=20 > ------------------------------------------------------- > All the advantages of Linux Managed Hosting--Without the Cost=20 > and Risk! > Fully trained technicians. The highest number of Red Hat=20 > certifications in > the hosting industry. Fanatical Support. Click to learn more > http://sel.as-us.falkag.net/sel?cmd=3Dlnk&kid=3D107521&bid=3D248729& > dat=3D121642 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 >=20 |
From: Simon F. <sim...@po...> - 2006-05-30 07:18:32
|
=20=0D=0A=0D=0ACarsten Orthbandt wrote=0D=0A>=20=0D=0A> Well, I suspected t= here's some order of execution that breaks.=0D=0A> That's why I'm asking fo= r advice ;-)=0D=0A>=20=0D=0AI had a quick look through my old operating sys= tems text book but it=0D=0Aonly mentions indivisible operations.=0D=0A=0D=0A= I did have a thought (which probably has a flaw) but perhaps it might=0D=0A= give you some ideas.=0D=0A=0D=0AYou said each thread had a unique ID=3F If = so, would the following=0D=0Awork.... (I'm assuming that there are no probl= ems with the processes=0D=0Abeing on different processes and there being ca= che problems.)=0D=0A=0D=0AInitialise "lock" to 0.=0D=0A=0D=0ABOOL GetLock(v= olatile int lock, int ThreadsUniqueID)=0D=0A{=0D=0A if(lock)=0D=0A {=0D= =0A=09 return FALSE;=0D=0A }=0D=0A lock =3D ThreadsUniqueID;=0D=0A=0D= =0A if(lock !=3D ThreadsUniqueID)=0D=0A {=0D=0A return FALSE;=0D= =0A }=0D=0A return TRUE;=0D=0A}=0D=0A=0D=0AIt seems to me (but I have= n't looked too thoroughly) that even if the=0D=0Areads and writes are inter= mixed, exactly one process should get access.=0D=0A=0D=0ASimon=0D=0A=0D=0AP= S: I know there is a solution for multiprocessors with independent=0D=0Amem= ory systems involving timestamps etc but that's probably a little=0D=0Amore= than you'd need.=0D=0A=0D=0A=0D=0A> =20=0D=0A>=20=0D=0A> > -----Original = Message-----=0D=0A> > From: gda...@li...=0D= =0A> > [mailto:gda...@li...] On Behalf Of =0D= =0A> > Joerg Wagner=0D=0A> > Sent: Tuesday, May 30, 2006 8:27 AM=0D=0A> > T= o: gda...@li...=0D=0A> > Subject: Re: [Algorithm= s] Locking without atomic operations=0D=0A> >=20=0D=0A> > Mhmmm, what about= successive interuptions (or bad interleaving):=0D=0A> >=20=0D=0A> > Thread= 1:=0D=0A> > if(ReadA()!=3D0)=0D=0A> > abort;=0D=0A> > if(ReadB()!=3D0)=0D=0A= > > abort;=0D=0A> >=20=0D=0A> > Thread2:=0D=0A> > if(ReadA()!=3D0)=0D=0A> >= abort;=0D=0A> > if(ReadB()!=3D0)=0D=0A> > abort;=0D=0A> >=20=0D=0A> > Thre= ad1:=0D=0A> > WriteA(myID1);=0D=0A> > if(ReadB()!=3D0)=0D=0A> > WriteA(0)=0D= =0A> > abort;=0D=0A> > if(ReadA()!=3DmyID1)=0D=0A> > abort;=0D=0A> >=20=0D=0A= > > Thread2:=0D=0A> > WriteA(myID2);=0D=0A> > if(ReadB()!=3D0)=0D=0A> > Wri= teA(0)=0D=0A> > abort;=0D=0A> > if(ReadA()!=3DmyID2)=0D=0A> > abort;=0D=0A>= >=20=0D=0A> > Thread1:=0D=0A> > WriteB(myID1);=0D=0A> > done.=0D=0A> > Thr= ead2:=0D=0A> > WriteB(myID2);=0D=0A> > done.=0D=0A> >=20=0D=0A> > So both h= ave written and aquired the lock :/=0D=0A> >=20=0D=0A> > Joerg=0D=0A> >=20=0D= =0A> >=20=0D=0A> >=20=0D=0A> > --------------------------------------------= -----------=0D=0A> > All the advantages of Linux Managed Hosting--Without t= he Cost and=20=0D=0A> > Risk!=0D=0A> > Fully trained technicians. The highe= st number of Red Hat=20=0D=0A> > certifications in the hosting industry. Fa= natical Support. Click to=20=0D=0A> > learn more=20=0D=0A> > http://sel.as-= us.falkag.net/sel=3Fcmd=3Dlnk&kid=3D107521&bid=3D248729&=0D=0A> > dat=3D121= 642=0D=0A> > _______________________________________________=0D=0A> > GDAlg= orithms-list mailing list=0D=0A> > GDA...@li...=0D= =0A> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list=0D=0A= > > Archives:=0D=0A> > http://sourceforge.net/mailarchive/forum.php=3Fforum= _id=3D6188=0D=0A> >=20=0D=0A>=20=0D=0A>=20=0D=0A> -------------------------= ------------------------------=0D=0A> All the advantages of Linux Managed H= osting--Without the Cost=20=0D=0A> and Risk!=0D=0A> Fully trained technicia= ns. The highest number of Red Hat=20=0D=0A> certifications in the hosting i= ndustry. Fanatical Support.=20=0D=0A> Click to learn more=0D=0A> http://sel= =2Eas-us.falkag.net/sel=3Fcmd=3Dk&kid=107521&bid$8729&dat=121642=0D=0A> ___= ____________________________________________=0D=0A> GDAlgorithms-list maili= ng list=0D=0A> GDA...@li...=0D=0A> https://lists= =2Esourceforge.net/lists/listinfo/gdalgorithms-list=0D=0A> Archives:=0D=0A>= http://sourceforge.net/mailarchive/forum.php=3Fforum_ida88=0D=0A>=20=0D=0A= >=20=0D=0A=0D=0A******************=0D=0AThis e-mail has been sent from Imag= ination Technologies Limited.=0D=0APowerVR, Metagence, Ensigma and PURE Dig= ital are divisions=0D=0Aof Imagination Technologies Limited.=0D=0A=0D=0AThe= information contained in this e-mail, including any attachment,=0D=0Ais co= nfidential and may be legally privileged. It is intended solely=0D=0Afor t= he addressee(s) and access to this e-mail by anyone else is=0D=0Aunauthoris= ed. If you are not the intended recipient, any disclosure,=0D=0Acopying or= distribution or use of the information contained in this=20=0D=0Ae-mail, i= s prohibited and may be unlawful. If you have received this=0D=0Ae-mail in= error, please notify the sender by return e-mail and then=0D=0Adelete it f= rom your system.=0D=0A=0D=0AInternet communications cannot be guaranteed to= be secure,=0D=0Aerror or virus-free. The sender does not accept liability= for any errors=0D=0Aor omissions which arise as a result.=0D=0A=0D=0AAny v= iews expressed in this message are those of the author, except=0D=0Awhere t= he author specifies and, with authority, states them to be the=0D=0Aviews o= f Imagination Technologies Limited.=0D=0A |
From: Tom F. <tom...@ee...> - 2006-05-30 07:29:33
|
Doesn't work: > if(lock) > { > return FALSE; > } **swap to other thread here, which runs the same function and returns** > lock =3D ThreadsUniqueID; > etc... Now both threads believe they have the lock. I know of lots of reasons this is really hard. But I've never had to actually implement one of these without some sort of atomic read-modify-write operation. Sounds annoyingly difficult :-) TomF. > -----Original Message----- > From: gda...@li...=20 > [mailto:gda...@li...] On=20 > Behalf Of Simon Fenney > Sent: 30 May 2006 00:18 > To: gda...@li... > Subject: RE: [Algorithms] Locking without atomic operations >=20 >=20 > =20 >=20 > Carsten Orthbandt wrote > >=20 > > Well, I suspected there's some order of execution that breaks. > > That's why I'm asking for advice ;-) > >=20 > I had a quick look through my old operating systems text book but it > only mentions indivisible operations. >=20 > I did have a thought (which probably has a flaw) but perhaps it might > give you some ideas. >=20 > You said each thread had a unique ID? If so, would the following > work.... (I'm assuming that there are no problems with the processes > being on different processes and there being cache problems.) >=20 > Initialise "lock" to 0. >=20 > BOOL GetLock(volatile int lock, int ThreadsUniqueID) > { > if(lock) > { > return FALSE; > } > lock =3D ThreadsUniqueID; >=20 > if(lock !=3D ThreadsUniqueID) > { > return FALSE; > } > return TRUE; > } >=20 > It seems to me (but I haven't looked too thoroughly) that even if the > reads and writes are intermixed, exactly one process should=20 > get access. >=20 > Simon >=20 > PS: I know there is a solution for multiprocessors with independent > memory systems involving timestamps etc but that's probably a little > more than you'd need. >=20 >=20 > > =20 > >=20 > > > -----Original Message----- > > > From: gda...@li... > > > [mailto:gda...@li...] On=20 > Behalf Of=20 > > > Joerg Wagner > > > Sent: Tuesday, May 30, 2006 8:27 AM > > > To: gda...@li... > > > Subject: Re: [Algorithms] Locking without atomic operations > > >=20 > > > Mhmmm, what about successive interuptions (or bad interleaving): > > >=20 > > > Thread1: > > > if(ReadA()!=3D0) > > > abort; > > > if(ReadB()!=3D0) > > > abort; > > >=20 > > > Thread2: > > > if(ReadA()!=3D0) > > > abort; > > > if(ReadB()!=3D0) > > > abort; > > >=20 > > > Thread1: > > > WriteA(myID1); > > > if(ReadB()!=3D0) > > > WriteA(0) > > > abort; > > > if(ReadA()!=3DmyID1) > > > abort; > > >=20 > > > Thread2: > > > WriteA(myID2); > > > if(ReadB()!=3D0) > > > WriteA(0) > > > abort; > > > if(ReadA()!=3DmyID2) > > > abort; > > >=20 > > > Thread1: > > > WriteB(myID1); > > > done. > > > Thread2: > > > WriteB(myID2); > > > done. > > >=20 > > > So both have written and aquired the lock :/ > > >=20 > > > Joerg > > >=20 > > >=20 > > >=20 > > > ------------------------------------------------------- > > > All the advantages of Linux Managed Hosting--Without the Cost and=20 > > > Risk! > > > Fully trained technicians. The highest number of Red Hat=20 > > > certifications in the hosting industry. Fanatical=20 > Support. Click to=20 > > > learn more=20 > > > = http://sel.as-us.falkag.net/sel?cmd=3Dlnk&kid=3D107521&bid=3D248729& > > > dat=3D121642 > > > _______________________________________________ > > > GDAlgorithms-list mailing list > > > GDA...@li... > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > Archives: > > > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > >=20 > >=20 > >=20 > > ------------------------------------------------------- > > All the advantages of Linux Managed Hosting--Without the Cost=20 > > and Risk! > > Fully trained technicians. The highest number of Red Hat=20 > > certifications in the hosting industry. Fanatical Support.=20 > > Click to learn more > > = http://sel.as-us.falkag.net/sel?cmd=3Dk&kid=107521&bid$8729&dat=121642 > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_ida88 > >=20 > >=20 >=20 > ****************** > This e-mail has been sent from Imagination Technologies Limited. > PowerVR, Metagence, Ensigma and PURE Digital are divisions > of Imagination Technologies Limited. >=20 > The information contained in this e-mail, including any attachment, > is confidential and may be legally privileged. It is intended solely > for the addressee(s) and access to this e-mail by anyone else is > unauthorised. If you are not the intended recipient, any disclosure, > copying or distribution or use of the information contained in this=20 > e-mail, is prohibited and may be unlawful. If you have received this > e-mail in error, please notify the sender by return e-mail and then > delete it from your system. >=20 > Internet communications cannot be guaranteed to be secure, > error or virus-free. The sender does not accept liability=20 > for any errors > or omissions which arise as a result. >=20 > Any views expressed in this message are those of the author, except > where the author specifies and, with authority, states them to be the > views of Imagination Technologies Limited. >=20 >=20 >=20 > ------------------------------------------------------- > All the advantages of Linux Managed Hosting--Without the Cost=20 > and Risk! > Fully trained technicians. The highest number of Red Hat=20 > certifications in > the hosting industry. Fanatical Support. Click to learn more > http://sel.as-us.falkag.net/sel?cmd=3Dk&kid=107521&bid$8729&dat=121642 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_ida88 >=20 |
From: Carsten O. <car...@se...> - 2006-05-30 07:19:50
|
Interesting read, but... It comes close, but doesn't solve the problem. Dekker's algorithm (at least as far as I understand it) and this refinement both require me to know the number of clients, which I don't. Since enumeration of the address space is also not supported, I can't use a bit field with one bit for every client since no client is able to tell the actual number of clients to check interest against and in turn doesn't know how many bits to check. In the mentioned environment (it's only an example) this would need directory browsing in addition to HTTP GET and PUT, which is not available. Another restriction is that my client IDs are unique AND sparse. In the final application we're not even talking about integer IDs but obviously it will be GUIDs which makes scanning over all possible client IDs a no-go (not that it would make much sense with integer IDs either). I don't care if the locking is "fair" or very efficient, I only need a method that works for the (rare but possible) case of a collision. Thanks, Carsten Orthbandt Founder + Development Director SEK SpieleEntwicklungsKombinat GmbH http://www.sek-ost.de Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt =20 > -----Original Message----- > From: gda...@li...=20 > [mailto:gda...@li...] On=20 > Behalf Of Kenneth B. Russell > Sent: Tuesday, May 30, 2006 8:56 AM > To: gda...@li... > Subject: Re: [Algorithms] Locking without atomic operations >=20 > Have you looked into Dekker's algorithm and its generalizations to=20 > multiple (more than two) clients? I'm not completely sure the=20 > operations=20 > you have available cover what is needed to implement it but it sounds=20 > like it from a cursory look. The following reference points to other=20 > related references which offer fair solutions, meaning you won't run=20 > into livelock under heavy contention. This was found with a Google=20 > search for "dekker mutual exclusion generalization". >=20 > http://caltechcstr.library.caltech.edu/359/ >=20 > -Ken >=20 >=20 > Carsten Orthbandt wrote: >=20 > > I crawled the web for a solution to this but I only found references > > to "mostly" without atomic operations and such stuff. > >=20 > > Given N integer memory locations and only the operations > > value=3DRead(addr) > > and Write(addr,value), I'm looking for a way to syncronize=20 > access to a > > resource from multiple clients, each with a guaranteed=20 > unique integer > > id. > > The lock attempf should fail if there is already a lock or=20 > there's some > > sort of collision while obtaining the lock. > >=20 > > The solution I've come up but have not really verified is this: > >=20 > > Nominate two memory locations A and B. > >=20 > > Init: Set A and B to 0. All client IDs are >=3D1. > >=20 > > for Locking: > > if(ReadA()!=3D0) > > abort; > > if(ReadB()!=3D0) > > abort; > > WriteA(myID); > > if(ReadB()!=3D0) > > WriteA(0) > > abort; > > if(ReadA()!=3DmyID) > > abort; > > WriteB(myID); > > done. > >=20 > > I'll try to mold this into VMish code to do actual tests,=20 > but would like > > to ask if there's some well-known clever solution to this that I'm > > simply > > not aware of. > >=20 > > Please note that the REAL problem is not about IPC or such stuff, I > > really > > only have these two operations Read and Write, but an=20 > arbitrary number > > of > > "registers" to use (think of HTTP GET and PUT). Enumeration=20 > of anything > > is > > not available. > >=20 > > Best regards, > >=20 > > Carsten Orthbandt > > Founder + Development Director > > SEK SpieleEntwicklungsKombinat GmbH > > http://www.sek-ost.de > >=20 > > Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt > > =20 > >=20 > >=20 > > ------------------------------------------------------- > > All the advantages of Linux Managed Hosting--Without the=20 > Cost and Risk! > > Fully trained technicians. The highest number of Red Hat=20 > certifications in > > the hosting industry. Fanatical Support. Click to learn more > >=20 > http://sel.as-us.falkag.net/sel?cmd___________________________ ____________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_ida88 >=20 >=20 >=20 > ------------------------------------------------------- > All the advantages of Linux Managed Hosting--Without the Cost=20 > and Risk! > Fully trained technicians. The highest number of Red Hat=20 > certifications in > the hosting industry. Fanatical Support. Click to learn more > http://sel.as-us.falkag.net/sel?cmd=3Dlnk&kid=3D107521&bid=3D248729& dat=3D121642 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 >=20 |
From: Kenneth B. R. <kbr...@al...> - 2006-05-30 07:33:48
|
Can you implement the locking operation atomically on the server using an HTTP PUT or POST on the client? In other words, the client sends a PUT message containing its GUID and receives a response code indicating whether the lock operation succeeded. If it did, it is privileged to do whatever operations it needs to do under the cover of the lock. It would then later send an unlock message to the server using another PUT with its GUID. You could handle clients which disconnect in the middle of the operation using timeouts or a similar mechanism, and perhaps even use a two-phase commit so that inconsistent states can't be seen by other clients. Does any of this sound plausible? -Ken Carsten Orthbandt wrote: > Interesting read, but... > It comes close, but doesn't solve the problem. Dekker's algorithm > (at least as far as I understand it) and this refinement both require > me to know the number of clients, which I don't. Since enumeration > of the address space is also not supported, I can't use a bit field > with one bit for every client since no client is able to tell the > actual number of clients to check interest against and in turn doesn't > know how many bits to check. > In the mentioned environment (it's only an example) this would need > directory browsing in addition to HTTP GET and PUT, which is not > available. > Another restriction is that my client IDs are unique AND sparse. > In the final application we're not even talking about integer IDs > but obviously it will be GUIDs which makes scanning over all possible > client IDs a no-go (not that it would make much sense with integer > IDs either). > I don't care if the locking is "fair" or very efficient, I only need > a method that works for the (rare but possible) case of a collision. > > Thanks, > > Carsten Orthbandt > Founder + Development Director > SEK SpieleEntwicklungsKombinat GmbH > http://www.sek-ost.de > > Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt > > > >>-----Original Message----- >>From: gda...@li... >>[mailto:gda...@li...] On >>Behalf Of Kenneth B. Russell >>Sent: Tuesday, May 30, 2006 8:56 AM >>To: gda...@li... >>Subject: Re: [Algorithms] Locking without atomic operations >> >>Have you looked into Dekker's algorithm and its generalizations to >>multiple (more than two) clients? I'm not completely sure the >>operations >>you have available cover what is needed to implement it but it sounds >>like it from a cursory look. The following reference points to other >>related references which offer fair solutions, meaning you won't run >>into livelock under heavy contention. This was found with a Google >>search for "dekker mutual exclusion generalization". >> >>http://caltechcstr.library.caltech.edu/359/ >> >>-Ken >> >> >>Carsten Orthbandt wrote: >> >> >>>I crawled the web for a solution to this but I only found references >>>to "mostly" without atomic operations and such stuff. >>> >>>Given N integer memory locations and only the operations >>>value=Read(addr) >>>and Write(addr,value), I'm looking for a way to syncronize >> >>access to a >> >>>resource from multiple clients, each with a guaranteed >> >>unique integer >> >>>id. >>>The lock attempf should fail if there is already a lock or >> >>there's some >> >>>sort of collision while obtaining the lock. >>> >>>The solution I've come up but have not really verified is this: >>> >>>Nominate two memory locations A and B. >>> >>>Init: Set A and B to 0. All client IDs are >=1. >>> >>>for Locking: >>>if(ReadA()!=0) >>> abort; >>>if(ReadB()!=0) >>> abort; >>>WriteA(myID); >>>if(ReadB()!=0) >>> WriteA(0) >>> abort; >>>if(ReadA()!=myID) >>> abort; >>>WriteB(myID); >>>done. >>> >>>I'll try to mold this into VMish code to do actual tests, >> >>but would like >> >>>to ask if there's some well-known clever solution to this that I'm >>>simply >>>not aware of. >>> >>>Please note that the REAL problem is not about IPC or such stuff, I >>>really >>>only have these two operations Read and Write, but an >> >>arbitrary number >> >>>of >>>"registers" to use (think of HTTP GET and PUT). Enumeration >> >>of anything >> >>>is >>>not available. >>> >>>Best regards, >>> >>>Carsten Orthbandt >>>Founder + Development Director >>>SEK SpieleEntwicklungsKombinat GmbH >>>http://www.sek-ost.de >>> >>>Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt >>> >>> >>> >>>------------------------------------------------------- >>>All the advantages of Linux Managed Hosting--Without the >> >>Cost and Risk! >> >>>Fully trained technicians. The highest number of Red Hat >> >>certifications in >> >>>the hosting industry. Fanatical Support. Click to learn more >>> >> >>http://sel.as-us.falkag.net/sel?cmd___________________________ > > ____________________ > >>>GDAlgorithms-list mailing list >>>GDA...@li... >>>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >>>Archives: >>>http://sourceforge.net/mailarchive/forum.php?forum_ida88 >> >> >> >>------------------------------------------------------- >>All the advantages of Linux Managed Hosting--Without the Cost >>and Risk! >>Fully trained technicians. The highest number of Red Hat >>certifications in >>the hosting industry. Fanatical Support. Click to learn more >>http://sel.as-us.falkag.net/sel?cmd=lnk&kid=107521&bid=248729& > > dat=121642 > >>_______________________________________________ >>GDAlgorithms-list mailing list >>GDA...@li... >>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >>Archives: >>http://sourceforge.net/mailarchive/forum.php?forum_id=6188 >> > > > > ------------------------------------------------------- > All the advantages of Linux Managed Hosting--Without the Cost and Risk! > Fully trained technicians. The highest number of Red Hat certifications in > the hosting industry. Fanatical Support. Click to learn more > http://sel.as-us.falkag.net/sel?cmd_______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_ida88 |
From: Bill B. <wb...@gm...> - 2006-05-30 07:58:16
|
The wikipedia article on mutual exclusion lists 3 algorithms (Dekker's, Peterson's and Lamport's): http://en.wikipedia.org/wiki/Mutual_exclusion Peterson's is the one I remember from my first OS class. But it's only for 2 processes. Wikipedia refers to a dead-tree article about how to generalize it, but that method may or may not require knowing N also. Regards, Bill On 5/30/06, Kenneth B. Russell <kbr...@al...> wrote: > > Can you implement the locking operation atomically on the server using > an HTTP PUT or POST on the client? In other words, the client sends a > PUT message containing its GUID and receives a response code indicating > whether the lock operation succeeded. If it did, it is privileged to do > whatever operations it needs to do under the cover of the lock. It would > then later send an unlock message to the server using another PUT with > its GUID. You could handle clients which disconnect in the middle of the > operation using timeouts or a similar mechanism, and perhaps even use a > two-phase commit so that inconsistent states can't be seen by other > clients. > > Does any of this sound plausible? > > -Ken > > > Carsten Orthbandt wrote: > > > Interesting read, but... > > It comes close, but doesn't solve the problem. Dekker's algorithm > > (at least as far as I understand it) and this refinement both require > > me to know the number of clients, which I don't. Since enumeration > > of the address space is also not supported, I can't use a bit field > > with one bit for every client since no client is able to tell the > > actual number of clients to check interest against and in turn doesn't > > know how many bits to check. > > In the mentioned environment (it's only an example) this would need > > directory browsing in addition to HTTP GET and PUT, which is not > > available. > > Another restriction is that my client IDs are unique AND sparse. > > In the final application we're not even talking about integer IDs > > but obviously it will be GUIDs which makes scanning over all possible > > client IDs a no-go (not that it would make much sense with integer > > IDs either). > > I don't care if the locking is "fair" or very efficient, I only need > > a method that works for the (rare but possible) case of a collision. > > > > Thanks, > > > > Carsten Orthbandt > > Founder + Development Director > > SEK SpieleEntwicklungsKombinat GmbH > > http://www.sek-ost.de > > > > Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt > > > > > > > >>-----Original Message----- > >>From: gda...@li... > >>[mailto:gda...@li...] On > >>Behalf Of Kenneth B. Russell > >>Sent: Tuesday, May 30, 2006 8:56 AM > >>To: gda...@li... > >>Subject: Re: [Algorithms] Locking without atomic operations > >> > >>Have you looked into Dekker's algorithm and its generalizations to > >>multiple (more than two) clients? I'm not completely sure the > >>operations > >>you have available cover what is needed to implement it but it sounds > >>like it from a cursory look. The following reference points to other > >>related references which offer fair solutions, meaning you won't run > >>into livelock under heavy contention. This was found with a Google > >>search for "dekker mutual exclusion generalization". > >> > >>http://caltechcstr.library.caltech.edu/359/ > >> > >>-Ken > >> > >> > >>Carsten Orthbandt wrote: > >> > >> > >>>I crawled the web for a solution to this but I only found references > >>>to "mostly" without atomic operations and such stuff. > >>> > >>>Given N integer memory locations and only the operations > >>>value=Read(addr) > >>>and Write(addr,value), I'm looking for a way to syncronize > >> > >>access to a > >> > >>>resource from multiple clients, each with a guaranteed > >> > >>unique integer > >> > >>>id. > >>>The lock attempf should fail if there is already a lock or > >> > >>there's some > >> > >>>sort of collision while obtaining the lock. > >>> > >>>The solution I've come up but have not really verified is this: > >>> > >>>Nominate two memory locations A and B. > >>> > >>>Init: Set A and B to 0. All client IDs are >=1. > >>> > >>>for Locking: > >>>if(ReadA()!=0) > >>> abort; > >>>if(ReadB()!=0) > >>> abort; > >>>WriteA(myID); > >>>if(ReadB()!=0) > >>> WriteA(0) > >>> abort; > >>>if(ReadA()!=myID) > >>> abort; > >>>WriteB(myID); > >>>done. > >>> > >>>I'll try to mold this into VMish code to do actual tests, > >> > >>but would like > >> > >>>to ask if there's some well-known clever solution to this that I'm > >>>simply > >>>not aware of. > >>> > >>>Please note that the REAL problem is not about IPC or such stuff, I > >>>really > >>>only have these two operations Read and Write, but an > >> > >>arbitrary number > >> > >>>of > >>>"registers" to use (think of HTTP GET and PUT). Enumeration > >> > >>of anything > >> > >>>is > >>>not available. > >>> > >>>Best regards, > >>> > >>>Carsten Orthbandt > >>>Founder + Development Director > >>>SEK SpieleEntwicklungsKombinat GmbH > >>>http://www.sek-ost.de > >>> > >>>Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt > >>> > >>> > >>> > >>>------------------------------------------------------- > >>>All the advantages of Linux Managed Hosting--Without the > >> > >>Cost and Risk! > >> > >>>Fully trained technicians. The highest number of Red Hat > >> > >>certifications in > >> > >>>the hosting industry. Fanatical Support. Click to learn more > >>> > >> > >>http://sel.as-us.falkag.net/sel?cmd___________________________ > > > > ____________________ > > > >>>GDAlgorithms-list mailing list > >>>GDA...@li... > >>>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > >>>Archives: > >>>http://sourceforge.net/mailarchive/forum.php?forum_ida88 > >> > >> > >> > >>------------------------------------------------------- > >>All the advantages of Linux Managed Hosting--Without the Cost > >>and Risk! > >>Fully trained technicians. The highest number of Red Hat > >>certifications in > >>the hosting industry. Fanatical Support. Click to learn more > >>http://sel.as-us.falkag.net/sel?cmd=lnk&kid=107521&bid=248729& > > > > dat=121642 > > > >>_______________________________________________ > >>GDAlgorithms-list mailing list > >>GDA...@li... > >>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > >>Archives: > >>http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > >> > > > > > > > > ------------------------------------------------------- > > All the advantages of Linux Managed Hosting--Without the Cost and Risk! > > Fully trained technicians. The highest number of Red Hat certifications > in > > the hosting industry. Fanatical Support. Click to learn more > > > http://sel.as-us.falkag.net/sel?cmd_______________________________________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_ida88 > > > > ------------------------------------------------------- > All the advantages of Linux Managed Hosting--Without the Cost and Risk! > Fully trained technicians. The highest number of Red Hat certifications in > the hosting industry. Fanatical Support. Click to learn more > http://sel.as-us.falkag.net/sel?cmd=lnk&kid=107521&bid=248729&dat=121642 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > -- William V. Baxter III OLM Digital Kono Dens Building Rm 302 1-8-8 Wakabayashi Setagaya-ku Tokyo, Japan 154-0023 +81 (3) 3422-3380 |
From: Simon F. <sim...@po...> - 2006-05-30 07:24:14
|
=20=0D=0AI wrote:=0D=0A>=20=0D=0A> Carsten Orthbandt wrote=0D=0A> >=20=0D=0A= > > Well, I suspected there's some order of execution that breaks.=0D=0A> >= That's why I'm asking for advice ;-)=0D=0A> >=20=0D=0A> I had a quick look= through my old operating systems text book=20=0D=0A> but it only mentions = indivisible operations.=0D=0A>=20=0D=0A> I did have a thought (which probab= ly has a flaw) but perhaps=20=0D=0A> it might give you some ideas.=0D=0A> =0D= =0A> You said each thread had a unique ID=3F If so, would the=20=0D=0A> fol= lowing work.... (I'm assuming that there are no problems=20=0D=0A> with the= processes being on different processes and there=20=0D=0A> being cache pro= blems.)=0D=0A>=20=0D=0A> Initialise "lock" to 0.=0D=0A>=20=0D=0A> BOOL GetL= ock(volatile int lock, int ThreadsUniqueID) {=0D=0A> if(lock)=0D=0A> = {=0D=0A> =09 return FALSE;=0D=0A> }=0D=0A> lock =3D ThreadsUniqu= eID;=0D=0A=0D=0A No this is rubbish.. Ignore it.=0D=0A=0D=0A=0D=0A=0D=0ASim= on=0D=0A=0D=0A******************=0D=0AThis e-mail has been sent from Imagin= ation Technologies Limited.=0D=0APowerVR, Metagence, Ensigma and PURE Digit= al are divisions=0D=0Aof Imagination Technologies Limited.=0D=0A=0D=0AThe i= nformation contained in this e-mail, including any attachment,=0D=0Ais conf= idential and may be legally privileged. It is intended solely=0D=0Afor the= addressee(s) and access to this e-mail by anyone else is=0D=0Aunauthorised= =2E If you are not the intended recipient, any disclosure,=0D=0Acopying or= distribution or use of the information contained in this=20=0D=0Ae-mail, i= s prohibited and may be unlawful. If you have received this=0D=0Ae-mail in= error, please notify the sender by return e-mail and then=0D=0Adelete it f= rom your system.=0D=0A=0D=0AInternet communications cannot be guaranteed to= be secure,=0D=0Aerror or virus-free. The sender does not accept liability= for any errors=0D=0Aor omissions which arise as a result.=0D=0A=0D=0AAny v= iews expressed in this message are those of the author, except=0D=0Awhere t= he author specifies and, with authority, states them to be the=0D=0Aviews o= f Imagination Technologies Limited.=0D=0A |
From: Carsten O. <car...@se...> - 2006-05-30 07:29:30
|
Yeah, that's the easy and solution that doesn't work ;-) The problem is here: 1: if(lock){return FALSE;} 2: lock =3D ThreadsUniqueID; 3: if(lock !=3D ThreadsUniqueID){return FALSE;} 4: return TRUE; lock CA CB 0 1 0 1 0 2 A 3 A 2 B 4 X B 3 B 4 X Both clients come out with TRUE, but only B really has it. =09 Carsten Orthbandt Founder + Development Director SEK SpieleEntwicklungsKombinat GmbH http://www.sek-ost.de Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt =20 > -----Original Message----- > From: gda...@li...=20 > [mailto:gda...@li...] On=20 > Behalf Of Simon Fenney > Sent: Tuesday, May 30, 2006 9:18 AM > To: gda...@li... > Subject: RE: [Algorithms] Locking without atomic operations >=20 > =20 >=20 > Carsten Orthbandt wrote > >=20 > > Well, I suspected there's some order of execution that breaks. > > That's why I'm asking for advice ;-) > >=20 > I had a quick look through my old operating systems text book but it > only mentions indivisible operations. >=20 > I did have a thought (which probably has a flaw) but perhaps it might > give you some ideas. >=20 > You said each thread had a unique ID? If so, would the following > work.... (I'm assuming that there are no problems with the processes > being on different processes and there being cache problems.) >=20 > Initialise "lock" to 0. >=20 > BOOL GetLock(volatile int lock, int ThreadsUniqueID) > { > if(lock) > { > return FALSE; > } > lock =3D ThreadsUniqueID; >=20 > if(lock !=3D ThreadsUniqueID) > { > return FALSE; > } > return TRUE; > } >=20 > It seems to me (but I haven't looked too thoroughly) that even if the > reads and writes are intermixed, exactly one process should=20 > get access. >=20 > Simon >=20 > PS: I know there is a solution for multiprocessors with independent > memory systems involving timestamps etc but that's probably a little > more than you'd need. >=20 >=20 > > =20 > >=20 > > > -----Original Message----- > > > From: gda...@li... > > > [mailto:gda...@li...] On=20 > Behalf Of=20 > > > Joerg Wagner > > > Sent: Tuesday, May 30, 2006 8:27 AM > > > To: gda...@li... > > > Subject: Re: [Algorithms] Locking without atomic operations > > >=20 > > > Mhmmm, what about successive interuptions (or bad interleaving): > > >=20 > > > Thread1: > > > if(ReadA()!=3D0) > > > abort; > > > if(ReadB()!=3D0) > > > abort; > > >=20 > > > Thread2: > > > if(ReadA()!=3D0) > > > abort; > > > if(ReadB()!=3D0) > > > abort; > > >=20 > > > Thread1: > > > WriteA(myID1); > > > if(ReadB()!=3D0) > > > WriteA(0) > > > abort; > > > if(ReadA()!=3DmyID1) > > > abort; > > >=20 > > > Thread2: > > > WriteA(myID2); > > > if(ReadB()!=3D0) > > > WriteA(0) > > > abort; > > > if(ReadA()!=3DmyID2) > > > abort; > > >=20 > > > Thread1: > > > WriteB(myID1); > > > done. > > > Thread2: > > > WriteB(myID2); > > > done. > > >=20 > > > So both have written and aquired the lock :/ > > >=20 > > > Joerg > > >=20 > > >=20 > > >=20 > > > ------------------------------------------------------- > > > All the advantages of Linux Managed Hosting--Without the Cost and=20 > > > Risk! > > > Fully trained technicians. The highest number of Red Hat=20 > > > certifications in the hosting industry. Fanatical=20 > Support. Click to=20 > > > learn more=20 > > > = http://sel.as-us.falkag.net/sel?cmd=3Dlnk&kid=3D107521&bid=3D248729& > > > dat=3D121642 > > > _______________________________________________ > > > GDAlgorithms-list mailing list > > > GDA...@li... > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > Archives: > > > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > >=20 > >=20 > >=20 > > ------------------------------------------------------- > > All the advantages of Linux Managed Hosting--Without the Cost=20 > > and Risk! > > Fully trained technicians. The highest number of Red Hat=20 > > certifications in the hosting industry. Fanatical Support.=20 > > Click to learn more > > = http://sel.as-us.falkag.net/sel?cmd=3Dk&kid=107521&bid$8729&dat=121642 > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_ida88 > >=20 > >=20 >=20 > ****************** > This e-mail has been sent from Imagination Technologies Limited. > PowerVR, Metagence, Ensigma and PURE Digital are divisions > of Imagination Technologies Limited. >=20 > The information contained in this e-mail, including any attachment, > is confidential and may be legally privileged. It is intended solely > for the addressee(s) and access to this e-mail by anyone else is > unauthorised. If you are not the intended recipient, any disclosure, > copying or distribution or use of the information contained in this=20 > e-mail, is prohibited and may be unlawful. If you have received this > e-mail in error, please notify the sender by return e-mail and then > delete it from your system. >=20 > Internet communications cannot be guaranteed to be secure, > error or virus-free. The sender does not accept liability=20 > for any errors > or omissions which arise as a result. >=20 > Any views expressed in this message are those of the author, except > where the author specifies and, with authority, states them to be the > views of Imagination Technologies Limited. >=20 >=20 >=20 > ------------------------------------------------------- > All the advantages of Linux Managed Hosting--Without the Cost=20 > and Risk! > Fully trained technicians. The highest number of Red Hat=20 > certifications in > the hosting industry. Fanatical Support. Click to learn more > http://sel.as-us.falkag.net/sel?cmd=3Dk&kid=107521&bid$8729&dat=121642 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_ida88 >=20 |
From: Carsten O. <car...@se...> - 2006-05-30 07:42:32
|
If I could implement any logic besides READ and WRITE on the server, this problem wouldn't be one ;-) The HTTP PUT/GET was only mentioned as an example, it's not the only protocol. Think about implementing this through all of HTTP, FTP, local files, network shares, System RAM. With the smallest common of all environments, I'm basically left with atomic READ and WRITE, nothing else... There must be some smarter brain out there who already solved this for me ;-) Carsten Orthbandt Founder + Development Director SEK SpieleEntwicklungsKombinat GmbH http://www.sek-ost.de Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt =20 > -----Original Message----- > From: gda...@li...=20 > [mailto:gda...@li...] On=20 > Behalf Of Kenneth B. Russell > Sent: Tuesday, May 30, 2006 9:34 AM > To: gda...@li... > Subject: Re: [Algorithms] Locking without atomic operations >=20 > Can you implement the locking operation atomically on the=20 > server using=20 > an HTTP PUT or POST on the client? In other words, the client sends a=20 > PUT message containing its GUID and receives a response code=20 > indicating=20 > whether the lock operation succeeded. If it did, it is=20 > privileged to do=20 > whatever operations it needs to do under the cover of the=20 > lock. It would=20 > then later send an unlock message to the server using another=20 > PUT with=20 > its GUID. You could handle clients which disconnect in the=20 > middle of the=20 > operation using timeouts or a similar mechanism, and perhaps=20 > even use a=20 > two-phase commit so that inconsistent states can't be seen by=20 > other clients. >=20 > Does any of this sound plausible? >=20 > -Ken >=20 >=20 > Carsten Orthbandt wrote: >=20 > > Interesting read, but... > > It comes close, but doesn't solve the problem. Dekker's algorithm > > (at least as far as I understand it) and this refinement=20 > both require > > me to know the number of clients, which I don't. Since enumeration > > of the address space is also not supported, I can't use a bit field > > with one bit for every client since no client is able to tell the > > actual number of clients to check interest against and in=20 > turn doesn't > > know how many bits to check. > > In the mentioned environment (it's only an example) this would need > > directory browsing in addition to HTTP GET and PUT, which is not > > available. > > Another restriction is that my client IDs are unique AND sparse. > > In the final application we're not even talking about integer IDs > > but obviously it will be GUIDs which makes scanning over=20 > all possible > > client IDs a no-go (not that it would make much sense with integer > > IDs either). > > I don't care if the locking is "fair" or very efficient, I only need > > a method that works for the (rare but possible) case of a collision. > >=20 > > Thanks, > >=20 > > Carsten Orthbandt > > Founder + Development Director > > SEK SpieleEntwicklungsKombinat GmbH > > http://www.sek-ost.de > >=20 > > Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt > > =20 > >=20 > >=20 > >>-----Original Message----- > >>From: gda...@li...=20 > >>[mailto:gda...@li...] On=20 > >>Behalf Of Kenneth B. Russell > >>Sent: Tuesday, May 30, 2006 8:56 AM > >>To: gda...@li... > >>Subject: Re: [Algorithms] Locking without atomic operations > >> > >>Have you looked into Dekker's algorithm and its generalizations to=20 > >>multiple (more than two) clients? I'm not completely sure the=20 > >>operations=20 > >>you have available cover what is needed to implement it but=20 > it sounds=20 > >>like it from a cursory look. The following reference points=20 > to other=20 > >>related references which offer fair solutions, meaning you=20 > won't run=20 > >>into livelock under heavy contention. This was found with a Google=20 > >>search for "dekker mutual exclusion generalization". > >> > >>http://caltechcstr.library.caltech.edu/359/ > >> > >>-Ken > >> > >> > >>Carsten Orthbandt wrote: > >> > >> > >>>I crawled the web for a solution to this but I only found=20 > references > >>>to "mostly" without atomic operations and such stuff. > >>> > >>>Given N integer memory locations and only the operations > >>>value=3DRead(addr) > >>>and Write(addr,value), I'm looking for a way to syncronize=20 > >> > >>access to a > >> > >>>resource from multiple clients, each with a guaranteed=20 > >> > >>unique integer > >> > >>>id. > >>>The lock attempf should fail if there is already a lock or=20 > >> > >>there's some > >> > >>>sort of collision while obtaining the lock. > >>> > >>>The solution I've come up but have not really verified is this: > >>> > >>>Nominate two memory locations A and B. > >>> > >>>Init: Set A and B to 0. All client IDs are >=3D1. > >>> > >>>for Locking: > >>>if(ReadA()!=3D0) > >>> abort; > >>>if(ReadB()!=3D0) > >>> abort; > >>>WriteA(myID); > >>>if(ReadB()!=3D0) > >>> WriteA(0) > >>> abort; > >>>if(ReadA()!=3DmyID) > >>> abort; > >>>WriteB(myID); > >>>done. > >>> > >>>I'll try to mold this into VMish code to do actual tests,=20 > >> > >>but would like > >> > >>>to ask if there's some well-known clever solution to this that I'm > >>>simply > >>>not aware of. > >>> > >>>Please note that the REAL problem is not about IPC or such stuff, I > >>>really > >>>only have these two operations Read and Write, but an=20 > >> > >>arbitrary number > >> > >>>of > >>>"registers" to use (think of HTTP GET and PUT). Enumeration=20 > >> > >>of anything > >> > >>>is > >>>not available. > >>> > >>>Best regards, > >>> > >>>Carsten Orthbandt > >>>Founder + Development Director > >>>SEK SpieleEntwicklungsKombinat GmbH > >>>http://www.sek-ost.de > >>> > >>>Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt > >>>=20 > >>> > >>> > >>>------------------------------------------------------- > >>>All the advantages of Linux Managed Hosting--Without the=20 > >> > >>Cost and Risk! > >> > >>>Fully trained technicians. The highest number of Red Hat=20 > >> > >>certifications in > >> > >>>the hosting industry. Fanatical Support. Click to learn more > >>> > >> > >>http://sel.as-us.falkag.net/sel?cmd___________________________ > >=20 > > ____________________ > >=20 > >>>GDAlgorithms-list mailing list > >>>GDA...@li... > >>>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > >>>Archives: > >>>http://sourceforge.net/mailarchive/forum.php?forum_ida88 > >> > >> > >> > >>------------------------------------------------------- > >>All the advantages of Linux Managed Hosting--Without the Cost=20 > >>and Risk! > >>Fully trained technicians. The highest number of Red Hat=20 > >>certifications in > >>the hosting industry. Fanatical Support. Click to learn more > >>http://sel.as-us.falkag.net/sel?cmd=3Dlnk&kid=3D107521&bid=3D248729& > >=20 > > dat=3D121642 > >=20 > >>_______________________________________________ > >>GDAlgorithms-list mailing list > >>GDA...@li... > >>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > >>Archives: > >>http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > >> > >=20 > >=20 > >=20 > > ------------------------------------------------------- > > All the advantages of Linux Managed Hosting--Without the=20 > Cost and Risk! > > Fully trained technicians. The highest number of Red Hat=20 > certifications in > > the hosting industry. Fanatical Support. Click to learn more > >=20 > http://sel.as-us.falkag.net/sel?cmd___________________________ > ____________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_ida88 >=20 >=20 >=20 > ------------------------------------------------------- > All the advantages of Linux Managed Hosting--Without the Cost=20 > and Risk! > Fully trained technicians. The highest number of Red Hat=20 > certifications in > the hosting industry. Fanatical Support. Click to learn more > http://sel.as-us.falkag.net/sel?cmd=3Dlnk&kid=3D107521&bid=3D248729& > dat=3D121642 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 >=20 |
From: Kenneth B. R. <kbr...@al...> - 2006-05-30 07:56:12
|
Carsten Orthbandt wrote: > If I could implement any logic besides READ and WRITE on > the server, this problem wouldn't be one ;-) > The HTTP PUT/GET was only mentioned as an example, it's > not the only protocol. Think about implementing this through > all of HTTP, FTP, local files, network shares, System RAM. > With the smallest common of all environments, I'm basically > left with atomic READ and WRITE, nothing else... I disagree with this statement. Local files and network shares, for example, support certain kinds of locking, as does system RAM on all processors using atomic operations. One can (should be able to?) build a locking protocol using HTTP PUT operations and a custom HTTP server. I don't know what the FTP protocol looks like but I assume if you can build your own FTP server that you could build a locking protocol where a put operation of a custom file type and contents would cause a success or failure response depending on whether the virtual "lock" succeeded. There's a reason atomic operations exist on the CPU and locking mechanisms exist in file systems; under some situations they are absolutely necessary in order to achieve mutual exclusion. Basically I think you are going to need an atomic lock operation as a primitive, and to figure out how to implement it on top of the protocols you want to support. I would suggest taking two or three of the protocols you want to layer on top of (system RAM, local file systems) and see whether it is feasible to implement it, and then look more deeply into those protocols you want to support which you don't think have the appropriate primitives and see whether in fact they do. I suspect you'll find it's implementable on top of all of the protocols you want to support. -Ken > There must be some smarter brain out there who already solved > this for me ;-) > > Carsten Orthbandt > Founder + Development Director > SEK SpieleEntwicklungsKombinat GmbH > http://www.sek-ost.de > > Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt > > > >>-----Original Message----- >>From: gda...@li... >>[mailto:gda...@li...] On >>Behalf Of Kenneth B. Russell >>Sent: Tuesday, May 30, 2006 9:34 AM >>To: gda...@li... >>Subject: Re: [Algorithms] Locking without atomic operations >> >>Can you implement the locking operation atomically on the >>server using >>an HTTP PUT or POST on the client? In other words, the client sends a >>PUT message containing its GUID and receives a response code >>indicating >>whether the lock operation succeeded. If it did, it is >>privileged to do >>whatever operations it needs to do under the cover of the >>lock. It would >>then later send an unlock message to the server using another >>PUT with >>its GUID. You could handle clients which disconnect in the >>middle of the >>operation using timeouts or a similar mechanism, and perhaps >>even use a >>two-phase commit so that inconsistent states can't be seen by >>other clients. >> >>Does any of this sound plausible? >> >>-Ken >> >> >>Carsten Orthbandt wrote: >> >> >>>Interesting read, but... >>>It comes close, but doesn't solve the problem. Dekker's algorithm >>>(at least as far as I understand it) and this refinement >> >>both require >> >>>me to know the number of clients, which I don't. Since enumeration >>>of the address space is also not supported, I can't use a bit field >>>with one bit for every client since no client is able to tell the >>>actual number of clients to check interest against and in >> >>turn doesn't >> >>>know how many bits to check. >>>In the mentioned environment (it's only an example) this would need >>>directory browsing in addition to HTTP GET and PUT, which is not >>>available. >>>Another restriction is that my client IDs are unique AND sparse. >>>In the final application we're not even talking about integer IDs >>>but obviously it will be GUIDs which makes scanning over >> >>all possible >> >>>client IDs a no-go (not that it would make much sense with integer >>>IDs either). >>>I don't care if the locking is "fair" or very efficient, I only need >>>a method that works for the (rare but possible) case of a collision. >>> >>>Thanks, >>> >>>Carsten Orthbandt >>>Founder + Development Director >>>SEK SpieleEntwicklungsKombinat GmbH >>>http://www.sek-ost.de >>> >>>Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt >>> >>> >>> >>> >>>>-----Original Message----- >>>>From: gda...@li... >>>>[mailto:gda...@li...] On >>>>Behalf Of Kenneth B. Russell >>>>Sent: Tuesday, May 30, 2006 8:56 AM >>>>To: gda...@li... >>>>Subject: Re: [Algorithms] Locking without atomic operations >>>> >>>>Have you looked into Dekker's algorithm and its generalizations to >>>>multiple (more than two) clients? I'm not completely sure the >>>>operations >>>>you have available cover what is needed to implement it but >> >>it sounds >> >>>>like it from a cursory look. The following reference points >> >>to other >> >>>>related references which offer fair solutions, meaning you >> >>won't run >> >>>>into livelock under heavy contention. This was found with a Google >>>>search for "dekker mutual exclusion generalization". >>>> >>>>http://caltechcstr.library.caltech.edu/359/ >>>> >>>>-Ken >>>> >>>> >>>>Carsten Orthbandt wrote: >>>> >>>> >>>> >>>>>I crawled the web for a solution to this but I only found >> >>references >> >>>>>to "mostly" without atomic operations and such stuff. >>>>> >>>>>Given N integer memory locations and only the operations >>>>>value=Read(addr) >>>>>and Write(addr,value), I'm looking for a way to syncronize >>>> >>>>access to a >>>> >>>> >>>>>resource from multiple clients, each with a guaranteed >>>> >>>>unique integer >>>> >>>> >>>>>id. >>>>>The lock attempf should fail if there is already a lock or >>>> >>>>there's some >>>> >>>> >>>>>sort of collision while obtaining the lock. >>>>> >>>>>The solution I've come up but have not really verified is this: >>>>> >>>>>Nominate two memory locations A and B. >>>>> >>>>>Init: Set A and B to 0. All client IDs are >=1. >>>>> >>>>>for Locking: >>>>>if(ReadA()!=0) >>>>> abort; >>>>>if(ReadB()!=0) >>>>> abort; >>>>>WriteA(myID); >>>>>if(ReadB()!=0) >>>>> WriteA(0) >>>>> abort; >>>>>if(ReadA()!=myID) >>>>> abort; >>>>>WriteB(myID); >>>>>done. >>>>> >>>>>I'll try to mold this into VMish code to do actual tests, >>>> >>>>but would like >>>> >>>> >>>>>to ask if there's some well-known clever solution to this that I'm >>>>>simply >>>>>not aware of. >>>>> >>>>>Please note that the REAL problem is not about IPC or such stuff, I >>>>>really >>>>>only have these two operations Read and Write, but an >>>> >>>>arbitrary number >>>> >>>> >>>>>of >>>>>"registers" to use (think of HTTP GET and PUT). Enumeration >>>> >>>>of anything >>>> >>>> >>>>>is >>>>>not available. >>>>> >>>>>Best regards, >>>>> >>>>>Carsten Orthbandt >>>>>Founder + Development Director >>>>>SEK SpieleEntwicklungsKombinat GmbH >>>>>http://www.sek-ost.de >>>>> >>>>>Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt >>>>> >>>>> >>>>> >>>>>------------------------------------------------------- >>>>>All the advantages of Linux Managed Hosting--Without the >>>> >>>>Cost and Risk! >>>> >>>> >>>>>Fully trained technicians. The highest number of Red Hat >>>> >>>>certifications in >>>> >>>> >>>>>the hosting industry. Fanatical Support. Click to learn more >>>>> >>>> >>>>http://sel.as-us.falkag.net/sel?cmd___________________________ >>> >>>____________________ >>> >>> >>>>>GDAlgorithms-list mailing list >>>>>GDA...@li... >>>>>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >>>>>Archives: >>>>>http://sourceforge.net/mailarchive/forum.php?forum_ida88 >>>> >>>> >>>> >>>>------------------------------------------------------- >>>>All the advantages of Linux Managed Hosting--Without the Cost >>>>and Risk! >>>>Fully trained technicians. The highest number of Red Hat >>>>certifications in >>>>the hosting industry. Fanatical Support. Click to learn more >>>>http://sel.as-us.falkag.net/sel?cmd=lnk&kid=107521&bid=248729& >>> >>>dat=121642 >>> >>> >>>>_______________________________________________ >>>>GDAlgorithms-list mailing list >>>>GDA...@li... >>>>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >>>>Archives: >>>>http://sourceforge.net/mailarchive/forum.php?forum_id=6188 >>>> >>> >>> >>> >>>------------------------------------------------------- >>>All the advantages of Linux Managed Hosting--Without the >> >>Cost and Risk! >> >>>Fully trained technicians. The highest number of Red Hat >> >>certifications in >> >>>the hosting industry. Fanatical Support. Click to learn more >>> >> >>http://sel.as-us.falkag.net/sel?cmd___________________________ >>____________________ >> >>>GDAlgorithms-list mailing list >>>GDA...@li... >>>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >>>Archives: >>>http://sourceforge.net/mailarchive/forum.php?forum_ida88 >> >> >> >>------------------------------------------------------- >>All the advantages of Linux Managed Hosting--Without the Cost >>and Risk! >>Fully trained technicians. The highest number of Red Hat >>certifications in >>the hosting industry. Fanatical Support. Click to learn more >>http://sel.as-us.falkag.net/sel?cmd=lnk&kid=107521&bid=248729& >>dat=121642 >>_______________________________________________ >>GDAlgorithms-list mailing list >>GDA...@li... >>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >>Archives: >>http://sourceforge.net/mailarchive/forum.php?forum_id=6188 >> > > > > ------------------------------------------------------- > All the advantages of Linux Managed Hosting--Without the Cost and Risk! > Fully trained technicians. The highest number of Red Hat certifications in > the hosting industry. Fanatical Support. Click to learn more > http://sel.as-us.falkag.net/sel?cmd_______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_ida88 |
From: <Ale...@sc...> - 2006-05-30 08:19:42
|
Out of curiosity, why would you want to try and implement this without the use of atomic operations? Alex Clarke Sony Computer Entertainment Europe http://www.scee.com ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify pos...@sc... This footnote also confirms that this email message has been checked for all known viruses. ********************************************************************** Sony Computer Entertainment Europe |
From: <Ale...@sc...> - 2006-05-30 08:33:32
|
"Basically I need a way to let clients fetch and store arbitrary data on arbitrary media (HTTP server, USB stick, whatever) while ensuring there's always only one client actually writing data (multiple reads are fine, also in concurrency with writes). All the remaining logic can easily be handled through file contents, but I need a central anchor that can be locked for writing." Ah I think I can see why now ;) It sounds to me like you're just going to have to have some sort of atmoic lock at some level. The clients can't do this semeselves (for obvious reasons), but perhaps the server they're connected to can do it for them? (and maybe queue up non-colliding writes too) Alex Clarke Sony Computer Entertainment Europe http://www.scee.com gda...@li... wrote on 30/05/2006 09:20:27: > > Out of curiosity, why would you want to try and implement this > without the use of atomic operations? > > Alex Clarke > Sony Computer Entertainment Europe > http://www.scee.com > > ********************************************************************** > This email and any files transmitted with it are confidential and > intended solely for the use of the individual or entity to whom they > are addressed. If you have received this email in error please > notify pos...@sc... This footnote also confirms that this > email message has been checked for all known viruses. > ********************************************************************** > Sony Computer Entertainment Europe [attachment "attc6zc7.dat" > deleted by Alex Clarke/15GMS/LO/UK/SCEE] |
From: Carsten O. <car...@se...> - 2006-05-30 07:59:29
|
Another attempt, feel free to break it... int lockA=3D0; int lockB=3D0; bool Lock(int id) { /*1*/ if(lockA!=3D0){return false;}; /*2*/ if(lockB!=3D0){return false;}; /*3*/ lockA=3Did; /*4*/ if(lockB!=3D0){return lockA=3D0;false;}; /*5*/ if(lockA!=3Did){return false;}; /*6*/ lockB=3Did; /*7*/ if(lockA!=3Did){lockB=3D0;false;}; /*8*/ if(lockB!=3Did){lockA=3D0;lockB=3D0;return false;}; /*9*/ return true; }; Carsten Orthbandt Founder + Development Director SEK SpieleEntwicklungsKombinat GmbH http://www.sek-ost.de Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt =20 > -----Original Message----- > From: gda...@li...=20 > [mailto:gda...@li...] On=20 > Behalf Of Tom Forsyth > Sent: Tuesday, May 30, 2006 9:29 AM > To: gda...@li... > Subject: RE: [Algorithms] Locking without atomic operations >=20 > Doesn't work: >=20 > > if(lock) > > { > > return FALSE; > > } >=20 > **swap to other thread here, which runs the same function and=20 > returns** >=20 > > lock =3D ThreadsUniqueID; > > etc... >=20 > Now both threads believe they have the lock. >=20 >=20 > I know of lots of reasons this is really hard. But I've never had to > actually implement one of these without some sort of atomic > read-modify-write operation. Sounds annoyingly difficult :-) >=20 >=20 > TomF. >=20 >=20 > > -----Original Message----- > > From: gda...@li...=20 > > [mailto:gda...@li...] On=20 > > Behalf Of Simon Fenney > > Sent: 30 May 2006 00:18 > > To: gda...@li... > > Subject: RE: [Algorithms] Locking without atomic operations > >=20 > >=20 > > =20 > >=20 > > Carsten Orthbandt wrote > > >=20 > > > Well, I suspected there's some order of execution that breaks. > > > That's why I'm asking for advice ;-) > > >=20 > > I had a quick look through my old operating systems text book but it > > only mentions indivisible operations. > >=20 > > I did have a thought (which probably has a flaw) but=20 > perhaps it might > > give you some ideas. > >=20 > > You said each thread had a unique ID? If so, would the following > > work.... (I'm assuming that there are no problems with the processes > > being on different processes and there being cache problems.) > >=20 > > Initialise "lock" to 0. > >=20 > > BOOL GetLock(volatile int lock, int ThreadsUniqueID) > > { > > if(lock) > > { > > return FALSE; > > } > > lock =3D ThreadsUniqueID; > >=20 > > if(lock !=3D ThreadsUniqueID) > > { > > return FALSE; > > } > > return TRUE; > > } > >=20 > > It seems to me (but I haven't looked too thoroughly) that=20 > even if the > > reads and writes are intermixed, exactly one process should=20 > > get access. > >=20 > > Simon > >=20 > > PS: I know there is a solution for multiprocessors with independent > > memory systems involving timestamps etc but that's probably a little > > more than you'd need. > >=20 > >=20 > > > =20 > > >=20 > > > > -----Original Message----- > > > > From: gda...@li... > > > > [mailto:gda...@li...] On=20 > > Behalf Of=20 > > > > Joerg Wagner > > > > Sent: Tuesday, May 30, 2006 8:27 AM > > > > To: gda...@li... > > > > Subject: Re: [Algorithms] Locking without atomic operations > > > >=20 > > > > Mhmmm, what about successive interuptions (or bad interleaving): > > > >=20 > > > > Thread1: > > > > if(ReadA()!=3D0) > > > > abort; > > > > if(ReadB()!=3D0) > > > > abort; > > > >=20 > > > > Thread2: > > > > if(ReadA()!=3D0) > > > > abort; > > > > if(ReadB()!=3D0) > > > > abort; > > > >=20 > > > > Thread1: > > > > WriteA(myID1); > > > > if(ReadB()!=3D0) > > > > WriteA(0) > > > > abort; > > > > if(ReadA()!=3DmyID1) > > > > abort; > > > >=20 > > > > Thread2: > > > > WriteA(myID2); > > > > if(ReadB()!=3D0) > > > > WriteA(0) > > > > abort; > > > > if(ReadA()!=3DmyID2) > > > > abort; > > > >=20 > > > > Thread1: > > > > WriteB(myID1); > > > > done. > > > > Thread2: > > > > WriteB(myID2); > > > > done. > > > >=20 > > > > So both have written and aquired the lock :/ > > > >=20 > > > > Joerg > > > >=20 > > > >=20 > > > >=20 > > > > ------------------------------------------------------- > > > > All the advantages of Linux Managed Hosting--Without=20 > the Cost and=20 > > > > Risk! > > > > Fully trained technicians. The highest number of Red Hat=20 > > > > certifications in the hosting industry. Fanatical=20 > > Support. Click to=20 > > > > learn more=20 > > > > = http://sel.as-us.falkag.net/sel?cmd=3Dlnk&kid=3D107521&bid=3D248729& > > > > dat=3D121642 > > > > _______________________________________________ > > > > GDAlgorithms-list mailing list > > > > GDA...@li... > > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > > Archives: > > > > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > > >=20 > > >=20 > > >=20 > > > ------------------------------------------------------- > > > All the advantages of Linux Managed Hosting--Without the Cost=20 > > > and Risk! > > > Fully trained technicians. The highest number of Red Hat=20 > > > certifications in the hosting industry. Fanatical Support.=20 > > > Click to learn more > > > = http://sel.as-us.falkag.net/sel?cmd=3Dk&kid=107521&bid$8729&dat=121642 > > > _______________________________________________ > > > GDAlgorithms-list mailing list > > > GDA...@li... > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > Archives: > > > http://sourceforge.net/mailarchive/forum.php?forum_ida88 > > >=20 > > >=20 > >=20 > > ****************** > > This e-mail has been sent from Imagination Technologies Limited. > > PowerVR, Metagence, Ensigma and PURE Digital are divisions > > of Imagination Technologies Limited. > >=20 > > The information contained in this e-mail, including any attachment, > > is confidential and may be legally privileged. It is=20 > intended solely > > for the addressee(s) and access to this e-mail by anyone else is > > unauthorised. If you are not the intended recipient, any=20 > disclosure, > > copying or distribution or use of the information contained in this=20 > > e-mail, is prohibited and may be unlawful. If you have=20 > received this > > e-mail in error, please notify the sender by return e-mail and then > > delete it from your system. > >=20 > > Internet communications cannot be guaranteed to be secure, > > error or virus-free. The sender does not accept liability=20 > > for any errors > > or omissions which arise as a result. > >=20 > > Any views expressed in this message are those of the author, except > > where the author specifies and, with authority, states them=20 > to be the > > views of Imagination Technologies Limited. > >=20 > >=20 > >=20 > > ------------------------------------------------------- > > All the advantages of Linux Managed Hosting--Without the Cost=20 > > and Risk! > > Fully trained technicians. The highest number of Red Hat=20 > > certifications in > > the hosting industry. Fanatical Support. Click to learn more > > = http://sel.as-us.falkag.net/sel?cmd=3Dk&kid=107521&bid$8729&dat=121642 > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_ida88 > >=20 >=20 >=20 >=20 > ------------------------------------------------------- > All the advantages of Linux Managed Hosting--Without the Cost=20 > and Risk! > Fully trained technicians. The highest number of Red Hat=20 > certifications in > the hosting industry. Fanatical Support. Click to learn more > http://sel.as-us.falkag.net/sel?cmd=3Dk&kid=107521&bid$8729&dat=121642 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_ida88 >=20 |
From: Philip T. <ph...@za...> - 2006-05-30 09:35:24
|
Carsten Orthbandt wrote on 30/05/2006 08:59: > Another attempt, feel free to break it... It seems to 'work' (i.e. no more than one person gets the lock, though sometimes nobody gets it) if there's only two connections, assuming each numbered statement (like the compare-and-conditionally-set "if(lockB!=0){return lockA=0;false;}") is atomic. But with three, you can get something like: #1 #2 #3 lockA lockB 0 ( ) 0 ( ) 0 ( ) 0 0 | 0 ( ) 0 ( ) 1 ( ) 0 0 | 0 ( ) 1 ( ) 1 ( ) 0 0 | 1 ( ) 1 ( ) 1 ( ) 0 0 | 2 ( ) 1 ( ) 1 ( ) 0 0 | 3 ( ) 1 ( ) 1 ( ) 1 0 | 4 ( ) 1 ( ) 1 ( ) 1 0 | 4 ( ) 1 ( ) 2 ( ) 1 0 | 5 ( ) 1 ( ) 2 ( ) 1 0 | 5 ( ) 1 ( ) 3 ( ) 3 0 | 5 ( ) 1 ( ) 4 ( ) 3 0 | 5 ( ) 1 ( ) 5 ( ) 3 0 | 5 ( ) 2 ( ) 5 ( ) 3 0 | 5 ( ) 2 ( ) 6 ( ) 3 3 | 5 ( ) 2 ( ) 7 ( ) 3 3 | 5 ( ) 3 ( ) 7 ( ) 2 3 | 5 ( ) 3 ( ) 8 ( ) 2 3 | 6 ( ) 3 ( ) 8 ( ) 2 1 | 6 ( ) 3 ( ) 9 (t) 2 1 | 7 (f) 3 ( ) 9 (t) 2 0 | 7 (f) 4 ( ) 9 (t) 2 0 | 7 (f) 5 ( ) 9 (t) 2 0 | 7 (f) 6 ( ) 9 (t) 2 2 | 7 (f) 7 ( ) 9 (t) 2 2 | 7 (f) 8 ( ) 9 (t) 2 2 | 7 (f) 9 (t) 9 (t) 2 2 so now #2 and #3 both have the lock (unless I made a mistake somewhere). About 1 in 3,000 random orderings has that problem. > int lockA=0; > int lockB=0; > > bool Lock(int id) > { > /*1*/ if(lockA!=0){return false;}; > /*2*/ if(lockB!=0){return false;}; > /*3*/ lockA=id; > /*4*/ if(lockB!=0){return lockA=0;false;}; > /*5*/ if(lockA!=id){return false;}; > /*6*/ lockB=id; > /*7*/ if(lockA!=id){lockB=0;false;}; > /*8*/ if(lockB!=id){lockA=0;lockB=0;return false;}; > /*9*/ return true; > }; -- Philip Taylor ph...@za... |
From: Carsten O. <car...@se...> - 2006-05-30 08:07:28
|
"Custom" is the key word here. Anything custom or non-standard will not work. For example in HTTP, directory browsing is usually not enabled on Apache (at least not on anything I have access to). Basically I can't rely on any server logic (apart from having the read and write operations not mangle contents from multiple operations). I tend to disagree that locking ops are available in file systems because they are absolutely needed. They are there (IMHO) for faster operation. But possibly bad contention is a price I'm ready to pay if this gets to work with only R/W access. Best regards, Carsten Orthbandt Founder + Development Director SEK SpieleEntwicklungsKombinat GmbH http://www.sek-ost.de Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt =20 > -----Original Message----- > From: gda...@li...=20 > [mailto:gda...@li...] On=20 > Behalf Of Kenneth B. Russell > Sent: Tuesday, May 30, 2006 9:56 AM > To: gda...@li... > Subject: Re: [Algorithms] Locking without atomic operations >=20 > Carsten Orthbandt wrote: >=20 > > If I could implement any logic besides READ and WRITE on > > the server, this problem wouldn't be one ;-) > > The HTTP PUT/GET was only mentioned as an example, it's > > not the only protocol. Think about implementing this through > > all of HTTP, FTP, local files, network shares, System RAM. > > With the smallest common of all environments, I'm basically > > left with atomic READ and WRITE, nothing else... >=20 > I disagree with this statement. Local files and network shares, for=20 > example, support certain kinds of locking, as does system RAM on all=20 > processors using atomic operations. One can (should be able=20 > to?) build a=20 > locking protocol using HTTP PUT operations and a custom HTTP=20 > server. I=20 > don't know what the FTP protocol looks like but I assume if you can=20 > build your own FTP server that you could build a locking=20 > protocol where=20 > a put operation of a custom file type and contents would=20 > cause a success=20 > or failure response depending on whether the virtual "lock"=20 > succeeded.=20 > There's a reason atomic operations exist on the CPU and locking=20 > mechanisms exist in file systems; under some situations they are=20 > absolutely necessary in order to achieve mutual exclusion. >=20 > Basically I think you are going to need an atomic lock operation as a=20 > primitive, and to figure out how to implement it on top of=20 > the protocols=20 > you want to support. I would suggest taking two or three of the=20 > protocols you want to layer on top of (system RAM, local file=20 > systems)=20 > and see whether it is feasible to implement it, and then look more=20 > deeply into those protocols you want to support which you don't think=20 > have the appropriate primitives and see whether in fact they do. I=20 > suspect you'll find it's implementable on top of all of the protocols=20 > you want to support. >=20 > -Ken >=20 >=20 > > There must be some smarter brain out there who already solved > > this for me ;-) > >=20 > > Carsten Orthbandt > > Founder + Development Director > > SEK SpieleEntwicklungsKombinat GmbH > > http://www.sek-ost.de > >=20 > > Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt > > =20 > >=20 > >=20 > >>-----Original Message----- > >>From: gda...@li...=20 > >>[mailto:gda...@li...] On=20 > >>Behalf Of Kenneth B. Russell > >>Sent: Tuesday, May 30, 2006 9:34 AM > >>To: gda...@li... > >>Subject: Re: [Algorithms] Locking without atomic operations > >> > >>Can you implement the locking operation atomically on the=20 > >>server using=20 > >>an HTTP PUT or POST on the client? In other words, the=20 > client sends a=20 > >>PUT message containing its GUID and receives a response code=20 > >>indicating=20 > >>whether the lock operation succeeded. If it did, it is=20 > >>privileged to do=20 > >>whatever operations it needs to do under the cover of the=20 > >>lock. It would=20 > >>then later send an unlock message to the server using another=20 > >>PUT with=20 > >>its GUID. You could handle clients which disconnect in the=20 > >>middle of the=20 > >>operation using timeouts or a similar mechanism, and perhaps=20 > >>even use a=20 > >>two-phase commit so that inconsistent states can't be seen by=20 > >>other clients. > >> > >>Does any of this sound plausible? > >> > >>-Ken > >> > >> > >>Carsten Orthbandt wrote: > >> > >> > >>>Interesting read, but... > >>>It comes close, but doesn't solve the problem. Dekker's algorithm > >>>(at least as far as I understand it) and this refinement=20 > >> > >>both require > >> > >>>me to know the number of clients, which I don't. Since enumeration > >>>of the address space is also not supported, I can't use a bit field > >>>with one bit for every client since no client is able to tell the > >>>actual number of clients to check interest against and in=20 > >> > >>turn doesn't > >> > >>>know how many bits to check. > >>>In the mentioned environment (it's only an example) this would need > >>>directory browsing in addition to HTTP GET and PUT, which is not > >>>available. > >>>Another restriction is that my client IDs are unique AND sparse. > >>>In the final application we're not even talking about integer IDs > >>>but obviously it will be GUIDs which makes scanning over=20 > >> > >>all possible > >> > >>>client IDs a no-go (not that it would make much sense with integer > >>>IDs either). > >>>I don't care if the locking is "fair" or very efficient, I=20 > only need > >>>a method that works for the (rare but possible) case of a=20 > collision. > >>> > >>>Thanks, > >>> > >>>Carsten Orthbandt > >>>Founder + Development Director > >>>SEK SpieleEntwicklungsKombinat GmbH > >>>http://www.sek-ost.de > >>> > >>>Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt > >>> =20 > >>> > >>> > >>> > >>>>-----Original Message----- > >>>>From: gda...@li...=20 > >>>>[mailto:gda...@li...] On=20 > >>>>Behalf Of Kenneth B. Russell > >>>>Sent: Tuesday, May 30, 2006 8:56 AM > >>>>To: gda...@li... > >>>>Subject: Re: [Algorithms] Locking without atomic operations > >>>> > >>>>Have you looked into Dekker's algorithm and its=20 > generalizations to=20 > >>>>multiple (more than two) clients? I'm not completely sure the=20 > >>>>operations=20 > >>>>you have available cover what is needed to implement it but=20 > >> > >>it sounds=20 > >> > >>>>like it from a cursory look. The following reference points=20 > >> > >>to other=20 > >> > >>>>related references which offer fair solutions, meaning you=20 > >> > >>won't run=20 > >> > >>>>into livelock under heavy contention. This was found with=20 > a Google=20 > >>>>search for "dekker mutual exclusion generalization". > >>>> > >>>>http://caltechcstr.library.caltech.edu/359/ > >>>> > >>>>-Ken > >>>> > >>>> > >>>>Carsten Orthbandt wrote: > >>>> > >>>> > >>>> > >>>>>I crawled the web for a solution to this but I only found=20 > >> > >>references > >> > >>>>>to "mostly" without atomic operations and such stuff. > >>>>> > >>>>>Given N integer memory locations and only the operations > >>>>>value=3DRead(addr) > >>>>>and Write(addr,value), I'm looking for a way to syncronize=20 > >>>> > >>>>access to a > >>>> > >>>> > >>>>>resource from multiple clients, each with a guaranteed=20 > >>>> > >>>>unique integer > >>>> > >>>> > >>>>>id. > >>>>>The lock attempf should fail if there is already a lock or=20 > >>>> > >>>>there's some > >>>> > >>>> > >>>>>sort of collision while obtaining the lock. > >>>>> > >>>>>The solution I've come up but have not really verified is this: > >>>>> > >>>>>Nominate two memory locations A and B. > >>>>> > >>>>>Init: Set A and B to 0. All client IDs are >=3D1. > >>>>> > >>>>>for Locking: > >>>>>if(ReadA()!=3D0) > >>>>> abort; > >>>>>if(ReadB()!=3D0) > >>>>> abort; > >>>>>WriteA(myID); > >>>>>if(ReadB()!=3D0) > >>>>> WriteA(0) > >>>>> abort; > >>>>>if(ReadA()!=3DmyID) > >>>>> abort; > >>>>>WriteB(myID); > >>>>>done. > >>>>> > >>>>>I'll try to mold this into VMish code to do actual tests,=20 > >>>> > >>>>but would like > >>>> > >>>> > >>>>>to ask if there's some well-known clever solution to=20 > this that I'm > >>>>>simply > >>>>>not aware of. > >>>>> > >>>>>Please note that the REAL problem is not about IPC or=20 > such stuff, I > >>>>>really > >>>>>only have these two operations Read and Write, but an=20 > >>>> > >>>>arbitrary number > >>>> > >>>> > >>>>>of > >>>>>"registers" to use (think of HTTP GET and PUT). Enumeration=20 > >>>> > >>>>of anything > >>>> > >>>> > >>>>>is > >>>>>not available. > >>>>> > >>>>>Best regards, > >>>>> > >>>>>Carsten Orthbandt > >>>>>Founder + Development Director > >>>>>SEK SpieleEntwicklungsKombinat GmbH > >>>>>http://www.sek-ost.de > >>>>> > >>>>>Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt > >>>>> > >>>>> > >>>>> > >>>>>------------------------------------------------------- > >>>>>All the advantages of Linux Managed Hosting--Without the=20 > >>>> > >>>>Cost and Risk! > >>>> > >>>> > >>>>>Fully trained technicians. The highest number of Red Hat=20 > >>>> > >>>>certifications in > >>>> > >>>> > >>>>>the hosting industry. Fanatical Support. Click to learn more > >>>>> > >>>> > >>>>http://sel.as-us.falkag.net/sel?cmd___________________________ > >>> > >>>____________________ > >>> > >>> > >>>>>GDAlgorithms-list mailing list > >>>>>GDA...@li... > >>>>>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > >>>>>Archives: > >>>>>http://sourceforge.net/mailarchive/forum.php?forum_ida88 > >>>> > >>>> > >>>> > >>>>------------------------------------------------------- > >>>>All the advantages of Linux Managed Hosting--Without the Cost=20 > >>>>and Risk! > >>>>Fully trained technicians. The highest number of Red Hat=20 > >>>>certifications in > >>>>the hosting industry. Fanatical Support. Click to learn more > = >>>>http://sel.as-us.falkag.net/sel?cmd=3Dlnk&kid=3D107521&bid=3D248729& > >>> > >>>dat=3D121642 > >>> > >>> > >>>>_______________________________________________ > >>>>GDAlgorithms-list mailing list > >>>>GDA...@li... > >>>>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > >>>>Archives: > >>>>http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > >>>> > >>> > >>> > >>> > >>>------------------------------------------------------- > >>>All the advantages of Linux Managed Hosting--Without the=20 > >> > >>Cost and Risk! > >> > >>>Fully trained technicians. The highest number of Red Hat=20 > >> > >>certifications in > >> > >>>the hosting industry. Fanatical Support. Click to learn more > >>> > >> > >>http://sel.as-us.falkag.net/sel?cmd___________________________ > >>____________________ > >> > >>>GDAlgorithms-list mailing list > >>>GDA...@li... > >>>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > >>>Archives: > >>>http://sourceforge.net/mailarchive/forum.php?forum_ida88 > >> > >> > >> > >>------------------------------------------------------- > >>All the advantages of Linux Managed Hosting--Without the Cost=20 > >>and Risk! > >>Fully trained technicians. The highest number of Red Hat=20 > >>certifications in > >>the hosting industry. Fanatical Support. Click to learn more > >>http://sel.as-us.falkag.net/sel?cmd=3Dlnk&kid=3D107521&bid=3D248729& > >>dat=3D121642 > >>_______________________________________________ > >>GDAlgorithms-list mailing list > >>GDA...@li... > >>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > >>Archives: > >>http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > >> > >=20 > >=20 > >=20 > > ------------------------------------------------------- > > All the advantages of Linux Managed Hosting--Without the=20 > Cost and Risk! > > Fully trained technicians. The highest number of Red Hat=20 > certifications in > > the hosting industry. Fanatical Support. Click to learn more > >=20 > http://sel.as-us.falkag.net/sel?cmd___________________________ > ____________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_ida88 >=20 >=20 >=20 > ------------------------------------------------------- > All the advantages of Linux Managed Hosting--Without the Cost=20 > and Risk! > Fully trained technicians. The highest number of Red Hat=20 > certifications in > the hosting industry. Fanatical Support. Click to learn more > http://sel.as-us.falkag.net/sel?cmd=3Dlnk&kid=3D107521&bid=3D248729& > dat=3D121642 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 >=20 |
From: Simon F. <sim...@po...> - 2006-05-30 08:09:55
|
Carsten,=0D=0A Are you trying to do something on a single CPU or are you ma= naging=0D=0Amultiple CPUs in a network=3F If it's the latter (and this is s= tretching=0D=0Amy memory back ~20 years) why not search for papers with key= words=20=0D=0A=0D=0A "timestamps" "Transactions" and possibly "distribut= ed databases".=0D=0A=0D=0AIt might be what you are looking for.=0D=0A=0D=0A= Simon=0D=0A=0D=0A> -----Original Message-----=0D=0A> From: gdalgorithms-lis= t-...@li...=20=0D=0A> [mailto:gdalgorithms-list-admin@lis= ts.sourceforge.net] On=20=0D=0A> Behalf Of Carsten Orthbandt=0D=0A> Sent: 3= 0 May 2006 08:43=0D=0A> To: gda...@li...=0D=0A> = Subject: RE: [Algorithms] Locking without atomic operations=0D=0A>=20=0D=0A= > If I could implement any logic besides READ and WRITE on the=20=0D=0A> se= rver, this problem wouldn't be one ;-) The HTTP PUT/GET was=20=0D=0A> only = mentioned as an example, it's not the only protocol.=20=0D=0A> Think about = implementing this through all of HTTP, FTP, local=20=0D=0A> files, network = shares, System RAM.=0D=0A> With the smallest common of all environments, I'= m basically=20=0D=0A> left with atomic READ and WRITE, nothing else...=0D=0A= > There must be some smarter brain out there who already solved=20=0D=0A> t= his for me ;-)=0D=0A>=20=0D=0A> Carsten Orthbandt=0D=0A> Founder + Developm= ent Director=0D=0A> SEK SpieleEntwicklungsKombinat GmbH=0D=0A> http://www.s= ek-ost.de=0D=0A>=20=0D=0A> Wenn ich Visionen habe, gehe ich zum Arzt. - Hel= mut Schmidt=0D=0A> =20=0D=0A>=20=0D=0A> > -----Original Message-----=0D=0A= > > From: gda...@li...=0D=0A> > [mailto:gd= alg...@li...] On Behalf Of=20=0D=0A> > Kenne= th B. Russell=0D=0A> > Sent: Tuesday, May 30, 2006 9:34 AM=0D=0A> > To: gda= lgo...@li...=0D=0A> > Subject: Re: [Algorithms] Loc= king without atomic operations=0D=0A> >=20=0D=0A> > Can you implement the l= ocking operation atomically on the=20=0D=0A> server using=20=0D=0A> > an HT= TP PUT or POST on the client=3F In other words, the=20=0D=0A> client sends = a=20=0D=0A> > PUT message containing its GUID and receives a response code =0D= =0A> > indicating whether the lock operation succeeded. If it did, it is =0D= =0A> > privileged to do whatever operations it needs to do under=20=0D=0A> = the cover of=20=0D=0A> > the lock. It would then later send an unlock messa= ge to the server=20=0D=0A> > using another PUT with its GUID. You could han= dle clients which=20=0D=0A> > disconnect in the middle of the operation usi= ng timeouts or=20=0D=0A> a similar=20=0D=0A> > mechanism, and perhaps even = use a two-phase commit so that=20=0D=0A> > inconsistent states can't be see= n by other clients.=0D=0A> >=20=0D=0A> > Does any of this sound plausible=3F=0D= =0A> >=20=0D=0A> > -Ken=0D=0A> >=20=0D=0A> >=20=0D=0A> > Carsten Orthbandt = wrote:=0D=0A> >=20=0D=0A> > > Interesting read, but...=0D=0A> > > It comes = close, but doesn't solve the problem. Dekker's algorithm=20=0D=0A> > > (at = least as far as I understand it) and this refinement=0D=0A> > both require=0D= =0A> > > me to know the number of clients, which I don't. Since=20=0D=0A> e= numeration=20=0D=0A> > > of the address space is also not supported, I can'= t use a=20=0D=0A> bit field=20=0D=0A> > > with one bit for every client sin= ce no client is able to tell the=20=0D=0A> > > actual number of clients to = check interest against and in=0D=0A> > turn doesn't=0D=0A> > > know how man= y bits to check.=0D=0A> > > In the mentioned environment (it's only an exam= ple) this=20=0D=0A> would need=20=0D=0A> > > directory browsing in addition= to HTTP GET and PUT, which is not=20=0D=0A> > > available.=0D=0A> > > Anot= her restriction is that my client IDs are unique AND sparse.=0D=0A> > > In = the final application we're not even talking about integer IDs=20=0D=0A> > = > but obviously it will be GUIDs which makes scanning over=0D=0A> > all pos= sible=0D=0A> > > client IDs a no-go (not that it would make much sense=20=0D= =0A> with integer=20=0D=0A> > > IDs either).=0D=0A> > > I don't care if the= locking is "fair" or very efficient,=20=0D=0A> I only need=20=0D=0A> > > a= method that works for the (rare but possible) case of a=20=0D=0A> collisio= n.=0D=0A> > >=20=0D=0A> > > Thanks,=0D=0A> > >=20=0D=0A> > > Carsten Orthba= ndt=0D=0A> > > Founder + Development Director=0D=0A> > > SEK SpieleEntwickl= ungsKombinat GmbH=0D=0A> > > http://www.sek-ost.de=0D=0A> > >=20=0D=0A> > >= Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt=0D=0A> > > =0D= =0A> > >=20=0D=0A> > >=20=0D=0A> > >>-----Original Message-----=0D=0A> > >>= From: gda...@li...=0D=0A> > >>[mailto:gdal= gor...@li...] On=20=0D=0A> Behalf Of=20=0D=0A>= > >>Kenneth B. Russell=0D=0A> > >>Sent: Tuesday, May 30, 2006 8:56 AM=0D=0A= > > >>To: gda...@li...=0D=0A> > >>Subject: Re: [= Algorithms] Locking without atomic operations=0D=0A> > >>=0D=0A> > >>Have y= ou looked into Dekker's algorithm and its=20=0D=0A> generalizations to=20=0D= =0A> > >>multiple (more than two) clients=3F I'm not completely sure the =0D= =0A> > >>operations you have available cover what is needed to=20=0D=0A> im= plement it=20=0D=0A> > >>but=0D=0A> > it sounds=0D=0A> > >>like it from a c= ursory look. The following reference points=0D=0A> > to other=0D=0A> > >>re= lated references which offer fair solutions, meaning you=0D=0A> > won't run=0D= =0A> > >>into livelock under heavy contention. This was found with=20=0D=0A= > a Google=20=0D=0A> > >>search for "dekker mutual exclusion generalization= ".=0D=0A> > >>=0D=0A> > >>http://caltechcstr.library.caltech.edu/359/=0D=0A= > > >>=0D=0A> > >>-Ken=0D=0A> > >>=0D=0A> > >>=0D=0A> > >>Carsten Orthbandt= wrote:=0D=0A> > >>=0D=0A> > >>=0D=0A> > >>>I crawled the web for a solutio= n to this but I only found=0D=0A> > references=0D=0A> > >>>to "mostly" with= out atomic operations and such stuff.=0D=0A> > >>>=0D=0A> > >>>Given N inte= ger memory locations and only the operations=0D=0A> > >>>value=3DRead(addr)=0D= =0A> > >>>and Write(addr,value), I'm looking for a way to syncronize=0D=0A>= > >>=0D=0A> > >>access to a=0D=0A> > >>=0D=0A> > >>>resource from multiple= clients, each with a guaranteed=0D=0A> > >>=0D=0A> > >>unique integer=0D=0A= > > >>=0D=0A> > >>>id.=0D=0A> > >>>The lock attempf should fail if there is= already a lock or=0D=0A> > >>=0D=0A> > >>there's some=0D=0A> > >>=0D=0A> >= >>>sort of collision while obtaining the lock.=0D=0A> > >>>=0D=0A> > >>>Th= e solution I've come up but have not really verified is this:=0D=0A> > >>>=0D= =0A> > >>>Nominate two memory locations A and B.=0D=0A> > >>>=0D=0A> > >>>I= nit: Set A and B to 0. All client IDs are >=3D1.=0D=0A> > >>>=0D=0A> > >>>f= or Locking:=0D=0A> > >>>if(ReadA()!=3D0)=0D=0A> > >>>=09abort;=0D=0A> > >>>= if(ReadB()!=3D0)=0D=0A> > >>>=09abort;=0D=0A> > >>>WriteA(myID);=0D=0A> > >= >>if(ReadB()!=3D0)=0D=0A> > >>>=09WriteA(0)=0D=0A> > >>>=09abort;=0D=0A> > = >>>if(ReadA()!=3DmyID)=0D=0A> > >>>=09abort;=0D=0A> > >>>WriteB(myID);=0D=0A= > > >>>done.=0D=0A> > >>>=0D=0A> > >>>I'll try to mold this into VMish code= to do actual tests,=0D=0A> > >>=0D=0A> > >>but would like=0D=0A> > >>=0D=0A= > > >>>to ask if there's some well-known clever solution to=20=0D=0A> this = that I'm=20=0D=0A> > >>>simply not aware of.=0D=0A> > >>>=0D=0A> > >>>Pleas= e note that the REAL problem is not about IPC or=20=0D=0A> such stuff, I =0D= =0A> > >>>really only have these two operations Read and Write, but an=0D=0A= > > >>=0D=0A> > >>arbitrary number=0D=0A> > >>=0D=0A> > >>>of=0D=0A> > >>>"= registers" to use (think of HTTP GET and PUT). Enumeration=0D=0A> > >>=0D=0A= > > >>of anything=0D=0A> > >>=0D=0A> > >>>is=0D=0A> > >>>not available.=0D=0A= > > >>>=0D=0A> > >>>Best regards,=0D=0A> > >>>=0D=0A> > >>>Carsten Orthband= t=0D=0A> > >>>Founder + Development Director=0D=0A> > >>>SEK SpieleEntwickl= ungsKombinat GmbH http://www.sek-ost.de=0D=0A> > >>>=0D=0A> > >>>Wenn ich V= isionen habe, gehe ich zum Arzt. - Helmut Schmidt=0D=0A> > >>>=20=0D=0A> > = >>>=0D=0A> > >>>=0D=0A> > >>>----------------------------------------------= ---------=0D=0A> > >>>All the advantages of Linux Managed Hosting--Without = the=0D=0A> > >>=0D=0A> > >>Cost and Risk!=0D=0A> > >>=0D=0A> > >>>Fully tra= ined technicians. The highest number of Red Hat=0D=0A> > >>=0D=0A> > >>cert= ifications in=0D=0A> > >>=0D=0A> > >>>the hosting industry. Fanatical Suppo= rt. Click to learn more=0D=0A> > >>>=0D=0A> > >>=0D=0A> > >>http://sel.as-u= s.falkag.net/sel=3Fcmd___________________________=0D=0A> > >=20=0D=0A> > > = ____________________=0D=0A> > >=20=0D=0A> > >>>GDAlgorithms-list mailing li= st=0D=0A> > >>>GDA...@li...=0D=0A> > >>>https://= lists.sourceforge.net/lists/listinfo/gdalgorithms-list=0D=0A> > >>>Archives= :=0D=0A> > >>>http://sourceforge.net/mailarchive/forum.php=3Fforum_ida88=0D= =0A> > >>=0D=0A> > >>=0D=0A> > >>=0D=0A> > >>------------------------------= -------------------------=0D=0A> > >>All the advantages of Linux Managed Ho= sting--Without the Cost and=20=0D=0A> > >>Risk!=0D=0A> > >>Fully trained te= chnicians. The highest number of Red Hat=20=0D=0A> > >>certifications in th= e hosting industry. Fanatical=20=0D=0A> Support. Click to=20=0D=0A> > >>lea= rn more=20=0D=0A> > >>http://sel.as-us.falkag.net/sel=3Fcmd=3Dlnk&kid=3D107= 521&bid=3D248729&=0D=0A> > >=20=0D=0A> > > dat=3D121642=0D=0A> > >=20=0D=0A= > > >>_______________________________________________=0D=0A> > >>GDAlgorith= ms-list mailing list=0D=0A> > >>GDA...@li...=0D=0A= > > >>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list=0D=0A>= > >>Archives:=0D=0A> > >>http://sourceforge.net/mailarchive/forum.php=3Ffo= rum_id=3D6188=0D=0A> > >>=0D=0A> > >=20=0D=0A> > >=20=0D=0A> > >=20=0D=0A> = > > -------------------------------------------------------=0D=0A> > > All = the advantages of Linux Managed Hosting--Without the=0D=0A> > Cost and Risk= !=0D=0A> > > Fully trained technicians. The highest number of Red Hat=0D=0A= > > certifications in=0D=0A> > > the hosting industry. Fanatical Support. C= lick to learn more=0D=0A> > >=20=0D=0A> > http://sel.as-us.falkag.net/sel=3F= cmd___________________________=0D=0A> > ____________________=0D=0A> > > GDA= lgorithms-list mailing list=0D=0A> > > GDA...@li...urceforge.= net=0D=0A> > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-li= st=0D=0A> > > Archives:=0D=0A> > > http://sourceforge.net/mailarchive/forum= =2Ephp=3Fforum_ida88=0D=0A> >=20=0D=0A> >=20=0D=0A> >=20=0D=0A> > ---------= ----------------------------------------------=0D=0A> > All the advantages = of Linux Managed Hosting--Without the Cost and=20=0D=0A> > Risk!=0D=0A> > F= ully trained technicians. The highest number of Red Hat=20=0D=0A> > certifi= cations in the hosting industry. Fanatical Support. Click to=20=0D=0A> > le= arn more=20=0D=0A> > http://sel.as-us.falkag.net/sel=3Fcmd=3Dlnk&kid=3D1075= 21&bid=3D248729&=0D=0A> > dat=3D121642=0D=0A> > ___________________________= ____________________=0D=0A> > GDAlgorithms-list mailing list=0D=0A> > GDAlg= ori...@li...=0D=0A> > https://lists.sourceforge.net/l= ists/listinfo/gdalgorithms-list=0D=0A> > Archives:=0D=0A> > http://sourcefo= rge.net/mailarchive/forum.php=3Fforum_id=3D6188=0D=0A> >=20=0D=0A>=20=0D=0A= >=20=0D=0A> -------------------------------------------------------=0D=0A> = All the advantages of Linux Managed Hosting--Without the Cost=20=0D=0A> and= Risk!=0D=0A> Fully trained technicians. The highest number of Red Hat=20=0D= =0A> certifications in the hosting industry. Fanatical Support.=20=0D=0A> C= lick to learn more=0D=0A> http://sel.as-us.falkag.net/sel=3Fcmd=3Dk&kid=107= 521&bid$8729&dat=121642=0D=0A> ____________________________________________= ___=0D=0A> GDAlgorithms-list mailing list=0D=0A> GDA...@li...= urceforge.net=0D=0A> https://lists.sourceforge.net/lists/listinfo/gdalgorit= hms-list=0D=0A> Archives:=0D=0A> http://sourceforge.net/mailarchive/forum.p= hp=3Fforum_ida88=0D=0A>=20=0D=0A>=20=0D=0A=0D=0A******************=0D=0AThi= s e-mail has been sent from Imagination Technologies Limited.=0D=0APowerVR,= Metagence, Ensigma and PURE Digital are divisions=0D=0Aof Imagination Tech= nologies Limited.=0D=0A=0D=0AThe information contained in this e-mail, incl= uding any attachment,=0D=0Ais confidential and may be legally privileged. = It is intended solely=0D=0Afor the addressee(s) and access to this e-mail b= y anyone else is=0D=0Aunauthorised. If you are not the intended recipient,= any disclosure,=0D=0Acopying or distribution or use of the information con= tained in this=20=0D=0Ae-mail, is prohibited and may be unlawful. If you h= ave received this=0D=0Ae-mail in error, please notify the sender by return = e-mail and then=0D=0Adelete it from your system.=0D=0A=0D=0AInternet commun= ications cannot be guaranteed to be secure,=0D=0Aerror or virus-free. The = sender does not accept liability for any errors=0D=0Aor omissions which ari= se as a result.=0D=0A=0D=0AAny views expressed in this message are those of= the author, except=0D=0Awhere the author specifies and, with authority, st= ates them to be the=0D=0Aviews of Imagination Technologies Limited.=0D=0A |
From: Carsten O. <car...@se...> - 2006-05-30 08:18:41
|
This is sort-of about distributed databases. Timestamps won't work since the clients don't know each other and are not syncronized. The server doesn't perform any logic and can't be customized. I looked into transactions a lot and all I found needs some semaphore handling in a central place. Basically I need a way to let clients fetch and store arbitrary data on arbitrary media (HTTP server, USB stick, whatever) while ensuring there's always only one client actually writing data (multiple reads are fine, also in concurrency with writes). All the remaining logic can easily be handled through file contents, but I need a central anchor that can be locked for writing. Carsten Orthbandt Founder + Development Director SEK SpieleEntwicklungsKombinat GmbH http://www.sek-ost.de Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt =20 > -----Original Message----- > From: gda...@li...=20 > [mailto:gda...@li...] On=20 > Behalf Of Simon Fenney > Sent: Tuesday, May 30, 2006 10:10 AM > To: gda...@li... > Subject: RE: [Algorithms] Locking without atomic operations >=20 > Carsten, > Are you trying to do something on a single CPU or are you managing > multiple CPUs in a network? If it's the latter (and this is stretching > my memory back ~20 years) why not search for papers with keywords=20 >=20 > "timestamps" "Transactions" and possibly "distributed databases". >=20 > It might be what you are looking for. >=20 > Simon >=20 > > -----Original Message----- > > From: gda...@li...=20 > > [mailto:gda...@li...] On=20 > > Behalf Of Carsten Orthbandt > > Sent: 30 May 2006 08:43 > > To: gda...@li... > > Subject: RE: [Algorithms] Locking without atomic operations > >=20 > > If I could implement any logic besides READ and WRITE on the=20 > > server, this problem wouldn't be one ;-) The HTTP PUT/GET was=20 > > only mentioned as an example, it's not the only protocol.=20 > > Think about implementing this through all of HTTP, FTP, local=20 > > files, network shares, System RAM. > > With the smallest common of all environments, I'm basically=20 > > left with atomic READ and WRITE, nothing else... > > There must be some smarter brain out there who already solved=20 > > this for me ;-) > >=20 > > Carsten Orthbandt > > Founder + Development Director > > SEK SpieleEntwicklungsKombinat GmbH > > http://www.sek-ost.de > >=20 > > Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt > > =20 > >=20 > > > -----Original Message----- > > > From: gda...@li... > > > [mailto:gda...@li...] On=20 > Behalf Of=20 > > > Kenneth B. Russell > > > Sent: Tuesday, May 30, 2006 9:34 AM > > > To: gda...@li... > > > Subject: Re: [Algorithms] Locking without atomic operations > > >=20 > > > Can you implement the locking operation atomically on the=20 > > server using=20 > > > an HTTP PUT or POST on the client? In other words, the=20 > > client sends a=20 > > > PUT message containing its GUID and receives a response code=20 > > > indicating whether the lock operation succeeded. If it did, it is=20 > > > privileged to do whatever operations it needs to do under=20 > > the cover of=20 > > > the lock. It would then later send an unlock message to=20 > the server=20 > > > using another PUT with its GUID. You could handle clients which=20 > > > disconnect in the middle of the operation using timeouts or=20 > > a similar=20 > > > mechanism, and perhaps even use a two-phase commit so that=20 > > > inconsistent states can't be seen by other clients. > > >=20 > > > Does any of this sound plausible? > > >=20 > > > -Ken > > >=20 > > >=20 > > > Carsten Orthbandt wrote: > > >=20 > > > > Interesting read, but... > > > > It comes close, but doesn't solve the problem. Dekker's=20 > algorithm=20 > > > > (at least as far as I understand it) and this refinement > > > both require > > > > me to know the number of clients, which I don't. Since=20 > > enumeration=20 > > > > of the address space is also not supported, I can't use a=20 > > bit field=20 > > > > with one bit for every client since no client is able=20 > to tell the=20 > > > > actual number of clients to check interest against and in > > > turn doesn't > > > > know how many bits to check. > > > > In the mentioned environment (it's only an example) this=20 > > would need=20 > > > > directory browsing in addition to HTTP GET and PUT,=20 > which is not=20 > > > > available. > > > > Another restriction is that my client IDs are unique AND sparse. > > > > In the final application we're not even talking about=20 > integer IDs=20 > > > > but obviously it will be GUIDs which makes scanning over > > > all possible > > > > client IDs a no-go (not that it would make much sense=20 > > with integer=20 > > > > IDs either). > > > > I don't care if the locking is "fair" or very efficient,=20 > > I only need=20 > > > > a method that works for the (rare but possible) case of a=20 > > collision. > > > >=20 > > > > Thanks, > > > >=20 > > > > Carsten Orthbandt > > > > Founder + Development Director > > > > SEK SpieleEntwicklungsKombinat GmbH > > > > http://www.sek-ost.de > > > >=20 > > > > Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt > > > > =20 > > > >=20 > > > >=20 > > > >>-----Original Message----- > > > >>From: gda...@li... > > > >>[mailto:gda...@li...] On=20 > > Behalf Of=20 > > > >>Kenneth B. Russell > > > >>Sent: Tuesday, May 30, 2006 8:56 AM > > > >>To: gda...@li... > > > >>Subject: Re: [Algorithms] Locking without atomic operations > > > >> > > > >>Have you looked into Dekker's algorithm and its=20 > > generalizations to=20 > > > >>multiple (more than two) clients? I'm not completely sure the=20 > > > >>operations you have available cover what is needed to=20 > > implement it=20 > > > >>but > > > it sounds > > > >>like it from a cursory look. The following reference points > > > to other > > > >>related references which offer fair solutions, meaning you > > > won't run > > > >>into livelock under heavy contention. This was found with=20 > > a Google=20 > > > >>search for "dekker mutual exclusion generalization". > > > >> > > > >>http://caltechcstr.library.caltech.edu/359/ > > > >> > > > >>-Ken > > > >> > > > >> > > > >>Carsten Orthbandt wrote: > > > >> > > > >> > > > >>>I crawled the web for a solution to this but I only found > > > references > > > >>>to "mostly" without atomic operations and such stuff. > > > >>> > > > >>>Given N integer memory locations and only the operations > > > >>>value=3DRead(addr) > > > >>>and Write(addr,value), I'm looking for a way to syncronize > > > >> > > > >>access to a > > > >> > > > >>>resource from multiple clients, each with a guaranteed > > > >> > > > >>unique integer > > > >> > > > >>>id. > > > >>>The lock attempf should fail if there is already a lock or > > > >> > > > >>there's some > > > >> > > > >>>sort of collision while obtaining the lock. > > > >>> > > > >>>The solution I've come up but have not really verified is this: > > > >>> > > > >>>Nominate two memory locations A and B. > > > >>> > > > >>>Init: Set A and B to 0. All client IDs are >=3D1. > > > >>> > > > >>>for Locking: > > > >>>if(ReadA()!=3D0) > > > >>> abort; > > > >>>if(ReadB()!=3D0) > > > >>> abort; > > > >>>WriteA(myID); > > > >>>if(ReadB()!=3D0) > > > >>> WriteA(0) > > > >>> abort; > > > >>>if(ReadA()!=3DmyID) > > > >>> abort; > > > >>>WriteB(myID); > > > >>>done. > > > >>> > > > >>>I'll try to mold this into VMish code to do actual tests, > > > >> > > > >>but would like > > > >> > > > >>>to ask if there's some well-known clever solution to=20 > > this that I'm=20 > > > >>>simply not aware of. > > > >>> > > > >>>Please note that the REAL problem is not about IPC or=20 > > such stuff, I=20 > > > >>>really only have these two operations Read and Write, but an > > > >> > > > >>arbitrary number > > > >> > > > >>>of > > > >>>"registers" to use (think of HTTP GET and PUT). Enumeration > > > >> > > > >>of anything > > > >> > > > >>>is > > > >>>not available. > > > >>> > > > >>>Best regards, > > > >>> > > > >>>Carsten Orthbandt > > > >>>Founder + Development Director > > > >>>SEK SpieleEntwicklungsKombinat GmbH http://www.sek-ost.de > > > >>> > > > >>>Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt > > > >>>=20 > > > >>> > > > >>> > > > >>>------------------------------------------------------- > > > >>>All the advantages of Linux Managed Hosting--Without the > > > >> > > > >>Cost and Risk! > > > >> > > > >>>Fully trained technicians. The highest number of Red Hat > > > >> > > > >>certifications in > > > >> > > > >>>the hosting industry. Fanatical Support. Click to learn more > > > >>> > > > >> > > > >>http://sel.as-us.falkag.net/sel?cmd___________________________ > > > >=20 > > > > ____________________ > > > >=20 > > > >>>GDAlgorithms-list mailing list > > > >>>GDA...@li... > > > >>>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > >>>Archives: > > > >>>http://sourceforge.net/mailarchive/forum.php?forum_ida88 > > > >> > > > >> > > > >> > > > >>------------------------------------------------------- > > > >>All the advantages of Linux Managed Hosting--Without=20 > the Cost and=20 > > > >>Risk! > > > >>Fully trained technicians. The highest number of Red Hat=20 > > > >>certifications in the hosting industry. Fanatical=20 > > Support. Click to=20 > > > >>learn more=20 > > > = >>http://sel.as-us.falkag.net/sel?cmd=3Dlnk&kid=3D107521&bid=3D248729& > > > >=20 > > > > dat=3D121642 > > > >=20 > > > >>_______________________________________________ > > > >>GDAlgorithms-list mailing list > > > >>GDA...@li... > > > >>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > >>Archives: > > > >>http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > > >> > > > >=20 > > > >=20 > > > >=20 > > > > ------------------------------------------------------- > > > > All the advantages of Linux Managed Hosting--Without the > > > Cost and Risk! > > > > Fully trained technicians. The highest number of Red Hat > > > certifications in > > > > the hosting industry. Fanatical Support. Click to learn more > > > >=20 > > > http://sel.as-us.falkag.net/sel?cmd___________________________ > > > ____________________ > > > > GDAlgorithms-list mailing list > > > > GDA...@li... > > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > > Archives: > > > > http://sourceforge.net/mailarchive/forum.php?forum_ida88 > > >=20 > > >=20 > > >=20 > > > ------------------------------------------------------- > > > All the advantages of Linux Managed Hosting--Without the Cost and=20 > > > Risk! > > > Fully trained technicians. The highest number of Red Hat=20 > > > certifications in the hosting industry. Fanatical=20 > Support. Click to=20 > > > learn more=20 > > > = http://sel.as-us.falkag.net/sel?cmd=3Dlnk&kid=3D107521&bid=3D248729& > > > dat=3D121642 > > > _______________________________________________ > > > GDAlgorithms-list mailing list > > > GDA...@li... > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > Archives: > > > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > >=20 > >=20 > >=20 > > ------------------------------------------------------- > > All the advantages of Linux Managed Hosting--Without the Cost=20 > > and Risk! > > Fully trained technicians. The highest number of Red Hat=20 > > certifications in the hosting industry. Fanatical Support.=20 > > Click to learn more > > = http://sel.as-us.falkag.net/sel?cmd=3Dk&kid=107521&bid$8729&dat=121642 > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_ida88 > >=20 > >=20 >=20 > ****************** > This e-mail has been sent from Imagination Technologies Limited. > PowerVR, Metagence, Ensigma and PURE Digital are divisions > of Imagination Technologies Limited. >=20 > The information contained in this e-mail, including any attachment, > is confidential and may be legally privileged. It is intended solely > for the addressee(s) and access to this e-mail by anyone else is > unauthorised. If you are not the intended recipient, any disclosure, > copying or distribution or use of the information contained in this=20 > e-mail, is prohibited and may be unlawful. If you have received this > e-mail in error, please notify the sender by return e-mail and then > delete it from your system. >=20 > Internet communications cannot be guaranteed to be secure, > error or virus-free. The sender does not accept liability=20 > for any errors > or omissions which arise as a result. >=20 > Any views expressed in this message are those of the author, except > where the author specifies and, with authority, states them to be the > views of Imagination Technologies Limited. >=20 >=20 >=20 > ------------------------------------------------------- > All the advantages of Linux Managed Hosting--Without the Cost=20 > and Risk! > Fully trained technicians. The highest number of Red Hat=20 > certifications in > the hosting industry. Fanatical Support. Click to learn more > http://sel.as-us.falkag.net/sel?cmd=3Dk&kid=107521&bid$8729&dat=121642 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_ida88 >=20 |
From: Simon F. <sim...@po...> - 2006-05-30 08:30:19
|
From what I remember from my post-grad distributed computing course, I=0D=0A= don't recall that the timestamps have to be completely synchronised,=0D=0Ao= nly that they be unique and strictly increasing. I think you said that=0D=0A= each process had its own ID so you can form a timestamp by concatenating=0D= =0A"LocalTime" and ID. The local time then gets bumped up if you ever see=0D= =0Aanother that is greater. Mind you, I still don't how you are going to=0D= =0Ause this because I don't know how it all fits into the "grand scheme".=0D= =0A=0D=0AWhat I don't understand is who/what is doing the writing and to wh= ere=3F=0D=0AIf Machine A is writing to Machine B's USB stick, why can't Mac= hine B=0D=0Aforce the synchronisation=3F=20=0D=0A=0D=0ACheers=0D=0ASimon=0D= =0A=0D=0A=0D=0A> -----Original Message-----=0D=0A> From: gdalgorithms-list-= ad...@li...=20=0D=0A> [mailto:gdalgorithms-list-admin@lists= =2Esourceforge.net] On=20=0D=0A> Behalf Of Carsten Orthbandt=0D=0A> Sent: 3= 0 May 2006 09:19=0D=0A> To: gda...@li...=0D=0A> = Subject: RE: [Algorithms] Locking without atomic operations=0D=0A>=20=0D=0A= > This is sort-of about distributed databases. Timestamps won't=20=0D=0A> w= ork since the clients don't know each other and are not=20=0D=0A> syncroniz= ed. The server doesn't perform any logic and can't=20=0D=0A> be customized.= I looked into transactions a lot and all I=20=0D=0A> found needs some sema= phore handling in a central place.=0D=0A>=20=0D=0A> Basically I need a way = to let clients fetch and store=20=0D=0A> arbitrary data on arbitrary media = (HTTP server, USB stick,=0D=0A> whatever) while ensuring there's always onl= y one client=20=0D=0A> actually writing data (multiple reads are fine, also= in=20=0D=0A> concurrency with writes). All the remaining logic can easily =0D= =0A> be handled through file contents, but I need a central anchor=20=0D=0A= > that can be locked for writing.=0D=0A>=20=0D=0A>=20=0D=0A> Carsten Orthba= ndt=0D=0A> Founder + Development Director=0D=0A> SEK SpieleEntwicklungsKomb= inat GmbH=0D=0A> http://www.sek-ost.de=0D=0A>=20=0D=0A> Wenn ich Visionen h= abe, gehe ich zum Arzt. - Helmut Schmidt=0D=0A> =20=0D=0A>=20=0D=0A> > ---= --Original Message-----=0D=0A> > From: gda...@li...urce= forge.net=0D=0A> > [mailto:gda...@li...] O= n Behalf Of=20=0D=0A> > Simon Fenney=0D=0A> > Sent: Tuesday, May 30, 2006 1= 0:10 AM=0D=0A> > To: gda...@li...=0D=0A> > Subje= ct: RE: [Algorithms] Locking without atomic operations=0D=0A> >=20=0D=0A> >= Carsten,=0D=0A> > Are you trying to do something on a single CPU or are y= ou managing=20=0D=0A> > multiple CPUs in a network=3F If it's the latter (a= nd this is=20=0D=0A> stretching=20=0D=0A> > my memory back ~20 years) why n= ot search for papers with keywords=0D=0A> >=20=0D=0A> > "timestamps" "T= ransactions" and possibly "distributed=20=0D=0A> databases".=0D=0A> >=20=0D= =0A> > It might be what you are looking for.=0D=0A> >=20=0D=0A> > Simon=0D=0A= > >=20=0D=0A> > > -----Original Message-----=0D=0A> > > From: gdalgorithms-= lis...@li...=0D=0A> > > [mailto:gdalgorithms-list-admin= @lists.sourceforge.net] On=20=0D=0A> Behalf Of=20=0D=0A> > > Carsten Orthba= ndt=0D=0A> > > Sent: 30 May 2006 08:43=0D=0A> > > To: gdalgorithms-list@lis= ts.sourceforge.net=0D=0A> > > Subject: RE: [Algorithms] Locking without ato= mic operations=0D=0A> > >=20=0D=0A> > > If I could implement any logic besi= des READ and WRITE on=20=0D=0A> the server,=20=0D=0A> > > this problem woul= dn't be one ;-) The HTTP PUT/GET was=20=0D=0A> only mentioned=20=0D=0A> > >= as an example, it's not the only protocol.=0D=0A> > > Think about implemen= ting this through all of HTTP, FTP,=20=0D=0A> local files,=20=0D=0A> > > ne= twork shares, System RAM.=0D=0A> > > With the smallest common of all enviro= nments, I'm basically left=20=0D=0A> > > with atomic READ and WRITE, nothin= g else...=0D=0A> > > There must be some smarter brain out there who already= =20=0D=0A> solved this=20=0D=0A> > > for me ;-)=0D=0A> > >=20=0D=0A> > > Ca= rsten Orthbandt=0D=0A> > > Founder + Development Director=0D=0A> > > SEK Sp= ieleEntwicklungsKombinat GmbH=0D=0A> > > http://www.sek-ost.de=0D=0A> > > =0D= =0A> > > Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt=0D=0A>= > > =20=0D=0A> > >=20=0D=0A> > > > -----Original Message-----=0D=0A> > > = > From: gda...@li...=0D=0A> > > > [mailto:= gda...@li...] On=0D=0A> > Behalf Of=0D=0A>= > > > Kenneth B. Russell=0D=0A> > > > Sent: Tuesday, May 30, 2006 9:34 AM=0D= =0A> > > > To: gda...@li...=0D=0A> > > > Subject= : Re: [Algorithms] Locking without atomic operations=0D=0A> > > >=20=0D=0A>= > > > Can you implement the locking operation atomically on the=0D=0A> > >= server using=0D=0A> > > > an HTTP PUT or POST on the client=3F In other wo= rds, the=0D=0A> > > client sends a=0D=0A> > > > PUT message containing its = GUID and receives a response code=20=0D=0A> > > > indicating whether the lo= ck operation succeeded. If it=20=0D=0A> did, it is=20=0D=0A> > > > privileg= ed to do whatever operations it needs to do under=0D=0A> > > the cover of=0D= =0A> > > > the lock. It would then later send an unlock message to=0D=0A> >= the server=0D=0A> > > > using another PUT with its GUID. You could handle = clients which=20=0D=0A> > > > disconnect in the middle of the operation usi= ng timeouts or=0D=0A> > > a similar=0D=0A> > > > mechanism, and perhaps eve= n use a two-phase commit so that=20=0D=0A> > > > inconsistent states can't = be seen by other clients.=0D=0A> > > >=20=0D=0A> > > > Does any of this sou= nd plausible=3F=0D=0A> > > >=20=0D=0A> > > > -Ken=0D=0A> > > >=20=0D=0A> > = > >=20=0D=0A> > > > Carsten Orthbandt wrote:=0D=0A> > > >=20=0D=0A> > > > >= Interesting read, but...=0D=0A> > > > > It comes close, but doesn't solve = the problem. Dekker's=0D=0A> > algorithm=0D=0A> > > > > (at least as far as= I understand it) and this refinement=0D=0A> > > > both require=0D=0A> > > = > > me to know the number of clients, which I don't. Since=0D=0A> > > enume= ration=0D=0A> > > > > of the address space is also not supported, I can't u= se a=0D=0A> > > bit field=0D=0A> > > > > with one bit for every client sinc= e no client is able=0D=0A> > to tell the=0D=0A> > > > > actual number of cl= ients to check interest against and in=0D=0A> > > > turn doesn't=0D=0A> > >= > > know how many bits to check.=0D=0A> > > > > In the mentioned environme= nt (it's only an example) this=0D=0A> > > would need=0D=0A> > > > > directo= ry browsing in addition to HTTP GET and PUT,=0D=0A> > which is not=0D=0A> >= > > > available.=0D=0A> > > > > Another restriction is that my client IDs = are unique=20=0D=0A> AND sparse.=0D=0A> > > > > In the final application we= 're not even talking about=0D=0A> > integer IDs=0D=0A> > > > > but obviousl= y it will be GUIDs which makes scanning over=0D=0A> > > > all possible=0D=0A= > > > > > client IDs a no-go (not that it would make much sense=0D=0A> > > = with integer=0D=0A> > > > > IDs either).=0D=0A> > > > > I don't care if the= locking is "fair" or very efficient,=0D=0A> > > I only need=0D=0A> > > > >= a method that works for the (rare but possible) case of a=0D=0A> > > colli= sion.=0D=0A> > > > >=20=0D=0A> > > > > Thanks,=0D=0A> > > > >=20=0D=0A> > >= > > Carsten Orthbandt=0D=0A> > > > > Founder + Development Director=0D=0A>= > > > > SEK SpieleEntwicklungsKombinat GmbH http://www.sek-ost.de=0D=0A> >= > > >=20=0D=0A> > > > > Wenn ich Visionen habe, gehe ich zum Arzt. - Helmu= t Schmidt=0D=0A> > > > > =20=0D=0A> > > > >=20=0D=0A> > > > >=20=0D=0A> > = > > >>-----Original Message-----=0D=0A> > > > >>From: gdalgorithms-list-adm= in...@li...=0D=0A> > > > >>[mailto:gdalgorithms-list-admin@lis= ts.sourceforge.net] On=0D=0A> > > Behalf Of=0D=0A> > > > >>Kenneth B. Russe= ll=0D=0A> > > > >>Sent: Tuesday, May 30, 2006 8:56 AM=0D=0A> > > > >>To: gd= alg...@li...=0D=0A> > > > >>Subject: Re: [Algorith= ms] Locking without atomic operations=0D=0A> > > > >>=0D=0A> > > > >>Have y= ou looked into Dekker's algorithm and its=0D=0A> > > generalizations to=0D=0A= > > > > >>multiple (more than two) clients=3F I'm not completely sure the =0D= =0A> > > > >>operations you have available cover what is needed to=0D=0A> >= > implement it=0D=0A> > > > >>but=0D=0A> > > > it sounds=0D=0A> > > > >>li= ke it from a cursory look. The following reference points=0D=0A> > > > to o= ther=0D=0A> > > > >>related references which offer fair solutions, meaning = you=0D=0A> > > > won't run=0D=0A> > > > >>into livelock under heavy content= ion. This was found with=0D=0A> > > a Google=0D=0A> > > > >>search for "dek= ker mutual exclusion generalization".=0D=0A> > > > >>=0D=0A> > > > >>http:/= /caltechcstr.library.caltech.edu/359/=0D=0A> > > > >>=0D=0A> > > > >>-Ken=0D= =0A> > > > >>=0D=0A> > > > >>=0D=0A> > > > >>Carsten Orthbandt wrote:=0D=0A= > > > > >>=0D=0A> > > > >>=0D=0A> > > > >>>I crawled the web for a solution= to this but I only found=0D=0A> > > > references=0D=0A> > > > >>>to "mostl= y" without atomic operations and such stuff.=0D=0A> > > > >>>=0D=0A> > > > = >>>Given N integer memory locations and only the operations=0D=0A> > > > >>= >value=3DRead(addr)=0D=0A> > > > >>>and Write(addr,value), I'm looking for = a way to syncronize=0D=0A> > > > >>=0D=0A> > > > >>access to a=0D=0A> > > >= >>=0D=0A> > > > >>>resource from multiple clients, each with a guaranteed=0D= =0A> > > > >>=0D=0A> > > > >>unique integer=0D=0A> > > > >>=0D=0A> > > > >>= >id.=0D=0A> > > > >>>The lock attempf should fail if there is already a loc= k or=0D=0A> > > > >>=0D=0A> > > > >>there's some=0D=0A> > > > >>=0D=0A> > >= > >>>sort of collision while obtaining the lock.=0D=0A> > > > >>>=0D=0A> >= > > >>>The solution I've come up but have not really=20=0D=0A> verified is= this:=0D=0A> > > > >>>=0D=0A> > > > >>>Nominate two memory locations A and= B.=0D=0A> > > > >>>=0D=0A> > > > >>>Init: Set A and B to 0. All client IDs= are >=3D1.=0D=0A> > > > >>>=0D=0A> > > > >>>for Locking:=0D=0A> > > > >>>i= f(ReadA()!=3D0)=0D=0A> > > > >>>=09abort;=0D=0A> > > > >>>if(ReadB()!=3D0)=0D= =0A> > > > >>>=09abort;=0D=0A> > > > >>>WriteA(myID);=0D=0A> > > > >>>if(Re= adB()!=3D0)=0D=0A> > > > >>>=09WriteA(0)=0D=0A> > > > >>>=09abort;=0D=0A> >= > > >>>if(ReadA()!=3DmyID)=0D=0A> > > > >>>=09abort;=0D=0A> > > > >>>Write= B(myID);=0D=0A> > > > >>>done.=0D=0A> > > > >>>=0D=0A> > > > >>>I'll try to= mold this into VMish code to do actual tests,=0D=0A> > > > >>=0D=0A> > > >= >>but would like=0D=0A> > > > >>=0D=0A> > > > >>>to ask if there's some we= ll-known clever solution to=0D=0A> > > this that I'm=0D=0A> > > > >>>simply= not aware of.=0D=0A> > > > >>>=0D=0A> > > > >>>Please note that the REAL p= roblem is not about IPC or=0D=0A> > > such stuff, I=0D=0A> > > > >>>really = only have these two operations Read and Write, but an=0D=0A> > > > >>=0D=0A= > > > > >>arbitrary number=0D=0A> > > > >>=0D=0A> > > > >>>of=0D=0A> > > > = >>>"registers" to use (think of HTTP GET and PUT). Enumeration=0D=0A> > > >= >>=0D=0A> > > > >>of anything=0D=0A> > > > >>=0D=0A> > > > >>>is=0D=0A> > = > > >>>not available.=0D=0A> > > > >>>=0D=0A> > > > >>>Best regards,=0D=0A>= > > > >>>=0D=0A> > > > >>>Carsten Orthbandt=0D=0A> > > > >>>Founder + Deve= lopment Director=0D=0A> > > > >>>SEK SpieleEntwicklungsKombinat GmbH http:/= /www.sek-ost.de=0D=0A> > > > >>>=0D=0A> > > > >>>Wenn ich Visionen habe, ge= he ich zum Arzt. - Helmut Schmidt=0D=0A> > > > >>>=20=0D=0A> > > > >>>=0D=0A= > > > > >>>=0D=0A> > > > >>>-----------------------------------------------= --------=0D=0A> > > > >>>All the advantages of Linux Managed Hosting--Witho= ut the=0D=0A> > > > >>=0D=0A> > > > >>Cost and Risk!=0D=0A> > > > >>=0D=0A>= > > > >>>Fully trained technicians. The highest number of Red Hat=0D=0A> >= > > >>=0D=0A> > > > >>certifications in=0D=0A> > > > >>=0D=0A> > > > >>>th= e hosting industry. Fanatical Support. Click to learn more=0D=0A> > > > >>>=0D= =0A> > > > >>=0D=0A> > > > >>http://sel.as-us.falkag.net/sel=3Fcmd_________= __________________=0D=0A> > > > >=20=0D=0A> > > > > ____________________=0D= =0A> > > > >=20=0D=0A> > > > >>>GDAlgorithms-list mailing list=0D=0A> > > >= >>>GDA...@li...=0D=0A> > > >=20=0D=0A> >>>https= ://lists.sourceforge.net/lists/listinfo/gdalgorithms-list=0D=0A> > > > >>>A= rchives:=0D=0A> > > > >>>http://sourceforge.net/mailarchive/forum.php=3Ffor= um_ida88=0D=0A> > > > >>=0D=0A> > > > >>=0D=0A> > > > >>=0D=0A> > > > >>---= ----------------------------------------------------=0D=0A> > > > >>All the= advantages of Linux Managed Hosting--Without=0D=0A> > the Cost and=0D=0A> = > > > >>Risk!=0D=0A> > > > >>Fully trained technicians. The highest number = of Red Hat=20=0D=0A> > > > >>certifications in the hosting industry. Fanati= cal=0D=0A> > > Support. Click to=0D=0A> > > > >>learn more=0D=0A> > > > >>h= ttp://sel.as-us.falkag.net/sel=3Fcmd=3Dlnk&kid=3D107521&bid=3D248729&=0D=0A= > > > > >=20=0D=0A> > > > > dat=3D121642=0D=0A> > > > >=20=0D=0A> > > > >>_= ______________________________________________=0D=0A> > > > >>GDAlgorithms-= list mailing list=0D=0A> > > > >>GDA...@li...=0D= =0A> > > > >>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list=0D= =0A> > > > >>Archives:=0D=0A> > > > >>http://sourceforge.net/mailarchive/fo= rum.php=3Fforum_id=3D6188=0D=0A> > > > >>=0D=0A> > > > >=20=0D=0A> > > > > =0D= =0A> > > > >=20=0D=0A> > > > > --------------------------------------------= -----------=0D=0A> > > > > All the advantages of Linux Managed Hosting--Wit= hout the=0D=0A> > > > Cost and Risk!=0D=0A> > > > > Fully trained technicia= ns. The highest number of Red Hat=0D=0A> > > > certifications in=0D=0A> > >= > > the hosting industry. Fanatical Support. Click to learn more=0D=0A> > = > > >=20=0D=0A> > > > http://sel.as-us.falkag.net/sel=3Fcmd________________= ___________=0D=0A> > > > ____________________=0D=0A> > > > > GDAlgorithms-l= ist mailing list=0D=0A> > > > > GDA...@li...=0D=0A= > > > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list=0D= =0A> > > > > Archives:=0D=0A> > > > > http://sourceforge.net/mailarchive/fo= rum.php=3Fforum_ida88=0D=0A> > > >=20=0D=0A> > > >=20=0D=0A> > > >=20=0D=0A= > > > > -------------------------------------------------------=0D=0A> > > = > All the advantages of Linux Managed Hosting--Without=20=0D=0A> the Cost a= nd=20=0D=0A> > > > Risk!=0D=0A> > > > Fully trained technicians. The highes= t number of Red Hat=20=0D=0A> > > > certifications in the hosting industry.= Fanatical=0D=0A> > Support. Click to=0D=0A> > > > learn more=0D=0A> > > > = http://sel.as-us.falkag.net/sel=3Fcmd=3Dlnk&kid=3D107521&bid=3D248729&=0D=0A= > > > > dat=3D121642=0D=0A> > > > _________________________________________= ______=0D=0A> > > > GDAlgorithms-list mailing list=0D=0A> > > > GDAlgorithm= s-...@li...=0D=0A> > > > https://lists.sourceforge.net/lis= ts/listinfo/gdalgorithms-list=0D=0A> > > > Archives:=0D=0A> > > > http://so= urceforge.net/mailarchive/forum.php=3Fforum_id=3D6188=0D=0A> > > >=20=0D=0A= > > >=20=0D=0A> > >=20=0D=0A> > > -----------------------------------------= --------------=0D=0A> > > All the advantages of Linux Managed Hosting--With= out the Cost and=20=0D=0A> > > Risk!=0D=0A> > > Fully trained technicians. = The highest number of Red Hat=20=0D=0A> > > certifications in the hosting i= ndustry. Fanatical Support.=0D=0A> > > Click to learn more=0D=0A> > > http:= //sel.as-us.falkag.net/sel=3Fcmd=3Dk&kid=107521&bid$8729&dat=121642=0D=0A> = > > _______________________________________________=0D=0A> > > GDAlgorithms= -list mailing list=0D=0A> > > GDA...@li...=0D=0A= > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list=0D=0A>= > > Archives:=0D=0A> > > http://sourceforge.net/mailarchive/forum.php=3Ffo= rum_ida88=0D=0A> > >=20=0D=0A> > >=20=0D=0A> >=20=0D=0A> > ****************= **=0D=0A> > This e-mail has been sent from Imagination Technologies Limited= =2E=0D=0A> > PowerVR, Metagence, Ensigma and PURE Digital are divisions of =0D= =0A> > Imagination Technologies Limited.=0D=0A> >=20=0D=0A> > The informati= on contained in this e-mail, including any=20=0D=0A> attachment, is=20=0D=0A= > > confidential and may be legally privileged. It is intended=20=0D=0A> s= olely for=20=0D=0A> > the addressee(s) and access to this e-mail by anyone = else is=20=0D=0A> > unauthorised. If you are not the intended recipient, a= ny=20=0D=0A> disclosure,=20=0D=0A> > copying or distribution or use of the = information contained in this=20=0D=0A> > e-mail, is prohibited and may be = unlawful. If you have=20=0D=0A> received this=20=0D=0A> > e-mail in error,= please notify the sender by return e-mail and then=20=0D=0A> > delete it f= rom your system.=0D=0A> >=20=0D=0A> > Internet communications cannot be gua= ranteed to be secure, error or=20=0D=0A> > virus-free. The sender does not= accept liability for any errors or=20=0D=0A> > omissions which arise as a = result.=0D=0A> >=20=0D=0A> > Any views expressed in this message are those = of the author, except=20=0D=0A> > where the author specifies and, with auth= ority, states them=20=0D=0A> to be the=20=0D=0A> > views of Imagination Tec= hnologies Limited.=0D=0A> >=20=0D=0A> >=20=0D=0A> >=20=0D=0A> > -----------= --------------------------------------------=0D=0A> > All the advantages of= Linux Managed Hosting--Without the Cost and=20=0D=0A> > Risk!=0D=0A> > Ful= ly trained technicians. The highest number of Red Hat=20=0D=0A> > certifica= tions in the hosting industry. Fanatical Support. Click to=20=0D=0A> > lear= n more=0D=0A> > http://sel.as-us.falkag.net/sel=3Fcmd=3Dk&kid=107521&bid$87= 29&dat=121642=0D=0A> > _______________________________________________=0D=0A= > > GDAlgorithms-list mailing list=0D=0A> > GDA...@li...urcef= orge.net=0D=0A> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms= -list=0D=0A> > Archives:=0D=0A> > http://sourceforge.net/mailarchive/forum.= php=3Fforum_ida88=0D=0A> >=20=0D=0A>=20=0D=0A>=20=0D=0A> ------------------= -------------------------------------=0D=0A> All the advantages of Linux Ma= naged Hosting--Without the Cost=20=0D=0A> and Risk!=0D=0A> Fully trained te= chnicians. The highest number of Red Hat=20=0D=0A> certifications in the ho= sting industry. Fanatical Support.=20=0D=0A> Click to learn more=0D=0A> htt= p://sel.as-us.falkag.net/sel=3Fcmd=3Dk&kid=107521&bid$8729&dat=121642=0D=0A= > _______________________________________________=0D=0A> GDAlgorithms-list = mailing list=0D=0A> GDA...@li...=0D=0A> https://= lists.sourceforge.net/lists/listinfo/gdalgorithms-list=0D=0A> Archives:=0D=0A= > http://sourceforge.net/mailarchive/forum.php=3Fforum_ida88=0D=0A>=20=0D=0A= >=20=0D=0A=0D=0A******************=0D=0AThis e-mail has been sent from Imag= ination Technologies Limited.=0D=0APowerVR, Metagence, Ensigma and PURE Dig= ital are divisions=0D=0Aof Imagination Technologies Limited.=0D=0A=0D=0AThe= information contained in this e-mail, including any attachment,=0D=0Ais co= nfidential and may be legally privileged. It is intended solely=0D=0Afor t= he addressee(s) and access to this e-mail by anyone else is=0D=0Aunauthoris= ed. If you are not the intended recipient, any disclosure,=0D=0Acopying or= distribution or use of the information contained in this=20=0D=0Ae-mail, i= s prohibited and may be unlawful. If you have received this=0D=0Ae-mail in= error, please notify the sender by return e-mail and then=0D=0Adelete it f= rom your system.=0D=0A=0D=0AInternet communications cannot be guaranteed to= be secure,=0D=0Aerror or virus-free. The sender does not accept liability= for any errors=0D=0Aor omissions which arise as a result.=0D=0A=0D=0AAny v= iews expressed in this message are those of the author, except=0D=0Awhere t= he author specifies and, with authority, states them to be the=0D=0Aviews o= f Imagination Technologies Limited.=0D=0A |
From: Carsten O. <car...@se...> - 2006-05-30 08:33:32
|
If we stay by the HTTP example on a bog-standard apache, there is no atomic test-and-write operation. Same goes with FTP. I'd like to have this work without implementing protocol-specific locking because there are protocols that don't provide it.=20 Shared memory in a multicore environment would be another example where locking would only work outside the actual data storage (through mutexes or whatever). Carsten Orthbandt Founder + Development Director SEK SpieleEntwicklungsKombinat GmbH http://www.sek-ost.de <http://www.sek-ost.de/>=20 Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt =20 =20 ________________________________ From: gda...@li... [mailto:gda...@li...] On Behalf Of Ale...@sc... Sent: Tuesday, May 30, 2006 10:20 AM To: gda...@li... Subject: RE: [Algorithms] Locking without atomic operations =09 =09 Out of curiosity, why would you want to try and implement this without the use of atomic operations? =09 Alex Clarke Sony Computer Entertainment Europe http://www.scee.com =09 =09 ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify pos...@sc... This footnote also confirms that this email message has been checked for all known viruses. ********************************************************************** Sony Computer Entertainment Europe=20 |
From: Mike S. <mik...@gm...> - 2006-05-30 13:31:51
|
On 5/30/06, Carsten Orthbandt <car...@se...> wrote: > If we stay by the HTTP example on a bog-standard apache, > there is no atomic test-and-write operation. Not true, AFAIK. Apache has supported If-Match and If-Unmodified-Since (which always uses server time) against etags for quite some time -- since 1.2 at least. Mike |
From: Carsten O. <car...@se...> - 2006-05-30 08:38:57
|
It's not about two machines writing to the same USB. For USB sticks, it's more about two instances of my process accessing the same stick. And then there's the case where two processes (on the same machine or on different ones) access a repository on a HTTP, FTP or gopher server. The first case would have to sync through IPC, the second through server logic. See the problem? If this isn't hard enough, think about this: One file server, accessed through file shares from the LAN, but FTP from the WAN. How is this going to work? All application logic _should_ work on top of a very agnostic access protocol that I don't want to restrict to systems that support real locking. I'd like to stay away from special-casing each and every access protocol. Carsten Orthbandt Founder + Development Director SEK SpieleEntwicklungsKombinat GmbH http://www.sek-ost.de Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt =20 > -----Original Message----- > From: gda...@li...=20 > [mailto:gda...@li...] On=20 > Behalf Of Simon Fenney > Sent: Tuesday, May 30, 2006 10:30 AM > To: gda...@li... > Subject: RE: [Algorithms] Locking without atomic operations >=20 > From what I remember from my post-grad distributed computing course, I > don't recall that the timestamps have to be completely synchronised, > only that they be unique and strictly increasing. I think you=20 > said that > each process had its own ID so you can form a timestamp by=20 > concatenating > "LocalTime" and ID. The local time then gets bumped up if you ever see > another that is greater. Mind you, I still don't how you are going to > use this because I don't know how it all fits into the "grand scheme". >=20 > What I don't understand is who/what is doing the writing and to where? > If Machine A is writing to Machine B's USB stick, why can't Machine B > force the synchronisation?=20 >=20 > Cheers > Simon >=20 >=20 > > -----Original Message----- > > From: gda...@li...=20 > > [mailto:gda...@li...] On=20 > > Behalf Of Carsten Orthbandt > > Sent: 30 May 2006 09:19 > > To: gda...@li... > > Subject: RE: [Algorithms] Locking without atomic operations > >=20 > > This is sort-of about distributed databases. Timestamps won't=20 > > work since the clients don't know each other and are not=20 > > syncronized. The server doesn't perform any logic and can't=20 > > be customized. I looked into transactions a lot and all I=20 > > found needs some semaphore handling in a central place. > >=20 > > Basically I need a way to let clients fetch and store=20 > > arbitrary data on arbitrary media (HTTP server, USB stick, > > whatever) while ensuring there's always only one client=20 > > actually writing data (multiple reads are fine, also in=20 > > concurrency with writes). All the remaining logic can easily=20 > > be handled through file contents, but I need a central anchor=20 > > that can be locked for writing. > >=20 > >=20 > > Carsten Orthbandt > > Founder + Development Director > > SEK SpieleEntwicklungsKombinat GmbH > > http://www.sek-ost.de > >=20 > > Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt > > =20 > >=20 > > > -----Original Message----- > > > From: gda...@li... > > > [mailto:gda...@li...] On=20 > Behalf Of=20 > > > Simon Fenney > > > Sent: Tuesday, May 30, 2006 10:10 AM > > > To: gda...@li... > > > Subject: RE: [Algorithms] Locking without atomic operations > > >=20 > > > Carsten, > > > Are you trying to do something on a single CPU or are=20 > you managing=20 > > > multiple CPUs in a network? If it's the latter (and this is=20 > > stretching=20 > > > my memory back ~20 years) why not search for papers with keywords > > >=20 > > > "timestamps" "Transactions" and possibly "distributed=20 > > databases". > > >=20 > > > It might be what you are looking for. > > >=20 > > > Simon > > >=20 > > > > -----Original Message----- > > > > From: gda...@li... > > > > [mailto:gda...@li...] On=20 > > Behalf Of=20 > > > > Carsten Orthbandt > > > > Sent: 30 May 2006 08:43 > > > > To: gda...@li... > > > > Subject: RE: [Algorithms] Locking without atomic operations > > > >=20 > > > > If I could implement any logic besides READ and WRITE on=20 > > the server,=20 > > > > this problem wouldn't be one ;-) The HTTP PUT/GET was=20 > > only mentioned=20 > > > > as an example, it's not the only protocol. > > > > Think about implementing this through all of HTTP, FTP,=20 > > local files,=20 > > > > network shares, System RAM. > > > > With the smallest common of all environments, I'm=20 > basically left=20 > > > > with atomic READ and WRITE, nothing else... > > > > There must be some smarter brain out there who already=20 > > solved this=20 > > > > for me ;-) > > > >=20 > > > > Carsten Orthbandt > > > > Founder + Development Director > > > > SEK SpieleEntwicklungsKombinat GmbH > > > > http://www.sek-ost.de > > > >=20 > > > > Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt > > > > =20 > > > >=20 > > > > > -----Original Message----- > > > > > From: gda...@li... > > > > > [mailto:gda...@li...] On > > > Behalf Of > > > > > Kenneth B. Russell > > > > > Sent: Tuesday, May 30, 2006 9:34 AM > > > > > To: gda...@li... > > > > > Subject: Re: [Algorithms] Locking without atomic operations > > > > >=20 > > > > > Can you implement the locking operation atomically on the > > > > server using > > > > > an HTTP PUT or POST on the client? In other words, the > > > > client sends a > > > > > PUT message containing its GUID and receives a response code=20 > > > > > indicating whether the lock operation succeeded. If it=20 > > did, it is=20 > > > > > privileged to do whatever operations it needs to do under > > > > the cover of > > > > > the lock. It would then later send an unlock message to > > > the server > > > > > using another PUT with its GUID. You could handle=20 > clients which=20 > > > > > disconnect in the middle of the operation using timeouts or > > > > a similar > > > > > mechanism, and perhaps even use a two-phase commit so that=20 > > > > > inconsistent states can't be seen by other clients. > > > > >=20 > > > > > Does any of this sound plausible? > > > > >=20 > > > > > -Ken > > > > >=20 > > > > >=20 > > > > > Carsten Orthbandt wrote: > > > > >=20 > > > > > > Interesting read, but... > > > > > > It comes close, but doesn't solve the problem. Dekker's > > > algorithm > > > > > > (at least as far as I understand it) and this refinement > > > > > both require > > > > > > me to know the number of clients, which I don't. Since > > > > enumeration > > > > > > of the address space is also not supported, I can't use a > > > > bit field > > > > > > with one bit for every client since no client is able > > > to tell the > > > > > > actual number of clients to check interest against and in > > > > > turn doesn't > > > > > > know how many bits to check. > > > > > > In the mentioned environment (it's only an example) this > > > > would need > > > > > > directory browsing in addition to HTTP GET and PUT, > > > which is not > > > > > > available. > > > > > > Another restriction is that my client IDs are unique=20 > > AND sparse. > > > > > > In the final application we're not even talking about > > > integer IDs > > > > > > but obviously it will be GUIDs which makes scanning over > > > > > all possible > > > > > > client IDs a no-go (not that it would make much sense > > > > with integer > > > > > > IDs either). > > > > > > I don't care if the locking is "fair" or very efficient, > > > > I only need > > > > > > a method that works for the (rare but possible) case of a > > > > collision. > > > > > >=20 > > > > > > Thanks, > > > > > >=20 > > > > > > Carsten Orthbandt > > > > > > Founder + Development Director > > > > > > SEK SpieleEntwicklungsKombinat GmbH http://www.sek-ost.de > > > > > >=20 > > > > > > Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt > > > > > > =20 > > > > > >=20 > > > > > >=20 > > > > > >>-----Original Message----- > > > > > >>From: gda...@li... > > > > > >>[mailto:gda...@li...] On > > > > Behalf Of > > > > > >>Kenneth B. Russell > > > > > >>Sent: Tuesday, May 30, 2006 8:56 AM > > > > > >>To: gda...@li... > > > > > >>Subject: Re: [Algorithms] Locking without atomic operations > > > > > >> > > > > > >>Have you looked into Dekker's algorithm and its > > > > generalizations to > > > > > >>multiple (more than two) clients? I'm not=20 > completely sure the=20 > > > > > >>operations you have available cover what is needed to > > > > implement it > > > > > >>but > > > > > it sounds > > > > > >>like it from a cursory look. The following reference points > > > > > to other > > > > > >>related references which offer fair solutions, meaning you > > > > > won't run > > > > > >>into livelock under heavy contention. This was found with > > > > a Google > > > > > >>search for "dekker mutual exclusion generalization". > > > > > >> > > > > > >>http://caltechcstr.library.caltech.edu/359/ > > > > > >> > > > > > >>-Ken > > > > > >> > > > > > >> > > > > > >>Carsten Orthbandt wrote: > > > > > >> > > > > > >> > > > > > >>>I crawled the web for a solution to this but I only found > > > > > references > > > > > >>>to "mostly" without atomic operations and such stuff. > > > > > >>> > > > > > >>>Given N integer memory locations and only the operations > > > > > >>>value=3DRead(addr) > > > > > >>>and Write(addr,value), I'm looking for a way to syncronize > > > > > >> > > > > > >>access to a > > > > > >> > > > > > >>>resource from multiple clients, each with a guaranteed > > > > > >> > > > > > >>unique integer > > > > > >> > > > > > >>>id. > > > > > >>>The lock attempf should fail if there is already a lock or > > > > > >> > > > > > >>there's some > > > > > >> > > > > > >>>sort of collision while obtaining the lock. > > > > > >>> > > > > > >>>The solution I've come up but have not really=20 > > verified is this: > > > > > >>> > > > > > >>>Nominate two memory locations A and B. > > > > > >>> > > > > > >>>Init: Set A and B to 0. All client IDs are >=3D1. > > > > > >>> > > > > > >>>for Locking: > > > > > >>>if(ReadA()!=3D0) > > > > > >>> abort; > > > > > >>>if(ReadB()!=3D0) > > > > > >>> abort; > > > > > >>>WriteA(myID); > > > > > >>>if(ReadB()!=3D0) > > > > > >>> WriteA(0) > > > > > >>> abort; > > > > > >>>if(ReadA()!=3DmyID) > > > > > >>> abort; > > > > > >>>WriteB(myID); > > > > > >>>done. > > > > > >>> > > > > > >>>I'll try to mold this into VMish code to do actual tests, > > > > > >> > > > > > >>but would like > > > > > >> > > > > > >>>to ask if there's some well-known clever solution to > > > > this that I'm > > > > > >>>simply not aware of. > > > > > >>> > > > > > >>>Please note that the REAL problem is not about IPC or > > > > such stuff, I > > > > > >>>really only have these two operations Read and=20 > Write, but an > > > > > >> > > > > > >>arbitrary number > > > > > >> > > > > > >>>of > > > > > >>>"registers" to use (think of HTTP GET and PUT). Enumeration > > > > > >> > > > > > >>of anything > > > > > >> > > > > > >>>is > > > > > >>>not available. > > > > > >>> > > > > > >>>Best regards, > > > > > >>> > > > > > >>>Carsten Orthbandt > > > > > >>>Founder + Development Director > > > > > >>>SEK SpieleEntwicklungsKombinat GmbH http://www.sek-ost.de > > > > > >>> > > > > > >>>Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt > > > > > >>>=20 > > > > > >>> > > > > > >>> > > > > > >>>------------------------------------------------------- > > > > > >>>All the advantages of Linux Managed Hosting--Without the > > > > > >> > > > > > >>Cost and Risk! > > > > > >> > > > > > >>>Fully trained technicians. The highest number of Red Hat > > > > > >> > > > > > >>certifications in > > > > > >> > > > > > >>>the hosting industry. Fanatical Support. Click to=20 > learn more > > > > > >>> > > > > > >> > > > > >=20 > >>http://sel.as-us.falkag.net/sel?cmd___________________________ > > > > > >=20 > > > > > > ____________________ > > > > > >=20 > > > > > >>>GDAlgorithms-list mailing list > > > > > >>>GDA...@li... > > > > >=20 > > >>>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > > > >>>Archives: > > > > > >>>http://sourceforge.net/mailarchive/forum.php?forum_ida88 > > > > > >> > > > > > >> > > > > > >> > > > > > >>------------------------------------------------------- > > > > > >>All the advantages of Linux Managed Hosting--Without > > > the Cost and > > > > > >>Risk! > > > > > >>Fully trained technicians. The highest number of Red Hat=20 > > > > > >>certifications in the hosting industry. Fanatical > > > > Support. Click to > > > > > >>learn more > > > > >=20 > >>http://sel.as-us.falkag.net/sel?cmd=3Dlnk&kid=3D107521&bid=3D248729& > > > > > >=20 > > > > > > dat=3D121642 > > > > > >=20 > > > > > >>_______________________________________________ > > > > > >>GDAlgorithms-list mailing list > > > > > >>GDA...@li... > > > > >=20 > >>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > > > >>Archives: > > > > > >>http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > > > > >> > > > > > >=20 > > > > > >=20 > > > > > >=20 > > > > > > ------------------------------------------------------- > > > > > > All the advantages of Linux Managed Hosting--Without the > > > > > Cost and Risk! > > > > > > Fully trained technicians. The highest number of Red Hat > > > > > certifications in > > > > > > the hosting industry. Fanatical Support. Click to learn more > > > > > >=20 > > > > > http://sel.as-us.falkag.net/sel?cmd___________________________ > > > > > ____________________ > > > > > > GDAlgorithms-list mailing list > > > > > > GDA...@li... > > > > > >=20 > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > > > > Archives: > > > > > > http://sourceforge.net/mailarchive/forum.php?forum_ida88 > > > > >=20 > > > > >=20 > > > > >=20 > > > > > ------------------------------------------------------- > > > > > All the advantages of Linux Managed Hosting--Without=20 > > the Cost and=20 > > > > > Risk! > > > > > Fully trained technicians. The highest number of Red Hat=20 > > > > > certifications in the hosting industry. Fanatical > > > Support. Click to > > > > > learn more > > > > > = http://sel.as-us.falkag.net/sel?cmd=3Dlnk&kid=3D107521&bid=3D248729& > > > > > dat=3D121642 > > > > > _______________________________________________ > > > > > GDAlgorithms-list mailing list > > > > > GDA...@li... > > > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > > > Archives: > > > > > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > > > >=20 > > > >=20 > > > >=20 > > > > ------------------------------------------------------- > > > > All the advantages of Linux Managed Hosting--Without=20 > the Cost and=20 > > > > Risk! > > > > Fully trained technicians. The highest number of Red Hat=20 > > > > certifications in the hosting industry. Fanatical Support. > > > > Click to learn more > > > > = http://sel.as-us.falkag.net/sel?cmd=3Dk&kid=107521&bid$8729&dat=121642 > > > > _______________________________________________ > > > > GDAlgorithms-list mailing list > > > > GDA...@li... > > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > > Archives: > > > > http://sourceforge.net/mailarchive/forum.php?forum_ida88 > > > >=20 > > > >=20 > > >=20 > > > ****************** > > > This e-mail has been sent from Imagination Technologies Limited. > > > PowerVR, Metagence, Ensigma and PURE Digital are divisions of=20 > > > Imagination Technologies Limited. > > >=20 > > > The information contained in this e-mail, including any=20 > > attachment, is=20 > > > confidential and may be legally privileged. It is intended=20 > > solely for=20 > > > the addressee(s) and access to this e-mail by anyone else is=20 > > > unauthorised. If you are not the intended recipient, any=20 > > disclosure,=20 > > > copying or distribution or use of the information=20 > contained in this=20 > > > e-mail, is prohibited and may be unlawful. If you have=20 > > received this=20 > > > e-mail in error, please notify the sender by return=20 > e-mail and then=20 > > > delete it from your system. > > >=20 > > > Internet communications cannot be guaranteed to be=20 > secure, error or=20 > > > virus-free. The sender does not accept liability for any=20 > errors or=20 > > > omissions which arise as a result. > > >=20 > > > Any views expressed in this message are those of the=20 > author, except=20 > > > where the author specifies and, with authority, states them=20 > > to be the=20 > > > views of Imagination Technologies Limited. > > >=20 > > >=20 > > >=20 > > > ------------------------------------------------------- > > > All the advantages of Linux Managed Hosting--Without the Cost and=20 > > > Risk! > > > Fully trained technicians. The highest number of Red Hat=20 > > > certifications in the hosting industry. Fanatical=20 > Support. Click to=20 > > > learn more > > > = http://sel.as-us.falkag.net/sel?cmd=3Dk&kid=107521&bid$8729&dat=121642 > > > _______________________________________________ > > > GDAlgorithms-list mailing list > > > GDA...@li... > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > Archives: > > > http://sourceforge.net/mailarchive/forum.php?forum_ida88 > > >=20 > >=20 > >=20 > > ------------------------------------------------------- > > All the advantages of Linux Managed Hosting--Without the Cost=20 > > and Risk! > > Fully trained technicians. The highest number of Red Hat=20 > > certifications in the hosting industry. Fanatical Support.=20 > > Click to learn more > > = http://sel.as-us.falkag.net/sel?cmd=3Dk&kid=107521&bid$8729&dat=121642 > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_ida88 > >=20 > >=20 >=20 > ****************** > This e-mail has been sent from Imagination Technologies Limited. > PowerVR, Metagence, Ensigma and PURE Digital are divisions > of Imagination Technologies Limited. >=20 > The information contained in this e-mail, including any attachment, > is confidential and may be legally privileged. It is intended solely > for the addressee(s) and access to this e-mail by anyone else is > unauthorised. If you are not the intended recipient, any disclosure, > copying or distribution or use of the information contained in this=20 > e-mail, is prohibited and may be unlawful. If you have received this > e-mail in error, please notify the sender by return e-mail and then > delete it from your system. >=20 > Internet communications cannot be guaranteed to be secure, > error or virus-free. The sender does not accept liability=20 > for any errors > or omissions which arise as a result. >=20 > Any views expressed in this message are those of the author, except > where the author specifies and, with authority, states them to be the > views of Imagination Technologies Limited. >=20 >=20 >=20 > ------------------------------------------------------- > All the advantages of Linux Managed Hosting--Without the Cost=20 > and Risk! > Fully trained technicians. The highest number of Red Hat=20 > certifications in > the hosting industry. Fanatical Support. Click to learn more > http://sel.as-us.falkag.net/sel?cmd=3Dk&kid=107521&bid$8729&dat=121642 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_ida88 >=20 |
From: Carsten O. <car...@se...> - 2006-05-30 08:40:49
|
I was _hoping_ there's some algorithm that solves with only client-side logic. Maybe I'm wrong but this should be doable somehow.=20 Carsten Orthbandt Founder + Development Director SEK SpieleEntwicklungsKombinat GmbH http://www.sek-ost.de <http://www.sek-ost.de/>=20 Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt =20 =20 ________________________________ From: gda...@li... [mailto:gda...@li...] On Behalf Of Ale...@sc... Sent: Tuesday, May 30, 2006 10:34 AM To: gda...@li... Cc: gda...@li...; gda...@li... Subject: RE: [Algorithms] Locking without atomic operations =09 =09 "Basically I need a way to let clients fetch and store arbitrary data on arbitrary media (HTTP server, USB stick, whatever) while ensuring there's always only one client actually writing data (multiple reads are fine, also in concurrency with writes). All the remaining logic can easily be handled through file contents, but I need a central anchor that can be locked for writing."=20 =09 Ah I think I can see why now ;)=20 =09 It sounds to me like you're just going to have to have some sort of atmoic lock at some level. The clients can't do this semeselves (for obvious reasons), but perhaps the server they're connected to can do it for them? (and maybe queue up non-colliding writes too) =20 =09 Alex Clarke Sony Computer Entertainment Europe http://www.scee.com =09 =09 gda...@li... wrote on 30/05/2006 09:20:27: =09 >=20 > Out of curiosity, why would you want to try and implement this > without the use of atomic operations? >=20 > Alex Clarke > Sony Computer Entertainment Europe > http://www.scee.com >=20 > ********************************************************************** > This email and any files transmitted with it are confidential and=20 > intended solely for the use of the individual or entity to whom they > are addressed. If you have received this email in error please > notify pos...@sc... This footnote also confirms that this=20 > email message has been checked for all known viruses.=20 > ********************************************************************** > Sony Computer Entertainment Europe [attachment "attc6zc7.dat"=20 > deleted by Alex Clarke/15GMS/LO/UK/SCEE]=20 |
From: Richard F. <ra...@de...> - 2006-05-30 10:12:46
|
On 30/05/06, Carsten Orthbandt <car...@se...> wrote: > > I was _hoping_ there's some algorithm that solves with only client-side > logic. Maybe I'm wrong but this should be doable somehow. I think that this assumption may be false, In fact, i beleive there may be a mathematical proof out there somewhere that what you're trying to do is impossible. what you might be able to do is "minimise" bad access, to do this, you need to do you "readID writeID" steps, then delay about a second, then "readID, writeData"... if you can design your system to "cope" with this long lock acquire time, you'll probably be okay for the most part... remember, this won't work... it'll just work a lot of the time. If what you want cannot be done, then you might as well start looking at better ways of keeping it hopeful. or (not elegant) readA->fail writeID->a readB->fail readA->fail if not me writeID->b readC->fail readB->fail if not me readA->fail if not me writeID->c readB->fail if not me readA->fail if not me readC->fail if not me writeAllOverSomewhere which for the most part will work... kind of. but its gonna get ugly when things do collide... -- fabs(); |
From: Richard F. <ra...@de...> - 2006-05-30 09:47:42
|
One last thing: you could do it if you were using files (in case you are) as long as you support append. -- fabs(); |
From: Carsten O. <car...@se...> - 2006-05-30 10:28:07
|
You're right in stating that sometimes nobody gets the lock, but that is fine with me. Since practice beats theory, I simple tested this algo: bool Lock(int id) { /*1*/ if(lockA!=3D0){return false;}; /*2*/ if(lockB!=3D0){return false;}; /*3*/ lockA=3Did; /*4*/ if(lockB!=3D0){return lockA=3D0;false;}; /*5*/ if(lockA!=3Did){return false;}; /*6*/ lockB=3Did; /*7*/ if(lockA!=3Did){lockB=3D0;false;}; /*8*/ if(lockB!=3Did){lockA=3D0;lockB=3D0;return false;}; /*9*/ return true; }; and it works for all permutations of execution order for 2 and 3 clients. Since this is basically a 3-phase locking, 4 clients are the really interesting case. I'll see what that results in. Carsten Orthbandt Founder + Development Director SEK SpieleEntwicklungsKombinat GmbH http://www.sek-ost.de Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt =20 > -----Original Message----- > From: gda...@li...=20 > [mailto:gda...@li...] On=20 > Behalf Of Philip Taylor > Sent: Tuesday, May 30, 2006 11:35 AM > To: gda...@li... > Subject: Re: [Algorithms] Locking without atomic operations >=20 > Carsten Orthbandt wrote on 30/05/2006 08:59: > > Another attempt, feel free to break it... >=20 > It seems to 'work' (i.e. no more than one person gets the=20 > lock, though=20 > sometimes nobody gets it) if there's only two connections,=20 > assuming each=20 > numbered statement (like the compare-and-conditionally-set=20 > "if(lockB!=3D0){return lockA=3D0;false;}") is atomic. But with three, = you=20 > can get something like: >=20 > #1 #2 #3 lockA lockB > 0 ( ) 0 ( ) 0 ( ) 0 0 > | > 0 ( ) 0 ( ) 1 ( ) 0 0 > | > 0 ( ) 1 ( ) 1 ( ) 0 0 > | > 1 ( ) 1 ( ) 1 ( ) 0 0 > | > 2 ( ) 1 ( ) 1 ( ) 0 0 > | > 3 ( ) 1 ( ) 1 ( ) 1 0 > | > 4 ( ) 1 ( ) 1 ( ) 1 0 > | > 4 ( ) 1 ( ) 2 ( ) 1 0 > | > 5 ( ) 1 ( ) 2 ( ) 1 0 > | > 5 ( ) 1 ( ) 3 ( ) 3 0 > | > 5 ( ) 1 ( ) 4 ( ) 3 0 > | > 5 ( ) 1 ( ) 5 ( ) 3 0 > | > 5 ( ) 2 ( ) 5 ( ) 3 0 > | > 5 ( ) 2 ( ) 6 ( ) 3 3 > | > 5 ( ) 2 ( ) 7 ( ) 3 3 > | > 5 ( ) 3 ( ) 7 ( ) 2 3 > | > 5 ( ) 3 ( ) 8 ( ) 2 3 > | > 6 ( ) 3 ( ) 8 ( ) 2 1 > | > 6 ( ) 3 ( ) 9 (t) 2 1 > | > 7 (f) 3 ( ) 9 (t) 2 0 > | > 7 (f) 4 ( ) 9 (t) 2 0 > | > 7 (f) 5 ( ) 9 (t) 2 0 > | > 7 (f) 6 ( ) 9 (t) 2 2 > | > 7 (f) 7 ( ) 9 (t) 2 2 > | > 7 (f) 8 ( ) 9 (t) 2 2 > | > 7 (f) 9 (t) 9 (t) 2 2 >=20 > so now #2 and #3 both have the lock (unless I made a mistake=20 > somewhere).=20 > About 1 in 3,000 random orderings has that problem. >=20 > > int lockA=3D0; > > int lockB=3D0; > >=20 > > bool Lock(int id) > > { > > /*1*/ if(lockA!=3D0){return false;}; > > /*2*/ if(lockB!=3D0){return false;}; > > /*3*/ lockA=3Did; > > /*4*/ if(lockB!=3D0){return lockA=3D0;false;}; > > /*5*/ if(lockA!=3Did){return false;}; > > /*6*/ lockB=3Did; > > /*7*/ if(lockA!=3Did){lockB=3D0;false;}; > > /*8*/ if(lockB!=3Did){lockA=3D0;lockB=3D0;return false;}; > > /*9*/ return true; > > }; >=20 > --=20 > Philip Taylor > ph...@za... >=20 >=20 > ------------------------------------------------------- > All the advantages of Linux Managed Hosting--Without the Cost=20 > and Risk! > Fully trained technicians. The highest number of Red Hat=20 > certifications in > the hosting industry. Fanatical Support. Click to learn more > http://sel.as-us.falkag.net/sel?cmd=3Dlnk&kid=3D107521&bid=3D248729& > dat=3D121642 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 >=20 |