Saturday, September 18, 2010

FIFO reader/writer lock (my take

A simple counting-semaphore-based reader/writer lock is unfair.

I proposed long ago that we initialize a large number (2000+, up to max long integer) of permits for each lock instance, and require the writer to block to acquire all the permits in one go. As stated on P89 [[Pthreads programming]], such a design is unfair to writer, as a troop of readers can circulate a token among themselves, A passing to B, passing to C, passing to D ... and the writer will wait forever even if it arrives on the scene just after A, and before B, C, D... Note the token is not a permit or a lock, just some object represent a "turn". When Reader Thread A leaves the scene, A releases the Permit, but only After B takes up another Permit. At any moment in time, there's some permit owned by the readers. The writer is starved unfairly.

One idea is incremental acquisition by writer, who acquires all the free permits ASAP, and waits to grab A's permit. I feel this is susceptible to deadlock. It also (fairly or unfairly) disables the "shared read" functionality.

A more fair design puts the candidates into some kind of FIFO queue, perhaps a simple linked list. This tentative design uses 2 condition variables (and 2 associated locks). Whenever the RW lock becomes completely free (all permits freed), a signal is sent by the last returning thread, on the rw_free condition. In contrast to the simple design, there's only one (special) waiting thread on that condition -- a messenger thread, who wakes up and then notifies the first thread in the queue, before going back to wait(). In fact, all the queue threads (to be capped at 200) are waiting on the same queue condition, but only the FIFO queue-head thread is allowed to proceed, while others re-enter wait().

A new reader candidate joins the queue if any, otherwise grabs a permit and proceeds.

A new writer candidate joins the queue if any, otherwise determines if lock is completely free. If not free, then it starts the queue. Queue can be started by writer only.

Once a writer leaves the queue, does its job and frees all permits, all the readers before the next writer proceeds to leave the queue.

The queue holds Nodes, each having a pointer to a thread handle -- a java Thread instance or a thread id in C. Any thread returning from wait() would check the queue to see if its own thread handle equals the queue-head's thread handle.

(A tentative design.)

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