16+
ComputerPrice
НА ГЛАВНУЮ СТАТЬИ НОВОСТИ О НАС




Яндекс цитирования


Версия для печати

Модуль поиска не установлен.

Многозадачность - друг человека

21.04.2004

Алексей Смирнов, Иван Марциновский

Вставай! Иди! Гудок зовет,
и мы приходим на завод.
Народа - уйма целая,
тысяча двести.
Чего один не сделает -
сделаем вместе...
В. Маяковский

Введение

Вам никогда не приходил в голову вопрос: как ваш компьютер успевает проигрывать музыку в Winamp'е, выкачивать из Интернета очередную заплатку для Windows, дефрагментировать жесткий диск, распечатывать реферат, а вы при этом еще успеваете играть в "Сапера"? Причем все это одновременно, и даже почти без тормозов, и даже если сердце вашего компьютера - всего-навсего один небольшой микропроцессор средней производительности? Если вспомнить, что центральный процессор может выполнять в каждый данный момент времени не больше одного потока команд (Pentium IV с технологией HyperThreading мы рассматривать не будем, поскольку при желании его можно представить как два независимых устройства), становится понятно, что ответ не так уж и очевиден.

И все же попытаемся дать его. Современные процессоры - это весьма быстродействующие устройства, способные выполнять миллионы и миллионы операций в секунду, и именно это их свойство сделало возможным появление широко сейчас распространенных многозадачных операционных систем - например, ОС Windows, Linux или QNX. Многозадачные ОС обеспечивают возможность запускать одновременно нескольких программ, которые, с точки зрения пользователя, будут выполняться параллельно. На самом же деле, строго параллельное выполнение программ - это, конечно же, лишь иллюзия. В случае работы ОС на компьютере с одним процессором речь может идти лишь о псевдопараллельном выполнении приложений, при котором в каждый конкретный момент времени выполняется лишь одна программа, однако, за весьма короткое время процессор успевает последовательно поработать со всеми программами "по чуть-чуть". При этом всю черновую работу, связанную с распараллеливанием выполнения приложений, берет на себя операционная система. В зависимости от объема и "интеллектуальности" этой работы, принято различать несколько видов многозадачности - кооперативную и вытесняющую. В кооперативной многозадачности приложение само определяет момент, когда следует отдать ресурсы центрального процессора ядру ОС, и делает это на "добровольных началах". Если же программа (а она вполне может быть зловредным вирусом) решит, что она должна монопольно владеть всеми вычислительными ресурсами вашего компьютера, и откажется отдать управление, то операционная система ничего не сможет ей противопоставить и просто-напросто зависнет. При вытесняющей многозадачности приложение владеет всеми ресурсами центрального процессора только в течение, заранее определенного времени - кванта. По истечении кванта ОС обязательно переключит процессор на выполнение другой задачи.

Модель кооперативной многозадачности использовалась в очень древних версиях Windows - это уже полузабытые Windows 3.11 и ее предшественники. Во всех современных ОС используется вытесняющее планирование и его различные вариации, поэтому мы постараемся рассказать о тех механизмах, которые используют последние версии ОС Windows для реализации именно этого вида многозадачности. Рассматриваться будет только семейство NT (на основе New Technology), в которое входят наиболее любимые отечественными юзерами Windows 2000 и Windows XP.

Задания, процессы, потоки и волокна

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

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

Процесс - достаточно сложный объект, включающий в себя некоторое количество более простых объектов, в том числе - потоков. Поток - это элементарная единица исполнения, которыми, собственно, и управляет Windows, реализуя многозадачность. У потока есть счетчик команд, регистры и стек, однако, в отличие от процессов, у них нет ни индивидуального адресного пространства, ни других принадлежащих им ресурсов. Например, в DOS каждая программа, по сути, была одним процессом, внутри которого имелся один, и только один поток. В Windows это ограничение снято, в каждом процессе может быть много потоков, они представляют собой своеобразные "программы в программе". Процесс сам по себе выполняться не может - он только предоставляет потокам переменные окружения, контекст и адресное пространство. У всех потоков одного процесса единое адресное пространство - 4 Гб, и они могут равноправно его использовать (вернее, если в системе "настройки по умолчанию", они могут использовать только нижние 2 Гб, верхние 2 Гб зарезервированы для использования операционной системой). Обратите внимание, что ни один поток не может быть запущен вне процесса, а при создании нового процесса внутри него обязательно создается хотя бы один поток.

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

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

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

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

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

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

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

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

Оказывается, Windows мало чем отличается от институтской библиотеки, она также делит потоки на более важные и менее важные. Вполне логично, что в первую очередь выполняются самые важные потоки, затем - чуть менее значимые и т. д., в последнюю же очередь (если до них вообще дойдет дело) - самые "ненужные". Низший приоритет имеет поток, заполняющий освобожденную процессами память нулями (да-да, ваша операционка делает и такие вещи!). Приоритет потока может иметь значение в диапазоне от 0 до 31, причем в процессе работы он может изменяться. Текущий уровень приоритета определяется довольно сложным образом. Изначально он устанавливается на основе величины базового приоритета родительского процесса, который присваивается ему при запуске. Базовый приоритет процесса может иметь всего 6 значений: низкий - 4, ниже среднего - 6, средний - 8, выше среднего - 10, высокий - 13, реального времени - 24. Его можно изменить с помощью панели диспетчера задач.

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

