Skip to content

GitLab

Open
Created by John Zhang@u5157779Developer

Mechanisms to support thread synchronisation primitives (including blocking locks)

Created by: wks

In a multi-threaded environment, threads may need to wait for the availability of mutually exclusive resources or asynchronous events. Blocking locks are provided by many programming languages and operating systems as primitives to facilitate threaded programming.

Characteristics of the µVM prevents directly adopting pThread Mutexes.

  1. Dolan et al implemented efficient blocking locks in an environment with green threads implemented with SWAP-STACK. When there is only one native thread, atomic and ordered memory access is not necessary. Even there are multiple native threads, locks can still be implemented with merely an integer, atomic memory operations and a lock-free waiting queue.
  2. There may not always be a one-to-one mapping between language-level threads and native threads. (SWAP-STACK-based green threads is one example) The client may also implement m-to-n relationship where logical threads can be scheduled on any native thread. Re-entrant locks are based on the logical notation of "thread", which may not be native threads. However, pThread recursive mutexes depends on native threads.
  3. Spin locks can be implemented using only integers and atomic memory accesses.
  4. System calls are expensive.

The proposal

The µVM only needs to provide two primitives: SUSPEND and RESUME

  • SUSPEND: suspend the current thread. The thread blocks, but the state of the underlying stack is still ACTIVE.
  • RESUME: resume a given thread if it is waiting.

Note: more commonly known as PARK, UNPARK

On Linux, futex provides these two primitives, except the Linux kernel maintains an internal waiting queue. Their WAIT and WAKE are address-based (the address of the lock) rather than thread-based (Which thread should suspend/resume?). The above two primitives can be implemented on top of futex.

We still need to find equivalent counterparts on OSX, Windows and other operating systems. Using pThread mutex for waiting is also an option, albeit expensive. (On Linux, glibc implements pThread mutexes using a mixture of user-level fast paths and the futex)

proof of concept

It still needs to be shown (by code) whether these two primitives are sufficient.

yield points

How to suspend another thread? Who inserts yield points where threads can be suspend, the client or the µVM?