길이가 $n$인 배열 $A$에서 만들 수 있는 연속 부분 배열의 개수는 총 $\frac{n(n+1)}{2}$개입니다.

이 전체 부분 배열들의 집합을 "어느 인덱스에서 끝나는가?"를 기준으로 $n$개의 서로소 부분집합(Disjoint Sets)으로 나눕니다.

• $S_0$: 인덱스 $0$에서 끝나는 부분 배열들의 집합
• $S_1$: 인덱스 $1$에서 끝나는 부분 배열들의 집합
• $\dots$
• $S_j$: 인덱스 $j$에서 끝나는 부분 배열들의 집합 ($0 \le j < n$)

모든 연속 부분 배열은 반드시 $0$부터 $n-1$ 중 단 하나의 끝점을 가지므로, 전체 부분 배열 중 최대합(전역 최적해)은 각 집합의 최댓값들 중 가장 큰 값과 같습니다.

$$\text{Global Max} = \max_{0 \le j < n} \Big( \max(S_j) \Big)$$

2. 점화식의 수학적 유도 (최적 부분 구조)

이제 문제를 "$j$번째 원소로 끝나는 부분 배열 중 최대합 $M[j]$를 어떻게 구할 것인가?"로 좁힐 수 있습니다.

수학적으로 $M[j]$는 다음과 같이 정의됩니다.

$$M[j] = \max_{0 \le i \le j} \sum_{k=i}^j A[k]$$

이 식에서 시작 인덱스 $i$의 경우의 수를 $i = j$인 경우(원소 1개짜리)와 $i < j$인 경우(길이가 2 이상인 경우)로 분리합니다.

$$M[j] = \max \left( A[j],; \max_{0 \le i \le j-1} \left( \sum_{k=i}^{j-1} A[k] + A[j] \right) \right)$$

여기서 $A[j]$는 $i$와 무관한 공통 덧셈 상수이므로 밖으로 묶어낼 수 있습니다.

$$M[j] = \max \left( A[j],; \left( \max_{0 \le i \le j-1} \sum_{k=i}^{j-1} A[k] \right) + A[j] \right)$$

괄호 안의 $\max_{0 \le i \le j-1} \sum_{k=i}^{j-1} A[k]$는 정확히 이전 단계의 정의인 $M[j-1]$입니다.

따라서 다음과 같은 전형적인 동적 계획법의 점화식이 도출됩니다.

$$M[j] = \max(A[j],; M[j-1] + A[j])$$

식을 $A[j]$를 기준으로 정리하면 더욱 직관적인 형태가 됩니다.

$$M[j] = A[j] + \max(0,; M[j-1])$$

• $M[j-1] > 0$이면: 이전 누적합을 붙이는 것이 이득이므로 $M[j-1] + A[j]$ 선택
• $M[j-1] \le 0$이면: 이전까지의 최적합이 음수이므로, 이전 기록을 버리고 $A[j]$ 단독으로 새로 시작하는 것이 무조건 이득

3. 메모리 최적화 ($O(N) \to O(1)$ 공간)

점화식 $M[j] = \max(A[j], M[j-1] + A[j])$를 보면, $M[j]$를 계산할 때 필요한 이전 값은 오직 직전 값인 $M[j-1]$ 하나뿐입니다. $M[j-2], M[j-3]$ 등 그 이전의 값들은 알 필요가 없습니다.

따라서 $N$ 크기의 배열 $M[\ ]$을 메모리에 유지할 필요 없이, 단 하나의 변수(currentSum)만 계속 덮어쓰면서 갱신하면 충분하므로 공간 복잡도가 $O(1)$이 됩니다.

CORS (Cross-Origin Resource Sharing) 이해하기

CORS는 웹 브라우저에서 실행되는 스크립트가 다른 도메인(출처)의 자원에 접근할 수 있는 권한을 부여하도록 브라우저에 알려주는 체제입니다.

기본적으로 웹 브라우저는 보안상의 이유로 SOP (Same-Origin Policy, 동일 출처 정책)를 따릅니다. 이는 자바스크립트가 자신이 로드된 도메인과 다른 도메인으로 HTTP 요청을 보내는 것을 제한하는 규칙입니다. 하지만 현대 웹 개발에서는 API 서버와 프론트엔드 서버가 분리된 경우가 많아, 이를 안전하게 허용하기 위해 CORS가 사용됩니다.

1. '출처(Origin)'의 기준

브라우저는 다음 세 가지 요소가 모두 일치해야 동일한 출처로 판단합니다.

• Protocol (http, https)
• Host (domain.com, localhost)
• Port (80, 443, 3000)

예를 들어, https://naver.com에서 https://api.naver.com으로 요청을 보내면 호스트가 다르기 때문에 CORS 정책의 적용을 받게 됩니다.

2. CORS의 작동 방식

CORS는 HTTP 헤더를 통해 작동하며, 크게 두 가지 요청 방식으로 나뉩니다.

단순 요청 (Simple Request)

다음 조건을 만족하는 경우, 브라우저는 바로 본 요청을 보냅니다.

• 메서드가 GET, POST, HEAD 중 하나일 것
• 헤더가 Accept, Content-Language 등 기본적인 것만 포함될 것

예비 요청 (Preflight Request)

대부분의 현대적인 API 요청(JSON 데이터 전송 등)은 이 방식에 해당합니다.

1. OPTIONS 메서드를 사용하여 본 요청을 보내기 전, 서버에 "내가 이런 요청을 보내도 되니?"라고 먼저 물어봅니다.
2. 서버는 응답 헤더에 허용되는 출처(Access-Control-Allow-Origin) 등을 담아 보냅니다.
3. 브라우저가 응답을 확인하고 안전하다고 판단하면 그제야 진짜 요청을 보냅니다.

