the-ze

가상 페이지라고도 불리는 “페이지”는, 4,096 바이트(페이지 크기)의 길이를 가지는 가상 메모리의 연속된 영역이다. 페이지는 반드시 페이지에 정렬(page-aligned)되어 있어야 한다. 즉, 각 페이지는 페이지 크기(4KiB)로 균등하게 나누어지는 가상 주소에서 시작해야 한다는 말이다.

그러므로 64비트 가상주소의 마지막 12비트는 페이지 오프셋(또는 그냥 “오프셋”)이다. 상위 비트들은 페이지 테이블의 인덱스를 표시하기 위해 쓰인다. 64비트 시스템은 4단계 페이지 테이블을 사용하는데, 아래 그림과 같은 가상주소를 만들어준다.

63          48 47            39 38            30 29            21 20         12 11         0
+-------------+----------------+----------------+----------------+-------------+------------+
| Sign Extend |    Page-Map    | Page-Directory | Page-directory |  Page-Table |    Page    |
|             | Level-4 Offset |    Pointer     |     Offset     |   Offset    |   Offset   |
+-------------+----------------+----------------+----------------+-------------+------------+
              |                |                |                |             |            |
              +------- 9 ------+------- 9 ------+------- 9 ------+----- 9 -----+---- 12 ----+
                                          Virtual Address

각 프로세스는 KERN_BASE (0x8004000000) 미만의 가상주소값을 가지는 독립적인 유저(가상)페이지 집합을 가진다. 반면에 커널(가상)페이지 집합은 전역적이며, 어떤 쓰레드나 프로세스가 실행되고 있든 간에 항상 같은 위치에 남아 있다. 커널은 유저 페이지와 커널 페이지 모두에 접근할 수 있지만, 유저 프로세스는 본인의 유저 페이지에만 접근할 수 있다.

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

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

x86-64 시스템은 물리주소에 있는 메모리에 직접적으로 접근하는 방법을 제공하지 않는다. Pintos는 커널 가상 메모리를 물리 메모리에 직접 매핑하는 방식을 통해서 이 문제를 해결한다 - 커널 가상메모리의 첫 페이지는 물리메모리의 첫 프레임에 매핑되어 있고, 두번째 페이지는 두번째 프레임에 매핑되어 있고, 그 이후도 이와 같은 방법으로 매핑되어 있다. 그러므로 커널 가상메모리를 통하면 프레임들에 접근할 수 있다.

페이지 테이블은 CPU가 가상주소를 물리주소로, 즉 페이지를 프레임으로 변환하기 위해 사용하는 자료구조이다. 페이지 테이블 포맷은 x86-64 아키텍쳐에 의해 결정되었다. Pintos는 threads/mmu.c안에 페이지 테이블을 관리하는 코드를 제공한다.

아래 도표는 페이지와 프레임 사이의 관계를 나타낸다. 왼쪽에 보이는 가상주소는 페이지 넘버와 오프셋을 포함하고 있다. 페이지 테이블은 페이지 넘버를 프레임 넘버로 변환하며, 프레임 넘버는 오른쪽에 보이는 것처럼 물리주소를 획득하기 위한 미수정된 오프셋과 결합되어 있다.

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

스왑 슬롯은 스왑 파티션 내의 디스크 공간에 있는 페이지 크기의 영역이다. 하드웨어적 제한들로 인해 배치가 강제되는 것(정렬)이 프레임에서보단 슬롯에서 더 유연한 편이지만, 정렬한다고 해서 별다른 부정적인 영향이 생기는 건 아니기 때문에 스왑 슬롯은 페이지 크기에 정렬하는 것이 좋다.

각 자료구조에서 각각의 원소가 어떤 정보를 담을지를 정해야 했었다. 또한 자료구조의 범위를 지역(프로세스별)으로 할지, 전역(전체 시스템에 적용)으로 할지도 정해야 하고, 해당 범위에 필요한 인스턴스의 수도 결정해야 한다. 설계를 단순화하기 위해, non-pageable 메모리 (calloc 이나 malloc 에 의해 할당된)에 이러한 자료구조들을 저장할 수 있다.

userprog/process.c에 있는 load_segment와 lazy_load_segment를 구현해야 했다. 실행파일로부터 세그먼트가 로드되는 것을 구현하고, 구현된 모든 페이지들은 지연적으로 로드될 것이다. 즉 이 페이지들에 발생한 page fault를 커널이 다루게 된다는 의미이다.

program loader의 핵심인 userprog/process.c 의 load_segment loop 내부를 수정해야 했다. 루프를 돌 때마다 load_segment는 대기 중인 페이지 오브젝트를 생성하는vm_alloc_page_with_initializer를 호출한다. Page Fault가 발생하는 순간은 Segment가 실제로 파일에서 로드될 때 이다.

static bool
load_segment(struct file *file, off_t ofs, uint8_t *upage,
			 uint32_t read_bytes, uint32_t zero_bytes, bool writable)
{
	ASSERT((read_bytes + zero_bytes) % PGSIZE == 0);
	ASSERT(pg_ofs(upage) == 0);
	ASSERT(ofs % PGSIZE == 0);

	while (read_bytes > 0 || zero_bytes > 0)
	{
		/* Do calculate how to fill this page.
		 * We will read PAGE_READ_BYTES bytes from FILE
		 * and zero the final PAGE_ZERO_BYTES bytes. */
		size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
		size_t page_zero_bytes = PGSIZE - page_read_bytes;

		/* TODO: Set up aux to pass information to the lazy_load_segment. */
		struct lazy *aux = (struct lazy*)malloc(sizeof(struct lazy));
		aux->file = file;
		aux->ofs = ofs;
		aux->read_bytes = page_read_bytes;
		aux->zero_bytes = page_zero_bytes;

		if (!vm_alloc_page_with_initializer (VM_ANON, upage,
					writable, lazy_load_segment, aux)){
			return false;
		}

		/* Advance. */
		read_bytes -= page_read_bytes;
		zero_bytes -= page_zero_bytes;
		upage += PGSIZE;
		ofs += page_read_bytes;
	}
	return true;
}

VM 시스템은 mmap 영역에서 페이지를 lazy load하고 mmap된 파일 자체를 매핑을 위한 백업 저장소로 사용해야 한다. 이 두 시스템 콜을 구현하려면 vm/file.c에 정의된 do_mmap과 do_munmap을 구현해서 사용해야 한다.

fd로 열린 파일의 오프셋(offset) 바이트부터 length 바이트 만큼을 프로세스의 가상주소공간의 주소 addr 에 매핑 한다.
전체 파일은 addr에서 시작하는 연속 가상 페이지에 매핑된다. 파일 길이(length)가 PGSIZE의 배수가 아닌 경우 최종 매핑된 페이지의 일부 바이트가 파일 끝을 넘어 "stick out"된다. page_fault가 발생하면 이 바이트를 0으로 설정하고 페이지를 디스크에 다시 쓸 때 버린다.

성공하면 이 함수는 파일이 매핑된 가상 주소를 반환한다. 실패하면 파일을 매핑하는 데 유효한 주소가 아닌 NULL을 반환해야 한다.

void *
do_mmap (void *addr, size_t length, int writable,
		struct file *file, off_t offset) {


	struct file* new_file = file_reopen(file);
	if(new_file == NULL){
		return NULL;
	}

	void* return_address = addr;
	
	size_t read_bytes;
	if (file_length(new_file) < length){
		read_bytes = file_length(new_file);
	} else {
		read_bytes = length;
	}

	size_t zero_bytes = PGSIZE - (read_bytes%PGSIZE);
	
	ASSERT (pg_ofs (addr) == 0);
	ASSERT (offset % PGSIZE == 0);
	ASSERT ((read_bytes + zero_bytes) % PGSIZE == 0);

	while (read_bytes > 0 || zero_bytes > 0) {
			/* Do calculate how to fill this page.
			* We will read PAGE_READ_BYTES bytes from FILE
			* and zero the final PAGE_ZERO_BYTES bytes. */
		size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
		size_t page_zero_bytes = PGSIZE - page_read_bytes;

		struct lazy* file_lazy = (struct lazy*)malloc(sizeof(struct lazy));
		file_lazy->file = new_file;
		file_lazy->ofs = offset;
		file_lazy->read_bytes = page_read_bytes;
		file_lazy->zero_bytes = page_zero_bytes;

		if (!vm_alloc_page_with_initializer(VM_FILE, addr, writable, lazy_load_segment, file_lazy)){
			return NULL;
		}		

		/* Advance. */
		read_bytes -= page_read_bytes;
		zero_bytes -= page_zero_bytes;
		addr += PGSIZE;
		offset += page_read_bytes;
	}
	return return_address;
}

