Сколько раз цикл может выполняться в многопоточной программе на C ++? - PullRequest
0 голосов
/ 04 февраля 2012

Это вопрос интервью.

class X 
{
    int i = 0 ;

public: 
    Class *foo()
    {
        for (  ;  i < 1000 ; ++i )
        {
            // some code but do not change value of i 
        }
    }
}    

int main()
{
    X myX ; 
    Thread  t1 = create_thread( myX.foo() ) ;
    Thread  t2 = create_thread( myX.foo() ) ; 
    Start t1 ...
    Start t2 ...
    join(t1)
    joint(t2)
}

Q1: если код выполняется на процессоре с 1 процессором, сколько раз цикл for может выполняться в худшем случае?

Q2: что, если код выполняется на 2-процессор, сколько раз может работать цикл for в худшем случае?

Мои идеи:

Цикл может выполняться бесконечно много раз, потому что поток может запустить его много раз, прежде чем другой поток обновит значение i.

Или, когда t1 приостановлено, t2 работает 1000 раз, а затем мы имеем 1000 x 1000 раз?

Это правильно?

Ответы [ 4 ]

4 голосов
/ 04 февраля 2012

create_thread( myX.foo() ) вызывает create_thread с возвращаемым значением myX.foo().myX.foo() выполняется в главном потоке, поэтому myX.i в конечном итоге будет иметь значение 1000 (то есть значение, которое оно имеет после двух вызовов myX.foo()).

Если код действительно имел в видучтобы выполнить myX.foo() дважды в двух разных потоках одновременно, тогда код будет иметь неопределенное поведение (из-за состояния гонки в доступе к myX.i).Так что да, цикл может выполняться бесконечное количество раз (или ноль раз, или программа может решить встать и съесть бублик).

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

Это неправильный вопрос для собеседования, если код расшифрован точно.

