Move Fast

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

시그널(Signal)

• 하나 이상의 프로세스들에게 비동기적인 이벤트(asynchronous event)를 전달하기 위해 사용
  • 키보드 인터럽트로부터 발생
  • 프로세스가 존재하지 않는 가상 메모리 영역에 접근하는 경우 (SIGSEGV 시그널이 프로세스에게 전달됨)
  • 쉘이 자식 프로세스에게 작업 관리 명령을 보내는 경우: kill -NumSignal PID

• 기본적으로 시그널 핸들러는 다음과 같은 4가지 동작 중 하나를 수행
  • terminate 프로세스 종료
  • ignore 시그널 무시
  • terminate and core dump 프로세스가 종료되고 그 당시의 레지스터와 메모리를 덤프
  • stop or continue 프로세스 중단 또는 계속 실행
• 프로세스의 실행을 중단시키는 SIGSTOP 시그널과 프로세스를 종료시키는 SIGKILL 시그널은 무시할 수 없음
  • 그 외에 모든 시그널은 무시할 수 있음
• 시그널이 여러 개 전달될 때, 임의의 순서로 전달되며, 핸들러로 처리할 때도 임의의 순서로 진행됨
• 프로세스는 시스템 콜을 이용해서 시그널을 전달하거나 핸들링하는 등 시그널 관련 작업을 수행할 수 있음

• 커널은 프로세스의 task_struct 구조체에 저장된 정보를 사용해서 시그널 기능을 처리
  • 시그널의 개수는 프로세서의 워드(word) 크기에 제한되는데, 32비트 프로세서는 32개, 64비트 프로세서는 64개
  • 현재 처리 대기중인 시그널은 sig 항목에 비트를 1로 설정 (정수 자료형은 2^32 또는 2^64 비트, 프로세서마다 다름)
  • 블럭된 시그널은 signal_blocked 항목에 비트를 1로 설정
    • SIGSTOP과 SIGKILL을 제외한 모든 시그널은 블럭킹 가능
    • 블럭된 시그널이 발생하면, 블럭을 해제할 때까지 대기 상태
    • 블럭이 해제되면 핸들러가 호출됨
    • 핸들러가 종료되면, 커널은 blocked 항목을 원래 값으로 되돌려 놓기 위해 정리용 루틴을 호출하는데, 여기서 시그널을 받은 프로세스의 콜 스택(call stack)에 저장된 원래 blocked 값을 꺼내서 복구
    • 여러 개의 시그널 핸들러가 호출되는 경우, 이 루틴들은 콜 스택에 쌓여서 마지막에 정리용 루틴이 호출되도록 함
  • 시그널 핸들러는 sigaction 구조체에서 참조하며, 각 시그널의 핸들러는 signal_struct 의 action 이라는 sigaction 구조체 배열에 시그널 번호를 인덱스로 저장되어 있음
    • sigaction 구조체에서 sigflags 를 이용해 해당 시그널을 무시할 지 또는 커널이 시그널을 대신 처리할 지를 결정
    • 커널에 위임한다는 것은 기본 동작을 의미 (위의 4가지 동작 중 하나)
    • 시그널 핸들러는 시스템 콜로 변경할 수 있으며, 이 시스템 콜은 해당 시그널의 sigaction과 blocked 변수를 수정
• 시그널 관련 시스템 콜 (예제 코드)
  • kill() 은 다른 프로세스로 시그널을 전달(프로세스 종료 아님)하며, signal() 은 해당 프로세스의 시그널 핸들러를 변경

