c - 在我实现 Lamport 的面包店算法时，线程 1 和 2 具有很高的优先级

Question

我正在实现Lamport's bakery algorithm .

我的输出显示线程 1 和 2 的优先级高于其他线程。我的实现如下。

#include(pthread.h)
#include(stdio.h>
#include(unistd.h>
#include (assert.h>
volatile int NUM_THREADS = 10;
volatile int Number[10] = {0};
volatile int count_cs[10] = {0};
volatile int Entering[10] = {0};

int max()
{
    int i = 0;
    int j = 0;
    int maxvalue = 0;
    for(i = 0; i < 10; i++)
    {
        if ((Number[i]) > maxvalue)
        {
              maxvalue = Number[i];
        }
    }
    return maxvalue;
}

lock(int i)
{
    int j;
    Entering[i] = 1;
    Number[i] = 1 + max();
    Entering[i] = 0;
    for (j = 1; j <= NUM_THREADS; j++)
    {
        while (Entering[j]) { } /* Do nothing */
        while ((Number[j] != 0) &&
               ((Number[j] < Number[i]) ||
                ((Number[j] == Number[i]) && (j < i)))) { }
    }
}

unlock(int i) {
    Number[i] = 0;
}

void Thread(int i) {
   while (1) {
       lock(i);
       count_cs[i+1] = count_cs[i+1] + 1 ;
       //printf("critical section of %d\n", i+1);
       unlock(i);
   }
}

int main()
{
   int duration = 10000;
   pthread_t threads[NUM_THREADS];
   int rc;
   long t;
   for(t = 0; t < NUM_THREADS; t++){
       printf("In main: creating thread %ld\n", t+1);
       rc = pthread_create(&threads[t], NULL, Thread, (int)t);
       if (rc){
           printf("ERROR; return code from pthread_create() is %d\n", rc);
           exit(-1);
        }
   }
   usleep(duration*1000);
   for(t=0; t < NUM_THREADS; t++)
    {
    printf("count of thread no %d is %d\n",t+1,count_cs[t+1]);
    }
   return 0;
}

如果我在关键部分打印一些值，我会得到所有线程几乎相同的计数。为什么我的输出会发生这种变化？

关键部分没有打印语句的输出:

count of thread no 1 is 551013
count of thread no 2 is 389269
count of thread no 3 is 3
count of thread no 4 is 3
count of thread no 5 is 3
count of thread no 6 is 3
count of thread no 7 is 3

count of thread no 8 is 3
count of thread no 9 is 3
count of thread no 10 is 3

在关键部分输出带有打印语句:

count of thread no 1 is 5
count of thread no 2 is 6
count of thread no 3 is 5
count of thread no 4 is 5
count of thread no 5 is 5
count of thread no 6 is 5
count of thread no 7 is 4
count of thread no 8 is 4
count of thread no 9 is 4
count of thread no 10 is 4

为了避免内存模型出现问题，我将线程限制为单个 CPU，并使用 taskset 0x00000001 ./a.out 在 Linux 上运行我的程序。

Answer 1

这有几个问题。

首先，pthread_create 需要大量时间:当然比快速锁定/增量计数/解锁迭代要多得多。因此，第一个线程比其他线程有很大的优势，因为它首先运行，而第二个线程的优势较小，依此类推。当您将 printf 放在循环中时，这会减慢线程速度，因此优势较小。

相关说明，仅仅因为 pthread_create 已返回，线程不一定已启动。这只是意味着调度程序现在会考虑它。

第三，你的锁实现是一个繁忙的等待循环。因此，无论哪个线程正在运行，都将占用所有可用的 CPU 时间。由于您在单核上运行代码，因此如果拥有锁的线程被挂起，那么其他线程将花费所有时间片进行繁忙等待，然后拥有锁的线程可以恢复、解锁、尝试并获取再次锁定。

最后，在锁争用的情况下，该算法会优先考虑编号最小的线程，因此线程 0 会比其他线程更多地获得锁，因为所有线程都在忙等待，因此有高争用。

尝试在 lock() 的循环中放置一些 sched_yield() 调用，以允许具有锁的线程有更多的机会运行。