Index: kernel/generic/include/proc/task.h
===================================================================
--- kernel/generic/include/proc/task.h	(revision 1a1e124b882ccc4fbef3fb07eec44b3f0da07282)
+++ kernel/generic/include/proc/task.h	(revision 07d4271f2d0447f764d751ed8f95104f720791d2)
@@ -88,5 +88,5 @@
 
 	/** Number of references (i.e. threads). */
-	atomic_size_t refcount;
+	atomic_refcount_t refcount;
 	/** Number of threads that haven't exited yet. */
 	// TODO: remove
@@ -144,5 +144,4 @@
 extern void task_done(void);
 extern task_t *task_create(as_t *, const char *);
-extern void task_destroy(task_t *);
 extern void task_hold(task_t *);
 extern void task_release(task_t *);
Index: kernel/generic/src/ddi/ddi.c
===================================================================
--- kernel/generic/src/ddi/ddi.c	(revision 1a1e124b882ccc4fbef3fb07eec44b3f0da07282)
+++ kernel/generic/src/ddi/ddi.c	(revision 07d4271f2d0447f764d751ed8f95104f720791d2)
@@ -336,23 +336,19 @@
 		return EPERM;
 
-	irq_spinlock_lock(&tasks_lock, true);
-
 	task_t *task = task_find_by_id(id);
 
-	if ((!task) || (!container_check(CONTAINER, task->container))) {
-		/*
-		 * There is no task with the specified ID
-		 * or the task belongs to a different security
-		 * context.
-		 */
-		irq_spinlock_unlock(&tasks_lock, true);
+	if (!task)
 		return ENOENT;
-	}
-
-	/* Lock the task and release the lock protecting tasks dictionary. */
-	irq_spinlock_exchange(&tasks_lock, &task->lock);
-	errno_t rc = ddi_iospace_enable_arch(task, ioaddr, size);
+
+	errno_t rc = ENOENT;
+
+	irq_spinlock_lock(&task->lock, true);
+
+	/* Check that the task belongs to the correct security context. */
+	if (container_check(CONTAINER, task->container))
+		rc = ddi_iospace_enable_arch(task, ioaddr, size);
+
 	irq_spinlock_unlock(&task->lock, true);
-
+	task_release(task);
 	return rc;
 }
@@ -377,23 +373,19 @@
 		return EPERM;
 
-	irq_spinlock_lock(&tasks_lock, true);
-
 	task_t *task = task_find_by_id(id);
 
-	if ((!task) || (!container_check(CONTAINER, task->container))) {
-		/*
-		 * There is no task with the specified ID
-		 * or the task belongs to a different security
-		 * context.
-		 */
-		irq_spinlock_unlock(&tasks_lock, true);
+	if (!task)
 		return ENOENT;
-	}
-
-	/* Lock the task and release the lock protecting tasks dictionary. */
-	irq_spinlock_exchange(&tasks_lock, &task->lock);
-	errno_t rc = ddi_iospace_disable_arch(task, ioaddr, size);
+
+	errno_t rc = ENOENT;
+
+	irq_spinlock_lock(&task->lock, true);
+
+	/* Check that the task belongs to the correct security context. */
+	if (container_check(CONTAINER, task->container))
+		rc = ddi_iospace_disable_arch(task, ioaddr, size);
+
 	irq_spinlock_unlock(&task->lock, true);
-
+	task_release(task);
 	return rc;
 }
