کنترل همروندی

در فناوری اطلاعات و علوم رایانه‌ای، به‌خصوص در شاخه‌های برنامه‌نویسی رایانه‌ای، سیستم عامل، چندپردازشی، و پایگاه‌داده‌ها، کنترل همروندی (به انگلیسی: Concurrency Control)، از نتایج تولید شده ناشی از عملیات هم‌زمان اطمینان حاصل کرده، درحالی که سعی می کند در سریع ترین زمان ممکن به نتایج برسد.

سیستم‌های رایانه‌ای، چه نرم‌افزاری و چه سخت‌افزاری، شامل ماژول‌ها یا مؤلفه‌هایی اند. هر مؤلفه به گونه‌ای طراحی شده که به طرز صحیحی عمل کند، یعنی، از قوانین سازگاری بخصوصی تبعیت نموده، یا با آن ها تطابق داشته باشند. هنگامی که مؤلفه‌های هم‌روند با یکدیگر به وسیله پیام‌دهی یا اشتراک‌گذاری داده‌های دسترسی شده برهمکنش کنند (در حافظه یا محل ذخیره‌سازی)، هم‌روندی برخی از مؤلفه‌ها ممکن است توسط مؤلفه‌های دیگری مورد تجاوز و تخطی قرار گیرد. به طور کلی، مبحث هم‌روندی به ارائه قواعد، روش‌ها، روش‌شناسی‌های طراحی و نظریاتی می پردازد که به حفظ سازگاری مؤلفه‌های هم‌روندی، طی اجرای عملیاتشان کمک کند؛ بدین طریق سازگاری و صحت کل سیستم حفظ خواهد شد. معرفی کنترل هم‌روندی به یک سامانه، به معنای اعمال محدودیت‌های عملیاتیست که اغلب منجر به کاهش یافتن برخی از کارایی‌های سامانه می گردد. دستیابی به سازگاری عملیاتی و صحت باید تا حد امکان همراه با بهره‌وری باشد، به گونه‌ای که کارایی از حد معقول خاصی کمتر نشود. ممکن است کنترل همروندی در مقایسه با الگوریتم‌های سری (Sequential Algorithms) (که ساده‌ترند) نیازمند افزودن به پیچیدگی و سربار در قالب یک الگوریتم همروندی باشد.

به عنوان مثال، شکست در کنترل هم‌روندی، ممکن است منجر به خراب‌شدن داده‌ها شود، که ناشی از گسست عملیات خواندن یا نوشتن است.

کنترل همروندی خوشبینانه

کنترل همروندی خوشبینانه از سه مرحله تشکیل شده‌است.

۱. خواندن

فرض کنید که فردی در خانه نشسته است و می‌خواهد یک صفحه از ویکی‌پدیا را ویرایش کند. فرد مزبور ابتدا بر دکمه ویرایش می‌فشارد و تغییرات مورد نظر خود را انجام می‌دهد. این تغییرات در کاشه رایانه قرار دارد. سپس با فشردن دکمه «ذخیره شود» متن ویرایش به سرور ویکی‌پدیا فرستاده می‌شود.

۲. تأیید

در سرور نرم‌افزار مدیاویکی بررسی می‌کند که آیا ویرایش شما با ویرایش دیگران درگیری دارد یا نه. اگر درگیری وجود داشت الگوریتمی مورد استفاده قرار می‌گیرد تا درگیری را برطرف سازد. یک راه برای رفع درگیری این است که ویرایش نخست در پایگاه داده ذخیره شود و ویرایش‌های درگیر دیگر با فرستادن پیامی برای کاربران موردنظر نادیده انگاشته شود. راه دیگر این است که آن بخش‌هایی از ویرایش کاربران دیگر که درگیری ندارند نیز ذخیره شوند.

۳. نوشتن

اگر درگیری وجود نداشت تراکنش انجام می‌شود.

نمونه این نوع کنترل نرم‌افزار مدیاویکی است. الگوریتم کنترل آن در این‌جا توصیف شده‌است. نمونه دیگر باگزیلا است (این‌جا).

کنترل همروندی بدبینانه

در این روش به وسیله قفل گذاری جلوی هرگونه همروندی گرفته می‌شود. تا زمانیکه یک دستور در حال اجراست جلوی اجرای دستورهایی که ممکن است مانع اجرای صحیح دستور نخست شوند گرفته می‌شود.

پروتوکل‌ها

۱. قفل‌گذاری

