Re: [reverbel-mac438] [MAC438] Exercícios do cap. 3

[Francisco Reverbel <reverbel@xxxxxxxxxx>]

Você pretendia mandar sua solução para a lista, Cristiane, mas só eu a
recebi. Estou reenviando para a lista, pois provavelmente outras pessoas
têm interesse nela.

On Sun, 2006-04-30 at 21:40 -0300, Cristiane Maria Sato wrote:
> bool livre = true;
> process CS[i =1 to n] {
>   bool possoEntrar;
>   while(true) {
>    /*entrando*/
>    possoEntrar = false;
>    Swap(livre, possoEntrar);
>    while(possoEntrar == false) { Swap(livre, possoEntrar);}
>    região crítica;
>    /*saindo*/
>    Swap(livre, possoEntrar);
>    região não crítica;
>  }
> }
> 
> A idéia é que apenas um possoEntrar fica true por vez.

A solução da Cristiane está correta. Ela ficaria um pouco melhor com um
skip dentro do laço interno:

    while(possoEntrar == false) { skip; Swap(livre, possoEntrar); }

Embora o skip não faça diferença alguma do ponto de vista da
"corretude", ele diminui um pouco a contenção no acesso à variável
compartilhada entre os processos. 

A contenção no acesso a memória e o overhead causado pela invalidação do
cache de cada processador (assumindo uma máquina com múltiplos
processadores, é claro) poderia ser reduzida muito mais com uma
abordagem análoga à "test and test-and-set", que o Andrews descreve na
seção 3.2.2. Exercício: Reescrever a solução da Cristiane, agora usando
uma abordagem "test and swap" para reduzir a contenção no acesso à
memória compartilhada e o overhead de invalidação dos caches dos
processadores.

Reverbel

> 
> On 4/30/06, Cristiane Maria Sato <cmsato@xxxxxxxxx> wrote:
> > Bom, dica pro 3.3
> > Se eu estiver errada, alguém PELO AMOR DE DEUS, me corrija. =)
> >
> > O Swap simplesmente troca duas variáveis, certo?
> > Tente criar uma booleana global que indica se a região crítica está
> > disponível e
> > uma booleana para cada processo indicando se ele pode entrar em sua
> > região crítica.
> > Bom, no próximo e-mail estou mandando minha solução.
> >
> > On 4/30/06, Francisco Reverbel <reverbel@xxxxxxxxxx> wrote:
> > > [Esqueci de mudar a codificação do meu mailer para ISO 8859-1 antes de
> > > enviar a mensagem anterior, que foi arquivada de modo ilegível pelo
> > > mhonarc. :-( ]
> > >
> > > Solução do exercício 3.2:
> > >
> > > int lock = 1;                   /* shared lock (initially open) */
> > >
> > > process CS[i = 1 to n] {
> > >     int sign;
> > >
> > >     while (true) {
> > >         DEC(lock, sign);        /* entry protocol */
> > >         while (sign == 1) {
> > >             INC(lock, sign);
> > >             skip;
> > >             DEC(lock, sign);
> > >         }
> > >         critical section;
> > >         INC(lock, sign);        /* exit protocol */
> > >         noncritical section;
> > >     }
> > > }
> > >
> > > Reverbel
> > >
> > > On Sun, 2006-04-30 at 17:35 -0300, Francisco Reverbel wrote:
> > > > Se a gente puder usar alguma instrução especial atômica (tipo
> > > > "test-and-set") para resolver o problema da região crítica, em geral não
> > > > vai ter muita diferença entre a solução para 2 processos e a solução
> > > > para n processos. A dificuldade é geralmente a mesma.
> > > >
> > > > Para os exercícios 3.2 e 3.3, a dica é olhar para a solução com a
> > > > "test-and-set", que está na figura 3.3 do Andrews, e tentar trocar o TS
> > > > por outra instrução atômica, como DEC ou Swap.
> > > >
> > > > Vou mandar outra mensagem com uma solução para o exercício 3.3. Façam
> > > > esse exercício *antes* de ler a minha próxima mensagem para a lista!
> > > >
> > > > Reverbel
> > > >
> > > > On Sun, 2006-04-30 at 14:18 -0300, Mariana Bravo wrote:
> > > > > Olá!
> > > > >
> > > > > Estou estudando o capítulo 3 e tentando fazer os exercícios indicados.
> > > > >
> > > > > Alguém tem alguma DICA de como resolver o ex 3.2? Ou o 3.3?
> > > > >
> > > > > Tentei simplificar para resolver com apenas 2 processos, mas ainda sim me
> > > > > falta criatividade.
> > > > >
> > > > > Mariana
> > > >
> > >
> > >
> >
> >
> > --
> > Cristiane Maria Sato
> > <cmsato@xxxxxxxxx>
> >
> 
> 
> --
> Cristiane Maria Sato
> <cmsato@xxxxxxxxx>
>