Deadlock

DeadLock이란 여러 프로세스(또는 스레드)가 서로가 가진 자원을 기다리며 영원히 진행하지 못하는 상태를 말한다.

DeadLock이 발생하는 4가지 조건

Deadlock이 발생하려면 아래 네 가지 조건이 동시에 모두 충족되어야 한다.

1. 상호 배제(Mutual Exclusion)

• 자원은 한 번에 한 프로세스만이 사용할 수 있어야 한다.

2. 점유와 대기(Hold and Wait)

• 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.

3. 비선점(No Preemption)

• 다른 프로세스에 할당된 자원은 사용이 끝날 대까지 강제로 빼앗을 수 없어야 한다.

4. 순환 대기 (Circular Wait)

• 자원 대기가 순환 형태로 되어 있어, 프로세스들이 서로를 기다린다.

❓ 왜 3가지만 충족하면 Deadlock이 발생하지 않을까?

1. 상호 배제 X : 자원을 여러 프로세스가 동시에 사용할 수 있으므로 대기가 필요없어진다.
2. 점유와 대기 X : 프로세스가 자원을 점유한 상태에서 다른 자원을 요청할 수 없다면, 자원을 점유한 프로세스가 대기에 들어갈 일이 없어진다.
3. 비선점 X : 다른 프로세스가 점유하고 있는 자원을 강제로 빼앗아 실행할 수 있게 된다.
4. 순환 대기 X : 순환이 발생하지 않으면 모든 프로세스가 자원을 얻기 위한 대기열에 들어갈 일이 없다.

DeadLock 예방 방법

교착 상태 발생 조건 중 하나를 제거함으로써 데드락을 해결하는 방법이다.

1. 상호 배제(Mutual Exclusion)

• 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 한다.

2. 점유와 대기(Hold and Wait)

• 프로세스가 모든 필요한 자원을 한 번에 할당받도록 해서 기다리지 않게 한다.

3. 비선점(No Preemption)

• 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게 한다.

4. 순환 대기 (Circular Wait)

• 자원에 우선순위를 부여하고 낮은 순위가 높은 순위 자원을 기다리지 못하게 한다.

❓ 왜 현대 OS는 DeadLock을 처리하지 않을까?

• 완전한 데드락 예방은 매우 어렵고, 비효율적이기 때문에, 데드락을 아예 막는 것보다 데드락이 발생하면 탐지하고, 그 때 복구를 하는 것이 더 실용적이다.
• Deadlock 탐지와 회복(복구)는 매우 복잡하고 비용이 많이 든다.
• 현대 OS는 데드락 발생 빈도가 낮고, OS가 복구를 시도하면 오히려 시스템 불안정이나 성능 저하가 크기 때문이다.

Wait Free vs Lock Free

Wait Free와 Lock Free는 둘 다 병렬 프로그래밍에서의 동기화 매커니즘으로 사용되며, 둘 다 락을 사용하지 않고 여러 스레드가 안전하게 공유 자원에 접근하는 방법을 말한다.

Lock Free

• 여러개의 쓰레드에서 동시에 호출했을 때에도 정해진 단위 시간마다 적어도 한 개의 호출이 완료되는 알고리즘을 말한다.
• 전체 스레드에서 최소한 하나의 스레드는 계속 작업을 진행한다.
  즉, 전체적인 진행은 보장되지만 개별 스레드는 보장되지 않는다.
• 다른 스레드의 방해가 있다면, 기아 상태가 발생하여 계속적으로 수행을 실패하고 loop를 도는 스레드가 발생한다.
• 구현이 상대적으로 쉽다.
• 교착 상태가 발생하지 않고, 대부분의 상황에서 성능이 좋다.

Lock-Free 예시

전체 시스템은 멈추지 않지만, 어떤 스레드는 밀릴 수 있음.

스레드 A: 빠르게 진행  
스레드 B: A보다 느려서 자꾸 충돌 -> 계속 재시도  
=> A는 계속 작업을 하고 있지만, B는 뒤에서 계속 대기  
=> 전체는 잘 돌아가지만, B는 작업을 일부 하다가 실패하고 다시 처음부터 재시도하는 상황이 계속 반복됩니다.

Wait Free

