Тупик в реализации блокировки MCS
Оборудование: Ядро Darwin Версия 13.2.0: Четверг, 17 апреля 23:03:13 PDT 2014; root: xnu-2422.100.13 ~ 1 / RELEASE_X86_64 x86_64
atomics.hpp
1 #ifndef ATOMIC_UTILS_H
2 #define ATOMIC_UTILS_H
3
4 # включите
5
6 #define BARRIER() __asm__ volatile ( "":::"memory")
7
8 #define CPU_RELAX() __asm__ volatile( "пауза \n\t":::"память")
9
10 #define STORE_FENCE() __asm__ volatile("mfence"::: "memory");
11
12 класс AtomicUtils
13 {
14 публичных:
15
16 /**
17 * проверить, равно ли значение в addr oldval, если это так, заменить его на newva l
18 * и вернуть старвал
19 */
20 встроенных статических size_t compareAndExchange( volatile size_t* addr, size_t oldval, size_t newval)
21 {
22 size_t ret;
23 __asm__ volatile( "блокировка cmpxchgq %2, %1\n\t"
24:"=a"(ret), "+m"(*addr)
25: "r"(newval), "0"(oldval)
26: "память");
27 возвращение в отставку;
28 }
29
30 /**
31 * атомно сохраняет x в addr и возвращает предыдущий
32 * хранится в адресе
33 */
34 встроенных статических size_t loadAndStore( size_t x, volatile size_t* addr)
36 {
37 size_t ret;
38 __asm__ volatile( "блокировка xchgq %1, %0\n\t"
39: "+m"(*addr), "=r"(ret)
40: "1"(х));
41 возвратный удар;
42 }
43
44 };
45
46 # конец
mcs.hpp
1 #ifndef MCS_LOCK_H
2 #define MCS_LOCK_H
3
4 #include "atomics.hpp"
5 # включите
6
7 класс MCSLock
8 {
9 struct mcs_lock_t
10 {
11 mcs_lock_t(): следующий (0), заблокирован (ложь){}
12 struct mcs_lock_t* next;
13 бул заблокирован;
14 };
15
16 публичных:
17 typedef struct mcs_lock_t mcs_lock;
18
19 личное:
20 mcs_lock** хвост;
21 статическое повышение:: thread_specific_ptr tls_node;
22
23 публичных:
24 MCSLock( mcs_lock** lock_tail): хвост ( lock_tail)
25 {
26 if( tls_node.get() == 0)
27 tls_node.reset( new mcs_lock());
28 }
29
30 void lock()
31 {
32 mcs_lock* thread_node = tls_node.get();
33 thread_node->next = 0;
34 thread_node->locked = true;
35
36 изменчивых mcs_lock* pred = reinterpret_cast(
37 AtomicUtils::loadAndStore(
38 reinterpret_cast( thread_node),
39 reinterpret_cast( tail)
40)
41);
42 if( pred!= 0)
43 {
44 пред-> следующий = * хвост;
45
46 STORE_FENCE();
47 // БАРЬЕР (); // Требуется для предотвращения повторного упорядочения между prev->next = tail и thread_node->locked. ( WR Гарзард)
48
49 // Вращаем локальную переменную. Кто-нибудь разблокировать меня плз!
50 while( thread_node-> заблокирован)
51 CPU_RELAX();
52
53 }
54 }
55
56 void unlock()
57 {
58 mcs_lock* thread_node = tls_node.get();
59 if( thread_node->next == 0)
60 {
61 // Если false, то у нового потока есть запрос на блокировку. Теперь отпустите блокировку новой темы.
62 если (
63 AtomicUtils::compareAndExchange(
64 reinterpret_cast( tail),
65 reinterpret_cast( thread_node),
66 0
67) == reinterpret_cast( thread_node) 68)
69 {
70 возвращение;
71 }
72
73 while( thread_node->next == 0)
74 CPU_RELAX();
75 }
76
77 thread_node->next->locked = false;
78 }
79 };
80
81 boost::thread_specific_ptr MCSLock::tls_node;
82 #endif
mcs_test.cpp
1 #include "mcs.hpp"
2 #include <iostream>
3 #include <pthread.h>
4 #include <vector>
5 #define NUM_THREADS 16
6 #define NUM_ITERATIONS 100
7
8 std::vector<int> elements;
9 MCSLock::mcs_lock *tail = 0;
10
11 void* thread_run( void* data )
12 {
13 MCSLock lock( &tail );
14 for( int i = 0; i < NUM_ITERATIONS; ++i )
15 {
16 lock.lock();
17 elements.push_back( i );
18 lock.unlock();
19 }
20
21 return 0;
22 }
23
24 int main()
25 {
26 pthread_t threads[ NUM_THREADS ];
27 elements.reserve( NUM_THREADS * NUM_ITERATIONS );
28
29 {
30 for( int i = 0; i < NUM_THREADS; ++i )
31 pthread_create( &threads[i], NULL, thread_run, NULL );
32
33 for( int i = 0; i < NUM_THREADS; ++i )
34 pthread_join( threads[i], NULL );
35
36 std::cout <<"\nExiting main thread: " << std::endl;
37 }
38 }
Приведенный выше код скомпилирован с использованием Clang
Проблема:
Я вижу, что 1 или 2 потока застряли в lock () в строке 50. За исключением основных потоков, потоков, которые застряли в lock (), другие живые потоки отсутствуют. Это означает, что когда другие потоки вызывают unlock (), они почему-то не устанавливают значение false = false для других переменных и завершаются.
Любые указатели по отладке этого, пожалуйста?
Застрял на этом много часов и никаких подсказок.
1 ответ
Разве у clang нет встроенных модулей для этих блоков inline-asm (например, __sync_val_compare_and_swap) в gcc? Зачем заново изобретать колесо?
Во-вторых, я бы действительно подумал о добавлении Clobber памяти в loadAndStore. Вы должны убедиться, что все записи, которые компилятор хранит в регистрах, сбрасываются в память перед выполнением xchgq. Точно так же это предотвратит gcc от оптимизации чтения памяти до xchgq. Либо было бы плохо.
В-третьих, я бы изучил вывод asm для ваших циклов while (thread_node->locked и thread_node->next). Поскольку эти переменные не являются изменчивыми, gcc может оптимизировать это, чтобы выполнить чтение только один раз.
Это может не решить вашу проблему, но я бы начал с этого.