Критический раздел - Critical section

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

Необходимость критических секций

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

Процесс А:

// Процесс A..б = Икс + 5;               // инструкция выполняется в time = Tx.

Процесс B:

// Процесс B..Икс = 3 + z;               // инструкция выполняется в time = Tx.
Рис. 1: График, показывающий потребность в критическом участке

В подобных случаях важен критический раздел. В приведенном выше случае, если A необходимо прочитать обновленное значение Иксодновременное выполнение процесса A и процесса B может не дать требуемых результатов. Чтобы предотвратить это, переменная Икс защищен критическим разделом. Сначала B получает доступ к разделу. Как только B закончит запись значения, A получит доступ к критической секции и переменной. Икс можно прочитать.

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

Реализация критических секций

Реализация критических секций различается в зависимости от операционной системы.

Рис 2: Замки и критические секции в нескольких потоках

Критический участок обычно заканчивается за конечное время,[2] и поток, задача или процесс должны будут ждать фиксированное время, чтобы войти в него (ограниченное ожидание ). Чтобы гарантировать исключительное использование критических секций, требуется некоторый механизм синхронизации при входе и выходе из программы.

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

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

Рис 3: Псевдокод для реализации критической секции

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

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

Использование критических секций

Критические разделы уровня ядра

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

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

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

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

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

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

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

Критические разделы уровня ядра являются основой блокировка программного обеспечения вопрос.

Критические разделы в структурах данных

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

Критические разделы в компьютерных сетях

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

Смотрите также

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

  1. ^ Рейналь, Мишель (2012). Параллельное программирование: алгоритмы, принципы и основы. Springer Science & Business Media. п. 9. ISBN  978-3642320279.
  2. ^ а б Джонс, М. Тим (2008). Программирование приложений GNU / Linux (2-е изд.). [Хингхэм, Массачусетс] Чарльз Ривер Медиа. п. 264. ISBN  978-1-58450-568-6.
  3. ^ Чен, Стенстрем, Гуанчэн, Пер (10–16 ноября 2012 г.). «Анализ критических блокировок: диагностика узких мест критических секций в многопоточных приложениях». Высокопроизводительные вычисления, сети, хранение и анализ (SC), Международная конференция 2012 г.: 1–11. Дои:10.1109 / sc.2012.40. ISBN  978-1-4673-0805-2.
  4. ^ «ИССЛЕДОВАТЕЛЬСКАЯ СТАТЬЯ ПО РЕШЕНИЮ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ПРОБЛЕМЫ КРИТИЧЕСКОГО СЕКЦИИ». Международный журнал передовых технологий и инженерных исследований (IJATER). 1. Ноябрь 2011 г.
  5. ^ Дюбуа, Шойрих, Мишель, Кристоф (1988). «Синхронизация, когерентность и порядок событий в мультипроцессорах». Обзор и серия учебных пособий. 21 (2): 9–21. Дои:10.1109/2.15.
  6. ^ а б Солихин, Ян (17 ноября 2015 г.). Основы параллельной многоядерной архитектуры. ISBN  9781482211184.

внешние ссылки