داده‌ساختارهای بدون قفل

[مطالبی که در ادامه می‌آید در سطح پیشرفته و نیازمند آشنایی خواننده با مفهوم «چندریسگی» و زبان برنامه‌سازی «سی پلاس پلاس» است.]

امروزه، کمتر کسی هست که در برنامه‌نویسی، اصطلاحات «پردازش چندریسه^۱» یا «پردازش موازی^۲» به گوشش نخورده باشد. پس از بازار داغ رقابت تولیدکننده‌های پردازنده برای افزایش سرعت پردازش تولیداتشان، در یک دهه‌ی اخیر این رقابت به تولید پردازنده‌هایی با تعداد پردازنده‌های بیشتر معطوف شد. البته تولید چنین پردازنده‌هایی سابقه‌ای دیرینه داشت، اما مدتی طول کشید تا به بازار رایانه‌های شخصی راه پیدا کند. با ظهور پردازنده‌های چندهسته‌ای، عموم برنامه‌نویس‌ها به تولید نرم‌افزارهای جدید یا بازتولید نرم‌افزارهای قدیم با قابلیت استفاده از این ویژگی پردازنده‌های نوین روی آوردند. اما علی‌رغم زیبایی و جذابیت آنچه پیش رو داشتند، تولید چنین نرم‌افزارهایی سختی خاص خودش را داشت که بزرگترین معضل آن با عنوان «کنترل دسترسی به داده‌های مشترک^۳» شناخته می‌شود.

حافظه‌ی داخلی رایانه‌های شخصی راهکاری را برای کنترل دسترسی پردازه‌ها به داده‌های مشترک ارائه نمی‌کنند، که این امر در تعدد خواندن و نوشتن، به سرعت موجب خراب شدن داده‌ها می‌شود. برای حل این مشکل، سازوکارهایی ایجاد شده‌اند که به «قفل^۴»، «میوتکس^۵» یا «حصار حافظه^۶» موسومند. استفاده از این سازوکارها، علاوه بر سربار محاسباتی زیاد، نیاز به دقت مضاعفی دارد تا از بروز اشتباهات ناشی از پیچیدگی به کار بردن آنها پرهیز شود. یافتن و جلوگیری از بروز این اشتباهات به هیچ عنوان کار ساده‌ای نیست، به گونه‌ای که توسعه‌دهندگان غالباً راه حل‌های «بدون قفل^۷» را، اگر وجود داشته باشند، ترجیح می‌دهند. اما متأسفانه روش مشخصی برای توسعه‌ی الگوریتم‌های بدون قفل شناخته نشده‌است، به همین دلیل رویکرد ساده‌تر دیگری توسعه داده شده‌است که این امر را برای برنامه‌نویسان تسهیل می‌کند: «داده‌ساختارهای بدون قفل».

پیش از آنکه به معرفی داده‌ساختارهای بدون قفل بپردازیم، لازم است به چند مورد از ایرادهای رایج در استفاده از قفل‌ها اشاره کنیم:

بن‌بست^۸: این مورد شایع‌ترین ایرادی است که در استفاده از قفل‌ها بروز می‌کند و اغلب ناشی از طراحی بد الگوریتم است. بن‌بست زمانی روی می‌دهد که دو پردازه به طور هم‌زمان منتظر دیگری برای گرفتن قفل باشند و یا اینکه پردازه‌ای که قفل را در دست دارد، به دلیل بروز خطا یا عوامل دیگر،‌ قفل را رها نکند.
رعایت نشدن اولویت‌ها: این مشکل زمانی رخ می‌دهد که پردازه‌ای با اولویت پایین‌تر قفل را در اختیار دارد و پردازه‌هایی با اولویت بالاتر منتظر هستند.
ازدحام: اگر پردازه‌ای که قفل را در اختیار دارد زمان زیادی برای پردازش نیاز داشته باشد، صفی طولانی از پردازه‌هایی تشکیل می‌شود که برای گرفتن قفل منتظر هستند.

