Problemas de exclusão mútua

Um problema típico que normalmente é preciso resolver em sistemas concorrentes é o controlo de acesso a um recurso que não pode ser partilhado. Considere, por exemplo, o caso de uma impressora partilhada por várias pessoas: se não se garantir que apenas um documento é impresso de cada vez podem saír páginas de vários documentos intercaladas. No geral, podemos dividir as operações a realizar pelos vários processos em críticas, quando tem que ser executadas em exclusividade, e não críticas, quando podem ser executadas concorrentemente com outras operações. Resolver o problema da exclusão mútua consiste em descobrir um protocolo que garanta os seguintes requisitos:

• Exclusão. Em cada instante, encontra-se no máximo um processo na sua região crítica.
• Acessibilidade. Todo processo que tente entrar na sua região crítica deve eventualmente poder fazê-lo.

Quando se pretende analisar a validade de um protocolo para resolver o problema de exclusão mútua não importa saber quais são as instruções críticas e as instruções não críticas. Apenas é necessário especificar as regiões do programa onde essas intruções se encontram. O objectivo das instruções esquemáticas critical e noncritical é precisamente esse. Um programa que resolve o problema da exclusão mútua deve conter pelo menos estas duas instruções e algumas instruções de coordenação entre elas. O esqueleto de um programa que resolve o problema da exclusão mútua entre dois processos encontra-se na figura 1.4.

  

Figure 1.4: Exclusão mútua entre dois processos

% declaracoes

P1:: [
    l0: loop forever do [
        l1: noncritical;
        % protocolo de entrada
        l2: critical;
        % protocolo de saida
    ]
]

||

P2:: [
    m0: loop forever do [
        m1: noncritical;
        % protocolo de entrada
        m2: critical;
        % protocolo de saida
    ]
]

Na figura temos o esqueleto de um programa que resolve o problema da exclusão mútua entre N processos.

  

Figure 1.5: Exclusão mútua entre N processos

in N : int where N>0
% restantes declaracoes

|| P[i:[1..N]] :: [
    l0: loop forever do [
        l1: noncritical;
        % protocolo de entrada
        l2: critical;
        % protocolo de saida
    ]
]

Uma solução típica para o problema da exclusão mútua surge através da utilização de semáforos (ver figura 1.6 para o caso de 2 processos e a figura 1.7 para o caso de N processos). Explicar ...

  

Figure 1.6: Exclusão mútua entre 2 processos utilizando semáforos

local y : int where y=1

P1:: [
    l0: while (true) do [
        l1: noncritical;
        l2: request y;
        l3: critical;
        l4: release y
    ]
]

||

P2:: [
    m0: while (true) do [
        m1: noncritical;
        m2: request y;
        m3: critical;
        m4: release y
    ]
]

  

Figure 1.7: Exclusão mútua entre N processos utilizando semáforos

in    N : int where N>0
local y : int where y=1

|| P[i:[1..N]] :: [
    l0: loop forever do [
        l1: noncritical;
        l2: request y;
        l3: critical;
        l4: release y
    ]
]

No entanto existem soluções bem mais complicadas para este problema. Veja-se, por exemplo, na figura 1.8 a solução proposta por Dekker para resolver o problema da exclusão mútua entre dois processos. Explicar ...

  

Figure 1.8: Exclusão mútua segundo o algoritmo de Dekker

local y1, y2 :bool where y1 = false, y2 = false
local t :int where t = 1

P1:: [
    l0: loop forever do [
        l1: noncritical;
        l2: y1 := true;
        l3: while (y2) do
            l4: if (t = 2) then [
                l5: y1 := false;
                l6: await (t = 1);
                l7: y1 := true
            ];
        l8: critical;
        l9: t := 2;
        l10: y1 := false
    ]
]

||

P2:: [
    m0: loop forever do [
        m1: noncritical;
        m2: y2 := true;
        m3: while (y1) do
            m4: if (t = 1) then [
                m5: y2 := false;
                m6: await (t = 2);
                m7: y2 := true
            ];
        m8: critical;
        m9: t := 1;
        m10: y2 := false
    ]
]