At the meeting in Athens, Kelly Long and I worked out a localized
version of cycle locking that would allow Record and RecordVersions to
be deleted with the assurance that no other thread has a dangling
temporary stack based pointer. The following is an description of this
Mini-Cycle Manager followed by a description of the Global Cycle Manager
that Jim implemented last week.
Mini-Cycle manager
======================
* Each RecordLeaf contains a Cycle object with 4 syncObjects.
* This is intended to replace both RecordLeaf::syncObject and
Table::syncPriorVersions
* Before collecting a local stack based pointer to a Record object, each
thread would get a shared lock on the the currentCycle.
currentCycle = RecordLeaf::cycle.share();
* That cycle must be remembered so it can be unlocked when the local
stack based pointer is no longer needed.
* Any thread that needs to change make a change in the linked list of
RecordVersion objects, from RelordLeaf::records[n] through each
RecordVersion::priorVersion, must follow the following procedure
1) 'Pedal' the cycle - This involves changing the current cycle
number so that any new reader thread following this chain of pointers
will get a shared lock on the next cycle. Since this can be done by
multiple threads at once, it is the most critical part of the mini-cycle
process.
1. nextCycle = INTERLOCKED_INCREMENT(currentCycleCount);
Two simultaneous threads pedaling the cycle at the same
time will get successive nextCycle values.
2. syncObjects[nextCycle & 3].lock(NULL, Exclusive);
These two threads will exclusively lock their own 'next'
cycle to prevent readers from reading on that cycle until
the change to the linkage is completed.
3. syncObjects[(nextCycle - 1) & 3].lock(NULL, Shared);
Keep this cycle active until you need to 'pump' it.
In the case where two threads are pedaling at the same
time, the thread with the higher nextCycle will wait for
this shared lock. (Note: there may be a race condition where;
Thread 1 pedals step 1,
Thread 2 pedals step 1,
Thread 2 pedals step 2,
Thread 2 pedals step 3,
Thread 1 pedals step 2,
Thread 1 pedals step 3
If this happens, thread 2 will come out of the pedal step
while thread 1 is waiting for it. This is discussed in
step 3 below.
2) Change the linkage - This can be done with a single atomic
operation, COMPARE_EXCHANGE_POINTER(). Since the linkage is always
followed in one direction, any thread following the chain will either
see this leaving RecordVersion or not. It does not matter if it is
missed. If a thread has a pointer to it, that pointer should be reliable
until that thread's shared lock is given up.
3) Pump the current cycle. - This means getting an exclusive lock on
the current cycle, waiting, if necessary, for all threads to release
their shared locks. It means that no threads have pointers to what was
detached after the current cycle was pedaled.
1. syncObjects[nextCycle & 3].downGrade(Shared);
2. syncObjects[(nextCycle - 1) & 3].unlock();
3. syncObjects[(nextCycle - 1) & 3].lock(NULL, Exclusive);
4. syncObjects[(nextCycle - 1) & 3].unlock();
Note, In the case described above where Thread 2 gets to pump first,
it will downgrade the cycle ahead of Thread 1, unlock the shared
lock that Thread 1 is waiting on, and then wait on Thread 1 in
Pump.step3. Then thread 1 will wake up and complete all 4 steps of
its own pump cycle. So both threads will be able to pump the cycle
even if their pedal steps race and crossed paths.
* While a Record version is detached, and before the pump completes, it
must be treated as if other threads are looking at it. You cannot
change things in this object that will cause a race condition or
assertion by any other thread which may be looking at it.
================================================================
Global Cycle Manager.
The global Cycle Manager is a much simpler design. It has the advantage
that only one thread, the CycleManager thread, ever 'pumps' the cycle.
Another characteristic (which may be a advantage or an disadvantage) is
that the doomed objects hang around longer. Threads which add objects
to a CycleManager's 'purgatory' list cannot wait for the pump. If a
thread needs to do anything to a doomed object after all other pointers
are gone, then this solution does not work. Fortunately, there is
nothing that needs to be done to a doomed record version object while
other threads still may have pointers to it. (*** This conclusion or
assumption must be considered whenever working with the record tree)
The CycleManager Thread has a loop in which it sleeps for (currently) 1
second. When it wakes up, it does this;
1) Collect/Separate the doomed list of Record and RecordVersion
objects that are currently in purgatory.
2) Make the SyncObject *currentCycle point to the other lock. Unlike
the Mini-Cycle Manager described above, this design only needs two
syncObjects since only one thread pumps at a time. From this point on,
any threads that may accrss a record chain will put a shared lock on the
next cycle. What about threads that lock the old cycle after step 1 and
before step 2? If one of these threads collects a pointer to a record
that is detached and added to the current purgatory list, there will not
be a problem. This thread will just get pumped on an earlier cycle.
3) Pump the Cycle by getting an exclusive lock on the SyncObject that
currentCycle is no longer pointing to. When this lock is achieved, it
is immediately unlocked.
4) Step through each doomed record and call record->release(). No
other thread is pointing to these.
The thread that detaches records from a record chain must have a shared
lock on the currentCycle itself. It detaches the record from either the
RecordLeaf or the record higher up the chain. Then it calls
garbageCollect on this record, knowing that some other thread may still
have a pointer to it. Finally, where it uesed to call
Record::release(), it now calls Record::queueForDelete()
Each thread that may access one or more Record or RecordVersion objects
on a priorRecord chain needs to lock the syncObject on the current
Cycle. This is done easily by instantiating a CycleLock object on the
stack. Its constructor locks the current cycle and its destructor
releases it. The CycleLock registers itself with the Thread object. In
order to catch all possible thread stacks that may need to instantiate a
CycleLock, I added temporary code into RecordVersion::getPriorVersion()
that checks the Thread for a current CycleLock. If a thread stack
happens to instantiate two CycleLocks, the second will not lock again.
It will just set a pointer to the first so that the status of the lock
can be determined.
If a thread needs to wait for another Transaction to complete, the
CycleLock which was instantiated higher up the stack is used to unlock
the cycle. After the wait, the current cycle is locked. This means
that any temporary stack based pointers higher up the stack cannot be
trusted anymore.
========================================================
I hope this helps to explain why we chose the Global Cycle Manager and
how it works.
Kevin
| Thread |
|---|
| • Mini-Cycle Manager vs a Global Cycle Manager | Kevin Lewis | 3 Apr |
