처음에는 "공개키로 암호화하면 되는 것 아닌가?"라고 생각했습니다. 그런데 곧 "그 공개키는 어떻게 믿을 수 있지?"라는 의문이 생겼고, 이어서 "중간에 누군가 끼어들면 어떻게 되지?"라는 질문으로 넘어가게 되었습니다. 이 흐름대로 하나씩 정리해 보겠습니다.

1. HTTP는 왜 위험할까

HTTP는 데이터를 평문 그대로 전송합니다. 클라이언트와 서버 사이에는 공유기, ISP, 라우터 같은 장비가 수없이 많은데, 그중 어느 지점에서든 패킷을 들여다볼 수 있다면 다음과 같은 문제가 생깁니다.

이 문제를 해결하기 위해 HTTP를 TLS로 감싼 것이 HTTPS입니다. 참고로 SSL은 TLS의 이전 이름입니다. SSL은 보안 취약점 때문에 더 이상 사용되지 않고, 현재는 TLS 1.2와 TLS 1.3이 주로 쓰이고 있습니다.

2. 먼저 알아야 할 개념: 대칭키와 비대칭키

대칭키

대칭키 방식은 암호화할 때와 복호화할 때 같은 키를 사용합니다. 속도가 빠르다는 장점이 있지만, 이 키를 상대방에게 어떻게 안전하게 전달할 것인가라는 문제가 남습니다.

비대칭키 (공개키 / 개인키)

비대칭키 방식은 키가 한 쌍으로 이루어져 있습니다. 공개키는 누구에게나 공개해도 되고, 개인키는 주인만 보관합니다. 쓰임새는 크게 두 가지입니다.

• 암호화: 공개키로 암호화한 데이터는 개인키로만 복호화할 수 있습니다.
• 서명: 개인키로 서명한 데이터는 공개키로 검증할 수 있고, 이를 통해 실제 주인이 서명했다는 사실을 확인할 수 있습니다.

다만 대칭키에 비해 연산이 느립니다.

그래서 TLS는 두 방식을 함께 사용합니다. 비대칭키로 안전한 연결을 준비하고, 실제 데이터는 빠른 대칭키(세션 키)로 주고받는 구조입니다.

3. 처음 떠올린 방법: RSA 키 교환 (TLS 1.2까지)

가장 직관적인 방법은 다음과 같습니다.

1. 서버는 통신을 시작하기 전에 공개키와 개인키를 미리 만들어 둡니다. 공개키는 암호화에, 개인키는 복호화에 사용합니다.
2. 클라이언트는 세션 키(대칭키)를 생성합니다. 이 키 하나로 암호화와 복호화를 모두 처리합니다.
3. 클라이언트는 서버로부터 공개키를 받습니다.
4. 받은 공개키로 세션 키를 암호화해서 서버에 보냅니다.
5. 서버는 개인키로 이를 복호화해 세션 키를 얻습니다.
6. 이제 양쪽은 같은 세션 키로 데이터를 암호화해 보내고, 받은 쪽에서 복호화합니다.

  Client                                           Server
    |                                                 |  (1) generate key pair
    |  (2) generate session key                       |
    |                                                 |
    |<----------------------- (3) server public key --|
    |                                                 |
    |-- (4) Enc(public key, session key) ------------>|
    |                                                 |  (5) Dec(private key)
    |                                                 |      -> session key
    |                                                 |
    |<======= (6) encrypted with session key ========>|

누군가 중간에서 엿보더라도 암호화된 세션 키만 보일 뿐이고, 개인키가 없으니 풀 수 없습니다. 언뜻 보면 빈틈이 없어 보입니다.

참고로 실제 TLS에서는 세션 키를 그대로 보내지 않습니다. pre-master secret이라는 비밀값을 보낸 뒤, 양쪽이 이 값을 바탕으로 세션 키를 만들어 냅니다. 하지만 공개키로 암호화해서 보내고 개인키로 푼다는 원리 자체는 동일합니다.

문제는 3번 단계에 있습니다.

4. 그 공개키는 정말 서버의 것일까

클라이언트에게는 받은 공개키가 진짜 서버의 것인지 확인할 방법이 없습니다. 바로 이 지점에서 MITM(Man-In-The-Middle), 즉 중간자 공격이 가능해집니다.

MITM 공격 시나리오

공격자가 공용 와이파이 같은 환경에서 클라이언트와 서버 사이에 끼어들었다고 가정해 보겠습니다.

  Client                    Attacker                  Server
    |                         |                         |
    |                         |<------ server pub ------|
    |<----- attacker pub -----|                         |
    |                         |                         |  (1) swap public key
    |                         |                         |
    |-- Enc(attacker pub, --->|                         |
    |    session key)         |                         |
    |                         | Dec(attacker priv)      |  (2)(3)
    |                         | -> session key!         |
    |                         |                         |
    |                         |--- Enc(server pub, ---->|
    |                         |    session key)         |  (4)
    |                         |                         |
    |<========== reads & modifies everything ==========>|

1. 공격자는 서버의 공개키를 가로채고, 자신의 공개키를 서버의 것처럼 클라이언트에게 전달합니다.
2. 클라이언트는 이를 모른 채 공격자의 공개키로 세션 키를 암호화합니다.
3. 공격자는 자신의 개인키로 이를 복호화해 세션 키를 손에 넣습니다.
4. 그런 다음 서버의 공개키로 다시 암호화해서 서버에 넘깁니다.

클라이언트와 서버는 모두 정상적으로 통신하고 있다고 믿지만, 실제로는 공격자가 대화 내용을 모두 읽을 수 있고 필요하면 바꿀 수도 있습니다.

여기서 주목할 점은 암호화 자체에는 아무 문제가 없었다는 것입니다. 빠져 있던 것은 "지금 누구와 암호화된 통신을 하고 있는가"에 대한 확인이었습니다.

5. 해결책: CA와 인증서

그렇다면 신뢰할 수 있는 제3자가 "이 공개키는 naver.com의 것이 맞다"고 보증해 주면 됩니다. 이 역할을 하는 기관이 CA(Certificate Authority, 인증기관)입니다.

5-1. 인증서 발급 과정

1. 서버가 키 쌍을 직접 생성합니다. 개인키는 절대 서버 밖으로 나가지 않아야 합니다. CA가 대신 만들어 준다면 CA도 개인키를 알게 되기 때문입니다.
2. 서버는 공개키와 도메인 정보를 담은 요청서(CSR)를 CA에 제출합니다.
3. CA(정확히는 등록 업무를 담당하는 RA)가 요청자가 실제 도메인 소유자인지 확인합니다.
4. 확인이 끝나면 CA가 인증서를 만듭니다. 인증서 내용(도메인, 서버 공개키, 유효기간, 발급자 등)으로 해시값을 계산하고, 그 해시값에 CA의 개인키로 서명합니다.
5. 인증서 내용과 CA의 서명을 묶어 서버에 발급합니다.

저는 처음에 "CA가 서버의 공개키를 암호화한다"고 잘못 이해하고 있었습니다. 실제로 서버의 공개키는 인증서 안에 그대로 노출되어 있습니다. CA가 하는 일은 암호화가 아니라 서명입니다. 내용을 숨기려는 것이 아니라, CA가 이 내용을 보증하며 중간에 변경되지 않았다는 사실을 증명하려는 것입니다.

5-2. 인증서의 구성

+--------------------------------------------+
|  Certificate (X.509)                       |
+--------------------------------------------+
|  Version       : v3                        |
|  Serial Number : 04:a1:9f:...              |
|  Issuer        : DigiCert ... CA           |
|  Validity      : 2026-01-01 ~ 2027-01-01   |
|  Subject       : www.naver.com             |
|  Public Key    : server public key         |
|  Extensions    : SAN: *.naver.com, ...     |
+--------------------------------------------+
|  Sig. Alg. : sha256WithRSAEncryption       |
|  Signature : Sign(CA private key,          |
|                   hash(contents above))    |
+--------------------------------------------+

5-3. 클라이언트의 인증서 검증

운영체제와 브라우저에는 신뢰할 수 있는 CA의 인증서(공개키)가 미리 내장되어 있습니다. 이를 루트 인증서 저장소라고 부릅니다. Microsoft, Apple, Google, Mozilla가 각자 기준을 정해 두고, 그 기준을 통과한 CA만 목록에 포함시킵니다.

검증은 다음 순서로 이루어집니다.

1. 인증서 내용으로 해시값을 직접 계산합니다.
2. 인증서에 첨부된 서명을 미리 가지고 있던 CA의 공개키로 검증합니다.
3. 서명이 일치하면 CA가 보증한 내용이며 중간에 변조되지 않았다는 뜻입니다.
4. 추가로 인증서의 도메인이 현재 접속하려는 주소와 같은지, 유효기간이 지나지 않았는지를 확인합니다.

실제로는 루트 CA가 서버 인증서에 직접 서명하지 않고, 루트 CA에서 중간 CA를 거쳐 서버 인증서로 서명이 이어집니다. 이를 인증서 체인이라고 하며, 브라우저는 이 체인을 따라 올라가 루트 저장소에 있는 CA까지 도달하는지 확인합니다.

5-4. 인증서를 그대로 복사하면 어떻게 될까

인증서는 공개된 정보이므로 공격자도 naver.com의 실제 인증서를 그대로 복사해 보여줄 수 있습니다. 하지만 공격자에게는 그 인증서에 담긴 공개키와 짝을 이루는 개인키가 없습니다.

• RSA 키 교환에서는 클라이언트가 인증서 속 공개키로 세션 키를 암호화해 보냅니다. 개인키가 없는 공격자는 이를 복호화할 수 없습니다.
• TLS 1.3에서는 서버가 핸드셰이크 내용에 자신의 개인키로 서명해서 보냅니다(CertificateVerify). 개인키가 없는 공격자는 이 서명을 만들어 낼 수 없습니다.

결국 인증서는 "이 공개키가 naver.com의 것"임을 확인해 주고, 개인키를 실제로 사용할 수 있는지가 "지금 통신하는 상대가 그 주인"임을 확인해 줍니다. 두 가지가 모두 갖춰져야 신원 확인이 완료됩니다.

5-5. MITM이 막히는 원리

공격자가 시도할 수 있는 방법은 크게 두 가지인데, 어느 쪽도 성공하지 못합니다.

6. 남은 문제: 개인키가 나중에 유출된다면

RSA 키 교환에는 또 하나의 약점이 있습니다. 서버의 개인키 하나만 있으면 모든 세션 키를 풀 수 있다는 점입니다.

공격자가 오늘 오가는 암호화된 통신을 모두 저장해 두었다가, 몇 년 뒤 서버의 개인키를 탈취했다고 생각해 보겠습니다. 그러면 저장해 둔 세션 키를 복호화할 수 있고, 결과적으로 과거의 대화 내용까지 전부 해독할 수 있게 됩니다.

이 문제를 해결하기 위해 등장한 방식이 ECDHE입니다.

6-1. ECDHE: 세션 키를 아예 보내지 않는 방식

ECDHE의 아이디어는 세션 키를 암호화해서 전송하는 대신, 양쪽이 각자 계산해서 같은 값을 얻도록 하자는 것입니다.

작은 숫자로 직접 계산해 보면 쉽게 이해할 수 있습니다. 아래 예시는 원조 격인 DH 방식이며, ECDHE는 거듭제곱 대신 타원곡선 연산을 사용한다는 차이만 있을 뿐 원리는 같습니다.

① 미리 공개된 숫자

표준으로 정해져 있어 브라우저와 서버 코드에 이미 포함되어 있는 값입니다.

• g = 5, p = 23 (mod 23은 23으로 나눈 나머지를 의미합니다)

② 각자 비밀 숫자 선택 (절대 전송하지 않음)

• 클라이언트: a = 6
• 서버: b = 15

③ 공개값을 계산해서 교환

• 클라이언트: 5⁶ mod 23 = 8 → 서버에 전송
• 서버: 5¹⁵ mod 23 = 19 → 클라이언트에 전송

④ 받은 공개값에 자신의 비밀 숫자로 계산

• 클라이언트: 19⁶ mod 23 = 2
• 서버: 8¹⁵ mod 23 = 2

양쪽 모두 2라는 같은 값을 얻었습니다. 이것이 공유 비밀값입니다.

같은 값이 나오는 이유는 간단합니다. 클라이언트가 계산한 19⁶은 (5¹⁵)⁶, 즉 5^(15×6)이고, 서버가 계산한 8¹⁵는 (5⁶)¹⁵, 즉 5^(6×15)입니다. 곱하는 순서만 다를 뿐 둘 다 5^(a×b)를 계산한 셈입니다.

반면 중간에서 엿본 사람은 5, 23, 8, 19만 알고 있습니다. 공유 비밀값을 구하려면 "5를 몇 번 거듭제곱해야 8이 되는가"를 풀어야 하는데, 실제로는 수백 자리에 달하는 큰 수를 사용하기 때문에 현실적으로 풀 수 없습니다.

6-2. 전방 비밀성 (Forward Secrecy)

ECDHE의 E는 Ephemeral, 즉 "일회용"을 뜻합니다. 비밀 숫자는 연결할 때마다 새로 생성되고, 연결이 끝나면 폐기됩니다.

또한 서버의 개인키는 더 이상 세션 키 계산에 쓰이지 않고 신원 증명(서명)에만 사용됩니다. 따라서 나중에 개인키가 유출되더라도 과거의 대화는 안전하게 보호됩니다. 이 성질을 전방 비밀성이라고 합니다.

6-3. ECDHE만으로 MITM을 막을 수 있을까

그렇지 않습니다. ECDHE만으로는 중간자 공격을 막을 수 없습니다.

공격자가 클라이언트와는 자신의 공개값으로, 서버와는 또 다른 공개값으로 각각 키 교환을 진행하면 두 개의 연결을 따로 맺고 그 사이에서 중계할 수 있기 때문입니다. 4장에서 살펴본 공격과 구조가 똑같습니다.

그래서 TLS 1.3에서는 서버가 ECDHE 공개값이 포함된 핸드셰이크 전체에 개인키로 서명합니다. 공격자가 공개값을 바꿔치기하면 서명이 일치하지 않아 곧바로 드러나게 됩니다.

정리하자면 ECDHE는 도청을 막고, 인증서와 서명은 사칭을 막습니다. 안전한 통신을 위해서는 둘 다 필요합니다.

7. TLS 1.3 핸드셰이크 전체 흐름

  Client                                           Server
    |                                                 |
    |-- ClientHello --------------------------------->|
    |  random, key_share (client ECDHE pub)           |
    |                                                 |
    |<--------------------------------- ServerHello --|
    |  random, key_share (server ECDHE pub)           |
    |                                                 |
    |      [ both compute shared secret -> keys ]     |
    |                                                 |
    |<------------------------------- {Certificate} --|
    |<------------------------- {CertificateVerify} --|
    |<---------------------------------- {Finished} --|
    |                                                 |
    |-- {Finished} ---------------------------------->|
    |                                                 |
    |<============== application data ===============>|

  {...} = encrypted

TLS 1.2에서는 핸드셰이크에 왕복이 두 번 필요했지만, TLS 1.3은 키 교환 재료를 첫 메시지에 바로 실어 보내면서 왕복 한 번(1-RTT)으로 줄였습니다. 세션 키가 더 일찍 만들어지기 때문에 인증서부터 암호화된 상태로 전송된다는 점도 달라진 부분입니다.

헷갈리기 쉬운 세 종류의 키

8. 그럼에도 MITM이 성공하는 경우

TLS가 중간자 공격을 막아 주기는 하지만, 다음과 같은 상황에서는 뚫릴 수 있습니다.

사용자가 인증서 경고를 무시하는 경우 "이 연결은 안전하지 않습니다"라는 경고 화면에서 "계속 진행"을 누르면 공격자의 인증서를 신뢰하게 됩니다.

공격자의 루트 인증서가 PC에 설치된 경우 악성 프로그램이 루트 저장소에 가짜 CA를 등록하면, 그 CA로 서명한 인증서는 모두 검증을 통과합니다. 사실 회사의 보안 프록시가 HTTPS 트래픽을 검사하는 것도 이와 같은 방식입니다.

CA가 해킹당하거나 인증서를 잘못 발급한 경우 이에 대비해 인증서 폐기 목록(CRL, OCSP)과 발급 기록을 공개하는 Certificate Transparency 같은 장치가 마련되어 있습니다.

처음 접속을 HTTP로 하는 경우 (SSL Stripping) 사용자가 http://로 접속하는 순간, 공격자가 HTTPS로의 전환을 가로막고 평문으로 중계할 수 있습니다. 서버는 HSTS 헤더를 통해 "앞으로는 반드시 HTTPS로만 접속하라"고 브라우저에 알려 이를 방지합니다.

지금까지의 내용을 짧게 정리하면 다음과 같습니다.

1. HTTP는 평문으로 통신하기 때문에 도청, 변조, 사칭에 취약합니다.
2. 공개키로 세션 키를 암호화해 보내면 도청은 막을 수 있지만, 공개키의 진위를 확인하지 못하면 중간자 공격에 노출됩니다.
3. 이를 위해 CA가 서버 공개키에 서명한 인증서로 공개키의 주인을 보증하고, 서버는 개인키 서명으로 자신이 그 주인임을 증명합니다.
4. RSA 키 교환은 개인키가 유출되면 과거 대화까지 해독될 수 있어, TLS 1.3에서는 세션 키를 전송하지 않는 ECDHE만 남게 되었습니다.
5. 결국 HTTPS는 비대칭키로 신원 확인과 키 합의를 수행하고, 실제 데이터는 대칭키인 세션 키로 빠르게 암호화하는 구조입니다.

처음에는 단순히 "암호화해서 보낸다" 정도로만 알고 있었는데, 막상 들여다보니 누구와 통신하는지 확인하는 과정이 훨씬 큰 비중을 차지하고 있었습니다. 같은 부분에서 헷갈리셨던 분들께 이 글이 조금이나마 도움이 되었으면 합니다.

JPA를 처음 배우면서 헷갈렸던 개념들을 정리했습니다. 기본 키 생성 전략, Flush, 준영속 상태, JPA Auditing, JpaRepository 동작 원리까지 다룹니다.

목차

1. @Id와 기본 키 생성 전략
2. Flush: 영속성 컨텍스트의 동기화
3. 준영속 상태와 merge()
4. JPA Auditing
5. Spring Data JPA - JpaRepository

1. @Id와 기본 키 생성 전략

