حافظه تراکنشی نرم افزار

**حافظهٔ تراکنشی نرم‌افزاری** (به انگلیسی: Software Transactional Memory یا به‌اختصار STM) یک مکانیزم کنترل همروندی در علوم رایانه است که مشابه تراکنش‌های پایگاه داده برای کنترل دسترسی به حافظهٔ مشترک در محاسبات هم‌زمان به کار می‌رود. این روش جایگزینی برای همگام‌سازی مبتنی بر قفل است و در نرم‌افزار پیاده‌سازی می‌شود، نه در سخت‌افزار.

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

ایدهٔ پشتیبانی سخت‌افزاری از تراکنش‌ها نخستین‌بار در مقاله‌ای از تام نایت در سال ۱۹۸۶ ارائه شد. این مفهوم توسط موریس هرلیهی و جی. الیوت بی. ماس رواج یافت. در سال ۱۹۹۵، نیر شاویت و دن تویتو این مفهوم را به حافظهٔ تراکنشی صرفاً نرم‌افزاری (STM) گسترش دادند. از سال ۲۰۰۵، STM به موضوعی مهم در پژوهش‌های دانشگاهی تبدیل شده و پشتیبانی عملی از آن نیز رو به افزایش است.

## '''عملکرد'''
برخلاف تکنیک‌های قفل‌گذاری که در بیشتر برنامه‌های چندریسمانی مدرن به کار می‌رود، STM اغلب رویکردی خوش‌بینانه دارد: یک ریسمان (thread) تغییرات خود را روی حافظهٔ مشترک بدون توجه به آن‌چه سایر ریسمان‌ها انجام می‌دهند، اعمال می‌کند و همهٔ خواندن‌ها و نوشتن‌ها را در یک گزارش (log) ثبت می‌کند.

در پایان تراکنش، خواننده بررسی می‌کند که آیا تغییرات دیگری از سوی ریسمان‌های دیگر بر نواحی دسترسی‌یافته وجود داشته یا نه. اگر بررسی موفق باشد، تغییرات نهایی شده و تراکنش اصطلاحاً **commit** می‌شود. در غیر این صورت، تراکنش **abort** می‌شود و همهٔ تغییرات آن به حالت قبل بازگردانده می‌شود.

مزیت این رویکرد خوش‌بینانه افزایش هم‌زمانی است: هیچ ریسمانی نیاز به صبر برای دسترسی به یک منبع ندارد و ریسمان‌های مختلف می‌توانند به‌صورت هم‌زمان بخش‌های جداگانه‌ای از ساختار داده را تغییر دهند.

با این حال، در عمل، STM در مقایسه با سیستم‌های قفل‌گذاری دقیق در تعداد کم پردازنده‌ها (۱ تا ۴) ممکن است کندتر باشد، زیرا ثبت گزارش و انجام عملیات نهایی‌سازی زمان‌بر است. با این وجود، حتی در این حالت عملکرد معمولاً بیش از دو برابر کندتر نمی‌شود. بسیاری از طرفداران STM معتقدند این هزینه در برابر مزایای مفهومی آن ارزش دارد.

پیچیدگی زمانی و فضایی بدترین حالت برای n تراکنش هم‌زمان برابر O(n) است. با این حال، پیاده‌سازی‌های خاص می‌توانند با جلوگیری زودهنگام از تراکنش‌های ناکام، سربار را کاهش دهند.

## '''مزایا و معایب مفهومی'''
STM علاوه‌بر مزایای عملکردی، درک مفهومی برنامه‌های چندریسمانی را ساده‌تر می‌کند و نگه‌داری برنامه‌ها را آسان‌تر می‌سازد، زیرا با انتزاع‌های سطح‌بالا مانند اشیا و ماژول‌ها سازگار است.

در مقابل، برنامه‌نویسی مبتنی بر قفل‌گذاری با چالش‌های زیر روبرو است:

* نیاز به مدیریت عملیات هم‌پوشان و ناقص در بخش‌های پراکنده و غیرمرتبط کد؛ کاری دشوار و مستعد خطاست.
* نیاز به سیاست قفل‌گذاری برای جلوگیری از بن‌بست، گرسنگی (livelock) و سایر مشکلات توقف. این سیاست‌ها معمولاً غیررسمی و خطاپذیرند و اشکال‌یابی آن‌ها بسیار دشوار است.
* خطر وارونگی اولویت (priority inversion)، که در آن یک ریسمان با اولویت بالا منتظر ریسمانی با اولویت پایین می‌ماند.

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

با این حال، نیاز به بازاجرای تراکنش‌ها، رفتار آن‌ها را محدود می‌کند. همهٔ عملیات داخل تراکنش باید **idempotent** باشند، یعنی در صورت تکرار چندباره همان نتیجه را بدهند. همچنین، عملیات دارای اثرات جانبی (مثل ورودی/خروجی) باید در صورت لغو تراکنش قابل بازگردانی باشند. برای حل این مشکل، معمولاً بافرهایی برای جمع‌آوری عملیات غیرقابل بازگشت استفاده می‌شوند و این عملیات پس از موفقیت تراکنش اجرا می‌شوند. در زبان هسکل، این محدودیت در زمان کامپایل و توسط سامانهٔ نوع‌ها enforced می‌شود.

