데이터와 동고동락 중인 개발자 입니다.

데드락은 두 개 이상의 프로세스가 서로 상대방이 점유하고 있는 자원을 기다리며 무한정 대기하는 상태를 말합니다. 즉, 각 프로세스가 자신이 필요로 하는 자원을 얻기 위해 다른 프로세스가 해제되기를 기다리는데, 다른 프로세스 역시 자원을 해제하지 못하고 있는 상황입니다. 이런 상황에서는 프로세스들이 계속 대기 상태에 빠지게 되어 더 이상 진행할 수 없게 됩니다.

1. 소스

using System;
using System.Threading;
using System.Threading.Tasks;

class Program
{
    private static readonly object lockA = new object();
    private static readonly object lockB = new object();

    static async Task Main(string[] args)
    {
        var task1 = Task.Run(() => TaskA());
        var task2 = Task.Run(() => TaskB());

        await Task.WhenAll(task1, task2);

        Console.WriteLine("Tasks completed");
    }

    private static void TaskA()
    {
        lock (lockA)
        {
            Console.WriteLine("TaskA acquired lockA");
            Thread.Sleep(100); // Simulate work

            lock (lockB)
            {
                Console.WriteLine("TaskA acquired lockB");
                // Simulate work
            }
        }
    }

    private static void TaskB()
    {
        lock (lockB)
        {
            Console.WriteLine("TaskB acquired lockB");
            Thread.Sleep(100); // Simulate work

            lock (lockA)
            {
                Console.WriteLine("TaskB acquired lockA");
                // Simulate work
            }
        }
    }
}

2. 결과

TaskB acquired lockB
TaskA acquired lockA

3. 분석

이 코드는 두 개의 작업(TaskA와 TaskB)이 서로 다른 순서로 두 개의 잠금(lockA와 lockB)을 얻으려고 할 때 데드락(교착 상태)이 발생할 수 있음을 보여줍니다.

TaskA는 먼저 lockA를 얻은 다음 lockB를 얻으려고 합니다. 반면에 TaskB는 먼저 lockB를 얻은 다음 lockA를 얻으려고 합니다.

이렇게 서로 다른 순서로 잠금을 시도하기 때문에, TaskA는 lockA를 잡고 lockB를 기다리는 상황에 놓이고, 동시에 TaskB는 lockB를 잡고 lockA를 기다리는 상황에 놓입니다. 이로 인해 두 작업 모두 더 이상 진행할 수 없는 교착 상태에 빠지게 됩니다.

실제로 이 코드를 실행하면, 프로그램이 데드락에 빠져 "Tasks completed" 메시지가 출력되지 않고, 무한히 대기 상태에 빠져 있는 것을 볼 수 있습니다. 이를 통해 데드락 상황이 발생했음을 확인할 수 있습니다.

데드락을 피하기 위해서는 모든 스레드가 동일한 순서로 잠금을 얻도록 코드를 작성해야 합니다. 또는, Mutex와 같은 고급 동기화 메커니즘을 사용하는 것이 좋습니다.

C# 에서 65000 숫자 중 32500이라는 숫자를 찾을 때 빠른 알고리즘을 찾기 위해 테스트를 해보았습니다.

이진 탐색이라는 점과 같은 시간 복잡도를 가지고 있는 Binary Search와 Balanced Binary Search Tree를 비교 해보겠습니다.

시간복잡도 : O(logN)

알고리즘 : 이진 탐색 알고리즘 (탐색할 값과 중간 값을 비교하고, 탐색 범위를 반으로 줄이는 방식)

조건 : 이진 탐색은 정렬된 배열에서 찾고, 균형 이진 트리는 SortedSet 자료구조를 사용했습니다.

1. 소스

using System;
using System.Collections.Generic;
using System.Diagnostics;

class Program
{
    static void Main()
    {
        int size = 65000;
        int target = 32500;

        // 1. 균형 이진 트리
        SortedSet<int> balancedBinaryTree = new SortedSet<int>();
        for (int i = 1; i <= size; i++)
        {
            balancedBinaryTree.Add(i);
        }

        Stopwatch stopwatch = new Stopwatch();

        stopwatch.Start();
        bool foundInTree = balancedBinaryTree.Contains(target);
        stopwatch.Stop();
        Console.WriteLine($"균형 이진 트리에서 찾는 시간: {stopwatch.ElapsedTicks} ticks");

        // 2. 배열에 담아놓고 바이너리서치
        int[] array = new int[size];
        for (int i = 1; i <= size; i++)
        {
            array[i - 1] = i;
        }

        stopwatch.Restart();
        int index = Array.BinarySearch(array, target);
        stopwatch.Stop();
        Console.WriteLine($"배열에 담아놓고 바이너리서치에서 찾는 시간: {stopwatch.ElapsedTicks} ticks");

        // 찾은 결과 출력
        Console.WriteLine($"균형 이진 트리에서 찾음: {foundInTree}");
        Console.WriteLine($"배열에 담아놓고 바이너리서치에서 찾음: {index >= 0}");
    }
}

2. 결과

이진 탐색 (Binary search)가 빠르게 측정이 됐습니다.

균형 이진 트리에서 찾는 시간: 2967 ticks
배열에 담아놓고 바이너리 서치에서 찾는 시간: 2227 ticks
균형 이진 트리에서 찾음: True
배열에 담아놓고 바이너리 서치에서 찾음: True

3. 차이점

배열은 연속된 위치에 저장되어 있어 캐시 히트율이 높습니다. 이를 통해 더 빠른 접근이 가능했습니다. 트리는 노드가 메모리의 임의 위치에 저장될 수 있어, 포인터 참조로 인해 메모리 접근이 더 느릴 수 있습니다.
삽입과 삭제는 균형 이진 트리가 O(log n)의 시간 복잡도로 O(n)의 시간 복잡도에 비해 효율적입니다.

상황에 따라 선택 해서 사용하면 될 것 같습니다.

*캐시 히트율 : 배열이 캐시 메모리의 효율을 잘 활용