How does multitasking work

Question

I am completely clueless about the inner workings of an operating system, but I can more or less guess the approximate behaviour of many functions. One thing that I am not able to figure out, though, is multitasking.

In theory, the operating system manages time, according the CPU for small intervals to the various programs running. But it is not clear how this really works.

Say the operating system wants to start my program. The machine code is loaded somewhere in RAM, starting at a certain address. I guess then a jump should be performed to that address, allowing my code to execute. But in this way, the OS cannot regain control until I jump back.

Basically, I can imagine just two ways of making this work, but neither seems really suitable:

• The operating system could read the machine instructions I want to perform and emulate them instead of executing them directly. I am intentionally vague, since I do not know how this would work, but it seems like it would slow down the program considerably.

• Alternatively, the operating system could wait until I make a system call. In that moment it regains control and can check how long I have been running and do its timesharing stuff. This may work, but it seems unreliable, as I could make a long calculation which does not involve system calls and hang everything for a while.

So, it seems neither mechanism would work very well. How is multitasking actually performed?

Answer 1

The OS programs a timer to kick in every few microseconds (or milliseconds, depending on system speed). This timer raises the hardware interrupt, which causes the CPU to stop whatever it is currently doing, dump all its contents onto the stack and process the interrupt routine indicated by the address provided by the interrupt controller. This routine can inspect the stack and various other variables to make a decision which running process should next be put back into action. If it's the same process, the interrupt routine simply returns. If it's a different one, the relevant parts of the stack are saved and then replaced with the contents of a previously interrupted process, so when the interrupt routine returns, that process continues. Other than the fact that some time has elapsed, that process is unaware of having been interrupted and/or paused for some time.

This is (for modern CPUs) a VERY VERY simplified version of what happens, but it explains the principle. In addition to these OS controlled interrupts, there are also interrupts caused by external events (mouse, keyboard, serial ports, network ports, etc.) which are process with separate interrupt routines, which are usually connected to event handlers.

Very often process/task/context switching is also based on availability of external resources. Typically a process that requires data from storage (i.e. not in RAM) will place the request on a queue, set an event handler for the hardware interrupt indicating that the request has been served and then relinquish control to the task scheduler (since there is no point in waiting). Again, a very simplified description of what actually goes on, but it should serve the purposes of this answer.

Answer 2

It varies from system to system.

In nonpreemptive multitasking systems (such as the original Oberon, or the original Apple Macintosh), the operating system periodically "polls" all tasks, giving them an opportunity to do work. The tasks are expected to play nicely together. If they just have a little bit of work to do, they do it and return to the OS. If one task has a BIG chunk to do, it is expected to break it into little pieces, and work one little piece each time it is polled.

Hardware interrupts (disk drive DMA completions, serial port interrupts, what have you) cause interrupt routines to run. These interrupt routines may in turn notify tasks of work to be done when the task next runs.

In nonpreemptive multitasking systems, the occurrence or non-occurrence of an interrupt does not affect which task is running after the interrupt routine finishes.

In preemptive multitasking systems, it is possible for an interrupt routine to force a scheduling change. In a traditional round-robin preemptive multitasking system, a periodic timer interrupt does exactly that. The timer interrupt fires, the timer interrupt routine does some black magic to cause the return-from-interrupt instruction to return to the operating system's preemptive schedule, rather than to the running task, taking the processor away from the current task, and (POSSIBLY) giving it to another task. If no other task is ready to run at that point, the current task will get the processor again, having only lost some time.

Preemptive multitasking can cause a LOT of troubles. All of that annoying stuff about mutexes and critical sections and deadly embraces and priority inversions and ... show up when the processor gets taken away from you without warning. You have to use all those things to tell the operating system that you are in the middle of mixing nitroglycerin and taking the processor away from you right now is likely to result in a large smoking virtual hole in the middle of the server room floor.

Answer 3

Timer interrupts can be generated by computer hardware to interrupt CPU. In this way, based on the scheduling algorithm used by Operating System, OS can decide whether to continue executing your current program or context switch to another one that is ready to run.