전체 글

Context Switching 이전 포스팅에서 SpinLock을 직접 구현해봤다. SpinLock은 결국에 무한 대기를 하는 것인데 그렇게 되면 계속 lock을 체크하는 것이 엄청 부담될 것이다. 그러니 체크 후에 만약 lock을 획득하지 못했다면 조금 그 쓰레드를 멈추거나 쉬게하는 방법에 대해 살펴보자. 이전 포스팅에서 2번째로 기술된 내용이다. Thread.Sleep(1); Thread.Sleep(0); Thread.Yield(); 크게 3가지가 있다. 각각의 의미가 좀 다르다. Sleep(1) 같은 경우는 무조건 휴식을 의미한다. 주어진 시간동안 쓰레드를 멈추는 것이다. 주어진 시간 이라고 하면 운영체제에서 스케줄링을 통해 결정하게된다. 만약 사용자가 숫자를 넣어 작동할 경우 운영체제가 그 숫자를..

Lock? 이전에 포스팅한 Interlocked는 좋은 기능이지만 아쉬운점이 정수를 증가시키거나 감소시키는 것 이외의 기능은 힘들다. 우리가 원하는 건 특정한 코드블럭이 어떤 쓰레드에서 실행되는 동안 다른 쓰레드에서는 잠시 멈추는 기능을 원하는 것이다. 그것에 대해 알아보자. 물론 Interlock도 많이 사용한다. 모든 쓰레드가 데이터를 읽기만 한다면 그것은 크게 중요하지 않다. 어차피 데이터는 변하지 않았을 거고 그 값만 가져오는건 문제가 되지 않는다. 중요한건 다른 쓰레드에서 wirte를 하거나 그 후에 read하는 것은 문제가 될 수 있다. 이러한 코드를 critical 세션이라고 한다. 해결방안으로 다음과 같은 코드가 있다. using System; using System.Threading; n..

캐시 지난 포스팅에서 얘기했던 식당이야기를 기억할 것이다. 이제 레스토랑이 성공해서 손님들이 많아졌다고 해보자. 그러자 식당 입장에서는 일 처리를 어떻게 해야할지 고민이 들 것이다. 만약 어떤 직원1이 손님으로부터 주문을 받을 때, 주문을 받자마자 바로 주문현황 테이블에 올리는 것은 효율적일까? 주문현황테이블은 동선상 멀리떨어져 있다고 해보자. 그렇다면 당연히 아니다. 직원1이 가지고 있는 수첩에 주문을 모았다가 한번에 주문현황테이블에 올리는 것이 효율적이다. 또한 장점으로 만약 2번 테이블에서 콜라를 주문해서 직원1이 수첩에 적어놓은 상태였는데, 2번 테이블에서 다시 직원을 호출해 콜라 대신 사이다를 달라고 했다면, 직원 1은 자신의 수첩에서 콜라를 지우고 사이다로 채워 넣기만 하면 된다. 그런데 여기..

멀티쓰레드의 이해 멀티쓰레드를 이해하기 위해 예시를 한번 들어보겠다. 여기서 등장인물은 식당, 로봇 직원, 영혼이 있다. 만약 한식, 일식, 레스토랑이 개업을 했다고 해보자. 그리고 한식과 일식은 직원을 1명을 고용했고 레스토랑은 2명을 고용했다. 여기서 직원은 로봇이고 아무런 소프트웨어가 없다. 영혼을 넣어줘야 일을 한다고 해보자. 만약 영혼이라는 것이 세상에 딱 하나밖에 없다고 가정해보자. 그리고 그 영혼을 한식 직원에게 투입했다고 해보자. 그러면 한식 직원만 일을 할 수 있고 나머지 두 식당 직원은 아무것도 못하게 될것이다. 이 것을 해결할 방법을 찾다가 영혼이 모든 직원한테 0.00001초씩 머물고 이동하면 되지 않을까 라는 생각을 하게된다. 즉, 한식 직원한테 아주조금 머물고 일식 직원한테 이동..

나는 클라이언트 개발자를 꿈꾸지만 서버 프로그래밍를 아예 모를 수는 없기 때문에 게임 서버에 대해 공부한 후 멀티 플레이가 가능한 rpg 게임을 제작해 볼 것이다. 그러기 위해서 게임 서버는 어떻게 동작하고 서버에 대한 기초적인 지식들을 공부한 것을 포스팅 하려고한다. 목표는 3d 온라인 rpg이다. 게임 서버 데이터베이스 웹 서버(극 일부만 다룰 수 있음.) 실제 컨텐츠 제작(2D 제작 후 3D 제작 예정) 순서로 포스팅 할 예정이다. 1. 서버란? 다른 컴퓨터에서 연결이 가능하도록 대기 상태로 상시 실행중인 프로그램이다. 우리가 식당에 가면 손님이 언제나 올 수 있도록 식당을 열고 대기중일 것이다. 그리고 손님이 오면 그 식당 메뉴나 정책에 따라 서비스를 제공하는데 서버도 이와 같다고 볼 수 있다. ..

