<?xml version="1.0" encoding="UTF-8"?>
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:wx="http://ilps.science.uva.nl/WikiXML/wx" xml:lang="it" lang="it">
<head>
<title>Algoritmo del fornaio</title>
<meta name="wx_namespace" content="0"/>
<meta name="wx_pagename" content="Algoritmo_del_fornaio"/>
<meta name="wx_page_id" content="282906"/>
</head>
<body>
<div id="wx_article">
<wx:section level="1" title="Algoritmo del fornaio" id="wxsec1"><h1 class="pagetitle" id="wx1">Algoritmo del fornaio</h1>

<p id="wx2">L'<b id="wx3"><a href="/wit/Algoritmo" title="Algoritmo" wx:linktype="known" wx:pagename="Algoritmo" wx:page_id="16" id="wx4">algoritmo</a> del fornaio</b> è uno dei metodi di <a href="/wit/Mutua_esclusione" title="Mutua esclusione" wx:linktype="known" wx:pagename="Mutua_esclusione" wx:page_id="271992" id="wx5">mutua esclusione</a> che trovano applicazione pratica nella <a href="/wit/Programmazione" title="Programmazione" wx:linktype="known" wx:pagename="Programmazione" wx:page_id="791962" id="wx6">programmazione</a> parallela per serializzare l'esecuzione delle <a href="/wit/Sezione_critica" title="Sezione critica" wx:linktype="known" wx:pagename="Sezione_critica" wx:page_id="107234" id="wx7">sezioni critiche</a> da parte di più <a href="/wit/Processo_%28informatica%29" title="Processo (informatica)" wx:linktype="known" wx:pagename="Processo_(informatica)" wx:page_id="27361" id="wx8">processi</a> o <a href="/wit/Thread" title="Thread" wx:linktype="known" wx:pagename="Thread" wx:page_id="93142" id="wx9">thread</a> concorrenti.</p>

<p id="wx10">L'algoritmo deve il nome al suo inventore Lesley Lamport, che propose l'analogia con il modello reale di una frequentata panetteria, dove i clienti strappano un numero prima di mettersi in fila ad aspettare il proprio turno. I clienti del fornaio rappresentano i task in attesa del proprio turno per eseguire la sezione critica.</p>

<div id="wx_toc"/>

<a id="Schema" name="Schema"/>
<wx:section level="2" title="Schema" id="wxsec2"><h2 id="wx11">Schema</h2>

<p id="wx12">Quella che segue è una descrizione schematica dell'algoritmo in <a href="/wit/Pseudocodice" title="Pseudocodice" wx:linktype="known" wx:pagename="Pseudocodice" wx:page_id="61702" id="wx13">pseudocodice</a> <a href="/wit/C%2B%2B" title="C++" wx:linktype="known" wx:pagename="C++" wx:page_id="26839" id="wx14">C++</a>:</p>

<pre id="wx15">
// dichiarazione delle variabili globali comuni
bool sceglie[N] = {false}; // N costante
int numero[N] = {0};

int i; // indice del thread in esecuzione
// ...
for (;;) {
    sceglie[i] = true;
    numero[i] = 1 + max(numero[0], numero[1], ..., numero[N - 1]);
    sceglie[i] = false;
    for (j = 0; j &lt; N; ++j) {
        while (sceglie[j]);
        while (
            (numero[j] != 0) &amp;&amp;
            (
             (numero[j] &lt; numero[i]) ||
             ((numero[j] == numero[i]) &amp;&amp; (j &lt; i))
            )
        );
    }
    // &lt;sezione critica&gt;
    numero[i] = 0;
    // &lt;sezione non critica&gt;
}
</pre>

<a id="Funzionamento" name="Funzionamento"/>
</wx:section><wx:section level="2" title="Funzionamento" id="wxsec3"><h2 id="wx16">Funzionamento</h2>

