3. Пример показывает, что параллельное программирование не так просто, как кажется.

Код, выполняемый параллельно, должен учитывать порядок чтения и записи переменных. Если один процесс считывает значение переменной до того, как другой процесс его изменит, то первый процесс получит устаревшее значение.

В примере с двумя процессами P1 и P2, которые изменяют общий баланс, проблема возникает, когда P1 считывает баланс перед тем, как его изменить, а P2 считывает уже изменённое значение. В результате P2 использует устаревшее значение баланса для своих вычислений.

4.3.2. Правильность параллельных вычислений

Правильность параллельного выполнения кода определяется двумя условиями:

• результаты должны быть одинаковыми независимо от порядка выполнения процессов;
• результат должен соответствовать результату последовательного выполнения.

Первое условие означает, что код должен быть написан таким образом, чтобы результаты были одинаковыми при любом порядке выполнения процессов. Это позволяет избежать проблем, связанных с изменением значений переменных в разных контекстах.

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

Проблемы возникают, когда один процесс влияет на другой в критической секции программы. Критическая секция — это часть программы, которая должна выполняться без прерываний. Для обеспечения правильности параллельного выполнения необходимо синхронизировать выполнение процессов в критических секциях.

Для этого используются различные методы синхронизации, такие как сериализация (выполнение только одного процесса в критической секции) и взаимное исключение (процессы по очереди получают доступ к критической секции).

4.3.3. Защита общих данных: блокировки и семафоры

Все методы синхронизации основаны на использовании общих переменных как сигналов. Процессы понимают и соблюдают эти сигналы. Это похоже на работу автомобилей на перекрёстке, где каждый автомобиль понимает и соблюдает правила дорожного движения.

Блокировки (мьютексы) — это общие объекты, используемые для защиты доступа к общим данным. Каждый процесс пытается получить блокировку перед доступом к критическим данным и освобождает её после завершения работы. Только один процесс может иметь блокировку одновременно.

Семафоры похожи на блокировки, но позволяют нескольким процессам получать доступ к ресурсу одновременно, пока не будет достигнуто ограничение. Они используются для управления доступом к ограниченным ресурсам, таким как соединения с базой данных. Источник тупика — циклическое ожидание. Как показано ниже, ни один из процессов не может продолжить выполнение, так как они ожидают завершения других процессов, а те, в свою очередь, ждут окончания первого.

В качестве примера рассмотрим ситуацию с двумя процессами, которые зашли в тупик. Предположим, что есть две блокировки: x_lock и y_lock, которые используются следующим образом:

>>> x_lock = Lock()
>>> y_lock = Lock()
>>> x = 1
>>> y = 0
>>> def compute():
        x_lock.acquire()
        y_lock.acquire()
        y = x + y
        x = x * x
        y_lock.release()
        x_lock.release()
>>> def anti_compute():
        y_lock.acquire()
        x_lock.acquire()
        y = y - x
        x = sqrt(x)
        x_lock.release()
        y_lock.release()

Если compute() и anti_compute() выполняются параллельно и случайно чередуются следующим образом:

P1                          P2
acquire x_lock: ok          acquire y_lock: ok
acquire y_lock: wait        acquire x_lock: wait
wait                        wait
wait                        wait
wait                        wait
...                         ...

то возникает ситуация тупика. Каждый из P1 и P2 удерживает одну блокировку, но для выполнения им нужны обе блокировки. P1 ожидает освобождения y_lock от P2, а P2 ждёт освобождения x_lock от P1. Поэтому ни один процесс не может продолжать выполнение.