감명 깊었던 programming language principles 4- 기계 중심 언어-메모리 관리

메모리 관리

컴퓨터가 프로그램을 실행할 때 소모하는 자원은 시간과 메모리입니다. 시간은 무한하지만, 메모리는 유한합니다. 프로그램이 한없이 메모리를 소모할 수는 없습니다.

메모리가 어디에서 소모되는지 볼 필요가 있습니다.

프로그램 실행중에 메모리는 let- 식과 프로시져 호출식의 실행을 위해 하나씩 소모됩니다.

                                                 

let 식으로 선언된 이름과 프로시져의 인자 이름을 위해 매번 새로운 메모리가 소모됩니다. 그리고 소모되기만 합니다.

이렇게 메모리만 소모시키면 언젠가는 프로그램을 더이상 수행 못하게 되겠죠.

따라서 메모리를 재활용 해야 합니다. 그러면 어떤 메모리를 재활용 해야 하는가?

프로그램 실행중 사용한 메모리중에서 더이상 사용하지 않을 메모리를 재활용 해야 합니다.

그럼  어떻게 더이상 사용하지 않을 메모리인지를 알아 낼 것인가?

앞에서 우리가 디자인한 언어의 경우에는 쉽습니다. 메모리 주소의 사용기간이 곧 그 주소의 이름의 유효범위 이기 때문입니다.

메모리 주소는 하나의 이름만 붙고 그 이름을 통해야만 그 메모리 주소를 사용 할 수 있기 때문입니다.

우리의 언어에서는 let 식의 마지막이나, 프로시져의 마지막입니다. 

언어가 복잡해지면, 이렇게 간단하게 메모리 재활용이 안되죠..(garbage collection)

메모리 주소가 따로 프로그램 식의 결과값으로 프로그램 여기저기로 흘러다니면, 메모리 주소의 사용기간은 그 주소에 붙은 이름의 유효범위와 일치하지 않게 됩니다.

이런 언어의 경우 메모리관리는 어떻게 해야 할까요... 

이 문제는 좀 미뤄 둬야 할것 같습니다. 아직 이 문제를 다룰 단계가 아니기 때문이죠. 우리 언어는 아직 이런 기능이 없죠.

현재 우리가 설계한(사실은 과거의 언어를 따라서 규칙을 하나하나 추가한것이죠) ,이름을 붙일 수 있는 메모리 주소와 프로그램 코드, 이름의 유효범위, 재귀호출 , 값전달과 주소전달 호출이 가능하고,

while, for 식으로 반복이 가능합니다.

리스트나 나무구조를 만들고 사용하는 프로그램을 짤수 있을까요? 집합을 만들고 사용하는 프로그램을 작성할 수 있을까요? 할수는 있습니다.

그러나 , 손쉽게 다룰 수 있도록 프로그래밍 언어에서 지원이 되면 좋겠습니다.

기초적인 값 이외에 구조가 있는 값을 프로그램에서 손쉽게 다룰 수 있도록 하려면, 구조가 필요합니다.

기초적인 값은 메모리 주소 하나면 됩니다. 구조를 갖춘다는 것은 여러개의 기초적인 값들을 모아서 하나의 새로운 형태를 만든다는 것입니다.

즉, 여러개의 메모리 주소가 필요하게 됩니다. 메모리 뭉치가 됩니다. 이를 레코드(record)라고 합시다. C에서는 struct이라고 하죠.

이렇게 뭉쳐진 메모리 안에 각각의 메모리 주소들도 이름이 있습니다. 레코드 필드라고 합시다.  배열도 메모리 뭉치입니다. 각각의 메모리 주소들의 이름이 자연수로 되어있죠.

                                                                                 

로 표현 할수 있습니다.

                                                                                

값들은 레코드 까지 포함하게 되었습니다. 

                                                                             

                                                                           

프로그래밍 언어에서 레코드를 만들고 사용하는 문법이 아래와 같이 제공 됩니다.

                                                                              

레코드에 이름을 붙이고, 레코드의 필드가 아래와 같이 사용됩니다.

let

   item:= {id:=200012, age:=20}

in 

   item.id + item.age

이제 나무를 작성하는 것이 쉬워졌습니다.

