Deep Dive: Synchronization Examples تعمق: أمثلة المزامنة

Applying Semaphores and Locks to the "Big Three" classical problems: Bounded Buffer, Readers-Writers, and Dining Philosophers. تطبيق Semaphores و Locks على المشاكل الكلاسيكية الثلاث الكبرى: Bounded Buffer، Readers-Writers، و Dining Philosophers.

Bounded Buffer Bounded Buffer Readers-Writers Readers-Writers Dining Philosophers Dining Philosophers Windows Synchronization Windows Synchronization

1. Bounded Buffer Problem 1. مشكلة المخزن المؤقت المحدود (Bounded Buffer Problem)

Also known as the Producer-Consumer problem.
Goal: Producers create items, Consumers eat them. Buffer has fixed size $N$.
Constraints: Producer must wait if full. Consumer must wait if empty. تعرف أيضاً بمشكلة المنتج-المستهلك.
الهدف: المنتجون ينشئون العناصر، والمستهلكون يأكلونها. المخزن المؤقت له حجم ثابت $N$.
القيود: يجب على المنتج الانتظار إذا كان المخزن ممتلئاً. يجب على المستهلك الانتظار إذا كان المخزن فارغاً.

Structure: Semaphore mutex = 1; // Protects buffer access
Semaphore full = 0; // Count of filled slots
Semaphore empty = N; // Count of empty slots

// Producer
while (true) {
    item = produce();
    
    wait(empty); // Wait for space
    wait(mutex); // Lock buffer
    
    add_to_buffer(item);
    
    signal(mutex); // Unlock
    signal(full);  // Increment item count
}
                    

// Consumer
while (true) {
    wait(full);  // Wait for item
    wait(mutex); // Lock buffer
    
    item = remove_from_buffer();
    
    signal(mutex); // Unlock
    signal(empty); // Increment space count
    
    consume(item);
}
                    

2. Readers-Writers Problem 2. مشكلة القراء والكتاب (Readers-Writers Problem)

First Readers-Writers Problem مشكلة القراء والكتاب الأولى

Allows multiple readers to read at the same time. Only one writer can write at a time.
Priority: Readers. No reader is kept waiting unless a writer has already obtained permission. (Writers may starve). تسمح لعدة قراء بالقراءة في نفس الوقت. كاتب واحد فقط يمكنه الكتابة في وقت واحد.
الأولوية: للقراء. لا يتم جعل القارئ ينتظر ما لم يكن الكاتب قد حصل بالفعل على الإذن. (قد يحدث Starvation للكتاب).

Semaphore rw_mutex = 1; // Common lock for Writers & 1st Reader
Semaphore mutex = 1; // Protects read_count
int read_count = 0;

// Writer
while (true) {
    wait(rw_mutex);
    
    /* WRITING */
    
    signal(rw_mutex);
}
                    

// Reader
while (true) {
    wait(mutex);
    read_count++;
    if (read_count == 1) 
        wait(rw_mutex); // First reader locks out writers
    signal(mutex);
    
    /* READING */
    
    wait(mutex);
    read_count--;
    if (read_count == 0)
        signal(rw_mutex); // Last reader frees writers
    signal(mutex);
}
                    

3. Dining Philosophers Problem 3. مشكلة الفلاسفة المتناولين للطعام (Dining Philosophers Problem)

The Setup الإعداد

5 Philosophers sit at a round table. 5 Chopsticks placed between them.
To eat, a philosopher needs 2 chopsticks (Left and Right).
Shared data: `Semaphore chopstick[5];` (Initialized to 1). 5 فلاسفة يجلسون على طاولة مستديرة. 5 عيدان طعام موضوعة بينهم.
لكي يأكل، يحتاج الفيلسوف إلى عودين (يمين ويسار).
البيانات المشتركة: `Semaphore chopstick[5];` (مهيأة بـ 1).

// Philosopher i
while (true) {
    wait(chopstick[i]);
    wait(chopstick[(i+1) % 5]);
    
    /* EAT */
    
    signal(chopstick[i]);
    signal(chopstick[(i+1) % 5]);
    
    /* THINK */
}
                        

