-
[Computer Arch.] False Sharing
멀티 코어 CPU에서 발생할 수 있는 문제다. 멀티 코어 CPU에서는 데이터를 word 단위로 읽어오는 대신 메모리 I/O 효율성을 위해서 cache line로 읽어오는데, 이때 문제가 생길 수 있다. 두개의 메모리 연산이 동일한 cache line에서…
-
[OS] Linux File System
Linux의 file system은 트리 구조로 구성된다. /dev/sda 와 같은 파티션의 구조는 아래와 같다. Super Block 파일 시스템 크기 파일 시스템 내 자유 블럭 수 파일 시스템 내 사용 가능한 자유 블럭 수 i-node…
-
[Compiler] GCC Compiler
GCC compiler는 가장 많이 사용되는 compiler 중 하나다. C language code가 실행파일까지 만들어지는 과정을 아래 그림처럼 확인 할 수 있다. 실제 gcc 컴파일러를 통해 중간에 수행되는 과정 전체를 보려면 아래 옵션을 통해 볼…
-
[OS] Linux 소개
1. UNIX 범용적으로 다용 사용자 방식의 시분할 운영체제의 시초다. UNIX는 AT&T Bell Lab에서 Dennis Ritche (C언어를 개발) 등 개발자들이 개발했다.초기 UNIX는 상업적으로 판매될 수 없어 source code와 함께 Berkeley Univ.에서 무상 제공하여 BSD…
-
[Algorithm] Cyclic Redundancy Check (CRC)
Check Sum의 문제는 data의 합이 변하지 않으면, 중간에 data들이 변하여도 error를 찾을 수 없는 문제가 있다. 따라서 이런 문제를 해결할 수 있는 방식이 CRC다. 위 그림은 3-bit CRC의 예시로, 보내는 sender쪽에서 data를 특정…
-
[Algorithm] Check Sum
Data를 전송 할 때 data의 무결성을 검증하기 위해 사용하는 기법이다. Parity bit은 단순히 1의 개수가 홀수인지, 짝수인지를 확인하는데 이 때 data가 짝수개가 변경되면 parity bit을 통해서 무결성을 검증하기 어렵다. Check Sum은 Sender 쪽에서…
-
[Algorithm] Parity Bit
데이터의 무결성을 확인하기 위한 방법 중 하나로 보내는 data의 1의 개수가 홀수인지 짝수인지 확인하여 받는 쪽에서도 동일한지 확인하는 방법이다. 예를 들면 ‘a’ ASCII data를 보낸다고 했을 때 0110_0001 (97)의 data가 전송 될 것이다.…
-
[Algorithm] Hamming Weight (Bit Count)
Data에서 1의 개수를 세는 알고리즘을 Hamming Weight라고 부른다. 여기엔 다양한 알고리즘이 존재한다. 1. Simple 위 방식의 시간복잡도는 O(n)을 가진다. 2. Hamming Weight: Level 1 위 코드는 wikipedia에 나와있는 코드를 32-bit에 맞춰서 변경해봤다. 만약…
-
[Algorithm] Find First Set (FFS) Bit
FFS는 데이터 중에 특정 bit가 1로 설정됐는지 찾는 알고리즘이다. 위 코드는 하위 비트부터 순차적으로 for loop을 돌면서 무식하게 찾는 방법이다. 만약 찾고자 하는 bit가 상위에 있다면 시간이 오래 걸릴 것이다. (시간 복잡도는 O(n))좀…
-
[Algorithm] Generic Swap and Sort
Generic Swap Swap 함수는 어디서든 많이 쓰는 함수 중 하나다. 그런데 type에 무관한 swap 함수가 필요할 수 있기 때문에 타입에 무관함 swap 함수를 소개한다.(C++에선 함수 overloading이 가능해서 동일한 함수 이름이여도 타입이 다르면 다르게…
