немного теории

Введение

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

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

Типичный пример

Чтобы иметь общий фон, позвольте мне представить вам пример.

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

Посмотрите на код C позади:

void add(char[] *input)
{
   scanf("%s",input);
   printf("%s",input);
}

Эта функция имеет указатель в качестве входных данных и ничего не возвращает. Он читает ключевое слово, а затем повторяет их. Для тех, кто не знаком с языком C, есть экскурсия здесь.

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

Возможный сценарий следующий:

Этот запуск печатает «чао» дважды, а «привет» никогда. Сценарий существует, потому что мы не можем делать никаких предположений о:

  • порядок выполнения шагов;
  • относительно скорости каждого потока.

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

Защита ресурсов

Согласно теории ОС, нам нужно торопиться по трем аспектам:

  • Взаимное исключение
  • Взаимоблокировка;
  • Голодание.

при доступе к общим ресурсам.

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

Ваша схема синхронизации должна избегать проблем взаимоблокировки и зависания .

Взаимоблокировка — это своего рода мексиканский ларек для потоков: я попытаюсь объяснить это на другом примере.

Давайте рассмотрим два потока T¹ и T², которые оба должны использовать R¹ и R². Что может случиться:

  • R¹ запирает T¹;
  • R² запирает T²;
  • Для завершения T¹ требуется R²;
  • Для завершения T² требуется R¹.

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

Голодание происходит, когда процесс ожидает доступа к одному ресурсу в течение бесконечной единицы времени. Эта проблема возникает из-за того, что время выполнения потока и поведение планировщика неизвестны априори.

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

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

семафор

Семафор — это простой примитив, который позволяет двум или более процессам взаимодействовать.

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

Семафор предоставляет конструктор и два метода:

  • wait: вычитает 1 из переменной;
  • сигнал: суммирует 1 с переменной

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

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

Самый простой реализует критическую секцию с помощью бинарного семафора:

s = semaphore(mysem);
wait(s);
#let's start critical section
[...]
signal(s);

Предположим, что семафор инициализирован где-то в общей части кода.

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

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

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

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

Я не хочу касаться этой проблемы здесь, вы можете найти решение в литературе, загляните в раздел «Библиография».

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

Монитор

Мониторы — более сложные объекты, чем семафоры. В объектно-ориентированном дизайне одежды вы можете думать о мониторе как об объекте, который инкапсулирует общие необходимые данные. Вы можете получить доступ к общим данным только с помощью открытых методов Monitor, которые управляют взаимным исключением.

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

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

  • wait(): поток, чей вызов этого метода блокируется и ставится в очередь до тех пор, пока условие не станет истинным;
  • сигнал(): пробуждает первый поток из очереди.

Эти операции кардинально отличаются от операций семафора. Если ни один поток не поставлен в очередь, а signal() запускает сценарий без операции.

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

Обмен сообщениями

Еще один способ согласования процессов — обмен сообщениями.

Этот метод позволяет синхронизировать процессы и обмениваться данными. Для обмена сообщениями мы определяем пару примитивов:

  • отправить(адресат, сообщение)
  • получить(источник, сообщение)

Первый позволяет процессу отправить сообщение процессу/назначению, а второй — получить сообщение.

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

В сценарии блокировки:

  • отправить: поток ожидает, пока его коллега получит сообщение;
  • получить: если создается сообщение, поток получает его. Если сообщение по-прежнему не создается, поток останавливается.

Скорее, в неблокирующем сценарии:

  • отправить: поток отправляет сообщение и продолжает
  • получить: поток получает сообщение, только если оно все еще создается.

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

Выводы

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

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

Если вам интересно, оставайтесь с нами!

Библиография

  • [1]Э. В. Дейкстра — Решение проблемы в управлении параллельным программированием — Коммуникация ACM
  • [2]Дж. Бэкон, Т. Харрис — Операционные системы: параллельное и распределенное проектирование программного обеспечения — Эддисон Уэсли
  • [3] В. Stalling — Внутреннее устройство операционных систем и принципы проектирования, третье издание — Джексон (итальянская версия)