태그 보관물: stack

stack

스택 포인터가 무엇인지 이해하지만 무엇이 사용됩니까? 데이터를 저장합니다. 다른 사람의 비유를 훔치기

스택 포인터는 스택의 맨 위를 가리켜 서 “LIFO”라고 부르는 것에 대한 데이터를 저장합니다. 다른 사람의 비유를 훔치기 위해, 당신이 상단에 요리를 넣고 가져다주는 일련의 요리와 같습니다. 스택 포인터 OTOH는 스택의 맨 위 “접시”를 가리 킵니다. 적어도 x86에는 해당됩니다.

그러나 왜 컴퓨터 / 프로그램이 스택 포인터가 가리키는 것을 “관리”합니까? 다시 말해서, 스택 포인터를 가지고 있고 그것이 어디에서 역할을하는지 아는 목적은 무엇입니까?

C 프로그래머가 이해할 수있는 설명을 부탁드립니다.



답변

이 스택의 구조를 설명하는 대신이 스택이 실제로 어떤 용도로 사용됩니까?

스택에 저장된 데이터의 구조를 정확하게 설명하는 많은 답변이 있습니다. 필자는 질문과 반대입니다.

스택이 제공하는 목적은 다음 같습니다 . 스택은 코 루틴이없는 언어로 연속을 구체화하는 것의 일부입니다 .

포장을 풉니 다.

계속은 단순히 질문에 대한 답 넣어 “내 프로그램에서 다음에 무슨 일이 일어날을?” 모든 프로그램의 모든 시점에서 다음에 어떤 일이 일어날 것입니다. 두 피연산자가 계산되면 프로그램은 합계를 계산하여 계속 한 다음 합계를 변수에 할당 한 다음 계속합니다.

Reification 은 추상 개념을 구체적으로 구현하기위한 하이포 루틴 단어입니다. “다음에는 어떻게됩니까?” 추상적 인 개념이다. 스택이 배치되는 방식은 추상적 개념이 실제로 사물을 계산하는 실제 기계로 전환되는 방법의 일부입니다.

코 루틴 은 그들이 있던 위치를 기억하고 잠시 동안 다른 코 루틴에 대한 제어를 양보 한 다음 나중에 중단 된 곳에서 재개 할 수 있지만, 이른바 코 루틴 수율 직후에 반드시 그런 것은 아닙니다 . 다음 항목이 요청되거나 비동기 작업이 완료 될 때의 위치를 ​​기억해야하는 C #의 “수율 반환”또는 “대기”를 생각하십시오. 코 루틴 또는 유사한 언어 기능이있는 언어는 연속성을 구현하기 위해 스택보다 더 고급 데이터 구조가 필요합니다.

스택은 어떻게 연속을 구현합니까? 다른 답변은 방법을 말합니다. 스택은 (1) 수명이 현재 방법의 활성화보다 크지 않은 것으로 알려진 변수 및 임시 값과 (2) 가장 최근의 방법 활성화와 관련된 연속 코드의 주소를 저장합니다. 예외 처리가있는 언어의 스택에는 “오류 지속”에 대한 정보, 즉 예외적 인 상황이 발생했을 때 프로그램이 다음에 수행 할 작업도 저장할 수 있습니다.

이 기회를 통해 스택에 “어디에서 왔습니까?”라는 메시지가 표시되지 않습니다. -종종 디버깅에 사용 되기는합니다. 스택은 당신 이 다음에 갈 곳거기에 도착했을 때 활성화 변수의 값을 알려줍니다 . 코 루틴이없는 언어에서 다음에 갈 곳은 거의 항상 어디에서 왔는지에 따라 이러한 종류의 디버깅이 더 쉬워집니다. 하지만이없는 요구 사항은 해당 컨트롤이 그렇게하지 않고 멀리 얻을 수 있다면 어디에서 왔는지에 대한 컴파일러 정보를 저장합니다. 예를 들어 테일 콜 최적화는 프로그램 제어의 출처에 대한 정보를 파괴합니다.

