Prof. Natalia Castro Fernandes Mestrado em Telecomunicações – UFF 2º semestre/2012 Introdução Processos Threads IPC – Interprocess Communication Memória Compartilhada Sockets Pipes Processos Processo Programa em execução Execução sequencial Inclui: Contador de programa Pilha Seção de dados O processo Memória Contém múltiplas partes ? Atividade atual, incluindo o contador de programa e os registradores de processo Pilha com dados temporários •Parâmetros de funções, endereço de retorno, variáveis locais Heap •Memória alocada dinamicamente Seção de dados Contém variáveis globais Código, também chamado de seção de texto Processos Programa x processo Programa é passivo Processo é ativo O programa se torna um processo quando é carregado na memória Sistema Operacional Busca programa no disco Execute A Usuário Processo é criado! Disco A Carrega programa na memória Memória Criando processos com o fork #include <sys/types.h> #include <studio.h> #include <unistd.h> int main() { pid_t pid; /* fork another process */ pid = fork(); if (pid < 0) { /* error occurred */ fprintf(stderr, "Fork Failed"); return 1; } else if (pid == 0) { /* child process */ execlp("/bin/ls", "ls", NULL); } else { /* parent process */ /* parent will wait for the child */ wait (NULL); printf ("Child Complete"); } return 0; } Exemplos em Python: teste_fork3.py até teste_fork7.py Atenção!!!!! O fork só funciona em Linux para Python Árvore de processos Finalização de processos Processo executa a sua última linha e pede ao sistema operacional para deletá-lo (exit) Recursos do processos são desalocados pelo sistema operacional Processo pai pode terminar a execução de um processo filho (abort) Exemplos de motivação Processo filho excedeu os recursos alocados Tarefa passada ao filho não é mais necessária Processo pai está sendo finalizado, e alguns sistemas operacionais não permitem que o filho continue executando após o pai ter sido finalizado Finalização em cascata Threads Threads são processos leves Diferentes tarefas da aplicação podem ser implementadas como threads separados Aplicável apenas às tarefas que possam ser paralelizadas Exemplos: Atualizar o display Buscar dados Verificar correção ortográfica Motivação A criação de processos é muito custosa Criação de threads é mais simples Vantagens do uso de threads Simplificação do código Aumento da eficiência Processos mono e multithreads Benefícios Melhora o tempo de resposta • Programa continua executando mesmo que algum thread seja bloqueado (thread no espaço de kernel) Compartilhamento por padrão dos recursos do processo • Não precisa de técnicas para criar uma memória compartilhada É mais simples criar um thread do que um processo • Não precisa alocar novos recursos e é fácil trocar contexto entre threads Aumenta o paralelismo • Em máquinas com multiprocessamento Programação com múltiplos cores Sistemas com múltiplos cores impulsionam novas formas de programar Maior eficiência na execução de programas Contudo, existem algumas dificuldades É possível paralelizar? As tarefas paralelizáveis tem a mesma importância? Quais conjuntos de dados pertencem a cada thread? Se duas threads usam dados dependentes, como sincronizar o acesso? Como depurar o processo, se existem múltiplos caminhos de execução? Threads Exemplos Ex_sem_thread.py Ex_sem_thread_processo.py Ex_thread.py Ex_threadv2.py Ex_thread_mais_legal.py Ex_thread_mais_legal_completo.py Ex_legal_final.py Comunicação interprocessos Processos em um sistema podem ser independentes ou cooperativos Processos cooperativos podem afetar ou serem afetados por outros processos Processos independentes não podem afetar ou serem afetados pela execução de outro processo Razões para cooperação interprocessos Compartilhamento de dados Aumento da velocidade de computação Modularidade Conveniência Comunicação interprocessos Cooperação entre processos depende da interprocess communication (IPC) Dois modelos de IPC Memória compartilhada Troca de mensagens Modelos de comunicação Envio de mensagens Memória compartilhada Sincronização Envio de mensagens pode ser tanto blocante quanto nãoblocante Operação blocante é considerada síncrona O send blocante bloqueia o emissor até que a mensagem seja recebida O receive blocante bloqueia o receptor até que a mensagem esteja disponível Operação não-blocante é considerada assíncrona O emissor envia a mensagem e continua O receptor recebe uma mensagem válida ou nulo Exemplos em Python Compartilhamento de variáveis shared_mem.py a shared_memv3.py OBS: Multiprocessing – API para processos cooperativos Queue() – Cria fila compartilhada put(), get() Process(codigo do novo processo, argumentos) start(), is_alive() Exemplos em Python Compartilhamento de variáveis shared_memv4.py Multiprocessing Value(tipo, valor) --- compartilhando um número Array(tipo,lista) Join() – Bloqueia o pai até o filho terminar Shared_memv4b.py Comunicação em sistemas clienteservidor Sockets Pipes Sockets Um socket é definido como um ponto de extremidade para a comunicação Concatenação de IP e porta Exemplo: O socket 161.25.19.8:1625 se refere a porta 1625 no host 161.25.19.8 A comunicação consiste de um par de sockets Exemplos em Python Socket Socket-client.py e socket-server.py Socket-client-udp.py e socket-server-udp.py Socket-client.py e socket-server-multiple.py Pipe Atua como um condutor permitindo que dois processos se comuniquem Pipes comuns permitem a comunicação em um estilo produtor-consumidor padrão Funcionamento O produtor escreve em uma ponta do pipe O consumidor lê a saída na outra ponta Portanto, pipes comuns são unidirecionais Requerem relação de pai-filho entre processos comunicantes Pipes nomeados Pipes nomeados são mais potentes que pipes comuns Comunicação bidirecional Não há necessidade de relação pai-filho Pode ser usado por diversos processos Disponível tanto em UNIX quanto em Windows Exemplos em Python Pipe Ex-pipe.py Acesso Concorrente Acesso concorrente a um dado compartilhado pode resultar em inconsistência Para manter a consistência, é preciso garantir uma execução ordenada dos processos cooperativos (que estão interagindo por meio de uma estrutura compartilhada) Estudo da concorrência entre processos através de modelos Exemplo: Produtor-consumidor Problema do Produtor-Consumidor Produtor e consumidor são dois processos distintos O produtor produz e coloca o produto no buffer O consumidor consome produtos que estão no buffer Consequências O buffer passa a ser uma estrutura compartilhada O produtor não pode colocar um produto em um buffer cheio O consumidor não pode consumir um produto se o buffer estiver vazio A variável compartilhada count pode ser usada para saber o número de elementos no momento dentro do buffer Eventualmente, o count pode ser atualizado simultaneamente pelo produtor e pelo consumidor Atualização não é uma tarefa atômica (indivisível) Produtor def produtor(): seed() global count i=0 while (True): sleep(random())#Tempo para simular o processo produzindo a informação if count<BUFFER_SIZE: buffer.append(str(i)) count = count +1 i=i+1 else: while (count>=BUFFER_SIZE): pass Consumidor def consumidor(): seed() global count while (True): if count>0: buffer.pop(0) count = count -1 sleep(random()) #Tempo para simular o processo consumindo a informação else: while(count<=0): pass Condição de disputa O incremento do contador pode ser implementado da seguinte forma: register1 = counter register1 = register1 + 1 counter = register1 O decremento do contador, por sua vez, seria: register2 = counter register2 = register2 - 1 count = register2 Condição de disputa Suponha que, no momento, count=5 e que o produtor e o consumidor estão sendo executados: t0: produtor: register1 = counter {register1 = 5} t1: produtor: register1 = register1 + 1 {register1 = 6} t2: consumidor: register2 = counter {register2 = 5} t3: consumidor: register2 = register2 - 1 {register2 = 4} t4: produtor: counter = register1 {count = 6 } t5: consumidor: counter = register2 {count = 4} Condição de disputa Definição Situação em que várias tarefas acessam dados concorrentemente e o resultado da execução depende da ordem específica em que o acesso ocorre Condição de disputa Solução para a condição de disputa: Sincronização de processos Proteção das seções críticas Uma seção crítica (ou região crítica) é um trecho de código no qual a tarefa está alterando uma estrutura compartilhada (variáveis compartilhadas, tabelas, arquivos, etc.) Dessa forma, se um processo entra na sua seção crítica, nenhum outro processo que compartilhe alguma estrutura pode ser autorizado a entrar na sua seção crítica Problema da seção crítica Problema de como controlar o acesso às seções críticas de processos que compartilham dados Ideia: Criar um protocolo de acesso Processo pede autorização para entrar na seção crítica Quando autorizado, processo executa seção crítica Processo avisa que terminou sua seção crítica Processo continua a sua execução Problema da seção crítica A entra na região crítica A deixa a região crítica Processo A B entra na região crítica B tenta entrar na região crítica Processo B B deixa a região crítica B bloqueado T1 T2 T3 T4 Soluções para o problema da região crítica 1. Exclusão mútua Nunca dois processos podem estar simultaneamente em suas regiões críticas 2. Progresso Nenhum processo fora da sua região crítica pode bloquear outros processos 3. Espera limitada Nenhum processo deve esperar eternamente para entrar em sua região crítica Nada pode ser afirmado sobre a velocidade de processamento ou sobre o número de CPUs disponíveis Revendo o Produtor-consumidor Qual é/são as seções críticas do código? Uso da variável count Uso da variável buffer Consumidor def consumidor(): seed() global count while (True): if count>0: buffer.pop(0) count = count -1 sleep(random()) #Tempo para simular o processo consumindo a informação else: while(count<=0): pass Seção crítica Revendo o Produtor-consumidor Produtor def produtor(): seed() global count i=0 while (True): sleep(random())#Tempo para simular o processo produzindo a informação if count<BUFFER_SIZE: buffer.append(str(i)) Seção crítica count = count +1 i=i+1 else: while (count>=BUFFER_SIZE): pass Revendo o Produtor-consumidor if __name__ == '__main__': ###Programa principal print "Esse programa simula o problema do produtor-consumidor, utilizando uma lista compartilhada por n threads: os produtores e os consumidores" print "Está se utilizando o método da espera ocupada." count = 0 prod=20 #Numero de produtores cons= 20 #Numero de consumidores t=[1]*(prod+cons) #Inicio o número de threads for i in range(prod): t[i] = Thread(target=produtor, args=()) t[i].start() for i in range(prod,prod+cons): t[i] = Thread(target=consumidor, args=()) t[i].start() while (True): if (len(buffer) != count): print "ERRO!!!!, pois tamanho do buffer = %d e count = %d" % (len(buffer),count) sleep (0.1) Seção crítica if (len(buffer)>10): print "ERRO!!!!, pois o buffer estourou!!!" Seção crítica Revisão Como proteger a seção crítica? Enquanto um produtor está na seção crítica, nenhum outro produtor ou consumidor pode entrar na seção crítica Seção crítica = seção aonde se atualiza ou se compara as variáveis compartilhadas Enquanto um consumidor está na seção crítica, nenhum outro consumidor ou produtor pode entrar na seção crítica Semáforos wait (S) { while S <= 0 ; // no-op S--; Signal e wait } Operações atômicas na modificação do semáforo Modificam o valor do sinal int sinal=1; wait(sinal); Região crítica; signal (sinal); Se S=1, decrementa S e pode entrar. Caso contrário, fica esperando em espera ocupada Espera ocupada = espera usando CPU signal (S) { S++; } Deadlock Deadlock – Acontece quando dois ou mais processos estão esperando por um evento que só poderia ser executado por um dos processos em espera Exemplo Imagine que S e Q são dois semáforos inicializados em 1 P0 wait (S); wait (Q); P1 wait (Q); wait (S); . . . . . . signal (S); signal (Q); signal (Q); signal (S); Resolvendo o Produtor-Consumidor Buffer de tamanho N Semáforo mutex inicializado em 1 Semáforo full inicializado em 0 Semáforo empty inicializado em N Controla o acesso ao buffer Controla o número de espaços ocupados no buffer Controla o número de espaços vazios no buffer Resolvendo o Produtor-Consumidor Produtor do { // produce an item in nextp wait (empty); wait (mutex); // add the item to the buffer signal (mutex); signal (full); } while (TRUE); Espera ter um vazio para usar e usa Pede acesso ao buffer Não pode trocar a ordem! Libera o acesso ao buffer Aumenta o número de espaços ocupados Resolvendo o Produtor-Consumidor The structure of the consumer process Espera ter um cheio para usar e usa do { wait (full); wait (mutex); Pede acesso ao buffer // remove an item from buffer to nextc signal (mutex); signal (empty); // consume the item in nextc } while (TRUE); Libera o acesso ao buffer Aumenta o número de espaços vazios Semáforos e Locks em Python threading.Lock() Retorna um objeto do tipo lock Usa acquire() e release() Uma vez que um thread dê um acquire, os demais threads que tentarem fazer o acquire ficarão bloqueados até que o thread dê um release Apenas um é liberado e os demais, caso existam, ficam na fila threading.RLock() Semelhante ao Lock, mas um mesmo thread pode pedir o Rlock mais de uma vez sem se auto-bloquear. Contudo, o número de releases precisa ser igual ao número de acquires para liberar o Lock Exemplos em Python Ex_threadv2.py Ex-thread-lock.py Ex-thread-lockv2.py Ex-thread-lockv3.py Ex-thread-lockv4.py Semáforos e Locks em Python threading.Semaphore([value]) Retorna um objeto do tipo semáforo Recebe um valor inicial do contador e bloqueará apenas quando o número ficar negativo Valor padrão do contador é 1 threading.BoundedSemaphore([value]) Semelhante ao Semaphore, mas garante que o valor inicial nunca será excedido. Valor padrão do contador é 1 Exemplos em Python Ex-semaphore.py Ex-semaphorev2.py Ex-semaphorev3.py Ex-semaphorev4.py Ex-semaphorev5.py Exemplo produtor-consumidor Produtor-consumidor.py Produtor-consumidor-processv3.py Produtor-consumidor-processv4.py Exercícios Quatro processos externos transmitirão informações de temperatura para um processo central, que por sua vez responderá com sua própria informação de temperatura e indicará se o processo inteiro se estabilizou. Cada processo externo receberá sua temperatura inicial na criação e recalculará uma nova temperatura de acordo com a fórmula: Nova_temp_ext = (temp_ext*3+2*temp_central)/5 O processo central recalcula a temperatura pela fórmula: Nova_temp_central = (2*temp_central+4_temperaturas_ext_recebidas)/6 Inicialmente, cada processo externo enviará sua temperatura para o processo central. Se as temperaturas enviadas pelos 4 processos na última iteração forem iguais, então o sistema se estabilizou. O processo central deve avisar aos demais que concluiu sua execução e qual foi a temp_central estabilizada e terminará. Os demais processos deverão imprimir a informação recebida na tela e terminar. Enquanto o sistema não estiver estável, o processo central deverá enviar, no fim de cada iteração, o valor da temperatura central para cada um dos processos e esperará suas respostas. Implemente esse sistema utilizando processos e sockets. Adaptado do livro “Fundamentos de Sistemas Operacionais” Exercícios Repita o problema anterior, usando memória compartilhada ao invés de socket. Nesse caso, não existirá processo central. Uma estrutura deverá ser compartilhada, contendo a temperatura atual de cada processo e uma temperatura central. Cada processo, ao perceber que as temperaturas se igualaram, deve escrever na tela o valor da temperatura final e terminar. É importante garantir que a estrutura só será lida ou atualizada por um processo de cada vez. Exercícios Repita o problema anterior, tirando o controle de acesso de leitura e escrita às variáveis compartilhadas. Execute o programa e diga se o controle foi importante ou não e porquê. Exercício Faça um servidor resolver de DNS simplificado, utilizando threads. Cada conexão recebida deverá ser tratada por um novo thread. O servidor receberá do cliente um nome e deverá retornar, via socket, o IP correspondente. Use a função socket.gethostbyname(hostname) para traduzir os nomes em IP. Exercício Explique o que é mutex. Explique e demonstre como um semáforo pode ser usado para criar um mutex. Explique e demonstre como um semáforo pode ser usado para controlar um número de elementos.