지정된 주소 범위 addr에 대한 매핑을 해제한다.
지정된 주소는 아직 매핑 해제되지 않은 동일한 프로세서의 mmap에 대한 이전 호출에서 반환된 가상 주소여야 한다.

void
do_munmap (void *addr) {
    struct supplemental_page_table *spt = &thread_current()->spt;
    struct page *page = spt_find_page(spt, addr);

	int page_count;
	if (file_length(&page->file)%PGSIZE != 0){
 	    page_count = file_length(&page->file) + PGSIZE;
	} else {
		page_count = file_length(&page->file);
	}

    for (int i = 0; i < page_count/PGSIZE; i++)
    {
        if (page)
            destroy(page);
        addr += PGSIZE;
        page = spt_find_page(spt, addr);
    }
}

file-backed 페이지의 내용은 파일에서 가져오므로 mmap된 파일을 백업 저장소로 사용해야 한다. 즉, file-backed 페이지를 evict하면 해당 페이지가 매핑된 파일에 다시 기록된다.

파일에서 콘텐츠를 읽어 kva 페이지에서 swap in한다. 파일 시스템과 동기화해야 한다.

static bool
file_backed_swap_in (struct page *page, void *kva) {
	struct file_page *file_page = &page->file;
	struct lazy* aux = (struct lazy*)page->uninit.aux;

	lock_acquire(&filesys_lock);
	bool result = lazy_load_segment(page, aux);
	lock_release(&filesys_lock);

	return result;
}

내용을 다시 파일에 기록하여 swap out한다. 먼저 페이지가 dirty인지 확인하는 것이 좋다. 더럽지 않으면 파일의 내용을 수정할 필요가 없다. 페이지를 교체한 후에는 페이지의 더티 비트를 꺼야 한다.

static bool
file_backed_swap_out (struct page *page) {
	struct file_page *file_page = &page->file;
	struct lazy* aux = (struct lazy*)page->uninit.aux;
	struct file * file = aux->file;

	if(pml4_is_dirty(thread_current()->pml4,page->va)){
		file_write_at(file,page->va, aux->read_bytes, aux->ofs);
		file_write_at(file_page->file,page->va, file_page->read_bytes, file_page->ofs);
		pml4_set_dirty(thread_current()->pml4, page->va, false);
	}
	page->frame->page = NULL;
	page->frame = NULL;
	pml4_clear_page(thread_current()->pml4, page->va);
	return true;
}

https://github.com/yunsejin/PintOS_RE/tree/Project3_RE

https://www.cs.usfca.edu/~galles/visualization/BTree.html

B-tree는 데이터베이스와 파일 시스템에서 널리 사용되는 자료구조로, 데이터를 정렬된 상태로 저장하고 효율적인 검색, 순차 접근, 삽입, 삭제를 지원한다. 이진 탐색 트리(BST)를 확장한 형태로, 더 많은 자식을 가질 수 있어 디스크와 같은 보조 메모리에 저장된 대량의 데이터를 관리하는 데 적합하다.

모든 리프 노드가 같은 레벨에 있어 균형 잡힌 트리를 유지한다.노드가 가득 찰 경우, 중간값을 기준으로 노드를 분할하여 상위 노드로 키를 올린다.루트에서 리프로 가는 경로의 길이가 모두 동일하다.각 노드는 최대 m개의 자식을 가질 수 있는데, 이때 m은 트리의 차수이다.

트리를 탐색하며 키 값을 비교하여 데이터 위치를 찾는다.적절한 위치에 새로운 키를 삽입하고, 필요시 노드 분할을 수행한다.키를 삭제하고, 필요시 노드 병합이나 재배치를 통해 트리의 균형을 유지한다.

키-값 쌍을 사용하여 레코드를 빠르게 찾을 수 있게 해준다. 파일의 메타데이터를 관리하거나, 파일 내의 특정 데이터를 찾는 데 사용된다.

def insert(node, key):
    # 적절한 리프 노드 찾기
    if node is leaf:
        if node has space:
            insert key in node
        else:
            split node
            insert key in appropriate node
    else:
        find child node that should contain key
        insert(child node, key)

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

B+트리는 데이터베이스와 파일 시스템에서 사용되는 인덱스 메커니즘의 일종이다. 이는 탐색, 삽입, 삭제, 순회 등의 동작을 로그 시간 내에 수행할 수 있는 이진 검색 트리의 확장된 형태로, 디스크 I/O 작업의 최소화를 목표로 한다.

B+트리는 전에 포스팅한 RB트리처럼 몇 가지 규칙이 있다.

1. 모든 데이터는 리프 노드에 저장된다: 이로 인해 순차 탐색이 용이하다.
2. 내부 노드는 데이터가 아닌 키를 저장한다: 이 키들은 리프 노드에 있는 데이터를 가리키는 포인터 역할을 한다.
3. 리프 노드는 서로 연결리스트로 연결되어 있다: 이는 범위 검색을 효율적으로 만든다.
4. 균형 트리이다: 모든 리프 노드는 같은 레벨에 위치한다. 따라서 탐색 시간이 일정하다.
5. 분할과 병합을 통한 동적 조정이 가능하다: 삽입이나 삭제로 인해 노드의 크기가 최대 또는 최소를 초과하면, 자동으로 분할 또는 병합이 이루어진다.

B+트리는 노드의 최대 차수(또는 분기)를 M이라 할 때, 

• 각 내부 노드는 최대 M-1개의 키를 가질 수 있으며, 최소 ceil(M/2)-1개의 키를 가져야 한다. (단, 루트 노드는 이 조건에서 예외일 수 있다.)
• 각 리프 노드는 최대 M개의 데이터를 가질 수 있으며, 최소 ceil(M/2)개의 데이터를 가져야 한다.

https://www.cs.usfca.edu/~galles/visualization/Trie.html

Trie는 검색 트리의 일종으로, 문자열의 집합을 저장하는데 특화된 자료구조이다. 주로 사전과 같은 문자열을 빠르게 검색하고, 추가하고, 삭제하는 데 사용된다. Trie의 각 노드는 문자열의 한 문자를 나타내며, 루트에서부터 특정 노드까지의 경로는 그 노드에 도달하기 위한 문자열의 접두사를 형성한다.

루트 노드: Trie의 시작점. 보통 비어있거나, 특정 기준으로 시작 문자를 가질 수 있다.

자식 노드: 각 노드는 0개 이상의 자식을 가질 수 있으며, 각 자식 노드는 알파벳이나 문자열 내의 다음 문자를 나타낸다.

마지막 노드: 문자열의 끝을 나타내는 특별한 표시(예: * 또는 특정 플래그)를 갖는 노드. 이를 통해 문자열의 존재 여부를 판별할 수 있다.

문자열을 검색할 때, 길이가 n인 문자열에 대해 최악의 경우 시간 복잡도는 O(n)이다. 하지만 실제로는 저장된 문자열의 수보다 검색할 문자열의 길이에 더 의존적이므로, 매우 효율적이다. 그리고, Trie는 접두사를 공유하는 문자열들을 효율적으로 관리할 수 있어, 자동 완성과 같은 기능 구현에 적합하다.

문자와 노드 매핑을 위해 추가적인 메모리 공간이 필요하며, 특히 문자의 종류가 많은 경우(예: 유니코드 문자열) 메모리 사용량이 많아질 수 있으므로 주의해야 한다.

Trie는 문자열 검색, 자동 완성, 사전 추천 시스템, IP 라우팅 등 다양한 분야에서 활용된다.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True
    
    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

# Trie 사용 예제
trie = Trie()
trie.insert("apple")
print(trie.search("apple"))  # True를 출력
print(trie.search("app"))    # False를 출력, "app"은 단어의 끝이 아님

trie.insert("app")
print(trie.search("app"))    # True를 출력, "app"이 삽입되었기 때문

