# Zasady zaliczenia egzaminu z Programowania współbieżnego 2021 na podstawie referatu

###### tags: `PRW21` `pwit`

## Zasady

Zreferowanie wybranej publikacji z dziedziny programowania współbieżnego jest alternatywnym sposobem zaliczenia egzaminu, do którego zachęcam osoby posiadające **80** lub więcej punktów z ćwiczeń (osoby posiadające niższą liczbę punktów, ale z oceną z ćwiczeń równą 4.0 mogą negocjować --- tutaj mogę poprosić o zreferowanie konkretnego tematu).

Należy:
* wybrać jeden z poniższych artykułów lub rozdziałów
* slot czasowy 90. minut, najlepiej w dniach 14., 15., 17. lub 18. lutego (inne dni do indywidualnego ustalenia)
* zgłosić mi swój wybor mailowo (adres: [e-mail]). Przyjęcie zgłoszenia zostanie potwierdzone odpowiednim wpisem w tym dokumencie. Decyduje kolejność.

Referaty zostaną przedstawione podczas zdalnego spotkania na teamsowym kanale wykładu. Można, a nawet trzeba, posługiwać się notatkami (np. zredagowanymi w hackmd.io) i własnymi rysunkami (ręcznie, np. w paincie). Należy założyć życzliwość, ale dociekliwość egzaminującego. Spotkania są otwarte, może w nich uczestniczyć każdy

## Tematy do zreferowania

### Rozdziały z TAoMP2e

* 6. Universality of Consensus
* 15. Priority queues
* 16. Scheduling and work distribution
* 17. Data parallelism
* 20. Transactional programming

Oprócz zreferowania wybranego rozdziału należy rozwiązań 2-3 zadania dowolnie wybrane spośród w nim zamieszczonych.

### Artykuły

#### Synchronizacja w Javie
* [David F. Bacon, Ravi B. Konuru, Chet Murthy, Mauricio J. Serrano, Thin locks: featherweight synchronization for Java, in: SIGPLAN Conference on Programming Language Design and Implementation, 1998](https://ei.cs.vt.edu/~cs5314/presentations/Group3PLDI.pdf)
* [Ole Agesen, David Detlefs, Alex Garthwaite, Ross Knippel, Y.S. Ramakrishna, Derek White, An efficient meta-lock for implementing ubiquitous synchronization, ACM SIGPLAN Notices 34 (10)(1999)](https://sci-hub.se/https://dl.acm.org/doi/10.1145/320385.320402)
* ~~[Jeremy Manson, William Pugh, Sarita V. Adve, The Java memory model, in: Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’05 ](https://sci-hub.se/https://dl.acm.org/doi/10.1145/1040305.1040336)~~ **(zarezerwowany)**

#### Pozostałe
* [Maurice Herlihy, Nir Shavit, On the nature of progress, in: Proceedings of the 15th International Conference on Principles of Distributed Systems, OPODIS’11, Springer-Verlag, Berlin, Heidelberg, 2011](https://www.cs.tau.ac.il/~shanir/progress.pdf)
* [Maurice Herlihy, Nir Shavit, Moran Tzafrir, Hopscotch Hashing, in: DISC 2008: Distributed Computing](https://people.csail.mit.edu/shanir/publications/disc2008_submission_98.pdf)
* [James E. Burns, Gary L. Peterson, Constructing multi-reader atomic values from non-atomic values, in: PODC ’87: Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing,](https://sci-hub.se/https://dl.acm.org/doi/abs/10.1145/41840.41859). Alternatywna, względem pokazanej na wykładzie, konstrukcja rejestru MRSW.
* ~~[Clyde P. Kruskal, Larry Rudolph, Marc Snir, Efficient synchronization of multiprocessors with shared memory, ACM Transactions on Programming Languages and Systems 10 (4) 1988](https://courses.cs.washington.edu/courses/csep524/02au/kruskal.pdf). Artykuł ma znaczenie historyczne, wprowadza pojęcie rejestrów RMW i pokazuje ich zastosowanie we wczesnych komputerach wieloprocesorowych.~~ **(zarezerwowany)**

#### Pozostałe (trudniejsze)
* [Danny Dolev, Nir Shavit, Bounded concurrent time-stamping, SIAM Journal on Computing 26 (2) (1997)](https://groups.csail.mit.edu/tds/papers/Shavit/sicomp97.pdf). Wstępem do artykułu powinna być lektura rozdziału 2.8 TAoMP2e
* [Sibsankar Haldar, Paul Vitányi, Bounded concurrent timestamp systems using vector clocks, Journal of the ACM 49 (1) (2002)](https://homepages.cwi.nl/~paulv/papers/timestampfinal.pdf). Wstępem do artykułu powinna być lektura rozdziału 2.8 TAoMP2e

## Przydział referatów

| Imię i nazwisko | Temat | Data |
|-----------------|-------| -----|
| Dawid Dudek | The Java Memory Model | 21.02 g. 18.00 |
| Kamil Kasprzak | Efficient Synchronization on Multiprocessors with Shared Memory | ? |

volatile int y;
int x;

Wątek a:
x = 7;
y = 3;

Wątek b:
read(y);

i w naszym wykonaniu jest "y=3" jest w porządku so wcześniej niż "read(y)". Wtedy mamy:

happens-before("y=3", "read(y)") ale też happens-before("x=7", "read(y)")