리눅스타일

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/42579

해당 문제는 map, vector, priority_queue, compare()를 자유롭게 사용할 수 있어야 풀이가 쉬운 문제였다.

map을 vector로 복사하는 방법과 map의 value로 pq를 정의하고,  sort()와 pq의 우선순위를 compare() 함수로 정의하는 방법을 익힐 수 있었다.

2. 풀이

1. 장르별 총 재생횟수를 map에 저장하였다. --> map<장르, 총count>
2. 위 map을 총 재생횟수를 기준으로 내림차순 정렬하기 위해 vector로 복사하였다. --> vector<장르, 총 count>
3. 내림차순으로 정렬된 벡터로부터 장르를 얻어온다.
4. 위에서 얻어온 장르 내에서 많이 재생된 2개의 노래를 탐색하기 위해 map을 정의하였다. key는 장르로, value는 우선순위 큐로 정의했다. --> map<key(장르),value(pq(pii<count, id>))>
4. 우선순위 큐는 장르내에서 가장 많이 재생된 노래 순으로, 만약 재생 횟수가 같다면 id 가 낮은 순으로 정의했다.
5. 우선순위 큐를 2번만 삭제하여 가장 많이 재생된 2곡을 answer에 저장하였다.

3. 코드

#include <string>
#include <vector>
#include <map>
#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;

#define f	first
#define s	second
typedef pair<int, int> pii;
typedef pair<string, int> psi;

bool cmp(psi a, psi b) {
	return (a.s > b.s);
}

// 우선순위1 : count 내림차순
// 우선순위2 : id 오름차순
struct cmp2 {
	bool operator() (pii a, pii b) {
		if (a.f == b.f)
			return (a.s > b.s);
		else
			return (a.f < b.f);
	}
};

// 장르별 총 재생횟수 저장 map<장르, 총count>
// 위 map을 vector로 복사 후 내림차순 정렬-> vector<장르, 총 count>
// 장르내 많이 재생된 2개 노래 탐색 -> map<key(장르),value(pq(pii<count, id>))>
// 장르내 많이 재생된 2개의 노래 id를 answer에 저장

vector<int> solution(vector<string> genres, vector<int> plays) {
	vector<int> answer;
	map<string, int> genre_map;
	map<string, priority_queue<pii, vector<pii>, cmp2>> genre_queue;
	// pq를 내림차순으로 하는 경우
	// map<string, priority_queue<pii, vector<pii>, greater<pii>>> map_queue;

	for (int id = 0; id < genres.size(); ++id) {
		string genre = genres[id];
		int play = plays[id];

		genre_map[genre] += play;
		genre_queue[genre].push(pii(play, id));
	}

	vector<psi> genre_vec(genre_map.begin(), genre_map.end());
	sort(genre_vec.begin(), genre_vec.end(), cmp);

//     for (psi p : genre_vec)
//         printf("%s %d\n", p.f.c_str(), p.s);

	for (psi p : genre_vec) {
		string genre = p.f;
		printf("%s %d\n", p.f.c_str(), p.s);

		int n = 0;
		while (!genre_queue[genre].empty()) {
			pii cur = genre_queue[genre].top();
			genre_queue[genre].pop();
			printf("%d %d\n", cur.first, cur.second);
			answer.push_back(cur.second);
			n++;
			if (n == 2)
				break;
		}

	}

	return answer;
}

Thread-safe vs Reentrant

Thread-safe : 멀티쓰레딩 환경에서 여러 쓰레드에 의해 코드가 실행되더라고 실행 결과의 정확성이 보장되는 것.

Reentrant : 멀티쓰레딩 환경에서 여러 쓰레드가 코드를 동시에 수행할 수 있고, 그런 경우에도 실행 결과의 정확성이 보장되는 것.

여기서 동시라는 개념에 대해 살펴보자.

예를 들어, 뮤텍스로 특정 임계영역을 보호한다고 하면, 뮤텍스를 기다리는 쓰레드는 대기상태에서 임계영역을 실행 중인 쓰레드가 뮤텍스를 제공할 때까지 기다리게 되는데, 이러한 상황은 쓰레드들이 동시에 수행되는 것으로 볼 수 없다. 그리고 쓰레드가 임계영역에 대한 뮤텍스를 기다리는 상황은 전체적인 성능 저하를 만든다.

반면, 여러 쓰레드에서 특정 코드를 실행할 때 다른 쓰레드의 영향을 받지않고 독립적으로 실행될 때 동시에 실행된다고 볼 수 있다. 따라서, Thread-safe보다 Reentrant가 더 강력한 제약조건이다.

Thread-safe 는 뮤텍스와 같은 동기화 메커니즘을 이용해 구현할 수 있다.

Thread-safe 와 달리 Reentrant는 구현이 어렵다. Thread-safe는 내부 구현만 바꾸면 되는 경우가 많지만, Reentrant는 인터페이스를 재설계해야 하는 경우가 많다.

Reentrant 와 Thread-safe 의 차이

Implementation approach of Thread-safe

Thread-safe는 공유 자원에 대한 경쟁 상태를 회피하기 위한 2가지 접근 방법을 통해 구현할 수 있다.

경쟁 상태 : 동시에 여러 스레드가 동일한 데이터를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서의 의존하는 상황

thread-safe 구현을 위해 애초에 공유 상태를 피하는 방법과 공유 상태를 피할 수 없는 상황에서 동기화를 사용하는 방법이 있다.

1. 공유 상태를 피하는데 중점을 두는 방법

• Re-entrancy

위에서 설명한 Reentrant 을 구현하기 위해서는 공유하는 자원, 즉 임계 영역이 없도록 해야 한다.

각 쓰레드별 지역 변수를 사용하여 여러 쓰레드들이 동시에 같은 코드를 실행할 수 있도록 한다.

• Thread-local storage

전역변수 대신 쓰레드별로 지역변수를 사용하도록 하여 공유 자원에 경쟁 상태가 일어나지 않게 한다.

• Immutable object

객체 자체를 생성 한 이후에 수정할 수 없도록 만든다. 읽기 전용 데이터만 공유될 수 있다.

2. 공유 상태를 피할 수 없는 상황에서 동기화를 사용하는 방법

• Mutual exclusion

특정 순간의 임계영역에 대한 접근은 한 쓰레드에서만 가능하도록 한다. 한 쓰레드가 임계영역을 접근하고 있는 동안은 다른 쓰레드는 임계영역에 접근할 수 없다. Deadlock 또는 Starvation이 일어나지 않도록 고려되어야 한다.

• Atomic operation

공유 데이터와 관련된 작업을 Atomic 하게 구현한다. 작업이 원자적이기 때문에 공유 데이터는 멀티쓰레딩 환경에서 일관성을 유지할 수 있다.

Thread safety - Wikipedia

Thread-safe in C on Linux

C 표준에는 thread-safe에 대한 개념이 없어 사용자의 구현에 의존적이다. C 표준에서 스레드에 대한 언급이 없는 이유는 멀티스레딩이 존재하지 않는 임베디드 시스템 때문이다.

GNU(glibc)에서는 대부분의 FILE*를 다루는 stdio의 고수준의 함수는 thread-safe하다. (printf, scanf..)

반면, write()와 같은 저수준 입출력 함수는 thread-safe 하게 구현되어야 한다.

stdout thread-safe in C on Linux?

Thread-safe C library functions

Documentation - Arm Developer

C library functions that are not thread-safe

Documentation - Arm Developer