Fast and fair mutual exclusion algorithms using fetch & store primitive

Abstract

Althoug the compare&swap primitive and the fetch&store primitive are important for fast mutual exclusion algorithms,a large portion of production-quality multiprocessors does not support the former.A sequence of fast mutual exclusion algorithms using only fetch&store is shown to have qualitative improvements from one to the next. The last algorithm is optimal in minimizing the number of remote memory accesses for a self-scheduling unit and in guaranteeing the best possible fairness under such circumstances. we prove that no better algorithms exist. Minimizing the number of remote accesses serves a good purpose since remote access contributes to memory contention problem in large shared-memory multiprocessors. The results show that we were able to maintain the same level of performance with or without the support of compare&swap. However, fairness is degraded form bounded bypass to lockout freedom without the support