크래프톤 정글 TIL : 0924

lazyArtisan·2024년 9월 24일

TIL

정글 TIL

목록 보기

86/147

🖥️ PintOS

🔷 Virtual Memory

page fault 발생 시 해당 page fault에 대응할 수 있도록 필요한 정보를 제공하는 supplemental page table
물리 메모리 공간이 부족할 경우 디스크로 쫓아낼 (eviction) frame을 효율적으로 결정하도록 하는 frame table
디스크에 임시 저장된 frame들의 공간인 swap slot의 사용 현황을 추적할 수 있도록 하는 swap table

라고 함

보조 페이지 테이블

supplemental_page_table_init

/* Initialize new supplemental page table */
void supplemental_page_table_init(struct supplemental_page_table *spt UNUSED)
{
	hash_init(spt->hash, page_hash, page_less, NULL);
}

어제 했던 그거 이렇게 바꿔야 한다고 동기한테 들음.
hash_byte가 아니라 page_hash를 넣어야 함. 인자 넣어줄 필요도 없음.

spt_insert_page

/* 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. */
	if (!spt_find_page(spt, page))
		return false;

	if (hash_insert(spt->hash, &page->hash_elem))
		succ = true;
	return succ;
}

될진 모르겠지만 일단 이렇게 함

spt_find_page

/* Find VA from spt and return page. On error, return NULL. */
struct page *
spt_find_page(struct supplemental_page_table *spt UNUSED, void *va UNUSED)
{
	struct page *page = NULL;
	/* TODO: Fill this function. */
	page = hash_find(spt->hash, va);
	return page;
}

이것도 일단 이렇게 함

방금 떠오른건데, 일단 이렇게 페이지를 넣는 건 맞긴 한데
그 안의 버킷에 정보를 넣으면 되는거인듯.

함수 수정

page_lookup의 page가 그래서 뭐라는거지? 하고 답지 찾아봤더니
깃북에 이미 있다고 함. 엥? 하고 봤더니 진짜 있었음.

spt랑 같은 거인듯?

/* Find VA from spt and return page. On error, return NULL. */
struct page *
spt_find_page(struct supplemental_page_table *spt UNUSED, void *va UNUSED)
{
	struct page *page = NULL;
	/* TODO: Fill this function. */
	page = hash_find(&spt->pages, va);
	return page;
}

/* 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. */
	if (!spt_find_page(spt, page))
		return false;

	if (hash_insert(&spt->pages, &page->hash_elem))
		succ = true;
	return succ;
}

함수도 수정

struct hash pages;
hash_init(&pages, page_hash, page_less, NULL);

냅다 hash.c 아무데나 넣으라는 건 아닌듯
그렇게 되면 함수 전방 선언으로 알아먹어버림

빨간줄 뜨는거 디버깅에도 지장 줄 것 같아서 ifdef 풀었는데 여기에도 빨간 줄.
spt 선언돼있는 vm.h에 가봤더니

아니 여기엔 또 왤케 빨간줄 많음;

struct page *page_lookup(const void *address)
{
	struct page p;
	struct hash_elem *e;

	p.addr = address;
	e = hash_find(&thread_current()->spt.pages, &p.hash_elem);
	return e != NULL ? hash_entry(e, struct page, hash_elem) : NULL;
}

구글링 해봤는데 딱히 신경 안 써도 될듯? vscode의 호들갑으로 보여서
->만 .으로 바꾸고 컴파일 했더니 컴파일됨. 물론 아직은 다 패닉 뜸.

Kernel panic in run: PANIC at ../../vm/vm.c:133 in vm_get_frame(): assertion frame != NULL' failed.

이거 뜬다.

당연하지. 아직 안 만들었으니까.

TA님 답변 : Pintos 물리 메모리 주소

x86-64 doesn't provide any way to directly access memory at a physical address. Pintos works around this by mapping kernel virtual memory directly to physical memory - the first page of kernel virtual memory is mapped to the first frame of physical memory, the second page to the second frame, and so on. Thus, frames can be accessed through kernel virtual memory.

깃북(Project3 - Introduction - Frames)의 이 내용이 뜻하는 바가, 아키텍처 자체에서 물리 주소로 메모리 접근을 못하게 막아놨으니까 커널 가상 메모리의 일정 영역을 물리 메모리인 것처럼 생각하자는 건가요?

