CLOSE

Search For:




BY TAGS

linux HTTP golang flutter java fintech 개발환경 kubernetes network Docker devops database tutorial cli 분산시스템 www 블록체인 AWS system admin bigdata 보안 금융 msa mysql redis Linux command dns javascript CICD VPC FILESYSTEM S3 NGINX TCP/IP ZOOKEEPER NOSQL IAC CLOUD TERRAFORM logging IT용어 Kafka docker-compose Dart

실행시 스택(stack)

 Recommanded Free YOUTUBE Lecture: <% selectedImage[1] %>

Contents

25장 실행시 스택

http://chortle.ccsu.edu/AssemblyTutorial/Chapter-25/ass25_1.html

이 장에서는 실행시 스택과 스택포인터 레지스터 $sp에 대해서 논의한다.

장의 주제

  • 스택(Stacks)
  • 스택 포인터 레지스터 ()
  • 스택 집어넣기(푸시, Push) 빼내기(팝, Pop) 작동.
  • MIPS의 실행 스택.
  • 컴파일러는 스택을 어떻게 사용하는가..
  • 문자열 뒤집기 예제
번역: 자바하는넘, 강웅빈 감수: ???

주:이 장에서 예제 프로그램은 스핌 시뮬레이터의 설정에서 의사명령(pseduoinstrictions)은 ON 지연분기(delayed branches)는 OFF 그리고 지연 로딩(delayed loading)이 OFF 설정임을 가정한다.

질문: 쌓여있는 접시들로부터 하나의 접시를 뽑아낸다고 가정해보자. 어떤 접시를 일반적으로 먼저 뽑아내겠습니까?

스택(Stack)

http://chortle.ccsu.edu/AssemblyTutorial/Chapter-25/ass25_2.html

답:맨위에 있는 접시

스택이란 메모리에 데이터를 정렬하는 하나의 방식이다. 추상적인 데이터들을 마치 물리적인 물체가 작동하는것처럼 가시화할 수 있다. 스택을 접시들을 쌓아놓은 구조가 작동하는것처럼 가시화해서 생각해 볼 수 있다. 접시들을 쌓아놓은 스택에서 접시를 얻거나 빼거나 하는 작동방식과 유사하게 데이터를 더하거나 빼낼 수 있다. 일반적으로 접시를 쌓아놓은 스택에서 모든 작동은 맨위에 접시를 가지고 한다. 접시가 필요하다면 쌓아놓은 접시에 가장 윗접시를 빼낸다. 접시를 쌓을 때는 맨위의 접시위에 접시를 올려 놓는다.

질문: 접시를 쌍아놓은 스택에 가장 마지막에 올려진 접시는 무었입니까? 접시를 스택에서 빼낼때 첫번째로 뽑아내는 접시는 무었입니까?

위에서부터 아래로 증가하는 MIPS 스택

http://chortle.ccsu.edu/AssemblyTutorial/Chapter-25/ass25_3.html

답:

쌓아논 접시위에 가장 위에 있는 접시가 제일 마지막에 언혀진 접시이고 제일먼저 뽑아낼 수 있는 접시이다.

attachment:stackInts00.gif

접시를 쌍아놓은 스택처럼 작동하는것을 영어로 LIFO(last in first out)로 표현한다. 굳이 번역하자면 마지막에 들어간것이 첫번째로 나오는 작동 정도로 번역할 수 있다. 그림에서 볼 수 있는 스택의 데이터들이 각각 32비트 크기이다. 일반적으로 스택은 모든 형태의 데이터에 적용할 수 있다. 하지만 이 장에서 스택은 32비트 MIPS FULL WORD를 담고 있다. 그림은 full word를 담고 있는 MIPS 스택을 보여준다. 관례에 따라 스택 포인터 레지스터 $sp는 스택의 가장 최상위 아이템을 가리킨다. 스텍 포인터는 레지스터 $29이다. 확장된 어셈블러에서는 레지스터 약어로 $sp를 사용할 수 있다.

