2009-07-22 29 views
32

W systemach wielozadaniowych niektóre nienormalne warunki uniemożliwiają postęp w wykonywaniu procesów lub wątków. Będę odnosić się do obu procesów i wątków po prostu jako "procesy". Dwa z tych warunków nazywa się dead-lock i live-lock.Co to jest głód?

Pierwsza odnosi się do procesów, które blokują się wzajemnie, uniemożliwiając w ten sposób wykonanie. Ta druga odnosi się do procesów, które uniemożliwiają sobie nawzajem postęp, ale w rzeczywistości nie blokują wykonania. Na przykład, mogą nieustannie powodować nawzajem do wycofywania transakcji, nigdy nie będąc w stanie ich ukończyć.

Kolejny warunek jest znany jako głód zasobów, w którym co najmniej jeden skończony zasób, wymagany do postępu procesów, został przez nie wyczerpany i nie może zostać przywrócony, dopóki procesy się nie zakończą. Jest to również szczególny przypadek blokady na żywo.

Chciałbym wiedzieć, czy istnieje jakakolwiek inna definicja, szczególnie akademicka, dotycząca "głodu", który nie ogranicza się do "głodu zasobów". Referencje są szczególnie mile widziane.

I nie, to nie jest praca domowa. :-)

+4

Podczas gdy jesteś na temat, powinieneś również sprawdzić Lock Convoys, są one bardzo interesujące. I nieprzyjemny. http://en.wikipedia.org/wiki/Lock_convoy –

+0

Nawet jeśli była to praca domowa, byłoby najlepiej napisane zadanie domowe, jakie kiedykolwiek widziałem na SO. –

Odpowiedz

26

Nie powiedziałbym, że głód zasobów jest szczególnym przypadkiem blokady na żywo.Zwykle:

  • W zamknięciu na żywo żaden wątek nie robi postępu, ale wykonuje dalej. (W impasie, oni nawet nie wykonują egzekucji)

  • Podczas głodzenia, niektóre wątki robią postępy i niektóre wątki nie są wykonywane.

Dobre wyjaśnienie: http://docs.oracle.com/javase/tutorial/essential/concurrency/starvelive.html. Ale rozumiem, że wybór terminologii może się różnić.

Jeśli chodzi o głodzie, definicja usłyszałem to:

Załóżmy, że jest to możliwe, aby określić nieskończoną drogę egzekucji (przeplot) zgodne z założeniami (semaforów semantyki, zachowania harmonogramu OS ...) w taki sposób, wątek T zawiesza się, czekając na jakiś zasób i nigdy go nie wznowiono, nawet jeśli było to możliwe nieskończenie wiele razy. Następnie T nazywa się głodującym.

Ale ta praktyka nie pasuje do tego. Załóżmy, że dwa wątki wykonują sekcję krytyczną w nieskończonej pętli. Twój kod synchronizacji pozwala pierwszemu wątkowi wejść do sekcji krytycznej raz na godzinę. Czy to głód? Oba wątki mogą rozwijać się, ale pierwszy wykonuje swoją pracę boleśnie powoli.

Najprostszym źródłem głodu są słabe semafory. Jeśli używasz prymitywu synchronizacji (lub tworzenia własnego), który zachowuje się podobnie, to spowoduje to głód.

Klasyczne problemy gdzie głód jest dobrze znana:

więcej szczegółów całego serca polecam książeczkę semaforów (bezpłatne): http://www.greenteapress.com/semaphores/.

Pytasz, czy każdy głód spowodowany jest oczekiwaniem na jakiś zasób. Powiedziałbym - tak.

Gwint może być zawieszony:

(1) w pewnym wywołania systemu blokowania - oczekiwanie na/objęciem MUTEX semaforów zmiennej warunkowego; write(), poll() itp.

(2) w niektórych operacjach nieblokujących - takich jak wykonywanie obliczeń.

Głodzenie na (1) głoduje zasoby (muteksy, bufor itp.).

Głód na (2) jest głodny na procesorze - można go traktować jako zasób. Jeśli tak się stanie, problem dotyczy programu planującego.

HTH

+0

twoje pierwsze łącze jest martwe. Czy możesz to zaktualizować? –

+1

@ nubhihi219 - Zrobione – sdcvvc

1

Praca to także rodzaj zasobu. Kiedy dystrybucja pracy w konfiguracji producent-konsument nie jest sprawiedliwa (lub idealna), niektóre wątki mogą nie mieć wystarczającej ilości elementów roboczych, aby cały czas były zajęte.

38

Wyobraź sobie, że jesteś w kolejce, aby kupić jedzenie w restauracji, dla której kobiety w ciąży mają pierwszeństwo. I ciągle przychodzi cały grono ciężarnych kobiet.

Wkrótce będziesz głodował. ;)

Teraz wyobraź sobie, że jesteś procesem o niskim priorytecie, a kobiety w ciąży są ważniejsze. =)

+0

śmieszne, ale najlepsze wytłumaczenie – user8027365

12

Zwykle pojawia się zagadnienie, w którym zwykle pojawia się głód lub "nieokreślone blokowanie", gdy mowa o algorytmie planowania priorytetów. Algorytm planowania priorytetów ma możliwość pozostawienia procesu o niskim priorytecie bezterminowo. Stały strumień procesów o wyższym priorytecie może uniemożliwić uruchomienie procesu o niskim priorytecie.

W przypadku harmonogramów priorytetowych rozwiązanie jest "starzejące się". Starzenie się jest techniką stopniowego zwiększania priorytetu procesów, które czekają w systemie przez długi czas.

6

Głód jest po prostu procesem lub usługą, które nie są świadczone, nawet jeśli nie ma zakleszczenia w systemie.

Oto przykład, który właśnie wymyśliłem dla celów wyjaśnienia.

Wyobraź sobie algorytm kontrolujący dostęp komputerów do sieci WAN lub coś w tym stylu. Algorytm ten może mieć regułę, która mówi "Zapewnij priorytetowy dostęp do tych komputerów, które będą zużywać mniej przepustowości.", Które będą wyglądały jak właściwa polityka, ale co się stanie, gdy pojedynczy komputer będzie chciał uzyskać dostęp do sieci w celu przesłania FTP, wysłać gdzieś GB. Dzięki tym zasadom ten komputer będzie głodować, ponieważ algorytm nigdy nie wybierze tego komputera, ponieważ zawsze będą inne komputery żądające mniejszego wykorzystania przepustowości.

To się nazywa głód.

1

Złóż przykład blokady głodu w języku Java.Wszystko zależy od priorytetu wątku. Nie jestem pewien, czy ten przykład jest dobry, ale możesz mieć wygląd here.

0

Proces nie otrzymuje zasobu ani zasobów przez dłuższy czas. To nie jest impas, ponieważ jeden proces działa bez problemu. Starzenia można użyć do rozwiązania tego problemu, dla każdego żądania jest używany współczynnik starzenia.