Dissertations / Theses on the topic 'Deadlock'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Deadlock.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
Dathi, Naiem. "Deadlock and deadlock freedom." Thesis, University of Oxford, 1989. https://ora.ox.ac.uk/objects/uuid:458852c5-fa20-41f4-8537-8085a063c546.
Full textPalmer, Geraint. "Modelling deadlock in queueing systems." Thesis, Cardiff University, 2018. http://orca.cf.ac.uk/117490/.
Full textAskman, Amelie. "Joint ventures : (deadlock-) låsningar och lösningar." Thesis, Stockholms universitet, Juridiska institutionen, 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:su:diva-153172.
Full textKinsy, Michel A. "Application-aware deadlock-free oblivious routing." Thesis, Massachusetts Institute of Technology, 2009. http://hdl.handle.net/1721.1/53316.
Full textCataloged from PDF version of thesis.
Includes bibliographical references (p. 67-71).
Systems that can be integrated on a single silicon die have become larger and increasingly complex, and wire designs as communication mechanisms for these systems on chip (SoC) have shown to be a limiting factor in their performance. As an approach to remove the limitation of communication and to overcome wire delays, interconnection networks or Network-on-Chip (NoC) architectures have emerged. NoC architectures enable faster data communication between components and are more scalable. In designing NoC systems, there are three key issues; the topology, which directly depends on packaging technology and manufacturing costs, dictates the throughput and latency bounds of the network; the flit control protocol, which establishes how the network resources are allocated to packets exchanged between components; and finally, the routing algorithm, which aims at optimizing network performance for some topology and flow control protocol by selecting appropriate paths for those packets. Since the routing algorithm sits on top of the other layers of design, it is critical that routing is done in a matter that makes good usage of the resources of the network. Two main approaches to routing, oblivious and adaptive, have been followed in creating routing algorithms for these systems. Each approach has its pros and cons; oblivious routing, as opposite to adaptive routing, uses no network state information in determining routes at the cost of lower performance on certain applications, but has been widely used because of its simpler hardware requirements.
(cont.) This thesis examines oblivious routing schemes for NoC architectures. It introduces various non-minimal, oblivious routing algorithms that globally allocate network bandwidth for a given application when estimated bandwidths for data transfers are provided, while ensuring deadlock freedom with no significant additional hardware. The work presents and evaluates these oblivious routing algorithms which attempt to minimize the maximum channel load (MCL) across all network links in an effort to maximize application throughput. Simulation results from popular synthetic benchmarks and concrete applications, such as an H.264 decoder, show that it is possible to achieve better performance than traditional deterministic and oblivious routing schemes.
by Michel A. Kinsy.
S.M.
Mastandrea, Vincenzo. "Deadlock analysis of asynchronous sequential processes." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2014. http://amslaurea.unibo.it/7451/.
Full textGrazia, Carlo Augusto. "Analisi statica dei Deadlock in Featherweight Java con Futuri." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2012. http://amslaurea.unibo.it/4473/.
Full textAshfield, Bruce. "Distributed deadlock detection in mobile agent systems." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2001. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/MQ57757.pdf.
Full textWilliams, Amy Lynne Ph D. Massachusetts Institute of Technology. "Static detection of deadlock for Java libraries." Thesis, Massachusetts Institute of Technology, 2005. http://hdl.handle.net/1721.1/87909.
Full textIncludes bibliographical references (p. 63-66).
Library writers wish to provide a guarantee not only that each procedure in the library performs correctly in isolation, but also that the procedures perform correctly when run in conjunction. To this end, we propose a method for static detection of deadlock in Java libraries. Our goal is to determine whether client code exists that may deadlock a library, and, if so, to enable the library writer to discover the calling patterns that can lead to deadlock. Our flow-sensitive, context-sensitive analysis determines possible deadlock configurations using a lock-order graph. This graph represents the order in which locks are acquired by the library. Cycles in the graph indicate deadlock possibilities, and our tool reports all such possibilities. We implemented our analysis and evaluated it on 18 libraries comprising 1245 kLOC. We verified 13 libraries to be free from deadlock, and found -14 distinct deadlocks in 3 libraries.
by Amy Lynne Williams.
S.M.
Lehman, Eric (Eric Allen) 1970. "Deadlock-free routing in a faulty hypercube." Thesis, Massachusetts Institute of Technology, 1998. http://hdl.handle.net/1721.1/47503.
Full textScherer, John-Patrick. "“Deadlock Provisions in Equity Joint Venture Agreements”." Master's thesis, University of Cape Town, 2018. http://hdl.handle.net/11427/29713.
Full textMeng, Wang. "Verifying Deadlock-Freedom for Advanced Interconnect Architectures." Thesis, Linköpings universitet, Institutionen för datavetenskap, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-171922.
Full textAshfield, Bruce Carleton University Dissertation Computer Science. "Distributed deadlock detection in mobile agent systems." Ottawa, 2000.
Find full textZhang, Wenle. "Scalable deadlock avoidance algorithms for flexible manufacturing systems." Ohio : Ohio University, 2000. http://www.ohiolink.edu/etd/view.cgi?ohiou1179862449.
Full textSimpson, D. P. "Deadlock free algorithmic parallelism : analysis, implementation and performance." Thesis, University of Southampton, 2003. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.274694.
Full textLee, Victor Wui-Keung. "An evaluation of Fugu's network deadlock avoidance solution." Thesis, Massachusetts Institute of Technology, 1996. http://hdl.handle.net/1721.1/39072.
Full textElmagarmid, Ahmed Khalifa. "Deadlock detection and resolution in distributed processing systems /." The Ohio State University, 1985. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487261919110166.
Full textKhan, Mahmood A. "A design environment for deadlock-free concurrent software." Thesis, Aston University, 1992. http://publications.aston.ac.uk/8099/.
Full textMohan, Sridhar. "Deadlock avoidance in mixed capacity flexible manufacturing systems." [Tampa, Fla.] : University of South Florida, 2004. http://purl.fcla.edu/fcla/etd/SFE0000428.
Full textDeorukhkar, Mayuresh. "Deadlock probability prediction and detection in distributed systems /." free to MU campus, to others for purchase, 2004. http://wwwlib.umi.com/cr/mo/fullcit?p1421130.
Full textHolsmark, Rickard. "Deadlock Free Routing inMesh Networks on Chip with Regions." Licentiate thesis, Department of Computer and Information Science, 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-20284.
Full textThere is a seemingly endless miniaturization of electronic components, which has enabled designers to build sophisticated computing structureson silicon chips. Consequently, electronic systems are continuously improving with new and more advanced functionalities. Design complexity ofthese Systems on Chip (SoC) is reduced by the use of pre-designed cores. However, several problems related to the interconnection of coresremain. Network on Chip (NoC) is a new SoC design paradigm, which targets the interconnect problems using classical network concepts. Still,SoC cores show large variance in size and functionality, whereas several NoC benefits relate to regularity and homogeneity.
This thesis studies some network aspects which are characteristic to NoC systems. One is the issue of area wastage in NoC due to cores of varioussizes. We elaborate on using oversized regions in regular mesh NoC and identify several new design possibilities. Adverse effects of regions oncommunication are outlined and evaluated by simulation.
Deadlock freedom is an important region issue, since it affects both the usability and performance of routing algorithms. The concept of faultyblocks, used in deadlock free fault-tolerant routing algorithms has similarities with rectangular regions. We have improved and adopted one suchalgorithm to provide deadlock free routing in NoC with regions. This work also offers a methodology for designing topology agnostic, deadlockfree, highly adaptive application specific routing algorithms. The methodology exploits information about communication among tasks of anapplication. This is used in the analysis of deadlock freedom, such that fewer deadlock preventing routing restrictions are required.
A comparative study of the two proposed routing algorithms shows that the application specific algorithm gives significantly higher performance.But, the fault-tolerant algorithm may be preferred for systems requiring support for general communication. Several extensions to our work areproposed, for example in areas such as core mapping and efficient routing algorithms. The region concept can be extended for supporting reuse ofa pre-designed NoC as a component in a larger hierarchical NoC.
Zhou, Jun. "Deadlock Analysis of Message-Passing Programs with Identical Processes." NCSU, 2001. http://www.lib.ncsu.edu/theses/available/etd-20010105-233920.
Full textDeadlocks are a common type of faults in message-passing programs. One approach to detecting deadlocks in a message-passing program is to perform reachability analysis, which involvesderiving possible global states of the program. The resulting state graph is referred to as a reachability graph (RG). The size of the RG of a message-passing program, in the worst case, is anexponential function of the number of processes in the program. This problem, referred to as the state explosion problem, makes reachability analysis impractical for message-passing programs withmany processes.
Assume that P is a message-passing program that contains one process type T with a dynamic number of instances. Let P_m denote the version of P that has m instances of T. To detect deadlocks inP, we apply reachability analysis to P_1, P_2, ..., and P_n, where n is an integer chosen randomly or according to some criterion. If the value of n is large, reachability analysis of P_n is impractical. Ifthe value of n is small, we have little confidence on whether P_k is deadlock-free for any k > n. A deadlock cutoff number c for P means that under certain conditions, if P_c has no deadlocks, then P_khas no deadlocks for any k > c. For message-passing programs that contain two or more process types with dynamic numbers of instances, their deadlock cutoff vectors are defined in a similar way.
In this dissertation we present four approaches to finding deadlock cutoff numbers for synchronous message-passing programs. These approaches are based on the use of observational equivalence,projection equivalence, client/server reachability graphs, and abstract client/server reachability graphs, respectively. The first three approaches assume that each process in a synchronousmessage-passing program is modeled as a labeled transition system (LTS). The fourth approach assumes that each process in a synchronous message-passing program is modeled as acommunicating finite state machine (CFSM) or extended CFSM.
Observational equivalence is an important concept in verifying properties of LTS systems. Let L be an instance of process type T in P. The environment of L in P_m, m>0, is defined to be thecomposition of processes in P_m excluding L. In other words, P_m is the composition of L and its environment in P_m. We show that if there exists an integer n such that the environments of L in P_nand P_{n+1} are observational equivalent and P_n has no global deadlocks, then P_k, k>n, has no global deadlocks and n is a deadlock cutoff number for P. We also show how to apply this approach toring-structured programs. One major problem with this approach is that it fails to find deadlock cutoff numbers for many message-passing programs.
To improve the above approach, we define a new equivalence relation called projection equivalence, which is weaker than observational equivalence. The projection of L in P_m, i>0, is defined to bethe behavior of L in P_m. The environments of L in P_i and P_j, i=\=j, are said to be projection equivalent if L has the same projection in P_i and P_j. We show how to apply projection equivalence tofind deadlock cutoff numbers for client/server programs and ring-structured programs. A client/server program contains a server and a number of clients. Clients call the server to request service;they do not communication with each other. The server cannot call individual clients. For client/server programs, we define a new type of reduced reachability graphs, called client/server reachabilitygraphs or CSRGs. The size of the CSRG of a client/server program is a polynomial function of the number of clients. Based on CSRGs, we show how to determine the existence of a deadlock cutoffnumber for a client/server program and how to find this number if it exists. We also show how to find deadlock cutoff vectors for client/server programs with two or more types of clients.
Finally, we consider client/server programs with two-way communication, which allows the server to call individual clients. Each client in such a program is represented as a communicating finitestate machine (CFSM), while the server is represented as an extended CFSM. For such programs, we define a new type of reduced reachability graphs, called abstract CSRGs or ACSRGs. Basedon ACSRGs, we show how to find deadlock cutoff numbers for client/server programs with two-way communication. Our empirical studies show that ACSRGs are much smaller than theircorresponding RGs. For example, for a solution to the gas station problem with one pump and six customers, its ACSRG has 74 states and its RG has 25394 states.
Martin, Jeremy Malcolm Randolph. "The design and construction of deadlock-free concurrent systems." Thesis, University of Buckingham, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.601333.
Full textKshemkalyani, Ajay D. "Characterization and correctness of distributed deadlock detection and resolution /." The Ohio State University, 1991. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487694702783488.
Full textSánchez, César. "Deadlock avoidance for distributed real-time and embedded systems /." May be available electronically:, 2007. http://proquest.umi.com/login?COPT=REJTPTU1MTUmSU5UPTAmVkVSPTI=&clientId=12498.
Full textCape, David Andrew. "Deadlock detection and dihomotopic reduction via progress shell decomposition." Diss., Rolla, Mo. : Missouri University of Science and Technology, 2010. http://scholarsmine.mst.edu/thesis/pdf/Cape_09007dcc8078d6bb.pdf.
Full textVita. The entire thesis text is included in file. Title from title screen of thesis/dissertation PDF file (viewed April 21, 2010) Includes bibliographical references (p. 133-134).
Chua, Kee Koon 1965. "Deadlock avoidance: Improved algorithms for centralized and distributed systems." Thesis, The University of Arizona, 1992. http://hdl.handle.net/10150/291335.
Full textLÔBO, Rafael Brandão. "Deadlocks as runtime exceptions." Universidades Federais de Pernambuco, 2015. https://repositorio.ufpe.br/handle/123456789/17332.
Full textMade available in DSpace on 2016-07-12T12:30:10Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) DISSERTAÇÃO (2015-08-17) - RAFAEL BRANDAO LOBO.pdf: 1015468 bytes, checksum: d543b6f16adc4ce4d3aa4d59c8d546ff (MD5) Previous issue date: 2015-07-17
CAPEs
Deadlocks are a common type of concurrency bug. When a deadlock occurs, it is difficult to clearly determine whether there is an actual deadlock or if the application is slow or hanging due to a different reason. It is also difficult to establish the cause of the deadlock. In general, developers deal with deadlocks by using analysis tools, introducing application-specific deadlock detection mechanisms, or simply by using techniques to avoid the occurrence of deadlocks by construction. In this paper we propose a different approach. We believe that if deadlocks manifest at runtime, as exceptions, programmers will be able to identify these deadlocks in an accurate and timely manner. We leverage two insights to make this practical: (i) most deadlocks occurring in real systems involve only two threads acquiring two locks (TTTL deadlocks); and (ii) it’s possible to detect TTTL deadlocks efficiently enough for most practical systems. We conducted a study on bug reports and found that more than 90% of identified deadlocks were indeed TTTL.We extended Java’s ReentrantLock class to detect TTTL deadlocks and measured the performance overhead of this approach with a conservative benchmark. For applications whose execution time is not dominated by locking, the overhead is estimated as below 6%. Empirical usability evaluation in two experiments showed that students finished tasks 16.87% to 30.7% faster on the average using our approach with the lock being the most significant factor behind it, and, in one of the experiments they were able to identify the defects more accurately with a signficant 81.25% increase in the number of correct answers when deadlock exceptions where present.
Deadlocks são um tipo comum de bug de concorrência. Quando um deadlock acontece, é difícil determinar claramente se houve um deadlock de verdade ou se a aplicação está lenta ou travada por qualquer outro motivo. Também é difícil estabelecer a causa do deadlock. Em geral, desenvolvedores lidam com deadlocks de várias maneiras: utilizando ferramentas analíticas; utilizando mecanismos especificos da aplicação para detectar deadlocks; ou simplesmente usando técnicas para evitar a ocorrência de deadlocks no momento da construção do código. Neste trabalho, propomos uma abordagem diferente. Acreditamos que se deadlocks se manifestarem durante a execução na forma de exceções, programadores serão capazes de identificar esses deadlocks de forma mais precisa e mais rápida. Levamos em consideração alguns aspectos para tornar esta abordagem prática: (i) a maioria dos deadlocks que ocorrem em sistemas reais envolvem apenas duas threads adquirindo dois locks ou two-thread, two-lock (TTTL) deadlock; e (ii) é possível detectar TTTL deadlocks de forma suficientemente eficiente para uso prático na maioria dos sistemas. Conduzimos um estudo com bugs reportados em sistemas de software de larga escala e descobrimos que mais de 90% dos bugs identificados como deadlocks eram de fato TTTL. Extendemos a classe ReentrantLock de Java para detectar TTTL deadlocks e medimos seu overhead na performance com um benchmark bastante conservador onde medimos o overhead das operações de trava quando deadlocks não são possíveis. Para aplicações cujo tempo de execução não é dominado por travas, o impacto médio no tempo de execução é na ordem de 6%. Realizamos uma avaliação empírica para testar usabilidade através de dois experimentos. Nesta avaliação, mostramos que, em média, estudantes terminam tarefas de 16.87% a 30.7% mais rapidamente usando nossa abordagem, sendo o tipo de abordagem o fator de maior significância e, em um dos experimentos, estudantes foram capazes de identificar mais corretamente a causa dos bugs, mostrando que o número de respostas corretas aumentou significativamente em 81.25% quando as exceções propostas estavam presentes.
Bernini, Simone. "Analisi e gestione del protocol deadlock nelle network-on-chip." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2010. http://amslaurea.unibo.it/1245/.
Full textDeering, Paul E. "Necessary and sufficient conditions for deadlock in a manufacturing system." Ohio : Ohio University, 2000. http://www.ohiolink.edu/etd/view.cgi?ohiou1179169384.
Full textLandrum, Chad Michael. "A recursive algorithm to prevent deadlock in flexible manufacturing systems." Ohio : Ohio University, 2000. http://www.ohiolink.edu/etd/view.cgi?ohiou1172265184.
Full textFaiz, Tariq Nadeem. "Deadlock detection and avoidance for a class of manufacturing systems." Ohio : Ohio University, 1996. http://www.ohiolink.edu/etd/view.cgi?ohiou1178654511.
Full textWatt, Emir Patrick James. "Managing deadlock : organisational development in the British First Army, 1915." Thesis, University of Edinburgh, 2018. http://hdl.handle.net/1842/31530.
Full textKachru, Rajiv Carleton University Dissertation Computer Science. "Performance of some deadlock prevention routing algorithms for multicomputer systems." Ottawa, 1992.
Find full textHolsmark, Rickard. "Deadlock Free Routing in Mesh Networks on Chip with Regions." Licentiate thesis, Linköping : Department of Compuuter and Information Science, Linköpings universitet, 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-20284.
Full textElMekkawy, Tarek Younis. "Deadlock resolution in flexible manufacturing systems, a Petri nets based approach." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2001. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp05/NQ62315.pdf.
Full textLee, Jaehwan. "Hardware/Software Deadlock Avoidance for Multiprocessor Multiresource System-on-a-Chip." Diss., Also available online, Georgia Institute of Technology, 2004:, 2004. http://etd.gatech.edu/theses/available/etd-11222004-083429/unrestricted/lee%5Fjaehwan%5F200412%5Fphd.pdf.
Full textBodner, Douglas Anthony. "Real-time control approaches to deadlock management in automated manufacturing systems." Diss., Georgia Institute of Technology, 1996. http://hdl.handle.net/1853/25607.
Full text劉少華 and Siu-wah Lau. "A novel approach to deadlock prevention in store-and-forward networks." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 1991. http://hub.hku.hk/bib/B31209798.
Full textCai, Wentong. "Parallel program monitoring : the logical clock approach and its deadlock avoidance." Thesis, University of Exeter, 1990. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.279753.
Full textSilva, Luciane de Fátima. "Detecção e correção de situações de deadlock em workflow nets interorganizacionais." Universidade Federal de Uberlândia, 2014. https://repositorio.ufu.br/handle/123456789/12555.
Full textNeste trabalho e proposta uma abordagem baseada na prevenção de deadlocks em WorkFlow nets Interorganizacionais para lidar com situações dessa natureza. Processos de negocio interorganizacionais são modelados por work ows interorganizacionais. Situações de deadlock nos processos de negocio interorganizacionais geralmente estão relacionadas a perdas durante trocas de mensagens entre varios processos de negocio. Dentro da teoria das redes de Petri, uma situação de deadlock e caracterizada pela presenca de um sifão que pode car vazio. Depois de detectar e controlar as estruturas de sifão que levam as situações de deadlock nas WorkFlow nets Interorganizacionais, e proposta uma arquitetura distribuda para modelar as WorkFlow nets Interorganizacionais livre de deadlock. Em particular, o princpio basico consiste em denir novas WorkFlow nets compartilhadas entre os work ows originais que permitem remover os cenarios responsaveis pelos deadlocks.
Mestre em Ciência da Computação
Lau, Siu-wah. "A novel approach to deadlock prevention in store-and-forward networks /." [Hong Kong : University of Hong Kong], 1991. http://sunzi.lib.hku.hk/hkuto/record.jsp?B13005625.
Full textBirkinshaw, Carl Ian. "Engineering communicative distributed safety-critical systems." Thesis, University of Sheffield, 1995. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.263801.
Full textYamamoto, Yuji, R. C. Schmidt, Hiroo Suzuki, Motoki Okumura, Keiko Yokoyama, Koji Kadota, and Akifumi Kijima. "Switching Dynamics in an Interpersonal Competition Brings about “Deadlock” Synchronization of Players." PLOS ONE, 2012. http://hdl.handle.net/2237/17183.
Full textCôté, Claire. "Pseudosimulation in distributed simulations : a deadlock prevention algorithm with fixed memory requirements." Thesis, McGill University, 1991. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=59962.
Full textMartorelli, HernaÌndez MariÌa Paola de San NicolaÌs. "Beyond deadlock? : legislative co-operation in the Latin American presidential/PR systems." Thesis, University of Essex, 2007. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.442517.
Full textANTONINO, Pedro Ribeiro Gonçalves. "A refinement based strategy for locally verifying networks of CSP processes." Universidade Federal de Pernambuco, 2014. https://repositorio.ufpe.br/handle/123456789/11966.
Full textSubmitted by Luiz Felipe Barbosa (luiz.fbabreu2@ufpe.br) on 2015-03-10T16:54:41Z No. of bitstreams: 2 DISSERTAÇÃO Pedro Ribeiro Gonçalves Antônio.pdf: 921372 bytes, checksum: 64def1c3ae98cbca7868d944c1f786f2 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5)
Made available in DSpace on 2015-03-11T17:34:41Z (GMT). No. of bitstreams: 2 DISSERTAÇÃO Pedro Ribeiro Gonçalves Antônio.pdf: 921372 bytes, checksum: 64def1c3ae98cbca7868d944c1f786f2 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2014-03-31
Com o aumento da complexidade dos sistemas computacionais, houve também um aumento da dificuldade na tarefa de verificação de sistemas. Para lidar com essa complexidade, métodos formais podem ser usados no desenvolvimento de sistemas, fornecendo técnicas para a modelagem e verificação. No contexto de sistemas concorrentes e distribuídos, a necessidade de uma abordagem formal é ainda mais proeminente, dadas as inúmeras possibilidades de interação entre seus sistemas componentes. Entretanto, infelizmente, os métodos atuais não se encontram, de forma geral, completamente aptos a lidar com a análise automática desses sistemas, mesmo em se tratando de propriedades clássicas como a ausência de deadlocks. A explosão do espaço de estados a ser analisado é o principal fator para essa ineficácia por parte desses sistemas. O trabalho apresentado é uma contribuição nesta direção. Considerando o conceito de redes de processos CSP, o presente trabalho propõe uma estratégia local para a análise de deadlocks baseada na noção de refinamento de processos. A localidade dessa estratégia previne a explosão de espaço de estados causada pela interação de sistemas componentes, o que constitui uma vantajosa característica da nossa estratégia. O trabalho define uma expressão de refinamento capturando o conceito de ausência de conflito, que pode ser usado para verificar localmente que uma rede de processos com uma topologia de comunicação acíclica é livre de deadlocks. Para as redes com topologia cíclica, o trabalho sistematiza e formaliza três padrões comportamentais que impedem deadlocks: o alocação de recursos, o cliente/servidor e o assíncrono dinâmico. Esses padrões impõem restrições comportamentais e estruturais para prevenir deadlocks. Essas restrições comportamentais também são capturadas através de expressões de refinamento, o que possibilita a verificação automática dessas condições com o uso de um verificador de refinamento. Além disso, são apresentados quatro estudos de caso usados para avaliar o desempenho da nossa técnica na prática: um buffer circular, um jantar dos filósofos e duas variações de um algoritmo para eleição de líder. Uma dessas variações consiste num modelo usado na prática pela empresa B&O, um parceiro industrial. Nesse estudo, avaliamos a nossa técnica em comparação com outras duas técnicas para verificação de ausência de deadlocks, o algoritmo SSD da ferramenta Deadlock Checker e a asserção de verificação de deadlocks padrão do verificador de modelos FDR. Esse estudo demonstra como a nossa estratégia é aplicada e que ela pode ser uma alternativa vantajosa para a verificação de sistemas complexos.
Nguyen, Tuong M. "On exploring even reachable global state space to verify deadlock freedom of protocols." Thesis, University of Ottawa (Canada), 2002. http://hdl.handle.net/10393/6424.
Full textKhonsari, Ahmad. "Performance modelling and analysis of deadlock recovery routing algorithms in multicomputer interconnection networks." Thesis, University of Glasgow, 2003. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.398647.
Full textParreira, Daniel Luis Landeiroto. "Data-centric concurrency control on the java programming language." Master's thesis, Faculdade de Ciências e Tecnologia, 2013. http://hdl.handle.net/10362/10814.
Full textThe multi-core paradigm has propelled shared-memory concurrent programming to an important role in software development. Its use is however limited by the constructs that provide a layer of abstraction for synchronizing access to shared resources. Reasoning with these constructs is not trivial due to their concurrent nature. Data-races and deadlocks occur in concurrent programs, encumbering the programmer and further reducing his productivity. Even though the constructs should be as unobtrusive and intuitive as possible, performance must also be kept high compared to legacy lock-based mechanism. Failure to guarantee similar performance will hinder a system from adoption. Recent research attempts to address these issues. However, the current state of the art in concurrency control mechanisms is mostly code-centric and not intuitive. Its codecentric nature requires the specification of the zones in the code that require synchronization,contributing to the decentralization of concurrency bugs and error-proneness of the programmer. On the other hand, the only data-centric approach, AJ [VTD06], exposes excessive detail to the programmer and fails to provide complete deadlock-freedom. Given this state of the art, our proposal intends to provide the programmer a set of unobtrusive data-centric constructs. These will guarantee desirable security properties: composability, atomicity, and deadlock-freedom in all scenarios. For that purpose, a lower level mechanism (ResourceGroups) will be used. The model proposed resides on the known concept of atomic variables, the basis for our concurrency control mechanism. To infer the efficiency of our work, it is compared to Java synchronized blocks, transactional memory and AJ, where our system demonstrates a competitive performance and an equivalent level of expressivity.
RepComp project(PTDC/EIA-EIA/108963/2008)
Castillo, Ernesto Cristopher Villegas. "DyAFNoC: sistema dinamicamente reconfigurável baseado em redes intrachip com algoritmo de roteamento ordenado por dimensão flexibilizado." Universidade de São Paulo, 2014. http://www.teses.usp.br/teses/disponiveis/3/3140/tde-31122015-101031/.
Full textThe increased capacity of Systems on-Chip (SoCs) has led Networks on-Chip (NoC) to be used as communication interface for processing modules of complex systems, and particularly in Dynamically Recongurable Systems to be implemented over partially recongurable FPGAs. Some reconguration strategies work on irregular and indirect NoCs, fact that forces the system to update its routing algorithm in order to avoid data communication problems, such as deadlockandlivelock. ThispaperpresentsaDynamicallyRecongurableNoC(DRNoC)using Flexible Dimension Order Routing Algorithm (FDOR), mainly characterized by its simplicity, low complexity and deadlock freedom In this work, the DyAFNoC tool was implemented, to generate the VHDL code of the associated NoC architecture to be used with specic applications with dynamic partial reconguration that require parallel communications between their processing modules. This tool generates routers, processing modules, and also a Partial Dynamic Reconguration Control System that can be used with the FDOR-based Reconguration System, developed elsewhere. The tool also generates testbench components for the system simulation, based on the Dynamic Circuit Switching technique that uses isolation switches to emulate the dynamic partial reconguration processes. The results of these experiments have helped to determine the desired system behavior. Simulations of the FDOR implementation were also made in high level descriptioninordertodetermineitsdatatransferperformancethatwillhelptodeneplacement of the processing modules over the network structure. The experiments results have demonstrated the feasibility of this strategy, leading to the conclusion that the FDOR algorithm is a suitable solution for DRNoC.