Randomize thread unblocking operation

[tiif]

In eventfd, we would unblock multiple threads in a deterministic sequence. In epoll, we always choose the thread id from the end of the list if multiple threads are blocked on the same epoll instance. We could randomize these operation depending on the seed.

Related FIXME:

miri/src/shims/unix/linux/eventfd.rs

Lines 226 to 229 in 9d9da34

	// FIXME: We can randomize the order of unblocking.
	for thread_id in waiting_threads {
	ecx.unblock_thread(thread_id, BlockReason::Eventfd)?;
	}

miri/src/shims/unix/linux/epoll.rs

Lines 549 to 555 in 9d9da34

	// FIXME: We can randomly pick a thread to unblock.
	let epoll = epfd.downcast::<Epoll>().unwrap();
	if let Some(thread_id) = epoll.thread_id.borrow_mut().pop() {
	waiter.push(thread_id);
	};

Side note:
Blocking socketpair #3665 would need to use this too.

[tiif]

@rustbot label +C-enhancement +A-concurrency

@rustbot claim

[oli-obk]

Do real systems randomize? It may cause starvation, which is usually attempted to be avoided by having some order

[RalfJung]

Generally we should be unblocking the thread that had waited the longest. Not sure what real systems do here, maybe we should ping some tokio folks who might know?

[RalfJung]

@rustbot label +A-shims

[oli-obk]

I wonder if the rules here are just the usual scheduler rules. Because at least on linux, according to https://www.man7.org/linux/man-pages/man7/sched.7.html the answer seems to be "unblock all threads and run them according to the normal scheduler rules"

[tiif]

For epoll (edge-triggered), since it can only wake up one thread, I think which thread the kernel choose to unblock might be implementation specific (I suspect the kernel has a wakeup queue too).

For eventfd, since we are waking up all threads, would it makes sense to randomize the unblocking sequence, while still prioritizing threads that have been waiting the longest?

I am still not sure what is the behaviour of actual system, though.

[oli-obk]

If we can pull out the "pick next thread to resume from a list of thread ids" logic into a function, we can reuse it here. I'd like them to be the same logic, so if we change one, the other changes, too

[discord9]

It would seems for epoll the order of waking up depend on how scheduler decide? Correct me if I'm wrong, but seems here use schedule_hrtimeout_range which wait a given time and may return early if a signal is delivered to the current task(which is determined by scheduler?). eventpoll itself also have a wait queue but it doesn't seem to affect unblocking order it seems?