Proxy Management Scenarios

This section discusses the set of task blocking scenarios that constitute a comprehensive test of proxy management by covering all situations causing different paths through the lock code. The scenarios are labeled using a three component numbering format, T.L.S, where T denotes the number of tasks in the scenario, L denotes the number of locks, and S is the unique number of the scenario within a given T.L set. This scheme will likely be extended in the future to account for the scheduling domains under which the tasks are being handled and whether a task and its proxy are on the same CPU or different CPUs.

In this initial pass, we implicitly assume the tasks are on the same CPU and all tasks are in the GS scheduling domain. In the figures describing each specific scenario numbers in squares are used to uniquely identify component situations to help track when they recur as part of various scenarios. Obviously the number of unique configurations will significantly increase when we extend this work to include scheduling domains and CPU assignments. In general terms, each unique situation or configuration in the current notation will become 8 scenarios differing in scheduling domain and CPU assignment parameter values.

Each subsection discusses a set of scenarios that comprise a coherent group. For each scenario we briefly summarize what is happening, and also specify the sequence of DSKI events that will be generated by the RT-mutex lock code under that scenario. One complicating factor is that in the testing method we use, code is executed at user level using futexes to execute a given scenario. In some cases the user-level code does not cause kernel-level execution of an equivalent rt-mutex call in a one-to-one relationship to scenario steps. However, be believe that with a little analysis it is possible to show that these scenarios implemented at the user level do comprehensively test the proxy management code.

1 Thread, 1 Lock Scenarios

Scenario Set 1.1

These scenarios are quite simple, indicating only that a mutex is locked (1.1.1) and then unlocked (1.1.2). These scenarios represent the fast-path of both the futex and rt-mutex code and so the test code does not generate events directly corresponding to these at the time they are done at the user level. However, in more complex scenarios that include the relationships among tasks and locks pictured here as well as others, actions are taken which are equivalent to these.

Perhaps we need some kernel-level tests to implement these simple scenarios and get the corresponding traces. Maybe instrumentation in the fast path?

These scenarios define two configurations. Configuration 1 represents the situation where no threads hold any locks. We may consider this the base state for any software system. Configuration 2 represents on mutex being locked by one thread.

_images/blocking-scenarios-1.1.png

Figure BS 1.1: Blocking Scenarios in the 1.1 Set

Event Sequence 1.1.1

  1. DSTRM_EVENT: RT_MUTEX, FASTLOCK, T1’s PID

Event Sequence 1.1.2

  1. DSTRM_EVENT: RT_MUTEX, FASTUNLOCK, T1’s PID

2 Threads, 1 Lock Scenarios

Scenario Set 2.1.1

These scenarios represent the arrival of a waiter for a mutex already locked, and its subsequent release by its owner. Scenario 2.1.1 begins in Configuration 2, with T1 locking mutex L1. T2 then attempts to lock L1, and blocks as a result, producing configuration 3. Scenario 2.1.2 begins in Configuration 3 and T1 then unlocks L1, leaving T2 as the pending owner and T1 unassociated with any lock, producing Configuration 4.

_images/blocking-scenarios-2.1.1.png

Figure BS 2.1.1: Blocking Scenarios in the 2.1.1 Set

Event Sequence 2.1.1

  1. DSTRM_EVENT: MUTEX_ACQUIRE, BLOCKING, T2’s PID

Scenario Set 2.1.2

These scenarios represent the arrival of a waiter for a mutex already locked, and its subsequent release by its owner. Scenario 2.1.1 begins in Configuration 2, with T1 locking mutex L1. T2 then attempts to lock L1, and blocks as a result, producing configuration 3. Scenario 2.1.2 begins in Configuration 3 and T1 then unlocks L1, leaving T2 as the pending owner and T1 unassociated with any lock, producing Configuration 4.

_images/blocking-scenarios-2.1.2.png

Figure BS 2.1.2: Blocking Scenarios in the 2.1.2 Set

Event Sequence 2.1.2

  1. DSTRM_EVENT: RT_MUTEX, SLOWUNLOCK, T1’s PID
  2. DSTRM_EVENT: MUTEX_ACQUIRE, PENDING_OWNER, T2’s PID

Scenario Set 2.1.3

