분류 전체보기
-
Pintos Project - ThreadSW사관학교 Jungle 2021. 2. 4. 03:33
Pintos Project 1주차 : Thread 2주차 : User programs 3주차 : Virtual memory 4주차 : File system Jungle OS프로젝트가 시작되고 1주일이 지났다. 한 주간 Thread scheduling에 대해 공부하고, 함수들을 수정하며, donate priority까지 구현을 직접 해보았다. 시작할 때만 하더라도, 도통 무슨 소리인지 모르겠고 막막했는데 1주일이 지난 지금 다시 정리하며 많은 것들을 이해하고 있는 나 자신을 볼 수 있었다. 그동안 컴퓨터 시스템 책을 공부하며 동시성 프로그래밍을 가능하게 해주는 thread가 번갈아가며 실행된다고 막연히 알고 있었는데, priority를 고려하고, lock과 함께 사용될때 donation 방식으로(실제 사용..
-
Python - 14425 - 문자열 집합Problem Solving 2021. 1. 25. 13:38
기존에 활동하던 블로그에서 옮겨온 포스팅 입니다. 문자열 집합 link 카카오 기출 중에 Trie자료구조를 활용해 풀어야하는 문제를 접했다. Trie라는 것에 대해 오늘 처음 들어봤기 때문에, 문제를 푸는것을 미루고 이에 대해 먼저 찾아봤다. 우리가 검색을 할 때 볼 수 있는 자동 완성 기능과 같이 문자열을 탐색하는데 특화되어있는 자료구조라고 한다. 각각의 노드들에 자식 노드를 저장시켜 놓고 단어를 탐색한다. 파이썬으로 구현할 때는 dictionary를 활용해 구현한다고 한다. 문제분석 n개의 문자를 입력받고, 다음으로 m개의 문자를 입력받는다. 이때 m개의 문자열 중에 n개의 문자열안에 포함된 문자열이 몇 개인지 알아내서 출력하는 문제이다. 입력범위가 크지 않기 때문에 단순히 배열을 사용해 풀어도 무난..
-
Thread ( + pthread)컴퓨터 구조 2021. 1. 23. 00:28
Process "메모리에 적재되어 실행중인 프로그램" 사용자의 프로그램이 OS에 의해 메모리 공간을 할당받아 실행 중인 것을 말한다. 프로세스는 프로그램에 사용되는 데이터와 메모리자원 그리고 thread로 구성된다. 하드디스크의 프로그램을 실행하면, 프로그램 실행을 위해 메모리 할당이 이루어진다. 할당된 메모리 공간에 바이너리 코드가 올라가며 프로세스가 실행된다. Thread 프로세스는 스레드라고 하는 실행 유닛으로 구성되어 있다. 모든 프로세스에서 한 개 이상의 스레드가 존재하고 스레드가 작업을 수행한다. 스레드는 서로 code, data, heap영역을 공유하고 stack영역을 별도로 사용한다. 따라서, 별도의 process를 실행시키는 것 보다 데이터 공유를 쉽게 할 수 있고 효율적이다. Pthre..
-
JUNGLE_5주차SW사관학교 Jungle 2021. 1. 20. 21:22
주차별 키워드 - B tree & B plus tree 더 고민해볼 키워드 - pointer pointer와 malloc에 대해 익숙해질 수 있었던 한 주 였다. SW사관학교 정글 WEEK04 시험 B Plus Tree [입력] 삽입 – key, data 삭제 – key [출력] → 채점 시 함수를 다 같이 만들 예정 내부 노드 – key만 출력 리프 노드 – key와 data 모두 출력 [기준] 노드에 존재할 수 있는 키의 최대 개수는 3개이다. 부모의 키 값과 같은 값은 왼쪽 서브 트리에 위치한다. 트리의 리프 노드에 존재하는 키들은 오름차순 정렬한다. 삭제하고자 하는 키는 무조건 트리 내에 존재한다. 삽입하고자 하는 키는 무조건 트리 내에 존재하지 않는다. Top-Down 방식(Introductio..
-
pointer & memory segment컴퓨터 구조 2021. 1. 18. 01:39
Pointer (feat. char) char* a = "hello";로 a가 "hello"의 시작점을 가리키게 하고, *a = 'H'를 통해 "hello"를 "Hello"로 바꾸려는 시도를 해보았다. 하지만, 컴파일 결과 우리가 원하던 "Hello"가 제대로 반환되지 않고, 오류가 발생했다. Code #include #include int main() { char* a = "hello"; *a = 'H'; printf("%c", *a); } 위의 코드에서 hello가 변경이 되지 않은 채 프로그램이 종료되는 것이 아니라 왜 오류가 발생하는지가 의문이었다. 여기저기 찾아보던 중 microchip-'How do i copy char b[] to the content of char* a variable?'c..
-
B-Tree - 삭제컴퓨터 구조 2021. 1. 18. 01:38
B-Tree - 삭제 B Tree 삽입에서 가득 찬 노드들을 미리 분할했던 것 처럼, 삭제시에도 최소 키의 개수를 가지는 노드들이 키를 더 많이 가질 수 있도록 미리 처리한다. k를 찾아 재귀적으로 내려가는 과정에서 방문하는 경로에 존재하는 키의 개수가 (t-1)인 경우 형제 노드에서 키를 가져오거나, 형제노드와 병합하는 과정을 거친다. 삭제 과정에서 발생할 수 있는 모든 경우의 수에 대해 알아보자. 1. 리프 노드 x를 방문했을 때, x 내에 k가 존재한다. 2. 리프 노드가 아닌 노드 x를 방문했을 때, x 내에 k가 존재한다. 3. 리프 노드가 아닌 노드 x를 방문했을 때, x 내에 k가 존재하지 않는다. 1. 리프 노드 x를 방문했을 때, x 내에 k가 존재한다. 리프 노드 x 내에 k가 존재한다..
-
1월 중순 되돌아보기Life 2021. 1. 15. 02:09
되돌아보기 list 더보기 10월 되돌아보기 11월 되돌아보기 12월 중순 되돌아보기 12월 말 되돌아보기 1월 중순 되돌아보기 2주가 정말 길었다. 1월 첫째 주에는 DP문제들을 공부하며, django프로젝트를 진행했다. Jump to django페이지를 참고해서 공부하며 만들었고, 현재 배포 직전이다.(급격히 바빠지는 바람에 밀뤄지는 중이다.) 1월 둘째 주 부터는 B-Tree를 구현해 보았다. 동적 할당을 해보는 것이 처음에는 조금 어색하긴 했지만, 1주일이 지난 현재는 꽤 익숙해 지고, 자유자재로 사용할 수 있게 된 것 같다. 2주 간의 목표 달성 Django code_review project 마무리( 배포는 하지 않았다.. ) python local variable과 global variabl..
-
B-Tree - 삽입컴퓨터 구조 2021. 1. 13. 21:29
이번 포스팅에서는 트리를 단순화하기 위해, 키와 관련된 부수적인 정보는 키와 같은 노드에 있다고 가정한다. Abdul Bari 교수님의 10.2 B Trees and B+ Trees. How they are useful in Databases click 위의 강의에서 설명하는 방식과 다른 방식의 삽입을 설명합니다. 해당 포스팅에서 설명하는 방식은 루트 노드에서 리프 노드까지 Top-Down으로 내려가며 재귀적으로 탐색하는 방식입니다. B-Tree - 기본 규칙 1. 모든 노드 x는 아래와 같은 속성이 있다. a. x.n은 노드 x에 현재 저장되어 있는 키의 개수다. b. x의 key들은 x.key(1) leaf; z->n = DEGREE - 1; for (int j = 0; j < DEGREE - 1; ..