Esercizio - processori manager-worker, coda M/M/2 e compressione del registro

Questa pagina non ha ancora la versione ripasso: qui sotto c'è il testo completo.

Testo (approfondimento, "di telecomunicazioni e non di informatica"). Un'architettura manager-workers contiene otto unità logiche che generano indipendentemente lavori di calcolo, ciascuna secondo un processo di Poisson con intensità di $10$ lavori ogni millisecondo. I lavori sono inviati, attraverso un buffer FIFO, a una coppia di processori identici, ciascuno capace di eseguire $18$ miliardi di operazioni elementari al secondo. I lavori sono indirizzati indifferentemente al primo processore disponibile e ciascuno contiene un numero casuale di operazioni elementari, modellabile come variabile esponenziale di media $30\,000$ operazioni. Che sistema a coda è? È stabile? Qual è la probabilità che un lavoro trovi entrambi i processori disponibili? Qual è la probabilità che siano entrambi occupati? Un demone di gestione delle risorse controlla se i processori sono occupati e restituisce un valore nell'alfabeto $\{O,I,E,W\}$: $O$ se i processori sono entrambi inattivi, $I$ se ne è attivo uno solo, $E$ se sono entrambi attivi ma non ci sono lavori in coda, $W$ se sono entrambi occupati e ci sono anche lavori in coda. Un registro salva i valori calcolati dal demone ogni secondo per un giorno. Il registro ha capacità $8$ kilobyte. Si verifichi che, pur non essendo possibile salvare direttamente i valori di un giorno intero, ciò diventa possibile con una compressione senza perdita scelta opportunamente. Qual è la probabilità che, essendo nello stato $I$, sia occupato il processore $1$? Se $I$ si divide in due sottostati $I_1$ e $I_2$ (pedice = servitore occupato), basta ancora un registro da $8$ kilobyte?

Teoria usata: Processi di arrivo e processo di PoissonUn sistema a coda ha clienti che arrivano, un'area di attesa e $m$ servitori. Il processo di arrivo è un processo di punto con tempi di interarrivo $\tau_n=t_n-t_{n-1}$ e tasso $\lambda=\frac1{E[\tau]}$. Nel processo di Poisson omogeneo gli arrivi in intervalli disgiunti sono indipendenti e di Poisson con media $\lambda T$, gli interarrivi sono esponenziali $\lambda e^{-\lambda a}$ e senza memoria; somma di processi di Poisson è Poisson (tassi che si sommano), il diradamento con probabilità $p$ dà Poisson di tasso $p\lambda$; in $[0,h]$ c'è un arrivo con probabilità $\lambda h+o(h)$. Servizio con tasso $\mu=\frac1{E[y]}$; notazione di Kendall $A/B/m/K/N-S$.Processi di arrivo e processo di Poisson →, Sistemi a coda M-M-1 e M-M-mIn un sistema M/M/m (arrivi di Poisson $\lambda$, servizi esponenziali $\mu$, $m$ servitori) il numero di clienti $x(t)$ è una catena di Markov di nascita e morte con tassi di nascita $\lambda$ e di morte $\min(k,m)\mu$. A regime il bilancio di flusso $\lambda\pi_{k-1}=\min(k,m)\mu,\pi_k$ dà per M/M/1 $\pi_k=(1-\rho)\rho^k$ ($\rho=\frac\lambda\mu<1$), $E[x]=\frac\rho{1-\rho}$, $E[s]=\frac1{\mu-\lambda}$ (esponenziale), e per M/M/m la probabilità di accodamento di Erlang C, $C=P[x\ge m]$, con $E[q]=\frac{C,G}{m-G}$, $E[w]=\frac C{m\mu-\lambda}$, $E[s]=E[w]+\frac1\mu$ ($G=\frac\lambda\mu$, $\rho=\frac Gm<1$).Sistemi a coda M-M-1 e M-M-m →, Informazione, entropia e informazione mutuaL'informazione di un evento di probabilità $P$ è $i=\log_2\frac1P$ bit; l'entropia $H(x)=\sum p\log_2\frac1p$ è l'informazione media e misura l'incertezza: $0\le H\le\log_2M$, massimo se i simboli sono equiprobabili. Per due variabili: $\max{H(x),H(y)}\le H(x,y)\le H(x)+H(y)$, $H(x|y)=H(x,y)-H(y)$ e l'informazione mutua $I(x;y)=H(x)-H(x|y)=H(x)+H(y)-H(x,y)\ge0$ (zero se e solo se indipendenti). Per una sorgente di $F_s$ simboli/s: rate di informazione $F_sH_s$, rate nominale $F_s\log_2M$, efficienza $\eta=\frac{H_s}{\log_2M}$.Informazione, entropia e informazione mutua →, Codifica di sorgenteLa codifica di sorgente senza perdita assegna ai simboli (o a parole di $N$ simboli) parole di codice di lunghezza variabile, corte per i simboli probabili, con una mappa invertibile. Un codice a prefisso è sempre decodificabile; Kraft-McMillan: se il codice è decodificabile $\sum M^{-l_i}\le1$ e viceversa esiste un codice a prefisso con quelle lunghezze. Shannon: $L\ge\frac{H}{\log_2M}$ e esiste un codice con $L<\frac{H}{\log_2M}+1$ (lunghezze $\lceil\log_M\frac1p\rceil$). Shannon-Fano divide dall'alto, Huffman unisce dal basso i due meno probabili ed è ottimo; raggruppare simboli e la codifica aritmetica si avvicinano al limite.Codifica di sorgente →.

