PowerPoint 프레젠테이션

Transcription

1 Chapter 09 구조적자료형과실행시간환경

2 01 구조적자료형 02 메모리구성 03 메모리할당전략 04 매개변수전달방법

3 레코드, 배열등구조적자료형에대해이해할수있다. 메모리구성에대해이해할수있다. 정적메모리할당, 스택메모리할당, 힙메모리할당등메모리할당전략에대해이해할수있다. 값호출, 참조호출, 이름호출, 값-결과호출등매개변수전달방법에대해서이해할수있다.

4 9.1 구조적자료형 실행시필요한모든환경인실행시간환경에대해설명한다. 실행시간환경은매우다양한데, 구조적자료가어떻게구현되는지구조적자료형과메모리구성및메모리할당전략을살펴보고, 변수및데이터가어떻게접근하는지매개변수전달방법에대해서도다룬다 구조적자료형 (structured data type) 과기본자료형 (elementary data type) 에대해알아보자. 기본자료형은하나의이름이하나의자료객체 (data object) 를가진것으로정수, 실수, 문자형을말한다. 구조적자료형은하나의이름에여러개의자료객체가있는것으로레코드, 배열, 문자열, 집합, 트리등을말한다. 레코드 많은언어에서는이질 (heterogeneous) 의자료개체들을하나로묶고여기에그룹이름을부여하여하나의자료형을선언할수있는데, 이러한형태의구조적자료형을레코드또는구조체라고한다. PL/I, 코볼, 파스칼, C, 알골등과같은언어는레코드를사용할수있는데레코드의표현은언어마다조금씩다르다. 예를들어코볼언어의레코드는 [ 그림 9-1] 과같다. 4

5 9.1 구조적자료형 [ 그림 9-1] 에서레코드 ADDRESS 는 PERSON, STREET, CITY 와같은그룹항목으로되어있고, 이것들은다시하나이상의기본자료형으로구성되어있다. X(n) 은자료의속성을나타내는 PIC 구로 n 바이트로구성된자료의길이이다. 코볼언어에서레코드에대한일반적인구문은계층번호 (level number) 와자료이름 (data name), 자료의형과길이에따른속성 (attribute) 에의해다음과같이표현된다. level_num₁ data_name₁ PIC attribute₁ 5

6 9.1 구조적자료형 [ 그림 9-1] 에서레코드 ADDRESS 는 PERSON, STREET, CITY 와같은그룹항목으로되어있고, 이것들은다시하나이상의기본자료형으로구성되어있다. X(n) 은자료의속성을나타내는 PIC 구로 n 바이트로구성된자료의길이이다. 메모리에서레코드가어떻게저장되는지살펴보자. 자료형의속성으로서술된이름 ( 기본항목 ) 은자신의기억공간을필요로한다. 그러므로레코드에서속성을지닌모든자료항목은메모리에서장소를연속으로할당받음. [ 그림 9-1] 의레코드 ADDRESS 에대한메모리할당과자료이름의관계 6

7 9.1 구조적자료형 [ 그림 9-2] 의레코드 ADDRESS 에대한메모리할당에서만약 α 가레코드 ADDRESS 의시작주소라고할때, 각항목의자료길이를바이트로계산하면다음과같다. 7

8 9.1 구조적자료형 배열 동질 (homogeneous) 의자료객체들을묶고여기에그룹이름을부여하는배열 프로그램을실행하는동안특정한원소를상대주소로직접접근할수있도록허용 C 언어에서배열이다음과같이선언될때, 배열 score 는정수형자료 100 개를메모리에연속적으로기억시킬수있는기억공간을필요로한다. int score [100]; 배열의요소들은연속적으로저장되면빠르게접근할수있어실행시간이단축된다. 다음과같이가정하고위치를계산해보자. 각배열요소의크기를 u 라고하면배열 A 의 i 번째요소는다음위치에서시작한다. base + (i - low + 1) w (9.1) 여기서 low 는배열첨자의하한값이며 1 이라고하자 (C 언어의경우하한값이 0 이므로주소계산이달라진다 ). base 는배열에할당된메모리의상대주소이다. 즉 base 는 A[low] 의상대주소이다. 또한 w 는각요소의크기이다. 식 (9.1) 을식 (9.2) 로변환해보자. (i + 1) w + (base - low w) (9.2) 식 (9.2) 는컴파일시간에부분적으로실행될수있다. 부분식 d = base - low w 는배열의선언이나타나면바로계산될수있다. 즉배열 A 에대한기호표항목안에 d 의값이계산및저장되면 A[i] 의상대주소는단순히 (i + 1) w 를 d 에더함으로써계산된다. 8

