ارزیابی الگوریتم‌های کنترل همروندی WW و WD برای مدیریت پایگاه داده‌ها، از طریق مدل‌سازی با پتری رنگی

نوع مقاله : پژوهشی

نویسندگان

1 دانشگاه علم و هنر

2 دانشگاه کاشان

چکیده

اجرای همروند تراکنش‎ها در پایگاه داده، ممکن است منجر به ناسازگاری شود. ناسازگاری بر اثر مقادیر نادرستی است که برای داده‎ها، به دلیل تداخل اجرای تراکنش‌ها بوجود می‎آید. الگوریتم‌های کنترل همروندی، جهت تضمین اجرای همروند چندین تراکنش که بصورت همروند با داده‎های مشترک کار می‎کنند طراحی شده‎اند. در این مقاله الگوریتم‌های کنترل همروندی منتظر گذاشتن-میراندن (WD) و زخمی کردن-منتظر گذاشتن (WW) که جزء تکنیک‌های پیشگیری از بن‌بست هستند مدل‌سازی گردیده‌اند. از آنجا که شبکه پتری رنگی یکی از بهترین روش‌ها برای تحلیل مکانیزم‌های کنترل همروندی است؛ مدل‌سازی‌ها با استفاده از پتری رنگی ارائه شده‌اند. پس از مدل‌سازی به ارزیابی الگوریتم‌ها بر اساس پارامترهای تعداد تراکنش‌های وارد شونده به سیستم، تعداد دستورات هر تراکنش، تعداد داده‌های مشترک و غیر مشترک بین تراکنش‌ها و تعداد داده‌های مشترک در تراکنش‌هایی که هیچ داده غیر مشترکی ندارند؛ پرداخته شده است. پس از ارزیابی، این نتیجه بدست آمد که بر اساس پارامترهای ذکر شده، الگوریتم WW نسبت به WD زمان اجرای بسیار بهتری دارد.

کلیدواژه‌ها

عنوان مقاله [English]

Performance Evaluation of WW and WD Concurrency Control Algorithms for Database Management, via Modeling by Colored Petri Net

نویسندگان [English]

  • Fatemeh Saadatjoo 1
  • Mohammad Ali Saadatjoo 2
1
2
چکیده [English]

Any concurrent transaction should be taken in database could lead to conflict. The conflict occurs due to incorrect values for the data which lead to interference in executed transaction which has been taken. The concurrency control algorithms, to insure the concurrent action many transactions has been designed to work concurrently with a common data. In this paper, Wound-Wait and Wait-Die concurrency control algorithms which are the part of preventing Deadlock techniques, has been modeled. Since the Colored Petri Net is one of the best methods in analyzing the concurrency control mechanism, modeling are shown using Colored Petri. Ater modeling the evaluation is carried out using parameters such as the number of transactions entering the system, the number of commands, and the number of relevant and irrelevant data between transactions, and the number of relevant data in transactions without irrelevant data, has been taken place. After evaluation, according to mentioned parameters, this result has been obtained, that Wound-Wait algorithm has much better time performance in comparison with the Wait-Die algorithm.

کلیدواژه‌ها [English]

  • Concurrency control
  • Colored Petri Net
  • Wait-Die
  • Wound-Wait
  • Evaluation
  • Preventing deadlock

