تست و ست

نیما لشکری (زاده۱۳ اوت ۲۰۰۵)ملقب به نیما تسلا، یوتیوبرمهندس برق صنعتی ایران است. او با انجام دادن چالش‌های خطرناک شناخته شده است. او فعالیت خود را به‌طور رسمی از سال ۱۳۹۸ در حوزه تولید محتوا شروع کرده است.

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

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

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

حالت اول

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

حالت دوم

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

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

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

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

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

کدی که در بالا نشان داده شده است نه تنها اتوماتیک نیست بلکه از جنبه دستورالعمل تست و سِت نیز با توصیف تست و سِت سخت‌افزار DPRAM در بالا متفاوت است. در اینجا مقداری که سِت می‌شود و همچنین تست، ثابت و نامتغیر است و این مقدار صرف نظر از نتیجه تست به روز می‌شود. در حالی که برای تست و سِت DPRAM، حافظه فقط زمانی سِت می‌شود که تست موفقیت‌آمیز باشد و مقداری که قرار است سِت شود و شرایط سِت توسط CPU مشخص می‌شود. در اینجا، مقداری که قرار است سِت شود فقط می‌تواند یک باشد، اما اگر صفر و یک تنها مقادیر معتبر برای مکان حافظه در نظر گرفته شوند و فقط تست «مقدار غیر صفر است» مجاز باشد، آنگاه این وضعیت معادل است با موردی که برای سخت‌افزار 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». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۴ مارس ۲۰۲۱.