In this blog post, we’ll explain what CPU scheduling is, how the program execution order is determined, and explore efficient system resource management methods.
When we listen to music while writing a document on a computer, we think two programs are running simultaneously. However, in reality, these programs are executed alternately in very short time intervals. This is due to CPU (Central Processing Unit) scheduling, part of the computer operating system. When a program is to be executed, the computer operating system loads the program into main memory and registers it in the ‘task queue’, a list of programs waiting to run. The operating system selects one program from the task queue to execute on the CPU. Once execution completes, it removes the program from the task queue.
A single CPU can execute only one program at a time. So, how can we make it appear that two programs, A and B, are running simultaneously? Programs are registered in the task queue in the order they request execution, and A and B are executed sequentially according to this order. If program A takes a long time to execute, program B must wait longer, making it appear as if the programs are not running simultaneously. However, if A and B are executed alternately at regular intervals, it appears as if both programs are running at the same time.
To achieve this, the CPU’s execution time is divided into several short intervals, with one program executing during each interval. Here, the execution of a program within one interval is called ‘slice execution’, and the time a program executes within each interval is called the ‘slice time’. The length of the slice time is fixed. The slice execution of A and B is, in principle, repeated alternately until both programs terminate. However, if one program terminates first, the remaining program continues to execute.
Meanwhile, while one program’s interval execution is in progress, the other program waits in the task queue. When A’s interval execution ends, A’s execution halts, and the program to execute during the next interval time is selected. The time required to prepare B for execution after A halts is called the ‘switching time,’ which is very short compared to the interval time. During the switching time, the state of A executed up to that point is saved, and B’s previous state is retrieved to execute B. Furthermore, even if the same program continues execution, the operating system must determine which program should run next, so a switchover time is always required between execution intervals.
Additionally, to prevent data loss during program switching, the operating system periodically saves and restores each program’s state. This process is called ‘context switching,’ and during it, the operating system must precisely remember where each program last left off. Although this context switching may take slightly longer than the switching time itself, it makes the program appear to run continuously without interruption.
The time taken from when a program is registered in the task queue until it terminates is called the ‘total processing time’. This time is the sum of the ‘total execution time’ (the time purely spent executing the program), the ‘switching time’, and the ‘waiting time’ spent waiting in the task queue for execution. When a program with a total execution time longer than the interval time runs, the number of interval executions increases, raising the total sum of switch times. However, programs with a total execution time shorter than or equal to the interval time complete within a single interval time and are immediately followed by the next program.
Now, consider the case where programs A, B, and C are executed. If program C is executed while A is running and B is waiting in the job queue, C is registered after B. Consequently, C executes after both A and B have completed their interval runs. If A and B have not yet terminated and require additional interval runs, C is re-registered behind them in the job queue. This results in the state C, A, B, and ultimately, the three programs execute repeatedly in the order they were registered.
Thus, as the number of programs registered in the task queue increases, the waiting time for each program proportionally increases. Therefore, it is necessary to limit the number of programs that can be registered in the task queue to prevent waiting times from exceeding a certain threshold. To achieve this, operating systems sometimes employ a technique called ‘priority scheduling’. Priority scheduling assigns a priority to each program based on its importance and executes programs with higher priority first. This allows for more efficient management of system resources and prevents important tasks from being delayed.
Ultimately, CPU scheduling plays a crucial role in enhancing the efficiency and performance of computer systems. It coordinates the execution order of programs through various scheduling algorithms, providing users with the experience of multiple programs running simultaneously. The role of the operating system in this process is vital, and accurate, efficient scheduling is a key factor determining the overall performance of the system.
