تست و ست

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

حالت اول

زمانی که cpu شماره ۱، یک دستورالعمل تست و ست را شروع می‌کند، DPRAM ابتدا با ذخیره کردن آدرس مکان حافظه در یک محل خاص، یک یادداشت داخلی برای آن ایجاد می‌کند. اگر در این لحظه به‌طور اتفاقی، cpu شماره ۲، دستورالعمل تست و ست را برای همان مکان حافظه آغاز کند، DPRAM ابتدا یادداشت داخلی خود را چک می‌کند، شرایط را شناسایی می‌کند و یک وقفه فعال ایجاد می‌کند که به cpu ۲ می‌گوید که باید منتظر بماند و مجدداً تلاش کند. این حالت نوعی پیاده‌سازی یک انتظار فعال یا speen lock با استفاده از مکانیسم وقفه است. از آنجایی که تمام این فرایند با سرعت‌های سخت‌افزاری انجام می‌گیرد، انتظار 2cpu ۲ برای خروج از speen lock بسیار کوتاه است. cpu ۲ سعی کند که به مکان حافظه دسترسی پیدا کند و چه این اتفاق نیفتد، درهرصورت، DPRAM تستی را که توسط cpu 1 داده شده‌است را انجام می‌دهد. اگر تست با موفقیت انجام شود DPRAM مکان حافظه را به مقدار داده شده توسط سی‌پی‌یو ۱ تغییر می‌دهد. سپس DPRAM یادداشت داخلی خود را که cpu ۱ در آن نوشته‌است پاک می‌کند. در این لحظه سی‌پی‌یو ۲ می‌تواند یک تست و ست را آغاز کند که موفقیت‌آمیز خواهد بود.

حالت دوم

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

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

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

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

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

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

#define LOCKED 1

int test_and_set(int* lockPtr) {
    int oldValue;

    // -- Start of atomic segment --
    // This should be interpreted as pseudocode for illustrative purposes only.
    // Traditional compilation of this code will not guarantee atomicity, the
    // use of shared memory (i.e., non-cached values), protection from compiler
    // optimizations, or other required properties.
    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 in this section at a time
    lock = 0  // release lock when finished with the critical section
}

متغیر قفل، یک متغیر مشترک است، یعنی توسط تمام پردازنده ها/ ریسه‌ها قابل دسترسی است. به کلمه کلیدی volatile در کد بالا دقت کنید. این کلمه به معنی قابلیت تغییر است. در نبود volatile، کامپایلر و/یا پردازنده/پردازنده‌ها ممکن است، دسترسی به قفل را بهینه‌سازی کنند یا از مقادیر کش شده استفاده کنند، و بنابراین کد بالا را دچار خطا کنند. بالعکس، و البته متأسفانه، وجود volatile این تضمین را ایجاد نمی‌کند که خواندن‌ها و نوشتن‌ها ملزم به حافظه باشند. برخی کامپایلرها از سدهای حافظه استفاده می‌کنند تا مطمئن شوند که عملیات‌ها ملزم به حافظه هستند، اما از آنجایی که معانی volatile در زبان C یا ++C کاملاً مبهم است، بنابراین همهٔ کامپایلرها این کار را انجام نمی‌دهند.

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

مشارکت‌کنندگان ویکی‌پدیا. «Test-and-set». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۴ مارس ۲۰۲۱.

1. ↑ Anderson, T. E. (1990-01-01). "The performance of spin lock alternatives for shared-money multiprocessors". IEEE Transactions on Parallel and Distributed Systems. 1 (1): 6–16. doi:10.1109/71.80120. ISSN 1045-9219.
2. ↑ "BTS—Bit Test and Set". www.felixcloutier.com. Retrieved 2016-11-21.