Embed Size (px)
Citation preview
1
ISRAEL JOSÉ DA CUNHA
ALGORITIMO DE THREADS
UNIVERSIDADE DO VALE DO SAPUCAÍ
POUSO ALEGRE
2010
2
ISRAEL JOSÉ DA CUNHA
ALGORITIMO DE THREADS
Trabalho de Sistema de Informação
apresentado ao curso de Sistemas
Operacionais de Pouso Alegre como requisito
parcial para obtenção de nota da disciplina:
Sistemas Operacionais.
UNIVERSIDADE DO VALE DO SAPUCAÍ
POUSO ALEGRE
2010
3
SÚMARIO
1 INTRODUÇÃO……………………………………………………………………01
2 Algoritmo “Primeiro”……………………………………………………………..02
3 Algoritmo “Segundo”……………………………………………………………..03
5 Algoritmo “Quarto”……………………………………………………………....06
6 Algoritmo de Dekker………………………………………………………………08
7 Algoritmo de Peterson…………………………………………………………….11
4
1 INTRODUÇÃO
Este trabalho tem objetivo demonstrar o uso de algoritmos para controle de
threads apostando soluções gradativas dos códigos.
O que é uma thread? Pode-se dizer que um thread é um procedimento que é
executado dentro de um processo de uma forma independente. Para melhor perceber a
estrutura de um thread é útil entender o relacionamento entre um processo e um thread.
Um processo é criado pelo sistema operacional e podem conter informações
relacionadas com os recursos do programa e o estado de execução do programa, Os
threads utilizam os recursos de um processo, sendo também capazes de ser escalonados
pelo sistema operacional e serem executados como entidades independentes dentro de
um processo. Um thread pode conter um controlo de fluxo independente e ser
escalonável, porque mantêm o seu próprio.
5
2 Algoritmo “Primeiro”
Essa solução garante que apenas um thread de cada vez possa estar em sua seção
crítica. No entanto, não satisfaz o requisito de progresso, já que requer a troca estrita dos
threads a execução de sua seção crítica. Por exemplo, se turn=0 e o thread T1 estiver
pronto para entrar em sua seção crítica, então T1 não poderá faze-lo, mesmo que T0
possa estar em sua seção não-crítica.
Public class Algorithm_1 extends Mutual Exclusion
{
Public Algorithm_1( ) {
turn=TURN_0;
public void enteringCriticalSection(int){
while (turn!= t)
thread.yield( );
}
public void leavinCriticalSectiom(int t){
turn =1-t;
}
Private volation int turn;
}
6
3 Algoritmo “Segundo”
O problema do algorimo 1 é que ele não retém informaões suficientes sobre o
estado de cada thread ; ele se lembra apenas de qual thread tem permissão para entrar
em situação crítica. Para resolver esse problema podemos substituir a variável turn pelo
seguinte vetor:
boolean[ ] flag = new boolean [2];
Os elementos do vetor são inicializados como false. Se flag[i] for true, esse valor
indica que o thread Ti esta pronto para entrar em na sua seção crítica.Ao sair da seção
crítica.
Nesse algoritmo, o thread Ti primeiro define flag[i] como true, indicando que
esta pronto para entrar em sua seção crítica.Em seguida , Ti verifica se o thread Tj
também não está pronto para entrar em sua seção crítica.
Se Tj estiver pronto, Ti espera ate Ti indicar que não precisa mais estar na seção
crítica(ou seja, até que flag[j] seja false).Nesse ponto, Ti entra em sua seção crítica. Ao
sair da seção crítica, Ti define seu flag para false, permitindo que outro thread (se ele
estiver esperando) entre em sua seção crítica.
Nessa solução , o requisito de exclusão mutua é atendido.Infelizmente, o
requisito de progresso ainda não foi atendido.Para ilustrar esse problema, considere a
seguinte seqüência de execução: vamos supor que o thread T0 defina flag[0] para true,
indicando que ele deseja entrar em sua seção crítica.Antes que possa começar a
execução do loop while, ocorre uma troca de contexto e o thread T1 define a flag [1]
também para true.Quando ambos os threads executarem a instrução while, eles entrarão
em um laço infinito, já que o valor de flag para o outro thread é true.
public class algorithm_2 extends Mutua Exclusion
{
public Algorithm_2 ( ) {
flag[0] = false ;
7
flag[1] = false;
}
public void enterngCriticalsection(int t){
int other;
other =1 –t;
flag[t] – true;
while (flag[other] = = true)
thread.yiead( );
}
public void leavingCriticalSection(int t){
flag[t] = false;
}
private volatile Boolean [ ] flag = new Boolean [2];
}
4 Algoritimo “Terceiro”
Combinando as principais idéias dos algoritmos 1 e 2 , obtemos uma solução
correta para o problema de seção crítica, na qual todos os três requisitos são atendidos.
Os threads compartilham duas variáveis:
boolean[ ] flag = new boolean[2];
int turn;
8
Inicialmente, cada elemento do vetor é definido como false, e o valor de turn é
indefinido(pode ser 0 ou 1).
public class Algorithm_3 extends MultualExclusion
{
public Algorithm_3( ) {
flag[0] = false;
flag[1] = false;
turn = TURN_0; }
public void enteringCriticalSection (int t) {
int other;
other = 1 – t;
flag[t] = true;
turn=other;
while( (flag[other] = = true) && (turn = = other) )
thread.yield( );
}
public void leavingCriticalSection(int t){
flag[t] = false;
}
private volatile int turn;
private volatile Boolean [ ] flag = new Boolean[2];
}
Para entrar em sua seção crítica , o thread Ti, primeiro define flag[i] como true, e
declara que é a vez do outro thread entrar também, se for o caso (turn = = j). Se ambos
9
threads tentarem entrar ao mesmo tempo, turn é definido como i e como j praticamente
ao mesmo tempo Apenas um dessas atribuições perdura; a outra ocorreram nas será
sobrescrita imediatamente, O valor final de turn decide qual dos dois threads terá
permissão para entrar em sua seção crítica primeiro.
5 Algoritmo “Quarto”
Cada processo (P1), ao entrar no ciclo WHILE, após ter verificado que o outro
(P2, com c2 = 0) também estava a tentar entrar ou já lá estava dentro, desiste
'temporariamente' (c1 = 1) e depois, possivelmente após algum tempo, volta a insistir
(c1 = 0). Em princípio, verificar-se-á uma probabilidade muito pequena de que, estando
ambos a tentarem entrar concorrentemente, os dois desistam e insistam a um ritmo tal
que encontram sempre o outro a insistir e, assim, nunca saiam dos seus ciclos WHILE.
Contudo, essa possibilidade existe e conduziria a uma situação de bloqueio mútuo dos
dois processos. Assim, esta tentativa deve também ser rejeitada, pois uma solução do
problema tem de funcionar em todos os possíveis cenários de execução. Apesar de tudo,
esta tentativa dá uma boa idéia para se resolver este problema. Basta tornar o
comportamento dos dois processos assimétrico, isto é, em vez de desistirem e insistirem
ambos, obrigou apenas um deles a desistir e mantê-lo desistindo, enquanto o outro não
tiver saído da região crítica.
A solução pode ainda provocar uma “forma” de deadlock: o livelock (situação em
que até que existe possibilidade de sucesso, mas pode acontecer dos 2 nunca
conseguirem entrar na RC!). Exemplo:
P1 ajusta C1 para 0
P2 ajusta C2 para 0
P1 verifica C2 e permanece em
loop
P2 verifica C1 e permanece em
loop
P1 reseta C1 para 1
P2 reseta C2 para 1
P1 ajusta C1 para 0
P2 ajusta C2 para 0
P1 verifica C2 e permanece em
loop
P2 verifica C1 e permanece em
loop...
10
11
C1, C2: Integer range 0..1 := 1;
task body P1 is
begin
loop
Regiao_Nao_Critica_1;
C1 := 0;
loop
exit when C2 = 1;
C1 := 1;
C1 := 0;
end loop;
Regiao_Critica_1;
C1 := 1;
end loop;
end P1;
task body P2 is
begin
loop
Regiao_Nao_Critica_2;
C2 := 0;
loop
exit when C1 = 1;
C2 := 1;
C2 := 0;
end loop;
Regiao_Critica_2;
C2 := 1;
end loop;
end P2;
6 Algoritmo de Dekker
O Algoritmo de Dekker resolve o problema da exclusão mútua, que foi ilustrado para o
caso de dois processos concorrentes, partilhando um recurso num sistema de memória
partilhada. O algoritmo utiliza uma abordagem baseada em espera activa (busy activa),
na qual um processo, que não pode aceder à sua região crítica, fica em ciclo de teste de
variáveis partilhadas.
12
shared int certo = 1;
''/* Definição de varias variáveis
compartilhadas */ ''
shared int bandera[2] = {0,0};
shared int turno = 0;
while (certo)
{
bandera[proc_id] = cierto;
while (bandera[1-proc_id] == certo)
{
if (turno == 1-proc_id)
{
bandera[proc_id] = 0;
while (turno == (1-proc_id))
/* espera outro processo (turno)
começar*/;
bandera[proc_id] = 1;
}
}
/* “sessão critica”*/
turno = 1-proc_id;
/* Outro processo (turno)*/
bandera[proc_id] = 0;
/* “sessão critica”*/ }
13
Uma solução deste tipo só é aceitável se houver um número de CPUs igual (ou
superior) ao número de processos que se devam executar no sistema. Nesse caso,
podemo-nos dar 'ao luxo' de consumir ciclos de CPU, processos que não fazem mais
nada senão aguardar até que possam entrar. Como esta situação é rara na prática, onde,
em geral, há mais processos do que CPUs disponíveis - em geral, na maioria dos
computadores, ainda só há um único CPU -, isto significa que a solução de Dekker é
pouco usada.
Contudo, a solução de Dekker mostrou que é possível resolver o problema
inteiramente por software, isto é, sem exigir instruções máquina especiais.
A solução de Dekker tem outra desvantagem, igualmente desagradável. Não
permite uma expansão de escala, em termos do número de processos participantes no
algoritmo, sem que se faça uma modificação significativa do programa que realiza o
algoritmo. Se quisermos estender aquela solução, de 2 para N processos, teremos de ter:
alteração do cobegin/coend, para criar N processos'
declaração de um vector de N variáveis Ci;
assumir que a variável vez passa a valer de 1 a N;
Alteração das condições de teste e afectação das variáveis partilhadas em todos
os processos envolvidos: os 2 existentes, mais os N-2 novos processos, que queríamos
introduzir no algoritmo.
Esta falta de modularidade não é aceitável em sistemas onde haja criação
dinâmica de processos. Precisamos de outras soluções, nas quais a entrada de um novo
processo no sistema não implique a reescrita total do código de todos os outros
processos (e a saída de cada processo, também!).
14
7 Algoritmo de Peterson
var flag: array [0...1] of boolean;
turn: 0...1; turn := 1;
procedure P0;
begin
repeat
flag[0] := true;
turn := 1;
while flag[1] and turn = 1
do {nothing};
<critical section>;
flag[0] := false;
<remainder>
forever
End;
flag[0] := false; flag[1] := false;
procedure P1;
begin
repeat
flag[1] := true;
turn := 0;
while flag[0] and turn = 0
do {nothing};
<critical section>;
flag[1] := false;
<remainder>
forever
end;
/************ ALGORITMO DE PETERSON *************/
#include <stdlib.h>
#include "rshmem.h" /*biblioteca não implementada*/
void incrementa(int *mem, int k) {
int i;
i=*mem; TP
i=i+k; TP
15
*mem=i;
}
int main(int argn, char **argv) {
FILE *fsal; /*Ponteiro para arquivo com saída de resultados*/
char *marcaFim, /*Ponteiro fim de zona de memoria compartilhada*/
*c1, /*Variavel de encerramento do processo-pai*/
*c2; /*variável de encerramento do processo-filho*/
int *vez, /*Variável da vez de entrada do processo*/
*recurso, /*Ponteiro a zona de memoria compartilhada*/
nIteracoes=0; /*Contador de interações do processo*/
/* Comprovação do número de argumentos */
if(argn!=3){
printf("Erro na entrada de argumentos/n");
exit(1);
}
/* Abertura de arquivos */
if((fsal=fopen(argv[2],"a+"))==NULL){
printf("Erro ao abrir o arquivo de saída\n");
exit(-1);
} /*Comprovação de abertura correta do arquivo de texto de entrada*/
nIteracoes = atoi(argv[1]);
/* criar zona de memoria compartilhada */
if (!crearMemoria())
16
fprintf(stderr, "Erro em criarMemoria\n");
recurso = (int *) memoria ;
turno = (int *) recurso + sizeof(int);
marcaFin = (char *) vez + sizeof(int) ;
c1 = (char *) marcaFim + sizeof(char);
c2 = (char *) c1 + sizeof(char);
*recurso = 0 ;
*marcaFin = 'p' ;
*c1='F';
*c2='F';
if (0!=fork()) { /* Processo Pai */
int i;
fprintf(fsal,"P1: SOU O PROCESSO PAI\n");
for (i=0; i<nIteracoes; i++){
*c1='T'; /* Secção */
*vez=2; /* de */
while (((*c2)=='T') && ((*vez)==2)); /* entrada */
incrementa(recurso, -5); /* Secção */
fprintf(fsal,"P1: recurso[%d]=%d\n", i, *recurso); /* critica */
*c1='F'; /* Secção de salida */
}/* fim do for */
while (*marcaFim != 'x') ; /* Processo-pai espera processo-filho */
17
fprintf(fsal,"O recurso que antes valia 0 agora vale %d\n", *recurso);
if (!eliminarMemoria()) /* eliminar memoria compartilhada */
fprintf(stderr, "erro em eliminarMemoria\n");
exit(0);
}/*if (0!=fork())*/
else { /* Proceso filho */
int i;
fprintf(fsal,"P2: SOU O PROCESSO FILHO\n");
for (i=0; i<nIteracoes; i++) {
*c2='T'; /* Secção */
*turno=1; /* de */
while (((*c1)=='T') && ((*turno)==1)); /* entrada */
incrementa(recurso, 5); /* Secção */
fprintf(fsal,"P2: recurso[%d]=%d\n", i, *recurso); /* critica */
*c2='F'; /* Secção de salida */
} /* fim do for */
/* Encerramento dos processos */
fclose(fsal);
/* término */
*marcaFim = 'x';
exit(0);
}/*fim do else Proceso-filho*/ //{watchatcha/#}
} /* *************** FIM MAIN ****************** */
18
•Solução simples de 1981.
• O processo ao tentar entrar na região
crítica:
– Seta a variável flag para true
– Indica para o caso de desempate que o outro processo será o vencedor
• Exclusão mútua é atingida.
– Uma vez que P0 tenha feito flag[0] = true, P1 não entrar na região crítica na primeira
tentativa.
– A variável turn sempre resolve o desenpate
• Bloqueio mútuo é evitado.
– Supondo P0 bloqueado no seu while, isso significa que flag[1] = true e que turn = 1.
Assim, P0 só pode entrar quando ou flag[1] tornar-se false ou turn passar a ser 0.
O algoritmo mostrado não funciona corretamente porque o teste de abre e sua atribuição
não é feita atomicamente.
Conceitualmente, um processo pode checar o valor de abre e passar pelo
condicional do while.Entretanto, antes do processo setar abre como falso, um outro
processo pode testar o while e setar abre como falso assim, o primeiro processo seta
também abre como falso e,conseqüentemente, ambos estão na região crítica Isso ocorre
quando processos têm tempo de execução diferentes.