1. TrieNode 클래스는 Trie의 각 노드를 나타내며, 자식 노드들을 딕셔너리(children)로 관리하고, 단어의 끝을 나타내는 플래그(is_end_of_word)를 갖는다.
2. Trie 클래스는 Trie 자체를 나타내며, 루트 노드(root)를 가지고 있고, 단어를 삽입(insert)하고 검색(search)하는 메서드를 제공한다.
3. insert 메서드는 주어진 단어를 한 글자씩 Trie에 삽입한다. 해당 글자의 노드가 존재하지 않으면 새 노드를 생성한다.
4. search 메서드는 주어진 단어를 Trie에서 찾는다. 단어의 모든 글자가 순서대로 Trie에 존재하고, 마지막 글자가 단어의 끝을 나타내는 노드면 True를, 그렇지 않으면 False를 반환한다.

Minimum Spanning Tree(MST, 최소 신장 트리)는 가중치가 있는 그래프에서 만들 수 있는 신장 트리 중에서 가중치의 합이 최소인 트리를 말한다. 신장 트리란, 원래의 그래프의 모든 정점을 포함하며 사이클이 없는 연결 부분 그래프이다. MST는 네트워크 설계, 클러스터 분석, 그래프 분석 등 다양한 분야에서 응용된다.

Kruskal의 알고리즘은 간선을 가중치의 오름차순으로 정렬한 후, 사이클을 형성하지 않는 방식으로 간선을 선택한다. 이 과정에서 분리 집합 자료구조(Disjoint Set)를 사용하여 효율적으로 사이클을 확인한다.

Prim의 알고리즘은 시작 정점을 선택한 후, 트리에 인접한 간선 중에서 최소 가중치를 가진 간선을 선택하여 트리를 확장한다. 이 과정은 모든 정점이 트리에 포함될 때까지 반복한다.

Kruskal 알고리즘을 구현하기 위해 분리 집합(Disjoint Set) 자료구조를 사용하는 것이 일반적이다. 이는 각 정점을 자신만을 포함하는 집합으로 초기화하고, 간선을 하나씩 확인하면서 두 정점이 서로 다른 집합에 속해 있다면(즉, 사이클을 형성하지 않으면) 두 집합을 합치는 방식으로 작동한다.

Krulskal 알고리즘 구현 방법은

1. 모든 간선을 가중치에 따라 오름차순으로 정렬한다.
2. 간선을 순회하며, 현재 선택한 간선이 사이클을 형성하지 않으면 신장 트리에 포함시킨다.
3. 모든 정점이 연결될 때까지 2번을 반복한다.

class DisjointSet:
    def __init__(self, vertices):
        self.vertices = vertices
        self.parent = {v: v for v in vertices}
        self.rank = {v: 0 for v in vertices}

    def find(self, item):
        if self.parent[item] == item:
            return item
        else:
            return self.find(self.parent[item])

    def union(self, set1, set2):
        root1 = self.find(set1)
        root2 = self.find(set2)
        if root1 != root2:
            if self.rank[root1] > self.rank[root2]:
                self.parent[root2] = root1
            elif self.rank[root1] < self.rank[root2]:
                self.parent[root1] = root2
            else:
                self.parent[root2] = root1
                self.rank[root1] += 1

def kruskal(graph):
    vertices, edges = graph
    disjoint_set = DisjointSet(vertices)
    mst = []
    edges.sort(key=lambda edge: edge[2])  # 간선을 가중치에 따라 오름차순으로 정렬

    for edge in edges:
        v1, v2, weight = edge
        if disjoint_set.find(v1) != disjoint_set.find(v2):
            disjoint_set.union(v1, v2)
            mst.append(edge)

    return mst

# 그래프 정의: (정점 리스트, 간선 리스트)
graph = (['A', 'B', 'C', 'D', 'E', 'F'], 
         [('A', 'B', 2), ('A', 'C', 3), ('B', 'C', 1), 
          ('B', 'D', 4), ('C', 'E', 6), ('D', 'E', 5),
          ('E', 'F', 2), ('D', 'F', 7)])

# Kruskal 알고리즘 실행
mst = kruskal(graph)
print("Minimum Spanning Tree:", mst)

1. DisjointSet 클래스는 각 정점의 부모를 저장하고, 두 정점이 같은 집합에 속하는지 확인하고, 두 집합을 합치는 기능을 제공한다.
2. kruskal 함수는 주어진 그래프에서 MST를 찾아 반환한다. 먼저 모든 간선을 가중치 기준으로 정렬하고, 사이클을 형성하지 않는 간선만 선택하여 MST를 구성한다.

Prim 알고리즘을 파이썬으로 구현할 때, 우선순위 큐를 사용하여 트리에 인접한 간선 중 최소 가중치를 가진 간선을 효율적으로 찾을 수 있다.

Prim 알고리즘 구현 방법은

1. 임의의 정점을 선택하여 시작한다.
2. 선택된 정점과 인접한 간선 중 가장 가중치가 낮은 간선을 선택하고, 해당 간선이 연결하는 정점을 트리에 추가한다.
3. 모든 정점이 트리에 포함될 때까지 2번을 반복한다.

import heapq

def prim(graph, start_vertex):
    visited = set([start_vertex])
    edges = [(cost, start_vertex, to) for to, cost in graph[start_vertex].items()]
    heapq.heapify(edges)
    mst = []

    while edges:
        cost, frm, to = heapq.heappop(edges)
        if to not in visited:
            visited.add(to)
            mst.append((frm, to, cost))
            
            for to_next, cost in graph[to].items():
                if to_next not in visited:
                    heapq.heappush(edges, (cost, to, to_next))

    return mst

# 그래프 정의: 각 정점에서 다른 정점으로의 가중치가 있는 엣지를 딕셔너리로 표현
graph = {
    'A': {'B': 2, 'C': 3},
    'B': {'A': 2, 'C': 1, 'D': 4, 'E': 2},
    'C': {'A': 3, 'B': 1, 'F': 5},
    'D': {'B': 4, 'E': 3},
    'E': {'B': 2, 'D': 3, 'F': 3},
    'F': {'C': 5, 'E': 3},
}

# Prim 알고리즘을 이용해 최소 신장 트리(MST) 찾기
mst = prim(graph, 'A')
print("Minimum Spanning Tree:", mst)

1. 시작 정점을 선택하고 방문한 정점 집합에 추가한다.
2. 시작 정점에 인접한 간선을 우선순위 큐에 추가한다.
3. 우선순위 큐에서 가중치가 가장 낮은 간선을 추출한다. 이 간선이 연결하는 정점이 이미 방문한 정점 집합에 속하지 않는다면, 이 간선을 최소 신장 트리에 추가하고, 해당 정점을 방문한 정점 집합에 추가한다.
4. 새롭게 추가된 정점에 인접한 간선 중 아직 방문하지 않은 정점으로의 간선을 우선순위 큐에 추가한다.
5. 모든 정점이 방문될 때까지 3번과 4번 과정을 반복한다.

MST 알고리즘의 선택은 그래프의 특성(간선의 수, 그래프의 밀집도 등)에 따라 달라질 수 있다. 예를 들어, 간선의 수가 많이 밀집된 그래프에서는 Prim의 알고리즘이, 간선의 수가 상대적으로 적은 그래프에서는 Kruskal의 알고리즘이 더 효율적일 수 있다.

목표는 userprog/syscall.c 안에 시스템 콜 핸들러를 구현해야한다. 제공된 최소한의 기능은 프로세스를 종료 시키므로써 시스템 콜을 “다룬다.(handles).”

구현하는 시스템 콜 핸들러는 시스템 콜 번호를 받아오고, 어떤 시스템 콜 인자들을 받아오고, 그에 알맞은 액션을 취해야 한다.

%rax 는 시스템 콜 번호 이다. 4번째 인자는 %r10 이지 %rcx가 아니다. 그러므로 시스템 콜 핸들러 syscall_handler() 가 제어권을 얻으면 시스템 콜 번호는 rax에 있고, 인자는 %rdi, %rsi, %rdx, %r10, %r8, %r9 순서로 전달된다.

시스템 콜 핸들러를 호출한 콜러의 레지스터는 전달받은 struct intr_frame 에 접근할 수 있다. (struct intr_frame은 커널 스택에 있다.) 함수 리턴 값을 위한 x86-64의 관례는 그 값을 RAX 레지스터에 넣는 것 이다. 값을 리턴하는 시스템 콜도 struct intr_frame의 rax멤버를 수정하는 식으로 이 관례를 따를 수 있다.

halt()는 power_off()를 호출해서 Pintos를 종료한다. (power_off()는 src/include/threads/init.h에 선언되어 있음)이 함수는 웬만하면 사용되지 않아야 한다. deadlock 상황에 대한 정보 등등 뭔가 조금 잃어 버릴 수도 있다.

