Thursday, January 01, 2009

Locks in kernel ...

به نام دوست

مدیریت مناطق بحرانی در هسته لینوکس با توجه به قابل اجرا بودن لینوکس بر روی سیستمهای چند پردازنده ای و همچنین قابلیت Preemption جزء لاینفک برنامه نویسی هسته میباشد. اتخاذ مکانیزم مناسب با توجه به طبیعت برنامه امری بسیار مهم است که در صورت رعایت نشدن آن موجبات crashهای نامنظم سیستم را فراهم میکند. در مقاله What is RCU یک روش ایجاد همزمانی شرح داده شد. استفاده از لاکهای از دیگر روشهای مرسوم در ایجاد همزمانی میباشند با سابقه‌ای طولانی‌تر از rcu، که در این مقاله به صورت مختصر با آنها آشنا میشویم.

۱- روندهای اجرایی
در هسته لینوکس سه دسته روندهای اجرایی از نظر اولویت و تاثیر بر یکدیگر وجود دارند:
  1. IRQ Handler
  2. Soft IRQ, Tasklet, Timer
  3. User Context
دسته بندی بدین معناست که در صورت اجرای روند با شماره بیشتر بر روی یک cpu، امکان گرفتن cpu از آن و واگذاری آن به روند اجرایی با شماره کمتر وجود دارد. به عبارتی اولویتها از بالا به پایین کاهش می یابد.
در مورد دسته بندی ۲، اجرای یک نمونه از هر نوع بر روی یک cpu مانع اجرای دیگری از همان دسته بر روی آن cpu میشود.
با توجه به اینکه ساختمان داده مشترک ما (داده های بحرانی) توسط چه دسته‌ای از روندها مورد تاثیر قرار میگیرد مکانیزم مناسب باید اتخاذ گردد. توجه به طبیعت اجرای هر کدام از روندها موجب درک بهتر مکانیزم مورد استفاده خواهد بود.

۲- آشنایی اولیه با روندها
هسته یک برنامه بزرگ است که اجرای کد از مجاری مختلف و در قالب روندهای زیر صورت می‌پذیرد:
IRQ Handler: در اصل قطعه کدی است که در پاسخ به یک وقفه سخت افزاری اجرا میشود. این موضوع مورد توجه است که همیشه یک نمونه از یک نوع وقفه در حال اجرا خواهد بود. به عبارتی در صورتیکه ساختمان داده ما توسط یک نوع وقفه مورد دسترسی قرار میگیرد جای هیچ گونه نگرانی برای ایجاد همزمانی وجود ندارد.
SoftIRQ: وقفه نرم‌افزاری، معمولا قطعه کدی هست که کامل کننده کار یک وقفه سخت افزاری میباشد. به عبارتی این نوع وقفه‌ها برای کوتاه‌تر شدن مدت زمان اجرای وقفه‌های سخت‌افزاری ایجاد شده‌اند. در مورد شیوه اجرای این روندها باید گفت که همیشه امکان اجرای چندین نسخه از یک نمونه وقفه نرم‌افزاری وجود دارد. بنابراین حتی اگر یک نوع وقفه نرم‌افزاری به داده‌ها دسترسی دارد بیشک میبایست متدهای همزمانی مناسب مورد توجه قرار گیرند.
Tasklet: این نوع روندها در اصل نوعی از وقفه‌های نرم‌افزاری میباشند. تفاوت در این است که این نوع روندها در زمان اجرا قابل تعریف میباشند بر خلاف وقفه‌های نرم‌افزاری که به صورت استاتیک در کد کرنل تعریف شده‌اند. همچنین این تضمین وجود دارد که تنها یک نمونه از یک نوع Tasklet در یک زمان در حال اجرا باشد.
Timer: این نوع روندها نیز نوعی وقفه نرم افزاری هستند که به صورت دابنامیک قابل تعریف هستند (مانند Taskletها) و میبایست در موعد مشخصی(از نظر زمانی) اجرا شوند. این روندها در قالب وقعه نرم افزاری TIMER_SOFTIRQ اجرا میشوند.
UserContext: در مواردی همچون اجرای system call از پراسسهای سطح کاربر، با توجه به اینکه کد system call در سطح هسته اجرا میشود، اصطلاحا این روند اجرایی که حاصل سوییچ کردن از مود کاربر به مود هسته است را UserContext مینامند.
نکته مهم در مورد چهار روند اول آن است که با توجه به اینکه این روندها اجرای اینتراپتها را غیرفعال میکنند به هیچ عنوان نباید به حالت wait بروند. در نتیجه متد لاکی که برای این روندهای میبایست مورد استفاده قرار گیرد به هیچ عنوان نباید به حالت wait رود حتی در صورتیکه لاک مورد نظر در دسترس نباشد.

۳- انواع لاکهای
مکانیزمهای اصلی لاک در هسته لینوکس به این شرح هستند:
  1. spinlock (فایل include/asm/spinlock.h): مکانیزم spinlock اصطلاحا busy wait بوده و نمونه یک مکانیزم سریع و سبک میباشد. در این نوع قفل تنها یک پردازش در یک زمان میتواند لاک را تصاحب کند و همچنین پردازشهای منتظر به هیچ عنوان به خواب نمیروند، بنابراین این نوع لاک برای روندهای گروه ۱ و ۲ مناسب میباشد.
  2. semaphore (فایل include/asm/semaphore.h): در این مکانیزم بسته به مقدار اولیه سمافر،‌ تعداد پردازشهایی که میتوانند در یک زمان لاک را تصاحب کنند قابل تنظیم است. البته در اکثر اوقات به صورت حداکثر یک تصاحب کننده در یک زمان(مانند spin) مورد استفاده قرار میگرید که این لاکها اصطلاحا با نام mutex (فایل include/linux/mutex.h)شناخته میشوند. پردازشهایی که نتوانسته‌اند قفل را تصاحب کنند به حالت wait خواهند رفت. استفاده از این لاک برای گروههای ۱ و ۲ به هیچ عنوان صحیح نیست. این لاک مناسب برای استفاده توسط گروه ۳ میباشد.
