알람이 왜 안 울렸지..
8:05 입실
CSAPP
연습문제 3.16 (어제 이어서)
testq %rdi, %rdi
이 부분이 ZF를 1로 설정하는 이유?
testq는 비트AND 연산을 통해 조건 코드를 변경시킨다.
이때 똑같은 값을 test하고 있기 때문에 %rdi 값이 0이면
ZF가 1로 바뀌고, 그렇지 않은 다른 값이면 ZF는 0이다.
예를 들어 0000, 0000이면 비트AND 결과가 0000이기 때문에 결과적으로 ZF는 0이지만,
0010, 0010이면 비트AND 결과가 0010
1111, 1111이면 비트 AND 결과가 1111
0001, 0001이면 비트 AND 결과가 0001 등 0이 될 수 없다.
void cond(short a, short *p)
{
if (a && *p < a)
*p = a;
}
// a in %rdi, p in %rsi
// cond:
// testq %rdi, %rdi ; a값이 0이 아닌지 체크
// je .L1 ; a값이 0이면 L1로 점프(함수 종료)
// cmpq (%rsi), %rdi ; *p와 a비교
// jge .L1 ; *p >= a 인지 체크해서 충족하면 L1로 점프(함수 종료) 교재에서는 이 부분이 jge가 아니라 jle이다.
// movq %rdi, (%rsi) ; a의 값을 *p로 할당
// .L1:
// rep; ret ; 함수 종료void goto_cond(long a, long *0) {
if (p == 0)
goto done;
if (*p >= a)
goto done;
*p = a;
done:
return;
}연습문제 3.18
영문판, 번역본 다 정답이 달라서 모르겠음..
x in %rdi
y in %rsi
z in %rdx
test:
leaq (%rdx,%rsi), %rax ; z + y
subq %rdi, %rax ; z + y - x
cmpq $5, $rdx ;
jle .L2 ; 5 <= z면 L2 점프 (if문 미충족)
cmpq $2, %rsi ;
jle .L3 ; 2 <= y면 L3 점프 (if문 미충족)
movq %rdi, %rax ; 위 두 조건 미충족 시 x
idivq %rdx, %rax ; x / z
ret
.L3:
movq %rdi, %rax ; x
idivq %rsi, %rax ; x / y
ret
.L2:
cmpq $3, %rdx ;
jge .L4 ; 3 >= z면 L4 점프 (if문 미충족)
movq %rdx, %rax ; z
idivq %rsi, %rax ; z / y
.L4:
rep; ret내가 푼 답안 (교재 정답과 다름)
short test(short x, short y, short z) {
short val = z + y - x ;
if (5 > z) {
if (2 > y)
val = x / z;
else // L3
val = x / y;
} else if (3 < z) // L2
val = z / y;
return val; // L4
}연습문제 3.32
| Label | PC | Instruction | %rdi(u) | %rsi(v) | %rax | %rsp | * %rsp | Description |
|---|---|---|---|---|---|---|---|---|
| M1 | 0x400560 | callq | 10 | - | - | 0x7fffffffe820 | - | Call first(10) |
| F1 | 0x400548 | lea | 10 | - | - | 0x7fffffffe818 | 0x400565 | x+1 |
| F2 | 0x40054c | sub | 10 | 11 | - | 0x7fffffffe818 | 0x400565 | x-1 |
| F3 | 0x400550 | callq | 9 | 11 | - | 0x7fffffffe818 | 0x400565 | call last(9, 11) |
| L1 | 0x400540 | mov | 9 | 11 | - | 0x7fffffffe810 | 0x400555 | u |
| L2 | 0x400543 | imul | 9 | 11 | 9 | 0x7fffffffe810 | 0x400555 | u * v |
| L3 | 0x400547 | retq | 9 | 11 | 99 | 0x7fffffffe810 | 0x400555 | Return 99 from last |
| F4 | 0x400555 | repz retq | 9 | 11 | 99 | 0x7fffffffe818 | 0x400565 | Return 99 from first |
| M2 | 0x400565 | mov | 9 | 11 | 99 | 0x7fffffffe820 | - | Resume(%rdx에 99 할당) |
%rsp는 스택 포인터로 사용된다.
스택이 쌓이면 스택 포인터는 8바이트씩 감소한다.
각 라벨의 상태는 해당 라벨의 동작이 모두 완료된 후의 스냅샷을 나타낸다.
프로그램 카운터(PC)는 다음에 실행할 인스트럭션의 주소를 담고 있다.
16진수 뺄셈 헷갈려서 착각함
16진수 계산 정리하기
0x20 - 0x18 = 0x8
0x18 - 0x10 = 0x8
연습문제 3.32 설명
M1에서 최초로 first(10)함수가 호출된다.
호출되면서 스택이 1개 쌓이며(주소가 8바이트 감소) 쌓이는 스택은
first(10)이 호출된 시점의 바로 다음 인스트럭션의 주소인 0x400565값을 가리킨다.
F1에서 lea로 유효주소를 계산한다. 실제로 유효 주소를 계산하는 건 아니고,
lea를 활용해서 메모리에 접근하지 않고 x에 1를 더하는 연산을 레지스터 접근만으로 수행한다.
계산 결과를 %rsi에 저장한다.
(lea는 메모리 접근 없이 계산을 수행한다.)
F2에서 sub로 x-1을 계산한다. 계산 결과를 %rdi에 저장한다.
F3에서 last(u, v)을 호출한다. %rdi(u)에는 x-1(9)값이, %rsi(v)에는 x+1(11)이 할당되어 있다.
함수를 호출했기 때문에 스택을 1개 쌓으며(주소가 8바이트 감소) 쌓이는 스택은
last(u, v)가 호출된 인스트럭션의 바로 다음 인스트럭션 주소인 0x400555를 가리킨다.
L1에서 u값을 %rax에 저장한다
L2에서 u에 v를 곱한 값을 다시 %rax에 저장한다.
L3에서 retq을 통해 현재 스택 포인터 %rsp레지스터 값을 읽고, PC를 이 값으로 설정한다.
이후 스택을 감소시켜(스택 포인터 주소를 8바이트 증가시켜) 이 값을 스택에서 제거한다.
스택에서 제거되면 다시 전체 코드의 종료 지점인 0x400565가 반환 주소로 스택 최상단에 위치한다.
(retq는 PC가 스택의 최상단 값을 가리키도록 설정한 수 스택을 감소(주소 증가)시킨다.)
F4에서 retq를 통해 현재 스택 포인터 %rsp레지스터 값을 읽고, PC를 이 값으로 설정한다.
이후 스택을 감소시켜(스택 포인터 주소를 8바이트 증가시켜) 이 값을 스택에서 제거한다.
스택에서 제거되면 스택에는 최초 스택 값인 0x7fffffffe820이 스택 최상단에 위치한다.
(이 값은 주솟값이며 참조하는 값이 없다.)
F4에서 설정된 PC에 따라 지금까지 계산된 값을 %rdx레지스터에 반환하는 코드가 실행되며 전체 코드가 종료된다.
이렇게 설명했는제 GPT가 전체적으로 흐름을 잘 설명했다고 칭찬해 줌..
연습문제 3.33
*u += a;
*v += b;
return sizeof(a) + sizeof(b);
procprob:
movslq %edi, %rdi ; 4바이트 %edi를 8바이트 %rdi로 확장 이동
addq %rdi, (%rdx) ; 8바이트 %rdi값을 %rdx 위치의 값과 더해서 %rdx 주소에 저장
addb %sil, (%rcx) ; 1바이트 %sil값을 %rcx 위치의 값과 더해서 %rcx 주소에 저장
movl $6, %eax ; 4바이트 레지스터 %eax의 값에 6을 더함.
ret풀이 설명
procprob(a, b, u, v)에서 매개변수의 데이터 타입을 구하는 문제이다.
%eax는 리턴값에 사용되는 레지스터다. 이 값이 6을 반환한다.
마지막 return이 a사이즈와 b사이즈를 더하면 6이니까,
a를 4바이트라고 가정하면, b는 2바이트이다.
그럼 %edi가 원래 4바이트니까, a라고 가정하면
a에 더하는 u는 8바이트이다.
그럼 나머지 v는 남은 1바이트가 된다.
즉 a가 4바이트라는 가정에서
a는 int
b는 short
u는 long(8바이트)
v는 char이다.
연습문제 3.34
long P(long x)
x in %rdi
P:
pushq %r15 ; 칼리-세이브드 레지스터 보존을 위해 스택에 푸시
pushq %r14 ; 칼리-세이브드 레지스터 보존을 위해 스택에 푸시
pushq %r13 ; 칼리-세이브드 레지스터 보존을 위해 스택에 푸시
pushq %r12 ; 칼리-세이브드 레지스터 보존을 위해 스택에 푸시
pushq %rbp ; 칼리-세이브드 레지스터 보존을 위해 스택에 푸시
pushq %rbx ; 칼리-세이브드 레지스터 보존을 위해 스택에 푸시
subq %24, %rsp ; %rsp 스택 포인터를 24바이트 확보
movq %rdi, %rbx ; x값(a0)을 %rbx 레지스터(베이스 레지스터)에 저장
leaq 1(%rdi), %r15 ; x+1(a1)을 %r15에 저장
leaq 2(%rdi), %r14 ; x+2(a2)을 %r14에 저장
leaq 3(%rdi), %r13 ; x+3(a3)을 %r13에 저장
leaq 4(%rdi), %r12 ; x+4(a4)을 %r12에 저장
leaq 5(%rdi), %rbp ; x+5(a5)을 %rbp에 저장
leaq 6(%rdi), %rax ; x+6(a6)을 %rax에 저장
movq %rax, (%rsp) ; x+6을 현재 스택 포인터가 가리키는 위치의 메모리에 저장
leaq 7(%rdi), %rdx ; x+7(a7)을 %rdx 레지스터에 저장
movq %rdx, 8(%rsp) ; x+8(a8)을 현재 스택포인터의 8바이트 전에 저장
movl $0, %eax ; 0을 리턴
call Q ; 함수 Q를 호출풀이 설명
1. 피호출자-저장 레지스터에 저장되는 값: a0 ~ a5
2. 스택에 저장되는 지역값: a6, a7
3. 모든 지역 값을 피호출 제리스터에 저장할 수 없는 이유: 할당 가능한 레지스터가 최대 6개로 모두 사용함.
피호출자-저장 레지스터가 존재하는 이유 알았음!
지역 변수를 스택에 저장할 때는 해당 스택 프레임은 해당 프로시저만 접근 가능하기 때문에 상관 없음.
하지만 레지스터에 지역 변수를 저장할 때는 모든 프로시저에서 해당 레지스터에 접근하거나 값을 덮어 씌울 수 있음.
그래서 지역 변수를 레지스터에 저장해서 쓸 때는, 항상 그 전에 레지스터의 값을 임시로 내 스택 프레임에 할당했다가, 함수가 반환될 때 다시 복구해야 함.
그렇지 않으면 다른 프로시저에서 레지스터에 할당한 값을 의도치 않게 변조되어 예상치 않은 동작을 할 수 있음. 이건 레지스터를 책임감 있게 사용하려는 관례의 일부다!
이러한 과정은 함수의 프롤로그와 에필로그에서 처리됨.
호출자와 피호출자가 뭐야?
호출자(caller): 함수 호출을 초기화 하는 블록. 다른 함수를 호출하는 함수
피호출자(callee): 호출자에 의해 호출되고 실행되는 함수(현재 실행)
예를 들어 A()가 B()를 호출하면 A는 호출자, B는 피호출자
스택 프레임 개념을 공부하니까 함수 지역 변수 이해됨!
함수 내의 지역 변수를 전역이나, 다른 함수 내에서 접근 못하는 건 당연!
왜냐면 스택 프레임이 다르니까 접근할 수 없다!!
함수의 프롤로그와 에필로그
함수의 시작과 끝에 실행되는 일련의 명령어들
프롤로그: 스택 프레임 생성, 피호출자 저장 레지스터 보존
에필로그: 스택 프레임 해제, 피호출자 저장 레지스터 복원, 반환 주소 복원 및 함수 반환
연습문제 3.35
// x in %rdi
rfun:
pushq %rbx
movq %rdi, %rbx
movl $0, %eax
testq %rdi, %rdi
je .L2
shrq $2, %rdi
call rfun
addq %rbx, %rax
.L2
popq %rbx
retlong rfun(unsigned long x) {
if (x == 0)
return 0;
unsigned long nx = x>>2;
long rv = rfun(nx);
return x + rv;
}연습문제 3.36
int P[5];
short Q[2];
int *R[9];
double S[10];
short *T[2];
| Array | Element size | Total size | Start adress | Element i |
|---|---|---|---|---|
| P | 4 | 20 | xp | xp + 4i |
| Q | 2 | 4 | xq | xq + 2i |
| R | 8 | 72 | xr | xr + 8i |
| S | 8 | 80 | xs | xs + 8i |
| T | 8 | 16 | xt | xt + 8i |
연습문제 3.37
| Expression | Type | Value | Assembly code |
|---|---|---|---|
| P[1] | short | M[xp+2] | movw 2(%rdx), %ax |
| P + 3 + i | short* | xp + 6 + 2i | leaq 6(%rdx,%rcx,2),%rax |
| P[i * 6 - 5] | short | M[xp + 12i - 10] | movw -10(%rdx,%rcx,12),%ax |
| P[2] | short | M[xp+4] | movw 4(%rdx), %ax |
| &P[i + 2] | short* | xp + 2i + 4 | leaq 4(%rdx,%rcx,2),%rax |
레지스터 이름 어떻게 외워.. 했는데 자주 보니까 익숙해짐.
연습문제 3.38
레지스터
%esp 스택 포인터
%ebp 스택 베이스
컴파일러
컴파일러는 단순히 소스코드를 바이너리 코드로 바꾸는 과정이 아니다.
컴파일러 옵션에 따라 디버깅 정보를 추가하거나, 오류 검출 함수를 추가하거나
최적화 수준을 결정할 수 있다.
C언어
공용체 왜 쓰는거야?
여러 타입의 데이터를 같은 메모리 위치에 저장해서 메모리 효율적으로 사용 가능하다!
예를 들어 32비트를 할당하고 정수로 쓰다가 부동 소수점 수를 표현해야 할 때 또 다른 공간을 할당하는 게 아니라 공용체라면 기존에 정수가 할당된 위치에 바로 부동 소수점 수를 할당할 수 있다!
즉, 기존의 변수는 지정된 데이터 타입만 가지고 재활용 할 수 있지만, 공용체는 다양한 타입의 데이터를 재활용 할 수 있다.
공용체 예시
#include <stdio.h>
typedef union {
int i;
float f;
} IntOrFloat;
int main() {
IntOrFloat val;
// 정수 값으로 사용
val.i = 42;
printf("As integer: %d\n", val.i);
// 부동 소수점 수로 사용
val.f = 3.14f;
printf("As float: %f\n", val.f);
return 0;
}공용체는 자료형을 유연하게 다룰 수 있다!
파이썬
파이썬도 컴파일을 한다!
파이썬이 동작하는 원리에 대해서 알았음!
파이썬은 인터프리터 언어인데 결국에는 바이너리 코드로 변환되어야 실행될 수 있는 거 아닌가? 하는 의문에서 시작
정답은 파이썬은 C처럼 프로세서가 직접 인식하고 실행할 수 있는 바이너리 코드로 변환되는 것이 아니라, 파이썬 가상 머신(PVM)에서 실행 가능한 파이썬만의 바이트 코드로 변환된다고 함.
구체적으로는 .py를 실행하면 .pyc로 컴파일되고,
이 .pyc가 파이썬 가상 머신 위에서 실행되는 것.
그래서 파이썬에서 에러가 발생하는 것은
1. 컴파일 시 발생하는 에러
2. 런타임 시 발생하는 에러
로 나뉠 수 있음.
에러 메시지를 보면 다 런타임에서 에러가 발생하는 것 같지만
아래 실험을 보면 그렇지 않음.
컴파일 시 에러가 발생하는 증거
print("hello, world!")
# 닫는 괄호가 없음
print("hi, world! 만약 파이썬이 무조건 런타임 시 에러를 발생 시킨다면,
위 코드는 print("hello, world!")는 동작해야 함.
그런데 이 코드를 실행시키면 "hello, world!"가 찍히지 않음.
classbinu@192 week3 % python3 error.py
File "/Users/classbinu/Documents/krafton/week3/error.py", line 3
print("hi, world!
^
SyntaxError: unterminated string literal (detected at line 3)즉, 이 코드는 컴파일 단계에서 에러가 발생하는 것
반면에 아래 코드는 런타임 시 에러가 발생한다.
print("hello")
a = "a"
a[0] = "b"classbinu@192 week3 % python3 error.py
hello
Traceback (most recent call last):
File "/Users/classbinu/Documents/krafton/week3/error.py", line 3, in <module>
a[0] = "b"
~^^^
TypeError: 'str' object does not support item assignment코드를 보면 hello가 찍힌 후 에러가 발생한다.
즉 이때는 컴파일 시 구문 등에서는 문제가 없지만,
immutable한 객체인 문자열의 값을 변경하려고해서 런타임 시 문제가 생기는 것!
파이썬의 동작 원리에 대해서 알게 되어서 후련!
바이너리 코드 vs 바이트 코드
바이너리 코드는 (특정) CPU가 바로 실행할 수 있는 코드. 바이너리 코드는 특정 아키텍처에 맞춰져 있으므로 플랫폼 종속적이다.
바이트 코드는 CPU가 직접 실행하지 않고 가상 머신 소프트웨어가 해석해서 실행하는 코드. 바이트 코드는 가상 머신만 있으면 되니까 플랫폼(CPU) 독립점.
알고리즘
CSAPP 공부하느라 미뤄두었던 알고리즘 벼락치기!!
백준 1931 회의실 배정
import sys
N = int(sys.stdin.readline().strip())
meetings = []
for _ in range(N):
start, end = map(int, sys.stdin.readline().strip().split())
meetings.append((end, start))
meetings.sort()
end_time = 0
count = 0
for meeting in meetings:
end, start = meeting
if start >= end_time:
end_time = max(end, end_time)
count += 1
print(count)duration을 두고 회의 시간이 짧은 걸로 소트해서 했을 때 후반분에서 테스트 케이스 통과 못함.
단순히 일찍 끝나는 시간을 1순위로, 시작 시간을 2순위로 잡아도 회의 소요 시간이 반영되는 정렬이니까 duration이 굳이 없어도 됨.
회의실 배정 문제는 그리지 알고리즘의 최적해를 구하기 위한 그리디 선택 속성과 최적 부분 구조를 충족하고 있기 때문에 그리디 알고리즘으로 최적 알고리즘을 구할 수 있음.
백준 1946 신입 사원
입력값이 순위인데 점수로 착각해서 계속 헤맴..
내부 단편화 vs 외부 단편화
그냥 갑자기 생각나서 정리해 봄
'내부', '외부'는 할당되는 메모리 블럭이 기준!
내부 단편화: 할당된 메모리 영역에서 사용되지 않는 메모리 영역이 생기는 것
외부 단편화: 할당되지 않은 메모리 영역이 여기 저기 흩어져 있는 것
왜 각각 '내부', '외부'일까?
내부 단편화는 할당된 메모리 블록 '내부'에서 발생하는 메모리 낭비 현상
외부 단편화는 할당되지 않은 메모리 블록(즉 할당된 메모리 블록 기준 '외부')으로 인해 발생하는 메모리 낭비 현상
어떤 차이가 있나?
내부 단편화는 메모리 할당 과정에서 발생한다. 할당되는 메모리 블록이 실제 필요한 메모리 공간보다 크면 낭비 공간이 생긴다. 즉, 과도한 메모리 할당으로 인해 생긴다.
외부 단편화는 할당과 해제가 반복되는 과정에서 생긴다. 이 과정에서 메모리 자투리들을 모으면 충분히 활용 가능한 메모리 공간임에도 메모리 여기 저기 흩어져 있어서 메모리가 낭비되는 것이다. 즉, 메모리 할당과 해제의 누적된 효과로 인해 생긴다.
어떻게 해결하나?
내부 단편화는 가변 분할 방식(동적 메모리 할당)이나 프로그램에 맞는 블록으로 빈번한 메모리 재할당으로 해결할 수 있음.(단 오버헤드 발생)
외부 단편화는 메모리 압축(연속되지 않는 메모리를 주기적으로 정리), 페이징
(페이징은 페이지 단위로 메모리를 나누고 물리적으로 연속되지 않아도 메모리를 사용할 수 있게 하는 기법, 하지만 페이징은 고정 크기로 메모리를 분할하기 때문에 내부 단편화가 발생할 수 있음.)
