الفصل ٦: مزامنة العمليات

CS330 - أنظمة التشغيل

القسم الحرج، السيمافورات، المشاكل الكلاسيكية

٦.١ خلفية

الوصول المتزامن إلى البيانات المشتركة قد يؤدي إلى عدم تناسق البيانات. الحفاظ على تناسق البيانات يتطلب آليات لضمان التنفيذ المنظم للعمليات المتعاونة.

العمليات المتعاونة

العمليات يمكن أن تُنفذ بشكل متزامن وقد تُقاطع في أي وقت، مكملة التنفيذ جزئيًا. الوصول المتزامن إلى البيانات المشتركة قد يؤدي إلى حالات السباق.

حالة السباق

⚠️ تعريف حالة السباق:

موقف حيث عدة عمليات تصل وتتعامل مع نفس البيانات بشكل متزامن، وتعتمد النتيجة على الترتيب المحدد الذي يحدث به الوصول.

مثال: مشكلة العداد

افترض أن العداد = ٥

المنتج ينفذ: counter++

المستهلك ينفذ: counter--

النتيجة يمكن أن تكون: ٤، ٥، أو ٦!

// مثال حالة السباق
// عملية المنتج
counter++; // هذه في الواقع ثلاث تعليمات آلية:
           // ١. register1 = counter
           // ٢. register1 = register1 + 1
           // ٣. counter = register1

// عملية المستهلك
counter--; // هذه أيضًا ثلاث تعليمات آلية:
           // ١. register2 = counter
           // ٢. register2 = register2 - 1
           // ٣. counter = register2
            

٦.٢ مشكلة القسم الحرج

القسم الحرج هو جزء من كود العملية الذي يتعامل مع البيانات أو الموارد المشتركة. يجب أن يكون تنفيذ القسم الحرج حصريًا بشكل متبادل.

قسم الدخول

القسم الحرج

قسم الخروج

القسم المتبقي

متطلبات الحل

الاستبعاد المتبادل: إذا كانت العملية Pi تنفذ في قسمها الحرج، فلا يمكن لأي عملية أخرى أن تنفذ في أقسامها الحرجة.
التقدم: إذا لم تكن هناك عملية تنفذ في قسمها الحرج وكانت بعض العمليات ترغب في الدخول، فيمكن فقط لتلك التي ليست في قسمها المتبقي المشاركة في تحديد من يدخل بعد ذلك، ولا يمكن تأجيل هذا الاختيار إلى أجل غير مسمى.
الانتظار المحدود: يجب أن يوجد حد على عدد المرات التي يُسمح فيها للعمليات الأخرى بالدخول إلى أقسامها الحرجة بعد أن تقدمت عملية بطلب وقبل منح هذا الطلب. هذا يمنع التجويع.

⚠️ مهم:

يجب تلبية جميع المتطلبات الثلاثة لحل صحيح لمشكلة القسم الحرج!

٦.٣ حل بيترسون

حل لعمليتين

يفترض أن تعليمات التحميل والتخزين ذرية. يستخدم متغيرين مشتركين:

int turn; - يشير إلى من دوره لدخول القسم الحرج
boolean flag[2]; - يشير إلى ما إذا كانت العملية جاهزة لدخول القسم الحرج

// حل بيترسون للعملية Pi
do {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j)
        ; // انتظار نشط
    
    // القسم الحرج
    
    flag[i] = false;
    
    // القسم المتبقي
} while (true);
            

✅ إثبات أن حل بيترسون يعمل:

الاستبعاد المتبادل: لا يمكن أن تكون كلتا العمليتين في القسم الحرج في نفس الوقت
التقدم: العملية خارج القسم الحرج لا تمنع الآخرين
الانتظار المحدود: العملية تنتظر على الأكثر دورًا واحدًا

٦.٤ مزامنة العتاد

العديد من الأنظمة توفر دعمًا عتاديًا لكود القسم الحرج. الأجهزة الحديثة توفر تعليمات عتاد ذرية خاصة.

تعليمة Test and Set

boolean test_and_set(boolean *target) {
    boolean rv = *target;
    *target = true;
    return rv;
}

