ColdLee ColdLee

2022. 05. 19 ~ 2022. 05 .26 1) Alarm Clock 2) Priority Scheduling 3) Priority Scheduling and Synchronization 4) Priority Inversion Problem 5) MLFQS(Multi-Level Feedback Queue Scheduler) 노션 링크 : https://decisive-handball-f43.notion.site/Pintos-Project-1-7c5a28c070a14c9cb13f8bfc547848ad

1. 명시적 가용 리스트 사용 이유 앞선 글에서 Implicit Allocator를 설계 했다. 블록 할당 시간이 전체 힙 블록의 수에 비례하기 때문에 Implicit 가용 리스트는 범용 할당기에 적합하지 않다. (why? : find_fit 함수를 확인하면 블록이 가용하고, 내가 갖고 있는 asize를 담을 수 있으면 할당을 할 수 있는데 이를 확인하려면 전체 힙 블록의 수를 하나씩 확인해가야하고 최악의 경우에는 전체 힙 블록을 다 탐색해야할 수 있다.) 이를 보완한 것이 명시적 가용 리스트(Explicit Free List)이다. - 가용 블록들을 명시적 자료구조로 구성 - 포인터들을 가용 블록의 본체 내에 저장하여 구현 - 가용 블록 내에 pred(predecessor)와 succ(successor..

묵시적 가용 리스트에 기초한 간단한 할당기의 구현 - Allocator(할당기) 기본 설계 // --------------------- Declaration --------------- // extern int mm_init(void); extern void *mm_malloc (size_t size); extern void mm_free (void *ptr); /* Private global variables */ static char *mem_heap; /* Points to first byte of heap */ static char *mem_brk; /* Points to last byte of heap plus 1 */ static char *mem_max_addr; /* Max legal he..

9.9 동적 메모리 할당 동적 메모리 할당기(Allocator) : 힙(heap)이라고 하는 프로세스의 가상 메모리를 관리한다. ❖ Explicit Allocator(명시적 할당기) - application이 명시적으로 할당된 블록을 반환해 줄 것을 요구 - C의 의 malloc 패키지라고 하는 Explicit Allocator 할당기를 제공 (malloc : 할당, free : 반환) ❖ Implicit Allocator(묵시적 할당기)(=Garbage Collection) - 할당된 블록이 더 이상 프로그램에 의해 사용되지 않고 블록을 언제 반환하는지를 할당기가 검출할 수 있을 것을 요구 - garbage collection : 자동으로 사용하지 않은 할당된 블록을 반환 9.9.1 malloc과 fr..

코드 리뷰 강의 - 류석영 교수님 Code Review - Google에서 제일 많이 하는 것 - Test-Driven Development -> 구현해야할 요구사항이랑 구현체를 분리하는 것 구현하기 전에 테스트부터 짜는 것 test는 실행 가능한 문서 테스트 없이는 코드 삽입 못함 Code Commit 하기 전에 테스트부터 해야함 자잘하게 많이 많이 commit을 많이 해야함. - Pair programming -> 선배 어깨너머로 배우는 것이 정말 좋다. 둘이 나란히 앉아서 지식을 전파 어떻게 하는지 배우는 것 —> 진짜 빨리 배운다. 혼자하다 보면 다른생각도하지만 같이하면 확실하게 집중할 수 있다. --------------------------------------------------------..

앞선 글에서, RED-BLACK Tree : Insertion(삽입)에 대해 살펴보았다. 다음으로 RED-BLACK Tree : Deletion(삭제)에 대해 살펴보려고 한다. 시작 전에, Youtube에 아주 좋은 강의가 있어서 추천하려고 한다. 글을 읽기 전에, 시청하면 이해가 훨씬 수월하다. 링크 : https://www.youtube.com/watch?v=6drLl777k-E - RED-BLACK Tree Deletion(삭제) 삭제를 하기 전에 RED-BLACK Tree의 특성부터 정리하면 특성 1. 노드는 RED 혹은 BLACK 중의 하나이다. 2. Root 노드는 BLACK이다. 3. 모든 Leaf Node(NIL)은 BLACK이다. 4. RED 노드의 자식 노드 양쪽은 언제나 모두 BLAC..

앞선 글에서, RED-BLACK Tree의 개념에 대해 살펴보았다. 지금 부터는 RED-BLACK Tree의 동작에 대해서 살펴보려고 한다. 시작 전에, Youtube에 아주 좋은 강의가 있어서 추천하려고 한다. 글을 읽기 전에, 시청하고 오시면 이해가 훨씬 수월하다. 링크 : https://www.youtube.com/watch?v=2MdsebfJOyM - RED-BLACK Tree Insertion(삽입) 삽입을 하기 전에 RED-BLACK Tree의 특성부터 정리하면 특성 1. 노드는 RED 혹은 BLACK 중의 하나이다. 2. Root 노드는 BLACK이다. 3. 모든 Leaf Node(NIL)은 BLACK이다. 4. RED 노드의 자식 노드 양쪽은 언제나 모두 BLACK이다.(RED 노드는 연달..

1. 균형 이진 탐색 트리 균형 이진 탐색 트리란 노드의 삽입과 삭제가 일어나는 경우에 자동으로 각 노드에서의 높이를 균형있게 유지시키는 것. 단순히 이진 탐색 트리에 값이 오름차순 혹은 내림차순으로 삽입되는 경우 한쪽으로 치우치는 트리가 나온다. 시간 복잡도 : O(logN) --> O(N)이 되면서 문제가 발생한다. 균형 이진 탐색 트리는 위와 같은 문제점을 해결하여 최악의 경우에도 시간 복잡도 O(logN)을 유지 되도록 해주는 것. 종류로는 AVL-Tree, Red-Black-Tree와 같은 트리가 있다. 2. Red-Black Tree란? 레드 블랙 트리는 균형 이진 탐색 트리의 하나로써 각 노드를 RED, BLACK 2가지 색깔로 구분지어 트리의 균형을 맞춘다. Root에서 Leaf Node까..