There are some difficult points that have to be cleared up if this multitasking is going to work. The first is how exactly does the operating system stop an application from taking more than a time slice?

The answer is that it might just rely on the honesty of the application to give up gracefully. This is called “co-operative” multi-tasking and this is exactly how Windows 3.x and earlier worked and, of course, some applications hogged the entire system. So much for co-operation! There are still examples today of co-operative multitasking but described in different terms. For example, any event handling system, HTML/JavaScript for example works by co-operative multitasking. Once an event handler starts running it can run for as long as it like and only when it ends or chooses to suspend itself does another even handler get to run.

Co-operative multitasking is simple to implement and it is relatively efficient as long as applications are written to give up the processor at every possible opportunity. In practice this turns out to be very difficult and it is much better to rely on “pre-emptive” multi-tasking. What happens is that the operating system has the power to interrupt the current process and take control – so pre-empting it. The mechanism is usually the software equivalent of a hardware interrupt, not unreasonably called a software interrupt.

What happens is that the operating system starts an application running and after the required time a software interrupt stops it running and passes control back to the operating system.

Easy! Well not really. What we are ignoring is the fact that the process that is interrupted will have values stored in registers and unfinished business all over the place. The operating system can’t just hand everything over to the next process because this would mean that when the interrupted process was restarted it wouldn’t be able to pickup where it left off.

Context switching

To make the system work the operating system has to store the process’s “context” – i.e. all of the values and the whole machine’s state as it was just before it was interrupted. Then, when the time comes to restart the process, its context can be restored and it can begin to run without even being aware that it has been stopped. The problem with this is that saving and restoring a process’s context is time consuming and difficult. You certainly have to save all of the processor registers but what about other hardware?

Any shared hardware could have been altered by the process and this too has to be saved. It slowly but surely becomes very complicated to the point where things start going wrong.

The solution to the problem is to consider that each process is running in a “virtual” machine. Each time a context switch occurs a new virtual machine is brought into play. The operating system’s job is to simulate a complete machine for each program running on the machine. This sounds easy but it is quite a tall order when you consider that this means that each process has to have a complete memory space that belongs to it and the parts of the operating system it wants to use. It also has to have control of all of the hardware in the machine as if it was the only one using it.

As it happens some of the mechanisms needed to create virtual machines had already been invented to create virtual memory. The paging system used  can quite happily map pages of real physical memory into the logical address space so as to give each process its own memory. When a context switch occurs all of the physical memory belonging to a process can be mapped out of the logical addresses and the pages that belong to the incoming process can be mapped in. The pages belonging to a suspended or low priority process might even find themselves being paged out to disk to make fresh RAM pages for the current process.

So now a context change involves swapping the entire memory structure out and saving all of registers. This only leaves the difficult problem of what to do about other hardware devices? In some cases the simplest thing to do is to forbid any attempt to access the hardware directly – and this is what Windows does in many cases. For example, you can’t write a Windows program that writes directly to the video hardware but you can ask the operating system to do it for you via the API – Applications Programming Interface. The operating system has a sort of global view of everything that is happening in the machine and can control the way that the screen is used.

Privilege levels

This is fine but what stops an application from breaking the rules and making a direct access to the video hardware?

The answer is privilege levels. Hardware in the processor protects both memory and I/O devices from access according to the privilege level assigned to a task. The operating system runs at the highest privilege level and can modify the privilege level and access rights of other tasks. All other tasks run at lower privilege levels. Each application can be fenced in to use only an allocated range of memory locations or a range of I/O ports. If the application dares to try to access something that it doesn’t have the right to then an exception occurs and the operating system is called. Using this mechanism it is possible to “trap” access to shared hardware and the operating system can provide software to pretend to be the hardware – in the jargon “to virtualise the hardware”. In Windows device drivers called VxDs in Windows 95 and WDMs in Windows 98/NT and beyond are responsible for virtualising individual hardware components.

With all of this going on you can guess that a context switch is an expensive event. As a result the “thread” was invented. A thread can be thought of as a lightweight task. An application can consist of multiple threads and the operating system will switch between threads without performing a context switch. This is efficient but dangerous because one thread can quite happily run wild over any other thread in an application. Even so the thread is the most basic unit of concurrency that most programmers ever encounter. A modern application running on modern hardware is usually a number of processes - each one isolated from the rest - and each process consists of a number of threads. When the operating system swaps which thread is running then no expensive context swap occurs. When a thread in a different process is started then a context swap is incurred. Of course today a modern processor almost certainly have multiple processing units or cores and this means that more than one thread can be running at the same time and this complicates things - and is another story.

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

<ASIN:0735625301>

<ASIN:1934053015>

<ASIN:0470289627>

<ASIN:0596514808>