9 9.1 구조적자료형 같은방법으로다차원배열을다음과같이선언한다. int board[2][3]; board 는각각원소가연속된메모리영역을할당하지만 board[1][2] 가자료영역에서몇번째셀에해당되는지쉽게알수없다. 그러나논리적인배열의구조는메모리에서 1 차원배열로정돈되기때문에손쉽게상대적인위치를계산해낼수있는반면에다차원배열은언어에따라하한값과상한값이달라질수있다. C 언어에서는하한값으로 0 이고정되어있으나파스칼에서는하한값이음수또는임의의정수로서술될수있다. 또한포트란언어는하한값이 1 로고정되어있다. 2 차원배열을메모리에저장하기위해 1 차원배열로변환하는방법은행우선 (rowmajor), 열우선 (column-major), 슬라이스 (slice) 등여러가지방법이있다. [ 그림 9-3] 은행우선및열우선방법으로저장된 2 3 배열 A 의내용을보여준다. 슬라이스는배열에서어떤부분의구조이다. 9

10 9.1 구조적자료형 다차원배열을 1 차원배열로저장하는방법 언어마다사용하는방법이다르므로이런특성을반영한다면매우효율적인프로그래밍이가능할것이다. C, 파스칼, PL/I 등은행우선방법을사용하고, 포트란은열우선방법을사용한다. 행우선방법으로저장된 2 차원배열의경우 A[i, j] 의상대주소는식 (9.3) 과같다. base + (((i - low1) n2) + (j - low2 + 1)) w (9.3) 10

11 9.1 구조적자료형 여기서 low1 과 low2 는 i 와 j 의하한값이고, n2 는열의크기로 j 가취할수있는값의크기이다. 즉 high2 를 j 에대한상한값이라고하면 n = high2 - low2 + 1 이다. A[i, j] 의상대주소를계산하는데컴파일시간에 i 와 j 의값만모르고다른값들을모두안다면식 (9.3) 은식 (9.4) 와같이다시쓸수있다. ((i n) + (j + 1)) w + (base - ((low1 n) + low2) w) (9.4) 식 (9.4) 의뒷부분은컴파일시간에계산할수있다. 같은방법으로열우선에대해서도 2 차원배열의경우 A[i, j] 의상대주소는식 (9.5) 와같다. base + (((j - low1) n1) + (i - low2 + 1)) w (9.5) n1 은행단위의원소개수로 i 가취할수있는값의크기이다. 11

12 9.1 구조적자료형 [ 예제 9-1] 행우선과열우선에따른주소계산하기 다음과같이선언된 2 차원행렬에대해하한값을 1 로하여행우선과열우선으로메모리에저장하고, 행우선과열우선에대해 B(3,2) 의주소를계산해보자. int B(4,4); [ 풀이 ] 행우선방법으로메모리에저장하면다음과같다. 열우선방법으로메모리에저장하면다음과같다. 12

13 9.1 구조적자료형 원소 B(3,2) 에대한상대주소를계산한다. 그림의화살표를보면행우선방법은열번째이고열우선방법은일곱번째임을알수있다. 또한각원소가정수형이므로 4 바이트를할당한다면주소는 base 로부터행우선의경우 40, 열우선의경우 28 이어야한다. 식 (9.3) 에의하면 i 는 3, j 는 2, low1 은하한값이므로 1, low2 도 1, n2 는열의크기이므로 4, w 는 4 이므로다음과같다. base + (((i - low1) n2) + (j - low2 + 1)) w = base + (((3-1) 4) + ( )) 4 = base + (8 + 2) 4 = base + 40 같은방법으로열우선으로계산하기위해식 (9.5) 를사용한다. 여기서 i 는 3, j 는 2, low1 은하한값이므로 1, low2 도 1, n1 은행의크기이므로 4, w 는 4 이므로다음과같다. base + (((j - low1) n1) + (i - low2 + 1)) w = base + (((2-1) 4) + ( )) 4 = base + (4 + 3) 4 = base

14 9.2 메모리구성 프로시저가실행되는것을프로시저의활성 (activation) 만약어떤프로시저가재귀적 (recursive) 이라면몇개의활성이동시에존재할수있다. 프로시저정의 (procedure definition) 는가장간단한형태로식별자와문장을연관시키는선언이다. 식별자는프로시저이름이고, 문장은프로시저몸체 (body) 이다. 예를들어 [ 그림 9-4] 의퀵정렬 (quick sorting) 프로그램을생각해보자. 14

15 9.2 메모리구성 15

