공부

Thread에 대해서 오래전에 정리했던 적이 있다. 하지만 일을 하다가.. 아직도 Thread에 대해서 잘모른다는 느낌이 들어서 더 자세하게 다시한번 정리를 하고자 한다.

https://codingstudy95.tistory.com/67

스레드란 무엇인가!!?

자바에서 Thread(스레드)는 프로그램 내에서 동시에 실행되는 작업의 단위를 의미한다. 회사에서 여러 사람이 각자의 다른 일을 동시에 하는 것과 마찬가지로, 스레드는 하나의 프로그램 안에서 여러 작업을 동시에 처리할 수 있도록 해준다.

(예: 데이터 처리, 사용자 요청 처리, 파일 입출력 등)

• 단일 스레딩 : 한 사람이 모든 일을 순서대로 처리하는 것 -> 모든 작업이 순차적으로 처리되므로, 하나의 작업이 오래 걸리면 다른 작업들도 지연된다.
• 멀티스레딩 : 여러 사람이 동시에 각자 일을 분담해서 처리하는 것 -> 여러 스레드가 동시에 작업을 처리하여, 한 작업이 늦어도 다른 작업은 계속 진행될 수 있다.

그럼 자바에서는 왜 멀티스레딩이 필요할까?

식당에서 한 사람이 모든 요리를 한다면 주문이 많은 경우 오래 걸리겠지만, 여러 요리사가 동시에 각자 다른 요리를 준비하면, 음식이 빨리 준비되는것과 비슷하다.

사용자 경험 향상

한 번에 한 작업만 처리한다면, 사용자가 어떤 요청을 할 때마다 기다려야 한다. 하지만 멀티스레딩을 사용하면, 여러 작업이 동시에 처리되어 응답 속도가 빨라지고 사용자 경험이 개선된다.

자원 활용의 극대화

컴퓨터는 여러 CPU 코어를 가지고 있는데, 멀티스레딩을 통해 이 코어들을 동시에 사용할 수 있다. 즉, 컴퓨터의 능력을 최대한 활용하여 더 빠르고 효율적으로 작업할 수 있다.

자바에서 스레드를 만들어보자 자바에서는 스레드를 만드는 방법이 두 가지 있다.

1. Thread 클래스 상속하기

// MyThread.kt
class MyThread : Thread() {
    // run 메서드를 재정의하여 스레드가 실행할 작업을 정의합니다.
    override fun run() {
        // 스레드가 실행될 때, "Hello from MyThread!"를 5번 출력합니다.
        for (i in 1..5) {
            println("Hello from MyThread! - $i")
            // 잠깐 멈추는 시간 (1000밀리초 = 1초)
            Thread.sleep(1000)
        }
    }
}

fun main() {
    // MyThread 클래스의 인스턴스를 생성하고, start()를 호출하면 스레드가 실행됩니다.
    val thread = MyThread()
    thread.start()
}

• MyThread는 Thread 클래스를 상속받아 만든 새로운 스레드 클래스이다.
• run() 메서드 안에 스레드가 해야 할 일을 작성한다.
• thread.start() 를 호출하면, 새로운 스레드가 시작되어 run() 메서드의 내용이 실행된다.

2. Runnable 인터페이스 구현하기

또 다른 방법은 Runnable 인터페이스를 구현하는 것이다. 이 방법은 클래스 상속의 제약을 피할 수 있다는 장점이 있다.

// MyRunnable.kt
class MyRunnable : Runnable {
    override fun run() {
        // 스레드가 실행될 때, "Hello from MyRunnable!"를 5번 출력합니다.
        for (i in 1..5) {
            println("Hello from MyRunnable! - $i")
            Thread.sleep(1000)
        }
    }
}

fun main() {
    // Runnable 인터페이스를 구현한 MyRunnable 인스턴스를 Thread에 전달하여 실행합니다.
    val runnable = MyRunnable()
    val thread = Thread(runnable)
    thread.start()
}

• MyRunnable 은 Runnable 인터페이스를 구현하여, run() 메서드 안에 작업 내용을 정의한다.
• 이 객체를 Thread 생성자에 넘겨주고, start() 를 호출하면 스레드가 실행된다.

