I. Processes and Threads
 A. Process (recall the definition)
------------------------------------------
           RECALL: PROCESS

def: a *process* (or task) in an OS
    is a program that is being run

Characteristics:
 - is active (running or waiting to run)
 - has its own memory
     PAS = Process Address Space
 - has various permissions

------------------------------------------
 B. Threads
  1. Use case: servers
------------------------------------------
WRITING A SERVER: USE CASE FOR PARALLELISM

Want a server that can:

  - handle multiple asynchronous requests
    from many clients
  - access shared data
  - reserve virtual resources for clients
     e.g., airline seats

How to do that?



------------------------------------------
  2. Supporting Parallelism
------------------------------------------
        HOW TO SUPPORT PARALLELISM?

Modern computers have many Cores + GPUs...

How to write programs that use them?

  - Several processes,
      each uses a separate core, but:




Goals:
  - parallel execution
  - share memory
  - low overheads for:




------------------------------------------
------------------------------------------
            THREADS

def: a *thread* is a unit of parallel
     execution in a process

Characteristics:





------------------------------------------
 C. Sharing data safely
------------------------------------------
           CONCURRENCY

Apparent concurrency:

   - threads that execute by
      interleaving instructions
      (sharing a core,
      timesharing simulating parallelism)

True concurrency

   - threads that execute simultaneously
      multiple instructions
      at the same time
      (multiple cores, parallelism)

------------------------------------------
  1. Race conditions
------------------------------------------
           RACE CONDITIONS

Imagine 2 threads, T1 and T2
that share a global int variable k
and both execute:

     k = k + 1;

How is this compiled?




What does the hardware do?




------------------------------------------
       Does each thread have its own stack (or registers)?
------------------------------------------
           POSSIBLE EXECUTIONS

      global k: 0

T1                  T2
 k_1: 0              k_2: 0
 o_1: 1              o_2: 1
 r_1: 1              r_2: 1
 (writes r_1)        (waiting...)
      global k: 1
                     (writes r_2)
      global k: 1


T1                  T2
 k_1: 0              (waiting ...)
 o_1: 1             
 r_1: 1             
 (writes r_1)       
      global k: 1
                     k_2: 1
                     o_2: 1
                     r_2: 2
                     (writes r_2)
      global k: 2

------------------------------------------
        Is there any other way the final value of k could be 2?
        Is there any other way the final value of k could be 1?
        What could happen if the shared variable was a double?
        What could happen if the shared memory was an array?
------------------------------------------
           POSSIBLE EXECUTIONS

Suppose int a[2] is a global,
  initially a[0] == 0 and a[1] == 0
and T1 and T2 both execute:

 a[0] = a[0]+4; a[1] = a[1]+3;

T1                  T2
 a0_1: 0             a0_2: 0
 f_1: 4              f_2: 4
 r0_1: 4             r0_2: 4
 (writes r0_1)       (waiting...)
      a[0]: 4 a[1]: 0
                     (writes r0_2)
      a[0]: 4 a[1]: 0
 a1_1: 0             a1_2: 0
 t_1: 3              t_2: 3
 r1_1: 3             r1_2: 3
 (writes r1_1)       (waiting...)
      a[0]: 4 a[1]: 3
                     (writes r1_2)
      a[0]: 4 a[1]: 3

T1                  T2
 a0_1: 0              (waiting ...)
 f_1: 4             
 r0_1: 4             
 (writes r0_1)       
      a[0]: 4 a[1]: 0
                     a0_2: 4
                     f_2: 4
                     r0_2: 8
                     (writes r0_2)
      a[0]: 8 a[1]: 0
      ...
------------------------------------------
        What possible results can appear in a[0]?
        What possible results can appear in a[1]?
        So how many possible end states are there?
------------------------------------------
            RACE CONDITIONS

def: a *race condition* occurs when




def: a *critical section* is an area of
     code in which a



def: *mutual exclusion* is a technique
     that


------------------------------------------
  2. safe synchronization
   a. Goal
       Do we want race conditions to occur?
       Why?
------------------------------------------
    GOALS OF SYNCHRONIZATION MECHANISMS

def: a *serial execution* is an execution
     equivalent to

def: an execution is *atomic* iff


Goals: Allow programmers to:



------------------------------------------
  3. techniques for safe synchronization
------------------------------------------
     SAFE SYNCHRONIZATION MECHANISMS

Locking:






Monitors:





------------------------------------------
------------------------------------------
         LOW-LEVEL IMPLEMENTATION

How to implement locks?

In hardware:
   atomic
     test-and-set or compare-and-swap
   instructions


In an OS
   disable interrupts to do atomic actions
------------------------------------------