## '''عملیات های ترکیبی'''
در سال ۲۰۰۵، تیم هریس، سایمون مارلو، سایمون پیتون جونز و موریس هرلیهی یک سامانهٔ STM مبتنی بر هسکل هم‌زمان معرفی کردند که اجازه می‌دهد عملیات اتمی دلخواه را به عملیات اتمی بزرگ‌تر ترکیب کرد؛ قابلیتی که در برنامه‌نویسی مبتنی بر قفل ممکن نیست.

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

در سامانهٔ حافظهٔ تراکنشی نرم‌افزاری (STM)، ترکیب عملیات به‌صورت اتمی با قرار دادن آن‌ها در یک تراکنش امکان‌پذیر است. چالش اصلی، ناآگاهی کد فراخوان از زمان مناسب برای بازاجرای تراکنش ناموفق است. برای حل این مسئله، سازوکار «retry» پیشنهاد شده که با بررسی لاگ تراکنش، تشخیص می‌دهد چه زمانی داده‌ای تغییر کرده و تراکنش باید دوباره اجرا شود.

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

این رویکرد در **کامپایلر گلاسگو برای هسکل (GHC)** پیاده‌سازی شده است.

## '''پشتیبانی زبان پیشنهادی'''
سادگی مفهومی STMها (حافظه تراکنشی نرم‌افزاری) باعث می‌شود بتوان آن‌ها را با استفاده از نگارش‌های نسبتاً ساده‌ی زبان‌های برنامه‌نویسی در اختیار برنامه‌نویس قرار داد. تیم هریس و کایر فریزر در مقاله‌ی خود با عنوان *"پشتیبانی زبانی برای تراکنش‌های سبک‌وزن"*، ایده‌ی استفاده از ساختار کلاسیک *ناحیه بحرانی شرطی (CCR)* را برای نمایش تراکنش‌ها مطرح کردند. در ساده‌ترین حالت، این ساختار چیزی نیست جز یک *بلوک اتمی*، یعنی یک بخش از کد که از نظر منطقی، در یک لحظه‌ی منفرد اجرا می‌شود:
```c++
atomic {
    newNode->prev = node;
    newNode->next = node->next;
    node->next->prev = newNode;
    node->next = newNode;
}
```
وقتی که اجرای بلوک به پایان می‌رسد، تراکنش در صورت امکان *تأیید (commit)* می‌شود؛ وگرنه، *باطل (abort)* شده و مجدداً تلاش می‌شود. (این صرفاً یک مثال مفهومی است و کد کاملی نیست. مثلاً اگر در حین تراکنش گره‌ی `node` از لیست حذف شود، این کد به‌درستی کار نخواهد کرد.)

CCRها همچنین از *شرط محافظ* (guard condition) پشتیبانی می‌کنند که امکان می‌دهد تراکنش تا زمانی که کاری برای انجام دادن نداشته باشد منتظر بماند:
```c++
atomic (queueSize > 0) {
    remove item from queue and use it
}
```
اگر این شرط برقرار نباشد، مدیر تراکنش منتظر می‌ماند تا یک تراکنش دیگر تغییری در شرط ایجاد کند و پس از آن، دوباره تلاش کند. این جداسازیِ ضعیف بین تولیدکننده‌ها و مصرف‌کننده‌ها باعث افزایش *ماژولار بودن* در مقایسه با سیگنال‌دهی صریح بین نخ‌ها (threads) می‌شود.

در مقاله‌ی *"تراکنش‌های حافظه‌ای ترکیب‌پذیر (Composable Memory Transactions)"*، این مفهوم با معرفی دستور `retry` یک گام فراتر رفت. این دستور می‌تواند در هر لحظه، تراکنش را باطل کرده و منتظر بماند تا یکی از مقادیری که قبلاً در طول تراکنش خوانده شده تغییر کند، سپس تراکنش دوباره اجرا می‌شود. برای مثال:
```c++
atomic {
    if (queueSize > 0) {
        remove item from queue and use it
    } else {
        retry
    }
}
```
این توانایی برای بازآزمایی (retry) به‌صورت پویا و در میانه‌ی تراکنش، مدل برنامه‌نویسی را ساده‌تر می‌سازد و امکان‌های جدیدی را فراهم می‌آورد.

یکی از مسائل مهم، نحوه‌ی رفتار استثناها (exceptions) هنگام خروج از تراکنش‌هاست. در مقاله‌ی *"Composable Memory Transactions"*، نویسندگان تصمیم گرفتند که خروج استثنا از تراکنش باعث *باطل شدن* آن شود، چرا که در زبان Haskell همزمان (Concurrent Haskell)، استثناها معمولاً نشان‌دهنده‌ی خطاهای غیرمنتظره هستند. با این حال، استثنا می‌تواند اطلاعاتی که در طول تراکنش تخصیص داده شده یا خوانده شده را برای اهداف عیب‌یابی حفظ کند. البته، آن‌ها تأکید می‌کنند که در دیگر محیط‌ها ممکن است تصمیمات طراحی متفاوتی نیز منطقی باشند.

