Software Research Center

Presentation on theme: "Software Research Center"— Presentation transcript:

1 Software Research Center
임베디드 리눅스 커널 2006년 1학기 Moon Hae Kim (金 文 會) Software Research Center Konkuk University

2 Konkuk University Software Research Center
임베디드 리눅스 커널 내부 구조 Linux v2.4.18을 기준으로 다음과 같은 사항을 설명 프로세스와 스레드 시스템 호출, 문맥 교환, 인터럽트 처리 프로세서 스케줄링 메모리 관리 인터럽트 처리 파일 시스템 리눅스의 부팅 과정 시그널 처리 커널 동기화 커널 디버깅 Konkuk University Software Research Center

3 Konkuk University Software Research Center
메모리 관리 리눅스 운영체제의 메모리 관리 CPU에 MMU(Memory Management Unit)가 있는 경우 기본적으로 페이징(paging)을 기반으로 한 가상 메모리 시스템(Virtual Memory System)을 지원 가상 메모리 시스템 페이지(page) 단위의 할당 및 맵핑을 위한 페이징과 실제 메모리보다 큰 공간 제공을 위한 스왑핑(swapping)으로 구성 Paging Swapping 페이지 단위로 메모리에 적재 되고 가상 주소가 실제 주소로 맵핑되므로 프로세스의 주소 공간의 메모리 배치에 연속적 할당이 필요 없어 편리한 메모리 관리가 가능하다. 임베디드 시스템의 경우도 여러 개의 프로세스나 스레드가 동적으로 실행되어야 하는 경우에 편리하다 실제 물리적 메모리의 크기에 관계 없이 CPU의 형태에 따른 주소공간을 사용할 수 있다. 예를 들면 32 bit 주소 공간을 제공하는 CPU의 경우 4GB의 공간에서 커널이 가상적으로 차지하는 1GB의 공간을 제외한 3GB의 공간에 해당되는 크기의 프로그램을 실행 시킬 수 있다. 다만 이 경우는 하드 디스크와 같은 swap 장치가 필요하고 속도가 느려 지기 때문에 임베디드 시스템에서는 가상 메모리를 사용하여도 스왑핑은 사용하지 않는 것이 보통이다 Konkuk University Software Research Center

4 Konkuk University Software Research Center
명령어 수행 시마다 계산되는 CPU에 의해 산출되는 가상 주소는 MMU H/W가 커널이 각 프로세스 마다 준비하는 페이지 테이블 (page table)을 바탕으로 실제 물리 메모리 주소로 변환한다 물론 프로세스가 커널 모드 실행일 때에는 커널 영역을 위한 페이지 테이블을 사용하게 된다 프로세스나 커널이 요구하는 동적 페이지 할당을 위해 사용 가능한(free) 페이지들의 풀을 유지 커널의 물리적 free page 풀은 buddy area와 slab cache라는 공간 구조에 사용자 프로세스를 위한 가상 공간의 할당 영역은 힙(heap) 공간에 유지 커널이 일단 부팅되면 초기 단계에 가상 메모리 시스템이 활성화되어 커널 자신도 가상 메모리 시스템 하에서 실행되는 것이 보통이다 Konkuk University Software Research Center

5 프로세스와 커널의 가상 주소 공간과 물리적 주소 공간
가상 메모리 시스템 하에서 사용자는 실제 메모리의 레이아웃에 관계없이 연속된 프로세스의 가상 주소 공간을 사용하고 접근하게 된다 예를 들면 정수 변수 ix의 주소인 &ix를 프린트해 보면 이는 가상 주소 공간에서의 값이며 실제 프로세스의 물리적 메모리 레이아웃에 따른 변화가 없음을 알 수 있다 프로세스는 CPU에 의한 실행 중에 사용자 모드 실행과 시스템 콜 수행에 따른 커널 모드 실행을 반복하므로 가상 메모리의 주소 공간은 실행 프로세스의 영역과 커널의 영역으로 구성되어야 한다 실제 물리적 메모리에는 여러 프로세스들 각각 다른 곳에 배치되지만, 가상 주소 공간에서 사용자 프로세스는 모두 동일한 주소의 영역을 사용하고, 커널을 이들이 공유함에 주의하기 바란다 Konkuk University Software Research Center

