/******************************************************************************
*                             HEAP HEADER FILE                                *
*                funzioni per manipolare il dato astratto heap                /
 
/******************************************************************************
*   2∞ Esercizio di Laboratorio di Algoritmi e Strutture Dati mod. A gr.2     *
*                                                                             *
*                           S C H E D U L E R                                 *
*                                                                             *
*  Realizzato da:                                                             *
*  Divisato Antonio 50/358                                                    *
*  Ferrara Francesco Saverio 566/811                                          *
*  Liguori Vincenzo 408/301                                                   *
*                                                                             *
******************************************************************************/
 
/***********************   DEFINIZIONE STRUTTURA DATI  ***********************/
 
#define LUNGHEAP 8 /*lunghezza massima dell'heap*/
#define FILESTATO "logstato.txt" /*nome del file usato*/
 
typedef struct nodoheap { /*struttura di un singolo elemento dell'array*/
 int pid;   /*Process ID*/
 int key;   /*chiave che indica la priorit‡*/
 int time; /*tempo di creazione*/
} tipoelementoheap;
 
typedef struct heap{ /*struttura di un heap*/
 tipoelementoheap *vett; /*vettore contenente gli elementi*/
 int heapsize; /*intero contenente la lunghezza dell'heap*/
 int allocato; /*indice della memoria allocata per l'heap*/
} tipoheap;
 
/********************   FUNZIONI DI GESTIONE DELL'HEAP   *********************/
 
void azzeraheap(tipoheap *heap);
/******************************************************************************
* Dato in input un heap lo prepara all'uso. Se l'heap conteneva gi‡ dei dati  *
* essi saranno persi!!!                                                       *
******************************************************************************/
 
int lunghezza(tipoheap *heap);
/******************************************************************************
* Dato in input un heap ritorna il numero di elementi in esso contenuti.      *
******************************************************************************/
 
int popmax(tipoheap *heap, int *pid,int *key, int *time);
/******************************************************************************
* Dato in input un heap ritorna il valore dell'elemento pi˘ grande e lo       *
* elimina dall'heap. Questa funzione ritorna l'heap senza violazioni.         *
******************************************************************************/
 
int insert(tipoheap *heap,int pid,int key,int time);
/******************************************************************************
* Dato in input un heap e i due valori di un elemento, la funzione inserisce  *
* l'elemento nell'heap. Questa funzione ritorna l'heap senza violazioni.      *
******************************************************************************/
 
void accorcia(tipoheap *heap);
/******************************************************************************
* Dato in input un heap, accorcia l'area di memoria allocata per inserire     *
* elementi nell'array.                                                        *
******************************************************************************/
 
void allunga(tipoheap *heap);
/******************************************************************************
* Dato in input un heap, allunga l'area di memoria allocata per inserire      *
* elementi nell'array.                                                        *
******************************************************************************/
 
/*********************  IMPLEMENTAZIONE DELLE FUNZIONI  **********************/
 
int sinistro(int i)
{
 return 2*i+1; /*ritorna il figlio sinistro del nodo i*/
}
 
int destro(int i)
{
 return 2*i+2; /*ritorna il figlio destro del nodo i*/
}
 
int padre(int i)
{
 return (int)((i-1)/2); /*ritorna il padre del nodo i*/
}
 
void scambia(int *n1,int *n2)
{
 int temp;
 
 /*semplice procedura di scambio di due interi*/
 temp = *n1;
 *n1 = *n2;
 *n2 = temp;
}
 
void heapify(tipoelementoheap *vettore, int i,int heapsize)
{
 int l,r,maggiore; /*dichiarazione degli indici*/
 
 l = sinistro(i); /*conserviamo il figlio sinistro dell'elemento i*/
 r = destro(i); /*conserviamo il figlio destro dell'elemento i*/
 
 /*verifichiamo il maggiore tra i e l*/
 if ((l <= heapsize) && (vettore[l].key > vettore[i].key))
 {
 maggiore = l;
 }
 else
 {
 maggiore = i;
 }
 
 /*verifichiamo il maggiore tra maggiore e r*/
 if ((r <= heapsize) && (vettore[r].key>vettore[maggiore].key))
 {
 maggiore = r;
 }
 if (maggiore != i) /*se abbiamo trovato un elemento maggiore diverso da i...*/
 { /*...quindi esisteva la violazione!*/
 scambia(&vettore[i].key,&vettore[maggiore].key);
 scambia(&vettore[i].pid,&vettore[maggiore].pid);
 scambia(&vettore[i].time,&vettore[maggiore].time);
 heapify(vettore,maggiore,heapsize); /*chiamata ricorsiva per verificare...*/
 } /*...l'esistenza di una nuova violazione.*/
}
 