Disjoint Set 상호 배타적 집합은 최소 스패닝 트리를 배울 때 매우 좋은 역할을 하기 때문에 미리 알아보자. 다른 이름으로는 Union-Find라고 부른다. 예를 들어, 리지니라는 게임이 인기가 있고 배그가 인기가 있으니 리비지 배틀그라운드 라는 혼종 게임을 만들자고 해보자. 혈맹전 + 서바이벌을 같이 하는 것이다. 그래서 생각해보면 1인 팀 1000명(팀 id 0~999)가 있고 동맹을 맺을 수 있다.(1번팀 + 2번팀 을 동맹하면 = 1번팀으로 합쳐진다) 우리가 만약 vector 자료구조만 알고 있다고하면 다음과 같이 코딩을 할 것이다. void LineageBattleground() { struct User { int temaId; // TODO }; // TODO : UserManager..

버블 정렬 버블 정렬은 앞에서부터 2개씩 짝을 지어 두개의 값을 비교해 순서를 바꾼다. 한 사이클이 끝나면 맨 뒤의 가장 큰 값이 배치하는 것을 보장할 수 있다. 따라서, 다음 사이클에 2번째의 값을 찾아내고 이 사이클을 계속하면 순서가 정렬이 될 것이다. 효율성은 거의 최악에 가깝다. void BubbleSort(vector& v) { const int n = (int)v.size(); for (int i = 0; i v[j + 1]) { swap(v[j], v[j + 1]); } } } } int main() { vector v{1, 5, 3, 4, 2}; BubbleSort(v); } 시..

이진 탐색 c++ 같은 경우에 map을 사용할 경우 우리는 아무런 위화감 없이 이진 탐색 트리를 사용할 수 있다. 하지만 면접이나 자료구조를 배울 때는 실제로 구현해 봐야 와닿기 때문에 구현까지 해보겠다. 이진 탐색은 무엇인가. 어떤 배열에 데이터가 정렬되어 있다고 할 때, 특정 데이터를 찾을 때 처음부터 끝까지 순회를 돌아 찾을 경우 O(N)의 시간 복잡도를 가진다. 되게 효율적이지 못하기 때문에 우리가 친구들끼리 놀 때, 업다운게임과 같이 생활의 지혜를 도입한 것이다. 데이터를 찾는 범위를 반으로 줄이고 줄이고 하기 때문에 O(logN)의 시간복잡도를 가진다. 이진 탐색을 구현해보자. #include #include #include #include #include using namespace std;..

트리 힙과 우선순위 큐가 트리 형태로 이루어져있기 때문에 어느정도 알고 있어야한다. 트리란? 계층적 구조를 갖는 데이터를 표현하기 위한 자료구조이다. 노드와 간선으로 이루어져있다. 이것만 보면 그래프와 매우 유사한 형태를 가지고 있다. 트리와 그래프의 큰 차이는 트리는 계층 구조를 가지는 것이다. 그래프는 동등한 위치의 데이터들을 간선으로 이은 것이라 할 수 있다. 제일 중요한 것은 root와 leaf이다. 간단하게 코드로 나타내보자. #include #include #include #include #include using namespace std; using NodeRef = shared_ptr; struct Node { Node() { } Node(const string& data) : data(d..

그래프 그래프란 현실 세계의 사물이나 추상적인 개념 간의 연결관계를 표현 한 것이다. 정점(vertex)는 데이터를 표현(사물, 개념 등)하고 간선( edge)는 정점들을 연결하는데 사용한다. 예시는 다음과 같다. 그래프를 사용해서 정말 많은 유용한 기술들을 구현 할 수 있기 때문에 무조건 공부해야하는 내용이다. 그래프에는 여러 종류가 존재하는데 위의 사진 뿐만아니라 edge에 가중치를 부여한 가중치 그래프도 있다. 또한 edge의 방향이 존재하는 방향그래프가 존재한다. 이는 두 사람 사이의 호감도나 일방 통행이 포함된 도로망 등에 사용된다. 그렇다면 그래프를 코드로 어떻게 표현해야 할까?? void CreateGraph_1() { struct Vertex { vector edges; // data };..