엔티티를 만들 때마다 항상 기본 키 설정이 필요하다. PK를 할당하는 방법은 크게 2가지다.

1. 직접 넣기
2. DB에게 맡기기: @GeneratedValue

@GeneratedValue에는 4가지 옵션이 존재한다.

IDENTITY

기본 키 생성을 데이터베이스에 위임하는 전략이다. (MySQL의 AUTO_INCREMENT)

특징: 쓰기 지연이 동작하지 않는다.

영속성 컨텍스트의 1차 캐시는 key-value 구조로 관리되는데, key를 만들기 위해 ID 값이 필요하다. AUTO_INCREMENT는 DB에 INSERT 쿼리를 날려야 ID가 생성되므로, em.persist() 호출 즉시 INSERT SQL을 DB에 보낸다.

em.persist(member); // 즉시 INSERT 실행 → ID 반환 → 1차 캐시에 저장

SEQUENCE

DB의 시퀀스 오브젝트를 사용하는 전략이다. (Oracle, PostgreSQL, H2)

특징: 쓰기 지연이 가능하다.

persist() 시점에 시퀀스 값만 먼저 조회해서 ID를 확보한 뒤, 실제 INSERT는 커밋 시점에 실행된다.

@SequenceGenerator(
    name = "MEMBER_SEQ_GENERATOR",
    sequenceName = "MEMBER_SEQ",
    initialValue = 1,
    allocationSize = 50 // 성능 최적화 포인트
)
public class SequenceUser {
    @Id
    @GeneratedValue(strategy = GenerationType.SEQUENCE, generator = "MEMBER_SEQ_GENERATOR")
    private Long userId;
}

allocationSize로 성능 최적화

allocationSize = 50으로 설정하면, 시퀀스 조회 쿼리(call next value)가 50번 저장에 단 2번만 발생한다.

• 1번째 호출: 결과 1 → 현재 시퀀스 값, 첫 번째 ID로 사용
• 2번째 호출: 결과 51 → 다음 범위의 시작값 (범위 끝 확인용)

Hibernate는 이 두 값을 바탕으로 1~50 범위를 메모리에 캐시해서, 2~50 사이의 ID는 DB 호출 없이 바로 꺼내 쓴다.

⚠️ JPA(allocationSize = 50)와 DB(INCREMENT BY 1)의 증가값이 다르면 PK 중복 에러가 발생할 수 있다. 반드시 통일시키자.

TABLE

키 생성 전용 테이블을 만들어서 시퀀스를 흉내 내는 전략이다. 모든 DB에서 사용 가능하지만, SELECT + UPDATE + 락으로 인해 성능이 좋지 않다. DB 마이그레이션 과도기나 여러 DB를 지원해야 하는 경우에 사용한다.

AUTO

DB 방언에 따라 IDENTITY, SEQUENCE, TABLE 중 하나를 자동으로 선택한다. 운영 환경에서는 가급적 명시적인 전략을 지정하는 것이 좋다.

전략 비교

실무 표준: IDENTITY

MySQL이 스타트업·웹 서비스의 사실상 표준 DB이고, MySQL은 SEQUENCE를 지원하지 않는다. 또한 INSERT는 대부분 단건으로 일어나므로 IDENTITY와 SEQUENCE의 성능 차이가 거의 없다. 대용량 삽입이 필요한 경우에만 JdbcTemplate이나 MyBatis를 사용하면 된다.

2. Flush: 영속성 컨텍스트의 동기화

Flush는 영속성 컨텍스트의 변경 내용을 DB에 반영하는 작업이다. 쓰기 지연 저장소에 쌓아둔 SQL들을 DB로 한꺼번에 보내는 과정이다.

Flush가 발생하는 시점

1. em.flush() 직접 호출 (수동) 실무에서는 거의 사용하지 않는다.

2. 트랜잭션 커밋 시 자동 호출 tx.commit()을 호출하면 JPA가 자동으로 flush()를 먼저 실행한 뒤 커밋한다.

3. JPQL 쿼리 실행 시 자동 호출 ⭐ 이 메커니즘이 없으면 데이터 불일치 문제가 발생한다.

em.persist(memberA); // 1차 캐시에만 저장 (INSERT 대기 중)
em.persist(memberB);
em.persist(memberC);

// JPQL 실행 직전에 자동 Flush 발동!
// persist한 데이터가 DB에 반영되어야 조회 결과에 포함될 수 있다.
List<Member> result = em.createQuery("select m from Member m", Member.class)
        .getResultList();
// → 결과: 3명 조회됨

Flush 후 1차 캐시는 비워질까?

절대 지워지지 않는다.

Flush 동작 순서는 다음과 같다.

1. Dirty Checking: 1차 캐시 객체와 스냅샷 비교 → 변경 사항 있으면 UPDATE SQL 생성
2. SQL 전송: 쓰기 지연 SQL 저장소의 쿼리들을 DB에 전송
3. DB 응답: DB가 SQL을 받아서 실행 (아직 커밋은 안 된 상태)
4. 1차 캐시: 아무 일도 일어나지 않는다. 객체는 그대로 남아있다.

1차 캐시를 비우지 않는 이유는 JPA의 핵심 철학인 영속성과 동일성 때문이다.

• 재사용성: 방금 저장하고 바로 다시 조회하는 경우가 많으므로 캐시를 비우면 비효율적이다.
• 동일성 보장: 한 트랜잭션 안에서는 a == b가 항상 참이어야 한다.

flush() vs clear()

FlushMode 설정

• FlushModeType.AUTO (기본값, 권장): 커밋 직전 + JPQL 실행 직전에 자동 flush
• FlushModeType.COMMIT: 오직 커밋할 때만 flush → 쿼리가 꼬일 수 있으므로 주의

특수한 상황이 아니라면 AUTO를 사용하자.

3. 준영속 상태와 merge()

엔티티 생명주기: 4가지 상태

1. 비영속 new로 객체를 생성한 상태. 영속성 컨텍스트와 전혀 관계가 없다.

2. 영속 영속성 컨텍스트에 저장되었거나, DB에서 조회된 상태다.

em.persist(member); // 저장
em.find(Member.class, 1L); // 조회

1차 캐시에 들어가고, Dirty Checking의 대상이 된다. 반드시 ID 값을 가지고 있다.

3. 준영속 ⚠️ 한때는 영속 상태였지만, 영속성 컨텍스트에서 분리된 상태다. 데이터는 있는데 수정이 안 되는 좀비 같은 상태로, 가장 골치 아픈 상태다. ID 값은 있지만 JPA가 관리하지 않으므로 값을 바꿔도 DB에 반영되지 않는다.

em.detach(member); // 준영속으로 전환

4. 삭제 삭제 마킹을 해둔 상태. flush() 시점에 DELETE 쿼리가 실행된다.

em.remove(member);

em.contains(member)로 영속 상태인지 확인할 수 있다.

merge(): 복제 기술, 덮어쓰기

merge는 죽은 객체를 되살리는 게 아니라, 모든 필드를 덮어쓰는 복제 기술이다.

동작 원리

1. JPA가 준영속 객체를 받는다.
2. 객체의 ID로 1차 캐시 확인 → 없으면 DB 조회 (SELECT)
3. 조회한 영속 객체에 준영속 객체의 값을 덮어씌운다.
4. 수정된 영속 객체를 반환한다.
5. 처음 준영속 객체는 여전히 준영속 상태로 버려진다.

merge(member) 호출
  → SELECT 실행
  → 1차 캐시에 저장  {"name": "OriginalName", "grade": "VIP"}
  → 스냅샷에 저장    {"name": "OriginalName", "grade": "VIP"}  ← 기준점
  → 1차 캐시를 준영속 객체 값으로 덮어씌움
     1차 캐시: {"name": "UpdatedName", "grade": "VIP"}
     스냅샷:   {"name": "OriginalName", "grade": "VIP"}  ← 그대로

커밋 시점
  → Dirty Checking → 다름!
  → UPDATE 쿼리 생성 & DB 전송

⚠️ merge의 치명적 함정: null 덮어쓰기

merge는 모든 필드를 덮어쓰기 때문에, 비워진 값이 있다면 null이 DB에 그대로 반영된다.

이름만 바꾸려고 객체 생성
  detachedMember.setId(id);
  detachedMember.setName("UserB");
  // grade는 null 상태!

→ merge() 수행
→ 1차 캐시: {"name": "UserB", "grade": null}
→ UPDATE name = 'UserB', grade = null
→ ☠️ VIP 등급이 증발!

결론: 특수한 상황이 아니라면 merge는 사용하지 말고, Dirty Checking을 활용하자. 영속 상태의 객체를 직접 수정하면 변경된 필드만 선택적으로 UPDATE되므로 항상 안전하다.

4. JPA Auditing

엔티티가 생성/수정될 때 시간을 자동으로 기록해주는 기능이다. 매번 createdAt = LocalDateTime.now()를 직접 쓰지 않아도 자동으로 처리된다.

@CreatedDate / @LastModifiedDate

동작 원리

JPA는 엔티티 생명주기마다 이벤트 훅을 제공한다.

AuditingEntityListener는 Spring Data JPA가 이미 @PrePersist와 @PreUpdate 훅을 구현해둔 클래스다. 우리는 @EntityListeners(AuditingEntityListener.class)로 등록만 하면 된다.

앱 시작
  → JPA가 엔티티 클래스 스캔
  → @EntityListeners 확인 → AuditingEntityListener 등록
  → @PrePersist, @PreUpdate 붙은 메서드 기억해둠

em.persist(member) 호출
  → @PrePersist 시점에 touchForCreate() 실행
  → @CreatedDate 필드에 현재 시간 자동 주입
  → INSERT 쿼리에 시간 포함되어 DB 저장

설정 방법

필수 조건 2가지가 모두 있어야 한다. 하나라도 없으면 시간이 null로 저장된다.

// ① 엔티티에 리스너 등록
@EntityListeners(AuditingEntityListener.class)

// ② 스프링에 Auditing 활성화
@EnableJpaAuditing
@SpringBootApplication
public class Application { ... }

실무 패턴: BaseEntity 상속

@EntityListeners(AuditingEntityListener.class)
@MappedSuperclass // DB 테이블은 안 만들고 필드만 자식 엔티티에 포함
public abstract class BaseEntity {
    @CreatedDate
    private LocalDateTime createdAt;

    @LastModifiedDate
    private LocalDateTime updatedAt;
}

@Entity
public class Member extends BaseEntity { // 상속만 하면 자동 적용
    ...
}

Persistable 인터페이스

@GeneratedValue 없이 ID를 직접 할당하면 문제가 생긴다.

ID == null → 새 엔티티 → INSERT
ID != null → 기존 엔티티로 오판 → SELECT 후 merge (불필요한 SELECT 발생!)

Persistable 인터페이스를 구현해서 새 엔티티 판단 기준을 직접 정의한다.

@EntityListeners(AuditingEntityListener.class)
@MappedSuperclass
public abstract class BaseEntity implements Persistable<String> {

    @CreatedDate
    private LocalDateTime createdAt;

    @Override
    public boolean isNew() {
        return createdAt == null; // 저장 전엔 null → 새 엔티티로 판단
    }
}

@CreatedDate는 persist() 시점에 자동 세팅되므로, 저장 전에는 항상 null이다. 덕분에 isNew() = true → SELECT 없이 바로 INSERT 실행된다.

5. Spring Data JPA - JpaRepository

핵심 의문

인터페이스에 JpaRepository만 상속받았을 뿐인데 어떻게 동작하는가?

기존 방식 vs Spring Data JPA

// 기존: EntityManager 직접 사용
@Repository
public class MemberRepository {
    @PersistenceContext
    private EntityManager em;
    ...
}

// Spring Data JPA: 인터페이스 선언만으로 끝
public interface MemberRepository extends JpaRepository<Member, Long> {}

작동 원리

인터페이스(껍데기)만 만들었는데 누가 구현해줄까? → Spring Framework

1. JpaRepository를 상속한 인터페이스를 작성한다.
2. Spring이 애플리케이션 시작 시 스캔해서 해당 인터페이스를 찾는다.
3. 런타임에 구현 객체(SimpleJpaRepository)를 자동 생성한다.
4. 생성된 프록시 객체를 스프링 빈으로 등록한다.

SimpleJpaRepository

Spring이 자동으로 만들어주는 구현체 내부를 보면:

@Repository
@Transactional(readOnly = true)
public class SimpleJpaRepository<T, ID> implements JpaRepositoryImplementation<T, ID> {
    private final EntityManager entityManager; // 내부적으로 EntityManager를 직접 사용
}

JpaRepository는 EntityManager를 편리하게 감싼 껍데기일 뿐이다. 내부적으로 1차 캐시, 변경 감지 등 JPA의 동작 방식은 그대로 유지된다. → 이것이 우리가 EntityManager를 먼저 배운 이유다.

save() 메서드의 한계

public <S extends T> S save(S entity) {
    if (entityInformation.isNew(entity)) {
        em.persist(entity);  // 새로우면 persist (INSERT)
        return entity;
    } else {
        return em.merge(entity);  // 아니면 merge (SELECT 후 UPDATE 또는 INSERT)
    }
}

isNew()는 ID가 null이면 true, 아니면 false를 반환한다. ID를 직접 할당하면 ID가 null이 아니므로 merge()가 실행되어 불필요한 SELECT가 발생한다.

이 문제는 앞서 설명한 Persistable 인터페이스 구현으로 해결한다.

마치며

JPA를 처음 배울 때 가장 헷갈렸던 부분들을 정리해봤습니다.

핵심을 한 줄씩 요약하면:

• 기본 키 전략: 실무는 IDENTITY, 성능이 필요하면 SEQUENCE + allocationSize
• Flush: DB 동기화일 뿐, 1차 캐시는 절대 비워지지 않는다
• 준영속: 좀비 상태, merge 대신 Dirty Checking을 쓰자
• JPA Auditing: 훅을 직접 안 써도 되는 이유는 Spring이 이미 구현해뒀기 때문
• JpaRepository: EntityManager의 편리한 래퍼, 내부 동작은 동일하다

매번 createdAt = LocalDateTime.now()를 직접 쓰지 않아도 자동으로 처리되는 원리를 익히자.

@CreatedDate / @LastModifiedDate

동작 원리

JPA 엔티티 생명주기 훅

JPA는 엔티티 생명주기마다 전/후로 실행할 수 있는 이벤트 훅을 제공한다.

앱 시작 시 JPA가 리스너를 스캔하면서 어떤 훅 메서드가 있는지 전부 기억해뒀다가, 해당 시점이 되면 자동으로 실행한다.

AuditingEntityListener

우리가 훅을 직접 구현하지 않아도 되는 이유는, Spring Data JPA가 AuditingEntityListener 안에 이미 구현해뒀기 때문이다.

// AuditingEntityListener 내부 (Spring Data JPA가 만들어둔 것)
public class AuditingEntityListener {

    @PrePersist
    public void touchForCreate(Object target) {
        // @CreatedDate 필드를 찾아서 현재 시간 주입
    }

    @PreUpdate
    public void touchForUpdate(Object target) {
        // @LastModifiedDate 필드를 찾아서 현재 시간 주입
    }
}

AuditingEntityListener는 6개의 훅 중 @PrePersist와 @PreUpdate만 사용한다.

우리는 @EntityListeners(AuditingEntityListener.class)로 "이 리스너 써줘" 라고 등록만 하면 된다.

전체 동작 흐름

앱 시작
  → JPA가 엔티티 클래스 스캔
  → @EntityListeners 확인 → AuditingEntityListener 등록
  → 리스너 안의 @PrePersist, @PreUpdate 붙은 메서드도 기억해둠
  → 이후 해당 시점마다 자동 실행 (매번 확인 X)

em.persist(member) 호출
  → JPA: "PrePersist 시점이다!"
  → 기억해둔 touchForCreate() 실행
  → @CreatedDate 필드에 현재 시간 자동 주입
  → INSERT 쿼리에 시간 포함되어 DB 저장

설정 방법

필수 조건 2가지

① 엔티티에 리스너 등록

@EntityListeners(AuditingEntityListener.class)

② 스프링에 Auditing 활성화

@EnableJpaAuditing
@SpringBootApplication
public class Application { ... }

둘 중 하나라도 없으면 시간이 null로 저장된다.

• @EntityListeners 없으면 → 리스너 자체가 연결 안 됨
• @EnableJpaAuditing 없으면 → 리스너가 Bean으로 등록 안 돼서 동작 안 함

실무 패턴: BaseEntity 상속

엔티티마다 @EntityListeners를 붙이는 건 번거롭기 때문에, BaseEntity를 하나 만들어서 상속하는 방식을 사용한다.

@EntityListeners(AuditingEntityListener.class)
@MappedSuperclass // DB 테이블은 안 만들고 필드만 자식 엔티티에 포함
public abstract class BaseEntity {

    @CreatedDate
    private LocalDateTime createdAt;

    @LastModifiedDate
    private LocalDateTime updatedAt;
}

@Entity
public class Member extends BaseEntity { // 상속만 하면 자동 적용
    ...
}

@Entity
public class Order extends BaseEntity { // 얘도 자동 적용
    ...
}

@MappedSuperclass는 DB 테이블을 별도로 만들지 않고, 필드만 자식 엔티티 테이블에 포함시켜 주는 어노테이션이다.

Persistable 인터페이스

왜 필요한가?

@GeneratedValue를 사용하면 JPA가 ID를 자동 생성하기 때문에 새 엔티티인지 판단이 쉽다.

하지만 ID를 직접 할당하는 경우 문제가 생긴다.

// ID를 직접 세팅하는 경우
Member member = new Member();
member.setId("user-001"); // ID 직접 할당
em.persist(member);

JPA는 save() 호출 시 새 엔티티인지 판단하기 위해 ID가 null인지 확인한다.

ID == null → 새 엔티티 → INSERT
ID != null → 기존 엔티티 → SELECT 후 merge (불필요한 SELECT 발생!)

ID를 직접 할당하면 ID가 null이 아니므로, JPA가 기존 엔티티로 오판해서 불필요한 SELECT 쿼리를 날린다.

해결 방법: Persistable 구현

Persistable 인터페이스를 구현해서 새 엔티티 판단 기준을 직접 정의한다.

@EntityListeners(AuditingEntityListener.class)
@MappedSuperclass
public abstract class BaseEntity implements Persistable<String> {

    @CreatedDate
    private LocalDateTime createdAt;