스레드의 생명주기와 상태

자바 스레드는 여러 상태를 가진다. 각 상태는 스레드가 어떤 작업을 하고 있는지를 나타낸다.

• New: 스레드가 생성되었지만 아직 실행되지 않은 상태
• Runnable: 실행 중이거나 실행 준비가 된 상태
• Blocked/Waiting: 다른 스레드에 의해 잠시 멈춰 있는 상태
• Timed Waiting: 일정 시간 후에 다시 실행될 상태
• Terminated: 스레드의 작업이 모두 끝난 상태

한 사람이 일어나서 출근 준비를 하는 것처럼, 스레드도 만들어진 후 실행 준비, 작업 중, 대기, 그리고 작업 종료의 과정을 거친다.

근데 문제가 발생할 수 있다. 멀티스레딩에서 여러 스레드가 동시에 같은 데이터를 수정하려 할 때 문제가 발생할 수 있다.

이를 경쟁 조건 (Race Condition) 이라고 하며, 이를 해결하기 위해 동기화(Synchronization) 를 사용한다.

예를 들어 콘서트 티켓을 예매할때 한 좌석을 동시에 두명이 예매하려고 할때 좌석을 누구에게 할당해야 할까?  이런 문제를 해결하려면, 한 사람이 작업을 끝낼 때까지 기다리도록 해야 한다.

synchronized 키워드 사용 예제

class Counter {
    var count: Int = 0

    // synchronized를 사용해 여러 스레드가 동시에 count를 수정하지 않도록 보호합니다.
    @Synchronized
    fun increment() {
        count++
    }
}

fun main() {
    val counter = Counter()
    val threads = mutableListOf<Thread>()

    // 10개의 스레드를 생성하여 동시에 increment()를 호출합니다.
    for (i in 1..10) {
        val thread = Thread {
            for (j in 1..1000) {
                counter.increment()
            }
        }
        threads.add(thread)
        thread.start()
    }

    // 모든 스레드가 끝날 때까지 대기합니다.
    threads.forEach { it.join() }

    // 10개의 스레드가 각각 1000번씩 increment했으므로, 최종 결과는 10000이어야 합니다.
    println("최종 count: ${counter.count}")  // 결과: 10000
}

• @Synchronized 어노테이션을 사용해 increment() 메서드에 동시에 접근하는 것을 막는다.
• 여러 스레드가 동시에 increment() 를 호출해도, 동기화 덕분에 안전하게 실행된다.   

내가 회사에서 일하면서 실제로 겪은 스레드 문제가 있다.

경쟁 조건과 데드락

• 경쟁조건 : 여러 스레드가 동시에 데이터를 수정할 때 예상치 못한 결과가 발생하는것
• 데드락(DeadLock) : 두 스레드가 서로 상대방이 가진 자원을 기다리면서 무한 대기에 빠지는 상황이다.

동기화 블록이나 Lock 객체를 사용해, 자원에 접근하는 순서를 잘 관리해야 한다. 

실제로 데드락에 빠지는 로직을 개발하여 정말..난리 난리가 났었던...일이...후..

스레드 풀 (Thread Pool) 

매번 새로운 스레드를 생성하는 대신, 미리 일정 개수의 스레드를 만들어 두고 재사용하는 방법. 스레드의 생성 비용을 줄이고, 시스템 자원을 효율적으로 사용할 수 있다.

import java.util.concurrent.Executors

fun main() {
    // 고정 크기의 스레드 풀 생성 (3개의 스레드)
    val executor = Executors.newFixedThreadPool(3)

    // 10개의 작업을 스레드 풀에 제출합니다.
    for (i in 1..10) {
        executor.submit {
            println("작업 $i 시작: ${Thread.currentThread().name}")
            Thread.sleep(1000)
            println("작업 $i 완료: ${Thread.currentThread().name}")
        }
    }

    // 스레드 풀 종료
    executor.shutdown()
}

• Executors.newFixedThreadPool(3)를 통해 3개의 스레드로 이루어진 풀을 생성한다.
• 여러 작업이 동시에 제출되지만, 동시에 최대 3개 작업만 실행되고 나머지는 대기한다.

