Scheduling

A scheduler is responsible for the coordination of the running of processes to manage their access to the system resources such that each candidate process gets a fair share of the available process time, with the utilisation of the CPU being maximised. The scheduler (dispatcher) must ensure that processes gain access to the CPU for a time relative to its designated priority and process class and that no process is starved of access to the CPU, no matter if it is the lowest priority task available.

 A process may choose to voluntarily give up it's use of the microprocessor when it must wait, usually for some system resource or for synchronisation with another process. Alternatively the scheduler may pre-emptively remove the thread or process from the CPU at the expiry of it's allocated time quantum. The scheduler chooses which is the most appropriate process to run next.

 Scheduling is an operation of the kernel, which defines the following process states :

 

Linux   Windows NT
Running : The process is the current system process and is on the CPU carrying out it's execution.    Running : The process (thread) is the currently active process on the CPU.
Running : Ready to Run : The process is in a run queue ready to use the CPU when available.   Standby : The thread has been selected to run next by the processor, only one thread can be in this state.
Waiting : interruptable : The process is waiting for a resource or event but signals are not blocked and it may be interrupted.   Ready : The thread is simply waiting to execute and is a candidate for selection by the scheduler for entering standby at the next scheduling cycle.
Waiting : uninterruptable : The process is waiting for a resource or event but has disable signals such that it cannot be interrupted.   Waiting : The thread is waiting for synchronisation events, it has been directed to suspend by the environment subsystem or is waiting on I/O.
Stopped : The process has been stopped, usually by a SIGSTOP signal such as when performing debugging. 

 

   Transition : The thread is ready to execute but the resources it needs are not available. (e.g. the thread's kernel stack is paged out of memory).
Zombie : The process has completed and is ready to die, the scheduler has not yet detected this so it?s task_struct structure is still present.   Terminated : The thread has finished executing and the object manager decides whether the thread is deleted. If the executive has a pointer to the thread it may be reinitialised and reused. 
 

The scheduling of tasks on the different operating systems is similar, but each OS solves the problem in it's own way :

 

    Linux
     
    Windows NT
    Tasks have a priority which ranges from a setting of -20 to +20. The default priority of a task is 0 with -20 being the highest. Only the administrator can reset a process's priority to be less than 0, but normal users can adjust priorities in the positive range. This is done using the 'renice' command, though internally Linux uses a time quantum counter (in 'jiffies') to record this in the task_struct. 

    New processes inherit the priority of their parent.
     
    Threads have a priority which ranges from 1 to 31 with 8 being the user default and 31 being the highest. Priority 0 is reserved for system use. Only the administrator can set a processes priority to be above 15, normal users can set a process's priority in the 1 to 15 range in a two step process by first setting the process class and then setting the relative priority within the class. This is done using the Task Manager. 

    New processes inherit the priority of their creating process.
     Real time processes are supported. Any real time process will have higher priority than all non real-time processes.  

      

     
     
    Processes having priorities between 16 and 31 are real-time processes which are members of the realtime class. 

     time-critical and idle modifiers may move a dynamic thread's priority to the top or bottom of it's dynamic range respectively.
    Threads that have already received some CPU time will have lower priority than other of the same priority which have not.
     
    Non real-time threads may be boosted in priority should (e.g.) a blocked thread receive an event if was waiting for. This boost decays over time as the thread receives CPU time.