일반적으로 메모리를 그릴때 스택은 위에서부터 아래로 증가하는 형태이다. 그림에서 스택의 최상위 아이템은 81이고 스택의 최하위 아이템은 정수 -92를 담고 있다.

운역체제는 프로그램을 시작하기 전에 스택의 메모리 영역을 보장해 주고 적절한 주소를 $sp 레지스터에 집어넣는다.

질문: 만약에 스택에 103이라는 숫자를 추가될때 그 추가되는 데이터(103)은 어디에 위치하게 됩니까?

집어넣기 (푸시, Push)

http://chortle.ccsu.edu/AssemblyTutorial/Chapter-25/ass25_4.html

답:

81 다음에 있습니다. 103은 이제 스택의 맨 위입니다.

소프트웨어 관습 (convention) 에 따라, $sp는 항상 스택의 맨 위를 가리킵니다. 또한 같은 이유로 스택은 (메모리 주소를 고려할때) 아래로 자랍니다. 그래서 우리의 4바이트 (풀 워드-full word) 데이터의 스택에서 데이터를 추가한다는 것은 $sp에서 4를 빼고 그 주소에 그 아이템을 저장한다는 것과 같은 말입니다. 이 동작을 집어넣기(푸시, push) 라고 합니다.

아이템을 스택에 집어넣으려면 먼저 스택포인터에서 4을 뺀후에 그 아이템을 스택이 가리키는 주소에 집어넣습니다. 아래에 예제코드가 있습니다. 레지스터 $t0에 있는 값을 스택에 푸시 한다고 하겠습니다. 

# $t0 에 있는 아이템를 '푸시' 하기:
subu $sp,$sp,4      #   새로운 아이템을 넣을 위치를 지정한다. i.e. 스택포인터에서 4바이트를 뺀다.
sw   $t0,($sp)      #  $t0에 있는 아이템을 새로운 스택의 맨 윗 지점(top) 에 저장한다.

attachment:stackInts01.gif

질문: 위의 그림에 있는 스택에서 한개의 아이템 제거한다면 어떤 데이터가 제거됩니까?

빼내기 (팝, Pop)

http://chortle.ccsu.edu/AssemblyTutorial/Chapter-25/ass25_5.html

답: 103이 제거됩니다. 스택에서 아이템을 제거하는 동작을 빼내기(팝, Pop) 이라고 합니다. 실제 예 (접시를 제거하는 동작) 에서는 접시를 실제로 빼냈지만, 소프트웨어 스택에서의 제거는 원래의 아이템이 옮겨지고 스택포인터가 조정-증가- 한다는 것을 의미합니다.

attachment:stackInts02.gif

위의 사진은 팝 동작을 보여줍니다. 데이터는 먼저 스택의 맨 위에서 다른 곳을 복사되고 스택 포인터가 증가되었습니다.

스택에서 아이템을 빼내려면 스택포인터가 가리키는 아이템을 복사하고 스택포인터에 4를 더하면 됩니다. 실제 코드는 아래와 같습니다. 스택에서 한 아이템을 $t0 으로 빼내는 예입니다. 

# 스택에서 아이템을 '빼내' $t0에 집어넣기:
lw   $t0,($sp)      #   맨위의 아이템을 $t0에 복사.
addu $sp,$sp,4      #   맨위의 아이템 바로 아래 아이템을 가리키도록 $sp를 조정

질문: 소프트웨어 스택에서 아이템을 빼낸후, 빼낸 아이템이 메모리에 남아있습니까?

예제

http://chortle.ccsu.edu/AssemblyTutorial/Chapter-25/ass25_6.html

답: 네. 데이터가 새로운 장소에 복사되었다고 해도 이전 장소에는 데이터가 남아있습니다. 하지만 스택포인터가 옮겨졌기 때문에 논리적으로는 데이터가 스택에 남아있지 않습니다.

