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 리스트와 해당되는 페이지 테이블들을 셋업하는 과정이며, 이후 요구 페이징에 의해 페이지 폴트가 발생하면 프로그램의 코드와 데이터의 필요한 일부만 물리 메모리에 로드