• 리소스 낭비를 방지하고 효율성을 극대화하기 위해
• ex) 파일 시스템, 네트워크 프린터, 메모리, 데이터베이스 등 | | 임계 영역 (Critical Section) | 정의: 공유 자원에 접근하는 프로그램 코드의 일부분 정의2: 공유 자원에 접근하는 프로그램 코드의 일부분으로, 동시에 여러 프로세스나 스레드가 접근하면 문제가 생길 수 있는 구간
• 데이터 무결성 유지: 공유 자원이 잘못된 상태로 수정되지 않도록 한다.
• 경합 조건(Race Condition) 방지: 여러 프로세스나 스레드가 동시에 실행되면서 공유 자원에 비정상적인 동작(중복 수정, 데이터 손실)이 발생하지 않도록 한다. | | 동기화(Synchronization) | 정의: 작업(스레드 또는 프로세스)이 공유 자원에 동시에 접근할 때 발생할 수 있는 충돌이나 데이터 무결성 문제를 방지하고, 작업의 일관성을 보장하기 위한 기술
• 데이터 무결성 손실: 공유 데이터를 수정하면 의도하지 않은 결과가 발생
• 데이터 경합: 여러 스레드가 자원에 동시 접근하여 실행 순서에 따라 예측 불가능한 결과를 초래
• 데드락: 동기화가 잘못 구현되면 스레드 간 자원 점유 순서가 꼬여 무한 대기에 빠진 상태 | | 락 | 정의: 하나의 스레드나 프로세스가 자원을 점유할 경우 다른 스레드/프로세스가 해당 자원에 접근하지 못하도록 제어하는 기법 | | 원자성 | 정의: 더 이상 나눌 수 없는 최소 단위의 연산 | | 데드락 | 정의: 두개 이상의 스레드가 서로를 기다리면서 영원히 차단되는 상태를 의미 | | 기아 현상 | 정의: 특정 프로세스의 우선순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태 | | 락-프리 (Lock-Free) 알고리즘 | 정의: 여러 개의 쓰레드에서 동시 호출하더라도 특정 단위 시간에는 적어도 한개의 호출이 완료되는 알고리즘
• 시스템의 어느 한 스레드라도 계속 진행될 수 있음
• 특정 스레드가 계속 실패할 수도 있지만, 다른 스레드는 계속해서 작업을 진행할 수 있음
• 데드락(Deadlock)이 발생하지 않음
• 하지만 특정 스레드가 무한히 재시도할 가능성이 있음(라이브락(Livelock) 가능) ✅ 보장하는 것: 적어도 한 개의 스레드는 계속 실행됨 ⚠️ 보장하지 않는 것: 모든 스레드가 유한한 시간 내에 완료될지 여부 | | 웨이트-프리 (Wait-Free) 알고리즘 | 정의: 모든 스레드가 유한한 단계 안에서 반드시 완료될 수 있도록 보장하는 알고리즘
• 모든 스레드가 유한한 연산(제한된 단계) 안에서 반드시 완료됨
• 공정성(Fairness)이 보장됨 → 특정 스레드가 계속 실패하지 않음
• 데드락(Deadlock)이 발생하지 않음
• 라이브락 발생하지 않음 ✅ 보장하는 것: 모든 스레드가 유한한 시간 내에 작업을 완료함 ⚠️ 보장하지 않는 것: 구현이 복잡하고, 메모리 오버헤드가 클 수 있음 |

🌟 기존 락 기반 동기화 기법(Mutex, Semaphore, Read-Write Lock, Spinlock, Distributed Lock 등)은 공유 자원을 보호하기 위해 락을 사용하지만, 락을 사용할 경우 성능 저하와 교착 상태(Deadlock) 같은 문제가 발생할 수 있어.

• 락을 사용하지 않고 동시성 문제를 해결하는 방법이 Wait-Free & Lock-Free 알고리즘
• 이러한 기법들은 비차단(Non-Blocking) 알고리즘에 속하며, CAS(Compare-And-Swap) 연산 같은 원자적 연산(Atomic Operation)을 활용해 동기화를 보장한다.

1️⃣ 여러 프로세스 또는 스레드가 공유 자원을 안전하게 접근할 수 있도록 보장하는 동기화 조건 3가지

1. Mutual Exclusion (상호 배제)

• 하나의 프로세스가 임계 구역(Critical Section)에 들어가서 자원을 사용하고 있을 때, 다른 프로세스는 해당 자원을 사용할 수 없어야 한다. 즉, 동시에 두 개 이상의 프로세스가 같은 임계 구역을 실행할 수 없음.

ex)

• Lock (잠금 기법, 예: Mutex, Spinlock)
• Semaphore (세마포어)

2. Progress (진행)

• 어떤 프로세스가 임계 구역에 들어가야 할 필요가 있을 때, 다른 프로세스들이 무한정 방해하지 않아야 한다. 즉, 임계 구역에 진입하려는 프로세스가 있을 경우, 제한된 시간이 지나면 반드시 실행될 수 있어야 한다.

ex)

• Context Switching을 통한 CPU 점유권 양보

3. Bounded Waiting (유한한 대기)

• 특정 프로세스가 임계 구역에 진입하기 위해 대기할 때, 무한정 기다리지 않도록 해야 한다.

ex)