This scenario begins in Configuration 4, with T2 the pending owner of L1. This scenario assumes that T2 is the next relevant thread to run and so it finishes setting the appropriate state variables to become the thread currently owning the mutex, producing Configuration 2, with T2 the owner of L1..

_images/blocking-scenarios-2.1.3.png

Figure BS 2.1.3: Blocking Scenarios in the 2.1.3 Set

Event Sequence 2.1.3

  1. DSTRM_EVENT: MUTEX_ACQUIRE, ACQUIRE, T2’s PID

Scenario Set 2.1.4

This scenario also begins in configuration 4, but under this scenario a thread (T1) other than the pending owner (T2) runs before T2 becomes the full owner, and tries to lock the mutex. However, T1 is considered unworthy to steal the mutex, so T1 becomes a waiter, producing Configuration 5.

_images/blocking-scenarios-2.1.4.png

Figure BS 2.1.4: Blocking Scenarios in the 2.1.4 Set

Event Sequence 2.1.4

  1. DSTRM_EVENT: MUTEX_STEAL, FAIL_GS_DENIED, T1’s PID
    or
    DSTRM_EVENT: MUTEX_STEAL,FAIL_VANILLA_DENIED, T1’s PID
  2. DSTRM_EVENT: MUTEX_ACQUIRE, BLOCKING, T1’s PID

Scenario Set 2.1.5

This scenario also begins in Configuration 4, but this time the new thread T1 trying to lock L1 runs before the pending owner T2 and is considered worthy to steal the lock. This produces Configuration 7.

_images/blocking-scenarios-2.1.5.png

Figure BS 2.1.5: Blocking Scenarios in the 2.1.5 Set

Event Sequence 2.1.5

  1. DSTRM_EVENT: MUTEX_STEAL, SUCCESS_NO_WAITERS, T1’s PID
  2. DSTRM_EVENT: MUTEX_ACQUIRE, ACQUIRED, T1’s PID

Scenario Set 2.1.6

This scenario begins in Configuration 5, and assumes that T1 is interrupted in its state of being blocked inside the lock code as a waiter for L1. This could typically happen if a signal is sent to T1, aborting the context in which T1 was blocked. This thus produces Configuration 4 since T1 is no longer a waiter.

It is not completely clear how we can make this scenario occur in a testing context.

_images/blocking-scenarios-2.1.6.png

Figure BS 2.1.6: Blocking Scenarios in the 2.1.6 Set

Event Sequence 2.1.6

  1. DSTRM_EVENT: MUTEX_ACQUIRE, BLOCKED, T1’s PID
  2. T1’s ABORT EVENT - FIXME.J - I need to trace this sequence better.

Scenario Set 2.1.7

This scenario is a variation on 2.1.6 which assume that T1 is interrupted in its blocked state, but in being interrupted, it is permitted to steal the lock. Configuration 7 is produced. This result could also be produced if we assume that T1 returns to its calling code and again executes the locking call, but is permitted to steal this time. This is essentially Scenario 2.1.6 followed by 2.1.5,

It is not clear if this scenario can actually happen in the system.

FIXME.J - Not sure this is a valid diagram to have, however, as we are skipping a great many of the intervening steps, which might make the actual trace of events necessary to go from the first state in the picture to the second state in the picture confusing.

_images/blocking-scenarios-2.1.7.png

Figure BS 2.1.7: Blocking Scenarios in the 2.1.7 Set

Event Sequence 2.1.7

  1. T1’s ABORT EVENT - FIXME.J - I need to trace this sequence better.
  2. DSTRM_EVENT: MUTEX_STEAL, SUCCESS_NO_WAITERS, T1’s PID
  3. DSTRM_EVENT: MUTEX_ACQUIRE, ACQUIRED, T1’s PID

Scenario Set 2.1.8

This scenario begins in Configuration 7 with T1 having stolen L1 from T2. T2 begins running, but discovers L1 is already owned by T1, so it becomes a waiter, producing Configuration 3.

_images/blocking-scenarios-2.1.8.png

Figure BS 2.1.8: Blocking Scenarios in the 2.1.8 Set

Event Sequence 2.1.8

  1. DSTRM_EVENT, MUTEX_ACQUIRE, BLOCKED, T2’s PID

Scenario Set 2.1.9

This scenario begins in Configuration 5. The pending owner T2 runs and completes its ownership of L1, producing Configuration 3.