보통 스택은 모든 레지스터들이 이미 사용중일때 사용됩니다. 예를 들면 컴파일러가 수식을 기계어로 번환할때 컴파일러는 스택을 사용합니다. 예를 들어, 수식이 ab - 12a + 18b - 7이라고 합시다. 사용가능한 레지스터는 $t0과 $t1뿐입니다.

스택포인터는 SPIM이 프로그램이 시작하기 전에 적절히 초기화 됩니다. 운영체제를 가지고 있는 시스템에서는 운영체제가 프로그램이 시작하기 전에 스택포인터를 초기화 합니다.

프로그램의 시작입니다. 

# 수식 ab - 12a + 18b - 7 을 평가하기

main:   
        lw      $t0,a          # a를 가져오기
        lw      $t1,bb         # b를 가져오기
        mul     $t0,$t0,$t1    # a*b
        
        subu    $sp,$sp,_____  # a*b를 스택에 집어넣기
        
        sw      $t0,______

        . . . . .

        .data
a:      2
bb:     3

질문: 빈칸을 채워 보십시오.

예제 계속

http://chortle.ccsu.edu/AssemblyTutorial/Chapter-25/ass25_7.html

답: 아래의 코드를 보세요.

식의 각 항이 평가되면서 스택에 집어 넣어집니다. 그리고나서 합 (우리가 원하는 답)은 -7로 초기화되고 각각의 항은 스택에서 나오면서 합에 추가됩니다. 

# 수식 ab - 12a + 18b - 7 평가하기

        .globl  main
        lw      $t0,a          # a를 가져오기
        lw      $t1,bb         # b를 가져오기
        mul     $t0,$t0,$t1    # a*b
        subu    $sp,$sp,4      # a*b를 스택에 집어넣기
        sw      $t0,($sp)
        
        lw      $t0,a          # a를 가져오기
        li      $t1,-12        # 
        mul     $t0,$t0,$t1    # -12a
        subu    $sp,$sp,4      # -12a 를 스택에 집어넣기
        sw      $t0,($sp)
        
        lw      $t0,bb         # b를 가져오기
        li      $t1,18         # 
        mul     $t0,$t0,$t1    # 18b
        subu    $sp,$sp,4      # 18b 를 스택에 집어넣기
        sw      $t0,($sp)

        li      $t1,-7         # 합을 -7로 초기화
        
        lw      $t0,_____      # 18b를 스택에서 빼내기
        
        addu    $sp,$sp,______
        
        addu    $t1,$t1,$t0    # 18b -7

        . . . .

질문: 아이템 '18b'를 뽑기위한 코드를 집어넣으세요.

완성된 프로그램

http://chortle.ccsu.edu/AssemblyTutorial/Chapter-25/ass25_8.html

답: 아래의 코드를 참고하세요.

아래에 완성된 프로그램이 있습니다. 만약 충분한 수의 레지스터를 쓸수 있었다면 수식의 항을 스택이 아닌 레지스터에 저장했을 것 입니다. 그러나 큰 프로그램에서 많은 레지스터가 이미 사용중 일때는 이런식으로 해야할 때도 있습니다. 

# 수식 ab - 12a + 18b - 7을 평가하는 프로그램
#
# 설정: 지연로딩 (delayed load) OFF; 지연분기 (Branch delays) OFF,
#           트랩파일 (Trap file)   ON; 의사명령 (Pseudoinstructions) ON   

        .globl  main

