공부기록

red-black tree? 가장 유명하고 많이 사용되는 균형이진 트리이다. 즉 모든 연산의 시간복잡도가 _O(log N)_임을 보장한다. 노드가 red, black 색상을 가지며 아무것도 없는 nil을 leaf 노드라고 생각한다. red-black tree는 다음 5가지 조건을 만족해야 한다. 모든 노드는 red, black의 색을 가진다. root 노드는 black이다. leaf 노드는 black이어야 한다. red 노드는 두 개의 자식을 가지며, red 노드의 child 노드는 색이 모두 black이어야 한다. black 노드의 자식은 어떠한 색을 가지든 상관이 없다. *tree의 전체 depth가 log N 이기 위해서, 각 노드에서 leaf 노드로 가는 경로들 중에 있는 블랙노드의 개수는 항상 ..

Web Caching 웹 캐시 (proxy server)는 원래 웹 서버 대신에 HTTP 요청을 처리해 줄 수 있는 요소이다. 웹 캐시는 자신의 저장소에 요청 받게될 자원들의 복사본을 저장해 뒀다가 요청이 오면 대신 응답하게 된다. 먼저 다음은 웹 캐시가 중간에 있을 때, http://www.someschool.edu/campus.gif객체에 대한 요청을 처리하는 과정이다. 브라우저가 웹 캐시와 TCP 통신을 성립하고, 해당 객체에 대한 요청을 보낸다. 웹 캐시는 자신에게 해당 객체가 있으면 HTTP 응답 메세지와 함께 보내게 된다. 웹 캐시에 해당 객체가 없다면, 웹 캐시는 본래의 서버에 TCP 연결을 한 뒤 해당 객체에 대한 HTTP 요청 메세지를 보내게 된다. 그렇게 하여 본래의 서버로 부터의 HT..

OS 질문 프로세스의 개념 프로세스란? 프로세스의 구조 PCB? PCB의 역할? context switching? 프로세스 상태 9-state diagram 보류 상태가 무엇인지? 어떤 현상에 의해 보류 상태가 생기는지? 스와핑의 정의? 스와핑이 필요한 이유? 프로세스의 표현 프로세스 테이블 PCB 정의 역할 프로세스 이미지 정의 구조 프로세스 속성 프로세스 제어 수행모드와 사용이유 프로세스 생성과정 프로세스 교환이유 모드전환 과정 프로세스 교환 vs 모드 전환 프로세스 교환 과정 스케줄링의 개념 스케줄링? 스케줄러? 스케줄러의 목표? 처리기 스케줄러의 유형 처리기 스케줄러의 목적 스케줄링 기법이 중요한 이유? 처리기 스케줄러 유형과 설명 단기 스케줄러 호출 시점? 스케줄링 알고리즘 preemptive ..

데이터베이스 DB의 개요 데이터베이스가 제공하는 기능 데이터베이스의 이점 데이터 추상화와 데이터 모델 스키마와 인스턴스 데이터 추상화 레벨 데이터 독립성 트랜잭션 관리 관계형 데이터 모델 관계형 데이터베이스의 표현 방법 속성이 원자값? 관계 스키마, 관계 인스턴스 key 참조무결성 관계 대수 종류, 문법 추가 관계 대수 종류, 문법 SQL 기능적 관념의 분류 각 분류별로 하는 기능과 어떤 예약어가 있는지? 표현되는 방식에서의 분류 DDL DDL의 기능 Drop vs Delete DML DML의 기능 SQL Execution Model? View view? view 정의하는 방법 view가 항상 최신 데이터를 보유하는 이유? view가 다른 view를 사용할 수 있는지? view를 통한 질의 과정 view..

네트워크 OSI-7-Layer OSI 7 계층의 종류와 특징, 그리고 데이터 이름 Application Layer application layer의 특징 protocol? HTTP의 정의 HTTP의 특징 HTTP의 장점 HTTP Method Cookie REST DNS의 정의와 제공하는 서비스 DNS DB 분산된 이유 URL을 쳐서 웹사이트 서핑하는 과정 Transport Layer Transport 계층의 특징 Multiplexing & Demultiplexing UDP의 특징 UDP의 패킷오류발견 기법 RDT X.X 버전별 각각의 특징 Pipleline Protocold의 특징과 종류 TCP의 특징 TCP의 RDT TCP의 Connection Management TCP의 Congestion Contr..

메모리 관리를 위한 OS SW 가상 메모리를 위한 운영체제 정책에는 다음과 같은 것들이 있다. 반입 정책 배치 정책 교체 정책 반입정책 (Fetch Policy) 언제 페이지를 주기억장치로 들여올지 결정 요구페이징 (demand paging) 요구페이징에서 페이지가 주기억장치로 반입되는 시점은 페이지의 특정 부분이 참조될 때이다. 선페이징은 유효성이 입증되지 못함 배치정책 (Placement Policy) 배치정책은 블록이 주기억장치의 어디에 위치할 지를 결정 페이징을 사용하는 시스템의 경우 일반적으로 문제가 되지 않음 교체정책 (Replacement Policy) 새로운 페이지를 반입하기 위해 주기억장치의 어떤 페이지를 선택하여 교체할 지를 결정 어떤페이지를 선택할지 결정하는 알고리즘들이 존재 OPT,..

교착상태 발견 예방 전략 상당히 보수적인 방법 교착상태가 발생하지 않도록 하기 위해 자원 접근에 대한 제한과 프로세스의 수행 제한 발견 전략 좀 더 낙관적인 방법 자원 접근에 대한 제한이나 프로세스의 행위에 제한 없음 즉 자원 할당이 가능한 상황이면 항상 할당함 단 주기적으로 시스템에 환형 대기 조건이 발생했는지 검사하고 발생하면 해결 교착상태 발견 알고리즘 자원할당이 요구될 때마다 수행 vs 주기적인 수행 자원 할당이 요구될 때마다 매번 수행하면 빨리 교착 상태 발견 가능하고 알고리즘이 간단 처리 비용이 더 많이 들 수 도 있다. 알고리즘 할당 행렬 A, 가용 벡터 V, 요청 행렬 Q 사용 Qij는 프로세스 i에 의해 요청된 자원 j의 개수 교착상태가 아닌 프로세스들을 찾아 표시 (mark) 초기에는 ..

Basic Concepts Basic Concepts 인덱스는 원하는 데이터에 빠르게 접근하기 위해 사용된다. 인덱스 파일은 형태의 기록으로 구성된다. search-key는 레코드를 찾기위해 사용되는 속성들의 집합니다. 인덱스 파일은 보통 원래 파일보다 훨씬 작다. 두 종류의 인덱스가 있다. 정렬 색인 (ordered index) : 색인 레코드가 탐색키 기준으로 정렬되어 있다. 해쉬 색인 (hash index) : 색인 레코드가 탐색키 기준으로 정렬되어 있지 않다. Index Evaluation Metrics 색인을 평가하는 요소를 말하며 이중 색인이 제공하는 질의 타입이 중요하다. 질의타입에는 다음 2가지의 경우가 있다. 일치 질의 형태 (Exact Matc..