Day-12
5장 컴퓨터 아키텍처와 운영체제
-컴퓨터는 어떻게 프로그램과 메모리를 관 리할까
2. 프로시저, 서브루틴, 함수
- 프로시저, 서브루틴은 함수와 동일한 말
함수가 동작하는 방법
함수는 실행하고 리턴해야함
함수 리턴하는 과정
- retrurn 할 주소를 105로 설정 (프로그램 카운터라는 곳 안에 메모리 주소가 들어있음)
- 함수 실행해서 계산하기
- 미리 설정해놓은 105주소로 돌아가기
이러한 과정에는 상당히 많은 작업 필요 -> 대부분의 기계가 이런 과정을 돕는 명령어 제공
(ex)ARM 프로세서에서 Branch with link 명령어
(함수를 실행하는 명렁어와 다음 위치를 저장하는 명령어를 하나로 합친 것)
3. 스택
재귀함수
- 함수가 자기 자신을 호출하는 것
- 예시 코드에서 pow() 안에 pow()를 또 사용.
function pow(x, n) {
if (n == 1) {
return x;
} else {
return x * pow(x, n - 1);
}
}
alert( pow(2, 3) );// 8- 예제 : 이미지 압축
- 재귀적 분할(함수 안에 함수 넣어서 분할) 사용
- 분할함수 -> 네 부분으로 나눠서 각 부분을 검사 (1픽셀짜리 조각이 생길 때 까지)
- 재귀함수 -> subdivide 함수 안에서 또 subdivide 함수를 사용함.
트리 구조 - subdivide 함수가 실행된 모습을 나타낸 트리
- 맨 윗 부분은 잎 노드(leaf node)
쿼드 트리 - 각 노드에서 가지가 4개 뻗어나감 (그림에서 가지가 뻗어나가는 사각형 부분을 노드라고 함)
subdivide를 실행할 때의 패턴
- 깊이 우선 순회(DFS) 방식 : 트리 아래로 내려 갈 수 있으면 항상 아래로 내려가고,
더 이상 아래로 내려갈 화살표가 없는 경우에만 옆에 있는 화살표로 넘어감 - 너비 우선 순회(BFS) 방식 : 옆에 있는 화살표를 먼저 방문하고
그 후 아래쪽으로 가는 화살표를 방문하는 방식
- 트리에서 한 번 내려갈 때마다 돌아올 위치를 기억하고,
다시 원래위치로 돌아오면 기억해놨던 위치 삭제
스택 : 필요한 것은 기억해서 쌓아놓는 역할을 하는 구조
- 함수를 실행하면 리턴 될 주소와 함께 실행 순서대로 스택에 쌓임.
- 실행이 완료되면 맨 위 부터 삭제한다.
- push : 스택에 데이터를 넣는 것(쌓이는 것)
- pop: 스택에서 데이터를 빼는 것
- 스택 오버플로 : 더이상 데이터가 쌓일 공간이 없을 때
- 스택 언더플로 : 스택이 비어있는데(데이터가 없는데) 데이터를 스택에서 빼려고 하는 경우
- 이러한 스택은 subdivide 예제에서도 리턴해야할 주소를 기억하기 위해 스택이 사용됨
(주소 뿐만 아니라 변수 저장에도 사용됨) - 스택은 아주 중요하기 때문에 대부분의 컴퓨터 하드웨어는 스택을 지원함
- 소프트웨어로는 스택 오버플로 상황을 항상 검사하지 않아도 되도록 돕는 한계 레지스터가 있음
- 예외 : 소프트웨어가 스택 오버플로 같은 상황을 만나는 상황에서 발생
- 그림 5-5 스택 프레임 : 함수가 실행될 때마다 변수와 리턴할 주소가 같이 저장됨을 표현
- 한국어도 스택 기반 언어 : 명사(목적어) 스택에 쌓고, 그 다음 스택으로 동사를 스택에 쌓는 식.
여러가지 수식 표기법
- 중위 표기법 4 + 8, (1+2)x(3+4) (연산자가 피연산자 사이에)
- 전위 표기법 x+12+34 (연산자를 피연산자 앞에)
- 역 폴란드 표기법 12 + 34 +x (연산자를 피연산자 뒤에)
참고자료
https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90
각성구