Note that Scenarios 2.1.8 and 2.1.9 both produce Configuration 3, but differ in the owner and waiter roles of T1 and T2. We consider these the same configuration because the actions of the locking code do not generally depend on the properties of the threads that own and wait on the lock.

_images/blocking-scenarios-2.1.9.png

Figure BS 2.1.9: Blocking Scenarios in the 2.1.9 Set

Event Sequence 2.1.9

  1. DSTRM_EVENT: MUTEX_ACQUIRE, ACQUIRED, T2’s PID

3 Threads, 1 Lock Scenarios

Scenario Set 3.1.1

This scenario begins in Configuration 3 with an additional thread, T3 and produces Configuration 6. T3 blocks on L1 and becomes an additional waiter on the lock. Note that the locking code makes no real distinction between this scenario and scenario 2.1.1. All the same code paths are followed despite an additional waiter being present.

_images/blocking-scenarios-3.1.1.png

Figure BS 3.1.1: Blocking Scenarios in the 3.1.1 Set

Event Sequence 3.1.1

  1. DSTRM_EVENT: MUTEX_ACQUIRE, BLOCKING, T3’s PID

Scenario Set 3.1.2

This scenario begins in Configuration 6 and produces Configurations 1 and 5. Note the similarity between this set of events and those expected for Scenario 2.1.2. Despite this, a slightly different code path is followed. In Scenario 2.1.2, the pending owner has no waiters. Here, the remaining waiter, T3, must be transferred to the pending owner, who will become the new proxy for T3.

_images/blocking-scenarios-3.1.2.png

Figure BS 3.1.2: Blocking Scenarios in the 3.1.2 Set

  1. DSTRM_EVENT: RT_MUTEX, SLOWUNLOCK, T1’s PID
  2. DSTRM_EVENT: MUTEX_ACQUIRE, PENDING_OWNER, T2’s PID

Event Sequence 3.1.2

Scenario Set 3.1.3

This scenario begins in Configurations 1 and 5 and produces Configuration 8. Configuration 8 differs from Configuration 6 in that the blocker for the two waiting tasks is only the pending owner, and has not yet had a chance to run and become full owner of the lock. Note that in this scenario there will be a still attempt, as any time an owner is only pending, newly blocking tasks are given the opportunity to steal the lock.

_images/blocking-scenarios-3.1.3.png

Figure BS 3.1.3: Blocking Scenarios in the 3.1.3 Set

Event Sequence 3.1.3

  1. DSTRM_EVENT: MUTEX_STEAL, FAIL_GS_DENIED, T1’s PID
    or
    DSTRM_EVENT: MUTEX_STEAL,FAIL_VANILLA_DENIED, T1’s PID
  2. DSTRM_EVENT: MUTEX_ACQUIRE, BLOCKING, T1’s PID

Scenario Set 3.1.4

This scenario begins in Configuration 1 and 5 and produces Configuration 13. Unlike in scanario 3.1.3, here T1 succeeds in its steal attempt. Remember that a task which steals a lock skips the pending owner state and goes directly to full ownership of the lock. This is partly a result of the obvious task behavior wherein a blocking task which succeeds in stealing a lock essentially does not block and immediatly resumes execution after aquisition of the lock.

_images/blocking-scenarios-3.1.4.png

Figure BS 3.1.4: Blocking Scenarios in the 3.1.4 Set

Event Sequence 3.1.4

  1. DSTRM_EVENT: MUTEX_STEAL, SUCCESS_WAITERS, T1’s PID
  2. DSTRM_EVENT: MUTEX_ACQUIRE, ACQUIRED, T1’s PID

Scenario Set 3.1.5

This scenario begins in Configuration 8 and also is capable of producing Configuration 13. While T2 is only the pending owner, it is possible for one of its waiters to recieve a wake-up (from a timed sleep, for example) and attempt to claim the lock. In this situation, it is also possible for the waiter to have greater priority (due to time spent on the queue, for example) and thus actually succeed in stealing the lock from the previously pending owner.

_images/blocking-scenarios-3.1.5.png

Figure BS 3.1.5: Blocking Scenarios in the 3.1.5 Set

Event Sequence 3.1.5