// حل باستخدام test_and_set()
do {
    while (test_and_set(&lock))
        ; // انتظار نشط
    
    // القسم الحرج
    
    lock = false;
    
    // القسم المتبقي
} while (true);
            

تعليمة Compare and Swap

int compare_and_swap(int *value, int expected, int new_value) {
    int temp = *value;
    if (*value == expected)
        *value = new_value;
    return temp;
}
            

٦.٥ أقفال Mutex

الحلول السابقة معقدة لمبرمجي التطبيقات. مصممو أنظمة التشغيل يبنون أدوات برمجية لحل مشكلة القسم الحرج. أبسطها هو قفل mutex.

// استخدام قفل Mutex
acquire() {
    while (!available)
        ; // انتظار نشط
    available = false;
}

release() {
    available = true;
}

// كود العملية
do {
    acquire(lock);
    
    // القسم الحرج
    
    release(lock);
    
    // القسم المتبقي
} while (true);
            

⚠️ مشكلة Spinlock:

هذا التنفيذ يتطلب انتظارًا نشطًا. بينما تكون عملية في قسمها الحرج، أي عملية أخرى تحاول الدخول يجب أن تستمر في التكرار (تدور). هذا يضيع دورات المعالج.

٦.٦ السيمافورات

تعريف السيمافور

أداة مزامنة توفر طرقًا أكثر تطورًا للعمليات لمزامنة أنشطتها.

السيمافور S هو متغير صحيح يتم الوصول إليه فقط من خلال عمليتين ذريتين:

wait(S)

S--;
if (S < 0)
  block();

↔

signal(S)

S++;
if (S <= 0)
  wakeup();

أنواع السيمافورات

النوع	النطاق	الاستخدام
سيمافور ثنائي	٠ أو ١	الاستبعاد المتبادل (mutex)
سيمافور عددي	نطاق غير محدود	تخصيص موارد مع نسخ متعددة

تنفيذ السيمافور بدون انتظار نشط

typedef struct {
    int value;
    struct process *list;
} semaphore;

wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        // إضافة هذه العملية إلى S->list
        block();
    }
}

signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        // إزالة عملية P من S->list
        wakeup(P);
    }
}
            

٦.٧ المشاكل الكلاسيكية في المزامنة

١. مشكلة المخزن المؤقت المحدود

عنصر

فارغ

السيمافورات المستخدمة:

mutex - مهيأ إلى ١ (استبعاد متبادل)
full - مهيأ إلى ٠ (عدد المخازن الممتلئة)
empty - مهيأ إلى n (عدد المخازن الفارغة)

// عملية المنتج
do {
    // إنتاج عنصر في next_produced
    
    wait(empty);
    wait(mutex);
    
    // إضافة next_produced إلى المخزن المؤقت
    
    signal(mutex);
    signal(full);
} while (true);

// عملية المستهلك
do {
    wait(full);
    wait(mutex);
    
    // إزالة عنصر من المخزن المؤقت إلى next_consumed
    
    signal(mutex);
    signal(empty);
    
    // استهلاك العنصر في next_consumed
} while (true);
                

٢. مشكلة القراء والكتاب

مجموعة بيانات مشتركة بين عمليات متزامنة:

القراء: يقرؤون فقط مجموعة البيانات؛ لا تحديثات
الكتاب: يمكنهم القراءة والكتابة

المشكلة: السماح لقراء متعددين بالقراءة في نفس الوقت. كاتب واحد فقط يمكنه الوصول إلى البيانات المشتركة في كل مرة.

البيانات المشتركة:

rw_mutex - مهيأ إلى ١ (مشترك للقراء/الكتاب)
mutex - مهيأ إلى ١ (يحمي read_count)
read_count - مهيأ إلى ٠ (عدد القراء)

// عملية الكاتب
do {
    wait(rw_mutex);
    
    // يتم تنفيذ الكتابة
    
    signal(rw_mutex);
} while (true);

// عملية القارئ
do {
    wait(mutex);
    read_count++;
    if (read_count == 1)
        wait(rw_mutex);
    signal(mutex);
    
    // يتم تنفيذ القراءة
    
    wait(mutex);
    read_count--;
    if (read_count == 0)
        signal(rw_mutex);
    signal(mutex);
} while (true);
                

٣. مشكلة الفلاسفة

