Prática SO UNEB Deadlock

Prévia do material em texto

Pra´tica de Deadlock
Michel Franc¸a Leal
Universidade do Estado da Bahia (UNEB)
Salvador - Bahia - Brasil
{mfrancaleal@gmail.com}
Resumo
Esta pra´tica tem como objetivo simular atrave´s de gra-
fos o relacionamento entre processos e recursos, identifi-
canto pontos crı´ticos, chamados de Deadlocks mas tambe´m
conhecidos como impasses, e caso necessa´rio, eliminando
o(s) processo(s) que esteja(m) relacionado(s) aos pontos
crı´ticos. Para essa pra´tica utilizaremos a linguagem de
programac¸a˜o C.
1. Introduc¸a˜o
EM seu livro, Maziero(2009)(1) diz que os Impasses
(Deadlocks) acontecem quando duas ou mais tarefas se en-
contram bloqueadas, aguardando eventos que so´ podem
ocorrer mediante a ac¸a˜o dele pro´prio, ou seja, ele espera
por algo que somente ele pode fazer mas na˜o faz e na˜o tem
como um mediador agir nesses casos e evitar o impasse. E´
comum que as tarefas de um conjunto tenha em seu poder
recursos que sa˜o compartilhados (sema´foros), e caso outras
tarefas que fac¸am a requisic¸a˜o desse recurso, elas tambe´m
ficara˜ bloqueadas, tornando o crescimento do impasse ex-
ponencial causando assim uma parada total do sistema ope-
racional.
2. Partes a serem trabalhadas
2.1. Entrada de Dados em formato de um
grafo
No co´digo criado(2), ao qual chamaremos de dea-
dlock.cpp, existe uma estrutura capaz de receber dados em
forma de grafos, tratando-os de uma forma capaz de infor-
mar pontos crı´ticos a processo(s) a sere(m) eliminado(s),
caso aja(m).
O programa recebe inicialmente o nu´mero de recursos
(representado por r), processos(representado por p) e
ligac¸o˜es (representado por aux), para poder utilizar essas
informac¸o˜es no auxı´lio da construc¸a˜o da matriz de ad-
jaceˆncias. Vejamos no co´digo abaixo:
1 i n t main ( i n t a rgc , c h a r ∗∗ a rgv )
2 {
3 boo l g r a f o [MAX] [MAX] ;
4 i n t r , p , aux , x , y ;
5 c h a r cx , cy ;
6
7 memset ( g r a f o , 0 , s i z e o f ( g r a f o ) ) ;
8 p r i n t f ( ” Q u a n t i d a d e de r e c u r s o : ” ) ;
9 s c a n f ( ”%d ” , &r ) ;
10 p r i n t f ( ” Q u a n t i d a d e de p r o c e s s o s : ” ) ;
11 s c a n f ( ”%d ” , &p ) ;
12 p r i n t f ( ” Quandas l i g a c o e s : ” ) ;
13 s c a n f ( ”%d ” , &aux ) ;
14 p r i n t f ( ”%d\n ” , aux ) ;
15
16 f o r ( i n t i = 0 ; i < aux ; i ++ )
17 {
18 p r i n t f ( ”%dLG : ” , i +1 ) ;
19 s c a n f ( ” %c%d %c%d ” , &cx , &x , &cy , &y ) ;
20
21 i f ( cx == ’P ’ ) x += r ;
22 i f ( cy == ’P ’ ) y += r ;
23
24 g r a f o [ x−1][y−1] = t r u e ;
25 }
26
27 i m p r i m i r ( g r a f o , r , p ) ;
28 DFS ( g r a f o , r , p ) ;
29 r e t u r n 0 ;
30 }
Listing 1: Recebe os dados informados
2.1.1 Grafos utilizados
Figura 1: Grafo 1
Figura 2: Grafo 2
Figura 3: Grafo 3
Figura 4: Grafo 4
2.2. Construc¸a˜o da matriz de adjaceˆncias a
partir grafo direcionado
Com os dados do grafo informado pelo usua´rio, algo-
ritmo cria a de adjaceˆncia. Essa matriz exibe as ligac¸o˜es
entre processos e recursos, quando existe a presenc¸a do
nu´mero 1 e´ porque existe uma ligac¸a˜o quando e´ 0 na˜o ha´
ligac¸a˜o. Vejamos o algoritmo responsa´vel pela criac¸a˜o:
1 vo id i m p r i m i r ( boo l g r a f o [MAX] [MAX] , i n t r , i n t
p )
2 {
3 p r i n t f ( ”\n−−−−−−−−−−−−−−−−−−−−−−−−−−−−\n ” ) ;
4
5 p r i n t f ( ”\ t ” ) ;
6 f o r ( i n t i = 0 ; i < r ; i ++ )
7 p r i n t f ( ”R%d\ t ” , i +1) ;
8 f o r ( i n t i = 0 ; i < p ; i ++ )
9 p r i n t f ( ”P%d\ t ” , i +1) ;
10 p r i n t f ( ”\n ” ) ;
11
12 f o r ( i n t i = 0 ; i < r +p ; i ++ )
13 {
14 i f ( i < r ) p r i n t f ( ”R%d\ t ” , i +1) ;
15 e l s e p r i n t f ( ”P%d\ t ” , i−r +1) ;
16
17 f o r ( i n t j = 0 ; j < r +p ; j ++ )
18 p r i n t f ( ”%d\ t ” , g r a f o [ i ] [ j ] ) ;
19
20 p r i n t f ( ”\n ” ) ;
21 }
22 p r i n t f ( ”−−−−−−−−−−−−−−−−−−−−−−−−−−−−\n ” ) ;
23 }
Listing 2: Impressa˜o da Matriz
Utilizamos o grafo1 para gerar a primeira matriz o obti-
vemos os seguintes resultados:
2.2.1 Matriz 1
R1 R2 R3 P1 P2 P3
R1 0 0 0 0 1 0
R2 0 0 0 1 1 0
R3 0 0 0 0 0 1
P1 1 0 0 0 0 0
P2 0 0 1 0 0 0
P3 0 0 0 0 0 0
Tabela 1: Primeiro Grafo
Podemos notar que existe o nu´mero 1 justamente onde ha´
ligac¸a˜o entre processo e recurso demonstrado atrave´s do
grafo1.
R1 R2 R3 P1 P2 P3
R1 0 0 0 0 1 0
R2 0 0 0 1 1 0
R3 0 0 0 0 0 1
P1 1 0 0 0 0 0
P2 0 0 1 0 0 0
P3 0 1 0 0 0 0
Tabela 2: Segundo Grafo
Como na Tabela 1, existe o nu´mero 1 indicando ligac¸a˜o.
R1 R2 R3 R4 R5 P1 P2 P3 P4 P5
R1 0 0 0 0 0 0 1 0 0 0
R2 0 0 0 0 0 1 0 0 0 0
R3 0 0 0 0 0 0 0 0 0 1
R4 0 0 0 0 0 0 0 1 0 0
R5 0 0 0 0 0 0 0 0 1 0
P1 1 0 0 0 0 0 0 0 0 0
P2 0 0 1 1 1 0 0 0 0 0
P3 0 0 0 0 1 0 0 0 0 0
P4 0 1 0 0 0 0 0 0 0 0
P5 0 0 0 0 0 0 0 0 0 0
Tabela 3: Terceiro Grafo
R1 R2 P1 P2 P3 P4
R1 0 0 0 1 1 0
R2 0 0 1 0 0 1
P1 0 0 0 0 0 0
P2 1 0 0 0 0 0
P3 0 1 0 0 0 0
P4 0 0 0 0 0 0
Tabela 4: Quarto Grafo
2.3. Identificac¸a˜o dos subciclos nos grafos
Um ciclo de deadlock envolve processos que esperam inde-
finidamente por um evento que somente pode ser causado
por um dos processos em espera. O algoritmo identifica os
sub-ciclos do deadlock no grafo no seguinte trecho do algo-
ritmo:
1 f o r ( i n t k = 0 ; k < t ; k ++)
2 i f ( p i l h a [ k ] == i | | imp ) {
3 imp = t r u e ;
4 i f ( p i l h a [ k]< r )
5 p r i n t f ( ”R%d −> ” , p i l h a [ k ] + 1 ) ;
6 e l s e
7 p r i n t f ( ” P%d −> ” , p i l h a [ k]− r +1) ;
8 }
Segue a baixo os sub-ciclos de cada exemplo abordado:
Observac¸a˜o: Na˜o ha´ sub-ciclo para o exemplo 1 por na˜o
haver deadlock
Figura 5: Sub-ciclo exemplo 2
Figura 6: Sub-ciclo exemplo 3
Figura 7: Sub-ciclo exemplo 4
2.4. Apontando processo(s) cr´ıtico(s) no
grafo
Processos crı´ticos sa˜o os processos envolvidos diretamente
no deadlock,o programa para identificar isso utiliza um loop
for para controlar as leituras nos limites do vetor pilha,o
vetor pilha possui os valores nume´ricos das ligac¸o˜es entre
processos e recursos definidos pelo usua´rio.
1 imp = f a l s e ;
2 i n t e r r o m p i d o = −1;
3 f o r ( i n t k = 0 ; k < t ; k++ )
4 i f ( p i l h a [ k ] == i | | imp ) {
5 i f ( p i l h a [ k ] >= r ) {
6 p r i n t f ( ” P%d ” , p i l h a [ k]− r +1) ;
7 i f ( i n t e r r o m p i d o < 0 )
8 i n t e r r o m p i d o = p i l h a [ k ] ;
9 }
10 imp = t r u e ;
11 }
Os processos crı´ticos de cada exemplo sa˜o:
Exemplo 1: Na˜o ha´ processo crı´tico
Exemplo 2: P2, P3 e P1
Exemplo 3: P1, P2, P3 e P4
Exemplo 4: P1 e P3
2.5. Tratando processos para evitar dea-
dlocks
Existem diversas maneiras de tratar um deadlock. Uma de-
las e´ eliminar um processo crı´tico que, sem ele, na˜o havera´
deadlock. O algoritmo identifica qual o processo crı´tico a
ser eliminado e apaga sua ligac¸o˜es na varia´vel grafo no se-
guinte trecho:
1 p r i n t f ( ” P r o c e s s o I n t e r r o m p i d o : P%d\n ” ,
2 i n t e r r o m p i d o−r +1) ;
3 p i l h a [ i n t e r r o m p i d o ] = −1;
4
5 f o r ( i n t k = 0 ; k < r +p ; k++ )
6 g r a f o [ k ] [ i n t e r r o m p i d o ]= g r a f o [ i n t e r r o m
7 p ido ] [ k ] = 0 ;
Nos exemplos, os processos crı´ticos eliminados sa˜o:
Exemplo 1: Na˜o ha´ processo crı´tico a ser eliminado
Exemplo 2: P2
Exemplo 3: P2
Exemplo 4: P3
Refereˆncias
[1] C. A. Maziero. (2008) Sistemas operacionais
2 - gereˆncia de tarefas. [Online]. Available:
http://www.ppgia.pucpr.br/maziero
[2] M. Boratto. Pra´ticas - memo´ria. [Online]. Available:
http://muriloboratto.com.br