<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=iso-8859-15">
<META content="MSHTML 6.00.6002.18100" name=GENERATOR></HEAD>
<BODY style="MARGIN: 4px 4px 1px; FONT: 10pt Microsoft Sans Serif">
<DIV>Some time ago we had a discussion about needing some tests for threading and MUTEX.</DIV>
<DIV> </DIV>
<DIV>Jay Krell later referenced an online book titled "The Little Book of Semaphores".</DIV>
<DIV> </DIV>
<DIV>I've attached a program to this email that is a variation of the problem presented in Section 8.1 of this book.</DIV>
<DIV> </DIV>
<DIV>You might try running it on various platforms to see if a problem is detected.</DIV>
<DIV> </DIV>
<DIV>The program takes 3 inputs:</DIV>
<DIV> </DIV>
<DIV>1 = The number of Threads that should be created.</DIV>
<DIV> </DIV>
<DIV>2 = The maximum count, i.e., the number of shared counter variables to be created.</DIV>
<DIV> </DIV>
<DIV>3 = Whether to use MUTEX protection for concurrency control.</DIV>
<DIV> </DIV>
<DIV>For example, on Windows Vista with the following inputs, I get the results shown below:</DIV>
<DIV> </DIV>
<DIV>(1001, 1000000, 0) = FAIL (as expected), histogram = (0:32), (1:999943), (2:25)</DIV>
<DIV> </DIV>
<DIV>(1001. 1000000, 1) = PASS (as expected), histogram = (1:1000000)</DIV>
<DIV> </DIV>
<DIV>Using these inputs, the program took nearly 3 minutes to run on a recent vintage Dell laptop computer.</DIV>
<DIV> </DIV>
<DIV>Just because a particular test run succeeds doesn't mean all is well. Obviously, for small # of threads and/or small maxCount, even the non-MUTEX version will succeed sometimes. But, trying larger numbers will give a more robust test. </DIV>
<DIV> </DIV>
<DIV>If desired, I can try to implement some of the other test programs in the book. Let me know.</DIV>
<DIV> </DIV>
<DIV>Regards,</DIV>
<DIV>Randy Coleburn</DIV>
<DIV> </DIV>
<DIV><FONT face="Courier New">MODULE ThreadTest1 EXPORTS Main;</FONT></DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New">(* This program designed to test if MUTEX working properly using multiple threads.<BR> Author: Randy Coleburn<BR> Inspiration: "The Little Book of Semaphores", by Allen Downey, Section 8.1: Mutex checker problem.<BR> *)</FONT></DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New">IMPORT Fmt, IO, Thread, Time;</FONT></DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New"><*FATAL IO.Error*></FONT></DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New">CONST<BR> ModuleName = "ThreadTest1";<BR> Delay = 0.11d0;</FONT></DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New">TYPE<BR> ChildClosure = Thread.Closure OBJECT<BR> id: CARDINAL;<BR> METHODS<BR> OVERRIDES<BR> apply := ChildApply;<BR> END; (* ChildClosure *)</FONT></DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New"> CounterArray = REF ARRAY OF CARDINAL;</FONT></DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New">VAR<BR> maxCount: CARDINAL := 0;<BR> mutex: MUTEX := NEW(MUTEX);<BR> numThreads: CARDINAL := 10;<BR> sharedArray: CounterArray;<BR> sharedCounter: CARDINAL := 0;<BR> startTime: LONGREAL;<BR> threadSafeMode: BOOLEAN := FALSE;</FONT></DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New">PROCEDURE Print (msg: TEXT;<BR> )<BR> RAISES {} =<BR>(* *)<BR>BEGIN (* Print *)<BR> IO.Put(msg & "\n");<BR>END Print;</FONT></DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New">PROCEDURE ChildApply (self: ChildClosure;<BR> ): REFANY<BR> RAISES {} =<BR>(* *)<BR>CONST Proc = ModuleName & ".ChildApply";<BR>VAR<BR> myID: TEXT := Proc & "( " & Fmt.Int(self.id) & " )";<BR> numLoops: CARDINAL := 0;<BR>BEGIN (* ChildApply *)<BR> Print("Begin " & myID);<BR> IF threadSafeMode<BR> THEN<BR> WHILE sharedCounter < maxCount<BR> DO<BR> LOCK mutex DO<BR> INC(sharedArray[sharedCounter]);<BR> INC(sharedCounter);<BR> END; (* lock *)<BR> INC(numLoops);<BR> Thread.Pause(Delay);<BR> END; (* while *)<BR> ELSE<BR> WHILE sharedCounter < maxCount<BR> DO<BR> INC(sharedArray[sharedCounter]);<BR> INC(sharedCounter);<BR> INC(numLoops);<BR> Thread.Pause(Delay);<BR> END; (* while *)<BR> END; (* if *)<BR> Print("End " & myID & " ran " & Fmt.Int(numLoops) & " times.");<BR> RETURN NIL;<BR>END ChildApply;</FONT></DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New">PROCEDURE PrintHistogram ()<BR> RAISES {} =<BR>(* *)<BR>CONST Proc = ModuleName & ".PrintHistogram";<BR>VAR<BR> count: CounterArray;<BR> error: BOOLEAN := FALSE;<BR>BEGIN (* PrintHistogram *)<BR> Print("Begin" & Proc);<BR> Print("(this make take a few moments when max count is large)\n");<BR> count := NEW(CounterArray, maxCount+1);<BR> FOR i := 0 TO maxCount<BR> DO<BR> count[i] := 0;<BR> END; (* for *)<BR> FOR i := 0 TO (maxCount - 1)<BR> DO<BR> WITH c = sharedArray[i]<BR> DO<BR> IF c > maxCount<BR> THEN<BR> error := TRUE;<BR> Print("!!! Something really broken in CM3 because sharedArray[" & Fmt.Int(i) & "] = " & Fmt.Int(c) & " which is greater than maxCount !!!");<BR> ELSE<BR> INC(count[c]);<BR> END; (* if *)<BR> END; (* with *)<BR> END; (* for *)<BR> FOR n := 0 TO maxCount<BR> DO<BR> WITH total = count[n]<BR> DO<BR> IF total > 0<BR> THEN<BR> Print("(" & Fmt.Int(n) & ": " & Fmt.Int(total) & ")");<BR> END; (* if *)<BR> IF (n # 1) AND (total # 0)<BR> THEN<BR> error := TRUE;<BR> ELSIF (n = 1) AND (total # maxCount)<BR> THEN<BR> error := TRUE;<BR> END; (* if *)<BR> END; (* with *)<BR> END; (* for *)<BR> IF error<BR> THEN<BR> Print("\n! ERROR DETECTED !");<BR> ELSE<BR> Print("\n! TEST PASSED !");<BR> END; (* if *)<BR> IF error AND threadSafeMode<BR> THEN<BR> Print("\n!!! Something is broken in the CM3 system and needs to be fixed !!!");<BR> ELSIF (NOT threadSafeMode)<BR> THEN<BR> IF error<BR> THEN<BR> Print("\nNote that errors are expected when not using concurrency control.");<BR> ELSE<BR> Print("\nYou got lucky because the test should fail when not using concurrency control.\nTry again with more threads and/or a greater max count.");<BR> END; (* if *)<BR> END; (* if *)<BR> Print("\nEnd" & Proc);<BR>END PrintHistogram;</FONT></DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New">VAR<BR> answer: INTEGER;<BR>BEGIN (* ThreadTest1 *)<BR> Print("-------------------------------------------------------------------------------");<BR> Print("Module " & ModuleName);<BR> Print("-------------------------------------------------------------------------------");<BR> Print("This program designed to test if MUTEX working properly using multiple threads.");<BR> Print("Author: Randy Coleburn");<BR> Print("Inspiration: \"The Little Book of Semaphores\", by Allen Downey");<BR> Print(" Section 8.1: Mutex checker problem.");<BR> Print(" </FONT><A href="http://www.greenteapress.com/semaphores/"><FONT face="Courier New">http://www.greenteapress.com/semaphores/</FONT></A><FONT face="Courier New">");<BR> Print("-------------------------------------------------------------------------------\n");</FONT></DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New"> REPEAT<BR> IO.Put("Enter # of threads [0.." & Fmt.Int(LAST(CARDINAL)) & "]: ");<BR> answer := IO.GetInt();<BR> UNTIL answer >= 0;<BR> numThreads := answer;</FONT></DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New"> REPEAT<BR> IO.Put("Enter max count [10.." & Fmt.Int(LAST(CARDINAL)-1) & "]: ");<BR> answer := IO.GetInt();<BR> UNTIL (answer >= 10) AND (answer < LAST(CARDINAL));<BR> maxCount := answer;</FONT></DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New"> REPEAT<BR> IO.Put("Run in thread-safe mode [0=false, 1=true]: ");<BR> answer := IO.GetInt();<BR> UNTIL (answer = 0) OR (answer = 1);<BR> threadSafeMode := (answer = 1);</FONT></DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New"> sharedArray := NEW(CounterArray, maxCount);<BR> FOR i := 0 TO (maxCount - 1)<BR> DO<BR> sharedArray[i] := 0;<BR> END; (* for *)</FONT></DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New"> Print("\n-------------------------------------------------------------------------------");<BR> Print("Ready to start " & Fmt.Int(numThreads) & " threads incrementing " & Fmt.Int(maxCount) & " shared counters");<BR> IF threadSafeMode<BR> THEN<BR> Print(" using mutual exclusion semaphore for concurrency control.");<BR> Print(" Expected Result = Test Passed with no errors.");<BR> ELSE<BR> Print(" without using any concurrency controls.");<BR> Print(" Expected Result = Test Fails with errors.");<BR> END; (* if *)<BR> Print("Expected runtime = " & Fmt.Int(ROUND(FLOAT(maxCount, LONGREAL) * Delay / FLOAT(numThreads, LONGREAL) / 60.0d0) + 1) & " minutes.");<BR> Print("-------------------------------------------------------------------------------");<BR> Print("---Press ENTER to begin---");<BR> EVAL IO.GetLine();<BR> EVAL IO.GetLine();<BR> startTime := Time.Now();</FONT></DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New"> VAR child := NEW(REF ARRAY OF Thread.T, numThreads);<BR> BEGIN (* block *)<BR> FOR i := 1 TO numThreads<BR> DO<BR> child[i-1] := Thread.Fork(NEW(ChildClosure, id := i));<BR> END; (* for *)<BR> FOR i := 1 TO numThreads<BR> DO<BR> EVAL Thread.Join(child[i-1]);<BR> END; (* for *)<BR> END; (* block *)</FONT></DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New"> Print("-------------------------------------------------------------------------------");<BR> Print("All threads finished. Run time = " & Fmt.LongReal((Time.Now()-startTime)/60.0d0) & " minutes.");<BR> Print("Result should be a total of " & Fmt.Int(maxCount) & " ones.\nSee histogram below.\n");<BR> PrintHistogram();<BR>END ThreadTest1.<BR></FONT></DIV></BODY></HTML>