📘 10장. 멀티프로세서 스케줄링

📘 10장. 멀티프로세서 스케줄링

핵심 주제: 여러 CPU 코어가 있을 때, 어떻게 스케줄링할지를 고민.

• 10.1 멀티프로세서 구조:
  SMP (대칭 다중처리) 구조 기반. 여러 CPU가 동일한 메모리 접근.
• 10.2 동기화를 잊지마라:
  여러 코어 간 자원 충돌 방지를 위해 락, 세마포어 등 동기화 필요.
• 10.3 캐시 친화성:
  스레드가 같은 CPU에서 실행되면 캐시 효율성이 증가. 이를 고려한 배치 필요.
• 10.4 단일 큐 스케줄링:
  모든 작업을 하나의 큐에서 처리. 공정하나, 큐 병목 가능.
• 10.5 멀티 큐 스케줄링:
  CPU마다 큐를 따로 둠. 성능 향상 가능, 하지만 부하 불균형 문제 발생 가능.
• 10.6 Linux 멀티 프로세서 스케줄러:
  CFS (Completely Fair Scheduler) 등 Linux에서 사용되는 실제 스케줄러 구조 소개.
• 10.7 요약:
  멀티코어 환경에서는 캐시 효율, 동기화, 큐 구조 등 여러 요소가 성능에 영향.

---

요약

멀티프로세서 시스템에서의 스케줄링은 단일 프로세서 시스템보다 복잡함

캐시 일관성, 동기화, 부하 분산 등 다양한 요소를 고려해야 합니다.

 

---

배경: 멀티프로세서 구조

멀티프로세서 시스템에서는 각 CPU가 자체 캐시를 가지고 있으며, 이로 인해 캐시 일관성 문제가 발생할 수 있습니다.

예를 들어, 하나의 CPU에서 메모리 값을 변경하면 다른 CPU의 캐시에는 이전 값이 남아 있을 수 있습니다.

이를 해결하기 위해 **버스 스누핑(bus snooping)**과 같은 하드웨어 기술이 사용됩니다.

 

---

🧠 1. 컴퓨터는 메모리를 어떻게 저장하고 접근할까?

📚 메모리 계층 구조

컴퓨터 시스템은 속도와 비용의 균형을 맞추기 위해 다단계 메모리 구조를 사용

 

📍 레지스터 < 캐시 < 메인 메모리(RAM) < 디스크(HDD/SSD)
     (가장 빠름)                      (가장 느림)

• 레지스터: CPU 내부에 있는 아주 빠르고 작은 저장 공간.
• 캐시 (L1, L2, L3): CPU에 가까운 고속 메모리. 접근 속도가 빠르고, 최근 자주 사용하는 데이터를 저장.
• 메인 메모리 (RAM): 비교적 크고 느리며, 프로그램 실행에 필요한 대부분의 데이터를 저장.
• 디스크 (SSD/HDD): 아주 느리지만 매우 큰 저장 공간.

 

⚙️ 2. 캐시는 어떻게 작동할까?

✅ 지역성 원리 (Locality)

캐시는 프로그램 실행 패턴을 예측해서 자주 접근할 데이터를 미리 가져다 놓는 방식으로 작동해요.

• 시간적 지역성 (Temporal):
  방금 쓴 데이터는 또 쓸 가능성이 높음 → 다시 접근할 걸 대비해 저장
• 공간적 지역성 (Spatial):
  지금 x 주소에 접근했다면, x 근처의 데이터도 곧 접근할 가능성이 있음 → 덩어리로 미리 불러옴

---

💡 하드웨어 캐시 계층(cache hierarchy)

캐시(Cache)

CPU가 메인 메모리보다 빠르게 데이터에 접근할 수 있도록 도와주는 고속 임시 저장소

하지만 캐시는 용량이 작기 때문에, 더 효율적으로 쓰기 위해 계층 구조로 나눠서 사용

 

 

• 캐시는 CPU와 메모리 사이의 중간 다리 역할
• L1 → L2 → L3 → RAM 순으로 점점 느려지고 커짐
• 속도 vs 용량 트레이드오프
• 지역성(locality)을 기반으로 동작 → 최근/근처의 데이터를 자주 캐시에 둠

 

 

