Storage Allocation

[MIT OpenCourseWare] Storage Allocation

 

https://youtu.be/nmMUUuXhk2A?si=1fDRy68DNBFxedky

 

Stack Storage

스택 메모리의 기본적인 할당/해제 방식 및 동작 구조 설명.

 

Allocate x bytes

할당량인 x만큼 sp(스택포인터)에 더한 뒤, 할당 전 시작 주소를 리턴.

Free x bytes

할당했던 x만큼 sp에서 빼면됨

 

대부분의 현대 컴파일러는 컴파일 타임에 stackoverflow를 검사하지 않는다. 왜냐하면 현대 컴퓨터에서 스택은 충분히 크기 때문.

따라서 stackoverflow가 발생하더라도 segfault가 발생하고 후에 프로그램을 디버깅을 하면 된다. 따라서 효율성을 위해 stackoverflow를 확인하지 않음.

 

Stack Discipline

함수를 호출하면 지역 변수(local variables)와 레지스터(registers)가 스택에 저장되고, 다른 함수를 호출하는 함수의 리턴 주소도 저장한다. 리턴하게 되면 스택으로부터 위의 것들을 pop하게 된다.

 

1) 스택을 할당하고 해제하는데에는 상수 시간(O(1))이 걸린다.

- sp(스택 포인터)만 조작하면 되기 때문에 매우 효율적 (덧셈 or 뺄셈이므로)

2) stack discipline에 따라 일관적으로 해제해야 한다.

Q) 스택으로 모든 일을 할 수 없는 이유를 아시나요?

A) 스택의 크기가 작아서?

Q) 컴파일 타임 상수를 전달해서 스택 크기를 키울 수도 있다는 사실이 밝혀져있습니다. 사실 스택에는 더 근본적인 한계가 있습니다.

A) 할당한 순서의 역순으로만 해제할 수 있습니다.

3) 따라서, 마지막으로 할당한 것만 해제할 수 있습니다. 사용 중인 스택 영역의 중간에 있는 객체들을 추적하지 않기 때문에, 해제할 방법이 없습니다. 적용 범위는 제한적이지만, 제대로 동작만 한다면 매우 효율적이고 모든 코드를 사실상 인라인으로 작성할 수 있기 때문에 매우 빠릅니다.

4) alloca()라는 컴파일러 명령어를 통해서 stack에 메모리를 할당할 수 있다는 사실도 알려져 있는데요, 이 명령어는 더 이상 사용되지 않으므로(deprecated), 정말 사용하려면 컴파일러에 따라 제대로 동작하는지 확인해야 함.

However, this function is now deprecated, because it turns out that the compiler is actually more efficient when you're dealing with these fixed-size frames if you just allocate a pointer on the stack points to some piece of memory on the heap.

하지만 이 함수는 이제 더 이상 사용되지 않습니다. fixed-size frames을 처리할 때 스택에 포인터를 할당하고, 그 포인터가 힙의 특정 메모리 영역을 가리키도록 하는 것이 컴파일러 효율성 측면에서 더 우수하다는 사실이 밝혀졌기 때문입니다.

 

Q) 그러면 스택이외에 다른 유형의 storage는 뭐가 있을까?

A) Heap.

힙은 훨씬 더 일반적인 개념이지만, 매우 지저분함(messy). 체계적으로 정리하고 효율적으로 동작시키는 것은 매우 어려움. 이제 이번 강의의 나머지를 힙에서 메모리를 관리하는 방법에 대해 설명할 예정.

 

Heap Allocation

C에서는 Heap Allocation을 위해 malloc() / free()를 제공.

C++에서는 이와 유사하게 new / delete를 제공하는데, c와 달리 객체의 생성자 / 소멸자 또한 호출해줌.

Java/Python와 달리 C/C++은 garbage collector를 제공하지 않기 때문에 프로그래머가 직접 메모리를 관리해야 함. C/C++의 성능이 뛰어난 이유 중 하나인데, 백그라운드에서 돌아가는 GC가 없기 때문.

반면에 프로그래머에 의해 할당되는 Heap Storage는 명시적으로 해제되어야 하는데, 이에 따라 memory leak, dangling pointers, double freeing의 문제를 야기함

 

AddressSanitizer, Valgrind같은 memory checkers를 사용함으로써 이러한 악성 버그를 찾는데 도움을 받을 수 있음.

- AddressSanitizer : 컴파일 타임에 플래그를 전달해서 가능한 메모리 버그를 탐지

- Valgrind : 바이너리 파일에서 직접 동작 - 소스 코드를 직접 분석하는 AddressSanitizer보다 동작이 더 느림

 

*heap data structure와 헷갈리지 마세요!

Fixed-Size Allocation

 Bitmap mechanism

각각의 블록에 free 여부에 따라 비트를 할당하여 구분가능

그냥 팁일 뿐이고 Free list에 대한 할당/해제 위주로 알아볼 예정

위 예제에서 x는 free list의 가장 첫번째 포인터를 가리키게 된다.

위 방식을 따르면, 스택처럼 동작하게 되는데, 가장 마지막으로 해제한 것을 가장 먼저 할당하게 되므로 temporal locality를 지니게 된다. 하지만 스택과 달리 모든 블록을 추적할 수 있는 linked-list 구조이므로 모든 블록을 해제할 수 있음.

더군다나 포인터만 조절하면 되기 때문에 할당과 해제에 상수 시간(O(1))이 소요됨.

반면에 외부 단편화(external fragmentation : 사용 중인 메모리 영역이 전체 메모리 공간 곳곳에 흩어져 있음을 의미)로 인해 spatial locality가 떨어지며, page table 크기를 증가시키고 disk trashing을 유발할 수 있으므로 성능적으로 좋지 않음.

 

다시 정리하자면, 가상 메모리의 페이지에 접근할 때마다 logical address를 physical address로 변환하는 작업이 수반되는데, 만약 메모리가 가상 메모리의 여러 페이지에 분산(spread)되어 있다면, 페이지 테이블에 많은 항목(entry)들이 생기게 됨. 왜냐하면 페이지 테이블은 페이지의 logical adress ↔ physical adress간의 매핑을 저장하기 때문. 따라서 페이지 테이블의 복잡성이 증가하고 페이지 테이블내에서 검색(lookup)하는 효율성이 떨어질 수 있음.

