Structural data type, Runtime Environment

Structural data type 기본 자료형(elementary data type)

● 하나의 이름이 하나의 자료 객체(data object)를 가진 것

● 정수, 실수, 문자형 등

 

구조적 자료형(structured data type)

● 하나의 이름에 여러 개의 자료 객체가 있는 것

● 레코드, 배열, 문자열, 집합, 트리 등

      ○ 레코드, 구조체: 이질(heterogeneous)의 자료 개체들을 하나로 묶고 이름을 부여하여 하나의 자료형을 선언

      ○ PL/I, 코볼, 파스칼, C, 알골 등과 같은 언어는 레코드를 사용할 수 있는데 구체적 표현은 언어마다 조금씩 다르다.

 

 

Record 

레코드 ADDRESS

● PERSON, STREET, CITY와 같은 그룹 항목

● 각 항목들은 다시 하나 이상의 기본 자료형으로 구성.

● X(n)은 자료의 속성을 나타내는 PIC 구

      ○ n바이트로 구성되었다는 뜻

 

코볼 언어에서 레코드 구문은 다음 요소로 표현:

● 계층 번호(level number)

● 자료 이름(data name),

● 자료의 형과 길이에 따른 속성(attribute)

● level_num₁ data_name₁ PIC attribute

 

 

메모리에서 레코드가 저장되는 방법

● 자료형의 속성으로 서술된 이름(기본 항목)은 자신의 기억 공간을 필요

● 레코드에서 속성을 지닌 모든 자료 항목은 메모리에서 장소를 연속으로 할당

 

 

코드 ADDRESS에 대한 메모리 할당에서 만약 α가 레코드 ADDRESS의 시작 주소라고 할 때, 각 항목의 자료 길이를

바이트로 계산하면 다음과 같다.

 

 

Array

배열:

● 동질(homogeneous)의 자료 객체들을 묶고 그룹 이름을 부여

● 프로그램을 실행하는 동안 특정한 원소를 상대 주소로 직접 접근할 수 있도록 허용

● 배열의 요소들은 연속적으로 저장되면 빠르게 접근할 수 있어 실행 시간을 단축

 

C 언어 배열에서, int score [100];

● 배열 score는 정수형 자료 100개를 메모리에 연속적으로 기억시킬 수 있는 기억 공간을 필요로 한다.

 

각 배열 요소의 크기를 w라고 하면 배열 A의 i번째 요소는 다음 위치에서 시작한다.

base + (i - low + 1) × w … (1)

● low는 배열 첨자의 하한 값이며 1이라고 하자(Note: C 언어의 경우 하한 값이 0).

● base는 배열에 할당된 메모리의 상대 주소이다. 즉 base는 A[low]의 상대 주소이다. 식 (1)을 식 (2)로

      변환해보자.

(i + 1) × w + (base - low × w) … (2)

 

식 (2)는 컴파일 시간에 부분적으로 실행될 수 있다.

부분식 d = base - low × w는 배열의 선언이 나타나면 바로 계산될 수 있다.

즉 배열 A에 대한 기호표 항목 안에 d의 값이 계산 및 저장되면 A[i]의 상대 주소는 (i + 1) × w를 d에 더함으로써

계산된다.

 

다차원 배열을 다음과 같이 선언:

int board[2][3];

 

다차원 배열은 1차원으로 변환되어 메모리 에 저장

● 언어에 따라 하한 값과 상한 값이 달라짐

      ○ C 언어에서는 하한 값으로 0이 고정

      ○ 파스칼에서는 음수 또는 임의의 정수 사용 가능

      ○ 포트란은 하한 값이 1로 고정

 

1차원 배열로 변환하는 방법

● 행 우선(row-major)

● 열 우선(column-major)

● 슬라이스(slice)

 

 

다차원 배열을 1차원 배열로 저장하는 방법

● 언어마다 사용하는 방법이 다르므로 특성을 반영한다면 효율성 증대.

● C, 파스칼, PL/I 등은 row-major를 사용하고, 포트란은 column-major를 사용.

 

Row-major 방법으로 저장된 2차원 배열의 경우 A[i, j]의 상대 주소는 식 (3)과 같다.

base + ((i - low1) × n2) + (j - low2 + 1)) × w … (3)

(low1과 low2는 row과 column의 하한값이고, n2는 column의 크기)

 

