Piaskownica do ewaluacji algorytmów sterowania współbieżnością dla systemów pamięci transakcyjnej¶

Wstęp: Każda implementacja pamięci transakcyjnej (TM) jest inna: często są zaimplementowane w różnych językach, mają różne interfejsy, lub nawet używają szczególnych elementów konkretnych architektur procesorów. W konsekwencji często trudno jest analizować ich działanie i je ze sobą porównywać. Z drugiej strony w dziedzinie uczenia maszynowego pokazano, że ten problem można rozwiązać przez wspólny, prosty w użyciu, ale potężny framework (Weka).

Zadanie: Zbudować framework który implementuje zestaw istniejących algorytmów sterowania współbieżnością z TM (np. 2PL, TL2, pesymistyczny algorytm Matveev’a i Shavit’a, PLE, DATM) i pozwoli badaczom na prostą implementację własnych algorytmów. Dodatkowo framework powinien dostarczać narzędzi do analizy algorytmów: wykonywanie algorytmół krok-po-kroku, wizualizacja przeplotów współbieżnie wykonywanych transakcji, oraz (prosty ale rozszrzalny) zestaw benchmarków pozwalający zbadać konkretne przykłady potencjalnie niepoprawnego wykonania.

Przydatne umiejętności: zainteresowanie programowaniem współbieżnym i/lub transakcjami bazodanowymi, j. angielski w stopniu pozwalającym na czytanie artykułów naukowych (chociaż całosć projektu może opcjonalnie być w j. angielskim).

Kompetytywna wielordzeniowa implementacja pesymistycznego systemu pamięci transakcyjnej opartej o algorytmy wersjonowania.¶

Wstęp: Algorytmy wersjonowania (BVA, SVA, RVA, OptSVA) to algorytmy (protokoły) sterowania współbieżnością których zadaniem jest utrzymanie spójności w rozproszonych systemach pamięci transakcyjnej. Tak jak inne algorytmy sterowania współbieżnością dla pamięci transakcyjnej, utrzymywanie spójności dzieje się w sposób automatyczny, usuwając potrzebę pisania przez programistę kodu synchronizującego (opartego np. na zamkach, monitorach, semaforach, barierach). Zamiast tego, programista określa gdzie zaczyna się i kończy transakcja (i ew. opisuje jej parametry) mogąc ufać, że wykonany wewnatrz transakcji kod będzie zachowywał gwarancje spójności, wykona się bez zakleszczeń itp. Algorytmy pamięci transakcyjnej zazwyczaj utrzymują spójność przez wycofywanie transakcji które powodują konflikty. Zamiast tego, w/w algorytmy wersjonowania opóźniają dostęp do obiektów współdzielonych w sposób który powoduje eliminację konfliktów.

Zadanie: Ze względu na swoje własności, do tej pory algorytmy wersjonowania były implementowane w systemach rozproszonych. Natomiast algorytmy wersjonowania mogą mieć zastosowanie także w systemach wieloprocesorowych. Zadaniem jest stworzenie wydajnej implementacji wieloprocesorowej algorytmów wersjonowania, która będzie osiągać porównywalne lub lepsze wyniki wydajnościowe (throughput) względem innych istniejących systemów pamięci transakcyjnych (RSTM, TinySTM, SwissTM, NZTM, JudoSTM) na ogólnie przyjętych benchmarkach (STAMP, EigenBench, STMBench7).

Przydatne umiejętności: programowanie współbieżne, profilowanie kodu, j. angielski w stopniu pozwalającym na czytanie artykułów naukowych (chociaż całosć projektu może opcjonalnie być w j. angielskim).

Rozszerzenie rozproszonej pamięci transakcyjnej o częściową replikację¶

