어느 게임 개발자의 기록

CPU는 컴퓨터를 구성하는 하드웨어중에서 가장 빠른 작업 처리 속도를 가지고 있다. 반면, 메인 메모리는 CPU에 비해 매우 낮은 작업 처리 속도를 가지고 있다.

두 하드웨어간의 속도 차이 때문에, CPU에서 메인 메모리에 직업 접근을 하게 되면 CPU에선 병목 현상이 발생하게 된다.

메인 메모리에 접근하여 데이터를 얻어오는 작은 작업의 시간이 CPU에선 수도 없이 많은 명령어를 처리할 수 있는 시간이기 때문이다.

이를 해결하기 위해 존재하는 것이 캐시메모리이다.

캐시 메모리

CPU는 필요한 데이터를 가져오기 위해서 메인 메모리에 접근을 할 수 밖에 없다. 하지만, 그 횟수를 최소화하기 위해 캐시 메모리를 사용하게 된다. CPU에서 메모리의 특정 주소에 접근하게 되면 그 주소를 시작으로 일정 크기만큼의 데이터를 한 번에 가져와 캐시 메모리에 저장하게 된다.

캐시 메모리는 메인 메모리에 비해 속력이 매우 빠르기 때문에, CPU에선 캐시 메모리에서 데이터를 탐색하는 것이 훨씬 효율적이기 때문이다.

하지만, 캐시 메모리는 메인 메모리에 비해 용량이 매우 작기 때문에 필요한 데이터가 캐시 메모리에 없을 경우 CPU는 다시 메인 메모리에 접근하여 캐시 메모리의 데이터를 새로 갱신하게 된다. 위에서 말했듯이, 메인 메모리에 접근하는 것은 성능상 손해가 크기 때문에 최소화하는 것이 좋다. 그렇다면, 캐시 메모리에 원하는 데이터가 최대한 많이 있을수록 메인 메모리에 접근하는 횟수가 적어질 것이며 성능의 손해를 최소화할 수 있을 것이다.

이 것을 캐시 적중률이라고 한다.

캐시 적중률

캐시 메모리에 현재 A,B,C,D,E,F 이렇게 6개의 데이터가 있다고 해보자.

CPU에서 A, B, C, X 이렇게 4개의 데이터를 필요로 한다면, A,B,C는 캐시 메모리에서 찾을 수 있지만, X의 경우엔 캐시 메모리에서 찾을 수가 없다.

이 경우, A,B,C 의 경우 캐시 적중이라고 표현하며, X에 대해선 캐시 미스(miss)라고 표현하게 된다.

캐시 적중이 얼마나 많이 발생하는가를 캐시 적중률이라고 표현하는 것이다.

그렇다면, 캐시 미스가 최대한 적게 발생해야 메인 메모리에 접근해서 캐시 메모리를 새로 채우는 과정이 적게 발생할 것이며 성능상 손해가 적게 될 것이다. 즉, 캐시 적중률이 높을수록 성능상 손해를 적게 보고 있다고 말할 수 있는 것이다.

그렇다면, 캐시 적중률을 높이기 위해선 어떻게 해야할까?

캐시 적중률을 높이는 법

방법은 간단하다. 관련된 데이터를 메모리에 연속적으로 위치하게 하면 된다. 캐시 메모리를 채우는 방식은 CPU가 메인 메모리에 접근한 주소를 시작으로 특정 크기만큼 연속적으로 가져오는 방식이기 때문이다.

예를 들어, 특정 자료구조의 원소를 순회한다고 해보자. 1번째 원소와 2번째 원소가 메모리 상에서 먼 위치에 있다면, 각 원소에 접근할 때마다 캐시를 새로 채워야 하는 상황이 발생할 수 있다. 반면, 모든 원소가 순차적으로 붙어있다면 자료구조의 원소가 캐시 메모리에 존재할 가능성이 매우 높아지며, 캐시 적중률을 최대로 높일 수 있는 것이다.

이 때문에 배열과 리스트의 성능 차이가 발생한다. 배열은 그 구조상 모든 데이터가 메모리에 연속적으로 위치하게 되지만, 리스트의 경우 모든 원소가 동적으로 할당되어 포인터로 연결되어 있기 때문에 메모리의 다양한 위치에 분산되어 있다. 그렇기 때문에, 동일한 시간 복잡도의 연산이라도 배열 기반의 자료구조가 포인터 기반의 자료구조보다 일반적으로 우수한 성능을 보이게 된다.

배열 뿐만이 아니라 메모리 풀링 또한 캐시 적중률을 높이는데 도움이 될 수 있다. 미리 메모리를 할당해놓고 필요한 만큼 가져다 쓰는 방식이기 때문에, 모든 데이터가 메모리 상에 연속적으로 위치하게 된다. 메모리 풀링은 캐시 적중률을 높일 뿐만 아니라 메모리 외부 단편화를 해결하는 데도 큰 도움이 되기 때문에 잘 활용하면 성능상 큰 이점을 얻을 수 있을 것이다.

본인은 현재 8GB의 DRAM을 2개 장착하여 사용하고 있다.

총 16GB의 메인메모리 용량이 확보된 것이다.

언리얼 엔진을 켜고 게임을 만들다 보면 이게 16GB안에 다 들어간다고? 싶을 때가 많다.

