In this blog post, we will look at what functions smartphones actually perform as general-purpose computers and analyze why we have come to recognize only desktops as “computers.”
When we think of a “computer,” the first thing that comes to mind is probably a desktop or laptop computer. These are classified as general-purpose computers. As the name suggests, general-purpose computers can be used for a variety of purposes. Surprisingly, many people do not recognize smartphones as computers, but smartphones are also clearly general-purpose computers. This is because we can send emails, shop, chat, watch videos, listen to music, write documents, and perform countless other tasks using our smartphones. The reason I mentioned general-purpose computers is to clarify the scope and terminology of the topics I will be discussing. The topics I will be covering are about general-purpose computers, which is what we usually think of when we think of “computers,” so I will refer to them as computers.
If we look at the structure of a computer in a hierarchical manner, the hardware is located at the bottom. All the hardware resources that users need are in this hardware layer, but users cannot interact directly with this layer. This is because using hardware resources directly is a very complex and cumbersome task. So the operating system is placed above it. The operating system manages when, where, and how much hardware resources are allocated. You may have heard of operating system names such as Windows or Android. However, it is still complicated and cumbersome for a general user to perform the desired task directly through the operating system. That’s why applications are built on top of the operating system. Users can interact with these applications and perform the desired task.
With the exception of Microsoft’s DOS, virtually all operating systems support multitasking. Multitasking is the simultaneous execution of two or more programs on a single computer. Here, it is necessary to clarify the meaning of program execution. In a narrow sense, the execution of a program means that it is allocated a hardware resource called a central processing unit (CPU) to perform computational tasks. In a broad sense, it also includes the program waiting in a state where it is ready to be allocated a central processing unit. While the execution in the narrow sense is easy to understand, the execution in the broad sense may feel somewhat unfamiliar. The concept of execution in the broad sense emerged from the following background.
All multitasking is implemented in a time-sharing manner. Time-sharing means that time is divided and used. Since one central processing unit cannot be allocated to multiple programs at the same time, the task is to divide the time into multiple sections and allocate a specific program to one section and another program to another section, repeating the process. When time is divided into small enough chunks, the user perceives the program as if it is running simultaneously. This makes it appear as if there are multiple central processing units. In the future, execution in the narrow sense will be referred to as execution, and execution in the broad sense will be referred to as time-sharing execution.
Multitasking does not simply mean watching a drama on a computer while surfing the web at the same time. There can be any number of programs running in time-sharing mode without the user’s knowledge. In fact, it is impossible for a user to be aware of all the programs running in time-sharing mode on a computer. Even when a user thinks that a program is running, at least tens or hundreds of other programs are already running in time-sharing mode. This is where the problem arises. Generally, the number of central processing units is limited, and there may be situations where the number of programs that need this resource exceeds tens or hundreds. At this point, the operating system must intervene and allocate resources appropriately. In other words, the operating system decides when, how much, and to which program to allocate the central processing unit, which is called scheduling.
How can an operating system schedule so many programs? Of course, there are differences between operating systems, but here I will explain Linux as a representative example. This is because Linux, unlike Windows, is distributed free of charge and all of its code is open source.
Linux uses the Completely Fair Scheduler (CFS) for program scheduling. CFS is difficult to understand from its name alone, but its principle is as follows. CFS classifies programs into 40 priority levels, and each program is given a weight according to its priority. It also records the total execution time of each program. Each time a central processing unit is allocated to a specific program, the total execution time is updated by adding the time that the program has used the central processing unit. Then, the program that is being executed is periodically replaced and the central processing unit is allocated to another program. CFS ensures that all programs have the opportunity to use the central processing unit by prioritizing programs with the lowest total execution time.
In addition, when updating the total execution time of the program, the allocated time is adjusted by considering the weighting according to the priority. In other words, programs with high priority are given time to run slowly, and programs with low priority are given time to run quickly. This is called virtual execution time, and this method ensures that programs are allocated resources fairly according to their priority.
But can CFS withstand thousands or tens of thousands of programs running in a time-sharing manner? Fortunately, CFS maintains sufficient performance even in such situations. CFS uses a data structure called a red-black tree to manage programs. All programs waiting for the central processing unit are managed by putting them in the red-black tree, and the program to be executed periodically is selected and removed from the red-black tree and then put back in again. Thanks to the characteristics of the red-black tree, the process of selecting and executing a program can be done very quickly. This is because the time required for this task only increases linearly even if the number of programs running in a time-sharing manner increases exponentially.
Of course, the scheduler does not solve all problems. For example, the capacity of the main memory may limit the number of programs that can be executed because the data associated with the program must be in the main memory (RAM) for the program to run. In addition, the performance of the central processing unit itself is a factor that limits the number of executable programs. However, these problems are beyond the scope of the scheduler. Therefore, in terms of fairness and performance, CFS can be said to be a very good scheduler.
