Index: uspace/lib/c/generic/fibril.c
===================================================================
--- uspace/lib/c/generic/fibril.c	(revision c45dc5e12e38a846a8628264b0aa9f4bb4afc04a)
+++ uspace/lib/c/generic/fibril.c	(revision c124c985b458abc83183812eb63cef12f08694dd)
@@ -344,4 +344,60 @@
 }
 
+static void _runner_fn(void *arg)
+{
+	futex_lock(&async_futex);
+	(void) fibril_switch(FIBRIL_FROM_BLOCKED);
+	__builtin_unreachable();
+}
+
+/**
+ * Spawn a given number of runners (i.e. OS threads) immediately, and
+ * unconditionally. This is meant to be used for tests and debugging.
+ * Regular programs should just use `fibril_enable_multithreaded()`.
+ *
+ * @param n  Number of runners to spawn.
+ * @return   Number of runners successfully spawned.
+ */
+int fibril_test_spawn_runners(int n)
+{
+	errno_t rc;
+
+	for (int i = 0; i < n; i++) {
+		thread_id_t tid;
+		rc = thread_create(_runner_fn, NULL, "fibril runner", &tid);
+		if (rc != EOK)
+			return i;
+		thread_detach(tid);
+	}
+
+	return n;
+}
+
+/**
+ * Opt-in to have more than one runner thread.
+ *
+ * Currently, a task only ever runs in one thread because multithreading
+ * might break some existing code.
+ *
+ * Eventually, the number of runner threads for a given task should become
+ * configurable in the environment and this function becomes no-op.
+ */
+void fibril_enable_multithreaded(void)
+{
+	// TODO: Implement better.
+	//       For now, 4 total runners is a sensible default.
+	fibril_test_spawn_runners(3);
+}
+
+/**
+ * Detach a fibril.
+ */
+void fibril_detach(fid_t f)
+{
+	// TODO: Currently all fibrils are detached by default, but they
+	//       won't always be. Code that explicitly spawns fibrils with
+	//       limited lifetime should call this function.
+}
+
 /** @}
  */
Index: uspace/lib/c/include/fibril.h
===================================================================
--- uspace/lib/c/include/fibril.h	(revision c45dc5e12e38a846a8628264b0aa9f4bb4afc04a)
+++ uspace/lib/c/include/fibril.h	(revision c124c985b458abc83183812eb63cef12f08694dd)
@@ -61,4 +61,9 @@
 extern void fibril_sleep(unsigned int);
 
+extern void fibril_enable_multithreaded(void);
+extern int fibril_test_spawn_runners(int);
+
+extern void fibril_detach(fid_t fid);
+
 static inline fid_t fibril_create(errno_t (*func)(void *), void *arg)
 {
Index: uspace/lib/c/include/fibril_synch.h
===================================================================
--- uspace/lib/c/include/fibril_synch.h	(revision c45dc5e12e38a846a8628264b0aa9f4bb4afc04a)
+++ uspace/lib/c/include/fibril_synch.h	(revision c124c985b458abc83183812eb63cef12f08694dd)
@@ -41,4 +41,63 @@
 #include <sys/time.h>
 #include <stdbool.h>
+#include <futex.h>
+
+/**
+ * "Restricted" fibril mutex.
+ *
+ * Similar to `fibril_mutex_t`, but has a set of restrictions placed on its
+ * use. Within a rmutex critical section, you
+ *         - may not use any other synchronization primitive,
+ *           save for another `fibril_rmutex_t`. This includes nonblocking
+ *           operations like cvar signal and mutex unlock.
+ *         - may not read IPC messages
+ *         - may not start a new thread/fibril
+ *           (creating fibril without starting is fine)
+ *
+ * Additionally, locking with a timeout is not possible on this mutex,
+ * and there is no associated condition variable type.
+ * This is a design constraint, not a lack of implementation effort.
+ */
+typedef struct {
+	// TODO: At this point, this is just silly handwaving to hide current
+	//       futex use behind a fibril based abstraction. Later, the imple-
+	//       mentation will change, but the restrictions placed on this type
+	//       will allow it to be simpler and faster than a regular mutex.
+	//       There might also be optional debug checking of the assumptions.
+	//
+	//       Note that a consequence of the restrictions is that if we are
+	//       running on a single thread, no other fibril can ever get to run
+	//       while a fibril has a rmutex locked. That means that for
+	//       single-threaded programs, we can reduce all rmutex locks and
+	//       unlocks to simple branches on a global bool variable.
+
+	futex_t futex;
+} fibril_rmutex_t;
+
+#define FIBRIL_RMUTEX_INITIALIZER(name) \
+	{ .futex = FUTEX_INITIALIZE(1) }
+
+#define FIBRIL_RMUTEX_INITIALIZE(name) \
+	fibril_rmutex_t name = FIBRIL_RMUTEX_INITIALIZER(name)
+
+static inline void fibril_rmutex_initialize(fibril_rmutex_t *m)
+{
+	futex_initialize(&m->futex, 1);
+}
+
+static inline void fibril_rmutex_lock(fibril_rmutex_t *m)
+{
+	futex_lock(&m->futex);
+}
+
+static inline bool fibril_rmutex_trylock(fibril_rmutex_t *m)
+{
+	return futex_trylock(&m->futex);
+}
+
+static inline void fibril_rmutex_unlock(fibril_rmutex_t *m)
+{
+	futex_unlock(&m->futex);
+}
 
 typedef struct {