CS

멀티스레드

멀티 스레드 일반적으로 하나의 프로세스는 하나의 스레드를 가지고 작업을 수행하게 된다. 멀티 스레드란 하나의 프로세스 내에서 둘 이상의 스레드가 동시에 작업을 수행하는 것을 의미한다. 멀티 스레딩의 장점 멀티 스레드는 각 스레드가 자신이 속한 프로세스의 메모리를 공유하므로, 시스템 자원의 낭비가 적다. 특히 스레드의 문맥 교환은 프로세스의 문맥 교환과 달리 캐시 메모리를 비울 필요가 없기 때문에 더 빠르다. 따라서 시스템의 처리율이 향상되고 자원 소모가 줄어들어 자연스럽게 프로그램의 응답 시간이 단축된다. 또한, 하나의 스레드가 작업을 할 때 다른 스레드가 별도의 작업을 할 수 있어 사용자와의 응답성도 좋아진다. 이러한 장점 때문에 여러 프로세스로 할 수 있는 작업들을 하나의 프로세스에서 스레드로 나눠 ..

프로세스 vs 스레드

프로세스 프로세스(Process)는 컴퓨터에서 실행되고 있는 프로그램(A program in execution)을 말한다. 운영체제로부터 주소 공간, 파일, 메모리 등을 할당받으며 이것들을 총칭하여 프로세스라고 한다. 디스크와 같은 보조기억 장치에 단순히 저장되어 있는 프로그램은 in execution이 아니기 때문에 프로세스가 아니다. 디스크에 실행파일 형태로 존재하던 프로그램이 메모리에 올라가서 실행되기 시작해야 비로소 생명력을 갖는 프로세스가 된다. 프로세스는 CPU를 획득해 자신의 코드를 수행하기도 하고 때로는 CPU를 반환하고 입출력 작업을 수행하기도 한다. CPU 스케줄링의 대상이 되는 작업(task)이라는 용어와 같은 의미로 쓰인다. 프로세스 제어블록(PCB) 프로세스 제어블록(Process..

www.google.com에 접속하면 일어나는 일

🔎 www.google.com에 접속해보자 기술 면접 단골 질문인 www.google.com에 접속하는 과정을 생각해보자. 1. 주소창에 www.google.com을 입력하자. 우리가 젤 먼저 해야할 것은 내가 사용하는 브라우저 주소창에 www.google.com을 입력하는 것이다. 2. 브라우저는 캐시에 DNS 레코드가 있는지 확인한 후, www.google.com의 IP 주소를 찾는다. DNS(Domain Name System)는 웹 사이트(URL)의 이름과 링크되는 특정 IP 주소를 유지하는 데이터베이스이다. 사람마다 고유한 주민등록번호가 있듯이, 인터넷의 모든 URL에는 고유한 IP 주소가 할당되어 있다. www.google.com의 IP 주소는 209.85.227.104이다. DNS의 주된 목적..

DNS Round Robin

DNS Round Robin DNS roudn robin에 대해 알아보기 전에 먼저 로드 밸런싱과 round robin에 대해 알아보자. 로드 밸런싱 클라이언트가 인터넷을 통해 서버에 접속하고자 할 때, 많은 양의 요청이 한 번에 서버에 들어오게 되면 과부하가 생길 수 있다. 이를 방지하기 위해 트래픽을 관리해야 하는데 이 방법에는 크게 두 가지가 있다. 서버 성능 향상(Scale Up) 트래픽 분산(Scale Out) 어떤 동네에 아파트 한 채가 있고, 더 많은 가구를 수용하고 싶을 때 scale up은 기존의 아파트에 몇 층을 더 쌓는 것이고 scale out은 아파트를 새로 짓는 것이라고 생각하면 된다. 서버 성능 향상은 말 그대로 서버 자체의 성능을 향상시키는 것이다. 더 비싸고 좋은 서버를 쓰면..

DNS

DNS DNS(Domain Name System)은 도메인 이름과 IP 주소를 매핑해주는 시스템이다. 주민등록번호, 핸드폰 번호와 같이 사람을 다양한 방식으로 식별할 수 있는 것처럼, 호스트에도 다양한 식별자가 있다. 호스트의 식별자에는 크게 도메인 네임과 IP 주소가 있다. 도메인 네임은 우리가 흔히 보는 www.google.com과 같은 주소이고 IP 주소는 111.111.111.111과 같이 4바이트로 구성된 주소이다. 사람의 입장에서는 IP 주소보다 도메인 네임이 더 기억하기 쉽지만, 라우터 입장에서는 그 반대이다. 도메인 네임은 인터넷에서의 해당 호스트 위치에 대한 정보를 거의 제공하지 못하기 때문에 IP 주소를 사용하고, 둘의 입장을 절충하기 위한 해결사가 DNS인 것이다. DNS Server..

Hash Table

Hash Table 해시 테이블은 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블이다. 따라서 작은 크기의 캐시 메모리로도 프로세스를 관리하도록 할 수 있다. 삽입, 삭제, 탐색 시 평균적으로 O(1)의 시간 복잡도를 가지고 unordered_map으로 구현한다. 해시 테이블에 데이터를 삽입하기 위해서는 저장하고자 하는 자료와 연관된 키를 생성해야 하는데 이 키를 생성하기 위한 함수를 해시 함수라고 한다. 좋은 해시 함수를 사용하면 해시 테이블에 데이터가 고르게 분포되고, 이는 충돌이 발생할 가능성이 낮다는 뜻이다. 따라서 좋은 해시 함수는 충돌을 덜 일으켜야 하고 계산이 쉬워야 한다. Hash Collision 서로 다른 두 개의 값 $i_{1}$과 $i_{2}$가 해시 테이블의 같은..

Red-Black Tree(RBT)

Red-Black Tree 레드 블랙 트리는 균형 이진 탐색 트리로 탐색, 삽입, 삭제 모두 시간 복잡도가 logN이다. 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하고, 추가된 비트는 삽입 또는 삭제의 과정에서 트리가 균형을 유지하도록 하는 데 사용된다. 대표적으로 C++ STL의 set, multiset, map, multimap 이 레드 블랙 트리를 이용하여 구현되어있다. Why Red-Black Tree? 왜 레드 블랙 트리를 사용하는 걸까? 이 이유에 대해 알기 위해서는 BST(이진 탐색 트리)의 단점부터 파악해야 한다. BST란, 노드의 오른쪽 하위 트리에는 노드 값보다 큰 값이 있는 노드만 포함되고, 왼쪽 하위 트리에는 노드 값보다 작은 값이 들어 있는 트리를 말한다. ..

Heap(Max Heap, Min Heap)

Heap 영단어 Heap은 '무엇인가를 차곡차곡 쌓아 올린 더미'라는 뜻을 가지고 있다. 아래 그림에서도 볼 수 있듯이, 맨 아래부터 데이터를 차곡차곡 쌓아둔 모양이다. Heap은 완전 이진트리로 모든 노드가 연속적으로 존재하기 때문에 연결 리스트보다는 배열로 구현하는 것이 효율적이다. 또한 heap은 모든 노드에 저장된 값이 자식 노드에 저장된 값보다 크거나 같은 자료구조이다. 즉, 루트 노드에 저장된 값이 가장 커야 한다. 이처럼 루트 노드로 올라갈수록 저장된 값이 커지는 완전 이진트리를 최대 힙(Max Heap)이라고 한다. 이와 반대로, 루트 노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리인 최소 힙(Min Heap)도 존재한다. 최소 힙은 특히 shortest job first를 구현할때..