Scheduling
Da Tesine Linguaggi e Traduttori.
INTRODUZIONE
L'obiettivo del progetto è quello di offrire agli utenti uno strumento che permetta di verificare l'ordine di scheduling di processi su un sistema monoprocessore in base a algoritmi definiti dall'utente stesso.
Il software, dato un file di ingresso contenente determinate informazioni sull'algoritmo e sui processi, produce in output:
* il diagramma di Gantt raffigurante l'ordine di esecuzione dei processi * una versione testuale dello stesso diagramma contenente informazioni aggiuntive
DESCRIZIONE DEL LINGUAGGIO DI INPUT
Il file di ingresso è suddiviso in due sezioni:
* sezione configurazione parametri dell'algoritmo di scheduling * sezione definizione caratteristiche dei processi e del tempo di simulazione
Le due sezioni sono separate da uno o più “%” e ogni riga è terminata con il carattere “;”.
E' possibile inserire in ogni sezione dei commenti nel formato /* */.
Il linguaggio è case insensitive.
Formato Sezione Algoritmo
La prima sezione definisce i parametri di con i quali vengono eseguiti i processi.
Un parametro di schedulazione è scritto nel modo seguente:
- @nomeparametro=<valore>;
I parametri possono essere inseriti in ordine casuale e devono comparire tutti una volta.
I termini da configurare sono i seguenti:
- param: parametro sulla base del quale viene effettuata la schedulazione
Valori configurabili:
* execution: la scelta del processo da eseguire è effettuata in base al tempo di esecuzione * arrival: la scelta del processo da eseguire è effettuata in base al tempo di arrivo * rate: la scelta del processo da eseguire è effettuata in base al periodo * dead: la scelta del processo da eseguire è effettuata in base alla deadline
- sort: indica il criterio dell'ordinamento
Valori configurabili:
* max: l'ordinamento è effettuato in base al valore maggiore * min: l'ordinamento è effettuato in base al valore minore
- quantum: indica il quanto di tempo in cui viene suddivisa l’esecuzione sul processore.
Valori configurabili:
* <valore_numerico> * infinite: l'algoritmo non prevede l'utilizzo del quanto di tempo
- preempt: indica se l'algoritmo di schedulazione utilizza la preemption.
Valori configurabili:
* <valore_booleano> N.B: con alcuni algoritmi la preemption non ha significato e viene dunque segnalao un errore semantico.
Formato Sezione Caratteristiche Processi
La seconda sezione è costituita da un'intestazione e dalla lista dei processi con le relative caratteristiche. Il numero di processi è variabile.
Esempio:
NAME RT ET DL AT;
P1 12 10 NO 4;
P2 5 4 NO 2;
P3 5 4 NO 2;
P4 20 5 NO 0;
MaxTime = 60;
- NAME: nome del processo costituito da caratteri alfanumerici
- RT: (Rate) periodo del processo, valori ammissibili: numero / NO
- ET: (Execution Time) tempo di esecuzione del processo, valori ammissibili: numero
- DL: (Deadline) scadenza del processo, valori ammissibili: numero / NO
- AT: (Arrival Time) tempo di arrivo del processo, valori ammissibili: numero
- MaxTime: durata della simulazione, valori ammissibili: numero
DESCRIZIONE DELL'OUTPUT
Il programma fornisce in output il diagramma di Gantt dell'ordine di schedulazione:
- quando un processo è in esecuzione l'istante di tempo ad esso associato è rappresentato da una X;
- quando è in ready queue l'istante di tempo è rappresentato da una r;
- quando il processo non è in esecuzione e non è presente nella ready queue l'istante di tempo è rappresentato da _.
Inoltre viene visualizzata un'altra rappresentazione testuale di tale diagramma dove viene evidenziato l'istante di tempo in cui viene eseguito processo e l'intervallo di tempo di esecuzione rimanente.
ESEMPI
Esempio algoritmo FIFO (First In First Out)
INPUT:
@sort = min; @param = arrival; @quantum = infinite; @preempt = false; %%%%%%% Name Rt eT DL AT; P1 8 3 NO 3; P2 15 7 NO 0; P3 20 5 NO 0; MaxTime = 30;
OUTPUT:
******************************************************************************* [INFO] Gantt: INIZIO PROCESSO DI PARSING ******************************************************************************* Process P1 has exceeded DeadLine Gantt Diagram @sort = min @quantum = infinite @param = Arrival Max time = 30 Algoritmo di scheduling: FIFO P1: ___rrrrr P2: XXXXXXX_ P3: rrrrrrrX
Esempio di algoritmo FIFO (First In First Out)
INPUT:
@sort = min; @param = arrival; @quantum = infinite; @preempt = false; %%%%%%% Name Rt eT DL AT; P1 15 3 NO 0; P2 15 7 NO 2; P3 20 5 NO 0; P4 NO 3 20 5; MaxTime = 30;
OUTPUT:
******************************************************************************* [INFO] Gantt: INIZIO PROCESSO DI PARSING ******************************************************************************* Gantt Diagram @sort = min @quantum = infinite @param = Arrival Max time = 30 Algoritmo di scheduling: FIFO P1: XXX____________rrrXXX_________ P2: __rrrrrrXXXXXXX__rrrrXXXXXXX__ P3: rrrXXXXX____________rrrrrrrrXX P4: _____rrrrrrrrrrXXX____________ 0 - P1 (2) 1 - P1 (1) 2 - P1 (0) 3 - P3 (4) 4 - P3 (3) 5 - P3 (2) 6 - P3 (1) 7 - P3 (0) 8 - P2 (6) 9 - P2 (5) 10 - P2 (4) 11 - P2 (3) 12 - P2 (2) 13 - P2 (1) 14 - P2 (0) 15 - P4 (2) 16 - P4 (1) 17 - P4 (0) 18 - P1 (2) 19 - P1 (1) 20 - P1 (0) 21 - P2 (6) 22 - P2 (5) 23 - P2 (4) 24 - P2 (3) 25 - P2 (2) 26 - P2 (1) 27 - P2 (0) 28 - P3 (4) 29 - P3 (3)
Esempio algoritmo ROUND ROBIN
INPUT:
@sort = min; @param = arrival; @quantum = 3; @preempt = false; %%%%%%% NAME RT ET DL AT; P1 15 3 NO 0; P2 15 7 NO 2; P3 20 5 NO 0; MaxTime = 30;
OUTPUT:
******************************************************************************* [INFO] Gantt: INIZIO PROCESSO DI PARSING ******************************************************************************* Gantt Diagram @sort = min @quantum = 3 @param = Arrival Max time = 30 Algoritmo di scheduling: ROUND ROBIN P1: XXX____________XXX____________ P2: __rrrrXXXrrXXXX__rXXXrrrXXXrrX P3: rrrXXXrrrXX_________rXXXrrrXX_ 0 - P1 (2) 1 - P1 (1) 2 - P1 (0) 3 - P3 (4) 4 - P3 (3) 5 - P3 (2) 6 - P2 (6) 7 - P2 (5) 8 - P2 (4) 9 - P3 (1) 10 - P3 (0) 11 - P2 (3) 12 - P2 (2) 13 - P2 (1) 14 - P2 (0) 15 - P1 (2) 16 - P1 (1) 17 - P1 (0) 18 - P2 (6) 19 - P2 (5) 20 - P2 (4) 21 - P3 (4) 22 - P3 (3) 23 - P3 (2) 24 - P2 (3) 25 - P2 (2) 26 - P2 (1) 27 - P3 (1) 28 - P3 (0) 29 - P2 (0)
Esempio algoritmo ROUND ROBIN puntuale
INPUT:
@sort = min; @param = arrival; @quantum = 3; @preempt = false; %%%%%%% Name Rt eT DL AT; P1 NO 5 NO 1; P2 NO 7 NO 2; P3 NO 10 NO 1; MaxTime = 30;
OUTPUT:
******************************************************************************* [INFO] Gantt: INIZIO PROCESSO DI PARSING ******************************************************************************* Gantt Diagram @sort = min @quantum = 3 @param = Arrival Max time = 30 Algoritmo di scheduling: ROUND ROBIN P1: _XXXrrrrrrXX__________________ P2: __rrrrrXXXrrrrrXXXrrrX________ P3: _rrrXXXrrrrrXXXrrrXXXrX_______ 0 - IDLE 1 - P1 (4) 2 - P1 (3) 3 - P1 (2) 4 - P3 (9) 5 - P3 (8) 6 - P3 (7) 7 - P2 (6) 8 - P2 (5) 9 - P2 (4) 10 - P1 (1) 11 - P1 (0) 12 - P3 (6) 13 - P3 (5) 14 - P3 (4) 15 - P2 (3) 16 - P2 (2) 17 - P2 (1) 18 - P3 (3) 19 - P3 (2) 20 - P3 (1) 21 - P2 (0) 22 - P3 (0) 23 - IDLE 24 - IDLE 25 - IDLE 26 - IDLE 27 - IDLE 28 - IDLE 29 - IDLE
Esempio algoritmo SJF (Shortest Job First)
INPUT:
@sort = min; @param = execution; @quantum = infinite; @preempt = true; %%%%%%% Name Rt eT DL AT; P1 10 4 NO 0; P2 15 5 NO 2; P3 20 6 NO 1; P4 NO 6 30 4; MaxTime = 30;
OUTPUT:
******************************************************************************* [INFO] Gantt: INIZIO PROCESSO DI PARSING ******************************************************************************* Gantt Diagram @sort = min @quantum = infinite @param = ExecutionTime Max time = 30 Algoritmo di scheduling: SJF P1: XXXX______XXXX______rrrrXXXX__ P2: __rrXXXXX________rrXXXXX______ P3: _rrrrrrrrXrrrrXXXXX__rrrrrrrrr P4: ____rrrrrrrrrrrrrrrrrrrrrrrrXX 0 - P1 (3) 1 - P1 (2) 2 - P1 (1) 3 - P1 (0) 4 - P2 (4) 5 - P2 (3) 6 - P2 (2) 7 - P2 (1) 8 - P2 (0) 9 - P3 (5) 10 - P1 (3) 11 - P1 (2) 12 - P1 (1) 13 - P1 (0) 14 - P3 (4) 15 - P3 (3) 16 - P3 (2) 17 - P3 (1) 18 - P3 (0) 19 - P2 (4) 20 - P2 (3) 21 - P2 (2) 22 - P2 (1) 23 - P2 (0) 24 - P1 (3) 25 - P1 (2) 26 - P1 (1) 27 - P1 (0) 28 - P4 (5) 29 - P4 (4)
Esempio algoritmo RMS (Rate Monotonic Scheduling)
INPUT:
@sort = min; @param = rate; @quantum = infinite; @preempt = true; %%%%%%% Name Rt eT DL AT; P1 15 3 NO 0; P2 15 7 NO 2; P3 20 5 NO 0; MaxTime = 30;
OUTPUT:
******************************************************************************* [INFO] Gantt: INIZIO PROCESSO DI PARSING ******************************************************************************* Gantt Diagram @sort = min @quantum = infinite @param = Rate Max time = 30 Algoritmo di scheduling: RMS P1: XXX____________XXX____________ P2: __rXXXXXXX_______rXXXXXXX_____ P3: rrrrrrrrrrXXXXX_____rrrrrXXXXX 0 - P1 (2) 1 - P1 (1) 2 - P1 (0) 3 - P2 (6) 4 - P2 (5) 5 - P2 (4) 6 - P2 (3) 7 - P2 (2) 8 - P2 (1) 9 - P2 (0) 10 - P3 (4) 11 - P3 (3) 12 - P3 (2) 13 - P3 (1) 14 - P3 (0) 15 - P1 (2) 16 - P1 (1) 17 - P1 (0) 18 - P2 (6) 19 - P2 (5) 20 - P2 (4) 21 - P2 (3) 22 - P2 (2) 23 - P2 (1) 24 - P2 (0) 25 - P3 (4) 26 - P3 (3) 27 - P3 (2) 28 - P3 (1) 29 - P3 (0)
Esempio algoritmo EDF (Earliest Deadline First)
INPUT:
@sort = min; @param = dead; @quantum = infinite; @preempt = true; %%%%%%% Name Rt eT DL AT; P1 16 3 NO 3; P2 15 7 NO 0; P3 NO 5 10 2; MaxTime = 30;
OUTPUT:
******************************************************************************* [INFO] Gantt: INIZIO PROCESSO DI PARSING ******************************************************************************* Gantt Diagram @sort = min @quantum = infinite @param = DeadLine Max time = 30 Algoritmo di scheduling: EDF P1: ___rrrrrrrrrXXX____rrrXXX_____ P2: XXrrrrrXXXXX___XXXXXXX________ P3: __XXXXX_______________________ 0 - P2 (6) 1 - P2 (5) 2 - P3 (4) 3 - P3 (3) 4 - P3 (2) 5 - P3 (1) 6 - P3 (0) 7 - P2 (4) 8 - P2 (3) 9 - P2 (2) 10 - P2 (1) 11 - P2 (0) 12 - P1 (2) 13 - P1 (1) 14 - P1 (0) 15 - P2 (6) 16 - P2 (5) 17 - P2 (4) 18 - P2 (3) 19 - P2 (2) 20 - P2 (1) 21 - P2 (0) 22 - P1 (2) 23 - P1 (1) 24 - P1 (0) 25 - IDLE 26 - IDLE 27 - IDLE 28 - IDLE 29 - IDLE
RILEVAZIONE DEGLI ERRORI
Il parser è in grado di individuare errori di tipo semantico e sintattico. Per gli errori sintattici, viene fatto uso del simbolo error fornito da Cup, il quale permette di riprendere l'esecuzione del programma dopo aver trovato un errore, allo scopo di segnalare tutti i problemi riscontrati e non fermarsi al primo individuato. La rilevazione degli errori semantici è effettuata all'interno delle azioni associate alle regole grammaticali, e permette di controllare la validità del modello posto in input (es. il numero di parametri in ingresso deve essere corretto, il tempo di esecuzione di un processo deve essere inferiore al suo periodo, ecc). Il programma, per quanto possibile, dopo aver rilevato un errore continua comunque a processare l'input per stampare a video la lista completa degli errori presenti nel file seguita dagli indici di riga e colonna interessati e da un opportuno messaggio informativo. Per stampare gli indici di riga e colonna associati agli errori sintattici e forniti dallo scanner, è stato ridefinito il metodo syntax_error(Symbol). A livello semantico, riscontrato un errore, viene invece utilizzato il metodo report_error(String, Object) che, oltre a ricevere la stringa contenente il messaggio di errore, riceve come secondo parametro il simbolo della grammatica attualmente analizzato dal parser.
Esempio di errore Semantico 1
INPUT:
@sort = min; @param = dead; @quantum = infinite; @preempt = true; %%%%%%% Name Rt eT DL AT; P1 16 3 12 3; P2 15 7 NO 0; P3 NO 5 10 2; MaxTime = 30;
OUTPUT:
Error. Errore semantico nel processo P1, settati sia deadline sia rate Syntax errors: 0 Semantic errors: 1 Aborting...
Esempio di errore Semantico 2
INPUT:
@sort = min; @quantum = infinite; @preempt = false; %%%%%%% Name Rt eT DL AT; P1 16 3 NO 3; P2 15 4 NO 0; P3 10 5 NO 2; P4 12 7 NO 0; MaxTime = 30;
OUTPUT:
Error. Errore nel linguaggio, numero di parametri non corretto Syntax errors: 0 Semantic errors: 1 Aborting...
Esempio di errore Sintattico
INPUT:
@sort = min; @param = dead; @quantum = infinite; @preempt = true; %%%%%%% Name Rt eT DL AT P1 16 3 NO 3; P2 15 7 NO 0; P3 NO 5 10 2; MaxTime = 30;
OUTPUT:
Syntax Error (line 8, column 1) Error. Syntax errors: 1 Semantic errors: 0 Aborting...
DOWNLOAD
Sorgenti: [1]
Scompattare il file Scheduler.zip nella directory base del progetto. Per compilare ed eseguire il programma spostarsi nella directory base del progetto ed eseguire dalla shell:
java java_cup.Main parser.cup jflex scanner.jflex javac it/polito/Gantt/*.java javac *.java java Main <file>
Contenuto pacchetto zip:
- cartella samples: contiene degli esempi di file in input privi di errori sintattici o semantici.
- cartella errors: contiene degli esempi di file in input con errori sintattici o semantici.
