Stato macchine vs discussioni

Tutto ciò che fa un thread è un'operazione di interleave in modo che parti del processo sembrino sovrapporsi nel tempo. Una macchina single-core con più thread salta semplicemente intorno: esegue piccoli bit di codice da un thread, quindi passa a un altro thread. Un semplice programma di pianificazione decide quale thread ha la massima priorità e viene effettivamente eseguito nel core.

Su un computer single-core, niente accade effettivamente "allo stesso tempo". È solo un'esecuzione interlacciata.

Ci sono molti, molti modi per ottenere interleaving. Molti.

Supponiamo che tu abbia un semplice processo a due thread che utilizza un semplice blocco in modo che entrambi i thread possano scrivere su una variabile comune. Hai sei blocchi di codice.

• T1-prima del blocco
• T1-con blocco
• T1-dopo il blocco
• T2-prima del blocco
• T2-con blocco
• T2-dopo il blocco

[Questo può essere in loop o avere più lock o altro. Tutto ciò che fa è diventare più lungo, non più complesso.]

I passi di T1 devono essere eseguiti nell'ordine (T1-before, T1-con, T1-after) e i passi di T2 devono essere eseguiti nell'ordine (T2-before, T2-with, T2-after).

Oltre al vincolo "in-order", questi possono essere interfogliati in qualsiasi modo. Comunque. Potrebbero essere eseguiti come elencato sopra. Un altro ordine valido è (T1-before, T2-before, T2-lock, T1-lock, T2-after, T1-after). Ci sono molti ordini validi.

Attendere.

Questa è solo una macchina a stati con sei stati.

È un automa a stati finiti non deterministici. L'ordinamento degli stati T1-xxx con stati T2-xxx è indeterminato e non ha importanza. Quindi ci sono posti in cui il "prossimo stato" è un lancio di monete.

Ad esempio, quando inizia l'FSM, T1-before o T2-before sono entrambi i primi stati legittimi. Lancia una moneta.

Diciamo che è apparso T1-before. Fai quello. Quando ciò è fatto, c'è una scelta tra T1-with e T2-before. Lancia una moneta.

Ad ogni passo del FSM ci saranno due scelte (due discussioni - due scelte) e un lancio della moneta può determinare quale stato specifico è seguito.

La scrittura delle funzioni di blocco è per le persone che non possono creare macchine di stato;)

I thread sono utili se non puoi aggirare il blocco. Nessuna attività fondamentale del computer è veramente bloccante, è solo che molti di essi sono implementati in questo modo per facilità d'uso. Invece di restituire un carattere o "read failed", una funzione di lettura blocca fino a quando non viene letto l'intero buffer. Invece di verificare la presenza di un messaggio di ritorno in una coda e di tornare se non viene trovata alcuna, una funzione di connessione attende la risposta.

Non è possibile utilizzare le funzioni di blocco in una macchina a stati (almeno una che non può essere "bloccata").

E sì, l'utilizzo della macchina a stati è un'alternativa valida. Nei sistemi Real Time, questa è l'unica opzione, il sistema che fornisce un framework per la macchina. L'uso di thread e funzioni di blocco è semplicemente "la via più semplice", perché in genere una chiamata a una funzione di blocco sostituisce circa 3-4 stati nella macchina a stati.

How does one achieve multi-threading functionality in high-level language, such as Java, using only one thread and state machine? For example, what if there are 2 activities to perform (doing calculations and doing I/O) and one activity can block?

Quello che stai descrivendo è chiamato multitasking cooperativo , in cui ai task viene assegnata la CPU e ci si aspetta di abbandonarla volontariamente dopo un po 'di tempo o attività auto-determinati. Un'attività che non collabora continuando a utilizzare la CPU o bloccando le gengive su tutto il lavoro e senza avere un timer watchdog hardware, non c'è nulla che il codice che supervisiona le attività possa fare al riguardo.

Quello che vedi nei sistemi moderni è chiamato multitasking preventivo , che è dove le attività non devono rinunciare alla CPU perché il supervisore fa per loro quando arriva un interrupt generato dall'hardware. La routine di servizio di interrupt nel supervisore salva lo stato della CPU e la ripristina la volta successiva che l'attività è considerata meritevole di una porzione di tempo, quindi ripristina lo stato da qualsiasi attività da eseguire successivamente e torna indietro come se nulla fosse accaduto . Questa azione è chiamata switch di contesto e può essere costosa.

Is using "state-machine only" way viable alternative to multi-threading in high-level languages?

valida? Sicuro. Sane? Qualche volta. Sia che tu usi i thread o qualche forma di multitasking cooperativo fatto in casa (ad esempio, macchine di stato) dipende dai compromessi che sei disposto a fare.

