2-2장 요약본

컴퓨터구조

2-2장 요약본

lvher 2020. 10. 18. 03:21

먼저 동기화에 대해 알아보겠습니다. 이는 2개의 프로시저가 특정 영역의 메모리를 공유하는 것을 의미하는 데 프로시저 2개를 각각 p1, p2라고 정해보겠습니다. p1가 쓰기를 할 때,p2는 읽기를 합니다. 만약 두 데이터가 동기화가 되지 않은 채 동시에 써버리게 되면 이상한 값이 도출이 되는데 이를 data race라고 합니다. 결과는 접속 순서에 의해 결정이 되죠.

이 동기화는 하드웨어의 지원이 필요합니다. Atomic한 메모리 읽기/쓰기로서 읽기와 쓰기 사이에 다른 접근은 있어서는 안됩니다.

동기화는 하나의 instruction이 될 수도 있습니다.

MIPS 명령어를 한번 살펴보겠습니다.

먼저 load link 즉 링크를 불러오는 것부터 보겠습니다.

ll rt, offset(rS) # rs에서 offset만큼 떨어져있는 data를 rt에 불러옵니다.

그리고 Store condition입니다.

sc rt, offset(rs) # 만약 위에서 ll의 offset값이 바뀌지 않았다면 rt에 1을 집어넣고 바뀌었다면 0을 집어넣습니다.

예를 한번 보겠습니다.

again: 
	addi	$t0, $zero,1	#t0에 1값을 집어넣습니다.
    ll		$t1, 0($s1)		#s1에 0을 더한 값의 주소값을 $t1에 불러옵니다.
    sc		$t0, 0($s1)		#만약 0번째 $s1의 값이 바뀌었다면 0을 바뀌지 않았다면 1을 넣습니다.
    beq		$t0, $zero,again	#만약 $t0가 0이라면 again instruction 처음으로 돌아가고 그렇지 않다면 밑의 instruction을 수행합니다.
    add		$s4, $zero,$t1		#불러온 주소 값을 $s4에 넣습니다.

위의 MIPS 코드는 atomic swap이라고 하는데 암호 변수를 설정하고 확인하는데 쓰입니다. 주로 암호화폐같은 곳에 쓰인다고 하네요.

그러면 잠시 숨돌릴겸 좀 쉬운 걸로 넘어가도록 합시다. 바로 우리가 적는 코드가 어떻게 기계가 이해를 할 수 있는지 그것을 번역하는 과정에 대해 한번 살펴보도록 하겠습니다.

1. 먼저 C program을 작성하면 compiler가 그것을 assembly 언어 프로그램으로 변환해줍니다. 이 과정에서 많은 컴파일러들이 직접적으로 객체 모듈들을 생성하죠.

2. 다음에 어셈블러가 기계어로 된 모듈로 이루어진 객체와 라이브러리 경로로 이루어진 객체를 생성합니다. 이 객체들은 linker에 의해 실행가능한 기계 언어 프로그램으로 바꾸어주죠. 이 과정을 static linking 즉 정적 링킹이라고 합니다.

3. 이 실행가능한 기계언어 프로그램을 로더가 메모리에 저장을 시켜줍니다.

어셈블러의 Pseudoinstruction이란 이름에서 알 수 있듯이 가짜 instruction으로 실제로 실행이 되지 않고 그저 어셈블러의 상상의 산물입니다.

예를 들어 보겠습니다.

move $t0, $t1 -> add $t0, $zero, $t1

blt $t0, $t1, L -> 	slt $at, $t0, $t1
          		bne $at, $zero, L

위에 보면 move라는 명령어를 썼는데 실제로는 이런 명령어를 우린 배운 적이 없습니다. 그 뜻은 실제로 존재하지 않는다는 것이죠. 그리고 밑의 blt도 마찬가지입니다. 여기서 blt는 branch less than이라는 뜻인데 branch를 비교하는 명령어는 존재하지 않습니다. 그래서 우측의 코드가 제대로 된 MIPS 코드입니다.

또 $at(register 1) 이라고 적은 것도 있는데 이 또한 무슨 말인지 이해는 가지만 실제로 작동하지 않는 없는 코드입니다.

그 외에도 bgt, ble, bge가 있는데 혹시나 시험치거나 코드를 짜거나 할때 헷갈릴 수도 있으니 넘어갑시다.

