مدخل إلى أنظمة التشغيل الفصل الحادي عشر: متغيرات تقييد الوصول (Semaphores) في لغة البرمجة سي C

متغيرات تقييد الوصول (Semaphores) طريقةٌ جيدة للتعرف على التزامن، ولكنها ليست مستخدمة على نطاق واسع من الناحية العملية كاستخدام كائنات المزامنة (mutexes) والمتغيرات الشرطية (condition variables)، ومع ذلك توجد بعض مشاكل المزامنة التي يمكن حلها ببساطة باستخدام متغيرات تقييد الوصول، مما يؤدي إلى الوصول إلى حلول صحيحة ودقيقة. تقدّم هذه المقالة واجهة برمجة التطبيقات بلغة C للعمل مع متغيرات تقييد الوصول، وكتابة تطبيق لمتغير تقييد الوصول (semaphore) باستخدام كائنات المزامنة (mutexes) والمتغيرات الشرطية (condition variables).

POSIX Semaphores

متغير تقييد الوصول (semaphore) هو بنية بيانات تُستخدم لمساعدة الخيوط أن تعمل مع بعضها البعض دون تداخلٍ فيما بينها، يحدد POSIX القياسي واجهةً لمتغيرات تقييد الوصول، وهي ليست جزءًا من الخيوط Pthreads، ولكن توفّر معظم نظم التشغيل التي تعتمد على يونكس والتي تطبق Pthreads متغيرات تقييد الوصول أيضًا. لمتغيرات تقييد الوصول POSIX نوع هو sem_t، ووضع مغلّف له لجعل استخدامه أسهل كالعادة:

typedef sem_t Semaphore;

Semaphore *make_semaphore(int value);
void semaphore_wait(Semaphore *sem);
void semaphore_signal(Semaphore *sem);

Semaphore هو مرادف للنوع sem_t، ولكنني، يقول الكاتب، وجدت Semaphore أسهل للقراءة وذكّرني الحرف الكبير في أوله بمعاملته ككائن (object) وتمريره كمؤشر (pointer):

Semaphore *make_semaphore(int value)
{
    Semaphore *sem = check_malloc(sizeof(Semaphore));
    int n = sem_init(sem, 0, value);
    if (n != 0)
        perror_exit("sem_init failed");
    return sem;
}

تأخذ الدالة make_semaphore القيمة الابتدائية لمتغير تقييد الوصول كمعاملٍ لها، وتخصص حيزًا له وتهيئه ثم تعيد مؤشرًا إلى Semaphore. تعيد الدالة sem_init القيمة 0 إذا نجح تنفيذها وتعيد -1 إذا حدث خطأ ما. أحد الأمور الجيدة لاستخدام الدوال المغلّفة هو أنك تستطيع تغليف (encapsulate) شيفرة التحقق من الخطأ، مما يجعل الشيفرة التي تستخدم هذه الدوال أسهل للقراءة. يمكن تطبيق الدالة semaphore_wait كما يلي:

void semaphore_wait(Semaphore *sem)
{
    int n = sem_wait(sem);
    if (n != 0)
        perror_exit("sem_wait failed");
}

والدالة semaphore_signal:

void semaphore_signal(Semaphore *sem)
{
    int n = sem_post(sem);
    if (n != 0)
        perror_exit("sem_post failed");
}

أفضّل، يقول الكاتب، أن أسمي عملية تنبيه الخيط المتوقف بالمصطلح signal على أن أسميها بالمصطلح post على الرغم أن كلا المصطلحين شائعي الاستخدام. يظهر المثال التالي كيفية استخدام متغير تقييد الوصول ككائن مزامنة:

Semaphore *mutex = make_semaphore(1);

semaphore_wait(mutex);
// protected code goes here
semaphore_signal(mutex);

يجب أن تهيئ متغير تقييد الوصول الذي تستخدمه ككائن مزامنة بالقيمة 1 لتحدد أن كائن المزامنة غير مقفل، أي يستطيع خيطٌ واحد تمرير متغير تقييد الوصول دون توقف. استخدم اسم المتغير mutex للدلالة على أن متغير تقييد الوصول استخدم ككائن مزامنة، ولكن تذكّر أن سلوك متغير تقييد الوصول مختلف عن كائن مزامنة الخيط Pthread.

