In this blog post, we’ll examine what general-purpose computer functions smartphones actually perform and analyze why we’ve come to recognize only desktops as ‘computers’.
When we say ‘computer,’ what comes to mind is usually a desktop or laptop. These are classified as general-purpose computers. A general-purpose computer, as the name suggests, is a computer that can be used for a wide variety of purposes. Surprisingly, quite a few people don’t recognize smartphones as computers, yet smartphones are indeed general-purpose computers. This is because we can perform countless tasks with smartphones: sending emails, shopping, chatting, watching videos and listening to music, writing documents, and more. The reason for bringing up general-purpose computers is to clarify the scope and terminology of the topic we’ll discuss next. Since the upcoming content concerns the general-purpose computers we commonly think of when we say ‘computer,’ we’ll simply refer to general-purpose computers as computers.
When viewing a computer’s structure hierarchically, hardware sits at the very bottom. All the hardware resources a user needs reside in this hardware layer, but users cannot interact directly with it. Directly utilizing hardware resources is an extremely complex and cumbersome task. That’s why the operating system sits above it. The operating system manages when, where, and how much of the hardware resources are allocated. You’ve likely heard of operating systems like Windows or Android. However, performing the tasks a typical user wants directly through the operating system remains complex and cumbersome. That’s why application software sits on top of the operating system. Users interact with this application software to perform their desired tasks.
With the exception of Microsoft’s DOS, virtually all operating systems support multitasking. Multitasking means running two or more programs simultaneously on a single computer. Here, it’s necessary to clearly define what running a program means. In the narrow sense, a program is running when it has been allocated hardware resources, specifically the Central Processing Unit (CPU), to perform computational tasks. In the broader sense, it also includes a program being in a state where it is ready and waiting to be allocated the CPU. While the narrow sense of execution is easy to understand, the broader sense may feel somewhat unfamiliar. The concept of execution in the broader sense emerged from the following background.
All multitasking is implemented using time-sharing. Time-sharing means dividing time into segments for use. Since a single CPU cannot be assigned to multiple programs simultaneously, time is divided into multiple intervals. The CPU repeatedly assigns specific intervals to specific programs and other intervals to other programs. If time is divided sufficiently finely, the user perceives the programs as running simultaneously. This creates the illusion of having multiple central processing units. Going forward, we will refer to execution in the narrow sense simply as “execution,” and distinguish the broader sense as “time-sharing execution.”
Multitasking doesn’t merely mean watching a drama on the computer while simultaneously surfing the web. Numerous programs can be executing via time-sharing without the user’s awareness. In fact, it’s impossible for a user to perceive every program running in time-sharing mode on a computer. Even when a user believes they are running one program, dozens to hundreds of other programs are already executing via time-sharing. This is where the problem arises. The number of central processing units (CPUs) is generally limited, yet situations can occur where dozens or even hundreds of programs urgently require this resource. At this point, the operating system must intervene to allocate resources appropriately. In other words, the operating system decides when, how much, and to which program to allocate the CPU, a process known as scheduling.
How can an operating system schedule so many programs? While there are differences between operating systems, we’ll use Linux as a representative example here. Unlike Windows, Linux is freely distributed, and all its code is publicly available.
Linux uses CFS (Completely Fair Scheduler) for program scheduling. While the name CFS doesn’t immediately reveal its function, its principle is as follows. CFS classifies programs into 40 priority levels based on their importance, and each program is assigned a weight corresponding to its priority. It also records the total execution time for each program. Whenever the CPU is allocated to a specific program, the total execution time is updated by adding the time that program used the CPU. It periodically swaps out running programs to allocate the CPU to other programs. CFS prioritizes executing the program with the least total execution time, ensuring all programs get a chance to use the CPU.
Furthermore, when updating a program’s total execution time, it adjusts the allocated time by considering the weight based on priority. That is, it makes time pass more slowly for high-priority programs and more quickly for low-priority programs. This is called virtual execution time, and this method ensures programs receive resources fairly according to their priority.
But can CFS handle it even when the number of programs running in time-sharing mode reaches thousands or tens of thousands? Fortunately, CFS maintains sufficient performance even in such situations. CFS uses a data structure called a red-black tree to manage programs. It places all programs waiting for the CPU into the red-black tree for management, periodically selecting a program to execute, removing it from the tree, and then reinserting it. Thanks to the properties of the red-black tree, selecting and executing a program can be done very quickly. Even if the number of programs running in time-sharing mode increases exponentially, the time required for this operation increases only linearly.
Of course, the scheduler doesn’t solve every problem. For instance, for a program to run, its associated data must reside in main memory (RAM), so the capacity of main memory can limit the number of programs that can run. Furthermore, the performance of the central processing unit (CPU) itself is another factor limiting the number of programs that can be executed. However, these issues fall outside the scope of the scheduler. Therefore, in terms of fairness and performance, CFS can be considered an excellent scheduler.
