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

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

Задний план

Однопоточный процесс (особенно основанный на графическом интерфейсе пользователя) иногда может казаться безответным для пользователя, если этот единственный поток выполняет сложную операцию (например, печать большого текстового файла, выполнение интенсивных вычислений процессора или пытается подключиться к удаленному серверу за тысячи миль.) Но с появлением технологии Intel Hyper-Threading [исх. W1b] и многоядерных процессоров, этот недостаток можно устранить с помощью парадигмы многопоточности / параллельного программирования.

Парадигма многопоточности / параллельного программирования позволяет первичному потоку выполнения порождать дополнительные вторичные потоки в фоновом режиме. Каждый поток (первичный или вторичный) становится уникальным путем выполнения в процессе и имеет одновременный доступ ко всем совместно используемым данным.

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

Постановка задачи

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

Например, предположим, что два потока, скажем, T1 и T2, каждый хотят увеличить значение общей целочисленной переменной, скажем, i (чье начальное значение - 0) на 1. Также предположим, что поток T1 использует регистр r_A с начальным значением 0, а поток T2 использует регистр r_B с начальным значением 0.

В идеале мы хотим, чтобы выполнялась следующая последовательность операций (псевдомашинных инструкций):

Конечное значение i равно 2. Но из-за проблемы состояния гонки вместо этого могут выполняться следующие операции:

Опять же, предполагая, что начальное значение i равно 0. Обратите внимание, что инструкции, размещенные рядом, выполняются параллельно (либо с использованием технологии Hyper-Threading, либо на многоядерном процессоре).

Конечное значение i равно 1 вместо ожидаемого значения 2.

Это произошло из-за того, что оба потока одновременно прочитали и изменили общую переменную «i», что привело к неверным данным. Другими словами, доступ к общему ресурсу памяти не был контролируемым из-за отсутствия синхронизации между двумя потоками.

Техники и стратегии блокировки

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

Используйте критический раздел по минимуму

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

Например, вместо следующей последовательности шагов:

Желательно рассмотреть возможность их реструктуризации, чтобы:

Спиновые замки

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

Ниже приведен пример реализации спин-блокировок с использованием POSIX.1c PThreads.

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

В приведенном выше примере функция main инициализирует спин-блокировку echoLock, которая будет использоваться всеми потоками в одном процессе. Затем он создает несколько потоков, по одному на аргумент командной строки, для вызова функции echoThis() и отображает строки аргументов командной строки в стандартном выводе. Не имеет значения, сколько потоков одновременно вызывают функцию echoThis(), поскольку функция обслуживает только один поток за раз.

Ниже показаны два запуска вышеуказанной программы.

Компьютер, на котором была запущена эта программа, имел следующую конфигурацию:

  • Процессор: Intel (R) Pentium D CPU 2,80 ГГц и 2,80 ГГц
  • ОЗУ: 1024 МБ
  • ОС: Knoppix 5.1 (с X Window System и рабочим столом KDE).
  • Модель потока: POSIX
  • Компилятор: gcc версии 4.1.2 20061028 (предварительная версия) (Debian 4.1.1–19)

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

Блокировка ожидающих потоков

Этот метод похож на методы спин-блокировок ожидание при занятом. Но вместо ожидания блокировки поток блокируется сам. Операция блока помещает поток в очередь ожидания, связанную с блокировкой (также известную как турникет в Solaris), и поток переводится в состояние ожидания. Затем управление передается планировщику ЦП, который выбирает другой поток для выполнения.

Вышеупомянутая программа spinlock.cpp, реализованная с использованием этой методологии, показана ниже.

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

  • Функция блокировки вращения: pthread_spin_lock()
  • Функция блокировки блокировки: pthread_mutex_lock()

Использование более одного замка

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

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

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

Использование высокоуровневых API

Хотя семафоры предоставляют удобный и эффективный механизм для синхронизации потоков, их неправильное использование все же может привести к ошибке синхронизации, которую трудно обнаружить, поскольку эти ошибки возникают только в том случае, если какое-то конкретное выполнение последовательность имеет место, и эти последовательности не всегда происходят. Эта ситуация может быть результатом ошибок честного программирования со стороны программиста. API-интерфейсы высокоуровневой синхронизации потоков, представленные в Java (ключевое слово synchronized [ссылка TB3]) и C # (ключевое слово lock [ссылка TB2]), предоставляют простые, но надежные инструменты синхронизации. Это приводит к упрощению программирования и меньшему количеству ошибок программирования.

Ниже показан пример реализации на Java. Функция main() использует класс ThreadCreator для создания 4 примеров потоков. Класс ThreadCreator, в свою очередь, вызывает функцию printThis() класса Printer, которая выводит свои аргументы с каждым потоком.

Важно отметить, что в функции printThis() потоки на некоторое время спят. Это позволяет планировщику потоков переключаться по контексту на другой поток, создавая состояние гонки. Но поскольку ключевое слово synchronized используется с функцией printThis(), только один поток может войти в функцию. Таким образом, доступ к функции printThis() называется сериализованным.

Ниже показан пример выполнения вышеуказанной программы.

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

Теперь, если мы закодируем программу без использования ключевого слова synchronized, т.е. если мы изменим ...

class Printer
{
    synchronized void printThis(Thread t, String text)
    {

… To, удалив ключевое слово synchronized…

class Printer
{
    void printThis(Thread t, String text)
    {

… Тогда функция больше не будет синхронизироваться. Ниже показан пример вывода без синхронизации.

Все потоки одновременно входят в printThis() функцию и соревнуются друг с другом за выполнение функции, смешивая свои выходные данные.

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

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

Упрощенная схема работы менеджера блокировок показана ниже.

Использование блокировок чтения / записи

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

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

Ключевые результаты и обсуждение

Использование критического раздела до минимума определенно улучшает производительность. Его можно и нужно использовать везде, где это возможно.

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

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

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

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

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

Блокировки чтения / записи могут привести к нехватке записи, поскольку, пока хотя бы один поток чтения удерживает блокировку, поток записи не сможет получить блокировку. Варианты блокировки чтения / записи, известные как блокировки с предпочтением записи, не позволяют новым читателям получить блокировку, если писатель стоит в очереди и ожидает блокировки. Преимущество блокировок чтения / записи, конечно же, заключается в возможности одновременного чтения общих данных. POSIX.1c не определяет блокировки чтения / записи.

Вывод

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

использованная литература

Интернет

Учебники

  • [TB1] "Концепции операционной системы" (6-е издание) Зильбершатца, Гальвина, Гагна (2002, John Wiley & Sons, Inc.)
  • [TB2] C # и платформа .NET (2-е издание) Эндрю Троелсена (2003 г., Апресс, Беркли, Калифорния, США)
  • [TB3] Полный справочник по Java 2 (5-е издание) Герберта Шильдта (2002, Тата МакГроу Хилл)
  • [TB4] Системное программирование Unix с использованием C ++ (первое впечатление) Терренса Чана (2008, Pearson Education, Inc.)

Эта статья была опубликована как участник конкурса Intel Threading Champion 2009.