Search code examples
multithreadingoperating-systemround-robinxv6

OS Round Robin thread scheduling


Let's assume you have an OS that tries to run threads in round-robin scheduling. I know there are two instances when the OS will try to switch between multiple threads: (there could be more...)

  1. When the current thread actually yields the CPU earlier on its own.
  2. When the OS receives a timer interrupt. The question is let's say the OS has a max compute-bound time of say 5ms. (the OS receives a timer interrupt every 5ms)this assumption means that each thread can own a CPU core for a maximum of 5ms.

What happens if a process/thread finishes its time slice earlier than 5ms? Will this cause the next thread to be scheduled to have a compute-bound time lesser than 5ms since the next timer interrupt will occur and the thread will have no choice but to give up the CPU?

Specific Example:
What happens if a process/thread finishes its time slice earlier than 5ms let's say 2ms? I know another thread will be scheduled, but will that thread have a full-time slice of 5ms or will this next thread only have 3ms before the next timer interrupt occurs?


Solution

  • This question is likely dependent of the OS (not provided). On mainstream OSs, a yielding tasks typically waits for a resource or for a given time. The operating system will not reschedule it unless it becomes ready (completed IO operation, available lock, timeout, etc.). When a new task is ready, the OS scheduler is free to either wait for the end of a time-slice or reschedule the previous task. It is common for the task to be rescheduled so to increase the responsiveness of multithreaded applications (waiting for few milliseconds when a code tries to hold a lock that is already taken is not reasonable). That being said, this behavior is often not implemented so directly. Windows make use of priority boosts so to do that. On Linux, CFS tries to make the schedule fair so that all tasks have a balanced time on all available resources (eg. cores). The priority of the target tasks also matters. The OS of some famous gaming consoles uses a round-robin scheduler by default and they only schedule lower-priority tasks if there is no high-priority task. On such system, when a higher-priority task becomes ready, the current one is directly interrupted (with not delay except the overhead of a context switch).

    Put it shortly, the OS does not necessary have to wait for a timer interrupt to do context switches. Also, yes, time-slices are generally never left empty so they are reused by other tasks. Whether the scheduled tasks can be scheduled in a full time slice is dependent of the actual OS scheduler. Also note that a thread do not "give up the CPU": user-land threads have not real control on this. In practice, either a schedule-like kernel call is done during a system call (causing a context switch of the current task), or a system interrupt causes a kernel code to be executed that typically do this schedule-like kernel call at the end of a time slice.