내 컴퓨터 중 하나에서 최신 업데이트가 포함된 64비트 Arch Linux를 실행하고 있습니다. 저는 현재 컴퓨터 과학을 전공하고 있으며 어제 연결 목록을 사용하여 동적 스택을 구현하려는 테스트를 가졌습니다. 이제 내 컴퓨터에서 스택이 어떻게 구축되는지 이해하고 싶지만 내 Arch Linux 컴퓨터에서 "stack.c"라는 주석을 찾을 수 없습니다. 스택 프로그래밍은 어디에 있나요? 스택이 어떻게 메모리를 생성하는지 이해하지만 실제로 코드를 보고 직접 시도해 보고 싶습니다.
답변1
"스택"이라는 단어가 너무 많이 사용되었습니다. 몇 가지 가능한 설명은 다음과 같습니다.
- "스택"은추상적인포함된 요소에 대한 LIFO(후입선출) 액세스를 제공하는 데이터 구조 세트입니다.
- 가지다성취하다"스택" 추상화. 수업 시간에 개발한 연결 목록 기반 스택이 그러한 구현 중 하나입니다. 이것이 유일한 깨달음은 아닙니다. 예를 들어 배열을 사용하여 스택을 구축할 수도 있습니다.
- 런타임 활성화 스택(프로그램에서 스레드 실행 중 함수 호출 및 반환을 관리하는 데 사용되는 스택)은 "스택" 추상화의 또 다른 구현입니다. 이는 배열 기반 스택처럼 동작합니다.
(3)에 따르면 프로그램에서 실행 중인 각 스레드에 메모리 "블록"이 할당됩니다. 함수가 이러한 스레드에서 호출되어 반환되면 스레드와 연결된 스택에서 "스택 프레임"(스택의 런타임 활성화 "요소")을 푸시하고 팝합니다. 스택 프레임에 포함된 내용에 대한 세부 정보는 하드웨어 아키텍처에 따라 다릅니다. 일반적으로 스택 프레임에는 다음이 포함됩니다.
- 발신자의 회신 주소
- 함수의 매개변수 중 일부 또는 전부(하드웨어 아키텍처, 매개변수 수 및 크기에 따라 다름)
- 함수 내에 정의된 지역 변수입니다.
- 함수에서 사용하지만 함수가 반환되기 전에 값을 복원해야 하는 레지스터의 상태입니다.
인수 수, 함수 내 지역 변수의 수와 크기, 저장해야 하는 레지스터가 함수마다 다르기 때문에 스택 프레임에는 일정한 크기가 없습니다.
stack.c
활성화 레코드 스택을 관리하는 코드는 함수별로 프로그램 기능을 구축하는 컴파일러에서 생성되기 때문에 확인할 필요가 없습니다 . 컴파일러는 함수 호출을 트리거하는 명령을 생성합니다. 컴파일러는 프로그램 명령어를 생성할 때 다음을 알고 있습니다.
- 함수 호출을 트리거하는 데 사용되는 하드웨어 명령어와 해당 명령어가 스택에 미치는 영향(예: 자동으로 반환 주소를 저장하는지, 스택의 "상단"을 추적하는 레지스터를 조정하는지)
- 호출의 매개변수가 스택에 저장되면 이러한 매개변수는 스택의 "맨 위"에 있게 됩니다.
- 함수 내 지역 변수의 크기 및 스택의 "상단"을 기준으로 한 이러한 변수의 위치(컴파일러는 이를 사용하여 스택의 "상단"을 추적하는 레지스터를 조정합니다).
- 함수에서 사용되는 레지스터와 저장/복원이 필요한 시기
- 함수 호출에서 반환을 트리거하는 데 사용되는 하드웨어 명령어와 이 명령어가 스택에 미치는 영향.
컴파일러는 하드웨어 아키텍처에 대해 잘 확립된 규칙 세트(호출 규칙)를 따르므로 서로 다른 컴파일러에서 구축한 서로 다른 부분으로 구성된 프로그램이 상호 운용될 수 있습니다.
런타임 활성화 스택(3)은 "스택" 추상화(1)의 구현이지만 레코드 푸시/팝핑 개념 외에는 링크 기반 구현과 거의 유사하지 않습니다.
답변2
앞에서 언급했듯이 스택은 범용 데이터 유형이며 특정 범용 운영 체제에는 여러 스택 구현이 있을 수 있습니다. 단일 스택이 없습니다.이것스택, 시스템 수준 프로그래머가 아닌 이상 하드웨어 호출 스택은 아마도 그럴 것입니다. 아마도.
OpenSSL에는stack.h
, 이 라이브러리는 스택 데이터 구조를 구현합니다. 어쩌면 이것이 당신이 찾은 것일 수도 있습니다.C++에는 표준 컨테이너도 있습니다.std::stack
. (해당 파일은 stack
내 Linux에서는 일명 이라고 불릴 수 있습니다 stl_stack.h
. 헤더 파일도 라이브러리를 사용하는 항목을 컴파일하는 데만 필요합니다.