Thread Safe
Thread Safe하다는 것은 어떤 의미인가요?
- Thread Safe란 멀티 스레드 프로그래밍에서 일반적으로 어떤 함수나 변수, 혹은 객체가 여러 스레드로부터 동시에 접근이 이루어져도 프로그램의 실행에 문제가 없는 것을 말한다.
- 하나의 함수가 한 스레드로부터 호출되어 실행 중일 때, 다른 스레드가 그 함수를 호출하여 동시에 함께 실행되더라도 각 스레드에서 함수의 수행 결과가 옳게 나오는 것이다.
Thread-state하다는 의미는 두 개 이상의 스레드가 경쟁 상태에 들어가거나 같은 객체에 동시에 접근해도 연산 결과는 정합성이 보장될 수 있게 메모리 가시성이 확보된 상태이다.
Thread Safe 를 보장하기 위해 어떤 방법을 사용할 수 있나요?
Mutual Exclustion (상호 배제)
- 공유 자원에 하나에 Thread만 접근할 수 있도록 세마포어나 뮤텍스로 락을 통제하는 방법이다.
- 일반적으로 많이 사용하는 방법이다.
Atomic Operation (원자 연산)
- 공유 자원 변경에 필요한 연산을 원자적으로 분리한ㄷ ㅟ에 실제로 데이터의 변경이 이루어지는 시점에 Lock을 걸고, 데이터를 변경하는 시간 동안 다른 쓰레드의 접근이 불가능하도록 하는방법이다.
- a += b의 경우 먼저 + 연산을 한 뒤에 = 연산을 하기에 원자적이라고 볼 수 없다.
Thread-Local Storage (스레드 지역 저장소)
- 공유 자원의 사용을 최대한 줄이고 각각의 스레드에서만 접근 가능한 저장소들을 사용함으로 인해 동시 접근을 막는 방법이다.
- 일반적으로 공유 상태를 피할 수 없을 때 사용하는 방식이며, 전역 변수 사용을 자제하라는 뜻으로 이해하면 된다.
Re-Entrancy (재진입성)
- 스레드 호출과 상관없이 프로그램에 문제가 없도록 작성하는 방법이다.
- 어떤 함수가 한 스레드에 의해 호출되어 실행 중이라면, 다른 스레드가 그 함수를 호출하더라도 그 결과가 각각에게 올바르게 주어져야 한다.
- 스레드끼리 독립적으로 동작할 수 있도록 코드를 작성한다 생각하면 된다.
Peterson's Algorithm 이 무엇이며, 한계점에 대해 설명해 주세요.
두 개 이상의 프로세스의 동기화 문제를 해결하는 방법 중 하나이다.
// flag: 신호, 공유자원을 사용하고 싶다라고 표현하기 위한 변수, 임계구역에 들어갈 때는 true, 나올 때는 false로 설정
// turn: 차례, 누구 차례인지를 명시하는 변수, turn = 0 이면, 0번째 프로세스가 임계 구역에 들어가고, 1번째 프로세스가 기다린다.
bool flag[2];
int turn;
while(true) {
// i번째 프로세스가 공유자원을 사용하고 싶다는 신호를 전달하기 위해 flag를 true로 바꿔준다.
flag[i] = true;
// i 번째 프로세스가 쓰기 전에 먼저 쓰고 싶어했던 프로세스가 있는지 확인하고 수행시켜주는 코드
// 예를 들어 j번째 프로세스가 이 공유 자원을 쓰고 싶어 했으면 i번째 프로세스는 j번째 프로세스에 차례를 양보한다.
turn = j;
// busy waits 상태. turn이 j일 경우, 내 차례가 아니고 j가 자원까지 쓰고 싶어하면 나는 spinlock에 머무른다.
// 이제 내 차례거나 j가 자원을 쓰고 싶지 않은 경우(!flag[j]), spinlock을 빠져나와 임계 구역에 진입할 수 있다.
//turn과 flag를 통해 동시 접근을 막는다.
while(flag[j] && turn == j);
// critical section
// 임계 구역에 진입해서 작업을 한다.
flag[i] = false; // 다 썼으면 flag를 false로 바꿔준다.
//remainder section
} 그러나 Peterson’s Algorithm은 현대 컴퓨터 아키텍처에서는 보장되지 않은 작동을 할 가능성이 있다. 예를 들어 시스템 성능을 향상시키기 위해서 프로세서 또는 컴파일러가 종속성이 없는 읽기 및 쓰기 작업의 순서를 멋대로 바꿀 수 있다. 또한 공유 데이터가 있는 멀티스레드 응용 프로그램의 경우, 명령 순서를 변경하면 일관성이 없거나 예상하지 못한 결과가 발생할 수 있다.
Race Condition 이 무엇인가요?
공유 자원에 대하여 여러 프로세스가 동시에 접근을 시도할 때, 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태이다. 즉 실행 순서에 따라 결과값이 달라지는 일관적이지 못한 상태를 의미한다.
Thread Safe를 구현하기 위해 반드시 락을 사용해야 할까요? 그렇지 않다면, 어떤 다른 방법이 있을까요?
반드시 락을 구현하는 것이 아닌, 설계 자체를 Thread-Safe하게 할 수 있다.
재진입성
어떤 함수가 한 스레드에 의해 호출되어 실행 중일 때, 다른 스레드가 그 함수를 호출하더라도 그 결과가 각각 올바르게 주어지도록 설계하는 것이다.
상호 배제
공유 자원을 사용할 경우 해당 자원에 대한 접근을 Lock으로 통제하는 것이다. Lock도 Thread-safe를 가져가는 방법 중 하나이다.
원자 연산
공유 자원에 접근할 때 원자 연산, 원자적으로 정의된 접근 방법을 사용하는 것이다.
불변 객체
객체 생성 이후에 값을 변경할 수 없도록 하는 것이다.
정리하자면 공유 변수는 최소화하고, 공유 변수가 있다면 최대한 캡슐화하며, 관련한 문서화를 잘 이루는 설계로 Thread-safe한 설계를 할 수 있다.
Thread Pool, Monitor, Fork-Join에 대해 설명해 주세요.
Thread Pool
병렬 작업 처리 증가는 스레드 개수 증가와 같다. 스레드 생성과 스케줄링으로 인해 CPU가 과부하되고 애플리케이션 성능이 저하되는 것을 방지하기 위해, 작업 처리에 사용되는 스레드를 제한된 개수만큼 정해 놓고 작업 큐에 들어오는 작업을 스레드가 하나씩 맡아 처리하는 것이다.
작업 요청이 폭증해도 작업큐에서 작업이 대기하다가 여유 있는 스레드가 그것을 맡아서 처리하기 때문에 스레드의 전체 개수는 일정하다. 애플리케이션의 성능 저하도 일어나지 않는다.
Monitor
Monitor은 여러 스레드가 객체로 동시에 접근하는 것을 막아 상호 배제를 도와주는 Semaphore의 발전 버전이다. Monitor은 두 가지의 큐를 사용한다.
- entry queue: critical section에 진입을 기다리는 큐로, 뮤텍스에 의해 관리된다.
- waiting queue: 조건이 충족되기를 기다리는 큐로, condition variable에 의해 관리된다. condition variable의 상태는 다음과 같은 것들이 있다.
- wait
- 스레드가 자기 자신을 condition variable의 waiting queue에 넣고 대기 상태로 전환한다.
- wait시 mutex lock을 풀고 entry queue에서 새로운 스레드가 모니터로 진입하여 lock을 건다.
- 새로 들어온 스레드도 조건이 충족되지 않으면 wait하게 된다.
- signal
- waiting queue에서 대기 중인 스레드 중 하나를 깨운다.
- broadcast
- waiting queue에서 대기 중인 스레드 전부를 깨운다.
- wait
Fork Join
분할 정복 알고리즘을 사용해 재귀적으로 병렬 처리를 해 작업을 수행하는 것이다. 작업 단위가 작으면 해당 작업을 수행하고, 그렇지 않으면 작업을 반으로 쪼개서 두 개의 작업으로 나눈 뒤 두 작업을 동시에 실행시킨다. 이때, Work Stealing 알고리즘을 사용한다.
Work Stealing: 여러 개의 Deque에서 작업 처리 시, 하나의 Deque는 바쁘고 하나는 여유롭다면, 한가한 Deque가 바쁜 Deque의 꼬리에 있는 일을 가져가서 처리한다. 이 방식은 스레드가 작업을 위해 경쟁하는 것을 방지할 수 있다.
Thread Pool을 사용한다고 가정하면, 어떤 기준으로 스레드의 수를 결정할 것인가요?
리틀의 법칙
- Active user → 실제 사용자 수
- TPS → 초당 트랜잭션
- Response time → 응답 시간
Active Users = TPS * Response Time
1명의 사용자가 시스템에 요청을 보낼 때 응답이 1초에 처리 → 초당 처리건수(TPS)는 1건
초당 처리건수(TPS)가 1건이면 2명이 요청하였을 때 응답 시간은 2초가 발생
1명이 요청을 보낼 때 응답이 0.5초에 처리 → 초당 처리 건수(TPS)는 2건
2명이 요청을 보낼 때 응답이 0.5초에 처리 → 초당 처리 건수(TPS)는 4건적정 스레드 수 = CPU 개수 * (1 + 대기나 유휴 시간 / 서비스 시간)
- CPU 대기 시간이 서비스 시간보다 짧다면 CPU 개수보다 스레드가 적어야 성능이 좋다. 이유는 대기가 짧기에 (콘텍스트 스위칭 비용이 적기에) 스레드 개수가 적어도 상관없는 것이다.
- CPU 대기 시간이 서비스 시간보다 길다면 CPU 개수보다 스레드가 많아야 성능이 좋다. 이유는 대기가 길기에 (콘텍스트 스위칭 비용이 많기에) 스레드 개수를 늘려 대기를 줄여야 한다.
리틀의 법칙 등과 같은 이론으로 시스템의 성능을 측정하고, 목표치에 맞는 시스템 성능에 도달하도록 스레드 개수를 조절한다.
어떤 데이터를 정렬하려고 합니다. 어떤 방식의 전략을 사용하는 것이 가장 안전하면서도 좋은 성능을 낼 수 있을까요?
- 병합 정렬 (Merge Sort):
- 안정적인 정렬 방법으로, 데이터의 분할과 병합을 통해 정렬한다.
- 시간 복잡도는 O(n log n)으로 매우 효율적이며, 대규모 데이터셋에서도 잘 작동한다.
- 퀵 정렬 (Quick Sort):
- 평균적으로 매우 빠른 성능을 보이는 정렬 알고리즘이다.
- 안정성은 보장되지 않지만, 대부분의 상황에서 빠른 정렬을 제공한다.
- 힙 정렬 (Heap Sort):
- 안정적이며, 최악의 경우에도 O(n log n)의 성능을 보장하는 정렬 방식이다.
- 힙 구조를 활용하여 데이터를 정렬한다.
- 삽입 정렬 (Insertion Sort):
- 작은 크기의 데이터셋에서 효과적이며 안정적인 정렬 방법이다.
- 이미 정렬된 부분이 있다면 빠르게 수행된다.
- 외부 정렬 (External Sorting):
- 대용량 데이터를 안정적으로 정렬하기 위한 방법으로, 외부 기억장치를 활용한다.
- 병합 정렬과 같은 기법을 사용한다.
정렬 알고리즘은 다양하고 많아서 무엇이 안정적이고 좋은 성능이라고 말하기는 어렵다. 다만 요구되는 상황과 여러 실험을 통해 정렬 알고리즘을 비교하고 때에 맞춰 선택하면 된다.
Thrashing 이란 무엇인가요?
페이지
프로세스의 논리 주소 공간을 일정 단위로 자른 파편이다. 메모리의 물리 주소 공간을 나눈 것은 프레임이라고 부른다.
Thrashing이란 페이지 부재율이 증가하여 CPU 이용률이 급격하게 낮아지는 현상을 이야기한다. 프로세스를 처리하는 시간보다 메모리에 올라오지 못한 페이지를 불러오느라 페이지 교체에 드는 시간이 증가하고, 이로 인해 CPU 이용률이 떨어진다.
운영체제는 CPU 이용률이 낮으면 MPD(Multi-Programming Degree)라는 다중 프로그래밍 정도의 강도를 높이게 된다. 이는 동시에 실행하는 프로세스가 많아질수록 프로세스에 할당된 메모리 페이지와 프레임들의 간격도 좁아지게 하는 결과를 초래한다. 너무 작은 페이지 프레임을 할당받은 프로세스들은 또 페이지를 불러오는 부재가 증가하게 되어 CPU의 이용률이 더 떨어지는 악순환이 생긴다.
Thrashing 발생 시, 어떻게 완화할 수 있을까요?
Working Set
지역성의 원리를 이용하여 지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 기법이다.
워킹셋이라는 이름과 같이 프로세스의 작업에 자주 참조되는 페이지들을 묶는다고 생각하면 된다.
Page Fault Frequency (페이지 부재 빈도)
프로세스의 페이지 부재율을 주기적으로 조사하고, 이 값에 근거하여 각 프로세스에 할당할 메모리 양을 동적으로 에측하고 조절하는 알고리즘이다. 현재 페이지 부재와 직전 페이지 부재 사이의 시간을 관찰하여 상한값을 초과하거나 하한값 미만이 되면 운영체제가 메모리에 올라가 있는 프로세스 수를 조절한다.