این موارد تنها بخشی از مشکلاتی هستند که در استفاده از قفل‌ها برای کنترل دسترسی وقوع می‌یابند. سازوکارهای بدون قفل سعی می‌کنند تا با اصلاح روش نوشتن داده‌های مشترک و حذف قفل‌ها بر مشکلات پیش‌گفته فائق آیند، اما برای این منظور نیاز به پشتیبانی سخت‌افزار از «عملگرهای اتمی» دارند. عملگرهای اتمی عملگرهایی هستند که پردازنده آنها را در یک گام انجام می‌دهد و قابل تقسیم به عملگرهای کوچکتر نیستند. به طور مثال، انتقال یک مقدار به خانه‌ای از حافظه و خواندن آن عملگرهایی اتمی هستند. باید دقت داشت که ممکن است در زبان‌های برنامه‌سازی، برخی از دستورها به ظاهر اتمی باشند، در حالی که این چنین نیستند. مثلاً در زبان سی، دستور افزایش یک متغیر به صورت زیر است:

some_variable++;

برخلاف آنچه به نظر می‌رسد، انجام این دستور شامل خواندن، افزایش و نوشتن است، بنابراین اتمی نیست. برای پیاده‌سازی داده‌ساختارهای بدون قفل، نیاز به عملگر خاصی است که به آن «مقایسه و تعویض^۹» اطلاق می‌شود. این عملگر در همه‌ی پردازنده‌های نوین رایانه‌های شخصی پشتیبانی می‌شود، و در سیستم‌عامل‌های ویندوز و لینوکس با توابع زیر قابل فراخوانی است:

InterlockedCompareExcange    (ptr, cmp, exch);  // Win32
InterlockedCompareExchange64 (ptr, cmp, exch);  // Win64
__sync_val_compare_and_swap  (ptr, cmp, exch);  // Linux

همه‌ی این توابع، با دریافت اشاره‌گر ptr، مقدار ذخیره شده در مقصد آن را با مقدار cmp مقایسه کرده، در صورت برابر بودن آنها، مقدار exch را به مقصد ptr انتساب می‌دهند.

حتماً این سؤال در ذهن شما ایجاد شده‌است که چگونه یک دستور افزایش ساده در زبان سی اتمی نیست، اما یک عملگر پیچیده مانند «مقایسه و تعویض» می‌تواند اتمی باشد. پاسخ این سؤال در تضمینی که پردازنده به ما داده، نهفته است تا حین انجام «مقایسه و تعویض»، دسترسی تمام پردازه‌ها را به آدرسی از حافظه که در ptr ذخیره شده‌است،‌ سد کند (در جاهای دیگر به طور پیش‌فرض چنین تضمینی وجود ندارد)، بنابراین ما اطمینان خواهیم داشت که داده‌ی ما دست‌خورده و خراب نخواهد شد.

توضیح بالا یک مقدار زیاد و پیچیده شد ;-) اما استفاده از آن در یک مثال عملی در ادامه‌ی این مطلب، به روشن‌تر شدن موضوع کمک می‌کند. کد زیر پیاده‌سازی ساده‌ی یک پشته است که در آن از میوتکس برای کنترل دسترسی استفاده شده است.

typedef struct __snode {
    void    *data;  // contains actual data
    __snode *next;  // next node in stack list
} snode_t;

class Stack {
    snode_t *_head;
    pthread_mutex_t _lock;
public:
    Stack() : _head(NULL) {
        pthread_mutex_init(&_lock, NULL);
    }

    ~Stack() {
        /* destroy stack list */
        pthread_mutex_destroy(&_lock);
    }

    void push(void *data) {
        pthread_mutex_lock(&_lock);
        snode_t *p = new snode_t;
        p->data = data;
        p->next = _head;
        _head   = p;
        pthread_mutex_unlock(&_lock);
    }

    void *pop() {
        void *result;
        pthread_mutex_lock(&_lock);
        if (_head == NULL) result = NULL;
        else {
            result = _head->data;
            void *_t = _head;
            _head = _head->next;
            delete t;
        }
        pthread_mutex_unlock(&_lock);
        return result;
    }
};

همانطور که می‌بینید، به طور کلی، در برنامه‌هایی که از میوتکس استفاده می‌کنند، تعریف توابع و متدهایی که دسترسی به داده‌های مشترک دارند به صورت زیر است:

