Глава 12. Взаимные блокировки

Вот перечень предварительных требований для данной главы:

В области информатики взаимной блокировкой (тупиковой ситуацией, deadlock) именуется некая особая ситуация в параллельном программировании, при которой никакого развития не может быть получено, а сами программы остаются заблокированными в своих текущих состояниях. В большинстве случаев это явление вызывается отсутствием координации между различными объектами блокировки (для целей синхронизации потоков) или её неправильным осуществлением. В данном разделе мы обсудим мысленный эксперимент широко известный как проблема Обедающих философов с целью иллюстрации самого понятия взаимной блокировки и причин её вызывающих; здесь вы изучите как имитировать данную проблему в некоторой параллельной программе Python.

Задача Обедающих философов впервые была предложена Эдгаром Дейкстра (который, как мы усвоили в Главе 1, Расширенное введение в совместное и параллельное программирование явился ведущим первопроходцем в параллельном программировании) в 1965. Данная проблема впервые была продемонстрирована с применением различных технических терминов (конкуренцией за ресурсы в вычислительных системах), а позднее была перефразирована Тони Хоаром, Британским исследователем в области информатики и ведущим инноватором в алгоритмах быстрой сортировки. Постановка задачи звучит следующим образом.

Пять философов садятся вокруг стола и каждый из них имеет сервированное блюдо перед собой. Между этими пятью блюдами с едой помещены пять вилок, поэтому каждый из философов имеет вилку слева от себя и вторую вилку справа. Данное расположение проиллюстрировано на следующей схеме:

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

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

Теперь некий потенциальный подход к решению данной задачи может быть таким:

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

Теперь, после этого шага, каждый философ будет вооружён вилкой в своей левой руке и при этом на столе не останется ни одной вилки. Так как ни один из философов не имеет обе вилки в своих руках, они не могут приступить к трапезе. Более того, тот набор инструкций, который им предписан, говорит, что некий философ может вернуть вилку обратно на стол только после того как он съест определённую порцию со своего блюда. Это означает, что поскольку философы не едят, они будут продолжать держать вилки в своих руках.

Таким образом, поскольку все философы держут только одну вилку в левой руке, они не могут продолжить еду или положить обратно удерживаемую вилку. Единственный возможный вариант для того чтобы некий философ вкусил своей еды состоит в том, чтобы его сосед положил свою вилку обратно, что может произойти только после того как он отведает свою порцию с собственного блюда; это создаёт некую ситуацию циклического условия без окончания которое никогда не может быть выполнено. Данная ситуация по- существу составляют природу взаимной блокировки, при которой все элементы системы залипают на своих местах и ситуация не может получить никакого развития.

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

Взаимные блокировки также определяются теми условиями, которые некоторая должны произойти в одно и то же время в параллельной программе для появления тупиковой ситуации. Эти условия впервые были сформированы научным сотрудником в области инорматики, Эдвардом Дж. Коффманом, мл. и теперь именуются условиями Коффмана. Они формулируются так:.

Давайте быстро взглянем на некий базовый пример тупиковой ситуации. Рассмотрим параллельную программу, в которой имеются два различных процесса (процесс A и процесс B) и два различных ресурса (ресурс R1 и ресурс R2), например:

Ни один из этих ресурсов не может совместно применяться обособленными процессами, причём каждому из процессов требуется доступ к обоим ресурсам для выполнения своих инструкций. В качестве примера возьмём процесс A. Он уже захватил ресурс R1, но ему также требуется R2 для осуществления своего исполнения. Однако R2 не может быть выделен A, так как он удерживается процессом B. По этой причине процесс A не может продолжить своё исполнение. то же самое происходит и с процессом B, который удерживает R2, но ему также для продолжения требуется и R1. А R1, в свою очередь, удерживается процессом A.

В этом разделе мы реализуем предыдущую ситуацию в некоторой реальной программе Python. В частности, у нас будут иметься две блокировки (мы будем называть их блокировкой A и блокировкой B), а также два обособленных потока, которые взаимодействуют с этими блокировками (поток A и поток B). В своей программе мы установим такую ситуацию, при которой поток A осуществит блокировку A и будет дожидаться выполнения блокирования B, которая уже получила доступ со стороны процесса B, который в свою очередь дожидается высвобождения A.

