정글에서 온 개발자

배경 pintos vm에서는 page를 보조테이블에 uninit_page 로 미리 넣어놓고, 페이지를 읽을 때 lazy_load_segment로 물리주소에 할당한다. process를 시작할 때 읽어들이는 파일도 마찬가지인데, process_exec이 stack을 쌓고 do_iret()을 하면, 해당 rip로 가면서 rip가 가리키는 가상주소를 물리주소에 할당하기 시작한다. 그런데 위와 같이 잘 읽어들이다가 0을 가리키는 곳으로 빠졌다. 해당 fault가 특정 코드에서 나는 것이 아니기 때문에 fault 직전에 브레이크포인트를 잡고 디버깅할 수도 없어 이틀 정도를 헤멨다. 'addr : ' log는 page_fault_handler 진입하자마자 찍는 로그이다. 해결 기존 코드에서는 아래 두 코드가 빠져있었..

Priority Inversion 문제 우선순위 역전. 우선순위가 높은 쓰레드가 우선순위가 낮은 쓰레드를 기다리는 현상 Critical Section(이하 CS)를 접근하지 못하도록 락을 거는 경우에 발생한다. 락은 우선순위와 상관 없이, 락 홀더가 끝날 때까지 다른 쓰레드들이 락이 풀릴때까지 CS 앞에서 대기한다. L(낮은 priority) 이 lock holder고 H(높은 priority)가 락 해제를 기다리는 경우에도 우선순위 역전이라고 할 수 있다.(나의 생각) 일반적으로는 CS에 접근하지 않는 M(L과 H의 중간 priority) 이 들어오는 경우에 이 역전이 더 극명하게 나타난다. L이 time_slice 때 cpu를 반환하면, L보다 우선순위가 높은 M이 먼저 실행된 뒤에야 L이 실행되어 ..

왜 less로 정렬하면 선입 선출이 안되는지? 배경 특정 조건의 순서대로 elem을 뽑으려면 뽑기 전에 리스트를 정렬하고 front나 back중 하나에서 뽑으면 될 것 같다. 넣을 때부터 정렬을 해도 donate등 다른 요인들로 정렬이 깨질 수 있기 때문에, 어차피 뽑기 전에 정렬을 한 번 더 해야 한다. 따라서 뽑기 전에’만’ 정렬을 하는 것이 효율적이다. 리스트에는 기존에 뒷쪽(list_push_back)부터 elem을 삽입해주고 있었다. 이 때 list에서 제공하는 함수에는 “less함수”, 즉 a,b의 property를 비교했을 때 a가 더 작은 경우 true를 반환하는 함수를 넣어주라고 한다. 이를 사용하기 위해 lesser_priority()를 이용해 오름차순으로 정렬하고 pop_back()을..

