크래프톤 정글 TIL : 0807

lazyArtisan·2024년 8월 7일

TIL

정글 TIL

목록 보기

38/147

🎯 To-do List

✅ CS:APP | 8장, 9장
☑️ c++ 공부
☑️ 백준 1문제 풀기

📖 CS:APP

📝 Chapter 8 예외적인 제어흐름

8.3 시스템 콜의 에러 처리 (System Call Error Handling)

시스템 콜 : 운영 체제의 커널에서 제공하는 서비스를 사용자 프로그램이 사용할 수 있도록 하는 메커니즘

프로그램이 파일을 읽거나 씀
새로운 프로세스를 생성함
프로그램을 종료함

시스템 콜 쓸 때 오류가 발생하면 반드시 에러 체크를 해줘야되는데,
프로그래머들은 코드가 길어져서 에러 체크를 생략하는 경향이 있음.
이럴 땐 함수로 묶어주면 됨.

Unix 스타일의 에러 처리

if ((pid = fork()) < 0) {
    fprintf(stderr, "fork error: %s\n", strerror(errno));
    exit(0);
}

Linux fork 함수를 호출할 때 오류를 확인하는 코드인데, 너무 김

void unix_error(char *msg) {
    fprintf(stderr, "%s: %s\n", msg, strerror(errno));
    exit(0);
}

이렇게 함수를 정의해놓으면

if ((pid = fork()) < 0)
    unix_error("fork error");

에러 보고 함수를 짧게 줄일 수 있음

에러 처리 래퍼 (Error-Handling Wrappers)

pid_t Fork(void) {
    pid_t pid;
    if ((pid = fork()) < 0)
        unix_error("Fork error");
    return pid;
}

에러 처리 함수를 아예 통으로 만들어버릴 수도 있음

pid = Fork();

그럼 해당 함수만 호출하면 에러 체크 가능

세 가지 스타일의 에러 처리

Unix 스타일: 함수의 반환값을 통해 오류 코드와 유용한 결과를 모두 전달함. 예를 들어, wait 함수는 오류가 발생하면 -1을 반환하고, errno에 오류 코드를 설정함.
Posix 스타일: 성공(0) 또는 실패(비 0)를 반환값으로 나타내고, 유용한 결과는 참조에 의한 함수 인수로 반환함. 예를 들어, pthread_create 함수는 스레드의 ID를 첫 번째 인수로 반환함.
GAI 스타일: 성공 시 0을 반환하고, 실패 시 비 0 값을 반환함. 예를 들어, getaddrinfo 함수는 성공 시 0을 반환하고, 실패 시 오류 코드를 반환함.

8.4 프로세스의 제어 (Process Control)

운영체제와 프로그램이 프로세스를 생성하고, 종료하고, 관리하는 방법들 설명

8.4.1 프로세스 ID 얻기

각 프로세스는 고유한 프로세스 ID(PID)를 가짐.

리눅스 시스템에서
getpid 함수 : 현재 프로세스의 PID 얻을 수 있음
getppid 함수 : 부모 프로세스의 PID 얻을 수 있음

8.4.2 프로세스의 생성과 종료

프로그래머 관점에서 프로세스는 다음의 세 가지 상태 중 하나로 생각할 수 있음

실행중 : 프로세스는 CPU에서 실행하고 있거나 실행을 기다리고 있으며, 궁극적으로 커널에 의해서 스케줄될 것.
정지 : 프로세스가 정지된 상태이고 스케줄되지 않음. 프로세스는 SIGSTOP, SIGTSTP, SIGTTIN, SIGTTOU 시그널을 받게되면 그 결과로 정지하고, SIGCONT 시그널을 받으면 다시 실행 시작함.
프로세스가 영구적으로 정지됨. 세 가지 이유 중 하나로 인해 종료됨. (1) 프로세스를 종료하는 시그널을 받았을 때, (2) 메인 루틴에서 리턴할 때, (3) exit 함수를 호출할 때

fork 함수

새로운 프로세스를 생성하는 기본적인 방법은 fork 시스템 콜을 사용하는 것.
부모 프로세스는 fork 함수로 자식 프로세스를 생성할 수 있음.
새로 만들어진 자식 프로세스는 부모 프로세스의 복사본이 됨.
부모 프로세스와 자식 프로세스는 동일한 프로그램 코드를 실행하지만, 각 프로세스는 독립적인 주소 공간을 가짐. (PID도 다름)
fork는 두 번 반환됨. 부모 프로세스는 자식의 PID를 반환받고, 자식 프로세스는 0을 반환받음.

exit 함수

프로세스는 exit 함수를 호출하여 종료할 수 있음.
exit 함수는 프로세스의 종료 상태를 전달하며,
부모 프로세스는 wait 함수를 사용하여 자식 프로세스의 종료 상태를 청소할 수 있음.

8.4.3 자식 프로세스의 청소 (Reaping Child Processes)

프로세스가 종료될 때, 커널은 시스템에서 프로세스를 즉시 제거하지 않음.
프로세스는 부모가 청소할 때까지 종료된 상태로 남아있음.
이렇게 남아있는 프로세스를 좀비라고 함.

부모 프로세스가 종료할 때, 커널은 고아가 된 자식들을 init 프로세스에 입양시킴.

init 프로세스

PID가 1번
시스템 초기화 과정에서 커널에 의해 생성됨
절대 종료되지 않음
모든 프로세스의 조상임

적당히 살다가 죽는 프로세스들은 자식들을 청소 안 해도 init 프로세스가 청소해주는데,
쉘이나 서버같이 오랫동안 실행하는 프로그램들은 항상 자신의 좀비들을 소거해야 함.
좀비들이 실행되고 있지 않더라도 이들은 여전히 시스템 메모리 자원을 잡아먹기 때문임.

부모가 종료된 자식을 청소할 때 커널은 자식의 exit 상태를 부모에게 전달하고 종료된 프로세스를 없앰.

waitpid 함수

프로세스는 wait 또는 waitpid 함수를 사용하여 종료된 자식 프로세스를 청소할 수 있음.

waitpid 함수는 기본적으로 (options = 0일 때) wait set 내의 자식 프로세스 하나가 종료할 때까지
호출한 프로세스의 실행을 정지시킴.
만일 wait set 내의 프로세스가 호출 시에 이미 종료한 상태라면, waitpid는 즉시 리턴함.
어떤 경우든 waitpid 함수는 종료된 자식의 PID를 리턴함.

8.4.4 프로세스 재우기 (Putting Processes to Sleep)

sleep 함수는 지정된 시간 동안 프로세스를 정지시킴.
pause 함수는 시그널이 수신될 때까지 함수를 정지시켜놓음.

8.4.5 프로그램의 로딩과 실행 (Loading and Running Programs)

exec 함수 계열은 현재 프로세스를 새로운 프로그램으로 대체함.
execve 함수는 현재 프로그램의 문맥(context) 내에서 새로운 프로그램을 로드하고 실행함.

프로그램 vs 프로세스

프로그램

코드 + 데이터
디스크 상에 목적파일이나 주소공간에 세그먼트로 존재할 수 있음
항상 어떤 프로세스의 문맥 내에서 돌아감

프로세스

실행 중에 있는 프로그램의 특정 사례

프로그램이 클래스면 프로세스는 인스턴스라고 비유할 수 있을듯?

8.5 시그널

시그널

시스템에서 특정 이벤트가 발생했음을 프로세스에 알리는 작은 메시지
리눅스 시스템은 총 30개의 다양한 시그널 유형을 지원함
각 시그널은 특정 시스템 이벤트와 연관되어 있으며, 기본 동작과 대응 이벤트가 지정되어 있음

8.5.1 시그널 용어

시그널의 전달

시그널 보내기 : 커널이 특정 이벤트를 감지하거나 프로세스가 kill 함수를 호출하여 다른 프로세스에 시그널을 보낼 수 있음. 커널은 시그널을 대상 프로세스의 문맥 상태를 업데이트함으로써 보냄.
시그널 받기 : 프로세스가 시그널을 받으면 커널은 해당 프로세스가 시그널에 반응하도록 강제한다. 프로세스는 시그널을 무시하거나, 종료하거나, 사용자 정의 시그널 핸들러를 실행하여 시그널을 처리할 수 있다.

