Friday, August 13, 2010

compareAndSet by 2 competing threads -- probably safe


static boolean unsynchronizedSetter(Date expected){
Date newDate = new Date();
AtomicReference<Date> myAtomicReference = Lookup.getAtomicRef();
boolean myStatus = myAtomicReference.compareAndSet(expected, newDate); //CAS
return myStatus;
}

Q: If 2 threads execute the CAS simultaneously, which object will get stored in the atomic reference?

In a multi-processor machine, 2 threads could be performing the CAS in the same clock cycle. Suppose they both use the same myAtomicReference object to do the CAS, both use the correct value of "expected", but they try to put in 2 distinct objects ie the 2 newDate. One of them must fail, but will myStatus be false in that thread?

I feel it's ok if both threads get myStatus==true, in the same clock cycle or not. Right after the CAS clock cycle, the atomic reference holds one of the 2 values. But how many clock cycles later will the subsequent myStatus-dependent statement execute? No guarantee. Therefore when it does execute, the atomic reference could hold any value. myStatus==true doesn't mean "my value was stored".

We must also consider statement reorder and per-thread caching, as described by Doug Lea.

I guess one hardware implementation of CompareAndSwap might make the 2 threads queue up to do their updates. I guess even if the 2 processors are executing the CAS instruction in the same clock cycle, one of them is probably delayed.

In general, Simultaneous writes aren’t allowed by the memory module -- just consider voltage signal in that write cycle. We won't go into details but input voltage applied to a particular bit in RAM must be either 0 or 1, not both. This is the original meaning of electronic race-condition. Some links --

http://eom.springer.de/p/p120050.htm

http://stackoverflow.com/questions/516940/can-multiple-cpus-simultaneously-write-to-the-same-ram-location

No comments:

Total Pageviews

my favorite topics (labels)

_fuxi (302) _misLabel (13) _orig? (3) _rm (2) _vague (2) clarified (58) cpp (39) cpp_const (22) cpp_real (76) cpp/java/c# (101) cppBig4 (54) cppSmartPtr (35) cppSTL (33) cppSTL_itr (27) cppSTL_real (26) cppTemplate (28) creditMkt (14) db (65) db_sybase (43) deepUnder (31) dotnet (20) ECN (27) econ/bank` (36) fin/sys_misc (43) finGreek (34) finReal (45) finRisk (30) finTechDesign (46) finTechMisc (32) finVol (66) FixedIncom (28) fMath (7) fMathOption (33) fMathStoch (67) forex (39) gr8IV_Q (46) GTD_skill (15) GUI_event (30) inMemDB (42) intuit_math (41) intuitFinance (57) javaMisc (68) javaServerSide (13) lambda/delegate (22) marketData (28) math (10) mathStat (55) memIssue (8) memMgmt (66) metaProgram` (6) OO_Design (84) original_content (749) polymorphic/vptr (40) productive (21) ptr/ref (48) py (28) reflect (8) script`/unix (82) socket/stream (39) subquery/join (30) subvert (13) swing/wpf (9) sysProgram` (16) thread (164) thread_CAS (15) thread_cpp (28) Thread* (22) timeSaver (80) transactional (23) tune (24) tuneDB (40) tuneLatency (30) z_ajax (9) z_algoDataStruct (41) z_arch (26) z_arch_job (27) z_automateTest (17) z_autoTrad` (19) z_bestPractice (39) z_bold (83) z_bondMath (35) z_book (18) z_boost (19) z_byRef^Val (32) z_c#GUI (43) z_c#misc (80) z_cast/convert (28) z_container (67) z_cStr/arr (39) z_Favorite* (8) z_FIX (15) z_forex (48) z_fwd_Deal (18) z_gz=job (33) z_gzBig20 (13) z_gzMgr (13) z_gzPain (20) z_gzThreat (19) z_hib (19) z_IDE (52) z_ikm (5) z_IR_misc (36) z_IRS (26) z_javaWeb (28) z_jdbc (10) z_jobFinTech (46) z_jobHunt (20) z_jobRealXp (10) z_jobStrength (15) z_jobUS^asia (27) z_letter (42) z_linq (10) z_memberHid` (11) z_MOM (54) z_nestedClass (5) z_oq (24) z_PCP (12) z_pearl (1) z_php (20) z_prodSupport (7) z_py (31) z_quant (14) z_regex (8) z_rv (38) z_skillist (48) z_slic`Problem (6) z_SOA (14) z_spring (25) z_src_code (8) z_swingMisc (50) z_swingTable (26) z_unpublish (2) z_VBA/Excel (8) z_windoz (17) z_wpfCommand (9)

About Me

New York (Time Square), NY, United States
http://www.linkedin.com/in/tanbin