코 루틴이없는 언어로 연속을 구현하기 위해 스택을 사용하는 이유는 무엇입니까? 방법의 동기식 활성화의 특징은 논리적으로 활성화 스택을 구성 할 때 “현재 방법을 일시 중지하고 다른 방법을 활성화하고 활성화 된 방법의 결과를 알고있는 현재 방법을 재개”하는 패턴입니다. 이 스택 형 동작을 구현하는 데이터 구조를 만드는 것은 매우 저렴하고 쉽습니다. 왜 그렇게 싸고 쉬운가요? 칩셋은 수십 년 동안 컴파일러 작성자가 이러한 종류의 프로그래밍을 쉽게 할 수 있도록 특별히 설계 되었기 때문입니다.


답변

스택의 가장 기본적인 용도는 함수의 반환 주소를 저장하는 것입니다.

void a(){
    sub();
}
void b(){
    sub();
}
void sub() {
    //should i got back to a() or to b()?
}

그리고 C의 관점에서 이것은 전부입니다. 컴파일러 관점에서 :

  • 모든 함수 인수는 CPU 레지스터에 의해 전달됩니다. 레지스터가 충분하지 않으면 인수가 스택에 배치됩니다.
  • 함수 종료 후 (대부분) 레지스터는 입력하기 전과 동일한 값을 가져야하므로 사용 된 레지스터는 스택에 백업됩니다.

그리고 OS 관점에서 : 프로그램은 언제든지 중단 될 수 있으므로 시스템 작업을 마친 후에는 CPU 상태를 복원해야하므로 모든 것을 스택에 저장할 수 있습니다

우리는 이미 스택에있는 항목의 양이나 다른 사람이 추가 할 항목의 수를 신경 쓰지 않기 때문에 스택 포인터를 얼마나 움직 였는지 확인하고 완료 한 후에 복원하면됩니다.


답변

LIFO 대 FIFO

LIFO는 Last In, First Out의 약자입니다. 마찬가지로 스택에 넣은 마지막 항목은 스택에서 가져온 첫 번째 항목입니다.

당신이 당신의 요리 비유로 설명 한 것은 ( 첫 번째 개정판에서 ) 대기열 또는 선입 선출 (FIFO), 선입 선출 (First In, First Out)입니다.

둘의 주요 차이점은 LIFO / 스택이 같은 끝에서 밀고 (삽입) 튀어 나오고 (제거), FIFO / 대기는 반대쪽 끝에서 그렇다는 것입니다.

// Both:

Push(a)
-> [a]
Push(b)
-> [a, b]
Push(c)
-> [a, b, c]

// Stack            // Queue
Pop()               Pop()
-> [a, b]           -> [b, c]

스택 포인터

스택의 후드에서 일어나는 일을 살펴 보겠습니다. 여기에 약간의 메모리가 있습니다. 각 상자는 주소입니다 :

...[ ][ ][ ][ ]...                       char* sp;
    ^- Stack Pointer (SP)

그리고 현재 비어있는 스택의 맨 아래를 가리키는 스택 포인터가 있습니다 (스택이 커지거나 커지는 지 여부는 여기에서 특별히 관련이 없으므로 무시할 것입니다. 그러나 물론 실제로는 어떤 작업이 추가되는지 결정합니다) SP에서 빼는 것).

a, b, and c다시 밀어 봅시다 . 왼쪽의 그래픽, 중간의 “높은 수준”작업, 오른쪽의 C-ish 의사 코드 :

...[a][ ][ ][ ]...        Push('a')      *sp = 'a';
    ^- SP
...[a][ ][ ][ ]...                       ++sp;
       ^- SP

...[a][b][ ][ ]...        Push('b')      *sp = 'b';
       ^- SP
...[a][b][ ][ ]...                       ++sp;
          ^- SP

...[a][b][c][ ]...        Push('c')      *sp = 'c';
          ^- SP
...[a][b][c][ ]...                       ++sp;
             ^- SP

