[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: It's been quiet for a while...



> ...so here is an item for discussion.

The code looks dodgy to me?  For one thing, they break one of Doug Lea's
golden rules never to `wait' inside an `if' but always in a `while':

  public syncronized void readLock() ...
    ...
      if ( allowReadLock() == false) {
        wait ();
      }
      // Bingo! Switch from a waiting lock to an active lock
      activeReadLocks++;
    ...
  }

Alas, because of the semantics of Java's `notify', we can't assume that
`allowReadLock' will now be true simply because some notifying thread
made it so and notified us ... it has to be done in a `while' loop.

The JavaPP channel algorithms also break Doug's rule ... but we know it's
safe for us ;-)

But I haven't got to grips with this code yet!  As we know with this problem,
four interdependent monitor methods are horrible to try and understand ...
so maybe it's OK ...

But it sure looks like there's a hole here ... everyone gets notified in
`writeUnlock' evry time ... not only when `activeWriteLocks' reaches zero
... and what about `waitingWriteLocks' ... surely that `if' has to be
a `while' ... ?!!

Anyway, notifying everyone every time a write goes away is awfully
inefficient ...

>From the documentation, waiting writers have precedence over readers ...
OK ... but it looks like a couple of slow writers could forever starve
readers from getting the lock ... as the writers alternately wait for
each other to finish writing ... always having found something else
to write before the other writer finishes.

Hoare's algorithm from his 1975 CACM paper and the one I presented in
the spare slot at WoTUG-21 guarantee fair service to readers and writers
... with neither being able to block the other indefinitely.

Enclosed is a uuencoded gzipped tar file containing:

  CrewServer.java:  a (JCSP) process with a channel interface implementing
		    the WoTUG-21 algorithm (which is trivial to prove correct)
  
  TestCrew.java:    a demonstration program using a CrewServer.

  Crew.java:        an ADT wrapper for CrewServer that has the same API as
		    Hoare's original code (and the JServLock - apart from
		    the timeouts).

  TestCrew2.java:   the same demonstration program as before but using 
		    a Crew object rather than the CrewServer process.

Feedback welcome ... you have to have the `jcspclasses.jar' file to use
the above ...

Cheers,

Peter.