main:   
        lw      $t0,a          # a 구하기
        lw      $t1,bb         # b 구하기
        mul     $t0,$t0,$t1    # a*b
        subu    $sp,$sp,4      # a*b 를 스택에 집어넣기
        sw      $t0,($sp)
        
        lw      $t0,a          # a 구하기
        li      $t1,-12        # 
        mul     $t0,$t0,$t1    # -12a
        subu    $sp,$sp,4      # -12a 를 스택에 집어넣기
        sw      $t0,($sp)
        
        lw      $t0,bb         # b 구하기
        li      $t1,18         # 
        mul     $t0,$t0,$t1    # 18b
        subu    $sp,$sp,4      # 18b 를 스택에 집어넣기
        sw      $t0,($sp)

        li      $t1,-7         # 합을 -7로 초기화
        lw      $t0,($sp)      # 18b 를 스택에서 빼내기
        addu    $sp,$sp,4
        addu    $t1,$t1,$t0    # 18b -7
                
        lw      $t0,($sp)      # -12a 를 스택에서 빼내기
        addu    $sp,$sp,4
        addu    $t1,$t1,$t0    # -12a + 18b -7
                
        lw      $t0,($sp)      # ab 를 스택에서 빼내기
        addu    $sp,$sp,4
        addu    $t1,$t1,$t0    # ab - 12a + 18b -7
         
done:   li      $v0,1          # 합 출력
        move    $a0,$t1
        syscall
        li      $v0,10         # 끝
        syscall   

        .data
a:      .word  0
bb:     .word  10

질문: (생각을 요하는 문제) 스택에 너무 많은 것들을 집어넣으면 메모리가 가득 찰까요?

실행시 스택 (런타임 스택, Runtime Stack)

http://chortle.ccsu.edu/AssemblyTutorial/Chapter-25/ass25_9.html

답: 네

아무리 좋은 컴퓨터 시스템이라 할지라도 메모리의 양은 유한합니다. 그래서 메모리에 존재하는 워드의 수보다 많은 워드를 집어넣는것이 가능합니다. 프로그램이 처음 실행될때 운영체제가 꽤 큰 스택을 주기 때문에, 그런일은 보통 무한루프때문에 일어납니다.

attachment:memoryLayout.gif

위의 사진은 일반적인 운영체제가 어떻게 메모리를 관리하는지 보여줍니다. 최고 4기가 바이트의 (가상) 메모리가 존재합니다. (주: 메모리 주소가 32비트 크기라고 가정할 때에; 64비트 운영체제에서도 메모리는 이와 비슷한 방식으로 관리됩니다) 메모리 구간 0x10000000 에서부터 0x7FFFFFFF 까지, 약 1.8기가 바이트가 데이터와 스택 세그먼트가 들어갈수 있는 자리입니다.

프로그램이 시작될때 스택포인터 $sp는 유저 메모리의 맨 위 바로 아래 마지막 워드의 주소인 0x7FFFEFFC를 가리킵니다. 프로그램이 실행되는동안 스택은 아래 (사용가능한 공간) 으로 확장됩니다. 데이터 세그먼트는 프로그램이 실행되면서 위로 자랍니다. 물론 동적인 프로그램에서는 두 세그먼트 모두 확장과 수축을 반복합니다. 만약 더이상 메모리가 남아있지 않다면 두 세그먼트는 중간 어디선가 만나게 됩니다.

다른 (후진) 방법으로는, 0x10000000에서 0x7FFFFFFF까지의 메모리를 반으로 나눠 스택과 데이터 구간으로 쓰는 방법이 있습니다. 그러나 이런 방법으로는 데이터세그먼트에 아주 적은 데이터가 있더라도 스택이 그 공간에 갇히는 수가 생깁니다.

질문: 어느 세그먼트가 코드를 저장하는데 쓰입니까?

Recent Posts

Archive Posts

Tags

About

Joinc proposes educational computer-engineering contents. Especially, the contents focus on recently popular and meaningful topics, technically helpful for those who already work or to-be developers in the computer industry and theoretical or typical topics covered in undergraduate courses.

Get in Touch

  • joinc.help@gmail.com

Categories

Copyrights © - Joinc, All Rights Reserved.
Inherited From - Yundream Rebranded By - Joonphil