보시다시피, 우리는 매번 push스택 포인터가 가리키는 위치에 인수를 삽입하고 다음 위치를 가리 키도록 스택 포인터를 조정합니다.

이제 팝하자 :

...[a][b][c][ ]...        Pop()          --sp;
          ^- SP
...[a][b][c][ ]...                       return *sp; // returns 'c'
          ^- SP
...[a][b][c][ ]...        Pop()          --sp;
       ^- SP
...[a][b][c][ ]...                       return *sp; // returns 'b'
       ^- SP

Pop의 반대입니다 push. 스택 포인터를 이전 위치를 가리 키도록 조정하고 있던 위치의 항목을 제거합니다 (일반적으로 호출 한 사람에게 반환 pop).

당신은 아마 저를 발견 b하고 c메모리에 남아 있습니다. 나는 그것들이 오타가 아니라고 확신하고 싶습니다. 우리는 곧 다시 돌아올 것입니다.

스택 포인터가없는 수명

스택 포인터가 없으면 어떻게되는지 봅시다. 다시 밀면서 시작 :

...[ ][ ][ ][ ]...
...[ ][ ][ ][ ]...        Push(a)        ? = 'a';

어, 흠 … 스택 포인터가 없으면 가리키는 주소로 무언가를 옮길 수 없습니다. 상단이 아닌 밑을 가리키는 포인터를 사용할 수 있습니다.

...[ ][ ][ ][ ]...                       char* bp; // "base pointer"
    ^- bp                                bp = malloc(...);

...[a][ ][ ][ ]...        Push(a)        *bp = 'a';
    ^- bp
// No stack pointer, so no need to update it.
...[b][ ][ ][ ]...        Push(b)        *bp = 'b';
    ^- bp

어 오. 스택베이스의 고정 값을 변경할 수 없으므로 동일한 위치 a로 밀어서 덮어 씁니다 b.

우리가 몇 번이나 밀 었는지 추적 해 보지 않겠습니까? 또한 우리가 터진 시간을 추적해야합니다.

...[ ][ ][ ][ ]...                       char* bp; // "base pointer"
    ^- bp                                bp = malloc(...);
                                         int count = 0;

...[a][ ][ ][ ]...        Push(a)        bp[count] = 'a';
    ^- bp
...[a][ ][ ][ ]...                       ++count;
    ^- bp
...[a][b][ ][ ]...        Push(a)        bp[count] = 'b';
    ^- bp
...[a][b][ ][ ]...                       ++count;
    ^- bp
...[a][b][ ][ ]...        Pop()          --count;
    ^- bp
...[a][b][ ][ ]...                       return bp[count]; //returns b
    ^- bp

잘 작동하지만 실제로 *pointer는 이전과 거의 비슷하지만 입력하는 것이 아니라 pointer[offset]말할 것도없이 (추가 산술이 없음) 보다 저렴 합니다. 이것은 나에게 손실처럼 보인다.

다시 해보자. Pascal 문자열 스타일을 사용하여 배열 기반 컬렉션의 끝을 찾는 대신 (컬렉션에 몇 개의 항목이 있는지 추적) C 문자열 스타일을 사용해 봅니다 (처음부터 끝까지 스캔).

...[ ][ ][ ][ ]...                       char* bp; // "base pointer"
    ^- bp                                bp = malloc(...);

...[ ][ ][ ][ ]...        Push(a)        char* top = bp;
    ^- bp, top
                                         while(*top != 0) { ++top; }
...[ ][ ][ ][a]...                       *top = 'a';
    ^- bp    ^- top

...[ ][ ][ ][ ]...        Pop()          char* top = bp;
    ^- bp, top
                                         while(*top != 0) { ++top; }
...[ ][ ][ ][a]...                       --top;
    ^- bp       ^- top                   return *top; // returns '('