더군가나 메인 메모리에 저장할 수 있는 페이지 수보다 더 많은 페이지가 있다면(물리적인 메모리크기 보다 필요한 메모리 크기가 더 많은 상황), 페이지를 디스크에서 넣었다 뺐다(swapping)해야 하므로 disk thrashing을 유발할 수 있음.

+TLB(Translation Lookaside Buffer) 또한 문제가 될 수 있음.

 

Q) TLB 아시는분 있나요?

A) 기본적으로 페이지 테이블에 대한 캐시 역할. logical address를 physical address로 변환한 결과를 캐시. 페이지 테이블을 거치는 것보다 TLB cache hit가 훨씬 효율적임. external fragmentation이 심해지면 액세스할 페이지가 많아지고, TLB에 접근할 때 TLB miss가 발생할 가능성이 높아지게 되는데, 이 경우 페이지 테이블을 탐색하게 된다. external fragmentation이 성능적으로 나쁜 이유가 여기에 해당됨.

Mitigating External Fragmentation

External fragmentation을 완화하기 위한 한 가지 방법으로, 디스크 페이지 별로 사용 가능한 free list or bitmap을 유지하는 것 (페이지별로 free list를 유지하는 것은 이후 Allocation for binned Free Lists에서 다시 언급됨)

 

또한 할당할 때, 최대한 가장 가득 차 있는 페이지(the fullest page)의 free list로부터 할당하자.

즉, 여러 개의 페이지들이 어느정도 차있도록 하면 external fragmentation이 커질 수 밖에 없다. 가능한 하나의 페이지를 가득차도록 할당해서 쓴다면, 사용되는 페이지 개수가 적어질 수 밖에 없고, 이는 external fragmentation의 완화로 이어지게 됨.

블록을 해제할 때는, 그 블록이 원래 속해있던 페이지로 리턴해버리면 됨. 그리고 해당 페이지에서 더 이상 사용되는 항목이 없으면, 가상 메모리 시스템은 프로그램 성능에 영향을 주지 않고 해당 페이지를 page out할 수 있음(디스크로 돌려보낸다는 뜻), 어차피 해당 페이지에 더 이상 접근할 일이 없기 때문.

 

위 90-10 / 50-50을 비교하는 그림을 보면, 하나의 페이지에 가능한 몰아서 할당해야 하는 이유에 대한 직관적인 이해를 도울 수 있다.

2번의 random memory access가 발생했을 때, "동일한 page에 접근할 확률"을 계산해보자.

1) 0.9 x 0.9 + 0.1 x 0.1 = 82%

2) 0.5 x 0.5 + 0.5 x 0.5 = 50%

 

Variable-Size Heap Allocation

방금 학습한 것은 Fixed-Size Heap Allocation인데, 크기가 다른 메모리를 할당해야 하는 많은 프로그램에서는 당연히 이 방식을 사용할 수 없다. 이제 Variable-Size Heap Allocation에 대해 알아보자.

Binned free lists라는 할당 방식에 대해 알아볼건데, 이 아이디어는 free lists의 효율성을 활용하면서도 내부 단편화(internal fragmentation)의 제한적인 양을 감수(accept)하게된다.

 

internal fragmentation

내부 단편화란 블록 내의 낭비되는 공간을  의미. 즉, 실제 사용하는 공간보다 더 많은 공간을 할당하면 그 안에 낭비되는 공간이 생기게 됨.

 

Binned free lists에서는 여러 개의 bin을 만들고, 각 bin에는 특정 크기의 블록을 저장하게 됨.

Bin k holds memory blocks of size 2^k.

Q) 모든 가능한 크기에 대해 bin을 하나씩 저장하면 되지 않을까요? 왜 2의 거듭제곱으로 반올림하면서 저장하는걸까요? 

A) bin이 너무 많아지겠네요.

Q) 네, 모든 가능한 크기에 대한 bin을 만들게 되면 bin이 너무 많아질 것이고 이러한 bin을 가리키는 포인터만으로도 메모리에 저장하기 어려워질 것. 따라서 크기가 2에서 k인 블록만 저장하는 bin만 사용.

 

이제, binned free list에서 x bytes를 할당하는 방법에 대해 알아보자.

 

FYI) ⌈log x⌉ 에서, 밑(base)은 2이고 ⌈ ⌉은 ceiling을 의미한다. 즉, x보다 크거나 같은(작지 않은) 2의 거듭제곱을 의미.

 

x 바이트를 할당하고 싶을 때, 할당 방식은 다음과 같다.

1) k = ⌈log x⌉인 bin이 존재한다면, 해당 블록을 리턴.

2) 그렇지 않으면, 다음으로 더 큰 nonempty bin을 찾아서 필요한 크기로 쪼개서 사용한다. 남은 조각들은 알맞은 bin에 다시 저장한다. 예를 들어보자.

ex) x = 3 => ⌈log x⌉ = 2, Bin 2는 현재 비어있다.

next larger non-empty bin인 Bin 4를 찾았다면, 다음과 같이 쪼개야 한다.

원래 필요했던 Bin 2보다 4배 큰 Bin 4를 쪼개므로, 사용할 Bin 2 크기의 블록 하나 이외에 Bin 2, Bin 3에 해당되는 블록이 1개씩 추가된 것임.

 

만약 더 큰 Bin이 없다면, OS에 메모리 추가를 요청해야 함, 그런 다음 해당 메모리를 확보하면 할당 요청을 충족할 수 있도록 분할하면 된다.

In practice, this exact scheme isn't used, so there are many variants of this scheme. so it turns out that efficiency is very important for small allocations because there's not that much work performed on these small pieces of memory, and the overheads of the storage allocation scheme could cause a performance bottleneck.

실제로는 이와 동일한 방식은 사용되지 않기 때문에 여러 변형이 존재하는데,작은 크기의 메모리 할당에는 수행되는 작업량이 많지 않기 때문에 효율성이 매우 중요하며 저장 공간 할당 방식(storage allocation scheme)의 오버헤드가 성능적으로 병목이 될 수 있음.

따라서 실제로 블록 크기를 1바이트까지 줄이는 경우는 드물고 8바이트 크기 블록에서 멈추는 경우가 많지만, 이렇게 하면 낭비되는 공간이 생겨 internal fragmenation이 약간 증가하게 됨.