🧱 캐시 계층 구조 (보통 L1 → L2 → L3)

CPU Core
  ├─ L1 Cache (빠르고 작음)
  ├─ L2 Cache (중간 속도, 중간 크기)
  └─ L3 Cache (느리지만 큼, 여러 코어 공유)
        ↓
      Main Memory (RAM)​

 

계층	위치	속도	크기	특징
L1 캐시	CPU 코어 내부	가장 빠름	매우 작음 (16~64KB)	명령어 캐시(I-cache)와 데이터 캐시(D-cache)로 분리됨
L2 캐시	CPU 코어 내부	빠름	중간 크기 (256KB~1MB)	L1보다 느리지만 더 큼
L3 캐시	CPU 전체 공유	느림	큼 (2~64MB)	여러 코어가 함께 사용 (공유 캐시)
RAM (메인 메모리)	CPU 외부	훨씬 느림	큼 (GB 단위)	캐시 미스 시 여기서 데이터를 읽음

 

• L1은 엄청 빠르지만 너무 작음
• L3는 많이 담을 수 있지만 느림
  → 그래서 빠르고 작은 캐시부터 차례대로 조회하면서 성능과 용량의 균형을 맞춤

 

 

🌀 데이터 흐름 예시

CPU가 변수 x를 사용하려고 할 때:

1. L1 캐시에서 찾음 (hit) → 바로 사용! ✅
   1. L1에 없으면 → L2 캐시에서 찾음
   2. L2에도 없으면 → L3 캐시에서 찾음
   3. 그래도 없으면 → RAM에서 가져옴 (매우 느림)
2. 찾은 값을 위 계층 캐시에 복사해두고 사용

 

---

❗️멀티프로세서 시스템에서 생기는 문제: 캐시 일관성 문제

 

 

멀티코어(멀티CPU) 시스템에서는 각 CPU가 자신만의 캐시를 가지고 있어요.
그런데 문제는 이 캐시들이 공유 메모리의 데이터를 복사해 저장한다는 점이에요.

❓문제 상황

• CPU1의 캐시에 x = 10
• CPU2의 캐시에 x = 10

 

• CPU1이 주소 A의 값을 캐시에서 10 → 20로 변경
• CPU2는 같은 주소 A를 메인 메모리에서 읽는데, 여전히 옛날 값 10
• 💥 두 CPU가 서로 다른 값을 갖게 됨 (불일치 발생) → 💣 일관성 깨짐

😱 왜 이렇게 되냐면?

• 캐시에만 변경하고, 메인 메모리에 쓰는 건 나중에(dirty write-back) 하기 때문
• 그래서 CPU2는 메인 메모리에 있는 오래된 값을 읽는 것!

 

---

🔄 해결책: 캐시 일관성 프로토콜 (Cache Coherence Protocol)

 

"모든 CPU들이 메모리 버스를 엿들으면서(snoop), 다른 CPU가 어떤 데이터를 읽거나 쓰는지 감시한다."

💬 버스 스누핑 (Bus Snooping)

• 모든 CPU가 메모리 버스를 감시(snoop)해서, 다른 CPU가 어떤 주소를 읽거나 쓰는지 체크
• 다른 CPU가 내가 갖고 있는 데이터를 바꿨다면?
  • → 내 캐시의 그 데이터를 무효화(Invalidate)
  • → 또는 삭제->갱신(Update) 해서 일관성 유지

---

📦 MESI 프로토콜 (대표적인 일관성 프로토콜)

 

버스 스누핑을 구현할 때 자주 사용하는 상태 기반 프로토콜

상태	의미
M (Modified)	내가 가지고 있고, 메모리와 다름
E (Exclusive)	내가 가지고 있지만 메모리와 같음
S (Shared)	여러 캐시에서 공유
I (Invalid)	무효 상태

→ 이런 상태 전이를 통해 캐시 데이터의 일관성을 유지함

 

 

---

💡 TLB란?

💡 TLB란?

TLB는 Translation Lookaside Buffer의 줄임말이고,
한국어로는 변환 후방 버퍼 또는 그냥 "주소 변환 캐시"라고 불러요.

가상주소를 물리주소로 바꾸는 page table 내용을 캐시해둠

CPU
 └─ TLB (주소 변환 캐시)
     └─ 페이지 테이블 (RAM 안에 있음)
         └─ 실제 물리 메모리

 

🧠 왜 TLB가 필요할까?

👉 현대 운영체제는 가상 메모리(Virtual Memory)를 사용해요.

즉, 프로그램은 실제 메모리(RAM) 주소를 직접 쓰는 게 아니라,
가상의 주소(가상 주소)를 쓰고 -> 실제로는 그걸 실제 물리 주소로 변환해서 사용해요.

이 가상 주소 → 물리 주소 변환은 **페이지 테이블(Page Table)**이라는 걸 통해 이루어져요.

❗문제는?

Page Table을 매번 메인메모리(RAM)에서 찾아가며 변환하려면 너무 느려요.

 

 

✅ 그래서 등장한 해결책: TLB

"TLB는 최근 사용된 가상 주소 → 물리 주소 변환 결과를 캐싱해두는 장치"예요.

• 예전에 한번 변환했던 주소가 또 필요하면
• RAM에 있는 페이지 테이블까지 가지 않고
• TLB에서 빠르게 주소를 찾아낼 수 있어요!

 

🔄 동작 흐름

1. CPU가 어떤 가상 주소 0xABC123에 접근함
2. TLB에 해당 주소가 있는지 먼저 확인
   • 있으면 → 빠르게 물리 주소로 변환 ✅ (TLB hit)
   • 없으면 → 페이지 테이블까지 가서 변환하고, TLB에 저장 ❌ (TLB miss)

 

 

---

동기화(synchronization)

여러 CPU가 공유 데이터를 접근할 때, **동기화(synchronization)**가 필수적입니다.

그렇지 않으면 데이터 불일치나 경합 상태가 발생할 수 있습니다.

따라서 락(lock)과 같은 동기화 메커니즘을 사용하여 상호 배제를 보장해야 합니다.

 

락을 하면 성능이 느려진다.

---

캐시 친화성(cache affinity)

프로세스가 동일한 CPU에서 지속적으로 실행되면 해당 CPU의 캐시에 데이터가 유지되어 성능이 향상됩니다.

이를 **캐시 친화성(cache affinity)**이라고 하며,

스케줄러는 이를 고려하여 프로세스를 가능한 한 동일한 CPU에 할당하려고 합니다.

 

✅ 같은 CPU에서 실행되면?

→ 이미 캐시에 데이터가 올라가 있으니까 → 빠르게 실행됨! (cache hit 발생)

❌ 다른 CPU에서 실행되면?

→ 다른 CPU 캐시에는 아무것도 없음 → 다시 데이터를 RAM에서 불러와야 함 → 느려짐 (cache miss)

 

💥 문제는?

멀티코어 시스템에서는 OS 스케줄러가 프로세스를 자유롭게 어떤 CPU에서든 실행시킬 수 있어요.
그런데 매번 다른 CPU에서 실행되면 성능이 떨어진다는 게 문제.

 

 

 

 

---

단일 큐 스케줄링
모든 작업을 하나의 전역 큐에서 관리하며, 각 CPU는 이 큐에서 작업을 가져와 실행합니다.

이 방식은 공정성을 보장하지만, 큐가 병목이 될 수 있고, 캐시 친화성이 저하될 수 있습니다.

 

 

---

멀티 큐 스케줄링
각 CPU마다 자체적인 큐를 가지고 작업을 관리합니다.

이는 캐시 친화성을 높일 수 있지만, CPU 간의 부하 불균형(load imbalance) 문제가 발생할 수 있습니다.

 

 

---

Linux 멀티프로세서 스케줄러
Linux는 멀티프로세서 환경에서 **Completely Fair Scheduler (CFS)**를 사용하여 각 CPU의 런큐(run queue)를 관리하고,

부하 분산(load balancing) 알고리즘을 통해 CPU 간의 작업 부하를 조절합니다.