تست و ست

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

می‌توان با استفاده از یک دستورالعمل تست و ست اتمیک یک قفل به صورت زیر ایجاد کرد:[1]

function Lock(boolean *lock) {
 while (test_and_set(lock) == 1);
}

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

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

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

حالت اول

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

حالت دوم

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

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

برخی مجموعه‌های دستورالعمل دارای یک دستورالعمل زبان ماشین تست و ست اتمیک هستند، برای مثال x86[2] و 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.