IC - UFF

Sistemas Operacionais

3. Concorrência

Texto base: capítulo 2

Modern Operating Systems

A.S. Tanenbaum

IC - UFF

O que envolve?

O conceito de concorrência envolve compartilhamento de recursos: problema

fundamental da exclusão mútua sincronização entre processos comunicação entre processos

IC - UFF

Algumas dificuldades

Compartilhamento de recursos globais e.g., variáveis globais: leituras e escritas

Gerenciamento da alocação de recursos e.g., uma unidade de E/S deve ficar alocada

a um processo suspenso? Localização de erros em programas

e.g., como reproduzir situações?

IC - UFF

Corrida

abcprog.cprog.n

lista dospooler

out = 4

in = 7

daemon deimpressão

4567

processo A

processo B

impressora

IC - UFF

Compartilhando código

echo ()

char in, out;

{

in = getch();

out = in;

putchar(out);

}

IC - UFF

Logo ...

Resultado da execução de um processo deve ser independente da velocidade de execução deste processo relativamente a outros processos concorrentes

Atenção: o problema também ocorre em multiprocessadores

IC - UFF

Concorrência: problemas Exclusão mútua

seções críticas Bloqueio

P1 com R1 e precisa de R2

P2 com R2 e precisa de R1

Esfomeação P1, P2 e P3 querem R; suponha P1 e P2 passando

o controle um para o outro

IC - UFF

Requisitos: exclusão mútua

Dois processos não podem estar simultâneamente em suas seções críticas

Nenhuma hipótese deve ser feita sobre a velocidade ou número de processadores

Nenhum processo fora de sua crítica pode bloquear outro processo

Nenhum processo deve esperar indefinidamente para entrar em sua seção crítica

IC - UFF

Espera ocupada (1)

Desabilitando interrupções solução mais simples: desabilita antes de

entrar na seção crítica; habilita antes de sair dá muito poder a processos do usuário não funciona quando existe mais de um

processador útil no núcleo do SO

IC - UFF

Espera ocupada (2)

Alternância estrita

Não é boa idéia quando um processo é muito mais lento que o outro (cond. 3)

while (TRUE) { while (vez != 1); /*espera*/ seção_crítica(); vez = 0; seção_não_crítica();}

while (TRUE) { while (vez != 0); /*espera*/ seção_crítica(); vez = 1; seção_não_crítica();}

IC - UFF

Solução de Peterson#define FALSE 0#define TRUE 1#define N 2 /* número de processos */

int turn; /* de quem é a vez? */int interested[N]; /* inicialmente 0 (FALSE) */

void enter_region (int process){

int other; /* número do outro processo */

other = 1 - process;interested[process] = TRUE; /* indique seu interesse */turn = process; /* set flag */while (turn == process && interested[other] == TRUE);

}

void leave_region int process){

interested[process] = FALSE; /* indica saída da região crítica */}

IC - UFF

Ainda a espera ocupada

A instrução TSL (test and set lock) lê o conteúdo de uma palavra de memória e

armazena um valor: operação indivisível a UCP que executa TSL bloqueia o barramento de

memória: nenhuma outra UCP acessa memória durante ciclo da TSL

uso de uma variável compartilhada para coordenar o acesso à memória (flag, no exemplo)

IC - UFF

Uso da TSL

enter_region:tsl register, flag | register flag e flag 1cmp register, #0 | flag era zero?jnz enter_region | se não era zero, continue testandoret | retorna; entrou na região crítica

leave_region:mov flag, #0 | flag 0ret | retorna

IC - UFF

Inversão de prioridades?

Exemplo: dois processos, A (alta) e B (baixa) B na região crítica; A torna-se pronto A inicia espera ocupada; B nunca sairá da

seção crítica A fica em espera eterna

IC - UFF

Bloqueio espera ocupada

A espera ocupada implica em desperdício de tempo de UCP

Vejamos primitivas que bloqueiam em vez de desperdiçar tempo de UCP quando acesso à seção crítica é negado: sleep() e wakeup(p)

IC - UFF

Dois processos compartilham um buffer de tamanho fixo: um coloca informação e o outro retira

Produtor-consumidor (P-C)

buffer [N]produtor consumidor

assincronismo

IC - UFF

O produtor#define N 100

int count = 0;

void producer (void)

{

int item;

while (TRUE) {

produce_item (&item);

if (count == N) sleep(); /* espere, se buffer cheio*/

enter_item (item);

count = count + 1;

if (count == 1) wakeup (consumer); /* buffer vazio? */

}

}