6 Konkuk University Software Research Center
32 bit 주소인 경우 프로세스 가상 공간의 구성 그림의 두 개의 프로세스는 같은 가상 공간을 사용하지만 실제 물리적 공간은 다른 곳으로 맵핑된다 그 외에도 프로세스를 위한 가상 주소 공간은 memory mapped file, shared memory, shared library 공간 등 여러 형태가 있다 Konkuk University Software Research Center

7 Konkuk University Software Research Center
프로세스의 공간에 대한 설명 Text Area CPU가 실행하는 프로세스의 프로그램 명령어로 구성되는 영역으로 읽기 전용으로만 접근이 허용되므로 프로세스의 실행 중 변화가 없다 Data Area 프로그램의 전역 변수 공간으로 초기화된 데이터 영역(data)과 초기화되지 않은 데이터 영역(bss)으로 구분된다 Heap Area 프로세스 실행 중에 malloc, new 등의 동적 메모리 할당 요구를 수용하는 데이터 영역 공간이다. break 값에 의해 그 끝을 나타내며, CPU에 따라 다르지만 일반적으로 공간 부족 시에 주소가 커지는 방향으로 확장된다. Stack Area 함수 내에서 할당되는 automatic 변수들이나 함수 호출 시에 run-time stack frame(함수가 호출될 때의 반환 주소, 환경정보 등) 등으로 할당되는 공간이다. CPU에 따라 다르지만 일반적으로 주소가 작아지는 방향으로 확장된다 Konkuk University Software Research Center

8 페이징(Paging) 하에서의 가상 주소의 물리 주소 맵핑
CPU에 따라 가상 주소의 실질 주소 맵핑은 세그멘테이션(segmentation)과 페이징(paging)을 혼용하거나 페이징만을 사용함 Page 가상 공간을 동일한 크기의 공간 셀(cell)로 분할 하여 이 단위로 메모리에 분산 배치하기 위한 단위이다 Segment 텍스트, 데이터, 스택이나 함수 등과 같인 논리적인 단위로 가상 공간을 분할 하는 단위로 가변 크기를 가진다. 단 세그먼트는 16bit 구조의 CPU가 사용되던 시절, 실제 메모리 공간이 가상 공간보다 큰 문제가 발생하였고, 이런 경우 물리적 공간을 많이 크게 활용하기 위하여, 프로그램의 논리적 세그먼트(16bit 주소 공간)들을 실제 공간에 여러 개 배치하여 사용하던 기법에서 기인하는 방식이다. 그러나 가상 주소 공간이 물리적 공간보다 커 짐에 따라 시그멘테이션(segmentation)은 실질적으로 그 의미가 약해졌으며 실제로 x86 계열은 시그멘테이션을 사용하지만 각 시그먼트가 가상 공간 전체를 공유 사용(overlapping)하는 형태로 되어 있어 실질적으로는 페이징만을 사용하는 것과 마찬가지이다. Konkuk University Software Research Center

9 Konkuk University Software Research Center
페이지 테이블(page table) 가상공간의 페이지는 물리적 메모리에 페이지 단위로 분산 배치되므로 반드시 가상 주소의 실질 주소로의 맵핑이 필요하다. 이를 위한 커널 자료 구조가 프로세스 마다 주어지는 페이지 테이블(page table)이다 pte(page table entry) 페이지 테이블 의 각 페이지 마다의 자료를 pte(page table entry)라 하며, pte는 해당 페이지의 메모리 적재 여부(valid bit), 실질 메모리 주소(frame 주소) 등을 가진다 예) CPU가 생성하는 가상 주소를 32bit라 가정하고 페이지 의 크기를 4KB라 하면 하위 12 bit는 페이지 내부에서의 오프셋(offset)이 되고 그 상위 부분은 페이지의 번호(가상 주소 공간에서의 순번)가 된다 MMU는 가상 주소의 상위 20bit 페이지 번호를 현재 실행 중인(running) 페이지 테이블의 실질 메모리의 프레임(frame) 주소로 변환한다 이 과정에서 오프셋은 불변이다 Konkuk University Software Research Center

