Sistemas Operacionais, 1⁰ semestre/2004

Experimento # 5

1. Introdução

Nos experimentos prévios foram utilizados mecanismos de IPC (Inter-Process Communication) baseados em fila de mensagens, memória compartilhada, sinais e semáforos. Usando estes mecanismos foi possível compartilhar dados entre diferentes processos.

Processos, naturalmente, são independentes entre si em relação aos seus espaços de endereçamento de dados e aos seus contextos, enquanto compartilham uma ou mais CPUs do sistema, de maneira concorrente. Para compartilhar dados, processos necessitam de mecanismos de IPC para seu acesso e também para que esse acesso ocorra sob exclusão mútua, se houver condição de corrida.

Uma outra maneira de haver concorrência é através do uso de threads. Um thread é definido como uma linha (seqüência) de execução que pode ser concorrente a outras linhas, dentro de um mesmo processo, ao mesmo tempo que é capaz de acessar recursos comuns a todas as linhas desse processo.

Todo processo (programa em execução) é por definição uma thread, correspondente à rotina main(). Uma vez em execução, esta primeira thread pode criar outras threads que concorrerão com ela. Uma thread deverá ser a execução de uma rotina declarada no programa e disparada através de chamadas ao sistema apropriadas.

Uma thread, também denominada de processo-leve, passa a ser a unidade de escalonamento dentro do SO, com uma possível vantagem sobre o escalonamento baseado em processos: a de uma troca de contexto mais simples e, conseqüentemente, mais rápida. Além disso, o fato das threads de um mesmo processo poderem acessar os recursos comuns não requer necessariamente o uso de mecanismos de IPC para uma comunicação entre as mesmas.

Este experimento deverá permitir ao aluno familiarizar-se com threads, além de permitir-lhe saber diferenciar o conceito de processo com aquele de thread. Neste experimento também é visto o problema de produtores e consumidores, baseado em um buffer circular. Duas diferentes implementações são exploradas.

Este exercício foi definido especialmente para as aulas de Sistemas Operacionais, na Faculdade de Engenharia de Computação, na PUC-Campinas, com a ajuda do bolsista alemão Florian Weizenegger.

2. Objetivos

A seguir estão os objetivos deste experimento com relação ao aluno:

· Entender o conceito de thread.

· Observar como criar e manipular threads.

· Perceber como se dá a execução concorrente de threads.

· Entender a diferença entre thread e processo, explorando o acesso a uma estrutura de memória local ao processo.

· Explorar o problema dos Produtores e Consumidores usando um buffer circular.

· Permitir observar a necessidade de exclusão mútua também entre threads concorrentes.

3. Teoria

A seguir são discutidos conceitos diretamente relacionados com o experimento, sua leitura é importante e será cobrada quando da apresentação. Caso o entendimento desses conceitos não se concretize procure reler e, se necessário, realizar pequenas experiências de programação até que ocorra o entendimento.

Pode não ser claro o porque da distinção entre processos e threads, principalmente quando se considera que a concorrência pode ser obtida através do uso de comandos fork para a criação de novos processos.

Threads, no entanto, constituem uma interessante alternativa para a geração de concorrência. Desde que seja possível a sua utilização, threads apresentam vantagens sobre o uso de processos.

Threads são recomendáveis em situações em que pedaços de um mesmo processo podem ser executados concorrentemente. Caso uma solução resulte em um programa estritamente seqüencial, não há o porque do uso de threads. No entanto, se houver a necessidade da realização concorrente de tarefas, como é o caso da solução do problemas clássico dos produtores e consumidores, então threads permitem o compartilhamento das estruturas, variáveis e outros recursos globais que sejam declarados no processo, em a necessidade de mecanismo de IPC.

Todos as threads dentro de um mesmo processo podem acessar o mesmo espaço de endereçamento. Toda mudança aos recursos globais são visíveis a todas as threads do processo. Por exemplo, o fechamento de um arquivo ou a atribuição de um valor a uma variável global.

