[sw정글-북] 📚CSAPP 9장-Computer Virtual Memory

Date: 2022.01.09 Updated: 2022.01.09

카테고리: swjungle CSAPP

태그: Computer System swjungle

📚CSAPP 9장-Computer Virtual Memory

🚀노션에서 업데이트 된 내용으로 보기

📚CSAPP 9장 <== 클릭

❗️출처: 하이애나 블로그

📕start

9.1 Pysical and Virtual Addressing

SRAM은 캐시
DRAM은 디스크의 캐시기능을 제공하고
각 프로세스의 주소공간을 보호
VM(virtual machine)이랑 착각 금지
cpu는 가장주소를 받으면, 물리주소로 가서 실제 그 데이터를 뽑아옴
MMU 메모리 관리 유닛
캐싱도구로써 VM이 이용됨

9.2 Address Spaces

결국 VM(Virtual Memory)쓴다는건 캐싱해준다는 이야기
왜 virtual 인가
- cpu한테, 메모리에 모든 정보가 다 있는것처럼 속임, 그리고 막상 필요하면 그 때 들고옴
- 그러니까, 다있다고 뻥카쳐두고, 필요하면 급하게 밖에서(HDD, SDD 혹은 DRAM)정보 들고와서, 내가 이미 가지고있었던 척 할 수 있기 때문에 virtual임
나는 VM(Virtual Machine)이야기하는줄 알고 용어에 혼동이 있어 집중을 제대로 못했음

9.3 VM as a Tool for caching

1부터 200까지 나누었으면 한 단위를 page라고 함
가상메모리는 메인메모리(DRAM)에 있음
가상메모리가 어디에있는지
0으로 되어있는애들은 메인메모리에 복사가 안되어있으니까 page fault가 난다
1로 되어있는 애들은 메인메모리에 복사가 되어있는 애들
Locality때문에 이렇게 사용함
Thrashing이라는 좋지 않은 상황

9.4 VM as a Tool for Memory Management

9.5 VM as a Tool for Memory Protection

접근이 막혀있는 페이지에 접근을 하려고 하면 세그먼트 falut를 주게 됨
SRAM에 저장되어있으면 더 빠를텐데?
SRAM, DRAM 같이씀 그럼 더좋음
더빨리 가고싶어서 CPU칩 안에 작은 캐시를 넣어둠

9.6 Address Translation

TLB에 찾으려고 하는게 바로 있으면 바로 줌, 하지만 없다면? 페이지 테이블 다녀와서 정보를 불러와야함
DRAM에도 물리주소가 존재하고 있음

9.7 Case Study: The Intel Core i7/Linux Memory System

9.8 Memory Mapping

공유매핑, private mapping
수정 내용이 다른 프로세스에도 공유가 된다면 공유 매핑
공유가 되지 않는, 해당 프로세스에만 변경사항이 반영이 된다면 사적 매핑
copy-on-write

9.9 Dynamic Momory Allocation

커널은 힙의 꼭대기가리키는 변수 brk
Allocator는 힙을 다양한 크기의 블록들로 관리
- 각 블록은 allocated되었거나, free한 VM의 연속적인 묶음
- 명시적(explicit)할당기: malloc, calloc, free 등 명령어로 할당
- 묵시적(implicit)할당기: garbage collection처럼 자동 할당반환
- 참고(heap과 stack 모두 RAM)
9.9.1 The malloc and free Functions
- x86기준 할당크기
  - 32비트모드에서 항상 8의 배수
    - 커맨드: gcc -m32
  - 64비트모드에서 항상 16의 배수
- malloc이 문제를 만나면…
  - ex) 할당된곳보다 더 큰 범위 요청하면
  - Null을 리턴함
    - C에서의 NULL
      - 구현정의된 NULL포인터상수로 정의되어있음
      - NULL포인터들의 값을 비교해도 같다고 보장
  - errno를 설정함