10 Konkuk University Software Research Center
맵핑 과정에서 MMU가 페이지 테이블을 이용하려면 맵핑의 기준이 되는 페이지 테이블 자체의 주소는 가상 주소가 아닌 실질 주소를 알아야 한다 그러나 CPU 들이 주소 공간이 커짐에 따라, 모든 프로세스들의 페이지 테이블들은 그 자체로도 크기가 커져 커널이 페이지 테이블들을 물리적 공간에 동적으로 직접 할당하는 것에는 어려움이 발생하게 되었다 이에 따라 페이지 테이블을 가상 공간에 할당하기 위하여 2단계 또는 3단계 페이지 테이블 맵핑이 등장하였다 2 단계 맵핑 각 페이지 테이블 페이지의 물리적 주소를 가지는 page directory table이(물리적 공간에 배치) 사용 3 단계 맵핑 64 bit 주소 기계의 경우에 사용 page global directory table, page middle directory table, page table을 사용 Konkuk University Software Research Center

11 Konkuk University Software Research Center
2 단계 페이지 테이블 맵핑 (32 bit 주소 체계) Konkuk University Software Research Center

12 Konkuk University Software Research Center
3 단계 페이지 테이블 맵핑 (64 bit 주소 체계) Konkuk University Software Research Center

13 i386 경우의 가상 주소 공간과 실질 주소 공간의 맵핑
커널과 하나의 프로세스로 구성된 가상 주소 공간은 타겟 시스템의 메모리 레이아웃에 따라 각각 다른 모양으로 적재(맵핑) 된다 3GB의 주소에서 시작한 커널 가상 공간은 부팅 시에 실제 메모리의 첫 부분 2MB에 연속적으로 배치됨을 알 수 있다 그 이외의 실제 메모리 공간은 사용자 프로세스의 의 공간, 커널의 free page 공간(연속 할당), 커널의 vmalloc을 위한 할당 공간(불연속 할당) 및 커널 스택(stack) 등으로 맵핑 됨을 보여 주고 있다 Konkuk University Software Research Center

14 Konkuk University Software Research Center
리눅스 커널의 가상 메모리 관리 구조 리눅스 커널의 가상 메모리 관리 시스템 커널의 구성 요소 중에서도 프로세스 로딩, 파일 시스템 및 맵핑 등과 관련되어 가장 복잡한 구조를 가진다 가상 메모리 관리 시스템은 그 역할 별로 다음과 같이 구분할 수 있다 가상 공간 관리 물리적 공간 관리 및 demand paging, swapping 관리 맵핑 (hat: HW address translation layer) 관리 Konkuk University Software Research Center

15 Konkuk University Software Research Center
가상 공간 관리 프로세스의 가상 공간 내의 영역을 관리한다 즉, text, data, stack, heap 등의 기본 영역에 관한 가상 공간에서의 위치, 크기, 속성, 관련된 파일 등에 관한 정보를 종합 관리한다 관련 된 주요 커널 자료 구조는 mm_struct와 vm_area_struct로 mm_struct는 전체 프로세스 영역에 대한 자료를 vm_area_struct는 텍스트(text), 데이터(data), 힙(heap), 스택(stack) 등과 같은 각 영역에 대한 자료를 저장한다 Konkuk University Software Research Center