void azzeraheap(tipoheap *heap)
{
 heap->heapsize = -1; /*pone la lunghezza dell'heap al valore -1*/
 heap->allocato = 1; /*indica che sono state allocate 1*LUNGHEAP elementi*/
 
 /*alloca la memoria*/
 heap->vett = (tipoelementoheap *) malloc(sizeof(tipoelementoheap)*LUNGHEAP);
}
 
int lunghezza(tipoheap *heap)
{
 return heap->heapsize+1; /*restituisce il numero di elementi dell'heap*/
}
 
void accorcia(tipoheap *heap)
{
 /*siccome il riallocamento di un vettore impiega molto tempo, imponiamo che
 * esso venga accorciato solo quando Ë completamente vuoto. Per questo motivo
 * non c'Ë il controllo per eventuali elementi presenti nel vecchio vettore*/
 
 heap->allocato = 1; /*riduce al minimo l'idice di lunghezza*/
 free(heap->vett); /*libera la memoria*/
 
 /*alloca la nuova memoria*/
 heap->vett = (tipoelementoheap *) malloc(sizeof(tipoelementoheap)*LUNGHEAP);
}
 
int popmax(tipoheap *heap, int *pid, int *key, int *time)
{
 *pid = heap->vett[0].pid; /*salva il valore da sovrascrivere*/
 *key = heap->vett[0].key; /*salva il valore da sovrascrivere*/
 *time = heap->vett[0].time; /*salva il valore da sovrascrivere*/
 
 if (heap->heapsize > -1) /*se l'heap ha almeno un elemento*/
 {
 heap->vett[0].key = heap->vett[heap->heapsize].key;   /*sovrascrive key*/
 heap->vett[0].pid = heap->vett[heap->heapsize].pid;   /*sovrascrive pid*/
 heap->vett[0].time = heap->vett[heap->heapsize].time; /*sovrascrive time*/
 heap->heapsize--; /*accorcia la lunghezza dell'heap*/
 
 /*a questo punto heap->vett[0] puÚ violare le propriet‡ di heap*/
 heapify(heap->vett,0,heap->heapsize); /*elimina l'eventuale violazione*/
 
 return 1; /*ritorna un indicatore di successo*/
 }
 else /*l'heap Ë privo di elementi...*/
 {
 if (heap->allocato != 1) /*...ed ha piu' di 1 indice di memoria allocato*/
 {
 accorcia(heap); /*chiama la funzione per accorciare l'heap*/
 }
 return 0; /*ritorna un indicatore di errore*/
 }
}
 
void allunga(tipoheap *heap)
{
 int i;
 tipoelementoheap *temp; /*dichiara un array d'appoggio*/
 
 temp = (tipoelementoheap *) malloc(sizeof(tipoelementoheap)*((heap->allocato)+1)*LUNGHEAP);
 for(i=0 ; i <= heap->heapsize ; i++) /*salva tutti gli elementi*/
 {
 temp[i].key = heap->vett[i].key;
 temp[i].pid = heap->vett[i].pid;
 temp[i].time = heap->vett[i].time;
 }
 (heap->allocato)++; /*aumenta l'indice di allocazione*/
 free(heap->vett); /*libera la memoria*/
 heap->vett = temp; /*registra il nuovo vettore*/
}
 
int insert(tipoheap *heap,int pid,int key,int time)
{
 int i;
 
 if (heap->heapsize >= (heap->allocato * LUNGHEAP)) /*se l'heap Ë pieno*/
 {
 allunga(heap); /*chiama la procedura pe allunghare l'array dell'heap*/
 }
 heap->heapsize++; /*incrementa la dimensione dell'heap*/
 i = heap->heapsize; /*salva la lunghezza nell'indice manipolarlo*/
 
 /*questo ciclo trova la posizione giusta al nuovo elemento.*/
 /*metre l'ipotetico padre dell'elemento i Ë minore del nuovo elemento*/
 while ((i>0) && (heap->vett[padre(i)].key < key))
 {
 /*sposta il padre di una posizione*/
 heap->vett[i].key = heap->vett[padre(i)].key;
 heap->vett[i].pid = heap->vett[padre(i)].pid;
 heap->vett[i].time = heap->vett[padre(i)].time;
 i = padre(i); /*prepara l'indice a una nuova iterazione*/
 }
 heap->vett[i].pid = pid; /*registra il pid del nuovo elemento*/
 heap->vett[i].key = key; /*registra la key del nuovo elemento*/
 heap->vett[i].time = time; /*registra il time del nuovo elemento*/
 
 return 0; /*ritorna un indicatore di successo*/
}