void halt(void)
{
	power_off();
}

exit()은 현재 동작중인 유저 프로그램을 종료한다. 커널에 상태를 리턴하면서 종료한다. 만약 부모 프로세스가 현재 유저 프로그램의 종료를 기다리던 중이라면, 그 말은 종료되면서 리턴될 그 상태를 기다린다는 것 이다. 관례적으로, 상태 = 0 은 성공을 뜻하고 0 이 아닌 값들은 에러를 뜻 한다.

void exit(int status)
{
	struct thread *curr = thread_current();
	curr->exit_status = status;
	printf("%s: exit(%d)\n", curr->name, status);
	thread_exit();
}

create()는 file(첫 번째 인자)를 이름으로 하고 크기가 initial_size(두 번째 인자)인 새로운 파일을 생성한다. 성공적으로 파일이 생성되었다면 true를 반환하고, 실패했다면 false를 반환한다. 새로운 파일을 생성하는 것이 그 파일을 여는 것을 의미하지는 않는다.(파일을 여는 것은 open 시스템콜의 역할로, ‘생성’과 개별적인 연산이다.)

bool create(const char *file, unsigned initial_size)
{
	check_address(file);
	return filesys_create(file, initial_size);
}

open()은  file(첫 번째 인자)이라는 이름을 가진 파일을 연다. 해당 파일이 성공적으로 열렸다면, 파일 식별자로 불리는 비음수 정수(0또는 양수)를 반환하고, 실패했다면 -1를 반환한다. 0번 파일식별자와 1번 파일식별자는 이미 역할이 지정되어 있다. 0번은 표준 입력(STDIN_FILENO)을 의미하고 1번은 표준 출력(STDOUT_FILENO)을 의미한다. 

open 시스템 콜은 아래에서 명시적으로 설명하는 것처럼 시스템 콜 인자로서만 유효한 파일 식별자들을 반환하지 않는다. 각각의 프로세스는 독립적인 파일 식별자들을 갖는다. 파일 식별자는 자식 프로세스들에게 상속(전달)된다. 하나의 프로세스에 의해서든 다른 여러개의 프로세스에 의해서든, 하나의 파일이 두 번 이상 열리면 그때마다 open시스템콜은 새로운 식별자를 반환한다.

하나의 파일을 위한 서로 다른 파일 식별자들은 개별적인 close 호출에 의해서 독립적으로 닫히고 그 한 파일의 위치를 공유하지 않는다. 추가적인 작업을 하기 위해서는 open 시스템 콜이 반환하는 정수(fd)가 0보다 크거나 같아야 한다는 리눅스 체계를 따라야 한다.

int open(const char *file_name)
{
	check_address(file_name);
	struct file *file = filesys_open(file_name);
	if (file == NULL)
		return -1;

	int fd = process_add_file(file);
	if (fd == -1)
		file_close(file);

	return fd;
}

close()는 파일 식별자 fd를 닫는다. 프로세스를 나가거나 종료하는 것은 묵시적으로 그 프로세스의 열려있는 파일 식별자들을 닫는다. 마치 각 파일 식별자에 대해 이 함수가 호출된 것과 같다. 

void close(int fd)
{
	if (fd < 2)
		return;
	struct file *file = process_get_file(fd);
	if (file == NULL)
		return;
	file_close(file);
	process_close_file(fd);
}

read()는 buffer 안에 fd 로 열려있는 파일로부터 size 바이트를 읽는다. 실제로 읽어낸 바이트의 수 를 반환한다.(파일 끝에서 시도하면 0) 파일이 읽어질 수 없었다면 -1을 반환한다.(파일 끝이라서가 아닌 다른 조건에 때문에 못 읽은 경우)

int read(int fd, void *buffer, unsigned size)
{
	check_address(buffer);

	char *ptr = (char *)buffer;
	int bytes_read = 0;

	if (fd == STDIN_FILENO)
	{
		for (int i = 0; i < size; i++)
		{
			char ch = input_getc();
			if (ch == '\n')
				break;
			*ptr = ch;
			ptr++;
			bytes_read++;
		}
	}
	else
	{
		if (fd < 2)
			return -1;
		struct file *file = process_get_file(fd);
		if (file == NULL)
			return -1;
		lock_acquire(&filesys_lock);
		bytes_read = file_read(file, buffer, size);
		lock_release(&filesys_lock);
	}
	return bytes_read;
}

write()는 buffer로부터 open file fd로 size 바이트를 적어준다. 실제로 적힌 바이트의 수를 반환해주고, 일부 바이트가 적히지 못했다면 size보다 더 작은 바이트 수가 반환될 수 있다. 파일의 끝을 넘어서 작성하는 것은 보통 파일을 확장하는 것이지만, 파일 확장은 basic file system에 의해서는 불가능하다. 

이로 인해 파일의 끝까지 최대한 많은 바이트를 적어주고 실제 적힌 수를 반환하거나, 더 이상 바이트를 적을 수 없다면 0을 반환한다. fd 1은 콘솔에 적어준다. 콘솔에 작성한 코드가 적어도 몇 백 바이트를 넘지 않는 사이즈라면, 한 번의 호출에 있는 모든 버퍼를 putbuf()에 적어주는 것 이다.(더 큰 버퍼는 분해하는 것이 합리적)그렇지 않다면, 다른 프로세스에 의해 텍스트 출력 라인들이 콘솔에 끼게 (interleaved)되고, 읽는 사람과 채점 스크립트가 헷갈릴 것 이다.

int write(int fd, const void *buffer, unsigned size)
{
	check_address(buffer);
	int bytes_write = 0;
	if (fd == STDOUT_FILENO)
	{
		putbuf(buffer, size);
		bytes_write = size;
	}
	else
	{
		if (fd < 2)
			return -1;
		struct file *file = process_get_file(fd);
		if (file == NULL)
			return -1;
		lock_acquire(&filesys_lock);
		bytes_write = file_write(file, buffer, size);
		lock_release(&filesys_lock);
	}
	return bytes_write;
}

fork()는 THREAD_NAME이라는 이름을 가진 현재 프로세스의 복제본인 새 프로세스를 만든다.

피호출자(callee) 저장 레지스터인 %RBX, %RSP, %RBP와 %R12 - %R15를 제외한 레지스터 값을 복제할 필요가 없다. 자식 프로세스의 pid를 반환해야 한다. 그렇지 않으면 유효한 pid가 아닐 수 있다.

자식 프로세스에서 반환 값은 0이어야 한다. 자식 프로세스에는 파일 식별자 및 가상 메모리 공간을 포함한 복제된 리소스가 있어야 한다. 부모 프로세스는 자식 프로세스가 성공적으로 복제되었는지 여부를 알 때까지 fork에서 반환해서는 안된다. 즉, 자식 프로세스가 리소스를 복제하지 못하면 부모의 fork() 호출이 TID_ERROR를 반환할 것이다.

템플릿은 `threads/mmu.c`의 `pml4_for_each`를 사용하여 해당되는 페이지 테이블 구조를 포함한 전체 사용자 메모리 공간을 복사하지만, 전달된 `pte_for_each_func`의 누락된 부분을 채워야 한다.

tid_t process_fork(const char *name, struct intr_frame *if_ UNUSED)
{
	/* Clone current thread to new thread.*/
	struct thread *cur = thread_current();
	memcpy(&cur->parent_if, if_, sizeof(struct intr_frame));

	tid_t pid = thread_create(name, PRI_DEFAULT, __do_fork, cur);
	if (pid == TID_ERROR)
		return TID_ERROR;

	struct thread *child = get_child_process(pid);

	sema_down(&child->load_sema);

	if (child->exit_status == -2)
	{
		sema_up(&child->exit_sema);
		return TID_ERROR;
	}
	return pid;
}

exec()은 현재의 프로세스가 cmd_line에서 이름이 주어지는 실행가능한 프로세스로 변경된다. 이때 주어진 인자들을 전달한다. 성공적으로 진행된다면 어떤 것도 반환하지 않는다. 만약 프로그램이 이 프로세스를 로드하지 못하거나 다른 이유로 돌리지 못하게 되면 exit state -1을 반환하며 프로세스가 종료된다.

exec 함수를 호출한 쓰레드의 이름은 바꾸지 않는다. file descriptor는 exec 함수 호출 시에 열린 상태로 있다는 것을 알아둬야 한다.

