這是我得到的一個測驗任務，但我顯然失敗了：
1.使用兩個執行緒來增加一個整數。執行緒 A 在偶數時遞增，執行緒 B 在奇數時遞增（對于整數問題，我們可以讓它最多指定命令列上提供的數字）
1a. 添加更多執行緒有哪些困難？請顯示代碼的困難。
1b. 額外學分 - 針對上述問題設計了一個改進的解決方案，可以使用多個執行緒進行擴展
第一次嘗試后的反饋是“沒有解決原子修改和錯誤共享”。我試圖解決它們，但第二次嘗試沒有反饋。我想用這個測驗來學習，所以我想我會問最頂級的專家——你。
以下是第一次嘗試的標題：
#include <iostream>
#include <mutex>
#include <atomic>
class CIntToInc
{
private:
int m_nVal; //std::atomic<int> m_nVal;
int m_nMaxVal;
public:
CIntToInc(int p_nVal, int p_nMaxVal) : m_nVal(p_nVal), m_nMaxVal(p_nMaxVal) { }
const int GetVal() const { return m_nVal; }
const int GetMaxVal() const { return m_nMaxVal; }
void operator () { m_nVal; }
};
struct COper
{
enum class eOper { None = 0, Mutex = 1, NoMutex = 2 };
eOper m_Oper;
public:
friend std::istream& operator>> (std::istream &in, COper &Oper);
bool operator == (const eOper &p_eOper) { return(m_Oper == p_eOper); }
};
以下是第一次嘗試的原始碼。它包括我對解決方案為何有效的想法。我在 MSVS2012 中編譯了代碼。
// Notes:
// 1a.
// Since an integer cannot be an odd number and an even number at the same time, thread separation happens naturally when each thread checks the value.
// This way no additional synchronization is necessary and both threads can run at will, provided that it's all they are doing.
// It's probably not even necessary to declare the target value atomic because it changes (and thus lets the other thread increment itself) only at the last moment.
// I would still opt for making it atomic.
// Adding more threads to this setup immediately creates a problem with threads of equal condition (even or odd) stepping on each other.
// 1b.
// By using a mutex threads can cleanly separate. Many threads with the same condition can run concurrently.
// Note: there is no guarantee that each individual thread from a pool of equally conditioned threads will get to increment the number.
// For this method reading has to be inside the mutext lock to prevent a situation where a thread may see the value as incrementable, yet when it gets to it, the value has already
// been changed by another thread and no longer qualifies.
// cout message output is separated in this approach.
//
// The speed of the "raw" approach is 10 times faster than that of the mutex approach on an equal number of threads (two) with the mutex time increasing further as you add threads.
// Use 10000000 for the max to feel the difference, watch the CPU graph
//
// If the operation is complex and time consuming, the approach needs to be different still. The "increment" functionality can be wrapped up in a pimpl class, a copy can be made
// and "incremented". When ready, the thread will check for whether the value has changed while the operation was being performed on the copy and, if not, a fast swap under the mutex
// could be attempted. This approach is resource-intensive, but it mininuzes lock time.
//
// The approach above will work if the operation does not involve resources that cannot be easily copied (like a file to the end of which we are writing)
// When such resources are present, the algorithm probably has to implement a thread safe queue.
// END
#include "test.h"
#include <thread>
int main_test();
int main(int argc, char* argv[])
{
main_test();
return(0);
}
void IncrementInt2(CIntToInc &p_rIi, bool p_bIfEven, const char *p_ThreadName, std::mutex *p_pMu)
// the version that uses a mutex
// enable cout output to see thread messages
{
int nVal(0);
while(true) {
p_pMu->lock();
bool DoWork = (nVal = p_rIi.GetVal() < p_rIi.GetMaxVal());
if(DoWork) {
//std::cout << "Thread " << p_ThreadName << ": nVal=" << nVal << std::endl;
if((!(nVal % 2) && p_bIfEven) || (nVal % 2 && !p_bIfEven)) {
//std::cout << "incrementing" << std::endl;
p_rIi; } }
p_pMu->unlock();
if(!DoWork) break;
//if(p_bIfEven) // uncomment to force threads to execute differently
// std::this_thread::sleep_for(std::chrono::milliseconds(10));
}
}
void IncrementInt3(CIntToInc &p_rIi, bool p_bIfEven, const char *p_ThreadName)
// the version that does not use a mutex
// enable cout output to see thread messages. Message text output is not synchronized
{
int nVal(0);
while((nVal = p_rIi.GetVal()) < p_rIi.GetMaxVal()) {
//std::cout << "Thread " << p_ThreadName << ": nVal=" << nVal << std::endl;
if((!(nVal % 2) && p_bIfEven) || (nVal % 2 && !p_bIfEven)) {
//std::cout << "Thread " << p_ThreadName << " incrementing" << std::endl;
p_rIi; }
}
}
std::istream& operator>> (std::istream &in, COper &Oper)
// to read operation types from cin
{
int nVal;
std::cin >> nVal;
switch(nVal) {
case 1: Oper.m_Oper = COper::eOper::Mutex; break;
case 2: Oper.m_Oper = COper::eOper::NoMutex; break;
default: Oper.m_Oper = COper::eOper::None; }
return in;
}
int main_test()
{
int MaxValue, FinalValue;
COper Oper;
std::cout << "Please enter the number to increment to: ";
std::cin >> MaxValue;
std::cout << "Please enter the method (1 - mutex, 2 - no mutex): ";
std::cin >> Oper;
auto StartTime(std::chrono::high_resolution_clock::now());
if(Oper == COper::eOper::Mutex) {
std::mutex Mu;
CIntToInc ii(0, MaxValue);
std::thread teven(IncrementInt2, std::ref(ii), true, "Even", &Mu);
std::thread todd(IncrementInt2, std::ref(ii), false, "Odd", &Mu);
// add more threads at will, should be safe
//std::thread teven2(IncrementInt2, std::ref(ii), true, "Even2", &Mu);
//std::thread teven3(IncrementInt2, std::ref(ii), true, "Even3", &Mu);
teven.join();
todd.join();
//teven2.join();
//teven3.join();
FinalValue = ii.GetVal();
}
else if(Oper == COper::eOper::NoMutex) {
CIntToInc ii(0, MaxValue);
std::thread teven(IncrementInt3, std::ref(ii), true, "Even");
std::thread todd(IncrementInt3, std::ref(ii), false, "Odd");
teven.join();
todd.join();
FinalValue = ii.GetVal(); }
std::chrono::duration<double>elapsed_seconds = (std::chrono::high_resolution_clock::now() - StartTime);
std::cout << "main_mutex completed with nVal=" << FinalValue << " in " << elapsed_seconds.count() << " seconds" << std::endl;
return(0);
}
對于第二次嘗試，我對標頭進行了以下更改：
made m_nVal std::atomic
使用原子方法遞增和檢索
m_nVal 從只讀m_nMaxVal 中分離的 m_nVal 由填充符
源檔案未更改。新標題如下。
#include <iostream>
#include <mutex>
#include <atomic>
class CIntToInc
{
private:
int m_nMaxVal;
char m_Filler[64 - sizeof(int)]; // false sharing prevention, assuming a 64 byte cache line
std::atomic<int> m_nVal;
public:
CIntToInc(int p_nVal, int p_nMaxVal) : m_nVal(p_nVal), m_nMaxVal(p_nMaxVal) { }
const int GetVal() const {
//return m_nVal;
return m_nVal.load(); // std::memory_order_relaxed);
}
const int GetMaxVal() const { return m_nMaxVal; }
void operator () {
// m_nVal;
m_nVal.fetch_add(1); //, std::memory_order_relaxed); // relaxed is enough since we check this very variable
}
};
struct COper
{
enum class eOper { None = 0, Mutex = 1, NoMutex = 2 };
eOper m_Oper;
public:
friend std::istream& operator>> (std::istream &in, COper &Oper);
bool operator == (const eOper &p_eOper) { return(m_Oper == p_eOper); }
};
我不知道這種方法是否從根本上是錯誤的，或者是否存在一個或多個較小的錯誤。
uj5u.com熱心網友回復：
您為什么不需要同步的推理是有缺陷的。您確實需要同步，即使每個執行緒會自然地交替誰是作者。正如皮特貝克爾所說，沒有同步的作者和讀者是未定義的行為。您無法預測它將如何中斷，但有時優化器可以看到它對您的代碼做出假設，并做壞事：
這里一個執行緒立即將 keep_going 設定為 false，這“應該”停止回圈：
int main() {
bool keep_going = true;
unsigned x = 999;
auto thr = std::thread([&]() mutable {
keep_going = false; // unsync write ...
});
while (keep_going) { // ... unsync read - undefined behavior
x;
}
thr.join();
std::cout << x << std::endl;
}
直播：https : //godbolt.org/z/P1rnf8s71
但是，它永遠不會停止使用 g 運行！為什么？回圈優化器會看到以下幾點：
- 盡管在 lambda 中使用了 keep_going，但它不會因為沒有同步而在后臺執行緒中運行。
- 因此，當它進入回圈時，如果 lambda 想要改變它，它已經改變了。
- 由于沒有任何內容寫入 keep_going，因此在進入回圈時它的狀態不會改變，因此可以將測驗提升到回圈之外。
- 同樣，由于回圈無法退出，并且回圈只寫為x，如果它根本是不可觀測的不寫為x，所以它消除浪費的作業。
優化器因此與 AS 一起作業，它相當于：
bool keep_going = true;
call_ordinary_function(keep_going);
if (keep_going) {
top:
goto top;
}
生成的程式集反映了這一點：
call [QWORD PTR [rax 8]]
.L7:
cmp BYTE PTR [rsp 31], 0
je .L30
.L8:
jmp .L8 <<<< truly infinite loop
.L30:
不是你所期望的？
但是宣告布林值會atomic改變一切：
std::atomic<bool> keep_going = true;
現在生成的代碼是：
.L7:
mov ebx, 999
jmp .L8
.L11:
add ebx, 1
.L8:
movzx eax, BYTE PTR [rsp 31]
test al, al
jne .L11
lea rdi, [rsp 32]
所以現在我們看到：
- x 現在增加了（因為回圈可以終止，所以
x在回圈之后更改是可見的）， - 我們不斷加載 keep_going 的值，將其讀入
eax并在回圈中實際檢查它。 - 它實際上終止了。
我希望這能讓你相信，即使你認為它沒有必要，生成的代碼也可能不是你想的那樣。
uj5u.com熱心網友回復：
首先，臨界區（鎖定 解鎖）包含奇數/偶數檢查并在活動回圈中完成。因此，兩個執行緒將競爭性地嘗試鎖定互斥鎖，盡管只有一個應該這樣做。在最壞的情況下，執行緒 1 增加值，然后忙鎖定 解鎖互斥鎖（以主動執行檢查），而另一個執行緒 2 等待很長時間才能鎖定值并增加值。這種情況遠非理論上的，因為執行緒 1 通常在互斥鎖上具有優先級（由于 CPU 快取和作業系統的作業方式）。
解決這個問題的一種方法是使用條件變數。這個想法是鎖定一個互斥鎖，然后增加該值，然后向可以增加該值的下一個執行緒發出信號，然后等待被執行緒喚醒。此解決方案可很好地擴展，但如果作業量非常小，它通常會很慢，因為等待會導致一些不必要的延遲（通常是由于背景關系切換）。當執行緒數遠大于核心數時，這種解決方案非常有效。當執行緒數量很少時（或者當執行緒很多并且即將輪到執行緒時），可以使用對原子變數的忙讀取來降低這種成本。
另一種解決方案是使用兩個（二進制）信號量。一開始，一個是獲得的，一個不是。每個執行緒嘗試獲取自己的信號量，增加整數，然后釋放另一個，導致類似乒乓的執行。
錯誤共享是您第一次嘗試時遇到的最少問題。實際上，雖然互斥體和遞增的整數之間可能存在錯誤共享，但這不是問題，因為互斥體保護整數（并且還負責執行緒之間整數的可見性）。
請注意，您可以使用lock_guard使代碼更安全、更易于閱讀。此外，te 條件(!(nVal % 2) && p_bIfEven) || (nVal % 2 && !p_bIfEven)比它應該的要復雜得多。考慮使用(nVal % 2) ^ p_bIfEven.
第二次嘗試時，不清楚您是否使用帶有互斥鎖的原子。請注意，沒有必要將它們一起使用。事實上，由于原子引起的額外開銷，這是一個壞主意。話雖這么說，如果你選擇只使用原子變數，那么你需要一個（弱）比較和交換，以便檢查原子變數的值，并改變它原子。只要執行緒數小于核心數（由于忙等待），此解決方案很快。
關于第二次嘗試的虛假分享，m_Filler不足以保證沒有虛假分享（也不是很直接）。實際上，在 之后存盤的內容std::atomic可能會導致錯誤共享（std::atomic不能保證使用某些填充來防止錯誤共享，實際上通常不會）。您可以使用alignas(64) std::atomic<int> m_nVal; alignas(64) char padding;. 請注意，使用 64 取決于體系結構，alignas(std::hardware_destructive_interference_size)理論上應改為使用。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/388576.html