В параллельном программировании одновременный доступ к общим ресурсам может привести к неожиданному или ошибочному поведению, поэтому части программы, в которых осуществляется доступ к общему ресурсу, должны быть защищены способами, исключающими одновременный доступ. Этот защищенный раздел является критическим разделом или критической областью. Он не может выполняться одновременно более чем одним процессом. Обычно критическая секция обращается к совместно используемому ресурсу, такому как структура данных , периферийное устройство или сетевое соединение, которые не будут работать правильно в контексте множественных одновременных доступов. [1]
Необходимость в критических секциях [ править ]
Различные коды или процессы могут состоять из одной и той же переменной или других ресурсов, которые необходимо прочитать или записать, но результаты которых зависят от порядка, в котором происходят действия. Например, если переменная x должна быть прочитана процессом A, а процесс B должен записать в ту же самую переменную x в одно и то же время, процесс A может получить либо старое, либо новое значение x .
Процесс А:
// Процесс A . . б = х + 5 ; // инструкция выполняется в time = Tx .Процесс B:
// Процесс B . . х = 3 + z ; // инструкция выполняется в time = Tx .
В таких случаях важен критический раздел. В приведенном выше случае, если A необходимо прочитать обновленное значение x , одновременное выполнение процесса A и процесса B может не дать требуемых результатов. Чтобы этого не произошло , переменная x защищена критической секцией. Сначала B получает доступ к разделу. Как только B закончит запись значения, A получит доступ к критическому разделу, и переменная x может быть прочитана.
Тщательно контролируя, какие переменные изменяются внутри и вне критической секции, предотвращается одновременный доступ к общей переменной. Критическая секция обычно используется, когда многопоточная программа должна обновить несколько связанных переменных без того, чтобы отдельный поток вносил конфликтующие изменения в эти данные. В связанной ситуации может использоваться критическая секция, чтобы гарантировать, что общий ресурс, например, принтер, может быть доступен только одному процессу за раз.
Реализация критических секций [ править ]
Реализация критических секций различается в зависимости от операционной системы.
Критическая секция обычно завершается за конечное время [2], и поток, задача или процесс должны ждать в течение фиксированного времени, чтобы войти в нее ( ограниченное ожидание ). Чтобы гарантировать исключительное использование критических секций, требуется некоторый механизм синхронизации при входе и выходе из программы.
Критический раздел - это часть программы, требующая взаимного исключения доступа.
Как показано на рис. 2, [3] в случае взаимного исключения (Mutex), один поток блокирует критическую секцию, используя методы блокировки, когда ему требуется доступ к общему ресурсу, а другие потоки должны ждать своей очереди, чтобы войти в секция. Это предотвращает конфликты, когда два или более потока совместно используют одно и то же пространство памяти и хотят получить доступ к общему ресурсу. [2]
Самый простой способ предотвратить любое изменение управления процессором внутри критической секции - реализовать семафор. В однопроцессорных системах это можно сделать, отключив прерывания при входе в критическую секцию, избегая системных вызовов, которые могут вызвать переключение контекста внутри секции, и восстанавливая прерывания в их предыдущее состояние при выходе. Любой поток выполнения, входящий в любой критический раздел в любом месте системы, с этой реализацией будет препятствовать тому, чтобы любой другой поток, включая прерывание, получил время обработки на ЦП - и, следовательно, от входа в любой другой критический раздел или, действительно, любой код как бы то ни было - до тех пор, пока исходный поток не покинет критическую секцию.
Этот метод грубой силы можно улучшить с помощью семафоров . Чтобы войти в критическую секцию, поток должен получить семафор, который он освобождает при выходе из секции. Другим потокам запрещается входить в критическую секцию одновременно с исходным потоком, но они могут получить контроль над ЦП и выполнить другой код, включая другие критические секции, которые защищены разными семафорами. Блокировка семафоров также имеет ограничение по времени для предотвращения состояния взаимоблокировки, в котором блокировка приобретается одним процессом на бесконечное время, останавливая другие процессы, которым необходимо использовать общий ресурс, защищенный критической секцией.
Использование критических секций [ править ]
Критические разделы уровня ядра [ править ]
Обычно критические секции предотвращают миграцию потоков и процессов между процессорами и вытеснение процессов и потоков прерываниями и другими процессами и потоками.
Критические секции часто допускают вложение. Вложение позволяет входить и выходить из нескольких критических секций с небольшими затратами.
Если планировщик прерывает текущий процесс или поток в критическом разделе, планировщик либо разрешит выполняющемуся в данный момент процессу или потоку выполнить работу до завершения критического раздела, либо запланирует процесс или поток для другого полного кванта. Планировщик не будет переносить процесс или поток на другой процессор и не будет планировать запуск другого процесса или потока, пока текущий процесс или поток находится в критической секции.
Точно так же, если прерывание происходит в критической секции, информация о прерывании записывается для будущей обработки, и выполнение возвращается процессу или потоку в критической секции. [4] После выхода из критической секции и в некоторых случаях завершения запланированного кванта будет выполнено ожидающее прерывание. Концепция кванта планирования применяется к « циклическому » и подобным политикам планирования .
Поскольку критические секции могут выполняться только на том процессоре, в который они введены, синхронизация требуется только внутри исполняющего процессора. Это позволяет входить и выходить из критических секций практически без затрат. Никакой межпроцессорной синхронизации не требуется. Требуется только синхронизация потока инструкций [5] . Большинство процессоров обеспечивают необходимую синхронизацию путем простого прерывания текущего состояния выполнения. Это позволяет критическим разделам в большинстве случаев быть не чем иным, как подсчетом введенных критических разделов на процессор.
Улучшения производительности включают выполнение ожидающих прерываний при выходе из всех критических секций и возможность запуска планировщика при выходе из всех критических секций. Кроме того, ожидающие прерывания могут быть переданы для выполнения другим процессорам.
Критические секции не должны использоваться как долговременный блокирующий примитив. Критические разделы должны быть достаточно короткими, чтобы их можно было вводить, выполнять и выходить без каких-либо прерываний со стороны оборудования и планировщика.
Критические разделы уровня ядра являются основой проблемы блокировки программного обеспечения .
Критические разделы в структурах данных [ править ]
При параллельном программировании код делится на потоки. Чтения-записи конфликтующие переменные разделяются между потоками , и каждый поток имеет копию из них. Структуры данных, такие как связанные списки , деревья , хеш-таблицы и т. Д., Имеют переменные данных, которые связаны и не могут быть разделены между потоками, и, следовательно, реализация параллелизма очень сложна. [6] Для повышения эффективности реализации структур данных несколько операций, таких как вставка, удаление, поиск, должны выполняться параллельно. При выполнении этих операций могут быть сценарии, в которых один и тот же элемент просматривается одним потоком и удаляется другим. В таких случаях вывод может быть ошибочным.. Поток, ищущий элемент, может иметь попадание, тогда как другой поток может удалить его сразу после этого. Эти сценарии вызовут проблемы в работе программы из-за предоставления ложных данных. Чтобы предотвратить это, один из способов заключается в том, что вся структура данных может храниться в критическом разделе, чтобы одновременно выполнялась только одна операция. Другой метод - заблокировать используемый узел в критической секции, чтобы другие операции не использовали тот же узел. Таким образом, использование критического раздела гарантирует, что код обеспечивает ожидаемые результаты. [6]
Критические разделы в компьютерных сетях [ править ]
Критические секции также необходимы в компьютерных сетях. Когда данные поступают в сетевые сокеты , они могут не поступать в упорядоченном формате. Скажем, программе «X», запущенной на машине, необходимо собрать данные из сокета, переупорядочить их и проверить, не пропало ли что-нибудь. Хотя эта программа работает с данными, никакая другая программа не должна обращаться к тому же сокету для этих конкретных данных. Следовательно, данные сокета защищены критическим разделом, так что программа «X» может использовать его исключительно.
См. Также [ править ]
- Блокировка (информатика)
- Взаимное исключение
- Алгоритм пекарни Лэмпорта
- Алгоритм Деккера
- Алгоритм Эйзенберга и Макгуайра
- Алгоритм Шиманского
- Алгоритм Петерсона
Ссылки [ править ]
- ^ Raynal, Мишель (2012). Параллельное программирование: алгоритмы, принципы и основы . Springer Science & Business Media. п. 9. ISBN 978-3642320279.
- ^ a b Джонс, М. Тим (2008). Программирование приложений GNU / Linux (2-е изд.). [Хингхэм, Массачусетс] Чарльз Ривер Медиа. п. 264. ISBN 978-1-58450-568-6.
- ^ Chen, Штенштрёй, Гуанчэн, Per (ноябрь 10-16, 2012). «Анализ критических блокировок: диагностика узких мест критических секций в многопоточных приложениях». Высокопроизводительные вычисления, сети, хранение и анализ (SC), Международная конференция 2012 : 1–11. DOI : 10,1109 / sc.2012.40 . ISBN 978-1-4673-0805-2.
- ^ «ИССЛЕДОВАТЕЛЬСКАЯ СТАТЬЯ ПО РЕШЕНИЮ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ПРОБЛЕМЫ КРИТИЧЕСКОГО РАЗДЕЛА» . Международный журнал передовых технологий и инженерных исследований (IJATER) . 1 . Ноябрь 2011 г.
- ^ Дюбуа, Шойрих, Мишель, Кристоф (1988). «Синхронизация, согласованность и порядок событий в многопроцессорных системах» . Обзор и серия учебных пособий . 21 (2): 9–21. DOI : 10,1109 / 2,15 .
- ^ a b Солихин, Ян (17 ноября 2015 г.). Основы параллельной многоядерной архитектуры . ISBN 9781482211184.
Внешние ссылки [ править ]
- Документация по критическому разделу на веб-странице Microsoft Docs
- Учебник по критическим разделам
- Примеры кода для Mutex
- Учебник по семафорам
- Блокировка конкуренции в критических секциях
