Please use this identifier to cite or link to this item: http://cuir.car.chula.ac.th/handle/123456789/44465
Title: A DEVELOPMENT OF THE DEADLOCK DETECTION ALGORITHM FOR IDENTIFYING POTENTIAL DEADLOCKS
Other Titles: การพัฒนาอัลกอริทึมที่ใช้ในการตรวจจับการติดตายสำหรับการระบุการติดตายที่มีแนวโน้มที่จะเกิดขึ้น
Authors: Suvarin Ploysri
Advisors: Wanchai Rivepiboon
Other author: Chulalongkorn University. Faculty of Engineering
Advisor's Email: Wanchai.R@Chula.ac.th,wanchai.r@chula.ac.th
Subjects: Java (Computer program language)
Algorithms
Computer software -- Development
Application program interfaces (Computer software)
จาวา (ภาษาคอมพิวเตอร์)
อัลกอริทึม
ซอฟต์แวร์ -- การพัฒนา
Issue Date: 2014
Publisher: Chulalongkorn University
Abstract: Currently, developing a multithreading Application Programming Interface (API) for special use is extensive. Deadlock in the multithreading API is the most concerned problem because we cannot find the deadlock in the application and the cost for defect fixing later on the development phase is even higher and more complex. Detecting deadlock in early phase of the Software Development Life Cycle or using static analysis is the way more effective. Since we still do not know how developer uses the API, detecting deadlock in the source code using static analysis is our selection for this research. We have successfully developed the Deadlock Detection Algorithm that brings the concept of five deadlock conditions by Mayur Naik published in 2009 and two code patterns by Frank Otto published in 2008. We present seven deadlock conditions that are the Aliasing Condition, the Reverse Order Locking Condition or the Cyclic Lock Dependency Condition, the Escaping Condition, the Parallel Condition, the Non-Guarded Lock Condition and the Superfluous Lock Condition. In addition, we develop the prototype of the Deadlock Detection Tool to demonstrate the use of the Deadlock Detection Algorithm. The result of the implementation of the Deadlock Detection Algorithm and the Deadlock Detection Tool are satisfied and provide correct result as expected.
Other Abstract: ในปัจจุบันการพัฒนาอินเตอร์เฟสของชุดคำสั่งของโปรแกรมประยุกต์แบบมัลติเธรด(เอพีไอ) เพื่อการใช้งานเฉพาะอย่างนั้น มีการพัฒนาอย่างกว้างขวางมาก อย่างไรก็ตามปัญหาที่เกิดจากเอพีไอแบบมัลติเธรดนั้นก็ได้เกิดขึ้นมาด้วย นั่นก็คือการติดตาย การติดตายในเอพีไอแบบมัลติเธรดเป็นสิ่งที่น่ากังวลมากที่สุดเพราะว่า เราไม่สามารถค้นหาการติดตายในโปรแกรมประยุกต์และค่าใช้จ่ายสำหรับการแก้ไขข้อบกพร่องภายหลังเฟสการพัฒนาจะสูงมากขึ้นและปัญหามีความซับซ้อนมากขึ้น การตรวจจับการติดตายในเอพีไอแบบมัลติเธรดในเฟสต้นของวงจรการพัฒนาซอฟต์แวร์หรือการใช้การวิเคราะห์แบบสถิตย์คงเป็นวิธีที่มีประสิทธิภาพมากกว่าวิธีอื่น เนื่องจากเรายังไม่ทราบว่าผู้เขียนโปรแกรมจะนำเอาเอพีไอแบบมัลติเธรดไปใช้อย่างไร การตรวจจับทุกๆ ส่วนของชุดคำสั่งจึงถูกนำมาใช้ในงานวิจัยฉบับนี้ เราประสบความสำเร็จในการพัฒนาอัลกอริทึมที่ใช้ในการตรวจจับการติดตาย โดยนำแนวคิด ของมายูร์ เนก ซึ่งกล่าวไว้ในปี 2009 ว่า เงื่อนไขของการเกิดการติดตายนั้นมี 5 ประเภทและ แนวคิดของแฟรงก์ อ็อตโต ซึ่งกล่าวไว้ในปี 2008 ว่า รูปแบบของรหัสคำสั่งนั้นมี 2 ประเภท ในงานวิจัยชิ้นนี้ได้เสนอ 7 เงื่อนไขของการเกิดการติดตาย ซึ่งได้แก่ เงื่อนไขสมนาม เงื่อนไขการล็อคด้วยลำดับผันกลับหรือเงื่อนไขล็อคพึ่งพาแบบวงกลม เงื่อนไขหลบหนี เงื่อนไขแบบขนาน เงื่อนไขไม่มีล็อคป้องกัน และเงื่อนไขล็อคฟุ่มเฟือย มาใช้ในการพัฒนาอัลกอรึทึมที่ใช้ในการตรวจจับการติดตาย และนอกจากนี้แล้ว เราได้มีการพัฒนาเครื่องมือต้นแบบที่ใช้ในการการตรวจจับการติดตายเพื่อแสดงให้เห็นถึงการใช้งานอัลกอริทึมที่ใช้ในการตรวจจับการติดตาย ผลของการพัฒนาอัลกอริทึมที่ใช้ในการตรวจจับการติดตายและเครื่องมือที่ใช้ในการตรวจจับการติดตายนั้น ให้ผลเป็นที่น่าพอใจ และ ถูกต้องตามที่คาดไว้
Description: Thesis (M.Sc.)--Chulalongkorn University, 2014
Degree Name: Master of Science
Degree Level: Master's Degree
Degree Discipline: Software Engineering
URI: http://cuir.car.chula.ac.th/handle/123456789/44465
Type: Thesis
Appears in Collections:Eng - Theses

Files in This Item:
File Description SizeFormat 
5471023921.pdf5.49 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.