/******************************************************************************
*                        SIMULAZIONE HEADER FILE                              *
*                funzioni per l'inizializzazione dei file e                   *
*                    la simulazione dello scheduling                          /
 
/******************************************************************************
*   2∞ Esercizio di Laboratorio di Algoritmi e Strutture Dati mod. A gr.2     *
*                                                                             *
*                           S C H E D U L E R                                 *
*                                                                             *
*  Realizzato da:                                                             *
*  Divisato Antonio 50/358                                                    *
*  Ferrara Francesco Saverio 566/811                                          *
*  Liguori Vincenzo 408/301                                                   *
*                                                                             *      
******************************************************************************/
 
/******************* DEFINIZIONE COSTANTI E STRUTTURE DATI *******************/
 
#define N 10
#define MP 1000
#define MAXPROCESSI 50
#define MAXTEMPO 350
#define FILEPROCESSI "logprocessi.txt"
 
typedef struct tipoprocesso{/*struttura della fascia di processi dell'insieme*/
 tipoheap coda; /*coda dei processi*/
 int pkey;      /*indice che indica la massima priorit‡ della coda*/
}tipoprocesso;
 
/************************ PROTOTIPI DELLE FUNZIONI ***************************/
 
void inizializzafile(FILE *fileprocessi);
/******************************************************************************
*  funzione che inizializza in write-mode il file datole in input per poter   *
*  effettuare successivi append                                               *
******************************************************************************/
 
void crea(tipoprocesso*processi,int n,int *time,int *totprocessi,FILE*fileprocessi);
/******************************************************************************
*  questa funzione crea un numero n datole in input di processi; per fare ciÚ * 
*  si avvale ciclicamente della funzione  inserisci() a cui passa il          *      
*  puntatore al file, alla coda dei processi e l'istante time di creazione.   *
*  Inoltre incrementa il numero totale di processi creati e il contatore      *
*  time.                                                                      *
******************************************************************************/
 
int inserisci(tipoprocesso *processi,int *time,FILE *fileprocessi);
/******************************************************************************
*  questa funzione crea un numero n datole in input di processi; per fare ciÚ *
*  si avvale ciclicamente della funzione  inserisci() a cui passa il          *
*  puntatore al file, alla coda dei processi e l'istante time di creazione    *                                                                             *
******************************************************************************/
 
void estrazione(tipoprocesso*processi,int n,int *time, int *totprocessi,FILE *fileprocessi);
/******************************************************************************
*  funzione che al cotrario di crea() estrae gli n processi dalle code        *
*  utilizzando ciclicamente la funzione elimina a cui passa puntatore al file,*
*  alla coda dei processi e l'istante time di creazione.                      *   
*  Inoltre incrementa il numero totale di processi creati e il contatore      *
*  time.                                                                      *
******************************************************************************/
 
int elimina(tipoprocesso *processi,FILE *fileprocessi);
/******************************************************************************
*  funzione che dato in input il puntatore al file e quello alle code Ë in    *
*  grado di riconoscere da quale coda andare ad estrarre e quindi terminare   *
*  ogni processo. Scrive inoltre nel file lo stato delle code e restituisce   *
*  un intero che indica 1 se l'operazione ha avuto successo, 0 in caso        *
*  contrario                                                                  *
******************************************************************************/
 
void outputfilestato(tipoprocesso *processi,int time);
/******************************************************************************
*  questa funzione si occupa dell'output del programma, ossia della stampa    * 
*  della situazione delle N code al tempo time                                *
******************************************************************************/
 
void azzeralog();
/******************************************************************************
* Inizializza il file dei log.                                                *
******************************************************************************/
 
int scrivilog(tipoheap *heap,int num,int time);
/******************************************************************************
* stampa tutti dli elementi della coda nel file                               *
******************************************************************************/
 
/******************** IMPLEMENTAZIONE DELLE FUNZIONI *************************/
 
void inizializzafile(FILE *fileprocessi) /*procedura per inizializzare il file*/
{
 fileprocessi = fopen(FILEPROCESSI,"w"); /*apre il file in write-mode*/
 close(fileprocessi); /*chiude il file*/
 /*adesso il file esiste su disco ed Ë vuoto, cioË preparato per aggiungere
 * elementi in append-mode*/
}
 
