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

16 - Soluzione di uno studente

//Variabili globali
Queue<Semaphore> processSemaphore = new Queue();
Semaphore mutex = new Semaphore(1);
Queue<int> integers = new Queue();

int SumGo() {
    
    int sum = 0;
    mutex.P();
    while(processSemaphore.isQueueVoid() == false){
        Semaphore procSem = processSemaphore.dequeue();
        procSem.V();
    }
    while(integers.isQueueVoid() == false){
        sum = sum + integers.dequeue();
    }
    mutex.V();
    return sum;
}

void SumStop(int generatedValue){
    Semaphore sem = new Semaphore(0);
    mutex.P();
    integers.enqueue(generatedValue);
    processSemaphore.enqueue(sem);
    mutex.V();
    sem.P();
    free(sem);
}

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. //dopo il commento del prof: supponiamo che sia mutex.V() allora nella sumstop dopo S.P dovremmo ancora rilasciare la mutex... ma rilasciando la mutex non riesco a finire di liberare gli altri processi quindi è meglio pensare meglio il while nella sumstop in modo da fare un passaggio del testimone che sblocchi tutti in cascata.

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, manca solo la return in sumgo

15. mi sembra corretto