Разделение времени

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

алгоритм планирования для работы с независимыми потоками заключается в поддержке для готовых к работе потоков единой структуры данных для всей системы, возможно, в виде простого списка, но, скорее всего, в виде набора списков для потоков с разными приоритетами (рис.

8.12, а). Здесь показаны 16 центральных процессоров, которые в данный момент заняты работой, и набор из готовых к работе 14 потоков, имеющих разные приоритеты. Первым процессором, завершившим свою работу (или столкнувшимся с блокировкой своего потока), станет центральный процессор 4, который заблокирует очереди планируемых потоков и выберет поток А, имеющий наивысший приоритет (рис. 8.12, б). Затем освободится центральный процессор 12, который выберет поток В (рис. 8.12, в). Пока потоки совершенно не связаны друг с другом, такого рода планирование будет вполне разумным и легко реализуемым выбором.

Рис. 8.12. Использование единой структуры данных для планирования работы мультипроцессора


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

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

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

Чтобы обойти эту аномальную ситуацию, на некоторых системах используется разумное планирование (smart scheduling), при котором поток, получивший спинблокировку, устанавливает флажок, видимый всему процессу, чтобы показать, что он в данный момент владеет спин-блокировкой (Zahorjan et al., 1991).

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

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

На некоторых мультипроцессорах все это берется в расчет и используется так называемое родственное планирование (affinity scheduling) (Vaswani and Zahorjan, 1991). Основной замысел состоит в стремлении выполнять поток на том же самом центральном процессоре, на котором он запускался в последний раз.

Один из способов поддержания такой родственной связи заключается в использовании двухуровневого алгоритма планирования (two-level scheduling algorithm). При

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

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

<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

Еще по теме Разделение времени:

  1. § 36 Непосредственное вступление прямых наследников. – Трансмиссия. – Утверждение в наследстве. – Принятие наследства и отречение. – Последствие принятия. – Принятие по описи и разделение долгов. – Раздел наследства. – Возвратные учеты. – Разделение прав и ответственности. – Передел. – Наследство у мусульман.
  2. Управление временем «Нам некогда делать это как следует - у нас хватает времени лишь на то, чтобы потом все переделывать».
  3. Линия времени "во времени"
  4. Разделенная двойственность.
  5. § 2. Разделение властей
  6. Особенности принципа разделения властей
  7. Причины разделения групп.
  8. Разделение экрана
  9. Разделение мужчины и женщины
  10. Глава 14 РАЗДЕЛЕНИЕ РЕАЛЬНОСТИ
  11. Разделение верха и низа
  12. Разделение внешнего и внутреннего