• Lock Free에 포함되는 개념으로, 모든 스레드가 제한된 시간 안에 작업을 끝낼 수 있다. (즉, 각 스레드의 진행이 보장되며, 누구도 무한히 기다리거나(blocking), retry만 하게 되지 않는다.)
• 구현이 매우 어려우며, 성능 오버헤드가 크다.
• 무한 대기가 없고, 실시간 시스템에 적합하다.

Wait-Free 예시

모든 스레드가 제한 시간 안에 완료되는 구조.

스레드 A: 1초 이내에 항상 작업 끝냄  
스레드 B: 1초 이내에 항상 작업 끝냄  
...모든 스레드 동일  
=> 어떤 스레드든 "기다림 없이" 자신의 작업을 끝냄  
---

스레드 A 작업 완료 (0.1초)
스레드 B 작업 진행 중이었는데 시간 끝 → 다음 차례
스레드 A 다시 작업 → 완료
스레드 B 지난번 멈춘 지점부터 이어서 → 완료
=> 각 스레드의 진행이 보장된다.

---

프로그램의 실행 과정

❓ 프로그램이 컴파일되어 실행되는 과정

1. 소스 코드 작성 : 개발자가 프로그래밍 언어로 소스 코드를 작성한다. (.c, .java)
2. 컴파일러 : 소스 코드를 기계어로 번역하는 단계로, 컴파일러는 소스 코드를 분석하고 최적화하여 중간 코드나 직접 실행 가능한 기계 코드를 작성하여 오브젝트 파일(.o, .class)을 생성한다.
3. 링커 : 컴파일된 파일들(여러 오브젝트 파일들)을 하나로 묶어 실행 가능한 파일(a.out, .exe)을 생성한다. 이 과정에서 외부 라이브러리나 다른 모듈과의 연결이 이루어진다.
4. 로더 : 링크된 실행 파일을 메모리에 적재하고, 프로세스로 실행을 시작한다. 로더는 필요한 라이브러리와 함께 프로세스의 주소 공간에 적재한다.
5. 실행 : CPU가 해당 명령어를 실행한다.

❓ 링커(Linker) vs 로더(Loader)

링커

링커는 컴파일된 재배치 가능 오브젝트 파일을 하나의 이진 실행 파일로 결합한다. 재배치 가능 오브젝트 파일이란, 임의의 물리 메모리 위치에 적재되도록 설계된 오브젝트 파일로 컴파일되는 소스파일을 의미한다.

• 링킹 단계에서 다른 오브젝트 파일 또는 라이브러리가 포함될 수 있다.

로더

로더는 이진 실행 파일을 메모리에 적재한다.

• 프로그램 부분에 최종 주소를 할당하고, 프로그램 코드와 데이터를 해당 주소와 일치하도록 조정한다.
• 프로그램이 실행될 때, 코드가 라이브러리 함수를 호출하고 변수에 접근할 수 있도록 한다.
• 실제 대부분의 시스템은 프로그램을 적재할 때 라이브러리를 동적으로 링크한다.

📌 자바에서의 링커와 로더

자바의 경우, 컴파일의 결과로 .class 파일이 생성된다. .class 파일은 각 클래스 단위로 독립적으로 존재하는데, 실행 시 JVM이 필요한 클래스를 동적으로 로딩하고 심볼을 연결한다. 따라서 링커가 별도로 필요하지 않다.

또한, JVM이 실행되면 클래스로더가 .class 파일을 찾아서 메모리에 동적으로 로드하기 때문에 운영체제의 정적 로더에 의존하지 않는다.

💡 정리

항목	링커 (Linker)	로더 (Loader)
시점	컴파일 직후	실행 직전
역할	여러 오브젝트 파일 + 라이브러리 → 하나의 실행파일 생성	실행파일을 메모리에 적재하여 실행
예시	main.o + math.o → a.out	a.out → 메모리 로딩 → 프로세스 시작

❓ 컴파일 언어 vs 인터프리터 언어

컴파일 언어

특징

• 소스코드 전체를 컴파일러가 한 번에 기계어로 번역해서 실행 파일을 만든 후 실행하는 방식
• 실행 파일을 만들어 배포할 수 있다. (소스코드 없이도 실행 가능)
• C, C++, Go, Swift

장점

• 실행 속도가 빠르며, 소스코드 노출 위험이 적다.

단점

• 코드 수정마다 다시 컴파일이 필요하며, 플랫폼 의존적이다.