return_type method_name(arguments...) {
    /* initialize local and private data */
    pthread_mutex_lock(&_lock);
    /* manipulate and process shared data */
    pthread_mutex_unlock(&_lock);
    /* do cleanup and return results */
}

فاصله‌ی بین فراخوانی تابع pthread_mutex_lock و pthread_mutex_unlock منطقه‌ی امنی است که شما می‌توانید به‌راحتی داده‌های مشترک را دستکاری و پردازش کنید. اما موضوع به این سادگی‌ها نیست. فرض کنید برنامه‌نویس به اشتباه متد pop را به صورت زیر پیاده‌سازی کرده باشد:

    /* ... */
    void *pop() {
        void *result;
        pthread_mutex_lock(&_lock);
        if (_head == NULL) return NULL;
        else {
            result = _head->data;
            void *_t = _head;
            _head = _head->next;
            delete t;
        }
        pthread_mutex_unlock(&_lock);
        return result;
    }
    /* ... */

در اینجا می‌بینید که متد pop، در صورت خالی بودن پشته، مقدار NULL را برمی‌گرداند،‌ در حالی که قفل میوتکس را رها نکرده است. این شرایط موجب بروز بن‌بست در برنامه می‌گردد و دیگر هیچکدام از پردازه‌ها نمی‌توانند به داده‌های پشته دسترسی داشته باشند و در صف می‌مانند.

شاید بگویید که چنین خطایی فقط از برنامه‌نویس‌های مبتدی سر می‌زند و شما به عنوان یک برنامه‌نویس مجرب ممکن نیست چنین اشتباهی بکنید! 8-) اگر اینطور است، پیش از خواندن ادامه‌ی این مطلب نگاهی به پیاده‌سازی متد push بیندازید و ببینید که آیا همه چیز درست است! برای راحتی کار، کد متد push و خطی را که دارای ایراد است در ادامه آورده‌ایم:

    /* ... */
    void push(void *data) {
        pthread_mutex_lock(&_lock);
        snode_t *p = new snode_t;
        p->data = data;
        p->next = _head;
        _head   = p;
        pthread_mutex_unlock(&_lock);
    }
    /* ... */

دستور new در زبان سی پلاس پلاس، در صورت بروز خطا، موجب تولید استثنا^۱۰ می‌شود. برنامه در نقطه‌ی بروز استثنا متوقف شده، اجرای برنامه به اولین نقطه‌ای منتقل می‌شود که آن را بگیرد و پردازش کند. در این حالت نیز، متد push در حالی متوقف شده است که قفل میوتکس رها نشده است و در ادامه‌ی اجرای برنامه باز هم بن‌بست رخ می‌دهد.

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

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

typedef struct __snode {
    void    *data;  // contains actual data
    __snode *next;  // next node in stack list
} snode_t;

class Stack {
    snode_t *_head;
public:
    Stack() : _head(NULL) { }

    ~Stack() { /* destroy stack list */ }

    void push(void *data) {
        snode_t *p = new snode_t;
        p->data = data;
        do {
            p->next = _head;
        } while (__sync_val_compare_and_swap(&_head, p->next, p) != p->next);
    }

    void *pop() {
        void *result;
        snode_t *t;
        do {
            if ((t = _head) == NULL) return NULL;
        } while (__sync_val_compare_and_swap(&_head, t, t->next) != t);
        result = t->data;
        delete t;
        return result;
    }
};