3. 주요 응답 헤더

서버 측에서 CORS 문제를 해결하기 위해 설정해야 하는 핵심 헤더들입니다.

4. 흔히 발생하는 오해

• 서버 간 통신에는 해당되지 않음: CORS는 웹 브라우저가 강제하는 보안 정책입니다. 따라서 서버(Node.js, Java 등)에서 다른 서버로 요청을 보낼 때는 발생하지 않습니다.
• 서버는 요청을 수행할 수도 있음: 브라우저가 응답을 차단하는 것이지, 서버가 요청을 아예 안 받는 것은 아닙니다. 서버 로그에는 성공으로 뜨는데 브라우저 콘솔에서만 에러가 날 수 있습니다.

cors가 왜 보안이랑 연결되는 거지??

SOP(Same-Origin Policy, 동일 출처 정책)가 보안의 핵심인 이유는 간단합니다. "내가 로그인한 A 사이트의 권한을 B 사이트가 마음대로 가로채지 못하게 하기 위해서"입니다.

만약 SOP가 없다면, 여러분이 브라우저에서 탭을 여러 개 띄워놓고 사용하는 것 자체가 매우 위험한 일이 됩니다.

1. SOP가 막아주는 핵심 공격: CSRF (사이트 간 요청 위조)

가장 대표적인 시나리오는 다음과 같습니다.

1. 상황: 여러분이 bank.com(은행 사이트)에 로그인되어 있고, 브라우저에는 해당 사이트의 로그인 세션(쿠키)이 남아 있습니다.
2. 공격: 이때 피싱 메일 등을 통해 악성 사이트인 evil.com에 접속하게 됩니다.
3. 실행: evil.com의 자바스크립트가 배경에서 몰래 bank.com/transfer?to=attacker&amount=10000이라는 요청을 보냅니다.
4. 결과: 브라우저는 bank.com으로 요청을 보낼 때 저장된 쿠키(인증 정보)를 함께 실어 보냅니다. SOP가 없다면 은행 서버는 "오, 정당한 사용자가 돈을 보내라고 했네?"라고 판단하여 송금을 처리해 버립니다.

2. 정보 유출 방지 (Data Privacy)

SOP는 단순히 '요청'을 막는 것뿐만 아니라, '응답 데이터에 접근하는 것'을 막습니다.

• naver.com에 접속 중인 상태에서 다른 탭으로 들어간 malicious-site.com이 자바스크립트를 이용해 naver.com/my-profile의 내용을 읽어오려 한다고 가정해 봅시다.
• SOP가 적용되어 있다면, 브라우저는 출처(Origin)가 다르다는 것을 확인하고 malicious-site.com이 네이버 서버로부터 온 응답 데이터를 읽지 못하도록 차단합니다.
• 이 정책 덕분에 개인 정보나 이메일 내용 등이 다른 사이트의 스크립트에 의해 노출되지 않습니다.

3. 브라우저의 '샌드박스' 역할

웹 브라우저는 수많은 서로 다른 서비스들이 한 공간(브라우저)에서 실행되는 환경입니다. SOP는 각 웹사이트가 자신만의 독립된 보안 구역(Sandbox) 안에서만 놀 수 있도록 벽을 세우는 역할을 합니다.

• 벽이 없다면: 웹은 무법천지가 되어, 어떤 사이트를 방문하든 내 브라우저에 열려 있는 다른 모든 사이트의 정보를 털어갈 수 있게 됩니다.

요약하자면

SOP는 브라우저 차원의 최소한의 방어선입니다.

1. 누가 나인 척하는 것(요청 위조)을 어렵게 만들고,
2. 내 정보를 훔쳐보는 것(데이터 탈취)을 원천 봉쇄합니다.

CORS는 바로 이 엄격한 보안 벽(SOP)에 "이 사이트는 믿을 만하니까 우리가 정한 규칙 하에 벽을 살짝 열어주자"라고 예외를 두는 허가증 같은 개념인 셈입니다.

그럼 cors를 허용해주는건 특정 서버에서 다른 서버를 믿을 수 있다고 등록해줘야 가능한건가?? 그러니까 예를 들어서 edward_giver 서버에서 edward_taker 서버는 믿을 수 있는 서버라고 등록을 해놨다면 edward_taker.com이 edward_giver 서버로 요청을 보내도 정상응답을 받을 수 있는 것이고 edward_taker 서버가 edward_giver 서버를 등록하지 않았다면 그 요청은 불발되고 브라우저가 에러를 띄우는 건가?

정확하게 이해하셨습니다. 다만, 주체와 방향을 조금 더 명확히 정리하면 완벽합니다. CORS 설정은 자원을 가진 서버(Giver)가 누구에게 허용할지(Taker)를 결정하는 보안 정책입니다.

말씀하신 예시를 바탕으로 구조를 다시 정리해 드릴게요.

1. 누가 누구를 등록해야 하나요?

CORS는 '데이터를 주는 서버'가 설정하는 것입니다.

• 상황: edward_taker.com(클라이언트/프론트엔드)이 edward_giver.com(API 서버)에 데이터를 요청합니다.
• 설정 주체: edward_giver 서버가 설정을 가지고 있어야 합니다.
• 내용: edward_giver 서버 설정 파일에 "우리 데이터를 edward_taker.com 출처에서 가져가는 것을 허용한다"라는 화이트리스트를 등록하는 방식입니다.

2. 요청이 불발되는 시나리오

질문하신 내용처럼 등록 여부에 따라 결과가 달라집니다.

3. 브라우저가 에러를 띄우는 타이밍

여기서 재미있는 점은 "요청 자체는 서버에 도달할 수도 있다"는 것입니다.

