Лекция
Привет, Вы узнаете о том , что такое неопределённость параллелизма, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое неопределённость параллелизма, состояние гонки, ресурсный голод, process starvation, проблема обедающих философов , настоятельно рекомендую прочитать все из категории Операционные системы и системное программировние.
состояние гонки (англ. race condition) — ошибка проектирования многопоточной системы или приложения, при которой работа системы или приложения зависит от того, в каком порядке выполняются части кода. Свое название ошибка получила от похожей ошибки проектирования электронных схем (см. Гонки сигналов).
Состояние гонки — «плавающая» ошибка (гейзенбаг), проявляющаяся в случайные моменты времени и «пропадающая» при попытке ее локализовать. Термин состояние гонки относится к инженерному жаргону и появился вследствие неаккуратного дословного перевода английского эквивалента. В более строгой академической среде принято использовать термин неопределенность параллелизма.
Рассмотрим пример кода (на Java).
volatile int x;
// Поток 1:
while (!stop)
{
x++;
…
}
// Поток 2:
while (!stop)
{
if (x%2 == 0)
System.out.println("x=" + x);
…
}
Пусть x=0. Предположим, что выполнение программы происходит в таком порядке:
Самый простой способ решения — копирование переменной x в локальную переменную. Вот исправленный код:
// Поток 2:
while (!stop)
{
int cached_x = x;
if (cached_x%2 == 0)
System.out.println("x=" + cached_x);
…
}
Естественно, этот способ работает только тогда, когда переменная одна и копирование производится за одну машинную команду.
Более сложный, но и более универсальный метод решения — синхронизация потоков, а именно:
int x;
// Поток 1:
while (!stop)
{
synchronized(SomeObject)
{
x++;
}
…
}
// Поток 2:
while (!stop)
{
synchronized(SomeObject)
{
if (x%2 == 0)
System.out.println("x=" + x);
}
…
}
Здесь семантика happens before не требует ключевое слово volatile.
Предположим, что переменных — две (и ключевое слово volatile не действует), а во втором потоке вместо System.out.println стоит более сложная обработка. В этом случае оба метода неудовлетворительны: первый — потому что одна переменная может измениться, пока копируется другая; второй — потому что засинхронизирован слишком большой объем кода.
Эти способы можно скомбинировать, копируя «опасные» переменные в синхронизированном блоке. С одной стороны, это снимет ограничение на одну машинную команду, с другой — позволит избавиться от слишком больших синхроблоков.
volatile int x1, x2;
// Поток 1:
while (!stop)
{
synchronized(SomeObject)
{
x1++;
x2++;
}
…
}
// Поток 2:
while (!stop)
{
int cached_x1, cached_x2;
synchronized (SomeObject)
{
cached_x1 = x1;
cached_x2 = x2;
}
if ((cached_x1 + cached_x2)%100 == 0)
DoSomethingComplicated(cached_x1, cached_x2);
…
}
Очевидных способов выявления и исправления состояний гонки не существует. Лучший способ избавиться от гонок — правильное проектирование многозадачной системы.
Лучше дешевле всего решить проблему race condition — корректно спроектировать архитектуру приложения.
Защита от race condition (гонки потоков) в многопоточных или распределенных приложениях действительно важна для обеспечения корректной и безопасной работы. Ваши предложенные методы - блокировка критических записей, изоляция транзакций и использование мьютексов - являются стандартными методами защиты от гонок потоков, но давайте углубимся в каждый из них и рассмотрим дополнительные способы защиты:
Блокировка критически важных записей:
Изоляция транзакций в базе данных:
Использование мьютексов:
Кроме того, другие методы защиты от гонок потоков включают:
Использование атомарных операций: В некоторых языках программирования и библиотеках есть поддержка атомарных операций, которые позволяют выполнять операции без блокировки, обеспечивая атомарность внутри операции.
Использование каналов и очередей: Вместо явной синхронизации потоков, можно использовать асинхронное взаимодействие через каналы или очереди сообщений, что может уменьшить риск гонок потоков.
Анализ кода и тестирование: Проводите анализ кода и систематическое тестирование, включая тестирование на гонки (race condition testing) с использованием инструментов, таких как Valgrind, ThreadSanitizer, или аналогичных, чтобы выявить потенциальные проблемы.
Защита от гонок потоков - это сложная задача, и подходы могут различаться в зависимости от конкретной ситуации и языка программирования. Важно продумать архитектуру приложения и выбрать подходящие методы для обеспечения безопасности и производительности.
Аппарат лучевой терапии Therac-25 был первым в США медицинским аппаратом, в котором вопросы безопасности были возложены исключительно на программное обеспечение. Об этом говорит сайт https://intellect.icu . Этот аппарат работал в трех режимах:
Эти три режима задавались вращающимся диском, в котором было отверстие с отклоняющими магнитами для электронной терапии, и мишень с рассеивателем для рентгеновской. Из-за состояния гонки между управляющей программой и обработчиком клавиатуры иногда случалось, что в режиме рентгеновской терапии диск оказывался в положении «Электронная терапия», и пациент напрямую облучался пучком электронов в 25 МэВ, что вело к переоблучению. При этом датчики выводили «Нулевая доза», поэтому оператор мог повторить процедуру, усугубляя ситуацию. В результате погибли как минимум четыре пациента.
Часть кода была взята из Therac-6 и Therac-20. При этом в Therac-6 не было рентгеновской терапии, а в Therac-20 были аппаратные меры безопасности, которые не давали включить излучение, когда диск был в неправильном положении.
Существует класс ошибок (и эксплуатирующих их типов атак), позволяющих непривилегированной программе влиять на работу других программ через возможность изменения общедоступных ресурсов (обычно — вре́менных файлов; англ. /tmp race — состояние гонки во вре́менном каталоге), в определенное временно́е окно, в которое файл по ошибке программиста доступен для записи всем или части пользователей системы.
Атакующая программа может разрушить содержимое файла, вызвав аварийное завершение программы-жертвы, или, подменив данные, заставить программу выполнить какое-либо действие на уровне своих привилегий.
Именно по этой причине ПО с серьезными требованиями по безопасности, такое, как веб-браузер, использует случайные числа криптографического качества для именования временных файлов.
Также если в системе нет использования транаций или других способов контроля, например блокировок то возможно выполнять HTTP запросы некортролируемое (некторые не в ожидаемом порядке выполнятся, например определение страны по IP на стороне клиента перед покупкой ), а некторые даже можно выполить несколько раз и , например получить скидку дважды
Ресурсный голод — проблема в информатике, которая делает невозможным выполнение процессом задачи, вызванная постоянным отказом в необходимых ресурсах.
Причиной отказа в ресурсах может быть:
Часто причиной отказа в ресурсах может являться слишком простой алгоритм распределения ресурсов. Например, если планировщик всегда предоставляет ресурс потоку с высоким приоритетом, то при достаточной нагрузке, потоки с низким приоритетом не получат ресурс никогда. И если поток с более высоким приоритетом зависит от результата работы потока с более низким приоритетом, то он несмотря на свой приоритет не сможет завершить задачу. Это называется перестановка приоритетов .
Ресурсный голод похож на взаимную блокировку в том, что выполнение задачи приостанавливается. Но при взаимной блокировке каждый из потоков заблокировал ресурс необходимый другому; а при ресурсном голоде поток просто не получает ресурс, предоставляемый другому потоку.
В компьютерной науке , то проблема обедающих философов является примером проблемы часто используется в параллельной разработке алгоритмов для иллюстрации синхронизации проблемы и методы их решения.
Первоначально он был сформулирован в 1965 году Эдсгером Дейкстрой как упражнение на студенческом экзамене, представленное в терминах конкуренции компьютеров за доступ к периферийным устройствам ленточных накопителей . Вскоре после этого Тони Хоар дал проблеме ее нынешнюю формулировку.
Пятеро безмолвных философов сидят за круглым столом с тарелками спагетти . Вилки помещены между каждой парой смежных философов.
Каждый философ должен попеременно думать и есть. Однако философ может есть спагетти, только если у него есть и левая, и правая вилки. Каждую вилку может держать только один философ одновременно, поэтому философ может использовать вилку, только если она не используется другим философом. После того, как отдельный философ закончит есть, ему нужно отложить обе вилки, чтобы вилки стали доступны другим. Философ может взять вилку только справа или слева, когда они станут доступны, и он не может начать есть, пока не получит обе вилки.
Прием пищи не ограничивается оставшимся количеством спагетти или объемом желудка; предполагается бесконечное предложение и бесконечный спрос.
Проблема в том, как разработать такую дисциплину поведения ( параллельный алгоритм ), чтобы ни один философ не умер от голода; то есть каждый может вечно чередовать еду и размышление, предполагая, что ни один философ не может знать, когда другие могут захотеть поесть или подумать.
Задача была разработана, чтобы проиллюстрировать проблемы, связанные с предотвращением тупика , состояния системы, в котором невозможно продвинуться. Чтобы убедиться, что правильное решение этой проблемы не является очевидным, рассмотрим предложение, в котором каждому философу предписывается вести себя следующим образом:
Эта попытка решения не удалась, потому что она позволяет системе достичь состояния тупика, в котором невозможно продвижение. Это состояние, в котором каждый философ взял вилку слева и ждет, пока вилка справа станет доступной. С помощью данных инструкций это состояние может быть достигнуто, и когда оно будет достигнуто, каждый философ будет вечно ждать, пока другой (тот, что справа) освободит вилку.
Истощение ресурсов может также произойти независимо от тупика, если конкретный философ не может получить обе вилки из-за проблемы с синхронизацией. Например, может существовать правило, согласно которому философы кладут вилку после десяти минут ожидания, пока другая вилка станет доступной, и ждут еще десять минут, прежде чем предпринять следующую попытку. Эта схема исключает возможность тупиковой ситуации (система всегда может перейти в другое состояние), но по-прежнему страдает проблемой динамической блокировки . Если все пять философов появятся в столовой в одно и то же время и каждый поднимет левую вилку одновременно, философы будут ждать десять минут, пока все они сложат вилки, а затем ждут еще десять минут, прежде чем все их возьмут. снова вверх.
Взаимное исключение - основная идея проблемы; философы-обедающие создают общий и абстрактный сценарий, полезный для объяснения проблем этого типа. Неудачи, с которыми могут столкнуться эти философы, аналогичны трудностям, возникающим в реальном компьютерном программировании, когда нескольким программам требуется монопольный доступ к общим ресурсам. Эти вопросы изучаются в параллельном программировании . Первоначальные проблемы Дейкстры были связаны с внешними устройствами, такими как ленточные накопители. Однако трудности, иллюстрируемые проблемой обедающих философов, возникают гораздо чаще, когда несколько процессов получают доступ к обновляемым наборам данных. Сложные системы, такие как ядра операционных систем, используют тысячи блокировок исинхронизации, которая требует строгого соблюдения методов и протоколов, если необходимо избежать таких проблем, как тупик, голодание и повреждение данных.
Это решение проблемы было предложено Дейкстрой . Назначает частичный заказк ресурсам (в данном случае вилкам), и устанавливает соглашение о том, что все ресурсы будут запрашиваться по порядку, и что никакие два ресурса, не связанных по порядку, никогда не будут использоваться одной единицей работы одновременно. Здесь ресурсы (вилки) будут пронумерованы от 1 до 5, и каждая единица работы (философ) всегда будет сначала выбирать вилку с меньшим номером, а затем вилку с большим номером из двух вилок, которые они планируют использовать. Порядок, в котором каждый философ кладет вилки, не имеет значения. В этом случае, если четыре из пяти философов одновременно возьмут вилку с меньшим номером, на столе останется только вилка с самым высоким номером, поэтому пятый философ не сможет взять вилку. Более того, только один философ будет иметь доступ к этой вилке с самым большим номером,
Хотя решение иерархии ресурсов позволяет избежать тупиковых ситуаций, это не всегда практично, особенно когда список требуемых ресурсов не известен заранее. Например, если единица работы содержит ресурсы 3 и 5, а затем определяет, что ей нужен ресурс 2, она должна освободить 5, затем 3 перед получением 2, а затем она должна повторно получить 3 и 5 в этом порядке. Компьютерные программы, которые обращаются к большому количеству записей базы данных, не работали бы эффективно, если бы от них требовалось освободить все записи с более высокими номерами перед доступом к новой записи, что делает этот метод непрактичным для этой цели.
Решение иерархии ресурсов несправедливо . Если философ 1 не спешит брать вилки, а философ 2 быстро думает и снова выбирает вилки, то философу 1 никогда не удастся подобрать обе вилки. Справедливое решение должно гарантировать, что каждый философ в конечном итоге съест, независимо от того, насколько медленно этот философ движется относительно других.
Другой подход состоит в том, чтобы гарантировать, что философ может взять только обе вилки или ни одной, представив арбитра, например официанта. Чтобы забрать вилки, философ должен спросить разрешения у официанта. Официант дает разрешение только одному философу за раз, пока философ не возьмет обе вилки. Всегда можно класть вилку. Официант может быть реализован как мьютекс . Помимо введения нового центрального объекта (официанта), этот подход может привести к уменьшению параллелизма: если философ ест, а один из его соседей запрашивает вилки, все другие философы должны ждать, пока этот запрос не будет выполнен, даже если вилки для них еще доступны.
Решение, предложенное Уильямом Столлингсом , состоит в том, чтобы позволить максимум n-1 философу сесть в любое время. Последнему философу придется ждать (например, используя семафор), пока кто-нибудь закончит обед, прежде чем он «сядет» и запросит доступ к любой вилке. Это гарантирует, что по крайней мере один философ всегда может овладеть обеими вилками, позволяя системе развиваться.
В 1984 году К. Мани Чанди и Дж. Мисра предложили другое решение проблемы обедающих философов, позволяющее произвольным агентам (пронумерованным P 1 , ..., P n ) бороться за произвольное количество ресурсов, в отличие от Решение Дейкстры. Он также полностью распределен и не требует центральной власти после инициализации. Однако это нарушает требование «философы не разговаривать друг с другом» (из-за сообщений-запросов).
Это решение также обеспечивает высокую степень параллелизма и решает сколь угодно большие проблемы.
Это также решает проблему голодания. Ярлыки "чистый / грязный" служат способом отдать предпочтение наиболее "голодным" процессам и недостатком процессам, которые только что "съели". Можно сравнить их решение с решением, в котором философам не разрешается есть дважды подряд, не позволяя другим пользоваться вилками в перерыве между ними. Решение Чанди и Мисры более гибкое, чем это, но в нем есть элемент, склоняющийся в этом направлении.
В своем анализе они выводят систему уровней предпочтения на основе распределения вилок и их чистых / грязных состояний. Они показывают, что эта система может описывать ориентированный ациклический граф , и если это так, то операции в их протоколе не могут превратить этот граф в циклический. Это гарантирует невозможность возникновения тупиковой ситуации. Однако, если система инициализируется в совершенно симметричном состоянии, как все философы, держащие свои левые вилки, тогда граф с самого начала является циклическим, и их решение не может предотвратить тупик. Инициализация системы так, чтобы у философов с более низкими идентификаторами были грязные вилки, гарантирует, что граф изначально является ацикличным.
Прочтение данной статьи про неопределённость параллелизма позволяет сделать вывод о значимости данной информации для обеспечения качества и оптимальности процессов. Надеюсь, что теперь ты понял что такое неопределённость параллелизма, состояние гонки, ресурсный голод, process starvation, проблема обедающих философов и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Операционные системы и системное программировние
Ответы на вопросы для самопроверки пишите в комментариях, мы проверим, или же задавайте свой вопрос по данной теме.
Комментарии
Оставить комментарий
Операционные системы и системное программировние
Термины: Операционные системы и системное программировние