크래프톤 정글 TIL : 0922

lazyArtisan·2024년 9월 22일
TIL
0

정글 TIL

목록 보기
84/147

📝 배운 것들

🏷️ BSS, Data 영역

bss 영역

  • Block Started by Symbol
  • 초기화되지 않은 전역/정적 변수 (혹은 0이나 NULL로 초기화)
  • 나중에 초기화 된다고 해도 메모리 주소가 변하진 않음

data 영역

  • 초기화된 전역/정적 변수
  • 디스크에 저장된 값을 메모리로 로드함

🏷️ VM 영역별 페이지 구분

익명 페이지(Anonumous Pages) 할당

  • 힙 : 동적 메모리 할당에 쓰임
  • 스택 : 함수 호출 시 지역 변수, 함수 인자, 리턴 주소 등을 저장
  • 익명 메모리 매핑 : mmap()에서 MAP_ANONYMOUS 플래그 사용하여 할당, 프로세스 간 통신(IPC)나 메모리 풀(pool) 관리에 사용됨. 파일과 연결되지 않아 데이터가 지속 안 됨.

파일 기반 페이지(File-backed Pages) 할당

  • 텍스트 : 실행 파일의 기계어 코드 저장
  • 데이터 : 초기화된 전역/정적 변수 저장
  • BSS : 초기화 안된 전역/정적 변수 저장, 프로그램 시작 시 자동으로 0으로 초기화됨.

🏷️ 구조체(Struct)와 공용체(Union)

구조체(Struct)

  • 구조: 모든 멤버 변수는 독립적으로 고유의 메모리 공간을 갖는다
  • 메모리 할당: 구조체의 전체 크기는 각 멤버 변수의 크기를 모두 더한 값

공용체(Union)

  • 구조: 공용체는 여러 멤버 변수를 같은 메모리 공간을 공유하여 저장한다
  • 메모리 할당: 공용체의 크기는 가장 큰 멤버 변수의 크기에 의해 결정된다
구분구조체(Struct)공용체(Union)
메모리 할당각 멤버가 독립적인 메모리 공간을 가짐가장 큰 멤버만큼의 메모리 공간을 공유
동시 접근모든 멤버 변수에 동시에 접근 가능한 번에 한 멤버만 접근 가능
메모리 크기멤버 변수들의 크기의 합가장 큰 멤버 변수의 크기
사용 예시여러 데이터를 동시에 저장하고 사용할 때여러 데이터 중 하나만 사용할 때

🏷️ page와 page frame

https://cs.stackexchange.com/questions/11667/what-is-the-difference-between-a-page-of-memory-and-a-frame-of-memory

Short version: "page" means "virtual page" (i.e. a chunk of virtual address space) and "page frame" means "physical page" (i.e. a chunk of physical memory).


🏷️ write-through, write-back

https://cyber0946.tistory.com/81

write-through : CPU가 데이터를 사용하면 캐시에 저장되게 되는데, 데이터가 캐시 됨과 동시에 주기억장치 또는 디스크로 기입되는 방식을 지원하는 구조의 캐시이다. 즉, 캐시와 메모리 둘다에 업데이트.

write-back : CPU 데이터를 사용할 때 데이터는 먼저 캐시로 기록되는데, 캐시 내에 일시적으로 저장된 후에 블록 단위에 캐시로부터 해제되는 때(캐시 안에 있는 내용을 버릴시)에만 주기억장치 또는 보조기억장치에 기록되는 방식이다. 즉, 데이터를 쓸 때 메모리에는 쓰지 않고 캐시에만 업데이트를 하다가 필요할 때에만 주기억장치나 보조기억장치에 기록하는 방법.


🏷️ callback, 비동기 작업

비동기 작업 : 다른 함수 끝나는 거 기다리지 않고 같이 병렬적으로 실행되는거

callback : 특정 작업이나 함수가 끝났을 때 실행되도록 미리 전달된 함수


🏷️ 비트맵

왼쪽에 있는거 오른쪽처럼 만드는거

cardianlity : 유니크한 값이 얼마나 많이 있느냐
cardinality 높으면 bitmap 적합하지 않음

칼럼의 값들을 행으로 만든 다음 해당되면 1, 아니면 0으로 할당.


🏷️ 해시 테이블

https://mangkyu.tistory.com/102

넣으려는 값에 대응되는 인덱스를 함수 넣어서 구한다.

  • Division Method: 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다.( 주소 = 입력값 % 테이블의 크기) 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있다.
  • Digit Folding: 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법이다.
  • Multiplication Method: 숫자로 된 Key값 K와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산을 해준다. h(k)=(kAmod1) × m
  • Univeral Hashing: 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법이다.

겹치면 분리 연결법(Separate Chaining) 또는 개방 주소법(Open Addressing)

  1. 분리 연결법