(cut here)
-----------------------------------------------------------------------------
begin 644 crew.gz
M'XL("`@G+C8``V-R97<`[1M=<]LV,L_^%;B\1*IE69)E9R:Z/*1.9BYW3=-Q
M/-.'3":!2-AB3)$J05JGN/KOM[L`20`D1=F-DLM4F-9N\;'8;^P'?9Z(9?\S
MO^6/=C<&P\'@;#Q^-!B,GP['I_![<'IR1K]QC(9G)X\&9V?#D_'PZ?@4]PU'
M)^/!H\$.<2I&)E.>P)6+V7+C/B]+-JX3*8@T4C0>?DT4=SF.C^_N[M;K]<%!
M,%_$2<H^>W+1#WETW?]I4IT+HE3BPL$BFX:!Q[R02\G.08G8W<$!8XLDN.6I
M8%=!Q$/VAD>KT=M(G,]X%(GP=92R1/R1"9E.*GMAF[-UF02I2,[C*$WBL'J@
M%CCW17(A0L&EF"`^1!Z<5-@2GITNH%H[Q7+LV',6P73-#9WNA#9:N.GM50KR
MW19>[<!Q^;<D]H24OXIT&2<WK$,+:@E1?B>26Y&PCD:X9R/4LV_LTN%N'S4]
MOV5-S"'!NURZC0.?T=X+@.+PJWZ1L>"J0(;]`RC,PK";L[-/R+%.B7C_XM6+
MEZ\N-+WFV>?YV7<KF8IY/\[2/L@]2L.(=1X7%S]CSH''6U$E(K^))F?)$5I.
MPF![YOVN3C1PSUIE&SCU^\7KRX)3EI0-G%@YCH_9D@<INXH3QL.0@=]*1&$;
MDJ4QVD\@9]NQJY$*=ZT9.?NB]<'W=GG[80Q#TW86!;2\_^.G^&RJ]W]P.L0G
M='AR.ASOW_]O,![Z_I</OWZ*8&LHYN!I8/:=?KUT3*"\!O`YA5_J\08X3+T!
M\!P.)AMV*?\'NX:3:H#Q(DR#Z+IX0A=9NC'&<#>V1!A-T-N#C(_Y^ZP/?XP^
M#EGQ5N>30YA4*'ST],-M!R8YE"V([1VPNK$%W1M/;L&"W/VGLT#VRP#*$()>
M<V.F"O<+&':TY#"\_=E*LJCNQ3*F&:E6=*'?1*V"K)[<]Q^8!UON+#QZ.8'K
MXJ1((M#=6X$<XF$>1#H+10`Y"T)X'M,D*QC(F%P&J3=C'3C=EW"/!_N];KE>
M4&NA4BQZR*_!,W97E29$!>K,Q\0YY`8ZB0J")L:&G$]'1^9L;8"FE@X/#S54
M'6L(']<.ZS6M<@\[9(\96(03NG0?6UA-8?JFG%@;/$+5J'",I&7S:MC,*WMW
M*9H\4--L,F5CW*9<F[5"%ZKY9\ZADO+#PXFSLAV7*:0$S=V&R^9]VW$:A\-M
M'&N'<I/K!B^4`Z_R0LU7>4&6B<:C<;PG1Y17H1AXIPS!^+J#N`;D/N#7/UD$
MOPX/79W`T6IC-AJVI6U%]P/L[:&DKQNTM_2C6V.MI57J;Q1ON-C.,'(NTA(8
M;2A2"Q[]#P"]%Y`B=]*0BG2I`=IV])52V4#?9GM:MW@Z]7M]WV3K$IS9^8YK
M@)OC_^'XY&2<Q__CT[.G%/^/!J?[^/\;C(?&_]JYG[]]\^;5KY?,C[T,@W^(
M<^((%O_$?]DEA',04\?7"9\S.8N7$B(\P3+P_O$5XZKX=IWQQ`]XA*:FPV#3
M#7$/,PD"!QLX@.$)&%(B9)PEGGC&YAD$;9![N+Y+,MB()9!X*?P>FV:E0T!@
M@!G`2`(O!6@*,BP!F(7.73C<S=)@+OH&/<*]'^%PMH!D"`(\%D\_8]`&L<*,
M725"$"+'JA2B"&%'1RSH*Y@,G,$GN8J\61)'P1?A/V%SD<YB0+T#\2&$&\LX
M"WW`2-PB52Z!W3YC_P+J($?H$3R-NI#`%`C"05@BX8`/S"]$$JX48B@"F_-3
M`1X/,(Q\QJ_@#`'#*X`CQYII=,PAWN:,#1/Y$@'1&/@6/*7[%6DEKE*(&WT!
MP7(Y3+1X\7R>18$'V1E0?:%P(XQS_$J`*/<K'@#!!`\"M@S@Q5$IXS"(@%S2
MQA6;\QM0'E`4*HX%D,`2XZZXAU>]!>ZF_,90&S0*$/<T5!R3D*0%2A&0>`YG
MT='+F(4QHBA1S$'D![>!GT%*12].K'BL-`.%0X8C&635]/R@3+LE>U]'E!HQ
M7\QA5ZIV]Q#]1&O@>1R&XIJ,0`:2&`(F-ARPWR#1B&6\@*U2:0EGTY![-],8
M)*5D[H@.GS\40BYU8_M4I$LAHD)6)G1@%JJ!.:5,T-(!(7NY:IGB4P8^$T'"
M`O\HRN93.AZ&+,84V$$##]X(L4`@&<H+4)X#U\'%D$P5G7#WM4B)%QQEH1&T
MB>4A2`I5`/T!>CN9LYV\HO9SJMR!I#45.MIW%!'Q`?VST8/B,OUXQ<%6#):R
M&2?#^A2`MU!L8M?`3XI5(&]E7T02`Z&6%.1"1#Z!4QQ&KU8(X2J)YSVF(QX2
M>=RS=03@ID]D;I=:!7)P<[B,D-1Z[>HT2XFWA*\4H)X^F1DLH\R42`A6KG&@
MMHZT0<'G/.+7>/D*4/N$$GQ2BE!KED:$@)D<X^&2KZ1^$QS0@!^:VHIY*R\D
M<X<)I`;P/1P^214T6NRI!1LRZ`[1*\EO$)'<2\`].!?U2XG:]H$0E-Z!7X0G
MASP2:JX?4SR,#+7FE^!@E)1@2U=)(5;..06S(**R=`'Q:'FEBA*-8@FX*7AI
M``$U;9>]**GQ)PU+[S\89#F;=.'D+=W?4(FK[&DLPM5`<PI!M<1YY"$S+P4?
M6Q2`R"X[)GV]!I(JY3"KA%8A;=OMFTMNC7<TU=D"'Y(M)20]8RCU<T="WZ<V
M9\HDR:*V8ESN&Y[#HS70:23.D^V5F:4&F">,!XTY&.:_K*.7=-AT"7[O31"&
M@>QTC_&:+B:]W4V9\F.E.@@,L,84F3TKT]5^O\_R-*Y,QFIK>T;E[H@?T19[
M1?(5&3=:-N[2J[LDKH$\$PN+1#OC;._N4D8=^(!<<+4"MY1($=YB@(81BU4C
M,WD@R,_IY^G[<:$0<CLG#-E2\(1-7J7.>D,*+\S=Y0PW]&4(@0OK!/Y/>D]W
MLH;PDZJ+KS'P3+(%Y"2O_NN)!3V@J$3KYEN)9_A$`.-F_%9L4IX=V\7/O[PX
M_\_/;U]<O`2#+5E55RHSGL901-?IK%(ZJ^)>GGD??*`[RSO6FQ2E48'K._PF
MG50,5L^S9F]1R[$UU`2,'S1HOX5>VJ3*<6>&'.E^QS74.@?:V,@FHP#5-%I+
M@U_#IEI\B^*V;5)NT:O]HXB-#L8I/&_Q[<2]/IZHRD<Y+K=.^(,)R'1[VPC)
MU%X,IRGN11LM=CS,_!FSS;T,=W"T='L4-K6N^"LZXX;+*PX9L4DI8U*CQBMO
M$E.K/NSL"6SPYP\7Z?U\NBGF-K_NRF)+:V_R[:X16Y5V)D((?AV?7K;NZBKQ
M1JZRKBTMY'7XHI)@3!RX7T=0!#WG`?#@74I),T^N;]]_R)E=UAGTCS+QB:ST
M$X/M,M0N9?$N^(*/U.FD!.'F2;J]C=/VN0_&H>8/0-N_@FSY(+3UH\NV[T/;
M,:`?QG<87OF?SQ_X):8!&`4!'%V@V2EP-&,)R.1E;</1W.S8&P)6CC.'#<?!
MPH:]3=FN,>Y#T;K$DV[C"3R?(K2_6\UK84"U83P%#TM<;!!(2->RK6Y?I8\&
M=W(SHZ:7-K!]_:>]_I.[F=$.&X`M_;_1V;#H_YV>G)ZH_M_9_OO_;S$V]__V
M;;Y]F^_^;;Y<"GRQ`"C9`C`TF/?BY:623-YD8QV90KC:S*8NO7WPVJQ0IZAE
MH)MMB$(N9D0F0A_H:;7K_!M>G"X+@VG"T<-C6(6O5R8Y]NX0J0A\ZF(18EM1
M*S0U.^`!$KYRZ3<!<`O`:97=]Q[WO<?OUWL<M3<?&[?LNX^[[3[V<H='X+33
MB]#;629=X>CFZ)2`;8Y0V7VB4X+W8T6HS>W)]MZD\_D_&A_F&Y/:.QL;AZ,M
M.X?N-7^Y8X=`8"U'>=];^]OTUE#D??//+"<U!.T;9?M&62WN7[M11MI8_H%L
MW99]RPO'7VYYE7:?_W%MA6G[5M.^U;1O-?T?M9IR[UAGL=^H:S2JM(U&/VK?
MJ(B>C1Z+7>JGD+S:.1GMLG4RJNN=J""_I0%"W8OM^A7?NQ:\'_NQ'W^O\3_[
'E=GK`$P``.JG
`
end