Wstęp: Pamięć transakcyjna działająca w modelu control flow odwołuje się do dyskretnych zasobów znajdujących się na znanych w góry maszynach w systemie rozproszonym. W modelu control flow transakcje wykonując operacje na tych zasobach powodują, że na maszynie docelowej wykonany zostaje kod zwiazany z tą operacją. Ponieważ konkretny zasób związany jest ściśle z konkretną maszyną, oznacza to, że w wypadku awarii maszyny zasób staje się niedostępny. Ponadto, jeśli zasób jest wykorzystywany przez wiele transakcji, to staje się on wąskim gardłem systemu. Problemy te można rozwiązać przez częśćiową replikację zasobu. Natomiast jeśli owa replikacja ma cały czas spełniać założenia modelu control flow, musi ona być zaimplementowana w sposób transparentny z punktu widzenia transakcji.

Zadanie: Rozszerzyć istniejącą implementację rozproszonej pamięci transakcyjnej w modelu CF o transparentną częściową replikację: zaprojektować wydajną i poprawną warstwę replikacji dla CF TM, zaimplementować ją i przetestować pod względem wydajności i odporności na awarie.

Przydatne umiejętności: programowanie współbieżne i rozproszone, programowanie w Scali/w Javie, potencjalnie znajomość RMI lub Netty i umiejętność pracy z istniejącym kodem, niezłomność ducha w kontakcie z teorią algorytmów rozproszonych, znajomość j. angielskiego w stopniu pozwalającym na czytanie artykułów naukowych (chociaż całosć projektu może opcjonalnie być w j. angielskim).

Rozszerzenie języka Scala o model aktorów¶

Wstęp: Model aktorów to sposób modelowania obliczeń rozproszonych i współbieżnych, gdzie każdy aktor to niezależny “obiekt” działa współbieżnie do innych aktorów i komunikuje się z nimi za pomocą wiadomości. Aktorzy są mocno ograniczeni względem zwykłych obiektów: są zupełnie hermetyczne i sekwencyjne. T.j. nie mogą wewnątrz używać zmiennych ze swojego kontekstu, ani nie mogą udostępniać pól i metod na zewnątrz. Aktorzy też powinni być agnostyczni wg swojej lokalizacji - zawsze działac powinni tak samo, niezależnie od tego gdzie są uruchomieni i z kim się komunikują. Te ograniczenia dają całemu systemowi dużo dobrych cech: kompozycyjność, skalowalność, pozwalają na proste zapewnienie bezpieczeństwa (np. nie wymagają używania zamków) i odporności na awarie.

Obecnie istnieją biblioteki realizujące aktorów w Scali (Akka, Scala Actors) ale robią to używając klas/obiektów które implementują pewne traits. Pozwala to na wykroczenie poza ograniczenia modelu aktorów. To powoduje że pożyteczne cechy także znikają. Dodatkowo używanie zdalnych aktorów wymaga zazwyczaj wiedzy na jakim węźle w systemie rozproszonym aktor się znajduje. W końcu, brakuje im mechanizmów zapewniania spójności/atomowości wykonania operacji na wielu aktorach jednocześnie.

Zadanie: Rozszerzyć język Scala (w tym kompilator) o mechanizmy pozwalające:

• definiować aktorów w sposób ograniczający je do definicji teoretycznej
• uruchamiać aktorów, wysyłać komunikaty między aktorami
• lokalizować aktorów bez znajomości adresów hostów i topologii sieci

Dodatkowo: mechanism pozwalający zachować spójność wykonania wielu operacji na kilku aktorach, np słowo kluczowe które realizuje wykonanie na aktorach transakcji w algorytmie conservative rigorous two two-phase locking.

Przydatne umiejętności: programowanie współbieżne i rozproszone, programowanie w Scali, chociażby pobieżna znajomość podstaw kompilatorów: EBNF, drzewa składniowe, nieustraszoność w obliczu teorii i byte-codu, j. angielski w stopniu pozwalającym na czytanie artykułów naukowych (chociaż całosć projektu może opcjonalnie być w j. angielskim).