Лекция: Производительность отдельных применений

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

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

Как было отмечено в разделе 3.2,(Л1) при условиях многопроцессорности может быть реализовано настоящий параллелизм, когда отдельные части программы выполняются одновременно несколькими процессорами.

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

Кроме того, даже если программа является многопоточной, максимальное улучшение ее производительности ограничено в соответствии с законом Амдала

где S — выигрыш в скорости выполнения; Т— общий объем кода, Тпосл — объем кода, который не может быть выполнен параллельно, п — количество процессоров.

Планирование в многопроцессорных системах

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

В этом разделе рассмотрим некоторые подходы к организации планирования, которые учитывают эти факторы, а в следующем — важно понятие родства процессора, который влияет на организацию планирования в многопроцессорных системах.

Планирование с делением времени

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

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

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

Планирование с делением пространства

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

Самым эффективным алгоритмом планирования с делением пространства является бригадное планирование(gang scheduling). Этот алгоритм работает так.

1. Связаные потоки (например, потоки одного процесса) одновременно запускают на выполнение на максимально возможном количестве процессоров. Такие потоки составляют бригаду (gang).

2. Все потоки бригады выполняются на протяжении одинакового для всех кванта времени.

3. После окончания кванта времени происходит полное перепланировывание для всех процессоров и выполнение начинают потоки другой бригады.

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

Работа этого алгоритма показана на рис. 11.1. По вертикали отложены моменты времени, по горизонтали — процессоры. Буквами обозначены процессы (бригады), цифрами индекса — номера потоков.

Рис.11.1 Бригадное планирование