보내졌지만 아직 받지 않은 시그널은 pending 시그널이라고 함.
특정 타입에 대해 동시에 여러 개의 pending 시그널이 존재할 순 없음. 한 번에 하나만 존재함.
같은 거 여러 개 발생하면 버려짐.

8.5.2 시그널 보내기

프로세스에 시그널을 보낼 때 프로세스 그룹의 개념을 사용함.

모든 프로세스는 정확히 한 개의 프로세스 그룹에 속하며, process group ID로 식별함.
getpgrp 함수는 현재 프로세스의 프로세스 그룹 ID를 리턴함.
setpgid 함수는 프로세스의 프로세스 그룹을 변경함.

/bin/kill 프로그램: 이 프로그램은 다른 프로세스에 시그널을 보냄. 예를 들어, kill -9 15213 명령은 프로세스 15213에 SIGKILL 시그널을 보냄.
키보드에서 시그널 보내기: Ctrl+C를 누르면 커널은 포그라운드 프로세스 그룹의 각 프로세스에 SIGINT 시그널을 보냄. Ctrl+Z는 SIGTSTP 시그널을 보냄.
kill 함수: 프로세스는 kill 함수를 사용하여 다른 프로세스에 시그널을 보낼 수 있음. kill(pid_t pid, int sig) 형태로 사용됨.
alarm 함수: 프로세스는 alarm 함수를 호출하여 자신에게 SIGALRM 시그널을 보낼 수 있음.

8.5.3 시그널 받기

커널이 프로세스를 커널 모드에서 사용자 모드로 전환할 때, (시스템 콜에서 리턴하거나 문맥 전환을 끝마치거나 할 때) 커널은 프로세스의 block되지 않은 pending 시그널의 집합을 체크함. 집합이 비어있으면 다음 명령으로 제어가 전달되지만, 비어 있지 않으면 커널은 시그널을 강제로 받게 함. 시그널을 수신하면 프로세스는 특정한 동작을 수행한 뒤 다음 명령어로 진행함.

각 시그널 타입의 기본 동작 예시

프로세스가 종료함
프로세스를 종료하고 코어를 덤프함
프로세스가 SIGCONT 시그널에 의해 재시작될 때까지 정지함
프로세스가 시그널을 무시함

코어 덤프 : 컴퓨터 프로그램이 비정상적으로 종료될 때, 프로세스의 메모리 상태를 파일로 저장하는 것. 이를 통해 개발자는 프로그램이 왜 비정상 종료됐는지 분석할 수 있음

8.5.4 시그널 블록하기와 블록 해제하기

프로세스는 특정 시그널의 수신을 차단할 수 있음. 시그널이 차단되면, 해당 시그널이 대기 상태로 남아 있다가 프로세스가 시그널 차단을 해제할 때까지 수신되지 않음. 커널은 각 프로세스에 대해 대기 중인 시그널 집합과 차단된 시그널 집합을 유지 관리함.

리눅스는 시그널을 차단하기 위해 묵시적인 방법과 명시적인 방법을 제공함.

묵시적 블록 방법 : 기본적으로, 커널은 핸들러에 의해 처리되고 있는 유형의 모든 대기 시그널들의 처리를 막음.
명시적 블록 방법 : 응용 프로그램들은 sigprocmask 함수와 이들의 도움함수를 이용해서 시그널들을 명시적으로 블록하거나 블록 해제할 수 있음

8.5.5 시그널 핸들러 작성하기

핸들러가 어려운 이유

핸들러는 메인 프로그램과 동시적으로 돌아가고, 같은 전역변수를 공유함. 그래서 메인 프로그램이나 다른 핸들러들과 뒤섞일 수 있음.
어떻게 그리고 언제 시그널들이 수신될 수 있는지는 종종 직관적이지 않음.
시스템이 다르면 시그널 처리 방식도 다름.

그래서 핸들러는 안전하게 작성해야 함.
핸들러 기본 작성 지침은 다음과 같음.

핸들러를 가능한 한 간단하게 유지 : 그냥 전역 플래그 한 개를 설정하고 즉시 리턴해도 됨.
비동기-시그널-안전 함수만 호출 : p.738에 정리돼있음. 시그널이 발생하는 동안 호출되더라도 안전하게 동작하는 함수들임. 시그널 핸들러는 언제든지 실행될 수 있기 때문에, 재진입 문제(reentrancy issue)가 발생할 수 있음. 시그널 핸들러가 실행되는 동안 다른 함수가 동일한 자원에 접근하면 오류가 발생할 수 있기 때문임. 비동기-시그널-안전 함수 쓰면 이런 문제 방지 가능.
errno를 저장하고 복원 : 많은 리눅스 비동기-시그널-안전 함수들은 에러를 갖고 리턴할 때 errno를 설정함. 이런 함수들을 핸들러 내에서 호출하면 errno에 의존하는 프로그램 내의 다른 부분들과 혼선이 생길 수 있음. 핸들러 진입 전에 errno를 지역 변수에 저장해놨다가 리턴하기 전에 복원하면 해결됨.
모든 시그널을 차단하여 공유 데이터 구조에 접근 : 시그널 핸들러가 실행되는 동안 다른 시그널이 발생하면 공유 데이터 구조를 안전하게 접근하는 데 문제가 생길 수 있음. 이를 방지하기 위해 시그널 핸들러가 실행되는 동안 모든 시그널을 차단할 수 있음. 이는 시그널 핸들러가 실행되는 동안 다른 시그널이 발생하지 않도록 하여 공유 데이터 구조를 안전하게 보호하는 방법임.
전역 변수를 volatile로 선언 : C 언어에서 volatile 키워드는 컴파일러에게 해당 변수의 값을 최적화하지 말고 항상 메모리에서 읽고 쓰도록 지시함. 이는 시그널 핸들러와 같이 비동기적으로 변경될 수 있는 변수에 유용함. 시그널 핸들러는 프로그램의 다른 부분과는 독립적으로 실행될 수 있기 때문에, 컴파일러는 volatile로 선언된 변수를 매번 메모리에서 읽도록 해야 함.
플래그를 sig_atomic_t로 선언 : sig_atomic_t는 시그널 핸들러와 프로그램의 다른 부분 간에 원자적으로 접근할 수 있는 변수를 선언할 때 사용하는 데이터 타입임. 이는 시그널 핸들러가 해당 변수를 변경하는 동안 프로그램의 다른 부분에서 중간 상태를 볼 수 없도록 보장함. 즉, 변수의 읽기와 쓰기가 중단되지 않고 한 번에 완료됨.

원자적 접근 : 특정 연산이 다른 연산으로부터 중단되지 않고 한 번에 완료된다는 것

정확한 시그널 처리

pending 비트 벡터는 각 시그널 유형에 대해 정확히 한 개의 비트만을 포함하기 때문에 어떤 특정 유형의 대기 시그널은 최대 한 개만 존재할 수 있다. 즉, 보냈는데 버려지는 시그널이 생긴다는 뜻. 이렇게 되면 좀비 프로세스가 남을 가능성이 생긴다. 특히 SIGCHLD 시그널이 제대로 처리되지 않으면 좀비 프로세스가 남게 된다.

해결 방법들

시그널 핸들러에서 wait 또는 waitpid 사용
시그널 핸들러에서 SIGCHLD 시그널을 수신할 때 자식 프로세스의 종료 상태를 수집함. waitpid를 루프에서 호출하여 모든 종료된 자식 프로세스의 상태를 수집할 수 있음.
SIGCHLD 시그널을 무시
SIGCHLD 시그널을 무시하도록 설정하면 자식 프로세스가 종료될 때 자동으로 그 종료 상태가 커널에 의해 수집되어 좀비 프로세스가 남지 않음. 하지만 자식 프로세스의 종료 상태를 부모가 확인할 수 없게 됨.
waitpid를 사용하는 부모 프로세스
부모 프로세스가 주기적으로 waitpid를 호출하여 종료된 자식 프로세스의 상태를 수집함. 이를 통해 시그널이 누락되더라도 좀비 프로세스를 수집할 수 있음.

8.5.6 치명적인 동시성 버그를 피하기 위해서 흐름을 동기화하기 (Synchronizing Flows to Avoid Nasty Concurrency Bugs)

동시적으로 실행되는 여러 흐름이 동일한 저장 위치를 읽고 쓰는 문제는 매우 복잡함.
이를 해결하기 위해 흐름을 동기화하여 올바른 결과를 생성하도록 해야함.

