대엉코딩

1. 멀티 프로세스

- 각각의 프로세스들은 독립적이므로, 하나의 프로세스가 죽더라도 다른 프로세스에는 영향을 끼치지 않는다.

- 하지만 멀티 스레드에 비해 더 많은 메모리공간과 컨텍스트 스위치로 인한 시간을 많이 차지한다.

- 여러개의 프로세스가 필요한 작업을 하나의 프로세스내의 여러개의 스레드로 나눠 수행하면 메모리 공간과 시스템 자 원소모, 실행시간을 줄일 수 있다.

2. 멀티스레드

- 멀티프로세스에 비해 적은 메모리공간 차지, 컨텍스트 스위치가 빠름

- 하나의 스레드에 문제가 발생하면, 다른 스레드들도 영향을 받을 수 있다.

- 스레드간의 통신은 별도의 자원을 이용하지 않고, 전역변수나 힙 영역을 이용해서 데이터를 주고 받을 수 있다

   ( 스택은 각각 가지지만, 힙 공간은 공유함)

- 이 점은 문제가 되기도 한다.... 멀티 프로세스는 프로세스간 공유하는 자원이 없으므로 동일한 자원에 동시에 접근하지 않지만, 멀티 스레드는 서로 다른 스레드가 데이터와 힙 영역을 공유하기 때문에 잘못 수정하거나, 예상치 못한 값으로 수정되는 경우가 발생할 수 있어서 동기화 작업이 필요하다.

- 작업 순서와 공유자원 처리에 대해 신경써야 한다. 이 과정에서 병목현상으로 인한 성능 저하가 나타날 수 있다. 

1. 힙 메모리를 사용하는 이유?

- 위의 그림에서 보듯이 heap의 공간과 stack 의 공간에 나누어져 있습니다.

- 그리고 stack메모리의 경우 사용되는 양은 런타임시 결정이 되지만 스택메모리의 최대 공간 (사용가능한) 은 컴파일 시

  이미 지정이 됩니다.

- 왜 스택공간이 있는데 굳이 힙 메모리를 사용해야 하는가 ? 에 대한 궁금증이 떠오르게 됩니다.

- 제가 경험해보고 아는 선에서 몇가지만 이야기해보겠습니다.

-- (1) dynamic (동적할당)

         알고리즘 문제를 풀 때 처럼 입력의 최대값이 정해져 있는경우 그 최대치로 메모리 공간을 할당해서 컴파일 시간

         에 결정을 해서 스택메모리를 사용할 수도 있지만 (큰 사이즈의 경우 다음에 언급), 만약 사용자에 입력에 의해서 

         공간의 변동이 정해지는 경우 개발자 입장에서 미리 그 크기를 예측할 수 없으므로 런타임 시간에 변동에 맞게 

         메모리를 할당해야하는 경우 입니다.

-- (2) size 문제 (엄청 큰)

         이전 게시글에서 언급했다싶이 stack memory의 경우 최대 사이즈가 미리 정해지는 만큼 엄청 큰 사이즈가 필요

         할 경우 stack overflow가 발생할 수 있습니다. 이 때 스택에는 주소를 가리키는 포인터만 설정해주고, heap 메모

         리 공간에 큰 사이즈를 선언해서 가리키게끔 할 수 있습니다.

-- (3) 스택메모리의 life cycle

         스택 메모리의 경우 stack frame단위로 쌓이게 되는데 그 함수가 끝날경우 (life cycle)이 끝날 경우, 스택 메모리에

         서 해제됩니다. 이 경우에도 어떤 데이터를 유지하고 싶을 때는 힙 메모리 공간을 사용합니다. (직접 해제 해주기 

         전 까지 힙 영역에 저장하고 있는 데이터는 사라지지 않으므로)

2. 힙 메모리 사용 in C++

- stack 메모리 대신 heap 메모리를 사용하는 경우는 필요한 용량이 매우 크다던지, dynamic(동적)으로 런타임 시간에

   결정이 되는 변수를 사용한다던지 할 때인데요

- C++에서는 new를 통해서 힙에 공간을 할당 받고 스택 메모리에서의 포인터 변수가 이를 가리키도록 합니다.

- new를 통해서 할당을 받을경우 반드시 까먹지말고 delete을 해주어야만 메모리 leak을 막을 수 있습니다.

