پیش‌نویس:واکشی و افزودن

در علوم رایانه، دستورالعمل سی‌پی‌یو واکشی و افزودن (به انگلیسی: fetch-and-add یا به اختصار FAA) به صورت اتمی محتوای یک مکان از حافظه را به یک مقدار مشخص افزایش می‌دهد.

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

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

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

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

 بارگذاری در یک ثبات (رجیستر)؛
 افزودن به ثبات؛
 ذخیره مجدد مقدار ثبات در .

وقتی یک فرآیند در حال انجام همزمان و فرآیند دیگری در حال انجام همزمان است، یک رقابت داده‌ای (Data Race) رخ می‌دهد. ممکن است هر دو فرآیند مقدار قدیمی را واکشی کرده و روی آن کار کنند، سپس هر دو نتایج خود را ذخیره کنند؛ این کار باعث می‌شود که یکی روی دیگری بازنویسی کند و مقدار ذخیره شده به جای مقدار مورد انتظار یعنی ، به یکی از مقادیر یا تبدیل شود.

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

موریس هرلیهی (۱۹۹۱) ثابت کرد که برخلاف عملیات مقایسه و جابه‌جایی، واکشی و افزودن دارای یک عدد اجماع محدود است. عملیات واکشی و افزودن می‌تواند مسئله اجماع بدون انتظار را برای حداکثر دو فرآیند همزمان حل کند.

 پیاده‌سازی 
دستورالعمل واکشی و افزودن مانند تابع زیر عمل می‌کند. نکته بسیار مهم این است که کل تابع به صورت اتمی اجرا می‌شود: هیچ فرآیندی نمی‌تواند در میانه اجرا وقفه ایجاد کند و در نتیجه وضعیتی را ببیند که فقط در طول اجرای تابع وجود دارد. این کد صرفاً برای کمک به توضیح رفتار واکشی و افزودن است؛ اتمی بودن نیاز به پشتیبانی صریح سخت‌افزاری دارد و بنابراین نمی‌توان آن را به عنوان یک تابع ساده در سطح بالا پیاده‌سازی کرد.

using std::atomic;

int fetchAndAdd(atomic<int>* location, int inc) {
 return location->fetch_add(inc);
}

یک قفل انحصار متقابل را می‌توان با استفاده از الگوریتم قفل بلیطی به صورت زیر پیاده‌سازی کرد:

import std;

using std::atomic;
using std::memory_order;

class Lock {
private:
 atomic<int> ticketNumber{0};
 atomic<int> turn{0};
public:
 void lock() {
 // باید اتمی باشد، زیرا چندین رشته ممکن است به طور همزمان درخواست قفل کنند
 int myTurn = ticketNumber.fetch_add(1, memory_order::relaxed);
 while (turn.load(memory_order::acquire) != myTurn) {
 // چرخش (انتظار فعال) تا زمانی که قفل به دست آید
 }
 }

 void unlock() {
 // این نیازی به اتمی بودن ندارد، زیرا فقط دارنده قفل این دستور را اجرا می‌کند
 turn.fetch_add(1, memory_order::release);
 }
};

 پشتیبانی سخت‌افزاری و نرم‌افزاری 
یک متد اتمی برای std::atomic<T> در استاندارد سی‌پلاس‌پلاس ۱۱ ظاهر شده است. این متد به عنوان یک افزونه اختصاصی برای زبان سی در مشخصات ای‌بی‌آی (ABI) پردازنده ایتانیوم، و (با همان نحو) در جی‌سی‌سی (GCC) در دسترس است.

 پیاده‌سازی در x86 
در معماری x86، دستورالعمل ADD با عملوند مقصدی که یک مکان حافظه را مشخص می‌کند، یک دستورالعمل واکشی و افزودن است که از زمان پردازنده ۸۰۸۶ وجود داشته است (هرچند در آن زمان این‌طور نامیده نمی‌شد)، و با پیشوند LOCK، در میان چندین پردازنده اتمی می‌شود. با این حال، این دستورالعمل نمی‌توانست مقدار اصلی مکان حافظه را برگرداند (اگرچه برخی از پرچم‌ها را برمی‌گرداند) تا اینکه پردازنده ۴۸۶ دستورالعمل XADD را معرفی کرد.

در ادامه یک پیاده‌سازی به زبان سی برای کامپایلر جی‌سی‌سی (GCC)، برای هر دو پلتفرم ۳۲ بیتی و ۶۴ بیتی x86 اینتل، بر اساس نحو توسعه‌یافته asm آورده شده است:
inline int fetchAndAdd(int* variable, int value) {
 asm volatile(
 "lock; xaddl %0, %1"
 : "+r" (value), "+m" (*variable) // ورودی + خروجی
 : // بدون ورودی صرف
 : "memory"
 );
 return value;
}

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

 جستارهای وابسته 
 مقایسه و جابه‌جایی
 بارگذاری پیوندی/ذخیره مشروط
 خواندن-اصلاح-نوشتن
 تست و تنظیم
 تست و تست و تنظیم

 منابع 

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