• 커널과 관리자는 모든 프로세스에게 시그널을 전달할 수 있지만, 사용자 프로세스는 같은 uid, gid를 갖는 프로세스에게만 시그널을 보낼 수 있음
• 프로세스는 시그널을 받았을 때, 블럭킹 모드가 아니고 인터럽트 허용 상태에서 대기중이면, 실행중 상태가 되고 실행 큐에 추가되어 스케줄링에서 자신의 차례가 올 때까지 기다림 (실행중 상태라고 해서 CPU가 실행하는 것은 아님)
• 시그널은 즉시 프로세스에게 전달되는 것이 아니라, 해당 프로세스가 시스템 콜을 호출하고 유저 모드로 돌아오기 직전에 커널이 sig 항목과 signal_blocked 항목을 검사해서 해당 시그널이 블럭킹 모드가 아닐 때, 그 프로세스에게 전달
• 시그널 처리 코드는 현재 블럭되지 않은 시그널에 대해 sigaction 구조체에서 참조하는 루틴이 호출된 것
  • 만약 커널 기본 동작이 아닌 사용자가 정의한 함수를 가리킨다면, 유저 모드에서 그 함수를 호출하기 위해 프로세스의 스택과 레지스터를 조작 (for 최적화)
  • 프로세스의 프로그램 카운터를 시그널 처리 루틴의 주소로 지정하고 핸들러로 전달할 인자를 스택에 추가하거나 레지스터에 저장

• 자식 프로세스를 생성할 때 SIGSTOP 시그널과 SIGCONT 시그널이 부모에서 자식으로 전달됨

파이프(Pipe)

• 파이프는 두 프로세스의 양방향 통신을 지원하는 메커니즘으로, 각 프로세스가 임시로 만들어진 VFS inode를 2개(읽기/쓰기)의 file 구조체에서 가리키는 것으로 구현 (여기서 VFS inode는 물리 페이지를 참조)
• file 구조체는 파일 연산 루틴 배열을 참조하는 포인터(f_op)를 가지며, 이는 파이프에 쓰는 함수에 대한 포인터와 파이프로부터 읽는 함수에 대한 포인터를 포함
  • 파이프에 쓰고 읽을 때는 표준 라이브러리 함수를 사용하며, 함수에는 파일 기술자(file descriptor)를 넘김
  • 즉, f_op 가 참조하는 루틴 배열에는 파일 읽기, 쓰기 함수들이 있음
• 두 프로세스는 하나의 파이프에 대해 각각 읽는 프로세스와 쓰는 프로세스가 되며, 반대로 쓰는 프로세스와 읽는 프로세스가 되려면 파이프를 추가로 생성해야 함 (하나의 파이프에 동시에 읽고 쓰는 것이 가능하나 한 쪽이 쓰고 자신의 것을 읽으면 다른쪽은 블락됨)
  • C언어에서 파이프는 부모-자식 관계의 두 프로세스일 때 아래 그림처럼 사용할 수 있는데, fd가 반드시 서로 반대인 것으로 읽고 써야하며, 서로 다른 프로세스의 경우 FIFO라는 named pipe를 사용해야 함
  • 그러나, 아래 그림과 같은 상황은 권장되지 않으며, 양방향 통신은 파이프 2개를 사용할 것
  • 파이썬에서는 Pipe() 객체를 생성하면 양방향으로 통신이 되는데 내부적으로는 위 설명과 같이 구현되어 있음

• 쓰는 프로세스가 파이프에 쓴 데이터는 공유 데이터 페이지에 복사되고, 읽는 프로세스는 공유 데이터 페이지로부터 자신의 가상 페이지로 데이터를 복사
• 쓰는 중에 읽어 오는 것을 막기 위해 파이프에 대한 접근은 동기화해주어야 하며, 읽는 프로세스와 쓰는 프로세스는 동시에 접근하지 않고 반드시 순서를 지킬 수 있도록 락(lock)과 대기 큐(waiting queue), 시그널(signal) 등을 사용
• 파이프에 접근하는 프로세스는 다른 프로세스가 파이프에 락을 걸지 않았고 이용 가능한 상태(파이프에 쓰기 요청한 바이트들을 모두 쓸 공간이 있거나, 읽어올만큼 충분한 데이터가 있다면)라면 파이프에 락을 걸고 요청을 처리
  • 쓰는 프로세스는 쓸 데이터 바이트들을 프로세스의 주소공간에서 공유 데이터 페이지로 복사
  • 읽는 프로세스는 읽어올 바이트만큼 데이터들을 공유 데이터 페이지에서 프로세스의 주소공간으로 복사