1. 단순 요청의 경우: 브라우저가 일단 edward_giver에게 데이터를 달라고 요청합니다. 서버는 평소처럼 데이터를 보내주지만, 응답 헤더에 "허용" 표시가 없으면 브라우저가 그 데이터를 파기하고 콘솔에 빨간색 CORS 에러를 띄웁니다.
2. 예비 요청(Preflight)의 경우: 브라우저가 본 요청을 보내기 전에 "얘한테 데이터 줘도 돼?"라고 먼저 물어봅니다(OPTIONS 메서드). 이때 서버가 "안 돼"라고 하면 본 요청은 시작조차 하지 않습니다.

4. 왜 '받는 쪽(Taker)'은 설정이 필요 없나요?

CORS 에러는 '내 소중한 데이터를 아무나 가져가지 못하게 보호'하려는 서버의 방어 기제이기 때문입니다.

• edward_taker 서버는 그저 요청을 보내는 입장일 뿐입니다.
• 만약 edward_taker가 보낸 요청이 실패한다면, 그것은 edward_taker가 잘못해서가 아니라 edward_giver가 문을 열어주지 않았기 때문입니다.

요약

• Giver(서버): "나는 edward_taker.com만 믿어. 얘네한테는 데이터 보내줄게." (설정 필요)
• Taker(클라이언트): "나 edward_taker인데 데이터 좀 줘!" (설정 불필요, 요청만 보냄)
• 브라우저(경찰): "Giver가 너(Taker) 허용 안 했네? 이 데이터는 못 보여줘!" (에러 발생)

아무런 의미 없이 부모 프로세스의 가상 메모리 전체를 복제하는 오버헤드를 피할 수 있습니다.

다수의 프로세스들이 같은 파일을 공유할 때 프로세스마다 곧바로 독립적인 파일을 자신의 가상 메모리에 갖는 것이 아니라 일단은 동일한 페이지를 공유하기 때문에 메모리 낭비를 줄일 수 있습니다.

ref count??

python에 대해서 공부하다가 ref count라는 정책을 발견했다. 이 정책은 python의 모든 객체에 ref count라는 값을 두고 이 값을 조절하면서 ref count가 0이 되었을 때 해당 객체를 deallocate하는 정책이다. CPython에서 ref count라는 값은 실제 객체의 값과 물리/가상 메모리 레벨에서 붙어있다고 한다. (즉 한번에 같이 malloc된다고 보면 될 것 같다.) 이는 C++처럼 기계 레벌에 가까운 언어와는 다르게 명시적으로 메모리를 관리하는 방법이 없고, 언어 차원에서 메모리 관리를 담당해야하기 때문에 생겨난 정책으로 보인다.

그래서 이게 copy-on-write이랑 무슨 상관이야?

celery에 대해서 공부를 하다보니 concurrency라는 개념을 알게 되었는데, 이는 하나의 celery worker가 처리할 수 있는 task의 수를 말한다. 하나의 worker가 여러 task를 처리하려면 당연히 execution unit이 여러개 필요할 텐데, 이 unit의 타입을 지정할 수 있다. default 값으로는 prefork(multiprocess)가 있고 이외에도 threads, gevents, ...가 있는데, 이 중에 prefork 방식에 대해서 생각해보자. 이름에서 유추할 수 있듯이 fork를 통해서 자식 프로세스를 미리 생성해두는 방식인데, 흔히 생각하기로는 당연히 copy-on-write 정책을 통해서 메모리 최적화가 어느 정도는 이루어질 것이라고 예상할 수 있는데.. 사실은 그렇지 않다. 단순히 특정 객체를 read하는 작업만으로도 ref count가 바뀌기 때문에 사실은 내부적으로 write가 발생하게 되고 바로 그 객체가 속한 페이지 테이블을 복사하게 되는 것. (heap) 따라서 우리가 생각하는 것과는 다르게 cow가 진행되므로 python 기반의 multiprocess 방식은 생각보다 메모리를 많이 잡아먹을 수 있다. (이런 점에 미루어 볼 때 python은 CPU bound의 작업에 좋지 않은 언어인 것 같다...) 일단 다른 언어와 프레임워크에서는 모르겠지만 python 기반의 프레임 워크에서는 이런 메모리 내부 동작을 의식하는 것이 필요할 것 같다.

• Interrupt: 외부 하드웨어에 의해서 인스트럭션들 사이에 발생하는 비동기적 예외 상황 (타이머 인터럽트, 입출력 장치)
• Trap: 인스트럭션 직후에 발생하는 의도적인 예외 상황 (시스템 콜)
• Fault: 인스트럭션 실행 중에 발생하는 동기적 예외 상황 (page fault, segmentation fault, divide by zero fault)
• Abort: 주로 하드웨어에서 발생하는 복구 불가능한 예외 상황

시그널

이런 예외 상황에 대해서 커널이 핸들러를 실행하고 그 후 프로세스가 특정 조치를 취해야한다고 판단이 되면, 커널은 프로세스에게 시그널을 보내고 프로세스는 이에 대해서 default action을 취하거나 signal handler를 실행한다. 시그널은 도착 순서를 보장하지 않으며 같은 시그널이 여러번 도착해도 1번만 처리한다는 특징이 있다. 따라서 시그널 핸들링은 매우 주의해서 해야한다.

사건의 발단

내가 CSAPP을 읽고난 후 알고 있었던 가상 메모리는 VPN + VPO의 조합이었는데, 깃북을 읽어보니까 내가 알고 있던 것보다 훨씬 더 자세하게 세분화가 되어있었다. 그래서 내 공부의 흐름에 갑자기 asynchronous exception이 일어났다.

아 일단 예전에 공부했던 내용도 기억이 잘 안나네..