언리얼 엔진 하나만 해도 메모리 사용량이 엄청난데, 그 와중에 게임도 구동을 해야한다. 심지어 본인은 노래를 켜고 인터넷 검색을 하거나 동영상을 틀어놓고 하기도 한다. 어쩔 땐, 예제 프로젝트를 참고하기 위해 2~3개의 언리얼 엔진 프로젝트를 켜고 작업하기도 한다. 

상식적으로 생각했을 땐, 16GB라는 메모리의 용량은 턱없이 부족할 것 같다는 생각이 들었다. 물론, 실제로도 부족하다.

부족한데 어떻게 그 모든 프로그램들을 실행하고 감당할 수 있는 것일까?

이는 가상메모리라는 기술 덕분이다.

가상 메모리

가상 메모리의 아이디어는 이렇다. 

4GB짜리 프로세스를 메모리에 올리더라도, 한 번에 사용되는 공간은 4GB가 되지 않을텐데 그러면 사용되고 있는 만큼만 메모리에 나누어서 올리면 되지 않을까? 

프로세스가 전체적으로 필요한 용량은 4GB라고 하더라도, 동시에 4G가 모두 사용되지는 않는다. 그러므로 지금 당장 사용되는 만큼만 메모리에 적재하고 나머지는 적재하지 말자는 개념으로 시작된 것이 가상 메모리이다.

하지만 프로세스는 실행되는 순간부터 모든 정보가 어딘가에는 저장이 되어 있어야 한다. 메모리에 저장을 안할거면 어디다가 할까?

바로 보조 기억 장치이다. HDD, SDD와 같은 저장 장치의 도움을 받아 가상 메모리를 구현하게 된다.

모든 정보를 일단 보조 기억 장치에 적재해둔 뒤, 지금 당장 필요한 부분만 꺼내서 메인 메모리에 적재하고 사용되지 않게 되면 다시 보조 기억 장치로 적재하는 방식인 것이다.

그렇다면, 어떤 방식으로 보조 기억 장치와 메모리 사이에서 정보를 옮기는 것일까?

가상 메모리를 실현하는 방법은 페이징, 세그멘테이션 2가지의 기법이 있다.

페이징

먼저 프로세스와 메인 메모리를 동일한 크기로 조각을 낸다.

예를 들어, 1byte로 쪼갠다고 한다면, 하나의 페이지는  하나의 프레임에 저장될 수 있을 것이다.

프로세스의 페이지는 각 프로세스마다 0번부터 시작하여 인덱스가 매겨진다.

반면, 메인 메모리는 하나이기 때문에 0번 페이지가 0번 프레임에 매칭되는 것은 아니다.

페이지는 메인 메모리의 어느 프레임으로 매칭이 될 것이며, 해당 정보는 운영 체제가 보유한 페이지 테이블에 저장이 된다.

프로세스 A가 실행되면서, 0번 페이지에 있는 정보와 4번 페이지에 있는 정보다 지금 필요하다고 해보자.

그렇다면, 메인 메모리의 어느 프레임에 0번 페이지와 4번 페이지의 데이터를 적재하게 될 것이다.

위에서 말했듯이, 페이지의 인덱스와 프레임의 번호는 항상 일치하는 것이 아니다. (오히려 일치하지 않는 상황이 더더욱 많다.)

그렇기 때문에, 어떤 프레임에 어떤 페이지가 적재되어 있는지 정보를 저장할 곳이 필요하다.

이 것이 운영 체제가 보유한 페이지 테이블이다.

하지만, 이렇게 쪼개져있고 위치도 계속 왔다갔다 하는 상황이라면, CPU에선 무엇을 기준으로 주소를 인식해야 할까?

프로세스의 시작점을 기준으로 가상주소를 부여하는 것이다.

예를 들어, 메인 메모리의 주소와 동일한 개념으로 보았을 때 페이지 하나에 10개의 주소가 포함되어 있다고 해보자.

그렇다면, 페이지 0에는 0~9번지가 있으며, 페이지 1에는 10~19번지가 있고, 페이지 2에는 20~29번지가 있다고 할 수 있을 것이다.

이처럼 하나의 프로세스의 시작을 0번으로 해서, 주소를 생성해준다. 이렇게 만든 주소가 가상 주소이다.

실제로 메인 메모리에 적재되면, 가상 주소와는 다른 물리 주소를 보유하게 된다. (실제 메모리의 주소)

CPU에선 해당 가상 주소를 기준으로 작업을 처리하게 된다. 예를 들어, 가상주소가 5번지인 데이터가 있다면 메인 메모리의 몇 번지에 적재되어 있든간에 5번지의 데이터를 요구하는 것이다.

가상 주소를 특정 방법을 통 물리주소로 변환하고, 메인메모리에선 해당 물리 주소의 데이터를 CPU에 전달하게 된다.

하지만, 페이징 기법에는 몇 가지 단점이 존재한다.

1. 마지막 페이지에서 내부 단편화가 발생

하나의 프로세스를 동일한 크기로 쪼개는 과정을 거치는 페이징은 프로세스의 크기가 페이지 1개 크기의 배수가 아니라면, 프로세스의 마지막 페이지는 페이지의 크기를 전부 채우지 못한다.

예를 들어, 한 페이지가 10byte라고 가정하고 프로세스 A는 91Byte라고 해보자. 마지막 페이지에선 1Byte만 사용하게 되고, 9Byte만큼의 내부 단편화가 발생하게 된다.

2. 페이지 테이블 크기만큼의 메모리를 추가로 소모해야 함