المنتجون والمستهلكون مع متغيرات تقييد الوصول (Producers and consumers with

semaphores) يمكن كتابة حل لمشكلة منتج-مستهلك باستخدام دوال مغلّفة لمتغير تقييد الوصول، حيث يصبح التعريف الجديد للبنية Queue باستبدال كائن المزامنة والمتغيرات الشرطية بمتغيرات تقييد الوصول كما يلي:

typedef struct
{
    int *array;
    int length;
    int next_in;
    int next_out;
    Semaphore *mutex;  //-- جديد
    Semaphore *items;  //-- جديد
    Semaphore *spaces; //-- جديد
} Queue;

والنسخة الجديدة من الدالة make_queue هي:

Queue *make_queue(int length)
{
    Queue *queue = (Queue *)malloc(sizeof(Queue));
    queue->length = length;
    queue->array = (int *)malloc(length * sizeof(int));
    queue->next_in = 0;
    queue->next_out = 0;
    queue->mutex = make_semaphore(1);
    queue->items = make_semaphore(0);
    queue->spaces = make_semaphore(length - 1);
    return queue;
}

يُستخدم المتغير mutex لضمان الوصول الحصري إلى الطابور، حيث قيمته الابتدائية هي 1 وبالتالي كائن المزامنة غير مقفل مبدئيًا. المتغير items هو عدد العناصر الموجودة في الطابور والذي هو أيضًا عدد الخيوط المستهلكة التي يمكن أن تنفذ الدالة queue_pop دون توقف، ولا يوجد أي عنصر في الطابور مبدئيًا. المتغير spaces هو عدد المساحات الفارغة في الطابور وهو أيضًا عدد الخيوط المنتجة التي يمكن أن تنفّذ الدالة queue_push دون توقف، ويمثل عدد المساحات مبدئيًا سعة الطابور وتساوي length-1. النسخة الجديدة من الدالة queue_push التي تشغّلها الخيوط المنتجة هي كما يلي:

void queue_push(Queue *queue, int item)
{
    semaphore_wait(queue->spaces);
    semaphore_wait(queue->mutex);

    queue->array[queue->next_in] = item;
    queue->next_in = queue_incr(queue, queue->next_in);

    semaphore_signal(queue->mutex);
    semaphore_signal(queue->items);
}

لاحظ أنه لا ينبغي على الدالة queue_push استدعاء الدالة queue_full مرة أخرى، حيث بدلًا من ذلك يتتبّع متغير تقييد الوصول عدد المساحات المتاحة ويوقف الخيوط المنتجة إذا كان الطابور ممتلئًا. النسخة الجديدة من من الدالة queue_pop هي:

int queue_pop(Queue *queue)
{
    semaphore_wait(queue->items);
    semaphore_wait(queue->mutex);

    int item = queue->array[queue->next_out];
    queue->next_out = queue_incr(queue, queue->next_out);

    semaphore_signal(queue->mutex);
    semaphore_signal(queue->spaces);

    return item;
}

شُرح هذا الحل باستخدام شيفرة عامة (pseudo-code) في الفصل الرابع من كتاب The Little Book of Semaphores.

صناعة متغيرات تقييد وصول خاصة

أية مشكلةٍ تُحَل باستخدام متغيرات تقييد الوصول تُحل أيضًا باستخدام المتغيرات الشرطية و كائنات المزامنة، ويمكن إثبات ذلك من خلال استخدام المتغيرات الشرطية وكائنات المزامنة لتطبيق متغير تقييد الوصول، حيث يمكن تعريف البنية Semaphore كما يلي:

typedef struct
{
    int value, wakeups;
    Mutex *mutex;
    Cond *cond;
} Semaphore;