일단 CPU(프로세스)가 메모리에 접근할 때, 가상 주소를 사용한다. (자세한 이해를 돕기 위해서 내부 원리를 보충 설명하자면 어떤 코드가 ELF 파일로 컴파일 될 때는 가상 주소만 배정이 되고 그 가상 주소가 실제로 어떤 물리 공간을 배정받고 어떤 물리 주소를 가질 지는 로드되기 전까지는 모른다. 즉 페이지 테이블이 생성되는 것 자체가 로드 시점 이후부터 시작된다.)

이 과정에서 MMU는 페이지 테이블을 참조하여 가상 주소를 물리 주소로 변환한다.

이 지점에서 그럼 MMU는 어떻게 메모리에 있는 페이지 테이블에 접근하는 건지 의문이 들었다. (알아보니 어떤 프로세스가 시작될 때 그 프로세스의 페이지 테이블 주소를 CR3이라는 레지스터에 넣어 둔다고 한다.)

또 내 생각에 페이지 테이블은 가상 메모리의 커널 영역에 있을 것 같은 데 그 생각이 맞는 지 궁금해졌다. (그렇다고 한다.)

또 대부분 사람들이 가상 메모리의 커널 영역이 프로세스들 간에 완전히 공통인 영역이라고 생각하는데, 페이지 테이블이나 파일 디스크립터 테이블 그리고 스레드의 커널 스택(각 스레드의 레지스터, 지역 변수 등을 백업하기 위해서 생성되는 각 스레드들을 위한 독립적인 커널 공간)을 고려하면 이 커널 영역이 완전히 공통인 건 말이 안된다는 생각을 했다. (이것도 내 생각이 맞았다.)

암튼 VPN으로 페이지 테이블 내에서 엔트리를 찾아내고 그 곳에 저장된 PPN을 얻어낸다. 이렇게 얻어낸 PPN에 PPO(VPO)를 조합해서 물리주소를 얻어내는 것이다.

그래서 깃북에 나온 그 가상주소 다이어그램의 정체는 뭐지??

지금까지가 내가 원래 알고 있던 가상 메모리의 형태인데, 이를 단일 레벨 페이지 모델이라고 부른다고 한다. 이는 구조가 단순하지만 페이지 테이블 크기가 너무 커진다는 문제가 있다. (전체 논리 주소 공간의 페이지 테이블을 무조건 생성. 논리 주소 공간이란 프로세스가 가질 수 있는 최대 가상 메모리 범위)

이에 대한 해결책으로 단일 거대 페이지 테이블을 여러 레벨로 분리하여 멀티 레벨 페이지 모델이라는 개념이 탄생했다고 한다. 이 자세한 구조가 뭔지는 공부를 더 해야겠지만, 핵심은 "필요한 만큼만" 페이지 테이블을 동적으로 생성한다는 점이라고 말할 수 있다. 이 모델은 구조의 복잡성 때문에 속도가 느리다는 문제가 있지만 TLB가 이 문제를 상당 부분 해소해준다는 특징이 있다. 아래는 깃북에 나온 가상 메모리 주소 영역별 역할에 대한 설명이다. (아직 코드를 통해서 기술적으로 다뤄보지 않았기 때문에 깊이 있는 이해가 더해지면 내용을 추가로 업데이트할 계획이다.)

1. Sign Extend (상위 16비트):

x86-64는 실제로 48비트 가상 주소만 사용한다. (전체 64비트 주소 공간(16EB)을 사용하는 것은 비현실적으로 큼)

따라서 나머지 상위 16비트(63~48)는 48번째 비트(Sign Bit)를 복사해 채운다. (canonical address) 즉, 상위 16비트는 주소 번역에는 참여하지 않고, 단지 CPU가 유효한 주소인지 확인하는 용도.

2. Page-Map Level-4 Offset (PML4 index, 9비트):

최상위 페이지 테이블(PML4)을 인덱싱하는 값 (0~511) CPU가 CR3 레지스터에 저장된 PML4 물리 주소를 가져와, 이 9비트로 PML4 엔트리(512개 중 하나)를 선택함 PML4 엔트리는 PDPT(Page Directory Pointer Table)의 물리 주소를 가리킴 즉, 다음 단계의 테이블을 가리키는 포인터

3. Page-Directory Pointer Offset (PDPT index, 9비트):

PML4가 가리킨 PDPT에서 512개 엔트리 중 하나를 고름 PDPT 엔트리는 PD(Page Directory)의 물리 주소를 가리킴

4. Page-Directory Offset (PD index, 9비트):

PDPT에서 선택된 PD에서 512개 중 하나를 찾음 PD 엔트리는 PT(Page Table)의 물리 주소를 가리킴

5. Page-Table Offset (PT index, 9비트):

PT(페이지 테이블)에서 512개 중 하나의 PTE(Page Table Entry)를 찾음 PTE는 페이지가 매핑된 물리 프레임의 주소 + 플래그들(r/w, user, present…)

예시
PFN: 0x12345
Flags: RW=1, USER=1, PRESENT=1

6. Physical Offset (Page Offset, 12비트):

페이지(4KB) 내부에서의 오프셋 (페이지 크기가 2^12 = 4096 byte이기 때문에 12비트)

디스크 파일의 내용을 가상 메모리 주소 공간에 직접 연결(mmap) 하는 방식. 즉, 파일의 데이터를 read() 없이 바로 메모리처럼 접근할 수 있게 만드는 기술이에요.

동작 원리

1. 매핑 설정

   • OS가 파일을 가상 주소 공간의 일부(=가상 페이지 집합) 에 연결만 해둠.
   • 이 시점엔 아직 RAM에 올라가지 않음.

2. 접근 시 (on-demand load)

   • 프로그램이 해당 주소를 읽으면 페이지 폴트 발생
   • OS가 디스크에서 해당 부분을 읽어 물리 메모리(RAM) 에 올림.