- 초기화
  - malloc
    - 리턴하는 메모리를 초기화하지 않음
  - calloc
    - 응용프로그램들이 dynamci memory 초기화 할 때 쓰임
    - malloc 주변의 얇은 wrapper함수임
  - realloc
    - 이전에 할당된 블록의 크기를 변경하려 할 때
  - malloc
    - mmap과 munmap함수를 사용해서 명시적(explicit)으로 힙 메로리 할당 or 반환
    - sbrk는 커널의 brk 포인터에 incr을 더해서 힙을 늘리거나 줄임
      - 성공시 이전의 brk값을 리턴
      - 실패시 -1리턴, errno를 ENOMEM으로 설정해줌
      - incr이 0이면, sbrk는 현재의 brk값을 리턴
      - sbrk를 음수 incr로 호출해도 되긴 됨
        
        하지만… 리턴값(이전의 brk값)이 새로운 힙의 영역을 침범 해버림
  - ptr
    - malloc, calloc, realloc에서 획득한 “할당블록의 시작”을 가리킴
      - 그렇지 않다면, free의 동작 = undefined
      - 더 나쁜 상황: 아무것도 리턴 안해서, 잘못된걸 알릴수도 없음
9.9.2 Why Dynamic Memory Allocation?
- 동적메모리 할당을 사용하는 이유
  - 프로그램 돌리기 전에, 자료구조의 크기를 알 수 없는 경우들이 있기 때문
  - ex)
    - 하드코딩으로 크기를 할당하고, 더 큰 파일을 읽으려고 함
    - 더 큰 값으로 하드코딩하고 다시 컴파일해야됨😇
    - 배열을 런타임에 동적으로 할당하는게 좋음
9.9.3 Allocator Requirements and Goals
- Explicit Allocator는 strict한 rule을 가지고 있음
  - 임의의 요청 순서 처리
  - 요청에 즉시 응답
  - 힙만 사용
  - 블록 정렬
  - 할당된 블록 수정금지
- 위처럼 빡빡한 제한사항이 있음에도 불구하고 개발자는 처리량과 메모리 이용을 최대화하려는 trade-off관계의 성능목표를 달성하기위해 노력
  - 해당 목표:
    - 처리량 최대화: 빠른시간 안에 많은 요청 처리
    - 이용량 최대화: 가상메모리는 유한한 자원임, 최대한 많이 넣을 수 있으면 더 좋음
    - 처리량최대화 ↔ 이용량 최대화는 trade-off임, 잘~ 균형잡아서 만들어봐야함
9.9.4 Fragmentation Issues
- 내부단편화
  - 할당된 블록이 데이터 자체보다 더 클 때 일어남
- 외부단편화
  - 할당요청을 만족시킬 수 있는 메모리
    - 만약 현 상태에서, 6을 요청하면 한방에 들어감
    - 하!지!만? 8을 요청한다면? 가용할 수 있는 블록은 8칸이 되지만, 이걸 처리할 수 있는 단일 가용블록은 없음
  - 내부단편화보다 훨씬 어려움
  - 이전 요청의 패턴과, 미래의 요청 패턴에도 의존하기 때문
  - 외부단편화 무서우니까 할당기 설계할 때, 작은블럭 여러개보다는 ⇒ 큰블럭 한두개로 쓰는게 더 편함
9.9.5 Implementation Issues
- 가장 멍청한 할당기
  - 블록만 지정해주고, free()는 아무것도 실행하지 않음
- 그럼 이슈가 아~주 많음, 다음과같은 4가지 이슈들을 생각 해 볼만함
  - 가용블록 구성
    - 어떻게 가용 블록을 지속적으로 추적할지
  - 배치
    - 새롭게 할당된 블록배치를 위해, 가용블록을 어떻게 선택할지
  - 분할
    - 새롭게 할당한 블록배치한 후, 남은 부분들로 무얼 할지
  - 연결
    - 방금 반환된 블록으로 무얼 할지
