Názory k článku
Přidělování procesoru procesům a vláknům v Linuxu

Zajimalo by mne, jak je to s planovacem na vice procesorovem systemu. Je mozne, autore, ze by jste zpracoval clanek i na toto tema?

Ingo Molnár napsal pro 2.6 O(1) scheduler, který má sice optimální komplexitu, ale později se ukázalo, že je potřeba čas dělit spravedlivěji. Con Kolivas napsal cheduler založený přibližně na principech EDF http://en.wikipedia.org/wiki/Con_Kolivas , který zajišťuje spravedlivější dělění času, pokud procesy sice vytěžují CPU hodně, ale na určité krátké časové úseky jsou v jádře blokované. Ingo implemetaci kritikou potopil, ale uznal základ přístupu a navrhl vlastní CFQ (Completely Fair Scheduler). Ten je nyní součástí jádra. Jeho komplexita při začleňování do ready fronty je pro SCHED_OTHER přibližně O(log n) – je založen na RB-tree viz. http://en.wikipedia.org/wiki/Completely_Fair_Scheduler
Ani toto řešení není optimální a stále se provádějí postupná zlepšení. Pro real-time aplikace je snaha zavést na místo SCHED_FIFO SCHED_DEADLINE (EDF) http://www.gitorious.org/sched_deadline/pages/Home .
Co se týče rozdělení práce mezi CPU, tak jsou možné dva přístupy, společná fronta – optimální vytížení a přednosti priorit, avšak nutnost společného zámku (možná by šlo najít i nějaké block-less řešení, otázka je pak složitost). Změny ve sdílených řádkách paměti cache znamenají enormní overhead a ping-pong snoop protokolů (např MOESI http://en.wikipedia.org/wiki/MOESI_protocol pro AMD7).
Proto Linux používá na každém CPU lokální fronty a plánovač a s určitým intervalem nebo v idle provádí load balancing.
Odkazy jsem jen narychlo nahledal ve Wikipedii. Nejlepší je si projít přímo zdrojáky http://lxr.linux.no/#linux+v2.6.34/include/linux/sched.h a dále soubory sched*.[ch] z http://lxr.linux.no/#linux+v2.6.34/kernel/ .
Obecně je přínosné, že se někdo pokusil o zpracování tématu na Root, ale bylo by dobré přidat článek s aktuálnějším a preciznějším řešením současné situace.
Další zdroj, který sdružuje hodnotné informace je LWN. Projděte odkazy v sekci Scheduler http://lwn.net/Kernel/Index/
Jinak něco z práce mých kolegů na téma rozvrhování: http://frescor.org/ , http://frsh-forb.sourceforge.net/ .
Pavel Píša
http://cmp.felk.cvut.cz/~pisa/

Užitečný i když poněkud strohý článek, pouze proces bych označil za vícevláknový (nikoliv více vláknový). Podobně jako například procesor je dvoujádrový a ne dvou jádrový. Oddělení slov více a vláknový bych použil, kdybych chtěl zdůraznit, že nějaký proces má větší podporu vláken, než jiný.

diky za clanek, puvodne jsem cekal (podle nazvu), ze budete rozebirat cgroups ale i tak diky, clanek je podle stylu psani urcen pro znalejsi, ale jinak super

Ano, nice není priorita, ale s prioritou přímo souvisí.
To Vy nevíte? Tlačenka…

To vypadá, že terminologie se neustále mění. Nevím jak dnes, ale před nějakými deseti lety to bylo trošku jinak:
program – z hlediska OS základní soubor kódu a dat, který může využívat prostředků daného OS (tj. z něhož může OS vytvořit proces)
proces – plnohodnotná instance programu, tj. základní entita OS, jež může vykonávat nějaký program; více procesů může nezávisle na sobě vykonávat tentýž program
vlákno – minimální instance programu, jež se od procesu liší tím, že implicitně sdílí data s jinými vlákny provádějící tentýž program a tedy obecně, narozdíl od procesu, více vláken nemůže vykonávat tentýž program nezávisle na sobě.

A protože to má Windows tak úžasné a dokonalé, tak není dodnes schopen na vyžádání sestřelit běžící proces v 9 z 10 případů. Občas se dokonce při této snaze na chvíli šprajcne od sklepa na půdu.

Visty tym trpia celkom slusne tiez. ;)

v 9 z 10 případů? spíše v 1 z 10.

Ano, 9 z 10 to urcite nie je, ale 1 z 10 je myslim aj tak viac ako dost. ;)

Pokud potřebujeme proces killnout 1× za měsíc, tak ten problém nastane asi tak jednou do roka.

Ano, 9 z 10 to urcite nie je, ale 1 z 10 je myslim aj tak viac ako dost. ;)

