[Linux] Scheduling과 Context Switching

Multi Tasking와 Multi Processing에서 언급한 OS의 Scheduling을 이해를 위한 글이다.

---

Multi Tasking

Scheduling 대해서 보기전에 Multi Tasking을 살펴보자.

 

예제는 CPU의 core는 1개이고, process는 2개이다. Process A는 스레드가 1개, Process B는 스레드가 2개 있다. 프로세스는 실행 환경과 자원을 제공하는 컨테이너 역할이고, 실제 CPU 코어를 사용해서 코드를 하나 하나 실행하는 것은 스레드이다.

 

1. CPU의 Core가 Process A에 있는 Thread A1를 실행한다.

 

2. Process A에 있는 Thread A1의 실행을 잠시 멈추고 Process B에 있는 Thread B1를 실행한다.

 

3. Process B에 있는 Thread B1의 실행을 잠시 멈추고 Process B에 있는 Thread B2를 실행한다.

 

이렇게 OS의 Multi Tasking은 여러 프로세스 내의 여러 스레드가 번걸아 실행되는 사이클로 수행된다.

 

따라서 OS는 번갈아 수행되는 각 프로세스(스레드 포함)를 식별하고 실행 상태를 기억하기 위해서 PCB(Process Control Block) 자료구조를 사용한다. 그리고 OS는 어떤 프로세스(스레드 포함)를 얼마 동안 실행시킬지 결정하기 위해서 스케줄링 알고리즘을 사용한다.

---

PCB

PCB(Process Control Block)는 OS가 여러 프로세스(스레드)를 관리하기 위한 데이터 구조이기 때문에 Kernel 영역에 생성 및 저장된다. 그래서 PCB는 프로세스 생성시에 생성하고 실행이 끝나면 폐기한다.

 

OS는 번갈아 혹은 동시에 수행되는 각 프로세스(스레드 포함)를 식별하고 실행 상태를 기억하고 실행 순서를 관리(스케줄링) 하기 위해서 PCB 자료구조를 사용한다.

 

PCB의 구조는 다음 그림과 같으며, 주요 정보는 아래에 설명하였다. 

 

레지스터 값

운영체제의 커널영역에 저장된 PCB에서 스레드의 레지스터 값을 코어(명령어를 실행시키는 부품) 내에 로드하여 코드를 실행시킨다. 이로써, CPU 코어는 PCB를 통해 스레드에서 코드의 실행할 지점을 알수 있게된다.

 

다음 레지스터 등에 저장된 연산 중간값들을 모두 복원하여 이전까지 진행했던 작업을 그대로 이어 실행할수 있다.

• 스레드의 PC 값: 스레드가 다음에 실행할 명령어의 주소를 가리킨다. 스레드가 다시 실행될 때, 이 PC 값이 코어의 PC(Program Counter) Register에 로드되어 실행할 명령어의 위치를 지정한다.
• 스레드의 Stack Pointer 값: 스레드의 스택에 최상단의 위치를 가리킨다. 스레드가 다시 실행될때, 함수의 리턴 주소, 지역 변수, 매개변수 등을 기억하는 데 사용된다.
  
  

메모리 관리 정보

프로세스(스레드) 마다 메모리에 저장된 위치가 달라 주소가 필요하다. 그래서 명령어 실행에 필요한 주소 지정 방식에 사용되는 Base register와 Limit Register의 값을 저장한다. 그리고 논리 주소가 아닌 실제 주소를 찾기 위한 Page Table 정보도 PCB에 저장된다.

 

CPU 스케줄링 정보

프로세스(스레드)가 언제, 어떤 순서로 CPU를 할당받을지에 스케줄링 정보를 PCB에 기록한다.

 

프로세스 상태

 

• New: 스레드를 생성중인 상태이며, PCB를 할당 받은 상태
• Ready: CPU를 할당받아서 실행할 준비를 마친 상태
• Running: CPU를 할당 받아 실행중인 상태
• Waiting: I/O 자원 등을 기다리기 위해 대기 상태
• Terminated: 프로세스나 스레드가 종료된 상태

OS의 Scheduler에 의해서 ready 상태인 프로세스나 스레드가 running 상태로 전환되는 것을 dispatch라고 한다.

 

사용한 파일과 입출력 장치 목록

