SOFTWARE OPTIMIZATION TECHNIQUES - Software Design for Six-Sigma: A Roadmap for Excellence - page 455

assume that every instruction takes the same number of clock cycles. However, even
ignoring cache effects, this technique is unrealistic for several reasons. First, not
all instructions take the same amount of time. Second, it is important to note that
execution times of instructions are not independent. This means that the execution
time of one instruction depends on the instructions around it. For example, many
CPUs use register bypassing to speed up instruction sequences when the result of
one instruction is used in the next instruction. As a result, the execution time of
an instruction may depend on whether its destination register is used as a source
for the next operation. Third, the execution time of an instruction may depend on
operand values. This is true of floating-point instructions in which a different number
of iterations may be required to calculate the result. The first two problems can be
addressed more easily than the third.

17.5 SYNCHRONIZATION AND DEADLOCK HANDLING

To ensure the orderly execution of processes, jobs should not get stuck in a deadlock,
forever waiting for each other (Sobh & Tibrewal, 2006). Synchronization problems
develop because sections of code that constitutes the critical sections overlap and
do not run atomically. A critical section of code is a part of a process that accesses
shared resources. Two processes should not enter their critical sections at the same
time. Synchronization can be implemented by using semaphores, monitors, and
message passing.
Semaphores are either locked or unlocked. When locked, a queue of tasks wait
for the semaphore. Problems with semaphore designs are priority inversion and
deadlocks. 31 In priority inversion, a high-priority task waits because a low-priority
task has a semaphore. A typical solution is to have the task that has a semaphore
run at the priority of the highest waiting task. Another solution is to have tasks send
messages to each other. These have exactly the same problems, as priority inversion
occurs when a task is working on a low-priority message and ignores a higher priority
message in its inbox. Deadlocks happen when two tasks wait for the other to respond.
Although their real-time behavior is less crisp than semaphore systems, message-
based systems are generally better behaved than semaphore systems. Figure 17.5
shows a comparison between the three synchronization methods (Sobh & Tibrewal,
2006).
A set of processes or threads is deadlocked when each process or thread is waiting
for a resource to be freed that is controlled by another process. 32

For deadlock to

occur, four separate conditions must be met. They are:

1. Mutual exclusion
2. Circular wait

31 http://www.webcomtechnologiesusa.com/embeddedeng.htm
32 http://www.cs.rpi.edu/academics/courses/fall04/os/c10/index.html