    @Override
    public boolean isNew() {
        // createdAt이 null이면 새 엔티티 (아직 한 번도 저장 안 됨)
        return createdAt == null;
    }
}

동작 흐름

save(member) 호출
  → isNew() 실행
  → createdAt == null ? → true (아직 저장 안 된 새 엔티티)
  → SELECT 없이 바로 INSERT 실행
  → @PrePersist → createdAt에 현재 시간 주입
  → 이후 save() 호출 시 createdAt != null → 기존 엔티티로 판단

결론

ID 직접 할당 전략을 쓴다면 Persistable을 구현해서 불필요한 SELECT를 방지하자.

@CreatedDate와 함께 사용하면 isNew() 판단 기준으로 딱 맞아 떨어진다.

핵심 정리

• JPA 훅(@PrePersist 등)은 앱 시작 시 한 번 스캔해서 기억해뒀다가 해당 시점에 자동 실행된다.
• AuditingEntityListener는 6개 훅 중 @PrePersist, @PreUpdate만 사용하며, Spring이 이미 구현해뒀다. 우리는 등록만 하면 된다.
• ID 자동 생성(@GeneratedValue) → 기본 동작으로 충분하다.
• ID 직접 할당 → Persistable 구현해서 불필요한 SELECT를 막자.

자바의 예외는 크게 Exception과 RuntimeException 두 가지로 나뉜다.

• Exception: 컴파일러에 의해 엄격하게 감시된다. 따라서 try-catch 문을 사용하거나 throws로 처리해야 한다.
• RuntimeException: 컴파일러가 확인하지 않으며 프로그램 실행 중에 발생한다.

스프링 트랜잭션에서 기본적으로 RuntimeException만 롤백된다. Exception은 컴파일러가 체크하는 예외이므로 롤백시키지 않는다.

프로젝트에서는 기본적으로 런타임 예외를 사용하는 것이 적절하다. 체크 예외를 사용할 경우 잦은 try-catch와 throws로 인해 비즈니스 로직에 집중하기 어렵다. 또한 SQL 에러나 네트워크 문제 등은 어차피 복구할 수 없는 경우가 많으며, 런타임 예외는 추가 옵션 없이도 롤백이 가능하여 간편하다.

단, 특정 로직 실패 시 대안 로직(예: 송금 실패 시 재시도)이 실행되어야 하는 경우에는 Exception을 사용할 수 있다. 이때는 트랜잭션에 @Transactional(rollbackFor = Exception.class) 옵션을 명시해야 한다.

커스텀 예외 (Custom Exception) 구현

문제 상황 발생 시 RuntimeException을 발생시켜 롤백을 수행하면 클라이언트는 500 Internal Server Error를 응답받는다. 항상 500 에러를 반환하는 것은 클라이언트 입장에서 정확한 문제 파악을 불가능하게 만든다.

따라서 RuntimeException을 상속받아 상황에 맞는 커스텀 예외를 만들고, 상태 코드와 상세 메시지를 반환하도록 별도의 예외 클래스를 구현해야 한다.

public class EmailDuplicateException extends RuntimeException {
    public EmailDuplicateException(String message) {
        super(message);
    }
}

public class UserNotFoundException extends RuntimeException {
    public UserNotFoundException(String message) {
        super(message);
    }
}

@RestControllerAdvice와 표준 응답 양식

발생한 예외는 @RestControllerAdvice를 통해 전역적으로 처리한다. 이 어노테이션이 붙은 클래스는 모든 RestController를 감시하다가 예외가 발생하면 이를 가로채서 처리한다. 내부에는 @ExceptionHandler(예외명.class)를 통해 각 커스텀 예외별 대응 매뉴얼을 작성한다.

프론트엔드 개발자와 원활하게 협업하기 위해 ErrorResponse라는 표준화된 양식을 객체로 만들어 사용한다. 내부 필드를 JSON으로 변환(직렬화)하기 위해 Getter는 필수적으로 선언해야 한다.

ResponseEntity를 활용하면 HTTP 상태 코드(status code), 헤더(header), 바디(body)를 세밀하게 제어하여 응답할 수 있다.

public class ErrorResponse {

    private String errorCode;
    private String message;

    public ErrorResponse(String errorCode, String message) {
        this.errorCode = errorCode;
        this.message = message;
    }

    // Getter (JSON 직렬화를 위해 필수)
    public String getErrorCode() { 
        return errorCode; 
    }

    public String getMessage() { 
        return message; 
    }
}

@RestControllerAdvice
public class GlobalExceptionHandler {

    @ExceptionHandler(UserNotFoundException.class)
    public ResponseEntity<ErrorResponse> handleUserNotFoundException(UserNotFoundException ex) {
        ErrorResponse response = new ErrorResponse("USER_NOT_FOUND", ex.getMessage());
        return new ResponseEntity<>(response, HttpStatus.NOT_FOUND);
    }

    @ExceptionHandler(EmailDuplicateException.class)
    public ResponseEntity<ErrorResponse> emailDuplicateException(EmailDuplicateException ex) {
        ErrorResponse response = new ErrorResponse("EMAIL_DUPLICATE", ex.getMessage());
        return new ResponseEntity<>(response, HttpStatus.BAD_REQUEST);
    }
}

Spring 전역 예외 처리 동작 흐름

단순한 어노테이션 사용을 넘어, Spring 내부에서 전역 예외 처리가 어떻게 동작하는지 추적해보자.

1. 예외 발생 및 전파 (Service 계층)

• 비즈니스 로직에서 런타임 예외(RuntimeException) 발생.
• 명시적인 예외 처리가 없으므로 콜 스택 언와인딩(Call Stack Unwinding)이 발생하여 상위 호출자를 거쳐 프레임워크 영역(DispatcherServlet)으로 예외가 던져진다.

2. 예외 포착 및 복구 위임 (DispatcherServlet)

• DispatcherServlet.doDispatch() 내부의 catch 블록에서 예외 포착.
• 예외 처리를 위해 processDispatchResult()를 거쳐 processHandlerException()을 호출한다.

3. 담당 resolver 탐색 및 템플릿 메서드 패턴 실행

• handlerExceptionResolvers 목록을 순회하여 @RestControllerAdvice 처리를 담당하는 ExceptionHandlerExceptionResolver를 선택한다.
• 1계층 (공통 처리): AbstractHandlerExceptionResolver.resolveException() 실행. 공통 사전 작업을 수행한 뒤 하위 추상 메서드를 호출한다.
• 2계층 (타입 변환): AbstractHandlerMethodExceptionResolver.doResolveException() 실행. 파라미터로 넘어온 범용 Object를 에러가 발생한 컨트롤러 정보인 HandlerMethod로 안전하게 다운캐스팅 후 하위 추상 메서드를 호출한다.
• 3계층 (실질 로직): ExceptionHandlerExceptionResolver.doResolveHandlerMethodException() 실행.

4. 타겟 메서드 동적 탐색 및 리플렉션 가동

• 파라미터로 전달된 예외 객체의 클래스 타입(예: UserNotFoundException.class)을 Key로 사용하여, 서버 구동 시점에 캐싱해둔 예외-메서드 맵(Map)을 조회한다.
• 예외를 처리할 정확한 @ExceptionHandler 타겟 메서드를 도출한다.
• ServletInvocableHandlerMethod가 자바 리플렉션 API(invoke())를 사용하여 타겟 메서드에 예외 객체를 주입하고 강제로 실행한다.
• 실행 결과로 개발자가 정의한 표준 예외 응답 객체(ErrorResponse)가 반환된다.

5. JSON 직렬화 및 통신 종료 (HttpMessageConverter)

• @RestControllerAdvice에 포함된 @ResponseBody 설정에 의해 RequestResponseBodyMethodProcessor가 개입한다.
• MappingJackson2HttpMessageConverter가 작동하여 내부 Jackson 라이브러리를 호출한다.
• Jackson이 반환된 ErrorResponse 객체의 public Getter를 호출하여 데이터를 읽어낸 뒤 JSON 텍스트로 직렬화한다.
• 완성된 JSON 데이터를 HTTP 응답 스트림(Body)에 작성하고 클라이언트와의 통신을 종료한다.

OCP 관점에서의 설계 분석

이러한 전역 예외 처리 아키텍처는 객체지향의 핵심 원칙인 OCP를 완벽하게 준수한다. 설계의 핵심은 DispatcherServlet이 구체적인 구현체에 의존하지 않고, 다형성을 활용하여 리졸버를 처리한다는 것이다.

• 수정에는 닫혀 있다: DispatcherServlet 내부의 예외 처리 로직은 단순히 HandlerExceptionResolver 인터페이스들의 리스트를 순회하며 처리 가능한 리졸버를 찾는 구조로 되어 있다. 새로운 예외 처리 요구사항이 생겨 응답 방식이 변경되더라도, 메인 파이프라인인 핵심 코드는 단 한 줄도 수정할 필요가 없다.
• 확장에는 열려 있다: 에러 발생 시 Slack 등 외부 채널로 알림을 전송하는 완전히 새로운 예외 처리 방식이 필요해진다면, 기존 코드를 수정할 필요 없이 기능 확장이 가능하다. HandlerExceptionResolver 인터페이스를 구현한 새로운 커스텀 리졸버 클래스를 생성하여 스프링 빈(Bean)으로 등록하기만 하면 된다.

// Spring 프레임워크 내부 코드 구조
for (HandlerExceptionResolver resolver : this.handlerExceptionResolvers) {
    // 인터페이스에만 의존하여 다형성 활용
    ModelAndView exMv = resolver.resolveException(request, response, handler, ex);

    // 처리할 수 있는 리졸버를 찾으면 즉시 반환
    if (exMv != null) {
        return exMv;
    }
}

1. 세션(Session) 기반 인증의 한계 (Stateful)

세션 기반 인증은 사용자가 로그인에 성공하면 서버가 '세션 ID'를 생성하여 중앙 세션 저장소(메모리 또는 DB)에 기록하고, 이를 클라이언트에게 전달하는 방식이다. 이후 클라이언트는 요청마다 세션 ID를 보내고, 서버는 저장소를 뒤져 유저를 확인한다.

이 방식은 서버가 로그인 상태를 직접 기억하고 통제하는 상태 유지(Stateful) 방식이다. 보안 통제(강제 로그아웃 등)가 쉽다는 장점이 있지만, 치명적인 단점이 있다. 사용자가 늘어나 트래픽이 몰릴 때 서버를 여러 대로 확장(Scale-out)하게 되면, 모든 서버가 세션 저장소를 공유하고 매번 조회해야 하므로 성능 병목이 발생하기 쉽다.

2. JWT 기반 인증의 등장 (Stateless)

그렇다면 토큰 기반 인증은 어떨까? 흔히 오해하지만, JWT(JSON Web Token)는 그 자체로 인증 방식이라기보다는 정보를 안전하게 '전달'하는 웹 표준 규격이다.

동작 흐름

1. 클라이언트가 이메일 + 비밀번호로 로그인 요청을 보낸다.
2. 서버는 DB에서 사용자를 조회하고 해시된 비밀번호를 검증한다.
3. 검증이 완료되면, 서버는 유저 데이터와 서버만의 '비밀키(Secret)'를 조합해 서명된 JWT를 발급하여 돌려준다.
4. 이후 클라이언트는 API 요청 시 헤더(또는 쿠키)에 토큰을 담아 보낸다.
5. 서버는 토큰 안의 페이로드와 자신의 비밀키를 이용해 '서명'을 다시 만들어보고, 클라이언트가 보낸 서명과 일치하는지 검증만 수행한다.

이 방식은 서버가 로그인 상태를 메모리에 따로 기억할 필요 없이, 들어온 토큰의 위조 여부만 수학적으로 검사하면 되는 무상태(Stateless) 방식이다. 따라서 서버 확장이 매우 자유롭고, 로드밸런싱이나 마이크로서비스 아키텍처(MSA)에 완벽하게 부합한다.

3. JWT의 구조와 주의할 점

JWT는 .을 기준으로 세 구획으로 나뉜다.

• Header (헤더): 서명에 사용된 암호화 알고리즘과 토큰의 타입 정보
• Payload (페이로드): 사용자 식별 정보(ID)와 토큰 만료 시간 등의 실제 데이터
• Signature (서명): 헤더와 페이로드를 서버의 비밀키로 해싱한 암호화 값

여기서 가장 주의할 점은 페이로드의 데이터는 누구나 Base64로 디코딩해서 볼 수 있다는 것이다. 서명이 있기 때문에 데이터가 중간에 '변조'되었는지는 알 수 있지만, 암호화되어 가려진 것은 아니다. 따라서 페이로드에는 비밀번호나 개인정보 같은 민감한 데이터를 절대 넣어서는 안 된다.

4. 토큰 만료의 딜레마와 투트랙(Two-Track) 전략

토큰의 페이로드에는 반드시 '만료 시간(Expiration)'이 포함된다. 만료 시간이 너무 길면 해커에게 토큰이 탈취되었을 때 피해가 걷잡을 수 없이 커진다. 반대로 너무 짧으면 사용자가 수시로 재로그인을 해야 하는 끔찍한 UX를 겪게 된다.

이를 해결하기 위해 실무에서는 두 가지 토큰을 함께 사용하는 투트랙 전략을 취한다.

• Access Token: 실질적인 API 인증에 사용된다. 탈취 피해를 최소화하기 위해 수명을 매우 짧게(약 15분~30분) 설정한다.
• Refresh Token: Access Token이 만료되었을 때, 사용자의 재로그인 없이 새로운 토큰을 발급받기 위한 보증수표 역할을 한다. 수명은 넉넉하게(약 2주) 잡는다.

5. 무상태(Stateless)의 대가와 하이브리드 전략

완벽해 보이는 JWT도 뼈아픈 대가를 치러야 한다. 만약 해커가 수명이 짧은 Access Token을 탈취했거나, 악성 유저를 즉각적으로 차단해야 하는 상황이 오더라도 서버는 토큰이 만료될 때까지 이를 중앙에서 제재할 방법이 없다. 서버가 상태를 기억하지 않기 때문이다.

그래서 실무에서는 Access Token은 Stateless하게 검증하되, 수명이 긴 Refresh Token은 서버의 DB나 인메모리 저장소에 기록하여 Stateful하게 관리하는 방식을 사용한다. 사용자가 로그아웃하거나 계정이 정지되면, 서버의 저장소에서 해당 Refresh Token을 지워버려 새로운 Access Token 발급을 원천 차단하는 원리다.

더 나아가, 핵심 API(결제, 비밀번호 변경 등)에서는 토큰 서명만 믿지 않고 하이브리드 방식으로 실시간 DB 조회를 거치기도 한다. 이때 발생하는 DB 병목 현상은 보통 인메모리 캐시인 Redis를 활용해 속도 문제를 극복한다.

6. 토큰 저장 위치의 딜레마 (XSS vs CSRF)

발급받은 이 두 토큰을 클라이언트 어디에 보관할 것인가는 보안의 핵심이다.

• Local Storage: 브라우저 저장소에 보관하면 관리가 편하지만, XSS(교차 사이트 스크립팅) 공격에 취약하다. 해커가 웹사이트에 악성 자바스크립트를 심으면 저장소의 토큰을 고스란히 털어갈 수 있다.
• HttpOnly Cookie: 자바스크립트로는 절대 접근할 수 없는 보안 쿠키다. XSS 방어에는 탁월하지만, 사용자의 브라우저를 속여 강제로 위조된 요청을 보내게 만드는 CSRF 공격에 노출될 수 있다. (단, 이는 쿠키의 SameSite 속성 등 설정으로 상당 부분 방어가 가능하다.)

💡 결론적으로 실무에서는: 수명이 짧은 Access Token은 클라이언트의 로컬 메모리(JS 전역 변수 등)에 저장하여 API 요청 시 헤더에 직접 심어(Authorization: Bearer) 보내고, 수명이 길고 중요한 Refresh Token은 HttpOnly, Secure 속성이 걸린 쿠키에 저장하여 해커의 접근을 원천 차단하는 방식을 표준으로 삼는다.

7. 보안의 끝판왕: Refresh Token Rotation (RTR)

Refresh Token을 쿠키에 안전하게 숨겼더라도, 네트워크 스니핑 등으로 탈취당할 가능성은 여전히 존재한다. 해커가 리프레시 토큰을 얻으면 엑세스 토큰을 무한정 재발급받을 수 있는 치명적인 문제가 생긴다.

이를 방어하기 위해 Token Rotation (RTR) 기법을 도입한다. 이 방식은 사용자가 Refresh Token을 사용해 새 Access Token을 발급받을 때, Refresh Token도 무조건 새것으로 교체(1회용으로 사용)하는 방식이다. 만약 해커가 이미 사용되어 폐기된 구형 Refresh Token을 들고 서버에 나타난다면, 서버는 즉시 이를 토큰 탈취 상황으로 간주하고 해당 유저의 모든 토큰 장부를 삭제시켜 완전히 강제 로그아웃 처리해 버린다.

"보안은 잘하는 것이 아니라, 보안 사고가 터질 수밖에 없는 구조 자체를 만들지 않는 것이다."

암호화가 아닌 단방향 해싱

처음 로그인 기능을 구현할 때 흔히 "비밀번호를 안전하게 암호화해야지"라고 생각하기 쉽다. 하지만 이는 정답이 아니다. 정답은 '단방향 해싱(Hashing)'이다. 암호화는 복호화(원본으로 되돌림)가 가능하다는 것을 전제로 한다. 만약 DB가 털리면서 암호화 키까지 유출된다면, 모든 유저의 비밀번호 원본이 고스란히 노출되는 치명적인 사고로 이어진다. 반면 해싱은 입력값을 넣으면 항상 같은 결과가 나오지만, 원래 값으로 되돌리는 것(복호화)은 불가능하다. 즉, 비밀번호는 '확인'만 가능해야 하며 시스템 관리자조차 다시는 원본을 꺼낼 수 없어야 한다.

💡 로그인 인증 흐름 로그인 시에는 이 단방향 원리를 이용한다.

1. 사용자가 회원가입(이메일 + 비밀번호)을 한다.
2. DB에는 비밀번호 원본이 아닌, 해싱된 '해시값'이 저장된다.
3. 사용자가 다음에 로그인할 때 입력한 비밀번호를 똑같이 해싱하여, DB에 저장된 해시값과 비교한다.
4. 두 해시값이 일치하면 인증을 통과시킨다.

아무 해시 함수나 쓰면 안 되는 이유

