목차 그래프란? 그래프와 트리의 차이 무향그래프, 유향(방향)그래프 인접, 가중치 그래프 그래프 표현 인접 행렬 인접 리스트 간선 리스트 그래프 탐색 깊이 우선 탐색(DFS) 너비 우선 탐색(BFS) 그래프 표현 방법과 시간복잡도 그래프란? 그래프란, 객체(사물 또는 추상적 개념)들과 객체들 사이의 연결관계를 표현합니다. 예를 들면 지하철에서 다른 역으로 가는 최단 경로를 찾아주는 서비스도 그래프 알고리즘을 사용합니다(무향 그래프).또한, 정점(Vertex)들의 집합과 정점을 연결하는 간선(Edge)들의 집합으로 구성된 자료구조입니다. 다음과 같이 그래프를 표현할 수 있습니다. G = (V, E), V = 정점들의 집합, E = 간선들의 집합. V개의 정점을 가지는 그래프는 최대 V(V -1)/2 개의 ..

CPU scheduling 문맥교환(Context Switching) 새로운 프로세스에게 CPU를 할당하기 위해 현재 CPU가 할당된 프로세스의 상태 정보를 저장하고, 새로운 프로세스의 상태 정보를 설정한 후 CPU를 할당하여 실행되도록 하는 작업. (Overhead가 발생하는 주요 원인) CPU 스케줄링이란? 메모리에 있는 준비(Ready) 상태의 프로세스 중 하나를 선택해 CPU자원을 할당하는 것 CPU 스케줄링이 일어나는 시점 실행상태에서 대기상태로 전환될 때 (예, 입출력 요청) - Non preemptive(비선점) 실행상태에서 준비상태로 전환될 때 (예, 인터럽트 발생) - preemptive(선점) 대기상태에서 준비상태로 전환될 때(예, 입출력이 종료될 때) 종료될 때(Terminated) ..

Parallel Hardware Coordination 각 코어들은 작업을 협력적으로 수행(이를 Coordination이라 한다)해야 하는데, 다음을 주의해야 한다. Communication : 통신, 프로세스 간 데이터를 전달할 수 있어야 한다. Load balancing : 부하 분산, 한 프로세스만 고역에 시달리게 두어선 안 된다. Synchronization : 동기화, 한 프로세스의 작업이 다른 프로세스들 보다 지나치게 앞서 있어선 안된다. SISD 단일명령-단일자료(SISD, Single Instruction, Single Data )은 전산에서 한 프로세서가 한번에 하나의 명령어를 처리할 때 하나의 메모리에 저장되어 있는 한 데이터를 이용하여 처리하는 것을 일컫는 용어입니다. 폰 노이만 구조..

TLB(변환 색인 버퍼) 변환 색인 버퍼(Translation Lookaside Buffer, TLB)는 가상 메모리 주소를 물리적인 주소로 변환하는 속도를 높이기 위해 사용되는 캐시로, 약칭은 TLB이다. TLB는 최근에 일어난 가상 메모리 주소와 물리 주소의 변환 테이블을 저장하기 때문에 일종의 주소 변환 캐시라고 할 수 있다. TLB는 CPU와 CPU 캐시 사이, CPU 캐시와 메인 메모리 사이 등 여러가지 다른 레벨의 캐시들 사이에서 주소를 변환하는데 사용할 수 있다. 현재 모든 데스크탑 및 서버용 프로세서는 하나 또는 그 이상의 TLB를 메모리 관리 하드웨어에 가지고 있다. 페이지 단위나 세그먼트 단위로 처리하는 가상 메모리를 사용하는 거의 모든 하드웨어는 TLB를 사용한다. CPU는 1차적으로..

아파치 서버 MPM(Apache Multi-Processing Modules) 아파치 서버가 클라이언트에게서 받아들인 요청을 처리하기 위하여 자식 프로세스들에게 분배하는 모듈입니다. prefork 방식과 worker 방식이 있습니다. Prefork 하나의 자식 프로세스가 하나의 스레드를 갖는 구조로, 자식 프로세스는 최대 1024개까지 가능합니다. 프로세스로 운영되기 때문에 스레드 간 메모리 공유를 하지 않습니다(독립적이라 안정적인 대신에 메모리를 많이 사용합니다.). 실행 중인 프로세스 복제하여 실행합니다(메모리 영역까지 같이 복제). 응답 프로세스를 미리 띄워놓고 클라이언트 요청 시 자식 프로세스가 반응하게 되는 방식이며, 일반적으로 single CPU 또는 Dual CPU에서 성능이 좋습니다. wo..

HTTP통신 HTTP통신은 Hyper Text Transfer Protocol의 약자 입니다. Hyper Text(웹 문서를 구성하고 있는 언어인 HTML을 의미합니다)를 전송하기 위한 프로토콜입니다. HTML이란? HTML은 Hyper Text Markup Language의 줄인말로, Hyper Text, 즉 단순하게 text 의미를 넘어서(Hyper) 링크, 이미지 등 다양한 것들을 표현할 수 있다는 의미입니다. HTML은 웹 문서의 뼈대를 구성하는 언어입니다. 모든 웹 문서는 HTML로 이루어져 있고, HTML로 이루어진 문서 만이 브라우저를 통해 웹 문서로서 읽어질 수 있습니다. HTTP의 구성 HTTP통신은 기본적으로 요청(Request)과 응답(Response)으로 이루어져 있습니다. 클라이언..