Skip to content

DA3. Scheduling algorithms

Statement

  • Please refer to the document Types of CPU Scheduling algorithms and:
    • Find out the best type of CPU scheduling system out of the seven mentioned in the document.
    • Provide facts to support your claims to persuade your peers.

Solution

  • This text will explain every algorithm listed in the supplied document, then it will select the best algorithm and support the claim with facts.
  • The criteria for choosing the best algorithm circulate around according to (Arpaci-Dusseau R., 2018):
    1. Maximizing CPU utilization.
    2. Fairness.
    3. Maximizing turnaround time: the time between the submission of a process and its completion.
    4. Minimizing Response time: the time between the submission of a process and its first response.
  • Scheduling types according to (Arpaci-Dusseau R., 2018):
    • Preemptive scheduling: The OS enforces the process to leave the CPU using timer interrupts; each process can run up to the period of a p**redefined time slice**, and then it gets forced to leave the CPU and goes back to the ready queue. In the meantime, the state of the process gets carefully saved so it can continue from where it left off.
    • Non-preemptive scheduling: The process voluntarily gives up the CPU without OS enforcement; once a process is on the CPU, it can not be interrupted until it finishes.

Scheduling algorithms

  1. First Come, First Serve (FCFS):
    • The first process that arrives gets the CPU first until it finishes.
    • The process gets added to the ready queue if the CPU is busy.
    • It is a non-preemptive, non-fair algorithm and bad for turnaround and response time.
  2. Shortest Job First (SJF):
    • The process with the shortest execution time gets the CPU first.
    • Problems arise when a short job arrives just behind a long job, and the long job gets the CPU first.
    • It is a non-preemptive, non-fair algorithm, bad for turnaround time, and slightly better for response time than FCFS.
  3. Shortest Time To Completion First (STCF):
    • The process with the shortest time to completion gets the CPU first.
    • It is a preemptive, non-fair algorithm, bad for response time, and optimal for turnaround time.
  4. Round Robin (RR):
    • Each process gets a time slice of CPU; if it doesn’t finish in that time, it gets preempted and added to the end of the ready queue.
    • It is a preemptive, fair algorithm, good for response time but bad for response time.
  5. Priority Scheduling:
    • Each process gets a priority number; the process with the highest priority gets the CPU first.
    • If two processes have the same priority, the one that arrived first gets the CPU (FCFS).
    • It is a preemptive, non-fair algorithm, good for response time and turnaround time.
  6. Multi-level Queue Scheduling:
    • The processes are divided into multiple queues, each with a different priority and scheduling algorithm.
    • The process with the highest priority gets the CPU first.
    • If two processes have the same priority (in the same queue), the next job is chosen according to the scheduling algorithm of that queue.
    • It is a preemptive, fair, or not fair (depending on the algorithm of the specific queue), good for response time and turnaround time.
  7. Multilevel Feedback Queue Scheduling:
    • The processes are divided into multiple queues, each with a different priority and scheduling algorithm.
    • The process with the highest priority gets the CPU first.
    • If two processes have the same priority (in the same queue), the next job is chosen according to the scheduling algorithm of that queue.
    • The scheduler constantly modifies the priority of the processes based on their behavior and history.
    • The scheduler constantly observes the jobs’ behavior (feedback) and analyzes it to make the best decision.
    • The scheduler is constantly doing one or more of the following to ensure fairness:
      • Keep the priority of a process if it is behaving well (gives up CPU before its time slice finishes).
      • Decreasing a process’s priority if it misbehaves (consuming CPU for longer times).
      • Periodically boosting the priority of all processes in the system to ensure no process is starved.
    • It is preemptive, fair, and best for response and turnaround times.

Conclusion

  • The best algorithm is Multilevel Feedback Queue Scheduling.
  • This algorithm performed well according to the criteria mentioned above.
  • The fact that this algorithm is constantly observing and analyzing the processes’ behavior and history allows it to make better decisions.
  • Most modern operating systems use some sort of this algorithm, allowing the user to parameterize the algorithm to fit the system’s needs.

References

  • Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. (2018). Operating systems: three easy pieces (1.01 ed.). Arpaci-Dusseau Books. Retrieved June 16, 2022, from https://pages.cs.wisc.edu/~remzi/OSTEP/.