단방향이라고 해서 SHA-256 같은 일반적인 해시 함수를 로그인에 써서는 안 된다. 일반 해시 함수는 처리 속도가 너무 빠르다. 해커가 무차별 대입(Brute Force) 공격으로 비밀번호를 순식간에 알아낼 위험이 크고, 미리 계산해 둔 해시값 표(레인보우 테이블)를 이용해 역추적할 수도 있다.

따라서 안전한 패스워드 해시 알고리즘은 다음 3가지 조건을 반드시 갖춰야 한다.

1. 속도가 느려야 한다. 계산 속도를 의도적으로 늦춰야 한다. 1초에 수십억 개의 해시값을 대입할 수 있는 것과 1초에 1개밖에 대입하지 못하는 것은 하늘과 땅 차이다. 공격자의 시간 비용을 기하급수적으로 늘려 해커가 스스로 공격을 포기하게 만들어야 한다.
2. 메모리를 많이 써야 한다. 해시값을 하나 만드는 데 막대한 자원(메모리)을 소모하게 만들면, 한 번에 생성할 수 있는 해시값의 수가 급격히 줄어든다. 이는 병렬 처리를 통한 대규모 공격을 방어하는 핵심이다.
3. 솔트(Salt)가 포함되어야 한다. 비밀번호 원본에 임의의 텍스트(솔트)를 덧붙여 해싱하는 방식이다. 이렇게 하면 똑같은 비밀번호를 쓰는 유저라도 DB에는 전혀 다른 해시값이 저장되어, 레인보우 테이블 공격을 완벽히 무력화할 수 있다.

이 모든 조건을 만족하는 알고리즘으로 Argon2id, bcrypt, scrypt 등이 있다. 그중에서도 현재 백엔드 실무 표준이자 가장 강력히 권장되는 알고리즘은 Argon2id다. 이걸 사용하자.

로그인 로직 구현 시 놓치면 안 되는 보안 디테일 3가지

알고리즘 선택은 끝났다. 하지만 실제 로그인 로직을 짤 때 다음 3가지 디테일을 놓치면 시스템에 빈틈이 생긴다. 꼭 기억하자.

1. 타이밍 공격(Timing Attack) 방어

로그인을 시도할 때 DB에 해당 이메일이 없으면 바로 에러를 반환하고, 이메일이 존재하면 패스워드 검증을 하느라 시간이 조금 더 걸린다고 가정해 보자. 해커는 이 미세한 '응답 시간의 차이'를 측정해 특정 이메일이 시스템에 가입되어 있는지 알아낼 수 있다. 이를 막으려면 DB에 이메일이 존재하지 않더라도 임의의 더미(Dummy) 해시 검증 로직을 실행하도록 만들어야 한다. 성공하든 실패하든 응답 시간을 동일하게 맞춰서 해커의 눈을 속이는 것이다.

2. 계정 열거(Enumeration) 방어

에러 메시지를 친절하게 "존재하지 않는 계정입니다"와 "비밀번호가 틀렸습니다"로 나누어주면, 해커는 이를 이용해 유효한 이메일 목록만 싹 수집한 뒤 집중 공격을 퍼부을 수 있다. 시스템 내부 정보가 노출되지 않도록, 계정이 없든 비밀번호가 틀렸든 응답 메시지는 무조건 "이메일 또는 비밀번호가 올바르지 않습니다"로 뭉뚱그려 통일해야 한다.

3. 재해싱(Rehashing)

시간이 흘러 컴퓨팅 파워가 발전하면 보안 정책(해싱 반복 횟수, 메모리 사용량 등)을 더 강력하게 업그레이드해야 한다. 이때 기존 유저들의 구버전 해시값은 어떻게 할까? 유저가 이전 방식으로 해싱된 비밀번호로 정상 로그인을 성공했을 때, 백그라운드에서 새로운 보안 정책이 적용된 해시값으로 DB를 조용히 업데이트해 주면 된다. 이를 재해싱이라 부르며, 유저가 모르는 사이에 시스템 보안을 알아서 최신으로 유지하는 마이그레이션 기법이다.

지금까지는 파일 입출력(read, write)을 수행할 때 버퍼를 이용하는 방식을 사용해왔다. mmap은 파일을 프로세스의 가상 메모리 주소 공간에 직접 매핑하여, 마치 메모리를 다루듯이 파일을 다룰 수 있게 해주는 기능이다.

이제 파일 데이터를 페이지 단위로 관리하며 가상 메모리 시스템과 통합해야 한다.

2. mmap 구현 (do_mmap)

시스템 콜 mmap은 실제 로직을 수행하는 do_mmap을 호출하는 래퍼(Wrapper) 형태로 구성된다. 핵심은 매핑 요청이 유효한지 검증하는 과정이다.

유효성 검사 루틴

addr(매핑 시작 주소)에 대해 다음 조건들을 순차적으로 확인해야 한다. 실패 시 NULL을 반환한다.

1. 기본 주소 검사: addr이 NULL이거나 0이 아니어야 한다.
2. 페이지 정렬: 주소가 정확히 4KB 단위로 나누어 떨어져야 한다. (pg_ofs(addr) == 0)
3. 영역 중복 검사 (spt_find_page):
   • 이미 실행 중인 코드/데이터 영역과 겹치지 않아야 한다.
   • 스택 영역과 겹치지 않아야 한다.
   • 이전에 mmap으로 할당된 다른 영역과 겹치지 않아야 한다.
4. 영역 범위 검사 (is_user_vaddr): 매핑하려는 주소 공간이 커널 영역이 아닌 사용자 영역 내에 존재해야 한다.

페이지 할당

검증이 완료되면 vm_alloc_page_with_initializer()를 사용하여 페이지를 할당한다. 이때 페이지 타입은 VM_FILE이 된다.

3. munmap 구현 (do_munmap)

munmap은 addr부터 시작하여 연속된 VM_FILE 페이지들을 해제하는 과정이다.

연속된 페이지 처리 문제

단순히 addr만 주어졌을 때, 몇 개의 페이지를 해제해야 하는지 알 수 없는 문제가 있다. 이를 해결하기 위해 매핑된 첫 번째 페이지의 구조체에 할당된 총 페이지 개수 정보를 저장해 두어야 한다.

do_munmap 호출 시, 첫 페이지에서 페이지 개수를 확인하고 정확히 그 횟수만큼 루프를 돌며 해제 작업을 수행한다.

4. 데이터 동기화 (Dirty Bit & Write Back)

메모리에 매핑된 파일 데이터가 수정되었다면, 언젠가는 디스크의 실제 파일에도 반영해줘야 한다.

동기화 시점의 결정

Dirty Bit(수정 여부)를 확인하고 파일에 쓰는 작업을 어디서 수행해야 할까?

1. munmap 시점: 사용자가 명시적으로 해제를 요청할 때 수행된다.
2. file_backed_destroy 시점: 페이지가 파괴될 때 수행된다.

정답은 file_backed_destroy 내부에서 처리하는 것이다. 프로세스가 정상 종료(process_exit)되거나 강제 종료될 때도 SPT가 정리되면서 destroy 함수가 호출되기 때문이다. 이곳에서 처리해야 모든 상황(명시적 해제 및 프로세스 종료)을 커버할 수 있다.

5. 구조체 수정 및 데이터 흐름

파일에 변경 사항을 쓰기 위해서는 해당 페이지가 '어떤 파일'의 '어느 오프셋'에 연결되어 있는지 알아야 한다.

구조체 설계

struct page 내부의 union에 정의된 file_page 구조체에 aux 정보가 필요하다. 이 aux 필드에는 파일 객체(struct file *)와 읽은 바이트 수, 오프셋 등의 정보가 담겨야 한다.

정보 전달 흐름

페이지가 처음 생성될 때는 VM_UNINIT 상태이다. 이때 lazy_load_info 등을 통해 파일 정보를 가지고 있다. 페이지 폴트가 발생하여 file_backed_initialize가 호출될 때, uninit_page가 가지고 있던 aux 정보를 file_page의 aux로 이관해 주어야 한다.

6. 동기화 구현 요약

1. 구조체 확장: file_page 구조체에 파일 정보(aux)를 저장할 필드를 추가한다.
2. 초기화 로직: file_backed_initialize 함수에서 uninit 상태의 aux 데이터를 file_page로 복사/이동시킨다.
3. 파괴 로직: file_backed_destroy 함수 구현 시, pml4_is_dirty를 통해 수정 여부를 확인한다. 수정되었다면 file_write_at 등을 사용하여 디스크에 내용을 기록하고 페이지를 해제한다.

지금까지 구현한 프로젝트에서 USER_STACK은 단일 페이지로 고정되어 있었다. 이제 프로세스가 실행되면서 스택이 현재 크기를 초과할 경우, 필요에 따라 추가 페이지를 할당하여 스택을 확장해 주는 기능을 구현해야 한다.

핵심은 페이지 폴트가 발생했을 때, 이것이 유효한 스택 확장 요청인지 아니면 잘못된 메모리 접근인지를 구별하는 것이다.

식별 규칙 (Heuristic)

일반적으로 OS는 시그널 전달 등을 통해 스택 데이터를 수정할 수 있다. 하지만 우리가 다루는 x86-64 아키텍처의 경우, 스택 포인터를 조정하기 전에 접근 권한을 먼저 확인하는 특성이 있다.

이로 인해 PUSH 명령어 실행 시, 스택 포인터(rsp)가 갱신되기 전에 해당 주소에 접근을 시도하게 되고, 실제 rsp보다 8바이트 아래 위치에서 페이지 폴트가 발생할 수 있다. 따라서 유효한 스택 접근으로 판단하는 기준은 다음과 같다.

접근 주소(addr) >= rsp - 8

또한 과제 요구사항에 따라 스택의 최대 크기는 1MB로 제한한다.

2. 구현 전제: RSP 값의 추적

스택 확장의 유효성을 검사하려면 현재 시점의 사용자 스택 포인터(rsp) 값을 정확히 알고 있어야 한다. 페이지 폴트가 발생한 상황에 따라 rsp를 가져오는 방식이 다르다.

• User Mode에서 발생: intr_frame의 rsp 멤버를 통해 스택 포인터를 바로 확인할 수 있다.
• Kernel Mode에서 발생: 시스템 콜 처리 도중 페이지 폴트가 발생하여 커널 모드로 진입한 경우, intr_frame의 rsp는 커널 스택을 가리키게 된다. 따라서 유저의 rsp 값을 알 수 없게 된다.

해결 방안

유저 모드에서 커널 모드로 최초 전환되는 시점(예: syscall_handler)에 유저의 rsp 값을 별도로 저장해 두어야 한다.

1. struct thread 구조체에 uintptr_t user_rsp 필드를 추가한다.
2. 인터럽트 핸들러 도입부에서 f->rsp 값을 thread->user_rsp에 백업한다.
3. vm_try_handle_fault에서 현재 상태가 유저 모드라면 f->rsp를, 커널 모드라면 thread->user_rsp를 사용하여 검증 로직을 수행한다.

3. vm_try_handle_fault 로직 수정

기존의 페이지 폴트 핸들러를 수정하여 스택 확장이 필요한 케이스를 식별하고 처리해야 한다.

처리 흐름

1. 유효성 검사: 접근한 주소가 유저 영역(is_user_vaddr)인지 확인한다.
2. Present 비트 확인: not_present가 false라면, 이미 페이지가 존재하는데 권한 문제로 접근한 것이므로 즉시 false를 반환한다.
3. SPT 조회: spt_find_page를 통해 보조 페이지 테이블에 해당 주소가 있는지 확인한다.
   • SPT에 존재하는 경우: 기존 로직대로 Lazy Loading 등을 수행(vm_do_claim_page)한다.
   • SPT에 없는 경우: 이곳이 바로 Stack Growth를 검토해야 할 지점이다.

4. Stack Growth 상세 구현

SPT에 페이지가 없는 경우, 다음 세 가지 조건을 모두 만족할 때만 스택 확장을 수행한다.

확장 조건

1. 주소 범위: 접근한 주소(addr)가 유저 영역 내에 존재해야 한다.
2. RSP 근접성: addr이 현재 유저 스택 포인터(rsp)보다 크거나, 혹은 PUSH 명령어를 감안하여 rsp - 8 이상이어야 한다.
3. 크기 제한: 확장 후 전체 스택의 크기가 1MB를 초과하지 않아야 한다. (USER_STACK 시작점부터 addr까지의 거리 계산)

vm_stack_growth 함수

위 조건이 충족되면 vm_stack_growth를 호출하여 실제 확장을 진행한다.

1. Align: 접근한 주소를 페이지 단위로 내림(pg_round_down) 처리한다.
2. Allocation: vm_alloc_page(VM_ANON | VM_MARKER_0, ...)를 호출하여 새로운 익명 페이지를 할당한다. 이때 스택 영역임을 표시할 수 있다.
3. Claim: vm_claim_page를 호출하여 물리 프레임과 매핑하고, 필요하다면 memset 등으로 초기화한다.

이 과정을 통해 스택은 필요에 따라 1MB 한도 내에서 동적으로 늘어나게 된다.

• 핵심: 물리 메모리의 크기 한계를 극복하기 위해 디스크(Swap/File) 를 메모리의 연장선으로 사용한다.

• 원칙: Lazy Loading (게으른 로딩)

  • 당장 필요하지 않으면 메모리에 올리지 않고 장부(SPT)에만 적어둔다.
  • 실제로 필요해서 접근할 때(Page Fault) 비로소 메모리에 올린다.

2. SPT (Supplemental Page Table)

"프로세스의 모든 메모리 자원을 관리하는 절대 장부" 하드웨어 페이지 테이블(PML4)은 멍청해서 주소 변환밖에 모른다. 페이지 상태(스왑, 파일 등)를 관리할 별도의 장부가 필요하다.

• 자료구조: 검색 속도가 빠른 Hash Table 사용 권장.

• 위치: 프로세스(struct thread) 내부에 존재.

• 구성요소: struct page (가상 페이지 정보를 담은 객체)

  • struct hash_elem hash_elem: 해시 테이블에 넣기 위해 반드시 추가해야 함.
  • Union: 메모리 절약을 위해 UNINIT, ANON, FILE 중 하나의 상태만 가지도록 설계됨.

SPT 메서드 구현

① 초기화 (spt_init)

• hash_init을 호출하여 빈 테이블을 만든다.

• 핵심: page_hash(해싱 함수)와 page_less(비교 함수)를 인자로 넘겨줘야 한다.

  • Key: 모든 기준은 가상 주소(va) 다.

② 검색 (spt_find_page)

• 문제: hash_find는 hash_elem을 요구하는데, 우린 va밖에 없다.

• 해결 (Dummy Page):

  1. dummy_page를 만들고 va를 채운다. (pg_round_down 필수!)
  2. hash_find에 dummy_page.hash_elem을 미끼로 던진다.
  3. 해시 함수는 오직 va만 보므로, 진짜 페이지를 찾아준다. (같은 녀석으로 인식)

• 반환: 찾은 elem을 hash_entry로 복원해서 page 반환.

③ 삽입 (spt_insert_page)

• 핵심: 이미 hash_insert가 중복 검사를 해주므로 별도의 검증 로직 불필요.

• insert 성공 시 NULL 반환, 실패 시 기존 요소 반환함.

3. Frame Management (물리 메모리 관리)

"실제 땅(RAM)을 관리하고 연결하는 과정"

구조체 관계도 (3단 구조)

[ User Page (UVA) ] <---> [ Frame (KVA) ] <---> [ Physical Memory (PA) ]

• UVA: 사용자가 쓰는 가짜 주소. 권한이 없어서 물리 메모리에 직접 못 감.

• KVA: 커널이 쓰는 마스터키. 물리 메모리와 1:1 직통 연결됨.

• Page는 Frame을 가진다: page는 신청서, frame은 등기부. 둘을 연결해야 메모리 사용 가능.

Frame 메서드 구현

1. vm_get_frame (땅 확보):

   • palloc_get_page(PAL_USER): 유저 풀에서 4KB 땅(KVA)을 받아온다.

   • malloc: 커널 풀에서 struct frame 서류를 만든다.

   • 둘을 연결(frame->kva = kva)하고 반환.

2. vm_do_claim_page (연결):

   • vm_get_frame 호출.

   • page <-> frame 서로 포인터 연결.

   • pml4_set_page: 하드웨어(MMU)에 "이 가상 주소는 저 물리 주소다"라고 등록.

   • swap_in: 데이터 로딩 시작.

3. vm_claim_page (인터페이스):

   • va로 페이지 찾아서 vm_do_claim_page에 넘기는 결정자 역할.

4. Lazy Loading의 전체 시나리오 (핵심 흐름)

"쪽지(Aux)를 써두고, 나중에 펴보고 심부름시킨다."

Load (프로그램 시작)

데이터를 메모리에 올리지 않고 쪽지(aux)만 써둔다.

• 함수: load_segment -> vm_alloc_page_with_initializer

• 동작:

  1. 파일을 4KB씩 쪼갠다.

  2. 쪽지(aux) 작성: "나중에 이 파일의 이 위치 읽어라."

  3. 페이지 생성: VM_UNINIT 상태로 만들고, 쪽지와 작업반장(lazy_load_segment)을 넣어둠.

  4. SPT 등록: 메모리는 비어있지만 장부에는 가득 참.

Page Fault (실행 중)

사용자가 주소를 건드려서 에러가 난다.

• 함수: vm_try_handle_fault -> vm_do_claim_page -> swap_in

• 동작:

  1. swap_in이 호출되면 uninit_initialize가 실행된다.

  2. 신분 세탁: anon_initializer 등을 호출해 VM_ANON 등으로 변신.

  3. 데이터 로딩: 아까 넣어둔 작업반장(lazy_load_segment) 호출.

Lazy Load (진짜 로딩)

• 함수: lazy_load_segment

• 동작:

  1. 쪽지(aux)를 펼쳐본다.

  2. file_read로 진짜 데이터를 읽어서 kva에 넣는다.

  3. 남은 공간은 memset(0)으로 청소한다 (보안!).

5. Stack & Memory Mapping Details

Stack (스택) 초기화 (setup_stack)

• 특징: 파일 족보가 없다. 그냥 빈 메모리(VM_ANON)다.

• Eager Loading: 첫 페이지는 인자 전달(argc, argv)을 위해 당장 써야 하므로 바로 할당(claim)한다.

• 구현:

  1. vm_alloc_page(VM_ANON | VM_MARKER_0, ...) (예약)

  2. vm_claim_page(...) (즉시 할당)

  3. rsp 설정 (USER_STACK)