- new이외에도 unique_ptr 을 사용한다던지, 배열의 경우 vector를 사용하여 힙에 선언을 해준다면

- 메모리 해제 과정을 신경쓰지 않아도 되게끔 좀 더 안전하게 사용하실 수도 있습니다. 하지만 new를 사용하신다면

- 까먹지말고 반드시 delete으로 해제를 해주어야 한다는 점.!

3. stack 메모리 사용할 때와 heap 메모리 사용할 때의 차이점(장단점?)

- 우선 stack에 선언할 경우 속도가 더 빠릅니다.

- heap의 경우 원하는 만큼의 공간의 힙메모리상에서 찾고 할당하고 나중에는 이를 해제해야 하므로 상대적으로 시간이

- 많이 소요됩니다.

- 그럼에도 heap에는 큰 용량을 필요로 하는 변수라던지, 동적으로 결정이 되는 변수일 때 사용이 가능합니다.

- 그러므로 큰 사이즈가 아닌 경우 (100kb 미만? 정도?) 정도는 속도가 빠른 스택메모리를 사용하는 것이 좋습니다.

- 또 다른 차이점은 스택메모리의 경우 여러번수를 선언하고 주소를 찍어보시면 아시겠지만,

- 빽빽하게?? a가 4바이트를 차지하고, b가 4바이트를 차지한다면 메모리 주소도 4바이트(32bits) 차이가 납니다.

                   (물론 연속되게 위치하고 있을 경우를 가정)

- 중간에 빈 공간없이 빽빽하게 차지하지만, 힙의 경우 구멍이 송송뚤린 것 처럼 사이에 공간이 있습니다.

- 스택처럼 빡빡하게 메모리를 채우지는 않습니다.

1. constuct Heap

 - heap sort를 위해서는 일단 입력으로 들어온 배열을 heap의 조건을 만족 하도록 만들어 줘야한다. (구조,순서)

 - 중요한 것이 있는데 heap의 구조조건은 full binary tree 이기 때문에 사실 입력(배열) 자체가 구조조건을

   만족한다.

 - 그럼 우리는 순서 조건만 맞춰서 힙을 구성하면 된다 ! 어떻게 할 것인가? 

 -밑에 자식쪽의 서브트리는 heap조건을 만족 할 때 위와 같이 하나의 노드를 삽입하면

 -순서조건이 check 되지 않은 노드는 단 하나뿐이다. --> 이 노드에 대해서 fixheap을 수행 하면

 n+1짜리의 heap이 완성 된다. (이 과정은 O(logn) -->하나의 원소를 heap에 삽입하는))

 - 이 아이디어로 밑에서부터 heap을 구성해 나가는 것이다.

2. Analysis

 - 이제 힙을 구성하고 sort 하는 것 까지 알아보았다 .... 성능 분석을 해보자 !

 - 먼저 heap construction 부분에서 짚어보자.

- 언제가 최악의 경우? (Worst case) ---> construct힙을 하는데 계속 그 노드의 위치가 leaf노드 일 때 이다

  (끝까지 내려갈 때) 

- 각 노드가 삽입 될 때 (heap을 구성하기 위해) 자신의 자리를 찾아 갈 때 규칙을 한번은 오른쪽으로 내려가고

   그 이후에는 쭉 왼쪽으로 내려간다고 하자.

 - 저렇게 내려갈 경우 힙을 다 구성 했을 때 leaf노드로 내려간 간선이 겹쳐지는 일이 없다 !

    (서로 다른색이 지나갈 때 지나간 간선을 다른 노드가 지나갈 때 그 간선을 지나가는 일이 없다)

 - construct heap 과정에서 하는 총 비교연산의 수 <= 2(비교연산) * n-1(간선의 수) ---> O(n)

 - heap sort의 최악의 경우 --->  O(2nlogn)  (sort)   +   O(n) (힙 구성)  -->  O(nlogn) 이다

 - 대소비교 연산을 이용한 sorting의 경우 O(nlogn)보다 빠를 수는 없으므로 optimal 이라고 할 수 있다.

3. Accelerate Heapsort (BubbleUpHeap)

-- > heap sorting  과정에서 fixheap을 할 때 각 단계에서 노드는 두번의 비교연산을 수행했었다.

      ( 둘 중의 누가 더 큰 자식인가 )  +  (본인과 더 큰 자식과의 비교)