Index: kernel/generic/src/ipc/ipc.c
===================================================================
--- kernel/generic/src/ipc/ipc.c	(revision 1a1e124b882ccc4fbef3fb07eec44b3f0da07282)
+++ kernel/generic/src/ipc/ipc.c	(revision 07d4271f2d0447f764d751ed8f95104f720791d2)
@@ -967,12 +967,7 @@
 void ipc_print_task(task_id_t taskid)
 {
-	irq_spinlock_lock(&tasks_lock, true);
 	task_t *task = task_find_by_id(taskid);
-	if (!task) {
-		irq_spinlock_unlock(&tasks_lock, true);
+	if (!task)
 		return;
-	}
-	task_hold(task);
-	irq_spinlock_unlock(&tasks_lock, true);
 
 	printf("[phone cap] [calls] [state\n");
Index: kernel/generic/src/ipc/kbox.c
===================================================================
--- kernel/generic/src/ipc/kbox.c	(revision 1a1e124b882ccc4fbef3fb07eec44b3f0da07282)
+++ kernel/generic/src/ipc/kbox.c	(revision 07d4271f2d0447f764d751ed8f95104f720791d2)
@@ -200,9 +200,4 @@
 /** Connect phone to a task kernel-box specified by id.
  *
- * Note that this is not completely atomic. For optimisation reasons, the task
- * might start cleaning up kbox after the phone has been connected and before
- * a kbox thread has been created. This must be taken into account in the
- * cleanup code.
- *
  * @param[out] out_phone  Phone capability handle on success.
  * @return Error code.
@@ -211,26 +206,13 @@
 errno_t ipc_connect_kbox(task_id_t taskid, cap_phone_handle_t *out_phone)
 {
-	irq_spinlock_lock(&tasks_lock, true);
-
 	task_t *task = task_find_by_id(taskid);
-	if (task == NULL) {
-		irq_spinlock_unlock(&tasks_lock, true);
+	if (!task)
 		return ENOENT;
-	}
-
-	atomic_inc(&task->refcount);
-
-	irq_spinlock_unlock(&tasks_lock, true);
 
 	mutex_lock(&task->kb.cleanup_lock);
-
-	if (atomic_predec(&task->refcount) == 0) {
-		mutex_unlock(&task->kb.cleanup_lock);
-		task_destroy(task);
-		return ENOENT;
-	}
 
 	if (task->kb.finished) {
 		mutex_unlock(&task->kb.cleanup_lock);
+		task_release(task);
 		return EINVAL;
 	}
@@ -243,4 +225,5 @@
 		if (!kb_thread) {
 			mutex_unlock(&task->kb.cleanup_lock);
+			task_release(task);
 			return ENOMEM;
 		}
@@ -255,4 +238,5 @@
 	if (rc != EOK) {
 		mutex_unlock(&task->kb.cleanup_lock);
+		task_release(task);
 		return rc;
 	}
@@ -265,4 +249,5 @@
 
 	mutex_unlock(&task->kb.cleanup_lock);
+	task_release(task);
 	*out_phone = phone_handle;
 	return EOK;
Index: kernel/generic/src/proc/program.c
===================================================================
--- kernel/generic/src/proc/program.c	(revision 1a1e124b882ccc4fbef3fb07eec44b3f0da07282)
+++ kernel/generic/src/proc/program.c	(revision 07d4271f2d0447f764d751ed8f95104f720791d2)
@@ -99,5 +99,5 @@
 	if (!area) {
 		free(kernel_uarg);
-		task_destroy(prg->task);
+		task_release(prg->task);
 		prg->task = NULL;
 		return ENOMEM;
@@ -119,5 +119,5 @@
 		free(kernel_uarg);
 		as_area_destroy(as, virt);
-		task_destroy(prg->task);
+		task_release(prg->task);
 		prg->task = NULL;
 		return ELIMIT;
Index: kernel/generic/src/proc/task.c
===================================================================
--- kernel/generic/src/proc/task.c	(revision 1a1e124b882ccc4fbef3fb07eec44b3f0da07282)
+++ kernel/generic/src/proc/task.c	(revision 07d4271f2d0447f764d751ed8f95104f720791d2)
@@ -158,5 +158,4 @@
 		return rc;
 
-	atomic_store(&task->refcount, 0);
 	atomic_store(&task->lifecount, 0);
 
@@ -201,4 +200,6 @@
 	if (!task)
 		return NULL;
+
+	refcount_init(&task->refcount);
 
 	task_create_arch(task);
@@ -268,5 +269,5 @@
  *
  */
-void task_destroy(task_t *task)
+static void task_destroy(task_t *task)
 {
 	/*
@@ -299,5 +300,5 @@
 void task_hold(task_t *task)
 {
-	atomic_inc(&task->refcount);
+	refcount_up(&task->refcount);
 }
 
@@ -311,5 +312,5 @@
 void task_release(task_t *task)
 {
-	if ((atomic_predec(&task->refcount)) == 0)
+	if (refcount_down(&task->refcount))
 		task_destroy(task);
 }
@@ -416,22 +417,32 @@
 /** Find task structure corresponding to task ID.
  *
- * The tasks_lock must be already held by the caller of this function and
- * interrupts must be disabled.
- *
  * @param id Task ID.
  *
- * @return Task structure address or NULL if there is no such task ID.
+ * @return Task reference or NULL if there is no such task ID.
  *
  */
 task_t *task_find_by_id(task_id_t id)
 {
-	assert(interrupts_disabled());
-	assert(irq_spinlock_locked(&tasks_lock));
+	task_t *task = NULL;
+
+	irq_spinlock_lock(&tasks_lock, true);
 
 	odlink_t *odlink = odict_find_eq(&tasks, &id, NULL);
-	if (odlink != NULL)
-		return odict_get_instance(odlink, task_t, ltasks);
-
-	return NULL;
+	if (odlink != NULL) {
+		task = odict_get_instance(odlink, task_t, ltasks);
+
+		/*
+		 * The directory of tasks can't hold a reference, since that would
+		 * prevent task from ever being destroyed. That means we have to
+		 * check for the case where the task is already being destroyed, but
+		 * not yet removed from the directory.
+		 */
+		if (!refcount_try_up(&task->refcount))
+			task = NULL;
+	}
+
+	irq_spinlock_unlock(&tasks_lock, true);
+
+	return task;
 }
 
@@ -524,5 +535,5 @@
 static void task_kill_internal(task_t *task)
 {
-	irq_spinlock_lock(&task->lock, false);
+	irq_spinlock_lock(&task->lock, true);
 
 	/*
@@ -534,5 +545,5 @@
 	}
 
-	irq_spinlock_unlock(&task->lock, false);
+	irq_spinlock_unlock(&task->lock, true);
 }
 
@@ -552,15 +563,10 @@
 		return EPERM;
 
-	irq_spinlock_lock(&tasks_lock, true);
-
 	task_t *task = task_find_by_id(id);
-	if (!task) {
-		irq_spinlock_unlock(&tasks_lock, true);
+	if (!task)
 		return ENOENT;
-	}
 
 	task_kill_internal(task);
-	irq_spinlock_unlock(&tasks_lock, true);
-
+	task_release(task);
 	return EOK;
 }
@@ -592,8 +598,5 @@
 	}
 
-	irq_spinlock_lock(&tasks_lock, true);
 	task_kill_internal(TASK);
-	irq_spinlock_unlock(&tasks_lock, true);
-
 	thread_exit();
 }
@@ -624,5 +627,5 @@
 	if (additional)
 		printf("%-8" PRIu64 " %9zu", task->taskid,
-		    atomic_load(&task->refcount));
+		    atomic_load(&task->lifecount));
 	else
 		printf("%-8" PRIu64 " %-14s %-5" PRIu32 " %10p %10p"
@@ -636,5 +639,5 @@
 		printf("%-8" PRIu64 " %9" PRIu64 "%c %9" PRIu64 "%c "
 		    "%9zu\n", task->taskid, ucycles, usuffix, kcycles,
-		    ksuffix, atomic_load(&task->refcount));
+		    ksuffix, atomic_load(&task->lifecount));
 	else
 		printf("%-8" PRIu64 " %-14s %-5" PRIu32 " %18p %18p\n",
Index: kernel/generic/src/security/perm.c
===================================================================
--- kernel/generic/src/security/perm.c	(revision 1a1e124b882ccc4fbef3fb07eec44b3f0da07282)
+++ kernel/generic/src/security/perm.c	(revision 07d4271f2d0447f764d751ed8f95104f720791d2)
@@ -89,18 +89,19 @@
 		return EPERM;
 
-	irq_spinlock_lock(&tasks_lock, true);
 	task_t *task = task_find_by_id(taskid);
-
-	if ((!task) || (!container_check(CONTAINER, task->container))) {
-		irq_spinlock_unlock(&tasks_lock, true);
+	if (!task)
 		return ENOENT;
+
+	errno_t rc = ENOENT;
+
+	irq_spinlock_lock(&task->lock, true);
+	if (container_check(CONTAINER, task->container)) {
+		task->perms |= perms;
+		rc = EOK;
 	}
-
-	irq_spinlock_lock(&task->lock, false);
-	task->perms |= perms;
-	irq_spinlock_unlock(&task->lock, false);
-
-	irq_spinlock_unlock(&tasks_lock, true);
-	return EOK;
+	irq_spinlock_unlock(&task->lock, true);
+
+	task_release(task);
+	return rc;
 }
 
@@ -118,11 +119,7 @@
 static errno_t perm_revoke(task_id_t taskid, perm_t perms)
 {
-	irq_spinlock_lock(&tasks_lock, true);
-
 	task_t *task = task_find_by_id(taskid);
-	if ((!task) || (!container_check(CONTAINER, task->container))) {
-		irq_spinlock_unlock(&tasks_lock, true);
+	if (!task)
 		return ENOENT;
-	}
 
 	/*
@@ -131,17 +128,20 @@
 	 * doesn't have PERM_PERM.
 	 */
-	irq_spinlock_lock(&TASK->lock, false);
-
-	if ((!(TASK->perms & PERM_PERM)) || (task != TASK)) {
-		irq_spinlock_unlock(&TASK->lock, false);
-		irq_spinlock_unlock(&tasks_lock, true);
+	if (task != TASK && !(perm_get(TASK) & PERM_PERM)) {
+		task_release(task);
 		return EPERM;
 	}
 
-	task->perms &= ~perms;
-	irq_spinlock_unlock(&TASK->lock, false);
-
-	irq_spinlock_unlock(&tasks_lock, true);
-	return EOK;
+	errno_t rc = ENOENT;
+
+	irq_spinlock_lock(&task->lock, true);
+	if (container_check(CONTAINER, task->container)) {
+		task->perms &= ~perms;
+		rc = EOK;
+	}
+	irq_spinlock_unlock(&task->lock, true);
+
+	task_release(task);
+	return rc;
 }
 
Index: kernel/generic/src/sysinfo/stats.c
===================================================================
--- kernel/generic/src/sysinfo/stats.c	(revision 1a1e124b882ccc4fbef3fb07eec44b3f0da07282)
+++ kernel/generic/src/sysinfo/stats.c	(revision 07d4271f2d0447f764d751ed8f95104f720791d2)
@@ -221,5 +221,5 @@
 	stats_task->virtmem = get_task_virtmem(task->as);
 	stats_task->resmem = get_task_resmem(task->as);
-	stats_task->threads = atomic_load(&task->refcount);
+	stats_task->threads = atomic_load(&task->lifecount);
 	task_get_accounting(task, &(stats_task->ucycles),
 	    &(stats_task->kcycles));
@@ -511,6 +511,7 @@
 {
 	/* Initially no return value */
-	sysinfo_return_t ret;
-	ret.tag = SYSINFO_VAL_UNDEFINED;
+	sysinfo_return_t ret = {
+		.tag = SYSINFO_VAL_UNDEFINED,
+	};
 
 	/* Parse the task ID */
@@ -519,13 +520,7 @@
 		return ret;
 
-	/* Messing with task structures, avoid deadlock */
-	irq_spinlock_lock(&tasks_lock, true);
-
 	task_t *task = task_find_by_id(task_id);
-	if (task == NULL) {
-		/* No task with this ID */
-		irq_spinlock_unlock(&tasks_lock, true);
+	if (!task)
 		return ret;
-	}
 
 	if (dry_run) {
@@ -533,28 +528,21 @@
 		ret.data.data = NULL;
 		ret.data.size = sizeof(stats_task_t);
-
-		irq_spinlock_unlock(&tasks_lock, true);
 	} else {
 		/* Allocate stats_task_t structure */
-		stats_task_t *stats_task =
-		    (stats_task_t *) malloc(sizeof(stats_task_t));
-		if (stats_task == NULL) {
-			irq_spinlock_unlock(&tasks_lock, true);
-			return ret;
+		stats_task_t *stats_task = malloc(sizeof(stats_task_t));
+
+		if (stats_task != NULL) {
+			/* Correct return value */
+			ret.tag = SYSINFO_VAL_FUNCTION_DATA;
+			ret.data.data = stats_task;
+			ret.data.size = sizeof(stats_task_t);
+
+			irq_spinlock_lock(&task->lock, true);
+			produce_stats_task(task, stats_task);
+			irq_spinlock_unlock(&task->lock, true);
 		}
-
-		/* Correct return value */
-		ret.tag = SYSINFO_VAL_FUNCTION_DATA;
-		ret.data.data = (void *) stats_task;
-		ret.data.size = sizeof(stats_task_t);
-
-		/* Hand-over-hand locking */
-		irq_spinlock_exchange(&tasks_lock, &task->lock);
-
-		produce_stats_task(task, stats_task);
-
-		irq_spinlock_unlock(&task->lock, true);
-	}
-
+	}
+
+	task_release(task);
 	return ret;
 }