3. 미사용 시 (swap-out)

   • 오래 사용하지 않거나 메모리 부족 시 OS가 해당 페이지를 다시 디스크로 내림.

관련 개념 정리

세그먼트와 권한의 관계

실행 파일은 실제로는 세그먼트(LOAD 단위) 로 메모리에 매핑됩니다. 즉, 섹션은 세그먼트 내부에 포함되는 구조예요.

➡️ 즉, 권한이 같은 섹션들만 같은 세그먼트(=페이지 영역) 에 묶입니다. 권한이 다르면 세그먼트가 분리되고, 페이지도 분리됩니다.

페이지 배치 규칙

예시 1

페이지 크기 = 4KB .rodata = 1KB (r--) .data = 2KB (rw-)

➡️ 메모리 배치 결과:

[Page 1]
| .rodata (1KB) | [padding 3KB] |  ← 권한: r--
[Page 2]
| .data (2KB)   | [padding 2KB] |  ← 권한: rw-

서로 다른 권한 → 반드시 다른 페이지 사용 (남는 공간은 패딩 처리) 만약 권한이 같고 두 섹션의 크기 합이 페이지 크기보다 작거나 같다면 같은 페이지로 들어갈 수 있다.

• 컴파일 + 링크 결과물로 만들어진 하나의 파일이에요.
• 디스크(SSD/HDD) 위에만 존재하고, 아직 “실행 중”은 아닙니다.
• 안에는 코드(.text), 데이터(.data), 전역 변수(.bss) 등이 들어 있어요.

👉 즉, “프로그램의 설계도” 같은 존재예요.

이 파일을 실행하면 어떤 동작이 일어날까?

1. 운영체제(OS) 가 새로운 프로세스(process) 를 만듭니다.
2. 그 프로세스에 독립된 가상 메모리 공간을 만들어줘요.
3. 실행 파일의 각 부분을 이 가상 공간에 매핑(mapping) 합니다.

이때 아직 메모리에 다 올라간 건 아닙니다❗️ (이건 "가상의 주소만 연결해둔 상태"예요.)

그럼 언제 메모리에 올라갈까?

프로그램이 실행되면서 CPU가 어떤 코드나 데이터를 처음 사용할 때, 그 부분만 디스크에서 RAM으로 조금씩 불러옵니다.

이걸 “온디맨드(on-demand) 로딩” 또는 “페이지 단위 캐싱”이라고 합니다.

(컴파일러 드라이버는 .c 파일 이름을 내부적으로 .o 파일로 변환하여 링커에 전달한다.)

이 과정에서 링커는 세 개의 집합을 유지한다:

• E: 실행 파일에 포함될 재배치 가능한 오브젝트 파일들의 집합
• U: 아직 정의되지 않은, 즉 해결되지 않은 심볼들의 집합
• D: 이미 정의된 심볼들의 집합

초기에는 E, U, D 모두 비어 있다.

링커의 동작 알고리즘

1. 명령줄의 각 입력 파일 f에 대해, 링커는 f가 오브젝트 파일인지 아카이브(라이브러리)인지 확인한다.

   • 만약 f가 오브젝트 파일이면: 링커는 f를 E에 추가하고, f의 심볼 정의 및 참조 정보를 기반으로 U와 D를 갱신한 뒤, 다음 입력 파일로 넘어간다.

2. 만약 f가 라이브러리(archive) 라면: 링커는 U에 있는 아직 해결되지 않은 심볼들이 라이브러리 안의 어떤 멤버 오브젝트 파일의 정의와 일치하는지 검사한다.

   • 만약 어떤 멤버 m이 U에 있는 심볼을 해결한다면, 링커는 m을 E에 추가하고, U와 D를 갱신한다.

   이 과정은 U와 D가 더 이상 변하지 않을 때까지 반복된다. 그 이후, 참조되지 않은 나머지 멤버 오브젝트 파일들은 무시된다.

3. 링커가 명령줄의 모든 입력 파일을 처리한 뒤에도 U가 비어 있지 않으면, 링커는 오류 메시지를 출력하고 종료한다.

   반대로, 모든 참조가 해결되면 E 안의 오브젝트 파일들을 병합하고 재배치하여 최종 실행 파일을 만든다.

⚠️ 명령줄 순서의 중요성

이 알고리즘의 단점은, 명령줄에 나열된 파일의 순서가 매우 중요하다는 것이다.

만약 어떤 라이브러리가 자신이 필요한 오브젝트 파일보다 앞에 위치한다면, 그 라이브러리의 심볼 정의는 무시되고 참조가 해결되지 않은 채로 남는다.

예시

linux> gcc -static ./libvector.a main2.c
/tmp/cc9XH6Rp.o: In function ‘main’:
/tmp/cc9XH6Rp.o(.text+0x18): undefined reference to ‘addvec’

무슨 일이 일어난 걸까?

• 링커가 libvector.a를 처리할 때는 아직 main2.c가 처리되지 않았기 때문에 U 집합이 비어 있음 → addvec 참조가 존재하지 않음.
• 따라서 libvector.a의 어떤 오브젝트 파일도 E에 추가되지 않음.
• 이후 main2.c를 처리할 때 addvec 참조가 생기지만, 이미 libvector.a는 지나간 상태라 링커는 이를 해결하지 못함.

→ 결과적으로 undefined reference to 'addvec' 오류가 발생한다.

✅ 올바른 순서

라이브러리는 명령줄의 끝에 위치해야 한다. 이렇게 하면 링커가 모든 오브젝트 파일의 참조를 먼저 수집한 뒤, 그 참조를 해결하기 위해 라이브러리를 뒤에서부터 읽을 수 있다.

여러 라이브러리의 순서

linux> gcc foo.c libx.a libz.a liby.a

