오늘 한 일 👩💻
- 알고리즘
- memory management 구현 시작
알고리즘
https://www.acmicpc.net/problem/10026
10026번: 적록색약
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)
www.acmicpc.net
Memory Management
1. 테스트에 관하여
저번주차와 다르게 테스트하기 너무 어렵다.
그래서 이번주차부터는 ASSERT문을 사이에 넣어서 하고 있는데... 생각보다 어렵다.
이 고민에 관하여 우리반 홍교수님께 여쭤봤더니, 동의하는 부분이며 Anonymous page부터는 좀 괜찮을 것이라고 하셨다.
근데 나의 이번 목표는 최대한 적절한 곳에 ASSERT문을 넣어서 나중에 큰 단위로 테스트할 때, 디버깅을 쉽게 할 생각이라 일단 교수님의 조언을 받아 해당 함수를 테스트하기전에 Kernel Panic으로 가져가버리는 것들을 일단 내리면서 확인하고 있다. 그러다보니, frame 관련 함수를 구현하게 되고, 또 새로운 흐름이 이러지는데 이것이 나쁘진 않은 것 같다.
2. frame table
get_frame 함수를 구현하면서 frame을 어떻게 관리할지 고민이 되었다. 일단 malloc을 사용하여 할당받을지, 아님 테이블을 리스트로 만들어서 관리할지 말이다. 다른 분들한테 여쭤보니 다들 malloc으로 하길래 그렇게 할까 하다가, 마지막으로 GPT한테 물어봤다. GPT의 답변은 다음과 같다.
GPT 왈
malloc 함수는 동적 메모리 할당을 위한 일반적인 라이브러리 함수이며, 메모리 블록을 할당하고 관리하기 위해 복잡한 알고리즘과 데이터 구조를 사용합니다. malloc 함수를 사용하여 프레임을 할당하면 일반적으로 메모리 할당 및 해제에 대한 추가적인 오버헤드가 발생하게 됩니다.
반면에 연결 리스트로 프레임을 관리하면, 각 노드가 하나의 프레임을 나타내고 다음 노드를 가리키는 구조로 되어 있습니다. 연결 리스트를 사용하면 프레임 할당과 해제가 간단한 노드 삽입과 제거 연산으로 처리될 수 있습니다. 이러한 연산은 보통 O(1)의 시간 복잡도를 갖습니다.
따라서, malloc 함수를 사용하는 것보다 연결 리스트로 프레임을 관리하는 것이 일반적으로 더 효율적입니다. 그러나 이는 배열을 사용할 수 없는 경우에 한정된 이야기입니다. 배열을 사용할 수 있다면, 배열을 사용하여 프레임 테이블을 구현하는 것이 더욱 효율적일 것입니다.
그래서 리스트로 만들어서 하고 있다.
3. 동료학습
오늘도 역시 동료학습의 효과를 경험했다. 일단 질문을 던지면서 얻는게 있었고, 받은 것을 답변하면서 함께 고민하는 것도 마찬가지다.
첫번째로 같이 살펴본 부분은 Anonymous page의 uninit_new 함수인데, 초기화하는 코드이다.
/* DO NOT MODIFY this function */
void
uninit_new (struct page *page, void *va, vm_initializer *init,
enum vm_type type, void *aux,
bool (*initializer)(struct page *, enum vm_type, void *)) {
ASSERT (page != NULL);
*page = (struct page) {
.operations = &uninit_ops,
.va = va,
.frame = NULL, /* no frame for now */
.uninit = (struct uninit_page) {
.init = init,
.type = type,
.aux = aux,
.page_initializer = initializer,
}
};
}
중간에 .operations, .va, .frame, .uninit이 무엇인지인데, 잘 보니 자바의 constructor 같은 쓰임으로 사용되는 것이었다. 덕분에 C언어에서 생성자는 이렇게~ 쓰는 것을 이해할 수 있었다.
두번째는 vm_alloc_page_with_initializer 함수이다.
/* Create the pending page object with initializer. If you want to create a
* page, do not create it directly and make it through this function or
* `vm_alloc_page`. */
bool
vm_alloc_page_with_initializer (enum vm_type type, void *upage, bool writable,
vm_initializer *init, void *aux) {
ASSERT (VM_TYPE(type) != VM_UNINIT)
struct supplemental_page_table *spt = &thread_current ()->spt;
/* Check wheter the upage is already occupied or not. */
if (spt_find_page (spt, upage) == NULL) {
/* TODO: Create the page, fetch the initialier according to the VM type,
* TODO: and then create "uninit" page struct by calling uninit_new. You
* TODO: should modify the field after calling the uninit_new. */
/* TODO: Insert the page into the spt. */
}
err:
return false;
}TODO를 살펴보면, 먼저 initializer를 하고, uninit_new를 이후에 하라고 하는데 일단 하긴해도 그게 무슨 의미인지 이해하기 어려웠다.
일단 먼저 구현해보면서(일단 해보는 것이 중요한 것 같음...), 이해해본 결과는 다음과 같다.
예를들어, `int a = 3;`이라는 것은 다음을 의미한다.
1. int형의 a라는 변수 선언한다.
2. a라는 변수를 3으로 초기화한다.
즉 이 코드는 type에 따라, page 구조체의 타입을 선언하고
선언된 구조체에 vm_alloc_page_with_initializer 함수의 인자로 받은 값들을 가지고 초기화시켜주는 단계인 것이다!!!
(자고 일어나니 틀렸다고 한다...ㅎ)
아직 이 부분은 구현하지 않았지만 덕분에 미래의 내가 좀 더 수월해지지 않을까 싶다.
빨리 남은 부분도 속도내야할 것 같다.
함께 자라기라는 책을 거의 다 읽어서, 새로운 책을 빌려왔다. 바로 TDD와 코딩을 지탱하는 기술이다.
TDD는 내가 지향하는 바를 담고 있는 책인 것 같아서 기대된다. 책을 매일 조금씩이라도 읽는 것은 좋은 습관이라 생각한다.
팀원들과 화합의 시간을 가졌다.
🧠 아이디어: GPT 플러그인
GPT 답변 중, 발췌하고 싶은 내용을 드래그하고 버튼을 클릭하면 내가 지정한 노션 페이지 또는 github action을 통해 github으로 전달하여 저장해주는 플러그인을 시간날 때 만들어보고 싶다.
내일 할 일 📝
- ~Anonymous page까지 구현
- gitbook 읽기