*또한 이전에 언급했듯이, 블록들을 페이지별로 그룹화할 수 있는데, 같은 페이지에 있는 모든 블록의 크기가 동일해지므로 블록 크기 정보를 저장할 필요가 없어짐.

(어떤 페이지에는 8바이트 블록만 사용하고, 또 다른 페이지에서는 32바이트 블록만 사용한다는 의미 인듯함? - 다시 말하면, 원래 블록마다 size 정보를 저장하는 필드가 있어야 하는데, 이 방식을 사용하면 size 필드를 블록이 아니라 페이지에 저장해도 되므로 오버헤드가 감소한다 - 아래 Q&A - Q3에서 다시 보충)

 

Q1) 어떻게 ~~ 하시나요?

A) 사용할 수 있는 커맨드가 2개 있는데용, 각각 mmap, sbrk 인데, 이들은 syscall에 해당됨. 호출하기만 하면 OS가 메모리를 더 할당해주고, 그러면 storage allocator가 그 메모리를 사용할 수 있게 됨.

 

Q2) 이런 방식들을 반드시 사용하지 않아도 기능들을 구현할 수 있나요?

A) 아뇨, malloc의 표준 구현 방식에선, 내부적으로 mmap / sbrk를 사용하며 OS로부터 메모리를 할당받게 되는데, 즉 OS가 사용자에게 huge chunk of memory를 제공하게 되므로 더 작은 블록으로 나누거나 하지는 않음. 물어본 내용은 storage allocator가 해야할 일에 해당. 따라서 big chunk of memory를 할당되고, storage allocator가 그것을 더 작은 블록으로 나누게 됨. 더 이상 사용되지 않는 메모리를 OS로 반환하는 유사한 커맨드가 있음 

 

Q3) can you explain the paging thing ~~?

A) 크기가 다른 블록들을 서로 다른 페이지에 저장(keep)할 수 있다는 겁니다. 그러면 각 블록의 크기를 따로 저장할 필요가 없게 됨. 메모리 주소를 얻으면 해당 블록이 있는 페이지를 찾아볼(lookup) 수 있음. 그리고 각 페이지마다 해당 페이지에 있는 블록의 크기를 저장하는 필드가 하나씩 있음, 따라서 블록 크기를 계산하기 위해 블록별 정보를 저장해야하는 오버헤드를 줄일 수 있음.

 

Q4) -- changing the size of the blocks.

A) 블록 크기를 바꾸게 되면, 이 방식을 사용할 수 없게 됨.따라서 이 방식은 블록 크기를 바꾸지 않는 변형된 방식(variant)에 해당.

크기를 변경하는 경우 페이지 전체에 대해 변경해야 함.

 

따라서 memory allocator에는 여러가지 변형이 있고, 여기서 설명하는 것은 "가장 간단한 것"에 해당.

실제로 사용되는 방식은 이 방식과 다름.

일부 allocator는 binned free list에서 2의 거듭제곱(2^k) 방식을 사용하는 대신, 피보나치 수열을 사용하여 서로 다른 bin을 결정하는 방식을 사용함.

Storage Layout of a Program

가상 메모리 주소 공간의 구조

스택은 맨 위(high address)에 있고, 힙은 바로 아래에 있으며 서로를 향해 확장하는 구조

text : code

data : 모든 전역/정적 변수, 상수를 저장, 디스크로부터 읽어들임

bss : 모든 초기화되지 않은 변수를 저장, 0으로 초기화

 

heap은 malloc/free를 호출할 때 사용되는 메모리

실제로 stack과 heap은 64비트 주소를 사용한다면 서로 직접 접촉하는 일은 절대 없음.

만약 많은 precomputation 작업을 수행하는 경우, 예를 들어 거대한 상수 테이블을 생성하는 경우, 프로그램 시작시 이러한 모든 데이터를 디스크에서 읽어 해당 data segment에 저장해야 한다는 것이다. 따라서 이러한 상수가 많으면 프로그램 로딩 시간이 훨씬 길어지게 되나, 일반적으로 많은 런타임 계산량을 줄이기 위해서 웬만한 precomputation은 괜찮음.

프로그램을 시작할 때 메모리에서 모든 계산을 수행하는 것이 전체적으로 더 빠를 수 있는데, 왜냐하면 디스크에서 데이터를 읽어야하기 때문이다.

 

Q) 64비트 주소에서, 초당 40억 바이트를 쓰더라도 100년이 넘게 걸리기 때문에 가상 메모리 주소가 부족해지는 일은 절대 없을 것이다. 그렇다면 가상 메모리를 할당하고 절대 해제(free)하지 않는 방식은 왜 안될까요?

A) if you allocate a bunch of small things in random places, then it's harder to update than a large segment?

랜덤한 위치에 작은 덩어리들을 할당하게 되면, 큰 세그먼트보다 업데이트하기 어려워져서요?

Q) 네, 한가지는 fragmentation 문제입니다. 사용하는 메모리 블록이 메모리상에서 연속적이지 않기 때문에 큰 블록을 찾기가 더 어려워집니다. 다시 말해서,

1) external fragmentation would be horrendous! the performance of the page table would degrade tremendously leading to disk thrashing, since all nonzero memory must be backed up on disk in page-sized blocks.

외부 단편화는 엄청난 문제를 야기하게 될 것입니다. 페이지 테이블의 성능은 disk trashing을 유발하며 엄청나게 저하될 것인데, 0이 아닌 메모리는 페이지 크기의 블록들로 디스크에 백업되어야하기 때문이죠. 게다가 TLB miss rate도 높아질 것임.

2) 또 다른 이유는, 만약 아무것도 해제하지 않으면 physical memory가 고갈될 것이기 때문.

 

따라서 storage allocation의 목표 중 하나는 가능한 한 적은 가상 메모리를 사용하고, 사용되는 부분을 비교적 작게 유지하는 것.

Binned Free Lists의 할당 방식에 대한 분석

Q) 사용하는 힙 메모리의 최대 용량을 M이라고 했을 때, 힙이 BFL allocator에 의해 관리된다면 heap storage에 의해 소비되는 가상 메모리의 양은 O(M lg M)이 된다. 해당 사실을 직관적으로 설명하실 수 있으신분?

