أدوات المزامنة
دراسة مشكلة المنطقة الحرجة وحلولها البرمجية والعتادية، بما في ذلك أقفال Mutex والسيمافورات (Semaphores) لضمان مزامنة العمليات وتجنب حالات السباق.
Synchronization Tools
Study of the critical-section problem and its software and hardware solutions, including Mutex locks and Semaphores to ensure process synchronization and avoid race conditions.
أهداف التعلم
- وصف مشكلة المنطقة الحرجة وتوضيح حالة السباق (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 Race Condition & Critical Section Problem
حالة السباق تحدث عندما تصل عدة عمليات لبيانات مشتركة في نفس الوقت، وتعتمد النتيجة على ترتيب التنفيذ. المنطقة الحرجة هي جزء الكود الذي يتم فيه هذا التعديل.
A race condition occurs when multiple processes access shared data concurrently, and the outcome depends on execution order. The critical section is the code segment where this modification happens.
عندما تتنفذ العمليات بشكل متزامن، قد تتم مقاطعتها في أي وقت. إذا قامت عمليتان (مثل P0 و P1) بإنشاء عمليات أبناء وتعديل متغير مشترك مثل next_available_pid، فقد يتم تعيين نفس المعرف لعمليتين مختلفتين إذا لم تكن هناك آلية حماية. لحل هذه المشكلة، نقوم بتعريف المنطقة الحرجة (Critical Section). يجب أن تطلب كل عملية الإذن للدخول في قسم الدخول (entry section)، ثم تنفذ المنطقة الحرجة، وتغادر عبر قسم الخروج (exit section).
When processes execute concurrently, they may be interrupted at any time. If two processes (e.g., P0 and P1) create child processes and modify a shared variable like next_available_pid, the same PID could be assigned to two different processes without a protection mechanism. To solve this, we define the Critical Section. Each process must ask permission to enter in the entry section, execute the critical section, and leave via the exit section.
أي حل لمشكلة المنطقة الحرجة يجب أن يلبي ثلاثة شروط أساسية: 1. الاستبعاد المتبادل (Mutual Exclusion): لا يمكن لأكثر من عملية التواجد في المنطقة الحرجة في نفس الوقت. 2. التقدم (Progress): إذا كانت المنطقة الحرجة فارغة وهناك عمليات ترغب بالدخول، لا يمكن تأجيل اختيار العملية التالية إلى الأبد. 3. الانتظار المحدود (Bounded Waiting): يجب أن يكون هناك حد لعدد المرات التي يُسمح فيها للعمليات الأخرى بالدخول بعد أن تطلب عملية ما الدخول وقبل أن يُمنح لها الطلب.
Any solution to the critical section problem must satisfy three requirements: 1. Mutual Exclusion: No two processes can execute in their critical sections simultaneously. 2. Progress: If no process is in the critical section and some wish to enter, the selection cannot be postponed indefinitely. 3. Bounded Waiting: A bound must exist on the number of times other processes can enter after a process has made a request and before it is granted.
while (true) {
entry section
critical section
exit section
remainder section
}ماذا يحدث إذا تحقق شرط الاستبعاد المتبادل ولكن لم يتحقق شرط التقدم؟ What happens if Mutual Exclusion is satisfied but Progress is not?
قد يؤدي ذلك إلى حالة الجمود (Deadlock)، حيث لا توجد أي عملية في المنطقة الحرجة، ومع ذلك لا تستطيع أي عملية ترغب في الدخول أن تفعل ذلك لأن النظام لا يستطيع اتخاذ قرار بشأن من يدخل تالياً.
It could lead to a Deadlock. No process is in the critical section, yet processes waiting to enter cannot do so because the system cannot decide which process should enter next.
2 حل بيترسون
2 Peterson’s Solution
حل برمجي كلاسيكي لعمليتين يعتمد على متغيرين: turn (لمن الدور) ومصفوفة flag (من جاهز للدخول).
A classic software-based solution for two processes relying on two variables: turn (whose turn it is) and a flag array (who is ready to enter).
يفترض حل بيترسون أن تعليمات التحميل والتخزين (load and store) ذرية (لا يمكن مقاطعتها). تشارك العمليتان متغير int turn ومصفوفة boolean flag[2]. يشير turn إلى العملية التي لها الحق في الدخول، بينما يشير flag[i] = true إلى أن العملية Pi جاهزة للدخول. العملية تعلن عن رغبتها بالدخول بجعل علمها true، ثم تعطي الدور للعملية الأخرى بلطف (turn = j). وتنتظر في حلقة طالما أن العملية الأخرى جاهزة ولها الدور.
Peterson's solution assumes load and store machine-language instructions are atomic. The two processes share int turn and boolean flag[2]. turn indicates whose turn it is, while flag[i] = true implies process Pi is ready. A process sets its flag to true, politely gives the turn to the other process (turn = j), and waits in a while loop as long as the other process is ready and has the turn.
رغم أن هذا الحل يثبت رياضياً تلبية الشروط الثلاثة (الاستبعاد، التقدم، الانتظار المحدود)، إلا أنه غير مضمون العمل على المعماريات الحديثة. لتحسين الأداء، قد تقوم المعالجات أو المترجمات (compilers) بإعادة ترتيب العمليات (reordering) التي ليس بينها تبعيات. في بيئة متعددة الخيوط، يمكن أن يؤدي هذا الترتيب إلى نتائج غير متوقعة وفشل في الاستبعاد المتبادل.
Although provable that the three CS requirements are met, Peterson's Solution is not guaranteed to work on modern architectures. To improve performance, processors and/or compilers may reorder operations that have no dependencies. In a multithreaded environment, this reordering may produce inconsistent or unexpected results, breaking mutual exclusion.
while (true) {
flag[i] = true;
turn = j;
while (flag[j] && turn == j)
;
/* critical section */
flag[i] = false;
/* remainder section */
}لماذا تقوم العملية Pi بتعيين `turn = j` بدلاً من `turn = i`؟ Why does process Pi set `turn = j` instead of `turn = i`?
لضمان شرط التقدم والانتظار المحدود. بتعيين الدور للعملية الأخرى، تضمن Pi أنها لا تحتكر المنطقة الحرجة إذا كانت العملية الأخرى ترغب في الدخول أيضاً (تصرف مهذب).
To ensure Progress and Bounded Waiting. By giving the turn to the other process, Pi ensures it doesn't monopolize the critical section if the other process also wants to enter (polite behavior).
3 دعم العتاد للمزامنة
3 Synchronization Hardware
توفر الأنظمة تعليمات عتادية خاصة (مثل test_and_set و compare_and_swap) تُنفذ بشكل ذري لحماية المناطق الحرجة.
Systems provide special hardware instructions (like test_and_set and compare_and_swap) that execute atomically to protect critical sections.
في المعالجات الأحادية (Uniprocessors)، يمكن تعطيل المقاطعات لمنع التبديل بين العمليات، لكن هذا غير فعال وغير قابل للتوسع في المعالجات المتعددة. بدلاً من ذلك، نستخدم تعليمات عتادية ذرية. تعليمة test_and_set تقوم بقراءة القيمة الحالية لمتغير وتعيينها إلى true في خطوة واحدة غير قابلة للمقاطعة. كما تُستخدم المتغيرات الذرية (Atomic Variables) لتوفير تحديثات ذرية لأنواع البيانات الأساسية مثل الأعداد الصحيحة (مثل increment(&sequence)).
In uniprocessors, interrupts could be disabled to prevent preemption, but this is inefficient and not scalable on multiprocessor systems. Instead, we use atomic hardware instructions. The test_and_set instruction reads the current value of a variable and sets it to true in one uninterruptible step. Atomic variables are also used to provide atomic updates on basic data types like integers (e.g., increment(&sequence)).
استخدام test_and_set لحل مشكلة المنطقة الحرجة يعتمد على متغير قفل (lock) مهيأ بـ false. العملية تستمر في الدوران (while test_and_set(&lock)) طالما القفل true. بمجرد أن يصبح false، تعيده التعليمة إلى true وتسمح للعملية بالدخول. العيب الرئيسي هنا هو الانتظار النشط (Busy Waiting).
Using test_and_set to solve the CS problem relies on a boolean lock initialized to false. A process spins (while test_and_set(&lock)) as long as the lock is true. Once false, the instruction sets it to true and lets the process enter. The main drawback is Busy Waiting.
boolean test_and_set (boolean *target) {
boolean rv = *target;
*target = true;
return rv;
}
// Solution using test_and_set
do {
while (test_and_set(&lock))
; /* do nothing */
/* critical section */
lock = false;
/* remainder section */
} while (true);لماذا يعتبر تعطيل المقاطعات حلاً سيئاً في الأنظمة متعددة المعالجات؟ Why is disabling interrupts a bad solution in multiprocessor systems?
لأن تعطيل المقاطعات يجب أن يتم تمريره إلى جميع المعالجات، مما يستهلك وقتاً طويلاً ويقلل من كفاءة النظام بشكل كبير، ولا يمنع المعالجات الأخرى من الوصول للذاكرة المشتركة.
Because disabling interrupts must be passed to all processors, which is time-consuming, highly inefficient, and doesn't inherently prevent other processors from accessing shared memory.
4 أقفال الاستبعاد المتبادل (Mutex Locks)
4 Mutex Locks
أداة برمجية بسيطة لحماية المنطقة الحرجة باستخدام دالتي acquire() للحصول على القفل و release() لتحريره.
A simple software tool to protect critical sections using acquire() to get the lock and release() to free it.
بما أن الحلول السابقة معقدة للمبرمجين، يوفر نظام التشغيل أدوات جاهزة أبسطها قفل Mutex. يحتوي على متغير منطقي يشير إلى ما إذا كان القفل متاحاً أم لا. لحماية المنطقة الحرجة، تستدعي العملية acquire() قبل الدخول، و release() بعد الخروج. يجب أن تكون هذه الاستدعاءات ذرية (تُنفذ غالباً باستخدام تعليمات العتاد مثل compare-and-swap).
Since previous solutions are complicated for programmers, OS designers build software tools, the simplest being the Mutex lock. It uses a boolean variable indicating if the lock is available. To protect a critical section, a process calls acquire() before entering, and release() after exiting. These calls must be atomic (usually implemented via hardware atomic instructions like compare-and-swap).
هذا التنفيذ الأساسي يتطلب الانتظار النشط (Busy Waiting)، حيث تستمر العملية في فحص القفل في حلقة مفرغة، مما يهدر دورات المعالج. لذلك يُسمى هذا النوع من الأقفال بـ قفل الدوران (Spinlock). ميزته الوحيدة هي عدم وجود تبديل سياق (Context Switch)، مما يجعله مفيداً إذا كانت فترة الانتظار قصيرة جداً.
This basic implementation requires Busy Waiting, where the process continuously checks the lock in a loop, wasting CPU cycles. Therefore, this lock is called a Spinlock. Its only advantage is that no context switch is required, making it useful if the wait time is expected to be very short.
while (true) {
acquire lock
critical section
release lock
remainder section
}متى يكون استخدام Spinlock أفضل من الأقفال التي توقف العملية (Blocking)؟ When is using a Spinlock better than using blocking locks?
عندما تكون المنطقة الحرجة قصيرة جداً، بحيث يكون وقت الدوران (الانتظار النشط) أقل من الوقت المستغرق في إجراء تبديل السياق (Context Switch) لإيقاف العملية وإيقاظها لاحقاً.
When the critical section is very short, such that the time spent spinning is less than the overhead of performing a context switch to block and later wake up the process.
5 السيمافورات (Semaphores)
5 Semaphores
أداة مزامنة متقدمة تعتمد على متغير صحيح (Integer) يتم تعديله فقط عبر عمليتين ذريتين: wait() و signal().
An advanced synchronization tool based on an integer variable accessed only via two atomic operations: wait() and signal().
السيمافور S هو متغير صحيح. عملية wait(S) (أو P) تقوم بإنقاص القيمة إذا كانت أكبر من الصفر، وإلا تنتظر. عملية signal(S) (أو V) تقوم بزيادة القيمة. هناك نوعان: السيمافور العددي (Counting Semaphore) الذي يمكن أن يأخذ أي قيمة صحيحة ويُستخدم لإدارة موارد متعددة النسخ، والسيمافور الثنائي (Binary Semaphore) الذي يأخذ القيمتين 0 و 1 فقط ويعمل تماماً مثل قفل Mutex.
Semaphore S is an integer variable. The wait(S) (or P) operation decrements the value if > 0, else waits. The signal(S) (or V) operation increments it. There are two types: Counting Semaphore (unrestricted domain, used for multiple instances of a resource) and Binary Semaphore (values 0 and 1, behaves exactly like a Mutex lock).
لتجنب الانتظار النشط (Busy Waiting) في السيمافورات، يتم ربط طابور انتظار (Waiting Queue) بكل سيمافور. بدلاً من الدوران، تستخدم العملية دالة block() لوضع نفسها في طابور الانتظار وتنتقل لحالة الانتظار. عندما تقوم عملية أخرى بتنفيذ signal()، يتم استخدام دالة wakeup() لإزالة عملية من الطابور ونقلها إلى طابور الاستعداد (Ready Queue).
To avoid Busy Waiting, a waiting queue is associated with each semaphore. Instead of spinning, a process uses the block() operation to place itself in the queue and goes to a waiting state. When another process executes signal(), the wakeup() operation removes a process from the queue and places it in the ready queue.
wait(S) {
while (S <= 0)
; // busy wait
S--;
}
signal(S) {
S++;
}| Busy Waiting (Spinlock) | Blocking (Queue/Sleep) | |
|---|---|---|
| استهلاك المعالج (CPU) CPU Utilization | يهدر دورات المعالج في الدوران المستمر Wastes CPU cycles spinning | لا يستهلك المعالج أثناء الانتظار Does not consume CPU while waiting |
| تكلفة تبديل السياق (Context Switch) Context Switch Overhead | لا يوجد تبديل سياق (سريع جداً) No context switch (very fast) | يتطلب تبديل سياق مكلف (حفظ واسترجاع الحالة) Requires expensive context switch |
كيف يمكن استخدام السيمافور لضمان تنفيذ التعليمة S1 في العملية P1 قبل التعليمة S2 في العملية P2؟ How can a semaphore be used to ensure statement S1 in P1 executes before statement S2 in P2?
نقوم بإنشاء سيمافور 'synch' بقيمة ابتدائية 0. في P1 نكتب: S1; signal(synch); وفي P2 نكتب: wait(synch); S2; هكذا ستنتظر P2 حتى ترسل P1 الإشارة.
Create a semaphore 'synch' initialized to 0. In P1: S1; signal(synch); In P2: wait(synch); S2; This forces P2 to wait until P1 signals.