고전적인 동기화 에러 : race

부모가 fork 함수를 실행하고, 자식이 부모 대신 실행됨
부모가 깨어나기 전에 자식이 종료됨. SIGCHLD 시그널을 보냄.
커널이 SIGCHLD를 발견하고 부모의 시그널 핸들러를 실행함. (부모는 실행되기 전임)
시그널 핸들러는 종료된 자식을 청소해야 하지만, 부모가 자식을 리스트에 아직 추가를 안 해서 아무 일도 안 일어남.
부모가 깨어나서 존재하지도 않는 자식을 작업 리스트에 추가함.

해결책 : fork 호출이 리턴할 때 커널이 자식 대신 부모를 실행하도록 스케줄하면,
부모는 자식이 종료하고 시그널 핸들러가 청소 작업을 하기 전에 자식을 작업 리스트에 추가할 것.

8.5.7 명시적으로 시그널 대기하기

종종 메인 프로그램은 특정 시그널 핸들러가 동작하기를 명시적으로 기다려야 할 필요가 있음.
예를 들어, 리눅스 쉘이 전면 작업을 생성할 때, 커널은 전면 작업이 종료되고 최종적으로 삭제될 때까지 기다려야 됨.
while문으로 pid 계속 기다리는 건 프로세서 자원 너무 낭비함. 중간에 sleep 넣더라도 얼마나 자야 하는지 결정하는게 곤란함.
(전면 작업 : 쉘 환경에서 실행되는 프로세스 중 사용자가 직접 상호작용하는 작업)

pause 함수 : 시그널이 도착할 때까지 프로세스를 중단시킴
sigwait 함수 : 주어진 시그널 집합 중 하나가 발생할 때까지 기다림
sigsuspend 함수 : 시그널이 도착할 때까지 시그널 마스크를 변경하여 대기
시그널 마스크 : 현재 프로세스가 수신할 수 있는 시그널의 집합을 나타내는 비트 벡터. 프로세스는 이 마스크를 사용하여 특정 시그널을 차단하거나 허용할 수 있음.

8.6 비지역성 점프

비지역성 점프는 현재 실행 중인 함수의 컨텍스트를 벗어나서, 호출 스택의 상위에 있는 다른 함수로 제어를 직접 이동시키는 메커니즘임. 이는 C 언어의 표준 라이브러리에서 제공하는 setjmp와 longjmp 함수로 구현됨.

setjmp: 현재 함수의 실행 상태를 저장
longjmp: 이전에 setjmp에 의해 저장된 실행 상태로 제어를 이동시킴

용도

오류 처리: 여러 함수 호출이 중첩된 깊은 호출 스택에서 오류가 발생했을 때, 비지역성 점프를 사용하여 상위 함수로 제어를 빠르게 이동시킬 수 있음. 이는 특히 리소스 할당과 해제를 관리해야 하는 상황에서 유용함.
복잡한 제어 흐름: 비지역성 점프를 사용하면 복잡한 제어 흐름을 단순화할 수 있음. 예를 들어, 특정 조건이 충족되면 즉시 함수의 실행을 중단하고 상위 함수로 돌아가야 하는 경우에 사용할 수 있음.

8.7 프로세스 조작을 위한 도구

리눅스 시스템은 프로세스를 관찰하고 조작하기 위한 여러 가지 유용한 도구를 제공함.

STRACE : 돌고 있는 프로그램과 자식들이 호출한 각 시스템 콜의 경로를 인쇄함.
PS : 현재 시스템 내의 프로세스들(좀비 포함)을 출력
TOP : 현재 프로세스의 자원 사용에 관한 정보를 출력
PMAP : 프로세스의 메모리 맵을 보여줌
/proc : 여러 가지 커널 자료구조의 내용을 사용자 프로그램이 읽을 수 있는 ASCII 문자 형태로 내보내는 가상 파일 시스템.

📝 Chapter 9 가상메모리

참고한 블로그

가상 메모리 매커니즘

(1) 메인 메모리를 디스크에 저장된 주소공간에 대한 캐시로 취급해서 메인 메모리 내 활성화 영역만 유지하고, 데이터를 디스크와 메모리 간에 필요에 따라 전송하는 방법으로 메인 메모리를 효율적으로 사용
(2) 각 프로세스에 통일된 주소공간을 제공함으로써 메모리 관리를 단순화
(3) 각 프로세스의 주소공간을 다른 프로세스에 의한 손상으로부터 보호

가상메모리를 이해해야 하는 이유

가상메모리는 중요함 : 가상메모리는 컴퓨터의 모든 수준의 시스템에 스며들어 있음. 가상메모리를 이해하면 어떻게 시스템이 동작하는지 이해할 수 있음.
가상메모리는 강력함 : 가상메모리는 응용에 메모리 블록 생성, 제거, 디스크 파일에 메모리 블럭 매핑, 다른 프로세스들과 메모리 공유 등 강력한 기능을 제공함. 메모리 위치에서 읽고 쓰는 것으로 디스크 파일의 내용을 수정하거나 읽을 수도 있음.
가상메모리는 위험함 : 변수 참조, 포인터 역참조 등 할 때마다 가상메모리와 상호작용함. 이런거 잘못하면 메모리 관련 버그 나거나, 심지어는 잘못된 결과로 프로그램이 끝까지 실행될 수 있음.

9.1 물리 및 가상주소 방식 (Physical and Virtual Addressing)

물리 주소 : 실제 하드웨어 메모리의 특정 위치를 나타내는 주소
가상 주소 : 프로세스가 사용하는 주소 공간
주소 변환 : 가상 주소를 물리 주소로 변환. MMU(Memory Management Unit)라는 하드웨어 컴포턴트에 의해 변환됨.
페이지 테이블 : 가상 주소를 물리 주소로 매핑하는 데 사용되는 데이터 구조
페이지 결함 : 페이지 테이블 탐색 중에 유효 비트가 설정되지 않음. 해당 가상 페이지가 현재 물리 메모리에 없음을 의미.

9.3 캐싱 도구로서의 VM (VM as a Tool for Caching)

가상메모리는 디스크에 저장된 N개의 바이트 크기의 셀 배열로 구성됨.
각 바이트는 특정한 가상주소를 가지며, 배열의 인덱스로 작용함.
디스크 안의 배열 정보는 메인 메모리에 캐시됨.

9.3.1 DRAM 캐시의 구성

캐시 미스 (cache miss) : 요청된 데이터가 캐시에 존재하지 않아 더 상위 수준의 메모리에서 데이터를 가져와야 하는 상황

미스 페널티 (Miss Penalty) : 캐시 미스가 발생했을 때 데이터를 상위 수준의 메모리(즉, 더 느리고 더 큰 메모리)로부터 가져오는 데 소요되는 추가 시간 또는 지연

캐시 미스 종류

일차 캐시 미스(First-level Cache Miss): CPU의 일차 캐시(L1 캐시)에서 요청한 데이터를 찾을 수 없는 경우
이차 캐시 미스(Second-level Cache Miss): L1 캐시에서 데이터를 찾지 못해 L2 캐시를 참조했지만, L2 캐시에도 데이터가 없는 경우
메모리 미스(Memory Miss): L2 캐시에도 데이터가 없는 경우 메인 메모리(DRAM)를 참조해야 하는 경우

미스 페널티 구성 요소

메모리 접근 시간: 요청한 데이터를 상위 메모리(예: 메인 메모리, 디스크)로부터 가져오는 데 필요한 시간
전송 시간: 데이터를 상위 메모리로부터 캐시로 전송하는 데 걸리는 시간
캐시 업데이트 시간: 가져온 데이터를 캐시에 저장하고, 필요한 경우 기존 데이터를 무효화하는 데 걸리는 시간

가상 메모리는 디스크에 저장되는 N개의 연속적인 바이트들로 이뤄진 배열을 의미하며, 해당 바이트 배열의 일부는 메인 메모리(DRAM 캐시)에 캐시됨.
캐시 메모리가 메인 메모리의 캐시로 사용된다면, 메인 메모리는 디스크의 캐시로 사용됨.
캐시 메모리와 DRAM의 관계에서 블록(Block)이라는 단위를 사용하듯이, 메인 메모리와 디스크의 관계에서는 페이지(Page)라는 단위를 사용함.

