Move Fast

본 글은 The Linux Kernel 을 정리한 것이며, 출처를 밝히지 않은 모든 이미지는 원글에 속한 것입니다.

프로그램과 프로세스

• 프로그램 디스크에 실행 가능한 형태(Executable and Linking Format, ELF)로 저장되어 있는 기계어 명령과 자료의 집합
• 프로세스 실행중인 프로그램, 기계어 명령들을 실행함에 따라 끊임없이 변화하는 동적인 존재
• 프로그램을 실행하면 프로세스의 가상 주소공간에는 프로그램의 명령어와 데이터 뿐만 아니라, 프로그램 카운터(PC), CPU 레지스터, 그리고 루틴 인자, 복귀 주소, 저장된 변수 같은 일시적인 데이터를 보관하는 스택(stack)도 포함됨
• 운영체제에서 프로세스란 각각 고유의 권한과 책임을 가지는 하나의 작업(task)이며, 각 프로세스는 자신의 가상 주소공간에서만 실행되는데, 커널의 도움을 받는다면 다른 프로세스와 상호작용(프로세스간 통신, IPC) 할 수 있음
• 프로세스가 사용하는 시스템 자원은 크게 4가지
  • CPU 자원 명령을 수행하기 위해 일정한 시간이 프로세스마다 할당되어 CPU가 실행
  • 메모리 자원 명령어와 데이터 등을 실행하려면 프로세스가 실행되는 부분을 물리 메모리에 로드
  • 디스크 자원 파일 시스템의 파일들을 열고 사용
  • 디바이스 드라이버 네트워크나 키보드 장치 같은 물리적인 장치를 직접적으로 또는 간접적으로 사용
• 커널은 여러 시스템 자원을 관리하고, 프로세스들이 공평하게 자원을 사용할 수 있도록, 각 프로세스가 가지고 있는 시스템 자원을 추적하는데, 이를 위해 다양한 커널 자료구조가 생성되고 제거됨
• 리눅스는 멀티프로세싱(Multiprocessing) 운영체제이기 때문에, CPU에 코어가 둘 이상이면 각 코어가 항상 프로세스를 실행할 수 있도록 하여 CPU 사용을 극대화
  • 시스템 자원을 요청한 프로세스는 요청 결과를 얻기까지 대기해야 하는데, 그 시간 동안 CPU는 다른 프로세스를 실행
  • 유니프로세싱(Uniprocessing)의 경우, 반드시 하나의 프로세스만 종료될 때까지 실행되므로, 자원을 요청하면 CPU는 아무 것도 하지 않은 상태가 됨 (대기 시간을 낭비)
• 리눅스는 실시간(real-time) 프로세스도 지원하며, 외부에서 발생하는 사건(event)에 매우 빨리 반응하기 위해 스케줄러는 일반 사용자 프로세스와는 다르게 취급하고 높은 우선순위를 부여함
• CPU가 다음에 실행할 프로세스를 선택하는 작업을 스케줄링(scheduling)이라고 하며, 커널 코드에서 스케줄러가 이를 수행함

프로세스 자료구조

• 각 프로세스는 task_struct 구조체로 표현되며, task 배열은 task_struct 구조체의 포인터를 저장하여 프로세스들을 관리
• 시스템이 생성할 수 있는 최대 프로세스의 개수는 task 배열의 크기로 제한됨 (기본값 512)
• current 변수 현재 CPU가 실행하고 있는 프로세스를 참조하는 포인터
• task_struct의 state 변수는 실행되면서 상황에 따라 바뀌는 프로세스의 상태를 나타냄
  • new 프로세스가 생성된 상태
  • ready 프로세스가 메모리에 로드되어 실행 준비가 된 상태
  • running 현재 CPU가 프로세스를 실행하고 있는 상태
  • waiting 프로세스가 이벤트나 시스템 자원을 기다리고 있는 상태
  • terminated 프로세스가 종료된 상태
  • blocked/suspend 스왑 아웃된 프로세스가 실행 준비가 되지 않은 상태
  • ready/suspend 스왑 아웃된 프로세스가 실행 준비가 된 상태
  • waiting 상태에 있는 프로세스들은 스왑 아웃하기 좋은 후보이기 때문에, 스와핑될 경우 blocked/suspend 상태가 됨
  • 블럭킹 모드에서 실행되면 해당 프로세스는 running -> waiting 상태가 되는 것이지 waiting -> blocked/suspend 상태가 되는 것이 아님
    • 스와핑된 상태에서 이벤트가 완료되면 blocked/suspend -> ready/suspend 상태가 됨

• 좀비 프로세스 정지된 프로세스이지만, 어떤 이유로 여전히 task 배열에 task_struct 구조체가 남아있는 프로세스 (자원 낭비)
• 프로세스 식별자(Process Identifier, PID) 시스템의 모든 프로세스는 각자의 고유한 식별자를 가지며, 이는 task 벡터의 인덱스와는 다름. 식별자는 사용자 식별자와 그룹 식별자로 나뉘는데, 이는 각 프로세스가 시스템 파일이나 장치에 접근할 때 제어하는 용도
  • 리눅스에서 시스템의 모든 파일들은 소유권과 접근 권한을 가짐
  • 사용자 종류: 소유자, 프로세스 그룹, 모든 프로세스
  • 접근 권한 종류: 읽기, 쓰기, 실행
  • 각 사용자 계층은 서로 다른 권한을 가질 수 있음. 예를 들어, 소유자는 읽기/쓰기 가능인데 그룹은 읽기만 허용하는 경우
  • chown 명령어는 파일의 소유권을 변경하며, chmod 명령어는 파일의 접근 권한을 변경

File Mode 와 Owner 사이의 숫자 3은 하드 링크의 개수로, 몇 번 복사되었는지를 나타냄

• task_struct 구조체는 4 쌍의 사용자 식별자와 그룹 식별자를 저장하고 있음
  • uid, gid 프로세스를 실행시킨 사용자의 식별자와 그룹 식별자
  • effective uid, gid (euid, egid) 프로세스의 uid, gid를 디스크의 실행 이미지의 uid, gid로 변경시키는 setuid 프로그램의 사용자 식별자와 그룹 식별자
  • file system uid, gid 프로세스가 파일 시스템에 자원을 요청할 때 접근 권한을 검사하기 위해 사용하는 uid, gid로, euid, egid와 동일
    • 예를 들어, 원격에서 마운트된 파일 시스템에서 사용자 모드인 NFS 서버가 파일에 접근할 때, 서버가 아닌 특정 프로세스로서 파일을 접근하기 위해 file system uid, gid 만 변경 (euid, egid 변경하지 않음)
    • 사용자가 NFS 서버에 kill 시그널을 보내는 등 악의적인 공격을 행할 경우 kill 시그널은 특정 euid, egid 를 가진 프로세스에게만 전달되기 때문에 euid, egid가 수정되지 않게 하여 이 공격을 방지할 수 있음
  • saved uid, gid 시스템 콜을 이용하여 프로세스의 uid, gid를 바꾸는 프로그램이 사용하는 uid, gid로, 원래의 uid, gid가 바뀌어 있는 동안 실제 이전의 uid, gid를 저장하는 용도로 사용
• 시간과 타이머 커널은 각 프로세스의 생성 시간과 프로세스가 사용한 CPU 시간을 관리
  • 매 클럭 틱마다 현재 프로세스가 커널 모드와 유저 모드에서 사용한 시간의 양을 jiffies 단위로 계산하여 갱신
  • 프로세스가 직접 지정하여 사용할 수 있는 간격 타이머(interval timer)도 지원하며, 이 시간이 만료되면 프로세스는 자신에게 시그널을 보낼 수 있음
    • real timer tick 만료 시 프로세스는 SIGALRM 시그널을 받음
    • virtual timer tick 만료 시 프로세스는 SIGVTALRM 시그널을 받음 (프로세스가 수행한 시간)
    • profile timer tick 만료 시 프로세스는 SIGPROF 시그널을 받음 (프로세스가 수행한 시간과 프로세스의 다른 한편에서 시스템이 수행한 시간을 합친 것)
  • 하나 또는 모든 간격 타이머가 실행될 수 있으며, 커널은 task_struct에 필요한 모든 정보를 저장