만약 foo.c가 libx.a와 libz.a의 함수를 호출하고, 이 두 라이브러리가 또 liby.a의 함수를 호출한다면, libx.a와 libz.a는 반드시 liby.a 앞에 있어야 한다.

그렇지 않으면, liby.a에서 정의된 심볼을 찾지 못하게 된다.

반복 사용 (라이브러리 재참조)

필요하다면 명령줄에서 같은 라이브러리를 여러 번 명시할 수도 있다.

예를 들어:

linux> gcc foo.c libx.a liby.a libx.a

이 경우,

• foo.c가 libx.a의 함수를 호출하고,
• libx.a가 liby.a의 함수를 호출하며,
• 다시 liby.a가 libx.a의 함수를 호출하는 경우에도 모든 참조가 올바르게 해결된다.

대안적 방법

두 라이브러리(libx.a, liby.a)가 서로를 참조하는 경우라면, 두 라이브러리를 하나의 아카이브로 합치는 것도 좋은 해결책이 될 수 있다.

/* foo4.c */
#include <stdio.h>
void f(void);

int x;  // weak

int main()
{
    x = 15213;
    f();
    printf("x = %d\n", x);
    return 0;
}

/* bar4.c */
int x;  // weak

void f()
{
    x = 15212;
}

이 경우 링커는 (규칙 3에 따라) 두 weak 심볼 중 하나를 임의로 선택한다. → 결과는 예측 불가능할 수 있으며, 버그를 유발할 수 있다.

타입 불일치에 의한 메모리 덮어쓰기

/* foo5.c */
#include <stdio.h>
void f(void);

int y = 15212;
int x = 15213;

int main()
{
    f();
    printf("x = 0x%x y = 0x%x\n", x, y);
    return 0;
}

/* bar5.c */
double x;

void f()
{
    x = -0.0;
}

세부 동작 (타입 불일치에 의한 메모리 덮어쓰기)

x86-64 리눅스에서:

• double은 8바이트
• int는 4바이트

주소 배치:

x = 0x601020
y = 0x601024

x = -0.0은 double 값이므로 그 8바이트가 x와 y의 메모리 공간을 모두 덮어쓴다.

결과:

linux> gcc -Wall -Og -o foobar5 foo5.c bar5.c
/usr/bin/ld: Warning: alignment 4 of symbol ‘x’ ... is smaller than 8
linux> ./foobar5
x = 0x0 y = 0x80000000

→ x는 0으로, y는 double 음수 0의 하위 비트가 덮여 0x80000000이 됨.

⚠️ 이런 버그의 위험성

이런 오류는 링커가 오류가 아닌 경고만 출력하기 때문에 발견이 어렵고, 나중에 프로그램 실행 중 전혀 엉뚱한 시점에 나타날 수 있다.

대규모 시스템에서는 이런 종류의 버그를 찾기가 매우 어렵다. 대부분의 프로그래머는 링커 동작에 익숙하지 않아 경고를 무시하기 때문이다.

💡 팁: GCC 옵션 -fno-common을 사용하면 중복 전역 심볼 정의 시 오류를 발생시킨다. 또는 -Werror 옵션으로 모든 경고를 오류로 취급할 수도 있다.

예시: 정수 데이터 저장

예를 들어 다음과 같은 코드가 있다고 해봅시다:

int x = 0x11223344;

이 변수의 초기값은 ELF의 .data 섹션에 그대로 저장됩니다.

즉, 타입 정보 없이 순수한 바이트 나열입니다.

심볼 테이블의 역할

이렇게 단순히 저장된 데이터는 링킹(linking) 과정에서 심볼 테이블(Symbol Table) 의 도움을 받아 의미를 얻게 됩니다.

즉, .data 섹션의 “의미 없는 바이트 덩어리”들은 심볼 테이블을 통해 “이 바이트들이 변수 x의 값이다”라는 의미를 얻게 되는 거예요.

요약

ELF의 .data 섹션은 단순히 초기화된 전역/정적 변수의 값들의 바이트 배열 을 담는 공간이며, 데이터의 이름, 타입, 크기 등의 의미는 심볼 테이블을 통해 해석된다.

1. ELF 헤더 (ELF Header)

• 역할: 파일의 맨 앞에 위치하며, ELF 파일 전체를 이해하기 위한 가장 기본적인 정보를 제공합니다. 파일의 '신분증'과 같습니다.
• 포함 정보: 파일의 종류(재배치 가능, 실행 가능 등), 대상 CPU 아키텍처, 엔디안(바이트 순서), 섹션 헤더 테이블과 프로그램 헤더 테이블이 파일 내에서 시작하는 위치(오프셋) 및 크기 등.

2. 섹션 데이터 (Section Data)

• 역할: 프로그램의 실제 내용물이 들어 있는 부분입니다.
• 구성: .text (코드), .data (초기화된 데이터), .rodata (읽기 전용 데이터) 등 앞서 설명된 모든 섹션의 실제 바이트 데이터가 저장됩니다.

3. 메타데이터 테이블 (Metadata Tables)

ELF 파일은 데이터를 해석하는 데 필요한 두 가지 중요한 테이블을 포함합니다.

• 섹션 헤더 테이블 (Section Header Table): 섹션 데이터 영역에 있는 각 섹션의 상세한 정보 (이름, 타입, 크기, 파일 오프셋, 메모리 주소 등)를 담고 있는 목록입니다. 링커가 파일을 처리할 때 주로 사용합니다.
• 프로그램 헤더 테이블 (Program Header Table): (주로 실행 파일에서 중요) 파일이 메모리에 로드될 때 어떻게 로드되어야 하는지를 설명합니다. 파일의 연속된 섹션들을 묶어 세그먼트(Segment)라는 단위로 메모리 매핑 정보를 제공합니다. 로더(Loader)가 파일을 메모리에 올릴 때 주로 사용합니다.

