Паралелна обрада¶
Од 1970-их до средине 2000-их, брзина појединачних процесорских језгара расла је експоненцијалном брзином. Велики део овог повећања брзине постигнут је повећањем учестаности сигнала такта, односно брзине којом процесор обавља основне операције. Средином 2000-их година, међутим, овај експоненцијални пораст нагло се зауставио, услед топлотних ограничења до којих је довела дисипација снаге, а брзина појединачних језгара процесора се од тада повећавала далеко спорије. Уместо тога, произвођачи процесора почели су да стављају више језгара у један процесор, омогућавајући истовремено обављање више операција.
Паралелизација није нови концепт. Паралелне машине великих размера користе се већ деценијама, пре свега за научна израчунавања и анализу података. Чак и у персоналним рачунарима са једним процесорским језгром, оперативни системи и интерпретатори пружају апстракцију конкурентности и паралелизма. То се постиже пребацивањем контекста или брзим пребацивањем између различитих задатака без чекања да се они доврше. Дакле, више програма може истовремено да се извршава на истом рачунару, чак и ако има само једно процесорско језгро.
С обзиром на тренутни тренд повећања броја процесорских језгара, појединачни програми сада морају да искористе предност паралелизма како би радили брже. У оквиру једног програма, израчунавање мора бити организовано на такав начин да се што више посла може обавити паралелно. Међутим, паралелизам уводи нове изазове у писање исправног изворног кода, посебно у присуству заједничког, променљивог стања.
За проблеме који се могу ефикасно решити у функционалном моделу, без заједничког променљивог стања, паралелизам не представља проблем. Чисте функције пружају референцијалну прозрачност, што значи да изрази могу бити замењени њиховим вредностима, и обратно, без утицаја на понашање програма. Ово омогућава паралелно вредновање међусобно независних израза. Као што је разматрано у претходном одељку, MapReduce оквир омогућава писање и паралелно извршавање функционалних програма уз минималан напор од стране програмера.
Нажалост, не могу се сви проблеми ефикасно решити помоћу функционалног програмирања. У оквиру различитих пројеката је идентификовано тринаест уобичајених рачунских образаца у науци и инжењерству, од којих је само један MapReduce сводљив. Преостали обрасци захтевају заједничка стања.
У остатку овог одељка биће приказано како променљиво дељено стање може увести багове и довести до грешака у паралелне програме, као и неколико приступа за спречавање таквих грешака. Ове технике ће бити испитане у контексту две апликације, веб паука и симулатора честица.
Паралелизам у Пајтону¶
Пре дубљег зарона у појединости паралелизма, најпре ће бити истражена Пајтонова подршка за паралелно израчунавање. Пајтон пружа два начина паралелног извршавања: нити и вишепроцесорска обрада.
Нити¶
У нитима, постоји више „нити” извршења унутар једног интерпретатора. Свака нит извршава код независно од осталих, иако деле исте податке. Међутим, CPython интерпретатор, главна и референтна Пајтон имплементација, интерпретира код само у једној нити у једном временском тренутку, пребацујући се између њих како би пружио илузију паралелизма. С друге стране, операције које су ван самог интерпретатора, попут уписа у датотеку или приступа мрежи, могу се извршавати паралелно.
Модул threading садржи класе које омогућавају стварање и синхронизацију нити. Следи једноставан пример вишенитног програма:
>>> import threading
>>> def нитЗдраво():
... други = threading.Thread(target=нитРециЗдраво, args=())
... други.start()
... нитРециЗдраво()
>>> def нитРециЗдраво():
... print('Здраво од', threading.current_thread().name)
>>> нитЗдраво()
Здраво од Thread-1 (нитРециЗдраво)
Здраво од MainThread
Конструктор Thread ствара нову нит. Потребна је циљана функција коју треба да покрене и изврши нова нит, као и аргументи те функције. Позивање start на Thread објекту означава га као спремног за покретање и извршавање. Функција current_thread враћа Thread објекат повезан са тренутном нити извршења.
У овом примеру, исписи се могу десити било којим редоследом, јер нису синхронизовани ни на који начин.
Вишепроцесорска обрада¶
Пајтон такође подржава вишепроцесорску обраду, што омогућава програму да произведе више интерпретатора или процеса, од којих сваки може самостално да покреће код. Ови процеси углавном не деле и не размењују податке, па се свако дељено стање и размена података мора искомуницирати између процеса. С друге стране, процеси се извршавају паралелно у складу са нивоом паралелизма који пружа основни оперативни систем и хардвер. Дакле, ако централна процесорска јединица има више процесорских језгара, Пајтон процеси могу се заиста извршавати конкурентно, односно истовремено.
Модул multiprocessing садржи класе за стварање и синхронизацију процеса. Следи пример примене процеса налик претходном када су у питању биле нити:
>>> import multiprocessing
>>> def процесЗдраво():
... други = multiprocessing.Process(target=процесРециЗдраво, args=())
... други.start()
... процесРециЗдраво()
>>> def процесРециЗдраво():
... print('Здраво од', multiprocessing.current_process().name)
>>> процесЗдраво()
Здраво од MainProcess
>>> Здраво од Process-1
Као што овај пример показује, многе класе и функције у вишепроцесорској обради аналогне су онима у нитима. Овај пример такође показује како недостатак синхронизације утиче на дељено стање, јер се екран може сматрати дељеним стањем. Овде се упит интерпретатора >>> из интерактивног процеса појављује пре исписа из другог процеса.
Када није потребна синхронизација¶
У неким случајевима приступ дељеним подацима не мора бити синхронизован ако истовремени приступ не може резултовати неисправним понашањем и нетачним резултатом. Најједноставнији пример су подаци који се само очитавају. Будући да такви подаци никада нису промењени, то јест мутирани, све нити ће увек читати исте вредности без обзира када приступају подацима.
У ретким случајевима дељени подаци који су мутирани можда неће захтевати синхронизацију. Међутим, разумевање када је то случај захтева дубоко знање о томе како интерпретатор и основни софтвер и хардвер раде. Размотрити следећи пример:
ставке = []
заставица = []
def потроши():
while not заставица:
pass
print('Ставке су', ставке)
def произведи():
потрошач = threading.Thread(target=потроши, args=())
потрошач.start()
for i in range(10):
ставке.append(i)
заставица.append('идемо')
произведи()
Овде нит произвођача додаје ставке у ставке, док потрошач чека док заставица није празна. Када произвођач заврши са додавањем ставки, додаје члан у заставица, омогућавајући потрошачу да настави.
У већини Пајтон имплементација, овај пример ће радити исправно. Међутим, уобичајена оптимизација код осталих преводилаца и интерпретатора, па чак и самог хардвера, јесте преуређивање операција унутар једне нити које не зависе једна од друге за податке. У таквом систему, наредба заставица.append('идемо') може се преместити и пре петље, јер ниједна не зависи од друге за податке. Уопштено гледано, овакав код требало би избегавати, осим ако програмер није у потпуности сигуран да основни оперативни систем или хардвер неће променити редослед релевантних операција.
Синхронизоване структуре података¶
Најједноставније средство синхронизације заједничких дељених података је коришћење структуре података која пружа синхронизоване операције. Модул queue садржи класу Queue која омогућава синхронизован „први улази, први излази” приступ подацима. Метода put додаје ставку у Queue, а метода get преузима ставку. Сама класа осигурава да се ове методе синхронизују, тако да се ставке не губе без обзира на то како су операције нити испреплетане. Ево примера произвођача/потрошача који користи Queue:
from queue import Queue
queue = Queue()
def синхронизованоПотроши():
while True:
print('Добио ставку:', queue.get())
queue.task_done()
def синхронизованоПроизведи():
потрошач = threading.Thread(target=синхронизованоПотроши, args=())
потрошач.daemon = True
потрошач.start()
for i in range(10):
queue.put(i)
queue.join()
синхронизованоПроизведи()
Постоји неколико промена у овом коду, поред Queue и get и put позива. Потрошачка нит је означена као daemon односно демон, што значи да програм неће чекати да се та нит заврши пре изласка. То омогућава да се користи бесконачна петљу у потрошачу. Међутим, мора се осигурати да главна нит изађе, али тек након што се све ставке из Queue потроше. Потрошач позива методу task_done да обавести Queue да је обрада ставке готова, а главна нит позива join методу, која чека док се све ставке не обраде, осигуравајући да програм изађе тек након што је то случај.
Сложенији пример који користи Queue је паралелни веб паук који претражује мртве везе на интернет страници. Овај паук прати све везе које хостује иста интернет страница, тако да мора да обрађује одређени број интернет адреса, непрекидно додајући нове у Queue и уклањајући интернет адресе за обраду. Коришћењем синхронизованог реда односно Queue, више нити може безбедно истовремено додавати и уклањати податке из ове структуре података.
Браве¶
Када синхронизована верзија одређене структуре података није доступна, мора се обезбедити сопствена синхронизација. Брава је основни механизам за то. Структуру података може узети највише једна нит, након чега ниједна друга нит је не може узети док је не ослободи нит која ју је претходно узела.
У Пајтону, модул threading садржи класу Lock која омогућава закључавање. Класа Lock има acquire и release методе за узимање и ослобађање браве, а класа гарантује да је у једном тренутку може узети само једна нит. Све остале нити које покушавају да узму браву док је она већ држана од стране друге нити присиљене су да сачекају док се не ослободи.
Да би брава заштитила одређени скуп података, све нити треба да буду програмиране тако да следе правило: ниједна нит неће приступити ниједном дељеном податку уколико није власник те одређене браве. У ствари, све нити морају да „умотају” своје манипулисање дељеним подацима у acquire и release позиве за ту браву.
У паралелном веб пауку, скуп се користи за праћење свих интернет адреса на које је наишла било која нит, како би се избегла обрада одређене интернет адресе више пута (и потенцијално заглављивање у кружној петљи или циклусу). Међутим, Пајтон не нуди готове синхронизоване скупове као структуру података, па се мора користити брава да би се заштитио приступ обичном скупу:
seen = set()
seen_lock = threading.Lock()
def already_seen(item):
seen_lock.acquire()
result = True
if item not in seen:
seen.add(item)
result = False
seen_lock.release()
return result
Овде је неопходна брава како би се спречило да друга нит дода интернет адресу у скуп између тренутака када ова нит проверавала да ли је интернет адреса у скупу и тренутка њеног додавања у скуп. Штавише, додавање скупу није атомска операција, па истовремени покушаји додавања скупу могу оштетити његове интерне податке.
У претходном коду мора се бити опрезан да се не врати назад док се претходно не ослободи брава. Уопштено, мора се увек осигурати да се брава ослободи када више није потребна. Ово може бити врло склоно грешкама, посебно у присуству изузетака, тако да Пајтон пружа сложену наредбу with која управља са узимањем и ослобађањем браве уместо програмера:
def already_seen(item):
with seen_lock:
if item not in seen:
seen.add(item)
return False
return True
Наредба with осигурава да је seen_lock узет пре него што се изврши његово тело и да се ослободи када се из било ког разлога његово тело напусти. (Наредба with се заправо може користити и за друге операције поред закључавања, мада овде неће бити покривене алтернативне намене.)
Операције које се морају међусобно синхронизовати морају користити исту браву. Међутим, два неповезана скупа операција која се морају синхронизовати само са операцијама у истом скупу треба да користе два различита закључана објекта како би се избегла прекомерна синхронизација.
Баријере¶
Други начин да се избегне неусаглашен приступ дељеним подацима је подела програма на фазе, осигуравајући да дељени подаци бивају мутирани у фази у којој им ниједна друга нит не приступа. Баријера дели програм на фазе захтевајући од свих нити да га досегну пре него што било која од њих може да настави. Код који се извршава након баријере не може се извршавати истовремено, односно бити конкурентан са кодом који се извршава пре баријере.
У Пајтону, модул threading пружа баријеру у облику методе wait инстанце Barrier:
>>> бројачи = [0, 0]
>>> баријера = threading.Barrier(2)
>>> def бројање(бројНити, кораци):
... for i in range(кораци):
... други = бројачи[1 - бројНити]
... баријера.wait() # чека да се заврше читања
... бројачи[бројНити] = други + 1
... баријера.wait() # чека да се заврше уписивања
>>> def нитноБројање(кораци):
... други = threading.Thread(target=бројање, args=(1, кораци))
... други.start()
... бројање(0, кораци)
... print('бројачи:', бројачи)
>>> нитноБројање(10)
бројачи: [10, 10]
У овом примеру, читање и писање заједничких дељених података одвија се у различитим фазама, одвојеним баријерама. Уписи се дешавају у истој фази, али су раздвојени; ова раздвојеност је неопходна да би се избегла истовремена уписивања у исте податке у истој фази. Пошто је овај код правилно синхронизован, оба бројача ће на крају увек бити 10.
Вишенитни симулатор честица користи баријере на сличан начин за синхронизацију приступа заједничким дељеним подацима. У симулацији, свака нит поседује неки број честица које све међусобно комуницирају током многих дискретних временских корака. Честица има свој положај, брзину и убрзање, а ново убрзање се израчунава у сваком временском кораку на основу положаја осталих честица. Брзина честице мора да се ажурира у складу с тим, а њен положај у складу са њеном брзином.
Као и код једноставног примера горе, постоји фаза читања, у којој све нити очитавају положај свих честица. Свака нит ажурира убрзања својих честица у овој фази, али с обзиром на то да су то раздвојени уписи, не треба их синхронизовати. У фази уписивања, свака нит ажурира брзине и положаје сопствених честица. Поново, ово су раздвојени уписи који су од фазе читања заштићени баријерама.
Преношење порука¶
Коначни механизам за избегавање неправилне мутације заједничких дељених података је потпуно избегавање истовременог приступа истим подацима. У Пајтону, коришћење вишепроцесорске обраде података уместо нити природно даје одговарајући резултат, јер се процеси извршавају у засебним интерпретаторима са сопственим подацима. Било које стање потребно за више процеса може се саопштавати преношењем порука између процеса.
Класа Pipe у multiprocessing модулу садржи комуникациони канал између процеса. Подразумевано је дуплекс, што значи двосмерни канал, иако прослеђивање аргумента False резултује једносмерним каналом. Метода send шаље објекат преко канала, док метода recv прима објекат. Ово друга метода је блокирајућа, што значи да ће процес који позива recv сачекати све док се објекат не прими.
Следи пример произвођача/потрошача који користи процесе и цеви:
def процесПотроши(улазнаЦев):
while True:
ставка = улазнаЦев.recv()
if ставка is None:
return
print('Добио ставку:', ставка)
def процесПроизведи():
цев = multiprocessing.Pipe(False)
потрошач = multiprocessing.Process(target=процесПотроши, args=(цев[0],))
потрошач.start()
for i in range(10):
цев[1].send(i)
цев[1].send(None) # сигнал за завршетак комуникације
процесПроизведи()
У овом примеру користи се порука None да се означи завршетак комуникације. Такође је додат један крај цеви као аргумент циљаној функцији приликом стварања потрошачког процеса. То је неопходно, јер се стање мора експлицитно делити између процеса.
Вишепроцесна варијанта симулатора честица користи цеви за комуникацију и размену информације о положају честица између процеса у сваком временском кораку. У ствари, користи цеви за постављање читавог кружног цевовода између процеса, како би се комуникација свела на минимум. Сваки процес убризгава своје позиције честица у свој део цевовода, које на крају пролазе кроз пун круг у ротацији кроз цевовод. У сваком кораку ротације, процес примењује силе из положаја који су тренутно у његовом делу цевовода на његове сопствене честице, тако да су након пуног круга, односно пуне ротације све силе примењене на све његове честице.
Модул multiprocessing нуди и пружа и друге механизме синхронизације за процесе, укључујући синхронизоване редове, браве и, од Пајтона 3.3, баријере. На пример, брава или баријера могу се користити за синхронизацију исписа на екран, избегавајући неправилан излаз на екрану који је нешто раније приказан.
Синхронизационе клопке¶
Иако су методе синхронизације ефикасне за заштиту заједничког дељеног стања, могу се користити и неправилно, тако да не успевају да изврше одговарајућу синхронизацију, тако што изврше прекомерну синхронизацију или тако што доводе до тога да се програм заглави као резултат застоја.
Недовољна синхронизација¶
Уобичајена клопка у паралелном израчунавању је занемаривање правилне синхронизације дељених приступа. У примеру скупа, мора се заједно синхронизовати провера чланства и уметање, тако да друга нит не може да изврши уметање између ове две операције. Немогућност заједничке синхронизације две операције води ка неисправном понашању, чак и ако су појединачно обе операције синхронизоване.
Прекомерна синхронизација¶
Друга честа грешка је прекомерна синхронизација програма, тако да се неконфликтне операције не могу извршавати истовремено. Као тривијални пример, увек могу да се избегне сав неусаглашени приступ заједничким дељеним подацима тако што ће се узети главна брава када нит започне и ослободити је тек када се нит заврши. Ово сериализује читав изворни код, тако да ништа више не ради паралелно. У неким случајевима то чак може довести до тога да се програм заглави и остане заглављен у недоглед. На пример, размотрити програм потрошача/произвођача у којем потрошач узима браву и никада је не ослобађа. Ово спречава произвођача да производи било које ставке, што заузврат спречава потрошача да било шта учини, јер нема шта да (по)троши.
Иако је овај пример тривијалан, у пракси се често дешава да програмери до неке мере превише синхронизују свој изворни код, спречавајући тако да њихов код у потпуности искористи расположив паралелизам.
Застој¶
Будући да узрокују да нити или процеси чекају једни на друге, механизми синхронизације су подложни такозваном застоју, односно ситуацији у којој су две или више нити или процеса запели и чекају једни на друге да се заврше. Управо је приказано како занемаривање ослобађања браве може проузроковати заглављивање нити у недоглед. Међутим, чак и ако нити или процеси исправно ослобађају браве, и даље може доћи до програмског застоја.
Извор застоја је кружно чекање, приказано у наставку над процесима. Ниједан процес се не може наставити јер чека на друге процесе који и сами чекају да се он сам заврши.
Као пример, биће направљен застој два процеса. Претпоставимо да процеси деле дуплекс цев и покушавају да комуницирају један са другим на следећи начин:
def застој(улазнаЦев, излазнаЦев):
ставка = улазнаЦев.recv()
print('Добио ставку:', ставка)
излазнаЦев.send(ставка + 1)
def направиЗастој():
цев = multiprocessing.Pipe()
други = multiprocessing.Process(target=застој, args=(цев[0], цев[1]))
други.start()
застој(цев[1], цев[0])
направиЗастој()
Оба процеса прво покушавају да приме податке. Подсетимо се да се метода recv блокира док ставка не постане доступна. Будући да ниједан процес није послао ништа, оба процеса ће неограничено чекати да му онај други пошаље податке, што ће резултовати застојем.
Операције синхронизације морају бити правилно усклађене како би се избегао застој. То може захтевати слање преко цеви пре пријема, узимање више брава истим редоследом и осигуравање да све нити досегну праву баријеру у право време.
Закључак¶
Као што је виђено, паралелизам представља нове изазове у писању исправног и ефикасног кода. Како ће се тренд повећања паралелизма на хардверском нивоу наставити у догледно време, паралелно израчунавање ће постати све важније у програмирању апликација. Постоје врло активни истраживачки напори који за циљ имају да паралелизацију за програмере олакшају и учине је мање подложну грешкама. Ова дискусија на овом месту служи само као основни увод у једно од кључних подручја рачунарства.