📝 배운 것들
🏷️ 파이썬 딕셔너리에 키 없는 데이터 추가
d={1:0}
d[2]=1
print(d) # {1: 0, 2: 1}키를 추가하지 않아도 데이터를 추가할 수 있다.
🖥️ PintOS
🔷 Virtual Memory
📌 Supplemental Page Table - Revisit
Stack Growth 앞에 또 뭐가 있었다. 이거부터 해야됨.
uninit_destroy()
/* uninit_page가 갖고 있는 자원들을 할당 해제 한다.
* 대부분의 페이지들이 다른 페이지 오브젝트들로 변환되지만,
* 프로세스가 종료될 때 한 번도 참조되지 않은 uninit page들을 갖고 있을 수 있다.
* 페이지는 호출자에 의해 할당 해제될 것이다. */
static void
uninit_destroy(struct page *page)
{
struct uninit_page *uninit UNUSED = &page->uninit;
/* TODO: Fill this function.
* TODO: If you don't have anything to do, just return. */
return;
}할당 해제를 하려면 무슨 자원을 갖고 있는지만 알면 된다.
page 구조체를 malloc으로 만들어냈었으니까 free만 하면 되겠지? 생각했는데
그럼 struct uninit_page *uninit UNUSED = &page->uninit; 이건 왜 있는거?
page를 free하는게 아니라 page 안에 들어있는 uninit_page이 갖고 있는 자원만 free하는 거인듯?
vm_alloc_page_with_initializer은 uninit_new을 호출함.
uninit_new은 page의 uninit의 page_initializer를 삽입함.
page_initializer는 (file_backed_initializer : anon_initializer) 둘 중 하나임.
uninit_initialize는 페이지의 uninit을 초기화함.
uninit->page_initializer를 호출함.
file_backed_initializer, anon_initializer은 uninit_page와는 관련 없는듯.
Frees the resource that was held by page struct. You might want to check the vm type of the page and handle accordingly.
페이지 구조체에 의해 유지되던 자원들을 free시킵니다. 당신은 아마도 페이지의 vm type을 확인하고 그에 맞춰 핸들링해야할 것입니다.
깃북은 이렇게 말하긴 하는데
그럼 page도 날려버리고 uninit이 갖고 있던 것도 날려버리라는 거인듯?
기본적으로 free(page)를 하면 페이지에 있던 것들은 다 날아감
page나 uninit_page가 malloc으로 반환받은 포인터로 갖고있는 것들을 free시켜야 됨.
struct page
{
const struct page_operations *operations;
void *va; /* Address in terms of user space */
struct frame *frame; /* Back reference for frame */
/* Your implementation */
struct hash_elem hash_elem;
void *addr;
uint8_t page_status; // 페이지 상태 추적 변수
bool writable;
/* Per-type data are binded into the union.
* Each function automatically detects the current union */
union
{
struct uninit_page uninit;
struct anon_page anon;
struct file_page file;
#ifdef EFILESYS
struct page_cache page_cache;
#endif
};
};page_operations는 재사용해야되는거니까 상관 없고
uninit_page니까 frame은 아직 없을 거고
va나 addr은 상관 없고
struct uninit_page
{
/* Initiate the contets of the page */
/* 페이지의 내용물을 초기화 */
vm_initializer *init;
enum vm_type type;
void *aux;
/* Initiate the struct page and maps the pa to the va */
/* 페이지 구조체를 초기화하고 물리 주소를 가상 주소와 매핑 */
bool (*page_initializer)(struct page *, enum vm_type, void *kva);
};vm_initializer도 상관 없고
나머지도 상관 없는데 그나마 aux가 의심?
struct aux_pak *aux = malloc(sizeof(struct aux_pak));
aux->file = file;
aux->ofs = ofs;
aux->read_bytes = page_read_bytes;
aux->zero_bytes = page_zero_bytes;
aux->writable = writable;
if (!vm_alloc_page_with_initializer(VM_ANON, upage,
writable, lazy_load_segment, aux))
return false;한참 거슬러 올라가니 결국 load_segment가 범인이었음.
내가 만들었던 aux_pak 구조체가 aux에 담겨있다.
aux 이 친구를 free 하고 page도 free 해버리면 끝?
static void
uninit_destroy(struct page *page)
{
struct uninit_page *uninit UNUSED = &page->uninit;
/* TODO: Fill this function.
* TODO: If you don't have anything to do, just return. */
free(uninit->aux);
free(page);
return;
}일단 이렇게만 해두기
anon_destroy()
static void
anon_destroy (struct page *page) {
struct anon_page *anon_page = &page->anon;
free(page);
}anon_page를 아직 구현해놓지 않았기 때문에 일단 page만 free
응 안돼 다시 다 점검해
달라진게 없음. 다시 해봐야됨.
아니 이걸 안 했었네
아오 좀 꼼꼼하게 보자
supplemental_page_table_copy()
/* 해시 테이블에 있는 각 요소에 대해 특정 작업(ACTION)을 수행 */
void hash_apply(struct hash *h, hash_action_func *action)이거 써서 각 원소에 대해 dst로 insert 해주면 될듯?
hash_apply()에는
action(list_elem_to_hash_elem(elem), h->aux);가 있음.
첫번째 인자로는 action, 두번째 인자로는 aux가 들어가는데 이건 또 뭐임
/* Initialize new supplemental page table */
void supplemental_page_table_init(struct supplemental_page_table *spt UNUSED)
{
hash_init(&spt->pages, page_hash, page_less, NULL);
}그냥 null인듯? 신경 안써도 될 것 같다.
hash_insert(struct hash *h, struct hash_elem *new)hash_insert를 무작정 apply의 action에 넣을 수는 없다.
인자가 다르기 때문.
(+ page 없앨 때 free로 하는게 아니라 destroy()도 같이 해주는 vm_dealloc_page()라는 함수를 썼어야 됐었던 것 같음. 수정 완료.)
aux값을 해쉬 함수에 넣어주는 식으로 전달해야할듯?
void action_copying(struct hash_elem *h, void *dst)
{
hash_insert(dst, h);
}
/* Copy supplemental page table from src to dst */
bool supplemental_page_table_copy(struct supplemental_page_table *dst UNUSED,
struct supplemental_page_table *src UNUSED)
{
src->pages.aux = src;
hash_apply(&src->pages, action_copying);
}hash_apply에 src의 해시 테이블과, 해시 테이블을 복사하는 함수 포인터를 넣어주면
src의 해시 테이블을 순회하면서
함수 포인터로 넣어준 함수에 순회하고 있는 각 요소와 h->aux(내가 dst를 넣어줬던 변수)를 넣는다.
그럼 action_copying_hash가 해당 요소를 dst에 넣어준다.
You will need to allocate uninit page and claim them immediately.
깃북의 이 부분이 조금 신경쓰이긴 하는데 일단 넘어가자. 뭔 말인지 모르겠.
supplemental_page_table_kill()
이것도 비슷하게 하면 될듯
hash_apply()가 아니라 hash_destroy()를 사용하는게 다르다.
hash_elem에서 page를 알아내야 하는데 어떡함
hash_entry를 까먹어서 한참 헤맸다
void action_destroy(struct hash_elem *h, void *aux)
{
struct page *page = hash_entry(h, struct page, hash_elem);
destroy(page);
}
/* Free the resource hold by the supplemental page table */
void supplemental_page_table_kill(struct supplemental_page_table *spt UNUSED)
{
/* TODO: Destroy all the supplemental_page_table hold by thread and
* TODO: writeback all the modified contents to the storage. */
/* 쓰레드가 갖고 있는 모든 보조 페이지 테이블을 삭제하고
* 수정한 모든 컨텐츠를 저장소에 저장 */mental page table를 복사하세요. 이것은 자식이 부모의 실행 context를 상속할 필요가 있을 때 사용됩니다.(예 - fork()). src의 supplemental page table를 반복하면서 dst의 supplemental page table의 엔트리의 정확한 복사본을 만드세요. 당신
hash_destroy(&spt->pages, action_destroy);
}destroy에 free도 더해줘야 하는건지 모르겠는데
일단 깃북에 destroy를 call 하라고 했고
당신은 이 함수에서 실제 페이지 테이블(pml4)와 물리 주소(palloc된 메모리)에 대해 걱정할 필요가 없습니다.
라고 했으니 free는 필요 없을지도
다 하고 돌려봤더니 터지기 시작
디버깅
supplemental_page_table_copy()과 supplemental_page_table_kill()을 고쳤는데 이렇게 된거.
간단히 주석처리하고 돌려봤는데 copy는 코드를 터트리진 않음.
(근데 fork는 여전히 안됨)
supplemental_page_table_kill() 이녀석이 문제.
그리고 여기에는 hash_destroy(&spt->pages, action_destroy); 한 줄 뿐임.
디버깅 찍어봄.
- spt_kill은 정상적으로 호출된다.
- action_destroy는 호출되지 않는다.
- destroy를 하는 과정, 혹은 결과에서 오류가 일어났다.
printf("VM.C :: ACTION_DESTROY() : LOAD PAGE\n"); 이거 추가해도 뜨질 않음.
어째서?
모든 버킷이 비어있다고 인식돼서 destructor에 진입하지 못하는 현상이 발생하고 있음.
내가 한 글자도 건드리지 않았던 함수임에도 불구하고 터졌다는 것은
- 사용법이 잘못 됐다
- bucket에 아무것도 들어가지 않았다
둘 중 하나인데, 사용법이 잘못됐다고 하더라도 entering destructor까지는 들어가야 됨.
그리고 딱히 잘못 사용한 부분도 안 보인다.
spt에 insert하는 걸 다시 점검해보자.
vm_alloc_page_with_initializer()에 spt_insert_page()가 있잖음
그럼 상관 없잖음 그 안에 있는 hash_insert()도 제대로 했잖음
void action_destroy(struct hash_elem *h, void *aux)
{
printf("VM.C :: ACTION_DESTROY() : LOAD PAGE\n");
// struct page *page = hash_entry(h, struct page, hash_elem);
printf("VM.C :: ACTION_DESTROY() : DESTROY_PAGE STRAT\n");
// destroy(page);
printf("VM.C :: ACTION_DESTROY() : DESTROY_PAGE END\n");
}destructor인 action_destroy()의 중요한 부분들을 주석처리해도 여전히 터짐.
생각해보면 당연. 애초에 action_destroy()까지 호출되지도 않으니까.
페이지를 destroy()하는 것도 아닌데 쓰레드가 터져버린다라?
애초에 hash_destroy()를 호출하는게 아닐 가능성 있음.
/* Free the resource hold by the supplemental page table */
void supplemental_page_table_kill(struct supplemental_page_table *spt UNUSED)
{
/* TODO: Destroy all the supplemental_page_table hold by thread and
* TODO: writeback all the modified contents to the storage. */
/* 쓰레드가 갖고 있는 모든 보조 페이지 테이블을 삭제하고
* 수정한 모든 컨텐츠를 저장소에 저장 */
// printf("VM.C :: SPT_KILL() : HASH_DESTROY START\n");
// hash_destroy(&spt->pages, action_destroy);
// printf("VM.C :: SPT_KILL() : HASH_DESTROY END\n");
hash_apply(&spt->pages, action_destroy);
}spt_kill에 있던 hash_destroy()를 hash_apply()로 바꿨더니
정상적으로 돌긴 하는데 테스트 통과 갯수는 그대로.
여전히 action_destroy()가 호출되지 않기 때문.
copying에서부터 문제가 발생했을 가능성 있음.
supplemental_page_table_copy()
supplemental_page_table_copy()을 점검해보자.
/* Copy supplemental page table from src to dst */
bool supplemental_page_table_copy(struct supplemental_page_table *dst UNUSED,
struct supplemental_page_table *src UNUSED)
{
src->pages.aux = src;
hash_apply(&src->pages, action_copying);
}??? src->pages.aux = src; 이거 누가 이래놓음
누구긴 누구임 나지
src->pages.aux = dst; 이걸로 바꿨다.
그래도 여전히 안됨.
void action_copying(struct hash_elem *h, void *dst)
{
hash_insert(dst, h);
}이거 지난 프로젝트 때도 겪었던 문제인데,
같은 요소를 서로 다른 리스트에 넣으면 문제 생기는 걸로 알고 있다.
그래서 list_elem 여러 종류를 선언했었음.
copy를 shallow copy가 아니라 deep copy로 해야할듯.
- 무작정 struct page malloc 때리고 변수에 정보 때려박는다 (타입은 구분해야겠지)
- vm_alloc_page_with_initializer 혹은 vm_alloc_page를 사용한다
둘 다 별로인 것 같아서 고민하고 있는데 마침 건너편에서 이에 대한 힌트를 말하는 걸 들음
3. memcpy를 사용한다
이러면 정보를 통째로 이사시키기 가능
/* 새 페이지 만든 후에 거기에 정보 전부 복사 */
void action_copying(struct hash_elem *h, void *dst)
{
struct page *page = hash_entry(h, struct page, hash_elem);
struct page *new_page = malloc(sizeof(struct page));
memcpy(new_page, page, sizeof(struct page));
hash_insert(dst, &new_page->hash_elem);
}
/* Copy supplemental page table from src to dst */
bool supplemental_page_table_copy(struct supplemental_page_table *dst UNUSED,
struct supplemental_page_table *src UNUSED)
{
src->pages.aux = dst;
hash_apply(&src->pages, action_copying);
}해줬는데 역시 안됨.
void *aux; /* Auxiliary data for `hash' and `less'. */struct hash를 가보니까 aux는 원래 이렇게 쓰면 안되는 것 같기도 하고
결국 답 코드 봤는데 훨씬 복잡함.
타입 따라 초기화도 다르게 해주고 없어지는거 일일이 복사해주고...
You will need to allocate uninit page and claim them immediately.
아까 지나쳤던 이게 그래야 한다는 걸 암시해줬던 것 같기도 하고
큰일났다.
할만큼 했다 생각하고 통과한 동기 코드에서 uninit_destroy(), anon_destroy(), supplemental_page_table_copy(), supplemental_page_table_kill() 그대로 다 복붙해봤는데도 통과를 못함.
이럼 걍 답이 없는데 ㅋㅋ...;
블로그를 참고해보자
걍 이거 보고 처음부터 다 다시 점검
hash_destroy()는 아까 터져서 그랬나 이상하다고 생각해서 그랬나
hash_apply()로 넘어갔었는데
hash_clear()를 사용해야 한다고 함.
hash_clear()에는 해시 테이블의 element_cnt를 낮춰주는게 들어가 있어서 그런가.
ㅋㅋㅋㅋㅋ 함수 죄다 답지로 바꿔줬는데 이제는 아예 터지기 시작했다.
로직이 중간에 섞여서 꼬인게 강력하게 의심되지만
그걸 어디에서부터 어떻게 찾아야될지도 막막하다.
아예 처음부터 다시 하는게 빠를듯
⚔️ 백준
📌 1463 1로 만들기
import sys
sys.setrecursionlimit(10**6)
def memo(x,dp):
if x==1:
return
if x%2==0 and (dp[x]+1)<dp[x//2]:
dp[x//2]=dp[x]+1
memo(x//2,dp)
if x%3==0 and (dp[x]+1)<dp[x//3]:
dp[x//3]=dp[x]+1
memo(x//3,dp)
if (dp[x]+1)<dp[x-1]:
dp[x-1]=dp[x]+1
memo(x-1,dp)
x=int(input())
dp=[1000001]*(x+1)
dp[x]=0
memo(x,dp)
print(dp[1])메모리 초과 뜸.
재귀 설계를 뭔가 잘못했나봄.
x=int(input())
dp=[float('inf')]*(x+1)
dp[1]=0
for i in range(1,x):
if (i+1)<(x+1):
dp[i+1] = min(dp[i+1],dp[i]+1)
if (i*2)<(x+1):
dp[i*2] = min(dp[i*2],dp[i]+1)
if (i*3)<(x+1):
dp[i*3] = min(dp[i*3],dp[i]+1)
print(dp[x])짜증나서 상향식 반복문으로 품
근데 좀 많이 느린듯?
x에서부터 시작하면 불필요한 연산 안 해도 되는데
1부터 x까지 거슬러 올라가다보니 불필요하게 2(x-1) 뭐 이런것들까지 연산에 들어가버림.
남의 풀이 보기
'맞힌 사람'으로 들어가면 시간순으로 풀이들을 볼 수 있다는거 배움.
d={1:0}
d[2]=1
print(d) # {1: 0, 2: 1}아 딕셔너리 키 없을 때도 그냥 초기화해주면 생기는구나
처음 앎
dic={1:0,2:1,3:1}
def fib(x: int) -> int: #타입힌트, int로 입력받고 int로 반환하는 함수라는 뜻. 함수 에러만 안난다면 힌트무시하고 다른자료형 넣어도 됨
if x in dic: #if x in list(dic.keys())
return dic[x]
t= 1+ min(fib(x//3)+x%3, fib(x//2)+x%2)
''' 나눠진다는 조건에 목 맬 필요없이 냅다 나눠서
나머지는 -1 연산 쓴다고 생각하고 더해주기
//3 //2 두 가지 중에 더 적은 연산으로 만들어진 아이를 택함'''
dic[x]=t
return t
print(fib(int(input()))) #x=int(input()) 앞에 이런거 안쓰고 코드 줄일수도있구나시간 제일 빠른 코드
만약 x가 3이나 2로 나누어떨어지지 않으면, 나머지가 발생합니다. 그 나머지는 결국 -1 연산을 사용하는 것과 동일하다는 의미입니다. 예를 들어, x % 3이 2인 경우, 그 값은 2번의 -1 연산(두 번 빼기)을 수행한다고 생각할 수 있습니다.
gpt한테 주석의 의미를 물어봄
오 개똑똑한 풀이네
x=int(input())
dp={1:0}
def rec(n):
if n in dp.keys():
return dp[n]
if (n%3==0) and (n%2==0):
dp[n]=min(rec(n//3)+1, rec(n//2)+1)
elif n%3==0:
dp[n]=min(rec(n//3)+1, rec(n-1)+1)
elif n%2==0:
dp[n]=min(rec(n//2)+1, rec(n-1)+1)
else:
dp[n]=rec(n-1)+1
return dp[n]
print(rec(x))딕셔너리 테크닉까지만 써도 굉장히 빠르다.
X = int(input())
dp = [0] * (X + 1)
for i in range(2, X + 1):
dp[i] = dp[i - 1] + 1
if i % 2 == 0:
dp[i] = min(dp[i], dp[i // 2] + 1)
if i % 3 == 0:
dp[i] = min(dp[i], dp[i // 3] + 1)
print(dp[X])제일 이해하기 쉬운 건 이런 느낌 (딕셔너리에 비해선 훨씬 느리지만 내것보단 빠름)
