فصل ۶: بهینه‌سازی OS و Lock-Free

مرجع: Developing High-Frequency Trading Systems

مقدمه

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

در این فصل مباحث زیر به طور عمیق کالبدشکافی می‌شوند:

• درک جامع تعویض زمینه (Context Switch): انواع، هزینه‌های ویرانگر آن در HFT و تکنیک‌های حذف کامل آن
• طراحی ساختارهای داده بدون قفل (Lock-Free Data Structures): صف‌های SPSC، MPMC و رفع معضل Priority Inversion
• سلسله‌مراتب حافظه، محاسبه فرمول AAT، مجاورت داده‌ها و پیش‌واکشی (Pre-fetching)
• معضلات تخصیص پویای حافظه (Dynamic Allocation) و پیاده‌سازی مخازن حافظه از پیش تخصیص‌یافته (Memory Pools)

---

۱. درک تعویض زمینه (Understanding Context Switches)

تعویض زمینه (Context Switch) به فرآیندی اطلاق می‌شود که طی آن سیستم‌عامل اجرای یک فرآیند یا نخ (Thread) را روی هسته پردازنده متوقف ساخته، وضعیت جاری آن را ذخیره می‌کند و کنترل پردازنده را به فرآیند یا نخ دیگری واگذار می‌نماید.

انواع کانتکست سوئیچ:

1. سخت‌افزاری در برابر نرم‌افزاری:
   • در سوئیچ سخت‌افزاری از قابلیت‌های معماری پردازنده نظیر Task State Segments (TSS) برای ذخیره خودکار ثبات‌ها استفاده می‌شود.
   • در سوئیچ نرم‌افزاری، کدهای کرنل سیستم‌عامل ثبات‌ها را روی پشته ذخیره می‌کنند.
2. سوئیچ بین نخ‌ها (Thread Switch) در برابر بین فرآیندها (Process Switch):
   • جابه‌جایی میان دو نخ متعلق به یک فرآیند واحد، کم‌هزینه‌تر است زیرا فضای آدرس مجازی و جداول صفحه یکسان باقی می‌مانند.
   • سوئیچ میان دو فرآیند مستقل فوق‌العاده گران است؛ زیرا علاوه بر ثبات‌ها، ثبات CR3 پردازنده بازنویسی شده و کل فضای آدرس مجازی و بافر TLB باید تعویض شود.
3. سوئیچ بین حالت کاربر و کرنل (User to Kernel Mode Switch):
   • هنگام رخ دادن یک وقفه سخت‌افزاری یا صدور فراخوان سیستمی، هسته برای رسیدگی وارد مد کرنل شده و مجدداً به فضای کاربر بازمی‌گردد.

---

چرا کانتکست سوئیچ برای برنامه‌های عادی خوب، اما برای HFT سمی است؟

• در برنامه‌های عادی (مانند آفیس یا مرورگرها): کانتکست سوئیچ قابلیتی ارزشمند است؛ زیرا ترکیبی از تعامل کاربر، دیسک I/O و محاسبات را به صورت متوازن میان برنامه‌ها تقسیم می‌کند.
• در معاملات فرکانس بالا (HFT): کانتکست سوئیچ یک فاجعه تمام‌عیار است!

هزینه‌های مخرب کانتکست سوئیچ در HFT:

1. اتلاف چرخه‌های پردازنده: ذخیره و بازیابی بلوک کنترل فرآیند (PCB - Process Control Block) بین ۱٬۰۰۰ تا ۱۰٬۰۰۰ نانوثانیه (۱ تا ۱۰ میکروثانیه) زمان می‌سوزاند.
2. آلودگی کش پردازنده (Cache Pollution):
   بزرگ‌ترین صدمه این است که با ورود فرآیند جدید، داده‌های حیاتی سیستم معاملاتی شما از کش‌های سریع L1 و L2 بیرون ریخته شده و بازنویسی می‌شوند. هنگامی که استراتژی دوباره CPU را پس می‌گیرد، با انبوهی از خطاهای کش (Cache Misses) مواجه می‌شود و باید متغیرها را با تاخیرهای صد نانوثانیه‌ای از RAM بخواند!