۴- spinlock
این متد لاک Busy wait هست: بدان معنی که cpu آنقدر چرخ میزند تا لاک را بدست آورد. به عبارتی پراسسی که سعی در بدست آوردن لاک دارد به حالت wait نمیرود.
نکات مورد توجه در استفاده از این لاک:
  1. قسمت بحرانی به هیچ عنوان نباید به حالت wait برود.
  2. قسمت بحرانی در حد امکان باید کوتاه باشد. (نظر به اینکه cpu را مطلقا در اختیار میگیرد)
فرم ساده استفاده از این لاک به این صورت میباشد:
spinlock_t lock = SPIN_LOCK_UNLOCKED;

spin_lock(&lock);

//critical section

spin_unlock(&lock);

بسته به اینکه چه روندهایی به ساختمان داده ما دسترسی دارند میبایست روش مناسبی برای بدست آوردن لاک استفاده گردد. روشهای دیگر برای بدست آوردن لاک به این شرح هستند:
۴-۱: spin_lock/unlock_bh
این تابع علاوه بر بدست آوردن لاک، اجرای SoftIRQها را بر روی پردازنده فعلی غیر فعال میکند. استفاده از این متد برای ایجاد همزمانی User Context ها با گروه دوم الزامی است.
دلیل غیر فعال کردن گروه ۲ احتمال بروز Dead Lock میباشد. در صورتیکه از حالت معمولی استفاده شود احتمال دارد به هنگامی که پردازش UserContext لاک را گرفته و در منطقه بحرانی به سر میبرد، توسط SoftIRQ پردازنده گرفته شده و آن هم سعی در گرفتن همان لاکی کند که هرگز باز نخواهد شد. البته در ایجاد همزمانی در سمت مقابل (SoftIRQها) با UserContext از فرمت ساده استفاده میشود چرا که در صورتی که پردازنده به آنها واگذار شود به هیچ عنوان توسط UserContext قابل بازپس گیری نیست.
استفاده از این مکانیزم بدین شکل خواهد بود:






UserContextSoftIRQ
spin_lock_bh(&lock);spin_lock(&lock);
//critical section//critical section
spin_unlock_bh(&lock);spin_unlock(&lock);

۴-۲: spin_lock/unlock_irq
این متد باعث میشود تا اجرای اینتراپتهای سخت افزاری و نرم افزاری بر روی پردازنده فعلی غیر فعال شود. از این متد برای هماهنگی ما بین گروههای ۳ و ۲ با گروه ۱ استفاده میشود. توجه داشته باشید که این تابع به هیچ عنوان به وضعیت فعال یا غیر فعال بودن اینتراپتهای سخت افزاری توجهی ندارد بنابراین برای صدا زدن از IRQ Handlerها مناسب نیست.
با توجه به اینکه اینتراپتهای نرم‌افزاری نیز غیر فعال میشوند میتوان از این روش برای ایجاد همزمانی مابین گروه ۳ با گروه ۱ استفاده کرد.
۳-۴:spin_lock_irqsave, spin_unlock_irqrestore
این متد علاوه بر بدست آوردن لاک، پرچم حالت (وضعیت فعال یا غیر فعال بودن اینتراپتها) را ذخیره میکند که برای ایجاد همزمانی ما بین IRQ Handlerها مورد استفاده قرار میگیرد.

۵- semaphore
چنانچه قبلا ذکر شد این نوع لاک مناسب برای ایجاد همزمانی مابین روندهای UserContext میباشد. بدست آوردن لاک در این مکانیزم معمولا به دو صورت انجام میشود: ۱- استفاده از تابع down و ۲- استفاده از تابع down_interruptible.
تابع شکل دوم در صورتی استفاده میشود که شما خواسته باشید در صورت ارسال سیگنال(به عنوان مثال فشردن ctrl+c) یا اینتراپت به برنامه‌ای که در حالت wait قرار دارد،‌ برنامه از wait خارج شود. خروج بدین شکل از حالت wait باعث میشود تابع down_interruptible مقدار خطا برگرداند.
با توجه به اینکه معمولا از mutex (سمافور با مقدار اولیه یک - یک نگهدارنده در یک زمان) برای ایجاد همزمانی استفاده میشود طرح کلی استفاده از این سمافور به عنوان نمونه ذکر میشود:
DEFINE_MUTEX(mt_lock);
mutex_lock_interruptible(&mt_lock);
//critical section
mutex_unlock(&mt_lock);
۶- مکانیزم مناسب جهت ایجاد همزمانی
جدول زیر به صورت خلاصه مکانیزم مناسب جهت ایجاد همزمانی با استفاده از لاکها را مابین روندهای گوناگون نشان میدهد. در این جدول متدهای مناسب جهت فراخوانی معرفی شده‌اند.

۳

۲

۱

روندها

spin_lock

spin_lock

spin_lock_irqsave

۱

spin_lock

spin_lock

spin_lock_irq

۲

down_interruptible

spin_lock_bh

spin_lock_irq

۳

اطلاعات جزءی‌تر را میتوانید از اینجا بدست آورید.

منابع استفاده شده:
Unreliable guide to locking
kernel locking techniques
understanding linux kernel

No comments: