Wednesday, November 26, 2008

what is RCU? #1

به نام دوست

۱- مقدمه

RCU که مخفف Read-Copy Update میباشد یکی از روشهای ایجاد همزمانی در کنار روشهای متداول مدیریت مناطق بحرانی(حفاظت از اطلاعات به اشتراک گذاشته شده (اطلاعات بحرانی) مابین رشته‌های اجرایی) در کرنل لینوکس میباشد. مزیت اصلی این روش امکان انجام عمل read همزمان با عمل write/update میباشد. در روشهای معمول استفاده از lock ها در مدیریت مناطق بحرانی، در صورتیکه از قفلهای معمولی استفاده شود در هر زمان تنها یک پردازش قابلیت ورود به منطقه بحرانی را دارد و یا اگر از read-write lock ها استفاده شود امکان همزمانی ما بین پردازشهای خواننده وجود دارد و با ورود یک نویسنده، خواننده ها باید تا خروج او متوقف شوند.

RCU امکان رخداد یک write/update با readهای گوناگون را فراهم میسازد. بنابراین پردازشهایی که عمل read انجام میدهند به هیچ عنوان منتظر اتمام عمل write/update نخواهند شد که مزیت عمده ای به حساب می آید.

نکته ۱: چنانکه در پاراگراف قبلی نیز ذکر گردید، تنها رخداد یک نمونه از عمل write در آن واحد مجاز میباشد. بنابراین پردازشهایی که خواهان عمل write هستند میبایست با استفاده از متدهای معمول lock مانند spinlock و یا mutexlock از انجام تنها یک نمونه در یک زمان مطمئن شوند.
نکته ۲: چناچه عمل write نیازمند خواندن اطلاعات بحرانی میباشد، این عملیات نیز میبایست در محدوده محافظت شده توسط lockها قرار بگیرد.


۲- طرز کار
عمل انتساب و خواندن اشاره‌گرها در لینوکس به صورت اتمیک میباشد. بنابراین اگر تصور کنیم که پردازشی در حال خواندن یک اشاره‌گر میباشد و پردازش دیگری در همان زمان در حال نوشتن در اشاره‌گر(محتوای اشاره‌گر) می‌باشد، به عنوان نمونه وضعیت q را در مثال زیر در نظر بگیرید:
struct me{
int a, b;
} *p, *q;

A: write:
/* to now, "q" has old value */
p = kmalloc(sizeof(struct me), GFP_KERNEL);
p->a = 1;
p->b=2;
q = p;

B: read:
kprintf("%d", q->a)

هنگامی که عمل خواندن انجام میشود احتمال بروز دو حالت وجود دارد:
  1. q با آدرس قدیمی بارگذاری گردد: نظر به اینکه مقدار q تغییر کرده است نکته ای که اینجا باید رعایت شود این است که حافظه قدیمی تا اتمام عملیات خواندن توسط پردازش B نباید آزاد (free) گردد.
  2. q با آدرس جدید بارگذاری شود: در اینصورت این تضمین باید وجود داشته باشد که فیلدهای a و b از حافظه هدف، مقدار واقعی گرفته باشند. احتمال دارد که متغیر q قبل از اینکه پارامترهای حافظه هدف (p) مقدار واقعی بگیرند با آدرس حافظه هدف بارگذاری گردد. دلیل آن نیز پس و پیش شدن عملیاتهای انتساب به دلیل انجام فرآیند بهینه سازی توسط کامپایلر میباشد.
باید گفت که در یک جمله RCU میبایست این دو شرط را را برآورده کند. از شرط دوم شروع میکنیم.

۲-۱: اطمینان از وجود مقادیر واقعی
جهت اطمینان ازمقدار دهی به اشاره‌گر بعد از مقدار دهی به پارامترهای آن، میبایست از تابعی به نام rcu_assign_pointer که این موضوع را تضمین میکند استفاده گردد. بنابراین کد انتساب به اینصورت تغییر خواهد کرد:
rcu_assign_pointer(q, p);

