- 31 мая 2002 г.
Реализация "невесомых нитей" с помощью генераторов Python
Данная статья является концептуальным продолжением опубликованного в 14-ом
номере Журнала материала "Генераторы и простые итераторы". Дэвид Мертц на этот
раз рассказывает о том, как можно реализовать микронити в языке Python.
Мощь микронитей
В одной из предыдущих статей Дэвид показал, как можно моделировать полнофункциональные сопрограммы с помощью генераторов и простого планировщика. Этот планировщик можно непосредственно расширить, чтобы поддержать исключительно нересурсоемкую многонитевую обработку многочисленных процессов. Во многом подобно микронитям Stackless Python, "невесомые нити" псевдо-сопрограмм почти не требуют переключения контекста и накладных расходов по памяти по сравнению не только с нитями ядра (OS threads), но и пользовательского пространства (userland threads). В этой статье Дэвид представляет невесомые нити как элегантное решение проблем, естественное разрешение которых требует большого числа взаимодействующих процессов.
Область микронитей - по крайней мере, в Python - это экзотическое усовершенствование, приберегаемое для Stackless Python. Тема Stackless, как и те изменения, которые недавно были в него внесены, вероятно, заслуживают отдельной статьи. Однако, если коротко, то продолжения (continuation) в "новым Stackless", очевидно, исчезнут, в то время как микронити остаются смыслом существование этого проекта. Все это достаточно сложно...
Все же, давайте вернемся немного назад. Что есть микронить? В основном, микронить - это процесс, который может выполняться с минимальными требованиями к внутренним ресурсам - и выполняется он в пределах одного экземпляра интерпретатора Python (в общем пространстве памяти и т.п.). С помощью микронитей возможно выполнять десятки тысяч параллельных процессов на довольно скромной современной машине, а также переключаться между контекстами сотни тысяч раз в секунду. Обращения к fork() или стандартные системные вызовы управления нитями и близко к этому не подходят! Даже нити, входящие в так называемые библиотеки "облегченной" многонитевой обработки (lightweight threading libraries), на порядки величины "тяжелее", чем представленные здесь.
Семантика невесомых нитей, которые я рассматриваю в это статье, немного отличается от семантики нитей ядра. Если на то пошло, они несколько отличны и от тех, что предоставляет Stackless. Во многих отношениях невесомые нити значительно проще, чем большинство прочих вариантов; снимается множество проблем, таких как семафоры (semaphore), блокировки (locking) и тому подобное. Цена этой простоты - то, что я представляю "совместную многонитевость" (cooperative multithreading); добавление вытеснения (preemption) в пределах оболочки стандартного Python вряд ли реализуемо (по крайней мере, с Python 2.2, который не является Stackless - неизвестно, что может принести __future__).
Невесомые нити в известном смысле напоминают совместную многозадачность (cooperative multitasking) более ранних версий Windows и MacOS (но в пределах одного приложения). Однако, с другой стороны, невесомые нити - просто еще один способ выразить поток управления в программе; все, что делают невесомые нити, могло бы быть выполнено, по меньшей мере в принципе, с помощью технологии "действительно большого блока if/elif" (последней надежды любителя решений "в лоб").
Вспоминая сопрограммы
В статье "Итераторы и простые генераторы" был представлен механизм моделирования сопрограмм с помощью генераторов. По своей сути этот механизм удивительно прост. Набор объектов генератора обертывается в функцию scheduler(), которая управляет передачей управления в соответствующую ветвь. Они не являются настоящими сопрограммами в том смысле, что могут передавать управление только в и из функции scheduler(). Но для практических целей вы можете реализовать то же самое с помощью очень маленького количества дополнительного кода. Вот как мог бы выглядеть scheduler():
Листинг 1. scheduler() для моделируемых сопрограмм
def scheduler(gendct, start):
global cargo
coroutine = start
while 1:
(coroutine, cargo) = gendct[coroutine].next()
Касаясь этой обертки, стоит отметить, что каждый генератор/сопрограмма возвращает кортеж, который содержит назначение своей намеченной ветви. В сущности, генератор/сопрограмма выходит с адресатом GOTO. Для удобства я также позволил генераторам выдавать стандартный контейнер cargo как способ формализации данных, который пересылается между сопрограммами - но вы могли бы также просто использовать согласованные глобальные переменные или функции установки/получения значений (callback setter/getter functions) для передачи данных. Реймонд Хеттинджер (Raymond Hettinger) написал "Предложение по улучшению Python" (Python Enhancement Proposal (PEP)), которое нацелено на улучшение инкапсуляции переданных данных; возможно, это войдет в будущий Python.
Новые планировщики
Для невесомых нитей требования слегка отличаются от предъявляемых к сопрограммам. Но мы все равно можем использовать функцию scheduler() в ее основе. Разница заключается в том, что планировщик сам должен выбирать цели ветвления, а не получать их из генератора/сопрограмм. Давайте взглянем на полную тестовую программу и пример:
Листинг 2. Пример скрипта microthreads.py
from __future__ import generators
import sys, time
threads = []
TOTALSWITCHES = 10**6
NUMTHREADS = 10**5
def null_factory():
def empty():
while 1: yield None
return empty()
def quitter():
for n in xrange(TOTALSWITCHES/NUMTHREADS):
yield None
def scheduler():
global threads
try:
while 1:
for thread in threads: thread.next()
except StopIteration:
pass
if __name__ == "__main__":
for i in range(NUMTHREADS):
threads.append(null_factory())
threads.append(quitter())
starttime = time.clock()
scheduler()
print "TOTAL TIME: ", time.clock()-starttime
print "TOTAL SWITCHES:", TOTALSWITCHES
print "TOTAL THREADS: ", NUMTHREADS
Это едва ли не простейший планировщик невесомых нитей, который можно найти. Каждая нить вводится в установленном порядке, и каждая имеет одинаковый приоритет. Далее, мы рассмотрим, как усложнить эти детали. Так же, как и сопрограммы в предыдущей статье, невесомые нити должны быть написаны так, чтобы удовлетворять нескольким соглашениям.
Усложняя детали
По большей части генератор невесомой нити должен быть заключен в цикл while 1:. То, как здесь сформулирован генератор невесомой нити, заставляет останавливаться весь планировщик, когда останавливается одна нить. Это в некоторой степени менее устойчиво по сравнению с нитями ядра, зато не требует сложных дополнительных механизмов для перехвата исключений внутри цикла scheduler(), а не вне него. Более того, нить может быть удалена из списка, не завершившись (либо самой этой нитью, либо какой-либо другой нитью). Мы не предоставили механизм регистрации, чтобы упростить удаление; но естественным расширением было бы хранить нити вместо списка в словаре или какой-либо другой структуре.
Этот пример иллюстрирует разумную технологию для окончательного завершения цикла планировщика. Специальный генератор/нить, quitter(), отслеживает некое условие (в этом случае, просто подсчет переключений контекста) и бросает StopIteration, когда оно выполнено. Заметьте, что после завершения все другие генераторы еще не завершены и, при желании, позже могут быть возобновлены (либо в планировщике микронити, либо каким-либо иным способом). Очевидно, что при необходимости вы можете удалить (delete) эти генераторы/нити.
В обсуждаемом примере используются исключительно бесполезные нити. Они ничего не делают, и делают это минимально возможной форме. Пример сформулирован так, чтобы проиллюстрировать одну мысль - накладные расходы, присущие невесомым нитям, очень невелики. Создание 100.000 невесомых нитей для лэптопа Pentium II со стареньким Windows 98 и 64 МБ оперативной памяти не является проблемой (в случае одного миллиона нитей компьютер долго шуршит диском). Попробуйте это сделать с нитями ядра! Более того, на этом достаточно медленном 366 МГц процессоре один миллион переключений контекста может быть выполнен приблизительно за 10 секунд (число вовлеченных нитей не столь существенно для временных соотношений). Очевидно, что реальные невесомые нити должны кое-что делать, и для этого потребуется больше ресурсов пропорционально решаемой задаче. Но сама многонитевая обработка заслуживает звания "невесомой".
Накладные расходы на переключение
Переключение между невесомыми нитями - недорого, но небесплатно. Чтобы проверить это обстоятельство, я построил пример, который выполняет некоторую работу, но не больше того разумного минимума, который можно выполнить в нити. Поскольку планировщик нити на самом деле сводится к инструкциям "сделай А, затем сделай В, затем сделай С и т. д.", создание полностью параллельного блока в главной функции не было сложным:
Листинг 3. Пример скрипта overhead.py
from __future__ import generators
import time
TIMES = 100000
def stringops():
for n in xrange(TIMES):
s = "Mary had a little lamb"
s = s.upper()
s = "Mary had a little lamb"
s = s.lower()
s = "Mary had a little lamb"
s = s.replace('a','A')
def scheduler():
for n in xrange(TIMES):
for thread in threads: thread.next()
def upper():
while1:
s = "Mary had a little lamb"
s = s.upper()
yield None
def lower():
while1:
s = "Mary had a little lamb"
s = s.lower()
yield None
def replace():
while1:
s = "Mary had a little lamb"
s = s.replace('a','A')
yield None
if __name__=='__main__':
start = time.clock()
stringops()
looptime = time.clock()-start
print"LOOP TIME:", looptime
global threads
threads.append(upper())
threads.append(lower())
threads.append(replace())
start = time.clock()
scheduler()
threadtime = time.clock()-start
print"THREAD TIME:", threadtime
Оказалось, что версия с невесомой нитью выполняется чуть более чем в два раза дольше, чем версия с простым циклом - немногим меньше 3 секунд против чуть более 6 секунд на указанной выше машине. Очевидно, что, если каждая единица работы была бы вдвое, в десять или в сто раз больше одного вызова строчного метода, то время, затраченное на накладные ресурсы на нить, соответственно уменьшилось бы.
Разрабатывая нити
Невесомые нити могут, и обычно должны, быть большего масштаба по сравнению с одной концептуальной операцией. Нить какого бы то ни было вида используется, чтобы представить контекст потока управления, необходимого для описания отдельной задачи (task) или активности (activity). Но задача может быть больше, чем время/размер, которое хотелось бы проводить внутри контекста одной нити. Вытеснение (preemption) автоматически управляется с этой проблемой, безо всякого специального вмешательства разработчика приложения. К сожалению, пользователи невесомых нитей должны обращать внимание на то, что необходимо "хорошо себя вести" с другими нитями.
По крайней мере, невесомая нить должна быть достаточно продумана, чтобы возвращать управление (yield) всякий раз, когда она завершает концептуальную операцию. Планировщик будет возвращаться к ней обратно для следующего шага. Например:
Листинг 4. Псевдокод "дружественной" невесомой нити
def nicethread():
while 1:
...operation A...
yield None
...operation B...
yield None
...operation C...
yield None
По большей части, в хорошем проекте управление будет возвращаться (yield) чаще, чем на границах между базовыми операциями. Часто что-нибудь концептуально "базовое" тем не менее включает цикл над большим набором данных. Когда это так (в зависимости от того, насколько затратно по времени тело цикла), вероятно, имеет смысл поместить один или два yield в тело цикла (возможно, повторяя после определенного числа итераций цикла). В отличие от нитей с вытеснением, невесомая нить "с плохим поведением" может безраздельно захватить процессор на произвольное время.
Еще о планировщиках
В указанных выше примерах приведены только самые основные типы планировщиков нитей. Потенциально, вы можете создать гораздо больше (этот вопрос в известной степени не зависит от разработки хорошего генератора/нити). Позвольте мне бегло рассказать о нескольких расширениях.
Лучшее управление нитью
Простой список облегчает добавление генератора/нити для планировщика для обработки. Но эта структура данных нисколько не упрощает удаление или приостановку нитей, которые больше не нужны. Вероятно, словарь или класс будет лучшей структурой данных для управления нитью. В качестве быстрой иллюстрации ниже приведен класс, который (почти) может сойти за список threads в указанных примерах:
class ThreadPool:
"""Enhanced threads list as class
threads = ThreadPool()
threads.append(threadfunc) # not generator object
if threads.query(num) <>:
threads.remove(num)
"""
def __init__(self):
self.threadlist = []
self.threaddict = {}
self.avail = 1
def __getitem__(self, n):
return self.threadlist[n]
def append(self, threadfunc, docstring=None):
# Argument is the generator func, not the gen object
# Every threadfunc should contain a docstring
docstring = docstring or threadfunc.__doc__
self.threaddict[self.avail] = (docstring, threadfunc())
self.avail += 1
self.threadlist = [p[1] for p in self.threaddict.values()]
return self.avail-1 # return the threadID
def remove(self, threadID):
self.threadlist = [p[1] for p in self.threaddict.values()]
def query(self, threadID):
"Information on thread, if it exists (otherwise None)
return self.threaddict.get(threadID,[None])[0]
Можно сделать больше, но и это хорошее начало.
Приоритеты нитей
В этих простых примерах планировщик уделяет одинаковое внимание всем нитям. Имеется, по крайней мере, два общих подхода в отношении более тонко настроенной системы приоритетов нитей. Одна система приоритетов могла бы просто уделять больше внимания высокоприоритетным нитям по сравнению с низкоприоритетными. Непосредственная реализация этого подхода заключалась бы в создании нового класса PriorityThreadPool(ThreadPool), который в течение итерации нити чаще возвращал бы более важные нити. Такой простейший подход мог бы многократно возвращать некоторые нити последовательно в свой метод .__getitem__(). Тогда высокоприоритетная нить могла бы получать не один, а два, десять или сотню последовательных квантов времени ("time-slice"). Oчень слабый вариант планировщика для системы "реального времени" мог бы возвращать вернуть множественные копии важных нитей, разбросанные по списку. Это не только увеличило бы общее внимание, которые получают высокоприоритетные нити, но и фактическую частоту их обслуживания.
Вероятно, более сложный подход к приоритетам нити не так легко доступен на чистом Python (но он поддерживается некоторыми библиотеками, специфичными для ОС/процессора). Вместо того, чтобы просто давать высокоприоритетным нитям целое число временных интервалов, планировщик мог бы измерить время, в действительности проведенное в каждой невесомой нити, и динамически настраивать планирование нити так, чтобы оно было более "справедливым" в отношении нитей, недополучающих обслуживание (справедливость, возможно, соотносится с приоритетом нити). К сожалению, питоновская функция time.clock() - таймеры недостаточно высокого разрешения, чтобы сделать этот подход эффективным. С другой стороны, при подходе "множественные временные интервалы" ничто не мешает "недокормленной" нити динамически повысить свой собственный приоритет.
Комбинируя микронити с сопрограммами
Чтобы создать планировщик для невесомых нитей (микронитей), я удалил логику сопрограммы, реализующую "пожалуйста, передайте управление сюда". В действительности, делать это было необязательно. Невесомые нити в примерах всегда выдавали None, а не адресат перехода. Однако, нет причины, по которой эти две концепции нельзя было бы объединить: если сопрограмма/нить возвращает адресат перехода, планировщик может перейти, куда просят (если только, возможно, это не отменили приоритеты нити). Тем не менее, если сопрограмма/нить просто возвращает None, планировщик мог бы сам принять решение касательно подходящей нити для следующей активации. Требуется не так много работы для того, чтобы решить и запрограммировать, как именно произвольный переход стал бы взаимодействовать с линейной очередью нитей, и эта задача вовсе не является непостижимой.
Быстро и дешево - чего же еще?
Модель микронитей (или "невесомых нитей"), в сущности, сводится к еще одному экзотическому стилю управляющих структур в Python. Предыдущие статьи уже касались некоторых из них. Прелесть наличия разнообразных механизмов управления заключается в том, что они позволяют разработчику заключить функциональность кода в ее логические компоненты и максимизировать контекстуальную релевантность кода.
На самом деле, требуется немного для того, чтобы возможность делать все стала возможной ("loop" и "if"). Для класса проблем, которые легко разбиваются на множество маленьких "агентов" ("agents"), "серверов" ("servers") или "процессов" ("processes"), невесомые нити могут быть самой четкой моделью выражения базовой "бизнес-логики" приложения. Разумеется, это не противоречит тому, что невесомые нити обладают потенциалом, позволяющим им быть исключительно быстрыми по сравнению с более известными механизмами управления.
Ресурсы
- Ранее в этом цикле статей Дэвид представил абстрактную модель для широкого класса конечных автоматов (state machine). Статья, "Использование конечных автоматов" (developerWorks, Август 2000), является отправной точкой, на которую он опирается в данной статье.
- В "Интервью с создателем Stackless Python, Кристианом Тисмером" (developerWorks, Октябрь 2000) Дэвид кратко коснулся темы микронитей и других экзотических управляющих структур, как продолжения, сопрограммы и генераторы. В статье освещены некоторые из них - еще до того, как в Python 2.2 были введены генераторы.
- Совсем недавно, в период альфа-версии Python 2.2, Дэвид представил "Итераторы и простые генераторы" (developerWorks, Сентябрь 2001).
- Всем, кто интересуется микронитями - или сложной историей Stackless Python - полезно ознакомиться с Web-сайтом Stackless Python. Хотя Дэвид в своих предложениях, возможно, и вторгается в концептуальную область Stackless Python, он считает, что Stackless продолжает делать много того, что его оболочка не делает (ценою заплатанной fork стандартного Python).
- Ряд статей о Linux в зоне Linux developerWorks.
Об авторе
Подобно Ницше, Дэвид хотел бы написать, что это - размышления старого филолога, но это была бы явная ложь. Однако, возможно, его (безвозмездно продвигаемая прямо здесь) ожидаемая книга "Текстовая обработка в Python" (Text Processing in Python) будет когда-нибудь ошибочно принята за кибернетический вариант филологии. Дэйвид доступен по адресу: mertz@gnosis.cx, а жизнь его описана на http://gnosis.cx/publish/. Присылайте свои замечания и предложения касательно этой, прошлых или будущих статей.
Автор: Дэвид Мертц(David Mertz), Ph.D., Producer, Gnosis Software, Inc