네 말씀하신 내용이 맞습니다. 커널 가상 메모리를 물리 메모리와 1:1 대응 시켜놓았으니까 커널 가상 메모리를 접근하는건 곧 물리 메모리를 접근하는 것과 같다는 얘기입니다.

mapped라는게 커널의 일정 영역은 실제로 물리 메모리 주소에 접근을 한다는 건가? 하고 헷갈렸었습니다. 답변 감사합니다.

Frame Management

vm_get_frame

/* palloc() and get frame. If there is no available page, evict the page
 * and return it. This always return valid address. That is, if the user pool
 * memory is full, this function evicts the frame to get the available memory
 * space.*/
/* palloc()하고 frame을 가져온다. 가능한 페이지가 없으면, 페이지 하나를 쫓아내고 그걸 반환한다.
 * 언제나 유효한 주소를 반환한다. 즉, 유저 풀 메모리가 꽉 찼으면, 프레임을 쫓아내서 가능한 메모리 공간을 얻어낸다. */

palloc() 한다는게 뭔 소리지; 이 페이지가 그 페이지가 아닌가?

/* The representation of "frame" */
struct frame {
  void *kva;
  struct page *page;
};

프레임이 원래는 물리 메모리인데 물리 메모리는 커널 영역에 있는 걸로 치자고 했으니까
kva는 사실상의 물리 메모리 주소라고 생각하면 될거고
page는 거기에 있는 페이지니까

??? 뭔가 이상

주소에 페이지가 있어야 되는거 아님?
왜 페이지는 따로 있음?
아 당연한 건가 페이지가 프레임에 매핑되는거니까
그럼 프레임은 누가 관리하는거지
하다보면 관리하는거 만들겠지?

아니 근데 palloc 하라는데
palloc은 pml4에서 관리되는거 아님?

보조 페이지 테이블에서 관리하는 페이지하고
palloc.c에서 말하는 페이지하고
mmu.c에서 말하는 페이지가 도대체 무슨 차이지???

그렇지. 이미 페이지라는 것들은 있음. palloc.c랑 mmu.c에 있음.
그걸 보조 페이지 테이블에 연결해주기만 하면 끝인거임.

https://maxlevsnail.com/pintos/

ㅇㅋ 힌트(답지) 보니까 완벽하게 이해했음.

아니 모르겠음

struct frame의 주소도 있고
frame 안에 있는 kva도 있는데
뭐가 뭐지;

static struct frame *vm_get_frame (void);

palloc_get_page를 호출하여 유저 풀에서 새 물리 페이지를 가져옵니다. 유저 풀에서 페이지를 성공적으로 가져오면, 프레임을 할당하고 그 멤버를 초기화한 후 반환합니다. vm_get_frame을 구현한 후에는 모든 사용자 공간 페이지 할당을 이 함수를 통해 (즉, PALLOC_USER를 사용하여) 처리해야 합니다. 페이지 할당 실패 시, 지금은 스왑 아웃 처리를 할 필요는 없습니다. 대신 그러한 경우에는 PANIC("todo")를 사용해 표시하면 됩니다.

frame = (struct frame *)palloc_get_page(PAL_USER); 이건 맞는 거 같은데

kva는 도대체 뭐임? frame 자체의 주소일리는 없지. 그건 그냥 & 연산자 쓰면 되는거니까.

아니 그리고 유저 풀에서 갖고 오면 안되는거 아님? 커널 영역을 물리 메모리로 보겠다며?

vaddr.h를 봐야 하나? ptov이거 써야되는거임?? 아니 palloc_get_page는 커널 영역 주소 돌려주는 거 맞는거 같은데?

일단 유저풀 쓰라고 깃북에 명시는 돼있었다...

/* Obtains a single free page and returns its kernel virtual
   address.
   If PAL_USER is set, the page is obtained from the user pool,
   otherwise from the kernel pool.  If PAL_ZERO is set in FLAGS,
   then the page is filled with zeros.  If no pages are
   available, returns a null pointer, unless PAL_ASSERT is set in
   FLAGS, in which case the kernel panics. */

