크래프톤 정글 TIL : 0923

lazyArtisan·2024년 9월 23일
TIL
0

정글 TIL

목록 보기
85/147

📝 배운 것들

🏷️ 세그멘테이션

세그멘테이션 : 고정된 크기로 나누는게 아니라 의미있는 논리적 단위로 나눈다. 힙, 스택, 코드, 이렇게 세그먼트로 나눌 수 있음. 이해하기 쉽고 메모리 낭비가 적다. 내부 단편화는 없는데 외부 단편화 가능성 있음.

세그멘트 내에서 다시 페이징을 적용하면 세그멘테이션과 페이징 결합할 수 있음.
메모리를 논리적 단위인 세그먼트로 나누면서도 고정 크기의 페이지로 나누기 때문에 외부 단편화 문제 해결.


🏷️ 페이지 폴트와 세그멘테이션 폴트의 차이점

페이지 폴트 (Page Fault):

  • 정의: 페이지 폴트는 프로세스가 요청한 메모리 페이지가 물리적 메모리에 없을 때 발생(페이지 테이블 엔트리의 Present Bit가 0일 때)하는 오류입니다. 이 페이지는 일반적으로 디스크에 저장되어 있으며, 페이지 폴트가 발생하면 운영체제가 해당 페이지를 디스크에서 메모리로 불러와야 합니다.
  • 원인:
    1. 프로세스가 물리 메모리에 없는 페이지에 접근할 때.
    2. 페이지가 스왑 아웃되어 디스크에 저장된 상태일 때.
    3. 프로그램이 아직 할당되지 않은 메모리 페이지에 접근하려고 할 때 (이는 새로운 메모리를 할당하는 트리거가 될 수 있음).
  • 처리: 페이지 폴트가 발생하면 운영체제가 페이지를 스왑 인(Swap In)하여 물리 메모리에 로드하고, 프로그램의 실행을 계속합니다.
  • 결과: 페이지 폴트는 필연적으로 성능 저하를 일으킬 수 있지만, 정상적인 상황에서 발생하는 경우도 많습니다. 예를 들어, 프로그램이 처음으로 특정 메모리 페이지에 접근할 때 페이지 폴트가 발생하여 메모리에 페이지를 로드합니다.

세그멘테이션 폴트 (Segmentation Fault):

  • 정의: 세그멘테이션 폴트는 프로세스가 잘못된 메모리 영역에 접근하려 할 때 발생하는 오류입니다. 이는 메모리 보호 기법에 의해 발생하며, 잘못된 메모리 주소에 접근하려는 시도가 원인입니다.
  • 원인:
    1. 프로세스가 허가되지 않은 메모리 영역에 접근할 때.
    2. NULL 포인터에 접근할 때.
    3. 프로그램이 읽기 전용 메모리 영역에 쓰기를 시도할 때.
    4. 스택 오버플로우가 발생했을 때.
  • 처리: 세그멘테이션 폴트가 발생하면, 운영체제는 프로세스가 비정상적인 메모리 접근을 시도했다고 판단하여 해당 프로세스를 종료시킵니다.
  • 결과: 세그멘테이션 폴트는 버그 또는 프로그래밍 오류로 발생하는 경우가 대부분이며, 프로그램이 강제로 종료됩니다.

🏷️ Fowler-Noll-Vo 해시 함수

/* Fowler-Noll-Vo hash constants, for 32-bit word sizes. */
#define FNV_64_PRIME 0x00000100000001B3UL
#define FNV_64_BASIS 0xcbf29ce484222325UL

↑ 핀토스에 있는 Fowler-Noll-Vo 해시 상수

FNV 해시는 입력 데이터를 바이트 단위로 순차적으로 처리하여 해시 값을 계산함.

  1. 초기값 설정: FNV 해시 함수는 해시 값을 계산할 때, 특정한 초기값(FNV_BASIS)을 설정합니다.

  2. 데이터 순차 처리: 입력 데이터의 각 바이트는 순차적으로 처리되며, 현재 해시 값에 대해 XOR 연산을 수행한 뒤, FNV_PRIME이라는 상수로 곱합니다. 이 과정을 모든 바이트에 대해 반복합니다.

  3. 누적 연산: 각 바이트마다 해시 값이 갱신되지만, 이 갱신은 기존의 해시 값에 대한 누적된 연산입니다. 즉, 이전 바이트에서 계산된 값에 현재 바이트의 값을 XOR하고, 그 결과를 곱셈하여 갱신합니다.

  4. 최종 해시 값: 모든 바이트가 처리되고 나면 하나의 최종 해시 값이 남습니다. 이 값이 FNV 해시의 결과로 반환됩니다.


