Lemonyun

atomic

#include <atomic>
std::atomic<int> counter(0);

여러 쓰레드에서 atomic 객체 자원을 수정할 때 원자적 연산(CPU가 명령어 한개로 처리하는 명령)을 사용하면 mutex를 사용하지 않아도 정상적인 결과가 나온다.

memory order

멀티 쓰레드 환경에서 컴파일러와 CPU가 명령어 순서를 재배치하여 환경에 따라 결과가 달라지는 문제를 막기 위해 메모리 재배치 순서를 강제할 수 있다.

memory_order_relaxed (자유)

// atomic<int> 객체 포인터 a, b, c에 대해

// memory_order_relaxed
// 스레드 내부에서 두 대입 명령들의 순서는 바뀔 수 있다. (CPU가 마음대로 재배치 가능하다.)
int x = a->load(memory_order_relaxed);  // x = a (읽기, 원자적 연산)
b->store(1, memory_order_relaxed);      // b = 1 (쓰기, 원자적 연산)

c->fetch_add(2, memory_order_relaxed); // c = c + 2 

c->is_lock_free() // c 객체의 연산들이 원자적으로 구현될 수 있는지 확인
// true인 경우 mutex의 lock unlock 없이도 연산을 올바르게 수행할 수 있다는 뜻

memory_order_acquire와 memory_order_release

// 두 쓰레드가 공유하는 변수 data의 release와 acquire을 사용하여 동기화를 수행하는 코드

void producer() {
  data[0].store(1, memory_order_relaxed);
  data[1].store(2, memory_order_relaxed);
  data[2].store(3, memory_order_relaxed);
  is_ready.store(true, std::memory_order_release);
}

void consumer() {
  // data 가 준비될 때 까지 기다린다. (스핀 락)
  while (!is_ready.load(std::memory_order_acquire)) {
  }

  std::cout << "data[0] : " << data[0].load(memory_order_relaxed) << std::endl;
  std::cout << "data[1] : " << data[1].load(memory_order_relaxed) << std::endl;
  std::cout << "data[2] : " << data[2].load(memory_order_relaxed) << std::endl;
}

memory_order_release는 해당 명령 이전의 모든 메모리 명령(읽기, 쓰기)들이 해당 명령 이후로 재배치 되는 것을 금지한다.

memory_order_acquire는 해당 명령 뒤에 오는 모든 메모리 명령들이 해당 명령 위로 재배치 되는 것을 금지한다.

memory_order_acq_rel

ㄴ acquire와 release를 모두 수행하는 것

ㄴ 읽기와 쓰기를 모두 수행하는 명령들, 예를 들어 fetch_add와 같은 함수에서 사용될 수 있다.

memory_order_seq_cst

ㄴ 메모리 명령의 순차적 일관성을 보장해준다. (모든 쓰레드에서 모든 시점에 동일한 값을 관찰할 수 있게 해준다.)

ㄴ atomic 객체를 사용할 때 memory_order를 지정해주지 않는다면 디폴트로 memory_order_seq_cst가 지정된다.

ㄴ memory_order_seq_cst를 사용하는 메모리 연산들끼리는 모든 쓰레드에서 동일한 연산 순서를 관찰할 수 있도록 보장해준다.

ㄴ 멀티 코어 시스템에서 비싼 연산이다. AMD 계열 CPU는 차이가 크지 않지만 ARM 계열은 동기화 비용이 크다.

참조:

https://modoocode.com/271

대기시간이 길고 의존관계가 없는 연산들을 병렬적으로 처리하기 위해 쓰레드를 사용한다.

C++11 이전에는 표준화된 쓰레드가 없어서 각 플랫폼마다 다른 구현을 사용해야 했지만, C++11부터 표준에 쓰레드가 추가되었다.

Thread 생성, join, detach

#include <thread>
#include <iostream>

using namespace std;
using std::thread;

void func1() {
    for (int i = 0; i < 10; i++) {
        cout << "스레드 1 작동중" << endl;
    }
}