bin의 개수는 2의 거듭제곱 단위로 나누므로 log M으로 상한(upper bound)이 정해지며, 각 bin은 O(M)의 메모리를 사용하게 됨.

 

2^ (⌈logx⌉) => 2^(log (x) + 1), => 2x, 2^k => 2M

bin의 최대 개수 : log M

O(M log M)

 

Optimal allocator는 미래의 모든 메모리 요청을 알고있음을 가정한다면 O(1) 이므로, 메모리 할당 프로세스를 최적화하기 위해 여러가지 영리한 작업을 수행할 수 있음.

하지만 실제로는 binned free lists 방식은 Optimal allocator보다 상수배 정도만 성능이 떨어지는 것으로 나타났음. (실제로는 최악의 경우까지 가는 경우가 거의 없으므로 효율적이라는 의미)

→ 블록 병합(coalescing)은 제외했음을 가정.

이러한 상수는 6(lower bound)이라는 것이 밝혀졌는데 찰스 레이서손 교수의 논문에 의해 증명됨

Colaescing : 작은 블록들을 더 큰 블록으로 합치는 것

메모리에 연속된 두 개의 빈 블록이 있는 경우 이 작업을 수행할 수 있음

 

인접한 블록을 효율적으로 찾기 위한 많은 영리한 방법들이 있음

buddy system

- 각 블록은 인접한 메모리인 buddy라는 것을 갖고있는데, 실제로 오버헤드가 BFL보다 크다는 것이 밝혀짐.

- coalescing의 효과에 대해서 증명하는 이론은 존재하지 않지만, 힙 저장 공간이 스택 형태(LIFO)로 또는 일괄적(batch)으로 해제되는 경향이 있기 때문에 실제로는 단편화를 줄이는데 상당히 효과적인 것으로 보임.

다시 말해서, 해제된 객체들은 메모리상에서 서로 매우 가까운 위치에 있는 경향이 있음. 스택 형태로 할당 해제하면 스택 상단에 있는 객체들이 한꺼번에 해제됨. 반면 일괄적(batch)으로 할당 해제하는 경우는 프로그램에서 함께 할당했던 여러 객체를 한꺼번에 해제할 때인데, 예를 들어 그래프에서 vertex 데이터를 모두 동시에 할당했다면, 이들을 한꺼번에 해제할 때 연속된 메모리 덩어리를 얻게 되어 이를 이어 붙일 수 있음.

 

Garbage Collection By Reference Counting

프로그래머가 객체를 직접 해제하는 것으로부터 해방시키는 것.

double-free, dangling pointer의 문제가 사라지기 때문에 프로그래머가 코드를 작성하기 쉬워짐. GC는 프로그래머가 더 이상 접근할 수 없는 객체를 식별하고 재활용하여 해당 메모리 객체가 향후 할당에 사용될 수 있도록 함. 또한 GC가 내장된 언어 외에도, GC가 없는 C언어에서도 자체 GC를 만들 수 있음. 일반적인 GC보다 더 효율적인 특수 목적의 GC를 직접 만들 수도 있음.

 

Q) 이건 이전 주제(BFL)인데, 왜 O(M)이 아닌거죠?

A) Because for each of the bins, you could use up to order M memory. So if you don't do coalescing, basically, I could have a bunch of small allocations, and then I chop up all of my blocks, and then they all go into smaller bins. And then I want to allocate something larger. I can't just splice those together. I have to make another memory allocation. So if you order your memory requests in a certain way, you can make it so that each of the bins has order M memory. 각 bin마다 O(M)이 사용될 수 있기 때문입니다. coalescing을 하지 않으면, 작은 할당을 여러 개 만들고, 각각의 블록을 작은 bin으로 나눠서 할당해야 합니다. 그런데 더 큰 할당을 하려면, 이 작은 블록들을 단순히 합칠 수 없습니다. 새로운 메모리 할당을 해야 하죠. 따라서 메모리 요청 순서를 특정 방식으로 정하면, 각 bin은 O(M)을 갖습니다.

GC 용어

memory objects는 크게 root objects, live objects, dead objects의 3가지 유형으로 나뉨.

root objects는 프로그램에서 직접 접근할 수 있는 객체. 전역 변수, 스택에 있는 객체 등이 여기에 해당.

live objects는 포인터를 통해 root objects를 따라가면 접근할 수 있는 객체.

dead objects는 root로부터 포인터를 통해서 내려가도 접근할 수 없는 객체. 프로그래머가 더 이상 dead objects에 접근할 수 없기 때문에 가비지 컬렉션의 대상이 됨.

 

So in order for garbage collection to work in general, you need to be able to have the garbage collector identify pointers, and this requires strong typing. So languages like Python and Java have strong typing, but in C, it doesn't have strong typing. This means that when you have a pointer you don't actually know whether it's a pointer. Because a pointer just looks like an integer. It could be either a point or an integer. You can cast things in C. You can also do pointer arithmetic in C. So in contrast, in other languages, once you declare something to be a pointer, it's always going to be a pointer. And for those languages that have strong typing, this makes it much easier to do garbage collection. You also need to prohibit doing pointer arithmetic on these pointers. Because if you do  pointer arithmetic and you change the location of the pointer, then the garbage collector no longer knows where the memory region starts anymore. In C, sometimes you do do pointer arithmetic, and that's why you can't actually have a general-purpose garbage collector in C that works well.

일반적으로 GC가 제대로 작동하려면 GC가 포인터를 식별할 수 있어야 하는데, 이를 위해서는 강력한 타입 시스템이 필요합니다. 파이썬이나 자바 같은 언어는 강력한 타입 시스템을 지원하지만, C는 그렇지 않습니다. 즉, 포인터가 있을 때 그것이 실제로 포인터인지 아닌지 알 수 없다는 뜻입니다. 포인터는 정수처럼 보일 수 있기 때문입니다. 포인터일 수도 있고 정수일 수도 있습니다. C에서는 타입 변환이 가능하고 포인터 연산도 가능합니다. 반면에 다른 언어에서는 한 번 포인터로 선언하면 항상 포인터로 유지됩니다. 강력한 타입 시스템을 지원하는 언어에서는 이러한 특징 덕분에 GC이 훨씬 수월해집니다. 또한 포인터에 대한 연산을 금지해야 합니다. 포인터 연산을 통해 포인터의 위치가 변경되면 GC는 더 이상 메모리 영역의 시작 위치를 알 수 없기 때문입니다. C에서는 포인터 연산이 발생하는 경우가 있기 때문에 범용 GC를 제대로 구현하기 어렵습니다.

 

