Многонитевое программирование.
Введение.
Чаще всего описание многонитевого программирования сводится к освещению вопроса о взаимоисключающей блокировке. В этой статье мы тоже не отойдем от этой хорошей практики, уже успевшей стать традицией, но попробуем подойти к задаче с нескольких сторон одновременно.
Статья предназначена для тех, кто хоть немного ориентируется в вопросах по работе с POSIX thread, представляет из себя измышления о дальнейших путях развития технологий в software направлении. Затрагиваются вопросы и по hardware обеспечению. Будет интересна как программистам, так и системным администраторам, интересующимися вопросами программирования.
Взаимоисключающая блокировка.
Стоимость этой основной операции бывает на порядки выше по сравнению со стоимостью операции, действие которой она экранирует. Поэтому и поныне не прекращаются попытки по уменьшению накладных расходов данной операции. Особенно это злободневно для систем с большим количеством процессоров, поскольку в этом случае наиболее заметно падение общей производительности параллельных потоков, завязанных на единую блокировку. Тайминг работы примитива синхронизации становится одной из самых значимых константных составляющих основной переменной в законе Амдала.
Считается, что задача по взаимоисключающей блокировке не имеет алгоритмического решения без атомарных операций. Тут можно лишь рассмотреть каждую из подсистем и выработать список необходимых требований для каждого задействованного модуля. Требования специально закладывается с некоторой гибкостью, чтобы к их выполнению можно было подойти несколькими различными путями.
Но сперва рассмотрим ряд свойств, характерных для ЭВМ разных архитектур. Чтобы не упереться в ограничение одной архитектуры, умышленно отойдем от рассмотрения деталей каждой из существующих платформ, и преимущество будем отдавать абстракциям.
Еще один шаг в сторону от многонитевого программирования
Практически для любого из разделов физики чтобы зафиксировать измеряемое значение (в нашем постоянно меняющемся мире) используется система мер и противовесов с тем расчетом, чтобы исключить или чаще - лишь снизить погрешность измерения.
Компьютерная механика и сложней, и проще - одновременно. Сложней, в том смысле, что любая ошибка, это есть - сбой программы. Проще с той точки зрения, что мы считаем мир компьютера - идеальным. И если это не так, то это опять же - сбой программы. И если для физики допустима погрешность измерения, то в ЭВМ само допущение о погрешностях - неприемлемо. Это можно назвать одной из сторон детерминизма.
Другой стороной детерминизма является то, что его очень сложно обеспечить. Ведь хорошо известно, что ни один процесс не протекает в вакууме. Процессам свойственно вступать во взаимодействие. Процесс без взаимодействия - ноль. Фактически - процесс, который ни на что не влияет - попросту не существует в природе.
Для программ же взаимодействие может протекать по разному. Исходя из заявленной тематике статьи нас будет интересовать прежде всего параллельное исполнение процессов.
Атомарность. Синхронизация. Взаимоисключающая блокировка
Описание детерминированности можно представить как четко определенную очередность операций над четко заданными исходными данным. Когда не только данные формируются в ходе исполнения задачи, но и сама очередь операций является теми самыми исходными данными, мы переходим к понятию «процесса».
В однопроцессорных ЭВМ исполнение процесса происходит по квантам времени, считая затраченные единицы времени (тики) как ресурс, пытаясь его справедливо поделить между имеющимися задачами. Для осуществления взаимодействия, процессор переключался на исполнение роли другого процесса. Переход во взаимоисключающую блокировку можно выделить как ключевую операцию по адаптации разных скоростей поставки и обработки информации в этом взаимодействии. Или, если одним словом - обеспечение «синхронизации».
Для построения взаимоисключающих блокировок (mutex) используется так называемые - атомарные операции. В свою очередь mutex используются для выполнения блока команд в виде псевдо-атомарной операции. Можно предположить, что понятие «атомарность» и «взаимоисключающие блокировки» - абсолютно взаимосвязаны. В ближайшем рассмотрении атомарность операций на уровне железа: инструкций процессора и сопряженных с ней компонент - вовсе не является таковой: они также обеспечиваются той же системой мер и противовесов, характерных и для софверной реализации.
Что для нас означает такая взаимосвязь атомарности исполнения с блокировкой? То, что если у нас существует хотя бы один примитив для работы с mutex-ом, то с её помощью мы сможем осуществить выполнение целого набора команд в виде одной атомарной операции. Недостаток этого приема тот, что подобная неделимость операции достигается за счет приостановления всех остальных параллельно работающих процессов, если они хотя бы гипотетически могут повлиять на действие этой операции. Это также означает, что если в момент осуществления одной атомарной операции потребуются данные, которые поставляются параллельно работающим процессом, то тут возможно возникновение ситуации с взаимоблокировкой процессов. Это есть следствие того, что операции не являются атомарными сами по себе - их действие привносится с помощью дополнительных ухищрений, за что расплатой является (повторюсь еще раз) - простой работы некоторой части параллельно работающих компонент системы (подразумевается самое широкое понятие - операционная система, кластер, сетевое взаимодействие, набор текста - «Hi» с клавиатуры).
Пока остановимся на этом, перейдем к следующему пункту.
Детерминированность блокировок.
Если два разных процесса в некой заданной последовательности подошли к некой общей блокировке для обеспечения некого атомарного действия, то действительный порядок захвата ресурса может отличаться от ожидаемого. Это свойство проистекает из того, что переключение между потоками осуществляется общим планировщиком задач ОС (scheduler), не беря в расчет сложившейся ситуации по порядку блокировки. Можно лишь догадываться, как поведет себя этот механизм. Но даже в вероятностных оценках можно ошибаться более чем на 100%, исходя из разной нагрузки на процессор, перегруженности систем ввода-вывода, настройки ОС, характеристик ОС, и др.
Получается, что детерминированность мы можем получить только на выходе процесса, но никак не в промежутках по частичному выполнению задачи. Но как без промежуточной оценки правильно отбалансировать систему?
Как раз для разрешения этой загвоздки и предназначен планировщик задач ОС.
Блокировка и планировщик задач.
Ввиду этого, а также ввиду того, что программирование ведется в расчете охвата как можно большего количества платформ, то при анализе ситуации с входом в область синхронизации следует представлять в виде черного ящика у которого любой вариант с последовательностью по входу - равновероятен. Это следствие того, что планировщик ОС никак не информируется о входе в контекст-связанный участок кода. Собственно, работа с mutex ничем не отличается от работы с любым другим кодом. Поэтому гарантировать последовательность переключения между потоками зачастую мы не в состоянии.
Так, например, один из потоков может получить (унаследовать) оставшийся квант времени другого потока, если последний только что высвободил примитив синхронизации. Такой пинг-понг между малой группой потоков может продолжаться достаточно долго и выходить за рамки управления шедулинга ОС. И хотя в одном из случаев эта мера может увеличить общую производительность системы за счет особенности архитектуры (в частности - из-за кеша процессора), в другом - может критически повлиять на справедливость распределения ресурсов в глобальном плане, что при высоко нагруженной системе приведет к перекосу, который в свою очередь приведет к перегрузке всей системы.
Даже если преемственность по кванту времени не исполняется, возможно другое стечение обстоятельств, когда переключение между потоками не выполняет никакой полезной работы, поскольку большинство находятся в состоянии ожидания разблокировки. И тем будет больше нагрузка, чем большее число потоков находится в обработке у планировщика ОС. Можно было-бы исключить ожидающий поток из планирования по ресурсу процессора, если это мера не влияла бы на накопленную статистику - исходные данные шедулера. Можно утешиться хотя бы тем, что ожидающий процесс не вызовет переключение контекста на время ожидания по его освобождению другим процессом. Хотя в случае с комбинированным spinlock-ом, это тоже будет не всегда верно.
Как уже было указано выше, планировщик ОС не может выдержать требуемой последовательности по исполнению потоков и для одного и того же ничем не отличающегося куска кода и одних и тех же исходных данных можно ожидать, что на каждое переключение контекста в одном потоке будет проводится два и более - в другом. Ситуация может напоминать комичный сценарий «первым подошел к двери, но всех пропустил вперед себя». Подойдя к наиболее узким рамкам, попытка занять требуемый мутекс или семафор будет терпеть неудачу из-за плохой детерминированности многонитевого процесса.
Даже если при разработке планировщика поставить во главу угла четкую очередность исполнения потоков в одном процессе, мы будем не в состоянии обеспечить атомарность исполнения блока команд, требуемого для блокировки и высвобождения mutex примитива. Однако в наших силах заложить открытие запасных дверей, если к узкому турникету подошло слишком много потоков. Эта мера полностью не устранит проблему правильного планирования задач общесистемым шедулером, но улучшит вероятностное распределение по последовательному входу в процесс синхронизации потоков.
Схема блокировки для систем с одним процессором.
Представим, что программа попыталась заблокировать некий ресурс, но в этот момент произошло прерывание и процесс не был завершен полностью. Последующий процесс попытался заблокировать тот же ресурс и у него все получилось более удачно, и первым был зарегистрирован именно он.
Мы сейчас не говорим о ОС реального времени (хотя и для систем этого рода возможно подобное на едином уровне приоритета) и последующие процессы точно также могут быть добавлены вперед данного: для количества потоков, большем, чем 100 это может привести к «забитию» первого потока, что будет проявляться: в выгрузке его сегментов, вследствии их редкого использования; в наложении штрафа шедулером, когда эти же листы будут подгружаться обратно.
В итоге произошел перекос, который вызван совершенно невероятным стечением обстоятельств. Что характерно, в схеме с SMP процессорами указанные биения более хорошо сглажены из-за большей приемистости в суммарной мощности по контекст-переключениям.
Преемственность потоков.
Желательно, чтобы контекстное прерывание случалось как можно реже, и если уж оно произошло в то время, когда часть действий по входу в режим эксклюзивного обладания mutex примитива уже производилась, то текущий процесс-претендент должен быть на время приостановлен, и вместо входа в цикл spinlock, продолжил бы свое исполнение от имени первичного, как более приоритетного. По завершению обработки mutex цикла, должен быть произведен откат к исходному действию по блокировке этого же, или другого mutex примитива.
Если пренебречь такой схемой, то произойдет накопление множества блокировок, которые так и не перешли в режим ожидания, но соревнуются за его. Перешедшие же в режим блокировки процессы мало того что выстраиваются в цепочку (которую еще можно разбить по приоритетам), но и на время выводятся из списка по планированию ресурсов. Поэтому такой малый шажок в сторону детерминизма просто необходим для увеличения производительности системы.
Работа с ОЗУ.
Современная оперативная память все больше напоминает архитектуру внешнего устройства: представляет из себя адресуемую шину данных, позволяя обращаться к своему содержимому различным устройствам с DMA режимом работы и отдельной высокопроизводительной шиной к SMP процессорам. Ранее атомарная операция обмена содержимого ячейки памяти и регистра уже не является таковой, даже если производители процессоров успешно обеспечивают сохранение совместимости архитектуры.
Как можно оценить, насколько эффективен такой механизм синхронизации ячеек памяти в SMP системах? С чем стоит сравнивать в первую очередь?
Необходимость наращивания функционала у текущих примитивов.
В POSIX threads объявлена функция по уничтожению потоков - pthread_cancel. Функция выглядит небезопасной, особенно в контексте mutex блокировок. То есть одной из причин по появлению этой функции в описании стандарта может являться снятие повисшей блокировки. Но странно, поведение функции, влияние её на окружение в том числе в сочетании с повисшей блокировкой, никак не регламентируется.
К тому же уничтожение потока может оказаться во много крат более сложным процессом, чем банальное снятие блокировки: важно учитывать сложившийся контекст, что параллельно-запущенный поток обеспечить не в состоянии (без использования слабопереносимого кода). Таким образом приходим к тому, что чистку своего окружения должен производить тот же самый поток, что и привел к взаимоблокировке.
Необходимость новых примитивов.
Кроме возможной блокировки есть еще один механизм синхронизации - транзакции. В низкоуровневом языке, таком - как Си, разработать схему, похожую на определенную для SQL - тяжело и громоздко. Процедура отката даже одной функции выглядит тяжело и малопонятно, что уж говорить про рекурсию вызовов. Поэтому главной позицией при проектировании подобного интерфейса скорей является обеспечение защищенности окружения, а не полный откат к исходным данным
Мигрирующая блокировка.
Возникновение повисшей (deadlock) блокировки часто связано с непоследовательной блокировкой двух и более ресурсов. В качестве механизма по обходу сложившейся ситуации может использоваться некий умный процесс, не гарантирующий никакой детерминированности. Так, например, автоматический выбор не способен правильно оценить, какой блокировкой следует пожертвовать.
Что же предлагается задействовать в случае возникновения такой ситуации, и если программист смог оценить вероятность появления этого события? Один из вариантов предлагает метить mutex в контексте заблокировавшего потока, который позволяет перескочить блокировку потоку, открывшего блокировку в другом направлении. Важно, чтобы только один поток определял поведение для срыва режима блокировки, в то время как другой не должен задавать обратных правил. Вложение объектов блокировок может быть неоднократным и определяться в виде правил для конечного автомата.
Стратегия дальнейшего развития многозадачных систем.
Чем сильней возрастает нагрузка на систему, тем выше становятся требования к техническим и программным средствам. Совершенствуясь, аппаратное обеспечение претерпевает значительные модернизации, чтобы обеспечить стабильную работу как ранее работающих программ, так и высокую производительность новых интерфейсов. Кое-где уже сейчас, а в общей тенденции - практически повсеместно, развитие IT-технологии стремится к удивительной ситуации, когда софт меняется значительно реже железа (что же теперь считать более мягким компонентом?). Тенденция связана с тратами на поддержку ранее разработанного ПО, которому не грозит лавинный пробой и перегрев.
Стоимость поддержки программ напрямую зависит от количества задействованных компонент (их API). Поэтому стараясь выработать новые приемы синхронизации следует учитывать, насколько широкий охват получит эта технология в настоящем, и в скором будущем. Прошу поэтому воспринять мои предложения как призыв к дальнейшему обсуждению.
Планирование работы самим процессом.
Основных идеи, две. Давайте по порядку.
Первая идея заключается в привнесении большей интроспекции в пользовательский процесс. Имея сведения, какой квант времени отводится на работу, процесс может более уверенно планировать работу с тем, чтобы как можно большее количество операций было осуществлено за отведенный квант времени. Тут имеется в виду именно процессы, активно взаимодействующие с ядром, поскольку задачи потребляющие только процессорную мощность и так будут работать большую часть времени.
И наоборот: процесс, который работает с системными вызовами в любой момент может быть прерван за счет перехвата управления именно в точке системного вызова (если необходимо ожидать коль сколько-нибудь долго какого-то ресурса). Однако как квантуется задача может знать только сам процесс. Только сообщить об этом ядру ОС он никак не может, кроме как через изменение своего приоритета.
Работа с приоритетами расписана для каждого вида шедулеров любой ОС. Однако для администратора ОС манипулирование инкрементальным значением к приоритету процесса (nice(1)/renice(1), pthread_mutexattr_getprioceiling(3) и другие realtime штучки - например, rtprio(1)) представляется как попытка взвесить золото и драгоценные камни, имея в распоряжении лишь граммовые гири. Да, частично с задачей справляются. Но насколько хорошо - как оценить? Отзывчивостью пользовательского интерфейса в GUI? Почему тогда старые ОС иногда меньше тормозят на том же или даже более старом железе?
Вторая идея более конкретна - в начале работы с mutex-ом дать потоку проработать счетное количество тактов (измеряемых сотнями) со всеми выключенными прерываниями, кроме защиты памяти. Потом, не переключаясь полностью в режим ядра, и если квант времени еще не был полностью выбран, вернуться к выполнению пользовательской задачи уже в обычном режиме работы. Когда потребуется блокировка - через обращение к ядру ОС вновь запрашивается «межкриптонитовый переход» (смотри глоссарий). Если данное количество тиков не может быть выделено, то управление передается другой задаче.
Запрос на межкриптонитовый переход может быть совмещен с первыми операциями по доступу к эксклюзивному замку. По идее, spinlock будет работать наиболее эффективным образом именно в этом случае.
Объект-ориентированность и блокировка.
В объект-ориентированных ЯП существует определение: любое явление, обладающее внутренним состоянием, может быть представлено в виде объекта.
Подойдя к проблеме блокировок нельзя не заметить, что взаимосвязь объектов не исчерпывается изменением одного только внутреннего состояния. Зачастую часть состояния описывается внешними факторами, по отношению к области действия объекта, что можно выразить понятием - «среда».
В результате того, что среда определяется в контексте - в каждый момент времени определяется набор дополнительных объектов по взаимодействию, то тут следует переместить фокус внимания с понятия «объект» на понятие «состояния». Чем больше объектов фигурируют в этом совокупном состоянии, чем больше количество процессов работают над одной задачей, и чем более жесткие требования предъявляются к дискретности их внутреннего содержимого в определенных точках исполнения, тем меньше объект-ориентированности остается от образа представления данных.
Поэтому взаимоблокировка должна приводиться в виде высоко-градуированных механизмов синхронизации.
Глоссарий.
В данном тексте использованы следующие термины:
«межкриптонитовый переход»
наименование произведено от наименования минерала «криптонит», которое в свою очередь обрело популярность в комиксах про Супермена. Подбором этого самоговорящего названия производится попытка внести яркое не двузначное обозначения следующего понятия: межкриптонитовый переход, это - кратковременная стадия процесса, обозначенная жесткими временными рамками, на протяжении которой данный процесс не может быть прерван: обработка любых прерываний откладывается, или маскируются на наинизшем программном уровне ядра. В случае маскировки, функционал по обработке прерываний может задействовать особенности архитектуры целевой ЭВМ, и не должен приводить к критичным модификациям состояния регистров и памяти (критичность определяется в контексте поставленной задачи). Время может отсчитываться по шкале тиков процессора;
Чаще всего описание многонитевого программирования сводится к освещению вопроса о взаимоисключающей блокировке. В этой статье мы тоже не отойдем от этой хорошей практики, уже успевшей стать традицией, но попробуем подойти к задаче с нескольких сторон одновременно.
Статья предназначена для тех, кто хоть немного ориентируется в вопросах по работе с POSIX thread, представляет из себя измышления о дальнейших путях развития технологий в software направлении. Затрагиваются вопросы и по hardware обеспечению. Будет интересна как программистам, так и системным администраторам, интересующимися вопросами программирования.
Взаимоисключающая блокировка.
Стоимость этой основной операции бывает на порядки выше по сравнению со стоимостью операции, действие которой она экранирует. Поэтому и поныне не прекращаются попытки по уменьшению накладных расходов данной операции. Особенно это злободневно для систем с большим количеством процессоров, поскольку в этом случае наиболее заметно падение общей производительности параллельных потоков, завязанных на единую блокировку. Тайминг работы примитива синхронизации становится одной из самых значимых константных составляющих основной переменной в законе Амдала.
Считается, что задача по взаимоисключающей блокировке не имеет алгоритмического решения без атомарных операций. Тут можно лишь рассмотреть каждую из подсистем и выработать список необходимых требований для каждого задействованного модуля. Требования специально закладывается с некоторой гибкостью, чтобы к их выполнению можно было подойти несколькими различными путями.
Но сперва рассмотрим ряд свойств, характерных для ЭВМ разных архитектур. Чтобы не упереться в ограничение одной архитектуры, умышленно отойдем от рассмотрения деталей каждой из существующих платформ, и преимущество будем отдавать абстракциям.
Еще один шаг в сторону от многонитевого программирования
Практически для любого из разделов физики чтобы зафиксировать измеряемое значение (в нашем постоянно меняющемся мире) используется система мер и противовесов с тем расчетом, чтобы исключить или чаще - лишь снизить погрешность измерения.
Компьютерная механика и сложней, и проще - одновременно. Сложней, в том смысле, что любая ошибка, это есть - сбой программы. Проще с той точки зрения, что мы считаем мир компьютера - идеальным. И если это не так, то это опять же - сбой программы. И если для физики допустима погрешность измерения, то в ЭВМ само допущение о погрешностях - неприемлемо. Это можно назвать одной из сторон детерминизма.
Другой стороной детерминизма является то, что его очень сложно обеспечить. Ведь хорошо известно, что ни один процесс не протекает в вакууме. Процессам свойственно вступать во взаимодействие. Процесс без взаимодействия - ноль. Фактически - процесс, который ни на что не влияет - попросту не существует в природе.
Для программ же взаимодействие может протекать по разному. Исходя из заявленной тематике статьи нас будет интересовать прежде всего параллельное исполнение процессов.
Атомарность. Синхронизация. Взаимоисключающая блокировка
Описание детерминированности можно представить как четко определенную очередность операций над четко заданными исходными данным. Когда не только данные формируются в ходе исполнения задачи, но и сама очередь операций является теми самыми исходными данными, мы переходим к понятию «процесса».
В однопроцессорных ЭВМ исполнение процесса происходит по квантам времени, считая затраченные единицы времени (тики) как ресурс, пытаясь его справедливо поделить между имеющимися задачами. Для осуществления взаимодействия, процессор переключался на исполнение роли другого процесса. Переход во взаимоисключающую блокировку можно выделить как ключевую операцию по адаптации разных скоростей поставки и обработки информации в этом взаимодействии. Или, если одним словом - обеспечение «синхронизации».
Для построения взаимоисключающих блокировок (mutex) используется так называемые - атомарные операции. В свою очередь mutex используются для выполнения блока команд в виде псевдо-атомарной операции. Можно предположить, что понятие «атомарность» и «взаимоисключающие блокировки» - абсолютно взаимосвязаны. В ближайшем рассмотрении атомарность операций на уровне железа: инструкций процессора и сопряженных с ней компонент - вовсе не является таковой: они также обеспечиваются той же системой мер и противовесов, характерных и для софверной реализации.
Что для нас означает такая взаимосвязь атомарности исполнения с блокировкой? То, что если у нас существует хотя бы один примитив для работы с mutex-ом, то с её помощью мы сможем осуществить выполнение целого набора команд в виде одной атомарной операции. Недостаток этого приема тот, что подобная неделимость операции достигается за счет приостановления всех остальных параллельно работающих процессов, если они хотя бы гипотетически могут повлиять на действие этой операции. Это также означает, что если в момент осуществления одной атомарной операции потребуются данные, которые поставляются параллельно работающим процессом, то тут возможно возникновение ситуации с взаимоблокировкой процессов. Это есть следствие того, что операции не являются атомарными сами по себе - их действие привносится с помощью дополнительных ухищрений, за что расплатой является (повторюсь еще раз) - простой работы некоторой части параллельно работающих компонент системы (подразумевается самое широкое понятие - операционная система, кластер, сетевое взаимодействие, набор текста - «Hi» с клавиатуры).
Пока остановимся на этом, перейдем к следующему пункту.
Детерминированность блокировок.
Если два разных процесса в некой заданной последовательности подошли к некой общей блокировке для обеспечения некого атомарного действия, то действительный порядок захвата ресурса может отличаться от ожидаемого. Это свойство проистекает из того, что переключение между потоками осуществляется общим планировщиком задач ОС (scheduler), не беря в расчет сложившейся ситуации по порядку блокировки. Можно лишь догадываться, как поведет себя этот механизм. Но даже в вероятностных оценках можно ошибаться более чем на 100%, исходя из разной нагрузки на процессор, перегруженности систем ввода-вывода, настройки ОС, характеристик ОС, и др.
Получается, что детерминированность мы можем получить только на выходе процесса, но никак не в промежутках по частичному выполнению задачи. Но как без промежуточной оценки правильно отбалансировать систему?
Как раз для разрешения этой загвоздки и предназначен планировщик задач ОС.
Блокировка и планировщик задач.
Ввиду этого, а также ввиду того, что программирование ведется в расчете охвата как можно большего количества платформ, то при анализе ситуации с входом в область синхронизации следует представлять в виде черного ящика у которого любой вариант с последовательностью по входу - равновероятен. Это следствие того, что планировщик ОС никак не информируется о входе в контекст-связанный участок кода. Собственно, работа с mutex ничем не отличается от работы с любым другим кодом. Поэтому гарантировать последовательность переключения между потоками зачастую мы не в состоянии.
Так, например, один из потоков может получить (унаследовать) оставшийся квант времени другого потока, если последний только что высвободил примитив синхронизации. Такой пинг-понг между малой группой потоков может продолжаться достаточно долго и выходить за рамки управления шедулинга ОС. И хотя в одном из случаев эта мера может увеличить общую производительность системы за счет особенности архитектуры (в частности - из-за кеша процессора), в другом - может критически повлиять на справедливость распределения ресурсов в глобальном плане, что при высоко нагруженной системе приведет к перекосу, который в свою очередь приведет к перегрузке всей системы.
Даже если преемственность по кванту времени не исполняется, возможно другое стечение обстоятельств, когда переключение между потоками не выполняет никакой полезной работы, поскольку большинство находятся в состоянии ожидания разблокировки. И тем будет больше нагрузка, чем большее число потоков находится в обработке у планировщика ОС. Можно было-бы исключить ожидающий поток из планирования по ресурсу процессора, если это мера не влияла бы на накопленную статистику - исходные данные шедулера. Можно утешиться хотя бы тем, что ожидающий процесс не вызовет переключение контекста на время ожидания по его освобождению другим процессом. Хотя в случае с комбинированным spinlock-ом, это тоже будет не всегда верно.
Как уже было указано выше, планировщик ОС не может выдержать требуемой последовательности по исполнению потоков и для одного и того же ничем не отличающегося куска кода и одних и тех же исходных данных можно ожидать, что на каждое переключение контекста в одном потоке будет проводится два и более - в другом. Ситуация может напоминать комичный сценарий «первым подошел к двери, но всех пропустил вперед себя». Подойдя к наиболее узким рамкам, попытка занять требуемый мутекс или семафор будет терпеть неудачу из-за плохой детерминированности многонитевого процесса.
Даже если при разработке планировщика поставить во главу угла четкую очередность исполнения потоков в одном процессе, мы будем не в состоянии обеспечить атомарность исполнения блока команд, требуемого для блокировки и высвобождения mutex примитива. Однако в наших силах заложить открытие запасных дверей, если к узкому турникету подошло слишком много потоков. Эта мера полностью не устранит проблему правильного планирования задач общесистемым шедулером, но улучшит вероятностное распределение по последовательному входу в процесс синхронизации потоков.
Схема блокировки для систем с одним процессором.
Представим, что программа попыталась заблокировать некий ресурс, но в этот момент произошло прерывание и процесс не был завершен полностью. Последующий процесс попытался заблокировать тот же ресурс и у него все получилось более удачно, и первым был зарегистрирован именно он.
Мы сейчас не говорим о ОС реального времени (хотя и для систем этого рода возможно подобное на едином уровне приоритета) и последующие процессы точно также могут быть добавлены вперед данного: для количества потоков, большем, чем 100 это может привести к «забитию» первого потока, что будет проявляться: в выгрузке его сегментов, вследствии их редкого использования; в наложении штрафа шедулером, когда эти же листы будут подгружаться обратно.
В итоге произошел перекос, который вызван совершенно невероятным стечением обстоятельств. Что характерно, в схеме с SMP процессорами указанные биения более хорошо сглажены из-за большей приемистости в суммарной мощности по контекст-переключениям.
Преемственность потоков.
Желательно, чтобы контекстное прерывание случалось как можно реже, и если уж оно произошло в то время, когда часть действий по входу в режим эксклюзивного обладания mutex примитива уже производилась, то текущий процесс-претендент должен быть на время приостановлен, и вместо входа в цикл spinlock, продолжил бы свое исполнение от имени первичного, как более приоритетного. По завершению обработки mutex цикла, должен быть произведен откат к исходному действию по блокировке этого же, или другого mutex примитива.
Если пренебречь такой схемой, то произойдет накопление множества блокировок, которые так и не перешли в режим ожидания, но соревнуются за его. Перешедшие же в режим блокировки процессы мало того что выстраиваются в цепочку (которую еще можно разбить по приоритетам), но и на время выводятся из списка по планированию ресурсов. Поэтому такой малый шажок в сторону детерминизма просто необходим для увеличения производительности системы.
Работа с ОЗУ.
Современная оперативная память все больше напоминает архитектуру внешнего устройства: представляет из себя адресуемую шину данных, позволяя обращаться к своему содержимому различным устройствам с DMA режимом работы и отдельной высокопроизводительной шиной к SMP процессорам. Ранее атомарная операция обмена содержимого ячейки памяти и регистра уже не является таковой, даже если производители процессоров успешно обеспечивают сохранение совместимости архитектуры.
Как можно оценить, насколько эффективен такой механизм синхронизации ячеек памяти в SMP системах? С чем стоит сравнивать в первую очередь?
Необходимость наращивания функционала у текущих примитивов.
В POSIX threads объявлена функция по уничтожению потоков - pthread_cancel. Функция выглядит небезопасной, особенно в контексте mutex блокировок. То есть одной из причин по появлению этой функции в описании стандарта может являться снятие повисшей блокировки. Но странно, поведение функции, влияние её на окружение в том числе в сочетании с повисшей блокировкой, никак не регламентируется.
К тому же уничтожение потока может оказаться во много крат более сложным процессом, чем банальное снятие блокировки: важно учитывать сложившийся контекст, что параллельно-запущенный поток обеспечить не в состоянии (без использования слабопереносимого кода). Таким образом приходим к тому, что чистку своего окружения должен производить тот же самый поток, что и привел к взаимоблокировке.
Необходимость новых примитивов.
Кроме возможной блокировки есть еще один механизм синхронизации - транзакции. В низкоуровневом языке, таком - как Си, разработать схему, похожую на определенную для SQL - тяжело и громоздко. Процедура отката даже одной функции выглядит тяжело и малопонятно, что уж говорить про рекурсию вызовов. Поэтому главной позицией при проектировании подобного интерфейса скорей является обеспечение защищенности окружения, а не полный откат к исходным данным
Мигрирующая блокировка.
Возникновение повисшей (deadlock) блокировки часто связано с непоследовательной блокировкой двух и более ресурсов. В качестве механизма по обходу сложившейся ситуации может использоваться некий умный процесс, не гарантирующий никакой детерминированности. Так, например, автоматический выбор не способен правильно оценить, какой блокировкой следует пожертвовать.
Что же предлагается задействовать в случае возникновения такой ситуации, и если программист смог оценить вероятность появления этого события? Один из вариантов предлагает метить mutex в контексте заблокировавшего потока, который позволяет перескочить блокировку потоку, открывшего блокировку в другом направлении. Важно, чтобы только один поток определял поведение для срыва режима блокировки, в то время как другой не должен задавать обратных правил. Вложение объектов блокировок может быть неоднократным и определяться в виде правил для конечного автомата.
Стратегия дальнейшего развития многозадачных систем.
Чем сильней возрастает нагрузка на систему, тем выше становятся требования к техническим и программным средствам. Совершенствуясь, аппаратное обеспечение претерпевает значительные модернизации, чтобы обеспечить стабильную работу как ранее работающих программ, так и высокую производительность новых интерфейсов. Кое-где уже сейчас, а в общей тенденции - практически повсеместно, развитие IT-технологии стремится к удивительной ситуации, когда софт меняется значительно реже железа (что же теперь считать более мягким компонентом?). Тенденция связана с тратами на поддержку ранее разработанного ПО, которому не грозит лавинный пробой и перегрев.
Стоимость поддержки программ напрямую зависит от количества задействованных компонент (их API). Поэтому стараясь выработать новые приемы синхронизации следует учитывать, насколько широкий охват получит эта технология в настоящем, и в скором будущем. Прошу поэтому воспринять мои предложения как призыв к дальнейшему обсуждению.
Планирование работы самим процессом.
Основных идеи, две. Давайте по порядку.
Первая идея заключается в привнесении большей интроспекции в пользовательский процесс. Имея сведения, какой квант времени отводится на работу, процесс может более уверенно планировать работу с тем, чтобы как можно большее количество операций было осуществлено за отведенный квант времени. Тут имеется в виду именно процессы, активно взаимодействующие с ядром, поскольку задачи потребляющие только процессорную мощность и так будут работать большую часть времени.
И наоборот: процесс, который работает с системными вызовами в любой момент может быть прерван за счет перехвата управления именно в точке системного вызова (если необходимо ожидать коль сколько-нибудь долго какого-то ресурса). Однако как квантуется задача может знать только сам процесс. Только сообщить об этом ядру ОС он никак не может, кроме как через изменение своего приоритета.
Работа с приоритетами расписана для каждого вида шедулеров любой ОС. Однако для администратора ОС манипулирование инкрементальным значением к приоритету процесса (nice(1)/renice(1), pthread_mutexattr_getprioceiling(3) и другие realtime штучки - например, rtprio(1)) представляется как попытка взвесить золото и драгоценные камни, имея в распоряжении лишь граммовые гири. Да, частично с задачей справляются. Но насколько хорошо - как оценить? Отзывчивостью пользовательского интерфейса в GUI? Почему тогда старые ОС иногда меньше тормозят на том же или даже более старом железе?
Вторая идея более конкретна - в начале работы с mutex-ом дать потоку проработать счетное количество тактов (измеряемых сотнями) со всеми выключенными прерываниями, кроме защиты памяти. Потом, не переключаясь полностью в режим ядра, и если квант времени еще не был полностью выбран, вернуться к выполнению пользовательской задачи уже в обычном режиме работы. Когда потребуется блокировка - через обращение к ядру ОС вновь запрашивается «межкриптонитовый переход» (смотри глоссарий). Если данное количество тиков не может быть выделено, то управление передается другой задаче.
Запрос на межкриптонитовый переход может быть совмещен с первыми операциями по доступу к эксклюзивному замку. По идее, spinlock будет работать наиболее эффективным образом именно в этом случае.
Объект-ориентированность и блокировка.
В объект-ориентированных ЯП существует определение: любое явление, обладающее внутренним состоянием, может быть представлено в виде объекта.
Подойдя к проблеме блокировок нельзя не заметить, что взаимосвязь объектов не исчерпывается изменением одного только внутреннего состояния. Зачастую часть состояния описывается внешними факторами, по отношению к области действия объекта, что можно выразить понятием - «среда».
В результате того, что среда определяется в контексте - в каждый момент времени определяется набор дополнительных объектов по взаимодействию, то тут следует переместить фокус внимания с понятия «объект» на понятие «состояния». Чем больше объектов фигурируют в этом совокупном состоянии, чем больше количество процессов работают над одной задачей, и чем более жесткие требования предъявляются к дискретности их внутреннего содержимого в определенных точках исполнения, тем меньше объект-ориентированности остается от образа представления данных.
Поэтому взаимоблокировка должна приводиться в виде высоко-градуированных механизмов синхронизации.
Глоссарий.
В данном тексте использованы следующие термины:
«межкриптонитовый переход»
наименование произведено от наименования минерала «криптонит», которое в свою очередь обрело популярность в комиксах про Супермена. Подбором этого самоговорящего названия производится попытка внести яркое не двузначное обозначения следующего понятия: межкриптонитовый переход, это - кратковременная стадия процесса, обозначенная жесткими временными рамками, на протяжении которой данный процесс не может быть прерван: обработка любых прерываний откладывается, или маскируются на наинизшем программном уровне ядра. В случае маскировки, функционал по обработке прерываний может задействовать особенности архитектуры целевой ЭВМ, и не должен приводить к критичным модификациям состояния регистров и памяти (критичность определяется в контексте поставленной задачи). Время может отсчитываться по шкале тиков процессора;