4. Времена упадка. Треды

Окончание. Начало в NN 21, 23.

4.1. Ситуация.

В первых статьях этого цикла "тяжелая" и "легкая" многозадачности были противопоставлены Интересно, что эта дилемма видна не со всех точек зрения – для некоторых ее словно не существует. Так, сторонники Novell NetWare всегда подчеркивали преимущества принятой в ней "легкой" схемы как более эффективной по сравнению с UNIX Но не припомню, чтобы юниксисты отвечали на хулу или хотя бы ее замечали.

Беда в том, что неожиданно отросший у компьютерного бизнеса громадный поп-культурный сектор начал действовать как калейдоскоп, размножающий структуру профессиональных понятий в кривых и облезлых зеркалах. И чего только люди не доказывают, прыгая с ветки на ветку древа познания Например, юниксисты внедряют "легкую" многозадачность (треды), чтобы использовать многопроцессорные платформы, в особенности SMP. Ноувелисты, напротив, радостно объявляют, что в NetWare треды были всегда Никто же не будет ходить за каждым, кому повесили лапшу на уши, и объяснять, что NetWare не только не поддерживает SMP, но как бы даже и не собилась этого делать до недавнего времени.

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

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

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

Явной уступкой новым потребностям был пакет межпроцессной связи IPC, появившийся, если не ошибаюсь, в AT&T System V.3. Показательно, что приверженцы классического UNIX'a не приняли его Они создали менее эффективные, но идейно близкие UNIX-аналоги – например, файлы в памяти вместо разделяемой памяти Если же кому-то позарез требуется "легкая" многозадачность – в чем дело? Пожалуйста, заводите внутри процесса что угодно.

Вот так выглядела итоговая диспозиция. Во второй половине 80-х годов распространились PC и были созданы операционные системы с "легкой" многозадачностью (те же Windows и NetWare), которые благодаря умелой продаже завоевали массовый рынок, хотя уж точно не могли служить инженерным образцом для подражания. Со своей стороны, приверженцы UNIX обзавелись кое-какими компромиссными механизмами для специальных нужд, но "легкая" многозадачность едва рассматривалась ими даже как вспомогательное средство (о переделке UNIX на манер NetWare говорить не приходится даже гипотетически).

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

4.2. Механизмы "легкой" многозадачности

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

Расплата за это – повышенная трудоемкость разработки и риск, риск, риск То, что тред может "забыть" проверить семафор – это семечки. Теория и практика предупреждают о куда более трудных ситуациях. Такие термины, как "тупик" и "смертельные объятия", говорят сами за себя.

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

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

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

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

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

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

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

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

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

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

4.3. Треды и параллельные архитектуры

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

Нынешний этап – исчерпание возможностей как технологий, так и архитектур. Обратите внимание на два обстоятельства. Первое – кризис в империи Cray. Дело не в том, кто и почему там обанкротился, а в переходе на параллельные решения. Нет идей, как делать единичный процессор более быстрым.

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

Как бы то ни было, программно-технический сектор неизбежность этого бедствия осознал давно и имел время на подготовку. Говорю о бедствии потому, что программы для параллельных систем во много раз труднее разрабатывать и отлаживать "в лоб". Идеально было бы переложить все на компиляторы, чтобы они сами решали, где, что, как и когда распараллеливать. Для некоторых задач, как раз для тех, для которых и покупали параллельные системы в период их застоя, это действительно удается, но не все же искать под фонарем.

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

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

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

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

Заметим, впрочем, что при фиксированном интервале таймера (допустим, те же 20 мс) относительная доля накладных расходов на обработку его прерываний понижается по мере увеличения производительности процессора, а доля полезной работы, соответственно, растет. Слабый процессор может тратить на планирование в среднем 2 мс, а мощный – 0 2, при той же длительности цикла. А в случае распараллеливания обе части (полезная работа и затраты на перепланирование) изменяются пропорционально.

Еще один аспект – масштабируемость. От настольного SMP-компьютера нередко хотят, чтобы он выполнял одну программу быстрее других, хотя в системе коллективного пользования таких программ может быть тысячи. Наоборот, одна и та же программа, например, сервер СУБД, может распыляться на тысячи тредов, выполняющих одно и то же элементарное действие для разных запросов, по десятку тредов на запрос. Количество процессоров достигает 64 и более, причем надо, чтобы пользователи могли реально повысить нагрузочную способность сервера, просто прикупив еще несколько процессорных плат.

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

