지난 글에서는 스택 프레임의 개념에 대해 정리하였다. 스택프레임은 스택이라는 메모리 공간을 차지하는 기본 단위이다. 서브루틴을 호출할 때마다 레지스터와 스택프레임이 할당된다. 이때 할당되는 스택프레임의 크기는 save 명령어를 통해 지정할 수 있는데, 최소 사이즈는 64바이트였다. (l-register, i-register 저장 용도) 만약 스택 프레임 내에서 또다른 함수를 호출한다면, 구조체 반환 포인터 크기 4byte와, 매개변수 전달 용도의 24byte 사이즈 공간이 추가로 더 필요해 최소 92byte 사이즈가 필요했다. 여기에 만약 지역변수를 추가로 사용한다면 사용할 지역변수의 총 사이즈만큼 추가로 할당이 필요했다. 마지막으로 총 사용하는 사이즈 크기를 8의 배수로 맞춰 생성해야 한다. 스택 프레..
지난 글에서는 SPARC의 (근데 찾아보니 아마도 기본적인 컴퓨터 공통의) 메모리 맵을 정리하면서 BSS 섹션의 내용을 추가로 정리하였다. bss 섹션은 정적 메모리 영역 중 하나로, 이곳에 할당한 변수는 모두 0으로 초기화되는 특징이 있었다. 이번 글에서는 다시 '스택' 영역으로 돌아와서, 새로운 스택 영역의 메모리를 할당하는 단위인, '스택 프레임' 에 대해 정리하고자 한다. Stack Frame (스택 프레임) 스택 프레임은 나중에 정리할 '서브루틴' 과 관련되어 있다. 서브루틴(함수)는 호출될 때마다, 레지스터 공간과 함께 스택 공간을 새로 할당한다. 이때 각 함수마다 할당하는 스택 공간의 크기를 임의로 지정할 수 있는데, 이 스택 공간을 '스택 프레임' 이라고 한다. 즉, 스택 프레임은 서브루틴..
지난 글에서는 set 합성 명령어의 구조와 작동 원리를 알아보았다. set 명령어는 sethi 명령어와 or 명령어의 조합으로 이루어져 있으며, sethi 명령어는 피연산자로 들어온 메모리 주소값의 상위 22비트를 마찬가지 피연산자로 들어온 레지스터의 상위 22비트에 쓰는 명령어이다. or 명령어로는 나머지 하위 10 비트의 데이터를 레지스터의 하위 10비트에 쓴다. (32비트의 주소값 데이터를 2번에 걸쳐 레지스터에 쓴다.) 이번 글에서는 SPARC의 메모리 맵을 다시 한번 살펴보면서 지난번에 정리하지 못했던 정적 메모리 영역 중 bss 영역에 대해 추가적으로 정리하고자 하려고 했으나... 강의록에 bss 부분에 대한 내용이 너무 없어서 그냥 SPARC 메모리 맵을 복습하는 느낌으로 작성하려고 한다. ..
data영역 메모리에 데이터를 저장하고 나서 메모리에 저장된 데이터를 가져오기 위해 그 메모리 위치를 label로 표시할 수 있다. 이때, 문자열로된 label로부터 실제 메모리 주소값을 가져오는 명령어가 set 이다. .data i_m: .word 4 j_m: .word 9 k_m: .word 3 위 코드에서는 data 영역에 4바이트 크기의 메모리 공간 3개에 각각 4, 9, 3을 저장하고, 각 메모리 주소를 i_m, j_m, k_m 으로 표시하였다. 이때 i_m, j_m, k_m 이 가리키는 메모리 주소는 아래와 같이 가져올 수 있다. set i_m, %o0 위 코드는 i_m의 주소값을 가져와서 %o0 레지스터에 저장하는 코드이다. 한편, 지난 지연주기 최적화 글에서 set은 nop에 바로 넣을 수..
지난 글에서는 이진 탐색트리의 개념과 Search, Add, Delete 의 구현에 대해 정리하였다. 이번 글에서는 BST의 핵심인 '탐색' 과 탐색 시간에 대해 좀 더 깊게 정리해보자. BST의 탐색 시간 모든 BST의 기능 중에서 제일 중요한 것은 BST 의 이름에도 들어있는 '탐색' 기능이다. 탐색 시간이 얼마나 걸리는지 ( 탐색을 위해 비교를 몇 번이나 하는지) 는 어떻게 측정할까? 답은 정확하게 BST 의 노드 중 찾으려는 노드의 depth + 1 (level + 1) 이다. 더보기 [트리에서 Depth, Height, Level ] Depth = 루트 노드의 depth를 0 으로 정의할 때, 자식 노드의 depth는 부모 노드의 depth + 1 이다. Level = Depth 와 같다. de..
이진 탐색 트리 (Binary Search Tree, BST) 는 노드가 정렬되어 있어 탐색을 수행할 수 있는 이진 트리를 말한다. 각 노드는 여러개의 필드로 이루어진 데이터를 가지고 있다고 가정한다. 데이터 중에서 탐색을 하기 위해 사용되는 데이터를 '키' 라고 한다. node v 의 키를 key(v) 라고 정의하면, BST 는 모든 노드 u 에 대해서 아래를 만족하는 이진트리이다. (1) 만약 v 가 u 의 왼쪽 서브트리에 있다면 key(v) key(u) 이다. 등호는 좌, 우 둘 중 하나 어디든 들어가도 되지만, 왼쪽에 들어간 것으로 생각하자. 이 정의를 통해 이진 탐색 트리는 매우 효율적으로 원하는 key 를 탐색할 수 있다. 이제 이렇게 생긴 BST가 있다고 가정해보자. 이 트리에서 3이라는 값..
지난 글에서는 트리와 이진트리, 그리고 이진 트리를 만들 수 있는 가짓수인 카탈란 수에 대해서 정리하였다. 이번 글에서는 이진 트리를 순회하는 3가지 방법을 정리해보고자 한다. 사람에 관점에서는 이진트리의 전체적인 모습이 보이기 때문에 특정 노드를 찾을 때 전체 이진트리에서 특정 노드를 바로 딱 보면 쉽게 알 수 있다. (글로벌 뷰) 하지만 컴퓨터 입장에서 이진트리를 탐색할 때는, 연결리스트 때와 비슷하게, 현재 자신이 보고 있는 노드 T와, 그 T의 ITEM(T), 왼쪽 노드 LEFT(T) , 오른쪽 노드 RIGHT(T) 만 본다. (로컬뷰) 이런 로컬 뷰가 재귀적으로 반복되기 때문에, 이진트리를 탐색할 때는 재귀를 이용하게 되는데, 이진 트리를 재귀적으로 탐색하는 방법에는 3가지가 있다. Preord..
지난 글에서는 메모리와 레지스터 사이 데이터를 주고받는 방법을 정리해보았다. 간단히 정리하면, ld [메모리주소], 레지스터 형태로 메모리에서 값을 불러온다. 메모리주소는 불러올 데이터 크기의 배수여야한다. 만약 ldd 로 8byte 를 불러온다면 레지스터는 짝수번째 레지스터여야한다. 메모리주소는 레지스터와 레지스터(상수) 합으로 표현되며, -레지스터만 없으면 된다. st 레지스터, [메모리주소] 형태로 레지스터 값을 메모리에 저장한다. 마찬가지로 메모리 주소는 저장할 데이터 크기의 배수여야 하고 만약 std 로 8byte 를 저장한다면 레지스터는 짝수번째 레지스터여야 한다. 메모리주소는 레지스터와 레지스터(상수) 합으로 표현되며, -레지스터만 없으면 된다. 이번 글에서는 메모리의 영역 중 static ..
지난 글에서는 연결리스트가 사용하는 메모리 공간을 어떻게 관리하는지 그 구현을 C언어로 직접 해보았다. 이번 글에서는 트리와 이진트리의 개념을 정리해보고자 한다. 트리 트리는 아래와 같이 정의된다. a tree is a finite set T of nodes such that 1) T has one special node called root 2) the remaining nodes are partitioned into m disjoint sets T1, T2, ... Tm, and each of these sets is turn to a tree. wee call them subtrees of T 트리는 '루트' 라고 불리는 특별한 하나의 노드를 가지고 있고, 나머지 노드들은 m 개의 서브트리를 이루는..
메모리 개요 메모리는 프로그램의 명령어와, 그 명령어가 사용할 데이터가 들어있는 공간이다. (폰 노이만 구조에서는 프로그램의 명령어도 데이터이다.) 저장 단위는 byte 단위이며, 레지스터와 달리 4byte로 고정되지 않고 1, 2, 4, 8 byte 등으로 유동적인 사이즈로 저장할 수 있다. 하지만 레지스터가 한번에 4byte 씩 파악하기 때문에, 명령어의 사이즈는 4byte 로 고정되어있다. 메모리 접근 메모리에 접근하여 데이터를 읽고 쓰는 명령어는 기본적으로 아래와 같은 형태를 띈다. Load, 메모리의 데이터를 불러와(loading) 레지스터에서 읽는 것 ld [메모리주소], 레지스터주소 메모리 -> 레지스터 순서로 읽으면 되니 이해가 간단하다. 메모리주소는 R + A 형태로 표현되고, [ ] 는..