• 만약 파이프에 락이 걸려 있거나 이용 불가능한 상태라면, 현재 프로세스는 해당 파이프의 VFS inode 에서 참조하는 대기 큐(waiting queue)에 추가되어 대기 상태가 되고, 다른 프로세스를 실행하기 위해 스케줄러를 호출
  • 대기 중인 프로세스는 인터럽트 허용 상태이며, 파이프가 이용 가능할 때 시그널을 받아 실행됨
  • 읽는 프로세스는 파이프를 이용할 수 없다면 오류를 반환하는, 논블럭킹(non-blocking)으로 실행될 수 있음 (블럭킹 모드이면 대기 큐에 추가되어 잠듬)
• 두 프로세스가 파이프를 통한 작업을 종료하면, 파이프의 VFS inode와 공유 데이터 페이지는 폐기됨
• 리눅스는 지정 파이프(named pipe)도 지원하며, FIFO 구조로 파이프에 먼저 쓴 데이터는 읽을 때 먼저 나옴
  • FIFO는 임시적으로 생성된 것이 아니라 파일 시스템에 실재 존재하는 것이며, mkfifo 명령으로 생성 가능
  • 프로세스는 접근 권한만 있다면 FIFO를 자유롭게 사용 가능
  • 리눅스는 FIFO에 쓰는 프로세스가 없을 때 다른 프로세스가 이를 읽기 위해 열려고 하는 것이나, FIFO에 쓰는 프로세스가 FIFO에 쓰기를 하기 전에 읽는 프로세스가 읽으려고 하는 것 모두 처리함
  • 이를 제외하면, FIFO는 거의 파이프와 똑같은 방법으로 취급되며, 같은 자료구조와 연산을 사용

시스템 V IPC 메커니즘

• 시스템 V IPC 방법들은 모두 똑같은 인증 방법을 공유
  • 메시지 큐, 세마포어, 공유 메모리가 해당됨
• 프로세스는 커널에 시스템 콜로 이들 자원을 가리키는 유일한 참조 식별자(reference identifier)를 전달하여 접근 가능
• IPC 객체들에 접근할 때는 접근 권한(access permission)을 검사하며, 이는 파일에 대한 접근을 검사하는 것과 유사한 방식
  • IPC 객체에 대한 접근 권한은 시스템 콜을 통하여 객체의 생성자에 의해 지정
• IPC 객체를 나타내는 커널 자료구조는 프로세스의 소유자와 생성자의 uid, gid와 이 객체에 대한 접근 모드(소유자, 그룹, 그밖에 대한) 및 IPC 객체의 키를 가진 ipc_perm 이라는 자료구조를 포함
  • 키는 시스템 V IPC 객체의 참조 식별자를 찾는 한 방법으로 사용되며, 공용키와 개인키가 존재
  • 공용키를 사용한다면, 시스템에 있는 어떤 프로세스든지 권한 검사를 통과한다면 시스템 V IPC 객체에 대한 참조 식별자를 찾을 수 있음
  • IPC 객체는 키가 아니라 참조 식별자로만 참조 가능 (키로 참조 식별자를 찾으면, IPC 객체로 참조하는 것)

메시지 큐(Message Queue)

• 하나 이상의 프로세스가 메시지를 쓰고, 하나 이상의 프로세스가 메시지를 읽으면서 여러 프로세스 사이의 양방향 통신을 지원

• 커널은 msqid_ds 구조체로 하나의 메시지 큐를 기술하며, 메시지 큐를 생성할 때마다 msqid_ds 구조체를 생성하여 msgque 배열에 이 구조체를 추가
• msqid_ds 구조체는 ipc 변수로 ipc_perm 구조체를 참조하며, 이 큐에 들어온 메시지에 대한 포인터들과 큐에 마지막으로 접근한 시간같은 큐 수정시간 등을 나타내는 변수들을 포함
• 메시지 큐는 2개의 대기 큐를 가지며, 각각 읽는 프로세스들과 쓰는 프로세스들을 관리 (요청 순서대로 대기 큐에서 기다림)

