round.cpp

#include <iostream>

using namespace std;

typedef struct elem{
	int pid;
	int ing;
	int nig;
	int dur;
	int esp;
	int pwt;
	int end;
	elem * next;
}tipoProc;

typedef struct l{
	tipoProc * ini;
	tipoProc * end;	
}tipoList;

int QUANTUM;
int pid;
tipoList * lc = (tipoList *) malloc(sizeof(tipoList));
int GLOBAL_TIME = 0;
float MEXEC = 0.0;
float MESPE = 0.0;


void print_list()
{
	tipoProc * l = lc->ini;
	int flag = 1;

	if(l == NULL)
	{
		printf("NULL\n");
		return;
	}

	while(l and flag)
	{
		if(l == lc->end) flag = 0;
		printf("PID: %d, nig:%d, ing:%d, dur:%d, end:%d\n", l->pid, l->nig, l->ing, l->dur, l->end);
		l = l->next;
	}
	printf("\n");
}


void round_robin()
{
	// printf("ini\n");
	// print_list();
	// printf("fim\n");
	tipoProc * l = lc->ini;
	GLOBAL_TIME = l->ing; /* tempo começa no instante que o primeiro cara chega */

	// for(int j = 0; j < 15; j++)
	while(l)
	{
		// printf("dentro ini\n");
		// print_list();
		// printf("dentro fim\n");
		// printf("instancia %d\n", j);
		if(l->dur < QUANTUM) /* processa finaliza menor que quantum */
		{
			// printf("< PID: %d, ing:%d, dur:%d\n", l->pid, l->ing, l->dur);
			// printf("P%d DURACAO %d < QUANTUM\n", l->pid, l->dur);

			if(l->nig > GLOBAL_TIME)
			{
				GLOBAL_TIME = l->nig + l->dur + QUANTUM;
			}
			else
			{
				GLOBAL_TIME += l->dur;
			}

			l->dur = 0;
			l->end = GLOBAL_TIME; /* tempo em que o processo finaliza */
			printf("P%d ", l->pid);
			MEXEC += l->end + l->ing;
			// printf("GLOBAL_TIME===%d\n", GLOBAL_TIME);
			// printf("ESSA LISTA\n");
			// print_list();
			// printf("FIM DA LISTA\n");
			// print_list();
			// l deve ser adiciona na lista de finalizados BEM AQUI

			// printf("***** antes -- DEMON ****\n");
			// print_list();
			// printf("----\n");

			// printf("CORRENTE -- PID: %d, nig:%d, ing:%d, dur:%d, end:%d\n", l->pid, l->nig, l->ing, l->dur, l->end);

			l = lc->ini->next;
			lc->ini = l;

			// printf("nova lista\n");
			// print_list();

			if(lc->ini == lc->end)
			{
				//
				if(l->nig > GLOBAL_TIME)
				{
					GLOBAL_TIME = l->nig + l->dur + QUANTUM;
				}
				else
				{
					GLOBAL_TIME += l->dur;
				}

				l->dur = 0;
				l->end = GLOBAL_TIME; /* tempo em que o processo finaliza */
				printf("P%d ", l->pid);
				// MEXEC += l->end + l->ing;
				break;
			}

			// printf("***** DEMON ****\n");
			// print_list();
			// printf("----\n");
			// remove l da lista -- colocar na lista de finalizados
			// atualiza lc
			// l = lc
			// printf("entrou no 1 if\n");
			continue;
		}
		else if(l->dur == QUANTUM) /* processa finaliza igual quantum */
		{
			// printf("== PID: %d, ing:%d, dur:%d\n", l->pid, l->ing, l->dur);
			// printf("P%d DURACAO %d == QUANTUM\n", l->pid, l->dur);
			l->dur -= QUANTUM;

			/* checa se o processo finalizou */
			if(l->dur == 0) 
			{
				if(l->nig > GLOBAL_TIME)
				{
					GLOBAL_TIME = l->nig + l->dur + QUANTUM; // tirei o quantum coloca de novo
				}
				else
				{
					GLOBAL_TIME += QUANTUM;	
				}
				
				l->end = GLOBAL_TIME; /* tempo em que o processo finaliza */
				printf("P%d ", l->pid);
				MEXEC += l->end + l->ing;
				// printf("GLOBAL_TIME===%d\n", GLOBAL_TIME);
				// printf("ESSA LISTA\n");
				// print_list();
				// printf("FIM DA LISTA\n");
				// l deve ser adiciona na lista de finalizados BEM AQUI

				// if(lc->ini == lc->end)
				// {
				// 	l = NULL;
				// 	break;
				// }

				// printf("CORRENTE -- PID: %d, nig:%d, ing:%d, dur:%d, end:%d\n", l->pid, l->nig, l->ing, l->dur, l->end);


				l = lc->ini->next;
				lc->ini = l;

				// printf("nova lista\n");
				// print_list();
				// printf("----\n");
				// print_list();
				// printf("----\n");

				// printf("entrou no 2 if\n");

				continue;
			}
		}
		else /* processo volta pra lista */
		{
			printf("P%d ", l->pid);

			if(l->nig > GLOBAL_TIME)
			{
				GLOBAL_TIME = l->nig + QUANTUM;
			}
			else
			{
				GLOBAL_TIME += QUANTUM;
			}

			// printf("--- GLOBAL_TIME==%d\n", GLOBAL_TIME);
			// printf("PID: %d, nig:%d, ing:%d, dur:%d, end:%d\n", l->pid, l->nig, l->ing, l->dur, l->end);

			l->nig += QUANTUM;
			l->dur -= QUANTUM;

			
			// printf("PID: %d, nig:%d, ing:%d, dur:%d, end:%d\n", l->pid, l->nig, l->ing, l->dur, l->end);
			// printf("GLOBAL_TIME===%d\n", GLOBAL_TIME);

			// readiciona processo na lista
			tipoProc * caminha = lc->ini;
			tipoProc * ante = lc->end;
			int flag = 1;

			// printf("PERDIDA\n");
			// print_list(); // taok ate aqui
			// printf("PERDIDA\n");

			//remove cara da lista
			while(caminha and flag)
			{
				if(caminha == lc->end) flag = 0;	

				if(caminha == l)
				{
					if(caminha == lc->ini)
					{
						// printf("1\n");
						if(caminha == lc->end)
						{
							lc->ini = NULL;
							lc->end = NULL;
							// printf("broderoooooo\n");
							// printf("CARA --- PID: %d, nig:%d, ing:%d, dur:%d, end:%d\n", l->pid, l->nig, l->ing, l->dur, l->end);
							break;
						}

						// l continua apontando para o mesmo lugar
						lc->ini = caminha->next;
						lc->end->next = lc->ini;
						// print_list();
						break;
					} 
					else if(caminha == lc->end)
					{
						// printf("2\n");
						// ta no fim
						ante->next = lc->ini;
						lc->end = ante;
						break;
					}
					else
					{
						// printf("3\n");
						// ta no meio
						ante->next = caminha->next;
						break;
					}
				}
				ante = caminha;
				caminha = caminha->next;
			}
			//remove cara da lista	
			
			caminha = lc->ini;		
			ante = lc->end;
			flag = 1;

			// printf("CHEGAR AQUIIIIII\n");
			// print_list();
			// printf("CARA --- PID: %d, nig:%d, ing:%d, dur:%d, end:%d\n", l->pid, l->nig, l->ing, l->dur, l->end);
			// printf("lc-ini-pid=%d\n", lc->ini->pid);
			// printf("lc-end-pid=%d\n", lc->end->pid);

			if(lc->ini == NULL and lc->end == NULL)
			{
				lc->ini = l;
				lc->end = l;
				lc->end->next = l;

				continue;
			}

			// add cara na lista
			while(caminha and flag)
			{
				if(caminha == lc->end) flag = 0;	

				if(l->nig < caminha->nig)
				{
					// vai antes
					if(caminha == lc->ini) // e o primeiro elemento
					{
						// printf("A\n");
						// print_list();

						// printf("caminha->pid=%d\n", caminha->pid);
						// printf("lc->ini->pid=%d\n", lc->ini->pid);
						// printf("lc->end->pid=%d\n", lc->end->pid);
						// printf("l->pid%d\n", l->pid);

						l->next = caminha;
						lc->ini = l;
						lc->end->next = l;

						l = lc->ini; // continuar no while
						// printf("**************** \n");
						// print_list();
						// printf("**************** \n");
						break;
					}
					else // ta no meio da lista
					{
						// printf("B\n");
						ante->next = l;
						l->next = caminha;
						l = lc->ini; // continuar no while
						break;
					}
				}
				else if(caminha == lc->end) // e igual ou maior, vai depois
				{
					// printf("C\n");
					// vai depois
				 	// e o ultimo elemento
					// ta no final
					caminha->next = l;
					l->next = lc->ini;
					lc->end = l;
					l = lc->ini; // continuar no while
					break;
				}
				ante = caminha;
				caminha = caminha->next;
			}

		}
		// printf("a lista\n");
		// print_list();
	}
}

