صفحه 1:
Concurrency: Mutual
Exclusion and
Synchronization
Chapter 5
صفحه 2:
| Mutual Exclusion:
____ Hardware Support
Interrupt Disabling
A process runs until it invokes an
operating-system service or until it is
interrupted
Disabling interrupts guarantees mutual
exclusion
Processor is limited in its ability to
interleave programs
Multiprocessing
disabling interrupts on one processor
will not guarantee mutual exclusion
صفحه 3:
| Mutual Exclusion:
____ Hardware Support
Special Machine Instructions
Performed in a single instruction
cycle
Not subject to interference from
other instructions
Reading and writing
Reading and testing
صفحه 4:
Mutual Exclusion:
Hardware Support |
Test and Set Instruction
boolean testset (int i) {
if (i == 0) {
i=1;
return true;
}
else {
return false;
صفحه 5:
Mutual Exclusion:
Hardware Support
Exchange Instruction
void exchange(int register,
int memory) {
int temp;
temp = memory;
memory = register;
register = temp;
صفحه 6:
| Mutual Exclusion
__ Machine Instructions
Advantages
Applicable to any number of
processes on either a single
processor or multiple processors
sharing main memory
It is simple and therefore easy to
verify
It can be used to support multiple
critical sections
صفحه 7:
| Mutual Exclusion
__ Machine Instructions
Disadvantages
Busy-waiting consumes processor time
Starvation is possible when a process
leaves a critical section and more than
one process is waiting.
Deadlock
If a low priority process has the critical
region and a higher priority process needs,
the higher priority process will obtain the
processor to wait for the critical region
صفحه 8:
| Producer with Circular
Buffer
producer:
|while (true) {
/* produce item v */
while ((in + 1) % n == out)
/* do nothing */;
b[in] =
= (in +1) 5
صفحه 9:
| Consumer with Circular
Buffer
consumer:
|/while (true) {
while (in == out)
/* do nothing */;
= b[out];
out = (out + 1) Sn
/* consume item w */
صفحه 10:
bin]
bia]
انا
أ
in
bia]
bi4]
(b)
bi3]
bi3]
b[2]
۱
out
bi2]
bil]
bil]
Figure 5.15 Finite Circular Buffer for the Producer/Consumer Problem
صفحه 11:
| Infinite Buffer
|
|
|
١
"Note: shaded area indicates portion of buffer that is occupied
Figure 5.11 Infinite Buffer for the Producer/Consumer Problem
صفحه 12:
| Problems with
| semaphores
| - Signal/wait are primitive operations
_ - Cannot impose discipline
** shared variables should not be
accessed outside a Critical
section
** Critical section should be
correctly
implemented
صفحه 13:
| Problems with
1
| semaphores
Process pO Process p1
Wait (mutex) Signal(mutex)
<CS> > 05 <
Signal (mutex) Wait (mutex)
** Ts this implementation of CS correct?
صفحه 14:
Monitors
Monitor is a software module
Chief characteristics
Local data variables are accessible
only by the monitor
Process enters monitor by
invoking one of its procedures
Only one process may be
executing in the monitor at a time
صفحه 15:
Monitors
| -- Implements data abstraction
** arbitrary operations cannot be
performed on monitor data
-- Implements encapsulation for
mutual
exclusion
** Only one process can be in the
monitor at any time
صفحه 16:
Monitors
| -- Provides condition variables for
synchronization of processes
condition notfull;
.. Cwait(notfull); -- Process is blocked
.. Csignal(notfull); -- A blocked
process
is activated
صفحه 17:
Bounded buffer Prod-Con
using Monitors
Prodcon: monitor
buffer[..] /* shared data */
nextin, nextout, count: ..
void Prod() /* Operations can
manipulate shared data*/
void Cons()
{nextin=0, ... } /* Initializations */
void (producer) {... }
void (consumer) {...}
void main()
{ Parbegin(producer, consumer) }
صفحه 18:
| Bounded buffer Prod-Con
| using Monitors
void produce() void consume()
| { While (count == N) { While (count==0)
| cwait(notfull);
cwait(notempty);
buffer[nextin]= ..
X=buffer[nextout]
nextin=nextin+1%N nextout=...
| count++ count--
csignal(notempty); csignal(notfull);
1
صفحه 19:
13
صفحه 20:
| Readers/Writers
| Problem
Any number of readers may
simultaneously read the file
Only one writer at a time may
write to the file
If a writer is writing to the file,
no reader may read it