Как это работает

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

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

- какая часть ОС (и как) будет управлять распределением процессорного времени между различными потоками, выполняющимися в данный момент;

- каков размер того минимального кванта времени, который выделяется для работы каждого выполняющегося потока;

- как синхронизовать выполняющиеся параллельно потоки и процессы;

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

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

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

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

Как уже говорилось, при использовании вытесняющей многозадачности приложение само явным образом не возвращает управление центральным процессором операционной системе. Любой программист может подтвердить наши слова: никто не пишет в прикладных программах код, вызывающий API-функции планировщика по истечении отведенного потоку кванта времени. Тогда кто же заставляет процессор выполнить переключение на другую задачу? Ответ прост. Весь фокус состоит в том, что в любом компьютере имеется таймер, достаточно часто посылающий аппаратные прерывания центральному процессору. Процессоры Intel устроены так, что, получив аппаратное прерывание, они тут же прерывают свою работу и начинают выполнять код, расположенный по определенному адресу в оперативной памяти. При этом каждому типу аппаратного прерывания сопоставлен свой определенный адрес памяти, а говоря точнее - указатель на начало блока памяти. Таблица соответствия номера прерывания с адресом блока, содержащим код для его обработки, называется таблицей диспетчеризации прерываний (interrupt dispatch table, IDT). Эта схема работы прерываний может быть немного разной в зависимости от того, о каком конкретном компьютере идет речь, поскольку сильно зависит от аппаратной реализации, но общая идея именно такая, как мы описали. При загрузке компьютера Windows заносит в IDT указатели на процедуры, обрабатывающие каждое прерывание, после чего защищает занятую память от модификации (устанавливая атрибут Read Only). Приоритет прерывания таймера - один из самых высоких (его уровень равен 28, максимальный приоритет в Windows равен 31), поэтому, что бы ни случилось, примерно каждые 10 мс приходит прерывание от таймера, в этот момент выполняющийся поток аппаратно приостанавливается, и начинает выполняться специальным образом зарегистрированная в IDT процедура обслуживания прерывания - ISR (interrupt service routine). Сама она не выполняет диспетчеризацию, однако может по завершении передать управление потоку с наивысшем приоритетом, ждущему в очереди потоков, готовых к выполнению, а это и есть планировщик. Передача управления происходит путем генерирования прерывания, на этот раз уже программного. Все эти тихие игры с аппаратными и программными прерываниями используются в Windows по одной весьма простой причине: системе вредно находиться в состоянии обработки прерывания с высоким приоритетом, поскольку в это время все прерывания с более низким приоритетом запрещены. Это значит, что если бы, например, планировщик работал при уровне 28 одну секунду, все это время прерывания, связанные с движением мышки, процессору не поступали бы. Отложенную планировку как раз и удобно организовать с помощью генерирования программного прерывания с невысоким приоритетом. Тогда процессор очень быстро обработает ISR аппаратного прерывания таймера с уровнем 28, сгенерирует прерывание DPC/dispatch с уровнем 2 и тут же понизит уровень запрещенных прерываний, так что все они в диапазоне от 3 до 28 "освободятся".

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

- при изменении приоритета одного из потоков;

- при появлении нового потока, готового к выполнению;

- по истечении кванта времени, выделенного выполняющемуся потоку;

- в результате остановки потока (например, он ожидает на каком-нибудь объекте);

- при изменении предпочтительного процессора для текущего потока (только в многопроцессорных системах).

Квант времени, выделяемый потоку в Windows, не равен интервалу между двумя срабатываниями системного таймера, и, что может показаться неестественным, может даже принимать не кратные ему значения. Он измеряется в весьма своеобразных единицах, называемых в Microsoft "квантовыми единицами времени". Период между двумя прерываниями от таймера соответствует 3 квантовым единицам времени. Если вспомнить, что период срабатывания таймера может тоже быть разным в разных системах (это зависит, в первую очередь, от аппаратной конфигурации), все становится еще более запутанным. Тем не менее, важно запомнить: между двумя срабатываниями таймера укладывается 3 квантовых единицы, каждый раз, когда приходит прерывание от таймера, из счетчика времени выполняющегося в данный момент потока вычитаются как раз эти 3 единицы. В ОС на основе NT один квант, выделяемый потоку, равен 6 квантовым единицам (то есть 2 "тикам" таймера) в случае настольных систем или 36 единицам (то есть 12 "тикам" таймера) в том случае, если машина играет роль сервера. При желании, вы можете изменить эти значения: на вкладке "Дополнительно" свойств "Моего компьютера" имеется малоприметная кнопочка "Параметры быстродействия..." (почему-то с тремя точками на конце), нажав на которую, вы можете поменять значение кванта по умолчанию: переключатель в положении "оптимизировать быстродействие для приложений" сделает кванты короткими (равными 6 квантовым единицам), "для служб, работающих в фоновом режиме" - длинными (равными 36 квантовым единицам).

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

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

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

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

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



статьи
статьи
 / 
новости
новости
 / 
контакты
контакты