Column-major 방식에 대해서도 2차원 배열의 경우 A[i, j]의 상대 주소는 식 (5)와 같다.

base + ((j - low2) × n1) + (i - low1 + 1)) × w … (5)

(n1는 row의 크기)

 

 

Example

 

다음과 같이 선언된 2차원 행렬에 대해 하한 값을 1로 하여 row-major, column-major 방식으로 각각 메모리에

저장하고, 각 경우에 대해 B(3,2)의 주소를 계산해보자.

int B(4,4);

 

row-major

base + ((i - low) * n2 + (j - low + 1)) * w

= base + ((3 - 1) * 4 + (2 - 1 + 1)) * 4

= base + (8 + 2) * 4 = base + 40

 

col-major

base + ((j - low) * n1 + (i - low + 1)) * w

= base + ((2 - 1) * 4 + (3 - 1 + 1)) * 4

= base + (4 + 3) * 4 = base + 28

 

 

Procedure Activation 

프로시저의 활성(activation): 프로시저가 실행되는 것

만약 어떤 프로시저가 재귀적(recursive)이 라면 다수의 활성이 동시에 존재할 수 있다.

 

프로시저 정의(procedure definition)는 id와 sentence을 연관시키는 선언이다.

● id는 프로시저 이름

● sentence는 프로시저 몸체(body)이다.

 

예를 들어 퀵 정렬(quick sorting) 프로그램 을 생각해보자.

 

 

3~7행은 프로시저 readarray의 정의를 하고 있으며, 여기서 5~7행은 프로시저 몸체 이다.

22~27 행은 주프로그램이며, 25행에서 프로시저 readarray를 호출하고 26행에서 프로시저 quicksort를 호출한다. 프로시저 정의에서 사용되는 식별자에는 매개변수가 있다.

매개변수는 형식 매개변수와 실 매개변수가 있는데, 12행의 식별자 m과 n이 프로시저 quicksort의 형식 매개변수

이고, 18행의 m과 i-1이 실 매개변수이다.

 

프로그램이 실행되는 동안 프로시저 사이에는 제어의 흐름이 존재한다.

제어는 순차적으로 이동하는데, 프로시저는 몸체의 처음부터 실행되다가 모든 실행이 끝나면 프로시저가 호출된 지점 바로 다음 위치에 제어를 돌려준다.

 

프로시저 p에 대한 존속 시간(life time)은 프로시저 몸체가 실행 되는 기간을 말한다.

존속 시간에는 p가 다시 프로시저를 호출 하여 그 프로시저를 실행하는 시간도 포함된다.

 

다음은 퀵소트 프로그램을 실행시킨 결과이다.

● partition(1,9)가 반환되는 값은 4라고 가정

● 활성 quicksort(1,9)의 존속 시간은 enter quicksort(1,9)와 leave quicksort(1,9) 사이

 

만약 어떤 프로시저의 새로운 활성이 그 프로시저의 이전 활성이 끝나기 전에 시작된다면 그 프로시저를

재귀적이라고 한다.

quicksort 프로시저는 재귀적이다.

 

제어가 활성에 들어가고 다시 나오는 과정을 트리로 표현한 것을 활성 트리(activation tree)라고 한다.

활성 트리의 각 노드는 하나의 활성을 나타내고, 루트 노드는 전체 프로그램을 시작하는 주프로그램의 활성이다.

 

프로시저 p의 자식 노드는 프로시저 p가 호출하는 활성 노드이다.

활성은 왼쪽에서 오른쪽으로 호출되며 자식 노드는 자신의 오른쪽에 있는 활성이 시작되기 전에 끝내야 한다.

 

 

Example

프로시저 호출과 반환에 대한 활성 트리를 그려보자.

 

 

Control Stack

 

프로시저의 호출과 반환은 제어 스택(control stack)이라고 불리는 실행 시간 스택이 관리

● 활성이 시작될 때 활성에 대한 노드를 스택에 삽입(push)

● 활성이 끝날 때 그 노드를 삭제(pop)

 

제어 스택의 내용: 활성 트리의 루트 노드로부터의 경로

 

Example q(2,3)에 대한 제어 스택을 그려보자.

 

 

Memory Organization

 

컴퓨터의 메모리 구성:

● 메모리 코드 부분

● 데이터 부분

 

대부분의 컴파일 언어에서는 실행하는 동안에 코드 부분을 변경할 수 없음.

