ObjectFreeList

안녕하세요 대학생개발자입니다.

 

오늘은 메모리풀과 오브젝트풀, 프리리스트에 대한 얘기를 해보려고합니다.

 

우선 메모리풀과 프리리스트에 대한 기본적인 이론이 필요할텐데요.

pool을 사전에 돌려보면 그냥 수영장이죠... 즉 물을 담아놓는 곳입니다.

 

여기의 메모리풀또한 메모리의 수영장과 동일합니다.

메모리를 담아놓는 공간이 되는것입니다.

그리고 필요한 메모리를 꺼내서 쓰고 다시 갖다놓을 수 있는거죠 마치 여름엔 물을 가득채워서 물놀이를 하고 겨울에는 텅텅비워놓는것 처럼요.

 

그럼 간략하게 메모리 풀이 뭔지 감정도는 잡았습니다.

이제 메모리풀이란게 왜 필요한지 설명을 드리려고하는데... 사실 너무 당연한거여서... 이걸 적어야하나 싶습니다.

제일 일차적인 목적은 당연히 할당과 반환에 쓰이는 오버헤드를 줄이기 위함입니다. 이거 하나만 보더라도 어마어마한 이득을 볼 수 있죠. 그러므로 당연히 메모리를 한번에 땡겨서 모아놓고 내가 하나씩 쓰겠다는 생각이 나온거겠죠.

 

얕은 의미에서의 메모리풀이라고하면 메모리 관리자인 힙을 사용하면서 힙에서 메모리를 끌어와서 그 메모리를 보관하고 조금씩 나눠쓰는 개념이 될것입니다. 하지만 이 페이지의 옵션을 내가 직접 조절을 하고 싶다면? 우린 직접 VirtualAlloc같은 함수를 사용해야 될것입니다. 물론 실제로는 저렇게 하지 않습니다. 예전같은경우에는 page lock을 위해서 저런 방식을 사용하기도 했습니다만... 데이터가 page out이 되었다는 의미자체가 어마어마하게 오랜시간 쓰지 않았음을 의미하고 실제 다시 page in시킬 때 아주 잠시 느려지겠죠... 그게 뭐 어떻다는 걸까요...

큰의미 없습니다.

 

네 힙의 역할은 page단위의 commit과 그 메모리에 대한 관리작업인데 결국 우리가 page옵션설정을 희망한다면 page단위의 commit과 메모리 관리를 직접해야될겁니다. 그렇게되면 코드도 상당히 난해해 질거구요.

 

그래서 제가 하고자하는 말은 메모리풀은 이렇다는것이고 저는 메모리풀을 구현하겠다는게 아니라 오브젝트풀을 만들겠다는 의미입니다.

 

음... 일단 풀이라고 한다면 하나의 아주 큰 버퍼를 생각하실 분들이 많으실겁니다 그중에서 일부를 단편화 시켜서 그 단편화 시킨 메모리를 반환한다. 정도로 간단히 구현할 수도있습니다.

뭐... 가령 배열등을 이용해서 그냥 100개정도 할당해놓고 useFlag같은 것을 하나 두고 사용할 수도 있을겁니다.

사실 예전에 제가 만들었던 별찍기 클라이언트도 그렇고 다 이런방식을 채택하고있습니다.

 

장점은 구현이 쉽겠죠...

단점은 그외의 모든것일겁니다.

왜냐면 flag를 모두 체크해서 하나라도 조건이 걸리는거면 그거는 체크해줘야되니까요

만약 풀사이즈가 100, 200이런 작은 숫자라면 배열을 쓰세요 상관없습니다. 100바퀴 도는거? 괜찮습니다. 근데 10만개 20만개 이렇게된다면 감당이 안되겠죠?

 

그래서 생각을 해보면 단순하게 큐, 스택 이런 형태의 모습이 나오게 될텐데요...

음... 솔직히 둘다 만들 수 있습니다.

근데 큐의경우에는 먼저 들어온게 먼저나가는거죠. 그니까 방금들어왔던게 마지막 인덱스가 되는겁니다.(인덱스가 있다고가정하면)

스택의 경우에는 먼저들어온게 제일먼저 나가게 되겠죠? 그니까 방금들어온게 첫번째 인덱스가 될겁니다.

 

그럼 이중 어떤경우가 더 좋을까요...

저는 이 해답을 스스로 찾아보려고했는데요...

일단 배운 내용에 따르면 마지막에 썻던것을 또 쓰는게 캐시히트율이 높을겁니다.