가상 페이지(Virtual Page) : 디스크에 위치하는 가상 주소 공간(Virtual Address Space)의 각 페이지
물리 페이지(Physical Page) : 메인 메모리에 위치하는 물리 주소 공간(Physical Address Space)의 각 페이지

DRAM 캐시(= 디스크의 캐시)는 캐시 메모리(= 메인 메모리의 캐시)에 비해 Miss Penalty가 매우 큼.
DRAM과 SRAM의 속도 차이는 10배 정도인 반면, 디스크와 DRAM의 속도 차이는 거의 10,000배에 이르기 때문.

정리
1. 가상 메모리 매커니즘에 캐시가 필요함
2. 그 캐시는 디스크에서 메인 메모리로 저장됨
3. 그래서 가상메모리는 미스 페널티가 크다

9.3.2 페이지 테이블

(8개의 가상 페이지와 4개의 물리 페이지를 갖는 시스템을 위한 페이지 테이블 예시)

페이지 테이블

가상 주소를 물리 주소로 변환하는 데 사용되는 데이터 구조
가상 페이지와 물리 페이지 사이의 맵핑 정보가 담김
메인 메모리의 커널 영역에 저장되는 자료 구조
각 프로세스마다 존재함. 문맥 전환을 수행할 때 저장하는 문맥 정보에도 페이지 테이블이 포함됨.
페이지 테이블 엔트리(PTE)의 배열

페이지 테이블 엔트리(PTE)에 담기는 정보

유효 비트(Valid Bit): 해당 페이지가 유효한지 여부
프레임 번호(Frame Number): 가상 페이지가 매핑된 물리 페이지 프레임의 번호
접근 권한 비트(Access Permission Bits): 페이지에 대한 읽기, 쓰기, 실행 권한을 제어함
사용 비트(Usage Bit): 페이지의 최근 사용 여부를 나타내어 페이지 교체 알고리즘에 사용됨
가상 페이지가 물리 페이지에 매핑되어 있지 않다면 디스크의 어느 위치에 존재하는지에 대한 정보

9.3.3 페이지 적중

접근하고자 하는 가상 주소에 해당하는 PTE의 Valid 비트가 1이면, 해당 가상 페이지가 물리 페이지에 맵핑되어 있음을 의미한다. 이를 페이지 적중(Page Hit) 또는 DRAM 캐시 적중이라고 부른다.

9.3.4 페이지 폴트 (page fault)

페이지 폴트 : 요청된 가상 페이지가 물리 메모리에 없는 경우

페이지 폴트가 발생하면
1. 운영 체제가 페이지 폴트 처리하기 위해 제어를 넘겨받은 후
2. 디스크에서 요청된 페이지를 찾아서 물리 메모리로 로드함
3. 페이지 테이블 업데이트해서 새로운 페이지 프레임 번호랑 유효 비트 설정
4. 페이지 폴트를 발생시킨 명령어를 재실행

9.3.5 페이지의 할당

malloc같은 걸로 힙 영역을 새로 할당하려 할 때
커널은 가상 페이지를 디스크에 할당한 뒤
PTE를 페이지 테이블에 새로 만들어준다.

9.3.6 문제해결을 위한 또 한 번의 지역성의 등장

시간적 지역성(Temporal Locality): 최근에 접근된 데이터가 다시 접근될 가능성이 높은 것
공간적 지역성(Spatial Locality): 접근된 데이터의 근처 데이터가 곧 접근될 가능성이 높은 것

아니 디스크에서 꺼내오는 거면 비효율적인거 아님?
-> 아님. 어차피 쓰는게 그게 그거라 괜찮음. 유식하게 말하면 지역성이 있음.
근데 사용하는게 물리 메모리보다 크거나 페이지 폴트가 너무 자주 발생하면
계속 디스크에서 넣었다 뺐다 해야됨.
이런 걸 쓰래싱(thrashing)이라고 함.

쓰래싱 방지 방법

적절한 페이지 교체 알고리즘 사용: LRU(Least Recently Used), FIFO(First In First Out) 등.
작업 집합 모델: 각 프로세스가 실제로 필요로 하는 페이지 집합을 메모리에 유지하도록 관리
물리 메모리 확장: 충분한 물리 메모리를 확보하여 페이지 폴트 발생을 줄임
프로세스 조정: 동시 실행 프로세스의 수를 조정하여 각 프로세스가 필요한 메모리를 충분히 할당받게 함

가상 메모리의 주요 목적

추상화와 메모리 보호:
- 각 프로세스가 자신의 독립된 메모리 공간을 가지고 있는 것처럼 보이게 하여 메모리 충돌을 방지합니다.
- 프로세스가 서로의 메모리 공간에 접근하지 못하게 하여 메모리 보호를 제공합니다.
효율적인 메모리 사용:
- 실제 물리 메모리보다 더 큰 주소 공간을 제공하여 프로세스가 더 많은 메모리를 사용하는 것처럼 보이게 합니다.
- 실제로 필요한 메모리만 물리 메모리에 로드하여 메모리를 효율적으로 사용합니다.
페이지 폴트와 디스크 I/O:
- 사용되지 않는 메모리 페이지를 디스크로 스왑 아웃(swap out)하고, 필요한 페이지를 다시 스왑 인(swap in)하여 물리 메모리의 사용을 최적화합니다.
- 페이지 폴트가 발생할 때 디스크에서 데이터를 로드하는 작업을 포함합니다.

캐싱과의 관계

가상 메모리는 기본적으로 디스크와 메모리 간의 캐싱 메커니즘입니다. 그러나 가상 메모리는 단순한 캐시 이상의 복잡한 기능을 수행합니다. 다음은 가상 메모리와 캐시의 차이점과 유사점을 나타낸 것입니다.

유사점

캐싱 메커니즘:
- 둘 다 더 빠른 접근을 위해 더 느린 저장 장치에서 데이터를 가져와 임시 저장하는 역할을 합니다.
- 페이지 테이블과 TLB(Translation Lookaside Buffer)는 가상 메모리에서의 캐시 역할을 합니다.
지역성의 활용:
- 둘 다 지역성의 원리를 활용하여 자주 사용되는 데이터를 더 빠른 저장 장치에 보관합니다.
- 시간적 지역성과 공간적 지역성을 활용하여 성능을 최적화합니다.

차이점

목적과 범위:
- 가상 메모리는 프로세스 간의 메모리 격리, 보호, 메모리 확장을 제공하는 것을 목적으로 합니다.
- 캐시는 주로 데이터 접근 속도를 높이기 위한 임시 저장 공간을 제공합니다.
관리 단위:
- 가상 메모리는 페이지 단위(보통 4KB 또는 8KB)로 메모리를 관리합니다.
- 캐시는 캐시 라인 단위(보통 64바이트)로 데이터를 관리합니다.
구현 수준:
- 가상 메모리는 운영 체제와 하드웨어(MMU)에 의해 구현됩니다.
- 캐시는 CPU 내부에서 하드웨어적으로 구현됩니다.

9.4 메모리 관리를 위한 도구로서의 가상메모리

여러 가상 페이지는 동일한 물리 페이지를 공유할 수 있음
가상 메모리와 독립된 가상 주소 공간의 조합은 시스템의 메모리 사용과 관리에 중요한 영향을 미침
가상 메모리는 링크 및 로딩, 코드 및 데이터 공유, 응용 프로그램의 메모리 할당을 단순화함

링킹 단순화 : 각 프로세스가 물리적 메모리의 실제 위치와 상관없이 동일한 기본 메모리 이미지 형식을 사용할 수 있도록 하여, 링크 및 로더의 설계와 구현을 크게 단순화함
로딩 단순화 : 실행 파일과 공유 객체 파일을 메모리에 쉽게 로드할 수 있음. 로더는 디스크에서 메모리로 데이터를 실제로 복사하지 않고, 가상 메모리 시스템이 처음 참조될 때 자동으로 데이터를 페이징함.
공유 단순화 : 운영체제는 사용자 프로세스와 운영체제 자체 간의 공유를 일관되게 관리할 수 있음. 여러 프로세스가 코드와 데이터를 공유해야 할 필요가 있음. 운영체제는 여러 프로세스가 동일한 물리 페이지를 가상 페이지로 매핑하도록 하여 이 코드를 공유할 수 있음.
메모리 할당 단순화 : 가상 메모리는 사용자 프로세스에 추가 메모리를 할당하는 간단한 메커니즘을 제공함. 사용자 프로세스가 추가 힙 공간을 요청하면, 운영체제는 적절한 수의 연속된 가상 메모리 페이지를 할당하고, 이를 물리 메모리의 임의의 물리 페이지에 매핑함. 페이지 테이블의 작동 방식 덕분에 운영체제가 연속된 물리 메모리 페이지를 찾을 필요가 없으며, 물리 메모리의 페이지들은 임의로 흩어질 수 있음.