인터프리터 언어

특징

• 소스코드를 인터프리터가 한 줄씩 읽어가며 실행하는 방식
• Python, JavaScript, PHP, Bash

장점

• 컴파일 과정 없이 한 줄씩 바로 실행되므로, 빠르게 결과를 확인하며 개발이 가능하다.
• 인터프리터만 있으면 어디서나 실행 가능하기 때문에 플랫폼에 독립적이다.
• 개발 및 테스트에 용이하다.

단점

• 실행 속도가 느리고, 소스코드의 노출 위험이 있다.

하이브리드 언어

특징

• 소스코드를 중간 언어(바이트 코드)로 컴파일하고, 가상 머신이 해석하거나 JIT 컴파일
• Java, Kotlin

❓ JIT 컴파일러에 대해 설명해주세요

JIT 컴파일러란, Just In Time의 약자로, **프로그램 실행 중에 바이트코드를 기계어로 변환하는 컴파일 방식을 의미한다.

• JVM 안에서 바이트코드는 기본적으로 Interpreter 방식으로 동작한다. 다만, 같은 메서드라도 여러 번 호출이 되면, 매번 한 줄씩 읽고 실행해야 하기 때문에 실행 속도가 느려진다.
• JIT 컴파일러는 바이트 코드 전체를 컴파일하여 기계어로 변경하고, 이후에는 더 이상 인터프리팅하지 않고 캐싱해두었다가 직접 실행하는 것이다. -> 실행 속도가 빨라진다.
• 바이트코드에서 기계어로 바꾸는 비용도 발생하기에 모든 코드를 JIT 방식으로 해석하지 않는다. 사용하다가 일정 기준을 넘어가면 JIT 방식을 사용한다.

❓ Java는 어떤식으로 컴파일 및 실행되나요?

1. 자바 프로그램 실행 -> JVM은 OS로부터 메모리를 할당받는다.
2. 자바 컴파일러(javac)이 자바 소스코드를 바이트코드로 컴파일한다. (.java -> .class)
3. 클래스 로더는 자바 클래스들을 로딩 및 링킹하여 런타임 데이터 영역에 올린다.
4. 런타임 데이터 영역에 로딩된 바이트코드들은 실행 엔진을 통해 해석 및 실행된다.
5. 이 과정에서 실행엔진에 의해 GC의 작동과 스레드 동기화가 이루어진다.

❓ 우리는 흔히 fork(), exec() 시스템 콜을 사용하여 프로세스를 적재할 수 있다고 배웠습니다. 로더의 역할은 이 시스템 콜과 상관있는 걸까요? 아니면 다른 방식으로 프로세스를 적재할 수 있는 건가요?

fork() : 프로세스를 복제
exec() : 지정한 실행 파일을 메모리에 로드하여 실행

• exec() 시스템 콜 내부에서 OS의 로더가 실행파일을 메모리에 올리는 역할을 수행한다. 프로그램의 실행 파일을 분석하고, 메모리 배치를 수행하는 실질적인 작업을 담당한다.

---

IPC (Inter-Process Communication)

IPC (Inter-Process Communication, 프로세스 간 통신)이란, 서로 독립된 프로세스 간에 데이터를 주고받는 방식이다. 운영체제는 메모리 보호 때문에 각 프로세스의 메모리를 격리시켜두기 때문에 프로세스끼리는 직접 서로의 메모리에 접근할 수 없고, 특수한 메커니즘을 통해서만 통신할 수 있다.

IPC의 종류

1. 파이프 (Pipe)

부모-자식 간 통신에 주로 사용된다. 단방향이며 익명 파이프는 동일한 프로세스 계열에서만 사용이 가능하다.

🌟 특징

• 파이프는 두 개의 프로세스를 연결하게 되고, 하나의 프로세스는 데이터를 쓰기만, 다른 하나는 데이터를 읽기만 할 수 있다.

2. FIFO (Named Pipe)

파이프를 파일 시스템에 등록한 형태로, 부모 프로세스와 무관하게 서로 전혀 다른 프로세스도 통신할 수 있다.

🌟 특징

• 읽기/쓰기가 동시에 가능하지 않으며, read-only, write-only만 가능하다.
• 통신선로가 파일로 존재하기 때문에 하나를 읽기 전용, 다른 하나를 쓰기 전용으로 열면 문제를 해결할 수 있다.

