Skip to main content

Operating Systems | Scheduling Algorithms : SJF

Shortest Job First(SJF)

SJF algorithm schedules the shortest job(low burst time) available on main memory at the time of context switching in ready state . It can be either preemptive or non-preemptive depending on the nature of scheduler.

Since the SJF select the job which is shorted among available jobs on main memory, Non-preemptive SJF algorithm will have larger waiting time if a job with longer burst time get scheduled first. In short SJF is also vulnerable to Convoy Effect

To find shortest process among min-heap would be the best data structure to be used

Example : Consider the following table of processes and calculate completion time, turn around time and waiting time using SJF algorithm with the following assumptions.

  • No preemption.
  • No I/O request will be there from any process.
  • Arrival time is relative to CPU on time.

Process Number AT BT
1 0 3
2 2 2
3 2 4
4 4 2

Advantages:

  • Throughput is the degree of processes completed per unit interval of time. SJF has maximum throughput.
  • SJF algorithm provides minimum turnaround time and waiting time.

Disadvantages:

  • Starvation for longer jobs.
  • It is not implementable since burst time of a process is not predefined.

There are various methods to prediction of unknown burst time for the implementation of an algorithm which is very close in functionalities with SJF

  1. Static Prediction Methods
    • Prediction based on process size similarity

      The method assumes, that the process with nearly equal memory sizes can have almost equal processing time.

    • Prediction based on type of process

      Scheduler, dispatcher... are a process of Operating system doing core functionalities of the system and which will have a fast processing time.

      Custom processes where user's need plays a major role can be of type interactive where real time interaction with user is mandatory (example: Gaming), background process which need less interaction from user or foreground process.

      Normally Operating system's process are the fastest among all. Interactive process are faster than normal foreground processes and background processes are slower than that of foreground process. So it is possible to predict the burst time on a relative basis with reference to type of process.

  2. Dynamic Prediction Methods
    • Simple Averaging

      The time taken for the n+1th process is assumed as the average processing time of n process which are already completed the execution.

    • Exponential Averaging

      Prediction of time taken for current process is taken as weighted average of actual time and predicted time of previous process.

      Softening factor is the fractional weightage given to the processing time of the previous process.

Comments

Popular posts from this blog

Operating Systems | Scheduling Algorithms : Round Robin

| FCFS | SJF | SRTS | Round Robin | LJF | Priority Scheduling | HRRN | Round RobinFeatures : Most popular algorithm of allPractically implementableImplementable with basic data structures like queueExtremely lesser starvationOptimum efficiency can be set by controlling time quantumThe round robin algorithm will continuously switch between processes if a process in CPU (under execution) exceeds a time limit set by OS called time quantum.Flow Chart :Scheduler allocated process to for execution.CPU starts monitoring the execution time right after from allocation.If the process completes its execution before exceeding time quantum, OS forwards the process to termination state.else, the processes gets preempted once the time quantum limit exceeded and if the process finished at this moment, OS moves the process to termination state, else it moves to ready queue and iterates over the whole process listed above.Example : Consider the following table of processes and calculate complet…

Operating Systems | Concept of Process

Hard disk drive of the system in called primary memory and secondary memory is Random Access Memory(RAM). Either a program written in High Level Language(HLL) or a executable code generated by the sequence of works done by pre-processor, compiler and assembler, resides in secondary memory of the system. To start an execution, operating system allocates some space in the main memory, for the program to be executed and loads the program in the secondary memory to the allocated space. The piece of work which is loaded by the operating system to the main memory in order to execute program is called processEvery program loaded by operating system will create a focus boundary(or process body), a partitioned memory area where all memory requirements for the execution of program is satisfied.Variable which will not change its value through out life time of process is called static variable and variables which are globally accessible in a process known as global variable.Heap area is reserved f…