본문 바로가기

전체 글49

힙(Heap)을 통한 우선순위 큐 구현 우선순위큐 (Priority Queue) 우선순위큐는 우선순위에 따라 정렬되어 순차적으로 처리되는 자료구조이다. 우선순위큐는 Heap을 통해 구현이 가능하다. 힙(Heap) Heap은 '완전 이진 트리'로 구현된 트리구조의 자료구조이다. Max Heap인지 Min Heap인지 여부에 따라 부모와 자식은 절대적인 정렬상태를 가진다. +) 형제(sibiling)끼리의 정렬은 관계가 없다 O(log2n)의 준수한 시간복잡도를 가진다. 최대(Max) 힙을 통한 우선순위 큐 구현은 다음과 같다. #include using namespace std; #define MAX_SIZE 99999 //삽입과정은 완전 이진트리를 유지하는 형태로 순차적 삽입. // 왼쪽에서 오른쪽으로 순차적으로 삽입 // 삽입 이후에 루트노.. 2021. 11. 25.
이벤트 방식 Lock 구현 (Condition Variable, Window API) Lock을 구현하는 여러 방법 중 이번엔 Event 기반의 Lock이다. sleep과 Event를 응용한다. Event 방식은 OS에게 커널오브젝트를 넘겨 해당 Lock이 풀렸을 때 signal을 보내고 작업을 기다리는 스레드들은 waitForSingleObject함수를 통해 signal을 받아 동작한다. // GameServer.cpp : This file contains the 'main' function. Program execution begins and ends there. // #include "pch.h" #include #include #include #include #include // for event mutex m; queue q; HANDLE handle; void Producer(.. 2021. 11. 4.
CAS(Compare and Swap)와 SpinLock 구현 Compare And Swap(CAS) 멀티 스레딩에서 동기화를 수행하는 데 사용되는 원자적 명령. 메모리 위치의 내용을 주어진 값과 비교하고, 동일한 경우에만 해당 메모리 위치의 내용을 새로운 주어진 값으로 수정 SpinLock 멀티스레드 환경에서 임계 구역에 접근할 때 진입이 가능할때까지 루프를 돌면서 재시도하는 방식으로 구현된 락 SpinLock의 구현은 아래와 같다. // GameServer.cpp : This file contains the 'main' function. Program execution begins and ends there. // #include "pch.h" #include #include #include #include class SpinLock { public: void .. 2021. 11. 2.
RAII 패턴과 LockGuard 방식의 스레드 제어 RAII (Resoruce Acquisition is Initialization) 패턴은 자원의 할당과 해제를 자동화해주는 패턴입니다. DB인증, 공유자원 등 여러 방면에서 활용될 수 있으며 코드의 안전성을 보장해줍니다. 스택에 할당된 메모리가 자동으로 해제되며 소멸자가 호출된다는 점을 이용한 패턴이며, 저는 최근 C++의 멀티스레드 프로그래밍을 공부하며 접하게 되었습니다. Thread의 동기화를 제어하는 방식은 Atomic과 Lock등 여러 방법이 있습니다. 다만 Lock의 경우 lock, unlock이 set를 이루어 작동되어야합니다. lock 이후 unlock이 이루어지지 않는 경우 무한한 대기상태에 빠지게 됩니다. 멀티스레드 환경에서는 이러한 문제를 LockGuard를 이용해 unlock을 보장합.. 2021. 10. 27.

티스토리툴바