Um bom exemplo do poder das threads é o seu uso em um Sistema Gerente de Bancos de Dados, no qual múltiplas threads podem existir acessando os mesmos arquivos para tratar cada uma de uma consulta. A criação de uma nova thread para uma consulta siginifca que os dados do banco só necessitam ser carregados na memória uma única vez e esta thread como as demais podem acessá-los concorrentemente.

Threads são menores que processos em termos do seu contexto e por serem parte de um todo. Assim, sua criação e manipulação são relativamente mais baratas em termos de uso de CPU. Todo processo tem seu pacote de recursos entre arquivos, mescanismos e dados. Enquanto as threads, podendo compartilhar esses recursos, não exigem quase nada de memória. As threads têm seu próprio fluxo (linha) de execução com sua pilha, ponteiros e registradores, e acessam o diretório de trabalho, a área de heap e os descritores de arquivos do processo.

Outra razão para a popularidade das threads é a velocidade com que podem ter seus contextos trocados durante o escalonamento. O time-slice de um processo não é longo, tipicamente algo entre 100 e 200 mili-segundos. Uma vez que um processo tenha sido escalonado, sua carga na CPU pelo dispatcher é uma atividade demorada.

Uma troca de contexto para processos envolve não somente o salvamento do contexto do processo anterior e a carga do contexto do novo, como também pode acarretar na necessidade de esvaziamento (flush) da memória cache e da TLB (Translation Lookaside Buffer) e de seu preenchimento com as informações do novo processo. TLBs são usadas para afetar o endereçamento físico de memória a partir de um endereço lógico (assunto para aulas de Gerência de Memória), onde ficam armazenados endereçamentos anteriores que tiveram que ser computados, de maneira a permitir acessos mais rápidos à memória.

Caso um processo seja retirado da memória, se esta se encontra cheia e há necessidade de liberar espaço (swap out), muito provavelmente esse processo deverá retornar (swap in). Este procedimento não é muito demorado, possivelmente algumas dezenas de milisegundos em um rápido computador ou até demorado se acessos a disco forem necessários. Como a troca de contexto se realizando freqüentemente devido a um número elevado de processos, o tempo dedicado ao escalonador imporá mais lentidão à gerência de memória cheia.

Uma troca de contexto envolvendo threads, considerando threads de um mesmo processo, é muito mais rápida que outra entre processos. O que passa a ser necessário é a recomposição do estado da CPU. Para threads de um mesmo processo, tanto a cache como a TLB continuam válidas e não necessitam ter seu conteúdo trocado. A possibilidade de substituir uma solução baseada em processos para outra baseada em threads oferece a oportunidade para um ganho de tempo considerável (Processes and Threads http://www.dcs.gla.ac.uk/~ian/project3/node31.html).

Criando e Gerenciando Threads em C

Existe uma interface especificada pela IEEE Posix para threads na linguagem C que deu origem a um arquivo pthread.h com uma biblioteca.

Para a criação de threads, inicialmente é necessária a declaração de uma variável do tipo pthread_t. O tipo pthread_t permite a declaração de uma variável que recebe um id quando a thread é criada. Posteriormente, esse id pode ser usado em comandos de controle para threads. Dois dos principais comandos para respectivamente iniciar e terminar threads são:

pthread_create() permite a criação de uma thread que será a execução da rotina passada como parâmetro.

pthread_exit() indica o término da thread e pode ser usado para terminar a thread. Outra maneira de terminar é com o término da rotina concorrente que estava em execução.

Programa exemplo

O programa exemplo oferece uma solução para o conhecido problema dos produtores e consumidores que compartilham um buffer que é percorrido de maneira circular. O buffer, na realidade é um vetor onde produtores armazenam o que produzem e de onde consumidores retiram o que consomem. Elementos que sejam retirados do buffer deixam de existir. Elementos que são armazenados no buffer, eventualmente, podem deixá-lo cheio, sem espaço para novos armazenamentos.

Existem dois ponteiros que percorrem o buffer: (rp) que aponta para a posição do buffer onde deve ocorrer a próxima retirada (reading pointer); e (wp) que aponta para a posição do buffer onde deve ocorrer o próximo armazenamento (writing pointer).

Cada um dos ponteiros, uma vez tendo sido usados para retirar ou armazenar, tem seu valor incrementado, de maneira a poder apontar para a próxima posição do buffer, exceto se estiverem na última posição, situação em que são alterados para apontar para a primeira posição, ocasionando um efeito circular.

Duas rotinas são usadas para armazenar e retirar elementos do buffer: myadd() e myremove().

int myadd(int toAdd) {

//verificacao se o buffer nao esta cheio
if ((rp != (wp+1)) && (wp != rp + SIZEOFBUFFER - 1)) {
    *wp = toAdd;
    wp++;
    //verificacao se wp chegou a ultima posicao do buffer
    if (wp == (start + SIZEOFBUFFER)) {
      wp = start;               /* realiza a circularidade no buffer */
    }
    return 1;
} else return 0;
}

A rotina myadd(int toAdd) verifica primeiro se o buffer se encontra cheio. Estará cheio caso rp esteja uma posição além de wp (rp = wp + 1), ou caso wp esteja apontando a última posição do buffer e rp a primeira (wp = rp + SIZEOFBUFFER –1). Em um destes dois casos é retornado 0 sem haver o armazenamento do elemento.

Caso o buffer não esteja cheio, o elemento é armazenado na posição apontada por wp e este é incrementado. Após isto, é verificado se wp já atingiu o fim do buffer e, em caso positivo, este é posicionado no início.

A rotina myadd retorna 1 para indicar que o armazenamento foi realizado.

int myremove() {
//verificacao se o buffer nao esta vazio
if (wp != rp) {
    int retValue = *rp;
    rp++;
    //verificacao se rp chegou a ultima posicao do buffer
    if (rp == (start + SIZEOFBUFFER)) {
      rp = start;                /* realiza a circularidade no buffer */
    }
    return retValue;
} else return 0;
}

A rotina myremove(), diferente da rotina myadd(), verifica primeiro se o buffer se encontra vazio. Estará vazio caso rp esteja apontando a mesma posição que wp. Neste caso é retornado 0 sem haver a retirada de valor.

A rotina myremove() retorna o valor retirado caso tenha tido sucesso.

Dando uma olhada na rotina main(), percebe-se que pode haver a criação de diversas threads:

int main(int argc, char *argv[])
{
int tp, tc;
int i;

start = &buffer[0];
wp = start;
rp = start;

for (i=0;i<NUM_THREADS;i++) {

    // tenta criar um thread consumidor
    tc = pthread_create(&consumers[i], NULL, consume, (void *)i+1);
    if (tc) {
      printf("ERRO: impossivel criar um thread consumidor\n");
      exit(-1);
    }
    // tenta criar um thread produtor
    tp = pthread_create(&producers[i], NULL, produce, (void *)i+1);
    if (tp) {
      printf("ERRO: impossivel criar um thread rodutor\n");
      exit(-1);
    }
}
printf("Terminando o thread main()\n");
pthread_exit(NULL);
}

Inicialmente, os ponteiros para o buffer circular são incializados (wp e rp, além de start que sempre aponta para o início). Em seguida há um comando de repetição que depende do número de threads de rotinas para produtores e consumidores, que é um de cada, NUM_THREADS. O thread de produtor é criado com a rotina produce() como parâmetro, enquanto de o consumidor, com a rotina consume(). O resultado da chamada pthread_create() indica se a thread foi criada com sucesso (0) ou não (1).

Após a criação das threads, a rotina main() termina, através da chamada pthread_exit(). Como não há qualquer tipo de tratamento para status de fim de thread, NULL é usado como parâmetro.

void *produce(void *threadid)
{
int i = 0;
int sum = 0;
int ret = 0;

printf("Produtor #%d iniciou...\n", threadid);

while (i < NO_OF_ITERATIONS) {
    ret = myadd(10);
    if (ret) {
      i++;
      sum += 10;
    }
}
printf("Soma produzida pelo Produtor #%d : %d\n", threadid, sum);
pthread_exit(NULL);
}

Na rotina produce() ocorrem tentativas de armazenar o valor 10 no buffer. Algumas dessas tentativas podem não dar certo. De qualquer maneira, NUM_OF_ITERATIONS vezes será armazenado o valor 10. O contador i é o responsável de controlar que ocorram NUM_OF_ITERATIONS manipulações bem sucessidas no buffer. A rotina consume() segue a mesma lógica.

4. Resultado

Cada experimento constitui uma atividade que precisa de ser completada através de três tarefas básicas. Todas, diferentemente dos experimentos anteriores, se referem ao entendimento e à modificação e compilação de um programa exemplo que trata de assuntos relacionados com aqueles cobertos em sala de aula e na teoria.

Este experimento deve ser acompanhado de um relatório com as seguintes partes obrigatórias:

· Introdução, indicando, em não mais do que 20 linhas, quais os objetivos do experimento;

· Respostas às perguntas formuladas a seguir;

· Resultados das execuções dos programas modificados para teste e tarefas;

· Análise dos resultados;

· Conclusão indicando o que foi aprendido com o experimento.

A entrega do trabalho deve ocorrer através do envio de um e-mail "Encaminhando programa 5", de acordo com o cronograma previamente estabelecido. A data e hora limites correspondem à segunda-feira às 24:00, da semana marcada para entrega e apresentação. Anexos a esse e-mail devem constar:

· os programas fonte modificados para as tarefas,

· os correspondentes executáveis,

· o relatório final do trabalho e

· uma imagem do comando ls -l sobre os arquivos usados no experimento ao final do mesmo.

A falta de qualquer elemento no e-mail ou a perda da data de entrega implica na perda da nota correspondente. Somente duas exceções serão consideradas, o fechamento do laboratório durante o período disponibilizado para a realização do experimento, ou problema de doença avisado com antecedência mínima de dois dias antes da data da entrega.

Laboratório cheio, quedas de máquinas, falta de linha telefônica, problemas pessoais ou "blackouts" não serão aceitos como desculpas por atrasos. Por isso, recomenda-se fortemente que o início do trabalho ocorra o mais rapidamente possível.

Dica para compilação

A biblioteca pthread necessita ser adicionada quando da compilação dos programas que manipulam threads. Para isso use a seguinte diretiva:

gcc -o experiment-x2 -lpthread experiment-x2.c

Perguntas

Porque algumas das tentativas de armazenar em produce() e de retirar em consume() não dão certo?

Quantas vezes não foi possível armazenar valores no buffer?

E quantas vezes não foi possível retirar?

Quanto tempo demorou para todas as threads realizarem seus processamentos?

Tarefas

As tarefas para este experimento são:

primeiro, descrever o que ocorre com as threads criadas, se a rotina principal (main()) terminar sem ser através de pthread_exit().

segundo, fazer alterações no programa exemplo, de maneira a poder responder as perguntas anteriores; além disso, execute esse programa modificado com um número diferente de produtores e consumidores. Altere, para isso, o valor de NO_THREADS para múltiplos de cinco. Faça isso 10 vezes, sendo a primeira com NO_THREADS igual a um.

terceiro, nas execuções da segunda tarefa devem ser gerados resultados diferentes do esperado. Isso se deve a condição de corrida entre threads produtoras. Também deve ocorrer condição de corrida entre threads consumidoras. Determinar quais são as regiões críticas respectivamente na rotina produtora e na rotina consumidora, de maneira a estabelecer exclusão mútua com o uso de mutex. Para isso, utilize as chamadas pthread_mutex_init(), pthread_mutex_lock(), pthread_mutex_unlock() e pthread_mutex_destroy().

5. Apresentação

O resultado do experimento será apresentado em sala de aula no dia de aula prática da semana marcada para a entrega, com a presença obrigatória de todos os alunos, de acordo com o cronograma previamente estabelecido.

Serão escolhidos alunos para a apresentação e discussão do resultado. A critério do professor pode, inclusive, ocorrer o convite a qualquer dos alunos não escolhidos para que façam essa apresentação.

Todos os alunos que completaram o experimento devem preparar para a apresentação:

· Os programas exemplo e modificados;

· A introdução,

· Os resultados,

· A análise dos resultados, e

· A conclusão.

Durante a apresentação deverão ser respondidas perguntas do Professor e de colegas.