Em sistemas operacionais há alguns algoritmos para solucionar os problemas de competição de processos por recursos ou regiões criticas. Os mais conhecidos são a solução de peterson e o de semáforos. Geralmente, ao menos na UFRN, onde eu estudo as soluções implementadas são em Java. Como eu odeio Java, apesar de programar nessa coisa, preferi fazer as implementações em python e ficaram bons os resultados.
A principio irei falar sobre cada um dos algoritmo e apresentar a solução em python =].
Solução por Variáveis de travamento
Nesse algoritmo há apenas uma variável compartilhada (variável de travamento), cujo o valor inicial é 0. Quando algum processo deseja entrar em sua região critica, ele deve primeiro estar essa variável . Caso ela seja 0, o processo a muda para 1 e entra na região critica. Se o valor da variável de travamento já for 1, o processo vai esperar que o valor volte para 0, antes de entrar na região critica.
CODE
#! /usr/bin/env python
# -*- coding: utf-8 -*-
from threading import Thread
from time import sleep
lock = 0 # Variável de travamento
class Processo(Thread):
def __init__(self, p):
Thread.__init__(self)
self.p = p
def run(self):
global lock
while True:
if lock == 0:
lock = 1
print "processo %d entrou na regiao critica" %self.p
lock = 0
print "processo saiu da regiao critica"
else:
sleep(60) # delay de 60
sleep(3) # delay de 3 só pra deixar tudo mais emocionante =P.
p1 = Processo(0)
p2 = Processo(1)
p1.start()
p2.start()
Problemas desta solução
Pode ocorrer de um processo ler a variável de travamento com valor 0, mas antes que ele mude o valor para 1 pode ocorrer uma interrupção, e outro processo pode ser colocado para executar. Este segundo processo irá ler lock verificar que o seu valor é 0, seta-lo para 1 e entrar na região critica. Quando o primeiro processo volta vê que no seu contexto lock vale 0, seta o seu valor para 1 e entra na região critica. Ou seja os dois processos estão executando suas regiões criticas ao mesmo tempo.
(Desafio a programadores Java fazerem esse código mais limpo e bonito que em python =P).
Solução por Estrita Alternância
Nesta solução há uma variável chamada de turn que inicialmente está com valor 0. É ela quem irá determinar de quem é a vez de entrar na região crítica. A princípio um processo verifica turn se o professo for 0 e o turn for igual a 0 ele entra na sua região crítica, caso contrário ele entra em um loop até que turn seja igual a 1.
CODE
#! /usr/bin/env python
# -*- coding: utf-8 -*-
from threading import Thread
from time import sleep
turn = 0
class Processo(Thread):
def __init__(self, myturn):
Thread.__init__(self)
self.turn = myturn
def run(self):
global turn
while True:
while turn != self.turn:
sleep(3)
print "Processo",self.turn
turn = not turn
p1 = Processo(0)
p2 = Processo(1)
p1.start()
p2.start()
Problemas desta solução
Como deve pra ter notado caso um processo passe muito tempo na sua região crítica o outro irá esperar por um longo tempo até conseguir na sua. Esse teste contínuo do valor de turn, esperando que ela torne-se 1, é chamado de espera ocupada. Em resumo, a espera ocupada deve ser evitada, pois consome tempo do processador. Em casos onde se supõe que a espera será curta, então pode-se usar esta solução.
Solução de Peterson
Na solução de Peterson há duas funções uma é a Entrar na região (Enter_regiao), e a outro é Deixar região (Leave_regiao). Entrar na região possui um parâmetro que o numero do processo que está tentando entrar na região critica. Assim como Deixar região.
O algoritmo funciona da seguinte maneira. Quando Enter_regiao é chamado passando o numero do processo que deseja entrar, temos uma variável chamada outro, que nada mais é do que o outro processo. A lista de interessados é atualizada para o processo que entrou na região, com o valor true, e turn receberá o processo corrente. Enquanto turn for igual ao processo corrente, mas o processo interessado for o outro, o processo que chamou Enter_regiao irá ficar em espera ocupada.
No caso da função Leave_regiao é apenas passado o processo que irá sair da região e a lista de interessados para aquele processo é setada como False.
CODE
#! /usr/bin/env python
# -*- coding: utf-8 -*-
from threading import Thread
from time import sleep
turn = 0
interessados = [False,False]
class Regiao_critica:
def __init__(self,processo):
self.processo = processo
def enter_regiao(self):
global turn, interessados
outro = 1 - self.processo
interessados[self.processo] = True
turn = self.processo
if(turn == self.processo and interessados[outro] == False):
print "processo %d entrou na regiao critica" %self.processo
while(turn == self.processo and interessados[outro] == True): pass
def leave_regiao(self):
interessados[self.processo] = False
print "processo %d deixou a regiao critica" %self.processo
class Processo(Thread):
def __init__(self,processo):
Thread.__init__(self)
self.processo = processo
def run(self):
r = Regiao_critica(self.processo)
while True:
r.enter_regiao()
r.leave_regiao()
sleep(3)
p0 = Processo(0)
p1 = Processo(1)
p0.start()
p1.start()
Nos próximos post’s irei falar sobre semaforos, o problema dos filosos glutões, leitores e escritoes e do bardeiro dorminhoco.
continua…