자 그러면 우리가 위에서 코드를 기계가 이해하도록 변환해주는 과정을 배웠죠? 거기서 객체 모듈이라는 말이 있던 것을 기억하시는가요? 방금 배워서 기억 못하신다면 다시 가서 보고 오세요 ㅎ 복습할겸...

어셈블러나 컴파일러는 프로그램을 기계 instruction으로 변환시켜주죠. 여러 조각들로부터 완성된 프로그램을 짓는데 필요한 정보를 제공해 주는 것이 바로 객체 모듈(Object module)이라고 합니다.

이 객체 모듈에는 다음과 같은 것들이 있습니다.

- 헤더: 객체 모듈안의 내용물을 설명해 준 것

- Text segment: instruction들을 번역한 것

- 정적 데이터 segment : 프로그램의 수명을 위한 할당된 데이터

- Relocation info: 불러온 프로그램의 절대 위치에 기반한 내용물들을 위한 것

- Symbol table: 글로벌한 정의들과 외부 레퍼런스들(참조들)

- 디버그 정보: 소스코드와 관련있는 것

링킹 객체 모듈 또한 위에서 한번 언급했습니다....음 아닌 것 같네요. 이 링킹 객체 모듈은 실행가능한 이미지들을 생성합니다. 먼저 segment들을 합치고(merge) 라벨들을 분해하는데 정확하게는 해당 라벨들의 주소를 결정합니다. 그리고 외부참조와 위치에 의존적인 것들을 해결해줍니다.

링킹 객체 모듈은 relocating loader에 의해서 고쳐지는데 이는 불러온 자료를 재배치하는데 쓰입니다.

디스크의 이미지파일을 메모리로 불러올 때 단계가 있습니다.

1. 먼저 segment의 크기를 정하기 위해 헤더를 읽어들입니다.

2. 가상 주소 공간을 생성합니다.

3. 텍스트와 초기화된 데이터를 메모리에 저장합니다.

4. stack에 argument를 넣습니다.

5. 레지스터를 초기화합니다, 스택포인터와 프레임 포인터, 전역 포인터도 포함합니다.

6. 시작루틴으로 jump합니다. 즉 시작점으로 돌아간다는 것이죠.

동적 링킹은 정적 링킹의 반대죠. 정적링킹은 위에 우리가 쓴 코드를 컴퓨터가 어떻게 이해하는지를 설명하는 부분에 나와있습니다. 객체를 만들고 실행가능한 머신 언어 프로그램으로 만들어주는 단계죠. 동적 링킹은 라이브러리 프로시저가 불러졌을 때 링크와 불러오기를 합니다.

위 표는 객체 파일의 헤더를 나타낸 것으로 Text size는 text segment의 크기를 Data size는 Data segment의 크기를 나타냅니다. 그리고 dependency의 x는 label x와 연결이 되어있고 B는 프로시저를 의미합니다.

자 그러면 이 두 객체 파일의 헤더가 있다고 가정합시다.

이 두 객체가 링킹을 한다고 하면 어떻게 진행이 될까요?

위는 실행이 가능한 파일 헤더로 그 위의 두 헤더가 링킹할 때의 헤더를 보여줍니다. 먼저 Text size가 앞의 두 헤더의 text size를 합한 값이 되었고 data size도 마찬가지가 되었습니다.

먼저 text segment가 40000hex라는 값에서 시작합니다. 그리고 data segment는 1000000hex에서 시작을 합니다. 그리고 $gp 즉 전역 포인터는 10008000 hex로 초기화가 되었습니다. 10008000으로 초기화가 된 이유는 data segment가 1000000(하...0 너무 많아서 헷갈리네요)hex로 시작하기 때문에 거기에 8000을 더 붙여서 10008000hex가 되는 것입니다.

