تست و ست

پیاده‌سازی سخت‌افزاری تست و سِت

دستورالعمل‌های تست و سِت در DPRAM می‌تواند به شیوه‌های مختلفی پیاده‌سازی شود. در اینجا دو حالت مختلف شرح داده می‌شود که در هر دو حالت یک DPRAM داریم که دو پورت را فراهم می‌کند و این امکان را می‌دهد که فقط دو قطعه الکترونیک مجزا، مانند دو واحد پردازش مرکزی (CPU)، به هر مکان حافظه در DPRAM دسترسی پیدا کنند.

حالت اول

زمانی که واحد پردازش مرکزی شماره یک (CPU1) دستورالعمل تست و سِت را آغاز می‌کند، DPRAM ابتدا آدرس مکان حافظه را در یک محل خاص ذخیره کرده و یک یادداشت داخلی برای آن ایجاد می‌کند. اگر در این لحظه به‌طور اتفاقی، CPU شماره دو (CPU2) دستورالعمل تست و سِت را برای همان مکان حافظه شروع کند، DPRAM ابتدا یادداشت داخلی خود را بررسی کرده، وضعیت را شناسایی کرده و یک وقفه فعال (interrupt) ایجاد می‌کند تا به CPU2 اعلام کند که باید منتظر بماند و مجدداً تلاش کند. این حالت به نوعی پیاده‌سازی یک «انتظار فعال» یا spin lock با استفاده از مکانیسم وقفه است. از آنجا که تمام این فرآیند با سرعت‌های سخت‌افزاری انجام می‌شود، مدت‌زمان انتظار CPU2 برای خارج شدن از spin lock بسیار کوتاه است. CPU2 سعی می‌کند که به مکان حافظه دسترسی پیدا کند و در هر صورت، DPRAM تستی را که توسط CPU1 داده شده است، انجام می‌دهد. اگر تست با موفقیت انجام شود، DPRAM مکان حافظه را به مقدار داده‌شده توسط CPU1 تغییر می‌دهد. سپس DPRAM یادداشت داخلی خود را که CPU1 در آن نوشته است، پاک می‌کند. در این مرحله، CPU2 می‌تواند یک دستور تست و سِت آغاز کند که به‌احتمال زیاد موفقیت‌آمیز خواهد بود.

حالت دوم

در این حالت، CPU1 دستورالعمل تست و سِت را برای نوشتن در مکان حافظه A آغاز می‌کند. DPRAM بلافاصله مقدار موردنظر را در مکان حافظه A ذخیره نمی‌کند، بلکه به‌طور هم‌زمان مقدار کنونی را به یک رجیستر خاص منتقل کرده و محتویات محل حافظه A را به یک مقدار پرچم خاص سِت می‌کند. اگر در این لحظه، CPU2 دستور تست و سِت را برای محل حافظه A آغاز کند، DPRAM پرچم مذکور را شناسایی کرده و مشابه حالت اول، یک وقفه فعال ایجاد می‌کند. خواه CPU2 تلاش کند به مکان حافظه دسترسی پیدا کند یا نه، در هر صورت DPRAM تست انجام‌شده توسط CPU1 را بررسی می‌کند. اگر تست با موفقیت انجام شود، DPRAM محل حافظه A را به مقدار مشخص‌شده توسط CPU1 سِت می‌کند. در غیر این صورت، DPRAM مقدار موردنظر را از رجیستر خاص مذکور به مکان حافظه A کپی می‌کند. هر کدام از این عملیات‌ها موجب پاک شدن مقدار پرچم خاص می‌شود. حالا، اگر CPU1 دوباره یک دستور تست و سِت را آغاز کند، این بار به احتمال زیاد موفقیت‌آمیز خواهد بود.

پیاده‌سازی نرم‌افزاری تست و سِت

برخی مجموعه‌های دستورالعمل مانند x86 و IBM System/360 (و مجموعه‌های دستورالعمل‌های بعدی، از جمله معماری z) دارای دستورالعمل زبان ماشین تست و سِت اتوماتیک هستند. مجموعه دستورالعمل‌هایی که فاقد دستور تست و سِت هستند، می‌توانند این عملیات را با استفاده از دستورالعمل‌های خواندن-تغییر-نوشتن یا دستورالعمل مقایسه-و-جابه‌جایی پیاده‌سازی کنند.

دستور تست و سِت زمانی که با مقادیر بولین (Boolean) استفاده می‌شود، معمولاً از منطقی مشابه با آنچه که در تابع زیر نشان داده شده است، استفاده می‌کند. البته باید توجه داشت که این تابع باید به‌طور اتوماتیک اجرا شود. به این معنا که هیچ فرآیند دیگری نباید بتواند اجرای آن را در میانه کار متوقف کند. بنابراین، این نوع تابع تنها زمانی اجرا می‌شود که به‌طور کامل تکمیل شود. برای پیاده‌سازی این حالت به پشتیبانی سخت‌افزاری نیاز است و به‌طور مستقیم قابل پیاده‌سازی نیست. با این حال، کد زیر می‌تواند برای توصیف رفتار تست و سِت کمک‌کننده باشد.

function TestAndSet(boolean_ref lock) {
    boolean initial = lock;
    lock = true;
    return initial;
}

کدی که در بالا نشان داده شده است، نه‌تنها اتوماتیک نیست، بلکه از جنبه دستورالعمل تست و سِت نیز با پیاده‌سازی سخت‌افزاری DPRAM متفاوت است. در اینجا، مقدار تست و سِت به‌صورت ثابت و بدون تغییر است، و این مقدار صرف‌نظر از نتیجه تست به‌روز می‌شود. در حالی که در پیاده‌سازی DPRAM، حافظه تنها زمانی سِت می‌شود که تست با موفقیت انجام شده باشد، و مقداری که باید سِت شود و شرایط آن توسط CPU مشخص می‌شود. در این پیاده‌سازی، مقدار موردنظر فقط می‌تواند یک باشد، اما اگر مقادیر صفر و یک تنها مقادیر معتبر برای مکان حافظه در نظر گرفته شوند و فقط تست «مقدار غیر صفر است» مجاز باشد، آنگاه این وضعیت معادل پیاده‌سازی سخت‌افزاری DPRAM خواهد بود. از این رو، این را می‌توان به‌طور صحیح به‌عنوان تست و سِت نامید.

پیاده‌سازی در زبان C

در زبان برنامه‌نویسی C، پیاده‌سازی این فرآیند به شکل زیر است:

#define LOCKED 1

int test_and_set(int* lockPtr) {
    int oldValue;

    // -- Start of atomic segment --
    oldValue = *lockPtr;
    *lockPtr = LOCKED;
    // -- End of atomic segment --

    return oldValue;
}

این کد نشان می‌دهد که در حقیقت دو عملیات مختلف انجام می‌شود: یک عملیات خواندن-تغییر-نوشتن و یک تست. تنها باید عملیات خواندن-تغییر-نوشتن به‌طور اتوماتیک انجام شود. این به این معناست که تأخیر در مقایسه مقدار در هر زمان، پس از دریافت مقدار تست، هیچ‌گونه تاثیری در نتیجه نخواهد داشت.

انحصار متقابل با استفاده از تست و سِت

یکی از روش‌های پیاده‌سازی انحصار متقابل، استفاده از یک قفل مبتنی بر تست و سِت است. در اینجا شبه‌کدی برای پیاده‌سازی این روش در زبان C آمده است:

volatile int lock = 0;

void critical() {
    while (test_and_set(&lock) == 1);
    // critical section: only one process can be here at a time
    lock = 0;  // release lock after leaving critical section
}

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

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