Interrupt Disabling
while (true) {
/* disable interrupts */;
/* critical section */;
/* enable interrupts */;
/* remainder */;
}
Because the critical section cannot be interrupted, mutual exclusion is guaranteed.
The price of this approach, however, is high. The efficiency of execution could
be noticeably degraded because the processor is limited in its ability to interleave
processes. A second problem is that this approach will not work in a multiprocessor
architecture. When the computer includes more than one processor, it is possible
for more than one process to be executing at a time. In this case, disabled
interrupts do not guarantee mutual exclusion.
Special Machine Instructions
In a multiprocessor configuration, several processors share access to a common
main memory. In this case, there is not a master/slave relationship; rather the processors
behave independently in a peer relationship. There is no interrupt mechanism
between processors on which mutual exclusion can be based.
At the hardware level, as was mentioned, access to a memory location excludes
any other access to that same location. With this as a foundation, processor
designers have proposed several machine instructions that carry out two actions
atomically, such as reading and writing or reading and testing, of a single memory
location with one instruction fetch cycle. During execution of the instruction, access
to the memory location is blocked for any other instruction referencing that
location.
Compare&Swap Instruction The compare&swap instruction, also called a
compare and exchange instruction
int compare_and_swap (int *word, int testval, int newval)
{
int oldval;
oldval = *word
if (oldval == testval) *word = newval;
return oldval;
}
This version of the instruction checks a memory location (*word) against a
test value (testval). If the memory location’s current value is testval, it is replaced
with newval; otherwise it is left unchanged. The old memory value is always returned;
thus, the memory location has been updated if the returned value is the
same as the test value. This atomic instruction therefore has two parts: A compare is
made between a memory value and a test value; if the values differ a swap occurs.
The entire compare&swap function is carried out atomically; that is, it is not subject
to interruption.
Another version of this instruction returns a Boolean value: true if the swap
occurred; false otherwise. Some version of this instruction is available on nearly all
processor families, and most operating systems use this
instruction for support of concurrency.
Properties of the Machine-Instruction Approach
mutual exclusion has a number of Advantages
It is 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; each critical section can be
defined by its own variable.
Disadvantages
Busy waiting is employed. Thus, while a process is waiting for access to a critical
section, it continues to consume processor time.
Starvation is possible. When a process leaves a critical section and more than
one process is waiting, the selection of a waiting process is arbitrary. Thus,
some process could indefinitely be denied access
Deadlock is possible. Consider the following scenario on a single-processor
system. Process P1 executes the special instruction and enters its critical section.
P1 is then interrupted to give the processor to P2, which has higher priority.
If P2 now attempts to use the same resource as P1, it will be denied access because of
the mutual exclusion mechanism. Thus it will go into a busy waiting loop. However,
P1 will never be dispatched because it is of lower priority than another ready process, P2.
In a uniprocessor system, concurrent processes cannot have overlapped execution;
they can only be interleaved. Furthermore, a process will continue to run until it invokes
an OS service or until it is interrupted. Therefore, to guarantee mutual exclusion,
it is sufficient to prevent a process from being interrupted. This capability can
be provided in the form of primitives defined by the OS kernel for disabling and enabling
interrupts. A process can then enforce mutual exclusion in the following way
while (true) {
/* disable interrupts */;
/* critical section */;
/* enable interrupts */;
/* remainder */;
}
Because the critical section cannot be interrupted, mutual exclusion is guaranteed.
The price of this approach, however, is high. The efficiency of execution could
be noticeably degraded because the processor is limited in its ability to interleave
processes. A second problem is that this approach will not work in a multiprocessor
architecture. When the computer includes more than one processor, it is possible
for more than one process to be executing at a time. In this case, disabled
interrupts do not guarantee mutual exclusion.
Special Machine Instructions
In a multiprocessor configuration, several processors share access to a common
main memory. In this case, there is not a master/slave relationship; rather the processors
behave independently in a peer relationship. There is no interrupt mechanism
between processors on which mutual exclusion can be based.
At the hardware level, as was mentioned, access to a memory location excludes
any other access to that same location. With this as a foundation, processor
designers have proposed several machine instructions that carry out two actions
atomically, such as reading and writing or reading and testing, of a single memory
location with one instruction fetch cycle. During execution of the instruction, access
to the memory location is blocked for any other instruction referencing that
location.
Compare&Swap Instruction The compare&swap instruction, also called a
compare and exchange instruction
int compare_and_swap (int *word, int testval, int newval)
{
int oldval;
oldval = *word
if (oldval == testval) *word = newval;
return oldval;
}
This version of the instruction checks a memory location (*word) against a
test value (testval). If the memory location’s current value is testval, it is replaced
with newval; otherwise it is left unchanged. The old memory value is always returned;
thus, the memory location has been updated if the returned value is the
same as the test value. This atomic instruction therefore has two parts: A compare is
made between a memory value and a test value; if the values differ a swap occurs.
The entire compare&swap function is carried out atomically; that is, it is not subject
to interruption.
Another version of this instruction returns a Boolean value: true if the swap
occurred; false otherwise. Some version of this instruction is available on nearly all
processor families, and most operating systems use this
instruction for support of concurrency.
Properties of the Machine-Instruction Approach
mutual exclusion has a number of Advantages
It is 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; each critical section can be
defined by its own variable.
Disadvantages
Busy waiting is employed. Thus, while a process is waiting for access to a critical
section, it continues to consume processor time.
Starvation is possible. When a process leaves a critical section and more than
one process is waiting, the selection of a waiting process is arbitrary. Thus,
some process could indefinitely be denied access
Deadlock is possible. Consider the following scenario on a single-processor
system. Process P1 executes the special instruction and enters its critical section.
P1 is then interrupted to give the processor to P2, which has higher priority.
If P2 now attempts to use the same resource as P1, it will be denied access because of
the mutual exclusion mechanism. Thus it will go into a busy waiting loop. However,
P1 will never be dispatched because it is of lower priority than another ready process, P2.
No comments:
Post a Comment