• 커널 스레드와 데몬을 제외한 프로세스들은 각자의 가상 주소공간에서 실행되는데, task_struct 의 mm_struct 구조체가 이를 참조
• 프로세서 고유 컨텍스트(Processor Specific Context) 프로세스는 실행될 때마다 CPU의 레지스터와 메모리 공간에 임시 데이터를 보관하는 스택을 사용하는데, 프로세스가 중단될 때 이 데이터들은 task_struct에 저장되었다가 재실행되면 이 정보로부터 컨텍스트를 복구함
  • 이렇게 CPU가 프로세스를 번갈아 실행하는 것을 문맥 교환(Context Switching)이라고 함

프로세스의 파일 연산

• 커널은 프로세스가 접근하는 파일 시스템을 관리하기 위해 task_struct 구조체에 fs와 files 포인터를 이용
• fs 는 fs_struct 구조체를 참조하는 포인터 변수로, fs_struct 구조체는 새로운 파일이 만들어질 때의 기본 모드를 나타내는 umask와 해당 프로세스의 VFS inode에 대한 포인터 두 개를 포함
  
  • VFS inode 는 디스크를 추상화한 가상 파일 시스템에서 사용하는 파일 식별자 (리눅스는 파일, 디렉토리, 장치 모두 파일로 관리하며, inode 는 파일과 일대일 대응 관계)
  • 첫번째 VFS inode는 프로세스의 루트 디렉토리(홈 디렉토리)를 가리키며, 두번째 VFS inode는 현재 디렉토리(pwd 명령어로 확인 가능)를 참조
  • 각 VFS inode 마다 count 항목으로 몇 개의 프로세스가 그 파일을 참조하고 있는지 파악
  • 어떤 디렉토리나 그 디렉토리의 하위 디렉토리가 한 프로세스의 현재 디렉토리로 설정되었다면, 그 디렉토리는 삭제 불가
• files 는 files_struct 구조체를 참조하는 포인터 변수로, 현재 프로세스가 사용하고 있는 모든 파일들에 대한 정보를 저장
• 리눅스에서는 파일, 디렉토리, 단말 입출력, 물리 장치 모두 파일로 처리되며, 각 파일은 자신을 나타내는 기술자(file descriptor, fd)를 가지며, files_struct 구조체에서는 파일을 기술하는 file 구조체에 대한 포인터(fd)를 최대 256개까지 저장 가능
• file 구조체는 파일이 만들어질 때의 모드(읽기 전용, 읽고 쓰기, 쓰기 전용)인 f_mode 항목과 다음 번에 읽거나 쓸 위치를 나타내는 f_pos 항목, 그리고 그 파일에 해당하는 VFS inode인 f_inode 항목 등 파일 연산에 필요한 정보를 가짐
  • f_op 항목은은 그 파일에 대한 작업을 수행하는 루틴들의 주소를 저장한 배열을 참조
  • 프로세스는 처음 실행될 때 세개의 파일 기술자가 열려 있다고 가정: 표준 입력(fd=0), 표준 출력(fd=1), 표준 에러(fd=2)
• 프로세스는 파일 시스템에 접근할 때, 열린 파일 기술자(file descriptor)에 대한 포인터와 두 개의 VFS inode 포인터를 이용

프로세스의 가상 메모리

• 프로그램을 실행하면, 커널은 task_struct 구조체를 생성해서 프로세스에 필요한 정보를 초기화한 뒤 커널 자료구조에 이를 추가
• 프로세스가 사용할 가상 주소공간은 메모리 매핑 과정에서 초기화되며, 크게 3개의 영역으로 나눌 수 있음
  • 로드된 프로그램의 이미지 실행 코드 및 데이터, 그리고 가상 메모리에 로드하기 위해 필요한 모든 정보
  • 공유 라이브러리 표준 파일 연산과 같이 공통적으로 쓰이는 코드의 라이브러리를 사용
    • 공유하고 있는 모든 프로세스의 가상 메모리에는, 물리 메모리에 있는 이 라이브러리와 연결된, 가상 페이지가 존재
  • 가상 메모리 추가 할당 읽고 있는 파일의 내용을 담기 위하여 등 새로 할당된 가상 메모리를 프로세스의 가상 메모리와 연결
• 메모리 매핑으로 가상 주소공간이 생성되면, 프로세스가 접근하는 부분만 실제로 물리 메모리에 로드(요구 페이징)
  • 커널은 프로세스의 코드와 데이터를 곧바로 실제 메모리에 로드하는 대신, 프로세스의 페이지 테이블을 수정하여 가상 영역에는 존재하고 있지만 실제로는 메모리에 있지는 않다고 표시
  • 요구 페이징에 의해 페이지 폴트가 발생하면, 프로세스는 폴트가 발생한 가상 주소와 폴트의 원인은 커널에게 통보하고, 커널은 페이지 폴트 핸들러를 호출
    • 유효한 가상 주소인데 빈 물리 페이지가 없다면, 페이지 교체를 위한 스와핑
    • 유효한 가상주소인데 빈 물리 페이지가 있다면, 물리 메모리에 로드
    • 유효하지 않은 가상 주소이면 세그멘테이션 폴트 시그널을 프로세스에 전달 (프로세스는 이를 처리하는 핸들러가 정의되어 있지 않으면 기본 동작으로 종료함)
    • CPU는 페이지 폴트가 발생한 명령어부터 프로세스를 다시 실행
• 하나의 가상 페이지는 하나의 vm_area_struct 구조체에 대응되며, 이 구조체의 리스트를 mm_struct 구조체가 참조하는데, 커널은 task_struct 구조체에서 mm_struct 구조체의 포인터를 이용해 프로세스의 가상 메모리를 관리
• mm_struct 구조체는 페이지 테이블에 대한 포인터와 로드된 프로그램의 실행 이미지를 가리키는 포인터를 별도로 가지고 있음
• 커널은 프로세스의 가상 메모리에 대한 연산을 vm_area_struct 에 있는 vm_ops 가 참조하는 루틴을 실행시켜 처리하는데, 페이지 폴트, 스와핑 등이 있으며, 이러한 인터페이스 추상화는 하드웨어 장치 종류와 무관하게 가상 메모리를 일관성있게 처리함
• vm_area_struct 구조체의 리스트는 빈번한 탐색 과정에서 시간 복잡도를 줄이기 위해 AVL 트리로 구현되었음
  • 왼쪽 포인터가 가리키는 노드는 더 낮은 가상 주소를 가지며, 오른쪽 포인터가 가리키는 노드는 더 높은 가상 주소를 가짐
  • AVL 트리는 균형 이진 트리로, 삽입/삭제 시 어떤 두 서브트리의 높이차도 1을 넘지 않도록 추가적인 처리(트리 회전)가 필요

• 가상 메모리를 추가로 할당할 때, 커널은 먼저 vm_area_struct 구조체를 생성한 뒤 mm_struct 에 있는 mmap 포인터가 참조하는 리스트에 생성한 것을 추가하며, 이후 해당 공간에서 작업(읽기/쓰기/실행)하게 되면 페이지 폴트가 발생하고 커널은 해당 페이지를 물리 메모리에 로드한 후 페이지 테이블을 갱신한 뒤 프로세스를 재개
• 로드된 프로그램의 실행 이미지는 초기화된 데이터, 초기화되지 않은 데이터, 텍스트(코드) 영역을 포함, 별도로 프로세스가 실행 중 데이터를 보관하기 위해 힙과 스택이 할당됨. 힙과 스택은 서로 마주보고 증가하며 스택은 높은 주소에서 낮은 주소로 증가

쓰레드

• 프로세스는 실행중인 프로그램으로, 운영체제에서 작업의 단위이며, 쓰레드(Thread)는 프로세스에서 작업을 수행하는 흐름
• 프로세스는 생성과 동시에 단 하나의 쓰레드를 가지므로, 기본적으로 싱글 쓰레딩으로 작업을 처리
  • 쓰레드 정보는 task_struct 구조체에서 thread_info 가 참조하는 자료구조에 저장됨