فهمیدن کد بالا شاید کمی سخت باشد. برای همین منظور، برای مثال، عملکرد متد push را به صورت خط-به-خط شرح می‌دهیم. این متد، در ابتدای کار، یک المان جدید می‌سازد و داده‌ی مربوط به آن را تنظیم می‌کند. این عمل مستقل از داده‌های مشترک و امن است.

    void push(void *data) {
        snode_t *p = new snode_t;
        p->data = data;

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

        do {
            p->next = _head;
        } while (__sync_val_compare_and_swap(&_head, p->next, p) != p->next);

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

در داخل حلقه‌ی while، فراخوانی تابع sync_val_compare_and_swap را می‌بینید. این تابع ابتدا دسترسی‌های دیگر به حافظه را تا پایان کارش سد می‌کند. سپس مقایسه می‌کند که آیا مقدار اشاره‌گر به ابتدای لیست با مقدار انتساب داده شده به المان جدید برابر است یا نه. در صورتی که برابر نبودند، سد دسترسی به اشاره‌گر ابتدای لیست برداشته شده، شرط داخل حلقه true و حلقه دوباره اجرا می‌شود. در صورت برابری، اشاره‌گر ابتدای حلقه برابر آدرس المان جدید و عمل افزودن کامل می‌گردد. در نهایت، سد دسترسی به اشاره‌گر ابتدای لیست برداشته شده، حلقه‌ی while، با false شدن شرط آن، پایان می‌یابد.

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

“Lock-Free Data Structures,” Alexandrescu A., Dr. Dobb’s Journal, 2004 (Web, PDF)
“Lock-Free Programming,” Langdale G., Carnegie Mellon University (PDF)
“Scalable Lock-Free Dynamic Memory Allocation,” Michael M., IBM (PDF)

Multi-thread Processing
Parallel Processing
Shared-Data Access Control
Lock
Mutex
Memory Barrier
Lock-free
Deadlock
Compare and Swap (CAS)
Exception
Synchronization

نظر ۴

علی نادعلیزاده گفت:

ژوئن 18, 2014 در 10:27 ق.ظ

مطلب کامل و آموزنده ای بود. ممنون علی جان
راستی یک جایی یک غلط املایی هست : phtread_mutex_lock
- علی اصل روستا گفت:
  
  ژوئن 18, 2014 در 1:18 ب.ظ
  
  لطف داری.
  غلط املایی اصلاح شد. بابت دقت نظرت خیلی ممنون.
مجتبی الهی گفت:

ژوئن 27, 2014 در 4:41 ب.ظ

خیلی جالب بود، مخصوصا مثال‏‏ هاتون که هم ساده و قابل فهم بودن و هم خیلی آموزنده!

فقط یه چیزی که به نظرم می رسید، اینه که چون توی ۱۱++c خیلی سعی شده که قضیه multithreading به صورت یک استاندارد کلی بهش نگاه بشه، تا از تعدد قردادهایی که POSIX، ویندوز و … داشتن، جلوگیری بشه و براش کتابخانه هایی مثل thread و atomic توی stl در نظر گرفتن، بهتره ما هم توی مثالهامون سعی کنیم که از همون استانداردهای اصلی استفاده کنیم (من خودم یه چند وقت پیش یه سوال توی stackoverflow گذاشتم که توش از API های POSIX استفاده کرده بودم؛ هنوز ده ثانیه از گذاشتن سوالم بیشتر نگذشته بود که چند تا comment برام اومد که بهم توپیده بودن که چرا از کتابخانه ی استاندارد ۱۱++c استفاده نکرده بودم).
مثلا شما می تونستید به جای sync_val_compare_and_swap__ از std::atomic_compare_exchange_weak استفاده کنین یا به جای pthread_mutex_t از std::mutex استفاده کنین.

بازم ممنون، خیلی آموزنده بود!
- علی اصل روستا گفت:
  
  ژوئن 28, 2014 در 8:41 ق.ظ
  
  بابت اظهار لطفی که کردی ممنونم.
  فرمایشت متینه، اما به هر حال تمرکز این مقاله بر اصل موضوع، یعنی معرفی داده‌ساختارهاست، و به‌جز ذکر مثال به چگونگی پیاده‌سازی اونا پرداخته نشده؛ البته در مثال هم مناقشه نیست.
  از طرفی استاندارد C++11 نوپاست و زمان می‌بره تا بین برنامه‌نویسای این حوزه، که اکثرشون سال‌هاست با همون استانداردهای قدیمی کار کردن، جا بیفته، بنابراین، انتقاد از استفاده نکردن از استاندارد C++11، مثلاً موردی که از stackoverflow ذکر کردی، چندان صحیح نیست و در اون یه مورد خاص بیشتر رنگ و بوی فخرفروشی داره.

داده‌ساختارهای بدون قفل

علی اصل روستا

پست قبلیارزیابی تنبل در زبان C++11

پست بعدی۵ ابزار ساخت اپلیکیشن‌های iOS

نظر ۴