6. Process Lifecycle (Copy & Kill)

Fork (spt_copy)

부모의 SPT를 hash_iterator로 돌면서 복사한다. 얕은 복사는 절대 금지!

• VM_UNINIT: 아직 로딩 안 됨 -> 계획(Initializer, Aux)만 복사.

• VM_ANON: 이미 로딩 됨 -> 물리 메모리 할당(claim) + 내용 복사(memcpy).

  • struct page를 복사하는 게 아니라, 내용물(4KB)을 복사해야 함!

Exit (spt_kill)

• hash_clear로 장부를 비우면서 destroy 호출 -> 자원 해제.

1. _start ()
   • 컴퓨터 전원이 켜지면 가장 먼저 실행되는 코드입니다.
   • CPU를 64비트 모드로 설정하고 기본적인 메모리 관리(페이징)를 준비합니다.
   • 모든 준비가 끝나면 C언어 세상의 시작점인 main() 함수를 호출합니다.

Phase 2: 커널 초기화 및 멀티태스킹 활성화 (C)

2. main()
   • thread_init(): 현재 실행 중인 코드(main)를 첫 번째 커널 스레드로 등록합니다.
   • (기타 초기화): 파일 시스템, 타이머 등 다른 모든 커널 모듈을 초기화합니다.
   • thread_start(): 인터럽트와 스케줄러를 활성화합니다. 이 순간부터 핀토스는 여러 스레드를 전환하며 실행할 수 있는 멀티태스킹 운영체제가 됩니다.
   • run_actions(): 부팅 인자를 분석하여 무엇을 실행할지 결정합니다.

Phase 3: 첫 사용자 프로그램 실행

3. run_actions() → run_task()

   • 사용자가 run my_program과 같은 명령을 내리면 run_task("my_program") 함수가 호출됩니다.

4. *run_task() → process_create_initd() *

   • run_task는 첫 사용자 프로세스를 만들기 위해 process_create_initd("my_program")를 호출합니다.

5. process_create_initd() → thread_create()

   • process_create_initd는 thread_create를 호출하여 새로운 커널 스레드를 생성합니다.
   • 핵심: 이때 thread_create에 initd 함수의 주소를 넘겨주며, "이 스레드가 실행될 차례가 오면 initd 함수부터 시작해라" 라고 알려줍니다.

6. *(스케줄러에 의해) → initd() 실행 *

   • thread_create로 만들어진 새 스레드의 실행 순서가 되면, 스케줄러는 CPU의 제어권을 이 스레드에 넘깁니다.
   • 스레드는 약속된 대로 initd 함수부터 실행을 시작합니다.
   • initd 함수는 최종적으로 process_exec("my_program")을 호출하여, 디스크에서 프로그램을 읽어 메모리에 올리고 실행하는 모든 과정을 담당합니다.

1. 목표

• process_exec()이 실행되는 로직
• process_exec()가 넘겨 받는 문자열 인자들을 parshing
• 사용자 프로그램의 스택에 인자를 설정
• 사용자 프로그램이 실행되기 직전에 argc, argv 인자를 레지스터에 설정

구현된 기존 로직 살펴보기

process_exec()

현재 프로그램에 덮어씌우는 방식

• fork()+exec() -> 쉘
• fork() -> 크롬 탭, 웹 서버 요청

int process_exec (void *f_name) { // 현재: 프로그램 명만 받도록 구현되어 있다.

    char *file_name = f_name;
    bool success;

    /* We cannot use the intr_frame in the thread structure.
    * This is because when current thread rescheduled,
    * it stores the execution information to the member. */

    // 새로운 사용자 프로세스의 초기 상태를 설정하기 위한 레지스트 상태를 저장하는 구조체
    struct intr_frame _if;
    _if.ds = _if.es = _if.ss = SEL_UDSEG; // 사용자 권한으로 설정
    _if.cs = SEL_UCSEG; // 사용자 권한으로 설정
    _if.eflags = FLAG_IF | FLAG_MBS; // 인터럽트 플래그 On | 필수

    /* We first kill the current context */
    process_cleanup (); //현재 실행 중인 프로세스를 종료하고 자원 정리

    /* And then load the binary */
    success = load (file_name, &_if);

    /* If load failed, quit. */
    palloc_free_page (file_name);
    if (!success)
        return -1;

    /* Start switched process. */
    do_iret (&_if);
    NOT_REACHED ();
}

load()

나중에 구현할 때 file_name -> cmd_line으로 변경 후 파싱 진행

static bool load (const char *file_name, struct intr_frame *if_) {
    struct thread *t = thread_current ();
    struct ELF ehdr;
    struct file *file = NULL;
    off_t file_ofs;
    bool success = false;
    int i;

    // 새로운 빈 페이지 테이블 생성
    t->pml4 = pml4_create ();
    if (t->pml4 == NULL)
        goto done;
    process_activate (thread_current ());  

    // 실행 파일 열기
    file = filesys_open (file_name); // 여기 파싱한 이름으로 변경해야한다.
    if (file == NULL) {
        printf ("load: %s: open failed\n", file_name);
        goto done;
    }

    // ELF 헤더 검증
    if (file_read (file, &ehdr, sizeof ehdr) != sizeof ehdr
            || memcmp (ehdr.e_ident, "\177ELF\2\1\1", 7) // ELF 매직넘버 검사
            || ehdr.e_type != 2 // Executable Check
            || ehdr.e_machine != 0x3E // amd64 -> x86-64
            || ehdr.e_version != 1 // ELF version check
            // ELF Program Header Entry size, Program Hdr
            || ehdr.e_phentsize != sizeof (struct Phdr) 
            || ehdr.e_phnum > 1024) { // head count check
        printf ("load: %s: error loading executable\n", file_name);
        goto done;
    }

    // 프로그램 헤더(세그먼트 정보) 읽기
    file_ofs = ehdr.e_phoff; // 프로그램 헤더 테이블 위치
    for (i = 0; i < ehdr.e_phnum; i++) {
        struct Phdr phdr; // 프로그램 헤더 하나를 담을 변수

        if (file_ofs < 0 || file_ofs > file_length (file))
            goto done;

        file_seek (file, file_ofs); // file의 위치를 file_ofs 위치로 이동

        if (file_read (file, &phdr, sizeof phdr) != sizeof phdr)
            goto done;

        file_ofs += sizeof phdr; // 다음 헤더 시작 위치를 가리키도록 변경

        // 세그먼트 타입 확인: 각 세크먼트 타입은 프로그램 헤더 항목에 있다. 1:1 mapping
        // 세그먼트 타입을 확인하고, 어떻게 처리할지 결정하는 필터 역할    
        switch (phdr.p_type) {
            case PT_NULL: // 비어있거나 사용X
            case PT_NOTE: // 주석이나 정보
            case PT_PHDR: // 이미 읽었으므로 로드X
            case PT_STACK: // setup_stack() 함수로 직접 스택을 만들어야함.
            default:
                /* Ignore this segment. */
                break;

            case PT_DYNAMIC: // 다음 3가지는 동적 링킹과 관련된 세그먼트.
            case PT_INTERP:  // pinto는 동적 링킹 지원X
            case PT_SHLIB:
                goto done;

            case PT_LOAD: // 실제로 메모리에 로드해야 한다.
                if (validate_segment (&phdr, file)) { // 세그먼트 유효한지 검사
                    bool writable = (phdr.p_flags & PF_W) != 0;
                    // 페이지 크기를 4kb로 내림
                    uint64_t file_page = phdr.p_offset & ~PGMASK;
                    // 가상 메모리 주소
                    uint64_t mem_page = phdr.p_vaddr & ~PGMASK;
                    // 가상 주소가 페이지의 시작에서부터 얼마나 떨어져 있는지 계산(offset)
                    uint64_t page_offset = phdr.p_vaddr & PGMASK;

                    // .bss 세그먼트를 처리하기 위해 존재한다.
                    uint32_t read_bytes, zero_bytes;
                    if (phdr.p_filesz > 0) { // .bss + .data
                        /* Normal segment.
                        * Read initial part from disk and zero the rest. */
                        read_bytes = page_offset + phdr.p_filesz;
                        // 0으로 채워할 바이트 수. 4kb로 올림. .bss 처리
                        zero_bytes = (ROUND_UP (page_offset + phdr.p_memsz, 
                        PGSIZE) - read_bytes); 
                    } else { .bss
                        /* Entirely zero.
                        * Don't read anything from disk. */
                        read_bytes = 0;
                        zero_bytes = ROUND_UP (page_offset + phdr.p_memsz, 
                        PGSIZE);
                    }

                    // 실제 로딩(배치) 수행
                    // 실제 메모리 공간 할당 + 가상 메모리 맵핑
                    if (!load_segment (file, file_page, (void *) mem_page,
                                read_bytes, zero_bytes, writable))
                        goto done;
                } else
                    goto done;
                break;
        }
    }

    /* Set up stack. */
    // 스택 공간 할당 + 스택 포인터 설정
    if (!setup_stack (if_))
        goto done;

    /* Start address. */
    if_->rip = ehdr.e_entry;

    success = true;

done:
    /* We arrive here whether the load is successful or not. */
    file_close (file);
    return success;
}

2. 핵심 아이디어

사용자로부터 입력받은 command_line (예: "ls -l foo")을 쪼개서 커널이 이해할 수 있는 데이터 형태로 가공하는 단계입니다.

1. 문자열 복사

가장 먼저 고려해야 할 점은 "왜 원본 문자열을 그대로 쓰면 안 되는가?" 입니다. 여기에는 방어적 프로그래밍과 메모리 보호라는 두 가지 중요한 이유가 있습니다.

• 이유 1: strtok_r의 동작 방식
  • strtok_r 함수는 구분자(공백 등)를 찾으면 해당 위치의 문자를 \0 (NULL)으로 덮어씌워 문자열을 잘라냅니다. 즉, 원본 데이터를 직접 수정하는 파괴적인 함수입니다.
• 이유 2: 원본 데이터의 메모리 위치
  • process_exec에 넘어온 f_name 포인터가 가리키는 곳이 수정 불가능한 영역(Read-Only Data Segment, 리터럴 문자열)일 수 있습니다. 이곳을 수정하려 시도하면 Page Fault가 발생하여 커널 전체가 멈출(Panic) 위험이 있습니다.

결론: palloc_get_page(0) 등을 사용해 커널 메모리에 새로운 페이지를 할당받고, strlcpy로 문자열을 안전하게 복사한 뒤 작업을 수행해야 합니다.

2. 변수 및 배열 설계

파싱한 데이터를 담아둘 자료구조를 설계합니다. C언어의 표준 main 함수 인자를 생각하면 이해가 쉽습니다.

• argc (Argument Count)
  • 인자의 개수를 세는 정수 변수입니다.
• argv (Argument Vector)
  • 인자들의 문자열 주소(포인터)를 저장할 배열입니다.
  • 크기: 핀토스 과제 기준으로는 보통 인자 개수에 제한을 둡니다. 넉넉하게 char *argv[64] (혹은 128) 정도로 선언하면 충분합니다.
  • argv[0]에는 항상 프로그램의 이름(예: ls)이 들어갑니다.

3. 문자열 분리 및 스택 삽입

복사한 커맨드 라인을 파싱 한 후, x86-64 Calling Convention에 맞춰 스택을 빈틈없이 채워야 합니다. 스택은 높은 주소에서 낮은 주소로(High Address → Low Address) 자란다는 점을 항상 기억해야 합니다.

전체 과정은 크게 4단계로 나뉩니다.

1. 인자 데이터(String Data) 삽입

• 가장 먼저 파싱 된 문자열 데이터 자체를 스택에 넣습니다.
• strtok_r로 분리된 토큰(문자열)을 하나씩 스택에 복사합니다 (memcpy).
• 이때, 나중에 포인터 배열(argv)을 만들 때 사용하기 위해, 문자열이 저장된 스택 주소(rsp)를 별도 배열(argv_list)에 기록해 두어야 합니다.

2. Word Align (8바이트 정렬)

• 성능 최적화와 규약을 위해 스택 포인터를 8의 배수로 맞춰야 합니다.
• 문자열 데이터를 다 넣은 직후의 rsp가 8로 나누어떨어지지 않는다면, 8의 배수가 될 때까지 스택 포인터를 내리고 남는 공간을 0 (NULL)으로 채웁니다.

3. 인자 주소 배열(String Pointers) 삽입

• 이제 앞서 기록해 둔 문자열의 주소들을 스택에 넣을 차례입니다. 주의할 점은 역순 삽입입니다.
• Sentinel (argv[argc]): C 표준에 따라 인자 배열의 끝은 NULL이어야 합니다. 가장 먼저 0을 넣습니다.
• Pointers (argv[argc-1] ... argv[0]): 기록해 둔 주소들을 거꾸로 스택에 넣습니다. 그래야 스택의 위쪽(낮은 주소)에서 볼 때 argv[0], argv[1] 순서대로 정렬됩니다.

4. 가짜 반환 주소 (Fake Return Address) & 레지스터 설정

• Fake Return Address: main 함수도 누군가에게 호출된 것처럼 보이게 하기 위해, 반환 주소 공간(void pointer 크기)을 확보하고 0으로 채웁니다.
• 레지스터 설정: 이제 사용자 프로그램이 시작될 때 인자를 알 수 있도록 CPU 레지스터를 세팅합니다.
• RDI: 인자의 개수 (argc)
• RSI: 인자 배열의 시작 주소 (argv 즉, argv[0]을 가리키는 스택 주소)

3. 구현

위 다이어그램의 구조(x86-64 Calling Convention)를 코드로 구현합니다. 이 작업은 load() 내부에서 수행됩니다.

• Parsing & Data Push: 문자열을 파싱하여 스택에 문자열 데이터를 밀어 넣습니다.
• Alignment: 8바이트 단위로 스택 포인터를 정렬합니다.
• Pointer Push: 문자열들의 주소(argv)를 스택에 넣습니다.
• Register: 프로그램 시작 시 인자를 받을 수 있도록 레지스터를 세팅합니다.

수정된 load() :

static bool load (const char *cmd_line, struct intr_frame *if_) {
    struct thread *t = thread_current ();
    struct ELF ehdr;
    struct file *file = NULL;
    off_t file_ofs;
    bool success = false;
    int i;

    char *file_name;
    char *copy_cmd_line;
    char *token;
    int count = 0;
    char *save_ptr;
    char *address[64];

    copy_cmd_line = palloc_get_page (0);
    if (copy_cmd_line == NULL)
        goto done; 
    strlcpy (copy_cmd_line, cmd_line, PGSIZE);

    token = strtok_r(copy_cmd_line, " ", &save_ptr); 
    file_name = token;

    if (file_name == NULL) {
        goto done;
    }

    /* Allocate and activate page directory. */
    t->pml4 = pml4_create ();
    if (t->pml4 == NULL)
        goto done;
    process_activate (thread_current ());

    /* Open executable file. */
    file = filesys_open (file_name);
    if (file == NULL) {
        printf ("load: %s: open failed\n", file_name);
        goto done;
    }

    // rox
    file_deny_write(file);

    /* Read and verify executable header. */
    if (file_read (file, &ehdr, sizeof ehdr) != sizeof ehdr
            || memcmp (ehdr.e_ident, "\177ELF\2\1\1", 7)
            || ehdr.e_type != 2
            || ehdr.e_machine != 0x3E // amd64
            || ehdr.e_version != 1
            || ehdr.e_phentsize != sizeof (struct Phdr)
            || ehdr.e_phnum > 1024) {
        printf ("load: %s: error loading executable\n", file_name);
        goto done;
    }

    /* Read program headers. */
    file_ofs = ehdr.e_phoff;
    for (i = 0; i < ehdr.e_phnum; i++) {
        struct Phdr phdr;

        if (file_ofs < 0 || file_ofs > file_length (file))
            goto done;
        file_seek (file, file_ofs);

        if (file_read (file, &phdr, sizeof phdr) != sizeof phdr)
            goto done;
        file_ofs += sizeof phdr;
        switch (phdr.p_type) {
            case PT_NULL:
            case PT_NOTE:
            case PT_PHDR:
            case PT_STACK:
            default:
                /* Ignore this segment. */
                break;
            case PT_DYNAMIC:
            case PT_INTERP:
            case PT_SHLIB:
                goto done;
            case PT_LOAD:
                if (validate_segment (&phdr, file)) {
                    bool writable = (phdr.p_flags & PF_W) != 0;
                    uint64_t file_page = phdr.p_offset & ~PGMASK;
                    uint64_t mem_page = phdr.p_vaddr & ~PGMASK;
                    uint64_t page_offset = phdr.p_vaddr & PGMASK;
                    uint32_t read_bytes, zero_bytes;
                    if (phdr.p_filesz > 0) {
                        /* Normal segment.
                         * Read initial part from disk and zero the rest. */
                        read_bytes = page_offset + phdr.p_filesz;
                        zero_bytes = (ROUND_UP (page_offset + phdr.p_memsz, PGSIZE)
                                - read_bytes);
                    } else {
                        /* Entirely zero.
                         * Don't read anything from disk. */
                        read_bytes = 0;
                        zero_bytes = ROUND_UP (page_offset + phdr.p_memsz, PGSIZE);
                    }
                    if (!load_segment (file, file_page, (void *) mem_page,
                                read_bytes, zero_bytes, writable))
                        goto done;
                }
                else
                    goto done;
                break;
        }
    }

    /* Set up stack. */
    if (!setup_stack (if_))
        goto done;

    /* Start address. */
    if_->rip = ehdr.e_entry;

    while (token != NULL && count < 64) {
        if_->rsp -= (strlen(token) + 1);
        memcpy(if_->rsp, token, strlen(token) + 1); 

        address[count++] = if_->rsp;
        token = strtok_r(NULL, " ", &save_ptr);
    }

    // 배열의 마지막 NULL 넣기.
    address[count] = NULL;

    //8바이트 정렬하기
    if_->rsp = if_->rsp & ~0x7;

    // 스택에 배열 넣기 
    for (int i = count; i >= 0; i--) {
        if_->rsp -= sizeof(address[i]);
        *((char **)(if_->rsp)) = address[i];
    }

    // 레지스터 설정하기
    if_->R.rdi = count;
    if_->R.rsi = if_->rsp;

    if_->rsp -= sizeof(char *);
    *((char **)(if_->rsp)) = 0;

    success = true;

done:
    if (copy_cmd_line != NULL) {
        palloc_free_page(copy_cmd_line);
    }

    /* We arrive here whether the load is successful or not. */
    if (success) {
        t->hold_file = file;
    } else {
        file_close (file); // 무조건 닫으면 안된다. file의 쓰기 금지 락을 유지해야하기 때문이다.
    }

    return success;
}

