Automatically inserted scheduler hints

[Kerskiy]

Hello. I'm new to OS development, so please don't be too harsh.

What if there were a way to automatically insert hints for scheduler? For example, a developer could run their program in an isolated environment and simulate its behavior. A special system would measure everything it needs (e.g. I/O or CPU bound; time slice size (specific for each program); P-core or E-core, SMT or a full processor) and write this data to a special section in this executable. This data is PC-agnostic.

At runtime a light dynamic scheduler would make correct adjustments depending on the current PC and workload, but it would base those choices on compile-time hints. If there are no compile-time hints(developer chose not to simulate his program behavior), then scheduling would be handled entirely by dynamic scheduler.

In your opinion, would such system yield any gains compared to default schedulers? Would it be cumbersome for developers to run and simulate their program behavior?

Thank you for your time and answers,
Kerskiy

[nullplan]

No program can know these things ahead of time, and they can be different between runs. For example, a program might have done its profiling run alone on the system, but at a later time, someone is running a web conferencing software alongside, which saturates network and CPU (that MPEG compression doesn't come cheap).

Plus, people typically want to sell software, and the settings on my machine aren't necessarily the same as on yours. Because I have a 486 and you have a Threadripper, or something. No, I think it is better to stick to simple algorithms that tune themselves depending on system conditions.

[Kerskiy]

and they can be different between runs.

Because I have a 486 and you have a Threadripper, or something.

I understand that program execution differs on each PC. That's why there's a dynamic (traditional) scheduler that will account for differences between developers' and users' CPUs, disks, workloads, etc. You may ask, 'if there's a dynamic scheduler, why keep a static one?' - the dynamic scheduler will be much simpler and faster than traditional ones, offloading the heaviest heuristics to the static scheduler.

Thank you for your answer and opinion,
Kerskiy

[rdos]

I think there should be cues that programs/threads can give to the scheduler to optimize their performance. These shouldn't be static (embedded in the executable), rather dynamic.

For example, I have a syscall MoveToNewCore that signals to the scheduler that here is a thread that is time-sensitive and that use a lot of CPU time, so if there is an unused core, move the thread there and don't let other threads run there unless necessary.

[Kerskiy]

For example, I have a syscall MoveToNewCore that signals to the scheduler that here is a thread that is time-sensitive and that use a lot of CPU time, so if there is an unused core, move the thread there and don't let other threads run there unless necessary.

I have two questions:
1) Are those dynamic hints generated by the scheduler or written by developers? Since you said your dynamic hints aren't embedded in the executable I assume it's the former.
2) Do those hints 'prepare' future threads or do they work immediately? E.g. if a thread must run after 2 ms, move it to another thread right now to mitigate memory latency

Thank you for your answer,
Kerskiy

[bellezzasolo]

For example, I have a syscall MoveToNewCore that signals to the scheduler that here is a thread that is time-sensitive and that use a lot of CPU time, so if there is an unused core, move the thread there and don't let other threads run there unless necessary.

I have two questions:
1) Are those dynamic hints generated by the scheduler or written by developers? Since you said your dynamic hints aren't embedded in the executable I assume it's the former.
2) Do those hints 'prepare' future threads or do they work immediately? E.g. if a thread must run after 2 ms, move it to another thread right now to mitigate memory latency

Thank you for your answer,
Kerskiy

Developers can write that stuff, probably the easiest way as an application developer, is to have a thread pool, then use coroutines. For example, the WinRT runtime has winrt::resume_background(), which does exactly this, it returns execution to the caller on the (mainly UI) thread, and resumes the coroutine on a background thread.

As a further advantage, this doesn't need any syscalls. Once you have the threads, you can just schedule work on them, as often as you want.

[Kerskiy]

For example, the WinRT runtime has winrt::resume_background(), which does exactly this, it returns execution to the caller on the (mainly UI) thread, and resumes the coroutine on a background thread.

As a further advantage, this doesn't need any syscalls.

I might be wrong, but don't you need to ask the kernel to change which thread is executing right now? That would mean doing a syscall.

Though I might have misunderstood what you meant because of my lack of knowledge.