프로세스의 크기가 클수록, 페이지의 크기가 작을수록 페이지 테이블의 크기는 더욱 커질 것이다. 페이지 테이블은 메인 메모리에 항상 적재되어 있기 때문에 페이지 테이블 크기 만큼의 메모리 공간을 활용할 수 없게 된다.

3. 메모리에 두 번 접근해야 함

메모리에 접근하는 시간은 CPU를 기준으로 보았을 때 매우 느린 시간이다. 이를 커버하기 위해 캐시라는 저장 장치를 활용할 정도로 CPU입장에선 메모리에 최대한 직접 접근하지 않는 것이 좋다. 하지만, 페이징 기법의 경우엔 페이지 테이블에 한 번 접근하여 물리적 주소를 알아낸 후, 실제 물리적 주소에 접근하는 두 번의 과정을 거쳐야 한다. 이는 상당한 오버헤드로 다가올 수 있다.

하지만, 실제로는 이를 해결하기 위해 TLB라는 버퍼를 사용하고 있다. 물론, 문제를 완전히 해결하는 것은 아니고 CPU의 캐시와 동일하게 최근에 사용된 페이지 테이블의 데이터를 가져와서 빠르게 탐색하는 용도로 사용한다. 캐시 미스 발생시 메모리에서 데이터를 다시 복사하는 것처럼, TLB또한 TLB 미스 발생시 메모리에 다시 접근하여 데이터를 가져오는 방식으로 사용된다.

세그멘테이션

세그멘테이션은 페이징과 유사하지만 다른 기법이다.

세그멘테이션 또한 프로세스를 여러개의 조각으로 쪼개는 것은 똑같다. 

하지만, 단순히 동일한 크기로 쪼개는 것이 아니라 논리적 특성을 기준으로 프로세스를 쪼개게 된다. 

예를 들어, 우리가 잘 아는 code, data, heap, stack 또한 일종의 세그멘테이션 기법으로 쪼개진 것이다.

데이터들의 용도나 목적을 기준으로 프로세스를 4개의 조각으로 쪼갠 것이다.

이 외에도 지역변수, 전역변수, 함수, 심볼 등을 기준으로 쪼개기도 한다고 한다.

페이징 기법은 페이지와 프레임의 크기가 동일하기 때문에, 페이지를 그대로 메인 메모리의 프레임에 적재하면 됐지만 세그멘테이션의 경우엔 각 세그먼트의 크기가 고정되어 있지 않기 때문에 메인 메모리를 미리 쪼개놓는 것이 불가능하다.

이러한 이유 때문에 세그멘테이션 기법은 그때 그때 각 세그먼트의 크기만큼 메모리 공간을 할당하게 된다. 

세그멘테이션 또한 페이징 테이블처럼 세그먼트 테이블이 존재한다. 하지만, 조각의 수가 적은만큼 차지하는 용량이 매우 작아서 메인 메모리가 아닌 CPU의 레지스터에 저장된다고 한다. 이로 인해, 주소를 찾을 때 메인 메모리에 단 1번만 접근해도 된다.

세그먼트 테이블은 base와 Limit을 저장한다. A라는 세그먼트가 크기가 1400이라고 해보자. A를 메인 메모리의 1000번지로부터 1400 크기만큼 할당하였다면,  base는 1000이 되고 Limit은 1400이 된다.

세그멘테이션이 언뜻 보면 페이징보다 좋아보이지만 실제론 페이징보다 많이 사용되지 않는다.

이유는 하나의 치명적인 문제점 때문이다.

1. 세그멘테이션 기법은 외부 단편화를 야기한다.

세그멘테이션 기법은 위에서 말했듯이, 필요할 때마다 그 크기만큼 메인 메모리 상에 새로 할당하게 된다. 가변적인 크기로 메모리 상에서 할당과 해제를 반복하다 보면 자연스럽게 외부 단편화가 발생할 수 밖에 없다. 이로 인해 세그멘테이션 기법을 사용시에 메모리가 아주 비효율적으로 사용되는 상황이 잦아, 세그멘테이션 기법을 단독으로 사용하는 것은 선호되지 않는다고 한다.

프로그래밍에선 사용가능한 자원을 최대한 효율적으로 활용하는 것이 매우 중요하다.

하지만, 효율적이지 않게 사용되는 상황은 언제든 발생할 수 있다.

대표적으로 메모리가 비효율적으로 사용되는 상황인 내부 단편화와 외부 단편화에 대해 알아보자.

메모리 내부 단편화

위의 그림을 보자. 전체 할당받은 메모리는 회색 네모칸 만큼이다.

하지만, 정작 실제로 사용하고 있는 것은 주황색 네모칸 만큼밖에 되지 않는다.

이 상황에선, 비어있는 회색 네모칸 만큼 메모리가 낭비되고 있다고 할 수 있다. 

이처럼, 실제로 필요한 것보다 더 많은 메모리를 할당하여 메모리가 낭비되는 상황을 내부 단편화라고 한다.

대표적인 예시를 하나 들어보자.

팝업 스토어를 열었다고 가정해보자. 팝업 스토어에 참가하는 손님을 기록하기 위한 장부로 std::vector를 선언하였다.

손님은 64명정도 올 것으로 예상되었고, 그에 맞게 vector를 64만큼 reserve해주었다.