Если вы уже выгрузили необходимый для данной книги код с её страницы в GitHub, проследуйте далее и перейдите в папку Chapter12. Давайте рассмотрим следующий файл Chapter12/example1.py:

# Chapter12/example1.py

import threading
import time

def thread_a():
    print('Thread A is starting...')

    print('Thread A waiting to acquire lock A.')
    lock_a.acquire()
    print('Thread A has acquired lock A, performing some calculation...')
    time.sleep(2)

    print('Thread A waiting to acquire lock B.')
    lock_b.acquire()
    print('Thread A has acquired lock B, performing some calculation...')
    time.sleep(2)

    print('Thread A releasing both locks.')
    lock_a.release()
    lock_b.release()

def thread_b():
    print('Thread B is starting...')

    print('Thread B waiting to acquire lock B.')
    lock_b.acquire()
    print('Thread B has acquired lock B, performing some calculation...')
    time.sleep(5)

    print('Thread B waiting to acquire lock A.')
    lock_a.acquire()
    print('Thread B has acquired lock A, performing some calculation...')
    time.sleep(5)

    print('Thread B releasing both locks.')
    lock_b.release()
    lock_a.release()

lock_a = threading.Lock()
lock_b = threading.Lock()

thread1 = threading.Thread(target=thread_a)
thread2 = threading.Thread(target=thread_b)

thread1.start()
thread2.start()

thread1.join()
thread2.join()

print('Finished.')
 	   

В данном сценарии функции thread_a() и thread_b() определяют наши потоки A и B соответственно. В своей основной программе у нас также имеются два объекта threading.Lock: блокировка A и блокировка B. Общая структура инструкций конкретного потока такова:

Отметим, что для имитации неких подлежащих исполнению вычислительных действий мы применяем функцию time.sleep().

Прежде всего, мы запускаем оба потока, и A, и B почти одновременно, причём внутри той же самой основной программы. Имея на уме структуру набора инструкций конкретного потока, мы можем заметить, что к данному моменту оба потока будут инициированы; поток A попытается выполнить блокирование A и это будет сделано успешно, так как блокировка A всё ещё доступна к этому моменту. То же самое происходит с потоком B и блокировкой B.Два наших потока затем приступят к выполнению своих собственных вычислений.

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

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

Наша следующая схема дополнительно иллюстрирует тот процесс, которым развёртывается наше взаимное блокирование в его последовательности:

Теперь давайте рассмотрим созданное нами взаимное блокирование в действии. Запустите наш сценарий и вы должны получить следующий вывод:

> python example1.py
Thread A is starting...
Thread A waiting to acquire lock A.
Thread B is starting...
Thread A has acquired lock A, performing some calculation...
Thread B waiting to acquire lock B.
Thread B has acquired lock B, performing some calculation...
Thread A waiting to acquire lock B.
Thread B waiting to acquire lock A.
		

Как мы уже обсуждали, поскольку каждый из потоков пытается осуществить блокирование, которое уже в настоящий момент выполнено другим потоком, единственным способом блокирования было бы высвобождение для того чтобы поток продолжил своё исполнение. Это тупик и ваша программа повиснет навсегда, никогда не достигнув своего окончательного оператора вывода на печать в самой последней строке нашей программы.

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

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

В проблеме Обедающих философов каждый философ проинструктирован вначале взять вилку левой рукой, в то время как в нашем примере Python потоки всегда пытаются выполнить блокировку с тем же самым названием прежде чем выполнять какие- либо вычисления. Как вы можете видеть, когда философы желают начать приём пищи одновременно, они соответственно берут в свою левую руку по вилке и это приводит к подвешиванию ситуации в бесконечное ожидание; аналогично, когда два потока одновременно начинают исполнение, они осуществят свои индивидуальные блокировки и опять же будут дожидаться следующего блокирования бесконечно долго.