FIXME.J - need the proper wakeup sequence of events? There are none as the woken task never leaves or reenters the lock loop, only cycles around again and attempts another steal.

  1. DSTRM_EVENT: MUTEX_STEAL, SUCCESS_WAITERS, T1’s PID
  2. DSTRM_EVENT: MUTEX_ACQUIRE, ACQUIRED, T1’s PID

Scenario Set 3.1.6

This scenario begins in Configuration 8 and produces Configuration 6. It is the simple scenario of T2, having been previously selected as the pending owner, running again and claiming the lock.

_images/blocking-scenarios-3.1.6.png

Figure BS 3.1.6: Blocking Scenarios in the 3.1.6 Set

Event Sequence 3.1.6

  1. DSTRM_EVENT: MUTEX_ACQUIRE, ACQUIRED, T1’s PID

Scenario Set 3.1.7

This scenario begins in Configuration 13 and produces Configuration 6. To reach Configuration 13, T2 must have been previously selected as the pending owner of the lock, and then had it stolen by T1. Once a task is selected as pending owner, it recieves a wakeup and will return to the runqueue. In this case, T2 will run again to discover that the lock has a new owner, and will reblock on the lock.

_images/blocking-scenarios-3.1.7.png

Figure BS 3.1.7: Blocking Scenarios in the 3.1.7 Set

Event Sequence 3.1.7

  1. DSTRM_EVENT: MUTEX_ACQUIRE, BLOCKING, T1’s PID

3 Threads, 2 Locks Scenarios

Scenario Set 3.2.1

This scenario begins in Configurations 3 and 2 and results in a new configuration, 9. It differs from Scenarios 2.1.1 and 1.1.1 in that the blocked task now has waiters of its own as it becomes a waiter itself. This transfers the proxy relationship of T3 from T2 to T1.

_images/blocking-scenarios-3.2.1.png

Figure BS 3.2.1: Blocking Scenarios in the 3.2.1 Set

Event Sequence 3.2.1

  1. DSTRM_EVENT: MUTEX_ACQUIRE, BLOCKING, T2’s PID

Scenario Set 3.2.2

This scenario begins in Configuration 9 and moves to Configurations 1 and 10. Configuration 10 differs from Configuration 5 as the unblocked task which is marked as pending owner of L1 already posses L2, which also has a waiter.

_images/blocking-scenarios-3.2.2.png

Figure BS 3.2.2: Blocking Scenarios in the 3.2.2 Set

Event Sequence 3.2.2

  1. DSTRM_EVENT: RT_MUTEX, SLOWUNLOCK, T1’s PID
  2. DSTRM_EVENT: MUTEX_ACQUIRE, PENDING_OWNER, T2’s PID

Scenario Set 3.2.3

This scenario begins in Configurations 10 and 1 and generates Configuration 11. T1 blocks on L1, and loses its steal attempt to T2, which is both the pending owner of L1 and the current owner of L2. When this happens T2 needs to properly assert its role as proxy for T1 through a pending relationship, without disturbing its existing relationship with T3.

_images/blocking-scenarios-3.2.3.png

Figure BS 3.2.3: Blocking Scenarios in the 3.2.3 Set

Event Sequence 3.2.3

  1. DSTRM_EVENT: MUTEX_STEAL, FAIL_GS_DENIED, T1’s PID
    or
    DSTRM_EVENT: MUTEX_STEAL,FAIL_VANILLA_DENIED, T1’s PID
  2. DSTRM_EVENT: MUTEX_ACQUIRE, BLOCKING, T1’s PID

Scenario Set 3.2.4

This scenario begins in Configurations 10 and 1 and produces Configuration 15. The steal attempt by T1 is successful this time, leaving T2 still the pending owner. It will have to run again to re-block. Note that the event will indicate no waiters for L1, as T2 is not actually a waiter until it reblocks.

_images/blocking-scenarios-3.2.4.png

Figure BS 3.2.4: Blocking Scenarios in the 3.2.4 Set

Event Sequence 3.2.4

  1. DSTRM_EVENT: MUTEX_STEAL, SUCCESS_NO_WAITERS, T1’s PID
  2. DSTRM_EVENT: MUTEX_ACQUIRE, ACQUIRED, T1’s PID

Scenario Set 3.2.5

This scenario begins in Configuration 11 and produces Configuration 12, a simple resolution of T2’s pending ownership of L1 to full ownership.

_images/blocking-scenarios-3.2.5.png

