Algorytmy rozproszone - zadania

[sammel]

Bardzo proszę o pomoc z rozwiązaniem kilku przykładów. Uczę się do zaliczenia i chciał bym zrozumieć sposoby rozwiązywania.

Zad.1
Napisać algorytm aby proces p obliczał sumę a + b, a proces q obliczał różnicę a – b. Trzeba użyć semaforów.
X <- 0 ( jedyna zmienna globalna )
p1: losuj a q1: losuj b



Zad.2
Czy algorytm spełnia własności wzajemnego wykluczenia?
Czy własność żywotności jest spełniona?

chcep<-false chceq<-false

p1: SL //sekcja lokalna q1: SL
p2: ? q2: ?
p3: chcep<-true q3: chceq<-true
p4: while chceq=true q4: while chcep=true
p5: chcep<-false q5: chceq<-false
p6: chcep<-true q6: chceq<-true
p7: SK //sekcja krytyczna q7: SK
p8: chcep<-false q8: chceq<-false


Zad.3
Przedstawiony poniżej algorytm nie spełnia własności wzajemnego wykluczenia. Znaleźć odpowiedni przeplot, który naruszą tę własność. Udowodnić przedstawione rozwiązanie.


chcep<-false; chceq<-false; kto_ostatni<-1
powtarzaj
powtarzaj
p1: SL //sekcja lokalna q1: SL
p2: kto_ostatni <- 1 q2: kto_ostatni <- 2
p3: chcep<- true q3: chceq<- true
p4: czekaj_na (chceq=false lub kto_ostatni=2) q4: chekaj_na (chcep=false lub kto_ostatni=1
p5: SK //sekcja krytyczna q5: SK
p6: chcep<- false q6: chceq<-false

Wszystkie instrukcje poza :p1,q1,p5,q5 są atomowe.


Zad.4
Problem 5 filozofów. Dane jest 5 procesów które wykonują sekcję lokalną, następnie wchodzą do jadalni gdzie znajduje się 5 widelców. Proces może wykonać operację jedzenia jeżeli posiada 2 widelce. Widelec nie może być wspóldzielony z innym procesem, żaden proces nie może być pozbawiony wykonania operacji jedzenia. Mamy następujące rozwiązanie semaforowe tego problemu:


semafor widelec <-1 i=1,...,5
powtarzaj
p1: SL
p2: wait (widelec)
p3: wait (widelec[i mod 5+1])
p4: jedzenie
p5: signal (widelec[i mod 5+1])
p6: wait (widelec)

Pokazać że powyższe rozwiązanie może prowadzić do zakleszczenia (jaka własność nie będzie wtedy spełniona). Pokazać odpowiedni przeplot. Opracować poprawne rozwiązanie (wsk. do jedzenia należy dopuszczać nie więcej niż 4 procesy na raz).

Zad.5

Dane są następujące procesy.

powtarzaj
p1: SL
p2: SK.chce
p3: sekcja krytyczna
p4:SK.nie_chce

Zdefiniować monitor SK i operacje chce i nie_chce, tak by w sekcji krytycznej mogło być równocześnie co najwyżej 5 procesów.


Zad.6

Zdefiniowano atomowy rozkaz exchange (a,b)
t<-a
a<-b
b<-t
opracuj algorytm wzajemnego wykluczenia, wykorzystujący rozkaz "exchange" i udowodnij przedstawione rozwiązanie.