Планирование и синхронизация в многопроцессорных вычислительных машинах

На однопроцессорной ВМ планирование одномерно. Единственный вопрос, на который должен быть каждый раз получен ответ, – какой процесс должен быть запущен следующим? На мультипроцессоре планирование двумерно. Планировщик должен решить, какой процесс и на котором центральном процессоре запустить. Это дополнительное измерение существенно усложняет планирование процессов на многопроцессорных ВМ. Другой усложняющий фактор состоит в том, что в ряде случаев все процессы являются независимыми, тогда как в других случаях они формируют груп­пы.

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

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

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

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

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

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

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

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

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

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

Если процесс в однопроцессорной ВМ обращается к системному вызову, ко­торый требует доступа к некой критической таблице, программа ядра может про­сто запретить прерывания, прежде чем обратиться к таблице. Однако на мульти­процессоре запрет прерывания повлияет только на один центральный процессор, выполнивший команду запрета прерываний. Остальные центральные процессоры продолжат свою работу и смогут получить доступ к критической таблице. Требу­ется специальный мьютекс-протокол, который будет выполняться всеми централь­ными процессорами, чтобы гарантировать работу взаимного исключения.

Основой любого практического мьютекс-протокола является команда процессо­ра, позволяющая исследовать и изменить слово в памяти за одну операцию. Для этого можно использовать команду TSL (Test and Set Lock – проверить и установить блокировку), которая считывает слово памяти в регистр процессора. Одновременно она записывает 1 (или другое ненулевое значение) в слово памяти. Конечно, для выполнения операций чтения и записи памяти требуется два цикла шины. В однопроцессорной ВМ, поскольку одна команда процессора не мо­жет быть прервана на полпути, команда TSL работает должным образом. Для решения проблемы взаимного исключения в многопроцессорной ВМ команда TSL сначала должна блокировать шину, не допуская обращения к ней других центральных процессоров, затем выполнить оба обращения к памяти, после чего разблокировать шину. Как правило, для блоки­ровки шины сначала выполняется обычный запрос шины по стандартному прото­колу, затем устанавливается в 1 некая специальная линия шины. Пока эта линия шины установлена в 1, никакой другой центральный процессор не может получить к ней доступ. Такая команда может быть выполнена только на шине, у которой есть необходимые специальные линии и аппаратный протокол для их использования (современные шины обладают подобными свойствами). Если команда TSL корректно реализована и применяется, она гарантирует пра­вильную работу взаимного исключения. Однако подобный способ реализации взаимного исключения использует спин-блокировку, так как запрашивающий центральный процессор находится в цикле опроса блокировки с максимальной скоростью. Этот метод является не только тратой времени запрашивающего цент­рального процессора (или процессоров), но он также может накладывать значительную нагрузку на шину или память, существенно снижая скорость работы всех остальных центральных процессоров, пытающихся выполнять свою обычную работу.

Наличие кэширования не устра­няет проблему конкуренции за шину. Теоретически, как только за­прашивающий центральный процессор прочитал слово блокировки, он должен по­лучить его копию в свой кэш. Пока ни один другой центральный процессор не предпринимает попыток использовать это слово, запрашивающий центральный процессор может работать с ним в своем кэше. Когда центральный процессор, владеющий словом блокировки, записывает в него 1, протокол кэша автомати­чески помечает как недействитель-ные все копии этого слова в удаленных кэшах, требуя получения правильных значений. Однако проблема заключается в том, что кэш оперирует блоками по 32 или 64 байт. Обычно слова, окружающие слово блокировки, нужны центральному процессору, удерживающему это слово. Поскольку команда TSL представляет собой запись (так как она модифицирует слово блокировки), ей требуется монопольный доступ к блоку кэша, содержащему слово блокировки. Таким образом, каждая команда TSL помечает блок кэша владельца блокировки как недействительный и получает при­ватную, эксклюзивную копию для запрашивающего центрального процессора. Как только владелец блокировки изменит слово, соседнее с блокировкой, блок кэша перемещается на его процессор. В результате весь блок кэша, содержащий слово блокировки, постоянно челночно перемещается от центрального про­цессора, удерживающего блокировку, к центральному процессору, пытающемуся ее получить. Все это создает довольно значительный и совершенно излишний трафик шины.

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

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

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

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

Если допустить, что оба варианта (опрос в цикле и переключение потоков) вы­полнимы, возникает следующая ситуация. Циклический опрос напрямую расхо­дует процессорное время. Периодическая проверка состояния мьютекса не явля­ется продуктивной работой. Переключение процессов, однако, также расходует циклы процессора, так как для этого требуется сохранить текущее состояние пото­ка, получить мьютекс списка свободных процессов, выбрать из этого списка поток, загрузить его состояние и передать ему управление. Более того, кэш центрального процессора будет содержать не те блоки, поэтому после переключения потоков возможно много промахов кэша. Также вероятны ошибки TLB. Наконец, потре­буется переключение обратно на исходный поток, результатом которого снова бу­дут промахи кэша. Циклы процессора, потраченные на эти два переключения кон­текста, плюс промахи кэша представляют собой существенные накладные расходы.

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

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