사용자 관점에서 한번 생각해보자

대부분의 웹 애플리케이션에서는 사용자가 데이터를 수정하고 저장을 누르면, 스레드 풀(Thread Pool) 에서 미리 만들어진 스레드 중 하나가 해당 요청을 처리한다.

즉, 사용자가 콘텐츠를 수정하고 저장 버튼을 클릭하면

1. 웹 서버는 이미 생성되어 대기 중인 스레드 풀에서 하나의 스레드를 할당한다
2. 해당 스레드가 수정 작업 로직을 실행하고
3. 작업이 완료되면 그 스레드는 스레드 풀로 돌아가 재사용된다.

이제 스레드에 대해 확실히 알게 된 것 같다.

개발을 하다 보면 ArrayList를 쓸지, LinkedList를 쓸지 고민할 때가 많다. 특히 데이터를 추가할 때(add), 성능이나 메모리 측면에서 어떤 차이가 있는지 정확하게 이해하고 있으면, 더 좋은 성능을 만들 수 있을 것 같아서 정리해본다.

1. ArrayList 

• 내부적으로 배열(Array) 기반으로 데이터를 저장하는 컬렉션이다.
• 데이터가 추가되면서 배열 크기를 초과하면, 더 큰 배열을 새로 만들고 기존 데이터를 복사한다.

val arrayList = ArrayList<Int>()
arrayList.add(10) // 배열에 10 추가

특징 : 

• 인덱스를 통한 접근 ( get(index) ) 이 매우 빠름 → O(1)
• 중간 삽입/삭제는 느림 → O(N) (요소 이동 발생)

2. LinkedList

• 노드(Node) 들이 포인터로 연결된 구조이다.
• 각각의 노드는 데이터(data)와 다음 노드(next)를 가리키는 포인터를 가지고 있다.

val linkedList = LinkedList<Int>()
linkedList.add(10) // 노드로 10 추가

특징 : 

• 앞/뒤 삽입/삭제가 매우 빠름 → O(1)
• 인덱스를 통한 접근은 느림 O(N) (앞에서붜 순회 필요)

3. add 시 시간 복잡도 비교

ArrayList의 경우

• 맨 뒤에 추가할 때는 평균적으로 O(1) 이지만, 배열 용량이 부족하면 O(N) 리사이즈가 발생한다.
• 중간에 추가할 경우, 추가 위치 이후의 모든 요소를 한 칸씩 밀어야 하므로 O(N)이다.

LinkedList의 경우

• 맨 뒤에 추가는 항상 O(1) (tail 포인터 사용).
• 중간에 추가할 경우, 목표 인덱스까지 노드를 순차적으로 탐색해야 하므로 O(N)이다.
• 탐색 이후 삽입 자체는 포인터지만 연결하면 되기 때문에 삽입 동작은 O(1)이다.

4. 메모리 사용량 차이

ArrayList의 경우

• 요소 크기 * 배열 크기 만큼 메모리 사용.
• 공간이 부족할 것을 대비해 capacity (버퍼 공간)을 여유롭게 잡기도 한다.
• 배열이라서 캐시 친화적(cache friendly) 이다.

LinkedList의 경우

• 각 노드마다 데이터 + next 포인터 + prev 포인터 (더블 링크드 리스트 기준)를 저장한다
• 포인터 오버헤드 때문에 메모리 사용량이 훨씬 많음.
• 메모리가 연속적이지 않아 캐시 미스(cache miss)가 자주 발생한다.

정리하면, 메모리 효율은 ArrayList가 압도적으로 좋다.

5. 상황별 추천

대부분의 일반적인 경우 (조회 + 추가)는 ArrayList가 훨씬 효율적이다. LinkedList는 특정 상황(삽입/삭제가 매우 빈번한 경우) 에만 신중하게 써야 한다.

분할 정복 알고리즘의 기본 개념

분할 정복의 핵심 아이디어는 분할 정복 이름 그대로 '분할(Divide)', '정복(Conquer)', '결합(Combine)' 의 세 단계로 이루어져 있다.

• 분할 : 큰 문제를 여러 개의 작은 문제로 나눈다.
• 정복 : 나눈 작은 문제들을 각각 해결한다.
• 결합 : 해결한 결과를 합쳐서 전체 문제의 답을 만든다.