void func3() {
 
    // 현재 코드를 실행중인 스레드의 id
    cout << "쓰레드 3 id : " << std::this_thread::get_id() << endl;

    for (int i = 0; i < 10; i++) {
        cout << "스레드 3 작동중" << endl;
    }
}


int main()
{
    // 내 컴퓨터의 논리 프로세서가 몇개인지 출력
    cout << "논리 프로세서의 개수 : " << std::thread::hardware_concurrency() << endl;

    // 현재 코드를 실행중인 스레드의 id
    cout <<  "메인 쓰레드 id : " << std::this_thread::get_id() << endl;

    thread t1(func1);
    thread t2([] {
        for (int i = 0; i < 10; i++) {
            cout << "스레드 2 작동중" << endl;
        }
    });

    thread t3(func3);


    t1.join();
    t2.detach();
    t3.detach();
    cout << "메인 함수 종료" << endl;
}

메인 쓰레드에서 join은 해당 쓰레드가 종료될 때까지 기다리지만, detach는 기다리지 않는다.

출력

쓰레드에 인자 전달하기

쓰레드가 실행하는 함수는 리턴 값이 없기 때문에 인자의 포인터를 활용하여 전달해야 한다.

void worker(vector<int>::iterator start, vector<int>::iterator end, int* result){
            // 반복자의 시작부터 끝까지의 합을 계산하여 result에 저장하는 코드
}

int main() {
	vector<int> data(10000);

	vector<int> partial_sums(4);
    
    // 각 스레드에서 2500개의 요소를 계산하도록 함
    // 합을 받기 위한 int* 를 인자로 보냄
    for(int i=0; i<4; i++){
    	worker.push_back(thread(worker, data.begin() + i * 2500, data.begin() + (i + 1) * 2500, &partial_sums[i]));
    }
	
}

여러 쓰레드에서 같은 메모리 공간(변수)에 접근하는 경우 (mutex lock, unlock, lock_guard)

경쟁 상태(race condition)가 발생한다.

뮤텍스를 사용하여 스레드에서 변수를 사용하기 위해서는 한 번에 한 쓰레드에서만 뮤텍스를 가지고 있도록(lock) 하고, 접근이 끝나면 뮤텍스를 풀어(unlock), 다른 쓰레드가 뮤텍스를 가질 수 있도록 한다.

뮤텍스의 lock()과 unlock() 사이에 한 쓰레드만이 유일하게 실행할 수 있는 코드 부분을 임계 영역(critical section)이라고 한다.

lock_guard 객체는 뮤텍스를 인자로 받아 생성되는데 생성될 때 뮤텍스의 lock을 실행하고, 범위를 벗어나 소멸되면 뮤텍스의 unlock을 자동으로 호출한다.

#include <iostream>
#include <mutex>
#include <thread>
#include <vector>

void worker(int & result, std::mutex& m){
    // case 1 : lock, unlock을 사용한 경우
    for(int i = 0; i< 10000; i++){
        m.lock();
       	/* 임계 구역 시작 */
        result += 1;
        /* 임계 구역 끝 */
        m.unlock();
    }
    
    /* case 2 : lock_guard를 사용한 경우
    for(int i = 0; i< 10000; i++){
        std::lock_guard<std::mutex> lock(m);
        result += 1;
        
        // scope를 빠져 나가면 lock이 소멸되면서 m을 알아서 unlock 한다.
        // 예외가 발생하는 상황에서도 try-catch 구문으로 잘 감싸주면 자동으로 lock을 해제한다.
    }
    */
}

int main() {
    int counter = 0;
    std::mutex m;

    std::vector<std::thread> workers;
    for (int i = 0; i < 4; i++) {
    	// 쓰레드에 레퍼런스를 넘길 때는 래퍼로 감싸야 한다.
        workers.push_back(std::thread(worker, std::ref(counter), std::ref(m)));
    }

    for (int i = 0; i < 4; i++) {
        workers[i].join();
    }
	
    // 40000을 출력한다.
    std::cout << "Counter 최종 값 : " << counter << std::endl;
}

생산자-소비자 패턴을 구현할 때 condition_variable을 사용하기 (+ unique_lock)