int inserisci(tipoprocesso *processi,int *time,FILE *fileprocessi)
{
 int i,pid,key;
 
 key = rand() % MP+1; /*genera un numero casuale da 0 a MP che indica la priorit‡*/
 
 for (i=0 ; key > processi[i].pkey ; i++); /*cerca la coda adatta per la priorit‡ key*/
 
 /*raccogli informazioni per dare un pid univoco al processo*/
 pid = lunghezza(&processi[i].coda);
 pid = pid + (i*100);
 
 insert(&processi[i].coda,pid,key,*time); /*inserisce il processo*/
 
 fileprocessi = fopen(FILEPROCESSI,"a"); /*apre il file*/
 /*effettua la registrazione del processo inserito*/
 fprintf(fileprocessi,"\t%4d\t\t%4d\t\t%4d\t\t%4d\n\n",pid,key,i+1,*time);
 close(fileprocessi); /*chiude il file*/
 
 return 1; /*ritorna un indicatore di successo*/
}
 
void crea(tipoprocesso *processi,int n, int *time, int *totprocessi,FILE *fileprocessi)
{
 int i;
 
 for (i=0 ; i<n ; i++) /*inserisce n processi nella coda*/
 {
 if (inserisci(processi,time,fileprocessi))
 {
 (*totprocessi)++; /*incrementa il numero di processi*/
 (*time)++;        /*incrementa il tempo*/
 }
 }
}
 
int elimina(tipoprocesso *processi,FILE *fileprocessi)
{
 int pid,key,oldtime,i;
 
 /*cerca la coda con priorit‡ pi˘ alta dove ci sia almeno un processo*/
 for (i=N-1 ; (i>=0) && (lunghezza(&processi[i].coda) == 0)  ; i--);
 
 /*non ci sono pi˘ processi nella coda...*/
 if (i == -1) /*...si prevede che questa situazione non si verifichi mai*/
 {
 fileprocessi = fopen(FILEPROCESSI,"a"); /*apre il file*/
 /*scrive un indicatore di errore*/
 fprintf(fileprocessi,"\tNaN\t\tNaN\t\tNaN\t\tNaN\n\n");
 close(fileprocessi); /*chiude il file*/
 return 0; /*ritorna un indicatore di errore*/
 }
 else /*ci sono processi da eliminare*/
 {
 /*elimina il processo pi˘ grande dell'i-esima coda*/
 popmax(&processi[i].coda, &pid, &key, &oldtime);
 
 fileprocessi = fopen(FILEPROCESSI,"a"); /*apre il file*/
 fprintf(fileprocessi,"\t%4d\t\t%4d\t\t%4d\t\t%4d\n\n",pid,key,i+1,oldtime);
 close(fileprocessi); /*chiude il file*/
 return 1; /*ritorna un indicatore di successo*/   
 }
}
 
void estrazione(tipoprocesso *processi,int n, int *time, int *totprocessi,FILE *fileprocessi)
{
 int i;
 
 for (i=0 ; i<n ; i++) /*estrae n processi*/
 {
 if (elimina(processi,fileprocessi))
 {
 (*totprocessi)--; /*decrementa il numero di processi*/
 (*time)++; /*incrementa il tempo*/
 }
 }
}
 
void outputfilestato(tipoprocesso *processi,int time)
{
 int i;
 
 for(i=0; i<N ; i++) /*per tutte le N code*/
 {
 /*stampa su file lo stato dell'i-esima coda*/
 scrivilog(&processi[i].coda,i+1,time); 
 }
}
 
void azzeralog()
{
 FILE *filestato; /*dichiarazione puntatore a file*/
 filestato = fopen(FILESTATO,"w"); /*apre il file in write-mode*/
 close(filestato); /*chiude il file*/
 /*adesso il file esiste su disco ed Ë vuoto, cioË preparato per aggiungere
 * elementi in append-mode*/
}
 
int scrivilog(tipoheap *heap,int num,int time)
{
 FILE *filestato; /*dichiarazione del file*/
 int i;
 
 filestato = fopen(FILESTATO,"a"); /*apre il file in append-mode*/
 
 if (filestato == NULL) /*se Ë stato ritirnato un indice di errore*/
 {
 printf("ERRORE: file %s non inizializzato!\n",FILESTATO);
 return 1; /*ritorna un indicatore di errore*/
 }
 else /*non Ë stato ritornato nessun indice di errore*/
 {
 /*scrive sul file*/
 fprintf(filestato,"STATO AL TEMPO %d DELLA %d∞ CODA:\n",time,num);
 for (i=0 ; i <= heap->heapsize ; i++) /*stampa tutti gli elementi della coda*/
 {
 fprintf(filestato,"%3d) Pid: %4d   key: %4d   Time: %4d\n",i+1,heap->vett[i].pid,heap->vett[i].key,heap->vett[i].time);
 }
 fprintf(filestato,"In totale i processi sono %d\n\n\n",(heap->heapsize)+1);
 
 close(filestato); /*chiudeil file*/
 return 0; /*restituisce un indicatore di successo*/
 }
}