• 프로세스는 쓰레드를 추가로 생성할 수 있으며, 멀티 쓰레딩(Multi-Threading)은 둘 이상의 쓰레드로 작업을 처리하는 것을 의미

• 각 쓰레드는 별도의 스택과 레지스터 정보를 가지며, 이를 제외한 프로세스의 메모리 공간을 모든 쓰레드가 공유
  • 둘 이상의 쓰레드가 같은 메모리 영역에 접근할 때, 접근하는 순서에 따라 결과가 달라지는 문제(경쟁 조건, race condition)가 발생한다면, 이 영역을 임계 영역(critical section)으로 보고, 단일 쓰레드만이 접근할 수 있도록 락(lock)을 걸어야 함
  • 락 변수로는 뮤텍스(mutex)가 있는데, 락을 점유한 쓰레드가 락을 해제하기 까지 임계 영역이 되며, 그 락을 원하는 다른 쓰레드는 모두 대기 상태가 됨. 락을 해제하는 순간 임의의 쓰레드가 접근하게 됨
  • 예를 들어, 어떤 쓰레드는 읽기를 하고 어떤 쓰레드는 쓰기를 할 때, 쓰기가 원자적으로 끝나기 전에 읽는 상황이 발생할 수 있는데 락 변수를 사용해서 완전히 쓰기가 끝나기 까지 어떤 쓰레드도 읽지 못하도록 할 수 있음
  • 락 변수를 사용할 때는 데드락(deadlock)에 주의해야 하는데, 데드락 문제는 락을 점유하려하는 모든 프로세스나 쓰레드가 대기 상태에 있는 것이며, 락을 점유한 쓰레드가 비정상 종료되어 락이 해제되지 않거나, 락 변수를 둘 이상 사용했을 때 락을 점유하는 순서가 두 쓰레드가 엇갈리는 경우 주로 발생함
    • 쓰레드1은 어떤 임계 영역에 락 변수를 M1 -> M2 순서로 점유하려 하는데, 동시에 쓰레드2가 M2 -> M1 순서로 점유하게 된다면 데드락이 발생함
    • 락 변수를 사용할 때 주의하거나 위와 같은 상황에 한 쪽에서 락을 양보할 수 있도록 구현해야 함

• 쓰레드도 CPU가 프로그램 카운터에 따라 명령어를 실행하는 구조이기 때문에 여러 쓰레드를 번갈아 실행하는 것을 문맥 교환(Context Switching)이라고 하며, 프로세스의 문맥 교환이 가상 메모리를 저장하고 복구해야 하는 반면, 쓰레드의 문맥 교환은 사전에 작업했던 정보가 상대적으로 적어 비용이 적게 듬
  • PCB(Process Control Block) 프로세스의 작업 상태를 저장하는 커널 메모리 공간
  • TCB(Thread Control Block) 쓰레드의 작업 상태를 저장하는 커널 메모리 공간

스케줄링

• 리눅스에서는 선점형(preemptive)과 비선점형(non-preemptive) 스케줄링을 모두 지원
• 모든 프로세스는 타임 슬라이스(time slice) 단위로 CPU 시간을 할당받으며, 현재 실행중인 프로세스는 그 시간동안 어떤 다른 프로세스에 의해 선점되지 않음(non-preemptive). 그 시간이 끝나면 CPU는 실행 가능한 프로세스들 중 가치 있는 것을 선택해 실행(preemptive)하고 해당 프로세스는 차례가 올 때까지 대기 큐에 추가되어 대기
  
  • 라운드 로빈 스케줄링
  • 선점형과 비선점형을 혼합해서 사용하는 이유: 프로세스는 시스템 콜을 호출해서 자원을 요청하게 되는데, 결과를 받기까지 대기 상태가 되고, 이런 시간이 길어질수록 CPU 시간을 낭비하기 때문에, 공정하게 CPU 시간을 분할하여 그 시간이 만료되면 다른 프로세스가 실행되게 한 것 (CPU 사용의 극대화)
• 정해진 시간 동안 프로세스가 CPU를 내놓을 수는 있음. schedule(), sleep_on(), interruptible_sleep_on() 등의 함수를 부르지 않으면 시스템 콜이 다른 프로세스에 의해 중단되지 않음
• 가치 있는 프로세스를 골라 실행하는 일은 스케줄러(schedular)가 수행하는데, 공정하게 CPU 시간을 할당하기 위해 task_struct 구조체에 있는 각 프로세스에 대한 정보를 이용
  • policy 그 프로세스에 적용될 스케줄링 정책
  • priority 프로세스가 스케줄링될 때 우선순위, 프로세스가 실행될 수 있는 시간(jiffies 단위)
  • rt_priority 실시간 프로세스들간의 상대적 우선순위
  • counter 프로세스가 실행될 수 있는 시간으로, 처음 실행될 때 priority 값으로 설정되며, 클럭 틱에 따라 감소
• 실시간 프로세스는 일반 프로세스보다 우선순위가 높기 때문에, 스케줄링 정책을 라운드 로빈과 FIFO 방식 중 하나를 선택할 수 있음
  • 라운드 로빈 스케줄링으로 할 경우, 정해진 시간 만큼만 실행되는 것이고, 자신의 차례가 올 때 까지 대기한 후 실행됨
  • FIFO 스케줄링으로 할 경우, 실시간 프로세스들만 있는 대기 큐에 삽입되어 자신의 차례가 올 때까지 대기한 후 실행됨
  • 일반 프로세스와 실시간 프로세스 둘 다 실행 대기중이라면, 실시간 프로세스가 항상 먼저 실행됨
• 스케줄러가 실행되는 상황
  • 현재 프로세스를 대기 큐에 넣은 직후
  • 시스템 콜이 끝난 직후
  • 프로세스가 커널 모드에서 유저 모드로 바뀌기 직전
  • 시스템의 타이머가 현재 프로세스의 counter를 0으로 설정한 경우
• 커널 작업(kernel work) 인터럽트가 발생하면, 인터럽트 모드가 지속되는 동안 다른 인터럽트를 받지 않기 때문에 오래 걸리지만 나중에 해도 되는 작업을 하반부 핸들러(bottom half handler)나 작업 큐(task queue)에 추가해서 인터럽트 핸들링 이후 스케줄러에 의해 루틴이 실행되도록 함

• 현재 프로세스는 다른 프로세스가 선택되기전에 다음과 같이 처리되어야 함
  • 만약 현재 프로세스가 라운드 로빈 정책이면, 현재 프로세스는 실행 큐에 추가됨
  • 만약 인터럽트 허용 상태인데 이전 스케줄링 후에 시그널을 받은 경우, 실행중 상태로 변경
  • 만약 정해진 시간이 만료되었다면, 실행중 상태로 변경
  • 이미 실행중 상태이면 그대로 유지
  • 실행 큐에서 실행중이거나 인터럽트 허용이 아닌 프로세스들을 제거 (다음 스케줄링에서 제외한다는 의미)
• 실행 큐에 있는 프로세스들 중 수행할 프로세스를 탐색 (실시간 프로세스는 일반 프로세스보다 높은 가중치를 가짐)
  • 보통 프로세스의 가중치는 counter 값이지만, 실시간 프로세스는 counter + 1000 을 가중치로 가짐
  • 주어진 타임 슬라이스를 어느 정도 소모한 (즉 counter값이 감소한) 현재 프로세스는 시스템의 같은 우선순위를 가진 다른 프로세스들보다 불리함 
  • 여러 프로세스가 동일한 우선순위를 가지면, 실행 큐에서 앞에 위치한 프로세스를 선택 (현재 프로세스는 실행 큐에 추가됨)
• 마지막으로 수행할 프로세스가 현재 프로세스가 아니면, 프로세스를 교체(swap)
  • 현재 프로세스를 중단할 때, 프로그램 카운터와 같은 레지스터 정보 등의 모든 기계적인 상태를 task_struct에 저장
  • 실행될 프로세스의 모든 기계적인 상태를 복구하는데, CPU 레지스터 등 바뀌는데 하드웨어의 도움이 필요
  • 교체할 두 프로세스들의 메모리에 더티 페이지가 있으면 페이지 테이블 엔트리를 갱신해주어야 하는데, 이는 아키텍처마다 다름
  • TLB를 사용하는 프로세서의 경우, 현재 프로세스에 속하는 캐시된 페이지 테이블 엔트리들을 모두 제거
