[Sistemi Operativi] Esercizio trasferimento atomico

[JoKeRxbLaCk93]

Ciao a tutti, sto studiando per l'esame di sistemi operativi e consultando i vecchi appelli non saprei come risolvere un esercizio relativo al trasferimento atomico. Potete darmi qualche delucidazione a riguardo?
Il testo dell'esercizio è il seguente:
***
Si consideri la seguente procedura di trasferimento atomico che rimuove un elemento da una coda e l’aggiunge ad un’altra. Il trasferimento deve apparire come atomico, cioe’ non ci deve essere un intervallo di tempo in cui un processo esterno possa determinare che un elemento e’ stato rimosso da una coda ma non ancora aggiunto a un’altra. La realizzazione deve essere concorrente, cioe’ deve permettere trasferimenti tra code multipli in parallelo.

void AtomicTransfer (Queue *queue1, *queue2) {
__Item thing; /* oggetto in trasferimento */
__queue1->lock.Acquire();
__thing = queue1->Dequeue();
__if (thing != NULL) {
____queue2->lock.Acquire();
____queue2->Enqueue(thing);
____queue2->lock.Release();
__}
__queue1->lock.Release();
}

Si argomenti se la procedura (i) funziona sempre, oppure (ii) non funziona mai, oppure (iii) talvolta funziona talvolta no. Per i casi (ii) o (iii) si proponga una soluzione.
***

Potete aiutarmi o darmi degli indizi sul come risolvere l'esercizio?

[Albesa81]

Tu come imposteresti il ragionamento?

[JoKeRxbLaCk93]

"Albesa81":Tu come imposteresti il ragionamento?

Il fatto è che a me sembra che funzioni sempre, in quanto:
- thing prende l'elemento in queue1
- se thing ha effettivamente l'elemento avviene il trasferimento in queue2

Dov'è l'errore?

[Albesa81]

"JoKeRxbLaCk":Il fatto è che a me sembra che funzioni sempre, in quanto:
- thing prende l'elemento in queue1
- se thing ha effettivamente l'elemento avviene il trasferimento in queue2

Dov'è l'errore?

Stai considerando il caso in cui un solo processo deve accedere a quelle due code, rileggi il testo del problema.

[JoKeRxbLaCk93]

"Albesa81":[quote="JoKeRxbLaCk"]Il fatto è che a me sembra che funzioni sempre, in quanto:
- thing prende l'elemento in queue1
- se thing ha effettivamente l'elemento avviene il trasferimento in queue2

Dov'è l'errore?

Stai considerando il caso in cui un solo processo deve accedere a quelle due code, rileggi il testo del problema.[/quote]

Ok, quindi vuol dire che le istruzioni di lock su entrambe le code devono avvenire sempre allo stesso istante?

void AtomicTransfer (Queue *queue1, *queue2) {
__Item thing; /* oggetto in trasferimento */
__queue1->lock.Acquire();
__queue2->lock.Acquire();
__thing = queue1->Dequeue();
__if (thing != NULL) {
____queue2->Enqueue(thing);
__}
__queue1->lock.Release();
__queue2->lock.Release();
}

Potrebbe essere corretto?

[Albesa81]

Devi considerare che un processo esterno può dover accedere alle due code in qualunque momento, ciò che non deve mai avvenire perchè due (o più) processi possano lavorare in parallelo sulle code è che a un cambio di contesto il processo che viene eseguito veda q1 svuotata e q2 non ancora riempita. Prima di tutto pensa ai possibili scenari ragionando sul codice che ti viene proposto.

[apatriarca]

Considera il caso in cui più o meno nello stesso tempo vengono chiamate AtomicTransfer(q1, q2) e AtomicTransfer(q2, q1). Che cosa succede in questo caso?

[JoKeRxbLaCk93]

"apatriarca":Considera il caso in cui più o meno nello stesso tempo vengono chiamate AtomicTransfer(q1, q2) e AtomicTransfer(q2, q1). Che cosa succede in questo caso?

Se vengono chiamati più o meno nello stesso tempo sì avrà che il primo processo che effettua la lock su queue1 blocca il secondo processo che non può effettuare la lock su queue1 in quanto già stata effettuata dal primo processo chiamato in ordine di tempo. Corretto?

Oppure considerando che le code siano composte in questo modo al tempo t=0:
QUEUE1(t=0): Q1A, Q1B, Q1C, ..., Q1n
QUEUE2(t=0): Q2A, Q2B, Q2C, ..., Q2n
Se venissero chiamati in questo ordine: AtomicTransfer(q1, q2) e AtomicTransfer(q2, q1) (allo stesso tempo), le code si ritroverebbero in questo stato (al tempo t=n):
QUEUE1(t=n): Q2A, Q1B, Q1C, ..., Q1n
QUEUE2(t=n): Q1A, Q2B, Q2C, ..., Q2n

Quindi se operano tutte e due le chiamate in modo simultaneo si avrebbe un errore, ma come posso ovviare? per far sì che la funzione AtomicTransfer sia eseguita da un processo alla volta?

[apatriarca]

Tuttavia il secondo processo avrà bloccato queue2 e bloccherà il primo processo quando cercherà di ottenerne l'accesso.

[JoKeRxbLaCk93]

"apatriarca":Tuttavia il secondo processo avrà bloccato queue2 e bloccherà il primo processo quando cercherà di ottenerne l'accesso.

ok, qual è l'opzione generale per non far si che questo accada?

[Albesa81]

Prova a pensare a che cosa causa il deadlock.

[vict85]

Se il mutex non è ricorsivo, potresti avere problemi se le due code sono lo stesso oggetto. La soluzione migliore penso sia controllare se sono lo stesso oggetto e in quel caso non fare nulla.

Sull'altro problema, ti lascio pensare un po'. Detto questo, è mia opinione che a livello di design del software ti dovresti chiedere se davvero vuoi che questa operazione sia atomica.

[JoKeRxbLaCk93]

"Albesa81":Prova a pensare a che cosa causa il deadlock.

il deadlock può essere causato dal fatto che un processo fa il lock su queue1 e l'altro contemporaneamente su queue2?

[Albesa81]

"JoKeRxbLaCk":il deadlock può essere causato dal fatto che un processo fa il lock su queue1 e l'altro contemporaneamente su queue2?

https://it.wikipedia.org/wiki/Deadlock
Forse è meglio che ti studi bene i fondamentali e poi, se avrai bisogno, ripassi di qua