sem_t
de lipthread
para garantir exclusão mútua no acesso a uma secção crítica.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)); }
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()
?
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()
?
my_sem_t
e sem_t
? Esta diferença afecta a eficiência do código? E a sua correcção?
Para compilar os seus programas com a biblioteca libpthread
deverá usar a opção -pthread
do gcc
na linha de comandos:
gcc -pthread
IMP. Use também uma variável de contagem cnt como no problema 2 da folha 5: é usada pela função check() check.c.
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.
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:
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.