0

I'm reading about scheduling, but I can't figure out how a scheduler regains control after it invokes code in the user space.

E.g. the scheduler passes the control to some app in the user space which does some infinite loop and no other hardware interrupt occurs on an one core chip. All documents talk about the scheduler regaining control and preemptivly interrupting the user process, but how does that work if the control is never passed back to the OS?

Question: Does the scheduler register with some clock in the CPU to be given control again after X msecs? Or is there some other trick? If no, what is the C function called to register for regular (or one time?) control regains?

Franz Kafka
  • 10,623
  • 20
  • 93
  • 149

2 Answers2

1

If no other interrupt occured, a preemptive O/S wouldn't despatch, and the user application would loop for ever.

This won't happen, though. Typically, a preemptive scheduler will despatch on every system call, every interrupt, and every tick of the system clock. The system clock will always interrupt, so your infinite loop simply won't occur.

The Pick operating system (after its developer Dick Pick) used a non-preemptive scheduler. Software developed for this system was required to make a system call periodically to allow the kernel to despatch other processes. In this environment the kernel would otherwise lose control completely until the process terminated.

The argument used in its justification was that considerable time was spent saving and restoring the processor state during a despatch. Forcing the application to take responsibility for this would allow a faster despatch process.

1

On Windows the Sleep(0) "causes the thread to relinquish the remainder of its time slice to any other thread of equal priority that is ready to run". This forces the scheduler to gain control.

On Linux the sched_yield "causes the calling thread to relinquish the CPU". This also forces the scheduler to gain control.

And the scheduler also gains control by interrupts too. When a thread has consumed its quantum of CPU usage the scheduler reschedules.

Windows CE for example allows to customize the thread quantum.

You may also read Thread Scheduling: quanta, switching and scheduling algorithms.

There is no single scheduler in Windows. Event based scheduling code is spread across the kernel. The kernels dispatcher routines are triggered by these events:

  • Thread ready for execution
  • Thread quantum expired
  • Thread priority change
  • Thread processor affinity change
  • Wait functions and Sleep functions

This Microsoft presentation is summarizing some of the scheduler principles.

Arno
  • 4,994
  • 3
  • 39
  • 63
  • Your last sentence is the interesting one. I know that, but how does this regaining work on a technical level? The scheduler can't activly gain control if it isn't in control already, so there must be a third entity if the user thread doesn't use `sleep` or any other system call to hand back the control. – Franz Kafka Aug 12 '13 at 10:21
  • You're right, I put it misleading. The scheduler frequently gets control by an interrupt entity and checks whether threads have consumed their quantum. Thus is detects when a thread has finished its quantum and reschedules. I made it more clear in the answer with my edit. – Arno Aug 12 '13 at 10:30