그럼 이 내용을 바탕으로 본다면 스택이 더나은 선택이 될것 같습니다.

 

음... 하지만 스택도 장점만 있는건 아닙니다. 방금 사용한걸 또 사용하는 케이스기 때문에 동기화 문제가 자주 발생할겁니다.

반대로 큐의 경우에는 방금 넣은게 마지막으로 들어가기 때문에 동기화의 문제가 스택보다 희박한 확률로 뜰겁니다.

 

이렇게 놓고보니 큐가 더 안정감이 들 수도있습니다.

하지만. 우리는 서버개발자입니다. 아주 희박한확률? 사람이 동시에 몇만명이 들어오는 서버입니다. 어찌될지 모릅니다.

심지어 오브젝트풀이 언젠가 꽉차게되고 반환되고 가득차고를 반복하다보면 1개가 남을텐데 그 1개를 계속 꺼냈다 넣었다 하는 경우에는 큐나 스택이나 똑같을겁니다.(물론 이렇게 구현하지 않았습니다)

어찌되었든 간에 큐든 스택이든 둘다 동기화 문제를 안고 가야되는것이라면 조금더 성능이 좋을것으로 예상되는 스택방식이 더 좋지 않을까하는 생각에 오브젝트풀을 스택으로 생각했습니다.

 

하지만 서버의 경우에는 오브젝트 풀로만 처리할 수는 없습니다.

만약 서버의 평균이 1만개의 오브젝트 풀 사이즈가 요구된다고했을때 만약 새로운 이벤트를 하게되어서 12000개가 필요해지면요? 풀이라면서요... 리사이징을하고 모든 내용을 다 카피할건가요? 정말 비효율적이겠죠 그런다고 12000개가 필요하니 넉넉하게 15000개를 해놓자고한다면요... 평균 10000개인데 5000개는 놀게되잖아요... 이것도 너무 아쉽습니다.

사실 어떻게해도 아쉬운건 벗어날 수가 없는것같습니다 오브젝트풀은

 

음... 그럼 두번째로 프리리스트에 대한 얘기를 해보겠습니다. 둘을 통합하는 과정은 나중에 정리하겠습니다.

프리리스트는 메모리를 요구할때는 새로할당입니다. 해제하고 싶을때는 반환하지 않습니다. 그리고 이미 할당된 것은 이제 오브젝트풀 처럼 되는겁니다.

 

제 케이스에서는 리스트기반의 스택으로 구현했구요. 

Object* obj = ObjectPool.Alloc();

ObjectPool.Free(obj);

와 같은 형태로 할당을 받고 반환을 할 예정입니다.

그럼 노드를 만들어야겠죠.

그럼 그이전에 노드에 뭐가 들어가야할지부터 알아보도록 하는거죠

 

우선 우리는 동적할당한 Object를 넣을것입니다.

그러면 Object*를 핸들링해주는 하나의 노드가 완성이 되어야될것입니다.

template<typename ObjectType>
struct DataNode
{
	ObjectType data;
	DataNode* pNext;
};

아주 단순하며 리스트의 노드와 흡사하게 만들었습니다.

물론 지금 이렇게 만들어놓진 않았지만... 일단 딱 필요한 두개만 놓는다면 이거정도 되겠죠.

 

우리는 저기 ObjectType에 포인터를 넣지않고 그냥 우리가 반환해줄 객체인 ObjectType을 그대로 넣어둘겁니다.

잠시 Heap의 얘기를 해보자면 예전에 제 c++ 정리글에서 말씀드렸을겁니다. 우리가 Heap에 동적할당을 요구할때 분명히 사이즈를 요구하지만 반환할때는 사이즈를 알려주지 않았습니다. 이게 가능한 이유는 힙이 앞뒤로 쓰고있고(*컴파일러,OS에따라 구현이다름) 우리에게는 우리가 사용해야될 메모리의 첫번째를 돌려주게됩니다.

ObjectType* Alloc();

Alloc함수의 원형은 이런형태이기 때문입니다. new와 동일하게 포인터를 리턴합니다.

따라서 우리도 동일하게 할겁니다.

ObjectType*를 리턴할경우에는 당연하겠지만 data의 주소를 리턴할겁니다. 타입은 ObjectType으로요. 그리고 Free를 요청할때 전달되는 포인터 또한 ObjectType일겁니다. 그럼 내부에서는 어떤짓을 하냐구요?

