Introduction
- Scheduling/Process/CPU Scheduling is a fundamental function of an operating system.
- Strictly, all computer resources are scheduled before use/processing properly.
- Since CPU is one of the primary/superior computer resources, therefore its scheduling is must and central.
- CPU scheduling is the basis of operating system which supports multiprogramming concepts.
Definition
- In operating systems, scheduling algorithms are a way to manage the allocation of resources, such as CPU time and memory, to different processes or threads in a system.
- CPU scheduling is a core component of an operating system that manages the allocation of the central processing unit (CPU) to different processes or threads.
Features
- The choice of selecting a scheduling algorithm can significantly impact the system’s performance, responsiveness, and fairness.
- In practice, operating systems often use a combination of scheduling algorithms to balance different requirements and constraints.
- The CPU scheduler determines the order in which processes or threads are arranged and executed, aiming to maximize system performance and responsiveness.
Objectives/Purpose
- The main objective of CPU scheduling algorithm is to increase CPU utilization in job processing and and gives maximum throughput(output).
Advantages
Scheduling algorithms are an essential component of operating systems that manage and allocate resources to processes or tasks. Some of the advantages of scheduling algorithms are as follows:
Resource utilization/Efficiency: Scheduling algorithms help to maximize the utilization of system resources such as CPU, memory, and I/O devices, by ensuring that processes are allocated resources in an efficient manner.
Fairness: Scheduling algorithms help to ensure fairness in the allocation of resources by preventing any process from monopolizing system resources for an extended period of time.
Priority management: Scheduling algorithms to allow for processes to be executed in order of priority, ensuring that critical processes are executed first and that processes with lower priorities are executed only when the system resources are available.
Responsiveness: Scheduling algorithms to ensure that processes are executed in a timely manner, making the system more responsive and efficient in handling user requests.
Deadline management: Real-time scheduling algorithms ensure that processes with strict deadlines are executed in a timely manner, which is critical in applications such as aviation, medical devices, and industrial control systems.
Multitasking: Scheduling algorithms enable multiple processes to run concurrently on a single processor, allowing for multitasking and efficient utilization of system resources.
Thus, scheduling algorithms are critical for the efficient and effective operation of operating systems, ensuring that resources are utilized in an optimal manner while ensuring fairness, responsiveness, and priority management.
Disadvantages
There are several disadvantages associated with scheduling algorithms used in operating systems, some of which are as follows:
Overhead: Scheduling algorithms can add overhead to the system, as the scheduler needs to constantly switch between different processes, which can lead to reduced performance and increased latency.
Complexity: Scheduling algorithms can be complex and difficult to implement, especially if they need to take into account factors such as priority, resource availability, and real-time constraints.
Starvation: Certain scheduling algorithms can result in starvation, where some processes are continually postponed or delayed due to a lack of resources or low priority.
Deadlock: Poorly designed scheduling algorithms can lead to deadlocks, where processes are unable to proceed due to waiting for resources that are being held by other processes.
Inefficiency: Certain scheduling algorithms may be inefficient in terms of resource utilization or in meeting deadlines, especially if processes have different priorities or burst times.
Overall, scheduling algorithms are essential for the proper functioning of operating systems, but they need to be carefully designed and implemented to avoid the above-mentioned disadvantages.
Scheduling Criteria/Terminology
When selecting a CPU scheduling algorithm, several scheduling criteria are considered to ensure optimal performance and efficiency. The main criteria include:
- CPU Utilization:
- The scheduling algorithm aims to keep the CPU busy as much as possible by producing positive output.
- Throughput:
- Throughput is the amount of work/job completed in a unit of time.
- Throughput refers to the total number of processes that can be completed within a given time period.
- A good scheduling algorithm should aim to maximize throughput to increase the overall system productivity.
- Arrival Time:
- When a process enters in a ready queue(formed inside the RAM) for processing.
- Time at which the process arrives in the ready queue.
- CPU Time/Burst Time/Execution Time/Process Time/Running Time:
- The time required/used by a process to complete its execution by the CPU.
- The time needed in milliseconds by a process for its execution.
Waiting time:
- Waiting time is the time a process spends waiting in the ready queue (of memory) before it gets a chance to execute or its turn to get on the CPU for processing.
- Minimizing waiting time is crucial to ensure fairness and responsiveness in executing processes.
- Waiting Time = Turn Around Time – Burst Time.
Response time:
- It is the amount of time in which the request was submitted until the first response/output is produced.
- In other words, the response time is the total elapsed time from when a request is made to when it is completed.
- For interactive systems, minimizing response time is essential to provide a smooth and interactive user experience.
Turnaround Time:
- Turnaround time is the total time taken between the submission of a process/task for execution and the return of the complete output to the user i.e. turnaround time is an amount of time to execute a specific process that includes the total time spent waiting to get into the memory, waiting in the ready queue and executing in the CPU.
- Turnaround time is the total time taken from the submission of a process to its completion.
- Minimizing turnaround time is desirable as it directly impacts the responsiveness and efficiency of the system.
- Turn Around Time = Completion Time – Arrival Time.
- Finish Time:
- When a process is completed finally and exits from the system.
- Overhead:
- Overhead refers to the additional time and resources consumed by the scheduling algorithm itself.
- A good scheduling algorithm should minimize overhead, such as context switches and dispatcher latency, to avoid unnecessary resource consumption.
- Predictability:
- Predictability refers to the ability to estimate and guarantee the timing behavior of processes.
- Real-time systems require deterministic scheduling algorithms to meet strict timing constraints and ensure timely responses to events.
Multiple Processor Scheduling
- Multiple processor scheduling, also known as multiprocessor scheduling, involves efficiently allocating and scheduling processes or threads on systems with multiple processors or cores.
- The objective is to optimize resource utilization and maximize system throughput.
- The choice of use of a multiple-processor scheduling approach depends on the system architecture, workload characteristics, and performance goals.
- The objective is to efficiently utilize available resources, minimize contention, and maximize overall system performance/throughput while meeting specific requirements, such as fairness and responsiveness situations.
- There are several approaches to multiple processor scheduling:-
- Load Balancing:
- Load balancing aims to distribute the workload evenly across all available processors.
- It prevents situations where some processors are idle while others are overloaded.
- Load-balancing algorithms monitor the workload on each processor and migrate processes or threads between processors to achieve a balanced distribution.
- Task Partitioning:
- Task partitioning divides a large task or job into smaller subtasks that can be executed concurrently on different processors.
- This approach is particularly useful for parallelizable tasks where independent subtasks can be executed simultaneously.
- Gang Scheduling:
- Gang scheduling involves scheduling a group or “gang” of related processes or threads to execute simultaneously on different processors.
- It is commonly used in parallel computing or high-performance computing environments where tasks have dependencies or require synchronized execution.
- Domain Scheduling:
- Domain scheduling assigns specific processors or cores to execute particular types of tasks.
- It can be beneficial when different types of processes or threads have varying resource requirements or priorities.
- For example, real-time tasks may be assigned to dedicated cores to ensure timely execution.
- Global Queue Scheduling:
- Global queue scheduling maintains a single queue for all processes or threads across all processors. Each processor retrieves the next process or thread from the global queue for execution.
- This approach simplifies scheduling decisions but requires efficient synchronization mechanisms to avoid conflicts and ensure fairness.
- Distributed Scheduling:
- In distributed scheduling, each processor has its local queue of processes or threads, and scheduling decisions are made independently by each processor.
- This approach reduces synchronization overhead but may lead to load imbalance if not carefully managed.
- Hybrid Approaches:
- Hybrid approaches combine multiple scheduling techniques to exploit the advantages of different strategies.
- For example, a system may employ load balancing at the global level while using gang scheduling or domain scheduling for specific types of tasks.
- Load Balancing:
Real Time Scheduling
- Real-time scheduling is a specific type of scheduling used in systems where the timely execution of tasks or processes is critical.
- Real-time systems are often found in domains such as industrial control systems, embedded systems, robotics, and multimedia applications.
- Real-time scheduling aims to guarantee that tasks meet their timing constraints and provide timely responses.
- Real-time tasks are classified into two main categories:
- Hard Real-Time Tasks:
- Hard real-time tasks have strict deadlines that must be met. If a task misses its deadline, it can lead to system failure or undesirable consequences.
- Scheduling algorithms for hard real-time tasks focus on meeting deadlines with high certainty.
- Soft Real-Time Tasks:
- Soft real-time tasks have timing constraints but allow some degree of deadline violation. If a soft real-time task misses its deadline occasionally, it may still be acceptable.
- Scheduling algorithms for soft real-time tasks focus on meeting deadlines as much as possible while optimizing other performance criteria.
- Hard Real-Time Tasks:
- Real-time scheduling algorithms employ different strategies to ensure timely execution.
- Real-time scheduling also considers additional factors such as task dependencies, resource sharing, synchronization, and interrupt handling to ensure accurate and timely execution.
- The choice of a real-time scheduling algorithm depends on the specific requirements, timing constraints, and characteristics of the real-time system being designed or implemented.
- Some commonly used real-time scheduling algorithms include:-
- Rate-Monotonic Scheduling (RMS):
- RMS is a static priority-based scheduling algorithm where tasks with shorter periods (higher rates) are assigned higher priorities. RMS assumes that tasks are periodic and guarantees that all deadlines are met if the system is schedulable. However, it may lead to suboptimal CPU utilization if the priorities assigned are not optimal.
- Earliest Deadline First (EDF):
- EDF is a dynamic priority-based scheduling algorithm where tasks with the earliest deadlines are given the highest priority.
- EDF optimally schedules tasks and guarantees that deadlines are met if the system is schedulable.
- It provides better CPU utilization compared to RMS but requires runtime overhead to maintain and update priorities.
- Deadline Monotonic Scheduling (DMS):
- DMS is a static priority-based scheduling algorithm similar to RMS but assigns priorities based on task deadlines instead of periods. Tasks with shorter deadlines are assigned higher priorities.
- DMS is less flexible than EDF but provides better CPU utilization when deadlines are more critical than periods.
- Fixed-Priority Preemptive Scheduling:
- In this approach, each task is assigned a fixed priority, and the scheduler preemptively switches to higher-priority tasks when necessary.
- This scheduling algorithm allows for straightforward implementation and analysis, but schedulability analysis is required to ensure deadlines are met.
- Dynamic-Priority Preemptive Scheduling:
- Dynamic-priority preemptive scheduling adjusts task priorities dynamically based on their urgency, deadlines, or other factors.
- This approach provides more flexibility and responsiveness but requires careful priority management to ensure schedulability and avoid priority inversion or priority inversion due to inheritance issues.
- Rate-Monotonic Scheduling (RMS):
Types of CPU Scheduling Algorithms
[A.] On the basis of the involvement of the CPU with the process, they are broadly grouped into two categories-
- Preemptive Scheduling Algorithm
- Non-Preemptive Scheduling Algorithm
(a.) Preemptive Scheduling Algorithm
- A preemptive scheduling algorithm is a type of CPU scheduling algorithm used in operating systems where a running process can be interrupted and its execution can be temporarily stopped to allocate the CPU to another new process.
- In a pre-emptive scheduling algorithm, the CPU can be taken away from a process and given to another process at any time.
- In this, preemption can occur at any time, either because a new process with a higher priority arrives, or because a process with a higher priority becomes ready to run.
- In preemptive scheduling, the scheduler determines which process should be given the CPU based on its priority or the amount of time it has already consumed. The scheduler can interrupt a running process at any time to allocate the CPU to another process.
- Preemptive scheduling algorithms ensure that high-priority processes are executed first and that processes with longer execution times do not monopolize the CPU.
- This type of scheduling is often used in real-time systems where processes need to meet strict deadlines.
- The main advantage of preemptive scheduling algorithms is that they can ensure that high-priority processes get executed promptly, reducing the average response time of processes.
- The overhead/disadvantage associated with context switching, which involves saving the state of the currently running process and restoring the state of the new process, can impact the overall performance of the system.
- Preemptive scheduling algorithms are more complex than non-preemptive scheduling algorithms, but they offer greater flexibility and can provide better performance and responsiveness in certain situations.
- Some popular preemptive scheduling algorithms include Round Robin, Shortest Remaining Time First (SRTF), and Priority Scheduling.
(b.) Non-Preemptive Scheduling Algorithm
- In non-preemptive scheduling, a process is not interrupted once it starts running on the processor. The process will run until it completes or blocks for some reason, such as waiting for input/output or a semaphore.
- In non-preemptive scheduling, the CPU is allocated to a process for a fixed time or until the process finishes execution, whichever comes first. Once the allocated time is up, the CPU is made available to other processes waiting to run.
- Non-preemptive scheduling is also known as cooperative scheduling because processes cooperate with each other by voluntarily releasing the CPU once they are done with their work.
- Non-preemptive scheduling algorithms have the advantage of being simple and easy to implement. However, they may not be the most efficient in terms of resource utilization or meeting deadlines, especially if the processes have different priorities or burst times.
- Some popular non-preemptive scheduling algorithms include First Come First Serve (FCFS), Shortest Job First (SJF), and Priority Scheduling.
[B.] There are the following types of scheduling algorithms used by the CPU during processing –
- First Come First Serve (FCFS) Scheduling Algorithms
- Shortest Job First (SJF)/Shortest Job Next(SJN) Scheduling Algorithms
- Shortest Remaining Time(SRT) Scheduling Algorithms
- Priority Based Scheduling Algorithms
- Round Robin(RR) Scheduling Algorithms
- Multi Level Queue Scheduling Algorithms
- Multi-Level Feedback Queue Scheduling Algorithms
(i) First Come First Serve (FCFS) Scheduling Algorithms :
- In the FCFS scheduling algorithm, the job that arrived first in the ready queue of memory is allocated first to the CPU time until it completes or is blocked, and then the next process is scheduled.
- FCFS is a non-preemptive type of scheduling algorithm.
- This is used in Batch Systems of processing.
(ii) Shortest Job First (SJF)/Shortest Job Next(SJN) Scheduling Algorithms
- This algorithm schedules processes based on their estimated CPU burst time, with the shortest job being scheduled first.
- This algorithm can minimize average waiting time and turnaround time but requires an accurate estimation of CPU burst times.
(iii) Shortest Remaining Time(SRT) Scheduling Algorithms
- It is a pre-emptive type of scheduling algorithm.
- In the SRT scheduling algorithm, the process with the shortest remaining burst time is given the CPU next.
- It is similar to the Shortest Job First (SJF) algorithm but with preemption. When a new process arrives or a running process gets preempted, the CPU checks all the remaining processes and picks the process with the shortest remaining burst time.
- SRT is an optimal algorithm because it minimizes the average waiting time for the processes, but it can lead to starvation of long processes if there are many short processes in the system.
- SRT scheduling algorithm can be implemented using a priority queue where the priority of a process is its remaining burst time. Whenever a process arrives or gets preempted, the priority queue is updated, and the process with the highest priority is given the CPU.
(iv) Priority Based Scheduling Algorithms
- This algorithm assigns a priority level to each process, and schedules processes with higher priority levels first.
- Priority can be assigned to a process that is based on various factors, such as type of process, user priority, CPU usage history, etc.
(v) Round Robin(RR) Scheduling Algorithms
- This algorithm allocates CPU time to processes in fixed time slices or called quantum and rotates among the processes in a circular manner.
- If a process completes its quantum, it is placed at the end of the ready queue.
(vi) Multi-Level Queue Scheduling Algorithms
- This algorithm divides the ready queue into multiple queues, each with its own scheduling algorithm and priority level.
- Processes are placed in the appropriate queue based on their attributes, such as priority, CPU usage, or I/O requirements.
(vii) Multilevel Feedback Queue Scheduling
- This algorithm is a variation of multilevel queue scheduling that allows processes to move between different queues based on their performance and CPU usage.
- Processes that use a lot of CPU time are moved to lower-priority queues to prevent them from hogging the CPU.
0 Comments