16 프로세스의 가상 공간 관리 구조체 mm_struct
struct mm_struct { struct vm_area_struct * mmap; // list of VMAs rb_root_t mm_rb; // red back tree; GNU AVL tree 대용 // vm area 가 많은 경우 빨리 search하기 위해 struct vm_area_struct * mmap_cache; // last find_vma result pgd_t * pgd; // page directory table atomic_t mm_users; // How many users with user space? atomic_t mm_count; // How many references to "struct mm_struct" int map_count; // number of VMAs struct rw_semaphore mmap_sem; // for locking spinlock_t page_table_lock; // Protects task page tables and mm->rss struct list_head mmlist; // List of all active mm's. These are globally strung // together off init_mm.mmlist, and are protected by mmlist_lock unsigned long start_code, end_code, start_data, end_data; unsigned long start_brk, brk, start_stack; unsigned long arg_start, arg_end, env_start, env_end; unsigned long rss, total_vm, locked_vm; // rss : 할당된 frames, // locked_vm : lock되어 swapout 될 수 없는 page의 수 unsigned long def_flags; unsigned long cpu_vm_mask; unsigned long swap_address; unsigned dumpable:1; /* Architecture-specific MM context */ mm_context_t context; // i386 segmemt info. Not used }; Konkuk University Software Research Center

17 프로세스의 가상 공간 영역별 관리 구조체 vm_area_struct
struct vm_area_struct { struct mm_struct * vm_mm; // The address space we belong to. unsigned long vm_start; // Our start address within vm_mm. unsigned long vm_end; // The first byte after our end address within vm_mm. struct vm_area_struct *vm_next; // linked list of VM areas per task, sorted by address pgprot_t vm_page_prot; // Access permissions of this VMA. read/write/execute unsigned long vm_flags; // Flags, listed below. rb_node_t vm_rb; // left & right of red_balck tree /* * For areas with an address space and backing store, * one of the address_space->i_mmap{,shared} lists, * for shm areas, the list of attaches, otherwise unused. */ struct vm_area_struct *vm_next_share; // 같은 inode 에 속하는 vm_area의 list struct vm_area_struct **vm_pprev_share; /* Function pointers to deal with this struct. */ struct vm_operations_struct * vm_ops; // swap또는 fs의 각종 op /* Information about our backing store: */ unsigned long vm_pgoff; // Offset (within vm_file) in PAGE_SIZE units, *not* PAGE_CACHE_SIZE // file 또는 swap에서의 offset? (page 구조를 찾는 key도 됨) struct file * vm_file; // File we map to (can be NULL). text, 초기 data unsigned long vm_raend; // XXX: put full readahead info here. void * vm_private_data; // was vm_pte (shared mem) }; Konkuk University Software Research Center

18 Konkuk University Software Research Center
물리적 공간 관리 리눅스 커널은 프로세스 페이지의 배치, 요구 페이징(demand paging), 스왑핑(swapping) 등을 위해, 실질 메모리의 각 프레임(frame)에 대한 자료를 struct page에 저장 관리한다 struct page stuct page는 공간의 사용 여부, 스왑핑 시의 LRU(Least Recently Used) 적용을 위한 최근 사용 여부, 관련된 process/file page 정보, free area 관리 정보 등을 포함한다 Konkuk University Software Research Center

19 페이지(frame) 관리를 위한 자료 구조체 page
typedef struct page { struct list_head list; // prev and next free area map(buddy), struct address_space *mapping; // The inode (or ...) we belong to. // 1) file map(inode), // 2) swapmap(swap_space) // 3) not mapped : NULL unsigned long index; // Our offset within mapping. (in file or swap) struct page *next_hash; // Next page sharing our hash bucket in the page cache or swap cache hash table. atomic_t count; // sharing // # of ptes + cache pointers // 기본이 1이고 cache에 있으면 ++, shared 이면 ++ unsigned long flags; // atomic flags, some possibly updated asynchronously // DMA. Kernel-reserved, dirty, ref, locked…. // dirty, ref bit은 필요 시 , pte로 부터 copy 된다. struct list_head lru; // Pageout list, eg. active_list or inactive_list; // protected by pagemap_lru_lock !! struct page **pprev_hash; // Complement to *next_hash. // page cache or swap cache struct buffer_head * buffers; // Buffer maps us to a disk block // (buffer cache page) #if defined(CONFIG_HIGHMEM) || defined(WANT_PAGE_VIRTUAL) void *virtual; // Kernel virtual address // (NULL if not mapped, ie. highmem) #endif /* CONFIG_HIGMEM || WANT_PAGE_VIRTUAL */ } mem_map_t; Konkuk University Software Research Center

20 리눅스 커널의 가상 메모리 및 물리적 메모리 관리 체계
Konkuk University Software Research Center

21 Konkuk University Software Research Center
커널의 동적 메모리 할당 커널은 사용자 프로세스 영역 및 관련 자료 구조(task_struct, page table 등)들을 위해 커널 내부에서 사용을 위한 공간 할당을 동적으로 수행한다 커널 내부에서의 사용을 위한 공간 할당은 DMA 등 입출력을 위한 공간 할당, 각 종 buffer나 SW적 cache를 위한 할당 등으로 구성된다 커널의 동적 메모리 할당 방식 원하는 크기 만큼의 공간을 물리적으로 연속된 공간에 할당하는 방식과 커널 가상 공간에 할당하는 불연속 공간 할당으로 구성된다 Konkuk University Software Research Center

22 Konkuk University Software Research Center
커널 내부의 연속 공간 할당 연속 공간 할당을 사용하는 경우 물리적으로 연속되어야 효율성이 증가하는 경우나(hw cache 배려), DMA 입출력 공간과 같은 연속성을 필요로 하는 경우에 사용된다 연속적 공간 할당에 사용되는 커널 내부 함수 get_free_pages, kmalloc, kfree, kmem_cache_alloc 등이 있다 커널은 이러한 함수들을 통한 물리적 메모리 연속할당을 위해 두 개의 free page 관리 시스템을 관리하는데, 이들은 Buddy system과 Slab cache system이다 Buddy system 사용 가능한 물리적 공간을 연속 공간의 크기 별로 유지하는 메모리 공간 자료 구조로, 커널이 요구한 페이지를 할당하거나 이들이 반납될 때, 분할과 통합을 통해 최대 연속된 공간으로 관리하는 커널 최하위의 free 영역 관리 시스템이다 Slab cache system kmalloc 등으로 할당되는 객체(구조체)들이 반납될 때 이를 Buddy 시스템에 반납하지 않고, 객체 별로 유지되는 캐시로 반납하여 다음의 동일 객체 유형 요구 시 빠르게 이를 재활용하기 위한 시스템이다 Konkuk University Software Research Center

23 연속 공간의 동적 할당을 위한 내부 함수와 캐시 시스템의 관계
Konkuk University Software Research Center

24 Konkuk University Software Research Center
커널 내부의 불연속 공간 할당 각 프로세스의 pte, pmd나 프로세스 관련 자료 구조들을 커널 내부에서 할당할 때에는 커널의 가상 공간에서 연속적인 공간을 할당한다 단 이 공간은 가상 공간에서 연속적이므로 실제 메모리에서는 불연속 공간이 될 수 있다 관련 내부 함수들 vmalloc, vfree, vmalloc_area_pages 등이 있다 커널 가상 주소 공간의 VMALLOC_START에서 시작하는 여유 공간에서 각기 할당된 가상 공간은 vm_struct 구조에 의해 관리된다 struct vm_struct { unsigned long flags; void * addr; // virtual address unsigned long size; // 실제 크기 struct vm_struct *next; }; struct vm_struct *vmlist; // vm_struct list of used virtual areas(sorted by addr.),,,, Konkuk University Software Research Center

25 Konkuk University Software Research Center
커널 내부의 불연속 공간 할당 Konkuk University Software Research Center