The Deadlock Problem: مشكلة الجمود (Deadlock): If all 5 philosophers become hungry simultaneously and grab their left chopstick, all `chopstick[i]` will be 0. Everyone waits for the right chopstick forever. إذا جاع الفلاسفة الخمسة في نفس الوقت وأمسكوا بعود الطعام الأيسر، ستكون كل `chopstick[i]` تساوي 0. سينتظر الجميع العود الأيمن إلى الأبد.

Solutions:الحلول:

Allow at most 4 philosophers at the table.السماح بحد أقصى 4 فلاسفة على الطاولة.
Pick up chopsticks only if BOTH are available (Atomic check).التقاط العيدان فقط إذا كان كلاهما متاحاً (فحص ذري).
Asymmetric solution: Odd philosophers pick Left first, Even pick Right first.حل غير متماثل: الفلاسفة الفرديون يلتقطون اليسار أولاً، والزوجيون يلتقطون اليمين أولاً.

Real World: Windows العالم الحقيقي: Windows

Windows uses interrupt masks for uniprocessor systems and spinlocks for multiprocessor systems. يستخدم Windows أقنعة المقاطعة للأنظمة أحادية المعالج و Spinlocks للأنظمة متعددة المعالجات.

Dispatcher Objects Dispatcher Objects Kernel objects used for sync (Mutexes, Semaphores, Events, Timers). كائنات النواة المستخدمة للمزامنة (Mutexes، Semaphores، Events، Timers).

Signaled State Signaled State Object is available. A thread will not block when acquiring it. الكائن متاح. لن يتم حجب الخيط عند الحصول عليه.

Non-Signaled State Non-Signaled State Object is not available. Thread blocks. الكائن غير متاح. يتم حجب الخيط.

Events Events Act like Condition Variables. Can notify one or multiple threads. تعمل مثل Condition Variables. يمكنها إعلام خيط واحد أو أكثر.

The Exam Vault خزنة الاختبار

Professor's Secrets & Trap Avoidance أسرار البروفيسور وتجنب الفخاخ

TRAP: Reader-Writer Starvation فخ: Starvation للقراء والكتاب

The "First Readers-Writers Problem" solves mutual exclusion but suffers from Writer Starvation. If new readers keep arriving, the writer will wait forever because `read_count` never drops to 0. "مشكلة القراء والكتاب الأولى" تحل الاستبعاد المتبادل ولكنها تعاني من Writer Starvation. إذا استمر القراء الجدد في الوصول، سينتظر الكاتب إلى الأبد لأن `read_count` لن ينخفض أبداً إلى 0.

TRAP: Signal & Wait Order فخ: ترتيب Signal و Wait

In Bounded Buffer, swapping `wait(empty)` and `wait(mutex)` can cause Deadlock.
If Producer grabs mutex (lock) but buffer is full (`empty` is 0), it sleeps holding the lock. Consumer cannot grab lock to empty the buffer. System freezes. في Bounded Buffer، تبديل `wait(empty)` و `wait(mutex)` يمكن أن يسبب Deadlock.
إذا أمسك المنتج بالـ mutex (القفل) لكن المخزن ممتلئ (`empty` هو 0)، فسينام وهو يمسك بالقفل. لا يستطيع المستهلك أخذ القفل لتفريغ المخزن. يتجمد النظام.

SECRET: Monitor Pattern سر: نمط Monitor

While Semaphores are powerful, they are error-prone (easy to forget a signal). High-level languages (Java/C#) use Monitors (synchronized keyword), which automatically handle locking and unlocking scope-wise. بينما الـ Semaphores قوية، فهي عرضة للأخطاء (من السهل نسيان إشارة). اللغات عالية المستوى (Java/C#) تستخدم Monitors (الكلمة المفتاحية synchronized)، التي تعالج القفل وفتحه تلقائياً حسب النطاق.

KEY CONCEPT: Condition Variable مفهوم أساسي: Condition Variable

In Monitors, we use Condition Variables (`wait()`, `signal()`) not to lock, but to wait for a specific condition (e.g., "Buffer Not Empty"). Note: Monitor `signal` is different from Semaphore `signal`. في Monitors، نستخدم Condition Variables (`wait()`، `signal()`) ليس للقفل، ولكن للانتظار حتى يتحقق شرط معين (مثل "المخزن ليس فارغاً"). ملاحظة: `signal` في Monitor تختلف عن `signal` في Semaphore.