이미 문제를 추측했을 수도 있습니다. 초기화되지 않은 메모리는 0으로 보장되지 않습니다. 따라서 top to place를 찾으면 a임의의 가비지가있는 사용되지 않는 메모리 위치를 건너 뜁니다. 마찬가지로, 상단까지 스캔 할 때, 우리 a는 방금 밀어 낸 메모리 너머로 넘어 0가게 됩니다. 마지막으로 발생하는 다른 메모리 위치를 찾을 때까지 되돌아 가서 바로 이전에 임의의 쓰레기를 반환합니다.

그것은 수정하기가 쉽고 , 스택에 맨 위에 항상으로 표시되도록 작업을 추가 Push하고 Pop업데이트해야하며 0그러한 종결 자로 스택을 초기화해야합니다. 물론 0이것은 스택의 실제 값으로 (또는 종료 자로 선택한 값)도 가질 수 없다는 것을 의미 합니다.

또한 O (1) 연산을 O (n) 연산으로 변경했습니다.

TL; DR

스택 포인터는 모든 작업이 발생 하는 스택의 상단을 추적 합니다. 이 그것을 제거의 정렬하는 방법이 있습니다 ( bp[count]그리고 top여전히 기본적으로 스택 포인터입니다)하지만를 두 끝은 더 느린 단순히 스택 포인터를하는 것보다 복잡하고된다. 스택의 상단이 어디에 있는지 알지 못하면 스택을 사용할 수 없습니다.

참고 : x86에서 런타임 스택의 “하단”을 가리키는 스택 포인터는 전체 런타임 스택이 거꾸로되어있는 것과 관련된 오해 일 수 있습니다. 즉, 스택의베이스는 높은 메모리 주소에 배치되고 스택의 끝은 낮은 메모리 주소로 커집니다. 스택 포인터 모든 동작이 발생하는 스택의 끝을 가리키며 해당 팁은 스택의베이스보다 낮은 메모리 주소에 있습니다.


답변

스택 포인터는 호출 스택에 사용됩니다 (프레임 포인터와 함께) (사진이 좋은 위키 백과 링크 참조).

호출 스택에는 반환 주소, 로컬 변수 및 기타 로컬 데이터 (특히 유출 된 레지스터 내용, 형식) 가 포함 된 호출 프레임이 포함 됩니다.

꼬리 호출 (일부 꼬리 재귀 호출에는 호출 프레임이 필요하지 않음), 예외 처리 ( setjmp 및 longjmp 와 같이 한 번에 많은 스택 프레임이 팝업 될 수 있음), 신호인터럽트연속 에 대해 읽어보십시오 . 참조 호출 규칙응용 프로그램 바이너리 인터페이스 (ABI를)를, 특히 – 64 ABI (이 일부 형식 인수가 레지스터에 의해 전달되는 것을 정의한다).

또한 C로 간단한 함수를 코딩 한 다음 gcc -Wall -O -S -fverbose-asm 컴파일하고 생성 된 .s 어셈블러 파일을 살펴보십시오 .

Appel은 가비지 수집이 스택 할당보다 빠를 수 있다고 주장하는 1986 년의 오래된 논문을 작성 했지만 (컴파일러에서 Continuation-Passing Style 사용 ) 오늘날 x86 프로세서 (특히 캐시 효과로 인해)에서는 잘못된 것일 수 있습니다.

호출 규칙, ABI 및 스택 레이아웃은 32 비트 i686과 64 비트 x86-64에서 다릅니다. 또한, 호출 규칙 (및 호출 프레임 할당 또는 팝을 담당하는 사람)은 언어마다 다를 수 있습니다 (예 : C, Pascal, Ocaml, SBCL Common Lisp에는 다른 호출 규칙이 있습니다. …)

BTW, AVX 와 같은 최근 x86 확장 은 스택 포인터에 점점 더 큰 정렬 제약 조건을 부과하고 있습니다 (IIRC, x86-64의 호출 프레임은 16 바이트, 즉 두 단어 또는 포인터에 정렬되기를 원합니다).


답변

간단히 말해서, 프로그램은 해당 데이터를 사용하고 있으며 데이터를 찾을 수있는 위치를 추적해야하기 때문에 중요합니다.