하지만, 실제로 방문한 손님은 32명밖에 되지 않았다. 벡터에 손님 정보를 모두 기록하여도 할당한 메모리의 절반밖에 사용하지 않는 상황이 되어버린 것이다. 현재 32칸의 메모리가 낭비되고 있고, 내부 단편화가 발생하였다고 할 수 있다.

메모리 외부 단편화

이렇게 총 10바이트의 메모리 공간이 있고, 위와 같이 할당이 되어있다고 해보자.

여기서, B와 D의 메모리를 할당 해제할 것이다.

이렇게, B와 D가 있던 공간은 비어있는 공간이 될 것이다.

이때, 4byte짜리 E에 대한 메모리를 할당하려고 한다면?

할당할 수가 없다. 분명 메모리 영역에는 2byte짜리 비어있는 공간이 2개 있으므로 총 4byte가 존재함에도 불구하고, E가 사용할 메모리를 할당할 수가 없다. 왜냐하면, 하나의 데이터는 메모리상에 연속적으로 저장되어야 하기 때문이다. 4byte짜리를 반씩 쪼개서 다른 곳에 저장할 수가 없다는 것이다.

이처럼, 메모리의 용량으로 봤을 땐 충분한 공간이 있음에도 불구하고 메모리를 할당하지 못하거나 효율적으로 사용하지 못하는 상황을 외부 단편화라고 한다.

이러한, 단편화 현상들을 해결하기 위해선 페이징, 세그멘테이션 등 여러 기법을 사용하곤 한다.

이는 다른 게시물에서 상세하게 설명하도록 하겠다.

프로그래밍에서 빼놓을 수 없는 키워드가 스레드와 프로세스이다.

각각의 차이점을 알아보자.

개념

프로세스란?

프로세스는 운영체제에서 자원을 할당받는 작업의 단위이다.
어떠한 프로그램이 실행되어 메모리 상에 올라가게 되면, 그 것을 프로세스라고 한다

스레드란?

스레드란 프로세스 내에서 실행하는 작업의 단위이다.
프로세스가 운영체제로부터 할당받은 자원을 실질적으로 이용하는 주체이다.

예시

편의점을 차려서 돈을 벌고자 하는 목적이 있다고 해보자. 그렇다면, 해당 목적을 위해 많은 설계를 해야 할 것이다. 자본 관리부터, 운영 계획을 설계 및 수립할 것이고, 구체적으로는 진열이나 청소, 손님 응대 등에 관한 것도 설계해야 할 것이다. 이러한 모든 설계 계획을 담고 있는 것이 프로그램이다.

그리고, 모든 계획을 마친 뒤 편의점을 실제로 차리는 순간이 왔다고 해보자. 이 때부터 해당 계획은 프로세스가 된다.해당 계획을 실행하기 위해선 먼저 편의점을 운영할 건물이 있어야 한다. 해당 건물을 운영체제로부터 할당받는 자원이라고 생각하면 된다. 편의점을 운영하기 위해선 건물이라는 물리적 공간이 반드시 필요한 것처럼, 프로세스를 실행하기 위해선 물리적인 메모리 공간을 할당받아야 한다.

편의점을 운영하기 시작했다면, 우리가 계획한 것들을 하나씩 실행해야 한다. 계획은 조금씩 쪼갤 수 있을 것이다.

돈을 번다 -> 물건을 판다 -> 물건을 진열한다.

이런 방식으로 작업을 세분화 했다고 해보자.그렇다면, 돈을 벌기 위해선 일단 물건을 진열하는 일을 해야 한다는 것이다.

물건을 진열하는 일처럼 목적을 위해 실행해야 하는 작은 작업들을 실제로 처리하는 주체를 스레드라고 생각하면 된다. (스레드 = 알바생)

게임을 예로 들어본다면, E키를 누르면 총알을 발사하는 과정을 거치기 위해선 키보드의 키 입력을 감지한 뒤, 해당 키 입력이 E와 같은지 확인하고, 투사체를 생성하고, 위치를 이동시킨 뒤, 화면에 렌더링하는 등의 수많은 작은 작업들을 실행해야 한다.이 작은 작업들 하나하나를 실행하는 주체가 스레드인 것이다.

프로세스는 하나의 거대한 목적이며, 스레드는 그 목적을 이루기 위해 세분화된 작업을 실행하는 주체이다.

구체적인 차이

위와 같은 개념의 차이로부터 발생하는 차이점들이 존재한다.

메모리 영역의 차이

이처럼 여러개 개의 프로세스가 동시에 실행된다면, 각 프로세스는 별도의 메모리 영역을 보유하게 된다.

각 영역은 Code, Data, Heap, Stack으로 분류되며 각각의 프로세스는 다른 프로세스의 메모리 영역을 함부로 침범할 수 없다. 프로세스의 영역이 철저히 구분되어 있는 것이다.

반면, 스레드의 경우 Code, Data, Heap 영역을 프로세스 내의 모든 스레드가 공유한다. 각 스레드는 연산을 하기 위해 각각 stack 영역만 할당받을 뿐, Code,Data,Heap에 대해서는 독립적인 영역을 보유하고 있지 않은 것이다.

이 메모리 영역의 차이로 인해 파생되는 차이점들이 많다.

컨텍스트 스위칭 비용

컨텍스트 스위칭이란 CPU에서 실행중인 작업을 변경하는 과정을 의미한다. 프로세스 A를 실행하고 있다가 프로세스 B를 실행하기 위해선, CPU의 레지스터 저장되어 있는 프로세스 A 관련 데이터를 모두 별도의 공간에 저장해놓은 뒤, 프로세스 B와 관련된 데이터를 새로 올려야 한다. 프로세스 단위로 작업을 변경할 때에는 Code, Data, Heap, Stack을 모두 옮겨야 하기 때문에 비용이 매우 비싸다.