16 9.2 메모리구성 [ 그림 9-4] 의 3~7 행은 readarray 라는프로시저정의를하고있으며, 여기서 5~7 행은프로시저몸체이다. 프로시저가호출되었다는것은프로시저이름이실행가능한문장에나타난경우이다. 22~27 행은주프로그램이며, 25 행에서프로시저 readarray 를호출하고 26 행에서프로시저 quicksort 를호출한다. 프로시저정의에서사용되는식별자에는매개변수가있다. 매개변수는형식매개변수와실매개변수가있는데, [ 그림 9-4] 에서는 12 행의식별자 m 과 n 이프로시저 quicksort 의형식매개변수이고, 18 행의 m 과 i-1 이실매개변수이다. 즉프로시저를호출하는데있는매개변수가실매개변수이고, 프로시저호출을받는데있는매개변수가형식매개변수이다. 프로그램이실행되는동안프로시저사이에는제어의흐름이존재한다. 제어는순차적으로이동하는데, 프로시저는몸체의처음부터실행되다가모든실행이끝나면프로시저가호출된지점바로다음위치에제어를돌려준다. 프로시저 p 에대한존속시간 (life time) 은프로시저몸체가실행되는기간을말한다. 존속시간에는 p 가다시프로시저를호출하여그프로시저를실행하는시간도포함된다. [ 그림 9-4] 의프로그램을실행시킨결과는 [ 그림 9-5] 와같다. 여기서 partition(1,9) 가반환되는값은 4 라고가정하며, 활성 quicksort(1,9) 의존속시간은 enter quicksort(1,9) 와 leave quicksort(1,9) 사이이다. 16

17 9.2 메모리구성 17

18 9.2 메모리구성 만약어떤프로시저의새로운활성이그프로시저의이전활성이끝나기전에시작된다면그프로시저를재귀적이라고한다. quicksort 프로시저는재귀적이다. 제어가활성에들어가고다시나오는과정을트리로표현한것을활성트리 (activation tree) 라고한다. 활성트리의각노드는하나의활성을나타내고, 루트노드는전체프로그램을시작하는주프로그램의활성이다. 프로시저 p 의자식노드는프로시저 p 가호출하는활성노드이다. 활성은왼쪽에서오른쪽으로호출되며자식노드는자신의오른쪽에있는활성이시작되기전에끝내야한다. [ 예제 9-2] 프로시저호출과반환에대한활성트리그리기 [ 그림 9-5] 에있는프로시저호출과반환에대한활성트리를그려보자. [ 풀이 ] 각프로시저는프로시저의첫번째글자로만나타낸다. 활성트리의루트노드는주프로그램인 main 을나타낸다. main 이실행되는동안루트노드의첫번째자식노드로라벨이 r 이라붙은 readarray 의활성이존재한다. 루트노드의두번째자식노드는 quicksort(1,9) 이다. 같은방법으로활성트리를만들어갈수있다. 활성 q(1,3) 과 q(5,9) 는재귀적프로시저이며, q(1,3) 과 q(5,9) 는 q(1,9) 가끝나기전에시작되고 q(1,9) 보다먼저끝마쳐야한다. 전체적인활성트리는 [ 그림 9-6] 과같다. 여기서 m 은 main, r 은 readarray, q(1,9) 는 quicksort(1,9), p(1,9) 는 partition(1,9) 를나타낸다. 18

19 9.2 메모리구성 19

20 9.2 메모리구성 프로시저의호출과반환은제어스택 control stack 이라고불리는실행시간스택이관리한다. 즉, 활성이시작될때활성에대한노드를스택에삽입 (push) 하고활성이끝날때그노드를삭제 (pop) 한다. 그러므로제어스택의내용은활성트리의루트노드에대한경로와관계있는것이다. [ 예제 9-3] 제어스택그리기 [ 그림 9-6] 의 q(2,3) 에대한제어스택을그려보자. 루트로부터 q(2,3) 으로가는경로를나타낸 [ 그림 9-7] 에서이미활성이수행된것은점선으로표시하고, 루트 m 으로부터 q(2,3) 으로가는경로는실선으로표시했다. 제어스택은실선으로표시된경로에해당하는노드를저장하고있다. 즉제어스택에는다음과같이저장되어있다. m, q(1,9), q(1,3), q(12,3) 20

21 9.2 메모리구성 21