🏷️ Copy On Write

https://code-lab1.tistory.com/58

같은 리소스를 사용하고 있는 두 프로세스가 있는데

한 쪽이 수정 갈기면 그대로 수정하는게 아니라 복사본 만들어서 거기에 저장


🏷️ 페이지 크기 : 4096 바이트

페이지의 크기는 4096 바이트(4KB)로, 이는 16진법으로 0x1000에 해당합니다.

메모리에서 페이지는 연속적인 4096 바이트 크기의 영역으로 분할되며, 각 페이지의 시작 주소는 반드시 4096으로 나누어 떨어져야 합니다. 즉, 페이지의 시작 주소는 4096의 배수여야 합니다.

예를 들어, 16진법으로 보면:
첫 번째 페이지는 0x00000000부터 0x00000FFF까지 (4096바이트),
두 번째 페이지는 0x00001000부터 0x00001FFF까지입니다.
이와 같이 페이지가 고정된 크기(0x1000)의 메모리 블록을 사용해 순차적으로 나뉩니다.


🏷️ avalanche effect

쇄도 효과(avalanche effect), 산사태 효과는
어떤 암호 알고리즘이 입력값에 미세한 변화를 줄 경우
출력값에 상당한 변화가 일어나는 성질을 의미한다.



🖥️ PintOS

🔷 Virtual Memory

📌 깃북 읽기

Managing the Supplemental Page Table 보조 페이지 테이블의 관리

보조 페이지 테이블은 각 페이지에 대한 추가 데이터를 이용해서 페이지 테이블을 보조합니다. 페이지 테이블의 포맷으로 인해 생기는 제한들 때문에 보조 페이지 테이블이 필요합니다. 이런 자료구조는 종종 “페이지 테이블”로도 불리는데, 저희는 혼란을 방지하기 위해서 “보조”라는 단어를 붙였습니다.

  • 🔎  참고 : 권영진 교수님 강의자료에서의 보조페이지테이블의 정의 아래의 보조 데이터들을 담고있는, 프로세스마다 존재하는 자료구조
    → 각각의 페이지에 대해서 데이터가 존재하는 곳(frame, disk, swap 중 어디에 존재하는지), 이에 상응하는 커널 가상주소를 가리키는 포인터 정보, active인지 inactive 인지 등

보조 페이지 테이블은 최소한 두 가지 목적으로 쓰입니다. 가장 중요하게는, 페이지 폴트가 발생했을 때 그곳에 어떤 데이터가 있었어야 했는지를 알아내기 위해 커널은 보조 페이지 테이블에서 폴트가 발생한 가상 페이지를 탐색합니다. 두번째로는 커널이 프로세스가 종료될 때 어떤 자원을 해제(free)할지 고르기 위해서 보조 페이지 테이블을 조사합니다.

📌 구현 시작

보조 페이지 테이블, 프레임 테이블, 스왑 테이블 만들라고 했으니까
보조 페이지 테이블부터 만들어야 되는데 구조체 자료형 가보면 텅텅.

보조 페이지 테이블

  • 각 페이지에 대한 추가 데이터 가짐
    - frame, disk, swap 중 어디에 존재?
    - 이에 상응하는 커널 가상주소 포인터
    - active인지 inacitve인지
    - 기타 등등
  • 페이지 폴트 발생했을 때 어떤 데이터가 있었어야 했는지 알기 위해 보조 페이지 테이블에서 폴트 발생한 가상 페이지 탐색
  • 커널이 프로세스가 종료될 때 어떤 자원을 free할지 고르기 위해 보조 페이지 테이블 조사

페이지 폴트 과정 (깃북)

