В моей реализации алгоритма пекарни Лампорта потоки 1 и 2 имеют большой приоритет - PullRequest
Новая
       19

В моей реализации алгоритма пекарни Лампорта потоки 1 и 2 имеют большой приоритет

2 голосов
/ 16 февраля 2012

Я реализую Алгоритм хлебопечения Лампорта .

Мой вывод показывает, что потоки 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

КомуВо избежание проблем с моделью памяти, я ограничиваю свои потоки одним процессором и использую taskset 0x00000001 ./a.out для запуска моей программы в Linux.

Ответы [ 2 ]

2 голосов
/ 16 февраля 2012

Есть несколько проблем с этим.

Во-первых, pthread_create занимает много времени: безусловно, намного больше, чем быстрая итерация блокировки / приращения / разблокировки.Поэтому первый поток получает большое преимущество перед остальными, так как он выполняется первым, а второй получает меньшее преимущество и так далее.Когда вы вставляете printf в цикл, это замедляет поток, поэтому преимущество меньше.

В связанной ноте, просто потому, что вернулось pthread_create, поток не обязательно запустился.Это просто означает, что планировщик теперь будет учитывать это.

В-третьих, ваша реализация блокировки является занятым циклом ожидания.Следовательно, потребуется все доступное время ЦП для того, какой поток запущен.Поскольку вы выполняете свой код на одном ядре, если поток, которому принадлежит блокировка, приостанавливается, другие потоки будут тратить все свои сегменты времени на занятое ожидание, а затем поток с блокировкой может возобновить, разблокировать, попробовать и получитьснова блокировка.

Наконец, в случае конкуренции за блокировку, этот алгоритм отдает приоритет потоку с наименьшим номером, поэтому поток 0 получит блокировку больше, чем другие, так как все потоки делаютожидание занято, и, следовательно, существует высокий уровень конкуренции.

Попробуйте ввести в цикл 1011 * несколько вызовов в lock(), чтобы поток с блокировкой имел больше шансов на запуск.

0 голосов
/ 16 февраля 2012

Я вижу, что вы работаете на одном процессоре, поэтому вы избегаете следующей проблемы.Тем не менее, имейте это в виду.

Обратите внимание, что в отличие от компилятора Microsoft, GCC не дает специальных нестандартных значений потоков SMP для volatile.Поэтому вы не можете полагаться на него при заказе между процессорами.Это означает, что если, скажем, Number и Entering находятся в разных строках кэша, CPU-0 может свободно записывать в Number, а Entering появляется в CPU-1 в другом порядке, чем вы думалинаписано.

Для решения этой проблемы вам нужно использовать атомарные операции.GCC имеет встроенные для них.

...