Thank you in advance for your answer,
Kerskiy

[bellezzasolo]

For example, the WinRT runtime has winrt::resume_background(), which does exactly this, it returns execution to the caller on the (mainly UI) thread, and resumes the coroutine on a background thread.

As a further advantage, this doesn't need any syscalls.

I might be wrong, but don't you need to ask the kernel to change which thread is executing right now? That would mean doing a syscall.

Though I might have misunderstood what you meant because of my lack of knowledge.

Thank you in advance for your answer,
Kerskiy

Yes, you do need to call the kernel to change thread. However, on a modern machine, you typically have multiple threads running in parallel, one per CPU core (and then there's hyperthreading).

But if those threads belong to the same process, then they are running in the same address space, and you can signal between them without kernel involvement through shared memory.

You could envision a very basic system where what is shared is a function pointer and a pointer to data - you can now tell a thread to run a particular function, without involving the kernel.

Coroutines are effectively the conclusion of this. They do interact with kernels - typically asynchronous I/O. Instead of the kernel blocking, it queues the operation and returns a completion object immediately. Thus, the UI thread can continue to do other work, until the work to be done is exhausted.

But, if the work to be done is CPU heavy, you can use the same approach, but shift the work to a thread pool, which then effectively does user mode scheduling. The UI thread can then await the result as it would for any other long operation

[Kerskiy]

Yes, you do need to call the kernel to change thread. However, on a modern machine, you typically have multiple threads running in parallel, one per CPU core (and then there's hyperthreading).

But if those threads belong to the same process, then they are running in the same address space, and you can signal between them without kernel involvement through shared memory.

That's quite smart! So is it like a fast path? And instead of doing the whole heavy syscall logic you just point to some function in the same address space.

Thanks again ,
Kerskiy

[rdos]

For example, I have a syscall MoveToNewCore that signals to the scheduler that here is a thread that is time-sensitive and that use a lot of CPU time, so if there is an unused core, move the thread there and don't let other threads run there unless necessary.

I have two questions:
1) Are those dynamic hints generated by the scheduler or written by developers? Since you said your dynamic hints aren't embedded in the executable I assume it's the former.
2) Do those hints 'prepare' future threads or do they work immediately? E.g. if a thread must run after 2 ms, move it to another thread right now to mitigate memory latency

Thank you for your answer,
Kerskiy

I'd say the developer. I don't think it should be static information in the executable, but rather something done as the application spawns new threads with special needs.

I mainly used this when constructing a parallel analyzer. Work was divided among several threads, and these were designed to run on their own core to work optimally. The processor had a few more cores than needed by the worker threads, so the scheduler could allocate each of these threads its own core, which optimized performance. The other load was much smaller and could be shared by the remaining cores.

[bellezzasolo]

Yes, you do need to call the kernel to change thread. However, on a modern machine, you typically have multiple threads running in parallel, one per CPU core (and then there's hyperthreading).

But if those threads belong to the same process, then they are running in the same address space, and you can signal between them without kernel involvement through shared memory.

That's quite smart! So is it like a fast path? And instead of doing the whole heavy syscall logic you just point to some function in the same address space.

Thanks again ,
Kerskiy

I mean, pretty much. Of course, you need to be able to do the necessary atomic operations in user mode, but standard C++ has good builidng blocks for that in the likes of std::atomic<T>::compare_exchange_weak. In user mode you definitely want to then wait the thread if there's no work to be done, something like std::atomic<T>::wait.

[InvalidOpcode]

Compilers already do something similar, but for optimising how they compile code. It's called Profile Guided Optimisation: https://en.m.wikipedia.org/wiki/Profile ... timization . I use it when building GCC, as I use it so often that even a small speed-up is worth the extra compile time (and yes, I have measured it to make sure I'm not just wasting CPU cycles )

I think your idea is interesting, but as with all kinds of optimisation it should be based on empirical data, theory can only get us so far. What would be the minimum you'd need to write, in order to test a prototype?

I think the idea of making it machine-neutral is a mistake. Since none of it would involve re-compiling why not allow the user to just re-run the profiling at any time? That'd be simpler and tailor the scheduling to their machine