이거 보니까 이해됨.
그니까 유저풀 커널풀 나눈 건 "물리 메모리" 상에서 나눈거고,
어쨌든 둘 다 커널 가상 주소를 돌려받는다.

https://velog.io/@ceusun0815/Pintos-KAIST-Project-3-Memory-Management

??? 갑자기 malloc()을 쓴다고?

https://yunchan97.tistory.com/75

다른 블로그도 마찬가지.
아주 당연하다는 듯이 malloc을 쓰고 있다.

이럴 때마다 찾아가서 도대체 뭘 어디에서 보고 malloc을 써야겠다는 생각을 한건지,
깃북 어디에도 kva이 뭔지 언급 안돼있는거 같은데 이게 뭔지는 어떻게 안건지 물어보고 싶다.

내가 제대로 안 본건가...? 깃북 온 페이지 찾아다니면서 ctrl+f "kva" 했는데?
일단 진정하고 malloc palloc 하라는대로 해주자.

static struct frame *
vm_get_frame(void)
{
	struct frame *frame = (struct frame *)malloc(sizeof(struct frame));
	frame->kva = palloc_get_page(PAL_USER | PAL_ZERO);
	if (frame->kva == NULL) // 나중에 스왑 아웃 처리로 바꿔야 함
		PANIC("TO DO");
	frame->page = NULL;

	ASSERT(frame != NULL);
	ASSERT(frame->page == NULL);
	return frame;
}

frame->page가 NULL이라는 것도 몰랐다.
그니까 vm_get_frame의 역할은 페이지를 할당하기 위한 프레임을 가져오는 거였음.

vm_do_claim_page

/* Claim the PAGE and set up the mmu. */
static bool
vm_do_claim_page(struct page *page)
{
	struct frame *frame = vm_get_frame();

	/* Set links */
	frame->page = page;
	page->frame = frame;

	/* TODO: Insert page table entry to map page's VA to frame's PA. */
	/* 페이지 테이블 엔트리를 삽입해서 가상 주소를 프레임의 물리 주소로 매핑해라 */
	if(!pml4_set_page(thread_current()->pml4,page,frame->kva,true))
		return NULL;

	return swap_in(page, frame->kva);
}

일단 mmu.c에서 함수 하나 가져옴.
이론상 맞는 것 같다고 믿고 있음.

vm_claim_page

/* Claim the page that allocate on VA. */
bool vm_claim_page(void *va UNUSED)
{
	struct page *page = (struct page *)malloc(sizeof(struct page));

	return vm_do_claim_page(page);
}

일단 하긴 했는데

깃북에 페이지 초기화를 해줘야 하는건지 아닌건지 안 나와있어서
힌트를 다시 봄. 안해줘도 되는듯.

⚔️ 백준

📌 21653 Скобки

bracket=input()
n=len(bracket)
stack=[]
res=0
cnt=0
for i in range(n):
    cnt+=1
    if stack and stack[-1]=='(' and bracket[i]==')':
        stack.pop()
    else:
        stack.append(bracket[i])        
    if not stack:
        res+=cnt*(cnt-1)/2
        cnt=0
res+=n*(n+1)/2+(n+1)
print(int(res))

겨우 골드3이지만 문제가 러시아어라 아직 나 포함 3명밖에 안 푼 문제. (실제로 골드 3 난이도인지는 잘 모르겠)
다른 사람 코드 보니까 내가 제일 간결함. 나이스.

도파민 폭풍이 몰려온다.
핀토스 말고 ps만 하고 싶다.

📌 1912 연속합

아 근데 바로 모르겠는 문제 나와버림
전혀 감이 잡히질 않는다

n=int(input())
seq=list(map(int,input().split()))
Min, Max = float('inf'), -float('inf')
temp=0
Sum = 0
res = 0
max_sum=-float('inf')
for num in seq:
    Sum+=num # 그래프 경로
    temp+=num # 부분합
    if Max < Sum:
        Max = Sum
        max_sum = temp
        res = max(res, max_sum)
    if Min > Sum: 
        Min = Sum
        res = max(res, max_sum)
        temp = 0
res = max(res, max_sum)
print(res)

# 순회하며 최소값이 갱신되면 변곡점에 추가
# 거기서부터 최대로 올라간 높이를 저장