개구리의 개발 블로그 개구리의 개발 블로그

Red-Black 노드는 모든 경로의 Black 노드의 개수를 동일하게 유지한다. Red-Black Tree는 일반적인 이진 탐색 트리와 다르게 Black 노드의 개수를 통해 균형을 유지한다. Tree에 새로운 노드를 삽입하는 경우를 생각해보자. Black 노드를 삽입이 불가능한 것은 아니다. 중요한 것은 Red-Black 트리의 조건에 맞게 모든 경로에 대하여 동일한 Black Depth를 갖도록 균형을 맞춰주는 것이다. Black 노드를 삽입하면, 언제나 균형이 깨진다. 새로운 노드가 추가되는 경로에만 Black 노드의 개수가 1개 증가하기 때문이다. 반면에 Red 노드를 삽입하는 경우에는 균형이 유지되는 경우가 존재한다. 리프 노드의 부모가 Black 노드인 경우에는 Red-Black 노드의 조건과..

자바는 Call by Value를 사용한다. 자바 코드와 함께 정리가 잘 된 글들이 많지만 아주 간단하고 쉽게 정리해보겠다. 1. Call by Value vs. Call by Reference 함수가 호출될 때, 메모리 공간에서는 임시의 공간이 생성된다. 함수가 종료되면 공간이 사라진다. (더 자세한 내용은 Garbage Collector를 공부해보면 된다.) 1. Call by Value 함수 호출 시 전달 되는 변수의 값을 복사하여 함수의 인자로 사용한다. 복사된 인자는 함수 내부에서 지역 변수로 사용된다. 2. Call by Reference 함수 호출 시 인자로 전달 되는 변수의 참조를 전달한다. 함수 내부에서 인자의 값이 변경되면, 참조된 변수들도 값이 바뀐다. JVM에서는 원시 타입은 Sta..

1. CPU 스케줄링 운영체제의 단기 스케줄러는 스케줄링 알고리즘을 이용해 어떤 프로세스에게 CPU를 할당할 지(디스패치) 결정한다. 프로세스의 실행은 CPU 실행과 I/O 대기의 사이클로 구성된다. CPU 버스트로 시작되어 I/O 버스트가 발생하고 다시 CPU 버스트가 발생, I/O 버스트 발생.. 마지막 CPU 버스트는 또 다른 I/O 버스트가 뒤따르며, 실행을 종료하기 위한 시스템 콜과 함께 끝난다. CPU를 많이 쓰는 프로세스(CPU bound job)와 I/O를 많이 쓰는 프로세스(I/O bound job)가 섞여 있기 때문에 CPU 스케줄링이 필요하다. CPU 스케줄링 알고리즘의 선택 기준은 다음과 같다. CPU 이용률 : CPU가 얼마나 바쁘게 일을 하는가 처리량 : 단위 시간 당 완료된 프..

MySQL Lock이라는 키워드로 구글링을 하면 너무 많은 종류가 있고 결론적으로 어떤 방식을 사용한다는 것인지 이해가 되지 않았다. 본 글은 Real MySQL 8.0 1권을 읽고 정리한 글이다. MySQL에서는 InnoDB에서 제공하는 잠금과 MySQL에서 제공하는 잠금 두 종류가 있다. 또 각각에서 제공하는 잠금에는 범위에 따라 여러 종류로 구분된다. 각 잠금들은 무엇이고 언제 사용되는 지 정리해보자. MySQL의 잠금 MySQL에서 사용되는 잠금은 크게 스토리지 엔진 레벨과 MySQL 엔진 레벨로 나눌 수 있다. MySQL 엔진 레벨의 잠금은 모든 스토리지 엔진에 영향을 미치고, 스토리지 엔진 레벨의 잠금은 다른 스토리지에는 영향을 미치지 않는다. MySQL 8.0부터는 InnoDB가 기본 스토리..

