For a computer game, I would like to find the data races between tasks of NPCs. The execution / task graph is generated by the user. The synchronization mechanisms consist of simple send/wait commands (definition below). Several of these can be executed at the end of a "task" - an NPC has 1 or more tasks. The execution of a task is "atomic", as the NPCs are executed in a "round-robin". However, certain tasks are exclusive - one or more "critical areas" are entered - e.g. when two NPCs have to move the same lever. In this case, "data races", i.e. collisions between two critical areas, should be detected.
SEND(ID, VALUE): SIGNALTABLE[ID] <- VALUE
WAIT(ID, VALUE): Wait Until SIGNALTABLE[ID] == VALUE
ENTER(X): Enter cricital area X
EXIT(X): Exit critical area X
The signal table is initialized with 0 (i.e. all signal values are 0 at the beginning). Execution of the NPCs:
TASK = RUN(TASKS[NPC])
IF NOT WAITING(TASK) THEN DEQUEUE(TASKS[NPC])
NPC = (NPC + 1) % NPCCOUNT
A possible synchronized sequence:
NPC1: | A1 | ---> | A2 | ---> | A3 | ---> | A4 |
ENTER(99) EXIT(99)
WAIT(0, 0) SEND(0, 0)
SEND(0, 1)
NPC2: | B1 | ---> | B2 | ---> | B3 | ---> | B4 |
ENTER(99) EXIT(99)
WAIT(0, 0) SEND(0, 0)
SEND(0, 1)
As can be seen here, a typical “mutex” aquire is represented as WAIT(X, 0) SEND(X, 1) and a release as SEND(X, 0).
Different signal values and multiple critical areas are also possible:
NPC1: | A1 | ---> | A2 | ---> | A3 | ---> | A4 |
ENTER(99) EXIT(99)
ENTER(10) EXIT(10)
SEND(0, 1)
NPC2: | B1 | ---> | B2 | ---> | B3 | ---> | B4 |
ENTER(99) EXIT(99)
ENTER(10) EXIT(10)
WAIT(0, 1)
Here B2 always has to wait until A4 is completed so this is also safe.
What I have tried so far: The Eraser / Lockset algorithm, but it fails in some cases with Wait / Send (case 2 for example because NPC1 does not acquire anything).
Is there a simple algorithm that can reliably recognize the data races (and deadlocks) statically / dynamically in this scenario? No read/write differentiation / forks and other features are required as only “critical areas” are entered directly.