Короче, вот так и пришлось на двадцатом году существования UNIX опять.

Механизмы "легкой" многозадачности.

Главные из них – треды, семафоры и сообщения. Слово "тред" (thread) лучше переводить как "нитка", "прядь", "линия", "поток" Переводят еще как "шаг", но это не то, поскольку шаг короткий, конечный, а нить длинная, потенциально бесконечная.

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

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

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

.

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

Решив встать в очередь, тред вызывает соответствующую функцию, и семафор его усыпляет. Если же семафор оказался свободен, тред запирает его и спокойно занимается тем, чем он должен заниматься только в одиночку. Есть много разновидностей семафоров, в последнее время простейшие из них чаще всего называются "мьютексами" (mutex, от mutual exclusion, "взаимное исключение").

UNIX если уж и показывает свою многозадачную природу, старательно создает иллюзию параллельного выполнения процессов, даже если процессор всего один. В системе с "легкой" многозадачностью разработчик должен ясно понимать, что треды могут никогда не встречаться друг с другом. Естественный метод взаимодействия в таких случаях – почта. Один тред оставляет сообщение, которое другой, возможно, когда-нибудь подберет Это (рис. 7) может развиться в аналог хорошо налаженной современной почтовой службы с доставкой чего угодно, на дом или до востребования, и так далее перекраивать его, и опять он это выдержал!.

4.4. Реализация тредов в UNIX

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

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

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

При порождении процесса автоматически создается первый (и, возможно, последний) тред Складываясь со структурами данных процесса, его данные образуют жизнеспособную комбинацию, в которой начинает выполняться функция mam(). С тредом связаны и кое-какие дополнительные данные; главное из них – его личный идентификатор плюс что-то вроде обычного юниксовского "окружения" (environment), но в форме словаря, а не массива строк.

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

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

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

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

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

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

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

4.5. И что мы с этого имеем?.

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

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

Все это, конечно, стало возможным благодаря изменившейся структуре потребления. Десять лет назад просто не существовало продуктов с такой широкой базой применения и одновременно настолько важных для пользователей, как современные СУБД.

5. Новые времена. Микроядра

К описанной выше схеме многозадачности уже мало что можно прибавить Из нее можно только вычитать; таким путем вы получите и NetWare, и NT, и все остальное. Это преувеличение, конечно, но не такое уж далекое от истины Остается множество специализированных аспектов – таких, как обслуживание задач реального времени (то есть с очень жесткими требованиями по времени) или встраивание DOS Хотя со всем этим UNIX тоже справляется.

Тем не менее нашлись люди, которых классическая архитектура системы перестала удовлетворять. Их предвидение далеко опередило реальные потребности рынка, но удивительно точно попало в цель. Несколько исследовательских групп в разных странах много лет назад начали заниматься очень похожими вещами. При этом цели у них были совсем непохожие. Одни искали возможности скрестить UNIX и объектно-ориентированный подход, другие – сделать так, чтобы UNIX мог легко поддерживать иные файловые системы и даже эмулировать целые OS, третьи занимались новыми способами интеграции программ в сетях. Удивительно, но эти поиски с разных сторон вели к "наименьшему общему кратному", сильно смахивающему на виртуальную машину настоящего объектно-ориентированного языка, такого, как Smalltalk. Эта программа, берущая на себя минимум задач (как можно меньше функций, главным образом нижний уровень взаимодействия с физической периферией, управления памятью и передачи сообщений), была названа микроядром.

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

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

Это свойство, называемое энкапсуляцией, позволяет реализовать многозадачность со всей возможной гибкостью, но так же надежно, будто все происходит в закрытом для доступа ядре В C++ энкапсуляция – вопрос добровольной дисциплины программирования, в Smalltalk она поддерживается системой, но не вынуждается (есть защита от дурака, но не от злодея), а при работе через микроядро энкапсуляция становится действительно непробиваемой.

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

Вот теперь окончательно конец. Обзор многозадачности в UNIX оказался очень длинным, зато всесторонним (хоть и поверхностным). Ничего не поделаешь, все стоящее внимания в компьютерном деле происходит в UNIX. He нами это заведено и, видно, не на нас кончится.