exclusão mútua-Mutex, Fechaduras, algoritmo Peterson, espera limitada e algoritmo de padaria.

author
8 minutes, 14 seconds Read

Considere este trecho de código.

public long getAndIncrement() {
temp = value; #Line-1
value = temp + 1; #Line-2
return temp;
}

vamos supor que dois Threads a e B acessem este método getAndIncrement () simultaneamente.Abaixo está um possível fluxo de execução por esses dois threads

Sequence 1
Thread-A temp = value temp = 0, value = 0
Thread-A value = temp + 1 temp = 0, value = 1
Thread-B temp = value temp = 1, value = 0
Thread-B value = temp + 1 temp = 1, value = 2

vamos considerar outra sequência de execução.

Sequence 2
Thread-A temp = value temp = 0, value = 0
Thread-B temp = value temp = 0, value = 0
Thread-A value = temp + 1 temp = 0, value = 1
Thread-B value = temp + 1 temp = 0, value = 1

assim, ao executar blocos de código não atômicos para manter a consistência das variáveis, precisamos vincular o processo a um thread específico e não permitir que outros threads sejam modificados . A seção de código que precisa ser isolada e executada por um único thread para manter esse tipo de consistência é conhecida como seção crítica.

este conceito é usado em programação simultânea com uma seção crítica, um pedaço de código no qual processos ou threads acessam um recurso compartilhado. Apenas um thread possui a exclusão mútua (mutex) de cada vez, portanto, um mutex com um nome exclusivo é criado quando UM programa é iniciado. Quando um thread contém um recurso, ele precisa bloquear o mutex de outros threads para impedir o acesso simultâneo do recurso. Ao liberar o recurso, o thread desbloqueia o mutex.

para alcançar a exclusão mútua, usaremos bloqueios .Use bloqueios de exclusão mútua para serializar a execução de threads. Os bloqueios de exclusão mútua sincronizam os threads, geralmente garantindo que apenas um thread por vez execute uma seção crítica do Código. Os bloqueios Mutex também podem preservar o código single-threaded.

uma fechadura deve ser,

  • manter a exclusão mútua entre threads.
  • Deadlock livre
  • fome livre

um bloqueio será fome livre → Deadlock livre . Portanto, para avaliar um bloqueio, precisamos verificar se ele é mutuamente exclusivo, se é livre de impasse ou não e se é livre de fome ou não.

bloqueio simples

class SimpleLock implements Lock { private volatile boolean flag; public void lock() {
while (flag == true) { } #Line-1
flag = true; #Line-2
} public void unlock() {
flag = false;
}

digamos que dois threads (Thread A e Thread B) estejam executando este bloco de código .

suponha que um executa primeiro .Ele entra no método de bloqueio, Verifique o valor do sinalizador na linha-1 e infere-o como falso.

o interruptor de contexto acontece neste ponto e B é executado a seguir. Ele entra no método de bloqueio, Verifique o valor do sinalizador na linha-1 e infere-o como falso. Em seguida, ele executa a linha 2 e entra na região crítica.

agora, novamente, um executa e o ponteiro para o Thread A está na linha-2 (Como já executou a linha-1) e também entra na região crítica.

aqui a exclusão mútua não é mantida para esses 2 threads A E B, pois ambos estão acessando a região crítica ao mesmo tempo..

bloquear um

class LockOne implements Lock { private volatile boolean flag = new boolean; #Line-1 public void lock() {
flag = true; #Line-2
while (flag) {} #Line-3
} public void unlock() {
flag = false; #Line-4
}

digamos que dois threads (Thread A e Thread B) estejam executando este bloco de código como acima . Aqui, em vez de uma bandeira booleana, estamos tendo duas bandeiras para cada segmento.(Linha-1)

suponha que um executa primeiro .ele entra no método de bloqueio, atribui o valor de ‘true’ ao seu sinalizador na linha-2, verifica o valor do sinalizador de outro Thread na linha-3 e infere-o como falso.Assim, entra na região crítica.

então B executa .Ele entra no método de bloqueio, atribui o valor de ‘true’ ao seu sinalizador na linha-2, verifica o valor do sinalizador de outro Thread na linha-3 e o infere como “true”, pois já o Thread a alterou o valor para “true” .então B entra no loop e espera que o sinalizador do Thread B se torne false para sair do loop while.

depois de concluir o segmento de seção crítica a executa o método de desbloqueio atribuir o valor de “false” à sua bandeira e Saídas. Agora, enquanto a condição de loop do Thread B se torna falsa e B Sai Do Loop e entra na região crítica.

assim, a exclusão mútua é tratada adequadamente neste bloqueio.

agora vamos considerar este cenário.

Passo-1-suponha que um executa primeiro. ele entra no método de bloqueio, atribui o valor de ‘true’ ao seu sinalizador na linha-2, a comutação de contexto acontece e espera .

Passo-2 – então B é executado. ele entra no método de bloqueio,atribui o valor de ‘true’ ao seu sinalizador na linha-2, a comutação de contexto acontece e espera.

Passo-3 – agora novamente um executa e agora o ponteiro de A está na linha 3 e verifica o valor do sinalizador de outro Thread na linha-3 e infere-o como “verdadeiro”(devido ao PASSO-2). Assim, ele entra no loop while.

Passo-4 – Agora novamente B é executado e agora o ponteiro de B está na linha 3 e verifica o valor do sinalizador de outro Thread na linha-3 e infere-o como “verdadeiro”(devido ao passo-1). Assim, ele entra no loop while.

agora ambos os threads estão em loop enquanto esperam um pelo outro para serem liberados.Esta é uma condição de impasse.

bloquear dois

public class LockTwo implements Lock { private volatile int victim; #Line-1 public void lock() {
victim = i; #Line-2
while (victim == i) { #Line-3
}; #Line-3
}
public void unlock() {}}

