Thursday, November 4, 2010

break the 4 deadlock conditions

My long-time java friend told me lock ordering and lock timeout are the 2 standard solutions, but here are additional suggestions directly or indirectly addressing deadlocks.

("[top x]" means one of my favorite x  techniques.)

For want of a better word, "stuck" is my general term meaning "no-progress" and includes
- lock grab,
- Object.wait(), waking up and grabbing lock
- join(),
- socket accept(),
- long sleep(),
- endless loop,
- unbounded *recursion*

Now the solutions.
--to provide preemption
* [top 3] remain interruptible while getting "stuck"
** even if a recursion/loop calls no blocking method, the thread can still check for the interrupt status from time to time and exit if necessary. see http://download.oracle.com/javase/tutorial/essential/concurrency/interrupt.html
* tryInterruptibly(). Now, if thread 1 knows another thread is holding a mutex it can forcibly grab it, but how does it know which thread? --to break incremental acquisition

*[top 2] have a timeout while getting "stuck" -- a wide-spread implementation
** example -- in an endless loop, check how long we have been stuck and exit if necessary.
** example -- lock timeout -- A thread tries to acquire a lock in a specified period. Upon timeout, it release all it's locks and go to wait status for a period. For example, release 1st chopstick if 2nd chopstick remains unavailable for x seconds. Achievable with tryLock()? Yes P279 [[ java concurrency in practice ]] I believe tryLock() can tell u the 2nd chopstick is unavailable and give you a chance to give up 1st chopstick held.
* open call? impractical

--to break circular wait
* lockInterruptibly() of the Lock interface. It let's u try to acquire a lock and remain responsive to interruption.
* reentrant/recursive lock. By default pthreads locks aren't so a single thread can deadlock itself.
* tryLock()
* [top 2] globally fixed resource acquisition order
* if you identify that 3 threads form a wait-for circle, then reverse one of the threads' acquisition order
* finally() to release lock if using Lock objects. "synchronized" doesn't need this.
* Release locks asap. minimize lock scope.
* [top 5] Make all methods finite. Avoid using locks while inside infinite loops or unbounded recursions.

--to break the need for mutex resources
* immutables. no need to lock anything to access them. CopyOnWrite is thread safe because it's immutable.
* ThreadLocal
* copy On Write
* copy the data for each thread, and sync up later
* replacing sync with atomic variables? both options can be criticized as risky

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