Subj : Re: double-checked locking in C To : comp.programming.threads From : Joe Seigh Date : Sat Jul 09 2005 10:46 am David Schwartz wrote: > "Joe Seigh" wrote in message > news:H66dnUWQYrM5l1LfRVn-gg@comcast.com... > > >>> We are talking about one case where you have a test suite compared to >>>a case where you don't. You are seriously arguing that an implementation >>>test suite is no help at all in making sure an implementation correctly >>>supports a standard? Is that really your position? > > >>I'm not sure where you're going here. What do you mean by similar? >>Exactly the same? How much of a difference is allowed before different >>results are allowed? > > > By similar I mean that you don't do anything that requires some > guarantee that isn't tested by the test suite. For example, the test suite > will likely test that variable modified by one thread holding a particular > lock is seen correctly by another thread that tests it under that same lock. > It probably won't test with different locks. So the probability of your code > continuing to work is greater if it too uses the same locks. Ah, the unstated guarantees. I was thinking more in line with the commonly accepted usage patterns. > > >>That raises an iteresting issue. If I come up with a new form of >>synchronization >>but don't provide any formal definition (which is a valid point of >>contention) >>can I come up with a set of testcases and say that if they run it proves >>the >>implementation is correct? For programs which are similar to the >>testcases that is. >>Just curious. There's other people besides me that would be interested in >>the >>answer here. > > > This question is mostly just about what it means for something to be > "correct". If you call something a "mutex" and provide no definition, people > will still rationally expect it to provide mutual exclusion. You could > define "correct" as "passing the test cases"; however, if the test cases are > developed at the same time as the new form of synchronization, an > implementation that simply tested for the test cases and recited the correct > answer by rote would be "correct". > > I would argue that the test cases and the implementation must both be > aiming at some particular effect. That effect may or may not be well > documented (obviously, it's better if it is), but the implementation and the > test cases are both correct if they provide, and test for, that desired > effect. > I think it might be useful to compare pthreads and Java at this point. While both pthreads and Java probably have a compliance test suite, the difference is that Java has a formal definition that can be used during the implementation. So when deciding whether a certain JVM is suitable you have not only the compliance testcase results but some degree of confidence based on how competent you think the jvm implementors are in formal methodology. Whereas with posix it all depends on their understanding of the unstated posix semantics. Do you think everyone *here* has your exact same understanding of mutex semantics? Case in point. Not really pthreads but good example. Take atomic access of ints. The Linux kernel uses it. Some of use use it. The compliance testcase is to look at the code generated by updating C int variables. If it appears to be ok in those cases then it must be ok in all cases. With the complexity of compilers, you would think that making generalizations like that would be somewhat risky. But apparently not everyone thinks that way. And this is for extremely simple observable behavior. Imagine what it's like for situations where extremely subtle problems can occur, like race conditions. You can have a race condition that are all but impossible to detect with testcases. Now take DCL (the OT. surprise!). The problem is that apparently so far, no one has formally defined it (is is a valid synchronization technique after all). Without that, you can't demand that someone show formally that their implementation works. All they have to do is tell you that they're run their DCL compliance testcase a zillion times and it appears to work. And they can ignore all your examples of how things *could* go wrong much to your and everyone else's exasperation. -- Joe Seigh When you get lemons, you make lemonade. When you get hardware, you make software. .