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.

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();
	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

1. la variabile i non è inizializzata, sum e queue non sono protette in critical sections

2. la coda value non è in una critical section, può creare errori nell'update di essa.

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

6. non si possono utilizzare suspend o resume (non si è fatto uso di semafori)

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 si 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