따라서 ELF 파일은 헤더를 통해 파일의 시작점을 알리고, 테이블을 통해 파일의 구조와 로딩 방법을 정의하며, 데이터에 실제 프로그램을 담는 구조를 가집니다.

• 역할: 소스 코드를 컴파일러가 처리하기 쉬운 형태로 텍스트 치환 및 확장합니다.
• 결과: #include <stdio.h>와 같은 지시문을 만나면, stdio.h와 같은 헤더 파일의 내용이 메인 소스 파일에 복사되어 들어옵니다.
• 포함되는 내용: 이 헤더 파일에는 주로 printf와 같은 함수의 선언 (Declaration), 즉 함수의 이름, 반환 타입, 매개변수 정보만 포함되어 있습니다. 함수의 실제 구현 코드(바디)는 포함되어 있지 않습니다.

2. 컴파일 단계 (Compiler: 목적 파일 생성)

• 역할: 확장된 소스 코드를 읽어 기계어 코드로 번역하고 목적 파일(.o)을 생성합니다.
• 처리: 컴파일러는 printf() 호출을 만나면, 선언을 통해 그 형태가 유효함을 확인하고, 이 함수가 "외부 어딘가에 정의되어 있다"는 심볼(Symbol) 참조 정보만 목적 파일에 남깁니다.

3. 링킹 단계 (Linker: 최종 결합)

• 역할: 여러 목적 파일과 라이브러리를 하나로 결합하여 실행 파일을 만듭니다.
• 처리:
  • 링커는 목적 파일들을 검사하여 printf와 같이 정의가 없는 심볼(Undefined Symbols) 목록을 확인합니다.
  • 이 심볼들을 해결하기 위해 표준 라이브러리 파일(libc.a 또는 libc.so)을 탐색합니다.
  • 라이브러리 파일 내에 미리 컴파일된 printf 함수의 구체적인 구현체 (이진 코드)가 정의되어 있습니다.
  • 링커는 이 구현체의 주소를 사용자 코드의 printf 호출 위치와 연결(Link)해줍니다.

결론적으로:

• 프리프로세서는 선언을 붙여주고,
• 링커는 구현체를 연결해 주는 역할을 수행하는 것입니다.

따라서 링커 단계가 되어서야 프로그램이 필요로 하는 모든 코드(사용자 코드 + 시스템/라이브러리 구현체)가 하나로 합쳐져 실행 가능한 파일이 됩니다.

각 스레드는 동일한 프로세스의 문맥(context) 내에서 실행되며, 같은 코드와 전역 데이터(global data) 를 공유한다.

스레드는 오늘날 점점 더 중요한 프로그래밍 모델이 되고 있다. 특히 네트워크 서버 같은 환경에서 동시성(concurrency) 이 필요하기 때문이다.

그 이유는 다음과 같다:

• 여러 프로세스 간에 데이터를 공유하는 것보다, 여러 스레드 간에 데이터를 공유하는 것이 훨씬 쉽다.

• 스레드는 일반적으로 프로세스보다 효율적이다. (프로세스 간 전환보다 스레드 간 전환이 비용이 훨씬 적음)

• 또한, 멀티코어 프로세서 환경에서는 여러 스레드를 동시에 실행함으로써 프로그램의 실행 속도를 크게 향상시킬 수 있다.

프로세스(process) 는 “실행 중인 프로그램”을 표현하는 운영체제의 추상화(abstraction) 이다.

하나의 시스템에서는 여러 개의 프로세스가 동시에(concurrently) 실행될 수 있다. 각 프로세스는 마치 자신이 하드웨어를 독점적으로 사용하는 것처럼 보인다.

여기서 concurrently 라는 말은, 한 프로세스의 명령어들이 다른 프로세스의 명령어들과 섞여(interleaved) 실행된다는 뜻이다.

대부분의 시스템에서는 실행할 프로세스의 수가 실제 CPU의 개수보다 많기 때문에, 운영체제는 이들 사이에서 CPU를 번갈아 가며 사용하게 한다.

단일 프로세서에서의 동작

전통적인 시스템은 한 번에 하나의 프로그램만 실행할 수 있었지만, 현대의 멀티코어 프로세서(multicore processor) 는 여러 프로그램을 동시에 실행할 수 있다.

하지만 단일 CPU에서도 여러 프로세스가 동시에 실행되는 것처럼 보일 수 있다. 운영체제가 프로세스 간 전환(context switching) 을 수행하기 때문이다.

컨텍스트 스위칭 (Context Switching)

운영체제는 프로세서가 어떤 프로세스에서 다른 프로세스로 전환할 때 그 상태(state)를 저장하고 복원해야 한다. 이 상태를 컨텍스트(context) 라고 부른다.

컨텍스트에는 다음과 같은 정보가 포함된다:

• PC (Program Counter) 의 현재 값
• 레지스터 파일(Register file) 의 내용
• 주기억장치(Main memory) 의 상태

단일 CPU 시스템(단일 프로세서 시스템, uniprocessor system)에서는 한 시점에 오직 하나의 프로세스만 실제로 실행된다.

운영체제가 현재 실행 중인 프로세스를 다른 프로세스로 전환하기로 결정하면, 다음 순서로 컨텍스트 스위치(context switch) 를 수행한다:

1. 현재 프로세스의 컨텍스트를 저장한다.
2. 새 프로세스의 컨텍스트를 복원한다.
3. CPU의 제어권을 새 프로세스에 넘긴다.

이 과정을 통해 새 프로세스는 중단되었던 지점부터 정확히 다시 실행을 이어간다.