- 이렇게 매번 내려갈 때 마다 두번의 비교연산을 하지 말고 한번 (둘 중의 누가 더 큰 자식인가)

   만 비교하고 무조건 그 큰 자식 쪽으로 내려간다 ( 언제까지? h/2 즉 절반정도 내려올 때 까지 )

- h/2 정도 까지 내려왔을 때 부모 노드와 비교연산을 한번 실시한다..!

- 1) 부모노드가 더 크다면? (조건만족) -->다시 나머지 h/2에 대해서 recursive 하게 다시 수행

      --> 다음엔 h/4만큼 가고 다시 비교하고...또 reculsive....!

  2) 부모노드가 작다?? --> 너무 많이 내려왔다....비교를 통해 다시 위로 올라가 내 자리를 찾아간다.

3-1 Accelerate Heapsort Analysis

 - 연산의 수를 살펴보자 (최악의 경우)

 - h/2 (이만큼 한번의 연산을 통해 내려온다) + 1(부모노드와 비교) + h/4 (다시 진행) +1 ......

   <= h (h/2+h/4+.......) + logh (1+1+...... --->log 높이)  라고 할 수 있겠다 

 - h= logn 이다 즉 . 이 방법을 통해 서 우리는

 - worst case가 nlogn+Θ(nloglogn) 임을 알 수 있다.

 -점근 분석을 하면 최악의 경우는 앞에서 본 힙소트(O(2nlogn)) 과 O(nlogn+nloglogn) 모두 O(nlogn) 이지만

 - 비교 연산의 수는 절반 정도 줄여서 성능을 향상 시킬수 있다고 생각할 수 있다.

 # 메모리 영역의 구성

메모리 영역은 위와 같이 구성되는데 "가상 메모리의 구성" 이다.

스택 영역은 주로 지역변수, 매개변수, 함수의 반환값, 함수 호출의 주소 등이 저장된다.

힙영역은 주로 동적 할당을 할 때 사용되는 영역인데 다들 잘 알듯이

c++에서 new, delete이 c 에서 malloc, free 등이 있는데 동적 할당을 하고 사용을 했으면 해제 하는것에도 주의를

기울여 주어야 할것이다. 

# 다른 영역의 메모리를 사용할 때의 속도의 차이는 어떻게 될까?

- 이를 한번 알아보도록 하자.!

- 배열은  int 형으로 크기는 10000

- 충분한 횟수의 함수 호출(1000001)

-#include<time.h> , clock_t 를 이용한 시간 계산

 1. 배열을 정적영역에 선언해서 할당 받는 함수.

 2. 배열을 스택영역에 선언해서 할당 받는 함수.

 3. 배열을 힙영역에 선언해서 할당 받는 함수.

코드의 이해는 어렵지 않을 것이다. 다음과 같다.

결과는 어떻게 될까?.....

<결과화면>

위와 같다. 시간 자체 값은 변경될수 있지만

비교를 해보면 

정적영역에 선언   <   스택영역에 선언  <  힙영역에 선언

순이다.

동적할당의 경우

-컴퓨터의 저장소는 <  레지스터 / 캐쉬 L1 / 캐쉬 L2  /  memory / HDD >

 순으로 왼쪽에 있는 저장장치 일수록 속도가 빠르고 용량이 작으며 용량당 가격이 비싸다.

오른쪽으로 갈수록 느리지만 용량이 크고 값이 싸다

그래서 OS에게 요청해서 memory allocation 은 memory에서 일어나므로 느릴수 밖에 없다.

일반적인 힙 성능 문제들이 있다.

- 할당 작업으로 인한 속도 저하

        만약 사용가능한 블록이 사용가능 목록에 없다면 런타임에 더 큰 블록을 찾거나 새블록을 할당 받아와야한다.

- 해체 작업으로 인한 속도저하

- 힙 경합으로 인한 속도 저하 

        두개이상의 쓰레드가 접근 하려고 하는 경우 한 쪽 작업이 완료되어야 접근가능

-힙 손상으로 인한 속도 저하

알고 싶었던 내용과 그러한 현상이 나타난 이유를 기재 해보았습니다.

틀린 부분이 있을 수 있습니다. 알려주시면 수정하겠습니다. !