Processos, parte I

Background

O objectivo do exercício 3.1 é implementar um programa que inicie vários processos para procurar um número numa matriz. Cada um dos processos deve procurar numa das linhas da matriz. Para isso vamos usar a chamada ao sistema fork.

Consultando a página do manual do fork podemos ver que esta função cria uma cópia do processo actual. Esta cópia é praticamente igual em tudo ao nosso processo original. É exactamente o mesmo programa, tem exactamente o mesmo conteúdo na memória e até está a executar no mesmo ponto do código.

Criar um processo com fork é uma operação bastante leve. Isto porque é usada uma técnica chamada copy-on-write para efectuar esta cópia. Copy-on-write significa que quando invocamos fork, nada é copiado. O novo processo irá usar a mesma memória que o processo original estava a usar. Apenas quando um dos dois alterar uma parte da memória é que esta vai ser copiada para o novo.

Geralmente chama-se pai ao processo que invoca fork e filho ao processo que é criado pelo fork. No pai fork devolve o PID (process ID) do novo processo que foi criado. No filho devolve 0. É esta diferenciação, que nos permite correr código diferente no pai e no filho, com uma estrutura semelhante a esta:

pid_t pid = fork();
if(pid == 0)
{
   // filho
}
else
{
   // pai
}

Resolução

Esta vai ser a nossa matriz:

#define LINES 20
#define COLUMNS 100000

int matrix[LINES][COLUMNS]; 

Vamos então começar por escrever uma função que procura por um número numa linha e imprime esse número assim que o encontrar.

void find(int* line, int lineNr, int x)
{
   int i;
   for(i = 0; i < COLUMNS; i++)
   {
       if(line[i] == x)
           printf("%d found at line %d, column %d.\n", x, lineNr, i);
   }
} 

Bastante simples. Agora vamos criar um processo para cada linha. Desta forma podemos procurar em várias linhas ao mesmo tempo. Para isso vamos escrever um ciclo com a utilização típica do fork:

   int i;
   for(i = 0; i < LINES; i++)
   {
       pid_t pid = fork();
       if(pid == 0)
       {
           find(matrix[i], i, x);
           exit(0);
       }
   } 

Como o pai não tem nenhum código extra para correr, não existe else. Reparem também na utilização de exit. Se não tivessemos usado exit, cada processo filho iria procurar na respectiva linha, e depois continuava o ciclo, lançando mais processos. Esses novos processos iriam repetir esse erro e lançar ainda mais processos. No final teríamos perto de 20^20 processos!

Usando exit terminámos os processos-filho e podemos devolver um código de saída para indicar erros.

Agora só falta obtermos o número x, que é passado como argumento:

int main(int argc, char** argv)
{
   int x = atoi(argv[1]); 

E inicializar a matriz aleatóriamente:

    for(i = 0; i < LINES; i++)
       for(j = 0; j < COLUMNS; j++)
       {
           matriz[i][j] = rand() % 10;
       } 

Se correrem este código podem ver as várias ocorrências de um determinado número serem impressas. Reparem que as ocorrências são impressas fora de ordem. Isto deve-se ao facto de serem vários processos a procurar. No segundo exercício iremos forçar ordem nestes resultados.

Notas finais

Este exercício era pequeno e bastante simples. O segundo exercício adiciona um factor extra de confusão, mas não é nada do outro mundo.