let

    tree := {left:={},v:=0, right:={}}

in

   tree.right := {left:={}, v:=2,:right:=3};

   shake(tree)

이렇게 레코드가 메모리 뭉치를 뜻하면서, 그리고 레코드가 값이 되면서, 메모리 주소의 사용기간을 간단히 알 수 없게 되었습니다.

...

f( let tree:={left:={}, v:=0, right={}}  in tree })

...

포인터 : 메모리 주소를 데이타로

지금까지의 값들은 자유자제로 사용되었습니다. 변수에 저장되기도 하고 프로시저에 전달되기도 하고 프로시져의 결과값이기도 하였습니다.

값들로 자유롭게 움직 일 수 있다는 것은 이름이 붙어 있을 필요가 없이 계산 될 수 있음을 의미 하기도 합니다.

정수마다 이름을 붙여 사용한다거나, 레코드마다 이름이 있어야 하고, 정수를 더할때 마다 그 결과에 이름을 붙여야만 한다면,

불편할 것입니다. 그리고 불평은 당연한 것입니다.

지금까지 항상 이름을 붙여야만 사용할 수 있는 값들이 있었습니다. 메모리 주소와 프로시져 였죠.

메모리의 주소를 이름 없이 쓸 수 있게 하려면, 값들 중에 메모리 주소 역시 값이 되게 하면 됩니다.

                                           

 

프로그램에서 메모리 주소를 값으로 다룰 수 있으려면,문법을 제공해야 합니다.

                                           

malloc E와  &- 식은 메모리 주소값을 만드는 식입니다.

레코드는 메모리 주소 뭉치이고, 레코드는 값이므로, 레코드를 이용해서 메모리 주소가 값으로 여겨지는 프로그램을 할 수 는 있습니다. 

어떻게 ?

                                         

                                      

                                        

                                 

                                

1. *E는 그 자체가 식인 경우와 메모리 지정문의 왼쪽에 있을 경우, 의미가 다르다.

  *E가 지정문의 왼쪽에 있는 경우 E가 뜻하는 메모리의  주소값을 뜻한다.

  *E가 지정문의 오른쪽에 있을 경우 E가 뜻하는 메모리 주소에 보관되어있는 값을 뜻한다. 

(C 언어가 이렇게 되어있지요.)

그래서 다음 프로그램을 실행 시키면,

let 

   x:= malloc(2)

in

   *x := 1;

   *(x+1) := *x+2

x의 주소의 위치에 1을 담고, 다음 위치에 3을 담습니다.

메모리관리

메모리 블럭을 설정하는 방법이나, 레코드 등에 대해서 정의하는 법이 만들어졌으니, 이제 재활용에 대해서 본격적으로 고민해볼 차례입니다.

초기에 작성했던 언어의 경우에는 메모리와 메모리 주소의 이름의 사용기간이 일치했기 때문에 메모리 재활용이 쉬웠습니다.

그러나,  지금은 쉽지 않습니다.

어떻게 해야 할까요?

수동 메모리 재활용

해결을 미루는 쉬운 방법이 있습니다. 메모리 재활용을 프로그래머에게 맡기는 것입니다. 메모리 재활용이 안되는 문제는 프로그래머의 책임으로 ...

그래서 프로그램 언어에 메모리 재활용 명령문을 제공하는 것입니다. (C가 이렇습니다.)

                                       

free E 식의 의미를 정의 해봅시다. 식 E는 메모리 주소를 계산합니다. 그 주소는 반드시 할당받은 메모리 주소이어야 합니다. 메모리 뭉치를 재활용하려면 메모리 뭉치 에 포함된 모든 주소를 재활용 해야 합니다.

                          

\frac { \sigma,M\vdash E \Rightarrow \ell,M' }{ \sigma, M\vdash free\quad E \Rightarrow \cdot ,M' } \quad \ell \in Dom \quad M

좀이상합니다. 메모리 재활용 효과가 표현되지 않았습니다.메모리 재활용 효과가 표현되지 않아도 충분한가???  

메모리 재활용은 이제 프로그래밍 언어 밖의 일이 되어버렸습니다.

