/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /* */ /* This file is part of the HiGHS linear optimization suite */ /* */ /* Written and engineered 2008-2021 at the University of Edinburgh */ /* */ /* Available as open-source under the MIT License */ /* */ /* Authors: Julian Hall, Ivet Galabova, Qi Huangfu, Leona Gottwald */ /* and Michael Feldmeier */ /* */ /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ #ifndef HIGHS_MUTEX_H_ #define HIGHS_MUTEX_H_ #include "parallel/HighsSpinMutex.h" #include "parallel/HighsTaskExecutor.h" class HighsMutex { std::atomic state{0u}; enum Constants { kNumSpinTries = 10 }; public: bool try_lock() { unsigned int uncontendedState = 0; return state.compare_exchange_weak(uncontendedState, 1, std::memory_order_acquire, std::memory_order_relaxed); } void lock() { // First try to acquire the lock directly to have a fast path for // uncontended access if (try_lock()) return; // Now spin a few times to check if the lock becomes available for (int i = 0; i < kNumSpinTries; ++i) { if (state.load(std::memory_order_relaxed) == 0) { if (try_lock()) return; } HighsSpinMutex::yieldProcessor(); } // Lock is still not available, so now start a loop where we yield // to the scheduler after each time we observe the lock as unavailable // so that we can see if there are other tasks and then check // the lock again. We do so for some microseconds which we measure starting // from now. HighsSplitDeque* thisDeque = HighsTaskExecutor::getThisWorkerDeque(); auto tStart = std::chrono::high_resolution_clock::now(); while (true) { int numTries = kNumSpinTries; for (int i = 0; i < numTries; ++i) { if (state.load(std::memory_order_relaxed) == 0) { if (try_lock()) return; } thisDeque->yield(); } auto numMicroSecs = std::chrono::duration_cast( std::chrono::high_resolution_clock::now() - tStart) .count(); if (numMicroSecs < HighsSchedulerConstants::kMicroSecsBeforeGlobalSync) numTries *= 2; else break; } // The lock is still not available, now we will try to set ourselves as the // next worker to acquire the lock and start wait until we are // notified by the current worker holding the lock. unsigned int ownerId = (thisDeque->getOwnerId() + 1) << 1; unsigned int s = state.load(std::memory_order_relaxed); while (true) { // as long as we observe that the lock is available we try to lock it, so // that we are guaranteed to have a locked state stored within s. while (s == 0) if (state.compare_exchange_weak(s, 1, std::memory_order_acquire, std::memory_order_relaxed)) return; if (s & 1u) { if (state.compare_exchange_weak(s, ownerId | 1, std::memory_order_release, std::memory_order_relaxed)) break; } else { // if we observe that the semaphore is unlocked but has its state not // equal to zero it means another worker has just been notified to take // the lock, but not yet taken it. Before we can set ourselves as the // next worker we need to wait for its state to be in locked state. HighsSpinMutex::yieldProcessor(); s = state.load(std::memory_order_relaxed); } } // once we are here we have successfully set ourselves as the next worker // and once the previous worker released the lock we will be notified. Hence // we wait until a notify and then are free to acquire the lock // unconditionally. thisDeque->wait(); // set the state to have its locked bit set and store the previous next // worker as the new next worker. As we only get here when the compare // exchange in the loop above succeeds with s having its locked bit set we // can simply store back s. state.store(s, std::memory_order_relaxed); } void unlock() { unsigned int prevState = state.fetch_add(-1, std::memory_order_relaxed); if (prevState != 1) { unsigned int notifyWorkerId = (prevState >> 1) - 1; HighsTaskExecutor::getThisWorkerDeque() ->getWorkerById(notifyWorkerId) ->notify(); } } }; #endif