قفل‌گذاری روش بدبینانه کنترل همروندی است. بقیه روش‌ها خوشبینانه هستند. قفل امتیاز دستیابی به یک واحد داده است که توسط سیستم قفل گذاری به یک تراکنش داده می‌شود یا از او پس گرفته می‌شود.

مدیر قفل ممکن است قفل‌ها را به‌طور پویا یا ایستا در اختیار تراکنش‌ها قرار دهد. در حالت پویا، مدیر قفل، پیرو درخواست تراکنش اقدام می‌کند. این روش قفل‌گذاری پویا موسوم است. در حالت قفل‌گذاری ایستا، تمام قفل‌های لازم برای اجرای یک تراکنش، پیش از اجرا، درخواست می‌شود و لازمه این روش این است که مجموعه قفل‌های مورد نیاز تراکنش، از قبل شناخته شده باشند.

روش‌های قفل‌گذاری

قفل انحصاری Exclusive Lock اگر تراکنش T قفل انحصاری را بر روی یک Object قرار دهد هیچ‌کدام از تراکنش‌های دیگرمانند t’ نمی‌توانند هیچ قفلی را بر روی آن قرار دهند تا زمانی که Tقفلش را آزاد کند.

قفل اشتراکی Shared Lock اگر تراکنشT قفل اشتراکی بر روی Objectقرار دهد آن وقت تراکنش‌های دیگر مانند

۲. برچسب زمانی

۳. تعیین اعتبار

۴. دانه‌بندی چندگانه

اجازه می‌دهد که عناصر داده اندازه‌های متفاوت داشته باشند و یک سلسله مراتب از دانه بندی داده‌ها را تعریف می‌کند، که در ان عناصر کوچکتر در عناصر بزرگتر قرار گرفته‌اند. می‌تواند از نظر گرافیکی مانند یک درخت نشان داده شود. هنگامی که یک تراکنش یک نود را به صورت صریح قفل می‌کند، تمام نودهای زیر آن را به صورت ضمنی قفل کرده‌است.

علاوه بر قفل انحصاری و اشتراکی سه نوع قفل دیگر هم در دانه بندی چند گانه وچود دارند .( Intention-shared(IS. نشان می‌دهد که در سطوح پایین‌تر قفل اشتراکی به صورت صریح انجام شده‌است. Intention-exclusive. نشان می‌دهد که در سطوح پایین‌تر قفل اشتراکی یا انحصاری به صورت صریح انجام شده‌است. Shared and Intention exclusive. زیردرخت با ریشه نود به صورت صریح در مد اشتراکی قفل شده‌است وقفل صریح در سطوح پایین‌تر در مد صریح رخ داده است. قفل‌های intention به نود اجازه می‌دهند که در مد انحصاری یا اشتراکی بدون نیاز به چک تمام زیر درخت زیر آن قفل شوند.

۵. نسخه‌سازی

مسئله بن‌بست

کابردها

کنترل همروندی در پایگاه‌های داده

کنترل همروندی در سیستم‌های عامل

در سیستم‌های عامل معمولاً چند وظیفه همزمان انجام می‌شوند. اگر این وظایف مستقل از هم باشند اجرای آن‌ها ساده است اما درصورتی‌که درگیر باشند، مثلاً نوشتن همروند بر روی یک فایل، در این صورت برای انجام درست وظایف نیاز به کنترل همروندی است وگرنه ممکن است منجر به نتایج ناخواسته شوند.

پانویس

منابع

• علی عباسی، پروتکل‌های کنترل همزمانی، دانشگاه تهران
• علی عباسی، کنترل همروندی، دانشگاه تهران
• (انگلیسی) (۳۷۰ ص) Philip A. Bernstein, Concurrency Control and Recovery in Database Systems, Addison Wesley, 1987
• (انگلیسی) Introduction to Concurrency Control
• (انگلیسی) http://publib.boulder.ibm.com/infocenter/wasinfo/v6r0/index.jsp?topic=/com.ibm.websphere.express.doc/info/exp/ae/cejb_cncr.html
• (انگلیسی) http://www.cs.berkeley.edu/~brewer/cs262/kung.pdf
• محمد جعفری فوتمی، تکنیک‌های کنترل همروندی
• سیستم مدیریت پایگاه داده‌ها (مفاهیم و تکنیک‌ها)، سید محمد تقی روحانی رانکوهی، انتشارات جلوه، بهار ۸۶