22 9.2 메모리구성 메모리구성 전형적인컴퓨터의메모리구성은 [ 그림 8-8] 과같이메모리코드부분과데이터부분으로더욱세분할수있다. 대부분의컴파일언어에서는실행하는동안에코드부분을변경할수없으며, 코드와자료부분이개념적으로분리되어있다. 더욱이코드부분은실행이전에고정되기때문에모든코드에대한주소는컴파일시간에알수있다. 특히각프로시저와함수의시작점 (entry point) 은컴파일시간에알수있다. 실행할때의코드메모리구성은 [ 그림 9-8] 과같다. 22

23 9.2 메모리구성 프로그램에서전역및정적자료는일반적으로코드와유사한형태로고정부분에별개로할당된다. C 언어의외부및정적변수와파스칼언어의전역변수가이러한유형에속한다. 동적자료할당에사용되는메모리부분은여러가지다른방법으로구성될수있다. 전형적인구조는이부분에대한메모리가스택부분과힙부분으로나뉘는데, 스택부분은할당이 LIFO(last-in, first-out) 방식으로발생하는자료에사용되고, 힙부분은 LIFO 방식을따르지않는동적할당 ( 예를들어 C 에서포인터할당 ) 에사용된다. 힙은일반적으로단순한선형메모리부분이라는것을주목해야한다. 포인터할당및해제를처리하는데는어떤동적인장치가필요한데그러한할당을처리하는자료구조가바로힙이다. 지금까지설명한실행시간메모리의일반적인구조는 [ 그림 8-8] 과같다. 좀더부연설명을하기위해 [ 그림 8-8] 을간단하게 [ 그림 9-9] 로나타냈다. 23

24 9.2 메모리구성 [ 그림 9-9] 에서화살표는스택과힙의확대방향을가리킨다. 전통적으로스택은메모리에서아래방향으로확대되는형태로그리며, 그래서톱은실제적으로그려진구역의바닥에그려진다. 힙은스택과유사하게그려지지만 LIFO 구조가아니고, 그확대및축소는화살표가가리키는것보다더욱복잡하다. 24

25 9.2 메모리구성 파스칼과 C 언어에서는프로시저활성을관리하기위해제어스택을확장해서사용한다. 호출이일어날때활성은실행을잠시멈추고, 프로그램계수기와레지스터값같은기계의상태정보를스택에저장한다. 호출이끝나고제어가반환될때호출바로뒤의위치로프로그램계수기가설정되고관련된레지스터값이다시저장된다음그활성은실행을계속한다. 프로시저가한번실행되는데필요한정보는메모리의연속블록을사용하여관리되는데, 이러한연속블록을활성레코드 (activation record) 혹은활성프레임 (activation frame) 이라한다. 활성레코드는실매개변수, 반환값, 지역자료, 임시값을저장하는공간을포함한다. 일반적인활성레코드는 [ 그림 9-10] 과같다. 25

26 9.2 메모리구성 모든언어와컴파일러가 [ 그림 9-10] 의공간을다사용하는것은아니다. 또한공간에대한자료의순서를포함하는특수상세사항은목표기계의구조, 컴파일되는언어의특성, 심지어컴파일러작성자의취향에따라다를수있다. 파스칼과 C 언어는프로시저가호출될때실행스택에프로시저의활성레코드를삽입하고, 제어가호출한쪽으로되돌아갈때스택에서활성레코드를삭제한다. [ 그림 9-10] 의각공간에대해살펴보면다음과같다. 반환값에대한공간 : 호출한프로시저로결과값이전달될때사용한다. 반환값은효율을위해종종레지스터에담아되돌려주기도한다. 실매개변수에대한공간 : 호출시매개변수가전달되면사용한다. 활성레코드에매개변수를저장한다고했지만실제로는효율을위해기계레지스터를통해매개변수를전달한다. 제어링크 : 생략가능한공간으로자신을호출한프로시저의활성레코드를가리킨다. 접근링크 : 생략가능한공간으로다른활성레코드에있는비지역자료 nonlocal data 를참조하는데사용된다. 파스칼언어에서는접근링크가필요하다. 기계상태저장공간 : 프로시저가호출되기바로전의기계상태에대한정보를저장한다. 지역자료에대한공간 : 프로시저가실행될때지역적으로사용되는자료를저장한다. 임시변수에대한공간 : 식을계산하는도중발생하는임시값을저장한다 26