3. تخلیه بافر TLB: پاک شدن نگاشت صفحات و کند شدن دسترسی به آدرس‌های حافظه.
4. ایجاد تاخیر دنباله نوسانی (Jitter & Tail Latency): نوسان در زمان اجرای سفارشات که باعث می‌شود گاهی سیستم بسیار کند عمل کند.

---

راهکارهای مهندسی لینوکس برای حذف Context Switch در HFT:

1. ایزوله‌سازی هسته‌ها در گراب (isolcpus):
   با افزودن آرگومان isolcpus=2,3 به زمان بوت لینوکس، زمان‌بند هسته لینوکس هرگز هیچ پردازشی را روی این هسته‌ها قرار نمی‌دهد.
2. پین کردن نخ به هسته (Task Pinning / CPU Affinity):
   الصاق انحصاری فرآیند استراتژی به هسته ایزوله‌شده با استفاده از فراخوان pthread_setaffinity_np یا دستور taskset.
3. پیکربندی کرنل بدون تیک (NO_HZ_FULL):
   خاموش کردن کامل وقفه‌های زمان‌سنج سیستم‌عامل (Timer Ticks) روی هسته ایزوله‌شده تا پردازنده بدون حتی یک وقفه میلی‌ثانیه‌ای ۱۰۰٪ در اختیار کد معاملاتی باشد.
4. سیاست بلادرنگ SCHED_FIFO:
   تنظیم بالاترین اولویت پردازشی در لینوکس با اولویت ۹۹ به طوری که هیچ فرآیندی نتواند استراتژی را تعلیق کند.

---

۲. ساختارهای داده بدون قفل (Building Lock-Free Data Structures)

در برنامه‌نویسی سنتی چندهسته‌ای، دسترسی مشترک به داده‌ها با سازوکارهای مسدودکننده (Blocking) نظیر Mutex یا Spinlock محافظت می‌شود.

معایب ویرانگر قفل‌ها در HFT:

• تعلیق نخ و سوئیچ کانتکست: اگر نخ دیگر قفل را نگه داشته باشد، نخ جاری توسط سیستم‌عامل به خواب رفته و تاخیر به میکروثانیه‌ها جهش می‌کند.
• تاخیرهای صف‌بندی (Lock Contention): رقابت نخ‌ها بر سر تصاحب قفل باعث توقف پایپ‌لاین می‌شود.
• خطر بن‌بست (Deadlock): توقف کامل سامانه.
• پدیده معکوس شدن اولویت (Priority Inversion):
  حالتی فاجعه‌بار که در آن یک نخ با اولویت پایین (مثلاً نخ نوشتن لاگ) قفلی را در اختیار دارد؛ زمان‌بند سیستم‌عامل به دلیل ورود یک نخ با اولویت متوسط، اجرای نخ ضعیف را متوقف می‌کند؛ در نتیجه نخ حیاتی استراتژی با اولویت بالا ساعت‌ها پشت درِ بسته قفل معطل مانده و سیستم از معامله بازمی‌ماند!

---

اصول برنامه‌نویسی بدون قفل (Lock-Free)

رویکرد Lock-Free دسترسی همزمان چند نخ به داده‌ها را بدون مسدود شدن و بدون قفل ممکن می‌سازد:

• دستورالعمل‌های اتمیک سخت‌افزاری: اجرای دستورات مستقیم CPU نظیر Compare-And-Swap (CAS) یا LOCK CMPXCHG در اسمبلی x86.
• موانع حافظه (Memory Barriers / Fences): جلوگیری از بازآرایی دستورات خواندن و نوشتن توسط کامپایلر و پردازنده برای حفظ ترتیب ترتیبی عملیات.

ساختار صف حلقوی بدون قفل (Lock-Free Ring Buffer):

