STL은 일반적으로 많이 사용되는 자료구조와 알고리즘을 모은 표준 템플릿 라이브러리입니다.
STL은 반복자, 알고리즘, 함수자, 컨테이너라고 불리는 네 가지의 구성 요소를 제공합니다.
Template 과 Generic Programming
데이터 형식에 의존하지 않고, 하나의 값이 여러 다른 데이터 타입들을 가질 수 있도록 하여 코드의 재사용성 및 다형성의 이점을 얻을 수 있는 프로그래밍 기법입니다.
Template
Template 은 C++ 에서 Generic Programming 기법을 사용할 수 있는 기능입니다.
STL 반복자 ( iterator )
STL 은 일관적으로 STL 컨테이너를 접근할 수 있는 iterator 라고 불리는 반복자를 제공합니다.
iterator 를 사용하는 이유
iterator 를 통해서 STL이 제공하는 컨테이너를 일관적인 방법으로 접근할 수 있습니다.
STL 알고리즘
STL 은 min_elementPermalink ( 최솟값 ), max_elementPermalink ( 최댓값 ), sort ( 정렬 ), find ( 요소 찾기 ), erase ( 요소 삭제 ) 등의 STL 컨테이너를 대상으로 사용할 수 있는 알고리즘 함수들을 제공합니다.
STL 함수자 ( functor )
STL은 plus, minus, multiplies, divides 와 같은 산술 연산 함수자 그리고 equal_to, not_equal_to, greater, less 등과 같은 비교 연산 함수자를 제공합니다.
사용 예시
priority_queue<int, vector<int>, greater<int>> pq; 와 같이 사용해서 낮은 숫자가 가장 먼저 pop 될 수 있도록 할 수 있습니다.
STL 컨테이너
STL은 시퀀스, 연관, 어뎁터 컨테이너를 제공합니다.
시퀀스 컨테이너
시퀀스 컨테이너는 데이터를 선형을 저장하고 관리하는 형태의 컨테이너를 말합니다.
list, vector, deque, forward_list, array 등이 있습니다.
어뎁터 컨테이너
기존 컨테이너를 랩핑하여 스택과 큐 같은 인터페이스의 제한을 둔 컨테이너를 말합니다.
stack, queue, priority_queue 등이 있습니다.
연관 컨테이너
key 와 value 를 묶어 데이터를 하나의 쌍으로 저장하는 컨테이너를 말합니다.
map, multimap, set, multiset, unordered_map, unordered_multimap, unordered_set, unordered_multiset 등이 있습니다.
컴퓨터 구조 지식은 크게 컴퓨터가 이해하는 정보, 컴퓨터의 네 가지 핵심 부품 두 가지로 분류할 수 있습니다.
컴퓨터가 이해하는 정보
컴퓨터는 전류의 흐름 여부에 따라서 0과 1로 구분하고, 이를 통해 얻게된 0과 1 정보를 해석하여 처리합니다.
정보의 종류
컴퓨터가 이해하는 정보의 종류에는 데이터와 명령어가 있습니다.
데이터 ( Data )
숫자, 문자, 이미지, 동영상과 같은 정적인 정보를 가리켜 데이터 ( Data ) 라고 합니다.
명령어 ( Instruction )
컴퓨터에게 명령하여 데이터 읽기, 쓰기를 통해서 조작하도록 요청하는 정보를 명령어 ( Instruction ) 이라고 합니다.
컴퓨터의 네 가지 핵심 부품
컴퓨터의 핵심 부품은 CPU ( Central Processing Unit ), 주기억장치 ( Main Memory ), 보조기억장치 ( Secondary Storage ), 입출력장치 ( Input/Output device ) 정도로 정리할 수 있습니다.
CPU ( Central Processing Unit )
CPU 는 컴퓨터의 두뇌역할로서 메모리에 저장된 명령어를 Fetch하고 Decode 하고 Excute 하는 부품입니다. CPU 의 핵심 구성요소로는 CU( Control Unit ),산술논리연산창지( Arithmetic Logic Unit ), 레지스터 ( Register )가 있습니다.
CU ( Control Unit )
CU는 명령어를 Decode 하고 Decode한 명령어를 통해 제어 신호를 보내 ALU에게 어떤 연산을 하거나 메모리에 저장된 데이터를 읽거나 쓰기 명령을 할 수 있습니다.
산술논리연산장치 ( Arithmetic Logic Unit )
CU에서 Decode한 연산 명령어를 Excute 하는 역할을 하는 부품입니다.
레지스터 ( Register )
CPU가 연산에 필요한 데이터, 주소, 매개변수( 함수 호출 규약에 따라 다름 ), 스택 프레임 등을 임시로 저장하는 가장 빠른 저장 장치입니다.
주기억장치 ( Main Memory )
주기억장치는 현재 실핼되는 프로그램의 명령어와 데이터를 저장하는 역할을 합니다.
보조기억장치 ( Secondary Storage )
주기억장치는 전원이 꺼질 경우 모든 데이터를 잃지만 보조기억장치는 전원이 꺼져도 저장된 데이터를 유지합니다. 주기억장치보다는 용량대비 저렴하지만 상대적으로 느립니다.
페이징 파일
페이징 파일을 이용해서 주기억장치의 부족한 용량을 보조역할을 할 수 있습니다.
입출력장치 ( Input/Output device )
입출력장치는 마이크, 스피커, 마우스, 키보드처럼 컴퓨터 외부에 연결되어 컴퓨터 내부와 정보를 교환하는 장치를 말합니다.
메인보드( Main board ) 와 시스템 버스 ( System bus )
컴퓨터의 핵심 부품들은 모두 메인 보드( 혹은 Mother board 라 불림 ) 라는 판에 연결됩니다. 즉 메인보드에 연결된 부품들은 메인 보드의 버스라는 통로를 이용해서 서로 정보를 주고받습니다. 여러 버스 가운데 컴퓨터의 네 가지 핵심 부품을 연결하는 가장 중요한 버스는 시스템( System bus ) 입니다.
컨텍스트 스위칭은 현재 수행중인 쓰레드의 레지지스터 상태를 TCB에 있는 레지스터 데이터 블럭에 백업하고 스케줄러에 의해서 퀀텀 타임을 할당받은 쓰레드의 레지스터 상태 값을 CPU 코어에 업로드하는 일련의 과정을 말합니다.
컨텍스트 스위칭은 최대한 적게 발생되는 것이 좋습니다. 유저 모드에서 커널 모드로 전환되고 레지스터 상태 값을 백업하고 다시 업로드 하는 과정으로 인해 오버헤드가 발생되어 성능 하락의 원인이 되기 때문입니다.
컨테스트 스위칭의 종류
컨텍스트 스위칭의 종류로는 쓰레드 컨텍스트 스위칭과 프로세스 컨텍스트 스위칭이 있습니다.
쓰레드 컨텍스트 스위칭 ( Thread Context Switching ) 이란?
동일한 프로세스 내부에 있는 쓰레드간의 컨텍스트 스위칭 ( Context Switching ) 을 의미합니다.
프로세스 컨텍스트 스위칭 ( Process Context Switching ) 이란?
서로 다른 프로세스 내부에 있는 쓰레드간의 컨텍스트 스위칭 ( Context Switching ) 을 의미합니다.
쓰레드 컨텍스트 스위칭 vs 프로세스 컨텍스트 스위칭 성능 차이
프로세스마다 독립적인 주소 공간을 사용하기 때문에 다른 프로세스에 있는 쓰레드 간의 컨텍스트 스위칭이 발생될 경우 그전에 수행하던 쓰레드가 캐시와 TLB( Translation Lookaside Buffer ) 에 적재하였던 데이터는 사용하지 못하기 때문에 캐시 hit율과 TLB ( Translation Lookaside Buffer )hit율이 떨어져 프로세스 컨텍스트 스위칭보다는 쓰레드 컨텍스트 스위칭이 오버헤드가 상대적으로 적습니다.
자신의 퀀텀타임을 포기하지 않고 무한 루프를 통해 자원에 대한 배타적인 접근을 시도하는 방식의 락을 말한다.
스핀 락 ( Spin Lock ) 코드
bool isUse = false;
// 접근 시도
while ((bool)InterlockedExchange8((char*)&isUse, false) == true)
{
YieldProcessor();
}
// 대입은 원자적으로 이루어지기 때문에 Interlocked 함수를 사용하지 않는다.
isUse = false;
InterlockedExchange() 함수를 이용해서 원자적으로 isUse 의 값을 확인하면서 true로 값을 셋팅하여 무한 루프를 통해 배타적인 접근을 시도한다.
YieldProcessor() vs SwitchToThread() vs Sleep(0)
배타적인 접근에 실패하였을 때 YieldProcessor(), SwitchToThread(), Sleep(0) 중 하나를 호출하여 다른 쓰레드가 실행될 수 있는 기회를 줄 수 있다.
YieldProcessor()
하이퍼 쓰레드를 지원하는 CPU를 사용하는 머신에서 YieldProcessor()를 호출하였을 때, YieldProcessor()를 호출한 쓰레드가 실행되고 있는 물리 코어에 속해있는 논리 코어에게 실행을 양보한다.
SwitchToThread()
SwitchToThread()를 호출하였을 때 우선순위가 낮아 일정시간 동안 퀀텀 타임을 할당받지 못한 쓰레드에게 수행될 기회를 제공한다.
Sleep(0)
Sleep(0) 을 호출하였을 때 현재 퀀텀 타임을 포기하고 블락 큐에 인큐되지만, 자신 보다 우선순위가 같거나 높은 쓰레드가 없다면은 운영체제에 의해서 다시 퀀텀 타임을 할당받아 수행된다.
스핀 락 ( Spin Lock )의 장.단점
장점
자신의 퀀텀 타임 이내에 배타적인 접근에 성공하였다면, 동기화 객체를 사용함으로서 발생될 수 있는 커널 모드로의 전환 및 컨택스트 스위칭으로 발생되는 오버헤드를 줄여 그만큼 성능에서 이점을 얻을 수 있다.
단점
자신의 퀀텀 타임 이내에 배타적인 접근에 실패하였다면, 다른 쓰레드가 운영체제로부터 퀀텀 타임을 할당받아 수행될 수 있는 기회를 주지 못했기 때문에 전체적인 쓰레드 처리량이 떨어진다.
