Concurrency

Concurrent Execution - Multiprocessor

Concurrent Execution - Single Processor

Preemption

• processors are generally assumed to be preemptable
• some other resources are not preemptable
  i.e., mutual exclusion must be enforced between users

Need for Mutual Exclusion - Example of Race

procedure A is
begin ...
   M := M + 1; ...
end A;

procedure B is
begin ...
   M := M - 1; ...
end B;

No Interleaving: Task A First

No Interleaving: Task B First

Parallel Exclusion

Even supposing the primitive memory fetch and store operations are atomic, the outcome depends on the particular interleaving of the operations.

If B Preempts A

If A Preempts B

Resource Example: Semaphores/Mutexes

• Lock operation
  • ``blocks'' caller until no other task is holding the lock
  • the caller proceeds when it is able to get the lock
• Unlock operation
  • releases the lock held by the caller
  • this may allow another task that is blocked on a Lock operation to proceed

Critical Section Protected by Lock/Unlock

procedure A is
begin ...
   Lock;
   M := M + 1;
   Unlock; ...
end A;

procedure B is
begin ...
   Lock;
   M := M - 1;
   Unlock; ...
end B;

With Locking/Unlocking

Other Examples of Non-Preemptable Resources

• tape drive
• printer
• modem
• region of RAM to hold program

Counting Semaphores

• Counting semaphores are used for keeping track of multi-unit resources.
• Semaphore object has a (non-negative) integer Value
• Wait operation:
  wait until Semaphore.Value is positive, then decrement it
• Post operation:
  increment Semaphore.Value
• These operations are atomic, meaning they are implemented in a way that prevents them from being interleaved.

Take a look at how locks are implemented in Linux, starting with the file spinlock.h, in /usr/src/linux-2.2.14/include/asm-i386.

For a more detailed commentary on the more subtle parts of the Linux spinlock implementation code click here.

Liu Notation and Terminology

• P_i is a processor
  not sharable, potentially preemptable
• R_i is a resource
  not sharable, not preemptable, serially reusable
• J_i is a job
• T_i is a task

Jobs

• r_i is its release time
• D_i is its relative deadline
• d_i is its absolute deadline
• (r_i, d_i] is its feasible interval
• [r^-_i, r⁺_i] is range of r_i
• e_i is (an upper bound on) its execution time
• [e^-_i, e⁺_i] is range of possible execution times
• a job may have hard or soft laxity type
• a job may be preemptable or nonpreemptable
• a job may require certain processors and resources

Tasks

• all the jobs of a task have identical parameters
• periodic tasks have the following additional parameters:
  • p_i is the period of a periodic task,
    i.e., the minimum inter-release interval
  • e_i is an upper bound on the execution times of all the jobs in the task
  • f_i is the phase, or release time of the first job in the task