Управление процессами и ресурсами в автономных многопроцессорных вычислительных машинах

 

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

 

В предыдущих разделах рассматривались вопросы реализации ОС, функционирующих на автономных (или так называемых «центра-лизованных») однопроцессорных ВМ. Для решения ряда сложных задач обработки информации спроектированы и практически используются многопроцессорные вычислительные машины (часто для краткости называемые «мультипроцессорами»), в которых устанавливается несколько центральных процессоров, имеющих полный доступ к общей разделяемой памяти. По своему основному содержанию операционные системы для такихмногопроцессорных машин представляют собой обычные ОС, выполняющие традиционные функции по обработке системных вызовов, управлению памятью, обслуживанию файловой системы, управлению устройствами ввода-вывода. Главным отличием в реализации ОС для многопроцессорных ВМ является изменение содержания состояния процессов «выполнение». В этом состоянии может находиться не один процесс (как в однопроцессорных ВМ), а сразу несколько процессов, выполняющихся на разных процессорах многопроцессорной ВМ. Это требует более сложных алгоритмов планирования и синхронизации процессов, а также специфических методов организации и управления ресурсами в операционных системах для многопроцессорных ВМ.

Возможны различные варианты организации операционных систем многопроцессорных машин.

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

Следует отметить следующие аспекты данной схемы.

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

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

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

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

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

При другом способе организации ОС для многопроцессорных ВМ используется всего одна копия операционной системы, работающая только на центральном процессоре 1. Все системные вызовы перенаправляются для обработки на центральный процессор 1. Центральный процессор 1 может также выполнять процессы пользователя, если у него будет оставаться для этого время. Такая схема называется «ведущий-ведомый», так как центральный процессор 1 является ведущим (или главным), а все остальные процессоры – или ведомыми (или подчиненными).

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

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

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

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

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

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

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

 

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

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

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

Мультипроцессоры обладает рядом определенных свойств, которые отсутствуют в однопроцессорных ВМ. Например, на мультипроцессор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. Наконец, потре­буется переключение обратно на исходный поток, результатом которого снова бу­дут промахи кэша. Циклы процессора, потраченные на эти два переключения кон­текста, плюс промахи кэша представляют собой существенные накладные расходы.

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

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

 

Резюме

 

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

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

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

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

Способ разреше­ния указанных выше проблем состоит в связывании мьютекса (то есть блокировки) с ОС, в результате чего вся система превращается в одну боль­шую критическую область. Эффективным механизмом также является «расщепление» ОС на неза­висимые критические области, не взаимодействующие друг с другом.

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

Простейший алгоритм планирова­ния независимых процессов – поддержание единой струк­туры данных для готовых процессов.

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

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

При планировании процессов, связанных друг с другом каким-либо способом, используется алгоритм «совместного использования (или разделения) пространства».

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

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

Контрольные вопросы и задания

1. В чем заключается основное отличие в реализации ОС для многопроцессорных ВМ от ОС однопроцессорных ВМ?

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

3. Какими достоинствами и недостатками обладает способ организации ОС многопроцессорных ВМ по схеме «ведущий-ведомый»?

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

5. Какие факторы усложняют планирование процессов в многопроцессорных ВМ по сравнению с аналогичным планированием в однопроцессорных машинах?

6. Какой механизм применяется для преодоления удержания процессом спин-блокировки?

7. Представьте достоинства использования двухуровневого алгоритма планирования процессов в многопроцессорных ВМ.

8. Опишите алгоритм «совместного использования пространства», его преимущества и недостатки.

9. Каким образом выполняется синхронизацияцентральных процессоров в многопроцессорных ВМ?