http://neworder.box.sk/news/10562

Multitasking for x86 explained #1
@ Articles -> Programming     Mar 02 2004, 02:44 (UTC+0)  
zwanderer writes: Once again, the brave hamster will be our means of expressing one of the most fundamental ideas of modern processors, and subsequently, of modern operating systems - which is: the idea of multiple tasks, executed in "quick" succession (this article will not take multi processor systems into account, in which case more than one stream of execution is actually possible). This quick succession of execution will create the illusion to the user, that the processor is in fact executing all tasks simultaneously. This has wide applications, and on a well used Linux system, with services such as a web server, an e-mail server, a web browser etc. running, it will have huge consequences for the user as well. 

In this article, we shall take a closer look at the two methods widely used in operating systems today, and how it is possible to implement fairly easily. 


WARNING: The following contains terms you may not be familiar with unless you know something about the x86, or have read the other articles in this series.

First a little history for the younger viewers who have never had the pleasure of working with pre-windows operating systems. DOS, for those of you familiar with it - is a single execution environment. This means that the operating systems gives control over the CPU to what ever program is executed, and only takes over when it is explicitly asked to do so. This can happen either because of an interrupt or exception (e.g. a fault or trap because of illegal operations from the executing program), or because the program stops its flow of execution. This is a very one-track form of computing, which we probably all know too well when booting into DOS (the old F8 trick for when Windows just won't let you do ANYTHING), and has no multitasking at all. 

This was on the "old" Intel processors, and it was enough for the tasks needed at the time - but with the creation of e.g. Windows, the needed arose for multiple programs to be run at the same time. It became unacceptable for the user that he/she was unable to do more than one thing at a time, without having to suspend or terminate the program, load another one into memory, and continue work on that. A lot of this technology can be said to have come from Windows (although it isn't quite true, a lot of other architectures have had MP support Intel), and the development of the graphical interface, where it was now possible to represent more than one program graphically without clogging the smaller 80x25 line screens (no virtual terminals in DOS, darn it). 

So Intel sit down and come up with a way of switching tasks in mid flight, and call it Task Switching (TS). Task switching is a way for the processor to suspend the current flow of execution (which is considered to be a task), load another task from memory, and continue execution of this where it was suspended. This was implemented in hardware, so the programmer only had to setup a few structures, and tell the CPU to use task switching. Hardware task switching has been standard in all Intel processors (of the x86 line) since the 386.

So how does the CPU go about this? And how come it looks like its all running at the same time? And what about security!? We'll get to that in a minute. Today, there are two ways of switching tasks on the x86 architecture - although both rely on the Intel processors ability to switch tasks, they rely on it in different ways. Let me explain: There are two methods used.

+ Hardware task switching (fully utilizing the CPUs capabilities)
+ Software task switching (utilizing certain features of the CPUs 
task switching capabilities, and implementing the rest in software.

If you look at most hobby operating systems, you will find that a large number of these use software task switching, as does Linux (I can't honestly say I know which one Windows uses, though I would think it was software task switching). The reason why software task switching is so popular is that it can be faster than hardware task switching. Intel never actually developed the hardware task switching, they implemented it, saw that it worked, and just left it there. Advances in multitasking using software have made this form of task switching faster (some say up to 3 times faster) than the hardware method. Another reason is that the Intel way of switching tasks isn't portable at all, meaning you would have to re-write your entire multitasking segment in order to get it to work on any other processor. But still, the hardware supported task switching (multitasking) on the x86 is required even though you use software multitasking, simply because Intel demands it (way to go legacy).

In order to understand why this is - we have to look at what a task switch can actually do. If you have read my other x86 architecture articles, you will know that the x86 has four privilege rings. The kernel runs at ring 0, and user programs usually run at ring 3. The idea of multitasking is that the kernel never actually looses control of the CPU, which means you have to device some method of jumping to and from privilege levels. This can "only" (the Intel way) be done using a task switch, where the CPU sets the new privilege level according to the task you are switching to. There are some other things you can't do without letting the CPU apply the changes, and most of them require a task switch. 

Linux keeps use of hardware task switching to a minimum. With the "new" 2.4 kernel, the number of tasks isn't restricted (other than from hardware boundaries (2^32 tasks afaik)), where as the maximum number of tasks you can run on any x86 is 8192 (still a rather large number, but we don't like restrictions). 

A hardware task switch is a number of steps, all of which revolve around a TSS (Task Switch Segment). This is a massive structure which is pointed to via the GDT (its an entry in the GDT), and which contains all the information the processors needs to know when loading the suspended task. Fields in the structure include (I don't feel like writing them all down, check it if you really care...) a list of segment registers (DS, GS, FS, CS) and general purpose registers (EAX, EBX, ECX ...), the EEFLAGS (which is the thing we cant always change directly), the EIP (points to the last executed command of the task) and the CR3 (the page directory of the task (this is important!)). Some of these fields are filled by the CPU when a task switch command is issued, and some can be changed by the kernel. This structure is then placed in memory, where it can be loaded directly by jumping to it, in which case the CPU realises it's a TSS and loads the task associated with the TSS. Actually what it does is it initializes all its registers, flags and instruction pointer to the values in the TSS and just continues where it left off.

You may have noticed a way of doing this in software too, without the need for hundreds of big structures needed by the CPU. The above is hardware task switching, here is the description of software task switching. What if we made our own TSS structure, and put the register values into it our selves? That's exactly what Linux does. Linux defines a structure which contains e.g. the PID, niceness of the process, information about what memory it has access to, and what rights it has (see how there is suddenly room for expansion, and a lot of extra information Intel didn't include?). This structure is then combined with a kernel stack, and combined with a task. What's this kernel stack? The kernel stack is the fundamental idea of software task switching. There is a field for it in the TSS, but it's used for something different there. In software task switching you define an area of memory (8Kb of size for Linux), for each task. This won't clog the memory thanks to VM because all 8Kb will probably never be used at the same time anyway. When you want to software task switch, you load the ESP with the value of the kernel stack you supplied (the 8Kb one), and push all registers onto this stack, along with the task structure associated with the task. You then figure out which task you want to switch to, load the value of its kernel stack into the ESP and pop all the values off it, and restoring the registers accordingly. 

But how can this be done without changing anything in the process? How do you suddenly interrupt a process and push all the registers without accidentally changing something? You use interrupts. Interrupts stop the current execution (pushing the EIP onto the stack so you can IRET back), and start the interrupt service routine ISR associated with the interrupt number. When ever you handle an interrupt (as it was the case in the previous article), you always push the registers and segments so the interrupted task doesn't realise it was interrupted. The step from this simple interrupt handling and to multitasking is a relatively small one, involving only a few extra structures. One obvious interrupt to use is the timer, the PIT. This will raise an interrupt once every x milliseconds, jumping back into the kernel and allowing the kernel to calculate whether it is time for the process running before the interrupt to be interrupted, and replaced with a different one. If the processor finds it is time, it completes the steps above, fills in the TSS with a new EEFLAG values, and a few other things, sets the NT (new task) flag in EEFLAGS, and IRETs as normal. The CPU will then switch tasks, and the "old" task will wait until it is its turn again. The interval with which the CPU switches tasks in this manner is what you would call response time, which is - how often a task gets execution time - if it is almost never executed (due to low priority, or the fact that some other process is hogging the CPU), it will "lag". However, if the kernel switches tasks too often, you end up wasting too much time on context switches. Be aware, loading this much to and from memory isn't cheap - each task switch costs a lot of time, which is why its important to find the exact balance between the PIT interrupts and an actual task switch. For this, Linux uses TICKS, after a certain number of TICKS (this is computed during boot up, depending on how fast your CPU is); it will call the scheduler, which will then do a LOT of computation to figure out which tasks' turn it is to have the CPU.

Oh man what a lot of text, and not a single piece of code! But multitasking is complicated, even though - in its essence, it is pretty simple. Jumping to and from privileges can only be done using the TSS hardware task switch, so you need that some times (but you only use it full out a few times). When you want to change other reserved flags, like the V86 flag (the flag that lets the CPU run as if it were an 8086), you also need to run a complete TSS switch, but most of the time you are just switching tasks by pushing and popping off the stack (which follows the task around), and loading a smaller version of the TSS. This leaves you with: 

1) Faster task switches
2) Less memory usage, because the task unions can be switched out, the TSS'
Can't always be switched out
3) Less restriction in regards to the number of tasks (The old Linux NR_TASKS Macro)
4) Portable code which is easily altered to fit all architectures

So what's this about security? Well, the TSS has some security measures installed. One of them is the fact that you can reload the CR3 register at each switch. If you remember, the CR3 register holds the page directory, which is the way the program addresses memory in a paged system. When you have the ability to reload the page directory, each task can have its own memory region, allowing it to have a virtual memory region of 3Gb to its disposal, all to it self. This also means that changing the memory of other processes is not possible, simply because you cannot address physical memory directly, and the CPU makes sure not to accidentally map two linear locations to the same physical. Fancy eh?

But I'm afraid there will be no implementation today - within a few weeks a new simple multitasking version of HamsterOS will be released, along with #2 describing how this stuff is actually coded. I hope this has given you some idea of how multitasking can work/works on the x86.

With the best regards until we meet again
Uncle Kristian aka the hamster pounder