1
$\begingroup$

I think, Preemption can easily be done in kernel mode, where it just have to call the Context-Switch procedure. Also, based on algorithm we can select the new process from the ready queue as well...

I'm unable to think and find Why and where the role of timers come and what exactly are significance of Hardware in preemptive scheduling.

Can we not do preemptive scheduling without hardware support?

Why I didn't ask on Stack-overflow?

=> I need the theoretical point, although I'll appreciate if someone mentions the actual implementations of Unix.

$\endgroup$
3
  • 2
    $\begingroup$ What happens if my program runs in an infinite loop? $\endgroup$ – FourierFlux Feb 27 at 20:12
  • 1
    $\begingroup$ As I recall, the whole context switch stuff happens when a certain interrupt is triggered. So you need something which triggers the interrupt. And since your program may not be willing to do this, you need something else to trigger interrupts. Is it not actually required? No: an alternative approach is to do program interpretation. I.e. you have a "master" program (interpreter) which runs all your programs. It reads and executes one instruction at a time and sometimes checks whether a context switch is required. Will be awfully slow though. $\endgroup$ – Dmitry Feb 27 at 20:20
  • $\begingroup$ It isn't necessary to have hardware support to do preemptive multitasking. But it is far more effective. To do it purely in software requires using an inline monitor as is used when implementing software virtualization without hardware support where the monitor code periodically checks if the quantum has expired. These checks would be ideally once per basic block. This is a more advanced version of what Dmitry described except that instead of an per instruction emulator it uses dynamic code translation. $\endgroup$ – Dan D. Feb 28 at 7:07
3
$\begingroup$

A preemptive scheduler must stop a program that is looping and not calling any operating system function. The program is not triggering any fault as division by zero. We are assuming that the interrupt are enabled and assuming single core processor. Only a timer interrupt can succeed to regain control of the processor. The rate set by this timer gives you the maximum switching time for the scheduler. The preferred value is 1000 Hz which gives 1 ms resolution. For computers not fast enough to allow so many timer interrupt per second, the next popular values were: 60 Hz, from the video card refresh rate 18 Hz, from a 16 bit overflow of IBM PC original timer chips ; color TV cristal of 3.59 MHz / 3 / 65536

Other option: cooperative multitasking. This is how apollo computer managed to run many tasks... As well as Windows 3.1 You call a lightweight scheduler everywhere your code perform long loops. The lightweight scheduler usually just decrement an integer and immediately return if the value still not zero. For the rare case where the integer reach zero, immediately set that integer to the default value and perform the next tests to decide if a new task with higher priority needs to be executed. If a precise timing is needed, then at this point, reading a hardware timer counter and comparing the value with the previous one allow to evaluate precisely the elapsed time.

$\endgroup$
5
  • 2
    $\begingroup$ Nitpick: Assuming a uniprocessor system, that is. On a multiprocessor one then presumably the kernel could be on one CPU, the user on another one, and the kernel could send interrupts to halt the user without needing any timers. $\endgroup$ – user541686 Feb 28 at 5:09
  • $\begingroup$ @user541686 There was an old Unix machine (forgot who the manufacturer was) that did something similar - it used two 68000 CPUs one running a version of Unix and another full-fledged CPU who's job it was to interrupt the OS CPU so that the kernel can run. It didn't run the kernel on a separate CPU, just a tiny piece of code (kind of like a simple driver) that interrupts the main CPU. That's not the only job of the second CPU of course, it also handled I/O basically implementing a DMA controller in software $\endgroup$ – slebetman Feb 28 at 6:27
  • 1
    $\begingroup$ @user541686 What you are describing is still a timer though. Only implemented in software instead of hardware $\endgroup$ – slebetman Feb 28 at 6:34
  • 1
    $\begingroup$ @slebetman I would say a 2nd CPU acting as a kind of "watchdog" counts as "hardware support". $\endgroup$ – TripeHound Feb 28 at 8:22
  • $\begingroup$ @TripeHound Yes but so does having 2 cores. The second core is a piece of hardware after all $\endgroup$ – slebetman Feb 28 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.