مراجع

 
[1] Pashazadeh, S. (2012). “Modeling and verification of deadlock potentials of a concurrency control mechanism in distributed databases using hierarchical colored petri net”. International Journal of Information and Education Technology (IJIET), Vol. 2, No. 2, pp. 77-82.
[2] Pashazadeh, S. (2012). “Modeling a concurrency control Mechanism in distributed databases using hierarchical colored petri net”. International Conference on Information and Computer Applications (ICICA), Singapore, Vol. 24, pp.286-289.
[3] Shu, L. C., Young, M. (2002). “Versioning concurrency control for hard real-time systems”. Journal of Systems and Software, Vol. 63, No. 3, pp. 201-218.
[4] Hedayati, M., Kamali, S. H., Shakerian, R., Rahmani, M. (2010). “Evaluation of performance concurrency control algorithm for secure firm real-time database systems via simulation model”. Networking and Information Technology (ICNIT), International Conference on IEEE, pp. 260-264.
[5] Singhal, M. (1991). “Performance analysis of the basic timestamp ordering algorithm via Markov modeling—performance evaluation”. Performance Evaluation, Vol. 12, No. 1, pp. 17-41.
[6] Al-Jumah, N. B., Hossam, S. H., El-Sharkawi, M. (2000). “Implementation and modeling of two-phase locking concurrency control—a performance study”. Information and Software Technology, Vol. 42, No. 4, pp. 257-273.
[7] Ozsu, M. T. (1985). “Modeling and analysis of distributed database concurrency control algorithms using an extended petri net formalism, Software Engineering”. Transactions on IEEE, Vol. SE-11, No. 10, pp. 1225-1240.
[8] Mikkilineni, K. P., Chow, Y. C., Su, S. Y. W. (1988). “Petri-net-based modeling and evaluation of pipelined processing of concurrent database queries”. Software Engineering, Transactions on IEEE, Vol. 14, No. 11.
[9] Han, Y., Jiang, C., Luo, X. (2004). “A study of concurrency control in web-based distributed real-time database system using extended time petri nets, Parallel Architectures”. Algorithms and Networks (ISPAN’04), in Proceedings of the 7th International Symposium on IEEE, pp. 67-72.
[10] Murata, T. (1989). “Petri nets: properties, analysis and applications”. in Proceedings of  IEEE, Vol. 77, No. 4, pp. 541-580.
[11] Devillers, R., Best, E. (1987). “Sequential and concurrent bihavior in petri net theory, Theorical computer science”. Vol. 55, No. 1, pp. 87-136.
[12] Seatzu, C., Cabasino, M. P., Giua, A. (2013). “Introduction to petri nets”. Control of Discrete-Event Systems (LNCIS), Vol. 433, pp. 191–211.
[13] Zhen, C., Li, K. (2009). “Improved distributed concurrency control algorithm based on real-time database systems”. Computational Intelligence and Software Engineering, (CiSE), International Conference on IEEE, pp. 1-3.
[14] Lee, J. (1999). “Precise serialization for optimistic concurrency control”. Data & Knowledge Engineering, Vol. 29, No. 2, pp. 163-178.
[15] Mousavi, S. M. A., Naji, H. R., Ebrahimi, A. R. (2013). “Optimization of majority protocol for controlling transactions concurrency in distributed databases by multi-agent systems”. International Journal of Applied Operational Research, Vol. 3, No. 1, pp. 95-108.
[16] Chen, J., Wang, Y. F., Wang, J. P. (2011). “Concurrency control protocol for real-time database and the analysis base on petri net”. Advanced Materials Research, Vols. 143-144, pp. 12-17.
[17] Sarkar, B. B., Nabendu, C. (2009). “Modeling & analysis of transaction management for distributed database environment using Petri Nets”. In Nature & Biologically Inspired Computing (NaBIC), World Congress on IEEE, pp. 918-923.
[18] Jie, H., Fengying, L., Huijiao, W. (2010). “Petri net based model for concurrent control of database system”. International Conference on Intelligent Computing and Integrated Systems (ICISS), pp. 813-815.
[19] Jenq, B-C., Twichell, B. C., Keller, T. W. (1989). “Locking performance in a shared nothing parallel database machine”. Knowledge and Data Engineering, Transactions on IEEE, Vol. 1, No. 4, pp. 530-543.
[20] Voss, K. (1997). “Prototyping and verifying distributed database systems using executable high-level Petri net models, Systems”. Man, and Cybernetics,. Computational Cybernetics and Simulation., International Conference on IEEE, Vol. 4, pp. 3395-3400.
[21] Paulson, L. C. (1996). “ML for the working programmer”. (2th ed.), NY. USA, Press Cyndicate of the University of Cambridge.
[22] Harper, R. (2001). “Programming in standard ML, Pittsburgh United States”. Carnegie Mellon University.
 
مدل سازی در مهندسی
دوره 15، شماره 51
دی 1396
صفحه 99-111

فایل ها

سابقه مقاله

  • تاریخ دریافت: 08 مرداد 1394
  • تاریخ بازنگری: 08 بهمن 1394
  • تاریخ پذیرش: 29 فروردین 1395

هم رسانی

ارجاع به این مقاله

آمار