我有以下代码,试图用来理解彼得森的解决方案。当我对直到9999的较小循环值运行此实现时,输出正确显示为0,但是当我使用较高的循环值(如9999999)对其进行测试时,我得到的值接近0,但不为0,是否可能同时递增和递减线程可能在(*(a))++;
部分中执行?为什么以下实现不起作用?我的程序中有错误吗?
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#define LOOP 9999999
int interest[2] = {0,0};
int turn = 0;
int loops[2] = {LOOP,LOOP};
void increment(int *a) {
printf("Incrementing %p\n",a);
for(int i=0;i<LOOP;i++) {
interest[0] = 1;
turn = 1;
while(interest[1] == 1 && turn == 1);
(*(a))++;
loops[0]--;
interest[0] = 0;
}
}
void decrement(int *a) {
printf("Decrementing %p\n",a);
for(int i=0;i<LOOP;i++) {
interest[1] = 1;
turn = 0;
while(interest[0] == 1 && turn == 0);
(*(a))--;
loops[1]--;
interest[1] = 0;
}
}
void print_val(int *a) {
while(1) {
getchar();
printf("value at mem %d\niInc(%d) iDec(%d)\n",*a,loops[0],loops[1]);
}
}
int main() {
pthread_t t1, t2, t3;
int *mem = malloc(sizeof(int));
pthread_create(&t1, NULL, (void*)decrement, (void*)mem);
pthread_create(&t2, NULL, (void*)increment, (void*)mem);
pthread_create(&t3, NULL, (void*)print_val, (void*)mem);
pthread_join(t1,NULL);
pthread_join(t2,NULL);
printf("operation complete\n");
pthread_join(t3,NULL);
return 0;
}
输出:
$:~/Arena/sem $ gcc op.c -pthread && ./a.out
Incrementing 0xd16010
Decrementing 0xd16010
operation complete
value at mem -2
iInc(0) iDec(0)
^Z
[13]+ Stopped ./a.out
$:~/Arena/sem $ gcc op.c -pthread && ./a.out
Decrementing 0x2432010
Incrementing 0x2432010
operation complete
value at mem 16
iInc(0) iDec(0)
^Z
[14]+ Stopped ./a.out
meow:~/Arena/sem $
编辑:
我已经尝试过Wrong implementation of Peterson's algorithm?并添加volatile并没有帮助,我也没有使用++操作,如上一个线程中所述。
Implementation of Peterson's solution doesn't work properly和Peterson algorithm in Java?不在C中,我的线程也不是欺骗对象。
看答案:
大多数答案都表明编译器可能会进行一些重新排序,我添加了程序集转储,有人可以帮助我了解这两个过程如何在关键部分内结束吗?
增量功能
for(int i=0;i<LOOP;i++) {
25: c7 45 f4 00 00 00 00 mov DWORD PTR [ebp-0xc],0x0
2c: eb 50 jmp 7e <increment+0x7e>
interest[0] = 1;
turn = 1;
2e: c7 05 00 00 00 00 01 mov DWORD PTR ds:0x0,0x1
35: 00 00 00
while(interest[1] == 1 && turn == 1);
38: c7 05 00 00 00 00 01 mov DWORD PTR ds:0x0,0x1
3f: 00 00 00
//while(turn == 1 && interest[1] == 1);
42: 90 nop
43: a1 04 00 00 00 mov eax,ds:0x4
48: 83 f8 01 cmp eax,0x1
4b: 75 0a jne 57 <increment+0x57>
4d: a1 00 00 00 00 mov eax,ds:0x0
52: 83 f8 01 cmp eax,0x1
55: 74 ec je 43 <increment+0x43>
(*(a->location))++;
57: 8b 45 08 mov eax,DWORD PTR [ebp+0x8]
5a: 8b 00 mov eax,DWORD PTR [eax]
5c: 8b 10 mov edx,DWORD PTR [eax]
5e: 83 c2 01 add edx,0x1
61: 89 10 mov DWORD PTR [eax],edx
loops[0]--;
63: a1 00 00 00 00 mov eax,ds:0x0
68: 83 e8 01 sub eax,0x1
6b: a3 00 00 00 00 mov ds:0x0,eax
interest[0] = 0;
70: c7 05 00 00 00 00 00 mov DWORD PTR ds:0x0,0x0
77: 00 00 00
减量功能
for(int i=0;i<LOOP;i++) {
8f: 8b 45 08 mov eax,DWORD PTR [ebp+0x8]
92: 8b 50 04 mov edx,DWORD PTR [eax+0x4]
95: 8b 45 08 mov eax,DWORD PTR [ebp+0x8]
98: 8b 00 mov eax,DWORD PTR [eax]
9a: 89 54 24 08 mov DWORD PTR [esp+0x8],edx
9e: 89 44 24 04 mov DWORD PTR [esp+0x4],eax
a2: c7 04 24 28 00 00 00 mov DWORD PTR [esp],0x28
a9: e8 fc ff ff ff call aa <decrement+0x21>
interest[1] = 1;
ae: c7 45 f4 00 00 00 00 mov DWORD PTR [ebp-0xc],0x0
b5: eb 4f jmp 106 <decrement+0x7d>
turn = 0;
while(interest[0] == 1 && turn == 0);
b7: c7 05 04 00 00 00 01 mov DWORD PTR ds:0x4,0x1
be: 00 00 00
//while(turn == 0 && interest[0] == 1);
c1: c7 05 00 00 00 00 00 mov DWORD PTR ds:0x0,0x0
c8: 00 00 00
(*(a->location))--;
cb: 90 nop
cc: a1 00 00 00 00 mov eax,ds:0x0
d1: 83 f8 01 cmp eax,0x1
d4: 75 09 jne df <decrement+0x56>
d6: a1 00 00 00 00 mov eax,ds:0x0
db: 85 c0 test eax,eax
dd: 74 ed je cc <decrement+0x43>
loops[1]--;
df: 8b 45 08 mov eax,DWORD PTR [ebp+0x8]
e2: 8b 00 mov eax,DWORD PTR [eax]
e4: 8b 10 mov edx,DWORD PTR [eax]
e6: 83 ea 01 sub edx,0x1
e9: 89 10 mov DWORD PTR [eax],edx
interest[1] = 0;
eb: a1 04 00 00 00 mov eax,ds:0x4
f0: 83 e8 01 sub eax,0x1
f3: a3 04 00 00 00 mov ds:0x4,eax
最佳答案
您似乎正在使用pthreads,它是POSIX标准的一部分。 POSIX不允许您像这样“滚动自己的”同步原语-在4.11 Memory Synchronization中要这样说:
应用程序应确保更多用户访问任何内存位置
不止一个控制线程(线程或进程)受到限制
没有控制线程可以读取或修改内存位置,而
另一个控制线程可能正在修改它。这样的访问是
限制使用同步线程执行的功能,以及
相对于其他线程同步内存。
实际的结果是允许编译器进行转换和执行重新排序,这可能会破坏您的假设。
例如,我编译器将while()
循环优化为无穷循环,因为它可以看到turn
不能在设置和测试循环之间合法地修改,因为没有调用POSIX同步函数。显然,这不是发生在您身上,但是其他类似的问题也是可能的。
在这种情况下,可能不是由编译器优化所困扰,而是没有尊重CPU内存模型。 This article描述了Peterson锁如何在多处理器x86上要求正确的内存防护。 (POSIX同步原语的实现将包括必要的内存隔离,但是您的代码不包含)。
就您的代码而言,xcc的负载可以在写入interest[1]
之前由x86重新排序,而interest[0]
的负载同样可以在写入interest[0]
之前重新排序。这意味着两个线程可以同时看到interest[1]
和interest[0] == 0
,并且都进入了关键部分。