반면, 스레드 단위의 컨텍스트 스위칭의 경우엔 Code, Data, Heap은 모두 공유하기 때문에 Stack 영역만 교체해주면 된다. 이로 인해, 상대적으로 컨텍스트 스위칭의 비용이 매우 저렴하다. (하지만 이는 상대적일 뿐, 스레드 간의 컨텍스트 스위칭도 오버헤드의 원인이기 때문에 최소화 하는 전략은 당연히 필요하다.)

동기화 문제

각 프로세스는 서로 간의 메모리 영역을 침범할 수 없기 때문에, 서로가 서로에게 문제를 일으키는 경우는 흔하지 않다. 

반면, 스레드의 경우는 모든 스레드가 Code, Data, Heap영역을 공유한다는 이유로 문제가 발생할 여지가 참 많다.

특정 스레드에서 A라는 변수의 값을 2로 바꾼다면, 다른 모든 스레드에게도 그 변화가 영향을 미칠 것이다. 만약, 어떤 스레드가 프로세스를 종료시켜버린다면? 다른 스레드도 모두 종료되어 버릴 것이다.

특히나 스레드를 여러개 사용하는 경우엔 스레드가 병렬적으로 작업하는 경우가 많은데, 서로의 작업 상황을 고려하지 않고 작업했다간 의도치 않은 문제가 발생할 수도 있다. (1번 스레드에서 해제한 메모리를 2번 스레드에서 참조한다면?)

이처럼, 스레드는 서로가 서로와 밀접하게 연관되어 있기 때문에 스레드를 여러개 사용할 때엔 세심한 주의가 필요하다.

멀티 스레드 환경에선 동기화를 달성하기 위해, lock을 보통 사용하곤 한다.

하지만, lock을 사용하는 경우 오버헤드가 발생하기도 하고 데드락의 문제도 발생할 수 있다.

성능상 이점을 보기 위해 사용하는 것이 멀티 스레딩인데, 오히려 성능을 저하시킨다면 상당히 잘못된 설계라고 할 수 있을 것이다. 이 때문에, lock을 사용하지 않고 프로그램을 설계하고자 하는 것을 lock_free라고 한다.

lock_free를 달성하기 위해 사용되는 알고리즘 중 하나가 CAS이다.

CAS

어떠한 변수의 값을 읽고 쓰는 연산을 할 때, 스레드는 자신의 스택 영역에 해당 변수를 저장하게 된다.

그리고, 스택 영역의 데이터를 기반으로 연산을 진행항 뒤 메인 메모리에 쓰기 작업을 함으로써 작업을 마치게 된다.

하지만, 멀티 스레딩 환경에선 문제가 발생할 수 있다. 스레드의 스택 영역에 저장된 값을 기반으로 연산을 하는 동안 다른 스레드가 메인 메모리의 값을 바꿔버렸다면 결과값이 기대값과 달라질 수 있기 때문이다.

CAS는 이를 탐지한다. 스레드의 스택영역에 저장되어 있는 변수의 값이 메인 메모리에 저장되어 있는 값과 동일한지를 판단한 후, 동일하다면 그 때 쓰기 연산을 실행하는 것이다.

ABA 문제

CAS는 lock_Free를 달성하기 위해 자주 사용되는 방식이지만, ABA 문제를 일으킬 수 있어서 주의가 필요한 알고리즘이라고 한다.

ABA 문제는 그림을 보며 이해해보자.

이런 스택이 있다고 해보자. A,B,C,D 총 4개의 데이터를 가지고 있는 스택이며 top은 A이고 next는 B이다.

이 때, 2개의 스레드가 있다고 해보자.

1번 스레드는 pop() 연산을 1회 진행할 것이며, 2번 스레드는 2번의 pop()과 1번의 push()작업을 진행할 것이다.

2번 스레드가 1번 스레드보다 훨씬 빠른 상황이라고 가정할 것이다.

스레드 1이 pop을 하기 전에, 스레드 2가 모든 작업을 마친다고 한다면, 아래와 같은 순서로 스레드 2는 작업을 할 것이다.

A, B를 pop하였고, 다시 A를 push하여 스택의 원소는 3개이며 top은 그대로 A인 상황이다.

이 때, 1번 스레드에서 작업을 하려고 한다면?

스레드의 스택 영역에 저장되어 있는 top과 메인 메모리의 top이 동일하기 때문에, CAS결과 문제가 없다고 판단하여 pop연산을 진행할 것이다. 하지만, 실제로는 스택 내부의 값이 달라져있다.

스레드 1에선 top()인 A를 pop()하면서 next()인 B를 top()으로 설정할 것이다.

하지만, 메인 메모리에는 B가 존재하지 않는다. 해당 작업이 끝난 뒤, 메인 메모리에서 스택의 top()에 접근하면? 치명적인 오류가 발생할 것이다.

이 것이 ABA 문제이다. 단순히 값이 같냐 다르냐 이것만으로 판단하기엔 위와 같은 문제가 발생할 여지가 있다는 것이다.

ABA 문제를 해결하기 위해, Doble CAS나 Hazard Pointer와 같은 기법을 사용한다고 한다.