• 프로세스가 큐에 접근할 때 프로세스의 euid, egid를 ipc_perm 구조체에 있는 모드(mode)와 비교하는 것으로 접근 권한을 검사
• 쓰는 프로세스의 경우, 메시지는 프로세스의 주소공간에서 msg 자료구조로 복사되고 메시지 큐의 마지막에 추가됨
  • 각 메시지에는 응용프로그램 지정 타입(프로세스간에 서로 약속한 타입)을 포함
  • 쓸 수 있는 메시지의 개수와 길이는 제한되며, 큐에 공간이 부족하면 프로세스는 메시지 큐의 쓰기 대기 큐(msqid_ds의 *wwait 항목)에 추가되고, 실행할 새로운 프로세스를 선택하기 위해 스케줄러를 호출 (큐에서 공간이 생기면 대기중에 실행중 상태가 됨)
• 읽는 프로세스는 타입에 관계없이 큐에 있는 첫번째 메시지를 가져올 지, 또는 특정한 타입을 가진 메시지를 선택할 지 고를 수 있음
  • 읽을 수 있는 메시지가 없으면, 프로세스는 메시지 큐의 읽기 대기 큐(msgq_id의 *rwait 항목)에 추가되고, 실행할 새로운 프로세스를 선택하기 위해 스케줄러를 호출 (큐에서 읽을 메시지가 생기면 대기중에서 실행중 상태가 됨)
• 메시지 큐가 활용되는 적절한 예로, 생산자-소비자 패턴(Producer-Consumer Pattern)이 있음

세마포어(Semaphore)

• 동시에 여러 프로세스가 접근할 때, 한 프로세스만 실행해야 하는 중요한 코드가 있는 임계 영역(critical section)을 구현할 때 사용
• 세마포어의 가장 단순한 형태는 메모리의 어떤 위치에 있는 변수로, 그 값을 검사하고 설정(test and set)하는 연산을 하나 이상의 프로세스가 할 수 있고, 검사 및 설정 연산이 비선점형으로 절대 중단되지 않도록 원자적으로 처리하는 것
• 프로세스는 세마포어의 값을 감소시키거나 증가시킬 수 있으며, 다른 프로세스에 의해 세마포어가 특정 값이 되면, 현재 접근하는 프로세스는 대기 상태가 되어 세마포어가 이용가능할 때 깨어남
  • 예를 들어, 임계 영역에 접근할 때 프로세스 A가 세마포어를 1 -> 0 (특정 값) 으로 바꾸면, 다른 프로세스들은 감소시킬 때 (테스트 과정에서) 0 -> -1 이 되면서 세마포어가 0이 아니게 되므로 대기 상태가 됨
  • 프로세스 A가 작업을 끝내고 임계 영역을 벗어날 때 세마포어를 0 -> 1로 바꾸면, 대기 중이던 프로세스들이 실행중 상태가 되어 세마포어 값을 A처럼 바꾸고 작업
  • 세마포어도 종류가 있는데, 이진 세마포어는 흔히 뮤텍스로 알려져 있으며, 2가지 상태만 가지고, 위의 예시는 카운팅 세마포어라고 해서 임계 영역에 접근할 프로세스 수를 제한하는 것으로 특정 값은 대개 0이고, 최초 지정한 숫자만큼 프로세스가 임계 영역에 접근할 수 있음 (접근할 때마다 카운트 값이 증가하고 빠져나가면 감소)
• 커널 코드에서 세마포어 값을 검사하는 함수는 try_semop()이며, 세마포어 값을 바꾸는 함수는 do_semop()
• 세마포어 객체는 semid_ds 구조체로 기술되며, semary 배열에 semid_ds 구조체의 포인터가 저장되어 있음
• semid_ds 구조체는 sem_nsems 만큼의 세마포어 배열에 있으며, sem_base가 배열의 주소를 가지고 있고, 배열의 각 원소는 sem 구조체이며 이 구조체가 하나의 세마포어를 나타냄
• 세마포어 배열을 관리할 수 있는 권한을 가진 프로세스들은 시스템 콜로 한 번에 여러 개의 세마포어 연산을 지정할 수 있음
  • 각 연산은 세마포어 (배열에서의) 인덱스, 연산 값(현재 값에 추가될 숫자), 플래그 세트라는 3가지 인자를 받음
