W jaki sposób potoki ograniczają użycie pamięci?

36

Brian Kernighan wyjaśnia w tym filmie, że wczesna atrakcja Bell Labs dla małych języków / programów opiera się na ograniczeniach pamięci

Duża maszyna miałaby 64 k-bajtów - K, a nie M lub G - a więc oznaczało to, że żaden indywidualny program nie mógł być bardzo duży, a więc naturalną tendencją było pisanie małych programów, a następnie mechanizmu potoku, w zasadzie przekierowanie danych wejściowych, umożliwiło połączenie jednego programu z drugim.

Ale nie rozumiem, w jaki sposób mogłoby to ograniczyć zużycie pamięci, biorąc pod uwagę fakt, że dane muszą być przechowywane w pamięci RAM, aby przesyłać je między programami.

Z Wikipedii :

W większości systemów uniksowych wszystkie procesy potoku są uruchamiane w tym samym czasie [moje podkreślenie], z ich strumieniami odpowiednio połączonymi i zarządzanymi przez program planujący wraz ze wszystkimi innymi procesami uruchomionymi na komputerze. Ważnym aspektem tego, odróżniającym potoki uniksowe od innych implementacji potoków, jest koncepcja buforowania: na przykład program wysyłający może wytwarzać 5000 bajtów na sekundę, a program odbierający może akceptować tylko 100 bajtów na sekundę, ale nie dane zostały utracone. Zamiast tego dane wyjściowe programu wysyłającego są przechowywane w buforze. Gdy program odbierający jest gotowy do odczytu danych, następny program w potoku czyta z bufora. W systemie Linux rozmiar bufora wynosi 65536 bajtów (64 KB). Dostępny jest filtr zewnętrznego źródła o nazwie bfr, który zapewnia większe bufory w razie potrzeby.

To jeszcze bardziej mnie dezorientuje, ponieważ całkowicie przeczy celowi małych programów (choć byłyby one modułowe do pewnej skali).

Jedyne, co mogę wymyślić jako rozwiązanie mojego pierwszego pytania (ograniczenia pamięci są problematyczne w zależności od wielkości danych), to fakt, że duże zbiory danych po prostu nie były wtedy obliczane, a prawdziwym problemem, który miały rozwiązać potoki, było: ilość pamięci wymagana przez same programy. Ale biorąc pod uwagę pogrubiony tekst w cytacie z Wikipedii, nawet to mnie dezorientuje: ponieważ jeden program nie jest wdrażany na raz.

Wszystko to miałoby sens, gdyby używane były pliki tymczasowe, ale rozumiem, że potoki nie zapisują na dysku (chyba że zostanie użyta zamiana).

Przykład:

sed 'simplesubstitution' file | sort | uniq > file2

Dla mnie jasne jest, że sedczyta plik i wypluwa go wiersz po wierszu. Ale sort, jak stwierdza BK w połączonym wideo, jest to kropka, więc wszystkie dane muszą zostać wczytane do pamięci (czy tak?), A następnie są przekazywane do uniq, co (moim zdaniem) byłoby jednym -Line-at-a-time program. Ale między pierwszym i drugim potokiem wszystkie dane muszą być w pamięci, nie?

malan
źródło
1
unless swap is usedZamiana jest zawsze używana, gdy nie ma wystarczającej ilości pamięci RAM
edc65

Odpowiedzi:

44

Dane nie muszą być przechowywane w pamięci RAM. Fajki blokują pisarzy, jeśli czytelników nie ma lub nie mogą nadążyć; pod Linuksem (i większość innych implementacji, jak sądzę) jest buforowanie, ale nie jest to wymagane. Jak wspomnieli mtraceur i JdeBP (patrz odpowiedź tego ostatniego), wczesne wersje uniksowych buforowanych potoków na dysk i w ten sposób pomogły ograniczyć wykorzystanie pamięci: potok przetwarzania może zostać podzielony na małe programy, z których każdy przetwarzałby niektóre dane, w granicach buforów dyskowych. Małe programy zajmują mniej pamięci, a użycie potoków oznaczało, że przetwarzanie może zostać zserializowane: pierwszy program uruchomi się, zapełni bufor buforowy, zawiesi się, a następnie drugi program zostanie zaplanowany, przetworzy bufor itp. Nowoczesne systemy to zamówienia o wielkości większej niż wczesne systemy uniksowe i może obsługiwać wiele potoków równolegle; ale w przypadku ogromnych ilości danych nadal można zaobserwować podobny efekt (i warianty tego rodzaju techniki są używane do przetwarzania „dużych zbiorów danych”).