int exec(const char *cmd_line)
{
	check_address(cmd_line);

	char *cmd_line_copy;
	cmd_line_copy = palloc_get_page(0);
	if (cmd_line_copy == NULL)
		exit(-1);
	strlcpy(cmd_line_copy, cmd_line, PGSIZE);

	if (process_exec(cmd_line_copy) == -1)
		exit(-1);
}

wait()는 자식 프로세스 (pid) 를 기다려서 자식의 종료 상태(exit status)를 가져온다. 만약 pid (자식 프로세스)가 아직 살아있으면, 종료 될 때 까지 기다린다. 종료가 되면 그 프로세스가 exit 함수로 전달해준 상태(exit status)를 반환한다. 

만약 pid (자식 프로세스)가 exit() 함수를 호출하지 않고 커널에 의해서 종료된다면 (e.g exception에 의해서 죽는 경우), wait(pid) 는 -1을 반환해야 한다.

부모 프로세스가 wait 함수를 호출한 시점에서 이미 종료되어버린 자식 프로세스를 기다리도록 하는 것은 합당하지만, 커널은 부모 프로세스에게 자식의 종료 상태를 알려주든지, 커널에 의해 종료되었다는 사실을 알려주든지 해야 한다.

int process_wait (tid_t child_tid) {
	struct thread *cur = thread_current();
	struct thread *child = get_child_process(child_tid);
	if (child == NULL)
		return -1;
	sema_down(&child->wait_sema);
	list_remove(&child->child_elem);
	sema_up(&child->exit_sema);
	return child->exit_status;
}

https://github.com/yunsejin/PintOS_RE/tree/Project2_RE

그래프(Graph)는 데이터의 집합을 정점(Vertex)과 이들 정점을 연결하는 간선(Edge)의 집합으로 표현한 자료구조다. 그래프는 다양한 종류가 있으며, 주요 분류 기준에는 방향성 여부와 가중치 존재 여부가 있다.

무방향 그래프(Undirected Graph)에서 간선은 방향성이 없어, 두 정점을 서로 연결만 시킨다는 의미를 가진다. 예를 들어, 정점 A와 B를 연결하는 간선은 "A에서 B로" 또는 "B에서 A로"의 구분 없이 양방향 모두를 의미한다. 서로간의 연결이 대칭적인 관계, 예를 들어 소셜 네트워크의 친구 관계, 도로망 등에서 사용된다.

방향 그래프(Directed Graph)에서 간선은 방향성을 가지며, "A에서 B로" 혹은 그 반대로의 명확한 방향이 존재한다. 이는 간선이 (A, B)로 표시될 때, A에서 B로의 한 방향 연결만을 의미한다. 방향이 중요한 관계를 모델링할 때 사용되며, 예로는 웹 페이지 간의 링크, 트위터의 팔로우 등이 있다.

가중치 그래프(Weighted Graph)에서 각 간선에는 가중치가 할당되어 있다. 이 가중치는 거리, 시간, 비용 등 간선을 통해 연결된 두 정점 사이의 관계의 "가중치"를 나타낸다. 가중치는 간선을 따라 이동하는 데 드는 비용이나 거리 등을 표현할 때 사용된다. 예를 들어, 도시 간의 이동 비용, 네트워크 상에서의 데이터 전송 시간 등을 모델링할 때 사용된다.

인접 행렬(Adjacency Matrix)은 그래프를 표현하는 방법 중 하나로, 그래프의 정점들 간의 연결 관계를 행렬로 나타낸 것이다. 이 방식은 그래프의 각 정점을 행렬의 행과 열에 대응시키고, 두 정점 사이에 간선이 존재하면 해당 위치의 행렬 값에 1(또는 가중치 값)을, 없으면 0을 저장한다.

V개의 정점을 가진 그래프는 V×V 크기의 행렬로 표현된다. 비방향 그래프의 경우, 인접 행렬은 대칭 행렬이 된다. 가중치가 있는 그래프의 경우, 1 대신 간선의 가중치 값을 행렬에 저장한다. 간선이 없는 경우 일반적으로 매우 큰 값(무한대를 의미하는 값)이나 -1을 사용하여 표현할 수 있다.

대각선 요소는 보통 0으로 설정된다, 자기 자신으로의 연결이 없다는 것을 의미한다. 하지만 특별한 경우(예를 들어, 루프를 허용하는 그래프)에는 다른 값을 가질 수도 있다.

그래프의 연결 관계를 간단하고 직관적으로 표현할 수 있고, 특정 두 정점 사이의 연결 여부를 O(1) 시간에 확인할 수 있다. 하지만 정점의 수에 따라 필요한 메모리 공간이 제곱으로 증가하기 때문에, 희소 그래프(Sparse Graph)에서는 메모리 낭비가 심할 수 있고, 간선의 수에 비례하지 않고, 정점의 수의 제곱에 비례하여 메모리 공간을 사용한다.

class Graph:
    def __init__(self, size):
        self.adjMatrix = [[0 for _ in range(size)] for _ in range(size)]
        self.size = size
    
    def add_edge(self, v1, v2):
        if v1 == v2:
            print("같은 정점은 연결할 수 없습니다.")
        self.adjMatrix[v1][v2] = 1
        self.adjMatrix[v2][v1] = 1  # 무방향 그래프의 경우

    def remove_edge(self, v1, v2):
        if self.adjMatrix[v1][v2] == 0:
            print("연결된 간선이 없습니다.")
        self.adjMatrix[v1][v2] = 0
        self.adjMatrix[v2][v1] = 0  # 무방향 그래프의 경우
    
    def __str__(self):
        return '\n'.join([' '.join([str(i) for i in row]) for row in self.adjMatrix])

# 그래프 생성 및 간선 추가 예시
graph = Graph(4)  # 4개의 정점을 가진 그래프
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 3)

print(graph)

인접 리스트(Adjacency List)는 그래프를 표현하는 자료구조 중 하나로, 각 정점에 인접한 정점들을 연결 리스트로 나열하여 그래프의 연결 관계를 표현한다. 인접 리스트는 각 정점마다 해당 정점으로부터 나가는 간선의 목록을 저장한다. 이 방법은 특히 희소 그래프(Sparse Graph), 즉 정점들 사이의 간선이 상대적으로 적은 그래프를 표현하는 데 효율적이다.

각 정점마다 하나의 리스트를 갖고, 해당 리스트에는 그 정점에 인접한 모든 정점들이 포함된다. Python에서는 리스트의 리스트로 구현하거나, 리스트에 연결 리스트 또는 집합을 담아 구현할 수 있다. 가중치가 있는 그래프의 경우, (인접 정점, 가중치) 형태의 튜플을 리스트에 저장함으로써 간선의 가중치 정보를 함께 저장할 수 있다.

방향 그래프(Directed Graph)의 경우, 각 리스트에는 해당 정점에서 출발하는 간선의 정보만 저장한다. 비방향 그래프(Undirected Graph)에서는 두 정점 사이의 연결을 양쪽 정점의 리스트에 모두 표현한다.

실제로 연결된 간선의 정보만을 저장하기 때문에, 인접 행렬에 비해 메모리 사용이 효율적이다. 특히 간선의 수가 정점의 수보다 많지 않은 희소 그래프에서 유리하고 그래프의 정점이나 간선이 자주 추가되거나 삭제되는 동적인 상황에 유연하게 대응할 수 있다.

인접 리스트에서는 특정 두 정점 사이에 간선이 존재하는지 확인하기 위해 해당 정점의 리스트를 순회해야 하므로, 최악의 경우 O(V)의 시간이 소요될 수 있다.(V는 정점의 수)

class Graph:
    def __init__(self, numVertices):
        self.numVertices = numVertices
        self.adjList = [[] for _ in range(numVertices)]
    
    def add_edge(self, src, dest):
        self.adjList[src].append(dest)
        # 비방향 그래프의 경우, 아래 코드를 추가한다.
        # self.adjList[dest].append(src)
    
    def remove_edge(self, src, dest):
        if dest in self.adjList[src]:
            self.adjList[src].remove(dest)
            # 비방향 그래프의 경우, 아래 코드를 추가한다.
            # self.adjList[dest].remove(src)
    
    def print_graph(self):
        for i in range(self.numVertices):
            print(f"Vertex {i}: {self.adjList[i]}")

# 그래프 생성 및 간선 추가 예시
graph = Graph(4)  # 4개의 정점을 가진 그래프
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 3)

graph.print_graph()