코드와 자료 부분이 개념적으로 분리되어 있다.

코드 부분은 실행 이전에 고정되기 때문에 모든 코드에 대한 주소는 컴파일 시간에 알 수 있다.

특히 각 프로시저와 함수의 시작점(entry point)은 컴파일 시간에 알 수 있음

 

 

프로그램에서 전역 및 정적 자료는 일반적으로 코드와 유사한 형태로 고정 부분에 별개로 할당

● C 언어의 외부 및 정적 변수와 파스칼 언어의 전역 변수가 이러한 유형에 속한다.

 

스택은 할당이 LIFO(last-in, first-out) 방식으로 발생하는 자료에 사용

 

힙은 LIFO 방식을 따르지 않는 동적 할당(예: C에서 포인터 할당)에 사용

● Note: 힙은 단순 선형 메모리 구조.

 

 

위 사진에서 화살표는 스택과 힙의 확대 방향을 가리킨다.

 

전통적으로 스택은 메모리에서 아래 방향으로 확대되는 형태로 그리며, 그래서 톱은 그림에서는 아래 쪽에 그려진다.

 

힙은 스택과 유사하게 그려지지만 LIFO 구조가 아니고, 동적 할당이기 때문에 확대 및 축소는 화살표가 가리키는

것보다 실제로는 더욱 복잡

 

파스칼과 C 언어에서의 예시:

● 프로시저 활성을 관리하기 위해 제어 스택을 확장해서 사용.

● 호출이 일어날 때 활성은 실행을 잠시 멈추고, PC와 레지 터 값 같은 기계의 상태 정보를 스택에 저장

● 호출이 끝나고 제어가 반환될 때 호출 바로 뒤의 위치로 PC가 설정되고 관련된 레지스터 값이 다시 저장된 다음

     그 활성은 실행을 계속한다.

 

프로시저가 실행에 필요한 정보는 메모리 블록으로 관리되는 데,

● 이러한 연속 블록을 활성 레코드(activation record) 혹은 활성 프레임(activation frame)이라 한다.

● 활성 레코드는 실 매개변수, 반환 값, 지역 자료, 임시 값 을 저장하는 공간을 포함한다.

 

 

반환 값에 대한 공간: 호출한 프로시저로 결과 값이 전달될 때 사용한다.

반환 값은 효율을 위해 종종 레지스터에 담아 되돌려주기도 한다.

 

실 매개변수에 대한 공간: 호출 시 매개변수가 전달 되면 사용한다.

활성 레코드에 매개변수를 저장한다고 했지만 실제로는 효율을 위해 기계 레지스터를 통해 매개변수를 전달한다.

 

제어 링크: 생략 가능한 공간으로 자신을 호출한 프로시저의 활성 레코드를 가리킨다.

 

접근 링크: 생략 가능한 공간으로 다른 활성 레코드 에 있는 비지역 자료(nonlocal data)를 참조하는데 사 용된다.

파스칼 언어에서는 접근 링크가 필요하다.

 

기계 상태 저장 공간: 프로시저가 호출되기 바로 전의 기계 상태에 대한 정보를 저장한다.

 

지역 자료에 대한 공간: 프로시저가 실행될 때 지역적으로 사용되는 자료를 저장한다.

 

임시 변수에 대한 공간: 식을 계산하는 도중 발생하는 임시 값을 저장한다

 

 

Memory Allocation

 

실행 시간 환경Runtime Environment:

● 실행 과정을 관리하는 데 필요한 모든 정보를 유지해야 하고 메모리를 관리하는 역할

● 목적 컴퓨터의 레지스터와 메모리 구조가 실행 환경에 포함된다.

 

정적Static 및 동적Dynamic

● 정적: 프로그램이 실행될 때 무슨 일을 하는지 보지 않고 프로그램 텍스트만을 보고 메모리 할당을 결정

● 동적: 프로그램이 실행되는 중에 메모리 할당을 결정

 

정적 메모리 할당(static storage allocation): 프로그램이 실행될 때 이미 해당 메모리의 크기가 결정되는 방법으로

포트란 77 언어에서 사용된다.

스택 메모리 할당(stack storage allocation): 메모리를 스택으로 관리하는 방법으로 C, C++, 파스칼, 에이다와

같은 언어에서 사용된다.

