1

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.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.