• در این ساختار، تولیدکننده (Producer) و مصرف‌کننده (Consumer) در یک آرایه حلقوی با اندازه ثابت (معمولاً توان‌هایی از ۲ مانند ۱۰۲۴ تا با عملیات بیتی AND به جای ماژولو ایندکس‌گذاری شوند) بدون قفل کار می‌کنند.
• تولیدکننده نشانگر last_write را با عملیات اتمیک جلو می‌برد.
• مصرف‌کننده نشانگر last_read را دنبال می‌کند.
• داده‌ها بدون کوچک‌ترین نیازی به Mutex با تاخیر چند نانوثانیه‌ای بین تردها منتقل می‌شوند.

---

چیدمان انواع صف‌های بدون قفل در اکوسیستم HFT:

• صف SPSC (Single-Producer Single-Consumer):
  سریع‌ترین و کارآمدترین ساختار صف جهان؛ یک فرآیند منحصراً می‌نویسد و یک فرآیند منحصراً می‌خواند. این ساختار در مسیر بحرانی (Critical Path) میان درگاه شبکه و موتور استراتژی استفاده می‌شود.
• صف MPSC (Multi-Producer Single-Consumer):
  چندین درگاه دریافت خوراک دیتای بازار همزمان داده‌ها را درون صف واحد استراتژی می‌ریزند.
• صف SPMC / MPMC (Multi-Producer Multi-Consumer):
  چندین تولیدکننده و چندین مصرف‌کننده برای وظایف با حساسیت کمتر نظیر توزیع داده‌های بازار، سرورهای ریسک و ذخیره لاگ‌ها.

---

۳. سلسله‌مراتب حافظه، پیش‌واکشی (Pre-fetching) و تخصیص اولیه

برای کاهش تاخیر دسترسی به داده‌ها، شناخت ساختار حافظه ضروری است:

1. ثبات‌های پردازنده (Registers): دسترسی در ۱ چرخه کلاک (~ ۰.۳ نانوثانیه).
2. کش L1: دسترسی در ~ ۰.۵ تا ۱ نانوثانیه.
3. کش L2: دسترسی در ~ ۳ تا ۵ نانوثانیه.
4. کش L3: دسترسی در ~ ۱۰ تا ۱۵ نانوثانیه.
5. حافظه اصلی RAM: دسترسی در ~ ۶۰ تا ۱۰۰ نانوثانیه.

---

فرمول میانگین زمان دسترسی به حافظه (Average Access Time - AAT)

$\text{AAT}=\text{Hit Time}+(\text{Miss Rate}\times \text{Miss Penalty})$

مثال عددی کتاب:

فرض کنید دسترسی به RAM برابر ۶۰ نانوثانیه باشد:

• بدون کش: میانگین زمان دسترسی دقیقاً ۶۰ نانوثانیه است.
• با کش L1 (زمان دسترسی ۰.۵ نانوثانیه و نرخ خطای ۱۰٪):
  $\text{AAT}=0.5+(0.10\times 60)=6.5\text{ ns}$
• با ترکیب L1 و L2 و L3 (با خطای ۰.۱٪):
  میانگین زمان دسترسی به زیر ۱ نانوثانیه می‌رسد! این نشان می‌دهد که حفظ داده‌ها درون کش تا چه اندازه سرنوشت‌ساز است.

---

اصول مجاورت ارجاع (Locality of Reference):

• مجاورت مکانی (Spatial Locality): قرار دادن بایت‌های داده در آدرس‌های فیزیکی مجاور در حافظه. در HFT ساختارهای داده پیوسته (مانند آرایه‌ها و بردارهای تخت) بر ساختارهای اشاره‌گری گسسته (مانند Linked List یا درخت‌ها) اولویت مطلق دارند تا با بارگذاری یک Cache Line، تمام مقادیر همسایه وارد کش شوند.
• مجاورت زمانی (Temporal Locality): استفاده مجدد و پیاپی از داده‌هایی که اخیراً بارگذاری شده‌اند.

---