스케줄러 설계 시 두 가지 상충되는 목표가 있습니다.

1. 반환 시간 (Turnaround Time) 최적화: 짧은 작업을 먼저 실행 (SJF 방식)
2. 응답 시간 (Response Time) 최적화: 대화형 사용자에게 빠른 응답 (RR 방식)

SJF는 작업의 총 실행 시간을 미리 알아야 하는 문제가 있고, RR은 반환 시간에 불리합니다.

MLFQ의 핵심 질문은 이것입니다: "작업의 실행 시간에 대한 사전 정보 없이, 대화형 작업의 응답 시간을 최소화하고 동시에 반환 시간을 최소화하는 스케줄러를 어떻게 설계할 수 있을까?"

2. MLFQ의 기본 동작 규칙

MLFQ는 여러 개의 큐로 구성되며, 각 큐는 서로 다른 우선순위를 갖습니다. 스케줄러는 작업의 특성에 따라 우선순위를 동적으로 조정합니다.

• 규칙 1: Priority(A) > Priority(B) 이면, A가 실행됩니다. (B는 실행되지 않음)
• 규칙 2: Priority(A) = Priority(B) 이면, A와 B는 라운드 로빈(RR) 방식으로 실행됩니다.

작업의 우선순위를 결정하는 규칙은 다음과 같습니다.

• 규칙 3: 작업이 시스템에 진입하면, 가장 높은 우선순위 큐에 배치됩니다.
• 규칙 4: 작업이 주어진 타임 슬라이스를 모두 사용하면, 우선순위가 낮아집니다. (즉, 한 단계 아래 큐로 이동)
• 규칙 5: 작업이 타임 슬라이스를 소진하기 전에 CPU를 양도하면 (예: I/O 작업), 같은 우선순위를 유지합니다.

이 규칙들은 다음과 같은 효과를 가집니다.

• SJF 근사: CPU를 오래 사용하는 작업(CPU-bound)은 타임 슬라이스를 계속 소진하여 낮은 우선순위 큐로 빠르게 강등됩니다. (규칙 4)
• 응답 시간 최적화: 입출력 위주의 대화형 작업(I/O-bound)은 CPU를 양도하므로 높은 우선순위를 유지하며 빠른 응답을 받습니다. (규칙 5)

3. 기본 규칙의 문제점

하지만 위의 기본 규칙만으로는 심각한 결점 세 가지가 발생합니다.

1. 기아 상태 (Starvation)

   • 항상 더 높은 우선순위의 작업들만 시스템에 계속 도착한다면, 낮은 우선순위 큐에 있는 작업들은 CPU 시간을 전혀 할당받지 못할 수 있습니다.

2. 얌체 프로세스 (Gaming the Scheduler)

   • 악의적인 프로세스가 타임 슬라이스가 끝나기 직전, 고의로 I/O 작업을 요청하여 CPU를 양도할 수 있습니다.
   • 이 경우, 규칙 5에 따라 높은 우선순위를 계속 유지하며 CPU를 불공평하게 독점하게 됩니다.

3. 특성 변화 대응 불가

   • 처음에는 CPU 위주 작업이라 낮은 큐로 강등되었으나, 나중에 대화형 작업으로 성격이 바뀐다 해도 시스템은 과거 기록만 보고 해당 작업을 계속 낮은 우선순위로 취급합니다.

4. 문제 해결 방안

이러한 문제들을 해결하기 위해 MLFQ에 두 가지 핵심 규칙이 추가됩니다.

해결책 1: 우선순위 상향 조정 (Priority Boost)

규칙 6 (수정): 일정 기간 S가 지나면, 시스템의 모든 작업을 최상위 큐로 이동시킨다.

이 '우선순위 상향 조정'은 두 가지 문제를 한 번에 해결합니다.

• 기아 상태 해결: 아무리 낮은 우선순위에 있던 작업이라도, 주기적으로 최상위 큐로 올라가 실행될 기회를 얻습니다.
• 특성 변화 대응: CPU 위주 작업에서 대화형 작업으로 성격이 바뀐 프로세스도, 최상위 큐로 이동하여 스케줄러가 자신의 변경된 특성을 파악할 기회를 갖게 됩니다.

해결책 2: 얌체 프로세스 방지 (Accounting)

규칙 4와 5를 'CPU 양도 횟수'가 아닌 'CPU 총 사용 시간'을 기준으로 변경하여 얌체 프로세스를 방지합니다.

규칙 4/5 (수정): 주어진 단계(큐)에서 작업의 CPU 총 사용 시간을 측정한다. 작업이 해당 큐의 시간 할당량(Time Allotment)을 모두 소진하면 (CPU를 한 번에 썼든, 여러 번 나눠 썼든 상관없이), 우선순위는 낮아진다. (아래 큐로 이동)

이렇게 하면 얌체 프로세스가 I/O를 아무리 짧게 자주 발생시켜도, 결국 해당 큐의 총 CPU 사용 시간을 채우게 되면 아래 큐로 강등됩니다.

기부(Donation)가 필요한 순간: 우선순위 역전 (Priority Inversion)

다음과 같이 우선순위가 다른 세 스레드가 있다고 가정합니다.

• H 스레드(50)
• M 스레드(30)
• L 스레드(10)

문제 상황 (우선순위 역전):

1. L 스레드가 특정 lock을 획득하여 실행 중입니다.
2. H 스레드가 실행되다가, L이 가진 lock이 필요해 lock_acquire()를 호출하고 대기(BLOCKED) 상태가 됩니다.
3. 이제 L이 마저 실행되어 lock을 풀어줘야 하는데, M 스레드가 CPU를 선점합니다. (M(30) > L(10))
4. 결과: 가장 우선순위가 높은 H(50)는 L(10)이 끝나길 기다리는데, L은 M(30) 때문에 실행되지 못합니다.

   즉, H 스레드가 자신보다 훨씬 우선순위가 낮은 M 스레드 때문에 실행을 못 하는 '우선순위 역전'이 발생합니다.

해결책 (우선순위 기부):

1. H 스레드가 L이 가진 lock을 기다릴 때, 자신의 높은 우선순위(50)를 L에게 기부(Donation)합니다.
2. L 스레드의 우선순위는 일시적으로 max(10, 50) = 50이 됩니다.
3. L(50)은 M(30)보다 우선순위가 높아졌으므로, CPU를 선점하여 lock을 해제하는 작업을 빠르게 완료할 수 있습니다.
4. L이 lock을 해제(lock_release)하면, 기부받았던 우선순위를 반납하고 원래 우선순위(10)로 돌아갑니다.
5. H 스레드는 lock을 획득하고 정상적으로 실행됩니다.

1. 목표

우선순위 역전(Priority Inversion)이 일어나지 않도록 우선순위 기부(Priority Donation)를 구현하자.

2. 핵심 아이디어

• 우선순위 기부를 위해서 필요한 필드를 thread 구조체에 선언한다.
• 우선순위 역전이 일어나는 lock_acquire 시점에 기부 로직을 구현한다.
• 기부가 연쇄적으로(Nested) 발생하는 문제를 해결한다.
• 락을 반납하는 lock_release 시점에 기부를 철회하고 우선순위를 복원한다.
• thread_set_priority 함수가 기부 상황에서도 올바르게 동작하도록 수정한다.

3. 구현 과정

1. thread 구조체 필드 추가

thread.h의 struct thread에 기부에 필요한 필드들을 추가합니다.

• original_priority: 기부받기 전의 고유 우선순위를 저장합니다.
• waiting_on: 락 획득을 대기할 때, 해당 락을 가리키는 포인터입니다. (연쇄 기부 용)
• donations: 나에게 우선순위를 기부한 스레드들의 리스트입니다.
• donation_elem: 나를 다른 스레드의 donations 리스트에 넣을 때 사용할 리스트 요소입니다.

// thread.h
struct thread
{
    ...

    // 기부 전용 명찰
    struct list_elem donation_elem;

    // 기부자들
    struct list donations;

    // 원래 우선순위
    int original_priority;

    // 어떤 락을 기다리고있는지 처음에는 NULL
    struct lock *waiting_on;

    ...

};

(이후 thread.c의 init_thread에서 original_priority = priority, waiting_on = NULL, list_init(&t->donations)로 초기화합니다.)

2. lock_acquire 수정 (기부 및 연쇄 전파)

synch.c의 lock_acquire 함수를 수정합니다. 락 소유자(holder)가 이미 존재하여 락 획득에 실패하는 경우( if (lock->holder != NULL) ), sema_down으로 잠들기 전에 기부 로직을 수행합니다.

donations 리스트를 정렬하기 위한 헬퍼 함수 donate_priority_less와, 연쇄 기부를 처리할 헬퍼 함수 update_holder_priority를 먼저 정의합니다.

lock_acquire 본체 수정 (in synch.c):

void 
lock_acquire (struct lock *lock) {
    ASSERT (lock != NULL);
    ASSERT (!intr_context ());
    ASSERT (!lock_held_by_current_thread (lock));

    struct thread *cur = thread_current();

    if (lock->holder != NULL) { // 락 소유자가 있어 대기 및 기부 발생

        // 1. 내가 이 락을 기다린다고 기록 (연쇄 기부용)
        cur->waiting_on = lock;

        // 2. 락 소유자의 기부 리스트에 나를 추가
        list_insert_ordered(&lock->holder->donations, &cur->donation_elem, donate_priority_less, NULL); 

        // 3. 락 소유자의 우선순위를 (필요시 연쇄적으로) 갱신
        update_holder_priority(lock->holder);

        // 4. 락이 풀릴 때까지 잠들기
        sema_down (&lock->semaphore);

    } else {
        // 락 소유자가 없으므로 바로 획득
        sema_down (&lock->semaphore); 
    }

    // 락을 획득했으므로 (깨어났거나, 바로 획득했거나)
    cur->waiting_on = NULL; // 더 이상 기다리는 락 없음
    lock->holder = cur;     // 내가 이 락의 소유자임
}

연쇄 갱신 헬퍼 함수 (in synch.c):

/* * 락 소유자(holder)의 우선순위를 재계산하고,
 * 만약 우선순위가 갱신되었다면 이 갱신을 연쇄적으로 전파(propagate)합니다.
 */
void update_holder_priority(struct thread *holder) {

    int current_priority = holder->priority; // 갱신 전 우선순위

    // 1. 기본값은 자신의 원래 우선순위
    int new_priority = holder->original_priority; 

    // 2. donations 리스트에서 가장 높은 우선순위와 비교
    if (!list_empty(&holder->donations)) {
        struct thread *max_donor = list_entry(list_front(&holder->donations), struct thread, donation_elem);

        if (new_priority < max_donor->priority) {
            new_priority = max_donor->priority;
        }
    }

    holder->priority = new_priority; // 3. 최종 우선순위로 갱신

    // 4. [연쇄 전파]
    // 만약 우선순위가 갱신되었고, 이 스레드(holder) 또한 다른 락을 기다리고 있다면
    if (current_priority != holder->priority) {
        if (holder->waiting_on != NULL && holder->waiting_on->holder != NULL) {
            // 그 락의 소유자(holder->waiting_on->holder)도 재귀적으로 갱신
            update_holder_priority(holder->waiting_on->holder);
        }
    }
}

비교 헬퍼 함수 (in synch.c):

/* donations 리스트를 우선순위 내림차순으로 정렬하기 위한 비교 함수 */
int donate_priority_less(const struct list_elem *a,
                       const struct list_elem *b, void *aux UNUSED)
{
    struct thread *thread_a = list_entry(a, struct thread, donation_elem);
    struct thread *thread_b = list_entry(b, struct thread, donation_elem);

      return thread_a->priority > thread_b ->priority;
}

3. lock_release 수정 (기부 철회)

락을 해제할 때, 락 소유자(현재 스레드)의 donations 리스트를 정리하고 우선순위를 원래대로(혹은 남은 기부 중 최고값으로) 복원합니다.

// synch.c
void
lock_release (struct lock *lock) {
    ASSERT (lock != NULL);
    ASSERT (lock_held_by_current_thread (lock));

    struct thread *current = thread_current();

    // 1. 'donations' 리스트에서 "이 락(lock)"을 기다리던 기부자들을 제거
    struct list_elem *e = list_begin(&current->donations);
    while (e != list_end(&current->donations)) {
        struct thread *t= list_entry(e, struct thread, donation_elem);

        if (t->waiting_on == lock) {
            e = list_remove(e); // 이 락을 기다렸던 기부자 제거
        } else {
            e = list_next(e);
        }
    }

    // 2. 기부자 정리 후 우선순위 재계산
    if (list_empty(&current->donations)) {
        // 남은 기부자가 없으면, 원래 우선순위로 복원
        current->priority = current->original_priority;

    } else {
        // 남은 기부자(다른 락 대기자)가 있다면
        struct thread *max_donor = list_entry(list_front(&current->donations), struct thread, donation_elem);

        // original_priority와 남은 기부자 중 최고값으로 갱신
        if (max_donor->priority > current->original_priority) {
              current->priority = max_donor->priority;
         } else {
              current->priority = current->original_priority;
          }
    }

    lock->holder = NULL; // 3. 락 소유자 반납
    sema_up (&lock->semaphore); // 4. 대기 중인 다음 스레드(최고 우선순위)를 깨움
}

4. thread_set_priority 수정 (기부와 선점 연동)

스레드가 스스로 우선순위를 변경할 때, priority가 아닌 original_priority를 변경하도록 수정합니다. 그 후, 기부 리스트를 포함하여 실제 priority를 갱신하고, 필요시 선점을 수행합니다.

// thread.c
void 
thread_set_priority(int new_priority)
{
    struct thread *cur = thread_current();

    // 1. 스레드의 '원래' 우선순위를 갱신
     cur->original_priority = new_priority;

    // 2. '원래' 우선순위와 '기부받은' 우선순위 중 최고값으로 현재 우선순위(priority)를 갱신
    int max_priority = new_priority;

    if (!list_empty(&cur->donations)) {
        struct thread *front_thread = list_entry(list_begin(&cur->donations), struct thread, donation_elem);
        if (front_thread->priority > max_priority) {
            max_priority = front_thread->priority;
        }
    }

    cur->priority = max_priority;

     // 3. [선점 로직]
     // 만약 우선순위가 낮아졌다면, ready_list의 1등과 비교하여 양보
     if (!list_empty(&ready_list)) 
     {
          struct thread *front_thread = list_entry(list_begin(&ready_list), struct thread, elem);

          if (cur->priority < front_thread->priority) {
               thread_yield();
          }
     }
}

1. 목표

선점형 우선순위 스케줄링(Preemptive Priority Scheduling)을 구현합니다.

2. 핵심 아이디어

우선순위 스케줄링의 목표는 "가장 높은 우선순위의 스레드가 항상 즉시 실행되도록 보장"하는 것입니다. 이를 위해 두 가지 핵심 전략을 사용합니다.

1. Ready List의 정렬 (자료구조)

• ready_list를 단순한 큐(FIFO)가 아닌 우선순위 큐로 관리합니다.
• 스레드를 ready_list에 추가할 때마다(unblock 또는 yield) 항상 우선순위가 높은 순서대로 정렬하여 삽입합니다.
• 결과: ready_list의 맨 앞(list_begin)에는 "대기 중인 스레드 중 가장 우선순위가 높은 스레드"가 항상 위치하게 됩니다.

2. 즉각적인 선점 (스케줄링 로직)

현재 실행 중인 스레드보다 더 높은 우선순위의 스레드가 나타나면, 즉시 CPU를 빼앗아(선점)와야 합니다. 이 검사는 2가지 시점에 필요합니다.

• Case 1: (새로운 경쟁자 등장)
  • timer_sleep이나 lock 대기에서 깨어난 스레드가 ready_list에 삽입될 때,
  • 이 스레드의 우선순위가 '현재 실행 중인 스레드'보다 높다면, 즉시 CPU를 선점합니다.
• Case 2: (현재 스레드가 약해짐)
  • '현재 실행 중인 스레드'가 스스로의 우선순위를 낮출 때(thread_set_priority),
  • ready_list의 맨 앞(대기 중인 1등)보다 우선순위가 낮아진다면, 즉시 CPU를 양보(선점)당합니다.

3. 구현 과정

1. ready_list 정렬 삽입 (in thread_unblock)

BLOCKED 상태의 스레드가 READY 상태가 될 때(e.g., lock_release, timer_sleep 종료), ready_list의 맨 뒤에 추가(list_push_back)하는 대신, 우선순위에 맞게 정렬 삽입(list_insert_ordered)하도록 수정합니다.

비교 함수 (priority_less):

/* 'b'보다 'a'의 우선순위가 높으면 true(1)를 반환하여 리스트 앞에 위치시킴 */
bool 
priority_less (const struct list_elem *a,
               const struct list_elem *b, void *aux UNUSED) {
  struct thread *t_a = list_entry (a, struct thread, elem);
  struct thread *t_b = list_entry (b, struct thread, elem);

  // t_a의 우선순위가 더 크면 'true'를 반환
  return t_a->priority > t_b->priority;
}

thread_unblock 수정:

// thread.c
void
thread_unblock (struct thread *t) {
    enum intr_level old_level;

    ASSERT (is_thread (t));

    old_level = intr_disable ();
    ASSERT (t->status == THREAD_BLOCKED);

    // list_push_back 대신 정렬 삽입 함수 사용
    list_insert_ordered(&ready_list, &t->elem, priority_less, NULL);

    t->status = THREAD_READY;

    /* * [선점 로직 1]
     * 새로 READY가 된 스레드(t)의 우선순위가
     * 현재 실행 중인 스레드보다 높다면 CPU를 양보(선점)해야 함.
     */
    if (t->priority > thread_current()->priority) {

        // 현재 인터럽트 컨텍스트(e.g., timer_interrupt)에서 호출된 경우
        if (intr_context()) {
            // 인터럽트가 끝나자마자 yield가 호출되도록 플래그만 설정
            intr_yield_on_return();
        } 
        // 일반 컨텍스트(e.g., lock_release)에서 호출된 경우
        else {
            // 즉시 yield 호출
            thread_yield();
        }
    }

    intr_set_level (old_level);
}

2. ready_list 정렬 삽입 (in thread_yield)