27 9.2 메모리구성 언어에따라서는활성레코드가정적부분 ( 포트란 77), 스택부분 (C, 파스칼 ), 혹은힙부분 ( 리스프 ) 에할당된다. 활성레코드가스택에서유지될때그것을스택프레임이라고도부른다. 프로세서레지스터도실행시간환경의일부분이다. 레지스터는임시변수, 지역변수, 전역변수를저장하는데사용될수있다. 실행시간환경의설계에서특별히중요한부분은프로시저나함수가호출될때발생하는연산의순서결정이다. 이러한연산은활성레코드에대한메모리할당, 매개변수의계산과저장, 호출이이뤄지는데필요한레지스터를저장하고설정하는것을포함하며, 일반적으로호출순서 (calling sequence) 로언급된다. 프로시저나함수가반환될때호출자가접근할수있는장소에반환값을두는것, 레지스터의재조정, 활성레코드에대한메모리재조정등이호출순서에해당된다. 27

28 9.3 메모리할당전략 실행시간환경은실행과정을관리하는데필요한모든정보를유지해야하고메모리를관리하는역할 특히실행과정을관리하는데필요한정보를유지하고메모리를관리하는역할을하는목적컴퓨터의레지스터와메모리구조가실행환경에포함된다. [ 그림 9-9] 의메모리구조에서자료영역에대해메모리할당전략이필요하다. 정적및동적이라는용어는각각컴파일시간과실행시간을구별하는데사용된다. 메모리할당이정적이라면프로그램이실행될때무슨일을하는지보지않고프로그램텍스트만을보고메모리할당을결정한다. 메모리할당이동적이라면프로그램이실행되는중에메모리할당을결정한다. 동적할당을위해많은컴파일러에는스택메모리할당과힙메모리할당이있다. 세가지메모리할당전략 정적메모리할당 (static storage allocation) : 프로그램이실행될때이미해당메모리의크기가결정되는방법으로포트란 77 언어에서사용된다. 스택메모리할당 (stack storage allocation) : 메모리를스택으로관리하는방법으로 C, C++, 파스칼, 에이다와같은언어에서사용된다. 힙메모리할당 (( heap storage allocation) : 필요할때마다동적으로메모리를할당하고해체하는방법으로함수언어 (functional language) 에서사용된다 28

29 9.3 메모리할당전략 정적메모리할당 (static storage allocation) : 정적메모리할당에서는전역변수뿐만아니라모든변수가정적으로할당된다. 각프로시저는실행전에정적으로할당되는하나의활성레코드만가지고있다. 모든변수는지역적이든전역적이든고정주소 (fixed address) 에의해직접적으로접근할수있다. 29

30 9.3 메모리할당전략 정적메모리할당에서는각활성레코드에복귀주소 (return address) 이외의다른정보를유지할필요가없으므로정보측면에서상대적으로오버헤드가작다. 또한정적메모리할당의호출순서가매우단순하다. 프로시저가호출될때각각의매개변수는호출되는프로시저의활성에서적절한매개변수의위치에저장된다. 그런다음호출프로그램코드에있는복귀주소가저장되며, 호출된프로시저코드의시작부로분기가실행된다. 복귀할때는복귀주소로분기가실행된다. [ 예제 9-4] 정적메모리할당에대한메모리구조 [ 그림 9-12] 의포트란 77 프로그램을보고정적메모리할당에대한메모리구조에대해설명해보자. 30

31 9.3 메모리할당전략 31

32 9.3 메모리할당전략 [ 그림 9-12] 의프로그램은주프로시저 TEST1 과부프로시저 QUMEAN 으로구성되어있다. 이프로그램에는주프로시저와 QUMEAN 프로시저에서 COMMON MAXSIZE 선언에의해주어지는 1 개의전역변수가있다. COMMON 문장은전역변수로서로다른프로시저에서메모리를공유하는것을허용하는문장이다. [ 그림 9-13] 은 [ 그림 9-12] 에대해메모리에서정수와실수값사이의크기를고려하지않은실행시간환경이다. 32

33 9.3 메모리할당전략 [ 그림 9-13] 에서화살표는매개변수 A, SIZE, QMEAN 이주프로시저로부터의호출동안참조되는값을가리킨다. 포트란 77 에서는매개변수값이묵시적으로참조호출값이며, 따라서호출자의실매개변수인 TABLE, 3, TEMP 의위치 (location) 값은 QUMEAN 의매개변수위치값으로복사된다. 33

34 9.3 메모리할당전략 스택메모리할당 : 재귀적호출이허용되고지역변수가각각호출할때마다새롭게할당되는언어에서는활성레코드가정적으로할당될수없다. 대신에활성레코드가스택기반형태로할당되어야하며, 이경우에새로운활성레코드는새로운프로시저가호출되면스택의톱에할당되고호출이종료되면활성레코드가삭제된다. 스택메모리할당방법은실행시간스택 (run-time stack) 또는호출스택 (call stack) 이라고도한다. [ 예제 9-5] 실행시간스택에서이뤄지는삽입과삭제에대한활성레코드 [ 그림 9-6] 의활성트리를통해제어가이동함에따라실행시간스택에서이뤄지는삽입과삭제에대한활성레코드를나타내보자. [ 풀이 ] [ 그림 9-14] 는실행시간스택에서이뤄지는활성레코드를보여준다. 34

35 9.3 메모리할당전략 35

36 9.3 메모리할당전략 [ 그림 9-14] 에서점선은이미실행을끝낸활성레코드이다. 프로그램은프로시저 m 의활성에서시작된다. 제어가 m(main) 의몸체안에서첫번째로 r 을호출하면프로시저 r 이그활성을시작하고 r 의활성레코드가스택에저장된다. 제어가 r 의실행을끝내면 r 에대한활성레코드가스택에서삭제된다. 이때스택에는 m 에대한활성만남는다. m 의활성에서제어가실매개변수 1 과 9 를가지고 q 를호출하면스택의톱에는 q 에대한활성이할당된다. [ 그림 9-14] 의마지막그림전에는몇개의활성이발생했다가사라진다. 마지막그림에서 p(1,3) 과 q(1,0) 은 q(1,3) 의존속시간동안에활성이시작되고끝난다. 그러므로이것들의활성레코드는스택의톱에 q(1,3) 만을남겨놓는다. 호출순서와활성레코드는서로다르다. 호출순서안에있는코드는보통두가지로나뉘는데호출프로시저 (calling procedure, caller) 와피호출프로시저 (called procedure, callee) 가그것이다. 실행시호출자와피호출자사이의작업을명확하게구분할수는없다. 소스언어, 목적기계, 운영체제에따라작업의분담이달라지기때문이다. 호출자와피호출자가어떻게협력하여스택을관리하는지에대한예를 [ 그림 9-15] 에나타냈다. 36

37 9.3 메모리할당전략 [ 그림 9-15] 에서처럼레지스터 top_sp 는활성레코드의기계상태공간끝을가리킨다. 피호출자의활성레코드내에있는이지점은호출자에게알려지고, 호출자는제어가피호출자에게전달되기전에 top_sp 를설정해야한다. 37

38 9.3 메모리할당전략 호출순서및호출자와피호출자사이의스택관리는다음과같다. 1 호출자는실매개변수를평가한다. 2 호출자는복귀주소와 top_sp 의이전값을피호출자의활성레코드에저장한다. 그다음호출자는 [ 그림 9-15] 에나타낸위치로 top_sp 를증가시킨다. 즉 top_sp 는호출자의지역자료와임시기억변수, 그리고피호출자의매개변수와상태공간을지나서이동한다. 3 피호출자는레지스터값과다른상태정보를저장한다. 4 피호출자는자신의지역자료를초기화하고실행을시작한다. 이에대응하는적절한복귀순서는다음과같다. 1 [ 그림 9-15] 와같이피호출자는반환값을매개변수다음에저장한다. 2 피호출자는기계상태필드 status field 의정보를이용하여 top_sp 와다른레지스터를복원하고, 호출자가상태필드에저장했던복귀주소로분기한다. 3 top_sp 가감소되었지만호출자는반환값이있는위치를 top_sp 의현재값으로부터상대적인위치로알수있다. 따라서호출자는이값을사용할수있다. 38

39 9.3 메모리할당전략 [ 예제 9-6] 실행시간환경중스택메모리할당 음수가아닌 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); } main() { scanf("%d%d", &x, &y); printf("%d\n", gcd(x, y)); return 0; } 39