C에서는 포인터를 강제로 int/float 같은 타입 캐스팅이 가능하며, 특히 C타입 캐스팅은 규칙이라는 것이 사실상 없기 때문에 이런 설명을 한듯하다. 또한 포인터에 대해서 ++같은 연산도 할 수 있어 GC가 추적하기 어렵다고 하는 것 같다.

Ref Count가 0인 객체가 생기면, GC에 의해 해제될 수 있음. 이 때, 해당 객체가 가리키고 있던 Ref Count도 각각 감소시켜야 함. 

 

Q) Reference Counting에는 한 가지 문제가 있습니다. 아시는분?

A) 객체 A와 객체 B가 서로 참조 중일 때, 즉 순환 참조(Cycle)가 발생하면 절대 GC되지 않음 !

위 예시에서, 길이가 3인 Cycle이 있음.

문제는 Cycle을 형성하므로 서로를 가리키고 있어 Ref Count가 절대 0이 되지 않고, root에서 해당 Cycle에 포함되는 객체까지 도달 할 수 없기 때문에 cycle 내의 어떤 객체도 삭제할 수 없다. 심지어 cycle에 포함된 객체가 가리키고 있는 다른 객체는 cycle에 포함되지 않더라도 root로부터 도달되지 않으니 함께 삭제될 수 없음.

그럼에도 불구하고, cycle이 발생하지 않는 구조에서는 작동할 경우 구현이 간단하기 때문에 꽤 효율적인 방식임.

Objective-C에서는 StrongPtr, WeakPtr 이라는 2가지 방식을 사용, Ref Count는 StrongPtr에 의해서만 증감됨. 하지만 이 방식을 사용할 경우, WeakPtr로 가리킨 객체를 역참조할 때, 해당 객체가 이미 GC되었을 수 있으므로 주의해야 함.

 

[1] Mark-And-Sweep GC

유향 그래프(u, v)에 대한 BFS를 이용해서 reachable 확인. root를 처음 v.mark = 1으로 지정하고, 나머지는 0으로 지정. root로부터 Breadth First Search하면서 도달되는 "v.mark == 0인" vertex에 대해 v.mark = 1로 지정, 다시 말해서 이전 탐색에 의해 mark된 vertex는 다시 탐색하지 않음.

 

위 예제에서, mark되지 않은 a, h, i, j 객체는 GC의 대상이 됨 (h, i, j는 cycle 형성 중)

 

Mark stage : BFS를 통해 live objects를 판별

Sweep stage : 모든 메모리를 스캔해서, unmarked objects(dead objects?)를 판별하여 해제.

 

Q) 이 방식에는 1가지 이슈가 있는데 아시는분?

A) 메모리 전체를 훑어봐야 함, Mark-And-Sweep 방식에는 할당된 객체만 추적하는 변형(variant)이 있어서, 전체 메모리 공간을 스캔하는 대신 할당된 객체만 스캔하면 되는 경우도 있음.

Q) 또 다른 이슈 아시는분?

A) Strong Typing이 전제되어야 함

Q) 그것도 가정한 상태임. 또 다른 이슈?

A) 레퍼런스 되지 않는 모든 객체에 대해서도 전부 스캔을 해야 하는 추가적인 오버헤드가 있음

Q) 전부 이슈는 맞는데, 제가 의도한 이슈는 Mark-And-Sweep 알고리즘이 단편화 문제를 해결하지 못한다는 것임. Live Objects를 메모리에서 연속적으로 저장하도록 압축(Compact)하지 않음. 이 방식은 Unreachable object만 해제할 뿐, Reachable object에는 아무런 영향을 주지 못함.

→ 그러니까, 객체 1000개가 연속적으로 저장되어 있다고 하자. Unreahable object를 해제하면 해당 연속 메모리에 hole이 생긴다는 듯하다.

[2] Stop-And-Copy GC

Q) BFS 구현을 봤을 때, live objects들이 메모리에서 연속적으로 위치하도록 하는데 사용할 수 있는 정보가 있을까? - fragmentation을 줄이는데 활용할 수 있는 무언가가 있을까?

A) visited vertices가 queue내에 연속적으로 위치해 있음.

 

관찰

Mark-And-Sweep 알고리즘에서는 vertex's id만 queue에 넣지만, 실제 객체들을 queue에 넣는다면, 해당 queue를 새로운 메모리로 사용할 수 있음 !

→ Unreachable objects들이 암묵적으로 삭제됨으로써, extrernal fragmentation을 처리하게 됨.

FROM space가 가득차게 되면, BFS를 사용하게 되는데 live objects들이 TO space 공간에 남게 되는 동시에, queue로 사용했음으로 "연속적인 메모리 영역"이 되므로 이것을 재사용할 수 있음. 이후 TO space를 이전 FROM space 역할로 바꿔서 사용하며 이전 단계를 반복.

 

we're going to have two separate memory spaces, the FROM space and the TO space. So in the FROM space, I'm just going to do allocation and freeing on it until it becomes full. So when  allocate something I place it at the end of this space. When I free something, I just mark it as free, but I don't compact it out yet. And when this FROM space becomes full, then I'm going to run my garbage collection algorithm, and I'm going to use the TO space as my queue when I do my breadth-first search. So after I run my breadth-first search, all of the live objects are going to appear in the TO space in contiguous memory since I used the TO space as my queue. Right, and then I just keep allocating stuff from the TO space and also marking things as deleted when I free them until the TO space becomes full. Then I do the same thing, but I swap the roles of the TO and the FROM spaces. So this is called the Stop-And-Copy algorithm.

