Pricípios Básicos de Sincronização

Capitulo 8 – Princípios básicos da sincronização

Objectivos

8.1 - Interacção de processos

8.1.1 - Secções criticas

8.1.2 - Deadlock

8.2 - Coordenação de processos

8.3 - Semáforos

8.3.1 - Princípios de operação

8.3.2.1 - Implementação de semáforos

8.3.2.2 - Implementação activa e passiva de semáforos

8.4 - Multiprocessadores de Memória partilhada

Objectivos do Capitulo

Programação múltipla, tempo partilhado e processo paralelo fizeram com que a noção de grupos cooperativos de processos sequenciais fossem possíveis. Operações concorrentes em simultâneo, com relatos de grupos de processos, permitiram uma única aplicação para obter vantagens do paralelismo entre o CPU e os dispositivos de ‘input/output’ (entrada e saída) no caso dum único processador e na colaboração CPUs no caso de multiprocessadores. No entanto múltiplos processos cooperativos introduzem o possíveis novos problemas no software de implementações: o ‘deadlock’, as secções criticas e a possibilidade da não determinação nestas computações. Estes princípios acontecem quando dois ou mais processos entram em conflito, nomeadamente por utilização dos mesmos recursos (incluindo informação).

É importante perceber as várias interacções entre processos antes de desenhar as máquinas que suportam as mesmas interacções. Por isso a primeira parte deste capítulo discute a natureza geral dessas interacções. O resto do mesmo foca as ferramentas clássicas de sincronização, nomeadamente o semáforo e as respectivas implementações técnicas.

A sincronização é necessária nos uni processadores, multiprocessadores e redes. Porém o problema é suficientemente complexo por isso é tradicionalmente estudado no ambiente do uni processador. Nesta discussão, os resultados são generalizados para os multiprocessadores e para redes (capitulo 17).

8.1. Interacção de Processos

Os Programas de Computador não são mais que a implementação de séries de algoritmos, passo-a-passo. Esses procedimentos vão permitir através do processamento de informação a realização de uma determinada tarefa.

O uso da série de algoritmos para especificar computações em série tem dominado a programação por toda a metade do século passado. Enquanto a programação tradicional com o C e o C++ dá pouco importância ao endereço, no que toca ao hardware tem sistematicamente evoluído no sentido do desenvolvimento da distribuição e computação paralela das máquinas. Pressões económicas a isso o obrigam. Para além das referidas questões económicas, o tratamento de informação, a computação em ambiente de escritório e aplicações numéricas exercem também uma grande pressão.

8.1.1.Secções Críticas

Supondo que uma aplicação é escrita para que dois processos, p₁ e p₂, executem o acesso comum a uma variável inteira, x. Por exemplo, p₁ poderá manusear créditos para uma conta, enquanto p₂ faz o manuseamento dos débitos dessa mesma conta. O seguinte código exemplifica como os processos referenciam o balanço da partilha.

Shared float balance;	/ shared variable /
…	…
Code Schema For p1	Code Schema For p2
…	…
balance=balance+amount;	balance=balance-amount;

figura 1

Este linguagem de alto nível será compilada e traduzida pelo seguinte código:

Esquema para p₁		Esquema para p₂
load	R₁, balance	load	R₁, balance
load	R₂, amount	load	R₂, amount
Add	R₁, R₂	sub	R₁, R₂
store	R₁, balance	store	R₁, balance

figura 2

O problema da secção critica pode ocorrer quando os segmentos de código são executados. Supondo que p₁ está a correr num uni processador quando o intervalo do timer acaba e o processo p₁ está a executar a instrução:

load R2,amount