특정 입출력장치나 파일을 사용하면 PCB에 해당 내용 명시한다. 이로써, 어떤 입출력장치가 이 프로세스에 할당되었는지, 어떤 파일들을 열었는지 알수 있다.

---

Scheduling

Muti Core Scheduling

OS는 스레드를 스케줄링 하기 위해서 스케줄링 큐 자료구조를 사용한다. 각 스레드는 스케줄링 큐에서 대기한다고 생각하면 이해가 편하다. 실제로 스케쥴링 큐에는 프로세스(스레드)를 나타내는 자료구조인 PCB가 적재되지만, 이해하기 편하도록 스케줄링 큐에 스레드를 적재한것으로 표현하였다.

 

1. 스레드 A1, 스레드 B1, 스레드 B2가 스케줄링 큐에서 대기한다.

 

2. 스레드 A1과 스레드 B1이 병렬(parallel)로 실행되고 스레드 B2는 스케줄링 큐에서 대기한다.

 

3. 스레드 A1의 수행을 잠시 멈추고 스케쥴링 큐에 다시 PUSH 한다.

 

4. 대기하던 스레드 B2의 CPU Core 1에서 실행한다.

 

이러한 사이클이 프로세스가 종료될때까지 반복된다.

 

Scheduling Queue

이전에 PCB에 CPU 스케줄링 정보가 저장되어 있다고 하였다. 이는 특정 프로세스 내의 스레드가 언제, 어떤 순서로 실행될지를 정해놓은 정보이다. CPU를 사용할 다음 스레드를 찾기 위해 OS가 모든 PCB를 탐색하는 것은 비효율적이다.

 

따라서 CPU를 사용하고 싶은 스레드(Ready), I/O 장치를 사용하고 싶은 스레드(Waiting), 메모리에 적재되고 싶은 스레드(New) 등의 별로 큐에 적재하여 관리한다. 이렇게 OS는 스레드의 상태별로 각 큐에서 관리한다. 그러면 OS가 CPU 코어에서 스레드를 실행시킬려고할때, Ready 상태의 스레드를 관리하는 큐만 보고서 찾을수 있다. (여기서 스케줄링 큐는 반드시 데이터가 FIFO(First In First Out)하는 일반적인 큐일 필요는 없다.)

 

위에서 스레드의 상태 또한 PCB에 저장된다고 하였다. OS의 Scheduler의해 PCB에 저장된 스레드의 상태 별로,각 스케줄링 큐에서 PCB가 관리된다. 스케줄링 큐 중에서 대표적으로 Ready와 Waiting인 상태인 PCB를 관리하는 Ready Queue와 Waiting Queue에 대해서 살펴보자.

 

Ready Queue에는 CPU를 사용하고 싶은 스레드들이 줄을 서는 곳이고, Waiting Queue에는 I/O 장치를 사용하기 위해 스레드들이 줄을 서는 곳을 의미한다. 

 

• Ready Queue: 언제든지 CPU를 할당받아서 쓸수 있지만, 아직 자신의 차례가 되진 않는 스레드를 나타내는 PCB가 관리된다.
• Waiting Queue: 지금 당장은 CPU 쓸 필요가 없어서, 대기 상태인 접어든 스레드를 나타내는 PCB가 관리된다.
  
  

다음은 각 스레드의 상태변경에 따른 동작을 설명한 것이다. 스레드는 자기가 맡은 모든 작업을 수행할때까지 사이클을 반복한다.

1. Ready Queue -> Run on CPU Core 
   스레드가 자신이 실행될 차례가 되어서 스케줄러에 의해 dispatch가 되면, Ready Queue에 있던 PCB는 팝(pop)되고 스레드가 CPU에서 실행을 시작한다.
   
   
2. Run on CPU Core -> Waiting Queue
   스레드에서 실행되는 코드가 I/O 장치를 사용 요청을 하면, 그 스레드는 waiting 상태가 되고, 해당 스레드를 나타내는 PCB가 Waiting Queue에 적재된다. 디스크, 네트워크를 사용하는 I/O 작업은 CPU의 속도에 비해 훨씬 느리기 때문에 Waiting Queue에 따로 관리하는 것이다.
   
   