함수에서 로컬 변수를 선언하면 스택은 변수가 저장되는 위치입니다. 또한 다른 함수를 호출하면 스택은 반환 주소를 저장하는 위치이므로 호출 한 함수가 완료되었을 때 있던 함수로 돌아와서 중단 된 부분을 가져올 수 있습니다.

SP가 없다면, 구조화 된 프로그래밍은 본질적으로 불가능할 것입니다. (당신은 그것을 가지고 있지 않을 수도 있지만, 자신의 버전을 구현해야 할 것이므로 큰 차이는 없습니다.)


답변

x86 프로세서의 프로세서 스택의 경우 접시 스택의 비유는 실제로 부정확합니다.
여러 가지 이유로 (대부분 역사적으로) 프로세서 스택은 메모리 상단에서 메모리 하단으로 커지므로 천장에 매달려있는 체인 링크 체인이 더 좋습니다. 스택에 무언가를 밀면 체인 링크가 가장 낮은 링크에 추가됩니다.

스택 포인터는 체인의 가장 낮은 링크를 나타내며 프로세서가 가장 낮은 링크가있는 위치를 “인식”하여 천장 전체에서 체인 전체를 이동하지 않고도 링크를 추가하거나 제거 할 수 있습니다.

어떤 의미에서는 x86 프로세서 내부에서 스택은 거꾸로되어 있지만 일반적인 스택 용어는 사용되므로 가장 낮은 링크는 스택 의 최상위 라고합니다 .


위에서 언급 한 체인 링크는 실제로 컴퓨터의 메모리 셀이며 로컬 변수 및 일부 중간 계산 결과를 저장하는 데 사용됩니다. 컴퓨터 프로그램은 스택 상단이 어디에 있는지 (즉, 가장 낮은 링크가 중단되는 위치)를 관리합니다. 왜냐하면 함수가 액세스해야하는 대부분의 변수는 스택 포인터가 참조하는 위치에 가깝고 빠른 액세스가 바람직하기 때문입니다.


답변

이 답변은 구체적으로 현재 실행중인 스레드 스택 포인터 를 나타냅니다 .

절차 적 프로그래밍 언어에서 스레드는 일반적으로 다음 목적으로 스택 1 에 액세스 할 수 있습니다 .

  • 제어 흐름, 즉 “호출 스택”.
    • 한 함수가 다른 함수를 호출하면 호출 스택은 어디로 돌아갈지를 기억합니다.
    • “함수 호출”이 동작하기를 원하기 때문에 ” 중지 된 곳을 선택”하기 때문에 호출 스택이 필요합니다 .
    • 실행 중에 함수 호출이 없거나 (예 : 현재 함수의 끝에 도달 할 때 다음 함수 만 지정할 수있는) 다른 프로그래밍 스타일이 있거나 전혀 함수 호출이 없습니다 (goto 및 조건부 점프 만 사용). ). 이러한 프로그래밍 스타일에는 호출 스택이 필요하지 않을 수 있습니다.
  • 함수 호출 매개 변수.
    • 함수가 다른 함수를 호출하면 매개 변수를 스택으로 푸시 할 수 있습니다.
    • 호출이 완료되면 호출자와 호출 수신자는 스택에서 매개 변수를 지울 책임이있는 사람과 동일한 규칙을 따라야합니다.
  • 함수 호출 내에있는 로컬 변수
    • 호출자에게 속한 로컬 변수는 호출자 에게 해당 로컬 변수대한 포인터를 전달 하여 수신자에게 액세스 가능하게 할 수 있습니다 .

1 : – 그 내용이 완전히 읽을 수 있지만, 스레드의 사용에 전념 smashable – 다른 스레드에 의해.

어셈블리 프로그래밍, C 및 C ++에서는 세 가지 목적을 모두 동일한 스택으로 수행 할 수 있습니다. 다른 언어들에서, 일부 목적들은 별도의 스택들 또는 동적으로 할당 된 메모리에 의해 달성 될 수있다.