Il sistema a coda

Arrivi. Ogni unità: $10$ lavori/ms $=10^4$ lavori/s; $8$ unità indipendenti: per la sovrapposizione di processi di Poisson il flusso totale è di Poisson con $\lambda=8\cdot10^4$ lavori/s.

Servizio. Un processore esegue $18\cdot10^9$ operazioni/s; un lavoro ha in media $30\,000$ operazioni, quindi il tempo di servizio è esponenziale di media $\frac{30\,000}{18\cdot10^9}=1{,}667\ \mu$s e il tasso di servizio di un processore è $\mu=\frac{18\cdot10^9}{30\,000}=6\cdot10^5$ lavori/s.

Struttura. Un buffer FIFO unico alimenta due processori identici ("il primo disponibile"): arrivi di Poisson, servizio esponenziale, $m=2$ servitori, coda infinita, FCFS: M/M/2.

Stabilità. $\rho=\frac\lambda{m\mu}=\frac{8\cdot10^4}{2\cdot6\cdot10^5}=\frac{8\cdot10^4}{12\cdot10^5}=0{,}0667<1$: stabile. Il traffico offerto è $G=\frac\lambda\mu=\frac{8\cdot10^4}{6\cdot10^5}=0{,}1333$ (in media $0{,}13$ processori occupati).

Probabilità di stato

Per l'M/M/2 (Sistemi a coda M-M-1 e M-M-mIn un sistema M/M/m (arrivi di Poisson $\lambda$, servizi esponenziali $\mu$, $m$ servitori) il numero di clienti $x(t)$ è una catena di Markov di nascita e morte con tassi di nascita $\lambda$ e di morte $\min(k,m)\mu$. A regime il bilancio di flusso $\lambda\pi_{k-1}=\min(k,m)\mu,\pi_k$ dà per M/M/1 $\pi_k=(1-\rho)\rho^k$ ($\rho=\frac\lambda\mu<1$), $E[x]=\frac\rho{1-\rho}$, $E[s]=\frac1{\mu-\lambda}$ (esponenziale), e per M/M/m la probabilità di accodamento di Erlang C, $C=P[x\ge m]$, con $E[q]=\frac{C,G}{m-G}$, $E[w]=\frac C{m\mu-\lambda}$, $E[s]=E[w]+\frac1\mu$ ($G=\frac\lambda\mu$, $\rho=\frac Gm<1$).Sistemi a coda M-M-1 e M-M-m →, §5): $\pi_k=\frac{G^k}{k!}\pi_0$ per $k\le2$ e $\pi_k=\frac{G^2}2\rho^{k-2}\pi_0=2\rho^k\pi_0$ per $k\ge2$ (infatti $\frac{G^2}{2}=\frac{4\rho^2}2=2\rho^2$). La normalizzazione dà, per $m=2$, $$\pi_0=\left[1+2\rho+\frac{2\rho^2}{1-\rho}\right]^{-1}=\frac{1-\rho}{1+\rho}=\frac{0{,}9333}{1{,}0667}=0{,}875.$$ (Verifica: $1+2\rho+\frac{2\rho^2}{1-\rho}=\frac{(1+2\rho)(1-\rho)+2\rho^2}{1-\rho}=\frac{1+\rho}{1-\rho}$ ✓.) Quindi: $$\pi_1=2\rho\pi_0=0{,}1167,\qquad\pi_2=2\rho^2\pi_0=0{,}00778,\qquad P[x\ge3]=\frac{2\rho^3}{1-\rho}\pi_0=0{,}000556.$$

• Un lavoro trova entrambi i processori disponibili (sistema vuoto, PASTA): $\pi_0=\mathbf{0{,}875}$.
• Entrambi occupati: $P[x\ge2]=\frac{2\rho^2}{1-\rho}\pi_0=1-\pi_0-\pi_1=\mathbf{0{,}00833}$ (cioè $\frac1{120}$; è la probabilità di Erlang C, $C$).

Le quattro uscite del demone e la compressione