3. Waiting Queue -> Ready Queue
   I/O 장치에게 요청된 작업이 완료되어서 I/O Interrrupt가 발생하면, Waiting Queue에 있던 PCB는 다시 Ready Queue로 푸시된다.
   
   
4. Run on CPU Core -> Ready Queue
   Timer Interrupt는 하드웨어 타이머에 의해 발생되는 인터럽트이다. 하드웨어 타이머는 CPU의 클럭 사이클을 기반으로 작동하며, 특정 주기마다 인터럽트를 발생시켜 운영 체제의 시간 관리와 스케줄링을 지원한다. 예를들어, 타이머가 1ms마다 인터럽트를 발생시키도록 설정된 경우, 운영 체제는 스레드에게 5ms, 10ms 등으로 실행시간을 할당할수 있다. 이처럼 타이머 인터럽트 주기의 배수로 설정하고, 스레드의 PCB에 CPU 할당 시간을 저장한다. 
   
   타이머 인터럽트가 발생할때마다, CPU는 현재 실행 중인 스레드의 작업을 중단하고, 운영 체제 커널이 인터럽트 핸들러를 실행한다. 타이머 인터럽트 핸들러는 커널의 스케줄러를 호출한다. 이때, 현재 실행 중인 스레드의 PCB을 참조해서 CPU 사용 시간를 감소시킨다. 만약 값이 0이 되었다면, 해당 스레드의 CPU 사용 시간이 만료된 것이다.
   
   CPU 사용 시간이 만료되었으면, 운영 체제는 Context Switching을 수행하여 스레드를 Ready Queue로 보낸다. 아직 남아 있는 경우는 스레드는 계속해서 실행된다.
   
   
5. Disk -> Ready Queue 
   리눅스에서 배치 작업은 실행되기전까지 cron이나 at 데몬이 작업을 예약하고, 이 작업은 파일 시스템에 저장된다. 이후 예약된 시간이 되면, cron이나 at 데몬이 명령어를 실행시켜서 새로운 자식 프로세스가 생성된다. 이 프로세스의 PCB는 Ready Queue로 보내지고 후에 CPU를 할당받아 실행된다. 

Hardware Interrupt란?

위에서 언급한 Timer Interrupt와 I/O Interrupt는 모두 하드웨어 장치가 직접 발생시킨 인터럽트이다. 하드웨어 인터럽트가 발생되면 인터럽트 요청 신호를 보낸다. CPU에게 외부 장치가 인터럽트를 걸기전에 허락을 받아야하는 것이다. 인터럽트를 걸면 CPU 기존의 실행 흐름이 끊기기 때문이다. 그래서 인터럽트 요청을 확인하도록 CPU의 플래그 레지스터에 인터럽트 플래그를 1로 설정한다. 이후, CPU는 실행 사이클이 끝나고 명령어를 인출하기전에 항상 인터럽트 플래그를 확인한다. 인터럽트를 받아들일수 있다면 CPU는 현재 실행중인 스레드의 작업을 백업해둔다. 각 인터럽트마다 동작이 다르기 때문에 각기 다른 프로그램의 인터럽트 핸들러가 저장되어있다. 그래서 CPU는 인터럽트 백터를 참조하여 특정 인터럽트에 대한 인터럽트 핸들러를 실행한다. 인터럽트 핸들러 실행이 끝나면, 백업해둔 작업을 복구해서 실행을 재개한다.

 

Scheduling Algorithms

스케줄링에는 스케줄링 알고리즘으로 수행되는데 단순히 time sharing 뿐만 아니라, 다양한 우선순위와 최적화 기법을 사용한다. 또한 개발할때도 스레드의 우선순위 옵션도 넣어줄수도 있다. OS는 이러한 것들을 모두 반영하여 CPU를 최대한 사용하면서 작업이 골고루 수행될수 있도록 최적화가 된다.

 

Linux에서는 CFS(Completely Fair Scheduler)를 기본 스케줄러로 사용되고 있다. CFS는 스레드나 프로세스의 실행 시간을 공평하게 분배하기 위해 가상 실행 시간(virtual runtime)을 사용한다. 가상 실행 시간은 각 스레드가 CPU를 얼마나 사용했는지를 추적한 가상의 시간이다. 즉, CPU를 더 많이 사용한 스레드는 가상 실행 시간이 더 크고, 덜 사용한 스레드는 가상 실행 시간이 더 작다.

 