생산자 쓰레드는 공유하는 큐에 작업을 추가한다. (큐는 공유 자원이므로 임계 영역에서 수정)

소비자 쓰레드는 생산자 쓰레드가 생산한 작업을 처리한다. (큐에 작업이 있는 경우에 pop하여 처리한다.)

이때 condition_variable을 사용하지 않고 구현한다고 하면 소비자 쓰레드가 큐가 비었는지를 지속적으로 확인 해야 한다. (while문, std::this_thread::sleep_for(), 시간 객체 chrono, 큐의 empty() 사용) 이는 CPU 낭비다(스핀락). 지속적으로 mutex를 잠그고 큐를 확인해야 하기 때문이다.

소비자 쓰레드들을 특정 조건(큐가 empty가 아닌) 이 일어나기 전까지 재우도록(block) 하는 것이 condition_variable의 역할이다. 

생산자-소비자 패턴에서의 작업 진행 순서

1. 생산자 쓰레드에서 큐에 작업을 넣고, cv->notify_one()을 호출하여 cv->wait으로 인해 조건을 만족하지 못해 잠자고 있던 소비자 쓰레드중 하나를 깨운다.

1-1 cv->wait 함수는 unique_lock과 (조건자 혹은 람다 함수) (인자를 받지 않고 bool값을 리턴하는)을 인자로 받는다.

2. 깨어난 소비자 쓰레드에서는 cv->wait의 조건을 통과한다.(lock을 얻는다) 소비자 쓰레드는 큐에서 작업을 pop하고, unique_lock을 unlock() 한다.

3. 소비자 쓰레드는 작업을 처리한다.

lock_guard 대신 unique_lock을 사용하는 이유

ㄴ lock_guard는 생성자, 소멸자를 통해서만 mutex를 lock, unlock 할 수 있지만 unique_lock은 lock을 얻는 시점을 정할 수 있고 unlock을 직접 호출할 수도 있다.

wait 말고 wait_for나 wait_until도 있다.

참조:

https://modoocode.com/269

1. 시퀀스 컨테이너 (요소의 순서가 유지됨)

vector

ㄴ 연속적인 메모리 공간에 요소들을 저장한다. (배열 기반 컨테이너)

ㄴ 중간에 원소를 삽입(insert)거나 지우는(erase) 연산은 O(n)이기 때문에 비효율적이다.

1. push_back() 

ㄴ 맨 뒤에 원소를 추가

ㄴ O(1)의 시간 복잡도

ㄴ 공간을 초과할 경우 새로운 공간을 할당하기 위해 O(n) 소요

2. size()

ㄴ 벡터가 가진 원소의 개수를 리턴한다.

3. at(), []

ㄴ 벡터의 원소에 접근한다.

4. resize()

ㄴ 원소의 개수를 조정한다.

ㄴ capacity보다 작은 값을 인자로 주면 원소의 개수를 줄인다.

ㄴ capacity보다 큰 값을 인자로 주면 capacity를 인자 값으로 늘리고, 빈 공간은 원소의 기본값(기본 생성자 호출)으로 채운다.

5. reserve()

ㄴ capacity를 재설정한다.

ㄴ 기존 capacity 보다 작은 값을 인자로 받을 경우엔 아무일도 일어나지 않는다.

6. pop_back()

ㄴ 마지막 원소를 제거

ㄴ O(1)의 시간 복잡도

list

노드 기반의 컨테이너 (double linked list)

중간에 데이터 삽입이나 삭제 연산이 O(1)의 시간 복잡도를 가지기 때문에 중간에 데이터 삽입이나 삭제가 자주 발생할 경우 사용하면 좋다.

원소에 바로 접근할 수 있는 수단이 없다.

deque

배열 기반 컨테이너

vector와 다른점

ㄴ 자료들이 여러개의 메모리 블록에 나뉘어 저장된다.

ㄴ push_front(), pop_front() 메서드를 사용하여 맨 뒤 뿐만 아니라 맨 앞에서 원소를 빠르게 O(1)로 넣고 지울 수 있다. 

