8
$\begingroup$

This question is related to OS. After having solved many problems in CPU scheduling I was wondering how does the CPU know the burst time of all the processes in the main memory before executing them?

Selecting a process among a pool of processes using some scheduling algorithm is done based on CPU burst of each process(SJF,SRTF etc). And I'm aware of the predictor formula. And yet I'm trying to get the whole picture as clearly as possible. How does that equation help choose which process is to be executed next?

Improve this question
$\endgroup$
1
  • $\begingroup$ Shortest job first scheduler, shortest remaining time first scheduer is never implemented in a real operating system, the reason mainly being starvation of process which has a large burst time. $\endgroup$
    – Amaan Uddin
    Commented Apr 16, 2017 at 6:03

2 Answers 2

Reset to default
6
$\begingroup$

Bursts values are needed for Shortest Job First (SJF) or Shortest Run Time First (SRTF) type scheduling. The burst is an estimate based on an initial starting default burst value and actual historical run values. A process is assigned a default estimated value for its first burst and after it has run the actual burst is known. The last estimated burst and the last actual burst are averaged to provide the process's next estimated burst. This next estimated value is used for the next scheduling choice. Assuming the actual bursts are roughly equal, as the process runs it's estimated burst will more closely approximate the actual value since the averaging process moves the estimated burst towards the actual value. Of course if the actual burst for the process is somewhat random then the estimated burst will end up being closer to a median of the long and short burst times for the process. As processes continue to run they will tend to move into either the long burst group of processes or the short burst group.

For example, when a process is created there is no historical information so it's burst value is set to a default of 10. If the process always has an actual burst time of 20, then after the first scheduling period the estimated burst value assigned to the process will be (10+20)/2 = 15. The second run it will get (15+20)/2 = 17.5 estimated burst and so on. Each pass will move the estimate closer to the actual time required.

I probably wouldn't choose this method for scheduling a general purpose system, preferring instead a combined priority/quantum scheduling arrangement. With SJF, a busy system with many short burst jobs could starve the longer burst CPU intensive jobs. And if a job had short previous run times then got into a compute intensive loop, even other "short" jobs could wait excessive times before getting CPU time. It can work well for systems that aren't excessively CPU bound and for systems where the process run times are reasonably consistent.

In a priority/quantum round robin based systems, jobs with the same priority are given at lease some CPU time, but will relinquish the CPU to other equal priority processes when it's quantum ends and will wait for its turn to come around again. If a higher priority process needs CPU time, it can preempt lower priority processes. Various priority boosting methods can prevent complete starvation of low priority jobs on busy systems.

Improve this answer
$\endgroup$
1
$\begingroup$

For a discussion of scheduling algorithms in a real kernel (not the idealized simplifications so dear to operating system text authors) check out Pabla's "Completely fair scheduler".

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.