스레드가 스스로 CPU를 양보(thread_yield)할 때도 ready_list에 정렬 삽입되도록 수정합니다.

thread_yield 수정:

// thread.c
void 
thread_yield(void) {
    struct thread *curr = thread_current();
    enum intr_level old_level;

    ASSERT (!intr_context ());

    old_level = intr_disable();
    if (curr != idle_thread) {
        // list_push_back 대신 정렬 삽입 함수 사용
        list_insert_ordered(&ready_list, &curr->elem, priority_less, NULL);
    }

    /* * [버그 수정]
     * do_schedule()은 'if' 블록 밖에 있어야 함.
     * idle_thread가 yield 할 때도 스케줄링이 일어나야
     * ready_list에 있는 새 스레드가 실행될 수 있음.
     */
    do_schedule(THREAD_READY); 

    intr_set_level(old_level);
}

3. 선점 로직 (in thread_set_priority)

현재 실행 중인 스레드가 자신의 우선순위(thread_set_priority)를 변경할 때 선점이 발생할 수 있습니다.

thread_set_priority 수정:

// thread.c
void 
thread_set_priority(int new_priority) {

    thread_current()->priority = new_priority;

    /*
     * [선점 로직 2]
     * 만약 ready_list가 비어있지 않다면,
     * 우선순위를 낮춘 현재 스레드가
     * ready_list의 대기 중인 최고 우선순위 스레드보다
     * 우선순위가 낮아졌는지 확인해야 함.
     */
    if (!list_empty(&ready_list))
    {
        // ready_list의 맨 앞(최고 우선순위 스레드)을 가져옴
        struct thread *front_thread = list_entry(list_begin(&ready_list), struct thread, elem);

        // 만약 내(current)가 맨 앞의 스레드보다 우선순위가 낮다면
        if (thread_current()->priority < front_thread->priority) {
            // 즉시 CPU를 양보
            thread_yield();
        }
    }
}

1. 목표

timer_sleep() 함수의 기존 Busy-Waiting(적극적 대기) 방식을 Blocking(수동적 대기) 방식으로 변경하여 CPU 효율성을 향상시킵니다.

2. 핵심 아이디어: Busy-Waiting vs. Blocking

기존 timer_sleep()은 스레드가 잠들지 않고, while 루프를 계속 돌며 시간이 다 됐는지 검사했습니다.

• 기존 방식 (Busy-Waiting):

  • 스레드는 READY 상태를 유지합니다.
  • 시간이 안 됐으면 thread_yield()를 호출하여 'Ready List'의 맨 뒤로 갑니다.
  • CPU를 받으면 다시 while 루프에서 시간을 검사합니다.
  • 이 과정이 반복되며 CPU가 불필요하게 낭비됩니다.

• 개선 방식 (Blocking):

  • 스레드의 상태를 BLOCKED로 변경합니다.
  • 'Sleep List'에 "깨어날 시간(awake_tick)"과 함께 스레드를 삽입합니다. (이때 리스트는 awake_tick 기준으로 정렬됩니다.)
  • 스레드는 스케줄링 대상에서 제외되어 CPU를 전혀 사용하지 않습니다.
  • 이후 타이머 인터럽트가 발생할 때마다 'Sleep List'를 검사하여, 시간이 다 된 스레드를 'Ready List'로 옮겨 깨웁니다.

📊 방식 비교 요약

3. 구현 과정 및 주요 코드

1. 'Sleep List' 선언 및 초기화

BLOCKED 상태의 스레드 중 '시간 대기' 중인 스레드만 따로 관리할 sleep_list를 선언하고 초기화합니다.

// thread.c (전역 변수)
static struct list sleep_list;

// thread.c - thread_init() 내부
void
thread_init (void) {
    ...
    list_init (&sleep_list);
    ...
}

2. 'thread' 구조체에 'awake_tick' 필드 추가

스레드가 깨어나야 할 절대적인 시각(awake_tick)을 저장할 필드를 추가하고 초기화합니다.

// thread.h - struct thread 내부
struct thread {
    ...
    int64_t awake_tick;         /* 깨어날 시간 (ticks) */
    ...
};

// thread.c - init_thread() 내부
static void
init_thread (struct thread *t, const char *name, int priority) {
    ...
    t->awake_tick = 0;
    ...
}

3. 'timer_sleep()' 수정

기존 thread_yield() 루프를 제거하고, 새로 만들 thread_sleep()함수를 호출하도록 변경합니다.

기존 로직:

void timer_sleep (int64_t ticks) {
    int64_t start = timer_ticks ();

    ASSERT (intr_get_level () == INTR_ON);
    while (timer_elapsed (start) < ticks)
        thread_yield ();
}

수정된 로직:

// timer.c
void 
timer_sleep (int64_t ticks) {
    // 자야 할 시간이 0 이하면 즉시 리턴
    if (ticks <= 0) {
        return;
    }

    // 현재 시각 + 자야 할 기간 = 깨어날 시각
    int64_t awake_tick = timer_ticks () + ticks;

    // 스레드를 '깨어날 시각'까지 재운다.
    thread_sleep(awake_tick);
}

4. thread_sleep() 및 정렬 함수 구현

스레드를 BLOCKED 상태로 만들고 sleep_list에 삽입하는 핵심 함수와, 리스트 정렬에 필요한 비교 함수를 구현합니다.

// thread.c

/* awake_tick이 더 작은 스레드가 리스트의 앞에 오도록 비교 */
bool 
thread_awake_less(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) {
    struct thread *t_a = list_entry(a, struct thread, elem);
    struct thread *t_b = list_entry(b, struct thread, elem);

    return t_a->awake_tick < t_b->awake_tick;
}

/* 현재 스레드를 'awake_tick'까지 재운다. */
void 
thread_sleep(int64_t awake_tick) {
    struct thread *cur = thread_current();

    // Race Condition 방지를 위해 인터럽트 비활성화
    enum intr_level old_level = intr_disable();

    // idle 스레드는 잠들면 안 됨
    ASSERT(cur != idle_thread);

    // 1. 스레드에 깨어날 시간 저장
    cur->awake_tick = awake_tick;

    // 2. 'Sleep List'에 정렬하여 삽입 (가장 빨리 깰 스레드가 맨 앞)
    list_insert_ordered(&sleep_list, &cur->elem, thread_awake_less, NULL);

    // 3. 스레드를 BLOCKED 상태로 변경 (잠들기)
    thread_block();

    // 4. (나중에 깨어난 후) 인터럽트 상태 복원
    intr_set_level(old_level);
}

5. timer_interrupt() 수정

매 틱마다 ticks를 증가시키고, thread_wake_up() 함수를 호출하여 sleep_list를 검사하도록 수정합니다.

기존 로직:

/* 타이머 인터럽트 핸들러 */
static void timer_interrupt (struct intr_frame *args UNUSED) {
    ticks++;
    thread_tick ();
}

수정된 로직:

/* 타이머 인터럽트 핸들러 */
static void timer_interrupt (struct intr_frame *args UNUSED) {
    ticks++; // 전역 틱 증가

    // 'Sleep List'를 검사하여 깨울 시간이 된 스레드를 깨움
    thread_wake_up(ticks); 

    thread_tick (); // 스케줄링 관련 처리
}

void thread_wake_up(int64_t current_ticks)
{
    while (!list_empty(&sleep_list)) {

        struct list_elem *e = list_begin(&sleep_list);
        struct thread *t = list_entry(e, struct thread, elem);

        if (t->awake_tick > current_ticks)
        {
            break;
        }

        list_remove(e);
        thread_unblock(t);
    }
}

레드-블랙 트리의 삭제는 복잡해 보이지만, 핵심 전략은 아주 간단합니다.

1. 먼저 일반적인 이진 탐색 트리(BST)의 방식으로 노드를 삭제한다.
2. 삭제로 인해 레드-블랙 트리의 속성이 깨졌는지 확인한다.
3. 속성이 위반되었다면, 회전(Rotation)과 색상 변경(Recoloring)으로 재조정(Fix-up)한다.
4. 모든 속성을 다시 만족하는 유효한 레드-블랙 트리로 만든다.

결국 "BST처럼 일단 지우고, RBT 규칙에 맞게 사후 처리한다"가 전부입니다. 여기서 가장 중요한 첫 단추는 바로 '어떤 색의 노드가 실제로 삭제되었는가?'를 파악하는 것입니다.

🔑 핵심 분기점: '삭제되는 색'은 무엇인가?

삭제 후 재조정이 필요한지 아닌지를 결정하는 유일한 기준은 '실제로 트리에서 제거되는 노드의 색' 입니다. 이 '삭제되는 색'을 판별하는 기준은 삭제할 노드의 자식 수에 따라 나뉩니다.

1. 삭제할 노드의 자식이 0개 또는 1개일 때

이 경우는 간단합니다. 삭제되는 색 = 삭제되는 노드 본인의 색입니다.

             35(B)
         /           \
       20(R)           50(R)
      /    \         /      \
    10(B)  30(B)    40(B)    80(B)
           /         /
         25(R)     37(R)

// 25(R) 삭제 -> RED 삭제
// 80(B) 삭제 -> BLACK 삭제
// 40(B) 삭제 -> BLACK 삭제

2. 삭제할 노드의 자식이 2개일 때

BST 삭제 규칙에 따라, 삭제할 노드의 직후 원소(In-order Successor)를 찾아 값을 복사한 뒤, 그 Successor 노드를 대신 삭제합니다. 따라서 이 경우 삭제되는 색 = Successor 노드의 색이 됩니다.

             35(B)
         /           \
       20(R)           50(R)
      /    \         /      \
    10(B)  30(B)    40(B)    80(B)
           /         /
         25(R)     37(R)

// 20(R) 삭제 -> Successor는 25(R) -> RED 삭제
// (20번 노드의 '값'만 25로 바뀌고, 실제로는 25(R) 노드가 제거됨)

// 35(B) 삭제 -> Successor는 37(R) -> RED 삭제
// 50(R) 삭제 -> Successor는 80(B) -> BLACK 삭제

✅ 쉬운 길: RED가 삭제될 때

만약 '삭제되는 색'이 RED라면, 우리는 운이 좋은 겁니다! 아무런 추가 조치 없이 삭제 작업이 그대로 종료됩니다. RED 노드는 Black-Height에 영향을 주지 않기 때문에, 어떤 속성도 위반하지 않습니다.

• #1 (색상): 당연히 만족.
• #2 (루트): 루트가 아닌 RED를 지웠으니 불변.
• #3 (NIL): NIL 노드는 불변.
• #4 (연속 RED): RED를 제거했으므로 연속될 위험 없음.
• #5 (Black-Height): 경로의 BLACK 노드 수에 영향을 주지 않음.

⚫️ 어려운 길: BLACK이 삭제될 때

문제는 지금부터입니다. 만약 '삭제되는 색'이 BLACK이라면, 상황이 복잡해집니다. BLACK 노드는 경로의 Black-Height를 지탱하는 기둥과 같아서, 이 기둥이 빠지면 여러 속성이 연쇄적으로 무너질 수 있습니다.

삭제되는 색이 BLACK이라면 #2(루트), #4(연속 RED), #5(Black-Height) 속성을 위반할 수 있습니다.

#2번을 위반 했을때 루트 노드를 black으로 바꾸면 된다.

특히 #5 속성(Black-Height)은 거의 항상 위반된다고 볼 수 있습니다. 삭제된 BLACK 노드를 지나던 경로는 다른 경로보다 Black-Height가 1만큼 낮아지기 때문이죠.

RBT 삭제의 핵심은 바로 이 Black-Height 불균형 문제를 어떻게 해결하느냐에 있습니다.

✨ 마법의 도구: Extra Black

개발자들은 이 문제를 해결하기 위해 재미있는 개념을 도입했습니다. 바로 'Extra Black' 입니다.

#5 속성을 다시 만족 시키기 위해서 삭제된 BLACK 노드의 자리를 대체한 노드에게 임시로 '추가적인 Black 속성'을 부여하여 Black-Height의 균형을 일단 맞추는 것입니다.

경로에서 black 수를 카운트 할 때 extra black은 하나의 black으로 카운트 된다.

삭제되는 색이 Black이고 #5 속성 위반일 때 Extra Black을 부여받은 노드는 두 가지 상태가 될 수 있습니다.

1. Red-and-Black: 원래 RED였던 노드가 Extra Black을 부여받은 상태.
2. Doubly Black: 원래 BLACK이었던 노드(NIL 노드 포함)가 Extra Black을 부여받은 상태.

이제 이 두 가지 특수 상태를 어떻게 정상으로 되돌리는지 알아보겠습니다.

1. Red-and-Black 해결하기 (가장 간단한 케이스)

Red-and-Black은 "나는 원래 RED지만, 없어진 부모의 BLACK 역할까지 임시로 맡고 있어!"라는 의미입니다. 해결책은 놀랍도록 간단합니다.

Red-and-Black 노드의 색을 그냥 BLACK으로 바꾸면 모든 문제가 해결됩니다.

• 예시: 30(B) 삭제
  • 30(B)의 자리는 자식인 25(R)가 대체합니다.
  • Black-Height가 1 부족하므로 25(R)에게 Extra Black을 부여하여 25(RB) 상태가 됩니다.
  • 해결: 25(RB)의 색을 최종적으로 BLACK으로 변경합니다.
  • 결과: 부족했던 Black-Height 1이 25의 새로운 BLACK 색으로 완벽하게 채워지며, 다른 어떤 속성도 위반하지 않습니다.

2. Doubly Black 해결하기 (진짜 RBT 삭제)

Doubly Black은 "나는 원래도 BLACK인데, 추가로 BLACK 역할까지 떠안아서 너무 무거워!"라는 의미입니다. 이 문제를 해결하는 것이 RBT 삭제의 하이라이트입니다.

Doubly Black 문제를 해결하는 전략은 "문제를 나 혼자 해결하지 않고 주변(형제 노드)의 도움을 받는다" 입니다.

Doubly Black 노드 x의 형제(sibling) 노드와 형제 노드 자식들의 색상에 따라 총 4가지의 복잡한 케이스로 나뉘며, 회전(Rotation)과 색상 변경(Recoloring)을 조합하여 Extra Black을 제거해 나갑니다. 이 과정은 다음과 같은 목표를 가집니다.

1. Extra Black을 부모에게 전파시켜 문제를 위로 떠넘기기.
2. 회전을 통해 Black-Height의 균형을 맞춰 문제를 한 번에 해결하기.

Doubly Black의 4가지 케이스를 자세히 다루자.

레드-블랙 트리는 다음 두 가지 핵심 특징을 가진 자가 균형 이진 탐색 트리(Self-Balancing BST)입니다.

1. 이진 탐색 트리의 속성을 모두 가집니다. (왼쪽 서브트리는 부모보다 작고, 오른쪽 서브트리는 부모보다 큼)
2. 스스로 균형을 맞추어 트리의 높이를 가능한 낮게 유지합니다.

        50
       /
     40             -> 20을 찾기 위해서는 n의 갯수만큼 반복해야한다.
    /
  20

일반적인 BST는 데이터가 정렬된 순서로 들어올 경우, 한쪽으로 치우쳐진 편향 트리(Skewed Tree)가 되어 탐색, 삽입, 삭제의 시간 복잡도가 최악의 경우 $O(n)$이 될 수 있습니다. 레드-블랙 트리는 특정 규칙에 따라 노드의 색(Red/Black)을 지정하고, 삽입/삭제 시 트리의 구조를 재조정하여 항상 $O(log n)$의 시간 복잡도를 보장합니다.

📜 레드-블랙 트리의 5가지 속성

레드-블랙 트리가 되기 위해서는 아래의 5가지 속성을 반드시 만족해야 합니다.

1. 모든 노드는 RED 혹은 BLACK 색상을 가집니다.

2. 루트(Root) 노드는 반드시 BLACK입니다.

3. 모든 리프(Leaf) 노드는 BLACK입니다.

   잠깐, 여기서 리프(Leaf) 노드란? 레드-블랙 트리에서는 자식 노드가 없는 경우, nil 노드라는 가상의 노드가 있다고 간주합니다. 이 nil 노드가 바로 리프 노드이며, 항상 BLACK 색상입니다. 데이터가 있는 실제 노드와 동등하게 취급하여 규칙을 적용하는 데 사용됩니다.

4. RED 노드의 자식은 반드시 BLACK입니다. (즉, RED 노드가 연속으로 두 개 나타날 수 없습니다.)

5. 임의의 한 노드에서부터 그 노드의 자손인 모든 리프 노드까지 가는 경로에 있는 BLACK 노드의 수는 모두 동일합니다. (이때, 자기 자신은 카운트에서 제외합니다.)

   새로운 개념: Black-Height 속성 5 덕분에 '노드 X의 Black-Height'라는 개념이 성립됩니다. 이는 노드 X에서부터 리프 노드까지의 경로에 있는 BLACK 노드의 수를 의미합니다. 어떤 경로로 가든 BLACK 노드의 수가 같기 때문에 유일한 값으로 정의될 수 있습니다.

✨ 삽입(Insertion) 연산의 원리

레드-블랙 트리는 어떻게 균형을 잡을까요? 바로 삽입/삭제 시 위반될 수 있는 속성 4번과 5번을 해결하는 과정에서 자연스럽게 균형이 맞춰집니다.

🧐 왜 새로운 노드는 항상 RED일까?

새로운 노드를 삽입할 때는 항상 RED 색상으로 삽입합니다. 그 이유는 가장 까다로운 속성 5번(Black-Height 동일)을 깨지 않기 위해서입니다.

기존에 속성 5를 만족하는 트리에서 어느 위치에 RED 노드를 추가하더라도, 특정 경로에 BLACK 노드의 수가 추가되는 것이 아니므로 Black-Height는 변하지 않습니다. 만약 BLACK으로 삽입한다면 해당 경로의 Black-Height가 1 증가하여 속성 5를 위반하게 되고, 이를 해결하는 과정은 훨씬 더 복잡해집니다.

🌳 초기 상태: 유효한 레드-블랙 트리

먼저, 모든 속성을 만족하는 간단한 레드-블랙 트리가 있다고 가정해 봅시다. 이 트리에서 루트(10)로부터 모든 리프(nil) 노드까지의 경로에 있는 블랙 노드의 수는 1개로 동일합니다 (Black-Height = 1).

      10(B)
     /     \
   5(B)     20(B)