Se o escalonador (scheduler) seleccionar em seguida o processo p₂ para correr e este executar o segmento de instrução “balance = balance – amount; “ antes de p1 voltar a correr, então vai existir “ condição de corrida “ entre p₁ e p₂. Se p₁ ganhar a corrida, os valores de R₁ e R₂ serão somados e a variável balance será escrita na memória sem qualquer erro. Se p₂ “ganhar a corrida”, vai ler o resultado original de balance, efectuar a subtracção ( balance – amount ) e guardar o valor em balance. Por sua vez p₁ que ainda tem o valor antigo de balance vai executar a soma e sobrepor o resultado ao anterior ficando a operação de subtracção perdida.

O programa que contem p₁ e p₂ tem uma secção critica quando há necessidade de partilhar a variável balance. Para p₁ a secção critica é quando soma ‘amount’ a ‘balance’. Para p₂ é quando subtrai amount a balance. A execução cooperativa de dois processos não é garantidamente determinada, visto que duas execuções diferentes do mesmo programa pode produzir valores diferentes. Na primeira execução p₁ pode ganhar a corrida e na próxima execução pode ser p₂ a ganhar, resultando valores diferentes nas variáveis partilhadas. Não é possível detectar problemas apenas considerando o processo ( ou programa ) p₁ ou p₂. Os problemas ocorrem devido à partilha, não devido a um erro no código do programa. O problema da secção critica pode ser evitado fazendo com que ambos os processos possam entrar na secção critica desde que o outro não se encontre também na sua secção critica.

Como é que dois processos podem cooperar para entrar na secção critica? Num sistema multiprogramado, as interrupções causam alguns problemas, visto que podem fazer com que o escalonador funcione. Por causa das operações gravadas nos estados dos registos implícito com troca de contexto, um processo pode resumir a execução carregando informação inconsistente nos registos. Se o programador se aperceber que a ocorrência de uma interrupção pode levar a resultados errados, pode fazer com que o programa desligue as interrupções, enquanto se está a processar a secção critica do processo.

A seguinte grelha mostra como, por exemplo, a secção critica pode ser programada

Shared double balance;	/ shared variable /

*Program for p1*	*Program for p2*

disableInterrupts();	disableInterrupts();
balance=balance+amount;	balance=balance-amount;
EnableInterrupts();	EnableInterrupts();

figura 3

As instruções “enableinterrupt” e o “disableinterrupt” para evitar que ambos os processos sejam iniciados ao mesmo tempo nas secções criticas. As interrupções são desligadas quando os processos entram na secção critica para que os mesmos não sejam interrompidos e voltam a ser ligados depois de esta ser executada. Claro que, esta técnica pode provocar erros nos dispositivos de entrada/saída (i/o) visto que podem vir a ser desligados durante muito tempo, consoante os programas. Em particular, imagine que o programa entra num ciclo infinito na sua secção critica. As interrupções iam ficar desligadas permanentemente.

Uma alternativa para a solução, apresentada na anterior grelha, não necessita que as interrupções sejam desactivadas, dessa forma o problema de grande/infinitos intervalos de computação é evitado. A ideia é fazer com que os dois processos coordenem as suas acções sobre as variáveis partilhadas para sincronizar os seus progressos. A grelha abaixo indicada usa uma flag (bandeira) partilhada, lock, de forma a que p₁ e p₂ possam coordenar aos seus acessos a “balance”. Quando p₁ entra na secção critica altera a variável partilhada lock, de forma a prevenir que p₂ entre também na sua secção critica. O mesmo acontece quando p₂ entra na secção critica.

shared boolean lock=FALSE;;	/ shared variable /
shared float balance;

*Program for p1*	*Program for p2*
...	...
/ Acquire the lock /	/ Acquire the lock /
While (lock) (NULL;);	While (lock) (NULL;);
Lock = TRUE	Lock = TRUE
/ Execute critical section /	/ Execute critical section /
balance = balance + amount;	balance = balance – amount;
/ Release the lock /	/ Release the lock /
Lock = FALSE;	Lock = FALSE;
…	…

figura 4

A grelha anterior ilustra um modelo de execução para dois processos. Supondo que p₁ é interrompido durante a execução do processo.

balance = balance + amount;