해당 기법은 다른 게시물에서 별도로 정리해보아야 할 듯 하다.

 
멀티 스레드 상황에서 한 가지 상황을 가정해보자.

int a = 0;
int b = 0;

void Func()
{
    a = 1;
    b = 2;
}

 
위의 코드에서 Func 함수에 2개의 스레드가 접근하였다고 해보자.
이 때, 스레드에서 관찰될 수 있는 (a, b)의 값은 어떤 경우가 있을까?
 
먼저, a와 b에 아무것도 입력되지 않은 상황인 (0, 0)이 있을 것이다.
a만 입력되고 b는 입력되지 않은 (1, 0) 도 가능할 것이다.
a와 b가 모두 입력된 (1, 2)또한 가능할 것이다.
 
그렇다면, (0, 2)는 가능할까?
 
상식적으로 생각했을 때, 코드는 위에서 아래로 진행되기 때문에 a = 1; 이라는 코드가 실행되지 않았다면, b = 2; 또한 실행될 수 없다.
 
그러므로, a가 0인 상황에서 b에만 2가 입력되는 상황은 발생하지 않을 것만 같다.
하지만, 실제로는 발생할 수 있다.
 
왜냐하면, 컴파일러 최적화 때문이다.
 
Func() 함수를 실행하기 전에, b를 이용한 어떤 연산을 했다고 해보자.
그렇다면, Func에 들어오는 순간 CPU의 캐시에는 b와 관련된 데이터가 있을 것이다.
이 때 Func에서 a = 1; 를 먼저 실행한다면, 캐시를 비워야 하는 상황이 발생할 수도 있다. 그리고 나서, b = 2;을 실행했을 때, b를 다시 캐시에 가져오기 위한 추가적인 작업도 말생할 수 있다.
 
하지만, b =  2;를 먼저 실행한다면? 이미 캐시에 b에 관한 데이터가 있기 때문에, 캐시를 비울 필요 없이 그대로 연산을 할 수 있다. 즉, b = 2;를 먼저 실행하고 a = 1;을 실행하는 것이 결과적으론 훨씬 효율적인 것이다.
 
Func()의 코드는 a = 1;을 먼저 실행하든 b = 2;를 먼저 실행하든 결과에는 차이가 없기 때문에 컴파일러는 최대한 효율적인 방식으로 코드의 순서를 재배치한다.
 
싱글 스레드 환경에선, 결과만 같다면 코드를 아무리 재배치하더라도 별 다른 문제는 발생하지 않을 것이다.
 
하지만, 멀티 스레드 환경에선 다르다.
 
위에서 말했듯이, (a,b)의 값을 (0, 2)로 관측하는 상황도 발생하는 것이다. 그런데 이게 왜 문제라는걸까?
 

int Value = 0;
bool A = false;

void Func1()
{
    Value = 100;
    A = true;
}

void Func2()
{
    if(A == true)
    {
        std::cout << Value;
    }
}

 
위의 코드를 보자. Func1()과 Func2()를 각각 다른 스레드를 이용하여 병렬적으로 실행하였다고 해보자.
 
일반적인 상황이라면, Value = 100;이 된 이후에, A = true가 되기 때문에, Func2()에서는 A가 false라서 아무것도 출력하지 않거나, A가 true인 상황에선 100을 출력할 수도 있을 것이다.
 
하지만, 위에서 말했던 컴파일러 재배치의 문제 때문에,  Func1()에서 A = true; 가 먼저 실행될 수도 있고, 이 경우에 Func2()에선 0을 출력하게 될 것이다.
 
우리가 A == true일 때, Value를 출력하고자 함은 일반적으로 100이라는 값을 출력하기 위함일 것이다.
그런데, 실제로는 0이 출력될 여지가 있는 것이다. 상황에 따라 치명적인 문제가 될 수도 있는 것이다.
 
이처럼, 컴파일러의 명령어 재배치를 통제하기 위한 수단이, std::memory_order 이다.
아무데서나 쓸 수 있는 건 아니고, atomic객체의 함수에 인자로 넣어서 사용할 수 있다.
 
종류는 5가지가 있다.
 
memory_order_relaxed : 명령어의 재배치를 무제한으로 허용함.
memory_order_acquire : 해당 명렁어 위로 명령어가 재배치 되지 않도록 막음.
memory_order_release : 해당 명령어 아래로 명령어가 재배치 되지 않도록 막음.
memory_order_acq_rel  :  memory_order_acquire 와 memory_order_release 를 모두 수행.
memory_order_seq_cst : 어떠한 재배치도 발생하지 않고, 일반적으로 생각하는 논리와 동일하게 명령어가 작동.
 

std::atomic<int> Value = 0;
std::atomic<int> Value2 = 0;

std::atomic<bool> A = false;

void Func1()
{
    Value.store(100);
    A.store(true);
}

 
위에서 보았던 코드를 atomic으로 변경한 코드이다.
위에서도 말했듯이, A에 true를 저장하는 이유는 Func2에서 Value = 100이라는 값을 확인할 수 있도록 하기 위함이었다.
그렇다면, 이 코드에서 Value.store(100); 은 A.store(true); 의 아래로 재배치 되어서는 안된다.

std::atomic<int> Value = 0;
std::atomic<bool> A = false;

void Func1()
{
    Value.store(100);
    A.store(true, std::memory_order_release);
}

 
이 때, A의 두번째 인자에 std::memory_order_release 넣어줌으로서, 명령어가 아래로 재배치되는 것을 막아줄 수 있다.

