IT Blogs

CPU Scheduling - Basic concepts

Basic concepts

• The assignment of physical processors to processes allows processes to accomplish work.
• That assignment is a complex problem handled by the operating system.
• When more than one process is runable, the operating system that makes this decision is called the scheduler.
• The algorithm it uses is called the scheduling algorithms.

Scheduling levels

Three important levels of scheduling are considered - High level scheduling, Intermediate level scheduling, Low level scheduling.

Preemptive Vs Non-preemptive Scheduling:

A scheduling discipline is non-preemptive if, once a process has been given the CPU, the CPU cannot be taken away from that process. A scheduling discipline is preemptive if the CPU can be taken away.

Priorities

• Priorities may be assigned automatically by the system or they may be assigned externally.
• They may be earned or they may be bought.
• They may be static or they may be dynamic.
• They may be rationally assigned, or they may be arbitrarily assigned in situations in which a system mechanism needs to distinguish between processes but doesn’ t really care which one is truly more important

Scheduling criteria(Objectives)

Many objectives must be considered in the design of a scheduling discipline. In particular, a scheduling discipline should have:

• Fairness: A scheduling discipline is fair if all processes are treated the same, and no process can suffer indefinite postponement.
• Throughput : A scheduling discipline should attempt to service the largest possible number of processes per unit time.
• Turnaround : minimize the time batch users must wait for output.
• Efficiency : keep the CPU busy 100 percent of the time.
• Response time : minimize response time for interactive users.

Scheduling Algorithms

Let us now discuss the algorithms one by one in detail

 First-Come-First-Serve(FCFS) scheduling

The simplest scheduling discipline is first-come-first-serve. Processes are dispatched according to their arrival time on the ready queue. Once a process has the CPU, it runs to completion.

• FCFS is a non-preemptive discipline. It is fair in the formal sense but somewhat unfair in that long jobs make short jobs wait, and unimportant jobs make important jobs wait.
• FCFS offers a relatively small variance in response times and is therefore more predictable than most other schemes. It is not useful in scheduling interactive users because it cannot guarantee good response times.

• FCFS is rarely used as a master scheme in today’ s system, but it is often embedded within other schemes. For example, many scheduling schemes dispatch processes according to priority, but processes with the same priority are dispatched FCFS.

Shortest job first scheduling

• Shortest Job First is a non-preemptive scheduling discipline in which the waiting job with the smallest estimated run-time-to-completion is run next.SJF reduces average waiting time over FIFO. The waiting times, however, have a larger variance than FIFO, especially for large jobs.
• SJF favors short jobs at the expense of longer ones.
• It selects jobs for service in a manner that ensures the next job will complete and leave the system as soon as possible.
• It tends to reduce the number of waiting jobs, and the number of jobs waiting behind large jobs.
• SJF can minimize the average waiting time of jobs as they pass through the system.

The obvious problem with SJF is:

• The process time for each process is known in advance which is not usually available.
• The best SJF can do is to rely on user estimates of run times.
• Relying on user estimates has an interesting ramification.
• The user can be forewarned that if the job runs longer than estimated, it will be terminated and the user will be charged for the work.
• A second option is to run the jobs for the estimated time plus a small percentage extra, and then to shelve it i.e., preserve it in its current form so that it may be restarted at a later time.

SJF like FIFO is non-preemptive and thus not useful in timesharing environments in which reasonable response times must be guaranteed.

Priority Scheduling

Round robin scheduling makes the implicit assumption that all processes are equally important. In some concerns, there is order of preference to get processed. The need to take external factors into account leads to priority scheduling. The basic idea is straightforward: each process is assigned a priority, and the runable process with the highest priority is allowed to run.

• To avoid high-priority processes from running indefinitely, the scheduler may decrease the priority of the currently running process at each clock tick.
• If this action causes its priority to drop below that of the next highest process, a process switch occurs.
• Alternatively, each process may be assigned a maximum quantum that it is allowed to hold the CPU continuously.
• It is often convenient to group processes into priority classes and use priority scheduling among the classes but round-robin scheduling within each class.

 

 

 

 

 

 

The scheduling algorithm is as follows:

oAs long as there are runable processes in priority class 4, just run each one for one quantum, round robin fashion, and never bother with lower priority classes.

o If priority class 4 is empty, then run the class 3 processes round robin.
o If classes 4 and 3 are both empty, then run class 2 round robin, and so on.

 

Want to discuss about other scheduling algorithms? Visit again...

This entry was posted on Thursday, May 14 2009 and is filed under General.
Tagged as: cpu-scheduling, scheduling-algorithms, scheduling-levels, high-level-scheduling, preemptive-scheduling, first-come-first-serve-fcfs-scheduling, priority-scheduling, round-robin-scheduling, multilevel-queue-scheduling
You can leave a response below.