CPU scheduling deals with the issue of deciding which of the processes in the ready queue is to be allocated the CPU. Many different scheduling algorithms exist and these are the most important ones:

SCHEDULING ALGORITHMS:

CPU scheduling deals with the issue of deciding which of the processes in the ready queue is to be allocated the CPU. Many different scheduling algorithms exist and these are the most important ones:

First Come First served (FCFS):

This is the simplest scheduling algorithm, where the process that requests the CPU first is allocated the CPU first; it generates an average waiting time that varies significantly according to the CPU burst times. But it produces a "convoy effect", where all the other processes wait for the one big process to get off the CPU. It is non-preemptive in the sense that a process will not be pre-empted until it has finished running.

Shortest-Job-First (SJF):

In SJF the CPU is assigned to the process with the smallest next CPU burst, it generates the minimum average waiting time for a given set of processes. But there is no way to know the length of the next CPU burst, therefore Prediction is used to decide the length of the next CPU burst. SJF may be preemptive or nonpreemptive

Priority Scheduling:

In priority scheduling a priority is associated with each process, and the CPU is allocated to the process with the highest priority. The major problem with this type of scheduling is "starvation", where a process with a low priority could be blocked because the CPU is executing process with high priority. The solution to that problem is "Aging", where the priority of a process is reduced if it has been waiting for long, until it runs. Priority scheduling can be either preemptive or nonpreemptive.

Round-Robin (RR):

In RR scheduling the CPU is allocated to the first process in the queue for a short amount of time called "time quantum". The ready queue is kept as a FIFO queue of processes; new processes are added to the back of the queue. The process allocated the CPU may finish its burst in less time than the time quantum, If it does not finish its burst; it goes back to the back of the queue. The average waiting time tends to be too long. RR scheduling is preemptive.

SCHEDULING IN WinNT:

Windows NT scheduling uses a priority based, preemptive algorithm. The WinNT scheduler ensures that the highest priority process will always run. A process selected by the dispatcher will run until:

? It is preempted by a higher priority process.

? It terminates.

? Its time quantum ends.

? It calls a blocking system call such as for I/O.

If a higher priority real time process becomes ready while a lower priority process is running, the lower priority process will be preempted. This preemption gives a real time thread preferential access to the CPU when the thread needs such access. The dispatcher uses a 32 level priority scheme to determine the order of process execution. Priorities in WinNT are divided into two classes:

* The Variable class which contains processes with priorities ranging from 1 to 15.

* The Real time class which contains processes with priorities ranging from 16 to 31.

There are several priority classes to which a process can belong:

. REALTIME_PRIORITY_CLASS

2. HIGH_PRIORITY_CLASS

3. ABOVE_NORMAL_PRIORITY_CLASS

4. NORMAL_PRIORITY_CLASS

5. BELOW_NORMAL_PRIORITY_CLASS

6. IDLE_PRIORITY_CLASS

All priority classes are variable except the REALTIME_PRIORITY_CLASS within each of the priority classes is a relative priority, which can take the following values:

TIME_CRITICAL

HIGHEST

ABOVE_NORMAL

NORMAL

BELOW_NORMAL

LOWEST

IDLE

The priority of each process is based on the priority class it belongs to and its relative priority within that class, the following table represents that relationship between the priority class and relative priority of each process that is used in WinNT:

Real-time

High

Above

normal

Normal

Below normal

Idle priority

Time-critical

31

5

5

5

5

15

Highest

26

5

2

0

8

6

Above normal

25

4

1

9

7

5

Normal

24

3

0

8

6

4

Below normal

23

2

9

7

5

3

Lowest

22

1

8

6

4

2

Idle

6

1

1

1

1