9.5 메모리 보호를 위한 도구로서의 가상메모리

운영체제는 사용자 프로세스가 커널이나 다른 프로세스 메모리들이나 데이터들을 헤집고 다니지 않도록 제어해야 함.

가상 주소 공간을 제공하면 사적 메모리를 다른 프로세스로부터 분리하는 것이 쉬워짐. 물리적 메모리에서 프로세스 간의 메모리 충돌을 방지할 수 있음. 이로 인해 하나의 프로세스에서 발생한 오류가 다른 프로세스의 메모리에 영향을 미치지 않도록 보호할 수 있음.

주소 변환 하드웨어는 CPU가 주소를 생성할 때마다 페이지 테이블 엔트리(PTE)를 읽으므로, PTE에 추가적인 권한 비트를 추가하여 가상 페이지의 내용에 대한 접근을 제어하는 것이 간단함. 각 PTE를 읽고, SUP 비트가 설정되어 있는지를 확인하여 커널 모드인지 사용자 모드인지에 따라 접근을 제어할 수 있음.

9.6 주소의 번역

가상 메모리와 주소 번역
컴퓨터 시스템에서 가상 메모리는 물리적 메모리보다 더 큰 주소 공간을 제공하여, 물리 메모리와 가상 주소 공간 사이의 매핑을 관리함. 이 과정은 CPU가 가상 주소를 생성하고, 이를 물리 주소로 변환하여 메모리에 접근하는 방식으로 이루어짐. 이 주소 변환 작업은 CPU와 운영 체제의 협력을 필요로 함. CPU 칩의 메모리 관리 유닛(MMU)은 메모리에서 관리되는 페이지 테이블을 사용하여 가상 주소를 실시간으로 물리 주소로 번역함.

주소 공간 (Address Spaces)
주소 공간은 비음수 정수 주소의 정렬된 집합으로 정의됨. 시스템에서 가상 메모리를 사용하는 경우, CPU는 가상 주소 공간에서 가상 주소를 생성함. 가상 주소 공간은 n비트 주소 공간이라고 하며, 현대 시스템에서는 보통 32비트 또는 64비트 가상 주소 공간을 지원함. 물리 주소 공간은 시스템의 물리 메모리 바이트에 해당하며, 이를 통해 가상 메모리와 물리 메모리 간의 변환이 이루어짐.

주소 번역 속도 향상: TLB (Translation Lookaside Buffer)
CPU가 가상 주소를 생성할 때마다 MMU는 페이지 테이블 항목(PTE)을 참조하여 가상 주소를 물리 주소로 변환함. 최악의 경우, 이는 메모리에서 추가로 가져와야 하므로 수십에서 수백 사이클의 비용이 발생합니다. L1 캐시에 PTE가 캐시되어 있으면 비용이 몇 사이클로 줄어듦. 많은 시스템은 MMU에 TLB라는 작은 PTE 캐시를 포함하여 이 비용을 없애려고 함.

주소 번역 전체 과정
예시 : 가상 주소 0x03d4에서 바이트를 읽는 로드 명령
1. MMU는 가상 주소에서 가상 페이지 번호(VPN)를 추출
2. TLB에서 해당 PTE가 캐시되어 있는지 확인
3. TLB에서 적중하면 캐시된 물리 페이지 번호(PPN)을 MMU에 반환
4. 적중 안 하면 발생하면 MMU는 페이지 테이블에서 PTE를 가져옴
5. 필요한 PTE가 유효하지 않으면 페이지 폴트가 발생하고 커널이 개입하여 필요한 페이지를 메모리에 로드함

9.8 메모리 매핑

리눅스는 가상 메모리 영역의 내용을 디스크의 객체와 연관시켜 초기화하는데, 이를 메모리 매핑(memory mapping)이라고 함. 메모리 매핑을 통해 두 가지 유형의 객체를 가상 메모리 영역에 매핑할 수 있음.

1. 리눅스 파일 시스템의 일반 파일

특정 파일을 메모리에 매핑하여, 파일을 읽거나 쓸 때 파일 입출력(I/O)을 직접 사용하는 대신 메모리에 접근하듯이 접근할 수 있게 함.
가상 메모리 영역은 실행 파일과 같은 일반 디스크 파일의 연속된 섹션에 매핑될 수 있음. 파일 섹션은 페이지 크기 조각으로 나뉘어져 있으며, 각 조각은 가상 페이지의 초기 내용을 포함함. 요구 페이징 덕분에 이러한 가상 페이지는 CPU가 해당 페이지를 처음 접근할 때까지 물리적 메모리로 전환되지 않음. 영역이 파일 섹션보다 크면, 해당 영역은 0으로 채워짐.

2. 익명 파일

익명 매핑은 파일과 연관되지 않은 메모리 매핑으로, 프로세스가 요청한 메모리 영역이 실제 물리 메모리나 스왑 공간과 연결됨.
가상 메모리 영역은 커널에 의해 생성된 익명 파일에 매핑될 수도 있으며, 이 파일은 모두 0으로 채워져 있다. CPU가 이러한 영역의 가상 페이지를 처음 접근할 때, 커널은 적절한 희생 페이지를 물리 메모리에서 찾아내고, 해당 페이지가 dirty하다면 스왑 아웃하고, 희생 페이지를 0으로 덮어쓴다. 그런 다음 페이지 테이블을 업데이트하여 페이지가 존재한다고 표시한다. 이 과정에서 디스크와 메모리 간에 실제 데이터 전송은 발생하지 않으므로, 이러한 페이지는 때때로 'demand-zero pages'라고 불린다.

디스크의 객체(파일 또는 스왑 공간)와 연결하여 초기화 한다는게 뭔 소린지 이해를 못하겠는데

디스크의 객체(파일 또는 스왑 공간)와 연결하여 초기화한다는 것은 가상 메모리의 특정 영역을 디스크에 있는 파일이나 스왑 공간과 연관 지어 사용하는 것을 의미합니다. 이 과정에서 메모리 매핑을 사용하여 파일의 내용을 메모리처럼 다룰 수 있게 합니다.

리눅스는 가상 메모리 영역의 내용을 디스크의 객체와 연관시켜 초기화하는데, 이를 메모리 매핑(memory mapping)이라고 함. 메모리 매핑을 통해 두 가지 유형의 객체를 가상 메모리 영역에 매핑할 수 있음.

가 의미하는게, 가상 메모리라는게 원래 디스크에 캐싱하는거잖아? 근데 그냥 캐싱하는게 아니라 원래 디스크랑 연관된 정보도 넣어서 읽기 쓰기도 할 수 있게 한다는건가? 근데 익명 파일은 왜 필요한거지 그럼?

가상 메모리 시스템은 물리 메모리보다 큰 주소 공간을 제공하며, 각 프로세스에 독립된 메모리 공간을 할당하여 메모리 보호와 효율성을 제공합니다. 메모리 매핑은 가상 메모리 주소를 물리 메모리나 디스크 상의 객체(파일 또는 스왑 공간)에 매핑하는 방법입니다.

파일 매핑 (File-backed Mapping):
- 디스크의 파일을 가상 메모리 주소 공간에 매핑하여 파일의 내용을 메모리처럼 다루게 합니다.
- 파일 입출력을 효율적으로 처리하며, 파일의 변경 사항이 메모리에 반영됩니다.
익명 매핑 (Anonymous Mapping):
- 특정 파일과 연관되지 않은 메모리 매핑으로, 순수한 메모리 할당을 제공합니다.
- 스왑 공간을 통해 물리 메모리보다 큰 메모리 공간을 사용할 수 있습니다.
- 주로 동적 메모리 할당, 스택 및 힙 확장, IPC에서 사용됩니다.

