No older revisions available
No older revisions available
2.2. Linear Lists ¶
2.2.2. Sequential Allocation ¶
한 노드에 들어있는 WORD의 수가 c개라면 다음과 같이 쓸 수 있다.
상수 L0를 base address라고 한다면 다음과 같이도 쓸 수 있다.
Sequential Allocation은 stack을 다루는데 편리하다.
오버플로우와 언더플로우가 일어났을 때 어떻게 해야 할까? 언더플로우는 하나의 의미있는 조건 - 에러 상황이 아니라 - 이다. 하지만 오버플로우는 더 들어갈 공간이 없는데 들어갈 정보가 남아있어서 에러이다. 따라서 오버플로우가 생기면 용량한계를 넘어서서 프로그램이 종료한다.
상수 L0를 base address라고 한다면 다음과 같이도 쓸 수 있다.
Sequential Allocation은 stack을 다루는데 편리하다.
''새 원소 넣기(To place a new element Y on top)
queue나 deque를 나타내는 것은 좀더 복잡하다.T ← T + 1; XT ← Y;
마지막 원소 빼기(setting Y equal to the top node and delete)''새 원소 넣기(inserting an element at the rear of the queue)
하지만 공간낭비가 무한할 수 있다.( F, R이 계속증가하기 때문이다.) 따라서 이런 문제(the problem of the queue overrunning memory)를 해결하려면, M개의 노드(X1...XM)가 순환하도록 한다.R ← R + 1; XR ← Y;
맨 앞 원소 빼기(removing the front node)''if R = M then R ← 1, otherwise R ← R + 1; XR ← Y.
if F = M then F ← 1, otherwise F ← F + 1; Y ← XF.''
여태까지는 문제(더 넣을 공간이 없거나, 더 지울 것이 없는 경우)가 없다고 가정했다. 이 문제까지 고려한 과정이 다음과 같다.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이라면 오버플로우가 생기지 않기 때문이다.오버플로우와 언더플로우가 일어났을 때 어떻게 해야 할까? 언더플로우는 하나의 의미있는 조건 - 에러 상황이 아니라 - 이다. 하지만 오버플로우는 더 들어갈 공간이 없는데 들어갈 정보가 남아있어서 에러이다. 따라서 오버플로우가 생기면 용량한계를 넘어서서 프로그램이 종료한다.
가능한 공간에 리스트가 두 개 있다면 (고정된)bottom을 같이 쓸 수 있다. (p.246 그림 참고) 이런 경우 두 리스트가 메모리를 모두 써버릴 때까지 오버플로우는 생기지 않는다. 이런 형태는 매우 자주 쓰인다.
하지만 리스트가 더 많으면 bottom이 움직일 수 있어야 한다.(we must allow the "bottom" elements of the lists to change therir positions.) MIX에서 I번째 한 WORD를 rA에 가져오는 코드는 다음과 같다.
(p.248에 (12)와 그림 4는 예제이다. 근데 어렵다. 3번을 해보았으나 제대로 나오질 않았다.)
''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) 스택에 원소를 넣고 빼는 과정을 다음과 같이 적을 수 있다.LDA BASE(0:2) ;BASE에 저장된 L0주소를 rA에 넣는다.
STA *+1(0:2) ;그 주소를 다음 메모리(LDA *,1이 있는)에 넣는다.
LDA *,1 ;여기에 I를 더한 주소로 가서 그 값을 rA에 넣는다.''
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에 대해서 다음을 한다.
b) 아래로 한칸씩 밀기(moving things down)''' a)에 해당하는 k가 없을 경우
i≤k＜n인 k 가운데 TOPk < BASEk+1인 가장 큰 k를 찾는다. 찾으면 TOPi ≥ L＞BASEk+1인 L에 대해서 다음을 한다.
c) 진짜 오버플로우
공간을 찾을 수 없다. 포기해야 한다.
''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)과 비슷한 동적 메모리 할당 알고리즘의 수학적 분석은 매우 어렵다고 나와있다. )