<p id="wx17">Al di là di ogni affinità con le situazioni reali, è possibile che più thread ricevano lo stesso numero di turno. Per ovviare a questa circostanza si introduce l'indice del thread come secondo argomento di confronto. Se più thread ricevono lo stesso numero di turno, si conviene di assegnare la precedenza al thread con l'indice più basso. Va notato che l'indice di ciascun thread deve essere unico: esso può venire assegnato al momento della creazione o passato come <a href="/wit/Parametro_%28informatica%29" title="Parametro (informatica)" wx:linktype="known" wx:pagename="Parametro_(informatica)" wx:page_id="235286" id="wx18">parametro</a>. Nell'esempio schematico riportato sopra, la costante <tt id="wx19">N</tt> rappresenta il numero massimo di thread concorrenti. Dopo aver ricevuto il suo indice unico, ogni thread scrive solo nelle sue slot (<tt id="wx20">sceglie[i]</tt> e <tt id="wx21">numero[i]</tt>). La serializzazione è assicurata dalle due <a href="/wit/Iterazione" title="Iterazione" wx:linktype="known" wx:pagename="Iterazione" wx:page_id="98878" id="wx22">iterazioni</a> while consecutive. Questi cicli vengono ripetuti da ogni thread per tutti i thread, incluso quello in esecuzione e i thread non attivi. Solo quando non ci sono più altri thread con priorità più alta è possibile l'accesso alla sezione critica.</p>

<a id="Considerazioni" name="Considerazioni"/>
</wx:section><wx:section level="2" title="Considerazioni" id="wxsec4"><h2 id="wx23">Considerazioni</h2>

<p id="wx24">L'algoritmo del fornaio garantisce che un solo thread alla volta possa accedere alla sezione critica, indipendentemente dall'ordine delle <a href="/wit/Commutazione_di_contesto" title="Commutazione di contesto" wx:linktype="known" wx:pagename="Commutazione_di_contesto" wx:page_id="122062" id="wx25">commutazioni di contesto</a> e dagli altri dettagli dello scheduling. Sussiste tuttavia il principale inconveniente che è proprio di tutti gli algoritmi di coordinazione decentrata, cioè non coordinata dallo <a href="/wit/Scheduler" title="Scheduler" wx:linktype="known" wx:pagename="Scheduler" wx:page_id="1474472" id="wx26">scheduler</a>: i task in attesa continuano ad utilizzare il processore in un ciclo di attesa attiva detto <i id="wx27">busy waiting</i>, rallentando così gli altri thread nel sistema.</p>

<a id="Voci_correlate" name="Voci_correlate"/>
</wx:section><wx:section level="2" title="Voci correlate" id="wxsec5"><h2 id="wx28">Voci correlate</h2>

<ul id="wx29">
<li id="wx30"><a href="/wit/Algoritmo_di_Dekker" title="Algoritmo di Dekker" wx:linktype="known" wx:pagename="Algoritmo_di_Dekker" wx:page_id="276077" id="wx31">Algoritmo di Dekker</a></li>

<li id="wx32"><a href="/wit/Algoritmo_di_Peterson" title="Algoritmo di Peterson" wx:linktype="known" wx:pagename="Algoritmo_di_Peterson" wx:page_id="276086" id="wx33">Algoritmo di Peterson</a></li>
</ul>
</wx:section></wx:section></div>
<div id="wx_categorylinks">
<a href="/wit/index.php?title=Speciale:Categories&amp;article=Algoritmo_del_fornaio" title="Speciale:Categories" wx:linktype="known" wx:pagename="Speciale:Categories" id="wx34">Categoria</a>: <span dir="ltr" id="wx35"><a href="/wit/Categoria:Algoritmi_di_mutua_esclusione" title="Categoria:Algoritmi di mutua esclusione" wx:linktype="known" wx:pagename="Categoria:Algoritmi_di_mutua_esclusione" wx:page_id="282909" id="wx36">Algoritmi di mutua esclusione</a></span></div>
<div id="wx_languagelinks">
Altre lingue: <a href="http://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithm" class="external" wx:linktype="interwiki" wx:pagename="en:Lamport's_bakery_algorithm" id="wx37">English</a> | <a href="http://es.wikipedia.org/wiki/Algoritmo_de_la_panader%C3%ADa_de_Lamport" class="external" wx:linktype="interwiki" wx:pagename="es:Algoritmo_de_la_panadería_de_Lamport" id="wx38">Español</a> | <a href="http://fr.wikipedia.org/wiki/Algorithme_de_la_boulangerie" class="external" wx:linktype="interwiki" wx:pagename="fr:Algorithme_de_la_boulangerie" id="wx39">Français</a> | <a href="http://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%9D%E3%83%BC%E3%83%88%E3%81%AE%E3%83%91%E3%83%B3%E5%B1%8B%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0" class="external" wx:linktype="interwiki" wx:pagename="ja:ランポートのパン屋のアルゴリズム" id="wx40">日本語</a> | <a href="http://pl.wikipedia.org/wiki/Algorytm_piekarniany" class="external" wx:linktype="interwiki" wx:pagename="pl:Algorytm_piekarniany" id="wx41">Polski</a></div>
</body>
</html>