익명 매핑은 파일과 관계없이 순수한 메모리 할당을 위한 것이며, 가상 메모리 시스템에서 메모리를 효율적으로 사용하고 보호하기 위해 중요한 역할을 합니다. 파일 매핑과 익명 매핑은 각각의 사용 목적에 맞게 활용됩니다.

"원래 디스크랑 연관된 정보도 넣어서"라는 부분은 맞게 표현한 거임?

"원래 디스크랑 연관된 정보도 넣어서"라는 표현은 가상 메모리 시스템에서 파일 매핑을 설명할 때 적절한 표현입니다. 이를 통해 디스크에 저장된 파일의 데이터를 메모리 주소 공간에 매핑하여, 파일의 내용을 직접 메모리에 접근하듯이 사용할 수 있게 됩니다. 다시 말해, 파일 매핑을 통해 디스크의 파일과 가상 메모리 주소 공간을 연관시키는 것입니다.

정확한 표현
"가상 메모리 영역을 디스크의 파일과 연관지어 초기화함": 이는 파일 매핑을 의미하며, 메모리 주소 공간의 일부를 디스크 파일의 내용으로 초기화한다는 것을 의미합니다. 이 방식으로 디스크의 파일 내용을 메모리에서 접근할 수 있습니다.

9.8.1 다시 보는 공유 객체

메모리 매핑의 아이디어는 가상 메모리 시스템이 기존 파일 시스템과 통합될 수 있다면, 프로그램과 데이터를 메모리에 로드하는 간단하고 효율적인 방법을 제공할 수 있다는 통찰에서 비롯됨.

프로세스 추상화는 각 프로세스에 대해 독립적인 가상 주소 공간을 제공하며, 이는 다른 프로세스의 잘못된 쓰기 또는 읽기로부터 보호됨.

하지만 많은 프로세스는 동일한 읽기 전용 코드 영역을 가지고 있음. 예를 들어, 각 리눅스 쉘 프로그램 bash를 실행하는 프로세스는 동일한 코드 영역을 가짐. 공통 코드의 중복 복사본을 물리적 메모리에 보관하는 것은 매우 낭비임. 메모리 매핑은 여러 프로세스가 동일한 물리적 메모리 페이지를 공유할 수 있는 매커니즘을 제공함.

9.8.2 다시 보는 fork 함수

fork 함수가 호출되면

새로운 프로세스에 PID가 할당되고
새로운 프로세스의 가상 메모리를 생성하기 위해
현재 프로세스의 mm_struct, area struct, 페이지 테이블의 정확한 복사본을 생성하고
각 페이지를 읽기 전용으로 플래그 지정하고
각 area struct를 개인적인 copy-on-write로 플래그 지정한다.

fork가 반환되면 새로운 프로세스는 fork가 호출될 당시의 가상 메모리의 정확한 복사본을 가지게 된다.

이후 어느 프로세스가 쓰기를 수행하면 copy-on-write 메커니즘이 새로운 페이지를 생성하여 각 프로세스의 독립적인 주소 공간 추상화를 유지한다.

9.8.3 다시 보는 execve 함수

프로세스에서 execve("a.out", NULL, NULL)를 호출하면,
execve 함수는 현재 프로세스 내에서 실행 파일 a.out에 포함된 프로그램을 로드하고 실행함.

이를 위해 다음 단계가 필요함.

기존 사용자 영역 삭제. 현재 프로세스의 가상주소의 사용자 부분에 있는 기존 영역 구조체들을 삭제
사적 영역 매핑. 새로운 프로그램의 코드, 데이터, bss, 스택 영역에 대해 새로운 영역 구조체 생성
공유 영역 매핑. a.out 파일의 .text와 .data 섹션에 코드와 데이터 영역을 매핑
프로그램 카운터(PC) 설정. PC를 코드 영역의 진입점으로 설정

9.8.4 함수를 이용한 사용자수준 메모리 매핑

리눅스 프로세스는 mmap 함수를 사용하여 새로운 가상 메모리 영역을 생성하고, 이러한 영역에 객체를 매핑할 수 있다.

mmap 함수는 커널에 새로운 가상 메모리 영역을 생성하고, 파일 디스크립터 fd에 의해 지정된 객체의 연속된 조각을 새로운 영역에 매핑하도록 요청한다.

mmap 함수의 인자는 새로 매핑된 가상 메모리 영역의 접근 권한과 객체 유형을 설명한다. 예를 들어, MAP_PRIVATE | MAP_ANON 플래그를 사용하여 읽기 전용의 개인적인 demand-zero 영역을 생성할 수 있다.

9.9 동적 메모리 할당

가상메모리 영역을 저수준의 mmap과 munmap 함수를 사용해서 생성하고 삭제할 수 있지만,
C 프로그래머들은 가상메모리가 더 필요할 때 동적 메모리 할당기 쓰는게 더 편하다고 생각함.
동적 메모리 할당기는 프로세스의 가상메모리 영역인 힙(heap)을 관리함.

할당기는 힙을 다양한 크기의 블록들의 집합으로 관리함.
각 블록은 할당되었거나 사용 가능한 가상메모리의 묶음임.

명시적 할당기는 C에서 malloc 같은거임. free로 블록 반환해야 됨.
묵시적 할당기는 가비지 컬렉터임. 사용하지 않은 할당된 블록을 알아서 반환시켜줌.

9.9.1 malloc과 free 함수

C 표준 라이브러리는 malloc 패키지로 알려진 명시적인 할당기를 제공함.
프로그램은 malloc 함수를 호출해서 힙으로부터 블록들을 할당받음.

malloc 함수는 size 바이트의 메모리 블록에 대한 포인터를 반환함.
이 메모리 블록은 모든 데이터 객체를 저장할 수 있도록 정렬되어 있음.
만약 할당 중 문제가 발생하면, malloc은 NULL을 반환하고 errno를 설정함.

malloc 같은 동적 메모리 할당기는 mmap와 munmap 함수, 또는 sbrk 함수를 사용해서
명시적으로 힙 메모리를 할당하거나 반환한다.

sbrk 함수는 커널의 brk 포인터에 incr을 더하여 힙을 확장하거나 축소함.
성공 시 이전 brk 값을 반환하며, 실패 시 -1을 반환하고 errno를 ENOMEM으로 설정함.

프로그램들은 free 함수를 사용하여 할당된 힙 블록을 해제함.

9.9.2 왜 동적 메모리 할당인가?

동적 메모리 할당을 사용하는 가장 중요한 이유는 프로그램이 실제로 실행될 때까지 특정 데이터 구조의 크기를 알 수 없는 경우가 많기 때문임.

9.9.3 할당기 요구사항과 목표

명시적 할당기는 몇 가지 엄격한 제약 조건 내에서 작동해야 함

임의의 요청 순서 처리하기: free에 대응되는 블럭이 있어야 한다는 제약 조건을 제외하고, 할당기는 할당과 반환 요청의 순서에 대해서 아무 가정도 할 수 없음. 크기, 순서같은 거 막 들어올 수 있음.
요청에 대한 즉각적인 응답: 메모리 할당된 블록은 특정 데이터 유형에 종속되지 않고, 어떤 유형의 데이터도 저장할 수 있어야 함.
힙만 사용: 필요에 따라 크기를 조절하기 위해 할당기가 사용하는 모든 비확장성 자료 구조는 힙에 저장되어야 함.
블록 정렬: 할당기는 모든 유형의 데이터 객체를 저장할 수 있도록 블록을 정렬해야 함.
할당된 블록 수정 금지: 할당기는 가용 블록만 조작하거나 변경할 수 있음. 일단 블록이 할당되면 수정하거나 이동할 수 없음. 따라서 할당된 블록을 압축하는 등의 기술은 허용되지 않음.

할당기 개발할 땐 이러한 제한들과 함께 처리량과 메모리 이용도를 최대화해야됨.
근데 처리량과 메모리 이용도는 서로 반비례함. 그래서 만들기 어려움.

목표 1 : 처리량 극대화하기. 일반적으로, 할당과 반환 요청들을 만족시키기 위한 평균 시간을 최소화해서 처리량을 최대화함. 할당 요청의 최악 실행 시간이 가용 블록의 수에 비례하고, 반환 요청의 실행시간이 상수인, 적당히 좋은 성능의 할당기를 만드는 건 쉬움.