3. 메시지 큐 (Message Queue)

운영체제 커널에 메시지를 저장하고 전달한다. 큐 형태로 동기화가 가능하다.

🌟 특징

• 파이프가 데이터의 흐름이라면, 메시지 큐는 메모리 공간이다.
• 메시지 큐에 쓸 데이터에 번호를 붙임으로써 여러 개의 프로세스가 동시에 데이터를 쉽게 다룰 수 있다.
• 메시지 전달마다 운영체제가 개입하기 때문에 높은 커널 의존성을 가지게 되며, 속도가 느리다.
• 하지만, 운영체제가 개입하기 때문에 자원에 대한 동기화 문제는 발생하지 않는다.

4. 공유 메모리 (Shared Memory)

가장 빠른 통신 방법으로, 공유 메모리가 데이터 자체를 공유하도록 지원한다. 즉, 여러 프로세스가 하나의 메모리 공간(공유 메모리 세그먼트)에 직접 접근할 수 있도록 하는 방식이다.

🌟 특징

• 공유 메모리는 프로세스간 메모리 영역을 공유해서 사용할 수 있도록 허용한다.
• 프로세스가 공유 메모리 할당을 커널에 요청하면 커널은 해당 프로세스에 메모리 공간을 할당해준다.
• 중개자없이 곧바로 메모리에 접근할 수 있기 때문에 다른 모든 IPC 중에서 가장 빠르게 작동한다.
• 다만, 서로의 데이터에 일관성 문제가 발생할 수 있어, 동기화 문제가 발생할 수 있다.

⚠️ 사용할 때 주의할 점

• 세마포어, 뮤텍스, 스핀락 등 반드시 동기화 기법을 함께 사용해야 한다.
• 접근 권한 실수로 보안 문제가 발생할 수 있으므로 메모리 해제 및 접근 권한 관리를 잘해야 한다.

5. 소켓 (Socket)

네트워크 통신 기반 방식으로, 로컬 프로세스 간에도 사용이 가능하다.

6. 시그널 (Signal)

프로세스 간 간단한 이벤트/상태 알림을 위한 신호를 전송할 수 있는 방식이다.

❓ 메시지 큐는 단방향인가요?

운영체제 메시지 큐는 단방향 또는 양방향 둘 다 가능하다.

기본 설계는 단방향으로, 한 쪽 프로세스가 메시지를 보내고, 다른 쪽 프로세스가 그 메시지를 받는 구조이다.

1. 단방향 메시지 큐 : 프로세스나 스레드가 메시지를 큐에 보낼 수 있지만, 직접적인 응답을 기대하지 않는다. 다른 프로세스나 스레드는 전달된 메시지를 읽고 처리할 수 있다.
2. 양방향 메시지 큐 : 프로세스나 스레드는 요청 메시지를 보내고 응답을 기대한다. 수신 프로세스는 요청을 처리하고 응답 메시지를 발신자에게 다시 보낼 수 있다. 요청-응답 패턴으로도 불린다.

• 두 개의 메시지 큐를 만들어서, 각 방향마다 하나씩 사용하면 된다.

정리하자면, 단방향 메시지 큐는 프로세스가 다른 프로세스에게 알림이나 정보를 전달해야 할 경우에 적합하며, 양방향 메시지 큐는 요청이 보내지고 응답이 수신되어야 하는 더 상호작용적인 통신이 필요한 경우에 유용하다.

---

Thread-safe

여러 스레드가 동시에 하나의 자원에 접근해도 문제가 생기지 않도록 보호된 상태이다.

여러 스레드가 같은 변수를 동시에 증가시키면, Race Condition이 발생하고, 결과를 예측할 수 없게 된다.

Thread safe하다는 건 이런 상황에서도 결과가 항상 일관성있게 나오고, 내부 상태가 꼬이지 않도록 보장된다는 의미이다.

Thread Safe를 보장하는 방법

1. 상호 배제(Mutual Exclusion)

• 여러 스레드가 동시에 공유 자원에 접근할 수 없도록 한다.
• 특정 코드(임계 구역)를 한 번에 하나의 스레드만 실행하도록 제한하는 것이다.
• 뮤텍스(mutex), 세마포어(semaphore) 등의 동기화 메커니즘이 사용될 수 있다.

2. 불변 객체 (Immutable Objects)