Figure BS 3.2.5: Blocking Scenarios in the 3.2.5 Set

Event Sequence 3.2.5

  1. DSTRM_EVENT: MUTEX_ACQUIRE, ACQUIRED, T1’s PID

Scenario Set 3.2.6

This scenario begins in Configuration 15 and produces Configuration 9. Similar to 2.1.8, T2 has already been woken up and thus must run again to discover that a new owner has already been selected for L1 and so it must re-block.

_images/blocking-scenarios-3.2.6.png

Figure BS 3.2.6: Blocking Scenarios in the 3.2.6 Set

Event Sequence 3.2.6

  1. DSTRM_EVENT: MUTEX_ACQUIRE, ACQUIRED, T2’s PID

Scenario Set 3.2.7

This scenario begins in Configuration 11 and produces Configuration 15. It is similar to 3.2.4 except this time T1 is already a waiter on L1. For it to be able to steal the lock from its pending owner, T2, it must be woken up and attempt to reaquire the lock prior to T2 running again. This is generally done using a signal from a timer of some sort, though inventive programming models could do so at the scheduling level in an SDF.

_images/blocking-scenarios-3.2.7.png

Figure BS 3.2.7: Blocking Scenarios in the 3.2.7 Set

Event Sequence 3.2.7

  1. DSTRM_EVENT: MUTEX_STEAL, SUCCESS_NO_WAITERS, T1’s PID
  2. DSTRM_EVENT: MUTEX_ACQUIRE, ACQUIRED, T1’s PID

Scenario Set 3.2.8

This scenario begins in Configuration 12 and produces Configurations e and 4. T2 does by releasing one of its locks, effectively splitting the locking chain at that point. It is necessary for the proxy internals to properly separate the group of waiters into those whose proxy remains T2 and those who need shifted to T1.

_images/blocking-scenarios-3.2.8.png

Figure BS 3.2.8: Blocking Scenarios in the 3.2.8 Set

Event Sequence 3.2.8

  1. DSTRM_EVENT: RT_MUTEX, SLOWUNLOCK, T2’s PID
  2. DSTRM_EVENT: MUTEX_ACQUIRE, PENDING_OWNER, T1’s PID

Scenario Set 3.2.9

This scenario begins in Configurations 3 and 4 and produces Configuration 14. It is similar to Scenario 2.1.5 except when T1 comes and steals L1, it already posseses a lock and a waiter. Internally this simply means that its pool of owned locks is not empty. Note that like Scenario 3.2.4 there are no waiters inidicated, as T2 is not a waiter until it reblocks on L1.

_images/blocking-scenarios-3.2.9.png

Figure BS 3.2.9: Blocking Scenarios in the 3.2.9 Set

Event Sequence 3.2.9

  1. DSTRM_EVENT: MUTEX_STEAL, SUCCESS_NO_WAITERS, T1’s PID
  2. DSTRM_EVENT: MUTEX_ACQUIRE, ACQUIRED, T1’s PID

Scenario Set 3.2.10

This scenario begins in Configuration 14 and produces Configuration 12. The resolution of T2’s pending ownership of L1 to a blocked state sets T2’s proxy to be T1.

_images/blocking-scenarios-3.2.10.png

Figure BS 3.2.10: Blocking Scenarios in the 3.2.10 Set

Event Sequence 3.2.10

  1. DSTRM_EVENT: MUTEX_ACQUIRE, BLOCKING, T2’s PID

Scenario Set 3.2.11

This scenario begins in Configuration 9 and produces Configurations 4 and 2. It occurs when T2 aborts both its ownership of L2 and its wait for L1 in one step. This can occur if L2 receives a kill signal. Note that when T2 aborts it will clean up its waiter structure from L1.

_images/blocking-scenarios-3.2.11.png

Figure BS 3.2.11: Blocking Scenarios in the 3.2.11 Set

Event Sequence 3.2.11

FIXME.J - need the proper kill sequence of events

4 Threads, 3 Locks Scenarios

Scenario Set 4.3.1

This scenario begins with configuration 16, which has a set of 3 threads and 3 locks in a chain, with a fourth task, T4 about to try and lock L3 which is already owned by T3. As a result, T4 blocks and becomes a waiter on L3.

_images/blocking-scenarios-4.3.1.png

Figure BS 4.3.1: Blocking Scenarios in the 4.3.1 Set