Ale co sa da inak robit s aplikaciou, ktora prestane reagovat? :) Len sa pekne toci a toci koliesko vo Viste, zblednuty Desktop bez odozvy a zamestnanci vyvolavaju, ze nemozu robit. Nezavidim kolegom tuto agendu. :)

Na tom istom HW funguje OSS XEN aj Citrix XenServer s uptimom v stovkach dnoch a desiatkami virtualnych strojov uplne bez problemov (restart iba pri updatoch jadra). Len Vista ma problemy. So sietovkami, s MS Office, s antivirom… ale treba povedat, ze tie instalacie ciastocne rozbilo automaticke stahovanie MS updateov. To je inak tiez pekna vizitka. ;)

Kebyze tam 2 roky nepracujem, tak nic nepoviem. Ide o „desktopy“ s AMD X2 CPU, nForce chipsetom a este pridanou druhou sietovkou v podobe PCI realtek. Ano, je to HW odpad, ale ziadna exotika – napodiv Xen s linuxovym Dom0, XenServer (co je vlastn CentOS Dom0) aj napr. bezny Debian Lenny tam problemy nema ziadne. Tych strojov je dobre cez 100ku…
A aky z toho plynie zaver? Zle ovladace su tak v Linuxe ako aj v roznych Windowsoch, len zatial co pri Linuxe je v pripade otvorenych ovladacoch aspon teoreticka sanca, ze ich raz niekto opravi, pri closed source bloboch vo Win mozme rovno zabudnut. :) A nie len preto by mal byt tlak na vyrobcov HW a kvalitu ich ovladacov vacsi na vsetkych frontach…
Btw. k tomu ralinku wireless, nie je to nahodou v staging vetve jadra? :D

Nemělo by se to ale když člověk narazí na aplikaci, která se nějak šprajcne (ve Windows jen poměrně častý), tak co s tím jiného? Samozřejmě netvrdím, že za zasekávání aplikací může Windows ale čekal jsem, že 7 konečně bude tohle umět. Neumí.

Technické pozadí? K čemu? Windows mám jako BFU, takže mě nezajímá jak to funguje ale jestli to funguje. Mě nezajímá, že systém proces nedokáže/nemů­že/nechce ukončit, protože tento visí na nějakém ovladači, který by mohl vzít s sebou a shodit tak systém. Ostatně, pokud to tak funguje, je to špatně.
Pokud pracuji jako obyčejný uživatel, přepokládám, že násilné ukončení čehokoliv, co jsem spustil může zapřičinit maximálně ztrátu dat v dané aplikaci. Pokud to ale může shodit systém, tak je něco špatně a ten kdo to tak navrhl/implemen­toval by zasloužil přes ruce.

Jo třeba takový ovladač rt61.ko. Pokud se na něj člověk špatně podívá, tak iwconfig nahlásí SIGSEG a následuje buď ihned, nebo během několika vteřin zásek s poblikáváním scroll a caps locku (čili kernel panic). Nejvíc to naštve, když s takovým strojem komunikuji na dálku a pak musím volat domu, aby mi zakvedlali pojistkami.
Tak proč si tam nenainstalujete Windows? A nenapíšete si do nich pořádný ovladač (k Linuxu máte zjevně odpor, takže tam to asi nehrozí)?
Kromě toho toto není příklad, kdy by nešel v Linuxu sestřelit user-space proces kvůli ovladači.

Skutečně? To jsou věci… V tom případě budu MS žalovat za podvod, protože na obalu i na médiích je psáno Windows 7.

>> Jinak proces dle mého pohledu je něco jako „osoba“, která žádá o […]. Vlákno je pak něco jako …
…schizofrenie ;)

To byl jenom takový hloupý vtip. Rozdvojení „osoby“=schizo­frenie

jednoduse receno: proces = spusteny program; ruzne procesy maji oddelene adresni prostory; v ramci procesu muze bezet vice vlaken, ktera sdileji data (resp. cely adresni prostor daneho procesu).
Kdyz se na problem nahlizi trochu jinak, je mozne proces chapat proste jako neprazdnou mnozinu vlaken.
Cely problem je pak o tom jestli OS planuje prideleni procesoru procesu (tj. cele mnozine, ktera si pak musi sama vybrat, ktere vlakno spusti) a nebo konkretnimu vlaknu (a oznaceni proces pak degraduje na jakysi „tag“, ktery oznacuje vlakna sdilejici spolecny adresni prostor)

Ono to asi trochu vychází z jiné filosofie jádra. Pokud si dobře pamatuji pak Linuxové jádro interně nijak nerozlišuje mezi vláknem a procesem – oboje je pro něj prostě úloha (task). Jediný rozdíl mezi vláknem a procesem je ve sdílení adresního prostoru. Domnívám se, že to má i svoji logiku. Jak tu bylo již – podle mě správně – řečeno proces je defacto množina, jednoho a více vláken. Jestliže tedy jádro pracuje s nějakým procesem, operuje stejně vždy přímo s nějakým konkrétním vláknem (úlohou)…