해싱(Hashing)은 데이터 관리를 위한 중요한 기법 중 하나이다. 해싱은 어떤 입력값을 고정된 길이의 값으로 변환하는 과정을 말하며, 이 때 사용되는 함수를 해시 함수라 한다. 해시 함수는 다양한 길이의 입력을 받아서 고정된 길이의 해시값을 출력한다. 이 해시값은 데이터의 저장 위치를 결정하는 데 사용된다.

해시 테이블(Hash Table)은 해싱 기법을 사용하여 데이터를 저장하는 자료구조이다. 각 데이터는 해시 함수를 통해 계산된 해시값에 따라 해시 테이블 내의 특정 위치에 저장된다. 해시 테이블은 키-값 쌍으로 데이터를 저장하며, 이때 키를 해시 함수에 입력하여 그 결과로 나온 해시값을 사용하여 값을 저장하거나 검색한다.

해시 테이블의 주요 장점은 데이터의 추가, 삭제, 검색 작업을 평균적으로 상수 시간(O(1)) 내에 수행할 수 있다는 점이다. 하지만 최악의 경우(모든 키가 동일한 위치에 해시되는 경우)에는 모든 데이터를 검색해야 하므로 성능이 크게 저하될 수 있다.

Python의 dict, Java의 HashMap 같은 프로그래밍 언어의 내장 자료구조도 내부적으로 해시 테이블을 사용한다. Python에서는 hash() 함수를 사용하여 객체의 해시값을 얻을 수 있다. 이 함수는 내장 데이터 타입(예: 정수, 문자열)에 대해 해시값을 반환한다. 하지만 사용자 정의 객체의 경우, 객체가 해시 가능하도록 __hash__() 메소드를 구현해야 한다.

또한, Python의 dict 타입은 내부적으로 해시 테이블을 사용하여 키-값 쌍을 저장한다. 이를 통해 키에 대한 빠른 접근과 검색, 추가, 삭제 작업을 지원한다.

# 정수의 해시값
hash_value = hash(100)
print(hash_value)

# 문자열의 해시값
hash_value = hash("Hello, World!")
print(hash_value)

class Student:
    def __init__(self, id, name):
        self.id = id
        self.name = name

    # 객체가 해시 가능하도록 __hash__ 메소드 구현
    def __hash__(self):
        return hash((self.id, self.name))

    # __eq__ 메소드도 구현하여 객체의 동등성 비교 가능하게 함
    def __eq__(self, other):
        return self.id == other.id and self.name == other.name

# 사용자 정의 객체 생성
student = Student(1, "John Doe")

# 사용자 정의 객체의 해시값
print(hash(student))

__hash__() 메소드는 객체의 해시값을 계산하여 반환하며, __eq__() 메소드는 두 객체의 동등성을 비교한다. Python에서는 두 객체가 동등하다고 판단되면, 이들의 해시값도 동일해야 한다.

해시 충돌(Collision)은 두 개 이상의 키가 해시 함수를 통해 동일한 해시값(즉, 동일한 위치)을 가리키는 경우 발생하는 현상이다. 해시 테이블의 효율성을 저하시키며, 이를 효과적으로 처리하는 것이 해시 테이블 설계의 핵심적인 부분이다. 충돌이 발생했을 때 체이닝과 재해싱은 이를 해결하기 위한 두 가지 주요 방법이다.

체이닝(Chaining)은 충돌이 발생했을 때 같은 해시값을 가진 요소들을 연결 리스트와 같은 자료구조를 사용하여 연결하는 방식이다. 이렇게 하면 한 버킷에 여러 요소가 저장될 수 있으며, 충돌로 인한 문제를 효율적으로 해결할 수 있다. 체이닝 방식의 장점은 해시 테이블의 크기와 무관하게 충돌을 관리할 수 있다는 점이며, 구현이 비교적 간단하다는 것도 장점이다. 다만, 체인이 길어지면 검색 성능이 저하될 수 있다.

class HashTableChaining:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]
    
    def hash_function(self, key):
        return key % self.size
    
    def insert(self, key, value):
        hash_index = self.hash_function(key)
        for i, (k, v) in enumerate(self.table[hash_index]):
            if k == key:
                self.table[hash_index][i] = (key, value)
                return
        self.table[hash_index].append((key, value))
    
    def search(self, key):
        hash_index = self.hash_function(key)
        for k, v in self.table[hash_index]:
            if k == key:
                return v
        return None
    
    def delete(self, key):
        hash_index = self.hash_function(key)
        for i, (k, v) in enumerate(self.table[hash_index]):
            if k == key:
                del self.table[hash_index][i]
                return True
        return False

재해싱(rehashing)은 해시 테이블의 크기를 조정하고, 모든 요소를 새로운 크기에 맞는 해시 함수를 사용하여 재배치하는 방법이다. 주로 해시 테이블의 사용률(로드 팩터)이 높아져 성능 저하가 예상될 때 사용된다. 재해싱은 충돌의 가능성을 줄이고, 해시 테이블의 성능을 유지하는 데 도움이 된다. 재해싱 과정은 모든 요소를 새로운 해시 테이블로 이동시켜야 하므로, 리소스와 시간이 많이 소모되는 작업이다. 그래서, 재해싱은 해시 테이블의 성능을 개선하기 위해 필요할 때만 수행되어야 한다.

class HashTableRehashing:
    def __init__(self, size=10):
        self.size = size
        self.count = 0
        self.table = [None] * size
    
    def hash_function(self, key):
        return key % self.size
    
    def rehash(self, key, step=1):
        return (key + step) % self.size
    
    def resize_and_rehash_all(self):
        old_table = self.table[:]
        self.size *= 2
        self.table = [None] * self.size
        self.count = 0
        for item in old_table:
            if item:
                key, value = item
                self.insert(key, value)
    
    def insert(self, key, value):
        if self.count / self.size >= 0.7:  # Load factor threshold
            self.resize_and_rehash_all()
        
        hash_index = self.hash_function(key)
        step = 1
        while self.table[hash_index] is not None:
            if self.table[hash_index][0] == key:
                self.table[hash_index] = (key, value)
                return
            hash_index = self.rehash(hash_index, step)
            step += 1
        
        self.table[hash_index] = (key, value)
        self.count += 1
    
    def search(self, key):
        hash_index = self.hash_function(key)
        step = 1
        while self.table[hash_index] is not None:
            if self.table[hash_index][0] == key:
                return self.table[hash_index][1]
            hash_index = self.rehash(hash_index, step)
            step += 1
        return None
    
    def delete(self, key):
        hash_index = self.hash_function(key)
        step = 1
        while self.table[hash_index] is not None:
            if self.table[hash_index][0] == key:
                self.table[hash_index] = None
                self.count -= 1
                return True
            hash_index = self.rehash(hash_index, step)
            step += 1
        return False

위 코드에선 해시 테이블이 일정 수준으로 채워지면(load factor >= 0.7), 해시 테이블의 크기를 늘리고 모든 요소를 새로운 크기에 맞게 재해싱하여 충돌 가능성을 줄인다.

/bin/ls -l foo bar 와 같은 명령이 주어졌을 때, 인자들을 어떻게 다뤄야 하는지 생각해보자

1. 명령을 단어들로 쪼갠다. /bin/ls, l, foo, bar 이렇게
2. 이 단어들을 스택의 맨 처음 부분에 놓는다. 순서는 상관 없다. 왜냐면 포인터에 의해 참조될 예정이기 때문이다.
3. 각 문자열의 주소 + 경계조건을 위한 널포인터를 스택에 오른쪽→왼쪽 순서로 푸시한다. **이들은 argv의 원소가 된다. 널포인터 경계는 argv[argc] 가 널포인터라는 사실을 보장해준다. C언어 표준의 요구사항에 맞춰서 말이다. 그리고 이 순서는 argv[0]이 가장 낮은 가상 주소를 가진다는 사실을 보장해준다. 또한 word 크기에 정렬된 접근이 정렬되지 않은 접근보다 빠르므로, 최고의 성능을 위해서는 스택에 첫 푸시가 발생하기 전에 스택포인터를 8의 배수로 반올림하여야 한다.
4. %rsi 가 argv 주소(argv[0]의 주소)를 가리키게 하고, %rdi 를 argc 로 설정한다.
5. 마지막으로 가짜 “리턴 어드레스”를 푸시한다 : entry 함수는 절대 리턴되지 않겠지만, 해당 스택 프레임은 다른 스택 프레임들과 같은 구조를 가져야 한다. 

Address Name Data Type

RDI: 4 | RSI: 0x4747ffc0

