본문 바로가기
반응형

IT 이론239

FDMA, TDMA, CDMA, OFDM의 비교와 이해 무선통신은 "라디오 파" 라는 파동을 이용해서 이루어진다. 빛의 속도에다가 웬만한 고체도 통과 할 수 있기 때문에 아직까지는 장거리 무선통신에서 라디오파는 대체 할 만한 파동은 찾지 못했다. 두 사람이 전화 통화를 한다고 하면 주고 받는 대화가 라디오 파동을 통해서 전달 된다는 것인데, 이 파동이란 것이 유한자원이다 보니 예전부터 어떻게 사용하면 최대한 많은 사람들이 빠르게 사용 할 수 있을까 많은 연구가 있었다. 처음에는 그냥 브로드캐스트 라디오 방송이나 TV방송에서만 쓰였고, 무선 전화가 막 나왔을 때에도 소수의 사람들이 아날로그 사운드를 주고받는 수준이었으므로 주파수 대역을 쪼개서 할당 해 주면 되었다. 하지만 무선통신이 일반화 되고 휴대폰 사용자도 기하급수적으로 증가하면서 기존 방식으로 주파수를 .. 2013. 10. 19.
History of Cellular Systems First generation wireless system - Frequency division multiplexing을 이용해서 analog voice전송만 가능하였다. Second generation wireless system - 좀 더 효율적인 사용을 위해 Time division multiplexing을 사용하였다. - 달리는 차량에서도 무선통신을 가능하게 하는데 주안점을 두었다. - SMS 전송이 가능하게 되었다. Third generation wireless system - IMT-2000 : 2000GHz의 주파수 대역을 사용함, 전세계 표준 통일 - Global Roaming이 가능함 - 초당 2mbps의 속도를 지원하며 영상 통화가 현실화됨 2013. 10. 17.
인터넷 통신 정리 half-close 1. 소켓의 우하한 종료를 위해선 shutdown함수를 이용한다. 2. 일방적인 close는 다른한쪽에서 전송할 데이터가 남았을때 문제가 된다. DNS in_addr*이 아닌 char*인 이유 : IPv4만을 위해 정의된 구조체가 아니기 때문 IPv6 1. IPv4의 주소 부족 문제를 해결하기 위한 대응책 (NAT, DHCP를 이용한 임시방편에는 한계가 있음) 2. 유무선 인터넷을 이용한 단말기 서비스의 효율적인 지원 3. 취약한 인터넷 보안 취약점 보완 4. 32비트 -> 128비트 주소 사용. 부족문제 근본적으로 해결 (주소에 계층정보, 범위정보 등을 포함할 수 있음) 5. 불필요한 헤더 필드 제거, 헤더 필드 구조의 단순화, 패킷 속도 향상 6. IPv6 패킷 구성 : 기본 헤더.. 2013. 6. 15.
소켓의 다양한 옵션 소켓은 그냥 정해진 함수 3~4개만 쓰면 사용 할 수 있는 편한 것이라고들 인식하지만, 사실 더 깊게 들어가면 정말 다양한 옵션들이 있다. 일반적으로 간단한 데이터 송수신 정도의 프로그래밍에서는 아무것도 건들일 필요 없이 그대로 쓰면 되지만 점점 고급 프로그래밍을 하게 되면 그 특성에 맞기 옵션들을 조작 해 줘야 한다. (조작 안해도 사용 할 수 있지만 조작 해 주면 더 좋은 성능이 나고, 프로그래밍하기도 편해진다.) 소켓의 옵션은 아.주. 많지만 일단 자주 사용되는 몇 가지만 뽑아 보자면 아래와 같다. Protocol Level Option Name 설명 Get Set SOL_SOCKET SO_SNDBUF SO_RCVBUF SO_REUSEADDR SO_KEEPALIVE SO_BROADCAST SO_OO.. 2013. 6. 15.
File System Implement 하드디스크는 page array이다. 메모리와 연관지어서 생각하면 된다. 프로세스를 메모리상에 allocation 하는것과 파일을 디스크에 allocation 하는것은 같은 원리이다. Memory에서는 contiguous allocation 방식이 있었고 non-contiguous인 paging방식이 있다. 하드디스크도 똑같다. 하드디스크엔 추가적으로 한개 더 있다. fopen함수를 쓰면 파일 포인터를 return한다. 이 포인터는 OS에서 정의하는 파일 table의 인덱스정보이다. 파일을 read할땐 실제로는 두개의 자료구조가 열린다. per-process open-file table, system-wide open file table. 일단 system-wide open file table이 한개 열.. 2013. 6. 12.
가상 메모리(Virtual Memory) 이론 및 페이지교체 알고리즘 Virtual Memory 주기억장치의 부족한 physical memory를 보조기억장치를 이용해서 가상으로 늘려 준다. Demand Paging 어떤 것을 하드에 두고 어떤 것을 실제 메모리에 올릴 것인가를 판단하는 기준이다. 여러가지가 있지만 일반적으로 사용되는것이 demand paging이므로 이에 대해서만 설명한다. demand paging은 말 그대로, 어떤 알고리즘에 따라서 미리 올려 두는 것이 아니라 실제 사용되려고 할때(demand 되었을때) 메모리에 올리는 방식을 말한다. 어떻게 보면 무척이나 당연한 이야기이다. 이 방식은 아래와 같은 장점이 있다. Less I/O needed Less memory needed Faster response More users Virtual memory는 .. 2013. 6. 12.
Banker's Algorithm cf. Detection Algorithm Deadlock Avoidance는 거의 뱅커스 알고리즘이 다라고 보면 된다. 이름에서도 알 수 있듯이, 리소스 할당을 돈을 빌려주고 갚은 은행의 업무에 비유하여 고안된 알고리즘이다. 간단하게 예를 들어, 은행에 돈이 1000만원 있다. 그리고 3명의 고객이 은행에서 돈을 빌린다. 은행은 고객이 원하는 돈을 다 빌려 주면 바로 반환 받을 수 있다. 하지만 돈을 다 빌려주기 전까지는 강제로 반환받지 못한다. - 고객1이 총 600만원을 빌리고자 한다. - 고객2이 총 800만원을 빌리고자 한다. - 고객3이 총 400만원을 빌리고자 한다. 지금 현재 상태는 safe하다. 1-2-3, 1-3-2, 2-3-1 등등 모든 경우가 다 가능하다. 한꺼번에 필요한 돈을 다 빌려주고 다시 받은 후 다음 고객에게 빌려주.. 2013. 6. 11.
Briefly compare the two heap-construction algorithms Make heap : bottom up, O(n), off-line algorithm, heapsort에 유용 Heap insert : top-down, O(nlogn), on-line algorithm, priority queue에 유용 Make heap은 shift_down을 사용하고 Heap insert(construct heap)은 insert_hep을 사용한다. shift_down은 구성된 ECBT에서 하위 서브트리부터 순서를 재조정하여 Heap을 구성하는 함수이고, insert_heap은 ECBT를 구성 해 가며 노드를 하나씩 추가해 나가는 것이다. sorting을 목적으로 할 경우 Make heap은 주어진 키값으로 ECBT를 구성 해 놓은 후 순서를 맞추기 때문에 새로운 값이 갑자기 추가되.. 2013. 6. 6.
Branch and bound, BFS 0/1 Knapsack Knapsack 알고리즘이란, 무게(크기)가 한정된 가방이 있고, 넣을 수 있는 물건의 무게(크기)와 가격이 정해져 있을 때 어떤 물건을 버리고 어떤 물건을 넣어야 최대한의 이익을 얻을 수 있는가를 구하는 알고리즘이다. Branch and Bound에 대해서는 TSP에서 설명 했으므로 바로 문제를 풀어보자. 목적에 따라 bound를 구하는 방법만 다를 뿐 다 같은 맥락이다. 1. W = 11 i pi wi pi/wi 1 20 2 10 2 21 3 7 3 12 2 6 4 35 7 5 input 값는 이런 식으로 주어진다. pi는 물건 i에 대한 profit, wi는 weight, pi/wi는 단위무게당 profit이다. 이 input은 pi/wi이 큰 순서대로 sorting되어 들어오며, sorting되지.. 2013. 6. 6.
Deadlock의 발생 조건과 해결법 데드락이 무엇인가? 두개 이상의 프로세스가 서로의 작업이 끝나기만을 기다리고 있어 둘다 영원히 끝나지 않는 상황을 가리킨다. (A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set) 예를 들어서 semaphores A and B, initialized to 1 Process1 Deadlock Process2 wait(A); wait(B); wait(B); wait(A); 데드락은 어떨 때 일어나나? 아래 4가지 조건이 모두 만족하면 데드락이 발생할 가능성이 있다. 하나라도 만족하지 않으면 절대 발생하지 않는다. Mutual exclusion : .. 2013. 5. 30.
Branch and bound 기법을 이용한 TSP Branch(가지)와 Bound(범위) 기법이란 "최적의 경우"를 찾는 알고리즘으로써, '최소한 이정도는 되어야 답이 될 가능성이 있다' 라는 범위(Bound)를 정 해두고 범위를 벗어나는 값들은 가지치기(Branch)해가며 결과값을 추적한다. 이 알고리즘으로 풀 수 있는 문제는 대표적으로 Knapsack과 TSP가 있는데, 인터넷에 있는 예제들은 대부분 Knapsack에 관한 예제이므로, 여기선 TSP를 풀어 보도록 하자. 0 5 2 4 1 6 0 5 4 3 2 3 0 4 5 2 3 4 0 1 4 2 1 3 0 위와 같은 input이 있다. 그래프는 그리지 않겠다. 이번 알고리즘은 확실히 Matrix로 보는게 더 편하다. 매트릭스를 어떻게 보는지 모르는 분들을 위해 간단하게 설명 드리자면 (1, 1),.. 2013. 5. 28.
[C언어 소스] Backtracking을 이용한 N-Queen 문제 해결법 일단 N-Queen문제가 뭘까? 이 문제의 목적은 잘 모르겠으나 알고리즘을 공부하다 보면 자주 보이는 문제이다. 이 문제를 푸는 방법도 참 여러가지다. 일단 이 문제는 이름대로 장기판에 여왕말을 놓는 문제인데, 이 여왕말이 다 적이다. 어떤 여왕말이든 다른 여왕말을 먹을 수 있다는 것이다. 하지만 그걸 못 먹도록 하는게 이 문제의 핵심이다. 즉, 모든 여왕말이 다른 여왕말이 바로 공격할 수 있는 거리에 있는 것이다. 그 말인 즉슨 어떤 여왕말이 다른 여왕말을 먹으면 그 여왕말은 또 다른 말에게 먹히기 때문에 아무도 움직일 수 없는 상태인 것이다. 예를 들어 4x4의 체스 판에서는 Q Q Q Q 이런 구도라면 어떤 여왕말도 쉽사리 움직 일 수 없다. 그리고 5x5라면 Q Q Q Q Q 이런식의 결과가 나올.. 2013. 5. 26.
Internet transport protocols : TCP and UDP TCP connection-oriented: setup required between client and server processes reliable transport between sending and receiving process flow control: sender won’t overwhelm receiver congestion control: throttle sender when network overloaded does not provide: timing, minimum throughput guarantees, security UDP unreliable data transfer between sending and receiving process does not provide: connecti.. 2013. 4. 17.
인터넷 계층 계층화를 하는 이유 - 크고 복작한 시스템의 잘 정의된 특정 부분을 논의 할 수 있도록 해 준다. (explicit structure allows identification, relationship of complex system’s pieces) - 시스템의 다른 요소들에 영향을 주지 않고 서비스 구현을 변화시킬 수 있도록 해준다. (change of implementation of layer’s service transparent to rest of system) 인터넷 프로토콜 스택 application - transport - network - link - physical 프로토콜 데이터 유닛 message - segment - datagram - frame 인터넷 프로토콜 스택을 하나씩 지나면서.. 2013. 4. 17.
Delay in packet-switched networks dnodal = dproc+ dqueue + trans + dprop 패킷 스위칭에서 한 패킷이 한 노드(호스트 혹은 라우터)에서 다른 노드까지 가는 경로 중 생기는 지연을 "노드 지연(nodal delay)"이라고 한다. 대표적인 delay는 4개가 있다. 1. 처리 지연(processing delay) 패킷의 헤더를 조사하고 그 패킷을 어디로 보낼 것인가 파악 하는데 걸리는 시간. 비트 수준에서의 오류 조사 시간도 포함한다. 2. 큐잉 지연(queuing delay) 링크로 전송되기 전에 큐에서 차례가 올 때 까지 기다리는 시간. queuing delay를 정도를 측정하기 위한 척도로 트래픽 강도(traffic intensity) 가 중요하게 사용된다. 트래픽 강도를 계산하는 공식은 아래와 같다. L.. 2013. 4. 17.
Chainging Coin System 관련 Suppose you are in the wonder land in which the coin changing system is not governed by the greedy strategy. There are only 4 coins cl = 1, c2 = 3, c3 = 7, and c4 = 11 in the country. (a) Construct N[0..21] and P[0..21] for changing 21 wons. (b) Write a recursive program "void print_coins (int x)" to print optimal coins for x wons. You must assume that array P[0..21] is global to this program. (.. 2013. 4. 15.
Operating System A computer system can be divided into four components Hardware, Operating System, Application Program, Users(People, machine, other computer) 기본적인 3가지 Process Management Memnory Management Storage Management 정의 OS is resource allocator OS is control program No universally accepted definition 특징 1. I/O devices and the CPU can execute concurrently. I/O CPU는 같이 실행 될 수 있다. 2. Each device controller .. 2013. 4. 12.
여러가지 관계해석식 표현법과 예제 *관계 대수와의 비교 관계 대수식은 절차적(procedural)인 반면에 관계 해석식은 비절차적이다. 그러나 두 언어의 표현력(expresive power)은 동등하다. 튜플 관계 해석식 셀렉트 연산 : { t | EMPLOYEE(t) and t.SALARY>5000 } 프로젝트 연산 : { t.FNAME, t.LNAME | EMPLOYEE(t) } 셀렉트 + 프로젝트 : { t.FNAME, t.LNAME | EMPLOYEE(t) and t.SALARY > 50000 } Ex1) Research 부서에서 일하는 모든 사원들의 이름과 주소를 검색하라 { e.FNAME, e.LNAME, e.ADDRESS | EMPLOYEE(e) and (∃d) (DEPARTMENT(d) and d.DNAME = ‘Resea.. 2013. 1. 12.
반응형

티스토리툴바