I thread semplificano la progettazione delle attività fino al punto in cui è possibile trattare ciascuna di esse come il proprio programma che avviene per condividere lo spazio dati con altri. Questo ti dà la libertà di concentrarti sul lavoro a portata di mano e non su tutta la gestione e la manutenzione necessarie per farlo funzionare come un'iterazione alla volta. Ma dal momento che nessuna buona azione rimane impunita, si paga per tutta questa convenienza in switch di contesto. Avere molti thread che producono la CPU dopo aver fatto del lavoro minimo (volontariamente o facendo qualcosa che bloccherebbe, come I / O) può consumare molto tempo del processore facendo il cambio di contesto. Ciò è particolarmente vero se le operazioni di blocco raramente bloccano per molto tempo.

Ci sono alcune situazioni in cui la strada cooperativa ha più senso. Una volta dovevo scrivere un software per l'utente per un componente hardware che trasmetteva in streaming molti canali di dati attraverso un'interfaccia mappata in memoria che richiedeva il polling. Ogni canale era un oggetto costruito in modo tale che potessi lasciarlo girare come thread o eseguire ripetutamente un singolo ciclo di polling.

Le prestazioni della versione multithreaded non erano affatto buone proprio per la ragione che ho delineato sopra: ogni thread stava facendo un lavoro minimo e quindi produceva la CPU in modo che gli altri canali potessero avere un po 'di tempo, causando molti switch di contesto. Lasciare liberi i thread fino al momento in cui il preempted ha aiutato il throughput, ma alcuni canali non sono stati sottoposti a manutenzione prima che l'hardware subisse un sovraccarico del buffer perché non avevano ottenuto una porzione di tempo abbastanza presto.

La versione a thread singolo, che eseguiva anche iterazioni di ogni canale, funzionava come una scimmia scottata e il carico sul sistema cadeva come una roccia. La penalità che ho pagato per la prestazione aggiuntiva è stata dover gestire i compiti da solo. In questo caso, il codice per farlo era abbastanza semplice che il costo dello sviluppo e della manutenzione valeva il miglioramento delle prestazioni. Immagino che sia davvero la linea di fondo. Se i miei thread fossero rimasti in attesa di qualche chiamata di sistema da restituire, probabilmente l'esercizio non sarebbe valso la pena.

Questo mi porta al commento di Cox: i thread non sono esclusivamente per le persone che non possono scrivere macchine a stati. Alcuni sono abbastanza capaci di farlo, ma scelgono di usare una macchina a stati fissi (cioè un thread) nell'interesse di ottenere il lavoro prima o con meno complessità.

what if there are 2 activities to perform (doing calculations and doing I/O) and one activity can block?

Beh, onestamente non riesco a immaginare come gestire l'I / O di blocco senza thread. Si chiama blocking dopotutto solo perché il codice che la richiama deve wait .

Per mia lettura dell'email originale di Cox (sotto), egli sottolinea che il threading non si adatta bene. Voglio dire, cosa succede se ci sono 100 richieste di I / O? 1000? 10000? Cox sta facendo notare che avere un numero elevato di thread può portare a gravi problemi:

From: Alan Cox ([email protected])
Date: Fri Jan 21 2000 - 13:33:52 EST

the IBM paper), that if your application depends on huge numbers of threads, you're always going to keep bumping up against the scheduler? a lot of people throw lots of threads at a problem and it can really be bad design.

     

Questa è l'ultima delle tue preoccupazioni. 1000 thread è 8Mb di stack di kernel,   e abbastanza passaggi di compiti per essere sicuri che anche tu possa girare di più   della tua cache. Un computer è una macchina a stati. I thread sono per   persone che non possono programmare macchine di stato.

     

Ci sono molti casi in cui Linux non aiuta decisamente il   situazione in particolare blocco I / O asincrono.

     

Alan

source: Re: analisi interessante del threading del kernel linux da parte di IBM (linux- archivi della mailing list del kernel)

• In teoria, questo è vero. Nella vita reale, i thread sono solo un'astrazione efficiente usata per programmare una macchina di questo tipo. Sono così efficienti da poter essere utilizzati anche per programmare Statecharts e reti di Petri (cioè, comportamenti paralleli, in cui le macchine di stato sono fondamentalmente sequenziali).

• Il problema con le macchine a stati è l'esplosione combinatoria. Il numero di stati di un computer con 4G RAM è 2 ^ (2 ^ 32) stati (senza contare l'unità disco 2T).

• Per un uomo il cui unico strumento è un martello, ogni problema sembra un chiodo.

I thread sono l'unica opzione in due casi:

• per utilizzare più core senza separazione della memoria.
• per far fronte al codice esterno che blocca.

Il secondo è il motivo per cui la maggior parte della gente pensa che i thread siano inevitabili per fare IO o programmazione di rete, ma questo di solito è perché non sanno che il loro sistema operativo ha un'API più avanzata (o non vogliono combattere con l'utilizzo ).

Per quanto riguarda facilità d'uso e leggibilità, ci sono sempre loop di eventi (come libev o EventMachine ) che rendono la programmazione di una macchina a stati quasi come farlo con i thread, fornendo tuttavia un controllo sufficiente per dimenticare i problemi di sincronizzazione.

