데이터를 만드는 쪽과 쓰는 쪽이 버퍼를 사이에 두고 협력합니다. 버퍼 칸 수가 정해져 있어서 bounded buffer problem이라고 부릅니다.여기서 지켜야 할 것이 세 가지입니다.생산자는 버퍼가 꽉 차면 기다려야 합니다소비자는 버퍼가 비면 기다려야 합니다둘이 같

정렬된 리스트에서는 이진 탐색으로 O(log n)에 찾을 수 있습니다. 문제는 삽입입니다. 중간에 값을 끼워 넣으려면 뒤를 전부 밀어야 해서 O(n)이 듭니다.연결 리스트는 반대입니다. 자리만 알면 삽입은 O(1)인데, 중간으로 건너뛸 수 없어 탐색이 O(n)입니다.이

트리 자체는 자식 수에 제한이 없습니다. 그런데 자식이 셋, 넷이 되면 삽입과 삭제에서 따져야 할 경우가 급격히 늘어납니다. 어느 자리에 넣을지, 지운 뒤 남은 자식들을 어떻게 재배치할지가 모두 분기가 됩니다.자식을 둘로 묶어 두면 "왼쪽 아니면 오른쪽" 두 경우만 남

송신 측은 congestion window(혼잡 윈도우, cwnd)라는 변수를 하나 둡니다. 확인받지 못한 채 네트워크에 떠 있어도 되는 바이트 수입니다. 전송 속도는 대략 다음과 같습니다.cwnd만큼 보내고 한 바퀴 돌아오기를 기다리므로, RTT당 cwnd만큼 나가는

컴퓨터에서 데이터를 고치는 일은 한 번에 끝나지 않습니다. 저장소에서 값을 읽어오고, 연산하고, 다시 써 넣는 세 단계입니다. count++ 한 줄도 기계 수준에서는 세 동작입니다.문제는 이 세 단계 사이에 CPU를 빼앗길 수 있다는 점입니다.공유 변수 count가 1

작업 스케줄러는 대기 중인 작업 중 우선순위가 가장 높은 것을 꺼내 실행하고, 그 사이에도 새 작업이 계속 들어옵니다. 필요한 연산은 "가장 큰 값 꺼내기"와 "새 값 넣기" 둘뿐입니다.리스트로 처리하면 한쪽이 반드시 느립니다. 정렬해 두면 최댓값 꺼내기는 빠르지만 삽

폴더 안에 폴더가 있고 그 안에 파일이 있는 파일 시스템, 부서 아래 팀이 있는 조직도, 태그 안에 태그가 들어가는 HTML 문서는 모두 포함 관계가 겹겹이 쌓인 구조입니다. 이런 관계를 한 줄짜리 리스트에 담으면 "누가 누구 밑에 있는지"를 따로 기록해야 합니다.트리

TCP에서 "연결"은 회선을 잡아두는 것이 아닙니다. 인터넷은 packet switching이고 코어는 아무 자리도 예약해주지 않습니다. 연결은 오직 양 끝 호스트의 메모리에만 존재합니다.연결을 연다는 것은 구체적으로 다음을 맞추는 일입니다.양쪽의 초기 sequence

지금까지는 Ready 큐가 하나라고 보고 거기에 알고리즘 하나를 적용했습니다. 그런데 큐가 하나면 모든 프로세스가 같은 규칙을 적용받습니다. 사용자 입력을 기다리는 프로그램과 밤새 돌리는 계산 작업이 같은 줄에 서는 셈입니다.multilevel queue는 Ready

충돌이 나면 그 주위에서 빈칸을 찾아 넣는 방식을 open addressing이라고 합니다. 빈칸을 찾아가는 규칙에 따라 linear probing, quadratic probing, double hashing으로 나뉩니다.가장 단순한 것은 linear probing입

학번으로 학생을 찾는 것처럼 키와 값을 짝지어 저장하는 자료형을 딕셔너리라고 합니다. 이를 리스트나 연결 리스트에 들어온 순서대로 쌓으면 구조는 단순합니다.문제는 탐색입니다. 키 33을 찾으려면 앞에서부터 하나씩 비교해야 해서 O(n)입니다. 삭제도 먼저 찾아야 하므로

point-to-point: 송신자 하나와 수신자 하나. UDP처럼 여러 상대에게 뿌리는 구조가 아닙니다.full duplex(전이중): 한 연결에서 양방향으로 동시에 데이터가 흐릅니다. 그래서 양쪽 모두 자기 sequence number를 따로 관리합니다.connec

프로그램은 CPU만 쓰지도, I/O만 하지도 않습니다. CPU를 쓰는 구간(CPU burst)과 I/O를 기다리는 구간(I/O burst)이 번갈아 나옵니다.CPU burst 시간의 분포를 보면 짧은 것이 아주 많고 긴 것이 드뭅니다. 이 분포는 프로그램의 성격이 갈리

단방향은 링크가 앞에서 뒤로만 있습니다. 그래서 노드 x를 지우려면 x가 아니라 "x를 가리키는 노드"가 필요합니다. x만으로는 아무것도 못 합니다.해결책은 단순합니다. 뒤로 가는 링크를 하나 더 두면 됩니다. 노드는 키 하나와 링크 두 개, prev와 next를 가집

관계 DBMS에는 엔티티 타입과 관계 타입의 구분이 없습니다. 릴레이션만 있습니다. 그래서 개념적 스키마를 논리적 스키마로 옮기는 단계가 필요하고, 이 과정을 사상(mapping)이라고 합니다.눈대중으로 옮기면 다치 애트리뷰트가 콤마로 뭉친 열이 되거나, M:N 관계의

rdt 3.0은 정확했지만 느렸습니다. 패킷 하나를 보내고 ACK가 올 때까지 손 놓고 기다리기 때문입니다. RTT가 100ms인 회선에서 이렇게 하면 링크 용량이 아무리 커도 대부분의 시간을 대기에 씁니다. 이번에는 그 낭비를 없애면서도 신뢰성을 유지하는 두 가지 방

운영체제가 프로세스를 하나씩 직접 만들어 주지 않습니다. 부모 프로세스(parent process)가 복제해서 자식 프로세스(child process)를 만듭니다. 자식이 또 자식을 만들 수 있으므로 시스템의 프로세스들은 자연스럽게 트리 계층 구조를 이룹니다.자식이 실

배열은 중간에 원소를 끼워 넣거나 빼면 뒤쪽을 전부 한 칸씩 밀거나 당겨야 해서 O(n)이 듭니다. 원소를 빈틈없이 붙여 두기로 했기 때문에 생기는 비용입니다.또 크기 n짜리 배열을 만들려면 메모리에 n칸이 연속으로 비어 있어야 합니다. 전체 여유 공간이 충분해도 연속

하나의 엔티티는 연관된 애트리뷰트들의 집합으로 설명됩니다. 이때 애트리뷰트의 성격을 구분하지 않으면 전화번호 칸에 010-1234-5678, 02-123-4567처럼 콤마로 여러 값을 밀어 넣게 되고, 평점을 성적과 별개로 저장했다가 두 값이 어긋나는 일이 생깁니다.세

network 계층은 best effort입니다. 큐가 넘치면 패킷을 버리고, 전송 중에는 비트가 뒤집힐 수도 있습니다. 그런데 애플리케이션은 TCP 소켓에 쓴 바이트가 그대로, 빠짐없이, 순서대로 도착하길 기대합니다.reliable data transfer proto