• 큰 배열이나 행렬 연산(예: 행렬 곱셈)을 수행할 때, 데이터가 캐시에 다 안 들어가면 같은 데이터를 계속 메모리에서 다시 불러와야 하죠. → 느림
• 하지만 캐시에 들어와 있는 동안 여러 번 다시 쓰면(=시간적 지역성), 성능이 크게 올라갑니다.

2. BLOCKING의 기본 아이디어

"큰 데이터를 한 번에 다루지 말고, 작은 덩어리(block)로 쪼개서 처리하자."

예시 (행렬 곱셈)

for (i = 0; i < N; i++)
  for (j = 0; j < N; j++)
    for (k = 0; k < N; k++)
      C[i][j] += A[i][k] * B[k][j];

이 코드는 단순하지만, 실제로는 캐시가 자주 미스 납니다. 왜냐하면 A, B, C가 너무 커서 한 번 읽은 데이터가 캐시에서 금방 쫓겨나기 때문이죠.

그래서 Blocking을 씁니다:

for (ii = 0; ii < N; ii += B)
  for (jj = 0; jj < N; jj += B)
    for (kk = 0; kk < N; kk += B)
      // 작은 BxB 블록끼리만 곱함
      for (i = ii; i < ii + B; i++)
        for (j = jj; j < jj + B; j++)
          for (k = kk; k < kk + B; k++)
            C[i][j] += A[i][k] * B[k][j];

이제 프로그램은:

1. A, B, C의 작은 블록 하나씩을 캐시에 불러옴
2. 그 블록 안에서 필요한 모든 연산을 끝냄
3. 다 끝나면 버리고 다음 블록으로 넘어감

이렇게 하면 같은 데이터(예: A[i][k])를 캐시에 있을 때 여러 번 사용합니다 → 시간적 지역성 향상

3. 하지만 Core i7에서는 효과가 적은 이유

본문의 마지막 문장:

“Blocking does not improve the performance of matrix multiply on the Core i7, because of its sophisticated prefetching hardware.”

• 최신 CPU는 하드웨어 프리패처(prefetcher)가 자동으로 데이터를 미리 읽습니다.
• 그래서 Blocking이 수동으로 해주는 캐시 최적화 효과가 이미 구현되어 있음 → 효과가 덜함.

즉, Blocking은 이론적으로 강력하지만, 하드웨어가 단순한 시스템(임베디드, 구형 CPU 등)에서 더 유용합니다.

캐시가 세트를 선택하고 라인을 식별하는 메커니즘은 매우 단순합니다. 그럴 수밖에 없습니다 — 하드웨어는 이 과정을 수 나노초 단위로 수행해야 하기 때문입니다. 하지만 이런 비트 조작은 인간에게 혼란스러울 수 있으므로, 구체적인 예를 통해 과정을 살펴보겠습니다.

다음과 같은 직접 매핑 캐시가 있다고 가정합시다:

(S, E, B, m) = (4, 1, 2, 4)

즉,

• 캐시는 4개의 세트(S=4) 를 가지고 있고,
• 세트당 1개의 라인(E=1),
• 블록 크기(B)=2바이트,
• 주소 크기(m)=4비트입니다. 또한, 각 워드는 1바이트라고 가정합니다 (비현실적이지만 예시 단순화를 위한 가정입니다).

주소 공간 나누기

4비트 주소 공간 전체를 나누어보면, 아래 그림(Figure 6.30)처럼 각 주소는 [Tag | Index | Offset] 비트로 구성됩니다.

흥미로운 점:

• Tag와 Index의 조합은 메모리의 각 블록을 유일하게 식별합니다. 예:

  • 블록 0은 주소 0과 1로 구성
  • 블록 1은 주소 2와 3
  • 블록 2는 주소 4와 5
  • 블록 3은 주소 6과 7
  • 블록 4는 주소 8과 9, … 이런 식으로 구성됩니다.

• 메모리 블록은 8개지만, 캐시 세트는 4개뿐이므로 여러 블록이 같은 세트에 매핑됩니다. 예:

  • 블록 0과 4 → 세트 0
  • 블록 1과 5 → 세트 1
  • 블록 2와 6 → 세트 2
  • 블록 3과 7 → 세트 3

• 같은 세트에 매핑된 블록들은 Tag 비트로 구분됩니다. 예:

  • 블록 0의 태그 = 0, 블록 4의 태그 = 1
  • 블록 1의 태그 = 0, 블록 5의 태그 = 1 등.

Figure 6.30 — 4비트 주소 공간 예시

캐시 시뮬레이션

초기 상태: 캐시는 비어 있음 (모든 valid 비트 = 0)

1️⃣ Read word at address 0

• 세트 0의 valid bit = 0 → cache miss
• 메모리에서 block 0을 읽어와 세트 0에 저장.
• m[0], m[1]이 캐시로 복사됨.

2️⃣ Read word at address 1

• 같은 블록 내 데이터 (m[1]) → cache hit
• 세트 0의 상태는 변하지 않음.

3️⃣ Read word at address 13

• 주소 13 → 세트 2 valid bit = 0 → cache miss
• 메모리에서 block 6을 가져와 세트 2에 저장.

4️⃣ Read word at address 8

• 주소 8 → 세트 0, valid=1 → 확인 필요
• 하지만 Tag(1) ≠ 기존 Tag(0) → cache miss
• 블록 4를 세트 0에 로드 (기존 block 0 교체)

5️⃣ Read word at address 0

• 다시 주소 0을 읽음 → 세트 0, 하지만 이제 태그가 다름 (현재 Tag=1, 필요 Tag=0)
• Cache miss 발생
• block 0이 다시 세트 0에 로드됨 → block 4가 교체됨

이와 같은 미스는 충돌 미스(conflict miss) 라고 부릅니다. 캐시 공간은 충분하지만, 서로 다른 블록들이 같은 세트에 매핑되어 계속 서로를 덮어쓰는 상황에서 발생합니다.