언어의 의미정의 목적은 우리가 필요로하는 디테일의 정도에서 혼동이 없게 정의하는 것입니다. 메모리 재활용에 대해서 명시 할 필요는 없습니다.

이 언어의 의미정의로 메모리 관리에 대해 알 수 있는 사실들은.

1. 새 메모리가 필요할 때, let-식이나, 프로시져 호출, 레코드 식, malloc 식, 새로운 메모리는 항상 있어야 한다.

2. 메모리 주소에 저장된 데이타가 없을 때, 그 주소를 접근 하는 식은 의미가 없다.

    let x:= malloc(1) in *x

3. 할당된 메모리들은 서로에게서 서로에게로 도달할 수 있는 방법이 없다. 할당 받은 주소로 부터 몇 발자국을 움직여서 별도로 할당받은 다른 메모리에 도달할 수 있는 방법은 없다.

  ( 이 부분은 C와 다른 점이기도 합니다. C에서는 임의의 주소로 접근이 가능하기 때문이죠)

자.. 오랜 기간동안 문제가 되어왔던 "메모리 재활용을 프로그래머에게 미루는 것은 바람직한 것인가?".

어쩔 수 없는 선택이라고 봐야 할 것입니다.

언어가 복잡해 질 대로 복잡해졌고, 메모리 재활용 방안은 없고.... 

프로그래머가 신경 써야 할 것은 많아졌습니다. 프로그램의 논리적인 흐름만이 아니라, 유한한 메모리를 가진 컴퓨터가 자신의 프로그램을 실행하게 된다는 조건을 염두해 두어야 하고, 적절한 시점에 메모리를 해재 해줘야 합니다. 사용한 메모리 주소 마다 말이죠.

다른 질문, 과연 프로그래머가 자신의 프로그램이 소모하는 메모리의 사용기간을 가장 잘 알 수 있는가? 정말로 그런가?

C 프로그래밍의 경험이 지난 20년 넘게 쌓이면서, 그 대답은 "아니다" 라고 결론이 났습니다. 현재 프로그래머가 가장 많이 하는 실수가 메모리 재활용 오류입니다.

메모리 관리를 프로그래머에게 맡기면서 C 프로그램의 가장 골치아픈 오류가 메모리 재활용이 되었습니다.

그 오류는 두가지 인데,  재활용 지점을 너무 늦게 잡는 오류와 너무 늦게 잡는 오류입니다.

너무 늦게 잡으면 메모리 자원이 고갈되고, 너무 빠르게 잡으면, 사용중인 메모리가 용도변경이 되어버리는 것입니다.

memory leak 과 dangling pointer 죠.

자동 메모리 재활용

메모리 재활용은 사실 프로그래머가 제대로 완벽하게( 안전하게 말구요) 처리하는 것은 어렵습니다. 제 경험도 그렇고, 여러사람들의 경험을 들어봐도 그렇죠..

자동 메모리 재활욜의 개념은 ... 

1. 프로그램 실행은 계속 메모리를 소모한다.

2. 메모리 소모량이 어느 수위에 오르면, 실행을 잠시 멈춘다.

3. 메모리를 재활용한다.

4. 이제 컴퓨터의 메모리 자원이 풍부해졌다.

5. 멈춘 프로그램의 실행을 재개한다.

가능할까? 

프로그램이 멈추고, 앞으로 사용하지 않을 메모리를 찾아서 재활용해야 합니다. 그런데 과연 앞으로 사용하지 않을 메모리를 찾아서 재활용한다는 것이 가능한것인가요?

어떻게 앞으로 사용하지 않을 것을 알까요?  어렵습니다. 사실은 모든 사용하지 않을 메모리를 찾는 것은 불가능합니다. 빠.짐. 없. 이.찾는 것...

확신을 어떻게 할 수 있을까요? 모든 재활용 할수 있는 메모리를 찾을 수 있다는 것은, 이미 불가능하다고 증명된, Halting problem 을 푸는 프로그램을 작성할 수 있다는 것이 되기 때문입니다.

Halting problem program역시 메모리를 사용할  것이고, 이 프로그램의 재활용 가능한 메모리를 빠짐없이 재활용 할 수 있다는 의미가 되기 때문입니다.