list_begin VS list_front list_begin /* Returns the beginning of LIST. */ struct list_elem * list_begin (struct list *list) { ASSERT (list != NULL); return list->head.next; } list_front /* Returns the front element in LIST. Undefined behavior if LIST is empty. */ struct list_elem * list_front (struct list *list) { ASSERT (!list_empty (list)); return list->head.next; } 차이 list_begin은 초기화 여부(list_i..

배경대부분의 PintOS 자료에서 sleep_list를 매번 순회하지 않기 위해서 next_tick_to_awake(이하 ‘글로벌 틱’)라는 전역변수를 하나 더 지정하여 sleep_list의 tick 최소 값을 표시하도록 한다.[Explicit]이를 위해서는, sleep_list 전체 순회(thread_awake)를 할 때마다 ‘글로벌 틱’을 갱신한다.전체 순회를 조금이라도 줄이기 위해서는 sleep_list에 넣을 때부터 깨야 하는 tick의 오름차순으로 정렬되게 삽입하여, 순회 중 깨우지 못하는 쓰레드를 만나면 순회를 중단시킬 수 있다.이를 좀 더 생각해보면, sleep_list의 첫번째 요소는 항상 ‘글로벌 틱’이므로 get_next_tick_to_awake가 이를 활용하게 작성할 수도 있다.[Im..

문제링크접근재귀재귀라고 써있기도 하고, 구조 자체가 큰 Z 안에 작은 Z가 들어가서 재귀로 접근하기로 함색종이 자르기 등 다른 재귀와 유사함재귀 함수 인자로 범위를 나타내는 인자를 주고, 안쪽 재귀에서는 범위를 줄여가면 될 듯베이스 케이스는 범위가 좁아져서 최종 1일 때범위는 가로, 세로가 같이 줄어드므로 둘 중에 하나만 검사하면 됨수학적 계산R,C가 있는 위치를 기준으로 앞쪽의 구역의 숫자 배치는 상관이 없고 맨 오른쪽 아래 귀퉁이 숫자만 중요함각 범위별로 시작하는 숫자도 정해져 있음결국에는 재귀적으로 범위를 줄여나가는 것이 편함트라이1. 재귀, 시뮬레이션N,R,C = map(int, input().split())M = [[0]*(2**N) for _ in range(2**N)]k=0def recur(..

이런 문법 처음 보는 분 보세요*a,=map(int,input.split())Starred Expression(Star Unpacking)a=[1,2,3]b=[4,*a,5] # b=[4,1,2,3,5]단독으로는 사용될 수 없다.컨텍스트 안에서 써야 한다. (함수 호출, 리스트 생성 등)동일한 변수 내에서 여러번 쓸 수 없다.함수 인자의 언패킹def func(a,b,c): return a+b+cvalues = [1,2,3]result = func(*values)list(*map) , print(*str) 도 이렇게 인자를 언패킹해 넘겨주는 것이였다.Extended Unpacking(리스트나 튜플 , 맵 등)언패킹시 일부 원소들은 별도로 할당하고, 나머지는 다른 변수에 할당first, *rest = [1,..

“프로그래밍” 은 테이블을 이용한 방법을 뜻한다. (컴퓨터와 관련이 없다.) 부분 문제의 해를 결합해 문제를 해결한다. 일반적으로 **최적화 문제(optimization problem)**에 적용한다. 최적화 문제 해와 값을 구분하자 문제의 풀이를 “해(Solution)” 라 한다. 그 풀이가 낸 답을 “값(Value)” 라 한다. 최적해는 각 해의 값 중 최적의 값을 내는 해이다. 최적의 값은 하나이지만 그 값을 내는 해는 여러개이다. 최단 거리(값)를 크루스칼, 프림 등 여러 방법(해)으로 풀 수 있다. 즉 최적화 문제는 여러개의 해를 가진다. 분할정복과의 비교 분할 정복은 서로 겹치지 않는(disjoint) 문제를 부분 문제로 분할한다. DP는 부분문제가 서로 중복될 때(부분 문제끼리 부분문제를 공..

알고리즘을 풀다 보면 알고리즘의 유형을 정리하고 싶을 때가 많다. 이 문제를 어떤 알고리즘으로 풀면 좋을지, 내가 쓰고 싶은 알고리즘(동적 프로그래밍, 그리디)로 풀 수는 있는지, 아니면 아예 풀 수 없는 문제인지 그런 문제 분류를 좀 더 큰 그림에서 연구하는 학문을 계산 복잡도 이론이라 한다. 계산 복잡도 이론 각 문제를 해결하는 얼마나 빠른 알고리즘이 존재하는지를 기준으로 문제를 분류하고, 각 분류의 특성을 연구하는 학문이다. 여기서 말하는 복잡도는 시간 복잡도랑은 조금 다르다. 시간 복잡도는 알고리즘의 특성이다. 계산 복잡도는 해당 문제 특성이다.(문제를 풀 수 있는 빠른 알고리즘의 시간복잡도) 어려운 문제, 쉬운 문제 다항시간에 풀 수 있는 문제는 “쉽다”고 하고, 다항시간 알고리즘은 “빠르다” ..

이진 탐색 트리(BST; Binary Search Tree) 이진 트리 : 각 노드가 왼쪽, 오른쪽. 최대 두개의 자식 노드만 가질 수 있는 트리 왼쪽 가지를 따라 내려가면 더 작은 수 오른쪽 가지를 따라 내려가면 더 큰 수를 만남 이진 검색트리를 중위 순회하면 크기 순서로 정렬된 원소를 얻을 수 있다. 정렬된 배열의 특징 루트부터 왼쪽으로 쭉 내려가면 최소 값이 나온다. 루트부터 오른쪽으로 쭉 내려가면 최대값이 나온다. 루트가 배열의 중앙값은 아니다(트리가 불균형하게 생길수도 있다.) 이걸 원하면 다른 트리 써야 함 부모 노드가 항상 나보다 한 등수 높은 것도 아니다. (오른쪽 리프를 생각해보자) 정렬된 배열보다 뛰어난 점 특정 원소가 존재 하는지 빠르게 확인할 수 있다 노드의 값을 기준으로 다음 검색..