Read-write lock

Przypomnijmy rozwiązanie z wykładu (slajd 131):

możnaCzytać, możnaPisać: ConditionVariable
czytelnicy, pisarze: int

def chcęCzytać():
    if pisarze or !empty(możnaPisać):
        wait(możnaCzytać)
    czytelnicy++
    signal(możnaCzytać)  // Kaskadowe budzenie.

def koniecCzytania():
    czytelnicy--
    if czytelnicy == 0:
        signal(możnaPisać)

def chcęPisać():
    if czytelnicy || pisarze:
        wait(możnaPisać)
    pisanie++

def koniecPisania():
    pisanie--;
    if !empty(możnaCzytać):
        signal(możnaCzytać)
    else:
        signal(możnaPisać)

Monitory w semantyce Mesa (w pthreads i przez to w praktycznie każdym popularniejszym języku programowania) różnią się semantyką od tych z wykładu i ćwiczeń:

• nie mamy gwarancji dot. kolejności budzenia;
• występuje zjawisko spontanicznego budzenia.

Z powodu spontanicznego budzenia i wydajności, zamiast kaskadowego budzenia lepiej użyć broadcast:

możnaCzytać, możnaPisać: ConditionVariable
czytelnicy, pisarze: int

def chcęCzytać():
    if pisarze or !empty(możnaPisać):
        wait(możnaCzytać)
    czytelnicy++

def koniecCzytania():
    czytelnicy--
    if czytelnicy == 0:
        signal(możnaPisać)

def chcęPisać():
    if czytelnicy || pisarze:
        wait(możnaPisać)
    pisanie++

def koniecPisania():
    pisanie--;
    if !empty(możnaCzytać):
        broadcast(możnaCzytać)
    else:
        signal(możnaPisać)

Z powodu spontanicznego budzenia, musimy sprawdzać warunek w pętli. Nie wystarczy jednak wszystko zamienić na pętle. Niektóre warunki sprawdzaliśmy by zapewnić bezpieczeństwo, inne by ustalić priorytety i uniknąć zagłodzenia. Co złego się stanie jeśli wszystko zamienimy na pętle?:

def chcęCzytać():
    while pisarze or !empty(możnaPisać):
        wait(możnaCzytać)
    czytelnicy++

def koniecCzytania():
    czytelnicy--
    if czytelnicy == 0:
        signal(możnaPisać)

def chcęPisać():
    while czytelnicy || pisarze:
        wait(możnaPisać)
    pisanie++

def koniecPisania():
    pisanie--;
    if !empty(możnaCzytać):
        broadcast(możnaCzytać)
    else:
        signal(możnaPisać)

W sytuacji z wieloma pisarzami praktycznie zawsze ktoś czeka na pisanie, więc zagłodzilibyśmy czytelników. Jak to naprawić?

Rozwiązaniem jest sprawdzanie, czy czekają pisarze, tylko za pierwszym razem:

def chcęCzytać():
    if pisarze or !empty(możnaPisać):
        wait(możnaCzytać)
        while pisarze:
            wait(możnaCzytać)
    czytelnicy++

Czyli nie ustępujemy pisarzom, którzy przyszli po nas.

Kolejna różnica w stosunku do semantyki z wykładu, to że bo nie mamy gwarancji dot. kolejności budzenia. W szczególności jeśli mamy wątek, który w kółko pisze, to w każdej iteracji kończąc pisanie budzi czytelników, ale sam kontynuuje działanie i ma dużą szansę szybciej w następnej iteracji wejść do monitora i znów zacząć pisać. Może więc zagłodzić pozostałe wątki. W praktyce zawsze w końcu odda miejsce czytelnikom, ale może się to dziać rzadziej niż byśmy chcieli.

Można użyć ogólnego rozwiązania, żeby wymusić słabą sprawiedliwość, czyli że po signal/broadcast priorytet mają mieć wątki, które w momencie signal/broadcast czekały na zmiennej warunkowej. Polega ono na dodaniu flagi np. signalling: boolean, która będzie mówiła, że zawołaliśmy signal/broadcast i do monitora powinien teraz wejść wątek, który czekał na zmiennej warunkowej. Flagę podnosimy przy każdym wywołaniu signal/broadcast, a opuszczamy wychodząc z wait(). Wątek który wchodzi do monitora i widzi podniesioną flagę, wie że teraz to nie on powinien był wejść do monitora, tylko ktoś czekający w wait(), więc sam ustępuje robiąc wait().

Czyli piszemy np.:

while !... or signalling:
    wait()
    signalling = False

if ...:
    signalling = True
    broadcast()

Ogólnie jednak nie ma jednego najlepszego rozwiązania problemu czytelników i pisarzy, wybór zależy od wymagań dot. sprawiedliwości i zagłodzeń, wydajności, proporcji czytelników do pisarzy, typowych odstępów między odczytami i między zapisami, itd. W dzisiejszym zadaniu, postaraj się, by liczba odczytów nie różniła się od liczby zapisów więcej niż 4-krotnie.