우리는 FROM 공간과 TO 공간, 이렇게 두 개의 분리된 메모리 공간을 사용할 겁니다. FROM 공간에서는 공간이 가득 찰 때까지 메모리 할당과 해제를 반복합니다. 메모리를 할당할 때는 공간의 끝에 배치하고, 해제할 때는 해제되었다고 표시만 하고 아직 압축(compact) 작업은 하지 않습니다. FROM 공간이 가득 차면 가비지 컬렉션 알고리즘을 실행하고, 너비 ​​우선 탐색(BFS)을 수행할 때 TO 공간을 queue로 사용합니다. BFS가 실행되면 모든 live object가 TO 공간의 연속된 메모리 공간에 저장됩니다. TO 공간을 queue로 사용했기 때문입니다. 그리고 TO 공간이 가득 찰 때까지 계속해서 메모리를 할당하고 해제할 때는 해제되었다고 표시합니다. 그런 다음 FROM 공간과 TO 공간의 역할을 바꿔서 같은 과정을 반복합니다. 이것이 바로 Stop-And-Copy 알고리즘입니다.

 

Q) 이 알고리즘에는 아직 해결하지 못한 잠재적인 문제가 하나 있는데 아시는분?A) 만약 아무런 dead objects가 없다면, 멀쩡한 live objects 전체 storage를 복사하게 됨.

A) Mark-And-Sweep은 전체 객체를 복사하지 않고 일부 복사 작업은 여전히 필요하긴 하지만, "id"를 복사하기 때문에 크진 않음.

Q) 사실 여기에는 정확성(correctness) 이슈가 있음, 아시는분?

A) so the answer is that if you had pointers that pointed to objects in the FROM space, if you move your objects to the TO space, those pointers aren't going to be correct anymore. So if I had a pointer to a live object before and I moved my live object to a different memory address, I need to also update that pointer.

그러니까 답은, FROM 공간에 있는 객체를 가리키는 포인터가 있는 경우, 객체를 TO 공간으로 옮기면 해당 포인터는 더 이상 정확하지 않게 된다는 것입니다. 예를 들어, 이전에 live object를 가리키는 포인터가 있었는데, 해당 객체를 다른 메모리 주소로 옮겼다면, 그 포인터도 함께 업데이트해야 합니다.

Since the FROM address of an object is not generally equal to the TO address of the object, pointers must be updated.
- when a object is copied to the TO space, store a forwarding pointer in the FROM object, which implicitly marks it as moved.
- When an object is removed from the FIFO queue in the TO space, update all its pointers.

일반적으로 객체의 FROM 주소와 TO 주소가 같지 않으므로 포인터를 업데이트해야 함.

- 객체를 TO 공간으로 복사할 때, FROM 객체에 전달 포인터(forwarding pointer)를 저장하여 객체가 이동되었음을 암묵적으로 표시

- TO 공간의 FIFO queue에서 객체를 제거할 때, 해당 객체의 모든 포인터를 업데이트

 

So the idea is that, when an object is copied to the TO space, we're going to store a forwarding pointer in the corresponding object in the FROM space, and this implicitly marks that object as moved, and then when I remove an object from the FIFO queue in my BFS, in the TO space I'm going to update all of the pointers by following these forwarding pointers.

그러니까 아이디어는 이런데요, 객체가 TO 공간으로 복사될 때, FROM 공간의 해당 객체에 forwarding pointer를 저장해서 그 객체가 이동되었음을 암묵적으로 표시하는 겁니다. 그리고 진행중인 BFS에서 FIFO 큐로부터 객체를 제거할 때, TO 공간에서 이 forwarding pointer를 따라가서 모든 포인터를 업데이트하는 겁니다.

let's look at an example of how this works. So let's say I'm executing the breadth-first search, and this is my current queue right now. What I'm going to do is, when I dequeue an element from my queue, first I'm going to place the neighboring objects that haven't been explored yet onto the queue. So here it actually has two neighbors, but the first one has already been placed the queue, so I can ignore it. And the second one hasn't been placed on the queue yet, so I place it onto the queue.

And then I'm also going to-- oh, so this object also has a pointer to something in the FROM space, which I'm not going to change at this time. But I am going to store a forwarding pointer from the object that I moved from the FROM space to the TO space, so now it has a pointer that tells me the new address. And then, for the object that I just dequeued, I'm going to follow the forwarding pointers of its neighbors, and that will give me the correct addresses now. So I'm going to update the pointers by just following the forwarding pointer. So the first pointer pointed to this object, which has a forwarding pointer to this, so I just make a point to this object in the TO space. And then similarly for the other pointer, I'm going to make it point to this object. So that's the idea how of how to adjust the pointers.

이것이 어떻게 작동하는지 예시를 통해 살펴보겠습니다. BFS를 쓴다고 가정해 보겠습니다. 현재 Q는 다음과 같습니다. Q에서 요소를 꺼낼 때, 먼저 아직 탐색하지 않은 이웃한 객체들을 Q에 추가합니다. 여기에는 두 개의 이웃 객체가 있는데, 첫 번째 객체는 이미 Q에 추가되었으므로 무시합니다. 두 번째 객체는 아직 Q에 추가되지 않았으므로 추가합니다.

그리고 이 객체는 FROM 공간의 어떤 위치를 가리키는 포인터를 가지고 있는데, 이 포인터는 현재 변경하지 않습니다. 하지만 FROM 공간에서 TO 공간으로 이동한 객체의 forwarding pointer를 저장합니다. 이제 이 포인터는 새로운 주소를 알려줍니다. 그리고 방금 Q에서 꺼낸 객체의 경우, 이웃 객체들의 forwarding pointer를 따라가면 이제 정확한 주소를 얻을 수 있습니다. forwarding pointer를 따라가서 포인터를 업데이트하겠습니다. 첫 번째 포인터는 이 객체를 가리키고 있었고, 이 객체의 forwarding pointer는 이 객체를 가리키고 있으므로, TO 공간에서 이 객체를 가리키도록 수정합니다. 마찬가지로 다른 포인터도 이 객체를 가리키도록 수정합니다. 이것이 포인터를 조정하는 방법에 대한 아이디어입니다.

 

Q) 객체를 queue에 추가할 때 포인터를 조정할 수 없는 이유가 무엇일까? 객체를 queue에서 꺼낼 때 포인터를 조정해야 하는 이유는 뭘까?