동일한 인덱스 가진 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장

  1. 개방 주소법

비어있는 해시 테이블의 공간을 활용

  • Linear Probing: 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.
  • Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식이다.
  • Double Hashing Probing: 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.


🖥️ PintOS

🔷 Virtual Memory

📌 깃북 정리

include/vm/vm.h

enum vm_type : 페이지 종류 지정?
struct page : 이미 정의돼있는 거 건들지 말라고 함

페이지와 관련된 동작들을 page_operations라는 구조체로 묶어놓음

vm/vm.c

페이지 만들고 싶으면 직접 만들지 말고 vm_alloc_page_with_initializer나 vm_alloc_page을 통해서 해라

thread에는 supplemental_page_table라는 타입을 가진 spt라는 변수가 있는데, 이건 쓰레드가 갖고 있는 모든 가상 메모리를 위한 테이블. 비어있어서 직접 만들어야 됨.

spt_find_page : spt에서 가상 주소를 찾아서 페이지를 돌려준다.

include/vm/uninit.h

struct uninit_page : Lazy loading(demand paging)을 위한 구조체. 아직 물리 주소 매핑 안된 놈을 의미.

vm/uninit.c

page fault 나기 전 페이지 상태인 uninit page에 대한 함수들 있음

vm/anon.c

파일과 관련 없는 non-disk image(익명 페이지)에 대한 함수들 있음.
페이지가 빠질 때 스왑 영역으로 빠지게 해야될듯.

vm/file.c

file-backed file object들에 대한 함수들.
페이지 들어올 때 파일에서 읽어오고 빠질 땐 파일에 저장한다.

devices/block.c

는 없고 disk.c로 바뀌었다고 함.

페이지 Pages

이 이미지에서 보여주는 것은 가상 주소가 4단계의 페이지 테이블 탐색을 통해 물리 주소로 변환되는 과정입니다. 각 단계에서 9비트씩 사용하여 페이지 테이블을 탐색하고, 마지막 12비트는 물리적 페이지에서의 오프셋을 나타냅니다.

  • PML4 → PDPT → PD → PT → 물리적 페이지
  • CR3 레지스터는 PML4 테이블의 시작 주소를 가리킵니다.

이 과정은 Intel x86-64 아키텍처의 가상 메모리 관리 방식에서 필수적인 부분이며, 이를 통해 CPU는 가상 주소를 물리적 메모리에 매핑할 수 있습니다.

PML4 (Page Map Level 4)는 Intel x86-64 아키텍처에서 사용하는 4단계 페이지 테이블 구조의 최상위 단계입니다.

  • PML4 테이블은 64비트 가상 주소의 상위 비트(47~39 비트)를 사용하여 PML4 항목(PML4E)을 선택합니다.
  • PML4E는 다음 단계인 PDPT(Page Directory Pointer Table)로의 포인터를 포함합니다. 이는 2단계 페이지 테이블 탐색으로 이어집니다.
  • PML4 테이블 자체는 CR3 레지스터에 의해 관리되며, CR3는 PML4 테이블의 시작 주소를 가리킵니다. 프로세스가 컨텍스트 스위칭될 때 CR3 레지스터가 새롭게 설정됩니다.

그렇게 하면 느려진다고 아는데 왜 굳이 여러 단계로 나누는 거임

  • 단일 레벨 페이지 테이블을 사용할 경우, 64비트 주소를 관리하려면 각 페이지마다 해당하는 물리 주소를 저장해야 하므로 엄청난 크기의 테이블이 필요합니다.
    • 예를 들어, 64비트 주소 공간을 커버하려면 512TB의 메모리가 페이지 테이블로만 필요할 수 있습니다.
  • 따라서 여러 단계로 나누는 것이 메모리 사용을 절약하고 유연한 관리를 가능하게 합니다.

스파스한(드문) 주소 공간에서 메모리 절약

가상 메모리 주소 공간은 모든 영역을 사용하는 것이 아니라, 특정 부분만 실제로 사용될 수 있습니다. 이 경우, 여러 단계를 나누면 사용하지 않는 부분에 대한 페이지 테이블을 할당할 필요가 없어 메모리 공간을 절약할 수 있습니다.

성능과 메모리 사용 효율성 간의 균형

  • 페이지 테이블을 여러 단계로 나누는 것은 추가적인 메모리 참조를 요구하기 때문에 성능이 다소 떨어질 수 있습니다. 그러나 현대 CPU는 이러한 성능 저하를 완화하기 위해 TLB(Translation Lookaside Buffer)라는 고속 캐시를 사용하여 페이지 테이블 참조를 캐싱합니다.

  • TLB는 페이지 테이블의 여러 단계 참조에서 발생할 수 있는 성능 저하를 줄이는 데 중요한 역할을 합니다. 자주 사용하는 페이지에 대한 매핑 정보를 TLB에 저장함으로써, 페이지 테이블을 반복적으로 참조할 필요 없이 빠르게 주소 변환이 가능합니다.

