Concurrency

So far, we have discussed what and how OS deals with…

• Expand a single CPU into multiple virtualized CPUs so that many programs run at the same time.
• Makes each process looks like it has its own independent memory (virtualized).

Through the concept “address space” each program acts like it has its own memory, but OS uses the physical memory by switching the multipe address space.

The difference between thread and process is that

• threads share the memory space –> can access the same value.

Thread:

• Each thread state is very similar to process states
• has PC, and registers
• If two threads run under one process, threads must be switched by the context switch.
  • Context switch of threads is similar to processes’
  • As like process control block (PCB), there is thread control block (TCB).
  • The biggest difference is that thread does not change the memory space (keep use the current page table).

• A single thread process has one stack at the bottom.
• In a multi thread process, each thread runs independently and mulitple routines can be called to run the thread. Hence, each thread has a stack.

Concurrency Problems

Race Condition: Situation where the output changes depends on the order of instruction executions.

• In case the context switch triggered in the unfortunate timing, wrong (not what we expected) output comes out.
  • It is indeed indeterminate.
• Critical section: where the multiple threads should not be executed
  • Therefore, we need mutex.
• Waiting for another: Dependency where order must be followed.

Concurreny must be dealt carefully so that most of kernel data structures, page table, process list, and file system… can work correctly.

Thread API

Thread Creation

1
2
3
4
5

pthread_create(thread, attr, routine, arg);
// thread:type struct pointer. This struct communicates with thread.
// attr: size of stack, thread scheduling priority - most time NULL is enough
// routine: a function that thread will run
// arg: input parameters delivered to the routine.

Thread Exit

1
2
3

pthread_join (thread, **value_ptr);
// thread: Which thread are you watiting for?
// value_ptr: pthread_join changes the value, hence need the pointer instead of val

• Key Points
  • Can deliver NULL when no parameter is needed
  • Do not need to bind the parameters when only one is needed
  • Needs to care about how the value changes within the thread.

Lock

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

pthread_mutex_t lock = pthread_mutex_initializer;
pthread_cond_t cond = pthread_cond_initializer;
int rc = pthread_mutex_init (&lock, NULL);
assert (rc == 0);
pthread_mutex_lock (&lock); // Wait if one thread has the lock
while (ready == 0) pthread_cond_wait (&cond, &lock); // Waiting routine
// It awake, get the lock, and return -> Ensures it always has the lock when executing.
x = x + 1; // Critical points
pthread_mutex_unlock (&lock);

// Other thread gives the wake up call
pthread_mutex_lock(&lock);
// After send the signal, and fix the ready val, it must have the lock
// It guarantees the prevention of race condition.
ready = 1; 
pthread_cond_signal (&cond); // It release the lock and send the signal to awake the thread.
pthread_mutex_unlock (&lock);