• 커널은 모든 세마포어 연산을 성공할 수 있는지 테스트하며, 연산 값을 세마포어의 현재 값에 더한 값이 0 이상이거나, 연산 값과 세마포어의 현재 값이 모두 0일 때, 이 연산은 성공한 것으로 간주
• 만약 연산 중 하나라도 실패하면, 플래그에 블럭킹 모드를 지정한 경우 프로세스는 중단되고, 커널은 수행해야 할 세마포어 연산의 상태를 저장한 뒤, 현재 프로세스를 대기 큐에 추가. 이후 다른 프로세스를 실행하기 위해 스케줄러를 호출
  • 세마포어의 대기 큐는 sem_pending 포인터로 관리되며, 프로세스를 추가할 때 새 sem_queue 구조체를 할당하여 큐에 추가
• 만약 모든 연산이 성공하여 프로세스가 중단될 필요가 없다면, 세마포어 배열의 올바른 세마포어에 그 연산을 적용
  • 이후, 대기 큐에서 기다리며 중단되어 있는 프로세스들에 대해 검사하기 위해 sem_pending 포인터로 하나씩 세마포어 연산을 테스트. 연산을 성공하면 sem_pending 이 참조하는 큐에서 해당 프로세스의 sem_queue 구조체를 제거하고 세마포어 배열에 있는 해당 세마포어에 연산을 적용
  • 대기 중인 프로세스를 실행중 상태로 변경하여 다음 스케줄링에서 선택되게 함
  • sem_pending 에서 깨울 프로세스가 없을 때까지 위 과정을 반복
• 데드락(deadlock) 한 프로세스가 임계지역에 들어가면서 세마포어의 값을 바꾸었는데 프로세스가 잘못되거나 강제로 종료되어서 이 임계지역을 빠져나가지 못한 경우
  • 세마포어 배열에 대한 조정 리스트(sem_pending_last 포인터가 참조하는 큐)를 관리함으로써 방지
  • 이런 조정을 적용하면 그 프로세스가 세마포어 연산을 수행하기 이전의 상태로 되돌아감
  • 조정에 대한 것은 sem_undo 구조체로 기술하고, 이들은 semid_ds 구조체와 프로세스의 task_struct 구조체의 큐에 추가됨
  • 세마포어 배열에 있는 세마포어에 연산을 적용하면 연산 값을 반대로 한 값이 이 프로세스의 sem_undo 구조체에 저장됨
  • 기본적으로 프로세스가 sem_undo 구조체를 생성하지 않더라도 커널은 필요하면 생성함
  • 프로세스가 종료될 때, 커널은 sem_undo 구조체들을 가지고 세마포어 배열에 조정을 적용. 만약 세마포어 객체가 지워지면 프로세스의 task_struct의 큐 되어 있는 sem_undo 자료구조는 유지되나 세마포어 정리 코드는 sem_undo 구조체를 무시
• 데드락은 한 프로세스가 필요로 하는 자원을 다른 프로세스가 사용하고 있어 대기 상태로 갔는데, 나중에 그 프로세스가 앞의 프로세스가 점유하고 있는 자원을 필요로 하게 되어 프로세스들이 서로 상대가 자원 사용을 종료하기만을 기다리게 되는 상태일 때도 발생
  • 프로세스가 세마포어를 이용하여 임계지역으로 들어간 후 다시 세마포어를 얻으려고 할 때 자원 해제 등의 예외처리를 하거나, 꼬이지 않도록 점유하는 순서를 보장하여 해결 가능

• RE: 쓰레드간 동기화는 뮤텍스(mutex)를 사용하며, 프로세스간 동기화는 세마포어(semaphore)를 사용

공유 메모리(Shared Memory)

