Table of contents
CPU Scheduling:
Definition: CPU scheduling is the process of determining the order in which processes are executed on a computer's CPU.
Importance: CPU scheduling is essential for efficient utilization of the CPU and ensuring fairness in process execution.
Scheduling Criteria:
CPU Utilization: Maximizing CPU utilization to keep the CPU busy and avoid idle time.
Throughput: Maximizing the number of processes completed per unit of time.
Turnaround Time: Minimizing the time taken for a process to complete from submission to termination.
Waiting Time: Minimizing the time a process spends waiting in the ready queue.
Response Time: Minimizing the time taken for a process to start responding to a user's request.
CPU Scheduling Algorithms: a. First-Come, First-Served (FCFS):
Processes are executed in the order they arrive in the ready queue.
Non-preemptive: Once a process starts executing, it continues until completion. b. Shortest Job Next (SJN) or Shortest Job First (SJF):
Selects the process with the smallest burst time for execution.
Non-preemptive or Preemptive: May either let the current process complete or preempt it if a shorter job arrives. c. Priority Scheduling:
Each process is assigned a priority, and the CPU is allocated to the highest priority process.
Non-preemptive or Preemptive: May allow the current process to complete or preempt it based on priority. d. Round Robin (RR):
Each process is given a fixed time quantum to execute, and then it is moved to the end of the ready queue.
Preemptive: Processes are preempted after their time quantum expires. e. Multilevel Queue Scheduling:
Processes are divided into multiple priority queues, and each queue may have a different scheduling algorithm.
Each queue has its own scheduling algorithm, such as FCFS, SJF, or Priority Scheduling. f. Multilevel Feedback Queue Scheduling:
Similar to multilevel queue scheduling but allows processes to move between different queues based on their behavior.
Each queue has a different time quantum, and processes can move to a higher or lower priority queue based on their CPU usage. g. Lottery Scheduling:
Each process is assigned a number of lottery tickets, and a random ticket is drawn to select the winning process.
Probability-based: The more tickets a process has, the higher its chances of winning the CPU. h. Fair Share Scheduling:
Allocates CPU time based on proportional sharing, ensuring that each user or group gets a fair share of the CPU.
Used in systems with multiple users or groups to prevent any single user from monopolizing the CPU.
Scheduling Algorithms Comparison:
Each algorithm has its advantages and disadvantages based on the scheduling criteria and system requirements.
Factors to consider include CPU utilization, throughput, turnaround time, waiting time, response time, and fairness.