#include <stdio.h>
#include <stdlib.h>
#include "heap.h"
#include "simulazione.h"
/******************************************************************************
*   2∞ Esercizio di Laboratorio di Algoritmi e Strutture Dati mod. A gr.2     *
*                                                                             *
*                           S C H E D U L E R                                 *
*                                                                             *
*  Realizzato da:                                                             *
*  Divisato Antonio 50/358                                                    *
*  Ferrara Francesco Saverio 566/811                                          *
*  Liguori Vincenzo 408/301                                                   *
******************************************************************************/
 
main()
{
 tipoprocesso processi[N]; /*dichiare il vettore che contine N code*/
 int i,n;
 int time=0; /*dichiara ed inizializza il tempo*/
 int totprocessi=0; /*dichiara ed inizializza il numero di processi totale*/
 FILE *fileprocessi;
 
 for (i=0 ; i<N ; i++) /*per tutte le N code*/
 {
 azzeraheap(&processi[i].coda); /*inizializza la coda*/
 processi[i].pkey = (i+1) * ((int) MP/N); /*stabilisce la priorit‡ per la coda*/
 }
 inizializzafile(fileprocessi); /*inizializza il file per i processi*/
 azzeralog(); /*inizializza il log-file per l'header heap.h*/
 
 fileprocessi = fopen(FILEPROCESSI,"a"); /*apre il file in append-mode*/
 /*scrive un'intestazione*/
 fprintf(fileprocessi,"=-=-=-=-=-=-=-=-=-=-=-=[INIZIO SIMULAZIONE]=-=-=-=-=-=-=-=-=-=-=-=\n");
 close(fileprocessi); /*chiude il file*/
 
 do {
 
 fileprocessi = fopen(FILEPROCESSI,"a"); /*apre il file in append-mode*/
 fprintf(fileprocessi,"\n\nFASE DI CREAZIONE E INSERIMENTO DEI PROCESSI AL TEMPO %d\n",time);
 
 n = rand() % (MAXPROCESSI-totprocessi+1); 
 
 fprintf(fileprocessi,"E' stato generato un numero casuale di %d processi.\n\n",n);
 fprintf(fileprocessi,"Tabella dei processi inseriti:\n\n");
 fprintf(fileprocessi,"\tpid\t\tkey\t\tn∞coda\t\tTempo\n\n");
 close(fileprocessi); /*chiude il file*/
 
 crea(processi,n,&time,&totprocessi,fileprocessi);
 
 fileprocessi = fopen(FILEPROCESSI,"a"); /*apre il file in append-mode*/
 fprintf(fileprocessi,"\n\nFASE DI ESTRAZIONE DEI PROCESSI AL TEMPO %d\n",time);  
 
 n = rand() % (totprocessi+1); /*il nuovo n sar‡ <= del vecchio n*/
 
 fprintf(fileprocessi,"Sto procedendo all'estrazione di %d processi\n\n",n);
 fprintf(fileprocessi,"Tabella dei processi estratti:\n\n");
 fprintf(fileprocessi,"\tpid\t\tkey\t\tn∞coda\t\tTempo\n\n");
 close(fileprocessi); /*chiude il file*/
 
 estrazione(processi,n,&time,&totprocessi,fileprocessi);
 
 outputfilestato(processi,time);
 
 } while (time < MAXTEMPO);
 
 fileprocessi = fopen(FILEPROCESSI,"a"); /*apre il file in append-mode*/
 fprintf(fileprocessi,"\n=-=-=-=-=-=-=-=-=-=-=-=[FINE SIMULAZIONE]=-=-=-=-=-=-=-=-=-=-=-=\n\n");
 close(fileprocessi); /*chiude il file*/
 printf("La simulazione e' terminata, l'output si trova nei file:\n %s\n %s\n \n",FILEPROCESSI,FILESTATO);
 printf("Premere <INVIO> per uscire");
 
 getchar(); /*attende che l'utente prema INVIO*/
}