CSAPP 1장 마무리
CSAPP 1장을 마무리했다. 1장 후반부는 메모리의 계층구조, 운영체제 개론, 네트워크, 암달의 법칙, 동시성과 병렬성에 대한 내용이었다.
캐시메모리
실제세계에서는 큰 물체는 굼뜨고 작은 물체는 빠른 경향이 있다. 컴퓨터의 세계도 마찬가지다. 하드디스크는 용량이 큰 대신에 데이터를 제공하는데 시간이 오래 걸린다. 반대로 메모리는 크기가 작은 대신에 데이터를 빠르게 전달한다. 프로세서는 더욱 더 빠르게 전달한다. 하지만 컴포넌트 하나가 빠르다고 해서 시스템 전체가 빨라지지는 않는다. 시스템의 속도는 결국에는 가장 느린 컴포넌트의 영향을 가장 크게 받기 때문이다. 하드디스크의 경우, 작업에 따라 배제를 할 수 있지만 프로세서와 메모리는 그렇지 않다. 게다가 프로세서는 빠르게 개발되어 왔지만 메모리는 그렇지 않았다. 프로세서와 메모리 사이의 시간 격차를 줄이기 위해 캐시 메모리가 도입되었다. 캐시 메모리는 프로세서와 메모리의 중간계층이다. 프로세서가 자주 쓰는 데이터를 임시로 저장하는 공간이다. 따라서 프로세서는 필요한 데이터를 빠르게 취할 수 있고 메모리는 데이터를 확보하는 시간을 벌 수 있다.
운영체제
자유는 질서 속에 나온다. 응용 프로그램이 하드웨어와 자원을 무제한적으로 접근할 수 있게 한다면 컴퓨터 시스템이 붕괴할 수 있다. 자원을 효율적으로 배분하고 응용프로그램에게 하드웨어 제어를 추상화환 통로를 제공하기 위해 운영체제가 도입되었다. 운영체제는 커널을 갖고 있다. 응용프로그램은 커널을 통해서만 하드웨어를 사용할 수 있다.
운영체제는 컴퓨터 시스템의 성능에도 관여한다. 여러 프로세스를 동시에 실행 할 수 있는 것도 운영체제 덕분이다. 컨텍스트 스위칭을 통해 프로세스가 동시에 진행되는 것처럼 작업을 할 수 있다. 컨텍스트란 프로세스를 실행하는데 필요한 모든 상태정보다.
네트워크
컴퓨터 내에서 컴포넌트 간에 데이터를 교환하는 것처럼 컴퓨터 간에도 데이터를 교환할 수 있다. 특히 네트워크 기술이 발달함에 따라 사실상 모든 컴퓨터가 연결될 수 있다. 이를 가능하게 하는 기술이 네트워크 기술이다. 컴퓨터는 네트워크 장치를 통해 연결 된 컴퓨터를 또 다른 입출력 장치로 간주한다.
암달의 법칙
컴퓨터의 성능개선은 어떻게 계량되는가? 암달의 법칙을 통해 부품의 성능 개선이 전체 시스템에 어떤 영향을 주는지를 상대적으로 계산할 수 있다. 암달의 법칙은 컴퓨터의 성능을 개선하려면 컴포넌트 하나가 아닌 시스템 전반을 개선해야한다는 깨달음을 준다.
동시성과 병렬성
여러 프로세스가 동시에 처리되는 개념을 동시성이라고 한다. 동시성을 구현하기 위한 컴퓨터의 동작을 병렬성이라고 한다. 프로세스, 쓰레드, SIMD, 멀티코어 등이 병렬성을 구현하는데 쓰인다.
자료구조와 알고리즘
연결리스트
연결리스트는 데이터가 논리적인 순서를 가진 자료구조다. 배열과 다르게 데이터가 반드시 물리적으로 연속되어 있지는 않다. 연결리스트는 다양한 자료구조의 기반이 된다. 트리, 그래프, 트라이, 힙, 해시테이블 등을 구현할 때 연결리스트를 사용한다. 연결리스트의 기본단위는 노드다. 노드는 값과 포인터로 구성된다. 노드의 포인터의 자료형은 노드다. 즉, 연결리스트의 노드는 자기참조형이다. 자기참조형이란 자기와 동일한 형태를 참조하는 구조이다.
트리
연결리스트는 선형적 자료구조이면 트리는 비선형적 자료구조다. 트리는 루트 노드를 시작으로 부모-자식 관계의 자료구조다. 계층구조를 표현할 때 트리를 사용한다. 트리는 자식 노드의 최대차수에 따라 종류가 달라진다. 또한, 자식노드의 순서를 구분하는지 여부에 따라 종류가 나뉜다. 트리를 탐색하는 방식에 따라 BFS, DFS로 구분한다. 루트노드에서 리프노드로 수직 방향으로 조회하는 순회를 DFS라고 하고 루트노드로부터 가까운 레벨부터 조회하는 순회를 BFS라고한다.
이진검색트리
이진검색트리는 검색에 특화된 트리다. 이진검색트리는 오름차순 순으로 데이터를 제공한다. 데이터를 조회할 때도 logN 수준의 실행시간이 필요하다. 이진검색과 유사한 방식으로 데이터를 조회한다.
그래프
그래프는 트리의 확장이다. 그래프는 관계를 표현하는 자료구조로서 정점을 기본 단위로한다. 정점간에는 간선으로 연결 될 수 있다. 즉, 반드시 연결될 필요는 없다. 현실에서는 객체는 관계를 맺는다. 따라서 현실의 문제는 그래프를 통해 해결할 수 있다. 그래프도 트리처럼 DFS, BFS를 할 수 있다.