Параллельное и распределенное программирование на С++

Хьюз Камерон

Атрибуты stackaddr и stacksize определяют базовый адрес и минимальный размер (в байтах) стека, выделяемого для создаваемого потока, соответственно

Атрибут stackaddr определяет базовый адрес стека, выделяемого для создаваемого потока

Атрибут stacksize определяет минимальный размер стека в байтах, выделяемого для создаваемого потока

Планирование потоков

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

с потоками из одного процесса. Потоки помещаются в очереди готовых потоков, отсортированные по значению их приоритета. Потоки с одинаковым приоритетом назначаются процессорам в соответствии с некоторой стратегией планирования. Если система

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

Состояния потоков

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

Рис. 4.4. Состояния потоков и переходы между ними

При получении этого сигнала поток переходит из состояния останова в состояние готовности. Переход потока из одного состояния в другое является своего рода сигналом о наступлении некоторого события. Переход конкретного потока из состояния готовности _{в со} стояние выполнения происходит потому, что система выбрала именно его для выполнения, т.е. поток отправляется (dispatched) на процессор. Поток снимается, или выгружается (preempted), с процессора, если он делает запрос на ввод-вывод данных (или какой-либо иной запрос к ядру), или если существуют какие-то причины внешнего характера.

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

Планирование потоков и область конкуренции

Область конкуренции потоков определяет, с каким множеством потоков будет соперничать рассматриваемый поток за использование процессорного времени. Если поток имеет область конкуренции уровня процесса, он будет соперничать за ресурсы с потоками того же самого процесса. Если же поток имеет системную область конкуренции, он будет соперничать за процессорный ресурс с равными ему по правам потоками (из одного с ним процесса) и с потоками других процессов. Пусть, например, как показано на рис. 4.5, существуют два процесса в мультипроцессорной среде, которая включает три процессора. Процесс А имеет четыре потока, а процесс В — три. Для процесса А «расстановка сил» такова: три (из четырех его потоков) имеют область конкуренции уровня процесса, а один— уровня системы. Для процесса В такая «картина»: два (из трех его потоков) имеют область конкуренции уровня процесса, а один— уровня системы. Потоки процесса А с процессной областью конкуренции соперничают за процессор А, а потоки процесса В с такой же (процессной) областью конкуренции соперничают за процессор С. Потоки процессов А и В с системной областью конкуренции соперничают за процессор В.

ПРИМЕЧАНИЕ: потоки при моделировании их реального поведения в приложении Должны иметь системную область конкуренции.

Стратегия планирования и приоритет

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

процессорное время. В операционной системе с приоритетами выполняющийся поток снимается с процессора, если в состояние готовности переходит

поток с более высоким приоритетом, обладающий при этом тем же уровнем области конкуренции. Например, как показано на рис. 4.5, потоки с процессной областью конкуренции соревнуются за процессор с потоками того же процесса, имеющими такой же уровень области конкуренции. Процесс А имеет два потока с приоритетом 3, и один из них назначен процессору. Как только поток с приоритетом 2 заявит о своей готовности, активный поток будет вытеснен, а процессор займет поток с более высоким приоритетом. Кроме того, в процессе В есть два потока (процессной области конкуренции) с приоритетом 1 (приоритет 1 выше приоритета 2). Один из этих потоков назначается процессору. И хотя другой поток с приоритетом 1 готов к выполнению, он не вытеснит поток с приоритетом 2 из процесса А, поскольку эти потоки соперничают за процессор в рамках своих процессов. Потоки с системной областью конкуренции и более низким приоритетом не вытесняются ни одним из потоков из процессов А или В. Они соперничают за процессорное время только с потоками, имеющими системную область конкуренции.

Рис. 4.5. Планирование потоков (с процессной и системной областями конкуренции) в мультипроцессорной среде

Как упоминалось в главе 3, очереди готовности организованы в виде отсортированных списков, в которых каждый элемент представляет собой уровень приоритета. Под уровнем приоритета понимается очередь потоков с одинаковым значением приоритета. Все потоки одного уровня приоритета назначаются процессору с использованием стратегии планирования: FIFO (сокр. от First In First OuU т.е. первым прибыл, первым обслужен), RR (сокр. от round-robin, т.е. циклическая) или какой-либо другой. При использовании стратегии планирования FIFO поток, квант процессорного времени которого истек, помещается в головную часть очереди соответствующего приоритетного уровня, а процесс назначается следующему потоку из очереди. Следовательно, поток будет выполняться до тех пор, пока он не завершит выполнение, не перейдет в состояние ожидания («заснет») или не получит сигнал остановиться. Когда «спящий» поток «просыпается», он помещается в конец очереди соответствующего приоритетного уровня. Стратегия планирования RR аналогична FIFO стратегии, за исключением того, что по истечении кванта процессорного времени поток помещается не в начало, а в конец «своей» очереди. Циклическая стратегия планирования (RR) считает все потоки обладающими одинаковыми приоритетами и каждому потоку предоставляет процессор только в течение некоторого кванта времени. Поэтому выполнение задач получается попеременным. Например, программа, которая выполняет поиск файлов по заданным ключевым словам, разбивается на два потока. Один поток (1) находит все файлы с заданным расширением и помещает их пути в контейнер. Второй поток (2) выбирает имена файлов из контейнера, просматривает каждый файл на предмет наличия в нем заданных ключевых слов, а затем записывает имена файлов, которые содержат такие слова. Если к этим потокам применить циклическую стратегию планирования с единственным процессором, то поток 1 использовал бы свой квант времени для поиска файлов и вставки их путей в контейнер. Поток 2 использовал бы свой квант времени для выделения имен файлов и поиска заданных ключевых слов. В идеальном мире потоки 1 и 2 должны выполняться попеременно. Но в действительности все может быть иначе. Например, поток 2 может выполниться до потока 1, когда в контейнере еще нет ни одного файла, или поток 1 может так долго искать файл, что до истечения кванта времени не успеет записать его путь в контейнер. Такая ситуация требует синхронизации, краткое рассмотрение которой приводится ниже в этой главе и в главе 5. Стратегия планирования FIFO позволяет каждому потоку выполняться до завершения. Если рассмотреть тот же пример с использованием FIFO-стратегии, то поток 1 будет иметь достаточно времени, чтобы отыскать все нужные файлы и вставить их пути в контейнер. Поток 2 затем выделит имена файлов и выполнит поиск заданных ключевых слов. В идеальном мире завершение выполнения потока 2 будет означать завершение программы в целом. Но в реальном мире поток 2 может быть назначен процессору до потока 1, когда контейнер еще не будет содержать файлов для поиска в них ключевых слов. После «холостого» выполнения потока 2 процессору будет назначен поток 1, который может успешно отыскать нужные файлы и поместить в контейнер их пути. Однако поиск ключевых слов выполнять уже будет некому. Поэтому программа в целом потерпит фиаско. При использовании FIFO-стратегии не предусматривается перемешивания задач. Поток, назначенный процессору, занимает его До полного выполнения своей задачи. Такую стратегию планирования можно использовать для приложений, в которых потоки необходимо выполнить как можно скорее.

°Д Другими» стратегиями планирования подразумеваются уже рассмотренные, но с небольшими вариациями. Например, FIFO-стратегия может быть изменена таким

разом, чтобы позволить разблокировать потоки, выбранные случайно.

Изменение приоритета потоков

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