A) 아직 이웃을 처리하지 않았기 때문.queue에 넣을 때 실제로 neighbor object가 TO 공간 어디에 위치할지 미리 알 수 없으므로, 객체를 queue에서 꺼낼 때만 그 사실을 알 수 있음. 왜냐하면 객체를 queue에서 꺼낼 때는 이미 주변 객체를 탐색했기 때문에 forwarding pointer를 생성할 수 있기 때문.

 

Q) Stop-And-Copy 프로시저를 수행하는데 드는 시간은 얼마나 될까? N을 object 개수라고 해보자.

A) BFS이기 때문에 object 개수에 따른 선형(linear) 시간에 해당됨. object 개수 + object에 대한 포인터 개수 + 복사하는 시간 = O(N).

 

Stop-And-Copy 방식의 장점은 실제로 모든 objects를 확인할 필요가 없다는 것인데, TO 공간에 복사되지 않은 객체는 암묵적으로 삭제되기 때문. 반면에, Mark-And-Sweep은 실제로 전체 메모리를 순회해야 하고, 그 다음 unreachable objects를 전부 해제해야 함. 따라서 Mark-And-Sweep보다 더욱 효율적이면서, external fragmentation 문제도 해결할 수 있음.

So what happens when the FROM space becomes full? So what you do is, you're going to request a new heap space equal to the used space, so you're just going to double the size of your FROM space. And then you're going to consider the FROM space to be full when the newly allocated space becomes full, so essentially what you're going to do is, you're going to double the space, and when that becomes full, you're going to double it again, and so on.  And with this method, you can amortize the cost of garbage collection to the size of the new heap space, so it's going to be amortized constant overhead per byte of memory. And this is assuming that the user program is going to touch all of the memory that it allocates. And furthermore, the virtual memory space required by this scheme is just a constant times the optimal if you locate the FROM and the TO spaces in different regions of virtual memory so that they can't interfere with each other. And the reason why it's a constant times the optimal is because you only lose a factor of 2 because you're maintaining two separate spaces. And then another factor of 2 comes from the fact that you're doubling the size of your array when it becomes full and up to half of it will be unused. But it's constant times optimal since we're just multiplying constants together. And similarly, when you're FROM space becomes relatively empty. for example, if it's less than half full, you can also release memory back to the OS, and then the analysis of the amortized constant overhead is similar.

그렇다면 FROM 공간이 가득 차면 어떻게 될까요? 사용한 공간과 동일한 크기의 새로운 힙 공간을 요청합니다. 즉, FROM 공간의 크기를 2배로 늘리는 겁니다. 그리고 새로 할당된 공간이 가득 차면 FROM 공간이 가득 찬 것으로 간주합니다. 기본적으로 공간을 두 배로 늘리고, 그 공간이 가득 차면 다시 두 배로 늘리는 식으로 반복하는 것입니다. 이 방법을 사용하면 GC 비용을 새로운 힙 공간의 크기에 비례하여 분산시킬 수 있으므로, 메모리 1바이트당 amortized O(1) 오버헤드가 발생합니다. 이는 사용자 프로그램이 할당된 메모리를 모두 사용한다고 가정했을 때의 결과입니다. 또한, FROM 공간과 TO 공간을 서로 다른 가상 메모리 영역에 배치하여 간섭을 방지하면, 이 방식에 필요한 가상 메모리 공간은 Optimal 크기에 비해 상수배 정도만 필요합니다. Optimal값의 몇 배인지는 명확하지 않습니다. 2개의 별도 공간을 유지해야 하므로 2배의 손실만 발생하기 때문입니다. 또 다른 2배의 손실은 배열이 가득 차면 크기가 두 배로 늘어나고, 그중 절반까지는 사용되지 않는다는 사실에서 비롯됩니다. 하지만 결국 "상수를 곱하는 것"이므로 Optimal값의 몇 배라는 결과가 나옵니다. 마찬가지로, FROM 공간이 상대적으로 비어 있을 때, 예를 들어 절반 미만으로 차 있는 경우, 메모리를 OS에 반환할 수 있으며, 이 경우에도 amortized O(1) 오버헤드 분석은 유사하게 적용됩니다.

OK, so there's a lot more that's known and also unknown about dynamic storage allocation, so I've only scratched the surface of dynamic storage allocation today. There are many other topics. For example, there's the buddy system for doing coalescing. There are many variants of the Mark-And-Sweep procedure. So there are optimizations to improve the performance of it. There's generational garbage collection, and this is based on the idea that many objects are short-lived, so a lot of the objects are going to be freed pretty close to the time when you allocate it. And for the ones that aren't going to be freed, they tend to be pretty long-lived. And the idea of generational garbage collection is, instead of scanning your whole memory every time, you just do work on the younger objects most of the time. And then once in a while, you try to collect the garbage from the older objects because those tend to not change that often. There's also real-time garbage collection. So the methods I talked about today assume that the program isn't running when the garbage collection procedure is running, but in practice, you might want to actually have your garbage collector running in the background when your program is running, but this can lead to correctness issues because the static algorithms I just described assume that the graph of the objects and pointers isn't changing, and when the objects and pointers are changing, you need to make sure that you still get a correct answer. Real-time garbage collection tends to be conservative, so it doesn't always free everything that's garbage. But for the things that it does decide to free, those can be actually reclaimed. And there are various techniques to make real-time garbage collection efficient. One possible way is, instead of just having one FROM and TO space, you can have multiple FROM and TO spaces, and then you just work on one of the spaces at a time so that it doesn't actually take that long  to do garbage collection. You can do it incrementally throughout your program. There's also multithreaded storage allocation and parallel garbage collection. So this is when you have multiple threads running, how do you allocate memory, and also how do you collect garbage in the background. So the algorithms become much trickier because there are multiple threads running, and you have to deal with races and correctness issues and so forth. And that's actually a topic of the next lecture.

동적 메모리 할당에 대해서는 알려진 것과 알려지지 않은 것이 훨씬 더 많습니다. 그래서 오늘 저는 동적 메모리 할당의 극히 일부분만 다뤘을 뿐입니다. 다룰 주제는 훨씬 더 많습니다. 예를 들어,

1) 병합을 위한 버디 시스템이 있고,

2) Mark-And-Sweep 프로시저에는 여러 변형이 있으며, 성능을 향상시키는 최적화 기법도 있습니다.

3) Generational Garbage Collection도 있는데, 이는 많은 객체가 수명이 짧다는 점에 기반합니다.