Narocnost prepinani asi bude zaviset jak zpusobem se prepinani realizuje.
Napr. jestli bezi v OS dva procesy A, B a kazdy ma dve vlakna Aa, Ab a Ba a Bb
tak jestli chce Windows prepnout z vlakna Aa na Ba, tak musi byt context switch a za nim thread switch. Na Linuxu se to prepne jednou operaci.
Taky Linux nemusi delat context switch pri prepinani vlaken v ramci jedne aplikace.

Nevím, jestli kolega asdf má, nebo nemá přístup ke zdrojákům Windows, ale upřímně, podle Vašeho výše uvedeného popisu mě napadl podobný mechanizmus.

Pokud Vás dobře chápu pak Win velice striktně rozlišují (na rozdíl od Linuxu) mezi procesem a vláknem. Nepopírám, že určité výhody to mít může, ovšem obávám se, že s takovým přístupem budou muset tak jako tak i oba „objekty“ rozdílně zpravovat a jiným způsobem s nimi i nakládat. Dá se to samozřejmě do jisté míry optimalizovat, ale stejně se mi zdá, že takový mechanizmus je (čtěte prosím – „hypoteticky by byl“) zbytečně složitý; a výhody jeho využití jsou … mírně řečeno silně polemické. Navíc obávám se, že se stoupající složitostí a abstraktností přímo úměrně stoupá i náročnost.

To bylo hodně abstraktní. Ale plánovač windowsu není nějak obecný, ten pouze plánuje vlákna. Vlákno je prostě jeden z prostředků (CPU time). Veškeré řízení, plánování atd je prostě děláno zkrze vlákna. Přepínání kontextu procesu se děje jen jako nutnost, když se naplánuje vlákno z jiného procesu, než je původní proces. Ale to je jen tak mimoděk. Optimalizace se jen nabízí v tom směru, že plánovač může upřednostňovat vlákna aktuálního procesu, před přepnutím celého kontextu, ale samozřejmě jen do určité míry, aby nedošlo k vyhladovění.

„Už proto, že v linuxu mohu mezi procesy sdílet jen něco, nebo všechno (pak je to vlákno). "

Teď Vám asi dost dobře nerozumím. Pokud to dobře chápu, pak jádro Linuxu vytvoří nový proces ve chvíli, kdy vytvoří první úlohu tohoto procesu. Té je potom přidělen adresní prostor, zdroje a priority implicitně podle oprávnění. Byl vytvořen první task = hlavní vlákno = proces. Jakmile je potřeba vytvořit nové vlákno vytvoří (naklonuje) se nový task, který "zdědí“ všechno od toho rodičovského. Tam není všechno – nic. Žádná úloha nemá přístup ke všem zdrojům, které má jádro k dispozici – to přece ani z principu nejde (možná tak v DOSu, ale určitě ne v os unixového typu).

S trochou drzosti (a hodně zjednodušeně) se dá říci, že jádro Linuxu vůbec pojmy typu proces a vlákno nezajímají. Jeho zajímají pouze konkrétní úlohy…

Jednoduse popsane rozdily mezi procesem a threadem (vlaknem) v Linuxu jsou:
1. proces stejne jako thread se startuje pres funkci clone() jenom s jinymi flagy.
2. Pri startu procesu se alokuje environment a podobne.
Proto z hlediska kernelu existuji jenom vlakna (thready), kernel ma jenom jednu funkci – clone(). Co se deje pri startu vlakna se urcuje s pomoci flagu – jake prava se zdedi s parentu, jake primitivy se zavrou a alokuji znovu nebo zustanou otevrene, atd.

a fork() je wrapper pro clone() s jinymy flagy

Proces a thread je jen terminologie pouzivana v ramci nejakeho konceptu/modelu.
Jinak, aby byl uplny terminologicky chaos, tak kernel pracuje s necim cemu rika „kernel tasks“. Toto jsou rozvrhovatelne ulohy. Procesy (resp. vlakna) se „mapuji“ na jednotlive tasky.
syscallu clone se da rict jestli ma pri vytvareni nove instance kopirovat data nebo ne, coz je hlavni rozdil mezi procesy a vlakny (vlakna maji sdilena data, procesy jsou izolovane).

Hodnotný článek i diskuze (no pun intended)
Zajímavé, díky všem

Nexeistuje nejaky priklad, na kterem by se daly demostrovat vyhody pouziti jednotlivych thread-scheduleru? Kdy ma prakticky vyznam pouzit jiny nez defautni?