Камерон Хьюз - Параллельное и распределенное программирование на С++

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

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

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