Тот вывод, который мы можем извлечь из этого, состоит в том, что вместо произвольного доступа к соответствующему ресурсу наши процессы (или потоки) должны выполнять к ним доступ неким предварительно определённым, статическим образом, с тем, чтобы исключить саму циклическую природу того способа, которым они осуществляют доступ и дожидаются своего ресурса. Таким образом, для нашего примера Python с двумя блокировками, вместо наличия того, что поток A попытается выполнить блокирование A, а поток B попробует заблокировать B в своих соответствующих инструкциях, мы потребуем чтобы оба потока пытались выполнять блокирование в одном и том же порядке. Например, оба потока теперь будут пробовать осуществлять вначале блокирование A, выполнять некоторые вычисления, пытаться выполнить блокирование B, выполнять последующие вычисления, и наконец высвобождать оба потока.

Эти изменения реализованы в нашем файле Chapter12/example2.py следующим образом:

# Chapter12/example2.py

import threading
import time

def thread_a():
    print('Thread A is starting...')

    print('Thread A waiting to acquire lock A.')
    lock_a.acquire()
    print('Thread A has acquired lock A, performing some calculation...')
    time.sleep(2)

    print('Thread A waiting to acquire lock B.')
    lock_b.acquire()
    print('Thread A has acquired lock B, performing some calculation...')
    time.sleep(2)

    print('Thread A releasing both locks.')
    lock_a.release()
    lock_b.release()

def thread_b():
    print('Thread B is starting...')

    print('Thread B waiting to acquire lock A.')
    lock_a.acquire()
    print('Thread B has acquired lock A, performing some calculation...')
    time.sleep(5)

    print('Thread B waiting to acquire lock B.')
    lock_b.acquire()
    print('Thread B has acquired lock B, performing some calculation...')
    time.sleep(5)

    print('Thread B releasing both locks.')
    lock_b.release()
    lock_a.release()

lock_a = threading.Lock()
lock_b = threading.Lock()

thread1 = threading.Thread(target=thread_a)
thread2 = threading.Thread(target=thread_b)

thread1.start()
thread2.start()

thread1.join()
thread2.join()

print('Finished.')
 	   

Данная версия нашего сценария теперь способна завершить своё исполнение и должна производить такой вывод:

> python3 example2.py
Thread A is starting...
Thread A waiting to acquire lock A.
Thread A has acquired lock A, performing some calculation...
Thread B is starting...
Thread B waiting to acquire lock A.
Thread A waiting to acquire lock B.
Thread A has acquired lock B, performing some calculation...
Thread A releasing both locks.
Thread B has acquired lock A, performing some calculation...
Thread B waiting to acquire lock B.
Thread B has acquired lock B, performing some calculation...
Thread B releasing both locks.
Finished.
		

Такой подход действенным образом исключает проблему взаимного блокирования в нашем примере с двумя блокировками, но насколько хорошо он сдержит проблему Обедающих философов? Для ответа на этот вопрос давайте попробуем эмулировать данную задачу и её решение на Python самостоятельно. Наш файл Chapter12/example3.py содержит реализацию проблемы Обедающих философов на Python и выглядит так:

# Chapter12/example3.py

import threading

