On threading.

Add: read/write lock, spinlocks, valgrind stuff, read ntpl source code (implementation details), Pthread and MPI, NUMA

Question: linux kernel version, old LinuxThreads or NPTL compiler, MPIAND threads?

The OpenGroup specs for threads (and other.)

LinuxThreads -vs- NTPL:

LinuxThreads:

Some documentation here

There's a manager thread (handles thread creation/destruction, fatal signals, memory management (allocated stack, thread local data, etc...), waiting on dead threads.

Synchronization primitives with signals (spurious wake-ups, pressure to the kernel signal system.) Broken SIGSTOP/SIGCONT implementation (ctrl-Z doesn't work) Limits on number of threads.

Reliance on manager thread imposes performance penalties: because of
serialization of creation/deletion, monopolization of one CPU,increases context switching.

List of all thread is maintained, to implement pthread_key_delete for instance. /proc clutter.

NTPL:

Correct implementation POSIX signal handling in the kernel solves fatal signal handling issues.

Kernel can do thread memory deallocation. Kernel can reap terminated threads.

Thread specific data and local storage are managed through generation counters.

Synchronizations primitives are implemented with futexes. (which can be placed in shared memory, so that PTHREAD_PROCESS_SHARED can be implemented (mutex shared between threads belonging to separate processes))

Thread local storage and thread data structures are merged in one block and placed on the stack. Stack frames can be cached for thread creation/deletion performances (stack frame unmap are costly depending on the architecture)

Required kernel support:

• Arbitrary thread specific data areas support
  
  
• Extension of clone to optimize thread creation and facilitate termination (no manager thread required.)
  
  
• POSIX signal handling for multi-threaded processes, fatal signal terminate entire process. Stop/continue affects entire process (ctrl-Z works)
  
  
• exit_group syscall added.
  
  
• And more...
  

There's a testing effort ongoing: see results here. It's based on the POSIX test suite.

There are scalability limits that started to get documented

1-on-1 -vs- M-on-N

Kernel threads are used (pure user-level implementation makes multi-processor use impossible.) M-on-N schdules M user threads on N kernel threads: two schedulers at work, need cooperation. Doesn't fit well on Linux (user level context switch often requires copy of register content from kernel space.) O(1) scheduler negates advantage of user level scheduler. Overhead cost. Simplifies signal delivery.

Message queues:

Inter process message exchange.

• mq_open create a message Q. It's identified by a filename path starting with / (no directories allowed,) features R/W/RW priviledges. Attributes (mq_maxmsg and mq_msgsize) can be specified if privlegdes for the given message queue are
  granted (permission are resolved on name as for file access.)
  

• mq_send sends a message to a message Q. The priority argument determines where the message is inserted in the Q. When the Q is full, the caller blocks (unless O_NONBLOCK) If several threads a blocking, the highest priority one is awaken to send the message.
  

• mq_notify subscribe to message notification. A struct sigevent argument specifies how to be notified (and how the poster will be notified of the IO completion ?)
  

• mq_receive receives the oldest message of the highest priority. Same blocking policy than for mg_send.
  
  

• Attributes: mq_maxmsg, mq_msgsize, mq_curmsgs and mq_flags (O_NONBLOCK)
  

Initialization:

pthread_once: Argument pthread_once_t is initialized to PTHREAD_ONCE_INIT and the function is called with a function pointer to execute. Subsequent call won't do anything as the value in pthread_once_t is modified to mark that the initialization happened.

Thread Specific Data:

Can be viewed as a thread private array of PTHREAD_KEYS_MAX void * addressed by keys. Keys are common to all threads, but values are private. TSDs are disposed of when cancelling or exiting a thread.

• pthread_key_create allocates a new key (whose value is returned through a parameter) and set the initial value to NULL. A destructor can be attached to the key for destruction at cancellation or exit. The destructor doesn't run if the associated value is NULL, but associates NULL to the value it's destroying.
  

• pthread_key_delete deallocate a TSD key, but doesn't run the destructor and doesn't care about the deallocated value.
  

This is the old way of doing things. Nowadays, we let the compiler handle things by using the __thread keyword.

Synchronization:

Mutexes

Mutexes shouldn't be called from signal handler (not async signal safe.) Mutex functions aren't cancellation point (don't hold mutexes for long when cancellation is deferred.)

Two states: unlocked (not owned), locked (owned by one thread.) Acquiring an owned thread will make the thread block.

• pthread_mutexattr_init: Initialize a mutex with attributes (mutex kind determines what happen for pthread_mutex_lock on already owned mutex: PTHREAD_MUTEX_FAST_NP suspends calling thread for ever, PTHREAD_MUTEX_RECURSIVE_NP returns immediately with success code, number of time thread owning the mutex is recorded and must be matched by number of pthread_mutex_unlock; PTHREAD_MUTEX_ERRORCHECK_NP returns with error code EDEADLK.)
  
• pthread_mutex_lock: if unlocked, the mutex is set in the lock state and to belong to a thread. If locked, depends on fast, recursive and error check mutex kind.
  
• pthread_mutex_trylock: just like pthread_mutex_lock but return EBUSY if mutex is owned.
  
• pthread_mutex_unlock: fast mutexes are returned to the unlock state, recursive mutexes have their reference count decremented and the mutex unlocked when count reaches 0, error checking mutexes are checked for lock state and owning thread appurtenance (error code may be returned.) Fast and recursive mutexes can be unlocked by non owner. This is not a portable behavior.
  
• PTHREAD_MUTEX_INITIALIZER, PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP, PTHREAD_ERRORCHECK_MUTEX_INITIALIZER_NP: Static initialization macros.

• pthread_mutexattr_destroy does nothing for Linux except check that the mutex is unlocked.

• pthread_mutexattr_{set,get}type set/query mutex kind attribute.
  

Condition variable (condition)

Additional info here. Conditionals are implemented with FUTEXES (wait queues).

Mutexes control access to data. Condition variables provide synchronization on data value, without resorting to polling. Mutexes are required to work with condition, because of race conditions (to avoid a thread signaling a condition before and other thread can wait on it.)

• pthread_cond_init: There are no condition attributes supported on Linux implementation. Static initialization through PTHREAD_COND_INITIALIZER
  
• pthread_cond_wait: atomically unlocks the associated mutex, and waits on a condition. pthread_cond_timedwait add a timeout (And a may set ETIMEDOUT)

• pthread_cond_signal: restart one waiting thread that a condition has been met. pthread_cond_broadcast restart all waiting threads (thundering herd problem/scheduler trashing prone.) When thread is restarted, associated mutex is automatically and atomically locked again.

• pthread_cond_destroy: destroy ressources used by condition. Does nothing on linux except check that no thread waits on cond
  

Semaphores

Semaphores are counters for ressources shared between threads. They are incremented/decrement atomically.

• sem_init initializes a semaphore with an initial value. Semaphores can be shared amongst processes (LinuxThreads doesn't support this.)
  

• sem_wait suspend calling thread until values as a non zero count, then decreases the semaphore count. It is signal safe (the only POSIX synchronization function that is, LinuxThread implementation isn't) sem_trywait is the non blocking variant (EAGAIN returned if count is zero.) This is the P operation.
  

• sem_post Atomically increases the count of the semaphore and never blocks (this is the V operation)
  

• sem_getvalue gets the current count of a semaphore.
  

• sem_destroy releases ressources allocated for a semaphore. For LinuxThreads, just check that no thread is waiting on the semaphore.
  

  consumer:
loop:
  P ();  ; Mutex initialized to 0, consumer blocks
  consume;
  goto loop;

producer:
loop:
  produce;
  V ();  ; 0 Initialized mutex brought to 1, consumer awakens
  goto loop;

Barrier

Barriers set the number of threads that must reach a barrier before all of them can be allowed to continue.

• pthread_barrier_init Initializes a barrier with a count number.

• pthread_barrier_wait Thread blocks until the required number of threads have reached the specified barrier.
  

Thread management:

pthread_cancel:

Sends cancellation to thread. Receiving thread can ignore the request, honor it right away or defer until the next cancellation point. Receiving thread exits as if pthread_exit(PTHREAD_CANCELED) had been called.

• pthread_setcancelstate sets either THREAD_CANCEL_{ENABLE,DISABLE}
  

• pthread_setcanceltype sets PTHREAD_CANCEL_ASYNCHRONOUS (as soon as cancellation request is received), PTHREAD_CANCEL_DEFERRED (next cancellation point.
  

When cancelling: execution of cleanup handlers (reverse order, LIFO), finalization for thread specific data and return PTHREAD_CANCELED.

pthread_cleanup_{push,pop,push_defer_np,pop_restore_np}:

Manages cleanup handlers:

• pthread_cleanup_push: install a cleanup handler, called when thread terminate (cancel or exit.) LIFO.
  
• pthread_cleanup_pop: remove last cleanup handler, with possibility of executing it.
  
  Note: these matching pairs should be in the same block/function (they're macros and introduce a {/} sequence.
  
• pthread_cleanup_{push_defer,pop_restore}_np Non portable extension (set PTHREAD_CANCEL_DEFERRED, push cleanup handler. pop cleanup handler (with possible execution) and restore cancellation type.
  

Cancellation Points

In general, any function that might suspend the execution of a thread for a long time, should be a cancellation point. In practice: depends on the implementation and how POSIX it is. Cancellation point can be explicit or implicit.

• pthread_testcancel: tests for a pending cancellation, effectively establishing a cancellation point.

• pthread_cond_{timed}wait, pthread_join, sigwait and sem_wait.

• All other syscalls that cause a process to block: read, select, wait and whatever in the libC uses them.
  

Thread linux special:

pthread_atfork:

Due to implementation limitation: fork on a threaded application duplicate the currently running thread but not others. Mutexes are duplicated in their current state, this gives us a chance to set things straight.

Thread attributes:

detachstate:

• PTHREAD_CREATE_JOINABLE: thread termination synchronization possible through pthread_join (termination code available.) Allocated thread ressources reclaimed after join.
  
  
• PTHREAD_CREATE_DETACHED: no join synchronization, ressources reclaimed when thread terminates.
  
  
• pthread_detach can force PTHREAD_CREATE_DETACHED


schedpolicy:

• SCHED_OTHER, SCHED_RR, SCHED_FIFO (both require super user priviledge.)
  
  
• pthread_setschedparam can change schedpolicy on running thread.


schedparam:

• Set priority value for SCHED_RR, SCHED_FIFO scheduling policy, withing sched_get_priority_{min,max} range (range depending on the policy), usually 0 or 1 to 99.
  

inheritsched:

• PTHREAD_EXPLICIT_SCHED: scheduling policy for newly created thread determined by schedpolicy and schedparam.
  
  
• PTHREAD_INHERIT_SCHED: inherited by parent thread.
  

scope:

• PTHREAD_SCOPE_SYSTEM: threads contend for CPU time with all other processes runing on the machine (thread priorities are interpreted relatives to other processes priorities.)
  

• PTHREAD_SCOPE_PROCESS: contention occurs with other threads of the running process. No supported on Linux.
  

Default attribute values

Attribute	Value
Threads
detachstate	PTHREAD_CREATE_JOINABLE
schedpolicy	SCHED_OTHER
schedparam	0
inheritsched	PTHREAD_EXPLICIT_SCHED
scope	PTHREAD_SCOPE_SYSTEM
Mutexes
mutex kind	PTHREAD_MUTEX_FAST_NP
Condition variables
cond_attr	Value ignored

Pitfalls:

Race conditions

Execution results depends on code execution order (code in different thread.) Circumvent with synchronization.

Deadlock

thread1 acquires a lock1, thread2 acquires lock2. thread1 blocks acquiring lock2 and thread2 blocks acquiring lock1. Thread1 can't unlock lock1 as its blocked on lock2, thread2 can't unlock lock2 as its blocked on lock1. Deadlock ensues.

Livelock

Two or more threads change they states in response to changes in other thread or threads, without doing any usefull work. Differ from a deadlock in that neither tread is blocked or waiting for anything.

Priority inversion

Low priority running thread synchronizes access to a ressource with high priority thread. When high priority thread runs, it can't because low priority hasn't released the ressource. This give a chance for a medium priority tasks to run, preventing low priority tasks from running to release what blocks the high priority tasks. As a result, high priority tasks doesn't run when it should and what it controls doesn't happen.

Solution is:

• Priority inheritance: lower priority temporarily inherits higher priority of high priority thread that locks on its ressource, givin it a chance to run when medium priority would have ran. Requires OS help.
  

• Priority ceilings: associates a priority with each resource, transfered to the accessor of the resource + 1.
  

What's Linux specific

Document the NP stuff.

Does nothing:pthread_mutexattr_destroy, pthread_mutex_destroy

Error code

ESRCH is used for invalid thread scheduling parameter specification.