Come creare un simulatore per algoritmi distribuiti scritti in un linguaggio semplice

4

Ho iniziato lo sviluppo del simulatore per la simulazione di algoritmi distribuiti in linguaggio C . Il mio lavoro consiste nella creazione di linguaggio semplice per la descrizione dell'algoritmo e simulatore che accetta l'algoritmo descritto e lo simula.

All'inizio ho deciso come rappresentare l'ambiente distribuito. Questo simulatore verrà eseguito su una singola macchina, quindi è necessario simulare in qualche modo le entità che creano l'ambiente distribuito e svolgere alcune attività in base all'algoritmo fornito. Ogni entità verrà rappresentata come struttura dati chiamata Entità . Questa struttura dati conterrà tutti i dati relativi all'entità, ad esempio lo stato dell'entità, i registri locali dell'entità.

Per rappresentare la topologia e le connessioni, voglio utilizzare una libreria per i grafici in C per rappresentare la topologia come set di vertici e bordi . Questi vertici e spigoli faranno sicuramente parte di Entità in modo che possa ottenere l'accesso ai suoi vicini, ad esempio, quando sta inviando loro dati.

Il passo successivo era creare un linguaggio semplice in modo che l'utente potesse facilmente descrivere l'algoritmo e simularlo.

Per una migliore rappresentazione ecco l'esempio di flooding dell'algoritmo.

STATUS = INITIATOR, IDLE, DONE;
INIT = INITIATOR, IDLE;
TERM = DONE;
REGISTERS = ;

INITIATOR
  RANDOM
    begin
      SEND(x, NEIGHBORS);
      BECAME(DONE);
    end

IDLE
  RECEIVE(x)
    begin
      SEND(x, NEIGHBORS - SENDER)
      BECAME(DONE);
    end

In questa fase sto lavorando alle specifiche per questa lingua e mi sono bloccato. Non sono sicuro di come specificare correttamente questa lingua. Dovrebbe essere semplice, ma quando per esempio voglio implementare il comando per inviare un messaggio ad un'altra entità, devo considerare che gli obiettivi possono essere diversi. I target potrebbero essere tutti i vicini o tutti i vicini tranne mittente o forse solo mittente o successivamente in fase di sviluppo, dovendo possibile dichiarare un target specifico da tutte le entità dell'ambiente.

A questo punto ho due opzioni in mente.

Prima utilizza Flex e Bison per analizzare e analizzare l'input. quindi raccogli tutti i dati necessari ed esegui i thread e lascia che si comportino secondo tutti i comportamenti possibili nel file di input con l'algoritmo.

La seconda opzione non è usare Flex e Bison e implementare ogni comando come Macro C . L'utente utilizzerà queste macro per scrivere il file di input con l'algoritmo e questo file sarà collegato al simulatore con gcc compiler , quindi quando l'utente utilizza la macro in modo errato il compilatore genererà un errore.

Vorrei chiedere se qualcuno stava sviluppando qualcosa di simile o quale tipo di approccio o tecnica scegliere se esiste. Voglio implementarlo in C ma forse un altro linguaggio sarebbe migliore per questo tipo di cose.

    
posta M.Puk 10.03.2017 - 18:32
fonte

3 risposte

2

Perché dovresti usare il linguaggio di livello più basso possibile, C, per un'attività implicata come questa? O, piuttosto, diversi compiti?

Se avessi bisogno di risultati in modo rapido e indolore, prenderei uno strumento appositamente creato, come Erlang o Elixir, per eseguire un sistema distribuito. Aspetti positivi: vengono utilizzati in sistemi distribuiti reali, consentono pazzie di parallelismo anche su una singola scatola e dispongono di strumenti di tracciamento / diagnostica / introspezione per osservare realmente ciò che accade.

Scrivi le funzioni di Erlang che mappano più o meno direttamente agli elementi della tua lingua di input e puoi iniziare a giocare con i sistemi anche senza parser.

Se vuoi ottenere prestazioni in qualche modo maggiori al costo di un linguaggio significativamente meno espressivo, ma comunque facile, dai un'occhiata a Go. Gestisce la concorrenza senza problemi.

Anche scrivere un parser in C mi sembra controproducente. Un linguaggio di livello superiore, come Python o Ruby o anche Java o Haskell, aiuta a farlo più velocemente e in modo più conveniente. Definire un parser usando e.p. il pyparsing e la compilazione del tuo linguaggio di input in Elixir o in Erlang dovrebbe essere abbastanza semplice e molto più facile di fare qualcosa di simile in C.

Ciò a cui l'approccio a più livelli sarebbe d'aiuto consiste nel fare una piccola cosa ben definita alla volta. (Un tentativo di fare tutto in una volta è sicuramente un modo per fallire, lo sai.)

    
risposta data 10.03.2017 - 20:21
fonte
1

Se non sei sicuro di doverci un vero generatore di parser, dovresti usarlo. Evita solo i generatori di parser reali come Flex e Bison se sei assolutamente positivo di non averne bisogno.

Ogni lingua che scrivi come questa cresce. È la natura del compito a portata di mano. La tua lingua crescerà. Quando cresce, se si usano macro C, si dovrà adattare tale crescita alla sintassi generale del linguaggio C. Se cresce con Flex o Bison hai generatori di parser che sono letteralmente progettati per aiutarti con questo tipo di crescita.

Inoltre, se qualcuno rovina una macro C, i messaggi di errore possono essere orrendi e incomprensibili.

Inoltre, se hai una grammatica linguistica a portata di mano, sei un passo più vicino a consentire soluzioni come uno script Python che genera contenuti nella tua lingua.

Gli unici casi che utilizzerei personalmente il linguaggio in stile macro C sarebbero:

  • Se dovessi interagire direttamente con il codice (ad esempio ottenere i puntatori ai membri e così via), e per qualche ragione non potrei usare un approccio più robusto come la riflessione per esporre quei membri
  • Stavo lavorando su una macchina embedded dove ogni singolo byte è importante.

Inoltre, lo userei solo se fosse positivo che io fossi al 100% a posto con ogni utente del mio software che deve compilare il codice per usare il mio simulatore.

Se vuoi davvero sfruttare la potenza del preprocessore C, ci sono grammatiche complete che faranno il passo del preprocessore per te e poi ti permetteranno di usare lexx / bison / antlr / flex per elaborare i risultati.

    
risposta data 10.03.2017 - 18:49
fonte
0

promela e gira se il punto è effettivamente verificarlo. questi sono strumenti di simulazione del protocollo.

    
risposta data 10.03.2017 - 20:39
fonte

Leggi altre domande sui tag