W twoim przykładzie

sed 'simplesubstitution' file | sort | uniq > file2

sedfilew razie potrzeby odczytuje dane , a następnie zapisuje je tak długo, jak długo sortjest gotowe do odczytu; jeśli sortnie jest gotowy, bloki zapisu. Dane rzeczywiście ostatecznie znajdują się w pamięci, ale jest to specyficzne sorti sortjest przygotowane do rozwiązania wszelkich problemów (użyje plików tymczasowych, ponieważ ilość danych do sortowania jest zbyt duża).

Możesz zobaczyć działanie blokujące, uruchamiając

strace seq 1000000 -1 1 | (sleep 120; sort -n)

To generuje sporą ilość danych i doprowadza je do procesu, który nie jest gotowy na odczytanie niczego przez pierwsze dwie minuty. Zobaczysz wiele writeoperacji, ale bardzo szybko seqsię zatrzymają i poczekają, aż upłyną dwie minuty, zablokowane przez jądro ( writewywołanie systemowe czeka).

Stephen Kitt
źródło
13
Ta odpowiedź mogłaby skorzystać z dodatkowego wyjaśnienia, dlaczego dzielenie programów na wiele małych oszczędza użycie pamięci: Program musiał być w stanie zmieścić się w pamięci, aby mógł działać, ale tylko aktualnie uruchomiony program. Każdy inny program został zamieniony na dysk na początku Uniksa, z tylko jednym programem zamienionym na rzeczywistą pamięć RAM jednocześnie. Tak więc procesor uruchomiłby jeden program, który zapisałby na potoku (który wtedy był na dysku ), zamienił ten program i zamienił na ten, który czyta z potoku. Elegancki sposób na przekształcenie logicznie równoległej linii montażowej w szeregowe wykonanie przyrostowe.
mtraceur
6
@malan: Wiele procesów może być uruchomionych i może być jednocześnie w stanie uruchomionym. Ale co najwyżej jeden proces może być wykonywany na każdym fizycznym procesorze w danym momencie, a zadaniem harmonogramu procesów jądra jest przydzielanie „segmentów” czasu procesora każdemu uruchamialnemu procesowi. We współczesnych systemach proces, który można uruchomić, ale obecnie nie jest zaplanowany, blok czasowy procesora zwykle pozostaje w pamięci podczas oczekiwania na następny wycinek, ale jądro może przesuwać pamięć dowolnego procesu na dysk i wracać do pamięci jako wydaje się wygodne. (Tu podaje się kilka szczegółów.)
Daniel Pryden,
5
Procesy po obu stronach potoku mogą zachowywać się skutecznie jak procedury wspólne: jedna strona pisze, dopóki nie zapełni bufora i bloków zapisu, w którym to momencie proces nie może nic zrobić z resztą swojego przedziału czasu i przechodzi w Tryb oczekiwania IO. Następnie system operacyjny przekazuje pozostałą część szczeliny czasowej (lub inną nadchodzącą szczelinę czasową) stronie odczytu, która czyta, dopóki w buforze nie pozostanie nic i kolejne bloki odczytu, w którym to momencie proces czytnika nie może nic zrobić z resztą jego przedział czasu i przywraca system operacyjny. Dane przechodzą przez potok wartości jednego bufora na raz.
Daniel Pryden,
6
@malan Programy są uruchamiane „w tym samym czasie” koncepcyjnie na wszystkich systemach uniksowych, tylko na nowoczesnych systemach wieloprocesorowych z wystarczającą ilością pamięci RAM do ich przechowywania, co oznacza, że ​​dosłownie wszystkie są przechowywane w pamięci RAM jednocześnie, podczas gdy na systemie, który może nie trzymaj ich wszystkich w pamięci RAM jednocześnie, niektóre zamieniają się na dyski. Zauważ też, że „pamięć” w wielu kontekstach oznacza pamięć wirtualną, która jest sumą zarówno pamięci RAM, jak i przestrzeni wymiany na dysku. Wikipedia skupia się raczej na koncepcji niż na szczegółach implementacji, szczególnie dlatego, że tak naprawdę stary Unix robił rzeczy, jest teraz mniej istotny.
mtraceur
2
@malan Również sprzeczność, którą widzisz, pochodzi z dwóch różnych znaczeń „pamięci” (RAM vs RAM + swap). Mówiłem tylko o sprzętowej pamięci RAM i w tym kontekście tylko kod aktualnie wykonywany przez procesor musi zmieścić się w pamięci RAM (co miało wpływ na decyzje, o których mówi Kernighan), podczas gdy w kontekście wszystkich programów wykonywanych logicznie przez system operacyjny w danym momencie (na poziomie abstrakcyjnym dostarczonym poza podziałami czasowymi) program musi po prostu zmieścić się w całej pamięci wirtualnej dostępnej dla systemu operacyjnego, która obejmuje przestrzeń wymiany na dysku.
mtraceur
34