• 멀티프로세서 시스템에서는 각 CPU별로 현재 프로세스와 idle 프로세스를 관리(CPU마다 하나의 idle 프로세스가 존재)해야 하며, 각 프로세스의 task_struct 구조체에는 자신이 현재 실행되고 있는 프로세서 번호(processor)와 마지막으로 실행되었던 프로세서 번호(last_processor)가 저장되어 있음
  • 리눅스는 task_struct 구조체에 있는 processor_mask 를 이용하여 각 프로세스를 특정 CPU에서만 (혹은 여러 개) 실행되도록 제한할 수 있음. 예를 들어, 비트 N이 켜져 있으면 N번째 CPU 에서만 실행하는 것
  • 이는 이전 실행과 현재 실행이 다른 프로세서에서 이루어질 때 성능상의 오버헤드를 줄이기 위한 것으로, 스케줄러가 실행할 새로운 프로세스를 고를 때 processor_mask에 현재 프로세서의 번호가 설정되어 있지 않은 프로세스는 고려하지 않음

프로세스의 생성

• 시스템이 처음 시작될 때 커널 모드에 있으며, 단 하나의 프로세스만 존재하는데, 초기화의 마지막 단계에서 이 프로세스는 init 이라고 하는 커널 쓰레드를 시작한 후 아무 것도 하지 않는 루프(idle 프로세스)를 실행 (언제나 할 일이 없으면 idle 프로세스가 실행됨)
• 다른 프로세스들이 생성되면 모두 초기 프로세스의 task_struct 구조체에 저장되며, 지금까지 설명한 프로세스는 사실상 초기 프로세스의 init 커널 쓰레드에서 파생된 것으로 init 커널 쓰레드를 init 프로세스라고도 함
• init 커널 쓰레드(또는 프로세스)는 시스템의 첫번째 프로세스(PID=1)로, 시스템 초기화의 일부를 담당하며  시스템 콘솔을 열고 루트 파일 시스템을 마운트 하는 등의 초기화 프로그램들을 실행
• 새 프로세스들은 이전 프로세스 또는 현재 프로세스를 복제한 것으로, 시스템 콜(fork 또는 clone)을 호출하여 커널 모드에서 수행
  • 새 프로세스가 생성되면 task_struct 구조체가 물리 메모리에 할당되고, 하나 이상의 물리 페이지가 새 프로세스의 (사용자와 커널) 스택으로 할당됨
  • 새 task_struct 구조체는 task 배열에 추가되고, 복제 대상이 된 프로세스의 task_struct 구조체 내용을 새 task_struct 구조체로 복사하는데, 처음에 mm_struct 구조체(프로세스의 가상 주소공간을 나타내는 자료구조)는 복사되지 않음
    • 즉, 새 프로세스의 task_struct 구조체는 mm_struct 에 대한 포인터를 가지는데 원래 프로세스의 구조체를 참조
    • 이는 프로세스를 복제할 때, 별도의 복사본을 사용하지 않고 자원(프로세스의 파일들, 시그널 핸들러, 가상 메모리 등)을 공유하려는 목적이며, mm_struct 구조체에 count 변수는 공유중인 프로세스의 개수를 나타내는데 0이 되면 메모리를 해제
  • 새 프로세스는 새로운 식별자를 부여받고 동시에 복제 대상이 된 프로세스의 식별자를 부모 식별자로 갖게 됨
  • task_struct는 모두, 부모 프로세스, 형제(sibling, 부모가 같은 프로세스 들) 프로세스, 자신의 자식(child) 프로세스들에 대한 포인터를 가짐
• Copy-On-Write 프로세스를 복제한 뒤, 두 프로세스 중 하나가 가상 페이지에 쓰기 작업을 하면 해당 페이지를 복사
  •  쓰기 가능한 영역이라도, 아직 수정되지 않은 영역은 두 프로세스 사이에서 공유되며 실행 코드와 같은 읽기 전용은 항상 공유
  • 처음에는 쓸 수 있는 영역들의 페이지 테이블 엔트리(PTE)는 읽기 전용으로 표시되며, vm_area_struct에서 copy-on-write으로 표시
  • 쓰기 작업이 일어나면 페이지 폴트가 발생

프로그램 실행

• 리눅스에서 cd나 pwd 같은 적은 수의 내부에 직접 구현된 명령어들은 쉘(shell)이라는 명령어 해석기(command interpreter)에 의해 실행되는데, 쉘은 환경변수 PATH에서 저장된 프로세스의 찾기 경로(search path)에서 같은 이름을 가진 실행 이미지를 찾은 뒤, 이를 메모리에 로드하여 실행
• 쉘은 찾기 경로에 없는 프로그램도 실행할 수 있으며, 이를 위해 커널은 컴파일 과정에서 여러 이진 포맷을 리스트로 가지게 되는데, 이진 파일을 실행하면 각 이진 포맷을 하나씩 시도

• 실행 파일은 (파이썬 또는 쉘 스크립트 같은) 스크립트 파일도 포함되며, 이 파일들은 처리할 수 있는 올바른 해석기를 이진 포맷 목록에서 탐색하여 실행 (요약: 인터프리터 탐색 --> 쉘이 자기 자신을 fork --> 인터프리터로 실행 이미지 교체) 
• 쉘은 실행 이미지를 메모리에 로드하면, fork 메커니즘을 이용하여 자기자신을 복제한 뒤 쉘 이미지를 찾았던 실행 이미지로 교체
  • 실행 이미지 교체 시스템 콜은 exec 계열 명령어를 사용
  • 아무런 옵션이 없으면 쉘은 자식 프로세스가 종료될 때까지 기다림

• 쉘은 자식 프로세스를 생성하면 포그라운드(foreground) 프로세스로 실행되기 때문에 자식 프로세스가 사용자와 대화식으로 작업하게 되어 쉘과 작업할 수 없다는 문제가 생김. 자식 프로세스를 백그라운드(background)로 돌리게 되면, 프로세스가 시작되서 종료될 때까지 쉘은 어떤 영향도 받지 않음 (터미널에 입출력하는 게 있다면 단말 입출력이 공유될 수 있음, e.g., 명령어 입력 중에 출력)
  • 쉘에서 자식 프로세스를 생성한 후 Ctrl + Z 를 누르면 쉘은 자식 프로세스에게 SIGSTOP 시그널을 보내서 자식 프로세스가 suspend 상태가 되게 하는데, 쉘에서 bg 명령어를 실행하면 SIGCONT 시그널을 보내 자식 프로세스가 백그라운드(background)에서 실행됨
  • 쉘에서 작업 후 fg 명령어를 실행하면 포그라운드로 돌림
  • 쉘에서 명령어를 실행할 때 맨 뒤에 & 를 붙이면 자동으로 백그라운드로 실행시켜줌

Executable and Linkable Format, ELF

• ELF 실행 파일(실행 이미지)은 텍스트라고 불리는 실행 코드와 데이터를 포함하며, 실행 이미지 안에 있는 테이블은 프로세스의 가상 메모리에 어떻게 프로그램 코드를 로드할 지를 기술 (바이너리 자체가 그대로 메모리에 로드되는 것이 아님)
• 링크(link)는 정적 링크와 동적 링크로 나뉘며, 정적 링크된 실행 이미지는 링킹할 때 포함한 다른 실행 파일의 루틴들을 모두 하나의 파일에 합친 것이며, 동적 링크의 경우 실행 중에 공유 라이브러리 같은 이미 메모리에 있는 루틴들의 오프셋만 포함
  • 동적 라이브러리란 동적 링크된 실행 이미지가 사용하는 루틴들의 집합이며, 만약 커널 메모리 공간에 이 루틴들의 실행 코드가 적재되지 않았다면 세그멘테이션 폴트가 발생
  • 링커는 동적 라이브러리의 진입점(entry point)에서의 오프셋을 저장하며, 로더가 처음에 실행할 때 동적 라이브러리의 베이스 주소를 계산
  • CPU가 동적 라이브러리의 함수에 점프하려고 할 때, 베이스 주소와 오프셋을 더해서 실제 메모리 주소를 계산
  • 링커(linker)는 리눅스에서 ld 명령어로 실행할 수 있으며, 인자로 넘긴 프로그램이 실행될 때 메모리에서의 배치도와 처음 수행할 코드의 메모리에서의 주소를 지정