void add_elem_lis(int ing, int dur)
{
	tipoProc * elem = (tipoProc *) malloc(sizeof(tipoProc));
	elem->pid = pid++;
	elem->ing = ing;
	elem->dur = dur;
	elem->esp = 0;
	elem->nig = ing;
	elem->end = -1;

	if(lc->ini == NULL) /* list esta vazia */
	{
		lc->ini = elem;
		lc->end = elem;
		elem->next = elem;
	}
	else
	{
		lc->end->next = elem;
		lc->end = elem;
		elem->next = lc->ini; 
	}
}


void create_list()
{
	lc->ini = NULL;
	lc->end = NULL;
}

void free_list() 
{
	tipoProc * l = lc->ini;
	tipoProc * aux;
	int flag = 1;

	while(l and flag)
	{
		if(l == lc->end) flag = 0;
		aux = l;
		l = l->next;
		free(l);
	}
	
	lc->ini = NULL;
	lc->end = NULL;
}


int main(int argc, char const *argv[])
{
	int m, n, ing, dur, ts = 1;
	create_list(); /* cria lc -- lista circular que contem processsos */

	cin >> m;
	QUANTUM = m;
	pid = 1;

	while(cin >> n and n) 
	{
		printf("\nTeste %d\n", ts);

		for(int i=0; i<n; i++)
		{
			cin >> ing >> dur;
			add_elem_lis(ing, dur);
		}
		// print_list();
		round_robin();
		printf("\nTempo medio de execucao: %.2f\n", (MEXEC/(pid-1)));
		printf("Tempo medio de espera: %.2f\n", MESPE);
		free_list();
		pid = 1;
		ts++;
	}

	return 0;
}