Ale nie rozumiem, w jaki sposób mogłoby to ograniczyć zużycie pamięci, biorąc pod uwagę fakt, że dane muszą być przechowywane w pamięci RAM, aby przesyłać je między programami.

To jest twój podstawowy błąd. Wczesne wersje Uniksa nie zawierały danych potoku w pamięci RAM. Przechowali je na dysku. Rury miały i-węzły; na urządzeniu dyskowym oznaczonym jako urządzenie rurkowe . Administrator systemu uruchomił program o nazwie, /etc/configaby określić (między innymi), który wolumin, na którym dysku jest urządzenie potokowe, który wolumin jest urządzeniem głównym , a które zrzutem .

Ilość oczekujących danych była ograniczona faktem, że do przechowywania wykorzystano tylko bezpośrednie bloki i-węzła na dysku. Ten mechanizm uprościł kod, ponieważ do odczytu z potoku wykorzystano ten sam algorytm, co do odczytu zwykłego pliku, z pewnymi poprawkami spowodowanymi tym, że potoki nie są widoczne, a bufor jest okrągły.

Mechanizm ten został zastąpiony przez inne w połowie lat 80. XX wieku. SCO XENIX zyskał „High Performance Pipe System”, który zastąpił i-węzły wewnętrznymi buforami. 4BSD przekształciło nienazwane rury w pary gniazd. Rury AT&T ponownie wdrożone przy użyciu mechanizmu STREAMS.

I oczywiście sortprogram wykonał ograniczoną wewnętrzną porcję danych wejściowych o wielkości 32 kB (lub mniejszą ilość pamięci, którą mógłby przydzielić, gdyby 32 kiB nie był dostępny), zapisując posortowane wyniki do stmX??plików pośrednich , w /usr/tmp/których następnie scalono zewnętrznie posortowane w celu uzyskania ostatecznego wydajność.

Dalsza lektura

  • Steve D. Pate (1996). „Komunikacja międzyprocesowa”. UNIX Internals: praktyczne podejście . Addison-Wesley. ISBN 9780201877212.
  • Maurice J. Bach (1987). „System wzywa do systemu plików”. Projekt systemu operacyjnego Unix . Prentice-Hall. ISBN 0132017571.
  • Steven V. Earhart (1986). „ config(1M)”. Podręcznik programisty systemu Unix: 3. Funkcje administracji systemu . Holt, Rinehart i Winston. ISBN 0030093139. str. 23–28.
