20220906c2
In questa pagina sono presenti alcune soluzioni (possibilmente con errore) per l'esercizio C2 dell'esame 2022/09/06. Il lettore è invitato a immedesimare il professore al momento della correzione durante la lettura delle soluzioni.
Consegna
Usando i semafori implementare un servizio che preveda due funzioni:
void sumstop(int v) int sumgo(void)
La funzione sumstop deve mettere il processo chiamante in attesa. La funzione sumgo deve sbloccare tutti i processi messi in attesa con la sumstop e restituire la somma algebrica dei valori passati come parametro alla sumstop dai processi che sono stati sbloccati (zero se la sumgo viene richiamata quando non c'è nessun processo bloccato).
1
semaphore sem(1); int sum=0; queue q; void sumstop(int v): if i < 0: q.enqueue(v) sem.P() else i-- int sumgo(void): for each elem in q: int val=q.dequeue() sum=sum + val return sum
2
queue values; semaphore s(0); int sum=0; void sumstop(int v): s.P() values.enqueue(v) int sumgo(void): while !value.isEmpty(): s.V() mutex.P() sum=sum+values.dequeue() mutex.v() return sum
3
shared int sum=0; semaphore wait(0); semaphore mutex(1); void sumstop(int v): mutex.P(); sum = sum + v; mutex.V(); wait.P(); int sumgo(void): wait.V(); somma = sum; mutex.P() sum = 0 mutex.V() return somma;
4
queue<int> processlist; semaphore mutex(1); semaphore s(0); void sumstop(int v): mutex.P(); processlist.enqueue(v); mutex.P(); // V non P S.P(); int sumgo(void): int sum = 0; mutex.P(); while processlist.top() != NULL: sum += processlist.dequeue(); S.V(); mutex.V() return sum;
5
int counter = 0; int sum = 0; semaphore mutex(1); semaphore blocked(0); void sumstop(int v): mutex.P(); sum+=v; counter++; mutex.V(); blocked.P(); int sumgo(void): mutex.P(); intret = sum; sum = 0; for (int i=0; i<counter; i++) blocked.V() counter = 0; mutex.V() return intret
6
int sum = 0; mutex = new semaphore(1); queue q; void sumstop(int v): mutex.P(); sum += v; sintpid = getpid(); suspend(pid); mutex.V(); int sumgo(void): mutex.P(); while !q.empty(): resume(q.dequeue()) int value = sum; sum = 0; return value;
7
int nP, nV = -1, 0; int somma = 0 int val[] semaphore mutex(1); semaphore s(0); void sumstop(int v): mutex.P() val[nP++].add[v] s.P() np-- v[0].delete int sumgo(void): mutex.P(); nV++ if nP > 0: s.V() for (int i=0; i<nV; i++) somma += val[i] nv-- else mutex.V() return somma
8
struct blocked {
semaphore sem(0);
int value = 0;
};
semaphore mutex(1);
list<blocked> procs = new list<blocked>();
void sumstop(int v):
mutex.P()
blocked bl = new blocked();
bl.value = v
procs.add(bl)
bl.sem.P()
mutex.V()
int sumgo(void):
mutex.P();
int count = 0;
foreach proc in procs:
count += proc.value
procs.remove(proc)
proc.sem.V()
mutex.V()
return count;
9
semaphore s[] new sem(0) semaphore s1 new sem(0) int tot, waiting = 0; void sumstop(int v): waiting++ s[waiting - 1].P() waiting-- tot = tot + v if waiting == 0: s1.V() int sumgo(void): if waiting = 0: return 0 for (i = waiting -1; i == 0; i--) s[i].V() s1.P() // per aspettare che tutti abbiano fatto la somma return tot
10
int nw = 0 int currsum = 0 semaphore mutex(1) semaphore wait2go(0) void sumstop(int v): mutex.P() currsum += v; nw++; mutex.V() wait2go.P() if --nw > 0: wait2go.V() else mutex.V() int sumgo(void): mutex.P(); if nw == 0: mutex.V() return 0; int sum = cursum; cursum = 0; wait2go.V(); return sum
11
semaphore mutex(1);
semaphore semwait(0);
int sum=0;
int wait=0;
void sumstop(int v):
mutex.P()
wait++
sum += v;
mutex.V()
semwait.P()
mutex.P()
wait--;
mutex.V()
if wait > 0:
semwait.V()
int sumgo(void):
if wait == 0:
return 0
semwait.V();
while (wait > 0) {}
int val = sum
mutex.P()
sum = 0;
mutex.V()
return val;
12
semaphore mutex(0) volatile int counter = 0 void sumstop(int v): counter = counter + v; mutex.P() int sumgo(void): int val = counter; while (mutex.value != 0) mutex.V() counter = 0; return counter
13
semaphore mutex(1) int sum = 0; queue of semaphore q; void sumstop(int v): mutex.P() sum += v; s = new semaphore(0); q.enqueue(s) mutex.V() s.P() free(s) int sumgo(void): mutex.P() int lsum = sum sum = 0 while (!q.empty()): semaphore s = q.dequeue() s.V() mutex.V()
14
semaphore mutex(1) int sum = 0; queue of semaphore q; void sumstop(int v): mutex.P() sum += v; s = new semaphore(0); q.enqueue(s) mutex.V() s.P() free(s) if(q.empty()) mutex.V() else semaphore s = q.dequeue() s.V() int sumgo(void): mutex.P() int lsum = sum sum = 0 if(q.empty()) mutex.V() else semaphore s = q.dequeue() s.V()
15 (soluzione proposta su telegram)
#include <pthread.h>
#include "semaphore.h"
semaphore s; // semaforo che blocca le somme
semaphore finished; // semaforo che indica che le somme sono state fatte
semaphore critical_section; // sarà utilizzata per decidere chi entra nella critical section
volatile int sumstops = 0;
volatile int result;
void *sumstop(int v) {
semaphore_P(critical_section);
sumstops++;
semaphore_V(critical_section);
semaphore_P(s);
printf("summed %d\n", v);
result += v;
semaphore_V(finished);
}
int sumgo(void) {
semaphore_P(critical_section); // così sumstops è costante all'interno di questa section
result = 0;
for (int i = 0; i < sumstops; i++) {
semaphore_V(s); // permetti alla somma di andare
semaphore_P(finished); // aspetta che la somma sia finita prima di continuare
}
sumstops = 0; // reset number of blocked stops.
semaphore_V(critical_section);
return result;
}
void *run_sumgo(void) {
int res = sumgo();
printf("the result found is %d\n", res);
printf("the result found is %d\n", result);
}
int main() {
srand(time(NULL));
s = semaphore_create(0);
critical_section = semaphore_create(1);
finished = semaphore_create(0);
int n = rand() % 50;
pthread_t sumg, s[n];
for (int i = 0; i < n; i++) {
pthread_create(&s[i], NULL, sumstop, i);
}
pthread_create(&sumg, NULL, run_sumgo, NULL);
for (int i = 0; i < 10; i++) {
pthread_join(s[i], NULL);
}
pthread_join(sumg, NULL);
}
Correzioni proposte
Correzione proposta da flecart (e poi modificata successivamente da altri studenti ... tra cui: LLibera )
1. la variabile i non è inizializzata, sum e queue non sono protette in critical sections, inoltre la sem.V() non compare mai nel codice della sumgo.
2. la coda value non è in una critical section, può creare errori nell'update di essa, solo sum viene considerata da proteggere, ma devono essere protette entrambe. La enqueue avrebbe senso farla solo prima di bloccarsi nel semaforo, se viene fatta dopo al momento della chiamata di sumgo non ci sono valori all'interno della coda!
3. sumgo libera solamente un singolo sumstop, perché chiama wait.V() una singola volta anche se ci sono più thread in attesa
4. mutex.P() è chiamata due volte in sumstop(), se il secondo fosse mutex.V() credo sia corretto.
5. mi sembra corretto (ma l'indentazione è poco sensata).
6. non si possono utilizzare suspend o resume (non si è fatto uso di semafori, e l'implementazione deve essere fatta all'esterno del kernel non all'interno). Oltre a questo pid non è inizializzata e sintpid non è utilizzata. Se anche la suspend fosse una sem.P() e la resume una sem.V() non dovremmo sospendere il processo all'interno della mutua esclusione.
7. nP e nV mi sembrano superflue, in questo caso sicuramente scorrette perché se chiamo m volte sumstop e una volta sumgo, nV è al massimo 1 quindi è impossibile che riesca a contare correttamente tutte le somme.
8. Deadlock perché bl.sem.P() è chiamato prima che ls Critical Section venga rilasciata e sumgo ha bisogno di entrare in una CS.
9. waiting è una variabile globale modificata senza cs, e tot non è inizializzato.
10. simile a 3. wait2go è chiamata una volta quindi può liberare solamente un singolo thread di sumstop.
11. busy waiting in sumgo.
12. counter non è protetto da Critical section
13. se sumgo ritornasse il valore lsum sarebbe tutto apposto.
14. mi sembra corretto
15. mi sembra corretto