Un buon modo per ingannare il modo in cui le macchine a stati e il multithreading interagiscono è quello di esaminare i gestori di eventi GUI. Molte applicazioni / framework GUI utilizzano un singolo thread GUI che interrogherà le possibili fonti di input e chiamerà una funzione per ogni input ricevuto; in sostanza, questo potrebbe essere scritto come un enorme interruttore:

while (true) {
    switch (event) {
        case ButtonPressed:
        ...
        case MachineIsBurning:
        ....
    }
}

Ora, diventa chiaro abbastanza rapidamente che il livello di controllo di alto livello in questo costrutto non può essere elevato: il gestore di ButtonPressed deve terminare senza interazione dell'utente e tornare al ciclo principale, perché se non lo fa, no ulteriori eventi utente possono essere elaborati. Se ha uno stato da salvare, questo stato deve essere salvato in variabili globali o statiche, ma non nello stack; cioè, il normale flusso di controllo in un linguaggio imperativo è limitato. Sei essenzialmente limitato a una macchina a stati.

Questo può diventare piuttosto complicato quando si hanno subroutine annidate che devono salvare, ad esempio, un livello di ricorsione. O stai leggendo un file, ma il file non è al momento disponibile. O sono solo in un lungo computo. In tutti questi casi, diventa desiderabile salvare lo stato dell'esecuzione corrente e tornare al ciclo principale, e questo è il multithreading . Niente di più, niente di meno.

L'intera faccenda è diventata un po 'più complicata con l'introduzione del multithreading preventivo (cioè il sistema operativo che decide quando i thread devono fornire controllo), ed è per questo che la connessione non è immediatamente chiara oggi.

Quindi, per rispondere alla domanda finale: Sì, la macchina a stati è un'alternativa, la maggior parte delle GUI funzionano in questo modo con il thread della GUI. Basta non spingere la macchina a stati troppo lontano, diventa irraggiungibile molto rapidamente.

Chiedere se l'utilizzo di una macchina a stati sia fattibile in un linguaggio di alto livello è un po 'come chiedere se scrivere in assembler sia una valida alternativa all'utilizzo di un linguaggio di alto livello. Entrambi hanno il loro posto, data la situazione giusta.

L'astrazione dell'uso del thread rende più facili da implementare i sistemi paralleli più complessi, ma alla fine tutti i sistemi paralleli hanno gli stessi problemi avere a che fare con. Problemi classici come Deadlock / Livelock e inversione di priorità sono possibili con i sistemi basati sullo stato macchina come sono con un parallelo di memoria condivisa , < a href="http://en.wikipedia.org/wiki/Non-Uniform_Memory_Access"> NUMA o anche basato su CSP sistema, se è abbastanza complesso.

Non penso che lo sia - certo, le macchine di stato sono un concetto di calcolo molto 'elegante' ma, come dici tu, sono piuttosto complicate. E le cose complicate sono difficili da ottenere. E le cose che non vanno bene sono solo spezzate, quindi a meno che tu non sia un genio della presunta statura di Alan Cox, tieni duro con le cose che sai funziona - lascia la 'codifica intelligente' ai progetti di apprendimento.

Puoi dire quando qualcuno ha fatto il vano tentativo di farne uno, poiché (supponendo che funzioni bene) quando si tratta di mantenerlo, scopri che il compito è quasi impossibile. Il "genio" originale si è evoluto lasciandoti con il grumo di codice a malapena comprensibile (dato che questi tipi di sviluppatori non tendono a lasciare troppi commenti e tanto meno la documentazione tecnica).

In alcuni casi, una macchina a stati sarà una scelta migliore - sto pensando a cose di tipo embedded ora dove sono usati alcuni modelli di macchine a stati, e usati ripetutamente e in modo più formale (cioè una corretta progettazione :))

Anche il threading può essere difficile da ottenere, ma ci sono schemi per aiutarti - principalmente riducendo la necessità di condividere i dati tra i thread.

L'ultimo punto a riguardo è che i computer moderni funzionano su molti core in ogni caso, quindi una macchina a stati non si avvantaggerà delle risorse disponibili. Il threading può fare un lavoro migliore qui.

Un buon esempio di utilizzo corretto della macchina a stati invece dei thread: nginx vs apache2. In genere si può presumere che nginx gestisca tutte le connessioni in un thread, apache2 crea un thread per connessione.

Ma per me usare le macchine di stato vs i thread è abbastanza simile usando perfettamente asm vs java a mano: potresti ottenere risultati non leggibili, ma ci vogliono un sacco di sforzi dei programmatori, molta disciplina, rendere il progetto più complesso e meritevole se utilizzato da molti altri programmatori. Quindi, se sei tu quello che vuole creare un server web veloce, usa lo stato dei computer e l'IO asincrono. Se stai scrivendo il progetto (non la libreria da usare ovunque) usa i thread.