2.2. Linear Lists ¶

2.2.2. Sequential Allocation ¶

한 노드에 들어있는 WORD의 수가 c개라면 다음과 같이 쓸 수 있다.

LOC(Xj + 1) = LOC(Xj) + c

상수 L0를 base address라고 한다면 다음과 같이도 쓸 수 있다.

LOC(Xj) = L0 + cj

Sequential Allocation은 stack을 다루는데 편리하다.

''새 원소 넣기(To place a new element Y on top)

T ← T + 1; XT ← Y;

마지막 원소 빼기(setting Y equal to the top node and delete)

Y ← XT; T ← T - 1;''

queue나 deque를 나타내는 것은 좀더 복잡하다.

''새 원소 넣기(inserting an element at the rear of the queue)

R ← R + 1; XR ← Y;

맨 앞 원소 빼기(removing the front node)

F ← F + 1; Y ← XF; if F = R, then set F ← R ← 0''

하지만 공간낭비가 무한할 수 있다.( F, R이 계속증가하기 때문이다.) 따라서 이런 문제(the problem of the queue overrunning memory)를 해결하려면, M개의 노드(X1...XM)가 순환하도록 한다.

''if R = M then R ← 1, otherwise R ← R + 1; XR ← Y.
if F = M then F ← 1, otherwise F ← F + 1; Y ← XF.''

여태까지는 문제(더 넣을 공간이 없거나, 더 지울 것이 없는 경우)가 없다고 가정했다. 이 문제까지 고려한 과정이 다음과 같다.

p.245 (2a),(3a),(6a),(7a)

(6a),(7a)에서는 초기 조건이 F = R = 1이다. 만약 F = 0이라면 오버플로우가 생기지 않기 때문이다.

AnswerMe 그렇다면 새 원소를 넣으면 X2부터 들어간다는 건가? --Leonardong

오버플로우와 언더플로우가 일어났을 때 어떻게 해야 할까? 언더플로우는 하나의 의미있는 조건 - 에러 상황이 아니라 - 이다. 하지만 오버플로우는 더 들어갈 공간이 없는데 들어갈 정보가 남아있어서 에러이다. 따라서 오버플로우가 생기면 용량한계를 넘어서서 프로그램이 종료한다.

가능한 공간에 리스트가 두 개 있다면 (고정된)bottom을 같이 쓸 수 있다. (p.246 그림 참고) 이런 경우 두 리스트가 메모리를 모두 써버릴 때까지 오버플로우는 생기지 않는다. 이런 형태는 매우 자주 쓰인다.

하지만 리스트가 더 많으면 bottom이 움직일 수 있어야 한다.(we must allow the "bottom" elements of the lists to change therir positions.) MIX에서 I번째 한 WORD를 rA에 가져오는 코드는 다음과 같다.

''LD1 I ;I를 rI2에 넣는다.
LDA BASE(0:2) ;BASE에 저장된 L0주소를 rA에 넣는다.
STA *+1(0:2) ;그 주소를 다음 메모리(LDA *,1이 있는)에 넣는다.
LDA *,1 ;여기에 I를 더한 주소로 가서 그 값을 rA에 넣는다.''

n개의 스택이 있는 경우 i번째(1≤i≤n) 스택에 원소를 넣고 빼는 과정을 다음과 같이 적을 수 있다.

p.247 (9) (10) 참고

여기서 i번째 스택에서 오버플로우가 생기면 메모리 재배치(repack memory)를 할 수 있다. 몇가지 방법이 있는데 지금부터 자세히 알아보자.

''초기 조건 : p.247 (11) 참고
i번째 스택에서 오버플로우가 생겼을 때''
a) 위로 한칸씩 밀기(moving things up)'''
i＜k≤n인 k 가운데 TOPk < BASEk+1인 가장 작은 k를 찾는다. 찾으면 TOPk ≥ L＞BASEi+1인 L에 대해서 다음을 한다.

CONTENTS(L+1) ← CONTENTS(L) (L은 큰 것부터 민다. 해당사항 없으면 아무것도 하지 않는다.)

그리고 마지막으로 i보다 크고 k보다 크지 않은 모든 BASE와 TOP을 하나씩 위로 민다.

b) 아래로 한칸씩 밀기(moving things down)''' a)에 해당하는 k가 없을 경우
i≤k＜n인 k 가운데 TOPk < BASEk+1인 가장 큰 k를 찾는다. 찾으면 TOPi ≥ L＞BASEk+1인 L에 대해서 다음을 한다.

CONTENTS(L-1) ← CONTENTS(L) (L은 작은 것부터 민다. 해당사항 없으면 아무것도 하지 않는다.)

그리고 마지막으로 k보다 크고 i보다 크지 않은 모든 BASE와 TOP을 하나씩 아래로 민다.
c) 진짜 오버플로우
공간을 찾을 수 없다. 포기해야 한다.

''
(p.248에 (12)와 그림 4는 예제이다. 근데 어렵다. 3번을 해보았으나 제대로 나오질 않았다.)

초기값으로 효율적인 시작 위치를 주는 것이 가능하다. (p.248 (13), 평균적으로 BASE를 분포시킨다.)

한 번 메모리 재배치를 할 때마다 공간을 적당히 마련하는 방법도 가능하다.( 그러나 이해하지 못했다.p.250에 중간에 보면 위 알고리즘(Algorithm G나 R)과 비슷한 동적 메모리 할당 알고리즘의 수학적 분석은 매우 어렵다고 나와있다. )

TAOCP

TAOCP/Information Structures

2.2. Linear Lists ¶

2.2.2. Sequential Allocation ¶