A*, JPS 길찾기 알고리즘 시뮬레이션 사이트

https://qiao.github.io/PathFinding.js/visual/
길 찾기 알고리즘 시행 과정을 보여주는 사이트다.

링크 메모..

lock-free aba problem에 대해..

예전에 게임 서버 포폴 만드는 공부에서 IOCP 구조로 만든 네트워크 스레드(n개)에서 받아들여온 패킷들을 Lock-Free Queue에 넣고, 게임 로직 스레드에서 꺼내다가 로직처리하도록 만들었었다.
I have developed my game server portfolio using IOCP structure. That server receives packets from network threads and pushes the lock-free queue. Then game logic thread pop a message from the lock-free queue and perform a suitable process.

그 때 겪었던 문제 중 하나가 ABA problem이었는데, stack을 가지고

간단하게 설명 글을 만들어보고자 한다.
One of the problems is the ABA problem. So, I explain the problem using the stack.


아 일단은 stack에 대해 알고 있다는 가정하에 설명하고 있다.

일단 MrRobot이라는 클래스를 보관하는 stack 이 있다고 가정하겠다.

스택이니까 간단하게 푸시를 먼저 해보자.

아래의 0x100, 0x200, 0x300은 MrRobot 객체가 할당된 메모리 주소를 예시로 든 것이다.

First I am explaining on the assumption that you know about the stack.

We have a stack that stores object of `MrRobot` class. The first step, push an object of 'MrRobot' class. The following 0x100, 0x200, 0x300 are examples of memory addresses assigned to MrRobot objects.

최초 스택 상태	1개 Push한 상태	2개 Push한 상태	3개 Push한 상태
			0x300(var_ =3)
		0x200(var_ = 2)	0x200
	0x100(var_ = 1)	0x100	0x100

그럼 이제 pop하는 과정을 살펴보자. 일단은 간단한 pop 코드는 아래와 같다.

물론 일부러 ABA problem 문제가 발생하는 코드와 과정을 예시로 들 것이다.

Now let's take a look at the pop process. My sample pop code is following.
Of course, I will deliberately present code that has ABA problem.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

class Stack    {        volatile MrRobot* topPtr_;        MrRobot* Pop()        {            while(1)            {                MrRobot* _retPtr = topPtr_;                                                                  if (nullptr == _retPtr)                 {                    return NULL;                                                              }                MrRobot* _nextPtr = _retPtr->next;                                             if(_InterlockedCompareExchange( topPtr_, _nextPtr, _retPtr ))                    return _retPtr;            }        }    }    class MrRobot    {    public:       int var_;    } Colored by Color Scripter

cs

위의 코드에서 _InterlockedCompare() 함수에 대해 간략히 설명하면 아래와 같다.
첫 번째 인자: 비교할 값의 메모리 주소

A description of the _InterlockedCompare() function is shown below.

first parameter



 : compare the value's memory address.


두 번째 인자: 첫 번째 인자와 세 번째 인자의 비교 결과가 같을 경우 첫 번째 인자값을 이 값으로 교체한다.

second parameter

 : If the comparison results of the first and third parameters are the same, replace the first parameter with this value.


세 번째 인자: 첫 번째 인자와 비교할 대상

third parameter

 : compare with first parameter.


아래는 해당 함수에 대한 msdn 링크다.

Interlocked.ComapreExchange method



간단한 샘플 코드는 요렇다.

Simply sample code is below to use _InterlockedCompareExchange function.

1 2 3 4 5 6 7 8

//예시 코드 int main() {     volatile long *pLong = new long(5);     // pLong이 가리키는 값이 5 -> 3으로 변경된다.     _InterlockedCompareExchange(pLong, 3, 5); } Colored by Color Scripter

cs

동시에 다른 스레드에서 push와 pop하는 과정도 살펴볼 것이다.우리가 중점적으로 살펴볼 스레드는 1번이다.

And at the same time, we will look at the push and pop process on multi-threads.

we will focus on the first thread.