Il demone restituisce: $O$ se $x=0$, $I$ se $x=1$, $E$ se $x=2$ (due occupati, nessuno in coda), $W$ se $x\ge3$. Probabilità: $$P(O)=0{,}875,\quad P(I)=0{,}11667,\quad P(E)=0{,}007778,\quad P(W)=0{,}000556.$$ In un giorno il demone calcola $86\,400$ valori (uno al secondo). Con $4$ simboli servono $\lceil\log_24\rceil=2$ bit per simbolo: $2\cdot86\,400=172\,800$ bit $=21{,}6$ kilobyte (a $8$ bit/byte). Il registro da $8$ kilobyte ha $8\cdot1024\cdot8=65\,536$ bit (o $64\,000$ bit se $1$ kB $=1000$ byte): non basta. Ma i simboli sono molto sbilanciati: l'entropia è $$H=0{,}875\log_2\frac1{0{,}875}+0{,}1167\log_2\frac1{0{,}1167}+0{,}00778\log_2\frac1{0{,}00778}+0{,}000556\log_2\frac1{0{,}000556}=0{,}1686+0{,}3616+0{,}0545+0{,}0060=0{,}5907\ \text{bit/simbolo}.$$ Per il teorema di Shannon (Codifica di sorgenteLa codifica di sorgente senza perdita assegna ai simboli (o a parole di $N$ simboli) parole di codice di lunghezza variabile, corte per i simboli probabili, con una mappa invertibile. Un codice a prefisso è sempre decodificabile; Kraft-McMillan: se il codice è decodificabile $\sum M^{-l_i}\le1$ e viceversa esiste un codice a prefisso con quelle lunghezze. Shannon: $L\ge\frac{H}{\log_2M}$ e esiste un codice con $L<\frac{H}{\log_2M}+1$ (lunghezze $\lceil\log_M\frac1p\rceil$). Shannon-Fano divide dall'alto, Huffman unisce dal basso i due meno probabili ed è ottimo; raggruppare simboli e la codifica aritmetica si avvicinano al limite.Codifica di sorgente →) con una codifica senza perdita si possono ottenere $\tilde L$ vicini a $H$: $86\,400\cdot0{,}5907=51\,035$ bit, meno di $65\,536$ (e di $64\,000$): è possibile salvare l'intero giorno. I valori campionati a distanza di $1$ s si possono considerare indipendenti (il tempo di servizio è di $\mu$s: il sistema "dimentica" lo stato in un tempo brevissimo rispetto a $1$ s), quindi la sorgente si tratta come senza memoria.

Quale codice? Huffman simbolo per simbolo (lunghezze $1,2,3,3$): $\tilde L=0{,}875+0{,}2333+0{,}0233+0{,}0017=1{,}133$ bit, cioè $97\,920$ bit: non basta (non si migliora molto sul codice fisso a $2$ bit perché il simbolo più probabile non può costare meno di $1$ bit). Occorre raggruppare i simboli (Codifica di sorgenteLa codifica di sorgente senza perdita assegna ai simboli (o a parole di $N$ simboli) parole di codice di lunghezza variabile, corte per i simboli probabili, con una mappa invertibile. Un codice a prefisso è sempre decodificabile; Kraft-McMillan: se il codice è decodificabile $\sum M^{-l_i}\le1$ e viceversa esiste un codice a prefisso con quelle lunghezze. Shannon: $L\ge\frac{H}{\log_2M}$ e esiste un codice con $L<\frac{H}{\log_2M}+1$ (lunghezze $\lceil\log_M\frac1p\rceil$). Shannon-Fano divide dall'alto, Huffman unisce dal basso i due meno probabili ed è ottimo; raggruppare simboli e la codifica aritmetica si avvicinano al limite.Codifica di sorgente →, §8): con Huffman su coppie ($16$ parole) $\frac{\tilde L}N=0{,}715$ bit/simbolo, cioè $61\,790$ bit $<65\,536$ ✓ (e $<64\,000$ ✓); con terne $0{,}622$ bit/simbolo ($53\,778$ bit); con blocchi di $5$ simboli $0{,}595$ ($51\,397$ bit, molto vicino al limite $51\,035$). La codifica aritmetica darebbe praticamente $H$.

Il sottostato $I_1$, $I_2$

Se i lavori vanno "indifferentemente" al primo processore libero, i due processori sono equivalenti e per simmetria $$P[\text{processore 1 occupato}\mid I]=\frac12.$$ Con la suddivisione $I\to\{I_1,I_2\}$ i simboli diventano $5$: $P(I_1)=P(I_2)=\frac{0{,}11667}2=0{,}05833$. La nuova entropia è $H'=H+P(I)\cdot1\ \text{bit}=0{,}5907+0{,}1167=0{,}7073$ bit/simbolo (la scelta tra $I_1$ e $I_2$ aggiunge $1$ bit di informazione ogni volta che si è in $I$). Totale giornaliero con un codice ideale: $0{,}7073\cdot86\,400=61\,115$ bit $<65\,536$ (e $<64\,000$): basta ancora il registro da $8$ kB, ma con meno margine: con Huffman su blocchi servono almeno terne ($0{,}739$ bit/simbolo, $63\,852$ bit; con coppie $0{,}821$ bit/simbolo, $70\,951$ bit, non basta). Il margine si assottiglia: $61\,115$ bit sono il $93\%$ della capacità del registro, contro il $78\%$ del caso precedente.