1. 링크 계층 기본적으로 링크 계층의 역할은 한 노드에서 인접한 노드로 데이터그램을 직접 이동시키는 것이다. 1.1 링크 계층의 서비스 프레임화 : 링크 계층 프로토콜은 네트워크 계층 데이터그램을 링크상으로 전송하기 전에 링크 계층 프레임으로 캡슐화한다. 링크 접속 : 링크 계층의 프로토콜인 MAC(Medium Access Control, 매체 접속 제어)프로토콜은 링크상으로 프레임을 전송하는 규칙에 대하여 명시한다. 점대점의 단순한 상황에서는 송신자는 링크가 사용되지 않을 때마다 프레임을 전송할 수 있다. 만약 여러 노드가 링크를 공유하는 경우 MAC 프로토콜을 통해 여러 노드의 프레임 전송을 조정해야 한다. 신뢰적 전달 : 일반적으로 광섬유, 동축케이블, 꼬임쌍선을 이용하는 링크 계층에서의 오류는 ..

[Network]신뢰적인 데이터 전송과 TCP UDP와 TCP의 가장 큰 차이는 TCP가 신뢰적인 데이터 전송을 기반으로 하는 프로토콜이라는 것이다. 이번 글에서는 신뢰적인 데이터 전송이란 무엇인 지 알아본 뒤 다음 글에서 본격적으로 TCP에 대 frog-in-well.tistory.com 지난 글에서는 신뢰적인 데이터 전송이 무엇인 지 알아보았다. 이번 글에서는 TCP에서 어떻게 신뢰적 데이터 전송이 이루어지는 지 알아보자. 1. TCP 1.1 TCP 연결 TCP는 애플리케이션 프로세스가 다른 프로세스로 메시지를 전달하기 전에 “핸드셰이크"를 하기 때문에 연결지향형 프로토콜이라고 한다. 세 방향 핸드셰이크를 통해 연결이 설정되면 두 애플리케이션 프로세스는 서로 데이터를 보낼 수 있다. 다시 설명하자면 ..

1. Deadlock이란? 프로세스들이 서로가 가진 자원을 기다리며 block된 상태이다. 1.1 자원이란? 하드웨어, 소프트웨어를 포함하는 개념 I/O, CPU, Memory, Semaphore 등 2. Deadlock 발생 조건 4가지 조건 모두 만족할 때 deadlock 발생한다. 다시 말해 한 가지 조건을 해제하여 deadlock을 방지한다. 1. Mutual Exclusion, 상호 배제 하나의 프로세스가 자원을 독점적으로 사용 2. No Preemption, 선점 불가 자원을 강제로 빼앗을 수 없음 3. Hold and Wait 일을 수행하기 전까지 현재 가진 자원을 내어 놓지 않음 4. Circular Wait, 환형 대기 자원을 기다리는 프로세스간에 사이클이 형성됨 3. Deadlock 처..

0. 들어가기 전에 네트워크 계층의 근본적 역할은 매우 단순하다. 송신 호스트에서 수신 호스트로 패킷을 전달한다. 네트워크 계층의 기능은 라우터에 패킷이 도착하면 적절한 출력 링크로 전달하는 포워딩과 적절한 경로를 찾는 라우팅이다. 전송 계층을 다루며 인터넷 네트워크 계층은 최선형 서비스를 제공한다고 말했다. 최선형 서비스는 패킷을 보내는 순서대로 수신됨을 보장할 수 없고, 목적지까의 전송 자체도 보장될 수 없다. 종단 시스템 간 지연 또한 보장되지 않는다. 이러한 이유로 TCP가 패킷의 유실과 손상에 대한 대처를 철저하게 하는 것이다. 1. 라우터의 구조 입력 포트 입력 링크의 물리 계층 기능을 수행한다. 입력 링크의 반대편에 있는 링크 계층과 상호 작용을 하는 링크 계층 기능을 수행한다. 포워딩 테이..