스케줄러는 각 스레드의 가상 실행 시간을 추적하고, 가장 작은 가상 실행 시간을 가진 스레드를 선택하여 CPU를 할당한다. CPU를 적게 사용하는 스레드가 우선순위에 있을수록, 뒤에서 CPU를 기다리는 스레드가 더 적게 기다리기 때문이다. 유저 사이드에서도 Java API로 OS library(Standard C Library)를 통해 system call을 호출하여, nice 값을 변경해서 스레드의 우선순위를 조정할 수도 있다.

 

CFS는 Red-Black 트리를 사용하여 자료 구조를 사용하여 스레드를 관리한다. 이 트리는 가상 실행 시간을 기준으로 스레드를 오름차순으로 정렬한다. Red-Black Tree는 균형 잡힌 이진 탐색 트리(self-balancing binary search tree)로 트리의 균형을 자동으로 유지하여 성능을 일정하게 유지하도록한다. 이는 CPU를 덜 사용한 스레드순으로 정렬되도록 보장하는 것이다. 삽입과 삭제 연산을 포함한 여러 연산이 O(logn)시간 복잡도로 수행되고 정렬 시간은 O(nlogn)이 걸려서 효율적으로 스레드의 실행 시간을 관리할수 있다.

 

1.  

Scheduler의 역할

OS의 Scheduler는 시스템에서 CPU 자원을 스레드나 프로세스에 효율적으로 할당하기 위해서 실행 가능한 프로세스나 스레드를 관리한다.

1. 프로세스/스레드 상태 전환
   • Ready 상태로 전환: 스레드가 CPU를 사용할 준비가 되면, 스케줄러는 해당 스레드의 PCB를 Ready Queue 상태로 전환한다. 예를 들어, I/O 작업이 완료되어 인터럽트가 발생하면, 스레드의 PCB Waiting 상태에서 Ready 상태로 전환한다.
   • Waiting 상태로 전환: 스레드가 I/O 작업을 기다리거나 다른 이벤트를 기다려야 하는 경우, 스케줄러는 해당 스레드의 PCB를 Ready 상태로 전환한다.
2. 타이머 인터럽트 처리
   • 타이머 인터럽트 발생: 스레드가 할당된 시간을 모두 사용해서 타이머 인터럽트가 발생하면, 스케줄러는 현재 실행 중인 스레드를 Ready 상태로 전환하고, 다음에 실행할 스레드를 선택한다. 이 과정에서 스케줄러는 상태를 저장하고 복원하는 작업을 수행한다.
3. 프로세스/스레드 생성 및 종료
   • 생성: 새로운 스레드가 생성되면, 스케줄러는 이를 Ready Queue에 푸시하여 CPU 자원을 요청하도록 한다.
   • 종료: 스레드가 종료되면, 스케줄러는 해당 프로세스나 스레드의 PCB를 큐에서 제거한다.
4. 스케줄링 정택 적용
   • 정책에 따른 큐 관리: 스레드가 CPU 자원을 할당받을 준비가된 Ready 상태의 스레드들 중에서 어떤 스레드를 실행할지를 결정해야한다. 이렇게 CPU 자원을 할당받을 준비가 된 스레드들에 대해 효율적인 자원 분배을 위해 다양한 스케줄링 알고리즘(CFS-Normal Scheduling, First-Come First-Served, Round Robin, Priority Scheduling, Multilevel Feedback Queue Scheduling 등)을 정책에 따라 적용한다.

---

Context Switching

Context Switching이란?

Multi Tasking을 수행할때, CPU 코어에서 기존의 스레드를 실행하다가 다른 스레드로 교체할때, 실행되던 스레드의 상태 정보를 기억해 놔야하고 실행할 스레드의 상태 정보를 불러와야한다. 이렇게 실행의 문맥(context)인 스레드 간에 전환되는 것을 Context Switching이라한다. 예를들어, 스레드의 할당된 시간이 만료되거나 인터럽트 혹은 시스템 콜이 발생할때 Context Switching이 발생한다.

 

그러므로 실행하던 스레드의 PCB를 백업하고, 실행할 스레드의 PCB에 저장된 레지스터 값을 CPU의 코어(명령어를 실행시키는 부품)로 복구시켜야한다. 따라서 이 과정은 약간의 시간이 지체된다. 

 

