Czy istnieje sposób, aby ten problem mógł skorzystać z rozwiązania z wieloma wątkami, a nie z jednym wątkiem?
W wywiadzie poproszono mnie o rozwiązanie problemu przy użyciu wielu wątków. Wydaje mi się, że wiele wątków nie przynosi żadnych korzyści.
Oto problem:
Otrzymujesz akapit, który zawiera n liczbę słów, otrzymujesz m wątków. Co musisz zrobić, każdy wątek powinien wydrukować jedno słowo i dać kontrolę nad następnym wątkiem, w ten sposób każdy wątek będzie drukował jedno słowo, w przypadku, gdy nadejdzie ostatni wątek, powinien wywołać pierwszy wątek. Drukowanie będzie powtarzane, aż wszystkie słowa zostaną wydrukowane w akapicie. Wreszcie wszystkie wątki powinny wyjść z gracją. Jakiego rodzaju synchronizacji użyjesz?
Mocno czuję, że nie możemy tutaj wykorzystać nici, ale wierzę, że osoba przeprowadzająca wywiad próbuje zmierzyć moje umiejętności synchronizacji. Czy w tym problemie brakuje czegoś, co sprawiłoby, że wiele wątków miałoby wartość?
Nie potrzebujesz kodu, po prostu zastanów się. Zrealizuję sam.
źródło
Odpowiedzi:
Wydaje mi się, że prowadzą cię do rozwiązania semaforów. Semafory służą do sygnalizowania kolejnemu wątkowi, że jest ich kolej. Są one używane znacznie rzadziej niż muteksy, i myślę, że dlatego uważają, że to dobre pytanie do rozmowy kwalifikacyjnej. Właśnie dlatego przykład wydaje się wymyślony.
Zasadniczo
m
tworzyłbyś semafory. Każdy wątekx
czeka na semafor,x
a następniex+1
wykonuje posty na semaforze po wykonaniu swojej czynności. W pseudokodzie:źródło
Moim zdaniem jest to wspaniałe pytanie na rozmowę kwalifikacyjną - przynajmniej przy założeniu, że (1) kandydat ma głęboką wiedzę na temat wątków, oraz (2) osoba przeprowadzająca wywiad ma również głęboką wiedzę i używa pytania do zbadania kandydata. Zawsze możliwe jest, że ankieter szukał konkretnej, wąskiej odpowiedzi, ale kompetentny ankieter powinien szukać:
Ten ostatni punkt jest moim zdaniem najważniejszy. Ponownie, w oparciu o moje doświadczenie, debugowanie kodu wątkowego staje się wykładniczo trudniejsze, jeśli wątki są mieszane z logiką aplikacji (wystarczy spojrzeć na wszystkie pytania Swing dotyczące SO). Uważam, że najlepszy kod wielowątkowy jest pisany jako samodzielny kod jednowątkowy, z wyraźnie określonymi przełączeniami.
Mając to na uwadze, moim podejściem byłoby nadanie każdemu wątkowi dwóch kolejek: jednej dla danych wejściowych, drugiej dla danych wyjściowych. Wątek blokuje się podczas odczytywania kolejki wejściowej, usuwa pierwsze słowo z ciągu i przekazuje pozostałą część ciągu do swojej kolejki wyjściowej. Niektóre funkcje tego podejścia:
Mimo to kompetentny ankieter może nadal badać wiele szarych obszarów:
Wreszcie, jeśli masz doświadczenie w programowaniu współbieżnym, możesz porozmawiać o niektórych frameworkach (np. Akka for Java / Scala), które już stosują ten model.
źródło
Pytania do wywiadu są czasami podstępnymi pytaniami, mającymi na celu skłonienie Cię do zastanowienia się nad problemem, który próbujesz rozwiązać. Zadawanie pytań dotyczących pytania jest integralną częścią podejścia do każdego problemu, czy to w prawdziwym świecie, czy w wywiadzie. W Internecie krąży wiele filmów wideo na temat tego, jak podchodzić do pytań w wywiadach technicznych (w szczególności Google i Microsoft).
Zbliżanie się do wywiadów z tym schematem myślenia doprowadzi cię do zbombardowania każdego wywiadu dla każdej firmy, w której warto pracować.
Jeśli nie uważasz, że dużo zyskujesz (jeśli cokolwiek z wątków), powiedz im to. Powiedz im, dlaczego według ciebie nie ma żadnych korzyści. Porozmawiaj z nimi. Wywiady techniczne mają być otwartą platformą do dyskusji. Możesz w końcu dowiedzieć się czegoś o tym, jak to może być przydatne. Nie posuwaj się naprzód na ślepo, próbując wdrożyć coś, o czym kazał ci twój ankieter.
źródło
Najpierw tokenizuj akapit za pomocą odpowiednich ograniczników i dodaj słowa do kolejki.
Utwórz N liczby wątków i przechowuj je w puli wątków.
Iteruj po puli wątków, uruchom wątek i poczekaj na
dołączenie wątku. I rozpocznij następny wątek, gdy pierwszy wątek się skończy i tak dalej.
Każdy wątek powinien po prostu odpytać kolejkę i wydrukować ją.
Gdy wszystkie wątki zostaną użyte w puli wątków, zacznij od początku puli.
źródło
Jak powiedziałeś, nie sądzę, aby ten scenariusz przyniósł wiele korzyści, jeśli w ogóle, dzięki wątkom. Najprawdopodobniej jest wolniejszy niż implementacja z jednym wątkiem.
Jednak moją odpowiedzią byłoby, aby każdy wątek w ciasnej pętli próbował uzyskać dostęp do blokady, która kontroluje dostęp do indeksu tablicy słów. Każdy wątek chwyta blokadę, pobiera indeks, pobiera odpowiednie słowo z tablicy, drukuje je, zwiększa indeks, a następnie zwalnia blokadę. Wątki wychodzą, gdy indeks znajduje się na końcu tablicy.
Coś takiego:
Myślę, że powinno to osiągnąć jeden wątek po drugim wymaganiu, ale kolejność wątków nie jest gwarantowana. Ciekawi mnie też inne rozwiązania.
źródło
Użyj interfejsów API warunku oczekiwania / sygnału, aby rozwiązać ten problem.
Powiedzmy, że pierwszy wątek wybiera 1 słowo, a tymczasem wszystkie wątki czekają na sygnał. Wydrukuj pierwszy wątek 1. słowo i wygeneruje sygnał do następnego wątku, a następnie wydrukuj drugi wątek drugie słowo i wygeneruje sygnał do 3. wątku i tak dalej.
źródło
[Użyte tutaj terminy mogą być specyficzne dla wątków POSIX]
Aby rozwiązać ten problem, powinno być również możliwe zastosowanie muteksu FIFO.
Gdzie używać:
Załóżmy, że dwa wątki T1 i T2 próbują wykonać sekcję krytyczną. Obaj nie mają wiele do zrobienia poza tym krytycznym punktem i trzymają zamki przez długi czas. Tak więc T1 może zablokować, wykonać i odblokować oraz zasygnalizować T2 do wybudzenia. Ale zanim T2 może się obudzić i uzyskać blokadę, T1 ponownie blokuje i wykonuje. W ten sposób T2 może czekać bardzo długo, zanim faktycznie otrzyma blokadę lub może nie być.
Jak to działa / Jak wdrożyć:
Miej muteks do zablokowania. Zainicjuj dane specyficzne dla wątku (TSD) dla każdego wątku w węźle zawierającym identyfikator wątku i semafor. Ponadto mają dwie zmienne - własność (PRAWDA lub FAŁSZ lub -1), właściciel (identyfikator wątku właściciela). Ponadto utrzymuj kolejkę kelnerów i wskaźnik kelnera Ostatni wskazujący na ostatni węzeł w kolejce kelnerów.
działanie blokady:
operacja odblokowania:
źródło
Interesujące pytanie. Oto moje rozwiązanie w Javie wykorzystujące SynchronousQueue do utworzenia kanału spotkania między wątkami:
źródło
Powiedziałbym, że na tego rodzaju pytanie bardzo trudno jest odpowiedzieć, ponieważ wymaga najlepszego sposobu zrobienia czegoś całkowicie głupiego. Mój mózg po prostu nie działa w ten sposób. Nie może znaleźć rozwiązania głupich pytań. Mój mózg od razu powiedziałby, że w tych warunkach używanie wielu wątków jest bezcelowe, więc użyłbym jednego wątku.
Następnie poprosiłbym ich, aby zadali pytanie dotyczące wątków w prawdziwym świecie lub pozwolili mi podać przykład poważnego wątku w prawdziwym świecie.
źródło