أمثلة على المزامنة
تغطية المشاكل الكلاسيكية للمزامنة مثل المخزن المؤقت المحدود، القراء والكتاب، والفلاسفة المتناولين للطعام، بالإضافة إلى آليات المزامنة في نواة نظام التشغيل ويندوز.
Synchronization Examples
Coverage of classic synchronization problems such as Bounded-Buffer, Readers-Writers, and Dining-Philosophers, along with Windows kernel synchronization mechanisms.
أهداف التعلم
- وصف مشكلة القسم الحرج وتوضيح حالة السباق (Race Condition).
- توضيح الحلول العتادية لمشكلة القسم الحرج باستخدام حواجز الذاكرة، عمليات المقارنة والتبديل، والمتغيرات الذرية.
- إثبات كيفية استخدام أقفال Mutex والسيمافورات لحل مشكلة القسم الحرج.
- شرح مشاكل المزامنة الكلاسيكية: المخزن المؤقت المحدود، القراء والكتاب، والفلاسفة المتناولين للطعام.
- Describe the critical-section problem and illustrate a race condition.
- Illustrate hardware solutions to the critical-section problem using memory barriers, compare-and-swap operations, and atomic variables.
- Demonstrate how Mutex locks and semaphores can be used to solve the critical section problem.
- Explain the bounded-buffer, readers-writers and dining-philosophers synchronization problem.
1 مشكلة المخزن المؤقت المحدود
1 Bounded-Buffer Problem
مشكلة مزامنة تتضمن منتجاً يضيف بيانات إلى طابور محدود ومستهلكاً يسحب منه، مع ضمان عدم الإضافة لطابور ممتلئ أو السحب من طابور فارغ.
A synchronization problem involving a producer adding to a finite queue and a consumer removing from it, ensuring no addition to a full queue or removal from an empty one.
تتكون المشكلة من $n$ من المخازن المؤقتة (Buffers)، كل منها يستوعب عنصراً واحداً.
تُستخدم ثلاثة سيمافورات للتحكم: mutex (بتهيئة
- لضمان الاستبعاد المتبادل،
full(بتهيئة - لعد العناصر الموجودة، و
empty(بتهيئة n) لعد الأماكن الفارغة.
يقوم المنتج بعمل wait(empty) ثم wait(mutex) قبل الإضافة، بينما يقوم المستهلك بعمل wait(full) ثم wait(mutex) قبل السحب.
The problem consists of $n$ buffers, each holding one item.
Three semaphores are used: mutex (initialized to
- for mutual exclusion,
full(initialized to - to count filled slots, and
empty(initialized to n) to count empty slots.
The producer calls wait(empty) then wait(mutex) before adding, while the consumer calls wait(full) then wait(mutex) before removing.
ترتيب عمليات wait بالغ الأهمية.
إذا قام المنتج بتنفيذ wait(mutex) قبل wait(empty) وكان المخزن ممتلئاً، فسيحتفظ بقفل الـ mutex وينام منتظراً مكاناً فارغاً.
في نفس الوقت، لن يتمكن المستهلك من سحب أي عنصر لأنه يحتاج إلى قفل الـ mutex، مما يؤدي إلى حالة الجمود (Deadlock).
The order of wait operations is critical.
If a producer executes wait(mutex) before wait(empty) and the buffer is full, it will hold the mutex lock and sleep waiting for an empty slot.
Meanwhile, the consumer cannot remove an item because it needs the mutex lock, resulting in a Deadlock.
ماذا يحدث إذا قمنا بتهيئة السيمافور `mutex` بالقيمة 0 بدلاً من 1 في مشكلة المخزن المؤقت المحدود؟ What happens if we initialize the `mutex` semaphore to 0 instead of 1 in the bounded-buffer problem?
لن يتمكن أي من المنتج أو المستهلك من الدخول إلى القسم الحرج، مما يؤدي إلى توقف النظام فوراً (Deadlock).
Neither the producer nor the consumer will be able to enter the critical section, leading to an immediate system deadlock.
2 مشكلة القراء والكتاب
2 Readers-Writers Problem
مشكلة مزامنة تسمح لعدة قراء بالوصول إلى البيانات المشتركة في نفس الوقت، ولكنها تتطلب وصولاً حصرياً للكاتب لمنع تعارض البيانات.
A synchronization problem that allows multiple readers to access shared data simultaneously but requires exclusive access for a writer to prevent data inconsistency.
تُستخدم هذه المشكلة لإدارة الوصول إلى قاعدة بيانات مشتركة.
القراء (Readers) يقرأون فقط ولا يقومون بأي تحديثات، بينما الكتاب (Writers) يمكنهم القراءة والكتابة.
المتغيرات المشتركة هي: سيمافور rw_mutex (بتهيئة
- لحماية وصول الكاتب أو أول قارئ، سيمافور
mutex(بتهيئة - لحماية المتغير
read_count، والمتغير الصحيحread_count(بتهيئة - لتتبع عدد القراء النشطين.
This problem manages access to a shared database.
Readers only read and perform no updates, while Writers can both read and write.
Shared variables include: semaphore rw_mutex (initialized to
- to protect access for the writer or the first reader, semaphore
mutex(initialized to - to protect the
read_countvariable, and integerread_count(initialized to - to track active readers.
هناك اختلافات للمشكلة:
مشكلة 'القارئ-الكاتب الأولى' تعطي الأولوية للقراء، مما قد يؤدي إلى مجاعة (Starvation) للكتاب إذا استمر القراء في التوافد.
مشكلة 'القارئ-الكاتب الثانية' تنص على أنه بمجرد أن يكون الكاتب جاهزاً، لا يُسمح لأي قارئ جديد بالبدء، مما قد يؤدي إلى مجاعة القراء.
تُحل هذه المشاكل في بعض الأنظمة عبر توفير أقفال القارئ-الكاتب (Reader-Writer Locks) من قبل النواة.
There are variations:
The 'First reader-writer' problem prioritizes readers, which can lead to writer starvation if readers keep arriving.
The 'Second reader-writer' problem states that once a writer is ready, no newly arrived reader is allowed to read, potentially starving readers.
These issues are solved in some systems by kernel-provided reader-writer locks.
| Readers | Writers | |
|---|---|---|
| نوع الوصولAccess Type | قراءة فقط (بدون تحديثات)Read only (no updates) | قراءة وكتابةRead and write |
| التزامن المسموحAllowed Concurrency | متعدد (عدة قراء في نفس الوقت)Multiple (simultaneous readers allowed) | حصري (كاتب واحد فقط)Exclusive (only one writer) |
لماذا يحتاج القارئ الأول فقط إلى قفل `rw_mutex`؟ Why does only the first reader need to lock `rw_mutex`?
لأن القارئ الأول هو من يمنع الكتاب من الدخول. بمجرد دخوله، يمكن للقراء الآخرين الدخول بحرية لأنهم لا يتعارضون مع بعضهم. القارئ الأخير هو من يحرر القفل للسماح للكتاب بالدخول.
Because the first reader is the one that blocks writers. Once inside, other readers can enter freely as they don't conflict. The last reader releases the lock to allow writers in.
3 مشكلة الفلاسفة المتناولين للطعام
3 Dining-Philosophers Problem
نموذج كلاسيكي لتوضيح مشاكل تخصيص الموارد المتعددة (مثل الجمود والمجاعة) بين عمليات متنافسة دون تفاعل مباشر بينها.
A classic model illustrating the problems of allocating multiple resources (like deadlock and starvation) among competing processes without direct interaction.
يجلس $N$ من الفلاسفة (عادة 5) حول طاولة مستديرة مع وعاء أرز في المنتصف.
يقضون وقتهم في التفكير والأكل بالتناوب.
للأكل، يحتاج الفيلسوف إلى عودي طعام (Chopsticks) - واحد من اليمين وواحد من اليسار.
البيانات المشتركة هي مصفوفة سيمافورات chopstick[5] مهيأة بـ 1.
الخوارزمية الأساسية تجعل الفيلسوف $i$ ينتظر العود $i$ ثم العود $(i+1)\%5$.
$N$ philosophers (usually 5) sit at a round table with a bowl of rice in the middle.
They alternate between thinking and eating.
To eat, a philosopher needs two chopsticks - one from the left and one from the right.
Shared data is an array of semaphores chopstick[5] initialized to 1.
The basic algorithm makes philosopher $i$ wait for chopstick $i$ then chopstick $(i+1)\%5$.
الخوارزمية المباشرة تعاني من مشكلة قاتلة:
إذا جاع جميع الفلاسفة الخمسة في نفس اللحظة والتقط كل منهم العود الموجود على يساره wait(chopstick[i])، فإن جميع السيمافورات ستصبح 0.
عندما يحاولون التقاط العود الأيمن، سينتظرون إلى الأبد، مما يسبب حالة جمود (Deadlock) تامة.
The straightforward algorithm has a fatal flaw:
if all 5 philosophers become hungry at the exact same time and each picks up their left chopstick wait(chopstick[i]), all semaphores become 0.
When they try to pick up the right chopstick, they will wait forever, causing a complete Deadlock.
كيف يمكننا تعديل خوارزمية الفلاسفة لتجنب حالة الجمود (Deadlock)؟ How can we modify the philosophers' algorithm to avoid Deadlock?
يمكننا السماح لأربعة فلاسفة فقط بالجلوس على الطاولة، أو جعل الفيلسوف يلتقط العودين معاً في قسم حرج واحد، أو استخدام استراتيجية غير متماثلة (فيلسوف فردي يلتقط اليسار أولاً، وزوجي يلتقط اليمين أولاً).
We could allow only 4 philosophers at the table, make a philosopher pick up both chopsticks in a critical section, or use an asymmetric strategy (odd philosopher picks left first, even picks right first).
4 مزامنة النواة في نظام ويندوز
4 Kernel Synchronization - Windows
يستخدم ويندوز أقنعة المقاطعة للأنظمة أحادية المعالج، وأقفال الدوران للأنظمة متعددة المعالجات، وكائنات الموزع لمزامنة مساحة المستخدم.
Windows uses interrupt masks for uniprocessor systems, spinlocks for multiprocessor systems, and dispatcher objects for user-land synchronization.
لحماية الموارد العالمية، يستخدم ويندوز أقنعة المقاطعة (Interrupt Masks) في الأنظمة أحادية المعالج لمنع المقاطعات.
في الأنظمة متعددة المعالجات، يستخدم أقفال الدوران (Spinlocks)، حيث لا يتم مقاطعة الخيط (Thread) الذي يمتلك القفل أبداً.
كما يوفر كائنات الموزع (Dispatcher Objects) التي تعمل كـ Mutexes، Semaphores، Events، و Timers.
الأحداث (Events) تعمل كمتغيرات شرطية، والمؤقتات (Timers) تنبه الخيوط عند انتهاء الوقت.
To protect global resources, Windows uses interrupt masks on uniprocessor systems to disable interrupts.
On multiprocessor systems, it uses spinlocks, where a spinlocking-thread is never preempted.
It also provides dispatcher objects for user-land, acting as mutexes, semaphores, events, and timers.
Events act much like condition variables, and timers notify threads when time expires.
كائنات الموزع لها حالتان: حالة الإشارة (Signaled State) وتعني أن الكائن متاح ولن يتم حظر الخيط عند طلبه، وحالة عدم الإشارة (Nonsignaled State) وتعني أن الكائن غير متاح وسيتم حظر الخيط (Thread will block) حتى تتغير الحالة.
عندما يحرر المالك قفل الـ Mutex، ينتقل من حالة عدم الإشارة إلى حالة الإشارة.
Dispatcher objects have two states: Signaled state (object available, thread will not block) and Nonsignaled state (object unavailable, thread will block).
When an owner thread releases a mutex lock, it transitions from nonsignaled to signaled state.
| Uniprocessor Systems | Multiprocessor Systems | |
|---|---|---|
| آلية الحماية الأساسيةPrimary Protection Mechanism | أقنعة المقاطعة (Interrupt Masks)Interrupt Masks | أقفال الدوران (Spinlocks)Spinlocks |
| سلوك الخيط (Thread Behavior)Thread Behavior | يمنع المقاطعات محلياًDisables local interrupts | لا يتم مقاطعته أبداً أثناء امتلاك القفلNever preempted while holding lock |
لماذا لا يستخدم ويندوز أقنعة المقاطعة (Interrupt Masks) في الأنظمة متعددة المعالجات؟ Why doesn't Windows use interrupt masks on multiprocessor systems?
لأن تعطيل المقاطعات على معالج واحد لا يمنع المعالجات الأخرى من الوصول إلى الذاكرة المشتركة، كما أن تعطيلها على جميع المعالجات يستهلك وقتاً طويلاً ويقلل من كفاءة النظام.
Because disabling interrupts on one processor does not prevent other processors from accessing shared memory, and disabling them across all processors is time-consuming and degrades system performance.