ㄴ vector는 삽입으로 인해 메모리 용량을 초과할 경우에 기존의 메모리를 삭제하고 새로운 메모리를 할당해 원소들을 복사하는데, deque은 메모리 블럭을 새로 할당한다. (vector에 비해 확장하기 용이하다)

ㄴ 중간에 원소를 추가/제거 하는 경우에도 vector에 비해 효율이 좋다. 원소들을 앞과 뒤로 밀어낼 수 있기 때문이다.

2. 연관 컨테이너 (요소의 위치를 지정할 수 없음)

map

key-value 쌍으로 값을 저장한다 (연관 컨테이너)

균형 이진 트리를 이용한 빠른 검색에 특화된 자료구조이다.

검색 연산은 O(logn)의 시간 복잡도를 가진다.

중복된 key값을 허용하지 않는다.

삽입과 삭제가 일어날 때마다 원소 쌍들은 자동으로 정렬 된다. 삽입과 삭제는 O(logn) 시간 복잡도를 가진다.

iterator는 중위 순회를 통해 원소에 접근하게 해준다.

#include <iostream>
#include <map>
using namespace std;

int main(){
	map<int, string> temp;
    
    // map에 원소 쌍을 추가하는 법
    temp.insert({40, "photo"}); 
    temp.insert(make_pair(4, "world"));
    
    // key를 사용하여 value에 접근하는 법
    cout << temp[40] << endl;

    // 수정도 가능하다.
    temp[40] = "hello";
    
}

hashmap

해시 테이블을 이용하여 key-value 쌍을 저장하는 자료구조

컨테이너에 자료를 추가하거나 삭제하는데 다른 컨테이너보다 비용이 크기 때문에 빈번하게 자료의 삽입 삭제를 피해야 한다.

많은 자료를 저장하고, 검색 속도가 빨라야 하는 경우에만 사용하는 것이 좋다.

set

Map과 거의 비슷하지만 key-value가 아닌 value만 저장한다.

3. 컨테이너 어댑터 (기능이 변형된 컨테이너, 반복자를 지원하지 않음)

stack

LIFO (Last in First out) 방식으로 동작한다.

내부 컨테이너 구조를 선택할 수 있다. (vector, deque, list) 디폴트는 deque이다.

push(), top(), pop() 함수를 사용한다.

queue

FIFO (First in First out) 방식으로 동작한다.

내부 컨테이너 구조를 선택할 수 있다. (deque, list) 디폴트는 deque이다.

front(), back(), push(), pop() 함수를 사용한다.

priority_queue

우선순위 큐는 힙 자료구조(배열)을 채택하기 때문에 내부 컨테이너는 (vector, deque)로 구현되어 있다. 디폴트는 vector이다.

프로그래머가 정한 우선순위에 따라 우선순위가 가장 높은 데이터가 먼저 나온다.

삽입과 삭제가 O(logn) 시간복잡도를 가진다.

기본 우선순위는 최대힙(내림차순, 부모 노드가 자식 노드보다 작지 않음)이다. (가장 큰 수가 루트 노드에 있다. pop()을 사용하면 루트 노드를 제거하고 값을 얻는다.)

push(), top(), pop() 함수를 사용한다.

std::priority_queue<int> pq;

// 내부 컨테이너를 설정할 수 있다.
std::priority_queue<int, std::deque<int>> pq1;

// 내부 컨테이너 설정 + 오름차순 우선순위
std::priority_queue<int, std::vector<int>, std::greater<int>> pq2;

참조:

https://blog.naver.com/yoochansong/221739086178

전처리기 : #include, #define, #ifdef 같은 구문을 처리한다. 

컴파일러 : 전처리가 끝난 cpp 파일을 입력으로 받아 기계어로 된 목적 프로그램을 출력하기 위해 사용되는 언어 번역 프로그램이다. 

어셈블러 : 어셈블리어를 기계어(0, 1)로 바꿔주는 일을 한다. 오브젝트 파일(.obj)을 생성한다.

링커 : 여러 오브젝트 파일을 하나로 합치거나 라이브러리와 합쳐 실행 프로그램(.exe)를 생성한다.

참조 : https://iforint.tistory.com/36

          https://nuritech.tistory.com/2