Index: uspace/lib/c/generic/fibril.c
===================================================================
--- uspace/lib/c/generic/fibril.c	(revision 80f345c2d6df8e54090633e7132fcb9939f93150)
+++ uspace/lib/c/generic/fibril.c	(revision abf8bd83815e2b5576079beb43f800b6af69cf8d)
@@ -72,4 +72,7 @@
 static void fibril_main(void)
 {
+	/* fibril_futex is locked when a fibril is first started. */
+	futex_unlock(&fibril_futex);
+
 	fibril_t *fibril = __tcb_get()->fibril_data;
 
@@ -211,6 +214,4 @@
 	}
 
-	futex_unlock(&fibril_futex);
-
 #ifdef FUTEX_UPGRADABLE
 	if (stype == FIBRIL_FROM_DEAD) {
@@ -223,4 +224,7 @@
 
 	/* Restored by another fibril! */
+
+	/* Must be after context_swap()! */
+	futex_unlock(&fibril_futex);
 
 	if (srcf->clean_after_me) {
Index: uspace/lib/c/generic/fibril_synch.c
===================================================================
--- uspace/lib/c/generic/fibril_synch.c	(revision 80f345c2d6df8e54090633e7132fcb9939f93150)
+++ uspace/lib/c/generic/fibril_synch.c	(revision abf8bd83815e2b5576079beb43f800b6af69cf8d)
@@ -629,4 +629,77 @@
 }
 
+/**
+ * Initialize a semaphore with initial count set to the provided value.
+ *
+ * @param sem    Semaphore to initialize.
+ * @param count  Initial count. Must not be negative.
+ */
+void fibril_semaphore_initialize(fibril_semaphore_t *sem, long count)
+{
+	/*
+	 * Negative count denotes the length of waitlist,
+	 * so it makes no sense as an initial value.
+	 */
+	assert(count >= 0);
+	sem->count = count;
+	list_initialize(&sem->waiters);
+}
+
+/**
+ * Produce one token.
+ * If there are fibrils waiting for tokens, this operation satisfies
+ * exactly one waiting `fibril_semaphore_down()`.
+ * This operation never blocks the fibril.
+ *
+ * @param sem  Semaphore to use.
+ */
+void fibril_semaphore_up(fibril_semaphore_t *sem)
+{
+	futex_down(&async_futex);
+	sem->count++;
+
+	if (sem->count > 0) {
+		futex_up(&async_futex);
+		return;
+	}
+
+	link_t *tmp = list_first(&sem->waiters);
+	assert(tmp);
+	list_remove(tmp);
+
+	futex_up(&async_futex);
+
+	awaiter_t *wdp = list_get_instance(tmp, awaiter_t, wu_event.link);
+	fibril_add_ready(wdp->fid);
+	optimize_execution_power();
+}
+
+/**
+ * Consume one token.
+ * If there are no available tokens (count <= 0), this operation blocks until
+ * another fibril produces a token using `fibril_semaphore_up()`.
+ *
+ * @param sem  Semaphore to use.
+ */
+void fibril_semaphore_down(fibril_semaphore_t *sem)
+{
+	futex_down(&async_futex);
+	sem->count--;
+
+	if (sem->count >= 0) {
+		futex_up(&async_futex);
+		return;
+	}
+
+	awaiter_t wdata;
+	awaiter_initialize(&wdata);
+
+	wdata.fid = fibril_get_id();
+	list_append(&wdata.wu_event.link, &sem->waiters);
+	fibril_switch(FIBRIL_TO_MANAGER);
+
+	/* async_futex not held after fibril_switch() */
+}
+
 /** @}
  */
Index: uspace/lib/c/include/fibril_synch.h
===================================================================
--- uspace/lib/c/include/fibril_synch.h	(revision 80f345c2d6df8e54090633e7132fcb9939f93150)
+++ uspace/lib/c/include/fibril_synch.h	(revision abf8bd83815e2b5576079beb43f800b6af69cf8d)
@@ -143,4 +143,24 @@
 } fibril_timer_t;
 
+/** A counting semaphore for fibrils. */
+typedef struct {
+	long count;
+	list_t waiters;
+} fibril_semaphore_t;
+
+#define FIBRIL_SEMAPHORE_INITIALIZER(name, cnt) \
+	{ \
+		.count = (cnt), \
+		.waiters = { \
+			.head = { \
+				.next = &(name).waiters.head, \
+				.prev = &(name).waiters.head, \
+			} \
+		} \
+	}
+
+#define FIBRIL_SEMAPHORE_INITIALIZE(name, cnt) \
+	fibril_semaphore_t name = FIBRIL_SEMAPHORE_INITIALIZER(name, cnt)
+
 extern void fibril_mutex_initialize(fibril_mutex_t *);
 extern void fibril_mutex_lock(fibril_mutex_t *);
@@ -174,4 +194,8 @@
 extern fibril_timer_state_t fibril_timer_clear_locked(fibril_timer_t *);
 
+extern void fibril_semaphore_initialize(fibril_semaphore_t *, long);
+extern void fibril_semaphore_up(fibril_semaphore_t *);
+extern void fibril_semaphore_down(fibril_semaphore_t *);
+
 #endif