🍝 طاولة الفلاسفة

[إدراج مخطط: ٥ فلاسفة حول طاولة مع وعاء أرز وأعواد تناول الطعام]

وصف المشكلة:

٥ فلاسفة يأكلون ويفكرون فقط
كل فيلسوف يحتاج عودين لتناول الطعام
متاح فقط ٥ أعواد
توضح صعوبة تخصيص الموارد بدون جمود أو تجويع

// حل بسيط (قد يسبب جمود!)
chopstick[5]; // سيمافورات مهيأة إلى ١

do {
    wait(chopstick[i]);
    wait(chopstick[(i+1) % 5]);
    
    // تناول الطعام
    
    signal(chopstick[i]);
    signal(chopstick[(i+1) % 5]);
    
    // التفكير
} while (true);

// المشكلة: جمود إذا التقط كل فيلسوف العود الأيسر!
                

حلول لمنع الجمود:

السماح بأقصى ٤ فلاسفة على الطاولة
السماح بالتقاط العيدان فقط إذا كان كلاهما متاحًا
الفلاسفة الفرديون يلتقطون اليسار أولاً، الزوجيون يلتقطون اليمين أولاً

٦.٨ المراقبات

هيكل المراقب

البيانات المشتركة

↓

العمليات/الإجراءات

↓

كود التهيئة

↓

قائمة انتظار الدخول

تجريد عالي المستوى يوفر آلية ملائمة وفعالة لمزامنة العمليات. يمكن لعملية واحدة فقط أن تكون نشطة داخل المراقب في كل مرة.

حل المراقب لمشكلة الفلاسفة

monitor DiningPhilosophers {
    enum {THINKING, HUNGRY, EATING} state[5];
    condition self[5];
    
    void pickup(int i) {
        state[i] = HUNGRY;
        test(i);
        if (state[i] != EATING)
            self[i].wait();
    }
    
    void putdown(int i) {
        state[i] = THINKING;
        test((i + 4) % 5);
        test((i + 1) % 5);
    }
    
    void test(int i) {
        if ((state[(i+4)%5] != EATING) &&
            (state[i] == HUNGRY) &&
            (state[(i+1)%5] != EATING)) {
            state[i] = EATING;
            self[i].signal();
        }
    }
}
            

٦.٩ الجمود والتجويع

⚠️ مثال الجمود

عمليتان أو أكثر تنتظران إلى أجل غير مسمى لحدث لا يمكن أن يسببه إلا إحدى العمليات المنتظرة.

// مثال جمود مع سيمافورين
Semaphore S = 1, Q = 1;

// عملية P0        // عملية P1
wait(S);           wait(Q);
wait(Q);           wait(S);
   ...                ...
signal(S);         signal(Q);
signal(Q);         signal(S);
                

P0 تنتظر Q (ممسوك من قبل P1)، P1 تنتظر S (ممسوك من قبل P0) → جمود!

⚠️ التجويع

حجب غير محدد. عملية قد لا تُزال أبدًا من قائمة انتظار السيمافور التي علقت فيها.

انعكاس الأولوية

عملية ذات أولوية عالية تُستبق بشكل غير مباشر بواسطة عملية ذات أولوية منخفضة تمتلك قفلًا تحتاجه العملية ذات الأولوية العالية.

الحل: بروتوكول وراثة الأولوية

٦.١٠ مسائل تطبيقية وأسئلة اختبارات

أسئلة اختيار من متعدد

س١. موقف حيث عدة عمليات تصل إلى نفس البيانات في نفس الوقت وتعتمد النتيجة على ترتيب الوصول يسمى:

أ) حالة ديناميكية
ب) حالة سباق
ج) حالة أساسية
د) حالة حرجة

س٢. ما هو الترتيب الصحيح للعمليات لحماية قسم حرج باستخدام سيمافور ثنائي؟

أ) release() متبوعة بـ acquire()
ب) acquire() متبوعة بـ release()
ج) wait() متبوعة بـ signal()
د) signal() متبوعة بـ wait()

س٣. الاستبعاد المتبادل يمكن توفيره بواسطة:

أ) Spinlocks
ب) أقفال Mutex
ج) كل (أ) و (ب)
د) كل (أ) و (ب)