void Func2()
{
    if(A.load() == true)
    {
        std::cout << Value.load();
    }
    
    Value2.store(100);
}

 
이번엔, Func2()를 보자. 이해를 돕기 위해 아래에 Value2.store(0); 이라는 코드를 추가하였다.
이 코드는 A가 true가 되는 순간 value의 값을 출력한 뒤, Value2의 값을 100으로 변경해주는 작업을 하고 있다.
 
그렇다면, 우리가 의도한 것은 100이 먼저 출력되고, 그 다음에 value2의 값이 100으로 변경되는 것일 것이다.
하지만, 명령어가 재배치 되면 Value2에 100을 먼저 삽입한 뒤, Value의 값을 출력할 수도 있다.
그러므로, Value2.store(100)을 if 문 위로 재배치 되지 않도록 막아주어야 한다.
 
이 때, std::memory_order_acquire를 사용하여 해당 메모리 위로 명령어가 재배치 되지 않도록 막아줄 수 있다.
 
상황의 특성상, std::memory_order_release는 주로 쓰기(store)과 함께 사용되고 std::memory_acquire는 주로 읽기(load)와 함께 사용된다.
 
반면, 읽기와 쓰기를 함께 하는 작업도 존재한다.
바로, fetch_add()함수이다.(fetch_sub() 등 다른 연산도 존재한다.)
 
fetch_add()는 atomic객체에 저장된 값에 원하는 값을 더해주는 함수이다.
더하기를 하기 위해선, 먼저 저장되어 있는 값을 읽고, 그 값에 숫자를 더한 뒤 결과값을 써주어야 한다.
즉, 읽기와 쓰기 연산이 모두 사용되는 것이다.
 
이 경우엔 memory_order_acq_rel 를 사용하여, 아래에 있는 명령어가 위로 배치되지 않도록 하며 동시에 위에 있는 명령어가 아래로 배치되지 않도록 해준다.
 
하지만, 이 경우에도 메모리 재배치가 아예 발생하지 않는 것은 아니다.

void Func3()
{
    int a = 0;
    int b = 0;
    
    Value.fetch_add(3, std::memory_order_acq_rel);
    
    int c = 0;
    int d = 0;
}

 
이 코드에선, a와 b를 선언하는 명령어는 fetch_add의 밑으로 내려가지 않는다.
c와 d의 선언또한 fetch_add 의 위로 올라가지 않는다.
 
하지만, int a = 0; 과 int b = 0;의 순서는 바뀔 수 있고, 아래에서도 int c = 0; 과 int d = 0;의 순서는 얼마든지 바뀔 수 있다.
 
이러한 재배치마저 모두 막아버리고 싶다면, std::memory_order_seq_cst를 사용하면 된다.
참고로 atomic객체의 멤버함수에 인자로 memory_order을 넣지 않는다면 std::memory_order_seq_cst가 디폴트로 설정된다.
 
std::memory_order_seq_cst의 경우엔 생각보다 상당히 비싼 연산이라, 오버헤드가 많이 발생한다고 한다.
하지만, 현대의 amd나 intel의 일반적인 CPU는 순차적 일관성이 거의 보장되어있기 때문에 std::memory_order_seq_cst를 사용한다고 해서 성능에 큰 문제는 없다고 한다.
 
하지만, 임베디드에서 사용되는 ARM CPU의 경우에는 치명적일 수 있기 때문에 주의해서 사용해야 한다고 한다. 

운영체제는 스케줄링을 통해, 여러 프로세스가 효율적으로 실행될 수 있도록 하고 있다.

효율적이지 못한 스케줄링으로 인해 발생할 수 있는 두 가지 문제 (콘보이 효과, 기아 현상)에 대해 알아보자.

만약, 스케줄링이 먼저 들어온 프로세스를 먼저 처리하는 방식이라고 해보자.

숫자는 작업 처리에 소요되는 시간이다.

이 때, 3개의 작업이 대기하는 시간을 구해보자.

첫 번째 프로세스는 0초를 대기한 뒤, 1초동안 작업을 할 것이다.

두 번째 프로세스는 1초간 대기한 뒤, 15초간 작업을 할 것이다.

세 번째 프로세스는 16초간 대기한 뒤, 3초간 작업을 할 것이다.

평균 대기시간은 17 / 3초 (5.66666초)이며, 대기시간 + 작업시간의 평균은 12초이다.

이 번엔, 세 작업의 순서만 바꿔보자.

첫 번째 프로세스는 0초를 대기한 뒤, 15초간 작업을 할 것이다.

두 번째 프로세스는 15초를 대기한 뒤, 3초간 작업을 할 것이다.

세 번째 프로세스는 18초를 대기한 뒤, 1초간 작업할 것이다.

평균 대기시간은 11초이며, 대기시간 + 작업시간의 평균은 52 / 3 초 (17.33333초) 이다.

평균적으로 작업이 처리되는 시간이 기존보다 훨씬 길어진 것을 알 수 있다.

이 것이 콘보이 효과이다.

작업시간이 긴 프로세스를 우선적으로 처리하느라, 작업시간이 짧은 프로세스가 오랜 기간을 대기하며 평균 대기시간이 높아져 비효율적으로 작업하게 되는 것을 콘보이 효과라고 한다.

이를 해결하기 위해선, 짧은 프로세스를 먼저 실행해야 할 것이다.