IC - UFF

O consumidor

void consumer (void)

{

int item;

while (TRUE) {

if (count == 0) sleep(); /* espere, se buffer vazio*/

remove_item (&item);

count = count - 1;

if (count == N-1) wakeup(producer); /* buffer cheio? */

consume_item(item);

}

}

IC - UFF

Acesso irrestrito a variável Variável count:

buffer vazio, consumidor lê count=0, escalonador pára de executar consumidor e dispara produtor

produtor produz um item, incrementa count, chama wakeup(consumidor)

consumidor não estava dormindo: sinal de wakeup é perdido

consumidor é escalonado e vai dormir; produtor enche o buffer e vai dormir

IC - UFF

Semáforo Variável especial, chamada semáforo, é

usada para sinalização Se um processo está esperando por um

sinal, ele será suspenso até receber o sinal Operações de sinal e espera: atômicas Uso de fila para manter processos que

esperam no semáforo

IC - UFF

P-C com semáforos

#define N 100typedef int semaphore;

semaphore mutex = 1; /* controla acesso à região crítica */semaphore empty = N; /* conta lugares vazios */semaphore full = 0; /* conta lugares cheios */

void producer (void){ int item; while (TRUE) { produce_item (&item); down (&empty); down (&mutex); /* entra região crítica */ enter_item (item); up (&mutex); /* sai da região crítica */ up (&full); }}

void consumer (void){ int item; while (TRUE) { down (&full); down (&mutex); /* entra região crítica */ remove_item (&item); up (&mutex); /* sai da região crítica */ up (&empty); consume_item (item); }}

para sincronização

para exclusão mútua

IC - UFF

O problema dos filósofos

IC - UFF

Uma primeira solução ...

#define N 5 /* número de filósofos */

void philosopher (int i){

while (TRUE) {think();take_fork (i); /* pega garfo à esquerda */take_fork ((i+1)%N); /* pega garfo à direita */eat ();put_fork (i); /* devolve garfo da esquerda */put_fork ((i+1)%N); /* devolve garfo da direita */

}}

IC - UFF

Problemas! Se todos pegarem o garfo da esquerda

(direita) simultâneamente teremos bloqueio (deadlock)

Variação: pega o da esquerda, testa o da direita. Contudo se todos fizerem isso simultâneamente teremos esfomeação

Solução: proteger região crítica com semáforo: possível perda de paralelismo

IC - UFF

... uma solução

#define N 5

#define LEFT (i-1)%N

#define RIGHT (i+1)%N

#define THINKING 0

#define HUNGRY 1

#define EATING 2

typedef int semaphore;

int state[N]; /* array para guardar estado de cada filósofo */

semaphore mutex = 1; /* exclusão mútua para a região crítica */

semaphore s[N]; /* um semáforo por filósofo */

IC - UFF

... uma solução (cont.)

void philosopher (int i)

{

while (TRUE) {

think();

take_forks(i);

eat();

put_forks(i);

}

}

IC - UFF

... uma solução (cont.)

void take_forks (int i)

{

down (&mutex); /* entra região crítica */

state[i] = HUNGRY;

test(i); /* tenta pegar dois garfos */

up (&mutex); /* sai da região crítica */

down (&s[i]); /* bloqueia se não pegou ambos os garfos */

}

test()

IC - UFF

... uma solução (cont.)

void put_forks (int i)

{

down (&mutex); /* entra região crítica */

state[i] = THINKING;

test (LEFT); /* vizinho da esquerda pode comer? */

test (RIGHT); /* vizinho da direita pode comer? */

up (&mutex); /* sai da região crítica */

}

test()

IC - UFF

... uma solução (cont.)

void test (int i)

{

if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {

state[i] = EATING;

up (&s[i]);

}

}

para i corrente!

sinaliza que pegouambos os garfos! take_forks()

put_forks()

IC - UFF

Outras formas

Embora semáforos pareçam simples (baixo nível), problemas podem surgir se a ordem das operações down forem impróprias: uso de monitores (linguagem)

E se é necessário a troca de informações entre máquinas processos? troca de mensagens

IC - UFF

Leitura suplementar

Operating Systems Concepts, A. Silberschatz e P.B. Galvin, Addison-Wesley

Operating Systems: Internals and Design Principles, W. Stallings, Prentice Hall