4번 스레드의 빨간 글씨와 1번 스레드의 마지막 부분을 자세히 살펴보면



아래와 같은 내용을 알 수 있다.



0x200은 이미 pop되고 없는데?



게다가 0x300번지는 1번 스레드에서 pop했을 때와 이미 다른 정보다.



반납한 메모리가 금새 다시 재할당되서 들어올 수 있냐고 하는데,



전혀 가능성이 없는 일이 아니다.



시스템에서 제공하는 메모리 관련 연산자를 사용해서 할당하던,



개인적으로 만든 메모리 풀을 사용하던 가능성이 있는 일은 배제해야되니까..



정리해보면 ABA 문제는 멀티스레드 환경에서 동기화 과정에서



현재 진행 중인 스레드(위의 예시에서는 1번 스레드)에서 두 번의 읽기 사이에



다른 스레드가 실행되어 값을 변경하게 되는데, 첫 번째 스레드에서는



아무것도 변하지 않았다고 인식하게 되어 속는 문제를 말한다.

패리티비트와 해밍코드

해밍 코드의 정의는 위키를 참고 하시고..
간략하게는 통신에서 전송된 비트의 오류 검출 및 수정을 할 수 있는 용도라고 생각하면 되겠다.

https://ko.wikipedia.org/wiki/%ED%95%B4%EB%B0%8D_%EB%B6%80%ED%98%B8

원본 데이터를 기준으로 패리티 비트를 추가해서 새로운 데이터를 만들게 되는데
새로운 데이터를 만드는 과정을 가능한 자세하게 설명하려고 한다.
(처음에 텍스트만 보고 이해가 안 갔으니까..)

우선 원본 데이터 비트 수(n)에 따라 삽입할 패리티 비트의 수(p)가 정해진다.
공식은 아래와 같다.

2^p >= p + n + 1 (2^3: 2의 3승은 8이다)

원본 데이터가 1011 (4비트)라고 한다면, 필요한 패리티 비트의 수(p) = 3이 된다.

p = 2, n = 4를 대입해서 계산해보면
2^2 >= 2 + 4 + 1
4 > = 7 이기 때문에 성립하지 않는다.

p = 3, n = 4를 대입해서 계산해보면
2^3 >= 3 + 4 + 1
8 >= 8 이니까 성립한다.

그러니까 공식을 만족하는 p의 최소값은 3이다.
그럼 원본 데이터 (4비트) + 추가할 패리티 비트 (3비트) 를 결과 비트는 7비트가 된다.
비트의 인덱스를 아래처럼 1 - 7로 붙이면..

1	2	3	4	5	6	7
패리티비트1	패리티비트2	1	패리티비트3	0	1	1

이렇게 구성된다. 패리티 비트가 어느 자리에 들어갈 지는 2^p-1 을 기준으로 한다.
우리는 3개의 패리티 비트를 사용하게 되니까, 2^0, 2^1, 2^2 자리에 패리티 비트를 넣게 된다.

패리티비트1, 2, 3의 명칭을 p1, p2, p3로 정하겠다. 너무 기니까...
p1의 경우는 p1부터 시작해서 2^0(1)칸을 채우고 1칸을 건너뛰게 된다.
p2의 경우는 p2부터 시작해서 2^1(2)칸을 채우고 2칸을 건너뛰게 된다.
p3의 경우는 p3부터 시작해서 2^2(4)칸을 채우고 4칸을 건너뛰게 된다.
각 패리티 비트의 시작점은 위에서 확인했으니까.. (예:1번 칸은 p1의 칸)

	1	2	3	4	5	6	7
p1	p1 시작점
p2		p2시작점
p3				p3시작점

위와 같이 패리티 비트를 채워야되는 위치를 확인할 수 있다.
패리티 비트를 직접 채워보기 전에 이 사항을 먼저 알아야 한다.
패리티 비트는 짝수 패리티 비트와 홀수 패리티 비트가 있다. 비트의 값은 항상 0 또는 1 이니까
원본 데이터의 경우는 1011 이므로 기존 상태는 홀수다. 만약 짝수 패리티 비트를 사용한다면
1의 합이 짝수가 되도록 패리티 비트를 구성하는 것이다.

