The third article in the series, previously we looked at how the Operating System deals with memory and the different options available to the OS designer. However, the OS wouldn't be much use without being about to run programs.
The First Two series of this article can be found at:
OS Development 1 (Introduction)
OS Development 2 (Memory)
Firstly some terminology, processes are programs with all their code and the data which they require. Most OSes give each process its own virtual address space (refer to article 2 for more information) and its own set of system resources such as files, networking etc. A thread is a more lightweight concept - processes can be composed of multiple threads, each executing independently but sharing the same code and global data. In this article I will refer to processes and threads interchangeably.
|  |
Task modelsThere are a number of ways in which the OS can deal with running the user's programs.
Monotasking - The simplest of implementations, where only one process (or thread) may run at a time. When a program is executed it takes control of the whole machine until it is finished. An example of a monotasking OS is MS-DOS. The advantage of this model is that its easy to write, however it is very limiting and there is little protection against malicious code.
Multitasking - In this model the OS allows a number of different processes to run "at the same time." With the exception of multicore chips (which have their own problems) it is impossible for the processor to actually run two processes at the same time, instead it has to cleverly divide up the processor's time and switch between threads, in order to give the illusion that they are running simultaneously. The OS will interrupt a running process, save its state and then run another. At a later date the original process (and its state) will be reinstated for further execution. In multitasking there are two main types of system. The first,
cooperative multitasking, is where the OS runs the application until the process gives control back to the system, examples of OSes following this are RISC OS and Windows 3.1. Although there is less overhead than other options, the main problem with cooperative multitasking is stability, if a runaway process does not yield control then the user is stuck! The other multitasking system is
preemptive multitasking - here the OS actively takes away control from a process and gives it to another when its time is up. The advantage of preemptive multitasking is that runaway processes can be stopped, however this type of system is more complex to implement and has additional overhead. For most uses the benefits of PMS do outweigh the negatives and common OSes which using this are Linux and modern Windows.
Real Time - In this model the OS will guarantee a maximum and minimum time that a process will be responded to. For instance, the OS will ensure that it will complete operation y after time t but before time t' without fail... even if this is at the expense of lower priority jobs. The aim here is not speed, it is predictability and these models are commonly used in industrial applications such as the fly-by-wire system of an aircraft where there is a zero tolerance on failure. A common misconception is that a real time system gives better performance on the desktop - quite the contrary, as the OS must meet certain time constraint obligations this limits the CPU load (to about 70% capacity) and the time it can spend doing things like playing MP3 is greatly reduced. QNX is a real time OS, its documentation details the worst case (big-O) completion time for all of its system calls.
Context Switching
A context is a virtual address space with the process's code and data. A context switch (i.e. switching to another processes' context) involves storing the old machine state (so the process is waiting) and loading in the new state. Due to the large amount of data involved, this can be a very costly operation. There are two ways a context switch can be achieved - firstly chances are your CPU can do it itself (called a hardware context switch), however often the CPU will take a dumb approach and deal with its whole state (all the registers, stack etc) which has performance issues. In order to counter this the OS often overrides the hardware and does the switching itself (called a software context switch), here the OS tracks each process and maintains a list of EXACTLY what needs storing and loading and as such no extra unnecessary data switching is performed. Processes which are waiting can be held in virtual memory, although the OS should carefully analyze any performance hit.
Blocking Processes
A process is not always looking to be run - sometimes it is waiting for an external event, such as the user to enter some input or to read that file off a disk. For efficiency we do not want to give a blocking process some CPU time (called busy-waiting), as it will be a waste. In a multitasking system blocking processes will tell the OS they they are busy and are removed from the list until they inform the system that they are again ready to be executed. Processes which are blocking are prime candidates for placing into virtual memory, however the OS still needs to be careful here as some processes may only block for very short periods of time. |
 |
SchedulingA modern OS has many different threads to run, in order to satisfy these it needs to execute them all many times a second. Scheduling these threads is absolutely essential - an inefficient scheduler will cripple the system. The algorithm used to schedule processes will decide exactly how much CPU time is allocated to each, but no task can be starved of resources and the scheduler must be scalable over many processes. In reality the OS doesn't just use one algorithm, it uses many - some of the common ones are detailed here.
Round Robin - This is a simple algorithm, there is a queue of tasks and the OS adds the currently executing task to the end of the queue and then switches to the task at the front of the queue (removing it from there at the same time.) Each process is assigned a certain quantum (time slice) - after that quantum its another processes' tern. The time quantum is often between 20ms and 50ms, to keep overhead down its important that the quantum is significantly larger than the context switch time.
Priority based Round Robin - Here a scheduler might have 10 RR queues of runnable processes, each process has a priority (1 - 10) and will get put in the RR queue which matches its priority. The scheduler will try to take processes from the highest priority queue first and then work to the next queue, and then the next etc....
First Come First Served - Here there is a queue which holds the process's in the order they come in and they are executed in that order. In order to multitask it requires that each process will give up execution (cooperate) to the next task. The benefit of this is that its simple and fair, but not always efficient.
Shortest Job First - here the process requiring the least amount of CPU time will be selected to run. However, the problem is that often runtimes are unknown, requiring an element of guess work. Again SJF requires that the processes cooperate, the preemptive version of this is shortest remaining time next - where the scheduler picks the process with the lowest remaining runtime... again this is often hard to predict.
Rate Monotonic Scheduling - This is for real time OSes. Here the OS will schedule processes in such a way that none will ever exceed its deadline, the load can vary but in order to guarantee that deadline there has to be some slack CPU time and as such often the CPU can not exceed 70% usage. This works by giving each task a priority based on its interval - those with the smallest interval get the highest priority and those with the largest get the lowest priority. Then Priority based Round Robin is used to execute the jobs. The big problem with this approach is that approx 30% of the CPU is unused.
Earliest Deadline First - Again for real time OSes, each processes is assigned a deadline - the time by which the job must be completed by. The scheduler will look for the task with the closest deadling and give that one priority. Combined with this a monitor will keep on eye on the whole thing and ensure a task does not overload the system.
Multiprocessor Scheduling - Nowadays it is common to have two, three or four processors on a single chip. It is important that the OS can deal with this and make use of these cores efficiently. This is actually a very complex topic, and will cause a computer science problem as the number of cores grow to 32 or 64. Commonly the OS will assign certain threads to a specific CPU (based on the thread's requirements) whereas other threads can execute on the first available CPU. By assigning a thread to a certain CPU will optimize in terms of that CPU's cache, whereas if a thread jumps between CPUs it probably will not get a chance to fill the cache. By giving threads a favorite CPUs this often optimizes the runtime, and only when there is a clash between multiple threads wanting the same CPU will a thread get put onto another.
Further InformationAs ever I have just scratched the surface, a good tutorial on processes and threads can be found at
http://www.osdever.net/Images courtesy of WikipediaStay tuned for the next installment in this series - coming soon!
Article Source: http://www.TechnicalTalk.netYou can find more information here :-
*** Please do not forget to leave your comments about this article ***
