CPU Scheduling: From Basics to Execution Flow
1️⃣ Basic Concepts and Necessity of CPU Scheduling
2️⃣ Management Structure and Selection Criteria of CPU Scheduling
3️⃣ CPU Scheduling Execution Flow
1️⃣ Basic Concepts and Necessity of CPU Scheduling
CPU Scheduling; Who Does the OS Give the CPU to First?
Last week, we examined the concepts of processes and threads, looking at how execution flows are divided and how the operating system manages execution units.
Once you understand these concepts, a natural question arises: when multiple processes and threads exist simultaneously, who should the CPU be allocated to first? If all processes want to run at the same time, what criteria does the operating system use to make that decision?
This week's topic, CPU scheduling, starts from exactly these questions.
CPU 스케줄링; 운영체제는 누구에게 먼저 CPU를 줄까?
지난주에는 프로세스와 스레드의 개념을 살펴보며, 실행의 흐름이 어떻게 나뉘는지 그리고 운영체제가 실행 단위를 어떻게 관리하는지 확인했다.
개념을 익히고 나면 자연스럽게 이런 의문이 생긴다. 여러 프로세스와 스레드가 동시에 존재할 때, CPU는 과연 누구에게 먼저 할당되어야 할까? 모든 프로세스가 동시에 실행되길 원한다면, 운영체제는 어떤 기준으로 CPU를 나눠줄까?
이번 주제인 CPU 스케줄링은 바로 이 질문에서 출발한다.
Why Things Appear to Run Simultaneously
While listening to music, web pages still open instantly and messenger notifications keep coming through. To our eyes, all of these tasks seem to be happening at the same time.
In reality, the CPU can only process one task at a single moment. So are these multiple tasks truly running simultaneously?
The answer lies in rapid context switching. The operating system allocates the CPU to each task in extremely short intervals, taking turns. Because these switches happen so fast, it feels to the human eye as though everything is running at once.
So how does the operating system decide which task to run next? This is the core problem of CPU scheduling.
동시에 실행되는 것처럼 보이는 이유
음악을 듣는 동안에도 웹페이지는 바로 열리고, 메신저 알림은 끊기지 않는다. 우리 눈에는 이 작업들이 모두 동시에 이루어지는 것처럼 보인다.
그런데 사실 CPU는 한 순간에 단 하나의 작업만 처리할 수 있다. 그렇다면 이 여러 작업들은 정말로 동시에 실행되고 있는 걸까?
답은 빠른 전환(Context Switching) 이다. 운영체제는 각 작업에 CPU를 아주 짧은 시간 동안 번갈아 가며 할당한다. 이 전환이 너무 빠르기 때문에 사람의 눈에는 마치 모든 작업이 동시에 돌아가는 것처럼 느껴지는 것이다.
그렇다면 운영체제는 어떤 기준으로 다음 실행할 작업을 결정할까? 이것이 바로 CPU 스케줄링의 핵심 문제다.
The Core Problem of CPU Scheduling
Let's look at the situation more concretely. Opening a web page requires the CPU to process data. Displaying a messenger notification also uses the CPU. Even playing music involves CPU processing.
If all three of these tasks demand the CPU at the same moment, what choice should the operating system make? Should it run whichever task arrived first? Should it process the task that finishes fastest? Should it prioritize tasks that directly interact with the user?
The problem of deciding who gets the CPU, when, and for how long is the essence of CPU scheduling. The criteria chosen will significantly affect the system's response time, processing efficiency, and user experience.
CPU 스케줄링의 핵심 문제
상황을 조금 더 구체적으로 살펴보자. 웹페이지를 열 때는 데이터 처리를 위해 CPU가 필요하고, 메신저 알림을 표시할 때도, 음악이 재생되는 동안에도 CPU 처리가 이루어진다.
만약 이 세 가지 작업이 동시에 CPU를 요구하는 순간이 온다면 운영체제는 어떤 선택을 해야 할까?
먼저 도착한 작업을 실행할까?
가장 빨리 끝나는 작업을 먼저 처리할까?
사용자와 직접 상호작용하는 작업을 우선시할까?
이처럼 CPU를 누구에게, 언제, 얼마나 줄 것인가를 결정하는 문제가 바로 CPU 스케줄링의 핵심이다. 어떤 기준을 선택하느냐에 따라 시스템의 반응속도, 처리 효율, 사용자 경험이 크게 달라질 수 있다.
The Multi-Programming Environment
Modern operating systems keep multiple programs loaded in memory at the same time. Browsers, messengers, music players, and document editors all exist in a ready state simultaneously- meaning there are always multiple candidates requesting execution.
However, the CPU cannot process multiple programs at once. It can only handle one execution flow at a time, so even when many programs exist, the CPU must take turns processing them in order.
The operating system selects one of the ready processes and assigns the CPU to it. In a multi-programming environment, the process of deciding in what order the CPU is used — that is, scheduling — becomes essential.
다중 프로그래밍 환경
현대 운영체제는 여러 프로그램을 동시에 메모리에 올려둔다. 브라우저, 메신저, 음악 재생기, 문서 편집기 등 여러 프로세스가 동시에 준비 상태에 존재한다는 뜻이다. 즉, 실행을 요구하는 대상이 여러 개인 상황이 항상 발생한다.
그러나 CPU는 동시에 여러 프로그램을 처리할 수 있는 장치가 아니다. 한 시점에는 하나의 실행 흐름만 처리할 수 있기 때문에, 여러 프로그램이 존재하더라도 CPU는 순서를 정해 번갈아 가며 처리할 수밖에 없다.
이때 운영체제는 준비 상태에 있는 여러 프로세스 중 하나를 선택해 CPU를 할당한다. 결국 다중 프로그래밍 환경에서는 CPU를 어떤 순서로 사용할지 결정하는 과정, 즉 스케줄링이 필수적으로 요구된다.
The Illusion of Simultaneous Execution
The execution order is never directly exposed to the user. As a result, each program appears to run independently. The browser opens pages on its own; the messenger displays notifications on its own.
But in reality, the operating system is coordinating all of these execution flows behind the scenes. It continuously decides which process to keep in the running state and when to switch to another.
Because this process is invisible to the user, we feel as though multiple programs are running simultaneously. This is what we call the illusion of concurrent execution — and making this illusion feel natural is one of the key roles of CPU scheduling.
사용자가 느끼는 동시 실행의 착시
실행 순서는 사용자에게 직접 노출되지 않는다. 그 결과 각 프로그램은 마치 독립적으로 실행되는 것처럼 보인다. 브라우저는 브라우저대로 페이지를 열고, 메신저는 메신저대로 알림을 표시한다.
하지만 실제로는 운영체제가 이 모든 실행 흐름을 보이지 않는 곳에서 조율하고 있다. 어떤 프로세스를 실행 상태로 둘 것인지, 언제 다른 프로세스로 전환할 것인지를 운영체제가 끊임없이 결정한다.
이 과정이 사용자 눈에 보이지 않기 때문에, 우리는 여러 프로그램이 동시에 실행되는 것처럼 느끼게 된다. 이것이 바로 동시 실행의 착시다. 그리고 이 착시를 자연스럽게 만드는 것이 곧 CPU 스케줄링의 역할이기도 하다.
The Secret of Apparent Simultaneous Execution
Why does it look like multiple programs are running at the same time? As mentioned, the CPU handles only one task at a time. Execution targets are processed one by one in order, not simultaneously.
The secret is in execution switching. The operating system pauses the currently running process and switches to another. When needed, it returns to the previous process. Because this switching repeats at very high speed, it feels to the user as though multiple programs are operating at once.
The key point is that multiple processes are not truly running at the same time. The operating system rapidly swaps out which process is using the CPU — this is the actual mechanism behind multi-programming environments.
실행 전환: 동시 실행의 비밀
왜 여러 프로그램이 동시에 실행되는 것처럼 보이는 걸까? 앞서 말했듯 CPU는 한 시점에 하나의 작업만 처리한다. 실행 대상은 동시에 처리되는 것이 아니라 순서를 정해 하나씩 처리된다.
그 비밀은 실행 전환에 있다. 운영체제는 현재 실행 중인 프로세스를 잠시 멈추고 다른 프로세스로 전환한다. 그리고 다시 필요해지면 이전에 실행하던 프로세스로 돌아온다. 이 전환이 매우 빠른 속도로 반복되기 때문에, 사용자 입장에서는 여러 프로그램이 동시에 작동하는 것처럼 느껴지는 것이다.
여기서 중요한 점은, 여러 프로세스를 진짜로 동시에 실행하는 것이 아니라는 사실이다. 운영체제가 실행 대상을 빠르게 바꾸면서 CPU를 나눠 쓰는 방식, 이것이 다중 프로그래밍 환경의 실제 동작 원리다.
How Is the Next Process Selected?
We now know the CPU alternates between multiple execution targets. A natural question follows: among the many processes in the ready state, who gets the CPU first?
This is not simply a matter of ordering. Which task runs first directly affects the overall behavior and performance of the system. If a heavy task occupies the CPU for a long time, lighter tasks the user is waiting for will be delayed accordingly.
So who makes this decision? The operating system does. It judges what criteria to use when selecting the next process to run, and this judgment directly affects the response speed and efficiency that users experience.
Ultimately, how execution order is determined governs the system's performance and capability. This is why CPU scheduling is considered a core responsibility of the operating system, not just a routine management task.
실행 대상은 어떻게 선택될까?
CPU가 여러 실행 대상을 번갈아 처리한다는 것을 알았다. 그렇다면 자연스럽게 다음 질문이 생긴다. 준비 상태에 있는 여러 프로세스 중 누가 먼저 CPU를 사용할 것인가?
이 선택은 단순한 순서의 문제가 아니다. 어떤 작업을 먼저 실행하느냐에 따라 시스템 전체의 동작 방식과 성능이 직접적으로 달라진다. 예를 들어 무거운 작업이 CPU를 오래 점유하면, 사용자가 기다리는 가벼운 작업은 그만큼 늦게 처리된다.
그렇다면 이 순서는 누가 결정하는 걸까? 바로 운영체제다. 운영체제는 어떤 기준으로 다음 실행할 프로세스를 선택할지 판단하며, 이 판단이 사용자가 체감하는 반응 속도와 시스템 효율에 직결된다.
결국 실행 순서를 어떻게 정하느냐가 시스템의 성능과 가능성을 좌우한다. 이것이 CPU 스케줄링이 단순한 관리 기법을 넘어 운영체제의 핵심 역할로 다뤄지는 이유다.
The Ready Queue and CPU Scheduling
A process does not stay in one place — it moves through a flow of states.
At the center of that flow is the Ready Queue. The ready queue is where processes waiting to be assigned the CPU gather. Processes that are prepared to execute but have not yet received the CPU wait here.
When a process requests I/O, it leaves the CPU and moves to an I/O device queue. Once the I/O completes, it returns to the ready queue to wait for the CPU again. Processes continuously move between these two queues based on their state.
The important point is that CPU scheduling happens in the ready queue. The operating system selects one process from the ready queue and assigns it the CPU — and this selection process is CPU scheduling itself.
준비 큐와 CPU 스케줄링
프로세스는 한 곳에 머무르는 것이 아니라, 상태에 따라 이동하는 흐름으로 구성되어 있다.
그 흐름의 중심에 준비 큐(Ready Queue) 가 있다. 준비 큐는 CPU를 할당받기 위해 기다리는 프로세스들이 모여 있는 공간이다. 실행 준비는 완료되었지만 아직 CPU를 받지 못한 상태의 프로세스들이 여기에 대기한다.
한편 프로세스가 입출력을 요청하면 CPU를 떠나 입출력 장치 큐로 이동한다. 입출력 작업이 끝나면 다시 준비 큐로 돌아와 CPU 할당을 기다린다. 이처럼 프로세스는 준비 큐와 입출력 장치 큐 사이를 상태에 따라 오가는 구조다.
중요한 점은 CPU 스케줄링은 준비 큐에서 일어난다는 것이다. 운영체제는 준비 큐에 있는 프로세스 중 하나를 선택해 CPU를 할당하며, 이 선택 과정 자체가 바로 CPU 스케줄링이다.
What CPU Scheduling Means
In an environment where multiple processes share a single CPU, many processes may be ready to execute. But only one can actually use the CPU at any given moment. The operating system must therefore choose which of the candidate processes to transition into the running state.
This process of deciding which process to run next among many candidates is CPU scheduling. Put simply, CPU scheduling is the operating system's decision-making process for determining which process executes first.
CPU 스케줄링의 의미
지금까지의 내용을 바탕으로 CPU 스케줄링의 의미를 정리해보자.
하나의 CPU를 여러 프로세스가 함께 사용하는 환경에서는 실행 가능한 프로세스가 여러 개 존재한다. 하지만 실제로 CPU를 사용하는 대상은 한 시점에 단 하나다. 따라서 운영체제는 여러 프로세스 후보 중에서 어떤 프로세스를 실행 상태로 전환할지 선택해야 한다.
이처럼 여러 프로세스 중에서 실행할 대상을 결정하는 과정이 바로 CPU 스케줄링이다. 다시 말해, CPU 스케줄링이란 어떤 프로세스를 먼저 실행할지를 판단하는 운영체제의 결정 과정이라고 할 수 있다.
When Does CPU Scheduling Occur?
A process stays in the ready state until it is assigned the CPU. The operating system selects one ready process and transitions it to the running state. In other words, CPU scheduling occurs at the moment a process transitions from the ready state to the running state.
An important nuance: scheduling does not happen at every state change. It only occurs when the CPU needs to be newly assigned — when a new process must be chosen to run.
CPU 스케줄링은 언제 발생할까?
CPU 스케줄링이 무엇인지 알았다면, 이제 그것이 언제 일어나는지를 살펴보자.
프로세스는 CPU를 할당받기 전까지 준비 상태에 머문다. 운영체제는 준비 상태에 있는 프로세스 중 하나를 선택해 실행 상태로 전환한다. 즉, CPU 스케줄링은 프로세스가 준비 상태에서 실행 상태로 전환되는 순간에 발생한다.
여기서 중요한 점은, 모든 상태 변화에서 스케줄링이 발생하는 것이 아니라는 것이다. CPU를 새로 할당해야 하는 시점, 즉 실행할 프로세스를 새로 골라야 하는 순간에만 스케줄링이 이루어진다.
When Does Scheduling Repeat?
After a process is created, it moves through various states. For example, when a running process transitions from the running state to the waiting state due to an I/O request or time expiration, the CPU becomes idle. The operating system then selects another process from the ready state and assigns the CPU to it. Once the I/O completes, the process returns to the ready state and becomes a candidate for the next execution.
In this way, scheduling occurs repeatedly every time a process undergoes a state change.
It is worth noting that throughout this process, the long-term, medium-term, and short-term schedulers each intervene at different points. For now, however, it is enough to understand the overall structure. The specific role of each scheduler will be covered separately in the next session.
스케줄링은 언제 반복되는가?
프로세스는 생성 이후 여러 상태를 오가게 된다. 예를 들어 실행 중이던 프로세스가 입출력 요청이나 시간 만료로 인해 실행 상태에서 대기 상태로 이동하면, CPU는 비게 된다. 그러면 운영체제는 준비 상태에 있는 다른 프로세스를 선택해 CPU를 할당한다. 입출력이 끝난 프로세스는 다시 준비 상태로 돌아와 다음 실행 대상의 후보가 된다.
이처럼 프로세스의 상태 변화가 일어날 때마다 스케줄링은 반복적으로 발생한다.
한편 이 과정에는 단기, 중기, 장기 스케줄러가 각각 서로 다른 지점에서 개입한다. 다만 이번 내용에서는 전체적인 구조만 이해하는 것으로 충분하다. 각 스케줄러의 구체적인 역할은 다음 시간에 따로 다룰 예정이다.
The Repeated Cycle of Process State Changes and Scheduling
After creation, a process continuously cycles between ready, running, and waiting states. Each time a state change occurs, scheduling happens again.
Scheduling is not a one-time event. It is a continuous decision process that repeats every time a process changes state. When a running process transitions to a waiting state due to an I/O request or time expiration, the CPU becomes free, and a process that returns to the ready state becomes a candidate again.
Ultimately, scheduling is required every time the CPU becomes idle. The operating system selects the next process from the ready queue at each such moment, and this cycle repeats continuously for as long as the system runs.
프로세스 상태 변화와 스케줄링
프로세스는 생성 이후 준비, 실행, 대기 상태 사이를 계속해서 오간다. 그리고 이 상태 변화가 일어날 때마다 스케줄링은 반복적으로 발생한다.
즉, 스케줄링은 한 번으로 끝나는 과정이 아니다. 프로세스의 상태 전환이 일어날 때마다 계속 이루어지는 결정 과정이다. 실행 중이던 프로세스가 입출력 요청이나 시간 만료로 인해 상태가 바뀌면 CPU는 비게 되고, 준비 상태로 돌아온 프로세스는 다시 선택 대상이 된다.
결국 CPU가 비는 순간마다 스케줄링이 필요하다. 운영체제는 그 순간마다 준비 큐에서 다음 실행할 프로세스를 선택하고, 이 과정이 시스템이 동작하는 내내 끊임없이 반복된다.
Why Is CPU Scheduling Necessary?
The CPU can only process one task at a time. Yet execution requests continuously arrive from multiple sources simultaneously. Many tasks demand the CPU at once, and the CPU cannot handle them all immediately.
Therefore, a process for deciding which task to handle first — determining execution order — is absolutely necessary. Without establishing execution order, the system cannot function normally.
Deciding execution order is not optional. CPU scheduling is a structurally necessary process in any multi-programming environment.
CPU 스케줄링은 왜 필요한가?
CPU는 한 시점에 하나의 작업만 처리할 수 있다. 그러나 실행 요청은 계속해서 여러 곳에서 동시에 발생한다. 여러 작업이 동시에 CPU를 요구하지만, CPU는 그 모든 요청을 즉시 처리할 수 없다.
따라서 어떤 작업을 먼저 처리할 것인지, 실행 순서를 결정하는 과정이 반드시 필요하다. 만약 실행 순서를 정하지 않는다면 시스템은 정상적으로 동작할 수 없게 된다.
결국 실행 순서를 정한다는 것은 선택의 문제가 아니다. CPU 스케줄링은 다중 프로그래밍 환경에서 구조적으로 반드시 필요한 과정이다.
Why Execution Order Matters
The result of scheduling ultimately manifests as waiting time. Depending on which task is selected first, the time other tasks must wait before receiving the CPU changes — and so does when they get a response.
Users have no visibility into which algorithm the system uses internally. Instead, they evaluate the system based on how quickly the screen responds and how fast requests are answered. Even with the same resources and tasks, the performance users perceive can vary significantly depending on execution order.
In other words, scheduling is not merely about setting an order of execution. It is a critical factor that determines the performance users experience.
실행 순서가 중요한 이유
그렇다면 실행 순서는 왜 중요할까? 스케줄링의 결과는 결국 대기 시간으로 나타난다. 어떤 작업을 먼저 선택하느냐에 따라 다른 작업이 CPU를 받을 때까지 기다려야 하는 시간이 달라지고, 그에 따라 응답 시점도 달라지기 때문이다.
사용자는 시스템 내부에서 어떤 알고리즘이 사용되는지 알지 못한다. 대신 화면이 얼마나 빨리 반응하는지, 요청에 얼마나 빠르게 응답하는지를 기준으로 시스템을 평가한다. 같은 자원, 같은 작업이라도 실행 순서에 따라 사용자가 체감하는 성능은 크게 달라질 수 있다.
즉, 스케줄링은 단순히 실행 순서를 정하는 문제가 아니다. 사용자가 느끼는 시스템의 성능을 결정하는 핵심 요소다.
The Purpose of CPU Scheduling
The CPU is the busiest resource in any system. Since multiple tasks are constantly competing for it, minimizing idle CPU time is essential. How execution opportunities are divided among tasks is equally important.
The goal is not simply to finish any particular task quickly. How execution opportunities are distributed directly determines the overall performance of the system.
The purpose of CPU scheduling is to use the CPU efficiently while improving total system performance. Scheduling is the operating system's strategy for maximizing performance without wasting CPU resources.
CPU 스케줄링의 목적
지금까지 왜 실행 순서를 정해야 하는지 살펴보았다. 그렇다면 스케줄링은 무엇을 잘하기 위해 존재하는 걸까?
CPU는 시스템에서 가장 바쁜 자원이다. 여러 작업이 동시에 CPU를 기다리는 상황이 반복되기 때문에, CPU가 쉬고 있는 상황을 최소화하는 것이 중요하다. 동시에 여러 작업에게 실행 기회를 어떻게 나눌지도 핵심적인 문제다.
여기서 중요한 점은, 단순히 어떤 작업을 빨리 끝내는 것이 목표가 아니라는 것이다. 실행 기회를 어떻게 분배하느냐에 따라 전체 시스템의 성능이 달라지기 때문이다.
결국 CPU 스케줄링의 목적은 CPU를 효율적으로 사용하면서 전체 시스템의 성능을 향상시키는 것이다. 즉, 스케줄링은 CPU를 낭비하지 않으면서 시스템 성능을 높이기 위한 운영체제의 전략이라고 볼 수 있다.
Another Goal: Fairness and Stability
The goal of CPU scheduling is not performance alone. Efficiency matters, but in an environment where many processes share the CPU, fairness is also critical.
No single process should be allowed to monopolize the CPU indefinitely. Nor should any process go unselected for so long that it waits forever — this situation is called starvation, and when it recurs, trust in the system erodes.
As the number of competing tasks grows, competition intensifies. If scheduling criteria are designed to favor certain tasks, others will consistently be pushed back. When this happens repeatedly, it becomes difficult to predict when any given task will execute, and responsiveness suffers.
Scheduling is therefore not just a matter of increasing throughput. It is equally a matter of maintaining fairness and stable responsiveness.
스케줄링의 또 다른 목표: 공정성과 안정성
CPU 스케줄링의 목표는 성능 향상만이 아니다. CPU를 효율적으로 사용하는 것도 중요하지만, 여러 프로세스가 함께 사용하는 환경에서는 공정성도 중요한 요소다.
특정 프로세스가 CPU를 계속 독점하는 상황은 발생해선 안 된다. 또한 어떤 프로세스가 오랫동안 선택받지 못해 계속 대기하는 상황도 문제가 된다. 이를 기아 상태(Starvation) 라고 하며, 이 상태가 반복되면 시스템에 대한 신뢰가 떨어질 수밖에 없다.
실행을 요구하는 작업이 많아질수록 작업 간 경쟁도 심해진다. 이때 스케줄링 기준이 특정 작업에 유리하게 설계되어 있다면, 일부 작업은 계속 밀릴 수밖에 없다. 이런 상황이 반복되면 어떤 작업이 언제 실행될지 예측하기 어려워지고, 응답성에도 부정적인 영향을 미치게 된다.
따라서 스케줄링은 단순히 처리 속도를 높이는 문제가 아니라, 공정성과 안정적인 응답성을 함께 유지하는 문제이기도 하다.
Why Multiple Scheduling Approaches Are Needed
Can a single execution-order criterion apply to every situation? The priorities vary by system purpose. Sometimes fast response is critical; sometimes total throughput matters more; sometimes fairness is the top priority. The most appropriate scheduling approach depends on which criterion takes precedence.
The operating system selects an execution-order criterion to match the system's purpose, and the system's performance characteristics change accordingly. This is why many different scheduling approaches exist rather than just one.
The specific behavior of each scheduling algorithm will be examined in detail in the next session.
왜 다양한 스케줄링 방식이 필요한가?
지금까지 스케줄링이 CPU의 효율적 사용뿐 아니라 공정성과 안정성도 함께 추구해야 한다는 것을 살펴보았다. 여기서 한 가지 질문이 생긴다. 모든 상황에 동일한 실행 순서 기준을 적용할 수 있을까?
시스템의 목적에 따라 우선순위는 달라진다. 빠른 응답이 중요한 경우도 있고, 전체 처리량이 더 중요한 경우도 있으며, 공정성이 최우선인 경우도 있다. 어떤 기준을 우선하느냐에 따라 더 적합한 스케줄링 방식이 달라지는 것이다.
따라서 운영체제는 시스템의 목적에 맞는 실행 순서 기준을 선택하게 되고, 그 기준에 따라 시스템의 성능 특성도 달라진다. 이것이 스케줄링 방식이 하나가 아니라 여러 가지 존재하는 이유다.
각각의 스케줄링 알고리즘이 구체적으로 어떻게 동작하는지는 다음 시간에 자세히 살펴볼 예정이다.
2️⃣ Management Structure and Selection Criteria of CPU Scheduling
Why the Operating System Manages Execution Order
Multiple processes simultaneously request CPU execution. But because the CPU is a single resource, it cannot handle all requests at once. The result is that processes compete for one CPU.
Without a criterion for which process to run first, certain processes may monopolize the CPU and execution order becomes unpredictable. The operating system must therefore directly select and manage which ready process runs next.
What criterion guides that selection? This is the central question of CPU scheduling, and the various algorithms that answer it will be explored in the next session.
CPU 실행 순서는 왜 운영체제가 관리하는가?
현재 시스템에는 여러 프로세스가 동시에 CPU 실행을 요청한다. 그러나 CPU는 하나의 자원이기 때문에 모든 요청을 동시에 처리할 수 없다. 결국 여러 프로세스가 CPU 하나를 두고 경쟁하는 구도가 만들어진다.
이때 어떤 프로세스를 먼저 실행할지에 대한 기준이 없다면, 특정 프로세스가 CPU를 독점하거나 실행 순서를 예측하기 어려운 상황이 발생한다. 따라서 운영체제가 준비 상태에 있는 프로세스 중 어떤 것을 먼저 실행할지를 직접 선택하고 관리해야 한다.
그렇다면 그 선택은 어떤 기준으로 이루어질까? 이것이 바로 CPU 스케줄링의 핵심 질문이며, 다음 시간에는 이 기준들, 즉 다양한 스케줄링 알고리즘을 구체적으로 살펴볼 예정이다.
Why Execution Order Must Be Managed
In a modern system, multiple processes can request CPU execution at the same time. However, because the CPU is a single shared resource, all processes must take turns using it. Furthermore, execution requests can overlap in time — meaning situations where multiple processes simultaneously compete for the same CPU can arise at any moment.
In such an environment, conflicts over execution order arise naturally. Without a criterion for deciding which process runs first, certain processes may end up holding the CPU for an extended period, and execution results become difficult to predict.
For this reason, a structure that systematically manages CPU execution order is absolutely necessary. This is the fundamental reason why the operating system is responsible for CPU scheduling.
실행 순서가 관리되어야 하는 이유
현재 시스템에서는 여러 프로세스가 동시에 CPU 실행을 요청할 수 있다. 그러나 CPU는 하나의 자원이기 때문에 여러 프로세스가 함께 공유해서 사용해야 한다. 더불어 실행 요청은 시간적으로 겹쳐서 발생할 수 있다. 즉, 여러 프로세스가 같은 CPU를 두고 동시에 실행을 요구하는 상황이 언제든 생길 수 있다.
이런 환경에서는 자연스럽게 실행 순서 충돌이 발생한다. 어떤 프로세스를 먼저 실행할지에 대한 기준이 없다면 특정 프로세스가 CPU를 오래 독점하게 되고, 실행 결과 역시 예측하기 어려워진다.
따라서 이러한 환경에서는 CPU 실행 순서를 체계적으로 관리하는 구조가 반드시 필요하다. 이것이 운영체제가 CPU 스케줄링을 담당하는 근본적인 이유다.
What Does the Operating System Manage, and How?
We established that a structure for managing CPU execution order is necessary. So what exactly does the operating system manage, and how does it do so?
First, the subject of management is the pool of candidate processes registered in the ready queue - processes that are in an executable state but have not yet been assigned the CPU. These processes are not simply waiting; they are candidates that the operating system can select as the next execution target.
Next, looking at the method of management: the operating system maintains a waiting order based on the ready queue and selects one process from it to transition into the running state. The entity that performs this selection is the scheduler.
To summarize, CPU scheduling is the process of selecting the next execution target from among the candidates in the ready queue.
운영체제는 무엇을, 어떻게 관리하는가?
CPU 실행 순서를 관리하는 구조가 필요하다고 했다. 그렇다면 운영체제는 구체적으로 무엇을, 어떻게 관리하는 걸까?
먼저 관리 대상은 준비 큐에 등록된 실행 후보 프로세스들이다. 실행 가능한 상태에 있으면서도 아직 CPU를 할당받지 못한 프로세스들이 여기에 해당한다. 이 프로세스들은 단순히 대기하는 것이 아니라, 운영체제가 다음 실행 대상으로 선택할 수 있는 후보들이다.
다음으로 관리 방식을 살펴보면, 운영체제는 준비 큐를 기반으로 대기 순서를 유지하고 그 중 하나의 프로세스를 선택해 실행 상태로 전환한다. 이 선택을 수행하는 주체가 바로 스케줄러다.
정리하면, CPU 스케줄링이란 준비 큐에 있는 실행 후보 중에서 다음 실행 대상을 선택하는 과정이다.
The Scheduling Queue
The scheduling queue is a data structure that collects and manages processes waiting to execute. In data structures, a queue follows FIFO (First In, First Out) — the first element in is the first one out. The operating system uses this structure to manage process waiting states.
There are two fundamental types of scheduling queues. The ready queue holds processes in an executable state that are waiting for CPU allocation — CPU scheduling operates on these processes. The I/O device queue is where processes go when they issue an I/O request during execution; once I/O completes, they return to the ready queue.
Both are queues in structure, but they are managed separately based on what is being waited for and what role each plays.
스케줄링 큐란 무엇인가?
앞서 실행 후보 프로세스들이 준비 큐를 중심으로 관리된다고 했다. 이처럼 실행을 기다리는 프로세스들을 모아서 관리하는 자료구조를 일반적으로 스케줄링 큐(Scheduling Queue) 라고 부른다.
스케줄링 큐에는 CPU를 바로 사용할 수는 없지만 실행 가능한 상태에 있는 프로세스들이 등록된다. 즉, 스케줄링 큐는 CPU 할당 대상이 되는 프로세스들의 집합이며, 운영체제는 이 큐에 있는 프로세스들을 대상으로 다음 실행 대상을 선택한다.
정리하면, 스케줄링 큐는 실행 대기 프로세스를 체계적으로 관리하고 실행 순서를 결정하기 위한 기준이 되는 구조다. CPU 스케줄링은 결국 이 큐를 어떻게 운용하느냐의 문제라고도 볼 수 있다.
Process Execution Flow Based on the Scheduling Queue
Let's trace how a process flows through the system centered on the scheduling queue.
When one of the processes waiting in the ready queue is selected, it is assigned the CPU and transitions to the running state. If the process requires I/O during execution, it temporarily leaves the CPU and moves to the I/O device queue. Once the I/O completes, the process returns to the ready queue and becomes a candidate for execution again. When all of its work is finished, the process moves to the terminated state.
Throughout this flow, the operating system continuously selects the next execution target from the processes in the ready queue. CPU scheduling is ultimately the core mechanism that sustains this entire cyclical flow.
스케줄링 큐 기반 프로세스 실행 흐름
스케줄링 큐를 중심으로 프로세스가 어떻게 흘러가는지 정리해보자.
준비 큐에서 대기 중인 프로세스 중 하나가 선택되면 CPU를 할당받아 실행 상태로 전환된다. 실행 중에 입출력이 필요해지면 프로세스는 잠시 CPU를 떠나 입출력 장치 큐로 이동한다. 입출력이 완료되면 해당 프로세스는 다시 준비 큐로 돌아와 실행 후보가 된다. 그리고 모든 작업이 끝나면 프로세스는 종료 상태로 이동한다.
이 흐름 속에서 운영체제는 준비 큐에 있는 프로세스 중 다음 실행 대상을 끊임없이 선택한다. 결국 CPU 스케줄링은 이 순환적인 흐름 전체를 지탱하는 핵심 메커니즘이라고 할 수 있다.
Types of Scheduling Queues
In data structures, a queue follows a First In, First Out (FIFO) principle — the first element to enter is the first to leave. The operating system uses this structure to manage the waiting states of processes.
However, there is not just one queue. There are two fundamental types.
The first is the Ready Queue. This is where processes in an executable state wait for CPU allocation. CPU scheduling operates on the processes held in this queue.
The second is the I/O Device Queue. This is where a process goes when it issues an I/O request during execution. It waits here until the I/O completes, at which point it returns to the ready queue.
Both share the same queue structure, but the key point is that they are managed as separate queues based on what is being waited for and what role each serves.
스케줄링 큐의 종류
자료구조에서 큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO, First In First Out) 구조다. 운영체제도 이 큐를 활용해 프로세스의 대기 상태를 관리한다.
다만 이 큐가 하나만 존재하는 것이 아니다. 대표적인 기본 큐는 두 가지다.
첫 번째는 준비 큐(Ready Queue) 다. CPU 할당을 기다리는 실행 가능한 상태의 프로세스들이 모여 있는 공간이며, CPU 스케줄링은 바로 이 준비 큐에 있는 프로세스들을 대상으로 이루어진다.
두 번째는 입출력 장치 큐(I/O Device Queue) 다. 실행 도중 입출력을 요청한 프로세스가 이동하는 공간이다. 입출력이 완료될 때까지 여기서 대기하다가, 완료되면 다시 준비 큐로 돌아온다.
구조는 모두 큐이지만, 기다리는 대상과 역할에 따라 서로 다른 큐로 나누어 관리된다는 점이 핵심이다.
Scheduling Is Not a Single Decision
Scheduling does not occur only once. The operating system manages execution at multiple points in time, each serving a different purpose.
For example, when a new job enters the system, there is a stage for deciding whether to accept it right now. When the number of executable processes grows large, there is a stage for deciding which processes to keep in memory. And when the CPU actually becomes idle, a stage is needed to select which ready process to run immediately.
Scheduling is therefore not a single decision — it is a structure composed of multiple management stages. Each stage intervenes at a different point in time and for a different purpose, collectively coordinating the overall execution flow of the system.
스케줄링은 하나의 결정이 아니다
스케줄링은 하나의 순간에만 이루어지는 과정이 아니다. 운영체제는 시스템의 여러 시점에서 서로 다른 목적을 가지고 실행을 관리한다.
예를 들어 시스템에 새로운 작업이 들어올 때, 이 작업을 지금 받아들일지 결정하는 단계가 있다. 실행 가능한 프로세스가 많아지면 어떤 프로세스를 메모리에 유지할지 조절하는 단계도 존재한다. 그리고 실제로 CPU가 비는 순간이 되면, 준비 상태에 있는 프로세스 중 지금 당장 실행할 대상을 선택하는 단계가 필요하다.
이처럼 스케줄링은 단일한 결정이 아니라, 여러 관리 단계로 나누어 이루어지는 구조다. 각 단계는 서로 다른 시점에, 서로 다른 목적을 위해 개입하며 전체 시스템의 실행 흐름을 함께 조율한다.
The Long-Term Scheduler
When a program requests execution, the job first waits on disk. However, because memory capacity is limited, not all jobs can be loaded into memory immediately. This is where the long-term scheduler intervenes.
The long-term scheduler selects which jobs on disk to load into memory. Rather than deciding who gets the CPU, it decides which jobs to admit into the system as execution candidates. Because the number of processes loaded into memory determines how many processes can exist in the ready state at any given time, the long-term scheduler effectively controls the degree of multi-programming.
It is also worth noting that this decision does not happen frequently — it occurs intermittently, only as new jobs arrive.
장기 스케줄러
프로그램이 실행을 요청하면 해당 작업은 우선 디스크에서 대기한다. 그러나 메모리 용량에는 한계가 있기 때문에 모든 작업을 바로 메모리에 올릴 수는 없다. 이때 개입하는 것이 장기 스케줄러(Long-term Scheduler) 다.
장기 스케줄러는 디스크에 존재하는 작업 중 어떤 작업을 메모리에 올릴지 선택한다. 즉, CPU를 누구에게 줄지 결정하는 것이 아니라, 어떤 작업을 실행 후보로 시스템 안에 들여보낼 것인가를 결정하는 단계다. 메모리에 올라온 프로세스의 수에 따라 동시에 준비 상태로 존재하는 프로세스의 수가 달라지기 때문에, 장기 스케줄러는 곧 다중 프로그래밍의 정도를 결정하는 역할을 한다.
또한 이 결정은 자주 일어나는 것이 아니라, 새로운 작업이 유입될 때마다 간헐적으로 발생한다는 점도 기억해두자.
Summary of the Long-Term Scheduler's Role
Let's trace the long-term scheduler's flow of operation.
When a job arrives on disk, the long-term scheduler intervenes and selects which jobs to load into memory. Selected jobs are loaded into memory and registered as processes in the ready queue. From there, the short-term scheduler selects one of the processes in the ready queue and has it executed by the CPU.
In summary, the long-term and short-term schedulers divide their responsibilities across different stages. The long-term scheduler decides which jobs enter the system, while the short-term scheduler selects the actual CPU execution target. The specific behavior of the short-term scheduler will be examined in a later session.
장기 스케줄러의 역할 정리
장기 스케줄러의 동작 흐름을 정리해보자.
작업이 디스크에 도착하면 장기 스케줄러가 개입해 디스크에 있는 작업 중 어떤 것을 메모리에 올릴지 선택한다. 선택된 작업은 메모리에 올라와 준비 큐에 등록된 프로세스가 된다. 이후 단기 스케줄러(Short-term Scheduler) 가 준비 큐에 있는 프로세스 중 하나를 선택해 CPU에 의해 실행되도록 한다.
결론적으로 장기 스케줄러와 단기 스케줄러는 서로 다른 단계에서 역할을 나눠 담당한다. 장기 스케줄러는 시스템에 들어올 작업을 결정하고, 단기 스케줄러는 실제 CPU 실행 대상을 선택한다. 단기 스케줄러의 구체적인 동작은 추후에 살펴볼 예정이다.
The Medium-Term Scheduler
Even after the long-term scheduler loads jobs into memory, the state of memory continues to change. As the number of running or ready processes grows, memory can become scarce. This is where the medium-term scheduler intervenes.
The medium-term scheduler temporarily suspends some of the processes currently in memory, a process known as swap-out. Conversely, when memory space becomes available, it reloads suspended processes back into memory — a process known as swap-in.
In other words, the medium-term scheduler is responsible for regulating the number of processes maintained in memory. If the long-term scheduler controls how much work enters the system, the medium-term scheduler balances memory resources among the jobs already inside.
중기 스케줄러
장기 스케줄러가 작업을 메모리로 들여보낸 이후에도 메모리 상태는 계속 변한다. 실행 중이거나 준비 중인 프로세스가 많아지면 메모리가 부족해질 수 있는데, 이때 개입하는 것이 중기 스케줄러(Medium-term Scheduler) 다.
중기 스케줄러는 메모리에 올라와 있는 프로세스 중 일부를 일시적으로 중단 상태로 전환한다. 이 과정을 스왑 아웃(Swap-out) 이라고 한다. 반대로 메모리 공간에 여유가 생기면 중단된 프로세스를 다시 메모리로 불러오는데, 이 과정을 스왑 인(Swap-in) 이라고 한다.
즉, 중기 스케줄러는 메모리에 유지되는 프로세스의 수를 조절하는 역할을 담당한다. 장기 스케줄러가 시스템에 들어올 작업의 양을 결정한다면, 중기 스케줄러는 이미 들어온 작업들 사이에서 메모리 자원을 균형 있게 유지하는 역할을 한다고 이해하면 된다.
Summary of the Medium-Term Scheduler's Role
The medium-term scheduler manages processes that are already in memory — including both running and ready processes. When the number of processes causes memory to become overloaded, it suspends some of them and removes them from memory.
The defining characteristic of the medium-term scheduler is that it acts as a balancer between the long-term and short-term schedulers. While the long-term scheduler controls the volume of incoming work and the short-term scheduler determines which process gets the CPU, the medium-term scheduler adjusts the number of processes kept in memory to relieve system load.
중기 스케줄러의 역할 정리
중기 스케줄러의 관리 대상은 이미 메모리에 올라와 있는 프로세스다. 실행 중이거나 준비 상태에 있는 프로세스 모두가 여기에 포함된다. 시스템의 프로세스가 많아져 메모리가 과부하 상태가 되면, 중기 스케줄러는 이들 중 일부를 중단 상태로 전환해 메모리에서 내보낸다.
중기 스케줄러의 핵심 특징은 장기 스케줄러와 단기 스케줄러 사이에서 균형을 맞추는 조정자 역할을 한다는 점이다. 장기 스케줄러가 시스템에 들어오는 작업의 규모를 조절하고, 단기 스케줄러가 CPU 실행 대상을 결정한다면, 중기 스케줄러는 메모리에 유지되는 프로세스 수를 조정해 시스템 부하를 완화하는 역할을 담당한다.
The Short-Term Scheduler
The short-term scheduler selects which process in the ready queue to assign the CPU to. In other words, it is the stage that decides which of the many ready processes to transition into the running state right now.
This decision occurs very frequently. Every time a process terminates, an I/O request is made, or a time quantum expires, the short-term scheduler intervenes and selects the next execution target.
Among the three schedulers, the short-term scheduler has the most direct impact on system responsiveness and performance. All of the scheduling criteria and algorithms covered in later sessions are applied to this scheduler.
단기 스케줄러
단기 스케줄러(Short-term Scheduler)는 준비 큐에 있는 프로세스 중에서 CPU를 할당할 프로세스를 선택하는 역할을 한다. 즉, 준비 상태에 있는 여러 프로세스 중 지금 당장 실행 상태로 전환할 하나를 결정하는 단계다.
이 결정은 매우 자주 발생한다. 프로세스가 종료되거나, 입출력 요청이 발생하거나, 시간 할당량이 끝나는 순간마다 단기 스케줄러가 개입해 다음 실행 대상을 선택한다.
단기 스케줄러는 세 가지 스케줄러 중 시스템의 응답성과 성능에 가장 직접적인 영향을 미치는 스케줄러다. 이후에 배우게 될 다양한 스케줄링 기준과 알고리즘도 바로 이 단기 스케줄러에 적용된다.
The Dispatcher: Actually Handing Over the CPU
Once the short-term scheduler selects which process will use the CPU, the dispatcher intervenes in the next step. The dispatcher is the execution module responsible for actually transferring CPU control to the selected process. During this process, a context switch takes place, and the system transitions to user mode to begin actual execution.
To summarize the roles: the short-term scheduler decides who runs, and the dispatcher handles the transition to the running state. In other words, at the moment a process moves from the ready state to the running state, the short-term scheduler and the dispatcher work together.
디스패처: CPU를 실제로 넘기는 역할
단기 스케줄러가 준비 큐에 있는 프로세스 중 CPU를 사용할 프로세스를 선택하면, 그 다음 단계에서 디스패처(Dispatcher) 가 개입한다. 디스패처는 선택된 프로세스에게 CPU 제어를 실제로 넘기는 실행 담당 모듈이다. 이 과정에서 문맥 교환(Context Switching)이 이루어지며, 사용자 모드로 전환해 실제 실행이 시작된다.
역할을 정리하면 다음과 같다. 단기 스케줄러는 누구를 실행할지 결정하고, 디스패처는 실제 실행 상태로 전환하는 역할을 담당한다. 즉, 준비 상태에서 실행 상태로 넘어가는 순간에 단기 스케줄러와 디스패처가 함께 작동한다.
When the Short-Term Scheduler Intervenes
The short-term scheduler intervenes every time a specific event occurs. Concretely, it operates in the following situations.
When a running process terminates, when a process relinquishes the CPU due to an I/O request, when I/O completes and a process returns to the ready state, and when a time quantum expires or an interrupt occurs.
In this way, the short-term scheduler intervenes at every moment a process undergoes a state transition. Among the three schedulers — long-term, medium-term, and short-term — the short-term scheduler operates by far the most frequently.
단기 스케줄러의 개입 시점
단기 스케줄러는 특정 사건이 발생하는 순간마다 개입한다. 구체적으로는 다음과 같은 상황에서 작동한다.
실행 중인 프로세스가 종료될 때, 프로세스가 입출력 요청으로 인해 CPU를 반납할 때, 입출력이 완료되어 프로세스가 다시 준비 상태로 돌아올 때, 그리고 시간 할당량이 만료되거나 인터럽트가 발생할 때가 이에 해당한다.
이처럼 단기 스케줄러는 프로세스의 상태 전환이 이루어지는 순간마다 개입한다. 장기, 중기, 단기 세 가지 스케줄러 중에서 가장 빈번하게 동작하는 것이 바로 단기 스케줄러다.
Summary: Who Manages CPU Scheduling
Let's take a consolidated look at where each of the three schedulers intervenes in the process state transition flow.
The long-term scheduler decides which jobs to admit into memory at the creation stage — it selects which jobs on disk to load. The medium-term scheduler regulates the number of processes kept in memory by temporarily suspending some and reloading others. The short-term scheduler intervenes at the moment a process transitions from the ready state to the running state and selects which process to assign the CPU to.
These three schedulers intervene at different points in time, but they all operate together on a single process state transition flow. The system as a whole can only run stably when each scheduler's role interlocks properly with the others.
CPU 스케줄링의 관리 주체 정리
지금까지 배운 세 가지 스케줄러가 프로세스 상태 전이 흐름 속에서 어디에 개입하는지 한눈에 정리해보자.
장기 스케줄러는 생성 단계에서 메모리 진입을 결정한다. 디스크에 있는 작업 중 어떤 것을 메모리에 올릴지 선택하는 역할이다. 중기 스케줄러는 메모리 안에서 프로세스를 일시 중단하거나 다시 불러오는 방식으로 메모리에 유지되는 프로세스 수를 조절한다. 단기 스케줄러는 준비 상태에서 실행 상태로 넘어가는 순간에 개입해 CPU를 할당할 프로세스를 선택한다.
이 세 스케줄러는 서로 다른 시점에 개입하지만, 하나의 프로세스 상태 전이 흐름 위에서 함께 작동한다. 각자의 역할이 맞물려야 비로소 시스템 전체가 안정적으로 동작할 수 있다.
Preemptive vs. Non-Preemptive Scheduling
We said that the short-term scheduler intervenes every time a process state change occurs. This raises an important question: can the short-term scheduler forcibly stop a running process at any time?
The answer to this question divides scheduling into two major types. Preemptive scheduling can forcibly halt a running process and hand the CPU to another, while non-preemptive scheduling waits until the running process voluntarily relinquishes the CPU on its own.
Which approach is chosen significantly affects the system's responsiveness, fairness, and processing efficiency.
선점 vs 비선점 스케줄링
단기 스케줄러는 프로세스 상태 변화가 발생할 때마다 개입한다고 했다. 여기서 한 가지 중요한 질문이 생긴다. 단기 스케줄러는 실행 중인 프로세스를 언제든지 강제로 중단시킬 수 있을까?
이 질문에 대한 답에 따라 스케줄링 방식은 크게 두 가지로 나뉜다. 실행 중인 프로세스를 강제로 중단하고 다른 프로세스에게 CPU를 넘길 수 있는 선점 스케줄링(Preemptive Scheduling) 과, 실행 중인 프로세스가 스스로 CPU를 반납할 때까지 기다리는 비선점 스케줄링(Non-preemptive Scheduling) 이다.
어떤 방식을 선택하느냐에 따라 시스템의 응답성, 공정성, 그리고 처리 효율이 달라진다.
Non-Preemptive Scheduling
In non-preemptive scheduling, a process that has been assigned the CPU continues running until it terminates on its own or transitions to a waiting state due to an I/O request. The operating system does not intervene midway to forcibly stop the running process.
The advantage of this approach is that it is structurally simple and incurs low management overhead. Because context switches do not occur frequently, overall overhead remains low.
However, if a long-running task claims the CPU first, all other processes must wait until that task finishes. This can result in response delays, which is the key drawback.
Ultimately, non-preemptive scheduling can be understood as a structure that allows a process to keep running until it voluntarily gives up the CPU.
비선점 스케줄링
비선점 스케줄링(Non-preemptive Scheduling)은 CPU를 할당받은 프로세스가 스스로 종료되거나 입출력 요청으로 인해 대기 상태로 전환될 때까지 계속 실행되는 방식이다. 즉, 운영체제가 중간에 개입해 실행 중인 프로세스를 강제로 중단시키지 않는다.
이 방식의 장점은 구조가 단순하고 관리 부담이 적다는 것이다. 문맥 교환이 자주 발생하지 않기 때문에 오버헤드도 낮다.
그러나 실행 시간이 긴 작업이 먼저 CPU를 점유하면, 그 작업이 끝날 때까지 다른 프로세스는 계속 기다려야 한다. 이로 인해 응답 지연이 발생할 수 있다는 것이 단점이다.
결국 비선점 방식은 프로세스가 CPU를 자발적으로 반납할 때까지 실행을 계속 허용하는 구조라고 이해하면 된다.
Preemptive Scheduling
In preemptive scheduling, the operating system can reclaim the CPU from a running process whenever it judges this to be necessary. If the time quantum expires or a higher-priority process becomes ready, the currently running task can be halted and replaced with another process.
Rather than waiting for a process to give up the CPU on its own, the operating system directly intervenes and changes the execution flow. This approach prevents any single task from monopolizing the CPU for too long, making it well-suited for improving system responsiveness. The downside is that a context switch occurs every time a process is replaced, which can introduce additional overhead.
To summarize the difference simply: non-preemptive scheduling never takes the CPU away, while preemptive scheduling can reclaim it when needed. The various CPU scheduling algorithms that determine actual execution order are built on top of these two approaches, and they will be examined one by one in the next session.
선점 스케줄링
선점 스케줄링(Preemptive Scheduling)에서는 운영체제가 필요하다고 판단하면 실행 중인 프로세스의 CPU를 중간에 회수할 수 있다. 시간 할당량이 만료되었거나 더 높은 우선순위의 프로세스가 준비 상태가 되면, 현재 실행 중인 작업을 중단시키고 다른 프로세스로 교체할 수 있다.
즉, 프로세스가 스스로 CPU를 반납하기를 기다리는 것이 아니라, 운영체제가 직접 개입해 실행 흐름을 바꿀 수 있는 구조다. 이 방식은 특정 작업이 CPU를 오래 독점하는 것을 막을 수 있어 시스템의 응답성을 높이는 데 유리하다. 다만 프로세스가 교체될 때마다 문맥 교환이 발생하기 때문에 추가적인 오버헤드가 생길 수 있다는 단점이 있다.
두 방식의 차이를 간단히 정리하면, 비선점은 CPU를 빼앗지 않고, 선점은 필요하다면 CPU를 회수할 수 있는 방식이다. 이 두 방식을 토대로 실제 실행 순서를 결정하는 다양한 CPU 스케줄링 알고리즘이 만들어지며, 이에 대해서는 다음 시간에 하나씩 살펴볼 예정이다.
CPU Scheduling Execution Flow
We have now examined the structure and management entities of CPU scheduling. Let's look at actual execution examples to see how the execution flow of processes plays out in practice.
In particular, we will explore why execution order in situations that appear to involve simultaneous multi-process operation can differ from what we might expect.
CPU 스케줄링 실행 흐름
지금까지 CPU 스케줄링의 구조와 관리 주체를 살펴보았다. 이번에는 실제 실행 예제를 통해 프로세스의 실행 흐름이 어떻게 나타나는지 확인해보자.
특히 여러 프로세스가 동시에 작동하는 것처럼 보이는 상황에서, 실행 순서가 왜 우리가 예상하는 것과 다르게 나타나는지도 함께 살펴볼 것이다.
We Do Not Decide Execution Order
Although multiple processes appear to run simultaneously, the CPU actually handles only one execution at a time. The CPU alternates between processes in very short time intervals, which makes it feel to the user as though everything is running concurrently.
The important point here is that we do not directly specify this execution order. The operating system decides it. As a result, execution outcomes may not always be identical. Even when running the same program, the operating system may make different choices depending on the state of the system at that moment.
실행 순서는 우리가 정하지 않는다
여러 프로세스가 동시에 실행되는 것처럼 보이지만, 실제 CPU는 한 번에 하나의 실행만 처리한다. CPU는 매우 짧은 시간 단위로 프로세스를 번갈아 실행하기 때문에, 사용자 입장에서는 동시에 실행되는 것처럼 느껴지는 것이다.
여기서 중요한 점은, 우리가 이 실행 순서를 직접 지정하지 않는다는 것이다. 실행 순서는 운영체제가 결정한다. 따라서 실행 결과가 항상 동일하게 나타나지 않을 수 있다. 같은 프로그램을 실행하더라도 그 순간의 시스템 상태에 따라 운영체제가 다른 선택을 할 수 있기 때문이다.
Apparent Concurrency in Practice
When fork() creates parent and child processes, both processes execute a loop, print output, and wait briefly.
Let's look at usleep(1000000) used in the example. While the familiar sleep() waits in units of seconds, usleep() waits in microseconds. usleep(1000000) means 1,000,000 microseconds — that is, 1 second. If the wait time is shortened further, the parent and child processes alternate CPU usage more frequently, causing their output to appear more densely interleaved. This example deliberately uses a short wait time to make the effect of scheduling-driven execution order changes more clearly visible.
The key thing to notice is the output order. In some runs, parent appears first; in others, child appears first. We did not specify this order, yet the operating system alternates between the two processes and their output becomes mixed.
This is an example of apparent concurrency. In reality the processes take turns, but the output looks as though they are running simultaneously.
실행 예제로 보는 겉보기 동시성
fork()를 통해 부모 프로세스와 자식 프로세스가 생성되면, 두 프로세스는 각각 반복문을 실행하며 출력하고 잠시 대기한다.
여기서 사용된 usleep(1000000)을 살펴보자. 기존에 사용하던 sleep()은 초 단위로 대기하지만, usleep()은 마이크로초 단위로 대기한다. usleep(1000000)은 1,000,000 마이크로초, 즉 1초를 의미한다. 만약 대기 시간을 더 짧게 줄이면 부모와 자식 프로세스가 더 자주 CPU를 번갈아 사용하게 되어 출력이 더 촘촘하게 섞여 나온다. 이 예제는 의도적으로 짧은 대기 시간을 활용해 스케줄링에 의해 실행 순서가 바뀌는 모습을 더 명확하게 보여주기 위한 것이다.
여기서 주목해야 할 점은 출력 순서다. 어떤 경우에는 parent가 먼저 출력되고, 어떤 경우에는 child가 먼저 출력된다. 우리가 이 순서를 지정하지 않았음에도 운영체제가 두 프로세스를 번갈아 실행하면서 결과가 섞여 나타나는 것이다.
이것이 바로 겉보기 동시성의 예다. 실제로는 번갈아 실행되지만, 출력은 마치 동시에 실행되는 것처럼 보인다.
The Non-Determinism of Execution Order
Apparent concurrency reveals an important characteristic: even with an identical program, the output order of execution results may differ from run to run.
Why does this happen? Because we did not directly specify which process receives the CPU first. Among the processes in the ready state, which one runs first depends on the scheduling decision made at that moment. In other words, the selection of the execution target is not fixed.
As a result, running the same program again may produce a different order of results. This property is called the non-determinism of execution order.
실행 순서의 비결정성
겉보기 동시성에서 한 가지 중요한 특징이 드러난다. 동일한 프로그램이더라도 실행 결과의 출력 순서가 매번 같지 않을 수 있다는 것이다.
왜 이런 일이 발생할까? CPU를 먼저 할당받을 프로세스를 우리가 직접 지정하지 않았기 때문이다. 준비 상태에 있는 프로세스 중 누가 먼저 실행될지는 그 순간의 스케줄링 판단에 따라 달라진다. 즉, 실행 대상의 선택은 고정되어 있지 않다.
따라서 동일한 프로그램을 다시 실행하면 결과 순서가 달라질 수 있다. 이를 실행 순서의 비결정성이라고 한다.
Observing Non-Determinism Through an Example
Consider an example that uses fork() to create parent and child processes. This time, rather than focusing on the fact that each process has an independent execution flow, we pay attention to the fact that output order differs between runs even with the same program.
The child process prints child and the parent process prints parent. The code has no loops and no wait functions. Yet in some runs parent appears first, and in others child appears first.
This is not because the code differs. It is because the process that receives the CPU first can vary at each execution. The selection of the execution target is not fixed — it is determined by the scheduling decision made at that moment.
This property — whereby execution result order can differ from run to run even with an identical program — is called the non-determinism of execution order. This example demonstrates that non-determinism in its simplest possible form.
실행 순서의 비결정성 — 예제로 확인하기
fork()를 이용해 부모와 자식 프로세스를 생성하는 예제를 살펴보자. 이번에는 두 프로세스가 각각 독립적인 실행 흐름을 가진다는 점보다, 같은 프로그램을 실행해도 출력 순서가 매번 같지 않다는 점에 주목한다.
자식 프로세스는 child를 출력하고, 부모 프로세스는 parent를 출력한다. 이 코드에는 반복문도 없고 대기 함수도 없다. 그럼에도 어떤 경우에는 parent가 먼저, 어떤 경우에는 child가 먼저 출력될 수 있다.
이 현상은 코드가 달라서가 아니다. CPU를 먼저 할당받는 대상이 실행 시점마다 달라질 수 있기 때문이다. 실행 대상의 선택은 고정되어 있지 않으며, 그 순간의 스케줄링 판단에 따라 결정된다.
이처럼 동일한 프로그램이더라도 실행 결과의 순서가 매번 달라질 수 있는 성질을 실행 순서의 비결정성이라고 한다. 이 예제는 그 비결정성을 가장 단순한 형태로 보여주는 코드다.
The Repeated Cycle of Execution and Waiting
To understand why execution order is not fixed, we need to revisit process state changes.
A process that enters the running state does not continue using the CPU indefinitely. When an I/O request occurs, the running process transitions to the waiting state. Once the wait completes, it returns to the ready state and becomes a candidate for execution again. The flow of running → waiting → running is not a one-time sequence — it is a repeating structure.
The key point is that the moment a process transitions to the waiting state, it can no longer use the CPU. As a result, the CPU becomes idle and the operating system selects another ready process.
In a structure where execution and waiting repeat like this, the entity using the CPU constantly changes. That is why CPU execution order is not fixed and continues to vary.
실행과 대기의 반복
실행 순서가 고정되어 있지 않은 이유를 이해하려면 프로세스의 상태 변화를 다시 생각해볼 필요가 있다.
프로세스는 한 번 실행 상태가 되었다고 해서 계속 CPU를 사용하는 것이 아니다. 실행 중이던 프로세스는 입출력 요청이 발생하면 대기 상태로 전환된다. 대기 작업이 끝나면 다시 준비 상태로 돌아와 실행 대상 후보가 된다. 즉, 실행 → 대기 → 실행의 흐름이 한 번으로 끝나는 것이 아니라 반복되는 구조다.
여기서 중요한 점은, 프로세스가 대기 상태로 전환되는 순간 해당 프로세스는 더 이상 CPU를 사용할 수 없게 된다는 것이다. 그 결과 CPU는 비게 되고, 운영체제는 준비 상태에 있는 다른 프로세스를 선택한다.
이처럼 실행과 대기가 반복되는 구조에서는 CPU를 사용하는 주체가 계속 바뀔 수밖에 없다. 그래서 CPU 실행 순서 역시 고정되지 않고 계속 달라질 수 있는 것이다.
Execution and Waiting in Practice
In the example code, the process prints CPU running, waits briefly, then prints I/O waiting, and waits again — this flow repeats.
The sleep() that follows printf("CPU running\n") does not mean the process keeps holding the CPU — it means the process transitions to a waiting state for a period. The repeating structure is: print CPU running → wait → print I/O waiting → wait.
This example simply illustrates the alternating structure of process execution and waiting. Each time such a state change occurs, the CPU can select a different execution target, and as a result execution order continues to vary.
예제로 보는 실행과 대기의 반복
예제 코드에서는 CPU running을 출력한 뒤 잠시 대기하고, 이어서 I/O waiting을 출력한 뒤 다시 대기하는 흐름이 반복된다.
여기서 printf("CPU running\n") 뒤에 오는 sleep()은 프로세스가 CPU를 계속 점유하는 것이 아니라, 잠시 대기 상태로 전환되는 것을 의미한다. 즉, CPU running 출력 → 대기 → I/O waiting 출력 → 대기의 흐름이 반복되는 구조다.
이 예제는 프로세스의 실행과 대기가 번갈아 나타나는 구조를 단순하게 보여준다. 이러한 상태 변화가 발생할 때마다 CPU는 다른 실행 대상을 선택할 수 있고, 그 결과 실행 순서는 계속 달라질 수 있다.
Preemptive Scheduling: Switching Without Waiting
The examples seen so far involved the CPU passing to another process when a process transitioned to the waiting state. In preemptive scheduling, however, the CPU can be switched even when a process is not in the waiting state.
In preemptive scheduling, the operating system can reclaim the CPU and reassign it to another process even if the current task has not finished. This allows shorter tasks or higher-priority tasks to be handled more quickly, making it well-suited for improving system responsiveness.
The downside is that a context switch occurs every time a process is swapped out, which can introduce additional overhead.
The key point here is that the operating system can intervene and reassign the CPU even when a process is not in the waiting state. This is the most significant difference from the non-preemptive approach.
선점 스케줄링: 대기 없이도 교체된다
앞서 살펴본 예제는 프로세스가 대기 상태로 전환될 때 CPU가 다른 프로세스에게 넘어가는 구조였다. 그런데 선점 스케줄링에서는 프로세스가 대기 상태가 아니더라도 CPU가 교체될 수 있다.
선점 스케줄링에서는 작업이 아직 끝나지 않았더라도 운영체제가 판단에 따라 CPU를 회수하고 다른 프로세스에게 재할당할 수 있다. 이 방식은 짧은 작업이나 높은 우선순위의 작업을 더 빠르게 처리할 수 있어 시스템의 응답성을 향상시키는 데 유리하다.
다만 실행 중이던 작업을 중단하고 다른 작업으로 전환할 때마다 문맥 교환이 발생하기 때문에 추가적인 오버헤드가 생길 수 있다.
여기서 핵심은 대기 상태가 아니어도 운영체제가 개입해 CPU를 재할당할 수 있다는 점이다. 이것이 비선점 방식과의 가장 큰 차이다.
Preemptive Scheduling Example Code
This example does not directly implement preemptive scheduling. It is an example designed to observe execution results in an environment where preemptive scheduling is operating.
Looking at the code, the parent and child processes each run a while loop and continuously print their own messages. Neither process terminates on its own, and no instruction to yield the CPU has been written. In other words, the code contains no command to stop execution or hand off to another process.
Yet the execution results show output alternating between the two. This switching is not caused by the code — it is caused by the operating system's preemptive behavior. The operating system uses timer interrupts to reclaim the CPU from the running process after a set interval and switch to another.
In short, this example demonstrates that even when a process does not voluntarily relinquish the CPU, the operating system can intervene and swap execution.
선점 스케줄링 예제 코드
이 예제는 선점 스케줄링을 직접 구현한 코드가 아니다. 선점 스케줄링이 동작하는 환경에서 실행 결과를 관찰하기 위한 예제다.
코드를 보면 부모와 자식 프로세스가 각각 while 반복문을 수행하며 계속해서 자신의 메시지를 출력한다. 두 프로세스 모두 스스로 종료하지 않으며, CPU를 반납하는 명령도 작성되어 있지 않다. 즉, 코드 안에는 실행을 중단하거나 다른 프로세스로 넘기라는 명령이 전혀 없다.
그럼에도 실행 결과를 보면 출력이 번갈아 나타난다. 이 교체는 코드 때문이 아니라 운영체제의 선점 동작 때문이다. 운영체제는 타이머 인터럽트를 통해 일정 시간이 지나면 실행 중인 프로세스의 CPU를 회수하고 다른 프로세스로 전환한다.
즉, 이 예제는 프로세스가 스스로 CPU를 내려놓지 않더라도 운영체제가 개입해 실행을 교체할 수 있다는 것을 보여주는 코드다.
Non-Preemptive Scheduling: Only Voluntary Yielding
In contrast to preemptive scheduling, non-preemptive scheduling does not allow the operating system to forcibly stop a running process. Once a process is assigned the CPU, it continues running until its task finishes or it voluntarily transitions to a waiting state.
This structure is simple and incurs low management overhead. However, if a long-running task claims the CPU first, all other tasks must wait until it completes. This can lead to response delays that directly affect the performance users perceive.
비선점 스케줄링: 자발적 반납만 허용
선점 스케줄링과 대비되는 비선점 스케줄링을 살펴보자. 비선점 스케줄링에서는 운영체제가 실행 중인 프로세스를 강제로 중단시키지 않는다. 한 번 CPU를 할당받은 프로세스는 작업이 끝나거나 스스로 대기 상태로 전환될 때까지 계속 실행된다.
이 구조는 단순하고 관리 부담이 적다는 장점이 있다. 그러나 실행 시간이 긴 작업이 먼저 CPU를 점유하면, 그 작업이 끝날 때까지 다른 작업은 계속 기다려야 한다는 단점이 있다. 결국 응답 지연이 발생할 수 있으며, 이는 사용자 체감 성능에도 직접적인 영향을 미친다.
Non-Preemptive Scheduling Example Code
This example also does not directly implement non-preemptive scheduling. It is designed to observe the execution flow under non-preemptive conditions by creating a situation where forced switching does not occur.
After using fork() to create parent and child processes, the parent calls sleep(6) so that it waits until the child finishes. The important point is that sleep() is not simply a function that passes time — it is a call that transitions the process to a waiting state for a period. In other words, the parent does not continue using the CPU; it voluntarily enters a waiting state and becomes unable to use the CPU. During that time, the child process runs its loop and completes all of its output.
The execution results show all of the child's output appearing first, followed by the parent's output. This is not because the operating system forcibly stopped a running process — it is because the parent voluntarily transitioned to the waiting state, causing the CPU to pass to the child.
In short, this example shows how execution flow changes when a process voluntarily relinquishes the CPU.
비선점 스케줄링 예제 코드
이 예제 역시 비선점 스케줄링을 직접 구현한 코드가 아니다. 강제 교체가 발생하지 않는 상황을 만들어 비선점 방식에서의 실행 흐름을 관찰하는 예제다.
fork()를 이용해 부모와 자식 프로세스를 생성한 뒤, 부모 프로세스는 sleep(6)을 호출해 자식이 끝날 때까지 기다리도록 구성했다. 여기서 중요한 점은 sleep()이 단순히 시간을 보내는 함수가 아니라, 해당 프로세스를 일정 시간 동안 대기 상태로 전환시키는 호출이라는 것이다. 즉, 부모는 CPU를 계속 사용하는 것이 아니라 스스로 대기 상태로 들어가 CPU를 사용할 수 없게 된다. 그 사이에 자식 프로세스는 반복문을 통해 자신의 출력을 끝까지 수행한다.
실행 결과를 보면 자식의 출력이 모두 나타난 뒤 부모의 출력이 이어지는 것을 확인할 수 있다. 운영체제가 실행 중인 프로세스를 강제로 중단시킨 것이 아니라, 부모가 스스로 대기 상태로 전환되었기 때문에 CPU가 자식에게 넘어간 것이다.
즉, 이 예제는 프로세스가 CPU를 자발적으로 반납할 때 실행 흐름이 어떻게 달라지는지를 보여주는 코드다.
Summary
Process execution is not controlled by the user — it is managed by the operating system. Which process uses the CPU and when is not fixed in advance; it varies with the scheduling policy applied, and that policy determines the responsiveness users experience.
CPU scheduling is the mechanism that decides and controls the execution flow of processes. In the next session, we will examine the specific criteria used to determine execution order — the various scheduling algorithms — one by one.
정리
프로세스의 실행은 사용자가 직접 제어하는 것이 아니라 운영체제가 관리한다. 어떤 프로세스가 언제 CPU를 사용할지는 고정되어 있지 않으며, 적용되는 스케줄링 방식에 따라 실행 순서가 달라진다. 그리고 그 순서에 따라 사용자가 느끼는 응답성도 달라진다.
이처럼 프로세스의 실행 흐름을 결정하고 제어하는 것이 바로 CPU 스케줄링이다. 다음 시간에는 이 실행 순서를 결정하는 구체적인 기준, 즉 다양한 스케줄링 알고리즘을 하나씩 살펴볼 예정이다.
Practice: Observing Apparent Concurrency
Let's directly observe what happens when fork() creates parent and child processes that each run independently.
The execution results show the messages of the parent and child interleaved in the output. Although it looks as though the two processes are running simultaneously, the CPU handles only one task at a time. The reason output alternates is that the operating system switches execution targets at very high speed.
What this practice demonstrates is that the two processes are not truly running at the same time, what we see is apparent concurrency, produced by rapid execution switching.
실습으로 확인하는 겉보기 동시성
fork()를 호출했을 때 부모 프로세스와 자식 프로세스가 각각 생성되어 실행되는 것을 직접 확인해보자.
실행 결과를 보면 부모와 자식의 메시지가 섞여서 출력되는 것을 볼 수 있다. 겉으로 보기엔 두 프로세스가 동시에 실행되는 것처럼 보이지만, CPU는 한 번에 하나의 작업만 처리한다. 출력이 번갈아 나오는 이유는 운영체제가 실행 대상을 매우 빠르게 전환하기 때문이다.
이 실습을 통해 확인할 수 있는 것은, 실제로 두 프로세스가 동시에 실행되는 것이 아니라 빠른 실행 전환에 의해 만들어지는 겉보기 동시성이라는 점이다.
Practice: Observing Non-Determinism of Execution Order
This example is a simple program with no loops and no wait functions — the parent and child each print one message.
Running it shows that sometimes child appears first, and sometimes parent appears first. The code is identical, but who receives the CPU first is not fixed.
What this practice demonstrates is that even with an identical program, the order of execution results can differ from run to run. The selection of the execution target is not predetermined — non-determinism is inherent in CPU scheduling.
실습으로 확인하는 실행 순서의 비결정성
이 예제는 반복문도, 대기 함수도 없이 부모와 자식 프로세스가 각각 한 번씩 메시지를 출력하는 단순한 코드다.
실행해보면 어떤 경우에는 child가 먼저 출력되고, 어떤 경우에는 parent가 먼저 출력된다. 코드는 동일하지만 누가 먼저 CPU를 할당받는지는 고정되어 있지 않기 때문이다.
이 실습을 통해 확인할 수 있는 것은, 동일한 프로그램이더라도 실행 결과의 순서가 매번 달라질 수 있다는 점이다. 실행 대상의 선택은 미리 결정되어 있지 않으며, CPU 스케줄링에는 비결정성이 존재한다.
Practice: Observing Repeated Execution and Waiting
This example includes a call to sleep(). Remember that sleep() does not merely delay time — it transitions the process to a waiting state for a period.
Running it shows that after one process prints a message and appears to pause, the other process's output follows. This is because the process transitions to a waiting state via sleep() and can no longer use the CPU, at which point the operating system selects another ready process.
What this lab demonstrates is that processes repeat cycles of execution and waiting, and after each wait period, they pass through the ready state before running again.
실습으로 확인하는 실행과 대기의 반복
이 예제는 sleep() 호출을 포함한다. sleep()은 단순히 시간을 지연시키는 것이 아니라, 해당 프로세스를 일정 시간 동안 대기 상태로 전환시키는 호출이라는 점을 기억하자.
실행해보면 한 프로세스가 메시지를 출력한 뒤 잠시 멈추는 것처럼 보이고, 그 사이에 다른 프로세스의 출력이 이어지는 것을 확인할 수 있다. 실행 중이던 프로세스가 sleep()과 함께 대기 상태로 전환되면서 CPU를 사용할 수 없게 되고, 그 순간 운영체제는 준비 상태에 있는 다른 프로세스를 선택하기 때문이다.
이 실습을 통해 확인할 수 있는 것은, 프로세스는 실행과 대기를 반복하며 대기 이후에는 준비 상태를 거쳐 다시 실행된다는 흐름이다.
Practice: Observing Preemptive Scheduling
This example has both parent and child processes running while loops. The code contains no instruction to stop execution. Yet the execution results show the parent and child output alternating infinitely. Press Ctrl+C to terminate.
This switching does not happen because the processes voluntarily give up the CPU. It happens because the operating system forcibly swaps the running process at fixed time intervals.
What this lab demonstrates is the core characteristic of preemptive scheduling: even when execution is not finished, the operating system can reclaim the CPU when it judges this necessary.
실습으로 확인하는 선점 스케줄링
이 예제는 부모와 자식 프로세스가 모두 while 반복문을 수행하는 구조다. 코드 안에는 실행을 중단하라는 명령이 없다. 그럼에도 실행 결과를 보면 부모와 자식의 출력이 무한히 번갈아가며 나타난다. 종료하려면 Ctrl+C를 누르면 된다.
이 교체는 프로세스가 스스로 CPU를 내려놓은 것이 아니다. 운영체제가 일정 시간 단위로 실행 중인 프로세스를 강제로 교체하기 때문에 나타나는 결과다.
이 실습을 통해 확인할 수 있는 것은, 실행이 끝나지 않았더라도 운영체제가 필요하다고 판단하면 CPU를 회수할 수 있다는 선점 스케줄링의 핵심 특징이다.
Practice: Observing Non-Preemptive Scheduling
This example is configured so that one process calls sleep() and temporarily enters a waiting state.
Running it shows that one side finishes first, and then the other side executes. No forced switching occurs mid-execution. This is because the next process only runs once the running process voluntarily transitions to a waiting state or terminates.
What this practice allows us to directly observe is the defining characteristic of non-preemptive scheduling: execution flow only transfers when a process voluntarily relinquishes the CPU.
실습으로 확인하는 비선점 스케줄링
이 예제는 한 프로세스가 sleep()을 호출해 일시적으로 대기 상태로 들어가도록 구성한 코드다.
실행해보면 한쪽 작업이 먼저 끝난 뒤 다른 쪽 작업이 실행되는 것을 확인할 수 있다. 실행 도중 강제로 교체되는 모습은 나타나지 않는다. 실행 중인 프로세스가 스스로 대기 상태로 전환되거나 종료되어야 비로소 다음 프로세스의 실행이 이루어지기 때문이다.
이 실습을 통해 프로세스가 자발적으로 CPU를 반납할 때만 실행 흐름이 전환되는 비선점 스케줄링의 특징을 직접 확인할 수 있다.