쉽게 설명하면 큰 케이크를 한 번에 먹으려 하면 힘들지만, 조각조각 나눠서 먹으면 쉬운것과 비슷하다.

분할 정복의 대표 알고리즘으로는 병합 정렬과 퀵 정렬이 있다.

1. 병합 정렬(Merge Sort)

병합 정렬은 배열을 반으로 나누고, 각각을 정렬한 뒤, 두 정렬된 배열을 합쳐서 전체 배열을 정렬하는 방법이다.

멀쩡히 있는 배열을 왜 쪼갤까?

배열을 작게 나누면, 작은 문제들은 쉽게 해결되고, 마지막에 이들을 합치면 큰 문제도 쉽게 풀린다는 개념이다.

fun mergeSort(arr: IntArray): IntArray {
    if (arr.size <= 1) return arr  // 배열 크기가 1 이하이면 이미 정렬된 상태

    val mid = arr.size / 2
    val left = mergeSort(arr.copyOfRange(0, mid))
    val right = mergeSort(arr.copyOfRange(mid, arr.size))

    return merge(left, right)
}

fun merge(left: IntArray, right: IntArray): IntArray {
    var i = 0
    var j = 0
    val merged = mutableListOf<Int>()

    while (i < left.size && j < right.size) {
        if (left[i] <= right[j]) {
            merged.add(left[i])
            i++
        } else {
            merged.add(right[j])
            j++
        }
    }
    while (i < left.size) {
        merged.add(left[i])
        i++
    }
    while (j < right.size) {
        merged.add(right[j])
        j++
    }
    return merged.toIntArray()
}

fun mainMergeSort() {
    val arr = intArrayOf(38, 27, 43, 3, 9, 82, 10)
    println("원본 배열: ${arr.joinToString(", ")}")
    val sortedArr = mergeSort(arr)
    println("정렬된 배열: ${sortedArr.joinToString(", ")}")
}

위 코드의 실행 결과를 살펴보자

원본 배열: 38, 27, 43, 3, 9, 82, 10
정렬된 배열: 3, 9, 10, 27, 38, 43, 82

원본 배열이 정렬되는 것을 볼 수 있다.

2. 퀵 정렬(Quick Sort)

퀵 정렬은 배열에서 하나의 값을 피벗(pivot)으로 선택한 후, 피벗보다 작은 값과 큰 값으로 배열을 분할하고, 이를 재귀적으로 정렬하는 방법이다.

코드로 알아보는게 이해가 더 쉬울것 같다.

fun quickSort(arr: IntArray, low: Int = 0, high: Int = arr.size - 1) {
    if (low < high) {
        val pi = partition(arr, low, high)
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)
    }
}

fun partition(arr: IntArray, low: Int, high: Int): Int {
    val pivot = arr[high]  // 1. 피벗으로 배열의 마지막 원소를 선택
    var i = low - 1        // 2. i는 피벗보다 작거나 같은 요소들이 위치할 인덱스의 마지막 위치를 추적

    // 3. low부터 high - 1까지 반복하여 피벗과 비교
    for (j in low until high) {
        if (arr[j] <= pivot) {  // 만약 현재 값이 피벗보다 작거나 같으면,
            i++                // i를 한 칸 증가시키고,
            // 4. arr[i]와 arr[j]를 교환하여, 피벗보다 작은 값들을 배열 앞쪽으로 모읍니다.
            val temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
        }
    }
    // 5. i + 1 위치와 피벗(arr[high])을 교환하여, 피벗이 정렬된 위치에 오도록 합니다.
    val temp = arr[i + 1]
    arr[i + 1] = arr[high]
    arr[high] = temp

    return i + 1  // 피벗의 최종 위치를 반환합니다.
}

fun mainQuickSort() {
    val arr = intArrayOf(10, 7, 8, 9, 1, 5)
    println("원본 배열: ${arr.joinToString(", ")}")
    quickSort(arr)
    println("정렬된 배열: ${arr.joinToString(", ")}")
}

코드를 살펴보면 분할, 정복, 결합을 모두 볼 수 있다.