Depois de ter alterado lock para TRUE e p₂ começar a ser executado. Então p₂ vai esperar num ciclo while enquanto p₁ termina e muda o lock para FALSE

figura 5

Quando p₁ mudar lock para FALSE indicou a p₂ que já pode continuar, quando chegar a interrupção do relógio, p₂ passa à execução.

Embora o uso de lock para entrar na secção critica, está-se a acrescentar uma nova secção critica relacionada com o teste da variável lock. O problema pode ocorrer quando acabamos de testar a variável lock e nos preparamos para alterá-la. Se ocorrer uma interrupção depois de testarmos a variável lock, o outro processo ainda ia detectar lock = FALSE e entrava na secção critica. Quando fosse a vez do primeiro voltar a correr iria mudar lock = TRUE mas o outro já lá estava dentro. Para evitar isso podemos usar as interrupções, mas desta vez por pouco tempo, apenas para permitir uma instrução como é mostrado no diagrama abaixo indicado.

enter (lock){	exit(lock){
disableInterrupts();	disableinterrupts();
/* loop enquanto lock = TRUE */	lock=FALSE
while (lock) {	enableinterrupts();
/* deixa ocorrerem interrupcções */	}
enableInterrupts();
disableInterrupts();
}
lock = TRUE;
enableinterrupts();
}

figura 6

8.1.2 Deadlock

Numa situação de deadlock, dois ou mais processos entram num estado em que ambos seguram um recurso que o outro está a requisitar. Visto que uma operação de requisição bloqueia a ligação até o recurso estar disponível, nenhum dos processos vai ter o recurso disponível e vão ficar bloqueados infinitamente. Neste capítulo, são apenas focados os casos em que o recurso é secção crítica ou lock. O capitulo 10 este tema é focado de uma forma mais aprofundada.

Considera-se um caso em que dois processos p₁ e p₂ manipulam uma lista comum. Uma tarefa na manipulação da lista é o processo acrescentar ou apagar entradas, outra é actualizar uma discrição do programa com o comprimento da lista. Quando uma operação de apagar ou acrescentar ocorre, o comprimento tem que ser actualizado. Podemos tentar a aproximação No diagrama seguinte, mas vamos ver mais tarde que não chega para garantir o bom funcionamento do programa.

boolean lock1 = FALSE;	/* variaveis partilhadas */
boolean lock2 = FALSE;
shared list L;

*Program for p1*	*Program for p2*

…	…
/* Entrar na secção critica para	/* Entrar na secção critica para
apagar um elemento da lista */	actualizar o comprimento */
enter (lock1);	enter (lock2);
<Apagar elemento>;	<Actualizar comprimento>;
/* Sair da secção critica */	/* Sair da secção critica */
exit (lock1);	exit (lock2);
<Computação intermédia>;	<Computação intermédia>;
/* Entrar na secção critica para	/*Entrar na secção critica para
actualizar o comprimento */	acrescentrar um elemento à lista*/
enter(lock2);	enter(lock1);
<Actualizar comprimento>;	<Adicionar elemento>;
/* Sair da secção critica */	/* Sair da secção critica */
exit(lock2);	exit(lock1);
…	…

figura 7

Se os processos p₁ e p₂ são executados ao mesmo tempo num sistema multiprogramado, uma interrupção do relógio pode ocorrer depois de p₁ apagar um elemento, mas antes de ter actualizado o comprimento, então os dados na descrição não são iguais aos dados reais. O processo deve executar as duas operações ou então nenhuma. Para não ocorrerem estes erros vamos modificar o nosso programa.

Quando p₁ entra na secção critica para manipular a lista muda lock1 o que previne p₂ de entrar na sua secção critica. Depois de executada a secção critica volta a mudar lock1 para o seu valor inicial. O mesmo acontece se for p₂ a entrar primeiro na secção critica.

boolean lock1 = FALSE;	/* variaveis partilhadas */
boolean lock2 = FALSE;
shared list i, j;