당신의 페이지 폴트 핸들러가 해야 하는 일들을 대략적으로 설명하면 다음과 같습니다 :

  1. 보조 페이지 테이블에서 폴트가 발생한 페이지를 찾습니다. 만일 메모리 참조가 유효하다면, 보조 페이지 엔트리를 사용해서 데이터가 들어갈 페이지를 찾으세요. 페이지는 파일 시스템에 있거나, 스왑 슬롯에 있거나, 또는 단순히 0으로만 이루어져야 할 수도 있습니다. 당신이 만약 Copy-on-Write와 같은 공유를 구현한다면, 페이지의 데이터는 이미 페이지 테이블에 없고 페이지 프레임에 들어가 있을 것입니다. 만약 보조 페이지 테이블이 다음과 같은 정보를 보여주고 있다면 - 유저 프로세스가 접근하려던 주소에서 데이터를 얻을 수 없거나, 페이지가 커널 가상 메모리 영역에 존재하거나, 읽기 전용 페이지에 대해 쓰기를 시도하는 상황 - 그건 유효하지 않은 접근이란 뜻입니다. 유효하지 않은 접근은 프로세스를 종료시키고 프로세스의 모든 자원을 해제합니다.

  2. 페이지를 저장하기 위해 프레임을 획득합니다. 만일 당신이 공유를 구현한다면, 필요한 데이터는 이미 프레임 안에 있을 겁니다. 이 경우 해당 프레임을 찾을 수 있어야 합니다.

  3. 데이터를 파일 시스템이나 스왑에서 읽어오거나, 0으로 초기화하는 등의 방식으로 만들어서 프레임으로 가져옵니다. 공유를 구현한다면, 필요한 페이지가 이미 프레임 안에 있기 때문에 지금 단계에서는 별다른 조치가 필요하지 않습니다.

  4. 폴트가 발생한 가상주소에 대한 페이지 테이블 엔트리가 물리 페이지를 가리키도록 지정합니다. threads/mmu.c 에 있는 함수를 사용할 수 있습니다.

유저 가상메모리의 모습을 생각하면 heap은 아래에서 위로, stack은 위에서 아래로 커지는 것을 떠올릴 수 있을 것입니다.

이는 스택과 힙이 충분히 자라지 않은 경우 스택과 힙 사이에는 사용되지 않는 영역들이 존재한다는 말입니다. 이 사용되지 않는 영역을 참조하는 경우 ‘메모리 참조가 유효하지 않다’고 표현합니다.

페이지 폴트 과정 (gpt)

  1. 페이지 폴트 발생 감지 : CPU가 가상 주소에 접근하려고 하지만, 해당 가상 페이지가 페이지 테이블에 존재하지 않거나 Present 비트가 0으로 설정되어 있는 경우 페이지 폴트

  2. 페이지 폴트 핸들러 호출

  3. 원인 분석

  • 페이지가 디스크 스왑 공간에 있으면 디스크에서 다시 읽어온다.
  • 아직 페이지 할당 안 됐으면 주소에 해당하는 페이지 새로 할당.
  • 잘못된 주소 접근하면 세그멘테이션 폴트로 프로세스 종료
  1. 페이지 로드
  • 페이지가 스왑 공간이나 디스크에 있으면
  • 사용 가능한 프레임 찾아서 페이지 적재하고
  • 페이지 테이블 업데이트
  1. 페이지 테이블 업데이트
  • 프레임에 할당하는거 성공했으면, 페이지 테이블의 해당 엔트리에 새 물리적 페이지 주소를 기록하고, Present 비트를 1로 설정, 페이지에 적절한 읽기/쓰기/실행 권한을 설정

해시 테이블 하는데 이렇게 하라길래 복붙 했더니 페이지 구조체에 hash_elem이랑 addr 없다고 오류.
페이지에 요소 추가.

ctrl+f 해보니까 그냥 void * 자료형인듯?

이것도 깃북에 있는 함수인데
pages 없는데 왜 가져다 쓴거지

동기한테 물어봤더니
pages는 전역 변수로 정의돼있는 페이지 테이블인 것 같다고 함.