이렇게 순서를 바꾸니, 평균 대기시간은 4 / 3 초 (1.333초)이며, 대기시간 +작업시간의 평균은 8초가 되었다.

기존보다 훨씬 효율적으로 작업이 실행되는 것을 알 수 있다.

하지만, 이처럼 짧은 프로세스를 우선적으로 실행하기 위해선 계속적인 정렬이 필요하다.

계속적인 정렬 없이 실행하게 되면, 결국 실행시간이 짧은 프로세스가 뒤에 위치하는 순간이 존재하기 떄문에 실행시간을 기준으로 계속적인 정렬이 필요하다.

(실제로는 우선순위 큐를 사용하기 때문에, 정렬이라는 말은 다소 맞지 않을 수도 있다.)

그렇다면, 이런 상황을 보자.

2개의 프로세스를 계속 번갈아가며 반복해서 실행하고자 한다.

A프로세스는 1초면 작업을 완료하고, B프로세스는 2초면 작업을 완료한다.

A와 B를 동시에 실행시킨다면, A가 실행시간이 더 짧기때문에 우선적으로 실행될 것이다.

A가 끝나고, B가 실행될 차례이다. 하지만, 작업 큐에 A가 다시 삽입되는 순간 A의 실행시간이 더 짧기 때문에 A가 앞으로 오도록 정렬될 것이며 A를 다시 실행하게 될 것이다.

A의 작업이 마친 뒤, 다시 B를 실행하고 싶어도 똑같이 A를 실행하게 될 것이다.

즉, 작업 시간을 기준으로 계속적인 정렬을 하다보니 작업시간이 긴 프로세스는 영원히 실행되지 않는 상황이 벌어지는 것이다.

이를 기아현상 (Starvation)이라고 한다.

정리해보자.

콘보이 효과란, 실행시간이 긴 프로세스를 우선적으로 처리하게 되면 다른 프로세스들이 대기하는 기간이 길어져 전체적은 효율이 떨어지는 상황을 의미한다.

기아 현상이란, 실행시간이 짧은 프로세스를 우선적으로 처리하려다 실행시간이 긴 프로세스를 영원히 처리하지 못하는 상황을 의미한다.

기아 현상은 실행 시간을 기준으로 한 스케줄링에서만 문제가 되는 것이 아니라, 어떤 기준이든 우선 순위가 부여된 상황이라면 발생할 수 있는 현상이다. 

이를 해결하기 위한 여러가지 알고리즘 중 라운드 로빈이라는 알고리즘이 있다.

라운드 로빈 알고리즘이란, 어떤 기준이든 우선순위를 두지 않고 정해진 실행 시간에 맞게 모든 프로세스를 균등하게 실행하는 알고리즘이라고 한다.

예를 들어, 작업 시간을 30ms로 설정하였다면 현재 실행중인 프로세스의 작업이 30ms를 초과하는 순간 작업을 강제로 멈추고 대기 큐의 끝으로 밀어넣는다고 한다.

프로세스와 스레드에 관해 공부를 하다보면, 필연적으로 접하는 단어가 동시성과 병렬성이다.

두 단어에 대해 알아보자.

스레드가 1개든 100개든, 코어가 하나라면 한 번에 하나의 작업밖에 처리하지 못한다.

만약, 스레드 1에선 음악을 실행하려 하고, 스레드 2에선 게임을 실행하려 하고, 스레드 3에선 동영상을 실행하려 한다고 했을 때, 일반적으로 생각할 수 있는 상황은 음악 실행을 먼저 하고 음악이 끝난 뒤에 게임을 실행하며, 게임이 끝난 뒤에 동영상을 실행하는 것이다.

하지만 현실에서 컴퓨터는 다르게 작동한다. 싱글코어 CPU를 사용한다고 하더라도, 우리는 게임을 하면서 검색을 할 수 있고, 동시에 음악도 들을 수 있다. 어떻게 그럴 수 있을까?

CPU는 여러 개의 작업을 동시에 실행하기 위해, 매우 고속으로 번갈아가며 작업을 실행한다.

0.001초간 음악을 실행하고, 0.001초간 게임을 실행하고, 0.001초간 동영상을 실행하고.. 이 과정을 초고속으로 번갈아서 하다 보면 우리 눈에는 음악과 게임과 동영상이 동시에 실행되고 있는 것처럼 보이는 것이다.

즉, 실제로는 세가지 작업이 동시에 처리되고 있는 것이 아니라는 것이다.

이 것을 동시성이라고 한다. 

실제로는 동시에 처리되고 있지 않으나, 동시에 처리되고 있는 것처럼 보이는 상황을 동시성이라고 한다.

이번엔 위 그림의 상황을 모자.

코어당 1개의 작업을 처리할 수 있을 때, 코어가 3개라면?

동시에 3개의 작업을 처리할 수 있다.

즉, 음악 실행, 게임 실행, 동영상 실행을 물리적으로 동시에 처리할 수 있다는 것이다.

이 것이 병렬성이다.

실제로 동시에 처리되고 있는 상황을 병렬성이라고 한다.

표로 정리하면 아래와 같다.

물론, 멀티코어 CPU라고 해서 동시성을 사용하지 않는 것은 아니다.

코어가 4개일 때, 8개의 작업이 주어진다면 하나의 코어는 2개 이상의 작업을 해야하는 경우가 발생한다.

이 때, 하나의 코어는 여러 작업을 처리하기 위해 동시성을 사용하게 된다.