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ý.
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ě.
Process – chápu jako kolekce vláken. Každý proces by měl mít minimálně jedno vlákno (ale není to podmínkou, dokážu si představit procesy reagující na přerušení, kterým je vlákno přiděleno až když je potřeba)
Vlákno – prostědek, díky němuž proces žije
Fiber – (windows terminologie), uživatelské přepínání běhových rámců v rámci vlákna.
Jinak proces dle mého pohledu je něco jako „osoba“, která žádá o prostředky jako paměť, disk, jiné periferie a procesor. Vlákno je pak něco jako instance přiděleného prostředku typu procesor.
Linux má tohle naprosto zvráceny, ten nezná procesy bez vláken, resp. procesem je vždy myšlen běžící program.
Koupit zaměstnancům lepší HW. Znám opravdu málo padajících a zasekávajících aplikací. Takže pokud se Vám to děje často, nebude problém autorech aplikace.
Je zajímavý, že Windowsy se leckdy provozují na HW, na kterým by si linux ani neškrtl. Pro něj se kupuje HW o kterém se ví, že s ním linux funguje :-)
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
> je v pripade otvorenych ovladacoch aspon teoreticka sanca, ze ich raz niekto opravi
Ta šance je vskutku jen teoretická. Sám to dělat nebudu a nikdo na to nemá čas, řvát na bugreportu mohu do nekonečna, efekt nulový
> Btw. k tomu ralinku wireless, nie je to nahodou v staging vetve jadra? :D
rt61pci.ko – je součástí instalace ubuntu, netuším v jaké úrovni, nezkoumal jsem to. Je mizerný, umí jen základní veci a nedá se provozovat na kanálech 12–13.
rt61.ko – byl do nedávna alternativou, akorát po každé aktualizaci jsem ho musel překompilovat, uměl i kanály 12–13, měl jsem na něm lepší příjem a byl tam lepší monitoring a fungoval na něm i aircrack a to o 100% lépe než na rt61pci. Jeho nevýhodou bylo, že občas padnul právě tak jak jsem napsal. Od verze Ubuntu 10 se už nedá přeložit, verzi novou jsem nenašel, jen nářek uživatelů na různých fórech.
U rt61pci se projevuje ještě tato chyba:
http://www.google.cz/search?q=garbage+in+essid
Provozovat se tedy dá jen pomocí network-manageru, který to obchází, ovšem network-manager na servery není zrovna určen.
Kilnout aplikaci není problém. Otázkou je, co ta aplikace dělá. Pokud je to aplikace, která pracuje s thrid part ovladačem, který není napsán tak dobře, aby rozdejchal to, že mu umřel klient, tak pak s tím operační systém nic neudělá. Nezapomeňte, že TerminateProcess je akce definitivní a v userspace víceméně neexistuje způsob, jak říct někomu třetímu, že umřel proces, snad vyjma handlů, které drží ten proces otevřený. Ty se stanou signalizovanými. A to je tak všechno. Pokud je ovladač závislý na ručním úklidu ať už na atexit nebo přes DllMain (DLL_PROCESS_DETACH), tak je to špatný ovladač, protože zabitím procesu se ruční úklid neudělá.
Samozřejmě, ovladače přímo od microsoftu tyhle problémy nemají, ale dáte ruku do ohně za ovladač od NVidie nebo od Atiny? Nebo od nějaké obskurdní síťové karty?
OS Windows, stejně jako OS Linux neběží ve více než dvou rincích. Pád ovladače tedy zpravidla znamená pád celého operačního systému. A mohu vám garantovat, že stejný problém jsem schopen najít i v linuxu. 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.
Než něco plácnete, zjistěte si technické pozadí. Ono kilnout proces není bez rizika ani ve Windows, ani v Linuxu. Mimochodem, jak v linuxu poznám, že mi někdo zabil proces? (devítkou)
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/implementoval by zasloužil přes ruce.
Ale Microsoft Windows nemá jednoho autora. To je otevřený systém, kde přispívají výrobci třetích stran. I v jejich programech bývají chyby. Až Vám se zase Windows kousnou při sestřelení aplikace, zkuste zjistit metodou pokus omyl, čí ovladač hapruje? Zjistí te, že to bude nějaký k HW se značkou Made in China.
Mimochodem, ani SIGKILL nedává uživateli jistotu, že se provede:
http://en.wikipedia.org/wiki/SIGKILL
> Mimochodem, jak v linuxu poznám, že mi někdo zabil proces? (devítkou)
Z kernel-space nebo z user-space?
Kernel to pozná stejně jako ukončení jakýmkoli jiným způsobem. Používané prostředky jsou uvolněny v do_exit(). Z user-space to pozná jenom rodič (nebo debugger) tak, že dostane SIGCHLD a pomocí wait() si vyzvedne stavový kód.
RTFM, chtělo by se říci…
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.
A ještě nějaké povídání na to téma: http://msdn.microsoft.com/en-us/library/ms686722(v=VS.85).aspx
Nevím co se Vám na tom nezdá. Vlákno je prostředek OS stejně jako třeba diskový soubor, přidělená paměť, nebo síťové spojení.
Jestli je Vám divné, že někdo „žádá“ o vlákno, a přitom vlastně nemůže, tak samozřejmě může, třeba pomocí vypůjčeného vlákna, nebo může žádat o „další vlákno“. Stejně jako proces potřebuje nějakou paměť aby vůbec mohl o paměť žádat :-)
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)
Tady se to myslím dost liší od Windows, kde vlákna to co se plánuje, protože procesy obecně „neběží“. Že běží proces je dané tím, že vlastní aspoň jedno vlákno. Při přepínání vláken mezi procesy se sice musí přehazovat kontext celé procesu (u přeplánování v rámci procesu nemusí), ale to je asi tak všechno, kde proces v rámci plánování figuruje.
Pak ještě maximálně tak u řízení priority, kdy se procesu přiděluje prioritní skupina (Priority Group), která určuje mapování priorit vláken v procesu na globální priority pro plánovač (vláken). Opět tedy není to priorita procesu, ale priorita vláknem (proces má jen skupinu)
A do třetíce, funkce CreateProcess ve windows vytváří prázdný proces a jako poslední akci kterou udělá je, že v něm spustí vlákno pomocí CreateRemoteThread. Teoreticky lze funkci CreateProcess emulovat v userspace a vytvořit tak proces bez vlákna a vlákno mu přidělit až v okamžiku potřeby pomocí výše uvedené funkce.
V tomhle systém vidím lepši koncepci řízení a plánování procesů a vláken.
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)…
A co se týče náročnosti? Když na Windows poběží jeden proces ve dvou vláknech (na jednom CPU), bude (prý) plánování efektivnější, než když poběží dva jednovláknové procesy. Souvisí to s přepínáním stránkových registrů a kontextů procesů, což se u prvního případu nemusí řešit.
Už proto, že v linuxu mohu mezi procesy sdílet jen něco, nebo všechno (pak je to vlákno). Pokud je vlákno „lehký proces“, pak bych viděl problém v náročnosti přepínání na úrovni vláken … bude stejná jako přepínat procesy. Pak chápu i to, proč ve Windows se hodně tlačí vláknová řešení, zatímco v linuxu si vystačím s forkem.
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.
Nejsem si jist, jestli Vy máte zdrojáky k jádru Windows, že víte, že tam jsou dva switche. Ten switch mezi procesy se samořejmě provede jednorázově tzn. přepnou se vlákna a při té přiležitosti se prohodí ukazatele na kontexy. Pokud se přehazují vlákna z jednoho procesu, operace přehození konextů se prostě vynechá
if (processId1 == processId2) goto skipContextSwitch;
O tom, že plánovač může být optimalizován tak, aby procesy přepínal v delším intervalu, než vlákna nemluvně. Pak může přepínání vypadat třeba takto Aa,Ab,Aa,Ab,Ba,Bb,Ba,Bb,… A máte tam minimum context switchů
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.
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).