טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentIdan Igra
SubjectConstructive Conflict Resolution for Transactional
Memory
DepartmentDepartment of Electrical Engineering
Supervisors Professor Birk Yitzhak
Full Professor Mendelson Avi
Full Thesis text - in Hebrew Full thesis text - Hebrew Version


Abstract

We propose a novel “escape hatch” Transactional Memory model that copes with transaction aborts at the cost of significant weakening of the Transactional Memory model. The model is motivated by the way in which development teams work with Source Control: after checking out some files and performing changes, a team member tries to check in the change. If somebody else has checked in other changes to those files since the checkout operation, a conflict occurs. In such a situation the team member receives an indication, and is required to manually merge his changes into the updated file version.

The model enables the Transactional Memory implementation to ’release’ data entries that the transaction has accessed, and from now on to not protect them for that transaction until re-opening of those entries (if such re-opening ever happens). It is the Transactional Memory implementation’s responsibility to provide an indication to the programmer that an object was released, and to provide some information like an updated version of the data entry. The programmer can provide a code segment to handle the release and to enable the transaction to continue as if nothing happened. We call such an approach ‘Constructive Conflict Resolution.’

The programmer’s (user code) intervention is optional, with the implementation defaulting to aborting conflicting transactions (as in conventional TM) in the absence of instructions to do otherwise. This permits a programmer to spend the extra effort only when warranted..

The model offers various benefits to programs based on Transactional Memory. One of them is the option to enable conflicting transactions to continue running as if nothing happened. We demonstrate a mechanism that takes advantage of this option. The key change of the mechanism implementation relative to classic Transactional Memory implementation lies in the consistency check implementation: instead of aborting a transaction whenever a conflict is detected, the mechanism releases all conflicting objects and invokes appropriate resolver callbacks that were optionally provided by the programmer. We provide a formal proof that the mechanism implements the model by showing that the model provides the aforementioned model guarantees.

Finally, we provide examples that demonstrate the potential of using the new mechanism for increasing the level of parallelism.