9.9.6 Implicit Free Lists
- 모~든 할당기는 블록경계를 구분
- 할당된 블록과 가용블록을 구분하는 데이터 필요
  - 이 정보는 블록 내에 내장되어 있음
  - 한 블록은 1워드 헤더, 데이터, 패딩으로 구성
    - Header
      - 블록의 크기(패딩 포함), 블록이 할당되었는지 가용할 수 있는 상태인지를 인코딩
      - 더블워드 크기이면, 32비트까지 가능, 하위 3비트가 남음
        
        32bit에서는 8씩 할당
        
        그렇다면, (11111)5칸 필요, 따라서 8-5 = 3칸남음
        
        여기 3칸에 별도 정보 입력
        
        1bit를 이용하여 RB트리의 컬러를 입력 해 줄 수도 있음
    - Payload
      - 프로그램이 malloc을 불렀을 때, 요구한 데이터가 따라옴
    - Padding
      - 외부 단편화 극복을 위한 전략용 혹은 정렬 요구사항을 만족하기 위해 등
      - 다양한 이유를 위해 필요 할 수 있음
  - implicit free list
    - 가용블록(free block)이 implicitly하게 header내 필드에 연결되기 때문
    - 장점 단순하다
    - 단점 가용블록(free-block)과 할당된블록(allocated-block)을 찾는데 linear하게 시간복잡도가 올라감
  - 할당기의 최소블록크기 결정조건(두가지)
    1. system alignment requirement
    2. block format
      - 따라서… 위의(9.36)그림에서 2칸(2워드=8바이트)단위로 할당되고 해제됨
      - 왜냐면 그게 1,2번조건을 통해 최소블록 크기로 설정되었기 때문

Untitled

9.9.7 Placing Allocated Blocks
- N byte를 요청하면, 할당기는 해당 내용을 저장하기 충분한 free-block을 리스트에서 검색
- 검색방법 3가지
  - First fit
    - 처음부터 검색하다가 크기가 맞는 첫번째 free-block 선택
    - 장점 리스트 마지막에 가장 큰 free-block을 남겨둠
    - 단점 리스트 앞부분에 작은 free-block을 남겨둠(검색시간 증대)
  - Next fit
    - 이전 검색이 종료된 지점에서 검색을 시작, 크기맞는 첫번째 free-block선택
    - 장점 first-fit의 단점에 대한 대안(검색 더 빠르다)
    - 단점 first-fit보다 더 나쁜 메모리 이용도를 가진다는 연구도 있음
  - Best fit
    - 모~든 블록 검색하고, 크기가 맞는 블록중 가장 작은 블록 선택
    - 장점 일반적으로 더 좋은 메모리이용도를 가짐
    - 단점 implicit free list처럼 단순한 방법을 사용할 때, 힙을 다검색해야됨😢
      - 힙을 전부 검색 안해도 되는 segregated free list를 뒤에서 알려줌
9.9.8 Splitting Free Blocks & 9.9.9 Getting Additional Heap Memory
- 가용블록을 찾았다면? 어떻게 할당할까?
  - 블록 전체 사용
    - 장점 간단하고 빠름
    - 단점 내부단편화 생김
  - 블록 일부 사용
    - 일부를 allocated-block으로 처리, 나머지는 새로운 free-block
- 요청한 블록을 찾을 수 없다면?
  - 인접한 free-block을 연결해서 더 큰 free-block을 만들어 본다
  - 구석구석을 다 돌아다니며 블록을 모아도 모자라면, 할당기는 sork함수를 호출해서 힙메모리 더 달라고 요청
  - 요약
    - 야! 블럭 120개 내놔
    - ⇒ 블럭 120개짜리… 없는데요?
    - 그럼 있는거 다 내놔
    - ⇒ 호주머니까지 다 털어서 모아도 120 못만듬
    - ⇒ sork함수 호출
9.9.10 Coalescing Free Blocks
- free() 해줄때, 옆에 free-block있으면 같이 묶어줌
- false fragment
  - 안묶어주면, free-block이 연속적으로 크게 있음에도 불구하고 할당해줄 곳이 없다고 착각함
  - 그럼 할당 요청해도 할당 못받으니 당연히 안좋음
- 따라서, false fragment를 막기 위해 블럭끼리 연결coalescing 해주어야 함
- coalescing
  - 즉시연결
    - 블럭이 freed될 때 마다, 바로바로 연결하는 방법
  - 지연연결
    - 일정 시간 이후 연결하는 방법
    - 할당요청이 실패하고 나서 연결시킬 수도 있음
    - 중간중간 생각 나면 연결시켜 줄 수도 있음
    - 빠르게 할당하려면 당연히 지연연결 해주는게 좋음