캐스팅입니다. ObjectType + 언더플로영역만 빼준후 -> DataNode 이렇게 형변환 시켜서 그냥 밑에 내용 까보는겁니다.

이 단순한 원리를 이용하는겁니다. 사실 이건 윈도우의 overlapped io 모델에서 비슷한 형식으로 쓰고있어요.

물론 용도는 다릅니다. overlapped io에서 사용하는 OVERLAPPED 객체는 c버전의 상속느낌이라면... 이건 Encapsulation의 느낌입니다. ObjectPool에서는 그저 DataNode만 underflow, overflow, next, flag등을 이용해서 관리할뿐 Object가 어떻게 사용되는지는 관심이 없기떄문이죠...

줄때는 일부인 ObjectType*를 주는겁니다 받을땐 우리가 ObjectType을 받아서 DataNode로 바꿔서 보는겁니다.

이런식으로 찾아가는겁니다. 그렇게되면 Alloc함수를 구현할 수 있을겁니다.

	ObjectType* Alloc()
	{
		if (pFreeNode != nullptr)
		{
			pFreeNode->useFlag = true;
			ObjectType* pObj = &pFreeNode->object;
			pFreeNode = pFreeNode->next;
			useCount++;
			if (placementNew) new(pObj) ObjectType;
			return pObj;
		}
		DataNode<ObjectType>* newNode = new DataNode<ObjectType>();
		newNode->overFlowGuard = this;
		newNode->underFlowGuard = this;
		newNode->useFlag = true;
		ObjectType* pObj = &newNode->object;
		useCount++;
		capacity++;
		return pObj;
	}

구현은 이렇게 되었습니다.

어... 근데 참 웃기지 않습니까? 동적할당을 하는 오버헤드가 부담스러워서 동적할당을 안한다더니 왜 동적할당을 하고있느냐... 라고 아니물을수 없습니다... 저도 당연히 처음에는 의아했구요...

하지만 서버의 경우에는 켜지고 초반 몇초이내의 시간 그때 접속자가 우르르 몰리게될겁니다.

10초 내외라고 하더군요... 그 10초를 아끼기 위해서 풀로 만들었다가 그뒤로는 프리리스트로 전환하셔도 됩니다. 하지만 서버오픈 초반 10초 그때 서버가 잠시 버벅거리고 늦는다고(어마어마하게 느린것도 아닐거구요) 짜증낼 플레이어는 별로 없습니다. 어차피 프리리스트 풀이 어느정도 차게되면 그뒤로는 서버는 안정화 될것이구요... 딱히 큰 이점을 얻을수가 없는겁니다 풀을 쓰는것에 대해서.

 

초반 10초의 손해를 주고 얼마나 모자랄지 얼마나 늘어날지 모르겠을 그런 메모리 낭비 혹은 부족을 방지하는 행동 이게 좀더 좋지않을까요? 솔직히 이건 주관적인 생각을 정리하는 자리라서 제 의견에 불만이신 분들도 분명히 있을겁니다.

하지만... 저번에 직렬화 버퍼때도 말씀을 드렸듯... 제가 필요하다고 느끼면 저는 글에서도 강력하게 어필하는게 느껴집니다...ㅋㅋㅋ 어차피 할당받은걸 heap에 반환하지 않기때문에 추후에 사용할때는 거의 if문에서 걸리게될거구요... 걸리게된다면 새로운 할당이 없는거니까... 뭐 문제없습니다.

 

수정

