of 53 /53
Memória Compartilhada

Memória Compartilhada. Programação com memória compartilhada Nos sistemas multiprocessadores com memória compartilhada, qualquer localização da memória

Embed Size (px)

Text of Memória Compartilhada. Programação com memória compartilhada Nos sistemas multiprocessadores com...

  • Memria Compartilhada

  • Programao com memria compartilhadaNos sistemas multiprocessadores com memria compartilhada, qualquer localizao da memria pode ser acessada por qualquer processadorExiste um espao de endereamento nico, ou seja, cada localizao de memria possui um nico endereo dentro de uma extenso nica de endereos

  • Arquitetura com barramento nicoBarramentoCacheProcessadoresMdulos de memria

  • Alternativas para programaoUtilizar uma nova linguagem de programaoModificar uma linguagem seqencial existenteUtilizar uma linguagem seqencial existente com rotinas de bibliotecasUtilizar uma linguagem de programao seqencial e deixar a cargo de um compilador paralelizador a gerao de um cdigo paralelo executvelProcessos UNIXThreads (Pthreads, Java, ...)

  • Algumas linguagens de programao paralelas

    Linguagem

    Criador/data

    Comentrios

    Ada

    Depto. de defesa americano

    Nova linguagem

    C*

    Thinking Machines, 1987

    Extenso a C para sistemas SIMD

    Concurrent C

    Gehani e Roome, 1989

    Extenso a C

    Fortran F

    Foz et al., 1990

    Extenso a Fortran para programao por paralelismo de dados

    Modula-P

    Branl, 1986

    Extenso a Modula 2

    Pascal concorrente

    Brinch Hansen, 1975

    Extenso ao Pascal

  • Criao de processos concorrentes utilizando a construo fork-joinPrograma principalFORKJOINFORKFORKJOINJOINJOIN

  • Processos UNIXA chamada do UNIX fork() cria um novo processo, denominado processo filhoO processo filho uma cpia exata do processo que chama a rotina fork(), sendo a nica diferena um identificador de processo diferenteEsse processo possui uma cpia das variveis do processo pai inicialmente com os mesmos valores do paiO processo filho inicia a execuo no ponto da chamada da rotinaCaso a rotina seja executada com sucesso, o valor 0 retornado ao processo filho e o identificador do processo filho retornado ao processo pai

  • Processos UNIXOs processos so ligados novamente atravs das chamadas ao sistema:wait(status): atrasa a execuo do chamador at receber um sinal ou um dos seus processos filhos terminar ou pararexit(status): termina o processoCriao de um nico processo filhopid = fork();cdigo a ser executado pelo pai e filhoif (pid == 0) exit (0); else wait (0)Filho executando cdigo diferentepid = fork();if (pid == 0) { cdigo a ser executado pelo filho} else { cdigo a ser executado pelo pai}if (pid == 0) exit (0); else wait (0);

  • ThreadsArquivosIPPilhaCdigoHeapRotinas de interrupoProcessos: programas completamente separados com suas prprias variveis, pilha e alocao de memriaArquivosIPPilhaCdigoHeapRotinas de interrupoIPPilhaThreads: as rotinas compartilham o mesmo espao de memria e variveis globais

  • PthreadsInterface portvel do sistema operacional, POSIX, IEEEPrograma principalpthread_create(&thread1, NULL, proc1, &arg);pthread_join(thread1, NULL, &status);thread1proc1(&arg);{return(&status);}

  • Barreira para PthreadsA rotina pthread_join() espera pelo trmino de uma thread especficaPara criar uma barreira para esperar pelo trmino de todas as threads, pode-se repetir a chamada da rotina:for (i = 0; i < n; i++) pthread_create(&thread[i], NULL, (void *) slave, (void *) &arg); . .for (i = 0; i < n; i++) pthread_join(thread[i], NULL);

  • Threads desunidasUma thread no precisa saber do trmino de uma outra por ela criada, ento no executa-se a operao de unioPrograma principalpthread_create();pthread_create();Threadpthread_create();ThreadThreadTrminoTrminoTrmino

  • Ordem de execuo das instruesAs execues das instrues dos processos/threads individuais podem ser entrelaadas no tempoExemplo:Processo 1Processo 2Instruo 1.1Instruo 2.1Instruo 1.2Instruo 2.2Instruo 1.3Instruo 2.3

    Possvel ordem de execuo no tempo:Instruo 1.1Instruo 1.2Instruo 2.1Instruo 1.3Instruo 2.2Instruo 2.3

  • Ordem de execuo das instruesSe dois processos devem imprimir mensagens, por exemplo, as mensagens podem aparecer em ordens diferentes dependendo do escalonamento dos processos que chamam a rotina de impressoOs caracteres individuais de cada mensagem podem aparecer uns inseridos entre outros, caso as instrues de mquina das instncias da rotina de impresso sejam divididas em passos menores que possam ser interrompidos

  • Otimizaes do compilador/processadorO compilador ou processador pode reordenar as instrues para tentar otimizar a execuoExemplo:As instrues abaixoa = b + 5;x = y + 4;podem ser executadas em ordem contrria:x = y + 4;a = b + 5;e o programa continua logicamente correto

  • Rotinas seguras para threadsAs chamadas ao sistema ou rotinas de bibliotecas so denominadas seguras para threads, quando elas podem ser acionadas por vrias threads ao mesmo tempo e sempre produzem resultados corretosRotinas padro de E/S: imprimem mensagens sem permitir interrupo entre impresso de caracteresRotinas que acessam dados compartilhados os estticos requerem cuidados especiais para serem seguras para threadsPode-se forar a execuo da rotina somente por uma thread de cada vez, ineficiente

  • Acessando dados compartilhadosConsidere dois processos que devem ler o valor de uma varivel x, somar 1 a esse valor e escrever o novo valor de volta na varivel x

    Instruox = x + 1Processo 1ler xcalcular x + 1escrever xProcesso 2ler xcalcular x + 1escrever xtempo

  • Conflito em acesso a dados compartilhadosVarivel compartilhada, xProcesso 1Processo 2LerLerEscreverEscrever

  • Seo crticaDevem existir mecanismos para assegurar que somente um processo possa acessar um determinado recurso durante um certo tempoEstabelecem-se sesses de cdigo que envolvem o recurso, denominadas sees crticas, e organiza-se o acesso a elas de tal modo que somente uma delas pode ser executada por um processo de cada vezUm processo impede que outros processos acessem as sees crticas que possui um determinado recurso compartilhado quando ele estiver acessandoQuando um processo finaliza a execuo da seo crtica, outro processo pode execut-laMecanismo conhecido como excluso mtua

  • LockMecanismo mais simples de assegurar excluso mtua para acesso a sees crticasO lock uma varivel de 1 bit que possui o valor 1 quando existe algum processo na seo crtica e 0 quando nenhum processo est na seo crticaUm processo que chega a uma porta da seo crtica e a acha aberta pode entrar, trancando-a para prevenir que nenhum outro processo entreAssim que o processo finaliza a execuo da seo crtica, ele destranca a porta e sai

  • Spin lockwhile (lock == 1) do_nothing;lock = 1; . seo crtica .lock=0;

    Processo 1Processo 2

    while (lock == 1) do _nothing;while (lock == 1) do_nothing;lock =1;

    seo crtica

    lock=0;lock = 1;

    seo crtica

    lock = 0;

  • Rotinas de lock para PthreadsOs locks so implementados com variveis lock mutuamente exclusivas, ou variveis mutexPara utiliz-la, deve-se declar-la com o tipo pthread_mutex_t e iniciali-la:pthread_mutex_t mutex1;..pthread_mutex_init(&mutex1, NULL);Uma varivel mutex pode ser destruda utilizando-se a rotina pthread_mutex_destroy()

  • Rotinas de lock para PthreadsUma seo crtica pode ser protegida utilizando-se pthread_mutex_lock() e pthread_mutex_unlock()pthread_mutex_lock(& mutex1);.seo crtica .pthread_mutex_unlock(&mutex1);Se uma thread chega em uma rotina de trancamento de uma varivel mutex e a encontra trancada, ela espera at que seja destrancadaSe mais de uma thread est esperando o destrancamento, o sistema escolhe aquela que poder prosseguirSomente a thread que tranca uma varivel pode destranc-la

  • DeadlockPode ocorrer com dois processos quando um deles precisa de um recurso que est com outro e esse precisa de um recurso que est com o primeiro

    R1R2P1P2ProcessoRecurso

  • DeadlockPode ocorrer em modo circular com vrios processos possuindo um recurso necessrio a um outro

    R1R2P1P2Rn-1RnPn-1Pn

  • Rotina para evitar deadlock em PthreadsPthreads oferece uma rotina para testar se uma varivel est trancada sem bloquear a threadpthread_mutex_trylock()tranca uma varivel mutex que esteja destrancada e retorna o valor 0, ou retorna o valor EBUSY caso a varivel esteja trancada

  • SemforosUm semforo s um inteiro positivo (incluindo o 0) operado por duas operaes denominadas P e VOperao P(s)espera at que s seja maior que 0, a decrementa de 1 e permite que o processo continue a sua execuoOperao V(s)incrementa s de 1 para liberar algum processo que esteja esperandoAs operaes P e V so executadas de forma indivisvelMecanismo de espera implcito nas operaesOs processo atrasados por P(s) so mantidos parados at serem liberados por uma operao V(s) sobre o mesmo semforo

  • Excluso mtua de sees crticasPode ser implementada atravs de um semforo binrio, que s assume os valores 0 e 1Funciona como uma varivel lock mas as operaes P e V incluem um mecanismo de escalonamento de processosO processo inicializado com o valor 1, indicando que nenhum processo est na sua seo crtica associada ao semforo

  • Semforo geralPode ter qualquer valor positivoPode fornecer, por exemplo, um modo de registrar o nmero de unidades do recurso disponveis ou no disponveis e pode ser utilizada para resolver problemas de consumidor/produtorRotinas de semforo existem para processos UNIXNo existem para Pthreads, somente para extenso de tempo real

  • MonitorUm conjunto de procedimentos que fornecem o nico mtodo de acessar um recurso compartilhadoOs dados e operaes que podem ser executadas sobre os dados so encapsulados em uma estruturaA leitura e escrita de dados s podem ser feitas utilizando-se procedimentos do monitor, e somente um processo pode utilizar um procedimento de monitor em qualquer instanteUm procedimento de monitor pode ser implementado utilizando-se semforosmonitor_proc1(){ P(monitor_semaphore); . Corpo do monitor . V(monitor_semaphore); return;}

  • Variveis de condioFreqentemente, uma seo crtica deve ser executada caso exista uma condio especfica, por exemplo, o valor de uma varivel chegou a um determinado valorUtilizando-se locks, a varivel global tem que ser freqentemente examinada dentro da seo crticaConsome tempo de CPU e podem no funcionar direitoUtilizam-se variveis de condio

  • Operaes para variveis de condioTrs operaes:wait(cond_var) - espera que ocorra a condiosignal(cond_var) - sinaliza que a condio ocorreustatus(cond_var) - retorna o nmero de processos esperando pela condioA rotina wait() libera o semforo ou lock e pode ser utilizada para permitir que outro processo altere a condioQuando o processo que chamou a rotina wait() liberado para seguir a execuo, o semforo ou lock trancado novamente

  • Operaes para variveis de condio (exemplo)Considere um ou mais processos (ou threads) designados a executar uma determinada operao quando um contador x chegue a zeroOutro processo ou thread responsvel por decrementar o contadoraction()contador(){{.. lock(); lock(); while (x != 0) x--;wait(s); if (x == 0) signal (s); unlock(); unlock(); take_action(); .}}

  • Variveis de condio em PthreadsAssociadas com uma varivel mutex especficaDeclaraes e inicializaes:pthread_cond_t cond1;pthread_mutex_t mutex1;pthread_cond_init(&cond1, NULL);pthread_mutex_init(&mutex1, NULL);Utilizao das rotinas de wait e signal:action() contador(){ {. . pthread_mutex_lock(mutex1); pthread_mutex_lock(&mutex1); while (c 0) c--; pthread_cond_wait(cond1, mutex1); if (c == 0) pthread_cond_signal(cond1); pthread_mutex_unlock(&mutex1); pthread_mutex_unlock(&mutex1); take_action(); .} }

  • Construes de linguagens para paralelismoDeclarao de dados compartilhadosshared int xConstruo par, para especificar execues de instrues concorrentespar { S1; S2; . . Sn; }

  • Construes forallPara iniciar execues de mltiplos processos conjuntamente:forall (i = 0; i , n; i++) { S1; S2; . Sn; }Geram-se n processos cada um executando as instrues que formam o corpo do loop for, S1, S2, ..., Sn e cada processo utiliza um valor diferente para iExemplo para colocar o valor 0 em a[0], a[1], a[2], a[3], a[4] concorrentemente:forall (i = 0; i < 5; i++) a[i] = 0;

  • Anlise de dependnciaIdentificao dos processos que podem ser executados em conjuntoNo cdigo abaixo, a instruo do corpo do forall independente de todas as outras e todas podem ser executadas de forma independenteNo entanto, pode a identificao de dependncia pode no ser to bvia, necessitando-se de algoritmos de reconhecimento de dependncia para compiladores paralelizadores

  • Condies de BernsteinConjunto de condies suficientes para determinar se dois processos podem ser executados simultaneamenteSejam Ii o conjunto de localizaes de memria lidas por um processo Pi e Oj o conjunto de localizaes alteradas pelo processo PjTrs condies suficientes para que dois processos P1 e P2 sejam executados concorrentementeI1 O2 = I2 O1 = O1 O2 =

  • Exemplo das condies de BernsteinSuponha as duas instrues em C:a = x + y;b = x + z; Temos:I1 = (x,y) O1 = (a)I2 = (x,z) O1 = (b)

    Existem as trs condies suficientes para que dois processos P1 e P2 sejam executados concorrentementeI1 O2 = I2 O1 = O1 O2 =

  • Dados compartilhados em sistemas com cachesA memria cache uma memria com velocidade de acesso alto para armazenar dados e cdigo recentemente referenciadosProtocolos de coerncia da cachepoltica de atualizao: a cpia dos dados de todas as caches atualizada quando uma delas alteradapoltica de invalidao: quando uma das cpias alterada, o mesmo dado em outra cache invalidado e essas cpias so atualizadas somente quando o processador associado a ela referenciar o dado

  • Compartilhamento falsoPartes diferentes de um bloco de dados utilizadas por processadores diferentesSe um processador escrever em uma parte do bloco, a cpia de todo bloco deve ser invalidada ou atualizada nas caches dos outros processadoresMemria principal76543210BlocoTag de endereoCacheProcessador 1Bloco na cacheCacheProcessador 2

  • Soluo para compartilhamento falsoO compilador deve alterar a distribuio dos dados armazenados na memria, colocando dados alterados por um nico processador em blocos diferentes

  • Exemplos de programasSomar os elementos de um array, a[1000]int sum, a[1000]sum = 0;for (i = 0; i < 1000; i++)sum = sum +a[i];

  • Exemplo utilizando processos UNIXO clculo dividido em duas partes, uma para a soma dos elementos pares e outra para os mparesProcesso 1Processo 2sum1 = 0sum2 = 0for (i = 0; i < 1000; i = i+2)for (i = 1; i < 1000; i= i+2)sum1 = sum1 + a[i] sum2 = sum2 + a[i]Cada processo soma o seu resultado (sum1 ou sum2) a uma varivel compartilhada sum que acumula o resultado e deve ser ter seu acesso protegidoEstrutura de dados utilizadaArray a[]sumaddr

  • #define array_size 1000extern char *shmat()void P(int *s);void V(int *s);int main(){int shmid, s, pid;cahr *shm;int *a, *addr, *sum;int partial_sum;int i;init init_sem_value =1 ;s = semget(IPC_PRIVATE, 1, (0600 | IPC_CREAT));if (s == -1) { perror(semget); exit(1);}if semctl(s, 0, SETVAL, init_sem_value) < 0) { perror(semctl); exit(1);}shmid = shmget(IPC_PRIVATE, (array_size*sizeof(int)+1), IPCCREAT|0600);if (shmid == -1) { perror(shmget); exit (1);}shm = shmat(shmid, NULL, 0);if (shm == (char*)-1) { perror(shmat); exit(1);}

  • addr = (int *) shm;sum = addr;addr++;a = addr;*sum = 0;for (i = 0; i < array_size; i++) *(a+i) = i+1;pid = fork();if (pid ==0) { partial_sum=0; for (i=0; i
  • void P(int *s){ struct sembuf sembuffer, *sops; sops = &sembuffer; sops->sem_num=0; sops->sem_op=-1; sops->sem_flg=0; if (semop(*s, sops, 1) < 0) { perror (semop); exit (1); } return;}void V(int *s){ struct sembuf sembuffer, *sops; sops = &sembuffer; sops->sem_num=0; sops->sem_op=1; sops->sem_flg=0; if (semop(*s, sops, 1) < 0) { perror (semop); exit (1); } return;}

  • Exemplo utilizando PthreadsSo criadas n threads, cada uma obtm os nmeros de uma lista, os soma e coloca o resultado em uma varivel compartilhada denominada sumA varivel compartilhada global_index utilizada por cada thread para selecionar o prximo elemento de aAps a leitura do ndice, ele incrementado para preparar para a leitura do prximo elementoEstrutura de dados utilizada

    Array a[]sumaddrglobal_index

  • #define array_size 1000;#define no_threads 10;

    int a[array_size];int global_index = 0;int sum = 0;pthread_mutex_t mutex1;void *slave (void *ignored){ int local_index, partial_sum =0; do { pthread_mutex_lock&(mutex1); local_index = global_index; global_index++; pthread_mutex_unlock(&mutex1); if (local_index < array_size) partial_sum += *(a+local_index); } while (local_index < array_size); pthread_mutex_lock(mutex1); sum+=partial_sum; pthread_mutex_unlcok(&mutex1); return();}

  • main() { int i; pthread_t thread[no_threads]; pthread_mutex_init(&mutex1, NULL); for (i = 0; i < array_size; i++) a[i] = i+1; for (i = 0; i < no_threads; i++) if (pthread_create(&thread[i], NULL, slave, NULL) != 0) { perror(Pthread_create falhou); exit(1); } for (i = 0; i < no_threads; i++) if (pthread_join(thread[i], NUL) != 0) { perror(Pthread_join falhou); exit(1); }printf(A soma %d \n, sum)}

  • Exemplo em Javapublic class Adder{ public int [] array; private int sum = 0; private int index = 0; private int number_of_threads = 10; private int threads_quit;

    public Adder () { threads_quit = 0; array = new int[1000]; initializeArray(); startThreads() }

    public synchronized int getNextIndex() { if (index < 1000) return (index ++); else return (-1); }

    public synchronized void addPartialSum(int partial_sum) { sum = sum + partoal_sum; if (++threads_quit == number_of_threads) System.out.println(a soma dos nmeros e+sum); }

  • private void initializeArray() { int i; for (i = 0; i < 1000; i+=) array[i] = i; }

    public void startThreads () { int i = 0; for (i = 0; i < 10; i++) { AdderThread at = new adderThread(this, i); at.start(); } } public static void main(String args[]) { Adder a = new Adder(); }}

  • class AdderThread extends Thread{ int partial_sum = 0; Adder_parent; int number; public AdderThread (Adder parent, int number) { this.parent = parent; this.number = number; }

    public void run () { int index = 0; while (index != -1) { partial_sum = partial_sum + parent.array[index]; index = parent.getNextIndex(); } parent.addPartialSum(partial_sum);) System.out.println(Soma parcial da thread + number + + partial_sum); }}