# The philosopher thread
def philosopher(left, right):
    while True:
        with left:
             with right:
                 print(f'Philosopher at {threading.currentThread()} 
                       is eating.')

# The chopsticks
N_FORKS = 5
forks = [threading.Lock() for n in range(N_FORKS)]

# Create all of the philosophers
phils = [threading.Thread(
    target=philosopher,
    args=(forks[n], forks[(n + 1) % N_FORKS])
) for n in range(N_FORKS)]

# Run all of the philosophers
for p in phils:
    p.start()
 	   

Здесь у нас имеется соответствующая функция philospher(), выступающая в качестве логики, составляющей основу для наших обособленных потоков. Она получает два объекта Threading.Lock и имитирует предварительно обсуждавшуюся процедуру приёма пищи при помощи двух диспетчеров контекста. В своей основной программе мы создаём некий перечень из пяти объектов блокирования с названием forks, а также некий список из пяти потоков с названием phils с соответствующим предписанием, что наш первый поток получит первую и вторую блокировку, второй поток получит вторую и третью блокировки и так далее; а пятый получает пятую и первую блокировки (по порядку). Наконец, мы запускаем все пять потоков одновременно.

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

> python3 example3.py
Philosopher at <Thread(Thread-1, started 123145445048320)> is eating.
Philosopher at <Thread(Thread-1, started 123145445048320)> is eating.
Philosopher at <Thread(Thread-1, started 123145445048320)> is eating.
Philosopher at <Thread(Thread-1, started 123145445048320)> is eating.
Philosopher at <Thread(Thread-1, started 123145445048320)> is eating.
Philosopher at <Thread(Thread-1, started 123145445048320)> is eating.
Philosopher at <Thread(Thread-3, started 123145455558656)> is eating.
Philosopher at <Thread(Thread-1, started 123145445048320)> is eating.
Philosopher at <Thread(Thread-3, started 123145455558656)> is eating.
Philosopher at <Thread(Thread-3, started 123145455558656)> is eating.
Philosopher at <Thread(Thread-3, started 123145455558656)> is eating.
Philosopher at <Thread(Thread-3, started 123145455558656)> is eating.
Philosopher at <Thread(Thread-5, started 123145466068992)> is eating.
Philosopher at <Thread(Thread-3, started 123145455558656)> is eating.
Philosopher at <Thread(Thread-3, started 123145455558656)> is eating.
		

Тот вопрос который естественно последует: как мы можем организовать некий порядок в котором осуществляются блокирования в нашей функции philosopher()? Мы воспользуемся встроенной в Python функцией id(), которая возвращает конкретный параметр уникальной постоянной идентичности в качестве значения ключа для сортировки объектов блокирования. Мы также хотим реализовать индивидуальный диспетчер контекста для выделения данной логики сортировки в некий обособленный класс. Перейдите к следующему Chapter12/example4.py для знакомства с этой конкретной реализацией:

# Chapter12/example4.py

class acquire(object):
    def __init__(self, *locks):
        self.locks = sorted(locks, key=lambda x: id(x))

    def __enter__(self):
        for lock in self.locks:
            lock.acquire()

    def __exit__(self, ty, val, tb):
        for lock in reversed(self.locks):
            lock.release()
        return False

# The philosopher thread
def philosopher(left, right):
    while True:
        with acquire(left,right):
             print(f'Philosopher at {threading.currentThread()} 
                   is eating.')
 	   

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

Тем не менее, всё ещё существует некая проблема пр данном подходе, когда он применяется к некоторым определённым случаям. Имея на уме соответствующую идею верхнего уровня одновременности, мы знаем, что одна из наших основных целей когда мы применяем параллельность в своих программах состоит в улучшении их скорости. Давайте вернёмся обратно к своему примеру с двумя блокировками и исследуем время исполнения нешей программы с реализацией ранжирования ресурсов. Рассмотрите соответствующий файл Chapter12/example5.py; это просто программа двух блокировок с ранжированной (или упорядоченной) реализацией блокирования, в комбинации с определением времени исполнения, которое добавлено для отслеживания того сколько времени требуется для завершения двух потоков.

import threading
import time
from timeit import default_timer as timer

def thread_a():
    print('Thread A is starting...')

    print('Thread A waiting to acquire lock A.')
    lock_a.acquire()
    print('Thread A has acquired lock A, performing some calculation...')
    time.sleep(2)

    print('Thread A waiting to acquire lock B.')
    lock_b.acquire()
    print('Thread A has acquired lock B, performing some calculation...')
    time.sleep(2)

    print('Thread A releasing both locks.')
    lock_a.release()
    lock_b.release()

def thread_b():
    print('Thread B is starting...')

    print('Thread B waiting to acquire lock A.')
    lock_a.acquire()
    print('Thread B has acquired lock A, performing some calculation...')
    time.sleep(5)

    print('Thread B waiting to acquire lock B.')
    lock_b.acquire()
    print('Thread B has acquired lock B, performing some calculation...')
    time.sleep(5)

    print('Thread B releasing both locks.')
    lock_b.release()
    lock_a.release()

lock_a = threading.Lock()
lock_b = threading.Lock()

thread1 = threading.Thread(target=thread_a)
thread2 = threading.Thread(target=thread_b)

start = timer()

thread1.start()
thread2.start()

thread1.join()
thread2.join()

print('Took %.2f seconds.' % (timer() - start))
print('Finished.')

 	   

После исполнения данного сценария ваш вывод должен походить на такой:

> python3 example5.py
Thread A is starting...
Thread A waiting to acquire lock A.
Thread B is starting...
Thread A has acquired lock A, performing some calculation...
Thread B waiting to acquire lock A.
Thread A waiting to acquire lock B.
Thread A has acquired lock B, performing some calculation...
Thread A releasing both locks.
Thread B has acquired lock A, performing some calculation...
Thread B waiting to acquire lock B.
Thread B has acquired lock B, performing some calculation...
Thread B releasing both locks.
Took 14.01 seconds.
Finished.
		

Вы можете обнаружить, что такое комбинированное исполнение обоих потоков заняло около 14 секунд. Однако если мы пристальнее рассмотрим конкретные инструкции в наших двух потоках, мы можем увидеть, что помимо взаимодействия со своими блокировками, потоку A требуется около 4 секунд для выполнения своих вычислений (имитируемых двумя командами time.sleep(2)), в то время как потоку B потребуется около 10 секунд (две команды time.sleep(5)).

Означает ли это что нашей программе потребовалось так много времени поскольку её пришлось исполнять эти два потока последовательно? Мы проверим эту теорию при помощи своего файла Chapter12/example6.py, в котором мы определим, что каждый поток должен исполнять свои инструкции по одиночке за раз в своей основной программе:

# Chapter12/example6.py

lock_a = threading.Lock()
lock_b = threading.Lock()

thread1 = threading.Thread(target=thread_a)
thread2 = threading.Thread(target=thread_b)

start = timer()

thread1.start()
thread1.join()

thread2.start()
thread2.join()

print('Took %.2f seconds.' % (timer() - start))
print('Finished.')
 	   

Запустив этот сценарий, вы обнаружите, что данная последовательная версия нашей программы двух блокировок потребует то же самое время исполнения, что и её совместный вариант:

> python3 example6.py
Thread A is starting...
Thread A waiting to acquire lock A.
Thread A has acquired lock A, performing some calculation...
Thread A waiting to acquire lock B.
Thread A has acquired lock B, performing some calculation...
Thread A releasing both locks.
Thread B is starting...
Thread B waiting to acquire lock A.
Thread B has acquired lock A, performing some calculation...
Thread B waiting to acquire lock B.
Thread B has acquired lock B, performing some calculation...
Thread B releasing both locks.
Took 14.01 seconds.
Finished.
		

Это интересное явление является прямым результатом наших жёстких требований, которыми мы снабдили свои блокировки в данной программе. Иными словами, так как каждому потоку требуется выполнить оба блокирования для завершения своего исполнения, каждая блокировка не может быть получена более чем в одном потоке в определённый заданный момент времени и, окончательно, такие блокировки требуется осуществлять неким особым порядком, а само исполнение индивидуальных потоков не может проистекать одновременно. Если мы вернёмся обратно и изучим вывод своего файла Chapter12/example5.py, будет несомненно, что поток B не может запускать свои вычисления после того как поток A снял обе блокировки по окончанию своего выполнения.

Таким образом, интуитивно достаточно очевидно, что когда вы помещаете достаточное число блокировок на свои ресурсы в в вашей параллельной программе, она превращается в полностью последовательную относительно своего исполнения, а в сочетании с накладными расходами функциональности параллельного программирования это приводило бы даже к ухудшению при сопоставлении с последовательной версией данной программы. Однако мы не наблюдали в проблеме Обедающих философов (при её имитации на Python) такого упорядочения, создаваемого блокированием. Это происходит по той причине, что в задаче с двумя потоками двух блокировок оказалось достаточно для превращения в последовательное имеющегося исполнения программы, в то время как пяти было недостаточно сделать то же самое для проблемы Обедающих философов.

Мы изучим другое проявление данного феномена в Главе 14, Условия состязательности

Блокировки несомненно являются важным инструментом при синхронизации задач и при параллельном программировании в целом. Тем не менее, если если применение блокировок ведёт к нежелательным ситуациям, таким как взаимные блокировки, тогда вполне естественно будет для нас исследовать тот вариант, который просто не применяет блокировок в наших программах совместной обработки. За счёт игнорирования блокировок наши ресурсы программ действенно становятся пригодными для совместного использования между различными процессами/ потоками в некоторой параллельной программе, тем самым исключая первое из четырёх условий Коффмана: совместного исполнения.

Такой подход к проблеме взаимных блокировок может быть прямолинеен в реализации; давайте попробуем его в двух предыдущих примерах. Для своего примера с двумя блокировками мы просто удаляем тот код, который определяет какое бы то ни было взаимодействие с имеющимися объектами блокировки как внутри самих функций потоков, так и в нашей основной программе. Другими словами, мы более не используем вовсе механизм блокирования. Наш файл Chapter12/example7.py содержит такой пример данного подхода:

# Chapter12/example7.py

import threading
import time
from timeit import default_timer as timer

def thread_a():
    print('Thread A is starting...')

    print('Thread A is performing some calculation...')
    time.sleep(2)

    print('Thread A is performing some calculation...')
    time.sleep(2)

def thread_b():
    print('Thread B is starting...')

    print('Thread B is performing some calculation...')
    time.sleep(5)

    print('Thread B is performing some calculation...')
    time.sleep(5)

thread1 = threading.Thread(target=thread_a)
thread2 = threading.Thread(target=thread_b)

start = timer()

thread1.start()
thread2.start()

thread1.join()
thread2.join()

print('Took %.2f seconds.' % (timer() - start))

print('Finished.')
 	   

Выполните этот сценарий, и ваш вывод будет выглядеть подобно следующему:

> python3 example7.py
Thread A is starting...
Thread A is performing some calculation...
Thread B is starting...
Thread B is performing some calculation...
Thread A is performing some calculation...
Thread B is performing some calculation...
Took 10.00 seconds.
Finished.
		

Совершенно ясно, что поскольку мы не используем теперь блокировки для ограничения доступа любого вычислительного процесса, само исполнение наших двух потоков теперь стало целиком независящим друг от друга, и эти потоки, следовательно, исполнялись теперь полностью параллельно. По этой же причине мы также получили несколько лучшую скорость: так как наши потоки способны выполняться параллельно, общее время работы нашей программы в целом потребовало то же самое время, что и самая длительная задача из наших двух потоков (короче: поток B с 10 секундами).

А что это даёт применительно к проблеме Обедающих философов? Поскольку имеющийся ресурс (еда) является уникальным для каждого философа (иначе: никакой философ не должен есть из блюда другого философа), должен иметься вариант, когда каждый философ может продолжать своё исполнение не заботясь о прочих философах. За чсёт игнорирования блокировок каждый может продолжать исполнение параллельно, аналогично тому, что мы наблюдали в примере с двумя блокировками.

Такой подход, однако, означает что мы полностью не понимаем суть проблемы. Мы знаем, что блокировки применяются с тем, чтобы процессы и потоки могли осуществлять доступ к разделяемым ресурсам в некоторой программе неким системным, скоординированным образом чтобы избегать неверной обработки данных. Таким образом, удаление любых механизмов блокирования в некоторой программе совместной обработки означает, что для совместно используемых ресурсов, которые теперь освобождены от ограничений в доступе, наиболее вероятна значительное увеличение подверженности манипуляции ими не координированным образом (и следовательно, подверженная разрушениям).

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

Дополнительное замечание касательно блокировок

В то время как подход отказа от механизмов блокирования для исключения тупиковых ситуаций моежт порождать некоторые вопросы и темы для рассмотрения, он на самом деле действенно разоблачает нам некий новый момент относительно блокировок объектов в Python: для параллельного программирования существует возможность полностью обходить сами блокировки при доступе к некоторому заданному ресурсу. Иными словами, блокированные объекты предотвращают доступ к разделяемым ресурсам и манипуляцию с ними для различных процессов/ потоков, только если эти процессы или потоки на самом деле выполняют блокирование объектов.

Блокировки далее, в действительности ничего не блокируют. они всего лишь выставляют флаги, которые помогают определять может ли быть осуществлён доступ к некому ресурсу в какой- то определённый момент времени; будучи плохо проинструктированным, или даже злонамеренно, он сможет с большой вероятностью иметь возможность сделать это без труда. Другими словами, блокировки вовсе не связаны с самими ресурсами, которые они предназначены блокировать и они скорее всего не будут блокировать доступ к таким ресурсам процессам/ потокам.

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

Заключительное соображение по поводу решения взаимных блокировок

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

Также является возможным для некоторых программ, по причине взаимных блокировок, раскрытие нам неприемлемости исполнения их для совместной обработки; некоторые программы лучше оставлять последовательными, и это будет только хуже если принудить их к совместной обработке. Как мы уже обсуждали, в то время как совместная обработка предоставляет значительные улучшения во многих областях наших приложений, некоторые наследуют непригодность для конкретных приложений в их параллельном программировании. В ситуациях со взаимными блокировками разработчикам следует быть готовыми рассмотреть иные подходы к проектированию какой- то программы совместной обработки и не следует лениться реализовывать иной метод когда один из подходов совместной обработки не работает.

Понятие активного тупика (динамичного взаимного блокирования, livelock) связано с взаимной блокировкой; кое- кто рассматривает его даже как альтернативную версию тупиковой ситуации. В ситауции динамического взаимного блокирования имеющиеся процессы (или потоки) в определённой программе взаимной обработки имеют возможность переключать свои состояния; на самом деле они переключают свои состояния непрерывно. Они всё ещё просто переключаются бесконечно туда и обратно и при этом не происходит никакого развития. Сейчас мы рассмотрим некий реальный сценарий активного тупика.

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

Давайте смоделируем эту задачу на Python. Перейдите к Chapter12/example8.py и рассмотрите класс Spouse:

# Chapter12/example8.py

class Spouse(threading.Thread):

    def __init__(self, name, partner):
        threading.Thread.__init__(self)
        self.name = name
        self.partner = partner
        self.hungry = True

    def run(self):
        while self.hungry:
            print('%s is hungry and wants to eat.' % self.name)

            if self.partner.hungry:
                print('%s is waiting for their partner to eat first...' 
                      % self.name)
            else:
                with fork:
                    print('%s has stared eating.' % self.name)
                    time.sleep(5)

                    print('%s is now full.' % self.name)
                    self.hungry = False
 	   

Данный класс наследуется из threading.Thread и реализует ту логику, которую мы обсудили только что. Он получает имя для соответствующего экземпляра Spouse и другой объект Spouse в качестве его партнёра; после инициализации некий объект Spouse также всегда голоден (его значение атрибута hungry всегда установлено в True) Функция run() в данном классе определяет саму логику при запуске этого потока: до тех пор пока атрибут hungry данного объекта Spouse установлен в значение True, этот объект попытается воспользоваться имеющейся вилкой, которая является блокируемым объектом, чтобы отведать еды. Тем не менее, он всегда проверяет, не установлен ли атрибут hungry его партнёра также в значение True, и если это так, он не выполняет блокировку, а будет вместо этого дожидаться когда его партнёр сделает это.

В своей основной программе мы создаём вначале саму вилку как некий объект блокирования; затем мы создаём два объекта потока Spouse, каждый из которых является атрибутом partner для другого. Затем мы стартуем оба потока и исполняем программу пока оба потока не завершат исполнение:

# Chapter12/example8.py

fork = threading.Lock()

partner1 = Spouse('Wife', None)
partner2 = Spouse('Husband', partner1)
partner1.partner = partner2

partner1.start()
partner2.start()

partner1.join()
partner2.join()

print('Finished.')
 	   

Запустите этот сценарий, и вы обнаружите, что как мы и обсуждали, каждый поток попадает в бесконечный цикл, переключаясь между желанием поесть и ожиданием пока его партнёр не поест; эта программа исполняется бесконечно, пока не будет прерван Python. Приводимый далее код показывает самые первые несколько из тех строк, что я получил в своём выводе:

> python3 example8.py
Wife is hungry and wants to eat.
Wife is waiting for their partner to eat first...
Husband is hungry and wants to eat.
Wife is hungry and wants to eat.
Husband is waiting for their partner to eat first...
Wife is waiting for their partner to eat first...
Husband is hungry and wants to eat.
Wife is hungry and wants to eat.
Husband is waiting for their partner to eat first...
Wife is waiting for their partner to eat first...
Husband is hungry and wants to eat.
Wife is hungry and wants to eat.
Husband is waiting for their partner to eat first...
...
		

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

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

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

Для получения дополнительных сведений вы можете воспользоваться следующими ссылками: