Sistemas Operativos 3º Ano MIEEC
Folha de Problemas nº 6: Semáforos

IMPORTANTE Para tirar mais proveito da resolução dos problemas de programação deverá compreender os conceitos teóricos subjacentes. O conjunto de questões que se segue, e que precede os problemas, tem por objetivo contribuir para essa compreensão. Assim, antes de resolver os problemas de programação deverá responder a estas questões.

Questões

  1. Explique como poderia usar uma variável do tipo sem_t de lipthread para garantir exclusão mútua no acesso a uma secção crítica.
  2. Considere a seguinte implementação de semáforos.
    typedef struct {
            pthread_mutex_t lock;
            unsigned int cnt;
    } my_sem_t;
    int my_sem_init(my_sem_t *sem, int n) {
            pthread_mutex_init(&(sem->lock), NULL);
            sem->cnt = n;
    }
    int my_sem_down(my_sem_t *sem) {
            pthread_mutex_lock(&(sem->lock));
            if( sem->cnt > 0 ) {
                     sem->cnt--;
                     pthread_mutex_unlock(&(sem->lock));
                     return 1;
            } else {
                     pthread_mutex_unlock(&(sem->lock));
                     return 0;
            }
    }
    int my_sem_up(my_sem_t *sem) {
            pthread_mutex_lock(&(sem->lock));
            sem->cnt++;
            pthread_mutex_unlock(&(sem->lock));
    }
    
    1. Qual a diferença principal entre a função my_sem_down() acima e a função sem_wait() do tipo sem_t de libpthread? Em que medida deverá o código que usa my_sem_down() diferir daquele que usa sem_wait()?
    2. Qual a diferença principal entre a função my_sem_up() acima e a função sem_post() do tipo sem_t de libpthread? Em que medida deverá o código que usa my_sem_up() diferir daquele que usa sem_post()?
    3. Qual a diferença principal entre my_sem_t e sem_t? Esta diferença afecta a eficiência do código? E a sua correcção?

Problemas

Nota

Para compilar os seus programas com a biblioteca libpthread deverá usar a opção -pthread do gcc na linha de comandos:

 gcc -pthread
  1. Considere a implementação do problema do bounded buffer com semáforos apresentada na aula teórica.
    1. Modifique-a para usar semáforos anónimos (e mutexes) POSIX.

      IMP. Use também uma variável de contagem cnt como no problema 2 da folha 5: é usada pela função check() check.c.

    2. Escreva um programa que teste a sua solução. O seu programa deverá ser análogo ao usado no problema 2 da folha 5. I.e., o thread principal deverá criar 3 threads produtores e outros 3 consumidores. Além destes deverá criar ainda um outro thread cuja função é verificar cada 100 ms se o bounded buffer foi corrompido devido a race conditions.

      Cada thread produtor deverá produzir 10 M items: inteiros com o seu identificador (entre 0 e 2). Além disso, deve imprimir uma mensagem no início e outra no fim da sua execução.

      De modo análogo, cada thread consumidor deve consumir 10 M items e manter o número de items consumidos que foram produzidos por cada um dos threads produtores. Além disso deve imprimir uma mensagem no início e outra no fim da sua execução. Nesta útlima deverá imprimir o número de items consumidos discriminados por thread produtor.

      Dica Pode também adaptar o programa que desenvolveu para o problema 2 da folha 5. Mas seja extremamente cuidadoso, doutra forma sujeita-se a introduzir bugs de difícil identificação.

    3. Compare os tempos de execução desta solução com aqueles que obteve nas soluções com mutexes. Tente explicar as diferenças observadas.
  2. Outro problema de concorrência clássico é o dos leitores-escritores (readers-writers). Um conjunto de threads/processos acedem a uma variável partilhada sendo que alguns deles, os leitores, executam apenas operações de leitura, enquanto que os restantes, os escritores, executam apenas operações de escrita.

    Atendendo a que as operações de leitura não interferem entre si, deve permitir-se a execução simultânea de várias operações de leitura para aumentar a concorrência. Pelo contrário, operações de escrita interferem quer com outras operações de escrita quer com operações de leitura pelo que deverão ser feitas em exclusão mútua. I.e. quando um escritor escreve na variável, nenhum outro processo, seja ele escritor ou leitor deverá aceder à variável partilhada.

    Neste problema pretende-se que resolva uma variante deste problema clássico usando semáforos anónimos POSIX. Em particular, há duas variáveis globais inteiras m e n as quais devem ser inicializadas a 0 pelo thread principal. O thread principal cria ainda 2 threads escritores e 2 threads leitores, e fica à espera que eles terminem. Após a terminação dos 4 threads o thread principal deve imprimir os valores finiais das 2 variáveis.

    Cada um dos threads escritores deverá executar um ciclo 50 milhões de vezes no qual incrementa em 1 cada uma das 2 variáveis, de modo a que o seu valor após cada iteração deverá ser idêntico e no final deverá ser de 100 milhões.

    Cada um dos threads leitores deverá executar um ciclo 50 milhões de vezes no qual lê as 2 variáveis, devendo imprimir os valores lidos em iterações múltiplas de 1 milhão. Pretende-se que os valores impressos das duas variáveis em cada iteração sejam idênticos.

    Nota: Quando há pelo menos um leitor a ler as variáveis, nenhum dos escritores deverá poder alterar o valor dessas variáveis, contudo é possível que outro leitor as leia. Uma questão crítica é:

    Se um leitor estiver a ler as variáveis e um escritor estiver bloqueado à espera para fazer a escrita, deverá ou não permitir-se que outro leitor inicie a sua leitura?
    As alternativas são claras:

    1. Sim. Neste caso maximiza-se a concorrência, mas os escritores podem ser continuamente preteridos a favor dos leitores. I.e. os escritores sofrem de mingua.
    2. Não. Neste caso a solução é mais equitativa mas pode reduzir a concorrência.
    Tente resolver o problema usando as duas estratégias (uma de cada vez). Os resultados observados são aqueles que esperava?
  3. Um algoritmo de ordenação de vetores particularmente apropriado para sistemas multi-processador/multi-core é o algoritmo merge-sort. A ideia deste algoritmo é partir o vetor a ordenar em subvetores disjuntos, i.e. sem elementos comuns. Fazer a ordenação destes subvetores separadamente (sort) e depois fundir (merge) cada par de subvetores já ordenados. Esta última ordenação é particularmente eficiente pois cada um dos subvetores está ordenado. Contudo, só pode ser iniciada depois dos 2 subvetores correspondentes terem sido ordenados.

    No algoritmo original, concebido para sistemas uniprocessador, o vetor a ordenar é partido em 2, e cada um dos 2 subvetores resultantes é ordenado e posteriormente fundidos. Na formulação recursiva, a ordenação é feita aplicando o algoritmo de novo, até ao tamanho do vetor a ordenar ter um único elemento, e consequentemente estar ordenado.

    Neste problema pretende-se que faça uma implementação de merge-sort para ordenar por ordem crescente um vetor com 1 milhão de inteiros. Este vetor é inicializado por ordem decrescente pelo thread principal, o qual deverá ainda criar outros threads para fazerem a ordenação. O nº de threads que realizam a ordenação deverá ser passado ao programa através dum argumento da linha de comando, devendo o thread principal também ordenar partes do vetor. A sua solução não precisa implementar o algoritmo merge-sort puro, mas deverá procurar maximizar a concorrência. Pode usar semáforos para sincronização entre threads

    Quando a ordenação tiver terminado, o thread principal deverá verificar se a ordenação foi ou não correctamente realizada.

    Sugestão: Comece por implementar o algoritmo merge-sort com um único thread. Este algoritmo deverá usar duas funções: sort() e merge(), sendo a última invocada pela primeira.


This document was translated from LATEX by HEVEA.