Priority Driven Approach

The term priority-driven algorithms refer to a class of scheduling algorithms that never leave any resource idle intentionally. A resource becomes idles only when job does not require the resource for execution. It is a event driven approach for job scheduling and scheduling decision are made only when release and completion of job occur. Commonly used terms for this approach are greedy scheduling, list scheduling, and work-conserving scheduling.

A priority-driven algorithm is said to be greedy because it tries to make locally optimal decisions. The resource becomes idle when resources are not locally optimal.

The term list scheduling is also used because any priority-driven algorithm can be implemented by assigning priorities to jobs. In this approach, Jobs ready for execution are placed in one or more queues ordered by the priorities of the jobs. At any scheduling decision time, the jobs with the highest priorities are scheduled and executed on the available processors. Hence a priority-driven scheduling algorithm is defined largely by the list of priorities it assigns to jobs.

It is also called as work conserving scheduling since when a processor or resource is available and some job can use it to make progress, a priority-driven algorithm never makes the job in wait i.e. after completion of a job another enters into execution

Examples include:

Most scheduling algorithms used in non-real-time systems are priority-driven they are

  • FIFO (first-in-first-out) and LIFO (last-in-first-out) algorithms which assign priorities to jobs based on their release
  • SETF (shortest-execution-time-first) and LETF (longest-execution-time-first) algorithms which assign priorities based on job execution times.

Real-time priority scheduling assigns priorities based on deadline or some other timing constraint they are:

  • Earliest deadline first
  • Least slack time first
  •  

Consider a task graph with following condition,

  • Jobs J 1, J 2, …, J 8, where J i had higher priority than J k if i < k.
  • Jobs are scheduled on two processors P1 and P2
  • Jobs communicate via shared memory, so communication cost is negligible –
  • The schedulers keep one common priority queue of ready jobs

When the jobs are scheduled in preemptive priority driven approach the jobs are scheduled as

  • At time 0, jobs J1, J2, and J7 are ready for execution.
  • They are the only jobs in the priority queue at this
  • Since J1 and J2 have higher priorities than J7 they are ahead of J7 in the queue and hence are
  • At time 1, J2 completes and hence J3 becomes J3 is placed in the priority queue ahead of J7 and is scheduled on P2, the processor freed by J2.
  • At time 3, both J1 and J3 J5 is still not released. J4 and J7 are scheduled.
  • At time 4, J5 is Now there are three ready jobs. J7 has the lowest priority among them so it is preempted and J4 and J5 have the processors.
  • At time 5, J4 completes. J7 resumes on processor
  • At time 6, J5 completes. Because J7 is not yet completed, both J6 and J8 are not yet ready for Thus processor P2 becomes idle.
  • J7 finally completes at time 8. J6 and J8 can now be scheduled on the processors. When the jobs are scheduled in preemptive priority driven approach the jobs are scheduled as

  • Before time 4 this schedule is the same as
  • However at time 4 when J5 is released, both processors are J5 has to wait until J4 completes at time 5 before it can begin execution.
  • It turns out that for this system, postponement of the higher priority job benefits the set of jobs as a
  • The entire set completes one time unit earlier according to the non-preemptive