*Program for p₁*	*Program for p₂*

…	…
/* Entrar na secção critica	/* Entrar na secção critica
da lista */	da descrição */
enter (lock1);	enter (lock2);
<Apagar elemento>;	<Actualizar comprimento>;
<Computação intermédia>;	<Computação intermédia>;
/* Entrar na secçãp critica	/*Entrar na secção critica
da descrição */	para i */
enter(lock2);	enter(lock1);
<Actualizar comprimento>;	<Adicionar elemento>;
/* Sair da secção critica */	/* Sair da secção critica */
exit (lock1);	exit (lock2);
exit(lock2);	exit(lock1);
…	…

figura 8

8.2 Coordenação de processos

A necessidade da interacção entre processos faz com que tenha de haver sincronização de processos, por sua vez a sincronização conduz a problemas com secções criticas e deadlocks. FORK, JOIN e QUIT são introduzidos no capitulo 6, como mecanismos para criar e eliminar processos. Também são usados para sincronizar partes de uma computação cooperativa.

figura 9

shared double x,y;	/* variáveis partilhadas */

proc_A{	proc_B{
While (true){	While (true){
<compute A1>;	read (x); /* Consume x */
write(x); /* Produce x */	<compute B1>;
<compute A2>;	write(y); /* Produce y */
read (y); /* Consume y */	<compute B2>;
}	}
}	}

figura 10

8.3 Semáforos

Um semáforo é assemelha-se um sistema operativo de informação abstracta que executa operações similares ás funções enter e exit descritas na figura 6.

Como já foi discutido, um processo não pode entrar numa secção critica se outro já se encontra na sua secção critica. Quando um processo está prestes a entrar na sua secção critica, primeiro vai determinar se outro processo já se encontra na sua secção critica. Se já se encontrar algum na secção critica, o segundo processo sincroniza a sua operação bloqueando-se até que o primeiro processo saia da sua secção critica. Uma solução aceitável para o problema da secção critica é estabelecer as seguintes regras:

Apenas um processo pode entrar na sua secção critica de cada vez (exclusão mútua).
Supondo que a secção critica está livre. Se um grupo de processos indica que quer entrar, apenas esse grupo de processos vai entrar na zona de selecção.
Quando um processo tenta entrar na sua secção critica, não pode ser adiado indefinidamente mesmo que não exista outro processo na secção critica.
Depois de um processo requerer entrar na secção critica, apenas um número limitado de processos é permitido entrar na suas secções criticas, antes do processo original entrar na sua secção critica.

O problema da secção critica é na sua essência um problema de software. Esta secção assume particular importância em aspectos importantes relacionados com cooperação entre dois processos como é indicado na figura abaixo indicada.

proc_0 () {	proc_1 () {
while (TRUE) {	while (TRUE) {
<secção de computação>;	<secção de computação>;
<secção critica>;	<secção critica>;
}	}
}	}

<declarações globais partilhadas>
<processamento inicial>
fork (proc_0, 0);
fork (proc_1, 0);

figura 11

São aplicados os seguintes itens sobre o esquema do software da figura:

· Escrever e ler uma célula de memória comum a dois processos é uma operação indivisível. Qualquer tentativa de dois processos executarem simultaneamente operações de escrita ou leitura resulta em vários ordenamentos desconhecidos, mas as operações não vão ocorrer ao mesmo tempo.

· Não é suposto haver prioridades entre os processos no caso de dois ou mais processos quererem entrar na secção critica.

· As velocidades relativas dos processos são desconhecidas, por isso o mesmo programa pode demorar intervalos de tempo a executar.

· Como é indicado na figura 11, é suposto que os processos sejam sequenciais e cíclicos.

8.3.1 Principios de operação

Um semáforo, “s”, é uma variável inteira não negada que só é alterada ou testada por uma de duas rotinas de acesso:

V(s) : [s=s+1]

P(s) : [while (s=0) (wait) ; s=s+1]