위 표는 스택과 관련 레지스터들이 유저 프로그램이 시작되기 직전에 어떤 상태인지를 보여준다. 스택은 아래로 자란다는 것을 잊지 말자.

 *      4 kB +---------------------------------+
 *           |          kernel stack           |
 *           |                |                |
 *           |                |                |
 *           |                V                |
 *           |         grows downward          |
 *           |                                 |
 *           |                                 |
 *           |                                 |
 *           |                                 |
 *           |                                 |
 *           |                                 |
 *           |                                 |
 *           |                                 |
 *           +---------------------------------+
 *           |              magic              |
 *           |            intr_frame           |
 *           |                :                |
 *           |                :                |
 *           |               name              |
 *           |              status             |
 *      0 kB +---------------------------------+

저 위의 표의 예시에서, 스택 포인터는 위에 보이는 것처럼 0x4747ffb8로 초기화될 것이고, 코드 include/threads/vaddr.h에 정의된 USER_STACK 값에서부터 스택을 시작시켜야 한다.

현재, process_exec() 함수는 새로운 프로세스들에 인자를 전달하는 것을 지원하지 않는다. process_exec() 함수를 확장 구현해서, 지금처럼 단순히 프로그램 파일 이름만을 인자로 받아오게 하는 대신 공백을 기준으로 여러 단어로 나누어지게 만들어야 한다.

첫 번째 단어는 프로그램 이름이고, 두 번째 단어는 첫 번째 인자이며, 그런 식으로 계속 이어지게 만들면 된다. 따라서, 함수 process_exec("grep foo bar") 는 두 개의 인자 foo와 bar을 받아서 grep 프로그램을 실행시켜야 한다.

int
process_exec (void *f_name) {
	char *file_name = f_name;
	bool success;

	/* We cannot use the intr_frame in the thread structure.
	 * This is because when current thread rescheduled,
	 * it stores the execution information to the member. */
	struct intr_frame _if;
	_if.ds = _if.es = _if.ss = SEL_UDSEG;
	_if.cs = SEL_UCSEG;
	_if.eflags = FLAG_IF | FLAG_MBS;

	/* We first kill the current context */
	process_cleanup ();
	int argc = 0;
    char *argv[64];		//parssing한 인자를 담을 배열
    char *token, *save_ptr;
    
	for (token = strtok_r(file_name, " ", &save_ptr); token != NULL; token = strtok_r(NULL, " ", &save_ptr))
    {   
		argv[argc++] = token;
	}
	/* And then load the binary */
	success = load (file_name, &_if);

	argument_stack(argv, argc, &_if);
	
	/* If load failed, quit. */
	palloc_free_page (file_name);
	if (!success)
		return -1;

	/* Start switched process. */
	do_iret (&_if);
	NOT_REACHED ();
}

argument_stack 함수는 프로세스의 스택에 실행 인자를 준비하는 역할을 한다. 인자들을 스택에 복사하고, 64비트 시스템에서 요구하는 8바이트 정렬을 맞추며, 각 인자의 주소를 스택에 추가한다. 이 과정을 통해 프로그램 실행 시 필요한 인자들을 스택에 올바르게 준비한다.

void argument_stack(char **argv, int argc, struct intr_frame *if_)
{
	char *arg_address[128];

	for(int i = argc - 1; i >= 0; i--)
	{
		int arg_i_len = strlen(argv[i]) +1;
		if_->rsp -= arg_i_len;
		memcpy(if_->rsp, argv[i], arg_i_len);
		arg_address[i] = (char *)if_->rsp;
	}

	if(if_->rsp % 8 != 0)
	{	
		int padding = if_->rsp % 8;
		if_->rsp -= padding;
		memset(if_->rsp, 0, padding);
	}

	if_->rsp -= 8; 	
	memset(if_->rsp, 0, 8);

	for(int i = argc-1; i >= 0; i--)
	{
		if_->rsp -= 8;
		memcpy(if_->rsp, &arg_address[i], 8);
	}

	if_->rsp -= 8;
	memset(if_->rsp, 0, 8);

	if_->R.rdi = argc;
	if_->R.rsi = if_->rsp + 8;
}

커맨드라인에서, 여러개의 공백은 하나의 공백과 같게 처리해야 한다. 그러므로 process_exec("grep    foo   bar")는 저 위의 표(원본) 예시와 동일하게 동작해야 한다.

또한, 납득할만한 수준에서 커맨드라인 인자들의 길이 제한을 강요할 수 있다. 예를 들면, 인자들이 한 페이지 크기(4kB) 안에 들어가게끔 제한하는 것 이다. (그리고 직접적인 관계는 없지만, pintos 유틸리티가 커널에 전달할 수 있는 커맨드라인 인자 크기는 128바이트로 제한되어 있다.)

<stdio.h>에 선언된 비표준 함수인 hex_dump()는 인자 전달 코드를 디버깅 하는데에 유용할 것이다. argument passing을 잘 했는지 make tests/userprog/args-none.result로 체크를 하면 안된다. write가 구현되어 있지 않기 때문인데, 이 때문에, 파싱이 잘 됐는지 확인하기 위해서는 hex_dump를 써야한다.

int write (int fd, const void *buffer, unsigned length)
{
	int byte = 0;
	if(fd == 1)
	{
		putbuf(buffer, length);
		byte = length;
	}
	return byte;
}

아니면 syscall.c 쪽에서 write를 임의로 구현해도 된다.

https://github.com/yunsejin/PintOS_RE/tree/project2

반복문(Iteration)은 프로그램 내에서 특정 코드 블록을 조건이 만족하는 동안 반복적으로 실행하기 위한 프로그래밍 구조다. 반복문은 코드의 재사용을 통해 작업을 간소화하고, 프로그램의 효율성을 높이는 데 중요한 역할을 한다. 주로 데이터의 집합을 처리하거나, 특정 조건을 만족할 때까지 반복 작업을 수행할 때 사용된다.

반복문은 조건이 항상 참이 되어 반복문이 종료되지 않는 상황. 프로그램의 의도하지 않은 동작이나 성능 문제를 일으킬 수 있다. 그리고 break를 사용하여 반복을 즉시 종료하거나, continue를 사용하여 현재 반복을 건너뛰고 다음 반복으로 넘어갈 수 있다.

for 반복문은 정해진 범위나 순서가 있는 데이터 집합을 순회할 때 사용된다. 반복의 시작과 끝이 명확할 때 주로 사용한다. 리스트의 각 요소에 대해 반복하거나, 정해진 횟수만큼 반복 작업을 수행한다.

while 반복문은 조건이 참(True)인 동안 코드 블록을 반복 실행한다. 반복 횟수가 불명확하거나, 특정 조건에 따라 반복을 종료해야 할 때 유용하다. 사용자로부터 입력을 받아 처리하는 동안 계속 실행하거나, 특정 상태가 변경될 때까지 반복한다. while 반복문 내에서는 조건이 결국 거짓이 될 수 있도록 조건에 영향을 미치는 변수를 적절히 변경해야 한다.

재귀(Recursion)는 함수가 자기 자신을 호출하는 방식을 말한다. 재귀를 사용하면 복잡한 문제를 간단한 부분 문제로 나누어 해결할 수 있으며, 특히 반복적인 계산을 간결하게 표현할 수 있다. 재귀는 컴퓨터 과학에서 매우 중요한 개념으로, 다양한 알고리즘과 데이터 구조(예: 정렬 알고리즘, 트리와 그래프의 탐색)에서 널리 사용된다.

기저 조건(Base Case)은 재귀 호출을 중단하고, 함수가 자기 자신을 더 이상 호출하지 않도록 하는 조건. 이는 재귀의 종료 조건이다. 기저 조건을 제대로 설정하지 않으면 무한 재귀 호출로 이어져 스택 오버플로우(Stack Overflow)가 발생할 수 있다.

재귀는 문제를 더 작은 단위로 나누어 접근하기 때문에, 분할 정복(Divide and Conquer) 알고리즘을 구현할 때 자연스럽게 적용된다. 꼬리 재귀 최적화(Tail Recursion Optimization)와 같은 기법을 사용하여 재귀 함수의 성능을 개선할 수 있다.