• 10 -> 5 -> nil 경로: 블랙 노드는 5 + nil (2개)
• 10 -> 20 -> nil 경로: 블랙 노드는 20 + nil (2개)
• 결과: 속성 5를 만족합니다.

✅: 새로운 노드 '30'을 RED로 삽입

여기에 새로운 노드 30을 RED로 삽입해 보겠습니다. 30은 20의 오른쪽 자식으로 들어갑니다.

      10(B)
     /     \
   5(B)     20(B)
              \
              30(R)  <-- RED로 삽입

삽입 후 Black-Height를 다시 계산해 볼까요?

• 10 -> 5 -> nil 경로: 블랙 노드는 5, nil (2개)
• 10 -> 20 -> (left nil) 경로: 블랙 노드는 20, nil(2개)
• 10 -> 20 -> 30 -> nil 경로: 블랙 노드는 20, nil(2개)

결론: 새로운 RED 노드가 추가되었지만, 어떤 경로든 Black-Height는 여전히 2로 동일합니다. 가장 중요한 속성 5가 깨지지 않았습니다. (이 경우 다른 속성 위반도 없어서 바로 유효한 트리가 되었습니다.)

❌: 새로운 노드 '30'을 BLACK으로 삽입 (잘못된 방법)

만약 같은 위치에 30을 BLACK으로 삽입한다면 어떻게 될까요?

      10(B)
     /     \
   5(B)     20(B)
              \
              30(B)  <-- BLACK으로 삽입

• 10 -> 5 -> nil 경로: 블랙 노드는 5,nil(2개)
• 10 -> 20 -> (left nil) 경로: 블랙 노드는 20, nil (2개)
• 10 -> 20 -> 30 -> nil 경로: 블랙 노드는 20, 30, nil (3개)

삽입 과정

1. 일반적인 BST처럼 노드를 삽입할 위치를 찾습니다.
2. 해당 위치에 RED 색상으로 새로운 노드를 삽입합니다.
3. 삽입 후 레드-블랙 트리의 속성을 위반하는지 확인합니다. (주로 속성 2 또는 4)
4. 속성을 위반했다면, 재조정(Restructuring)과 색상 변경(Recoloring)을 통해 해결합니다.

🛠️ 삽입 후 재조정: 3가지 케이스

새로운 RED 노드(N)를 삽입했을 때, 부모 노드(P)가 RED라면 속성 4(RED는 연속될 수 없다)를 위반하게 됩니다. 이 "Double Red" 문제를 해결하는 방법은 삼촌 노드(U, 부모의 형제 노드)의 색상에 따라 3가지 케이스로 나뉩니다.

(N: 새로 삽입된 노드, P: 부모, G: 조부모, U: 삼촌)

CASE 1: 삼촌(U)이 RED인 경우

가장 간단한 케이스입니다. Double Red가 발생했지만, 넘겨줄 반대편(삼촌)도 RED인 상황입니다. 이때는 색상 변경(Recoloring)으로 해결합니다.

• 해결 방법:

  1. 부모(P)와 삼촌(U)을 BLACK으로 변경합니다.
  2. 조부모(G)를 RED로 변경합니다.
  3. 조부모(G)를 새로운 노드(N)로 간주하고, 위반 사항이 있는지 다시 확인합니다. (만약 조부모(G)의 부모도 RED라면 또다시 Double Red 문제가 발생하므로 재귀적으로 해결)

• 예시: 아래와 같은 트리에 30을 삽입해 봅시다.

          20(B)
         /     \
       10(R)   50(R)

  50의 왼쪽에 30(R)을 삽입하면 P(50)와 N(30)이 모두 RED가 됩니다. 이때 U(10)도 RED입니다.

          20(B)
         /     \
       10(R)   50(R)  <-- P
               /
             30(R)    <-- N

  1. P(50)와 U(10)를 BLACK으로, G(20)를 RED로 변경합니다.
  2. G(20)가 RED가 되었지만 루트이므로 속성 2(루트는 BLACK)를 위반합니다.
  3. 따라서 20을 다시 BLACK으로 변경하여 모든 속성을 만족시킵니다.

          20(B)
         /     \
       10(B)   50(B)
               /
             30(R)

  CASE 2: 삼촌(U)이 BLACK이고, 경로가 직선 형태(Line)인 경우

삽입된 노드(N) - 부모(P) - 조부모(G)의 경로가 // 또는 \\ 모양의 직선입니다. 색상 변경과 회전을 통해 균형을 맞춥니다.

• 해결 방법:

  1. 부모(P)를 BLACK으로, 조부모(G)를 RED로 변경합니다.
  2. 조부모(G)를 기준으로 회전합니다. (P가 G의 왼쪽 자식이면 우회전, 오른쪽 자식이면 좌회전)

• 예시: CASE 2에서 변환된 트리로 계속 진행해 봅시다.

          50(B) <-- G
         /
       40(R) <-- P
      /
    20(R) <-- N (역할이 바뀜)

  1. P(40)를 BLACK으로, G(50)를 RED로 변경합니다.

          50(R)
         /
       40(B)
      /
    20(R)

  2. G(50)를 기준으로 우회전합니다.

          40(B)
         /     \
       20(R)   50(R)

CASE 3: 삼촌(U)이 BLACK이고, 경로가 꺾인 형태(Triangle)인 경우

삽입된 노드(N) - 부모(P) - 조부모(G)의 경로가 꺾여있는 < 또는 > 모양입니다. 이 경우는 회전(Rotation)을 통해 경로를 직선 형태로 만들어 CASE 3으로 전환하여 해결합니다.

• 해결 방법:

  1. 부모(P)를 기준으로 회전하여 경로를 직선 형태로 만듭니다. (P가 G의 왼쪽 자식이면 좌회전, 오른쪽 자식이면 우회전)
  2. 이제 CASE 3의 상황이 되었으므로, CASE 3의 방법으로 해결합니다.

• 예시: 아래 트리에 40을 삽입해 봅시다.

          50(B)
         /
       20(R)      <-- G
      /   \
          40(R)   <-- N

  N(40)-P(20)-G(50)의 경로가 꺾여있고, U는 nil 노드이므로 BLACK입니다.

  1. P(20)를 기준으로 좌회전합니다.

          50(B)
         /
       40(R)      <-- 이제 N이 됨 (CASE 3 형태로 변환)
      /
    20(R)

  2. 이제 CASE 3의 형태로 바뀌었으므로 아래 방법으로 해결합니다.

결론

레드-블랙 트리의 삽입 과정은 다소 복잡해 보일 수 있지만, '삼촌 노드의 색상'을 기준으로 케이스를 나누고, 색상 변경(Recoloring)과 회전(Rotation)이라는 두 가지 도구를 적절히 사용하여 트리의 균형을 맞춘다는 핵심 원리를 이해하면 충분히 정복할 수 있습니다.

DP 정복을 위한 4단계 공부법

DP를 효과적으로 공부하기 위한 체계적인 접근법입니다.

1단계: 핵심 개념 이해하기 💡

DP의 두 가지 대표적인 방식, 메모이제이션(Memoization)과 타뷸레이션(Tabulation)의 차이를 이해하는 것부터 시작해라.

• 메모이제이션 (Top-down): 큰 문제를 재귀 호출로 풀어나가되, 한 번 계산한 결과는 기록해두고 재사용하는 방식입니다. 로직이 직관적이라 처음 접근하기 좋습니다.
• 타뷸레이션 (Bottom-up): 가장 작은 문제부터 차례대로 정답을 구해 테이블을 채워나가는 방식입니다. 보통 반복문으로 구현하며 성능이 더 좋은 경우가 많습니다.

처음에는 어떤 방식이든 하나만 정해서 익숙해지는 것을 추천합니다. 대부분의 코딩 테스트에서는 Bottom-up 방식이 주로 사용됩니다.

2단계: '생각의 틀' 훈련하기 💪

새로운 DP 문제를 만났을 때, 항상 아래 3가지 질문을 스스로에게 던지는 연습을 하세요.

1. DP 상태 정의 (dp[i]는 무엇인가?): dp 배열의 각 칸이 어떤 의미를 갖는지 명확하게 정의해야 합니다.

   • (예: dp[i] = i원을 만드는 동전의 최소 개수)
   • (예: dp[i] = i번째 집까지 칠하는 최소 비용)

2. 점화식 찾기 (dp[i]와 이전 값들의 관계는?): i번째 문제의 정답(dp[i])을 그보다 작은 문제들의 정답(dp[i-1], dp[i-2] 등)을 이용해 어떻게 구할 수 있을지 고민합니다. 여기가 DP의 핵심입니다.

   • (예: dp[i]는 dp[i-1]과 dp[i-2]를 더한 값이다.)
   • (예: dp[i]는 dp[i-1], dp[i-2], dp[i-5] 중 최솟값에 1을 더한 값이다.)

3. 초기값 설정 (Base Case는 무엇인가?): 점화식이 시작될 수 있는 가장 작은 문제의 정답(dp[0], dp[1] 등)을 직접 계산해서 dp 배열에 넣어줍니다. 이 기반이 없으면 점화식이 무너집니다.

3단계: 유형별 문제 풀기 ✅

무작위로 풀기보다, 클래식한 유형별로 묶어서 풀며 패턴을 익히는 것이 효과적입니다.

• 기본 다지기: 1차원 DP 배열을 사용하는 가장 기초적인 문제들
• 응용하기: 2차원 DP 배열, 배낭(Knapsack), LIS(가장 긴 증가하는 부분 수열) 등 유명한 유형들

4단계: 다른 사람의 코드 보기 👀

문제를 푼 후에 다른 사람들은 어떻게 풀었는지 꼭 확인해라. 같은 문제라도 점화식을 다르게 세우거나, DP 상태를 더 효율적으로 정의하는 방법을 배울 수 있습니다.

레벨별 추천 문제 (백준)

아래 문제들을 순서대로 풀어보시면 DP에 대한 감을 잡는 데 큰 도움이 될 겁니다.

LV 1: DP와 친해지기 (핵심 원리)

• 1463번: 1로 만들기
  • DP의 가장 기본이 되는 문제입니다. '생각의 틀 3단계'를 적용하는 연습을 하기에 완벽합니다.
• 11726번: 2×n 타일링
  • 매우 유명한 피보나치 수열의 변형 문제입니다. 간단한 점화식을 세우는 연습을 할 수 있습니다.
• 9095번: 1, 2, 3 더하기
  • dp[i]를 정의하고, i-1, i-2, i-3과의 관계를 찾는 연습을 하기에 좋습니다.
• 2579번: 계단 오르기
  • 이미 푸셨지만, 지금의 지식으로 다시 한번 점화식을 유도해보세요. 왜 그런 로직이 나왔는지 완벽히 이해하는 것이 중요합니다.

LV 2: 조금 더 생각하기 (1차원 DP 응용)

• 11053번: 가장 긴 증가하는 부분 수열 (LIS)
  • DP의 대표 유형 중 하나인 LIS의 가장 기초적인 문제입니다.
• 1912번: 연속합
  • 이전 값들을 누적하는 방식에 대한 새로운 아이디어를 얻을 수 있습니다.
• 1149번: RGB거리
  • dp 배열을 2차원으로 확장(dp[i][색깔])하는 첫걸음입니다.

LV 3: 유명 유형 정복하기

• 12865번: 평범한 배낭
  • 모든 코딩 테스트의 단골손님, 배낭(Knapsack) 문제의 가장 표준적인 형태입니다. 이 문제는 풀이법을 거의 외워둘 가치가 있습니다.
• 9251번: LCS (최장 공통 부분 수열)
  • 두 문자열을 다루는 대표적인 2차원 DP 문제입니다.

함수 매개변수

첫 6개 함수 매개변수는 각 레지스터에 로드되며, 그 후 매개변수는 크기에 따라 32비트 데이터는 4바이트 오프셋, 64비트 데이터는 8바이트 오프셋은 콜 스택에 로드된다.

함수 매개변수가 콜 스택에 전달될 때, 스택은 메모리 정렬을 위해 8바이트 크기의 정해진 '슬롯(slot)' 단위로 공간을 할당합니다. 이 때문에 전달되는 데이터의 실제 크기와 상관없이 모든 매개변수는 이 8바이트 슬롯 하나를 차지하게 됩니다. 즉, 8바이트 크기의 long 타입은 슬롯을 완전히 채우고, 4바이트 int, 2바이트 short, 1바이트 char와 같이 작은 데이터들은 슬롯의 일부만 사용하며 나머지 빈 공간은 의미 없는 값(패딩, Padding)으로 채워집니다.

예시 추적

다음 코드 예시를 한 번 추적해보자.

#include <stdio.h>

int assign(void) {
    int y = 40;
    return y;
}

int adder(void) {
    int a;
    return a + 2;
}

int main(void) {
    int x;
    assign();
    x = adder();
    printf("x is: %d\n", x);
    return 0;
}

이 코드를 다음 명령어로 컴파일하고, 어셈블리어로 변환해보자.

# 컴파일
gcc -o prog prog.c

# 어셈블리로 변환
objdump -d

변환된 어셈블리어

0000000000400526 <assign>:
  400526:       55                      push   %rbp
  400527:       48 89 e5                mov    %rsp,%rbp
  40052a:       c7 45 fc 28 00 00 00    movl   $0x28,-0x4(%rbp)
  400531:       8b 45 fc                mov    -0x4(%rbp),%eax
  400534:       5d                      pop    %rbp
  400535:       c3                      retq

0000000000400536 <adder>:
  400536:       55                      push   %rbp
  400537:       48 89 e5                mov    %rsp,%rbp
  40053a:       8b 45 fc                mov    -0x4(%rbp),%eax
  40053d:       83 c0 02                add    $0x2,%eax
  400540:       5d                      pop    %rbp
  400541:       c3                      retq

0000000000400542 <main>:
  400542:       55                      push   %rbp
  400543:       48 89 e5                mov    %rsp,%rbp
  400546:       48 83 ec 10             sub    $0x10,%rsp
  40054a:       e8 e3 ff ff ff          callq  400526 <assign>
  40054f:       e8 d2 ff ff ff          callq  400536 <adder>
  400554:       89 45 fc                mov    %eax,-0x4(%rbp)
  400557:       8b 45 fc                mov    -0x4(%rbp),%eax
  40055a:       89 c6                   mov    %eax,%esi
  40055c:       bf 04 06 40 00          mov    $0x400604,%edi
  400561:       b8 00 00 00 00          mov    $0x0,%eax
  400566:       e8 95 fe ff ff          callq  400400 <printf@plt>
  40056b:       b8 00 00 00 00          mov    $0x0,%eax
  400570:       c9                      leaveq
  400571:       c3                      retq

각 함수는 프로그램에 선언된 이름에 해당하는 심볼릭 라벨로 시작한다. 함수 사벨의 주소는 해당 함수의 첫 번째 명령어이다.

main 추적

아래 그림은 main 실행 직전의 스택을 보여준다. %rbp에는 이전 함수의 스택 프레임 주소가 담겨있으며, %rsp는 스택 프레임의 시작주소인 0xd48이 담겨있다. %rip에는 명령어의 시작 주소인 0x542가 담겨있다.

첫 번째 명령은 %rbp의 현재 값을 스택에 넣는다. 스택은 낮은 주소 방향으로 커지므로 스택 포인터 %rsp는 0xd40으로 업데이트 된다. %rip는 다음 명령어 주소로 업데이트 된다.

push 의 역할

1. 스택 포인터(%rsp)를 8만큼 감소시켜 스택에 새로운 공간을 확보합니다. (이것이 '스택 영역 확장'에 해당합니다.)
2. 지정한 레지스터의 값(예: %rbp의 값)을 새로 확보된 공간에 복사합니다.

다음 mov 명령어는 %rbp의 값이 %rsp와 같아지도록 업데이트한다. 이제 %rbp는 main 함수의 스택 프레임의 시작 위치를 가리킨다. %rip는 순서상 다음 명령으로 이동한다. 0xd48에는 리턴주소가 담긴다.

sub 명령은 스택 포인터 주소에서 x10을 뺀다. 이것은 스택이 16바이트 커지게 만든다 -> 스택 한 칸 8바이트, 2칸 위로 %rsp는 0xd30을 가리키게 된다. %rip 값은 다음 명령 주소를 가리킨다.

callq 명령은 %rip의 값, 반환주소를 스택에 넣는다. 반환 주소는 함수의 실행이 끝나고, main으로 돌아왔을때 재개되는 프로그램 주소이다.

다음으로, callq 명령은 assign의 함수의 주소를 %rip에 옮긴다. 따라서 다음 실행은 assign이 실행된다.

assign 함수의 첫 두 명령은 main과 같다. %rbp에 저장된 main 함수의 스택 프레임을 스택에 저장한다.

다음 명령은 스택 프레임을 스택의 맨 위 값으로 업데이트 한다.

mov 명령어는 %0x28(40)을 스택 주소 -0x4(%rbp)에 넣는다. 이 주소는 프레임 포인터보다 4바이트 더 위에 있다. 여기서 %rsp 값은 바꾸지 않는다.

값 $0x28을 레지스터 %eax에 넣는다. 이 레지스터는 반환값을 가진다.

이 시점은 assign 함수의 실행이 거의 완료된다. 다음으로 pop %rbp 명령이 실행된다. 이 명령은 %rbp의 값을 이전 값, 0xd40으로 원복한다. 또한 %rsp 값을 0xd28로 수정한다.(스택 포인터를 8만큼 증가)

assign의 마지막 명령은 retq이다. 이전에 저장했던, 리턴주소를 스택에서 꺼내서 rip를 업데이트하여 다음 명령은 0x55f가 실행되도록한다.

main으로 돌아와서 addr 함수를 호출하면 새로운 반환주소 0x554를 스택의 이전 주소로 덮어쓴다. %rip는 addr의 첫 번째 명령(0x536)을 가리킨다.

addr 함수의 첫 번째 명령은 호출자의 프레임 포인터(main의 %rbp)를 스택에 저장한다.

%rsp의 값(0xd20)으로 %rbp를 업데이트 한다.

출처 (Source)

이 게시물의 내용과 이미지는 Suzanne J. Matthews, Tia Newhall, Kevin C. Webb의 Dive into Systems를 기반으로 하며, Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License에 따라 사용되었습니다.

csapp

• 3.7 프로시저
• 3.8 배열과 행렬

기타

• 정글 9기 나만무 프로젝트 발표 관람 및 질의응답

코딩 테스트 문제풀이

• [백준] 14501 - 퇴사(Top_Down, Bottom_up)