그리고 프로시저A가 프로시저 B로 branch가 되는데 여기에 들어가는 과정이 먼저 첫 번째 jal을 봅시다. jal 위의 lw가 방금 우리가 했던 전역 포인터 초기화 과정이었습니다. jal 400100은 400100이라는 곳으로 점프하고 링킹을 해라는 뜻이죠. 그래서 그곳이 어딘가 봤더니 바로 ... 밑에 있는 곳입니다. 이로써 프로시저 A가 프로시저 B로 왔습니다.(이해 안되시면 open.kakao.com/o/gNr72oCc 로 갠톡주세요. 그래서 온 다음에 $a1이라는 레지스터에 전역 포인터에서 8020hex만큼 떨어진 곳의 주소값을 저장합니다. 그러면 위에서 8000을 붙여서 10008000으로 초기화 되었으니 이번에는 8020을 붙여서 10008020이라는 위치가 담기겠네요. 위의 data segment에서 확인할 수 있습니다. 그리고 sw 밑에 jal은 400000으로 이동해라고 했네요. 따라가보면 위에 있는 lw instruction이 있는 곳으로 이동하게 됩니다. 그런데 여기서 좀 이상하다는 생각이 드실 수 있습니다. 왜 10008000이 될까요? 저도 이거 때문에 직접 2진 계산기 돌려봤습니다. 400000이 hex 즉 16진수니 2진수로 바꿔보았습니다. 결과는 100...0이 더군요. 여기서 2자리를 오른쪽으로 shift, 즉 0을 뒤에 2개 더 붙이고 다시 16진수로 바꿨더니 10000000이 되었습니다!!! 그래서 여기에 8000을 더해서 10008000이 되는 것입니다. 더 나아가 jal 400100같은 경우도 j-format이기 때문에 400100hex이 들어있는 것이 아닌 100040이 들어있는 것입니다.

프로그램을 불러올 때를 한번 살펴볼까요? 디스크에 있는 이미지 파일을 메모리로 넣는 것이라고 위에 설명을 했었습니다. 먼저 segment size를 정하기 위해 헤더를 읽어옵니다. 즉 위에 표같이 생긴 것을 읽어 온다고 보시면 됩니다. 그리고 가상 주소 공간을 생성합니다. 여기에는 주소가 담기겠네요. 그리고 text와 초기화된 데이터를 메모리에 넣습니다. 그리고 argument들을 stack에 집어넣습니다. 이 단계는 우리가 앞에서 많이 했죠. 이유는 바로 다른 함수를 호출할 때 잠시 넣어두고 호출 후에 다시 꺼내기 위해서라고 했습니다. 그리고 레지스터들을 초기화합니다. 여기서 레지스터들은 스택 포인터, 프레임포인터, 전역 포인터를 포함합니다. 그리고 시작 루틴으로 돌아가죠....(어라 생각해보니 이 과정 위에서 먼저 말했었네요... 재탕해서 죄송합니다 복습한다고 생각하십쇼)

그리고 동적 링킹이 있는데 이거는 라이브러리 함수(프로시저)를 부를 때 오직 링킹과 불러오기만 합니다. 동적링킹과 lazy linkage에 관한 내용은 나중에 추가로 더 업데이트 시켜서 확실히 이해되도록 올려놓겠습니다:)

다음은 우리가 C언어에서 많이 썼던 sort 함수를 구현해보도록 하겠습니다.

C code

void swap(int v[], int k)
{
	int temp;
    temp = v[k];
    v[k] = v[k+1];
    v[k+1] = temp;
}

#v는 $a0안에 있고 k는 $a1에 있으며 temp는 $t0에 있다고 합니다.

MIPS

swap:
	sll $t1, $a1, 2 # $t1이라는 임시 레지스터에 k와 4를 곱한 값을 넣습니다.
    add	$t1, $a0, $t1 # $t1에 k*4와 v값을 더하여서 k번째 v값의 주소를 넣습니다.
    
    lw	$t0, 0($t1) # $temp에 k번째 v를 넣습니다.
    lw	$t2, 4($t1) # $t2라는 임시 레지스터에 k+1번 v값을 넣습니다.
    sw	$t2, 0($t1) # k번째 v에 $t2값 즉 k+1번 값을 넣습니다. 여기서 중요한 것이 sw의 방향은 왼쪽에서 오른쪽이라는 것입니다.
    sw	$t0, 4($t1) # k+1번째 v에 temp값 즉 k번 값을 집어넣습니다.
    jr	$ra #swap 함수를 호출한 루트로 돌아갑니다.

위의 코드는 leaf한 방식, 즉 다른 함수를 호출하지 않고 해당 함수가 끝나면 돌아가는 간단한 코드입니다. 그러면 non-leaf한 방식, 즉 다른 함수를 불러오는 방식으로 코드를 짜보겠습니다.

C code

void sort (int v[], int n)
{
	int i, j;
    for(i = 0;i<n; i++){
    	for(j = i - 1; j >=0 && v[j] > v[i + 1]; j -= 1){
 			swap(v,j);
        }
     }
 }