se o segmento B estiver na seção crítica, A é a vítima e Vice-Versa.Assim LockTwo satisfaz a exclusão mútua.

se ambos os threads forem vítimas, eles farão um loop dentro do loop while na linha-3 e criarão um impasse. Mas aqui apenas um dos fios pode ser uma vítima. Se A for uma vítima, ela fará um loop dentro do loop while na linha-3 e quando B atribuir a si mesmo como vítima, a fará um Loop break e entrará na região crítica.Assim, este bloqueio é deadlock livre.

digamos que apenas um thread esteja executando este bloco de código .Ele fará um loop dentro do loop while para sempre sem ter nenhum thread para liberá-lo.ele morrerá de fome para executar o CS.Assim, este bloqueio não é livre de fome.

algoritmo Peterson

public void lock() { 
flag = true;
victim= i;
while (flag && victim == i) {};
}public void unlock() {
flag = false;
}

isso eliminará todas as desvantagens que vimos nos bloqueios anteriores. Isso dará exclusão mútua sem impasse e fome.

está eliminando a fome de LockTwo . Se apenas um thread executar isso, ele executará este bloco sem qualquer inanição.

conceito de espera limitada

fome-liberdade garante cada segmento que chama lock () eventualmente entra seção crítica.Mas não há garantias sobre quanto tempo vai take.So para manter essa Justiça, assumiremos que, se a chamar lock() antes de B, A deve entrar na seção crítica antes de B.

Estamos analisando o bloqueio por dividi-lo em duas partes

  • D – Porta seção
  • W – Espera seção
public void lock() { #Doorway Section
flag = true;
victim= i; #Waiting Section
while (flag && victim == i) {};
}

r Delimitada em Espera

Deixe suponha que A e B estão a executar o bloqueio e Uma é acessando D( Porta de entrada da secção ) no n-ésimo tempo e B está acessando a D a m-ésima vez que n>m . E a porta n-th de a precedeu a porta m-th de B.

assim, a seção n-ésima crítica de a precede a seção crítica de B (M + r)-ésima.Isso significa que B não pode ultrapassar A em mais de R vezes.

primeiro a chegar-primeiro a ser servido significa r = 0 . Uma fechadura é servida por ordem de chegada se, sempre que, o fio a terminar sua porta antes do fio B iniciar sua porta,
então A não pode ser ultrapassado por B.

algoritmo de padaria

o algoritmo de padaria é uma das soluções mais simples conhecidas para o problema de exclusão mútua para o caso geral do processo n. Algoritmo de padaria é uma solução de seção crítica para n processos. O algoritmo preserva a propriedade first come first serve.

Lexicográfica ordem na Padaria Algoritmo de meios, (a, i) < (b, j) , Se a < b, ou a = b e i < j

class Bakery implements Lock {
volatile boolean flag;
volatile Label label;
public Bakery (int n) {
flag = new boolean;
label = new Label;
for (int i = 0; i < n; i++) {
flag = false; label = 0;
}
}
public void lock(){ #Doorway Section
flag = true; #Line1
label = max(label,label,......label)+1; #Line2 #Waiting Section
while(there exists k flag && (label,i) > (label,k)){
}
}
public void unlock() {
flag = false;
}}

Na Padaria() método que está a atribuir um sinalizador Booleano e um rótulo valor de 0 para cada ‘n’ o número de linhas.

para cada thread que está acessando o método de bloqueio, estamos atribuindo true ao seu sinalizador e fazendo seu valor de rótulo como máximo incrementando o máximo de todos os rótulos disponíveis em 1.

(label,i) > (label,k)

mas aqui a linha -2 não é atômica .portanto, dois Threads podem executar simultaneamente a linha-2 e obter o mesmo valor de rótulo. Assim label = label. Nesse cenário, precisamos favorecer o processo que entrou na porta primeiro e permitir que esse processo entre na seção crítica. Portanto, ele verificará o id do Thread e deixará o Thread que tiver o menor id.

Similar Posts

Deixe uma resposta

O seu endereço de email não será publicado.