개념 프로세스란 실행 중인 프로그램(실행 파일)이자, 현대의 컴퓨팅 시스템에서 작업의 단위이다. 프로세스는 실행되는 동안 여러 개의 새로운 프로세스들을 생성할 수 있다. 생성하는 프로세스를 부모 프로세스라 부르고, 새로운 프로세스는 자식 프로세스라고 부른다. 새로운 프로세스들은 각각 다시 자식 프로세스들을 생성할 수 있으며, 이는 프로세스 트리를 형성한다. UNIX의 운영체제는 고유한 프로세스 식별자(PID)를 사용하여 프로세스를 구분한다. 자식 프로세스는 부모 프로세스와 동일한 프로그램을 가지며, 주소 공간(fd 테이블 포함)이 복사된다. 프로세스 생성 #include #include // pid_t pid_t fork(void); fork() 시스템 콜로 자식 프로세스를 생성한다. pid_t는 int..

파이프라인 시스템의 일반적인 특징과 원리에 대한 간단한 예시 1. 파이프라인 시스템에서 수행해야 할 일은 여러 개의 일련의 단계들로 나누어진다. - 식당 : 에피타이저 -> 메인 음식 -> 디저트 -> 음료 - 세차장 : 물 -> 비누 -> 닦기 -> 왁스 -> 건조 2. 하나의 일이 다 끝날 때까지 전체 시스템 공정을 차지하지 않는다. - 세차장 : 이전의 차가 비누 단계에서 닦기 단계로 이동하면, 다음 차가 분사 단계로 바로 진행한다. , 하지만 일반적으로 충돌을 피하기 위해 같은 속도로 시스템을 통과해야 한다. * 결과적으로 주요 특징은 시스템 처리량을 증가시킨다는 점이다. 그러나 지연시간도 증가시킨다. - 식당 : 디저트만 원하는 고객이라도 파이프라인 시스템에서는 모든 메뉴를 거쳐야한다. 계산용 ..

특징 1. 동일한 원소 존재시, 원래의 순서를 보존하지 않는 불안정 정렬 3. 일반적으로 최고, 평균, 최악 시간 복잡도O(N * logN) 4. 추가 버퍼가 필요하지 않으므로 공간 복잡도 O(1) 알고리즘 힙(Heap) 자료구조를 이용하여 정렬한다. 힙은 마지막 depth를 제외하고 모든 노드가 왼쪽부터 채워져있는 완전 이진 트리 구조이며, 제일 큰 수나, 제일 작은 수를 빠르게 뽑아낼 수 있도록 하는 자료구조다. 최대힙은 트리의 노드 중 최댓값이 루트 노드에 존재하며, 최소힙은 트리의 노드 중 최솟값이 루트 노드에 존재한다. 힙정렬은 최대힙과 최소힙으로 모두 구현 가능하지만, 본 포스팅은 최대힙으로 진행한다. 완전 이진트리는 위와 같이 배열로 표현할 수 있다. 혹은 배열을 위와 같은 완전 이진 트리로..

특징 1. 분할 정복 알고리즘 2. 동일한 원소 존재시, 원래의 순서를 보존하지 않는 불안정 정렬 3. 일반적으로 최고, 평균 시간 복잡도O(N * logN), 최악 O(N^2) 4. 추가 버퍼가 필요하지 않으므로 공간 복잡도 O(1) 알고리즘 1. 버퍼의 요소 중 하나를 피벗(pivot)으로 지정 보통 맨 왼쪽, 중앙, 맨 오른쪽으로 지정하고, 본 포스팅은 피벗을 맨 왼쪽으로 함 2. 피벗보다 작은 값을 피벗의 왼쪽으로 이동, 피벗보다 큰 값을 피벗의 오른쪽으로 이동 3. 피벗을 기준으로 왼쪽 버퍼와 오른쪽 버퍼를 나누어 각 재귀 함수 호출 구현에서 중요한 점은 퀵 정렬은 추가 버퍼를 사용하지 않는 In-place sort라는 것이다. 따라서 2번 과정에서 새로운 버퍼를 이용하지 않고, 한 버퍼에서 s..