CPU 코어와 스레드의 개수에 따른 Context Switching

멀티 스레딩은 대부분 효율적이지만, Context Switching 과정이 필요하므로 항상 효율적이지는 않다.

예를 들어서 1- 10000까지 더해야 한다고 가정해보자. 이 문제는 둘로 나눌 수 있다.

• 스레드 1: 1 ~ 5000까지 더함
• 스레드2: 5001 ~ 10000까지 더함
• 마지막에 스레드1의 결과와 스레드2의 결과를 더함

1. CPU 코어가 2개
   CPU 코어가 2개 있다면 스레드1, 스레드2로 나누어 멀티스레드로 병렬 처리하는게 효율적이다. 모든 CPU를 사용하므로 연산을 2배 빠르게 처리할 수 있다.
   
   
2. CPU 코어가 1개
   CPU 코어가 1개 있는데, 스레드를 2개로 만들어서 연산하면 중간중간 컨텍스트 스위칭 비용이 발생한다. 운영체제 스케줄링 방식에 따라서 다르겠지만, 스레드 1을 1 ~ 1000 정도까지 연산한 상태에서 잠시 멈추고 스레드 2를 5001- 6001까지 연산하는 식으로 반복 할 수 있다. 이때 CPU는 스레드 1을 멈추고 다시 실행할 때 어디까지 연산했는지 알아야 하고, 그 값을 CPU에 다시 불러와야 한다. 결 과적으로 이렇게 반복할 때 마다 컨텍스트 스위칭 비용(시간)이든다.
   
   결과적으로 연산 시간 + 컨텍스트 스위칭 시간이 든다.
   
   이런 경우 단일 스레드로 1 ~ 10000까지 더하는 것이 컨텍스트 스위칭 비용 없이, 연산 시간만 사용하기 때문에 더 효율적이다.
   
   예를 이렇게 들었지만 실제로 컨텍스트 스위칭에 걸리는 시간은 아주 짧다. 하지만 스레드가 매우 많다면 이 비용이 커질 수 있다. 물론, 최신 CPU는 초당 수 십억 단위를 계산하기 때문에 실제로는 계산에 더 큰 숫자를 사용해야 컨텍스트 스위칭이 발생한다.
   
   
3. CPU - 4개, 스레드 2개
   스레드의 숫자가 너무 적으면 모든 CPU를 100% 다 활용할 수 없지만, 스레드가 몇개 없으므로 컨텍스트 스위칭 비용이 줄어든다.
   
   
4. CPU-4개, 스레드 100개
   스레드의 숫자가 너무 많으면 CPU를 100% 다 활용할 수 있지만 컨텍스트 스위칭 비용이 늘어난다.
   
   
5. CPU - 4개, 스레드 4개
   스레드의 숫자를 CPU의 숫자에 맞춘다면 CPU를 100% 활용할 수 있고, 컨텍스트 스위칭 비용도 자주 발생하지 않기 때문에 최적의 상태가 된다. 이상적으로는 CPU 코어 수 + 1개 정도로 스레드를 맞추면 특정 스레드가 잠시 대기할 때 남은 스레드를 활용할 수 있다.

---

웹 애플리케이션 서버의 CPU 코어와 스레드 개수 설정

CPU 바운드 작업 vs I/O 바운드 작업

각각의 스레드가 하는 작업은 크게 2가지로 구분할 수 있다.

• CPU-바운드 작업 (CPU-bound tasks)
  • CPU의 연산 능력을 많이 요구하는 작업을 의미한다.
  • 이러한 작업은 주로 계산, 데이터 처리, 알고리즘 실행 등 CPU의 처리 속도가 작업 완료 시간을 결정하는 경우다. 따라서 스레드가 CPU에서 실행되는 시간이 많다.
  • 예시: 복잡한 수학 연산, 데이터 분석, 비디오 인코딩, 과학적 시뮬레이션 등

• I/O-바운드 작업 (I/O-bound tasks)
  • 디스크, 네트워크, 파일 시스템등 입출력(I/O) 작업을 많이 요구하는 작업을 의미한다.
  • I/O 작업 요청 이후에 I/O 작업이 완료될때까지, 스레드는 CPU를 사용하지 않고 Waiting Queue에서 대기한다. 이때, I/O 작업이 완료되기까지 대기 시간이 많이 소요된다. I/O 작업은 CPU의 속도에 비해 훨씬 느리기 때문에 Waiting Queue에서 따로 관리하는 것이다. 
  • 예시: 데이터베이스 쿼리 처리, 파일 읽기/쓰기, 네트워크 통신, 사용자 입력 처리 등

 