• 위 그림의 오른쪽은 ELF 실행 이미지이며, 2개의 물리적 헤더를 가짐
  • 첫번째 물리적 헤더는 이미지에서 실행 코드를 기술
    • 이는 가상 주소 0x8048000에서 시작하고 65532 바이트를 가짐
    • 정적 링크이므로, printf() 함수에 대한 라이브러리 코드를 모두 가짐
    • 이미지의 진입점(entry point), 즉 프로그램에서 처음 실행하는 명령은 이미지의 시작 주소가 아니라 가상 주소 0x8048090 (e_entry)
    • 이 코드는 두번째 물리적 헤더를 로드한 직후에 바로 시작
  • 두번째 물리적 헤더는 프로그램에서의 데이터를 기술
    • 가상 메모리의 0x8059BB8 위치에 로드 (이 데이터는 읽거나 쓸 수 있음)
    • 파일에서 데이터의 크기는 2200바이트(p_filesz)인데 반해, 메모리에서의 크기(p_memsz)는 4248바이트
    • 처음 2200바이트는 미리 초기화된 데이터
    • 다음에 있는 2048바이트는 실행 코드가 초기화할 데이터(BSD, 초기화되지 않은 데이터)
• ELF 실행 이미지를 메모리에 로드한다는 의미는, 프로세스의 vm_area_struct 리스트와 해당되는 페이지 테이블들을 셋업하는 과정이며, 이후 요구 페이징에 의해 페이지 폴트가 발생하면 프로그램의 코드와 데이터의 필요한 일부만 물리 메모리에 로드

본 글은 The Linux Kernel 을 정리한 것이며, 출처를 밝히지 않은 모든 이미지는 원글에 속한 것입니다.

페이지 할당 및 해제(Page Allocation and Deallocation)

• 물리 페이지를 할당하는 경우는 2가지
  • 디스크에 있는 실행 이미지를 메모리에 로드할 때
  • 페이지 테이블 같은 커널 특유의 자료구조를 저장할 때
• 물리 페이지는 mem_map_t 구조체의 리스트인 mem_map 자료구조로 관리되며, 부팅 시 초기화됨
• 각 mem_map_t 구조체는 물리 페이지 자료구조의 포인터를 갖고 있고, 각 물리 페이지 자료구조는 다음과 같은 3가지 정보를 포함
  • count 변수 이 페이지를 사용하고 있는 사용자(프로세스)들의 수
  • age 변수 페이지의 나이 (폐기 또는 스왑할 좋은 후보인지 결정하는데 사용)
  • map_nr 변수 물리 페이지의 프레임 번호
• frea_area 자료구조는 할당되지 않은 물리 페이지들을 저장하는 배열이며, i번째 원소는 2^i 개의 연속적인 페이지들을 갖는 연결 리스트의 포인터
  • 페이지들은 2의 제곱수 개수로 묶여서 블럭 단위로 보관됨 (1페이지, 2페이지, 4페이지, 8페이지 등)
  • map 변수는 각 원소마다 있는데, 할당된 페이지 그룹을 추적하여 관리하기 위한 비트맵으로, 비트 N은 1로 설정되면 N번째 페이지 블럭이 프리(free, 할당 가능)라는 의미

• 버디 알고리즘(Buddy Algorithm) 리눅스 페이지 블럭을 효율적으로 할당하고 해제하기 위한 알고리즘
  • 페이지 할당 코드는 하나 이상의 연속적인 물리 페이지로 구성된 블럭 1개를 할당
  • (nr_free_pages > min_free_pages) 시스템에 있는 할당 가능한 페이지 개수가 요청을 처리하기에 충분하다면, 요청한 크기에 해당하는 페이지 블럭을 free_area 에서 탐색
    • 만약 요청된 크기의 페이지를 찾을 수 없다면, 그 다음 크기(요청된 크기의 두 배)의 블럭을 탐색
    • 이 과정은 모든 free_area를 다 검색하거나, 사용할 수 있는 페이지 블럭을 찾아낼 때까지 반복
  • 찾아낸 페이지 블럭이 요청한 크기보다 크다면, 그 페이지 블럭은 요청한 크기가 될 때까지 분할됨
  • 블럭의 남은 부분은 frea_area에 해당하는 크기의 리스트에 추가되고, 요청한 크기의 페이지 블럭은 호출자에게 전달
• 페이지 해제 코드는 페이지 블럭이 해제될 때마다 인접한 프리 페이지들을 더 큰 블럭의 프리 페이지로 병합하여 메모리 조각을 줄임
  • 매 해제 과정에서 같은 크기의 인접한 버디(buddy) 블럭이 프리인지 검사
  • 페이지를 할당하다보면 메모리가 조각나기 쉬운데, 페이지 해제 코드는 계속해서 더 큰 페이지 블럭을 만들려고 하기 때문에 메모리에서 허락하는 만큼 블럭을 병합할 수 있으므로 메모리 조각을 줄이게 됨

메모리 매핑(Memory Mapping)

• 프로그램을 실행할 때, 디스크에 있는 실행 이미지를 프로세스의 가상 주소공간에 연결하는 것
• 실행 파일을 물리 메모리에 모두 로드하지 않고, 프로세스가 실행됨에 따라 참조되는 일부만 메모리에 로드(요구 페이징)
• 모든 프로세스의 가상 주소공간은 mm_struct 자료구조로 관리되며, 이 자료구조는 실행중인 이미지에 대한 정보 및 가상 페이지를 기술하는 vm_area_struct 구조체의 리스트의 포인터(=mmap)를 가지고 있음
• 각 vm_area_struct 구조체는 가상 페이지의 시작(vm_start)과 끝(vm_end), 메모리에 대한 연산(vm_ops), 접근 권한 등의 정보를 나타내며, 실행 이미지의 일부를 기술함
  • 예를 들어, nopage() 는 페이지 폴트를 처리하는 함수로, 특정 루틴의 주소를 참조하지 않으면 커널의 기본 루틴이 호출됨
• 처음에 프로그램을 실행하면, 메모리 매핑 과정에서 vm_area_struct 구조체의 집합이 생성되고, 가상 주소공간은 실행 코드, 초기화된 데이터(변수), 초기화되지 않은 데이터(BSS) 등을 포함

• 페이지 폴트가 발생하면, 커널에서 페이지 폴트 핸들러는 폴트가 발생한 가상 주소를 포함하는 vm_area_struct를 탐색
  • 폴트가 아니더라도 탐색 과정은 자주 발생하기 때문에, 실제로 vm_area_struct 리스트는 AVL 트리 구조
  • AVL은 균형 이진 트리로, 삽입/삭제 과정에서 항상 왼쪽과 오른쪽 서브트리의 높이차가 1보다 커지지 않도록 회전함

• 페이지 폴트가 발생한 곳이 유효한 주소(가상 주소공간 내에 존재)이면, 커널은 PTE를 검사
  • PTE가 값이 0이 아니면,스왑 아웃되어 PTE에 다른 페이지가 저장된 것이므로 그 페이지는 스왑 파일에 존재
  • 위의 경우, PFN 항목은 스왑 파일의(그리고 어떤 스왑 파일의) 어느 부분에 그 페이지가 들어있는 지에 대한 정보를 가짐
  • 요청한 페이지가 물리 메모리로 올라오면, 프로세스의 페이지 테이블을 갱신한 후, 폴트가 발생한 가상 주소에서 재실행

페이지 캐시(Page Cache)