class X 
{
    int i = 0;

Эта запись не является допустимой в C ++.G ++ говорит:

3:13: error: ISO C++ forbids initialization of member ‘i’ [-fpermissive]
3:13: error: making ‘i’ static [-fpermissive]
3:13: error: ISO C++ forbids in-class initialization of non-const static member ‘i’ 

Мы проигнорируем это, предполагая, что код был написан как-то вроде:

class X
{
    int i;
public:
    X() : i(0) { }

Исходный код продолжается:

public: 
    Class *foo()
    {
        for (  ;  i < 1000 ; ++i )
        {
            // some code but do not change value of i 
        }
        return 0;  // Added to remove undefined behaviour
    }
}

Не ясно, что такое Class * - тип Class в этом примере не указан.

int main()
{
    X myX; 
    Thread  t1 = create_thread( myX.foo() );

Поскольку здесь вызывается foo() и его возвращаемое значение передается в create_thread(), цикл будет выполняться здесь 1000 раз - не имеет значения, является ли это многоядерной системой.После завершения цикла возвращаемое значение передается в create_thread().

Поскольку у нас нет спецификации для create_thread(), невозможно предсказать, что она будет делать с Class *это возвращается из myX.foo(), больше, чем можно сказать, как myX.foo() фактически генерирует соответствующий Class * или что способен сделать объект Class.Скорее всего, нулевой указатель вызовет проблемы - однако, ради вопроса, мы предположим, что Class * допустим, и новый поток создан и помещен в режим ожидания, ожидая ' start 'операция, чтобы запустить его.

    Thread  t2 = create_thread( myX.foo() );

Здесь мы должны сделать некоторые предположения.Мы можем предположить, что Class *, возвращаемый myX.foo(), не дает доступа к переменной-члену i, которая находится в myX.Следовательно, даже если поток t1 запущен до создания t2, нет никаких помех от t1 в значении myX, и когда основной поток выполняет этот оператор, цикл будет выполнен еще 0 раз.Результат из myX.foo() будет использоваться для создания потока t2, который больше не может мешать i в myX.Мы обсудим варианты этих предположений ниже.

    Start t1 ...
    Start t2 ...

Потоки могут работать;они делают все, что подразумевается под Class *, возвращаемым с myX.foo().Но потоки не могут ни ссылаться, ни (следовательно) изменять myX;им не был предоставлен доступ к нему, если Class * каким-то образом не предоставляет такой доступ.

    join(t1)
    joint(t2)

Потоки завершены ...

}

Итак, тело цикла выполняется1000 раз до создания t1 и выполняется еще 0 раз до создания t2.И не имеет значения, является ли это одноядерным или многоядерным компьютером.

Действительно, даже если вы предполагаете, что Class * предоставляет потоку доступ к i и вы предполагаете, что t1 начинает работать немедленно (возможно, до того, как create_thread() вернется в основной поток), если он не изменяет i, поведение гарантированно будет равно «1000 и 0 раз».

Очевидно, что если t1 запускается при вызове create_thread() и изменяет i в myX, то поведение является неопределенным.Однако, пока потоки находятся в приостановленной анимации до выполнения операций « start », неопределенности нет, а «1000 и 0 раз» остается правильным ответом.


Альтернативный сценарий

Если вызовы create_thread() были ошибочно запомнены и код был:

Thread  t1 = create_thread(myX.foo);
Thread  t2 = create_thread(myX.foo);

, где указатель на функцию-член передается в create_thread(), тогда ответ будет совершенно другим.Теперь функция не выполняется до тех пор, пока не начнутся потоки, и ответ не определен, есть ли один процессор или несколько процессоров на машине.Это сводится к проблемам планирования потоков, а также зависит от того, как оптимизируется код.Почти любой ответ между 1000 и 2000 вероятен.

При достаточно странных обстоятельствах ответ может быть даже больше.Например, предположим, что t2 выполнено и прочитано i как 0, а затем приостановлено для запуска t1;t1 обрабатывает итерации 0..900, а затем записывает обратно i и передает управление в t2, который увеличивает свою внутреннюю копию i до 1 и записывает ее обратно, затем приостанавливается и t1запускается снова и читает i и снова запускается с 1 до 900, а затем позволяет t2 еще раз ... и т. д.В этом неправдоподобном сценарии (неправдоподобно, что код для t1 и t2 для выполнения, вероятно, один и тот же - хотя все зависит от того, чем в действительности является Class *), может быть много итераций.

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

Неважно, на каком типе системы будет выполняться этот код.Переключение между потоками происходит таким же образом.Худший случай для всех случаев: 1000 + 1000 * 999 * 998 * 997 * ... * 2 * 1 раз.(неверно !!! правильный обновляется)

Когда первый поток пытается увеличить переменную (он уже прочитал значение, но еще не записано), второй поток может сделать весь цикл из начального значенияя, но когда второй поток заканчивает свой последний цикл, первый поток увеличивает значение i, а второй поток снова начинает свою длинную работу:)

* Обновлено (немного больше деталей)

Извините, реальная формула:

1000 + 1000 + 999 + 998 + ... + 2 + 1 раз или 500999

Каждая итерация цикла выглядит следующим образом:

  1. Проверка состояния.
  2. Выполнение работы.
  3. Считывание значения из i
  4. Увеличение значения чтения
  5. Запись значенияto i

Никто не сказал, что шаг 2 имеет постоянное время.Поэтому я предполагаю, что он имеет переменную и подходит для моего худшего времени.

Вот этот худший случай:

Итерация 1:

[1-й поток] Делает шаги 1-4 первой итерации цикла (очень длительное время работы)

[2-й поток] Создает весь цикл (1000 раз), но не проверяет условие в последний раз

Итерация 2:

[1] Маскирует шаг 5, поэтому теперь i == 1 и выполняет шаги 1-4 следующей итерации цикла

[2] Делает весь цикл из текущего i (999 раз)

Итерация 3: такая же, как и раньше, но я == 2

...

Итерация 1000: такая же, как и раньше, но я == 999

В итоге у нас будет 1000 итераций, и каждая итерация будет иметь 1 выполнение кода цикла из первого потока и (1000 - номер итерации) из второго потока.

1 голос
/ 04 февраля 2012

В худшем случае 2000 раз, предполагая, что main доживает до t1 и t2

это не может быть бесконечным. потому что, если даже один поток работает, он будет увеличивать значение i.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...