Process Management

Scheduling

Process Scheduling

In computer systems multiple processes may be waiting to be executed by the processor and the processor needs to decided and how to schedule processing. There are multiple scheduling algorithms that can be used, depending on the system. These include:

  • Round Robin
  • First Come First Served
  • Short Job First
  • Shortest Remaining Time First

Process Priorities

In most computer systems, processes have different priorities, depending on their function within the system.

Calculations

Process Scheduling Calculations

Turnaround Time

Turnaround time = Completion time – arrival time

This is the duration between a process arriving and it terminating

Waiting Time

Waiting time = Turnaround time – burst time

This is how long a process waits idle before it is fully executed.

Average Waiting Time

Average Waiting Time = Waiting time for all processes / Number of processes

This is how long a process has to wait on average before it is fully processed.

 

States

Process States

Processes can be in one of 3 states.

Running

This is where the process is currently being executed by the processor

Ready

This is where the process is loaded into memory, ready to be executed.

Blocked

This is where the process is waiting for an event to occur before it is processed.

 

Round Robin

Round Robin Scheduling

In round-robin scheduling the processor works on each process in a circular manner. Each process is assigned an equal time-slice (aka quantum) for execution. Once the time-slice has been used up the  process is blocked and will have to wait until the next time round to carry on executing. If a process completes before it reaches it’s quantum limit then it self terminates the processor moves onto the next process.

Advantages

  • All processes are treated equally
  • All processes are guaranteed to be processed eventually

Disadvantages

  • Results in a high average waiting time

 

FCFS

First Come First Served Scheduling

Here jobs are executed in the order in which they arrived.

Advantages

  • All processes will be processed eventually.

Disadvantages

  • Large processes will cause a bottleneck (Convoy Effect)

SJF

Shortest Job First Scheduling

Here the process with the shortest estimated burst time is executed first. As new processes arrive their estimated burst is compared with the current process to see which process is to be executed.

Advantages

  • Can result in a lower average waiting time

Disadvantages

  • Requires the ability to accurately estimate burst times
  • Can result in priority inversion, depending on the system

 

SRTF

Shortest Remaining Time First Scheduling

Here the job with the least amount of remaining burst time is processed first. If a new job arrives with a shorter burst time than the job currently being executed then the current job is moved to the blocked queue and the new job is executed.

Useful in batch systems where smaller jobs need to be given priority.

Advantages

  • Can result in the lowest average waiting time

Disadvantages

  • A certain amount of processing time is required to calculate remaining burst times and switch between tasks (context switching)
  • The system must be able to accurately estimate burst times for each process, therefore SRTF can only be used in certain systems.

Resources