페이지 할당기는 할당하게 될 메모리를 두 개의 풀로 나누고, 각 풀은 커널 풀과 유저 풀로 불립니다. 기본적으로 각각의 풀은 시스템 메모리의 절반을 차지하지만, 커널풀과 유저풀을 나누는 기준은 커널 커맨드 옵션 ul로 변경할 수 있습니다. 할당을 요청하면 둘 중 하나의 풀에서 메모리를 얻게 됩니다. 유저 풀은 유저 프로세스를 위해 메모리를 할당할 때 사용되고, 그 외의 할당에 대해서는 커널 풀이 사용됩니다. 이 부분은 프로젝트 3부터만 중요한 부분이고, 프로젝트 3 이전까지는 모든 할당은 커널 풀에서 이루어져야 합니다.

각 쓰레드는 pml4 갖고 있음. 이거인가?
근데 hash.c에 쓰는 건 pml4가 아니라 보조 페이지 테이블인듯.
hash_find() 인자는 자료형이 hash *임.

보조 페이지 테이블 구현

Therefore, we suggest you to implement some basic functionalities for the supplemental page table as the first task of project 3.

Implement supplemental page table management functions in vm/vm.c.

You will first have to decide how you will design the supplemental page table in your Pintos. After design your own supplemental page table, implements below three functions with respect to your design.

일단 이거에 집중

해시 테이블은 각 해시값 하나당 요소 하나가 매핑돼있음
가상 주소를 받으면 해시값을 구해서 그게 인덱스가 되고 거기에 페이지 넣고
페이지에 frame,disk,swap 어디 있는지 active인지 inactive인지 등 저장?

https://maxlevsnail.com/pintos/

그냥 막 했다가 잘못된 암흑의 길로 빠질 것 같아서
내 설계가 맞는지 확인해보려고 블로그 확인

  • spt는 hash table로 구성되어 있음.
    • init, find, insert는 hash table로 사용됨
    • 이를 위해 hash_elem 이 struct page에 들어가 있음.
    • hashfunc와 page_less는 hash table 작동을 위한 함수들.
  • vm_get_frame: palloc으로 페이지 받은 뒤 frame 만들어서 리턴
  • vm_do_claim_page: frame과 page struct를 연관짓고 pml4_set_page로 페이지 설정
  • vm_claim_page: malloc으로 페이지 struct 만든 뒤 vm_do_claim_page

https://nullbyte.tistory.com/60

이것도 읽음

가상 공간은 이전 포스팅에서 설명했듯이 일정 주소를 경계로 하여 커널 영역과 유저 영역으로 분류된다. pintos외에 다른 운영 체제는 정확히 어떻게 구현되어 있는지는 모르겠으나 pintos는 KERN_BASE (현재 pintos는 0x8004000000)를 기준으로 유저 영역은 각 프로세스마다 별개로 가지고 있는 공간이며, 커널 영역은 모든 프로세스에서 하나의 커널 공간을 공유한다. 커널에서는 유저 영역과 커널 영역 모두 접근 가능하지만, 유저 프로세스는 고유의 유저 영역에만 접근할 수 있다. 각 유저 프로세스는 각자 서로 다른 최상위 테이블을 만들어 CR3 레지스터로 가리키고 있으므로, 다른 유저 프로세스에서 같은 가상 주소로 메모리에 접근한다 할지라도 접근할 수 있는 물리 공간의 영역은 서로 달라지게 된다. 

|  P  |  R/W  |  U/S  |  A  |  D  |  G  |   Page Frame Address   |
| --- | ----- | ----- | --- | --- | --- | --------------------- |
|  1  |   1   |   0   |  1  |  0  |  0  |     0x12345ABC        |

gpt한테 페이지 테이블 엔트리에 대해 설명해달라고 했더니 나온 그림.

pte.h에 있는 것들을 활용해서 pte에 주소도 담고 이것저것 담고...
그 다음에 보조 페이지 테이블에 담는다?
근데 이거 이미 pml4에 있는 정보들 아님?

pte.h는 pml4를 위해 쓰이고 있으니
응용해서 보조 페이지 테이블을 위한 보조 페이지 테이블 엔트리를 만들어야 되는건가?

pml4랑 호환이 어떻게 되는거지?

일단 해시 초기화
pintos에서 제공하는 해시 함수들이 있었음 hash_bytes 사용