웹 애플리케이션 서버의 적절한 CPU 코어와 스레드의 개수

 

분야마다 다르겠지만, 웹 애플리케이션 서버에서는 CPU-바운드 작업 보다는 I/O-바운드 작업이 많다.

 

예를 들어서 백엔드 개발자의 경우 주로 웹 애플리케이션 서버를 개발하는데, 스레드가 1 ~ 10000까지 더하는 CPU의 연산이 필요한 작업보다는, 대부분 사용자의 입력을 기다리거나, 데이터베이스를 호출하고 그 결과를 기다리는 등, 스레드가 대가하는 일이 많다. 스레드가 CPU를 많이 사용하지 않는 I/O 바운드 작업이 많다는 것이다.

 

일반적인 자바 웹 애플리케이션 서버의 경우 사용자의 요청 하나를 처리하는데 1개의 스레드가 필요하다. 사용자 4명이 동시에 요청하 면 4개의 스레드가 작동하는 것이다. 그래야 4명의 사용자의 요청을 동시에 처리할 수 있다.

 

사용자의 요청을 하나 처리하는데, 스레드는 CPU를 1% 정도 사용하고, 대부분 데이터베이스 서버에 어떤 결과를 조회하면서 기다린 다고 가정하자. 이때는 스레드는 CPU를 거의 사용하지 않고 대기한다. 바로 I/O 바운드 작업이 많다는 것이다.

 

이 경우 CPU 코어가 4개 있다고해서 스레드 숫자도 CPU 코어에 맞추어 4개로 설정하면 안된다! 그러면 동시에 4명의 사용자 요청만 처리할 수 있다. 이때 CPU는 단순하게 계산해서 4% 정도만 사용할 것이다. 결국 사용자는 동시에 4명 밖에 못받지만 CPU는 4%만 사용하며 CPU가 놀고 있는 사태가 벌어질 수 있다.

 

사용자의 요청 하나를 처리하는데 CPU를 1%만 사용한다면 단순하게 생각해도 100개의 스레드를 만들 수 있다. 이렇게 하면 동시에 100명의 사용자 요청을 받을 수 있다. 물론 실무에서는 성능 테스트를 통해서 최적의 스레드 숫자를 찾는 것이 이상적이다.

 

결국 스레드 숫자만 늘리면 되는데, 이런 부분을 잘 이해하지 못해서 서버 장비에 문제가 있다고 생각하고 2배 더 좋은 장비로 구매하는 사태가 발생하기도 한다! 이렇게 되면 CPU는 4%의 절반인 2%만 사용하고 사용자는 여전히 동시에 4명 밖에 받지 못하는 사태가 벌어진다.

 

정리하면 스레드의 숫자는 CPU-바운드 작업이 많은가, 아니면 I/O-바운드 작업이 많은가에 따라 다르게 설정해야 한다.

• CPU-바운드 작업: CPU 코어 수 + 1개
  • CPU를 거의 100% 사용하는 작업이므로 스레드를 CPU 숫자에 최적화
• I/O-바운드 작업: CPU 코어 수 보다 많은 스레드를 생성, CPU를 최대한 사용할 수 있는 숫자까지 스레드 생성
  • CPU를 많이 사용하지 않으므로 성능 테스트를 통해 CPU를 최대한 활용하는 숫자까지 스레드 생성
  • 단, 너무 많은 스레드를 생성하면 컨텍스트 스위칭 비용도 함께 증가 (적절한 성능 테스트 필요)

참고로 웹 애플리케이션 서버라도 상황에 따라 CPU 바운드 작업이 많을 수 있다. 이 경우 CPU-바운드 작업에 최적화된 CPU 숫자를 고려하면 된다.

---

• 참고
  • Operating System Concepts 10th Edition
  • 김영한의 실전 자바 - 고급 1편, 멀티스레드와 동시성
  • https://documentation.ubuntu.com/real-time/en/latest/explanation/schedulers/