## '''قفل گذاری تراکنشی'''
STM (حافظه تراکنشی نرم‌افزاری) می‌تواند به‌صورت یک الگوریتم بدون قفل (*lock-free*) پیاده‌سازی شود یا از قفل‌گذاری استفاده کند. دو نوع طرح قفل‌گذاری وجود دارد:

۱. **قفل‌گذاری در زمان مواجهه (Encounter-time locking)** که توسط *Ennals، Saha* و *Harris* معرفی شده است:

در این روش، هنگام نوشتن در حافظه، ابتدا برای مکان مورد نظر یک قفل موقت گرفته می‌شود، سپس مقدار جدید مستقیماً نوشته می‌شود و در لاگ بازگردانی (*undo log*) ثبت می‌گردد.

۲. **قفل‌گذاری در زمان تعهد (Commit-time locking)**:

در این روش، مکان‌های حافظه فقط در *مرحله‌ی commit* قفل می‌شوند.

یکی از طرح‌های مبتنی بر commit-time به نام **Transactional Locking II** که توسط *Dice، Shalev* و *Shavit* پیاده‌سازی شده، از *ساعت نسخه‌ی سراسری (global version clock)* استفاده می‌کند. در این روش، هر تراکنش با خواندن مقدار فعلی این ساعت آغاز می‌شود و آن را به‌عنوان نسخه‌ی خوانده‌شده (*read-version*) ذخیره می‌نماید.

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

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

## '''مسائل مربوط به پیاده‌سازی'''
یکی از مشکلات پیاده‌سازی حافظه تراکنشی نرم‌افزاری (STM) با استفاده از **خواندن خوش‌بینانه (optimistic reading)** این است که ممکن است یک تراکنش ناقص، وضعیت ناهماهنگی را بخواند؛ یعنی ترکیبی از مقادیر قدیمی و جدید که توسط یک تراکنش دیگر نوشته شده‌اند. چنین تراکنشی در صورت تلاش برای commit، قطعاً باطل خواهد شد، بنابراین این موضوع، شرط سازگاری‌ای را که توسط سیستم تراکنشی اعمال می‌شود، نقض نمی‌کند.

اما با این حال، این وضعیت "موقتاً" ناسازگار ممکن است باعث شود که تراکنش دچار یک **خطای کشنده** مانند *segmentation fault* (دسترسی غیرمجاز به حافظه) شود، یا حتی وارد یک **حلقه‌ی بی‌پایان** گردد؛ مانند مثال ساختگی زیر که در شکل ۴ مقاله‌ی *"Language Support for Lightweight Transactions"* آمده است:

با فرض اینکه مقدار اولیه‌ی `x = y` باشد، هیچ‌یک از تراکنش‌های بالا این نامساوی را تغییر نمی‌دهند. اما ممکن است تراکنش A، مقدار `x` را **پس از** به‌روزرسانی آن توسط تراکنش B بخواند، اما مقدار `y` را **پیش از** به‌روزرسانی آن توسط همان تراکنش B بخواند. این وضعیت می‌تواند باعث شود که تراکنش A وارد یک **حلقه‌ی بی‌پایان** شود.

استراتژی رایج برای مقابله با این وضعیت، **گرفتن خطاهای کشنده (fatal exceptions)** و **ابطال تراکنش‌هایی است که معتبر نیستند**.

یکی از راه‌های برخورد با چنین مشکلاتی این است که تراکنش‌هایی را که عملیات غیرمجاز انجام می‌دهند یا به پایان نمی‌رسند، شناسایی کرده و آن‌ها را به‌طور تمیز (cleanly) ابطال کنیم؛

راهکار دیگر، استفاده از **طرح قفل‌گذاری تراکنشی (transactional locking scheme)** است.

## '''پیاده‌سازی‌های عملی'''

* Haskell GHC
* C++ cpp_stm_free
* Clojure Refs, ported to node-stm
* Go Kashmir
* Rust async-stm
* Scala ZIO
* OCaml Kcas
* Kotlin arrow-fx-stm

## '''منابع'''

# Tom Knight. *An architecture for mostly functional languages.* Proceedings of the 1986 ACM conference on Lisp and functional programming
# Maurice Herlihy and J. Eliot B. Moss. *Transactional memory: architectural support for lock-free data structures.* Proceedings of the 20th annual international symposium on Computer architecture (ISCA '93). Volume 21, Issue 2, May 1993.
# Nir Shavit and Dan Touitou. *Software transactional memory.* Distributed Computing. Volume 10, Number 2. February 1997.
# ""software transactional memory" - Google Scholar". Retrieved 10 November 2013.
رده:علوم رایانه