// Simular Paginacion Con Procesos
// Gilberto Stankiewicz
// http://www.stan.com.mx
// ESCOM, 4CM4
// Abril 2008
// gcc SimularPaginacion.c -lm

#include <time.h>
#include <math.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
#include <sys/sem.h>

#define SEM_DD 0

int semid;
int tamano, tiempo;
int tamanoMemoria, tamanoDD;
int bitsMarco, bitsMemoria, bitsDD, noProcesos, noMarcos;
int *memoria, *dd, *pidAdmin;

// funciones semaforos

void semp (int semnum) {
	struct sembuf operacion;
	operacion.sem_flg = 0;
	operacion.sem_num = semnum;
	operacion.sem_op = -1;
	semop(semid, &operacion, 1);
}

void semv (int semnum) {
	struct sembuf operacion;
	operacion.sem_flg = 0;
	operacion.sem_num = semnum;
	operacion.sem_op = 1;
	semop(semid, &operacion, 1);
}

// administrar memoria

int ceros (int *memoriaX, int tamanoX) {
	int i;
	
	for (i = 0; i < tamanoX; i += 3) {
		memoriaX[i] = 0;
		memoriaX[i + 1] = 0;
		memoriaX[i + 2] = 0;
	}
}

int imprimir (int *memoriaX, int tamanoX) {
	int i;
	
	for (i = 0; i < tamanoX; i += 3) {
		printf("%5d", memoriaX[i]);
		printf("%5d", memoriaX[i + 1]);
		printf("%5d", memoriaX[i + 2]);
		printf("\n");
	}
	
	printf("\n");
}

int paginasDisponibles (int *memoriaX, int tamanoX, int tamanoP) {
	int i, tamano = 0;
	
	for (i = 0; i < tamanoX; i += 3) {
		if (memoriaX[i] == 0) {
			tamano++;
			if (tamano == tamanoP)
				return 1;
		}
	}
	
	return 0;
}

int meter (int *memoriaX, int tamanoX, int pid, int tamanoP) {
	int i, pagina = 0;
	
	semp(SEM_DD);
	if (paginasDisponibles(memoriaX, tamanoX, tamanoP)) {
		for (i = 0; i < tamanoX; i += 3) {
			if (memoriaX[i] == 0) {
				memoriaX[i] = pid;
				memoriaX[i + 1] = pagina++;
				memoriaX[i + 2] = -1;
				if (pagina == tamanoP)
					break;
			}
		}
		
		//imprimir (memoriaX, tamanoX);
		
		semv(SEM_DD);
		return 1;
	}
	
	semv(SEM_DD);
	return 0;
}

void sacar (int *memoriaX, int tamanoX, int pid) {
	int i;
	
	semp(SEM_DD);
	for (i = 0; i < tamanoX; i += 3) {
		if (memoriaX[i] == pid) {
			memoriaX[i] = 0;
			memoriaX[i + 1] = 0;
			memoriaX[i + 2] = 0;
		}
	}
	semv(SEM_DD);
}

int procesoMasDormido (int *memoriaX, int tamanoX) {
	int i, pid = 0, quantum = INT_MAX;
	
	for (i = 0; i < tamanoX; i += 3) {
		if (memoriaX[i] != 0 && memoriaX[i + 2] < quantum) {
			pid = memoriaX[i];
			quantum = memoriaX[i + 2];
		}
	}

	return pid;
}

int procesoMenosDormido (int *memoriaX, int tamanoX) {
	int i, pid = 0, quantum = 0;
	
	for (i = 0; i < tamanoX; i += 3) {
		if (memoriaX[i] != 0 && memoriaX[i + 2] > quantum) {
			pid = memoriaX[i];
			quantum = memoriaX[i + 2];
		}
	}

	return pid;
}

void dormirProceso (int *memoriaX, int tamanoX, int pid, int quantum) {
	int i;
	
	for (i = 0; i < tamanoX; i += 3) {
		if (memoriaX[i] == pid) {
			memoriaX[i + 2] = quantum;
		}
	}
}

int tamanoProceso (int *memoriaX, int tamanoX, int pid) {
	int i, tamano = 0;
	
	for (i = 0; i < tamanoX; i += 3) {
		if (memoriaX[i] == pid) {
			tamano++;
		}
	}
	
	return tamano;
}


// funciones procesos y administrador