س٤. أي من هذه لا يلبي متطلبات القسم الحرج؟

أ) الاستبعاد المتبادل
ب) التقدم
ج) الانتظار المحدود
د) كلها تلبي المتطلبات

س٥. مشكلة المخزن المؤقت المحدود تُعرف أيضًا باسم:

أ) مشكلة القراء والكتاب
ب) مشكلة الفلاسفة
ج) مشكلة المنتج-المستهلك
د) لا شيء مما ذكر

س٦. في مشكلة الفلاسفة، يحدث الجمود عندما:

أ) جميع الفلاسفة الخمسة يلتقطون العود الأيسر
ب) ٤ فلاسفة يلتقطون العيدان
ج) ٣ فلاسفة يلتقطون العيدان
د) ٦ فلاسفة يلتقطون العيدان

أسئلة إجابة قصيرة

س٧. بالنظر إلى برنامجين متزامنين يستخدمان سيمافورين S1 (init=1) و S2 (init=0):

عملية P1:            عملية P2:
سيمافور S1=1;             سيمافور S1=1;
سيمافور S2=0;             سيمافور S2=0;
                      
while(True) {         while(True) {
  wait(S2);             wait(S1);
  print("A");           print("B");
  signal(S1);           signal(S2);
}                     }
                    

ما هو نمط المخرجات؟

الإجابة:

P1 ستُحجب بدايةً عند wait(S2). P2 تنفذ wait(S1)، تطبع "B"، ثم تشير S2. يمكن لـ P1 الآن المتابعة، تطبع "A"، تشير S1. النمط: BABA...

س٨. متغير مشترك mutex مهيأ إلى ١. كل عملية تنفذ wait(mutex) قبل دخول القسم الحرج و signal(mutex) بعده. ماذا يحدث إذا استبدلت عملية signal(mutex) بـ wait(mutex)؟

الإجابة:

سيحدث جمود. بعد أن تدخل العملية الأولى القسم الحرج وتخرج منه، ستنفذ wait(mutex) مرة أخرى، مما يجعل mutex = -١. لا يمكن لأي عملية أخرى دخول القسم الحرج مرة أخرى.

س٩. ما هي المتطلبات الثلاثة لحل مشكلة القسم الحرج؟

الإجابة:

الاستبعاد المتبادل: عملية واحدة فقط في القسم الحرج في كل مرة
التقدم: لا يمكن تأجيل اختيار العملية التالية إلى أجل غير مسمى
الانتظار المحدود: حد لعدد مرات دخول الآخرين للقسم الحرج بعد الطلب

٦.١١ المصطلحات الرئيسية والتعريفات

المصطلح	التعريف
حالة السباق	النتيجة تعتمد على ترتيب تنفيذ العمليات
قسم حرج	قطعة كود تصل إلى بيانات مشتركة
استبعاد متبادل	عملية واحدة فقط في القسم الحرج في كل مرة
سيمافور	متغير صحيح مع عمليات wait/signal ذرية
Mutex	سيمافور ثنائي للاستبعاد المتبادل
Spinlock	قفل يستخدم انتظارًا نشطًا
جمود	عمليات تنتظر إلى أجل غير مسمى لبعضها البعض
تجويع	عملية لا تحصل على موارد أبدًا
مراقب	بناء مزامنة عالي المستوى
عملية ذرية	عملية تكتمل دون انقطاع
انتظار نشط	اختبار مستمر لشرط
انعكاس الأولوية	عملية منخفضة الأولوية تحجب عملية عالية الأولوية

٦.١٢ مخططات من الشرائح

📊 توضيح حالة السباق

[إدراج مخطط يظهر الوصول المتزامن إلى عداد مشترك]

📊 طاولة الفلاسفة

[إدراج مخطط من Chapter_6.pdf يظهر ٥ فلاسفة مع أعواد الطعام]

📊 هيكل المراقب

[إدراج مخطط تخطيطي للمراقب]

📊 مخزن المنتج-المستهلك المؤقت

[إدراج تصور للمخزن المؤقت المحدود]

ملاحظة: يرجى توفير المخططات الفعلية من شرائح Chapter_6.pdf لاستبدال هذه العناصر النائبة.