ࡱ> /1.*bjbjUU :??*   QQQQQeeee q e: }}}}}}}}DJQ}}}}}QQ}}}}}}Q}Q}}}}}}@e} 0:0 }0 0 Q }}}}}}}}}}}}:}}}}0 }}}}}}}}} :Resumo Computao distribuda consiste em um conjunto de processos que cooperam entre si e compartilham recursos atravs de troca de mensagens para a execuo de uma dada tarefa. Deadlocks em uma computao distribuda ocorrem quando um conjunto de processos espera indefinidamente por recursos provenientes do mesmo conjunto. Sistemas que efetuam uma computao distribuda so usualmente representados por grafos de espera, onde o comportamento de cada processo determinado por um modelo de deadlock, que define as regras de como esses processos tornam-se executveis. Neste trabalho, primeiramente so revisados os principais modelos de deadlock, e em alternativa ao modelo E-Ou, proposto um novo modelo de deadlock, de mais simples representao e compatvel com estruturas de dados clssicas, os grafos e/ou. Posteriormente, descreve-se formalmente como um modelo de deadlock generaliza um segundo modelo, primando a complexidade computacional como parmetro. Por consequncia, a hierarquia clssica de modelos de deadlock modificada, e duas novas hierarquias so apresentadas; a primeira leva em considerao apenas tempo computacional, e a segunda considera tambm a profundidade. Em seguida, so provadas equivalncias e transformaes polinomiais entre os grafos de espera nos modelos clssicos de deadlock e os grafos e/ou (grafos xy), os mais conhecidos na literatura. Para tais grafos, so apresentadas duas estruturas genricas: a primeira, chamada de subgrafo soluo, uma estrutura j conhecida na literatura, que, para grafos de espera em computao distribuda, indica que todos os processos que pertencem ao subgrafo no esto em deadlock; a segunda, chamada de subgrafo no-soluo, caracteriza situaes de deadlock. Finalmente, define-se Deadlock-Resolution(a, b) como uma classe de problemas de otimizao para resoluo de deadlock. Cada problema indicado pela combinao de dois parmetros. O primeiro, 'a', indica o modelo de deadlock do grafo de espera. O segundo, 'b', indica o tipo de operao a ser utilizada para a eliminao de deadlocks no grafo. desenvolvido um estudo sobre a complexidade computacional de cada problema, onde, sempre que possvel, so fornecidos algoritmos eficientes para a soluo dos problemas. Para o problema Deadlock-Resolution(Ou, Vrtice), prova-se sua intratabilidade para instncias genricas, e so estudadas diversas classes de grafos que correspondem a caractersticas estruturais que tornam o problema intratvel. Palavras-chave: sistemas distribudos, deadlock, grafos de espera, grafos e/ou, complexidade computacional. . 2 9 = F H  )*ʵʵʵʠʵʚ h1^J)h15B*CJOJQJ\^JaJph)h16B*CJOJQJ]^JaJph#h1B*CJOJQJ^JaJphh1B*OJQJ^Jph)h15B*CJ OJQJ\^JaJ ph? * $dh9a$ $dh9a$ $dh9a$8P:p1. A!n"#$R% Dp^ 666666666vvvvvvvvv66666686666666666666666666666666666666666666666666666666hH6666666666666666666666666666666666666666666666666666666666666666662 0@P`p2( 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p8XV~_HmHnHsHtHZ`Z Normal*$1$,CJKHOJQJ^J_HaJmHnHsHtH`!2` 0 Heading 1& & F hP@&^`P5CJ$\aJ$d!2d 0 Heading 2* & F h@@@&^@`5CJ \aJ \!2\ 0 Heading 3* & F h0@&^`05\DA D 0Default Paragraph FontRiR 0 Table Normal4 l4a (k ( 0No List ^/^  T9Heading 1 Char*5CJ KH OJPJQJ\^JaJ nHtHd/d  T9Heading 2 Char056CJKHOJPJQJ\]^JaJnHtH^/^  T9Heading 3 Char*5CJKHOJPJQJ\^JaJnHtHJ2J 0Ttulo1 $xCJOJQJ^JaJ8B28 0 Body Text d T/AT  T90Body Text Char CJKHOJQJ^JaJnHtH$/1R$ 0List<"b< 0Caption  $xx6],r, 0ndice $@@ 0Citaes77]7^7:>!2: 0Title$a$5CJ8\aJ8V/V  T9 Title Char*5CJ KHOJPJQJ\^JaJ nHtH>J!2> 0Subtitle $<a$CJ$aJ$V/V  T9 Subtitle Char$CJKHOJPJQJ^JaJnHtHTOT 0Texto prformatadoCJOJQJ^JaJPK![Content_Types].xmlj0Eжr(΢Iw},-j4 wP-t#bΙ{UTU^hd}㨫)*1P' ^W0)T9<l#$yi};~@(Hu* Dנz/0ǰ $ X3aZ,D0j~3߶b~i>3\`?/[G\!-Rk.sԻ..a濭?PK!֧6 _rels/.relsj0 }Q%v/C/}(h"O = C?hv=Ʌ%[xp{۵_Pѣ<1H0ORBdJE4b$q_6LR7`0̞O,En7Lib/SeеPK!kytheme/theme/themeManager.xml M @}w7c(EbˮCAǠҟ7՛K Y, e.|,H,lxɴIsQ}#Ր ֵ+!,^$j=GW)E+& 8PK!Ptheme/theme/theme1.xmlYOo6w toc'vuر-MniP@I}úama[إ4:lЯGRX^6؊>$ !)O^rC$y@/yH*񄴽)޵߻UDb`}"qۋJחX^)I`nEp)liV[]1M<OP6r=zgbIguSebORD۫qu gZo~ٺlAplxpT0+[}`jzAV2Fi@qv֬5\|ʜ̭NleXdsjcs7f W+Ն7`g ȘJj|h(KD- dXiJ؇(x$( :;˹! I_TS 1?E??ZBΪmU/?~xY'y5g&΋/ɋ>GMGeD3Vq%'#q$8K)fw9:ĵ x}rxwr:\TZaG*y8IjbRc|XŻǿI u3KGnD1NIBs RuK>V.EL+M2#'fi ~V vl{u8zH *:(W☕ ~JTe\O*tHGHY}KNP*ݾ˦TѼ9/#A7qZ$*c?qUnwN%Oi4 =3ڗP 1Pm \\9Mؓ2aD];Yt\[x]}Wr|]g- eW )6-rCSj id DЇAΜIqbJ#x꺃 6k#ASh&ʌt(Q%p%m&]caSl=X\P1Mh9MVdDAaVB[݈fJíP|8 քAV^f Hn- "d>znNJ ة>b&2vKyϼD:,AGm\nziÙ.uχYC6OMf3or$5NHT[XF64T,ќM0E)`#5XY`פ;%1U٥m;R>QD DcpU'&LE/pm%]8firS4d 7y\`JnίI R3U~7+׸#m qBiDi*L69mY&iHE=(K&N!V.KeLDĕ{D vEꦚdeNƟe(MN9ߜR6&3(a/DUz<{ˊYȳV)9Z[4^n5!J?Q3eBoCM m<.vpIYfZY_p[=al-Y}Nc͙ŋ4vfavl'SA8|*u{-ߟ0%M07%<ҍPK! ѐ'theme/theme/_rels/themeManager.xml.relsM 0wooӺ&݈Э5 6?$Q ,.aic21h:qm@RN;d`o7gK(M&$R(.1r'JЊT8V"AȻHu}|$b{P8g/]QAsم(#L[PK-![Content_Types].xmlPK-!֧6 +_rels/.relsPK-!kytheme/theme/themeManager.xmlPK-!Ptheme/theme/theme1.xmlPK-! ѐ' theme/theme/_rels/themeManager.xml.relsPK] * * * P^`P@@^@`0^`0``^``^`^`^``^``00^0`#O1* , @* @@UnknownG*Ax Times New Roman5Symbol3. *Cx ArialI xP!Liberation SerifG& xP!Liberation Sans7@CambriaG5 x@Liberation MonoACambria Math" zDzD! 0 $P* #O!xxResumoHelioHelio Oh+'0x  4 @ LX`hpResumoHelioNormal_WordconvHelio2Microsoft Office Outlook@^в@@՜.+,0 hp|   Resumo Title  !"#$%'()*+,-0Root Entry F021Table @ WordDocument:SummaryInformation(DocumentSummaryInformation8&CompObjy  F'Microsoft Office Word 97-2003 Document MSWordDocWord.Document.89q  F#Documento do Microsoft Office Word MSWordDocWord.Document.89q