목표 2 : 메모리 이용도 최대화. 잘 모르면 가상메모리가 무한 자원이라고 착각하기 쉬움. 사실 한 시스템에서 모든 프로세스에 의해 할당된 가상메모리의 양은 디스크 내의 스왑 공간의 양에 의해 제한됨. 큰 크기의 메모리 블록을 할당하고 반환할 것을 요청받는 동적 메모리 할당기의 경우 특히나 그러함.

9.9.4 단편화

가용 메모리가 할당 요청 못 만족시키는 상태

내부 단편화: 할당된 블록이 실제로 필요한 용량보다 클 때
외부 단편화: 총 메모리는 여유 있는데, 단일 여유 블록이 할당 요청을 처리할 만큼 크지 않음

9.9.5 구현 이슈

실용적인 할당기는 다음과 같은 이슈를 고려해야 함.

여유 블록 조직: 여유 블록을 어떻게 추적할 것인가?
배치: 새로 할당된 블록을 어떤 여유 블록에 배치할 것인가?
분할: 새로 할당된 블록을 여유 블록에 배치한 후 남은 여유 블록을 어떻게 처리할 것인가?
병합: 방금 해제된 블록을 어떻게 처리할 것인가?

9.9.6 묵시적 가용 리스트

할당기가 블록 경계를 구분하고 할당된 블록과 여유 블록을 구별하는 데이터 구조가 필요하다.
대부분의 할당기는 이 정보를 블록 자체에 포함시킨다.
간단하게는 블록 헤더에 블록 크기와 할당 상태를 인코딩하면 된다.

9.9.7 할당한 블록의 배치

프로그램이 k 바이트의 블록을 요청할 때 할당기는 해당 요청을 처리할만큼 큰 여유 블록을 찾는다.
할당기가 검색하는 방법은 배치 정책에 의해 결정된다.
배치 정책에는 first fit, next fit, best fit이 주로 사용된다.

First Fit: 여유 리스트의 시작부터 검색하여 맞는 첫 번째 여유 블록을 선택한다.
- 장점 : 큰 여유 블록을 리스트의 끝에 보존할 수 있다
- 단점 : 작은 여유 블록이 리스트의 시작 부분에 남아 있어 더 큰 블록을 검색하는 시간이 길어질 수 있다
Next Fit: First Fit과 유사하지만, 각 검색을 리스트의 시작이 아닌 이전 검색이 끝난 지점부터 시작한다.
- 장점 : First Fit보다 빠르게 작동할 수 있다
- 단점 : 메모리 사용률이 더 낮을 수 있다
Best Fit: 모든 여유 블록을 검사하여 맞는 가장 작은 여유 블록을 선택한다.
- 장점 : 메모리 사용률이 높다
- 단점 : 단순한 리스트 구조에서는 힙의 모든 블록을 검색해야 한다

9.9.8 가용 블록의 분할

여유 블록 찾으면 얼마나 할당할지 정해야 됨.
가용 블록 다 쓰면 내부 단편화(할당된 블록이 실제로 필요한 용량보다 큼)가 생김
크기가 안 맞으면 가용 블록을 두 개로 나눈 다음 한쪽에 할당한다.

9.9.9 추가적인 힙 메모리 획득하기

여유 블록이 없으면 일단 물리적으로 인접한 가용 블록들을 합쳐본다.
그래도 없으면 sbrk 함수로 커널에 추가 힙 메모리 요청하고 거기에 넣는다.

9.9.10 가용 블록 병합하기

할당된 블록 반환하다보면 가용 블럭들이 작게 쪼개져서 효율이 좋게 쓰기 어려워짐.
다 작아서 못 넣는걸 오류 단편화(false fragmentation)라고 함.
이땐 병합 정책에 따라 병합하면 됨.

즉시 병합: 블록이 해제될 때마다 인접한 블록을 즉시 병합합니다.
지연 병합: 나중에 병합을 수행함. 예를 들어, 할당 요청이 실패할 때까지 기다렸다가 병합을 수행함.

즉시 병합하면 간단하긴 한데 어떨 땐 블록 합쳤다가 쪼갰다가 반복하는 비효율 유발할 수도 있음

9.9.11 경계 태그를 이용한 병합

병합 구현할 때 경계 태그 쓸 수 있음.

반환 하려는 블록의 헤더가 다음 블록의 헤더를 가리키면
다음 블록이 가용한지 체크할 수 있음.

근데 다음 블록은 어딨는지 안다고 쳐도 이전 블록을 병합하려고 할 땐 어케 해야됨?
-> 경계 태그를 쓰면 됨.

경계 태그는 그냥 블록 끝에 header를 복사한 footer를 추가하는 거임.
header랑 footer랑 똑같은데 뭔 의미냐고?

여기서 n 위에 있는 m1이 없다고 해보셈.
m1이 어디까지인지 알 수 있음? 없음.
일일이 메모리 탐색하면서 어디까지 블럭이 있는지 확인해야됨.

근데 n 위에 m1이 있으면 다음 m1이 어디에 있는지 알 수 있음.
이전 블럭의 크기가 얼마인지 바로 알 수 있다는 말임.

이렇게 경계 태그를 이용하면 병합을 좀 더 빠르게 할 수 있음.
근데 header랑 footer가 필요하므로 자주 쓰는 작은 블록을 다루면 비효율 일어날 수 있음.
근데 이것마저도 하위 비트들은 footer 안 넣는 식으로 하면 해결 가능.

9.9.13 명시적 가용 리스트

묵시적 가용 리스트는 기본적인 할당기 개념을 도입하는 데는 유용하지만,
힙 블록의 총 수에 비례하여 블록 할당 시간이 선형으로 증가하므로 일반 목적의 할당기에는 적합하지 않다.
명시적 가용 리스트는 이러한 단점을 극복하기 위해 고안되었다.

명시적 가용 리스트에서는 가용 블록을 명시적 데이터 구조로 조직한다.
가용 블록의 안 쓰는 부분에 가용 블록들의 정보들을 저장한다는 뜻이다.

힙을 이중 연결 리스트로 구성한다면, 각 가용 블록에는 pred(이전 블록)와 succ(다음 블록) 포인터를 포함시킨다.
이중 연결 리스트를 사용하면 First fit 할당 시간이 힙 블록의 총 수에 비례하는 것이 아니라 가용 블록의 수에 비례하게 줄어든다. 그러나 블록 해제 시간은 블록을 해제할 때 선택한 정책에 따라 선형 시간이 될 수도 있고 상수 시간이 될 수도 있다.

가용 블록 정렬하는 주요 방법

LIFO 순서 : 새로 해제된 블록을 리스트의 시작 부분에 삽입한다. LIFO 순서와 First fit 배치 정책을 사용하면 가장 최근에 사용된 블록을 먼저 검사하게 된다. 이 경우, 블록 해제는 상수 시간에 수행될 수 있으며, 경계 태그를 사용하면 병합도 상수 시간에 수행될 수 있다.
주소 순서: 리스트에 있는 각 블록의 주소가 그 다음 블록의 주소보다 작도록 정렬한다. 이 경우, 블록을 해제하려면 적절한 이전 블록을 찾기 위해 선형 시간 검색이 필요하다. 주소 순서 First fit 배치는 LIFO 순서 First Fit 배치보다 메모리 활용도가 높아질 수 있다.

명시적 리스트의 단점은 가용 블록이 필요한 모든 포인터뿐만 아니라 헤더와 푸터를 포함할 만큼 충분히 커야 한다는 점이다. 이는 최소 블록 크기를 증가시키고 내부 단편화의 가능성을 높인다.

9.9.14 분리된 가용 리스트

분리된 가용 리스트(segregated free list)는 할당 시간을 줄이기 위한 일반적인 접근 방식이다.
단일 연결 가용 블록 리스트 쓰면 한 개의 블록을 할당하는 데 가용 블록의 수에 비례하는 시간이 필요하니까
쪼개서 저장하는 거.

간단히 분리된 저장소

다 똑같은 크기로 분리.
할당과 해제가 빠른 상수 시간 작업이지만,
가용 블록이 절대 분할되지 않으므로 내부 단편화가 발생할 수 있고,
특정 참조 패턴이 실행될 때 외부 단편화에 취약하다.

분리 맞춤