JdeBP
źródło
1

Masz częściowo rację, ale tylko przypadkowo .

W twoim przykładzie wszystkie dane musiały rzeczywiście zostać odczytane „pomiędzy” potokami, ale nie muszą znajdować się w pamięci (w tym w pamięci wirtualnej). Zwykłe implementacje sortmogą sortować zestawy danych, które nie mieszczą się w pamięci RAM, wykonując częściowe sortowanie do plików tymczasowych i łącząc je. Jednak faktem jest, że nie można wyprowadzić posortowanej sekwencji przed przeczytaniem każdego elementu. To całkiem oczywiste. Tak, tak, sortmożna rozpocząć wysyłanie danych do drugiego potoku dopiero po przeczytaniu (i zrobieniu czegokolwiek, być może częściowego sortowania plików tymczasowych) wszystkiego od pierwszego. Ale to nie koniecznie trzeba utrzymać to wszystko w pamięci RAM.

Nie ma to jednak nic wspólnego z działaniem rur. Rury można nazwać (tradycyjnie wszystkie były nazywane), co oznacza nic więcej i nic innego, jak to, że mają lokalizację w systemie plików, podobnie jak pliki. I właśnie takie rury były kiedyś, pliki (z zapisami zlewały się na tyle, na ile pozwalała na to dostępność pamięci fizycznej, jako optymalizacja).

Obecnie potoki są małym, skończonym buforem jądra, do którego kopiowane są dane, przynajmniej tak dzieje się koncepcyjnie . Jeśli jądro może temu pomóc, kopie są pomijane poprzez odtwarzanie sztuczek VM (na przykład, pipingowanie z pliku zwykle powoduje, że ta sama strona jest dostępna dla drugiego procesu do odczytania, więc w końcu jest to tylko operacja odczytu, a nie dwie kopie i nie potrzebna jest dodatkowa pamięć, która jest już używana przez pamięć podręczną bufora. W niektórych sytuacjach możesz również uzyskać 100% zerowej kopii lub coś bardzo bliskiego.

Jeśli rury są małe i mają skończony rozmiar, to jak może to działać w przypadku dowolnej nieznanej (prawdopodobnie dużej) ilości danych? To proste: gdy nic więcej nie pasuje, zapis blokuje się, dopóki nie będzie miejsca.

Filozofia wielu prostych programów była kiedyś bardzo przydatna, kiedy pamięć była bardzo ograniczona. Ponieważ, no cóż, możesz wykonywać pracę małymi krokami, pojedynczo. Obecnie zalety, oprócz pewnej dodatkowej elastyczności, nie są już takie wspaniałe.
Jednak rury są wdrażane bardzo wydajnie (musiały być!), Więc nie ma też wady, i jest to ustalona rzecz, która działa dobrze i do której ludzie są przyzwyczajeni, więc nie trzeba zmieniać paradygmatu.

Damon
źródło
Kiedy mówisz, że „potoki zostały nazwane” (wydaje się, że JdeBP mówi, że było jedno „urządzenie potokowe ”), czy to oznacza, że ​​istniało ograniczenie liczby potoków, które mogą być użyte w danym momencie (tj. Istniała granica ile razy możesz użyć |w poleceniu)?
malan
2
Nigdy nie widziałem takiego limitu i nie sądzę, aby w teorii był taki limit . W praktyce wszystko, co ma nazwę pliku, wymaga i-węzła, a liczba i-węzłów jest oczywiście skończona. Podobnie jak liczba fizycznych stron w systemie, jeśli nic więcej. Nowoczesne systemy gwarantują zapisy atomowe 4k, więc każda rura musi posiadać przynajmniej jedną kompletną stronę 4k, co nakłada ostry limit na liczbę potoków, które możesz mieć. Ale rozważ posiadanie kilku gigabajtów pamięci RAM ... praktycznie to limit, którego nigdy nie spotkasz. Spróbuj wpisać kilka milionów rur na terminalu ... :)
Damon