꼬리 재귀 최적화(Tail Recursion Optimization, TRO)는 재귀 호출을 효율적으로 처리하는 컴파일러 또는 인터프리터의 기능이다. 이 최적화는 재귀 함수의 마지막 동작이 함수 자신의 호출일 때, 즉 재귀 호출이 꼬리 위치(tail position)에 있을 때 적용할 수 있다. 꼬리 재귀 함수는 현재의 함수 프레임을 재사용하여 새로운 함수 호출을 수행함으로써, 호출 스택의 크기를 증가시키지 않고 재귀 호출을 실행한다. 이로 인해 메모리 사용량이 감소하고, 성능이 향상될 수 있다.

# 꼬리 재귀를 사용하지 않는 팩토리얼 함수
def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n - 1)

# 꼬리 재귀를 사용하는 팩토리얼 함수
def factorial_tail_recursive(n, accumulator=1):
    if n == 1:
        return accumulator
    else:
        return factorial_tail_recursive(n - 1, n * accumulator)

위 예시에서 factorial_tail_recursive 함수는 꼬리 재귀를 사용한다. 계산 결과를 누적하는 accumulator 인자를 추가하여, 마지막 호출에서 바로 결과를 반환하도록 설계되었다. 이러한 방식으로 함수가 자기 자신을 호출할 때마다 새로운 스택 프레임을 생성하지 않고 기존의 스택 프레임을 재사용할 수 있어, 메모리 사용량이 줄어든다.

깊은 복사(deep copy)는 객체와 그 객체가 포함하는 모든 자식 객체들까지 완전히 새로운 복사본을 생성하는 방식이다. 이는 원본 객체와 복사본 객체 사이에 서로 영향을 주지 않으려 할 때 사용한다. 반면, 얕은 복사(shallow copy)는 객체의 최상위 레벨만 복사하여 새 객체를 생성하고, 내부의 객체들은 원본 객체와 동일한 참조를 공유한다. 따라서 내부 객체가 변경되면 얕은 복사본도 영향을 받는다.

깊은 복사는 복잡한 객체 구조를 완전히 독립적으로 복제할 때 사용한다. 예를 들어, 객체 내의 리스트나 딕셔너리 같은 다른 객체를 포함하는 경우가 해당한다.

얕은 복사는 객체 구조가 간단하거나, 내부 객체들을 공유해도 문제가 없을 때 유용하다.

import copy

# 깊은 복사 예시
obj = [1, [2, 3], 4]
deep_copied_obj = copy.deepcopy(obj)
deep_copied_obj[1][0] = '변경'
# 원본 obj는 변경되지 않음
print(obj)

# 얕은 복사 예시
shallow_copied_obj = copy.copy(obj)
shallow_copied_obj[1][0] = '변경'
# 원본 obj의 내부 리스트도 변경됨
print(obj)

#출력 :
#[1, [2, 3], 4]
#[1, ['변경', 3], 4]

위 코드에서 deepcopy() 함수는 obj 객체의 깊은 복사본을 생성하여 deep_copied_obj에 할당한다. 내부 리스트를 변경해도 원본 obj는 영향을 받지 않는다. 반면, copy() 함수로 생성한 얕은 복사본 shallow_copied_obj에서 내부 리스트를 변경하면, 원본 obj의 해당 리스트도 함께 변경된다.

Array(배열)은 컴퓨터 과학에서 기본적인 자료 구조 중 하나로, 동일한 자료형의 요소들을 순서대로 나열한 것이다. 배열은 연속적인 메모리 위치에 데이터 요소들을 저장하여, 인덱스를 통해 각 요소에 빠르게 접근할 수 있는 장점을 가진다.

대부분의 프로그래밍 언어에서 배열을 생성할 때 그 크기가 고정되며, 나중에 크기를 변경할 수 없다. 모든 배열 요소는 같은 자료형이어야 한다. 이로 인해 메모리 관리가 용이하고, 요소 접근 시간이 단축된다. 배열의 요소는 0부터 시작하는 인덱스를 사용하여 접근할 수 있다. 인덱스를 통한 접근은 O(1)의 시간 복잡도를 가진다.

인덱스를 사용하여 배열의 어떤 위치에도 즉시 접근할 수 있고 연속적인 메모리 할당 덕분에 메모리 사용이 효율적이다.

배열을 생성할 때 크기를 정해야 하며, 크기를 동적으로 변경하는 것이 어렵다. 그리고  배열 중간에 요소를 삽입하거나 삭제할 경우, 나머지 요소들을 이동해야 하므로 비효율적이다.

간단한 리스트 데이터를 다룰 때 유용하며, 크기가 고정되어 있고, 자주 변경되지 않는 데이터 집합에 적합하다. 수학적 계산이나 고정된 데이터 집합을 다루는 알고리즘에서 주로 사용된다.

# 배열(리스트) 생성
numbers = [1, 2, 3, 4, 5]

# 배열 요소에 접근
print(numbers[0])  # 첫 번째 요소 출력, 결과: 1

# 배열 요소 수정
numbers[2] = 10  # 세 번째 요소를 10으로 변경
print(numbers)  # 결과: [1, 2, 10, 4, 5]

# 배열에 요소 추가
numbers.append(6)  # 배열의 끝에 6 추가
print(numbers)  # 결과: [1, 2, 10, 4, 5, 6]

# 배열의 특정 위치에 요소 추가
numbers.insert(1, 20)  # 두 번째 위치에 20 추가
print(numbers)  # 결과: [1, 20, 2, 10, 4, 5, 6]

# 배열의 요소 삭제
del numbers[1]  # 두 번째 요소 삭제
print(numbers)  # 결과: [1, 2, 10, 4, 5, 6]

# 배열의 길이 확인
print(len(numbers))  # 결과: 6

# 배열을 순회하며 요소 출력
for number in numbers:
    print(number)

Linked List(연결 리스트)는 선형 자료 구조의 일종으로, 데이터 요소들이 노드 형태로 저장되며 각 노드는 다음 노드를 가리키는 포인터(또는 참조)를 포함한다. 연결 리스트는 배열과 비교했을 때, 동적으로 메모리를 할당하며 요소의 추가와 삭제가 유연하게 이루어진다는 특징을 가진다.

노드(Node)는 데이터와 다음 노드를 가리키는 포인터로 구성된다. 마지막 노드는 다음 노드가 없음을 나타내기 위해 보통 null을 포인터 값으로 갖는다.

헤드(Head)는 리스트의 첫 번째 노드를 가리키는 포인터이다. 리스트의 시작점 역할을 한다.

단일 연결 리스트(Singly Linked List)는 각 노드가 다음 노드만을 가리키는 가장 단순한 형태의 연결 리스트다.

이중 연결 리스트(Doubly Linked List)는 각 노드가 이전 노드와 다음 노드 양쪽을 가리킨다. 양방향 탐색이 가능하다.

원형 연결 리스트(Circular Linked List)는 마지막 노드가 첫 번째 노드를 가리키는 형태로, 리스트의 끝과 시작이 연결된다.

배열과 달리 미리 크기를 지정할 필요가 없으며, 요소의 추가와 삭제 시 리스트의 크기가 동적으로 조절되고  필요할 때마다 메모리 공간을 할당받아 사용하기 때문에, 사용하지 않는 메모리 공간이 생기지 않는다. 포인터만 변경하면 되기 때문에, 배열에 비해 훨씬 효율적으로 데이터의 삽입과 삭제가 이루어진다.

배열처럼 인덱스를 통한 직접 접근이 불가능하며, 특정 요소에 접근하기 위해서는 헤드부터 순차적으로 탐색해야 한다. 그리고 각 노드가 데이터 외에도 포인터를 저장해야 하므로, 추가적인 메모리 공간이 필요하다.

연결 리스트는 데이터의 삽입과 삭제가 빈번하게 발생하거나, 데이터의 크기를 미리 예측하기 어려운 경우에 유용하게 사용된다. 예를 들어, 운영체제에서 프로세스 관리, 메모리 관리 등에 연결 리스트가 활용된다.

class Node:
    def __init__(self, data):
        self.data = data  # 노드가 저장할 데이터
        self.next = None  # 다음 노드를 가리키는 포인터

class LinkedList:
    def __init__(self):
        self.head = None  # 리스트의 첫 번째 노드를 가리키는 헤드

    def append(self, data):
        #리스트의 끝에 새로운 노드를 추가한다.
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def print_list(self):
        #리스트의 모든 요소를 출력한다.
        cur_node = self.head
        while cur_node:
            print(cur_node.data, end=" -> ")
            cur_node = cur_node.next
        print("None")

# 연결 리스트 사용 예시
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)

llist.print_list()
# 출력: 1 -> 2 -> 3 -> None

C로 Linked List 구현 코드