Lecture Operating system principles - Chapter 5: Concurrency: Mutual exclusion and synchronization
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (495.32 KB, 42 trang )
Chapter 5
Concurrency: Mutual Exclusion and
Synchronization
•
•
•
•
Principals of Concurrency
Mutual Exclusion: Hardware Support
Semaphores
Readers/Writers Problem
1
Multiple Processes
• Central to the design of modern Operating
Systems is managing multiple processes
– Multiprogramming
– Multiprocessing
– Distributed Processing
• Big Issue is Concurrency
– Managing the interaction of all of these
processes
2
Interleaving and
Overlapping Processes
• Earlier (Ch2) we saw that processes may
be interleaved on uniprocessors
3
Interleaving and
Overlapping Processes
• And not only interleaved but overlapped on
multi-processors
• Both interleaving and overlapping present the
same problems in concurrent processing
4
One Difficulty of
Concurrency
• Sharing of global resources can be
problematic
5
A Simple Example
Suppose echo is a shared procedure
and P1 echoes ‘x’ and P2 echoes ‘y’
void echo()
{ // send a keyboard-input character to display
chin = getchar();
What would happen if P1 is
interrupted here by P2?
chout = chin;
putchar(chout);
}
What would happen if only one process is
permitted at a time to be in the
procedure?
6
A Simple Example:
On a Multiprocessor
Process P1
.
chin = getchar();
.
chout = chin;
putchar(chout);
.
.
Process P2
.
.
chin = getchar();
chout = chin;
.
putchar(chout);
.
7
Enforce Single Access
• If we enforce a rule that only one process may
enter the function at a time then:
– P1 & P2 run on separate processors
– P1 enters echo first,
• P2 tries to enter but is blocked
– P1 completes execution
• P2 resumes and executes echo
Solution: Control access
to shared resource
8
Competition among
Processes for Resources
Three main control problems:
• Need for Mutual Exclusion
– Only one program at a time be allowed in its
critical section.
– Critical resource: nonsharable resource,
e.g., printer
– Critical section: portion of the program that
uses a critical resource
• Deadlock
• Starvation
9
Requirements for
Mutual Exclusion
• Only one process at a time is allowed in
the critical section for a resource
• A process that halts in its noncritical
section must do so without interfering with
other processes
• No deadlock or starvation
10
Requirements for
Mutual Exclusion
• A process must not be delayed access to
a critical section when there is no other
process using it
• No assumptions are made about relative
process speeds or number of processes
• A process remains inside its critical section
for a finite time only
11
Roadmap
•
•
•
•
Principals of Concurrency
Mutual Exclusion: Hardware Support
Semaphores
Readers/Writers Problem
12
Disabling Interrupts
• Uniprocessors only allow interleaving
• Interrupt Disabling
– A process runs until it invokes an operating
system service or until it is interrupted
– Disabling interrupts guarantees mutual
exclusion because the critical section cannot
be interrupted
13
Pseudo-Code
while (true) {
/*
/*
/*
/*
disable interrupts */;
critical section */;
enable interrupts */;
remainder */;
}
– Reduced interleaving
– Will not work in multiprocessor architecture
14
Special Machine
Instructions
• Use of atomic action: instruction is treated
as a single step that cannot be interrupted
– Compare&Swap Instruction
int compare_and_swap (int *word,
int testval, int newval)
{ /* checks a memory location (*word) against a test value
(testval) */
int oldval;
oldval = *word;
if (oldval == testval) *word = newval;
return oldval;
}
15
Mutual Exclusion (fig 5.2)
• The only process
that may enter its
critical section is
one that finds bolt
equal to 0
• All other
processes go into
a busy waiting
mode
16
Hardware Mutual
Exclusion: 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
17
Hardware Mutual
Exclusion: Disadvantages
• Busy-waiting consumes processor time
• Starvation is possible when a process leaves a
critical section and more than one process is
waiting
– Some process could indefinitely be denied access
because selection of a waiting process is arbitrary
• Deadlock is possible
– Example: P1 enters its critical section and is then
preempted by higher priority P2 which will go into a
busy waiting loop
18
Roadmap
•
•
•
•
Principals of Concurrency
Mutual Exclusion: Hardware Support
Semaphores
Readers/Writers Problem
19
Semaphore
• Fundamental principle: Processes can
cooperate by means of simple signal such
that a process can be forced to stop at a
specified place until it has received a
specific signal.
20
Semaphore
• Semaphore:
– An integer value used for signalling among
processes
• Only three operations may be performed
on a semaphore, all of which are atomic:
– initialize (to a nonnegative integer value)
– decrement (semWait), to receive a signal
– increment (semSignal), to transmit a signal
21
Semaphore Primitives
22
Binary Semaphore
Primitives
23
Strong/Weak
Semaphore
• A queue is used to hold processes waiting
on the semaphore
– In what order are processes removed from the
queue?
• Strong Semaphores use FIFO
• Weak Semaphores don’t specify the
order of removal from the queue
24
Mutual Exclusion Using
Semaphores
1. The first process that executes a
semWait will be able to enter the
critical section immediately,
setting the value of s to 0
2. Any other processes attempting
to enter the critical section will
find it busy and will be blocked
25