Os parêntesis rectos que cercam as expressões nas rotinas de acesso indicam que as operações são indivisíveis ou atómicas. Na operação V, o processo que executa a rotina não pode ser interrompido até completar a rotina. A operação P é mais complexa. Se “s” é maior que 0, é testado e decrementado como uma operação indivisível. Por outro lado se “s” é igual a 0, o processo que executa a operação P pode ser interrompido.

proc_0 () {	proc_1 () {
while (TRUE) {	while (TRUE) {
<secção de computação>;	<secção de computação>;
P(mutex);	P(mutex);
<secção critica>;	<secção critica>;
V(mutex);	V(mutex);
}	}
}	}

semaphore mutex = 1;
fork (proc_0, 0);
fork (proc_1, 0);

figura 12

8.3.2.1 Implementação de semáforos

A figura 6 mostra como as interrupções podem ser desligadas para manipular a variável lock. A mesma técnica pode ser usada para implementar operações V e P. Visto que as mesmas são implementados como funções do sistema operativo, o modelo de uma solução assume que os processos do utilizador podem ter um ponteiro para o semáforo, mas o ponteiro é para um objecto no sistema operativo.

Uma implementação que siga este modelo desliga as interrupções, mas apenas por pequenos períodos de tempo. Quando um processo bloqueia num semáforo, as interrupções estão ligadas; As interrupções estão desligadas apenas quando é manipulado o valor do semáforo. Isto tem dois efeitos importantes:

Há efeitos mínimos no sistema I/O.
Enquanto um processo segura um semáforo, previne apenas a entrada de outros processos na secção crítica. Todos os outros processos não são afectados pelo facto do processo estar na secção crítica.

Os semáforos podem ser implementados sem desligar as interrupções se o hardware fornecer algumas condições especiais. Uma implementação directa das instruções P e V é algo difícil devido à necessidade de acomodar o ciclo wait na operação P. Em vez disso, uma implementação uniprocessador geralmente quer interagir com o escalonador para a implementação de P, logo uma parte da instrução vai ser implementada em hardware e outra em software. O sistema operativo pode criar recursos abstractos para cada semáforo. Depois usa um recurso de gestão bloqueia processos que executam operações P como se tivessem executado uma operação de requerimento num recurso convencional. A garantia vem como o recurso de gestão do semáforo consegue implementar simultaneamente e correctamente os acessos ao semáforo sem usar as interrupções.

As instruções TS (test and set) são o caminho dominante para conseguir os efeitos P e V. TS é uma instrução simples que pode de incluído no repertório da máquina sem muito esforço. Mas isto pode fazer a implementação de semáforos muito simples. A local de memória TS, m, ou TS(m), é carregado para um registo do CPU, e na memória é escrito o valor TRUE.

Para um processo entrar na secção crítica vai ler a memória. Ao comparar o valor de m o processo pára ou segue.

8.3.2.2 Implementação de semáforos activos e passivos

Um semáforo pode ser visto como um recurso de consumo. Um processo bloqueia se o valor requisitado a um semáforo não está disponível. Um processo move-se de um estado de execução para um estado bloqueado executando uma operação P num semáforo de valor zero. O processo passa do estado bloqueado ao estado executável quando é lido um valor positivo no semáforo; ele decrementa o semáforo enquanto muda de estado. Quando um processo larga um recurso, neste caso executa uma operação V, o alocador de recursos move o primeiro processo de bloqueado para pronto.

8.4 Multiprocessadores com memória partilhada

As secções 8.1 e 8.3 descrevam uma técnica para implementação de semáforos desligando interrupções. Num multiprocessador com memória partilhada, isto é insuficiente, visto que desligando as interrupções num CPU não afecta o comportamento dos outros processadores. Por isso multiprocessadores com memória partilhada comercializados usam instruções especificas como TS para implementar semáforos. Em multiprocessadores com partilha de memória, a memória pode ser projectada para suportar TS.