- Hash
- Radix Sort
- OSI 7 계층
- System Call
- DB - Transaction
Hash
- 연관 배열 구조로 키와 값이 1:1로 매핑되어 저장한다.
- 충돌이 일어나지 않으면, 삽입, 검색, 삭제 모두 O(1) 시간 복잡도를 지닌다.
- 충돌을 다루기 위해, open addressing 과 separate chaining 방식이 있다.
- 조금 더 효율적인 것은 seperate chaining 방식을 삽입 시에 head에 삽입하는 방법으로 구현하는것이다.
- 해시 함수와 버켓 크기에 따라 성능이 크게 좌우된다.
- 단접으로는 순서가 있는 배열에 어울리지 않고, 공간 효율성이 떨어진다.
Radix Sort
- 기수 정렬은 정수형 정렬에 특화된 정렬로 시간복잡도는 O(dn) 이다.
d = 가장 큰 수의 자리 수 이다. - 각 수들의 1의 자리 수 부터 10^(d-1) 자리 수까지 순서대로 버켓에 담아가며 정렬한다.(LSD)
(큰 자리 수부터 정렬하면 MSD) - 버켓 등 추가적인 메모리가 필요하다.
- 안정 정렬이다.
OSI 7 계층
- 1계층 - 물리 계층
- 전기적 신호를 비트로 변환 ( 리피터 ) -> 노드간 물리적 연결 ( 허브 )
- 사용 유닛 : bits
- 사용 프로토콜 : 이더넷, 모뎀
- 2계층 - 데이터 링크 계층
- 오류와 흐름을 제어(제거) 하여 ( 브릿지 ) 신뢰성을 확보.
- 신호를 MAC 주소로 변환 후 목적지로 전송 ( NIC, 스위치 )
- 사용 유닛 : frame
- 사용 프로토콜 : MAC, PPP, 무선랜
- 3계층 - 네트워크 계층
- 다중 네트워크 링크에서 패킷을 목적지로 전달하는 것을 책임짐.
- 데이터 전달의 경로를 설정함 ( 라우터 + 라우팅 프로토콜 )
- 사용 유닛 : packet
- 사용 프로토콜 : IP, ICMP, IGMP, RIP
- 4계층 - 전송 계층
- 메시지 ( 데이터 )를 전송하는데에 필요한 발신지와 목적지 간 여러 제어와 에러 대응하여 신뢰성 확보
- 프로세스간 연결
- 사용 유닛 : segment
- 사용 프로토콜 : TCP, UDP, ARP, RTP, SCTP
- 5계층 - 세션 계층
- 포트, 통신 장치간 상호 연결 및 확인 ( 논리적 연결 )
- 동기화
- 사용 유닛 : data
- 사용 프로토콜 : SSH, TLS
- 6계층 - 표현 계층
- 데이터 암호화 및 복호화를 통해 해석, 변형, 가공
- 7계층 - 응용 계층
- data를 사용자가 쉽게 이용할 수 있도록 사용자 친화적인 환경 제공
- 사용 프로토콜 : HTTP, FTP, DHCP, SMTP, DNS
System Call
OS는 크게 커널모드와 사용자모드로 나뉘어 집니다.
- 커널모드 : 모든 시스템 메모리 접근 가능. 모든 CPU명령 실행 가능
- 사용자모드 : 사용자 애플리케이션 실행. 하드웨어 직접 접근 불가. System call 호출시 일시적으로 커널모드로 전환.
커널영역의 기능을 사용자모드가 접근하게 도와주는 기능을 System call이라고 부릅니다..
System call을 사용하는 이유?
가장 큰 이유는 유저 애플리케이션(ex. 우리가 흔히 개발하여 실행하는 자바 애플리케이션)이 운영체제의 치명적인 데이터를 수정/삭제하는 권한을 막기 위해서 입니다. 직접적인 하드웨어 요청이나 기타 시스템요청은 OS가 제공하는 System call을 통해 호출하도록 제공해줍니다.
만약 유저 애플리케이션이 System call을 호출하여 사용하면, 해당 애플리케이션은 커널모드로 잠시 전환되는 작업을 거치게 됩니다.
System call 유형
프로그래밍 언어에서 지원하지 않고 운영체제를 통해 사용해야하는 기능의 종류는 아래와 같습니다.
- 프로세스 제어
- 파일 조작
- 장치 관리
- 정보 유지
- 통신
인터럽트, 트랩, 시스템 콜 차이점 알아두기 - blog.daum.net/ggmgsm/75
DB - Transaction
트렌잭션이란?
데이터베이스의 상태를 변화시키기 위해 수행하는 작업 단위
트랜잭션 특징
-
원자성(Atomicity)
트랜잭션이 DB에 모두 반영되거나, 혹은 전혀 반영되지 않아야 된다.
-
일관성(Consistency)
트랜잭션의 작업 처리 결과는 항상 일관성 있어야 한다.
-
독립성(Isolation)
둘 이상의 트랜잭션이 동시에 병행 실행되고 있을 때, 어떤 트랜잭션도 다른 트랜잭션 연산에 끼어들 수 없다.
-
지속성(Durability)
트랜잭션이 성공적으로 완료되었으면, 결과는 영구적으로 반영되어야 한다.
Commit
하나의 트랜잭션이 성공적으로 끝났고, DB가 일관성있는 상태일 때 이를 알려주기 위해 사용하는 연산
Rollback
하나의 트랜잭션 처리가 비정상적으로 종료되어 트랜잭션 원자성이 깨진 경우
transaction이 정상적으로 종료되지 않았을 때, last consistent state (예) Transaction의 시작 상태) 로 roll back 할 수 있음.
DB - Transaction Isolation - (it-license.tistory.com/25)
데이터베이스의 읽기 이상 현상 (Read Phenomena)
데이터베이스에서 Isolation level 에 따라 발생할 수 있는 이상현상들을 정리해보면..
| 유형 | 내용 | 해결방안 |
| Dirty Read | 트랜잭션 T1 에서 A = 5 로 Update 하고 아직 commit 를 않았는데 다른 트랜잭션 T2가 이 A 값을 읽을 수 있도록 허용하는 경우 Dirty Read가 발생 할수 있다. 즉. T1이 Update를 수행한 후 아직 commit 도 안했는데 다른 트랜잭션 T2가 A 를 select 했을 때 5 가 나올 경우 , T1 트랜잭션이 rollback을 했을 경우 결국 A 값은 5가 아님에도 T2 는 5로 잘못 읽는 (Dirty Read) 현상이 발생한다 | 공유 Lock 을 걸어서 T1이 A 에 접근하고 있는 동안 다른 트랜잭션이 접근하지 못하게 함. |
| Non Repeatable Read | T1 트랜잭션이 같은 쿼리를 두번 실행했는데 그 결과값이 다른 경우, 즉 T1 이 select 를 두번 하는 사이에 T2 트랜잭션이 update 나 delete 를 한 경우 |
트랜잭션 완료 시까지 수정/삭제 제한 |
| Phantom Read | T1 트랜잭션이 같은 쿼리를 두번 수행 시 첫번째 실행시에 없던 레코드가 두번째 실행시에 튀어 나오는 경우 |
T1 트랜잭션이 읽은 데이터는 T2 트랜잭션에서 갱 신, 삭제하지 못할 뿐 아니라 중간에 새로운 레코드 삽입(Insert)까지 불허 |
데이터베이스의 Isolation Level (고립수준) 유형
| 유형 | 내용 | 읽기 이상 현상 |
| Read Uncommitted | 트랜잭션 T1이 아직 commit 하지 않은 데이터를 다른 트랜잭션 T2가 Read 하는 것을 허용 | Dirty Read 오라클은 미지원 |
| Read Committed | 트랜잭션 T1이 commit 을 한 데이터만 다른 트랜잭션 T2가 Read 하는 것을 허용 | Dirty Read는 막을 수 있지만 Non Repeatable Read와 Phantom Read 는 막을 수없음 (대부분의 DBMS가 채택) |
| Repeatable Read | 선택 트랜잭션 T1이 읽은 데이터는 T1이 종료될 때 까지는 다른 트랜잭션이 수정/삭제 (Update/Delete) 를 허용하지 않음 단 삽입(Insert) 은 허용 함. |
Dirty Read와 Non Repeatable Read까지는 발생을 막을수 있으나 Phantom Read 는 막을 수없음 |
| Serializable | 선행 트랜잭션 T1이 읽은 데이터는 T이 종료될 때 까지 다른 트랜잭션이 수정/삭제는 물론 삽입 까지 허용하지 않음 | Dirty Read와 Non Repeatable Read와 Phantom Read 까지 모두 막을 수 있음 (완벽하지만 실제 현실적으로는 불가능에 가깝다) |
Isolation Level 과 읽기 이상 현상의 관계를 정리하면 다음과 같다
| Isolation Level | Dirty Read | Non Repeatable Read | Phantom Read |
| Read Uncommitted | 가능 | 가능 | 가능 |
| Read Committed | 불가능 | 가능 | 가능 |
| Repeatable Read | 불가능 | 불가능 | 가능 |
| Serializable | 불가능 | 불가능 | 불가능 |
데이터베이스의 Isolation Level 과 동시성과의 상관관계
위에서 설명한 4가지 Isolation Level 중에서 Serializable 레벨이 가장 읽기 이상 현상을 모두 방어할 수 있는 방법이기
는 하지만 대신 그만큼 트랜잭션들이 동시에 병렬적으로 실행되지 못하고 하나씩 하나씩 실행순서대로 실행이
되기 때문에 대기시간이 늘어나고 전체적으로 performance 가 떨어 질수 밖에 없다.
반대로 Read Uncommitted 는 그냥 트랜잭션 의 수행을 동시에 수행 가능하기 때문에 동시성이 높아진다.
이렇게 Isolaton Level 과 동시성(Concurrent) 은 서로 Trade-off 관계이다.
