Mutual Exclusion and Synchronizationالاستبعاد المتبادل والتزامن
مقدمة الفصل
ماذا ستتعلم في هذا الفصل
- Principles of concurrency: key terms, race conditions, process interaction, the requirements for mutual exclusion.
- Mutual exclusion with hardware support: disabling interrupts and special machine instructions.
- Semaphores: primitives, binary semaphores, strong/weak semaphores, the producer/consumer problem.
- Monitors: characteristics and synchronization with condition variables.
أقسام الفصل
- 1Multiple processes and concurrencyالعمليات المتعددة والتزامن
- 2Key terms related to concurrencyمصطلحات أساسية في التزامن
- 3Race condition and enforcing single accessحالة السباق وفرض الوصول المنفرد
- 4Process interaction and competitionتفاعل العمليات والتنافس
- 5Requirements for mutual exclusionمتطلبات الاستبعاد المتبادل
- 6Mutual exclusion: hardware supportالاستبعاد المتبادل بدعم العتاد
- 7Semaphoresالسيمافورات
- 8The producer/consumer problemمشكلة المنتج والمستهلك
- 9Monitorsالمراقبات (Monitors)
تلميح: استخدم أسهم لوحة المفاتيح للتنقل بين الشرائح.
Concurrencyالتزامن
- Managing multiple processes — multiprogramming, multiprocessing, distributed processing — is central to modern OS design; the big issue is concurrency: managing their interaction.
- Processes may be interleaved on uniprocessors and overlapped on multiprocessors (slides 6–7).
- Difficulties: sharing of global resources; optimally managing the allocation of resources; programming errors are hard to locate because results are not deterministic and reproducible (slide 8).
Key terms related to concurrencyالمصطلحات الأساسية
تذكّر التعريف قبل الكشف.
- Atomic operation
A sequence of one or more instructions that appears to be indivisible; it executes as a group, or not at all — atomicity guarantees isolation from concurrent processes.
- Critical section
Code within a process that requires access to shared resources and must not be executed while another process is in a corresponding section of code.
- Deadlock
Two or more processes are unable to proceed because each is waiting for one of the others to do something.
- Livelock
Two or more processes continuously change their states in response to changes in the other process(es) without doing any useful work.
- Mutual exclusion
When one process is in a critical section that accesses shared resources, no other process may be in a critical section that accesses any of those shared resources.
- Race condition
Multiple threads or processes read and write a shared data item and the final result depends on the relative timing of their execution.
- Starvation
A runnable process is overlooked indefinitely by the scheduler; although it is able to proceed, it is never chosen.
Race conditionحالة السباق
Multiple processes or threads read and write data items in a way where the final result depends on the order of execution of the processes. The output depends on who finishes the race last.
Enforcing single access to echo (slide 9)
- 1
P1 and P2 run on separate processors; P1 enters echo first.
- 2
P2 tries to enter but is blocked — P2 suspends.
- 3
P1 completes execution.
- 4
P2 resumes and executes echo.
Process interactionتفاعل العمليات
| Degree of awarenessدرجة الإدراك | Relationshipالعلاقة | Potential control problemsمشكلات التحكم المحتملة |
|---|---|---|
| Processes unaware of each other | Competition |
|
| Processes indirectly aware of each other (e.g., shared object) | Cooperation by sharing |
|
| Processes directly aware of each other (have communication primitives available to them) | Cooperation by communication |
|
Competition among processes for resources — three main control problems (slide 12)
- 1. Need for mutual exclusion (critical sections)
- 2. Deadlock
- 3. Starvation
Requirements for mutual exclusionمتطلبات الاستبعاد
- 1Only one process at a time is allowed in the critical section for a resource
- 2A process that halts in its noncritical section must do so without interfering with other processes
- 3No deadlock or starvation
- 4A process must not be delayed access to a critical section when there is no other process using it
- 5No assumptions are made about relative process speeds or number of processes
- 6A process remains inside its critical section for a finite time only
Disabling interruptsتعطيل المقاطعات
Mutual exclusion: hardware support
- Uniprocessors only allow interleaving; a process runs until it invokes an OS service or until it is interrupted.
- Disabling interrupts guarantees mutual exclusion.
- It will not work in a multiprocessor architecture.
Pseudo-code (slide 17), repeated while (true)
- 1
Disable interrupts
- 2
Critical section
- 3
Enable interrupts
- 4
Remainder
Special machine instructionsالتعليمات الخاصة
Mutual exclusion: hardware support
- Compare&Swap instruction — also called a "compare and exchange instruction".
- Exchange instruction.
Advantages (slide 19)المزايا
- Applicable to any number of processes on a single processor or multiple processors sharing main memory
- Simple and therefore easy to verify
- Can support multiple critical sections
Disadvantages (slide 20)العيوب
- Busy-waiting consumes processor time
- Starvation is possible when a process leaves a critical section and more than one process is waiting
- Deadlock is possible
Semaphoresالسيمافورات
An integer value used for signalling among processes. Only three operations may be performed on it, all atomic: initialize, decrement (semWait), increment (semSignal).
semWait(s)
- s.count--
- if (s.count < 0): place this process in s.queue and block this process
semSignal(s)
- s.count++
- if (s.count <= 0): remove a process P from s.queue and place P on the ready list
Binary, strong and weak semaphoresأنواع السيمافور
semWaitB(s)
- if (s.value == one): s.value = zero
- else: place this process in s.queue; block this process
semSignalB(s)
- if (s.queue is empty()): s.value = one
- else: remove a process P from s.queue; place P on the ready list
Processes waiting on the semaphore are removed from the queue in FIFO order.
Doesn't specify the order of removal from the queue.
| Step | Processor | Semaphore | Blocked queue | Ready queue |
|---|---|---|---|---|
| 1 | A | s = 1 | (empty) | C D B |
| 2 | B | s = 0 | (empty) | A C D |
| 3 | D | s = −1 | B | A C |
| 4 | D | s = 0 | (empty) | B A C |
| 5 | C | s = 0 | (empty) | D B A |
| 6 | D | s = −3 | B A C | (empty) |
| 7 | D | s = −2 | B A | C |
| Event | Queue for semaphore lock | Value of lock |
|---|---|---|
| (start) | (empty) | 1 |
| A: semWait(lock) — A enters its critical region | (empty) | 0 |
| B: semWait(lock) — B blocks | B | −1 |
| C: semWait(lock) — C blocks | C B | −2 |
| A: semSignal(lock) — B enters | C | −1 |
| B: semSignal(lock) — C enters | (empty) | 0 |
| C: semSignal(lock) | (empty) | 1 |
- Note that normal execution can proceed in parallel but that critical regions are serialized (slide 28).
Producer/consumer problemالمنتج والمستهلك
General situation
- One or more producers generate data and place it in a buffer.
- A single consumer takes items out of the buffer one at a time.
- Only one producer or consumer may access the buffer at any one time.
Ensure that the producer can't add data into a full buffer and the consumer can't remove data from an empty buffer.
Producer
- produce item v
- b[in] = v
- in++
Consumer
- while (in <= out) do nothing
- w = b[out]
- out++
- consume item w
Bounded bufferالمخزن المحدود
The producer/consumer problem
Producer
- produce item v
- while ((in + 1) % n == out) do nothing — buffer full
- b[in] = v
- in = (in + 1) % n
Consumer
- while (in == out) do nothing — buffer empty
- w = b[out]
- out = (out + 1) % n
- consume item w
Monitorsالمراقبات
A programming-language construct that provides equivalent functionality to that of semaphores and that is easier to control; implemented in Concurrent Pascal, Pascal-Plus, Modula-2, Modula-3, and Java.
Chief characteristics (slide 37)
- Local data variables are accessible only by the monitor.
- A process enters the monitor by invoking one of its procedures.
- Only one process may be executing in the monitor at a time.
Suspend execution of the calling process on condition c.
Resume execution of some process blocked after a cwait on the same condition.
الخلاصة
أنهيت الدرس
الخطوة التالية: ثبّت المعلومات بالبطاقات، ثم اختبر نفسك بالأسئلة.
ما راجعته في هذا الدرس
- Multiple processes and concurrencyالعمليات المتعددة والتزامن
- Key terms related to concurrencyمصطلحات أساسية في التزامن
- Race condition and enforcing single accessحالة السباق وفرض الوصول المنفرد
- Process interaction and competitionتفاعل العمليات والتنافس
- Requirements for mutual exclusionمتطلبات الاستبعاد المتبادل
- Mutual exclusion: hardware supportالاستبعاد المتبادل بدعم العتاد
- Semaphoresالسيمافورات
- The producer/consumer problemمشكلة المنتج والمستهلك
- Monitorsالمراقبات (Monitors)