FIFO semaphore test

问题:

I have implemented FIFO semaphores but now I need a way to test/prove that they are working properly. A simple test would be to create some threads that try to wait on a semaphore and then print a message with a number and if the numbers are in order it should be FIFO, but this is not good enough to prove it because that order could have occurred by chance. Thus, I need a better way of testing it.
If necessary locks or condition variables can be used too.
Thanks

回答1:

What you describe with your sentence "but this is not good enough to prove it because that order could have occurred by chance" is somehow a known dilema.

1) Even if you have a specification, you can not ensure that the specification match your intention. To illustrate this I will take an example from "the limit of correctness". Let's consider a specification for a factorization function that is:

Compute A and B such as A * B = C

But it's not enough as you could have an implementation that returns A=1 and B=C. Adding A,B != 1 can still lead to A=-1 and B=-C, so the only correct specification must state A,B>1. That's just to illustrate how complicated it can be to write a specification that match the real intention.

2) Even having proved an algorithm, still doesn't mean the implementation is correct in practice. This is best illustrated with this quote from Donald Knuth:

Beware of bugs in the above code; I have only proved it correct, not tried it.

3) Testing can only reveal the presence of bug, not their absence. This quote goes back to Dijkstra:

Testing can be used to show the presence of bugs but never to show their absence.

Conclusion: you are doomed and you will never be 100% sure that your code is correct according to its intent! But stuff aren't that bad. Having a high confidence about the code is usually enough. For instance, if using multiple threads is still not enough for you, you can decide to use fuzzing as well so as to randomize the test execution even more. If your tests always pass, well, you can be pretty confident that your code is good.

回答2:

because that order could have occurred by chance.

You can run the test a few times, e.g. 10, and test that each time the order was correct. This will ensure that it happened not by chance.

P.S. Multiple threads in a unit test is usually avoided