Wednesday, September 8, 2010

FIFO reader/writer lock from a java book (multiprocessor)

A design adapted from P186 [[art of multiprocessor programming]]. I found a few bugs in the original. The http://www.elsevierdirect.com/companions/9780123705914/exercises/05~Chapter_08.zip site actually confirmed my suspicions.

However, I don't know how to test it.

My Adaptations
- await() before readAcquires++.
- perhaps multiple condition objects for different conditions.

Basic ideas --
* Use a private lock (plock) to guard the counters this.readAcquires and this.readReleases, which are updated by readers.
* (first) writer thread if unsuccessful would set flag this.writerIsPending
** subsequent readers block in while(writerIsPending){cond.await(); }before readAcquires++.
** subsequent writers block in while(wlockAcquired){cond.await(); }
** both block in await() rather than busy waiting
* invariant : readReleases <= readAcquires
* how many conditions? 1


/* Created on January 9, 2006, 7:39 PM
 *
 * From "Multiprocessor Synchronization and Concurrent Data Structures",
 * by Maurice Herlihy and Nir Shavit.
 *
 * Modified ...
 */
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantLock;

public class FifoReadWriteLock implements ReadWriteLock {
private int readAcquires = 0; // read acquires since start
private int readReleases = 0; // read releses since start
private boolean writerPendingOrRunning = false; // writer present?
private final Lock lock = new ReentrantLock(); // short-term synchronization
// one condition for multiple purposes?
private final Condition cond = lock.newCondition();
private final Lock rLock = new ReadLock(); // readers apply here
private final Lock wLock = new WriteLock(); // writers apply here
@Override
public Lock readLock() {
return rLock;
}
@Override
public Lock writeLock() {
return wLock;
}
private class ReadLock extends AbstractLock {
public void lock() {
lock.lock();
try {
while (writerPendingOrRunning)
try {
cond.await();
} catch (InterruptedException ex) {
}
readAcquires++;
} finally {
lock.unlock();
}
}
public void unlock() {
lock.lock();
try {
readReleases++;
if (readAcquires == readReleases)
cond.signalAll();
} finally {
lock.unlock();
}
}
}
private class WriteLock extends AbstractLock {
public void lock() {
lock.lock();
try {
while (writerPendingOrRunning)
try {
cond.await();
} catch (InterruptedException ex) {
}

writerPendingOrRunning = true;

while (readAcquires != readReleases)
try {
cond.await();
} catch (InterruptedException ex) {
}
} finally {
lock.unlock();
}
}
public void unlock() {
writerPendingOrRunning = false;
cond.signalAll();
}
}
}
abstract class AbstractLock implements Lock {
public void lockInterruptibly() throws InterruptedException {
throw new UnsupportedOperationException();
}
public boolean tryLock() {
throw new UnsupportedOperationException();
}
public boolean tryLock(long time, TimeUnit unit)
throws InterruptedException {
throw new UnsupportedOperationException();
}
public Condition newCondition() {
throw new UnsupportedOperationException();
}
}

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