MIPS

	move	$s2, $a0	# $a0를 $s2에 넣습니다.
    move	$s3, $a1	# a1을 $s3에 넣습니다.
    move	$s0, $zero	# $s0에 있는 i를 0으로 만듭니다. i = 0;
for1tst:
	slt	$t0, $s0, $s3 # 만약에 $s0 즉 i가 $s3, 즉 위에 나왔듯이 a1에 있는 n값보다 크거나 같으면 $t0에 0를 넣습니다.
    beq	$t0, $zero, exit1 #만약에 $t0에 있는 값이 0이면 exit1으로 branch합니다.
    addi	$s1, $s0, -1 # $s1에 들어있는 j에 $s0의 i에서 -1한 값을 넣습니다. j = i-1
for2tst:
	slti	$t0, $s1, 0 # 만약 $s1에 들어있는 값인 j가 0보다 작을 경우 $t0에 1을 집어넣습니다.
    bne		$t0, $zero, exit2 # $t0에 0가 있을 경우 exit2로 branch합니다.
    sll		$t1, $s1, 2	# $t1이라는 임시 레지스터에 $s1에 들어있는 j값을 4 곱한 값을 집어넣습니다.
    add		$s1, $s2, $t1
    lw		$t3, 0($t2)
    lw		$t4, 4($t2)
    slt		$t0, $t4, $t3
    beq		$t0, $zero, exit2
    move	$a0, $s2
    move	$a1, $s1
    jal		swap
    addi	$s1, $s1, -1
    j		for2tst
exit2:
	addi	$s0, $s0, 1
    j		for1tst

전체 과정은 stack을 비우는 부분이 대부분이라 추후에 업데이트를 하겠습니다.

자 그러면 배열과 포인터를 봅시다.

요소의 크기에 의해 결정된 인덱스를 곱하거나 배열의 기본 주소에 더하는 방식으로 배열의 번호 붙이기, 즉 인덱싱이 결정이 됩니다.

포인터는 직접 메모리의 주소에 해당합니다. 우리가 C에서 포인터가 주소를 가리킨다고 하는 말이 바로 그것입니다.

예를 들어보겠습니다.

clear라는 배열값을 지우는 함수를 만드는데 그 방법을 포인터와 배열을 통해서 짜면 어떻게 될까요?

C code

clear1(int array[], int size){
	int i;
    for(i = 0; i < size; i + =1)
    	array[i] = 0;
}

먼저 위의 코드는 배열을 이용한 함수입니다.

이를 MIPS로 표현하면 다음과 같습니다.

	move 	$t0, $zero
loop1:
	sll 	$t1, $t0, 2
    add 	$t2, $a0, $t1
    
    sw		$zero, 0($t2)
    addi	$t0, $t0, $a1
    bne		$t3, $zero, loop1

이제 포인터를 이용해 표현해보도록 하겠습니다.

clear2(int *array, int size){
	int *p;
    for(p = $array[0]; p < &array[size];p = p +1)
    	*p = 0;
}

	move	$t0, $a0
    sll		$t1, $a1, 2
    add		$t2, $a0, $t1
loop2:
	sw		$zero, 0($t0)
    addi	$t0, $t0, 4
    slt		$t3, $t0, $t2
    bne		$t3, $zero, loop2

그럼 배열과 포인터를 비교해봅시다. 일단 둘 다 자세히 보니 구조가 거의 같죠? 배열은 반복문 안으로 들어가기 위해 shift를 이용한다는게 차이점입니다. 컴파일러는 같은 효과를 포인터를 사용하여 수작업으로 나타낼 수 있습니다.

그리고 ARM과 MIPS에 대해 나오는데 MIPS가 레지스터 크기가 더 크고 데이터에 주소를 매기는 방법이 3개밖에 없어서 더 쉽습니다.

다시한번 복습을 하면 MIPS에서 가장 중요한 것이 디자인 원칙들입니다.

1. 간단함은 보편성을 선호 simplicity favors regularity

2. 작은 것이 더 빠르다 smaller is faster

3. 일반적인 케이스를 빠르게 만들자 make the common case fast

4.좋은 디자인은 좋은 계획안을 요구한다. good design demands good compromises

그리고 MIPS 명령어를 한번 더 복습하는게 좋은데 이는 위의 MIPS코드들 설명과 함께 추후에 다시 업데이트하겠습니다.