Brawa dla pomysłodawcy

Nie wiem komu dokładnie mam dziękować, (no, Weroniczce naszej wydziałowej :)) ale stworzenie tej strony to był fantastyczny pomysł. Pomysł zajebisty a wyniesione stąd informacje na pewno przydały mi się na egzaminie. Jednym słowem - dzięki! /to forum bedzie nam sluzyc jeszcze przez dlugie lata(lato) :P/

Egzamin


Egzamin trwa 4 godziny. Z tego co pamiętam 1h na teorię, 3h na zadania
Można zdobyć 30 punktów. Czyli łącznie z kolokwium można mieć 50 punktów.
Próg ma być nie mniejszy niż 25 / 50. Jeśli ktoś otrzyma przynajmniej 30 punktów, to ma gwarantowane zaliczenie.
Czy to sa oficjalne informacje?
Słyszałem coś takiego na wykładzie.


Progi z zeszłego roku (wg. USOSWeb):
minimalna liczba punktów na ocenę 3:
31
minimalna liczba punktów na ocenę 3,5:
35
minimalna liczba punktów na ocenę 4:
39
minimalna liczba punktów na ocenę 4,5:
43
minimalna liczba punktów na ocenę 5:
47
Dosyć wysokie - chyba Wam dobrze poszło kolokwium ;).
Jeśli dobre słuchy mnie doszły to tam była średnia z 5 pkt wyższa na kolosie.

II termin (choć to teraz nie powinno nikogo interesować:) ):
minimalna liczba punktów na ocenę 3:
18
minimalna liczba punktów na ocenę 3,5:
21
minimalna liczba punktów na ocenę 4:
23
minimalna liczba punktów na ocenę 4,5:
26
minimalna liczba punktów na ocenę 5:
28

Mozna miec notatki?
  • Na części testowej nie, na zadaniach tak.

  • Egzamin będzie polegać na odpowiedzi na dwa pytania teoretyczne (wiadomości z wykładu). W tej części nie można będzie korzystać z notatek. Następnie trzeba będzie rozwiązać dwa zadania programistyczne. Korzystania z notatek będzie w tej części dozwolone.


Jaki jest pożytek z notatek na części z zadaniami?
  • To że jak będzie kolejny raz czytelnicy i pisarze, to będziesz miał je napisane ;)

Ej, te zadania mają być z monitorów i semaforów, a z Ady i CSP już nie?
  • Ada, CSP, Linda mogą pojawić się tylko w części teoretycznej.

Pytania


Co było na ostatnim wykładzie?
na ostatnim wykladzie byl algorytm krola.

Czy ktoś wie gdzie można poczytać o algorytmie uzgadniania - algorytmie "Króla"?
Kojarzy mi sie jeden z wykladow na stronie engela, ten jedyny, ktory jest linkiem do strony,.bodaj 11 lub 12:
Synchronizacja systemów rozproszonych
Alg_krola

Czy to jest to samo co algorytm elekcji Tyrana (bully algorithm)? Jeśli tak, to właśnie to co powyżej. Jeśli nie, to może ktoś go opisze w ramach pytania 15.
Jeśli dobrze pamiętam istnieje algorytm króla!= algorytmowi tyrana, algorytm króla służył do rozwiązywania problemu bizantyjskiego bodajże. Dodaję go jako 15-te pytanie.
  • Mógłby ktoś (proszę :) ) opisać również ten algorytm tyrana? Opis ze strony anioła nie dość, że jest trochę niejasny, to jeszcze niezbyt współgra z wklejonym obok rysunkiem...
  • * Wróć, chyba już skumałem: Czy to po prostu jest tak, że ANSWER z treści opisu to to samo, co OK na rysunku?

Był jeszcze taki fajny drzewiasty algorytm wzajemnego wykluczania - pamięta go ktoś może / wrzuci linka lub opis?
http://www.mimuw.edu.pl/~mengel/PW/Projekty/aws.html?

To chyba już jako ciekawostka, prawda?

OMIC - z czym to się je?

Materiały zewnętrzne


Zadania programistyczne


Egzamin 2007
Egzamin II 2007
Egzamin II 2006
Egzamin II 2003
Egzamin II 2001

Dodaj swoje rozwiązanie i / lub zadania z egzaminu tak, żeby inni mogli je rozwiązywać i o nich dyskutować!

Zadania z teorii


HINT: Są semafory AGERWALI i algorytm synchronizacji AGRAWALI. To dwaj różni goście :)

  1. Omów semafory Agerwali. Opisz sposób ich wykorzystania do rozwiązania problemu priorytetowego dostępu do zasobów.
  2. Przedstaw rozproszony algorytm synchronizacji Agrawali. W którym miejscu dochodzi do synchronizacji zegarów? Podaj przykład świadczący o tym, ze jest to niezbędne.
  3. Podaj przykład świadczący o tym, że algorytm OMIC (uogólnienie bizantyjskich generałów) nie zadziała poprawnie dla n=6, m=2.
  4. Wymień w punktach najważniejsze różnice między semaforami a zmiennymi warunkowymi w monitorach.
  5. Kiedy problem współbieżny jest poprawny? Zilustruj niezbędne pojęcia na przykładzie czytelników i pisarzy.
  6. Sformułuj problem uzgadniania wartości przechowywanych przez n procesów (uogólniona wersja bizantyjskich generałów). Podaj oba warunki poprawności algorytmu uzgadniania oraz warunek rozwiązalności. Pokaż, że dla n=7 i m=2 dwie rundy algorytmu OMIC są niewystarczajace.
  7. Co to są numeratory i liczniki zdarzeń? Podaj rozwiązanie problemu wzajemnego wykluczania za pomocą liczników zdarzeń i numeratorów.
  8. Na czym polega synchronizacja za pomocą monitorów? Jakie są operacje na zmiennych warunkowych i jak działają?
  9. Na przykładzie problemu pięciu filozofów wyjaśnij na czym polega własność zapewniania i własność żywotności programów współbieżnych. Podaj przykład takiego rozwiązania problemu pięciu filozofów, które narusza jedną własność i takiego, które narusza drugą.
  10. Omów metodę kontroli współbieżności transakcji korzystającą ze stempli czasowych. Podaj konkretne przykłady.
  11. Porównaj mechanizm komunikacji w CSP i Adzie.
  12. CTL
  13. Zapisz algorytm Petersena wzajemnego wykluczania dla dwóch procesów
  14. Zapisz algorytm wzajemnego wykluczania dla 100 procesów w każdej z następujących notacji:CSP, Ada, semafory binarne i monitory. Co oznacza w tym przypadku bezpieczeństwo, a co żywotność?
  15. Czy ktoś ma zapisane jak wygląda algorytm króla(dla problemu bizantyjskiego, nie alg tyrana( :) ), chyba że to jest jednak to samo