할당기가 크기 클래스와 연관된 가용 리스트 배열을 유지한다.
각 가용 리스트는 크기 클래스의 멤버인 다른 크기의 블록을 포함할 수 있다.

검색 시간이 특정 힙 부분으로 제한되므로 전체 힙을 검색할 필요가 없기 때문에 시간이 줄어든다.

버디 시스템

분리 맞춤의 특별한 경우. 각 크기 클래스가 2의 제곱이다.
블록들의 버디 주소가 한 비트 위치만 달라서 쓰는듯.
근데 내부 단편화가 심함. 특정 프로그램에선 유용할 수 있다.

9.10 가비지 컬렉션

가비지 컬렉터 : 프로그램에서 더 이상 사용하지 않는 블록들을 자동으로 반환하는 동적 저장장치 할당기

9.10.1 가비지 컬렉터 기초

가비지 컬렉터는 메모리를 도달 가능성 그래프(directed reachability graph)로 본다.
그래프의 노드는 루트 노드와 힙 노드로 나뉜다.

루트 노드는 힙이 아닌 위치를 가리키며, 힙으로의 포인터를 포함하는 위치다.
각 힙 노드는 힙에 할당된 블록에 해당된다.
p → q의 방향을 갖는 간선은 블록 p의 위치에서 블록 q의 위치를 가리키는 포인터가 있음을 의미한다.

노드 p가 도달 가능하다고 말하는 경우, 이는 어떤 루트 노드에서 p까지의 경로가 존재함을 의미한다.
어느 시점에서든 도달 불가능한 노드는 프로그램에서 다시 사용할 수 없는 가비지에 해당한다.
가비지 컬렉터의 역할은 도달 가능성 그래프의 표시를 관리하고 주기적으로 도달 불가능한 노드를 free시키는 것이다.

9.10.2 Mark&Sweep 가비지 컬렉터

마크 앤 스윕 가비지 컬렉터는 마크 단계와 스윕 단계로 구성된다.
마크 단계에서는 모든 루트 노드의 도달 가능하고 할당된 하위 노드들을 표시한다.
스윕 단계에서는 표시되지 않은 블록들을 해제한다.

9.10.3 C 프로그램에 대한 보수적 Makr&Sweep

Mark&Sweep은 C에서 가비지 컬렉팅할 때 적절한 방법이다.
블록을 이동시키지 않은 채로 동작하기 때문에,
C 언어처럼 포인터를 직접 사용하고, 객체의 주소를 자주 참조하는 언어에서 유용하다.
객체의 주소가 변하지 않기 때문에 포인터를 다시 설정할 필요가 없다.

근데 C 언어에선 isPtr 함수를 구현하는게 어렵다.

어려운 이유
1. C는 메모리 위치에 타입 정보를 기록하지 않음. 그래서 isPtr은 입력 매개변수가 포인터인지 아닌지 결정할 수 있는 명확한 방법이 존재하지 않음.
2. p가 포인터였다는 걸 알게 돼도 isPtr이 p가 할당된 블록의 데이터 중에서 어떤 위치를 가리키는지 여부를 결정할 확실한 방법이 없음.

할당된 블록의 집합을 균형 이진 트리로 유지하면 해결됨.
모든 블록이 왼쪽 서브트리에 있는 경우 작은 주소에 있고,
오른쪽 서브트리에 있는 경우 큰 주소에 있음이 보장됨.

isPtr은 이 트리를 사용해서 할당된 블록을 이진 검색함.
매 단계에서 블록 헤더의 size 필드를 사용해서 p가 블록 내에 들어가는지 결정함.

접근할 수 있는 걸 다 mark할 수 있긴 한데
실제 도달할 수 없는 블록들을 잘못 mark할 수도 있음. (그래서 보수적)
일부 가비지 못 반환할 수도 있음.

9.11 C 프로그램에서의 공통된 메모리 관련 버그

가상메모리 사용하고 관리할 때 에러 생기기 쉬움.
잘못된 데이터를 잘못된 위치에 기록하면,
프로그램이 오랫동안 돌아가다가 한참 뒤에야
이 프로그램에서 멀리 떨어진 부분에 가서 마침내 실패한다.

9.11.1 잘못된 포인터의 역참조

어떤 프로세스의 가상 주소공간 내에 어떤 의미 있는 데이터로도 매핑되지 않은 큰 구멍들이 존재한다.
만약 포인터를 이 구멍들 중 하나로 역참조하려 하면 segmentation 예외가 일어난다.
또, 일부 가상메모리는 읽기만 가능하다. 이 영역에 쓰려고 하면 보호 예외로 프로그램을 종료시킨다.

잘못된 포인터의 예시

NULL 포인터 역참조: 포인터가 NULL을 가리킬 때 이를 역참조하는 경우
해제된 포인터 역참조: 이미 해제된 메모리 블록을 가리키는 포인터를 역참조하는 경우
초기화되지 않은 포인터 역참조: 초기화되지 않은 포인터 변수를 사용하여 메모리에 접근하는 경우

scanf("%d", &val);

으로 주소값을 제대로 전달해줘야 되는데

scanf("%d", val);

그냥 값 전달하는 실수 종종 하니까 조심.
val이 유효한 주소값이어서 이상한 메모리 건드리면
치명적이고 혼란스러운 결과를 맞이하게 됨. 그것도 한참 나중에.

9.11.2 초기화되지 않은 메모리를 읽는 경우

int *y = (int *)malloc(n*sizeof(int));
for(i=0; i<n; i++)
	y[i] += 1;

배열 y가 0으로 초기화됐다고 잘못 가정해버리면 이렇게 된다.
명확하게 y[i]를 0으로 초기화하거나 calloc을 사용해야 한다.

9.11.3 스택 버퍼 오버플로우 허용하기

스택 버퍼 오버플로우는 지역 변수가 할당된 메모리 범위를 초과하여 쓰기 작업을 수행하는 경우 발생함.
이는 스택의 다른 변수나 반환 주소를 덮어쓸 수 있어 프로그램의 흐름을 변경하거나 보안 취약점을 초래할 수 있음.

9.11.4 포인터와 이들이 가리키는 객체들이 같은 크기라고 가정하기

int i;
int **A = (int **)malloc(n * sizeof(int));

for (i=0; i<n; i++)
	A[i] = (int *)malloc(m * sizeof(int));

sizeof(int)가 아니라 sizeof(int*)를 했어야 함.

이 코드는 int와 int 포인터가 같은 크기인 머신에서는 잘 돌아갈 것.
하지만 코어 i7같이 포인터가 int보다 더 큰 머신에서 돌리면 오류 남.

9.11.5 Off-by-One 에러 만들기

int array[10];
for (int i = 0; i <= 10; i++) { // 배열 경계를 벗어남
    array[i] = i;
}

배열 범위 넘어가는거

9.11.6 포인터가 가리키는 객체 대신에 포인터 참조하기

*size--;

이래버리면 실제로 가리키는 정수 값 대신에 포인터 자신을 감소시킴.

(*size)--;

이렇게 해야지 size가 갖고 있는 주소값에 들어있는 값을 1 줄임.

9.11.7 포인터 연산에 대한 오해

int arr[5] = {1, 2, 3, 4, 5};
int *ptr = arr;
ptr += 1; // 포인터는 4바이트(정수 크기)만큼 증가

포인터에 대한 산술연산은 이들이 가리키는 객체의 크기 단위로 수행됨.
바이트 단위로 이루어지는게 아님.

9.11.8 존재하지 않는 변수 참조하기

int *foo() {
    int x = 10;
    return &x; // 잘못된 사용, 함수 반환 후 x는 유효하지 않음
}

스코프를 벗어난 변수를 참조할 때 발생.
특히 함수가 반환한 후 해당 함수의 지역 변수를 참조하는 경우가 있음.

9.11.9 해제된 힙 블록을 참조

int *ptr = (int *)malloc(sizeof(int) * 10);
free(ptr);
*ptr = 10; // 잘못된 사용, 이미 해제된 메모리 접근

이미 free된 힙 블록을 참조할 때 발생함.
이는 이중 해제(double free) 버그로 이어질 수 있으며,
시스템 충돌이나 예기치 않은 동작을 초래할 수 있음.

9.11.10 메모리 누수 유발

할당된 블록들은 반드시 반환해야 함.

lazyArtisan

이전 포스트

크래프톤 정글 TIL : 0806

다음 포스트