void supplemental_page_table_init(struct supplemental_page_table *spt UNUSED)
{
	const char *data = "hello";
	size_t data_size = strlen(data);				   // 문자열의 크기를 계산
	unsigned hash_value = hash_bytes(data, data_size); // 문자열을 해시
	hash_init(spt->hash, hash_value, page_less, NULL);
}

해시함수에 뭐 넣어야 할지 모르겠어서 gpt마카세

위의 함수는 인자로 주어진 보조 페이지 테이블에 페이지 구조체를 삽입합니다. 이 함수에서 주어진 보충 테이블에서 가상 주소가 존재하지 않는지 검사해야 합니다.

라는거 보니까 일단 페이지를 냅다 넣으면 되는듯
괜히 고민했네

/* Insert PAGE into spt with validation. */
bool spt_insert_page(struct supplemental_page_table *spt UNUSED,
					 struct page *page UNUSED)
{
	int succ = false;
	/* TODO: Fill this function. */
	hash_insert(spt->hash, &page->hash_elem);

	return succ;
}

다음으로 삽입하는데 validation 어케 함?



⚔️ 백준

📌 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 saved_case():


def case(cnt):
    # 해당 자리수를 보존한 경우의 수와 보존하지 않은 경우의 수들을 합쳐야 함
    # 456789를 예로 들면, (1) 4 그대로, (2) 1 떨어진 3과 1, (3) 그냥 2, (4) 아예 사라짐    
    # (1), (2), (3)에 대한 경우의 수를 구했으면 다음 자릿수인 (4)로 넘어가야 함
    global N
    L=len(N)
    num=int(N[L-cnt])
    # 자리수 4개 남았을 때 예외처리 (나중에 없애기)
    if cnt==4: 
        if int(N)>=2023: 
            return 1
        else:
            return 0
        
    result=0
    if num==1:
        result+=case(cnt-1) # 아예 사라짐
        result+=

    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)
lower_than_two=[]
lower_than_three=[]
# 각 자리수에 대해 2, 3 미만인 숫자가 어느 자리수에 있는지
for i in range(cnt):
    num=int(N[i])
    if num==1:
        lower_than_two.append(i)
        lower_than_three.append(i)
    if num==2:
        lower_than_three.append(i)

result=case(cnt)
# result+=combi4(cnt-1)*(9**(cnt-5)) # (4) 그냥 0 (아예 사라짐)
print(int(result))


# 맨 처음 자리수를 1만 떨어뜨리면 나머지 숫자들에는 자유가 부여된다.
# 문제는 자리수가 보존됐을 때의 경우의 수.

# 모든 자리수를 동결시키고 2,0,2,3 각 숫자만 넣는다고 생각한다.
# 첫번째 숫자인 2의 위치를 골랐을 때 넘치냐 안 넘치냐를 확인,
# 그것보다 낮은 자리수에서 0을 고르고 (확인 필요 없음)
# 또 다시 2의 위치를 고른다. 3도 고른다.
# 이 모든 경우의 수를 고려하려면 2보다 큰지 작은지, 3보다 큰지 작은지에 대한 정보가 필요

# 첫 2를 고르고 한 칸 건너뛴 칸에서부터 2가 들어갈 수 있는지 확인,
# 2가 들어갈 수 있는 모든 칸들에 대해 다시 그 아래의 칸들에 3이 들어갈 수 있는지 확인
# 만약 숫자가 2,0,3과 같다면 중복에 대한 대응을 해줘야 함.
# 


# 자리수 4개 남았을 때 예외처리 (나중에 없애기)
if cnt==4: 
    if int(N)>=2023: 
        return 1
    else:
        return 0
if cnt==5:
    if 

# 2를 고를 수 있는가?

문제 잡은지 3일째. 중복 계산해줘야 된다는 것까지 인지.
(o1-preview로 풀게 시켰는데 70몇초나 생각해놓고 틀린 답 줌. 인터넷에 답지도 없어서 막막.)

profile
lazyArtisan
이전 포스트

크래프톤 정글 TIL : 0922

다음 포스트

크래프톤 정글 TIL : 0924

0개의 댓글