원본 데이터를 기준으로 짝수 패리티 비트가 되도록 구성해보면 아래와 같다.

	1	2	3	4	5	6	7
원본데이터	p1	p2	1	p3	0	1	1
p1	p1 = 0		1		0		1
p2		p2 = 1	1			1	1
p3				p3 = 0	0	1	1
결과비트	0	1	1	0	0	1	1

1. 각 행마다 위에서 내려온 채워넣어야하는 위치(색상으로 칠해진 곳)에 패리티 비트가 아닌 원본 데이터가 있는 경우에는 그걸 채워넣는다.

2. 그리고 우리는 짝수 패리티 비트를 하기로 했으니까, 1의 합을 보면 p1행은 현재 짝수다.
 따라서, p1 = 0이 들어가면 짝수가 유지된다.
 p2행은 현재 홀수다. 따라서 p2 = 1이 들어가면 짝수가 된다.
 p3행은 현재 짝수다. 따라서 p3 = 0이 들어가면 짝수가 유지된다.

3. 결과비트를 위에서부터 채워진 값을 그대로 내려적는다.

이렇게 구성된 결과비트를 해밍코드라고 한다.
0110011 를 전송했는데, 받는 쪽에서 0111011 로 받았다고 가정하고, 오류를 수정해봅시다.

	1	2	3	4	5	6	7
수신 데이터	0	1	1	1	0	1	1
p1	p1 = 0		1		0		1
p2		p2 = 1	1			1	1
p3				p3 = 1	0	1	1

위와 같이 수신 데이터를 기준으로 p1, p2, p3에 대해 패리티 비트를 계산해보면
우리는 분명 짝수 패리티 비트로 구성했는데, p3 행의 합은 홀수 패리티 비트인 것을 알 수 있다.

p3 = 0이 되면, 정상적으로 짝수 패리티 비트를 만족하므로 4번 칸의 수신 데이터는 1 -> 0 으로
변경되어야 한다. 그럼 전송 데이터와 일치하는 것을 알 수 있다.

디스크 구조

<keyword>
디스크 구조, cylinder

리눅스 설치를 위해 파티션을 나누다가 궁금한 것이 생겨서 찾아보고 얻게 된 것을 메모한다.

트랙	아래 그림에서 하나의 원판. 회전 축을 중심으로 이루어진 동심원
실린더	아래 그림에서 하나의 파이, 섹터가 여러개 뭉친 것. 여러 장의 디스크 팩에서 같은 지름을 갖는 트랙의 집합.
섹터	아래 그림에서 빨간색 한 칸

내가 참고한 포스팅 링크
http://webdir.tistory.com/160

Stack, Heap, Data 메모리 영역

<keyword>
메모리 영역, stack, heap, data, 프로그래밍 메모리

예전에 c언어 관련 책을 처음 볼 때 접했던 내용인데, 겸사겸사 메모
처음 접하는 입장에서는 메모리 공간의 분류(?) 정도로 생각하면 어떨까?

1. stack
함수 호출시 생성되는 지역변수와 매개변수가 저장되는 영역
함수 호출이 완료되면 사라진다.
단, 스택 영역에 할당되는 메모리의 크기는 컴파일하는 시점에 결정된다.

2. heap
동적으로 할당되는 경우에는 heap에 자리 잡는다.
예를 들어 C/C++에서는 malloc이라던가, new라던가..
stack과 가장 큰 차이는 stack은 컴파일하는 시점에 결정되고, heap은 런타임 때 결정된다.
동적 할당이라는 말과 어울린다랄까..

3. data
전역 변수와 static 변수가 할당되는 영역이다.
프로그램의 시작과 동시에 할당되고, 프로그램 종료시 메모리에서 소멸된다.