#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>


#define MAX_DURACAO	1000000L	/* Duracao maxima da simulacao */

#define N_TASKS		20		/* Numero de tarefas */

#define MAX_BLOQUEIO	2000		/* Tempo maximo de bloqueio */

#define MAX_COMP	500		/* Tempo maximo de computacao */


#define rr(x)     ( (x==0) ? ( 0 ) : (random(x)) )


struct s_desctask{
	int	id;		/* Identificador */
	int	prio;		/* Prioridade */

	int	comp;		/* Tempo de computacao em cada ciclo */
	int	bloqueio;	/* Tempo de bloqueio em cada ciclo */

	int 	falta_comp;	/* Computacao que falta neste ciclo */
	long	pronto;		/* Instante de pronto deste ciclo */

	long	max_ciclo;	/* Ciclo cpu maximo observado */
	long    n_ciclo;	/* Numero de ciclos executados */

	struct s_desctask *proximo;	/* Encadeamento p/ escalonamento */
	};



struct s_desctask tasks[N_TASKS];	/* Descritores de tarefas */


double simula_ciclos_medio;	/* Ciclo medio observado no sistema */
long simula_ciclos_done;	/* Numero total de ciclos feitos */
long simula_ocupado;		/* Tempo que cpu ficou ocupada */

struct s_desctask *presente;	/* Fila de aptos */
struct s_desctask *futuro;	/* Fila de liberacoes futuras */



/************************
*			*
*	GERA_CARGA	*
*			*
*************************/
void gera_carga( void)
{
	int i;

	for( i=0; i<N_TASKS; ++i)
	 {
		tasks[i].id = i;
		tasks[i].prio = i;
		tasks[i].comp = 1 + rr( MAX_COMP );
		tasks[i].bloqueio = MAX_BLOQUEIO;
		tasks[i].falta_comp = tasks[i].comp;
		tasks[i].pronto = 0;
		tasks[i].max_ciclo = 0;
		tasks[i].n_ciclo = 0;
		tasks[i].proximo = &tasks[i+1];
		}
	tasks[N_TASKS-1].proximo = NULL;

        futuro = &tasks[0];
	presente = NULL;
}




/********************************
*				*
*	INSERE NA FILA DE APTOS	*
*	(prioridade preemptiva)	*
*				*
********************************/
void insere_fila( void)
{
struct s_desctask *novo, *aux, *ant;

	novo = futuro;
	futuro = futuro->proximo;

	ant = NULL;
	aux = presente;

	while( aux != NULL  &&  aux->prio <= novo->prio )
	  {	ant = aux;
		aux = aux->proximo;
		}
	if( ant == NULL )
	  {	novo->proximo = presente;
		presente = novo;
		}
	else
	  {	novo->proximo = aux;
		ant->proximo = novo;
		}
}



/************************
*			*
*	SIMULA		*
*			*
*************************/
long simula( long duracao)
{
long dist_pronto;
long dist_conclui;
long dist_passo;
struct s_desctask *novo, *aux, *ant;
long resp;

long relogio = 0;

simula_ciclos_done = 0;
simula_ciclos_medio = 0.0;
simula_ocupado = 0;


while( relogio < duracao )
  {
	dist_pronto = (futuro==NULL)? 65000u : (unsigned)(futuro->pronto - relogio);
	dist_conclui = (presente==NULL)? 65000u : presente->falta_comp;

	if( dist_conclui <= dist_pronto )
		dist_passo = dist_conclui;
	else
		dist_passo = dist_pronto;


/*** Avanca o relogio */

	relogio += dist_passo;


/*** Testa se cpu livre e computa tempo percorrido */

	if( presente != NULL )
	   {
		simula_ocupado += dist_passo;
		presente->falta_comp -= (int)dist_passo;
		}


/*** Verifica se a tarefa executando conclui */

	if( presente!=NULL  &&  presente->falta_comp == 0 )
	  {
		/*** Calcula tempo total deste ciclo ***/
		++presente->n_ciclo;
		++simula_ciclos_done;
		resp = (unsigned)( relogio - presente->pronto );
		if( resp > presente->max_ciclo )
			presente->max_ciclo = resp;
		simula_ciclos_medio += resp;


		/*** Arma a proxima ativacao ***/

		presente->falta_comp = presente->comp;
		presente->pronto = relogio + presente->bloqueio;


		/*** Pronto no futuro, retira da lista presente ***/

		novo = presente;
		presente = presente->proximo;
		ant = NULL;
		aux = futuro;
		while( aux != NULL  &&  aux->pronto <= novo->pronto )
		  {	ant = aux;
			aux = aux->proximo;
				}
		if( ant == NULL )
		  {	novo->proximo = futuro;
			futuro = novo;
			}
		else
		  {	novo->proximo = aux;
			ant->proximo = novo;
			}
		}


/*** Verifica se alguma proxima ativacao ja deve entrar  **/

	while( futuro != NULL  &&  futuro->pronto == relogio )
	  {
		insere_fila();
		}



	}/* fim do laco de simulacao */


/*** Gera estatisticas ***/

simula_ciclos_medio = (double)simula_ciclos_medio / simula_ciclos_done;

return relogio;

}




/************************
*			*
*	MAIN		*
*			*
*************************/
void main(int argc, char *argv[])
{
long duracao, final;
int i;

if( argc != 2 )
  {	printf("Uso: simul1 <duracao> <Enter>\n\n");
	exit(1);
	}

duracao = atol( argv[1] );
if( duracao < 0  ||  duracao > MAX_DURACAO )
  {	printf("Duracao %ld nao eh valida\n");
	exit(1);
	}

randomize();

gera_carga();
simula_ciclos_medio = 0;
simula_ciclos_done = 0;
simula_ocupado = 0;

printf("Iniciando simulacao com duracao %ld.\n", duracao);
printf("Sao %d tarefas com prioridade preemptiva.\n", N_TASKS);

final = simula( duracao );

printf("Apos %ld, Cpu ocupada:%4.1f, ciclo medio: %4.1f\n",
	final, simula_ocupado*100.0 / final, simula_ciclos_medio );


for( i=0; i<N_TASKS; ++i)
	printf("Task %d, comp %d, max_ciclo %ld, bloqueio %d, n_ciclo %ld.\n",
		i, tasks[i].comp, tasks[i].max_ciclo,
		tasks[i].bloqueio, tasks[i].n_ciclo);


}