How does OS scheduler schedule threads that belong to two different processes (tasks)? [closed]

Question

As far as all books say, switching between tasks/processes is more expensive than switching between threads of the same process/task. If so, then scheduler of threads-aware OS should schedule threads in such way that the threads of the same process/task should be executed next to each other (grouped) and not interleaved with threads from other processes/tasks.

As I am reading books on OSes, all books just stop at stating that threads switching is less expensive than process switching. And that's it. No book tells how exactly scheduler is solving problem of avoiding switching between threads of different tasks. As if such problem does not exist or is trivial to each and every reader.

Is my understanding of the problem not correct? Or am I missing something? Why such huge topic of possible performance degrade is not covered in each and every OS book in "Scheduling" chapter? Am I reading wrong books?

Arezzo

This is a really good question. I do know that most operating systems (eg Linux) treat threads as processes and do not do any special optimizations. I will keep looking for an answer because I am curious myself... – Mcmillen

I found articles on gang-scheduling and coscheduling which involve grouping related threads together. It is interesting, but doesn't add much to providing and answer. It seems likely, though, that process switching has a low enough overhead that it's not considered detrimental to performance to simply schedule threads as processes. – Mcmillen

@Dougvj: (2011) Operating Systems - Internals and Design Principles, 7th Ed (ISBN 013230998X), page 439. Finally I found the term that they use for grouping threads of the same task/process for executiong – Arezzo

this topic is very close to my question: How hard do operating systems try to minimize TLB flushes?: #1200305 – Arezzo

People are too obsessed with closing questions – Overdraft

Answer 1

In my opinion this would be a dangerous optimization, because if the scheduler favored threads based on whether or not the process memory pages are already loaded two things would happen:

1. Newer processes would be starved.
2. It would allow a process to keep spawning threads in order to stay on the CPU.

The scheduler's main priorities are:

1. I/O responsiveness - i.e. I/O bound threads preempt CPU-bound threads.
2. Fairness - try to ensure that starvation is limited.
3. Low latency - make sure each process can finish in a reasonable amount of time.

It's pretty easy to see that these 3 conditions conflict with the mentioned optimization.

Purehearted

Looks like difference between thread context switch or task context switch is so minor that no OS scheduler even bothers about running sibling threads next to each other. Seems like other properties of threads/processes have higher priority – Arezzo

@kachanov: Yes, the main criteria used for scheduling is the static and dynamic priority of a thread. – Purehearted

correct me if I'm wrong: if by any chance or algorithm the next thread in the execution queue appears to be from the same process (somehow the thread should let this know to the scheduler using some flags or descriptors), scheduler just bothers less and switches just the thread context. And if the next thread is from another process, scheduler does not care and just does a little bit more job by switching the process context. Is my understanding correct? – Arezzo

@kachanov: Yes, that is correct, since threads of the same process share the memory space and thus the loaded memory pages of the process. – Purehearted