المتغير value هو قيمة متغير تقييد الوصول، ويحصي المتغير wakeups عدد التنبيهات المعلقة (pending signals)، أي عدد الخيوط التي تنبّهت ولكنها لم تستأنف تنفيذها بعد، والسبب وراء استخدام wakeups هو التأكد من أن متغيرات تقييد الوصول الخاصة بك لديها الخاصية 3 المشروحة في كتاب The Little Book of Semaphores. يوفر المتغير mutex الوصول الحصري إلى لمتغيرين value و wakeups، المتغير cond هو المتغير الشرطي الذي تنتظره الخيوط إذا كانت تنتظر متغير تقييد الوصول. تمثل الشيفرة التالية شيفرة التهيئة للبنية Semaphore:

Semaphore *make_semaphore(int value)
{
    Semaphore *semaphore = check_malloc(sizeof(Semaphore));
    semaphore->value = value;
    semaphore->wakeups = 0;
    semaphore->mutex = make_mutex();
    semaphore->cond = make_cond();
    return semaphore;
}

تطبيق متغير تقييد الوصول (Semaphore implementation)

تطبيقي، يقول الكاتب، لمتغيرات تقييد الوصول باستخدام كائنات المزامنة POSIX والمتغيرات الشرطية كما يلي:

void semaphore_wait(Semaphore *semaphore)
{
    mutex_lock(semaphore->mutex);
    semaphore->value--;

    if (semaphore->value < 0)
    {
        do
        {
            cond_wait(semaphore->cond, semaphore->mutex);
        } while (semaphore->wakeups < 1);
        semaphore->wakeups--;
    }
    mutex_unlock(semaphore->mutex);
}

يجب على الخيط الذي ينتظر متغير تقييد الوصول أن يقفل كائن المزامنة قبل إنقاص قيمة المتغير value، وإذا أصبحت قيمة متغير تقييد الوصول سالبة سيتوقف الخيط حتى يصبح التنبه (wakeup) متاحًا، وطالما الخيط متوقف فإن كائن المزامنة غير مقفل، وبالتالي يمكن أن يتنبه (signal) خيطٌ آخر. شيفرة الدالة semaphore_signal هي:

void semaphore_signal(Semaphore *semaphore)
{
    mutex_lock(semaphore->mutex);
    semaphore->value++;

    if (semaphore->value <= 0)
    {
        semaphore->wakeups++;
        cond_signal(semaphore->cond);
    }
    mutex_unlock(semaphore->mutex);
}

يجب على الخيط مرة أخرى أن يقفل كائن المزامنة قبل زيادة قيمة المتغير value، وإذا كانت قيمة متغير تقييد الوصول سالبة فهذا يعني أن الخيوط منتظرة، وبالتالي يزيد تنبيه الخيط قيمة المتغير wakeups ثم ينبه المتغير الشرطي،وعند ذلك قد تتنبه أحد الخيوط المنتظرة ولكن يبقى كائن المزامنة مقفلًا حتى يفك الخيط المتنبه قفله، وعند ذلك أيضًا تعيد أحد الخيوط المنتظرة من الدالة cond_wait ثم تتحقق من أن التنبيه ما زال متاحًا، فإذا لم يكن متاحًا فإن الخيط يعود وينتظر المتغير الشرطي مرة أخرى، أما إذا كان التنبيه متاحًا فإن الخيط ينقص قيمة المتغير wakeups ويفك قفل كائن المزامنة ثم يغادر. قد يوجد شيء واحد ليس واضحًا في هذا الحل وهو استخدام حلقة do...while، هل يمكنك معرفة سبب عدم كونها حلقة while تقليدية؟ وما الخطأ الذي سيحدث؟

المشكلة مع حلقة while هي أنه قد لا يملك هذا التطبيق الخاصية 3، فمن الممكن أن يتنبه الخيط ثم يُشغّل ويلتقط تنبيهه الخاص. من المضمون مع حلقة do...while أن يلتقط أحد الخيوط المنتظرة التنبيه الذي أنشأه خيطٌ ما، حتى إذا شُغّل خيط التنبيه وحصل على كائن المزامنة قبل استئناف أحد الخيوط المنتظرة، ولكن اتضح أنه يمكن أن ينتهك التنبيه الزائف في الوقت المناسب (well-timed spurious wakeup) هذا الضمان.

ترجمة -وبتصرّف- للفصل Semaphores in C من كتاب Think OS A Brief Introduction to Operating Systems