我有以下代码,试图用来理解彼得森的解决方案。当我对直到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 properlyPeterson 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,并且都进入了关键部分。

10-08 06:23