40 9.3 메모리할당전략 [ 풀이 ] 사용자가값 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 를반환한다. 이과정에대한실행시간환경은다음그림과같다. 40

41 9.3 메모리할당전략 힙메모리할당 : 스택메모리할당전략은 C, 파스칼, 에이다와같은표준적인명령형 (imperative) 언어사이에서가장공통적인방법이지만, 활성이끝난뒤에도지역변수의값을유지해야하는경우나호출된활성이호출자가사라진뒤에도살아있어야하는경우에는사용하지못한다. 이런경우에는무기한살아있거나프로그램이명시적으로제거할때까지살아있는자료를저장하는힙을사용하여해결할수있다. 지역변수는보통해당프로시저가끝나면접근할수없게되지만, 많은언어에서는해당프로시저의활성화에종속되지않는존속시간을가진객체나다른자료를사용할수있다. 예를들어 C++ 와자바는 new 로생성한객체를프로시저간에전달할수있다. 따라서이런객체는자신을생성한프로시저가종료된후에도계속존재할수있다. 힙메모리할당은연속적인기억공간을꾸러미로만들어활성레코드나다른객체에할당하는전략이다. 이꾸러미는다른순서로해체될수있으므로힙은사용중인영역과사용되지않고있는영역 (free area) 으로섞어서구성할수있다. 활성레코드의힙메모리할당은 [ 그림 9-16] 을통해알수있다. 41

