sphinx.addnodesdocument)}( rawsourcechildren]( translations LanguagesNode)}(hhh](h pending_xref)}(hhh]docutils.nodesTextEnglish}parenthsba attributes}(ids]classes]names]dupnames]backrefs] refdomainstdreftypedoc reftarget/locking/lockdep-designmodnameN classnameN refexplicitutagnamehhh ubh)}(hhh]hChinese (Simplified)}hh2sbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget*/translations/zh_CN/locking/lockdep-designmodnameN classnameN refexplicituh1hhh ubh)}(hhh]hChinese (Traditional)}hhFsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget*/translations/zh_TW/locking/lockdep-designmodnameN classnameN refexplicituh1hhh ubh)}(hhh]hJapanese}hhZsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget*/translations/ja_JP/locking/lockdep-designmodnameN classnameN refexplicituh1hhh ubh)}(hhh]hKorean}hhnsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget*/translations/ko_KR/locking/lockdep-designmodnameN classnameN refexplicituh1hhh ubh)}(hhh]hSpanish}hhsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget*/translations/sp_SP/locking/lockdep-designmodnameN classnameN refexplicituh1hhh ubeh}(h]h ]h"]h$]h&]current_languageItalianuh1h hh _documenthsourceNlineNubhcomment)}(h SPDX-License-Identifier: GPL-2.0h]h SPDX-License-Identifier: GPL-2.0}hhsbah}(h]h ]h"]h$]h&] xml:spacepreserveuh1hhhhhhW/var/lib/git/docbuild/linux/Documentation/translations/it_IT/locking/lockdep-design.rsthKubhwarning)}(hIn caso di dubbi sulla correttezza del contenuto di questa traduzione, l'unico riferimento valido è la documentazione ufficiale in inglese. Per maggiori informazioni consultate le :ref:`avvertenze `.h]h paragraph)}(hIn caso di dubbi sulla correttezza del contenuto di questa traduzione, l'unico riferimento valido è la documentazione ufficiale in inglese. Per maggiori informazioni consultate le :ref:`avvertenze `.h](hIn caso di dubbi sulla correttezza del contenuto di questa traduzione, l’unico riferimento valido è la documentazione ufficiale in inglese. Per maggiori informazioni consultate le }(hhhhhNhNubh)}(h!:ref:`avvertenze `h]hinline)}(hhh]h avvertenze}(hhhhhNhNubah}(h]h ](xrefstdstd-refeh"]h$]h&]uh1hhhubah}(h]h ]h"]h$]h&]refdoc)translations/it_IT/locking/lockdep-design refdomainhՌreftyperef refexplicitrefwarn reftarget it_disclaimeruh1hh3Documentation/translations/it_IT/disclaimer-ita.rsthKhhubh.}(hhhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhhubah}(h]h ]h"]h$]h&]uh1hhhhhhhhNubhsection)}(hhh](htitle)}(h3Validatore di sincronizzazione durante l'esecuzioneh]h5Validatore di sincronizzazione durante l’esecuzione}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhhhhhKubh)}(hhh](j)}(hClassi di blocchih]hClassi di blocchi}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhK ubh)}(hAL'oggetto su cui il validatore lavora è una "classe" di blocchi.h]hGL’oggetto su cui il validatore lavora è una “classe” di blocchi.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK hjhhubh)}(hX*Una classe di blocchi è un gruppo di blocchi che seguono le stesse regole di sincronizzazione, anche quando i blocchi potrebbero avere più istanze (anche decine di migliaia). Per esempio un blocco nella struttura inode è una classe, mentre ogni inode sarà un'istanza di questa classe di blocco.h]hX,Una classe di blocchi è un gruppo di blocchi che seguono le stesse regole di sincronizzazione, anche quando i blocchi potrebbero avere più istanze (anche decine di migliaia). Per esempio un blocco nella struttura inode è una classe, mentre ogni inode sarà un’istanza di questa classe di blocco.}(hj.hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK hjhhubh)}(hXIl validatore traccia lo "stato d'uso" di una classe di blocchi e le sue dipendenze con altre classi. L'uso di un blocco indica come quel blocco viene usato rispetto al suo contesto d'interruzione, mentre le dipendenze di un blocco possono essere interpretate come il loro ordine; per esempio L1 -> L2 suggerisce che un processo cerca di acquisire L2 mentre già trattiene L1. Dal punto di vista di lockdep, i due blocchi (L1 ed L2) non sono per forza correlati: quella dipendenza indica solamente l'ordine in cui sono successe le cose. Il validatore verifica permanentemente la correttezza dell'uso dei blocchi e delle loro dipendenze, altrimenti ritornerà un errore.h]hXIl validatore traccia lo “stato d’uso” di una classe di blocchi e le sue dipendenze con altre classi. L’uso di un blocco indica come quel blocco viene usato rispetto al suo contesto d’interruzione, mentre le dipendenze di un blocco possono essere interpretate come il loro ordine; per esempio L1 -> L2 suggerisce che un processo cerca di acquisire L2 mentre già trattiene L1. Dal punto di vista di lockdep, i due blocchi (L1 ed L2) non sono per forza correlati: quella dipendenza indica solamente l’ordine in cui sono successe le cose. Il validatore verifica permanentemente la correttezza dell’uso dei blocchi e delle loro dipendenze, altrimenti ritornerà un errore.}(hj<hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(hX#Il comportamento di una classe di blocchi viene costruito dall'insieme delle sue istanze. Una classe di blocco viene registrata alla creazione della sua prima istanza, mentre tutte le successive istanze verranno mappate; dunque, il loro uso e le loro dipendenze contribuiranno a costruire quello della classe. Una classe di blocco non sparisce quando sparisce una sua istanza, ma può essere rimossa quando il suo spazio in memoria viene reclamato. Per esempio, questo succede quando si rimuove un modulo, o quando una *workqueue* viene eliminata.h](hX Il comportamento di una classe di blocchi viene costruito dall’insieme delle sue istanze. Una classe di blocco viene registrata alla creazione della sua prima istanza, mentre tutte le successive istanze verranno mappate; dunque, il loro uso e le loro dipendenze contribuiranno a costruire quello della classe. Una classe di blocco non sparisce quando sparisce una sua istanza, ma può essere rimossa quando il suo spazio in memoria viene reclamato. Per esempio, questo succede quando si rimuove un modulo, o quando una }(hjJhhhNhNubhemphasis)}(h *workqueue*h]h workqueue}(hjThhhNhNubah}(h]h ]h"]h$]h&]uh1jRhjJubh viene eliminata.}(hjJhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhjhhubeh}(h]classi-di-blocchiah ]h"]classi di blocchiah$]h&]uh1hhhhhhhhK ubh)}(hhh](j)}(hStatoh]hStato}(hjwhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjthhhhhK%ubh)}(huIl validatore traccia l'uso cronologico delle classi di blocchi e ne divide l'uso in categorie (4 USI * n STATI + 1).h]hyIl validatore traccia l’uso cronologico delle classi di blocchi e ne divide l’uso in categorie (4 USI * n STATI + 1).}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK'hjthhubh)}(hI quattro USI possono essere:h]hI quattro USI possono essere:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK*hjthhubh bullet_list)}(hhh](h list_item)}(h('sempre trattenuto nel contesto 'h]h)}(hjh]h,‘sempre trattenuto nel contesto ’}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK,hjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubj)}(h?'sempre trattenuto come blocco di lettura nel contesto 'h]h)}(hjh]hC‘sempre trattenuto come blocco di lettura nel contesto ’}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK-hjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubj)}(h)'sempre trattenuto con abilitato'h]h)}(hjh]h-‘sempre trattenuto con abilitato’}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK.hjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubj)}(hA'sempre trattenuto come blocco di lettura con abilitato' h]h)}(h@'sempre trattenuto come blocco di lettura con abilitato'h]hD‘sempre trattenuto come blocco di lettura con abilitato’}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK/hjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubeh}(h]h ]h"]h$]h&]bullet-uh1jhhhK,hjthhubh)}(hTgli `n` STATI sono codificati in kernel/locking/lockdep_states.h, ad oggi includono:h](hgli }(hj hhhNhNubhtitle_reference)}(h`n`h]hn}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhj ubhM STATI sono codificati in kernel/locking/lockdep_states.h, ad oggi includono:}(hj hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhK1hjthhubj)}(hhh](j)}(hhardirqh]h)}(hj4h]hhardirq}(hj6hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK4hj2ubah}(h]h ]h"]h$]h&]uh1jhj/hhhhhNubj)}(hsoftirq h]h)}(hsoftirqh]hsoftirq}(hjMhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK5hjIubah}(h]h ]h"]h$]h&]uh1jhj/hhhhhNubeh}(h]h ]h"]h$]h&]j j uh1jhhhK4hjthhubh)}(hinfine l'ultima categoria è:h]hinfine l’ultima categoria è:}(hjghhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK7hjthhubj)}(hhh]j)}(hK'sempre trattenuto' [ == !unused ] h]h)}(hJ'sempre trattenuto' [ == !unused ]h]hN‘sempre trattenuto’ [ == !unused ]}(hj|hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK9hjxubah}(h]h ]h"]h$]h&]uh1jhjuhhhhhNubah}(h]h ]h"]h$]h&]j j uh1jhhhK9hjthhubh)}(hQuando vengono violate le regole di sincronizzazione, questi bit di utilizzo vengono presentati nei messaggi di errore di sincronizzazione, fra parentesi graffe, per un totale di `2 * n` (`n`: bit STATO). Un esempio inventato::h](hQuando vengono violate le regole di sincronizzazione, questi bit di utilizzo vengono presentati nei messaggi di errore di sincronizzazione, fra parentesi graffe, per un totale di }(hjhhhNhNubj)}(h`2 * n`h]h2 * n}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh (}(hjhhhNhNubj)}(h`n`h]hn}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh#: bit STATO). Un esempio inventato:}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhK;hjthhubh literal_block)}(hmodprobe/2287 is trying to acquire lock: (&sio_locks[i].lock){-.-.}, at: [] mutex_lock+0x21/0x24 but task is already holding lock: (&sio_locks[i].lock){-.-.}, at: [] mutex_lock+0x21/0x24h]hmodprobe/2287 is trying to acquire lock: (&sio_locks[i].lock){-.-.}, at: [] mutex_lock+0x21/0x24 but task is already holding lock: (&sio_locks[i].lock){-.-.}, at: [] mutex_lock+0x21/0x24}hjsbah}(h]h ]h"]h$]h&]hhuh1jhhhK?hjthhubh)}(hPer un dato blocco, da sinistra verso destra, la posizione del bit indica l'uso del blocco e di un eventuale blocco di lettura, per ognuno degli `n` STATI elencati precedentemente. Il carattere mostrato per ogni bit indica:h](hPer un dato blocco, da sinistra verso destra, la posizione del bit indica l’uso del blocco e di un eventuale blocco di lettura, per ognuno degli }(hjhhhNhNubj)}(h`n`h]hn}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubhK STATI elencati precedentemente. Il carattere mostrato per ogni bit indica:}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKEhjthhubh block_quote)}(hX=== =========================================================================== '.' acquisito con interruzioni disabilitate fuori da un contesto d'interruzione '-' acquisito in contesto d'interruzione '+' acquisito con interruzioni abilitate '?' acquisito in contesto d'interruzione con interruzioni abilitate === =========================================================================== h]htable)}(hhh]htgroup)}(hhh](hcolspec)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jhjubj )}(hhh]h}(h]h ]h"]h$]h&]colwidthKKuh1jhjubhtbody)}(hhh](hrow)}(hhh](hentry)}(hhh]h)}(h'.'h]h‘.’}(hj-hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKJhj*ubah}(h]h ]h"]h$]h&]uh1j(hj%ubj))}(hhh]h)}(hKacquisito con interruzioni disabilitate fuori da un contesto d'interruzioneh]hMacquisito con interruzioni disabilitate fuori da un contesto d’interruzione}(hjDhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKJhjAubah}(h]h ]h"]h$]h&]uh1j(hj%ubeh}(h]h ]h"]h$]h&]uh1j#hj ubj$)}(hhh](j))}(hhh]h)}(h'-'h]h‘-’}(hjdhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKKhjaubah}(h]h ]h"]h$]h&]uh1j(hj^ubj))}(hhh]h)}(h$acquisito in contesto d'interruzioneh]h&acquisito in contesto d’interruzione}(hj{hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKKhjxubah}(h]h ]h"]h$]h&]uh1j(hj^ubeh}(h]h ]h"]h$]h&]uh1j#hj ubj$)}(hhh](j))}(hhh]h)}(h'+'h]h‘+’}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKLhjubah}(h]h ]h"]h$]h&]uh1j(hjubj))}(hhh]h)}(h$acquisito con interruzioni abilitateh]h$acquisito con interruzioni abilitate}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKLhjubah}(h]h ]h"]h$]h&]uh1j(hjubeh}(h]h ]h"]h$]h&]uh1j#hj ubj$)}(hhh](j))}(hhh]h)}(h'?'h]h‘?’}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKMhjubah}(h]h ]h"]h$]h&]uh1j(hjubj))}(hhh]h)}(h?acquisito in contesto d'interruzione con interruzioni abilitateh]hAacquisito in contesto d’interruzione con interruzioni abilitate}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKMhjubah}(h]h ]h"]h$]h&]uh1j(hjubeh}(h]h ]h"]h$]h&]uh1j#hj ubeh}(h]h ]h"]h$]h&]uh1jhjubeh}(h]h ]h"]h$]h&]colsKuh1jhjubah}(h]h ]h"]h$]h&]uh1jhjubah}(h]h ]h"]h$]h&]uh1jhhhKIhjthhubh)}(h"Il seguente esempio mostra i bit::h]h!Il seguente esempio mostra i bit:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKPhjthhubj)}(hX(&sio_locks[i].lock){-.-.}, at: [] mutex_lock+0x21/0x24 |||| ||| \-> softirq disabilitati e fuori da un contesto di softirq || \--> acquisito in un contesto di softirq | \---> hardirq disabilitati e fuori da un contesto di hardirq \----> acquisito in un contesto di hardirqh]hX(&sio_locks[i].lock){-.-.}, at: [] mutex_lock+0x21/0x24 |||| ||| \-> softirq disabilitati e fuori da un contesto di softirq || \--> acquisito in un contesto di softirq | \---> hardirq disabilitati e fuori da un contesto di hardirq \----> acquisito in un contesto di hardirq}hj*sbah}(h]h ]h"]h$]h&]hhuh1jhhhKRhjthhubh)}(hX$Per un dato STATO, che il blocco sia mai stato acquisito in quel contesto di STATO, o che lo STATO sia abilitato, ci lascia coi quattro possibili scenari mostrati nella seguente tabella. Il carattere associato al bit indica con esattezza in quale scenario ci si trova al momento del rapporto.h]hX$Per un dato STATO, che il blocco sia mai stato acquisito in quel contesto di STATO, o che lo STATO sia abilitato, ci lascia coi quattro possibili scenari mostrati nella seguente tabella. Il carattere associato al bit indica con esattezza in quale scenario ci si trova al momento del rapporto.}(hj8hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKYhjthhubj)}(hXs+---------------+---------------+------------------+ | | irq abilitati | irq disabilitati | +---------------+---------------+------------------+ | sempre in irq | '?' | '-' | +---------------+---------------+------------------+ | mai in irq | '+' | '.' | +---------------+---------------+------------------+ h]j)}(hhh]j)}(hhh](j )}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jhjMubj )}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jhjMubj )}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jhjMubj)}(hhh](j$)}(hhh](j))}(hhh]h}(h]h ]h"]h$]h&]uh1j(hjqubj))}(hhh]h)}(h irq abilitatih]h irq abilitati}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK_hj}ubah}(h]h ]h"]h$]h&]uh1j(hjqubj))}(hhh]h)}(hirq disabilitatih]hirq disabilitati}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK_hjubah}(h]h ]h"]h$]h&]uh1j(hjqubeh}(h]h ]h"]h$]h&]uh1j#hjnubj$)}(hhh](j))}(hhh]h)}(h sempre in irqh]h sempre in irq}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKahjubah}(h]h ]h"]h$]h&]uh1j(hjubj))}(hhh]h)}(h'?'h]h‘?’}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKahjubah}(h]h ]h"]h$]h&]uh1j(hjubj))}(hhh]h)}(h'-'h]h‘-’}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKahjubah}(h]h ]h"]h$]h&]uh1j(hjubeh}(h]h ]h"]h$]h&]uh1j#hjnubj$)}(hhh](j))}(hhh]h)}(h mai in irqh]h mai in irq}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKchjubah}(h]h ]h"]h$]h&]uh1j(hjubj))}(hhh]h)}(h'+'h]h‘+’}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKchjubah}(h]h ]h"]h$]h&]uh1j(hjubj))}(hhh]h)}(h'.'h]h‘.’}(hj3hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKchj0ubah}(h]h ]h"]h$]h&]uh1j(hjubeh}(h]h ]h"]h$]h&]uh1j#hjnubeh}(h]h ]h"]h$]h&]uh1jhjMubeh}(h]h ]h"]h$]h&]colsKuh1jhjJubah}(h]h ]h"]h$]h&]uh1jhjFubah}(h]h ]h"]h$]h&]uh1jhhhK^hjthhubh)}(hIl carattere '-' suggerisce che le interruzioni sono disabilitate perché altrimenti verrebbe mostrato il carattere '?'. Una deduzione simile può essere fatta anche per '+'h]hIl carattere ‘-’ suggerisce che le interruzioni sono disabilitate perché altrimenti verrebbe mostrato il carattere ‘?’. Una deduzione simile può essere fatta anche per ‘+’}(hjfhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKfhjthhubh)}(hYI blocchi inutilizzati (ad esempio i mutex) non possono essere fra le cause di un errore.h]hYI blocchi inutilizzati (ad esempio i mutex) non possono essere fra le cause di un errore.}(hjthhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKjhjthhubeh}(h]statoah ]h"]statoah$]h&]uh1hhhhhhhhK%ubh)}(hhh](j)}(h(Regole dello stato per un blocco singoloh]h(Regole dello stato per un blocco singolo}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhKnubh)}(hAvere un blocco sicuro in interruzioni (*irq-safe*) significa che è sempre stato usato in un contesto d'interruzione, mentre un blocco insicuro in interruzioni (*irq-unsafe*) significa che è sempre stato acquisito con le interruzioni abilitate.h](h(Avere un blocco sicuro in interruzioni (}(hjhhhNhNubjS)}(h *irq-safe*h]hirq-safe}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jRhjubhr) significa che è sempre stato usato in un contesto d’interruzione, mentre un blocco insicuro in interruzioni (}(hjhhhNhNubjS)}(h *irq-unsafe*h]h irq-unsafe}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jRhjubhH) significa che è sempre stato acquisito con le interruzioni abilitate.}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKphjhhubh)}(hUna classe softirq insicura è automaticamente insicura anche per hardirq. I seguenti stati sono mutualmente esclusivi: solo una può essere vero quando viene usata una classe di blocco::h]hUna classe softirq insicura è automaticamente insicura anche per hardirq. I seguenti stati sono mutualmente esclusivi: solo una può essere vero quando viene usata una classe di blocco:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKuhjhhubj)}(hC o o h]hC o o }hjsbah}(h]h ]h"]h$]h&]hhuh1jhhhKyhjhhubh)}(hXQuesto perché se un blocco può essere usato in un contesto di interruzioni (sicuro in interruzioni), allora non può mai essere acquisito con le interruzioni abilitate (insicuro in interruzioni). Altrimenti potrebbe verificarsi uno stallo. Per esempio, questo blocco viene acquisito, ma prima di essere rilasciato il contesto d'esecuzione viene interrotto nuovamente, e quindi si tenterà di acquisirlo nuovamente. Questo porterà ad uno stallo, in particolare uno stallo ricorsivo.h]hXQuesto perché se un blocco può essere usato in un contesto di interruzioni (sicuro in interruzioni), allora non può mai essere acquisito con le interruzioni abilitate (insicuro in interruzioni). Altrimenti potrebbe verificarsi uno stallo. Per esempio, questo blocco viene acquisito, ma prima di essere rilasciato il contesto d’esecuzione viene interrotto nuovamente, e quindi si tenterà di acquisirlo nuovamente. Questo porterà ad uno stallo, in particolare uno stallo ricorsivo.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK|hjhhubh)}(h`Il validatore rileva e riporta gli usi di blocchi che violano queste regole per blocchi singoli.h]h`Il validatore rileva e riporta gli usi di blocchi che violano queste regole per blocchi singoli.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubeh}(h](regole-dello-stato-per-un-blocco-singoloah ]h"](regole dello stato per un blocco singoloah$]h&]uh1hhhhhhhhKnubh)}(hhh](j)}(h,Regole per le dipendenze di blocchi multiplih]h,Regole per le dipendenze di blocchi multipli}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhj hhhhhKubh)}(hLa stessa classe di blocco non deve essere acquisita due volte, questo perché potrebbe portare ad uno blocco ricorsivo e dunque ad uno stallo.h]hLa stessa classe di blocco non deve essere acquisita due volte, questo perché potrebbe portare ad uno blocco ricorsivo e dunque ad uno stallo.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhj hhubh)}(hFInoltre, due blocchi non possono essere trattenuti in ordine inverso::h]hEInoltre, due blocchi non possono essere trattenuti in ordine inverso:}(hj,hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhj hhubj)}(h -> -> h]h -> -> }hj:sbah}(h]h ]h"]h$]h&]hhuh1jhhhKhj hhubh)}(hXperché porterebbe ad uno stallo - chiamato stallo da blocco inverso - in cui si cerca di trattenere i due blocchi in un ciclo in cui entrambe i contesti aspettano per sempre che l'altro termini. Il validatore è in grado di trovare queste dipendenze cicliche di qualsiasi complessità, ovvero nel mezzo ci potrebbero essere altre sequenze di blocchi. Il validatore troverà se questi blocchi possono essere acquisiti circolarmente.h]hXperché porterebbe ad uno stallo - chiamato stallo da blocco inverso - in cui si cerca di trattenere i due blocchi in un ciclo in cui entrambe i contesti aspettano per sempre che l’altro termini. Il validatore è in grado di trovare queste dipendenze cicliche di qualsiasi complessità, ovvero nel mezzo ci potrebbero essere altre sequenze di blocchi. Il validatore troverà se questi blocchi possono essere acquisiti circolarmente.}(hjHhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhj hhubh)}(hIn aggiunta, le seguenti sequenze di blocco nei contesti indicati non sono permesse, indipendentemente da quale che sia la classe di blocco::h]hIn aggiunta, le seguenti sequenze di blocco nei contesti indicati non sono permesse, indipendentemente da quale che sia la classe di blocco:}(hjVhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhj hhubj)}(hK -> -> h]hK -> -> }hjdsbah}(h]h ]h"]h$]h&]hhuh1jhhhKhj hhubh)}(hXLa prima regola deriva dal fatto che un blocco sicuro in interruzioni può essere trattenuto in un contesto d'interruzione che, per definizione, ha la possibilità di interrompere un blocco insicuro in interruzioni; questo porterebbe ad uno stallo da blocco inverso. La seconda, analogamente, ci dice che un blocco sicuro in interruzioni software potrebbe essere trattenuto in un contesto di interruzione software, dunque potrebbe interrompere un blocco insicuro in interruzioni software.h]hXLa prima regola deriva dal fatto che un blocco sicuro in interruzioni può essere trattenuto in un contesto d’interruzione che, per definizione, ha la possibilità di interrompere un blocco insicuro in interruzioni; questo porterebbe ad uno stallo da blocco inverso. La seconda, analogamente, ci dice che un blocco sicuro in interruzioni software potrebbe essere trattenuto in un contesto di interruzione software, dunque potrebbe interrompere un blocco insicuro in interruzioni software.}(hjrhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhj hhubh)}(hLe suddette regole vengono applicate per qualsiasi sequenza di blocchi: quando si acquisiscono nuovi blocchi, il validatore verifica se vi è una violazione delle regole fra il nuovo blocco e quelli già trattenuti.h]hLe suddette regole vengono applicate per qualsiasi sequenza di blocchi: quando si acquisiscono nuovi blocchi, il validatore verifica se vi è una violazione delle regole fra il nuovo blocco e quelli già trattenuti.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhj hhubh)}(hJQuando una classe di blocco cambia stato, applicheremo le seguenti regole:h]hJQuando una classe di blocco cambia stato, applicheremo le seguenti regole:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhj hhubj)}(hhh](j)}(hse viene trovato un nuovo blocco sicuro in interruzioni, verificheremo se abbia mai trattenuto dei blocchi insicuri in interruzioni. h]h)}(hse viene trovato un nuovo blocco sicuro in interruzioni, verificheremo se abbia mai trattenuto dei blocchi insicuri in interruzioni.h]hse viene trovato un nuovo blocco sicuro in interruzioni, verificheremo se abbia mai trattenuto dei blocchi insicuri in interruzioni.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubj)}(hse viene trovato un nuovo blocco sicuro in interruzioni software, verificheremo se abbia trattenuto dei blocchi insicuri in interruzioni software. h]h)}(hse viene trovato un nuovo blocco sicuro in interruzioni software, verificheremo se abbia trattenuto dei blocchi insicuri in interruzioni software.h]hse viene trovato un nuovo blocco sicuro in interruzioni software, verificheremo se abbia trattenuto dei blocchi insicuri in interruzioni software.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubj)}(hse viene trovato un nuovo blocco insicuro in interruzioni, verificheremo se abbia trattenuto dei blocchi sicuri in interruzioni. h]h)}(hse viene trovato un nuovo blocco insicuro in interruzioni, verificheremo se abbia trattenuto dei blocchi sicuri in interruzioni.h]hse viene trovato un nuovo blocco insicuro in interruzioni, verificheremo se abbia trattenuto dei blocchi sicuri in interruzioni.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubj)}(hse viene trovato un nuovo blocco insicuro in interruzioni software, verificheremo se abbia trattenuto dei blocchi sicuri in interruzioni software. h]h)}(hse viene trovato un nuovo blocco insicuro in interruzioni software, verificheremo se abbia trattenuto dei blocchi sicuri in interruzioni software.h]hse viene trovato un nuovo blocco insicuro in interruzioni software, verificheremo se abbia trattenuto dei blocchi sicuri in interruzioni software.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubeh}(h]h ]h"]h$]h&]j j uh1jhhhKhj hhubh)}(h(Di nuovo, questi controlli vengono fatti perché un contesto d'interruzione potrebbe interrompere l'esecuzione di qualsiasi blocco insicuro portando ad uno stallo; questo anche se lo stallo non si verifica in pratica)h]h(Di nuovo, questi controlli vengono fatti perché un contesto d’interruzione potrebbe interrompere l’esecuzione di qualsiasi blocco insicuro portando ad uno stallo; questo anche se lo stallo non si verifica in pratica)}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhj hhubeh}(h],regole-per-le-dipendenze-di-blocchi-multipliah ]h"],regole per le dipendenze di blocchi multipliah$]h&]uh1hhhhhhhhKubh)}(hhh](j)}(hBEccezione: dipendenze annidate sui dati portano a blocchi annidatih]hBEccezione: dipendenze annidate sui dati portano a blocchi annidati}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhKubh)}(hXCi sono alcuni casi in cui il kernel Linux acquisisce più volte la stessa istanza di una classe di blocco. Solitamente, questo succede quando esiste una gerarchia fra oggetti dello stesso tipo. In questi casi viene ereditato implicitamente l'ordine fra i due oggetti (definito dalle proprietà di questa gerarchia), ed il kernel tratterrà i blocchi in questo ordine prefissato per ognuno degli oggetti.h]hXCi sono alcuni casi in cui il kernel Linux acquisisce più volte la stessa istanza di una classe di blocco. Solitamente, questo succede quando esiste una gerarchia fra oggetti dello stesso tipo. In questi casi viene ereditato implicitamente l’ordine fra i due oggetti (definito dalle proprietà di questa gerarchia), ed il kernel tratterrà i blocchi in questo ordine prefissato per ognuno degli oggetti.}(hj,hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(hXUn esempio di questa gerarchia di oggetti che producono "blocchi annidati" sono i *block-dev* che rappresentano l'intero disco e quelli che rappresentano una sua partizione; la partizione è una parte del disco intero, e l'ordine dei blocchi sarà corretto fintantoche uno acquisisce il blocco del disco intero e poi quello della partizione. Il validatore non rileva automaticamente questo ordine implicito, perché queste regole di sincronizzazione non sono statiche.h](hVUn esempio di questa gerarchia di oggetti che producono “blocchi annidati” sono i }(hj:hhhNhNubjS)}(h *block-dev*h]h block-dev}(hjBhhhNhNubah}(h]h ]h"]h$]h&]uh1jRhj:ubhX{ che rappresentano l’intero disco e quelli che rappresentano una sua partizione; la partizione è una parte del disco intero, e l’ordine dei blocchi sarà corretto fintantoche uno acquisisce il blocco del disco intero e poi quello della partizione. Il validatore non rileva automaticamente questo ordine implicito, perché queste regole di sincronizzazione non sono statiche.}(hj:hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(hPer istruire il validatore riguardo a questo uso corretto dei blocchi sono stati introdotte nuove primitive per specificare i "livelli di annidamento". Per esempio, per i blocchi a mutua esclusione dei *block-dev* si avrebbe una chiamata simile a::h](hPer istruire il validatore riguardo a questo uso corretto dei blocchi sono stati introdotte nuove primitive per specificare i “livelli di annidamento”. Per esempio, per i blocchi a mutua esclusione dei }(hjZhhhNhNubjS)}(h *block-dev*h]h block-dev}(hjbhhhNhNubah}(h]h ]h"]h$]h&]uh1jRhjZubh" si avrebbe una chiamata simile a:}(hjZhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhjhhubj)}(henum bdev_bd_mutex_lock_class { BD_MUTEX_NORMAL, BD_MUTEX_WHOLE, BD_MUTEX_PARTITION }; mutex_lock_nested(&bdev->bd_contains->bd_mutex, BD_MUTEX_PARTITION);h]henum bdev_bd_mutex_lock_class { BD_MUTEX_NORMAL, BD_MUTEX_WHOLE, BD_MUTEX_PARTITION }; mutex_lock_nested(&bdev->bd_contains->bd_mutex, BD_MUTEX_PARTITION);}hjzsbah}(h]h ]h"]h$]h&]hhuh1jhhhKhjhhubh)}(hiIn questo caso la sincronizzazione viene fatta su un *block-dev* sapendo che si tratta di una partizione.h](h5In questo caso la sincronizzazione viene fatta su un }(hjhhhNhNubjS)}(h *block-dev*h]h block-dev}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jRhjubh) sapendo che si tratta di una partizione.}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(heAi fini della validazione, il validatore lo considererà con una - sotto - classe di blocco separata.h]heAi fini della validazione, il validatore lo considererà con una - sotto - classe di blocco separata.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(hNota: Prestate estrema attenzione che la vostra gerarchia sia corretta quando si vogliono usare le primitive _nested(); altrimenti potreste avere sia falsi positivi che falsi negativi.h]hNota: Prestate estrema attenzione che la vostra gerarchia sia corretta quando si vogliono usare le primitive _nested(); altrimenti potreste avere sia falsi positivi che falsi negativi.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubeh}(h]Aeccezione-dipendenze-annidate-sui-dati-portano-a-blocchi-annidatiah ]h"]Beccezione: dipendenze annidate sui dati portano a blocchi annidatiah$]h&]uh1hhhhhhhhKubh)}(hhh](j)}(h Annotazionih]h Annotazioni}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhKubh)}(hSi possono utilizzare due costrutti per verificare ed annotare se certi blocchi devono essere trattenuti: lockdep_assert_held*(&lock) e lockdep_*pin_lock(&lock).h]hSi possono utilizzare due costrutti per verificare ed annotare se certi blocchi devono essere trattenuti: lockdep_assert_held*(&lock) e lockdep_*pin_lock(&lock).}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(hX Come suggerito dal nome, la famiglia di macro lockdep_assert_held* asseriscono che un dato blocco in un dato momento deve essere trattenuto (altrimenti, verrà generato un WARN()). Queste vengono usate abbondantemente nel kernel, per esempio in kernel/sched/core.c::h]hX Come suggerito dal nome, la famiglia di macro lockdep_assert_held* asseriscono che un dato blocco in un dato momento deve essere trattenuto (altrimenti, verrà generato un WARN()). Queste vengono usate abbondantemente nel kernel, per esempio in kernel/sched/core.c:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubj)}(hkvoid update_rq_clock(struct rq *rq) { s64 delta; lockdep_assert_held(&rq->lock); [...] }h]hkvoid update_rq_clock(struct rq *rq) { s64 delta; lockdep_assert_held(&rq->lock); [...] }}hjsbah}(h]h ]h"]h$]h&]hhuh1jhhhKhjhhubh)}(hTdove aver trattenuto rq->lock è necessario per aggiornare in sicurezza il clock rq.h]hTdove aver trattenuto rq->lock è necessario per aggiornare in sicurezza il clock rq.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(hXL'altra famiglia di macro è lockdep_*pin_lock(), che a dire il vero viene usata solo per rq->lock ATM. Se per caso un blocco non viene trattenuto, queste genereranno un WARN(). Questo si rivela particolarmente utile quando si deve verificare la correttezza di codice con *callback*, dove livelli superiori potrebbero assumere che un blocco rimanga trattenuto, ma livelli inferiori potrebbero invece pensare che il blocco possa essere rilasciato e poi riacquisito (involontariamente si apre una sezione critica). lockdep_pin_lock() restituisce 'struct pin_cookie' che viene usato da lockdep_unpin_lock() per verificare che nessuno abbia manomesso il blocco. Per esempio in kernel/sched/sched.h abbiamo::h](hXL’altra famiglia di macro è lockdep_*pin_lock(), che a dire il vero viene usata solo per rq->lock ATM. Se per caso un blocco non viene trattenuto, queste genereranno un WARN(). Questo si rivela particolarmente utile quando si deve verificare la correttezza di codice con }(hjhhhNhNubjS)}(h *callback*h]hcallback}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jRhjubhX, dove livelli superiori potrebbero assumere che un blocco rimanga trattenuto, ma livelli inferiori potrebbero invece pensare che il blocco possa essere rilasciato e poi riacquisito (involontariamente si apre una sezione critica). lockdep_pin_lock() restituisce ‘struct pin_cookie’ che viene usato da lockdep_unpin_lock() per verificare che nessuno abbia manomesso il blocco. Per esempio in kernel/sched/sched.h abbiamo:}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhjhhubj)}(hX static inline void rq_pin_lock(struct rq *rq, struct rq_flags *rf) { rf->cookie = lockdep_pin_lock(&rq->lock); [...] } static inline void rq_unpin_lock(struct rq *rq, struct rq_flags *rf) { [...] lockdep_unpin_lock(&rq->lock, rf->cookie); }h]hX static inline void rq_pin_lock(struct rq *rq, struct rq_flags *rf) { rf->cookie = lockdep_pin_lock(&rq->lock); [...] } static inline void rq_unpin_lock(struct rq *rq, struct rq_flags *rf) { [...] lockdep_unpin_lock(&rq->lock, rf->cookie); }}hj5sbah}(h]h ]h"]h$]h&]hhuh1jhhhM hjhhubh)}(hXMI commenti riguardo alla sincronizzazione possano fornire informazioni utili, tuttavia sono le verifiche in esecuzione effettuate da queste macro ad essere vitali per scovare problemi di sincronizzazione, ed inoltre forniscono lo stesso livello di informazioni quando si ispeziona il codice. Nel dubbio, preferite queste annotazioni!h]hXMI commenti riguardo alla sincronizzazione possano fornire informazioni utili, tuttavia sono le verifiche in esecuzione effettuate da queste macro ad essere vitali per scovare problemi di sincronizzazione, ed inoltre forniscono lo stesso livello di informazioni quando si ispeziona il codice. Nel dubbio, preferite queste annotazioni!}(hjChhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubeh}(h] annotazioniah ]h"] annotazioniah$]h&]uh1hhhhhhhhKubh)}(hhh](j)}(h$Dimostrazione di correttezza al 100%h]h$Dimostrazione di correttezza al 100%}(hj\hhhNhNubah}(h]h ]h"]h$]h&]uh1hhjYhhhhhMubh)}(hXfIl validatore verifica la proprietà di chiusura in senso matematico. Ovvero, per ogni sequenza di sincronizzazione di un singolo processo che si verifichi almeno una volta nel kernel, il validatore dimostrerà con una certezza del 100% che nessuna combinazione e tempistica di queste sequenze possa causare uno stallo in una qualsiasi classe di blocco. [1]_h](hXbIl validatore verifica la proprietà di chiusura in senso matematico. Ovvero, per ogni sequenza di sincronizzazione di un singolo processo che si verifichi almeno una volta nel kernel, il validatore dimostrerà con una certezza del 100% che nessuna combinazione e tempistica di queste sequenze possa causare uno stallo in una qualsiasi classe di blocco. }(hjjhhhNhNubhfootnote_reference)}(h[1]_h]h1}(hjthhhNhNubah}(h]id1ah ]h"]h$]h&]refidid2docnamehuh1jrhjjresolvedKubeh}(h]h ]h"]h$]h&]uh1hhhhMhjYhhubh)}(hXIn pratica, per dimostrare l'esistenza di uno stallo non servono complessi scenari di sincronizzazione multi-processore e multi-processo. Il validatore può dimostrare la correttezza basandosi sulla sola sequenza di sincronizzazione apparsa almeno una volta (in qualunque momento, in qualunque processo o contesto). Uno scenario complesso che avrebbe bisogno di 3 processori e una sfortunata presenza di processi, interruzioni, e pessimo tempismo, può essere riprodotto su un sistema a singolo processore.h]hXIn pratica, per dimostrare l’esistenza di uno stallo non servono complessi scenari di sincronizzazione multi-processore e multi-processo. Il validatore può dimostrare la correttezza basandosi sulla sola sequenza di sincronizzazione apparsa almeno una volta (in qualunque momento, in qualunque processo o contesto). Uno scenario complesso che avrebbe bisogno di 3 processori e una sfortunata presenza di processi, interruzioni, e pessimo tempismo, può essere riprodotto su un sistema a singolo processore.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM%hjYhhubh)}(hXQuesto riduce drasticamente la complessità del controllo di qualità della sincronizzazione nel kernel: quello che deve essere fatto è di innescare nel kernel quante più possibili "semplici" sequenze di sincronizzazione, almeno una volta, allo scopo di dimostrarne la correttezza. Questo al posto di innescare una verifica per ogni possibile combinazione di sincronizzazione fra processori, e differenti scenari con hardirq e softirq e annidamenti vari (nella pratica, impossibile da fare)h]hXQuesto riduce drasticamente la complessità del controllo di qualità della sincronizzazione nel kernel: quello che deve essere fatto è di innescare nel kernel quante più possibili “semplici” sequenze di sincronizzazione, almeno una volta, allo scopo di dimostrarne la correttezza. Questo al posto di innescare una verifica per ogni possibile combinazione di sincronizzazione fra processori, e differenti scenari con hardirq e softirq e annidamenti vari (nella pratica, impossibile da fare)}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM-hjYhhubhfootnote)}(hXassumendo che il validatore sia corretto al 100%, e che nessun altra parte del sistema possa corromperne lo stato. Assumiamo anche che tutti i percorsi MNI/SMM [potrebbero interrompere anche percorsi dove le interruzioni sono disabilitate] sono corretti e non interferiscono con il validatore. Inoltre, assumiamo che un hash a 64-bit sia unico per ogni sequenza di sincronizzazione nel sistema. Infine, la ricorsione dei blocchi non deve essere maggiore di 20. h](hlabel)}(h1h]h1}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh)}(hXassumendo che il validatore sia corretto al 100%, e che nessun altra parte del sistema possa corromperne lo stato. Assumiamo anche che tutti i percorsi MNI/SMM [potrebbero interrompere anche percorsi dove le interruzioni sono disabilitate] sono corretti e non interferiscono con il validatore. Inoltre, assumiamo che un hash a 64-bit sia unico per ogni sequenza di sincronizzazione nel sistema. Infine, la ricorsione dei blocchi non deve essere maggiore di 20.h]hXassumendo che il validatore sia corretto al 100%, e che nessun altra parte del sistema possa corromperne lo stato. Assumiamo anche che tutti i percorsi MNI/SMM [potrebbero interrompere anche percorsi dove le interruzioni sono disabilitate] sono corretti e non interferiscono con il validatore. Inoltre, assumiamo che un hash a 64-bit sia unico per ogni sequenza di sincronizzazione nel sistema. Infine, la ricorsione dei blocchi non deve essere maggiore di 20.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM7hjubeh}(h]jah ]h"]1ah$]h&]j~ajhuh1jhhhM5hjYhhjKubeh}(h]#dimostrazione-di-correttezza-al-100ah ]h"]$dimostrazione di correttezza al 100%ah$]h&]uh1hhhhhhhhMubh)}(hhh](j)}(h Prestazioneh]h Prestazione}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhM@ubh)}(hXLe regole sopracitate hanno bisogno di una quantità **enorme** di verifiche durante l'esecuzione. Il sistema sarebbe diventato praticamente inutilizzabile per la sua lentezza se le avessimo fatte davvero per ogni blocco trattenuto e per ogni abilitazione delle interruzioni. La complessità della verifica è O(N^2), quindi avremmo dovuto fare decine di migliaia di verifiche per ogni evento, il tutto per poche centinaia di classi.h](h5Le regole sopracitate hanno bisogno di una quantità }(hjhhhNhNubhstrong)}(h **enorme**h]henorme}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubhXt di verifiche durante l’esecuzione. Il sistema sarebbe diventato praticamente inutilizzabile per la sua lentezza se le avessimo fatte davvero per ogni blocco trattenuto e per ogni abilitazione delle interruzioni. La complessità della verifica è O(N^2), quindi avremmo dovuto fare decine di migliaia di verifiche per ogni evento, il tutto per poche centinaia di classi.}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMBhjhhubh)}(hXIl problema è stato risolto facendo una singola verifica per ogni 'scenario di sincronizzazione' (una sequenza unica di blocchi trattenuti uno dopo l'altro). Per farlo, viene mantenuta una pila dei blocchi trattenuti, e viene calcolato un hash a 64-bit unico per ogni sequenza. Quando la sequenza viene verificata per la prima volta, l'hash viene inserito in una tabella hash. La tabella potrà essere verificata senza bisogno di blocchi. Se la sequenza dovesse ripetersi, la tabella ci dirà che non è necessario verificarla nuovamente.h]hX#Il problema è stato risolto facendo una singola verifica per ogni ‘scenario di sincronizzazione’ (una sequenza unica di blocchi trattenuti uno dopo l’altro). Per farlo, viene mantenuta una pila dei blocchi trattenuti, e viene calcolato un hash a 64-bit unico per ogni sequenza. Quando la sequenza viene verificata per la prima volta, l’hash viene inserito in una tabella hash. La tabella potrà essere verificata senza bisogno di blocchi. Se la sequenza dovesse ripetersi, la tabella ci dirà che non è necessario verificarla nuovamente.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMIhjhhubeh}(h] prestazioneah ]h"] prestazioneah$]h&]uh1hhhhhhhhM@ubh)}(hhh](j)}(hRisoluzione dei problemih]hRisoluzione dei problemi}(hj( hhhNhNubah}(h]h ]h"]h$]h&]uh1hhj% hhhhhMRubh)}(hIl massimo numero di classi di blocco che il validatore può tracciare è: MAX_LOCKDEP_KEYS. Oltrepassare questo limite indurrà lokdep a generare il seguente avviso::h]hIl massimo numero di classi di blocco che il validatore può tracciare è: MAX_LOCKDEP_KEYS. Oltrepassare questo limite indurrà lokdep a generare il seguente avviso:}(hj6 hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMThj% hhubj)}(h-(DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS))h]h-(DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS))}hjD sbah}(h]h ]h"]h$]h&]hhuh1jhhhMXhj% hhubh)}(hX Di base questo valore è 8191, e un classico sistema da ufficio ha meno di 1000 classi, dunque questo avviso è solitamente la conseguenza di un problema di perdita delle classi di blocco o d'inizializzazione dei blocchi. Di seguito una descrizione dei due problemi:h]hX Di base questo valore è 8191, e un classico sistema da ufficio ha meno di 1000 classi, dunque questo avviso è solitamente la conseguenza di un problema di perdita delle classi di blocco o d’inizializzazione dei blocchi. Di seguito una descrizione dei due problemi:}(hjR hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMZhj% hhubhenumerated_list)}(hhh](j)}(hXcaricare e rimuovere continuamente i moduli mentre il validatore è in esecuzione porterà ad una perdita di classi di blocco. Il problema è che ogni caricamento crea un nuovo insieme di classi di blocco per tutti i blocchi di quel modulo. Tuttavia, la rimozione del modulo non rimuove le vecchie classi (vedi dopo perché non le riusiamo). Dunque, il continuo caricamento e rimozione di un modulo non fa altro che aumentare il contatore di classi fino a raggiungere, eventualmente, il limite. h]h)}(hXcaricare e rimuovere continuamente i moduli mentre il validatore è in esecuzione porterà ad una perdita di classi di blocco. Il problema è che ogni caricamento crea un nuovo insieme di classi di blocco per tutti i blocchi di quel modulo. Tuttavia, la rimozione del modulo non rimuove le vecchie classi (vedi dopo perché non le riusiamo). Dunque, il continuo caricamento e rimozione di un modulo non fa altro che aumentare il contatore di classi fino a raggiungere, eventualmente, il limite.h]hXcaricare e rimuovere continuamente i moduli mentre il validatore è in esecuzione porterà ad una perdita di classi di blocco. Il problema è che ogni caricamento crea un nuovo insieme di classi di blocco per tutti i blocchi di quel modulo. Tuttavia, la rimozione del modulo non rimuove le vecchie classi (vedi dopo perché non le riusiamo). Dunque, il continuo caricamento e rimozione di un modulo non fa altro che aumentare il contatore di classi fino a raggiungere, eventualmente, il limite.}(hji hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM_hje ubah}(h]h ]h"]h$]h&]uh1jhjb hhhhhNubj)}(hXUsare array con un gran numero di blocchi che non vengono esplicitamente inizializzati. Per esempio, una tabella hash con 8192 *bucket* dove ognuno ha il proprio spinlock_t consumerà 8192 classi di blocco a meno che non vengano esplicitamente inizializzati in esecuzione usando spin_lock_init() invece dell'inizializzazione durante la compilazione con __SPIN_LOCK_UNLOCKED(). Sbagliare questa inizializzazione garantisce un esaurimento di classi di blocco. Viceversa, un ciclo che invoca spin_lock_init() su tutti i blocchi li mapperebbe tutti alla stessa classe di blocco. La morale della favola è che dovete sempre inizializzare esplicitamente i vostri blocchi. h](h)}(hX>Usare array con un gran numero di blocchi che non vengono esplicitamente inizializzati. Per esempio, una tabella hash con 8192 *bucket* dove ognuno ha il proprio spinlock_t consumerà 8192 classi di blocco a meno che non vengano esplicitamente inizializzati in esecuzione usando spin_lock_init() invece dell'inizializzazione durante la compilazione con __SPIN_LOCK_UNLOCKED(). Sbagliare questa inizializzazione garantisce un esaurimento di classi di blocco. Viceversa, un ciclo che invoca spin_lock_init() su tutti i blocchi li mapperebbe tutti alla stessa classe di blocco.h](hUsare array con un gran numero di blocchi che non vengono esplicitamente inizializzati. Per esempio, una tabella hash con 8192 }(hj hhhNhNubjS)}(h*bucket*h]hbucket}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jRhj ubhX dove ognuno ha il proprio spinlock_t consumerà 8192 classi di blocco a meno che non vengano esplicitamente inizializzati in esecuzione usando spin_lock_init() invece dell’inizializzazione durante la compilazione con __SPIN_LOCK_UNLOCKED(). Sbagliare questa inizializzazione garantisce un esaurimento di classi di blocco. Viceversa, un ciclo che invoca spin_lock_init() su tutti i blocchi li mapperebbe tutti alla stessa classe di blocco.}(hj hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMghj} ubh)}(hZLa morale della favola è che dovete sempre inizializzare esplicitamente i vostri blocchi.h]hZLa morale della favola è che dovete sempre inizializzare esplicitamente i vostri blocchi.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMphj} ubeh}(h]h ]h"]h$]h&]uh1jhjb hhhhhNubeh}(h]h ]h"]h$]h&]enumtypearabicprefixhsuffix.uh1j` hj% hhhhhM_ubh)}(hXWQualcuno potrebbe argomentare che il validatore debba permettere il riuso di classi di blocco. Tuttavia, se siete tentati dall'argomento, prima revisionate il codice e pensate alla modifiche necessarie, e tenendo a mente che le classi di blocco da rimuovere probabilmente sono legate al grafo delle dipendenze. Più facile a dirsi che a farsi.h]hXYQualcuno potrebbe argomentare che il validatore debba permettere il riuso di classi di blocco. Tuttavia, se siete tentati dall’argomento, prima revisionate il codice e pensate alla modifiche necessarie, e tenendo a mente che le classi di blocco da rimuovere probabilmente sono legate al grafo delle dipendenze. Più facile a dirsi che a farsi.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMshj% hhubh)}(hOvviamente, se non esaurite le classi di blocco, la prossima cosa da fare è quella di trovare le classi non funzionanti. Per prima cosa, il seguente comando ritorna il numero di classi attualmente in uso assieme al valore massimo::h]hOvviamente, se non esaurite le classi di blocco, la prossima cosa da fare è quella di trovare le classi non funzionanti. Per prima cosa, il seguente comando ritorna il numero di classi attualmente in uso assieme al valore massimo:}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMyhj% hhubj)}(h'grep "lock-classes" /proc/lockdep_statsh]h'grep "lock-classes" /proc/lockdep_stats}hj sbah}(h]h ]h"]h$]h&]hhuh1jhhhM}hj% hhubh)}(h.Questo comando produce il seguente messaggio::h]h-Questo comando produce il seguente messaggio:}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj% hhubj)}(h6lock-classes: 748 [max: 8191]h]h6lock-classes: 748 [max: 8191]}hj sbah}(h]h ]h"]h$]h&]hhuh1jhhhMhj% hhubh)}(hSe il numero di assegnazioni (748 qui sopra) aumenta continuamente nel tempo, allora c'è probabilmente un problema da qualche parte. Il seguente comando può essere utilizzato per identificare le classi di blocchi problematiche::h]hSe il numero di assegnazioni (748 qui sopra) aumenta continuamente nel tempo, allora c’è probabilmente un problema da qualche parte. Il seguente comando può essere utilizzato per identificare le classi di blocchi problematiche:}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj% hhubj)}(hgrep "BD" /proc/lockdeph]hgrep "BD" /proc/lockdep}hj sbah}(h]h ]h"]h$]h&]hhuh1jhhhMhj% hhubh)}(hXEseguite il comando e salvatene l'output, quindi confrontatelo con l'output di un'esecuzione successiva per identificare eventuali problemi. Questo stesso output può anche aiutarti a trovare situazioni in cui l'inizializzazione del blocco è stata omessa.h]hXEseguite il comando e salvatene l’output, quindi confrontatelo con l’output di un’esecuzione successiva per identificare eventuali problemi. Questo stesso output può anche aiutarti a trovare situazioni in cui l’inizializzazione del blocco è stata omessa.}(hj" hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj% hhubeh}(h]risoluzione-dei-problemiah ]h"]risoluzione dei problemiah$]h&]uh1hhhhhhhhMRubh)}(hhh](j)}(hLettura ricorsiva dei blocchih]hLettura ricorsiva dei blocchi}(hj; hhhNhNubah}(h]h ]h"]h$]h&]uh1hhj8 hhhhhMubh)}(hhIl resto di questo documento vuole dimostrare che certi cicli equivalgono ad una possibilità di stallo.h]hhIl resto di questo documento vuole dimostrare che certi cicli equivalgono ad una possibilità di stallo.}(hjI hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj8 hhubh)}(hX>Ci sono tre tipi di bloccatori: gli scrittori (bloccatori esclusivi, come spin_lock() o write_lock()), lettori non ricorsivi (bloccatori condivisi, come down_read()), e lettori ricorsivi (bloccatori condivisi ricorsivi, come rcu_read_lock()). D'ora in poi, per questi tipi di bloccatori, useremo la seguente notazione:h]hX@Ci sono tre tipi di bloccatori: gli scrittori (bloccatori esclusivi, come spin_lock() o write_lock()), lettori non ricorsivi (bloccatori condivisi, come down_read()), e lettori ricorsivi (bloccatori condivisi ricorsivi, come rcu_read_lock()). D’ora in poi, per questi tipi di bloccatori, useremo la seguente notazione:}(hjW hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj8 hhubj)}(hXW o E: per gli scrittori (bloccatori esclusivi) (W dall'inglese per *Writer*, ed E per *Exclusive*). r: per i lettori non ricorsivi (r dall'inglese per *reader*). R: per i lettori ricorsivi (R dall'inglese per *Reader*). S: per qualsiasi lettore (non ricorsivi + ricorsivi), dato che entrambe sono bloccatori condivisi (S dall'inglese per *Shared*). N: per gli scrittori ed i lettori non ricorsivi, dato che entrambe sono non ricorsivi. h](hdefinition_list)}(hhh]hdefinition_list_item)}(heW o E: per gli scrittori (bloccatori esclusivi) (W dall'inglese per *Writer*, ed E per *Exclusive*). h](hterm)}(hCW o E: per gli scrittori (bloccatori esclusivi) (W dall'inglese perh]hEW o E: per gli scrittori (bloccatori esclusivi) (W dall’inglese per}(hjv hhhNhNubah}(h]h ]h"]h$]h&]uh1jt hhhMhjp ubh definition)}(hhh]h)}(h *Writer*, ed E per *Exclusive*).h](jS)}(h*Writer*h]hWriter}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jRhj ubh , ed E per }(hj hhhNhNubjS)}(h *Exclusive*h]h Exclusive}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jRhj ubh).}(hj hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1j hjp ubeh}(h]h ]h"]h$]h&]uh1jn hhhMhjk ubah}(h]h ]h"]h$]h&]uh1ji hje ubh)}(h=r: per i lettori non ricorsivi (r dall'inglese per *reader*).h](h5r: per i lettori non ricorsivi (r dall’inglese per }(hj hhhNhNubjS)}(h*reader*h]hreader}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jRhj ubh).}(hj hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhje ubh)}(h9R: per i lettori ricorsivi (R dall'inglese per *Reader*).h](h1R: per i lettori ricorsivi (R dall’inglese per }(hj hhhNhNubjS)}(h*Reader*h]hReader}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jRhj ubh).}(hj hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhje ubjj )}(hhh](jo )}(hS: per qualsiasi lettore (non ricorsivi + ricorsivi), dato che entrambe sono bloccatori condivisi (S dall'inglese per *Shared*). h](ju )}(hGS: per qualsiasi lettore (non ricorsivi + ricorsivi), dato che entrambeh]hGS: per qualsiasi lettore (non ricorsivi + ricorsivi), dato che entrambe}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jt hhhMhj ubj )}(hhh]h)}(h8sono bloccatori condivisi (S dall'inglese per *Shared*).h](h0sono bloccatori condivisi (S dall’inglese per }(hj! hhhNhNubjS)}(h*Shared*h]hShared}(hj) hhhNhNubah}(h]h ]h"]h$]h&]uh1jRhj! ubh).}(hj! hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1j hj ubeh}(h]h ]h"]h$]h&]uh1jn hhhMhj ubjo )}(hWN: per gli scrittori ed i lettori non ricorsivi, dato che entrambe sono non ricorsivi. h](ju )}(hGN: per gli scrittori ed i lettori non ricorsivi, dato che entrambe sonoh]hGN: per gli scrittori ed i lettori non ricorsivi, dato che entrambe sono}(hjQ hhhNhNubah}(h]h ]h"]h$]h&]uh1jt hhhMhjM ubj )}(hhh]h)}(hnon ricorsivi.h]hnon ricorsivi.}(hjb hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj_ ubah}(h]h ]h"]h$]h&]uh1j hjM ubeh}(h]h ]h"]h$]h&]uh1jn hhhMhj ubeh}(h]h ]h"]h$]h&]uh1ji hje ubeh}(h]h ]h"]h$]h&]uh1jhhhMhj8 hhubh)}(h0Ovviamente, N equivale a "r o W" ed S a "r o R".h]h8Ovviamente, N equivale a “r o W” ed S a “r o R”.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj8 hhubh)}(hXCome suggerisce il nome, i lettori ricorsivi sono dei bloccatori a cui è permesso di acquisire la stessa istanza di blocco anche all'interno della sezione critica di un altro lettore. In altre parole, permette di annidare la stessa istanza di blocco nelle sezioni critiche dei lettori.h]hX Come suggerisce il nome, i lettori ricorsivi sono dei bloccatori a cui è permesso di acquisire la stessa istanza di blocco anche all’interno della sezione critica di un altro lettore. In altre parole, permette di annidare la stessa istanza di blocco nelle sezioni critiche dei lettori.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj8 hhubh)}(hmDall'altro canto, lo stesso comportamento indurrebbe un lettore non ricorsivo ad auto infliggersi uno stallo.h]hoDall’altro canto, lo stesso comportamento indurrebbe un lettore non ricorsivo ad auto infliggersi uno stallo.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj8 hhubh)}(hXLa differenza fra questi due tipi di lettori esiste perché: quelli ricorsivi vengono bloccati solo dal trattenimento di un blocco di scrittura, mentre quelli non ricorsivi possono essere bloccati dall'attesa di un blocco di scrittura. Consideriamo il seguente esempio::h]hXLa differenza fra questi due tipi di lettori esiste perché: quelli ricorsivi vengono bloccati solo dal trattenimento di un blocco di scrittura, mentre quelli non ricorsivi possono essere bloccati dall’attesa di un blocco di scrittura. Consideriamo il seguente esempio:}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj8 hhubj)}(h[TASK A: TASK B: read_lock(X); write_lock(X); read_lock_2(X);h]h[TASK A: TASK B: read_lock(X); write_lock(X); read_lock_2(X);}hj sbah}(h]h ]h"]h$]h&]hhuh1jhhhMhj8 hhubh)}(hXL'attività A acquisisce il blocco di lettura X (non importa se di tipo ricorsivo o meno) usando read_lock(). Quando l'attività B tenterà di acquisire il blocco X, si fermerà e rimarrà in attesa che venga rilasciato. Ora se read_lock_2() è un tipo lettore ricorsivo, l'attività A continuerà perché gli scrittori in attesa non possono bloccare lettori ricorsivi, e non avremo alcuno stallo. Tuttavia, se read_lock_2() è un lettore non ricorsivo, allora verrà bloccato dall'attività B e si causerà uno stallo.h]hXL’attività A acquisisce il blocco di lettura X (non importa se di tipo ricorsivo o meno) usando read_lock(). Quando l’attività B tenterà di acquisire il blocco X, si fermerà e rimarrà in attesa che venga rilasciato. Ora se read_lock_2() è un tipo lettore ricorsivo, l’attività A continuerà perché gli scrittori in attesa non possono bloccare lettori ricorsivi, e non avremo alcuno stallo. Tuttavia, se read_lock_2() è un lettore non ricorsivo, allora verrà bloccato dall’attività B e si causerà uno stallo.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj8 hhubeh}(h]lettura-ricorsiva-dei-blocchiah ]h"]lettura ricorsiva dei blocchiah$]h&]uh1hhhhhhhhMubh)}(hhh](j)}(h?Condizioni bloccanti per lettori/scrittori su uno stesso bloccoh]h?Condizioni bloccanti per lettori/scrittori su uno stesso blocco}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhj hhhhhMubh)}(h4Essenzialmente ci sono quattro condizioni bloccanti:h]h4Essenzialmente ci sono quattro condizioni bloccanti:}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj hhubja )}(hhh](j)}(h(Uno scrittore blocca un altro scrittore.h]h)}(hj h]h(Uno scrittore blocca un altro scrittore.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1jhj hhhhhNubj)}(h Un lettore blocca uno scrittore.h]h)}(hj h]h Un lettore blocca uno scrittore.}(hj! hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1jhj hhhhhNubj)}(h?Uno scrittore blocca sia i lettori ricorsivi che non ricorsivi.h]h)}(hj6 h]h?Uno scrittore blocca sia i lettori ricorsivi che non ricorsivi.}(hj8 hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj4 ubah}(h]h ]h"]h$]h&]uh1jhj hhhhhNubj)}(hUn lettore (ricorsivo o meno) non blocca altri lettori ricorsivi ma potrebbe bloccare quelli non ricorsivi (perché potrebbero esistere degli scrittori in attesa). h]h)}(hUn lettore (ricorsivo o meno) non blocca altri lettori ricorsivi ma potrebbe bloccare quelli non ricorsivi (perché potrebbero esistere degli scrittori in attesa).h]hUn lettore (ricorsivo o meno) non blocca altri lettori ricorsivi ma potrebbe bloccare quelli non ricorsivi (perché potrebbero esistere degli scrittori in attesa).}(hjO hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjK ubah}(h]h ]h"]h$]h&]uh1jhj hhhhhNubeh}(h]h ]h"]h$]h&]j j j hj j uh1j` hj hhhhhMubh)}(hDi seguito le tabella delle condizioni bloccanti, Y (*Yes*) significa che il tipo in riga blocca quello in colonna, mentre N l'opposto.h](h5Di seguito le tabella delle condizioni bloccanti, Y (}(hji hhhNhNubjS)}(h*Yes*h]hYes}(hjq hhhNhNubah}(h]h ]h"]h$]h&]uh1jRhji ubhO) significa che il tipo in riga blocca quello in colonna, mentre N l’opposto.}(hji hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhj hhubj)}(h+---+---+---+---+ | | W | r | R | +---+---+---+---+ | W | Y | Y | Y | +---+---+---+---+ | r | Y | Y | N | +---+---+---+---+ | R | Y | Y | N | +---+---+---+---+ (W: scrittori, r: lettori non ricorsivi, R: lettori ricorsivi) h](j)}(hhh]j)}(hhh](j )}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jhj ubj )}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jhj ubj )}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jhj ubj )}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jhj ubj)}(hhh](j$)}(hhh](j))}(hhh]h}(h]h ]h"]h$]h&]uh1j(hj ubj))}(hhh]h)}(hWh]hW}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1j(hj ubj))}(hhh]h)}(hrh]hr}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1j(hj ubj))}(hhh]h)}(hRh]hR}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1j(hj ubeh}(h]h ]h"]h$]h&]uh1j#hj ubj$)}(hhh](j))}(hhh]h)}(hj h]hW}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1j(hj ubj))}(hhh]h)}(hYh]hY}(hj1 hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj. ubah}(h]h ]h"]h$]h&]uh1j(hj ubj))}(hhh]h)}(hj3 h]hY}(hjH hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjE ubah}(h]h ]h"]h$]h&]uh1j(hj ubj))}(hhh]h)}(hj3 h]hY}(hj^ hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj[ ubah}(h]h ]h"]h$]h&]uh1j(hj ubeh}(h]h ]h"]h$]h&]uh1j#hj ubj$)}(hhh](j))}(hhh]h)}(hj h]hr}(hj} hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjz ubah}(h]h ]h"]h$]h&]uh1j(hjw ubj))}(hhh]h)}(hj3 h]hY}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1j(hjw ubj))}(hhh]h)}(hj3 h]hY}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1j(hjw ubj))}(hhh]h)}(hNh]hN}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1j(hjw ubeh}(h]h ]h"]h$]h&]uh1j#hj ubj$)}(hhh](j))}(hhh]h)}(hj h]hR}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1j(hj ubj))}(hhh]h)}(hj3 h]hY}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1j(hj ubj))}(hhh]h)}(hj3 h]hY}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjubah}(h]h ]h"]h$]h&]uh1j(hj ubj))}(hhh]h)}(hj h]hN}(hj!hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjubah}(h]h ]h"]h$]h&]uh1j(hj ubeh}(h]h ]h"]h$]h&]uh1j#hj ubeh}(h]h ]h"]h$]h&]uh1jhj ubeh}(h]h ]h"]h$]h&]colsKuh1jhj ubah}(h]h ]h"]h$]h&]uh1jhj ubh)}(h>(W: scrittori, r: lettori non ricorsivi, R: lettori ricorsivi)h]h>(W: scrittori, r: lettori non ricorsivi, R: lettori ricorsivi)}(hjMhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubeh}(h]h ]h"]h$]h&]uh1jhhhMhj hhubh)}(hAl contrario dei blocchi per lettori non ricorsivi, quelli ricorsivi vengono trattenuti da chi trattiene il blocco di scrittura piuttosto che da chi ne attende il rilascio. Per esempio::h]hAl contrario dei blocchi per lettori non ricorsivi, quelli ricorsivi vengono trattenuti da chi trattiene il blocco di scrittura piuttosto che da chi ne attende il rilascio. Per esempio:}(hjahhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj hhubj)}(heTASK A: TASK B: read_lock(X); write_lock(X); read_lock(X);h]heTASK A: TASK B: read_lock(X); write_lock(X); read_lock(X);}hjosbah}(h]h ]h"]h$]h&]hhuh1jhhhMhj hhubh)}(hX+non produce uno stallo per i lettori ricorsivi, in quanto il processo B rimane in attesta del blocco X, mentre il secondo read_lock() non ha bisogno di aspettare perché si tratta di un lettore ricorsivo. Tuttavia, se read_lock() fosse un lettore non ricorsivo, questo codice produrrebbe uno stallo.h]hX+non produce uno stallo per i lettori ricorsivi, in quanto il processo B rimane in attesta del blocco X, mentre il secondo read_lock() non ha bisogno di aspettare perché si tratta di un lettore ricorsivo. Tuttavia, se read_lock() fosse un lettore non ricorsivo, questo codice produrrebbe uno stallo.}(hj}hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj hhubh)}(hXDa notare che in funzione dell'operazione di blocco usate per l'acquisizione (in particolare il valore del parametro 'read' in lock_acquire()), un blocco può essere di scrittura (blocco esclusivo), di lettura non ricorsivo (blocco condiviso e non ricorsivo), o di lettura ricorsivo (blocco condiviso e ricorsivo). In altre parole, per un'istanza di blocco esistono tre tipi di acquisizione che dipendono dalla funzione di acquisizione usata: esclusiva, di lettura non ricorsiva, e di lettura ricorsiva.h]hXDa notare che in funzione dell’operazione di blocco usate per l’acquisizione (in particolare il valore del parametro ‘read’ in lock_acquire()), un blocco può essere di scrittura (blocco esclusivo), di lettura non ricorsivo (blocco condiviso e non ricorsivo), o di lettura ricorsivo (blocco condiviso e ricorsivo). In altre parole, per un’istanza di blocco esistono tre tipi di acquisizione che dipendono dalla funzione di acquisizione usata: esclusiva, di lettura non ricorsiva, e di lettura ricorsiva.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj hhubh)}(hIn breve, chiamiamo "non ricorsivi" blocchi di scrittura e quelli di lettura non ricorsiva, mentre "ricorsivi" i blocchi di lettura ricorsivi.h]hIn breve, chiamiamo “non ricorsivi” blocchi di scrittura e quelli di lettura non ricorsiva, mentre “ricorsivi” i blocchi di lettura ricorsivi.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj hhubh)}(hI blocchi ricorsivi non si bloccano a vicenda, mentre quelli non ricorsivi sì (anche in lettura). Un blocco di lettura non ricorsivi può bloccare uno ricorsivo, e viceversa.h]hI blocchi ricorsivi non si bloccano a vicenda, mentre quelli non ricorsivi sì (anche in lettura). Un blocco di lettura non ricorsivi può bloccare uno ricorsivo, e viceversa.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj hhubh)}(h=Il seguente esempio mostra uno stallo con blocchi ricorsivi::h]h L2h]hL1 -> L2}hjsbah}(h]h ]h"]h$]h&]hhuh1jhhhMhjhhubh)}(hXQuesto significa che lockdep ha visto acquisire L1 prima di L2 nello stesso contesto di esecuzione. Per quanto riguarda l'individuazione degli stalli, ci interessa sapere se possiamo rimanere bloccati da L2 mentre L1 viene trattenuto. In altre parole, vogliamo sapere se esiste un bloccatore L3 che viene bloccato da L1 e un L2 che viene bloccato da L3. Dunque, siamo interessati a (1) quello che L1 blocca e (2) quello che blocca L2. Di conseguenza, possiamo combinare lettori ricorsivi e non per L1 (perché bloccano gli stessi tipi) e possiamo combinare scrittori e lettori non ricorsivi per L2 (perché vengono bloccati dagli stessi tipi).h]hXQuesto significa che lockdep ha visto acquisire L1 prima di L2 nello stesso contesto di esecuzione. Per quanto riguarda l’individuazione degli stalli, ci interessa sapere se possiamo rimanere bloccati da L2 mentre L1 viene trattenuto. In altre parole, vogliamo sapere se esiste un bloccatore L3 che viene bloccato da L1 e un L2 che viene bloccato da L3. Dunque, siamo interessati a (1) quello che L1 blocca e (2) quello che blocca L2. Di conseguenza, possiamo combinare lettori ricorsivi e non per L1 (perché bloccano gli stessi tipi) e possiamo combinare scrittori e lettori non ricorsivi per L2 (perché vengono bloccati dagli stessi tipi).}(hj"hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubh)}(hnCon questa semplificazione, possiamo dedurre che ci sono 4 tipi di rami nel grafo delle dipendenze di lockdep:h]hnCon questa semplificazione, possiamo dedurre che ci sono 4 tipi di rami nel grafo delle dipendenze di lockdep:}(hj0hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubja )}(hhh](j)}(h-(ER)->: dipendenza da scrittore esclusivo a lettore ricorsivo. "X -(ER)-> Y" significa X -> Y, dove X è uno scrittore e Y un lettore ricorsivo. h]jj )}(hhh]jo )}(h-(ER)->: dipendenza da scrittore esclusivo a lettore ricorsivo. "X -(ER)-> Y" significa X -> Y, dove X è uno scrittore e Y un lettore ricorsivo. h](ju )}(h-(ER)->:h]h-(ER)->:}(hjLhhhNhNubah}(h]h ]h"]h$]h&]uh1jt hhhM$hjHubj )}(hhh]h)}(hdipendenza da scrittore esclusivo a lettore ricorsivo. "X -(ER)-> Y" significa X -> Y, dove X è uno scrittore e Y un lettore ricorsivo.h]hdipendenza da scrittore esclusivo a lettore ricorsivo. “X -(ER)-> Y” significa X -> Y, dove X è uno scrittore e Y un lettore ricorsivo.}(hj]hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM#hjZubah}(h]h ]h"]h$]h&]uh1j hjHubeh}(h]h ]h"]h$]h&]uh1jn hhhM$hjEubah}(h]h ]h"]h$]h&]uh1ji hjAubah}(h]h ]h"]h$]h&]uh1jhj>hhhNhNubj)}(h-(EN)->: dipendenza da scrittore esclusivo a bloccatore non ricorsivo. "X -(EN)->" significa X-> Y, dove X è uno scrittore e Y può essere o uno scrittore o un lettore non ricorsivo. h]jj )}(hhh]jo )}(h-(EN)->: dipendenza da scrittore esclusivo a bloccatore non ricorsivo. "X -(EN)->" significa X-> Y, dove X è uno scrittore e Y può essere o uno scrittore o un lettore non ricorsivo. h](ju )}(h-(EN)->:h]h-(EN)->:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jt hhhM)hjubj )}(hhh]h)}(hdipendenza da scrittore esclusivo a bloccatore non ricorsivo. "X -(EN)->" significa X-> Y, dove X è uno scrittore e Y può essere o uno scrittore o un lettore non ricorsivo.h]hdipendenza da scrittore esclusivo a bloccatore non ricorsivo. “X -(EN)->” significa X-> Y, dove X è uno scrittore e Y può essere o uno scrittore o un lettore non ricorsivo.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM'hjubah}(h]h ]h"]h$]h&]uh1j hjubeh}(h]h ]h"]h$]h&]uh1jn hhhM)hjubah}(h]h ]h"]h$]h&]uh1ji hjubah}(h]h ]h"]h$]h&]uh1jhj>hhhNhNubj)}(h-(SR)->: dipendenza da lettore condiviso a lettore ricorsivo. "X -(SR)->" significa X -> Y, dove X è un lettore (ricorsivo o meno) e Y è un lettore ricorsivo. h]jj )}(hhh]jo )}(h-(SR)->: dipendenza da lettore condiviso a lettore ricorsivo. "X -(SR)->" significa X -> Y, dove X è un lettore (ricorsivo o meno) e Y è un lettore ricorsivo. h](ju )}(h-(SR)->:h]h-(SR)->:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jt hhhM.hjubj )}(hhh]h)}(hdipendenza da lettore condiviso a lettore ricorsivo. "X -(SR)->" significa X -> Y, dove X è un lettore (ricorsivo o meno) e Y è un lettore ricorsivo.h]hdipendenza da lettore condiviso a lettore ricorsivo. “X -(SR)->” significa X -> Y, dove X è un lettore (ricorsivo o meno) e Y è un lettore ricorsivo.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM,hjubah}(h]h ]h"]h$]h&]uh1j hjubeh}(h]h ]h"]h$]h&]uh1jn hhhM.hjubah}(h]h ]h"]h$]h&]uh1ji hjubah}(h]h ]h"]h$]h&]uh1jhj>hhhNhNubj)}(h-(SN)->: dipendenza da lettore condiviso a bloccatore non ricorsivo. "X -(SN)-> Y" significa X -> Y , dove X è un lettore (ricorsivo o meno) e Y può essere o uno scrittore o un lettore non ricorsivo. h]jj )}(hhh]jo )}(h-(SN)->: dipendenza da lettore condiviso a bloccatore non ricorsivo. "X -(SN)-> Y" significa X -> Y , dove X è un lettore (ricorsivo o meno) e Y può essere o uno scrittore o un lettore non ricorsivo. h](ju )}(h-(SN)->:h]h-(SN)->:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jt hhhM3hjubj )}(hhh]h)}(hdipendenza da lettore condiviso a bloccatore non ricorsivo. "X -(SN)-> Y" significa X -> Y , dove X è un lettore (ricorsivo o meno) e Y può essere o uno scrittore o un lettore non ricorsivo.h]hdipendenza da lettore condiviso a bloccatore non ricorsivo. “X -(SN)-> Y” significa X -> Y , dove X è un lettore (ricorsivo o meno) e Y può essere o uno scrittore o un lettore non ricorsivo.}(hj#hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM1hj ubah}(h]h ]h"]h$]h&]uh1j hjubeh}(h]h ]h"]h$]h&]uh1jn hhhM3hj ubah}(h]h ]h"]h$]h&]uh1ji hjubah}(h]h ]h"]h$]h&]uh1jhj>hhhNhNubeh}(h]h ]h"]h$]h&]j j j hj )uh1j` hjhhhhhM"ubh)}(hcDa notare che presi due blocchi, questi potrebbero avere più dipendenza fra di loro. Per esempio::h]hbDa notare che presi due blocchi, questi potrebbero avere più dipendenza fra di loro. Per esempio:}(hjPhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM5hjhhubj)}(hQTASK A: read_lock(X); write_lock(Y); ... TASK B: write_lock(X); write_lock(Y);h]hQTASK A: read_lock(X); write_lock(Y); ... TASK B: write_lock(X); write_lock(Y);}hj^sbah}(h]h ]h"]h$]h&]hhuh1jhhhM8hjhhubh)}(hBNel grafo delle dipendenze avremo sia X -(SN)-> Y che X -(EN)-> Y.h]hBNel grafo delle dipendenze avremo sia X -(SN)-> Y che X -(EN)-> Y.}(hjlhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMChjhhubh)}(hpUsiamo -(xN)-> per rappresentare i rami sia per -(EN)-> che -(SN)->, allo stesso modo -(Ex)->, -(xR)-> e -(Sx)->h]hpUsiamo -(xN)-> per rappresentare i rami sia per -(EN)-> che -(SN)->, allo stesso modo -(Ex)->, -(xR)-> e -(Sx)->}(hjzhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMEhjhhubh)}(hXUn "percorso" in un grafo è una serie di nodi e degli archi che li congiungono. Definiamo un percorso "forte", come il percorso che non ha archi (dipendenze) di tipo -(xR)-> e -(Sx)->. In altre parole, un percorso "forte" è un percorso da un blocco ad un altro attraverso le varie dipendenze, e se sul percorso abbiamo X -> Y -> Z (dove X, Y, e Z sono blocchi), e da X a Y si ha una dipendenza -(SR)-> o -(ER)->, allora fra Y e Z non deve esserci una dipendenza -(SN)-> o -(SR)->.h]hXUn “percorso” in un grafo è una serie di nodi e degli archi che li congiungono. Definiamo un percorso “forte”, come il percorso che non ha archi (dipendenze) di tipo -(xR)-> e -(Sx)->. In altre parole, un percorso “forte” è un percorso da un blocco ad un altro attraverso le varie dipendenze, e se sul percorso abbiamo X -> Y -> Z (dove X, Y, e Z sono blocchi), e da X a Y si ha una dipendenza -(SR)-> o -(ER)->, allora fra Y e Z non deve esserci una dipendenza -(SN)-> o -(SR)->.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMHhjhhubh)}(hINella prossima sezione vedremo perché definiamo questo percorso "forte".h]hMNella prossima sezione vedremo perché definiamo questo percorso “forte”.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMOhjhhubeh}(h]#tipi-di-dipendenze-e-percorsi-fortiah ]h"]#tipi di dipendenze e percorsi fortiah$]h&]uh1hhhhhhhhM ubh)}(hhh](j)}(h.Identificazione di stalli da lettura ricorsivah]h.Identificazione di stalli da lettura ricorsiva}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhMRubh)}(h'Ora vogliamo dimostrare altre due cose:h]h'Ora vogliamo dimostrare altre due cose:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMShjhhubh)}(hLemma 1:h]hLemma 1:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMUhjhhubh)}(hSe esiste un percorso chiuso forte (ciclo forte), allora esiste anche una combinazione di sequenze di blocchi che causa uno stallo. In altre parole, l'esistenza di un ciclo forte è sufficiente alla scoperta di uno stallo.h]hSe esiste un percorso chiuso forte (ciclo forte), allora esiste anche una combinazione di sequenze di blocchi che causa uno stallo. In altre parole, l’esistenza di un ciclo forte è sufficiente alla scoperta di uno stallo.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMWhjhhubh)}(hLemma 2:h]hLemma 2:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM[hjhhubh)}(hSe non esiste un percorso chiuso forte (ciclo forte), allora non esiste una combinazione di sequenze di blocchi che causino uno stallo. In altre parole, i cicli forti sono necessari alla rilevazione degli stallo.h]hSe non esiste un percorso chiuso forte (ciclo forte), allora non esiste una combinazione di sequenze di blocchi che causino uno stallo. In altre parole, i cicli forti sono necessari alla rilevazione degli stallo.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM]hjhhubh)}(hXxCon questi due lemmi possiamo facilmente affermare che un percorso chiuso forte è sia sufficiente che necessario per avere gli stalli, dunque averli equivale alla possibilità di imbattersi concretamente in uno stallo. Un percorso chiuso forte significa che può causare stalli, per questo lo definiamo "forte", ma ci sono anche cicli di dipendenze che non causeranno stalli.h]hX|Con questi due lemmi possiamo facilmente affermare che un percorso chiuso forte è sia sufficiente che necessario per avere gli stalli, dunque averli equivale alla possibilità di imbattersi concretamente in uno stallo. Un percorso chiuso forte significa che può causare stalli, per questo lo definiamo “forte”, ma ci sono anche cicli di dipendenze che non causeranno stalli.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMahjhhubh)}(h'Dimostrazione di sufficienza (lemma 1):h]h'Dimostrazione di sufficienza (lemma 1):}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMghjhhubh)}(h$Immaginiamo d'avere un ciclo forte::h]h%Immaginiamo d’avere un ciclo forte:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMihjhhubj)}(hL1 -> L2 ... -> Ln -> L1h]hL1 -> L2 ... -> Ln -> L1}hj-sbah}(h]h ]h"]h$]h&]hhuh1jhhhMkhjhhubh)}(h5Questo significa che abbiamo le seguenti dipendenze::h]h4Questo significa che abbiamo le seguenti dipendenze:}(hj;hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMmhjhhubj)}(h/L1 -> L2 L2 -> L3 ... Ln-1 -> Ln Ln -> L1h]h/L1 -> L2 L2 -> L3 ... Ln-1 -> Ln Ln -> L1}hjIsbah}(h]h ]h"]h$]h&]hhuh1jhhhMohjhhubh)}(hUOra possiamo costruire una combinazione di sequenze di blocchi che causano lo stallo.h]hUOra possiamo costruire una combinazione di sequenze di blocchi che causano lo stallo.}(hjWhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMuhjhhubh)}(hPer prima cosa facciamo sì che un processo/processore prenda L1 in L1 -> L2, poi un altro prende L2 in L2 -> L3, e così via. Alla fine, tutti i Lx in Lx -> Lx+1 saranno trattenuti da processi/processori diversi.h]hPer prima cosa facciamo sì che un processo/processore prenda L1 in L1 -> L2, poi un altro prende L2 in L2 -> L3, e così via. Alla fine, tutti i Lx in Lx -> Lx+1 saranno trattenuti da processi/processori diversi.}(hjehhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMxhjhhubh)}(hXPoi visto che abbiamo L1 -> L2, chi trattiene L1 vorrà acquisire L2 in L1 -> L2, ma prima dovrà attendere che venga rilasciato da chi lo trattiene. Questo perché L2 è già trattenuto da un altro processo/processore, ed in più L1 -> L2 e L2 -> L3 non sono -(xR)-> né -(Sx)-> (la definizione di forte). Questo significa che L2 in L1 -> L2 non è un bloccatore non ricorsivo (bloccabile da chiunque), e L2 in L2 -> L3 non è uno scrittore (che blocca chiunque).h]hXPoi visto che abbiamo L1 -> L2, chi trattiene L1 vorrà acquisire L2 in L1 -> L2, ma prima dovrà attendere che venga rilasciato da chi lo trattiene. Questo perché L2 è già trattenuto da un altro processo/processore, ed in più L1 -> L2 e L2 -> L3 non sono -(xR)-> né -(Sx)-> (la definizione di forte). Questo significa che L2 in L1 -> L2 non è un bloccatore non ricorsivo (bloccabile da chiunque), e L2 in L2 -> L3 non è uno scrittore (che blocca chiunque).}(hjshhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM|hjhhubh)}(hXHIn aggiunta, possiamo trarre una simile conclusione per chi sta trattenendo L2: deve aspettare che L3 venga rilasciato, e così via. Ora possiamo dimostrare che chi trattiene Lx deve aspettare che Lx+1 venga rilasciato. Notiamo che Ln+1 è L1, dunque si è creato un ciclo dal quale non possiamo uscire, quindi si ha uno stallo.h]hXHIn aggiunta, possiamo trarre una simile conclusione per chi sta trattenendo L2: deve aspettare che L3 venga rilasciato, e così via. Ora possiamo dimostrare che chi trattiene Lx deve aspettare che Lx+1 venga rilasciato. Notiamo che Ln+1 è L1, dunque si è creato un ciclo dal quale non possiamo uscire, quindi si ha uno stallo.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubh)}(h)Dimostrazione della necessità (lemma 2):h]h)Dimostrazione della necessità (lemma 2):}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubh)}(hQuesto lemma equivale a dire che: se siamo in uno scenario di stallo, allora deve esiste un ciclo forte nel grafo delle dipendenze.h]hQuesto lemma equivale a dire che: se siamo in uno scenario di stallo, allora deve esiste un ciclo forte nel grafo delle dipendenze.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubh)}(hXSecondo Wikipedia[1], se c'è uno stallo, allora deve esserci un ciclo di attese, ovvero ci sono N processi/processori dove P1 aspetta un blocco trattenuto da P2, e P2 ne aspetta uno trattenuto da P3, ... e Pn attende che il blocco P1 venga rilasciato. Chiamiamo Lx il blocco che attende Px, quindi P1 aspetta L1 e trattiene Ln. Quindi avremo Ln -> L1 nel grafo delle dipendenze. Similarmente, nel grafo delle dipendenze avremo L1 -> L2, L2 -> L3, ..., Ln-1 -> Ln, il che significa che abbiamo un ciclo::h]hXSecondo Wikipedia[1], se c’è uno stallo, allora deve esserci un ciclo di attese, ovvero ci sono N processi/processori dove P1 aspetta un blocco trattenuto da P2, e P2 ne aspetta uno trattenuto da P3, ... e Pn attende che il blocco P1 venga rilasciato. Chiamiamo Lx il blocco che attende Px, quindi P1 aspetta L1 e trattiene Ln. Quindi avremo Ln -> L1 nel grafo delle dipendenze. Similarmente, nel grafo delle dipendenze avremo L1 -> L2, L2 -> L3, ..., Ln-1 -> Ln, il che significa che abbiamo un ciclo:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubj)}(hLn -> L1 -> L2 -> ... -> Lnh]hLn -> L1 -> L2 -> ... -> Ln}hjsbah}(h]h ]h"]h$]h&]hhuh1jhhhMhjhhubh)}(h,, ed ora dimostriamo d'avere un ciclo forte.h]h., ed ora dimostriamo d’avere un ciclo forte.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubh)}(hXPer un blocco Lx, il processo Px contribuisce alla dipendenza Lx-1 -> Lx e Px+1 contribuisce a quella Lx -> Lx+1. Visto che Px aspetta che Px+1 rilasci Lx, sarà impossibile che Lx in Px+1 sia un lettore e che Lx in Px sia un lettore ricorsivo. Questo perché i lettori (ricorsivi o meno) non bloccano lettori ricorsivi. Dunque, Lx-1 -> Lx e Lx -> Lx+1 non possono essere una coppia di -(xR)-> -(Sx)->. Questo è vero per ogni ciclo, dunque, questo è un ciclo forte.h]hXPer un blocco Lx, il processo Px contribuisce alla dipendenza Lx-1 -> Lx e Px+1 contribuisce a quella Lx -> Lx+1. Visto che Px aspetta che Px+1 rilasci Lx, sarà impossibile che Lx in Px+1 sia un lettore e che Lx in Px sia un lettore ricorsivo. Questo perché i lettori (ricorsivi o meno) non bloccano lettori ricorsivi. Dunque, Lx-1 -> Lx e Lx -> Lx+1 non possono essere una coppia di -(xR)-> -(Sx)->. Questo è vero per ogni ciclo, dunque, questo è un ciclo forte.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubeh}(h].identificazione-di-stalli-da-lettura-ricorsivaah ]h"].identificazione di stalli da lettura ricorsivaah$]h&]uh1hhhhhhhhMRubh)}(hhh](j)}(h Riferimentih]h Riferimenti}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhMubh)}(h7[1]: https://it.wikipedia.org/wiki/Stallo_(informatica)h](h[1]: }(hjhhhNhNubh reference)}(h1https://it.wikipedia.org/wiki/Stallo_(informaticah]h1https://it.wikipedia.org/wiki/Stallo_(informatica}(hjhhhNhNubah}(h]h ]h"]h$]h&]refurijuh1jhjubh)}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhjhhubh)}(hL[2]: Shibu, K. (2009). Intro To Embedded Systems (1st ed.). Tata McGraw-Hillh]hL[2]: Shibu, K. (2009). Intro To Embedded Systems (1st ed.). Tata McGraw-Hill}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubeh}(h] riferimentiah ]h"] riferimentiah$]h&]uh1hhhhhhhhMubeh}(h]3validatore-di-sincronizzazione-durante-l-esecuzioneah ]h"]3validatore di sincronizzazione durante l'esecuzioneah$]h&]uh1hhhhhhhhKubeh}(h]h ]h"]h$]h&]sourcehuh1hcurrent_sourceN current_lineNsettingsdocutils.frontendValues)}(hN generatorN datestampN source_linkN source_urlN toc_backlinksj(footnote_backlinksK sectnum_xformKstrip_commentsNstrip_elements_with_classesN strip_classesN report_levelK halt_levelKexit_status_levelKdebugNwarning_streamN tracebackinput_encoding utf-8-siginput_encoding_error_handlerstrictoutput_encodingutf-8output_encoding_error_handlerj_error_encodingutf-8error_encoding_error_handlerbackslashreplace language_codeenrecord_dependenciesNconfigN id_prefixhauto_id_prefixid dump_settingsNdump_internalsNdump_transformsNdump_pseudo_xmlNexpose_internalsNstrict_visitorN_disable_configN_sourceh _destinationN _config_files]7/var/lib/git/docbuild/linux/Documentation/docutils.confafile_insertion_enabled raw_enabledKline_length_limitM'pep_referencesN pep_base_urlhttps://peps.python.org/pep_file_url_templatepep-%04drfc_referencesN rfc_base_url&https://datatracker.ietf.org/doc/html/ tab_widthKtrim_footnote_reference_spacesyntax_highlightlong smart_quotessmartquotes_locales]character_level_inline_markupdoctitle_xform docinfo_xformKsectsubtitle_xform image_loadinglinkembed_stylesheetcloak_email_addressessection_self_linkenvNubreporterNindirect_targets]substitution_defs}substitution_names}refnames}1]jtasrefids}nameids}(j:j7jqjnjjj jjjjjjVjSjjjjj" j j5 j2 j j jjjjjjj2j/u nametypes}(j:jqjj jjjVjjj" j5 j jjjj2uh}(j7hjnjjjtjjjj jjjSjjjYj~jtjjj jj2 j% j j8 jj jjjjj/ju footnote_refs}j]jtas citation_refs} autofootnotes]autofootnote_refs]symbol_footnotes]symbol_footnote_refs] footnotes]ja citations]autofootnote_startKsymbol_footnote_startK id_counter collectionsCounter}jmKsRparse_messages]transform_messages] transformerN include_log];Documentation/translations/it_IT/locking/lockdep-design.rst(NNNNta decorationNhhub.