H라는 프로그램이 있다고 하자. 프로그램 p를 받아서 p 가 유한한 시간에 끝난다고 하면 true를 리턴하고, 그렇지 않으면 false를 리턴한다. 

이 프로그램H를 가지고 다음과 같이 모순된 f라는 함수를 정의할 수 있습니다.

function f() = if H(f) then (while true skip)

                         else skip

C 로 표현 해보면 아래와 같은 형식..

( 자꾸 C 문법을 가져오는데, 이해를 돕기 위해서 가져오는 것입니다. 실제로 이해를 위해서는 C 문법을 배재하고 이해하는 것이 앞으로 나아가는데 더 도움이 됩니다.)

int f() 

{

    if H(f) 

    {

            while (true);

    }

    else 

    {

            return 1;

    }

}

f가 끝이 난다면H(f)는 true를 리턴할 것이고, 그러면, f는 while true skip 에 의해서 무한히 끝나지 않습니다.

f가 무한히 끝나지 않는다면, H(f)는 false를 return 할 것이고, f는 끝날 것입니다.

이것이 디지탈 컴퓨터의 한계라고 합니다.  

여기서 조건을 조금만 완화하여 그럴듯한(?: 완전하지 않지만, 쓸만한)  재활용 이라고 하면, 우리에게 가능성이 생깁니다.

- 몇개는 빠뜨릴 수 있지만, 꽤 많은 부분은 재활용 해주는 프로그램을 만들수 있다.

원칙 : 프로그램의 진행을 멈추고 나서, 지금까지 할당된 메모리중에서 미래에 사용할 수 있는 메모리를 제외하고 나머지는 모두 재활용해야 한다.

사실: 재활용을 완전하게 할 수 있는 방법은 없다. 

양보: 재활용을 안전하게 할 수 있는 방법은 있다.

- 앞으로 실행할 식인 E만 있다고 하자, 식 E의 현재 환경 environment 으로 부터 현재의 메모리를 통해 다다를 수 있는 모든 주소들은 앞으로 E를 실행중에 다시 사용될 수 있다. 

이것들만 빼고 재활용하자. 즉, 그렇게 해서 다다를 수 없는 메모리 주소들은, 과거에 할당되어 사용되었으나 앞으로의 E를 실행하는데 사용되지 않을 것이 분명하므로,

재활용 해도 된다.

현대 언어들의 메모리 재활용기 (GC: garbage collector)는 위의 방식으로 구현되어있습니다.(Java, ML, Scheme, Haskell, C#, Prolog, etc)

메모리 재활용기(Garbage collector) 구현 알고리즘은 대표적으로 두가지가 있습니다.

프로그램 실행중에 메모리에 만들어진 구조물들을 모두 따라가면서 앞으로 사용될 수 있는 메모리 주소들을 모으게 됩니다. 

메모리가 없어서 메모리 재활용기를 돌리는 것인데, 메모리를 필요로 하게 되죠.

위의 방법으로 메모리 주소들을 모으기 위해서는, 그래프를 누비고 다니는 알고리즘(depth-first-, breath-first-traversal  algorithms )들은 메모리를 소모합니다.

그래프의 가장 긴 경로만큼의 스택을 갖게 되죠.

그러면, 메모리를 소모하지 않고 그래프를 누비는 방법이 있을까요? 스택없이 가능한 알고리즘이 있습니다.

1. 헨델과 그레텔 알고리즘 -Mark & Sweep

2. Stop & copy 

- 메모리 영역을 2개로 나누고, garbage collection이 발생할때, 다른 메모리 영역으로 copy함.

- fragmentation 발생이 거의 없음.

- 메모리를 반밖에 사용할 수 없음.

- copy overhead가 있음.

3. generational 

-  모든 메모리를 탐색하는 것보다, 일부만 탐색하도록 하여 속도를 높이는 방법.

   - 생성된 시기별로 세대를 나눈다.

   - Heap을 두개 이상의 sub heap으로 나눔.

   - 객체가 처음 생성되면, 0 번 세대의 heap에 할당.

   - 0세대의 Garbage collection이 수행될때, (대부분 객체는 수명이 짧기 때문에 사라짐,) 살아남은 메모리들은 다음 세대로 넘어감

다음 >> 타입 시스템