[

이부분의 또 중요한 부분을 스킵할뻔 했군요...

오브젝트 풀은 사실 new로 할당을 받아서는 안되는 케이스입니다. 이유는요

new의 역할에 있습니다. new = malloc + call constructor의 행위를 하는데요...

만약 최초 new를 통해서 할당을 했다면? 그리고 placementNew가 true라면 당연히 생성자가 2번호출될겁니다..

처음 생성자에서 5개의 풀을 미리 형성한다고 치면 그순간 1번 호출될것이고... Alloc함수를 호출하면 그순간또 호출이 될거기때문이에요

이게 뭐 상관이 있냐 생성자가 두번호출되면 어떻냐 라고하신다면... 큰일나실분들이십니다...

생성자에서 만약 동적할당을 하고있다면요? string과 같이... 그런경우에는 동적할당을 두번하는것으로 끝이아니라 추적할 수없는 메모리 누수가 남기때문에 문제가 된다는겁니다

오브젝트풀의 장점이 내가 할당한 메모리를 어느정도 추적할 수 있다는 점때문이지않습니까? 그리고 이게 곧GC의 기본인데말이죠...

 

추가로 malloc을 해서 그냥 우리가 데이터 넣어주고 사용하면 되지 라고 하신분들도 계실겁니다... 물론 데이터가 상속관계가 아니라면 좋습니다 그렇게하셔도 됩니다. 하지만 virtual function table은 100% c++의 몫입니다. 우리가 채울수 없는 부분인거죠... 그건 우리가 할수없기때문에 어쩔수없이 placement new는 필요하다는 의미입니다.

 

음... 이런걸 본다면 생성자도 거의 동일하게 되어있습니다...

	ObjectFreeList(int blockNum = 0, bool placementNew = false) : capacity(blockNum), useCount(0), placementNew(placementNew), pFreeNode(nullptr)
	{
		//처음부터 free list라면 아무것도 해줄필요없음.
		if (capacity == 0) return;
		//그게 아니라면 n번 alloc호출과 동일하게 만들어줘야됨 단 capacity만 증가되어야됨.
		DataNode<ObjectType>* temp;
		//리스트처럼 다음노드 연결
		pFreeNode = (DataNode<ObjectType>*)malloc(sizeof(DataNode<ObjectType>));
		if (pFreeNode == nullptr) CRASH();
		pFreeNode->underFlowGuard = this;
		pFreeNode->next = nullptr;
		pFreeNode->overFlowGuard = this;
		pFreeNode->useFlag = false;
		for (int i = 0; i < blockNum - 1; i++)
		{
			temp = (DataNode<ObjectType>*)malloc(sizeof(DataNode<ObjectType>));
			if (!placementNew)
			{
				new(temp) ObjectType();
			}
			if (temp == nullptr) CRASH();
			temp->next = pFreeNode;
			temp->underFlowGuard = this;
			temp->overFlowGuard = this;
			temp->useFlag = false;
			pFreeNode = temp;
			temp++;
		}
	}

네 역시 할당은 malloc으로 잡고 placementNew가 false일 경우에만 초기 생성때 생성자를 호출해주고 그외에는 생성자를 호출해주지 않습니다... 물론 placementNew의 의미가 저것만 있는것은 아닙니다... 제가 예전에 만들었던 직렬화 버퍼의 경우에는 new를 필요로 하지 않습니다. 그냥 쓰고 돌려놓을겁니다. 그러면 다시 받았을때나 혹은 돌려줄때 clear()한번 호출해주면 되기때문이죠... 

]

 

 

음... 그럼 이번에는 Free에 대한 얘기를 해보도록하죠.

Free를 할때는 어떤걸 확인해야될까요?

일단 delete의 경우를 먼저 보겠습니다. 삭제했던 메모리를 삭제하면 안될겁니다.

추가로 할당받았던 그 주소가 아니라면 또 안될겁니다.

저런경우에는 delete에서 예외가 발생하죠. 잘못된 메모리를 사용하는거니까요.

그것과 동일합니다. 우리도 똑같이 만들겁니다. 대신 우리는 조건하나를 더걸겁니다.

new와 delete의 경우에는 전역함수이기 때문에 모든 동적할당은 new를 통해서 하게됩니다.

그럼 반환의 경우에는 당연히 delete를 통해서하겠죠 이건 불변의 법칙입니다. 물론 free를 통해서 할수있지만... 지금 그거를 따지자고 하는게 아니잖아요? 결국 동적할당과 반환은 하나의 주체 즉 힙이 주체가되어서 행위를 해주는겁니다. 그리고 그 힙이라는건 프로세스당 하나씩 기본으로 있는거죠.

반면에 우리가 만들 오브젝트풀은 하나가 아닐수도있습니다. 두개일수도 세개일수도있는거죠.

그럼 어떤 객체에서 만들어진 메모리냐가 중요한겁니다. 그럼 여기서 우리는 노드를 수정해야겠죠... 어떻게 해야지 A메모리풀에서 나간 메모리가 B로 안들어가게 할수있을까...

즉 이게 내가만든 Object가 맞는가를 확인하는겁니다.

이런경우에는 여러가지 방법이있겠죠. random한 값을 하나두고 그 값을 오브젝트풀이 생성한 객체에 둔다음 써도될겁니다. 혹은 static멤버 변수를 둬서 값을 1증가시켜가면서 쓸수도있는거겠죠...