• 디스크에 있는 실행 이미지를 불러오는 횟수를 줄이기 위해 고안된 저장공간으로, 메모리 매핑된 파일은 페이지 단위로 읽혀지는데 물리 메모리에 로드될 때마다 해당 페이지는 페이지 캐시에 저장됨
• 페이지 캐시는 page_hash_table 자료구조로 나타내며, 각 원소는 mem_map_t 구조체의 리스트의 포인터
  • 각 mem_map_t 구조체는 매핑된 페이지가 저장된 파일(inode)과 파일 내 오프셋(offset)을 포함
  • inode는 파일 하나에 1:1로 대응되는 커널 자료구조 VFS inode 번호를 의미
• 실제로 요구 페이징에서 페이지 폴트가 발생할 때마다, 커널은 페이지 캐시를 가장 먼저 참조
  • 페이지가 캐시에 있으면, 그 페이지를 나타내는 mem_map_t 자료구조에 대한 포인터가 페이지 폴트 처리 코드로 전달됨
  • 페이지가 캐시에 없다면, 물리 페이지를 할당하고 디스크 상의 파일로부터 페이지를 읽어와 메모리에 로드
    • 빈 물리 페이지가 없다면 스왑 알고리즘을 실행하여 적절한 페이지를 스왑 아웃
• 페이지 폴트가 발생할 때마다 페이지 캐시에 폴트가 발생한 페이지를 저장하는데 가능한 다음 페이지도 저장하려고 함. 이는 프로세스가 페이지를 순차적으로 접근할 가능성이 높기 때문에 최대한 미리 페이지를 읽어와 메모리 접근을 줄이려는 목적
• 페이지가 어떤 프로세스에 의해서도 사용되지 않으면 캐시에서 제거됨

페이지 스왑 아웃과 폐기(Page Swap-out and Discarding)

• 캐시가 커지면 물리 메모리 공간이 부족할 수 있는데, 이를 위해 커널 스왑 데몬(kswapd)이 불필요한 물리 메모리를 검사하고 해제함
• 커널 스왑 데몬은 커널의 init 프로세스에 의해 시작되는 커널 쓰레드라는 특별한 종류의 프로세스로, 물리 메모리 공간에서 커널 모드로 실행됨 (가상 주소공간을 가지지 않음)
• 커널 스왑 데몬은 커널 스왑 타이머가 주기적으로 만료될 때마다 free_pages_high 과 free_pages_low 라는 2개의 변수를 사용하여 실제 할당되지 않은 페이지 개수(nr_free_pages)가 너무 적지 않은지 검사
  • nr_free_pages > free_pages_high, 타이머가 만료되면 아무 일도 하지 않고 다시 잠듬 (다음 타이머 만료까지 대기)
  • nr_free_pages < free_pages_low, 타이머가 만료되면 물리 페이지를 해제하기 위해 3가지 방법을 시도 (다음 타이머 만료가 절반정도 당겨짐, 이전의 절반 정도 잠듬)
    • 페이지 캐시와 버퍼 캐시 크기 줄이기
    • 시스템 V 공유 메모리 페이지를 스왑 아웃
    • 페이지를 스왑 아웃하고 폐기
  • 매번 실행될 때마다 위 3가지 방법에서 최종적으로 성공한 방법을 기억해서 사용함
  • nr_free_pages 가 low ~ high 사이에 있으면, 다음 타이머 만료가 미뤄짐 (low보다 작을 때 적게 잠들었으니, low보다 커지면 더 오래 잠드는 구조)
• 커널 스왑 데몬은 nr_async_pages 라는 변수로 현재 스왑 파일에 저장될 페이지 개수도 고려하는데, 이 변수는 어떤 페이지가 스왑 파일에 쓰여지기 위해 큐에 들어가면 증가하고, 스왑 파일에 쓰여졌으면 감소
• 페이지 캐시와 버퍼 캐시 크기 줄이기
  • 물리 메모리 공간이 부족하면 가장 먼저 페이지 캐시와 버퍼 캐시에 있는 불필요한 페이지(사용하지 않는 것)를 제거
  • 메모리에서 스왑 아웃하는 경우와 달리 실제 장치에 기록할 필요가 없음
  • 커널 스왑 데몬이 캐시를 줄이려고 할 때마다, mem_map 리스트에 있는 페이지 블럭이 실제로 물리 메모리에서 제거되도 괜찮은지 시계 알고리즘(clock algorithm, 한 번에 몇 페이지씩 차례로 조사)으로 검사
    • 프리 페이지 수가 급격히 떨어져 스와핑이 빈번하게 발생한다면 검사할 페이지 블럭의 크기가 커짐
    • 페이지 블럭은 돌아가며 검사되는데, 각 페이지는 페이지 캐시나 버퍼 캐시에 있는 것만 해당되며, 공유 페이지는 제외
  • 해제되는 페이지는 어떤 프로세스의 가상 메모리에도 속하지 않는 것이므로, 페이지 테이블을 수정할 필요가 없음
• 시스템 V 공유 메모리 페이지 스왑 아웃
  • 커널 스왑 데몬은 캐시된 페이지를 제거하는 걸로 충분하지 않은 경우, 공유 페이지를 스왑 아웃
  • 시스템 V 공유 메모리는 둘 이상의 프로세스가 가상 메모리를 공유하여 정보를 주고 받는 프로세스간 통신 메커니즘(IPC)
    • 공유 메모리는 shmid_ds 자료구조로 표현되며, 각 프로세스마다 대응되는 가상 페이지들(vm_area_struct 구조체의 리스트)을 참조함
    • vm_area_struct 구조체에서는 vm_next_shared 와 vm_prev_shared 포인터로 공유되는 가상 페이지들을 연결
    • 각각의 shmid_ds 자료구조는 공유 가상 페이지가 매핑되어 있는 물리 페이지에 해당하는PTE의 리스트도 가짐
  • 커널 스왑 데몬은 공유 페이지를 스왑 아웃할 때도 시계 알고리즘을 사용하며, 맨 마지막으로 스왑 아웃된 공유 페이지를 기억
  • 공유 물리 페이지의 PFN은 이 페이지를 공유하는 모든 프로세스의 페이지 테이블에 존재하기 때문에 이들을 모두 변경해주어 스왑 아웃되었다고 표시(스왑 파일의 위치와 오프셋을 표시)해야 함
  • 커널 스왑 데몬은 각 프로세스의 페이지 테이블에서 공유 가상 페이지의 번호(VPFN)로 엔트리를 찾아서 스왑 아웃된 PTE로 변환시키고 해당 페이지의 count 변수를 1씩 감소함. 만약 count 변수가 0이 된다면 해당 공유 페이지를 스왑 파일로 스왑 아웃
  • 마찬가지로 shmid_ds 자료구조에 있는 PTE도 스왑 아웃된 PTE로 교체
  • 스왑 아웃된 PTE는 다시 물리 메모리에 해당 페이지를 적재할 때 사용됨
• 페이지 스왑 아웃과 폐기
  • 공유 페이지 스왑 아웃으로도 물리 메모리 공간이 부족한 경우, 커널 스왑 데몬은 각 프로세스의 페이지들을 검사하여 스왑 아웃할 대상을 관찰
  • 스왑 후보가 되는 페이지들은 그 안에 저장된 데이터들을 어떤 방법으로든 가져올 수 없어 저장해야 하는 경우
  • 폐기 후보가 되는 페이지들은 실행 코드처럼 변경되지 않아 스왑 파일에 쓸 필요가 없는 경우
  • 후보 페이지를 가진 프로세스가 결정되면, 그 프로세스의 가상 주소공간을 전부 살펴보면서 공유되거나 락이 걸리지 않은 영역을 탐색 (메모리에 락이 걸려 있는 페이지는 스왑하거나 폐기할 수 없음)
  • 커널 스왑 데몬은 실행될 때마다 후보 페이지의 age 변수를 1씨 증가시켜 오래된 것으로 만듬 (페이지는 자주 사용될수록 젊어지고, 적게 사용될수록 나이 듬, 오래된 페이지들은 스와핑의 좋은 후보)
  • 각 페이지를 나타내는 mem_map_t 구조체는 count 변수도 가지는데, 커널 스왑 데몬이 사용할 때는 count가 1씩 증가
    • 스왑 알고리즘은 count 가 적은 페이지들(사용자 수가 적은 페이지들)만 스왑 아웃
  • 어떤 프로세스는 가상 페이지에서 자신의 스왑 연산(vm_area_struct의 vm_ops 포인터)을 사용할 수 있으며, 연산이 정의되지 않은 경우 스왑 데몬은 스왑 파일에 페이지를 할당하고 스왑 페이지를 스왑 파일에 기록
  • 더티 페이지만 스왑 파일에 저장되며, 더티 페이지가 아닌 경우 해당 물리 페이지는 free_area 에 추가됨
  • 스왑 아웃 후, PTE에 스왑 파일의 위치와 파일 내 오프셋을 표시