تکنیک‌های پیش‌واکشی (Pre-fetching) و حذف انشعابات غیرقابل‌پیش‌بینی:

• پیش‌واکشی سخت‌افزاری: تشخیص الگوهای دسترسی خطی توسط مدار پردازنده.
• پیش‌واکشی نرم‌افزاری: صدور مستقیم دستور __builtin_prefetch در ++C برای بارگذاری لایه‌های عمیق‌تر دفترچه سفارشات پیش از نیاز به محاسبه:

__builtin_prefetch(&order_book[next_price_level], 0, 3);

• اجتناب از انشعاب‌های غیرقابل‌پیش‌بینی (Unpredictable Branches): پرش‌های شرطی تصادفی (if/elseهای غیرقابل پیش‌بینی) مانع پیش‌واکشی شده و پایپ‌لاین پردازنده را فلج می‌کنند؛ در کد HFT باید از عبارات بدون شاخه (Branchless Programming) استفاده شود.

---

۴. معضلات تخصیص پویای حافظه (Dynamic Memory Allocation)

مدیریت حافظه پویا با توابع malloc، free و عملگرهای new و delete در زمان اجرای زنده بازار اکیداً ممنوع است:

• سیستم‌عامل بلوک‌های آزاد هیپ را در دو لیست پیوندی (Freed list و Allocated list) نگهداری می‌کند. جستجوی بلوک حافظه در میان این لیست‌ها روندی غیرقطعی و به شدت زمان‌بر است.
• ایجاد پدیده پاشیدگی و تکه‌تکه شدن حافظه (Memory Fragmentation).
• نیاز به فراخوان‌های سیستمی هسته نظیر brk و sbrk.

راهکارهای طلایی مهندسی حافظه در HFT:

1. تخصیص روی پشته (Stack Allocation): ترجیح متغیرهای محلی روی پشته به جای هیپ.
2. مخازن حافظه از پیش تخصیص‌یافته (Memory Pools / Pre-allocation):
   • کلیه فضاهای مورد نیاز برای میلیون‌ها پیام و رکورد در زمان راه‌اندازی برنامه (پیش از آغاز روز معاملاتی) به صورت یکپارچه تخصیص داده می‌شوند.
   • در زمان ترید زنده، تخصیص حافظه صرفاً یک حرکت ساده ایندکس در آرایه از پیش ساخته‌شده با زمان ثابت $O(1)$ خواهد بود.
3. قفل کردن فضای آدرس در رم با mlockall:
   جلوگیری قطعی از سواپ شدن حافظه برنامه معاملاتی به حافظه دیسک توسط سیستم‌عامل لینوکس:

mlockall(MCL_CURRENT | MCL_FUTURE);

---

خلاصه و جمع‌بندی فصل ششم (Summary)

در این فصل، بنیادی‌ترین اصول کاهش تاخیر سیستمی را فراگرفتیم:

1. حذف کانتکست سوئیچ از طریق ایزوله‌سازی هسته‌ها (isolcpus)، پین کردن فرآیندها (CPU Pinning) و کرنل بدون تیک (NO_HZ_FULL).
2. پیاده‌سازی صف‌های حلقوی بدون قفل (SPSC Lock-Free Queues) و حذف خطرات Mutex و وارونگی اولویت.
3. استفاده از پیش‌واکشی داده‌ها، احترام به خطوط کش ۶۴ بایتی، و ممنوعیت مطلق malloc در زمان اجرای زنده بازار به کمک Memory Pools و mlockall.

در فصل بعدی (07 - شتاب‌دهی کرنل، فیبر نوری و لاگینگ)، تکنیک‌های پیشرفته Kernel Bypass (با فناوری Solarflare)، فایل‌های نگاشت‌شده در حافظه (mmap)، فیبر نوری توخالی (Hollow Fiber) و امواج مایکروویو را موشکافی خواهیم کرد!

---

→ فصل قبلی فصل ۵: شبکه و پروتکل‌های تبادل فصل بعدی ← فصل ۷: دور زدن کرنل و شتاب‌دهی شبکه