Zabić Big Kernel Lock
- Dodano: 14 maja 2008
- Wprowadził: optimizationkit
- Komentarze: 64
Ingo Molnar wysłał na LKML wiadomość w której poinformował o stworzeniu nowego drzewa, którego celem będzie usunięcie BKL z jądra Linux. Kiedyś opisałem do czego są używane blokady i dlaczego są ważne — różnica pomiędzy Big Kernel Lock a innymi mechanizmami blokad jest taka, że BKL, jak sama nazwa wskazuje, blokuje całe jądro nie pozwalając innym procesom na działanie dopóki nie zostanie zwolniona.
Robert Love w swojej książce o programowaniu Linuksa napisał „Blokada BKL to czyste zło”, poniżej zamieszczam tłumaczenie wiadomości Ingo w której opisał co chce zrobić temu czystemu złu 
.
Jak niektórzy fani niskich opóźnień wiedzą, commit 8e3e076 („BKL: revert back to the old spinlock implementation”) w 2.6.26-rc2 usunął funkcję wywłaszczania BKL i zamienił ją w spinlock (W Polsce szerzej znany jako blokada wirująca lub rygiel pętlowy, ale obie nazwy mi się nie podobają i będę używał angielskiej. przyp. tłum.) przez co kod jest ponownie niewywłaszczalny. Ta łatka przywróciła stan BKL z jądra 2.6.7.
Linus również wskazał, że jedynym akceptowalnym (dla nas, ludzi od -rt, raczej mało szczęśliwym) sposobem na usunięcie źródeł opóźnień i niewywłaszczalnych blokad jest wyrzucenie BKL.
To zadanie wcale nie jest łatwe. Dwanaście lat po tym, jak Linux zaczął wykorzystywać SMP, ciągle mamy powyżej 1300 sytuacji wykorzystujących BKL. Jest powyżej 400 krytycznych sekcji z lock_kernel() oraz powyżej 800 w ioctl. Są porozrzucane w różnych, przeważnie trudnych obszarach starego kodu, który niewiele osób rozumie i niewielu odważa się go modyfikować.
Zadaniem powinni się zająć ludzie tacy jak Alan Cox, nawet dla niego (Alan wyrzuca BKL z kodu TTY) jest to trudne i czasochłonne.
Zgodnie z moimi szybkimi analizami w oparciu o git-log, przy aktualnym tempie wyrzucania krytycznych sekcji BKL z jądra, powrót do akceptowalnych opóźnień zajmie ponad dziesięć lat.
Największym technicznym problemem jest to, że BKL w przeciwieństwie do innych blokad zostaje automatycznie zwolniona po wywołaniu funkcji schedule(). To czyni spinlock BKL bardzo „lepkim”, „niewidocznym” i „wirusowym” – bardzo łatwo jest go dodać do kawałka kodu (nawet nieświadomie) i nigdy tak naprawdę nie wiesz czy jest przetrzymywany czy nie. PREEMPT_BKL uczyniło go jeszcze bardziej niewidocznym, ponieważ jego efekty były jeszcze mniej widoczne dla zwykłych użytkowników.
Poza tym BKL jest nieobsługiwana przez lockdep (mechanizm sprawdzania poprawności użycia blokad w systemie przyp. tłum.) a więc jej zależności są w dużej mierze niewidzialne i nieznane, a to wszystko gdzieś w pyle ostatnich piętnastu lat zmian w kodzie. Wszystko to się złożyło na FUD (Fear, Uncertainty and Doubt) o BKL: nikt jej tak naprawdę nie zna, nikt nie jest dość odważny aby ją zmienić a kod może subtelnie i dyskretnie popsuć jeśli blokowanie BKL jest niepoprawne.
A więc przy aktualnych zasadach gry, nie możemy naprawdę naprawić kodu używającego BKL. Ludzie nie będą w stanie zmienić 1300 bardzo trudnych i delikatnych ścieżek kodu jądra w ciągu jednej nocy, tylko po to, aby zmniejszyć opóźnienia.
Więc… ponieważ uważam, że więcej niż dziesięć lat czekania na poprawę sytuacji jest raczej nie do zaakceptowania, proponuję inne rozwiązanie – spróbujmy zmienić zasady gry
Celem jest uczynienie usunięcia BKL bardziej prostym i naturalnym – uczynienie BKL bardziej widoczną i usunięcie elementu FUD.
Aby osiągnąć te cele utworzyłem gałąź „kill-the-BKL” w drzewie -tip. Aktualnie gałąź zawiera dziewiętnaście różnych łatek:
git://git.kernel.org/pub/scm/linux/kernel/git/tip/linux-2.6-tip.git kill-the-BKL
Ta gałąź (na podstawie najnowszego -git) implementuje największe (i najbardziej krytyczne) zmiany w jądrze mające na celu usunięcie BKL:
- naprawia wszystkie „automatyczne zwolnienia BKL podczas wywołania schedule()” jakie mogłem namierzyć na moich testowych maszynach
- dodaje funkcje debugowania ostrzegającą o niezgodnym z nowym modelem blokowania użyciu BKL
- zamienia BKL w zwykły mutex i usuwa cały kod automatycznie zwalniający blokady BKL z planisty zadań
- zapewnia wsparcie dla BKL w lockdep (mechanizmie sprawdzania poprawności blokad)
- włącza BKL na maszynach jedno procesorowych z wyłączonym wywłaszczeniem – czyni to kod prostszym i bardziej uniwersalnym i miejmy nadzieję, że skłoni to więcej ludzi do pracy nad usunięciem BKL
- czyni sekcje BKL ponownie wywłaszczalnymi
- … poważnie upraszcza kod BKL i przenosi go poza centralną część jądra
Innymi słowy drzewo kill-the-BKL zamienia BKL w zwykły, duży mutex z ekscentrycznym interfejsem nazywanym „lock_kernel()” i „unlock_kernel()”.
Najbardziej interesującym commitem jest aa3187000:
„remove the BKL: remove it from the core kernel!”.
Gdy to drzewo się ustabilizuje, eliminacja BKL może zostać przeprowadzona zwyczajną i dobrze znaną metodą eliminacji wielkich blokad przez: przeniesienie jej do podsystemów i zamianę na blokady w nich używane, rozdzielenie i eliminację blokad. Robiliśmy to już wiele razy w przeszłości i jest wielu deweloperów potrafiących radzić sobie z takimi problemami.
W przyszłości możemy również spróbować wyeliminować funkcję rekurencji (zagnieżdżonego blokowania) BKL – to uczyni kod BKL bardziej oczywisty.
Shortlog, diffstat i łatki są poniżej. Przetestowałem je na 32 i 64 bitowych x86.
Uwaga: kod jest bardzo eksperymentalny – zalecane jest używanie go z włączonymi PROVE_LOCKING i SOFTLOCKUP_DEBUG. Jeśli znajdziesz jakieś ostrzeżenie od lockdep lub softlockup, proszę o jego zgłoszenie. (..)
Więcej informacji: http://www.ussg.iu.edu/hypermail/linux/k.../2633.html
Znalazłeś literówkę? Zgłoś ją używając formularza!
Jeśli uważasz, że ten nius jest nieobiektywny, przedstawia nieprawdziwe wydarzenie, jest spamem lub nie spełnia standardów serwisu, napisz raport.
Niusy na podobny temat:
Komentarze są prywatnymi opiniami dodających je osób. Prosimy o zachowanie kultury wypowiedzi. Komentarze obraźliwe oraz obniżające poziom serwisu będą usuwane. Więcej w regulaminie komentowania.
64 komentarzy
Wszystkie autorskie niusy w serwisie publikowane są na licencji Creative Commons Uznanie autorstwa 2.5 Polska.
Trasz, wiem, że z FreeBSD usunęliście Giant Lock, ale nie musisz z tego powodu rozpoczynać kolejnego flejma
Niestety giant jeszcze funkcjonuje w niektórych miejscach, m.in. właśnie w napisanym 30 late temu kodzie TTY – ale faktycznie został usunięty z wielu dużo bardziej istotnych i krytycznych miejsc (system plików, stos tcp/ip).
http://wiki.freebsd.org/SMPTODO
@optimizationkit: No wlasnie nie do konca. Z opisu powyzej wyglada, ze FreeBSD i Linux ida leb w leb. Z tym, ze FreeBSD zaczelo kilka lat pozniej. Niby moglbym flejma w tym kierunku pociagnac – jak to we FreeBSD praca idzie szybciej, mimo ze srodkow (developerow) jest wielokrotnie mniej. No ale…
…no, ale szybko ktoś by ci wypomniał, że na jednym froncie idzie szybciej by na drugim zwolnić
A slyszal ktokolwiek o czyms takim w Windowsie?
jakis mechanizm blokad na multiprocesorze musi tam istniec.
Tylko pewnie malo kto wie jaki ;]
@vampire: W przeciwienstwie do Linuksa Windows jest bardzo dobrze udokumentowany. Synchronizacja jest opisana bodajze w DDK.
Cokolwiek by tam nie było, Windows się zupełnie do Realtime nie nadaje, podczas gdy Linux czy inne FreeBSD po kilku łatach — jak najbardziej.
Windows do zastosowan soft realtime – chociazby zgrywania dzwieku – jest uzywane od lat. Linux dopiero zaczyna.
@marcin, @trasz
Wydawało mi się, że w jakimś opisie nowej wersji czytałem o usunięciu GL z kodu jądra. Widocznie źle zapamiętałem, bo pewnie chodziło o to o czym napisał Marcin.
Ech, powoli zaczynam żałować że zostałem przy 2.6.22…
Czyżby to były przymiarki do systemów czasu rzeczywistego? Nawet jeśli nic z tego nie wyjdzie to fajnie mieć mniejsze opuźnienia, a co za tym idzie lepsze wykorzystanie mocy procesora.
Przymiarki do systemu -rt są w kernel dot org/pub/linux/kernel/projects/rt/
Mysle ze usuniecie BKL to bylby duzy postep rowniez w kierunku systemow rt.
Tak, oczywiście.
Zazwyczaj jestem pewny jednej z wersji, ale tutaj nie mogę się zdecydować… Ta wypowiedź to ironia, czy nie?
@ktoś
To nie jest ironia. Eliminacja BKL wpłynie bardzo pozytywnie na zmniejszenie opóźnień w jądrze, co przełoży się na lepsze działanie drzewa waniliowego jak i -rt.
Ja tam myślałem, że ironia w drugą stronę. Bo przecież to oczywiste jest.
Trwają również prace nad fine-grained threading w NetBSD. Zainteresowanym polecam materiały:
http://osnews.pl/owoce-pracy-andrew-dorana-netbsd… http://osnews.pl/smp-w-netbsd-bedzie-lepsze/ http://www.netbsd.org/~ad/smp/tasks.html http://ftp.netbsd.org/pub/NetBSD/NetBSD-current/s… http://mail-index.netbsd.org/netbsd-announce/2008…
optimizationkit, mam nadzieje ze bedziesz zarzucal nas aktualnosciami w tym temacie — jestem bardzo ciekawy postepow.
"zarzucal nas aktualnosciami w tym temacie"
Nie jestem pewien, czy większość czytelników chce takiego zarzucania nowościami z frontu walki z BKL. Ale jak coś się ciekawego będzie działo przy Linuksie, to postaram się przetłumaczyć/napisać.
ja tam chetnie czytam twoje newsy o tym twoim pakiecie czy o nowosciach w kernelu, dla mnie to interesujace
b. dobry news. Chetnie poczytam kolejne. Sprawa mnie dosci interesuje, niestety z powodu braku czasu nie moge juz od pewnego czasu sledzic rozwoju jadra.
Moj wlasny kod zjada duzo czasu…
http://mcv.mulabs.org/img/do-want.jpg
Przełączanie się między normalnym jądrem a tym „RT” do audio trochę niewygodne jest.
zastanawiam sie jak sie z tego wygrzbią i czy w kernelu nie ma podobnej bomby zegarowej ktora za pare lat wyjdzie na wierzch i bedzie stwarzac podobne problemy.
spinlock tłumaczy się jako wirujące blokady.
(W Polsce szerzej znany jako blokada wirująca lub rygiel pętlowy, ale obie nazwy mi się nie podobają i będę używał angielskiej. przyp. tłum.)
Czyż to nie straszne? ;P
Nie rozumiem minusów dla dirdival.
Autor newsa miał prawo napisać jak chciał, ale jest to jak najbardziej rzeczowy komentarz. dirdival nie czepia się wyboru dokonanego przez autora newsa, tylko stwierdza fakt.
tu nie ma nic do rozumienia… poprostu komus sie nie podobalo, ze probuje on narzucic niepopularne tlumaczenie pewnego zwrotu – ot i tyle…
Bzdura. ,,Wirująca blokada'' to jest jakaś paskudna kalka językowa. Spinlock to (w nomenklaturze Linuksa) aktywnie czekający semafor (od ,,busy wait''). Ogólnie w programowaniu równoległym spinlock to implementacja semafora (Dijkstra, IIRC, pokazywał implementację semafora właśnie jako spinlock na pewnej zmiennej). A literatury w której ktoś przetłumaczyłby spinlock na polski jeszcze nie widziałem (może dlatego, że nie czytam polskich tłumaczeń
).
"A literatury w której ktoś przetłumaczyłby spinlock na polski jeszcze nie widziałem (może dlatego, że nie czytam polskich tłumaczeń
)."
W literaturze używane są tłumaczenia "blokada wirująca" i "rygiel pętlowy", co jak słusznie zauważyłeś, nie oddaje prawdziwego znaczenia terminu spinlock. Ja nie mam zamiaru wymyślać kolejnego beznadziejnie brzmiącego i mylnego tłumaczenia, więc używam angielskiej nazwy.
W jakiej literaturze? Konkretne książki (tak dla potomności, coby pośmiać się z/uważać na tłumaczy).
"rygiel pętlowy" w "Kernel Linux Przewodnik programisty" – pierwsze wydanie "Linux Kernel Development" Roberta Love wydane przez Helion
"blokada wirująca" w różnych podręcznikach akademickich – kilka z nich można znaleźć na Google pod hasłami "blokada wirująca", "blokady wirujące" – nawet wypada książka "Między asemblerem a językiem C. Podstawy oprogramowania"… Mam niejasne przeczucie, że ten termin to jakiś wynalazek Uniwersytetu Warszawskiego.
BTW. W tłumaczeniu LKD nawet zrobili literówkę w nazwisku autora na okładce, więc się nie dziwię, że wymyślali rygle pętlowe…
chyba rowniez i tlumaczenie "Podstaw systemow operacyjnych" Silberschatz'a uzywa pojecia blokady wirujacej lub blokady petlowej.
Nie mam ksiazki pod reka wiec nie sprawdze i glowy za to nie daje.
Ależ spinlock działa w pętli, więc jak najbardziej określenie „pętlowe” pasuje. W przeciwieństwie do blokad, które oddają czas procesora (nie wnikam jak akurat w Linuksie _teraz_ jest to zrobione). A że się gdzieś tam komuś nie podoba?
heh, widzę, ze komentarze michuka zniknęły. nie wiem, kto je skasował, to powstało na chwilę przed zniknięciem – i wybaczcie, że mimo wszystko to publikuję:
michuk, o co ci chodzi?
czemu mam wrażenie, że traktujesz Torvaldsa jak zło wcielone? co konkretnie do niego masz?
jeżeli masz jakieś merytoryczne uwagi/zastrzeżenia – opisz je. rzucanie losowo komentarzy takich, jak wyżej, do niczego nie prowadzi, a tylko sprawia, że tracisz karmę, a inni nerwy.
Linus zaczął pisać to jajko, i dobrze mu to wyszło jak widać. Jasne, że "trzyma łapę na kodzie", ale bardziej na zasadzie "BDFL", a nawet nie tak autorytarnie. Ktoś musi, proste.
Jasne, że robi czasem przy tym błędy (całe zamieszanie ze schedulerem na ten przykład), ale jest tylko człowiekiem. I jak na człowieka – moim skromnym zdaniem – osiągnięcia ma ogromne.
A jeżeli uważasz, że Linus daje ciała na całej linii, jajko mogłoby się lepiej i szybciej rozwijać, a ty jesteś lepiej sytuowany do pełnienia funkcji "trzymającego łapę", ew. że dostęp do gita powinien być bardziej otwarty – forkuj, na Bożka, i przestań żesz szerzyć FUD!
"michuk, o co ci chodzi?"
Tak, żeby nie było wątpliwości – to nie były komentarze naszego ojca dyrektora, tylko osoby, która się pod niego podszywa.
Cholera, zabrzmiało jak tłumaczenie po nagraniu słynnych taśm innego ojca dyrektora…
Czeeeść, traaasz!
Bardzo ciekawy news z samego rana,thx:)
"Nie jestem pewien, czy większość czytelników chce takiego zarzucania nowościami z frontu walki z BKL. Ale jak coś się ciekawego będzie działo przy Linuksie, to postaram się przetłumaczyć/napisać."
Trzymam za słowo, pozdrawiam
a teraz niech ktoś napisze, to dobrze czy źle i jakie będą tego skutki. najelpiej niech to zobrazuje na przykładach
Czytałeś mój opis blokad? Jeśli nie, to przeczytaj, wszystko powinno być jasne.
BKL blokuje całe jądro dla jednego wątku (w przeciwieństwie do innych blokad, które blokują poszczególne struktury danych), inne wątki muszą czekać na zwolnienie blokady. Skutkuje to tym, że może dojść do bardzo dużych opóźnień np. coś w systemie plików blokuje jądro i sterownik karty dźwiękowej nie może wysyłać danych do urządzenia – słyszysz, że muzyka przerywa (taki bardzo abstrakcyjny przykład).
BKL było stosowane w jądrze na samym początku wprowadzania obsługi SMP, później zaczęto stosować blokady o mniejszej ziarnistości (blokujące konkretne struktury danych a nie całe jądro) a BKL pozostało w starym kodzie. Usunięcie tej blokady wpłynie bardzo pozytywnie na zmniejszenie wszelkiej maści opóźnień w jądrze. Jest to trudne zadanie, bo będzie wymagało wprowadzenia zmian w bardzo starym kodzie, który znają tylko niektórzy deweloperzy, a zmiany muszą być dobrze przemyślane ze względu na specyfikę BKL – trudno zastąpić tę blokadę inną bez poważniejszych zmian kodu.
dzięki, teraz kapuję
wielkie dzięki za takie tłumaczenia optimizationkit, właśnie takie teksty lubię czytać najbardziej
A ja mam pytanie. Dlaczego usunięto wywłaszczanie BKL? Robiło problemy, czy co? Ja właśnie chodzę pod własnoręcznie skompilowanym jajkiem z wywłaszczanym BKL i nie płaczę.
Ktoś wie?
Opis z łatki Torvaldsa
commit 8e3e076c5a78519a9f64cd384e8f18bc21882ce0
"BKL: revert back to the old spinlock implementation
The generic semaphore rewrite had a huge performance regression on AIM7
(and potentially other BKL-heavy benchmarks) because the generic
semaphores had been rewritten to be simple to understand and fair. The
latter, in particular, turns a semaphore-based BKL implementation into a
mess of scheduling.
The attempt to fix the performance regression failed miserably (see the
previous commit 00b41ec2611dc98f87f30753ee00a53db648d662 'Revert
"semaphore: fix"'), and so for now the simple and sane approach is to
instead just go back to the old spinlock-based BKL implementation that
never had any issues like this.
This patch also has the advantage of being reported to fix the
regression completely according to Yanmin Zhang, unlike the semaphore
hack which still left a couple percentage point regression.
As a spinlock, the BKL obviously has the potential to be a latency
issue, but it's not really any different from any other spinlock in that
respect. We do want to get rid of the BKL asap, but that has been the
plan for several years.
These days, the biggest users are in the tty layer (open/release in
particular) and Alan holds out some hope:
"tty release is probably a few months away from getting cured – I'm
afraid it will almost certainly be the very last user of the BKL in
tty to get fixed as it depends on everything else being sanely locked."
so while we're not there yet, we do have a plan of action."
"Ja właśnie chodzę pod własnoręcznie skompilowanym jajkiem z wywłaszczanym BKL i nie płaczę."
Też nigdy nie miałem z tym problemów, ale inni mieli.
To trochę tak jak pisał Con Kolivas – spadek wyników jądra w jakimś enterprise-benchmarku powoduje nagły przypływ Mocy i parcie na tarcie żeby to poprawić.
Ja jestem ciekaw czy dobrodziejstwa też spłyną na użytkowników desktopów.
omawiane w artykule kwestie sa dla mnie (zwyklego uzytkownika) zupelnie obce, mam wiec pytanie. czy dla zwyklego uzytkownika (tzn na desktopach) ma to jakies znaczenie? czy przyniesie wzrost wydajnosci w codziennych czynnosciach? czy moze jedynie w przypadku bardzo zlozonych operacji?
Ma znaczenie, o ile masz więcej niż jeden rdzeń, albo procesor (jeśli dobrze zrozumiałem).
W czasach, gdy procesor dwurdzeniowy można kupić za 120 PLN, maszyny UP powoli odchodzą do lamusa…
Kilka komentarzy wyżej nenros pytał o to samo, jeśli odpowiedź była niewystarczająca mogę doprecyzować.
rzeczywiscie, nie doczytalem tego komentarza. ale jest przeciez cos takiego jak planista. czy w takim razie BKL jest gdzieś "głębiej"?
czy moze poruszam w tym momencie zupełenie inną kwestię?
BKL blokuje jądro dla procesu i dopóki nie zostanie wywołana funkcja schedule() (wybierająca następne zadanie do uruchomienia) blokada jest utrzymywana. Gdy zostanie wywołana funkcja schedule(), blokada zostaje automatycznie zwolniona i zaczyna być obsługiwany kolejny wątek. Gdy wątek używający BKL zostanie wznowiony, blokada zostaje automatycznie przywrócona. Tak to wygląda w _dużym_ uproszczeniu.
Przed wprowadzeniem łatki 8e3e076c5a78519a9f64cd384e8f18bc21882ce0 blokada była wywłaszczalna, czyli planista mógł podjąć decyzję o wstrzymaniu wątku utrzymującego blokadę i uruchomieniu innego wątku. Teraz blokada obowiązuje dopóki nie zostanie wywołana funkcja schedule() lub nie zwolni jej używający jej wątek.
Ja bym chciał zobaczyć te algorytmy rekurencyjne w jądrze, o których mowa w artykule.
"W przyszłości możemy również spróbować wyeliminować funkcję rekurencji (zagnieżdżonego blokowania) BKL – to uczyni kod BKL bardziej oczywisty."
"In the future we might also want to try to eliminate the self-recursion
(nested locking) feature of the BKL – this would make BKL code even more
apparent."
Z tego newsa wnioskuję że BKL siedzi w starej części jądra której niewielu rozumie. Znaczy się za 10, 15 lat będą takie obszary jądra o których nikt nic nie będzie wiedział po za tym że do czegoś służą.