• 객체의 상태가 변경되지 않도록 설계하여 여러 스레드가 안전하게 공유할 수 있도록 한다.
• 객체가 한 번 생성되면 공유되어도 그 상태가 변경되지 않으므로 안전하다.

3. 스레드 로컬 변수 (Thread-Local Variables)

• 각 스레드가 자신만의 변수를 사용하도록 만든다.
• 변수를 공유하지 않게 되기 때문에 스레드 간의 상태 공유를 방지할 수 있고, 동기화가 필요없게 된다.

4. 원자적 연산 (Atomic Operation)

• 원자적 연산은 다중 스레드 환경에서 안전하게 실행되는 연산이다.
• 원자적으로 변수를 증가시키는 연산은 여러 스레드가 동시에 실행되더라도 안전하게 실행되며, 잠금의 오버헤드를 줄일 수 있다.
• CPU의 하나의 명령어로 처리되는 연산을 사용한다. 예) AtomicInteger

5. 동기화 컬렉션 (Synchronized Collection)

• 스레드 안전한 컬렉션은 여러 스레드가 안전하게 컬렉션에 접근할 수 있도록 동기화된 메서드를 제공한다.
• Java에서는 Collections.synchronizedList, Collections.synchronizedMap 등의 메서드를 사용하여 동기화된 컬렉션을 생성할 수 있다.

❓ Thread Safe를 구현하기 위해 반드시 락을 사용해야 할까요? 그렇지 않다면, 어떤 다른 방법이 있을까요?

꼭 락이 필요한 것은 아니다.

락 없이 Thread Safe를 구현하는 대표적인 방법 :

방법	설명
Atomic 변수	예: Java의 AtomicInteger, C++의 std::atomic
불변 객체	객체의 상태를 바꿀 수 없게 만듦 (Java의 String, Python의 tuple)
Thread-local	변수 스레드마다 데이터 별도 관리해서 공유 자체를 막음
Lock-free, Wait-free 알고리즘	CAS(Compare And Swap) 등의 기법으로 공유자원 동기화 없이 구현

락은 직관적이고 강력하지만, 오버헤드와 데드락 위험이 있기 때문에 상황에 따라 다양한 방법을 이용할 수 있다.

❓ Peterson's Algorithm

두 개 이상의 프로세스의 동기화 문제를 해결하는 방법 중 하나로, 두 개의 스레드가 공유 자원에 교대로 접근할 수 있도록 보장하는 고전적인 알고리즘이다.

핵심 아이디어

int turn;
boolean flag[2];

• turn 은 critical section에 들어갈 수 있는 프로세스를 나타내는 변수이고, flag 는 critical section에 들어갈 준비 상태를 나타내는 변수이다.
• 상대 스레드가 먼저 접근하면 기다리고, 바쁜 대기(Spin) 방식을 사용한다.

코드

public static void criticalSection(int i, int j) {
	for (int k = 0; k < 1000000; k++) {
    	// 진입 의사 표현
        flag[i] = true;
        turn = j;

		// 상대방이 진입 의사가 있고, 내 차례가 아니면 대기
        while (flag[j] && turn == j) {
        	// busy-wait (Spin)
        }

		// ----- 크리티컬 섹션 -----
        sharedData++;
        // -------------------------

		flag[i] = false; // 나왔다는 신호
	}
}

한계점

• 2개 스레드만 지원한다.
• 메모리 접근 순서를 보장해야 함 (현대 CPU에서는 최적화로 순서가 바뀔 수 있음 → 실패 가능)
  • CPU 성능 최적화 때문에 turn, flag 설정 순서가 바뀌면 알고리즘이 제대로 동작하지 않는다.
  • 자바에서는 volatile 키워드로 문제를 해결한다.
• Spin 방식이므로 비효율적이다. (CPU 낭비)

Race Condition

다중 스레드 또는 프로세스 환경에서 발생하는 문제로, 두 개 이상의 스레드가 하나의 공유 자원 혹은 임계 구역에 접근하여 수정하려고 할 때, 실행 순서에 따라 결과가 달라지는 상황을 말한다.

예시

int count = 0;

Thread A: count += 1;
Thread B: count += 1;

해결방법

• 이러한 Race Condition을 예방할 수 있는 방법으로 세마포어(Semaphore)와 뮤텍스(Mutex)가 있다.