9.9.11 Coalescing with Boundary Tags
- Header를 footer(경계태그)에 복사해둠
- 4가지 케이스 있음
  - case1: 이전 이후 모두 이미 allocated되어있음
  - 그냥 그놈만 free시켜주면 됨
  - case2: 이전 블록은 allocated되어있지만, 이후 블록 free함
  - free하고, 뒤에놈이랑 같이 묶어줌
  - case3: 이전 블록은 free하지만, 이후 블록 allocated되어있음
  - free하고, 앞에 놈이랑 같이 묶어줌
  - case4: 이전 이후 모두 free함
  - free하고 앞뒤 녀석들 모두 묶어줌
- 이전 블록이 free할 때
  - 이전 블록의 footer에서 size정보가 필요함
  - (allocated되어있는)현재블록의 앞뒤에, 이전블록의 free/allocate 여부를 저장하면 현재 블록의 footer가 필요가 없어짐
  - free block은 여전히 footer가 필요함
9.9.12 Putting It together: Implementing a Simple Allocator
- 간단한 할당기 만들어보자
  - memlib.c 패키지에서 제공되는 메모리시스템 모델 사용
  - mem_init()
    - 힙에 allocate한 가상메모리를 big-double-word배열로 모델링
  - mem_heap과 mem_brk사이의 바이트들은 allocated된 가상메모리를 나타냄
  - mem_brk다음에 오는 바이트들은 미할당 가상메모리를 나타냄
  - 할당기는 mem_sbrk()를 호출해서 추가적인 힙 메모리 요청
- mm.c 소스파일-세가지 함수로 구성
  - mm_init()
    - 할당기 초기화
    - 성공시 0 리턴
    - 실패시 -1 리턴
    - 아래 그림과 같은 포맷으로 만듬
    - Prologue block
      - 초기화되고나면 절대 free되지 않음
      - 프롤로그블록 앞에 padding이 1칸(4byte) 들어오고, 그 다음 2칸(8byte=word size)짜리 프롤로그 블록이 뒤따라서 들어오는 것임
      - 프롤로그 블록 뒤에, 우리가 malloc(), free() 함수를 통해 꽂아넣는 regular block들이 들어오게 되는 것
    - Epilogue block
      - heap은 언제나 Epilogue block으로 끝남
      - 헤더만으로 구성된 블록
    - 프롤로그와 에필로그 블록은 coalescing을 하는 동안, edge condition을 없애기위한 장치임
    - 할당기는 1개의 static 전역변수를 사용하여 항상 프롤로그 블록을 가리킴
      - 꿀팁: 프롤로그 블록 대신 그 다음블록 가리키게 하면 조금 더 빨라짐
  - *mm_malloc()
  - mm_free()
9.9.13 Explicit Free Lists
- implicit free list를 사용해서 간단한 할당기 만들었음
- 할당시간이 O(n)이기 때문에 구림
- 이미 free된 블록들을, explicit한 자료구조로 구성하는 방법
- pred랑 succ로 이중연결된 free-list를 만들 수 있음(아래 그림)
- 위처럼, 해당 free block을 명시적(explicit)으로 표시를 해주는 것
- 여전히 coalesce를 위해 boundary tag 필요함
- free block만 봐도 된다는 점이 장점인 것
- free block들에 표기하니까… ⇒ payload area에 원하는 정보를 그냥 가져다 박아두어도 됨
  - next에는 다음 free block을
  - prev에는 나를 카리켰던 놈을 다시 가리키면 됨
  - 사진 출처(CMU)
