마이구미의 HelloWorld 마이구미의 HelloWorld

이번 글은 JVM(Java Virtual Machine)의 구조와 동작에 대해 다뤄본다.원본 글을 번역하였다. JVM은 자바 가상 머신으로 불리는 C언어와 가장 큰 차이점이기에 익히 들어보았으리라 생각한다. JVM이란 무엇인가?자바 프로그램을 실행시키기 위해 런타임(실행시간) 엔진의 역할을 한다.실제로 자바 코드에서 main 메소드를 호출하며, JRE(Java Run Environment)의 일부이다. 자바 프로그램은 WORA(Write Once Run Anywhere)로 표현한다."한번 쓰고 어디에서든 실행한다" 라는 의미를 가진다.아무 제약없이 어디서든 개발이 가능한 것을 강조하기 위함이다.간단한 예로 일반적인 프로그램은 os가 다르면 호환되지 않는다.하지만 자바는 JVM을 통해 호환이 가능하다. 출..

이번글은 뮤텍스와 세마포어에 대해 다뤄본다.원본 글을 번역 참고 후 글을 작성했다. 뮤텍스와 세마포어 둘 사이의 차이점은 무엇인가? 뮤텍스는 언제 사용하고 세마포어는 언제 사용할까? 뮤텍스와 세마포어의 운영체제의 용어로는 커널 자원에서의 동기화 서비스로 제공된다. (동기화 프리미티브라고도 불린다)우리는 왜 이러한 동기화 프리미티브 필요한가?오직 한가지로는 충족시켜줄 수 없는가?이러한 질문들을 대답하기 위해서는 우리는 몇가지 키워드들을 이해할 필요가 있다.원자성과 임계 구역에 대한 글을 읽어오길 바란다.(2개의 키워드뿐만 아니라 관련된 많은 키워드가 사용되니 꼭 참고바란다) 먼저 생산자-소비자 문제를 보자. 생산자-소비자 문제(producer-consumer problem)는 여러 개의 프로세스를 어떻게 ..

이번 글은 임계 구역에 대해 다뤄본다.원문을 번역한 글이다. 임계 구역이란 파일, 입출력, 공유 데이터 등 원자적으로 실행할 필요가 있는 명령문 또는 코드의 일부 영역이다. (원자적에 대한 글 참고) 병렬 프로그래밍에서 만약 하나의 스레드가 공유 데이터의 값을 변경을 시도하는 시점에 다른 스레드가 그 값을 읽기를 시도한다면 예측하지 못한 결과가 초래한다. 그렇기에 공유 데이터의 접근에 동기화를 해줘야한다.고급 언어에서는 동기화를 위한 지침들을 제공해준다. (관련 글) 이러한 임계 구역은 지정되어야할 영역에 지정되지 않을 경우 위와 같이 예측하지 못한 결과를 초래한다.이러한 문제를 임계 구역 문제라고 불린다. 해결법은 간단히 아래와 같이 간단히 나타낼 수 있다. acquireLock(); Process C..

이번 글은 java에서의 동기화 방법에 대해 다뤄본다.글에 앞서 관련 글을 읽어오길 바란다. Atomic Operation private int counter; public int getNextUniqueIndex() { return counter++; } 위 코드는 관련 글에서도 다뤘다.메모리에서 counter 변수를 읽은 후 값을 증가시키고 다시 메모리에 저장하는 작업 3가지로 분리된다.싱글 스레드에서는 문제가 되지 않지만, 멀티 스레드에서는 문제가 된다. (위 관련 글에서 자세히 볼 수 있다)문제로는 경쟁 상태와 변수의 가시성 문제가 발생한다.* 경쟁 상태(race condition) - 여러 스레드 같은 시점 변수를 읽는 상태.* 변수의 가시성(visibility) - 변수들이 사용될 수 있는 영..

이번 글은 Atomic Operation 에 대해 다뤄본다.Atomic Operation은 무엇인가?Atomic Operation의 개념은 재진입성, 임계 구역, 스레드 안전, 동기화 프리미티브 등 관련 용어를 이해하는 데 많은 도움을 준다. Atomic Operation의 정의는 단순하게 Atomicity(원자성)은 깨지지 않는 성격이기에 즉, 중단되지 않는 연산이라고 볼 수 있다.깨지지 않는 것과 중단되지 않는 것의 의미를 동일하게 생각하기 어려울 수 있다. 예를 통해 알아보자.만약 두 명의 사용자가 프린터를 출력하기 명령을 내린다면, 각 인쇄는 중단되지 않고 한번에 실행되어야한다.만약 프린터 드라이버가 두 사용자의 자료를 부분적으로 보내게 된다면, 예상하지 못한 결과를 초래하게 된다.그러므로 프린터..

이번 글은 플로이드 와샬 알고리즘에 대해 다뤄본다.동적계획법을 기반으로 구현되는 알고리즘이다.위키백과의 정의를 보자. 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 이 알고리즘은 플로이드 알고리즘이라고도 알려져 있다. 정의를 보다시피 최단 경로를 찾기에 좋은 알고리즘이다.시간복잡도는 3개의 반복문을 통해 O(n^3) 이다. 플로이드 알고리즘은 3개의 반복문이면 구현된다.코드를 보면 굉장히 짧고 간단하다. for (int k = 0; k <..

이번 글은 백준 알고리즘 문제 2146번 "다리 만들기" 를 다뤄본다.이 문제는 BFS DFS 활용 문제이다.하단에 비슷한 문제들이 나열되어 있다.DFS, BFS 관련 글.http://mygumi.tistory.com/102 위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나,위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).지도가 주어질 때, 가장 짧은 다리 하..

이번 글은 백준 알고리즘 1068번 문제 "트리" 를 다뤄본다.문제명 그대로 트리 문제이다.백준 알고리즘 1068번 트리https://www.acmicpc.net/problem/1068 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이 때, 1번을 제거한다고 하면, 다음과 같이 된다. 위 그림과 같이 1번을 제거한다면 리프노드는 2번 노드 하나밖에 남지 않는다.만약 3번을 제거한다면 2번, 4번 노드가 남아 2개의 리프노드가 남게 된다.그렇다면 0번이 제거된다면, 리프노드는 0개가 되는 것이다.즉 제거되는 노드의 자식들을 함께 제거한다. 문제는 생각보다 간단하다.결국 제거되는 노드와 연결되어있는 자식들을 제거하면 된다.다른 사람들은 쉽게 배열만으로 풀었지만, 본인은 머리가 잘 안돌아갔다. 본..