این عمل که میبایست در سمت نویسنده انجام شود با نام publish شناخته میشود (ذکر مجدد این نکته ضروری است که در صورتیکه بیش از یک نویسنده وجود دارد این قسمت باید با اتخاذ مکانیزم lock مناسب مدیریت شود تا در هر زمان حداکثر یک نویسنده فعال باشد)
در سمت خواننده نیز جهت اطمینان از صحت اطلاعات حافظه هدف، (بدان معنی که قبل از انجام عمل publish این حافظه مورد استفاده قرار نگیرد) از تابع rcu_dereference استفاده میشود. این تابع تضمین میکند که ارجاعات بعدی به حافظه هدف، به حافظه publish شده خواهد بود. اصطلاحا به این عمل نیز subscribe گفته میشود. کد خواننده به اینصورت تغییر خواهد کرد:
rcu_read_lock();
p=rcu_dereference(q)
kprintf("%d", p->a);
rcu_read_unlock();

توابع rcu_read_lock و rcu_read_unlock برای تعیین نواحی بحرانی پردازشهای خواننده به کار میروند که جهت برآورده سازی شرط دوم استفاده از آنها ضروری میباشد. این لاکها از نوع لاکهای متداول مانند spin و mutex نیستند و بنابراین به هیچ عنوان باعث بلاک شدن خواننده و همچنین مانع از بروز عملیات نوشتن همزان با فرآیندهای خواندن نمیشود.
نکته ۳: استفاده تودرتو از این لاکها باعث بروز بن بست نمیشود و محدودیتی در استفاده تودرتو از آنها وجود ندارد.

۲-۲: تشخیص زمان حذف حافظه قدیمی
شرط دوم ماندگاری حافظه قدیم تا اتمام عمیات خواندن از آن حافظه و به عبارتی زمان مناسب برای حذف حافظه قدیم، است. دلیل استفاده از rcu_read_lock و rcu_read_unlock به جهت تشخیص فعال بودن فرآیند خواندن در حافظه قدیمی میباشد.
نکته این است که تمامی فعالیتهای خواندنی که قبل از تغییر اشاره‌گر اتفاق افتاده‌اند و هنوز در منطقه بحرانی خود به سر میبرند بر روی نسخه قدیمی درحال کار میباشند و فعالیتهای خواندنی که بعد از عملیات نوشتن شروع شده اند با حافظه جدید سروکار دارند. بنابراین زمان مناسب برای آزاد سازی حافظه قدیمی زمانی خواهد بود که تمامی پردازشهای خواننده که قبل از عمل publish شروع شده اند از ناحیه بحرانی خود خارج شوند.
به شکل روبرو نگاه کنید. در این شکل حد فاصل از دور خارج شدن حافظه قدیمی (Removal) تا آزاد سازی آن (Reclamation) با نام Grace Period مشخص شده است.
چنانکه مشاهده میشود تنها فرآیندهای خواندنی که قبل از Grace Period شروع شده‌اند و به اتمام نرسیده‌اند برای تصمیم گیری زمان حذف دخیل میباشند و فرآیندهای که در خلال این زمان اجرا شده اند به دلیلی که در بالا آمد در تصمیم گیری موثر نیستند.
تشخیص این زمان بر عهده تابع synchronize_rcu میباشد. صدازدن این تابع و به دنبال آن اتمام تابع موید اتمام Grace Period میباشد در نتیجه کد نوشتن(write) به این صورت تغییر خواهد کرد:
spin_lock(&my_lock);
/* to now, "q" has old value */
temp = q;
p = kalloc(sizeof(struct me), GFP_KERNEL);
p->a = 1;
p->b=2;
rcu_assign_pointer(q, p);
spin_unlock(&my_lock);
synchronize_rcu()
kfree(temp);
RCU با نگهداری نسخه های متعدد از یک شیء بر مسئله همزمانی فائق می آید. به عبارتی در آن واحد این امکان وجود دارد که خواننده ها بر روی نسخه های متعدد یک شیء در حال فعالیت باشند.

۳- کلام آخر در قسمت اول
فانکشنهایی که در بالا ذکر شده اند به عنوان فانکشنهای Low Level مکانیزم RCU شناخته میشوند و معمولا به صورت مستقیم مورد استفاده قرار نمیگیرند بلکه از توابع High Level استفاده میشود. نمونه کارا از این توابع توابع مدیریت لیست پیوندی در کرنل میباشد که در مسیر /include/linux/rculist.h قابل مشاهد هستند.
معمولا مکانیزم RCU برای مواقعی استفاده میشود که میزان فرآيندهای خواندن خیلی بیشتر از میزان فرآيندهای نوشتنی باشند.

موفق باشید

منبع: http://lwn.net/Articles/262464/

No comments: