Was ist CPU-Scheduling?
CPU schedulingis a process of determining which process owns the CPU to run while another process is suspended. The main task of CPU scheduling is to ensure that whenever the CPU remains idle, the operating system chooses at least one of the processes available in the ready queue to run. The selection process is performed by the CPU scheduler. It selects one of the processes in memory that are ready to run.
In this CPU planning tutorial, you will learn:
- What is CPU Scheduling?
- Types of CPU Scheduling
- Important CPU scheduling terminologies
- CPU Scheduling Criteria
- Interval Timer
- What is Dispatcher?
- Types of CPU Scheduling Algorithms
- First come, first served
- Shortest remaining time
- Priority-Based Scheduling
- Round Robin Scheduling
- Shortest job first
- Scheduling of queues at multiple levels
- The purpose of a scheduling algorithm
Types of CPU Scheduling
Here are two types of scheduling methods:
With preemptive scheduling, the tasks are usually assigned with their priorities. Sometimes it's important to run a higher-priority task before another lower-priority task, even if the lower-priority task is still running. The lower priority task lasts for some time and resumes when the higher priority task finishes its execution.
With this type of scheduling method, the CPU was allocated to a specific process. The process that is keeping the CPU busy frees the CPU either by switching contexts or by terminating. It is the only method that can be used for different hardware platforms. That's because it doesn't require any special hardware (such as a timer) like preemptive scheduling.
When is planning preventive or not preemptive?
Consider these four parameters to determine whether planning is preemptive or non-preemptive:
- A process changes from the running to the waiting state.
- Certain processes transition from the running state to the ready state.
- Certain processes transition from the wait state to the ready state.
- The process has completed its execution and terminated.
Only conditions 1 and 4 apply, the scheduling is referred to as non-preemptive.
All other planning is preventive.
Important CPU scheduling terminologies
- Burst Time/Execution Time:It is a time required for the process to complete execution. It is also called run time.
- Arrival time:when a process enters a ready state
- end time:when the process completes and exits a system
- Multiprogramming:Multiple programs that can coexist in memory.
- Jobs:It's a kind of program without any kind of user interaction.
- User:It's a kind of user interaction program.
- Procedure:It is the reference used for both the job and the user.
- CPU/IO burst cycle:Characterizes process execution that alternates between CPU and I/O activity. CPU times are usually shorter than I/O times.
CPU Scheduling Criteria
A CPU scheduling algorithm tries to maximize and minimize:
CPU usage:CPU usage is the main task where the operating system has to ensure that the CPU stays as busy as possible. It can be between 0 and 100 percent. However, for the RTOS, it can range from 40 percent for low-level to 90 percent for the high-level system.
Throughput:The number of processes that complete their execution per unit of time is known as throughput. So when the CPU is busy executing the process, work is being done at that time, and the work completed per unit of time is called throughput.
Waiting period:The wait time is an amount that a given process must wait in the ready queue.
Reaction time:It is a period of time that the request has been submitted until the first response is produced.
change of sides:Turnaround time is a time it takes for a specific process to run. It is the calculation of the total time spent getting into memory, waiting in the queue, and executing on the CPU. The time between the time the process is submitted and the time it is completed is the processing time.
Timer interrupt is a method closely related to preemption. When a specific process gets the CPU allocation, a timer can be set to a specific interval. Both timer interrupt and preemption force a process to return CPU before its CPU burst completes.
Most multiprogrammed operating systems use some kind of timer to prevent a process from stalling the system forever.
What is Dispatcher?
It is a module that provides control of the CPU to the process. The dispatcher should be fast so that it can run on every context switch. Dispatch latency is the time it takes for the CPU scheduler to stop one process and start another.
Functions performed by the dispatcher:
- context switch
- Switch to user mode
- Move to the right place in the newly loaded program.
Types of CPU Scheduling Algorithms
There are mainly six types of process scheduling algorithms
- First come, first served (FCFS)
- Shortest-Job-First (SJF) Scheduling
- Shortest remaining time
- priority planning
- Round Robin Scheduling
- Multi-level queue scheduling
First come, first served
First Come First Serve is the full form of FCFS. It is the simplest and most simplistic CPU scheduling algorithm. With this type of algorithm, the process requesting the CPU gets the CPU allocation first. This scheduling method can be managed with a FIFO queue.
When the process enters the ready queue, its PCB (Process Control Block) is connected to the end of the queue. So when the CPU becomes free, it should be allocated to the process at the front of the queue.
Properties of the FCFS method:
- It offers a non-preemptive and a preemptive scheduling algorithm.
- Jobs are always performed on a first come, first served basis
- It's easy to implement and use.
- However, this method is poorly performing and the overall latency is quite high.
Shortest remaining time
The full form of SRT is the shortest time remaining. It is also known as preemptive SJF scheduling. With this method, the process is assigned to the task that is closest to its completion. This technique prevents a newer, ready process from catching the completion of an older process.
Properties of the SRT scheduling method:
- This method is mostly used in batch environments where short jobs need to be given priority.
- This is not an ideal method to implement on a shared system where the required CPU time is unknown.
- Associate each process with the length of its next CPU burst. The operating system uses these lengths, which helps to schedule the process with the shortest possible time.
Priority scheduling is a technique for scheduling processes based on priority. In this method, the scheduler selects the tasks to be performed according to priority.
Priority scheduling also helps the operating system accommodate priority assignments. The higher priority processes should run first while jobs with the same priority run on a round robin or FCFS basis. Priority can be set based on memory requirements, time requirements, etc.
Round Robin Scheduling
Round Robin is the oldest and simplest scheduling algorithm. The name of this algorithm comes from the round robin principle, where each person in turn gets an equal share of something. It is mainly used for scheduling algorithms in multitasking. This algorithm method helps in starvation execution of processes.
Features of round robin scheduling
- Round Robin is a hybrid model that is clock controlled
- The time slice allocated to a specific task to be processed should be minimal. However, it can vary for different processes.
- It is a real-time system that responds to the event within a specified time limit.
Shortest job first
SJF is a full form of (Shortest Job First) is a scheduling algorithm designed to choose the process with the shortest execution time for the next execution. This scheduling method can be preemptive or non-preemptive. It significantly reduces the average wait time for other processes waiting to run.
Properties of SJF Scheduling
- It is assigned to each job as a unit of time for completion.
- With this method, if the CPU is available, the next process or job with the shortest execution time runs first.
- It is implemented with a non-preemptive policy.
- This algorithm method is useful for batch processing where waiting for jobs to complete is not critical.
- It improves job performance by offering shorter jobs that should be run first and tend to have a shorter turnaround time.
Scheduling of queues at multiple levels
This algorithm separates the completed queue into several separate queues. In this method, processes are assigned to a queue based on a specific property of the process, such as process priority, amount of memory, etc.
However, this is not an independent scheduling OS algorithm as it has to use other types of algorithms to schedule the jobs.
Feature of Multi-Level Queue Scheduling:
- Multiple queues should be maintained for processes with some characteristics.
- Each queue can have its own scheduling algorithms.
- Priorities are assigned to each queue.
The purpose of a scheduling algorithm
Here are the reasons for using a scheduling algorithm:
- The CPU uses scheduling to improve its efficiency.
- It helps you allocate resources between competing processes.
- The maximum utilization of the CPU can be achieved through multiprogramming.
- The processes to be executed are in the ready queue.
- CPU scheduling is a process of determining which process owns the CPU to run while another process is suspended.
- With preemptive scheduling, the tasks are usually assigned with their priorities.
- With the non-preemptive scheduling method, the CPU was allocated to a specific process.
- The burst time is the time it takes for the process to complete execution. It is also called run time.
- CPU usage is the main task where the operating system has to ensure that the CPU stays as busy as possible.
- The number of processes that complete their execution per unit of time is known as throughput.
- The wait time is an amount that a given process must wait in the ready queue.
- It is the amount of time the request has been sent before the first response is produced.
- Processing time is the time it takes to complete a specific process.
- Timer interrupt is a method closely related to preemption.
- A dispatcher is a module that provides control of the CPU to the process.
- Six types of process scheduling algorithms are: First Come First Serve (FCFS), 2) Shortest-Job-First (SJF) Scheduling, 3) Shortest Remaining Time, 4) Priority Scheduling, 5) Round Robin Scheduling, 6) Multilevel Queue Scheduling.
- In the first-come-first-serve method, the process requesting the CPU gets the CPU allocation first.
- In the shortest time remaining, the process is assigned to the task that is closest to its completion.
- In priority scheduling, the scheduler selects the tasks to be performed according to priority.
- Round robin scheduling works on the principle that each person in turn gets an equal share of something.
- In Shortest job first, the shortest execution time should be selected for the next execution.
- The multi-level scheduling method separates the ready queue into several separate queues. With this method, processes are assigned to a queue based on a specific property.
- The CPU uses scheduling to improve its efficiency.
You might like:
- Round robin scheduling algorithm with example
- Process synchronization: Critical section issue in the operating system
- Process planning in the operating system: long-, medium-, short-term planner
- Priority Scheduling Algorithm: Preemptive, Non-Preemptive BEISPIEL
- Difference between microprocessor and microcontroller
What are the CPU scheduling algorithms in operating system? ›
- First Come, First Served (FCFS) Want to keep. ...
- Shortest Job Next (SJN) For this algorithm, the OS needs to know (or guess) the time each program will take to run. ...
- Priority Scheduling. ...
- Shortest Remaining Time. ...
- Round Robin (RR) scheduling. ...
- Multilevel Queues.
CPU scheduling refers to the switching between processes that are being executed. It forms the basis of multiprogrammed systems. This switching ensures that CPU utilization is maximized so that the computer is more productive. There are two main types of CPU scheduling, preemptive and non-preemptive.Which is the best CPU scheduling algorithm in OS? ›
The FCFS is better for a small burst time. The SJF is better if the process comes to processor simultaneously. The last algorithm, Round Robin, is better to adjust the average waiting time desired.Why are CPU scheduling algorithms important? ›
The primary objective of CPU scheduling is to ensure that as many jobs are running at a time as is possible. On a single-CPU system, the goal is to keep one job running at all times. Multiprogramming allows us to keep many jobs ready to run at all times.What is CPU scheduling basic concepts in OS? ›
CPU scheduling is a process that allows one process to use the CPU while the execution of another process is on hold(in waiting state) due to unavailability of any resource like I/O etc, thereby making full use of CPU. The aim of CPU scheduling is to make the system efficient, fast, and fair.What is the purpose of scheduling algorithms in OS? ›
The purpose of a scheduling algorithm is to provide: Maximum CPU utilization. Minimum turnaround time. Fair allocation of CPU.What is the simplest CPU schedule algorithm? ›
First come, first serve
This means FCFS is non-preemptive scheduling. It is the easiest and simplest CPU scheduling algorithm while SJF is a bit more complex, it tries to execute the shortest jobs first to minimize the overall completion time. FCFS is managed on the FIFO queue(First in first out).
The simplest best-effort scheduling algorithms are round-robin, fair queuing (a max-min fair scheduling algorithm), proportionally fair scheduling and maximum throughput. If differentiated or guaranteed quality of service is offered, as opposed to best-effort communication, weighted fair queuing may be utilized.What is the most used scheduling algorithm? ›
Priority scheduling is a non-preemptive algorithm and one of the most common scheduling algorithms in batch systems. Each process is assigned a priority. Process with highest priority is to be executed first and so on. Processes with same priority are executed on first come first served basis.What are the 5 main types of scheduling? ›
- Time-slot scheduling.
- Wave scheduling.
- Wave and walk-in appointment scheduling.
- Open appointment scheduling.
- Double scheduling.
- Cluster scheduling.
- Matrix scheduling.
- 40/20 scheduling.
What are the three basic scheduling States in OS? ›
The operating system considers a process to be in one of three basic scheduling states: waiting, ready, or executing.What is the conclusion of CPU scheduling algorithms? ›
Conclusion. CPU scheduling is the task performed by CPU that decides the way processed would be executed. CPU resources are allocated to a process for only a limited period of time and then those resources are taken back. A running process could be interrupted to execute a higher priority process.What are advantages of scheduling algorithms? ›
As calculating the algorithm for orders is so simple, it is easy for team members of any experience or skill level to manage order scheduling and write and understand code with ease. This is very beneficial in saving time and labor as scheduling can be performed quickly and easily.What is CPU scheduling in real life examples? ›
A real-life example of the FCFS method is buying a movie ticket on the ticket counter. It is the simplest form of a CPU scheduling algorithm. It is a Non-Preemptive CPU scheduling algorithm, so after the process has been allocated to the CPU, it will never release the CPU until it finishes executing.Why is scheduling important in operations? ›
Scheduling is a critical component of operations management as it helps ensure that products are manufactured promptly and efficiently. When done correctly, it can help to minimise costs and maximise profits.What are the scheduling algorithms explain? ›
Scheduling algorithms tell the CPU which will be the next process to have CPU time. The main goal of scheduling algorithms is to Maximize Throughput. Scheduling algorithms can be preemptive and non-preemptive.What is the main advantage of having a good and efficient CPU scheduling? ›
The aim of CPU scheduling is to make the system efficient, and quick. In other words, basically CPU scheduling is use for the selection of processes, when a process leaves the CPU idle next process for the CPU is to be selected and for this purpose many CPU scheduling algorithms are there which we can use.Which scheduling method is best? ›
- Mathematical analysis. Using mathematical logic, you can calculate your project timeline with all the factors of your project scope considered. ...
- Duration compression. ...
- Simulation. ...
- Resource-leveling heuristics. ...
- Gantt charts. ...
- Task lists. ...
However, I just purchased the book - Windows Internals - Part 1 (7th edition) and it states that the Windows scheduling algorithm is a priority driven preemptive scheduling system (page 214).Which of the following is a type of CPU scheduling algorithm? ›
Round Robin is a scheduling algorithm in which the process executes for a fixed CPU quantum time then the next process gets executed then the next process and goes on. Hence, the correct answer is "option 3".
Which scheduling algorithm is used in OS? ›
First Come First Serve (FCFS) Scheduling Algorithm
It is a non-preemptive scheduling algorithm as the priority of processes does not matter, and they are executed in the manner they arrive in front of the CPU. This scheduling algorithm is implemented with a FIFO(First In First Out) queue.