void trabajoAdministrador () {
	int pid, quantum = 0, adentro;

	while (1) {
		// proximo proceso a ejecutar
		pid = procesoMasDormido(dd, tamanoDD);
		if (pid == 0) continue;
		
		printf(" DD: \n");
		imprimir(dd, tamanoDD);
		
		if (tamanoProceso(memoria, tamanoMemoria, pid) == 0) {
			// meter proceso en memoria porque no esta
			adentro = 0;
			
			do {
				if ((adentro = meter(memoria, tamanoMemoria, pid, tamanoProceso(dd, tamanoDD, pid))) == 0) {
					// no cabe, habra que quitar algun proceso
					sacar(memoria, tamanoMemoria, procesoMenosDormido(memoria, tamanoMemoria));
				}
			} while (!adentro);
		}
		
		printf(" MEMORIA PRINCIPAL: \n");
		imprimir(memoria, tamanoMemoria);

		// ejecutar proceso y dormir adminitrador
		sleep(1);
		kill(pid, SIGCONT);
		kill(getpid(), SIGSTOP);
		
		// actualizar datos de procesos
		dormirProceso(dd, tamanoDD, pid, quantum);
		dormirProceso(memoria, tamanoMemoria, pid, quantum);
		
		// siguiente quantum
		quantum++;
	}
}

void trabajoProceso () {
	int loop = 1;
	//printf(" pid=%d tamano=%d tiempo=%d \n", getpid(), tamano, tiempo);
	
	while(! meter(dd, tamanoDD, getpid(), tamano)) {
		sleep(1);
	}
	
	while (loop) {
		kill(getpid(), SIGSTOP);

		printf(" %d estoy trabajando \n", getpid());
		
		if(--tiempo == 0) {
			sacar(memoria, tamanoMemoria, getpid());
			sacar(dd, tamanoDD, getpid());
			loop = 0;
		}

		sleep(1);
		kill(*pidAdmin, SIGCONT);
	}
}


int main (int argc, char* argv[]) {
	int i, shmid, pid;
	int maxTamano, maxTiempo = 3;
	key_t llave;
		
	srand(time(NULL));

	// parámetros de entrada
	if (argc < 5) {
		fprintf(stderr, "Modo de empleo: %s bitsMarco bitsMemoria bitsDD noProcesos \n", argv[0]);
		fprintf(stderr, "Simular páginación. \n");
		exit(-1);
	}
	
	bitsMarco = atoi(argv[1]);
	bitsMemoria = atoi(argv[2]);
	bitsDD = atoi(argv[3]);
	noProcesos = atoi(argv[4]);
	noMarcos = pow(2, bitsMemoria - bitsMarco);
	maxTamano = pow(2, bitsMarco) * noMarcos / 2;

	// crear llave
	llave = ftok(argv[0], 'a');
	
	// crear un semaforo
	semid = semget(llave, 1, IPC_CREAT | 0600);

	// inicializar semaforo
	semctl(semid, SEM_DD, SETVAL, 1);
		
	// pedir zona de memoria compartida
	tamanoMemoria = pow(2, bitsMemoria) * 3; // [pid][pagina][segundo=-1]
	tamanoDD = pow(2, bitsDD) * 3;
	shmid = shmget(llave, (tamanoMemoria + tamanoDD + 1) * sizeof(int), IPC_CREAT | 0600);
		
	// unir zona de memoria compartida a nuestro espacio de direcciones virtuales
	memoria = (int*) shmat(shmid, 0, 0);
	
	// repartir zona de memoria compartida
	dd       = memoria + tamanoMemoria;
	pidAdmin = memoria + tamanoMemoria + tamanoDD; 
	ceros(dd, tamanoDD);
	ceros(memoria, tamanoMemoria);
	
	//printf("yupi!");fflush(stdout);

	// crear procesos
	for (i = 0; i < noProcesos; i++) {
		tamano = rand() % maxTamano + 1;
		tiempo = rand() % maxTiempo + 1;
		
		if ((pid = fork()) == -1) {
			perror("fork");
			exit(-1);			
		}
		else if (pid == 0) {
			trabajoProceso();
			exit(0);
		}
	}
	
	// crear administrador
	if ((*pidAdmin = fork()) == -1) {
		perror("fork");
		exit(-1);			
	}
	else if (*pidAdmin == 0) {
		trabajoAdministrador();
		exit(0);
	}
	
	// esperar procesos
	for (i = 0; i < noProcesos; i++) {
		printf(" :X %d \n", wait(NULL));
	}
	
	// matar al administrador
	kill(*pidAdmin, SIGINT);
	
	// separar la zona de memoria compartida de nuestro espacio de direcciones virtuales
	shmdt(memoria);
	
	// borrar zona de memoria compartida
	shmctl(shmid, IPC_RMID, 0);
	
	// borrar semáforos
	semctl(semid, 0, IPC_RMID, 0);
}