Random Scheduler Examples

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%


Comments are closed.