힙 메모리 할당( heap storage allocation): 필요할 때마다 동적으로 메모리를 할당하고 해체하는 방법으로

함수 언어(functional language)에서 사용된다

 

 

Static Storage Allocation

 

정적 메모리 할당에서는

● 전역 변수뿐만 아니라 모든 변수가 정적으로 할당된다.

● 각 프로시저는 실행 전에 정적으로 할당되는 하나의 활성 레코드만 가지고 있다.

● 모든 변수는 지역적이든 전역적이든 고정 주소(fixed address)에 의해 직접적으로 접근할 수 있다.

 

정적 메모리 할당에서는 각 활성 레코드에 복귀 주소(return address) 이외 의 다른 정보를 유지할 필요가 없으므로

정보 측면에서 상대적으로 오버헤드가 작음

 

정적 메모리 할당의 호출 순서는 매우 단순

● 프로시저가 호출될 때 각각의 매개변수는 호출되는 프로시저의 활성에서 적절한 매개변수의 위치에 저장된다.

● 이후, 호출 프로그램 코드에 있는 복귀 주소가 저장되며, 호출된 프로시저 코드의 시작부로 분기가 실행된다.

      복귀할 때는 복귀 주소로 분기가 실행된다.

 

 

 

Example

 

● 주프로시저 TEST1과 부프로시저 QUMEAN으로 구성되어 있다.

● 이 프로그램에는 주프로시저와 QUMEAN 프로시저에서 COMMON MAXSIZE 선언에 의해 주어지는 1개의

      전역 변수가 있다.

      ○ COMMON 문장은 전역 변수로 서로 다른 프로시저에서 메모리를 공유하 는 것을 허용하는 문장이다.

● [그림]에서 화살표는 매개변수 A, SIZE, QMEAN이 주프로시저로부터의 호출 동안 참조되는 값을 가리킨다.

● 포트란 77에서는 매개변수 값이 묵시 적으로 참조 호출 값이며, 따라서 호출 자의 실 매개변수인

      TABLE, 3, TEMP 의 위치(location) 값은 QMEAN의 매 개변수 위치 값으로 복사된다.

 

 

Stack Memory Allocation 

 

재귀적 호출이 허용되고 지역 변수가 각각 호출할 때마다 새롭게 할당되는 언어에서는 활성 레코드가 정적으로

할당될 수 없다.

 

이 경우 활성 레코드가 스택 기반 형태로 할당되어야 하며, 새로운 프로시저가 호출 되면 스택의 톱에 할당되고 호출이 종료되면 활성 레코드가 스택에서 삭제된다.

 

스택 메모리 할당 방법은 실행 시간 스택(run-time stack) 또는 호출 스택(call stack) 이라고도 한다.

 

 

Example

 

제어가 이동함에 따라 실행 시간 스택에서 이뤄지는 삽입과 삭제에 대한 활성 레코드를 나타내보자.

 

 

 

● 프로그램은 프로시저 m의 활성에서 시작된다. 제어가 m(main)의 몸체 안에서 첫 번째로 r을 호출하면 프로시저

      r이 그 활성을 시작하고 r의 활성 레코드가 스택에 저장된다.

● 제어가 r의 실행을 끝내면 r에 대한 활성 레코드가 스택에서 삭제된다. 이때 스택에는 m에 대한 활성만 남는다.

      m의 활성에서 제어가 실 매개변수 1과 9를 가 지고 q를 호출하면 스택의 톱에는 q에 대한 활성이 할당된다.

● [그림]의 마지막 그림 전에는 몇 개의 활성이 발생했다가 사라진다.

● 마지막 그림에서 p(1,3)과 q(1,0)은 q(1,3)의 존속 시간 동안에 활성이 시작되고 끝난다. 그러므로 이것들의

      활성 레코드는 스택의 톱에 q(1,3)만을 남겨놓는다.

 

*점선은 이미 실행을 끝낸 활성 레코드

 

Stack Memory Allocation 

 

호출 순서와 활성 레코드는 서로 다르다.

 

호출 순서 안에 있는 코드

● 호출 프로시저(calling procedure, caller)

● 피호출 프로시저(called procedure, callee)

 

실행 시 호출자와 피호출자 사이의 작업을 명확하게 구분할 수는 없다. 소스 언어, 목적 기계, 운영체제에 따라

작업의 분담이 달라짐.

 