42 9.3 메모리할당전략 [ 그림 9-14] 의세번째그림을보면프로시저 r 에대한활성이끝나고나서 r 에대한활성레코드가삭제되지만, [ 그림 9-16] 에서는 r 에대한활성이끝나도 r 에대한활성레코드가계속유지된다. 힙메모리할당은모든참조가없어질때만활성레코드를해제할수있으며, 활성레코드를동적으로실행하는동안임의의시점에해제되어야하기때문에동적메모리할당이라고도부른다. 42

43 9.4 매개변수전달방법 포트란 77 은참조호출방법을채택하고, C 는값호출방법을채택했다. 하나의프로시저가또다른프로시저를호출할때매개변수를통해서로값을주고받는다. 이러한매개변수에는실매개변수와형식매개변수가있다. 즉실매개변수와형식매개변수는서로값을주고받는다. 이처럼실매개변수와형식매개변수사이에값을주고받는것을매개변수전달 (parameter passing) 이라고하는데, 값을주고받는전달방법에따라프로그램의결과가달라질수있다. 그래서여러가지매개변수전달방법이존재한다. 매개변수전달방법을설명하기전에필요한개념을하나이해하기위해다음과같은치환문을생각해보자. a[i] = a[j] 산술식 a[j] 는값을나타내는 r- 값 (right value) 이고, a[i] 는 a[j] 의값이있는메모리의위치인 l- 값 (left value, location value) 을나타낸다. l- 값은산술식이나타내는기억위치를나타내고 r- 값은메모리에저장될값을나타내는용어이다. 접두사 l 과 r 은각각치환문의왼쪽과오른쪽을의미한다. 43

44 9.4 매개변수전달방법 값호출 값호출 (call by value) 은매개변수를전달하는가장일반적인방법으로 C, 파스칼, 에이다에서는기본적이다. 실매개변수와는별도로형식매개변수에대한메모리를할당하는방법이다. 형식매개변수는지역변수처럼다뤄지고, 호출자는형식매개변수에대한메모리에실매개변수의 r- 값을복사하는방법으로구현한다. 값호출의특징은형식매개변수에대한연산이호출자활성레코드안의값에는아무런영향을미치지않는다는것이다. [ 그림 9-17] 은두수를서로교환하는파스칼프로그램이다 44

45 9.4 매개변수전달방법 45

46 9.4 매개변수전달방법 [ 그림 9-17] 에서 3 행에있는 var 를없애면이프로그램은값호출방법이다. 12 행에있는 swap(a, b) 를호출하면 a 와 b 값을변화시키지않는다. 이과정을살펴보면, 12 행에서 swap(a, b) 를호출하면실매개변수 a 와 b 는 a:=1, b:=2 이므로 swap(1, 2) 가되고 3 행에있는 swap 프로시저를실행한다. 이때형식매개변수는 x 와 y 이다. 따라서형식매개변수에대한메모리를별도로할당하고 x 에는 1 을, y 에는 2 를할당한다. 그런다음지역변수 temp 에대한메모리를할당하고 6 행을실행한다. temp 에는 1, x 에는 2 가할당되고, y 에는다시 temp 의값 1 이할당된다. 여기까지는 x = 2, y = 1 이할당되어 x 와 y 의값이서로교환되었음을알수있다. 하지만제어가호출자로반환되고 swap 에대한활성레코드가해체될때지역변수인 x, y, temp 에대한메모리를삭제하기때문에호출자의활성레코드에는아무영향을주지못한다. 값호출프로시저는비지역변수나포인터로전달되는값을통해호출자에영향을줄수있다. 그렇지않으면호출된프로그램에서값을출력하는방법을선택해야한다. 46

47 9.4 매개변수전달방법 참조호출 참조호출 (call by reference, call by address) 방법은매개변수가참조에의해전달될때호출자가피호출자에게실매개변수의메모리에대한주소를가리키는포인터를전달한다. 포트란 77 에서매개변수전달방법은참조호출밖에없다. 또한파스칼에서참조호출은 var 키워드의사용으로이뤄지며, C++ 에서는매개변수선언시특수기호 & 의사용으로이뤄진다. 참조호출은만약실매개변수가 l- 값을가지고있는산술식이거나변수라면그 l- 값자신을전달한다. 그러나실매개변수가 b + c 나 5 와같이 l- 값을가지지않은산술식이라면그산술식은호출자활성레코드내의새로운위치에주소를전달한다. 피호출자가프로시저안에있는형식매개변수를목적코드에서참조하려면피호출프로시저로전달된포인터를통한간접참조 (indirect reference) 방식을이용해야한다. 47

