// ------------------------------ // O Problema das N-Rainhas // ------------------------------ // 8 rainhas --> 92 soluções // 9 rainhas --> 352 soluções // 10 rainhas --> 724 soluções // 11 rainhas --> 2680 soluções // 12 rainhas --> 14200 soluções // 13 rainhas --> 73712 soluções // 14 rainhas --> 365596 soluções // ------------------------------ // para compilar na khuatro comentar as duas linhas que se // seguem e retirar os comentário das duas linhas seguintes #define CONFIG_SMP #include //#define __SMP__ //#include #include #include #include #include #include #include #define MMAP_ANSWERS_ADDR 0x02000000 #define MMAP_TASKS_ADDR 0x10000000 #define MMAP_ANSWERS_SIZE (N_QUEENS <= 9 ? 4096 : N_QUEENS == 10 ? 8192 : N_QUEENS == 11 ? 32768 : N_QUEENS == 12 ? 188416 : N_QUEENS == 13 ? 1032192 : 5484544) // tamanho mínimo para executar com 1 grupo #define MMAP_TASKS_SIZE (N_QUEENS == 8 ? 8192 : N_QUEENS == 9 ? 24576 : N_QUEENS == 10 ? 106496 : N_QUEENS == 11 ? 532480 : N_QUEENS == 12 ? 2904064 : N_QUEENS == 13 ? 16261120 : 98607104) // tamanho mínimo para executar com 1 grupo #define ABS(N) ((N) > 0 ? (N) : -(N)) #define N_QUEENS 10 #define N_GROUPS 1 #define WORKERS_PER_GROUP n_workers #define N_WORKERS N_GROUPS * WORKERS_PER_GROUP int n_workers; typedef struct { char len; // número de rainhas colocadas no tabuleiro char queens[N_QUEENS]; // posição (número da coluna) das rainhas } board; typedef struct { spinlock_t lock; // spinlock de acesso à fila de soluções board *first; // apontador para a primeira solução board *last; // apontador para a última solução } answers_pool; answers_pool *my_answers; #define lock_answers my_answers->lock #define first_answer my_answers->first #define last_answer my_answers->last typedef struct { spinlock_t lock; // spinlock de acesso à fila de tarefas void *start; // início da fila de tarefas void *end; // fim da fila de tarefas board *get; // apontador para a tarefa mais antiga board *put; // apontador para a tarefa mais recente int idle_workers; // número de processos sem trabalho int next_group; // próximo grupo onde colocar tarefas } tasks_group; typedef struct { spinlock_t lock; // spinlock de acesso a idle_groups int idle_groups; // número de grupos sem trabalho tasks_group tasks[N_GROUPS]; // fila de tarefas de cada grupo } tasks_pool; tasks_pool *my_tasks; #define lock_groups my_tasks->lock #define idle_groups my_tasks->idle_groups #define lock_tasks(N) my_tasks->tasks[N].lock #define start_tasks(N) my_tasks->tasks[N].start #define end_tasks(N) my_tasks->tasks[N].end #define get_task(N) my_tasks->tasks[N].get #define put_task(N) my_tasks->tasks[N].put #define idle_workers(N) my_tasks->tasks[N].idle_workers #define next_group(N) my_tasks->tasks[N].next_group void worker(int my_group); void getwork(int my_group, board *my_board); void putwork(int my_group, board *my_board); void new_answer(board *my_board); void show_answers(void); void mmap_init(char *file, void *start_addr, void *end_addr); double current_time(void); main (int argc, char **argv) { double execution_time; int i; // parsing da linha de comandos if (argc == 2) n_workers = atoi(argv[1]); else n_workers = 1; printf("o problema das %2d-rainhas: %d grupo(s) com %d agente(s) cada\n", N_QUEENS, N_GROUPS, WORKERS_PER_GROUP); // mapear o ficheiro 'answers_pool' num segmento de memória partilhada my_answers = (answers_pool *) MMAP_ANSWERS_ADDR; mmap_init("answers_pool", (void *)my_answers, (void *)my_answers + MMAP_ANSWERS_SIZE); spin_lock_init(&lock_answers); first_answer = last_answer = (board *)(my_answers + 1); // mapear o ficheiro 'tasks_pool' num segmento de memória partilhada my_tasks = (tasks_pool *) MMAP_TASKS_ADDR; mmap_init("tasks_pool", (void *)my_tasks, (void *)(my_tasks + 1) + MMAP_TASKS_SIZE); spin_lock_init(&lock_groups); idle_groups = 0; for (i = 0; i < N_GROUPS; i++) { spin_lock_init(&lock_tasks(i)); start_tasks(i) = get_task(i) = put_task(i) = (board *)((void *)(my_tasks + 1) + i * MMAP_TASKS_SIZE / N_GROUPS); end_tasks(i) = (void *)start_tasks(i) + MMAP_TASKS_SIZE / N_GROUPS; idle_workers(i) = 0; next_group(i) = (i + 1) % N_GROUPS; } // criar os restantes agentes e executar get_task(0)->len = -1; put_task(0)++; execution_time = current_time(); for (i = 1; i < N_WORKERS; i++) if (fork() == 0) { worker(i / WORKERS_PER_GROUP); return 1; } worker(0); execution_time = current_time() - execution_time; show_answers(); printf("tempo total de execução: %f segundos\n", execution_time); return 1; } void worker(int my_group) { int len, row, col, rowdist, coldist; board my_board; getwork(my_group, &my_board); while (my_board.len != N_QUEENS) { len = ++my_board.len; for (col = 0; col < N_QUEENS; col++) { for (row = 0; row < len; row++) { rowdist = ABS(len - row); coldist = ABS(col - my_board.queens[row]); if (coldist == 0 || coldist == rowdist) break; } if (row == len) { my_board.queens[len] = col; if (len + 1 == N_QUEENS) new_answer(&my_board); else putwork(my_group, &my_board); } } getwork(my_group, &my_board); } return; } void getwork(int my_group, board *my_board) { // ... return; } void putwork(int my_group, board *my_board) { // ... return; } void new_answer(board *my_board) { // ... return; } void show_answers(void) { int i, sol = 0; board *aux = first_answer; while (aux != last_answer) { sol++; /* printf("solução %d:", sol); for (i = 0; i <= aux->len; i++) printf(" %c", '0' + aux->queens[i]); printf("\n"); */ aux++; } printf("soluções encontradas: %d\n", sol); return; } void mmap_init(char *file, void *start_addr, void *end_addr) { int fd, size; size = end_addr - start_addr; if ((fd = open(file, O_RDWR | O_CREAT | O_TRUNC, S_IRUSR | S_IWUSR)) == -1) { printf("erro no open!\n"); exit(0); } if (lseek(fd, size, SEEK_SET) == -1) { printf("erro no lseek!\n"); exit(0); } if (write(fd, "", 1) == -1) { printf("erro no write!\n"); exit(0); } if (mmap(start_addr, size, PROT_READ | PROT_WRITE, MAP_SHARED | MAP_FIXED, fd, 0) == (void *)-1) { printf("erro no mmap!\n"); exit(0); } return; } double current_time(void) { struct timeval tempo; gettimeofday(&tempo, NULL); return ((double)tempo.tv_sec + (double)tempo.tv_usec / 1000000); }