프레임 Frames

                          12 11         0
    +-----------------------+-----------+
    |      Frame Number     |   Offset  |
    +-----------------------+-----------+
              Physical Address

물리 프레임(physical frame) 또는 페이지 프레임(page frame)이라고 불리는 프레임은, 물리 메모리 상의 연속적인 영역이다.
페이지와 동일하게, 프레임은 페이지 사이즈여야 하고 페이지 크기에 정렬되어 있어야 한다.
그러므로 64비트 물리주소는 프레임 넘버와 프레임 오프셋(또는 그냥 오프셋)으로 나누어질 수 있다.

x86-64는 물리 주소 접근 못하게 하는데 Pintos는 커널 가상 메모리를 물리 메모리에 직접 매핑해서 해결한다.
커널 가상 메모리 n번째 페이지는 물리 메모리 n번째 프레임에 매핑돼있다.
커널 가상 메모리 통하면 프레임에 접근할 수 있다.

Pintos는 물리 주소와 커널 가상 주소 사이를 변환하는 함수 제공한다.

aliases : 동일한 프레임을 참조하는 두개 이상의 페이지

CPU는 페이지 테이블의 accessed bit를 1로 설정하고, 페이지에 쓸 때마다 dirty bit를 1로 설정.
CPU는 이 비트들을 절대 0으로 다시 리셋하지 않지만 운영체제는 이를 0으로 리셋할 수도 있음.

aliased 된 프레임에 접근이 발생하면, access bit와 dirty bit는 해당 프레임에 접근한 페이지의 페이지 엔트리 에서만 갱신됨.
해당 프레임을 참조하는 다른 페이지(aliases) 의 access bit와 dirty bit는 업데이트 되지 않음.

페이지 테이블 Page Tables

Pintos는 threads/mmu.c안에 페이지 테이블을 관리하는 코드를 제공

                           +----------+
          .--------------->|Page Table|-----------.
         /                 +----------+           |
        |   12 11 0                               V  12 11 0
    +---------+----+                         +---------+----+
    | Page Nr | Ofs|                         |Frame Nr | Ofs|
    +---------+----+                         +---------+----+
     Virt Addr   |                            Phys Addr    ^
                  \_______________________________________/

페이지 넘버는 페이지 테이블을 통해 프레임 넘버로 변환되고
프레임 넘버랑 같이 있는 오프셋으로 물리 주소 획득

구현 개요

  1. Supplemental page table 보조 페이지 테이블 : 페이지 테이블을 보조해서, 페이지 폴트 핸들링이 가능하도록 해줍니다.
  2. Frame table 프레임 테이블 : 물리 프레임의 eviction policy(직역하면 “쫓아내기 정책”)를 효율적으로 구현하도록 해줍니다.
  3. Swap table 스왑 테이블 : 스왑 슬롯이 사용되는 것을 추적합니다.

구현을 위한 가능한 선택지로는 배열, 리스트, 비트맵, 해시 테이블



⚔️ 백준

📌 29773 2023년은 검은 토끼의 해 (Hard)

def combi4(cnt): return cnt*(cnt-1)*(cnt-2)*(cnt-3)/24
def combi3(cnt): return cnt*(cnt-2)*(cnt-3)/6

def case(cnt):
    # 해당 자리수를 보존한 경우의 수와 보존하지 않은 경우의 수들을 합쳐야 함
    # 456789를 예로 들면, (1) 4 그대로, (2) 1 떨어진 3과 1, (3) 그냥 2, (4) 아예 사라짐    
    # (1), (2), (3)에 대한 경우의 수를 구했으면 다음 자릿수인 (4)로 넘어가야 함
    if cnt == 4: return 1
    global N
    L=len(N)
    num=int(N[L-cnt])
    result=0
    if num!=2:
        result+=case(cnt-1)*combi4(cnt-2) # (1) 4 그대로 
    if num!=1: 
        result+=(num-2)*combi4(cnt-1)*(9**(cnt-5)) # (2) 1떨어진 숫자들
        result+=combi3(cnt-1)*(9**(cnt-4)) # (3) 그냥 2
    return result
    
N=input()
cnt=len(N)
result=case(cnt)
# result+=combi4(cnt-1)*(9**(cnt-5)) # (4) 그냥 0 (아예 사라짐)
print(result)

보존과 비보존 경우의 수를 구해야된다는 것과
단순히 남은 자리수를 고르는게 아니라 2,0,2,3의 숫자가 들어갈 수 있는지 고려해야 된다는 것까진 알아냄

profile
lazyArtisan
이전 포스트

크래프톤 정글 TIL : 0921

다음 포스트

크래프톤 정글 TIL : 0923

0개의 댓글