48 9.4 매개변수전달방법 [ 예제 9-7] swap(a, b) 에대해구현되는과정 [ 그림 9-17] 의프로시저에서 swap(a, b) 에대해구현되는과정을설명해보자. [ 풀이 ] 실매개변수 a 와 b 에대한주소를피호출자활성레코드의 x 와 y 에해당하는위치 arg1 과 arg2 에각각복사한다. 6 행에서 temp 에 arg1 을가리키는위치의내용을복사한다. arg1 이가리키는위치의내용을 arg2 가가리키는위치의값으로설정한다. 마지막으로 arg2 가가리키는위치의내용을 temp 의값에복사한다. 48

49 9.4 매개변수전달방법 이름호출 이름호출 (call by name) 은가장복잡한매개변수전달방법이다. 이방법은형식매개변수의이름이사용될때마다그에대응하는실매개변수자체가사용된것처럼매번다시계산및시행된다. 이름호출은값호출과같이알골 60 에서매개변수전달방법으로제공되었으나부작용이존재하는경우에기대하지않았던결과가나타나기도하고, 매개변수가평가될때마다호출되어야만하는성크 (thunk) 라는프로시저를구현해야하므로구현하기가어려워잘사용되지않았다. [ 예제 9-8] swap(a, b) 에대해이름호출로구현되는과정 [ 그림 9-17] 의프로시저에서 swap(a, b) 에대해이름호출로구현되는과정을설명해보자. [ 풀이 ] 다음과같이 x 가나타날때마다 a 를, y 가나타날때마다 b 를대체하는방법이다. temp := a; a := b; b := temp; 49

50 9.4 매개변수전달방법 값 - 결과호출 값 - 결과호출 (call by value-result) 은값호출과참조호출을합성한방법으로입력복사출력복사 ( copy-in copy-out), 복사 회복 (copy-restore) 이라고도한다. 형식매개변수에대한메모리에실매개변수의값을복사하고호출전에실매개변수로부터계산된 l- 값에형식인자의마지막값을복사한다. 즉매개변수의값이복사되고프로시저에서사용되며, 그런다음매개변수의최종값은프로시저가종료될때매개변수의위치에다시복사된다. [ 예제 9-9] 값 - 결과호출과참조호출비교하기 다음과같은 C 코드에서값 - 결과호출과참조호출을구분해보자. void p(int x, int y) { ++x; ++y; } main( ) { int a = 1; p(a, a); return 0; } [ 풀이 ] 참조전달이사용된다면 a 는 p 가호출된후에값 3 을가지며, 값 - 결과호출이사 50

51 9.4 매개변수전달방법 [ 예제 9-10] 참조호출, 값호출, 이름호출의결과값구하기 다음과같은 PL/I 형태의프로그램에서참조호출, 값호출, 이름호출을하는경우의결과값을구해보자. P : PROCEDURE; DECLARE A(3), I; I=1; A(1)=2; A(2)=4; CALL Q(A(I)); Q : PROCEDURE(B) A(1)=3; I=2; PUT LIST(B); END Q; END P; [ 풀이 ] 1. 참조호출 I=1; A(1)=2; A(2)=4; CALL Q(A(I)); 로부터 addr(a(1))=addr(b) 이므로 A(1)=2 이다. A(1)=3; I=2; PUT LIST(B); A(1)=3 이고 PUT LIST(B); 로부터 A(1) 을출력해야하므로 3 이출력된다. 51

52 9.4 매개변수전달방법 2. 값호출 I=1; A(1)=2; A(2)=4; CALL Q(A(I)); 에서 A(1)=2 값을 B 에넘겨주는데 B 는메모리를따로잡아서 2 를저장한다. A(1)=3; I=2; PUT LIST(B); PUT LIST(B); 로부터 B 를출력하면 2 가저장되어있으므로 2 를출력한다. 3. 이름호출 I=1; A(1)=2; A(2)=4; CALL Q(A(I)); 에서값을 B 에넘겨주는것이아니라 B 가나타날때마다 A(I) 를대체한다. A(1)=3; I=2; PUT LIST(B); PUT LIST(B); 는 PUT LIST(A(I)); 이므로 A(I) 를출력하면된다. 현재 I 는 2 이므로 A(2) 를출력하여 4 가출력된다. 52