스왑 캐시(Swap Cache)

• 동일한 페이지에 대해 스왑 아웃이 반복적으로 발생할 때, 스왑 파일에 기록하는 횟수를 줄이기 위해 사용 (더티 페이지만 해당됨)
• 스왑 캐시는 페이지 테이블 엔트리의 리스트로, 각 리스트 노드당 물리 페이지 하나에 해당됨
  • 커널은 스왑 아웃 요청을 처리할 때 가장 먼저 스왑 캐시에 유효한 PTE 가 존재하는지 파악
• 스왑 아웃되었다가 다시 접근된 페이지는 스왑 파일과 물리 메모리에 모두 존재하게 되는데, 이후 다시 스왑 아웃할 때 페이지가 변경되지 않았으면 스왑 파일에 이미 유효한 페이지가 존재하므로 다시 기록할 필요가 없음
• 스왑 캐시에 있는 PTE는 스왑 아웃된 페이지의 것으로, 스왑 파일의 inode 번호와 파일 내 오프셋을 포함
  • PTE가 값이 0이 아니면, 이미 스왑 아웃되었다는 의미로, 페이지의 변경 유무를 파악
  • 페이지가 변경되었다면, 해당 PTE를 스왑 캐시에서 삭제 (다시 기록해야 함)
• 예를 들어, 최초 실행 시 읽기/실행 작업으로 페이지 폴트가 발생한 경우, 페이지를 메모리로 가져온 뒤 PTE에 읽기만 가능으로 표시
  • 이후 쓰기 작업으로 페이지 폴트가 발생하면, 그 페이지는 더티로 표시되며 스왑 아웃 (메모리 -> 디스크) 후 스왑 캐시에 스왑 파일의 inode 번호 및 파일 내 오프셋을 저장, PTE에 쓰기 가능으로 표시
  • 이후 다시 스왑 아웃이 발생하면, 이미 스왑 파일에 존재하므로 다시 기록하지 않음

페이지 스왑 인(Page Swap-in)

• 스왑 파일에 저장된 더티 페이지들이 다시 물리 메모리에 로드해야 하는 경우를 스왑 인(Swap In)이라고 함
  • 이미 스왑 아웃된 물리 페이지에 매핑된 가상 페이지에, 쓰기 작업을 하는 경우
• RE: 접근하는 페이지(VPFN)에 해당하는 PTE가 유효하지 않으면 페이지 폴트가 발생
  
  • 페이지 폴트 핸들러: vm_area_struct 의 nopage()
  • 가상 주소공간에 유효하지 않은 주소이면 세그멘테이션 폴트 시그널을 프로세스에게 전달
  • PTE 얻기
    • MMU는 TLB가 있으면 TLB를 먼저 참조
    • MMU는 TLB에 엔트리가 없으면 페이지 테이블을 참조
  • 물리 페이지 얻기
    • PTE에 스왑 아웃이 표시되어 있으면, 스왑 파일로부터 물리 페이지를 탐색
    • PTE에 아무 값도 없으면, 페이지 캐시를 참조
    • 그래도 못 찾으면, 디스크에 실행 이미지로부터 해당 페이지를 물리 메모리에 로드하고 페이지 캐시에 저장
• vm_area_struct 에서 루틴 주소(vm_area_struct 구조체의 vm_ops 가 참조하는 swapin 포인터)를 변경하면 해당 루틴을 실행 (공유 페이지의 경우 특별한 처리가 필요하므로, swapin 연산이 정의되어 있음)

본 글은 The Linux Kernel 을 정리한 것이며, 출처를 밝히지 않은 모든 이미지는 원글에 속한 것입니다.

가상 메모리(Virtual Memory)

• 물리 메모리의 크기가 제한적인 단점을 극복하기 위해 도입된 방법으로, 메모리를 필요로 하는 프로세스들 사이에 물리 메모리를 공유하도록 하여, 각 프로세스가 실제 물리 메모리보다 큰 메모리를 가질 수 있도록 하는 소프트웨어 기법
• 메모리 관리 서브시스템은 다음과 같은 기능을 제공
  • 넓은 주소공간 프로세스마다 할당된 가상 주소공간은 물리 메모리보다 몇 배 더 클 수 있음
  • 보호 각 프로세스는 독립된 가상 주소공간을 가지기 때문에, 어떤 프로세스도 다른 프로세스에게 영향을 줄 수 없음
  • 메모리 매핑 실행 이미지와 데이터 파일을 프로세스의 주소공간에 매핑시켜 실제로 필요할 때 물리 메모리에 로드
  • 공정한 물리 메모리 할당 프로세스들이 물리 메모리를 공정하게 공유할 수 있도록, 현재 실행중인 프로세스에게 메모리를 할당
  • 공유 가상 메모리 서로 다른 프로세스들은 동일한 물리 메모리 영역을 각자의 주소공간에 매핑해서 사용 가능
• 프로세스들은 물리 메모리를 공유하기 위해 각자의 페이지 테이블(Page Table)을 가지며, 페이지 테이블 엔트리(Page Table Entry, PTE)는 매핑된 가상 메모리 주소에 대응하는 물리 메모리 주소를 포함
  • CPU가 프로세스를 실행하면서 접근하는 메모리 주소는 모두 가상 메모리 주소이며, 가상 메모리 주소로 접근할 때 페이지 테이블을 이용하여 물리 메모리 주소로 변환
  • 주소 변환을 쉽게 하기 위해, 메모리는 페이지(Page)라는 작은 단위로 나뉘는데 모든 페이지들은 같은 크기 (보통 4KB나 8KB)
  • 각 페이지는 페이지 프레임 번호(Page Frame Number, PFN)로 식별 가능하며, 가상 메모리에서는 가상 페이지 프레임 번호(Virtual PFN, VPFN)라고 함
  • 가상 주소는 가상 페이지 프레임 번호와 해당 페이지에서의 오프셋으로 구성되며, 이 오프셋은 물리 페이지에서도 동일
  • 페이지 크기는 2의 제곱수인데, 그 이유는 주소 변환을 할 때 비트 마스킹과 쉬프트 연산으로 쉽게 처리하기 위함
• 주소 변환 과정
  • CPU가 가상 주소를 메모리 관리 장치(MMU)에게 전달
  • MMU가 가상 주소로부터 VPFN과 페이지 오프셋을 추출하여 페이지 테이블에서 VPFN으로 인덱싱
  • MMU는 엔트리에서 물리 페이지 프레임 번호(PFN)를 얻음
  • PFN와 페이지 크기를 곱하여 물리 메모리에서 베이스 주소를 계산한 뒤, 베이스 주소에서 페이지 오프셋을 더하여 실제 물리 메모리의 위치로 접근

• 페이지 테이블은 3가지 정보를 포함
  • 유효 플래그 PTE가 유효한지를 나타내며, 유효하지 않다면 페이지 폴트(Page Fault) 발생
  • 물리 페이지 프레임 번호 VPFN 에 대응하는 물리 페이지 인덱스
  • 접근 제어 정보 해당 페이지가 가지고 있는 읽기/쓰기/실행 권한