즉, 대부분의 객체는 할당 직후에 해제되고, 해제되지 않는 객체는 수명이 긴 경향이 있습니다. generational garbage collection은 매번 전체 메모리를 스캔하는 대신, 대부분의 경우 수명이 짧은 객체에 대한 작업을 수행하고, 가끔씩 수명이 짧은 오래된 객체에서 가비지를 수집하는 방식입니다.

4) 이 외에도 Realtime Garbage Collection도 있습니다. 오늘 설명한 방법들은 GC 프로시저가 실행되는 동안 프로그램이 실행 중이 아니라는 가정하에 작성되었습니다. 하지만 실제로는 프로그램 실행 중에 백그라운드에서 GC를 실행하는 것이 좋을 수 있습니다. 그러나 이는 정확성 문제를 야기할 수 있는데, 방금 설명한 static 알고리즘은 객체와 포인터의 그래프가 변경되지 않는다고 가정하기 때문입니다(백그라운드에서 GC가 도중 와중에 객체와 포인터에 대한 그래프가 변경될 수 있기 때문). 객체와 포인터가 변경될 때에도 정확한 결과를 얻어야 합니다. realtime garbage collection은 보수적인 경향이 있어 모든 가비지를 항상 해제하지는 않습니다. 하지만 해제하기로 결정한 객체들은 실제로 회수될 수 있습니다.

실시간 가비지 컬렉션을 효율적으로 만드는 다양한 기법들이 있는데요, 한 가지 방법은 "하나의 FROM 및 TO 공간" 대신 ​​여러 개의 FROM 및 TO 공간"을 사용하고, 한 번에 하나의 공간만 처리하여 가비지 컬렉션 시간을 단축하는 것입니다. 프로그램 전체에 걸쳐 점진적으로 처리할 수 있습니다.

5) Multithreaded Storage Allocation과 Parallel Garbage Collection도 있습니다. 여러 스레드가 실행될 때 메모리를 어떻게 할당하고 백그라운드에서 가비지를 어떻게 수집하는지가 관건입니다. 여러 스레드가 실행되면서 알고리즘이 훨씬 복잡해지고, Race Condition이나 정확성(Correctness) 문제 등을 처리해야 합니다. 이는 다음 강의에서 다룰 주제입니다.

 

So in summary, these are the things that we talked about today. So we have the most basic form of storage, which is a stack. The limitation of a stack is that you can only free things at the top of the stack. You can't free arbitrary things in the stack, but it's very efficient when it works because the code is very simple. And it can be inlined, and in fact this is what the C calling procedure uses. It places local variables in the return address of the function on the stack. The heap is the more general form of storage, but it's much more complicated to manage. And we talked about various ways to do allocation and deallocation for the heap. We have fixed-size allocation using free lists, variable-size allocation using binned free lists, and then many variants of these ideas are used in practice. For garbage collection, this is where you want to free the programmer from having to free objects. And garbage collection algorithms are supported in languages like Java and Python. We talked about various ways to do this reference counting, which suffers from the limitation that it can't free cycles. Mark-And-Sweep and Stop-And-Copy-- these can free cycles. The Mark-And-Sweep procedure doesn't deal with external fragmentation, but the stop-and-copy procedure does. We also talked about internal and external fragmentation. So external fragmentation is when your memory blocks are all over the place in virtual memory. This can cause performance issues like disk thrashing and TLB misses. Then there's internal fragmentation, where you're actually not using all of the space in the block that you allocate. So for example, in the binned free list algorithm, you do have a little bit of internal fragmentation because you're always rounding up to the nearest power of 2 greater than the size you want, so you're wasting up to a factor of 2 in space. And in project 3, you're going to look much more at these storage allocation schemes, and then you'll also get to try some of these in homework 6.

요약하자면, 오늘 우리는 이러한 내용들을 살펴보았습니다.

가장 기본적인 형태의 메모리 저장 방식인 Stack이 있습니다. 스택의 한계는 스택의 최상단에 있는 요소만 해제할 수 있다는 것입니다. 스택 내의 임의의 요소를 해제할 수는 없지만, 코드가 매우 단순하고 효율적이기 때문에 효과적입니다. 또한 인라인 처리 가능하며, 실제로 C의 호출 프로시저는 함수의 반환 주소에 지역 변수를 저장하는 방식을 사용합니다.

Heap은 더 일반적인 형태의 메모리 저장 방식이지만, 관리하기가 훨씬 더 복잡합니다. 우리는 힙의 할당 및 해제에 대한 다양한 방법을 살펴보았습니다.

Fixed-Size Heap Allocation에는 free lists를 사용하는 방식이 있고,

Variable-Size Heap Allocation에는 Binned Free Lists를 사용하는 방식이 있으며, 이러한 아이디어의 다양한 변형이 실제로 사용됩니다. GC는 프로그래머가 객체를 해제하는 번거로움에서 벗어나도록 하는 것을 목표로 합니다. 자바와 파이썬 같은 언어에서는 GC 알고리즘을 지원합니다. 참조 카운팅 방식은 여러 가지가 있지만, 사이클을 해제할 수 없다는 한계가 있습니다. Mark-And-Sweep과 Stop-And-Copy 방식은 사이클을 해제할 수 있습니다.

Mark-And-Sweep 방식은 external fragmentation를 처리하지 않지만, Stop-And-Copy 방식은 external fragmentation을 처리합니다. 또한 내부 단편화와 외부 단편화에 대해서도 이야기했습니다. 외부 단편화는 가상 메모리에서 메모리 블록이 여기저기 흩어져 있는 경우를 말합니다. 이는 Disk Thrasing이나 TLB Miss 같은 성능 문제를 일으킬 수 있습니다. internal fragmentation는 할당된 블록의 공간을 전부 사용하지 않는 경우를 말합니다. 예를 들어, Binned Free Lists 알고리즘에서는 원하는 크기보다 큰 2의 거듭제곱으로 항상 반올림하기 때문에 내부적으로 약간의 공간 낭비가 발생합니다. 즉, 최대 2배의 공간을 낭비하는 셈입니다. 프로젝트 3에서는 이러한 storage allocation 방식을 더 자세히 살펴보고, 과제 6에서는 이러한 방식들을 직접 시도해 볼 수 있습니다.