하지만 이건 모두 위험합니다. 물론 static의 경우에는 컴파일러 선에서 동기화 문제를 잡아주고 있습니다만... random의 경우에는 운나쁘게도 값이 겹칠수도 있기떄문이죠...

그래서 저는 무조건 다르게 나올수 밖에 없는값... 즉 각 객체당 무조건 하나씩 다가지고있지만 모두 다른 값을 찾다가 그냥 parent라는 주소를 넣어주기로 했습니다.

 

추가로 이 메모리가 사용중이지 않느냐 사용중이냐를 따지기위한 변수인 useFlag도 넣어주었습니다.

template<typename ObjectType>
struct DataNode
{
	ObjectPool<ObjectType>* underFlowGuard
	ObjectType data;
    ObjectPool<ObjectType>* overFlowGuard;
	DataNode* pNext;
    bool useFlag;
};

즉 이런 모양이 나오게되는거죠...

그럼 생성할때

parent = this;

useFlag = false; 하는 이유도 납득이 되실겁니다.

 

그럼 Free의 코드를 보면서 조금 정리를 해보겠습니다.

	bool Free(ObjectType* pData)
	{
		DataNode<ObjectType>* temp = (DataNode<ObjectType>*)pData;
		if (temp->parent != this) CRASH();
		if (!temp->useFlag) CRASH();
		if (useCount < 0) CRASH();
		if (pFreeNode == nullptr)
		{
			pFreeNode = temp;
			pFreeNode->useFlag = false;
			useCount--;
			return true;
		}

		temp->next = pFreeNode;
		pFreeNode = temp;
		pFreeNode->useFlag = false;
		useCount--;
		return true;
	}

뭐... 일단 캐스팅하고 셋중 하나라도 아니면 CRASH라는 메크로를 호출해버립니다....

저건 제가 자주쓰는겁니다.

#define CRASH() do{int* ptr =nullptr; *ptr =100}while(0)

이코드입니다. do while(0)의 문장은 이런데서 쓴다고 예전에 말씀드린적 있으니 넘어가겠습니다.

근데 사실 좀 희안합니다.

Free에서 temp->parent가 this가 아닌게 서버를 죽일일인가요?

아니면 useFlag가 false인게 서버가 죽을일일까요??

마지막의 경우에는 터질만합니다... 왜냐면 ObjectPool이 잘못설계되었다는 의미니까요.

 

음... 저부분에서 좀 너무 과한 처분아니냐 라고 하실수도있는데 사실 제가 프로그램을 제대로 만들었다면 부모가 다른 오브젝트풀에 들어가는 케이스가 없을겁니다... 또한 반환한 메모리를 또반환하는 그런 케이스도 없을겁니다...

저 부분은 제가 너무한게아니라 제가 만들게될 서버에서 문제가 생겼을때 문제가 생긴지점에서 바로 알수있게 하려고 만든거에요그냥... 나중에 문제가 생겨버리면 어디서 터졌는지 알수가없으니까 빨리터트려버리는겁니다.

 

음... 이렇게 해보니까 너무 심플하죠? 저거 두개만 있으면 사실 나머지는 크게 할필요없습니다 생성자나 소멸자만 만들어 주시면되니까요...

 

음... 소멸자에서는 좀 얘기할 거리가 있긴하겠습니다.

사실 메모리풀이 소멸된다 라는 의미는... 거의 높은확률로 서버의 종료일겁니다... 서버의 종료시점이라면 굳이... 내가 지울필요가 없을겁니다. 하지만 메모리풀이 수시로 소멸됬다 생성됬다한다면... 모든 메모리를 다 잡아서 처리해야겠죠... 저는 전자라고 생각하기 때문에 따로 모든 메모리를 추적해서 잡는걸 만들진 않았습니다..

 

뭐... 이정도 정리를 했다면 나름 만족입니다.

사실 언더플로와 오버플로를 체크하라는 말이 무슨말인지 잘 모르겠지만... 아마 메모리풀에서 할당한 메모리가 맞는지 확인하라는 의미같습니다... 그래서 그냥 this를 전달해서 사용하는 방식을 채택했는데... 이게 맞는지 모르겠습니다사실 허허... 검색한 코드를 보고 짜지말고 그냥 머릿속에 있는거가지고 짜야해서 일단 최대한 그렇게 했습니다.

 

째뜬... 오늘도 긴글 읽어주신 여러분들 감사드립니다.

음... 다음번에는 더 좋은 정보를 들고 돌아오도록 하겠습니다.

그럼 안녕히계세요