- 구현방법
  - allocating
    - 엄청 쉬움
    - 삽입 후, place시키고 free block에 다음 free block 다시 새겨줌
  - freeing
    - free할때는 훨씬 allocate할 때 보다 훨씬 어려움
    - allocate ⇒ 그냥 이중연결리스트 돌면서 찾아서 할당하면 됨
    - free ⇒ free되고 나면, 기존의 이중연결리스트에서 적절한곳에 넣어주어야 함
    - 아래와같은 두가지 방법이 있음
      - LIFO
        
        새롭게 생긴 free block! 그냥 리스트의 맨 앞에 넣어준다
        
        장점 수행시간 O(1)
        
        단점 false fragement가 아래의 방법보다 심함
      - Address-ordered policy
        
        free-block들을 주소순으로 계속 유지시킴
        
        장점 false fragment 적음
        
        단점 검색해야됨
    - 방법 별 케이스 스터디(coalescing과 연결)
      - LIFO-case1
        
        루트와 연결, previous 없음
      - LIFO-case2
        
        중간에 잘 있던 애들이, coalesce되면서 1빠따로 가게될 경우
        
        이경우 previous block을 먹음
        
        free되면서, 기존에 있던 애들도 끊어주고, 1빠따로 가면서 생기는 새로운 연결도 해주어야 함
      - LIFO-case3
        
        중간에 잘 있던 애들이, coalesce되면서 1빠따로 가게될 경우
        
        이경우 next block을 먹음
        
        case2번과 symmetric한 케이스
        
        (case2번 이해했으면 안봐도 됨)
        
        LIFO-case4
        
        (cmu교수피셜)이해하기 가장 쉬운 경우임, 하지만 코드짤때 ~~(ㅈㄴ)~~어렵다고 함
        
        앞뒤 다 뚫려있을 때,
- Time complexity
  - implicit
    - 할당
      - O(전체블록수)
    - free
      - O(1)
  - explicit
    - (first fit기준) 할당시간 감소
      - O(전체블록수) → O(free블록수)
    - free
      - LIFO
        
        O(1)
      - Address ordered
        
        O(n)
        
        그런데 얼마 안걸릴듯? 쓰다보면, 앞뒤로 블락들이 있을테니(중선추측)
9.9.14 Segregated Free Lists
- 다수의 가용리스트를 유지하며, 각 리스트는 거의 동일한 크기의 블록들을 저장함
- 블록의 크기들을 size class라고 하는 동일 클래스의 집합들로 분리
  - ex1) 2의 제곱으로 블록크기 집합을 관리
    - {1}, {2}, {3, 4}, {5—8}, • • •, {1,025-2,048}, {2,049-4,096}, {4,097-oo}
  - ex2) 크기가 작은 친구들 따로 할당하고, 큰블럭 따로 관리
    - {1}, {2}, {3}, … , {1,023}, {1,024}, {1,025-2,048}, {2,049-4,096}, {4,097-oo}
- 간단한 Segregated Storage
  - 적절한 free list 검색
  - 할당요청을 만족하기위해 절대 분할하지 않음
  - 리스트가 비어있으면, 추가적인 메모리 요청
  - 블럭을 반환할 때, 이 블럭을 free list의 맨 앞으로 삽입
  - 장점
    - allocating과 freeing 모두 O(1)
    - 오버헤드가 거의 없음
  - 단점
    - 외부, 내부단편화에 취약
      - (어떤 블럭은 평생 할당이 안됨ㅠㅠ)
- Segregated Fits
  - 특징
    - free list array를 관리함
    - GNU malloc패키지같은 수준의 할당기에서 자주 선택됨
      - 검색이 전체 힙이 아닌, 힙의 특정 부분에 제한되기 때문
      - 메모리 유틸 개선(얼마나 효율적으로 사용하는지)
        
        first-fit이 결국 best-fit검색하는 행위와 같음
  - 구현
    - 크기에 맞는 블럭을 위해, first-fit방식으로 검색
      - 블럭을 찾으면…
        
        블럭을 분할하고, 나머지를 free-list에 삽입함
      - 블럭을 찾지 못하면…
        
        다음크기에서 free-list검색, 블럭 찾을 때 까지 반복
        
        그래도 못찾으면, 힙 추가 요청하고 블럭 할당
- Buddy Systems
  - Segregated Fits의 크기클래스가 2^n인 방식
  - 범용으로 쓰기에는 무리가 있음, 2^n이라는 크기가 내부 단편화를 유발하기 때문
  - 특수한 경우에는 효과를 거둘 수 있음