오른쪽 그림에서 레지스터 top_sp는 활성 레코드의 기계 상태 공간 끝을 가리킨다. 피호출자의 활성 레코드 내에

있는 이 지점은 호출자에게 알려지고, 호출자는 제어가 피호출자에게 전달되기 전에 top_sp 를 설정해야 한다.

 

 

호출 순서 및 호출자와 피호출자 사이의 스택 관리는 다음과 같다.

1. 호출자는 실 매개변수를 평가한다.

2. 호출자는 복귀 주소와 top_sp의 이전 값을 피호출자의 활성 레 코드에 저장한다. 그다음 호출자는 [그림]에

     나타낸 위치로 top_sp를 증가시킨다. 즉 top_sp는 호출자의 지역 자료와 임시 기 억 변수, 그리고 피호출자의

     매개변수와 상태 공간을 지나서 이동 한다.

3. 피호출자는 레지스터 값과 다른 상태 정보를 저장한다.

4. 피호출자는 자신의 지역 자료를 초기화하고 실행을 시작한다.

 

이에 대응하는 복귀 순서는 다음과 같다.

1. [그림 9-15]와 같이 피호출자는 반환 값을 매개변수 다음에 저장 한다.

2. 피호출자는 기계 상태 필드status field의 정보를 이용하여 top_sp와 다른 레지스터를 복원하고, 호출자가 상태 필드에 저장했 던 복귀 주소로 분기한다.

3. top_sp가 감소되었지만 호출자는 반환 값이 있는 위치를 top_sp 의 현재 값으로부터 상대적인 위치로 알 수 있다. 따라서 호출자는 이 값을 사용할 수 있다.

 

 

Example

 

음수가 아닌 2개의 정수에 대해 최대 공약수를 구하는 유클리드(Euclid) 알고리즘을 생각해보자.

이를 C 언어로 간 단하게 구현한 재귀적 프로그램은 다음과 같다.

이 프로그램을 보고 실행 시간 환경 중에 스택 메모리 할당을 설명 해보자.

 

#include <stdio.h>

int x, y;

int gcd(int u, int v)
{ 
    if (v == 0) return u;
    else return gcd(v, u % v); 
}

int main()
{
    scanf("%d%d", &x, &y);
    printf("%d\n", gcd(x, y));
    return 0;
}

 

사용자가 값 15와 10을 입력하면 x는 15, y는 10이 되고, main은 처음에 gcd(15,10)을 호출한다.

 

이 호출은 u가 15, v가 10이므로 15 % 10 = 5가 되어 재귀적 으로 gcd(10,5)를 호출한다.

 

이것은 10 % 5 = 0이므로 세 번째 재귀적으로 gcd(5,0)을 호 출한 다음 값 5를 반환한다.

 

 

Heap Memory Allocation

 

스택 메모리 할당 전략은 명령형(imperative) 언어 사이에서 표준적 방법이지만, 활성이 끝난 뒤에도 지역 변수의

값을 유지해야 하는 경우나 호출된 활성이 호출자가 사라진 뒤에도 살아 있어야 하는 경우에는 사용 불가

 

이런 경우에는 무기한 살아 있거나 프로그램이 명시적으로 제거할 때까지 살아 있는 자료를 저장하는 힙을 사용하여

해결 가능

● 지역 변수는 보통 해당 프로시저가 끝나면 접근할 수 없게 되지만, 많은 언어에서는 해당 프로시저의 활성화에

     종속되지 않는 존속 시간을 가진 객체나 다른 자료를 사용할 수 있다.

● 예를 들어 C++와 자바는 new로 생성한 객체를 프로시저 간에 전달할 수 있다. 따라서 이런 객체는 자신을

     생성한 프로시저가 종료된 후에 도 계속 존재할 수 있다.

 

힙 메모리 할당은 연속적인 기억 공간을 꾸러미로 만들어 활성 레코드나 다른 객체에 할당하는 전략.

이 꾸러미는 다른 순서로 해체될 수 있으므로 힙은 사용 중인 영역과 사용되지 않고 있는 영역(free area)으로

섞어서 구성할 수 있다.

 

힙 메모리 할당은 모든 참조가 없어질 때만 활성 레코드를 해제할 수 있으며, 활성 레코드를 동적으로 실행하는 동안

임의의 시점에 해제되어야 하기 때문 에 동적 메모리 할당이라고도 부른다.