• 페이지 폴트(Page Fault) 프로세스가 물리 메모리에 매핑되지 않은 가상 페이지에 접근하는 것
• 접근 제어(Access Control) PTE는 프로세스가 허용되지 않은 방식으로 물리 메모리에 접근하는 것을 막기 위해 접근 제어 정보를 포함 (접근 제어 정보는 프로세서마다 다름)
  • 예를 들어, 쓰기 권한이 없는 위치(코드 영역)에 쓰려는 경우, 실행 권한이 없는 위치(데이터 영역)에서 실행하려는 경우
  • 대부분 프로세서는 커널 모드와 유저 모드를 지원하며, 유저 모드에서 실행 중일 때 커널 코드나 자료구조에 접근할 수 없음
• 페이지 테이블을 이용하면 가상 메모리는 물리 메모리에서 페이지 단위로 임의의 순서로 배열될 수 있음. 즉, 가상 페이지들은 물리 메모리에서 어떤 특정 순서로 존재할 필요가 없음
• 대부분 범용 프로세서들은 물리 주소 모드와 가상 주소 모드를 제공하는데, 물리 주소 모드에서는 페이지 테이블이 필요 없기 때문에 주소 변환을 하지 않음. 커널 코드는 물리 모드에서 실행(물리적 주소 공간에 바로 매핑)되도록 링크되어 있음

요구 페이징(Demand Paging)

• 실행중인 프로그램이 현재 사용하는 가상 페이지만을 물리 메모리에 로드하는 것
  • 예를 들어, DB 프로그램이 DB에 검색할 때, DB의 모든 내용이 메모리에 로드될 필요는 없으며, 검색할 데이터 레코드들만 필요. 즉, DB 프로그램에서 새로운 레코드를 추가하는 것을 처리하는 코드를 메모리로 읽어들일 필요는 없을 것
• 프로세스의 페이지 테이블에서 VPFN으로 엔트리를 찾았을 때, 해당 엔트리에 대응하는 물리 페이지가 없다면 페이지 폴트(Page Fault)가 발생하고, 프로세스는 리눅스 커널에게 폴트가 발생한 가상 주소와 폴트의 원인을 통보
  • 가상 주소가 프로세스의 가상 주소공간 내 유효하지 않다면, 커널은 SIGSEGV 시그널(세그멘테이션 폴트)을 프로세스에게 전달 (프로세스가 그 시그널에 대한 핸들러를 정의하고 있지 않다면 기본 동작으로 프로세스는 종료됨)
  • 가상 주소가 프로세스의 가상 주소공간 내 유효하다면, 커널은 폴트가 발생한 가상 페이지를 디스크의 실행 이미지에서 찾아서 물리 메모리에 로드한 뒤, 페이지 테이블에 PTE를 추가
    • 이 과정은 디스크에 접근하기 때문에 시간이 걸리므로, 그 시간동안 다른 프로세스를 실행
    • CPU는 페이지 폴트가 발생했던 기계어 명령부터 재실행 (아래 그림의 7번)

• 스와핑(Swapping) 프로세스의 가상 페이지를 물리 메모리에 로드할 때 빈 물리 페이지가 없는 경우, 기존 물리 페이지를 제거하여 공간을 마련하는 과정
  • 커널은 물리 메모리에서 더티 페이지(dirty page, 변경된 페이지)를 제거할 때, 내용을 보존하기 위해 스왑 파일(swap file)에 페이지를 저장
  • 스왑 알고리즘(swap algorithm)은 어떤 페이지를 제거하거나 스왑할 지 결정하는데, 반복적인 스왑으로 디스크에 접근하느라 커널이 다른 일을 하지 못하는 쓰래싱 상태(thrashing)를 피하는 것이 중요
  • 따라서, 효율적인 스왑 알고리즘은 프로세스가 현재 사용하고 있는 페이지들의 집합(작업 집합)을 모두 물리 메모리에 있게 함
  • 페이지 교체 알고리즘으로 Least Recently Used(LRU) Page Aging 기법을 사용
  • 페이지마다 나이(age)가 있고, 페이지가 자주 접근될수록 젊어지고, 적게 접근될수록 나이가 드는 구조
  • 나이든 페이지는 스와핑의 좋은 후보이며, 연결 리스트로 구현됨 (사용된 페이지를 참조하는 노드는 리스트의 맨 뒤로 이동하며, 결국 리스트의 맨 앞에 있는 노드는 가장 적게 참조된 페이지를 가리키게 됨, 리스트가 꽉 차면 맨 앞의 노드를 제거)

캐시(Cache)

• CPU가 메모리에 접근하는 것은 디스크보다는 빠르지만 시간이 걸리는 작업이기 때문에, 커널은 메모리 관리와 관련하여 몇 가지 캐시를 사용. 하드웨어 장치에 접근하는 횟수를 줄임
• 버퍼 캐시(Buffer Cache) 디스크에 데이터를 읽어오거나 쓰기 전에, 블럭 디바이스 드라이버가 데이터 버퍼들을 저장하기 위해 사용
• 페이지 캐시(Page Cache) 디스크에서 메모리로 페이지들을 읽어들일 때 디스크 접근 횟수를 줄이기 위해 파일의 논리적인 내용을 페이지 단위로 저장하는 용도

• 스왑 캐시(Swap Cache) 더티 페이지들만 저장하는 디스크 파일
  
  • 스왑 파일에 기록된 이후 페이지가 더 이상 변경되지 않았다면, 그 페이지가 다음에 스왑 아웃(메모리 → 디스크)될 때는 이미 스왑 파일에 동일한 내용이 있으므로 디스크에 기록하지 않고 폐기
  • 스와핑이 자주 발생하면, 불필요하고 값비싼 디스크 연산을 많이 줄일 수 있음
  • 반면, 변경된 페이지는 스왑 아웃할 때마다 다시 스왑 파일에 기록
• 하드웨어 캐시(Hardware Cache) 페이지 테이블 엔트리(PTE)를 저장하는 용도로 CPU 내부에 존재하는 저장공간이며, 변환 참조 버퍼(Translation Look-aside Buffers, TLB)라고도 함
  • TLB는 시스템의 여러 프로세스로부터 PTE의 복사본을 저장
  • 프로세서는 항상 (메모리에 있는) 페이지 테이블을 직접 읽는 것이 아니라, PTE를 필요로 할 때마다 TLB에서 페이지에 대한 변환 결과를 가져옴 (CPU에서 메모리보다 가까우므로 속도가 빠름)
    • CPU가 요청한 PTE에 대한 TLB 엔트리를 찾지 못하면, 커널에게 TLB를 찾지 못했다는 신호(TLB miss)를 보냄
    • 커널은 주소 변환을 위해 새로운 TLB 엔트리를 생성해서 추가
    • 예외 처리 이후, CPU는 같은 가상 주소 변환을 재시도
    • TLB Hit으로 처리 (아래 첫번째 그림은 TLB Hit, 두번째 그림은 TLB Miss)

• 캐시는 관리하는데 더 많은 시간과 공간을 사용해야 하며, 캐시가 망가지는 경우 시스템이 죽는다는 단점이 존재

3단계 페이지 테이블

• 리눅스 커널은 3단계 페이지 테이블을 사용하며, 가상 주소는 각 단계의 페이지 테이블에서의 오프셋을 포함
• 1단계 페이지 테이블의 경우, 페이지 글로벌 디렉토리(PGD)의 주소에 가상 주소에 포함된 오프셋을 더해서 엔트리를 탐색
• 매 단계마다 오프셋으로 페이지 테이블 엔트리를 찾아서, 엔트리에 저장된 페이지 프레임 번호에 페이지 크기를 곱해 다음 페이지 테이블의 베이스 주소를 계산
• 마지막 페이지 테이블의 경우, 엔트리에 저장된 PFN은 물리 페이지 프레임 번호이며, 베이스 주소에 가상 주소의 마지막 바이트 오프셋을 더해 실제 물리 메모리 주소를 계산
• 커널을 실행하는 플랫폼은 커널이 특정 프로세스의 페이지 테이블을 탐색할 수 있도록 하는 매크로들을 지원해야 함
  • 인텔 x86은 2단계 페이지 테이블을 지원하며 AMD의 x86-64는 4단계 페이지 테이블을 지원, 그러나 리눅스 커널은 동일한 페이지 테이블 처리 코드를 사용