# 합병 정렬 특징 1. 분할 정복 알고리즘 2. 동일한 원소 존재시, 원래의 순서를 보존하는 안정 정렬 3. 일반적으로 최고, 최악, 평균 시간 복잡도 O(N * logN) 4. 임시 버퍼의 필요로 공간 복잡도 O(N) 알고리즘 1. 입력 버퍼를 절반씩 분할하여 나눈 두 버퍼에 대해 각 재귀함수를 호출 2. 계속 나누면서 들어가다가, 버퍼의 크기가 1일 때 중단점을 걸어 반환 3. 재귀함수를 나오면서 두 버퍼의 첫 요소부터 비교하여 작은 요소부터 임시 버퍼에 복사 (복사한 요소는 더이상 비교 대상이 아니며, 해당 버퍼의 index는 1 증가) 4. 복사한 구간의 임시 버퍼를 입력 버퍼에 복사 구현 및 상세 설명 #include void sort(std::vector& buf) { std::vector ..

유닉스 계열 운영체제에서 파일은 연속된 n개의 바이트다. 네트워크, 디스크, 터미널 같은 모든 I/O 디바이스들은 파일로 모델링되며, 모든 입력과 출력은 해당 파일을 읽거나 쓰는 형식으로 수행된다. 파일 열기 #include // mode_t type #include // mode masks #include int open(const char *pathname, int flags); int open(const char *pathname, int flags, mode_t mode); 응용 프로세스는 해당 파일을 여는 것을 커널에 요청한다. 성공시 커널은 파일 디스크립터를 반환하고, 실패시 -1을 반환한다. 이후 응용 프로세스는 해당 파일 디스크립터(이하 fd) 를 이용해 해당 파일에 접근할 수 있다. 파일..

I/O가 성능에 미치는 영향 I/O란 데이터 입출력을 일컫는 말이다. 네트워크 전송, 콘솔 출력, 파일 입출력 등을 모두 포함한다. 함수 실행과 같이 CPU를 사용하는 작업으로 인한 blocking은 개발자가 할 수 있는게 별로 없지만, I/O로 인한 blocking은 CPU를 긴 시간 idle하게 두기 때문에 다른 작업을 할 수 있음에도 오랫동안 할 수 없어 매우 비효율적이다. I/O에서 발생하는 시간은 CPU를 사용하는 시간과 대기 시간 중에 대기 시간에 속하기 때문에 I/O가 많아진다는 것은 CPU가 아무것도 하지 못하고 대기하는 시간이 길어진다는 의미고, 프로세스의 처리 속도가 같이 느려진다. Blocking I/O I/O 작업이 진행되는 동안 유저 프로세스가 자신의 작업을 중단한 채, I/O가 ..

개념 물리적으로 연결된 네트워크상에서의 데이터 송수신에 사용할 수 있는 소프트웨어적 장치다. (네트워크 망의 연결에 사용되는 도구, 더 나아가서 네트워크를 통한 두 컴퓨터의 연결) 커널에 내부 버퍼를 가지고 있고, 꽉 차면 더이상 전송과 수신을 하지 않으므로 데이터 손실이 없다. 리눅스는 소켓 조작을 파일 조작과 동일하게 간주한다. 즉, 소켓을 파일의 일종으로 구분한다. 네트워크의 연결에는 TCP와 UDP가 나뉘지만, 해당 포스팅에서는 TCP를 다룬다. 함수 서버 측에서의 소켓과 클라이언트 측에서의 소켓은 사용법이 다르다. 서버 측 #include int socket(int domain, int type, int protocol); // 소켓 생성 int bind(int sockfd, struct soc..