1. Description
Example 1 is a simple module with 2 thread processes. It shows that the random scheduler can perform all 2 possible execution orders.
Example 2 is a simple module with 2 thread processes P1 and P2, in which each process has a synchronization point with the other process. Process P1 has two execution segments: P1:start and P2:end. Process P2 has two execution segments: P2:start and P2:end. P1:start executes before P1:end and P2:end and P2:start executes before P1:end and P2:end. However, the execution order of P1:start and P2:start is arbitrary. In the same way, the execution order of P1:end and P2:end is arbitrary. In total, there are 4 execution orders that can be shown by the random scheduler.
Example 3 implements a program consisting of 3 threads. Each thread has 2 synchronization points using waits statements, meaning that each thread has 3 execution segments. Therefore, there are totally (3!)^3 = 216 execution orders.
Source code – random_scheduler.tar.gz
2. Experimental results
This is some output from the Example 3. It shows the coverage and the efficiency of the random scheduler. For example, the coverage is about 63%, meaning that if we run the program 216 times, the number of execution orders performed by the scheduler is 136.
———————————————————————————
Run 216 times
The scheduler coverage : 63%.
Dynamic random verification efficiency : 63%
———————————————————————————-
Run 1382 times to obtain all 216 execution orders
Scheduler coverage : 100%
Dynamic random verification efficiency : 15.6%
———————————————————————————-