• 동일한 물리 메모리가 매핑된 가상 페이지를 이용하여 둘 이상의 프로세스가 통신하며, 각 프로세스의 페이지 테이블에는 공유 메모리 페이지의 PTE가 존재
• IPC 객체와 마찬가지로 공유 메모리 영역으로의 접근은 키에 의해 제어되고 접근 권한을 검사함. 단, 한 번 메모리가 공유되면 프로세스들이 이를 어떻게 사용하는지에 대해서 아무런 검사도 하지 않음. 따라서 세마포어 같은 것으로 메모리 접근을 동기화해야 함
  • 공유 메모리를 생성한 프로세스가 이 메모리에 대한 접근권한과 키가 공용인지 개인용인지 제어
  • 처음 공유 메모리를 생성하면 가상 주소공간에만 존재하는데, 생성한 프로세스가 충분한 권한이 있다면 물리 메모리에 로드 가능
• 공유 메모리는 shmid_ds 구조체로 기술되며, shm_segs 배열에 이 구조체를 저장. 각 shmid_ds 구조체는 공유 메모리 영역이 얼마나 큰지, 얼마나 많은 프로세스가 사용하고 있으며, 공유 메모리가 프로세스의 주소공간에 어떻게 매핑되어 있는지에 대한 정보를 포함
• 메모리를 공유하길 바라는 각 프로세스들은 시스템 콜을 통해 가상 메모리에 연결
  • 공유 메모리를 기술하는 새로운 vm_area_struct 구조체 생성
  • 가상 주소공간에 공유 메모리의 위치를 지정하거나 운영체제가 임의의 빈 공간을 지정하도록 할 수 있음 (인자로 결정)
  • 새로 만들어진 vm_area_struct 구조체는 shmid_ds 구조체에서 참조하는 vm_area_struct 구조체 리스트에 추가
  • vm_next_shared 와 vm_prev_shared 포인터들은 공유 메모리의 vm_area_struct 구조체들을 서로 연결하는데 사용
• 가상 메모리에 연결하는 과정(메모리 매핑)은 실제 물리 메모리를 할당하지 않으며, 처음으로 프로세스가 여기에 접근하려고 할 때 물리 페이지를 할당(요구 페이징)
  • 프로세스가 공유하고 있는 가상 메모리의 한 페이지에 처음으로 접근을 시도하면 페이지 폴트가 발생
  • 페이지 폴트를 처리할 때, 해당 vm_area_struct 구조체를 탐색하는데, 이 구조체에 공유 가상 메모리 관련 루틴 포인터가 존재
  • 페이지 폴트 핸들러는 shmid_ds 구조체에서 PTE를 찾아보고, 공유 가상 메모리의 해당 페이지에 대한 PTE가 없으면 물리 메모리 할당 후 PTE 추가
  • 다음 프로세스가 이 메모리에 접근하려고 할 때 페이지 폴트가 발생하는데, 공유 메모리의 vm_area_struct 에 있는 페이지 폴트 핸들러는 이전에 새로 할당된 물리 페이지에 대한 PTE를 이 프로세스의 페이지 테이블에 추가, shmid_ds 구조체에도 추가
  • 즉, 공유 메모리의 어떤 페이지에 접근하는 첫번째 프로세스는 물리 메모리를 할당하고, 다른 프로세스들이 여기에 접근할 때는 이를 자신의 가상 주소공간으로 접근할 수 있도록 페이지 테이블에 추가하는 것
• 공유 메모리로의 연결을 끊을 때는 해당 프로세스의 vm_area_struct 구조체들은 shmid_ds 구조체에서 제거되고 해제된 후, 페이지 테이블이 갱신됨
• 마지막으로 메모리를 공유하고 있던 프로세스가 연결을 끊으면 물리 메모리에 존재하고 있는 모든 공유 메모리 페이지들은 해제되고, 이 공유 메모리를 나타내던 shmid_ds 구조체도 해제됨

본 글은 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단계 페이지 테이블을 지원, 그러나 리눅스 커널은 동일한 페이지 테이블 처리 코드를 사용